Collision detection ppt

collision detection avoidance ppt and Particle System Simulation
Dr.ShaneMatts Profile Pic
Dr.ShaneMatts,United States,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Comment
MIT EECS 6.837 Computer Graphics Implicit Integration Collision Detection Philippe Halsman: Dali Atomicus MIT EECS 6.837 – Matusik This image is in the public domain. Source: Wikimedia Commons. 1 Midterm th • Tuesday, October 16 2:30pm – 4:00pm • In class • Two-pages of notes (double sided) allowed 2 Plan • Implementing Particle Systems • Implicit Integration • Collision detection and response – Point-object and object-object detection – Only point-object response 3 ODEs and Numerical Integration • Given a function f(X,t) compute X(t) • Typically, initial value problems: – Given values X(t )=X 0 0 – Find values X(t) for t t 0 • We can use lots of standard tools 4 ODE: Path Through a Vector Field • X(t): path in multidimensional phase space “When we are at state X at time t, where will X be after an infinitely small Image by MIT OpenCourseWare. time interval dt ?” • f=d/dt X is a vector that sits at each point in phase space, pointing the direction. 5 Many Particles • We have N point masses – Let’s just stack all xs and vs in a big vector of length 6N i – F denotes the force on particle i i • When particles do not interact, F only depends on x and v . i i f gives d/dt X, remember 6 Implementation Notes • It pays off to abstract (as usual) – It’s easy to design your “Particle System” and “Time Stepper” to be unaware of each other • Basic idea – “Particle system” and “Time Stepper” communicate via floating-point vectors X and a function that computes f(X,t) • “Time Stepper” does not need to know anything else 7 Implementation Notes • Basic idea – “Particle System” tells “Time Stepper” how many dimensions (N) the phase space has – “Particle System” has a function to write its state to an N- vector of floating point numbers (and read state from it) – “Particle System” has a function that evaluates f(X,t), given a state vector X and time t – “Time Stepper” takes a “Particle System” as input and advances its state 8 Particle System Class class ParticleSystem virtual int getDimension() virtual setDimension(int n) virtual float getStatePositions() virtual setStatePositions(float positions) virtual float getStateVelocities() virtual setStateVelocities(float velocities) virtual float getForces(float positions, float velocities) virtual setMasses(float masses) virtual float getMasses() float m_currentState 9 Time Stepper Class class TimeStepper virtual takeStep(ParticleSystem ps, float h) 10 Forward Euler Implementation class ForwardEuler : TimeStepper void takeStep(ParticleSystem ps, float h) velocities = ps-getStateVelocities() positions = ps-getStatePositions() forces = ps-getForces(positions, velocities) masses = ps-getMasses() accelerations = forces / masses newPositions = positions + hvelocities newVelocities = velocities + haccelerations ps-setStatePositions(newPositions) ps-setStateVelocities(newVelocities) 11 Mid-Point Implementation class MidPoint : TimeStepper void takeStep(ParticleSystem ps, float h) velocities = ps-getStateVelocities() positions = ps-getStatePositions() forces = ps-getForces(positions, velocities) masses = ps-getMasses() accelerations = forces / masses midPositions = positions + 0.5hvelocities midVelocities = velocities + 0.5haccelerations midForces = ps-getForces(midPositions, midVelocities) midAccelerations = midForces / masses newPositions = positions + 0.5hmidVelocities newVelocities = velocities + 0.5hmidAccelerations ps-setStatePositions(newPositions) ps-setStateVelocities(newVelocities) 12 Particle System Simulation ps = new MassSpringSystem(particleCount, masses, springs, externalForces) stepper = new ForwardEuler() time = 0 while time 1000 stepper-takeStep(ps, 0.0001) time = time + 0.0001 // render 13 Particle System Simulation ps = new MassSpringSystem(particleCount, masses, springs, externalForces) stepper = new MidPoint() time = 0 while time 1000 stepper-takeStep(ps, 0.0001) time = time + 0.0001 // render 14 Computing Forces • When computing the forces, initialize the force vector to zero, then sum over all forces for each particle – Gravity is a constant acceleration – Springs connect two particles, affects both i – dv /dt = F (X, t) is the vector sum of all forces on particle i i nd i – For 2 order F =m a system, i i dx /dt is just the current v i i 15 Questions? Image removed due to copyright restrictions. 16 Euler Has a Speed Limit • h 1/k: oscillate. h 2/k: explode ’ Image removed due to copyright restrictions please see slide 5 on "Implicit Methods" from Online Siggraph '97 Course notes, available at http://www.cs.cmu.edu/baraff/sigcourse/. 17 From the SIGGRAPH PBM notes a f 1 Integrator Comparison a f 1 • Midpoint: f m – ½ Euler step – evaluate f m – full step using f m b • Trapezoid: – Euler step (a) – evaluate f 1 Image by MIT OpenCourseWare. – full step using f (b) 1 – average (a) and (b) • Better than Euler but still a speed limit 18 Midpoint Speed Limit • x’=-kx • First half Euler step: x =x-0.5 hkx = x(1-0.5 hk) m • Read derivative at x : f =-kx =-k(1-0.5 hk)x m m m • Apply derivative at origin: 2 2 x(t+h)=x+hf = x-hk(1-0.5hk)x =x(1-hk+0.5 h k ) m • Looks a lot like Taylor... • We want 0x(t+h)/x(t)1 2 2 -hk+0.5 h k 0 hk(-1+0.5 hk)0 For positive values of h & k = h 2/k • Twice the speed limit of Euler 19 Stiffness • In more complex systems, step size is limited by the largest k. – One stiff spring can ruin things for everyone else • Systems that have some big k values are called stiff systems. • In the general case, k values are eigenvalues of the local Jacobian From the siggraph PBM notes © David Baraff and Andrew Witkin. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/help/faq-fair-use/. 20

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.