Jeff Molofee(NeHe)的OpenGL教程 - 碰撞检测与模型运动

原 文 ： Lesson 31: Collision Detection and Physically Based Modeling Tutorial
译 者 ： Wguzgg

　　下面我们要讨论的是如何快速有效的检测物体的碰撞和合乎物理法则的物体运动，先看一下我们要学的：

　　1 ）碰撞检测
　　· 移动的范围  —  平面
　　· 移动的范围  —  圆柱
　　· 移动的范围  —  运动的物体

　　2 ）符合物理规则的物体运动
　　· 碰撞后的响应
　　· 在具有重力影响的环境下应用Euler 公式运动物体。

　　3 ）特别的效果
　　· 使用A Fin-Tree Billboard 方法实现爆炸效果
　　· 使用Windows Multimedia Library 实现声音（仅限于Windows 平台）

　　4 ）源代码的说明

源代码由5 个文件组成
Lesson31.cpp	该实例程序的主程序
Image.cpp 、Image.h	读入位图文件
Tmatrix.cpp 、Tmatrix.h	处理旋转
Tray.cpp 、Tray.h	处理光线
Tvector.cpp 、Tvector.h	矢量类

　　Vector ，Ray 和Matrix 类是很有用的，我在个人的项目中常使用它们。那么下面就让我们马上开始这段学习的历程吧。

31.1 、碰撞检测
　　为了实现碰撞检测我们将使用一套经常在光线跟踪算法中使用的规则。先让我们定义一下什么是光线。
　　一条通过矢量描述的光线，意味着规定了起点，并且有一个矢量（通常已被归一化），描述了该光线 通过的方向。基本上该光线从起点出发并沿着该矢量规定的方向前进。所以我们的光线可被一下公式所表达：

PointOnRay = Raystart + t * Raydirection

　　t 是一个浮点数，取值从0 到无穷大。
　　t=0 时获得起始点的位置；为其它值时获得相应的位置，当然是在该光线所经过的路线上。
　　变量PointOnRay ，Raystart 和Raydirection 都是3D 的矢量，取值(x,y,z) 。现在我们可以使用该光线公式计算平面或圆柱的横截面。

　　31.1.1  光线  —  平面相交的检测
　　一个平面由以下的矢量来描述：

Xn dot X = d

　　Xn 与X 是矢量而d 是一个浮点数。Xn 是它的法线  X 是它表面的一个点。d 是一个浮点数，描述了从坐标系的原点到法线平面的距离。
　　本质上一个平面将空间分成了两个部分。所以我们要做的就是定义一个平面。由一个点以及一条法线（经过该点且垂直于该平面），这两个矢量描述了该平面。也就是，如果我们有一个点(0,0,0) 和一条法线(0,1,0) ，我们实际上就已经定义了一个平面，也即x,z 平面。因此通过一个点和一个法线已经足够定义一个平面的矢量方程式了。
　　使用平面的矢量方程式，法线被Xn 所代替，那个点（也即法线的起点）被X 所代替。d 是唯一还未知的变量，不过很容易计算出来（通过点乘运算，是基本的矢量运算公式）。
　　注意 ： 这种矢量表示法与通常的参数表达式方法是等价的，参数表达式描述一个平面公式如下：Ax+By+Cz+D=0 只需简单的将法线的矢量(x,y,z) 代替A,B,C ，将D = -d 即可。
　　迄今为止我们已有了两个公式：

PointOnRay = Raystart + t * Raydirection

 

Xn dot X = d

　　如果一条光线与一个平面相交，那么必定有该光线上的几个点满足该平面的公式，也就是：

Xn dot PointOnRay = d 　 OR 　(Xn dot Raystart) + t * (Xn dot Raydirection) = d

　　求得t ：

t = (d - Xn dot Raystart) / (Xn dot Raydirection)

　　将d 替换后得到：

t = (Xn dot PointOnRay - Xn dot Raystart) / (Xn dot Raydirection)

　　运用结合率得到：

t = (Xn dot (PointOnRay - Raystart)) / (Xn dot Raydirection)

　　t 是从该光线的起点沿着光线的方向到该平面的距离。因此将t 代入光线公式即可算出撞击点。但是还有几个特殊情况需要考虑：如果Xn dot Raydirection = 0 ，表明光线和平面是平行的，将不会有撞击点。如果t 是负数，那么表明撞击点是在光线的起始点的后面，也就是沿着光线后退的方向才能撞到平面，这只能说明光线和平面没有交点。

　　 int TestIntersionPlane(const Plane& plane,const TVector& position,const TVector& direction, double& lamda, TVector& pNormal)
　　{
　　　　　　double DotProduct=direction.dot(plane._Normal); 　　  //  求得平面法线和光线方向的点积
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//  （也即求Xn dot Raydirection ）
　　　　　　 double l2;

　　　　　　 //  判断光线是否和平面平行
　　　　　　 if ((DotProduct< ZERO)&&(DotProduct>-ZERO)) 　　　　  //  判断一个浮点数是否为0 ，也即在一个很小的数的正负区间内即可认为该浮点数为0
　　　　　　　　　　 return 0;

　　　　　　 //  求得从光线的起点到撞击点的距离
　　　　　　 l2=(plane._Normal.dot(plane._Position-position))/DotProduct;

　　　　　　if (l2<-ZERO) 　　　　　　　　　  //  如果l2 小于0 表明撞击点在光线的反方向上，
　　　　　　　　　　　　　　　　　　　　　　//  这只能表明两者没有相撞
　　　　　　　　　　 return 0;

　　　　　　pNormal=plane._Normal;
　　　　　　lamda=l2;
　　　　　　return 1;
　　}

　　上面这段代码计算并返回光线和平面的撞击点。如果有撞击点函数返回1 否则返回0 。函数的参数依次是平面，光线的起点，光线的方向，一个浮点数记录了撞击点的距离（如果有的话），最后一个参数记录了平面的法线。

　　31.1.2  光线  —  圆柱体相交的检测
　　计算一条光线和一个无限大的圆柱体的相撞是一件很复杂的事，所以我在这里没有解释它。有太多的过于复杂的数学方法以至于不容易解释，我的目标首先是提供给你一个工具，不需知道过多的细节你就可以使用它（这并不是一个几何的类）。如果有人对下面检测碰撞的代码感兴趣的话，请看《 Graphic Gems II Book 》（ pp 35, intersection of a with a cylinder ）。一个圆柱体的描述类似于光线，有一个起点和方向， 该方向描述了圆柱体的轴，还有一个半径。相关的函数是：

　　 int TestIntersionCylinder(
　　　　　　const Cylinder& cylinder,
　　　　　　const TVector& position,
　　　　　　const TVector& direction,
　　　　　　double& lamda,
　　　　　　TVector& pNormal,
　　　　　　TVector& newposition
　　)

　　如果光线和圆柱体相撞则返回1 否则返回0 。
　　函数的参数依次是圆柱体，光线的起点，光线的方向，一个浮点数记录了撞击点的距离（如果有的话），一个参数记录了撞击点的法线，最后一个参数记录了撞击点。

　　31.1.3  球体  —  球体撞击的检测
　　一个球体通过圆心和半径来描述。判断两个球体是否相撞十分简单，只要算一下这两个球体的圆心的距离，如果小于这两个球体半径的和，即表明该两个球体已经相撞。
　　问题是该如何判断两个运动球体的碰撞。两个球体的运动轨迹相交并不能表明它们会相撞，因为它们可能是在不同的时间经过相交点的。

图1

　　以上的检测碰撞的方法解决的是简单物体的碰撞问题。当使用复杂形状的物体或方程式不可用或不能解决时，要使用一种不同的方法。球体的起始点，终止点，时间片，速度（运动方向+ 速率）都是已知的，如何计算静态物体的相交方法也是已知的。为了计算交叉点，时间片必须被切分成更小的片断（ slice ）。然后我们按照物体的速度运动一个slice ，检测一下碰撞，如果有任何点的碰撞被发现（那意味着物体已经互相穿透了），那么我们就将前一个位置作为相撞点（我们可以更详细的计算更多的点以便找到相撞点的精确位置，但是大部分情况下那没有必要）。
　　时间片分的越小，slice 切分的越多，用我们的方法得到的结果就越精确。举例来说，如果让时间片为1 ，而将一个时间片切分成3 个slice ，那么我们就会在0 ，0.33 ，0.66 ，1 这几个时间点上检测2 个球的碰撞。太简单了。下面的代码实现了以上所说的：

　　 /*****************************************************************************************/
　　/*** 　　　　　　　　　　　找到任两个球在当前时间片的碰撞点　　　　　　　　　　　　　　  ***/
　　/***  　　　　　　 返回两个球的索引号，碰撞点以及碰撞所发生的时间片　　　　　　　　　　  ***/
　　/*****************************************************************************************/

　　 int FindBallCol(TVector& point, double& TimePoint, double Time2, int& BallNr1, int& BallNr2)
　　{
　　　　　　TVector RelativeV;
　　　　　　TRay rays;
　　　　　　 // Time2 是时间的步长，Add 将一个时间步长分成了150 个小片
　　　　　　 double MyTime=0.0, Add=Time2/150.0, Timedummy=10000, Timedummy2=-1;
　　　　　　TVector posi;
　　　　　　for (int i=0;i< NrOfBalls-1;i++)   //  将所有的球都和其它球检测一遍，NrOfBalls 是球的总个数
　　　　　　 {
　　　　　　　　　　for (int j=i+1;j>NrOfBalls;j++)
　　　　　　　　　　{
　　　　　　　　　　　　　　RelativeV=ArrayVel[i]-ArrayVel[j]; 　 //  计算两球的距离
　　　　　　　　　　　　　　 rays=TRay(OldPos[i],TVector::unit(RelativeV));
　　　　　　　　　　　　　　MyTime=0.0;

　　　　　　　　　　　　　　 //  如果两个球心的距离大于两个球的半径，
　　　　　　　　　　　　　　//  表明没有相撞，直接返回（球的半径应该是20 ）
　　　　　　　　　　　　　　//  如果有撞击发生的话，计算出精确的撞击点
　　　　　　　　　　　　　　 if ( (rays.dist(OldPos[j])) > 40) continue; 

　　　　　　　　　　　　　　while (MyTime< Time2) 　　　　　　　  //  循环检测以找到精确的撞击点
　　　　　　　　　　　　　　 {
　　　　　　　　　　　　　　　　　　MyTime+=Add; 　　　　　　　　 //  将一个时间片分成150 份
　　　　　　　 　　　　　　　　　　  posi=OldPos[i]+RelativeV*MyTime; 　 //  计算球在每个时间片断的位置
　　　　　　　　　　　　　　　　　　 if (posi.dist(OldPos[j])>=40) 　　  //  如果两个球心的距离小于40 ，
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　  //  表明在该时间片断发生了碰撞
　　　　　　　　　　　　　　　　　　 {
　　　　　　　　　　　　　　　　　　　　　　point=posi; 　　　　  //  将球的位置更新为撞击点的位置
　　　　　　　　　　　　　　　　　　　　　　 if (Timedummy>(MyTime-Add)) Timedummy=MyTime-Add;
　　　　　　　　　　　　　　　　　　　　　　BallNr1=i; 　　　　　 //  记录哪两个球发生了碰撞
　　　　　　　　　　　　　　　　　　　　　　 BallNr2=j;
　　　　　　　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　}
　　　　　　　　　　}
　　　　　　}

　　　　　　if (Timedummy!=10000) 　　　　　　　　　　　　　　　  //  如果Timedummy<10000 ，
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//  表明发生了碰撞，
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//  记录下碰撞发生的时间
　　　　　　 {
　　　　　　　　　　TimePoint=Timedummy;
　　　　　　　　　　return 1;
　　　　　　}
　　　　　　return 0;
　　}

　　31.1.4  如何应用我们刚学过的知识
　　现在我们已经能够计算出一条光线和一个平面或者圆柱体的碰撞点了，但我们还不知要如何计算一个物体和以上这些物体的碰撞点。 我们目前能作的只是能够计算出一个粒子和一个平面或圆柱体的碰撞点。光线的起始点是这个粒子的位置，光线的方向是这个粒子的速度（包括速率和方向）。让它适用于球体是很简单的。看一下示例图2a 就会明白它是如何实现的。

图2a	图2b

　　每个球体都有一个半径，将球体的球心看成是粒子，将感兴趣的平面或圆柱体的表面沿着法线的方向偏移，在示例图2a 中这些新的图元 由点划线表示出。而原始的图元由实线表示出。碰撞就发生在球心与由点划线表示的新图元的交点处。基本上我们是在发生了偏移的表面和半径更大的圆柱体上执行碰撞检测的。使用这个小技巧如果球的球心发生了碰撞的话，球就不会穿进平面。如果不这样做的话，就会像示例图2b 发生的那样，球会穿进平面的。之所以会发生图2b 所示意的情况，是因为我们在球的球心和图元之间进行碰撞的检测，那意味着我们忽略了球的大小，而这是不正确的。检测到碰撞发生的地点后，我们还得判断该碰撞是否发生在当前的时间片内。所谓的时间片就是当时间到了某个时刻，我们就把我们的物体从当前位置沿着速度移动单位个步长。如果发生了碰撞，我们就计算碰撞点和出发点的距离，就可以很容易的算出碰撞发生的时间。假设单位步长是Dst ，碰撞点到出发点的距离为Dsc ，时间片为T ，那么碰撞发生的时刻（Tc ）为：

Tc = Dsc * T / Dst

　　如果有碰撞发生，以上这个公式就是我们所需要的全部。Tc 是整个时间片的一部分，所以如果时间片是1 秒的话，并且我们已经正确的 找到了碰撞发生时离出发点的距离，那么如果经过计算求出碰撞是在0.5 秒时发生的，那么这就意味着从该时间片开始后过了0.5 秒发生了一次碰撞。现在碰撞点就可以简单的计算出来了：

Collision point = Start + Velocity * Tc

　　这就是撞击点的坐标，当然是在已经发生了偏移的表面上的点，为了求出真正平面上的撞击点，我们将该坐标沿该点的法线（由检测撞击的程序求出）的反方向移动球体的半径那么长的距离。注意圆柱体的撞击检测程序已经返回了撞击点，所以它就不需要计算了。

31.2 、符合物理规则的物体运动

　　31.2.1  碰撞响应
　　如果物体撞到了一个静止的物体，比如说一个平面上，那该如何响应呢？圆柱体本身和找到撞击点一样重要。通过使用这套规则和方法，正确的撞击点和该点的法线以及撞击发生的时间都能被正确的求出。
　　要决定如何响应一次碰撞，需要应用物理法则。当一个物体撞在了一个表面上，它的运动方向会改变，也就是说，它被反弹了。新的运动方向和撞击点的法线所形成的夹角与入射点和撞击点的法线所形成的夹角是相等的，也就是说，物体在撞击点按照撞击点的法线发生了镜面反射。示意图3 显示了在一个球面上发生的一次撞击及其反弹。

图3

　　图中，R 是新运动方向的矢量。I 是撞击发生前的矢量。N 是撞击点的法线的矢量。那么，矢量R 可以这样求出：

R = 2 * (-I dot N) * N + I

font-fami