“An adaptive staggered-tilted grid for incompressible flow simulation” by Xiao, Chan, Wang, Zhu and Yang
Conference:
Type(s):
Title:
- An adaptive staggered-tilted grid for incompressible flow simulation
Session/Category Title: Animation: Fluid
Presenter(s)/Author(s):
Abstract:
Enabling adaptivity on a uniform Cartesian grid is challenging due to its highly structured grid cells and axis-aligned grid lines. In this paper, we propose a new grid structure – the adaptive staggered-tilted (AST) grid – to conduct adaptive fluid simulations on a regular discretization. The key mechanics underpinning our new grid structure is to allow the emergence of a new set of tilted grid cells from the nodal positions on a background uniform grid. The original axis-aligned cells, in conjunction with the populated axis-tilted cells, jointly function as the geometric primitives to enable adaptivity on a regular spatial discretization. By controlling the states of the tilted cells both temporally and spatially, we can dynamically evolve the adaptive discretizations on an Eulerian domain. Our grid structure preserves almost all the computational merits of a uniform Cartesian grid, including the cache-coherent data layout, the easiness for parallelization, and the existence of high-performance numerical solvers. Further, our grid structure can be integrated into other adaptive grid structures, such as an Octree or a sparsely populated grid, to accommodate the T-junction-free hierarchy. We demonstrate the efficacy of our AST grid by showing examples of large-scale incompressible flow simulation in domains with irregular boundaries.
References:
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. 36, 4 (July 2017).Google ScholarDigital Library
2. Ryoichi Ando and Christopher Batty. 2020. A practical octree liquid simulator with adaptive surface resolution. ACM Transactions on Graphics 39, 4 (jul 2020). Google ScholarDigital Library
3. Ryoichi Ando, Nils Thürey, and Chris Wojtan. 2013. Highly Adaptive Liquid Simulations on Tetrahedral Meshes. ACM Trans. Graph. 32, 4, Article 103 (July 2013), 10 pages. Google ScholarDigital Library
4. Vinicius C. Azevedo and Manuel M. Oliveira. 2013. Efficient smoke simulation on curvilinear grids. Computer Graphics Forum 32, 7 (2013), 235–244. Google ScholarCross Ref
5. Christopher Batty, Florence Bertails, and Robert Bridson. 2007. A fast variational framework for accurate solid-fuid coupling. ACM Trans. Graph. 26, 3 (2007), 100. Google ScholarDigital Library
6. Christopher Batty, Stefan Xenos, and Ben Houston. 2010. Tetrahedral embedded boundary methods for accurate and flexible adaptive fluids. Computer Graphics Forum 29, 2 (2010), 695–704. Google ScholarCross Ref
7. Tyson Brochu, Christopher Batty, and Robert Bridson. 2010. Matching Fluid Simulation Elements to Surface Geometry and Topology. In ACM SIGGRAPH 2010 Papers (SIGGRAPH ’10). ACM, New York, NY, USA, Article 47, 9 pages. Google ScholarDigital Library
8. Nuttapong Chentanez, Bryan E Feldman, François Labelle, James F. O’Brien, and Jonathan R Shewchuk. 2007. Liquid simulation on lattice-based tetrahedral meshes. In Symposium on Computer Animation 2007 – ACM SIGGRAPH / Eurographics Symposium Proceedings, SCA 2007. 219–228.Google ScholarDigital Library
9. Nuttapong Chentanez and Matthias Müller. 2011. Real-time Eulerian Water Simulation Using a Restricted Tall Cell Grid. In ACM SIGGRAPH 2011 Papers (SIGGRAPH ’11). ACM, New York, NY, USA, Article 82, 10 pages. Google ScholarDigital Library
10. Pascal Clausen, Martin Wicke, Jonathan R. Shewchuk, and James F. O’Brien. 2013. Simulating Liquids and Solid-Liquid Interactions with Lagrangian Meshes. ACM Transactions on Graphics 32, 2 (April 2013), 17:1–15. https://doi.org/0.1145/2451236.2451243 Presented at SIGGRAPH 2013.Google ScholarDigital Library
11. Jonathan M Cohen, Sarah Tariq, and Simon Green. 2010. Interactive fluid-particle simulation using translating Eulerian grids. In Proceedings of I3D 2010: The 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. 15–22. Google ScholarDigital Library
12. Fernando De Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015. Power particles: An incompressible fluid solver based on power diagrams. ACM Transactions on Graphics 34, 4 (2015). Google ScholarDigital Library
13. Yoshinori Dobashi, Yasuhiro Matsuda, Tsuyoshi Yamamoto, and Tomoyuki Nishita. 2008. A Fast Simulation Method Using Overlapping Grids for Interactions between Smoke and Rigid Objects. Comput. Graph. Forum 27 (04 2008), 477–486. Google ScholarCross Ref
14. Michael G. Edwards and Hongwen Zheng. 2008. A quasi-positive family of continuous Darcy-flux finite-volume schemes with full pressure support. J. Comput. Phys. 227, 22 (2008), 9333 — 9364. Google ScholarDigital Library
15. Sharif Elcott, Yiying Tong, Eva Kanso, Peter Schröder, and Mathieu Desbrun. 2007. Stable, Circulation-preserving, Simplicial Fluids. ACM Trans. Graph. 26, 1, Article 4 (Jan. 2007). Google ScholarDigital Library
16. R. Elliot English, Linhai Qiu, Yue Yu, and Ronald Fedkiw. 2013. Chimera grids for water simulation. In Proceedings – SCA 2013: 12th ACM SIGGRAPH / Eurographics Symposium on Computer Animation. 85–94. Google ScholarDigital Library
17. Doug Enright, Duc Nguyen, Frederic Gibou, and Ron Fedkiw. 2003. Using The Particle Level Set Method And A Second Order Accurate Pressure Boundary Condition For Free Surface Flows. In In Proc. 4th ASME-JSME Joint Fluids Eng. Conf., number FEDSM2003-45144. ASME. 2003–45144.Google Scholar
18. Bryan E. Feldman, James F. O’Brien, Bryan M. Klingner, and Tolga G. Goktekin. 2005. Fluids in Deforming Meshes. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation 2005. http://graphics.berkeley.edu/papers/Feldman-FDM-2005-07/Google Scholar
19. Kai Gao and Lianjie Huang. 2017. An improved rotated staggered-grid finite-difference method with fourth-order temporal accuracy for elastic-wave modeling in anisotropic media. J. Comput. Phys. 350 (2017), 361–386. Google ScholarCross Ref
20. Ming Gao, Xinlei Wang, Kui Wu, Andre Pradhana, Eftychios Sifakis, Cem Yuksel, and Chenfanfu Jiang. 2018. GPU optimization of material point methods. SIGGRAPH Asia 2018 Technical Papers, SIGGRAPH Asia 2018 37, 6 (2018). Google ScholarDigital Library
21. Frederic Gibou, Ronald P. Fedkiw, Li-Tien Cheng, and Myungjoo Kang. 2002. A Second-order-accurate Symmetric Discretization of the Poisson Equation on Irregular Domains. J. Comput. Phys. 176, 1 (Feb. 2002), 205–227. Google ScholarDigital Library
22. Abhinav Golas, Rahul Narain, Jason Sewall, Pavel Krajcevski, Pradeep Dubey, and Ming Lin. 2012. Large-scale fluid simulation using velocity-vorticity domain decomposition. In ACM Transactions on Graphics, Vol. 31. Google ScholarDigital Library
23. Ryan Goldade, Yipeng Wang, Mridul Aanjaneya, and Christopher Batty. 2019. An adaptive variational finite difference framework for efficient symmetric octree viscosity. ACM Transactions on Graphics 38, 4 (2019), 1–14. Google ScholarDigital Library
24. F. H. Harlow and J. E. Welch. 1965. Numerical Calculation of Time-Dependent Viscous Incompressible Flow of Fluid with Free Surface. Physics of Fluids 8 (Dec. 1965), 2182–2189. Google ScholarCross Ref
25. Ben Houston, Michael B. Nielsen, Christopher Batty, Ola Nilsson, and Ken Museth. 2006. Hierarchical RLE level set. ACM Transactions on Graphics 25, 1 (2006), 151–175. Google ScholarDigital Library
26. Yuanming Hu, Mit Csail, Tzu-Mao Li, U C Berkeley, Luke Anderson, Jonathan Ragan-Kelley, Berkeley Frédo Durand, and Frédo Durand. 2019. Taichi: A Language for High-Performance Computation on Spatially Sparse Data Structures. ACM Trans. Graph 38, 6 (2019), 16. Google ScholarDigital Library
27. Yuanming Hu, Yu Fang, Ziheng Ge, Ziyin Qu, Yixin Zhu, Andre Pradhana, and Chenfanfu Jiang. 2018. A moving least squares material point method with displacement discontinuity and two-way rigid body coupling. ACM Transactions on Graphics 37, 4 (jul 2018), 1–14. Google ScholarDigital Library
28. H. Ibayashi, C. Wojtan, N. Thuerey, T. Igarashi, and R. Ando. 2018. Simulating Liquids on Dynamically Warping Grids. IEEE Transactions on Visualization and Computer Graphics (2018), 1–1. Google ScholarCross Ref
29. Geoffrey Irving, Eran Guendelman, Frank Losasso, and Ronald Fedkiw. 2006. Efficient Simulation of Large Bodies of Water by Coupling Two and Three Dimensional Techniques. In ACM SIGGRAPH 2006 Papers (SIGGRAPH ’06). ACM, New York, NY, USA, 805–811. Google ScholarDigital Library
30. Bryan M. Klingner, Bryan E. Feldman, Nuttapong Chentanez, and James F. O’Brien. 2006. Fluid Animation with Dynamic Meshes. In ACM SIGGRAPH 2006 Papers (SIGGRAPH ’06). ACM, New York, NY, USA, 820–825. Google ScholarDigital Library
31. François Labelle and Jonathan Richard Shewchuk. 2007. Isosurface stuffing: Fast tetrahedral meshes with good dihedral angles. Proceedings of the ACM SIGGRAPH Conference on Computer Graphics (2007), 1–10. Google ScholarDigital Library
32. Haixiang Liu, Yuanming Hu, Bo Zhu, Wojciech Matusik, and Eftychios Sifakis. 2018. Narrow-band topology optimization on a sparsely populated grid. SIGGRAPH Asia 2018 Technical Papers, SIGGRAPH Asia 2018 37, 6 (2018), 1–14. Google ScholarDigital Library
33. Yang Liu and Mrinal K. Sen. 2009. A new time space domain high-order finite-difference method for the acoustic wave equation. J. Comput. Phys. 228, 23 (2009), 8779 — 8806. Google ScholarDigital Library
34. Frank Losasso, Ronald Fedkiw, and Stanley Osher. 2006. Spatially adaptive techniques for level set methods and incompressible flow. Computers and Fluids 35, 10 (2006), 995–1010. Google ScholarCross Ref
35. Frank Losasso, Frédéric Gibou, and Ron Fedkiw. 2004. Simulating Water and Smoke with an Octree Data Structure. In ACM SIGGRAPH 2004 Papers (SIGGRAPH ’04). ACM, New York, NY, USA, 457–462. Google ScholarDigital Library
36. Marek Krzysztof Misztal, Robert Bridson, Kenny Erleben, Jakob Andreas Bærentzen, and François Anton. 2010. Optimization-based Fluid Simulation on Unstructured Meshes. In Workshop in Virtual Reality Interactions and Physical Simulation “VRIPHYS” (2010), Kenny Erleben, Jan Bender, and Matthias Teschner (Eds.). The Eurographics Association. Google ScholarCross Ref
37. M. K. Misztal, K. Erleben, A. Bargteil, J. Fursund, B. Bunch Christensen, J. A. Bærentzen, and R. Bridson. 2012. Multiphase flow of immiscible fluids on unstructured moving meshes. Computer Animation 2012 – ACM SIGGRAPH / Eurographics Symposium Proceedings, SCA 2012 (2012), 97–106. Google ScholarCross Ref
38. Ken Museth. 2013. VDB: High-resolution Sparse Volumes with Dynamic Topology. ACM Trans. Graph. 32, 3, Article 27 (July 2013), 22 pages. Google ScholarDigital Library
39. Michael B. Nielsen and Robert Bridson. 2016. Spatially adaptive FLIP fluid simulations in bifrost, robert bridson. In SIGGRAPH 2016 – ACM SIGGRAPH 2016 Talks. ACM Press, New York, New York, USA, 1–2. Google ScholarDigital Library
40. Michael B. Nielsen, Konstantinos Stamatelos, Morten Bojsen-Hansen, Duncan Brinsmead, Yannick Pomerleau, Marcus Nordenstam, and Robert Bridson. 2018. A collocated spatially adaptive approach to smoke simulation in bifrost. (2018), 1–2. Google ScholarDigital Library
41. Stanley Osher and Ronald Fedkiw. 2003. Level Set Methods and Dynamic Implicit Surfaces. Applied Mathematical Sciences, Vol. 153. Springer New York, New York, NY. Google ScholarCross Ref
42. Stephane Popinet. 2003. Gerris: a tree-based adaptive solver for the incompressible Euler equations in complex geometries. J. Comput. Phys. 190, 2 (2003), 572 — 600. Google ScholarDigital Library
43. N. Rasmussen, D. Enright, D. Nguyen, S. Marino, N. Sumner, W. Geiger, S. Hoon, and R. Fedkiw. 2004. Directable Photorealistic Liquids. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’04). Eurographics Association, Goslar Germany, Germany, 193–202. Google ScholarDigital Library
44. Olivier Roussel, Kai Schneider, Alexei Tsigulin, and Henning Bockhorn. 2003. A conservative fully adaptive multiresolution algorithm for parabolic PDEs. J. Comput. Phys. 188, 2 (2003), 493 — 523. Google ScholarDigital Library
45. Erik H. Saenger and Thomas Bohlen. 2004. Finite difference modeling of viscoelastic and anisotropic wave propagation using the rotated staggered grid. GEOPHYSICS 69, 2 (2004), 583–591. arXiv:https://doi.org/10.1190/1.1707078 Google ScholarCross Ref
46. Erik H. Saenger, Norbert Gold, and Serge A. Shapiro. 2000. Modeling the propagation of elastic waves using a modified finite-difference grid. Wave Motion 31, 1 (2000), 77–92. Google ScholarCross Ref
47. Rajsekhar Setaluri, Mridul Aanjaneya, Sean Bauer, and Eftychios Sifakis. 2014. SPGrid: A sparse paged grid structure applied to adaptive smoke simulation. ACM Transactions on Graphics (TOG) 33, 6 (2014), 205.Google ScholarDigital Library
48. Funshing Sin, Adam W. Bargteil, and Jessica K. Hodgins. 2009. A Point-based Method for Animating Incompressible Flow. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’09). ACM, New York, NY, USA, 247–255. Google ScholarDigital Library
49. Jos Stam. 1999. Stable Fluids. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’99). ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 121–128. Google ScholarDigital Library
50. Alexey Stomakhin, Craig Schroeder, Lawrence Chai, Joseph Teran, and Andrew Selle. 2013. A material point method for snow simulation. ACM Transactions on Graphics 32, 4 (jul 2013), 1. Google ScholarDigital Library
51. J. Teran, Neil Molino, R. Fedkiw, and R. Bridson. 2005. Adaptive physics based tetrahedral mesh generation using level sets. Engineering with Computers 21, 1 (2005), 2–18. Google ScholarCross Ref
52. Bram van Es, Barry Koren, and Hugo J. de Blank. 2014. Finite-difference schemes for anisotropic diffusion. J. Comput. Phys. 272 (2014), 526 — 549. Google ScholarCross Ref
53. Bram van Es, Barry Koren, and Hugo J. de Blank. 2016. Finite-volume Scheme for Anisotropic Diffusion. J. Comput. Phys. 306, C (Feb. 2016), 422–442. Google ScholarDigital Library
54. Chris Wojtan and Greg Turk. 2008. Fast viscoelastic behavior with thin features. ACM Transactions on Graphics 27, 3 (2008). Google ScholarDigital Library
55. Xiao Zhai, Fei Hou, Hong Qin, and Aimin Hao. 2018. Fluid Simulation with Adaptive Staggered Power Particles on GPUs. IEEE Transactions on Visualization and Computer Graphics (2018), 1–14. Google ScholarCross Ref
56. Bo Zhu, Minjae Lee, Ed Quigley, and Ronald Fedkiw. 2015. Codimensional non-Newtonian Fluids. ACM Trans. Graph. 34, 4, Article 115 (July 2015), 9 pages. Google ScholarDigital Library
57. Bo Zhu, Wenlong Lu, Matthew Cong, Byungmoon Kim, and Ronald Fedkiw. 2013. A New Grid Structure for Domain Extension. ACM Trans. Graph. 32, 4, Article 63 (July 2013), 12 pages. Google ScholarDigital Library
