May 25, 2011
May 25, 2011
Particle System Dynamics
By: Andrew Witkin
Particles are objects that have mass, position and velocity, and respond to forces, but no spatial extent.
Phase Space
It is a second order equation, a second time derivative is taken. (Unlike in the previous chapter)
Best Particle Systems
We want two views of the model
From outside the model should look like a monolith (a point in high dimensional space)
From within the model should be structured (collection of distinct interacting objects.
It involves two main parts – the particles and the entities that apply forces to particles.
Structure of a particle for C:
Typdef struct{
Float m; //mass
Float *x; // position vector
Float *v; // velcotiy vector
Float *f; // force accumulator
}*Particle
Then in order to be represented in a coherent way
Typdef struct{
Particle *p; //array of pointers to particles
Int n; //number of particles
Float t; //simulation clock
}*ParticleSystem;
Forces
The particle system maintains a list of force objects, each has access to any / all particles and has code to apply its own forces.
Can be grouped into 3 categories
1. Unary forces, such as gravity and drag – act independently on each particle.
2. N-ary foces(springs) apply forces to a fixed set of particles
3. Forces of spatial interaction (attraction and repulsion), act on any / all pairs of particles depending on positions.
Each can be implemented differently.
Unary forces
Gravity – trivial to implement. Gravity can be implemented into the system rather than a distinct object.
Viscous Drag
Has the form f = -kv, where k is the coefficient of drag. Particle gradually comes to rest. Good to have at least a little drag applied to each particle. (can also be a part of the system rather than a distinct object)
n-ary forces
binary force is Hooks law spring.
Equal and opposite forces act on each particle.
In object oriented, would have a function where 1 fetches positions and velocities from the two particle structures, performs its calculations, and sums the results into the particles force accumulators.
Spatial Interaction Forces
Spatial interaction forces may act on any pair of particles. Approx models for fluid behavior, and large scale particle simulations are also used in physics.
User Interaction
Controlled particles
Particles whose motion is procedurally controlled (like moving in a circle) can provide dynamic elements like motors.
Velocities and positions of controlled particles must be maintained at their correct values – if not the forces such as spring forces will behave incorrectly.
Structures
Beams, blocks, etc. can be made out of masses and springs.
Energy Functions
Force laws, such as position, velocity, and time dependent formulae are not laws of physics. They are things we design to hold things in a desired configuration.
Detection
There are two parts to collisions: detecting and responding to the detections. After an ODE step collision is detected, the correct thing to do is to roll back the whole system to the time of the instant of contact. Easier, but less accurate, account is to just displace the point when it collides.
Response
Partition velocity and force vectors into 2 orthogonal components: one normal to the collision surface, the second parallel to it. Simplest collision to consider is elastic without friction.
May 25, 2011
Differential Equation Basics
By: Witkin and Baraff
Ordinary Differential Equations (ODE)
ẋ = f(x,t)
X describes the motion of point p on a plane.
Derivative ẋ depends on time in 2 ways:
1. Derivative vectors wiggle.
2. Point p sees different vectors at different times.
Numerical Methods
Starts with symbolic solutions -> function form needs to be guessed.
ẋ = -kx is satisfied by x = e^kt
Numerical -> discrete time steps relative to x. (initial value is x(t_0))
Bigger the time step, bigger the error.
Euler’s Method
x(t_0 + h) = x_0 + hx(t_0)
Euler’s method is not very accurate.
It can also be unstable and isn’t efficient.
To improve Euler’s method, look at the Taylor series. Only the first two terms are really used so the error is O(h^2)
Midpoint Method
Takes an Euler step, but then goes further -> performs a second derivative evaluation at the midpoint. (Second evaluation is used to calculate the step)
Runge Kuta is order 4, the error is O(h^5)
Adaptive Step Sizes
See how large of a step can be taken and still be within a certain error.
Implementation
Want to write ODE solvers so you can change them easily, the code then becomes reusable.
Should be able to handle:
-Solver must know length to allocate storage, perform vector arithmetic, etc
-Set / Get x and t. Needs to be able to install new values at the end of a step. And sets intermediate values during the operation.
-Evaluate fat current x and t
