结合轴对齐包围盒和空间划分的碰撞检测算法  

Collision detection algorithm based on AABB bounding box and space division

作　　者：于瑞云[1] 赵金龙 余龙 张倩妮 Yu Ruiyun;Zhao Jinlong;Yu Long;Zhang Qianni(Department of Software,Northeastern University,Shenyang 110819,China)

机构地区：[1]东北大学软件学院,沈阳110819

出　　处：《中国图象图形学报》2018年第12期1925-1937,共13页Journal of Image and Graphics

基　　金：国家自然科学基金项目(61672148;61502092);教育部-中国移动科研基金项目(MCM20160201);辽宁省百千万人才工程基金项目(201514)~~

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]