基于包围盒和二叉树的游戏虚拟场景碰撞检测方法

A Collision Detection Method for Game Virtual Scenes based on Bounding Boxes and Binary Trees

常规游戏虚拟场景碰撞检测方法由于缺乏对包围盒的简化处理,导致碰撞检测效率较低。对此,提出基于包围盒和二叉树的游戏虚拟场景碰撞检测方法。首先,通过对协方差矩阵进行求解,对包围盒的方向进行判定,在此基础上根据原始虚拟物体的几何边缘构建出轴向包围盒。并采用二叉树原理,对轴向包围盒存储结构进行简化,从而减少待测节点的数量。最后通过计算随机包围盒的中心点距离,对包围盒的相交情况进行判定,从而实现碰撞检测。测试结果表明,采用提出的方法对游戏虚拟场景中的物体进行碰撞检测时,该算法的平均碰撞检测时间始终低于0.8 ms,具有较高的检测效率。

Currently,conventional collision detection methods for game virtual scenes mainly construct the bounding boxes with different topologies based on the external contour features of 3D objects,and detect the collision situation of 3D objects through the intersection test of bounding boxes.However,due to the lack of simplified processing of bounding boxes,the collision detection efficiency is low.In this regard,a collision detection method for game virtual scenes based on bounding boxes and binary trees was proposed in this paper.Firstly,the direction of the bounding boxes was determined by solving the covariance matrix,and the axial bounding boxes were constructed based on the geometric edges of the original virtual object.Secondly,the binary trees principle was used to simplify the storage structure of the axial bounding boxes,so as to reduce the number of nodes to be tested.Finally,by calculating the distance between the center points of the random bounding boxes,the intersection of the bounding boxes was determined,thereby achieving collision detection.The test results show that the average collision detection time of the proposed algorithm is always lower than 0.8 ms when using the proposed method to detect objects in the virtual scene of the game,which has a high detection efficiency.