I'm trying a incremental raster-based approach to PianoApprentice's scanline polygon fill. You can get a feeling for potentially how fast it could run, from this code, but as explained below, it's currently pretty broken ... :-( This draws the outline and records the x & y coord of every point on each line where y has changed by 1 step while it draws. It sorts this array of (x,y) pairs first by y, then subsorted by x. For each pair of coordinates on the same y, it draws a line between them (with a special case for the single point apex of a triangle - which unfortunately doesn't work correctly if there is more to come on the same y scanline, and anyway it really shouldn't be needed because the point ought to be drawn twice. I'm not really sure where these odd points are coming from...) The line drawing using Bresenham's only stores the leftmost point of a horizontal sequence where it is incrementing one large x step at a time, which is OK for the left sides of polygons but is wrong for the right sides, and I don't have a good solution yet since I can't tell while drawing a line if it's on the left or the right of a filled area. I guess I could use a DDA rather than Bresenham's to get proper stepping in Y, but I was trying to avoid floating point math altogether, to make it really fast.
The primary purpose of the rewrite was to simplify the logic and make it easier to understand, but it doesn't count if the code doesn't work correctly. (I haven't quite duplicated the details of @PianoApprentice's algorithm - apart from the relatively minor Bresenham issue mentioned above, it doesn't handle self-intersection the way PianoApprentice's does, and I'm not sure why. If any of the smart kids can fix this (without doing floating point arithmetic to draw the outline) I'd be very grateful. And impressed. A secondary purpose of using a raster-based algorithm is that it opens up the possibility of filling Bezier curves with no extra effort...
