Convex Polygon Rasterization Tutorial

This tutorial describes rasterization of convex simple polygons. A polygon is convex if the line connecting any two points inside the polygon does not leave the polygon boundaries. If the line leaves polygon boundaries then it is concave. Rasterization of such polygons is costly and is best avoided.

The algorithm of convex polygon rasterization finds the horizontal lines starting on left and ending on the right edges of a polygon. Starting from the line connecting the first vertex to the next, the line rasterization algorithm is applied to find each pixel belonging to that line. The point's x value is added to the minimum or maximum array of x values at its corresponding y value, depending if x is smaller or greater than the value already there. The minimum-x array is initialized to the maximum integer value, while the maximum-x array is initalized to the minimum integer value. Doing this will make sure that the initial values are always added to the array (any integer value is greater than the minimum and lesser than the maximum). When all the edges of a polygon are traversed the horizontal lines are drawn at each y from the minimum to the maximum x values.

Back when the drawing was done in 13h mode and the resolution of the screen was constant, the array of maximum and minimum x values was the same size as the height of the screen. In that case a point would be added to the array at index eqaul to its y value. However, when the screen is not of the constant height, it is better to dynamically allocate memory for the array of max/min x values. So doing will no longer enable us to add a point at its y value, and instead a point at height y is added at index y - min_y, where min_y is the minimum y value of all the vertices of a polygon. The length of the array is going to be max_y - min_y + 1, where max_y is the maximum y of the vertices.

The next diagram shows what the array contains before (a) and after (b) the max/min values were added to it:

Here are the steps in convex polygon rasterization algorithm. They are also labeled in the source code below:

1. Find smallest and largest y values for all the vertices describing the polygon. (small_y, large_y)
2. Make array(s) of length large_y - small_y + 1 that will contain min/max x coordinates of all horizontal lines. Initialize all minimum values to INT_MAX and all maximum values to INT_MIN.
3. Going through all the vertices, connect each vertex to the next until the first one is reached. For each non-horizontal line formed use the line rasterization algorithm, only instead of drawing the point place its x value in min/max array at index y - small_y. x coordinate is placed into minimum array if its value is less than the one already there, or/and is placed into maximum array if its value is greater.
4. Traverse through the min/max array and draw horizontal lines from min_x to max_x.

Source Code

Please email me with suggestions and/or bugs at:
myp@andrew.cmu.edu or mikepolyakov@hotmail.com