Hierarchical back-face computation

We present a sub-linear algorithm to compute the set of back-facing polygons in a polyhedral model. The algorithm partitions the model into hierarchical clusters based on the orientations and positions of the polygons. As a preprocessing step, the algorithm constructs spatial decompositions with respect to each cluster. For a sequence of back-face computations, the algorithm exploits the coherence in view-point movement to efficiently determine whether it is in front of or behind a cluster. Due to coherence, the algorithm's expected running time is linear in the number of clusters on average. We have applied this algorithm to speed up the rendering of polyhedral models. On average, we are able to cull about 40% of the polygons. The algorithm accounts for 5% of the total CPU time per frame on an SGI Onyx. The overall frame rate is improved by 40-75% as compared to the standard back-face culling implemented in hardware. We also present an extension of our back-face computation algorithm to determine silhouettes of polygonal models. Our technique finds true perspective silhouettes by collecting edges at the common boundaries of back-facing and front-facing clusters. (C) 1999 Published by Elsevier Science Ltd. All rights reserved.