“Adaptive tetrapuzzles: efficient out-of-core construction and visualization of gigantic multiresolution polygonal models” by Cignoni, Ganovelli, Gobbetti, Marton, Ponchio, et al. …

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.

1. BOTSCH, M., AND KOBBELT, L. 2003. High-quality point-based rendering on modern GPUs. In Proc. Pacific Graphics, 335–343. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
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. Google ScholarDigital Library
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.Google Scholar
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.Google ScholarCross Ref
7. COHEN-OR, D., AND LEVANONI, Y. 1996. Temporal continuity of levels of detail in delaunay triangulated terrain. In IEEE Visualization ’96, IEEE. Google ScholarDigital Library
8. DACHSBACHER, C., VOGELSGANG, C., AND STAMMINGER, M. 2003. Sequential point trees. In Proc. SIGGRAPH, 657–662. Google ScholarDigital Library
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. Google ScholarDigital Library
10. EL-SANA, J., AND CHIANG, Y.-J. 2000. External memory view-dependent simplification. Computer Graphics Forum 19, 3(Aug.), 139–150.Google ScholarCross Ref
11. EL-SANA, J., AND VARSHNEY, A. 1999. Generalized view-dependent simplification. Computer Graphics Forum 18, 3, 83–94.Google ScholarCross Ref
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
16. HOPPE, H. 1998. Smooth view-dependent level-of-detail control and its aplications to terrain rendering. In IEEE Visualization ’98 Conf., 35–42. Google ScholarDigital Library
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. Google ScholarDigital Library
18. ISENBURG, M., LINDSTROM, P., GUMHOLD, S., AND J. SNOEYINK. 2003. Large mesh simplification using processing sequences. In Proc. IEEE Visualization. Google ScholarDigital Library
19. ISENBURG, M. 2001. Triangle strip compression. Computer Graphics Forum 20, 2, 91–101.Google ScholarCross Ref
20. LEVENBERG, J. 2002. Fast view-dependent level-of-detail rendering using cached geometry. In Proceedings IEEE Visualization ’02, IEEE, 259–266. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
23. LINDSTROM, P. 2003. Out-of-core construction and visualization of multiresolution surfaces. In ACM 2003 Symposium on Interactive 3D Graphics, 93–102, 239. Google ScholarDigital Library
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. Google ScholarDigital Library
25. MAUBACH, J. 1995. Local bisection refinement for n-simplicial grids generated by bisection. SIAM Journal of Scientific Computing 16, 210–227. Google ScholarDigital Library
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. Google ScholarDigital Library
27. PASCUCCI, V. 2002. Slow growing subdivision (SGS) in any dimension: Towards removing the curse of dimensionality. Computer Graphics Forum 21, 3, 451–460.Google ScholarCross Ref
28. POMERANZ, A. A. 2000. ROAM Using Surface Triangle Clusters (RUSTiC). Master’s thesis, University of California at Davis.Google Scholar
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.Google Scholar
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. Google ScholarDigital Library
31. SAMET, H. 1990. Applications of Spatial Data Structures. Addison Wesley, Reading, MA. Google ScholarDigital Library
32. SHAFFER, E., AND GARLAND, M. 2001. Efficient adaptive simplification of massive meshes. In Proc. IEEE Visualization 2001, IEEE Press, 127–134. Google ScholarDigital Library
33. WU, J., AND KOBBELT, L. 2003. A stream algorithm for the decimation of massive meshes. In Proc. Graphics Interface, 185–192.Google Scholar
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. Google ScholarDigital Library