浏览量:448

9.2. 包围盒

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

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

9.2. 包围盒

9.2.1. 最小有向包围盒的创建

问题描述:给定一个点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),求包围该点集的最小有向包围盒。

通常这个问题可以简化为求凸多面体的最小有向包围盒问题,关于最小有向包围盒的创建方法有很多[1,2,3,4,5,8],O'Rourke[1]在1985年提出了一种复杂度是\(O({{n}^{3}})\)的精确算法。包围盒在碰撞检测中有很重要的应用,为了提高效率,可以采用更高效的有向包围盒估计算法,评价最小有向包围盒估计算法有两个非常重要的指标:效率和紧密度,即要在尽可能短的时间内,创建出尽可能紧密的拟合点集的包围盒。Barequet和Har-Peled[3](2001)提出了两种估计算法,一种实现难度较大、复杂度是\(O(n+1/{{\varepsilon }^{4.5}})\)的算法(其中\(0\prec \varepsilon \le 1\)),另外一种相对较容易实现、复杂度是\(O(n\log n+n/{{\varepsilon }^{4.5}})\)的算法。而Gottschalk[4,5]则提出了一种线性的估计算法,虽然不是最优拟合,但是紧密度上也表示很好,本节将介绍该算法。

首先计算出点集的三维凸包,参见第九章,可以得到\(n\)个三角形,记为\(\Delta {{p}^{k}}{{q}^{k}}{{r}^{k}},0\le k\prec n\),其中\({{p}^{k}}\)\({{q}^{k}}\)\({{r}^{k}}\)分别是三角形的3个顶点,三角形的面积记为\({{A}^{k}}\),凸包的整个面积就记作

\[{A^M} = \sum\limits_{k = 0}^{n - 1} {{A^k}} \]

此外,三角形的质心记为\({{m}^{k}}=({{p}^{k}}+{{q}^{k}}+{{r}^{k}})/3\),也就是3个顶点的平均值,整个凸多面体的质心的加权平均值记为

\[{M^M} = \frac{1}{{{A^M}}}\sum\limits_{k = 0}^{n - 1} {{A^k}{m^k}} \]

上角标\(k\)表示第\(k\)个三角形,上角标\(M\)表示整个凸多面体,下角标\(i\)表示第\(i\)个分量,在三维下\(i=0,1,2\)。表示那么利用这些定义,就可以计算出一个\(3\times 3\)的协方差矩阵,如等式(9.1)所示,它表示点集在三维空间的分布关系,可以使用矩阵的特征向量来表征这个矩阵,它的特征向量也就是所求有向包围盒三个轴的方向向量,计算出它的特征向量并将其归一化,这些向量就是包围盒的方向向量:\({{v}^{0}},{{v}^{1}},{{v}^{2}}\)。协方差矩阵是一个对称矩阵,开源软件包Gmm++[6]提供了求对称矩阵特征向量的对称QR迭代算法。

\[{C_{i,j}} = E[{x_i}{x_j}] - E[{x_i}]E[{x_j}] = \left[ {\left( {\frac{1}{{{A^M}}}\sum\limits_{k = 0}^{n - 1} {\frac{{{A^k}}}{{12}}} (9m_i^km_j^k + p_i^kp_j^k + q_i^kq_j^k + r_i^kr_j^k)} \right) - m_i^Mm_j^M} \right] \tag{9.1}\]

接下来就是找到包围盒的中心和半长,可以将凸包上的点投影到方向向量上,然后找到每个方向上的最大值和最小值\(l_{\min }^{k},l_{\max }^{k}\),其中\(0\le k\le 2\),那么包围盒中心的计算如等式(9.2)所示,包围盒的半长如等式(9.3)所示。

\[C = \frac{{l_{\min }^0 + l_{\max }^0}}{2}{v^0} + \frac{{l_{\min }^1 + l_{\max }^1}}{2}{v^1} + \frac{{l_{\min }^2 + l_{\max }^2}}{2}{v^2} \tag{9.2}\]

\[l_{half}^k = \frac{{l_{\min }^k + l_{\max }^k}}{2} \tag{9.3}\]

接下来介绍等式(9.1)的推导过程。三角形可以用参数方程表示

\[{X^k}(s,t) = {p^k} + s \cdot {u^k} + t \cdot {v^k},s \in [0,1],t \in [0,1 - s] \tag{9.4}\]

其中,\({u^k} = {q^k} - {p^k},{v^k} = {r^k} - {p^k}\)

协方差矩阵能表示为

\[{C_{i,j}} = E[{x_i}{x_j}] - E[{x_i}]E[{x_j}] \tag{9.5}\]

由期望的定义,有

\[E[{x_i}] = \frac{{\int_M {{x_i}dA} }}{{\int_M {dA} }} \tag{9.6}\]

\[E[{x_i}{x_j}] = \frac{{\int_M {{x_i}{x_j}dA} }}{{\int_M {dA} }} \tag{9.7}\]

对于凸多面体的积分,可以看成是每个三角形积分的和,则

\[\int_M {dA} = \sum\limits_{k = 0}^{n - 1} {\int_{{\Delta ^k}} {dA} } = {A^M}\]

所以,等式(9.6)等价为

\[\begin{array}{l}E[{x_i}] = \frac{1}{{{A^M}}}\int_M {{x_i}dA} = \frac{1}{{{A^M}}}\sum\limits_{k = 0}^{n - 1} {\int_{{\Delta ^k}} {{x_i}dA} } = \frac{1}{{{A^M}}}\sum\limits_{k = 0}^{n - 1} {\left\| {{u^k} \times {v^k}} \right\| \cdot \int_0^1 {\int_0^{1 - s} {X_i^k(s,t)dtds} } } \\ = \frac{1}{{{A^M}}}\sum\limits_{k = 0}^{n - 1} {{A^k}m_i^k} = m_i^M\end{array}\]

同理,等式(9.7)可以化简为

\[\begin{array}{l}E[{x_i}{x_j}] = \frac{1}{{{A^M}}}\int_M {{x_i}{x_j}dA} = \frac{1}{{{A^M}}}\sum\limits_{k = 0}^{n - 1} {\left\| {{u^k} \times {v^k}} \right\| \cdot \int_0^1 {\int_0^{1 - s} {X_i^k(s,t) \cdot X_j^k(s,t)dtds} } } \\ = \frac{1}{{{A^M}}}\sum\limits_{k = 0}^{n - 1} {\frac{{{A^k}}}{{12}}} (9m_i^km_j^k + p_i^kp_j^k + q_i^kq_j^k + r_i^kr_j^k)\end{array}\]

把它们代入(9.5)中,就得到等式(9.1)。

协方差矩阵可以表示点集的空间分布关系,协方差方法无法精确的得到体积、表面积、宽最优的包围盒,它只能表示点集的分布估计。以二维空间下的包围盒为例,如图9.2所示,图(a)显示了包围凸多面边\({{P}_{1}}\)的最优包围盒,当多边形的边发生了变换,若用协方差拟合法进行计算,就会得到图(b)实线所示的包围盒,显然包围盒\(OB{{B}_{2}}\)不是凸多边形\({{P}_{2}}\)的最优包围盒。Gottschalk[4]证实,协方差拟合法得到的2D包围盒的面积能控制在最小面积的2倍范围内;推测,协方差拟合法得到的3D包围盒的体积能控制在最小体积的4.63倍范围内。

2015-3-24 15-21-36

图9.2 在二维空间下,协方差拟合法求凸多边形的包围盒

9.2.2. 射线与包围盒的相交测试

包围盒主要有两种:轴对齐包围盒和有向包围盒,Woo[16](1990)提出一种巧妙的算法,通过选择候选面计算相交,称为吴氏算法,Haines[17](1989)提出了一种射线与轴对齐包围盒相交测试的“厚板方法”,Akenine-Möller等[14](2002)把“厚板方法”扩展到射线与有向包围盒的相交测试。吴氏算法和“厚板方法”相比较,性能相当,具体受使用方法、处理器的体系结构等诸多因素的影响[14]。本节将分别介绍射线与轴对齐包围和有向包围盒相交测试的“厚板方法”。

1.    射线与轴对齐包围盒的相交测试

问题描述:射线\(L(t)=P+t\cdot \vec{d}\)与轴对齐包围盒\(\left( {{B}_{\min }},{{B}_{\max }} \right)\)的相交测试,其中, \({{B}_{\min }}=\left( b_{x}^{\min },b_{y}^{\min },b_{z}^{\min } \right),{{B}_{\max }}=\left( b_{x}^{\max },b_{y}^{\max },b_{z}^{\max } \right)\)\(b_{x}^{\min }\prec b_{x}^{\max },b_{y}^{\min }\prec b_{y}^{\max },b_{z}^{\min }\prec b_{z}^{\max },\vec{d}=\left( {{d}_{x}},{{d}_{y}},{{d}_{z}} \right)\)

2015-3-24 15-21-50

图9.3 射线与轴对齐包围盒的相交测试

一个包围盒有6个矩形面,把两个互相平行的矩形看成一块厚板,那么问题就转化为求射线与互相垂直的3块厚板的相交,算法有点类似于Cyrus-Beck的直线裁剪算法。初始阶段,设\({{t}_{0}}=-\infty ,{{t}_{1}}=+\infty \)。首先处理\(YZ\)平面,如图9.3(a)所示,相当于从\(P\)点处,从左往右观察包围盒,判断射线与包围盒上\(X=b_{x}^{\min }\)\(X=b_{x}^{\max }\)处的两个互相平行的平面的相交情况,得到图9.3(b)所示的图,现在需要计算射线与该厚板的相交,若射线与厚板的两个平面相交,必有

\[\left\{ \begin{array}{l}{P_x} + {t_{0,x}}{d_x} = b_x^{\min }\\{P_x} + {t_{1,x}}{d_x} = b_x^{\max }\end{array} \right. \tag{9.8}\]

计算(9.8)式,可以得到

\[{t_{0,x}} = \frac{{b_x^{\min } - {P_x}}}{{{d_x}}},{t_{1,x}} = \frac{{b_x^{\max } - {P_x}}}{{{d_x}}} \tag{9.9}\]

\({{d}_{x}}\ne 0\),设\({{t}_{0,x}}\prec {{t}_{1,x}}\),则取\({{t}_{0}}=\max \left( {{t}_{0,x}},{{t}_{0}} \right)\)\({{t}_{1}}=\min \left( {{t}_{1,x}},{{t}_{1}} \right)\);反之,若\({{d}_{x}}=0\),说明射线与\(YZ\)平面平行,若\({{P}_{x}}\prec b_{x}^{\min }\)或者\({{P}_{x}}\succ b_{x}^{\max }\),则射线与包围盒一定不相交,否则,可能相交,不做进一步的处理。

在处理完\(YZ\)平面后,再分别处理\(XY\)平面和\(ZX\)平面,也采用类似的处理方法。

射线与轴对齐包围盒的相交测试伪码如下所示:

射线\(L(t)=P+t\cdot \vec{d}\)与轴对齐包围盒\({{B}_{\min }}=\left( b_{x}^{\min },b_{y}^{\min },b_{z}^{\min } \right),{{B}_{\max }}=\left( b_{x}^{\max },b_{y}^{\max },b_{z}^{\max } \right)\)的相交测试,若相交,\(Q\)表示返回的交点
return ({DISJOINT, INTERSECTING})
1.    \({{t}_{0}}=-\infty ,{{t}_{1}}=+\infty \);
2.    for each \(i\in \left\{ x,y,z \right\}\)
3.           if \({{d}_{i}}==0\), then
4.                  if \({{P}_{i}}\prec b_{i}^{\min }\) or \({{P}_{i}}\succ b_{i}^{\max }\), then
5.                         return DISJOINT;
6.                  end if;
7.           else
8.                  \({{t}_{0}}'=(b_{i}^{\min }-{{P}_{i}})/{{d}_{i}}\);
9.                  \({{t}_{1}}'=(b_{i}^{\max }-{{P}_{i}})/{{d}_{i}}\);
10.                 if \({{t}_{0}}'\succ {{t}_{1}}'\), then
11.                        swap(\({{t}_{0}}',{{t}_{1}}'\));
12.                 end if;
13.                 \({{t}_{0}}=\max ({{t}_{0}}',{{t}_{0}})\);
14.                 \({{t}_{1}}=\min ({{t}_{1}}',{{t}_{1}})\);
15.                 if \({{t}_{0}}\succ {{t}_{1}}\) or \({{t}_{1}}\prec 0\), then
16.                        return DISJOINT;
17.                 end if;
18.          end if;
19.   end for;
20.   if \({{t}_{0}}\ge 0\), then
21.          \(t={{t}_{0}}\);
22.   else
23.          \(t={{t}_{1}}\);
24.   end if;
25.   \(Q=P+t\vec{d}\);                                                   //交点
26.   return INTERSECTING;

2.    射线与有向包围盒的相交测试

问题描述:射线\(L(t)=P+t\cdot \vec{d}\)与有向包围盒\(C+{{h}_{0}}{{\vec{u}}_{0}}+{{h}_{1}}{{\vec{u}}_{1}}+{{h}_{2}}{{\vec{u}}_{2}}\)的相交测试,其中,\(\vec{d}=\left( {{d}_{x}},{{d}_{y}},{{d}_{z}} \right)\)\(-{{l}_{0}}\le {{h}_{0}}\le {{l}_{0}},-{{l}_{1}}\le {{h}_{1}}\le {{l}_{1}},-{{l}_{2}}\le {{h}_{2}}\le {{l}_{2}},\left\| {{{\vec{u}}}_{0}} \right\|=\left\| {{{\vec{u}}}_{1}} \right\|=\left\| {{{\vec{u}}}_{2}} \right\|=1,{{l}_{0}},{{l}_{1}},{{l}_{2}}\succ 0\)

2015-3-24 15-22-03

图9.4 射线与有向包围盒的相交测试

计算射线与有向包围盒相交的“厚板方法”是上一小节算法的改进,本节只对\({{t}_{0}},{{t}_{1}}\)的计算公式进行介绍,如图9.4所示。设射线跟和轴\({{\vec{u}}_{0}}\)垂直的、且互相平行的两个平面相交,交点分别是\(P+{{t}_{0,x}}\vec{d}\)\(P+{{t}_{1,x}}\vec{d}\),交点沿着\({{\vec{u}}_{0}}\)方向上的投影,有

\[\left\{ \begin{array}{l}\left( {P + {t_{0,x}}\vec d - C} \right) \cdot {{\vec u}_0} = - {l_0}\\\left( {P + {t_{1,x}}\vec d - C} \right) \cdot {{\vec u}_0} = {l_0}\end{array} \right. \tag{9.10}\]

解得

\[{t_{0,x}} = \frac{{\left( {C - P} \right) \cdot {{\vec u}_0} - {l_0}}}{{\vec d \cdot {{\vec u}_0}}},{t_{1,x}} = \frac{{\left( {C - P} \right) \cdot {{\vec u}_0} + {l_0}}}{{\vec d \cdot {{\vec u}_0}}} \tag{9.11}\]

对于与轴\({{\vec{u}}_{1}}\)、轴\({{\vec{u}}_{2}}\)的处理方法也是类似的。射线与有向包围盒的相交测试伪码如下所示:

射线\(L(t)=P+t\cdot \vec{d}\)与有向包围盒\(C+{{h}_{0}}{{\vec{u}}_{0}}+{{h}_{1}}{{\vec{u}}_{1}}+{{h}_{2}}{{\vec{u}}_{2}}\)的相交测试,其中\(\vec{d}=\left( {{d}_{x}},{{d}_{y}},{{d}_{z}} \right)\)\(-{{l}_{0}}\le {{h}_{0}}\le {{l}_{0}},-{{l}_{1}}\le {{h}_{1}}\le {{l}_{1}},-{{l}_{2}}\le {{h}_{2}}\le {{l}_{2}},\left\| {{{\vec{u}}}_{0}} \right\|=\left\| {{{\vec{u}}}_{1}} \right\|=\left\| {{{\vec{u}}}_{2}} \right\|=1,{{l}_{0}},{{l}_{1}},{{l}_{2}}\succ 0\),若相交,\(Q\)表示返回的交点
return ({DISJOINT, INTERSECTING})
1.    \({{t}_{0}}=-\infty ,{{t}_{1}}=+\infty \);
2.    for( \(k=0\) ; \(k\prec 3\) ; \(k=k+1\) )
3.           \(r={{\vec{u}}_{k}}\cdot \vec{d}\);
4.           \(s={{\vec{u}}_{k}}\cdot \left( C-P \right)\);
5.           if \(r==0\), then
6.                  if \(-s-{{l}_{k}}\succ 0\) or \(-s+{{l}_{k}}\prec 0\), then
7.                         return DISJOINT;
8.                  end if;
9.           else
10.                 \({{t}_{0}}'=s-{{l}_{k}}/r\);
11.                 \({{t}_{1}}'=s+{{l}_{k}}/r\);
12.                 if \({{t}_{0}}'\succ {{t}_{1}}'\), then
13.                        swap(\({{t}_{0}}',{{t}_{1}}'\));
14.                 end if;
15.                 \({{t}_{0}}=\max \{{{t}_{0}}',{{t}_{0}}\}\);
16.                 \({{t}_{1}}=\min \{{{t}_{1}}',{{t}_{1}}\}\);
17.                 if \({{t}_{0}}\succ {{t}_{1}}\) or \({{t}_{1}}\prec 0\), then
18.                        return DISJOINT;
19.                 end if;
20.          end if;
21.   end for;
22.   if \({{t}_{0}}\ge 0\), then
23.          \(t={{t}_{0}}\);
24.   else
25.          \(t={{t}_{1}}\);
26.   end if;
27.   \(Q=P+t\vec{d}\);
28.   return INTERSECTING;

9.2.3. 线段与包围盒的重叠测试

问题描述:线段\({{P}_{0}}{{P}_{1}}\)与包围盒\(C+{{h}_{0}}{{\vec{u}}_{0}}+{{h}_{1}}{{\vec{u}}_{1}}+{{h}_{2}}{{\vec{u}}_{2}}\)重叠测试,其中,\(-{{l}_{0}}\le {{h}_{0}}\le {{l}_{0}}\),\(-{{l}_{1}}\le {{h}_{1}}\le {{l}_{1}}\),\(-{{l}_{2}}\le {{h}_{2}}\le {{l}_{2}},\left\| {{{\vec{u}}}_{0}} \right\|=\left\| {{{\vec{u}}}_{1}} \right\|=\left\| {{{\vec{u}}}_{2}} \right\|=1,{{l}_{0}},{{l}_{1}},{{l}_{2}}\succ 0\)

Gregory[22]等(1999)提出了一种基于分离轴理论来判断线段与包围盒是否重叠的算法,本节将详细地描述该算法。

首先需要考虑投影间隔的计算。给定一条经过原点的直线\(L\),它的方向是\(\vec{v}\),设点\(p'\)是点\(p\)在该直线上的投影,那么\(p\cdot \vec{v}/\left\| {\vec{v}} \right\|\)就是点\(p'\)由原点起始沿着直线\(L\)的有符号距离。对于线段\({{P}_{0}}{{P}_{1}}\),它的中点是\(M=\left( {{P}_{0}}+{{P}_{1}} \right)/2\),记向量\(\vec{w}={{P}_{1}}-M\),则线段的两个端点可以表示为\(M+\vec{w}\)\(M-\vec{w}\)\(\left\| {\vec{w}} \right\|\)等于线段长度的一半。线段的中点\(M\)沿着直线\(L\)的有符号距离为

\[{d_s} = \frac{{\vec v \cdot M}}{{\left\| {\vec v} \right\|}} \tag{9.12}\]

线段的半长向量\(\vec{w}\)沿着直线\(L\)的投影长度为

\[{L_s} = \frac{{\left\| {\vec v \cdot \vec w} \right\|}}{{\left\| {\vec v} \right\|}} \tag{9.13}\]

设包围盒的中心是直线\(L\)的原点,那么等式(9.12)就表示包围盒中心到线段中点的投影间隔。包围盒沿着方向\(\vec{v}\)的投影间隔为

\[{L_b} = \frac{{{l_0}\left\| {{{\vec u}_0} \cdot \vec v} \right\| + {l_1}\left\| {{{\vec u}_1} \cdot \vec v} \right\| + {l_2}\left\| {{{\vec u}_2} \cdot \vec v} \right\|}}{{\left\| {\vec v} \right\|}} \tag{9.14}\]

若沿着\(\vec{v}\)方向的轴是线段与包围盒的分离轴,当且仅当满足条件

\[\left\| {{d_s}} \right\| \succ {L_b} + {L_s} \tag{9.15}\]

不等式两边同时乘以大于零的值\(\left\| {\vec{v}} \right\|\),不等式保持不变,以后计算\({{d}_{s}},{{L}_{b}},{{L}_{s}}\)时,不需要再除以\(\left\| {\vec{v}} \right\|\),以减少不必要的计算。

把线段的两个端点,沿着有向包围盒的三条轴方向作投影

\[{P_i}' = \left( {{{\vec u}_0} \cdot ({P_i} - C),{{\vec u}_1} \cdot ({P_i} - C),{{\vec u}_2} \cdot ({P_i} - C)} \right) \tag{9.16}\]

其中,\(i=0,1\)。接下来,只要判断线段\({{P}_{0}}'{{P}_{1}}'\)与轴对齐包围盒\(\left( -{{l}_{0}},-{{l}_{1}},-{{l}_{2}} \right),\left( {{l}_{0}},{{l}_{1}},{{l}_{2}} \right)\)是否重叠。

2015-3-24 15-22-20

图9.5 线段与包围盒的重叠测试

如图9.5所示,轴对齐包围盒的三条轴分别是\({{\vec{d}}_{0}}=\left( 1,0,0 \right),{{\vec{d}}_{1}}=\left( 0,1,0 \right),{{\vec{d}}_{2}}=\left( 0,0,1 \right)\)。现在以\({{\vec{d}}_{0}}\)为例,判断它是否是条分离轴。由于它的\(Y\)分量和\(Z\)分量都是零,所以\({{L}_{b}}={{l}_{0}}\)。线段的半长向量\(\vec{w}\)沿着轴\({{\vec{d}}_{0}}\)的投影长度为\({{L}_{s}}=\left\| {{w}_{x}} \right\|\)。那么,轴\({{\vec{d}}_{0}}\)是线段与包围盒的分离轴,当且仅当满足条件

\[\left\| {{M_x}} \right\| \succ {l_0} + \left\| {{w_x}} \right\| \tag{9.17}\]

对于轴\({{\vec{d}}_{1}}\)和轴\({{\vec{d}}_{2}}\)的处理,也是类似的。

现在考虑由包围盒的三条轴的方向向量与线段的方向向量叉积生成新的方向向量是否是分离轴,即判断轴\({{\vec{d}}_{k}}\times \vec{w}\)是否是线段与包围盒的分离轴,其中\(k\in \left\{ 0,1,2 \right\}\)。以\(k=0\)为例,则\({{\vec{d}}_{0}}\times \vec{w}=\left( 0,-{{w}_{z}},{{w}_{y}} \right)\),则\(\left\| {{d}_{s}} \right\|=\left\| -{{w}_{z}}{{M}_{y}}+{{w}_{y}}{{M}_{z}} \right\|\)\({{L}_{s}}=0\)\({{L}_{b}}={{l}_{1}}\left\| {{w}_{z}} \right\|+{{l}_{2}}\left\| {{w}_{y}} \right\|\),那么,轴\({{\vec{d}}_{0}}\times \vec{w}\)是线段与包围盒的分离轴,当且仅当满足条件

\[\left\| { - {w_z}{M_y} + {w_y}{M_z}} \right\| \succ {l_1}\left\| {{w_z}} \right\| + {l_2}\left\| {{w_y}} \right\|\]

对于轴\({{\vec{d}}_{1}}\times \vec{w}\)和轴\({{\vec{d}}_{2}}\times \vec{w}\)也可以采用类似的方法推导出来。

基于分离轴理论,判断线段与包围盒重叠测试的算法伪码如下所示:

判断线段\({{P}_{0}}{{P}_{1}}\)与包围盒\(C+{{h}_{0}}{{\vec{u}}_{0}}+{{h}_{1}}{{\vec{u}}_{1}}+{{h}_{2}}{{\vec{u}}_{2}}\)是否重叠,其中,\(-{{l}_{0}}\le {{h}_{0}}\le {{l}_{0}},-{{l}_{1}}\le {{h}_{1}}\le {{l}_{1}}\)\(-{{l}_{2}}\le {{h}_{2}}\le {{l}_{2}},\left\| {{{\vec{u}}}_{0}} \right\|=\left\| {{{\vec{u}}}_{1}} \right\|=\left\| {{{\vec{u}}}_{2}} \right\|=1,{{l}_{0}},{{l}_{1}},{{l}_{2}}\succ 0\)
return ({DISJOINT, OVERLAPPING})
1.      \({{p}_{0}}={{P}_{0}}-C\);
2.      \({{p}_{1}}={{P}_{1}}-C\);
3.    \({{P}_{0}}'=\left( {{{\vec{u}}}_{0}}\cdot {{p}_{0}},{{{\vec{u}}}_{1}}\cdot {{p}_{0}},{{{\vec{u}}}_{2}}\cdot {{p}_{0}} \right)\);
4.    \({{P}_{1}}'=\left( {{{\vec{u}}}_{0}}\cdot {{p}_{1}},{{{\vec{u}}}_{1}}\cdot {{p}_{1}},{{{\vec{u}}}_{2}}\cdot {{p}_{1}} \right)\);
5.      \(M=\left( {{P}_{0}}'+{{P}_{1}}' \right)\cdot 0.5\);
6.      \(\vec{w}=M-{{P}_{0}}'\);
7.      \(X=\left\| {{w}_{x}} \right\|\);
8.      \(Y=\left\| {{w}_{y}} \right\|\);
9.      \(Z=\left\| {{w}_{z}} \right\|\);
10.    if \(\left\| {{M}_{x}} \right\|\succ X+{{l}_{0}}\) or \(\left\| {{M}_{y}} \right\|\succ Y+{{l}_{1}}\) or \(\left\| {{M}_{z}} \right\|\succ Z+{{l}_{2}}\)then
11.             return DISJOINT;
12.    else if \(\left\| -{{w}_{z}}{{M}_{y}}+{{w}_{y}}{{M}_{z}} \right\|\succ {{l}_{1}}Z+{{l}_{2}}Y\) or \(\left\| -{{w}_{z}}{{M}_{x}}+{{w}_{x}}{{M}_{z}} \right\|\succ {{l}_{0}}Z+{{l}_{2}}X\)
or \(\left\| -{{w}_{y}}{{M}_{x}}+{{w}_{x}}{{M}_{y}} \right\|\succ {{l}_{0}}Y+{{l}_{1}}X\), then
13.             return DISJOINT;
14.    end if;
15.    return OVERLAPPING;

最坏情况下, 9个求绝对值的操作,6个对比操作,33个加法操作,31个乘法操作。

9.2.4. 平面与包围盒的相交测试

确定平面与包围盒是否相交,很容易想到的一种方法是:可以把包围盒的8个顶点代入平面的参数方程中,得到的结果有正有负,就说明这些顶点位于平面两侧(或者恰好在平面上),因此两者相交。Akenine-Möller等[14](2002)就描述了两种平面与包围盒的算法。一种方法利用了平面与包围盒相交,则它必定与包围盒的一条对角线相交这个性质,所以只要找到那条对角线,把它的两个顶点代入平面的方程中,判断求解的结果的符号即可。另外一种方法是通过对比投影半长与包围盒中心到平面的距离来判定是否相交。因为第2种算法在平面与两种包围盒相交测试问题上的描述是相同的,所以本节选择只在平面与有向包围盒的相交测试问题对该算法进行描述,而第1种算法在两种包围的相交测试问题上存在差异,所以将分别进行介绍。

1.    平面与轴对齐包围盒的相交测试

问题描述:平面\(\vec{n}\cdot X+d=0\)与轴对齐包围盒\(\left( {{B}_{\min }},{{B}_{\max }} \right)\)的相交测试,其中, \({{B}_{\min }}=\left( b_{x}^{\min },b_{y}^{\min },b_{z}^{\min } \right),{{B}_{\max }}=\left( b_{x}^{\max },b_{y}^{\max },b_{z}^{\max } \right)\),\(b_{x}^{\min }\prec b_{x}^{\max },b_{y}^{\min }\prec b_{y}^{\max },b_{z}^{\min }\prec b_{z}^{\max },\vec{n}=\left( {{n}_{x}},{{n}_{y}},{{n}_{z}} \right)\)

为了判断它们是否相交,要从包围盒上找到一条与平面法向量\(\vec{n}\)方向最接近的对角线,把条对角线上的两个端点\({{V}^{\min }}\)\({{V}^{\max }}\)代入平面的参数方程中。如果得到的符号相反,说明平面与包围盒相交;如果至少有一个零,说明它们相切;否则,它们相交。

如何找到与平面法向量\(\vec{n}\)方向最接近的对角线呢?注意到,该对角线上的两个端点\({{V}^{\min }}\)\({{V}^{\max }}\),满足等式

\[\left\{ \begin{array}{l}{V^{\min }} \cdot \vec n = \min \{ {V^i} \cdot \vec n\} \\{V^{\max }} \cdot \vec n = \max \{ {V^i} \cdot \vec n\} \end{array} \right. \tag{9.18}\]

2015-3-24 15-22-35

图9.6 平面与轴对齐包围盒的相交测试,包围盒在平面的负半空间

其中,\({{V}^{i}}\)表示包围盒的顶点。要找到使得式子\(x\cdot {{n}_{x}}+y\cdot {{n}_{x}}+z\cdot {{n}_{z}}\)分别取得最小值和最大值的顶点。对于\(k\in \left\{ x,y,z \right\}\),如果\({{n}_{k}}\succ 0\),取\(V_{k}^{\min }=b_{k}^{\min },V_{k}^{\max }=b_{k}^{\max }\);否则,取\(V_{k}^{\min }=b_{k}^{\max }\)\(V_{k}^{\max }=b_{k}^{\min }\)。依据这个规则,确定\({{V}^{\min }}\)\({{V}^{\max }}\)后,代入平面方程中,如果\({{V}^{\min }}\cdot \vec{n}+d\succ 0\),则包围盒在平面的正半空间上;如果\({{V}^{\max }}\cdot \vec{n}+d\prec 0\),则包围盒在平面的负半空间上;如果\({{V}^{\max }}\cdot \vec{n}+d=0\)或者\({{V}^{\min }}\cdot \vec{n}+d=0\),则平面与包围盒相切于相应的顶点上;否则,平面与包围盒相交。

算法伪码如下所示:

平面\(\pi :\vec{n}\cdot X+d=0\)与轴对齐包围盒\({{B}_{\min }}=\left( b_{x}^{\min },b_{y}^{\min },b_{z}^{\min } \right),{{B}_{\max }}=\left( b_{x}^{\max },b_{y}^{\max },b_{z}^{\max } \right)\)的相交测试,其中,\(b_{x}^{\min }\prec b_{x}^{\max },b_{y}^{\min }\prec b_{y}^{\max },b_{z}^{\min }\prec b_{z}^{\max }\)\(\vec{n}=\left( {{n}_{x}},{{n}_{y}},{{n}_{z}} \right)\)
return ({POSITIVE, NEGETIVE, TANGENT, INTERSECTING})
1.    for each \(k\in \left\{ x,y,z \right\}\)
2.           if \({{n}_{k}}\succ 0\), then
3.                  \(V_{k}^{\min }=b_{k}^{\min }\);                          //顶点\({{V}^{\min }}=\{V_{x}^{\min },V_{y}^{\min },V_{z}^{\min }\}\)
4.                  \(V_{k}^{\max }=b_{k}^{\max }\);                         //顶点\({{V}^{\max }}=\{V_{x}^{\max },V_{y}^{\max },V_{z}^{\max }\}\)
5.           else
6.                  \(V_{k}^{\min }=b_{k}^{\max }\);
7.                  \(V_{k}^{\max }=b_{k}^{\min }\);
8.           end if;
9.    end for;
10.   if \({{V}^{\min }}\cdot \vec{n}+d\succ 0\), then
11.          return POSITIVE;
12.   else if \({{V}^{\max }}\cdot \vec{n}+d\prec 0\), then
13.          return NEGETIVE;
14.   else if \({{V}^{\max }}\cdot \vec{n}+d=0\) or \({{V}^{\min }}\cdot \vec{n}+d=0\), then
15.          return TANGENT;
16.   end if;
17.   return INTERSECTING;

2.    平面与有向包围盒的相交测试

问题描述:平面\(\vec{n}\cdot X+d=0\)与有向包围盒\(C+{{h}_{0}}{{\vec{u}}_{0}}+{{h}_{1}}{{\vec{u}}_{1}}+{{h}_{2}}{{\vec{u}}_{2}}\)的相交测试,其中,\(\vec{n}=\left( {{n}_{x}},{{n}_{y}},{{n}_{z}} \right)\),\(-{{l}_{0}}\le {{h}_{0}}\le {{l}_{0}},-{{l}_{1}}\le {{h}_{1}}\le {{l}_{1}},-{{l}_{2}}\le {{h}_{2}}\le {{l}_{2}},\left\| {{{\vec{u}}}_{0}} \right\|=\left\| {{{\vec{u}}}_{1}} \right\|=\left\| {{{\vec{u}}}_{2}} \right\|=1,{{l}_{0}},{{l}_{1}},{{l}_{2}}\succ 0\)

方法一.

跟平面与轴对齐包围盒相比,需要作进一步的改进,即把包围盒的三条轴沿着平面法向量方向作投影

\[\vec n' = \left( {\vec n \cdot {{\vec u}_0},\vec n \cdot {{\vec u}_1},\vec n \cdot {{\vec u}_2}} \right) \tag{9.19}\]

寻找\({{V}^{\min }}\)\({{V}^{\max }}\)时,使用法向量\(\vec{n}'\),而不是\(\vec{n}\),其它跟平面与轴对齐包围盒的相交测试相似,算法伪码如下所示:

平面\(\vec{n}\cdot X+d=0\)与有向包围盒\(C+{{h}_{0}}{{\vec{u}}_{0}}+{{h}_{1}}{{\vec{u}}_{1}}+{{h}_{2}}{{\vec{u}}_{2}}\)的相交测试,其中,\(\vec{n}=\left( {{n}_{x}},{{n}_{y}},{{n}_{z}} \right)\)\(-{{l}_{0}}\le {{h}_{0}}\le {{l}_{0}},-{{l}_{1}}\le {{h}_{1}}\le {{l}_{1}},-{{l}_{2}}\le {{h}_{2}}\le {{l}_{2}},\left\| {{{\vec{u}}}_{0}} \right\|=\left\| {{{\vec{u}}}_{1}} \right\|=\left\| {{{\vec{u}}}_{2}} \right\|=1,{{l}_{0}},{{l}_{1}},{{l}_{2}}\succ 0\)
return ({POSITIVE, NEGETIVE, TANGENT, INTERSECTING})
1.    \(\vec{n}'=\left( \vec{n}\cdot {{{\vec{u}}}_{1}},\vec{n}\cdot {{{\vec{u}}}_{2}},\vec{n}\cdot {{{\vec{u}}}_{3}} \right)\);
2.    for for( \(k=0\) ; \(k\prec 3\) ; \(k=k+1\) )
3.           if \({{n}_{k}}'\succ 0\), then
4.                  \(V_{k}^{\min }=-{{l}_{k}}\);                               //顶点\({{V}^{\min }}=\{V_{x}^{\min },V_{y}^{\min },V_{z}^{\min }\}\)
5.                  \(V_{k}^{\max }={{l}_{k}}\);                                //顶点\({{V}^{\max }}=\{V_{x}^{\max },V_{y}^{\max },V_{z}^{\max }\}\)
6.           else
7.                  \(V_{k}^{\min }={{l}_{k}}\);
8.                  \(V_{k}^{\max }=-{{l}_{k}}\);
9.           end if;
10.   end for;
11.   if \({{V}^{\min }}\cdot \vec{n}'+C\cdot \vec{n}+d\succ 0\), then
12.          return POSITIVE;
13.   else if \({{V}^{\max }}\cdot \vec{n}'+C\cdot \vec{n}+d\prec 0\), then
14.          return NEGETIVE;
15.   else if \({{V}^{\max }}\cdot \vec{n}'+C\cdot \vec{n}+d=0\) or \({{V}^{\min }}\cdot \vec{n}'+C\cdot \vec{n}+d=0\), then
16.          return TANGENT;
17.   end if;
18.   return INTERSECTING;

方法二.

将有向包围盒的三条轴线投影到平面的法线方向上,投影等式为

\[r = {l_0}\left\| {\vec n \cdot {{\vec u}_0}} \right\| + {l_1}\left\| {\vec n \cdot {{\vec u}_1}} \right\| + {l_2}\left\| {\vec n \cdot {{\vec u}_2}} \right\| \tag{9.20}\]

若包围盒中心到给定平面的距离\(\vec{n}\cdot C+d\succ r\),则包围盒在平面的正半空间上;若距离\(\vec{n}\cdot C+d\prec -r\),则包围盒在平面的负半空间上;若距离\(\vec{n}\cdot C+d=r\)\(\vec{n}\cdot C+d=-r\),则平面与包围盒相切于包围盒的某个顶点上;反之,则平面与包围盒相交。

接下来,证明这种方法的正确性。对于\(k\in \left\{ 0,1,2 \right\}\),如果\(\vec{n}\cdot {{\vec{u}}_{k}}\succ 0\),则投影长取\({{l}_{k}}\left( \vec{n}\cdot {{{\vec{u}}}_{k}} \right)\),反之,则取\(-{{l}_{k}}\left( \vec{n}\cdot {{{\vec{u}}}_{k}} \right)\)。相当于\(r={{V}^{\max }}\cdot \vec{n}'\)\(-r={{V}^{\min }}\cdot \vec{n}'\),中心到平面的有符号距离表示为\(\vec{n}\cdot C+d\),其中\(\vec{n}'\)如等式(9.19)所示。如果\(\vec{n}\cdot C+d\succ r\),即有\({{V}^{\min }}\cdot \vec{n}'+\vec{n}\cdot C+d\succ 0\),包围盒在平面的正半空间上。对于包围盒在平面的负半空间上,平面与包围盒相切、相交的情况,也可以类似推导出来,。显然,方法二是方法一的另外一种表示方式,但方法二显得更加精练些。

算法伪码如下所示:

平面\(\vec{n}\cdot X+d=0\)与有向包围盒\(C+{{h}_{0}}{{\vec{u}}_{0}}+{{h}_{1}}{{\vec{u}}_{1}}+{{h}_{2}}{{\vec{u}}_{2}}\)的相交测试,其中,\(\vec{n}=\left( {{n}_{x}},{{n}_{y}},{{n}_{z}} \right)\)\(-{{l}_{0}}\le {{h}_{0}}\le {{l}_{0}},-{{l}_{1}}\le {{h}_{1}}\le {{l}_{1}},-{{l}_{2}}\le {{h}_{2}}\le {{l}_{2}},\left\| {{{\vec{u}}}_{0}} \right\|=\left\| {{{\vec{u}}}_{1}} \right\|=\left\| {{{\vec{u}}}_{2}} \right\|=1,{{l}_{0}},{{l}_{1}},{{l}_{2}}\succ 0\)
return ({POSITIVE, NEGETIVE, TANGENT, INTERSECTING})
1.    \(r={{l}_{0}}\left\| \vec{n}\cdot {{{\vec{u}}}_{0}} \right\|+{{l}_{1}}\left\| \vec{n}\cdot {{{\vec{u}}}_{1}} \right\|+{{l}_{2}}\left\| \vec{n}\cdot {{{\vec{u}}}_{2}} \right\|\);
2.    if \(\vec{n}\cdot C+d\succ r\), then
3.           return POSITIVE;
4.    else if \(\vec{n}\cdot C+d\prec -r\), then
5.           return POSITIVE;
6.    else \(\vec{n}\cdot C+d==r\) or \(\vec{n}\cdot C+d==-r\), then
7.           return TANGENT;
8.    end if;
9.    return INTERSECTING;

9.2.5. 三角形与包围盒的重叠测试

问题描述:三角形\(T:\Delta {{V}_{0}}{{V}_{1}}{{V}_{2}}\)与有向包围盒\(C+{{h}_{0}}{{\vec{u}}_{0}}+{{h}_{1}}{{\vec{u}}_{1}}+{{h}_{2}}{{\vec{u}}_{2}}\)的重叠测试,其中,\(-{{l}_{0}}\le {{h}_{0}}\le {{l}_{0}}\),\(-{{l}_{1}}\le {{h}_{1}}\le {{l}_{1}},-{{l}_{2}}\le {{h}_{2}}\le {{l}_{2}},\left\| {{{\vec{u}}}_{0}} \right\|=\left\| {{{\vec{u}}}_{1}} \right\|=\left\| {{{\vec{u}}}_{2}} \right\|=1,{{l}_{0}},{{l}_{1}},{{l}_{2}}\succ 0\)

Voorhies[18](1992)提出一种判断三角形与长方体是否相交的算法,Green和Hatch[19](1995)扩展了该算法的用途,使得该算法能判断任意多边形与长方体之间是否重叠。该算法通过3个重叠检测来判定:1)检测多边形的顶点是否在长方体内,若至少存在一个这样的顶点,说明它们重叠;2)检测多边形的边是否与长方体相交,若至少存在一条这样的边,说明它们重叠;3)检测长方体的四条对角线是否与多边形相交,若至少存在一条这样的对角线,说明它们重叠。相反,若一个多边形通过了3个检测步骤,说明它们是分离的。可以在网上找到该算法的C++实现代码[21]

此外,Akenine-Möller[20](2001)提出了一种基于分离轴理论的算法,该算法具有更高的效率,本节将对这种算法进行详细的介绍。

跟线段与包围盒的重叠检测类似,把三角形的三个端点,沿着有向包围盒的三条轴方向做投影

\[{P_i} = \left( {{{\vec u}_0} \cdot ({V_i} - C),{{\vec u}_1} \cdot ({V_i} - C),{{\vec u}_2} \cdot ({V_i} - C)} \right) \tag{9.21}\]

其中\(i=0,1,2\)。接下来,只要判断\(\Delta {{P}_{0}}{{P}_{1}}{{P}_{2}}\)与轴对齐包围盒\(\left( -{{l}_{0}},-{{l}_{1}},-{{l}_{2}} \right),\left( {{l}_{0}},{{l}_{1}},{{l}_{2}} \right)\)是否重叠,包围盒的中心是\(\left( 0,0,0 \right)\)

2015-3-24 15-22-53

图9.7 三角形与包围盒的重叠检测

如图9.7所示,基于分离轴理论,需要对下面的13条轴线进行检测:

  • i.     [3个检测] \({{\vec{e}}_{0}}=\left( 1,0,0 \right),{{\vec{e}}_{1}}=\left( 0,1,0 \right),{{\vec{e}}_{2}}=\left( 0,0,1 \right)\),分别是轴对齐包围盒的3条轴线。
  • ii.    [1个检测] \(\Delta {{P}_{0}}{{P}_{1}}{{P}_{2}}\)的法线\(\vec{n}\)
  • iii.   [9个检测] \({{\vec{a}}_{ij}}={{\vec{e}}_{i}}\times {{\vec{f}}_{j}}\),其中\(i,j\in \left\{ 0,1,2 \right\}\)\({{\vec{f}}_{0}}={{P}_{1}}-{{P}_{0}},{{\vec{f}}_{1}}={{P}_{2}}-{{P}_{1}},{{\vec{f}}_{2}}={{P}_{0}}-{{P}_{2}}\)

对于第i种情况,以轴\({{\vec{e}}_{0}}\)为例,将\(\Delta {{P}_{0}}{{P}_{1}}{{P}_{2}}\)的3个顶点沿着\({{\vec{e}}_{0}}\)方向做投影,由于\({{\vec{e}}_{0}}\)\(Y\)分量和\(Z\)分量都是零,所以3个点到包围盒中心的投影间隔分别是\({{t}_{0}}={{P}_{0,x}},{{t}_{1}}={{P}_{1,x}},{{t}_{2}}={{P}_{2,x}}\),找到3个投影间隔的最小值\(\min \left\{ {{t}_{0}},{{t}_{1}},{{t}_{2}} \right\}\)和最大值\(\max \left\{ {{t}_{0}},{{t}_{1}},{{t}_{2}} \right\}\)。如果\(\min \left\{ {{t}_{0}},{{t}_{1}},{{t}_{2}} \right\}\succ {{l}_{0}}\)或者\(\max \left\{ {{t}_{0}},{{t}_{1}},{{t}_{2}} \right\}\prec -{{l}_{0}}\),说明三角形与包围盒分离。否则,还需要对其它轴进行检测。对于轴\({{\vec{e}}_{1}}\)和轴\({{\vec{e}}_{2}}\)的情况,也是类似的。

对于第ii种情况,判断\(\Delta {{P}_{0}}{{P}_{1}}{{P}_{2}}\)所在的平面与包围盒是否相交,若不相交,说明三角形与包围盒分离。否则,还需要对其它轴进行检测。

对于iii种情况,以\(i=0,j=0\)为例,\({{\vec{a}}_{00}}={{\vec{e}}_{0}}\times {{\vec{f}}_{0}}=\left( 0,-{{f}_{0,z}},{{f}_{0,y}} \right)\)。将\(\Delta {{P}_{0}}{{P}_{1}}{{P}_{2}}\)的3个顶点沿着\({{\vec{a}}_{00}}\)方向做投影,得\({{s}_{0}}={{\vec{a}}_{00}}\cdot {{P}_{0}}={{P}_{0,z}}{{P}_{1,y}}-{{P}_{0,y}}{{P}_{1,z}}\)\({{s}_{1}}={{\vec{a}}_{00}}\cdot {{P}_{1}}={{P}_{0,z}}{{P}_{1,y}}-{{P}_{0,y}}{{P}_{1,z}}={{s}_{0}}\)\({{s}_{2}}={{\vec{a}}_{00}}\cdot {{P}_{2}}=-{{f}_{0,z}}{{P}_{2,y}}+{{f}_{0,y}}{{P}_{2,z}}\)。由于\({{s}_{0}}={{s}_{1}}\),我们不再需要找到\(\left\{ {{s}_{0}},{{s}_{1}},{{s}_{2}} \right\}\)的最小值和最大值,只要找到最小值\(\min \left\{ {{s}_{0}},{{s}_{2}} \right\}\)和最大值\(\max \left\{ {{s}_{0}},{{s}_{2}} \right\}\)

\(\Delta {{P}_{0}}{{P}_{1}}{{P}_{2}}\)的3个顶点沿着\({{\vec{a}}_{00}}\)方向做投影,并计算出一条半径\(r\)

\(r={{l}_{0}}\left\| {{a}_{00,x}} \right\|+{{l}_{1}}\left\| {{a}_{00,y}} \right\|+{{l}_{2}}\left\| {{a}_{00,z}} \right\|={{l}_{1}}\left\| {{f}_{0,z}} \right\|+{{l}_{2}}\left\| {{f}_{0,y}} \right\|\)

如果\(\min \left\{ {{r}_{0}},{{r}_{2}} \right\}\succ r\)或者\(\max \left\{ {{r}_{0}},{{r}_{2}} \right\}\prec -r\),说明三角形与包围盒分离。否则,还需要对其它轴进行检测。

对于其它8条轴的检测方法,也是类似的。但为了能顺利的完成算法的实现,这里描述两条重要的结论:

  • i.     \({{e}_{0}}\times {{f}_{i}}=\left( 0,-{{f}_{i,z}},{{f}_{i,y}} \right),{{e}_{1}}\times {{f}_{i}}=\left( {{f}_{i,z}},0,-{{f}_{i,x}} \right),{{e}_{2}}\times {{f}_{i}}=\left( -{{f}_{i,y}},{{f}_{i,x}},0 \right)\)
  • ii.    对于\({{e}_{i}}\times {{f}_{0}}\)\({{s}_{0}}={{s}_{1}}\);对于\({{e}_{i}}\times {{f}_{1}}\)\({{s}_{1}}={{s}_{2}}\);对于\({{e}_{i}}\times {{f}_{2}}\)\({{s}_{2}}={{s}_{0}}\)

如果检测完13条轴,都没有出现分离的情况,说明三角形与包围盒是重叠的。

算法伪码如下所示:

三角形\(T:\Delta {{V}_{0}}{{V}_{1}}{{V}_{2}}\)与有向包围盒\(C+{{h}_{0}}{{\vec{u}}_{0}}+{{h}_{1}}{{\vec{u}}_{1}}+{{h}_{2}}{{\vec{u}}_{2}}\)的重叠测试,其中,\(-{{l}_{0}}\le {{h}_{0}}\le {{l}_{0}}\)\(-{{l}_{1}}\le {{h}_{1}}\le {{l}_{1}},-{{l}_{2}}\le {{h}_{2}}\le {{l}_{2}},\left\| {{{\vec{u}}}_{0}} \right\|=\left\| {{{\vec{u}}}_{1}} \right\|=\left\| {{{\vec{u}}}_{2}} \right\|=1,{{l}_{0}},{{l}_{1}},{{l}_{2}}\succ 0\)
return ({DISJOINT, OVERLAPPING})
1.    \(V{{'}_{0}}={{V}_{0}}-C,V{{'}_{1}}={{V}_{1}}-C,V{{'}_{2}}={{V}_{2}}-C\);
2.    \({{P}_{0}}=\left( {{{\vec{u}}}_{0}}\cdot {{V}_{0}}',{{{\vec{u}}}_{1}}\cdot {{V}_{0}}',{{{\vec{u}}}_{2}}\cdot {{V}_{0}}' \right)\);
3.    \({{P}_{1}}=\left( {{{\vec{u}}}_{0}}\cdot {{V}_{1}}',{{{\vec{u}}}_{1}}\cdot {{V}_{1}}',{{{\vec{u}}}_{2}}\cdot {{V}_{1}}' \right)\);
4.    \({{P}_{2}}=\left( {{{\vec{u}}}_{0}}\cdot {{V}_{2}}',{{{\vec{u}}}_{1}}\cdot {{V}_{2}}',{{{\vec{u}}}_{2}}\cdot {{V}_{2}}' \right)\);
5.    \({{e}_{0}}={{P}_{1}}-{{P}_{0}}\);                                          //测试轴\(\left( 1,0,0 \right)\times {{e}_{0}},\left( 0,1,0 \right)\times {{e}_{0}},\left( 0,0,1 \right)\times {{e}_{0}}\)
6.    \({{v}_{0}}={{P}_{0}},{{v}_{1}}={{P}_{1}},{{v}_{2}}={{P}_{2}}\);
7.    if TestAxisEdge(\(\{{{v}_{0}},{{v}_{1}},{{v}_{2}}\}\),\({{e}_{0}}\)) == DISJOINT, then
8.           return DISJOINT;
9.    end if;
10.   \({{e}_{1}}={{P}_{2}}-{{P}_{1}}\);                                          //测试轴\(\left( 1,0,0 \right)\times {{e}_{1}},\left( 0,1,0 \right)\times {{e}_{1}},\left( 0,0,1 \right)\times {{e}_{1}}\)
11.   \({{v}_{0}}={{P}_{1}},{{v}_{1}}={{P}_{2}},{{v}_{2}}={{P}_{0}}\);
12.   if TestAxisEdge(\(\{{{v}_{0}},{{v}_{1}},{{v}_{2}}\}\),\({{e}_{1}}\)) == DISJOINT, then
13.          return DISJOINT;
14.   end if;
15.   \({{e}_{2}}={{P}_{0}}-{{P}_{2}}\);                                          //测试轴\(\left( 1,0,0 \right)\times {{e}_{2}},\left( 0,1,0 \right)\times {{e}_{2}},\left( 0,0,1 \right)\times {{e}_{2}}\)
16.   \({{v}_{0}}={{P}_{2}},{{v}_{1}}={{P}_{0}},{{v}_{2}}={{P}_{1}}\);
17.   if TestAxisEdge(\(\{{{v}_{0}},{{v}_{1}},{{v}_{2}}\}\),\({{e}_{2}}\)) == DISJOINT, then
18.          return DISJOINT;
19.   end if;
20.   if \(\min \left\{ {{P}_{0,x}},{{P}_{1,x}},{{P}_{2,x}} \right\}\succ {{l}_{0}}\) or \(\max \left\{ {{P}_{0,x}},{{P}_{1,x}},{{P}_{2,x}} \right\}\prec -{{l}_{0}}\), then
21.          return DISJOINT;                       //测试轴(1,0,0)
22.   else if \(\min \left\{ {{P}_{0,y}},{{P}_{1,y}},{{P}_{2,y}} \right\}\succ {{l}_{1}}\) or \(\max \left\{ {{P}_{0,y}},{{P}_{1,y}},{{P}_{2,y}} \right\}\prec -{{l}_{1}}\), then
23.          return DISJOINT;                      //测试轴(0,1,0)
24.   else if \(\min \left\{ {{P}_{0,z}},{{P}_{1,z}},{{P}_{2,z}} \right\}\succ {{l}_{2}}\) or \(\max \left\{ {{P}_{0,z}},{{P}_{1,z}},{{P}_{2,z}} \right\}\prec -{{l}_{2}}\), then
25.          return DISJOINT;                      //测试轴(0,0,1)
26.   end if;
27.   \(\vec{n}=\left( {{P}_{1}}-{{P}_{0}} \right)\times \left( {{P}_{2}}-{{P}_{0}} \right)\);                        //测试三角形的法向量\(\vec{n}\)
28.   \(d=-\vec{n}\cdot {{P}_{0}}\);                                              //平面的参数方程为\(\vec{n}\cdot X+d=0\)
29.   for \(k\in \left\{ x,y,z \right\}\)
30.          if \({{n}_{k}}\succ 0\), then                             //令\({{l}_{x}}={{l}_{0}},{{l}_{y}}={{l}_{1}},{{l}_{z}}={{l}_{2}}\)
31.                 \(P_{k}^{\min }=-{{l}_{k}}\);
32.                 \(P_{k}^{\max }={{l}_{k}}\);
33.          else
34.                 \(P_{k}^{\min }={{l}_{k}}\);
35.                 \(P_{k}^{\max }=-{{l}_{k}}\);
36.          end if;
37.   end for;
38.   if \(\vec{n}\cdot {{P}^{\min }}+d\succ 0\) or \(\vec{n}\cdot {{P}^{\max }}+d\prec 0\), then
39.          return DISJOINT;
40.   end if;
41.   return OVERLAPPING;

bool TestAxisEdge(Point \(\{{{v}_{0}},{{v}_{1}},{{v}_{2}}\}\), Vector \(e\))
return ({DISJOINT,INTERSECTING})
1.    \(X=\left\| {{e}_{x}} \right\|\);
2.    \(Y=\left\| {{e}_{y}} \right\|\);
3.    \(Z=\left\| {{e}_{z}} \right\|\);
4.    \({{s}_{0}}=-{{e}_{z}}*{{v}_{0,y}}+{{e}_{y}}*{{v}_{0,z}}\);                      //测试轴\(\left( 1,0,0 \right)\times e\)
5.    \({{s}_{2}}=-{{e}_{z}}*{{v}_{2,y}}+{{e}_{y}}*{{v}_{2,z}}\);
6.    \(r=Z*{{l}_{1}}+Y*{{l}_{2}}\);
7.    if \(\max \left\{ {{s}_{0}},{{s}_{2}} \right\}\prec -r\) or \(\min \left\{ {{s}_{0}},{{s}_{2}} \right\}\succ r\), then
8.           return DISJOINT;
9.    end if;
10.   \({{s}_{0}}={{e}_{z}}*{{v}_{0,x}}-{{e}_{x}}*{{v}_{0,z}}\);                               //测试轴\(\left( 0,1,0 \right)\times e\)
11.   \({{s}_{2}}={{e}_{z}}*{{v}_{2,x}}-{{e}_{x}}*{{v}_{2,z}}\);
12.   \(r=Z*{{l}_{0}}+X*{{l}_{2}}\);
13.   if \(\max \left\{ {{s}_{0}},{{s}_{2}} \right\}\prec -r\) or \(\min \left\{ {{s}_{0}},{{s}_{2}} \right\}\succ r\), then
14.          return DISJOINT;
15.   end if;
16.   \({{s}_{0}}=-{{e}_{y}}*{{v}_{0,x}}+{{e}_{x}}*{{v}_{0,y}}\);                      //测试轴\(\left( 0,0,1 \right)\times e\)
17.   \({{s}_{2}}=-{{e}_{y}}*{{v}_{2,x}}+{{e}_{x}}*{{v}_{2,y}}\);
18.   \(r=Y*{{l}_{0}}+X*{{l}_{1}}\);
19.   if \(\max \left\{ {{s}_{0}},{{s}_{2}} \right\}\prec -r\) or \(\min \left\{ {{s}_{0}},{{s}_{2}} \right\}\succ r\), then
20.          return DISJOINT;
21.   end if;
22.   return OVERLAPPING;

9.2.6. 有向包围盒与有向包围盒的重叠测试

问题描述:有向包围盒\({{C}^{A}}+h_{0}^{A}\vec{u}_{0}^{A}+h_{1}^{A}\vec{u}_{1}^{A}+h_{2}^{A}\vec{u}_{2}^{A}\)\({{C}^{B}}+h_{0}^{B}\vec{u}_{0}^{B}+h_{1}^{B}\vec{u}_{1}^{B}+h_{2}^{B}\vec{u}_{2}^{B}\)的重叠测试,其中\(-l_{0}^{k}\le h_{0}^{k}\le l_{0}^{k},-l_{1}^{k}\le h_{1}^{k}\le l_{1}^{k},-l_{2}^{k}\le h_{2}^{k}\le l_{2}^{k},\left\| \vec{u}_{0}^{k} \right\|=\left\| \vec{u}_{1}^{k} \right\|=\left\| \vec{u}_{2}^{k} \right\|=1,l_{0}^{k},l_{1}^{k},l_{2}^{k}\succ 0,k\in \{A,B\}\)

一种很直线但效率不高的方法,就是先判断包围盒\(A\)的12条边与包围盒\(B\)是否重叠,再判断包围盒\(B\)的12条边与包围盒\(A\)是否重叠,若至少存在1条边-包围盒重叠的情况,说明两个包围盒重叠,否则不重叠。

2015-3-24 15-23-06

图9.8 包围盒\(A\)\(B\)在轴线方向\(\vec{n}\)上的投影间隔不重叠,则\(A\)\(B\)相互分离

Gottschalk[4,5]提出了用于碰撞检测的数据结构OBBTree,并提出了一种基于轴分离理论的OBB与OBB的重叠检测算法,本节将详细介绍该算法。

基于轴分离理论,只要找到一条将两个包围盒分开的轴线并且确保投影间隔不重叠,就说明这两个包围盒是不重叠。如图9.8所示,\({{I}_{A}}\)\({{I}_{B}}\)分别表示包围盒\(A\)和包围盒\(B\)在轴线方向\(\vec{n}\)上的投影间隔,投影间隔\({{I}_{A}}\)\({{I}_{B}}\)不发生重叠,那么就可以保证\(A\)\(B\)不重叠。

对于\(A\)\(B\)来说,这就需要对下列的15条轴线方向进行检测:

  • i.     \(A\)的3条轴线\(\vec{u}_{0}^{A},\vec{u}_{1}^{A},\vec{u}_{2}^{A}\)
  • ii.    \(B\)的3条轴线\(\vec{u}_{0}^{B},\vec{u}_{1}^{B},\vec{u}_{2}^{B}\)
  • iii.   来自\(A\)\(B\)组合的9条轴线\(\vec{u}_{i}^{A}\times \vec{u}_{j}^{B}\),其中\(i,j\in \{0,1,2\}\)

2015-3-24 15-23-18

图9.9 判断\(A\)\(B\)在轴线方向\(\vec{n}\)上的投影间隔是否重叠

给定一条轴线方向\(\vec{n}\),如何判断投影间隔是否发生重叠呢?如图9.9所示,将\(A\)\(B\)投影到轴线方向\(\vec{n}\)上,投影半长分别用\({{r}_{A}}\)\({{r}_{B}}\)表示,向量\(\vec{t}={{C}^{B}}-{{C}^{A}}\)在轴线方向\(\vec{n}\)上的投影用\(s\)表示。

\[{{r}_{A}}=\left( l_{0}^{A}\left\| \vec{u}_{0}^{A}\cdot \vec{n} \right\|+l_{1}^{A}\left\| \vec{u}_{1}^{A}\cdot \vec{n} \right\|+l_{2}^{A}\left\| \vec{u}_{2}^{A}\cdot \vec{n} \right\| \right)/\left\| {\vec{n}} \right\|\]

\[{{r}_{B}}=\left( l_{0}^{B}\left\| \vec{u}_{0}^{B}\cdot \vec{n} \right\|+l_{1}^{B}\left\| \vec{u}_{1}^{B}\cdot \vec{n} \right\|+l_{2}^{B}\left\| \vec{u}_{2}^{B}\cdot \vec{n} \right\| \right)/\left\| {\vec{n}} \right\|\]

\[s=\left\| \vec{t}\cdot \vec{n} \right\|/\left\| {\vec{n}} \right\|\]

\(A\)\(B\)在轴线方向\(\vec{n}\)上的投影间隔不重叠,当且仅当它们满足条件

\[s \succ {r_A} + {r_B} \tag{9.22}\]

接下来,分别考虑三种类型的轴线的重叠判断。

       i种类型:

\(\vec{n}\)是包围盒\(A\)的一条轴线,以\(\vec{u}_{0}^{A}\)为例,由于包围盒\(A\)的3条轴线互相垂直,重叠判断的不等式表示为

\[\left\| {\vec t \cdot \vec u_0^A} \right\| \succ l_0^A + l_0^B\left\| {\vec u_0^A \cdot \vec u_0^B} \right\| + l_1^B\left\| {\vec u_0^A \cdot \vec u_1^B} \right\| + l_2^B\left\| {\vec u_0^A \cdot \vec u_2^B} \right\|\]

共需要4个求绝对值操作,15个乘法操作,12个加/减法操作。

       ii种类型:

\(\vec{n}\)是包围盒\(B\)的一条轴线,以\(\vec{u}_{0}^{B}\)为例,由于包围盒\(B\)的3条轴线互相垂直,重叠判断的不等式表示为

\[\left\| {\vec t \cdot \vec u_0^B} \right\| \succ l_0^A\left\| {\vec u_0^B \cdot \vec u_0^A} \right\| + l_1^A\left\| {\vec u_0^B \cdot \vec u_1^A} \right\| + l_2^A\left\| {\vec u_0^B \cdot \vec u_2^A} \right\| + l_0^B\]

共需要4个求绝对值操作,15个乘法操作,12个加/减法操作,与第i种类型相似。

       iii种类型:

\(\vec{n}\)是两个包围盒轴线的叉积,以\(\vec{n}=\vec{u}_{0}^{A}\times \vec{u}_{0}^{B}\)为例,重叠判断的不等式表示为

\[\begin{array}{l}\left\| {\vec t \cdot \left( {\vec u_0^A \times \vec u_0^B} \right)} \right\| \succ l_0^A\left\| {\left( {\vec u_0^A \times \vec u_0^B} \right) \cdot \vec u_0^A} \right\| + l_1^A\left\| {\left( {\vec u_0^A \times \vec u_0^B} \right) \cdot \vec u_1^A} \right\| + l_2^A\left\| {\left( {\vec u_0^A \times \vec u_0^B} \right) \cdot \vec u_2^A} \right\| + \\l_0^B\left\| {\left( {\vec u_0^A \times \vec u_0^B} \right) \cdot \vec u_0^B} \right\| + l_1^B\left\| {\left( {\vec u_0^A \times \vec u_0^B} \right) \cdot \vec u_1^B} \right\| + l_2^B\left\| {\left( {\vec u_0^A \times \vec u_0^B} \right) \cdot \vec u_2^B} \right\|\end{array}\]

利用点积、叉积的性质\(\vec u \cdot \left( {\vec v \times \vec w} \right) = \vec w \cdot \left( {\vec u \times \vec v} \right) = \vec v \cdot \left( {\vec w \times \vec u} \right)\),不等式可以化简为

\[\begin{array}{l}\left\| {\vec t \cdot \left( {\vec u_0^A \times \vec u_0^B} \right)} \right\| \succ l_0^A\left\| {\left( {\vec u_0^A \times \vec u_0^A} \right) \cdot \vec u_0^B} \right\| + l_1^A\left\| {\left( {\vec u_1^A \times \vec u_0^A} \right) \cdot \vec u_0^B} \right\| + l_2^A\left\| {\left( {\vec u_2^A \times \vec u_0^A} \right) \cdot \vec u_0^B} \right\| + \\l_0^B\left\| {\left( {\vec u_0^B \times \vec u_0^B} \right) \cdot \vec u_0^A} \right\| + l_1^B\left\| {\left( {\vec u_0^B \times \vec u_1^B} \right) \cdot \vec u_0^A} \right\| + l_2^B\left\| {\left( {\vec u_0^B \times \vec u_2^B} \right) \cdot \vec u_0^A} \right\|\end{array}\]

\(\vec u_0^k,\vec u_1^k,\vec u_2^k\)是互相垂直的单位长度的轴线,有\(\vec u_0^k \times \vec u_1^k = {c_2}\vec u_2^k,\vec u_1^k \times \vec u_2^k = {c_0}\vec u_0^k,\vec u_2^k \times \vec u_0^k = {c_1}\vec u_1^k\),其中\({c_0},{c_1},{c_2} \in \{ - 1,1\} ,k \in \{ A,B\} \),不等式继续化简,得

\[\left\| {\vec t \cdot \left( {\vec u_0^A \times \vec u_0^B} \right)} \right\| \succ l_1^A\left\| {\vec u_2^A \cdot \vec u_0^B} \right\| + l_2^A\left\| {\vec u_1^A \cdot \vec u_0^B} \right\| + l_1^B\left\| {\vec u_2^B \cdot \vec u_0^A} \right\| + l_2^B\left\| {\vec u_1^B \cdot \vec u_0^A} \right\|\]

共需要5个求绝对值操作,25个乘法操作,16个加/减法操作。

第i种类型的轴有3条,第ii种类型的轴有3条,第iii种类型的轴有9条,总共需要69个求绝对值操作,315个乘法操作,216个加/减法操作。

我们可以进一步优化上面的不等式,以包围盒\(A\)为参考系,\(A\)的中心为原点,它的3条轴线分别是\(\vec{u}_{0}^{A}=(1,0,0),\vec{u}_{1}^{A}=(0,1,0),\vec{u}_{2}^{A}=(0,0,1)\)。相对于包围盒\(A\)\(B\)的中心坐标用\(C\)表示,它的3条轴线分别用\({{\vec{u}}_{0}},{{\vec{u}}_{1}},{{\vec{u}}_{2}}\)表示,有

\[\left\{ \begin{array}{l}C = \left( {({C^B} - {C^A}) \cdot \vec u_0^A,({C^B} - {C^A}) \cdot \vec u_1^A,({C^B} - {C^A}) \cdot \vec u_2^A} \right)\\{{\vec u}_0} = \left( {\vec u_0^B \cdot \vec u_0^A,\vec u_0^B \cdot \vec u_1^A,\vec u_0^B \cdot \vec u_2^A} \right)\\{{\vec u}_1} = \left( {\vec u_1^B \cdot \vec u_0^A,\vec u_1^B \cdot \vec u_1^A,\vec u_1^B \cdot \vec u_2^A} \right)\\{{\vec u}_2} = \left( {\vec u_2^B \cdot \vec u_0^A,\vec u_2^B \cdot \vec u_1^A,\vec u_2^B \cdot \vec u_2^A} \right)\end{array} \right.\]

现在用新的坐标表示优化上面的不等式。

       i种类型:

\[\begin{array}{l}\left\| {C \cdot \left( {1,0,0} \right)} \right\| \succ l_0^A + l_0^B\left\| {\left( {1,0,0} \right) \cdot {{\vec u}_0}} \right\| + l_1^B\left\| {\left( {1,0,0} \right) \cdot {{\vec u}_1}} \right\| + l_2^B\left\| {\left( {1,0,0} \right) \cdot {{\vec u}_2}} \right\|\\ \Leftrightarrow \left\| {{C_x}} \right\| \succ l_0^A + l_0^B\left\| {{{\vec u}_{0,x}}} \right\| + l_1^B\left\| {{{\vec u}_{1,x}}} \right\| + l_2^B\left\| {{{\vec u}_{2,x}}} \right\|\end{array}\]

共需要4个求绝对值操作,3个乘法操作,3个加/减法操作。

       ii种类型:

\[\begin{array}{l}\left\| {C \cdot {{\vec u}_0}} \right\| \succ l_0^A\left\| {{{\vec u}_0} \cdot \left( {1,0,0} \right)} \right\| + l_1^A\left\| {{{\vec u}_0} \cdot \left( {0,1,0} \right)} \right\| + l_2^A\left\| {{{\vec u}_0} \cdot \left( {0,0,1} \right)} \right\| + l_0^B\\ \Leftrightarrow \left\| {C \cdot {{\vec u}_0}} \right\| \succ l_0^A\left\| {{{\vec u}_{0,x}}} \right\| + l_1^A\left\| {{{\vec u}_{0,y}}} \right\| + l_2^A\left\| {{{\vec u}_{0,z}}} \right\| + l_0^B\end{array}\]

共需要4个求绝对值操作,6个乘法操作,5个加/减法操作。

       iii种类型:

\[\begin{array}{l}\left\| {C \cdot \left( {\left( {1,0,0} \right) \times {{\vec u}_0}} \right)} \right\| \succ l_1^A\left\| {\left( {0,0,1} \right) \cdot {{\vec u}_0}} \right\| + l_2^A\left\| {\left( {0,1,0} \right) \cdot {{\vec u}_0}} \right\| + l_1^B\left\| {{{\vec u}_2} \cdot \left( {1,0,0} \right)} \right\| + l_2^B\left\| {{{\vec u}_1} \cdot \left( {1,0,0} \right)} \right\|\\ \Leftrightarrow \left\| { - {u_{0,z}}{C_y} + {u_{0,y}}{C_z}} \right\| \succ l_1^A\left\| {{u_{0,z}}} \right\| + l_2^A\left\| {{u_{0,y}}} \right\| + l_1^B\left\| {{u_{2,x}}} \right\| + l_2^B\left\| {{u_{1,x}}} \right\|\end{array}\]

共需要5个求绝对值操作,6个乘法操作,4个加/减法操作。

第i种类型的轴有3条,第ii种类型的轴有3条,第iii种类型的轴有9条,优化后的方法总共需要69个求绝对值操作,81个乘法操作,60个加/减法操作。若算上坐标变换的操作,总共需要69个求绝对值操作,117个乘法操作,87个加/减法操作。可以发现,不等式中会重复使用轴线\({{\vec{u}}_{i}},i\in \{0,1,2\}\)中元素的绝对值,可以把它们保存起来备用,避免后面对同一个值重复求绝对值,所以算法总共只需要24个求绝对值操作。

Akenine-Möller等[14]指出,以不同的顺序对轴线进行检测,会对程序性能有一定的影响。可以先进行最简单的轴线检测,做出快速的重叠排除测试,轴线检测顺序是:第i种类型,第ii种类型,第iii种类型。根据具体的应用,可以在有向包围盒与有向包围盒相交测试之前增加一个快速的排除测试,包围球体的球心在包围盒的中心,根据包围盒的半长\({{l}_{0}},{{l}_{1}},{{l}_{2}}\)可以计算出球体的半径,然后通过球体与球体的重叠测试,进行快速排除检测。

有向包围盒与有向包围盒的重叠测试的伪码如下所示:

有向包围盒\({{C}^{A}}+h_{0}^{A}\vec{u}_{0}^{A}+h_{1}^{A}\vec{u}_{1}^{A}+h_{2}^{A}\vec{u}_{2}^{A}\)与有向包围盒\({{C}^{B}}+h_{0}^{B}\vec{u}_{0}^{B}+h_{1}^{B}\vec{u}_{1}^{B}+h_{2}^{B}\vec{u}_{2}^{B}\)的重叠测试,其中\(-l_{0}^{k}\le h_{0}^{k}\le l_{0}^{k},-l_{1}^{k}\le h_{1}^{k}\le l_{1}^{k},-l_{2}^{k}\le h_{2}^{k}\le l_{2}^{k},\left\| \vec{u}_{0}^{k} \right\|=\left\| \vec{u}_{1}^{k} \right\|=\left\| \vec{u}_{2}^{k} \right\|=1,l_{0}^{k},l_{1}^{k},l_{2}^{k}\succ 0,k\in \{A,B\}\)
return ({DISJOINT,OVERLAPPING})
1.    \(\vec{o}={{C}^{B}}-{{C}^{A}}\);
2.    \(C=\left( \vec{o}\cdot \vec{u}_{0}^{A},\vec{o}\cdot \vec{u}_{1}^{A},\vec{o}\cdot \vec{u}_{2}^{A} \right)\);
3.    \({{\vec{u}}_{0}}=\left( \vec{u}_{0}^{B}\cdot \vec{u}_{0}^{A},\vec{u}_{0}^{B}\cdot \vec{u}_{1}^{A},\vec{u}_{0}^{B}\cdot \vec{u}_{2}^{A} \right)\);
4.    \({{\vec{u}}_{1}}=\left( \vec{u}_{1}^{B}\cdot \vec{u}_{0}^{A},\vec{u}_{1}^{B}\cdot \vec{u}_{1}^{A},\vec{u}_{1}^{B}\cdot \vec{u}_{2}^{A} \right)\);
5.    \({{\vec{u}}_{2}}=\left( \vec{u}_{2}^{B}\cdot \vec{u}_{0}^{A},\vec{u}_{2}^{B}\cdot \vec{u}_{1}^{A},\vec{u}_{2}^{B}\cdot \vec{u}_{2}^{A} \right)\);
6.    \(f{{u}_{0}}=\left( \left\| {{u}_{0,x}} \right\|,\left\| {{u}_{0,y}} \right\|,\left\| {{u}_{0,z}} \right\| \right)\);
7.    \(f{{u}_{1}}=\left( \left\| {{u}_{1,x}} \right\|,\left\| {{u}_{1,y}} \right\|,\left\| {{u}_{1,z}} \right\| \right)\);
8.    \(f{{u}_{2}}=\left( \left\| {{u}_{2,x}} \right\|,\left\| {{u}_{2,y}} \right\|,\left\| {{u}_{2,z}} \right\| \right)\);
9.    if \(\left\| {{C}_{x}} \right\|\succ l_{0}^{A}+l_{0}^{B}\cdot f{{u}_{0,x}}+l_{1}^{B}\cdot f{{u}_{1,x}}+l_{2}^{B}\cdot f{{u}_{2,x}}\) or             //检测轴\(\left( 1,0,0 \right)\)
\(\left\| {{C}_{y}} \right\|\succ l_{1}^{A}+l_{0}^{B}\cdot f{{u}_{0,y}}+l_{1}^{B}\cdot f{{u}_{1,y}}+l_{2}^{B}\cdot f{{u}_{2,y}}\) or             //检测轴\(\left( 0,1,0 \right)\)
\(\left\| {{C}_{z}} \right\|\succ l_{2}^{A}+l_{0}^{B}\cdot f{{u}_{0,z}}+l_{1}^{B}\cdot f{{u}_{1,z}}+l_{2}^{B}\cdot f{{u}_{2,z}}\), then         //检测轴\(\left( 0,0,1 \right)\)
10.          return DISJOINT;
11.   end if;
12.   if \(\left\| C\cdot {{{\vec{u}}}_{0}} \right\|\succ l_{0}^{A}f{{u}_{0,x}}+l_{1}^{A}f{{u}_{0,y}}+l_{2}^{A}f{{u}_{0,z}}+l_{0}^{B}\) or                    //检测轴\({{\vec{u}}_{0}}\)
\(\left\| C\cdot {{{\vec{u}}}_{1}} \right\|\succ l_{0}^{A}f{{u}_{1,x}}+l_{1}^{A}f{{u}_{1,y}}+l_{2}^{A}f{{u}_{1,z}}+l_{1}^{B}\) or                    //检测轴\({{\vec{u}}_{1}}\)
\(\left\| C\cdot {{{\vec{u}}}_{z}} \right\|\succ l_{0}^{A}f{{u}_{2,x}}+l_{1}^{A}f{{u}_{2,y}}+l_{2}^{A}f{{u}_{2,z}}+l_{2}^{B}\), then         //检测轴\({{\vec{u}}_{2}}\)
13.          return DISJOINT;
14.   end if;
15.   \(s=\left\| -{{u}_{0,z}}\cdot {{C}_{y}}+{{u}_{0,y}}\cdot {{C}_{z}} \right\|,{{r}_{A}}={{l}_{1}}\cdot f{{u}_{0,z}}+{{l}_{2}}\cdot f{{u}_{0,y}},{{r}_{B}}={{l}_{1}}\cdot f{{u}_{2,x}}+{{l}_{2}}\cdot f{{u}_{1,x}}\);
16.   if \(s\succ {{r}_{A}}+{{r}_{B}}\), then                                                     //检测轴\(\left( 1,0,0 \right)\times {{\vec{u}}_{0}}\)
17.          return DISJOINT;
18.   end if;
19.   \(s=\left\| -{{u}_{1,z}}\cdot {{C}_{y}}+{{u}_{1,y}}\cdot {{C}_{z}} \right\|,{{r}_{A}}={{l}_{1}}\cdot f{{u}_{1,z}}+{{l}_{2}}\cdot f{{u}_{1,y}},{{r}_{B}}={{l}_{0}}\cdot f{{u}_{2,x}}+{{l}_{2}}\cdot f{{u}_{0,x}}\);
20.   if \(s\succ {{r}_{A}}+{{r}_{B}}\), then                                                     //检测轴\(\left( 1,0,0 \right)\times {{\vec{u}}_{1}}\)
21.          return DISJOINT;
22.   end if;
23.   \(s=\left\| -{{u}_{2,z}}\cdot {{C}_{y}}+{{u}_{2,y}}\cdot {{C}_{z}} \right\|,{{r}_{A}}={{l}_{1}}\cdot f{{u}_{2,z}}+{{l}_{2}}\cdot f{{u}_{2,y}},{{r}_{B}}={{l}_{0}}\cdot f{{u}_{1,x}}+{{l}_{1}}\cdot f{{u}_{0,x}}\);
24.   if \(s\succ {{r}_{A}}+{{r}_{B}}\), then                                                     //检测轴\(\left( 1,0,0 \right)\times {{\vec{u}}_{2}}\)
25.          return DISJOINT;
26.   end if;
27.   \(s=\left\| {{u}_{0,z}}\cdot {{C}_{x}}-{{u}_{0,x}}\cdot {{C}_{z}} \right\|,{{r}_{A}}={{l}_{0}}\cdot f{{u}_{0,z}}+{{l}_{2}}\cdot f{{u}_{0,x}},{{r}_{B}}={{l}_{1}}\cdot f{{u}_{2,y}}+{{l}_{2}}\cdot f{{u}_{1,y}}\);
28.   if \(s\succ {{r}_{A}}+{{r}_{B}}\), then                                                     //检测轴\(\left( 0,1,0 \right)\times {{\vec{u}}_{0}}\)
29.          return DISJOINT;
30.   end if;
31.   \(s=\left\| {{u}_{1,z}}\cdot {{C}_{x}}-{{u}_{1,x}}\cdot {{C}_{z}} \right\|,{{r}_{A}}={{l}_{0}}\cdot f{{u}_{1,z}}+{{l}_{2}}\cdot f{{u}_{1,x}},{{r}_{B}}={{l}_{0}}\cdot f{{u}_{2,y}}+{{l}_{2}}\cdot f{{u}_{0,y}}\);
32.   if \(s\succ {{r}_{A}}+{{r}_{B}}\), then                                                     //检测轴\(\left( 0,1,0 \right)\times {{\vec{u}}_{1}}\)
33.          return DISJOINT;
34.   end if;
35.   \(s=\left\| {{u}_{2,z}}\cdot {{C}_{x}}-{{u}_{2,x}}\cdot {{C}_{z}} \right\|,{{r}_{A}}={{l}_{0}}\cdot f{{u}_{2,z}}+{{l}_{2}}\cdot f{{u}_{2,x}},{{r}_{B}}={{l}_{0}}\cdot f{{u}_{1,y}}+{{l}_{1}}\cdot f{{u}_{0,y}}\);
36.   if \(s\succ {{r}_{A}}+{{r}_{B}}\), then                                                     //检测轴\(\left( 0,1,0 \right)\times {{\vec{u}}_{2}}\)
37.          return DISJOINT;
38.   end if;
39.   \(s=\left\| -{{u}_{0,y}}\cdot {{C}_{x}}+{{u}_{0,x}}\cdot {{C}_{y}} \right\|,{{r}_{A}}={{l}_{0}}\cdot f{{u}_{0,y}}+{{l}_{1}}\cdot f{{u}_{0,x}},{{r}_{B}}={{l}_{1}}\cdot f{{u}_{2,z}}+{{l}_{2}}\cdot f{{u}_{1,z}}\);
40.   if \(s\succ {{r}_{A}}+{{r}_{B}}\), then                                                     //检测轴\(\left( 0,0,1 \right)\times {{\vec{u}}_{0}}\)
41.          return DISJOINT;
42.   end if;
43.   \(s=\left\| -{{u}_{1,y}}\cdot {{C}_{x}}+{{u}_{1,x}}\cdot {{C}_{y}} \right\|,{{r}_{A}}={{l}_{0}}\cdot f{{u}_{1,y}}+{{l}_{1}}\cdot f{{u}_{1,x}},{{r}_{B}}={{l}_{0}}\cdot f{{u}_{2,z}}+{{l}_{2}}\cdot f{{u}_{0,z}}\);
44.   if \(s\succ {{r}_{A}}+{{r}_{B}}\), then                                                     //检测轴\(\left( 0,0,1 \right)\times {{\vec{u}}_{1}}\)
45.          return DISJOINT;
46.   end if;
47.   \(s=\left\| -{{u}_{2,y}}\cdot {{C}_{x}}+{{u}_{2,x}}\cdot {{C}_{y}} \right\|,{{r}_{A}}={{l}_{0}}\cdot f{{u}_{2,y}}+{{l}_{1}}\cdot f{{u}_{2,x}},{{r}_{B}}={{l}_{0}}\cdot f{{u}_{1,z}}+{{l}_{1}}\cdot f{{u}_{0,z}}\);
48.   if \(s\succ {{r}_{A}}+{{r}_{B}}\), then                                                     //检测轴\(\left( 0,0,1 \right)\times {{\vec{u}}_{2}}\)
49.          return DISJOINT;
50.   end if;
51.   return OVERLAPPING;

spacer

Leave a reply