[ / main / writing / polygons ]

    Polygon Fillers



1997 Jeff Weeks and Codex software

Sample source code:
polys.zip




    Introduction




Filling a polygon is a fairly simple process. Filling a polygon effeciently and effectively, however, is a whole other matter. We must be able to draw the polygon extremely fast and in a manner than adjacent polygons never overlap, or leave gaps between each other. This is where some planning is needed.




    Flat Colour Filling




The simplest polygon filler to understand is, ofcourse, the flat colour filler. It simply fills the whole polygon with the same colour. Now, to be as efficient as possible, we will try to break up our polygon into horizontal spans so that we can use a very effecient horizontal line function. One of the fastest routines in graphics programming. For the time being we will also restrict our polygons to convex polygons, or, polygons where for every y coordinate there are two, and only two, corresponding x coordinates. In otherwords, by drawing a horizontal line anywhere in the polygon, it should only cross two boundaries of the polygon.




So, our first step will be to convert this polygon into horizontal spans that we can feed to our horizontal line function. We can do this, simply, by rasterizing, or scanning, along the lines of the polygon, and storing the coordinates of each point on the line in a global array.




Okay, so that may not have completely sunk in. Here's what we'll do. First off, create a structure such as the following:

    typedef struct Scanline {
      int startx, endx;
    }

Now make an array of these Scanline structures. You should have as many scanline structures as you do scanlines. For example, in a 640x480 screen, you should have an array of 480 Scanline structures.




What we must do now is scan along each line of the polygon and store it's coordinates in the appropriate Scanline structure. Before we do so, however, we should first set the startx, and endx variables in each structure to an imposible value. Why? Well, when we're adding x coordinates to the Scanline structure we need to know where to put them; In startx, or endx. We can figure this out by testing if startx equals the impossible value. This means it hasn't been initiated with an x coordinate and we store our value in startx. Otherwise we'd store our value in endx.




So, it still remains to be seen exactly how we'll scan along the polygon lines. However, the answer is quite simple. A regular line drawing routine will almost suffice for what we need. There's only one problem with a regular line drawing algorithm; It can possibly give more than one x per y. Remember, we want only two x's per scanline, and with a convex polygon, this means only one x per polygon line.




As you can see, the regular line function is providing us with two x's per y in this example while the rasterizing line function is giving us only one, which is what we want. You can write a simple line rasterization function by looping for the y delta and calculating the coresponding x by continually adding an increment value obtained by dividing the two deltas of the line. My code uses a fixed point math rasterization function to achieve this.




Not only is the fixed point method fast, it also makes sure polygons never overlap or leave gaps. How? Well, just take a look at the above picture. The x's that we were given to use were on the left of the actual, true line. Assuming you use the same function for all lines that means that the right edge of the polygon will butt up perfectly with adjacent polygons. The same would be true if the rasterizing function returned only the pixels on the right side of the true line. It doesn't really matter, as long as it's consistant.




Okay, now that you've scanned along each polygon line and stored the x coordinates in the Scanline array, all you must do is draw horizontal lines between each pair of x coordinates. Ofcourse, don't draw lines where the startx value is still the impossible value. This means that the polygon does not consist of any lines on that particular scan line. Also, if endx ends up being the impossible value, set it to startx and plot only a pixel.




There's just one more thing of importance here. When rasterizing your lines you should always ignore the first point. Why? Because two lines will share this point. If you were to include this point then the other line would as well, and therefore your startx and endx values for that scanline would be identical, and a single pixel would be plotted insead of a line. By skipping the first pixel you let the other line which contains that point to rasterize it, and therefore, it is only included once in the scanline structure, as it should be.




Okay, so to recap here. The steps to render a polygon are as follows:

    . Set the Scanline structures up with impossible values
    . Rasterize each line in the polygon into the Scanline structure
    . Draw the horizontal lines defined in the scanline structure



It's really that simple.




    Goraud Shading Filling




Now that you know how to fill a regular solid colour polygon, lets go on to goraud shading a polygon. This technique is really not that much different. Infact, it's almost exactly the same. The steps you take are identical, but differ inside the rasterization function.




The rasterization function of each line must now take into account the colours of the polygon. Normally, with a solid colour filler, you would define your polygon as a simple array of coordinates. With a goraud shader, however, you must provide a colour value along with those coordinates. In other words, the polygon is defined as an array of vertices, and a colour value for each vertex.




The job of the rasterization function, now, is to interpolate between the coordinates, as we have been doing, but to also interpolate between the colour values at each endpoint of the line. This can be done using the same fixed point technique used in the solid filler. Now, since we're interpolating between colours, we'll also need a place to put them. For this reason the Scanline structure must be changed to something like the following:

    typedef struct Scanline {
      int startx, endx;     // the starting and ending x's
      int startc, endc;     // the starting and ending colours
    }



Now you must write a horizontal line function to draw a line from startx to endx while interpolating the colours from startc to endc. It's easier than you think, I'll bet. Check out my code for an example.




So, now the process is simple. Ofcourse, any text is further explained by presenting working source code, and so I have done just that. If any of these descriptions seem less than ideal then please take a look at the source code and perhaps it'll all start coming together. The concept is really very simple, but difficult to explain on paper.




    Texture Mapped Filling




Well, when you think about it, texture mapping and goraud shading are very similar. Afterall, goraud shading is, really, texture mapping a palette onto the polygon. Texture mapping just goes one step further and creates a picture instead of a gradient.




So, as you can guess, the difference's will be in the rasterization function, which must now interpolate between texture coordinates, as well as the horizontal line function, which must be able to draw a horizontal line using the texture provided. Here's how it all comes together.




First, the rasterization function. This function must now interpolate four different things. The x and y values of the polygon line, and the x and y values of the texture values specified as end points. In other words, to define a polygon for texture mapping you must define an array of points, and a texture coordinate for each point. This means our Scanline structure will change again:

    typedef struct Scanline {
      int startx, endx;     // the starting and ending x's
      int startc, endc;     // the starting and ending colours
      int starttx, startty; // the starting and ending texture coordinates
      int endtx,   endty;
    }



You'll notice that we left the goraud shading variables in there. That's probably a good idea because then you can use the same Scanline structure for both Goraud shading and texture mapping, not to mention Goraud shaded texture mapping :)




Okay, so now you rasterize each of the four elements into the scanline structure and then draw horizontal lines between them. The horizontal line function must now be able to draw a horizontal lines while interpolating the texture coordinates. Again, this is a fairly simple task. Just take a look at my source code for an example of this.