Particle SystemsReadingWhat are particle systems?Particle in a flow fieldVector fieldsDiff eqs and integral curvesEuler’s methodParticle in a force fieldSecond order equationsPhase spaceDifferential equation solverParticle structureSingle particle solver interfaceParticle systemsParticle system solver interfaceParticle system diff. eq. solverForcesParticle systems with forcesGravity and viscous dragDamped springderivEvalBouncing off the wallsCollision DetectionNormal and tangential velocityCollision ResponseParticle frame of referenceThe OpenGL geometry pipelineProjection and modelview matricesRobot arm code, revisitedComputing particle launch pointNext lectureUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don FussellParticle SystemsUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 2ReadingRequired:Witkin, Particle System Dynamics, SIGGRAPH ’97 course notes on Physically Based Modeling.Witkin and Baraff, Differential Equation Basics, SIGGRAPH ’01 course notes on Physically Based Modeling.OptionalHocknew and Eastwood. Computer simulation using particles. Adam Hilger, New York, 1988.Gavin Miller. “The motion dynamics of snakes and worms.” Computer Graphics 22:169-178, 1988.University of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 3What are particle systems?A particle system is a collection of point masses that obeys some physical laws (e.g, gravity, heat convection, spring behaviors, …).Particle systems can be used to simulate all sorts of physical phenomena:University of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 4Particle in a flow fieldWe begin with a single particle with:Position, Velocity, Suppose the velocity is actually dictated by some driving function g:xg(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 Fall 2008 Don Fussell 5Vector fieldsAt any moment in time, the function g defines a vector field over x:How does our particle move through the vector field?University of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 6Diff eqs and integral curvesThe equation is actually a first order differential equation.We can solve for x through time by starting at an initial point and stepping along the vector field:This is called an initial value problem and the solution is called an integral curve.Start Here € x•= g(r x ,t)University of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 7Euler’s methodOne simple approach is to choose a time step, t, and take linear steps along 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 (more complicated) methods exist, e.g., “Runge-Kutta” and “implicit integration.” € 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 Fall 2008 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 and velocity 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 Fall 2008 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 order equations.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 Fall 2008 Don Fussell 10Phase spaceConcatenate x and v to make a 6-vector: position in phase space.Taking the time derivative: another 6-vector.A vanilla 1st-order differential equation.€ xv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥€ •€ • € r x r v ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ € xv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥=r v r f m ⎡ ⎣ ⎢ ⎤ ⎦ ⎥€ •€ •University of Texas at Austin CS384G - Computer Graphics Fall 2008 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 Fall 2008 Don Fussell 12Particle structurem⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦xvfpositionvelocityforce accumulatormassPosition in phase spaceHow do we represent a particle?University of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 13Single particle solver interfacem⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦xvf⎡ ⎤⎢ ⎥⎣ ⎦xv/m⎡ ⎤⎢ ⎥⎣ ⎦vf[ ]6getDimderivEvalgetStatesetStateUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 14Particle systemsparticlesn timeIn general, we have a particle system consisting of n particles to be 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 Fall 2008 Don Fussell 15Particle system solver interfacederivEvalget/setStategetDimFor n particles, the solver interface now looks like:particlesn 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 -
View Full Document
Unlocking...