TL;DR
This paper presents a publicly available implementation of the "Compressed Progressive Meshes" (CPM) algorithm for efficiently compressing and decompressing 3D triangle meshes. The authors introduce several improvements to the original CPM, focusing on flexible parameter choices for error metrics, geometric prediction, and quantization, leading to a robust and adaptable compression framework.
What Problem Does This Paper Address?
The increasing complexity and size of 3D models, driven by advancements in scanning technology and the rise of applications like VR and AR, create significant challenges for storage, transmission, and real-time rendering. Delivering these large models efficiently over networks, especially to devices with varying capabilities, requires effective compression techniques. Progressive compression addresses this by allowing meshes to be transmitted and reconstructed at multiple levels of detail (LoD), adapting to network conditions and device limitations. While progressive mesh compression methods exist, many are limited to specific mesh types (e.g., manifold meshes) or lack flexibility in their parameters. This paper aims to provide a practical, open-source implementation of a progressive mesh compression algorithm that is both efficient and highly configurable.
Methods
The core of this work is the implementation of the Compressed Progressive Meshes (CPM) algorithm, which operates by iteratively simplifying a 2-manifold triangle mesh through edge collapse operations. This simplification process is guided by a local error metric, and the information needed to reconstruct the mesh at finer levels of detail is encoded. Key aspects of their approach include:
- Preprocessing: Ensures the input mesh is 2-manifold and applies uniform quantization to vertex coordinates.
- Iterative Simplification (Edge Collapse): Batches of edge collapses are performed, guided by a chosen error metric. The algorithm prioritizes edges that introduce minimal error while respecting topological constraints to ensure the mesh remains valid and decodable.
- Information Encoding: For each simplification batch, information about the vertex splits (the inverse of edge collapses) is encoded. This includes:
- Connectivity: Encoded using bitmasks (vertex bitmask, one-ring bitmask) to indicate which vertices will be split and the configuration of their surrounding edges.
- Geometry: Encoded as residuals (prediction errors) between actual and predicted vertex positions.
- Geometric Predictors: Three predictors are offered: no-prediction, delta prediction, and butterfly prediction, allowing for trade-offs between compression ratio and geometric accuracy.
- Error Metrics: Three local error metrics are implemented: edge length, local absolute volume error, and a variant of the Quadric Error Metric (QEM). These metrics influence the simplification process and the resulting mesh quality at different LoDs.
- Base Mesh Encoding: The coarsest level of detail (the base mesh) is encoded using a state-of-the-art single-rate compression algorithm (Draco).
- Progressive Decoding: The decoder reconstructs the mesh progressively by applying the encoded vertex splits, starting from the base mesh and adding detail from each refinement chunk.
The authors emphasize the modularity of their implementation, allowing users to select different combinations of error metrics, position types (how the new vertex is placed after collapse), and geometric predictors.
Datasets
The authors used a dataset composed of eight 2-manifold triangle meshes: four regular and four irregular models. These models were chosen to represent smooth surfaces and to test the performance of the butterfly geometry prediction, particularly for meshes with varying degrees of regularity. The paper also references the "fandisk" model from a previous CPM implementation [15] for comparative analysis.
Key Insights and Ideas
- Parameter Flexibility is Key: The paper highlights that offering a choice of error metrics, geometric predictors, and position types significantly impacts compression performance and the quality of the reconstructed mesh. This allows users to tailor the compression to specific application needs.
- Trade-offs in Geometry Prediction: The butterfly prediction, while generally offering better compression (lower bpv), can sometimes introduce slightly more distortion compared to simpler methods like delta prediction, especially when the mesh is not perfectly regular. The choice depends on the desired balance between file size and visual fidelity.
- Local Error Metrics Influence Mesh Regularity: Different error metrics lead to different mesh characteristics at lower LoDs. Edge length tends to produce more uniform meshes but with higher geometric error, while QEM and local absolute volume error better preserve shape, albeit with less uniform triangle distribution.
- Connectivity Optimization Potential: The paper notes that connectivity information can be a significant portion of the compressed bitstream, and suggests that optimizations to the connectivity bitmask encoding could further improve compression ratios, especially for regular meshes.
Key Results
- Competitive Compression: The implemented CPM method achieves compression rates comparable to or better than existing state-of-the-art progressive mesh compression algorithms, particularly for geometry information.
- Parameter Impact: Experiments showed that the combination of the local absolute volume error metric, midpoint position, and butterfly prediction yielded the best rate-distortion performance for their chosen dataset and quantization levels (10, 12, and 16 bits).
- Bit Allocation: Header information is minimal (around 1.23 bpv). Connectivity typically consumes around 7.26 bpv, with potential for reduction in regular meshes. Geometry information varies significantly with quantization bits, ranging from ~6 bpv to ~24 bpv.
- Performance: Compression is more computationally intensive than decompression, with meshes under 165k vertices being necessary to keep compression times under 20 seconds on their test hardware. Decompression of the first ten LoDs is typically achieved in under 2 seconds.
Limitations and Future Work
- Tie-breaks in Spanning Tree Construction: The current preprocessing step for handling duplicate vertices can sometimes lead to visual artifacts, especially with low quantization bits. The authors suggest replacing this with a "remove root tie-breaks" step to limit vertex relocation and improve visual quality.
- Connectivity Bitmask Optimization: While some optimizations are mentioned, further exploration into connectivity bitmask encoding, potentially using different entropy coders for varying batch sizes, is suggested.
- Adaptive Quantization: The paper notes that at very low mesh resolutions, quantization error becomes less significant than mesh element reduction. Adaptive quantization could improve performance at low bit rates.
- Local Frenet Frame: While beneficial in some contexts, the expected gain from using a local Frenet frame for projecting residual vectors is smaller in their case compared to other work.
- Mesh Attributes: The paper outlines how other mesh attributes (like texture coordinates) could be compressed, but notes that texture seams require special handling.
- Polygonal and Non-Manifold Meshes: Extending the method to handle polygonal and non-manifold meshes would require additional symbols or techniques like vertex duplication.
Summary updated