Resources on Monte Carlo Geometry Processing
Course Material: slides [keynote (1 GB), pdf (100 MB)], live recording (coming soon!), GitHub
Abstract: Accurately analyzing large amounts of geometric data is critical for many scientific and engineering applications. Techniques based on partial differential equations (PDEs) provide powerful tools for analyzing physical systems, but conventional solvers are not yet at a stage where they “just work” on problems of real-world complexity. A constant challenge is spatial discretization, which divides the domain into a high-quality volumetric mesh for PDE-based analysis. Unfortunately, this approach does not scale well to modern computer architectures, and as such, there remains a large divide between our ability to visualize and analyze the natural world.
The walk on spheres (WoS) algorithm makes a radical departure from conventional PDE solvers, by reformulating fundamental PDEs like the Poisson equation as recursive integrals that can be solved using the Monte Carlo method. Since these integrals closely resemble those in light transport, one can leverage deep knowledge from Monte Carlo rendering to build new scalable algorithms with vastly different numerical tradeoffs, such as avoiding volumetric meshing altogether.
This course, presented at the Symposium on Geometry Processing Graduate School, provides a broad overview of grid-free Monte Carlo methods for PDEs, with an emphasis on teaching the key principles of Monte Carlo, from sample generation and variance reduction to system design, by ways of WoS and its recent generalizations.
Associated Publications and Code
The course material is based on the following publications:
Monte Carlo Geometry Processing [Project, Paper, PhD thesis, Talk]
Walk on Stars: Grid-Free Monte Carlo for PDEs with Neumann Boundary Conditions [Project, Paper, Talk]
Walkin’ Robin: Walk on Stars with Robin Boundary Conditions [Project, Paper]
Grid-Free Monte Carlo for PDEs with Spatially Varying Coefficients [Project, Paper, Talk]
Boundary Value Caching for Walk on Spheres [Paper, Talk]
All solvers and geometric queries are implemented in the open-source Zombie and FCPW libraries (respectively). Also checkout the following basic code examples: WoS for Laplace, WoS for Poisson, WoSt step-by-step tutorial.
Additional Resources (will be updated regularly)
WoS relies on and connects rich concepts from Monte Carlo methods, PDEs, and stochastic differential equations: from a harmonic analysis perspective, WoS is a Monte Carlo method for solving Laplace equations, while from a random process perspective, it is an acceleration strategy for simulating Brownian motion. Here are some enjoyable reference resources on these topics:
CMU 21-387: Monte Carlo Methods and Applications [Course webpage]
Monte Carlo Methods - a special topics course [Book]
Physically Based Rendering: From Theory To Practice [Book] - Goto reference for MC rendering
Harmonic Function Theory [Book]
Partial Differential Equations by Lawrence C. Evans [Book]
Stochastic Differential Equations by Bernt Øksendal [Book]
Handbook of Brownian Motion - Facts and Formulae [Book]
Einstein’s Investigations on the Theory of Brownian Movement from 1926! [Book]
Some Continuous Monte Carlo Methods for the Dirichlet Problem [Mervin Muller’s original paper on WoS]
The Rate of Convergence of the Walk on Spheres Algorithm [Paper]
WoS has recently seen growing interest in computer graphics, as it shares many computational benefits with Monte Carlo rendering: logarithmic scaling with geometric detail, robustness, trivial parallelism, output-sensitive evaluation, and the ability to work with different geometric representations. Beyond our own work on the topic, here is a non-exhaustive list of publications on advanced/alternative WoS estimators:
Kelvin Transformations for Simulations on Infinite Domains [Project, Paper]
Coupling Conduction, Convection and Radiative Transfer in a Single Path-Space [Project, Paper]
A Monte Carlo Method for Fluid Simulation [Project, Paper]
Velocity-Based Monte Carlo Fluids [Project, Paper]
Neural Monte Carlo Fluid Simulation [Project, Paper]
A Differential Monte Carlo Solver For the Poisson Equation [Project, Paper]
Solving Inverse PDE Problems using Grid-Free Monte Carlo Estimators [Paper]
Heat Simulation on Meshless Crafted-Made Shapes [Paper]
A Practical Walk-on-Boundary Method for Boundary Value Problems [Project, Paper]
Walk on Spheres for PDE-based Path Planning [Paper]
Stochastic Computation of Barycentric Coordinates [Paper]
as well as strategies for improving efficiency and increasing applicability to more boundary representations:
A Bidirectional Formulation for Walk on Spheres [Project, Paper]
Mean Value Caching for Walk on Spheres [Paper]
Neural Caches for Monte Carlo Partial Differential Equation Solver [Project, Paper]
Solving Poisson Equations using Neural Walk-on-Spheres [Paper]
Discontinuity-Aware 2D Neural Fields [Project, Paper]
GPU-Accelerated Monte Carlo Geometry Processing for Gradient-Domain Methods [Paper]
Hierarchical Point Distance Fields [Paper]
Spelunking the deep: Guaranteed queries on neural implicit surfaces via range analysis [Project, Paper]
Ray Tracing Harmonic Functions [Project, Paper]
Also, here are a few fun educational demos, blogs and tweets:
ShaderToy demos [implicit surface, curve inflation, diffusion curves]
Blogs [demofox, javascript implementation]
Tweets [MCGP, WoSt, Variable Coefficients, Path Planning]
Course Contributors
Citation
If you want to cite this course, use the following BibTeX:
@inproceedings{Sawhney:2024:MCGP,
author = {Sawhney, Rohan and Miller, Bailey},
booktitle = {SGP 2024 Graduate School Courses},
title = {Monte Carlo Geometry Processing},
year = {2024}}
License
This tutorial is licensed under the CC BY 4.0 license.