三人行必有我师焉,择其善者而从之,其不善者而改之
三人行必有我师焉,择其善者而从之,其不善者而改之
三人行必有我师焉,择其善者而从之,其不善者而改之
三人行必有我师焉,择其善者而从之,其不善者而改之
三人行必有我师焉,择其善者而从之,其不善者而改之

浅析圆形物体的碰撞检测及应用
作者:Neoxone    发表时间: 2011年03月16号,星期三     阅读:10,889 次

物体的碰撞检测是游戏动画中常涉及的内容,当然我没做过游戏,只是最近接触canvas比较多,也有不少热衷html5的canvas的人提起了这个碰撞检测,所以试着拿网上一位大牛的canvas检测算法做些分析注释。
先引用些链接(看来我要形成这个习惯了):
重力版google:http://mrdoob.com/projects/chromeexperiments/google_gravity/——非规则物体的碰撞。
可融性水滴:http://hakim.se/experiments/html5/blob/03/——一个物体由多个点连接构成。

本文涉及的一个碰撞检测方法是针对于圆形物体的。显然这是比较有规律可循的,但也不要小看圆形物体的碰撞检测,一些非规则物体也可以包围球的形式使用圆形检测来检测。
代码来自:http://www.benjoffe.com/es/code/demos/collide/
本文做了一些中文翻译,并会稍加分析。

    // Coliding Discs experiment
  1. // Copyright Benjamin Joffe, 2010
  2. // 中文注释:ONEBOYS >> http://www.cssass.com
  3.  
  4.     var canvas = document.getElementById('balls');
  5.     var ctx = canvas.getContext('2d');
  6.     var co = [];
  7.     var starter = Math.random()*9 >> 0; //白球序号(随机值用右移位实现去尾取整)
  8.     
  9.     for (var i=0; i<9; i++)
  10.     {
  11.         co[i] = {  //折行排列(x,y)
  12.             x: (760/3)*(0.5+i%3),         
  13.             y: (760/3)*(0.5+((i/3)>>0)),   
  14.             r: 2*(i*2+15),             
  15. c: starter==i ? '#fff' : '#000'
  16.         };
  17.         // 随机速度(保证向量长度为1)
  18.         co[i].vx = 1-2*Math.random(); 
  19.         co[i].vy = Math.sqrt(1-co[i].vx*co[i].vx) * ( Math.random() < 0.5 ? -1 : 1 );
  20.         
  21.         // 起始阶段除白球外其他球保持静止。半径越小,i值越大,速度越大。
  22.         co[i].vx *= i==starter ? 200/co[i].r : 0;
  23.         co[i].vy *= i==starter ? 200/co[i].r : 0;
  24.     }
  25.     
  26.     function draw()
  27.     {     
  28.         ctx.fillStyle='rgba(220,220,220,0.5)';
  29.         ctx.fillRect(0,0,canvas.width, canvas.height); //涂白清屏(带透明度)
  30.         for (i=0; i<co.length; i++)
  31.         {
  32. ctx.fillStyle=co[i].c;
  33.             ctx.beginPath();
  34.             ctx.moveTo(co[i].x+co[i].r, co[i].y);
  35.             ctx.arc(co[i].x, co[i].y, co[i].r, 0, Math.PI*2, true);
  36.             ctx.fill();
  37.         }
  38.     }
  39.     
  40.     function move()
  41.     {
  42.         var total_time_left = 5;
  43.         var t=0;
  44.         var col_index; // 肇事球
  45.         var col_index2 // 被撞球
  46.         
  47.         var col_time; // 距离发生碰撞的时间
  48.         var ball_time; // 碰撞倒计时
  49.         var temp;
  50.         
  51.         var i, j, test_method;
  52.         var col_method; //碰撞方式
  53.  
  54.         while (true)
  55.         {
  56.         
  57.             col_index = -1; // choose an invalid index initially
  58.             col_time = total_time_left;
  59.             
  60.             // this loop finds the ball that will collide first
  61.             for (i=0; i<co.length; i++)
  62.             {
  63.                 // (god forbid) 若发生了灵异现象,超出了屏幕,立即反向。
  64.                 if (co[i].vx < 0 && co[i].x < co[i].r || co[i].vx > 0 && co[i].x + co[i].r > canvas.width)
  65.                 {
  66.                     co[i].vx *= -1;
  67.                     continue;
  68.                 }
  69.           
  70.                 if (co[i].vy < 0 && co[i].y < co[i].r || co[i].vy > 0 && co[i].y + co[i].r > canvas.height)
  71.                 {
  72.                     co[i].vy *= -1;
  73.                     continue;
  74.                 }
  75.                 
  76.                 // now for the real collision checks
  77.             
  78.                 // 球与墙之间检测
  79.                 for (test_method = 0; test_method < 4; test_method++ )
  80.                 {
  81.                     switch (test_method)
  82.                     {
  83.                         case 0 :
  84.                             ball_time = (co[i].r - co[i].x) / co[i].vx; //球与左壁发生碰撞的倒计时
  85.                             break;
  86.                         case 1 :
  87.                             ball_time = (co[i].r - co[i].y) / co[i].vy; // top wall
  88.                             break;
  89.                         case 2 :
  90.                             ball_time = (canvas.width - co[i].r - co[i].x) / co[i].vx; // right wall
  91.                             break;
  92.                         case 3 :
  93.                             ball_time = (canvas.height - co[i].r - co[i].y) / co[i].vy; // bottom wall
  94.                             break;
  95.                     }
  96.                     if (ball_time > 0 && ball_time < col_time) //碰撞时间为正值,且小于之前算出的碰撞时间(求出最迫切的碰撞)。
  97.                     {
  98.                         col_time = ball_time;
  99.                         col_index = i;
  100.                         col_method = test_method;
  101.                     }
  102.                 }
  103.                                 
  104.                 // 球球之间检测(检测第i球与后面所有球)
  105.                 for (j = i+1; j < co.length; j++)
  106.                 {
  107.                     ball_time = check_collision(co[i], co[j]);  /* **球球检测算法** */
  108.                     if (ball_time > 0 && ball_time < col_time)
  109.                     {
  110.                         col_method = 5;
  111.                         col_time = ball_time;
  112.                         col_index = i;
  113.                         col_index2 = j;
  114.                     }
  115.                 }
  116.             }
  117.             
  118.             // 增加位移
  119.             for (i=0; i<co.length; i++)
  120.             {
  121.                 co[i].x += col_time * co[i].vx;
  122.                 co[i].y += col_time * co[i].vy;
  123.             }
  124.             
  125.             if (col_index == -1) break; // 如无碰撞,退出循环
  126.             
  127.             // 撞到屏幕,反向
  128.             if (col_method == 0 || col_method == 2) // side walls
  129.             {
  130.                 co[col_index].vx*=-1;
  131.             }
  132.             if (col_method == 1 || col_method == 3) // top and bottom walls
  133.             {
  134.                 co[col_index].vy*=-1;
  135.             }
  136. //球球相撞
  137.             if (col_method == 5)
  138.             {
  139.                 apply_collision(co[col_index], co[col_index2]); /* ** 球球碰撞后果 ** */
  140.             }
  141.             total_time_left -= col_time;
  142.         }
  143.     }
  144.     
  145.     // 球球相撞检测
  146.      function check_collision(b1, b2){ //返回当b1,b2接触所需要的时间。
  147. var a = b1.x - b2.x,   
  148.     b = b1.vx - b2.vx, 
  149.     c = b1.y - b2.y,   
  150.     d = b1.vy - b2.vy;
  151. // I probably shouldn't have crushed the following logic into one line, makes it just a wee bit unreadable 作者在此处做了一些代码混淆。下面3行是我重写的。
  152. //return b==0&&d==0||(c=(b=2*(a*b+c*d)+0*(d=b*b+d*d))*b-4*d*(a*a+c*c-(c=b1.r+b2.r)*c))<0?-1:(-b-Math.sqrt(c))/(2*d);
  153. if(b==0&&d==0 ) return -1;
  154. var p=(a*b+c*d)/(b*b+d*d);
  155. return -p-Math.sqrt(((b1.r+b2.r)*(b1.r+b2.r)-(a*a+c*c))/(b*b+d*d)+p*p);
  156. }
  157.     
  158.     // 球球相撞处理
  159.     function apply_collision(b1, b2){ //b1,b2已接触
  160.         var
  161.             a = (b2.r * b2.r) / (b1.r * b1.r) , //半径的平方比(反映质量比)
  162.             b = (b1.y - b2.y) / (b1.x - b2.x) , //球心连线构成的正切值
  163.             c = 2*( (b1.vx - b2.vx) +b* ( b1.vy - b2.vy ) )/((1+b*b)*(1+a)); //改变的速度发生在球心连线上。
  164.         b2.vx += c;
  165.         b2.vy += c*b;
  166.         b1.vx -= c*a;
  167.         b1.vy -= c*a*b;
  168.     }
  169.     
  170.     setInterval(function()
  171.     {
  172.         move();
  173.         draw();
  174.     },30);
  175.     draw();

下面简略说一下两球之间的碰撞检测方法check_collision:
当前位置两球的x方向距离为a,y方向距离为c,两球x方向上的相对速度为b,y方向上为d。
假设经过时间t之后,两球相撞。
此时,两球的距离为(r1+r2),而在x方向上的距离应为(a+bt),y方向上距离为(c+dt)
根据直角三角形性质:(a+bt)^2+(c+dt)^2=(r1+r2)^2
经过数学换算可得:t=-(a*b+c*d)/(b*b+d*d)-Math.sqrt(((b1.r+b2.r)*(b1.r+b2.r)-(a*a+c*c))/(b*b+d*d)+((a*b+c*d)/(b*b+d*d))*((a*b+c*d)/(b*b+d*d)))
如果你不会换算,可以看看这个链接:http://www.wolframalpha.com/input/?i=(a%2Bb*t)^2%2B(c%2Bd*t)^2%3D(r1%2Br2)^2

碰撞检测符合碰撞条件之后之后,就是碰撞反弹了apply_collision。
碰撞问题其实在高中物理中,已经有所学习了。我们要解的这个问题就是一个弹性斜碰撞的问题。
这种碰撞符合的定律是:动量守恒(碰撞前后矢量和相等)和动能守恒(碰撞后起码不增加)定律。

今日就此搁笔,明天起请了年假,回来后可能的话此文再做更新,本来还准备在写个demo来着的。
回见,各位。

标签: , ,

9 条评论 发表在“浅析圆形物体的碰撞检测及应用”上

  1. ):16:( 好多代码啊,我淹死了。。。。

    回复

  2. 我喜欢这里。。。还能运行起来看看的

    回复

  3. ABC 说:

    ):14:( 那个网站挺不错的

    回复

  4. youwenda 说:

    @ONEBOYS : 能否给详细解释下碰撞之后也就是apply_collision 函数中公式是怎么来的么,没想明白啊!
    这里多谢啦。。。

    回复

    ONEBOYS 回复:

    @youwenda, 上面提到,这是一个完全弹性斜碰的问题。
    我们知道完全弹性正碰问题,需要用到动能守恒和动量守恒定理,两(等)式联立可以得到最终速度,(上面是先得到差速度c)。
    斜碰与正碰的差别在于,在球连线上的动量守恒,所以需要用的两球连线与坐标系构成的角度的正切值,进行分解。

    回复

    ONEBOYS 回复:

    @ONEBOYS, 我仔细列了一下式子,的确很难得出c=2*( (b1.vx – b2.vx) +b* ( b1.vy – b2.vy ) )/((1+b*b)*(1+a));这条结果。推荐看下Flash.ActionScript.3.0动画教程这本书里的“两个轴上的动量守恒”这一节,那里也有弹性斜碰的解法。

    回复

  5. yourtone 说:

    ):8:( 膜拜!我在怀疑,会不会有一个时刻,他们会停下来?

    回复

  6. lsg2409 说:

    很棒,看了看,有点疑惑,while(true)这个循环起什么作用呢?

    回复

留下回复

):9:( ):8:( ):7:( ):6:( ):5:( ):4:( ):3:( ):2:( ):20:( ):1:( ):19:( ):18:( ):17:( ):16:( ):15:( ):14:( ):13:( ):12:( ):11:( ):10:(