# 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.

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

Convex Hull Generation - 2013

Sweep and prune - 2007

igCollision - 2007

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

Intersection routines Resources Page

Collision Detection and Spatial Indexes - 2012

http://howlingmoonsoftware.com/wordpress/collision-detection-and-spatial-indexes/