PolyCut: Monotone Graph-Cuts for PolyCube Base-Complex Construction

ACM Transactions on Graphics, Volume 32, Issue 6 (SIGGRAPH ASIA 2013 Papers)


PolyCubes, or orthogonal polyhedra, are useful as parameterization base-complexes for various operations in computer graphics. However, computing quality PolyCube base-complexes for general shapes, providing a good trade-off between mapping distortion and singularity counts, remains a challenge. Our work improves on the state-of-the-art in PolyCube computation by adopting a graph- cut inspired approach. We observe that, given an arbitrary input mesh, the computation of a suitable PolyCube base-complex can be formulated as associating, or labeling, each input mesh triangle with one of six signed principal axis directions. Most of the criteria for a desirable PolyCube labeling can be satisfied using a multi-label graph-cut optimization with suitable local unary and pairwise terms. However, the highly constrained nature of Poly-Cubes, imposed by the need to align each chart with one of the principal axes, enforces additional global constraints that the labeling must satisfy. To enforce these constraints, we develop a constrained discrete optimization technique, PolyCut, which embeds a graph-cut multi-label optimization within a hill-climbing local search framework that looks for solutions that minimize the cut energy while satisfying the global constraints. We further optimize our generated PolyCube base-complexes through a combination of distortion-minimizing deformation, followed by a labeling update and a final PolyCube parameterization step. Our PolyCut formulation captures the desired properties of a PolyCube base-complex, balancing parameterization distortion against singularity count, and produces demonstrably better PolyCube base-complexes then previous work.

Updates on ongoing advances reported here.





Siggraph Presentation (~60MB)
Siggraph Fast Forward (~3MB)
Results (~190MB)
Hex-Meshes (~17MB)




Hex Meshing



author    = {Livesu, Marco and Vining, Nicholas and Sheffer, Alla and Gregson, James and Scateni, Riccardo},
title     = {PolyCut: Monotone Graph-Cuts for PolyCube Base-Complex Construction},
journal   = {Transactions on Graphics (Proc. SIGGRAPH ASIA 2013)},
year      = {2013},
volume    = {32},
number    = {6},
doi       = {10.1145/2508363.2508388},
publisher = {ACM}}