Last Updated October 16, 2013

Collision detection

References:

van den Bergen, G. Collision Detection in interactive 3D environments. Morgan Kaufmann, 2004. Ch.5

Watt, A. & Policarpo, F. 3D Games Realtime Rendering, Vol 1. Addison-wesley, 2001. Ch.15.

BSP tree FAQ

Ming C. Lin and John F. Canny. A fast algorithm for incremental distance calculation. IEEE/International Conference on Robotics and Automation "ICRA", April 1991.

Melax, Stan. BSP Collision Detection As Used In MDK2 and NeverWinter Nights. Gamasutra.com

Ostgard, N. Quake 3 BSP Collision Detection. Devmaster.net

Introduction

Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other physical simulations, it also has applications in robotics. In addition to determining whether two objects have collided, collision detection systems may also calculatetime of impact (TOI), and report a contact manifold (the set of intersecting points).[1] Collision response deals with simulating what happens when a collision is detected (see physics engine, ragdoll physics). Solving collision detection problems requires extensive use of concepts from linear algebra and computational geometry.

Collision detection has two main applications

• detecting collision between objects
• path planning

A generalised collision detection involves computing the interaction of N independent objects (requiring N²) interactions. Most applications deal with only one or a few moving objects in an otherwise static scene.

Consider 2 objects (say, racing cars) each composed of 1000 faces, testing each pair of faces in this situation would require;

(N²-N)/2 = 999,000/2~=450,000 intersection tests

Consider a race with 20 cars, there are 190 pairs of cars in this situation each pair needs 450,000 tests, giving a total of 85 million intersection tests each frame or or 4,250,000,000 every second at 50fps.

Collision detection is a general term, which can be applied to the following problems;

1. detecting if two objects collide
2. calculating the point of contact between two objects

A posteriori versus a priori

In the a posteriori case, we advance the physical simulation by a small time step, then check if any objects are intersecting, or are somehow so close to each other that we deem them to be intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are somehow "fixed" to account for the collision. We say that this method is a posteriori because we typically miss the actual instant of collision, and only catch the collision after it has actually happened.

In the a priori methods, we write a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. We call this a priori because we calculate the instants of collision before we update the configuration of the physical bodies.

The main benefits of the a posteriori methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the a posteriori algorithms are in effect one dimension simpler than the a priori algorithms. Indeed, an a priori algorithm must deal with the time variable, which is absent from the a posteriori problem.

On the other hand, a posteriori algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected.

The benefits of the a priori algorithms are increased fidelity and stability. It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution.

Some objects are in resting contact, that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (a posteriori) or slide (a priori) and their relative motion is below a threshold, friction becomes stiction and both objects are arranged in the same branch of the scene graph.

Collision detection Approaches

There are two approaches to solving this problem;

1. Broad phase/Narrow phase:
   • The broad phase culls away pairs of objects which cannot possibly collide, either because of game rules, or because they are found to be separated
   • The narrow phase uses expensive geometry to determine accurate collision detection

2. Single Phase methods
   • proximity and contact points are computed using a single phase

Collision detection is a similar process to view frustum culling. Visibility testing is basically testing if an object 'collides' with the view volume. Because of this similarity, BSP trees have proved to be a useful approach to collision detection.

The most common technique for of collision detection is a broad phase strategy using bounding volumes to determine if objects can potentially collide; if the bounding boxes do not intersect, then the objects could not possibly collide. Intersecting between bounding volumes is a much cheaper than testing every face of a pair of objects.

An important trade-off when performing bounding volume testing is that of "bounding efficiencies", the amount of space inside the bounding box but outside the object. The simplest bounding volumes , with respect to intersection tests are a sphere and an axis aligned bounding box (AABB). Both of these usually have poor bounding efficiency due to the fact that they do not align themselves to the object at hand. More complex bound volumes are possible, but with the added cost of more complex intersection test.

Bounding volumes can be layered, so that an intersection with a simple bounding box (e.g. sphere) would lead to an intersection test with a more bounding efficient volume, which would lead to actual face intersection tests.

Broad phase/Narrow phase strategies are popular because the choice of algorithm for each method is independent.

Broad phase Strategies

Temporal Coherence

In most applications, collision are rare with respect to the frame rate, so performing test on every pair of objects, every frame is wasteful.

One method of exploiting temporal coherence is with 4-dimensional bounding volumes. Consider an stationary object with maximum acceleration a_max. At any future time $t$ it's position must be within the radius $a_{max}\frac{t^{2}}{2}+\vec{v}t$

If the particle is moving with velocity $\vec{v}$ and a starting position $\vec{s}$ then its position lies within $\vec{a_{max}}\frac{t^{2}}{2}$ of the point $\vec{s}+\vec{v}t$.

$|a_{max}|\frac{t^{2}}{2}+\vec{v}t+\vec{s}$

This expression traces a parabolic horn through 4-dimensional space. For simplicity, a 4D bounding trapezoid can be used to bound this volume.

Pairs of object's bounding volumes are tested for earliest possible time of intersection. This occurs when their 4D bounding boxes intersect. No further tests are mad until this intersection time is reached, at which point a more accurate test is performed and the space-time envelope is recomputed.

If the game rules specify a fixed path for an object, an even simpler bounding volume can be used.

Spatial Coherence

Octrees can be used for collision detection. the tree is descended until a region with two or more object is encountered. These objects are subject to a more accurate test.

The objects are moving, so the octree must be updated at each timestep.

Video describing the code needed for an Octree collision detection system

Bounding Boxes

A bounding box is a primitive shape that encloses the model and should have the following properties;

1. The box should fit the object as tightly as possible (high "bounding efficiencies").
2. Overlap tests for bounding boxes should be inexpensive.
3. The bounding box should be representable using a small mount of storage.
4. If the bounding box is to be re- computed regularly, the the cost of computing should be small

The use of bounding boxes is extremely common. The 4 common types of bounding boxes are;

1. Spheres; no need to update as object moves/rotates. Calculated as a radius from the "center", efficiency is low for long objects. Stored as 4 scalars, invariant under rotation
2. AABB (axis aligned bounding boxes), these need to be updated as the object moves. If a rotation is involved, the update can be relatively costly. The box can be made big enough to house all possible rotations. Stored as 6 scalars. Intersection tests are very quick.
3. OBB (oriented bounding boxes) the smallest box which will accommodate the object. These are costly to compute, but this can be done off-line. Any transformations applied to the underlying object can be applied to the box. Typically have the highest bounding efficiency of the commonly used bounding boxes. Testing for intersections is time consuming.
4. DOP (Discrete Orientation polytope). A generalisation of the AABB. Constructed by taking a number of suitably oriented planes at infinity and moving them until they collide with the object. The DOP is then the convex polytope resulting from intersection of the half-spaces bounded by the planes. Popular choices are the beveled bounding box, made from 10 (if beveled only on vertical edges), 18 (if beveled on all edges), or 26 planes (if beveled on all edges and corners). A DOP constructed from k planes is called a k-DOP. Intersection tests can be costly. Stored as 2k scalars

Bounding volume hierarchy

A bounding volume hierarchy captures geometric coherence in a model. This is a tree which stores objects in the leaves, each node contains a bounding volume which encloses all the objects in its sub trees. Intersection queries can be quick as branches are rapidly culled as per normal tree searches.

Constructing a bounding volume hierarchy can be expensive and maintaining it dynamically is costly, so are used for rigid models.

The procedure for testing for intersections between two bounding volume trees is;

 

Intersect( nodeA, nodeB){
	if nodeA.volume does not intersect nodeB.volume 
		return false
	
	if both nodes are leaves // no children
			//InstesersectPrimitive examines pairwise
			//exact collisoion detection
			return IntersectPrimitive(nodeA, nodeB)
	
	if both nodes are not leaves  (have children){
		if NodeA.volume > nodeB.volume 
			swap nodes //code beow assumes nodeA is smaller
			
		//compare the node with the smaller volume with the children of the node
		//with the larger volume
		foreach(childnode in nodeB)// iterate through B's child nodes
			Intersect(nodeA, childnode)
	}	
	else{ // one node is a leaf the other is a parent (has children)
		if nodeA is a leaf{
			leafnode= nodeA
			parentnode=nodeB;
		}
		else{
			leafnode= nodeB
			parentnode=nodeA;
		}
			
		foreach(childnode in parentNode)// iterate through all the  child nodes
			Intersect(leafnode, childnode)
	}

}		

Constructing an AABB tree

A typical AABB tree is a binary tree. At each step, the smallest bounding box of the set of primitives is computed and the set of primitives is split by a well chosen partitioning plane. The two resulting subsets are the processed recursively.

The partitioning plane is selected as a plane orthogonal to the longest axis of the bounding box for the set. This ensures that the bounding boxes are "fat" (cube-like) , which is a more efficient shape. It turns out that the best strategy for choosing the partitioning plane is halfway along the bounding box. The objects are then classified as belonging to the negative (left) or positive(right) half space. Objects that intersect the half space are classified depending on their mid-point.

Overlap checking with AABBs

Intersection checking between two AABBs involves checking for an overlap in all axis. We can do this be considering the projection of the centre of each of the AABB and measureing the distance between. If the distance is less than the sum of half-widths then there is overlap.

Separating axis theorem

The separating axis theorem(SAT) says that if two convex objects are not penetrating, there exists an axis for which the projection of the objects will not overlap. The SAT is used to quickly check for collisions between object aligned bounding boxes, DOPs and any convex polyhedra.

This procedure is a generalisation of finding overlapping AABBs

A good description of SAT with flash demos is here

This page has actual code to perform SAT

A full mathematical explanation of the mechanisim is given by David Eberly.

For two OBBs we create candidadate axes. These will be the 'local' axes of each object. The vertices of each object is projected onto an axis. The porection sof each object are checked if there is an overlap. The OBB collide if and only if there is no overlap on any axis.

In general, the separating axis theorem can be used to test collisions between any two convex polygons(2D).

SAT with 3D polyhedra

See this gamedev.stackexchage.com answer

In this case, the candidate axes will be the normals of all the edges. In the 3D case we need to chech for edge-edge collision. In order to see if there is a separation between two edges we need to project on to the axis formed by the cross product of each pair of edges.

Imagine two cubes which are almost but not quite touching edge-on-edge. the two edges from a plane seraration the two objects. The only way to see this 'gap' in a projection is to project onto the axis at right angles to the plane, this axis will be the cross product of the two edges.

For two cubes this means checking an axis for each (unique) face-normal of each cube (3x2) plus the axes formed by the cross product of the edges of A with the edges of B (3x3=9). Total candidate axes are 15.

For more complex polyhedra the number of candidate axes rise quickly.

how many axes are needed for two tetrahedrons? answer in tooltip

Minimum translation vector (MTV)

If two objects are found to be intersecting, it is often required that the objects moved so they are separated as part of the collision response.  SAT can return a Minimum Translation Vector (MTV). The MTV is the minimum magnitude vector used to push the shapes out of the collision. 

The direction of the MTV is found by finding the axis with the smallest overlap. The length of the MTV is the amount of overlap.

Narrow Phase Collision Detection

Exact Collision Between Pairs of Convex or Concave Polygons (in 2D)

To determine the exact collision between any two polygons, use edge/edge intersection tests for all pairs of edges.

One method of checking for edge intersection is to find a separating line between the end points of the edges.

Another method is to solve for the parametric form of the lines;

double kross(Vector2D vec1, Vector2D vec2){
    return vec1.x*vec2.y-vec1.y*vec2.x;
}
 
//one edge is a-b, the other is c-d
Vector2D edgeIntersection(Vector2D a, Vector2D b, Vector2D c, Vector2D d){
    double det=kross(b-a,d-c);
    double t=kross(c-a,b-a)/det;
    double s=kross(c-a,c-d)/det;
    if ((t<0)||(s<0)||(t>1)||(s>1))return NO_INTERSECTION;
    return a+t*(b-a);
}

Exact Collision Between Pairs of Convex Polyhedra

Given two convex polyhedra P & Q, we test each vertex of P to see if it is enclosed in Q and each vertex of Q to see if it is enclosed in P.

To test if a vertex is enclosed in a polyhedra, we must show that the vertex is on the 'inside' of every face of the polyhedra.

Given a vertex v and a face with a normal n and point p, the vertex is on the inward side of the face if

(v-p).n < 0

This test is performed for a vertex against every face of the other object.

A complete collision test should also involve the case where and edge intersects a face, without vertices intersecting.

To test if an edge [v_i,v_j] intersects a face we perform inside/outside tests for each end point

d_i=(v_i-p).n (perpendicular distance to the plane)

d_j=(v_j-p).n

If d_i & d_j have different signs then the edge intersects the plane. It remains to find the point of intersection

t=d_i/(d_i+d_j)

p=v_i+t(v_j-v_i)

This test is carried out for the edge against every face of the polygon. At this stage we know where the edge intersects the planes supporting the polyhedron, but we do not know if the edge intersects the polyhedron itself.

A candidate edge now has a sequence of intersections (sorted by t), which are potential entry and exit points. Each pair of entry/exit points is considered separately. The mid-point is chosen and this mid point is tested if it lies within the polyhedra. If so, then the edge intersects the polyhedra.

Exact Collision in a triangle soup

For a triangle soup (or non-convex polygons) we need to test each pair of triangles. Check each edge in the triangle; does it straddle the other triangle's plane? If so, check if intersection point is in other tiangle.

Efficient exact collision detection methods

A much quicker, but more complicated exact collision detection methods are the Lin-Canny method or GJK algorithm.

© Ken Power 1996-2016