依赖包围盒紧密率及多层建模结构的混合碰撞检测算法

摘要

For the problem that in complex environment the low efficiency of object bounding box selection and updating directly lead to the extended collision detection time, a new hybrid CD algorithm relying on the tightness ratio of bounding volume and multi-layer modeling structure is proposed.The algorithm firstly divides object shape into four kinds by computing and comparing the tightness ratio of bounding box, using sphere bounding box, axis-aligned bounding box, oriented bounding box and ellipsoid bounding box respectively and carrying on intersection test in two bounding box for eliminating disjoint objects quickly and accurately.Meanwhile, in order to reduce the update time for constructing bounding box tree,the optimization method of multi-layer modeling structure which in-cludes triangle,rigid body and model is proposed to construct bounding box tree.Finally,the experimental results show that,compared with using a single bounding box and the traditional hybrid bounding box collision detection al-gorithm,the proposed algorithm shortens the time of intersection test greatly and improves the efficiency of collision detection.%针对复杂环境下物体包围盒选择与更新的低效性,直接导致了碰撞检测时间延长的问题,提出了一种依赖包围盒紧密率及多层建模结构的混合碰撞检测算法.算法首先通过计算比较包围盒紧密率将物体形状分为四类,分别采用Sphere包围盒、轴向平行包围盒、方向包围盒和椭球体包围盒,对两两包围盒进行相交测试,快速准确地剔除不相交的物体.同时,提出三角面片-刚体-模型的多层建模结构的优化方法来构造包围盒树(BVT),减少包围盒树更新时间.最后实验结果表明,相比采用单一包围盒和传统结构的混合包围盒检测算法,该算法能大幅度地缩短相交测试的时间,提高碰撞检测的效率.