基于OBB层次结构碰撞检测的改进算法

摘要

方向包围盒(Oriented bounding box，OBB)的构造以及包围盒的相交测试的计算量都比较大,严重影响了在模拟、仿真的应用,尤其是有变形物体的场景。引入近似凸包的思想提出一种快速构造方向包围盒算法,很大程度上减少了构造方向包围盒(OBB)层次结构的顶点数,改进后的算法在降低构造层次结构时间的同时,对方向包围盒的紧密性代价几乎没有影响,在有些时候还提高了包围盒的紧密性。在包围盒相交测试方面,提出了一种基于单测度的相交预判方法,该算法在检测过程中省去了大量包围盒的相交测试计算,提高了相交测试的速度。最后将两种改进算法联合的碰撞检测框架与常用的基于均值和协方差矩阵的包围盒构造和基于分裂轴的算法进行比较,证明了算法具有高效性。