Adaptively sampled particle fluids

ABSTRACT

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.

References

1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617--625.
2. Amenta, N., Bern, M., and Kamvysselis, M. 1998. A new voronoi-based surface reconstruction algorithm. In SIGGRAPH '98, 415--421.
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.
4. Blinn, J. F. 1982. A generalization of algebraic surface drawing. ACM Trans. Graph. 1, 3, 235--256.
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.
6. Clavet, S., Beaudoin, P., and Poulin, P. 2005. Particle-based viscoelastic fluid simulation. In SCA 2005, 219--228.
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.
8. Desbrun, M., and Cani, M.-P. 1998. Active implicit surface for animation. In Graphics Interface, 143--150.
9. Desbrun, M., and Cani, M.-P. 1999. Space-time adaptive simulation of highly deformable substances. Tech. rep., INRIA Nr. 3829.
10. Feldman, B. E., O'Brien, J. F., Klingner, B. M., and Goktekin, T. G. 2005. Fluids in deforming meshes. In SCA 2005.
11. Foskey, M., Lin, M. C., and Manocha, D. 2003. Efficient computation of a simplified medial axis. In SM 2003, 96--107.
12. Foster, N., and Metaxas, D. 1996. Realistic animation of liquids. Graph. Mod. and Im. Proc. 58, 5, 471--483.
13. Foster, N., and Metaxas, D. 1997. Controlling fluid animation. 178--188.
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.
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.
16. Hong, J.-M., and Kim, C.-H. 2005. Discontinuous fluids. ACM Trans. Graph. 24, 3, 915--920.
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.
18. Kipfer, P., and Westermann, R. 2006. Realistic and interactive simulation of rivers. In Proceedings Graphics Interface 2006, 41--48.
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.
20. Klingner, B. M., Feldman, B. E., Chentanez, N., and O'Brien, J. F. 2006. Fluid animation with dynamic meshes. In SIGGRAPH '06.
21. Kolluri, R., O'Brien, J. F., and Shewchuck, J. R. 2004. Provably better moving least squares. In Annual Fall Workshop on Computational Geometry.
22. Lastiwka, M., Quinlan, N., and Basa, M. 2005. Adaptive particle distribution for smoothed particle hydrodynamics. Int. J. Numer. Meth. Fluids 47.
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.
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.
25. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. In SIGGRAPH '04, 457--462.
26. Monaghan, J. J. 2005. Smoothed particle hydrodynamics. Rep. Prog. Phys. 68, 1703--1758.
27. Müller, M., Charypar, D., and Gross, M. 2003. Particle-based fluid simulation for interactive applications. In SCA 2003, 154--159.
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.
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.
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.
31. Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods. Cambridge University Press.
32. Shi, L., and Yu, Y. 2004. Visual smoke simulation with adaptive octree refinement. In Computer Graphics and Imaging.
33. Stam, J. 1999. Stable fluids. In SIGGRAPH '99, 121--128.
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.
35. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. In SIGGRAPH '06, 826--834.
36. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 3, 965--972.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Image and video acquisition

  • Computer graphics

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry