Looking for a fast polygon rendering algorithm

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.

[To see links please register here]

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.

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


[1]:

[To see links please register here]

How about [Bresenham's][1] 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.

[1]:

[To see links please register here]

I would start by converting the polygon to a collection of triangles and render those, because triangles are easy to render by scanlines. Although even so there are some details.

Essentially, the `draw-triangle` sub-procedure will be given a raw triangle and proceed:

1. Reject degenerate triangles (where two of the three vertices overlap).
2. Sort the vertices in Y (since there are only three you can hardcode the sorting logic).
3. Now, at this point you should know that there will be three kinds of triangles: ones with a flat top, ones with a flat bottom, and "general" triangles. You want to handle a general triangle by essentially splitting it into one each of the flat types. This is because you don't want to have an `if` test every scanline to detect if the slope changed.
4. To render a flat triangle, you would run two Bresenham algorithms in parallel to iterate the pixels comprising the edges, and use the points they give you as the endpoints of each horizontal scanline.

It may be easier to break the problem into two parts. First, locate/write an algorithm that draws and fills a triangle. Second, write an algorithm that breaks up an arbitrary polygon into triangles (using different combinations of the vertices).

To draw/fill a triangle, use Bresenham's Line Algorithm to simultaneously draw a line between points 0 and 1, and between 1 and 2. For each input point `x`, draw the pixel if it is equal to or in between the `y` points generated by the two lines. When you reach one endpoint, continue by using the unfinished side and the side that has not yet been used.

**Edit:**
To break your convex polygon into triangles, arrange the points in order and call them `P1, P2, ... PN`. Let `P1` be your "root" point, and build triangles using that point and combinations of adjacent points. For example, a pentagon would yield the three triangles `P1-P2-P3`, `P1-P3-P4`, and `P1-P4-P5`. In general, a convex polygon with `N` sides will decompose into `N-2` triangles.