A straightforward way to draw silhouettes is to explicitly test every edge in the model. We compute an edge structure based on the face normals of the model, which are also used for back face culling as in Zhang et al. [29]. An edge is a silhouette edge if and only if:

where

We use a more complex preprocess and search algorithm when classifying edges becomes a bottleneck. This algorithm is similar in spirit to Zhang et al. [29], but requires looking at arcs on the Gauss map instead of points. The Gauss map of an edge on a polyhedral model is a great arc on the sphere of orientations (Figure 8). Under orthographic projection, a plane through the origin in this sphere defines the view. All of the faces on one side of the plane are front facing, and on the other side they are back facing. If the ``arc'' corresponding to an edge is intersected by this plane, it is a silhouette edge. To search for such edge/plane intersections, we store the arcs in a hierarchy on the sphere to quickly cull edges that can not be silhouettes. We have implemented a decomposition of the sphere starting with a platonic solid (octahedron or icosahedron) and all successive levels are four to one splits of spherical triangles. An arc is stored at the lowest possible level of the hierarchy. This makes silhouette extraction logarithmic in the number of edges for smooth models where the arcs tend to be short. One problem with this hierarchy is that the edges of the spherical triangles on the sphere interfere with the arcs and limit how far they can be pushed down the hierarchy. The probability of being stored in a leaf node that can contain an arc of a given length decreases as the size of the triangles shrink because the boundaries of these spherical triangles become denser as you recurse. An ad hoc solution to this problem is to use multiple hierarchies, whose spherical triangles are different, and store an arc in the hierarchy with the spherical triangle with the smallest area that contains it. A more attractive alternative would be to use ``bins'' on the sphere that overlap and/or making data dependent hierarchies.

Under perspective viewing, the region you have to check grows, based on planes containing the object and intersecting the eye. Building a spatial hierarchy over the model as in [29] would minimize this effect. One advantage of any software approach is that it makes it easier to implement different styles of line drawing.