“Detailed water with coarse grids: combining surface meshes and adaptive discontinuous Galerkin” by Edwards and Bridson

  • ©Essex Edwards and Robert Bridson




    Detailed water with coarse grids: combining surface meshes and adaptive discontinuous Galerkin


Session Title: Fluids



    We present a new adaptive fluid simulation method that captures a high resolution surface with precise dynamics, without an inefficient fine discretization of the entire fluid volume. Prior adaptive methods using octrees or unstructured meshes carry large overheads and implementation complexity. We instead stick with coarse regular Cartesian grids, using detailed cut cells at boundaries, and discretize the dynamics with a p-adaptive Discontinuous Galerkin (DG) method. This retains much of the data structure simplicity of regular grids, more efficiently captures smooth parts of the flow, and offers the flexibility to easily increase resolving power where needed without geometric refinement.


    1. Adams, B., Pauly, M., Keiser, R., and Guibas, L. J. 2007. Adaptively sampled particle fluids. ACM Trans. Graph. 26, 3 (July). Google ScholarDigital Library
    2. Ando, R., Thürey, N., and Tsuruno, R. 2012. Preserving fluid sheets with adaptively sampled anisotropic particles. IEEE Transactions on Visualization and Computer Graphics 18, 8, 1202–1214. Google ScholarDigital Library
    3. Ando, R., Thürey, N., and Wojtan, C. 2013. Highly adaptive liquid simulations on tetrahedral meshes. ACM Trans. Graph. (Proc. SIGGRAPH 2013) (July). Google ScholarDigital Library
    4. Arnold, D., Brezzi, F., Cockburn, B., and Marini, L. 2002. Unified analysis of discontinuous Galerkin methods for elliptic problems. SIAM journal on numerical analysis 39, 5, 1749–1779. Google ScholarDigital Library
    5. Babuska, I., and Guo, B. 1992. The h, p and hp version of the finite element method basic theory and applications. NASA STI/Recon Technical Report N 93, 22550.Google Scholar
    6. Batty, C., Xenos, S., and Houston, B. 2010. Tetrahedral embedded boundary methods for accurate and flexible adaptive fluids. In Proceedings of Eurographics.Google Scholar
    7. Bojsen-Hansen, M., and Wojtan, C. 2013. Liquid surface tracking with error compensation. ACM Transactions on Graphics (SIGGRAPH 2013) 32, 4, 79:1–79:10. Google ScholarDigital Library
    8. Boyd, J. P. 2001. Chebyshev and Fourier spectral methods. Courier Dover Publications.Google Scholar
    9. Bridson, R. 2008. Fluid Simulation for Computer Graphics. A K Peters/CRC Press, Sept. Google ScholarDigital Library
    10. Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM J. Sci. Comput. 31, 4, 2472–2493. Google ScholarDigital Library
    11. Brochu, T., Batty, C., and Bridson, R. 2010. Matching fluid simulation elements to surface geometry and topology. ACM Trans. Graph. 29, 4, 1–9. Google ScholarDigital Library
    12. Castillo, P., Cockburn, B., Perugia, I., and Schötzau, D. 2000. An a priori error analysis of the local discontinuous Galerkin method for elliptic problems. SIAM Journal on Numerical Analysis 38, 5, 1676–1706. Google ScholarDigital Library
    13. Castillo, P. 2006. A review of the local discontinuous Galerkin (LDG) method applied to elliptic problems. Applied numerical mathematics 56, 10, 1307–1313. Google ScholarDigital Library
    14. Chentanez, N., and Müller, M. 2011. Real-time eulerian water simulation using a restricted tall cell grid. In ACM SIGGRAPH 2011 Papers, ACM, New York, NY, USA, SIGGRAPH ’11, 82:1–82:10. Google ScholarDigital Library
    15. Chentanez, N., Feldman, B. E., Labelle, F., O’Brien, J. F., and Shewchuk, J. R. 2007. Liquid simulation on lattice-based tetrahedral meshes. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’07, 219–228. Google ScholarDigital Library
    16. Cockburn, B., Kanschat, G., and Schötzau, D. 2005. The local discontinuous Galerkin method for linearized incompressible fluid flow: a review. Computers & fluids 34, 4, 491–506.Google Scholar
    17. Edwards, E., and Bridson, R. 2012. A high-order accurate particle-in-cell method. International Journal for Numerical Methods in Engineering 90, 9, 1073–1088.Google ScholarCross Ref
    18. Eggers, J. 2011. The subtle dynamics of liquid sheets. Journal of Fluid Mechanics 672, 1.Google ScholarCross Ref
    19. English, R. E., Qiu, L., Yu, Y., and Fedkiw, R. 2013. Chimera grids for water simulation. In Proceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, New York, NY, USA, SCA ’13, 85–94. Google ScholarDigital Library
    20. Enright, D., Fedkiw, R., Ferziger, J., and Mitchell, I. 2002. A hybrid particle level set method for improved interface capturing. Journal of Computational Physics 183, 1, 83–116. Google ScholarDigital Library
    21. Foster, N., and Metaxas, D. 1996. Realistic animation of liquids. Graphical models and image processing 58, 5, 471–483. Google ScholarDigital Library
    22. 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. (Proc. SIGGRAPH) 25, 3, 805–811. Google ScholarDigital Library
    23. Karniadakis, G. E., and Sherwin, S. J. 1999. Spectral/hp element methods for CFD. Oxford University Press.Google Scholar
    24. Kaufmann, P., Martin, S., Botsch, M., and Gross, M. 2009. Flexible simulation of deformable models using Discontinuous Galerkin FEM. Graphical Models 71, 4, 153–167. Special Issue of ACM SIGGRAPH / Eurographics Symp. Comp. Anim. 2008. Google ScholarDigital Library
    25. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. In ACM Transactions on Graphics (TOG), vol. 23, ACM, 457–462. Google ScholarDigital Library
    26. Misztal, M., and Bærentzen, J. 2012. Topology adaptive interface tracking using the deformable simplicial complex. ACM Transactions on Graphics 31, 3. Google ScholarDigital Library
    27. Misztal, M., Bridson, R., Erleben, K., Bærentzen, J., and Anton, F. 2010. Optimization-based fluid simulation on unstructured meshes. In Proceedings of the 7th Workshop on Virtual Reality Interaction and Physical Simulation (VRIPHYS 2010), SIGGRAPH.Google Scholar
    28. Misztal, M., Erleben, K., Bargteil, A., Fursund, J., Christensen, B., Bærentzen, J., and Bridson, R. 2012. Multiphase flow of immiscible fluids on unstructured moving meshes. In Eurographics/ACM SIGGRAPH Symposium on Computer Animation, The Eurographics Association, 97–106. Google ScholarDigital Library
    29. Moresi, L., Dufour, F., and Mhlhaus, H.-B. 2003. A lagrangian integration point finite element method for large deformation modeling of viscoelastic geomaterials. Journal of Computational Physics 184, 2, 476–497. Google ScholarDigital Library
    30. Müller, M. 2009. Fast and robust tracking of fluid surfaces. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, New York, NY, USA, SCA ’09, 237–245. Google ScholarDigital Library
    31. Osher, S., and Fedkiw, R. 2003. Level set methods and dynamic implicit surfaces, vol. 153. Springer.Google Scholar
    32. Qin, R., and Krivodonova, L. 2012. A discontinuous Galerkin method for solutions of the Euler equations on Cartesian grids with embedded geometries. Journal of Computational Science.Google Scholar
    33. Schwab, C. 1998. p-and hp-finite element methods: Theory and applications in solid and fluid mechanics. Clarendon Press Oxford.Google Scholar
    34. Solenthaler, B., and Gross, M. 2011. Two-scale particle simulation. ACM Trans. Graph. 30, 4 (July), 81:1–81:8. Google ScholarDigital Library
    35. Thürey, N., Wojtan, C., Gross, M., and Turk, G. 2010. A multiscale approach to mesh-based surface tension flows. In ACM SIGGRAPH 2010 Papers, ACM, New York, NY, USA, SIGGRAPH ’10, SIGGRAPH, 48:1–48:10. Google ScholarDigital Library
    36. Wojtan, C., and Turk, G. 2008. Fast viscoelastic behavior with thin features. ACM Trans. Graph. 27, 3, 1–8. Google ScholarDigital Library
    37. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2009. Deforming meshes that split and merge. In ACM Transactions on Graphics (TOG), vol. 28, ACM, 76. Google ScholarDigital Library
    38. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2010. Physics-inspired topology changes for thin fluid features. ACM Trans. Graph. 29, 4, 1–8. Google ScholarDigital Library
    39. Wojtan, C., Müller-Fischer, M., and Brochu, T. 2011. Liquid simulation with mesh-based surface tracking. In ACM SIGGRAPH 2011 Courses, ACM, New York, NY, USA, SIGGRAPH ’11, ACM, 8:1–8:84. Google ScholarDigital Library
    40. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. In ACM SIGGRAPH 2005 Papers, ACM, SIGGRAPH, 965–972. Google ScholarDigital Library

ACM Digital Library Publication: