“Subspace fluid re-simulation” by Kim and Delaney

  • ©Theodore Kim and John Delaney




    Subspace fluid re-simulation

Session/Category Title: Fluid Grids & Meshes




    We present a new subspace integration method that is capable of efficiently adding and subtracting dynamics from an existing high-resolution fluid simulation. We show how to analyze the results of an existing high-resolution simulation, discover an efficient reduced approximation, and use it to quickly “re-simulate” novel variations of the original dynamics. Prior subspace methods have had difficulty re-simulating the original input dynamics because they lack efficient means of handling semi-Lagrangian advection methods. We show that multi-dimensional cubature schemes can be applied to this and other advection methods, such as MacCormack advection. The remaining pressure and diffusion stages can be written as a single matrix-vector multiply, so as with previous subspace methods, no matrix inversion is needed at runtime. We additionally propose a novel importance sampling-based fitting algorithm that asymptotically accelerates the precomputation stage, and show that the Iterated Orthogonal Projection method can be used to elegantly incorporate moving internal boundaries into a subspace simulation. In addition to efficiently producing variations of the original input, our method can produce novel, abstract fluid motions that we have not seen from any other solver.


    1. Amsallem, D., and Farhat, C. 2012. Stabilization of projection-based reduced-order models. International Journal for Numerical Methods in Engineering 91, 4, 358–377.Google ScholarCross Ref
    2. An, S. S., Kim, T., and James, D. L. 2008. Optimizing Cubature for Efficient Integration of Subspace Deformations. ACM Trans. on Graphics 27, 5 (Dec.), 165. Google ScholarDigital Library
    3. Anttonen, J., King, P., and Beran, P. 2003. POD-based reduced-order models with deforming grids. Mathematical and Computer Modelling 38, 41–62. Google ScholarDigital Library
    4. Baraff, D., and Witkin, A. 1992. Dynamic simulation of non-penetrating flexible bodies. In Computer Graphics (Proceedings of SIGGRAPH 92), 303–308. Google ScholarDigital Library
    5. Barbič, J., and James, D. L. 2005. Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Trans. on Graphics 24, 3 (Aug.), 982–990. Google ScholarDigital Library
    6. Bergmann, M., Cordier, L., and Brancher, J.-P. 2005. Optimal rotary control of the cylinder wake using proper orthogonal decomposition reduced-order model. Physics of Fluids 17, 9, 097101.Google ScholarCross Ref
    7. Berkooz, G., Holmes, P., and Lumley, J. L. 1993. The proper orthogonal decomposition in the analysis of turbulent flows. Annual Rev. Fluid Mech, 539–575.Google Scholar
    8. Bourguet, R., Braza, M., and Dervieux, A. 2011. Reduced-order modeling of transonic flows around an airfoil submitted to small deformations. Journal of Computational Physics 230, 1, 159–184. Google ScholarDigital Library
    9. Bro, R., and De Jong, S. 1997. A fast non-negativity-constrained least squares algorithm. Journal of Chemometrics 11, 5, 393–401.Google ScholarCross Ref
    10. Bro, R., 2001. The n-way toolbox. http://bit.ly/Wmq8zM.Google Scholar
    11. Brochu, T., Keeler, T., and Bridson, R. 2012. Linear-time smoke animation with vortex sheet meshes. In Proceedings of the ACM SIGGRAPH/Eurographics Sym. on Computer Animation, 87–95. Google ScholarDigital Library
    12. Carlberg, K., Bou-Mosleh, C., and Farhat, C. 2011. Efficient non-linear model reduction via a least-squares petrovgalerkin projection and compressive tensor approximations. International Journal for Numerical Methods in Engineering 86, 2, 155–181.Google ScholarCross Ref
    13. Chadwick, J. N., An, S. S., and James, D. L. 2009. Harmonic shells: a practical nonlinear sound model for near-rigid thin shells. ACM Trans. Graph. 28, 5 (Dec.), 119:1–119:10. Google ScholarDigital Library
    14. Chen, D., and Plemmons, R. 2007. Nonnegativity constraints in numerical analysis. In Symposium on the Birth of Numerical Analysis.Google Scholar
    15. De Witt, T., Lessig, C., and Fiume, E. 2012. Fluid simulation using laplacian eigenfunctions. ACM Trans. Graph. 31, 1, 10:1–10:11. Google ScholarDigital Library
    16. Deparis, S., and Rozza, G. 2009. Reduced basis method for multi-parameter-dependent steady navierstokes equations: Applications to natural convection in a cavity. Journal of Computational Physics 228, 12, 4359–4378. Google ScholarDigital Library
    17. Fedkiw, R., Stam, J., and Jensen, H. W. 2001. Visual simulation of smoke. In Proceedings of SIGGRAPH, 15–22. Google ScholarDigital Library
    18. Foster, N., and Metaxas, D. 1997. Modeling the motion of a hot, turbulent gas. In Proceedings of SIGGRAPH, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 181–188. Google ScholarDigital Library
    19. Golub, G., and Van Loan, C. 1996. Matrix Computations, 3rd ed. The Johns Hopkins University Press, Baltimore. Google ScholarDigital Library
    20. Guennebaud, G., Jacob, B., et al., 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
    21. Henderson, R. D. 2012. Scalable fluid simulation in linear time on shared memory multiprocessors. In Proceedings of the Digital Production Symposium, ACM Press, 43–52. Google ScholarDigital Library
    22. Homescu, C., Petzold, L. R., and Serban, R. 2005. Error estimation for reduced-order models of dynamical systems. SIAM Journal on Numerical Analysis 43, 4, 1693–1714. Google ScholarDigital Library
    23. James, D. L., and Fatahalian, K. 2003. Precomputing interactive dynamic deformable scenes. ACM Transactions on Graphics 22, 3 (July), 879–887. Google ScholarDigital Library
    24. Kim, T., and James, D. L. 2009. Skipping steps in deformable simulation with online model reduction. ACM Transactions on Graphics 28, 5 (Dec.), 123:1–123:9. Google ScholarDigital Library
    25. Kim, T., and James, D. L. 2011. Physics-based character skinning using multi-domain subspace deformations. In ACM SIGGRAPH/Eurographics Sym. on Computer Animation, ACM, New York, NY, USA, 63–72. Google ScholarDigital Library
    26. Kim, T., Thürey, N., James, D., and Gross, M. 2008. Wavelet turbulence for fluid simulation. ACM Trans. Graph. 27 (August), 50:1–50:6. Google ScholarDigital Library
    27. Kim, D., Sra, S., and Dhillon, I. S. 2012. A non-monotonic method for large-scale non-negative least squares. Optimization Methods and Software (OMS) (Jan.).Google Scholar
    28. Kleinberg, J., and Tardos, E. 2006. Algorithm Design. Addison-Wesley. Google ScholarDigital Library
    29. Klingner, B. M., Feldman, B. E., Chentanez, N., and O’Brien, J. F. 2006. Fluid animation with dynamic meshes. In Proceedings of SIGGRAPH, 820–825. Google ScholarDigital Library
    30. Krysl, P., Lall, S., and Marsden, J. E. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. International Journal for Numerical Methods in Engineering 51, 479–504.Google ScholarCross Ref
    31. Lawson, C. L., and Hanson, R. J. 1974. Solving Least Square Problems. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
    32. LeGresley, P. A., and Alonso, J. J. 2001. Investigation of non-linear projection for pod based reduced order models for aerodynamics. In AIAA Aerospace Sciences Meeting and Exhibit.Google Scholar
    33. Lentine, M., Zheng, W., and Fedkiw, R. 2010. A novel algorithm for incompressible flow using only a coarse grid projection. ACM Trans. Graph. 29 (July), 114:1–114:9. Google ScholarDigital Library
    34. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Trans. Graph. 23, 457–462. Google ScholarDigital Library
    35. Lumley, J. 1967. The structure of inhomogeneous turbulent flows. Atmospheric turbulence and radio wave propagation, 166–178.Google Scholar
    36. Luo, Y., and Duraiswami, R. 2011. Efficient parallel nonnegative least squares on multicore architectures. SIAM Journal on Scientific Computing 33, 5, 2848–2863. Google ScholarDigital Library
    37. Meyer, M., and Anderson, J. 2007. Key Point Subspace Acceleration and Soft Caching. ACM Transactions on Graphics 26, 3 (July), 74. Google ScholarDigital Library
    38. Moës, N., Dolbow, J., and Belytschko, T. 1999. A finite element method for crack growth without remeshing. International Journal for Numerical Methods in Engineering 46, 1, 131–150.Google ScholarCross Ref
    39. Molemaker, J., Cohen, J. M., Patel, S., and Noh, J. 2008. Low viscosity flow simulations for animation. In ACM SIGGRAPH/Eurographics Sym. on Computer Animation, 9–18. Google ScholarDigital Library
    40. Moler, C., and Van Loan, C. 2003. Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Review 45, 1, 3–49.Google ScholarDigital Library
    41. Mullen, P., Crane, K., Pavlov, D., Tong, Y., and Desbrun, M. 2009. Energy-preserving integrators for fluid animation. ACM Trans. Graph. 28, 3 (July), 38:1–38:8. Google ScholarDigital Library
    42. Narain, R., Sewall, J., Carlson, M., and Lin, M. C. 2008. Fast animation of turbulence using energy transport and procedural synthesis. ACM Trans. Graph. 27 (December), 166:1–166:8. Google ScholarDigital Library
    43. Pentland, A., and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. In Computer Graphics (Proceedings of SIGGRAPH 89), 215–222. Google ScholarDigital Library
    44. Pfaff, T., Thuerey, N., and Gross, M. 2012. Lagrangian vortex sheets for animating fluids. ACM Trans. Graph. 31, 4 (July), 112:1–112:8. Google ScholarDigital Library
    45. Pharr, M., and Humphreys, G. 2010. Physically-Based Rendering: From Theory to Implementation. Morgan Kaufmann. Google ScholarDigital Library
    46. Portugal, L. F., Júdice, J. J., and Vicente, L. N. 1994. A comparison of block pivoting and interior-point algorithms for linear least squares problems with nonnegative variables. Mathematics of Computation 63, 208 (Oct.), 625–643. Google ScholarDigital Library
    47. Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 1992. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, New York, NY, USA. Google ScholarDigital Library
    48. Rabani, E., and Toledo, S. 2001. Out-of-core svd and qr decompositions. In SIAM Conference on Parallel Processing for Scientific Computing.Google Scholar
    49. Schechter, H., and Bridson, R. 2008. Evolving sub-grid turbulence for smoke animation. In ACM SIGGRAPH/Eurographics Sym. on Computer Animation, 1–7. Google ScholarDigital Library
    50. Selle, A., Fedkiw, R., Kim, B., Liu, Y., and Rossignac, J. 2008. An unconditionally stable maccormack method. J. Sci. Comput. 35, 2–3 (June), 350–371. Google ScholarDigital Library
    51. Seo, J., Irving, G., Lewis, J. P., and Noh, J. 2011. Compression and direct manipulation of complex blendshape models. ACM Trans. Graph. 30, 6 (Dec.), 164:1–164:10. Google ScholarDigital Library
    52. Serre, G., Lafon, P., Gloerfelt, X., and Bailly, C. 2012. Reliable reduced-order models for time-dependent linearized euler equations. Journal of Computational Physics 231, 15, 5176–5194. Google ScholarDigital Library
    53. Sethian, J. 1999. Level set methods and fast marching methods. Cambridge University Press.Google Scholar
    54. Shah, A. 2007. Cooking effects. In ACM SIGGRAPH 2007 courses, ACM, New York, NY, USA, SIGGRAPH ’07, 45–58. Google ScholarDigital Library
    55. Sifakis, E., and Barbič, J. 2012. Fem simulation of 3d deformable solids: a practitioner’s guide to theory, discretization and model reduction. In ACM SIGGRAPH 2012 Courses, ACM, New York, NY, USA, SIGGRAPH ’12, 20:1–20:50. Google ScholarDigital Library
    56. Stam, J. 1999. Stable fluids. In SIGGRAPH 1999, 121–128. Google ScholarDigital Library
    57. Stanton, M., Sheng, Y., Wicke, M., Perazzi, F., Yuen, A., and andAdrien Treuille, S. N. 2013. Non-polynomial galerkin projection on deforming meshes. ACM Trans. Graph. 32 (July). Google ScholarDigital Library
    58. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. ACM Transactions on Graphics 25, 3 (July), 826–834. Google ScholarDigital Library
    59. Vasilescu, M. A. O., and Terzopoulos, D. 2004. Tensortextures: multilinear image-based rendering. ACM Trans. Graph. 23, 3 (Aug.), 336–342. Google ScholarDigital Library
    60. Wicke, M., Stanton, M., and Treuille, A. 2009. Modular bases for fluid dynamics. ACM Trans. on Graphics 28, 3 (Aug.), 39. Google ScholarDigital Library

ACM Digital Library Publication: