碰撞检测_碰撞检测算法 - CSDN
碰撞检测 订阅
计算机边发送数据边检测信道上的信号电压大小。 展开全文
计算机边发送数据边检测信道上的信号电压大小。
信息
技术类别
互联网技术
方    法
模拟算法
中文名
碰撞检测
常见形式
3D游戏
监督学习监督学习词性解释
通信信道中的碰撞检测 就是计算机边发送数据边检测信道上的信号电压大小。当一个站检测到的信号电压摆动值超过了一定的门限值时,就会认为总线上至少有两个站同时在发送数据,表示产生了碰撞。在发生碰撞的时候,总线上传输信号产生了严重的失真,无法从中恢复出有用的信息来。每一个正在发送数据的站,一旦发现总线上产生了碰撞,就立即停止发送,以免继续浪费资源,再等待一段时间后再次发送。以太网取51.2μs为争用期长度。对于10Mb/s以太网,在争用期内可发送512bit,即64B。则以太网在发送数据时,若前64B没有冲突,则后续的数据就不会发生冲突。如果发生冲突了一定是在发送的前64B以内。由于一检测到冲突就立即中止发送,这时已经发出去的数据一定小于64B,因此,以太网规定最短有效长为64B,凡长度小于64B的帧都是由于冲突而异常中止的无效帧。发送数据的站一旦发现发生碰撞时,除了立即停止发送数据外,还要继续发送若干比特的认为干扰信号,以便让所有用户都知道已经发生了碰撞。3D游戏中的碰撞检测碰撞检测在3D游戏中至关重要,好的碰撞检测要求人物在场景中可以平滑移动,遇到一定高度内的台阶可以自动上去,而过高的台阶则把人挡住,遇到斜率较小的斜坡可以上去,斜率过大则把人挡住,在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。在满足这些要求的同时还要做到足够精确和稳定,防止人物在特殊情况下穿墙而掉出场景。碰撞检测做得好了是应该的,不易被人注意到,因为这符合我们日常生活中的常识。做得差了却很容易让人发现,人物经常被卡住不能前进或者人物穿越了障碍。所以大部分人都觉得写碰撞检测代码是件吃力不讨好的事情,算法复杂、容易出bug、不容易出彩。下面还是回到正题,看看我们该如何解决这个难题。早期3D游戏的碰撞检测多数基于格子或者BSP树,基于格子的系统实现简单但精度不够,不属于严格意义的3D碰撞检测。基于BSP树的碰撞检测一度十分流行,算法基本已经成熟定型,但它的固有缺点却使它不太适合游戏。BSP树需要很长的预处理时间不适合加载时计算,BSP划分经常会产生原多边形数三到四倍的多边形,考虑到不用保存法线、颜色、uv等信息也要增加将近一倍的资源容量,在一个大的游戏中将模型资源的容量从200M增加到400M相信是大部分人都不愿接受的。对于任意复杂三角形集合(mesh)的碰撞检测多数基于BVTree(bounding volume tree),具体可以是aabb tree,obb tree或者K-dop tree,这也是当今各种物理引擎和碰撞检测引擎流行的做法。上面是碰撞检测按数据结构不同的分类,按检测方式又可以分为离散点的碰撞检测和连续碰撞检测(CCD continuous collision detection)。离散点的碰撞检测是指定某一时刻T的两个静态碰撞体,看它们之间是否交迭,如果没有交迭则返回它们最近点的距离,如果交迭则返回交迭深度,交迭方向等。连续碰撞检测则是分别指定在T1、T2两个时刻两个碰撞体的位置,看它们在由T1运动到T2时刻的过程中是否发生碰撞,如果碰撞则返回第一碰撞点的位置和法线。连续碰撞检测是最为自然的碰撞检测,可以大大方便碰撞响应逻辑的编写,可以很容易避免物体发生交迭或者穿越。离散点的碰撞检测则没有那么友好,当检测到碰撞时两个物体已经发生了交迭,如果其中有三角形网格对象那么已经有许多三角形发生了交迭,如何将两个交迭的对象分开并按合理的方式运动是一个挑战。虽然连续碰撞检测是最自然的方式,但它的实现非常复杂,运算开销也很大,所以大部分成熟的物理引擎和碰撞检测引擎还是采用了基于离散点的碰撞检测,为了避免物体交迭过深或者彼此穿越,大多都要采用比较小的模拟步长。成功商业3D游戏普遍采用的碰撞检测是采用BSP树及包装盒方式。简单讲就是采用一个描述用的正方体或者球型体包裹住3D物体对象整体(或者是主要部分),之后根据“描述用”包装盒的距离、位置等信息来计算是否发生碰撞。
收起全文
  • 碰撞检测经典解决方案

    万次阅读 2012-07-10 09:06:57
    碰撞检测在3D游戏中至关重要,好的碰撞检测要求人物在场景中可以平滑移动,遇到一定高度内的台阶可以自动上去,而过高的台阶则把人挡住,遇到斜率较小的斜坡可以上去,斜率过大则把人挡住,在各种前进方向被挡住的...




            碰撞检测在3D游戏中至关重要,好的碰撞检测要求人物在场景中可以平滑移动,遇到一定高度内的台阶可以自动上去,而过高的台阶则把人挡住,遇到斜率较小的斜坡可以上去,斜率过大则把人挡住,在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。在满足这些要求的同时还要做到足够精确和稳定,防止人物在特殊情况下穿墙而掉出场景。


           碰撞检测做得好了是应该的,不易被人注意到,因为这符合我们日常生活中的常识。做得差了却很容易让人发现,人物经常被卡住不能前进或者人物穿越了障碍。所以大部分人都觉得写碰撞检测代码是件吃力不讨好的事情,算法复杂、容易出bug、不容易出彩。下面还是回到正题,看看我们该如何解决这个难题。

           早期3D游戏的碰撞检测多数基于格子或者BSP树,基于格子的系统实现简单但精度不够,不属于严格意义的3D碰撞检测。基于BSP树的碰撞检测一度十分流行,算法基本已经成熟定型,但它的固有缺点却使它不太适合现在的游戏。BSP树需要很长的预处理时间不适合加载时计算,BSP划分经常会产生原多边形数三到四倍的多边形,考虑到不用保存法线、颜色、uv等信息也要增加将近一倍的资源容量,在一个大的游戏中将模型资源的容量从200M增加到400M相信是大部分人都不愿接受的。目前对于任意复杂三角形集合(mesh)的碰撞检测多数基于BVTree(bounding volume tree),具体可以是aabb tree,obb tree或者K-dop tree,这也是当今各种物理引擎和碰撞检测引擎流行的做法。

           上面是碰撞检测按数据结构不同的分类,按检测方式又可以分为离散点的碰撞检测和连续碰撞检测(CCD continuous collisiondetection)。离散点的碰撞检测是指定某一时刻T的两个静态碰撞体,看它们之间是否交迭,如果没有交迭则返回它们最近点的距离,如果交迭则返回交迭深度,交迭方向等。连续碰撞检测则是分别指定在T1、T2两个时刻两个碰撞体的位置,看它们在由T1运动到T2时刻的过程中是否发生碰撞,如果碰撞则返回第一碰撞点的位置和法线。连续碰撞检测是最为自然的碰撞检测,可以大大方便碰撞响应逻辑的编写,可以很容易避免物体发生交迭或者穿越。离散点的碰撞检测则没有那么友好,当检测到碰撞时两个物体已经发生了交迭,如果其中有三角形网格对象那么已经有许多三角形发生了交迭,如何将两个交迭的对象分开并按合理的方式运动是一个挑战。虽然连续碰撞检测是最自然的方式,但它的实现非常复杂,运算开销也很大,所以目前大部分成熟的物理引擎和碰撞检测引擎还是采用了基于离散点的碰撞检测,为了避免物体交迭过深或者彼此穿越,它们都要采用比较小的模拟步长。

           由于碰撞检测引擎的复杂性和对效率的高要求,我们应该尽量使用目前成熟的完整引擎,而不是自己去开发。经过评估,我决定采用Opcode碰撞检测引擎来做游戏中人物和场景的碰撞检测。Opcode的主要功能是用aabb tree管理复杂三角形集合来和射线、球体,立方体,另一个三角形集合等进行离散点上的碰撞检测,如果检测到交迭则返回所有发生交迭的三角形。Opcode的特点是高度的内存使用优化和极好的效率,ODE物理引擎底层就采用它来做复杂三角形mesh的碰撞检测,Opcode的作者也是NovodeX(PhysX前身)物理引擎的核心开发人员,据说NovodeX采用了Opcode的一个更优化版本。由此可见Opcode的成熟与效率。

           确定了要使用的引擎,下面要讨论的算法就和具体引擎无关了,适合于任何离散点的碰撞检测引擎。我们用AABB包围盒来代表场景中的人物,看看如何实现文章开头所提出的效果。

            首先解释一下检测地面的方式,沿人物包围盒的四条竖边向下投四条射线,射线的终点略低于人物的脚底(也就是说射线的长度是有限的),如果与场景发生碰撞并且碰撞平面的斜率小于某一值则取得碰撞点的高度,否则视为这条射线没有检测到地面。将所有射线检测到的地面高度最大值作为最后的地面高度,如果四条射线都没有检测到地面则认为人物悬空。

     vD = 当前帧人物位移

    p0 = 人物包围盒中心当前位置

    bOnGroundP1; // 人物是否站在地面

    bOnGroundP3; // 人物是否站在地面

    bOnGround; // 人物是否站在地面

     

    p1 = p0 + vD

    在p1位置检测地面

    if( 检测到地面 )

    {

         将包围盒下放到地面得到位置p2

        bOnGroundP1 = true;

    }

    else

    {

         p2 = p1;

        bOnGroundP1 = false;

    }

    测试p2点的包围盒是否与场景交迭

    if( 交迭 )

    {

         取得所有交迭三角形的法线,将它们相加后取平均值,得到法线normal

         将法线与向上的向量叉乘得到切线方向tangent

         // 计算人物沿切线滑动后的位置,注意这里用p0做计算。

         // 如果要使滑动更平滑可以把p0向法线方向推出一些

         // p3 =p0 + normal * 0.1f + vD.Dot(tangent);

         p3 = p0 +vD.Dot(tangent); 

     

         在p3位置检测地面

         if( 检测到地面 )

         {

            将包围盒下放到地面得到位置p4

             bOnGroundP3 = true;

         }

         Else

         {

            p4 = p3;

             bOnGroundP3 = false;

         }

     

         测试p4点的包围盒是否与场景交迭

         if( 交迭 )

         {

            测试p1点的包围盒是否与场景交迭

            if( 交迭 )

            {

                 // 无法得到合理的移动位置,人物位置保持不变

                 // 等待下一帧玩家调整前进方向再做测试

                 将p0作为人物的新位置

                 bOnGround = true;

                 return;

            }

            else

            {

                 将p1作为人物的新位置

                 bOnGround = bOnGroundP1;

                 return;

            }

         }

         Else

         {

            将p4作为人物的新位置

            bOnGround = bOnGroundP3;

             return;

         }

    }

    else

    {

         将p2作为人物的新位置

        bOnGround = bOnGroundP1;

         return;

    }

     

    上面的算法基本达到了文章开头所提到的效果,在某些复杂情况下人物移动还有些不流畅,但没有发现人物有穿越障碍物的现象。在大部分情况下人物的新坐标都会由p2点返回,最坏情况是人物被卡住返回p0点。在P4 3.0G的机器上可以支持120个人物在最坏情况下保持30帧的游戏帧数。

     

     

     

    在使用广义碰撞阶段迅速排除了大量物体以后,将会使用精确到多边形级别的精确碰撞,比如两个凸包之间的碰撞,凸包和面片之间的碰撞,以及2次曲面和多边形面片的碰撞,在游戏中常用的两次曲面有,椭圆体,圆柱体,胶囊,球体等等。对于两个凸包之间的碰撞算法目前比较流行的是SAT,分离轴测试算法可以静态和动态的计算出两个凸包之间的碰撞时间法向量等等。但是对于面数较多的凸包以及2次曲面却不大适合,此时一般使用GJK算法但是GJK算法本身强壮性的实现问题一直是一个较难的问题。在我的一项使用BSP进行碰撞检测的实验中,人物以胶囊来模拟,房屋内部通过非SOLID 的LEAFY BSP来构造,在使用BSP剔除了大量面片以后,遇到这样一个问题:如何在最后筛选下的三角形面片进行碰撞测试,以确定碰撞发生的时间,法向量等。

    本文提出一种简单,易懂,准确的方法用来确定一个以速度v前进的胶囊和一个凸多边形第一次发生碰撞的时间。

    首先一个胶囊是所有到某根线段的距离等于某个值r的点的集合:




    如图:虚线表示该线段这里以ab表示,r代表所有点到该线段的长度:

    首先观察静态情况下的碰撞情况。当一个多边形面片和胶囊碰撞的时候,实际上是该多边形面片中存在一些点,这些点到线段ab的距离小于了r,这是因为在胶囊外部的点到线段ab的距离均大于r(胶囊是所有到某根线段的距离等于某个输r的点的集合)。所以在两个物体都静止的情况下相交测试实际上是测试线段ab到多边形的最短距离,如果该距离<R那么存在碰撞,否则不存在碰撞:



    如图这里以一个三角形为例子,左图中该三角形的所有点到线段ab的距离均大于r所以和该胶囊不相交,而右图中三角形的黑色区域中的点到线段ab的距离小于r所以该三角形和胶囊相交。

    所以实际上只要计算一条线段到某个多边形的距离,然后和r作比较就可以知道是否发生碰撞。而一条线段和一个多边形的距离计算,需要分以下几个步骤(以三角形为例)

    A将线段ab的2个端点投影到三角形所在平面,并检查投影点是否落在三角形内部,如果是的话将该投影距离作为一个候选值

    B分别计算线段ab和三角形的三条边的最短距离点对,并检查该点对中的点是否落在线段中(ab线段和三角形的边线段中)如果是的话将该点对的距离作为一个候选值。

    C分别计算线段ab的两个端点到三角形每条边的投影(实际上是计算最近点对),并检查该投影是否落在边的线段中如果是的话作为一个候选值保存。

    D分别计算三角形的3个顶点到线段ab上的投影,并检查该投影是否落在线段ab中。如果是的话作为一个候选值保存。

    E 分别计算三角形的3个顶点到线段ab的两个顶点,把距离作为候选值保存。

    这样一来碰撞检测就归结为,点和线段,线段和线段,以及点和面的最短点对的计算了,

    最后将上述的候选值进行比较,结果最小的那个就是三角形中到线段ab的距离。

    上述方法非常容易推广到动态的情况也就是:当胶囊以速度v运动时第一次和三角形发生碰撞的时间。问题归结为在哪个时间T线段ab到三角形的距离等于半径r,而这又归结为上述A,B,C,D,E 5个子问题。如果能够分别求出这5个子问题的时间,t1,t2,t3,t4,t5那么取这5个时间中的最小值就是胶囊和三角形发生碰撞的确切时间了。

    下面以两条直线,一条静止,另外一条以速度v移动作为例子,来说明求得时间的过程。问题等同于:

    给定一条静止,另外一条以速度v移动的直线,求出在哪个时间T这两条直线的距离等于半径r。

    对于两条直线,假设直线的方程分别为:

    L1:P1+r1*t;

    L2:P2+r2*t;

    现在架设直线L2以速度v={vx,vy,vz}移动;

    根据两条直线的距离公式

    d=|P1P2 .(r1Xr2)| /|(r1Xr2)|

    其中P1P2是向量代表 P2-P1,X代表叉积,.代表点积

    由于r1,r2是常量不会随着直线的移动而改变,这里令(r1Xr2)=r={x*,y*,z*}

    P1={x1,y1,z1}不变,P2={x2+vx*t, y2+vy*t, z2+vz*t}其中t代表时间是个变量

    带入公式d=|P1P2 .(r1Xr2)| /|(r1Xr2)|可得

    d(t)=x*(x2-x1)+y*(y2-y1)+z*(z2-z1)+(x*vx+y*vy+z*vz)t

    令(x*vx+y*vy+z*vz)=a; x*(x2-x1)+y*(y2-y1)+z*(z2-z1)=b;

    那么d(t) = at+b -----------------------------(1)

    公式1就是两条直线之间的距离随着时间t变化的函数,这是一个带符号的距离,两边平方可得 d^2(t)= (at+b)^2

    这是一个两次方程,假设胶囊半径为r 那么只要求解方程(at+b)^2=r^2这个方程就可以求出子问题B的时间了,同时注意计算出时间t之后还需要计算出该时间两条直线的线最近点对是否都处在两条对应的线段上,如果是的话才是一个合理的时间否则就抛弃该时间。

    通过同样的推导可以分别求出其他子问题的时间取这些时间,取这些时间的最小值就是碰撞第一次发生的时间,当然在求解2次方程过程中要考虑到delta<或者=0的情况这些情况都有自己的物理意义,以上面两条线段距离为例d^2(t)= (at+b)^2中如果a=0

    那么方程恒等于b^2,考察a=0的物理意义,a=0也就是(x*vx+y*vy+z*vz)=0;其中x*,y*,z*是这两条直线所组成的面的法向量

    这表面移动速度平行于这两条直线所组成的面。显然距离是恒定不变的。



    结论:

    以上方法很容易推广到凸多边形,以及求出碰撞的法向量(根据最短时间是由上述A,BCDE中那种情况所引起的)。

    在一般网游的室内环境检测中,使用胶囊模拟人物已经足够了,结合BSP的漂亮剪枝能力,可以做出比较满意和快速的碰撞检测,人物和其他物件的碰撞可以采用凸包比较或者GJK方法等。

     

     

     

     

    周末一天没事写个游戏,好简单的,里面的亮点是碰撞检测代码,是我在国外论坛上看到的一个算法,算是很强的了.下面我贴出来,然后讲一下大致思路,关于游戏的代码就不贴了,一大串的看了也心烦 ^^"
    点击浏览该文件

    这个函数就是碰撞检测的关键,我给它启名叫 "描边"
    首先里面两个参数,第一个pmc就是要描边的mc,第二个num是要描的级数(等下会解释到),我们先可以先看下里面的逐句解释


    function doFigure(pmc, num) {//pmc建立一个数组,数组的大小是num*2;
    pmc.point = new Array(num*2);//pmc的长和宽中取大的,然后除以2
    var mx = Math.max(pmc._width, pmc._height)/2;//360num等分
    var inc = 360/num;// 定义两个变量等下用
    var n = 0;var i = 0;
    // while循环的次数为 i<num*2;while (i<(num*2)) {//从下面n+=inc知道 xsys就是每一个等分上xy的所指的方向var xs = Math.cos((n*Math.PI)/180);var ys = Math.sin((n*Math.PI)/180);//pmc(x,y)点为定点,半径为mx的一个圆的轨迹var x = pmc._x+(mx*xs);var y = pmc._y+(mx*ys);//如果x,y没有接触到pmc,不断循环while (!pmc.hitTest(x, y, true)) {// x,y分别减x -= xs;y -= ys;//如果都小于0,break跳出循环if (x<0 && y<0) {break;}}//把此时的xy,分别计入point数组中pmc.point[i] = x-pmc._x;pmc.point[i+1] = y-pmc._y;n += inc;i += 2;}}

     

    他这么做到底什么意思呢?
    其实point里面就是记录了,一个图形的边缘的坐标.他是怎么做到的?
    我们抛开所有从最里面的while循环讲起吧.
    while
    的条件是,(x,y)点没有接触到pmc的时候,就不断循环,循环的内容是 x-=xs,y-=ys;
    如果我们前面什么也没看,应该可以想象,一开始(x,y)点一定在pmc的右边,然后不断的减一个数值xs,ys,直到减到x,y碰到pmc为止,这样,x,y就是pmc上的一点坐标了.
    但是我们目前还不知道xy是怎么定义的,还有就是xsys怎么来的
    往上看

    var xs = Math.cos((n*Math.PI)/180);
    var ys = Math.sin((n*Math.PI)/180);
    var x = pmc._x+(mx*xs);
    var y = pmc._y+(mx*ys);

    数学好的,一看就看出来了,这是圆的极坐标公式,就是以pmc(x,y)为定点,mx为半径的圆的轨迹.
    看到这里,应该可以猜到,一定是让一些点以圆的方式出现在mc的周围,然后每个点往mc靠拢,知道每个点都靠到mc上面.
    这样我们只要解决这个圆的大小问题了,也就是mx的大小,实际上,你把mx定义成一个很大的数也没问题,但是这样做,会浪费很多,对于写程序的来说,不必要的浪费是不行的^^
    那么看上面的

    var mx = Math.max(pmc._width, pmc._height)/2;

    这里就定下了 mx的大小,也就是从mc的长和宽中找一个较大的出来,这样可以保证画出来的圆把整个mc都抱在了里面,大家看到除以2了吧,所以一定能想到 mc 的注册点一定是在中心哦(这也是关键之一^^)
    接着,和定义半径大小一样,我们做个360度每一度检测一下,也是可以的,但是这样做会很费资源,而且也没有必要那么精细.
    所以才会有一个描边级数num,这个级数就是规定了,num个等次来描,来记录num个点的坐标.然后就是运用了
    随便画个形状,在这个mc中写下面的代码,场景上再建立一个mc,命名为mc2
    你可以看到,你的描边级数越高,每次检测的就越多,所以尽量减少就可以了,像我游戏里面只定义了10.
    其实这只是一个大概的数据,并不是百分百的描边,不过这样已经够用了^^"

     


    onClipEvent (load) {numb = 100;
    _root.doFigure(_name, numb);}
    onClipEvent (enterFrame) {_root.hit = false;
    i = 0;while (i < (numb * 2)) {
    x = points[i] + _x;y = points[i + 1] + _y;
    if (_root.mc2.hitTest(x, y, true)) {_root.hit = true;
    break;}
    i = i + 2;}
    }onClipEvent (mouseDown) {
    if (this.hitTest(_root._xmouse, _root._ymouse, true)) {this.startDrag();
    }}
    onClipEvent (mouseUp) {this.stopDrag();
    }

     

    数学不好,解释的不太清楚,大家不懂的再发贴问,我尽量解释,当然也请高手帮忙完善^^!

     

     

     

    转】MSDN中关于OnDrawItem的说明

    afx_msgvoidOnDrawItem(intnIDCtl,LPDRAWITEMSTRUCTlpDrawItemStruct);

    Parameters

    nIDCtl

         存储发送WM_DRAWITEM消息的控件ID,如果是菜单发送的,nIDCtl的值为0

    lpDrawItemStruct

         一个指向DRAWITEMSTRUCT结构体的指针,该结构体保存有关要被绘制的项目与绘制所需要的类型等星系。

    Remarks

    当自绘按钮(owner-draw button),下拉列表框(combo box),列表框(list box)视觉属性,或者菜单发生变化时,框架为他们的owner调用该函数。

    DRAWITEMSTRUCT结构的itemAction成员定义了要进行的绘制操作行为。该值确定了所需的绘制动作。

    在处理完此消息之前,应用程序应当确保由DRAWITEMSTRUCT结构的成员hDC标识的设备上下文还原到默认状态。

    如果上面结构的成员hwndItem指向CButtonCMenuCListBox或者CComboBox对象,那么就调用相应类的DrawItem虚函数。重载相应类的DrawItem成员函数来绘制各个项。

     

    其他的一些说明:

    OnPaint()这个函数是在已经有形的控件上进行画图的     
      OnPaint()  
      {  
         
    在这里只是画原控件没有的图形  
      }  
       
      OnDrawItem()
    这个函数是自已去绘画一个控件,根据你想要的形状,图案.它是建立一个控件的外表而用到的

     

    可以这样理解,OnDrawItem是画窗口中的子控件的,因为它的入口参数LPDRAWITEMSTRUCT带入不同子控件的相关参数,而且,你得把字控件设置成自画类型,才会调用到OnDrawItem,顺便说一下自画,不是所有设置成自画类型的控件都会调用父窗口的OnDrawItem,例如ListBox的自画,你就必须重载CListBoxDrawItem方法和MeasureItem方法才可以,但象菜单,按钮等的自画则会调用OnDrawItemOnPaintOnDrawItem不在一个范畴内,他是WM_PAINT的响应函数,凡是基于CWnd的类都有OnPaint事件发生,就是说凡是窗口都有WM_PAINT事件发生。(不知道我理解的对不对)

     

     

     

    2009产品创新数字化峰会征文:基于CAD的碰撞检测技术及其在虚拟装配拆卸系统中的应用

    1 引言

        几何形体间的碰撞检测在虚拟装配和拆卸过程中几乎无处不在,碰撞检测的精度决定了虚拟装配和拆卸的精度,对于目前的商用VR开发平台而言,普遍采用多边形(通常是三角形)描述场景中的任意几何形体,并通过纹理映射、光照模型来模型物体在真实世界的视觉效果。而多边形模型首先是面模型,面模型不包括物体的内部信息,无法计算由面所组成的体之间的空间干涉情况,只能计算面面之间的相交情况;其次多边形模型只是对形体几何的逼近形式,对形体的逼近程度决定了三角形面片数量的多少,逼近程度越高,三角形网格数量越多,渲染和碰撞检测的时间开销越大;对形体的描述形式决定了基于多边形网格的碰撞检测算法难以实现物体间的精确碰撞检测。

        精确的碰撞检测首先要保证模型是精确的,其次要保证碰撞检测算法要基于精确模型之间的空间相交求解。在目前一些大型的商用CAD软件中,如UGPro/E等,不仅采用初等解析曲面和样条曲面定义几何物体的外形轮廓曲面,而且采用的是体模型,能够准确定义几何物体的内外部空间,同时其提供的静态干涉检查功能和算法是成熟的,分析时间是高效的,本文通过把商用CAD系统提供的干涉检查功能无缝集成到定制开发的虚拟装配和拆卸系统中,一方面能够实现形体间的精确碰撞检测,同时能够快速地绘制场景以实现交互,并进一步通过采用诸如包围盒等方式构造合适的精确碰撞检测加速策略,快速排除大量不会发生碰撞的物体对,降低复杂场景中进行精确碰撞检测的开销,提高虚拟装配/拆卸系统的实时性。

    2 总体技术方案

        目前商用的VR开发平台均不提供基于CAD几何模型的精确碰撞检测功能,而只提供基于多边形相交测试的碰撞检测功能,不仅碰撞检测精度难以提高,而且由于难以判别包容干涉、接触干涉、硬干涉三种之间的区别,对于虚拟装配和拆卸过程中广泛存在的对齐、贴合、相切等情况难以得到正确的碰撞检测结果,从而影响系统对这类情况做出正确的反应。

        通过深入的研究和程序开发,本文在VR环境中实现了基于CAD几何模型的快速精确碰撞检测功能,图1是系统结构框图。

        从图中可以看出,CAD模型是联系前台的场景展示和后台的碰撞检测计算的纽带,一方面,基于CAD的精确碰撞检测平台在后台对CAD模型进行空间干涉计算,另一方面,前台根据CAD模型动态生成场景图并进行绘制以用于用户交互,从而将仿真的三维显示和仿真计算分离。当场景中的几何对象发生运动时,通过在二者之间建立的通讯技术同步更新运动的几何对象在场景中的几何方位并保持一致。几何对象运动过程中的干涉计算采用离散时间步的方法进行计算,即:几何对象运动时,在场景中以一定的时间间隔步进,同时把该物体运动后的空间方位通过通讯传递给后台用于计算的CAD碰撞检测平台,在后台同步更新运动部件的空间方位后,与其它部件在该时刻进行静态的碰撞干涉计算,然后得到并分析计算结果,并把计算结果通过通讯计算传递到前台VR环境控制端,如果部件间没有发生干涉,则继续进行下一个步进动作,否则在场景中发出干涉信号并做出相应的反应。这样只要步进的距离或角度足够合理,可以获得几何对象运动过程中可能发生的任何干涉情况。

    1系统结构框图

    3 关键技术

        3.1基于CAD的精确碰撞检测算法及其程序实现

        CAD交互界面下的干涉检查功能无法实现批量自动化处理,显然无法集成到定制开发的VR系统中去,为此,必须找到脱离CAD交互运行界面的程序自动化计算方法。通常而言,高端商用CAD系统提供有二次开发包,在其开发包上进行二次开发有望实现干涉检测的程序自动化处理。

        UG NX是高端CAD系统,其提供的二次开发工具NX/Open功能强大,在NX/Open的基础上能够开发实现任意几何对象之间的精确碰撞检测的自动计算。

        使用NX/Open的进行干涉检查分析的步骤如下:

        1)创建一个间隙分析数据集,分配空间并设置相关属性

        2)设置间隙分析模式,允许采用实体模型或多边形网格模型进行干涉检查。

        3)设置间隙分析规则,设置需要排除的干涉检查对。

        4)设置间隙分析中用于分析的几何对象。

        5)进行间隙分析,对上面的设置进行干涉分析。

        6)对计算结果进行分析。从计算结果中找到发生硬干涉的物体对以及干涉区域。

        使用NX/Open进行干涉检查的计算结果的干涉类型分为如下4类:

        1)不干涉:几何对象间没有发生干涉;

        2)包容干涉:一个几何对象在另一个几何对象内部;

        3)硬干涉:两个几何物体在三维空间存在空间位置重叠并且存在相交的空间曲面;

        4)接触干涉:两个几何物体在三维空间存在点或空间曲面接触,但不存在公共的实体空间;

        通过对干涉计算结果进行分析,可以得到任意两个几何对象间的准确的空间干涉情况。

        3.2基于CADVR场景图动态生成技术

        商用VR开发平台不能识别并绘制CAD模型,商用的VR开发平台通常只支持多边形网格模型,而CAD模型是由参数曲面组成的三维实体模型,为了在VR开发平台下渲染CAD模型,必须根据CAD模型的层次结构动态生成VR场景图对象。

        根据CAD模型动态创建VR场景图的关键在于把CAD参数曲面转换为某张逼近程度的多边形网格模型,并按照规定的层次和结构组合成一颗场景树。

        对于一个UG装配文件,采用如下方式组织VR场景图(VR开发平台采用Vega Prime):

        1)Vega Prime场景图根节点上创建一个vpObject组节点,UG装配文件根节点对应于该组节点。

        2)对于UG装配中的每一个部件,在Vega Prime场景图中创建一个vpTransform节点,并把该节点作为第一步创建的vpObject节点的子节点。根据该部件在装配中的空间方位矩阵定义一个vpTransform节点中的方位矩阵,如果该部件是零件模型,则创建一个vsGeometry节点,并把该节点作为vpTransform的子节点;如果该部件仍然是一个装配模型,则再创建一个vpTransform节点,并把该节点作为上一级vpTransform的子节点,把该vpTransform节点作为父节点递归调用步骤2

        通过如上步骤,建立了与CAD模型层次结构类似的Vega Prime场景图结构。

        CAD几何模型到多边形网格模型的转换需要借助于具体的参数曲面离散和多边形网格剖分算法,对于不同类型的的参数曲面,曲面离散和多边形网格剖分算法复杂程度不同,文献[1]对此有详细的描述。

    3.3 可视化前端与后台计算端的几何对象空间方位同步机制

        由于用于用户交互的可视化前端绘制的是由参数曲面离散生成的多边形网格,而后台碰撞检测计算采用的是最初的CAD模型,为了保证碰撞检测结果的正确性,必须保证这两个环境中的部件在任意时刻的空间相对方位保持一致。基于CADVR场景图动态生成技术保证了在初始时刻二者在空间方位上的一致性,同步机制需要保证在任意时刻运动部件在二者当中具有同样的运动特性。采用如下步骤保证二者中的几何对象空间方位的一致性:

        1)Vega Prime场景图节点对象和CAD中的几何对象之间建立一一映射关系,只有建立了一一映射关系,才有可能当用户在交互界面中选择并移动或旋转了某个几何对象时,系统才能指导该几何对象对应于CAD中的哪一个几何对象,并进行相应的平移或旋转。

        2)定义一个结构,该结构用于描述平移或旋转的类型及所有参数以及碰撞检测结果,变换的类型及参数用于在CAD计算端进行同样的变换操作,碰撞检测结果用于指示可视化前端进行相应的响应。该结构定义如下:

        Struct CommunicationData{
        Tag_t motionprt;  //
    当前运动的几何对象
        Unsigned int motiontype;  //0
    代表平移,123分别绕xyz轴旋转
        Double translate[3];  //
    代表进行平移的坐标值
        Double angle;  //
    代表旋转的角度值
        BOOL bIsCollision;  //
    代表是否发生空间干涉 }
       
        3)
    当可视化前端选中某个几何对象并进行相应的运动后,填充CommunicationData中的数据并传递到CAD计算端,CAD计算端根据旋转或平移的大小重新计算运动部件在CAD场景中的方位矩阵,最后采用UF_ASSEM_reposition_part_occurrence或者UF_ASSEM_reposition_instance函数把运动部件放置在新的位置。

        4)CAD端计算运动部件在新的方位处与其它部件之间的空间干涉情况,如果干涉计算结果为硬干涉,则发生空间干涉,填充CommunicationData结构中的bIsCollision域并通知可视化前端,可视化前端获取该值并做出相应的反应。

       3.4 碰撞检测加速策略

        层次包围盒方法的基本思想是用体积略大而几何特性简单的包围盒来近似描述复杂的几何对象,进而通过构造树状层次结构来逼近对象的几何模型,直到几乎完全获得对象的几何特性,从而只需对包围盒重叠的部分进行进一步的相交测试。层次包围盒最重要的特点是能够应用于任意形状的几何对象的物体的碰撞检测,因此也是目前应用最广泛的一种碰撞检测方法。

        层次包围盒树根据包围盒类型的不同又可分为包围球、AABBOBBk-Dop等等,对应于每一类的包围盒都有一个代表性的碰撞检测算法,包围盒的示意图如图6所示:

        1是对几种基本包围盒的碰撞检测算法的性能比较,沿坐标轴的包围盒AABBaxis-aligned bounding boxes)是使用的最久也是最广的包围盒类型,一个给定对象的AABB被定义为包含该对象且各边平行于坐标轴的最小的六面体。其计算十分简单,只需分别计算组成对象的基本几何元素集合中各个元素的顶点的XYZ坐标的最大值和最小值即可;两个AABB相交当且仅当它们在三个坐标轴上的投影区间均重叠,AABB间的相交测试最多只需要6次比较运算。AABB也是众多VR开发平台广泛支持的包围盒类型,为此,本文采用AABB作为选定的包围盒类型。

        本文采用AABB层次包围盒加基于CAD模型的精确碰撞检测算法实现碰撞检测,其中层次包围盒算法用于快速排除场景中没有发生干涉的物体对,对于采用层次包围盒算法计算后仍然干涉的物体对,用采用基于CAD模型的精确碰撞检测算法进行准确的碰撞检测,这样一方面保证了碰撞检测结果的正确性,另一方面能够大大降低碰撞检测的时间开销。


    1基本包围盒碰撞检测算法比较

    4 应用实例及结论

        3是在Vega Prime中开发的原型系统的程序运行界面,在该原型系统中,通过选择运动部件并设置运动路径(平移和旋转),程序通过计算运动部件运动过程中与其它部件的空间干涉情况来判断该运动过程是否存在干涉,空间干涉的结果根据在运动过程中运动部件和非运动部件的UG CAD模型的空间干涉情况得出。


    3原型系统运行界面


    4用于碰撞检测测试的模型

        4是用于虚拟安装测试的模型,需要把红色部件插入到另一个部件的中心圆孔中(圆孔直径与红色物体外径相同),实际上,在插入圆孔的过程中,它们之间只存在接触干涉,而不存在空间硬干涉,对此,基于CAD模型的精确碰撞检测算法可以正确识别,而基于多边形相交测试的碰撞检测算法只能把这类情况作为发生干涉进行处理。

        2显示了在p4 3.4GCPU4G内存和Nvidia Quadro Fx1400显卡微机上进行测试时(红色物体逐步插入圆孔中心,采样100帧的平均值)不同碰撞检测算法和时间开销比较表。


    2几种碰撞检测算法计算的平均时间开销

        从试验结果可以看出,基于CAD模型的精确碰撞检测算法可以区分接触干涉和硬干涉以及包容干涉之间的区别,同时可以在很快的时间开销下完成几何物体间的精确碰撞检测,采用层次包围盒可以进一步降低碰撞检测的时间开销,而采用基于多边形一一相交测试的碰撞检测算法的时间开销随着用于碰撞检测的多边形数目的增加而急剧增加。

        实践证明,本文提出的技术方案切实可行,不仅解决了商用VR开发系统中碰撞检测精度难以提高的技术问题,而且用于精确碰撞检测的时间开销能够满足工程实际需要。

    [参考文献]

    [1] 赵瑛峰,NX Openflight数据交换输出接口开发技术研究[J]产品数字化实践论文集,电子工业出版社,2008.5

    // 球体-球体的碰撞 Sphere-Sphere Collision 
     
    bool IsCollidingSphereToSphere()
    {
          // 两个小球的相对速度
          relative_vel = Sphere2_Vel - Sphere1_Vel;
          r = Sphere1_Radius + Sphere2_Radius;
          relative_position = Sphere2_Center – Sphere1_Center;
          // 检查两个小球是否已经碰撞
          if ((Sqr_relative_position - (r*r)) &lt;= 0)
                return true; 
     
          // 提前跳过测试:如果两个小球朝向远离对方的方向移动,则返回false
          float rel_distance = sqrt(Sqr_relative_pos) - (r); 
     
          //这里我们需要检测两次update之间是否存在碰撞
          if (rel_distance &lt; (sqrt(Sqr_relative_vel)*update_interval))
          {
                time_fract = rel_distance/sqrt(Sqr_relative_vel);
                time_remain = update_interval – time_fract;
                if ((Sqr_relative_pos - (r*r)) &lt;= 0)          {     return true;              }      }      return ((relative_movement * relative_movement - ((Sqr_relative_pos - r*r) -              Sqr_relative_vel)) &gt;
                0);
    } 
     
    // 球体-平面的碰撞 Sphere-Plane Collision
    bool IsCollidingSphereToPlane()
    {
          // 提前跳过测试:检查小球是否可以在没有碰撞的情况下移动,
          // 如果可以,则返回false
          // 如果不可以则检测球体与平面之间的距离是否为
          for (int i=0; i&lt;6; i++)
          {
                // 小球的速度与平面法向量的点积
                // 如果点积为,则速度矢量平行与平面,因此不可能碰撞
                float unit_normal_vel_dot = normal . velocity;
                if (unit_normal_vel_dot &lt; 0.0f)
                {
                      // 计算平面公式
                      float D1 = normal * point_on_plane;
                      float normal_pos_dot = normal . center_S;
                      // 计算球心到平面的距离
                      float distance = (D1-normal_pos_dot)/unit_normal_vel_dot;
                      // 这里处理球体已经接触到盒子的情况
                      if (distance &lt;= radius1)                {                   collide = true;                      // 存储这个面的法向量              }                    break;             }            else         {                  float Projected = velocity * update_interval;                 // 这里处理球体在update_interval时间移动距离x               // 但是x小于球与平面的距离的情况                 if (Projected &gt; distance)
                      {
                            collide = true;
                            time_fract = (distance–radius)/velocity;
                            time_remain = update_interval - time_fract;
                      }
                      break;
                }
          }
          return collide;

     

     

     

     

    物移动控制是单机和网游中比较重要的部分,但前单机游戏使用动力学以及IK动画等已经达到了非常逼真的地步,在大型网络游戏中这样的物理模拟同步是很实现的,因此在目前多数网游中仍旧是采取使用一个包围体(盒子或者胶囊)来模拟人物。一个好的移动系统是很重要的,平滑的贴墙滑动以及下滑,跳跃等会带给玩家顺畅的手感否则则会有种奇怪的感觉,本文具体介绍了一下碰撞反应,包括贴墙滑动等的具体实现细节。包括一个demo实例 。
    目前物理引擎里面大多自带独立于刚体的人物角色控制,但是物理引擎需要特定的物理模型命名以及比较大的物理模拟开销度。如果需要定制自己的特别功能或者需要简化计算(同时模拟多个延迟或者玩家的反应)。就必须自己完成人物碰撞反应控制的代码。
    要完成人物发生碰撞以后的行为控制,需要碰撞检测系统提供以下的碰撞信息,对于每一个碰撞:
    1. 碰撞发生的时间
    2. 碰撞的法向量
    3. 碰撞点
    对于基本的人物碰撞控制反应来说,以上3点是必须的,有时还需要提供和包围体发生碰撞的具体三角形信息。

    对于场景上的物体首先使用胶囊所在的包围盒AABB或者OBB和场景中的碰撞体包围盒作层次碰撞裁减,至于具体怎么组织可以任意,比如可以采用AABB或者OBB树,也可以采用简单的球树。但碰撞进行到树的叶子节点后开始检测人物的AABB盒和该AABB盒所包围的OBJECT的碰撞情况。如果发现这2个AABB(OBB)盒将会发生碰撞,那么开始使用人物的胶囊体和景物所带的三角面片进行精确到polygon soup级别的比较。这时候仍旧可以优化,比如说我还做了一步把一个Object中的三角形面片打成BSP树的形式存储起来,这样可以大大减少胶囊和三角形碰撞检测的次数,因为这种动态检测是十分耗时的。有关胶囊和三角形面片的比较可以参考:http://dev.gameres.com/Program/Abstract/Arithmetic/capsule.mht中的方法。 对于BSP的划分以及AABB碰撞检测就不用多说了~到处都可以找到文章。
    对于地形而言,也是采用同样的方法,只不过对于地形而言三角形信息不用额外存储,只需要使用和渲染相同的三角形(对于景物来说一般不会使用渲染用的三角形而会使用更加简化数量更少的简化网格碰撞模型)。这里可以有很多优化的技巧,因为地形本身是规则的cell一个地形是由若干个patch(一般是16X16)组成的,而每个patch是由若干cell(一般是16X16)组成的。对于patch来说一般已经组织到了一颗QUADTREE中了因为视棱锥裁减也需要这种结构,因此碰撞检测中的AABB-AABB阶段使用这颗已经存在的QUADTREE就可以快速的完成层次碰撞检测了。但发现某个patch中的AABB和人物的AABB发生碰撞后需要检测每一个CELL所在的AABB和人物AABB盒的碰撞,这里可以使用点小技巧比如说首先将AABB盒投影到CELL所在的XY平面上,找出被投影覆盖的那些CELL然后再检测这些CELL的AABB盒是否和人物的发生碰撞。一但确定了某个CELL和人物发生碰撞那么就可以将该CELL中的三角形取出(一般为2个)依次和人物所在的胶囊进行三角形-胶囊的碰撞检测。
    这样当碰撞检测系统完成任务以后我们将会获得一个碰撞信息的数组:
    class CollideInFo{
    public:
    GFVECTOR_3D m_worldcdnorm;//碰撞法向量
    GFPOINT_3D m_worldpoint;//碰撞点
    float m_cdtime;//碰撞时间
    };

    CollideInFo collidearray[];
    然后使用这个数组就可以进行碰撞后的处理了包括,沿墙滑动下滑等等。在具体说明整个人物移动控制算法之前,首先说下动态碰撞检测和静态碰撞检测的区别,动态碰撞检测是指物体A以速度V前进了T时间,在这期间第一次和物体B发生碰撞的时间。这样的碰撞检测必须返回第一次2个物体发生碰撞的时间。而静态检测是指2个不动的物体是否互相相交对于这种检测是不需要返回时间的。动态检测算法比静态的复杂而且也耗用更多的时间。一个完善的碰撞系统需要解决以上2种碰撞检测,如果你不想自己写检测代码,目前比较流行的有OPCODE,SOLID库等检测库 。你可以直接使用他们提供的功能,这里我采用的是自己写检测代码的方法,目前只用到三角形-胶囊,AABB-AABB,OBB-OBB的碰撞检测。 [Page]
    完成了包围体(用的是胶囊)和三角形的碰撞,胶囊和BSP,地形的碰撞检测之后,拥有了碰撞的信息 1。碰撞时间。2。碰撞法向量。3。碰撞点。接着就可以处理人物在碰撞后的反应了。
    首先人物的一次移动分2个阶段,第一个是初始阶段,使用静态碰撞检测获得该阶段的速度(具体做法在后面说)。第2阶段使用该速度去做动态碰撞检测得到碰撞信息,根据这些碰撞信息去处理碰撞后的反应。
    先来看第一阶段,过程对于一个胶囊我们需要获取他周围的临近面片的信息,以决定这个胶囊目前所处平面的倾斜度,是否贴着不可通过的墙等等。我采用的方法是将胶囊体略为膨胀一些,然后调用静态碰撞检测的代码获取和该膨胀后的胶囊体相交的三角形面片碰撞信息如图:
    棕色的是原始的胶囊体,红色的表示将胶囊半径略为增加以后的胶囊体,蓝色的2个地形是将胶囊膨胀以后所发生相交的2个三角形,而如果不采用膨胀的话该胶囊是不和任何三角形相交的,具体膨胀数值可以设为胶囊下落的最小高度,比如你设定胶囊离底部物体超过0.6单位属于腾空状态的话你就将膨胀数值设为0.6。在这个例子中我们将会检测到2个碰撞(蓝色部分)这2个碰撞法向量正好是这2个三角面的法向量(在很多情况下也可能不是这个看你的碰撞代码中法向量是如何计算的了)。其中底部的那个是可行走平面,另外一个是不可行走平面,有了这2个碰撞平面就很简单了,如果用户输入的速度和那个不可行走的平面相反(也就是撞向那个不可行走平面),那么那个不可行走平面是有效的,这样他和底部那个可行走的平面所组成的交线就是人物的初始速度,如果用户输入的速度和那个不可行走的平面法向量相同,那么这个不可行走平面没有作用人物最终的速度就是把用户速度投影到该可行走平面上的速度。
    0顶一下

    具体计算是否能够水平移动以及移动速度的算法:当给出M个不可行走平面和N个可行走平面时:
    1首先将速度在N个可行走平面上分解,检查这些分解的速度是否有效(如何判断速度有效下面会说道)
    2如果在1的时候存在一个有效的速度直接返回该速度
    3没有有效速度,这时检查NXM个平面的交线,将速度在上面分解同时检查是否存在有效速度
    4如果存在有效速度返回该速度
    5否则检查MXM条交线的,将速度在上面分解同时检查是否存在有效速度
    6如果存在有效速度返回该速度
    7否则返回0速度
    那么如何判定速度是否有效呢,首先我们知道了所有碰撞的信息,给定一个速度,如果该速度和所有碰撞的法向量的夹角都是小于90度那么这就是个有效速度,(说明该分解后速度不会引起和这些碰撞面的在一次碰撞,因为该速度是将物体拉下远离该平面的方向的)。如果只要有一个夹角大于90度那么该速度就是非有效速度,同时在移动时还要判断该速度的倾斜角是否大于最大下滑倾斜角。注意 5是很重要的因为2个不可行走的平面所形成的交线仍旧可能是可以行走的,甚至是水平的。
    以上的部分是检查是否能够水平移动的,如果不能水平移动那么该物体会下滑,1如果没有检测到碰撞平面说明物体处于腾空状态,这时候给物体加上重力加速度,产生一个往下的速度和原来的水平速度结合起来(如果存在)。
    如图棕色是原始状态胶囊经过上一帧移动后到达蓝色的位置这时通过上诉算法可以检测到胶囊腾空,这时他的速度为水平速度(红色)+下滑速度(绿色)。
    2如果检测到碰撞平面但是平面以及它们的交线都是不可行走的(倾斜角大于可行走角度)那么依次将当前速度在碰撞平面分解,以及检测每一条可能下滑的交线。得出速度后检测是否是有效速度具体过程和前面检查水平速度时的方法一样,只是将速度投影到平面上的方法不一样具体方法可以根据程序需要,我这里采用首先去掉原始速度在碰撞平面法线的分量,然后将速度分解为2个速度一个是贴着平面水平移动的速度另外一个是贴着平面下滑的速度。注意如果上一帧更新后物体处于下滑状态那么当前速度就因该是该下滑速度,否则则是用户输入的速度。
    如果用户输入的速度是跳跃也就是带Z分量的速度那么,计算初始速度这一步需要略过直接输入给下一阶段用户起跳的速度。

    阶段2计算初始速度引起的碰撞

    对于多数情况来说,计算完初始速度就不会再发生碰撞了,一旦发生,那么我们依旧传入碰撞面的那些法向量,碰撞点的信息,同样采用前面计算初始速度时所采用的方法,计算出碰撞后的调整速度。 [Page]

    整个处理过程基本上就是这样的,其中可能还会出现一些小问题比如说误差控制等。总结一条就是人物行走要么研着平面分解速度要么沿着2个平面的交线行走或者下滑。这个是Demo示例画面(由于没有人帮我做动画。。所以demo中目前只有行走动画,没有起跳,下落等动画。。)

     

     


    展开全文
  • 碰撞检测之OBB-OBB检测

    万次阅读 2016-08-01 13:20:19
    2D情况首先回顾一下SAP两个凸包多边形,当且仅当存在一条线,这两个多边形在这条线上的投影不相交,则这两个多边形也不相交.这条线称为Separating Axis.垂直Separating Axis存在一条Separating Line将两个多边形分开...

    2D情况

    首先回顾一下SAP



    两个凸包多边形,当且仅当存在一条线,这两个多边形在这条线上的投影不相交,则这两个多边形也不相交.


    这条线称为Separating Axis.垂直Separating Axis存在一条Separating Line将两个多边形分开。


    这里还有一个要确定的,就是如果两个矩形之间存在Separating Line,则一定存在一条和两个矩形中的一条边平行。每个矩形对边平行,则我们只需要检查四个方向是否存在Separating Line,如下图



    找Separating Line 就是找Separating Axis, Separating Axis也只有四个方向,所以将矩形在四个轴上投影就可以了,如下图









    下面来看具体的计算


    定义下面几个变量

    PA = coordinate position of the center of rectangle A
    Ax = unit vector representing the local x-axis of A
    Ay = unit vector representing the local y-axis of A
    WA = half width of A (corresponds with the local x-axis of A)
    HA = half height of A (corresponds with the local y-axis of A)


    PB = coordinate position of the center of rectangle B

    Bx = unit vector representing the local x-axis of B
    By = unit vector representing the local y-axis of B
    WB = half width of B (corresponds with the local x-axis of B)
    HB = half height of B (corresponds with the local y-axis of B)


    T= PB - PA

    轴L是Seprating Axis的条件是

    |Proj ( T )| > 0.5 * |Proj ( RectangleA )| + 0.5 *|Proj ( RectangleB )|


    Proj是投影计算, 展开

    | T • L | > | ( WA*Ax ) • L | + | ( HA*Ay ) • L | + | ( WB*Bx ) • L | + |( HB*By ) • L |

    L只有四种情况,AX, AY, BX, BY

    CASE 1:
    // L = Ax
    | T • Ax | > | ( WA*Ax ) • Ax | + | ( HA*Ay ) • Ax | + | ( WB*Bx ) • Ax | + |( HB*By ) • Ax |
    | T • Ax | > WA + 0 + | ( WB*Bx ) • Ax | + |( HB*By ) • Ax |
    | T • Ax | > WA + | ( WB*Bx ) • Ax | + |( HB*By ) • Ax |

    如果成立,存在Separating Axis平行Ax。


    CASE 2:
    // L = Ay
    | T • Ay | > HA + | ( WB*Bx ) • Ay | + |( HB*By ) • Ay |

    如果成立,存在Separating Axis平行Ay。


    CASE 3:
    // L = Bx
    | T • Bx | > | ( WA* Ax ) • Bx | + | ( HA*Ay ) • Bx | + WB

    如果成立,存在Separating Axis平行Bx。


    CASE 4:
    // L = By
    | T • By | > | ( WA* Ax ) • By | + | ( HA*Ay ) • By | + HB

    如果成立,存在Separating Axis平行By。



    三维情况

    在三维情况下的,之前的Separating Line就变成了Separating Plane,如下图



    每个Box都有三组面,每组面都是平行的,Separating Plane都是平行其中的一个面。则两个box的SAT中可能的Separating Axis有六个




    下图中Separating Plane就平行于右边Box的一个面



    然而还有一种情况,如下



    这种情况,两个Box并不相交,但是他们并没有发生碰撞,这种情况,Separating Plane的法线是两条红线的叉乘



    所以在三维情况下Box和Box的碰撞检测需要判定的情况有6+9种

    CASE 1:L = Ax  CASE 2:L = Ay  CASE 3:L = Az   CASE 4:L = Bx   CASE 5:L = By  CASE 6:L = Bz

    CASE 7:L = Ax Bx  CASE 8:L = Ax By  CASE 9:L = Ax Bz  CASE 10:L = Ay Bx  

    CASE 11:L = Ay By  CASE 12:L = Ay Bz  CASE 13:L = Az Bx  CASE 14:L = Az By  CASE 15:L = Az Bz


    判断条件还是

    | T • L | > | ( WA*Ax ) • L | + | ( HA*Ay ) • L | + |( DA*Az ) • L |+ | ( WB*Bx ) • L | + |( HB*By ) • L | + |( DB*Bz ) • L |

    一点优化,关于T • L 

    T • (Ax * Bx) =(T •  Az)(Ay •  Bx) - (T•  Ay)(Az •  Bx)

    这里将有叉乘的地方进行了转化,要看证明的请看参考资料。


    好,可以上代码了

      public static bool IntersectBoxBox(Box box0, Box box1)
            {
                Vector3 v = box1.center - box0.center;
    
                //Compute A's basis
                Vector3 VAx = box0.rotation * new Vector3(1, 0, 0);
                Vector3 VAy = box0.rotation * new Vector3(0, 1, 0);
                Vector3 VAz = box0.rotation * new Vector3(0, 0, 1);
    
                Vector3[] VA = new Vector3[3];
                VA[0] = VAx;
                VA[1] = VAy;
                VA[2] = VAz;
    
                //Compute B's basis
                Vector3 VBx = box1.rotation * new Vector3(1, 0, 0);
                Vector3 VBy = box1.rotation * new Vector3(0, 1, 0);
                Vector3 VBz = box1.rotation * new Vector3(0, 0, 1);
    
                Vector3[] VB = new Vector3[3];
                VB[0] = VBx;
                VB[1] = VBy;
                VB[2] = VBz;
    
                Vector3 T = new Vector3(Vector3.Dot(v, VAx), Vector3.Dot(v, VAy), Vector3.Dot(v, VAz));
    
                float[,] R = new float[3, 3];
                float[,] FR = new float[3, 3];
                float ra, rb, t;
    
                for (int i = 0; i < 3; i++)
                {
                    for (int k = 0; k < 3; k++)
                    {
                        R[i, k] = Vector3.Dot(VA[i], VB[k]);
                        FR[i, k] = 1e-6f + Mathf.Abs(R[i, k]);
                    }
                }
    
                // A's basis vectors
                for (int i = 0; i < 3; i++)
                {
                    ra = box0.extents[i];
                    rb = box1.extents[0] * FR[i, 0] + box1.extents[1] * FR[i, 1] + box1.extents[2] * FR[i, 2];
                    t = Mathf.Abs(T[i]);
                    if (t > ra + rb) return false;
                }
    
                // B's basis vectors
                for (int k = 0; k < 3; k++)
                {
                    ra = box0.extents[0] * FR[0, k] + box0.extents[1] * FR[1, k] + box0.extents[2] * FR[2, k];
                    rb = box1.extents[k];
                    t = Mathf.Abs(T[0] * R[0, k] + T[1] * R[1, k] + T[2] * R[2, k]);
                    if (t > ra + rb) return false;
                }
    
                //9 cross products
    
                //L = A0 x B0
                ra = box0.extents[1] * FR[2, 0] + box0.extents[2] * FR[1, 0];
                rb = box1.extents[1] * FR[0, 2] + box1.extents[2] * FR[0, 1];
                t = Mathf.Abs(T[2] * R[1, 0] - T[1] * R[2, 0]);
                if (t > ra + rb) return false;
    
                //L = A0 x B1
                ra = box0.extents[1] * FR[2, 1] + box0.extents[2] * FR[1, 1];
                rb = box1.extents[0] * FR[0, 2] + box1.extents[2] * FR[0, 0];
                t = Mathf.Abs(T[2] * R[1, 1] - T[1] * R[2, 1]);
                if (t > ra + rb) return false;
    
                //L = A0 x B2
                ra = box0.extents[1] * FR[2, 2] + box0.extents[2] * FR[1, 2];
                rb = box1.extents[0] * FR[0, 1] + box1.extents[1] * FR[0, 0];
                t = Mathf.Abs(T[2] * R[1, 2] - T[1] * R[2, 2]);
                if (t > ra + rb) return false;
    
                //L = A1 x B0
                ra = box0.extents[0] * FR[2, 0] + box0.extents[2] * FR[0, 0];
                rb = box1.extents[1] * FR[1, 2] + box1.extents[2] * FR[1, 1];
                t = Mathf.Abs(T[0] * R[2, 0] - T[2] * R[0, 0]);
                if (t > ra + rb) return false;
    
                //L = A1 x B1
                ra = box0.extents[0] * FR[2, 1] + box0.extents[2] * FR[0, 1];
                rb = box1.extents[0] * FR[1, 2] + box1.extents[2] * FR[1, 0];
                t = Mathf.Abs(T[0] * R[2, 1] - T[2] * R[0, 1]);
                if (t > ra + rb) return false;
    
                //L = A1 x B2
                ra = box0.extents[0] * FR[2, 2] + box0.extents[2] * FR[0, 2];
                rb = box1.extents[0] * FR[1, 1] + box1.extents[1] * FR[1, 0];
                t = Mathf.Abs(T[0] * R[2, 2] - T[2] * R[0, 2]);
                if (t > ra + rb) return false;
    
                //L = A2 x B0
                ra = box0.extents[0] * FR[1, 0] + box0.extents[1] * FR[0, 0];
                rb = box1.extents[1] * FR[2, 2] + box1.extents[2] * FR[2, 1];
                t = Mathf.Abs(T[1] * R[0, 0] - T[0] * R[1, 0]);
                if (t > ra + rb) return false;
    
                //L = A2 x B1
                ra = box0.extents[0] * FR[1, 1] + box0.extents[1] * FR[0, 1];
                rb = box1.extents[0] * FR[2, 2] + box1.extents[2] * FR[2, 0];
                t = Mathf.Abs(T[1] * R[0, 1] - T[0] * R[1, 1]);
                if (t > ra + rb) return false;
    
                //L = A2 x B2
                ra = box0.extents[0] * FR[1, 2] + box0.extents[1] * FR[0, 2];
                rb = box1.extents[0] * FR[2, 1] + box1.extents[1] * FR[2, 0];
                t = Mathf.Abs(T[1] * R[0, 2] - T[0] * R[1, 2]);
                if (t > ra + rb) return false;
    
                return true;
            }

    测试代码

    public class BoxBoxTester : MonoBehaviour {
        public GameObject box;
        public GameObject box1;
        Box _box;
        Box _box1;
        // Use this for initialization
        void Start()
        {
            _box = new Box();
            _box1 = new Box();
        }
    
        // Update is called once per frame
        void Update()
        {
            _box.center = box.transform.position;
            _box.rotation = box.transform.rotation;
            _box.extents = 0.5f * box.transform.localScale;
    
            _box1.center = box1.transform.position;
            _box1.rotation = box1.transform.rotation;
            _box1.extents = 0.5f * box1.transform.localScale;
    
            if (NIntersectTests.IntersectBoxBox(_box, _box1))
            {
                box.GetComponent<MeshRenderer>().materials[0].SetColor("_Color", new Color(1, 0, 0));
            }
            else
            {
                box.GetComponent<MeshRenderer>().materials[0].SetColor("_Color", new Color(1, 1, 1));
            }
        }
    }
    


    运行结果




    参考

    Separating Axis Theorem for Oriented Bounding Boxes

    展开全文
  • 游戏开发中常见的几种碰撞检测

    千次阅读 2017-11-02 14:05:52
    在游戏中,经常需要进行碰撞检测的实现,例如判断前面是否有障碍以及判断子弹是否击中飞机,都是检测两个物体是否发生碰撞,然后根据检测的结果做出不同的处理。 进行碰撞检测的物体可能有些的形状和复杂,这些需要...

    在游戏中,经常需要进行碰撞检测的实现,例如判断前面是否有障碍以及判断子弹是否击中飞机,都是检测两个物体是否发生碰撞,然后根据检测的结果做出不同的处理。 进行碰撞检测的物体可能有些的形状和复杂,这些需要进行组合碰撞检测,就是将复杂的物体处理成一个一个的基本形状的组合,然后分别进行不同的检测。 下面简单介绍一下两种最基本的形状进行碰撞的时候进行的处理。

    1、矩形和矩形进行碰撞
    一般规则的物体碰撞都可以处理成矩形碰撞,实现的原理就是检测两个矩形是否重叠。

    矩形1的参数是:左上角的坐标是(x1,y1),宽度是w1,高度是h1;
    矩形2的参数是:左上角的坐标是(x2,y2),宽度是w2,高度是h2。

    在检测时,数学上可以处理成比较中心点的坐标在x和y方向上的距离和宽度的关系。

    即两个矩形中心点在x方向的距离的绝对值小于等于矩形宽度和的二分之一,同时y方向的距离的绝对值小于等于矩形高度和的二分之一。

    x方向:| (x1 + w1 / 2) – (x2 +w2/2) | < |(w1 + w2) / 2|
    y方向:| (y1 + h1 / 2 ) – (y2 + h2/2) | < |(h1 + h2) / 2 |

    在程序中,只需要将上面的条件转换成代码就可以实现了

    2、圆形和圆形的碰撞

    圆形和圆形的碰撞应该说是一种最简单的碰撞,因为在数学上对于两个圆形是否发生重叠,有计算两个圆心之间的距离的公式。

    那么条件就变为:计算两个圆心之间的距离是否小于两个圆的半径和。

    假设
    圆形1的左上角坐标是(x1,y1),半径是r1,
    圆形2的左上角的坐标是(x2,y2),半径是r2。

    因为MIDP1.0中没有浮点数,而且浮点数的运算比较慢,
    所以我们将条件做一个简单的变换:对于条件的两边都进行平方,这样就去掉了开方的运算步骤。

    下面是数学表达式:
    (x1 – x2)2 + (y1 – y2)2 < (r1 + r2)2
    在程序中,只需要将上面的条件转换成代码就可以了。

    展开全文
  • Pygame:碰撞检测

    千次阅读 2020-02-12 18:31:12
    文章目录(一)碰撞检测的原理(二)手动写代码实现碰撞检测1️⃣版本一2️⃣版本二(三)使用sprite 提供的现成的碰撞检测函数 ????大家好!我是近视的脚踏实地,虽然近视,但是脚踏实地,这一篇来学习游戏中的...


    🚴大家好!我是近视的脚踏实地,虽然近视,但是脚踏实地,这一篇来学习游戏中的碰撞检测,然后继续完善未完成的小游戏

    (一)碰撞检测的原理

    大部分游戏都是要做碰撞检测的,因为你要知道小球是否发生了碰撞,子弹是否击中了目标等等。那么其实碰撞原理也很简单,事实就是检测两个精灵是否存在重叠的部分。
    在这里插入图片描述

    比如上面这张图👆,width表示的就是圆心的距离,r1、r2分别表示他们的半径,此时width是大于他们的半径之和的,那么他们就是没有产生重叠,也就是没有发生碰撞,那么当碰撞发生的那一刹那,如下图👇
    在这里插入图片描述

    可以看到此时width是等于r1+r2的,圆心距刚好等于两个半径之和.再来看看下面第三张图片
    在这里插入图片描述

    可以看到当他们重叠,产生交集的时候,width是小于r1+r2的,所以得到的结果就是判断两个小球是否发生碰撞,我们只要检测两个小球的圆心距是否小于等于他们两个半径之和就🉑了

    (二)手动写代码实现碰撞检测

    1️⃣版本一

    collide_check.py:👇

    import pygame
    import sys
    import math
    from pygame.locals import *
    from random import *
    
    # 球类继承自Spirte类
    class Ball(pygame.sprite.Sprite):
        def __init__(self, image, position, speed, bg_size):
            pygame.sprite.Sprite.__init__(self)
    
            self.image = pygame.image.load(image).convert_alpha()
            self.rect = self.image.get_rect()
            self.rect.left, self.rect.top = position
            self.speed = speed
            self.width, self.height = bg_size[0], bg_size[1]
    
        def move(self):
            self.rect = self.rect.move(self.speed)
    
            
            # 如果小球的左侧出了边界,那么将小球左侧的位置改为右侧的边界
            # 这样便实现了从左边进入,右边出来的效果
            if self.rect.right < 0:
                self.rect.left = self.width
    
            elif self.rect.left > self.width:
                self.rect.right = 0
    
            elif self.rect.bottom < 0:
                self.rect.top = self.height
    
            elif self.rect.top > self.height:
                self.rect.bottom = 0
    
    def collide_check(item,target):
         col_balls = []
         for each in target:
             distance = math.sqrt(\
                  math.pow((item.rect.center[0] - each.rect.center[0]), 2) + \
                  math.pow((item.rect.center[1] - each.rect.center[1]), 2))
             if distance <= (item.rect.width + each.rect.width) / 2:
                  col_balls.append(each)
         return col_balls
             
    def main():
        pygame.init()
    
        ball_image = "gray_ball.png"
        bg_image = "background.png"
    
        running = True
    
        bg_size = width, height = 1024, 681
        screen = pygame.display.set_mode(bg_size)
        pygame.display.set_caption("Play the ball - Monster ZF")
    
        background = pygame.image.load(bg_image).convert_alpha()
        
        # 用来存放小球对象的列表
        balls = []
    
        # 创建五个小球
        BALL_NUM = 5
        for i in range(BALL_NUM):
            # 位置随机,速度随机
            position = randint(0, width-100), randint(0, height-100)
            speed = [randint(-10, 10), randint(-10, 10)]
            ball = Ball(ball_image, position, speed, bg_size)
            balls.append(ball)
    
        clock = pygame.time.Clock()
    
        while running:
            for event in pygame.event.get():
                if event.type == QUIT:
                    pygame.quit()
                    sys.exit()
    
            screen.blit(background, (0, 0))
    
            for each in balls:
                each.move()
                screen.blit(each.image, each.rect)
    
            for i in range(BALL_NUM):
                item = balls.pop(i)
    
                if collide_check(item,balls):
                     item.speed[0] = -item.speed[0]
                     item.speed[1] = -item.speed[1]
    
                balls.insert(i, item)
    
            pygame.display.flip()
            clock.tick(30)
            
    
    if __name__ == "__main__":
        main()
    
    

    代码解析:这个代码是从上一篇博客中拷贝过来然后接着添加碰撞检测的代码。

    那么首先在main函数上面先写个def collide_check(item, target): 用于碰撞检测的函数,这个函数应该有两个参数,第一个参数是传入一个项目,传入一个球,传入一个object,然后第二个参数是传入一组球,一个列表的球,因为我们有5个球,传入第一个球,然后碰撞,检测他跟其他四个球是否发生碰撞,如果是的话,你这个球就应该向别的地方去移动,移动方向应该发生改变,这里用target来存放其他的四个球。

    接着用for each in target: 循环把每一个球取出来,然后我们就 distance = math.sqrt(…) 求他们的圆心距,我们的rect矩形对象,就是每一个Surface对象都会有一个rect矩形对象描述这个Surface对象的位置,那么这个rect矩形对象有个center的属性,他就是表示这个rect矩形对象的中心的那个点的坐标,然后这里计算距离需要用到Math函数,去前面导入Math模块,那么这个计算圆心距的原理就是小学数学的问题了,那么就是比如有两个点(x1,y1)、(x2,y2),那他们的距离就是x1-x2的平方 + y1-y2的平方 最后再开根号就🉑了

    接着 if distance <= (item.rect.width + each.rect.width) / 2: 再来判断他们的圆心距和他们的半径之和,半径就是他们的宽度之和(直径+直径)除以2,如果比半径和小的话,就说明他们发生了一个重叠,那就把会发生重叠的元素item把它添加到一个列表里边去,然后把这个列表给返回,👉col_balls = []col_balls.append(each),最后return col_balls 把这个列表返回,如果列表里边有内容,那么这些内容就是跟这个item发生发生碰撞的所以的其他的小球,如果说返回的是一个空列表,那么说明这个球很幸运,他没有和任何球发生碰撞

    然后我们应该在哪里要添加,那就是应该在移动小球之后,就要对他进行检测,如果说检测到他们移动之后是发生碰撞的,那么我们就把它的方向给取反,我们现在先再加个定义BALL_NUM = 5,这样显得更专业,以后要修小球个数就改这个变量就可以了,接着把for循环里的5换成BALL_NUM

    接着写到for i in range(BALL_NUM):item = balls.pop(i),这个循环就是用来检测,检测的时候,因为刚刚写的那个检测碰撞的方法是这里的item是跟target其他的四个小球,而不是全部,因为他自己跟自己肯定会相撞,他是跟其他四个小球,所以说在这里检测的时候就需要先把自己给拿出来,就是用pop方法,

    取完之后,if collide_check(item, balls): 就可以调用那个刚刚写好的,用于检测的方法,然后现在这个balls里边剩下的就是四个小球,如果说检测之后列表里有内容,那就 item.speed[0] = -item.speed[0]、item.speed[1] = -item.speed[1] 这个item自身的问题就要对他进行修改,把它两个方向上的速度取反就可以了

    接着 balls.insert(i, item) 处理完要记得把小球放回去,放回列表中,从哪拿出来就放回哪去,从i拿就放回i处,比如说刚开始循环是第0号元素,那我拿出来之后原来的1号就变成0号了,那我又放到0号,原来的0号又变成1号了,大概就是这个意思,这个时候先来运行检测一下刚刚完成的代码:如下:👇
    在这里插入图片描述
    从运行结果来看,碰撞的效果成功了👏👏,老是抖抖的,But!那两个球在干嘛😂😂,缠缠绵绵的也不分开。

    原因其实是这样:小球在诞生的时候,它诞生的位置,就是其他小球已经出来了,这个小球诞生的时候,所在的位置正好有其他的小球,那么它就诞生在别的小球的上方了,因此代码中就会检测到两个小球会发生碰撞了,碰到的话,他的speed速度就会取反,但是取反,如果不能一次性将他们移出这个覆盖的范围的话,比如说,假设他们覆盖的范围是5,5个像素的位置相交,然后他们取反之后,他们的速度都是-1,一个1一个-1,那么他们通过一次移动是不能离开这个相交的范围的,所以在他们下一次检测的时候,他又测试到碰到碰撞,所以他们的位置就再次取反,又要往相同的方向去运动,他们又要相交了,所以就一直在那抖动脱离不开,所以要怎么解决呢🤔

    2️⃣版本二

    那么其实解决的方法也很简单,就是创建小球的时候,先调用检查碰撞的方法就可以了,作如下修改:👇
    在这里插入图片描述
    代码解析:while collide_check(ball, balls): 这里检测ball跟balls,就是跟已经创建出来,已有的列表其他小球是否发生碰撞的检测,如果说while True,即有碰撞返回碰撞的小球的话,就说明这个ball应该重新分配。

    接着ball.rect.left, ball.rect.top = randint(0, width-100), randint(0, height-100) 这里需要的是 不要直接写ball.position,因为 position只是作为参数传进去然后初始的,position并不是这个球类的一个属性,是属性才可以这么调用,但他只是作为参数传进去的,然后position这个参数是传给self.rect.left, self.rect.top 的,所以这里就是这样写ball.rect.left, ball.rect.top

    import pygame
    import sys
    import math
    from pygame.locals import *
    from random import *
    
    # 球类继承自Spirte类
    class Ball(pygame.sprite.Sprite):
        def __init__(self, image, position, speed, bg_size):
            pygame.sprite.Sprite.__init__(self)
    
            self.image = pygame.image.load(image).convert_alpha()
            self.rect = self.image.get_rect()
            self.rect.left, self.rect.top = position
            self.speed = speed
            self.width, self.height = bg_size[0], bg_size[1]
    
        def move(self):
            self.rect = self.rect.move(self.speed)
    
            
            # 如果小球的左侧出了边界,那么将小球左侧的位置改为右侧的边界
            # 这样便实现了从左边进入,右边出来的效果
            if self.rect.right < 0:
                self.rect.left = self.width
    
            elif self.rect.left > self.width:
                self.rect.right = 0
    
            elif self.rect.bottom < 0:
                self.rect.top = self.height
    
            elif self.rect.top > self.height:
                self.rect.bottom = 0
    
    def collide_check(item,target):
         col_balls = []
         for each in target:
             distance = math.sqrt(\
                  math.pow((item.rect.center[0] - each.rect.center[0]), 2) + \
                  math.pow((item.rect.center[1] - each.rect.center[1]), 2))
             if distance <= (item.rect.width + each.rect.width) / 2:
                  col_balls.append(each)
         return col_balls
             
    def main():
        pygame.init()
    
        ball_image = "gray_ball.png"
        bg_image = "background.png"
    
        running = True
    
        bg_size = width, height = 1024, 681
        screen = pygame.display.set_mode(bg_size)
        pygame.display.set_caption("Play the ball - Monster ZF")
    
        background = pygame.image.load(bg_image).convert_alpha()
        
        # 用来存放小球对象的列表
        balls = []
    
        # 创建五个小球
        BALL_NUM = 5
        for i in range(BALL_NUM):
            # 位置随机,速度随机
            position = randint(0, width-100), randint(0, height-100)
            speed = [randint(-10, 10), randint(-10, 10)]
            ball = Ball(ball_image, position, speed, bg_size)
    
            while collide_check(ball, balls):
                ball.rect.left, ball.rect.top = randint(0, width-100), randint(0, height-100)
            balls.append(ball)
    
        clock = pygame.time.Clock()
    
        while running:
            for event in pygame.event.get():
                if event.type == QUIT:
                    pygame.quit()
                    sys.exit()
    
            screen.blit(background, (0, 0))
    
            for each in balls:
                each.move()
                screen.blit(each.image, each.rect)
    
            for i in range(BALL_NUM):
                item = balls.pop(i)
    
                if collide_check(item,balls):
                     item.speed[0] = -item.speed[0]
                     item.speed[1] = -item.speed[1]
    
                balls.insert(i, item)
    
            pygame.display.flip()
            clock.tick(30)
            
    
    if __name__ == "__main__":
        main()
    

    在这里插入图片描述

    (三)使用sprite 提供的现成的碰撞检测函数

    上面的碰撞函数是我们自己实现的,那么下面来继续学习下 sprite 提供的现成的碰撞检测函数,那么我们为什么还要学这个现成的呢,因为我们自己实现的collide_check() 函数只是适用于圆与圆之间的碰撞检测,如果说其他的多边型,或者说矩形,三角形,还有一些不规则的多边形等等,那么自己写的collide_check() 就有局限性了,达不到相应的效果了。

    Pygame 的 sprite 模块事实上已经提供了一个成熟的碰撞检测的函数供我们使用,这也是我们要将我们的类继承 sprite 模块的 Sprite 基类的原因。

    spritecollide(sprite, group, dokill, collided = None)

    如上,sprite模块提供了 spritecollide() 方法用于 检测某个精灵是否与指定的组中其它精灵发生碰撞,事实上跟刚刚自己写的collide_check() 原理基本上是类似的。

    他有四个参数,第一个参数是指定被检测的精灵,就是我们刚刚的item。

    第二个参数是指定一个组,就是我们刚才里边的列表,这个组的话,他是 sprite 的一个组,所以我们要由sprite.Group() 来生成

    第三个参数是设置是否从组中删除检测到碰撞的精灵,如果设置为True的话,如果发生碰撞,他会把组中跟他产生碰撞的精灵给删除掉

    第四个参数是指定一个回调函数,他是用于定制特殊的检测方法,如果说第四个参数忽略的话,那么是默认检测精灵的之间的 rect (矩形)属性

    那下面也是拿上一篇博客的代码来继续增添检测碰撞的代码

    import pygame
    import sys
    from pygame.locals import *
    from random import *
    
    # 球类继承自Spirte类
    class Ball(pygame.sprite.Sprite):
        def __init__(self, image, position, speed, bg_size):
            # 初始化动画精灵
            pygame.sprite.Sprite.__init__(self)
    
            self.image = pygame.image.load(image).convert_alpha()
            self.rect = self.image.get_rect()
            # 将小球放在指定位置
            self.rect.left, self.rect.top = position
            self.speed = speed
            self.width, self.height = bg_size[0], bg_size[1]
            self.radius = self.rect.width / 2
    
        def move(self):
            self.rect = self.rect.move(self.speed)
    
            # 如果小球的左侧出了边界,那么将小球左侧的位置改为右侧的边界
            # 这样便实现了从左边进入,右边出来的效果
            if self.rect.right < 0:
                self.rect.left = self.width
    
            elif self.rect.left > self.width:
                self.rect.right = 0
    
            elif self.rect.bottom < 0:
                self.rect.top = self.height
    
            elif self.rect.top > self.height:
                self.rect.bottom = 0
            
    def main():
        pygame.init()
    
        ball_image = "gray_ball.png"
        bg_image = "background.png"
    
        running = True
    
        # 根据背景图片指定游戏界面尺寸
        bg_size = width, height = 1024, 681
        screen = pygame.display.set_mode(bg_size)
        pygame.display.set_caption("Play the ball - Monster ZF")
    
        background = pygame.image.load(bg_image).convert_alpha()
    
        # 用来存放小球对象的列表
        balls = []
        group = pygame.sprite.Group()
    
        # 创建五个小球
        for i in range(5):
            # 位置随机,速度随机
            position = randint(0, width-100), randint(0, height-100)
            speed = [randint(-10, 10), randint(-10, 10)]
            ball = Ball(ball_image, position, speed, bg_size)
            while pygame.sprite.spritecollide(ball, group, False, pygame.sprite.collide_circle):
                ball.rect.left, ball.rect.top = randint(0, width-100), randint(0, height-100)
            balls.append(ball)
            group.add(ball)
    
        clock = pygame.time.Clock()
    
        while running:
            for event in pygame.event.get():
                if event.type == QUIT:
                    pygame.quit()
                    sys.exit()
                
            screen.blit(background, (0, 0))
    
            for each in balls:
                each.move()
                screen.blit(each.image, each.rect)
    
            for each in group:
                group.remove(each)
    
                if pygame.sprite.spritecollide(each, group, False, pygame.sprite.collide_circle):
                    each.speed[0] = -each.speed[0]
                    each.speed[1] = -each.speed[1]
    
                group.add(each)
    
            pygame.display.flip()
            clock.tick(30)
    
    
    if __name__ == "__main__":
        main()
    

    在这里插入图片描述
    首先要先添加一个pygame自己的sprite的Group,然后他才能进行一个检测,因为刚刚讲了这个spritecollide函数他是需要他们自己的Group,所以要在这里创建一个他自己的Group

    在这里插入图片描述
    那么这次我们有经验了,在创建小球的时候先来个碰撞检测,不然又会出现两个球一直在那抖啊抖,spritecollide函数第一个参数就是传入需要检测的小球,第二个参数传入一个group,第三个参数传进False,,第四个参数先不管

    接着如果检测到碰撞的话同时来修改他的位置ball.rect.left, ball.rect.top = randint(0, width-100), randint(0, height-100)

    接着group.add(ball) add是填加一个元素到组里边去,而remove就是从里边删除,那这里就把ball装进去

    在这里插入图片描述
    接着让小球移动后也要来做个碰撞检测,还是同样的 group.remove(each) 先把这个小球从组里边拿出来,拿出来之后那对他进行一个检测,pygame.sprite.spritecollide(each, group, False, pygame.sprite.collide_circle): 我们不希望他检测之后从组里删除,所以设置为False,就是按照之前的套路来走,思路是一样

    下面就是如果检测到了碰撞,就修改他的方向,然后检测完之后,又把它添加回去,跟之前的思路是一样的

    接着就运行调试一下,发现同样可以实现碰撞检测的功能了,但是这还是有一些瑕疵,仔细看可以发现有时候,碰撞检测并不是完美的,有的情况相撞的时候,他们中间是还有空隙的,感觉他们还没有接触,他们就碰撞了,但有时候也不会,那这是什么原因呢🤔,

    其实是这样的,刚刚提到spritecollide方法的时候,说了他的第四个参数collided = None 如果不指定的话,就表示检测的精灵是检测rect的属性是否重叠,那我们的小球事实上就是这样的👇:
    在这里插入图片描述
    这里是对PNG图片的透明部分做了一个加深,所以当两个小球是这样的形式,这样的角度碰撞的话,他事实上这个rect矩形已经撞上了。那么这个sprite模块里边刚好有个collide_circle方法👇:

    collide_circle(left,right)

    这个函数就是专门用于检测两个圆之间是否发生碰撞,这个函数有两个参数,就分别是两个精灵,他会自动传进去,所以直接把这个函数的名字作为spritecollide方法的第四个参数传进去就好了。

    但是要注意**collide_circle(left,right)**这个函数的话他需要精灵对象有一个叫做 radius半径的属性,所以精灵的话再去添加一个属性就好,再去给之前的第四个参数补上
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    到这里他就会去检测两个圆形是否真正发生碰撞,而不是两个rect,那么现在就已经是完美的检测碰撞了,效果如下:👇
    在这里插入图片描述

    本篇博客到这就完啦,下一篇继续完善这个小游戏,非常感谢您的阅读🙏,如果对您有帮助,可以帮忙点个赞或者来波关注鼓励一下喔😬 ,嘿嘿👀

    展开全文
  • 很多游戏中都需要使用碰撞检测算法检测两个物体的碰撞,但通常这些碰撞检测算法都很耗时很容易拖慢游戏的速度。这里我们学习一下使用四叉树来对碰撞检测进行优化,优化的根本是碰撞检测时跳过那些明显离得很远的物体...
  • 碰撞检测

    2019-04-09 19:04:18
    // 碰撞检测 // // Created by 柯木超 on 2019/4/9. // Copyright © 2019年 柯木超. All rights reserved. // #import "GameViewController.h" typedef NS_ENUM(NSUInteger,MaskType) { M...
  • 场景碰撞检测

    2019-08-28 20:40:34
    碰撞检测:用于检测场景相机漫游时与模型之间的碰撞,当相机与模型之间的距离等于指定的检测距离时,相机则不能继续向模型拉近。在浏览三维场景时,当视角遇见模型,不会穿入模型内部。 (二)操作步骤 碰撞分析功能...
  • 碰撞检测和触发检测

    2019-07-17 01:47:17
    发生碰撞的条件:主动方必须有Rigidbody,发生碰撞的两个游戏对象必须有Collider,被动方对于RigidBody可有可无,碰撞检测方法里的参数表示主动方发生触发的条件:发生碰撞的物体两者其中之一有Rigidbody即可,发生...
  • 碰撞检测是很多动画中必不可少的,你必须掌握基于几何图形的碰撞检测、基于距离的碰撞检测方法,以及如何更有效的的检测多物体间的碰撞。 https://www.kancloud.cn/dennis/canvas/340130...
  • 游戏中的碰撞检测

    2019-01-12 23:11:38
    游戏中的碰撞检测方式有很多,不同的算法之间主要是在精度和速度之间权衡。以下几种方式按照速度排序说明。以2D为例,3D不过是增加了一维罢了,算法理解上没太大区别。   一、地图格子划分检测  最简单的一种...
  • 这几天放寒假了,时间也多了...他虽然是搞C++的,但听了我代码解释中有检测圆形碰撞时,他立刻就发现了问题,他告诉我,敌人可以看作是方块,而攻击范围是圆的,如果把敌人弄成圆形进行碰撞检测那必然不准,应该检测
  • 游戏里实现碰撞检测方法

    千次阅读 2016-06-24 14:31:32
    几乎所有的3D游戏都离不开碰撞检测——无论是各物体之间的碰撞检测,还是物体与场景之间的碰撞检测。在真实世界中,你是很自然地不能穿墙而过的,所以很多人在玩各种3D游戏的时候自然而然的忽视了碰撞检测这一过程的...
  • cocos2dx碰撞检测算法

    千次阅读 2016-09-12 15:37:29
    在Cocos2d-x 3.x版本添加了对3D物体的支持后,3D物体的碰撞检测方法也随之更新,其中一种最简单的碰撞检测方法就是AABB碰撞检测。1.AABB包围盒在游戏中,为了简化物体之间的碰撞检测运算,通常会对物体创建一个规则...
  • 像素级碰撞检测

    2019-04-09 00:41:07
    那么,像素级碰撞检测,就是通过AS中自带的碰撞检测,再加上自己的逻辑算法来实现检测是否碰撞的,分为下面三个步骤: 1、通过AS自带碰撞检测两个对象是否碰撞到; 2、为两个对象的碰撞区域分别染色(假设为对象1和....
  • 1: 掌握碰撞检测的基本步骤; 2: 掌握开启碰撞检测和响应碰撞; 3: 完成道具拾取案例,理解group与groupIndex; 1: creator有碰撞检测系统 +物理碰撞系统,这个是两个独立的模块; 2: 给creator的游戏世界中的物体来进行...
  • Java游戏之碰撞检测

    千次阅读 2015-05-18 23:49:43
    Java游戏之碰撞检测在进行Java游戏开发时,我们经常会遇到碰撞检测的问题。如坦克大战中,炮弹与坦克相遇发生爆炸;守卫者游戏中,守卫者发射的箭与怪物相遇使怪物失血;打飞机游戏中,飞机发送的子弹与敌机相遇干掉...
  • Java简单游戏开发之碰撞检测

    万次阅读 多人点赞 2013-05-20 08:43:07
     不久之前在论坛上有人发贴,使用java编写的超级马里奥如何实现碰撞检测,笔者自己以前  也做过Tank大战。里面同样涉及到碰撞检测,翻翻U盘里的东西还在,什么时候也给共享出来。  这篇文章就简单游戏中的碰撞...
  • 一、解决碰撞检测穿透方法一 首先我们知道只要是跟碰撞相关的基本都是离不开刚体 Rigidbody这个组件,刚体中有一个参数适用于检测碰撞的 如下图 Collision Detection就是碰撞检测。 然而有时候开发游戏,对于高速...
  • Unity3d开发基础篇之射线碰撞检测

    千次阅读 2019-11-20 19:28:36
    Unity3d开发基础篇之射线碰撞检测介绍射线的创建和显示 介绍        在游戏开发过程中,很多地方要用到射线碰撞检测。比如:射击游戏中子弹是否击中敌人,在RPG游戏中是否捡到装备,无人驾驶...
  • canvas圆球碰撞检测

    2018-01-23 09:17:59
    本文为canvas绘制圆形碰撞检测(圆形与圆形),后期一直更新哦 x:圆横坐标,y:圆纵坐标,r:圆半径,w:浏览器宽度,h:浏览器高度 arc画圆碰撞 move移动后,碰撞浏览器边缘反弹回来,(碰撞检测)  x...
1 2 3 4 5 ... 20
收藏数 46,018
精华内容 18,407
关键字:

碰撞检测