《碰撞检测算法的探讨》由会员分享，可在线阅读，更多相关《碰撞检测算法的探讨（2页珍藏版）》请在金锄头文库上搜索。
1、碰撞检测算法的探讨摘 要 ：在视景仿真和 3d 游戏设计中，碰撞检测是必不可少的一部分 通过对碰撞检测算法的现状的研究，在几种碰撞检测算法的基础上，提出了一种经过改进的用于判断三维空间中视点或运动物体与场景的碰撞检测算法。关键词 ： 碰撞检测；包围盒；不规则包围体；视景仿真1 概述随着计算机图形学 仿真技术和硬件技术的发展, 用高质量的计算机动画来对现实世界进行模拟与再创造已成为可能 在虚拟世界中如果不加以控制, 运动的物体可以相互穿过,而实际上,这些在真实的世界中是不可能的,我们需要加一个控制机制来真实的模拟现实世界于是, 碰撞检测成为模拟现实世界不可缺少的控制方法。2 碰撞检测算法研究现状
2、目前碰撞检测算法主要有两种, 一种是转化为判断线面的相交问题, 另一种是建立在包围盒基础上,并对其不断完善的算法 这两种算法的原理为:第一种:以视点为起点,前进步长为长度形成线段 , 将此线段与场景中的所有可见面进行相交运算,如果有交点(相交),则表示发生了碰撞第二种: 如果是物体与场景之间的碰撞检测 ,则沿前进方向作一条射线,射线首先与包围盒检测相交,然后再作多变性相交检测;如果是三维实体之间的碰撞检测, 给三维对象建立包围盒,计算包围盒在三维空间的相交情况,具体做法是先用包围盒(球) 进行两两碰撞检测,如果碰撞到了包围球, 则用多边形碰撞检测方法进行计算,但场景实体很多的话,这个方法的效率
3、比较低。在国外, 也有学者在此两种算法的基础上提出一些新的算法 Moore 曾提出了两个有效的碰撞检测算法, 其一是用来处理三角剖分过的物体表面, 由于任一问题表面均可表示成一系列三角面片, 因而该碰撞检测算法具有普遍性, 该算法的缺点是当景物为一复杂的雕塑曲面时,三角剖分可能产生大量的三角片,这会大大影响算法的效率 而另一算法则用来处理多面体环境的碰撞检测:Moore 和 Wilhelems 根据 Cyrus- Beck 裁剪算法提出了一种凸多面体碰撞检测算法, 即通过检测多面体顶点是否相互包含来判定它们是否发生碰撞在国内, 最近提出的算法有利用层次有向包围盒, 即用若干体积略大而形状简单且
4、规则的几何包围体来代替复杂形状的几何对象,来进行碰撞检测; 还有一种基于分离包围盒的碰撞检测的算法, 这种算法有效的提高了碰撞检测的效率3 算法提出碰撞检测按运动物体所处的空间可分为二维平面碰撞检测和三维空间碰撞检测 由于平面物体的构造都可用多边形来表示, 故其检测算法相对要简单一些; 而三维物体的构造比较复杂,其碰撞检测算法也比较困难 三维空间碰撞可分为两运动实体的碰撞, 一个运动实体对静态场景的碰撞 碰撞检测就是检测两物体在空间沿给定轨迹移动时是否发生碰撞, 最初碰撞点的检测就是当一物体以给定的运动规律运动,并将与另一物体发生碰撞时,检测它们在最初发生碰撞时的接触部位4 算法实现在三维虚拟
5、世界中, 场景都是有一系列模型组成的 对于模型来说,大部分都可以看作是有一个个的凸多面体构成的, 且凸多面体由 N 个平面唯一确定 判断运动物体与场景的碰撞问题, 可以简化为运动物体与其最接近的模型的碰撞问题,而模型由凸多面体构成,进而简化为运动物体与平面相交的问题,传统的算法都是要给模型建立包围盒,包围盒分为盒状和球状, 其中以球状的比较简单,只需记录圆心和半径即可检测碰撞, 矩形包围盒相对比较麻烦 但是,这两种用于检测碰撞不够精确,扩大了检测的区域,有些还没有碰撞的物体,也可能会被检测为已碰撞 算法的提出主要是为了解决在场景中进行漫游时视点的碰撞问题,所以假定物体的运动轨迹为直线,并通过对
6、模型生成不规则多面包围体来检测碰撞碰撞检测主要用来检测运动物体与场景内模型是否存在相互包含, 运动物体可以是点也可以是实体 此算法的设计,综合了包围盒(球)算法的优点,在一定程度上克服了它的弱点 首先,选择运动物体的碰撞检测点,并记录碰撞检测点的坐标,作为碰撞检测的依据;然后,为模型建立不规则包围体; 最后,进行几何计算检测碰撞的发生,主要分为三个步骤:第一步, 在运动物体上选取用于检测碰撞的点如果视点是一个点, 那么我们直接记录其坐标即可; 如果是一个实体我们需要选择其运动方向上最前面的点, 具体做法是沿实体的前进方向做一条射线, 确定任意一个与该射线垂直的平面, 改变平面的在射线方向的位置
7、,使其沿实体的前进方向靠近实体,计算平面与实体的交点,并记录此交点,作为检测碰撞的点第二步,为模型建立包围盒以质心为中心, 根据模型的点与质心的距离排列各点, 选择距离质心最远的三个点建立一个三角形, 然后查找一个距离质心第四远的点和第二 三远的点,建立三角形,依次类推,为模型建立不规则包围体,第三步,判断是否发生碰撞 通过第一步我们已选择用于检测碰撞的点记为 T(x,y,z),假如模型的不规则包围体有 n 个面组成,第 i 个面的方程为Ai*X+Bi*Y+Ci*Z+D=0 即 Ni*P+D=0, 其中Ni=(Ai,Bi,Ci)为平面的法向量,P=(X,Y,Z)为平面中的点如果该平面的法向量指
8、向前面的话, 那么 Ni*P+D0, 表示 P 点在平面前, 反之, 如果 Ni*P+D0,则表示此点在平面后 将 T 带入此方程, 对于构成这个凸多面体的所有平面,T 点都在其后的话,那么 T 在这个多面体内部,反之,T 点在其外部 即判断构成模型的所有面 Ni*T+D0(i=1 2 n),是否成立,若成立则发生碰撞,反之,没有发生碰撞5 结论该碰撞检测算法是在已有的此类算法的基础上进行改进而成的,此算法的优点是简单便于编程实现,它可以在视景仿真中,用于检测视点与场景模型的碰撞,但是,对于复杂的场景,此算法还需要很大的改进 因为,根据实际需要,可能要定制复杂的漫游路线,并不都是直线,另外,此算法需要遍历模型中的所有平面, 不能有效降低其时间复杂度 随着对其研究的不断深入,相信一定会有更加全面的算法用于该领域.参考文献1王志强 洪嘉振 杨辉 碰撞检测问题研究综述 J软件学报 ,1999(10).2邹益盛,丁国富,许明恒,何邕,实时碰撞检测算法综述 J计算机应用研究,2008(25):8-12.3王炜,李文辉,张振花, 一种基于分离包围盒的快速碰撞检测算法J软件学报,2008(19):143-150.4王锐,华炜,许高峰,彭群生,鲍虎军, 实体网络模型的变分层次有向包围盒构建 J软件学报,2008(19):31-34.
