Regular and irregular multi-resolution terrain models: a comparison

ABSTRACT

The paper deals with the problem of modeling large-size terrain data sets. To this aim, we consider multi-resolution models based on triangle meshes. We analyze and compare two multi-resolution terrain models based on regular and irregular meshes. The two models are viewed as instances of a common multi-resolution model, that we call a multi-resolution triangle mesh. Our comparison takes into account the space requirements of the data structures implementing the two models as well their effectiveness in supporting the extraction of variable-resolution terrain representations.

REFERENCES

• 1: Emanuele Danovaro , Leila De Floriani , Paola Magillo , Enrico Puppo, Compressing Multiresolution Triangle Meshes, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.345-364, July 12-15, 2001
• 2: Mark de Berg , Katrin Dobrindt, On levels of detail in terrains, Proceedings of the eleventh annual symposium on Computational geometry, p.426-427, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220334]
• 3: Leila De Floriani, A Pyramidal Data Structure for Triangle-Based Surface Description, IEEE Computer Graphics and Applications, v.9 n.2, p.67-78, March 1989 [doi>10.1109/38.19053 ]
• 4: L. De Floriani and P. Magillo. Multiresolution mesh representation: Models and data structures. In M.Floater, A.Iske, and E.Qwak, editors, Tutorials on Multiresolution in Geometric Modelling, pages 363--418. Springer-Verlag, 2002.
• 5: Leila De Floriani , Paola Magillo , Enrico Puppo, VARIANT: A System for Terrain Modeling at Variable Resolution, Geoinformatica, v.4 n.3, p.287-315, October 2000 [doi>10.1023/A:1009805426595 ]
• 6: Leila De Floriani , Enrico Puppo, Hierarchical triangulation for multiresolution surface description, ACM Transactions on Graphics (TOG), v.14 n.4, p.363-411, Oct. 1995 [doi>10.1145/225294.225297]
• 7: Mark Duchaineau , Murray Wolinsky , David E. Sigeti , Mark C. Miller , Charles Aldrich , Mark B. Mineev-Weinstein, ROAMing terrain: real-time optimally adapting meshes, Proceedings of the 8th conference on Visualization '97, p.81-88, October 18-24, 1997, Phoenix, Arizona, United States
• 8: W. Evans, D. Kirkpatrick, and G. Townsend. Right-triangulated irregular networks. Algorithmica, 30(2):264--286, 2001.
• 9: D. Gomez and A. Guzman. Digital model for three-dimensional surface representation. Geo-Processing, 1:53--70, 1979.
• 10: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 11: Hugues Hoppe, Smooth view-dependent level-of-detail control and its application to terrain rendering, Proceedings of the conference on Visualization '98, p.35-42, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 12: R. Klein and S. Gumhold. Data compression of multiresolution surfaces. In Visualization in Scientific Computing '98, Springer-Verlag, pages 13--24. 1998.
• 13: Michael Lee , Hanan Samet , Leila de Floriani, Constant-Time Neighbor Finding in Hierarchical Tetrahedral Meshes, Proceedings of the International Conference on Shape Modeling & Applications, p.286, May 07-11, 2001
• 14: Peter Lindstrom , David Koller , William Ribarsky , Larry F. Hodges , Nick Faust , Gregory A. Turner, Real-time, continuous level of detail rendering of height fields, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.109-118, August 1996 [doi>10.1145/237170.237217]
• 15: Anil Maheshwari , Pat Morin , Jörg-Rüdiger Sack, Progressive TINs: algorithms and applications, Proceedings of the 5th ACM international workshop on Advances in geographic information systems, p.24-29, November 10-14, 1997, Las Vegas, Nevada, United States [doi>10.1145/267825.267834]
• 16: Renato Pajarola, Large scale terrain visualization using the restricted quadtree triangulation, Proceedings of the conference on Visualization '98, p.19-26, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 17: E. Puppo, Variable resolution triangulations, Computational Geometry: Theory and Applications, v.11 n.3-4, p.219-238, Dec. 1998
• 18: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 19: R. Sivan and H. Samet. Algorithms for constructing quadtree surface maps. In Proceedings 5th International Symposium on Spatial Data Handling, pages 361--370, 1992.
• 20: Gabriel Taubin , André Guéziec , William Horn , Francis Lazarus, Progressive forest split compression, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.123-132, July 1998 [doi>10.1145/280814.280834]
• 21: Brian Von Herzen , Alan H. Barr, Accurate triangulations of deformed, intersecting surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.103-110, July 1987
• 22: Julie C. Xia , Jihad El-Sana , Amitabh Varshney, Adaptive Real-Time Level-of-Detail-Based Rendering for Polygonal Models, IEEE Transactions on Visualization and Computer Graphics, v.3 n.2, p.171-183, April 1997 [doi>10.1109/2945.597799 ]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms

Keywords:
multi-resolution, regular and irregular structures, terrain models