摘要： 传统连续碰撞检测算法处理变形三角网格模型时需要大量冗余元素测试。为此,提出一种基于网格拓扑优化的连续碰撞检测优化算法。为减少冗余元素测试,在底层剔除使用2个步骤,采用网格拓扑进行优化,使相邻三角面片不必执行所有的15对元素测试,并使用额外包围盒进一步剔除不相交基元。实验结果表明,该算法可以减少大量的不必要元素测试,提高剔除效率及连续碰撞检测的整体性能,相比额外包围盒算法元素测试个数约减少了5/6,相比三角形表示算法和孤儿集算法元素测试个数约减少了一半。

关键词: 碰撞检测, 连续碰撞检测, 变型三角网格模型, 网格拓扑, 额外包围盒, 底层剔除

Abstract: A large number of redundant elementary tests are needed in traditional continuous collision detection methods for deformable triangle meshes.To solve this problem,a novel continuous collision detection algorithm based on mesh topology is proposed to improve the performance of continuous collision detection algorithm.Two steps are used in low-level culling to reduce the redundant elementary tests.The optimization based on mesh topology guarantees less than 15 elementary tests which are executed by adjacent triangles.The disjoint primitives are further removed by additional bounding boxes.Experimental results show that the proposed algorithm reduces unnecessary elementary tests significantly,so the culling efficiency is increased.Specifically,the proposed algorithm reduces the number of elementary tests about 6 times compared with representative-triangles algorithm.Compared with additional bounding boxes algorithm and orphan sets algorithm,the number of elementary tests of the proposed algorithm is both reduced about twice.The proposed algorithm can also improve the overall performance of continuous collision detection because the culling efficiency is creased.

Key words: collision detection, continuous collision detection, deformable triangle mesh model, mesh topology, additional bounding box, low-level culling

中图分类号: 

• TP391