“Subspace fluid re-simulation” by Kim and Delaney
Conference:
Type(s):
Title:
- Subspace fluid re-simulation
Session/Category Title: Fluid Grids & Meshes
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
