A manifold of planar triangular meshes with complete Riemannian metric
HTML articles powered by AMS MathViewer
- by Roland Herzog and Estefanía Loayza-Romero;
- Math. Comp. 92 (2023), 1-50
- DOI: https://doi.org/10.1090/mcom/3775
- Published electronically: September 12, 2022
- PDF | Request permission
Abstract:
Shape spaces are fundamental in a variety of applications including image registration, morphing, matching, interpolation, and shape optimization. In this work, we consider two-dimensional shapes represented by triangular meshes of a given connectivity. We show that the collection of admissible configurations representable by such meshes forms a smooth manifold. For this manifold of planar triangular meshes we propose a geodesically complete Riemannian metric. It is a distinguishing feature of this metric that it preserves the mesh connectivity and prevents the mesh from degrading along geodesic curves. We detail a symplectic numerical integrator for the geodesic equation in its Hamiltonian formulation. Numerical experiments show that the proposed metric keeps the cell aspect ratios bounded away from zero and thus avoids mesh degradation along arbitrarily long geodesic curves.References
- Ilka Agricola and Thomas Friedrich, Elementary geometry, Student Mathematical Library, vol. 43, American Mathematical Society, Providence, RI, 2008. Translated from the 2005 German original by Philip G. Spain. MR 2387369, DOI 10.1090/stml/043
- M. Alexa, Recent advances in mesh morphing, Computer Graphics Forum 21 (2002), no. 2, 173–198, DOI 10.1111/1467-8659.00575.
- M. Alexa, D. Cohen-Or, and D. Levin, As-rigid-as-possible shape interpolation, Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’00, 2000, pp. 157–164, DOI 10.1145/344779.344859.
- Nina Amenta and Carlos Rojas, Dihedral deformation and rigidity, Comput. Geom. 90 (2020), 101657, 13. MR 4109629, DOI 10.1016/j.comgeo.2020.101657
- A. Baghaie, Z. Yu, and R. M. D’souza, Fast mesh-based medical image registration, Advances in Visual Computing, Springer International Publishing, 2014, pp. 1–10, DOI 10.1007/978-3-319-14364-4_1.
- Martin Bauer, Philipp Harms, and Peter W. Michor, Sobolev metrics on shape space of surfaces, J. Geom. Mech. 3 (2011), no. 4, 389–438. MR 2888014, DOI 10.3934/jgm.2011.3.389
- Martin Bauer, Philipp Harms, and Peter W. Michor, Sobolev metrics on shape space, II: Weighted Sobolev metrics and almost local metrics, J. Geom. Mech. 4 (2012), no. 4, 365–383. MR 3011892, DOI 10.3934/jgm.2012.4.365
- Martin Berggren, A unified discrete-continuous sensitivity analysis method for shape optimization, Applied and numerical partial differential equations, Comput. Methods Appl. Sci., vol. 15, Springer, New York, 2010, pp. 25–39. MR 2642680, DOI 10.1007/978-90-481-3239-3_{4}
- Temistocle Bîrsan, Bounds for elements of a triangle expressed by $R$, $r$ and $s$, Forum Geom. 15 (2015), 99–103. MR 3499916
- F. L. Bookstein, Size and shape spaces for landmark data in two dimensions, Statist. Sci. 1 (1986), no. 2, 181–222, DOI 10.1214/ss/1177013696.
- M. C. Delfour and J.-P. Zolésio, Shapes and geometries, 2nd ed., Advances in Design and Control, vol. 22, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. Metrics, analysis, differential calculus, and optimization. MR 2731611, DOI 10.1137/1.9780898719826
- Manfredo Perdigão do Carmo, Riemannian geometry, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1992. Translated from the second Portuguese edition by Francis Flaherty. MR 1138207, DOI 10.1007/978-1-4757-2201-7
- B. A. Dubrovin, A. T. Fomenko, and S. P. Novikov, Modern geometry—methods and applications. Part III, Graduate Texts in Mathematics, vol. 124, Springer-Verlag, New York, 1990. Introduction to homology theory; Translated from the Russian by Robert G. Burns. MR 1076994, DOI 10.1007/978-1-4612-4474-5
- Herbert Edelsbrunner and John L. Harer, Computational topology, American Mathematical Society, Providence, RI, 2010. An introduction. MR 2572029, DOI 10.1090/mbk/069
- Tommy Etling, Roland Herzog, Estefanía Loayza, and Gerd Wachsmuth, First and second order shape optimization based on restricted mesh deformations, SIAM J. Sci. Comput. 42 (2020), no. 2, A1200–A1225. MR 4085136, DOI 10.1137/19M1241465
- J. Gallier, Notes on convex sets, polytopes, polyhedra, combinatorial topology, Voronoi diagrams and Delaunay triangulations, Preprint, arXiv:0805.0292, 2008.
- William B. Gordon, An analytical criterion for the completeness of Riemannian manifolds, Proc. Amer. Math. Soc. 37 (1973), 221–225. MR 307112, DOI 10.1090/S0002-9939-1973-0307112-5
- Ernst Hairer, Christian Lubich, and Gerhard Wanner, Geometric numerical integration illustrated by the Störmer-Verlet method, Acta Numer. 12 (2003), 399–450. MR 2249159, DOI 10.1017/S0962492902000144
- B. Heeren, M. Rumpf, P. Schröder, M. Wardetzky, and B. Wirth, Exploring the geometry of the space of shells, Computer Graphics Forum 33 (2014), no. 5, 247–256, DOI 10.1111/cgf.12450.
- B. Heeren, M. Rumpf, M. Wardetzky, and B. Wirth, Time-discrete geodesics in the space of shells, Computer Graphics Forum 31 (2012), no. 5, 1755–1764, DOI 10.1111/j.1467-8659.2012.03180.x.
- R. Herzog and E. Loayza-Romero, A discretize-then-optimize approach to PDE-constrained shape optimization, Preprint, arXiv:2109.00076, 2021.
- Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal, Fundamentals of convex analysis, Grundlehren Text Editions, Springer-Verlag, Berlin, 2001. Abridged version of Convex analysis and minimization algorithms. I [Springer, Berlin, 1993; MR1261420 (95m:90001)] and II [ibid.; MR1295240 (95m:90002)]. MR 1865628, DOI 10.1007/978-3-642-56468-0
- D. Horak and J. Jost, Spectra of combinatorial Laplace operators on simplicial complexes, Adv. Math. 244 (2013), 303–336, DOI 10.1016/j.aim.2013.05.007.
- D. C. Kay, College Geometry: A Unified Development, CRC Press, 2011.
- David G. Kendall, Shape manifolds, Procrustean metrics, and complex projective spaces, Bull. London Math. Soc. 16 (1984), no. 2, 81–121. MR 737237, DOI 10.1112/blms/16.2.81
- M. Kilian, N. J. Mitra, and H. Pottmann, Geometric Modeling in Shape Space, ACM Transactions on Graphics (TOG), vol. 26, ACM, 2007, p. 64, DOI 10.1145/1275808.1276457.
- E. Klassen, A. Srivastava, M. Mio, and S. H. Joshi, Analysis of planar shapes using geodesic paths on shape spaces, IEEE Trans. Pattern Anal. Mach. Intell. 26 (2004), no. 3, 372–383, DOI 10.1109/TPAMI.2004.1262333.
- John M. Lee, Introduction to topological manifolds, 2nd ed., Graduate Texts in Mathematics, vol. 202, Springer, New York, 2011. MR 2766102, DOI 10.1007/978-1-4419-7940-7
- John M. Lee, Introduction to Riemannian manifolds, Graduate Texts in Mathematics, vol. 176, Springer, Cham, 2018. Second edition of [ MR1468735]. MR 3887684
- X. Liu, Y. Shi, I. Dinov, and W. Mio, A computational model of multidimensional shape, Int. J. Comput. Vis. 89 (2010), no. 1, 69–83, DOI https://doi.org/10.1007/s11263-010-0323-0.
- Peter W. Michor and David Mumford, Riemannian geometries on spaces of plane curves, J. Eur. Math. Soc. (JEMS) 8 (2006), no. 1, 1–48. MR 2201275, DOI 10.4171/JEMS/37
- M. K. Misztal, Deformable simplicial complexes, Ph.D. Thesis, Technical University of Denmark, 2010.
- Bijan Mohammadi and Olivier Pironneau, Applied shape optimization for fluids, 2nd ed., Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford, 2010. MR 2567067
- A. Paganini, Numerical shape optimization with finite elements, Ph.D. Thesis, ETH Zürich, 2016.
- Alfio Quarteroni and Alberto Valli, Numerical approximation of partial differential equations, Springer Series in Computational Mathematics, vol. 23, Springer-Verlag, Berlin, 1994. MR 1299729, DOI 10.1007/978-3-540-85268-1
- Volker H. Schulz, Martin Siebenborn, and Kathrin Welker, Efficient PDE constrained shape optimization based on Steklov-Poincaré-type metrics, SIAM J. Optim. 26 (2016), no. 4, 2800–2819. MR 3582826, DOI 10.1137/15M1029369
- J. Sokołowski and J.-P. Zolésio, Introduction to Shape Optimization, Springer, New York, 1992.
- Dragutin Svrtan and Darko Veljan, Non-Euclidean versions of some classical triangle inequalities, Forum Geom. 12 (2012), 197–209. MR 2955631
- Y.-L. Yang, Y.-J. Yang, H. Pottmann, and N. J. Mitra, Shape space exploration of constrained meshes, ACM Trans. Graph. 30 (2011), no. 6, 124, DOI https://doi.org/10.1145/2024156.2024158.
- L. Younes, Computable elastic distances between shapes, SIAM J. Appl. Math. 58 (1998), no. 2, 565–586, DOI 10.1137/S0036139995287685.
- L. Younes, Shapes and Diffeomorphisms, vol. 171, Springer, 2010.
- L. Younes, Spaces and manifolds of shapes in computer vision: an overview, Image Vis. Comput. 30 (2012), no. 6-7, 389–397, DOI https://doi.org/10.1016/j.imavis.2011.09.009.
- J.-P. Zolésio, Control of moving domains, shape stabilization and variational tube formulations, Control of Coupled Partial Differential Equations, Springer, 2007, pp. 329–382, DOI 10.1007/978-3-7643-7721-2_15.
Bibliographic Information
- Roland Herzog
- Affiliation: Interdisciplinary Center for Scientific Computing, Heidelberg University, 69120 Heidelberg, Germany
- MR Author ID: 726929
- ORCID: 0000-0003-2164-6575
- Email: roland.herzog@iwr.uni-heidelberg.de
- Estefanía Loayza-Romero
- Affiliation: Institute for Analysis and Numerics, University of Münster, 48149 Münster, Germany
- ORCID: 0000-0001-7919-9259
- Email: estefania.loayza-romero@uni-muenster.de
- Received by editor(s): January 26, 2021
- Received by editor(s) in revised form: January 9, 2022
- Published electronically: September 12, 2022
- Additional Notes: The second author was partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy EXC 2044–390685587, Mathematics Münster: Dynamics–Geometry–Structure.
- © Copyright 2022 American Mathematical Society
- Journal: Math. Comp. 92 (2023), 1-50
- MSC (2020): Primary 53Z50, 57Z25, 53C22
- DOI: https://doi.org/10.1090/mcom/3775
- MathSciNet review: 4496958