求解射线与三角形的交点,在光线追踪、碰撞检测、目标拾取等场景中经常使用,是计算机图形学中最基本的操作。下面介绍常用的求解射线与三角形交点的算法。
问题定义
求解射线与三角形交点示意图如图1所示。
射线的参数方程如下,其中O是射线的起点,D是射线的方向,t是常数。
$$O+Dt$$
该方程的含义是一个点从起点O开始,沿着方向D移动任意长度,得到终点R,根据t值的不同,得到的R值也不同,所有这些不同的R值便构成了整条射线,比如下面的射线,起点是P0,方向是u,p0 + tu也就构成了整条射线。
三角形的参数方程如下,其中$V_0$,$V_1$和$V_2$是三角形的三个点,$u, v$是$V_1$和$V_2$的权重,$1-u-v$是$V_0$的权重,并且满足$u>=0, v >= 0,u+v<=1$。
$$(1-u-v)V_0+uV_1+vV_2$$
直观方法
求解射线与三角形的交点最直观的方法如下:
- 判断射线是否与平面相交
- 判断点是否在三角形内
但该方法需要额外计算三角形所在平面,效率不高。
Moller-Trumbore方法(Journal of Graphic Tools, 1997)
Moller-Trumbore方法中,求射线与三角形的交点即求解如下方程:
$$O+Dt=(1-u-v)V_0+uV_1+vV_2$$
其中t,u,v是未知数,其他都是已知的。
移项并整理,将t,u,v提取出来作为未知数,得到下面的线性方程组:
$$\begin{bmatrix}
-D& V_1-V_0 &V_2-V_0
\end{bmatrix}\begin{bmatrix}
t\u\v
\end{bmatrix}=O-V_0$$
现在开始解这个方程组,这里要用到两个知识点,一是克莱姆法则,二是向量的混合积。
令$E_1 = V_1 - V_0,E_2 = V_2 - V_0,T = O - V_0$上式可以改写成:
$$\begin{bmatrix}
-D& E_1 & E_2
\end{bmatrix}\begin{bmatrix}
t\u\v
\end{bmatrix}=T$$
根据克莱姆法则,可得到t,u,v的解为:
$$
\begin{bmatrix}
t\u\v
\end{bmatrix}
=\frac{1}{\begin{vmatrix}
-D & E_1 & E_2
\end{vmatrix} }
\begin{vmatrix}
T&E_1&E_2\
-D& T& E_2\
-D & E_1& T
\end{vmatrix}
$$
根据混合积公式:
$$\begin{vmatrix}
a&b&c
\end{vmatrix}
=a\times{b}\cdot{c}$$
上式改写为:
$$
\begin{bmatrix}
t\u\v
\end{bmatrix}
=\frac{1}{\begin{bmatrix}
-D \times E_2 \cdot E_1
\end{bmatrix} }
\begin{vmatrix}
T \times E_1 \cdot E_2\
D \times E_2 \cdot T\
T \times E_1 \cdot D
\end{vmatrix}
$$
令$P=D \times E_2$,$Q=T \times E_1$,得到最终的公式:
$$\begin{bmatrix}
t\u\v
\end{bmatrix}
=\frac{1}{\begin{bmatrix}
P \cdot E_1
\end{bmatrix} }
\begin{vmatrix}
Q \cdot E_2\
P \cdot T\
Q \cdot D
\end{vmatrix}
$$
之所以提炼出P和Q是为了避免重复计算。
参考链接
- 射线和三角形的相交检测(ray triangle intersection test),by zdd.
- 光线-三角形求交测试算法[译], by PKUWWT.
- 克莱姆法则,by wikipedia.
- 混合积,by wikipedia.
- 重心坐标,by wikipedia.
- 重心坐标(Barycentric coordinates),by 杨超.