skip to main content
article

Adaptive tetrapuzzles: efficient out-of-core construction and visualization of gigantic multiresolution polygonal models

Published: 01 August 2004 Publication History

Abstract

We describe an efficient technique for out-of-core construction and accurate view-dependent visualization of very large surface models. The method uses a regular conformal hierarchy of tetrahedra to spatially partition the model. Each tetrahedral cell contains a precomputed simplified version of the original model, represented using cache coherent indexed strips for fast rendering. The representation is constructed during a fine-to-coarse simplification of the surface contained in diamonds (sets of tetrahedral cells sharing their longest edge). The construction preprocess operates out-of-core and parallelizes nicely. Appropriate boundary constraints are introduced in the simplification to ensure that all conforming selective subdivisions of the tetrahedron hierarchy lead to correctly matching surface patches. For each frame at runtime, the hierarchy is traversed coarse-to-fine to select diamonds of the appropriate resolution given the view parameters. The resulting system can interatively render high quality views of out-of-core models of hundreds of millions of triangles at over 40Hz (or 70M triangles/s) on current commodity graphics platforms.

Supplemental Material

MOV File

References

[1]
BOTSCH, M., AND KOBBELT, L. 2003. High-quality point-based rendering on modern GPUs. In Proc. Pacific Graphics, 335--343.
[2]
CHIANG, Y.-J., GOODRICH, M. T., GROVE, E. F., TAMASSIA, R., VENGROFF, D. E., AND VITTER, J. S. 1995. External-memory graph algorithms. In Proc. ACM-SIAM Symposium on Discrete Algorithms, 139--149.
[3]
CHIANG, Y.-J., EL-SANA, J., LINDSTROM, P., PAJAROLA, R., AND SILVA, C. T. 2003. Out-of-core algorithms for scientific visualization and computer graphics. IEEE Visualization 2003, Tutorial 4 Course Notes.
[4]
CIGNONI, P., MONTANI, C., ROCCHINI, C., AND SCOPIGNO, R. 2003. External memory management and simplification of huge meshes. IEEE Transactions on Visualization and Computer Graphics 9, 525--337.
[5]
CIGNONI, P., DE FLORIANI, L., PASCUCCI, V., ROSSIGNAC, J., AND SILVA, C. T. 2003. Multiresolution modeling, visualization, and compression of volumetric data. IEEE Visualization 2003, Tutorial 3 Course Notes.
[6]
CIGNONI, P., GANOVELLI, F., GOBBETTI, E., MARTON, F., PONCHIO, F., AND SCOPIGNO, R. 2003. BDAM -- batched dynamic adaptive meshes for high performance terrain visualization. Computer Graphics Forum 22, 3, 505--514.
[7]
COHEN-OR, D., AND LEVANONI, Y. 1996. Temporal continuity of levels of detail in delaunay triangulated terrain. In IEEE Visualization '96, IEEE.
[8]
DACHSBACHER, C., VOGELSGANG, C., AND STAMMINGER, M. 2003. Sequential point trees. In Proc. SIGGRAPH, 657--662.
[9]
DUCHAINEAU, M., WOLINSKY, M., SIGETI, D., MILLER, M., ALDRICH, C., AND MINEEV-WEINSTEIN, M. 1997. ROAMing terrain: Real-time optimally adapting meshes. In Proceedings IEEE Visualization '97, IEEE, 81--88.
[10]
EL-SANA, J., AND CHIANG, Y.-J. 2000. External memory view-dependent simplification. Computer Graphics Forum 19, 3(Aug.), 139--150.
[11]
EL-SANA, J., AND VARSHNEY, A. 1999. Generalized view-dependent simplification. Computer Graphics Forum 18, 3, 83--94.
[12]
ERIKSON, C., MANOCHA, D., AND BAXTER, W. 2001. HLODs for faster display of large static and dynamic environments. In Proc. ACM Symposium on Interactive 3D Graphics, 111--120.
[13]
FISCHER, K., ANDGÄRTNER, B. 2003. The smallest enclosing ball of balls: combinatorial structure and algorithms. In Proceedings of the nineteenth conference on Computational geometry, ACM Press, 292--301.
[14]
GREGORSKI, B., DUCHAINEAU, M., LINDSTROM, P., PASCUCCI, V., AND JOY, K. I. 2002. Interactive view-dependent rendering of large IsoSurfaces. In Proc. IEEE Visualization, 475--484.
[15]
HOPPE, H. 1997. View-dependent refinement of progressive meshes. In SIGGRAPH 97 Conference Proceedings, Addison Wesley, T. Whitted, Ed., Annual Conference Series, ACM SIGGRAPH, 189--198. ISBN 0-89791-896-7.
[16]
HOPPE, H. 1998. Smooth view-dependent level-of-detail control and its aplications to terrain rendering. In IEEE Visualization '98 Conf., 35--42.
[17]
HOPPE, H. 1999. New quadric metric for simplifying meshes with appearance attributes. In Proceedings of the 10th Annual IEEE Conference on Visualization (VIS-99), ACM Press, New York, pages 59--66.
[18]
ISENBURG, M., LINDSTROM, P., GUMHOLD, S., AND J. SNOEYINK. 2003. Large mesh simplification using processing sequences. In Proc. IEEE Visualization.
[19]
ISENBURG, M. 2001. Triangle strip compression. Computer Graphics Forum 20, 2, 91--101.
[20]
LEVENBERG, J. 2002. Fast view-dependent level-of-detail rendering using cached geometry. In Proceedings IEEE Visualization '02, IEEE, 259--266.
[21]
LINDSTROM, P., AND PASCUCCI, V. 2002. Terrain simplification simplified: A general framework for view-dependent out-of-core visualization. IEEE Transaction on Visualization and Computer Graphics 8, 3, 239--254.
[22]
LINDSTROM, P. 2000. Out-of-core simplification of large polygonal models. In Comp. Graph. Proc., Annual Conf. Series (SIGGRAPH 2000), ACM Press, Addison Wesley, 259--262.
[23]
LINDSTROM, P. 2003. Out-of-core construction and visualization of multiresolution surfaces. In ACM 2003 Symposium on Interactive 3D Graphics, 93--102, 239.
[24]
LUEBKE, D., AND ERIKSON, C. 1997. View-dependent simplification of arbitrary polygonal environments. In ACM Computer Graphics Proc., Annual Conference Series, (SIGGRAPH 97), 199--208.
[25]
MAUBACH, J. 1995. Local bisection refinement for n-simplicial grids generated by bisection. SIAM Journal of Scientific Computing 16, 210--227.
[26]
OHLBERGER, M., AND RUMPF, M. 1998. Adaptive projection operators in multiresolution scientific visualization. IEEE Transactions on Visualization and Computer Graphics 4, 4, 344--364.
[27]
PASCUCCI, V. 2002. Slow growing subdivision (SGS) in any dimension: Towards removing the curse of dimensionality. Computer Graphics Forum 21, 3, 451--460.
[28]
POMERANZ, A. A. 2000. ROAM Using Surface Triangle Clusters (RUSTiC). Master's thesis, University of California at Davis.
[29]
PRINCE, C. 2000. Progressive Meshes for Large Models of Arbitrary Topology. Master's thesis, Department of Computer Science and Engineering, University of Washington, Seattle.
[30]
RUSINKIEWICZ, S., AND LEVOY, M. 2000. QSplat: A multiresolution point rendering system for large meshes. In Comp. Graph. Proc., Annual Conf. Series (SIGGRAPH 00), ACM Press, 343--352.
[31]
SAMET, H. 1990. Applications of Spatial Data Structures. Addison Wesley, Reading, MA.
[32]
SHAFFER, E., AND GARLAND, M. 2001. Efficient adaptive simplification of massive meshes. In Proc. IEEE Visualization 2001, IEEE Press, 127--134.
[33]
WU, J., AND KOBBELT, L. 2003. A stream algorithm for the decimation of massive meshes. In Proc. Graphics Interface, 185--192.
[34]
XIA, J., AND VARSHNEY, A. 1996. Dynamic view-dependent simplification for polygonal models. In IEEE Visualization '96 Proc., R. Yagel and G. Nielson, Eds., 327--334.

Cited By

View all
  • (2024)LetsGo: Large-Scale Garage Modeling and Rendering via LiDAR-Assisted Gaussian PrimitivesACM Transactions on Graphics10.1145/368776243:6(1-18)Online publication date: 19-Nov-2024
  • (2024)Neural Geometry Fields For MeshesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657399(1-11)Online publication date: 13-Jul-2024
  • (2023)View-dependent Adaptive HLOD: real-time interactive rendering of multi-resolution modelsProceedings of the 20th ACM SIGGRAPH European Conference on Visual Media Production10.1145/3626495.3626507(1-10)Online publication date: 30-Nov-2023
  • Show More Cited By

Index Terms

  1. Adaptive tetrapuzzles: efficient out-of-core construction and visualization of gigantic multiresolution polygonal models

          Recommendations

          Comments

          Information & Contributors

          Information

          Published In

          cover image ACM Transactions on Graphics
          ACM Transactions on Graphics  Volume 23, Issue 3
          August 2004
          684 pages
          ISSN:0730-0301
          EISSN:1557-7368
          DOI:10.1145/1015706
          Issue’s Table of Contents
          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          Published: 01 August 2004
          Published in TOG Volume 23, Issue 3

          Permissions

          Request permissions for this article.

          Check for updates

          Author Tags

          1. Level of Detail
          2. Out-Of-Core Algorithms

          Qualifiers

          • Article

          Contributors

          Other Metrics

          Bibliometrics & Citations

          Bibliometrics

          Article Metrics

          • Downloads (Last 12 months)22
          • Downloads (Last 6 weeks)5
          Reflects downloads up to 17 Feb 2025

          Other Metrics

          Citations

          Cited By

          View all
          • (2024)LetsGo: Large-Scale Garage Modeling and Rendering via LiDAR-Assisted Gaussian PrimitivesACM Transactions on Graphics10.1145/368776243:6(1-18)Online publication date: 19-Nov-2024
          • (2024)Neural Geometry Fields For MeshesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657399(1-11)Online publication date: 13-Jul-2024
          • (2023)View-dependent Adaptive HLOD: real-time interactive rendering of multi-resolution modelsProceedings of the 20th ACM SIGGRAPH European Conference on Visual Media Production10.1145/3626495.3626507(1-10)Online publication date: 30-Nov-2023
          • (2023)Micro-Mesh ConstructionACM Transactions on Graphics10.1145/359244042:4(1-18)Online publication date: 26-Jul-2023
          • (2022)Protection of Intangible Cultural Heritage Based on VR: Taking Xiuyan Jade Carving Craft as an ExampleMathematical Problems in Engineering10.1155/2022/51461932022(1-8)Online publication date: 4-Aug-2022
          • (2022)Fiblets for Real‐Time Rendering of Massive Brain TractogramsComputer Graphics Forum10.1111/cgf.1448641:2(447-460)Online publication date: 24-May-2022
          • (2022)A Memory Efficient Encoding for Ray Tracing Large Unstructured DataIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.311486928:1(583-592)Online publication date: 1-Jan-2022
          • (2022)A novel method for adaptive terrain rendering using memory-efficient tessellation codes for virtual globesJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2022.09.01734:10(9393-9408)Online publication date: Nov-2022
          • (2022)An integrative view of foveated renderingComputers and Graphics10.1016/j.cag.2021.10.010102:C(474-501)Online publication date: 1-Feb-2022
          • (2022)High‐performance virtual globe GPU terrain rendering using game engineComputer Animation and Virtual Worlds10.1002/cav.210834:2Online publication date: 10-Aug-2022
          • Show More Cited By

          View Options

          Login options

          Full Access

          View options

          PDF

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader

          Figures

          Tables

          Media

          Share

          Share

          Share this Publication link

          Share on social media