“Shape from metric” by Chern, Knöppel, Pinkall and Schröder

  • ©Albert Chern, Felix Knöppel, Ulrich Pinkall, and Peter Schröder

Conference:


Type:


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


ACM Digital Library Publication:



Overview Page: