Animations with Particles in Computer Graphics
Lets say we are asked to make an animation of throwing a basketball. How can we do?
- Option 1: Manual Animation
- Manually move the basketball according to a certain curve
- Doesn’t look realistic
- Manually move the basketball according to a certain curve
- Option 2: Physically Based Animation
- Numerically solve the governing equations to move the basketball
- New animations automatically look realistic
- Numerically solve the governing equations to move the basketball
Particles
- Moving mass points in 2D or 3D space
Particle Systems
- Simulation of many particles at once
- Particles can be:
- Independent
- Dependent (Interact with each other)
Particles
The
Particle
class is about each particle,and the
ParticleSystem
is about a collection of particles.
Each particle is described by:
- Position
- Velocity
- Accumulated force
- Mass
where is the time.
Given the Accumulated force and the mass, we want to find the position.
Forces
- Gravitational
- Viscous drag
- Spring force
In general, we cannot mathematically solve the equations of motion
We numerically estimate them using Time Discretization.
We cannot use continuous time on a computer
We consider discrete time instead
- where is called “time step”
Using Verlet Integration:
- Has less numerical issues comparing to Euler’s method
- Based on the central difference approximation
1 | newPosition = position + (position - prevPosition) + deltaT*deltaT*globalGravity; |
Collisions and constraints
Constraints:
- The things to restrict the motion of each particles
- e.g. Walls, obstacles, other particles etc.
- Collision against a wall
- Bead on a wire
- e.g. Walls, obstacles, other particles etc.
We can use Force-based or Position-based to solve the problem.
- Force-based constraints
- Exact solutions
- Sometimes difficult to apply
- In Implementation:
- Check if there is any collision
- then solve for constraint forces
- Position-based constraints
- Easy and general
- May not correspond to the real physics
- In Implementation:
- Check if there is any collision
- then remove collisions by moving points
Collision against a Wall
Force-based
General recipe:
- Reflect the velocity (i.e., adjust the force)
- Push the position to resolve the collision
- Reflect the velocity by the collision boundary (e.g., the wall surface)
Position-based
General recipe:
- Check if there is any collision
- Reflect the previous position
- Push both the current and previous positions to resolve the collision
Example: a wall at where is a constant
We dont want x pass through K that .
Visualization from.
in this case.
Check for collision:
condition: old position didnt pass through the wall and the new position pass through the wall
is the condition “old position didnt pass through the wall” necessary?
Collision response:
Update the old position with (new position - old position) and update new position with the value at wall
where .
means the attribute of the vector in code here
can be incorporated by scaling the distance
Bead on a wire
Force-based
Solve for constraint force
- Constraint on position
- Constraint on kinetic energy
Position-based
- Project the position back to the circle wire
where is the position of center, is the radius.
It is basically denominator is basically normalizing the thing.
Multi-body Dynamics
Interacting particles for more advanced effects
Collision Processing
Key aspect of any dynamics simulation
- Collision detection
- Collision response
Collision Detection
Detect if there is any interpenetration occurred
Lets consider two circle with center and
Collision can be detected if
1 | static bool collisionDetection(const Particle part_i, const Particle part_j, const float sphereRadius_i, const float sphereRadius_j){ |
Simple Pseudocode for simultaneous collisions:
1 | for some number of times { |
Note that checking all the combinations detections is costly.
There are some methods to make the detection efficient.
- Basically using acceleration data structure
Collision Response: Force-based
- New velocities based on laws of conservation
Energy Conservation does by definition
Collision Response: Position-based
- Just push circles away from each other lmao
Note that the overlap distance =
Then push each other
Energy Conservation in Position-based Response
- Modify the previous locations according to the conservation of energy
Gravitational fields
Newton’s law of gravity
where is the gravitational constant (Not )
Note that may become a very small value. Always add a small value to the distance.
1 | static float3 gravityField(const Particle part_i, const Particle part_j) { |
^Note that it really depends on how you gonna tweak the parameters.
Pseudocode of Basic implementation (Do this in each time step before time integration):
- Double loop over all the particles
- For each particle, add the gravitational force by all the others
- ^Repeat for all particles
- O(N^2) for N particles
1 | for all the particles i { |
My implementation:
1 | void step() { |