面向虚拟环境漫游的快速碰撞检测算法

Fast collision detection algorithm for virtual environment walkthrough

分析了虚拟漫游中的碰撞检测失真现象,讨论了克服碰撞检测失真的方法,根据漫游碰撞检测精度要求不高的特点,提出了一种虚拟环境漫游的快速碰撞检测算法.该算法采用包围球来代替化身,先通过三次半空间剔除来建立碰撞形体集,再利用化身运动的几何连贯性将碰撞形体集分割成碰撞形体子集,最后通过实施对球与多边形的碰撞检测来计算碰撞点和可移动距离.实验表明,该算法能在基本不降低帧率的情况下对虚拟环境进行漫游,对一个由1 796个形体组成的虚拟环境,碰撞检测开关处于开和关两种状态时的帧率分别为13.268帧/s和13.340帧/s.

The distortion of collision detection in virtual environment walkthroughs was analyzed, and the methods of how this distortion is overcome were discussed. According to the character of low precision requirement in collision detection for virtual environment walkthrough, a fast collision detection algorithm for virtual environment walkthrough is presented. This algorithm substitutes a ball for avatar in collision detection and creates collision bodies set by three half-space culling. Then adopting the geometry continuity of avatar motion, it divides the bodies set into sub bodies sets. Finally, it calculates collision point and movable distance of avatar by implementing collision detection between ball and polygons. The test result show that the algorithm has very little influence on the FPS（frames per second） of virtual environment walkthrough. In a virtual environment which includes 1 796 bodies, when the switch of collision detection is on or off, the FPS is 13. 268 frame/s or 13. 340 frame/s respectively.