GitHub repo can be found here: https://github.com/Nightmask3/Physics-Framework

I had to make a physics engine for one of my classes at DigiPen (CS550 – Physics Simulations).

The requirements of this physics engine were:

1) Have a broadphase collision detection implementation
2) Have a method of resolving collision
3) Must use three dimensional rigid body physics

Overview

The engine uses an Entity-Component system that communicates using an Observer pattern.

A good primer on the observer pattern can be found here: http://gameprogrammingpatterns.com/observer.html

Everything in the engine that wishes to listen to events, must inherit from the interface/abstract base class Observer.

A code snippet of the Observer:Everything that wants to send events must own a Subject for that event:

Subjects can have lists of Observers who subscribe and listen for events to fire in the future, as well as send one-time “fire and forget” events to Objects as well.
This allows for event-driven communication between Observers and Objects (which most things in the engine are).

All the managers in the engine derive from Observer, allowing for them to listen to events from GameObjects, the Engine, components etc.

The component hierarchy is fairly typical:

Integration:

By default, the engine uses a semi-implicit Euler integration method. RK-4 was implemented, but never required to be used. Same goes for a Verlet integrator that was also implemented.

There are some caveats to integration, such as where colliders that are marked as ‘Static’ are not integrated. This is an issue of poor component design where I require objects that don’t really need physics (namely static objects) to still own one as they contain some data that is necessary for collision detection.

An improvement to this would be to decouple the Collider and Physics components dependencies so that a Collider could function without a Physics component also belonging to the owner.

Collision Detection:

The Gilbert-Johnson-Keerthi (GJK) algorithm is used to provide a Boolean check of whether the two convex shapes that are being tested are intersecting. The strength of GJK is that it can be manipulated completely based on the type of support function (or) support map being used.

Originally, I was using the naïve method of looping through all vertices and getting the dot product of each vertex against the search direction and finding the vertex furthest along that direction. However, for a shape with the spatial symmetry about all three axes (i.e. a cube or a sphere) it is possible to use another method involving an ‘Extents’ approach, which just multiplies the sign of the search direction against the half size of the cube (or the radius of the sphere). In this engine I have only implemented cubes, so this method proved sufficient.

EPA:

If/when GJK finds a simplex that encloses the origin, it passes the simplex onto EPA which attempts to locate the closest point possible to the origin in the Minkowski space, which should give the contact point, in theory.

In practice, due to the limitations of 32-bit floating point precision and math, EPA is very prone to numerical error, and as Dirk Gregorious as stated on various forums, is a method he does not personally like. I began to see why when I encountered some situations whose blame falls squarely on the imprecision of EPA and its inability to return a consistent contact point or one that can be guaranteed to be close to the center of mass.

It’s my belief that persistent manifolds in fact are a way to make up for the imprecision introduced by EPA into the resolution process, though also the issue of error in impulse solvers exacerbates this.

When EPA returns a point that is within a tolerable limit of the origin, the contact point is extrapolated using barycentric projection. There is an iteration limit of 50 to prevent the EPA from cycling infinitely.

Collision Resolution:

The contact that is generated by EPA is registered using a contact/collision constraint.

This constraint is solved using a method given by Erin Catto in his paper “Iterative Dynamics using Temporal Coherence”. It involves a sequential impulse method that comes down to a linear complementarity problem that must be solved using a numerical solver of some type.

The type of solver used in the paper and here is a projected Gauss-Siedel solver, which is shown to converge faster for this use-case than the Jacobi-Hamilton solver.

The solver performs velocity correction to ensure the velocity-level constraint is satisfied and objects will no longer move into each other, and the penetration is resolved using a Baumgarte stabilization method, which massages the constraint forces to get them to do “virtual work”.

There is also a slop term that is provided on the Baumgarte stabilization to allow objects to penetrate a bit before we apply the Baumgarte term.

Issues:

Lack of persistent manifolds and numerical issues with GJK and EPA mean that there are still some penetrations that can happen in some situations.

Additionally the issue of jitter can cause penetrations to happen. I plan on continuing with the implementation of this engine at least until I can obtain stable stacking, just to teach myself as well as to have that on my portfolio.

Conclusion:

I am pretty satisfied with the final state of my engine. It’s far from perfect, but considering that last year I spent upwards of three months trying to implement OBBs using SAT and I failed utterly, the fact that I managed to implement a working engine with detection and response is honestly enough for me.