碰撞检测.doc

碰撞检测(CollisionDetection,CD)也称为干涉检测或者接触检测,用来检测不同对象之间是否发生了碰撞,它是计算机动画、系统仿真、计算机图形学、计算几何、机器人学、CAD\CAM等研究领域的经典问题。碰撞物体可以分为两类:面模型和体模型。面模型是采用边界来表示物体,而体模型则是使用体元表示物体。面模型又可根据碰撞后物体是否发生形变分为刚体和软体,刚体本身又可根据生成方式的不同分为曲面模型和非曲面模型。目前对于碰撞的研究多集中于面模型的研究,因为体模型是一种三维描述方式,对它进行碰撞检测代价较高。而在面模型的研究中,对刚体的研究技术更为成熟。下面列举几种常用的碰撞检测技术:1:包围盒(boundingbox)是由Clark提出的,基本思想是使用简单的几何形体包围虚拟场景中复杂的几何物体,当对两个物体进行碰撞检测时,首先检查两个物体最外层的包围盒是否相交,若不相交,则说明两个物体没有发生碰撞,否则再对两个物体进行检测。基于这个原理,包围盒适合对远距离物体的碰撞检测,若距离很近,其物体之间的包围盒很容易相交,会产生大量的二次检测,这样就增大了计算量。包围盒的类型主要有AABB(AlignedAxisBoundingBox)沿坐标轴的包围盒、包围球、OBB(OrientedBoundingBox)方向包围盒和k-DOP(kDiscreteOrientationPolytopes)离散方向多面体等。AABB是包含几何对象且各边平行于坐标轴的最小六面体,两个AABB包围盒相交当且仅当它们三个坐标轴上的投影均重叠,只要存在一个方向上的投影不重叠,那么它们就不相交。AABB间的相交测试和包围体的更新速度比其他算法效率高,因此使用最广泛,尤其适用于多物体运动的大规模环境和变形体碰撞检测。OBB包围盒的相交测试基于分离轴的理论的,它的构造关键在于包围盒最佳方向的确定,最佳方向必须保证在该方向上包围盒的尺寸最小。由于其较好的紧密性,大大提高了算法的效率,但需要较多的存储空间,构造和更新包围体的速度都比较慢,不能有效地处理变形体等情况。k-DOP使用k/2对的平行平面来包围物体,如果在由k-DOP的边构成的固定方向集合种的某个方向上的投影不重叠,则包围盒必不相交;如果在所有方向上的投影都重叠,则包围盒必相交。通过调整k的取值,k-DOP可以在简单性、紧密性中达到一定的折衷,从而提高碰撞检测的效率。包围盒是目前应用最为广泛的碰撞检测方法,包围盒本身的简单性和所包围物体的紧密性是相互矛盾的,简单性越高其紧密性差,反之如此,所以如何解决这个矛盾是包围盒技术的关键。,并记录所有单元内的特征,通过查询同一个单元或相邻单元内的特征间的相交情况来判断是否发生碰撞检测。按照剖分空间的方法可分为均匀剖分和非均匀剖分。均匀剖分是将场景中的空间均匀的划分为大小一致的单元格,非均匀剖分的方法很多,如BSP树和Kd树等。空间剖分法使用于物体之间距离较远的场景,因为如果物体之间的距离很近,需要对单元格进行更深的递归分割,这样需要更多的空间存储单元格,并需要进行更多的单元格相交测试,从而降低了效率。,表示距离物体表面的最小距离。距离场是矢量场,距离的正负可表示物体在外部或内部,用距离场表