“Dual loops meshing: quality quad layouts on manifolds” by Campen, Bommes and Kobbelt

We present a theoretical framework and practical method for the automatic construction of simple, all-quadrilateral patch layouts on manifold surfaces. The resulting layouts are coarse, surface-embedded cell complexes well adapted to the geometric structure, hence they are ideally suited as domains and base complexes for surface parameterization, spline fitting, or subdivision surfaces and can be used to generate quad meshes with a high-level patch structure that are advantageous in many application scenarios. Our approach is based on the careful construction of the layout graph’s combinatorial dual. In contrast to the primal this dual perspective provides direct control over the globally interdependent structural constraints inherent to quad layouts. The dual layout is built from curvature-guided, crossing loops on the surface. A novel method to construct these efficiently in a geometry- and structure-aware manner constitutes the core of our approach.

1. Boier-Martin, I. M., Rushmeier, H. E., and Jin, J. 2004. Parameterization of triangle meshes over quadrilateral domains. In Proc. SGP ’04, 197–208. Google ScholarDigital Library
2. Bommes, D., Vossemer, T., and Kobbelt, L. 2008. Quadrangular parameterization for reverse engineering. Mathematical Methods for Curves and Surfaces, 55–69. Google ScholarDigital Library
3. Bommes, D., Zimmer, H., and Kobbelt, L. 2009. Mixed-integer quadrangulation. In Proc. SIGGRAPH 2009, 1–10. Google ScholarDigital Library
4. Bommes, D., Lempfer, T., and Kobbelt, L. 2011. Global structure optimization of quadrilateral meshes. Computer Graphics Forum 30, 2, 375–384.Google ScholarCross Ref
5. Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. In Proc. SIGGRAPH 2004, 905–914. Google ScholarDigital Library
6. Daniels, J., Silva, C. T., Shepherd, J., and Cohen, E. 2008. Quadrilateral mesh simplification. ACM Trans. Graph. 27, 5, 148. Google ScholarDigital Library
7. Daniels, J., Silva, C. T., and Cohen, E. 2009. Semi-regular quadrilateral-only remeshing from simplified base domains. Comput. Graph. Forum 28, 5, 1427–1435. Google ScholarDigital Library
8. Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., and Hart, J. C. 2006. Spectral surface quadrangulation. In Proc. SIGGRAPH 2006, 1057–1066. Google ScholarDigital Library
9. Eck, M., and Hoppe, H. 1996. Automatic reconstruction of b-spline surfaces of arbitrary topological type. In Proc. SIGGRAPH 96, 325–334. Google ScholarDigital Library
10. Eppstein, D., Goodrich, M. T., Kim, E., and Tamstorf, R. 2008. Motorcycle Graphs: Canonical Quad Mesh Partitioning. Computer Graphics Forum 27, 5, 1477–1486. Google ScholarDigital Library
11. Erickson, J., and Whittlesey, K. 2005. Greedy optimal homotopy and homology generators. In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038–1046. Google ScholarDigital Library
12. 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, 147. Google ScholarDigital Library
13. Ji, Z., Liu, L., and Wang, Y. 2010. B-mesh: A modeling system for base meshes of 3d articulated shapes. In Proc. Pacific Graphics ’10, 2169–2178.Google Scholar
14. Kälberer, F., Nieser, M., and Polthier, K. 2007. Quad-cover – surface parameterization using branched coverings. Computer Graphics Forum 26, 3, 375–384.Google ScholarCross Ref
15. Kovacs, D., Myles, A., and Zorin, D. 2011. Anisotropic quadrangulation. Comp. Aided Geom. Design 28, 8, 449–462. Google ScholarDigital Library
16. Krishnamurthy, V., and Levoy, M. 1996. Fitting smooth surfaces to dense polygon meshes. In Proc. SIGGRAPH 96, 313–324. Google ScholarDigital Library
17. Lai, Y.-K., Jin, M., Xie, X., He, Y., Palacios, J., Zhang, E., Hu, S.-M., and Gu, X. 2010. Metric-driven rosy field design and remeshing. IEEE Trans. Vis. Comput. Graph. 16, 1, 95–108. Google ScholarDigital Library
18. Marinov, M., and Kobbelt, L. 2004. Direct anisotropic quad-dominant remeshing. In Proc. Pacific Graphics ’04, 207–216. Google ScholarDigital Library
19. Müller-Hannemann, M. 1998. Hexahedral mesh generation by successive dual cycle elimination. In Int. Meshing Roundtable 98, 379–393.Google Scholar
20. Murdoch, P., Benzley, S., Blacker, T., and Mitchell, S. A. 1997. The spatial twist continuum: a connectivity based method for representing all-hexahedral finite element meshes. Finite Elem. Anal. Des. 28, 137–149. Google ScholarDigital Library
21. Myles, A., Pietroni, N., Kovacs, D., and Zorin, D. 2010. Feature-aligned T-meshes. In Proc. SIGGRAPH 2010, 117:1–117:11. Google ScholarDigital Library
22. Palacios, J., and Zhang, E. 2007. Rotational symmetry field design on surfaces. In Proc. SIGGRAPH 2007, 55:1–55:10. Google ScholarDigital Library
23. Panozzo, D., Puppo, E., Tarini, M., Pietroni, N., and Cignoni, P. 2011. Automatic construction of quad-based subdivision surfaces using fitmaps. IEEE Trans. Vis. Comput. Graph. 17, 10, 1510–1520. Google ScholarDigital Library
24. Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic global parameterization. ACM Trans. Graph. 25, 1460–1485. Google ScholarDigital Library
25. Ray, N., Vallet, B., Li, W. C., and Lévy, B. 2008. N-symmetry direction field design. ACM Trans. Graph. 27, 10:1–10:13. Google ScholarDigital Library
26. Ray, N., Vallet, B., Alonso, L., and Levy, B. 2009. Geometry-aware direction field processing. ACM Trans. Graph. 29, 1, 1:1–1:11. Google ScholarDigital Library
27. Schmidt, R., Grimm, C., and Wyvill, B. 2006. Interactive decal compositing with discrete exponential maps. In Proc. SIGGRAPH 2006, 605–613. Google ScholarDigital Library
28. Sethian, J. A., and Vladimirsky, A. 2003. Ordered upwind methods for static hamilton-jacobi equations: Theory and algorithms. SIAM J. Numerical Analysis 41, 1, 325–363. Google ScholarDigital Library
29. Tarini, M., Hormann, K., Cignoni, P., and Montani, C. 2004. Polycube-maps. In Proc. SIGGRAPH 2004, 853–860. Google ScholarDigital Library
30. Tarini, M., Puppo, E., Panozzo, D., Pietroni, N., and Cignoni, P. 2011. Simple quad domains for field aligned mesh parametrization. Proc. SIGGRAPH Asia 2011 30, 6. Google Scholar
31. Tierny, J., Daniels, J., Nonato, L. G., Pascucci, V., and Silva, C. 2011. Interactive quadrangulation with reeb atlases and connectivity textures. IEEE TVCG 99. Google ScholarDigital Library
32. Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Proc. SGP ’06, 201–210. Google ScholarDigital Library
33. Zhang, M., Huang, J., Liu, X., and Bao, H. 2010. A wave-based anisotropic quadrangulation method. In Proc. SIGGRAPH 2010., 118:1–118:8. Google ScholarDigital Library