“Power diagrams and sparse paged grids for high resolution adaptive liquids” by Aanjaneya, Gao, Liu, Batty, , et al. …
Conference:
Type:
Title:
- Power diagrams and sparse paged grids for high resolution adaptive liquids
Session/Category Title: Fluids III
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We present an efficient and scalable octree-inspired fluid simulation framework with the flexibility to leverage adaptivity in any part of the computational domain, even when resolution transitions reach the free surface. Our methodology ensures symmetry, definiteness and second order accuracy of the discrete Poisson operator, and eliminates numerical and visual artifacts of prior octree schemes. This is achieved by adapting the operators acting on the octree’s simulation variables to reflect the structure and connectivity of a power diagram, which recovers primal-dual mesh orthogonality and eliminates problematic T-junction configurations. We show how such operators can be efficiently implemented using a pyramid of sparsely populated uniform grids, enhancing the regularity of operations and facilitating parallelization. A novel scheme is proposed for encoding the topology of the power diagram in the neighborhood of each octree cell, allowing us to locally reconstruct it on the fly via a lookup table, rather than resorting to costly explicit meshing. The pressure Poisson equation is solved via a highly efficient, matrix-free multigrid preconditioner for Conjugate Gradient, adapted to the power diagram discretization. We use another sparsely populated uniform grid for high resolution interface tracking with a narrow band level set representation. Using the recently introduced SPGrid data structure, sparse uniform grids in both the power diagram discretization and our narrow band level set can be compactly stored and efficiently updated via streaming operations. Additionally, we present enhancements to adaptive level set advection, velocity extrapolation, and the fast marching method for redistancing. Our overall framework gracefully accommodates the task of dynamically adapting the octree topology during simulation. We demonstrate end-to-end simulations of complex adaptive flows in irregularly shaped domains, with tens of millions of degrees of freedom.
References:
1. David Adalsteinsson and James A. Sethian. 1995. A fast level set method for propagating interfaces. J. Comp. Phys. 118 (1995), 269–277. Google ScholarDigital Library
2. Bart Adams, Mark Pauly, Richard Keiser, and Leonidas J. Guibas. 2007. Adaptively sampled particle fluids. ACM Trans. Graph. (SIGGRAPH)- 26, 3 (2007), 48.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. 2015. A dimension-reduced pressure solver for liquid simulations. Computer Graphics Forum (Eurographics) 34, 2 (2015), 473–480.Google ScholarDigital Library
5. Franz Aurenhammer. 1987. Power diagrams: properties, algorithms, and applications. SIAM J. Comput. 16, 1 (1987), 78–96. Google ScholarDigital Library
6. Adam W. Bargteil, James F. O’Brien, Tolga G. Goktekin, and John A. Strain. 2006. A semi-Lagrangian contouring method for fluid simulation. ACM Trans. Graph. 25, 1 (2006), 19–38. Google ScholarDigital Library
7. 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
8. 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
9. Morten Bojsen-Hansen and Chris Wojtan. 2013. Liquid surface tracking with error compensation. ACM Trans. Graph. (SIGGRAPH) 32, 4 (2013), 79:1–79:10.Google ScholarDigital Library
10. Robert Bridson. 2015. Fluid simulation for computer graphics, 2nd edition. A. K. Peters, Ltd.Google Scholar
11. 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
12. Tyson Brochu and Robert Bridson. 2009. Robust topological operations for dynamic explicit surfaces. SIAM J. Sci. Comput. 31, 4 (2009), 2472–2493. Google ScholarDigital Library
13. 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. ACM Press, 219–228. Google ScholarDigital Library
14. Nuttapong Chentanez, Tolga G. Goktekin, Bryan E. Feldman, and James F. O’Brien. 2006. Simultaneous coupling of fluids and deformable bodies. In Symposium on Computer Animation. ACM Press, 83–89. Google ScholarDigital Library
15. Nuttapong Chentanez and Matthias Müller. 2011. Real-time Eulerian water simulation using a restricted tall cell grid. ACM Trans. Graph. (SIGGRAPH) 30, 4 (2011), 82.Google ScholarDigital Library
16. Nuttapong Chentanez and Matthias Müller. 2012. Mass-conserving Eulerian liquid simulation. In Symposium on Computer Animation. 245–254.Google Scholar
17. 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
18. Fernando de Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015. Power particles: an incompressible fluid solver based on power diagrams. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 50.Google ScholarDigital Library
19. Mathieu Desbrun and Marie-Paule Gascuel. 1996. Smoothed particles: a new paradigm for animating highly deformable bodies. In Eurographics Workshop on Computer Animation and Simulation. 61–76. Google ScholarCross Ref
20. Christian Dick, Marcus Rogowsky, and Rüdiger Westermann. 2016. Solving the fluid pressure Poisson equation using multigrid – evaluation and improvements. IEEE TVCG 22, 11 (2016), 2480–2492. Google ScholarCross Ref
21. Sharif Elcott and Peter Schröder. 2006. Building your own DEC at home. In ACM SIGGRAPH Course Notes. 55–59. 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. Robert Elliot English, Linhai Qiu, Yue Yu, and Ronald Fedkiw. 2013a. An adaptive discretization of incompressible flow using a multitude of moving Cartesian grids. J. Comp. Phys. 254 (2013), 107–154. Google ScholarDigital Library
24. Robert Elliot English, Linhai Qiu, Yue Yu, and Ronald Fedkiw. 2013b. Chimera grids for water simulation. In Symposium on Computer Animation. ACM Press, 85–94. Google ScholarDigital Library
25. Doug Enright, Stephen Marschner, and Ronald Fedkiw. 2002. Animation and rendering of complex water surfaces. ACM Trans. Graph. (SIGGRAPH) 21, 3 (2002), 736–744. Google ScholarDigital Library
26. Doug Enright, Duc Nguyen, Frédéric Gibou, and Ron Fedkiw. 2003. Using the particle level set method and a second order accurate pressure boundary condition for free surface flows. In Proceedings of the 4th ASME-JSME Joint Fluids Engineering Conference. ASME, 337–342. Google ScholarCross Ref
27. Bryan E. Feldman, James F. O’Brien, and Bryan M. Klingner. 2005. Animating gases with hybrid meshes. ACM Trans. Graph. (SIGGRAPH) 24, 3 (2005), 904–909. Google ScholarDigital Library
28. Florian Ferstl, Rüdiger Westermann, and Christian Dick. 2014. Large-scale liquid simulation on adaptive octree grids. IEEE TVCG 20, 10 (2014), 1405–1417.Google Scholar
29. Nick Foster and Ronald Fedkiw. 2001. Practical animation of liquids. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’01). 23–30. Google ScholarDigital Library
30. Nick Foster and Dimitris Metaxas. 1996. Realistic animation of liquids. Graphical Models and Image Processing 58, 5 (1996), 471–483. Google ScholarDigital Library
31. Frédéric Gibou, Ron Fedkiw, Li-Tien Cheng, and Myungjoo Kang. 2002. A second order accurate symmetric discretization of the Poisson equation on irregular domains. J. Comp. Phys. 176, 1 (2002), 205–227. Google ScholarDigital Library
32. Abhinav Golas, Rahul Narain, Jason Sewall, Pavel Krajcevski, Pradeep Dubey, and Ming Lin. 2012. Large-scale fluid simulation using velocity-vorticity domain decomposition. ACM Trans. Graph. (SIGGRAPH Asia) 31, 6 (2012), 148.Google ScholarDigital Library
33. Ryan Goldade, Christopher Batty, and Chris Wojtan. 2016. A practical method for high-resolution embedded liquid surfaces. Computer Graphics Forum (Eurographics) 35, 2 (2016), 233–242.Google ScholarCross Ref
34. Eran Guendelman, Andrew Selle, Frank Losasso, and Ronald Fedkiw. 2005. Coupling water and smoke to thin deformable and rigid shells. ACM Trans. Graph. (SIGGRAPH) 24, 3 (2005), 973–981. Google ScholarDigital Library
35. Arthur Guittet, Mathieu Lepilliez, Sebastian Tanguy, and Frédéric Gibou. 2015a. Solving elliptic problems with discontinuities on irregular domains: the Voronoi Interface Method. J. Comp. Phys. 298 (2015), 747–765. Google ScholarDigital Library
36. Arthur Guittet, Maxime Theillard, and Frédéric Gibou. 2015b. 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
37. Nambin Heo and Hyeong-Seok Ko. 2010. Detail-preserving fully-Eulerian interface tracking framework. ACM Trans. Graph. (SIGGRAPH Asia) 29, 6 (2010), 176:1–176:8.Google Scholar
38. Jeong-Mo Hong and Chang-Hun Kim. 2005. Discontinuous fluids. ACM Trans. Graph. (SIGGRAPH) 24, 3 (2005), 915–920. Google ScholarDigital Library
39. Geoffrey Irving, Eran Guendelman, Frank Losasso, and Ronald Fedkiw. 2006. Efficient simulation of large bodies of water by coupling two and three dimensional techniques. ACM Trans. Graph. (SIGGRAPH) 25, 3 (2006), 805–811. Google ScholarDigital Library
40. Chenfanfu Jiang, Craig Schroeder, Andrew Selle, Joseph Teran, and Alexey Stomakhin. 2015. The affine particle-in-cell method. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 51.Google ScholarDigital Library
41. Doyub Kim, Oh-young Song, and Hyeong-Seok Ko. 2009. Stretching and wiggling liquids. ACM Trans. Graph. (SIGGRAPH Asia) 28, 5 (2009), 120.Google Scholar
42. Theodore Kim and Ming C. Lin. 2007. Fast animation of lightning using an adaptive mesh. IEEE TVCG 12, 2 (2007), 390–402. Google ScholarDigital Library
43. 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
44. Zuzana Krivá, Angela Handlovičová, and Karol Mikula. 2016. Adaptive cell-centered finite volume method for diffusion equations on a consistent quadtree grid. Advances in computational mathematics 42, 2 (2016), 249–277. Google ScholarDigital Library
45. Michael Lentine, Mridul Aanjaneya, and Ronald Fedkiw. 2011. Mass and momentum conservation for fluid simulation. In Symposium on Computer Animation. 91–100. Google ScholarDigital Library
46. Michael Lentine, Matthew Cong, Saket Patkar, and Ronald Fedkiw. 2012. Simulating free surface flow with very large time steps. In Symposium on Computer Animation. 107–116.Google Scholar
47. Michael Lentine, Wen Zheng, and Ronald Fedkiw. 2010. A novel algorithm for incompressible flow using only a coarse grid projection. ACM Trans. Graph. (SIGGRAPH) 29, 4 (2010), 114.Google ScholarDigital Library
48. Haixiang Liu, Nathan Mitchell, Mridul Aanjaneya, and Eftychios Sifakis. 2016. A scalable schur-complement fluids solver for heterogeneous compute platforms. ACM Trans. Graph. (SIGGRAPH) 35, 6 (2016), 201.Google ScholarDigital Library
49. 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
50. 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
51. David F. Martin and Kelley L. Cartwright. 1996. Solving Poisson’s equation using adaptive mesh refinement. Technical Report. EECS Department, University of California, Berkeley. 19 pages.Google Scholar
52. Aleka McAdams, Eftychios Sifakis, and Joseph Teran. 2010. A parallel multigrid Poisson solver for fluids simulation on large grids. In Symposium on Computer Animation. 65–74.Google Scholar
53. Michael L. Minion. 1996. A projection method for locally refined grids. J. Comp. Phys. 127, 1 (1996), 158–178. Google ScholarDigital Library
54. Marek Misztal and Andreas Bærentzen. 2012. Topology-adaptive interface tracking using the deformable simplicial complex. ACM Trans. Graph. 31, 3 (2012), 24. Google ScholarDigital Library
55. Marek Misztal, Robert Bridson, Kenny Erleben, Andreas Bærentzen, and François Anton. 2010. Optimization-based fluid simulation on unstructured meshes. In VRIPHYS. 11–20.Google Scholar
56. Jeroen Molemaker, Jonathan M. Cohen, Sanjit Patel, and Jonyong Noh. 2008. Low viscosity flow simulations for animation. In Symposium on Computer Animation. 9–18.Google Scholar
57. Patrick Mullen, Pooran Memari, Fernando de Goes, and Mathieu Desbrun. 2011. HOT: Hodge-optimized triangulations. ACM Trans. Graph. (SIGGRAPH) 30, 4 (2011), 103.Google ScholarDigital Library
58. Matthias Müller. 2009. Fast and robust tracking of fluid surfaces. In Symposium on Computer Animation. ACM, New York, NY, USA, 237–245. Google ScholarDigital Library
59. Yen Ting Ng, Chohong Min, and Frédéric Gibou. 2009. An efficient fluid-solid coupling algorithm for single-phase flows. J. Comp. Phys. 228, 23 (2009), 8807–8829. Google ScholarDigital Library
60. Michael B. Nielsen and Robert Bridson. 2016. Spatially adaptive FLIP fluid simulations in Bifrost. In ACM SIGGRAPH talks. 41. Google ScholarDigital Library
61. Blair Perot and V. Subramanian. 2007. Discrete calculus methods for diffusion. J. Comp. Phys. 224, 1 (2007), 59–81. Google ScholarDigital Library
62. Stéphane Popinet. 2003. Gerris: a tree-based adaptive solver for the incompressible Euler equations in complex geometries. J. Comp. Phys. 190, 2 (2003), 572–600. Google ScholarDigital Library
63. Andrew Selle, Ronald Fedkiw, Byungmoon Kim, Yingjie Liu, and Jarek Rossignac. 2008. An unconditionally stable MacCormack method. SIAM J. Sci. Comput. 35, 2–3 (2008), 350–371.Google Scholar
64. 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
65. James Sethian. 1999. Level set methods and fast marching methods. Cambridge University Press.Google Scholar
66. James A. Sethian and Alexander Vladimirsky. 2000. Fast methods for the Eikonal and related Hamilton-Jacobi equations on unstructured meshes. Proceedings of the National Academy of Sciences 97, 11 (2000), 5699–5703. Google ScholarCross Ref
67. Adamandios Sifounakis, Sangseung Lee, and Donghyun You. 2016. A conservative finite volume method for incompressible Navier-Stokes equations on locally refined nested Cartesian grids. J. Comp. Phys. 326 (2016), 845–861. Google ScholarDigital Library
68. Funshing Sin, Adam W. Bargteil, and Jessica K. Hodgins. 2009. A point-based method for animating incompressible flow. In Symposium on Computer Animation. ACM Press, 247–255. Google ScholarDigital Library
69. Barbara Solenthaler and Markus Gross. 2011. Two-scale particle simulation. ACM Trans. Graph. (SIGGRAPH) 30, 4 (2011), 81.Google ScholarDigital Library
70. Jos Stam. 1999. Stable fluids (SIGGRAPH ’99). 121–128.Google Scholar
71. Tetsuya Takahashi and Ming C. Lin. 2016. A Multilevel SPH Solver with Unified Solid Boundary Handling. Computer Graphics Forum 35, 7 (2016), 517–526. Google ScholarDigital Library
72. Chris Wojtan, Nils Thuerey, Markus Gross, and Greg Turk. 2009. Deforming meshes that split and merge. ACM Trans. Graph. (SIGGRAPH) 28, 3 (2009), 76.Google ScholarDigital Library
73. Jihun Yu, Chris Wojtan, Greg Turk, and Chee Yap. 2012. Explicit mesh surfaces for particle based fluids. Computer Graphics Forum (Eurographics) 31, 2 (2012), 815–824.Google ScholarDigital Library
74. Xinxin Zhang and Robert Bridson. 2014. A PPPM fast summation method for fluids and beyond. ACM Trans. Graph. (SIGGRAPH Asia) 33, 6 (2014), 206.Google ScholarDigital Library
75. Bo Zhu, Wenlong Lu, Matthew Cong, Byungmoon Kim, and Ronald Fedkiw. 2013. A new grid structure for domain extension. ACM Trans. on Graph.(SIGGRAPH) 32, 4 (2013), 63.Google ScholarDigital Library
76. Yongning Zhu and Robert Bridson. 2005. Animating sand as a fluid. ACM Trans. Graph. (SIGGRAPH) 24, 3 (2005), 965–972. Google ScholarDigital Library
