Polygon Rasterization (C)

From LiteratePrograms
Jump to: navigation, search

This article will describe a way to efficiently rasterize an arbitrary polygon, using highest quality permitted by a raster display: anti-aliasing and sub-pixel positioning, and using the cheapest operation allowed by a CPU: mostly addition and bit-shifting. With this generic algorithm, we will then see how to draw some common polygons: line segment with variable width and square cap, polygon path with miter join, square cap and variable width.

The algorithm will be based on the scanline polygon fill. The implementation will be written in C99 and using SDL as a rendering backend.


[edit] Scanline fill

This section will just briefly explain the idea behind the scanline polygon-fill algorithm. A polygon will be described by a series of points, where each points begin a segment with the next one, including the last point that automatically connects with the first point.

The scanline fill algorithm consists, for each scanline the polygon may alter on the bitmap, in finding all the points that intersect with this scanline and all the segments. Each intersection points is then sorted according to its ascending x coordinate. The polygon is finally filled by taking the sorted points by pairs and filling with the given color between each of these pairs.

To efficiently find the intersection points, segments are usually first sorted in ascending order using their lowest y coordinate (considering the origin of the coordinate system being at the top left corner, as it is usual for computer raster display). Horizontal segments (y1 == y2) can be completely discarded. That way the polygon can be rendered in passes, which are a set of scanlines where the amount of potential intersecting segments does not change.

The sub-pixel positioning and anti-aliasing will be implemented by upscaling the coordinate system by the factor 16. This number is not arbitrary, assuming a color depth of 8bit per channel. 8bit means that there is 256 possible intensities per channel. If we upscale the coordinate by 16, each pixel of the display will cover a 16 by 16 area in our upscaled polygon, where up to 256 pixels from the polygon can fit. Counting the number of pixels that fit, will actually give us the alpha component to modulate the actual color of the polygon.

Knowing all of this, we can already defined some classical datatypes we will need for our algorithm, along with the prototype of the filling function:

<<Image data structure>>=
typedef struct Image_t *       Image;
typedef uint8_t *              DATA8;
typedef uint16_t *             DATA16;

#define BPP        4
#define VALUES     (1<<BPP)
#define HALF       (VALUES/2)
#define MASK       (VALUES-1)
#define EPSILON    (1/256.)
#define FTOI(v)    (((int)(v) << BPP) | (int) ((v) * (1<<BPP)))

struct Image_t
	int   width, height, bpp;
	int   stride;
	DATA8 bitmap;

int FillPolygon(Image img, int * pts, int cnt, uint32_t col);

The function is supposed to return 1 is the drawing is successful, 0 otherwise. This function will have to allocate a single small memory buffer, and be sure that parameters are sane. The array of points will have to be upscaled before calling the function. To convert floatting point numbers into the fixed point coordinate system, it is possible to use the FTOI() macro.

[edit] Iterator

A huge part of the algorithm will consist in enumerating all the x coordinates there is in a segment while iterating along the vertical axis (y). This kind of job is perfectly handled using Digital Differential Analyzer (DDA). A brief explanation about DDA can be found here, the version we will be using here is slightly different. Given two points (x1, y1) and (x2, y2), iterate between y1 and y2 (1 step increment), and linearly interpolate the corresponding x value. Therefore, we can define the following functions/datatype:

<<Iter structure>>=
typedef struct Iter_t          Iter;

struct Iter_t
	Iter * next;
	int    x, y, err, sx, rem, quot;
	int    dx, dy, xe, ye;

<<DDA helper functions>>=
static void InitDDA(Iter * iter, int xs, int xe, int ys, int ye, int cy)
	/* Pre-condition: ye > ys */
	div_t q = div(iter->dx = xe - xs, iter->dy = ye - ys);
	iter->y    = ys;
	iter->ye   = ye;
	iter->x    = xs;
	iter->xe   = xe;
	iter->err  = iter->dy >> 1;
	iter->rem  = abs(q.rem);
	iter->quot = q.quot;
	iter->sx   = (xs < xe ? 1 : -1);
	if (cy > ys) /* Clipping */
		q = div((cy - ys) * iter->dx, iter->dy);
		iter->x   = xs + q.quot;
		iter->y   = cy;
		iter->err = iter->dy - q.rem + (iter->dy >> 1);

static inline void IterDDA(Iter * iter)
	iter->y ++;
	iter->x += iter->quot;
	iter->err -= iter->rem;
	if (iter->err <= 0)
		iter->x += iter->sx, iter->err += iter->dy;

#define ISDDAEND(iter) ((iter).y >= (iter).ye)

The extra cy parameter for InitDDA() is used for vertical clipping. The interpolated value will be stored in Iter.x.

[edit] Segment sorting

Before starting the rasterization process, we need to sort the segment according to their lowest y coordinate. We will use a simple sort insertion algorithm, although with a bit more code we could have used the standard function qsort() from <stdlib.h>.

<<PolyVertex datatype>>=
typedef struct PolyVertex_t *  PolyVertex;
struct PolyVertex_t
	int x1, y1;
	int x2, y2;

<<Segment sorting>>=
PolyVertex vertex, v;
int        i, y, yend, vcnt, w;
DATA16     scanline;

w = img->width;
scanline = malloc(cnt * sizeof *vertex + w * 2);
if (scanline == NULL) return 0;
vertex = (PolyVertex) (scanline + w);

/* Sort vertex according to increasing y coordinate */
for (i = 0, yend = 0, vcnt = 0; i < cnt; i += 2)
	PolyVertex_t vtx;
	int * sec = i + 2 < cnt ? pts + i + 2 : pts;
	if (pts[i+1] == sec[1]) continue; /* Horizontal line = skip */
	/* Be sure y1 < y2 */
	if (pts[i+1] < sec[1])
		vtx.x1 = pts[i],   vtx.x2 = sec[0],
		vtx.y1 = pts[i+1], vtx.y2 = sec[1];
		vtx.x1 = sec[0], vtx.x2 = pts[i],
		vtx.y1 = sec[1], vtx.y2 = pts[i+1];

	/* Vertical clipping */
	if (vtx.y2 < 0 || vtx.y1 >= (img->height<<BPP)) continue;
	/* Sort insert */
	for (y = 0, v = vertex; y < vcnt && vtx.y1 > v->y1; y ++, v ++);
	if (y < vcnt)
		memmove(v+1, v, (vcnt-y) * sizeof *v);
	*v = vtx; vcnt ++;
	if (vtx.y2 > yend) yend = vtx.y2;
if (yend > (img->height<<BPP))
	yend = img->height<<BPP;

scanline is a memory buffer we will need in the rasterization process. We allocate this buffer at the same time, just to avoid some extra boiler-plate code. yend will be used to track when the last scanline has been processed.

[edit] Complete algorithm

[edit] Drawing line segment

[edit] Sample test program

[edit] Drawing polygon path

Download code