“A new grid structure for domain extension” by Zhu, Lu, Cong, Kim and Fedkiw

  • ©Bo Zhu, Wenlong Lu, Matthew Cong, Byungmoon Kim, and Ronald Fedkiw




    A new grid structure for domain extension


Session Title: Fluid Grids & Meshes



    We present an efficient grid structure that extends a uniform grid to create a significantly larger far-field grid by dynamically extending the cells surrounding a fine uniform grid while still maintaining fine resolution about the regions of interest. The far-field grid preserves almost every computational advantage of uniform grids including cache coherency, regular subdivisions for parallelization, simple data layout, the existence of efficient numerical discretizations and algorithms for solving partial differential equations, etc. This allows fluid simulations to cover large domains that are often infeasible to enclose with sufficient resolution using a uniform grid, while still effectively capturing fine scale details in regions of interest using dynamic adaptivity.


    1. Adams, B., Pauly, M., Keiser, R., and Guibas, L. J. 2007. Adaptively sampled particle fluids. ACM Trans. Graph. (SIGGRAPH Proc.) 26, 3. Google ScholarDigital Library
    2. Anderson, D. A., Tannehill, J. C., and Pletcher, R. H. 1997. Computational Fluid Mchanics and Heat Transfer. Taylor & Francis, 531.Google Scholar
    3. Benek, J. A., Steger, J. L., and Dougherty, F. C. 1983. A flexible grid embedding technique with applications to the euler equations. In 6th Computational Fluid Dynamics Conference, AIAA, 373–382.Google Scholar
    4. Benek, J. A., Buning, P. G., and Steger, J. L. 1985. A 3–d chimera grid embedding technique. In 7th Computational Fluid Dynamics Conference, AIAA, 322–331.Google Scholar
    5. Berger, M., and Colella, P. 1989. Local adaptive mesh refinement for shock hydrodynamics. J. Comput. Phys. 82, 64–84. Google ScholarDigital Library
    6. Berger, M., and Oliger, J. 1984. Adaptive mesh refinement for hyperbolic partial differential equations. J. Comput. Phys. 53, 484–512.Google ScholarCross Ref
    7. Brochu, T., Batty, C., and Bridson, R. 2010. Matching fluid simulation elements to surface geometry and topology. ACM Trans. Graph. (SIGGRAPH Proc.), 47:1–47:9. Google ScholarDigital Library
    8. Chentanez, N., and Müller, M. 2011. Real-time eulerian water simulation using a restricted tall cell grid. ACM Trans. Graph. (SIGGRAPH Proc.) 30, 4, 82:1–82:10. Google ScholarDigital Library
    9. Cohen, J. M., Tariq, S., and Green, S. 2010. Interactive fluid-particle simulation using translating eulerian grids. In Proc. of the 2010 ACM SIGGRAPH Symp. on Interactive 3D Graphics and Games, 15–22. Google ScholarDigital Library
    10. Dobashi, Y., Matsuda, Y., Yamamoto, T., and Nishita, T. 2008. A fast simulation method using overlapping grids for interactions between smoke and rigid objects. Comput. Graph. Forum 27, 2, 477–486.Google ScholarCross Ref
    11. Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Trans. Graph. (SIGGRAPH Proc.) 21, 3, 736–744. Google ScholarDigital Library
    12. Enright, D., Nguyen, D., Gibou, F., and Fedkiw, R. 2003. Using the particle level set method and a second order accurate pressure boundary condition for free surface flows. In Proc. 4th ASME-JSME Joint Fluids Eng. Conf., number FEDSM2003–45144. ASME.Google Scholar
    13. Fedkiw, R., Stam, J., and Jensen, H. 2001. Visual simulation of smoke. In Proc. of ACM SIGGRAPH 2001, 15–22. Google ScholarDigital Library
    14. Feldman, B., O’Brien, J., Klingner, B., and Goktekin, T. 2005. Fluids in deforming meshes. In Proc. of the ACM SIGGRAPH/Eurographics Symp. on Comput. Anim., 255–259. Google ScholarDigital Library
    15. Golas, A., Narain, R., Sewall, J., Krajcevski, P., Dubey, P., and Lin, M. 2012. Large-scale fluid simulation using velocity-vorticity domain decomposition. ACM Trans. Graph. 31, 6, 148:1–148:9. Google ScholarDigital Library
    16. Hong, J., Shinar, T., and Fedkiw, R. 2007. Wrinkled flames and cellular patterns. ACM Trans. Graph. (SIGGRAPH Proc.) 26, 3, 47. Google ScholarDigital Library
    17. Houston, B., Nielsen, M., Batty, C., Nilsson, O., and Museth, K. 2006. Hierarchical RLE level set: A compact and versatile deformable surface representation. ACM Trans. Graph. 25, 1, 1–24. Google ScholarDigital Library
    18. 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. (SIGGRAPH Proc.) 25, 3, 805–811. Google ScholarDigital Library
    19. Kim, B.-M., Liu, Y., Llamas, I., and Rossignac, J. 2005. Flowfixer: Using BFECC for fluid simulation. In Eurographics Workshop on Natural Phenomena 2005. Google ScholarDigital Library
    20. Klingner, B. M., Feldman, B. E., Chentanez, N., and O’Brien, J. F. 2006. Fluid animation with dynamic meshes. ACM Trans. Graph. (SIGGRAPH Proc.) 25, 3, 820–825. Google ScholarDigital Library
    21. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Trans. Graph. (SIGGRAPH Proc.) 23, 457–462. Google ScholarDigital Library
    22. Losasso, F., Talton, J., Kwatra, N., and Fedkiw, R. 2008. Two-way coupled sph and particle level set fluid simulation. IEEE TVCG 14, 4, 797–804. Google ScholarDigital Library
    23. Nguyen, D., Fedkiw, R., and Jensen, H. 2002. Physically based modeling and animation of fire. ACM Trans. Graph. (SIGGRAPH Proc.) 21, 721–728. Google ScholarDigital Library
    24. Rasmussen, N., Enright, D., Nguyen, D., Marino, S., Sumner, N., Geiger, W., Hoon, S., and Fedkiw, R. 2004. Directable photorealistic liquids. In Proc. of the 2004 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim., 193–202. Google ScholarDigital Library
    25. Selle, A., Rasmussen, N., and Fedkiw, R. 2005. A vortex particle method for smoke, water and explosions. ACM Trans. Graph. (SIGGRAPH Proc.) 24, 3, 910–914. Google ScholarDigital Library
    26. Selle, A., Fedkiw, R., Kim, B., Liu, Y., and Rossignac, J. 2008. An Unconditionally Stable MacCormack Method. J. Sci. Comp. 35, 2, 350–371. Google ScholarDigital Library
    27. Shah, M., Cohen, J. M., Patel, S., Lee, P., and Pighin, F. 2004. Extended galilean invariance for adaptive fluid simulation. In Proc. of the 2004 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim., 213–221. Google ScholarDigital Library
    28. Sin, F., Bargteil, A. W., and Hodgins, J. K. 2009. A point-based method for animating incompressible flow. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim., ACM, New York, NY, USA, SCA ’09, 247–255. Google ScholarDigital Library
    29. Söderström, A., Karlsson, M., and Museth, K. 2010. A pml-based nonreflective boundary for free surface fluid animation. ACM Trans. Graph. 29, 5, 136:1–136:17. Google ScholarDigital Library
    30. Solenthaler, B., and Gross, M. 2011. Two-scale particle simulation. ACM Trans. Graph. (SIGGRAPH Proc.) 30, 4, 81:1–81:8. Google ScholarDigital Library
    31. Solenthaler, B., and Pajarola, R. 2009. Predictive-corrective incompressible sph. ACM Trans. Graph. (SIGGRAPH Proc.) 28, 3, 40:1–40:6. Google ScholarDigital Library
    32. Stam, J. 1999. Stable fluids. In Proc. of SIGGRAPH 99, 121–128. Google ScholarDigital Library
    33. Sussman, M., and Smereka, P. 1997. Axisymmetric free boundary problems. J. Fluid Mech. 341, 269–294.Google ScholarCross Ref
    34. Sussman, M., Algrem, A. S., Bell, J. B., Colella, P., Howell, L. H., and Welcome, M. L. 1999. An adaptive level set approach for incompressible two-phase flow. J. Comput. Phys 148, 81–124. Google ScholarDigital Library
    35. Takizawa, K., Yabe, T., Tsugawa, Y., Tezduyar, T. E., and Mizoe, H. 2007. Computation of free-surface flows and fluid object interactions with the cip method based on adaptive meshless soroban grids. Comput. Mech. 40, 1, 167–183.Google ScholarCross Ref
    36. Yabe, T., Mizoe, H., Takizawa, K., Moriki, H., Im, H.-N., and Ogata, Y. 2004. Higher-order schemes with cip method and adaptive soroban grid towards mesh-free scheme. J. Comput. Phys. 194, 1. Google ScholarDigital Library
    37. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. (SIGGRAPH Proc.) 24, 3, 965–972. Google ScholarDigital Library

ACM Digital Library Publication: