郑红波,左少华,程燕飞,秦绪佳,张美玉,徐晓刚

1(浙江工业大学 计算机科学与技术学院,杭州 310023) 2(海军大连舰艇学院 航海系,辽宁 大连 116018)

1 引 言

在三维空间场景中,运动物体需要随时了解自己所处的位置,掌握快速到达目的地的路径.由于运动物体都具有一定的体积和宽度,因此,保证所选择道路足够宽阔,能够顺利通过是一个重要的约束条件.在运动过程中,诸如房屋、树木等景物是无法穿透的,这是选择运动路线中的约束条件之一,需要进行碰撞检测.从上可以看出,在三维复杂场景中,往往因为复杂的环境和视点范围有限,无法识别出运动物体所在的位置,目的地位置也同样很难被快速辨认出,因此需要预先进行路径规划[1],而在此过程中,需要通过碰撞检测来获得可行的运动路径.

在碰撞检测方面已经有一些不错的工作.Jiménez、Segura提出了基于四面体的复杂多边形的碰撞检测算法[2],使得两个待检测的物体特征之间的相交测试数被大幅度地降低了,但与此同时,四面体的构建、包围体的分层和区域的划分过程较为复杂,并且多个物体间的重复区域未被排除导致重复多次检测;Chang、Kim 提出的面向包围盒(OBB)的检测算法[3]虽然能够一定程度上减少检测处理时间,但不易于碰撞点的坐标采集和碰撞的响应,是因为采用本地对象坐标而不是全局对象坐标来进行检测;Schauer、Nüchter提出了基于高效k-d树的碰撞检测算法[4],主要通过kd-CD和简单kd-CD检测算法、kd-PD和快速kd-PD碰撞……