浏览量:339

3.5. 线性对象的相交

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

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

3.5. 线性对象的相交

本小节重点介绍二维空间上线性对象之间的相交测试算法,采用参数方程法可以解决二维空间上直线与直线、直线与射线、直线与线段、射线与射线、射线与线段、线段与线段的相交测试问题,对于线段与线段的相交测试问题,还介绍了交叉跨越法和Antonio极简法这两种算法,最后简单的介绍了三种解决三维空间上线性对象相交测试的方法。

3.5.1. 直线与直线的相交

问题描述:两条二维空间上的直线\({P_0} + s{\vec d_0}\)与\({P_1} + t{\vec d_1}\),\(t,s \in \left( { – \infty , + \infty } \right)\)之间的相交测试。

两条直线之间只有三种关系:相交、平行、重合。

在判定算法前,先介绍下二维向量的基础知识,二维向量叉积的计算结果是一个常数,计算公式为:

\[\vec w \times \vec v = ({w_x},{w_y}) \times ({v_x},{v_y}) = {w_x}{v_y} – {w_y}{v_x} \tag{3.26}\]

二维向量有三条重要的性质:

  1. \(\left| {\vec w \times \vec v} \right| = \left\| {\vec w} \right\|\left\| {\vec v} \right\|\left| {\sin \theta } \right|\),其中θ是向量\(\vec w\)与向量\(\vec v\)之间的夹角;
  2. \(\vec w \times \vec v = – \vec v \times \vec w\);
  3. \(\vec w \times \vec w = \vec 0\);

接着介绍两条直线之间的关系判定算法,可以分为两种情况来讨论:

1.  平行或者重合的情况

由叉积i性质,可知,如果\(\left| {{{\vec d}_0} \times {{\vec d}_1}} \right| = 0\),说明两条直线的夹角是0,即两条直线是重合或者平行关系;否则,两条直线必相交。

2015-3-22 17-30-48

图3.12 两条直线的相交测试

接着判定是平行还是重合,如图3.12所示,设\(\vec \Delta = {P_1} – {P_0}\),通过条件(3.27)是否成立来确定两者的关系,如果条件成立,则两条直线重合,否则,它们平行。(3.27)中的两个等式是等价的,即任意一个等式成立,就可以得出另外一个等式也成立,反之,任意一个等式不成立,则另外一个等式也不成立。

\[\left( {\vec \Delta \times {{\vec d}_0} = 0} \right) \vee \left( {\vec \Delta \times {{\vec d}_1} = 0} \right) \tag{3.27}\]

2.  相交的情况

如果两条直线相交,则求出它们的交点。当\({P_0} + s{\vec d_0} = {P_1} + t{\vec d_1}\)时,移项得:

\[s{\vec d_0} – t{\vec d_1} = {P_1} – {P_0} = \vec \Delta \tag{3.28}\]

把等式两边都叉乘上向量\({\vec d_0}\)和\({\vec d_1}\),有:

\[{\vec d_0} \times {\vec d_1}t = \vec \Delta \times {\vec d_0},{\vec d_0} \times {\vec d_1}s = \vec \Delta \times {\vec d_1} \tag{3.29}\]

这是一个关于\(s\),\(t\)的二元一次方程组,可以计算出\(s\)和\(t\)的值

\[t = \frac{{\vec \Delta \times {{\vec d}_0}}}{{{{\vec d}_0} \times {{\vec d}_1}}},s = \frac{{\vec \Delta \times {{\vec d}_1}}}{{{{\vec d}_0} \times {{\vec d}_1}}} \tag{3.30}\]

把求解出的\(s\)或者\(t\)的值,代入直线的参数方程,就可以计算出交点。

算法的伪码如下所示:

判定两条直线\({P_0} + s{\vec d_0}\)和\({P_1} + t{\vec d_1}\),\(t,s \in R\)的关系,若相交,求解出交点\(Q\)
return ({OVERLAPPING,PARALLEL,INTERSECTING})
1.    \(K = {\vec d_0} \times {\vec d_1},\vec \Delta = {P_1} – {P_0}\);
2.    if \(K = = 0\),then
3.           if \(\vec \Delta \times {\vec d_0} = = 0\) (或\(\vec \Delta \times {\vec d_1} = = 0\)), then
4.                  return OVERLAPPING;
5.           else
6.                  return PARALLEL;
7.           end if;
8.    else
9.           \(t = \left( {\vec \Delta \times {{\vec d}_0}} \right)/K\)或\(s = \left( {\vec \Delta \times {{\vec d}_1}} \right)/K\);
10.          \(Q = {P_0} + s{\vec d_0}\)或\(Q = {P_1} + t{\vec d_1}\);
11.          return INTERSECTING;
12.   end if;

在实现过程中需要注意一些细节,运用浮点数运算来区分平行和不平行,当\(\left| {{{\vec d}_0} \times {{\vec d}_1}} \right|\)接近于0时,可能得到非常奇怪的结果。由二维叉积的性质i,有\(\left| {{{\vec d}_0} \times {{\vec d}_1}} \right| = \left\| {{{\vec d}_0}} \right\|\left\| {{{\vec d}_1}} \right\| \cdot \left| {\sin \theta } \right|\),如果分量\(\left\| {{{\vec d}_0}} \right\|\)或者\(\left\| {{{\vec d}_1}} \right\|\)非常的小,都可以导致两个向量的叉积结果变得非常的小,甚至于接近0,所以如果\(\left| {{{\vec d}_0} \times {{\vec d}_1}} \right|\)接近0,并不能保证\(\left| {\sin \theta } \right|\)接近0,例如两个长度非常小的、互相垂直的向量叉积,结果也可能接近0。有两种方法可以解决这个问题:

  1. 限制两个叉积操作的向量的长度,比如要求直线的方向向量都是归一化的,即长度为1,就避免了这个问题;
  2. 可以采用不等式(3.31)来判断夹角\(\theta \)是否接近于0,不等式成立,则夹角\(\theta \)为0,否则,不为0。

\[{\left| {{{\vec d}_0} \times {{\vec d}_1}} \right|^2} \prec {\varepsilon ^2}{\left\| {{{\vec d}_0}} \right\|^2}{\left\| {{{\vec d}_1}} \right\|^2} \tag{3.31}\]

3.5.2. 直线与射线的相交测试

问题描述:二维空间上的直线\({P_0} + s{\vec d_0}\)与射线\({P_1} + t{\vec d_1}\),\(s \in R,t \in [0, + \infty )\)之间的相交测试。

2015-3-22 17-31-06

图3.13 直线与射线的四种关系,(a)平行,(b)重合,(c)相交,(d)分离

直线与射线的关系,除了平行、重合、相交这三种关系外,还可能是分离,如图3.13所示。这里指的分离关系是为区别于上面三种情况而做出的表述。算法跟直线与直线的相交测试相似,不再赘述,算法的伪码如下所示,注意跟直线与直线的相交测试作对比:

判定直线\({P_0} + s{\vec d_0}\)和射线\({P_1} + t{\vec d_1}\),\(s \in R,t \in [0, + \infty )\)的关系,若相交,求解出交点\(Q\)
return ({OVERLAPPING,PARALLEL,INTERSECTING,DISJOINT})
1.    \(K = {\vec d_0} \times {\vec d_1},\vec \Delta = {P_1} – {P_0}\);
2.    if \(K = = 0\),then
3.           if \(\vec \Delta \times {\vec d_0} = = 0\) (或\(\vec \Delta \times {\vec d_1} = = 0\) ), then
4.                  return OVERLAPPING;
5.           else
6.                  return PARALLEL;
7.           end if;
8.    else
9.           \(t = \left( {\vec \Delta \times {{\vec d}_0}} \right)/K\);
10.          if \(t \prec 0\), then
11.                 return DISJOINT;
12.          else
13.                 \(Q = {P_1} + t{\vec d_1}\);
14.                 return INTERSECTING;
15.          end if;
16.   end if;

3.5.3. 直线与线段的相交测试

问题描述:二维空间上的直线\({P_0} + s{\vec d_0}\)与线段\({P_1} + t{\vec d_1}\),\(s \in \left( { – \infty , + \infty } \right),t \in [0,1]\)之间的相交测试。

直线与线段的关系,可以分为四种关系:平行、重合、相交、分离,与射线不同的是,射线的要求是\(t \prec 0\),而线段的要求是\(0 \le t \le 1\),算法伪码不再赘述。

3.5.4. 射线与射线的相交测试

问题描述:二维空间上的射线\({P_0} + s{\vec d_0}\)与射线\({P_1} + t{\vec d_1}\),\(s,t \in [0, + \infty )\)之间的相交测试。

射线和射线之间共有四种关系:平行、重合、相交、分离。

2015-3-22 17-31-28

图3.14 分离的两种情况,(a)两条射线在同一条直线上;(b)两条射线夹角不为0

分离关系有两种情况,如图3.14所示:(a)如果两条射线在同一条直线上,它们可能是分离关系;(b)如果两条射线的夹角不为0,它们也可能是分离关系。

2015-3-22 17-31-37

图3.15 相交的两种特殊情况,(a)两条射线在同一条直线上,两条射线的原点重合;(b)两条射线的夹角不为0时,相交于一点

相交关系有两种情况,如图3.15所示:(a)如果两条射线在一条直线上,它们可能相交于一点;(b)如果两条射线的夹角不为0,它们可能相交于一点。

判定算法是基于直线与直线的相交测试算法,但是当两条射线在同一个直线上,可以有相交、分离和重合三种关系,如图3.16所示。点积的性质有\(\vec w \cdot \vec n = \left\| {\vec w} \right\| \cdot \left\| {\vec n} \right\| \cdot \cos \theta ,\theta \)表示两个向量之间的夹角,如果\(\vec w \cdot \vec n \prec 0\),则\(\theta \)大于90;如果\(\vec w \cdot \vec n \succ 0\),则\(\theta \)小于90;如果\(\vec w \cdot \vec n = 0\),则\(\theta \)等于90。所以,令\(\vec \Delta = {P_1} – {P_0}\),可以得到如下结论:

  1. 若满足条件\(\left( {\vec \Delta \cdot {{\vec d}_0} \succ 0} \right) \vee \left( {\vec \Delta \cdot {{\vec d}_1} \prec 0} \right)\),则两条射线重合;
  2. 若满足条件\(\left( {\vec \Delta \cdot {{\vec d}_0} \prec 0} \right) \wedge \left( {\vec \Delta \cdot {{\vec d}_1} \succ 0} \right)\),则两条射线分离;
  3. 否则,两条射线相交于原点。

算法伪码跟“射线与射线的相交测试”相似,不再赘述。

3.5.6. 线段与线段的相交测试

问题描述:二维空间两条线段\(\overline {{P_0}{P_1}} \)和\(\overline {{P_2}{P_3}} \)的相交测试,其中\({P_k} = ({x_k},{y_k}),0 \le k \le 3\)。

至少有三种方法,可以判定线段与线段的相交测试。第一种方法,采用的是参数方程的方法,该方法不仅能判断两条线段是否相交,还能计算出它们的交点。第二种方法,Corment et al[1](2001)描述了一种相交测试的方法,该方法使用判断线段是否跨越直线的思想。第三种方法,Antonio[5](1992)描述的一种高效判断线段相交测试的方法,如果不考虑两条线段在同一条直线上的情况,该算法仅需要9个加法,6个乘法即可得出结果,如果考虑线段位于同一条直线上的情况,则需要额外的判断,但是该算法无法求出交点,因此适合只需要相交判断而不需要求交点的应用。

方法一. 参数方程法

线段与线段之间总共有四种关系:平行、重合、相交、分离。两条线段表示成参数方程的形式,分别是\({P_0} + t({P_1} – {P_0}),0 \le t \le 1\)和\({P_2} + s({P_3} – {P_2}),0 \le s \le 1\),跟直线与直线的相交测试类似,只是\(s\)和\(t\)的限制不同。

线段与线段的相交测试分两种情况,一种情况是两条线段所在的直线相交,采用直线与直线相交测试的方法,求\(s\)和\(t\)的值,判定\(s\)和\(t\) 的值是否在\([0,1]\)范围内,如果在,两条线段相交,否则,不相交。

2015-3-22 21-43-27

图3.18 两条线段在同一条直线上的情况,(a)分离;(b)重叠;(c)相交

另外一种情况,就是当两条线段在同一条直线上时,如图3.18所示。在同一条直线上的两条线段的关系判定,很容易想到的一种方法就是:把一条线段上的两个点代入另一条线段的参数方程中,算出参数,例如把\({P_2}\)和\({P_2}\)代入线段\(\overline {{P_0}{P_1}} \)的参数方程中,算出相应的值\({t_0}\)和\({t_1}\)。设\({t_0} < {t_1}\),如果\({t_0} = 1\)或者\({t_1} = 0\),则两条线段相交;如果\({t_0} \succ 1\)或者\({t_1} \prec 0\),则两条线段分离;否则,线段重合。求解\({t_0}\)和\({t_1}\)时,需要除以\(({P_1} – {P_0})\)的\(x\)分量或者\(y\)分量,选择绝对值更大的分量,避免出现0的情况。可以注意到,求出值\({t_0}\)和\({t_1}\)后,并不需要利用它们求解,只需要依据它们的大小关系判断点的位置,因此可以在不等式的两边同时乘以分母,避免除法操作。

线段与线段的相交检测的算法伪码如下所示:

求线段\(\overline {{P_0}{P_1}} \)和线段\(\overline {{P_2}{P_3}} \)的相交测试,两条线段可以分别用参数方程\({P_0} + s \cdot {\vec d_0},0 \le s \le 1\)和\({P_2} + t \cdot {\vec d_1},0 \le t \le 1\)表示,其中\({\vec d_0} = {P_1} – {P_0},{\vec d_1} = {P_3} – {P_2}\),若相交,求出交点\(Q\)
return ({OVERLAPPING,PARALLEL,INTERSECTING,DISJOINT})
1.    \({\vec d_0} = {P_1} – {P_0},{\vec d_1} = {P_3} – {P_2}\);
2.    \(K = {\vec d_0} \times {\vec d_1},\vec \Delta = {P_2} – {P_0}\);
3.    if\(K = = 0\), then
4.           if\(\left| {{{\vec d}_{0,x}}} \right| \succ \left| {{{\vec d}_{0,y}}} \right|\), then
5.                  \({t_0} = {x_2} – {x_0},{t_1} = {x_3} – {x_0},d = {\vec d_{0,x}}\);
6.           else
7.                  \({t_0} = {y_2} – {y_0},{t_1} = {y_3} – {y_0},d = {\vec d_{0,y}}\);
8.           end if;
9.           if\(d \prec 0\), then
10.                 \({t_0} = – {t_0},{t_1} = – {t_1},d = – d\);
11.          end if;
12.          if\({t_0} \succ {t_1}\),then
13.                 swap(\({t_0}\),\({t_1}\)); //交换\({t_0}\),\({t_1}\)的值
14.          end if;
15.          if\({t_0} \succ d||{t_1} \prec 0\),then
16.                 return DISJOINT;
17.          else if\({t_1} = = 0\), then
18.                 \(Q = {P_0}\);
19.                 return INTERSECTING;
20.          else if\({t_0} = = d\), then
21.                 \(Q = {P_1}\);
22.                 return INTERSECTING;
23.          else
24.                 return OVERLAPPING;
25.          end if
26.   else
27.          \(t = \left( {\vec \Delta \times {{\vec d}_0}} \right)/K\),\(s = \left( {\vec \Delta \times {{\vec d}_1}} \right)/K\);
28.          if\(\left( {0 \le s \le 1} \right)\& \& \left( {0 \le t \le 1} \right)\), then
29.                 \(Q = {P_0} + s({P_1} – {P_0})\);
30.                 return INTERSECTING;
31.          else
32.                 return DISJOINT;
33.          end if;
34.   end if;

方法二. 交叉跨越法

除了采用参数方程的方法,Corment et al[1](2001)描述了另外一种判断两条线段相交的方法。该算法的基本思想是:若点\({P_0}\)位于某条直线的一边,而点\({P_1}\)位于该直线的另一边,则称线段\(\overline {{P_0}{P_1}} \)跨越了这条直线;若点\({P_0}\)和\({P_1}\)恰好落在直线上,即出现边界情况,需要具体的讨论。两条线段相交当且仅当下面两个条件至少成立一个:

  1.  每条线段都跨越了包含另一条线段的直线;
  2. 一条线段的某个端点落在另一条线段上;

定义一个函数\({\mathop{\rm ORIENTATION}\nolimits} (p,q,r)\),若三个点\(p,q,r\)是逆时针顺序的,则返回1;若三点是顺时针方向,则返回-1;否则,三点共线,则返回0。则有:

\({\mathop{\rm ORIENTATION}\nolimits} (p,q,r)\)
1.    \(d = (q – p) \times (r – p)\);
2.    if d < 0, then
3.           return -1;
4.    else if d > 0, then
5.           return 1;
6.    else
7.           return 0;
8.    end if;

2015-3-22 21-43-41

图3.19 交叉跨越法判定两条线段是否相交

对于线段\(\overline {{P_0}{P_1}} \)和\(\overline {{P_2}{P_3}} \),如果对于\(\left( {{P_0},{P_1},{P_2}} \right)\)与\(\left( {{P_0},{P_1},{P_3}} \right)\),一组是逆时针方向,另一组是顺时针方向,说明点\({P_2},{P_3}\)分别位于线段\(\overline {{P_0}{P_1}} \)的两侧。如果\({P_2},{P_3}\)位于线段\(\overline {{P_0}{P_1}} \)的两侧且\({P_0},{P_1}\)位于线段\(\overline {{P_2}{P_3}} \)的两侧,则两条线段相交,如图3.19(a)所示;如果存在一组点对,在线段的同一侧,就说明两条线段不相交,如图4.19(b)所示,虽然\({P_0},{P_1}\)在线段\(\overline {{P_2}{P_3}} \)的两侧,但是\({P_2},{P_3}\)在线段\(\overline {{P_0}{P_1}} \)的同一侧,因此两条线段不相交。

2015-3-22 21-43-53

图3.20 线段的一个点在另一条线段所在的直线上

现在考虑三点共线的情况,如图3.20所示,图(a)中,有\(\left( {{P_0},{P_1},{P_2}} \right)\)共线且点\({P_2}\)在线段\(\overline {{P_0}{P_1}} \)上,那么两条线段相交于点\({P_2}\);但是,对于图(b),\(\left( {{P_0},{P_1},{P_2}} \right)\)共线,点\({P_2}\)不在线段\(\overline {{P_0}{P_1}} \)上,那么两条线段分离。

线段与线段的相交测试的交叉跨越法的伪码如下所示:

线段\(\overline {{P_0}{P_1}} \)和线段\(\overline {{P_2}{P_3}} \)的相交测试
return ({TRUE,FALSE})
1.    \({d_1} = {\mathop{\rm ORIENTATION}\nolimits} ({P_0},{P_1},{P_2})\), \({d_2} = {\mathop{\rm ORIENTATION}\nolimits} ({P_0},{P_1},{P_3})\);
\({d_3} = {\mathop{\rm ORIENTATION}\nolimits} ({P_2},{P_3},{P_0})\); \({d_4} = {\mathop{\rm ORIENTATION}\nolimits} ({P_2},{P_3},{P_1})\);
2.    if ((\({d_1} \succ 0\)且\({d_2} \prec 0\))或(\({d_1} \prec 0\)且\({d_2} \succ 0\)))且
((\({d_3} \succ 0\)且\({d_4} \prec 0\))或(\({d_3} \prec 0\)且\({d_4} \succ 0\))), then
3.           return TRUE;
4.    else if \({d_1} = 0\)且点\({P_2}\)在线段\(\overline {{P_0}{P_1}} \)上, then
5.           return TRUE;
6.    else if \({d_2} = 0\)且点\({P_3}\)在线段\(\overline {{P_0}{P_1}} \)上, then
7.           return TRUE;
8.    else if \({d_3} = 0\)且点\({P_0}\)在线段\(\overline {{P_2}{P_3}} \)上, then
9.           return TRUE;
10.   else if \({d_4} = 0\)且点\({P_1}\)在线段\(\overline {{P_2}{P_3}} \)上, then
11.          return TRUE;
12.   else
13.          RETURN FALSE;
14.   end if;

方法三. Antonio极简法

在一些应用中,只需要判断两条线段是否相交,而不需求出交点。Antonio[5](1992)就描述了一种只用于判断两条线段是否相交的方法,该方法通过较多的比较和排除操作来实现,避免了除法操作,在最坏情况下,只需要9个加法操作和6个除法操作即可完成,算法非常高效。

2015-3-22 21-44-04

图3.21 线段\(\overline {{P_0}{P_1}} \)和线段\(\overline {{P_2}{P_3}} \)相交于点\(P*\)

如图3.21所示,设有两条线段\(\overline {{P_2}{P_3}} \)和\(\overline {{P_2}{P_3}} \),相交于点\(P*\),交点\(P*\)如等式(3.31)所示

\[\begin{array}{l}P* = {P_0} + \alpha ({P_1} – {P_0})\\P* = {P_2} + \beta ({P_3} – {P_2})\end{array} \tag{3.31}\]

两式相减,得

\[({P_0} – {P_2}) + \alpha ({P_1} – {P_0}) = \beta ({P_2} – {P_3}) \tag{3.32}\]

\[\begin{array}{l}A = {P_1} – {P_0}\\B = {P_2} – {P_3}\\C = {P_0} – {P_2}\end{array} \tag{3.33}\]

解等式(3.32),得到

\[\alpha = \frac{{{B_y}{C_x} – {B_x}{C_y}}}{{{A_y}{B_x} – {A_x}{B_y}}},\beta = \frac{{{A_x}{C_y} – {A_y}{C_x}}}{{{A_y}{B_x} – {A_x}{B_y}}} \tag{3.34}\]

注意到等式(3.34)中的分母相同,只需要一次计算,所以一共只需要9个加法操作和6个乘法操作。由于最终不需要交点值,所以并不需要计算出\(\alpha \)和\(\beta \)的值,只需要测试它们是否介于\([0,1]\)范围内,这样可以避免除法操作。此外,在实现的时候,有个小技巧,先判断\(\alpha \)是否在\([0,1]\)范围内,如果不在范围内,就不需要再对\(\beta \)计算;否则,计算出\(\beta \),再判断\(\beta \)是否在\([0,1]\)范围内。采用这种方法,在一些测试样例中,可能减少对\(\beta \)不必要的计算。

线段与线段的相交测试的Antonio极简法的伪码如下所示:

判断线段\(\overline {{P_0}{P_1}} \)和线段\(\overline {{P_2}{P_3}} \)是否相交
return ({TRUE,FALSE})
1.    \(A = {P_1} – {P_0},B = {P_2} – {P_3},C = {P_0} – {P_2}\);
2.    \(a = {B_y}{C_x} – {B_x}{C_y},b = {A_x}{C_y} – {A_y}{C_x},c = {A_y}{B_x} – {A_x}{B_y}\);
3.    if\(c \succ 0\), then
4.           if \(a \prec 0\)或\(a \succ c\),then
5.                  return FALSE;
6.           else if\(b \prec 0\)或\(b \succ c\), then
7.                  return FALSE;
8.           else
9.                  return TRUE;
10.          end if;
11.   else if\(c \prec 0\), then
12.          if\(a \succ 0\)或\(a \prec c\),then
13.                 return FALSE;
14.          else if\(b \succ 0\)或\(b \prec c\), then
15.                 return FALSE;
16.          else
17.                 return TRUE;
18.          end if;
19.   else
20.          if\(a \ne 0\), then
21.                 return FALSE;
22.          end if;
23.          if\(\left| {{A_x}} \right| \succ \left| {{A_y}} \right|\), then
24.                 \({t_0} = {x_2} – {x_0},{t_1} = {x_3} – {x_0},d = {A_x}\);
25.          else
26.                 \({t_0} = {y_2} – {y_0},{t_1} = {y_3} – {y_0},d = {A_y}\);
27.          end if;
28.          if\(d \prec 0\), then
29.                 \({t_0} = – {t_0},{t_1} = – {t_1},d = – d\);
30.          end if;
31.          if\({t_0} \succ {t_1}\),then
32.                 swap(\({t_0}\),\({t_1}\)); //交换\({t_0}\),\({t_1}\)的值
33.          end if;
34.          if \({t_1} \prec 0||{t_0} \succ d\),then
35.                 return FALSE;
36.          else
37.                 return TRUE;
38.          end if;
39.   end if;

3.5.7. 三维空间线性对象间的相交

问题描述:三维空间下的两条线性对象\({L_0}(s) = {P_0} + s{\vec d_0}\)和\({L_1}(t) = {P_1} + t{\vec d_1}\)的相交测试。

首先进行共面检测,若两条线性对象不共面,则它们必不相交。共面检测,可能帮排除很多不必要的计算。判断两条线性对象是否共面的方法是:设\(\vec n = {\vec d_0} \times {\vec d_1}\),若\(\vec n \cdot ({P_0} – {P_1}) = 0\),则两条线性对象共面;否则,不共面。

对于共面的两条线性对象的相交检测,至少有三种方法。

方法一. 参数方程法

Akenine-Möller et al[4](2011)描述了一种方法,现在考虑直线与直线的相交测试,则两条直线的相交判断的推导过程,如下所示:

1: \({L_0}(s) = {L_1}(t)\)
2: \({P_0} + s{\vec d_0} = {P_1} + t{\vec d_1}\)
3: \(\left\{ {\begin{array}{*{20}{c}}{s{{\vec d}_0} \times {{\vec d}_1} = ({P_1} – {P_0}) \times {{\vec d}_1}}\\{t{{\vec d}_0} \times {{\vec d}_1} = ({P_1} – {P_0}) \times {{\vec d}_0}}\end{array}} \right.\)
4: \(\left\{ {\begin{array}{*{20}{c}}{s\left( {{{\vec d}_0} \times {{\vec d}_1}} \right) \cdot \left( {{{\vec d}_0} \times {{\vec d}_1}} \right) = \left[ {({P_1} – {P_0}) \times {{\vec d}_1}} \right] \cdot \left( {{{\vec d}_0} \times {{\vec d}_1}} \right)}\\{t\left( {{{\vec d}_0} \times {{\vec d}_1}} \right)\left( {{{\vec d}_0} \times {{\vec d}_1}} \right) = \left[ {({P_1} – {P_0}) \times {{\vec d}_0}} \right] \cdot \left( {{{\vec d}_0} \times {{\vec d}_1}} \right)}\end{array}} \right.\)
5:\(\left\{ {\begin{array}{*{20}{c}}{s = \frac{{\left[ {({P_1} – {P_0}) \times {{\vec d}_1}} \right] \cdot \left( {{{\vec d}_0} \times {{\vec d}_1}} \right)}}{{{{\left\| {{{\vec d}_0} \times {{\vec d}_1}} \right\|}^2}}}}\\{t = \frac{{\left[ {({P_1} – {P_0}) \times {{\vec d}_0}} \right] \cdot \left( {{{\vec d}_0} \times {{\vec d}_1}} \right)}}{{{{\left\| {{{\vec d}_0} \times {{\vec d}_1}} \right\|}^2}}}}\end{array}} \right.\)

当\({\left\| {{{\vec d}_0} \times {{\vec d}_1}} \right\|^2}\)等于0时,则这两条直线互相平行或者重合的。

当\({\left\| {{{\vec d}_0} \times {{\vec d}_1}} \right\|^2}\)不等于0时,若两条直线不共面,则求出\(s\)和\(t\)值,代入相应的参数方程,就可以求出两条直线上距离最小的两个点;若两条直线共面,则求出\(s\)和\(t\)值后,就可以计算出两条直线的交点了。

如果不是两条直线的相交检测,而是任意两条线性对象之间的相交测试,例如直线、射线、线段,这时候就得考虑\(s\)和\(t\)限定的范围,它的判定与二维线性对象的相交检测判定方法相似,这里不再赘述。

方法二. 投影法

对于两条共面的线性对象的相交检测,可以把它们投影到二维平面上,若它们在二维平面上相交,求出\(s\)和\(t\)的值,然后就可以计算出三维交点;若它们在二维平面平行,则它们在三维平面也是平行的;若它们在二维平面重叠,则它们在三维平面也是重叠的。

在将三维线性对象投影二维平面上时,若任意选择一个投影面,就可能发生错误,例如,把三维直线\(L(s) = (0,0,0) + s \cdot (0,1,0)\)投影到\(XZ\)平面上,那么该直线可能就退化成一个点。可以采用的做法是:令\(\vec n = ({n_x},{n_y},{n_z}) = {\vec d_0} \times {\vec d_1}\),求出法向量\(\vec n\)分量的绝对值最大的轴,即\({n_{\max }} = \max (\left| {{n_x}} \right|,\left| {{n_y}} \right|,\left| {{n_z}} \right|)\),若\({n_{\max }} = \left| {{n_x}} \right|\),则两条线性对象投影到\(YZ\)平面上;若\({n_{\max }} = \left| {{n_y}} \right|\),则两条线性对象投影到\(ZX\)平面上;否则,两条线性对象投影到\(XY\)平面上。投影法把三维问题降低为二维,简化了问题,是一种解决三维计算几何问题很通用的方法。

方法三. 距离法

采用距离法,也可判定两条线性对象是否相交。首先计算出两条线性对象之间的距离,如果距离不为零,则它们一定不相交;如果距离为零,再判断两条线性对象是否重叠。至此,就可以判定是否相交,而三维空间上线性对象的距离计算参见第3.4节。

spacer

Leave a reply