浏览量:689

4.3. 线性对象与三角形的交

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

4.3. 线性对象与三角形的交

问题描述:在三维空间上,判断线性对象\(P + t\vec d\)与三角形\(\Delta {V_0}{V_1}{V_2}\)是否相交,若相交,求出交点,三角形所在的平面是\(\pi \)

2015-3-23 1-45-52

图4.11 直线与三角形的四种关系

三维空间的模型通常是由一个个三角形面片构成的,线性对象与三角形的相交检测也显得特别的重要。如图4.11所示,一条直线与三角形可能有四种关系:1)直线\({L_0}\)与三角形相交;2)直线\({L_1}\)与三角形所在的平面相交,但与三角形不相交;3)直线\({L_2}\)与在三角形所在的平面上;4)直线\({L_3}\)与三角形所在的平面平行。

一种朴素的检测算法是计算线性对象与三角形所在的平面的交点,再判断交点是否在三角形内。如果交点在三角形内,则线性对象与三角形相交;否则,不相交。这种算法效率不仅效率较低,而且更容易造成浮点数误差。因为计算机中的浮点数占用字节有限,能表示的精度有限,有效数较少,求直线与平面的交点,由于对同一个变量多次的乘法或者除法操作,造成误差的叠加,最后计算出来的结果由于精度问题,可能造成较大的误差。例如,三角形顶点的坐标数值较大,计算的直线与平面的交点,会由于精度误差导致求出的交点偏离平面,即可以检测到交点不在平面上。

Möller&Trumbore(1997)[1]提出了一种更加高效的射线与三角形相交测试的算法,而且乘法或者除法操作造成的误差叠加较少,精度损失更小,因此性能上更加健壮。

三角形内的任意一点都可以用它相对于三角形的顶点的位置来定义:

\(T(u,v) = (1 - u - v){V_0} + u{V_1} + v{V_2} \tag{4.18}\)

其中,\((u,v) \in D = \{ (u,v):u \ge 0,v \ge 0,u + v \le 1\} \),称为重心坐标(barycentric coordinate)。直线可以用参数方程表示为\(P + t\vec d\),因此计算直线与三角的交点的等式为

\[P + t\vec d = \left( {1 - u - v} \right){V_0} + u{V_1} + v{V_2} \tag{4.19}\]

整理,得

\[\left[ {\begin{array}{*{20}{c}}{ - \vec d}&{{V_1} - {V_0}}&{{V_2} - {V_0}}\end{array}} \right]\left[ {\begin{array}{*{20}{c}}t\\u\\v\end{array}} \right] = \left[ {P - {V_0}} \right] \tag{4.20}\]

这相当于是一个齐次线性方程组,\((t,u,v)\)是它的解,可以采用克拉姆法则来求解,得到

\[\left[ {\begin{array}{*{20}{c}}t\\u\\v\end{array}} \right] = \frac{1}{{\left| {\begin{array}{*{20}{c}}{ - \vec d}&{{E_1}}&{{E_2}}\end{array}} \right|}}\left[ {\begin{array}{*{20}{c}}{|T}&{{E_1}}&{{E_2}|}\\{| - \vec d}&T&{{E_2}|}\\{| - \vec d}&{{E_1}}&{T|}\end{array}} \right] \tag{4.21}\]

其中,\(T = P - {V_0},{E_1} = {V_1} - {V_0},{E_2} = {V_2} - {V_0}\),依据线性代数的知识,易知\(\left| {\begin{array}{*{20}{c}}A&B&C\end{array}} \right| = (A \times B) \cdot C\)\( = - (A \times C) \cdot B = - (C \times B) \cdot A\),因此等式(4.21)可以写成:

\[\left[ {\begin{array}{*{20}{c}}t\\u\\v\end{array}} \right] = \frac{1}{{\left( {\vec d \times {E_2}} \right) \cdot {E_1}}}\left[ {\begin{array}{*{20}{c}}{\left( {T \times {E_1}} \right) \cdot {E_2}}\\{\left( {\vec d \times {E_2}} \right) \cdot T}\\{\left( {T \times {E_1}} \right) \cdot \vec d}\end{array}} \right] \tag{4.22}\]

如果得到的解\((u,v) \in D\),那么直线与平面的交点位于三角形内;否则,位于三角形外。注意,若\(u = 0\)\(v = 0\)\(u + v = 1\),则交点在三角形的边上。

直线与三角形相交测试的算法伪码如下所示:

在三维空间上,判断直线\(L(t) = P + t\vec d,t \in \left( { - \infty , + \infty } \right)\)与三角形\(\Delta {V_0}{V_1}{V_2}\)是否相交,若相交,求出交点,三角形所在的平面是\(\pi \)
return ({OVERLAPPING, PARALLEL, DISJOINT, INTERSECTING})
1.    \(T = P - {V_0},{E_1} = {V_1} - {V_0},{E_2} = {V_2} - {V_0}\);
2.    \(M = \vec d \times {E_2}\);
3.    \(det = M \cdot {E_1}\);
4.    if\(det = = 0\),then
5.           \(d = \left( {{E_1} \times {E_2}} \right) \cdot T\);
6.           if\(d = = 0\), then
7.                  return OVERLAPPING;                     //直线与平面\(\pi \)重叠
8.           else
9.                  return PARALLEL;                            //直线与平面\(\pi \)平行
10.          end if
11.   else
12.          \(K = T \times {E_1}\);
13.          \(t = K \cdot {E_2}/det\)
14.          \(u = M \cdot T/det\);
15.          \(v = K \cdot \vec d/det\);
16.          if \(u \prec 0\)||\(v \prec 0\)||\(u + v \succ 1\),then
17.                 return DISJOINT;                            //直线与三角形不相交
18.          else
19.                 \(Q = P + t\vec d\);
20.                 return INTERSECTING;                     //直线与三角形相交于点\(Q\)
21.          end if;
22.   end if;

如果需要求射线与三角形的交,必需限定\(t\)的取值范围,\(t\)必需满足条件\(t \ge 0\),若计算出来的\(t \prec 0\),则射线与三角形不相交。同样,如果需要求线段与三角形的交,线段的参数方程仍然可以表示为\(P + t\vec d\),线段的两个端点分别是\(P\)\(P + \vec d\),则\(t\)必需满足条件\(0 \le t \le 1\),因此,若计算出来的\(t \prec 0\)\(t \succ 1\),则线段与三角形不相交。

注意到,在上述的算法伪码中,已经把一些中间变量存储起来,避免重复计算,可以提高算法的速度,例如中间变量\(T = P - {V_0},{E_1} = {V_1} - {V_0},{E_2} = {V_2} - {V_0},\vec d \times {E_2},T \times {E_1}\)

spacer

Leave a reply