Hierarchical Back-Face Culling

We present a sub-linear algorithm for computing and culling back-facing polygons that yields a significant performance improvement in the interactive rendering of large polygonal models. The algorithm partitions a polygonal model it into hierarchical clusters based on the normals and positions of the polygons. It does not explicitly compute all the back-facing polygons but rather decides, in expected constant time, whether an entire cluster is back-facing. As a pre-processing step, the algorithm partitions the space into regions with respect to each cluster. During rendering, it exploits frame-to-frame coherence to track the view-point. The algorithm has been applied to a number of models and its performance is a function of number of clusters, the depth of the hierarchies, and the characteristics of the graphics system. In practice, we are able to cull 30 \Γ 55% of the polygons in about 5 \Γ 10% of the total CPU time per frame on an SGI Indigo2 Extreme for models composed of t...