“A Framework for Solving Parabolic Partial Differential Equations on Discrete Domains” by Silva, Stein and Solomon
Conference:
Type(s):
Title:
- A Framework for Solving Parabolic Partial Differential Equations on Discrete Domains
Presenter(s)/Author(s):
Abstract:
We present a method to solve a class of parabolic PDE on triangle mesh surfaces. Our method leverages a splitting integrator combined with a convex optimization step. We apply our method on a number of linear and nonlinear PDE that appear in diffusion and front propagation tasks in geometry processing.
References:
[1]
T. Aumentado-Armstrong and K. Siddiqi. 2017. Stochastic heat kernel estimation on sampled manifolds. Comput. Graph. Forum 36, 5 (2017), 131?138.
[2]
Guy Barles. 2013. An Introduction to the Theory of Viscosity Solutions for First-Order Hamilton?Jacobi Equations and Applications. Springer, Berlin, 49?109.
[3]
R. G. Barrera, G. A. Estevez, and J. Giraldo. 1985. Vector spherical harmonics and their application to magnetostatics. European Journal of Physics 6, 4 (1985), 287?294.
[4]
Alexander Belyaev and Pierre-Alain Fayolle. 2020. An ADMM-based scheme for distance function approximation. Numer. Algorithms 84, 3 (2020), 983?996.
[5]
Alexander G. Belyaev and Pierre-Alain Fayolle. 2015. On variational and PDE-based distance function approximations. Computer Graphics Forum 34, 8 (2015), 104?118.
[6]
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyr?. 2015. Iterative Bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing 37, 2 (2015), A1111?A1138.
[7]
Alexander I. Bobenko and Peter Schr?der. 2005. Discrete Willmore flow. Eurographics Symposium on Geometry Processing (2005).
[8]
Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Levy. 2010. Polygon Mesh Processing. AK Peters / CRC Press.
[9]
Zhili Chen, Renguo Feng, and Huamin Wang. 2013. Modeling friction and air effects between cloth and deformable bodies. ACM Trans. Graph. 32, 4, Article 88 (2013).
[10]
Michael G. Crandall, Hitoshi Ishii, and Pierre-Louis Lions. 1992. User?s guide to viscosity solutions of second order partial differential equations. Bull. Amer. Math. Soc.27 (1992), 1?67.
[11]
Michael G. Crandall and Pierre-Louis Lions. 1983. Viscosity solutions of Hamilton-Jacobi equations. Trans. Amer. Math. Soc. 277, 1 (1983), 1?42.
[12]
M. G. Crandall and P. L. Lions. 1984. Two approximations of solutions of Hamilton-Jacobi equations. Math. Comp. 43, 167 (1984), 1?19.
[13]
Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Trans. Graph. 32, 5 (2013), 1?11.
[14]
Keenan Crane. 2013. Spot. https://www.cs.cmu.edu/kmcrane/Projects/ModelRepository/
[15]
Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems 26 (2013).
[16]
Mathieu Desbrun, Mark Meyer, Peter Schr?der, and Alan H. Barr. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques, 317?324.
[17]
Haixia Du and Hong Qin. 2004. Medial axis extraction and shape manipulation of solid objects using parabolic PDEs. In Proceedings of the Ninth ACM Symposium on Solid Modeling and Applications. Eurographics Association, Goslar, DEU, 25?35.
[18]
Ye Duan, Liu Yang, Hong Qin, and Dimitris Samaras. 2004. Shape reconstruction from 3D and 2D data using PDE-based deformable surfaces. In Computer Vision – ECCV 2004. Springer, Berlin, 238?251.
[19]
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. Association for Computing Machinery, New York, NY, USA, Article 2, 11 pages.
[20]
Sharif Elcott, Yiying Tong, Eva Kanso, Peter Schr?der, and Mathieu Desbrun. 2007. Stable, circulation-preserving, simplicial fluids. ACM Trans. Graph. 26, 1 (Jan.2007), 4?es.
[21]
Lawrence C. Evans. 2010. Partial Differential Equations (second ed.). Graduate Studies in Mathematics, Vol. 19. American Mathematical Society, Providence, RI, USA.
[22]
W. H. Fleming and P. E. Souganidis. 1989. On the existence of value functions of two-player, zero-sum stochastic differential games. Indiana Univ. Math. J. 38, 2 (1989), 293?314.
[23]
Sergei K. Godunov and I. Bohachevsky. 1959. Finite difference method for numerical computation of discontinuous solutions of the equations of fluid dynamics. Matemati?eskij sbornik 47(89), 3 (1959), 271?306.
[24]
Michael Grant and Stephen Boyd. 2008. Graph implementations for nonsmooth convex programs. In Recent Advances in Learning and Control, V. Blondel, S. Boyd, and H. Kimura (Eds.). Springer-Verlag Limited, Berlin, 95?110. http://stanford.edu/boyd/graph_dcp.html
[25]
Michael Grant and Stephen Boyd. 2014. CVX: Matlab Software for Disciplined Convex Programming, version 2.1. http://cvxr.com/cvx
[26]
Haotian Gu, Jack Xin, and Zhiwen Zhang. 2021. Error estimates for a POD method for solving viscous g-equations in incompressible cellular flows. SIAM Journal on Scientific Computing 43, 1 (2021), A636?A662.
[27]
Jeong-Mo Hong, Tamar Shinar, and Ronald Fedkiw. 2007. Wrinkled flames and cellular patterns. ACM Trans. Graph. 26, 3 (2007), 47?52.
[28]
Hughes Hoppe. 1994. Fandisk. https://github.com/alecjacobson/common-3d-test-models
[29]
Guillaume Huguet, Alexander Tong, Mar?a Ramos Zapatero, Christopher J. Tape, Guy Wolf, and Smita Krishnaswamy. 2023. Geodesic Sinkhorn for fast and accurate optimal transport on manifolds. (2023).
[30]
Hitoshi Ishii. 1987. Perron?s method for Hamilton-Jacobi equations. Duke Mathematical Journal 55, 2 (1987), 369?384.
[31]
Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/
[32]
J?rgen Jost. 2011. The Laplace Operator and Harmonic Differential Forms. Springer, Berlin, Chapter 3, 89?131.
[33]
Tosio Kato. 1974. On the Trotter-Lie product formula. Proceedings of the Japan Academy 50, 9 (1974), 694?698.
[34]
Stanford University Computer Graphics Laboratory. 1994. Stanford Bunny. https://graphics.stanford.edu/data/3Dscanrep/
[35]
T. A. Leatham, D. M. Paganin, and K. S. Morgan. 2022. X-ray dark-field and phase retrieval without optics, via the Fokker-Planck equation. IEEE Transactions on Medical Imaging 42, 6 (2022), 1681?1695.
[36]
Yu-Yu Liu, Jack Xin, and Yifeng Yu. 2013. A numerical study of turbulent flame speeds of curvature and strain G-equations in cellular flows. Physica D: Nonlinear Phenomena 243, 1 (2013), 20?31.
[37]
Christian L?onard. 2014. A survey of the Schr?dinger problem and some of its connections with optimal transport. Discrete and Continuous Dynamical Systems 34, 4 (2014), 1533?1574.
[38]
Gury Ivanovich Marchuk. 1988. Splitting methods. Nauka, Moscow, (1988), 264.
[39]
Andrei Medved, Riley Davis, and Paula A. Vasquez. 2020. Understanding fluid dynamics from Langevin and Fokker?Planck equations. Fluids 5, 1, Article 40 (2020).
[40]
Duc Quang Nguyen, Ronald Fedkiw, and Henrik Wann Jensen. 2002. Physically based modeling and animation of fire. ACM Trans. Graph. 21, 3 (2002), 721?728.
[41]
Michael B. Nielsen, Morten Bojsen-Hansen, Konstantinos Stamatelos, and Robert Bridson. 2022. Physics-based combustion simulation. ACM Trans. Graph. 41, 5, Article 176 (2022), 21 pages.
[42]
James F. O?Brien, Adam W. Bargteil, and Jessica K. Hodgins. 2002. Graphical modeling and animation of ductile fracture. ACM Trans. Graph. 21, 3 (2002), 291?294.
[43]
Stanley Osher and James A. Sethian. 1988. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79, 1 (1988), 12?49.
[44]
Shige Peng and Detang Zhou. 2008. Maximum principle for viscosity solutions on Riemannian manifolds. arXiv e-prints, Article arXiv:0806.4768 (June2008), arXiv:0806.4768 pages. DOI:arxiv:0806.4768.
[45]
James A. Sethian. 1985. Curvature and the evolution of fronts. Communications in Mathematical Physics 101, 4 (1985), 487?499.
[46]
Bogdan Smolka and Konrad W. Wojciechowski. 1997. Contrast enhancement of badly illuminated images based on Gibbs distribution and random walk model. In Computer Analysis of Images and Patterns. Springer, Berlin, 271?278.
[47]
Justin Solomon, Fernando de Goes, Gabriel Peyr?, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Trans. Graph. 34, 4, Article 66 (2015), 11 pages.
[48]
B. P. Sommeijer, L. F. Shampine, and J. G. Verwer. 1998. RKC: An explicit solver for parabolic PDEs. J. Comput. Appl. Math. 88, 2 (1998), 315?326.
[49]
Gilbert Strang. 1968. On the construction and comparison of different splitting schemes. SIAM J. Numer. Anal. 5, 3 (1968), 506?517.
[50]
K. C. Toh, M. J. Todd, and R. H. T?t?nc?. 1999. SDPT3 ? A Matlab software package for semidefinite programming, Version 1.3. Optimization Methods and Software 11, 1?4 (1999), 545?581.
[51]
H. F. Trotter. 1959. On the product of semi-groups of operators. Proc. Amer. Math. Soc. 10, 4 (1959), 545?551.
[52]
Reha H. T?t?nc?, Kim-Chuan Toh, and Michael J. Todd. 2003. Solving semidefinite-quadratic-linear programs using SDPT3. Mathematical Programming 95, 2 (2003), 189?217.
[53]
C?dric Villani. 2003. Topics in Optimal Transportation. Graduate Studies in Mathematics, Vol. 58. American Mathematical Society, Providence, RI, USA.
[54]
F. A. Williams. 1985. Turbulent combustion. In The Mathematics of Combustion, John D. Buckmaster (Ed.). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 97?131.
[55]
Andrew Witkin and Michael Kass. 1991. Reaction-diffusion textures. In Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques. Association for Computing Machinery, New York, NY, USA, 299?308.
[56]
Guoliang Xu, Qing Pan, and Chandrajit L. Bajaj. 2006. Discrete surface modelling using partial differential equations. Computer Aided Geometric Design 23, 2 (2006), 125?145.
[57]
YahooJAPAN. 2013. Koala. https://www.thingiverse.com/thing:182225
[58]
Jue Yan and Stanley Osher. 2011. A local discontinuous Galerkin method for directly solving Hamilton?Jacobi equations. J. Comput. Phys. 230, 1 (2011), 232?244.
