光线求交测试

光线求交用于拾取、光线追踪、地面高度查询等。本页给出四类经典测试：光线-球（代数解与带早期拒绝的几何优化解）、光线-盒（平板法与光线斜率法）、光线-三角形（Möller-Trumbore，直接从顶点求重心坐标与距离）、光线-多边形（先求平面交点，再投影到二维做交叉数测试）。共同思路是先做便宜的拒绝测试、推迟除法与开方、必要时降维。

光线-球（22.6 节）

球心 $\mathbf{c}$、半径 $r$，把光线代入 $\lVert\mathbf{p}-\mathbf{c}\rVert-r=0$，利用 $\mathbf{d}\cdot\mathbf{d}=1$ 得

$$t^2+2bt+c=0,\quad b=\mathbf{d}\cdot(\mathbf{o}-\mathbf{c}),\; c=(\mathbf{o}-\mathbf{c})\cdot(\mathbf{o}-\mathbf{c})-r^2,\quad t=-b\pm\sqrt{b^2-c}$$

$b^2-c<0$ 则错过，可省去开方；否则取最小正根。（网站上的碰撞检测章节给出了数值更稳定的解法。）

几何优化解：

1. $\mathbf{l}=\mathbf{c}-\mathbf{o}$，$l^2=\mathbf{l}\cdot\mathbf{l}$；$l^2<r^2$ 表示原点在球内，必然相交（只需布尔结果时可退出）。
2. $s=\mathbf{l}\cdot\mathbf{d}$；若 $s<0$ 且原点在球外，球在光线背后，拒绝。
3. $m^2=l^2-s^2$；若 $m^2>r^2$ 必然错过，拒绝。此后保证相交。
4. $q=\sqrt{r^2-m^2}$，交点距离 $t=s\pm q$：原点在球外取 $s-q$，在球内取 $s+q$。

完整执行时运算量与代数解相当，但拒绝发生得早得多，平均成本更低。（预存 $r^2$ 看似优化，实际可能因多访问内存而更慢。）圆柱、圆锥、椭球、胶囊、菱形体也有类似的几何优化方法。

光线-盒（22.7 节）

平板法（Kay 与 Kajiya，源自 Cyrus-Beck 裁剪）：把盒看成三个平板，对每个平板求进入与离开的 $t_i^{min}$、$t_i^{max}$，

$$t^{min}=\max(t_u^{min},t_v^{min},t_w^{min}),\qquad t^{max}=\min(t_u^{max},t_v^{max},t_w^{max})$$

$t^{min}\le t^{max}$ 则直线与盒相交（最远的"进入"不晚于最近的"离开"）；再要求 $t^{max}\ge0$ 才是光线（盒不在背后）。OBB 实现要点：$\mathbf{p}=\mathbf{a}^c-\mathbf{o}$，每条轴算 $e=\mathbf{a}^i\cdot\mathbf{p}$、$f=\mathbf{a}^i\cdot\mathbf{d}$；$|f|>\epsilon$（约 $10^{-20}$，仅防除法溢出）时 $t_{1,2}=(e\pm h_i)/f$ 并更新区间，区间为空或 $t^{max}<0$ 立即拒绝；光线平行于平板时若 $-e-h_i>0$ 或 $-e+h_i<0$ 则在平板外，拒绝。最后返回 $t^{min}>0$ 时的 $t^{min}$，否则 $t^{max}$。

优化：预先计算 $1/f$ 用乘法代替除法；循环内尽早与当前最近距离 $l$ 比较；AABB 时 $e=p_i$、$f=d_i$，直接用 $\mathbf{a}^{min}$、$\mathbf{a}^{max}$；允许除以零并正确解读结果可省掉平行判断；某些 NVIDIA 架构可用单条 GPU 指令完成"最小值中的最大值"。平板法可推广到 k-DOP、视锥和任意凸多面体。用 SAT 也能推导光线-盒测试，但得不到交点距离。

光线斜率法（Eisemann 等，2007）：在三个二维投影中测试，每个投影中由两个盒角定义光线"看到"的极值范围（类似轮廓边），光线斜率必须介于原点到这两点的斜率之间，三个投影都通过才命中。部分比较项只依赖光线，预计算后可高效测试大量盒；可只返回是否命中，也可稍加成本返回距离。

光线-三角形（22.8 节，Möller-Trumbore）

不需要预存三角形法线（对网格省内存，对动态几何免于每帧重算平面方程）。三角形上点 $\mathbf{f}(u,v)=(1-u-v)\mathbf{p}_0+u\mathbf{p}_1+v\mathbf{p}_2$，$(u,v)$ 为重心坐标（第三个权重 $w=1-u-v$，可用于纹理坐标、法线、颜色插值）。令 $\mathbf{o}+t\mathbf{d}=\mathbf{f}(u,v)$，记 $\mathbf{e}_1=\mathbf{p}_1-\mathbf{p}_0$，$\mathbf{e}_2=\mathbf{p}_2-\mathbf{p}_0$，$\mathbf{s}=\mathbf{o}-\mathbf{p}_0$，得线性方程组 $(-\mathbf{d}\;\;\mathbf{e}_1\;\;\mathbf{e}_2)(t,u,v)^T=\mathbf{s}$。几何上相当于把三角形平移到原点并变换为单位三角形、光线方向对齐 x 轴。由克莱姆法则与混合积恒等式：

$$\begin{pmatrix}t\\u\\v\end{pmatrix}=\frac{1}{\mathbf{q}\cdot\mathbf{e}_1}\begin{pmatrix}\mathbf{r}\cdot\mathbf{e}_2\\ \mathbf{q}\cdot\mathbf{s}\\ \mathbf{r}\cdot\mathbf{d}\end{pmatrix},\qquad \mathbf{q}=\mathbf{d}\times\mathbf{e}_2,\;\mathbf{r}=\mathbf{s}\times\mathbf{e}_1$$

实现顺序：算 $a=\mathbf{e}_1\cdot\mathbf{q}$（矩阵行列式），$|a|<\epsilon$（正常浮点条件下 $10^{-5}$ 即可）拒绝；$f=1/a$；$u=f(\mathbf{s}\cdot\mathbf{q})$，$u<0$ 拒绝；$v=f(\mathbf{d}\cdot\mathbf{r})$，$v<0$ 或 $u+v>1$ 拒绝；最后 $t=f(\mathbf{e}_2\cdot\mathbf{r})$。所有计算延迟到需要时；单面版本剔除行列式为负的三角形，可把唯一的除法推迟到确认相交之后。

变体与注意：

• 若可多存数据，存 $\mathbf{p}_0,\mathbf{e}_1,\mathbf{e}_2$ 和未归一化法线 $\mathbf{n}=\mathbf{e}_1\times\mathbf{e}_2$，令 $\mathbf{m}=\mathbf{s}\times\mathbf{d}$，则 $(t,u,v)=\frac{1}{-\mathbf{n}\cdot\mathbf{d}}(\mathbf{n}\cdot\mathbf{s},\;\mathbf{m}\cdot\mathbf{e}_2,\;-\mathbf{m}\cdot\mathbf{e}_1)$，主要省一次叉积；是否更快取决于额外内存访问，需实测。
• 直接在三维中操作的光线-三角形测试大多计算上等价，可用 SSE 一次测 4 条光线。
• 这类测试可能把恰好打在边或顶点上的光线判为未命中，光线可能从共享边穿过网格；Woop 等给出边与顶点都"水密"的测试，性能略低。
• 另一类方法先求与平面交点，再投影到使三角形面积最大的坐标平面做二维包含测试；不同 CPU、编译器、命中率下没有单一最佳测试。

光线-多边形（22.9 节）

多边形平面 $\mathbf{n}_p\cdot\mathbf{x}+d_p=0$，交点参数

$$t=\frac{-d_p-\mathbf{n}_p\cdot\mathbf{o}}{\mathbf{n}_p\cdot\mathbf{d}}$$

$|\mathbf{n}_p\cdot\mathbf{d}|<\epsilon$ 视为平行。然后丢弃法线绝对值最大的分量，把顶点和交点投影到对应坐标平面（避免投影成零面积），该分量可预存，拓扑在投影下保持（前提是多边形确实平坦）。

交叉数测试（Jordan 曲线定理，又称奇偶测试）：从点出发沿 +x 方向发射射线，与多边形边相交奇数次则在内部。对自交多边形，有些视觉上在内部的区域会被判为外部；若要都算内部，需计算环绕数 (winding number)。实现时把点平移到原点：边两端 y 同号则不可能相交；否则若两端 x 都为正则计数，若 x 异号则求与 x 轴交点判断正负。射线恰好经过顶点时可能被计两次，约定 $y\ge0$ 的顶点视为在射线上方即可避免。高效版本用符号消去代替除法求截距；对顶点很多的多边形，先比较 x 坐标差再做判断可能更快。

重心坐标可推广到凸和凹多边形；由直线段与贝塞尔曲线组成的闭合轮廓也可用类似的交叉计数，并可在像素着色器中用于文本渲染。

GEA 的视角：碰撞查询中的射线（卷 II 14.3.7.1）

• GEA 的射线投射把"射线"定义为有向线段：$p(t)=p_0+t\mathbf d$，$t\in[0,1]$，终点 $p_1=p_0+\mathbf d$。接触点用唯一的 $t$ 值描述，多数 API 直接返回 $t$。这与本页各算法求出的参数 $t$ 是同一个量，只是 GEA 把 $t$ 限制在线段范围内，长度就是查询距离。
• 引擎 API 通常返回最早接触（$t$ 最小），有的返回线段穿过的全部 collidable。每个接触包含 $t$、被击中对象的 id，可能还有法线等表面属性。射线推广到移动整个凸形状就是形状投射，此时 $t$ 只描述形状中心的位置，必须另外返回接触点。详见 碰撞查询。

PBRT 的视角：离线光线追踪器里的形状求交（PBRT 4e 第 6 章）

上文 RTR4 和 GEA 讲的是单个求交算法；PBRT 讲的是一个离线渲染器怎样把它们组织成统一的 Shape 接口，并且把浮点误差当成算法的一部分（误差部分见 浮点误差与鲁棒光线求交）。

Shape 接口（6.1）

• 每个形状必须提供：渲染空间 AABB Bounds()、法线方向锥 NormalBounds()（用于判断发光形状照不到某点）、Intersect()（返回 $(0,t_{max})$ 内最近交点及 SurfaceInteraction）、谓词 IntersectP()（阴影光线用，更快）、Area()、两种 Sample()/PDF()（按面积、按参考点立体角，见 形状采样）。
• $t$ 在变换下不变：物体空间射线 $\mathbf o_o=\mathbf M\mathbf o_r,\ \mathbf d_o=\mathbf M\mathbf d_r$，交点 $\mathbf p_o=\mathbf o_o+t\mathbf d_o$，两边左乘 $\mathbf M^{-1}$ 得 $\mathbf p_r=\mathbf o_r+t\mathbf d_r$。前提是变换后不归一化方向，所以 pbrt 刻意不归一化物体空间射线。
• 不支持单面形状：光栅化器用背面剔除提速，但光线追踪通常要先求交才知道法线朝向，收益小；而且不封闭的单面物体会让"从光源到点"和"从点到光源"两条阴影光线结论不一致，物理上不自洽。这与实时管线默认开启背面剔除的做法相反（见 剔除技术）。

光线-AABB 平板法（6.1.2）

与上文 22.7 节相同的平板法，PBRT 补充了两个工程细节：

• 不检查 $d_x=0$：1/d_x 得到 $\pm\infty$，算法仍正确；原点恰在平板面上又平行时会出现 $0\cdot\infty=$ NaN，更新 $t_0,t_1$ 的比较写成"NaN 时保持不变"的形式（任何与 NaN 的比较都为假）。
• 预先算好方向倒数和各分量符号的版本可以直接选出近/远平面，省掉依赖计算结果的比较；BVH 遍历中这一优化让总渲染时间快约 15%。

二次曲面：球、圆柱、圆盘（6.2–6.4）

• 球心在原点、半径 $r$：$at^2+bt+c=0$，$a=|\mathbf d|^2,\ b=2(\mathbf d\cdot\mathbf o),\ c=|\mathbf o|^2-r^2$（式 6.3）；圆柱去掉 $z$ 分量；圆盘直接 $t=(h-o_z)/d_z$，$d_z=0$ 时判为不相交。系数用区间类 Interval 计算，判别式用 6.8.3 的精确形式。
• 部分球/圆柱用 $z_{min},z_{max},\phi_{max}$ 裁剪：$\phi=\operatorname{atan2}(y,x)$ 映射到 $[0,2\pi)$；$t_0$ 被裁掉再试 $t_1$。只有用户确实裁剪了 $z$ 才做 $z$ 测试，否则舍入会误裁。
• 拆成 BasicIntersect()（只算 $t$、物体空间点和 $\phi$）与 InteractionFromIntersection()（构造完整几何）：IntersectP() 只用前者；GPU 路径先在所有形状中找到最近交点再构造 SurfaceInteraction，正好对应。
• 曲面微分几何：球的 $\partial p/\partial u=(-\phi_{max}y,\ \phi_{max}x,\ 0)$，$\partial p/\partial v=(\theta_{max}-\theta_{min})(z\cos\phi,\ z\sin\phi,\ -r\sin\theta)$；法线导数用 Weingarten 方程（见 参数曲面与贝塞尔面片），供第 10 章的纹理抗锯齿使用。

三角形：Woop 水密求交（6.5.3）

与上文 Möller-Trumbore 的对照：

其他细节：先检测退化三角形（变换后的舍入可能让退化三角形"变得不退化"）；先用未归一化的 $\sum e_iz_i$ 与 $t_{max}\sum e_i$ 比较，确定有效后才做除法（式中 $\sum e_i$ 为负时不等号反向）；重心坐标 $b_i=e_i/\sum e_j$。几何法线用边向量 dp02 × dp12 而不是 $\partial p/\partial u\times\partial p/\partial v$，以免坏的 UV 参数化翻转法线；与插值着色法线不在同一侧时，翻转的是几何法线。

双线性面片与曲线（6.6–6.7）

• 双线性面片（四个顶点不必共面，双直纹曲面）用 Reshetov (2019) 的单精度算法：固定 $u$ 得到一族直线 $f_u(v)$，射线与这族直线的距离为 0 是关于 $u$ 的二次方程，所以最多两个交点；对 $[0,1]$ 内的根再用两直线最近点公式求 $v,t$（含行列式）。
• 曲线（三次贝塞尔 + 线性插值宽度）：用 LookAt 把曲线变到射线坐标系，"上"方向取垂直于射线和首末控制点连线的方向以收紧包围盒；递归二分（变差缩减性保证细分后更直），到最大深度后用首末点线段近似，求最近点参数 $w=\frac{(\mathbf p-\mathbf p_0)\cdot(\mathbf p_3-\mathbf p_0)}{\|\mathbf p_3-\mathbf p_0\|^2}$，再判断距离是否小于半宽；用过端点的切线垂线作边函数，避免相邻段重复计数。详见 毛发渲染。

原书问题

• 6.1.4 物体空间射线的下标：在线版写的是"物体空间射线 $r_o$ 的原点为 $\mathbf M\mathbf o_o$、方向为 $\mathbf M\mathbf d_o$"。本页解码该处 SVG 字形（下标为 LATINMODERNMAIN-6F 即字母 o），确认原文如此；按上下文应为 $\mathbf M\mathbf o_r$、$\mathbf M\mathbf d_r$（由渲染空间量变换而来），紧接的推导也只有这样才成立。来源：https://pbr-book.org/4ed/Shapes/Basic_Shape_Interface#IntersectionCoordinateSpaces
• 6.5.3 边函数符号与图注矛盾：正文说"边函数对直线右侧的点为正、左侧为负"，图 6.14 的图注却说左侧为正。按式 6.5 $e(\mathbf p)=(p_{1x}-p_{0x})(p_y-p_{0y})-(p_x-p_{0x})(p_{1y}-p_{0y})$ 验算：取 $\mathbf p_0=(0,0),\ \mathbf p_1=(1,0),\ \mathbf p=(0,1)$（在有向线左侧）得 $e=1>0$，图注正确、正文写反（算法只要求三者同号，不受影响）。来源：https://pbr-book.org/4ed/Shapes/Triangle_Meshes#Ray–TriangleIntersection
• 6.5.1 习题引用编号：正文"参见章末习题 6.8.8"的链接指向的是第一道习题（在渲染空间直接求交二次曲面，即习题 6.1）；6.8.8 是"讨论"小节的编号，在线版的显示编号有误。