首先,三角形的三个顶点定义了一个平面。每个平面都有一个法线,可以看作垂直于平面表面的直线。考虑到我们知道三角形顶点(A,B和C)的坐标,我们可以计算向量AB和AC(它们只是从A到B和A到C的线)。为此,我们只需从A中减去B和从A中减去C。
要计算平面的法线(逻辑上,由于三角形位于平面中,它与三角形的法线相同),我们只需计算AB和AC的叉积。这两个矢量位于同一平面,因为它们连接三角形的顶点。由该叉积产生的矢量(表示为N)救是三角形的法线(图1)。
数学表达如下:
A = v1 - v0 = (1-(-1), (-1)-(-1), 0) = (2, 0, 0)
B = v2 - v0 = (0-(-1), 1-(-1), 0) = (1, 2, 0)
C = A × B
N_x = A.y * B.z - A.z * B.y = 0
N_y = A.z * B.x - A.x * B.z = 0
N_z = A.x * B.y - A.y * B.x = 2 * 2 - 0 * 1 = 4
N = (0, 0, 4)
(注意:在向量里,符号“×”指叉积,符号“⋅”指点积)
如果对C进行归一化,我们得到向量(0,0,1),它与正z轴平行。
这里还有一点需要注意的是,如果交换A与B向量叉乘的顺序,会得到一个与C方向想法的向量:
N = B × A
N_x = B.y * A.z - B.z * A.y = 0
N_y = B.z * A.x - B.x * A.z = 0
N_z = B.x * A.y - B.y * A.x = 0 * 1 - 2 * 2 = -4
N = (0, 0, -4)
这里涉及到三角形顶点申明顺序和方向(绕组)
设光线与平面的相交点为p,则p减掉三角形任意一个顶点所生成的向量位于平面内;又因为两个垂直的向量的点积为0。所以有:
(p - v1) ⋅ N = 0;(公式1)
p点也可以用光线来表示:
p = O + tR;(公式2)
其中O为光线原点,R为光线的方向(已归一化)。
将公式2带入公式1,得到:
((O + tR) - v1) ⋅ C = 0;
由于O, R, v1, C已知,可求得t,将t带入公式二,即可求得焦点p;
t = ((v1 - O) ⋅ N) / (R ⋅ N)(公式3)
此时有两个需要注意的点
1,当三角形位于光线的背后的时候,此时 t < 0;
2,当三角形与光线平行时,此时公式3无解;如果注意一下公式3,会发现此时(R ⋅ N) = 0;那么此时公式3会除以0;所以要提前测试一下;
求得交点之后,还需要进行内外测试。目前所求的交点为光线与平面的交点,所以还不知道交点是否在三角形内;所以需要进行内外测试已检测交点是否在三角形内;
如图2所示,有一个与x轴对齐的矢量A。让我们假设这个向量实际上与三角形的一个边对齐(由两个顶点V0V1定义的边)。现在,第二条边B由三角形的顶点V0和V2定义。让我们计算这两个向量的叉积。结果是一个向量,它指向与z轴和三角形法线相同的方向。
A=(1,0,0)
B=(1,1,0)
C.x = A.y * B.z − A.z * B.y =0
C.y = A.z * B.x − A.x * B.z =0
C.z = A.x * B.y − A.y * B.x = 1 ∗ 1 − 0 ∗ 1 = 1
C=(0,0,1)
现在,假设顶点V2不是坐标(1,1,0),而是坐标(1,-1,0)。换句话说,我们已经反映了它关于x轴的位置。如果我们现在计算交叉积 A x B',我们得到结果C'=(0, 0,-1)
A=(1,0,0)
B=(1,−1,0)
C.x = A.y * B.z − A.z * B.y =0
C.y = A.z * B.x − A.x * B.z=0
C.z = A.x * B.y − A.y * B.x=1∗−1−0∗1=−1
C=(0,0,−1)
我们知道光线与三角形相交的点在同一平面上。从上面的测试中得知,如果位于三角形平面中的交点P位于矢量A的左侧,那么三角形的法线和向量C是正的(C是A和B之间的叉积的结果。在这种情况下,A =(V1-V0)和B =(P-V0))。但是,如果P位于A的右侧,则该点积为负。在图2中可以看到,当它位于A的左侧时,P点位于三角形内部。为了测试点p是否在三角形内,需要重复左/右测试对于三角形的每个边缘。如果对于每个三角形边缘,发现点P位于矢量C的左侧(其中C分别定义为三角形的每个边缘的V1-V0,V2-V1和V0-V2),那么我们知道确保P在三角形内。如果任何三角形边缘的测试失败,则P位于三角形边界之外。该过程如图3所示。
代码如下:
bool rayTriangleIntersect(
const Vec3 \& orig, const Vec3& dir,
const Vec3& v0, const Vec3& v1, const Vec3& v2,
float t)
{
Vec3 v1v0 = v1 - v0;
Vec3 v2v0 = v2 - v0;
Vec3 N = v1v0.crossProduct(v2v0); // 求三角形法向量
//求交点P
float NdotRayDirection = N.dotProduct(dir);
if(fabs(NdotRayDirection) < kEpsilon) return false; //如果三角形法向量与光线的点积接近于0,可以认为光线与三角形平行,此时没有交点,返回false
t = (N.dotProduct(v0) + N.dotProduct(orig)) / NdotRayDirection; //计算t值
if(t < 0) return false; //如果t小于0,那么三角形在光线背后,返回false
Vec3 P = orig + t * dir; //计算交点p
Vec3 C;
//内外测试
Vec3 vp0 = P - v0;
Vec3 edge0 = v1 - v0;
C= edge0.crossProduct(vp0);
if(C < 0) return false; //在三角形外边,返回false
Vec3 vp1 = P - v1;
Vec3 edge1 = v2 - v1;
C= edge1.crossProduct(vp1);
if(C < 0) return false; //在三角形外边,返回false
Vec3 vp2 = P - v2;
Vec3 edge2 = v0 - v2;
C= edge2.crossProduct(vp2);
if(C < 0) return false; //在三角形外边,返回false
return true; //三角形与光线有交点,返回true
}