In this set of articles, we will see different bounding volumes techniques to implement collision detection in 3D environments.
Axis-aligned Bounding-Boxes
As with 2D collision detection, axis-aligned bounding-boxes (AABB) are the quickest algorithm to determine whether two game entities are overlaping or not. It consists in wrapping game entities in a non-rotated (thus axis-aligned) box, and check overlapping between these boxes.
The axis-aligned constraint is there because of performance reasons. The overlapping between two non-rotated boxes can be check with just logical comparisons, whereas rotated boxes require trigonometry operations as well, which are slower. If you have entities that will be rotating, you can either modify the dimensions of the bounding-box so it still wraps the object, or opt for another bounding geometry, such as spheres (which are invariant to rotation). Here's a graphic example of an AABB that adapts its size to fit the rotating entity:
Note: If you are using Three.js, check out the Bounding Boxes with Three.js article.
Point versus AABB
Checking if a point is inside an AABB is just checking whether its coordinates fall inside each of the axis. Assuming Px, Py and Pz are the point's coordinates, and BminX, BmaxZ, etc. contain the limits of the AABB:
Or in JavaScript:
function isPointInsideAABB(point, box) {
return (point.x >= box.minX && point.x <= box.maxX) &&
(point.y >= box.minY && point.y <= box.maxY) &&
(point.z >= box.minY && point.z <= box.maxZ);
}
AABB versus AABB
Checking whether an AABB intersects another AABB is similar to the point test. We just need to do one test per axis, using the boxes' boundaries. This figure shows the tests over the X axis.
Mathematically:
In JavaScript:
function intersect(a, b) {
return (a.minX <= b.maxX && a.maxX >= b.minX) &&
(a.minY <= b.maxY && a.maxY >= b.minY) &&
(a.minZ <= b.maxZ && a.maxZ >= b.minZ);
}
Bounding spheres
Using bounding spheres to detect collisions is a bit more expensive than AABB, but still a quick test. The main advantage of spheres is that they are invariant to rotation, so if the wrapped entity rotates, the bounding sphere would still be the same.
Point versus sphere
To check whether an sphere contains a point we need to calculate the distance between the point and the sphere's center. If it's smaller or equal than the radius of the sphere, the point is inside it.
Taking into account, that the euclidean distance between two points A and B is :
In JavaScript:
function isPointInsideSphere(point, sphere) {
// we are using multiplications because is faster than calling Math.pow
var distance = Math.sqrt((point.x - sphere.x) * (point.x - sphere.x) +
(point.y - sphere.y) * (point.y - sphere.y) +
(point.z - sphere.z) * (point.z - sphere.z));
return distance < sphere.radius;
}
The code above features an square root. An easy optimization to avoid it consists on squaring the radius instead. So the final sentence would involve distance < sphere.radius * sphere.radius.
Sphere versus sphere
The sphere versus sphere test is also similar to the point vs sphere. What we need to test instead is that the distance between the centers is less or equal than the sum of their radiuses.
Mathematically:
In JavaScript:
function intersect(sphere, other) {
// we are using multiplications because is faster than calling Math.pow
var distance = Math.sqrt((sphere.x - other.x) * (sphere.x - other.x) +
(sphere.y - other.y) * (sphere.y - other.y) +
(sphere.z - other.z) * (sphere.z - other.z));
return distance < (sphere.radius + other.radius); }
}
Sphere versus AABB
Testing a sphere versus an AABB is slightly more complicated, but still simple and fast. A trivial approach would be checking every vertex of the AABB and do a point versus sphere test. However, testing all the vertices is unnecessary –we can get by with just the closest point (not necessarily a vertex) to the sphere's center. We can get this value by clamping the sphere's center to the AABB's limits.
In JavaScript:
function intersect(sphere, box) {
// get box closest point to sphere center by clamping
var x = Math.max(box.minX, Math.min(sphere.x, box.maxX);
var y = Math.max(box.minY, Math.min(sphere.y, box.maxY);
var z = Math.max(box.minZ, Math.min(sphere.z, box.maxZ);
// this is the same as isPointInsideSphere
var distance = Math.sqrt((x - sphere.x) * (x - sphere.x) +
(y - sphere.y) * (y - sphere.y) +
(z - sphere.z) * (z - sphere.z));
return distance < sphere.radius;
}
See also
Related articles on MDN:
External resources:
- Simple intersection tests for games on Gamasutra
- Bounding volume on Wikipedia