Möller-Trumbore 算法

什么是Möller-Trumbore 算法

Möller-Trumbore 算法是一种快速求三角形与光线是否相交的算法，它是由Tomas Moller和Ben Trumbore于1997年在一篇题名为“Fast, Minimum Storage Ray/Triangle Intersection”的论文中介绍。

为什么要学Möller-Trumbore 算法

首先先看看正常我们求一个三角形和光线相交的过程。

tm01.png

1.这里的当光线与平面相交就有点p满足：
(p - p0) dot N = 0 (N是平面的法线) 同时 p = o + t * d;(o 是光线的起点, d是光线的方向, t是时间)。
只有当(p - p0) dot N = 0 才能满足p点在平面内 p - p0这个向量垂直于法线方向。

2.在求得平面上的点还得判断该点是否在三角形内。
也就是一般做法是需要判断光线是否于平面相交，在判断相交的点是否在三角形内。需要计算两个步骤。

有没有一种直接直接判断三角形是否与光线相交的方法呢？
这就是现在介绍的Möller-Trumbore 算法。

Möller-Trumbore 算法的核心思想是一步到位的计算出光线是否与三角形相交，主要利用到的知识点是三角形的重心坐标。
我们已知点P可以写成三角形三个顶点乘上某个系数相加的形式：

P = aA + uB + vC; 同时 1 <= a , u, v >= 0, a + u + v = 1

那么就可以写成

o + td = aA + uB + vC;

a = 1 - b - c

o + td = (1 - u - v)A + uB + vC; 
=> o + td =  A - uA - vA + uB + vC;
=> o + td =  A + (B - A)u  +  (C - A)v;
=> o - A = -td + (B-A)u + (C-A)v;

这样就有了三个未知数t ，b，c。

tm02.png

然后这里我们可以根据克莱姆法则(Cramer's rule)
E1 = (B - A) E2 = (C - A) T = (o - A)
得到一个M: [-D E1 E2]
C : [T]

klm.png

我们只需要替换C到对应M的列里就可以得到

mt : [T E1 E2]
t = mt / M
t = |T E1 E2 | / |-D E1 E2|

mu : [-D T E2]
u = mu / M
u = |-D T E2 | / |-D E1 E2|
mv : [-D E1 T]
v = mv / M
v = |-D E1 T | / |-D E1 E2|
然后将这三个变量整合起来得

tm03.png

在根据混合积公式得

tm04.png

tm05.png

这就完成了整个过程的推导，剩下的就是带入数据去判断即可。