TL;DR
MATTopo is a new framework for computing 3D Medial Axis Transforms (MAT) that guarantees the resulting "skeleton" is topologically identical to the original shape. By combining volumetric Restricted Power Diagrams (RPD) with a novel GPU-based "fractional Euler characteristic" check, it produces geometrically accurate, feature-preserving medial meshes using significantly fewer medial spheres than previous state-of-the-art methods.
What Problem Does This Paper Address?
The Medial Axis Transform (MAT) is a fundamental tool in geometry processing, acting as a "skeleton" that captures a shape's topology and geometric protrusions. However, computing an accurate 3D MAT is notoriously difficult.
Existing approximation methods usually fall into one of two traps:
- Topological Failure: Methods like MATFP can produce "broken" skeletons where parts of the mesh disconnect or holes appear that weren't in the original shape (losing "homotopy equivalence").
- Geometric Smoothing: Voxel-based or point-cloud methods often struggle to capture sharp features (like the crisp edges of a CAD model), resulting in rounded, inaccurate reconstructions.
The authors aim to bridge this gap, creating a method that is both topologically robust and capable of preserving the sharp "external features" of CAD models and the complex "internal features" (seams and junctions) of organic shapes.
Methods
The core of MATTopo is the Volumetric Restricted Power Diagram (RPD). While previous methods often looked only at the surface, MATTopo discretizes the entire 3D volume into sub-regions (cells) based on a set of medial spheres.
Key technical innovations include:
- Local Topological Checking: Based on the Nerve Theorem, the authors prove that if every individual element of the RPD (cells, faces, edges) is "contractible" (basically, a single piece with no holes), then the resulting medial mesh is guaranteed to be topologically equivalent to the input shape.
- Fractional Euler Characteristic: To make this check efficient on a GPU, the authors developed a way to compute the Euler characteristic ($X$) "on the fly" during the clipping process. Instead of building a complex global data structure, they assign fractional values to vertices, edges, and faces, allowing for localized, parallelized topological assessment.
- Adaptive Refinement: The algorithm starts with a very small number of spheres (e.g., 50) and iteratively adds new ones only where topological inconsistencies or geometric errors are detected. This "surgical" approach keeps the final mesh simple and efficient.
Datasets
The authors evaluated MATTopo using:
- The ABC Dataset: A large-scale dataset of CAD models. They specifically tested on the first 100 models in the
10k/testfolder. - Organic Models: 14 complex organic shapes frequently used in graphics research, such as the "Fertility," "Happy Buddha," and "Rozy" models.
- Comparison Baselines: They compared their results against MATFP (feature-preserving), Power Crust (PC), Scaled Axis Transform (SAT), and Voxel Cores (VC).
Key Insights and Ideas
- Topology is Local: The most powerful insight is that global topological correctness can be enforced through local checks. By ensuring each "power cell" in the RPD is well-behaved, the entire skeleton falls into place.
- Efficiency through Sparsity: Unlike previous methods that favor dense initial samplings, MATTopo shows that starting sparse and adding spheres adaptively leads to a much cleaner result. It often uses 10 times fewer spheres than MATFP while achieving comparable or better reconstruction accuracy.
- The Power of Volumetric RPD: Moving from surface-based RPD to volumetric RPD is computationally more expensive, but it provides the necessary "internal" information to guarantee that the skeleton doesn't just look right on the outside but is structurally sound on the inside.
Key Results
- Topological Accuracy: MATTopo consistently matched the "Ground Truth" Euler characteristic ($GT X$) across all test models, whereas MATFP and point-cloud methods frequently produced incorrect values (e.g., an Euler characteristic of 557 for a model where it should be -3).
- Complexity: For the "Fertility" model, MATTopo achieved a high-quality reconstruction with only 5k spheres, compared to 14k-36k required by other methods.
- Geometric Fidelity: The reconstruction error (Hausdorff distance) was significantly lower than voxel-based or point-cloud methods. For example, on the "Rozy" model, MATTopo achieved an error of 0.45%, while the next best non-feature-preserving method was at 1.89%.
Limitations and Future Work
- Computation Time: Because the method performs volumetric clipping (cutting 3D tetrahedra by half-spaces), it is slower than surface-only methods. Processing a single model currently takes several minutes.
- Parallelization: While the RPD computation is on the GPU, the feature preservation and sphere-generation stages are not yet fully parallelized.
- Extreme Complexity: The current GPU implementation can struggle with extremely large input meshes (e.g., over 5.5 million tetrahedra), which the authors aim to address in future iterations through better memory management and parallelization strategies.
Summary updated