General algorithm for rastering vector image

Question

What is the general algorithm of rasterizing vector image? I've found a lot of algorithms of rasterizing primitives such as lines, circles, Bezier curves etc. But for general, what should I do? Simply, go foreach vector figure in vector picture, get its pixels and put them into raster image? Or something else?

And another question, how can I improve the time of processing using concurrency? I can, for example, separate vector figures and concurrently get their pixels. But maybe there are other methods to do this?

Answer 1

The general rasterization algorithm is this, for each polygon in the image.

(A polygon is defined as one or more closed curves made from straight line segments and parametric splines - in normal practice these are 2nd-order (conic alias quadratic) and 3rd-order (cubic) Bézier splines. These closed curves are defined so that the inside is always on the left, as the curve is traversed; so ordinary shapes run anti-clockwise and holes run clockwise.)

(i) (projection) Convert the polygon to the same coordinate system as the destination bitmap. The resolution need not be the same, and for anti-aliased images is often greater: for example, FreeType uses 64ths of pixels.

(ii) (make monotonic in Y) Where necessary, split each segment of the polygon into smaller segments that run continuously upward or downward. This stage is needed only for curved segments, and is relatively easy when using Bézier splines. The usual method is to bisect repeatedly until monotonicity is achieved. Discard all horizontal segments.

(iii) (mark the run limits) Draw each segment into a temporary bitmap. Use Bresenham's algorithm for straight lines; for curves, bisect until the line is no further than (say) 1/8 of a pixel from the real curve, then use a straight line from start to end. When drawing, mark pixels in some way to indicate (a) whether they are starts or ends of runs - downward lines are starts, and upward lines are ends; (b) the coverage - the fraction of the pixel that's inside the shape. This is where algorithms differ in the details, and where winding rules (non-zero versus even-odd) are distinguished.

(iv) (scan) Traverse the temporary bitmap, row by row. For each row, scan from left to right. Maintain a state which indicates whether the current position is inside the shape or not by (for example) adding the number stored in the bitmap to a stored number. In simple monochrome rasterization this number, written in the previous stage, will be +1 when crossing an edge into the shape and -1 when coming out of the shape. Accumulate runs of pixels in the same state. Send the runs to your drawing module: for example, FreeType emits runs consisting of a Y coordinate, start and end X coordinates, and coverage from 0 to 255. The drawing module can using the coverage as an alpha value applied to the current drawing colour, or as a mask applied to a texture.

The above is a great over-simplification but gives the general idea.

Most open-source programs use rasterization code derived from one of the following projects:

FreeType - a font rasterizer which contains both mono and anti-aliasing rasterizer modules that are relatively easy to use stand-alone - that is, for any shape, not just for fonts. I have used this system successfully in several commercial portable C++ projects.

FreeType's system was inspired by Raph Levien's Libart.

Anti-Grain is another popular and influential C++ library.

There is also the scan-line edge flag system implemented by Kiia Kallio, which looks promising and seems to be faster than Anti-Grain.

Most but not all of these libraries accept shapes made from quadratic and cubic Bézier splines as well as straight line segments. Those which don't (e.g., K. Kallio's library) take straight-edged polygons only; but it is quite easy to 'flatten' a curve into a series of line segments closer than a desired maximum distance from the actual curve. FreeType does that internally, and its code can be borrowed when necessary.