“Integer-grid maps for reliable quad meshing” by Bommes, Campen, Ebke, Alliez and Kobbelt

  • ©David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt



Session Title:

    Quads & Meshing


    Integer-grid maps for reliable quad meshing




    Quadrilateral remeshing approaches based on global parametrization enable many desirable mesh properties. Two of the most important ones are (1) high regularity due to explicit control over irregular vertices and (2) smooth distribution of distortion achieved by convex variational formulations. Apart from these strengths, state-of-the-art techniques suffer from limited reliability on real-world input data, i.e. the determined map might have degeneracies like (local) non-injectivities and consequently often cannot be used directly to generate a quadrilateral mesh. In this paper we propose a novel convex Mixed-Integer Quadratic Programming (MIQP) formulation which ensures by construction that the resulting map is within the class of so called Integer-Grid Maps that are guaranteed to imply a quad mesh. In order to overcome the NP-hardness of MIQP and to be able to remesh typical input geometries in acceptable time we propose two additional problem specific optimizations: a complexity reduction algorithm and singularity separating conditions. While the former decouples the dimension of the MIQP search space from the input complexity of the triangle mesh and thus is able to dramatically speed up the computation without inducing inaccuracies, the latter improves the continuous relaxation, which is crucial for the success of modern MIQP optimizers. Our experiments show that the reliability of the resulting algorithm does not only annihilate the main drawback of parametrization based quad-remeshing but moreover enables the global search for high-quality coarse quad layouts – a difficult task solely tackled by greedy methodologies before.


    1. Bommes, D., Zimmer, H., and Kobbelt, L. 2009. Mixed-integer quadrangulation. In SIGGRAPH ’09: ACM SIGGRAPH 2009 papers, ACM, New York, NY, USA, 1–10. Google ScholarDigital Library
    2. Bommes, D., Vossemer, T., and Kobbelt, L. 2010. Quadrangular parameterization for reverse engineering. In Proc. on Mathematical Methods for Curves and Surfaces, Springer-Verlag, Berlin, Heidelberg, MMCS’08, 55–69. Google ScholarDigital Library
    3. Bommes, D., Lempfer, T., and Kobbelt, L. 2011. Global structure optimization of quadrilateral meshes. Comput. Graph. Forum 30, 2, 375–384.Google ScholarCross Ref
    4. Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., and Zorin, D. 2012. State of the art in quad meshing. In Eurographics STARS.Google Scholar
    5. Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., and Lévy, B. 2010. Polygon Mesh Processing. AK Peters.Google Scholar
    6. Bouaziz, S., Deuss, M., Schwartzburg, Y., Weise, T., and Pauly, M. 2012. Shape-up: Shaping discrete geometry with projections. Comp. Graph. Forum 31, 5 (Aug.), 1657–1667. Google ScholarDigital Library
    7. Campen, M., Bommes, D., and Kobbelt, L. 2012. Dual loops meshing: Quality quad layouts on manifolds. ACM Trans. Graph. 31, 4. Google ScholarDigital Library
    8. Catmull, E., and Clark, J. 1998. Seminal graphics. ACM, New York, NY, USA, ch. Recursively generated B-spline surfaces on arbitrary topological meshes, 183–188. Google ScholarDigital Library
    9. Daniels, J., Silva, C. T., Shepherd, J., and Cohen, E. 2008. Quadrilateral mesh simplification. In SIGGRAPH Asia ’08: ACM SIGGRAPH Asia 2008 papers, ACM, New York, NY, USA, 1–9. Google ScholarDigital Library
    10. Daniels, II, J., Silva, C. T., and Cohen, E. 2009. Localized quadrilateral coarsening. In SGP ’09: Proceedings of the Symposium on Geometry Processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 1437–1444. Google ScholarDigital Library
    11. Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., and Hart, J. C. 2006. Spectral surface quadrangulation. In SIGGRAPH ’06: ACM SIGGRAPH 2006 Papers, 1057–1066. Google ScholarDigital Library
    12. Eckstein, I., Surazhsky, V., and Gotsman, C. 2001. Texture mapping with hard constraints. Comput. Graph. Forum 20, 3.Google ScholarCross Ref
    13. Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In Advances in Multiresolution for Geometric Modelling, N. A. Dodgson, M. S. Floater, and M. A. Sabin, Eds., Mathematics and Visualization. Springer, Berlin, Heidelberg, 157–186.Google Scholar
    14. Gu, Z., Rothberg, E., and Bixby, R., 2011. Gurobi optimizer 4.5: http://www.gurobi.com.Google Scholar
    15. Hormann, K., Lévy, B., and Sheffer, A. 2007. Mesh parameterization: theory and practice. In SIGGRAPH ’07: ACM SIGGRAPH 2007 courses, 1. Google ScholarDigital Library
    16. Huang, J., Zhang, M., Ma, J., Liu, X., Kobbelt, L., and Bao, H. 2008. Spectral quadrangulation with orientation and alignment control. ACM Trans. Graph. 27, 5, 1–9. Google ScholarDigital Library
    17. IBM, 2012. Ilog cplex optimizer 12: http://www.ibm.com.Google Scholar
    18. Kälberer, F., Nieser, M., and Polthier, K. 2007. Quad-cover – surface parameterization using branched coverings. Computer Graphics Forum 26, 3 (Sept.), 375–384.Google ScholarCross Ref
    19. Khodakovsky, A., Litke, N., and Schröder, P. 2003. Globally smooth parameterizations with low distortion. In ACM SIGGRAPH 2003 Papers, ACM, New York, NY, USA, SIGGRAPH ’03, 350–357. Google ScholarDigital Library
    20. Kimmel, R., and Sethian, J. A. 1998. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci. USA, 8431–8435.Google Scholar
    21. Kovacs, D., Myles, A., and Zorin, D. 2010. Anisotropic quadrangulation. In Proceedings of the 14th ACM Symposium on Solid and Physical Modeling, ACM, New York, NY, USA, SPM ’10, 137–146. Google ScholarDigital Library
    22. Li, E., Lévy, B., Zhang, X., Che, W., Dong, W., and Paul, J.-C. 2011. Meshless quadrangulation by global parametrization. Computer and Graphics. Google ScholarDigital Library
    23. Li, Y., Liu, Y., Xu, W., Wang, W., and Guo, B. 2012. All-hex meshing using singularity-restricted field. ACM Trans. Graph. 31, 6 (Nov.), 177:1–177:11. Google ScholarDigital Library
    24. Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. 31, 4 (July), 108:1–108:13. Google ScholarDigital Library
    25. Micciancio, D. 2006. The hardness of the closest vector problem with preprocessing. IEEE Trans. Inf. Theor. 47, 3 (Sept.), 1212–1215. Google ScholarDigital Library
    26. Möbius, J., and Kobbelt, L. 2012. Openflipper: An open source geometry processing and rendering framework. In Curves and Surfaces, vol. 6920 of Lecture Notes in Computer Science. Springer Berlin/Heidelberg, 488–500. Google ScholarDigital Library
    27. Murdoch, P., Benzley, S., Blacker, T., and Mitchell, S. 1997. The spatial twist continuum: A connectivity based method for representing all-hexahedral finite element meshes. Finite Element in Analysis and Design 28, 2 (December), 137–149. Google ScholarDigital Library
    28. Nieser, M., Reitebuch, U., and Polthier, K. 2011. Cubecover- parameterization of 3d volumes. Comput. Graph. Forum 30, 5, 1397–1406.Google ScholarCross Ref
    29. Novotni, M., and Klein, R. 2002. Computing geodesic distances on triangular meshes. In The 10-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision’2002 (WSCG’2002).Google Scholar
    30. Owen, S. J., Staten, M. L., Canann, S. A., and Saigal, S. 1999. Q-morph: an indirect approach to advancing front quad meshing. International Journal for Numerical Methods in Engineering 44, 9, 1317–1340.Google ScholarCross Ref
    31. Pardalos, P., and Resende, M. 2002. Handbook of applied optimization. Oxford University Press, Incorporated.Google Scholar
    32. Pietroni, N., Tarini, M., and Cignoni, P. 2010. Almost isometric mesh parameterization through abstract domains. IEEE Transaction on Visualization and Computer Graphics 16, 4 (July/August), 621–635. Google ScholarDigital Library
    33. Pietroni, N., Tarini, M., Sorkine, O., and Zorin, D. 2011. Global parametrization of range image sets. ACM Transactions on Graphics, Proceedings of SIGGRAPH Asia 2011 30, 6. Google ScholarDigital Library
    34. Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic global parameterization. ACM Trans. Graph. 25, 4, 1460–1485. Google ScholarDigital Library
    35. Ray, N., Vallet, B., Li, W. C., and Lévy, B. 2008. N-symmetry direction field design. ACM Trans. Graph. 27, 2, 1–13. Google ScholarDigital Library
    36. Sheffer, A., Praun, E., and Rose, K. 2006. Mesh parameterization methods and their applications. Found. Trends. Comput. Graph. Vis. 2 (January), 105–171. Google ScholarDigital Library
    37. Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. In SIGGRAPH ’08: ACM SIGGRAPH 2008 papers, 1–11. Google ScholarDigital Library
    38. Tarini, M., Pietroni, N., Cignoni, P., Panozzo, D., and Puppo, E. 2010. Practical quad mesh simplification. Computer Graphics Forum (Special Issue of Eurographics 2010 Conference) 29, 2, 407–418.Google Scholar
    39. Tarini, M., Puppo, E., Panozzo, D., Pietroni, N., and Cignoni, P. 2011. Simple quad domains for field aligned mesh parametrization. ACM Transactions on Graphics, Proceedings of SIGGRAPH Asia 2011 30, 6. Google ScholarDigital Library
    40. Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Proc. of SGP, EG Association, Aire-la-Ville, Switzerland, SGP ’06, 201–210. Google ScholarDigital Library
    41. Wächter, A., and Biegler, L. T. 2006. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106 (May), 25–57. Google ScholarDigital Library
    42. Weber, O., Myles, A., and Zorin, D. 2012. Computing extremal quasiconformal maps. Comp. Graph. Forum 31, 5 (Aug.), 1679–1689. Google ScholarDigital Library
    43. Yu, H., Lee, T.-Y., Yeh, I.-C., Yang, X., Li, W., and Zhang, J. J. 2012. An rbf-based reparameterization method for constrained texture mapping. IEEE Transactions on Visualization and Computer Graphics 18, 7 (July), 1115–1124. Google ScholarDigital Library
    44. Zhang, M., Huang, J., Liu, X., and Bao, H. 2010. A wave-based anisotropic quadrangulation method. ACM Trans. Graph. 29 (July), 118:1–118:8. Google ScholarDigital Library

ACM Digital Library Publication: