Abstract: To promote the low computation efficiency of multi-object collision detection in complex virtual environment, a new collision detection algorithm is proposed in this paper, which is based on the combination of space decomposition and ellipsoid Bounding Box. The algorithm firstly uses space segmentation approach to identify the neighbouring objects, secondly simulates the neighbouring objects by using ellipsoid-trees, and finally detects the contact status of objects in parallel by using multi-task parallel processing technology based on the thread pool. To reduce the complexity of intersection tests between ellipsoids, The algorithm firstly forecasts the contact status of ellipsoids, and then transforms the test between the three-dimensional ellipsoids to the test between the two between the two-dimensional ellipses, it improves the efficiency of the algorithm. Experimental results show that the algorithm is more efficient than other algorithms.

Key words: ellipsoid Bounding Box, space decomposition, collision detection, parallel algorithm, hierarchical bounding box, task tree

摘要： 为提高复杂环境下多物体碰撞检测的效率，提出了一种基于均匀网格分割与椭球包围盒的并行碰撞检测算法。该算法首先用均匀网格分割法来确定相邻物体，然后用紧密性较好的椭球包围盒层次树依次把它们包围，并利用基于线程池的多任务并行处理技术实现了并行化。为降低椭球相交测试的复杂度，先预测了椭球间的相交情况，再将三维椭球降维成二维椭圆，从而整体提高了算法的效率。通过实验数据表明，相对于其他算法，该算法具有较好的性能。

关键词: 椭球包围盒, 空间分割, 碰撞检测, 并行算法, 层次包围盒, 任务树