Boundary Conditions for Particle Systems

CS 493/693 Lecture, Dr. Lawlor

Making particles bounce off a boundary is a surprisingly subtle problem. The inherent difficulty is that boundaries are discontinuities, where a particle falling at 1g in gravity suddenly smacks into the floor, which can easily push back with hundreds or thousands of gravities of accelleration. Because our timestep is designed to work at 1g, not 100g, and certainly not for timesteps with half of one and then half of the other, it's pretty difficult to track the actual forces involved in the collision process with any reasonable efficiency.

But it's easy to fake something close that usually works by just:

Detect that you've crossed into bad territory.
Flip the velocity so you'll tend to leave the bad area.

A typical implementation looks like:

	if (particle.pos.z<0.0) { /* we're underground! */
		particle.vel.z=-0.7*particle.vel.z; /* semi-elastic bounce */
	}

The constant 0.7 is the elasticity of the collision:

0.0 means the particles land on the floor, splat, and stick. Like toast, or wet clay.
0.3-0.7 or so gives a reasonable bounce, eventually decaying to zero. Most objects fall in this range.
1.0 means the particles rebound to their exact starting height, like perfect ball bearings.
2.0 means the particles rebound higher with each bounce, like flubber.

There are several things that go wrong with this, however--the worst is that particles often get "stuck" on the boundary, since flipping the velocity only tends to make them leave if the initial velocity was high enough (and pointing in the direction you expected). If the particle was already leaving, flipping the velocity just makes the problem worse in the next timestep.

So a reasonable modification is to push the particle out of the ground, in addition to modifying the velocity:

	if (particle.pos.z<0.0) { /* we're underground! */
		particle.vel.z=-0.7*particle.vel.z; /* semi-elastic bounce */
		particle.pos.z=0.0; /* push particle out of the ground */
	}

This works, but note that we're adding energy to the system by doing this. With a large enough timestep, this can cause particles to bounce out of control, but with a reasonable timestep, the overall motion is pretty good. If you're concerned about this energy addition, the right answer is to solve for the sub-timestep moment when particle.pos.z=0, take a sub-timestep in velocity to that instant, flip the velocity, and then finish out the timestep.

However, there is still a "jitter" problem with particles that should be sitting stationary on the floor:

In even timesteps, gravity pulls the particle down, and the particle falls below the floor. The code above pushes it back up to z=0, which is fine. But the velocity is flipped around to be small and positive.
In odd timesteps, the positive velocity actually pulls the particle a tiny distance up off the floor.

This can matter if you're taking large timesteps, or keeping a close eye on things on the floor. The fix is to penalize the positive velocity we give to the particle, something like:

		particle.vel.z=-0.7*particle.vel.z-0.2;

Precisely, we want to cancel out the velocity from a few steps' accelleration due to gravity, so the 0.2 above should be 2*dt*gravity_accelleration. This means particles sitting on the floor will always have a small negative velocity, but that's OK because we reset the position every step.

More generally problems at the boundary conditions, like most discontinuities, can almost always be resolved by one of the following:

Shrinking the timestep (dt) until the discontinuity doesn't matter. This uses up CPU time.
Using some elegant mathematics to determine the exact answer. This can take serious thought.
Slapping in a fudge factor to kill off the bad behavior. This often only works for a particular range of parameters, and can be tricky to create.

Curved Boundaries

Curved boundaries are reasonably easy to model--the "inside boundary" check becomes a distance-from-surface computation (for a sphere, a radius computation), and the velocity bounce is implemented as a reflection about the surface normal. The GLSL "reflect" function is quite handy for this--if your vector library doesn't have "reflect" already, definitely add it!

vec3 reflect(vec3 I,vec3 N)   {return I-2.0*dot(N,I)*N;}
...
	particle.vel=0.7*reflect(particle.vel,normalize(surface_normal));

Multiple Boundaries

It can become exceedingly difficult to push particles out of a sharp corner between two boundaries. Often pushing the particle outside boundary A just pushes it deeper into boundary B, and vice versa. Many commercial computer games allow the player to become irrevokably wedged into boulders or other randomly oriented geometry, so the problem isn't easy to solve in general.

One simple fix is to resolve the "fix A, or B?" boundary question by adding a third boundary C, to push the particle away from problematic corners. Often simulated worlds have many invisible collision-only geometry "blockers", if only to keep the viewers corralled inside the good looking area of the world.