“A Monte Carlo Method for Fluid Simulation” by Rioux-Lavoie, Sugimoto, Özdemir, Shimada, Batty, et al. …
Conference:
Type(s):
Title:
- A Monte Carlo Method for Fluid Simulation
Session/Category Title: Fluid Simulation
Presenter(s)/Author(s):
Abstract:
We present a novel Monte Carlo-based fluid simulation approach capable of pointwise and stochastic estimation of fluid motion. Drawing on the Feynman-Kac representation of the vorticity transport equation, we propose a recursive Monte Carlo estimator of the Biot-Savart law and extend it with a stream function formulation that allows us to treat free-slip boundary conditions using a Walk-on-Spheres algorithm. Inspired by the Monte Carlo literature in rendering, we design and compare variance reduction schemes suited to a fluid simulation context for the first time, show its applicability to complex boundary settings, and detail a simple and practical implementation with temporal grid caching. We validate the correctness of our approach via quantitative and qualitative evaluations – across a range of settings and domain geometries – and thoroughly explore its parameters’ design space. Finally, we provide an in-depth discussion of several axes of future work building on this new numerical simulation modality.
References:
1. Ryoichi Ando, Nils Thuerey, and Chris Wojtan. 2015. A Stream Function Solver for Liquid Simulations. ACM Transactions on Graphics (TOG) 34 (2015).
2. Alexis Angelidis and Fabrice Neyret. 2005. Simulation of Smoke based on Vortex Filament Primitives. In Eurographics/ACM SIGGRAPH Symposium on Computer Animation.
3. James Arvo and David Kirk. 1990. Particle transport and image synthesis. Proceedings of the 17th annual conference on Computer graphics and interactive techniques.
4. Vinicius C Azevedo, Christopher Batty, and Manuel M Oliveira. 2016. Preserving geometry and topology for fluid flows with thin obstacles and narrow gaps. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–12.
5. Benedikt Bitterli, Chris Wyman, Matt Pharr, Peter Shirley, Aaron Lefohn, and Wojciech Jarosz. 2020. Spatiotemporal Reservoir Resampling for Real-Time Ray Tracing with Dynamic Direct Lighting. ACM Trans. Graph. 39, 4, Article 148 (jul 2020), 17 pages.
6. John C. Bowers, Jonathan Leahey, and Rui Wang. 2011. A Ray Tracing Approach to Diffusion Curves. In Proceedings of the Twenty-Second Eurographics Conference on Rendering (Prague, Czech Republic) (EGSR ’11). Eurographics Association, Goslar, DEU, 1345–1352.
7. Robert Bridson. 2015. Fluid Simulation for Computer Graphics. A K Peters/CRC Press.
8. Robert Bridson, Jim Houriham, and Marcus Nordenstam. 2007. Curl-noise for procedural fluid flow. ACM Transactions on Graphics (TOG) 26, 3 (2007).
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.
10. Stephen Brooks. 1998. Markov chain Monte Carlo method and its application. Journal of the royal statistical society: series D (the Statistician) 47, 1 (1998), 69–100.
11. Barbara Busnello, Franco Flandoli, and Marco Romito. 2005. A probabilistic representation for the vorticity of a three-dimensional viscous fluid and for general systems of parabolic equations. Proceedings of The Edinburgh Mathematical Society 48 (2005).
12. Anne Campion-Renson and Marcel J Crochet. 1978. On the stream function-vorticity finite element solutions of Navier-Stokes equations. Internat. J. Numer. Methods Engrg. 12, 12 (1978).
13. Chakravarty R. Alla Chaitanya, Anton S. Kaplanyan, Christoph Schied, Marco Salvi, Aaron Lefohn, Derek Nowrouzezahrai, and Timo Aila. 2017. Interactive Reconstruction of Monte Carlo Image Sequences Using a Recurrent Denoising Autoencoder. ACM Trans. Graph. 36, 4, Article 98 (jul 2017), 12 pages.
14. Albert Chern, Felix Knöppel, Ulrich Pinkall, Peter Schröder, and Steffen Weißmann. 2016. Schrödinger’s smoke. ACM Transactions on Graphics (TOG) 35, 4 (2016).
15. Alexandre Joel Chorin. 1973. Numerical study of slightly viscous flow. Journal of Fluid Mechanics 57 (1973).
16. Pascal Clausen, Martin Wicke, Jonathan R Shewchuk, and James F O’Brien. 2013. Simulating liquids and solid-liquid interactions with Lagrangian meshes. ACM Transactions on Graphics (TOG) 32, 2 (2013).
17. Blender Online Community. 2022. Blender – a 3D modelling and rendering package. Blender Foundation, Stichting Blender Foundation, Amsterdam. http://www.blender.org
18. Peter Constantin and Gautam Iyer. 2007. A stochastic Lagrangian representation of the 3-dimensional incompressible Navier-Stokes equations. Communications on Pure and Applied Mathematics 61 (2007).
19. Robert L Cook. 1986. Stochastic sampling in computer graphics. ACM Transactions on Graphics (TOG) 5, 1 (1986).
20. Georges-Henri Cottet and Petros D Koumoutsakos. 2000. Vortex methods: theory and practice. Vol. 8. Cambridge university press Cambridge.
21. Benoit Couët, Oscar Buneman, and Anthony Leonard. 1981. Simulation of three-dimensional incompressible flows with a vortex-in-cell method. J. Comput. Phys. 39, 2 (1981), 305–328.
22. Ana Bela Cruzeiro. 2020. Stochastic Approaches to Deterministic Fluid Dynamics: A Selective Review. Water 12, 3 (2020).
23. Freddy Delbaen, Jinniao Qiu, and Shanjian Tang. 2015. Forward-Backward Stochastic Differential Systems Associated to Navier-Stokes Equations in the Whole Space. Stochastic Processes and their Applications 125 (2015).
24. Mathieu Desbrun and Marie-Paule Gascuel. 1996. Smoothed particles: A new paradigm for animating highly deformable bodies. In Computer Animation and Simulation’96. Springer.
25. Sharif Elcott, Yiying Tong, Eva Kanso, Peter Schröder, and Mathieu Desbrun. 2007. Stable, circulation-preserving, simplicial fluids. ACM Transactions on Graphics (TOG) 26, 1 (2007).
26. Ronald Fedkiw, Jos Stam, and Henrik Wann Jensen. 2001. Visual simulation of smoke. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques.
27. Nicholas I. Fisher. 1995. Statistical Analysis of Circular Data. Cambridge University Press.
28. Nick Foster and Ronald Fedkiw. 2001. Practical animation of liquids. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques.
29. Cindy M Goral, Kenneth E Torrance, Donald P Greenberg, and Bennett Battaile. 1984. Modeling the interaction of light between diffuse surfaces. ACM SIGGRAPH computer graphics 18, 3 (1984), 213–222.
30. L Greengard and V Rokhlin. 1987. A fast algorithm for particle simulations. J. Comput. Phys. 73, 2 (1987), 325–348.
31. Toshiya Hachisuka. 2005. Combined Lagrangian-Eulerian approach for accurate advection. In ACM SIGGRAPH 2005 Posters. 114–es.
32. David AB Hyde and Ronald Fedkiw. 2019. A unified approach to monolithic solid-fluid coupling of sub-grid and more resolved solids. J. Comput. Phys. 390 (2019), 490–526.
33. Y. Le Jan and A. S. Sznitman. 1997. Stochastic cascades and 3-dimensional Navier-Stokes equations. Probability Theory and Related Fields 109 (1997).
34. Wojciech Jarosz, Craig Donner, Matthias Zwicker, and Henrik Wann Jensen. 2008. Radiance caching for participating media. ACM Transactions on Graphics (TOG) 27, 1 (2008), 1–11.
35. Chenfanfu Jiang, Craig Schroeder, Andrew Selle, Joseph Teran, and Alexey Stomakhin. 2015. The affine particle-in-cell method. ACM Transactions on Graphics (TOG) 34, 4 (2015).
36. James T Kajiya. 1986. The rendering equation. In Proceedings of the 13th annual conference on Computer graphics and interactive techniques.
37. Nima Khademi Kalantari, Steve Bako, and Pradeep Sen. 2015. A Machine Learning Approach for Filtering Monte Carlo Noise. ACM Trans. Graph. 34, 4, Article 122 (jul 2015), 12 pages.
38. Jaroslav Krivánek, Pascal Gautron, Sumanta Pattanaik, and Kadi Bouatouch. 2005. Radiance caching for efficient global illumination computation. IEEE Transactions on Visualization and Computer Graphics 11, 5 (2005), 550–561.
39. Wei Li, Kai Bai, and Xiaopei Liu. 2018. Continuous-scale kinetic fluid simulation. IEEE Transactions on Visualization and Computer Graphics 25, 9 (2018), 2694–2709.
40. Wei Li, Yixin Chen, Mathieu Desbrun, Changxi Zheng, and Xiaopei Liu. 2020. Fast and Scalable Turbulent Flow Simulation with Two-Way Coupling. ACM Trans. Graph. 39, 4, Article 47 (jul 2020), 20 pages.
41. Thomas Lundgren and Petros Koumoutsakos. 1999. On the generation of vorticity at a free surface. Journal of Fluid Mechanics 382 (1999), 351–366.
42. Chaoyang Lyu, Wei Li, Mathieu Desbrun, and Xiaopei Liu. 2021. Fast and versatile fluid-solid coupling for turbulent flow simulation. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–18.
43. Sylvain Maire and Etienne Tanre. 2013. Monte Carlo approximations of the Neumann problem. Walter de Gruyter GmbH 19 (2013).
44. Gisiro Maruyama. 1955. Continuous Markov processes and stochastic equations. Rendiconti del Circolo Matematico di Palermo 4, 1 (1955), 48–90.
45. Olivier Mercier, Xi-Yuan Yin, and Jean-Christophe Nave. 2013. The characteristic mapping method for the linear advection of arbitrary sets. arXiv preprint arXiv:1309.2731 (2013).
46. Nicholas Metropolis and Stanislaw Ulam. 1949. The monte carlo method. Journal of the American statistical association 44, 247 (1949).
47. Zackary Misso, Benedikt Bitterli, Iliyan Georgiev, and Wojciech Jarosz. 2022. Unbiased and consistent rendering using biased estimators. ACM Transactions on Graphics (TOG) 41, 4 (2022), 1–13.
48. Marek Krzysztof Misztal, Kenny Erleben, Adam Bargteil, Jens Fursund, Brian Bunch Christensen, Jakob Andreas Bærentzen, and Robert Bridson. 2013. Multiphase flow of immiscible fluids on unstructured moving meshes. IEEE transactions on visualization and computer graphics 20, 1 (2013).
49. Patrick Mullen, Keenan Crane, Dmitry Pavlov, Yiying Tong, and Mathieu Desbrun. 2009. Energy-Preserving Integrators for Fluid Animation. ACM Trans. Graph 28 (2009).
50. Matthias Müller, David Charypar, and Markus H Gross. 2003. Particle-based fluid simulation for interactive applications.. In Symposium on Computer animation.
51. Mervin E Muller. 1956. Some continuous Monte Carlo methods for the Dirichlet problem. Annals of Mathematical Statistics 27, 3 (1956).
52. Mohammad Sina Nabizadeh, Albert Chern, and Ravi Ramamoorthi. 2021. Kelvin Transformations for Simulations on Infinite Domains. ACM Transactions on Graphics (TOG) 40, 4 (2021).
53. Jan Novák, Iliyan Georgiev, Johannes Hanika, and Wojciech Jarosz. 2018. Monte Carlo methods for volumetric light transport simulation. In Computer Graphics Forum, Vol. 37. Wiley Online Library.
54. Bernt Oksendal. 2013. Stochastic differential equations: an introduction with applications. Springer Science & Business Media.
55. Sang Il Park and Myoung Jun Kim. 2005. Vortex fluid for gaseous phenomena. In Eurographics/ACM SIGGRAPH Symposium on Computer Animation.
56. MF Peeters, WG Habashi, and EG Dueck. 1987. Finite element stream function-vorticity solutions of the incompressible Navier-Stokes equations. International journal for numerical methods in fluids 7, 1 (1987).
57. Tobias Pfaff, Nils Thuerey, and Markus Gross. 2012. Lagrangian vortex sheets for animating fluids. ACM Transactions on Graphics (TOG) 31, 4 (2012).
58. Matt Pharr. 2018. Guest Editor’s Introduction: Special Issue on Production Rendering. ACM Transactions on Graphics (TOG) 28, 3 (2018).
59. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2018. Physically based rendering: From theory to implementation. Morgan Kaufmann.
60. Yang Qi, Dario Seyb, Benedikt Bitterli, and Wojciech Jarosz. 2022. A bidirectional formulation for Walk on Spheres. Computer Graphics Forum (Proceedings of EGSR) 41, 4 (July 2022).
61. Ziyin Qu, Xinxin Zhang, Ming Gao, Chenfanfu Jiang, and Baoquan Chen. 2019. Efficient and conservative fluids using bidirectional mapping. ACM Transactions on Graphics (TOG) 38, 4 (2019).
62. Christian P. Robert and George Casella. 1999. Monte Carlo Statistical Methods (Springer Texts in Statistics). Springer-Verlag, Berlin, Heidelberg.
63. Takahiro Sato, Christopher Batty, Takeo Igarashi, and Ryoichi Ando. 2018. Spatially adaptive long-term semi-Lagrangian method for accurate velocity advection. Computational Visual Media 4, 3 (2018).
64. 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).
65. Rohan Sawhney, Dario Seyb, Wojciech Jarosz, and Keenan Crane. 2022. Grid-Free Monte Carlo for PDEs with Spatially Varying Coefficients. ACM Transactions on Graphics (TOG) 41, 4 (2022).
66. Andrew Selle, Nick Rasmussen, and Ronald Fedkiw. 2005. A vortex particle method for smoke, water and explosions. In ACM SIGGRAPH.
67. Naoharu H. Shimada and Toshiya Hachisuka. 2020. Quantum Coin Method for Numerical Integration. cgforum 39 (2020).
68. Nikolai A Simonov. 2017. Walk-on-spheres algorithm for solving third boundary value problem. Applied Mathematics Letters 64 (2017), 156–161.
69. Jos Stam. 1999. Stable fluids. In Proceedings of the 26th annual conference on Computer graphics and interactive techniques.
70. Geoffrey Ingram Taylor and Albert Edward Green. 1937. Mechanism of the production of small eddies from large ones. Proceedings of the Royal Society of London. Series A – Mathematical and Physical Sciences 158, 895 (1937), 499–521.
71. Jerry Tessendorf and Brandon Pelfrey. 2011. The characteristic map for fast and efficient vfx fluid simulations. In Computer Graphics International Workshop on VFX, Computer Animation, and Stereo Movies. Ottawa, Canada.
72. Eric Veach and Leonidas J Guibas. 1997. Metropolis light transport. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques. 65–76.
73. Jiří Vorba and Jaroslav Křivánek. 2016. Adjoint-driven Russian Roulette and Splitting in Light Transport Simulation. ACM Transactions on Graphics (TOG) 35, 4, Article 42 (2016).
74. Gregory J Ward, Francis M Rubinstein, and Robert D Clear. 1988. A ray tracing solution for diffuse interreflection. In Proceedings of the 15th annual conference on Computer graphics and interactive techniques. 85–92.
75. Shiying Xiong, Rui Tao, Yaorui Zhang, Fan Feng, and Bo Zhu. 2021. Incompressible Flow Simulation of Vortex Segment Clouds. ACM Transactions on Graphics (TOG) 40, 4 (2021).
76. Dongbin Xiu and George Em Karniadakis. 2001. A semi-Lagrangian high-order method for Navier-Stokes equations. Journal of computational physics 172, 2 (2001), 658–684.
77. Shuqi Yang, Shiying Xiong, Yaorui Zhang, Fan Feng, Jinyuan Liu, and Bo Zhu. 2021. Clebsch Gauge Fluid. ACM Transactions on Graphics (TOG) 40, 4 (2021).
78. Xinxin Zhang and Robert Bridson. 2014. A PPPM fast summation method for fluids and beyond. ACM Transactions on Graphics (TOG) 33, 6 (2014).
79. Yongning Zhu and Robert Bridson. 2005. Animating sand as a fluid. ACM Transactions on Graphics (TOG) 24, 3 (2005).
