TL;DR
Researchers have developed a robust, automatic algorithm that transforms complex 3D surface meshes into "polycubes"—blocky representations where every face aligns with a standard XYZ axis. By separating the process into distinct topological and geometric steps and using an iterative Poisson system, the method handles high-genus, open-boundary, and even non-orientable meshes faster and more accurately than previous state-of-the-art techniques.
What Problem Does This Paper Address?
In computer graphics, a polycube is a simplified version of a 3D model made entirely of axis-aligned blocks. Think of it as a "LEGO-fied" version of a smooth mesh. These shapes are incredibly useful for tasks like texture mapping, hexahedral remeshing (turning a surface into a grid of cubes), and volumetric parameterization.
However, creating polycubes is notoriously difficult. Early methods required tedious manual interaction. Recent automatic methods often struggled with "topological degeneracies" (glitches in the shape), were limited to closed meshes (no holes), or required massive computational power to solve non-linear optimization problems. The authors aim to provide a method that is simple to implement, fast, and robust enough to handle almost any mesh you throw at it.
Methods
The authors break the polycube construction process into three explicit components:
- Segmentation: Dividing the mesh into different "charts."
- Polycube Topology: Assigning each chart to one of the six primary axes ($\pm X, \pm Y, \pm Z$).
- Polycube Geometry: The core contribution of the paper.
The "Geometry" step uses a face normal rotation-based deformation. Instead of trying to solve a complex, non-linear energy minimization problem all at once, they use an iterative Poisson system.
Here’s the "aha" moment: they adapt a "stretching energy" formula from previous work but treat the rotations as known constants based on the target polycube axes. This turns a difficult problem into a series of simple linear equations ($Lx = b$). By recomputing the rotation matrices at each step and solving the linear system again, the mesh gradually "snaps" into a polycube shape. Because it's based on a Poisson system, the algorithm naturally preserves edges and area better than methods that only look at vertex normals.
Datasets
The authors evaluated their algorithm on hundreds of models of varying complexity. Specific sources mentioned include:
- Aim@Shape Repository: A standard collection of digital shapes.
- Stanford 3D Scanning Repository: Famous models like the Stanford Bunny and Dragon.
- [FBL16] Dataset: A specific dataset used in prior polycube research for direct comparison.
Key Insights and Ideas
- Explicit Separation: By treating topology and geometry as separate steps, the algorithm avoids the "local minima" traps that plague joint optimization methods.
- Face vs. Vertex Rotations: Unlike some previous methods that rotate vertex normals, this method rotates face normals. This is a critical distinction that allows the algorithm to process non-orientable surfaces (like the Costa surface) and meshes with open boundaries.
- Metric Preservation: While the deformation technically changes the mesh's metric, the authors observe that their Poisson-based approach keeps edge length changes remarkably small, leading to less distortion in the final polycube.
- Rapid Convergence: The iterative process is highly efficient. In many cases, the polycube shape is virtually finalized by the 5th iteration, even if the algorithm continues to run for 100+ iterations to fine-tune planarity.
Key Results
- Robustness: The method successfully processed models with high genus (lots of holes), open boundaries, and complex branching (e.g., a "wooden fish" or a "gargoyle").
- Speed: Because it only requires solving linear systems, it is significantly faster than non-linear optimization-based competitors.
- Quality: Quantitative comparisons (edge and area error diagrams) showed that this method preserves the original mesh's characteristics better than the previous state-of-the-art method by Fu et al. [FBL16].
- Versatility: It is one of the few polycube methods capable of handling non-orientable meshes, demonstrated by the successful deformation of the "Costa" surface.
Limitations and Future Work
The primary limitation acknowledged by the authors is that their deformation technique does not currently guarantee a bijection (a perfect one-to-one mapping) between the original mesh and the polycube. In some extreme cases, the mesh might self-intersect during deformation.
For future work, the authors plan to incorporate additional constraints into the geometry step to ensure a bijective map, which would make the tool even more reliable for downstream applications like hexahedral meshing.
Summary updated