“Differentiable Geodesic Distance for Intrinsic Minimization on Triangle Meshes”
Conference:
Type(s):
Title:
- Differentiable Geodesic Distance for Intrinsic Minimization on Triangle Meshes
Presenter(s)/Author(s):
Abstract:
We present a novel approach for the intrinsic minimization of distance-based objectives defined on triangle meshes. We demonstrate our differentiable geodesic distance framework on geodesic networks and membranes on surfaces, two-way coupling between hosting surface and embedded system, differentiable Voronoi diagrams, and efficient computation of Karcher means on complex shapes.
References:
[1]
Alexander Belyaev and Pierre-Alain Fayolle. 2020. An ADMM-based scheme for distance function approximation. Numerical Algorithms 84 (2020), 983–996.
[2]
Alexander G Belyaev and Pierre-Alain Fayolle. 2015. On variational and PDE-based distance function approximations. In Computer Graphics Forum, Vol. 34. Wiley Online Library, 104–118.
[3]
Alexander I Bobenko and Boris A Springborn. 2007. A discrete Laplace-Beltrami operator for simplicial surfaces. Discrete & Computational Geometry 38, 4 (2007), 740–756.
[4]
Prosenjit Bose, Anil Maheshwari, Chang Shu, and Stefanie Wuhrer. 2011. A survey of geodesic paths on 3D surfaces. Computational Geometry 44, 9 (2011), 486–498.
[5]
Jindong Chen and Yijie Han. 1990. Shortest paths on a polyhedron. In Proceedings of the sixth annual symposium on Computational geometry. 360–369.
[6]
Yanqing Chen, Timothy A Davis, William W Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Transactions on Mathematical Software (TOMS) 35, 3 (2008), 1–14.
[7]
Gabriel Cirio, Jorge Lopez-Moreno, David Miraut, and Miguel A Otaduy. 2014. Yarn-level simulation of woven cloth. ACM Transactions on Graphics (TOG) 33, 6 (2014), 1–11.
[8]
Gabriel Cirio, Jorge Lopez-Moreno, and Miguel A Otaduy. 2015. Efficient simulation of knitted cloth using persistent contacts. In Proceedings of the 14th ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 55–61.
[9]
Keenan Crane, Marco Livesu, Enrico Puppo, and Yipeng Qin. 2020. A Survey of Algorithms for Geodesic Paths and Distances. arXiv e-prints, Article arXiv:2007.10430 (July 2020), arXiv:2007.10430 pages. arXiv:2007.10430 [cs.GR]
[10]
Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Transactions on Graphics (TOG) 32, 5 (2013), 1–11.
[11]
Michal Edelstein, Nestor Guillen, Justin Solomon, and Mirela Ben-Chen. 2023. A Convex Optimization Framework for Regularized Geodesic Distances. In ACM SIGGRAPH 2023 Conference Proceedings (Los Angeles, CA, USA) (SIGGRAPH ’23). Association for Computing Machinery, New York, NY, USA, Article 2, 11 pages.
[12]
Ye Fan, Joshua Litven, David IW Levin, and Dinesh K Pai. 2013. Eulerian-on-lagrangian simulation. ACM Transactions on Graphics (TOG) 32, 3 (2013), 1–9.
[13]
Matthew Fisher, Boris Springborn, Alexander I Bobenko, and Peter Schroder. 2006. An algorithm for the construction of intrinsic Delaunay triangulations with applications to digital geometry processing. In ACM SIGGRAPH 2006 Courses. 69–74.
[14]
Mark Gillespie, Nicholas Sharp, and Keenan Crane. 2021. Integer coordinates for intrinsic geometry processing. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–13.
[15]
Eitan Grinspun, Anil N Hirani, Mathieu Desbrun, and Peter Schr?der. 2003. Discrete shells. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation. Citeseer, 62–67.
[16]
Ga?l Guennebaud, Beno?t Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.
[17]
Michael Hofer and Helmut Pottmann. 2004. Energy-minimizing splines in manifolds. In ACM SIGGRAPH 2004 Papers. 284–293.
[18]
Weizhen Huang, Julian Iseringhausen, Tom Kneiphof, Ziyin Qu, Chenfanfu Jiang, and Matthias B Hullin. 2020. Chemomechanical simulation of soap film flow on spherical bubbles. ACM Transactions on Graphics (TOG) 39, 4 (2020), 41–1.
[19]
Theodore Kim and David Eberle. 2020. Dynamic deformables: implementation and production practicalities. In ACM SIGGRAPH 2020 Courses. 1–182.
[20]
Ron Kimmel and James A Sethian. 1998. Computing geodesic paths on manifolds. Proceedings of the national academy of Sciences 95, 15 (1998), 8431–8435.
[21]
Yun-Jin Lee and Seung-Yong Lee. 2001. Geometric Snakes for Triangular Meshes. Journal of the Korea Computer Graphics Society 7, 3 (2001), 9–18.
[22]
Duo Li, Shinjiro Sueda, Debanga R Neog, and Dinesh K Pai. 2013. Thin skin elastodynamics. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–10.
[23]
Yue Li, Juan Montes, Bernhard Thomaszewski, and Stelian Coros. 2022. Programmable digital weaves. IEEE Robotics and Automation Letters 7, 2 (2022), 2891–2896.
[24]
Bangquan Liu, Shuangmin Chen, Shi-Qing Xin, Ying He, Zhen Liu, and Jieyu Zhao. 2017a. An optimization-driven approach for computing geodesic paths on triangle meshes. Computer-Aided Design 90 (2017), 105–112.
[25]
Hsueh-Ti Derek Liu, Mark Gillespie, Benjamin Chislett, Nicholas Sharp, Alec Jacobson, and Keenan Crane. 2023. Surface Simplification using Intrinsic Error Metrics. ACM Transactions on Graphics (TOG) 42, 4 (2023), 1–17.
[26]
Jian Liu, Shiqing Xin, Xifeng Gao, Kaihang Gao, Kai Xu, Baoquan Chen, and Changhe Tu. 2021. Computational Object-Wrapping Rope Nets. ACM Transactions on Graphics (TOG) 41, 1 (2021), 1–16.
[27]
Yong-Jin Liu, Dian Fan, Chun-Xu Xu, and Ying He. 2017b. Constructing intrinsic Delaunay triangulations from the dual of geodesic Voronoi diagrams. ACM Transactions on Graphics (TOG) 36, 2 (2017), 1–15.
[28]
Claudio Mancinelli and Enrico Puppo. 2023. Computing the Riemannian center of mass on meshes. Computer Aided Geometric Design 103 (2023), 102203.
[29]
Eder Miguel, Mathias Lepoutre, and Bernd Bickel. 2016. Computational design of stable planar-rod structures. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–11.
[30]
Joseph SB Mitchell, David M Mount, and Christos H Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (1987), 647–668.
[31]
Juan Montes, Bernhard Thomaszewski, Sudhir Mudur, and Tiberiu Popa. 2020. Computational design of skintight clothing. ACM Transactions on Graphics (TOG) 39, 4 (2020), 105–1.
[32]
William Neveu, Ivan Puhachov, Bernhard Thomaszewski, and Mikhail Bessmeltsev. 2022. Stability-aware simplification of curve networks. In ACM SIGGRAPH 2022 Conference Proceedings. 1–9.
[33]
Jorge Nocedal and Stephen J Wright. 1999. Numerical optimization. Springer.
[34]
Bo Pang, Zhongtian Zheng, Guoping Wang, and Peng-Shuai Wang. 2023. Learning the geodesic embedding with graph neural networks. ACM Transactions on Graphics (TOG) 42, 6 (2023), 1–12.
[35]
Jes?s P?rez, Bernhard Thomaszewski, Stelian Coros, Bernd Bickel, Jos? A Canabal, Robert Sumner, and Miguel A Otaduy. 2015. Design and fabrication of flexible rod meshes. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–12.
[36]
Gabriel Peyr?, Mickael P?chaud, Renaud Keriven, Laurent D Cohen, et al. 2010. Geodesic methods in computer vision and graphics. Foundations and Trends? in Computer Graphics and Vision 5, 3–4 (2010), 197–397.
[37]
Konrad Polthier and Markus Schmies. 2006. Straightest geodesics on polyhedral surfaces. In ACM SIGGRAPH 2006 Courses. 30–38.
[38]
Yipeng Qin, Xiaoguang Han, Hongchuan Yu, Yizhou Yu, and Jianjun Zhang. 2016. Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–13.
[39]
Yingying Ren, Julian Panetta, Tian Chen, Florin Isvoranu, Samuel Poincloux, Christopher Brandt, Alison Martin, and Mark Pauly. 2021. 3D weaving with curved ribbons. ACM Transactions on Graphics 40, ARTICLE (2021), 127.
[40]
Christian Schumacher, Steve Marschner, Markus Gross, and Bernhard Thomaszewski. 2018. Mechanical characterization of structured sheet materials. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–15.
[41]
Nicholas Sharp et al. 2019b. Polyscope. www.polyscope.run.
[42]
Nicholas Sharp and Keenan Crane. 2020a. A laplacian for nonmanifold triangle meshes. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 69–80.
[43]
Nicholas Sharp and Keenan Crane. 2020b. You can find geodesic paths in triangle meshes by just flipping edges. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–15.
[44]
Nicholas Sharp, Keenan Crane, et al. 2019a. GeometryCentral: A modern C++ library of data structures and algorithms for geometry processing. https://geometry-central.net/. (2019).
[45]
Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019c. Navigating Intrinsic Triangulations. ACM Trans. Graph. 38, 4 (2019).
[46]
Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019d. The vector heat method. ACM Transactions on Graphics (TOG) 38, 3 (2019), 1–19.
[47]
Jack Sherman and Winifred J Morrison. 1950. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. The Annals of Mathematical Statistics 21, 1 (1950), 124–127.
[48]
Shinjiro Sueda, Garrett L Jones, David IW Levin, and Dinesh K Pai. 2011. Large-scale dynamic simulation of highly constrained strands. In ACM SIGGRAPH 2011 papers. 1–10.
[49]
Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J Gortler, and Hugues Hoppe. 2005. Fast exact and approximate geodesics on meshes. ACM transactions on graphics (TOG) 24, 3 (2005), 553–560.
[50]
Philip Trettner, David Bommes, and Leif Kobbelt. 2021. Geodesic distance computation via virtual source propagation. In Computer graphics forum, Vol. 40. Wiley Online Library, 247–260.
[51]
Johannes Wallner, Helmut Pottmann, and Michael Hofer. 2005. Fair curve networks in nonlinear geometries. In ACM SIGGRAPH 2005 Sketches. 32–es.
[52]
Nicholas J Weidner, Kyle Piddington, David IW Levin, and Shinjiro Sueda. 2018. Eulerian-on-lagrangian cloth simulation. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–11.
[53]
Shiqing Xin, Pengfei Wang, Rui Xu, Dongming Yan, Shuangmin Chen, Wenping Wang, Caiming Zhang, and Changhe Tu. 2022. SurfaceVoronoi: Efficiently Computing Voronoi Diagrams Over Mesh Surfaces with Arbitrary Distance Solvers. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1–12.
[54]
Shi-Qing Xin, Shuang-Min Chen, Ying He, Guo-Jin Wang, Xianfeng Gu, and Hong Qin. 2011. Isotropic mesh simplification by evolving the geodesic delaunay triangulation. In 2011 Eighth International Symposium on Voronoi Diagrams in Science and Engineering. IEEE, 39–47.
[55]
Bowen Yang, William Corse, Jiecong Lu, Joshuah Wolper, and Chen-Fanfu Jiang. 2019. Real-time fluid simulation on the surface of a sphere. Proceedings of the ACM on Computer Graphics and Interactive Techniques 2, 1 (2019), 1–17.
[56]
Xiang Ying, Xiaoning Wang, and Ying He. 2013. Saddle vertex graph (SVG) a novel solution to the discrete geodesic problem. ACM Transactions on Graphics (TOG) 32, 6 (2013), 1–12.
[57]
Jonas Zehnder, Stelian Coros, and Bernhard Thomaszewski. 2016. Designing structurally-sound ornamental curve networks. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–10.
