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

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