Collision

So my first program was a color line that moved across screen with a beep as it hit the top. Instant haxxor.

There are two parts of collision detection, the first is to detect if something is not colliding and the second is to detect if something is colliding. Generally speaking the second part is slow and takes many calculations. By finding objects that do not interact as soon as possible in the physics system it need to do less hard work later. They are called broad phase and narrow phase.

Broad phase

The focus of this phase is to get a list of all the objects that have no possibility of colliding in the next simulation update.

Brute force

This is the no broad phase at all option. Loop all objects and check them against each other and if they collide do something. Works for few objects and if the test is really simple.

for(i=0; i<numObjects-1; i++)

{

for(j=i+1; i<numObjects; i++)

{

collideInfo info = collides(obj[i], obj[j])

if(info.didcollide)

response(obj[i], obj[j],info)

}

Spatial Partitioning

Split the world into smaller areas based on some rule. Ex are quadtrees, octrees, bsp trees or any sort of tree really. Insert the object into any cells that it's axis aligned bounding box touch. Build a list of object pairs that occupy the same cells as they need to be tested against each other. Next frame rebuild the data.

Sweep and Prune

- GPG 1: p228-238

Narrow phase

Here the focus is on is object A colliding with object B and if so how to we get all the information we need about the collision. What happens when the object's that collides does not matter here, thats the response part of the collision.

Reference

Physics for Game Programmers : Robust Contact Creation for Physics Simulation - 2015

Automatic avoidance for player characters on an indie budget - 2014

Physics for Game Programmers - 2013

Convex Hull Generation - 2013

Collision Detection Using the Separating Axis Theorem - 2012

Collision detection for dummies - 2011

Contact Points Using Clipping - 2011

Speculative Contacts – a continuous collision engine approach - 2011

EPA (Expanding Polytope Algorithm) - 2010

GJK – Distance & Closest Points - 2010

GJK (Gilbert–Johnson–Keerthi) - 2010