Contents

Polygon Filling? How do you do that?

---

In order to fill a polygon, we do not want to have to determine the type of polygon that we are filling. The easiest way to avoid this situation is to use an algorithm that works for all three types of polygons. Since both convex and concave polygons are subsets of the complex type, using an algorithm that will work for complex polygon filling should be sufficient for all three types. The scan-line polygon fill algorithm, which employs the odd/even parity concept previously discussed, works for complex polygon filling.

Reminder: The basic concept of the scan-line algorithm is to draw points from edges of odd parity to even parity on each scan-line.

What is a scan-line? A scan-line is a line of constant y value, i.e., y=c, where c lies within our drawing region, e.g., the window on our computer screen.

The scan-line algorithm is outlined next.

Note: The data structures used to store polygon edges and their access varies slightly from the Foley book.

---

The Moment You've Been Waiting For ... The Algorithm!

When filling a polygon, you will most likely just have a set of vertices, indicating the x and y Cartesian coordinates of each vertex of the polygon. The following steps should be taken to turn your set of vertices into a filled polygon.

1. Initializing All of the Edges:

   The first thing that needs to be done is determine how the polygon's vertices are related. The all_edges table will hold this information.

   Each adjacent set of vertices (the first and second, second and third, ..., last and first) defines an edge. For each edge, the following information needs to be kept in a table:

   1. The minimum y value of the two vertices.

   2. The maximum y value of the two vertices.

   3. The x value associated with the minimum y value.

   4. The slope of the edge.

   The slope of the edge can be calculated from the formula for a line:

   y = mx + b;

   where m = slope,   b = y-intercept,

               y₀ = maximum y value,

               y₁ = minimum y value,

               x₀ = maximum x value,

               x₁ = minimum x value

   The formula for the slope is as follows:

   m = (y₀ - y₁) / (x₀ - x₁).

   For example, the edge values may be kept as follows, where N is equal to the total number of edges - 1 and each index into the all_edges array contains a pointer to the array of edge values.

   

2. Initializing the Global Edge Table:

   The global edge table will be used to keep track of the edges that are still needed to complete the polygon. Since we will fill the edges from bottom to top and left to right. To do this, the global edge table table should be inserted with edges grouped by increasing minimum y values. Edges with the same minimum y values are sorted on minimum x values as follows:

   1. Place the first edge with a slope that is not equal to zero in the global edge table.

   2. If the slope of the edge is zero, do not add that edge to the global edge table.

   3. For every other edge, start at index 0 and increase the index to the global edge table once each time the current edge's y value is greater than that of the edge at the current index in the global edge table.

      Next, Increase the index to the global edge table once each time the current edge's x value is greater than and the y value is less than or equal to that of the edge at the current index in the global edge table.

      If the index, at any time, is equal to the number of edges currently in the global edge table, do not increase the index.

      Place the edge information for minimum y value, maximum y value, x value, and 1/m in the global edge table at the index.

   The global edge table should now contain all of the edge information necessary to fill the polygon in order of increasing minimum y and x values.

3. Initializing Parity

   The initial parity is even since no edges have been crossed yet.

4. Initializing the Scan-Line

   The initial scan-line is equal to the lowest y value for all of the global edges. Since the global edge table is sorted, the scan-line is the minimum y value of the first entry in this table.

5. Initializing the Active Edge Table

   The active edge table will be used to keep track of the edges that are intersected by the current scan-line. This should also contain ordered edges. This is initially set up as follows:

   Since the global edge table is ordered on minimum y and x values, search, in order, through the global edge table and, for each edge found having a minimum y value equal to the current scan-line, append the edge information for the maximum y value, x value, and 1/m to the active edge table. Do this until an edge is found with a minimum y value greater than the scan line value. The active edge table will now contain ordered edges of those edges that are being filled as such:

   

6. Filling the Polygon

   Filling the polygon involves deciding whether or not to draw pixels, adding to and removing edges from the active edge table, and updating x values for the next scan-line.

   Starting with the initial scan-line, until the active edge table is empty, do the following:

   1. Draw all pixels from the x value of odd to the x value of even parity edge pairs.

   2. Increase the scan-line by 1.

   3. Remove any edges from the active edge table for which the maximum y value is equal to the scan_line.

   4. Update the x value for for each edge in the active edge table using the formula x₁ = x₀ + 1/m. (This is based on the line formula and the fact that the next scan-line equals the old scan-line plus one.)

   5. Remove any edges from the global edge table for which the minimum y value is equal to the scan-line and place them in the active edge table.

   6. Reorder the edges in the active edge table according to increasing x value. This is done in case edges have crossed.

<< Previous Page

Next Page >>