适用于复杂场景的碰撞检测算法研究

创建虚拟场景不仅要进行静态建模，更重要的是进行动态建模。而且物体之间的实时碰撞检测是关键。首先对常用检测算法的检测效率进行了分析和比较。然后重点针对复杂虚拟场景中吉有大量物体的特点，提出了混合包围盒碰撞检测算法。该算法利用帧与帧之间的时间和几何相关性，把对（cn^2＋m）个对象的动态跟踪转化为它们在三个坐标轴上的投影的排序问题，把时间复杂度由O（n^2）降低为O（n）。并引入树的深度的概念，根据不同的应用场合合理控制检测深度以加快检测速度。理论分析和仿真计算都表明，该算法能够满足多达几百个运动物体的实时交互碰撞检测。

A Collision Detection Algorithm for Complex Environment

Collision detection has been a fundamental problem in designing virtual reality system and a fast and interactive collision detection algorithm is a fundamental component of a large-scale virtual environment.In this paper,the authors analyze and compare the detection efficiency of usual collision detection (CD) algorithms.Then an algorithm for collision detection using hybrid bounding box is presented.This algorithm can reduce the time from O(n~2) to O(n) by the temporal and geometric coherence and quicken the detection rate by controlling the detection depth reasonably.At last,a simulation example is given to prove that the algorithm can determine all the collisions in an environment involving more than 800 moving polytopes.