快速高效的碰撞检测算法

Fast Efficient Collision Detection

为了提高碰撞检测算法的效率,提出了一种快速高效的碰撞检测方法.利用Morton码存储物体信息,给出一种改进的图层级结构,可快速分割物体空间,减少物体对相交检测;利用图形处理器(GPU)的并行处理特性进行物体包围盒层级树构建、树遍历,不仅可以快速处理碰撞检测中的事务,还可节省存储空间.实验表明,该方法能够快速构建物体层级结构,并能进行高效的碰撞检测计算.

To speed up collision detection, a novel parallel algorithm for collision detection was proposed. Firstly, spatial Morton codes are used in linear ordering for geometric primitives, this is fast to build boun- ding volume hierarchies. Secondly, a top-down approach that uses the graph of model to build hierarchies optimized from skeletons connection. Thirdly, both algorithms are combined into a hybrid algorithm that need few memories for GPU construction performance and scalability leading to significantly decreased build time. The experimental results show the algorithm has efficient speedup to construct hierarchies of models with up to several million triangles and is fast for collision detection.