QEx: robust quad mesh extraction

Abstract

The most popular and actively researched class of quad remeshing techniques is the family of parametrization based quad meshing methods. They all strive to generate an integer-grid map, i.e. a parametrization of the input surface into R² such that the canonical grid of integer iso-lines forms a quad mesh when mapped back onto the surface in R³. An essential, albeit broadly neglected aspect of these methods is the quad extraction step, i.e. the materialization of an actual quad mesh from the mere "quad texture". Quad (mesh) extraction is often believed to be a trivial matter but quite the opposite is true: numerous special cases, ambiguities induced by numerical inaccuracies and limited solver precision, as well as imperfections in the maps produced by most methods (unless costly countermeasures are taken) pose significant challenges to the quad extractor. We present a method to sanitize a provided parametrization such that it becomes numerically consistent even in a limited precision floating point representation. Based on this we are able to provide a comprehensive and sound description of how to perform quad extraction robustly and without the need for any complex tolerance thresholds or disambiguation rules. On top of that we develop a novel strategy to cope with common local fold-overs in the parametrization. This allows our method, dubbed QEx, to generate all-quadrilateral meshes where otherwise holes, non-quad polygons or no output at all would have been produced. We thus enable the practical use of an entire class of maps that was previously considered defective. Since state of the art quad meshing methods spend a significant share of their run time solely to prevent local fold-overs, using our method it is now possible to obtain quad meshes significantly quicker than before. We also provide libQEx, an open source C++ reference implementation of our method and thus significantly lower the bar to enter the field of quad meshing.

References

1. Alliez, P., Cohen-Steiner, D., Devillers, O., Lévy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. In Proc. SIGGRAPH 2003.
2. Bommes, D., Zimmer, H., and Kobbelt, L. 2009. Mixed-integer quadrangulation. In Proc. SIGGRAPH 2009.
3. Bommes, D., Campen, M., Ebke, H.-C., Alliez, P., and Kobbelt, L. 2013. Integer-grid maps for reliable quad meshing. In Proc. SIGGRAPH 2013.
4. Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., and Zorin, D. 2013. Quad-mesh generation and processing: A survey. Computer Graphics Forum.
5. Campen, M., Bommes, D., and Kobbelt, L. 2012. Dual loops meshing: quality quad layouts on manifolds. ACM Trans. Graph. 31, 4 (July), 110:1--110:11.
6. Dong, S., Kircher, S., and Garland, M. 2005. Harmonic functions for quadrilateral remeshing of arbitrary manifolds. Comput. Aided Geom. Des. 22, 5 (July), 392--423.
7. Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., and Hart, J. C. 2006. Spectral surface quadrangulation. In ACM SIGGRAPH 2006 Papers, ACM.
8. Edelsbrunner, H., and Mücke, E. P. 1990. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph. 9, 1 (Jan.), 66--104.
9. Fortune, S. 1995. Numerical stability of algorithms for 2d delaunay triangulations. International Journal of Computational Geometry & Applications 5, 01n02, 193--213.
10. Hoffmann, C. M. 2001. Robustness in geometric computations. Journal of Computing and Information Science in Engineering 1, 2, 143--156.
11. Huang, J., Zhang, M., Ma, J., Liu, X., Kobbelt, L., and Bao, H. 2008. Spectral quadrangulation with orientation and alignment control. In Proc. SIGGRAPH Asia 2008.
12. Kälberer, F., Nieser, M., and Polthier, K. 2007. Quadcover - surface parameterization using branched coverings. Computer Graphics Forum 26, 3, 375--384.
13. Li, E., Lévy, B., Zhang, X., Che, W., Dong, W., and Paul, J.-C. 2011. Meshless quadrangulation by global parameterization. Computers & Graphics 35, 5.
14. 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.).
15. Marinov, M., and Kobbelt, L. 2004. Direct anisotropic quaddominant remeshing. In Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, PG '04.
16. Myles, A., and Zorin, D. 2013. Controlled-distortion constrained global parametrization. ACM Trans. Graph. 32, 4.
17. Myles, A., Pietroni, N., Kovacs, D., and Zorin, D. 2010. Feature-aligned t-meshes. ACM Trans. Graph. 29, 4, 1--11.
18. Nieser, M., Reitebuch, U., and Polthier, K. 2011. Cubecover--parameterization of 3d volumes. Computer Graphics Forum 30, 5, 1397--1406.
19. Nieser, M., Palacios, J., Polthier, K., and Zhang, E. 2012. Hexagonal global parameterization of arbitrary surfaces. IEEE Trans. Vis. Comput. Graph. 18, 6, 865--878.
20. Priest, D. 1991. Algorithms for arbitrary precision floating point arithmetic. In Computer Arithmetic, 1991. Proceedings., 10th IEEE Symposium on, 132--143.
21. Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic global parameterization. ACM Trans. Graph. 25, 4.
22. Shewchuk, J. R. 1996. Robust Adaptive Floating-Point Geometric Predicates. In Proceedings of the Twelfth Annual Symposium on Computational Geometry.
23. Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Proc. SGP '06.
24. Yap, C. K. 1988. A geometric consistency theorem for a symbolic perturbation scheme. In Proceedings of the fourth annual symposium on Computational geometry.
25. Zhang, Y., Bajaj, C., and Xu, G. 2005. Surface smoothing and quality improvement of quadrilateral/hexahedral meshes with geometric flow. In Proc. of the 14th IMR, B. Hanks, Ed.
26. Zhang, M., Huang, J., Liu, X., and Bao, H. 2010. A wave-based anisotropic quadrangulation method. In Proc. SIGGRAPH 2010.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry