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.
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
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;
There are two approaches to solving this problem;
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.
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.
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.
A bounding box is a primitive shape that encloses the model and should have the following properties;
The use of bounding boxes is extremely common. The 4 common types of bounding boxes are;
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)
...
}
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.
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
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
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.
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.
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 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;
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.
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.
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.
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.
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.
BSP trees are used for single phase collision detection. These can be used in two ways;
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.
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.