Progressive lossless compression of arbitrary simplicial complexes
Authors:
- Pierre-Marie GandoinPGPierre-Marie Gandoin
- Olivier DevillersODOlivier Devillers
Open Access
- 1 July 2002
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 21 (3) , 372-379
Abstract
Efficient algorithms for compressing geometric data have been widely developed in the recent years, but they are mainly designed for closed polyhedral surfaces which are manifold or "nearly manifold". We propose here a progressive geometry compression scheme which can handle manifold models as well as "triangle soups" and 3D tetrahedral meshes. The method is lossless when the decompression is complete which is extremely important in some domains such as medical or finite element.While most existing methods enumerate the vertices of the mesh in an order depending on the connectivity, we use a kd-tree technique [Devillers and Gandoin 2000] which does not depend on the connectivity. Then we compute a compatible sequence of meshes which can be encoded using edge expansion [Hoppe et al. 1993] and vertex split [Popović and Hoppe 1997].The main contributions of this paper are: the idea of using the kd-tree encoding of the geometry to drive the construction of a sequence of meshes, an improved coding of the edge expansion and vertex split since the vertices to split are implicitly defined, a prediction scheme which reduces the code for simplices incident to the split vertex, and a new generalization of the edge expansion operation to tetrahedral meshes.Keywords
This publication has 8 references indexed in Scilit:
- Valence-Driven Connectivity Encoding for 3D MeshesComputer Graphics Forum, 2001
- Compressed progressive meshesIEEE Transactions on Visualization and Computer Graphics, 2000
- Efficient compression of non-manifold polygonal meshesComputational Geometry, 1999
- Wrap&Zip decompression of the connectivity of triangle meshes compressed with EdgebreakerComputational Geometry, 1999
- Edgebreaker: connectivity compression for triangle meshesIEEE Transactions on Visualization and Computer Graphics, 1999
- Geometric compression through topological surgeryACM Transactions on Graphics, 1998
- Multi-resolution 3D approximations for rendering complex scenes1993
- Arithmetic coding for data compressionCommunications of the ACM, 1987