「碰撞检测」3D环境中碰撞检测

碰撞检测

Axis-aligned bounding boxes（AABB包围盒）原文地址

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

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

这里写图片描述

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

这里写图片描述

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

1,点与 AABB

如果检测到一个点是否在AABB内部就非常简单了 — 我们只需要检查这个点的坐标是否在AABB内; 分别考虑到每种坐标轴. 如果假设 Px, Py 和 Pz 是点的坐标, BminX–BmaxX, BminY–BmaxY, 和 BminZ–BmaxZ 是AABB的每一个坐标轴的范围, 我们可以使用以下公式计算两者之间的碰撞是否发生:

f(P,B)=(Px>=BminX∧Px<=BmaxX)∧(Py>=BminY∧Py<=BmaxY)∧(Pz>=BminZ∧Pz<=BmaxZ)

或者用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);
}

2,AABB 与 AABB

检查一个AABB是否和另一个AABB相交类似于检测两个点一样. 我们只需要基于每一条坐标轴并利用盒子的边缘去检测. 下图显示了我们基于 X 轴的检测 — 当然, AminX–AmaxX 和 BminX–BmaxX 会不会重叠?

这里写图片描述

在数学上的表示就像这样:

f(A,B)=(AminX<=BmaxX∧AmaxX>=BminX)∧(AminY<=BmaxY∧AmaxY>=BminY)∧(AminZ<=BmaxZ∧AmaxZ>=BminZ)

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

球体碰撞

球体碰撞边缘检测比AABB盒子稍微复杂一点,但他的检测仍相当容易的。球体的主要优势是他们不变的旋转，如果包装实体旋转，边界领域仍将是相同的。他们的主要缺点是,除非他们包装的实体实际上是球形,包装的实体通常不是一个完美的球形(比如用这样的球形包装一个人将导致一些错误,而AABB盒子将更合适)。

1,点与球

检查是否一个球体包含一个点，我们需要计算点和球体的中心之间的距离。如果这个距离小于或等于球的半径,这个点就在里面。

这里写图片描述

两个点A和B之间的欧氏距离是

(Ax-Bx)2)+(Ay-By)2+(Az-Bz)

,我们的公式指出，球体碰撞检测是:

f(P,S)=Sradius>=(Px-Sx)2+(Py-Sy)2+(Pz-Sz)2

或者用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;
}

上面的代码有一个平方根,是一个开销昂贵的计算。一个简单的优化,以避免它由半径平方,所以优化方程不涉及distance < sphere.radius * sphere.radius.

2,球体与球体

测试一个球和一个AABB的碰撞是稍微复杂,但过程仍然简单和快速。一个合乎逻辑的方法是，检查AABB每个顶点,计算每一个点与球的距离。然而这是大材小用了,测试所有的顶点都是不必要的,因为我们可以侥幸计算AABB最近的点(不一定是一个顶点)和球体的中心之间的距离,看看它是小于或等于球体的半径。我们可以通过逼近球体的中心和AABB的距离得到这个值。

这里写图片描述

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

使用一个物理引擎

原文 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.

转发者说: 上面英文并不难,本人才疏学浅有翻译不对的地方请指正或直接看原文

3D物理引擎提供了碰撞检测算法,大多数也是基于边界检测,物理引擎是创建一个虚拟形状,这个模拟形状是在模拟碰撞中要使用到的,请查看演示demo 这里是源代码同时也可以看一下开始的物理引擎CAMON.JS

[参考资料]

3D环境中碰撞检测

碰撞检测

1,点与 AABB

2,AABB 与 AABB

球体碰撞

1,点与球

2,球体与球体

使用一个物理引擎

相关阅读

栏目导航

推荐阅读

热门阅读