Toward General-Purpose Monte Carlo PDE Solvers for Graphics Applications
| dc.contributor.author | Sugimoto, Ryusuke | |
| dc.date.accessioned | 2025-11-13T08:10:48Z | |
| dc.date.available | 2025-11-13T08:10:48Z | |
| dc.date.issued | 2025-09-22 | |
| dc.description.abstract | This thesis develops novel Monte Carlo methods for solving a wide range of partial differential equations (PDEs) relevant to computer graphics. While traditional discretization-based approaches efficiently compute global solutions, they often require expensive global solves even when only local evaluations are needed, and can struggle with complex or fine-scale geometries. Monte Carlo methods based on the classical Walk on Spheres (WoS) approach [Muller 1956] offer pointwise evaluation with strong geometric robustness, but in practice, their application has been largely limited to interior Dirichlet problems in volumetric domains. We significantly broaden this scope by designing versatile Monte Carlo solvers that handle a diverse set of PDEs and boundary conditions, validated through comprehensive experimental results. First, we introduce the Walk on Boundary (WoB) method [Sabelfeld 1982, 1991] to graphics. While retaining WoS’s advantages, WoB applies to a broader range of second-order linear elliptic and parabolic PDE problems: various boundary conditions (Dirichlet, Neumann, Robin, and mixed) in both interior and exterior domains. Because WoB is based on boundary integral formulations, its structure more closely parallels Monte Carlo rendering than WoS, enabling the application of advanced variance reduction techniques. We present WoB formulations for elliptic Laplace and Poisson equations, time-dependent diffusion problems, and develop a WoB solver for vector-valued Stokes equations. Throughout, we discuss how sampling and variance reduction methods from rendering can be adapted to WoB. Next, we address the nonlinear Navier-Stokes equations for fluid simulation, whose complexity challenges Monte Carlo techniques. Employing operator splitting, we separate nonlinear terms and solve the remaining linear terms with pointwise Monte Carlo solvers. Recursively applying these solvers with timestepping yields a spatial-discretization-free method. To deal with the resulting exponential computational cost, we also propose cache-based alternatives. Both vorticity- and velocity-based formulations are explored, retaining the advantages of Monte Carlo methods, including geometric robustness and variance reduction, while integrating traditional fluid simulation techniques. We then propose Projected Walk on Spheres (PWoS), a novel solver for surface PDEs, inspired by the Closest Point Method. PWoS modifies WoS by projecting random walks onto the surface manifold at each step, preserving geometric flexibility and discretization-free, pointwise evaluation. We also adapt a noise filtering technique for WoS to improve PWoS. Finally, we outline promising future research directions for Monte Carlo PDE solvers in graphics, including concrete proposals to enhance WoB. | |
| dc.identifier.uri | https://diglib.eg.org/handle/10.2312/3607251 | |
| dc.language.iso | en | |
| dc.publisher | University of Waterloo | |
| dc.title | Toward General-Purpose Monte Carlo PDE Solvers for Graphics Applications | |
| dc.type | Thesis |