Looking for a fast polygon rendering algorithm

Question

I am working with a Microchip dsPIC33FJ128GP802. It's a small DSP-based microcontroller, and it doesn't have much power (40 million instructions per second). I'm looking for a way to render a convex (i.e. simple) polygon. I am only dealing with 2D shapes, integer math, and set or clear pixels (i.e. 1 bit per pixel.) I already have routines for drawing fast horizontal and vertical lines (writing up to 16 pixels in 88 cycles), so I would like to use a scanline algorithm.

However, all the algorithms I have found seem to depend on division (which takes 18 cycles on this processor) and floating point math (which is emulated in software and so is very slow; it also takes up a lot of ROM), or assume that I have a large amount of memory. I only have 2K left, ~14K is used for graphics RAM of my 16K. So does anyone know of any good, embedded machine algorithms they can point me to with a simple C or pseudocode implementation which I can implement in assembly? Preferably on the 'net, I don't live near any good bookstores with many programming books.

Thanks. :)

EDIT: Clarification, this is a polygon filling algorithm I'm looking for. I can implement a polygon outline algorithm using Bresenham's line drawing algorithm (as Marc B suggests.)

EDIT #2: I wanted to let everyone know I got a basic algorithm up in Python. Here's a link to the code. Public domain code.

http://dl.dropbox.com/u/1134084/bresenham_demos.py

Answer 1

How about Bresenham's Line algorithm? After some setup, it's pure integer math, and can be adapted to draw a polygon by simple iteration of starting points along the polygon edges.

comments followup:

I'll try to draw this in ASCII, but it'll probably look like crud. Bresenham's can be used to draw a filled polygon by picking a starting edge, and iteratively moving a bresenham line across the canvas parallel to that point.

Let's say you've got some points like this:

*(1)
                      *(3)

    *(2)         
                 *(4)

These are numbered in left-right sort priority, so you pick the left-most starting point (1) and decide if you want to go vertically (start 1,2) or horizontally (1,3). That'd probably depend on how your DSP does its display, but let's go with vertical.

So... You use the 1-2 line as your starting bresenham line. You calculate the starting points of your fill lines by using lines 1-3 and 2-4 as your start/end points. Start a bresenham calculation for each, and draw another Bresenham between those two points. Kinda like:

1.1 -> 2.1, then 1.2 -> 2.2, then 1.3 -> 2.3

etc... until you reach the end of either of those lines. In this case, that'd be when the lower starting point reaches (4). At that point, you start iterating up the 4,3 line, until you reach point 3 with both starting points, and you're done.

*-------
 \\\\\\\\              *
  \\\\\\\\ 
   *-----\\         
         -------  *

Where the dashes are the starting points you calculated along 1-3 and 2-4, and the slashes are the fill lines.

Of course, this only works if the points are properly sorted, and you've got a convex polygon. If it's concave, you'll have to be very careful to not let your fill lines cross over the border, or do some pre-processing and subdivide the original poly into two or more convex ones.

Answer 2

You may want to look at Michael Abrash's articles on Dr Dobbs about polygon fill/raster/etc. It uses fixed-point math

Answer 3

Thomas, if you have a Bresenham line drawing algorithm available, then use it as a basis for further enhancement: divide your polygon to sub-polygons with an horizontal cutting line through every vertex. Then, start tracing the 2 left and right sides of each of these sub-polys, using Bresenham. This way you have the 2 end-points of each scan line in your polygon.