“An adaptive variational finite difference framework for efficient symmetric octree viscosity” by Goldade, Wang, Aanjaneya and Batty

  • ©Ryan Goldade, Yipeng Wang, Mridul Aanjaneya, and Christopher Batty




    An adaptive variational finite difference framework for efficient symmetric octree viscosity

Session/Category Title:   Fluids I



    While pressure forces are often the bottleneck in (near-)inviscid fluid simulations, viscosity can impose orders of magnitude greater computational costs at lower Reynolds numbers. We propose an implicit octree finite difference discretization that significantly accelerates the solution of the free surface viscosity equations using adaptive staggered grids, while supporting viscous buckling and rotation effects, variable viscosity, and interaction with scripted moving solids. In experimental comparisons against regular grids, our method reduced the number of active velocity degrees of freedom by as much as a factor of 7.7 and reduced linear system solution times by factors between 3.8 and 9.4. We achieve this by developing a novel adaptive variational finite difference methodology for octrees and applying it to the optimization form of the viscosity problem. This yields a linear system that is symmetric positive definite by construction, unlike naive finite difference/volume methods, and much sparser than a hypothetical finite element alternative. Grid refinement studies show spatial convergence at first order in L∞ and second order in L1, while the significantly smaller size of the octree linear systems allows for the solution of viscous forces at higher effective resolutions than with regular grids. We demonstrate the practical benefits of our adaptive scheme by replacing the regular grid viscosity step of a commercial liquid simulator (Houdini) to yield large speed-ups, and by incorporating it into an existing inviscid octree simulator to add support for viscous flows. Animations of viscous liquids pouring, bending, stirring, buckling, and melting illustrate that our octree method offers significant computational gains and excellent visual consistency with its regular grid counterpart.


    1. Mridul Aanjaneya, Ming Gao, Haixiang Liu, Christopher Batty, and Eftychios Sifakis. 2017. Power diagrams and sparse paged grids for high resolution adaptive liquids. ACM Trans. Graph. (SIGGRAPH) 36, 4 (2017), 140. Google ScholarDigital Library
    2. Ann S. Almgren, John B. Bell, and Phillip Colella. 1998. A conservative adaptive projection method for the variable density incompressible Navier-Stokes equations. J. Comp. Phys. 142, 1 (1998), 1–46. Google ScholarDigital Library
    3. Ryoichi Ando, Nils Thuerey, and Chris Wojtan. 2013. Highly adaptive liquid simulations on tetrahedral meshes. ACM Trans. Graph. (SIGGRAPH) 32, 4 (2013), 103. Google ScholarDigital Library
    4. Ryoichi Ando, Nils Thuerey, and Chris Wojtan. 2015a. A dimension-reduced pressure solver for liquid simulations. Computer Graphics Forum (Eurographics) 34, 2 (2015), 473–480. Google ScholarDigital Library
    5. Ryoichi Ando, Nils Thuerey, and Chris Wojtan. 2015b. A stream function solver for liquid simulations. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 53. Google ScholarDigital Library
    6. Luiz Fernando de Souza Andrade, Marcos Sandim, Fabiano Petronetto, Paulo Pagliosa, and Afonso Paiva. 2015. Particle-based fluids for viscous jet buckling. Computers and Graphics 52 (2015), 106–115. Google ScholarDigital Library
    7. Adam W. Bargteil, Chris Wojtan, Jessica K. Hodgins, and Greg Turk. 2007. A finite element method for animating large viscoplastic flow. ACM Trans. Graph. (SIGGRAPH) 26, 3 (2007), 16. Google ScholarDigital Library
    8. Christopher Batty. 2017. A cell-centred finite volume method for the Poisson problem on non-graded quadtrees with second order accurate gradients. J. Comp. Phys. 331 (2017), 49–72. Google ScholarDigital Library
    9. Christopher Batty, Florence Bertails, and Robert Bridson. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Trans. Graph. (SIGGRAPH) 26, 3 (2007), 100. Google ScholarDigital Library
    10. Christopher Batty and Robert Bridson. 2008. Accurate viscous free surfaces for buckling, coiling, and rotating liquids. In Symposium on Computer Animation. 219–228. Google ScholarDigital Library
    11. Christopher Batty and Ben Houston. 2011. A simple finite volume method for adaptive viscous liquids. In Symposium on Computer Animation. 111–118. Google ScholarDigital Library
    12. Christopher Batty, Andres Uribe, Basile Audoly, and Eitan Grinspun. 2012. Discrete viscous sheets. ACM Trans. Graph. (SIGGRAPH) 31, 4 (2012), 113. Google ScholarDigital Library
    13. Christopher Batty, Stefan Xenos, and Ben Houston. 2010. Tetrahedral embedded boundary methods for accurate and flexible adaptive fluids. Computer Graphics Forum (Eurographics) 29, 2 (2010), 695–704.Google ScholarCross Ref
    14. Miklos Bergou, Basile Audoly, Etienne Vouga, Max Wardetzky, and Eitan Grinspun. 2010. Discrete viscous threads. ACM Trans. Graph. (SIGGRAPH) 29, 4 (2010), 116. Google ScholarDigital Library
    15. Andrea Bonito, Marco Picasso, and Manuel Laso. 2006. Numerical simulation of 3D viscoelastic flows with free surfaces. J. Comp. Phys. 215, 2 (2006), 691–716. Google ScholarDigital Library
    16. Robert Bridson. 2015. Fluid simulation for computer graphics, 2nd edition. AK Peters / CRC Press.Google Scholar
    17. Tyson Brochu, Christopher Batty, and Robert Bridson. 2010. Matching fluid simulation elements to surface geometry and topology. ACM Trans. Graph. (SIGGRAPH) 29, 4 (2010), 47. Google ScholarDigital Library
    18. Steve Capell, Seth Green, Brian Curless, Tom Duchamp, and Zoran Popović. 2002. A multiresolution framework for dynamic deformations. In Symposium on Computer Animation. 41–47. Google ScholarDigital Library
    19. Mark Carlson, Peter J. Mucha, R. Van Horn, and Greg Turk. 2002. Melting and flowing. In Symposium on Computer Animation. 167–174. Google ScholarDigital Library
    20. Nuttapong Chentanez, Bryan E. Feldman, François Labelle, James F. O’Brien, and Jonathan Richard Shewchuk. 2007. Liquid simulation on lattice-based tetrahedral meshes. In Symposium on Computer Animation. 219–228. Google ScholarDigital Library
    21. Pascal Clausen, Martin Wicke, Jonathan Richard Shewchuk, and James F. O’Brien. 2013. Simulating liquids and solid-liquid interactions with Lagrangian meshes. ACM Trans. Graph. 32, 2 (2013), 17. Google ScholarDigital Library
    22. Sharif Elcott, Yiying Tong, Eva Kanso, Peter Schröder, and Mathieu Desbrun. 2007. Stable, circulation-preserving, simplicial fluids. ACM Trans. Graph. 26, 1 (2007), 4. Google ScholarDigital Library
    23. Henrik Fält and Doug Roble. 2003. Fluids with extreme viscosity. In SIGGRAPH Sketches. 1. Google ScholarDigital Library
    24. Florian Ferstl, Rudiger Westermann, and Christian Dick. 2014. Large-scale liquid simulation on adaptive hexahedral grids. IEEE TVCG 20, 10 (2014), 1405–1417.Google Scholar
    25. Nick Foster and Dimitris Metaxas. 1996. Realistic animation of liquids. Graphical Models and Image Processing 58, 5 (1996), 471–483. Google ScholarDigital Library
    26. Ming Gao, Andre Pradhana Tampubulon, Chenfanfu Jiang, and Eftychios Sifakis. 2017. An adaptive generalized interpolation material point method for simulating elastoplastic materials. ACM Trans. Graph. (SIGGRAPH Asia) 36, 6 (2017), 223. Google ScholarDigital Library
    27. T.V. Gerya, D. A. May, and T. Duretz. 2013. An adaptive staggered grid finite difference method for modeling geodynamic Stokes flows with strongly variable viscosity. Geochemistry, Geophysics, Geosystems 14, 4 (2013), 1200–1225.Google Scholar
    28. Tolga G. Goktekin, Adam W. Bargteil, and James F. O’Brien. 2004. A method for animating viscoelastic fluids. ACM Trans. Graph. (SIGGRAPH) 23, 3 (2004), 463–468. Google ScholarDigital Library
    29. Eitan Grinspun, Peter Krysl, and Peter Schröder. 2002. CHARMS: A simple framework for adaptive simulation. ACM Trans. Graph. (SIGGRAPH) 21, 3 (2002), 281–290. Google ScholarDigital Library
    30. Arthur Guittet, Maxime Theillard, and Frédéric Gibou. 2015. A stable projection method for the incompressible Navier-Stokes equations on arbitrary geometries and adaptive Quad/Octrees. J. Comp. Phys. 292 (2015), 215–238. Google ScholarDigital Library
    31. Jeong-Mo Hong and Chang-Hun Kim. 2005. Discontinuous fluids. ACM Trans. Graph. (SIGGRAPH) 24, 3 (2005), 915–920. Google ScholarDigital Library
    32. Lior Horesh and Eldad Haber. 2011. A second order discretization of Maxwell’s equations in the quasi-static regime on octree grids. SIAM J. Sci. Comput. 33, 5 (2011), 2805–2822. Google ScholarDigital Library
    33. Bryan M. Klingner, Bryan E. Feldman, Nuttapong Chentanez, and James F. O’Brien. 2006. Fluid animation with dynamic meshes. ACM Trans. Graph. (SIGGRAPH) 25, 3 (2006), 820–825. Google ScholarDigital Library
    34. Egor Larionov, Christopher Batty, and Robert Bridson. 2017. Variational stokes: a unified pressure-viscosity solver for accurate viscous liquids. ACM Trans. Graph. (SIGGRAPH) 36, 4 (2017), 101. Google ScholarDigital Library
    35. Frank Losasso, Ronald Fedkiw, and Stanley Osher. 2006. Spatially adaptive techniques for level set methods and incompressible flow. Computers & Fluids 35, 10 (2006), 995–1010.Google ScholarCross Ref
    36. Frank Losasso, Frédéric Gibou, and Ron Fedkiw. 2004. Simulating water and smoke with an octree data structure. ACM Trans. Graph. (SIGGRAPH) 23, 3 (2004), 457–462. Google ScholarDigital Library
    37. Chohong Min and Frédéric Gibou. 2006. A second order accurate projection method for the incompressible Navier-Stokes equations on non-graded adaptive grids. J. Comp. Phys. 219, 2 (2006), 912–929. Google ScholarDigital Library
    38. Marek Misztal, Robert Bridson, Kenny Erleben, Andreas Baerentzen, and Francois Anton. 2010. Optimization-based fluid simulation on unstructured meshes. In VRIPHYS. 11–20.Google Scholar
    39. Marek Misztal, Kenny Erleben, Adam W. Bargteil, B. Bunch Christensen, Andreas Baerentzen, and Robert Bridson. 2014. Multiphase flow of immiscible fluids on unstructured moving meshes. IEEE TVCG 20, 1 (2014), 4–16. Google ScholarDigital Library
    40. Patrick Mullen, Keenan Crane, Dmitry Pavlov, Yiying Tong, and Mathieu Desbrun. 2009. Energy-preserving integrators for fluid animation. ACM Trans. Graph. (SIGGRAPH) 28, 3 (2009), 38. Google ScholarDigital Library
    41. Rahul Narain, Abhinav Golas, and Ming C. Lin. 2010. Free-flowing granular materials with two-way solid coupling. ACM Trans. Graph. (SIGGRAPH Asia) 29, 6 (2010), 173. Google ScholarDigital Library
    42. Michael B. Nielsen and Robert Bridson. 2016. Spatially adaptive FLIP fluid simulations in Bifrost. In ACM SIGGRAPH talks. 41. Google ScholarDigital Library
    43. K. D. Nikitin, M. A. Olshanskii, K. M. Terekhov, and Y. V. Vassilevski. 2011. A numerical method for the simulation of free surface flows of viscoplastic fluid in 3D. Journal of Computational Mathematics (2011), 605–622.Google Scholar
    44. K. D. Nikitin and Yuri V. Vassilevski. 2008. Free surface flow modelling on dynamically refined hexahedral meshes. Russian Journal of Numerical Analysis and Mathematical Modelling 23, 5 (2008), 469–485.Google ScholarCross Ref
    45. Maxim A. Olshanskii, Kirill M. Terekhov, and Yuri V. Vassilevski. 2013. An octree-based solver for the incompressible Navier-Stokes equations with enhanced stability and low dissipation. Computers & Fluids 84 (2013), 231–246.Google ScholarCross Ref
    46. Andreas Peer, Markus Ihmsen, Jens Cornelis, and Matthias Teschner. 2015. An implicit viscosity formulation for SPH fluids. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 114. Google ScholarDigital Library
    47. Daniel Ram, Theodore Gast, Chenfanfu Jiang, Craig Schroeder, Alexey Stomakhin, Joseph Teran, and Pirouz Kavehpour. 2015. A material point method for viscoelastic fluids, foams and sponges. In Symposium on Computer Animation. 157–163. Google ScholarDigital Library
    48. Nick Rasmussen, Doug Enright, Duc Nguyen, Sebastian Marino, N. Sumner, Willi Geiger, Samir Hoon, and Ron Fedkiw. 2004. Directable photorealistic liquids. In Symposium on Computer Animation. 193–202. Google ScholarDigital Library
    49. Rajsekhar Setaluri, Mridul Aanjaneya, Sean Bauer, and Eftychios Sifakis. 2014. SPGrid: A sparse paged grid structure applied to adaptive smoke simulation. ACM Trans. Graph. (SIGGRAPH Asia) 33, 6 (2014), 205. Google ScholarDigital Library
    50. Lin Shi and Yizhou Yu. 2004. Visual smoke simulation with adaptive octree refinement. Computer Graphics and Imaging (2004), 13–19.Google Scholar
    51. Side Effects Software. 2018. Houdini.Google Scholar
    52. Jos Stam. 1999. Stable fluids. In SIGGRAPH. 121–128. Google ScholarDigital Library
    53. Alexey Stomakhin, Craig Schroeder, Chenfanfu Jiang, Lawrence Chai, Joseph Teran, and Andrew Selle. 2014. Augmented MPM for phase-change and varied materials. ACM Trans. Graph. (SIGGRAPH) 33, 4 (2014), 138. Google ScholarDigital Library
    54. Tetsuya Takahashi, Yoshinori Dobashi, Issei Fujishiro, Tomoyuki Nishita, and Ming C. Lin. 2015. Implicit formulation for SPH-based viscous fluids. Computer Graphics Forum (Eurographics) 34, 2 (2015), 493–502. Google ScholarDigital Library
    55. Jeremy D. Wendt, William Baxter, Ipek Oguz, and Ming C. Lin. 2007. Finite volume flow simulations on arbitrary domains. Graphical Models 69, 1 (2007), 19–32. Google ScholarDigital Library
    56. Chris Wojtan and Greg Turk. 2008. Fast viscoelastic behavior with thin features. ACM Trans. Graph. (SIGGRAPH) 27, 3 (2008), 47. Google ScholarDigital Library
    57. Yonghao Yue, Breannan Smith, Christopher Batty, Changxi Zheng, and Eitan Grinspun. 2015. Continuum foam: A material point method for shear-dependent flows. ACM Trans. Graph. 34, 5 (2015), 160. Google ScholarDigital Library
    58. Yonghao Yue, Breannan Smith, Peter Yichen Chen, Maytee Chantharayukhonthorn, Ken Kamrin, and Eitan Grinspun. 2018. Hybrid Grains: Adaptive Coupling of Discrete and Continuum Simulations of Granular Media. ACM Trans. Graph. (SIGGRAPH Asia) 37, 6 (2018), 283. Google ScholarDigital Library
    59. Bo Zhu, Minjae Lee, Ed Quigley, and Ronald Fedkiw. 2015. Codimensional non-Newtonian fluids. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 115. Google ScholarDigital Library
    60. Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29, 2 (2010), 16. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: