Scan converting convex polygons

A problem in scan converting acgeneral n-sided convex polygon is that a given scan line will not necessarily cross all sides of a polygon.

For a triangle there was only one side not intersected so a simple test was sufficient. If there are many sides it becomes inefficient to test against all sides. So we keep a list of "active" edges, i.e., edges that are crossed by the current scan line. This list is kept by having a list of edges, sorted by Ytop value, and using two pointers, one to the first active edge and the second to the llast active edge.

Here is an example of the changing active edge list as a 5-sided polygon is scan converted.

Sorted list of edges (by Ytop)

List 1

CB is the pointer to top of active edges
CD is the pointer to bottom of active edges
DE
BA
EA

List 2

CB
CD
DE is the pointer to top of active edges
BA is the pointer to bottom of active edges
EA

List 3

CB
CD
DE
BA is the pointer to top of active edges
EA is the pointer to bottom of active edges

So a modified Top Level Algorithm:

  1. Sort sides and create Edge List (Draw horizontal edges)
  2. Repeat
    Update active edge pointers (Top Bottom)
    Find x-intersections
    Draw-lines
    Reference: The above derivation was taken from Hearn & Baker.

Solid Polygon menu
HyperGraph Table of Contents.
HyperGraph Home page.

Last changed May 13, 1998, G. Scott Owen, owen@siggraph.org