There are many ways to draw polygons. All have their uses. Some are fast, others very slow. The most popular method, used in practically every game, rendering engine, and graphics package which handles polygons, is known as scan converting.
This method uses only integer maths, takes up very little memory, and is simple to understand. The algorithm can be adapted to handle flat or gourad shaded, textured and bump mapped polygons.
It is an approximate method. You will never be able to draw a totally perfect polygon with smooth edges on a normal screen, because of the fact that the picture is divided up into pixels. It is possible to make the edges look better, but the edges will nevertheless look jaggy.
On a pixelated screen, a small polygon like this will end up with nasty edges when viewed close
The method works by taking the polygon a line at a time, processing all the edges, then filling in the surface. If you haven't already, take a look at the page about drawing lines. You will find this very helpful.
A single scan conversion is the process of converting a polygon edge into data which can be used
by the polygon filling routine. The process is essentially a single case of the line drawing
algorithm. A polygon edge is calculated as if it were a line, but the line is not drawn to the
screen. Instead the information is saved in a buffer for use later.
Rather than having a different routine to handle nearly horizontal or nearly vertical lines, all edges are handled as nearly vertical.
So the line algorithm travels down an edge, calculating the X-coordinate of the pixel which lies closest to the line for each Y-coordinate.
Having calculated the x-coordinates for every edge of the polygon, the next step is to loop through the Y-coordinates spanned by the top and bottom of the polygon, and draw lines between pairs of X-coordinates.
Scan convert first edge.
Scan convert third edge.
Now that all edges have been scan-converted,
you need to begin filling. Start at the top of the polygon, and draw a horizontal strip between
the left and right edges. Work your way down, drawing horizontal strips across the polygon until
it is filled. One filled polygon.
Now that you know the basic idea behind it, there are many things to consider.
Left(0 to 199) : integer Right(0 to 199) : integerNow if you always list the points of the polygon in anti-clockwise order. Then you can easily determine which lines make up the left and the right edges of the polygon. Lines who's first point is above the second make up the left edges. Lines who's first point is below the second make up the right edges. Lines who's points lie at the same y coordinate can be ignored. Store the X values in either the Left or Right arrays accordingly. Then, when you come to fill the polygon, the x coordinates are already there in the right order.
In these cases, it is essential to write a scan-converter which guarantees that all pixels lie within the polygon's boundaries. This is, of course, easier said than done. What about pixels that lie exactly on a polygon boundary?
I now present what I believe to be a perfect scan-converting routine. It allows you to specify the vertices of the polygon to non-integer coordinates on the screen. This makes the polygon move a lot more fluidly. It also draws pixels which lie inside the edges of the polygon.
Perfectly scanned polygons move much more smoothly than those calculated with integer maths, and so are more pleasing to the eye. Take a look at Quake, then Tomb Raider or Syndicate Wars. You will see that the cheap polygons in Tomb Raider move in a rather jittery way, making the scenery look like it's held together with selotape. Quake's smoothly rendered polygons on the other hand give the architecture a more solid feel.
There is a demo available showing the difference between integer and Fixed Point polygons. It requires DOS/4GW to run.
So, lets take a really close look at the edges of a polygon:
OK, this may get complicated, and involve a little maths, but the results are excelent.
Take a close look at the line that is to be scan converted, the yellow one. The two points that it is being drawn between (white dots (x1,y1) & (x2,y2)) do not lie exactly at the center of any pixel, (green dots). However, when the polygon comes to be rendered, it must be drawn using horizontal strips that are drawn between integer coordinates.
The way to handle this is calculate the X intersection of the line with horizontal scanlines.
Then save the X coordinate of the nearest pixel inside the polygon.
Firstly some variables we'll need.
NonIntegers: gradient ex, ey x1, y1, x2, y2 Ax, Ay, Bx, By Integers: height the function int() returns the integer part of a number. i.e. int(5.7) = 5OK, so lets break down the steps:
dx = x2 - x1 dy = y2 - y1 gradient = dx/dy
ey = int(y1+1) - y1
ex = gradient*ey
Ax = x1 + ex Ay = int(y1+1)
By = int(y2)
You will notice that there is a divide in the calculation. Risk of a divide by zero. If dy is equal to zero, then you can simply ignore the entire line.
Right, now you have calculated all those things, the line can be scan converted. This scan converting process is actually faster than the one used for integer polygons (if you're using fixed point maths, otherwise it's slower). There are no IF's and JUMP's involved. The loop can be unrolled nicely to process at increadible speed.
So the inner loop looks something like this:
x = Ax loop y from Ay to By YBuffer(y) = x x=x+gradient end of loop
Again, you will have to handle Left hand lines and Right hand lines differently. The case given here is for a Left hand line. I will leave it up to you to work out how to handle the other side.
It takes as arguments; The initial x value (x), The gradient (DeltaX), the number of scan lines to calculate (length), and a pointer to the first element in the Y Buffer.
EAX = x EBX = DeltaX ECX = length EDI = pointer to YBuffer[Y] top: mov [edi], eax ; YBuffer[y] = x add eax, ebx ; x = x + DeltaX add edi, 4 ; y = y + 1 dec ecx jnz top: ;end of loopThis can be unrolled and can calculate polygon edges very fast indeed. This version has been unrolled four times
EAX = x EBX = DeltaX ECX = length EDI = pointer to YBuffer[Y] shr ecx ; halve the number of loops jnc NoSingle ; if there are an even number of lines to do, ; then don't do this odd one mov [edi], eax ; YBuffer[y] = x cmp ecx, 0 ; are there any more left? je NoMore ; if not, then exit add eax, ebx ; x = x + 1 add edi, 4 ; y = y + 1 NoSingle: shr ecx ; halve the number of loops again jnc NoSingle ; if the number of lines is a multiple of 4 ; then don't do these odd two mov [edi], eax ; YBuffer[y] = x add eax, ebx ; x = x + DeltaX mov [edi+4], eax ; YBuffer[y+1] = x add eax, ebx ; x = x + DeltaX cmp ecx, 0 ; are there any more left? je NoMore ; if not, then exit add edi, 8 ; y = y + 2 NoDouble: top: mov [edi], eax ; YBuffer[y] = x add eax, ebx ; x = x + DeltaX mov [edi+4], eax ; YBuffer[y+1] = x add eax, ebx ; x = x + DeltaX mov [edi+8], eax ; YBuffer[y+2] = x add eax, ebx ; x = x + DeltaX mov [edi+12], eax ; YBuffer[y+3] = x add eax, ebx ; x = x + DeltaX add edi, 16 ; y = y + 4 dec ecx ; jnz top ; end of loopSo, after all the edges of the polygon have been scan converted, you have an array of pairs of X coordinates where the edges cross horizontal scanlines. Assuming you are going to fill the area with a solid colour, you should loop down the height of the polygon, drawing horizontal strips from one side to the other. Remember that you only want to draw pixels that lie inside the polygon. So draw from the first pixel to the right of the left edge, to the first pixel to the left of the right edge. geddit?
Take a look at the polygon again, this time filled. The centres of the filled pixels all lie within the polygon. The X coordinates stored in the YBuffer would be:
y x1 x2 --------- 0: (-, -) 1: (3, 3) 2: (3, 3) 3: (2, 4) 4: (1, 4) 5: (3, 5) 6: (6, 5)You will notice that on the last line, 6, X1 is larger then X2. This is because the polygon crosses the line, but pokes between pixels. This strip does not get drawn.
I hope I have convinced you to only ever write perfect scan converters from now on. There shouldn't really be any excuse for using tacky integer polys any more. Computers are quite fast enough to cope with the tiny extra computing overhead involved, and you as a programmer, I have no doubt, are more then capable of writing the code.