University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don FussellParticle SystemsUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 2ReadingRequired:Witkin, Particle System Dynamics, SIGGRAPH ’97course notes on Physically Based Modeling.Witkin and Baraff, Differential Equation Basics,SIGGRAPH ’01 course notes on Physically BasedModeling.OptionalHocknew and Eastwood. Computer simulation usingparticles. Adam Hilger, New York, 1988.Gavin Miller. “The motion dynamics of snakes andworms.” Computer Graphics 22:169-178, 1988.University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 3What are particle systems?A particle system is a collection of pointmasses that obeys some physical laws (e.g,gravity, heat convection, spring behaviors,…).Particle systems can be used to simulate allsorts of physical phenomena:University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 4Particle in a flow fieldWe begin with a single particle with:Position,Velocity,Suppose the velocity is actually dictated bysome driving function g:g(x,t)xy ! r x =xy" # $ % & ' ! r v = x•=dr x dt=dx dtdy dt" # $ % & ' ! x•= g(r x ,t)University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 5Vector fieldsAt any moment in time, the function g defines avector field over x:How does our particle move through the vectorfield?University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 6Diff eqs and integral curvesThe equationis actually a first order differential equation.We can solve for x through time by starting at an initialpoint and stepping along the vector field:This is called an initial value problem and the solution iscalled an integral curve.Start Here ! x•= g(r x ,t)University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 7Euler’s methodOne simple approach is to choose a time step, Δt, and take linear stepsalong the flow:Writing as a time iteration:This approach is called Euler’s method and looks like:Properties:Simplest numerical methodBigger steps, bigger errors. Error ~ O(Δt2).Need to take pretty small steps, so not very efficient. Better (morecomplicated) methods exist, e.g., “Runge-Kutta” and “implicitintegration.” ! r x i+1=r x i+ "t #r v i ! r x (t + "t) =r x (t) + "t # x(t) =r x (t) + "t # g(r x ,t)! •University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 8Particle in a force fieldNow consider a particle in a force field f.In this case, the particle has:Mass, mAcceleration,The particle obeys Newton’s law:The force field f can in general depend on the position andvelocity of the particle as well as time.Thus, with some rearrangement, we end up with: ! r a " x =dr v dt=d2r x dt2! •• ! r f = mr a = mx! •• ! x =r f (r x ,x,t)m! ••! •University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 9This equation:is a second order differential equation.Our solution method, though, worked on first order differential equations.We can rewrite this as:where we have added a new variable v to get a pair of coupled first orderequations.Second order equations ! x =r v v =r f (r x ,r v ,t)m" # $ $ % & ' ' ! •! • ! x =r f (r x ,x,t)m! ••! •University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 10Phase spaceConcatenate x and v to make a 6-vector: position in phase space.Taking the time derivative: another6-vector.A vanilla 1st-order differentialequation.! xv" # $ % & ' ! •! • ! r x r v " # $ % & ' ! xv" # $ % & ' =r v r f m" # $ % & ' ! •! •University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 11Differential equation solverApplying Euler’s method:Again, performs poorly for large Δt.And making substitutions:Writing this as an iteration, we have:Starting with: ! xv" # $ % & ' =r v r f m" # $ % & ' ! •! • ! r x (t + "t) =r x (t) + "t # x(t)! •! x(t + "t) = x(t) + "t # x(t)! •! •! •• ! r x (t + "t) =r x (t) + "t #r v (t)! • ! x(t + "t) = x(t) + "t #r f (r x ,x,t) m! •! • ! r x i+1=r x i+ "t #r v i ! r v i+1=r v i+ "t #r f imUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 12Particle structurem! "# $# $# $# $% &xvfpositionvelocityforce accumulatormassPosition in phase spaceHow do we represent a particle?University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 13Single particle solver interfacem! "# $# $# $# $% &xvf! "# $% &xv/m! "# $% &vf[ ]6getDimderivEvalgetStatesetStateUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 14Particle systemsparticles n timeIn general, we have a particle system consisting of n particles tobe managed over time: ! r x 1r v 1r f 1m1" # $ $ $ $ % & ' ' ' ' r x 2r v 2r f 2m2" # $ $ $ $ % & ' ' ' ' Kr x nr v nr f nmn" # $ $ $ $ % & ' ' ' 'University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 15Particle system solver interfacederivEvalget/setStategetDimFor n particles, the solver interface now looks like:particles n time ! 6nr x 1r v 1r x 2r v 2Kr x nr v nr v 1r f 1m1r v 2r f 2m2Kr v nr f nmnUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 16Particle system diff. eq. solverWe can solve the evolution of a particle system again using theEuler method: ! r x 1i+1r v 1i+1Mr x ni+1r v ni+1" # $ $ $ $ $ $ % & ' ' ' ' ' ' =r x 1ir v 1iMr x nir v ni" # $ $ $ $ $ $ % & ' ' ' ' ' ' + (tr v 1ir f 1im1Mr v nir f nimn" # $ $ $ $ $ $ % & ' ' ' ' ' 'University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 17ForcesEach particle can experience a force which sendsit on its merry way.Where do these forces come from? Someexamples:Constant (gravity)Position/time dependent (force fields)Velocity-dependent (drag)Combinations (Damped springs)How do we compute the net force on a particle?University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 18Particle systems with forcesparticlesn timeforcesF2FnfnfForce objects are black boxes that point to the particles they influenceand add in their contributions.We can now visualize the particle system with force
View Full Document
Unlocking...