Contents

But What About...?

The scan-line polygon fill algorithm covers these cases, but you may not understand how or why. The following will explain the handling of special cases to the algorithm.

  1. Horizontal Edges:

    Here we follow the minimum y value rule during scan-line polygon fill. If the edge is at the minimum y value for all edges, it is drawn. Otherwise, if the edge is at the maximum y value for any edge, we do not draw it. (See the next section containing information about top vs. bottom edges.)

    This is easily done in the scan-line polygon fill implementation. Horizontal edges are removed from the edge table completely.

    How are horizontal lines filled in then, you ask? Since each horizontal line meets exactly two other edge end-points on the scan-line, the algorithm will allow a fill of the pixels between those two end-point vertices when filling on the scan-line which the horizontal line is on, if it meets the top vs. bottom edge criteria.

    --> -->

    As can be seen above, if we start with a polygon with horizontal edges, we can remove the horizontal edges from the global edge table. The two endpoints of the edge will still exist and a line will be drawn between the lower edge, following the scan-line polygon fill algorithm. (The scan-line for the bottom horizontal edge is indicated by the magenta, arrowed line.)

  2. Bottom and Left Edges vs. Top and Right Edges:

    If polygons, having at least one overlapping edge the other, were filled completely from edge to edge, these polygons would appear to overlap and/or be distorted. This would be especially noticeable for polygons in which edges have limited space between them.

    In order to correct for this phenomenon, our algorithm does not allow fills of the right or top edges of polygons. This distortion problem could also be corrected by not drawing either the left or right edges and not drawing either the top or bottom edges of the polygon. Either way, a consistent method should be used with all polygons. If some polygons are filled with the left and bottom edges and others with the bottom and right edges, this problem will still occur.

    -->

    As can be seen above, if we remove the right and top edges from both polygons, the polygons no longer appear to be different shapes. For polygons with more overlap than just one edge, the polygons will still appear to overlap as was meant to happen.

  3. How do we deal with two edges meeting at a vertex when counting parity? This is a scenario which needs to be accounted for in one of the following ways:

    1. When dealing with two edges which meet at a vertex and for both edges the vertex is the minimum point, the pixel is drawn and is counted twice for parity.

      Essentially, the following occurs. In the scan-line polygon fill algorithm, the vertex is drawn for the first edge, since it is a minimum value for that edge, but not for the second edge, since it is a right edge and right edges are not drawn in the scan-line fill algorithm. The parity is increased once for the first edge and again for the second edge.

    2. When dealing with two edges which meet at a vertex and for both edges the vertex is the maximum point, the pixel is not drawn and is counted twice for parity.

      Basically, this occurs because the vertex is not drawn for the first edge, since it is a maximum point for that edge, and parity is increased. The vertex is then not drawn for the second edge, since it is a right edge, and parity is The point should not be drawn since maximum y values for edges are not drawn in the scan-line polygon fill implementation.

    3. When dealing with two edges which meet at a vertex and for one edge the vertex is the maximum point and for the other edge the vertex is the minimum point, we must also consider whether the edges are left or right edges. Two edges meeting in such a way can be thought of as one edge which is "bent".

      If the edges are on the left side of the polygon, the pixel is drawn and is counted once for parity purposes. This is due to the fact that left edges are drawn in the scan-line polygon fill implementation. The vertex is drawn just once for the edge which has this vertex as its minimum point. Parity is incremented just once for this "bent edge".

    4. If both edges are on the right, the pixel is not drawn and is counted just once for parity purposes. This is due to the fact that right edges are not drawn in the scan-line polygon fill implementation.

<< Previous Page Next Page >>