This paper presents an implementation of a stable height-field fluid solver on non-uniform quadtree grids. Smoothing kernel interpolation allow one to use semi-Lagrangian advection on the nonuniform grid. A modification to the advection make it mass conserving. The non-uniform grid allow the model to run on a very tight cell budget with high frame rates even for arbitrary sized environments. Gravity acceleration is implemented as a modified explicit Euler step with upwind differencing. The differencing is based on a definition of a node neighbour which doesnt require the neighbor to be a quadtree leaf. This solves the problems of hanging nodes inherent with quadtrees. This model is suitable for water propagating over height field terrains in interactive environments like video games.
Fluid dynamics; semi-Lagrangian advection; upwind differencing; adaptive grid; quadtree
ASPLUND; P. 2007. Dynamic Spreading of Wildfire. Master’s thesis; Kungliga Tekniska Hgskolan.
AXELSSON; T. 2007. Realtidssimulering av vtskor i datorspel mha partikelsystem. Master’s thesis; Hgskolan Skvde.
BEAUDOIN; P.; PAQUET; S.; AND POULIN; P. 2001. Realistic and controllable fire simulation. In Graphics Interface 2001; 159– 166.
BRIDSON; R.; AND MLLER-FISCHER; M.; 2006. Fluid simulation course notes; siggraph.
BRIDSON; R.; AND MLLER-FISCHER; M. 2007. Combating dissipation. SIGGRAPH.
BRIDSON; R.; AND MLLER-FISCHER; M. 2007. Fluid simulation. SIGGRAPH.
BRIDSON; R.; AND MLLER-FISCHER; M. 2007. More accurate pressure solves. SIGGRAPH.
BRIDSON; R.; FEDKIW; R.; AND MLLER-FISCHER; M. Fluid simulation course notes; siggraph 2007.
CORDS; H. 2007. Mode-splitting for highly detailed; interactive liquid simulation. In GRAPHITE ’07: Proceedings of the 5th international conference on Computer graphics and interactive techniques in Australia and Southeast Asia; ACM; New York; NY; USA; 265–272.
DUCHAINEAU; M. A.; WOLINSKY; M.; SIGETI; D. E.; MILLER; M. C.; ALDRICH; C.; AND MINEEV-WEINSTEIN; M. B. 1997. ROAMing terrain: real-time optimally adapting meshes. In IEEE Visualization; 81–88.
DUNN; A.; AND MILNE; G. 2004. Modelling wildfire dynamics via interacting automata. In Cellular Automata; Springer Berlin; vol. 3305; 395–404.
ELCOTT; S. 2005. Discrete; Circulation-Preserving; and Stable Simplicial Fluids. Master’s thesis; California Institute of Technology.
FITZPATRICK; R. Upwind differencing. [Online; accessed 9-June- 2008].
FOSTER; N.; AND METAXAS; D. 1996. Realistic animation of liquids. Graphical models and image processing: GMIP 58; 5; 471–483.
GREEN; S.; 2008. Particle-based fluid simulation; nvidia.
HEGEMAN; K.; CARR; N. A.; AND MILLER; G. S. 2006. Particlebased fluid simulation on the gpu. In Computational Science –
ICCS 2006; Springer; V. N. Alexandrov; G. D. van Albada; P. M. Sloot; and J. Dongarra; Eds.; vol. 3994 of LNCS; 228–235.
HINSINGER; D.; NEYRET; F.; AND CANI; M.-P. 2002. Interactive animation of ocean waves. In ACM-SIGGRAPH/EG Symposium on Computer Animation (SCA).
HOFFMAN; J.; AND JOHNSON; C. 2006. Computational Turbulent Incompressible Flow. Springer.
HUGOSON; P.; AND NILSSON; A. 2007. Hybrid Fluid Simulation. Master’s thesis; Hgskolan Kalmar.
IRVING; G.; GUENDELMAN; E.; LOSASSO; F.; AND FEDKIW; R. 2006. Efficient simulation of large bodies of water by coupling two and three dimensional techniques. In SIGGRAPH ’06: ACM
SIGGRAPH 2006 Papers; ACM; New York; NY; USA; 805–811. KARAFYLLIDIS; I.; AND THANAILAKIS; A. 1997. A model for predicting forest fire spreading using cellular automata. Ecological Modelling 99; 1; 87–97.
KASS; M.; AND MILLER; G. 1990. Rapid; stable fluid dynamics for computer graphics. In SIGGRAPH ’90: Proceedings of the 17th annual conference on Computer graphics and interactive techniques; ACM; New York; NY; USA; 49–57.
KPPEN; T.; AND NIVFORS; A. 2005. Realtidsrendering av stora vattenytor. Master’s thesis; Hgskolan Kalmar.
LAYTON; A. T.; AND VAN DE PANNE; M. 2002. A numerically efficient and stable algorithm for animating water waves. In The Visual Computer; Springer-Verlag; 41–53.
LEE; H.; KIM; L.; MEYER; M.; AND DESBRUN; M. 2001. Meshes on fire. In Proceedings of the Eurographic workshop on Computer animation and simulation; Springer-Verlag New York; Inc.; New York; NY; USA; 75–84.
LIU; P.-S.; AND CHOU; Y.-H. 1997. A grid automation of wildfire growth simulation.
LOMAX; H.; THOMAS H. PULLIAM; AND ZINGG; D. W. 2001. Fundamentals of Computational Fluid Dynamics. Springer- Verlag.
LUEBKE; D.; REDDY; M.; COHEN; J. D.; VARSHNEY; A.; WATSON; B.; AND HUEBNER; R. 2003. Level of Detail for 3D Graphics. Morgan Kaufmann.
MAES; M. M.; FUJIMOTO; T.; AND CHIBA; N. 2006. Efficient animation of water flow on irregular terrains. In GRAPHITE ’06: Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast Asia; ACM; New York; NY; USA; 107–115.
MITTRING; M. 2007. Finding next gen: Cryengine 2. In SIGGRAPH ’07: ACM SIGGRAPH 2007 courses; ACM; New York; NY; USA; 97–121.
MLLER-FISCHER; M. 2007. Real time fluids in games.
SIGGRAPH. M¨ULLER; M.; SCHIRM; S.; AND DUTHALER; S. 2007. Screen space meshes. In SCA ’07: Proceedings of the 2007 ACM SIGGRAPH/ Eurographics symposium on Computer animation; Eurographics Association; Aire-la-Ville; Switzerland; Switzerland; 9–15.
NOE; K. O.; 2004. Implementing rapid; stable fluid dynamics on the gpu.
O’BRIEN; J. F.; AND HODGINS; J. K. 1995. Dynamic simulation of splashing fluids. In Computer Animation ’95; 198–205.
ROGERS; S. E.; AND KWAK; D. 1991. An upwind differencing scheme for the incompressible navier-stokes equations. Appl. Numer. Math. 8; 1; 43–64.
STAM; J. 1999. Stable fluids. In Siggraph 1999; Computer Graphics Proceedings; Addison Wesley Longman; Los Angeles; A. Rockwood; 121–128.
STAM; J. 2001. A simple fluid solver based on the fft. J. Graph. Tools 6; 2; 43–52.
STAM; J.; 2003. Real-time fluid dynamics for games.
TESSENDORF; J. 1999. Simulating ocean water. In SIGGRAPH Course Notes; SIGGRAPH.
THUREY; N.; M¨ULLER-FISCHER; M.; SCHIRM; S.; AND GROSS; M. 2007. Real-time breakingwaves for shallow water simulations. In PG ’07: Proceedings of the 15th Pacific Conference on Computer Graphics and Applications; IEEE Computer Society; Washington; DC; USA; 39–46.
WEISSTEIN; E. W. Distribution function. accessed 12-March- 2008.
WEISSTEIN; E. W. Probability function. accessed 12-March-2008.
WIKLUND; O. 2007. A Computational Study of a Finite Element Method for Two Phase Flow. Master’s thesis; Kungliga Tekniska Hgskolan.
WONG; A. C. 2003. The Moving Contact Line in a Shallow Water Simulation. Master’s thesis; University of British Columbia.
W.W.; H.; R.H.; G.; M.G.; T.; W.H.; R.; AND D.G.; D. 2000. Simulating fire patterns in heterogeneous landscapes. Ecological Modelling 135; 2-3; 243–263.
