“Subdivision schemes for fluid flow” by Weimer and Warren

The motion of fluids has been a topic of study for hundreds of years. In its most general setting, fluid flow is governed by a system of non-linear partial differential equations known as the Navier-Stokes equations. However, in several important settings, these equations degenerate into simpler systems of linear partial differential equations. This paper will show that flows corresponding to these linear equations can be modeled using subdivision schemes for vector fields. Given an initial, coarse vector field, these schemes generate an increasingly dense sequence of vector fields. The limit of this sequence is a continuous vector field defining a flow that follows the initial vector field. The beauty of this approach is that realistic flows can now be modeled and manipulated in real time using their associated subdivision schemes.

1. F. Brezzi, M. Fortin: Mixed and Hybrid Finite Element Methods, Springer, 1991.
2. W.L. Briggs: A Multigrid Tutorial. Society for Industrial and Applied Mathematics, 1987.
3. E. Catmull, J. Clark: Recursive generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design 10(6), pp. 350-355,1978.
4. J. Chen, N. Lobo: Toward interactive-rate simulation of fluid with moving obstacles using Navier-Stokes equations. Graphical Models and Image Processing, 57(2),pp. 107-116,1995.
5. N. Chiba et al.: Visual simulation of water currents using a particle-based behavioral model. Journal of Visualization and Computer Animation 6, pp. 155- 171, 1995.
6. B. Chopard, M. Droz: Cellular Automata Modeling of Physical Systems. Cambridge University Press, 1998.
7. T. DeRose, M. Kass, T. Truong: Subdivision sulfaces in character animation. Proceedings of SIGGRAPH 98. In Computer Graphics Proceedings, Annual Conference Series, pp. 85-94, 1998.
8. D. Doo, M. Sabin: Behavior of recursive division sulfaces near extraordinary points. Computer Aided Design 10(6), pp. 356-360,1978.
9. N. Dyn: Interpolation of scattered data by radial functions. In C. K. Chui et al. (eds.): Topics in Multivariate App~vximation, Academic Press, pp. 47-61, 1987.
10. N. Dyn: Subdivision schemes in computer aided geometric design. In W. Light (ed.): Advances in Numerical Analysis H, Oxford University Press, , pp. 36- 104, 1992.
11. N. Foster, D. Metaxas: Realistic animation of liquids. Graphical Models and Image Processing, 58 (5), pp. 471-483,1996.
12. N. Foster, D. Metaxas: Modeling the motion of a hot, turbulent gas. Proceedings of SIGGRAPH 97. In Computer Graphics Proceedings, Annual Conference Series, pp. 181-188,1997.
13. J. Hosckek, D. Lasser: Fundamentals of Computer Aided Geometric Design. A K Peters, 1993.
14. H. Hoppe, T. DeRose, T. Duchamp, M. Halstead, H. Jin, J. McDonald, J. Schweitzer, W. Stuetzle: Piecewise smooth surface reconstruction. Proceedings of SIGGRAPH 94. In Computer Graphics Proceedings, Annual Conference Series, pp. 295-302,1994.
15. Z. Kadi, A. Rockwood: Conformal maps defined about polynomial curves. Computer Aided Geometric Design 15, pp. 323-337,1998.
16. M. Kass, G. Miller: Rapid, stable fluid dynamics for computer graphics. Proceedings of SIGGRAPH 89. In Computer Graphics Proceedings, Annual Conterence Series, pp. 49-57,1989.
17. J. Liggett: Fluid Mechanics. McGraw Hill, 1994.
18. L. Kobbelt: A variational app~vach to subdivision. Computer Aided Geometric Design 13, pp. 743-761,1996.
19. L. Kobbelt: Variational design with parametric meshes of arbitrary topology. To appear, http ://www9.informatik.unierlangen.de/Persons/Kobbelt/papers/design.ps.gz, 1998.
20. L. Kobbelt, S. Campagna, J. Vorsatz, H.-P. Seidel: Interactive multi-resolution modeling on arbitrary meshes. Proceedings of SIGGRAPH 98. In Computer Graphics Proceedings, Annual Conference Series, pp. 105-114,1998.
21. J. Lane, R. Riesenfeld. A theoretical development for the computer generation and display of piecewise polynomial sulfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence 2, 1, pp. 35-46, 1980.
22. G. Miller, A. Pearce: Globular dynamics: A connected particle system for animating viscous fluids. Computers and Graphics 13 (3), pp. 305-309,1989.
23. D. H. Rothman, S. Zaleski: Lattice-Gas Cellular Automata. Cambridge University Press, 1997.
24. T.W. Sederberg, J. Zheng, D. Sewell, M. Sabin: Non-unifo1~ recursive subdivision sulfaces. Proceedings of SIGGRAPH 98. In Computer Graphics Proceedings, Annual Conference Series, pp. 387-394,1998.
25. J. Stare, E. Fiume: Turbulent Wind Fields for Gaseous Phenomena. Proceedings of SIGGRAPH 93. In Computer Graphics Proceedings, Annual Conference Series, pp. 369-376,1993.
26. R. S. Varga: Matrix Iterative Analysis. Prentice-Hall, 1962.
27. J. Warren, H. Weimer: A cookbook for variational subdivision, in D. Zorin (ed.): Subdivision for Modeling and Animation, SIGGRAPH 99 course-notes number 37, 1999.
28. H. Weimer, J. Warren: Subdivision schemes for thin plate splines. Computer Graphics Forum 17, 3, pp. 303-313 & 392, 1998.
29. J. Wejchert, D. Haumann: Animation Aelvdynamics. Proceedings of SIG- GRAPH 91. Computer Graphics 25 (3), pp. 19-22,1991.
30. D. M. Young: Iterative Solution of Large Linear Systems. Academic Press, 1971.
31. D. Zorin, P. Schr~der, W. Sweldens: Interactive multiresolution mesh editing. Proceedings of SIGGRAPH 97. In Computer Graphics Proceedings, Annual Conference Series, pp. 259-168,1997.