空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

一、Demo说明

二、暴力法

三、网格划分

实测

分析

四、四叉树

四叉树的构建细节

实测

五、松散四叉树

实测

八叉树

六、层次包围盒树（BVH）

包围盒

AABB树

AABB树构建细节

实测

总结

前言

碰撞检测是一个非常经典的问题。虽然现在我们都有物理引擎提供的便捷接口，很多时候不需要我们手动实现，但是了解其中的算法思想有助于拓展我们的思维。而且很多问题其实都可以转化为碰撞检测问题，如：视锥体裁剪、LOD（视野范围与显示对象的碰撞）、RTS游戏中单位自动攻击警戒范围内的敌方单位（警戒范围与敌方单位的碰撞）、光线追踪等。本次分享的不是碰撞检测中的检测算法（分离轴、GJK等），而是用于过滤检测对象的空间划分算法。我将通过实现一个碰撞检测的小demo来介绍碰撞检测中如何使用空间划分做优化以及他们的实现原理。

一、Demo说明

在一个100*100的空间内，随机生成2000个1*1的小方块，小方块生成后会随机赋予一个初速度，小方块将沿速度方向匀速运动，碰到空间边界会反弹。小方块之间不会反弹。现在需要检查方块是否与其他方块发生了碰撞（相交），是的话将方块标记为红色，否则为白色。每种方法的测试中都将列出以下数据做为对比：帧率（FPS）、维护空间数据结构耗时（rebuild time）、碰撞检测耗时（check time）、碰撞检测函数调用次数（intersectsCheckCount）。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

使用trigger

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

使用Physics.OverlapBoxNonAlloc

二、暴力法

如果我们直接对所有的方块两两检测是否发生碰撞，那么算法的时间复杂度将是N平方。在测试中的2000个方块已经卡成PPT，不足1帧。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

暴力法效果图

三、网格划分

可以发现在暴力法中做了太多多余的检查，如果能提前过滤掉一些明显不可能发生碰撞的方块就好了。思路：将空间按网格分块，只对有可能发生碰撞的网格内的方块进行碰撞检测。具体做法就开启一个网格的数组，然后根据方块的坐标计算出应该属于哪些格子，最后只需要对每个格子内的方块进行碰撞检测即可。

实测

下面是将使用32*32的网格来划分空间，这里可以通过对方块的左下角和右上角坐标取模快速得到方块属于哪些网格。经过网格划分之后性能得到了大幅提升。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$ $空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

网格划分效果图

分析

网格划分在大部分时候都是简单又有效的。但是缺点也很明显，如果我们的空间再大点，方块分布也不是这么均匀的话。我们的网格大小就不好定了。网格太大的话碰撞检测的候选项就会增多，降低优化效果。网格太小的话就需要开辟更多的网格节点，而且可能很多节点都不会包含方块造成内存的浪费。下面是将空间扩大到1000*1000，方块初始位置设为左下角后的测试。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

按32*32的网格划分

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

按128*128的网格划分

为了保证网格划分的效果，在更大的空间里就必须使用更多的网格去划分空间。

四、四叉树

网格划分的缺点是空间划分太过死板，因此我们需要一个更灵活的空间划分方案。四叉树就其中之一，四叉树是一种类似二叉树的数据结构，树中的子节点数只能是4或0（叶子节点）。我们将用树中的每个节点对应到空间中的一片区域，并包含这个区域中的对象。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

从图中我们可以清晰的看到树节点到空间的对应关系。根节点代表整个空间的大小，然后将父节点的空间均等地划分为4份，并由4个子节点来表示，然后层层递归下去。

因为不可能无限制的划分下去，一般我们会设置两个阈值来控制一个节点是不是应该继续划分：最大对象数和最大划分层级。当一个节点代表的区域中包含的对象数超过最大对象数，且当前层级小于最大划分层级时，我们才对当前节点进行划分，并将当前节点包含的对象分配到子节点中去。这样就能将对象分布密集的区域划分的更细，实现灵活的空间划分。

利用四叉树将空间划分完毕后，我们就能根据树结构快速查询可能与检测区域发生碰撞的候选项了。具体做法就是从根节点开始检查当前节点代表的区域是否与待检测节点相交，是的话将当前节点包含的对象添加到候选项列表中，然后递归检测子节点即可。

四叉树的构建细节

上面提到的四叉树模型是个理想概念。实际问题中是不会有完美的点，对象都是有一定大小的，比如我们的方块。当方块与多个节点区域相交时怎么办？这里就有两种方案来处理这种情况。下面例子中最大对象数设置为2。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

例子

方案一：只在四叉树的叶子节点包含对象。无法完美划分的对象将分配到每个相交的子区域中。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

使用方案一划分后的树结构

方案二：不只在叶子节点包含对象。无法完美划分的对象留在当前节点中。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

使用方案二划分后的树结构

实测

接下来分别使用两种方案测试一下看看实际表现如何。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

方案一效果图

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

方案二效果图

两种方案帧数都不如网格划分，但是带来了更灵活的空间利用和更稳定的表现（针对之前的更大空间更不均匀的分布），后面会用之前网格最后的例子做对比，我们现在先来分析四叉树两种方案的优劣。四叉树在对象移动后需要重新调整树的结构，这里会产生的额外的开销。

方案一中由于一个对象会同时存在于多个节点中，每一个节点中的对象都要检测是否还在当前节点的区域内，所以在调整树结构的时候开销更大。

方案二中因为存在存在大量“压线”的不能继续往下划分的对象，导致在查询候选项的时候加入了很多明显不可能发生碰撞的对象。比如在之前四叉树中的构建细节中举的例子，当我们要查询方块1所在的区域可能发生碰撞的候选项时，我们会获取到[1,4,5,7]，而按方案一只会获取到[1]。这一点也可以从实测中两种方案的碰撞检测函数的调用次数看出来。

下面我们实际对比一下两种方案获取到的候选项的差异。取左下角区域的候选项，将候选项标记为绿色。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

方案一左下角候选项

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$

方案二左下角候选项

如果能将方块抽象成点就能避免方案二中的问题了，于是就有了松散四叉树。

五、松散四叉树

基于“使用更大的候选区域，检测结果总不会错”的事实。我们可以让四叉树节点实际包含的区域（下图b中的outer boundary）比它代表的区域（下图b中的inner boundary）略大一点。所以这里“松散”对应的是“紧凑”。如下图(c)我们的四叉树节点实际包含是的区域的会有部分重叠的。而实际区域大多少合适呢？综合考虑是边长扩大到原来的2倍泛用性最广，这种情况下只要判断对象的大小是否大于当前节点的子节点所代表的区域大小，如果的大于节点代表区域就留在当前节点。否则只需要判断对象的中心点属于哪个子节点即可分配到对应子节点中。

$空间划分算法优化碰撞检测研究（网格划分、四叉树\八叉树、层次包围盒树BVH）Unity C#实现$