Mixed-integer quadrangulation

ABSTRACT

We present a novel method for quadrangulating a given triangle mesh. After constructing an as smooth as possible symmetric cross field satisfying a sparse set of directional constraints (to capture the geometric structure of the surface), the mesh is cut open in order to enable a low distortion unfolding. Then a seamless globally smooth parametrization is computed whose iso-parameter lines follow the cross field directions. In contrast to previous methods, sparsely distributed directional constraints are sufficient to automatically determine the appropriate number, type and position of singularities in the quadrangulation. Both steps of the algorithm (cross field and parametrization) can be formulated as a mixed-integer problem which we solve very efficiently by an adaptive greedy solver. We show several complex examples where high quality quad meshes are generated in a fully automatic manner.

REFERENCES

• 1: Pierre Alliez , David Cohen-Steiner , Olivier Devillers , Bruno Lévy , Mathieu Desbrun, Anisotropic polygonal remeshing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 2: Alliez, P., Ucelli, G., Gotsman, C., and Attene, M. 2005. Recent advances in remeshing of surfaces. Research report, AIM@SHAPE Network of Excellence.
• 3: Ben-Chen, Mirela, Gotsman, Craig, Bunin, and Guy. 2008. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum 27, 2 (April), 449--458.
• 4: Bommes, D., Vossemer, T., and Kobbelt, L. 2009. Quadrangular parameterization for reverse engineering. Lecture Notes in Computer Science, to appear.
• 5: Botsch, M., Bommes, D., and Kobbelt, L. 2005. Efficient linear system solvers for mesh processing. In IMA Conference on the Mathematics of Surfaces, Springer, R. R. Martin, H. E. Bez, and M. A. Sabin, Eds., vol. 3604 of Lecture Notes in Computer Science, 62--83.
• 6: Chen, Y., Davis, T. A., Hager, W. W., and Rajamanickam, S. 2006. Algorithm 8xx: Cholmod, supernodal sparse cholesky factorization and update/downdate. Technical Report TR-2006-005, University of Florida.
• 7: David Cohen-Steiner , Jean-Marie Morvan, Restricted delaunay triangulations and normal cycle, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777839]
• 8: Shen Dong , Peer-Timo Bremer , Michael Garland , Valerio Pascucci , John C. Hart, Spectral surface quadrangulation, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 9: Matthew Fisher , Peter Schröder , Mathieu Desbrun , Hugues Hoppe, Design of tangent vector fields, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 10: Floudas, C. A. 1995. Nonlinear and Mixed-Integer Optimization Fundamentals and Applications. Hardback.
• 11: Gorry, G., Shapiro, J., and Wolsey, L. 1970. Relaxation methods for pure and mixed integer programming problems. Cambridge, M.I.T., Cambridge.
• 12: Aaron Hertzmann , Denis Zorin, Illustrating smooth surfaces, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.517-526, July 2000 [doi>10.1145/344779.345074]
• 13: Klaus Hildebrandt , Konrad Polthier , Max Wardetzky, Smooth feature lines on surface meshes, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
• 14: Kai Hormann , Konrad Polthier , Alia Sheffer, Mesh parameterization: theory and practice, ACM SIGGRAPH ASIA 2008 courses, p.1-87, December 10-13, 2008, Singapore [doi>10.1145/1508044.1508091]
• 15: Jin Huang , Muyang Zhang , Jin Ma , Xinguo Liu , Leif Kobbelt , Hujun Bao, Spectral quadrangulation with orientation and alignment control, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
• 16: Kälberer, F., Nieser, M., and Polthier, K. 2007. Quadcover - surface parameterization using branched coverings. Computer Graphics Forum 26, 3 (Sept.), 375--384.
• 17: Liliya Kharevych , Boris Springborn , Peter Schröder, Discrete conformal mappings via circle patterns, ACM Transactions on Graphics (TOG), v.25 n.2, p.412-438, April 2006 [doi>10.1145/1138450.1138461]
• 18: Yu-Kun Lai , Leif Kobbelt , Shi-Min Hu, An incremental approach to feature aligned quad dominant remeshing, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York [doi>10.1145/1364901.1364921]
• 19: Martin Marinov , Leif Kobbelt, Direct Anisotropic Quad-Dominant Remeshing, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.207-216, October 06-08, 2004
• 20: Nicolas Ray , Wan Chiu Li , Bruno Lévy , Alla Sheffer , Pierre Alliez, Periodic global parameterization, ACM Transactions on Graphics (TOG), v.25 n.4, p.1460-1485, October 2006 [doi>10.1145/1183287.1183297]
• 21: Ray, N., Vallet, B., Alonso, L., and Lévy, B. 2008. Geometry aware direction field design. Tech. rep., INRIA - ALICE Project Team. Accepted pending revisions.
• 22: Nicolas Ray , Bruno Vallet , Wan Chiu Li , Bruno Lévy, N-symmetry direction field design, ACM Transactions on Graphics (TOG), v.27 n.2, p.1-13, April 2008 [doi>10.1145/1356682.1356683]
• 23: Boris Springborn , Peter Schröder , Ulrich Pinkall, Conformal equivalence of triangle meshes, ACM SIGGRAPH ASIA 2008 courses, p.1-11, December 10-13, 2008, Singapore [doi>10.1145/1508044.1508062]
• 24: Y. Tong , P. Alliez , D. Cohen-Steiner , M. Desbrun, Designing quadrangulations with discrete harmonic forms, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 25: Eugene Zhang , Konstantin Mischaikow , Greg Turk, Vector field design on surfaces, ACM Transactions on Graphics (TOG), v.25 n.4, p.1294-1326, October 2006 [doi>10.1145/1183287.1183290]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Keywords:
direction field, mixed-integer, parametrization, quadrangulation, remeshing, singularities