[size="5"]What

Rendering convex n-gons (shapes that have more than 2 vertices) to the frame buffer can be a challenge, especially if you wish to accomplish this with any amount of speed. I'll outline a very simple and fast algorithm.

[size="5"]Why

Some polygon renderers can benefit greatly by rendering n-gons rather than triangular patches. In a doom-style environment, this would (on average) drop the number of polygons to render by 50%. This does not mean that you'll render less screen-space. But it does cut down on the time spent in the overhead of triangular scan-conversion setup.

In my past experiences, with a generic dataset (includes indoor and outdoor scene data with objects in the environment) the average reduction from triangles to n-gons was typically 50%.

Clipping (2D or 3D) usually results in n-gons that must be triangulated for rendering. You can avoid this step by simply rendering the clipped n-gons themselves.

As you'll see, the routines outlined here will perform very well for triangular polygons as well (comparable to a dedicated triangular patch renderer.)

[size="5"]How

[size="3"]Define

Let's start off by defining our basic model of an n-gon (the input to our renderer).

Since an n-gon has an unlimited number of vertices (which may be limited for memory or speed purposes) we'll need a way to store our n-gon. For this example, we'll use a linked list rather than a static array of vertices for each polygon. This linked list MUST contain vertices that appear in a specific order -- we'll assume clockwise for this explanation, but it really doesn't matter. It also shouldn't matter which vertex is stored in the list first, as long as the last vertex in the list connects to the first, closing the polygon.

Also, for the purpose of this example, we'll assume that the polygon is non-textured, Lambert shaded (i.e. a constant shade across the entire polygon, often referred to as "flat shaded"), and rendered on screen, from top to bottom.

For this example, our vertex list is defined as:

`typedef struct s_vert`

{

int x, y;

struct s_vert *next;

} sVert;

And our polygon is defined as:

`typedef struct s_poly`

{

sVert *verts;

char color;

} sPoly;

For simplicity, we'll assume our X and Y values are fixed-point values (stored in 32-bit integers) and there will be no sub-pixel correction applied.

One final note before I go on... none of the code in this WWH was compiled or even tested. It is simply here as an example to aid the text in explaining the processes involved.

[size="3"]Setup

Since we'll be rendering from top-to-bottom, we'll need to find our top vertex, so scan through the list of vertices and locate that top vertex (this assumes we know our polygon is stored in "poly"):

`sVert *pTop = poly.verts;`

sVert *pVerts = poly.verts->next;

for( ; pVerts; pVerts = pVerts->next)

{

if (pVerts->y < pTop->y)

pTop = pVerts;

}

Later, we'll need to discern the left edge from the right edge, so make two copies of this top vertex. These will reperesent the top of the left edge and top of the right edge.

`sVert lTemp = *pTop; // copy`

sVert rTemp = *pTop; // copy

sVert *lTop = &lTemp;

sVert *rTop = &rTemp;

int currentY = pTop->y;

Starting at the top vertex, calculate the edge deltas for the edges to the left and to the right. Since your polygon's vertices are oriented in clockwise order in every case (unless you decide you want to render back-facing polygons) the left edge will always be defined as the current vertex (top) and the previous vertex. The right edge will always be defined as the current vertex (top) and the next vertex.

Keep in mind that since the vertices are stored in a list, you may have to wrap to the beginning or end of the list to get the previous or next vertex (getPrev() and getNext() account for the this, and should manually wrap to the beginning or end of the list). These are the bottoms of the left and right edges, with their deltas:

`sVert *lBot = getPrev(pTop);`

sVert *rBot = getNext(pTop);

float lDelta = calcDelta(&lTop, &lBot);

float rDelta = calcDelta(&rTop, &rBot);

int lHeight = lBot->y - lTop->y; // Height of the left edge

int rHeight = lBot->y - lTop->y; // Height of the right edge

`for(;;)`

{

` int height = MIN(lBot->y - lTop->y, rBot->y - rTop->y);`

` if (height < 0) break;`

` for(int i = 0; i < height; i++)`

{

renderSpan(lTop->x, rTop->x, currentY);

currentY++;

lTop->x += lDelta;

lHeight--;

rTop->x += rDelta;

rHeight--;

}

` if (!lHeight)`

{

lTop = lBot;

lBot = getPrev(lBot);

lDelta = calcDelta(& lTop, & lBot);

lHeight = lBot->y - lTop->y; // Height of the left edge

}

if (!rHeight)

{

rTop = rBot;

rBot = getNext(rBot);

rDelta = calcDelta(& rTop, & rBot);

rHeight = lBot->y - lTop->y; // Height of the right edge

}

}

[size="5"]Notes

You may notice that we've been stepping the left and right edges using the actual vertices that define the tops of those edges, not spare copies of them (we only copied the TOP vertex). If you share vertices between polygons, you'll have destroyed those vertices for the next polygon to be rendered. You'll need to create a separate copy of each vertex for stepping.

Triangles are simpler to deal with than n-gons. One major reason is because they're always planar. If you somehow get an n-gon that is not planar, you may find yourself rendering a concave n-gon (whether you plan to or not.)

Gouraud shaded n-gons can be very tricky because as they rotate in screen space, the intensities across the surface of the n-gon changes direction. Consider the following example: A 4-sided n-gon with alternate vertices having intensities of dark, bright, dark, bright. As that n-gon rotates on screen and the two dark vertices are across from each other, you'll have a dark line connecting them horizontally (gouraud interpolation will see little or no change between them, so the entire scanline will be pretty much the same shade). However, if you rotate that n-gon 90 degrees on-screen, you'll find that with the two bright vertices across from each other horizontally, the center scanline will be bright. If the gouraud were to remain constant, then the dark line would have become vertical. Instead, the intensity across the n-gon has changed. Larger n-gons tend to show this more often than small n-gons.

Unlike triangles, the deltas for U and V (texture) across the surface of an n-gon horizontally may not be constant from scanline to scanline. If the polygon was planar mapped (a texture plane was projected to get U/V coordinates for all vertices of an n-gon) then it is safe to assume that these deltas are constant from scanline to scanline. Otherwise, they're not.

However, Z and W (depth) across the surface of the n-gon does not suffer from the same potential problems as do the U and V. The delta depth across each scanline in the n-gon is constant from scanline to scanline.

I would like to extend thanks to Konstantin Putnik for his input and for finding bugs that made their way into this document as I attempted to simplify the code for the sake of explanation.