1) 如果盒子的大小不相等:
- 在X轴上对盒子进行排序
- 通过仅在范围内比较(因为它是1D且已排序,所以只需比较范围内的盒子),为每个盒子生成1D邻接列表,例如第一个盒子为[(1,2),(1,3),(1,5),....],第二个盒子为[(2,1),(2,6),..]等(从当前索引开始而非从索引0开始,向两个方向迭代直到超出盒子范围)
- 遍历1D邻接列表并删除重复项或仅在向后处理时不执行最后一步(仅与大于索引的盒子进行比较以避免重复)
- 将邻接点按盒子索引分组,例如[(1,a),(1,b),..(2,c),(2,d)...]
- 在每个组内按Y轴对第二个盒子的邻接点进行排序
- 在每个组内,创建2D邻接列表,例如[(1,f),(1,g),..]
- 删除重复项
- 再次按第一个盒子索引分组
- 对每个组中第二个盒子的Z值进行排序
- 创建3D邻接列表
- 删除重复项
- 按对中的第一个索引进行分组
- 结果为当前邻接列表(它是稀疏矩阵,因此除非所有盒子都与其他盒子相接触,否则不会占用完整的O(N * N)内存消耗)
因此,总共需要:
- 1次完整排序(O(N * logN))
- 2次部分排序,其长度取决于碰撞数量
- 3次将对配对在一起(每个都是O(N))
- 删除重复项(或只与较小索引进行比较):O(N)
这应该比O(N^2)更快。
2) 如果矩形大小相等,则可以执行以下操作:
3) 如果矩形大小不相等,则仍然可以通过多个较小的正方形盒子“构建”它们并应用第二(2)种方法。这将通过每个原始盒子的k = 正方形盒子数乘以总计算时间复杂度来增加。这仅需要在每个较小的正方形盒子中添加一个额外的“父”盒子指针来更新原始盒子条件。
这个方法和第二个方法可以轻松并行化,以获得更高的性能。但我认为第一个方法应该在每次扫描轴后使用越来越少的内存,因此您可以轻松地进行4维、5维等操作,而第二种和第三种方法需要处理更多数据,因为碰撞单元格数量增加了。如果所有框都接触所有框,则两种算法都可能变得太慢。
4) 如果有“体育场中的茶壶”问题(所有框在网格的单个单元格中,仍然不接触或仅相距几个单元格),
- 从框中心构建八叉树(或任何嵌套结构)
- 在八叉树遍历中计算碰撞,只访问最近的节点,向上/向下遍历树
1-revisited) 如果框移动缓慢(因此您需要在每个新帧中重新构建邻接列表),则方法(1)会变得有些棘手。缓冲区域太小,需要在每个帧上重新计算,计算量很大。缓冲区域太大,则需要维护更大的碰撞列表,并进行额外的过滤以获取真正的碰撞。
2-revisited) 如果环境是无限周期的(例如在模拟《黑客帝国》中被困在火车站中的Neo),则可以再次使用单元格网格,但这次要使用包裹边界作为额外的碰撞检查。
对于上述所有方法(除第一个方法外),您可以通过先进行球形碰撞检查(广泛碰撞检查)来加速碰撞检查,以避免不必要的框碰撞检查。(球形碰撞不需要平方根,因为两侧具有相同的计算,只需平方差之和即可)。这应该只会线性加速。
对于每个单元格具有限定数量的框的方法(2),您可以使用向量化(SIMD)来进一步加速检查。同样,这应该会给出线性加速。
对于所有方法,您可以使用多个线程来加速其中一些步骤,从而实现另一个线性加速。
即使没有上述任何方法,问题中的两个for循环也可以修改为进行瓷砖计算,以保持在L1高速缓存中,以获得额外的线性性能,然后在寄存器(SSE/AVX)中进行第二个瓷砖计算,以在暴力时间复杂度期间实现峰值计算性能。对于较少数量的框,这可能比那些加速结构运行得更快,而且简单易行:
select a group of boxes n=multiple of 8
select another group of boxes n=multiple of 8
iterate first group 8 by 8
iterate second group 8 by 8
Only rotate the vector to scan all 8 elements (64 collision checks for each 2 vectors)
write results for 8 boxes in first group
坐标仅是16位整数吗?那么您可以使用哈希(distanceX,distanceY,distanceZ,sizeXYZ)作为键和true/false作为值来缓存每个碰撞结果。
因此,解决方案取决于您的问题。N是多少?箱子重叠很多吗?它们堆积在一个大环境中还是散布开来?系统中有多少个核心? 有多少内存?盒子是否移动以及移动速度如何?您对多少个盒子的运行时期望是什么?
编辑:我尝试编写了一个自适应网格(对“体育场里的茶壶”问题进行了优化),代码不到500行:https://github.com/tugrul512bit/FastCollisionDetectionLib
它没有优化以降低缓冲区分配开销,也不是多线程和向量化的,但对于均匀分布的粒子和离质心100倍远的一些距离结合在一起的粒子,它可以线性扩展。它比暴力方法快数百到数千倍,取决于粒子数量在20k到100k之间。但还没有针对不同形状的盒子进行测试,只针对相同的盒子。