光线追踪

在光线追踪中，假设相机是个点而不是个矩形。
然后将每个像素和相机相连并延长这条线，作为光线，这条线被称为“眼睛光线”。
这根光线会和场景中的物体相交，记录下最近的交点。
将交点与光源相连，判断能否被光源直接照到。
使用着色器进行着色，写入该像素点的颜色值。

Whitted风格光线追踪

当光线与物体相交时，计算该光线的反射光、折射光。同时不断递归反射光、折射光，计算每一个反射光、折射光与场景的交点、产生的反射光、折射光，并与光源相连，判断是否能被光源直接照射到。然后使用着色器进行着色，并将最后将得到的所有颜色值相加。

光线与模型的交点

定义光线

对于任意一条光线，可以用\(r(t)=o+td (0 \le t < \infty \)来表示。
其中r为光线，t为时间，o为光源，d为光线方向。

光线与球体的交点

球体p的定义\((p-c)^2-R^2=0\)

将光线带入球体的公式中：\((o+td-c)^2-R^2=0\)
\(a t^2+b t+c=0, \text { where }\)
\(a=\mathbf{d} \cdot \mathbf{d}\)
\(b=2(\mathbf{o}-\mathbf{c}) \cdot \mathbf{d}\)
\(c=(\mathbf{o}-\mathbf{c}) \cdot(\mathbf{o}-\mathbf{c})-R^2\)
\(t=\frac{-b \pm \sqrt{b^2-4 a c}}{2 a}\)

利用△可知与球体的交点个数，用求根公式即可得出交点

光线与隐式表面的交点

定义隐式表面p：\(f(p)=0\)
将光线带入公式\(f(o+td)=0\)
解出方程的根即可

光线与显式表面的交点

求光线与显式表面的交点，即为求光线与三角形求交点。

定义平面：

定义平面的法线N，再定义平面上任意一点\(p^{\prime}\)，如果有一点在平面内，这个点与p'的连线与法线垂直。

即平面p： \((p-p') \cdot N=0\)

令\(p=r(t)\)
\(\left(\mathbf{p}-\mathbf{p}^{\prime}\right) \cdot \mathbf{N}=\left(\mathbf{o}+t \mathbf{d}-\mathbf{p}^{\prime}\right) \cdot \mathbf{N}=0\)

即可求出t：
\(t=\frac{\left(\mathbf{p}^{\prime}-\mathbf{o}\right) \cdot \mathbf{N}}{\mathbf{d} \cdot \mathbf{N}}\)
\(0 \leq t<\infty\)

Möller Trumbore算法

该算法可以快速求出光线在三角形内的交点。

如果光线与平面的交点在三角形内，那这一点也就能够用重心坐标表示，即：
\(\overrightarrow{\mathbf{O}}+t \overrightarrow{\mathbf{D}}=\left(1-b_1-b_2\right) \overrightarrow{\mathbf{P}}_0+b_1 \overrightarrow{\mathbf{P}}_1+b_2 \overrightarrow{\mathbf{P}}_2\)

令：
\(\begin{aligned}
& \overrightarrow{\mathbf{E}}_1=\overrightarrow{\mathbf{P}}_1-\overrightarrow{\mathbf{P}}_0 \\
& \overrightarrow{\mathbf{E}}_2=\overrightarrow{\mathbf{P}}_2-\overrightarrow{\mathbf{P}}_0 \\
& \overrightarrow{\mathbf{S}}=\overrightarrow{\mathbf{O}}-\overrightarrow{\mathbf{P}}_0 \\
& \overrightarrow{\mathbf{S}}_1=\overrightarrow{\mathbf{D}} \times \overrightarrow{\mathbf{E}}_2 \\
& \overrightarrow{\mathbf{S}}_2=\overrightarrow{\mathbf{S}} \times \overrightarrow{\mathbf{E}}_1
\end{aligned}\)

利用Cramer 法则：
\(\left[\begin{array}{l}
t \\
b_1 \\
b_2
\end{array}\right]=\frac{1}{\overrightarrow{\mathbf{S}}_1 \cdot \overrightarrow{\mathbf{E}}_1}\left[\begin{array}{c}
\overrightarrow{\mathbf{S}}_2 \cdot \overrightarrow{\mathbf{E}}_2 \\
\overrightarrow{\mathbf{S}}_1 \cdot \overrightarrow{\mathbf{S}} \\
\overrightarrow{\mathbf{S}}_2 \cdot \overrightarrow{\mathbf{D}}
\end{array}\right]\)

即可求出上述方程的解，其算力开销非常低。

加速算法

包围盒

使用包围盒将每一个模型包围起来，如果光线与包围盒相交，才计算光线和包围盒内模型的每个三角形是否相交。

将包围和理解为3组对面形成的交集：

轴对齐包围盒AABB

Axis-Aligned Bounding Box，每个面都和坐标轴的面平行。

在二维中，判断一个长方形和一条直线是否有交集，可以先求出其和线x0，x1的两个交点，再求出和线y0，y1的两个交点

因为当光线进入到所有的面，才能确定光进入到包围盒中，而当光线离开任意一个面，即为离开包围盒。所以求出其中最大的\(t_{min}\)和最小的\(t_{max}\)即为光线实际进入和离开盒子的时间。

即\(t_{enter}=max(t_{min}),t_{exit}=min(t_{max})\)。在三维空间中同理。

如果\(t_{enter}<t_{exit}\)，即为光线经过了包围盒（光线在包围盒中待了一段时间）。

但是光线是射线，不是直线，所以当\(t_{exit}<0\)，说明物体在光线的背后，即不可能有交点。
当\(t_{exit}>=0,t_{enter}<0\)，即光线的起点在包围盒内部。

所以当且仅当\(t_{enter}<t_{exit},t_{exit}\ge0\)时，光线穿过包围盒。

计算光线与面何时相交：
\(t=\frac{\left(\mathbf{p}^{\prime}-\mathbf{o}\right) \cdot \mathbf{N}}{\mathbf{d} \cdot \mathbf{N}}\)
而这里的面是与坐标轴平面平行的，所以可以简化运算：
对于yz平面平行，即为垂直于x轴：
\(t=\frac{\mathbf{p}_x^{\prime}-\mathbf{o}_x}{\mathbf{d}_x}\)