# 9.2. 包围盒

## 9.2. 包围盒

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

${A^M} = \sum\limits_{k = 0}^{n – 1} {{A^k}}$

${M^M} = \frac{1}{{{A^M}}}\sum\limits_{k = 0}^{n – 1} {{A^k}{m^k}}$

${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}$

$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}$

${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}$

${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}$

$\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}$

$\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.2.2. 射线与包围盒的相交测试

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

$\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}$

${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}$

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.    射线与有向包围盒的相交测试

$\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}$

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. 线段与包围盒的重叠测试

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

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

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

${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}$

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

${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}$

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

$\left\| { – {w_z}{M_y} + {w_y}{M_z}} \right\| \succ {l_1}\left\| {{w_z}} \right\| + {l_2}\left\| {{w_y}} \right\|$

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.2.4. 平面与包围盒的相交测试

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

$\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}$

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’ = \left( {\vec n \cdot {{\vec u}_0},\vec n \cdot {{\vec u}_1},\vec n \cdot {{\vec u}_2}} \right) \tag{9.19}$

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}$

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. 三角形与包围盒的重叠测试

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

${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.     [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}}$$。

$$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\|$$

• 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}}$$。

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. 有向包围盒与有向包围盒的重叠测试

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

• 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\}$$；

${{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\|$

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$

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}$

$\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\|$

$\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}$

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}$

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}$

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

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;