Sign in to follow this  
mancubit

simplistic rasterizing of convex polygons - tutorial?

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this