USSCD：一个基于均匀空间分割的快速碰撞检测算法

对于存在大量运动物体的虚拟环境，碰撞检测往往成为影响系统计算效率的瓶颈，为提高多体碰撞检测的效率，提出了一个基于均匀空间分割的快速多体碰撞检测算法——USSCD，该算法首先将物体空间均匀分割成一系列单元格，然后在每个单元格，通过基于AVL排序的扫描排除法进行碰撞检测，同时依据物体的分布密度，提出了一个计算单元格尺寸的优化方法，通过一系列实验，测试了USSCD算法的性能，并与I-COLLIDE算法进行比较，实验结果表明，在均匀分布条件下，当物体数量较大时，USSCD的效率高于I-COLLIDE算法，而且，USSCD算法的效率基本不受物体运动相关性的影响。

USSCD:A Fast Collision Detection Algorithm Based on Uniform Spatial Subdivision

In complex virtual environment, where there are massive moving objects, collision detection would become the bottle-neck of system performance. To promote the computation efficiency in such case, a fast N-body collision detection algorithm, USSCD, is proposed, which is based on uniform spatial subdivision. In this algorithm, the computation complexity is reduced with a hybrid scheme, first, the object space is uniformly subdivided into a series of voxels; then, collision detection, based on the scheme of sorting-based sweep and prune, is performed within each voxel. Based on distribution density of objects, an optimal method is proposed to compute the size of voxels in uniform space subdivision, for a special class of collision detection algorithms, this method can lead to minimum computation complexity. USSCD was implemented, and compared with I-COLLIDE through a serial of tests. The results show that USSCD is superior in performance when massive objects are uniformly distributed. Moreover, the performance of USSCD is more stable than that of I-COLLIDE in consideration of variable correlation between objects.