View volume culling using a probabilistic caching scheme

Abstract

This paper a new algorithm for view volume culling. During an interactive walkthrough of a 3D scene, at any moment a large proportion of objects will be outside of the view volume. Frame-to-frame coherence implies that the sets of objects that are completely outside, completely inside, or intersecting the boundary of the view volume, will change slowly over time. This coherence is exploited to develop an algorithm that quickly identifies these three sets of objects, and partitions those completely outside into subsets which are probabilistically sampled according to their distance from the view volume. A statistical object representation scheme is used to classify objects into the various sets. The algorithm is implemented in the context of a Binary Space Partition tree, and preliminary investigation of the algorithm on two scenes with more than 11,000 polygons, suggests that it is approximately twice as fast as the hierarchical bounding box approach to culling, and that only about 14% of the total frame-polygons are passed through the viewing pipeline during the course of a walkthrough.