David Bommes
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.
Supplemental Material
Available for Download
This zip-package contains auxillary material for the article
- Alliez, P., Cohen-Steiner, D., Devillers, O., Levy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. ACM Trans. Graph. 22, 3, 485--493. Google Scholar
Digital Library
- Alliez, P., Ucelli, G., Gotsman, C., and Attene, M. 2005. Recent advances in remeshing of surfaces. Research report, AIM@SHAPE Network of Excellence.Google Scholar
- 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
- Bommes, D., Vossemer, T., and Kobbelt, L. 2009. Quadrangular parameterization for reverse engineering. Lecture Notes in Computer Science, to appear.Google Scholar
- 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
- 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
- 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
- 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
- Fisher, M., Schröder, P., Desbrun, M., and Hoppe, H. 2007. Design of tangent vector fields. ACM TOG 26, 3, 56. Google ScholarDigital Library
- Floudas, C. A. 1995. Nonlinear and Mixed-Integer Optimization Fundamentals and Applications. Hardback.Google Scholar
- Gorry, G., Shapiro, J., and Wolsey, L. 1970. Relaxation methods for pure and mixed integer programming problems. Cambridge, M.I.T., Cambridge.Google Scholar
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Zhang, E., Mischaikow, K., and Turk, G. 2006. Vector field design on surfaces. ACM Trans. Graph. 25, 4, 1294--1326. Google ScholarDigital Library
Index Terms
- Mixed-integer quadrangulation
Recommendations
Instant field-aligned meshes
We present a novel approach to remesh a surface into an isotropic triangular or quad-dominant mesh using a unified local smoothing operator that optimizes both the edge orientations and vertex positions in the output mesh. Our algorithm produces meshes ...
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 ...
Mixed-integer quadrangulation
SIGGRAPH '09: ACM SIGGRAPH 2009 papersWe 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 ...
Comments