一文读懂射线与三角形相交算法Moller-Trumbore算法

一文读懂射线与三角形相交算法Moller-Trumbore算法

本文首发于oakchina.cn,文章PDF下载

作者:OAK人工智能俱乐部成员@阮培源(微信:阮PY)

本文目的

在计算机视觉中,经常需要判断一条射线是否与“三角形”相交。射线的起点o 是相机镜头O 在像平面的2D 点,射线的另外一点p 是“世界坐标系中的某个3D 点P 通过投影后在像平面上的2D 点”。“三角形”是3D 物体在像平面上“某个需求渲染表面的三角形小区域”。如果p 在三角形上,意味着相机可以看见3D 物体上的点P,该三角形需要被渲染。

那么,如何判断射线是否与三角形相交呢?本文就是来阐述该问题。

1、三角形ABC 内的点P 的性质

对于三角形ABC 内的任意一点P,学过线性代数和向量加法【两个向量相加等于两个向量组成的平行四边形的对角线向量】的就知道, 向量AP 、AB 、AC 线性相关。

向量AP 、AB 、AC 线性相关且点P 在三角形ABC 之内,可以写为下面形式【P 在三角形内,意味这0 <= u, v <= 1, u+v <= 1 】:

注意: 如果P 点不在三角形内, 那么是没法写为上面的向量相加的方程, 且满足0 <=u, v<= 1 和u+v <= 1 的约束条件的。

上面公式可以拆开写为:

得到:

这也是点P 的表示方法:点P 可以表示为点A、B、C 分别乘以某个因子,然后相加。这里有约束条件: 0 <= u, v <= 1 且u+v <= 1 。

总结:如果点P 在三角形内,那么P 一定能写为P = (1 – u – v ) A + u B + v C 的形式。

重心坐标: 当把ABC 看成坐标系,始于A 点,基为: 向量AB 和向量AC 。这个坐标系叫做重心坐标系(barycentric,bary- 重的)。在重心坐标系中,有方程:

继续写:

甚至我们还可以把它写成矩阵形式:

实际上,我们可以看作是在寻找向量(u, v, 1) 同时垂直于向量

和向量

这不就是叉乘么?同时这给了我们一个有了P 点,求u 和v 的思路。

xvector = (B_x - A_x, C_x - A_x, A_x - P_x)
yvector = (B_y - A_y, C_y - A_y, A_y - P_y)
W = xvector 叉乘yvector ; 注意: 这里W 是向量[u, v, 1],W 在x- y- z 坐标系中的坐标值为[u, v, 1]

重点来了: 因为我们讨论的是二维的三角形, 如果W 的z 分量不等于1 则说明P 点不在三角形内。

因为我们的计算中涉及到浮点数,可能W 的z 分量不会一定等于1.0 。
令W 的三个分量是(a, b, c),我们代入原式子:

2、三角形Möller-Trumbore 算法(下文简称为M-T 算法)

Möller-Trumbore 算法的核心思想是一步到位的计算出光线是否与三角形相交,主要利用到的知识点是三角形的重心坐标。它是由Tomas Moller 和Ben Trumbore 于1997 年在一篇题名为“Fast, Minimum Storage Ray/Triangle Intersection”的论文中介绍。

传统的“求三角形与光线是否相交的算法”比较繁琐比较慢,而M-T 算法很直接很快。

2.1、传统求解射线是否与三角形相交的方法

首先看看用“循规蹈矩的笨方法”求一个三角形和光线相交的过程。

射线方程为: r ( t ) = O + t d , 0 ≤ t ≤∞ ; 这里的射线r ( t ) 其实是“有长度”其长度由t 决定, 射线的起点是O ,长度是“t 个单位向量d 的模长”。可以将t 理解为“时间或是尺度因子”。即:给定起点O ,方向向量d, 射线能射多远,就由t 决定。“射线是否与平面相交的问题,也就看看是否有一个具体的t1, 0 ≤ t 1 ≤∞ , 使得点p = r (t 1)在平面上。”

平面方程为: (p – p ’)·N = 0 , 即:给定一个法向量N, 平面上的任意向量(p – p’) 与N的内积等于0。也可以理解为:给定法向量N 和一点p ’, 那么满足(p -p ’)·N = 0 的任意点 p 就确定了一个平面,该平面过点p’,并且与向量N 垂直。

有了上面的射线方程和平面方程,那么,判断一条射线r (t )是否与平面相交的问题,就可以表示为对下面方程求解t ,如果t 在【0, +∞】内有解t1 ,那么就可以说射线r ( t )与平面相交。

假设p = r ( t ), 对下面方程求解t 。

基于上面的分析,我们可以知道,传统上判断射线是否与三角形相交时,可以分为两步:

第一步: 判断射线是否与【三角形所在】平面相交。当光线r (t )与平面相交, 就有点p 满足(p – p ’)·N =0 , 同时p = o + t * d 。只有当(p – p ’)·N = 0 才能满足p 点在平面内。(p – p ’)这个向量垂直于法线方向。

第二步: 确定射线与平面相交后,再求得其交点p , 并判断该点是否在三角形内。

引出MT 算法:

有没有一种直接直接判断三角形是否与光线相交的方法呢?M-T 算法就是这个活的!

2.2、M-T 算法

我们已经知道,点P 可以写成三角形三个顶点乘上某个系数相加的形式:

P = a A + u B + v C; 其中1 <= a 且u, v >= 0 且a + u + v = 1

那么就可以写成:

o + t d = a A + u B + v C

由于a + u + v = 1 ,所以a = 1 – u – v ,所以,上式子可以继续写为:

o + t d = (1 – u – v ) A + u B + v C
=> o + t d = A – u A – v A + u B + v C
=> o + t d = A + (B – A)u + (C – A)v
=> o – A = -t d + (B-A) u + (C-A) v

这样就有了三个未知数t ,u ,v 和一个方程:

我们可以根据克莱姆法则(Cramer’s rule)求解该问题,也就是:已知A、B、C,可以根据克莱姆法则得到D,然后根据上面方程求得t ,u ,v,如果t ,u ,v 满足下面条件,那么射线就与三角形相交。
条件1:求得的t 必须是一个大于0 的数。
条件2:求得的u 和v 必须是一非负的数且值小于等于1。
条件3:求得的v + u 必须是一个小于等于1 的数。

推荐产品