graphicspolygonscanline

How to deal with horizontal edges in polygon scanline algorithm?


I'm trying to implement a scanline polygon fill using the even/odd technique, but horizontal edges have me perplexed. There are a number of similar questions on the site, but the answers are either a lot more work or simply don't help.

The most commonly-repeated suggestion is to just ignore horizontal edges, but that fails in the simple case of an upright star:

top outline of a low-resolution 5-pointed star

You can see that the scanline corresponding to the top of the left and right points has four vertices. If the horizontal edges are not considered, then all of those vertices are unshared, which means they are only counted once. That results in the middle part of the line (overlapping the upper point) being left unpainted.

For the even/odd technique to work in this case, we need to count both outer vertices just once each and both inner vertices twice each; then the entire line will be properly filled. But I can't see how to determine that algorithmically. I feel like there must be a solution short of giving up on even/odd entirely, but I don't know what it is.


Solution

  • There is a general rule that works; the condition that triggers it is not, as I thought, a repeated x-intercept value, but simply the fact that an edge's intercept on the current scanline is one of its vertices.

    When you find that an edge intercepts the current scanline, if the interception point is either vertex of the edge, then only count the edge if the other vertex is in the yet-to-be-scanned portion of the scene. If the other vertex is at the same y coordinate (so the edge is horizontal) or if it is in the already-scanned region, then the intercept is simply ignored.

    In the case of a star as in my image, let's assign letters to the vertices like so:

              A                               
                     
                     
    I       J   B       C
                      
          H       D      
                     
              F          
                     
        G           E    
    

    Assume we're sacnning from the top down and arrive at the line containing I, J, B, and C: