Graphics Reference
In-Depth Information
With that in mind, Listing 34.1 is a simple algorithm for rendering the visible
contours and crease edges of a smooth polygonal shape that represents a surface
with no self-intersections so that each edge is either shared by two faces or on the
boundary.
Listing 34.1: Drawing the visible contours, boundary, and crease edges of a
polygonal shape from the point Eye.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Initialize
z
-
buffer and projection matrix
Clear
z
-
buffer to maximum depth
Clear color buffer to all white
Render all faces in white
edgeFaceTable =
new empty hastable with edges as keys and faces as values
outputEdges =
new empty list of edges
foreach face
f
in model
:
foreach edge
e
of
f
:
if e
is a crease edge
:
outputEdges.insert(e)
else if e
is not in
edgeFaceTable:
edgeFaceTable.insert(e, f)
else:
eyevec = e.firstVertex - Eye
f1 = edgeFaceTable.get(e)
// get other face adjacent to e
if dot(f1, eyevec)
*
dot(f, eyevec) < 0:
outputEdges.insert(e)
edgeFaceTable.remove(e)
foreach
edge
in
edgeFaceTable.keys():
outputEdges.insert(edge)
Render all edges in outputEdges in black
The key ideas in this algorithm are that boundary edges are those that appear
in only one polygon, and hence they are left in the table after all pairs have been
processed, and that a pair of faces that are adjacent at some edge make a contour
edge if one face normal points toward the eye and the other points away. Thus,
the list of output edges consists of all contour, crease, and boundary edges. The
rendering of the surface in white as an initialization prevents hidden output edges
from being seen (i.e., it generates occlusions). In practice, we often draw each
contour edge slightly displaced toward the eye so that it is not hidden by the faces
it belongs to. This slight displacement can unfortunately let a very slightly hid-
den contour be revealed, but in practice the algorithm tends to work quite well.
Chapter 33 gives a rather different approach to generating a contour rendering
that does not suffer from this problem, but that does not handle boundary edges or
crease edges.
Note that the preceding algorithm generates a list of edges to be drawn, but it
does not try to draw a stroke along the contour; it merely renders each edge as a
line segment. If you want to draw a long smooth curve (perhaps using the vertices
of the edges as control points for a spline curve, or even making a slightly wiggly
curve to convey a hand-drawn “feel”) you need to assemble the edges into chains
in which each edge is adjacent to its predecessor and successor in the list. For a
smooth closed surface, such chains exist, and for a generic view, the chains form
closed curves on the surface (i.e., cycles). (The crease edges may form noncyclic
chains, however.) Unfortunately, for a polygonal approximation of a smooth sur-
face, there's no such simple description of the contours. As Figure 34.11 shows,
Figure 34.11: A triangulated
cylinder in which every edge is a
contour edge when viewed from
directly overhead.
