“View-dependent refinement of progressive meshes” by Hoppe

Level-of-detail (LOD) representations are an important tool for real-time rendering of complex geometric environments. The previously introduced progressive mesh representation defines for an arbitrary triangle mesh a sequence of approximating meshes optimized for view-independent LOD. In this paper, we introduce a framework for selectively refining an arbitrary progressive mesh according to changing view parameters. We define efficient refinement criteria based on the view frustum, surface orientation, and screen-space geometric error, and develop a real-time algorithm for incrementally refining and coarsening the mesh according to these criteria. The algorithm exploits view coherence, supports frame rate regulation, and is found to require less than 15% of total frame time on a graphics workstation. Moreover, for continuous motions this work can be amortized over consecutive frames. In addition, smooth visual transitions (geomorphs) can be constructed between any two selectively refined meshes. A number of previous schemes create view-dependent LOD meshes for height fields (e.g. terrains) and parametric surfaces (e.g. NURBS). Our framework also performs well for these special cases. Notably, the absence of a rigid subdivision structure allows more accurate approximations than with existing schemes. We include results for these cases as well as for general meshes.

1. ABI-EzzI, S. S., AND SUBRAMANIAM, S. Fast dynamic tessellation of trimmed NURBS surfaces. Computer Graphics Forum (Proceedings of Eurographics ’94) 13, 3 (1994), 107-126.
2. BAJAJ, C., AND SCHIKORE, D. Error-bounded reduction of triangle meshes with multivariate data. SPIE 2656 (1996), 34-45.
3. CIGNONI, P., PuPPO, E., AND SCOPIGNO, R. Representation and visualization of terrain surfaces at variable resolution. In Scientific Visualization ’95 (1995), R. Scateni, Ed., World Scientific, pp. 50-68.
4. CLARK, J. Hierarchical geometric models for visible surface algorithms. Communications of the ACM 19, 10 (October 1976), 547-554.
5. COHEN, J., VARSHNEY, A., MANOCHA, D., TURK, Q., WE- BER, H., AGARWAL, P., BROOKS, F., AND WRIGHT, W. Simplification envelopes. Computer Graphics (SIGGRAPH ’96 Proceedings) (1996), 119-128.
6. DE FLORIANI, L., MARZANO, P., AND PUPPO, E. Multiresolution models for topographic surface description. The Visual Computer 12, 7 (1996), 317-345.
7. EVANS, F., SKIENA, S., AND VARSHNEY, A. Optimizing triangle strips for fast rendering. In Visualization ’96 Proceedings (1996), IEEE, pp. 319-326.
8. FUNKHOUSER, T., AND SI~QUIN, C. Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments. Computer Graphics (SIGGRAPH ’93 Proceedings) (1993), 247-254.
9. GU~ZIEC, A. Surface simplification with variable tolerance. In Proceedings of the Second International Symposium on Medical Robotics and Computer Assisted Surgery (November 1995), pp. 132-139.
10. HOPPE, H. Progressive meshes. Computer Graphics (SIGGRAPH ’96 Proceedings) (1996), 99-108.
11. KIRKPATRICK, D. Optimal search in planar subdivisions. SIAM Journal on Computing 12, 1 (February 1983), 28-35.
12. KUMAR, S., AND MANOCHA, D. Hierarchical visibility culling for spline models. In Proceedings of Graphics Interface ’96 (1996), pp. 142-150.
13. KUMAR, S., MANOCHA, D., AND LASTRA, A. Interactive display of large-scale NURBS models. In 1995 Symposium on Interactive 3D Graphics (1995), ACM SIGGRAPH, pp. 51-58.
14. LINDSTROM, P., KOLLER, D., RIBARSKY, W., HODGES, L., FAUST, N., AND TURNER, G. Real-time, continuous level of detail rendering of height fields. Computer Graphics (SIGGRAPH ’96 Proceedings) (1996), 109-118.
15. LOUNSBERY, M., DEROSE, T., AND WARREN, J. Multiresolution surfaces of arbitrary topological type. ACM Transactions on Graphics 16, 1 (January 1997), 34-73.
16. LUEBKE, D. Hierarchical structures for dynamic polygonal simplification. TR 96-006, Department of Computer Science, University of North Carolina at Chapel Hill, 1996.
17. OHSHIMA, T., YAMAMOTO, H., AND TAMURA, H. Gaze-directed adaptive rendering for interacting with virtual space. In Proc. oflEEE 1996 Virtual Reality Annual Intnl. Syrup. (1996), pp. 103-110.
18. ROCKWOOD, A., HEATON, K., AND DAVIS, T. Real-time rendering of trimmed surfaces. In Computer Graphics (SIGGRAPH ’89 Proceedings) (1989), vol. 23, pp. 107-116.
19. ROSSIGNAC, J., AND BORREL, P. Multi-resolution 3D approximations for rendering complex scenes. In Modeling in Computer Graphics, B. Falcidieno and T. L. Kunii, Eds. Springer-Verlag, 1993, pp. 455-465.
20. SCARLATOS, L. L. A refined triangulation hierarchy for multiple levels of terrain detail. In Proceedings, IMAGE V Conference (June 1990), pp. 115-122.
21. SCHROEDER, W., ZARGE, J., AND LORENSEN, W. Decimation of triangle meshes. Computer Graphics (SIGGRAPH ‘ 92 Proceedings) 26, 2 (1992), 65-70.
22. SHIRMAN, L., AND ABI-EzzI, S. The cone of normals technique for fast processing of curved patches. Computer Graphics Forum (Proceedings of Eurographics ’93) 12, 3 (1993), 261-272.
23. TAYLOR, D. C., AND BARRETT, W. A. An algorithm forcontinuous resolution polygonalizations of a discrete surface. In Proceedings of Graphics Interface ’94 (1994), pp. 33-42.
24. XlA, J., AND VARSHNEY, A. Dynamic view-dependent simplification for polygonal models. In Visualization ’96 Proceedings (1996), IEEE, pp. 327-334.