“Computing inversion-free mappings by simplex assembly” by Fu and Liu
Conference:
Type(s):
Title:
- Computing inversion-free mappings by simplex assembly
Session/Category Title: Parameterization & Remeshing
Presenter(s)/Author(s):
Abstract:
We present a novel method, called Simplex Assembly, to compute inversion-free mappings with low or bounded distortion on simplicial meshes. Our method involves two steps: simplex disassembly and simplex assembly. Given a simplicial mesh and its initial piecewise affine mapping, we project the affine transformation associated with each simplex into the inversion-free and distortion-bounded space. The projection disassembles the input mesh into disjoint simplices. The disjoint simplices are then assembled to recover the original connectivity by minimizing the mapping distortion and the difference of the disjoint vertices with respect to the piecewise affine transformations, while the piecewise affine mapping is restricted inside the feasible space. Due to the use of affine transformations as variables, our method explicitly guarantees that no inverted simplex occurs, and that the mapping distortion is below the bound during the optimization. Compared with existing methods, our method is robust to an initialization with many inverted elements and positional constraints. We demonstrate the efficiency and robustness of our method through a variety of geometric processing tasks.
References:
1. Aigerman, N., and Lipman, Y. 2013. Injective and bounded distortion mappings in 3D. ACM Trans. Graph. (SIGGRAPH) 32, 4, 106:1–106:14.
2. Ben-Chen, M., Gotsman, C., and Bunin, G. 2008. Conformal flattening by curvature prescription and metric scaling. Comput. Graph. Forum (EG) 27, 2, 449–458. Cross Ref
3. Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., and Lévy, B. 2010. Polygon Mesh Processing. A K Peters/CRC Press.
4. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. (SIGGRAPH) 29, 4, 38:1–38:6.
5. Chen, R., and Weber, O. 2015. Bounded distortion harmonic mappings in the plane. ACM Trans. Graph. (SIGGRAPH) 34, 4, 73:1–73:12.
6. Crane, K., Pinkall, U., and Schröder, P. 2011. Spin transformations of discrete surfaces. ACM Trans. Graph. (SIGGRAPH) 30, 104:1–104:10.
7. Crane, K., Pinkall, U., and Schröder, P. 2013. Robust fairing via conformal curvature flow. ACM Trans. Graph. (SIGGRAPH) 32, 61:1–61:10.
8. Degener, P., Meseth, J., and Klein, R. 2003. An adaptable surface parameterization method. In Int. Meshing Roundtable, 201–213.
9. Diamanti, O., Vaxman, A., Panozzo, D., and Sorkine-Hornung, O. 2015. Integrable PolyVector fields. ACM Trans. Graph. (SIGGRAPH) 34, 4, 38:1–38:12.
10. Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In In Advances in Multiresolution for Geometric Modelling, Springer, 157–186.
11. Floater, M. S. 2003. One-to-one piecewise linear mappings over triangulations. Math. Comput. 72, 685–696.
12. Fu, X.-M., Liu, Y., and Guo, B. 2015. Computing locally injective mappings by advanced MIPS. ACM Trans. Graph. (SIGGRAPH) 34, 4, 71:1–71:12.
13. Guennebaud, G., Jacob, B., et al., 2010. Eigen v3. http://eigen.tuxfamily.org.
14. Hormann, K., and Greiner, G. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design: Saint-Malo 1999. Vanderbilt University Press, 153–162.
15. Ivanov, A. O., and Tuzhilin, A. A. 1994. Minimal Networks: The Steiner Problem and Its Generalizations. CRC Press.
16. Jin, Y., Huang, J., and Tong, R. 2014. Remeshing-assisted optimization for locally injective mappings. Comput. Graph. Forum (SGP) 33, 5, 269–279.
17. Kovalsky, S. Z., Aigerman, N., Basri, R., and Lipman, Y. 2014. Controlling singular values with semidefinite programming. ACM Trans. Graph. (SIGGRAPH) 33, 4, 68:1–68:13.
18. Kovalsky, S. Z., Aigerman, N., Basri, R., and Lipman, Y. 2015. Large-scale bounded distortion mappings. ACM Trans. Graph. (SIGGRAPH ASIA) 34, 6, 191:1–191:10.
19. Levi, Z., and Zorin, D. 2014. Strict minimizers for geometric optimization. ACM Trans. Graph. (SIGGRAPH) 33, 6, 185:1–185:14.
20. Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. (SIGGRAPH) 21, 3, 362–371.
21. Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. (SIGGRAPH) 31, 4, 108:1–108:13.
22. Lipman, Y. 2014. Bijective mappings of meshes with boundary and the degree in mesh processing. SIAM J. Imaging Sciences 7, 2, 1263–1283. Cross Ref
23. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. Comput. Graph. Forum (SGP) 27, 5, 1495–1504.
24. Liu, T., Gao, M., Zhu, L., Sifakis, E., and Kavan, L. 2016. Fast and robust inversion-free shape manipulation. Comput. Graph. Forum (EG) 35, 2. Cross Ref
25. Myles, A., Pietroni, N., and Zorin, D. 2014. Robust field-aligned global parametrization. ACM Trans. Graph. (SIGGRAPH) 33, 4, 135:1–135:14.
26. Nocedal, J., and Wright, S. 2006. Numerical Optimization, 2nd ed. Springer.
27. Paillé, G.-P., Ray, N., Poulin, P., Sheffer, A., and Lévy, B. 2015. Dihedral angle-based maps of tetrahedral meshes. ACM Trans. Graph. (SIGGRAPH) 34, 4, 54:1–54:10.
28. Poranne, R., and Lipman, Y. 2014. Provably good planar mappings. ACM Trans. Graph. (SIGGRAPH) 33, 4, 76:1–76:11.
29. Rabinovich, M., Poranne, R., Panozzo, D., and Sorkine-Hornung, O. 2016. Scalable locally injective maps. Tech. rep., ETH.
30. Schüller, C., Kavan, L., Panozzo, D., and Sorkine-Hornung, O. 2013. Locally injective mappings. Comput. Graph. Forum (SGP) 32, 5, 125–135.
31. Sheffer, A., and de Sturler, E. 2001. Parameterization of faceted surfaces for meshing using angle-based flattening. Eng. Comput. 17, 3, 326–337. Cross Ref
32. Sheffer, A., Lévy, B., Mogilnitsky, M., and Bogomyakov, A. 2005. ABF++: fast and robust angle based flattening. ACM Trans. Graph. 24, 2, 311–330.
33. Smith, J., and Schaefer, S. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. (SIGGRAPH) 34, 4, 70:1–70:9.
34. Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. (SIGGRAPH) 27, 3, 77:1–77:11.
35. Tutte, W. T. 1963. How to draw a graph. In Proceedings of the London Mathematical Society, vol. 13, 747–767.
36. Weber, O., and Zorin, D. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Trans. Graph. (SIGGRAPH) 33, 4, 75:1–75:12.
37. Weber, O., Myles, A., and Zorin, D. 2012. Computing extremal quasiconformal maps. Comput. Graph. Forum 31, 5, 1679–1689.
38. Xu, Y., Chen, R., Gotsman, C., and Liu, L. 2011. Embedding a triangular graph within a given boundary. Comput. Aided Geom. Des. 28, 6, 349–356.
39. Yu, Y., Zhou, K., Xu, D., Shi, X., Bao, H., Guo, B., and Shum, H.-Y. 2004. Mesh editing with Poisson-based gradient field manipulation. ACM Trans. Graph. (SIGGRAPH) 23, 3, 644–651.
40. Zayer, R., Lévy, B., and Seidel, H.-P. 2007. Linear angle based parameterization. In Symp. Geom. Proc., 135–141.
