Archived

This topic is now archived and is closed to further replies.

CuteBug

Scan Line Polygon Fill Algorithm

Recommended Posts

Could any one please explain me how scan line polygon algorithm is implemented? How do we get to know between which two intersections we need to fill? Thx in advance... "A byte is a large bit to crunch!"

Share this post


Link to post
Share on other sites
If you''ve got as far as working out which edges cross the current scan line, then you need to sort the edges into ascending x co-ordinates, then just fill between alternate edges.

Share this post


Link to post
Share on other sites
It''s really simple if you make sure your polygons are triangles. (not much harder if they are not).

You poly has three points (A,B,C). You want to draw this to the screen.

.......A
....C...
.........B

Find out which point will be ''highest'' on the screen. In the above case, it''s A.

You then need to figure out how to draw a line from A-C and a line from A-B.
Because we''re drawing to the screen, we assume that we increment by one pixel in the y direction. so we only need a delta X for each side of the triangle.

leftDeltaX = (a.x -c.x) / ( a.y - c.y)
rightDeltaX = ( a.x - b.x) / ( a.y - c.y)

What this gives us is the number of pixels to move vertically for each horizontal pixel we move.

Now we''ll want to keep track of a left and right x. Y will be shared.
leftX = a.x
rightX = a.x
tempY = a.y

then just start travering your line and filling in the polygon:

line ( leftX, tempY, rightX, tempY);
leftX = leftX + leftDeltaX;
rightX = rightX + rightDeltaX;

Keep doing this until your done drawing one ''side''. When this happens, you need to recalculate the appropriate side''s deltaX to reflect the new destination and what not.

In our example A-C will be completed before A-B. We recalculate leftDeltaX to reflect line segment C-B.
leftDeltaX = ( c.x - b.x) / ( c.y - b.y)

And then just keep on drawing!

Cheers,
Will

Share this post


Link to post
Share on other sites