skip to main content
research-article
Open access

Kelvin transformations for simulations on infinite domains

Published: 19 July 2021 Publication History

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.

Supplementary Material

VTT File (3450626.3459809.vtt)
ZIP File (a97-nabizadeh.zip)
a97-nabizadeh.zip
MP4 File (a97-nabizadeh.mp4)
MP4 File (3450626.3459809.mp4)
Presentation.

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.
[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.
[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.
[4]
Jean-Pierre Berenger. 1994. A perfectly matched layer for the absorption of electromagnetic waves. Journal of computational physics 114, 2 (1994), 185--200.
[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.
[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.
[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.
[8]
Robert Bridson. 2015. Fluid simulation for computer graphics. CRC press.
[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.
[10]
CADENS. 2015. Computational Science and Data Visualization take the spotlike in new Solar Superstorms documentary. https://www.ncsa.illinois.edu/news/story/solar_superstorms
[11]
Albert Chern. 2019. A Reflectionless discrete perfectly matched layer. J. Comput. Phys. 381 (2019), 91--109.
[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.
[13]
Keenan Crane. 2019. The n-dimensional cotangent formula. Online note (2019). https://www.cs.cmu.edu/~kmcrane/Projects/Other/nDCotanFormula.pdf
[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.
[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.
[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.
[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.
[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.
[19]
Sam Freeland and Robert Bentley. 2000. SolarSoft. Encyclopedia of Astronomy and Astrophysics (2000), 3390.
[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.
[21]
Dan Givoli. 1992. Numerical methods for problems in infinite domains. Elsevier.
[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.
[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.
[24]
Gerald Gold. 2020. On the Kelvin Transformation in Finite Difference Implementations. Electronics 9, 3 (2020), 442.
[25]
Leslie Greengard and Vladimir Rokhlin. 1987. A fast algorithm for particle simulations. Journal of computational physics 73, 2 (1987), 325--348.
[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.
[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.
[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.
[29]
Doug L James. 2016. Physically based sound for computer animation and virtual environments. In ACM SIGGRAPH 2016 Courses. 22:1--22:8.
[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.
[31]
Oliver Dimon Kellogg. 1953. Foundations of Potential Theory. Vol. 31. Courier Corporation.
[32]
Stephen Kirkup. 2019. The boundary element method in acoustics: A survey. Applied Sciences 9, 8 (2019), 1642.
[33]
Prem K Kythe. 2020. An introduction to boundary element methods. CRC press.
[34]
William McLean. 2000. Strongly elliptic systems and boundary integral equations. Cambridge university press.
[35]
Norman Meyers. 1963. An expansion about infinity for solutions of linear elliptic equations. Journal of Mathematics and Mechanics 12, 2 (1963), 247--264.
[36]
Mervin E Muller. 1956. Some continuous Monte Carlo methods for the Dirichlet problem. The Annals of Mathematical Statistics 27, 3 (1956), 569--589.
[37]
NASA Scientific Visualization Studio. 2018. The Dynamic Solar Magnetic Field with Introduction. https://svs.gsfc.nasa.gov/4623
[38]
NASA Solar Dynamics Observatory. 2020. NASA AIA/HMI Data. https://sdo.gsfc.nasa.gov/data/aiahmi/
[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.
[40]
Jonathan Novak. 2014. Pólya's random walk theorem. The American Mathematical Monthly 121, 8 (2014), 711--716.
[41]
Paul William Partridge, Carlos Alberto Brebbia, et al. 2012. Dual reciprocity boundary element method. Springer Science & Business Media.
[42]
Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically based rendering: From theory to implementation. Morgan Kaufmann.
[43]
Eric Priest. 2014. Magnetohydrodynamics of the Sun. Cambridge University Press.
[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.
[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.
[46]
Stefan A Sauter and Christoph Schwab. 2010. Boundary element methods. In Boundary Element Methods. Springer, 183--287.
[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.
[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.
[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.
[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.
[51]
Elke Spindler. 2016. Second kind single-trace boundary integral formulations for scattering at composite objects. Ph.D. Dissertation. ETH Zurich.
[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.
[53]
Alexey Stomakhin and Andrew Selle. 2017. Fluxed animated boundary method. ACM Transactions on Graphics (TOG) 36, 4 (2017), 68:1--68:8.
[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.
[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.
[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.
[57]
Semyon V Tsynkov. 1998. Numerical solution of problems on unbounded domains. A review. Applied Numerical Mathematics 27, 4 (1998), 465--532.
[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.
[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.
[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.
[61]
Steffen Weißmann and Ulrich Pinkall. 2010. Filament-based smoke with vortex shedding and variational reconnection. ACM Transactions on Graphics (TOG) 29 (2010).
[62]
Eric W Weisstein. 2000. Pólya's random walk constants. From MathWorld-A Wolfram Web Resource (2000). https://mathworld.wolfram.com/PolyasRandomWalkConstants.html
[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.
[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.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 40, Issue 4
August 2021
2170 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/3450626
Issue’s Table of Contents
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 July 2021
Published in TOG Volume 40, Issue 4

Check for updates

Author Tags

  1. Helmholtz equation
  2. Kelvin transform
  3. Möbius transform
  4. Monte Carlo method
  5. Poisson equation
  6. infinite domain

Qualifiers

  • Research-article

Funding Sources

  • Ronald L. Graham Chair
  • UC San Diego Center for Visual Computing

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)285
  • Downloads (Last 6 weeks)30
Reflects downloads up to 09 Jan 2025

Other Metrics

Citations

Cited By

View all

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Full Access

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media