“Adaptively sampled particle fluids” by Adams, Pauly, Keiser and Guibas

We present novel adaptive sampling algorithms for particle-based fluid simulation. We introduce a sampling condition based on geometric local feature size that allows focusing computational resources in geometrically complex regions, while reducing the number of particles deep inside the fluid or near thick flat surfaces. Further performance gains are achieved by varying the sampling density according to visual importance. In addition, we propose a novel fluid surface definition based on approximate particle-to-surface distances that are carried along with the particles and updated appropriately. The resulting surface reconstruction method has several advantages over existing methods, including stability under particle resampling and suitability for representing smooth flat surfaces. We demonstrate how our adaptive sampling and distance-based surface reconstruction algorithms lead to significant improvements in time and memory as compared to single resolution particle simulations, without significantly affecting the fluid flow behavior.

1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617–625. Google ScholarDigital Library
2. Amenta, N., Bern, M., and Kamvysselis, M. 1998. A new voronoi-based surface reconstruction algorithm. In SIGGRAPH ’98, 415–421. Google ScholarDigital Library
3. Bargteil, A. W., Goktekin, T. G., O’Brien, J. F., and Strain, J. A. 2006. A semi-lagrangian contouring method for fluid simulation. ACM Trans. Graph. 25. Google ScholarDigital Library
4. Blinn, J. F. 1982. A generalization of algebraic surface drawing. ACM Trans. Graph. 1, 3, 235–256. Google ScholarDigital Library
5. Carlson, M., Mucha, P. J., and Turk, G. 2004. Rigid fluid: animating the interplay between rigid bodies and fluid. In SIGGRAPH ’04, 377–384. Google ScholarDigital Library
6. Clavet, S., Beaudoin, P., and Poulin, P. 2005. Particle-based viscoelastic fluid simulation. In SCA 2005, 219–228. Google ScholarDigital Library
7. Desbrun, M., and Cani, M.-P. 1996. Smoothed particles: A new paradigm for animating highly deformable bodies. In 6th Eurographics Workshop on Computer Animation and Simulation ’96, 61–76. Google ScholarDigital Library
8. Desbrun, M., and Cani, M.-P. 1998. Active implicit surface for animation. In Graphics Interface, 143–150.Google Scholar
9. Desbrun, M., and Cani, M.-P. 1999. Space-time adaptive simulation of highly deformable substances. Tech. rep., INRIA Nr. 3829.Google Scholar
10. Feldman, B. E., O’Brien, J. F., Klingner, B. M., and Goktekin, T. G. 2005. Fluids in deforming meshes. In SCA 2005. Google ScholarDigital Library
11. Foskey, M., Lin, M. C., and Manocha, D. 2003. Efficient computation of a simplified medial axis. In SM 2003, 96–107. Google ScholarDigital Library
12. Foster, N., and Metaxas, D. 1996. Realistic animation of liquids. Graph. Mod. and Im. Proc. 58, 5, 471–483. Google ScholarDigital Library
13. Foster, N., and Metaxas, D. 1997. Controlling fluid animation. 178–188.Google Scholar
14. Frisken, S. F., Perry, R. N., Rockwood, A. P., and Jones, T. R. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In SIGGRAPH ’00, 249–254. Google ScholarDigital Library
15. Guendelman, E., Selle, A., Losasso, F., and Fedkiw, R. 2005. Coupling water and smoke to thin deformable and rigid shells. In SIGGRAPH ’05, 973–981. Google ScholarDigital Library
16. Hong, J.-M., and Kim, C.-H. 2005. Discontinuous fluids. ACM Trans. Graph. 24, 3, 915–920. Google ScholarDigital Library
17. Irving, G., Guendelman, E., Losasso, F., and Fedkiw, R. 2006. Efficient simulation of large bodies of water by coupling two and three dimensional techniques. ACM Trans. Graph. 25, 3,805–811. Google ScholarDigital Library
18. Kipfer, P., and Westermann, R. 2006. Realistic and interactive simulation of rivers. In Proceedings Graphics Interface 2006, 41–48. Google ScholarDigital Library
19. Kitsionas, S., and Whitworth, A. P. 2002. Smoothed particle hydrodynamics with particle splitting, applied to self-gravitating collapse. Monthly Notices of the Royal Astronomical Society 330.Google Scholar
20. Klingner, B. M., Feldman, B. E., Chentanez, N., and O’Brien, J. F. 2006. Fluid animation with dynamic meshes. In SIGGRAPH ’06. Google ScholarDigital Library
21. Kolluri, R., O’Brien, J. F., and Shewchuck, J. R. 2004. Provably better moving least squares. In Annual Fall Workshop on Computational Geometry.Google Scholar
22. Lastiwka, M., Quinlan, N., and Basa, M. 2005. Adaptive particle distribution for smoothed particle hydrodynamics. Int. J. Numer. Meth. Fluids 47.Google Scholar
23. Liu, M. B., Liu, G. R., and Lam, K. Y. 2006. Adaptive smoothed particle hydrodynamics for high strain hydrodynamics with material strength. Shock Waves 15.Google Scholar
24. Lorensen, W. E., and Cline, H. E. 1987. Marching cubes: A high resolution 3d surface construction algorithm. In SIGGRAPH ’87, vol. 21, 163–169. Google ScholarDigital Library
25. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. In SIGGRAPH ’04, 457–462. Google ScholarDigital Library
26. Monaghan, J. J. 2005. Smoothed particle hydrodynamics. Rep. Prog. Phys. 68, 1703–1758.Google ScholarCross Ref
27. Müller, M., Charypar, D., and Gross, M. 2003. Particle-based fluid simulation for interactive applications. In SCA 2003, 154–159. Google ScholarDigital Library
28. Owen, J. M., Villumsen, J. V., Shapiro, P. R., and Martel, H. 1998. Adaptive smoothed particle hydrodynamics: Methodology. II. The Astroph. J. Sup. Series 116.Google Scholar
29. Pauly, M., Keiser, R., Adams, B., Dutré;, P., Gross, M., and Guibas, L. J. 2005. Meshless animation of fracturing solids. ACM Trans. Graph. 24, 3, 957–964. Google ScholarDigital Library
30. Premoze, S., Tasdizen, T., Bigler, J., Lefohn, A. E., and Whitaker, R. T. 2003. Particle-based simulation of fluids. Comput. Graph. Forum 22, 3, 401–410.Google ScholarCross Ref
31. Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods. Cambridge University Press.Google Scholar
32. Shi, L., and Yu, Y. 2004. Visual smoke simulation with adaptive octree refinement. In Computer Graphics and Imaging.Google Scholar
33. Stam, J. 1999. Stable fluids. In SIGGRAPH ’99, 121–128. Google ScholarDigital Library
34. Thürey, N., Rüde, U., and Stamminger, M. 2006. Animation of open water phenomena with coupled shallow water and free surface simulation. In SCA 2006, 157–166. Google ScholarDigital Library
35. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. In SIGGRAPH ’06, 826–834. Google ScholarDigital Library
36. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 3, 965–972. Google ScholarDigital Library