“PolyCut: monotone graph-cuts for PolyCube base-complex construction” by Livesu, Vining, Sheffer, Gregson and Scateni – ACM SIGGRAPH HISTORY ARCHIVES

“PolyCut: monotone graph-cuts for PolyCube base-complex construction” by Livesu, Vining, Sheffer, Gregson and Scateni

  • 2013 SA Technical Papers_Livesu_PolyCut-monotone graph-cuts for PolyCube base-complex construction

Conference:


Type(s):


Title:

    PolyCut: monotone graph-cuts for PolyCube base-complex construction

Session/Category Title:   Geometry Ops

Presenter(s)/Author(s):


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.

References:


    1. Alice Project-team. Graphite. http://alice.loria.fr/software/graphite/.
    2. Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., and Zorin, D. 2013. Quad-mesh generation and processing: A survey. Computer Graphics Forum.
    3. Boykov, Y., and Kolmogorov, V. 2001. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 359–374.
    4. Boykov, Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence 23, 2001.
    5. Chang, C.-C., and Lin, C.-Y. 2010. Texture tiling on 3d models using automatic polycube-maps and wang tiles. J. Inf. Sci. Eng. 26, 1, 291–305.
    6. Eppstein, D., and Mumford, E. 2010. Steinitz theorems for orthogonal polyhedra. In Proc. Symposium on Computational Geometry, 429–438.
    7. Gregson, J., Sheffer, A., and Zhang, E. 2011. All-hex mesh generation via volumetric polycube deformation. Computer Graphics Forum (Proc. SGP) 30, 5.
    8. Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry images. ACM Trans. Graph. 21, 3 (July), 355–361.
    9. Han, S., Xia, J., and He, Y. 2010. Hexahedral shell mesh construction via volumetric polycube map. In Proc. Symposium on Solid and Physical Modeling, 127–136.
    10. He, Y., Wang, H., Fu, C.-W., and Qin, H. 2009. A divide-and-conquer approach for automatic polycube map construction. Computers and Graphics 33, 3, 369–380.
    11. Hoos, H., and Sttzle, T. 2004. Stochastic Local Search: Foundations & Applications. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
    12. Hormann, K., and Floater, M. S. 2006. Mean value coordinates for arbitrary planar polygons. ACM Transactions on Graphics 25, 4 (Oct.), 1424–1441.
    13. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. SIGGRAPH, 561–566.
    14. Kolmogorov, V., and Zabih, R. 2004. What energy functions can be minimized via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 65–81.
    15. Lévy, B., and Liu, Y. 2010. Lp centroidal voronoi tesselation and its applications. ACM Transactions on Graphics (Proc. SIGGRAPH).
    16. Li, B., and Qin, H. 2012. Component-aware tensor-product trivariate splines of arbitrary topology. Computers & Graphics.
    17. Li, B., Li, X., Wang, K., and Qin, H. 2010. Generalized polycube trivariate splines. In Proc. Shape Modeling International, 261–265.
    18. Li, X., Xu, H., Wan, S., Yin, Z., and Yu, W. 2010. Feature-aligned harmonic volumetric mapping using mfs. Computers & Graphics 34, 3, 242–251.
    19. Li, B., Li, X., Wang, K., and Qin, H. 2012. Surface mesh to volumetric spline conversion with generalized polycubes. IEEE Transactions on Visualization and Computer Graphics 99.
    20. Lin, J., Jin, X., Fan, Z., and Wang, C. C. L. 2008. Automatic polycube-maps. In Proc. Advances in geometric modeling and processing, 3–16.
    21. Praun, E., and Hoppe, H. 2003. Spherical parametrization and remeshing. ACM Trans. Graph. 22, 3 (July), 340–349.
    22. Shamir, A. 2008. A survey on mesh segmentation techniques. Comput. Graph. Forum 27, 1539–1556.
    23. Sheffer, A., Praun, E., and Rose, K. 2006. Mesh parameterization methods and their applications. Foundations and Trends in Computer Graphics and Vision 2, 2, 105–171.
    24. Tarini, M., Hormann, K., Cignoni, P., and Montani, C. 2004. PolyCube-Maps. ACM Transactions on Graphics 23, 3 (Aug.), 853–860. Proc. of ACM SIGGRAPH 2004.
    25. Wan, S., Yin, Z., Zhang, K., Zhang, H., and Li, X. 2011. A topology-preserving optimization algorithm for polycube mapping. Computers & Graphics 35, 3, 639–649.
    26. Wang, H., He, Y., Li, X., Gu, X., and Qin, H. 2007. Polycube splines. In Proc. Symposium on Solid and physical modeling, 241–251.
    27. Wang, H., Jin, M., He, Y., Gu, X., and Qin, H. 2008. User-controllable polycube map for manifold spline construction. In Proc. Symposium on Solid and physical modeling, 397–404.
    28. Xia, J., He, Y., Yin, X., Han, S., and Gu, X. 2010. Direct-product volumetric parameterization of handlebodies via harmonic fields. In Proc. Shape Modeling International, IEEE, 3–12.
    29. Xia, J., Garcia, I., He, Y., Xin, S.-Q., and Patow, G. 2011. Editable polycube map for gpu-based subdivision surfaces. In Proc. Symposium on Interactive 3D Graphics and Games, 151–158.
    30. Xu, Y., Chen, R., Gotsman, C., and Liu, L. 2011. Embedding a triangular graph within a given boundary. Computer Aided Geometric Design 28, 6, 349–356.
    31. Yao, C., and Lee, T. 2008. Adaptive geometry image. IEEE Transactions on Visualization and Computer Graphics 14, 4, 948–960.

ACM Digital Library Publication:


Overview Page:


Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org