“Orbifold Tutte embeddings”
Conference:
Type(s):
Title:
- Orbifold Tutte embeddings
Session/Category Title: Mappings and Parameterizations
Presenter(s)/Author(s):
Abstract:
Injective parameterizations of surface meshes are vital for many applications in Computer Graphics, Geometry Processing and related fields. Tutte’s embedding, and its generalization to convex combination maps, are among the most popular approaches for computing parameterizations of surface meshes into the plane, as they guarantee injectivity, and their computation only requires solving a sparse linear system. However, they are only applicable to disk-type and toric surface meshes.In this paper we suggest a generalization of Tutte’s embedding to other surface topologies, and in particular the common, yet untreated case, of sphere-type surfaces. The basic idea is to enforce certain boundary conditions on the parameterization so as to achieve a Euclidean orbifold structure. The orbifold-Tutte embedding is a seamless, globally bijective parameterization that, similarly to the classic Tutte embedding, only requires solving a sparse linear system for its computation.In case the cotangent weights are used, the orbifold-Tutte embedding globally minimizes the Dirichlet energy and is shown to approximate conformal and four-point quasiconformal mappings. As far as we are aware, this is the first fully-linear method that produces bijective approximations to conformal mappings.Aside from parameterizations, the orbifold-Tutte embedding can be used to generate bijective inter-surface mappings with three or four landmarks and symmetric patterns on sphere-type surfaces.
References:
1. Aigerman, N., Poranne, R., and Lipman, Y. 2014. Lifted bijections for low distortion surface mappings. ACM Transactions on Graphics (TOG) 33, 4, 69.
2. Aigerman, N., Poranne, R., and Lipman, Y. 2015. Seamless surface mappings. ACM Transactions on Graphics (TOG), in print.
3. Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., and Davis, J. 2005. Scape: Shape completion and animation of people. ACM Trans. Graph. 24, 3 (July), 408–416.
4. Ben-Chen, M., Gotsman, C., and Bunin, G. 2008. Conformal flattening by curvature prescription and metric scaling. In Computer Graphics Forum, vol. 27, Wiley Online Library, 449–458.
5. Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., and Zorin, D. 2013. Quad-mesh generation and processing: A survey. In Computer Graphics Forum, vol. 32, Wiley Online Library, 51–76.
6. 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 32, 6, 51–76.
7. Castelli Aleardi, L., Fusy, R., and Kostrygin, A. 2014. Periodic planar straight-frame drawings with polynomial resolution. In LATIN 2014: Theoretical Informatics, A. Pardo and A. Viola, Eds., vol. 8392 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 168–179.
8. Conway, J. H., Burgiel, H., and Goodman-Strauss, C. 2008. The symmetries of things. Appl Math Comput 10, 12.
9. Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of surface meshes. In Computer Graphics Forum, vol. 21, Wiley Online Library, 209–218.
10. Feingold, D. G., and Varga, R. S. 1962. Block diagonally dominant matrices and generalizations of the gerschgorin circle theorem. Pacific J. Math. 12, 4, 1241–1250.
11. Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In Advances in multiresolution for geometric modelling. Springer, 157–186.
12. Floater, M. 2003. One-to-one piecewise linear mappings over triangulations. Mathematics of Computation 72, 242, 685–696.
13. Floater, M. S. 2003. Mean value coordinates. Computer aided geometric design 20, 1, 19–27.
14. Giorgi, D., Biasotti, S., and Paraboschi, L. 2007. SHREC: SHape REtrieval Contest: Watertight models track. http://watertight.ge.imati.cnr.it/.
15. Gortler, S. J., Gotsman, C., and Thurston, D. 2006. Discrete one-forms on meshes and applications to 3d mesh parameterization. Computer Aided Geometric Design 23, 2, 83–112.
16. Gotsman, C., Gu, X., and Sheffer, A. 2003. Fundamentals of spherical parameterization for 3d meshes. ACM Transactions on Graphics (TOG) 22, 3, 358–363.
17. Gu, X., and Yau, S.-T. 2003. Global conformal surface parameterization. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, Eurographics Association, 127–137.
18. 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.
19. Kälberer, F., Nieser, M., and Polthier, K. 2007. Quadcover-surface parameterization using branched coverings. In Computer Graphics Forum, vol. 26, Wiley Online Library, 375–384.
20. Kazhdan, M., Solomon, J., and Ben-Chen, M. 2012. Can mean-curvature flow be modified to be non-singular? Comp. Graph. Forum 31, 5 (Aug.), 1745–1754.
21. Kharevych, L., Springborn, B., and Schröder, P. 2006. Discrete conformal mappings via circle patterns. ACM Transactions on Graphics (TOG) 25, 2, 412–438.
22. Kim, V. G., Lipman, Y., and Funkhouser, T. 2011. Blended intrinsic maps. In ACM Transactions on Graphics (TOG), vol. 30, ACM, 79.
23. Knöppel, F., Crane, K., Pinkall, U., and Schröder, P. 2013. Globally optimal direction fields. ACM Trans. Graph. 32, 4.
24. Kobourov, S., and Landis, M. 2007. Morphing planar graphs in spherical space. In Graph Drawing, M. Kaufmann and D. Wagner, Eds., vol. 4372 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 306–317.
25. Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. In ACM Transactions on Graphics (TOG), vol. 21, ACM, 362–371.
26. Lovász, L. 2004. Discrete analytic functions: an exposition. Surveys in differential geometry 9, 241–273.
27. Myles, A., and Zorin, D. 2012. Global parametrization by incremental flattening. ACM Transactions on Graphics (TOG) 31, 4, 109.
28. Myles, A., and Zorin, D. 2013. Controlled-distortion constrained global parametrization. ACM Transactions on Graphics (TOG) 32, 4, 105.
29. Palacios, J., and Zhang, E. 2007. Rotational symmetry field design on surfaces. In ACM Transactions on Graphics (TOG), vol. 26, ACM, 55.
30. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental mathematics 2, 1, 15–36.
31. Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic global parameterization. ACM Transactions on Graphics (TOG) 25, 4, 1460–1485.
32. Ray, N., Vallet, B., Li, W.-C., and Lvy, B. 2008. N-symmetry direction field design. In ACM Transactions on Graphics. Presented at SIGGRAPH.
33. Schwartz, R. E. 2011. Mostly surfaces, vol. 60. American Mathematical Soc.
34. Sheffer, A., Lévy, B., Mogilnitsky, M., and Bogomyakov, A. 2005. Abf++: fast and robust angle based flattening. ACM Transactions on Graphics (TOG) 24, 2, 311–330.
35. Sheffer, A., Praun, E., and Rose, K. 2006. Mesh parameterization methods and their applications. Found. Trends. Comput. Graph. Vis. 2, 2 (Jan.), 105–171.
36. Springborn, B., Schröder, P., and Pinkall, U. 2008. Conformal equivalence of triangle meshes. ACM Transactions on Graphics (TOG) 27, 3, 77.
37. Sun, J., Wu, T., Gu, X., and Luo, F. 2014. Discrete conformal deformation: Algorithm and experiments. CoRR abs/1412.6892.
38. Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SGP ’06, 201–210.
39. Tsui, A., Fenton, D., Vuong, P., Hass, J., Koehl, P., Amenta, N., Coeurjolly, D., DeCarli, C., and Carmichael, O. 2013. Globally optimal cortical surface matching with exact landmark correspondence. In Proceedings of the 23rd International Conference on Information Processing in Medical Imaging, Springer-Verlag, Berlin, Heidelberg, IPMI’13, 487–498.
40. Tutte, W. T. 1963. How to draw a graph. Proc. London Math. Soc 13, 3, 743–768.
41. Weber, O., and Zorin, D. 2014. Locally injective parametrization with arbitrary fixed boundaries. ACM Transactions on Graphics (TOG) 33, 4, 75.
