Physics‎ > ‎

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
SAT (Separating Axis Theorem) - 2010
Testing if a point is inside a Polygon - 2010
Sweep and prune - 2007
igCollision  - 2007
Supporting Cylinder Collision - 2007
Robust Continuous Collision Detection - 2005
BSP Collision Detection As Used In MDK2 and NeverWinter Nights - 2001
When Two Hearts Collide: Axis-Aligned Bounding Boxes - 2000
General Collision Detection for Games Using Ellipsoids  - 2000
Advanced Collision Detection Techniques - 2000
Crashing into the New Year: Collision Detection - 2000
Collision Detection: Alogrithms and applications
I–COLLIDE: an Interactive and Exact Collision Detection System for Large Scale Environments
N tutorial A - Basic Collision Detection and Response
N tutorial B - Grid-Based Collision Detection and Raycasting
Simple Intersection Tests For Games
Object/Object Intersection
Collision detection - 2015 Overview , Box intersection and Benchmarks
Comments