UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Interactive flow field modeling for the design and control of fluid motion in computer animation Gates, William Franklin 1994

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


831-ubc_1994-0139.pdf [ 2.24MB ]
JSON: 831-1.0051299.json
JSON-LD: 831-1.0051299-ld.json
RDF/XML (Pretty): 831-1.0051299-rdf.xml
RDF/JSON: 831-1.0051299-rdf.json
Turtle: 831-1.0051299-turtle.txt
N-Triples: 831-1.0051299-rdf-ntriples.txt
Original Record: 831-1.0051299-source.json
Full Text

Full Text

INTERACTIVE F L O W F I E L D M O D E L I N G FOR THE D E S I G N AND C O N T R O L OF F L U I D M O T I O N IN C O M P U T E R A N I M A T I O N by W I L L I A M F R A N K L I N G A T E S B.Sc , The University of California at Davis, 1991 A T H E S I S S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F S C I E N C E IN T H E F A C U L T Y O F G R A D U A T E S T U D I E S D E P A R T M E N T O F C O M P U T E R S C I E N C E We accept this thesis as conforming to the_refluired standard T H E U N I V E R S I T Y OF B R I T I S H C O L U M B I A January, 1994 © William Franklin Gates, 1994 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of CoMPotSEt The University of British Columbia Vancouver, Canada Date DE-6 (2/88) ABSTRACT Ubiquitous and captivating, fluid—gaseous and liquid—motion is often desired in computer animation. For example, rives, lakes, and clouds enhance flights simulations. Realizing realistic fluid behaviour, however, can be difficult and laborious using traditional computer animation methods. Ad hoc kinematic models of fluid motion have been presented to facilitate the ani-mation of fluids, but it is not clear how to extend or integrate these models to describe more general fluid motion. Simple dynamic models have been presented, but it is difficult to con-trol the dynamic simulation to achieve the desired effect. To address this problem, a simple, hydrodynamically-based framework for realistically integrating models of fluid flow for com-puter animation purposes is presented. This framework is based on the continuity equation for incompressible flow, and allows flow fields to be linearly combined, regardless of whether they are interactively modeled or computed by dynamic simulation. Novel interactive flow field mod-eling methods are introduced to allow the animator to manipulate spline curves that correspond to streamlines in the flow field. The spline-based flow fields can be computed at interactive speed on standard graphics workstations. Many dynamic simulations produce flow fields that satisfy the continuity equation, and these can be linearly combined with the modeled flow field to define a mean flow field which is sampled at the nodes of a lattice. Turbulence is modeled by advecting stochastic distributions of models of vortex flow with the mean flow, allowing infinite resolution for small-scale complexity. Geometric models are advected using the final resulting flow field. A simple animation system incorporating the interactive flow modeling methods was implemented and shows this approach to be a promising and easily extendable method of realistically animating fluids. n TABLE OF CONTENTS Abstract ii Table of Contents iii List of Figures vi Acknowledgements viii Dedication ix Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Denning the Problem 2 1.2.1 Modeling Motion 3 1.2.2 Criteria for an Ideal Method 4 1.2.3 A Framework for Animating Fluids 5 1.3 Thesis Overview 7 Chapter 2 Previous Work 8 2.1 Water Waves 9 2.2 Ship Wakes 14 2.3 Waterfalls 14 2.4 Highly Viscous Liquids 14 2.5 State of the Art 15 in Chapter 3 A Few Fundamentals of Fluid Flow 17 3.1 Introduction 17 3.2 Eulerian and Lagrangian Frames 18 3.3 Equations of Motion 19 3.4 Kinematic Boundary Conditions 20 3.5 Bernoulli Equation 21 3.6 Surface Tension 22 3.7 Equation of Continuity 23 Chapter 4 Interactive Flow Field Modeling 25 4.1 Overview 25 4.2 Principle of Superposition 26 4.3 Basic Flow Fields 27 4.3.1 Uniform 27 4.3.2 Point Source and Sink 27 4.3.3 Vortex 29 4.4 Spline-Based Flow Field Modeling 29 4.4.1 Overview 31 4.4.2 A Directed Flow Primitive 32 4.4.3 A Spline-Based Flow Primitive 34 4.5 Turbulence 39 4.6 A Continuum of Control 40 IV Chapter 5 Implementation and Results 43 5.1 Implementation 43 5.1.1 Interaction 44 5.1.2 Flow Visualization 44 5.1.3 Rendering 44 5.2 Using FLOW 45 5.3 Results 45 Chapter 6 Conclusions and Future Work 51 6.1 Conclusions 51 6.2 Future Work 52 Glossary 53 Bibliography 54 v L I S T OF FIGURES 1.1 Framework for an ideal animation method for fluids 6 4.1 Flow field of point source 28 4.2 Flow field of point sink 29 4.3 Flow field of line vortex 30 4.4 Flow field of directed flow primitive 33 4.5 A plot of the vz component of the directed flow primitive for a fixed r 34 4.6 A spline flow primitive 37 4.7 Another view of spline flow primitive 38 4.8 Flow field of two spline flow primitives 38 4.9 Turbulent flow 39 4.10 Turbulent flow 40 VI 5.1 Flow around object 46 5.2 Frame one from Liquid Skull 47 5.3 Frame two from Liquid Skull 47 5.4 Frame three from Liquid Skull 47 5.5 Frame four from Liquid Skull 47 5.6 Frame five from Liquid Skull 48 5.7 Frame six from Liquid Skull 48 5.8 Frame seven from Liquid Skull 48 5.9 Frame eight from Liquid Skull 48 5.10 Frame nine from Liquid Skull 49 5.11 Frame ten from Liquid Skull 49 5.12 Frame eleven from Liquid Skull 49 5.13 Frame twelve from Liquid Skull 49 5.14 Frame thirteen from Liquid Skull 50 5.15 Frame fourteen from Liquid Skull 50 5.16 Frame fifteen from Liquid Skull 50 5.17 Frame sixteen from Liquid Skull 50 vn ACKNOWLEDGEMENTS I would like to thank my supervisor, Dr. Alain Fournier, for the freedom to explore, the support to persevere, and the guidance to succeed. The second reader, Dr. David R. Forsey, has my appreciation not just for his reviewing of this thesis, but for being a source of encouragement from the beginning. The student reader, Mr. Christopher G. Healey, deserves acknowledgment and several mochas for his many helpful comments. A number of friendly colleagues also went out of their way to provide valuable assistance, including Dr. Pierre Poulin who offered a fountain of helpful references, Mr. Christopher A. Romanzin who parted the Red Sea of writing a thesis using the LMjjX document preparation system, and Mr. Kevin W. Arthur, Mr. Andrew D. Naiberg, Mr. Larry Palazzi, and Mr. Torre D. Zuk who helped drown thesis ennui in Canterbury. Finally, I would like to acknowledge the financial support provided by Computer Science De-partment of the University of British Columbia through teaching assistantships and by the National Science and Engineering Research Council through research assistantships that made this research possible. vin To my father, a place called Cascadia, and a love of water. IX C H A P T E R O N E I N T R O D U C T I O N Water, water, every where, And all the boards did shrink; Water, water, every where Nor any drop to drink. —Samuel Taylor Coleridge Steam wisping off a rain-soaked tree warming in the sun, bathwater whirling down a drain, a waterfall cascading down a cliff—fluid motion is complex, mysterious, and beautiful. For ages, artists have been trying to capture this beauty, and scientists have been trying to model this motion. Recently, computer animators—both artists and scientists—have attempted to realize the motion of fluids. But while computer animation methods have proven to be a powerful tool for visually representing rigid, human-constructed objects and are routinely used in industry, animating fluids has proven more difficult (Wyvill et al., 1986). 1.1 M O T I V A T I O N Given the sheer ubiquity of fluids (gases and liquids), the computer animation of flowing fluids has almost as many applications as computer animation itself. When the captivating motion of fluids is also considered, the computer animation of fluids needs little justification. Applications include: • design of fountains, artificial waterfalls and streams, • adding models of rivers, lakes, and clouds to visualizations of geographic databases, • enhanced realism in simulation systems such as flight simulators, • artistic tools, 1 Chapter 1: Introduction 2 • creating television and motion picture visual effects, and • visualization of fluid phenomena in general. The wide range of applications motivate the development of animation tools to assist the anima-tor in creating animations of fluid flow. These applications—besides justifying the problem— help define the problem, i.e., motivate criteria for such animation tools. 1.2 D E F I N I N G T H E P R O B L E M Creating a computer animation can be loosely divided into two steps: modeling, building ge-ometric models and designing their movement and rendering, the synthesizing of images from these geometric models using an illumination model, a model of how light interacts with the geometry. Many challenges remain in both the modeling and rendering of fluids. This thesis addresses the motion modeling aspect of animating fluids. In general, geometric modeling and motion modeling cannot be decoupled as the geometry may constrain the possible motions (if realistic motion is desired). However, fluids are continuously deformable, and thus lack any geometric constraints on their motion. Modeling fluid motion is an extremely broad problem. The range of flowing fluid phenomena can be difficult to encompass: flowing fluids include dripping honey, clouds blowing in the wind, tsunamis, rain, fire, flowing beer, and galaxy formation. Yet, a common set of physical principles underlie these phenomena and motivate a unified approach to modeling their motion. To make the problem addressed by this thesis concrete and tractable without narrowing its scope, criteria for an ideal solution are defined, a framework for this solution is presented, and the aspect of this framework addressed by this thesis is discussed. Chapter 1: Introduction 3 1.2.1 M O D E L I N G M O T I O N The classic method of motion modeling in computer animation is keyframing where the positions of geometric models are positioned at particular frames (keyframes), say frame one and frame ten, and the positions at frames two through nine are computed by interpolation. Realistically animating complex fluid motion such as a breaking wave this way would be extremely difficult. Another traditional method of modeling motion is to design motion paths, often using cubic B-splines, that specify the path an object follows. Motion paths are often adequate for models of rigid bodies, but become more difficult for deformable models, and impractical for fluids. An alternative to keyframing and using motion paths is to use functions that describe the shape of the object over time. For example, traveling sine waves can be used to approximate water waves. Computer graphics researchers have presented ad hoc models for particular fluid motions, but these approaches are limited when more general motion is desired as ad hoc models cannot in general be combined in a straightforward fashion. A more recent approach to modeling motion is dynamic simulation: forces are modeled, and from Newton's second law of motion, f = ma, the acceleration is computed and integrated to describe the motion of the geometric model. For example, classical mechanics has been used to animate rigid bodies (Hahn, 1988). This approach has been quite successful, since it gives the animator a high-level control over the motion: the forces. The basic challenges of so-called "physically-based modeling" are developing a dynamic model, finding an efficient method of solving it, and developing some method of controlling the motion. Motion control is essential since dynamic simulation usually defines an initial-value problem that is time-evolved, and realizing a desired motion requires guessing the proper initial conditions and specification of external forces. The problem with a physically-based model for flowing fluid is that while very good models of fluid motion exist, e.g., the Navier-Stokes equations, the numerical solution is generally computationally intensive and often difficult to set up, especially for free-surface flow problems. Chapter 1: Introduction 4 Computer graphics researchers have opted for simplified dynamic models. Perhaps owing to the complexity of fluid motion, relatively little work has been done: a general method of animating fluids remains a challenging problem. 1.2.2 C R I T E R I A FOR A N IDEAL M E T H O D To alleviate this difficulty, criteria are defined for an ideal method that allows different motion models to be integrated. The applications of the computer animation of fluids motivate the following criteria for such a method: • realism, the motion should be realistic at the relevant scale, • efficiency, the method should be fast enough to be useful, • controllability, the motion computed by dynamic simulation should be easily controlled by the animator, and • generality, the method should not be ad hoc. The realism criterion, dictated by applications such as flight simulation, means the animation method should allow the creation of fluid models that appear to behave like real fluids at the relevant scale. In other words, there is no need for the motion to be in agreement with real fluids beyond what can be perceived in the computer animation. Formally defining a metric for realism, however, is a complex psychophysical problem that has not been fully addressed. The efficiency criterion means the method should be fast enough to allow interactive animation on standard graphics workstations. As rendering algorithms such as raytracing and radiosity cannot run at interactive rates on most graphics workstations, interaction will have to occur in a "preview mode" using a simple rendering method. Of course, the actual speed is highly dependent on the type of machine, network load, swap space, and other variables. A possible heuristic is that on the order of hundreds of samples used to represent the fluid (vertices, control points, particles) should be animated at interactive rates (certainly no slower than one frame Chapter 1: Introduction 5 per second). Implicit in this criterion is that any numerical solution method also be stable over relatively long time steps (on the order of 1/30 second, a typical time between animation frames): a fast method that requires very short time steps to be stable is not efficient. The controllability criterion means the animation method should allow the animator to easily create fluid flow where it is desired and control it at will. This criterion addresses an often noted problem with physical simulation for computer animation: the equations describing the physical phenomena are usually time-evolved from initial conditions and thus getting the desired behaviour can require numerous simulation trials. The generality criterion means the animation method should be flexible, open-ended, and allow different motion models to be realistically integrated. Consider creating a computer animation of a fountain. A liquid jet might emerge upward, continuous at first, then breaking into discrete parts, then into drops and mist, falling back on itself, and then into a pool where circular waves emanate from each drop, interfere with another, refract with changes in depth, and reflect off boundaries. While ad hoc models could cover separate parts of the modeling, e.g., circular wave motion or drops moving under a gravitational force, ad hoc models are often difficult to integrate, and while two models may be physically valid, there may be no guarantee that their combination is also physically valid. Ideally, we would like models that describe as many different phenomena (waves, jets, spray) as possible to minimize the number of tools the animator must become familiar with and use to create any particular animation. 1.2.3 A F R A M E W O R K FOR A N I M A T I N G F L U I D S The criteria just defined pose a large and challenging problem. Rather than introduce another ad hoc model for a specific fluid phenomena, a framework for solving the general problem is proposed and a subset of this framework is addressed by this thesis. The framework consists of three major components: dynamic simulation, interactive flow field modeling, and turbulence modeling (Figure 1.1). A flow field computed by dynamic simulation Chapter 1: Introduction Geometric modeling J \ f -> Discretization of fluid domain \ > Numerical solution of a dynamic model \ Flow field from dynamic simulation \ Superposition of "flow primitives" 1 Flow field from interactive modeling / Dynamic Simulation Interactive Flow Field Modeling Interactive blending " Mean flow field v r Superposition of turbulence Final flow field Advect geometric models Figure 1.1: Framework for an ideal animation method for fluids. and a flow field interactively model are blended to define a mean flow field. A turbulent flow field is superimposed on the mean flow field. This thesis presents new methods for interactive flow field modeling using "flow primitives" based on cubic B-splines rather than point primitives and presents a method for using these flow fields to control the flow fields computed by dynamic simulation. A novel turbulent flow modeling method is also introduced. Chapter 1: Introduction 7 1.3 T H E S I S O V E R V I E W Chapter two reviews previous work in modeling flowing fluid phenomena. Chapter three briefly discusses basic principles of fluid mechanics to provide a background for subsequent chapters. In chapter four, interactive flow field modeling methods are presented. They are based on the law of conservation of mass as expressed by the continuity equation for incompressible flow. Solutions of this equation are known as "flow primitives" and can be linearly combined. Point primitives (e.g., source, sink, vortex) are reviewed, and novel flow primitives based on cubic B-splines are introduced. Also within this framework, a new method of modeling turbulent flow is introduced as well as a method of controlling the dynamic simulation of fluid flow. In chapter five, a simple animation system incorporating these integrated models is described, and resulting animations are presented. And finally, in chapter six, the advantages and disadvantages of this method are discussed and possible future work is suggested. CHAPTER T W O PREVIOUS W O R K GUARD: 'Alio. 'Oo is it? ARTHUR: It is King Arthur, and these are my Knights of the Round Table... Go and tell your master that we have been charged by God with a sacred quest. If he will give us food and shelter for the night, he can join us in our quest for the Holy Grail. GUARD: Well, I'll ask 'im but I don't think 'e'll be very keen... Uh, 'e's already got one, you see? ARTHUR: What? LANCELOT: He says they've already got one! ARTHUR: Are you sure he's got one? GUARD: Oh yes, it's ver' nice... —from Monty Python's The Holy Grail Computer graphics researchers have modeled a variety of fluid phenomena. Early work focused on water waves, using simple stochastic models for rough ocean surfaces (Perlin, 1985) and sim-ple kinematic models such as traveling sinusoids for progressive waves (Max, 1981). Later work introduced more sophisticated models for water waves including a stochastic model employing an empirical model of the power spectrum of a rough sea (Mastin et al., 1987), kinematic mod-els describing changes in the shape of waves with varying ocean depth. (Fournier and Reeves, 1986; Peachey, 1986; T'so and Barsky, 1987), and a dynamic model describing wave reflection and net transport of water (Kass and Miller, 1990). More recently, particle systems (Reeves, 1983) where the particles are point masses that do not interact with each other have been used to model ship wakes (Goss, 1990) and waterfalls (Sims, 1990). Interacting particle systems, where the interaction is based on molecular dynamic models, have been used to model highly viscous liquids (Miller and Pearce, 1989; Terzopoulos et al., 1989; Tonnesen, 1991). Despite considerable success with these approaches, animating fluids in general remains a challenging problem. 8 Chapter 2: Previous Work 9 2.1 W A T E R W A V E S Water waves have been modeled by stochastic, kinematic, and dynamic models. Stochastic motion models use random or probabilistic methods to add complexity where deterministic motion is not required. The small scale (relative to the image) of the waves often allows stochastic techniques to be used to bump map a surface model, possibly driven by a kinematic or dynamic model. Perlin (1985) modeled ocean waves by stochastically perturbing surface normals (bump map-ping) according to a superposition of randomly distributed spherical wavefront sources. A random spatial frequency / is assigned to each spherical wavefront source. The amplitude of the wavefronts are 1 / / , and the phase of the sources is modulated by a function of y/J. Mastin, Watterberg, and Mareda (1987) used Fourier synthesis with an empirically-based model of the power spectrum of a fully-aroused ocean surface. The algorithm consists of the following steps: 1. Generate a white-noise image. 2. Fast Fourier Transform (FFT) the image. 3. Modulate spatial frequencies based on an empirical model of the power spectrum. 4. Inverse FFT the image. 5. Generate a height field based on image values. The anisotropic filter attenuates frequencies in one direction and passes frequencies in a per-pendicular directions, giving long-crestedness. Motion is simulated by manipulating the FFT phase. An alternative approach to modeling water waves is to use a model of the changing geometry of the liquid surface. For the following review, a common notation is used: the XY plane models Chapter 2: Previous Work 10 the ocean at rest and the positive Z axis points out of the earth. When height fields are used, rj(x, y,t) = z is the height of the ocean. Max (1981) used superimposed traveling sinusoids n r](x, y,t) = ^2 a,i sm{piX + qiy - uJit) i= l where (pi,Qi) is related to the direction of sinusoid i. Linear small-amplitude wave theory gives a (traveling) sine wave as a solution of the linearized equations. The animator specifies the free parameters. Ts'o and Barsky (1987) extended Max's approach to include the effects of wave refraction by means of "wave-tracing", i.e., pre-computing the effect of refraction due to changing depth using Snell's law for a given sinusoid and direction. Peachey (1986) used a similar model but changed the shape of the wave according to wave steepness and ocean depth. The height is given by n r)(x,y,t) - ^ajWi(fraction^*(a,y,<)]) where Wi is a linear waveform with amplitude a .^ The phase function is Oi(x,y,t) = 6i(x,y,t0) — - . It depends on the cumulative effects of the depth of the water from the wave origin; these effects are calculated using numerical integration of a function relating the phase to variable depth. The wave profile function, Wi(u), 0 < u < 1, Wi ranges over the interval [—1,1], with the crest at Wi(0) = 1. The wave profile function is linearly blended between a sinusoidal function, Wi(u) = C0S(27TU), Chapter 2: Previous Work 11 and a quadratic function, Wi(t0 = 8 | u - i | 2 - l , based on wave steepness, S = H/L. When the depth is small, the parameter u is exponentiated to shift its values toward zero. This has the effect of steepening the front of the wave crest and stretching out the back of the crest (for waves beginning to break). Spray is modeled with particle systems. Fournier and Reeves (1986) modeled the ocean surface as a parametric surface and modeled wave motion by orbital motion of points on the surface. Unlike a height field representation, the parametric surface representation allows waves to curl over. The equations of the motion of a particle are x = XQ + rsin((f)) z = ZQ — rcos(^) where the phase angle is <\> = KXO — Lot. To model the effect of wind on top of the crests, the phase angle is modified as (f> = KXO — cot — XAzAt where Az is the height of the wave above the sea level at rest, At is displacement in time, and A is a constant of proportionality. This modification causes a given point to accelerate at the top of the orbit and decelerate at the bottom. Accounting for depth allows for refraction of wavefronts so that waves approaching a beach (with a shallow bottom) take the shape of the shore. The model relates wavelength to the depth h by: K = , . \/tanh(/c00/i) The effects of depth on the orbit of a point depend on the effects of depth of all other points before that point: the phase delay is cumulative. It is modeled by: Chapter 2: Previous Work 12 Breaking waves are modeled using x = XQ + r cos aSx sin <\> + sin aSz cos 4> z = ZQ + r cos aSz cos <f> + sin aSx cos cf> where Sx = I 52 = 5 x ( l - e " K ^ ) causing the orbits to become elongated in the direction of the wave motion. Stochastic bump mapping is used to model small-scale waves. Foam and spray are modeled by non-interacting point masses, with initial position and velocity based on the wave shape and celerity (speed) according to a physically-based model. Both are time-evolved according to Newton's second law with a gravitational force. Deterministic motion can also be described dynamically, i.e., describing the forces and com-puting the change in the shape of the liquid surface using Newton's second law of motion. This means only the initial conditions (mass, position, and velocity) and the forces need to be specified. Kass and Miller (1990) model fluid flow by simplifying hydrodynamic equations to the two-dimensional wave equation and then numerically solving it to animate a height field. This model describes wave refraction, reflection, and net transport of the liquid. The model also describes changing topology subject to the limits of a height field representation. To make the model amenable to a rapid and stable numerical solution, a number of assumptions are made: • The liquid surface can be represented by a height field. • The vertical component of the liquid velocity can be ignored. Chapter 2: Previous Work 13 • The horizontal component of the liquid velocity is small and approximately constant. • The depth varies slowly. With these assumptions, hydrodynamic equations of motion and continuity can be approxi-mated by the two-dimensional wave equation ^=9dV2h (2.1) where z = h(x) is the height of the liquid surface, z = b(x) is the height of the ground, d(x) = h(x) — b(x) is the water depth, and g is gravitational acceleration. Waves have celerity Vgd-Equation (2.1) is discretely approximated (in the ar-direction) using finite differences by and numerically integrated using a first order implicit method where hn - hn~l hn = hn = At hn - hn'1 At giving a system of linear equations with a simple tridiagonal matrix form that can be quickly solved. The linear nature of the problem and the implicit integration scheme make the solution method quite stable. The two-dimensional problem is solved by alternately solving the one-dimensional problem in the x and y directions using the alternating direction implicit (ADI) method. Chapter 2: Previous Work H 2.2 S H I P W A K E S Ship wakes—actually the foam and spray of ship wakes—have been simulated in real time using standard particle systems (Goss, 1990). New particles are periodically generated with initial positions and velocities determined by ad hoc kinematic and stochastic models of the bow and stern wakes. Khan (1994) is modeling ship wakes by developing a function that describes the the shape of the water surface is response to ship position, direction, and speed. This kinematic function is based on fluid dynamic models. 2.3 WATERFALLS Sims (1990) animates a waterfall and other liquid phenomena by using thousands of motion-blurred particles, point masses that move under the influence of gravity. Efficiency is achieved by the use of a parallel implementation of Reeves's (1983) particle systems. The particles do not interact and can pass through each other. 2.4 H I G H L Y V I S C O U S L I Q U I D S Highly viscous liquids have been modeled as a collection of interacting particles (Miller and Pearce, 1989; Terzopoulos et al., 1989; Tonnesen, 1991). By simulating molecular forces between pairs of particles, the system of particles as a whole behaves like a highly viscous liquid, e.g., lava, mud, and slime (Miller and Pearce, 1989). In general the simulated force fjj between particle i at position x, and particle j at position Xj is repulsive at shorter ranges and attractive at longer ranges for surface tension (cf. section 3.6). In particular, Miller and Pearce (1989) used Hj — (,xi Xj dn~ d™ Chapter 2: Previous Work 15 whereas Terzopoulos et al. (1989) used f I \(& a \ hj — rriimj (xt XJ) i n ^ j , where ( is how close the particles are allowed to be. Tonnesen (1991) incorporated thermal energy 9 as Ui = ( x i" Xj) T ^ T [nmd^ ~ nmd^)' where d = I the distance between the particles, a and 0 are constants of proportionality for the attractive and repulsive forces, and typically n = 12 and m = 6. Damping is added by the use of a force that is a function of the velocity and opposite in its direction. While the straightforward algorithm for computing the interparticle forces is 0(n2) for n par-ticles (the force on each particle depends on all other particles), the range of influence of the interparticle force can be limited and by using spatial subdivision methods, the computational complexity of this approach can be reduced. Time-evolving dynamic equations of interacting point masses using a purely explicit numerical solution methods is more appropriate for "soft collisions" between particles, since in other cases stability problems emerge unless very small time steps are used (Miller and Pearce, 1989). Attaching field functions to these particles and rendering an isosurface of this field (blobbies) provides a way to model a liquid surface with changing topology. 2.5 S T A T E OF T H E A R T To summarize the state of the art in modeling fluids for computer animation: • Stochastic models of waves are relatively advanced and convincing and can be superim-posed (via bump mapping) onto surface models controlled by kinematic and dynamic models for small-scale complexity. Chapter 2: Previous Work 16 • Kinematic models of waves are also quite convincing, and are usually efficient and easy to control, but require specific models for specific motions. • Dynamic models describe motion at a higher level (in terms of forces—not velocity or position, both of which, of course, can be derived from forces) and hence are more general, but are hard to control, and can be inefficient, unstable, and inaccurate. • Most wave models do not account for the changing topology of breaking waves. However, using particles as the control points for an implicit surface easily handles topological changes in the isosurface. • Most models are ad hoc and difficult to integrate to describe more general fluid phenom-ena. Going back a few centuries to the first principles of fluid dynamics for underlying and unifying concepts of fluid flow will address some of these difficulties. CHAPTER T H R E E A F E W F U N D A M E N T A L S OF F L U I D F L O W SECRET SACRED WARS ROACH: So many forces at work...so many cross-overs... so many tie-ins...I need more character! FLEA GLE R OA CHES: Uh-oh. SECRET SACRED WARS ROACH: And we all know the only way to create char-acter... don't we? —from Dave Sim's Cerebus This chapter briefly reviews some basic concepts of fluid mechanics necessary for the interactive flow field modeling methods of the next chapter. 3.1 I N T R O D U C T I O N Fluid flow has been studied for centuries. The challenge is to select an appropriate framework for computer animation purposes, i.e, one that satisfies the accuracy, efficiency, controllability, and generality criteria defined in the first chapter. An early consideration is whether to look to molecular dynamics or to hydrodynamics. As mentioned in the previous chapter, point masses governed by molecular forces have been used to model viscous liquids (Miller and Pearce, 1989; Terzopoulos et al., 1989; Tonnesen, 1991). However, at a macroscopic scale, the scale of hydrodynamics and human perception, a liquid is considered to be continuous and essentially incompressible; at a microscopic scale, the scale of molecular dynamics, compressible behaviour can be observed, as molecules attract and repel one another. Conservation of liquid volume is not guaranteed. Also, it is unclear what constitutes the liquid boundary when simulating a liquid with a relatively small number of point masses. A macroscopic description of fluid, i.e., a hydrodynamic model, seems more appropriate than a model based on dynamics at the molecular level as it inherently alleviates most of the above problems. 17 Chapter 3: A Few Fundamentals of Fluid Flow 18 To establish a background for the framework for integrating flow models for computer anima-tion, the fundamentals of fluid mechanics are briefly reviewed1. 3 . 2 E U L E R I A N A N D L A G R A N G I A N F R A M E S In the field of hydrodynamics, the motion of liquids is described in two ways: Lagrangian and Eulerian. In the Lagrangian approach, the motion of each fluid particle is followed as it moves through space. Fluid velocity in a Lagrangian description Vi(t) = ui + vj + wk (i, j , and k are the unit vectors and t is time) is given in terms of the velocity of a particular particle i, and fluid acceleration is simply the change in the particle's velocity over time. In the Eulerian approach, the motion of fluid particles at a given point in space is described. A Eulerian description of fluid velocity in Cartesian coordinates is given by: v(x, y, z, t) = u(x, y, z, t)i + v(x, y, z, i)j + w(x, y, z, t)k. The acceleration in Eulerian terms is not simply the change in fluid velocity over time at a given point, but rather the change in fluid velocity of a fluid particle moving through a given point. It is given by the Stokes (or substantial or total) derivative of the velocity: Dv d\ dv dv dv dv _ = _ + (v.V)v = _ + „ _ + „ - + « , - . Note that if a fluid particle is moving in a circle, for example, dv/dt = 0 whereas D\/Dt is nonzero. An Eulerian frame is generally more convenient for work in fluid mechanics. An Eulerian description of liquid motion can be converted to Lagrangian terms by taking the Taylor series expansion of the Lagrangian velocity, which to first order is va(<) = v £ ( a , t ) + (j va(*)d<J • V a v E ( a , i ) . The interested reader is referred to the following books for a more detailed treatment of hydrodynamics: Crapper (1984), Feynmann et al. (1964), Kinsman (1984), Lamb (1945), Newman (1977), O'Neill (1986), Potter (1975), Rouse (1959), Roy (1988), Sabersky (1964), and Stoker (1987). Chapter 3: A Few Fundamentals of Fluid Flow 19 where v a is the Lagrangian velocity of a fluid particle at point a at time t = 0 and \E is the Eulerian velocity. 3.3 E Q U A T I O N S OF M O T I O N While the equations of motion for fluids may be complex, they are simply versions of Newton's second law of motion, as stated in the Principia: the change of motion is proportional to the motive force impressed and is made in the direction of the right line in which that force is impressed, or f = ma, where the mass m is the constant of proportionality. Note that the equations of motion express conservation of momentum: the change in momentum over time equals the applied forces. The well-known Navier-Stokes equation is: / 0 ( ^ " + ( V ' V ) V ) = / 9 f - V P - | V ^ V ' v ) ' where p is the density, p is the pressure, f is the external force including gravity, and \i is the coefficient of dynamic viscosity. The Navier-Stokes equation can be simplified by assuming the fluid is inviscid (or ideal), i.e., the viscosity, the friction between fluid particles, is zero. The velocity of a fluid next to a boundary is zero: notice the dust on the blades of a fan. The velocity just a short distance away can be quite large, and the viscosity can have a dominate effect on the liquid behaviour at this boundary layer, creating vorticity which, depending on the geometry and Reynolds number (ratio of inertial to viscous forces), may cause a negligible disturbance or may expand until it drastically affects the entire flow pattern causing turbulent flow where the velocity at a given point varies erratically. Turbulent flow is usually contrasted with laminar flow where the flow is steady near boundaries. Away from the boundary layer the Chapter 3: A Few Fundamentals of Fluid Flow 20 effects of viscosity are generally negligible, and in the study of water waves, viscosity is usually ignored, i.e., the liquid is assumed to be inviscid. If the fluid is assumed to be inviscid, then the Navier-Stokes equations of motion reduce to the Euler equations of motion, which in Eulerian terms are ut + uux + vuy + wuz = - -ppx Vt + UVX + Wy + wvz = - -ppx -wt + uwx + vwy + wwz = - -ppx or in vector form In Lagrangian terms, the Euler equations of motion are pax = -px pay = -py - g paz = -pz or in vector form pa = p— = - V p - pg where v(i) is the velocity in Lagrangian terms. 3.4 K I N E M A T I C B O U N D A R Y C O N D I T I O N S (3.1) (3.2) (3.3) (3.4) Fluid does not flow through solid boundaries, of course; this constraint is express by the kine-matic boundary condition. For inviscid flow, if the fluid is in contact with a rigid boundary, the component of the velocity in the direction of the normal out of the fluid must match the normal component of the velocity of the boundary, u, v • n = u • n. (3.5) Chapter 3: A Few Fundamentals of Fluid Flow 21 For a fixed boundary this reduces to: v n = 0. For viscous flow, there is a no-slip condition on the tangential component of the fluid velocity. 3 . 5 B E R N O U L L I E Q U A T I O N Often the Euler equations of motion (3.2) are more useful when they are integrated to give a form of Bernoulli's equation. Here we derive Bernoulli's equation for irrotational and possibly unsteady flow (as opposed to the other, perhaps more familiar forms of Bernoulli's equation for steady flow). Euler's equation can be written as ^ + ( v - V ) v = - ^ - g . (3.6) ot p Defining the fluid speed as . . d(j> d(f> d(f> where v = W(p and using the vector analysis identity V ( y j = v x (V x v) + (v- V)v, allows the left-hand side of equation (3.6) to be written as ^ + ( v - V ) v = ^ ( V ^ ) + v Q / ) - v x ( V x v ) . (3.7) Since the fluid is assumed to be irrotational, V x v = 0, Chapter 3: A Few Fundamentals of Fluid Flow 22 and since — gz = g, equation (3.7) can be reduced to Integration gives Bernoulli's equation for irrotational but possibly unsteady flow « + ^ + £ + „ _ C ( ( ) . (3.8) As the constant of integration C(t) is a function of time only and has no effect on any spatial gradient it is usually taken to be zero. Often equation (3.8) is linearized and applied at the fixed surface z — 0: -^•+9V + - = 0 at z = 0 (3.9) at p where z = i](x, y, t) is the height of the free surface. 3.6 S U R F A C E T E N S I O N Molecules throughout a liquid experience attractive molecular forces, but these forces cancel out in the interior of a liquid. On the surface of a liquid, however, a molecule experiences a net attractive force towards the interior of the liquid. Thus, molecules in the surface layer have a higher potential energy than molecules in the interior of the liquid, and since a liquid tends to minimize its potential energy, it tends to minimize its surface area. The resultant behaviour— as if the surface were a stretched membrane—produces what is called surface tension. Surface tension is typically modeled by constraining the curvature of the liquid surface. Chapter 3: A Few Fundamentals of Fluid Flow 23 3.7 E Q U A T I O N OF C O N T I N U I T Y While the equations of motions express conservation of momentum, they do not express the conservation of mass. Considering the conservation of mass gives rise to another equation, the continuity equation. The continuity equation states the divergence of the density flux must be equal to the time change in density, This equation can be simplified by assuming the fluid is incompressible, i.e. the fluid volume does not change with changes in applied pressure. This approximation is often made in the study of fluid flow, and is quite reasonable for computer animation purposes. For example, the density of water increases by no more than 0.5% when the pressure applied is increased by 100 atmospheres for constant temperatures (Stoker, 1957). And while gaseous flow may seem to be compressible flow, almost all examples of compressible behaviour of a gas occur with respect to a closed volume—when the gas is free to move, it simply moves without being compressed (Potter, 1975). The assumption that the fluid is incompressible allows the continuity equation to be simplified to V - v = 0. (3.10) Thus, perhaps surprisingly, conservation of mass is expressed without a term for mass. For constant density2, the continuity equation also expresses conservation of fluid volume. Any surface advected with the flow has no flow through it and conserves the mass of the domain it bounds. The vector form of the continuity equation can be written out in in three common coordinate systems that will prove convenient: Cartesian, cylindrical and spherical. In Cartesian Note that technically incompressible does not necessarily mean the density is constant. A necessary and sufficient condition for a fluid to be incompressible is that the Stokes derivative of the liquid density be zero, i.e., Dp/Dt = 0, so while the density is constant along streamlines, it is not necessarily constant at all points of the fluid. However, this distinction is often ignored. Chapter 3: A Few Fundamentals of Fluid Flow 24 coordinates the continuity equation is: dvx(x,y,z) dvy(x,y,z) dvz(x,y,z) ^ Q 1 dx dy dz In cylindrical coordinates the continuity equation is: d(rvr(r,6,z)) dv0(r,6,z) dvz(r,6,z) _ ror rod oz In spherical coordinates the continuity equation is: d{vR(R,9^)R2) d(v0(R,0,<f>)sme) dv^(R,e,<f>) = R2dR i2 sin 000 RsmOdtf) ' For irrotational flow, i.e., when the curl of the velocity is zero, the velocity field can be repre-sented as the gradient of a scalar potential field: V<j>{x,y,z,t) = v(x,y,z,t) which when substituted into the continuity equation for incompressible fluid flow gives the potential (Laplace) equation: V2<f>(x,y,z) = 0. CHAPTER FOUR I N T E R A C T I V E F L O W F I E L D M O D E L I N G in-flu-ence [ME, fr. MF, fr. ML influentia, fr. L injiuent-, injluens, prp. oj injluere to flow in, jr. in- + jluere to flow ~ more at FLUID] la: an ethereal fluid held to flow from the stars and to affect the actions of humans — Webster's 7th Dictionary While dynamic simulation of fluid motion can be done efficiently enough for computer animation purposes under restrictive conditions (Kass and Miller, 1990), in general dynamic simulation of fluid flow appears to be too computationally expensive to be appropriate as a general tool for realistically animating fluids. Using straight dynamic simulation of hydrodynamic models as a method for animating fluids begs the following problems: 1. How are initial conditions realistically modeled? 2. How are turbulent effects created and controlled? 3. How is the motion controlled in general? In this chapter interactive flow field modeling methods are presented to address these problems. 4.1 O V E R V I E W Fluids present several challenges for computer animation stemming from their continuously deformable nature. To date, these challenges have not fully addressed by dynamic simulation methods. Consider using dynamic simulation to animate water flowing out of hose, making a loop, and flowing into a bucket. Hydrodynamic simulation can describe fluid motion in response to the forces acting on the fluid. These forces can be modeled (Sims, 1990), but would require the animator to guess what forces are required to have the water make a loop and flow into 25 Chapter 4-' Interactive Flow Field Modeling 26 the bucket. While the dynamic simulation of articulated solid objects can be controlled using kinematic constraints and inverse dynamics (Barzel and Barr, 1988; Isaacs and Cohen, 1987; Piatt and Barr, 1988; Witkin and Kass, 1988), with fluids the number of degrees of freedom is essentially infinite, so these constraint methods do not appear to be applicable. A priori, flow field modeling appears more appropriate. Sims (1990) presented ad hoc "velocity operators" for controlling the motion of particle systems. Ebert et al. (1993) used a combination of three-dimensional grids and ad hoc flow field functions to model flow fields. In these methods, the task of ensuring realism is left to the animator. A more accurate method is to use superposition of simple solutions to the potential equation such as those corresponding to source, sink, and vortex flow to model more complex flow fields (Haumann, 1991; Wejchert and Haumann, 1991). Using just these point source, sink, and vortex "flow primitives", however, makes certain mod-eling tasks difficult, e.g., modeling a path for the fluid to follow. To allow more control in modeling flow fields, a flow primitive based on a cubic B-spline is introduced. A new method of modeling turbulent flow is also presented that gives the animator greater control over the tur-bulence. Finally, a simple method of blending interactively modeled and dynamically simulated flow fields is presented. 4.2 P R I N C I P L E OF S U P E R P O S I T I O N The point flow primitives, the spline-based flow primitives, the turbulence modeling, and the control method for dynamic simulation are all integrated by a common framework: the conti-nuity equation for incompressible flow (3.10). For partial differential equations that are both linear and homogeneous, such as equation (3.10), the principle of superposition applies: if v i , V2, . . . , v„ are solutions to equation (3.10) and c\, C2, • • •, c„ are scalars, then a linear com-bination of these solutions ClVl + c2v2 + • • • + c„vn is also a solution. Thus, flow fields satisfying the continuity equation for incompressible flow can be arbitrarily scaled and summed and result in a flow field that satisfies the continuity Chapter 4-' Interactive Flow Field Modeling 27 equation. This principle is the basis of all the methods in this chapter. 4 . 3 B A S I C F L O W F I E L D S A number of simple flow fields that satisfy the continuity equation for incompressible flow are well-known. Such flow fields include those corresponding to uniform, point source, point sink, point dipole, and continuous straight-line vortex flows. A well-known method of constructing more complex flow fields is to superpose a number of these "basic" flow fields (flow primitives). 4 . 3 . 1 U N I F O R M The simplest flow pattern is uniform flow where the fluid velocity at every point is the same, ai + bj + ck. This clearly satisfies the continuity equation for incompressible flow: dvx dvv dvz da db dc —- + —- + —- = h^- + — = 0 dx dy dz dx ay dz Note that a linear combination of uniform flow fields will simply result in another uniform flow field. More generally, v = (a + f(y, z))\ + (b + f{x, z))l + (c + f(x, y))k satisfies the continuity equation for incompressible flow. 4 . 3 . 2 P O I N T S O U R C E A N D S I N K Another basic flow field is one corresponding to the flow from a point source located at the origin (Figure 4.1). Chapter 1^: Interactive Flow Field Modeling 28 Figure 4.1: Flow field of point source. In spherical coordinates (R, 6, <f>) this flow field is given by: m ; (4.1) Note that there is a singularity at the origin. The constant m is called the strength of the source: the discharge through any closed surface surrounding the origin is 4wm. It can be easily seen that equation (4.1) satisfies the continuity equation by recalling the con-tinuity equation in spherical coordinates: d(uR2) d(vsm9) Ow + + R2dR R sin 686 Ranffd<f> 0. Negating equation (4.1) gives m Chapter J^: Interactive Flow Field Modeling 29 Figure 4.2: Flow field of point sink, which represents the flow towards a point sink at the origin (Figure 4.2). 4.3.3 V O R T E X Using cylindrical coordinates (r, 0, z), the flow field corresponding to straight-line vortex is given by: v = - J . r (4.2) Figure 4.3 shows the flow field for a vortex. 4.4 S P L I N E - B A S E D F L O W F I E L D M O D E L I N G While the basic flow fields (point flow primitives) can be linearly combined to produce more complex flow fields that satisfy the continuity equation for incompressible flow, it is difficult Chapter ^: Interactive Flow Field Modeling 30 * I \ % 1 N>" K -ft" \ W^ s f Figure 4.3: Flow field of line vortex. Chapter 4'- Interactive Flow Field Modeling 31 to obtain specific motion, e.g., directed motion along a given path, using only these basic flow fields. A more powerful flow primitive is desired. 4.4.1 O V E R V I E W An interactive flow field modeling method should minimize the effort required by the animator to realize the desired flow field. An intuitive approach would be for the animator to design the general flow pattern by specifying some streamlines in the flow field. Streamlines are lines that are tangential to the fluid velocity; for steady flow, they are the lines a fluid particle will follow. After specifying some streamlines, a realistic flow field would then be computed that contains those streamlines. This computation could be accomplished by a relaxation method or some other numerical solution method given that a well-defined problem could be developed. However, such a method would require solving a partial differential equation in three dimensions. A simpler and much more efficient approach is to use flow primitives based on curves, say cubic B-splines, that have flow fields where the streamlines follow the shape of the curve and the magnitude of the flow attenuates away from it. Superposition of these spline-based flow primitives would then automatically give blending between the primitives where each primitive could be weighted for either local or global effect. Such a spline-based flow primitive can be developed by integrating a special point primitive along a spline. This point primitive—call it a directed flow primitive—has a specified velocity at a given point (say the origin) that attenuates in magnitude moving away from this point yet maintains the same direction as much as possible while satisfying the continuity equation. This directed flow primitive can then be continuously distributed (integrated) over a spline such that the direction of each directed flow primitive on the spline is always tangential to the spline, giving a flow field where the streamlines of the flow correspond to the shape of the spline and attenuate radially in magnitude away from the spline. Chapter 4'- Interactive Flow Field Modeling 32 4.4.2 A D I R E C T E D F L O W P R I M I T I V E Criteria for the flow field of the directed flow primitive can be defined as follows: • The velocity is a maximum at the origin and is oriented in the direction of the positive z axis. • The magnitude of the velocity goes to zero moving away from the origin. • The direction of the velocity everywhere is close to the direction at the origin, more so where the magnitude of the velocity is greater. • The magnitude of z coordinate of the velocity can be an arbitrary function of the radial distance from the z axis. • The flow field satisfies the continuity equation. Together, these properties ensure when this point flow primitive is integrated along a curve, the streamlines of the resulting flow field correspond to the shape of the curve and the flow is strongest near the curve. Such a flow primitive was derived in cylindrical coordinates (Figure 4.4): v = vri + vej + vzk (4.3) where cz vr(x,y,z,t)= (4.4) (a + zz) (b + rz) ve(x,y,z,t) = 0, (4.5) and ^ v> z>f) = ^T^) ( ^ T H ) - (6T7^) + / ( r ) ( 4-6) where a, b, c are constants. Figure 4.5 shows vz for a fixed r. A plot of vr for a fixed z would be similar. Chapter j : Interactive Flow Field Modeling Figure 4.4: Flow field of directed flow primitive. Chapter 4-' Interactive Flow Field Modeling Figure 4.5: A plot of the vz component of the directed flow primitive for a fixed r. This flow field can be shown to satisfy the continuity equation which in cylindrical coordinates is: f) (rii(T ft vW rli)n(r ft ?\ f)ii Ir ft y\ (4.7) d (rvr(r, 6, z)) dve(r,6,z) dvz(r,0,z) _ rdr "dd dz as and d(rvr) d crz cz rdr rdr \(a + z2f (b + r2) J (a + z2)2 \r(b + r2) (b + r2) 2r dvz _ d dz dz 2r 2(a + z2) \r(b + r2) (b + r2)2 + f(r) -2cz 2r 2(a + z2)2 \r(b+r2) (b + r2)2 4 . 4 . 3 A S P L I N E - B A S E D F L O W P R I M I T I V E All that remains in the derivation of the spline-based flow primitive is to integrate the directed flow primitive over a cubic B-spline. Cubic B-splines are chosen as a basis of this fluid motion modeling tool because they are familiar motion modeling tools to most computer animators. Chapter 4'- Interactive Flow Field Modeling 35 Cubic B-splines are a type of parametric piecewise cubic curves tha t approximate a series of m + 1 control points Po, -Pi? • • • 5 Pm,m > 3, with a curve consisting of m - 2 cubic polynomial segments QZ^QA, • •., Qm. The parameter range on which Qi is defined is U < t < £;+i for 3 < i < m. For each i > 4, there is a join point or knot between Q;_i and Qi at the parameter value ti ( the knot value). The initial point at t3 and final point at fm+i are also knots, for a total of m — 1 knots. The uniform nonrational B-spline formulation for curve segment i is Q.-(*) = Xi(t) yi(t) Zi(t) T,-Mg s GB S i ti <t < ti+i (4.8) where and the B-spline basis matrix is (t-tt)3 (t-U)2 (t-ti) 1 MBs - 1 3 3 1 3 - 6 3 0 - 3 0 3 0 1 4 1 0 (4.9) and the B-spline geometry vector is: GBSl = Pi-3 Pi-2 P-l Pi (4.10) Expanding equation (4.8) out gives: Qi(t ~ U ( I - * )3 j - 3 + 3t3 - 6t2 + 4 6 Pi-2 + 3t3 + 3t2 + 3t + 1 6 Pi-i + -zPi 6 (4.11) Chapter 4-' Interactive Flow Field Modeling for 0 < t < 1 and 3 < i < m. Nonuniform nonrational B-splines are given by: Qj-(i) — Pj_3B,-_3,4 + P,-_2Bj_2,4 + Pj - lBj -1 ,4 + P8'B;,4 (4.12) for 3 < i < m and U < t < ti-\ where Bi,i{t) 1 t; < t < ti+i 0 otherwise Bi,2(t) = J-Ji-Bi^t) + Jt+2 J Bi+ltl(t) ti+l — U ti+2 ~ ti+1 Bid*) = 7LJlrBi,2(t) + Jt+3 J Bi+h2(t) ti+2 — ti ti+3 ~ ti+i BiM = 7L~\Bldt) + 4 U+4 , f Bt+1>3(t) ti+3 — ti ti+i — ti+l (4.13) (4.14) (4.15) (4.16) Integration over a parametric curve C with parameter t and arc length s is given by: The arc length s from a to b on a parametric curve in three dimensions is: -i:f( = f\f^\\fdy\\fdz dtj +{ft) +Vdt]dt and so integrating basic flow fields over splines takes the form: /fl v(.,», w.).»w,>*>)/(£)% (t )' + (^)2* (4.17) where (XQ, yo, ZQ) is the location of the point primitive. Chapter 4'- Interactive Flow Field Modeling 31 ^ " - • < < : • • . • • • - . ' - - S X < / \ ' | i ' r \ \ ^ - - • - . . • • - * Figure 4.6: A spline flow primitive. Gaussian quadrature can be used to approximate the integral: rb N / W(x)f(x)dx&J2Wif(Xi) Ja i=l When W(x) = 1, the numerical integration procedure is known as Gauss-Legendre integration, and there are procedures to calculate the weights and abscissas (Press et al., 1988). Integration of the directed flow primitive gives the flow field of spline-based flow primitive (Figures 4.6 and 4.7). Figure 4.8 shows the flow field resulting from two spline flow primitives. When kinematic control over the changes in the flow field are desired, time-varying flow prim-itives can be used. The existence, strength, and position of these primitives can vary in time. Note that the rate of change of the strength of the flow primitives is directly related to a force acting on the flow field. These changes can be made explicitly by the animator or a wide range of models can be used, e.g., the flow primitives could be advected by a flow field modeled by the methods of this chapter. Chapter 4'- Interactive Flow Field Modeling 38 ^*** I ', -1 v Figure 4.7: Another view of spline flow primitive. Figure 4.8: Flow field of two spline flow primitives. Chapter 4'- Interactive Flow Field Modeling 39 Figure 4.9: Turbulent flow. 4.5 T U R B U L E N C E Turbulent flow produces much of the visual complexity of fluid motion. A number of computer graphics researchers have developed models of turbulent flow fields that can be used (Shinya and Fournier, 1992; Ebert, 1993; Stam and Fiume, 1993). These flow fields are modeled using Fourier synthesis, i.e., modifying a white noise spectrum in the frequency domain and then taking the inverse FFT of it. This approach presents several difficulties for animating the turbulent motion of fluids: • The fluid has no effect on the turbulent field. • It is not clear how to localize turbulent motion in space or time. • Uniform grids are generally required, limiting resolution. For example, it is unclear how to use these methods to create an animation of a rock in a river creating turbulent motion that diffuses downstream. An alternative approach is suggested based on a concept used in fluid dynamics: describing turbulent flow in terms of vortices of various shapes, size, and rotational speeds being carried along by the mean flow (Rouse, 1959). Flows corresponding to vortex flow can be generated where stochastic motion is desired and these flows can be advected with the mean flow field. The Chapter 4- Interactive Flow Field Modeling 40 Figure 4.10: Turbulent flow. stochastic distribution (in space and time) of these vortices can be based on power spectrums introduced in graphics or from the study of turbulent flow or be specified by the animator. Further, the attributes of these vortices can change over time, and the vortices themselves can eventually dissipate according to parameters defined by the animator. Besides interactive approaches to modeling the generation of turbulence, models of the formation of turbulence can be used. Turbulence can always safely be assumed to be present in flows previously or currently in a state of shear at moderate to high Reynolds numbers (ratio of inertial to viscous forces). Figures 4.9 and 4.10 shows frames from an interactive animation of turbulent flow. A uniform flow field is used as the mean flow field. Particles are advected upwards from a fluid source at the bottom of the frames. Part of the way up, a turbulent source generates vortices for a simulation of, for example, smoke from a recently extinguished candle. 4.6 A C O N T I N U U M OF C O N T R O L As discussed, the continuity equation for incompressible flow (3.10) can be used as a basis for the framework for integrating flow models for computer animation discussed in the first chapter. This equation completely and kinematically describes an incompressible flow field and is independent of the equations of motion being used. In the framework, fluid flow is modeled in an Eulerian frame, and the flow is defined everywhere. Chapter J^: Interactive Flow Field Modeling 41 The flow is decomposed into two main components, mean flow and turbulent flow. The mean flow is further decomposed into flows interactively modeled using kinematic methods and flows derived from dynamic simulation. The mean flow can be computed on a grid to make it more efficient; the turbulent flow is described by continuous functions for detail at small-scales. Using dynamic models that describe changes in the flow field, such as the Navier-Stokes equations, dynamic simulation methods can be used to describe a time-dependent flow field vd(x,y,z,t). The flow primitives presented in this chapter can be arbitrarily superposed and linearly weighted in time as: n ^2ci(t)vi(x,y,z,t) where is directly related to a force on the fluid, but unlike modeling forces, modeling the flow field allows the animator to deal directly with the motion of the fluid and not with the changes in the motion of the fluid. And finally, turbulence can be modeled by using a turbulent flow field, vt. This flow field can be computed using the methods of Stam and Fiume (1993), Shinya and Fournier (1992), or the methods introduced in this chapter. These flow fields can be trivially integrated by superposition: n v = cdvd(x, y, z,t) + J2 Ci(t)vi(x, y, z, t) + ctvt(x, y, z, t) (4.19) »=i while satisfying the continuity equation for incompressible flow: V • I cdvd(x, y, z,t) + ^2 Ci(t)vi(x, y, z, t) + ctvt(x, y, z,t)\ = 0. (4.20) Chapter 4' Interactive Flow Field Modeling 42 Thus, the animator can arbitrarily weight the effects of the flow field from dynamic simulation and the interactively modeled flow field, providing a continuum of control from letting dynamic simulation run free to an explicitly modeled flow pattern. Further, turbulent motion can be superposed on the resulting flow field at will. CHAPTER FIVE IMPLEMENTATION AND RESULTS Those are my principles. If you don't like them I have others. —Groucho Marx In this chapter, the implementation of a small animation system incorporating the interactive flow field modeling methods of the previous chapter is described. The use of this system and the flow modeling methods are discussed. 5.1 IMPLEMENTATION In order to test the framework and flow modeling methods, it was necessary to implement a relatively small animation system (about 10,000 lines of code). While various toolkits exist to assist the development of animation systems, fluid flow does not mesh well with the currently popular object-oriented paradigm of such toolkits, and thus an animation system had to be written from scratch. Using the C programming language, the workhorse of the computer graphics community, and Graphics Library (GL) from Silicon Graphics the animation system FLOW was implemented. FLOW allows the interactive modeling and visualization of flow fields and provides a testbed for the methods of the previous chapter. Geometric models, from particles to complex polyhedrons, can be advected in the flow field. Animation scripts for the renders Rayshade (Kolb, 1991) and Optik (Amanatides et al., 1993) can be automatically generated. 43 Chapter 5: Implementation and Results 44 5.1.1 I N T E R A C T I O N A large part (roughly a third) of the implementation concerns the user interface. The interface toolkit FORMS (Overmars, 1991) greatly simplified this task. The user can position flow primitives using the mouse to model the mean flow field and then place turbulent sources in this flow field. Geometric models can be interactively positioned in the flow field. Most modeling parameters can be interactively adjusted. 5.1.2 F L O W VISUALIZATION Visualization of vector fields is an active area of computer graphics research (Cabral and Lee-dom, 1993). Two standard techniques were found to be effective, though not ideal: particle traces and vector arrows. With particle traces (for steady flow, these are streamlines) the user can position a cursor in the flow field, and from a disc normal to the velocity at that point, particles are advected by means of Runge-Kutta numerical integration for a distance that can be interactively varied. With vector arrows, a grid is constructed where the nodes have arrows representing the magnitude and direction of the velocity at that point. 5.1.3 R E N D E R I N G For interactive work, geometric primitives are advected with the flow using standard graphics library routines. Several thousand particles can be advected at interactive rates on a Silicon Graphics Crimson workstation. For producing the final animation, scripts are output that can be used by the raytracers Optik and Rayshade to produce high-quality images. Particles can be used as points that define an isosurface (known as a "blobby") to provide a surface model for the raytracing of liquid models. Chapter 5: Implementation and Results 45 5.2 U S I N G FLOW To create an animation using FLOW, the following steps are taken: 1. Using point and spline flow primitives, a flow field is constructed. 2. Interactively using one of the flow the visualization methods, the flow field is inspected and modified. 3. Geometric models are interactively placed into the flow field and advected by it. 4. When a satisfactory sequence has been obtained, the results are recorded as a series of Optik or Rayshade scripts. Flow fields from dynamic simulations can be imported into FLOW and blended with the flow fields that were interactively modeled, but this has not been tested. 5.3 R E S U L T S Using cubic B-splines as flow primitives is a promising method of designing flow fields, but more work is required to refine this new flow primitive to make it a more useful animation tool. The number of degrees of freedom available to the animator is quite high: the animator is responsible for controlling the magnitude and radial influence of the flow along each spline. The turbulent flow modeling methods were surprisingly effective, and a small number of vortices were required to give good results. The simplicity of this method is attractive to the animator. One approach to modeling flow around an object is to associate a distribution of point source flow primitives with the object. Figure 5.1 shows a simple example where a single point source flow primitive is used to model flow around a sphere. In this figure the point source flow primitive is at the center of the sphere. The flow field for this source primitive is superposed with a uniform flow field oriented upwards in the figure. Particles are created under the sphere and are advected with the resulting flow field: up and around the sphere. In general a distribution Chapter 5: Implementation and Results 46 Figure 5.1: Flow around object. of point sources and sinks can be used to simulate flow around an object. While realizing accurate flow patterns around complex objects using distributions of point primitives may be a nontrivial task, for computer animation often crude approximations to the actual flow pattern are adequate. A short animation called Liquid Skull was produced to demonstrate how a polygonal object can be advected in an animator-designed flow field (see figures 5.2 to 5.3). This animation represents X-rays of an overly ambitious graduate student's skull as he tackles a thesis topic that is much too large. Chapter 5: Implementation and Results 47 Figure 5.2: Frame one from Liquid Skull Figure 5.3: Frame two from Liquid Skull A 4 / / / Figure 5.4: Frame three from Liquid Skull Figure 5.5: Frame four from Liquid Skull Chapter 5: Implementation and Results Figure 5.6: Frame five from Liquid Skull Figure 5.7: Frame six from Liquid Skull / / / / / Figure 5.8: Frame seven from Liquid Skull Figure 5.9: Frame eight from Liquid Skull Chapter 5: Implementation and Results 49 / / / Figure 5.10: Frame nine from Liquid Skull Figure 5.11: Frame ten from Liquid Skull Figure 5.12: Frame eleven from Liquid Skull Figure 5.13: Frame twelve from Liquid Skull Chapter 5: Implementation and Results 50 Figure 5.14: Frame thirteen from Liquid Skull Figure 5.15: Frame fourteen from Liquid Skull / Figure 5.16: Frame fifteen from Liquid Skull Figure 5.17: Frame sixteen from Liquid Skull CHAPTER SIX CONCLUSIONS AND F U T U R E W O R K Don't let it end like this. Tell them I said something. —Last words of Pancho Villa 6.1 C O N C L U S I O N S A general framework based on a first principle of fluid mechanics, the conservation of fluid mass, was presented. This simple framework, using linear combinations of solutions to the continuity equation for incompressible flow, allows the realistic blending of animator-modeled flow fields and flow fields resulting from dynamic simulation. Numerical solution of even the simplest hy-drodynamic models for the types of flows of interest to computer animation—three-dimensional, free-surface flow with changing topologies—remains an active area of computational fluid dy-namics research. Thus, most of the effort was focused on novel interactive flow field modeling methods based on the manipulation of splines that influence the flow and correspond to stream-lines in it. These flows can be superimposed with the well-known source, sink, dipole, and vortex flows. Turbulence is modeled by using stochastic distributions of vortices that are advected with the mean flow. This has several advantages, since the turbulence has a small-scale effect and is continuously defined by functions whereas the mean flow can be given on a three-dimensional grid. The use of flow fields allows any geometric model to be advected with the flow. The flow fields can also be used as three-dimensional textures. These flow fields realistically model the motion of fluids: the animator can specify the general motion of fluid without worrying about collision detection within the fluid, maintaining constant volume, or the details of the motion. The result is a method of designing and controlling fluid motion for computer animation that is part of a general, efficient, and realistic method of animating fluids. 51 Chapter 6: Conclusions and Future Work 52 6.2 F U T U R E W O R K A main goal of this thesis is to avoid the ad hoc methods of previous work, and every effort was made to make the methods introduced amenable to easy refinement and extension. It is hoped that the integrated approach of this thesis along with the general hydrodynamic framework invite future work. The framework was designed to easily integrate flow fields produced by dynamic simulation. Considerable effort went into exploring many rapid and stable numerical solution methods for simple hydrodynamic models, but even the simplest models present formidable challenges. One potentially fruitful avenue of future work: modeling liquid geometrically by oriented particle systems and using the boundary element method (Banerjee and Butterfield, 1981; Hartmann, 1989; Liggett and Liu, 1983; Pozrikidis, 1992) to solve the relevant equations. While the bound-ary element method is currently too slow for computer animation purposes, it may be made more efficient in the near future. Another approach is to use Smoothed Particle Hydrodynam-ics (SPH) (Gingold and Monaghan, 1982; Haddad et al., 1991; Monaghan and Gingold, 1983; Monaghan and Lattanzio, 1985) which involves using particles that are filtered point samples. A challenge with using SPH for incompressible free-surface flow is to propose a well-defined problem and derive a stable numerical solution method for it—initial-boundary value problems are notoriously subtle. Other possible extensions include compressible flow and reactive flow, allowing, for example, fire. Also, closely related to fluid motion is the motion of elastically deformable models. The boundary element method is also applicable to these models. Ultimately, the goal is a unified approach to the modeling of natural phenomena. This thesis is one step on the long path to this goal. Glossary advect transport by a current in a fluid boundary layer part of a fluid flowing near a body which has a reduced flow due to viscosity compressible flow flow where the fluid volume can change with changes in applied pressure Eulerian frame a frame of reference where fluid properties are described at fixed spatial locations inviscid zero viscosity, i.e., not viscous irrotational flow flow with zero vorticity incompressible flow flow where the fluid volume does not change with changes in applied pressure Lagrangian frame a frame of reference where fluid properties are described with respect to specific fluid particles laminar flow flow that is steady near boundaries (unlike turbulent flow) Reynolds number ratio of viscous to inertial forces steady flow flow where the fluid velocity does not change with time Stokes derivative derivative taken in an Eulerian frame streamline line tangential to fluid velocity; for steady flows, a fluid particle follows a streamline turbulent flow flow where the fluid velocity varies erratically uniform flow flow where the fluid velocity is the same at all points in the fluid unsteady flow flow where the fluid velocity changes with time viscosity property of a fluid that enables it to develop and maintain shearing stress, providing resistance to flow viscous having viscosity; contrasted with inviscid vorticity a vector measure of local rotation in a fluid flow 53 Bibliography [1] AMANATIDES, J., BUCHANAN, J., POULIN, P. , AND W O O , A. Optik User's Guide: Version 2.6. 1993. [2] BANERJEE, P. K., AND BUTTERFIELD, R. Boundary Element Methods in Enigineering Science. McGraw-Hill, 1981. [3] BARZEL, R., AND BARR, A. H. A Modeling System Based On Dynamic Constraints. Computer Graphics (SIGGRAPH '88 Proceedings), 22:4 (August 1988), 179-188. [4] CABRAL, B., AND LEEDOM, L. C. Imaging vector fields using line integral convolution. Computer Graphics (SIGGRAPH '93 Proceedings) (August 1993), 263-270. [5] CRAPPER, G. D. Introduction to Water Waves. Ellis Horwood Limited, 1984. [6] EBERT, D. S., CARLSON, W. E., AND PARENT, R. E. Solid Spaces and Inverse Par-ticle Systems for Controlling the Animation of Gases and Fluids. The Visual Computer {expected November 1993). [7] FEYNMAN, R. P. , LEIGHTON, R. B., AND ANDS, M. S. The Feynman Lectures on Physics. Addison-Wesley, Reading, Massachusetts, 1963. [8] FOURNIER, A., AND REEVES, W. T. A Simple Model of Ocean Waves. Computer Graphics (SIGGRAPH '86 Proceedings), 20:4 (August 1986), 75-84. [9] GINGOLD, R. A., AND MONAGHAN, J. J. Kernel Estimates as a Basis for General Particle Methods in Hyrdodynamics. Journal of Computational Physics, ^6 (1982), 429-453. [10] Goss, M. E. A Real Time Particle System for Display of Ship Wakes. IEEE Computer Graphics and Applications, 10:3 (May 1990), 30-35. [11] HADDAD, B., CLAUSSET, F., AND COMBES, F . Vectorising the Smooth Particle Hydro-dynamics. Journal of Computational Physics, 97 (1991), 103-126. [12] HAHN, J. K. Realistic Animation of Rigid Bodies. Computer Graphics (SIGGRAPH '88 Proceedings), 22:4 (August 1988), 299-308. [13] HARTMANN, F . Introduction to Boundary Elements: Theory and Applications. Springer-Verlag, 1989. [14] HAUMANN, D., W E J C H E R T , J., ARYA, K., BACON, B., KHORASANI, A., NORTON, A., AND SWEENEY, P . An Application of Motion Design and Control For Physically-Based Animation. Proceedings of Graphics Interface '91 (June 1991), 279-286. 54 Bibliography 55 [15] ISAACS, P . M., AND COHEN, M. F. Controlling Dynamic Simulation with Kinematic Constraints, Behavior Functions and Inverse Dynamics. Computer Graphics (SIGGRAPH '87 Proceedings), 21:4 (July 1987), 215-224. [16] KASS, M., AND MILLER, G. Rapid, Stable Fluid Dynamics for Computer Graphics. Computer Graphics (SIGGRAPH '90 Proceedings), 24:4 (August 1990), 49-57. [17] KINSMAN, B. Wind Waves. Dover, 1984. [18] KOLB, C. E. Rayshade User's Guide and Reference Manual. 1991. [19] LAMB, H. Hydrodynamics. Dover, 1945. [20] LIGGETT, J. A., AND LIU, P. L.-F. The Boundary Integral Equation Method for Porous Media Flow. George Allen & Unwin, 1983. [21] MASTIN, G., WATTERBERG, P. , AND MAREDA, J. Fourier Synthesis of Ocean Scenes. IEEE Computer Graphics and Applications, 7:3 (March 1987), 16-23. [22] M A X , N. Vectorized Procedural Models for Natural Terrain: Waves and Islands in the Sunset. Computer Graphics (SIGGRAPH '81 Proceedings), 15:3 (August 1981), 317-324. [23] MILLER, G., AND PEARCE, A. Globular Dynamics: A Connected Particle System for Animating Viscous Fluids. Computers and Graphics, 13:3 (1989), 305-309. [24] MONAGHAN, J., AND GINGOLD, R. A. Shock Simulation by the Particle Method SPH. Journal of Computational Physics, 52 (1983), 374-389. [25] MONAGHAN, J., AND LATTANZIO, J. A Refined Particle Method for Astrophysical Prob-lems. Astronomy and Astrophysics, 149 (1985), 135-143. [26] NEWMAN, J. N. Marine Hydrodynamics. MIT Press, 1977. [27] O ' N E I L L , M. E., AND CHORLTON, F . Ideal and Incompressible Fluid Dynamics. Ellis Horwood Limited, 1986. [28] OVERMARS, M. Forms Library: A Graphical User Interface Toolkit for Silicon Graphics Workstations. 1991. [29] PEACHEY, D. Modeling Waves and Surf. Computer Graphics (SIGGRAPH '86 Proceed-ings), 20:4 (August 1986), 65-74. [30] PERLIN, K. An Image Synthesizer. Computer Graphics (SIGGRAPH '85 Proceedings), 19:3 (July 1985), 287-296. [31] PLATT, J., AND BARR, A. Constraint Methods for Flexible Models. Computer Graphics (SIGGRAPH '88 Proceedings), 22:4 (August 1988), 279-288. [32] POTTER, M. C , AND FOSS, J. F . Fluid Mechanics. The Ronald Press Company, New York, 1975. Bibliography 56 [33] POZRIKIDIS, C. Boundary Integral and Singularity Methods for Linearized Viscous Flow. Cambridge University Press, 1992. [34] PRESS, W. H., FLANNERY, B. P. , TEUKOLSKY, S. A., AND VETTERLING, W. T. Nu-merical Recipes in C. Cambridge University Press, 1988. [35] REEVES, W. T. Particle systems - A technique for modeling a class of fuzzy objects. Computer Graphics (SIGGRAPH '83 Proceedings), 17:3 (July 1983), 359-376. [36] ROUSE, H. Advanced Mechanics of Fluids. John Wiley & Sons, New York, 1959. [37] ROY, D. N. Applied Fluid Mechanics. Ellis Horwood Limited, New York, 1988. [38] SABERSKY, R. H., AND ACOSTA, A. J. Fluid Flow. Macmillan Company, New York, 1964. [39] SHINYA, M., AND FOURNIER, A. Stochastic motion — Motion under the influence of win d. Computer Graphics Forum (EUROGRAPHICS '92 Proceedings), 11:3 (September 1992), 119-128. [40] SIMS, K. Particle Animation and Rendering Using Data Parallel Computation. Computer Graphics (SIGGRAPH '90 Proceedings), 24:4 (August 1990), 405-413. [41] STAM, J., AND FlUME, E. Turbulent wind fields for gaseous phenomena. Computer Graphics (SIGGRAPH '93 Proceedings) (August 1993), 369-376. [42] STOKER, J. J. Water Waves. Interscience Publishers, 1957. [43] TERZOPOULOS, D., PLATT, J., AND FLEISCHER, K. Heating and Melting Deformable Models (From Goop to Glop). Proceedings of Graphics Interface 1989 (June 1989), 219-226. [44] TONNESEN, D. Modeling Liquids and Solids Using Thermal Particles. Proceedings of Graphics Interface 1991 (June 1991), 255-262. [45] Ts 'o , P . Y., AND BARSKY, B. A. Modeling and Rendering Waves: Wave-Tracing Us-ing Beta-Splines and Reflective and Refractive Texture Mapping. ACM Transactions on Graphics, 6:3 (July 1987), 191-214. [46] WEJCHERT, J., AND HAUMANN, D. Animation Aerodynamics. Computer Graphics (SIG-GRAPH '91 Proceedings), 25:4 (July 1991), 19-22. [47] WITKIN, A., AND KASS, M. Spacetime Constraints. Computer Graphics (SIGGRAPH '88 Proceedings), 22:4 (August 1988), 159-168. [48] WYVILL, G., PEARCE, A., AND WYVILL, B. The Representation of Water. Proceedings of Graphics Interface '86 (May 1986), 217-222. 


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items