“Scalable laplacian eigenfluids” by Cui, Sen and Kim

  • ©Qiaodong Cui, Pradeep Sen, and Theodore Kim



Entry Number: 87

Session Title:

    Fluids 1: Raiders of the Lost Volume


    Scalable laplacian eigenfluids




    The Laplacian Eigenfunction method for fluid simulation, which we refer to as Eigenfluids, introduced an elegant new way to capture intricate fluid flows with near-zero viscosity. However, the approach does not scale well, as the memory cost grows prohibitively with the number of eigenfunctions. The method also lacks generality, because the dynamics are constrained to a closed box with Dirichlet boundaries, while open, Neumann boundaries are also needed in most practical scenarios. To address these limitations, we present a set of analytic eigenfunctions that supports uniform Neumann and Dirichlet conditions along each domain boundary, and show that by carefully applying the discrete sine and cosine transforms, the storage costs of the eigenfunctions can be made completely negligible. The resulting algorithm is both faster and more memory-efficient than previous approaches, and able to achieve lower viscosities than similar pseudo-spectral methods. We are able to surpass the scalability of the original Laplacian Eigenfunction approach by over two orders of magnitude when simulating rectangular domains. Finally, we show that the formulation allows forward scattering to be directed in a way that is not possible with any other method.


    1. Steven S. An, Theodore Kim, and Doug L. James. 2008. Optimizing Cubature for Efficient Integration of Subspace Deformations. ACM Trans. Graph. 27, 5, Article 165 (Dec. 2008), 10 pages. Google ScholarDigital Library
    2. Alexis Angelidis. 2017. Personal Communication. (2017).Google Scholar
    3. David Baraf and Andrew Witkin. 1998. Large steps in cloth simulation. In Proceedings of SIGGRAPH. 43–54. Google ScholarDigital Library
    4. John P Boyd. 2001. Chebyshev and Fourier spectral methods. Dover Publications.Google Scholar
    5. Robert Bridson. 2015. Fluid simulation for computer graphics. CRC Press. Google ScholarDigital Library
    6. Tyson Brochu, Todd Keeler, and Robert Bridson. 2012. Linear-time Smoke Animation with Vortex Sheet Meshes. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 87–95. Google ScholarDigital Library
    7. K. J. Burns, G. M. Vasil, J. S. Oishi, D. Lecoanet, B. P. Brown, and E. Quataert. 2017. Dedalus project. http://dedalus-project.org. (2017).Google Scholar
    8. CG Canuto, MY Hussaini, A Quarteroni, and TA Zang. 2007. Spectral Methods: Evolution to Complex Geometries and Applications to Fluid Dynamics. Springer. Google ScholarCross Ref
    9. Claudio Canuto, M Yousuf Hussaini, Alfio Quarteroni, and TA Zang. 1988. Spectral methods in fluid dynamics. Springer.Google Scholar
    10. Albert Chern, Felix Knöppel, Ulrich Pinkall, Peter Schröder, and Steffen Weissmann. 2016. Schrödinger’s Smoke. ACM Trans. Graph. 35, 4, Article 77 (July 2016), 13 pages. Google ScholarDigital Library
    11. Seth Davidovits and Nathaniel J Fisch. 2016. Sudden viscous dissipation of compressing turbulence. Physical Review Letters 116, 10 (2016).Google ScholarCross Ref
    12. Tyler De Witt, Christian Lessig, and Eugene Fiume. 2012. Fluid Simulation Using Laplacian Eigenfunctions. ACM Trans. Graph. 31, 1, Article 10 (2012), 11 pages. Google ScholarDigital Library
    13. Ronald Fedkiw, Jos Stam, and Henrik Wann Jensen. 2001. Visual Simulation of Smoke. In Proceedings of SIGGRAPH. 15–22. Google ScholarDigital Library
    14. Florian Ferstl, Rüdiger Westermann, and Christian Dick. 2014. Large-scale liquid simulation on adaptive hexahedral grids. IEEE Transactions on Visualization and Computer Graphics 20, 10 (2014), 1405–1417.Google ScholarCross Ref
    15. Matteo Frigo and Steven G. Johnson. 2005. The Design and Implementation of FFTW3. Proc. IEEE 93, 2 (2005), 216–231. Special issue on “Program Generation, Optimization, and Platform Adaptation”.Google ScholarCross Ref
    16. Uriel Frisch. 1995. Turbulence: The Legacy of AN Kolmogorov. Cambridge University Press.Google ScholarCross Ref
    17. Chuyuan Fu, Qi Guo, Theodore Gast, Chenfanfu Jiang, and Joseph Teran. 2017. A Polynomial Particle-in-cell Method. ACM Trans. Graph. 36, 6, Article 222 (Nov. 2017), 12 pages. Google ScholarDigital Library
    18. Gene H Golub and Charles F Van Loan. 2012. Matrix computations. Vol. 3. JHU Press.Google Scholar
    19. David Gottlieb and Steven A Orszag. 1977. Numerical analysis of spectral methods: theory and applications. SIAM.Google Scholar
    20. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org. (2010).Google Scholar
    21. Mohit Gupta and Srinivasa G. Narasimhan. 2007. Legendre Fluids: A Unified Framework for Analytic Reduced Space Modeling and Rendering of Participating Media. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 17–25. Google ScholarDigital Library
    22. Milos Hasan, Edgar Velazquez-Armendariz, Fabio Pellacini, and Kavita Bala. 2008. Tensor Clustering for Rendering Many-Light Animations. Computer Graphics Forum 27, 4 (2008), 1105–1114. Google ScholarDigital Library
    23. Ronald D. Henderson. 2012. Scalable Fluid Simulation in Linear Time on Shared Memory Multiprocessors. In Proceedings of the Digital Production Symposium (DigiPro ’12). 43–52. Google ScholarDigital Library
    24. Nambin Heo and Hyeong-Seok Ko. 2010. Detail-preserving fully-Eulerian Interface Tracking Framework. ACM Trans. Graph. 29, 6, Article 176 (Dec. 2010), 8 pages. Google ScholarDigital Library
    25. Chenfanfu Jiang, Craig Schroeder, Andrew Selle, Joseph Teran, and Alexey Stomakhin. 2015. The Affine Particle-in-cell Method. ACM Trans. Graph. 34, 4, Article 51 (July 2015), 10 pages. Google ScholarDigital Library
    26. Aaron Demby Jones, Pradeep Sen, and Theodore Kim. 2016. Compressing Fluid Subspaces. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 77–84. Google ScholarDigital Library
    27. Theodore Kim. 2013. Zephyr. http://www.tkim.graphics/RESIM/source.html. (2013).Google Scholar
    28. Theodore Kim and John Delaney. 2013. Subspace Fluid Re-simulation. ACM Trans. Graph. 32, 4, Article 62 (2013), 9 pages. Google ScholarDigital Library
    29. Theodore Kim, Nils Thürey, Doug James, and Markus Gross. 2008. Wavelet Turbulence for Fluid Simulation. ACM Trans. Graph. 27, 3, Article 50 (Aug. 2008), 6 pages. Google ScholarDigital Library
    30. Cornelius Lanczos. 1938. Trigonometric interpolation of empirical and analytical functions. J. Math Phys. 17, 1–4 (1938), 123–199.Google ScholarCross Ref
    31. Beibei Liu, Gemma Mason, Julian Hodgson, Yiying Tong, and Mathieu Desbrun. 2015. Model-reduced Variational Fluid Simulation. ACM Trans. Graph. 34, 6, Article 244 (2015), 12 pages. Google ScholarDigital Library
    32. Benjamin Long and Erik Reinhard. 2009. Real-time Fluid Simulation Using Discrete Sine/Cosine Transforms. In Symposium on Interactive 3D Graphics and Games. 99–106. Google ScholarDigital Library
    33. Frank Losasso, Frédéric Gibou, and Ron Fedkiw. 2004. Simulating Water and Smoke with an Octree Data Structure. ACM Trans. Graph. 23, 3 (Aug. 2004), 457–462. Google ScholarDigital Library
    34. A. McAdams, E. Sifakis, and J. Teran. 2010. A Parallel Multigrid Poisson Solver for Fluids Simulation on Large Grids. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 65–74. Google ScholarDigital Library
    35. Patrick Mullen, Keenan Crane, Dmitry Pavlov, Yiying Tong, and Mathieu Desbrun. 2009. Energy-preserving Integrators for Fluid Animation. ACM Trans. Graph. 28, 3, Article 38 (2009), 8 pages. Google ScholarDigital Library
    36. Rahul Narain, Jason Sewall, Mark Carlson, and Ming C. Lin. 2008. Fast Animation of Turbulence Using Energy Transport and Procedural Synthesis. ACM Trans. Graph. 27, 5, Article 166 (Dec. 2008), 8 pages. Google ScholarDigital Library
    37. Steven A Orszag. 1969. Numerical methods for the simulation of turbulence. The Physics of Fluids 12, 12 (1969), II–250.Google ScholarCross Ref
    38. Steven A Orszag. 1971. Accurate solution of the Orr-Sommerfeld stability equation. Journal of Fluid Mechanics 50, 4 (1971), 689–703.Google ScholarCross Ref
    39. Tobias Pfaff, Nils Thuerey, and Markus Gross. 2012. Lagrangian Vortex Sheets for Animating Fluids. ACM Trans. Graph. 31, 4, Article 112 (July 2012), 8 pages. Google ScholarDigital Library
    40. Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM. Google ScholarDigital Library
    41. H. Schechter and R. Bridson. 2008. Evolving Sub-grid Turbulence for Smoke Animation. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 1–7. Google ScholarDigital Library
    42. Andrew Selle, Ronald Fedkiw, Byungmoon Kim, Yingjie Liu, and Jarek Rossignac. 2008. An unconditionally stable MacCormack method. Journal of Scientific Computing 35, 2 (2008), 350–371. Google ScholarDigital Library
    43. Andrew Selle, Nick Rasmussen, and Ronald Fedkiw. 2005. A Vortex Particle Method for Smoke, Water and Explosions. ACM Trans. Graph. 24, 3 (July 2005), 910–914. Google ScholarDigital Library
    44. Rajsekhar Setaluri, Mridul Aanjaneya, Sean Bauer, and Eftychios Sifakis. 2014. SPGrid: A Sparse Paged Grid Structure Applied to Adaptive Smoke Simulation. ACM Trans. Graph. 33, 6, Article 205 (Nov. 2014), 12 pages. Google ScholarDigital Library
    45. Jos Stam. 1999. Stable Fluids. In Proceedings of SIGGRAPH. 121–128. Google ScholarDigital Library
    46. Jos Stam. 2002. A Simple Fluid Solver Based on the FFT. J. Graph. Tools 6, 2 (Sept. 2002), 43–52. Google ScholarDigital Library
    47. Matt Stanton, Yu Sheng, Martin Wicke, Federico Perazzi, Amos Yuen, Srinivasa Narasimhan, and Adrien Treuille. 2013. Non-polynomial Galerkin Projection on Deforming Meshes. ACM Trans. Graph. 32, 4, Article 86 (July 2013), 14 pages. Google ScholarDigital Library
    48. Lloyd N Trefethen. 2000. Spectral methods in MATLAB. SIAM. Google ScholarDigital Library
    49. Adrien Treuille, Andrew Lewis, and Zoran Popović. 2006. Model Reduction for Real-time Fluids. ACM Trans. Graph. 25, 3 (July 2006), 826–834. Google ScholarDigital Library
    50. Geofrey M. Vasil, Keaton J. Burns, Daniel Lecoanet, Sheehan Olver, Benjamin P. Brown, and Jeffrey S. Oishi. 2016. Tensor calculus in polar coordinates using Jacobi polynomials. J. Comput. Phys. 325 (2016), 53 — 73. Google ScholarDigital Library
    51. Stefen Weissmann and Ulrich Pinkall. 2010. Filament-based Smoke with Vortex Shedding and Variational Reconnection. ACM Trans. Graph. 29, 4, Article 115 (July 2010), 12 pages. Google ScholarDigital Library
    52. Martin Wicke, Matt Stanton, and Adrien Treuille. 2009. Modular Bases for Fluid Dynamics. ACM Trans. Graph. 28, 3, Article 39 (July 2009), 8 pages. Google ScholarDigital Library
    53. Xinxin Zhang, Robert Bridson, and Chen Greif. 2015. Restoring the Missing Vorticity in Advection-projection Fluid Solvers. ACM Trans. Graph. 34, 4, Article 52 (July 2015), 8 pages. Google ScholarDigital Library
    54. Yongning Zhu and Robert Bridson. 2005. Animating Sand As a Fluid. ACM Trans. Graph. 24, 3 (July 2005), 965–972. Google ScholarDigital Library

ACM Digital Library Publication: