“Scalable laplacian eigenfluids” by Cui, Sen and Kim
Conference:
Type(s):
Entry Number: 87
Title:
- Scalable laplacian eigenfluids
Session/Category Title: Fluids 1: Raiders of the Lost Volume
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
