“View-dependent simplification of arbitrary polygonal environments” by Luebke and Erikson

Hierarchical dynamic simplification (HDS) is a new approach to the problem of simplifying arbitrary polygonal environments. HDS operates dynamically, retessellating the scene continuously as the user’s viewing position shifts, and adaptively, processing the entire database without first decomposing the environment into individual objects. The resulting system allows real-time display of very complex polygonal CAD models consisting of thousands of parts and hundreds of thousands of polygons. HDS supports various preprocessing algorithms and various run-time criteria, providing a general framework for dynamic view-dependent simplification. Briefly, HDS works by clustering vertices together in a hierarchical fashion. The simplification process continuously queries this hierarchy to generate a scene containing only those polygons that are important from the current viewpoint. When the volume of space associated with a vertex cluster occupies less than a user-specified amount of the screen, all vertices within that cluster are collapsed together and degenerate polygons filtered out. HDS maintains an active list of visible polygons for rendering. Since frame-to-frame movements typically involve small changes in viewpoint, and therefore modify the active list by only a few polygons, the method takes advantage of temporal coherence for greater speed.

1. Aliaga, Daniel. “SGI Performance Tips” (Talk). For more information see: http ://www. cs. unc. edu/,~aliaga/IR-perf . html .
2. Cho, Y., U. Neumann, J. Woo. “Improved Specular Highlights with Adaptive Shading”, Computer Graphics International 96, June, 1996.
3. Clark, James H. “Hierarchical Geometric Models for Visible Surface Algorithms,” Communications of the ACM, Vol 19, No 10, pp 547-554.
4. Cohen, J., A. Varshney, D. Manocha, G. Turk, H. Weber, P. Agarwal, F. Brooks, W. Wright. “Simplification Envelopes”, Computer Graphics, Vol 30 (SIGGRAPH 96).
5. Cosman, M., and R. Schumacker. “System Strategies to Optimize CIG Image Content”. Proceedings Image II Co nference (Scotsdale, Arizona), 1981.
6. Eck, M., T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, W. Stuetzle. “Multiresolution Analysis of Arbitrary Meshes”, Computer Graphics, Vol 29 (SIGGRAPH 95).
7. Funkhouser, Thomas, and Carlo Sequin. “Adaptive Display Algorithm for Interactive Frame Rates During Visualization of Complex Virtual Environments”. Computer Graphics, Vol 27 (SIGGRAPH 93).
8. Hoppe, Hugues. “Progressive Meshes”, Computer Graphics, Vol 30 (SIGGRAPH 96).
9. Taosong He, L. Hong, A. Kaufman, A. Varshney, and S. Wang. “Voxel-Based Object Simplification”. Proceedings Visualization 95, IEEE Computer Society Press (Atlanta, GA), 1995, pp. 296-303.
10. Kumar, Subodh, D. Manocha, W. Garrett, M. Lin. “Hierarchical Backface Computation”. Proc. Of 7th Eurographics Workshop on Rendering, 1996.
11. Maciel, Paulo, and Shirley, Peter. “Visual Navigation of Large Environments Using Textured Clusters”, Proceedings 1995 SIGGRAPH Symposium on Interactive 3D Graphics (Monterey, CA), 1995, pp. 95-102.
12. Luebke, David. “Hierarchical Structures for Dynamic Polygonal Simplification”. University of North Carolina Department of Computer Science Tech Report #TR96-006, January, 1996.
13. Ohshima, Toshikazu, H. Yamamoto, H. Tamura. “Gaze- Directed Adaptive Rendering for Interacting with Virtual Space.” Proc. of lEEE 1996 Virtual Reality Annual Intnl. Symposium. (1996), pp 103- 110.
14. Rohlf, John and James Helman. “IRIS Performer: A High Performance Multiprocessing Toolkit for Real-Time 3D Graphics”, Computer Graphics, Vol 28 (SIGGRAPH 94).
15. Rossignac, Jarek, and Paul Borrel. “Multi-Resolution 3D Approximations for Rendering Complex Scenes”, pp. 455-465 in Geometric Modeling in Computer Graphics, Springer-Verlag, Eds. B. Falcidieno and T.L. Kunii, Genova, Italy, 6/28/93-7/2/93. Also published as IBM Research Report RC17697 (77951) 2/19/92.
16. Schroeder, William, Jonathan Zarge and William Lorenson, “Decimation of Triangle Meshes”, Computer Graphics, Vol 26 (SIGGRAPH 92)
17. Shirman, L., and Abi-Ezzi, S. “The Cone of Normals Technique for Fast Processing of Curved Patches”, Computer Graphics Forum (Proc. Eurographics ’93) Vol 12, No 3, (1993), pp 261-272.
18. Teller, Seth, and Carlo Sequin. “Visibility Preprocessing for Interactive Walkthroughs”, Computer Graphics, Vol 25 (SIGGRAPH 91).
19. Turk, Greg. “Re-tiling Polygonal Surfaces”, Computer Grap hics, Vol 26 (SIGGRAPH 92).
20. Varshney, Amitabh. “Hierarchical Geometry Approximations”, Ph.D. Thesis, University of North Carolina Department of Computer Science Tech Report TR-050
21. Xia, Julie and Amitabh Varshney. “Dynamic View- Dependent Simplification for Polygonal Models”, Visualization 96.