Print

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




    虚拟现实与增强现实    




  <<上一篇 




  下一篇>> 





结合轴对齐包围盒和空间划分的碰撞检测算法
expand article info 于瑞云, 赵金龙, 余龙, 张倩妮
东北大学软件学院, 沈阳 110819

摘要

目的 碰撞检测是虚拟现实,特别是虚拟装配中的关键技术。针对基于包围盒的碰撞检测算法的准确性和检测效率不足的问题,提出一种结合AABB轴对齐包围盒和空间划分的碰撞检测算法。方法 本文算法采用分步检测的方法,利用AABB算法来确定两包围盒的相交区域后,结合模型移动方向和运动趋势进行空间划分,利用碰撞检测的时空相关性,对时空相关的部分进行相交测试,通过将包围盒还原成三角面以及点的方式来保证检测的准确性。结果 本文算法与AABB层次包围盒二叉树算法、$k$-Dops包围盒算法以及BPS空间分割树算法进行对比实验分析。在碰撞的几何精度上,本文算法在大部分情况下与AABB算法和$k$-Dops算法的距离差超过阈值0.02,证明本文算法在碰撞几何精度上有明显的提高。在碰撞检测时耗上,随着碰撞检测难度的不断增加,本文算法在平移自由度下比AABB算法和BSP算法、在旋转自由度下比AABB算法和$k$-Dops算法的检测时间均降低了50%以上。在三角面数对算法碰撞检测时耗的影响上,当运动模型的三角面数较多时,本文算法表现出更高的稳定性。结论 结合AABB包围盒和空间划分方法的碰撞检测算法,在减少碰撞检测所需时间的同时提高了碰撞检测的准确性,可以满足虚拟装配技术中对碰撞检测算法准确性的要求,同时也能满足使用者实时性的交互习惯。

关键词

虚拟装配; AABB包围盒; 空间划分; 碰撞检测; 分步检测; 时空相关性; 三角面

Collision detection algorithm based on AABB bounding box and space division
expand article info 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

0 引言

虚拟现实(VR)技术是一种可以在虚拟环境中完成一系列动作的计算机技术,随着计算机软硬件的不断发展,虚拟环境的搭建越发完整,功能越发完善。虚拟现实技术利用计算机模拟三维动态视角和实体行为,利用鼠标、键盘、传感头盔、数据手套等设备进行交互,从而让操作它的用户在视觉、听觉和触觉上有一种身临其境的感觉。虚拟现实技术是基于计算机技术发展起来的,同时又给了计算机技术新的灵感,其中GPU等技术也得到了研究机构和企业的追捧。

虚拟装配技术是虚拟现实技术在设计与制造领域的重要应用之一,它已经引起了企业和研究机构的广泛关注。虚拟装配技术的发展与计算机技术、虚拟现实技术的发展紧密相关,近年来也取得了较好的发展,有些虚拟装配系统已经走出实验室,走进了企业。文献[1]中将虚拟装配描述为:利用计算机工具, 而不需产品或者支持过程的物理实现, 通过分析、预建模、可视化、数据表示等进行或者辅助进行装配相关的工程决策。这个定义较全面地描述了虚拟装配技术。

碰撞检测问题在计算机动画(computer nimation)、计算机图形学(CG)和虚拟现实等领域都有着重要的意义。碰撞检测算法就是检测虚拟环境中,虚拟物体是否发生穿透现象,所以碰撞检测算法对虚拟环境的真实性和实时性起到关键作用。然而在碰撞检测算法中, 真实性和实时性是两个相互矛盾的问题,真实性要求算法的准确性,实时性则要求算法的高效性,在游戏引擎中对实时性要求较高,而机械装配仿真行业则对真实性要求较高。

就碰撞检测算法中检测较为精确的算法而言,目前研究较成熟的方法为层次包围盒和空间分解法等。其中层次包围盒法是基于图形的碰撞检测算法,用特定的体积来近似描述特殊几何对象,从而只需要对较容易做相交判断的特定体积进行相交测试。

在实际使用中,层次包围盒是一种较常用的方法,常见的包围盒有轴对齐包围盒AABB(axis-aligned bounding boxes)[2]、球形包围盒spheres[3]、有向包围盒OBB(oriental bounding box)[4]和离散方向凸包围盒$k$-Dops(discrete orientation polytopes)[5]等。图 1所示为几种典型的包围盒在2维平面上的构造方式。空间分解法常用于要求较高精确度的碰撞检测中,该方法较符合人类对空间的认知和理解。

图 1 几种典型包围盒的构造方式
Fig. 1 The structure of several typical bounding box methods
((a) AABB; (b) ball; (c) OBB; (d) 6-Dops)

这些较成熟的算法大都不能在实时检测的情况下,提供准确的检测结果,所以本文提出一种在满足实时检测条件的同时,能给出较准确结果的碰撞检测算法。

1 相关工作

基于包围盒的碰撞检测算法在碰撞检测算法中较为重要。其基本思想是利用简单的几何体来包围复杂几何体,利用包围盒的相交测试代替复杂几何体的相交测试,从而大大提升计算效率。

沿坐标轴的包围盒AABB在碰撞检测的研究中使用得最久最广。一个给定对象的AABB包围盒被定义为包含该对象且各边平行于坐标轴的最小六面体[6-7]图 1(a)给出一个简化的2维平面中的AABB包围盒。给定对象的AABB包围盒通过遍历对象的所有顶点,找出顶点的$X$坐标、$Y$坐标和$Z$坐标的最大值和最小值来得到,而包围盒间的相交测试通过比较两个AABB包围盒在3个坐标轴上的投影区间是否均重叠来判断,因此AABB包围盒间的相交测试最多只需要6次比较运算。文献[8]通过对AABB包围盒的压缩优化了AABB方法,提高了测试的速度。文献[9]采用基于时间的AABB包围盒和间隔减半法剔除场景中不相交的物体,该方法较好地处理了高速运动物体的遗漏和刺穿问题。

基于包围球的碰撞检测算法将物体包围到最小的球体中。包围球的球心可以用物体顶点中的最大值和最小值的平均值来确定。包围球之间的相交测试也相对容易,对于两个包围球,如果两球心的距离小于半径之和,则两包围球相交。所以包围球的相交测试仅需要一次比较即可得出判断结论。文献[10]提出一种融合R-Sphere包围球的变形体碰撞检测算法,该算法将有公共顶点的三角片构造成包围球,首先利用包围球快速剔除不相交的物体,之后利用粒子群算法将3维问题转换成2维问题。

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}}$中所有方向对上的投影区间都重叠,则认为它们是相交的。

空间分割法是一种在一定程度内可以提高碰撞检测效率的方法,它将整个虚拟空间分割成等体积的规则单元格,以此将场景中的物体分割成更小的群组,并只对占据了同一单元格或相邻单元格的几何对象进行相交测试。目前优秀的空间分割方法是BSP(二叉空间分割)树,这种方式使用超平面将空间划分为两个部分,作为空间树的两个节点,并使用超平面将节点空间分割。移动物体可以利用这棵空间树检测自身的某一部分和另外的物体是否位于超平面的同侧,然后遍历这棵树直到检测碰撞或没碰撞为止。这种算法的缺点是需要先构造空间树,且算法的精确度由树的深度决定,越深的BSP树精确度越高,同时时耗越长。空间分割法适合于物体分布均匀且稀疏的场景。对于物体较多且分布不均匀的情况,需要将单元格分割成更小的单元格,大量的单元格之间的相交测试降低了碰撞检测速度并且会占用大量的存储空间。文献[14]提出了一种基于椭球包围盒与空间分割的碰撞检测算法,椭球包围盒与空间分割的碰撞检测算法。算法首先通过均匀网格分割的方法对物体进行粗略碰撞检测,确定相邻的物体对,然后为相邻的物体构建包围盒进行精确检测。文献[15]提出了一种改进的空间分割与包围盒混合的碰撞检测算法,添加链表的方式运用于空间分割算法中,有效地改进了传统算法计算量复杂、数据庞大等众多缺点。文献[16]提出一种基于空间分解法和混合包围盒的碰撞检测算法,利用均匀剖分法确定相邻对象,在包围盒碰撞检测中,提出了一种顶层采用AABB,其他层采用OBB的混合层次包围盒结构,提高了碰撞检测的效率和实时性。

在对碰撞检测精确度有要求的情况下,传统的碰撞检测方法大都利用AABB包围盒构建AABB层次包围盒二叉树,并对AABB包围盒二叉树进行遍历来断定两物体是否碰撞。遍历过程可以被描述成任务树,任务树的子任务树之间是“或”关系,只要其中一个子任务树测试出相交,则两个物体产生碰撞。如果对整个任务树进行遍历后未出现相交现象,则断定两物体未发生碰撞。A和B代表两个物体,$\alpha $$\beta $分别是两个物体包围盒二叉树的根节点,则两物体碰撞检测任务树可如图 2所示。

图 2 对象$A$$B$碰撞检测任务树
Fig. 2 Collision detection task tree of $A$ and $B$

包围盒算法虽然计算效率尚可,但是检测准确度却不高,而基于层次包围盒二叉树的碰撞检测算法检测准确,但判断效率不高。本文将假设算法背景为机械零部件的虚拟装配系统,这意味着算法将碰撞几何精度放到第1位,将碰撞检测时耗放到第2位。本文提出一种结合AABB和空间划分的碰撞检测算法(DAASD),该算法在预检测阶段利用AABB判断两对象是否有相撞可能,在相交测试阶段利用空间分割法划分检测区域,并摒弃包围盒,将检测单位还原至三角面和点,保证了检测的准确性,减少误判情况的发生。

该算法的创新在于采用了分步式的方法,该方法可以发挥每一个步骤中算法的优势,最大程度规避独立算法的缺陷。该算法的另一创新和贡献在于提出了一种按移动方向进行空间划分的方法,结合模型移动方向和运动趋势进行空间划分可以最大程度提高同一划分空间中模型碰撞的概率,提高算法的精确度并减少运算时间。最后本算法提出了一种判断点集是否穿过三角面的快速检测方法,这为本算法第2阶段的碰撞检测提供了理论支撑。该算法不适用于螺栓与螺母式以及完美贴合式的装配阶段,以上阶段利用空间约束方式可以起到良好的效果。

2 DAASD算法设计与实现

DAASD算法从虚拟装配的实际过程出发,考虑到虚拟装配系统中,执行零部件装配大都不是并发进行的,所以只有一个零部件是可移动的。传统碰撞检测需要深度优先遍历完任务树之后才能判断当前时刻是否有相交发生。这其中包围盒二叉树的建立要经过为根节点建造包围盒,确定分裂轴、分裂点进行划分,递归直至构建出完整二叉树。检测阶段对包围盒树每一层的节点进行遍历检测。然而,在最坏情况下,即两个物体只有一个三角面相交,则包含相交三角形面片的所有包围盒均要做包围盒的相交测试,计算上存在大量冗余。如果能考虑到虚拟装配的特征,即当前只有一个零部件是可以移动的,则在设计算法的时候就可以发挥其优势,达到实时检测的准确性以及算法的高效性。

DAASD算法分为预检测阶段和相交测试阶段。在算法的预检测阶段,为场景中各个物体建立包围盒。由于是进行预检测,所以不需要精度较高的OBB包围盒和$k$-Dops包围盒。在这里选用构建快捷、便于更新、紧密性好、相交测试简单、便于快速排除不相交物体以及快速判断可能相交区域的AABB包围盒。由于AABB包围盒在确定碰撞和确定包围盒相交区域上具有较高的效率,所以选用AABB包围盒来确定两包围盒的相交区域,即可能产生碰撞的区域。在利用包围盒确定可能相交区域后,对可能相交区域进行区域划分,对每一个规划好的区域进行相交测试。利用碰撞检测的时空相关性,对时空相关的部分进行相交测试可以大大减少遍历任务树的时间消耗,在保证碰撞检测精确度的同时提升碰撞检测效率。DAASD碰撞检测流程如图 3所示。

图 3 DAASD算法流程图
Fig. 3 Algorithm flow chart of DAASD

2.1 预检测阶段

DAASD算法的预检测阶段采用构建AABB包围盒的方法来查找两物体之间的可能相交区域,沿坐标轴的包围盒AABB在碰撞检测的研究历史中使用得最久、最广。一个给定对象的AABB包围盒被定义为包含该对象且各边平行于坐标轴的最小的六面体。给定对象的AABB包围盒通过遍历对象中的所有顶点,找出顶点的$X$坐标、$Y$坐标和$Z$坐标的最大值和最小值来得到,这6个值构成包围盒的8个顶点,而AABB包围盒间的相交测试是通过比较两个AABB包围盒在3个坐标轴上的投影区间是否都重叠来进行。对象的AABB包围盒在$X$$Y$$Z$方向上的最大最小值分别确定了它在3个坐标轴上的投影区间,因此AABB包围盒间的相交测试最多只需要6次比较运算。这将大大减少预检测阶段的计算量。

遍历模型中的每一个顶点,利用$X_\min$$X_\max$$Y_\min$$Y_\max$$Z_\min$$Z_\max$来构造AABB包围盒。利用判断包围盒向各轴的投影是否有重叠来判断包围盒是否相交。如果判断相交,则对场景中相交对象的AABB包围盒的轴向坐标求交集,构成待检测区域 ${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}}$, 待检测区域${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}}$图 4虚线构成六面体所示。

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

图 4 AABB构造的待检测区域
Fig. 4 The area to be detected generated by AABB

式中,A和B分别代表两相交物体包围盒, $\mathit{\boldsymbol{p}}$${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}}$区域中的点,$\mathit{\boldsymbol{U}}_x$为A、B两包围盒在$X$轴上投影的交集,$\mathit{\boldsymbol{U}}_y$为A、B两包围盒在$Y$轴上投影的交集,$\mathit{\boldsymbol{U}}_z$为A、B两包围盒在$Z$轴上投影的交集。

$ \begin{array}{*{20}{c}} {\left\{ {\mathit{\boldsymbol{p}}\left| {\mathit{\boldsymbol{p}}.x \in {\mathit{\boldsymbol{U}}_x},\mathit{\boldsymbol{p}}.y \in {\mathit{\boldsymbol{U}}_y},} \right.} \right.}\\ {\left. {\mathit{\boldsymbol{p}}.z \in {\mathit{\boldsymbol{U}}_z},\mathit{\boldsymbol{p}} \in {\mathit{\boldsymbol{U}}_{\rm{A}}}} \right\} = \emptyset } \end{array} $ (5)

$ \begin{array}{*{20}{c}} {\left\{ {\mathit{\boldsymbol{p}}\left| {\mathit{\boldsymbol{p}}.x \in {\mathit{\boldsymbol{U}}_x},\mathit{\boldsymbol{p}}.y \in {\mathit{\boldsymbol{U}}_y},} \right.} \right.}\\ {\left. {\mathit{\boldsymbol{p}}.z \in {\mathit{\boldsymbol{U}}_z},\mathit{\boldsymbol{p}} \in {\mathit{\boldsymbol{U}}_{\rm{B}}}} \right\} = \emptyset } \end{array} $ (6)

$ \mathit{\boldsymbol{P}} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} k\mathit{\boldsymbol{\alpha }}\\ k\mathit{\boldsymbol{\beta }}\\ k\mathit{\boldsymbol{y}} \end{array}&\begin{array}{l} x < y,z\\ y < x,z\\ z < x,y \end{array} \end{array}} \right. $ (7)

式中,$k$为系数,$P$为平面的法向量,$\mathit{\boldsymbol{\alpha }}$为与坐标轴$X$轴同方向的法向量,$\mathit{\boldsymbol{\beta }}$为与坐标轴$Y$轴同方向的法向量,$\mathit{\boldsymbol{\gamma }}$为与坐标轴$Z$轴同方向的法向量。

如果式(5)或者式(6)成立,则表明当前两对象中至少有一个对象在区域${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}}$中不存在点,即不可能产生碰撞,否则对区域${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}}$进行区域划分。对所划分的区域${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}}$,要结合物体的移动方向来进行相交测试。任取区域${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}}$中一点,以其移动所形成直线构成的平面来分割区域${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}}$可在减少检测次数的情况下提高有效检测次数。为减少计算复杂度,可选用$X$$Y$$Z$轴正方向作为分割平面的法向量。在选择3个轴方向上,参考物体的移动方向。任取区域${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}}$中一点,利用其移动前后两位置所形成的线段投影到$X$$Y$$Z$ 3个坐标轴上,选取投影最短的轴,则以该坐标轴为法向量确定分割平面。根据分割平面将区域${\mathit{\boldsymbol{\varphi }}_{{\rm{AB}}}}$分割成$K$个子集合,并对$K$个子集内的三角面做相交测试。其中,$K$的大小可以根据模型的移动精度和复杂度适当调节。$K$过大或过小都会影响算法的整体效率。

图 5为对待检测区域的空间划分示意图,其是在$XY$平面中的划分。两点所形成的直线向$Y$轴映射的投影要小于向$X$轴映射的投影,所以选择与$Y$轴同向的法向量作为分割平面的法向量,即图中虚线表示分割平面。

图 5 空间划分示意图
Fig. 5 Space partition

2.2 相交检测阶段

DAASD算法的相交测试在区域划分后的各个子区域中进行。在不规则物体的碰撞检测中,不规则物体表面可以被认为是多个极小的点构成,所以在数学模型中可以将移动的极小的点定义为点向量,记为$\mathit{\boldsymbol{Q}}$。在虚拟装配中,将当前不需要装配的不规则物体看作由无数个三角面包围而成。在碰撞检测中,就可以通过代表运动中的不规则物体的点集以及代表当前无需装配不规则物体的三角面来判定两物体是否有碰撞关系。为了减少计算次数,提高计算效率,在这里将引入三角期望的概念。在概率论和统计学中,一个离散性随机变量的期望值(或数学期望,或均值,亦简称期望)是实验中每次可能结果的概率乘以其结果的总和。期望值是随机实验在相同条件下重复多次的结果计算出的等同“期望”的平均值,期望值也是该变量输出值的平均数。期望值并不一定包含于变量的输出值集合内。在三角期望的概念中,即是把三角形3个顶点看做3个离散变量,利用离散变量获取期望值,看做是三角面可能出现的位置。而3点出现的概率相等,即1/3。$E(x)$$E(y)$$E(z)$可以近似地看做是三角面的坐标从而将三角面点化,简化计算复杂度。$E(x)$$E(y)$$E(z)$的计算方法为

$ \left\{ \begin{array}{l} E\left( x \right) = \left( {{x_1} + {x_2} + {x_3}} \right)/3\\ E\left( y \right) = \left( {{y_1} + {y_2} + {y_3}} \right)/3\\ E\left( z \right) = \left( {{z_1} + {z_2} + {z_3}} \right)/3 \end{array} \right. $ (8)

式中,$x_1$$y_1$$z_1$为三角面一个顶点的3个坐标,$x_2$$y_2$$z_2$$x_3$$y_3$$z_3$为三角面另外两个顶点的坐标。

在碰撞检测中,检测碰撞的发生就是要看点集是否穿过三角面,穿过三角面就会被判定为发生碰撞。判断是否产生碰撞需要两个位置,一个是不规则物体移动之前的位置,另一个是移动之后的位置。判断点是否穿过三角面首先要判断点移动前后位置是否分布在三角面所在平面的两侧。判断点在两时刻位置是否在三角面两侧的方法为

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

式中,$\mathit{\boldsymbol{a}}$$\mathit{\boldsymbol{b}}$$\mathit{\boldsymbol{c}}$分别为三角面的3个顶点坐标,$\mathit{\boldsymbol{V}}_1$$\mathit{\boldsymbol{V}}_2$分别是三角面的两条边向量,式(11)中$n$是将方向向量单位化处理。$D$表示顶点$\mathit{\boldsymbol{a}}$在平面法向量$\mathit{\boldsymbol{N}}$上的投影,即三角面所在平面距离原点的距离;$\mathit{\boldsymbol{Q}}_1$$\mathit{\boldsymbol{Q}}_2$分别代表点在移动前和移动后的位置坐标,$D_{q1}$$D_{q2}$分别代表$\mathit{\boldsymbol{Q}}_1$$\mathit{\boldsymbol{Q}}_2$$\mathit{\boldsymbol{a}}$$\mathit{\boldsymbol{b}}$$\mathit{\boldsymbol{c}}$平面法向量$\mathit{\boldsymbol{N}}$上的投影长度。$D_1$$D_2$分别为移动前和移动后两点到原点的距离与平面到原点距离的差值。

在计算出$D_{q1}$$D_{q2}$$D$3个距离之后就可以判断这个点在前一时刻和现在时刻是否分布在三角面所在平面两侧,如果分布在平面的同侧,那么可以判断为点的运动不会与这个三角面发生碰撞。如果$D_1$$D_2$同号则说明移动前和移动后两点在三角面所在平面同侧,否则说明两点分布在平面两侧,可能发生碰撞。

在判断点的移动有可能穿过三角面后,通过判断移动前和移动后两点所形成的空间线段和三角面交点来确定是否发生了碰撞。计算线段与有限平面交点的方法有很多,可以较少消耗计算机内存并且效率较高的求交点的方法为

$ \left\{ \begin{array}{l} x = {D_{q1}} \cdot x + {D_{q2}} \cdot x \times t\\ y = {D_{q1}} \cdot y + {D_{q2}} \cdot y \times t\\ z = {D_{q1}} \cdot z + {D_{q2}} \cdot z \times t \end{array} \right. $ (17)

式(17)为直线的参数方程,表示直线为空间中穿过$D_{q1}$$D_{q2}$两点的直线。空间平面的点法式方程为

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

式中,$\mathit{\boldsymbol{N}}$为三角平面所在平面的法向量,$a$为三角平面上的一个顶点。通过式(17) (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)

求得$t$的值带入式(17)即可得出移动前和移动后两点所在直线和三角面所在平面交点的$x$$y$$z$,再判断所求交点是否落在三角面上,如果落在三角面上则判断发生碰撞,否则判断未发生碰撞。

2.3 模型更新

在虚拟环境中,由于模型是动态运动的,所以要对虚拟环境中动态的模型进行实时地更新。由本小节前部分可知,虚拟环境中的模型可以看做一个点集,这个点集分布在模型的表面,所以在虚拟空间中,对动态模型的状态和位置不断地更新也就是对点集状态和位置不断地更新。对于点集的更新有两种形式,一种是平移更新,另一种是旋转更新,其中旋转更新分为绕坐标轴的旋转和绕任意轴的旋转。

在虚拟环境中,3维空间坐标变换可以采用齐次坐标技术来描述空间的各点坐标及其变换。设虚拟环境中模型的某个顶点为$\mathit{\boldsymbol{P}}$,这个模型的顶点在平移后为$\mathit{\boldsymbol{P}}'$,模型在虚拟环境中的空间平移变量为$\mathit{\boldsymbol{t}}({t_x}, {t_y}, {t_z})$,即虚拟空间中模型向$X$轴向平移$t_x$,向$Y$轴向平移$t_y$,向$Z$轴向平移$t_z$。则利用齐次坐标技术来描述空间平移,即

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

由于装配的虚拟空间为3维空间,所以在虚拟空间中的旋转变换要比2维下的旋转变换复杂,除了需要知道旋转的角度之外,还需要知道旋转轴。如果将虚拟空间中坐标系的3个坐标轴依次当作旋转轴,则可以较容易地完成旋转的变换。对于绕$X$轴、$Y$轴、$Z$轴的旋转,旋转角度分别为$\alpha $$\beta $$\gamma $,则可以利用本文第二章中所提到的相关原理进行坐标变换,式(21)—式(23)分别为对应绕$X$轴、$Y$轴和$Z$轴的旋转变换矩阵

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

在旋转的过程中可以默认变换的顺序分别为绕$X$轴旋转、绕$Y$轴旋转和绕$Z$轴旋转,则可以将绕$X$轴旋转、绕$Y$轴旋转和绕$Z$轴旋转的变换矩阵进行整合。

3 实验结果与分析

本文实验采用OGRE引擎、C++语言,对DAASD算法、AABB层次包围盒算法以及$k$(16)-DOPs分别进行实验,并对实验结果进行对比和分析,最后给出结论。为了验证本算法的有效性,本文对DAASD算法、AABB层次包围盒算法、$k$-Dops以及BPS空间分割树进行时间复杂度对比,利用OGRE引擎建立了5个典型的实验环境且进行了仿真实验,并对仿真结果进行分析。实验中模型选为两个大三角面数的水壶模型,该模型具备平面、曲面、环形等,可以较好地验证算法的优劣。5个实验环境分别针对算法碰撞几何精度、算法平移自由度下碰撞检测时耗、算法旋转自由度下碰撞检测时耗、三角面数对算法碰撞检测时耗影响等方面搭建,并计算实验结果,针对实验结果进行分析和对比并得出结论。

本文实验均是在OGRE环境下完成的,OGRE引擎是一个成熟稳定、渲染效果好、跨平台,而且拥有丰富功能的实时3D图形库,同时OGRE引擎具有的开源性和高度可扩展性也给本文实验带来了巨大的便利,它对原本图形库进行了封装,这样很多底层的技术就不必去详究,从而把更多的精力放到碰撞检测上。OGRE环境作为一种C++的开源资源包,提供了一定的渲染技术,作为实验环境可以较直观地感受装配工程。C++的内核以及较低层次的封装也可以较大程度地展示算法本身的优点以及缺点。环境初始化为无重力场景。

3.1 复杂度分析

对于DAASD算法,假设场景中模型个数为$M$, 模型中三角面数为$N$,空间划分度为$K$,则对于每次碰撞检测所需的时间复杂度为${\rm{O}}\left( {\frac{{M!}}{2} \times \frac{N}{K} \times \frac{N}{K}} \right)$

对于AABB层次包围盒二叉树算法,根据场景中对两对象的碰撞检测任务树的遍历可以得出其计算时间复杂度。设碰撞检测树的个数为$M$,碰撞检测树叶子节点数为$X$,则进行一次碰撞检测平均时间复杂度为 ${\rm{O}}\left( {\frac{{M!}}{2} \times \frac{{X \times {{\log }_4}\left( {{X^2}} \right) + 1}}{2}} \right)$。如果模型三角面数设为$N$,根据碰撞检测任务树性质,可以得出$X=N^2$,最终可以得出AABB层次包围盒二叉树算法复杂度为${\rm{O}}\left( {\frac{{M!}}{2} \times \frac{{{N^2} \times 2 \times 2 \times {{\log }_4}\left( N \right) + 1}}{2}} \right) $

3.2 碰撞几何精度测试

在虚拟环境中,初始化一个无重力的场景,并在场景中放置两个壶模型,两模型三角面数均为517个随机选取6个位置,对这6个位置进行碰撞检测,在同一位置利用DAASD算法分别与AABB层次包围盒算法、$k$(16)-Dops以及BPS空间分割树算法进行碰撞检测,并记录3种经典算法与DAASD算法碰撞检测时检测出碰撞所在位置的距离差。图 6为随机选的6个位置,并且这6个位置未按检测的难易程度进行排序。

图 6 测试准确性用例位置
Fig. 6 Accuracy test cases

图 7为4种算法在图 6中6个位置中发生碰撞时位置的距离差。这6次实验在同一实验环境、同一计量单位、相同位置下,利用DAASD算法进行碰撞检测时两模型的贴合度都要高于利用AABB层次包围盒二叉树算法进行的碰撞检测。这6次实验中,两算法在同一位置的距离差分别为0.11、0.03、0.04、0.01、0.049和0.03。当距离差超过0.02时,会有较明显的视觉缝隙。在6次实验中,有5次实验数据超过阈值0.02,并且有一个位置的距离差达到0.11,在此位置两算法会有特别明显的视觉差别,这说明DAASD算法在碰撞的几何精度上较AABB层次包围盒二叉树有较明显的提高。

图 7 4种算法的几何精确度差值
Fig. 7 Difference of the accuracy of the four algorithms

另外一组实验是在虚拟装配或游戏领域比较常用的算法$k$-Dops包围盒与DAASD算法两者之间进行,$k$取值为16。同样测试的为两算法同一位置最近距离的距离差,距离差分别为:0.22、0.50、0.73、0.69、0.04、1.24。在6次实验中,只有一次距离差接近阈值0.02。且距离差较大,这说明DAASD算法在碰撞检测的几何精度上远远高于这种单包围盒中最精确的$k$(16)-Dops包围盒算法。

接下来的一组实验是在BPS空间分割树算法中选取适当深度的划分方式与DAASD算法进行比较,当前选择深度为16。同样测试的是在同一位置最近距离的距离差,差距分别为:-0.19、-0.35、-0.45、-0.57、-0.39、-0.91,由于BPS算法与包围盒算法不同,包围盒特征为包围覆盖,所以包围盒检测相交的时候实际物体不一定相交,所以当检测碰撞时,物体间会有一定缝隙。BPS算法为空间分割法,当两物体相交但相交区域没有超平面分割,这时即使物体相交也不会检测碰撞,所以包围盒算法的数据与BPS空间分割算法数据会存在正负之分。

3.3 碰撞检测时耗测试

在虚拟环境中,初始化一个无重力的场景,并在场景中放置3个茶壶模型,3个模型三角面数均为517个。在场景中选取12个位置,两种算法在检测到碰撞之前都可以达到这12个位置。把这12个位置分成两组,并按碰撞检测的难易从易到难排列,分别利用DAASD算法和AABB层次包围盒二叉树算法进行测试。其中6个位置用于测试平移自由度下两算法时效,另外6个位置用于测试旋转自由度下两算法时效。两组位置分别用于同一个场景、两个实验环境下。

测试平移自由度所使用6个位置如图 8所示,这6个位置按对模型使用AABB层次包围盒二叉树碰撞检测算法进行碰撞检测时的难易程度进行排序。处于1号位置的碰撞检测为较容易的碰撞检测,处于6号位置的碰撞检测为相对较难的碰撞检测。其他位置碰撞检测难易程度介于1号位置和6号位置之间,并呈现递增的趋势。图 9为4种算法在平移自由度下的时间消耗。

图 8 平移自由度下时耗用例位置
Fig. 8 Collision detection when the translational degree of freedom is allowed
图 9 平移自由度下的时间消耗
Fig. 9 Time consumption of translational degree of freedom

图 9所绘制出的曲线结果可以看出,在碰撞检测较为简单的1号和2号位置,AABB层次包围盒二叉树碰撞检测算法的时耗较低,但是两算法的时耗没有产生较明显差异。随着碰撞检测难度的不断增加,DAASD算法的算法效率逐渐彰显。这一实验结果证明在平移自由度下,DAASD算法的检测时效比AABB层次包围盒二叉树算法的检测时效更为优越。而$k$-Dops算法由于是单包围盒检测,所以在平移自由度环境下并不耗时。BSP由于空间树的深度没有特别深,仅为16层,所以时效上优于AABB层次包围盒算法。

测试旋转自由度所使用6个位置如图 10所示,这6个位置按对模型使用AABB层次包围盒二叉树碰撞检测算法进行碰撞检测的难易程度进行排序。处于1号位置的碰撞检测为较易的碰撞检测,处于6号位置的碰撞检测为相对较难的碰撞检测。其他位置碰撞检测难易程度介于1号位置和6号位置之间,并呈现递增的趋势。图 11为在旋转自由度下DAASD算法、AABB层次包围盒算法、$k$(16)-Dops算法以及BSP算法,在6个位置进行一次检测所需的平均时耗。

图 10 旋转自由度下时耗用例位置
Fig. 10 Collision detection when the rotational degree of freedom is allowed
图 11 旋转自由度下的时间消耗
Fig. 11 Time consumption of rotational degree of freedom

图 11所绘制出的曲线结果可以看出,在碰撞检测较为简单的1号、2号和3号位置,虽然AABB层次包围盒二叉树算法时耗较高,但是这两种算法之间没有较为明显的时耗差异。随着碰撞检测难度的不断增加,DAASD算法的算法效率逐渐彰显,并且在同一位置的计算时耗上产生了较大的差异。这一实验结果证明在旋转自由度下,DAASD算法的效率比基于AABB层次包围盒二叉树算法的效率更高,且DAASD算法的优越性随着碰撞检测难度的增加表现的愈为显著。而$k$(16)-Dops算法,在旋转自由度下的碰撞检测时耗则好于AABB层次包围盒算法和DAASD算法,但是较平移自由度下的时耗较差。BSP算法由于空间划分为16层,所以时效上会优于AABB层次包围盒算法。

从以上两个实验中可以看出在简单的位置AABB层次包围盒的计算效率与DAASD算法的计算效率基本持平,随着碰撞检测复杂程度的递增,DAASD算法的优势逐渐凸显。在旋转自由度下,随着计算复杂度的增加,效率差距会呈现较为显著的差异,这一实验结果验证了DAASD算法在计算复杂模型碰撞检测的过程中,有着更为优越的表现。$k$-Dops由于是单包围盒算法,所以在计算时效上有着较强的优势。

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

在虚拟环境中,初始化一个无重力的场景,在场景中分别放置两个模型。第1组实验中,设定面数为530的茶壶模型为移动对象,设定不同面数的模型为静止对象,不同面数模型经过3DMax建模软件降面,确保模型外形一致。利用坐标定位方法确保每次碰撞检测位置相同,得出当前位置下每一次碰撞检测所需要的时间。第1组实验结果如表 1所示。第2组实验中,设定面数为530的茶壶模型为静止对象,设定不同面数的模型为运动对象,利用坐标定位方法确保每次碰撞检测的位置相同,得出当前位置下每一次碰撞检测所需要的时间。第2组实验结果如表 2所示。由于$k$(16)-Dops算法为单包围盒算法,所以三角面数对该算法无本质上的影响,本小节不再赘述该算法的实验。

表 1 运动模型为少面数情况下的时间消耗
Table 1 Time consumption of less faces motion model

下载CSV
静止对象的三角面数 移动对象的三角面数 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

表 2 运动模型为多面数情况下的时间消耗
Table 2 Time consumption of more faces motion model

下载CSV
静止对象的三角面数 移动对象的三角面数 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中可以看出,在相同位置发生碰撞检测后,DAASD算法计算时耗小于基于AABB层次包围盒二叉树碰撞检测算法,但差距不大。并且随着静止模型面数的不断增加,单次平均检测时耗在两种碰撞检测算法的计算下都呈上升的趋势。BSP算法在当前深度的情况下,平均时耗小于AABB层次包围盒,但高于DAASD算法。

表 2中可以看出,在相同位置发生碰撞检测后,DAASD算法计算的时耗少于AABB层次包围盒二叉树算法,且差距较大。并且随着模型面数的不断增加,单次平均检测时耗在两种碰撞检测算法的计算下都呈上升的趋势,且随着模型面数的不断增加,利用两种算法计算碰撞的单次平均时耗的差距也越来越大。BSP算法与DAASD算法特征一致,对于面数较多的移动物体表现比较稳定。

结合表 1表 2可以看出, 当移动模型的面数较大时,对基于AABB层次包围盒二叉树算法的时耗影响较大,而对DAASD算法与BSP空间分割算法的时耗影响较小。这个实验可以证明,当运动模型的三角面数较大时,DAASD算法与BSP空间分割算法会比AABB层次包围盒二叉树碰撞检测算法表现出更高的稳定性。

4 结论

目前,相关的碰撞检测算法已经比较丰富,但是随着虚拟现实技术的发展,工业应用上对碰撞检测要求也越来越高。国内外学者对虚拟现实技术方面的碰撞检测算法研究比较多,但是真正能让虚拟装配技术应用到工业上的碰撞检测算法却较少。本文对传统碰撞检测算法进行了论述,并提出一个结合AABB和空间划分的碰撞检测算法(DAASD)。算法通过结合传统的包围盒碰撞检测算法和空间划分法,并将检测从包围盒还原成三角面和点的碰撞检测,在减少了碰撞检测所需时间的同时也提高了碰撞检测的准确性。该算法可以满足虚拟装配技术中对碰撞检测算法准确性的需求,同时在计算时间上也满足使用者的交互习惯。该算法适用于虚拟装配领域中的展示和教学。对于高精度类虚拟装配应用,此算法应与空间约束等限制自由度的但可精确装配的算法搭配应用。

参考文献

  • [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]