“Progressive forest split compression” by Taubin, Guéziec, Horn and Lazarus

In this paper we introduce the Progressive Forest Split (PFS) representation, a new adaptive refinement scheme for storing and transmitting manifold triangular meshes in progressive and highly compressed form. As in the Progressive Mesh (PM) method of Hoppe, a triangular mesh is represented as a low resolution polygonal model followed by a sequence of refinement operations, each one specifying how to add triangles and vertices to the previous level of detail to obtain a new level. The PFS format shares with PM and other refinement schemes the ability to smoothly interpolate between consecutive levels of detail. However, it achieves much higher compression ratios than PM by using a more complex refinement operation which can, at the expense of reduced granularity, be encoded more efficiently. A forest split operation doubling the number n of triangles of a mesh requires a maximum of approximately 3:5n bits to represent the connectivity changes, as opposed to approximately (5 + log2 (n)) n bits in PM. We describe algorithms to efficiently encode and decode the PFS format. We also show how any surface simplification algorithm based on edge collapses can be modified to convert single resolution triangular meshes to the PFS format. The modifications are simple and only require two additional topological tests on each candidate edge collapse. We show results obtained by applying these modifications to the Variable Tolerance method of Guéziec.

1. MPEG4/SNHC verification model 5.0, July 1997. ISO/IEC JTC1/- SC29/WG 11 Document N 1820, Caspar Horne (ed.).
2. E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design, 10:350-355, 1978.
3. M. Deering. Geometric compression. In Siggraph’95 Conference Proceedings, pages 13-20, August 1995.
4. D. Doo and M. Sabin. Behaviour of recursive division surfaces near extraordinary points. Computer Aided Design, 10:356-360, 1978.
5. M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle. Multiresolution analysis of arbitrary meshes. In Siggraph’95 Conference Proceedings, pages 173-182, August 1995.
6. A. Gu6ziec. Surface simplification with variable tolerance. In Second Annual International Symposium on Medical Robotics and Computer Assisted Surgery, pages 132-139, Baltimore, MD, November 1995.
7. A. Gu6ziec, G. Taubin, E Lazarus, and W. Horn. Cutting and Stitching: Efficient Conversion of a Non-Manifold Polygonal Surface to a Manifold. Technical Report RC-20935, IBM Research, July 1997.
8. A. Gu6ziec, G. Taubin, E Lazarus, and W. Horn. Simplicial maps for progressive transmission of polygonal surfaces. In VRML 98. ACM, February 1998.
9. M. Hall and J. Warren. Adaptive polygonalization of implicitly defined surfaces. IEEE Computer Graphics and Applications, pages 33-42, November 1990.
10. B. Hamann. A data reduction scheme for triangulated surfaces. Computer Aided Geometric Design, 11 (2): 197-214,1994.
11. H. Hoppe. Progressive meshes. In Siggraph’96 Conference Proceedings, pages 99-108, August 1996.
12. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Mesh optimization. In Siggraph’93 Conference Proceedings, pages 19-25, July 1993.
13. C. Loop. Smooth subdivision surfaces based on triangles. Master’s thesis, Dept. of Mathematics, University of Utah, August 1987.
14. J. Popovi6 and H. Hoppe. Progressive simplicial complexes. In Siggraph’97 Conference Proceedings, pages 217-224, August 1997.
15. R. Ronfard and J. Rossignac. Simplifying a triangular mesh with multiple planar constraints. Technical report, IBM Research, 1994.
16. R. Ronfard and J. Rossignac. Triangulating multiply-connected polygons: A simple, yet efficient algorithm. Computer Graphics Forum, 13(3):C281-C292,1994. Proc. Eurographics’94, Oslo, Norway.
17. J. Rossignac and E Borrel. Geometric Modeling in Computer Graphics, chapter Multi-resolution 3D approximations for rendering complex scenes, pages 455-465. Springer Verlag, 1993.
18. G. Taubin. A signal processing approach to fair surface design. In Siggraph’95 Conference Proceedings, pages 351-358, August 1995.
19. G. Taubin, W.E Horn, E Lazarus, and J. Rossignac. Geometric Coding and VRML. Proceedings of the IEEE, July 1998. (to appear) Also IBM Research TR RC-20925, July 1997.
20. G. Taubin and J. Rossignac. Geometry Compression through Topological Surgery. ACM Transactions on Graphics, April 1998. (to appear).
21. D. Zorin, E Schr6der, and W. Sweldens. Interactive multiresolution mesh editing. In Siggraph’97 Conference Proceedings, pages 259- 268, August 1997.