“Preserving geometry and topology for fluid flows with thin obstacles and narrow gaps” by Azevedo

  • ©Vinicius C. Azevedo, Christopher Batty, and Manuel M. Oliveira




    Preserving geometry and topology for fluid flows with thin obstacles and narrow gaps

Session/Category Title:   SOUND, FLUIDS & BOUNDARIES




    Fluid animation methods based on Eulerian grids have long struggled to resolve flows involving narrow gaps and thin solid features. Past approaches have artificially inflated or voxelized boundaries, although this sacrifices the correct geometry and topology of the fluid domain and prevents flow through narrow regions. We present a boundary-respecting fluid simulator that overcomes these challenges. Our solution is to intersect the solid boundary geometry with the cells of a background regular grid to generate a topologically correct, boundary-conforming cut-cell mesh. We extend both pressure projection and velocity advection to support this enhanced grid structure. For pressure projection, we introduce a general graph-based scheme that properly preserves discrete incompressibility even in thin and topologically complex flow regions, while nevertheless yielding symmetric positive definite linear systems. For advection, we exploit polyhedral interpolation to improve the degree to which the flow conforms to irregular and possibly non-convex cell boundaries, and propose a modified PIC/FLIP advection scheme to eliminate the need to inaccurately reinitialize invalid cells that are swept over by moving boundaries. The method naturally extends the standard Eulerian fluid simulation framework, and while we focus on thin boundaries, our contributions are beneficial for volumetric solids as well. Our results demonstrate successful one-way fluid-solid coupling in the presence of thin objects and narrow flow regions even on very coarse grids.


    1. Aftosmis, M. J., Berger, M. J., and Melton, J. E. 1998. Robust and efficient Cartesian mesh generation for component-based geometry. AIAA Journal 36, 6, 952–960.Google ScholarCross Ref
    2. Batty, C., Bertails, F., and Bridson, R. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Trans. Graph. 26, 3, 100. Google ScholarDigital Library
    3. Batty, C., Xenos, S., and Houston, B. 2010. Tetrahedral embedded boundary methods for accurate and flexible adaptive fluids. Computer Graphics Forum (Eurographics) 29, 2, 695–704.Google ScholarCross Ref
    4. Bojsen-Hansen, M., and Wojtan, C. 2013. Liquid surface tracking with error compensation. ACM Trans. Graph. 32, 4, 79:1–79:10. Google ScholarDigital Library
    5. Brochu, T., Batty, C., and Bridson, R. 2010. Matching fluid simulation elements to surface geometry and topology. ACM Trans. Graph. 29, 4, 47. Google ScholarDigital Library
    6. CGAL. 2016. CGAL User and Reference Manual, 4.8 ed. CGAL Editorial Board.Google Scholar
    7. Chentanez, N., Goktekin, T. G., Feldman, B. E., and O’Brien, J. F. 2006. Simultaneous coupling of fluids and deformable bodies. In Symp. on Computer Animation, 83–89. Google ScholarDigital Library
    8. Chentanez, N., Feldman, B. E., Labelle, F., O’Brien, J. F., and Shewchuk, J. R. 2007. Liquid simulation on lattice-based tetrahedral meshes. In Symp. on Computer Animation, 219–228. Google ScholarDigital Library
    9. Clausen, P., Wicke, M., Shewchuk, J. R., and O’Brien, J. F. 2013. Simulating liquids and solid-liquid interactions with Lagrangian meshes. ACM Trans. Graph. 32, 2, 17. Google ScholarDigital Library
    10. Crockett, R. K., Colella, P., and Graves, D. T. 2011. A Cartesian grid embedded boundary method for solving the Poisson and heat equations with discontinuous coefficients in three dimensions. J. Comp. Phys. 230, 7, 2451–2469. Google ScholarDigital Library
    11. Day, M., Colella, P., Lijewski, M., Rendleman, C., and Marcus, D. 1998. Embedded boundary algorithms for solving the Poisson equation on Complex Domains. Tech. rep., LBNL.Google Scholar
    12. Dick, C., Rogowsky, M., and Westermann, R. 2016. Solving the fluid pressure Poisson equation using multigrid – evaluation and improvements. IEEE TVCG.Google Scholar
    13. Edwards, E., and Bridson, R. 2014. Detailed water with coarse grids: Combining surface meshes and adaptive discontinuous Galerkin. ACM Trans. Graph. 33, 4, 136:1–136:9. Google ScholarDigital Library
    14. Elcott, S., Tong, Y., Kanso, E., Schröder, P., and Desbrun, M. 2007. Stable, circulation-preserving, simplicial fluids. ACM Trans. Graph. 26, 1, 4. Google ScholarDigital Library
    15. 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 Proceedings of the 4th ASME-JSME Joint Fluids Engineering Conference, ASME, 337–342.Google Scholar
    16. Fedkiw, R., Stam, J., and Jensen, H. W. 2001. Visual simulation of smoke. In SIGGRAPH, 15–22. Google ScholarDigital Library
    17. Feldman, B. E., O’Brien, J. F., and Klingner, B. M. 2005. Animating gases with hybrid meshes. ACM Trans. Graph. 24, 3 (jul), 904–909. Google ScholarDigital Library
    18. Ferstl, F., Westermann, R., and Dick, C. 2014. Large-scale liquid simulation on adaptive octree grids. IEEE TVCG Preprint.Google Scholar
    19. Guendelman, E., Selle, A., Losasso, F., and Fedkiw, R. 2005. Coupling water and smoke to thin deformable and rigid shells. ACM Trans. Graph. 24, 3, 973–981. Google ScholarDigital Library
    20. Hellrung, J., Wang, L., Sifakis, E., and Teran, J. 2012. A second order virtual node method for elliptic problems with interfaces and irregular domains. J. Comp. Phys. 231, 4, 2015–2048. Google ScholarDigital Library
    21. Houston, B., Bond, C., and Wiebe, M. 2003. A unified approach for modeling complex occlusions in fluid simulations. In SIGGRAPH Sketches. Google ScholarDigital Library
    22. Johansen, H., and Colella, P. 1998. A Cartesian grid embedded boundary method for Poisson’s equation on irregular domains. J. Comp. Phys. 147, 1 (nov), 60–85. Google ScholarDigital Library
    23. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3, 561–566. Google ScholarDigital Library
    24. Kim, D., Song, O.-y., and Ko, H.-S. 2009. Stretching and wiggling liquids. ACM Trans. Graph. 28, 5, 120. Google ScholarDigital Library
    25. Klingner, B. M., Feldman, B. E., Chentanez, N., and O’Brien, J. F. 2006. Fluid animation with dynamic meshes. ACM Trans. Graph. 25, 3, 820–825. Google ScholarDigital Library
    26. Labelle, F., and Shewchuk, J. R. 2007. Isosurface stuffing: Fast tetrahedral meshes with good dihedral angles. ACM Trans. Graph. 26, 3, 57. Google ScholarDigital Library
    27. Langer, T., Belyaev, A., and Seidel, H.-P. 2006. Spherical barycentric coordinates. In Eurographics Symposium on Geometry Processing, 81–88. Google ScholarDigital Library
    28. Lenaerts, T., and Dutré, P. 2008. Unified SPH model for fluid-shell simulations. Tech. rep., Katholieke Universiteit Leuven.Google Scholar
    29. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Trans. Graph. 23, 3 (aug), 457–462. Google ScholarDigital Library
    30. Losasso, F., Fedkiw, R., and Osher, S. 2005. Spatially adaptive techniques for level set methods and incompressible flow. Computers & Fluids 35, 10, 995–1010.Google ScholarCross Ref
    31. Misztal, M., Bridson, R., Erleben, K., Baerentzen, A., and Anton, F. 2010. Optimization-based fluid simulation on unstructured meshes. In VRIPHYS.Google Scholar
    32. Mittal, R., and Iaccarino, G. 2005. Immersed boundary methods. Annual review of fluid mechanics 37, 239–261.Google Scholar
    33. Molino, N., Bao, Z., and Fedkiw, R. 2004. A virtual node algorithm for changing mesh topology during simulation. ACM Trans. Graph. 23, 3 (aug), 385–392. Google ScholarDigital Library
    34. Nesme, M., Kry, P. G., Jevrábková, L., and Faure, F. 2009. Preserving topology and elasticity for embedded deformable models. ACM Trans. Graph. 28, 3, 52. Google ScholarDigital Library
    35. Ng, Y. T., Min, C., and Gibou, F. 2009. An efficient fluid-solid coupling algorithm for single-phase flows. J. Comp. Phys. 228, 23, 8807–8829. Google ScholarDigital Library
    36. Ozgen, O., Kallmann, M., Ramirez, L., and Coimbra, C. 2010. Underwater cloth simulation with fractional derivatives. ACM Trans. Graph. 29, 3, 23. Google ScholarDigital Library
    37. Purvis, J. W., and Burkhalter, J. E. 1979. Prediction of critical Mach number for store configurations. AIAA Journal 17, 11, 1170–1177.Google ScholarCross Ref
    38. Qiu, L., Yu, Y., and Fedkiw, R. 2015. On thin gaps between rigid bodies two-way coupled to incompressible flow.Google Scholar
    39. Rasmussen, N., Enright, D., Nguyen, D., Marino, S., Sumner, N., Geiger, W., Hoon, S., and Fedkiw, R. 2004. Directable photorealistic liquids. In Symposium on Computer Animation, 193–202. Google ScholarDigital Library
    40. Robinson-Mosher, A., Shinar, T., Gretarsson, J., Su, J., and Fedkiw, R. 2008. Two-way coupling of fluids to rigid and deformable solids and shells. ACM Trans. Graph. 27, 3, 46. Google ScholarDigital Library
    41. Robinson-Mosher, A., English, R. E., and Fedkiw, R. 2009. Accurate tangential velocities for solid fluid coupling. In Symposium on Computer Animation, 227–236. Google ScholarDigital Library
    42. Roble, D., bin Zafar, N., and Falt, H. 2005. Cartesian grid fluid simulation with irregular boundary voxels. In SIGGRAPH Sketches, 138. Google ScholarDigital Library
    43. Rosatti, G., Cesari, D., and Bonaventura, L. 2005. Semi-implicit, semi-Lagrangian modelling for environmental problems on staggered Cartesian grids with cut cells. J. Comp. Phys. 204, 1 (mar), 353–377. Google ScholarDigital Library
    44. Schwartz, P., Barad, M., Colella, P., and Ligocki, T. 2006. A Cartesian grid embedded boundary method for the heat equation and Poisson’s equation in three dimensions. J. Comp. Phys. 211, 2, 531–550. Google ScholarDigital Library
    45. Selle, A., Fedkiw, R., Kim, B., Liu, Y., and Rossignac, J. 2008. An unconditionally stable MacCormack method. SIAM J. Sci. Comput. 35, 2-3, 350–371. Google ScholarDigital Library
    46. Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In ACM ’68 Proceedings of the 1968 23rd ACM national conference, 517–524. Google ScholarDigital Library
    47. Sifakis, E., Der, K., and Fedkiw, R. 2007. Arbitrary cutting of deformable tetrahedralized objects. In Symposium on Computer Animation, 73–80. Google ScholarDigital Library
    48. Sin, F., Bargteil, A. W., and Hodgins, J. K. 2009. A point-based method for animating incompressible flow. In Symposium on Computer Animation, ACM Press, 247–255. Google ScholarDigital Library
    49. Stam, J. 1999. Stable fluids. In SIGGRAPH, 121–128. Google ScholarDigital Library
    50. Teran, J., Sifakis, E., Blemker, S. S., Ng-Thow-Hing, V., Lau, C., and Fedkiw, R. 2005. Creating and simulating skeletal muscle from the visible human data set. IEEE TVCG 11, 3, 317–328. Google ScholarDigital Library
    51. Wang, K., Gretarsson, J., Main, A., and Farhat, C. 2012. Computational algorithms for tracking dynamic fluidstructure interfaces in embedded boundary methods. International Journal for Numerical Methods in Fluids 70, 4, 515–535.Google ScholarCross Ref
    52. Wang, Y., Jiang, C., Schroeder, C., and Teran, J. 2014. An adaptive virtual node algorithm with robust mesh cutting. In Symposium on Computer Animation, 77–85. Google ScholarDigital Library
    53. Weber, D., Mueller-Roemer, J., Stork, A., and Fellner, D. 2015. A cut-cell geometric multigrid Poisson solver for fluid simulation. Computer Graphics Forum 34, 2, 481–491. Google ScholarDigital Library
    54. Wojtan, C., Thuerey, N., Gross, M., and Turk, G. 2010. Physically-inspired topology changes for thin fluid features. ACM Trans. Graph. 29, 3, 50. Google ScholarDigital Library
    55. Zheng, W., Zhu, B., Kim, B., and Fedkiw, R. 2015. A new incompressibility discretization for a hybrid particle MAC grid representation with surface tension. J. Comp. Phys. 280, 1, 96–142. Google ScholarDigital Library
    56. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 3 (jul), 965–972. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: