发布时间: 2018-12-16 摘要点击次数: 全文下载次数: DOI: 10.11834/jig.180050 2018 | Volume 23 | Number 12 虚拟现实与增强现实

 收稿日期: 2018-02-07; 修回日期: 2018-07-11 基金项目: 国家自然科学基金项目（61672148，61502092）；教育部—中国移动科研基金项目（MCM20160201）；辽宁省百千万人才工程基金项目（201514） 第一作者简介: 于瑞云, 1974年生, 男, 教授, 主要研究方向为群智感知与计算、移动大数据分析、混合现实技术等。E-mail:yury@mail.neu.edu.cn;赵金龙, 男, 硕士研究生, 主要研究方向为计算机视觉, 混合现实技术。Email:zjl1x1@163.com;余龙, 男, 硕士研究生, 主要研究方向为计算机视觉, 混合现实技术。Email:2436910023@qq.com. 中图法分类号: TP391 文献标识码: A 文章编号: 1006-8961(2018)12-1925-13

# 关键词

Collision detection algorithm based on AABB bounding box and space division
Yu Ruiyun, Zhao Jinlong, Yu Long, Zhang Qianni
Department of Software, Northeastern University, Shenyang 110819, China
Supported by: National Natural Science Foundation of China (61672148, 61502092); Ministry of Education-China Mobile Research Fund(MCM20160201)

# Abstract

Objective Collision detection is a key technique applied in virtual reality, especially in virtual assembly. A collision detection algorithm based on an object space uses three-dimensional geometric features of the object for expansion and calculation. This phenomenon is evaluated by two methods, namely, a space division method and a bounding box method. The collision detection algorithm based on the bounding box method has attracted considerable attention and is widely used globally. The testing between the bounding boxes increases the possibility of collision detection errors. This condition can be explained by the use of an algorithm based on the axis-aligned bounding box (AABB) hierarchy binary tree that has many testing nodes but lowers detection efficiency in several cases. The space division method divides the entire virtual space into a sequence of equally sized cells and only detects objects in the same cell. The space division method is suitable for consistently distributed and sparse objects. The cells are divided into small sizes for cases with many objects and irregular distribution. The intersection tests between the collections of cells reduce the collision detection speed and require considerable storage space. To solve the problems of traditional collision detection algorithms, this study proposes a collision detection algorithm based on AABB bounding box and space division. Method The proposed algorithm utilizes a step-by-step detection method. In the pre-detection phase of the algorithm, a bounding box is generated for each object in the scene. This method determines the intersection area of the two bounding boxes based on the AABB algorithm. Subsequently, the method divides the areas of intersections to conduct cross-tests on each planned area. The algorithm combines the direction and movement trend of the model to create a space division. The intersection of space-time related parts is evaluated based on the corresponding correlation of collision detection. In this algorithm, the spatial correlation of the object is used to reduce the detection range, which improves the efficiency of the algorithm. The transfer of bounding box into triangle surfaces and points is used to reduce detection errors. The algorithm refines the interference detection between the triangle plane and points. This process directly restores the collision detection between various models. In addition, the algorithm uses a rapid detection method to determine whether a set of points passes through a triangle or not. The detection method conducted in two steps obviously improves the efficiency of the collision detection algorithm. Result In the experiment, five typical experimental environments are established to compare the AABB hierarchical bounding box binary tree algorithm, $k$-Dops(discrete orientation polytopes) bounding box algorithm, and BPS(Binary Space Partitioning Tree) spatial segmentation tree algorithm. Two kettle models with a large number of triangular faces are used as the experimental model. The model has planes, surfaces, and rings, which can verify the advantages and disadvantages of the algorithm. The five experimental environments are built to evaluate the geometric collision accuracy, collision detection time loss in the translation degree of freedom and rotation degree of freedom, and the impact of the number of triangle faces on collision detection of the algorithm. In terms of geometric collision accuracy, six locations are randomly selected in performing collision detection. At the same position, the algorithm is used to perform collision detection by using three traditional algorithms. The space difference between the three algorithms and the proposed algorithm is recorded. The distance between the proposed algorithm and AABB algorithm and the distance between the algorithm and $k$-Dops algorithm exceed the threshold of 0.02 in most cases. Visible visual gaps are observed when the distance exceeds 0.02. This finding proves that the algorithm remarkably improves the collision geometry accuracy. In terms of collision time consumption and collision detection difficulty, the proposed algorithm reduces the detection time by more than 50% in contrast to the AABB algorithm and BSP algorithm for the translation degree of freedom. Moreover, the proposed algorithm reduces the detection time by more than 50% in contrast to the $k$-Dops algorithm and AABB algorithm in the rotation degree of freedom. The experimental results show that the proposed algorithm attains superior performance in the calculation of collision detection for complex models. In terms of the influence of triangle number on the algorithm's collision detection time consumption, two groups of experiments are conducted in this study. We use a coordinate positioning method to ensure that each collision detection position is the same and the required time for each collision detection in the current position is obtained. In the first set of experiments, a teapot model with 530 faces is set as the dynamic model, and a model with different number of faces is set as the static model. In the second group of experiments, a teapot model with a face number of 530 is set as the static model, and a model with different number of faces is set as the dynamic model. The experiment result shows that the computational time cost of the proposed algorithm is less than those of the AABB algorithm and the BSP algorithm when collision detection occurs at the same location. The proposed algorithm shows high stability when the triangle number of the motion model is large. The algorithm reduces the detection scope to reduce the cost and improves the detection efficiency of the algorithm and the geometric accuracy of collision detection. Conclusion This study proposes a collision detection algorithm that combines the bounding box and space division methods. The proposed algorithm utilizes the advantages of the bounding box method, such as easy update, speed, compactness, and simple cross-section testing, to rapidly exclude the disjoint objects and determine the areas that may intersect. At the same time, the probability of model collision in the same partition space is increased using the space division method. The space division method reduces the collision detection time and invariably improves the collision detection accuracy. The proposed algorithm is suitable in virtual assembly technology field, which can increase its accuracy and can satisfy the real-time interaction of the users.

# Key words

virtual assembly; AABB bounding boxes; space division; collision detection; the step detection; space-time correlation; triangle faces

# 1 相关工作

OBB方向包围盒的定义为包含几何对象且相对于坐标轴方向任意的最小长方体。OBB在构造上较复杂，关键在于确定包围盒的方向，最佳方向是保证在该方向上可以得到一个尺寸最小的包围盒。确定OBB方向包围盒，首先要利用所有顶点向量求出平均向量，利用平均向量计算出协方差矩阵，再求出协方差矩阵的特征向量，将这个特征向量单位化之后，设定这个向量为OBB包围盒的局部坐标轴向。将所有顶点向局部坐标向量轴投影，在3个轴向上的最大值和最小值的距离差为OBB包围盒的大小，顶点均值为OBB包围盒中心。OBB包围盒的相交测试也利用分轴定理，即选定两个OBB包围盒的分离轴。一般情况下会确定15条分离轴，当有一条分离轴检测到投影不重叠即判定两包围盒不相交。文献[11]研究了一种AABB和OBB相结合的碰撞检测算法，首先通过对象投影来快速剔除不相交的物体，接着用AABB构建剩下的物体，初步判断出可能相交的物体，最后用OBB来精确检测。

$k$-Dops包围盒构造起来要比AABB包围盒和OBB包围盒困难，但碰撞检测的精确度要高于AABB包围盒和OBB包围盒。文献[12]中提到$k$-Dops包围盒是一种由$k$/2个平行平面对组成的多面体，它是AABB包围盒的推广和一般化，目的是增加AABB包围盒的包围效率。$k$-Dops包围盒的问题在于它是AABB包围盒的一般化，必须在所包含的物体旋转时进行更新。对于$k$-Dops包围盒的相交判断，文献[13]中提到由于所有的$k$-Dops包围盒都由来自同一个集合$\mathit{\boldsymbol{D}}$中的方向向量所定义，所以$k$-Dops间的相交测试也较简单。$\mathit{\boldsymbol{D}}$中有$k$/2对方向相反的向量对，$k$-Dops在每对向量上的最大延伸确定了它在该对向量上的投影区间，一个$k$-Dops包围盒可由在这些向量对上的$k$/2个投影区间所确定。因此，$k$-Dops包围盒间的相交测试可以通过投影区间的重叠测试来完成，只要两个$k$-Dops包围盒在$\mathit{\boldsymbol{D}}$中某一个方向对上的投影区间不重叠，就可以判定它们是不相交的，如果它们在$\mathit{\boldsymbol{D}}$中所有方向对上的投影区间都重叠，则认为它们是相交的。

 ${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}} = \left\{ {\mathit{\boldsymbol{p}}\left| {\mathit{\boldsymbol{p}}.x \in {\mathit{\boldsymbol{U}}_x},\mathit{\boldsymbol{p}}.y \in {\mathit{\boldsymbol{U}}_y},\mathit{\boldsymbol{p}}.z \in {\mathit{\boldsymbol{U}}_z}} \right.} \right\}$ (1)

 ${\mathit{\boldsymbol{U}}_x} = {\mathit{\boldsymbol{U}}_{{\rm{A}}x}}\left( {{X_{{\rm{Amin}}}},{X_{{\rm{Amax}}}}} \right) \cap {\mathit{\boldsymbol{U}}_{{\rm{B}}x}}\left( {{X_{{\rm{Bmin}}}},{X_{{\rm{Bmax}}}}} \right)$ (2)

 ${\mathit{\boldsymbol{U}}_y} = {\mathit{\boldsymbol{U}}_{{\rm{A}}y}}\left( {{Y_{{\rm{Amin}}}},{Y_{{\rm{Amax}}}}} \right) \cap {\mathit{\boldsymbol{U}}_{{\rm{B}}y}}\left( {{Y_{{\rm{Bmin}}}},{Y_{{\rm{Bmax}}}}} \right)$ (3)

 ${\mathit{\boldsymbol{U}}_z} = {\mathit{\boldsymbol{U}}_{{\rm{A}}z}}\left( {{Z_{{\rm{Amin}}}},{Z_{{\rm{Amax}}}}} \right) \cap {\mathit{\boldsymbol{U}}_{{\rm{B}}z}}\left( {{Z_{{\rm{Bmin}}}},{Z_{{\rm{Bmax}}}}} \right)$ (4)

 ${\mathit{\boldsymbol{V}}_1} = \mathit{\boldsymbol{b}} - \mathit{\boldsymbol{a}}$ (9)

 ${\mathit{\boldsymbol{V}}_2} = \mathit{\boldsymbol{c}} - \mathit{\boldsymbol{a}}$ (10)

 $\mathit{\boldsymbol{N}} = n\left( {{\mathit{\boldsymbol{V}}_1} \times {\mathit{\boldsymbol{V}}_2}} \right)$ (11)

 $D = \mathit{\boldsymbol{N}} \cdot \mathit{\boldsymbol{a}}$ (12)

 ${D_{q1}} = \mathit{\boldsymbol{N}} \cdot {\mathit{\boldsymbol{Q}}_1}$ (13)

 ${D_{q2}} = \mathit{\boldsymbol{N}} \cdot {\mathit{\boldsymbol{Q}}_2}$ (14)

 ${D_1} = {D_{q1}} - D$ (15)

 ${D_2} = {D_{q2}} - D$ (16)

 $\begin{array}{*{20}{c}} {\mathit{\boldsymbol{N}}.x \times \left( {x - a.x} \right) + \mathit{\boldsymbol{N}}.y \times \left( {y - a.y} \right) + }\\ {\mathit{\boldsymbol{N}}.z \times \left( {z - a.z} \right) = 0} \end{array}$ (18)

 $t = \frac{{\left( \begin{array}{l} \left( {a.x - {D_{q1}} \cdot x} \right) \times \mathit{\boldsymbol{N}}.x + \\ \left( {a.y - {D_{q1}} \cdot y} \right) \times \mathit{\boldsymbol{N}}.y + \\ \left( {a.z - {D_{q1}} \cdot z} \right) \times \mathit{\boldsymbol{N}}.z \end{array} \right)}}{{\left( \begin{array}{l} \mathit{\boldsymbol{N}}.x \times {D_{q2}} \cdot x + \\ \mathit{\boldsymbol{N}}.y \times {D_{q2}} \cdot y + \\ \mathit{\boldsymbol{N}}.z \times {D_{q2}} \cdot z \end{array} \right)}}$ (19)

# 2.3 模型更新

 $\left( {x',y',z',1} \right) = \left( {x,y,z,1} \right)\left[ {\begin{array}{*{20}{c}} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ {{t_x}}&{{t_y}}&{{t_z}}&1 \end{array}} \right]$ (20)

 $\mathit{\boldsymbol{Rot}}\left( {x,\alpha } \right) = \left[ {\begin{array}{*{20}{c}} 1&0&0&0\\ 0&{\cos \alpha }&{\sin \alpha }&0\\ 0&{ - \sin \alpha }&{\cos \alpha }&0\\ 0&0&0&1 \end{array}} \right]$ (21)

 $\mathit{\boldsymbol{Rot}}\left( {y,\beta } \right) = \left[ {\begin{array}{*{20}{c}} {\cos \beta }&0&{ - \sin \beta }&0\\ 0&1&0&0\\ {\sin \beta }&0&{\cos \beta }&0\\ 0&0&0&1 \end{array}} \right]$ (22)

 $\mathit{\boldsymbol{Rot}}\left( {z,\gamma } \right) = \left[ {\begin{array}{*{20}{c}} {\cos \gamma }&{\sin \gamma }&0&0\\ { - \sin \gamma }&{\cos \gamma }&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{array}} \right]$ (23)

# 3.4 三角面数对算法时耗的影响测试

Table 1 Time consumption of less faces motion model

 静止对象的三角面数 移动对象的三角面数 DASSD算法的计算耗时/ms AABB算法的计算耗时/ms BSP算法的计算耗时/ms 1 2 124 530 1.70 1.90 2.32 2 4 031 530 4.30 6.20 5.99 3 6 009 530 7.90 10.90 13.56 4 8 106 530 9.80 16.50 15.22

Table 2 Time consumption of more faces motion model

 静止对象的三角面数 移动对象的三角面数 DASSD算法的计算耗时/ms AABB算法的计算耗时/ms BSP算法的计算耗时/ms 1 530 2 124 2.20 32.40 6.23 2 530 4 031 3.20 101.60 10.11 3 530 6 009 6.50 148.50 18.52 4 530 8 106 8.80 216.70 24.44

# 参考文献

• [1] Cecil J, Jones J. VREM:an advanced virtual environment for micro assembly[J]. International Journal of Advanced Manufacturing Technology, 2014, 72(1-4): 47–56. [DOI:10.1007/s00170-014-5618-9]
• [2] Smith A, Kitamura Y, Takemura H, et al. A simple and efficient method for accurate collision detection among deformable polyhedral objects in arbitrary motion[C]//Virtual Reality Annual International Symposium. Research Triangle Park, NC: IEEE, 1995: 136-145.[DOI: 10.1109/VRAIS.1995.512489]
• [3] Palmer I J, Grimsdale R L. Collision detection for animation using sphere-trees[J]. Computer Graphics Forum, 1995, 14(2): 105–116. [DOI:10.1111/1467-8659.1420105]
• [4] Gottschalk S, Lin M C, Manocha D. OBBTree: a hierarchical structure for rapid interference detection[C]//Proceedings of the 23rd annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1996: 171-180.[DOI: 10.1145/237170.237244]
• [5] Kay T L, Kajiya J T. Ray tracing complex scenes[J]. ACM Siggraph Computer Graphics, 1986, 20(4): 269–278. [DOI:10.1145/15886.15916]
• [6] Xing Y S, Liu X P, Xu S P. Efficient collision detection based on AABB trees and sort algorithm[C]//Proceedings of IEEE ICCA 2010. Xiamen: IEEE, 2010: 328-332.[DOI: 10.1109/ICCA.2010.5524093]
• [7] Chang J W, Kim M S. Efficient triangle-triangle intersection test for OBB-based collision detection[J]. Computers & Graphics, 2009, 33(3): 235–240. [DOI:10.1016/j.cag.2009.03.009]
• [8] Pan Z K, Li J B. Collision detection algorithm based on compressed AABB tree[J]. Computer Science, 2005, 32(2): 213–215. [潘振宽, 李建波. 基于压缩的AABB树的碰撞检测算法[J]. 计算机科学, 2005, 32(2): 213–215. ] [DOI:10.3969/j.issn.1002-137X.2005.02.059]
• [9] Fang B, Wang Z L, Guo X W. Four-dimensional space and time hierarchical collision detection method based on AABB bounding box[J]. Computer Measurement & Control, 2014, 22(2): 397–399, 420. [方彬, 王竹林, 郭希维. 基于AABB的四维时空层次包围盒碰撞检测方法[J]. 计算机测量与控制, 2014, 22(2): 397–399, 420. ] [DOI:10.3969/j.issn.1671-4598.2014.02.027]
• [10] Jin Y X, Qin Z P, Li Z. Deformation collision detection algorithm fusing R-Sphere bounding volume[J]. Computer Engineering and Design, 2017, 38(1): 92–96. [靳雁霞, 秦志鹏, 李照. 融合R-Sphere包围球的变形体碰撞检测算法[J]. 计算机工程与设计, 2017, 38(1): 92–96. ] [DOI:10.16208/j.issn1000-7024.2017.01.018]
• [11] Hu Y M. A hybrid collision detection algorithm based on bounding volume hierarchy[J]. Computer Engineering and Science, 2012, 34(6): 127–130. [胡咏梅. 基于层次包围盒的混合碰撞检测算法[J]. 计算机工程与科学, 2012, 34(6): 127–130. ] [DOI:10.3969/j.issn.1007-130X.2012.06.025]
• [12] Li L, Zhang Y J. A survey on algorithms of non-negative matrix factorization[J]. Acta Electronica Sinica, 2008, 36(4): 737–743. [李乐, 章毓晋. 非负矩阵分解算法综述[J]. 电子学报, 2008, 36(4): 737–743. ] [DOI:10.3321/j.issn:0372-2112.2008.04.023]
• [13] Zhang P, Du G L. A fast continuous collision detection algorithm based on K_DOPs[C]//Proceedings of 2011 International Conference on Electronics, Communications and Control. Ningbo: IEEE, 2011: 617-621.[DOI: 10.1109/ICECC.2011.6066778]
• [14] Sun J G, Wu S H. Collision detection algorithm based on ellipsoid bounding box and spatial decomposition[J]. Computer Engineering and Applications, 2016, 52(4): 217–222. [孙劲光, 吴素红. 基于空间分割与椭球包围盒的碰撞检测算法[J]. 计算机工程与应用, 2016, 52(4): 217–222. ] [DOI:10.3778/j.issn.1002-8331.1405-0105]
• [15] Wang W, Zhou C, Yang Y, et al. Virtual maintenance-oriented collision detection algorithm[J]. Computer Applications and Software, 2016, 33(4): 235–238. [王崴, 周诚, 杨云, 等. 面向虚拟维修的碰撞检测算法[J]. 计算机应用与软件, 2016, 33(4): 235–238. ] [DOI:10.3969/j.issn.1000-386x.2016.04.055]
• [16] Song T, Shu T, Mei C, et al. A collision detection algorithm based on spatial partitioning and hybrid bounding box[J]. Fire Control & Command Control, 2016, 41(11): 94–97. [宋涛, 舒涛, 梅朝, 等. 基于空间分解与混合包围盒的碰撞检测算法[J]. 火力与指挥控制, 2016, 41(11): 94–97. ] [DOI:10.3969/j.issn.1002-0640.2016.11.022]