基于分类遍历的碰撞检测优化算法

来源：计算机应用杂志2015年第1期北京时间：

作者：孙劲光, 吴素红

单位：1. 辽宁工程技术大学 电子与信息工程学院, 辽宁 葫芦岛125105;2. 辽宁工程技术大学 研究生院, 辽宁 葫芦岛125105

摘要：针对现有层次树遍历方法的低效率问题,提出了一种基于分类遍历的碰撞检测算法.首先根据两个物体树中节点的平衡因子差值来将所有的物体对进行分类:结构相似的,采用同步下降遍历方法;结构不相似的,采用交换下降遍历方法,这减少了相交测试的次数.然后加入时空相关性和优先级策略优化遍历过程.最后通过实验结果表明,相比基于统一遍历的碰撞检测算法,该算法缩短了相交测试的时间,物体数目越多,快速性优势越显著,大约可以缩减所需时间的1/5.

关键词：碰撞检测,层次包围盒,分类遍历,深度优先,物体结构,时空相关性

基金资助：国家科技支撑计划项目(2013BAH120f00).