next up previous
Next: Line Styles Up: Displaying Important Edges and Previous: Hardware Methods

Software Methods

 

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 v is a vertex on the edge, e is the eye point, and n are the outward facing surface normal vectors of the two faces sharing the edge. This situation only occurs when one face is front facing and the other is back facing. While this computation is simple, it can potentially become a bottleneck with large models. Since we have to shade (or prime the z buffer for hidden surface elimination) this computation can be done in parallel while the model is being rendered.


  
Figure 8: The arc in a Gauss map seen in 2D. The two bold line segments are faces that share a vertex. The orientations of their normals can be represented as points on the circle. The arc between those two points represents all orientations swept out between the two normals. In 3D the same reasoning applies, and the arc is an arbitrary segment on a great circle.

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.



next up previous
Next: Line Styles Up: Displaying Important Edges and Previous: Hardware Methods