基于混合层次包围盒的快速碰撞检测算法

Fast Collision Detection Algorithm Based on Hybrid Hierarchical Bounding Box

针对复杂虚拟场景,提出一种基于混合层次包围盒的快速碰撞检测算法。考虑到包围盒构造的低效性问题,提取物体凸体来近似代替物体模型,减少了参与包围盒计算的顶点数量,可以在保持包围盒紧密性的同时,降低包围盒构造时间。设计了一种新的Sphere-AABB-OBB混合层次包围盒结构,可先利用外层Sphere包围盒和AABB包围盒快速排除不相交的模型,再对内层OBB包围盒进行相交检测,从而提高相交检测效率。实验表明,在复杂虚拟场景下,上述算法显著减少了包围盒构造时间和包围盒相交检测时间,有效提高了虚拟场景碰撞检测的效率。

For complex virtual scenes,a fast collision detection algorithm based on hybrid hierarchicalbounding box is proposed in this paper.Firstly,considering the low efficiency of bounding box construction,the object convex body was extracted to approximately replace the object model,which reduced the number of vertices involved in bounding box calculation and the bounding box construction time while maintaining the tightness of the bounding box.Secondly,this paper designd a new Sphere-AABB-OBB hybrid hierarchicalbounding box structure,which can quickly eliminate the disjoint model by using the outer sphere bounding box and AABB bounding box,and then detect the intersection of the inner OBB bounding box,so as to improve the efficiency of intersection detection.Experiments show that in complex virtual scenes,the proposed algorithm significantly reduces the bounding box construction time and bounding box intersection detection time,and effectively improves the efficiency of collision detection in virtual scenes.