有向边界框间最短距离计算方法问询

一、基于分离轴定理（SAT）的距离计算 #

SAT原本用于碰撞检测，扩展后可直接计算最短分离距离：

• 核心逻辑：两个凸体不碰撞的充要条件是存在一条分离轴，两物体在该轴上的投影无重叠。所有候选分离轴中，投影间距最小的那个值就是两OBB的最短距离；若所有轴投影都重叠，则碰撞（距离为0）。
• 3D OBB的候选分离轴共15个：
  • 两个OBB各自的3个主轴（共6个）
  • 两个OBB主轴两两叉乘得到的非零向量（3×3=9个）

计算步骤 #

1. 对每个候选轴，快速计算两OBB在该轴上的投影区间：
   不用遍历8个顶点，利用OBB的中心、主轴和半长计算：
   设OBB A的中心为C_A，主轴方向向量为u1, u2, u3，半长为h1, h2, h3，轴为n，则：

   proj_extent_A = h1 * abs(dot(u1, n)) + h2 * abs(dot(u2, n)) + h3 * abs(dot(u3, n))
   proj_min_A = dot(C_A, n) - proj_extent_A
   proj_max_A = dot(C_A, n) + proj_extent_A
   

   同理计算OBB B的proj_min_B和proj_max_B。
2. 判断投影区间是否重叠：
   • 若重叠，跳过该轴；
   • 若不重叠，计算间距distance = max(proj_min_A, proj_min_B) - min(proj_max_A, proj_max_B)（取正值），记录当前最小间距。
3. 遍历完所有轴后，最小间距即为最短距离；若所有轴都重叠，距离为0。

优化点 #

• 提前缓存OBB的主轴、半长参数（车辆作为刚体，主轴方向和半长通常固定），减少重复计算。

二、基于GJK算法的距离计算 #

GJK是通用的凸体碰撞检测与距离计算算法，适合OBB这类规则凸体：

• 核心逻辑：通过迭代构建单纯形（3D中为四面体），逼近两物体闵可夫斯基差的原点。若原点在闵可夫斯基差内部，说明碰撞；否则，找到闵可夫斯基差上离原点最近的点，其模长就是两OBB的最短距离。

针对OBB的优化 #

• 支持点快速计算：给定方向d，OBB的支持点可通过主轴直接推导：

  support_point = C ± h1*sign(dot(u1, d))*u1 ± h2*sign(dot(u2, d))*u2 ± h3*sign(dot(u3, d))*u3
  

  无需遍历8个顶点，大幅提升效率。
• 连续帧迭代优化：利用上一帧的单纯形作为初始值，减少当前帧的迭代次数，适合移动车辆的实时追踪。

三、方法选择建议 #

• SAT实现直观，代码量小，适合对实时性要求适中的车辆模拟场景，同时能兼顾碰撞检测和距离计算。
• GJK通用性更强，若后续需要扩展到其他凸碰撞体（如带凸形外壳的车辆），或两OBB距离较远时，迭代次数少、效率更高。
• 两种方法都能满足车辆实时计算需求，可根据实现复杂度和后续扩展需求选择。

四、实时追踪额外优化 #

• 优先做快速预检测：先用轴对齐边界框（AABB）判断两OBB是否可能重叠，若不可能，直接跳过精细计算；
• 连续帧复用方向：用上一帧的最短距离方向作为SAT的优先检测轴，或GJK的初始搜索方向，减少计算量；
• 碰撞优先判断：若检测到碰撞，直接返回距离0，无需继续计算最短距离。

内容的提问来源于stack exchange，提问作者SeungHo Jang