一种基于可能碰撞集的碰撞检测方法

为了提高虚拟环境中碰撞检测的实时性和有效性,提出了一种基于可能碰撞集的碰撞检测方法.该方法首先通过预测环境中刚体在当前帧和下一帧之间的可能运动轨迹来构建一个各边与世界坐标系各坐标轴平行,且包围该运动轨迹的包围盒;然后利用空间平铺技术来快速检测与某一平铺单元同时相交的轨迹包围盒,即可得到当前帧的可能碰撞集;接着对可能碰撞集中的刚体对进行最早碰撞时间tmin的求解,并根据tmin进行排序;最后只对具有最小tmin值的刚体对进行碰撞检测.仿真试验结果表明,与目前已有的碰撞检测算法相比,该方法简单、快速,不仅可以有效解决多个刚体环境中碰撞发生的次序问题,同时,该方法还能保证碰撞检测的完整性和唯一性.另外,理论和实践也证明了该方法的正确性和有效性.

A Collision Detection Method Based on Possible Collision Set

A simple, fast collision detection method is presented, which is based on possible collision set (PCS). The algorithm comprises two main parts: the construction of the possible collision set and the computation of the soonest possible time of collision. First a track bounding box, whose edges are parallel to the global coordinate axes is computed for each rigid body in the environment. Then a spatial tiling technique is employed to obtain a possible collision set P of current frame by searching which bounding boxes overlap. After that, a soonest possible time of collision tmin is estimated for every pair of rigid bodies in the P based on Lin-Canny closest features algorithm. Thus the collision check will only be applied to the element that has the minimum value of tmin. Compared with other methods, this one can reduce times of collision check dramatically in collision intensive environment and real time or near real time collision detection can be achieved easily. In addition, the PCS method assures integrality and uniqueness of collision detection in the environment. Some simulation tests are also designed ?based on the method. The correctness and effectiveness are proved in both theory and practice.