Hey all! Took longer than expected - sorry. Also sorry for the confusion - I wasn't aware of the non-zero winding rule and thought it referred to something completely different.
Okay so I'll try to explain the issues I ran into with the polygon filler in the software at work. Of course we're going to assume an even-odd fill rule for simplicity, and because up until 20 minutes ago it's all I was familiar with. Again though, the problem isn't what to fill - it's how to deal with intersections of line segment
end points. First, a picture:
[edit - removed stuff about bresenham lines... see next post]
As for the even-odd rule, for anyone reading that doesn't know already, take the grey horizontal scan line as an example. To fill the polygon you just fill every
other pair of points. So you'd fill blue to purple. Skip purple to yellow. Fill yellow to green. This works correctly even if the polygon creates it's own holes. It's arguable whether this is superior to the non-zero rule (
http://en.wikipedia.org/wiki/Nonzero-rule), depending on application.
Now as for line intersections. The intersection at 'F' is a non-issue. The polygon fills correctly here.
Now let's assume you are counting the intersection at
both endpoints of a single line segment. At 'B', you would get an intersection for both the red and blue lines. Upon filling, you'd fill from red to blue, then
skip blue to yellow, fill yellow to purple, and skip purple to green. Oops!
So, to fix this, we always calculate the intersection for the 1st endpoint of a line segment, but not the second. This fixes the issue at 'B'. But now, at A, C, D, and F, there is a problem. Take 'A' for example. We only calculate the intersection for, say, the red line. Then at 'D', the same thing happens for just the green line. So on this scanline we fill from 'A' to 'D' !! Oops again! However, it was actually fine when we counted the intersection at
both endpoints as above when we failed at 'B' in the first place.
So, after all that, the final solution is this:
- By default, calculate line segment intersection inclusive of the 1st endpoint and exclusive of the 2nd.
- However, if the line segment's 2nd end point happens to be at a peak such as it is in A, C, D, or E,
include the 2nd end point.
Those 2 rules will solve your problem as proposed, if I understood correctly. I really hope it helps! (and I hope this wasn't too verbose... I'm not that great at this - I just happened to be familiar with the problem).