Constrained Particle Sim (Baraff and Witkin)

Class	Instructor	Date	Language	Ta'ed	Code
CS 4496 Computer Animation	Karen Liu	Spring 2013	C++	No	Github Repo
CS 4496 Computer Animation	Karen Liu	Spring 2015	C++	Yes	Code N/A
CS 4496 Computer Animation	Karen Liu	Spring 2016	C++	Yes	Code N/A
CS 7496 Graduate Computer Animation	Karen Liu	Fall 2016	C++	Yes	Code N/A

This project implemented a particle simulator using many of the mechanisms and architecture suggested in the Baraff and Witkin SIGGRAPH class from the late 90's. I implemented numerous integrators - Forward Euler, Implicit Euler, Semi-Implicit Euler, RK3, RK4, Verlet - all accessible for each individual particle via function pointers so I could compare their performance on a particle-by-particle basis. I implemented numerous forces - gravity, particle-particle attraction/repulsion, damped spring forces - and collisions - particle-particle, particle-sphere collider, particle-planar collider, with and without friction. I also implemented both positional (to make a simple cloth that responded to collisions) and force constraints, as well as a Conjugate Gradient solver to build a mass-spring system with many particles solved with an implicit integrator. I also added a 3D euler-grid based fluid solver to provide environmental effects for certain simulations, like the "seaweed" sim below.

The simulator itself consists of numerous simulation windows, each with a different base configuration. An essential component of this simulator, for me, was to be able to actively configure the environment, like adding new particles and constraints on the fly. Both particle-to-particle constraints and fixed circular constraints can be drawn by the user while the simulation is in progress. The user can also click-drag on the screen to add a force to the particles, or to the environmental fluid, if the particular sim window has such a fluid. This is also demonstrated below.

Below are some videos of the particle sim in action (with links if the videos don't play automatically) :

Comparison of Integrators in Freefall Sim.

These sets of falling particles are intended to illustrate the error inherent in the various approximation-based integrators that I implemented. The first particle on the left is solving the solution analytically (freefall with V0 = 0 and constant gravitational acceleration) and therefore serves as a ground truth. The integrators used for each of the subsequent particles are : Explicit(Forward) Euler, Midpoint Method, RK3, RK4, Implicity Euler, Trapezoidal Rule, Verlet, Generalized RK4.

A few interesting observations :

At the end of the clip I add a force to all the particles (except the ground truth), by dragging from left to right across the screen.
The RK3, RK4 and Generalized RK4 are all effectively the same in this simulation, since their errors are all of a higher order (in power of timestep) than the function describing the motion.
Since the Verlet integrator I implemented doesn't consider the velocity at each time step, and since I handle collisions with planar colliders by reflecting the velocity vector of the particle across the normal of the collider (scaled by some constant (0,1] representing collider elasticity), the collision is not handled correctly and the particle falls through the ground.

Comparison of Integrators in a constrained system.

A compensating force is derived to keep the particles following the circular constraint path. The ground truth implementation only solves for gravitational force and so does not follow the circular constraint, but otherwise the integrators are the same as those listed above, from top to bottom, Left Column : Ground Truth, Explicit(Forward) Euler, Midpoint Method; Middle Column : RK3, RK4, Implicity Euler; Right Column : Trapezoidal Rule, Verlet, Generalized RK4.

Note the compounding error in the forward methods (Forward Euler, Midpoint Method) causing them to explode.

Circular Constrained Particle.

Note the particles being added, as well as both a fixed-center constraint and a particle-to-particle constraint, via user input. This sim uses an RK4 integrator on all particles.

Newton's Cradle.

Again particles and constraints are added when the sim is paused (the jump in the middle of the clip is due splicing two screen caps with a few seconds dropped in the middle).

"Roller Coaster"

With this simulation, I have the various particles possibly jump constraints where the constraint paths touch, based on the direction of the applied force on the particle when it reaches the contact point. As the clip runs I apply various forces to the system via mouse-drags, and particles can be seen to jump between various constraints accordingly.

"Seaweed" Sim

In this sim, each vertical construct consists of particles and constraints between them to maintain their distance. Furthermore, "torques" are applied at each particle to attempt to keep the next particle directly above it (this started as an inverted pendulum experiment). Lastly, I put a 3D Euler-grid fluid in this sim, and instead of the click-drag input modifying the force on the particles directly, it modifies the force in the fluid, which in turn applies forces to each particle.