“Integer-grid maps for reliable quad meshing” by Bommes, Campen, Ebke, Alliez and Kobbelt
Conference:
Type(s):
Title:
- Integer-grid maps for reliable quad meshing
Session/Category Title: Quads & Meshing
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
