PolyCut
Open Access
- 1 November 2013
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 32 (6) , 1-12
Abstract
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 PolyCubes, 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.Keywords
Funding Information
- Networks of Centres of Excellence of Canada
- University of British Columbia
- Natural Sciences and Engineering Research Council of Canada
- Mitacs
This publication has 27 references indexed in Scilit:
- Quad‐Mesh Generation and Processing: A SurveyComputer Graphics Forum, 2013
- All‐Hex Mesh Generation via Volumetric PolyCube DeformationComputer Graphics Forum, 2011
- L
p
Centroidal Voronoi Tessellation and its applicationsACM Transactions on Graphics, 2010
- A divide-and-conquer approach for automatic polycube map constructionComputers & Graphics, 2009
- A survey on Mesh Segmentation TechniquesComputer Graphics Forum, 2008
- Mesh Parameterization Methods and Their ApplicationsFoundations and Trends in Computer Graphics and Vision, 2007
- Mean value coordinates for arbitrary planar polygonsACM Transactions on Graphics, 2006
- An experimental comparison of min-cut/max- flow algorithms for energy minimization in visionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- What energy functions can be minimized via graph cuts?IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Fast approximate energy minimization via graph cutsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001