Nossos voluntários ainda não traduziram este artigo para o Português (do Brasil). Junte-se a nós e ajude-nos a fazer o trabalho!

Você também pode ler o artigo em English (US).

This article provides an introduction to the different bounding volume techniques used to implement collision detection in 3D environments. Followup articles will cover implementations in specific 3D libraries.

## Axis-aligned bounding boxes

As with 2D collision detection, **axis-aligned bounding boxes** (AABB) are the quickest algorithm to determine whether the two game entities are overlapping or not. This consists of wrapping game entities in a non-rotated (thus axis-aligned) box and checking the positions of these boxes in the 3D coordinate space to see if they are overlapping.

The** axis-aligned constraint** is there because of performance reasons. The overlapping area between two non-rotated boxes can be checked with logical comparisons alone, whereas rotated boxes require trigonometric operations as well, which are slower to calculate. 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 to use another bounding geometry type, such as spheres (which are invariant to rotation.) The animated GIF below shows a graphic example of an AABB that adapts its size to fit the rotating entity. The box constantly changes dimensions to snugly fit the entity contained inside.

**Note:** Check out the Bounding Volumes with Three.js article to see a practical implementation of this technique.

### Point vs. AABB

Checking if a point is inside an AABB is pretty simple — we just need to check whether the point's coordinates fall inside the AABB; considering each axis separately. If we assume that *P _{x}*,

*P*and

_{y}*P*are the point's coordinates, and

_{z}*B*–

_{minX}*B*,

_{maxX}*B*–

_{minY}*B*, and

_{maxY}*B*–

_{minZ}*B*are the ranges of each axis of the AABB, we can calculate whether a collision has occurred between the two using the following formula:

_{maxZ}$f(P,B)=\; (P\_x\; >=\; B\_\{minX\}\; \backslash wedge\; P\_x\; <=\; B\_\{maxX\})\; \backslash wedge\; (P\_y\; >=\; B\_\{minY\}\; \backslash wedge\; P\_y\; <=\; B\_\{maxY\})\; \backslash wedge\; (P\_z\; >=\; B\_\{minZ\}\; \backslash wedge\; P\_z\; <=\; B\_\{maxZ\})$

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.minZ && point.z <= box.maxZ); }

### AABB vs. 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. The diagram below shows the test we'd perform over the X-axis — basically, do the ranges *A _{minX}*–

*A*and

_{maxX}*B*–

_{minX}*B*overlap?

_{maxX}Mathematically this would look like so:

$f(A,B)\; =$

And in JavaScript, we'd use this:

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 complex than AABB, but still fairly quick to 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. Their main disadvantage is that unless the entity they are wrapping is actually spherical, the wrapping is usually not a good fit (i.e. wrapping a person with a bounding sphere will cause a lot of false positives, whereas an AABB would be a better match).

### Point vs. sphere

To check whether a sphere contains a point we need to calculate the distance between the point and the sphere's center. If this distance is smaller than or equal to the radius of the sphere, the point is inside it.

Taking into account that the euclidean distance between two points *A* and *B* is $\backslash sqrt\{(A\_x\; -\; B\_x)\; ^\; 2)\; +\; (A\_y\; -\; B\_y)^2\; +\; (A\_z\; -\; B\_z)\}$ , our formula for point vs. sphere collision detection would work out like so:

$f(P,S)\; =\; S\_\{radius\}\; >=\; \backslash sqrt\{(P\_x\; -\; S\_x)^2\; +\; (P\_y\; -\; S\_y)^2\; +\; (P\_z\; -\; S\_z)^2\}$

Or 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 a square root, which can be expensive to calculate. An easy optimization to avoid it consists of squaring the radius, so the optimized equation would instead involve `distance < sphere.radius * sphere.radius`

.

### Sphere vs. sphere

The sphere vs sphere test is similar to the point vs sphere test. What we need to test here is that the distance between the sphere's centers is less than or equal to the sum of their radii.

Mathematically, this looks like so:

$f(A,B)\; =\; \backslash sqrt\{(A\_x\; -\; B\_x)^2\; +\; (A\_y\; -\; B\_y)^2\; +\; (A\_z\; -\; B\_z)^2\}\; <=\; A\_\{radius\}\; +\; B\_\{radius\}$

Or in JavaScript:

function intersect(sphere, other) { // we are using multiplications because it's 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 vs. AABB

Testing whether a sphere and an AABB are colliding is slightly more complicated, but still simple and fast. A logical approach would be to check every vertex of the AABB, doing a point vs sphere test for each one. This is overkill, however — testing all the vertices is unnecessary, as we can get away with just calculating the distance between the AABB's *closest** point* (not necessarily a vertex) and the sphere's center, seeing if it is less than or equal to the sphere's radius. We can get this value by clamping the sphere's center to the AABB's limits.

In JavaScript, we'd do this test like so:

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; }

**NOTE: This only works if the vertex itself is colliding with the sphere. If the sphere is only colliding on a face, or even completely encapsulated by the BB, then this calculation method does not work.**

var sphere = {x: 0, y: 0, z: 0, radius: 1}; //Sphere of radius 1 centered on origin var box = {minX: -2, minY: -2, minZ: 0, maxX: 2, maxY: 2, maxZ: 4}; //Box 4×4×4, centered on x-y origin, one side on z plane, cutting sphere in half 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; } intersect(box, sphere); //returns false, should return true since rectangle is cutting sphere in half.

## Using a physics engine

**3D physics engines** provide collision detection algorithms, most of them based on bounding volumes as well. The way a physics engine works is by creating a **physical body**, usually attached to a visual representation of it. This body has properties such as velocity, position, rotation, torque, etc., and also a **physical shape**. This shape is the one that is considered in the collision detection calculations.

We have prepared a live collision detection demo (with source code) that you can take a look at to see such techniques in action — this uses the open-source 3D physics engine cannon.js.

## See also

Related articles on MDN:

External resources:

- Simple intersection tests for games on Gamasutra
- Bounding volume on Wikipedia

## Etiquetas do documento e colaboradores

**Etiquetas:**

**Colaboradores desta página:**cursorweb, chrisdavidmills, RafeyIqbalRahman, wbamberg, thenoelman, SvenskNavi, kevzettler, rileym7, kelvinscarlet, ladybenko, hbloomer

**Última atualização por:**cursorweb,