Abstract
Rendering high quality digital terrains at interactive rates requires carefully crafted algorithms and data structures able to balance the competing requirements of realism and frame rates, while taking into account the memory and speed limitations of the underlying graphics platform. In this survey, we analyze multiresolution approaches that exploit a certain semi-regularity of the data. These approaches have produced some of the most efficient systems to date. After providing a short background and motivation for the methods, we focus on illustrating models based on tiled blocks and nested regular grids, quadtrees and triangle bin-trees triangulations, as well as cluster-based approaches. We then discuss LOD error metrics and system-level data management aspects of interactive terrain visualization, including dynamic scene management, out-of-core data organization and compression, as well as numerical accuracy.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Asano, T., Ranjan, D., Roos, T., Welzl, E., Widmayer, P.: Space filling curves and their use in the design of geometric data structures. Theor. Comput. Sci. 181, 3–15 (1997)
Balmelli, L., Ayer, S., Vetterli, M.: Efficient algorithms for embedded rendering of terrain models. In: Proceedings IEEE International Conference on Image Processing ICIP 98, pp. 914–918 (1998)
Balmelli, L., Liebling, T., Vetterli, M.: Computational analysis of 4-8 meshes with application to surface simplification using global error. In: Electronic Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG) (2001)
Bao, X., Pajarola, R.: LOD-based clustering techniques for optimizing large-scale terrain storage and visualization. In: Proceedings SPIE Conference on Visualization and Data Analysis, pp. 225–235 (2003)
Bao, X., Pajarola, R., Shafae, M.: SMART: an efficient technique for massive terrain visualization from out-of-core. In: Proceedings Vision, Modeling and Visualization (VMV), pp. 413–420 (2004)
Baumann, K., Döllner, J., Hinrichs, K., Kersting, O.: A hybrid, hierarchical data structure for real-time terrain visualization. In: Computer Graphics International, pp. 85–92 (1999)
Cignoni, P., Ganovelli, F., Gobbetti, E., Marton, F., Ponchio, F., Scopigno, R.: BDAM: batched dynamic adaptive meshes for high performance terrain visualization. In: Proceedings EUROGRAPHICS, pp. 505–514 (2003).
Cignoni, P., Ganovelli, F., Gobbetti, E., Marton, F., Ponchio, F., Scopigno, R.: Planet-sized batched dynamic adaptive meshes (P-BDAM). In: Proceedings IEEE Visualization, pp. 147–155. IEEE Press, Washington, DC (2003)
Cignoni, P., Ganovelli, F., Gobbetti, E., Marton, F., Ponchio, F., Scopigno, R.: Batched multi triangulation. In: Proceedings IEEE Visualization, pp. 207–214. IEEE Press, Washington, DC (2005)
Cignoni, P., Montani, C., Scopigno, R.: A comparison of mesh simplification algorithms. Comput. Graph. 22(1), 37–54 (1998)
De Floriani, L., Kobbelt, L., Puppo, E.: A survey on data structures for level-of-detail models. In: N. Dodgson, M. Floater, M. Sabin (eds.) Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization, pp. 49–74. Springer, Berlin Heidelberg New York (2004)
De Floriani, L., Magillo, P., Puppo, E.: Building and traversing a surface at variable resolution. In: IEEE Visualization’97 (1997)
De Floriani, L., Marzano, P., Puppo, E.: Multiresolution models for topographic surface description. Vis. Comput. 12(7), 317–345 (1996)
De Floriani, L., Puppo, E., Magillo, P.: A formal approach to multiresolution modeling. In: R. Klein, W. Straßer, R. Rau (eds.) Geometric Modeling: Theory and Practice, pp. 302–323. Springer, Berlin Heidelberg New York (1997)
Duchaineau, M., Wolinsky, M., Sigeti, D.E., Miller, M.C., Aldrich, C., Mineev-Weinstein, M.B.: ROAMing terrain: Real-time optimally adapting meshes. In: Proceedings IEEE Visualization, pp. 81–88 (1997)
Evans, W., Kirkpatrick, D., Townsend, G.: Right-triangulated irregular networks. Algorithmica 30(2), 264–286 (2001)
Falby, J., Zyda, M., Pratt, D., Mackey, L.: NPSNET: hierarchical data structures for real-time 3-dimensional visual simulation. Comput. Graph. 17(1), 65–69 (1993)
Garland, M.: Multiresolution modeling: survey and future opportunities. Eurographics State of The Art Report (STAR), Aire-la-Ville, Switzerland (1999)
Gerstner, T.: Multiresolution compression and visualization of global topographic data. Tech. Rep. 29. Institute for Applied Mathematics, University of Bonn (1999)
Gerstner, T.: Top-down view-dependent terrain triangulation using the octagon metric. Tech. Rep. Institute of Applied Mathematics, University of Bonn (2003)
Gerstner, T., Pajarola, R.: Topology preserving and controlled topology simplifying multiresolution isosurface extraction. In: Proceedings IEEE Visualization, pp. 259–266. IEEE Press, Washington, DC (2000)
Gerstner, T., Rumpf, M., Weikard, U.: Error indicators for multilevel visualization and computing on nested grids. Comput. Graph. 24(3), 363–373 (2000)
Gobbetti, E., Marton, F., Cignoni, P., Benedetto, M.D., Ganovelli, F.: C-BDAM: compressed batched dynamic adaptive meshes for terrain rendering. Comput. Graph. Forum 25(3), 333–342 (2006)
Hebert, D., Kim, H.: Image encoding with triangulation wavelets. In: Proceedings of SPIE, vol. 2569, pp. 381–392. SPIE, Bellingham, WA (1995)
Heckbert, P.S., Garland, M.: Survey of polygonal surface simplification algorithms. In: SIGGRAPH 97 Course Notes 25 (1997)
Hitchner, L.E., McGreevy, M.W.: Methods for user-based reduction of model complexity for virtual planetary exploration. In: Proceedings Symposium on Electronic Imaging, pp. 1–16. SPIE, Bellingham, WA (1993)
Hoppe, H.: Smooth view-dependent level-of-detail control and its application to terrain rendering. In: Proceedings IEEE Visualization, pp. 35–42. IEEE Press, Washington, DC (1998)
Hwa, L.M., Duchaineau, M.A., Joy, K.I.: Real-time optimal adaptation for planetary geometry and texture: 4-8 tile hierarchies. IEEE Trans. Vis. Comput. Graph. 11(4), 355–368 (2005)
Koller, D., Lindstrom, P., Ribarsky, W., Hodges, L.F., Faust, N., Turner, G.: Virtual GIS: A real-time 3D geographic information system. In: Proceedings IEEE Visualization, pp. 94–100. IEEE Press, Washington, DC (1995)
Lario, R., Pajarola, R., Tirado, F.: Hyperblock-QuadTIN: Hyper-block quadtree based triangulated irregular networks. In: Proceedings IASTED Invernational Conference on Visualization, Imaging and Image Processing (VIIP), pp. 733–738 (2003)
Levenberg, J.: Fast view-dependent level-of-detail rendering using cached geometry. In: Proceedings IEEE Visualization, pp. 259–266. IEEE Press, Washington, DC (2002)
Lindstrom, P., Koller, D., Hodges, L.F., Ribarsky, W., Faust, N., Turner, G.: Level-of-detail management for real-time rendering of phototextured terrain. Tech. Rep. TR 95-06, Graphics, Visualization, and Usability Center, Georgia Tech (1995)
Lindstrom, P., Koller, D., Ribarsky, W., Hodges, L., Faust, N.: An integrated global GIS and visual simulation system. Tech. Rep. GVU Technical Report 97-0, Georgia Tech Research Institute (1997)
Lindstrom, P., Koller, D., Ribarsky, W., Hodges, L.F., Faust, N., Turner, G.A.: Real-time, continuous level of detail rendering of height fields. In: Proceedings ACM SIGGRAPH, pp. 109–118. ACM SIGGRAPH, New York (1996)
Lindstrom, P., Pascucci, V.: Visualization of large terrains made easy. In: Proceedings IEEE Visualization, pp. 363–370. IEEE Press, Washington, DC (2001)
Lindstrom, P., Pascucci, V.: Terrain simplification simplified: a general framework for view-dependent out-of-core visualization. IEEE Trans. Vis. Comput. Graph. 8(3), 239–254 (2002)
Losasso, F., Hoppe, H.: Geometry clipmaps: terrain rendering using nested regular grids. ACM Trans. Graph. 23(3), 769–776 (2004)
Luebke, D.: A developer’s survey of polygonal simplification algorithms. IEEE Comput. Graph. Appl. 21(3), 24–35 (2001)
Luebke, D., Reddy, M., Cohen, J.D., Varshney, A., Watson, B., Huebner, R.: Level of Detail for 3D Graphics. Morgan Kaufmann, San Francisco, CA (2003)
Malvar, H.S.: Fast progressive image coding without wavelets. In: Data Compression Conference, pp. 243–252 (2000)
Ohlberger, M., Rumpf, M.: Adaptive projection operators in multiresolution scientific visualization. IEEE Trans. Vis. Comput. Graph. 5(1), 74–93 (1999)
Pajarola, R.: Large scale terrain visualization using the restricted quadtree triangulation. In: Proceedings IEEE Visualization, pp. 19–26 (1998)
Pajarola, R.: Large scale terrain visualization using the restricted quadtree triangulation. Tech. Rep. 292, Dept. of Computer Science, ETH Zürich (1998)
Pajarola, R., Antonijuan, M., Lario, R.: QuadTIN: Quadtree based triangulated irregular networks. In: Proceedings IEEE Visualization, pp. 395–402. IEEE Press, Washington, DC (2002)
Pajarola, R., Ohler, T., Stucki, P., Szabo, K., Widmayer, P.: The Alps at your fingertips: virtual reality and geoinformation systems. In: Proceedings International Conference on Data Engineering (ICDE), pp. 550–557. IEEE Press, Washington, DC (1998)
Pajarola, R., Widmayer, P.: Virtual geoexploration: concepts and design choices. Int. J. Comput. Geom. Appl. 11(1), 1–14 (2001)
Pomeranz, A.A.: ROAM Using Surface Triangle Clusters (RUSTiC). Dissertation, University of California at Davis (2000)
Puppo, E.: Variable resolution terrain surfaces. In: Proceedings of the 8th Canadian Conference on Computational Geometry, pp. 202–210 (1996)
Puppo, E.: Variable resolution triangulations. Comput. Geom. 11(3–4), 219–238 (1998)
Reddy, M., Leclerc, Y., Iverson, L., Bletter, N.: TerraVision II: visualizing massive terrain databases in VRML. IEEE Comput. Graph. Appl. 19(2), 30–38 (1999)
Rivara, M.C.: A discussion on the triangulation refinement problem. In: Proceedings of the 5th Canadian Conference on Computational Geometry, pp. 42–47 (1993)
Rivara, M.C.: A discussion on mixed (longest-side midpoint insertion) delaunay techniques for the triangulation refinement problem. In: Proceedings of the 4th International Meshing Roundtable, pp. 335–346 (1995)
Samet, H.: Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison Wesley, Reading, MA (1989)
Samet, H.: The Design and Analysis of Spatial Data Structures. Addison Wesley, Reading, MA (1989)
Schneider, J., Westermann, R.: GPU-friendly high-quality terrain rendering. J. WSCG 14(1–3), 49–56 (2006)
Schrack, G.: Finding neighbors of equal size in linear quadtrees and octrees in constant time. Comput. Vision Graph. Image Process. Image Underst. 55(2), 221–230 (1992)
Sivan, R.: Surface modeling using quadtrees. Tech. Rep. CS-TR-3609, University of Maryland, College Park, Computer Vision Laboratory, Center for Automation Research (1996)
Sivan, R., Samet, H.: Algorithms for constructing quadtree surface maps. In: Proceedings of the 5th International Symposium on Spatial Data Handling, pp. 361–370 (1992)
Ulrich, T.: Rendering massive terrains using chunked level of detail. In: Super-size-it! Scaling up to Massive Virtual Worlds (ACM SIGGRAPH Tutorial Notes). ACM SIGGRAPH, New York (2000)
Velho, L.: Using semi-regular 4-8 meshes for subdivision surfaces. J. Graph. Tools 5(3), 35–47 (2001)
Velho, L., Gomes, J.: Variable resolution 4-k meshes: concepts and applications. Comput. Graph. Forum 19(4), 195–214 (2000)
Von Herzen, B., Barr, A.H.: Accurate triangulations of deformed, intersecting surfaces. In: Proceedings ACM SIGGRAPH, pp. 103–110. ACM SIGGRAPH, New York (1987)
Wahl, R., Massing, M., Degener, P., Guthe, M., Klein, R.: Scalable compression and rendering of textured terrain data. J. WSCG 12, 521–528 (2004)
Wloka, M.: Optimizing the graphics pipeline. In: Programming Graphics Hardware (Eurographics 2004 Tutorial No. 4). Eurographics Association, Aire-la-Ville, Switzerland (2004)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pajarola, R., Gobbetti, E. Survey of semi-regular multiresolution models for interactive terrain rendering. Visual Comput 23, 583–605 (2007). https://doi.org/10.1007/s00371-007-0163-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-007-0163-2