直线与平面求交

本页收录 RTR4 第 22.15～22.16 节的基础几何工具：二维直线/光线/线段求交（垂直点积法与无除法的早期拒绝法）、三维直线求交与异面直线最近点，以及三个平面的交点公式（可用于求 k-DOP 等平面围成凸体的角点）。这些在游戏中常用于射线检测、二维几何、碰撞与包围体构建。

二维：垂直点积法（22.15.1 节）

两直线 $\mathbf{r}_1(s)=\mathbf{o}_1+s\mathbf{d}_1$、$\mathbf{r}_2(t)=\mathbf{o}_2+t\mathbf{d}_2$。利用垂直向量 $\mathbf{a}\cdot\mathbf{a}^{\perp}=0$，两边分别点乘 $\mathbf{d}_2^{\perp}$、$\mathbf{d}_1^{\perp}$ 消去另一个参数：

$$s=\frac{(\mathbf{o}_2-\mathbf{o}_1)\cdot\mathbf{d}_2^{\perp}}{\mathbf{d}_1\cdot\mathbf{d}_2^{\perp}},\qquad t=\frac{(\mathbf{o}_1-\mathbf{o}_2)\cdot\mathbf{d}_1^{\perp}}{\mathbf{d}_2\cdot\mathbf{d}_1^{\perp}}$$

$\mathbf{d}_1\cdot\mathbf{d}_2^{\perp}=0$ 时平行。有效范围：直线任意；光线 $s,t\ge0$；方向归一化、长度 $l_1,l_2$ 的线段 $0\le s\le l_1$、$0\le t\le l_2$；若令 $\mathbf{d}_1=\mathbf{p}_2-\mathbf{p}_1$ 等端点差，则 $0\le s,t\le1$。

二维：无除法线段测试（Antonio）

令 $\mathbf{a}=\mathbf{q}_2-\mathbf{q}_1$，$\mathbf{b}=\mathbf{p}_2-\mathbf{p}_1$，$\mathbf{c}=\mathbf{p}_1-\mathbf{q}_1$，$d=\mathbf{c}\cdot\mathbf{a}^{\perp}$，$e=\mathbf{c}\cdot\mathbf{b}^{\perp}$，$f=\mathbf{a}\cdot\mathbf{b}^{\perp}$，则 $s=d/f$，$t=e/f$；$f=0$ 时共线。由于分母相同且不需要显式的 $s,t$，用比较代替除法：$f>0$ 时若 $d<0$ 或 $d>f$ 则不相交；$f<0$ 时若 $d>0$ 或 $d<f$ 则不相交；对 $e$ 同样测试，都通过则相交。比上一方法更快（更多比较和早期拒绝，避免除法），有整数版本源码。

三维直线（22.15.2 节）

三维中用叉积（$\mathbf{a}\times\mathbf{a}=\mathbf{0}$）代替垂直点积：两边减去原点后分别叉乘 $\mathbf{d}_2$、$\mathbf{d}_1$，再点乘 $\mathbf{d}_1\times\mathbf{d}_2$，得

$$s=\frac{\det(\mathbf{o}_2-\mathbf{o}_1,\;\mathbf{d}_2,\;\mathbf{d}_1\times\mathbf{d}_2)}{\lVert\mathbf{d}_1\times\mathbf{d}_2\rVert^2},\qquad t=\frac{\det(\mathbf{o}_2-\mathbf{o}_1,\;\mathbf{d}_1,\;\mathbf{d}_1\times\mathbf{d}_2)}{\lVert\mathbf{d}_1\times\mathbf{d}_2\rVert^2}$$

分母为 0 表示平行；两直线异面（不共面）时，$s$、$t$ 给出两条直线上最近点的位置。当作线段使用时检查 $0\le s\le l_1$、$0\le t\le l_2$。健壮处理特殊情况的完整解法与源码见 Rhodes。

三平面交点（22.16 节）

三个平面以单位法线 $\mathbf{n}_i$ 和平面上任一点 $\mathbf{p}_i$ 给出，唯一交点

$$\mathbf{p}=\frac{(\mathbf{p}_1\cdot\mathbf{n}_1)(\mathbf{n}_2\times\mathbf{n}_3)+(\mathbf{p}_2\cdot\mathbf{n}_2)(\mathbf{n}_3\times\mathbf{n}_1)+(\mathbf{p}_3\cdot\mathbf{n}_3)(\mathbf{n}_1\times\mathbf{n}_2)}{|\mathbf{n}_1\;\mathbf{n}_2\;\mathbf{n}_3|}$$

分母是三法线的行列式，有两个及以上平面平行时为零。平面以隐式形式 $\mathbf{n}_i\cdot\mathbf{x}+d_i=0$ 给出时，取离原点最近的点最便宜：沿法线从原点发射光线 $t\mathbf{n}_i$ 与平面相交得 $t=-d_i$，即 $\mathbf{p}_i=-d_i\mathbf{n}_i$（法线须为单位长度，$d_i$ 是原点到平面的负垂直距离）。用合适的平面组合代入，可求出由 k 个平面组成的 k-DOP 等凸多面体的角点。