3D tutorials: Polygon Scan Conversion

Polygons are two-dimentional (flat) shapes bounded by straight lines going from one vertex to the other. Usually triangles are used, because they always define a flat surface. For the example I used quadrilaterals, since they can be used more intuitively for a cube. By the way, polygons are plotted in two dimensions, 3D vertices are first converted to 2d using perspective projection shown above. There are many ways to draw polygons, but the main idea is to find the lines connecting the vertices and fill in the inside. The way you find an edge between two points is by using the good old y=mx+b line equation from highschool math class. In case you forgot (I didn't, cause I learned it last year :-), this equation uses an x coordinate to find a y on the line. 'm' stands for the slope of the line and b for its y-intercept (the point where x is 0). Basically all we need from here is the slope. It is defined by rise/run, ie: delta_y/delta_x; but we need x in function of y, for reasons I will explain later. Since you have the two endpoints (x1,y1) and (x2,y2), you can easily get the slope by:

m=(x2-x1)/(y2-y1)

This gives you the amount by which x changes every time you increase y by one. Now all you need to do is start at the first coordinate and each time you increment y, add m to x. It would look something like this.

m=(x2-x1)/(y2-y1);
x=x1;

for(y=y1; y < y2; y++)
{
edge[y]=x;
x+=m;
}


Now I'll tell you why we needed the x coordinates. The reason is the way you fill the poly: you draw horizontal lines at each y coordinate, and you need the two endpoints. It's done with horizontal lines instead of vertical because it's much easier and faster to program. But wait! You only have one side so far. What you need to do is set up two arrays, one for the left edge(s) and one for the right. As you trace each edge, put it on the appropriate side. This is a bit tricky. I'll explain the triangles first.

First you need to sort the vertices by height. Now you can trace an edge from the top to the bottom vertex in one edge buffer, and from 1 to 2 and 2 to 3 in the other buffer. The problem here is that you don't know which side each edge should go into. Its only implication is that you might have to swap the endpoints when you're drawing your horizontal line. The other thing you can do is find the point on the long edge which is at the same height as the middle vertex. If you work out the math, this becomes:

m=(V0.x-V2.x)/(V0.y-V2.y)
x=V2.x+(V2.y-V1.y)*m


Now you subtract the middle vertex's x coordinate from the one you just got, and if the result is negative, the middle point is to the right, otherwise to the left of the long side. You use this to decide which sides belong to which edge buffer. If for some reason you can't implement it, one of the examples on the shading page does.

For polygons with more sides, you go around from one vertex to the next and trace the edges. There is no easy way to automatically put them in the right edge buffer, so you have to decide while you're tracing the side. If there was no other edge at a particular y coordinate, then the present line's x coordinate is put into both buffers. If there was another line at the particular location in the buffer you're trying to write, then you only replace the existing value if your present edge's x coordinate is more to the right, or more to the left, depending on which side it is. This means that if you have a point at 100 in both buffers and your point is 250, then you write your value to the right buffer, since it is more to the right then 100. On the other hand you can't write to the left one, because the value already present is more to the left.

int left_edge[scr_y_res], right_edge[scr_y_res];


for (y=y1; y < y2; y++)
{
if(xright_edge[y])
right_edge[y]=(int)x;
x+=m;
}


This method can be used for polygons with any number of vertices, as long as they are not concave (ie: four or more sides going through the same y coordinate). Now all you have left to do is connect the two edges with a horizontal line at every y coordinate on the screen. This second method is too slow for triangles though, because of all the checks while filling the buffers, so don't use it. In general there is no reason to use anything other than triangles.

Now that you have two edge buffers, you just draw the horizontal lines from one to the other. You start at the top and work downwards:

for(y=V0.y; y < V2.y; y++) // for triangle with vertices sorted by height
{
x1=left_edge[y].x;
x2=right_edge[y].x;


for(x=x1; x < x2; x++)
{
putpixel(x, y, c);
}
}


Sorting and Backface Removal



But your object still doesn't look solid at all. That's because the back sides show up in front half the time. A logical solution is arranging the polys so that back sides stay at the back. You can sort the sides by their z value and then draw them back to front. You need to use the average z value across the polygon. You get this by adding all the z values together and dividing the result by the number of vertices of the poly. You can use any sorting algorythm you want. This still doesn't fix everything, especially with few sided polyhedrons like my cube. The next method will correct everything and also speed things up. This is about finding out if the polygon is facing towards the viewer or away. It's called 'backface culling' and is done by finding out if the vertices of the poly are in clockwise order. For this reason you should create your objects with the vertices in the right order. What you need is two vectors originating fron the same point. You get these by choosing three consecutive points and subtracting the middle one from the other two. Now you basically use the z part of the cross product (explained below) of the two vectors, which is either positive or negative, according to the points being in clockwise or anticlockwise order. You only draw the sides that are facing you, so at least half of them will always be invisible (for closed objects), saving display time.
The equation is:


if ((x1*y2 - x2*y1) > 0) then clockwise

<< Prev


Safety Tutorials
Spyware Removal Links
Mozilla Tips