分页: 1 / 1

Quake中的碰撞检测

帖子发表于 : 2017年 12月 5日 17:25
awakening3d
Quake的场景主体结构由凸多面体(代码里的brush)搭建而成,凸多面体所有的面把空间天生的bsp分割,检测上简单高效。比如判断一个点是否在多面体内部(代码里叫solid),只要检测点是否在所有面的内侧就行了。有了简单的场景结构,Quake里物理碰撞检测极其高效。首先运动对象的形状由一个box代替,然后由一个 trace() 函数追踪与场景的碰撞,输入运动的 起始origin 与 结束end,返回真正能走的距离(fraction: 0~1, 0表示走不动,1表示走完全程,其他值表示走到中途碰撞了)。返回信息还包括发生碰撞的平面(plane),对象等,具体可看 trace_t 结构。

有了 trace 函数,我们看下核心的移动检测函数:
(该函数在代码里还有另一个版本SV_FlyMove,稍有差异,有兴趣可比较下)
代码: 全选
#define   MIN_STEP_NORMAL   0.7      // can't step up onto very steep slopes
#define   MAX_CLIP_PLANES   5
void PM_StepSlideMove_ (void)
{
   int         bumpcount, numbumps;
   vec3_t      dir;
   float      d;
   int         numplanes;
   vec3_t      planes[MAX_CLIP_PLANES];
   vec3_t      primal_velocity;
   int         i, j;
   trace_t   trace;
   vec3_t      end;
   float      time_left;
   
   numbumps = 4;
   
   VectorCopy (pml.velocity, primal_velocity);
   numplanes = 0;
   
   time_left = pml.frametime;

   for (bumpcount=0 ; bumpcount<numbumps ; bumpcount++) // 这个循环里,碰到某个面,则从碰撞点反弹接着走,但最多反弹numbumps次
   {
      for (i=0 ; i<3 ; i++)
         end[i] = pml.origin[i] + time_left * pml.velocity[i]; // 计算结束点

      trace = pm->trace (pml.origin, pm->mins, pm->maxs, end); // 由给定的box与起始结束点,尝试在场景中移动

      if (trace.allsolid) //全程在实心区,走不动
      {   // entity is trapped in another solid
         pml.velocity[2] = 0;   // don't build up falling damage
         return;
      }

      if (trace.fraction > 0) // fraction大于零,说明往前走了一段
      {   // actually covered some distance
         VectorCopy (trace.endpos, pml.origin); // 把碰撞点当作新的起始点,继续尝试往前走
         numplanes = 0; // 碰撞面数清零
      }

      if (trace.fraction == 1) // fraction等于1,说明走完全程了
          break;      // moved the entire distance

      // save entity for contact
      if (pm->numtouch < MAXTOUCH && trace.ent)
      {
         pm->touchents[pm->numtouch] = trace.ent;
         pm->numtouch++;
      }
      
      time_left -= time_left * trace.fraction; // 计算剩余的运行时间

      // slide along this plane
      if (numplanes >= MAX_CLIP_PLANES)
      {   // this shouldn't really happen
         VectorCopy (vec3_origin, pml.velocity);
         break;
      }

      VectorCopy (trace.plane.normal, planes[numplanes]); // 记录发生碰撞的平面
      numplanes++;


//
// modify original_velocity so it parallels all of the clip planes
//
// 这个循环处理与速度向量与碰撞面间的反弹,如果numplanes等于1,那么是前面刚发生了一次碰撞,只要简单计算新的速度方向
// 如果numplanes大于1,说明已经走不动了,那么就尝试找一新的方向去走
      for (i=0 ; i<numplanes ; i++)
      {
         PM_ClipVelocity (pml.velocity, planes[i], pml.velocity, 1.01); // 根据入射向量与平面计算反射向量
         for (j=0 ; j<numplanes ; j++) // 检查反射向量是否与所有碰撞面相对
            if (j != i)
            {
               if (DotProduct (pml.velocity, planes[j]) < 0) // 速度与面反向
                  break;   // not ok
            }
         if (j == numplanes) // 说明前面走完了循环,那么新的速度方向与所有碰撞面都是同向的,就是远离平面
            break;
      }
      
      if (i != numplanes) // 说明前面循环里找到了可用的新速度方向
      {   // go along this plane
      }
      else  // 没找到合适的新方向,
      {   // go along the crease 尝试沿着平面接缝方向走
         if (numplanes != 2) // numplanes > 2,碰撞面超过两个,那么原地停止
         {
//            Con_Printf ("clip velocity, numplanes == %i\n",numplanes);
            VectorCopy (vec3_origin, pml.velocity);
            break;
         }
         CrossProduct (planes[0], planes[1], dir); // 计算两个碰撞面的接缝方向
         d = DotProduct (dir, pml.velocity); // 根据速度与接缝方向的夹角计算新速度大小
         VectorScale (dir, d, pml.velocity); // 得到沿接缝方向的新速度
      }
      //
      // if velocity is against the original velocity, stop dead
      // to avoid tiny occilations in sloping corners
      //
      if (DotProduct (pml.velocity, primal_velocity) <= 0) // 如果新速度与最初的速度反向,那么停止运动,以避免在某些角落里来回反复震荡
      {
         VectorCopy (vec3_origin, pml.velocity);
         break;
      }
   }

   if (pm->s.pm_time)
   {
      VectorCopy (primal_velocity, pml.velocity);
   }
}


我们可以看到,quake里的物理碰撞检测是极其高效的,与物理库的运算量简直不在一个数量级(当然没那么精确与全面,但有些游戏里物理是不需要太精确的),带来的结果就是在场景里走动平滑流畅,碰到障碍自动换方向滑动,这种走动的流畅感是quake系列最特色之一,对设计自己的游戏与引擎都有借鉴之处。