“Shape from metric” by Chern, Knöppel, Pinkall and Schröder
Conference:
Type(s):
Entry Number: 63
Title:
- Shape from metric
Session/Category Title: Cleaning Up the Mesh We Made
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We study the isometric immersion problem for orientable surface triangle meshes endowed with only a metric: given the combinatorics of the mesh together with edge lengths, approximate an isometric immersion into R3. To address this challenge we develop a discrete theory for surface immersions into R3. It precisely characterizes a discrete immersion, up to subdivision and small perturbations. In particular our discrete theory correctly represents the topology of the space of immersions, i.e., the regular homotopy classes which represent its connected components. Our approach relies on unit quaternions to represent triangle orientations and to encode, in their parallel transport, the topology of the immersion. In unison with this theory we develop a computational apparatus based on a variational principle. Minimizing a non-linear Dirichlet energy optimally finds extrinsic geometry for the given intrinsic geometry and ensures low metric approximation error.We demonstrate our algorithm with a number of applications from mathematical visualization and art directed isometric shape deformation, which mimics the behavior of thin materials with high membrane stiffness.
References:
1. Michael F. Atiyah. 1971. Riemann Surface and Spin Structures. Ann. sci. de l’Éco. N. Sup. 4, 1 (1971), 47–62.Google Scholar
2. Seung-Yeob Baek, Jeonghun Lim, and Kunwoo Lee. 2015. Isometric Shape Interpolation. Comp. & Graph. 46 (2015), 257–263. Google ScholarDigital Library
3. Abdenago Barros, Esdras Medeiros, and Romildo Silva. 2011. Two Counterexamples of Global Differential Geometry for Polyhedra. JP J. Geom. Top. 11, 1 (2011), 65–76.Google Scholar
4. Marcel Berger. 2010. Geometry Revealed. Springer.Google Scholar
5. Vincent Borrelli, Saïd Jabrane, Francis Lazarus, and Boris Thibert. 2012. Flat Tori in Three-Dimensional Space and Convex Integration. Proc. Nat. Acad. Sci. 109, 19 (2012), 7218–7223. Project page: http://hevea-project.fr/ENIndexHevea.html.Google ScholarCross Ref
6. Vincent Borrelli, Saïd Jabrane, Francis Lazarus, and Boris Thibert. 2013. Isometric Embeddings of the Square Flat Torus in Ambient Space. Ensaios Matemáticos 24 (2013), 1–91.Google Scholar
7. Friedrich Bös, Max Wardetzky, Etienne Vouga, and Omer Gottesman. 2016. On the Incompressibility of Cylindrical Origami Patterns. J. Mech. Des. 139, 2 (2016), 021404:1–9.Google ScholarCross Ref
8. Davide Boscaini, Davide Eynard, Drosos Kourounis, and Michael M. Bronstein. 2015. Shape-from-Operator: Recovering Shapes from Intrinsic Operators. Comp. Graph. Forum 34, 2 (2015), 265–274. Google ScholarDigital Library
9. Mario Botsch, Mark Pauly, Markus Gross, and Leif Kobbelt. 2006. PriMo: Coupled Prisms for Intuitive Surface Modeling. In Proc. Symp. Geom. Proc. 11–20. Google ScholarDigital Library
10. Sofien Bouaziz, Mario Deuss, Yuliy Schwartzburg, Thibaut Weise, and Mark Pauly. 2012. Shape-Up: Shaping Discrete Geometry with Projections. Comp. Graph. Forum 31, 5 (2012), 1657–1667. Google ScholarDigital Library
11. Werner Boy. 1903. Über die Curvatura integra und die Topologie geschlossener Flächen. Math. Ann. 57 (1903), 151–184.Google ScholarCross Ref
12. Robert Bridson, S. Marino, and Ronald Fedkiw. 2003. Simulation of Clothing with Folds and Wrinkles. In Proc. Symp. Comp. Anim. 28–36. Google ScholarDigital Library
13. Yu. D. Burago and V. A. Zalgaller. 1960. Polyhedral Embedding of a Flat Metric with Conical Singularities. Vestnik Leningrad Univ. 15, 7 (1960), 66–80.Google Scholar
14. Yu. D. Burago and V. A. Zalgaller. 1995. Isometric Piecewise-Linear Embeddings of Two-Dimensional Manifolds with a Polyhedral Metric into R3. Algebra i Analiz 7, 3 (1995), 76–95. English translation in St. Petersburg Math. J. 7, 3 (1996), 369–385.Google Scholar
15. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A Simple Geometric Model for Elastic Deformations. ACM Trans. Graph. 29, 4 (2010), 38:1–38:6. Google ScholarDigital Library
16. Keenan Crane, Mathieu Desbrun, and Peter Schröder. 2010. Trivial Connections on Discrete Surfaces. Comp. Graph. Forum 29, 5 (2010), 1525–1533.Google ScholarCross Ref
17. Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2011. Spin Transformations of Discrete Surfaces. ACM Trans. Graph. 30, 4 (2011), 104:1–104:10. Google ScholarDigital Library
18. Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Robust Fairing via Conformal Curvature Flow. ACM Trans. Graph. 32, 4 (2013), 61:1–61:10. Google ScholarDigital Library
19. Mathieu Desbrun, Eva Kanso, and Yiying Tong. 2008. Discrete Differential Forms for Computational Modeling. In Discrete Differential Geometry, Alexander I. Bobenko, Peter Schröder, John M. Sullivan, and Günther M. Ziegler (Eds.). Oberwolfach Seminars, Vol. 38. Birkhäuser Verlag.Google Scholar
20. Paweł Dłotko. 2012. A Fast Algorithm to Compute Cohomology Group Generators of Orientable 2-Manifolds. Patt. Recog. Lett. 33, 11 (2012), 1468–1476. Google ScholarDigital Library
21. David Eppstein. 2003. Dynamic Generators of Topologically Embedded Graphs. In Proc. ACM-SIAM Symp. Disc. Alg. 599–608. Google ScholarDigital Library
22. Jeff Erickson and Kim Whittlesey. 2005. Greedy Optimal Homotopy and Homology Generators. In Proc. ACM-SIAM Symp. Disc. Alg. 1038–1046. Google ScholarDigital Library
23. Gerd Fischer (Ed.). 2017. Mathematical Models (2nd ed.). Springer Spektrum.Google Scholar
24. Stefan Fröhlich and Mario Botsch. 2011. Example-Driven Deformations Based on Discrete Shells. Comp. Graph. Forum 30, 8 (2011), 2246–2257.Google ScholarCross Ref
25. Herman Gluck. 1974. Almost all Simply Connected Closed Surfaces are Rigid. In Geometric Topology (Lecture Notes in Mathematics), Vol. 438. Springer, 225–239.Google Scholar
26. Eitan Grinspun, Anil Hirani, Mathieu Desbrun, and Peter Schröder. 2003. Discrete Shells. In Proc. Symp. Comp. Anim. 62–67. Google ScholarDigital Library
27. Misha Gromov. 1986. Partial Differential Relations. Springer.Google Scholar
28. André Haefliger and Valentin Poénaru. 1964. La Classification des Immersions Combinatoires. Pub. Math. I’IHÉS 23 (1964), 75–91.Google Scholar
29. Joel Hass and John Hughes. 1985. Immersions of Surfaces in 3-Manifolds. Topology 24, 1 (1985), 97–112.Google ScholarCross Ref
30. Morris W. Hirsch. 1959. Immersions of Manifolds. Trans. Amer. Math. Soc. 93 (1959), 242–276.Google ScholarCross Ref
31. Tim Hoffmann and Zi Ye. 2018. A Discrete Extrinsic and Intrinsic Dirac Operator. (2018). arXiv:1802.06278.Google Scholar
32. Martin Isenburg, Stefan Gumhold, and Craig Gotsman. 2001. Connectivity Shapes. In Proc. IEEE Vis. 135–142. Google ScholarDigital Library
33. Eric Jones, Travis Oliphant, Pearu Peterson, and others. 2001. SciPy: Open Source Scientific Tools for Python. Online at http://scipy.org/. (2001).Google Scholar
34. Louis H. Kauffman and Thomas F. Banchoff. 1977. Immersions and mod-2 Quadratic Forms. Amer. Math. Month. 84, 3 (1977), 168–185.Google Scholar
35. Michael Kazhdan, Jake Solomon, and Mirela Ben-Chen. 2012. Can Mean-Curvature Flow Be Made Non-Singular? Comp. Graph. Forum 31, 5 (2012), 1745–1754. Google ScholarDigital Library
36. Scott Kircher and Michael Garland. 2008. Free-Form Motion Processing. ACM Trans. Graph. 27, 2 (2008), 12:1–12:13. Google ScholarDigital Library
37. Nicolaas H. Kuiper. 1955. On C1-isometric Imbeddings I & II. Indag. Math. 58 (1955), 545–556, 683–689.Google ScholarCross Ref
38. H. Blaine Lawson and Marie-Louise Michelsohn. 1990. Spin Geometry. PMS, Vol. 38. Princeton UP.Google Scholar
39. Peter Li and Shing-Tung Yau. 1982. A New Conformal Invariant and its Applications to the Willmore Conjecture and the first Eigenvalue of Compact Surfaces. Inv. Math. 69, 2 (1982), 269–291.Google ScholarCross Ref
40. Yaron Lipman, Olga Sorkine, David Levin, and Daniel Cohen-Or. 2005. Linear Rotation-Invariant Coordinates for Meshes. ACM Trans. Graph. 24, 3 (2005), 479–487. Google ScholarDigital Library
41. Nelson Max. 1976. Turning a Sphere Inside Out. Computer Animation. (1976). Available from CRC Press.Google Scholar
42. Nelson Max and Tom Banchoff. 1981. Contributions to Analysis and Geometry. JH Univ. P., Chapter Every Sphere Eversion has a Quadruple Point, 191–209.Google Scholar
43. John Nash. 1954. C1 Isometric Imbeddings. Math. Ann. 60, 3 (1954), 383–396.Google ScholarCross Ref
44. Deniele Panozzo, Enrico Puppo, Marco Tarini, and Olga Sorkine-Hornung. 2014. Frame Fields: Anisotropic and Non-orthogonal Cross Fields. ACM Trans. Graph. 33, 4 (2014), 134:1–134:11. Google ScholarDigital Library
45. Ulrich Pinkall. 1985. Regular Homotopy Classes of Immersed Surfaces. Topology 24, 4 (1985), 421–434.Google ScholarCross Ref
46. Henry Segerman. 2016. Visualizing Mathematics with 3D Printing. Johns Hopkins U. P.Google Scholar
47. Carlo H. Séquin. 2011. Torus Immersions and Transformations. Technical Report UCB/EECS-2011-83. UC Berkeley.Google Scholar
48. Amit Singer. 2011. Angular Synchronization by Eigenvectors and Semidefinite Programming. App. Comp. Harm. Anal. 30, 1 (2011), 20–36.Google ScholarCross Ref
49. Amit Singer and Hau-Tieng Wu. 2012. Vector Diffusion Maps and the Connection Laplacian. Comm. Pure Appl. Math. 65, 8 (2012), 1067–1144.Google ScholarCross Ref
50. Stephen Smale. 1959. A Classification of Immersions of the Two-Sphere. Trans. Amer. Math. Soc. 90, 2 (1959), 281–290.Google ScholarCross Ref
51. Olga Sorkine and Marc Alexa. 2007. As-Rigid-As-Possible Surface Modeling. In Proc. Symp. Geom. Proc. 109–116. Google ScholarDigital Library
52. Y. Wang, B. Liu, and Y. Tong. 2012. Linear Surface Reconstruction from Discrete Fundamental Forms on Triangle Meshes. Comp. Graph. Forum 31, 8 (2012), 2277–2287. Google ScholarDigital Library
53. Hassler Whitney. 1937. On Regular Closed Curves in the Plane. Comp. Math. 4 (1937), 276–284.Google Scholar
54. Tim Winkler, Jens Drieseberg, Marc Alexa, and Kai Hormann. 2010. Multi-Scale Geometry Interpolation. Comp. Graph. Forum 29, 2 (2010), 309–318.Google ScholarCross Ref
55. Min Zhang, Wei Zeng, Ren Guo, Feng Luo, and Xianfeng David Gu. 2015. Survey of Discrete Ricci Flow. J. Comput. Sci. Technol. 30, 3 (2015), 598–613.Google ScholarCross Ref
