“Real-time, continuous level of detail rendering of height fields” by Lindstrom, Koller, Ribarsky, Hodges, Faust, et al. …

We present an algorithm for real-time level of detail reduction and display of high-complexity polygonal surface data. The algorithm uses a compact and efficient regular grid representation, and employs a variable screen-space threshold to bound the maximum error of the projected image. A coarse level of simplification is performed to select discrete levels of detail for blocks of the surface mesh, followed by further simplification through repolygonalization in which individual mesh vertices are considered for removal. These steps compute and generate the appropriate level of detail dynamically in real-time, minimizing the number of rendered polygons and allowing for smooth changes in resolution across areas of the surface. The algorithm has been implemented for approximating and rendering digital terrain models and other height fields, and consistently performs at interactive frame rates with high image quality.

1. AKELEY, K. RealityEngine Graphics. Proceedings of SIGGRAPH 93. In Computer Graphics Proceedings, Annual Conference Series, 1993, ACM SIG- GRAPH, pp. 109-116.
2. COSMAN, M. A., MATHISEN, A. E., and ROBINSON, J. A. A New Visual System to Support Advanced Requirements. In Proceedings, IMAGE V Conference, June 1990, pp. 370-380.
3. DE BERG, M. and DOBRINDT, K. T. G. On Levels of Detail in Terrains. In 11 th ACM Symposium on Computational Geometry, June 1995.
4. DE FLORIANI, L. and PuPPO, E. Hierarchical Triangulation for Multiresolution Surface Description. ACM Transactions on Graphics 14(4), October 1995, pp. 363-411.
5. DOUGLAS, D. H. Experiments to Locate Ridges and Channels to Create a New Type of Digital Elevation Model. Cartographica 23(4), 1986, pp. 29-61.
6. ECK, M., DEROSE, T., DUCHAMP, T., HOPPE, H., LOUNSBERY, M., and STUETZLE, W. Multiresolution Analysis of Arbitrary Meshes. Proceedings of SIGGRAPH 95. In Computer Graphics Proceedings, Annual Conference Series, 1995, ACM SIGGRAPH, pp. 173-182.
7. FALBY, J. S., ZYDA, M. J., PRATT, D. R., and MACKEY, R. L. NPSNET: Hierarchical Data Structures for Real-Time Three-Dimensional Visual Simulation. Computers & Graphics 17(1), 1993, pp. 65-69.
8. FERGUSON, R. L., ECONOMY, R., KELLY, W. A., and RAMOS, P. P. Continuous Terrain Level of Detail for Visual Simulation. In P~vceedings, IMAGE V Conference, June 1990, pp. 144-151.
9. FOWLER, R. J. and LITTLE, J. J. Automatic Extraction of Irregular Network Digital Terrain Models. Proceedings of SIGGRAPH 79. In Computer Graphics 13(2) (August 1979),pp. 199-207.
10. GARLAND, M. and HECKBERT, P. S. Fast Polygonal Approximation of Terrains and Height Fields. Technical Report CMU-CS-95-181, CS Dept., Carnegie Mellon U., 1995.
11. Graphics Library P1vgramming Guide. Silicon Graphics Computer Systems, 1991.
12. GROSS, M. H., GATTI, e., and STAADT, O. Fast Multiresolution Surface Meshing. In P1vceedings of Visualization ’95, October 1995, pp. 135-142.
13. HECKBERT, P. S. and GARLAND, M. Multiresolution Modeling for Fast Rendering. In P1vceedings of Graphics Intelface ’94, 1994, pp. 1-8.
14. HOPPE, H., DEROSE, T., DUCHAMP, T., MCDONALD, J., and STUETZLE, W. Mesh Optimization. Proceedings of SIGGRAPH 93. In Computer Graphics Proceedings, Annual Conference Series, 1993, ACM SIGGRAPH, pp. 19-26.
15. NEIDER, J., DAVIS, T., and WOO, M. OpenGL P~vgramming Guide. Addison- Wesley, 1993.
16. ROHLF, J. and HELMAN, J. IRIS Performer: A High Performance Multiprocessing Toolkit for Real-Time 3D Graphics. Proceedings of SIGGRAPH 94. In Computer Graphics Proceedings, Annual Conference Series, 1993, ACM SIG- GRAPH, pp. 381-394.
17. S AMET, H. The Quadtree and Related Hierarchical Data Structures. ACM Computing Surveys 16(2), June 1984, pp. 187-260.
18. SCARLATOS, L. L. A Refined Triangulation Hierarchy for Multiple Levels of Terrain Detail. In P~vceedings, IMAGE V Conference, June 1990, pp. 114-122.
19. SCHRODER, F. and ROSSBACH, P. Managing the Complexity of Digital Terrain Models. Computers & Graphics 18(6), 1994, pp. 775-783.
20. SCHRoEDER, W. J., ZARGE, J. A., and LORENSON, W. E. Decimation of Triangle Meshes. Proceedings of SIGGRAPH 92. In Computer Graphics 26(2) (July 1992), pp. 65-70.
21. SOUTHARD, D. A. Piecewise Planar Surface Models from Sampled Data. Scientific Visualization of Physical Phenomena, June 1991, pp. 667-680.
22. TAYLOR, D. C. and BARRET, W. A. An Algorithm for Continuous Resolution Polygonalizations of a Discrete Surface. In P~vceedings of Graphics Interface ’94, 1994,pp. 33-42.