|Previous||Table of Contents||Next|
Listing 38.2 isnt particularly interesting; it merely draws each horizontal line in the passed-in list in the simplest possible way, one pixel at a time. (No, that doesnt make the pixel the fundamental primitive; in the next chapter Ill replace Listing 38.2 with a much faster version that doesnt bother with individual pixels at all.)
Listing 38.1 is where the action is in this chapter. Our goal is to scan out the left and right edges of each polygon so that all points inside and no points outside the polygon are drawn, and so that all points located exactly on the boundary are drawn only if they are not on right or bottom edges. Thats precisely what Listing 38.1 does. Heres how:
Listing 38.1 first finds the top and bottom of the polygon, then works out from the top point to find the two ends of the top edge. If the ends are at different locations, the top is flat, which has two implications. First, its easy to find the starting vertices and directions through the vertex list for the left and right edges. (To scan-convert them properly, we must first determine which edge is which.) Second, the top scan line of the polygon should be drawn without the rightmost pixel, because only the rightmost pixel of the horizontal edge that makes up the top scan line is part of a right edge.
If, on the other hand, the ends of the top edge are at the same location, the top is pointed. In that case, the top scan line of the polygon isnt drawn; its part of the right-edge line that starts at the top vertex. (Its part of a left-edge line, too, but the right edge overrides.) When the top isnt flat, its more difficult to tell in which direction through the vertex list the right and left edges go, because both edges start at the top vertex. The solution is to compare the slopes from the top vertex to the ends of the two lines coming out of it in order to see which is leftmost. The calculations in Listing 38.1 involving the various deltas do this, using a rearranged form of the slope-based equation:
Once we know where the left edge starts in the vertex list, we can scan-convert it a line segment at a time until the bottom vertex is reached. Each point is stored as the starting X coordinate for the corresponding scan line in the list well pass to DrawHorizontalLineList. The nearest X coordinate on each scan line thats on or to the right of the left edge is selected. The last point of each line segment making up the left edge isnt scan-converted, producing two desirable effects. First, it avoids drawing each vertex twice; two lines come into every vertex, but we want to scan-convert each vertex only once. Second, not scan-converting the last point of each line causes the bottom scan line of the polygon not to be drawn, as required by our rules. The first scan line of the polygon is also skipped if the top isnt flat.
Now we need to scan-convert the right edge into the ending X coordinate fields of the line list. This is performed in the same manner as for the left edge, except that every line in the right edge is moved one pixel to the left before being scan-converted. Why? We want the nearest point to the left of but not on the right edge, so that the right edge itself isnt drawn. As it happens, drawing the nearest point on or to the right of a line moved one pixel to the left is exactly the same as drawing the nearest point to the left of but not on that line in its original location. Sketch it out and youll see what I mean.
Once the two edges are scan-converted, the whole line list is passed to DrawHorizontalLineList, and the polygon is drawn.
Listing 38.1 handles zero-length segments (multiple vertices at the same location) by ignoring them, which will be useful down the road because scaled-down polygons can end up with nearby vertices moved to the same location. Horizontal line segments are fine anywhere in a polygon, too. Basically, Listing 38.1 scan-converts between active edges (the edges that define the extent of the polygon on each scan line) and both horizontal and zero-length lines are non-active; neither advances to another scan line, so they dont affect the edges being scanned.
Ive limited this chapters code to merely demonstrating the principles of filling convex polygons, and the listings given are by no means fast. In the next chapter, well spice things up by eliminating the floating point calculations and pixel-at-a-time drawing and tossing a little assembly language into the mix.
|Previous||Table of Contents||Next|