Cameron Swords

Polyhedral Collisions

I've looked into several methods for polyhedral collision detection and utterly failed at attempted implementations. In addition, I have looked into several 3D engine that may include the features that we would like to see for these collision simulations.

GJK Algorithm

The Gilbert-Johnson-Keerthi Algorithm is a tolerably accurate algorithm for collision detection between polyhedra. It works by computing a Minkowski Difference and iterating along the difference to check if the difference contains the origin. Because of the nature of the difference, if it contains the origin, then there exists some $A$, a point in the first object, and $B$, a point in the second object, such that $A - B = 0$, which means $A = B$, which implies that the shapes overlap.

The basic algorithm is as follows:

Vector s = support(b1,b2,new Vector(1,0,0));
Simplex simplex = new Simplex(s);
Vector dir = s.scaleBy(-1.0);
do {
    Vector a = support(b1,b2,dir);
    if ( < 0) return false;
} while(!doSimplex(simplex,dir));
return true;

In the above code, the 'support' function takes two bodies and a direction vector and computes a new point in the Minkowski difference along the given direction. The 'doSimplex' function looks at the number of points in the simplex, determines which, if any, to remove, and ultimately computes a new direction vector for the support function to use. For more details, see the GJK Algorithm page of the wiki.

Open Dynamics Engine

The Open Dynamics Engine is a GPL-licensed physics engine that is supposed to perform polyhedral collisions among other things. While getting working polyhedral code together in the engine was relatively straight-forward, the basic integrator was unreliable and often produced numerical results due to divisions by zero during vector normalization. In the end, because of this serious flaw, simulations could not be pushed far enough to be scientifically worthwhile. For more details on the experimentation and performance of the engine, please see the Open Dynamics Engine page of the wiki.

Fortress Programming Language

I've also done basic research into the Fortress programming language. Preliminary notes include its similarity to Scala and the usefulness of implicitly parallel for loops. The current language implementation is slow, however.

Basic Particle Simulation

  • Completed a standard kick-step gravitation simulation
  • Particle-particle collisions fully implemented

Look here For implementation details.

MVS Implementation


  • Hamiltonian -> Jacobi coordinate conversion

To Complete

  • Acceleration Kick
  • Drift Step
  • Jacobi -> Hamiltonian coordinate conversion


Dr. Lewis recently modified his Gravity-Collision Tree to optionally build a collision lock graph (as opposed to the standard lock grid method). After discussion, he implemented it. I am currently running timing tests to examine if there is any speed increase as a result of the new code. For more details, see the Lock-Graph Testing page.


Distribution Difference Filter

I spent some time (a day or so) implementing a Distribution Difference Filter; the filter takes two distributions and removes one from the other. It also supports different methods of scaling the distribution that is being subtracted.