Sparse terrain pyramids

ABSTRACT

Bintrees based on longest edge bisection and hierarchies of diamonds are popular multiresolution techniques on regularly sampled terrain datasets. In this work, we consider Sparse Terrain Pyramids as a compact multiresolution representation for terrain datasets whose samples are a subset of those lying on a regular grid. While previous diamond-based approaches can efficiently represent meshes built on a complete grid of resolution (2^k +1)², this is not suitable when the field values are uniform in large areas or simply non-existent. We explore properties of diamonds to simplify an encoding of the implicit dependency relationship between diamonds. Additionally, we introduce a diamond clustering technique to further reduce the geometric and topological overhead of such representations. We demonstrate the coherence of our clustering technique as well as the compactness of our representation.

REFERENCES

• 1: J. Blow. Terrain Rendering at High Levels of Detail. Proc. of the 2000 Game Developers Conference, 2000.
• 2: P. Cignoni, F. Ganovelli, E. Gobbetti, F. Marton, F. Ponchio, and R. Scopigno. BDAM- Batched Dynamic Adaptive Meshes for High Performance Terrain Visualization. Computer Graphics Forum, 22(3):505--514, 2003.
• 3: Paolo Cignoni , Fabio Ganovelli , Enrico Gobbetti , Fabio Marton , Federico Ponchio , Roberto Scopigno, Planet-Sized Batched Dynamic Adaptive Meshes (P-BDAM), Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.20, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250366]
• 4: L. De Floriani and P. Magillo. Multi-resolution mesh representation: models and data structures. In M. Floater, A. Iske, and E. Quak, editors, Principles of Multi-resolution Geometric Modeling, Lecture Notes in Mathematics, pages 364--418, Berlin, 2002. Springer Verlag.
• 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: L. De Floriani, E. Puppo, and P. Magillo. Applications of computational geometry to Geographic Information Systems. In J. R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, chapter 7, pages 333--388. Elsevier Science, 1999.
• 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: Thomas Gerstner, Multiresolution Compression and Visualization of Global Topographic Data, Geoinformatica, v.7 n.1, p.7-32, March 2003 [doi>10.1023/A:1022818126783]
• 10: T. Gerstner. Top-down view-dependent terrain triangulation using the octagon metric. Technical report, Institut für Angewandte Mathematik, University of Bonn, 2003.
• 11: Benjamin Gregorski , Mark Duchaineau , Peter Lindstrom , Valerio Pascucci , Kenneth I. Joy, Interactive view-dependent rendering of large isosurfaces, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 12: Lok M. Hwa , Mark A. Duchaineau , Kenneth I. Joy, Real-Time Optimal Adaptation for Planetary Geometry and Texture: 4-8 Tile Hierarchies, IEEE Transactions on Visualization and Computer Graphics, v.11 n.4, p.355-368, July 2005 [doi>10.1109/TVCG.2005.65]
• 13: Sylvain Lefebvre , Hugues Hoppe, Perfect spatial hashing, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 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: Peter Lindstrom , Valerio Pascucci, Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualization, IEEE Transactions on Visualization and Computer Graphics, v.8 n.3, p.239-254, July 2002 [doi>10.1109/TVCG.2002.1021577]
• 16: David Luebke , Benjamin Watson , Jonathan D. Cohen , Martin Reddy , Amitabh Varshney, Level of Detail for 3D Graphics, Elsevier Science Inc., New York, NY, 2002
• 17: Joseph M. Maubach, Local bisection refinement for N-simplicial grids generated by reflection, SIAM Journal on Scientific Computing, v.16 n.1, p.210-227, Jan. 1995 [doi>10.1137/0916014]
• 18: 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
• 19: Renato Pajarola , Enrico Gobbetti, Survey of semi-regular multiresolution models for interactive terrain rendering, The Visual Computer: International Journal of Computer Graphics, v.23 n.8, p.583-605, July 2007 [doi>10.1007/s00371-007-0163-2]
• 20: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 21: R. Sivan and H. Samet. Algorithms for constructing quadtree surface maps. Proc. 5th Int. Symposium on Spatial Data Handling, pages 361--370, 1992.
• 22: U.S. Geological Survey. Global 30 arc second elevation data. http://edc.usgs.gov/products/elevation/gtopo30/gtopo30.html.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

Keywords:
diamond hierarchies, longest edge bisection, multiresolution terrain models, nested triangle meshes