More Web Proxy on the site http://driver.im/

research-article

Subspace fluid re-simulation

Authors:

John DelaneyAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 32, Issue 4

Article No.: 62, Pages 1 - 9

https://doi.org/10.1145/2461912.2461987

Published: 21 July 2013 Publication History

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.

Supplementary Material

ZIP File (a62-kim.zip)

Supplemental material.

Download
171.53 MB

MP4 File (tp104.mp4)

Download
21.23 MB

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.

[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.

Digital 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.

Digital Library

[4]

Baraff, D., and Witkin, A. 1992. Dynamic simulation of non-penetrating flexible bodies. In Computer Graphics (Proceedings of SIGGRAPH 92), 303--308.

Digital 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.

Digital 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.

[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.

[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.

Digital Library

[9]

Bro, R., and De Jong, S. 1997. A fast non-negativity-constrained least squares algorithm. Journal of Chemometrics 11, 5, 393--401.

[10]

Bro, R., 2001. The n-way toolbox. http://bit.ly/Wmq8zM.

[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.

Digital 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.

[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.

Digital Library

[14]

Chen, D., and Plemmons, R. 2007. Nonnegativity constraints in numerical analysis. In Symposium on the Birth of Numerical Analysis.

[15]

De Witt, T., Lessig, C., and Fiume, E. 2012. Fluid simulation using laplacian eigenfunctions. ACM Trans. Graph. 31, 1, 10:1--10:11.

Digital 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.

Digital Library

[17]

Fedkiw, R., Stam, J., and Jensen, H. W. 2001. Visual simulation of smoke. In Proceedings of SIGGRAPH, 15--22.

Digital 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.

Digital Library

[19]

Golub, G., and Van Loan, C. 1996. Matrix Computations, 3rd ed. The Johns Hopkins University Press, Baltimore.

Digital Library

[20]

Guennebaud, G., Jacob, B., et al., 2010. Eigen v3. http://eigen.tuxfamily.org.

[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.

Digital 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.

Digital Library

[23]

James, D. L., and Fatahalian, K. 2003. Precomputing interactive dynamic deformable scenes. ACM Transactions on Graphics 22, 3 (July), 879--887.

Digital 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.

Digital 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.

Digital 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.

Digital 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.).

[28]

Kleinberg, J., and Tardos, E. 2006. Algorithm Design. Addison-Wesley.

Digital 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.

Digital 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.

[31]

Lawson, C. L., and Hanson, R. J. 1974. Solving Least Square Problems. Prentice Hall, Englewood Cliffs, NJ.

[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.

[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.

Digital 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.

Digital Library

[35]

Lumley, J. 1967. The structure of inhomogeneous turbulent flows. Atmospheric turbulence and radio wave propagation, 166--178.

[36]

Luo, Y., and Duraiswami, R. 2011. Efficient parallel nonnegative least squares on multicore architectures. SIAM Journal on Scientific Computing 33, 5, 2848--2863.

Digital Library

[37]

Meyer, M., and Anderson, J. 2007. Key Point Subspace Acceleration and Soft Caching. ACM Transactions on Graphics 26, 3 (July), 74.

Digital 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.

[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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital Library

[45]

Pharr, M., and Humphreys, G. 2010. Physically-Based Rendering: From Theory to Implementation. Morgan Kaufmann.

Digital 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.

Digital 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.

Digital Library

[48]

Rabani, E., and Toledo, S. 2001. Out-of-core svd and qr decompositions. In SIAM Conference on Parallel Processing for Scientific Computing.

[49]

Schechter, H., and Bridson, R. 2008. Evolving sub-grid turbulence for smoke animation. In ACM SIGGRAPH/Eurographics Sym. on Computer Animation, 1--7.

Digital 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.

Digital 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.

Digital 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.

Digital Library

[53]

Sethian, J. 1999. Level set methods and fast marching methods. Cambridge University Press.

[54]

Shah, A. 2007. Cooking effects. In ACM SIGGRAPH 2007 courses, ACM, New York, NY, USA, SIGGRAPH '07, 45--58.

Digital 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.

Digital Library

[56]

Stam, J. 1999. Stable fluids. In SIGGRAPH 1999, 121--128.

Digital 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).

Digital 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.

Digital Library

[59]

Vasilescu, M. A. O., and Terzopoulos, D. 2004. Tensortextures: multilinear image-based rendering. ACM Trans. Graph. 23, 3 (Aug.), 336--342.

Digital Library

[60]

Wicke, M., Stanton, M., and Treuille, A. 2009. Modular bases for fluid dynamics. ACM Trans. on Graphics 28, 3 (Aug.), 39.

Digital Library

Cited By

Hernández JBravo JAres de Parga S(2024)CECM: A continuous empirical cubature method with application to the dimensional hyperreduction of parameterized finite element modelsComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2023.116552418(116552)Online publication date: Jan-2024
https://doi.org/10.1016/j.cma.2023.116552
Wang XXu YLiu SRen BKosinka JTelea AWang JSong CChang JLi CZhang JBan X(2024)Physics-based fluid simulation in computer graphics: Survey, research trends, and challengesComputational Visual Media10.1007/s41095-023-0368-y10:5(803-858)Online publication date: 27-Apr-2024
https://doi.org/10.1007/s41095-023-0368-y
Bravo JHernández JAres de Parga SRossi R(2024)A subspace‐adaptive weights cubature method with application to the local hyperreduction of parameterized finite element modelsInternational Journal for Numerical Methods in Engineering10.1002/nme.7590Online publication date: 3-Sep-2024
https://doi.org/10.1002/nme.7590
Show More Cited By

Index Terms

Subspace fluid re-simulation
1. Computing methodologies
  1. Computer graphics
    1. Animation
      1. Physical simulation
    2. Shape modeling
2. Mathematics of computing
  1. Continuous mathematics
    1. Topology
      1. Geometric topology

Recommendations

Subspace condensation: full space adaptivity for subspace deformations

Subspace deformable body simulations can be very fast, but can behave unrealistically when behaviors outside the prescribed subspace such as novel external collisions, are encountered. We address this limitation by presenting a fast, flexible new method ...
Multiphase Viscoelastic Non-Newtonian Fluid Simulation
SCA '24: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation

We propose an SPH-based method for simulating viscoelastic non-Newtonian fluids within a multiphase framework. For this, we use mixture models to handle component transport and conformation tensor methods to handle the fluid's viscoelastic stresses. In ...
Multiple-Fluid SPH Simulation Using a Mixture Model

This article presents a versatile and robust SPH simulation approach for multiple-fluid flows. The spatial distribution of different phases or components is modeled using the volume fraction representation, the dynamics of multiple-fluid flows is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 32, Issue 4

July 2013

1215 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2461912

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2013

Published in TOG Volume 32, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Information and Intelligent Systems

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
817
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)11

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hernández JBravo JAres de Parga S(2024)CECM: A continuous empirical cubature method with application to the dimensional hyperreduction of parameterized finite element modelsComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2023.116552418(116552)Online publication date: Jan-2024
https://doi.org/10.1016/j.cma.2023.116552
Wang XXu YLiu SRen BKosinka JTelea AWang JSong CChang JLi CZhang JBan X(2024)Physics-based fluid simulation in computer graphics: Survey, research trends, and challengesComputational Visual Media10.1007/s41095-023-0368-y10:5(803-858)Online publication date: 27-Apr-2024
https://doi.org/10.1007/s41095-023-0368-y
Bravo JHernández JAres de Parga SRossi R(2024)A subspace‐adaptive weights cubature method with application to the local hyperreduction of parameterized finite element modelsInternational Journal for Numerical Methods in Engineering10.1002/nme.7590Online publication date: 3-Sep-2024
https://doi.org/10.1002/nme.7590
Tang JKim BAzevedo VSolenthaler B(2023)Physics‐Informed Neural Corrector for Deformation‐based Fluid ControlComputer Graphics Forum10.1111/cgf.1475142:2(161-173)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14751
Tao MBatty CBen-Chen MFiume ELevin D(2022)VEMPICACM Transactions on Graphics10.1145/3528223.353013841:4(1-22)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530138
Flynn SHart DMorse BHolladay SEgbert P(2021)Generalized fluid carving with fast lattice-guided seam computationACM Transactions on Graphics10.1145/3478513.348054440:6(1-15)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480544
Cui QLanglois TSen PKim T(2021)Spiral-spectral fluid simulationACM Transactions on Graphics10.1145/3478513.348053640:6(1-16)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480536
Bai KWang CDesbrun MLiu X(2021)Predicting high-resolution turbulence details in space and timeACM Transactions on Graphics10.1145/3478513.348049240:6(1-16)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480492
Peng TZhou XLiu JHu XChen CWu ZPeng DQin X(2021)Modeling of fabric motion based on small videosThe Journal of The Textile Institute10.1080/00405000.2021.1874120113:2(324-331)Online publication date: 16-Feb-2021
https://doi.org/10.1080/00405000.2021.1874120
Bai KLi WDesbrun MLiu X(2020)Dynamic Upsampling of Smoke through Dictionary-based LearningACM Transactions on Graphics10.1145/341236040:1(1-19)Online publication date: 18-Sep-2020
https://dl.acm.org/doi/10.1145/3412360
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents