这篇翻译不完整。请帮忙从英语翻译这篇文章

本文介绍了用于在3D环境中实现不同边界体积碰撞检测的技术。 后续文章将讨论特定3D库中的实现。

Axis-aligned bounding boxes(AABB包围盒

 

在游戏中,为了简化物体之间的碰撞检测运算,通常会对物体创建一个规则的几何外形将其包围。其中,AABB(axis-aligned bounding box)包围盒被称为轴对齐包围盒。

与2D碰撞检测一样,轴对齐包围盒是判断两个物体是否重叠的最快算法,物体被包裹在一个非旋转的(因此轴对齐的)盒中,并检查这些盒在三维坐标空间中的位置,以确定它们是否重叠。

由于性能原因,轴对齐是有一些约束的。两个非旋转的盒子之间是否重叠可以通过逻辑比较进行检查,而旋转的盒子则需要三角运算,这会导致性能下降。如果你有旋转的物体,可以通过修改边框的尺寸,这样盒子仍可以包裹物体,或者选择使用另一种边界几何类型,比如球体(球体旋转,形状不会变)。下图是一个AABB物体旋转,动态调节盒大小适应物体的例子。

Note: 参考这里使用Three.js进行边界体积碰撞检测。

Point versus 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 Px, Py and Pz are the point's coordinates, and BminXBmaxX, BminYBmaxY, and BminZBmaxZ are the ranges of each exis of the AABB, we can calculate whether a collision has occured between the two using the following formula:

f(P,B)=(Px>=BminXPx<=BmaxX)(Py>=BminYPy<=BmaxY)(Pz>=BminZPz<=BmaxZ)f(P,B)= (P_x >= B_{minX} \wedge P_x <= B_{maxX}) \wedge (P_y >= B_{minY} \wedge P_y <= B_{maxY}) \wedge (P_z >= B_{minZ} \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.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. The diagram below shows the test we'd perform over the X axis — basically, do the ranges AminXAmaxX and BminXBmaxX overlap?

updated version

Mathematically this would look like so:

f(A,B)=(AminX<=BmaxXAmaxX>=BminX)(AminY<=BmaxYAmaxY>=BminY)(AminZ<=BmaxZAmaxZ>=BminZ)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 a AABB would be a better match).

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 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 (Ax-Bx)2)+(Ay-By)2+(Az-Bz)\sqrt{(A_x - B_x) ^ 2) + (A_y - B_y)^2 + (A_z - B_z)} , our formula for point versus sphere collision detection would work out like so:

f(P,S)=Sradius>=(Px-Sx)2+(Py-Sy)2+(Pz-Sz)2f(P,S) = S_{radius} >= \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 versus 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)=(Ax-Bx)2+(Ay-By)2+(Az-Bz)2<=Aradius+Bradiusf(A,B) = \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 versus 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;
}
 

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:

文档标签和贡献者

 此页面的贡献者: varcat
 最后编辑者: varcat,