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

A generalised collision detection involves computing the interaction of N independent objects (requiring N2) 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;

(N2-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

There are two approaches to solving this problem;

  1. Broad phase/Narrow phase:

  2. Single Phase methods

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 amax. At any future time t it's position must be within the radius amaxt2/2.

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

amaxt2/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, say) 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

Maintain a sorted list of extents for the bounding boxes in each axis. Sweep through each axis to identify overlaps (pairs of extents which overlap). If the same overlaps exists in all axis, then an intersection has occurred.

 
Sort all the x-axis extents 
Sort y axis extents 
Sort z-axis extents  
  note: a modified bubble sort can be used as the lists do not change much between 
  frames 
  
reset active list (list of active extents) 
reset output list (list of  potential intersections) 

sweep through the x-axis extents if an extent entry is found for each entry on the active list create a pair with the current box and send to output list put the associated box on the active list if an extent exit is found, remove associated box from active list
sweep through y-axis-extents if an extent entry is found, for each entry on the active list create a pair with the current box, if this pair is in the outputlist, mark as "potential" put the associated box on the active list if an extent exit is found, remove associated box from active list remove entries on the output list not marked as "potential"
sweep through z-axis-extents if an extent entry is found, for each entry on the active list create a pair with the current box, if this pair is in the outputlist, mark as "intersected" put the associated box on the active list if an extent exit is found, remove from active list remove entries on the output list not marked as "intersected" the output list now contains a list of intersecting bounding boxes

Object Spatial Partitioning

As we have seen partitioning space in to voxels is wasteful on memory. For a collision detection system, the voxel/object relationships would have to be constantly updated for moving objects.

However, voxels can be effective if used on a local(per object) basis.

During the build phase, each object is enclosed in a Oriented Bounding box (OBB). This box is called a container. The container is then subdivided into a regular grid. Each voxel in the grid points to the polygons contained within.

The container receives the same transformations as the object.

The container, which mirrors the rotations of the object, is enclosed in an AABB.

The collision detection between objects A & B proceeds as follows;

Test the two AABBs for overlap, if there is no overlap, exit

Transform B into A's local space and find the AABB of B. The AABB of A in A's local space will be A's container. Determine which voxels of A overlap B's AABB.
Transform A into B's local space and find the AABB of A. The AABB of B in B's local space will be B's container. Determine which voxels of A overlap B's AABB. Compare each of the polygons in A's intersection voxels to each of the polygons in B's intersection voxels. These are the only polygons which can possibly collide

 

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.

 

 

Narrow Phase Collision Detection

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 two edges intersect, without vertices intersecting.

 

To test if an edge [vi,vj] intersects a plane we perform inside/outside tests for each end point

di=(vi-p).n (perpendicular distance to the plane)

dj=(vj-p).n

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

t=di/di+dj

x=vi+t(vj-vi)

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

 

Lin-Canny Closest Features Method

The brute-force approach discussed above is very expensive and takes no advantage of temporal or spatial coherence.

An attractive method developed by Lin & Canny can compute collisions between polyhedra. The great thing about this method is that object complexity does not impact significantly on the speed of the algorithm.

Features & Voronoi regions

Features of a polyhedron are vertices, edges and faces. Points in the space around a polyhedron can be classified according to which feature is closest. These groups of points are called voronoi regions. Voronoi regions can be calculated at build-time.

To determine which feature is closest to a given point, just figure out which voronoi region the point is in.

The Lin-Canny approach uses voronoi regions to determine which two features of two polyhedra are closest.

The goal of this algorithim is to find the closest points between two objects. A pair of points are closest if they are both in voronoi region of the other feature.

Given a pair of features there are 6 cases to consider;

  1. vertex to vertex
  2. vertex to edge
  3. vertex to face
  4. edge to edge
  5. edge to face
  6. face to face

Cases 5 & 6 will only occur when a edge or face is exactly parallel to a face, as this occurs extremely rarely we will not consider them.

The technique starts with an arbitrary pair of features (one on each polyhedron) and then find the closest points (pointa & pointb) between these features.

We must check if pointa is the closest point in polyhedron A to polyhedron B. (is pointa in the voronoi region of pointb's feature?)

We must check if pointb is the closest point in polyhedron B to polyhedron A.(is pointb in the voronoi region of pointa's feature?)

If either check fails, then find a new feature which is closer and recheck.

Eventually the closest points will be found.

 

Closest point

The algorithm requires that the closest points between each pair of features be found;

For vertex to vertex, the closest points are the vertices themselves (trivial case)

For vertex to edge, the closest point is determined by finding the perpendicular distance to the edge's supporting line from the vertex. If this point lies outside the edge, end point closest to the point is used.

For vertex to face, the perpendicular distance to the supporting plane is found, if this point lies outside the face, then the face vertex closest is used.

 

 

Point-Vertex test

If a vertex is the closest feature to a point, then the point must lie in the voronoi region of the vertex.

If the point lies inside the Voronoi region of the feature, the the feature is the nearest feature to that point, otherwise son eother feature is nearer.

The voronoi region of a vertex is the space enclosed by planes through the vertex at right angles to each of the vertex's edges. If a point lies 'outside' one of these planes then the edge associated with that plane is a closer feature to the point and the procedure selects the edge as a candidate closest feature.

Point-Edge Test

If an edge is the closest feature on a polyhedron to a point, then the point must lie in the voronoi region of the edge.

The voronoi region of edge is the space enclosed by two planes through the edge at right angles to each of the edges faces. Planes at right angles to the edge through the endpoints complete the voronoi region. If a point lies 'outside' one of these planes then the face or vertex associated with that plane is a closer feature to the point and the procedure selects the face or vertex as a candidate closest feature.

Point-Face Test

If a face is the closest feature on a polyhedron to a point, then the point must lie in the voronoi region of the face.

The voronoi region of face is the space enclosed by the planes through the edges at right angles to the faces. If a point lies 'outside' one of these planes then edge with that plane is a closer feature to the point and the procedure selects the edge as a candidate closest feature.

 

Procedure

  1. If the features are a pair of vertices, then they both have to satisfy the applicability conditions imposed by each other, in order for them to be the closest features. If either one of the vertices fails the applicability test imposed by the other, the algorithm will return a new pair of features ­ one of the two vertices and the edge for which the test failed, then continue checking the new features until it finds the closest pair.
  2. Given a vertex and an edge, the algorithm will check whether the vertex satisfies the applicability conditions imposed by the edge and whether the nearest point on the edge to the vertex satisfies the applicability conditions imposed by the vertex. If both verifications return value "true", then they are the closest features. Otherwise, a corresponding new pair of features (depending on which test failed) will be returned and the algorithm will proceed until it finds the pair of closest features.
  3. For the case of a vertex and a face, both of the applicability tests imposed by the face to the vertex and from vertex to the nearest point on the face must be satisfied for this pair to qualify as the "closest­ feature pair". Otherwise, a new pair of features will be returned and the algorithm will be called again until the closest­feature pair is found.
  4. Similarly, given a pair of edges as inputs, if their nearest points satisfy the applicability conditions imposed by the each other, then they are the closest features between two polyhedra. If not, one of the edges will be changed to a neighboring vertex or a face and the check will be done again on the new pair of features.
  5. When a given pair of features is an edge and a face, we first need to decide whether the edge is parallel to the face. If it isn't, then the actual closest features will be either one of the vertices of the edge and the face, or the edge and some other edge bounding the face. The former case occurs when this vertex satisfies the vertex­face applicability condition, and when the edge is pointing "into" the face in the direction of this vertex. Otherwise the latter case applies. The edge (bounding the face) to be chosen is the edge which is closest to the original edge.

Single Phase Collision detection

BSP trees

BSP trees are used for single phase collision detection. These can be used in two ways;

  1. ray intersecting
  2. tree merging

Using BSP trees for ray intersecting

Testing for ray intersecting objects in a scene is a useful procedure in graphics and games. It asks the question, "if I move along this direction, which objects will I hit?". This is an important question for path finding, interactive games and has applications in lighting and shadow calculations. Testing for ray intersection is also a solution to the time-step problem, in which a collision might not be detected because the collision fell between two time steps. (An example of under sampling).

The test procedure is recursive, as usual;

testintersect(bsp_root,start_of_ray, end_of_ray);
...
...
test_intersect(node, s, e){
	check which side of plane for s and e
	if(s and e are on +ive side) // ray cannot intersect plane
		test_intersect(node.positivechild,s,e);
	else if(s and e are on -ive side)// ray cannot intersect plane
		test_intersect(node.negativechild,s,e);
	else{ // points on either side of plane
		find point of intersection (i) between ray and plane
		if( i is inside face)
			output intersection;
		// split ray in two and test the two pieces against the left and right sub trees
		p=point on positive side;
		n=point on negative side
		test_intersect(node.negativechild,n,i);	
		test_intersect(node.positivechild,p,i);	
	}
}
		

To test if a point is inside a triangle (or any polygon) test if the point is on the 'inside' of each edge of the triangle. Normals for each edge need to be maintained.

Collision detection using BSP tree merging

Given a local BSP tree for an object, it can be seen that the left most node corresponds to the inside of the object. We can merge two bsp trees to determine if their spaces overlap. By merging one tree with another, a collision is present if parts of the second tree are inserted into the leftmost node of the first tree.