USSCD:A Fast Collision Detection Algorithm Based on Uniform Spatial Subdivision
USSCD：一个基于均匀空间分割的快速碰撞检测算法

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.