Jump to content
  • Advertisement


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


Scan Line Polygon Fill Algorithm

This topic is 5645 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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.


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!


Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!