“A PPPM fast summation method for fluids and beyond” by Zhang and Bridson
Conference:
Type(s):
Title:
- A PPPM fast summation method for fluids and beyond
Session/Category Title: Newton's Garden
Presenter(s)/Author(s):
Abstract:
Solving the N-body problem, i.e. the Poisson problem with point sources, is a common task in graphics and simulation. The naive direct summation of the kernel function over all particles scales quadratically, rendering it too slow for large problems, while the optimal Fast Multipole Method has drastic implementation complexity and can sometimes carry too high an overhead to be practical. We present a new Particle-Particle Particle-Mesh (PPPM) algorithm which is fast, accurate, and easy to implement even in parallel on a GPU. We capture long-range interactions with a fast multigrid solver on a background grid with a novel boundary condition, while short-range interactions are calculated directly with a new error compensation to avoid error from the background grid. We demonstrate the power of PPPM with a new vortex particle smoke solver, which features a vortex segment-approach to the stretching term, potential flow to enforce no-stick solid boundaries on arbitrary moving solid boundaries, and a new mechanism for vortex shedding from boundary layers. Comparison against a simpler Vortex-in-Cell approach shows PPPM can produce significantly more detailed results with less computation. In addition, we use our PPPM solver for a Poisson surface reconstruction problem to show its potential as a general-purpose Poisson solver.
References:
1. Anderson, C. R. 1983. Vortex Methods for Flows of Variable Density. PhD thesis, University of California, Berkeley.
2. Anderson, C. R. 1986. A method of local corrections for computing the velocity field due to a distribution of vortex blobs. J. Comp. Physics 62, 111–123.
3. Angelidis, A., and Neyret, F. 2005. Simulation of smoke based on vortex filament primitives. In Symposium on Computer Animation, 87–96.
4. Brochu, T., Keeler, T., and Bridson, R. 2012. Linear-time smoke animation with vortex sheet meshes. In Proc. Symp. Comp. Animation, 87–95.
5. Brown, G. L., and Roshko, A. 1974. On density effects and large structure in turbulent mixing layers. J. Fluid Mechanics 64, 775–816.Cross Ref
6. Chorin, A. J. 1973. Numerical study of slightly viscous flow. Journal of Fluid Mechanics Digital Archive 57, 04, 785–796.Cross Ref
7. Cohen, J. M., Tariq, S., and Green, S. 2010. Interactive fluid-particle simulation using translating Eulerian grids. In ACM Symp. I3D, 15–22.
8. Cottet, G.-H., and Koumoutsakos, P. 2000. Vortex methods – theory and practice. Cambridge University Press.
9. Couet, B., Buneman, O., and Leonard, A. 1981. Simulation of three-dimensional incompressible flows with a vortex-in-cell method. Journal of Computational Physics 39, 2, 305–328.Cross Ref
10. Fedkiw, R., Stam, J., and Jensen, H. W. 2001. Visual simulation of smoke. In Proc. SIGGRAPH, 15–22.
11. Ferstl, F., Westermann, R., and Dick, C. 2014. Large-scale liquid simulation on adaptive hexahedral grids. Visualization and Computer Graphics, IEEE Transactions on PP, 99, 1–1.
12. Green, S. 2008. Cuda particles. nVidia Whitepaper 2, 3.2, 1.
13. Greengard, L., and Rokhlin, V. 1987. A fast algorithm for particle simulations. J. Comp. Physics 73, 325–348.
14. Gumerov, N. A., and Duraiswami, R. 2008. Fast multipole methods on graphics processors. Journal of Computational Physics 227 (2008/09/10/), 8290–8313.
15. Henderson, R. D. 2012. Scalable fluid simulation in linear time on shared memory multiprocessors. In Proceedings of the Digital Production Symposium, ACM, New York, NY, USA, DigiPro ’12, 43–52.
16. Herrmann, M. 2005. An Eulerian level set/vortex sheet method for two-phase interface dynamics. J. Comput. Phys. 203, 2 (Mar.), 539–571.
17. Hockney, R. W., and Eastwood, J. W. 1989. Computer Simulation Using Particles. Taylor & Francis, Jan.
18. Jacobson, A., Kavan, L., and Sorkine-Hornung, O. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. Graph. 32, 4, 33:1–33:12.
19. Kazhdan, M. M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symp. Geometry Processing, 61–70.
20. Koumoutsakos, P., Cottet, G.-H., and Rossinelli, D. 2008. Flow simulations using particles: bridging computer graphics and CFD. In ACM SIGGRAPH 2008 Classes, 25:1–25:73.
21. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Transactions on Graphics 23, 457–462.
22. McAdams, A., Sifakis, E., and Teran, J. 2010. A parallel multigrid poisson solver for fluids simulation on large grids. In Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’10, 65–74.
23. Molemaker, J., Cohen, J. M., Patel, S., and Noh, J. 2008. Low viscosity flow simulations for animation. In SCA ’08: Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, Eurographics Association, 9–18.
24. Museth, K., Lait, J., Johanson, J., Budsberg, J., Henderson, R., Alden, M., Cucka, P., Hill, D., and Pearce, A. 2013. Openvdb: An open-source data structure and toolkit for high-resolution volumes. In ACM SIGGRAPH 2013 Courses, ACM, New York, NY, USA, SIGGRAPH ’13, 19:1–19:1.
25. Park, S. I., and Kim, M.-J. 2005. Vortex fluid for gaseous phenomena. In Proc. Symp. Comp. Animation, 261–270.
26. Pfaff, T., Thuerey, N., Selle, A., and Gross, M. 2009. Synthetic turbulence using artificial boundary layers. ACM Trans. Graph. 28.
27. Pfaff, T., Thuerey, N., and Gross, M. 2012. Lagrangian vortex sheets for animating fluids. ACM Trans. Graph. 31, 4, 112:1–8.
28. Selle, A., Rasmussen, N., and Fedkiw, R. 2005. A vortex particle method for smoke, water and explosions. ACM Transactions on Graphics 24, 910–914.
29. Stam, J. 1999. Stable fluids. In Proc. SIGGRAPH, 121–128.
30. Teschner, M., Heidelberger, B., Mueller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proc. VMV, 47–54.
31. Theuns, T. 1994. Parallel PPPM with exact calculation of short range forces. Computer Physics Commun. 78, 3, 238–246.Cross Ref
32. Walther, J. H. 2003. An influence matrix particle-particle particle-mesh algorithm with exact particle-particle correction. J. Comp. Physics 184, 670–678.
33. Wang, H., Sidorov, K. A., Sandilands, P., and Komura, T. 2013. Harmonic parameterization by electrostatics. ACM Trans. Graph. 32, 5 (Oct.), 155:1–155:12.
34. Weissmann, S., and Pinkall, U. 2010. Filament-based smoke with vortex shedding and variational reconnection. ACM Trans. Graph. 29.
35. Wu, J.-Z. 1995. A theory of three-dimensional interfacial vorticity dynamics. Physics of Fluids 7, 2375–2395.Cross Ref
36. Yaeger, L., Upson, C., and Myers, R. 1986. Combining physical and visual simulation–creation of the planet Jupiter for the film “2010”. Proc. SIGGRAPH 20, 4 (Aug.), 85–93.
37. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 965–972.
