Games101，Lecture 13（光线与物体求交，引入包围盒）

光线追踪

光线追踪更多的用于离线应用。
因为一帧一般需要一万个CPU小时。

原理

由摄像机发出感应光线，判断与物体相交的点是否可以与。光源连线（无遮挡物）。

如何判断光线与物体有交点，是管线追踪中较难的部分。

光线与物体求交

1.与隐式表示的曲面求交

通过 光线方程 与 曲面方程求解 是否有根 判断光线与曲面是否有交点。

2、与显式表面（三角形）求交

补充：可以通过光线与三角形求交，还可以判断光线是否在三角形内。

光线与三角形求交可以分解成两个物体：

1. 光线与平面相交
2. 判定交点是否在三角形内

如何判断点在平面内

平面用一个向量，和一个点 P ‘ P‘ P‘表示。若p点在面内，则 ( p − p ′ ) ∗ N = 0 (p-p')*N = 0 (p−p′)∗N=0。
将 P = O + t D P=O+tD P=O+tD带入式中 ⇒ \Rightarrow ⇒

一种更为简便的方法（Moller Trumbore算法）

将点在三角形内公式与直线方程直接联系得

求解：

解得 t , b 1 , b 2 t,b_1,b_2 t,b1​,b2​,若t为正，b1>0,b2>0,b1+b2<1。则点在三角形内

计算：
原 式 ⇒ t ∗ ( − D ⃗ ) + b 1 ∗ ( P 1 ⃗ − P 0 ⃗ ) + b 2 ∗ ( P 2 ⃗ − P 0 ⃗ ) = O ⃗ − P 0 ⃗ 原式\Rightarrow t*(-\vec D) + b_1*(\vec {P_1} - \vec {P_0}) + b_2*(\vec {P_2} - \vec {P_0}) = \vec O - \vec {P_0} 原式⇒t∗(−D )+b1​∗(P1​ ​−P0​ ​)+b2​∗(P2​ ​−P0​ ​)=O −P0​ ​
将 E 1 , E 2 , S E_1,E_2,S E1​,E2​,S代入得
原 式 ⇒ [ − D ⃗ , E 1 ⃗ , E 2 ⃗ ] [ t b 1 b 2 ] = S ⃗ 原式\Rightarrow \begin{bmatrix} -\vec D ,& \vec{E_1}, & \vec{E_2} \end{bmatrix} \begin{bmatrix} t \\ b_1 \\ b_2 \end{bmatrix}= \vec S 原式⇒[−D ,​E1​ ​,​E2​ ​​]⎣⎡​tb1​b2​​⎦⎤​=S
之后应该是对 [ − D ⃗ , E 1 ⃗ , E 2 ⃗ ] \begin{bmatrix} -\vec D ,& \vec{E_1}, & \vec{E_2} \end{bmatrix} [−D ,​E1​ ​,​E2​ ​​]求逆，至于求逆后为什么会简化为上面的式子，我就不知道了！！

算法复杂度：

光线与表面求交加速方法

如果一条光线和每个三角形求交，那么太慢了，Cost = 光线数*三角形数*求交复杂度。

包围盒

使用包围盒（完全）包裹某个物体，如果光线和包围盒都没有交点，那么更不可能与包围盒内的三角形相交。

Axis-Aligned Bounding Box(轴对齐包围盒)

包围盒以x，y，z轴为法线定义。

判定光线和盒子求交

对于一条光线， P ( x , y , z ) = O ( x , y , z ) + d ( x ′ , y ′ , z ′ ) ∗ t ; P(x,y,z) = O(x,y,z)+d(x',y',z')*t; P(x,y,z)=O(x,y,z)+d(x′,y′,z′)∗t;
定能求出 x = x 0 , x = x 1 x=x_0,x=x_1 x=x0​,x=x1​时的 t m i n , t m a x t_{min},t_{max} tmin​,tmax​，y，z轴同理。（t可能为负）

1. 求出x，y，z轴分别对应的 t m i n , t m a x t_{min},t_{max} tmin​,tmax​
2. 求出三个 t m i n t_{min} tmin​的最大值 t e n t e r t_{enter} tenter​，三个 t m a x t_{max} tmax​的最小值 t e x i t t_{exit} texit​。
3. 如果 t e n t e r < t e x i t t_{enter} < t_{exit} tenter​<texit​，则光线可能通过包围盒。
4. 特别判断：
   如果 t e x i t < 0 t_{exit}<0 texit​<0,物体在光线背后。无交点。
   如果 t e x i t > 0 , t e n t e r < 0 t_{exit}>0,t_{enter}<0 texit​>0,tenter​<0,光线在盒子里面，一定有交点。
   综上：当且仅当 t e n t e r < t e x i t & & t e x i t > 0 t_{enter} < t_{exit} \&\& t_{exit}>0 tenter​<texit​&&texit​>0 则一定有交点。

如何理解：

• 当且仅当光线进入所有轴方向，光线才会进入包围盒。
• 当且仅当光线离开任何一个轴方向，光线就会离开包围盒。

下一节课再讲解对光线与表面求交的其他更块的算法。