基于空间扫描策略的3维相交检测算法

Intersection detection algorithm for 3D objects utilizing spatial sweeping strategy

针对复杂虚拟场景中碰撞检测和空间分析等操作实时性差的问题,提出一种适用于3维空间对象间的快速相交检测算法———Space Sweep。该算法首先根据场景内空间对象分布特征,构建事件点及其列表;利用空间扫描策略,自适应地构建一系列假想的空间扫描面;在扫描面移动的过程中,将空间对象的状态分为死亡态、激活态和休眠态,通过只对当前处于激活态的空间对象进行相交测试,有效地减少了空间对象间不必要的相交计算。该算法提高了虚拟场景中3维空间对象间相交检测的效率,为3D GIS中实时空间分析提供了有力的技术支持。最后,通过对比测试验证了本文算法的实用性。

To resolve the problem that the traditional collision detection algorithm and spatial analysis operations in the virtual scene have bad real-time performance, a fast intersection detection algorithm named SpaeeSweep for threedimensional spatial objects is presented. Based on the distribution characters of spatial objects, the event points and their lists are constructed firstly. After that, by using the spatial sweeping strategy, a series of imaginary spatial sweeping planes are constructed adaptively. During the sweeping process, the state of the spatial objects is classified into death state, active state and sleeping state. Only spatial objects in the active state are used to conduct of the intersection testing. Therefore, many unnecessary intersection calculations are abstained, and the efficiency of the algorithm is improved. This algorithm improves the efficiency of intersection detection between the three-dimensional objects in the virtual scene, and provides strong technical support for real-time spatial analysis in 3D GIS. At last, the practicality of this algorithm is validated by comparing tests.