On incremental rendering of silhouette maps of a polyhedral scene

We consider the problem of incrementally rendering a polyhedral scene while the viewpoint is moving. In practical situations the number of geometric primitives to be rendered can be very large - hundreds of thousands or millions, but these may come from only a moderate number of objects that happen to have been finely tessellated. It is sometimes advantageous to render only the silhouettes of the objects, rather than the objects themselves, and then exploit coherence or other methods to optimize the rendering of single-object regions with uniform reflectance properties. Such an approach is also regularly used in the domain of non-photorealistic rendering, where the rendering of silhouette edges plays a key role. The hard part in efficiently implementing a kinetic approach to this problem is to realize when the rendered silhouette undergoes a combinatorial change. In this paper, we obtain bounds on a number of combinatorial problems involving the complexity of these events for a collection of k objects, with a total of n edges. We assume that our objects are convex polytopes, and that the viewpoint is moving along a straight line, or along an algebraic curve. The resulting bounds will then depend on both the number of objects, and the total number of edges, in such a way that we can describe the advantages of focusing on the silhouettes of combinatorially large objects. We also study the special case when the scene is a polyhedral terrain, and present improved bounds for this case. In addition to event bounds, we also obtain algorithms that compute all the changes occurring during a linear motion, (both for general scenes and for terrains).