Filling Convex Polygons

Filling Convex Polygons

So you've learned how to scan convert a polygon perfectly, now you're looking for a tasty filling. There is a wide choice of fillings, from plain vanilla to textured, transparent, bump mapped,Gourad and Phong shaded. I will try and give a explaination of each one.

Filling a polygon is the process of taking the information created by the scan converter, and using it to fill the polygon using horizontal strips of pixels. This is also known as Rendering.

This is usually one of the most time consuming pieces of code, especially if you are trying to perform bump-mapping and phong shading and texture mapping all in one go. So it is well worth spending time optimising this inner loop carefully. It will be quite justified by the speed increase.

Simple this one, been around since the begining of time, and still very popular. There are very many different techniques for doing this, each suited to different computers and video modes.I can't explain them all, mostly because I don't actually know them all. However I can go into some detail about filling on a VGA 8-bit screen.

Flat shading simply means filling the whole of the polygon in the same colour. It is a very easy piece of code to write, especially on an 8-bit screen, and can be made to run four times faster in Mode-X.

Firstly a very simple algorithm:

```minY = (Top of polygon)
maxY = (Bottom of polygon)
loop Y from minY to maxY
x1 = left(Y)
x2 = right(Y)
loop X from x1 to x2
plot a pixel at (X,Y)
end of X loopend of Y loop
```
Never use this algorithm. It is just about the slowest way of acheiving a flat fill. Everything about the inner loop is wrong. Let's take it apart bit by bit:

1. The plot pixel routine is called for every pixel on the polygon. This represents hundreds or thousands of unnecessary procedure calls. Moving the pixel plotting code into the inner loop will eradicate these.

2. The plot pixel routine will calculate the address of each pixel you ask it to plot. This usually involvesa multiply somewhere along the line. Again waste of time. For a start you know that, inside the inner loop, every pixel you plot is right next to the previous one. So you only need calculate the address of the first pixel, and the subsequent pixels along that line are at the next address:

```minY = (Top of polygon)
maxY = (Bottom of polygon)
loop Y from minY to maxY
x1 = left(Y)
x2 = right(Y)
loop X from x1 to x2
end of X loopend of Y loop
```

3. Most computers are capable or writing not only bytes, but also words and double words. Writing one of these is as fast as writing a byte (as long as it is aligned correctly). So you can fill the line in half the time. You must be sure however that words are aligned on even addresses, and double words arealigned on addresses divisible by 4:

(I do not apologise for using GOTO's, they make it much easier to convert pseudocode into assembler)

```minY = (Top of polygon)
maxY = (Bottom of polygon)
loop Y from minY to maxY
x1 = left(Y)
x2 = right(Y)
length = x2-x1+1				; number of pixels to write
if length = 1 then				; if there is only one pixel to draw
write a byte to (PixelAddress)		; then write one pixel
goto DoneThisLine				; and finish
end if
if (PixelAddress AND 3) =1 or 3		; if it's not on a word or doubleword boundary
write a byte to (PixelAddress)		; then write one pixel
length = length - 1				;
end if
if length <= 2 then goto LastStuff		; if there are only a couple of pixels left, then don't
; bother being flash, just write them
if (PixelAddress AND 3) =2			; if it's on a word boundary
write a word to (PixelAddress)		; then write 2 pixels
length = length - 2
end if
if length < 4 then goto LastStuff		; if there are only a couple of pixels left, then don't
; bother being flash, just write them

loop while length >= 4			; MAIN INNER LOOP
write a DoubleWord to (PixelAddress)	;   write 4 pixels
length = length - 4				;  end of loop
; END OF LOOP
LastStuff:					; now write the last couple of pixels
if length = 3 then				; if there are 3 pixels left
write a word to (PixelAddress)		; then draw 2 pixels
write a byte to (PixelAddress+1)		; and 1 more
goto DoneThisLine				; and finish
end if
if length = 2 then				; if there are 2 pixels left
write a word to (PixelAddress)		; then draw them
goto DoneThisLine				; and finish
end if
if length = 1 then				; if there's one pixel left
write a byte to (PixelAddress+1)		; then draw it
goto DoneThisLine				; and finish
end if
DoneThisLine:					; FINISHED THIS LINE
end of Y loop
```