Fast extraction of polyhedral model silhouettes from moving viewpoint on curved trajectory

The efficient extraction of model silhouettes is essential in many applications, such as non-photorealistic rendering, backface culling, shadow computation, and computing swept volumes. For dynamically moving viewpoints, efficient silhouette extraction is more important for system performance. Accordingly, this paper presents an incremental update algorithm for computing a perspective silhouette sequence for a polyhedral model. The viewpoint is assumed to move along a given trajectory q(t), where t is the time parameter. As the preprocessing step, the time-intervals during which each model edge is contained in the silhouette, defined as silhouette time-intervals, are computed using two major computations: (i) intersecting q(t) with two planes and (ii) a number of dot products. If q(t) is a curve of degree n, there are at most n+1 silhouette time-intervals for an individual edge. The silhouette time-intervals are then used to determine the edges that should be added or deleted from the previous silhouette for each discrete viewpoint, thereby providing an optimal way to compute a sequence of silhouettes. A search-based algorithm is also presented that extracts the silhouette edges for each time point tj by searching the silhouette time-intervals containing tj. The performance of the proposed algorithms is analyzed and experimental results are compared with those for the anchored cone algorithm suggested by Sander et al. [In: Akeley K, editor. Siggraph 2000, Computer Graphics Proceedings. Annual Conference Series. New York/Reading, MA/New York: ACM Press/ACM SIGGRAPH/Addison-Wesley/Longman; 2000. p. 327-34.]