“Progressive simplicial complexes” by Popović and Hoppe

In this paper, we introduce the progressive simplicial complex (PSC) representation, a new format for storing and transmitting triangulated geometric models. Like the earlier progressive mesh (PM) representation, it captures a given model as a coarse base model together with a sequence of refinement transformations that progressively recover detail. The PSC representation makes use of a more general refinement transformation, allowing the given model to be an arbitrary triangulation (e.g. any dimension, non-orientable, non-manifold, non-regular), and the base model to always consist of a single vertex. Indeed, the sequence of refinement transformations encodes both the geometry and the topology of the model in a unified multiresolution framework. The PSC representation retains the advantages of PM’s. It defines a continuous sequence of approximating models for runtime level-of-detail control, allows smooth transitions between any pair of models in the sequence, supports progressive transmission, and offers a space-efficient representation. Moreover, by allowing changes to topology, the PSC sequence of approximations achieves better fidelity than the corresponding PM sequence. We develop an optimization algorithm for constructing PSC representations for graphics surface models, and demonstrate the framework on models that are both geometrically and topologically complex.

1. ANDUJAR, C., Ayala, D., Brunet, P., Joan-Arinyo, R., AND SOLE, J. Automatic generation of multiresolution boundary representations. Computer Graphics Forum (Proceedings of Eurographics ’96) 15, 3 (1996), 87-96.
2. Bajaj, C., and Schikore, D. Error-bounded reduction of triangle meshes with multivariate data. SPIE 2656 (1996), 34-45.
3. Bertolotto, M., De Floriani, L., Bruzzone, E., and Puppo, E. Multiresolution representation of volume data through hierarchical simplicial complexes. In Aspects of visual form processing (1994), C. Arcelli, L. Cordella, and G. Sanniti di Baja, Eds., World Scientific, pp. 73-82.
4. Bertolotto, M., De Floriani, L., and Marzano, P. Pyramidal simplicial complexes. In Solid Modeling ’95 (May 1995), pp. 153-162.
5. Brisson, E. Representation of d-dimensional geometric objects. PhD thesis, Dept. of Computer Science and Engineering, U. of Washington, 1990.
6. Clark, J. Hierarchical geometric models for visible surface algorithms. Communications of the ACM 19, 10 (October 1976), 547-554.
7. Deering, M. Geometry compression. Computer Graphics (SIG- GRAPH ’95 Proceedings) (1995), 13-20.
8. Funkhouser, T., and Sequin, C. Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments. Computer Graphics (SIGGRAPH ’93 Proceedings) (1993), 247-254.
9. Garland, M., and Heckbert, P. Surface simplification using quadric error metrics. Computer Graphics (SIGGRAPH ’97 Proceedings) (1997).
10. Gueziec, A. Surface simplification inside a tolerance volume. Research Report RC-20440, IBM, March 1996.
11. He, T., Hong, L., Varshney, A., and Wang, S. Controlled topology simplification. IEEE Transactions on Visualization and Computer Graphics 2, 2 (June 1996), 171-184.
12. Heckbert, P., and Garland, M. Survey of polygonal surface simplification algorithms. Tech. Rep. CMU-CS-95-194, Carnegie Mellon University, 1995.
13. Hoppe, H. Progressive meshes. Computer Graphics (SIGGRAPH ’96 Proceedings) (1996), 99-108.
14. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. Mesh optimization. Computer Graphics (SIGGRAPH ’93 Proceedings) (1993), 19-26.
15. Hudson, J. Piecewise Linear Topology. W.A. Benjamin, Inc, 1969.
16. Jungerman, M., and Ringel, G. Minimal triangulations on orientable surfaces. Acta Mathematica 145, 1-2 (1980), 121-154.
17. Lang, V., and Lienhardt, P. Geometric modeling with simplicial sets. In Pacific Graphics ’95 (August 1995), pp. 475-493.
18. Luebke, D. Hierarchical structures for dynamic polygonal simplification. TR 96-006, Department of Computer Science, University of North Carolina at Chapel Hill, 1996.
19. Paoluzzi, A., Bernardini, F., Cattani, C., and Ferrucci, V. Dimension-independent modeling with simplicial complexes. ACM Transactions on Graphics 12, 1 (January 1993), 56-102.
20. Ronfard, R., and Rossignac, J. Full-range approximation of triangulated polyhedra. Computer Graphics Forum (Proceedings of Eurographics ’96) 15, 3 (1996), 67-76.
21. Rossignac, J., and Borrel, P. Multi-resolution 3D approximations for rendering complex scenes. In Modeling in Computer Graphics, B. Falcidieno and T. L. Kunii, Eds. Springer-Verlag, 1993, pp. 455-465.
22. Schaufler, G., and St. urzlinger, W. Generating multiple levels of detail from polygonal geometry models. In Virtual Environments ’95 (Eurographics Workshop) (January 1995), M. G~bel, Ed., Springer Verlag, pp. 33-41.
23. Schmalstieg, D., and Schaufler, G. Smooth levels of detail. In Proc. of IEEE 1997 Virtual Reality Annual Intnl. Symp. (1997), pp. 12-19.
24. Schroeder, W., Zarge, J., and Lorensen, W. Decimation of triangle meshes. Computer Graphics (SIGGRAPH ’92 Proceedings) 26, 2 (1992), 65-70.
25. Spanier, E. H. Algebraic Topology. McGraw-Hill, New York, 1966.
26. Taubin, G., and Rossignac, J. Geometry compression through topological surgery. Research Report RC-20340, IBM, January 1996.
27. Turk, G. Re-tiling polygonal surfaces. Computer Graphics (SIG- GRAPH ’92 Proceedings) 26, 2 (1992), 55-64.
28. Wavefront Technologies, Inc. Wavefront File Formats, Version 4.0 RG-10-004, first ed. Santa Barbara, CA, 1993.
29. Weiler, K. The radial edge structure: a topological representation for non-manifold geometric boundary modeling. In Geometric modeling for CAD applications. Elsevier Science Publish., 1988.
30. Witten, I., Neal, R., and Cleary, J. Arithmetic coding for data compression. Communications of the ACM 30, 6 (June 1987), 520-540.