“Bounded distortion mapping spaces for triangular meshes” by Lipman

The problem of mapping triangular meshes into the plane is fundamental in geometric modeling, where planar deformations and surface parameterizations are two prominent examples. Current methods for triangular mesh mappings cannot, in general, control the worst case distortion of all triangles nor guarantee injectivity.This paper introduces a constructive definition of generic convex spaces of piecewise linear mappings with guarantees on the maximal conformal distortion, as-well as local and global injectivity of their maps. It is shown how common geometric processing objective functionals can be restricted to these new spaces, rather than to the entire space of piecewise linear mappings, to provide a bounded distortion version of popular algorithms.

1. Ahlfors, L. 1966. Lectures on quasiconformal mappings. University lecture series. American Mathematical Society.Google Scholar
2. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Proceedings of SIGGRAPH ’00, ACM, New York, NY, USA, 157–164. Google ScholarDigital Library
3. Amenta, A. B., Bern, M. W., and Eppstein, D. 1997. Optimal point placement for mesh smoothing. In Proc. 8th Symp. Discrete Algorithms, ACM and SIAM, 528–537. Google ScholarDigital Library
4. Andersen, E. D., and Andersen, K. D. 1999. The MOSEK interior point optimization for linear programming: an implementation of the homogeneous algorithm. Kluwer Academic Publishers, 197–232.Google Scholar
5. Aronov, B., Seidel, R., and Souvaine, D. 1993. On compatible triangulations of simple polygons. Comput. Geom. Theory Appl. 3 (June), 27–35. Google ScholarDigital Library
6. Ben-chen, M., Gotsman, C., and Bunin, G. 2008. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum 27.Google Scholar
7. Bern, M. W., and Eppstein, D. 1995. Mesh generation and optimal triangulation. In Computing in Euclidean Geometry, D.-Z. Du and F. K.-M. Hwang, Eds., second ed., no. 4 in Lecture Notes Series on Computing. World Scientific, 47–123.Google Scholar
8. Bookstein, F. L. 1989. Principal warps: Thin-plate splines and the decomposition of deformations. IEEE Trans. Pattern Anal. Mach. Intell. 11 (June), 567–585. Google ScholarDigital Library
9. Brenner, S., and Scott, L. 2008. The mathematical theory of finite element methods. Texts in applied mathematics. Springer.Google Scholar
10. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29 (July), 38:1–38:6. Google ScholarDigital Library
11. Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic Pa-rameterizations of Surface Meshes. Computer Graphics Forum 21.Google Scholar
12. Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, SIGGRAPH ’95, 173–182. Google ScholarDigital Library
13. Floater, M. S., and Hormann, K. 2005. Surface Parameterization: a Tutorial and Survey. Advances in Multiresolution for Geometric Modelling, 157–186.Google Scholar
14. Floater, M. S. 2003. One-to-one piecewise linear mappings over triangulations. Mathematics of Computation 72, 685–696. Google ScholarDigital Library
15. Gaidashev, D., and Khmelev, D. 2008. On numerical algorithms for the solution of a beltrami equation. SIAM J. Numer. Anal. 46 (May), 2238–2253. Google ScholarDigital Library
16. Gortler, S. J., Gotsman, C., and Thurston, D. 2006. Discrete one-forms on meshes and applications to 3d mesh parameterization. Comput. Aided Geom. Des. 23, 2 (Feb.). Google ScholarDigital Library
17. Hormann, K., and Greiner, G. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design: Saint-Malo 1999, P.-J. Laurent, P. Sablonnière, and L. L. Schumaker, Eds., Innovations in Applied Mathematics. Vanderbilt University Press, Nashville, TN, 153–162.Google Scholar
18. Igarashi, T., Moscovich, T., and Hughes, F. J. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph 24, 1134–1141. Google ScholarDigital Library
19. Imayoshi, Y., and Taniguchi, M. 1992. An introduction to Teichmüller spaces. Springer-Verlag.Google Scholar
20. Jacobson, A., Baran, I., Popović, J., and Sorkine, O. 2011. Bounded biharmonic weights for real-time deformation. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH) 30, 4, 78:1–78:8. Google ScholarDigital Library
21. Jin, M., Kim, J., and Gu, X. D. 2007. Discrete surface ricci flow: Theory and applications. In In IMA Conference on the Mathematics of Surfaces, 209–232. Google ScholarDigital Library
22. Johnen, A., Remacle, J.-F., and Geuzaine, C. 2012. Geometrical validity of curvilinear finite elements. In Proceedings of the 20th International Meshing Roundtable. 255–271.Google Scholar
23. Kharevych, L., Springborn, B., and Schröder, P. 2006. Discrete conformal mappings via circle patterns. ACM Trans. Graph. 25 (April), 412–438. Google ScholarDigital Library
24. Levy, B., Petitjean, S., Ray, N., and Maillo t, J. 2002. Least squares conformal maps for automatic texture atlas generation. In ACM SIGGRAPH conference proceedings, ACM, Ed. Google ScholarDigital Library
25. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27, 3. Google ScholarDigital Library
26. Lipman, Y., Kim, V., and Funkhouser, T. 2012. Simple formulas for quasiconformal plane deformations. ACM Transactions on Graphics, accepted for publication. Google ScholarDigital Library
27. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. In Proceedings of the Symposium on Geometry Processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SGP ’08, 1495–1504. Google ScholarDigital Library
28. Maillot, J., Yahia, H., and Verroust, A. 1993. Interactive texture mapping. In SIGGRAPH ’93: Proceedings of the 20th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 27–34. Google ScholarDigital Library
29. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 15–36.Google ScholarCross Ref
30. Ruppert, J. 1995. A delaunay refinement algorithm for quality 2-dimensional mesh generation. In Selected papers from the fourth annual ACM SIAM symposium on Discrete algorithms, Academic Press, Inc., Orlando, FL, USA, 548–585. Google ScholarDigital Library
31. Sander, P. V., Snyder, J., Gortler, S. J., and Hoppe, H. 2001. Texture mapping progressive meshes. In Proceeding of SIGGRAPH ’01, ACM, New York, NY, USA, 409–416. Google ScholarDigital Library
32. Schaefer, S., McPhail, T., and Warren, J. 2006. Image deformation using moving least squares. ACM Trans. Graph. 25 (July), 533–540. Google ScholarDigital Library
33. Sheffer, A., Lévy, B., Mogilnitsky, M., and Bogomyakov, A. 2005. Abf++: fast and robust angle based flattening. ACM Trans. Graph. 24 (April), 311–330. Google ScholarDigital Library
34. 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
35. Shewchuk, J. R. 1996. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In Applied Computational Geometry: Towards Geometric Engineering, M. C. Lin and D. Manocha, Eds., vol. 1148 of Lecture Notes in Computer Science. Springer-Verlag, May, 203–222. Google ScholarDigital Library
36. Solomon, J., Ben-Chen, M., Butscher, A., and Guibas, L. 2011. As-Killing-As-Possible Vector Fields for Planar Deformation. Computer Graphics Forum 30, 5, 1543–1552.Google ScholarCross Ref
37. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proceedings of the fifth Eurographics symposium on Geometry processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 109–116. Google ScholarDigital Library
38. Sorkine, O., Cohen-Or, D., Goldenthal, R., and Lischinski, D. 2002. Bounded-distortion piecewise mesh parameterization. In Proceedings of IEEE Visualization, IEEE Computer Society, 355–362. Google ScholarDigital Library
39. Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. 27 (August), 77:1–77:11. Google ScholarDigital Library
40. Stephenson, K. 2005. Introduction to circle packing: the theory of discrete analytic functions. Cambridge University Press.Google Scholar
41. Tutte, W. T. 1963. How to Draw a Graph. Proceedings of the London Mathematical Society s3–13, 1, 743–767.Google ScholarCross Ref
42. Weber, O., and Gotsman, C. 2010. Controllable conformal maps for shape deformation and interpolation. ACM Trans. Graph. 29, 78:1–78:11. Google ScholarDigital Library
43. Zeng, W., and Gu, X. D. 2011. Registration for 3d surfaces with large deformations using quasi-conformal curvature flow. In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, 2457–2464. Google ScholarDigital Library
44. Zeng, W., Luo, F., Yau, S. T., and Gu, X. D. 2009. Surface quasi-conformal mapping by solving beltrami equations. In Proceedings of the 13th IMA International Conference on Mathematics of Surfaces XIII, Springer-Verlag, Berlin, Heidelberg, 391–408. Google ScholarDigital Library