一种快速混合碰撞检测算法研究

Fast Hybrid Collision Detection Algorithm

为提高虚拟环境的临境感和真实感,对其中的关键技术碰撞检测进行研究,提出了一种快速碰撞检测算法。复合层次包围盒碰撞检测能发挥不同类型包围盒碰撞检测的优势进行检测,但不能充分利用当前图形硬件的快速并行计算的优势;基于流的碰撞检测算法可充分发挥后者的优势,但会造成许多冗余检测。提出的新算法将复合层次包围盒碰撞检测算法与基于流的碰撞检测算法相结合:在预处理阶段构造复合层次包围盒树,然后利用复合层次包围盒碰撞检测算法进行初步检测快速排除不可能相交的物体对,接着利用基于流的碰撞检测算法对得到的碰撞子集进行精确求交,得到碰撞检测的结果。实验通过与RAPID和原始的基于流的碰撞检测算法进行比较,证明该算法能有效进行实时碰撞检测。

In order to improve the on-sport sensation and realism in virtual environment,a fast collision detection algorithm is proposed.Collision detection by using hybrid bounding boxes could take advantage of various bounding boxes,the parallel computing capability of current graphics hardware,however,is not considered.The stream-based collision detection algorithm could take advantage of the latter,but would cause a number of redundant detection.The proposed algorithm combines the hybrid hierarchical bounding volume algorithm and the stream-based real-time collision detection algorithm.In the preliminary period,the hybrid hierarchical bounding volume is established.The intersection test uses the hierarchical bounding volume to eliminate the possibility of collision between objects far apart;then it accurately determines the contact status among objects in closer proximity by stream-based collision detection algorithm.Experiment indicates that the algorithm is more efficient than RAPID and the original stream-based collision detection algorithm in complex virtual environment.