Multi-resolution out-of-core modeling of terrain and teological data

ABSTRACT

Multi-resolution is a useful tool for managing the complexity of huge terrain and geological data sets. Since encoding large data sets may easily exceed main memory capabilities, data structures and algorithms capable of efficiently working in external memory are needed. In our work, we aim at developing an out-of-core multi-resolution model dimension-independent, that can be used for both terrains, represented by Triangulated Irregular Networks(TINs), and 3D data, such as geological data, represented by tetrahedral meshes. We have based our approach on a general multi-resolution model, that we have proposed in our previous work, which supports the extraction of variable-resolution representations. As first step, we have developed, in a prototype simulation system, a large number of clustering techniques for the modifications in a multi-resolution model. Here, we describe such techniques, and analyze and evaluate them experimentally. The result of this investigation has led us to select a specific clustering approach as the basis for an efficient out-of-core data structure.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 2: Paolo Cignoni , Leila De Floriani , Paola Magillo , Enrico Puppo , Roberto Scopigno, Selective Refinement Queries for Volume Visualization of Unstructured Tetrahedral Meshes, IEEE Transactions on Visualization and Computer Graphics, v.10 n.1, p.29-45, January 2004 [doi>10.1109/TVCG.2004.1260756]
• 3: 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, September 2003.
• 4: Paolo Cignoni , Fabio Ganovelli , Enrico Gobbetti , Fabio Marton , Federico Ponchio , Roberto Scopigno, Adaptive tetrapuzzles: efficient out-of-core construction and visualization of gigantic multiresolution polygonal models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 5: Paolo Cignoni , Claudio Montani , Claudio Rocchini , Roberto Scopigno, External Memory Management and Simplification of Huge Meshes, IEEE Transactions on Visualization and Computer Graphics, v.9 n.4, p.525-537, October 2003 [doi>10.1109/TVCG.2003.1260746]
• 6: E. Danovaro. Multi-resolution Modeling of Discrete Scalar Fields. PhD thesis, Dept. of Computer and Information Sciences, University of Genova (Italy), 2005.
• 7: Emanuele Danovaro , Leila De Floriani , Paola Magillo , Enrico Puppo , Davide Sobrero , Neta Sokolovsky, The Half-Edge Tree: A Compact Data Structure for Level-of-Detail Tetrahedral Meshes, Proceedings of the International Conference on Shape Modeling and Applications 2005 (SMI' 05), p.334-339, June 13-17, 2005 [doi>10.1109/SMI.2005.47]
• 8: 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]
• 9: L. De Floriani, E. Puppo, and P. Magillo. A formal approach to multi-resolution modeling. In W. Strasser, R. Klein, and R. Rau, editors, Geometric Modeling: Theory and Practice, pages 302--323. Springer-Verlag, 1997.
• 10: Christopher DeCoro , Renato Pajarola, XFastMesh: fast view-dependent meshing from external memory, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 11: J. El-Sana and Y.-J. Chiang. External memory view-dependent simplification. Computer Graphics Forum, 19(3):139--150, August 2000.
• 12: Michael Garland , Eric Shaffer, A multiphase approach to efficient surface simplification, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 13: 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
• 14: Martin Isenburg , Peter Lindstrom , Stefan Gumhold , Jack Snoeyink, Large Mesh Simplification using Processing Sequences, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.61, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250408]
• 15: Peter Lindstrom, Out-of-core simplification of large polygonal models, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.259-262, July 2000 [doi>10.1145/344779.344912]
• 16: Peter Lindstrom, Out-of-core construction and visualization of multiresolution surfaces, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California [doi>10.1145/641480.641500]
• 17: 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]
• 18: Peter Lindstrom , Cláudio T. Silva, A memory insensitive technique for large model simplification, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 19: David Luebke , Benjamin Watson , Jonathan D. Cohen , Martin Reddy , Amitabh Varshney, Level of Detail for 3D Graphics, Elsevier Science Inc., New York, NY, 2002
• 20: P. Magillo. The MT library. http://www.disi.unige.it/person/MagilloP/MT/.
• 21: P. Magillo , V. Bertocci, Managing Large Terrain Data Sets with a Multiresolution Structure, Proceedings of the 11th International Workshop on Database and Expert Systems Applications, p.894, September 06-08, 2000
• 22: E. M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257--276, May 1985.
• 23: J. A. Orenstein. Multidimensional tries used for associative searching. Information Processing Letters, 14(4):150--157, 1982.
• 24: Renato Pajarola, FastMesh: Efficient View-Dependent Meshing, Proceedings of the 9th Pacific Conference on Computer Graphics and Applications, p.22, October 16-18, 2001
• 25: Enrico Puppo, Variable Resolution Terrain Surfaces, Proceedings of the 8th Canadian Conference on Computational Geometry, p.202-210, August 12-15, 1996
• 26: J. Rossignac and P. Borrel. Multi-resolution 3D approximations for rendering complex scenes. In B. Falcidieno and T. L. Kunii, editors, Modeling in Computer Graphics, pages 455--465. Springer-Verlag, October 17--18 1993.
• 27: 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
• 28: Eric Shaffer , Michael Garland, Efficient adaptive simplification of massive meshes, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 29: W. Wang, J. Yang, and R. Muntz. PK-tree: a spatial index structure for high dimensional point data. In K. Tanaka and S. Ghandeharizadeh, editors, Proceedings 5th International Conference on Foundations of Data Organization and Algorithms (FODO), pages 27--36, Kobe, Japan, November 1998.
• 30: Sung-Eui Yoon , Brian Salomon , Russell Gayle , Dinesh Manocha, Quick-VDR: Out-of-Core View-Dependent Rendering of Gigantic Models, IEEE Transactions on Visualization and Computer Graphics, v.11 n.4, p.369-382, July 2005 [doi>10.1109/TVCG.2005.64]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
multi-resolution, out-of-core, terrain models