RIGID BODY COLLISION SIMULATION WITH GJK AND EPA AND SEQUENTIAL IMPULSES AND CONTACT CONSTRAINT SOLVER

BACKGROUND

I use my DirectX 11 framework as my base engine to start this project. I modified the time step to fix time step which will run more than 60 times of physics interaction in 60 FPS. I use Semi-Implicit Euler Method to compute linear and angular velocity. The simulation took inertia tensor (Solid Cuboid) for torque. And all objects have one Cuboid in Rigid-body

BROAD PHASE

The Broad Phase is the first step of the collision detection to simply detect Axis-Aligned Bounding Box (AABB) between two objects. I use Dynamic Bounding Volume Hierarchies (BVH), a binary tree depended on Surface Area Heuristic. In the beginning, I build complete BVH first and re-insert the moving object. Using Enlarge AABB can reduce the number of BVH refresh time. The Green boxes are leaves in BVH.

NARROW PHASE

After the Broad Phase, the Narrow Phase will detect collision in detail. I use Gilbert–Johnson–Keerthi (GJK) for collision check on two Oriented Bounding Boxes (OBB). After two objects have collided, I use Expanding Polytope Algorithm (EPA) to find the contact points with the shortest penetrating distance. The image shows the EPA.

COLLISION RESOLUTION

After creating contact info, I use an incremental contact manifold method to create contact manifold, a list of contacts (max 4 for good stability). I use Sequential impulses and contact constraints to solve the Collision Resolution by given contact manifolds. The image show contact manifold and stacking without penetration.