Public Group

# simplistic rasterizing of convex polygons - tutorial?

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

## Recommended Posts

i am searching for a simple tutorial on howto rasterize convex polygons. I speak of the method of drawing horizontal lines to fill up a polygon. My current book where i am trying to learn 3D-Graphics covers this part, but i dont understand it completly, so maybe an other tutorial may help me out here. Anyone knows a source for this? didnt found any for this simple problem :( edit: i would prefer a theoretical approach of this issue, but an actual implementation would help too..

##### Share on other sites
Scanline conversion is fairly simple. The fact that your polygon is convex means you can draw a line from any point on its edge to any other point on its edge and it won't go outside of the polygon; this means that if you treat each row of pixels as a line going from left to right, then it intersects the polygon in exactly two places - one where it 'enters' the polygon and one where it 'exits.' If you can find those two points then all you need to do is fill in all the pixels between them.

As far as finding the intersections goes, the simplest approach is just to test the pixel-row line against each line-segment that makes up the edge of the polygon. There are ways of making it faster, but you probably want to implement it correctly first and worry about making it faster afterwards.

##### Share on other sites
Assuming your polygon is defined as some sort of array of vertices:

1. If you need to, transform your polygon into screen coordinates.

2. Iterate through the vertices until you find the top and bottom vertices. (If it helps, the top vertex will be the only one higher than both the vertex before and after it, and vice-versa for the bottom one.

3. Keep 3 variables as you draw your lines:
. a) The left-edge start vertex. = Top vertex.
. b) The right-edge finish vertex. = Top vertex.
. c) The row (line) number. Start at the top.
(Assuming clockwise vertices - easy to switch).

4. Loop the row number from top to bottom.
For each line:
. a) Check if have gone below the left-edge finish vertex. If so, modular-increment left-edge start vertex (left_edge = (left_edge + 1) % num_edges).
. b) Same for right-edge except decrement (right_edge = (right_edge + num_edges - 1) % num_edges.
. c) Calculate the horizontal start & finish points of the line by interpolating based on the coordinates of the two edge vertices and the line number. (You can speed this up significantly by calculating dx/dy and adding this to the previous start or finish positions).
. d) Draw the line.

NOTE: This is an quickie and doesn't deal very well with completely horizontal lines.

##### Share on other sites
edit: cutted my last post - i finally got it :-) thx all!

btw: this tutorial helped me too:

http://www.devmaster.net/articles/software-rendering/part3.php

[Edited by - mancubit on July 28, 2008 10:36:55 AM]

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 14
• 46
• 22
• 27
• ### Forum Statistics

• Total Topics
634046
• Total Posts
3015224
×