土法炼钢兴趣小组的算法知识备份

游戏中的数学 (5) - 相交检测

目录

引言

相交检测 (Intersection Test) 是物理引擎的心脏。 它回答了“子弹是否击中敌人?”、“玩家是否站在地面上?”等问题。

1. 射线检测 (Raycasting)

射线由一个起点 \(O\) 和一个方向 \(D\) 定义:\(R(t) = O + D \cdot t\) (\(t \ge 0\))。

射线与球体 (Ray vs Sphere)

球体方程:\(|P - C|^2 = r^2\)。 将射线方程代入球体方程,会得到一个关于 \(t\)一元二次方程\[ at^2 + bt + c = 0 \]

Ray Sphere Intersection

通常我们只关心最小的正解 \(t\),那是最近的击中点。

射线与平面 (Ray vs Plane)

将射线代入平面方程 \(\vec{n} \cdot P + d = 0\)\[ \vec{n} \cdot (O + D \cdot t) + d = 0 \] 解出 \(t\): \[ t = \frac{-(\vec{n} \cdot O + d)}{\vec{n} \cdot D} \]

注意分母 \(\vec{n} \cdot D\): - 如果接近 0,说明射线与平面平行,无交点。 - 如果 > 0,说明射线从背面射出(通常不检测)。

2. AABB 包围盒 (Axis-Aligned Bounding Box)

这是最简单也是最快的碰撞检测形状。 它由两个点定义:\(min(x,y,z)\)\(max(x,y,z)\)。 “轴对齐”意味着盒子不能旋转,永远平行于世界坐标轴。

AABB vs AABB 检测

两个 AABB 相交,当且仅当它们在 X、Y、Z 三个轴上都重叠

bool Intersect(AABB a, AABB b) {
    return (a.min.x <= b.max.x && a.max.x >= b.min.x) &&
           (a.min.y <= b.max.y && a.max.y >= b.min.y) &&
           (a.min.z <= b.max.z && a.max.z >= b.min.z);
}

这是物理引擎中宽阶段 (Broad Phase) 碰撞检测的核心算法,用于快速剔除不可能相撞的物体。

3. 射线与 AABB (Slab Method)

将 AABB 看作是三组平行的平面(X轴一对,Y轴一对,Z轴一对)。 射线必须穿过所有三组“板 (Slab)”的重叠区域才算击中盒子。 这通常涉及计算 \(t_{min}\)\(t_{max}\) 在三个轴上的最大值和最小值。

总结

复杂的网格碰撞(Mesh Collider)通常太慢,游戏开发中会尽量用组合的 AABB 或球体来近似。


< 上一篇: 距离与检测 | 回到目录 | 下一篇: 运动学基础 >


By .