“Mixed-integer quadrangulation” by Bommes, Zimmer and Kobbelt

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.

1. Alliez, P., Cohen-Steiner, D., Devillers, O., Levy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. ACM Trans. Graph. 22, 3, 485–493. Google ScholarDigital Library
2. Alliez, P., Ucelli, G., Gotsman, C., and Attene, M. 2005. Recent advances in remeshing of surfaces. Research report, [email protected] Network of Excellence.Google Scholar
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.Google ScholarCross Ref
4. Bommes, D., Vossemer, T., and Kobbelt, L. 2009. Quadrangular parameterization for reverse engineering. Lecture Notes in Computer Science, to appear.Google Scholar
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. Google ScholarDigital Library
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.Google Scholar
7. Cohen-Steiner, D., and Morvan, J.-M. 2003. Restricted delaunay triangulations and normal cycle. In SCG ’03: Proceedings of the nineteenth annual symposium on Computational geometry, 312–321. Google ScholarDigital Library
8. 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
9. Fisher, M., Schröder, P., Desbrun, M., and Hoppe, H. 2007. Design of tangent vector fields. ACM TOG 26, 3, 56. Google ScholarDigital Library
10. Floudas, C. A. 1995. Nonlinear and Mixed-Integer Optimization Fundamentals and Applications. Hardback.Google Scholar
11. Gorry, G., Shapiro, J., and Wolsey, L. 1970. Relaxation methods for pure and mixed integer programming problems. Cambridge, M.I.T., Cambridge.Google Scholar
12. Hertzmann, A., and Zorin, D. 2000. Illustrating smooth surfaces. In SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 517–526. Google ScholarDigital Library
13. Hildebrandt, K., Polthier, K., and Wardetzky, M. 2005. Smooth feature lines on surface meshes. In SGP ’05: Proceedings of the third Eurographics symposium on Geometry processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 85. Google ScholarDigital Library
14. 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
15. 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
16. Kälberer, F., Nieser, M., and Polthier, K. 2007. Quadcover – surface parameterization using branched coverings. Computer Graphics Forum 26, 3 (Sept.), 375–384.Google Scholar
17. Kharevych, L., Springborn, B., and Schröder, P. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25, 2, 412–438. Google ScholarDigital Library
18. Lai, Y.-K., Kobbelt, L., and Hu, S.-M. 2008. An incremental approach to feature aligned quad dominant remeshing. In SPM ’08: Proceedings of the 2008 ACM symposium on Solid and physical modeling, 137–145. Google ScholarDigital Library
19. Marinov, M., and Kobbelt, L. 2004. Direct anisotropic quaddominant remeshing. In PG ’04: Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, IEEE Computer Society, Washington, DC, USA, 207–216. Google ScholarDigital Library
20. 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
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.Google Scholar
22. 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
23. Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. In SIGGRAPH ’08: ACM SIGGRAPH 2008 papers, 1–11.Google Scholar
24. Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Proc. SGP, Eurographics Association, 201–210. Google ScholarDigital Library
25. Zhang, E., Mischaikow, K., and Turk, G. 2006. Vector field design on surfaces. ACM Trans. Graph. 25, 4, 1294–1326. Google ScholarDigital Library