Building a 3D Portal Engine - Issue 08 - Polygon Filling by (19 February 1999) Return to The Archives
 Introduction This is the last article about the basics of 3D coding for a while. After this one, we'll dive straight in the essentials of Portal rendering, starting with the most simplistic forms, and advancing to the better ones while on the way exploring the opportunities that they bring.

But before we get to that, there's one last issue that has to be addressed. You can do wire polygons. That's easy. But how are those incredible cool perspective correct bilinear filtered bumpmapped tilable true-color polygons done in real-time? Well, it's actually not too hard. There are a few things to explain, and let's get this article structured this time:
• Generic polygon rendering: Tracing outlines
• Interpolate - interpolate - interpolate
• The buzzwords, and how to do it - Phong, bumps, bilerp
• So, to start with the first one: Tracing outlines. No matter how your final polygon should look, this is how to start. All polygon fillers that I ever saw use this approach.

To fill a polygon, you draw horizontal (or in some cases, vertical) lines, from left to right, top to bottom, until you have drawn the entire polygon. So, you have to start with finding out what the start points and end points of these lines are. That's what I call 'outline tracing' or 'edge tracing'.

It's done like this: First define two arrays, with as many elements as there are lines on your screen. The first array is called 'x_start', the second 'x_end'. Next, find out wich lines your polygon covers. This can be done by finding out what the minimum and maximum y coordinates of any of the vertices of your polygon are. Then, for this range, initialize the arrays with impossible values. For example, x_start could be set to '10000', x_end to '-10000'. Finally, process the edges. Interpolate from the start of the edge to the end, skipping one screen line per iteration. Compare the x value of each line the edge covers with the minimum and maximum values that you keep in the arrays, and replace those values if neccessary.

Here's some pseudo-code:

 ``` // Declare the arrays int x_start[SCREEN_HEIGHT], x_end [SCREEN_HEIGHT]; // Determine first and last line that the polygon covers int y_min = SCREEN_HEIGHT+1; int y_max = -1; for (int i=0; i ymax) ymax = polygon.vertex(i).y; } if (y_min == y_max) return; // Initialize arrays for this range for (i=y_min; i x_end[p]) x_end[p]=xpos; // Advance one screen line x1 += deltax; } ```

At the end of this process, x_start and x_end contain exactly what you need: The contours of the polygon. Note that there is another way to trace the outlines of triangles; in that case it's more efficient to skip the arrays and trace the left and right side of the polygon simultaneously. I will not explain this technique, since I hardly ever use it. You could add it as a special case to your 3D engine, for polygons that are (still) triangles after clipping.

OK, next important thing for polygon filling is INTERPOLATION. You have already seen some interpolation in the pseudo code, where the x position of the edge is interpolated from the minimum y-value to the maximum y-value. Filling the lines from left to right with a single color requires no further interpolation of course, but as soon as you want to do even a little bit more, you'll need a big dosis of interpolation.

Imagine that you assigned a texture to your polygon. Now each vertex has not only an 'x' and 'y' position, but also an 'U' and 'V' value. In this case, you need four extra arrays: u_start, u_end, v_start and v_end. During the edge tracing, you should now not only remember the x-position per screen line, but also the U-value at the start and end of each line, plus the V-value. The U and V delta's can be calculated the same way as the x_delta in the above pseudo code too.

Once you have your arrays filled with x, U and V values, you want to draw the spans. And here's the interpolation again: Just like a loop that draws from x_start to x_end for a given line interpolates from x_start to x_end, you should interpolate u_start to u_end, and v_start to v_end. So, you need a delta-U and delta-V PER LINE. It's calculated as follows:

 ``` delta_u = (u_end[line]-u_start[line])/(x_end[line]-x_start[line]); delta_v = (v_end[line]-v_start[line])/(x_end[line]-x_start[line]); ```

So, when drawing pixel 10 from a span, you should draw the texel at the U/V location that can be determined as follows:

 ``` u_position = u_start[line] + delta_u * 10; v_position = v_start[line] + delta_v * 10; ```

Of course, just like in the pseudo code for the edge tracer, you need to decide wheter you want to use floating point or fixed point for your delta's, since integer values are clearly not good for storing delta's that are smaller than 1.

Every polygon filler is based on these principles. With this knowledge in mind, let's explore some techniques that you'll see pretty often in the feature-lists of 3D engines:

This is the name for interpolating color values over a polygon. Each vertex is assigned an intensity or RGB color, wich is then first interpolated over the edges, just like the texture in the above example, and then over the lines, again, just like the texture. You can either interpolate a single value ('intensity'), to get a single light color, or interpolate red, green and blue separately.