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.

Flat Shading

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)
  PixelAddress = address of pixel at (x1, Y)
  loop X from x1 to x2
    write a byte to (PixelAddress)
    PixelAddress = PixelAddress + 1
  end of X loopend of Y loop

Much faster already.

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
  PixelAddress = address of pixel at (x1, Y)	; calculate address of first pixel
  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				;
    PixelAddress = PixelAddress + 1		; next address
  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
    PixelAddress = PixelAddress + 2		; next address
  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
    PixelAddress = PixelAddress + 4		;   next address
    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