Polygon Scan Converting

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 up.

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.

1.
Scan convert first edge.

2.
Scan convert second edge.

3.
Scan convert third edge.

4.
Scan convert fourth 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.

how do you store the x values?

For convex polygons, there is a very quick and easy way to handle this. Create two arrays of integers, big enough to store an x value for each scanline of the screen. Call them Left and Right.
For example, for a 320x200 screen:

Left(0 to 199)  : integer
Right(0 to 199) : integer

Now 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.

which points to fill?

If you use a simple line drawing algorithm to calculate the x-coordinates, you will find that many of the pixels drawn will actually lie slightly outside the boundaries of the polygon. This means that where polygons share the same edge, some pixels will be drawn twice. Now, this may or may not be a bad thing. It depends on how perfectly you need your polygons to be drawn. In many cases, if the polygons are flat shaded, people will never notice the fact. However, you may have transparent polygons, in which case you will get funny looking pixels at the boundaries between polygons, where the surface appears to be double thickness. It can be fatal however. If the edge of a texture mapped polygon lies very close to it's vanishing point at an oblique angle, a pixel outside the polygon may just lie past the horizon. In many perspective correct texture mapping routines, this could cause a divide by zero error. These should be avoided at all cost.

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.

Perfect scan converting

OK, so this routine is going to use non-integer maths. That does not mean you will need slow floating point code. This can all be done with resonably fast fixed point maths, which can be handled extremely fast in assembler. Even faster, dare I say it, than the integer code I gave for drawing lines. If you don't know about fixed point maths, then you'll have to either find out for yourself, wait till I write a document on it, or just use floating point code for now.

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) = 5

OK, so lets break down the steps:

1. Calculate the gradient of the line:

	dx = x2 - x1
	dy = y2 - y1
	gradient = dx/dy

2. Calculate ey:

	ey = int(y1+1) - y1

3. Calculate ex:

	ex = gradient*ey

4. Calculate coordinates of A:

	Ax = x1 + ex
	Ay = int(y1+1)

5. Calculate y coordinate of B:

	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.

Scan converting in Assembler

Here is an example of a scan converter I wrote in Assembler. It works on 32-bit Fixed Point numbers only.

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 loop

This 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 loop

So, 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.