“Kelvin transformations for simulations on infinite domains” by Nabizadeh, Ramamoorthi and Chern

  • ©Mohammad Sina Nabizadeh, Ravi Ramamoorthi, and Albert Chern

Conference:


Type:


Title:

    Kelvin transformations for simulations on infinite domains

Presenter(s)/Author(s):



Abstract:


    Solving partial differential equations (PDEs) on infinite domains has been a challenging task in physical simulations and geometry processing. We introduce a general technique to transform a PDE problem on an unbounded domain to a PDE problem on a bounded domain. Our method uses the Kelvin Transform, which essentially inverts the distance from the origin. However, naive application of this coordinate mapping can still result in a singularity at the origin in the transformed domain. We show that by factoring the desired solution into the product of an analytically known (asymptotic) component and another function to solve for, the problem can be made continuous and compact, with solutions significantly more efficient and well-conditioned than traditional finite element and Monte Carlo numerical PDE methods on stretched coordinates. Specifically, we show that every Poisson or Laplace equation on an infinite domain is transformed to another Poisson (Laplace) equation on a compact region. In other words, any existing Poisson solver on a bounded domain is readily an infinite domain Poisson solver after being wrapped by our transformation. We demonstrate the integration of our method with finite difference and Monte Carlo PDE solvers, with applications in the fluid pressure solve and simulating electromagnetism, including visualizations of the solar magnetic field. Our transformation technique also applies to the Helmholtz equation whose solutions oscillate out to infinity. After the transformation, the Helmholtz equation becomes a tractable equation on a bounded domain without infinite oscillation. To our knowledge, this is the first time that the Helmholtz equation on an infinite domain is solved on a bounded grid without requiring an artificial absorbing boundary condition.

References:


    1. Martin D Altschuler and Gordon Newkirk. 1969. Magnetic fields and the structure of the solar corona. Solar Physics 9, 1 (1969), 131–149.Google ScholarCross Ref
    2. Gavin Barill, Neil G Dickson, Ryan Schmidt, David IW Levin, and Alec Jacobson. 2018. Fast winding numbers for soups and clouds. ACM Transactions on Graphics (TOG) 37, 4 (2018), 43:1–43:12.Google ScholarDigital Library
    3. Carl M Bender and Steven A Orszag. 2013. Advanced mathematical methods for scientists and engineers I: Asymptotic methods and perturbation theory. Springer Science & Business Media.Google Scholar
    4. Jean-Pierre Berenger. 1994. A perfectly matched layer for the absorption of electromagnetic waves. Journal of computational physics 114, 2 (1994), 185–200.Google ScholarDigital Library
    5. Mikhail Bessmeltsev and Justin Solomon. 2019. Vectorization of line drawings via polyvector fields. ACM Transactions on Graphics (TOG) 38, 1 (2019), 9:1–9:12.Google ScholarDigital Library
    6. Morten Bojsen-Hansen and Chris Wojtan. 2016. Generalized non-reflecting boundaries for fluid re-simulation. ACM Transactions on Graphics (TOG) 35, 4 (2016), 96:1–96:7.Google ScholarDigital Library
    7. Kalina Borkiewicz, AJ Christensen, Drew Berry, Christopher Fluke, Greg Shirah, and Kel Elkins. 2019. Cinematic Scientific Visualization: The Art of Communicating Science. In SIGGRAPH Asia 2019 Courses. ACM Press, Article 107.Google Scholar
    8. Robert Bridson. 2015. Fluid simulation for computer graphics. CRC press.Google ScholarDigital Library
    9. Tyson Brochu, Todd Keeler, and Robert Bridson. 2012. Linear-time smoke animation with vortex sheet meshes. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Citeseer, 87–95.Google Scholar
    10. CADENS. 2015. Computational Science and Data Visualization take the spotlike in new Solar Superstorms documentary. https://www.ncsa.illinois.edu/news/story/solar_superstormsGoogle Scholar
    11. Albert Chern. 2019. A Reflectionless discrete perfectly matched layer. J. Comput. Phys. 381 (2019), 91–109.Google ScholarDigital Library
    12. Xavier Claeys, Ralf Hiptmair, and Elke Spindler. 2017. Second kind boundary integral equation for multi-subdomain diffusion problems. Advances in Computational Mathematics 43, 5 (2017), 1075–1101.Google ScholarDigital Library
    13. Keenan Crane. 2019. The n-dimensional cotangent formula. Online note (2019). https://www.cs.cmu.edu/~kmcrane/Projects/Other/nDCotanFormula.pdfGoogle Scholar
    14. Fang Da, Christopher Batty, Chris Wojtan, and Eitan Grinspun. 2015. Double bubbles sans toil and trouble: Discrete circulation-preserving vortex sheets for soap films and foams. ACM Transactions on Graphics (TOG) 34, 4 (2015), 149:1–149:9.Google ScholarDigital Library
    15. Fang Da, David Hahn, Christopher Batty, Chris Wojtan, and Eitan Grinspun. 2016. Surface-only liquids. ACM Transactions on Graphics (TOG) 35, 4 (2016), 78:1–78:12.Google ScholarDigital Library
    16. Björn Engquist and Andrew Majda. 1977. Absorbing boundary conditions for numerical simulation of waves. Proceedings of the National Academy of Sciences 74, 5 (1977), 1765–1766.Google ScholarCross Ref
    17. Sergey Ermakov, Vladimir Viktorovich Nekrutkin, and Aleksandr Stepanovich Sipin. 1989. Random processes for classical equations of mathematical physics. Vol. 34. Springer Science & Business Media.Google Scholar
    18. Robert Finn and David Gilbarg. 1957. Three-dimensional subsonic flows, and asymptotic estimates for elliptic partial differential equations. Acta Mathematica 98 (1957), 265–296.Google ScholarCross Ref
    19. Sam Freeland and Robert Bentley. 2000. SolarSoft. Encyclopedia of Astronomy and Astrophysics (2000), 3390.Google Scholar
    20. Frederic Gibou, Ronald P Fedkiw, Li-Tien Cheng, and Myungjoo Kang. 2002. A second-order-accurate symmetric discretization of the Poisson equation on irregular domains. J. Comput. Phys. 176, 1 (2002), 205–227.Google ScholarDigital Library
    21. Dan Givoli. 1992. Numerical methods for problems in infinite domains. Elsevier.Google Scholar
    22. Dan Givoli and Joseph B Keller. 1989. A finite element method for large domains. Computer Methods in Applied Mechanics and Engineering 76, 1 (1989), 41–66.Google ScholarDigital Library
    23. Abhinav Golas, Rahul Narain, Jason Sewall, Pavel Krajcevski, Pradeep Dubey, and Ming Lin. 2012. Large-scale fluid simulation using velocity-vorticity domain decomposition. ACM Transactions on Graphics (TOG) 31, 6 (2012), 148:1–148:9.Google ScholarDigital Library
    24. Gerald Gold. 2020. On the Kelvin Transformation in Finite Difference Implementations. Electronics 9, 3 (2020), 442.Google ScholarCross Ref
    25. Leslie Greengard and Vladimir Rokhlin. 1987. A fast algorithm for particle simulations. Journal of computational physics 73, 2 (1987), 325–348.Google ScholarDigital Library
    26. Chester E Grosch and Steven A Orszag. 1977. Numerical solution of problems in unbounded regions: coordinate transforms. J. Comput. Phys. 25, 3 (1977), 273–295.Google ScholarCross Ref
    27. Marcus D Hanwell, Donald E Curtis, David C Lonie, Tim Vandermeersch, Eva Zurek, and Geoffrey R Hutchison. 2012. Avogadro: an advanced semantic chemical editor, visualization, and analysis platform. Journal of cheminformatics 4, 1 (2012), 17:1–17:17.Google ScholarCross Ref
    28. Isaac Harari and Thomas JR Hughes. 1992. A cost comparison of boundary element and finite element methods for problems of time-harmonic acoustics. Computer Methods in Applied Mechanics and Engineering 97, 1 (1992), 77–102.Google ScholarDigital Library
    29. Doug L James. 2016. Physically based sound for computer animation and virtual environments. In ACM SIGGRAPH 2016 Courses. 22:1–22:8.Google ScholarDigital Library
    30. Doug L James, Jernej Barbič, and Dinesh K Pai. 2006. Precomputed acoustic transfer: output-sensitive, accurate sound generation for geometrically complex vibration sources. ACM Transactions on Graphics (TOG) 25, 3 (2006), 987–995.Google ScholarDigital Library
    31. Oliver Dimon Kellogg. 1953. Foundations of Potential Theory. Vol. 31. Courier Corporation.Google Scholar
    32. Stephen Kirkup. 2019. The boundary element method in acoustics: A survey. Applied Sciences 9, 8 (2019), 1642.Google ScholarCross Ref
    33. Prem K Kythe. 2020. An introduction to boundary element methods. CRC press.Google Scholar
    34. William McLean. 2000. Strongly elliptic systems and boundary integral equations. Cambridge university press.Google Scholar
    35. Norman Meyers. 1963. An expansion about infinity for solutions of linear elliptic equations. Journal of Mathematics and Mechanics 12, 2 (1963), 247–264.Google Scholar
    36. Mervin E Muller. 1956. Some continuous Monte Carlo methods for the Dirichlet problem. The Annals of Mathematical Statistics 27, 3 (1956), 569–589.Google ScholarCross Ref
    37. NASA Scientific Visualization Studio. 2018. The Dynamic Solar Magnetic Field with Introduction. https://svs.gsfc.nasa.gov/4623Google Scholar
    38. NASA Solar Dynamics Observatory. 2020. NASA AIA/HMI Data. https://sdo.gsfc.nasa.gov/data/aiahmi/Google Scholar
    39. Michael B Nielsen and Robert Bridson. 2011. Guide shapes for high resolution naturalistic liquid simulation. ACM Transactions on Graphics (TOG) 30, 4 (2011), 83:1–83:12.Google ScholarDigital Library
    40. Jonathan Novak. 2014. Pólya’s random walk theorem. The American Mathematical Monthly 121, 8 (2014), 711–716.Google ScholarCross Ref
    41. Paul William Partridge, Carlos Alberto Brebbia, et al. 2012. Dual reciprocity boundary element method. Springer Science & Business Media.Google Scholar
    42. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically based rendering: From theory to implementation. Morgan Kaufmann.Google Scholar
    43. Eric Priest. 2014. Magnetohydrodynamics of the Sun. Cambridge University Press.Google Scholar
    44. M Reali, G Dassie, and V Pennati. 1984. Solution of the two-dimensional exterior Laplace problem by a general finite difference method via inversion transformation. In Numerical methods for transient and coupled problems: proceedings of an International Conference held in Venice, Italy on July 9th-13th, 1984. Pine Ridge Press, 447.Google Scholar
    45. Syuhei Sato, Yoshinori Dobashi, and Tomoyuki Nishita. 2018. Editing fluid animation using flow interpolation. ACM Transactions on Graphics (TOG) 37, 5 (2018), 173:1–173:12.Google ScholarDigital Library
    46. Stefan A Sauter and Christoph Schwab. 2010. Boundary element methods. In Boundary Element Methods. Springer, 183–287.Google Scholar
    47. Rohan Sawhney and Keenan Crane. 2020. Monte Carlo geometry processing: a grid-free approach to PDE-based methods on volumetric domains. ACM Transactions on Graphics (TOG) 39, 4 (2020), 123:1–123:18.Google ScholarDigital Library
    48. Camille Schreck, Christian Hafner, and Chris Wojtan. 2019. Fundamental solutions for water wave animation. ACM Transactions on Graphics (TOG) 38, 4 (2019), 130:1–130:14.Google ScholarDigital Library
    49. Andreas Söderström, Matts Karlsson, and Ken Museth. 2010. A PML-based nonreflective boundary for free surface fluid animation. ACM Transactions on Graphics (TOG) 29, 5 (2010), 136:1–136:17.Google ScholarDigital Library
    50. Justin Solomon, Amir Vaxman, and David Bommes. 2017. Boundary element octahedral fields in volumes. ACM Transactions on Graphics (TOG) 36, 4 (2017), 114b:1–114b:16.Google ScholarDigital Library
    51. Elke Spindler. 2016. Second kind single-trace boundary integral formulations for scattering at composite objects. Ph.D. Dissertation. ETH Zurich.Google Scholar
    52. Oded Stein, Eitan Grinspun, Max Wardetzky, and Alec Jacobson. 2018. Natural boundary conditions for smoothing in geometry processing. ACM Transactions on Graphics (TOG) 37, 2 (2018), 23:1–23:13.Google ScholarDigital Library
    53. Alexey Stomakhin and Andrew Selle. 2017. Fluxed animated boundary method. ACM Transactions on Graphics (TOG) 36, 4 (2017), 68:1–68:8.Google ScholarDigital Library
    54. William Thomson. 1845. Extrait d’une Lettre de M. William Thomson à M. Liouville: Electric Images. Journal de mathématiques pures et appliquées (1845), 364–367.Google Scholar
    55. William Thomson. 1872. Chapter XIV – Electric Images – Extrait d’une Lettre de M. William Thomson à M. Liouville. In Reprint of papers on electrostatics and magnetism. Macmillan & Company, 144 — 177.Google Scholar
    56. Nils Thürey, Ulrich Rüde, and Marc Stamminger. 2006. Animation of open water phenomena with coupled shallow water and free surface simulations. In Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation. 157–164.Google ScholarDigital Library
    57. Semyon V Tsynkov. 1998. Numerical solution of problems on unbounded domains. A review. Applied Numerical Mathematics 27, 4 (1998), 465–532.Google ScholarDigital Library
    58. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional field synthesis, design, and processing. Computer Graphics Forum 35, 2 (2016), 545–572.Google ScholarCross Ref
    59. Ryan Viertel and Braxton Osting. 2019. An approach to quad meshing based on harmonic cross-valued maps and the Ginzburg-Landau theory. SIAM Journal on Scientific Computing 41, 1 (2019), A452–A479.Google ScholarDigital Library
    60. Jui-Hsien Wang, Ante Qu, Timothy R Langlois, and Doug L James. 2018. Toward wave-based sound synthesis for computer animation. ACM Transactions on Graphics (TOG) 37, 4 (2018), 109:1–109:16.Google ScholarDigital Library
    61. Steffen Weißmann and Ulrich Pinkall. 2010. Filament-based smoke with vortex shedding and variational reconnection. ACM Transactions on Graphics (TOG) 29 (2010).Google Scholar
    62. Eric W Weisstein. 2000. Pólya’s random walk constants. From MathWorld-A Wolfram Web Resource (2000). https://mathworld.wolfram.com/PolyasRandomWalkConstants.htmlGoogle Scholar
    63. Xinxin Zhang and Robert Bridson. 2014. A PPPM fast summation method for fluids and beyond. ACM Transactions on Graphics (TOG) 33, 6 (2014), 206:1–206:11.Google ScholarDigital Library
    64. Xinxin Zhang, Robert Bridson, and Chen Greif. 2015. Restoring the missing vorticity in advection-projection fluid solvers. ACM Transactions on Graphics (TOG) 34, 4 (2015), 52:1–52:8.Google ScholarDigital Library


ACM Digital Library Publication:



Overview Page: