3D碰撞/物体检测是如何工作的？

Question

3D碰撞/物体检测是如何工作的？

algorithmdata-structures3dcollision-detection

58

我一直很想知道这个问题。在像GTA这样的游戏中，有成千上万个物体，游戏怎么会立即知道你是否在医疗包附近呢？

显然不可能为每个物体都设置一个事件监听器，迭代也不是好的选择。我只是想知道它是如何实现的。

- jmasterx

6个回答

9

四叉树和八叉树, 另一个四叉树, 是使用空间分割的流行方法，用于实现此目的。后面的示例显示，在处理碰撞时，与逐对暴力搜索相比，可以减少97％的处理时间。

- joshperry

4

游戏物理引擎中常用的技术之一是扫描和修剪方法。这在David Baraff's SIGGRAPH notes（参见Motion with Constraints章节）中有解释。Havok绝对使用了这种方法，我认为它也是Bullet中的一个选项，但我不确定PhysX是否也使用了它。

其思想是可以查看每个轴上AABB（轴对齐边界框）的重叠；如果两个对象的AABB的投影在所有三个轴上重叠，则AABB必须重叠。通过对AABB的起点和终点进行排序，可以相对快速地检查每个轴；由于通常大多数对象移动得不太快，因此帧之间存在很多时间相干性，因此排序不会发生太大变化。

一旦扫描和修剪检测到AABB之间的重叠，您就可以对对象进行更详细的检查，例如球体与盒子的碰撞。如果详细检查显示出碰撞，则可以通过施加力来解决碰撞，并/或触发游戏事件或播放音效。

- celion

2

没错。通常情况下，并不是每个对象都有一个事件监听器。通常在内存中会有一棵非二叉树结构，模拟你的游戏地图。可以想象成地铁/地下铁路地图。

这种内存结构是游戏中物品的集合。包括玩家、怪物、可捡起的物品或可能爆炸并对你造成伤害的物品。因此，当玩家在游戏中移动时，玩家对象指针会在游戏/地图内存结构中移动。

参见如何使我的游戏实体了解周围的事物？

- kingchris

1

有很多可以使用的优化。首先-任何物体（以i为索引）被一个立方体所包围，中心坐标为CXi，CYi，尺寸为Si 其次-碰撞检测是基于估计值的：

a) 找到所有满足条件的i、j立方体对：Abs(CXi-CXj)<(Si+Sj) AND Abs(CYi-CYj)<(Si+Sj)

b) 现在只处理a)中获取的一组对。我们更准确地计算它们之间的距离，类似于Sqrt(Sqr(CXi-CXj)+Sqr(CYi-CYj))，现在对象表示为几个简单图形的集合-立方体、球体、圆锥体-并且我们使用几何公式来检查这些图形的交点。

c) b)中具有检测到交点的对象将作为需要进行物理计算等处理碰撞的对象。

- user224564

1

我想推荐Christer Ericson的实时碰撞检测的优秀书籍。它介绍了碰撞检测的基础知识，并提供了当代研究成果的参考资料。《实时碰撞检测》（摩根·考夫曼交互式3D技术系列）

- wojakzek

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- charstar · Accepted Answer

关于如何处理大型世界的空间分割方法，通常会使用类似四叉树或kd树的方式进行划分，这样可以使得查找最近邻居的时间复杂度降低到线性以下（分数幂次，或者在3D游戏中为O(N^(2/3))）。这些方法通常被称为二进制空间划分（BSP）。

对于碰撞检测，每个物体通常还有一个与之关联的包围盒网格（由一组构成凸多面体的多边形组成）。这些高度简化的网格（有时只是一个立方体）不绘制，而是用于检测碰撞。最原始的方法是创建一个垂直于连接两个物体中点的线的平面，并将该平面与该线相交于中点处。如果一个物体的包围盒在该平面的两侧都有点，则发生碰撞（只需要测试其中一个包围盒与平面的位置关系）。另一种方法是增强的GJK距离算法。如果您需要一份教程，可以查看NeHe Productions的OpenGL第30课。

顺便提一下，包围盒还可用于其他优化，例如所谓的遮挡查询。这是一种确定哪些物体在其他物体（遮挡者）后面，因此不需要处理/渲染的过程。包围盒还可用于截锥体剔除，即确定哪些物体在透视视图体积之外（太近、太远或超出您的视野角度），因此不需要渲染。

正如Kylotan指出的那样，使用包围体在检测遮挡时可能会产生错误的阳性结果，并且对于某些类型的对象（例如通过甜甜圈孔洞观察）根本不起作用。让这些对象正确地遮挡是关于“门户剔除”的另一个主题。