CSC 418: Scan Conversion of Polygons

Polygons

[Hill: p. 287-291. Foley & van Dam: p. 471-477]

Different types of polygons:

Triangles are often particularly nice to work with because they are always planar and simple convex.

A variety of polygon representations can be used, one of the most common ones being an ordered list of references to a vertex list. This avoids redundant storage and redundant computations. We'll also be associating a variety of other information with vertices, such as normals, colours, and texture coordinates.

Scan Conversion

[Hill: 570-576. Foley & vanDam: p. 92-99]

The job of scan conversion is to shade pixels lying within a closed polygon, and to do so efficiently. The fill colour will in general depend on the lighting, texture, and visibility of the polygon being scan-converted. These will be ignored for the time being.

Let's assume that the polygon is closed and has ordered edges.

The scan conversion algorithm then works as follows:

intersect each scanline with all edges
sort intersections in x
calculate parity of intersections to determine in/out
fill the 'in' pixels

Special cases:

horizontal edges can be excluded
vertices lying on scanlines

change in sign of y_i-y_i+1: count twice
no change: shorten edge by one scanline

Shortening an edge

Many intersection tests can be eliminated by taking advantage of coherence between adjacent scanlines.

Edges that intersect scanline y are likely to intersect y+1
x changes predictably from scanline y to y+1

The following two data structures can be used by an efficient scan-conversion algorithm.

Edge Table

o traverse edges
 o eliminate horizontal edges
 o if not local extremum, shorten upper vertex
 o add edge to linked-list for the scanline
   corresponding to the lower vertex, storing:
   - y_upper: last scanline to consider
   - x_lower: starting x coordinate for edge
   - 1/m:     for incrementing x; compute before shortening

Active Edge List (AEL)

The AEL is a linked list of active edges on the current scanline, y. Each active edge has the following information:

  - y_upper: last scanline to consider
  - x:       edge's intersection with current y)
  - 1/m:     for incrementing x

The active edges are kept sorted by x.

Scan Conversion Algorithm

o for each scanline
  o add edges in edge table to AEL
  o if AEL <> NIL
    o sort AEL by x
    o fill pixels between edge pairs
    o delete finished edges
    o update each edge's x

Extensions

multiple overlapping polygons -- priorities
colour, patterns, Z for visibility