Abstract
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 pre-processing 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 if it is in front of or behind a cluster. Due to coherence, the algorithm’s performance 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 almost half the polygons. The algorithm accounts for 5 – 10% of the total CPU time per frame on an SGI Indigo2 Extreme. The overall frame rate is improved by 40 – 75% as compared to the standard back-face culling implemented in hardware.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Airey, J. Rohlf, and F. Brooks. Towards image realism with interactive update rates in complex virtual building environments. In Symposium on Interactive 3D Graphics, pages 41–50, 1990
M Bern, D. Dobkin, D. Eppstein, and R. Grossman. Visibility with a moving point of view. Algonthmica, 11:360–78, 1994.
W. Bouma and G. Vanecek Velocity-based collision detection. In A. Paeth, editor, Graphics Gems V, pages 380–385, Academic Press, 1995.
J.H. Clark. Hierarchical geometric models for visible surface algorithms. Communications of the ACM, 19(10):547–554, 1976.
F. C Crow. Shadow algorithms for computer graphics. ACM Computer Graphics, 11(3).242–248, 1977.
D. P. Dobkin and D. G. Kirkpatrick Fast detection of polyhedral intersection. In Proc. 9th Internat. Colloq. Automata Lang. Program., volume 140 of Lecture Notes in Computer Science, pages 154–165. Springer-Verlag, 1982.
J. Foley, A Van Dam, J. Hughes, and S Feiner. Computer Graphics: Principles and Practice Addison Wesley, Reading, Mass., 1990
H. Fuchs, Z. Kedem, and B Naylor. On visible surface generation by a priori tree structures. In Proc. of ACM Siggraph, volume 14, pages 124–133, 1980.
N. Greene, M. Kass, and G. Miller. Hierarchical z-buffer visibility. In Proc. of ACM Siggraph, pages 231–238, 1993
S. Kumar and D Manocha. Hierarchical visibility culling for spline models. In Proceedings of Graphics Interface, pages 142–150, Totonto, Canada, 1996
M. Newell, R. Newell, and T. Sancha. A new solution to the hidden surface problem. Proc. ACM Ann. Conf., pages 443–448, 1972.
F.P Preparata and M I Shamos Computational Geometry. Springer-Verlag, New York, 1985.
R. Schumacker, B. Brand, M Gilliland, and W. Sharp. Study for applying computer-generated images to visual generation. Technical report, AFHRL-TR-69-74, US Air Force Human Resources Lab, 1969.
L.A. Shirman and S.S. Abi-Ezzi. The cone of normals technique for fast processing of curved patches. In EUROGRAPHICS, pages 261–272, 1993.
I. Sutherland, R. Sproull, and R. Schumaker. A characterization of ten hidden-surface algorithms. Computing Surveys, 6(1):1–55, 1974.
S.L. Tanimoto. A graph-theoretic real-time visible surface editing technique. In Proc. of ACM Siggraph, pages 223–228, 1977.
S J. Teller. Visibility Computations in Densely Occluded Polyheral Environments. PhD thesis, CS Division, UC Berkeley, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag/Wien
About this paper
Cite this paper
Kumar, S., Manocha, D., Garrett, W., Lin, M. (1996). Hierarchical Back-Face Computation. In: Pueyo, X., Schröder, P. (eds) Rendering Techniques ’96. EGSR 1996. Eurographics. Springer, Vienna. https://doi.org/10.1007/978-3-7091-7484-5_24
Download citation
DOI: https://doi.org/10.1007/978-3-7091-7484-5_24
Published:
Publisher Name: Springer, Vienna
Print ISBN: 978-3-211-82883-0
Online ISBN: 978-3-7091-7484-5
eBook Packages: Springer Book Archive