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.