基于混合包围盒与三角形相交的碰撞检测优化算法  

Optimized collision detection algorithm based on hybrid bounding box and intersection of triangles

作　　者：孙敬荣 卢新明[1,2] SUN Jingrong;LU Xinming(Shandong University of Science and Technology,Qingdao,Shandong 266590,China;Shandong Key Laboratory of Wisdom Mine information technology,SDUST,Qingdao,Shandong 266590,China)

机构地区：[1]山东科技大学,山东青岛266590 [2]山东科技大学山东省智慧矿山信息技术省级重点实验室,山东青岛266590

出　　处：《计算机工程与应用》2018年第19期198-203,共6页Computer Engineering and Applications

基　　金：国家重点研发计划(No.2017YFC0804406);山东省重点研发计划(No.2016ZDJS02A05)

摘　　要：碰撞检测的速度与准确性是众多计算机应用程序的关键难题之一。为了提高检测速度同时兼顾准确性,将检测分为两个阶段:预处理检测阶段首先均匀剖分待测空间以确定相邻对象,然后对相邻的对象构造AABB-OBB混合层次包围盒,改进包围盒的构造方式,同时改善任务结构加速遍历过程;详细检测阶段在M?ller算法基础上加以改进,构造新的计算坐标系,对空间几何三角形进行投影降维,在二维平面上解决空间问题,从而减少算法总的计算量。实验结果表明,在保证碰撞检测准确性的前提下其检测速度大幅提高。In the problem of collision detection,the speed and accuracy is one of the key challenges for many computer application programs.A new detection algorithm is proposed that can improve the detection speed and the accuracy,it is based on two phases:Firstly,in the preprocessing detection stage,uniformly dissect the space which is measured to determine the adjacent objects and constructs the AABB-OBB mixed hybrid bounding box.The structure of the bounding box and the task structure are optimized which accelerate the ergodic process;then,in detailed test phase,a new calculation of coordinate system based on M?ller algorithm is improved.The space geometric triangle is projected and reduced aiming at the space problems in two-dimensional plane,so that the total calculation of the algorithm is reduced.Compared with the traditional algorithm,the experimental results show that the detection speed of the new algorithm is greatly improved under the premise of ensuring the accuracy of collision detection.

关 键 词：碰撞检测 混合包围盒 任务结构 三角形相交 坐标系变换 降维 

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