Few things in game development are as conceptually difficult or annoying to debug as a physics engine. Building a physics engine from scratch was one of the biggest challenges I have ever faced. There are a lot of factors that need to be taken into account: forces, torques, integration, numerical stability, deterministic behavior, mass and inertia, object representation, spaces, orientation, collisions detection, penetration, impulses, dampening and stabilization, contact discovery, contact caching, collision graphs, sleeping, resting contact, rolling, sliding, friction, constraint solving… *takes a deep breath*… the list keeps on going. The even bigger problem is that finding out where to start or what to do next is like trying to find Atlantis underneath Mount Everest; it’s takes a lot of time and focus.

Having said that, I was able to persevere through a lot of the gory details (with the help of my Professor Erik Mohrmann) and the result was a mini physics engine. This implementation features constraint solving taken from Erin Catto’s thesis paper, as well as the other bunch of expected features in a physics engine. Overall I must admit, at the end of the project I was not at all happy with my physics engine, but having said that I know a lot more than I did and know exactly what I would change or do differently next time. Here’s a few videos taken from the engine while it was in development.

The below demo shows off the Minkowski Portal Refinement algorithm. To give everyone a brief overview… lets start with the basics. Imagine I wanted to see if a convex polyhedra (lets call it A) contained a point or not. We could make an infinite half plane with every face, and see if the point is inside each half plane… but that could get ugly for convex shapes with large amounts of faces. Would you buy the argument that if another convex shape, B, is inside the original convex shape A, and the point is inside B, then it is necessarily inside A? Given that’s the case, what if we could find a smaller shape inside A that contains the point, instead of testing with every face? That’s a good portion of MPR.

The second mind trip comes primarily from computational geometry and Minkowski spaces, but I’ll see if I can’t sum it up. Imagine you had two shapes J and K, and somehow you subtracted every single point in J from every single point in K. One interesting thing that would come up is that if the shapes were colliding, then necessarily the zero vector would show up in the subtraction (because the two shapes would have at least one point in common, thus that point minus itself is zero!). Furthermore, we introduced a new operation called the Minkowski Difference, which is essentially the subtraction I described above, however, it turns out that we don’t actually need to subtract all the points from each other (this would be prohibitively expensive). Instead, what we can do is attempt to combine what we talked about above with the Minkowski Difference operation, and attempt to find the zero vector! This step is a little more complicated than I’m making it out to be, but that is the gist of the algorithm (actually what I covered is more like GJK, but MPR is a subset of GJK). From that point, when you find the origin, it turns out you can also find the penetration depth and contact normals.

For anyone that wants to see an implementation or code sample, here it is: MPR