Last Updated April 15, 2010

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 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. detectingif 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_maxt²/2.

If the particle is moving with velocity v and a starting position s then its position lies within a_maxt²/2 of the point s+vt.

a_maxt²/2 <= s+vt

This equality 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.hese objects are subject to a more accurate test.

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

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 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
	else if both nodes are leaves
		return IntersectPrimitive(nodeA.primitive, nodeB.primitive)
	
	else if both nodes are internal
		if NodeA.volume > nodeB.volume 
			swap nodes //saves me writing the code twice for each case
		//compare the node with the smaller volume with the children of the node
		//with the larger volume
		Intersect(nodeA, nodeB.child1)
		Intersect(nodeA, nodeB.child2)
		Intersect(nodeA, nodeB.child3)
		...
	else // one node is a leaf the other is internal
		if NodeA is internal
			swap nodes //saves me writing the code twice for each case
		Intersect(nodeA, nodeB.child1)
		Intersect(nodeA, nodeB.child2)
		Intersect(nodeA, nodeB.child3)
		...
}		
		 

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 diatance is less than the sum of half-widths then there is overlap.

Spherical Collision Detection

Using a sphere as a bounding volume for broad phase collision detection, or using the sphere as a surrogate object for narrow phase collision detection allows us to reduce collision detection to a point test.

The approach involves 'inflating' the objects of the world equally in all directions by the size of the sphere's radius, and then reducing the sphere to a point.

The simplest method to inflate the world is to displace the vertices along their normals. Sharp corners can produce redundant space, which can be reduced by the use of 'bevel' planes.

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 full 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 centre of each object is projected onto an axis. The distance between the two projected points is compared to the sum of the "half-widths" or "half-heights". If there is not overlap, then the OBB do not collide. 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) or polyhedra(3D). In this case, the candidate axes will be the normals of all the edges (or faces). The vertices from each object are projected on to the candidate axes and the min & max are found, then a check for overlap is made

Narrow Phase Collision Detection

Exact Collision Between Pairs of Convex or Concave Polygons

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 a 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 is the Lin-Canny method or GJK algorithm.

© Ken Power 2010