浏览量:950

4.4. 三角形与三角形的重叠检测

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

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

4.4. 三角形与三角形的重叠检测

问题描述:在三维空间上,有两个三角形\({T_1}:\Delta V_0^1V_1^1V_2^1\)\({T_2}:\Delta V_0^2V_1^2V_2^2\),分别位于平面\({\pi _1}\)\({\pi _2}\)上,判断这两个三角形是否重叠。

2015-3-23 10-47-28

图4.12 三角形和它所在的平面

至少有六种算法可以用于判定三角形与三角形是否相交。第一种算法,也是最朴素的算法,速度最慢。第二种算法,由Möller et al[3](1997)提出了一种更加高效的算法,算法是基本思路是:若两个三角形相交,那么它们所在的平面必相交于一条直线,两个三角形分别在该直线上产生间隔,如图4.12所示,若间隔重叠,则两个三角形相交,否则,不相交,因此该方法也称为间隔重叠法。第三种算法,Guigue& Devillers [7](2003)对间隔重叠法进行改进,通过采用行列式的计算,来判断两个三角形是否相交,有效的避免的除法操作,由于不用求解实际的间隔值,浮点数的误差相对较小,因此也比第二种算法更稳定。第四种算法,Held[4](1997)实现了一个名为ERIT的软件包,用于三维空间的相交测试,ERIT包括了一种三角形与三角形相交测试的算法,该方法的算法比第一种算法高效,由于需要求交点操作,必需包括一些必要的除法运算,再根据求出的交点进行后续的判断,浮点数的精度误差更大,因此稳定性上也不如第二种和第三种算法。此外,Shen et al[5](2003)提出了一种通过计算线与线之间有向距离的方法,来判定两个三角形是否相交,还可以采用分离轴的方法实现相交测试[4]。下面将分别介绍前四种算法的思想和实现方法。

4.4.1. 朴素算法

首先,判断三角形\({T_1}\)的每一条边,是否与三角形\({T_2}\)相交,若至少存在一条这样的边,说明两个三角形相交;接着,判断三角形\({T_2}\)的每一条边,是否与三角形\({T_1}\)相交。最坏情况下,需要做6次线段与三角形的相交测试,这是最容易想到的一种算法,也是最暴力的算法。

4.4.2. 间隔重叠法

Möller[3](1997)提出了通过判断两个三角形在相交直线上是否重叠的方法来实现两个三角形的重叠检测。设平面\({\pi _2}\)的参数方程表示为\({{\vec{d}}_{2}}\cdot X+{{D}_{2}}=0\)\(X\)是平面上的点,由三角形初始化一个平面,即\({{\vec{d}}_{2}}=(V_{1}^{2}-V_{0}^{2})\times (V_{2}^{2}-V_{0}^{2}),{{D}_{2}}=-{{\vec{d}}_{2}}\cdot V_{0}^{2}\)

三角形\({{T}_{1}}\)上的顶点到到平面\({{\pi }_{2}}\)的有符号距离用如下等式表示,由于这里只需要判断有符号距离的符号,所以可以不需要除法\(\left\| {{{\vec{d}}}_{2}} \right\|\)

\({{d}_{V_{i}^{1}}}={{\vec{d}}_{2}}\cdot V_{i}^{1}+{{D}_{2}},i=0,1,2 \tag{4.23}\)

现在,如果对于所有的\(i=0,1,2\)\({{d}_{V_{i}^{1}}}\ne 0\)(说明没有顶点在平面上),同时所有的值均具有相同的符号,那么\({{T}_{1}}\)的三个顶点都位于平面的同一侧。这样,就可以排除重叠的可能性。对于三角形\({{T}_{2}}\)和平面\({{\pi }_{1}}\),也需要这样的测试,测试过程也是相同的。这两步测试,可以避免很多不必要的计算,如果通过了这两个测试,说明两个平面必相交,两个平面相交于一条直线,即\({{\vec{d}}_{1}}\times {{\vec{d}}_{2}}\)一定存在。

如果对于所有的\(i=0,1,2,{{d}_{V_{i}^{1}}}=0\),说明两个三角形在同一个平面上,这种情况在后面会单独讨论。如果不是都为零的情况,设两个平面相交的直线的参数方程是\(L=O+t\vec{d}\),其中\(\vec{d}={{\vec{d}}_{1}}\times {{\vec{d}}_{2}}\)表示相交直线的方向向量,\(O\)表示相交直线上任意一点。通过前面的测试,可以保证,如果两个三角形相交,那么它们一定相交于直线\(L\)上。如图4.12所示,图(a)中每个三角形与直线\(L\)相交,会产生间隔,而且产生的间隔重叠,那么这两个三角形就是相交的,但图(b)中两个三角形产生的间隔不会重叠,因此两者不相交的。

现在,我们需要计算三角形\({{T}_{1}}\)与直线\(L\)相交的间隔,需要重排列顶点顺序,使得\(V_{0}^{1}\)\(V_{2}^{1}\)在平面\({{\pi }_{2}}\)的相同一侧,而\(V_{1}^{1}\)在另一侧,对于顶点在平面上的特殊情况,在后面会介绍。现在必需计算出边\(\overline{V_{0}^{1}V_{1}^{1}}\)和边\(\overline{V_{1}^{1}V_{2}^{1}}\)与直线\(L\)相交点,确定它们之间间隔的标量表示,把三角形的顶点投影到直线上,即:

\[{{p}_{V_{i}^{1}}}=\vec{d}\cdot (V_{i}^{1}-O),i=0,1,2 \tag{4.24}\]

2015-3-23 11-21-08

图4.13 两个三角形之间的相交

如图4.13所示,两个平面相交于直线\(L\),边\(\overline{V_{0}^{1}V_{1}^{1}}\)与直线\(L\)相交于点\(B\)\(A_{0}^{1},A_{1}^{1}\)分别是三角形\({{T}_{1}}\)上的顶点\(V_{0}^{1},V_{1}^{1}\)在平面\({{\pi }_{2}}\)上的投影点,\(C_{0}^{1},C_{1}^{1}\)分别是顶点\(V_{0}^{1},V_{1}^{1}\)在直线\(L\)上的投影点,有\(\overline{C_{0}^{1}V_{0}^{1}}\bot L,\overline{C_{1}^{1}V_{1}^{1}}\bot L\)。令\(B=O+{{t}_{1}}\vec{d}\),则现在需要计算出参数\({{t}_{1}}\)。易知,\(\Delta A_{0}^{1}BC_{0}^{1}\)\(\Delta A_{1}^{1}BC_{1}^{1}\)是相似三角形,且\(\Delta A_{0}^{1}BV_{0}^{1}\)\(\Delta A_{1}^{1}BV_{1}^{1}\)也是相似三角形,即有:

\[\frac{\overline{BC_{0}^{1}}}{\overline{BC_{1}^{1}}}=\frac{\overline{BA_{0}^{1}}}{\overline{BA_{1}^{1}}}=\frac{\overline{A_{0}^{1}V_{0}^{1}}}{\overline{A_{0}^{1}V_{1}^{1}}} \tag{4.25}\]

其中,\(\overline{BC_{0}^{1}}={{p}_{B}}-{{p}_{V_{0}^{1}}},\overline{BC_{1}^{1}}={{p}_{V_{1}^{1}}}-{{p}_{B}}\),易推导出:

\[{{t}_{1}}={{p}_{V_{0}^{1}}}+({{p}_{V_{1}^{1}}}-{{p}_{V_{0}^{1}}})\frac{{{d}_{V_{0}^{1}}}}{{{d}_{V_{0}^{1}}}-{{d}_{V_{1}^{1}}}} \tag{4.26}\]

用相同的方法,可以计算出边\(\overline{V_{1}^{1}V_{2}^{1}}\)与直线\(L\)交点的标量\({{t}_{2}}\),现在标量\({{t}_{1}}\)\({{t}_{2}}\)就能表示三角形\({{T}_{1}}\)与直线\(L\)相交的间隔。使用同样的方法,就可以计算出三角形\({{T}_{2}}\)与直线\(L\)相交的间隔,如果两个间隔互相重叠,那么这两个三角形一定相交。

如果两个三角形是共面的情况,可以把它们投影到一个轴对齐的二维平面上,例如,把要把三角形\({{T}_{1}}\)投影到一个二维平面上,\({{\vec{d}}_{1}}\)是三角形\({{T}_{1}}\)所在的平面的法向量。若\(\left| {{{\vec{d}}}_{1x}} \right|=\max \{\left| {{{\vec{d}}}_{1x}} \right|,\left| {{{\vec{d}}}_{1y}} \right|,\left| {{{\vec{d}}}_{1z}} \right|\}\),把三角形\({{T}_{1}}\)投影到\(YZ\)平面上;若\(\left| {{{\vec{d}}}_{1y}} \right|=\max \{\left| {{{\vec{d}}}_{1x}} \right|,\left| {{{\vec{d}}}_{1y}} \right|,\left| {{{\vec{d}}}_{1z}} \right|\}\),把三角形\({{T}_{1}}\)投影到\(ZX\)平面上;若\(\left| {{{\vec{d}}}_{1z}} \right|=\max \{\left| {{{\vec{d}}}_{1x}} \right|,\left| {{{\vec{d}}}_{1y}} \right|,\left| {{{\vec{d}}}_{1z}} \right|\}\),把三角形\({{T}_{1}}\)投影到\(XY\)平面上。采用这种投影方法,得到的三角形的投影面积最大。这就把三维的两个三角形的相交测试问题转化为二维的问题了。可以测试三角形\({{T}_{1}}\)的所有边是否同\({{T}_{2}}\)的所有边相交,如果存在相交的情况,则两个三角形相交,否则判断三角形的一个点是否在另外一个三角形内,即判断三角形\({{T}_{1}}\)的任意一个顶点是否包含在\({{T}_{2}}\)中和三角形\({{T}_{2}}\)的任意一个顶点是否包含在\({{T}_{1}}\)中。

算法还可以继续优化,三角形与直线相交的间隔发生位移,并不影响间隔测试的结果,因此就可以把等式(4.26)简化为

\[{{p}_{V_{i}^{1}}}=\vec{d}\cdot V_{i}^{1},i=0,1,2 \tag{4.27}\]

将等式中的\(O\)消除掉了,此外,把直线\(L\)沿着它最对齐的轴投影,这也不会影响到重叠测试的结果,避免了计算量,如等式(4.28)所示,

\[{p_{V_i^1}} = \left\{ {\begin{array}{*{20}{c}}{V_{ix}^1,if{\rm{ }}\left| {{{\vec d}_x}} \right| = \max \{ \left| {{{\vec d}_x}} \right|,\left| {{{\vec d}_y}} \right|,\left| {{{\vec d}_z}} \right|\} }\\{V_{iy}^1,if{\rm{ }}\left| {{{\vec d}_y}} \right| = \max \{ \left| {{{\vec d}_x}} \right|,\left| {{{\vec d}_y}} \right|,\left| {{{\vec d}_z}} \right|\} }\\{V_{iy}^1,if{\rm{ }}\left| {{{\vec d}_z}} \right| = \max \{ \left| {{{\vec d}_x}} \right|,\left| {{{\vec d}_y}} \right|,\left| {{{\vec d}_z}} \right|\} }\end{array}} \right. \tag{4.28}\]

其中,\(V_{0x}^{1}\)表示顶点\(V_{0}^{1}\)x分量。

对于不共面的两个三角形,需要重排列顶点,保证三角形的一个顶点在平面的一侧,剩下两个点在另一侧,但如果是存在一个三角形的点在另一个三角形所在平面上时,就需要特别考虑,这又可以分为两种情况来考虑:

1.    三角形上有且只有两个顶点在平面上

设三角形\(T:pqr\)有且只有两个顶点在平面上,设\(p\)\(q\)在平面上,此时,顶点\(p\)\(q\)到它们的相交直线\(L\)的投影,就是间隔标量\({{t}_{1}}\)\({{t}_{2}}\)

2.    三角形上有且只有一个顶点在平面上

设三角形\(T:pqr\)有且只有一个顶点在平面上,设\(p\)在平面上,如果\(q\)\(r\)到平面的有符号距离同号,则把\(p\)分配为平面一侧,\(q\)\(r\)分配为平面的另一侧;否则,\(q\)\(r\)到平面的有符号距离异号,则从\(q\)\(r\)中随机取一个顶点为平面的一侧,剩下两个顶点为平面另一侧。

间隔重叠法的算法伪码如下所示:

在三维空间上,有两个三角形\({{T}_{1}}:\Delta V_{0}^{1}V_{1}^{1}V_{2}^{1}\)\({{T}_{2}}:\Delta V_{0}^{2}V_{1}^{2}V_{2}^{2}\),分别位于平面\({{\pi }_{1}}\)\({{\pi }_{2}}\)上,判断这两个三角形是否重叠
return ({TRUE, FALSE})
1.    \({{\vec{d}}_{1}}=(V_{1}^{1}-V_{0}^{1})\times (V_{2}^{1}-V_{0}^{1}),{{D}_{1}}=-{{\vec{d}}_{1}}\cdot V_{0}^{1}\);               //初始化三角形\({{T}_{1}}\)所在平面\({{\pi }_{1}}\)
2.    \(dis{{t}_{2}}[0]={{\vec{d}}_{1}}\cdot V_{0}^{2}+{{D}_{1}}\);                                  //三角形\({{T}_{2}}\)上的顶点到平面\({{\pi }_{1}}\)的有符号距离
3.    \(dis{{t}_{2}}[1]={{\vec{d}}_{1}}\cdot V_{1}^{2}+{{D}_{1}}\);
4.    \(dis{{t}_{2}}[2]={{\vec{d}}_{1}}\cdot V_{2}^{2}+{{D}_{1}}\);
5.    \({{k}_{0}}=dis{{t}_{2}}[0]\cdot dis{{t}_{2}}[1],{{k}_{1}}=dis{{t}_{2}}[1]\cdot dis{{t}_{2}}[2]\);
6.    if \({{k}_{0}}\succ 0\)&&\({{k}_{1}}\succ 0\), then                     //三角形\({{T}_{2}}\)上的三个顶点在平面上的同一侧
7.           return FALSE;
8.    else if \(dis{{t}_{2}}[0]==0\)&&\(dis{{t}_{2}}[1]==0\)&&\(dis{{t}_{2}}[2]==0\), then                  //三角形\({{T}_{1}}\)\({{T}_{2}}\)共面
9.           把\({{T}_{1}}\)\({{T}_{2}}\)投影到二维平面,判断两个二维三角形是否重叠,并将结果返回;
10.   end if;
11.   \({{\vec{d}}_{2}}=(V_{1}^{2}-V_{0}^{2})\times (V_{2}^{2}-V_{0}^{2}),{{D}_{2}}=-{{\vec{d}}_{2}}\cdot V_{0}^{2}\);        //初始化三角形\({{T}_{2}}\)所在平面\({{\pi }_{2}}\)
12.   \(dis{{t}_{1}}[0]={{\vec{d}}_{2}}\cdot V_{0}^{1}+{{D}_{2}}\);                                  //三角形\({{T}_{1}}\)上的顶点到平面\({{\pi }_{2}}\)的有符号距离
13.   \(dis{{t}_{1}}[1]={{\vec{d}}_{2}}\cdot V_{1}^{1}+{{D}_{2}}\);
14.   \(dis{{t}_{1}}[2]={{\vec{d}}_{2}}\cdot V_{2}^{1}+{{D}_{2}}\);
15.   \({{k}_{0}}=dis{{t}_{1}}[0]\cdot dis{{t}_{1}}[1],{{k}_{1}}=dis{{t}_{1}}[1]\cdot dis{{t}_{1}}[2]\);
16.  if \({k_0} \succ 0\)&& \({k_1} \succ 0\), then                          //三角形\({T_1}\)上的三个顶点在平面上的同一侧
17.          return FALSE;
18.   end if;
19.   \(\vec{d}={{\vec{d}}_{1}}\times {{\vec{d}}_{2}}\);                                                //相交直线\(L\)所在的方向向量
20.   \( ({{t}_{0}},{{t}_{1}})=\operatorname{COMPUTE}\_INTERVAL(\Delta V_{0}^{1}V_{1}^{1}V_{2}^{1},\vec{d},dis{{t}_{1}})\);    //\({{T}_{1}}\)在直线\(L\)上的间隔,有\({{t}_{0}}\prec {{t}_{1}}\)
21.   \( ({{s}_{0}},{{s}_{1}})=\operatorname{COMPUTE}\_INTERVAL(\Delta V_{0}^{2}V_{1}^{2}V_{2}^{2},\vec{d},dis{{t}_{2}})\); //\({{T}_{2}}\)在直线\(L\)上的间隔,有\({{s}_{0}}\prec {{s}_{1}}\)
22.   if \({{t}_{0}}\succ {{s}_{1}}||{{t}_{1}}\prec {{s}_{0}}\), then
23.          return FALSE;
24.   else
25.          return TRUE;
26.   end if;

\(\operatorname{COMPUTE}\_INTERVAL(\Delta {{V}_{0}}{{V}_{1}}{{V}_{2}},\vec{d},dist)\)
/* 计算三角形\(\Delta {{V}_{0}}{{V}_{1}}{{V}_{2}}\)在方向为\(\vec{d}\)的直线上的间隔,三角形上的三个顶点到另一个平面的有符号距离分别表示为\(dist[0],dist[1],dist[2]\)*/
1.    对有符号距离按照从小到大排序,使得\(dist[{{k}_{0}}]\le dist[{{k}_{1}}]\le dist[{{k}_{2}}]\),但\(dist[0],dist[1],dist[2]\)
三个值不变;                                   //\({{k}_{0}},{{k}_{1}},{{k}_{2}}\in \{0,1,2\}\),且三个值互不一样,表示索引
2.    if \(\left| {{{\vec{d}}}_{x}} \right|=\max \{\left| {{{\vec{d}}}_{x}} \right|,\left| {{{\vec{d}}}_{y}} \right|,\left| {{{\vec{d}}}_{z}} \right|\}\), then
3.           \(axis=x\);
4.    else if \(\left| {{{\vec{d}}}_{y}} \right|=\max \{\left| {{{\vec{d}}}_{x}} \right|,\left| {{{\vec{d}}}_{y}} \right|,\left| {{{\vec{d}}}_{z}} \right|\}\), then
5.           \(axis=y\);
6.    else
7.           \(axis=z\)
8.    end if;
9.    if \(dist[{{k}_{0}}]==0\)&&\(dist[{{k}_{1}}]==0\), then
10.          \({{t}_{0}}={{V}_{{{k}_{0}},axis}}\);
11.          \({{t}_{1}}={{V}_{{{k}_{1}},axis}}\);
12.   else if \(dist[{{k}_{1}}]==0\)&&\(dist[{{k}_{2}}]==0\), then
13.          \({{t}_{0}}={{V}_{{{k}_{1}},axis}}\);
14.          \({{t}_{1}}={{V}_{{{k}_{2}},axis}}\);
15.   else
16.          if \(dist[{{k}_{1}}]\prec 0\), then
17.                 SWAP(\({{k}_{0}},{{k}_{2}}\));                                  //交换两个值
18.          end if;
19.        \({{p}_{0}}={{V}_{{{k}_{0}},axis}},{{p}_{1}}={{V}_{{{k}_{1}},axis}},{{p}_{2}}={{V}_{{{k}_{2}},axis}}\);
20           \({{t}_{0}}={{p}_{1}}+({{p}_{0}}-{{p}_{1}})\cdot dist[{{k}_{1}}]/(dist[{{k}_{1}}]-dist[{{k}_{0}}])\);
21.          \({{t}_{1}}={{p}_{2}}+({{p}_{0}}-{{p}_{2}})\cdot dist[{{k}_{2}}]/(dist[{{k}_{2}}]-dist[{{k}_{0}}])\);
22.   end if;
23.   if \({{t}_{0}}\succ {{t}_{1}}\), then
24.          SWAP(\({{t}_{0}},{{t}_{1}}\));
25.   end if;
26.   return \(\left( {{t}_{0}},{{t}_{1}} \right)\);

4.4.3. 间隔重叠法的改进算法

Guigue& Devillers [7](2003)对间隔重叠法进行改进,不需要求出具体的数值,因此能更稳定的检测两个三角形是否相交。

给定4个三维空间上的点\(a=({{a}_{x}},{{a}_{y}},{{a}_{z}}),b=({{b}_{x}},{{b}_{y}},{{b}_{z}}),c=({{c}_{x}},{{c}_{y}},{{c}_{z}})\)\(d=({{d}_{x}},{{d}_{y}},{{d}_{z}})\),可以定义一个行列式\(\left[ a,b,c,d \right]\)为:

\[\left[ {a,b,c,d} \right] = - \left| {\begin{array}{*{20}{c}}{{a_x}}&{{b_x}}&{{c_x}}&{{d_x}}\\{{a_y}}&{{b_y}}&{{c_y}}&{{d_y}}\\{{a_z}}&{{b_z}}&{{c_z}}&{{d_z}}\\1&1&1&1\end{array}} \right| = (d - a) \cdot \left( {(b - a) \times (c - a)} \right) \tag{4.29}\]

2015-3-23 11-24-57

图4.14 行列式\(\left[ a,b,c,d \right]\)的几何意义

解释下行列式\(\left[ a,b,c,d \right]\)的符号的几何意义,基于右手法则,如图4.14所示,它表示点\(d\)是在由\(a\)\(b\)\(c\)确定的平面的正半空间上,负半空间上,还是在平面上。若行列式为正,则表示点\(d\)在平面正半空间上;若为负,则表示在负半空间上;若为零,则表示在平面上,即4个点在同一个平面上。

首先,需要检测三角形\({{T}_{1}}\)与三角形\({{T}_{2}}\)所在平面\({{\pi }_{2}}\)的相交情况,可以检测\(\left[ V_{0}^{2},V_{1}^{2},V_{2}^{2},V_{0}^{1} \right] \)\(\left[ V_{0}^{2},V_{1}^{2},V_{2}^{2},V_{1}^{1} \right] \)\(\left[ V_{0}^{2},V_{1}^{2},V_{2}^{2},V_{2}^{1} \right] \)的符号,则存在三种不同的情况:1)若三个行列式都有相同的符号,且不存在零,说明三角形\({{T}_{1}}\)的三个顶点在平面\({{\pi }_{2}}\)的相同一侧,则三角形与平面不相交,因此不需要再做进一步的测试;2)若三个行列式的符号都是零,说明两个三角形共面,可以把它们投影到一个轴对齐的二维平面上,将三维的问题转化为二维的问题;3)若三个行列式存在相反的符号,或者部分为零,说明三角形\({{T}_{1}}\)与平面\({{\pi }_{2}}\)相交。采用同样的方法,也可以检测三角形\({{T}_{2}}\)与三角形\({{T}_{1}}\)所在平面\({{\pi }_{1}}\)的相交情况。其实,这一个阶段的判断与Möller的间隔重叠法是相同的。

接着,考虑不存在任何一个三角形的顶点在平面上的情况,即点只能在平面的正半空间或者负半空间。对三角形的顶点进行重新排列,使得三角形\({{T}_{1}}\)的顶点\(V_{1}^{1}\)在平面\({{\pi }_{2}}\)的一侧,顶点\(V_{0}^{1}\)\(V_{2}^{1}\)在另一侧,同样对于三角形\({{T}_{2}}\)来说,顶点\(V_{1}^{2}\)在平面\({{\pi }_{1}}\)的一侧,\(V_{0}^{2}\)\(V_{2}^{2}\)在另一侧。相对于顶点\(V_{1}^{1}\)\(V_{1}^{2}\))来说,三角形\({{T}_{2}}\)\({{T}_{1}}\))的三个顶点是逆时针顺序的,即由顶点\(V_{1}^{1}\)\(V_{1}^{2}\))观察三角形\({{T}_{2}}\)\({{T}_{1}}\))的顶点是逆时针顺序排列的,如图1.14所示。重排列三角形\({{T}_{1}}\)\({{T}_{2}}\)的顶点,需要实现两个目标:1)顶点\(V_{1}^{i}\)在平面\({{\pi }_{3-i}}\)的一侧,顶点\(V_{0}^{i}\)\(V_{2}^{i}\)在另一侧;2)由顶点\(V_{1}^{i}\)观察三角形\({{T}_{3-i}}\),三角形的三个顶点是逆时针顺序的,其中\(i\in \{1,2\}\)。在具体的实现中,相对于\(V_{1}^{1}\),判断三角形\({{T}_{2}}\)的顶点是否逆时针顺序排列的,可以采用行列式\(\left[ V_{0}^{2},V_{1}^{2},V_{2}^{2},V_{1}^{1} \right] \),若行列式为负数,则三角形\({{T}_{2}}\)的顶点是顺时针顺序的;若行列式是正数,则是逆时针顺序的。

2015-3-23 11-25-07

图4.15 三角形\({{T}_{1}}\)\({{T}_{2}}\)相交,它们在直线\(L\)产生的间隔分别是\([i,j]\)\([k,l]\)

通过上面的重排列处理,如图4.15所示,现在可以确定三角形\({{T}_{2}}\)上的边\(\overline{V_{1}^{2}V_{0}^{2}}\)与直线\(L\)相交处的标量是\(k\),边\(\overline{V_{1}^{2}V_{2}^{2}}\)与直线\(L\)相交处的标量是\(l\),必然有\(k\prec l\)。对于三角形\({{T}_{1}}\),计算出来的间隔标量\(i\)\(j\),必然有\(i\prec j\)。两个三角形在直线\(L\)上产生的间隔分别是\([i,j]\)\([k,l]\),可以通过判断间隔是否重合,来判断两个三角形是否相交。还有一种方法就是利用行列式来判断,若行列式\(\left[ V_{1}^{1},V_{2}^{1},V_{1}^{2},V_{2}^{2} \right] \)\(\left[ V_{1}^{1},V_{0}^{1},V_{0}^{2},V_{1}^{2} \right] \)满足不等式(4.30),则两个三角形相交,否则,不相交。由前面对行列式的几何解释,可知,\(\left[ V_{1}^{1},V_{2}^{1},V_{1}^{2},V_{2}^{2} \right]\le 0\)几何意义可理解为顶点\(V_{2}^{2}\)在顶点\(V_{1}^{1},V_{2}^{1},V_{1}^{2}\)所确定平面的负半空间,\(\left[ V_{1}^{1},V_{0}^{1},V_{0}^{2},V_{1}^{2} \right]\le 0\)几何意义可理解为顶点\(V_{1}^{2}\)在顶点\(V_{1}^{1},V_{0}^{1},V_{0}^{2}\)所确定平面的负半空间。

\[\left[ {V_1^1,V_2^1,V_1^2,V_2^2} \right] \le 0 \wedge \left[ {V_1^1,V_0^1,V_0^2,V_1^2} \right] \le 0 \tag{4.30}\]

最后,介绍顶点在平面上这种特殊情况的解决方法:

1.    三角形上有且只有两个顶点在平面上

例如,三角形\({{T}_{1}}\)存在两个顶点,设\(V_{0}^{1}\)\(V_{2}^{1}\)在平面上,则指定\(V_{1}^{1}\)在平面的一侧,而\(V_{0}^{1}\)\(V_{2}^{1}\)在另一侧。

2.    三角形上有且只有一个顶点在平面上

例如,三角形\({{T}_{1}}\)存在一个顶点在平面上,设\(V_{1}^{1}\)在平面上,若\(V_{0}^{1}\)\(V_{2}^{1}\)在平面的两侧,则指定\(V_{0}^{1},V_{2}^{1}\)中任意一个在平面的一侧,而剩下两个顶点在平面的另一侧;若\(V_{0}^{1}\)\(V_{2}^{1}\)在平面的相同一侧,则指定\(V_{1}^{1}\)在平面的一侧,而\(V_{0}^{1}\)\(V_{2}^{1}\)在平面的另一侧。此时,如果采用行列式\(\left[ V_{0}^{2},V_{1}^{2},V_{2}^{2},V_{1}^{1} \right] \)来判别三角形\({{T}_{2}}\)的顶点顺序,会出现错误,因为行列式的值为0,可以通过等式\(d=-\left[ V_{0}^{2},V_{1}^{2},V_{2}^{2},V_{0}^{1} \right] \)或者\(d=-\left[ V_{0}^{2},V_{1}^{2},V_{2}^{2},V_{2}^{1} \right]\)来判定,若\(d\)值为负数,则三角形\({{T}_{2}}\)的顶点是顺时针顺序的;若\(d\)值是正数,则是逆时针顺序的。

Guigue& Devillers提出的改进算法的伪码如下所示:

在三维空间上,有两个三角形\({{T}_{1}}:\Delta V_{0}^{1}V_{1}^{1}V_{2}^{1}\)\({{T}_{2}}:\Delta V_{0}^{2}V_{1}^{2}V_{2}^{2}\),分别位于平面\({{\pi }_{1}}\)\({{\pi }_{2}}\)上,判断这两个三角形是否重叠
return ({TRUE, FALSE})
1.    \({{\vec{d}}_{1}}=(V_{1}^{1}-V_{0}^{1})\times (V_{2}^{1}-V_{0}^{1}),{{D}_{1}}=-{{\vec{d}}_{1}}\cdot V_{0}^{1}\);               //初始化三角形\({{T}_{1}}\)所在平面\({{\pi }_{1}}\)
2.    \(dis{{t}_{2}}[0]={{\vec{d}}_{1}}\cdot V_{0}^{2}+{{D}_{1}}\);                                  //三角形\({{T}_{2}}\)上的顶点到平面\({{\pi }_{1}}\)的有符号距离
3.    \(dis{{t}_{2}}[1]={{\vec{d}}_{1}}\cdot V_{1}^{2}+{{D}_{1}}\);
4.    \(dis{{t}_{2}}[2]={{\vec{d}}_{1}}\cdot V_{2}^{2}+{{D}_{1}}\);
5.    \({{k}_{0}}=dis{{t}_{2}}[0]\cdot dis{{t}_{2}}[1],{{k}_{1}}=dis{{t}_{2}}[1]\cdot dis{{t}_{2}}[2]\);
6.    if \({{k}_{0}}\succ 0\)&&\({{k}_{1}}\succ 0\), then                     //三角形\({{T}_{2}}\)上的三个顶点在平面上的同一侧
7.           return FALSE;
8.    else if \(dis{{t}_{2}}[0]==0\)&&\(dis{{t}_{2}}[1]==0\)&&\(dis{{t}_{2}}[2]==0\), then                  //三角形\({{T}_{1}}\)\({{T}_{2}}\)共面
9.           把\({{T}_{1}}\)\({{T}_{2}}\)投影到二维平面,判断两个二维三角形是否重叠,并将结果返回;
10.   end if;
11.   \({{\vec{d}}_{2}}=(V_{1}^{2}-V_{0}^{2})\times (V_{2}^{2}-V_{0}^{2}),{{D}_{2}}=-{{\vec{d}}_{2}}\cdot V_{0}^{2}\);        //初始化三角形\({{T}_{2}}\)所在平面\({{\pi }_{2}}\)
12.   \(dis{{t}_{1}}[0]={{\vec{d}}_{2}}\cdot V_{0}^{1}+{{D}_{2}}\);                                  //三角形\({{T}_{1}}\)上的顶点到平面\({{\pi }_{2}}\)的有符号距离
13.   \(dis{{t}_{1}}[1]={{\vec{d}}_{2}}\cdot V_{1}^{1}+{{D}_{2}}\);
14.   \(dis{{t}_{1}}[2]={{\vec{d}}_{2}}\cdot V_{2}^{1}+{{D}_{2}}\);
15.   \({{k}_{0}}=dis{{t}_{1}}[0]\cdot dis{{t}_{1}}[1],{{k}_{1}}=dis{{t}_{1}}[1]\cdot dis{{t}_{1}}[2]\);
16.   if \({{k}_{0}}\succ 0\)&&\({{k}_{1}}\succ 0\), then                     //三角形\({{T}_{1}}\)上的三个顶点在平面上的同一侧
17.          return FALSE;
18.   end if;
19.   \(\operatorname{REORDER}(dis{{t}_{1}},inde{{x}_{1}})\);
20. \(\operatorname{REORDER}(dis{{t}_{2}},inde{{x}_{2}})\);
21.   if  (\(dis{{t}_{1}}[inde{{x}_{1}}[0]]==0\)&&\(dis{{t}_{1}}[inde{{x}_{1}}[1]]\succ 0\)) ||
(\(dis{{t}_{1}}[inde{{x}_{1}}[0]]\ne 0\) &&\(dis{{t}_{1}}[inde{{x}_{1}}[0]]\prec 0\)), then
22.          SWAP(\(inde{{x}_{1}}[1],inde{{x}_{1}}[2] \));
23.   end if;
24.   if  (\(dis{{t}_{2}}[inde{{x}_{2}}[0]]==0\)&&\(dis{{t}_{2}}[inde{{x}_{2}}[1]]\succ 0\)) || (\(dis{{t}_{2}}[inde{{x}_{2}}[0]]\ne 0\) &&\(dis{{t}_{2}}[inde{{x}_{2}}[0]]\prec 0\)), then
25.          SWAP(\(inde{{x}_{2}}[1],inde{{x}_{2}}[2]\));
26.   end if;
27.   if \(\left[ V_{inde{{x}_{1}}[0]}^{1},V_{inde{{x}_{1}}[1]}^{1},V_{inde{{x}_{2}}[0]}^{2},V_{inde{{x}_{2}}[1]}^{2} \right]\succ 0||\left[ V_{inde{{x}_{1}}[0]}^{1},V_{inde{{x}_{1}}[2]}^{1},V_{inde{{x}_{2}}[2]}^{2},V_{inde{{x}_{2}}[0]}^{2} \right]\succ 0\), then
28.          return FALSE;
29.   else
30.          return TRUE;
31.   end if;

\(\operatorname{REORDER}(dist,index)\)
/* \(dist\)是一个数组,存储一个三角形的三个顶点到另一个三角形所在平面的有符号距离,\(index\)是一个数组,表示三角形三个顶点的索引数组 */
1.    \(k=0\);
2.    if \(dist[1]\prec dist[k]\), then
3.           \(k=1\);
4.    else if \(dist[2]\prec dist[k]\), then
5.           \(k=2\);
6.    end if;
7.    \(i=(k+1)%3,j=(k+2)%3\);
8.    if \(dist[k]==0\), then
9.           if \(dist[i]==0\), then
10.                 \(k=j\);
11.          else if \(dist[j]==0\), then
12.                 \(k=i\);
13.          end if;
14.   else
15.          if \(dist[i]\prec 0\), then
16.                 \(k=j\);
17.          else if \(dist[j]\prec 0\), then
18.                 \(k=i\);
19.          end if;
20.   end if;
21.   \(index[0]=k,index[1]=(k+1)%3,index[2]=(k+2)%3\);

4.4.4. ERIT法

Held[4](1997)实现了一个名为ERIT的三维空间的相交测试包,里面描述了一种三角形与三角形相交测试的算法。

2015-3-23 11-25-23

图4.16 三角形\({{T}_{1}}\)\({{T}_{2}}\)相交,\({{T}_{2}}\)与三角形\({{T}_{1}}\)所在的平面相交于线段\(S\)

如图4.16所示,首先根据三角形\({{T}_{1}}\)的三个顶点,初始化平面\({{\pi }_{1}}\),判断三角形\({{T}_{2}}\)的三个顶点是否在平面\({{\pi }_{1}}\)的同一侧。如果在同一侧,则两个三角形不可能相交;否则,两个三角形可能会发生相交。如果两个三角形共面,可以把它们投影到一个轴对齐的二维平面上,将三维的问题转化为二维的问题。同样,需要判断\({{T}_{1}}\)的三个顶点与平面\({{\pi }_{2}}\)的关系,这一步与间隔重叠测试法是相同的。

接着计算出三角形\({{T}_{2}}\)\({{T}_{1}}\)所在的平面\({{\pi }_{1}}\)的交线\(S\),可以求出三角形\({{T}_{2}}\)的三条线段\(\overline{V_{0}^{2}V_{1}^{2}}\)\(\overline{V_{1}^{2}V_{2}^{2}}\)\(\overline{V_{2}^{2}V_{0}^{2}}\)与平面\({{\pi }_{1}}\)的交点。这种方法需要三次求线段与平面的相交操作,可以对顶点进行重排列,使得一个顶点在平面的一侧,另外两个顶点在平面的另一侧,例如顶点\(V_{1}^{2}\)在平面\({{\pi }_{1}}\)的一侧,顶点\(V_{0}^{2}\)\(V_{2}^{2}\)在平面的另外一侧,接着求线段\(\overline{V_{0}^{2}V_{1}^{2}}\)\(\overline{V_{1}^{2}V_{2}^{2}}\)与平面\({{\pi }_{1}}\)的相交即可,这样只需要两次求线段和平面的相交操作。

如果交线\(S\)完全包含在三角形\({{T}_{1}}\)中,或者与三角形\({{T}_{1}}\)相交,那么\({{T}_{2}}\)\({{T}_{1}}\)相交;否则,彼此不相交。判断交线\(S\)与三角形\({{T}_{1}}\)相交,可以把三维的点沿轴对齐投影到二维平面上,转化为判断二维空间上线段与三角形的相交测试。这样,只要判断线段与三角形的三条边的相交测试即可。

spacer

Leave a reply