TL;DR
This paper introduces GEncode, a novel geometry-driven mesh compression algorithm that can handle meshes of arbitrary topology and dimension. Unlike previous methods that rely on implicit assumptions about mesh regularity, GEncode explicitly incorporates prior knowledge about the mesh's geometry and topology, leading to competitive compression ratios and broader applicability, especially for scanned and remeshed models.
What Problem Does This Paper Address?
The field of computer graphics increasingly deals with massive and complex 3D meshes, necessitating efficient compression techniques. Existing mesh compression algorithms often struggle with the diversity of mesh types, relying on implicit assumptions about their structure (e.g., regular connectivity, simple topology). This limits their effectiveness for models generated by processes like scanning or reverse engineering, which can have arbitrary topology, higher dimensions, or singularities. The paper aims to bridge this gap by developing a compression scheme that is both general (handling arbitrary meshes) and efficient, by explicitly leveraging geometric and topological priors.
Methods
GEncode is a geometry-driven compression scheme, meaning it encodes the mesh's geometry separately from its connectivity. The core innovation lies in how it handles connectivity.
- Geometry Encoding: The paper synthesizes two existing geometry encoding techniques (from [GD02] and [BWK02]) that use space partition trees (similar to octrees) to encode vertex coordinates. This synthesis aims to combine the strengths of both methods for better compression, particularly on smaller models and 3D meshes.
- Connectivity Encoding (GEncode's Core): GEncode uses an "advancing front" approach, similar to greedy reconstruction algorithms. However, instead of solely relying on a geometric criterion to choose the next vertex (apex) to attach a new cell, GEncode uses a two-pronged strategy:
- Geometric Range: A geometric function (e.g., distance to the front cell's barycenter, or a mesh quality criterion like circumradius) is used to define a range
[Rmin, Rmax]of candidate apexes. This range is quantized, and the quantized range itself is encoded. - Apex Identifiers: Within this geometric range, candidate apexes are further ordered by a "geometric prior" (a function
Gthat predicts the probability of a vertex completing the front cell). The algorithm then encodes the identifier (position in the ordered list) of the correct apex. This prioritizes likely candidates, leading to lower entropy. - Topological Priors: GEncode can optionally incorporate topological information (e.g., manifoldness, boundary presence) to further improve compression ratios. For instance, it can avoid encoding certain parameters for simplicial manifolds without boundaries.
- Arbitrary Dimension and Topology: The framework is designed to handle meshes of arbitrary dimension and topology, including non-pure complexes, by recursively encoding sub-complexes.
Datasets
The paper evaluates GEncode on a variety of common 3D models, including:
- Surfaces: animal, art, cad, math, medical, sculpture, original, re-meshed.
- Volumes (Tetrahedral Meshes): terrain, mechanical, iron piece, sphere, etc. (as listed in Table 4).
These datasets are used to compare GEncode's performance against existing methods like Edgebreaker, Grow&Fold, and streaming compression. The paper does not introduce new benchmark datasets but uses established ones to demonstrate GEncode's generality and efficiency.
Key Insights and Ideas
- Explicit Priors are Key: The most significant insight is that explicitly encoding geometric and topological priors, rather than relying on implicit assumptions, is crucial for achieving general and efficient mesh compression. This allows GEncode to adapt to diverse mesh types.
- Geometry-Driven Connectivity: The paper demonstrates that a geometry-driven approach can effectively compress connectivity, especially when combined with intelligent candidate selection and ordering.
- Trade-off in Quantization: The paper highlights the critical trade-off between quantizing the geometric range (affecting range encoding cost) and the number of candidate apexes (affecting apex identifier encoding cost). Finding the right balance is essential for optimal compression.
- Generality Matters: GEncode's ability to handle arbitrary dimensions and topologies (including non-manifold cases) is a major advancement over many existing methods.
Key Results
- Competitive Compression Ratios: GEncode achieves compression ratios comparable to or better than state-of-the-art methods like Edgebreaker for surfaces and is highly competitive with Grow&Fold and streaming compression for volumes.
- Surface Performance: For surfaces, GEncode's compression ratios are competitive with Edgebreaker, even on non-manifold or non-orientable meshes where Edgebreaker struggles.
- Volume Performance: For tetrahedral meshes, GEncode shows significant gains, outperforming streaming compression by over 35% on average, albeit at a higher computational cost.
- Adaptability: The choice of geometric criterion (e.g., Delaunay constraint, distance) significantly impacts compression, demonstrating GEncode's flexibility in adapting to different mesh characteristics.
Limitations and Future Work
- Computational Cost: The paper acknowledges that the geometric range localization procedure can be slow, especially for general geometric ranges, leading to higher computational costs compared to streaming compression methods.
- Geometry Encoding: While GEncode's geometry encoding is a synthesis of existing methods, further improvements in this area are possible.
- Mixed Encoding: The authors suggest that future work could explore mixed geometry/connectivity encoding strategies, which might further enhance compression ratios.
- Non-Simplicial Meshes: While GEncode handles non-simplicial meshes, the paper notes that the current implementation might require modifications for certain degenerated cases to guarantee reconstruction.
- NP-Hardness: The recognition of manifoldness in higher dimensions is NP-hard, which is a limitation for fully automated topological prior utilization in those cases.
Summary updated