跨格会让同一物体对多次进入候选抽屉提交窄相前需要去重。封面展示的是候选收集过程。空间分区像给场景放了许多抽屉。但一个物体可能跨过抽屉边界两个物体也可能在相邻格子的边缘相碰。只按中心点登记常常能画出整齐的网格却漏掉需要检查的物体对。先留下一个能反复运行的反例大箱子越过四个格子小箱子碰到它的一角。广相位只筛候选不作最终判决空间网格、四叉树等方法先减少潜在物体对之后仍要用适合形状的窄相位判断实际接触。两者应分开测试候选可以多一些漏掉真实接触则无法由后面的精确算法补救。下面使用轴对齐矩形及固定网格。它不是完整四叉树也不处理旋转、连续碰撞或高速穿越。把这些范围说清楚比直接给出O(NlogN)的总括更有价值最坏情况下很多物体仍可能聚到同一格子。多格登记后物体对要去重把包围盒覆盖的格子全部登记同一对物体就可能在多个格子出现。候选对按稳定ID排序后放入集合精确检测只做一次。实际实现还要确定边界规则恰好贴在网格线上是否占另一格。保守多算通常可以接受但必须统一不同分支使用不同闭开区间会让相同场景得到不同候选。先保住不漏再谈节省多少性能记录应来自目标场景和设备。Unity Profiler可以连接实际目标平台取样在编辑器里看到某段代码更短不足以宣布物理帧耗时下降。对我而言周末值得保留的一行结果不是“优化成功”而是下面这个跨格候选仍然存在。以后替换数据结构时它也能继续提醒我不要弄丢这对箱子。跨越分区边界的大物体登记多个格子再对候选物体对去重最后才做精确碰撞。把关键规则缩成一个可运行例子下面使用 Python 3 标准库表达算法规则保存为example.py后运行python3 example.py。它便于观察输入和输出不替代引擎中的 C、Shader 或模型实现。from math import floor from itertools import combinations def candidates(boxes): cells {} for ident, (x0, y0, x1, y1) in enumerate(boxes): for x in range(floor(x0), floor(x1) 1): for y in range(floor(y0), floor(y1) 1): cells.setdefault((x, y), []).append(ident) return {tuple(sorted(pair)) for ids in cells.values() for pair in combinations(ids, 2)} boxes [(0, 0, 1.2, 1.2), (0.9, 0.9, 1.5, 1.5), (4,4,5,5)] pairs candidates(boxes) assert pairs {(0, 1)} print(unique candidate pairs:, sorted(pairs))本例输出unique candidate pairs: [(0, 1)]这一步完成后再增加负坐标、极大包围盒和全部重叠场景。算法在理想分布里省下多少工作可以慢慢测先别让最普通的一次边界接触从系统里消失。适用范围未运行刚体引擎或统计帧时间网格例子只验证候选覆盖与去重没有声称完整碰撞检测通过。相关资料Unity Profiler手册
跨格会让同一物体对多次进入候选抽屉提交窄相前需要去重。封面展示的是候选收集过程。空间分区像给场景放了许多抽屉。但一个物体可能跨过抽屉边界两个物体也可能在相邻格子的边缘相碰。只按中心点登记常常能画出整齐的网格却漏掉需要检查的物体对。先留下一个能反复运行的反例大箱子越过四个格子小箱子碰到它的一角。广相位只筛候选不作最终判决空间网格、四叉树等方法先减少潜在物体对之后仍要用适合形状的窄相位判断实际接触。两者应分开测试候选可以多一些漏掉真实接触则无法由后面的精确算法补救。下面使用轴对齐矩形及固定网格。它不是完整四叉树也不处理旋转、连续碰撞或高速穿越。把这些范围说清楚比直接给出O(NlogN)的总括更有价值最坏情况下很多物体仍可能聚到同一格子。多格登记后物体对要去重把包围盒覆盖的格子全部登记同一对物体就可能在多个格子出现。候选对按稳定ID排序后放入集合精确检测只做一次。实际实现还要确定边界规则恰好贴在网格线上是否占另一格。保守多算通常可以接受但必须统一不同分支使用不同闭开区间会让相同场景得到不同候选。先保住不漏再谈节省多少性能记录应来自目标场景和设备。Unity Profiler可以连接实际目标平台取样在编辑器里看到某段代码更短不足以宣布物理帧耗时下降。对我而言周末值得保留的一行结果不是“优化成功”而是下面这个跨格候选仍然存在。以后替换数据结构时它也能继续提醒我不要弄丢这对箱子。跨越分区边界的大物体登记多个格子再对候选物体对去重最后才做精确碰撞。把关键规则缩成一个可运行例子下面使用 Python 3 标准库表达算法规则保存为example.py后运行python3 example.py。它便于观察输入和输出不替代引擎中的 C、Shader 或模型实现。from math import floor from itertools import combinations def candidates(boxes): cells {} for ident, (x0, y0, x1, y1) in enumerate(boxes): for x in range(floor(x0), floor(x1) 1): for y in range(floor(y0), floor(y1) 1): cells.setdefault((x, y), []).append(ident) return {tuple(sorted(pair)) for ids in cells.values() for pair in combinations(ids, 2)} boxes [(0, 0, 1.2, 1.2), (0.9, 0.9, 1.5, 1.5), (4,4,5,5)] pairs candidates(boxes) assert pairs {(0, 1)} print(unique candidate pairs:, sorted(pairs))本例输出unique candidate pairs: [(0, 1)]这一步完成后再增加负坐标、极大包围盒和全部重叠场景。算法在理想分布里省下多少工作可以慢慢测先别让最普通的一次边界接触从系统里消失。适用范围未运行刚体引擎或统计帧时间网格例子只验证候选覆盖与去重没有声称完整碰撞检测通过。相关资料Unity Profiler手册
