Polygons
[Angel3: 50, 176-178][FVFH: 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
[Angel3: 401-408][FVFH: 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 slope: 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