NeHe OpenGL第三十課：碰撞檢測

碰撞檢測:

這是一課激動的教程，你也許等待它多時了。你將學會碰撞剪裁，物理模擬太多的東西，慢慢期待吧。
?
碰撞檢測和物理模擬(作者:Dimitrios Christopoulos (christop@fhw.gr))

碰撞檢測

這是一個我遇到的最困難的題目,因為它沒有一個簡單的解決辦法.對于每一個程序都有一種檢測碰撞的方法.當然這里有一種蠻力,它適用于各種不同的應用,當它非常的費時.
我們將講述一種算法,它非常的快,簡單并易于擴展.下面我們來看看這個算法包含的內容:

1) 碰撞檢測?
移動的球-平面?
移動的球-圓柱?
移動的球-移動的球?
2) 基于物理的建模?
碰撞表示?
應用重力加速度?
3) 特殊效果?
爆炸的表示，利用互交叉的公告板形式?
聲音使用Windows聲音庫?
4) 關于代碼?
代碼被分為以下5個部分?
Lesson30.cpp?? : 主程序代碼l?
Image.cpp, Image.h : 加載圖像?
Tmatrix.cpp, Tmatrix.h : 矩陣?
Tray.cpp, Tray.h : 射線?
Tvector.cpp, Tvector.h : 向量

1) 碰撞檢測

我們使用射線來完成相關的算法，它的定義為:

射線上的點 = 射線的原點+ t * 射線的方向

t 用來描述它距離原點的位置，它的范圍是[0, 無限遠).

現在我們可以使用射線來計算它和平面以及圓柱的交點了。

射線和平面的碰撞檢測：

平面被描述為：

Xn dot X = d

Xn 是平面的法線.
X 是平面上的一個點.
d 是平面到原點的距離.

現在我們得到射線和平面的兩個方程:

PointOnRay = Raystart + t * Raydirection
Xn dot X = d

如果他們相交，則上訴方程組有解，如下所示：

Xn dot PointOnRay = d

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

解得 t:

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

t代表原點到與平面相交點的參數,把t帶回原方程我們會得到與平面的碰撞點.如果Xn*Raydirection=0。則說明它與平面平行，則將不產生碰撞。如果t為負值，則說明交點在射線的相反方向，也不會產生碰撞。
??
//判斷是否和平面相交，是則返回1，否則返回0int TestIntersionPlane(const Plane& plane,const TVector& position,const TVector& direction, double& lamda, TVector&

pNormal){
double DotProduct=direction.dot(plane._Normal);
double l2;

//判斷是否平行于平面
if ((DotProduct<ZERO)&&(DotProduct>-ZERO))?
return 0;

l2=(plane._Normal.dot(plane._Position-position))/DotProduct;

if (l2<-ZERO)?
return 0;

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

射線-圓柱的碰撞檢測

計算射線和圓柱方程組得解。??
???
int TestIntersionCylinder(const Cylinder& cylinder,const TVector& position,const TVector& direction, double& lamda, TVector& pNormal,TVector& newposition)

球-球之間的碰撞檢測

球被表示為中心和它的半徑，決定兩個球是否相交就是求出它們之間的距離是否小于它們的直徑。

在處理兩個移動的球是否相交時，有一個bug就是，當它們的移動速度太快，回出現它們相交，但在相鄰的兩步檢測不出它們是否相交的情況，如下圖所示：

有一個替代的辦法就是細分相鄰的時間片斷，如果在這之間發生了碰撞，則確定有效。我們把這個細分時間段設置為3，代碼如下：???
???
//判斷球和球是否相交，是則返回1，否則返回0int FindBallCol(TVector& point, double& TimePoint, double Time2, int& BallNr1, int& BallNr2){?TVector RelativeV;?TRay rays;?double MyTime=0.0, Add=Time2/150.0, Timedummy=10000, Timedummy2=-1;?TVector posi;??//判斷球和球是否相交?for (int i=0;i<NrOfBalls-1;i++)?{? for (int j=i+1;j<NrOfBalls;j++)? {?????? RelativeV=ArrayVel[i]-ArrayVel[j];???rays=TRay(OldPos[i],TVector::unit(RelativeV));???MyTime=0.0;
if ( (rays.dist(OldPos[j])) > 40) continue;

while (MyTime<Time2)
{
MyTime+=Add;
posi=OldPos[i]+RelativeV*MyTime;
if (posi.dist(OldPos[j])<=40) {
point=posi;
if (Timedummy>(MyTime-Add)) Timedummy=MyTime-Add;
BallNr1=i;
BallNr2=j;
break;
}

}
}

}

if (Timedummy!=10000) { TimePoint=Timedummy;
return 1;
}

return 0;
}

怎樣應用我們的知識

現在我們已經可以決定射線和平面/圓柱的交點了,如下圖所示:

當我們找到了碰撞位置后,下一步我們需要知道它是否發生在當前這一步中.如果距離碰撞點的位置小于這一步球體運動的間隔,則碰撞發生.我們使用如下的方程計算運動到碰撞時所需的時間:
Tc= Dsc*T / Dst?
接著我們知道碰撞點位置,如下面公式所示:
Collision point= Start + Velocity*Tc

2) 基于物理的模擬

碰撞反應

為了計算對于一個靜止物體的碰撞,我們需要知道以下信息:碰撞點,碰撞法線,碰撞時間.

它是基于以下物理規律的,碰撞的入射角等于反射角.如下圖所示:

R 為反射方向
I 為入射方向
N 為法線方向

反射方向有以下公式計算 :

R= 2*(-I dot N)*N + I?
??
rt2=ArrayVel[BallNr].mag();??????// 返回速度向量的模
ArrayVel[BallNr].unit();??????// 歸一化速度向量

// 計算反射向量
ArrayVel[BallNr]=TVector::unit( (normal*(2*normal.dot(-ArrayVel[BallNr]))) + ArrayVel[BallNr] );
ArrayVel[BallNr]=ArrayVel[BallNr]*rt2;?????

球體之間的碰撞

由于它很復雜，我們用下圖來說明這個原理.??

U1和U2為速度向量，我們用X_Axis表示兩個球中心連線的軸，U1X和U2X為U1和U2在這個軸上的分量。U1y和U2y為垂直于X_Axis軸的分量。M1和M2為兩個球體的分量。V1和V2為碰撞后的速度，V1x,V1y,V2x,V2y為他們的分量。

在我們的例子里，所有球的質量都相等，解得方程為，在垂直軸上的速度不變，在X_Axis軸上互相交換速度。代碼如下：
??
TVector pb1,pb2,xaxis,U1x,U1y,U2x,U2y,V1x,V1y,V2x,V2y;
double a,b;
pb1=OldPos[BallColNr1]+ArrayVel[BallColNr1]*BallTime;???// 球1的位置
pb2=OldPos[BallColNr2]+ArrayVel[BallColNr2]*BallTime;???// 球2的位置
xaxis=(pb2-pb1).unit();???????// X-Axis軸
a=xaxis.dot(ArrayVel[BallColNr1]);?????// X_Axis投影系數
U1x=xaxis*a;????????// 計算在X_Axis軸上的速度
U1y=ArrayVel[BallColNr1]-U1x; // 計算在垂直軸上的速度
xaxis=(pb1-pb2).unit();???????
b=xaxis.dot(ArrayVel[BallColNr2]);?????
U2x=xaxis*b;????????
U2y=ArrayVel[BallColNr2]-U2x;
V1x=(U1x+U2x-(U1x-U2x))*0.5;??????// 計算新的速度
V2x=(U1x+U2x-(U2x-U1x))*0.5;
V1y=U1y;
V2y=U2y;
for (j=0;j<NrOfBalls;j++)??????// 更新所有球的位置
ArrayPos[j]=OldPos[j]+ArrayVel[j]*BallTime;
ArrayVel[BallColNr1]=V1x+V1y;??????// 設置新的速度
ArrayVel[BallColNr2]=V2x+V2y;??????
???
萬有引力的模擬

我們使用歐拉方程來模擬萬有引力，如下所示：?
Velocity_New = Velovity_Old + Acceleration*TimeStep
Position_New = Position_Old + Velocity_New*TimeStep

在每次模擬中，我們用上面公式計算的速度取代舊的速度

3) 特殊效果

爆炸

最好的表示爆炸效果的就是使用兩個互相垂直的平面，并使用alpha混合在窗口中顯示它們。接著讓alpha變為0，設定爆炸效果不可見。代碼如下所示：??
???
// 渲染/混合爆炸效果
glEnable(GL_BLEND);???????// 使用混合
glDepthMask(GL_FALSE);???????// 禁用深度緩存
glBindTexture(GL_TEXTURE_2D, texture[1]);????// 設置紋理
for(i=0; i<20; i++)???????// 渲染20個爆炸效果
{
?if(ExplosionArray[i]._Alpha>=0)
?{
??glPushMatrix();
??ExplosionArray[i]._Alpha-=0.01f;???// 設置alpha
??ExplosionArray[i]._Scale+=0.03f;???// 設置縮放
??// 設置顏色
??glColor4f(1,1,0,ExplosionArray[i]._Alpha);??
??glScalef(ExplosionArray[i]._Scale,ExplosionArray[i]._Scale,ExplosionArray[i]._Scale);
??// 設置位置
??glTranslatef((float)ExplosionArray[i]._Position.X()/ExplosionArray[i]._Scale,
???(float)ExplosionArray[i]._Position.Y()/ExplosionArray[i]._Scale,
???(float)ExplosionArray[i]._Position.Z()/ExplosionArray[i]._Scale);
??glCallList(dlist);?????// 調用顯示列表繪制爆炸效果
??glPopMatrix();
?}
}

聲音

在Windows下我們簡單的調用PlaySound()函數播放聲音。

4) 代碼的流程

如果你成功的讀完了理論部分，在你開始運行程序并播放聲音以前。我們將用偽代碼向你介紹一些整個流程，以便你能成功的看懂代碼。??
???
While (Timestep!=0)
{
?對每一個球
?{
??計算最近的與平面碰撞的位置;
??計算最近的與圓柱碰撞的位置;
??如果碰撞發生，則保存并替換最近的碰撞點;
?}
?檢測各個球之間的碰撞;
?如果碰撞發生，則保存并替換最近的碰撞點;

?If (碰撞發生)
?{
??移動所有的球道碰撞點的時間;
??(We already have computed the point, normal and collision time.)
??計算碰撞后的效果;
??Timestep-=CollisonTime;
?}
?else
??移動所有的球體一步
}

下面是對上面偽代碼的實現：
??
//模擬函數，計算碰撞檢測和物理模擬void idle(){? double rt,rt2,rt4,lamda=10000;? TVector norm,uveloc;? TVector normal,point,time;? double RestTime,BallTime;? TVector Pos2;? int BallNr=0,dummy=0,BallColNr1,BallColNr2;? TVector Nc;
//如果沒有鎖定到球上，旋轉攝像機
if (!hook_toball1)
{
camera_rotation+=0.1f;
if (camera_rotation>360)
camera_rotation=0;
}

RestTime=Time;
lamda=1000;

//計算重力加速度
for (int j=0;j<NrOfBalls;j++)
ArrayVel[j]+=accel*RestTime;

//如果在一步的模擬時間內(如果來不及計算，則跳過幾步)
while (RestTime>ZERO)
{
lamda=10000;

//對于每個球，找到它們最近的碰撞點
for (int i=0;i<NrOfBalls;i++)
{
//計算新的位置和移動的距離
OldPos[i]=ArrayPos[i];
TVector::unit(ArrayVel[i],uveloc);
ArrayPos[i]=ArrayPos[i]+ArrayVel[i]*RestTime;
rt2=OldPos[i].dist(ArrayPos[i]);

//測試是否和墻面碰撞
if (TestIntersionPlane(pl1,OldPos[i],uveloc,rt,norm))
{?
//計算碰撞的時間
rt4=rt*RestTime/rt2;

//如果小于當前保存的碰撞時間，則更新它
if (rt4<=lamda)
{?
if (rt4<=RestTime+ZERO)
if (! ((rt<=ZERO)&&(uveloc.dot(norm)>ZERO)) )
{
normal=norm;
point=OldPos[i]+uveloc*rt;
lamda=rt4;
BallNr=i;
}
}
}

if (TestIntersionPlane(pl2,OldPos[i],uveloc,rt,norm))
{
rt4=rt*RestTime/rt2;

if (rt4<=lamda)
{?
if (rt4<=RestTime+ZERO)
if (! ((rt<=ZERO)&&(uveloc.dot(norm)>ZERO)) )
{
normal=norm;
point=OldPos[i]+uveloc*rt;
lamda=rt4;
BallNr=i;
dummy=1;
}
}

}

if (TestIntersionPlane(pl3,OldPos[i],uveloc,rt,norm))
{
rt4=rt*RestTime/rt2;

if (rt4<=lamda)
{?
if (rt4<=RestTime+ZERO)
if (! ((rt<=ZERO)&&(uveloc.dot(norm)>ZERO)) )
{
normal=norm;
point=OldPos[i]+uveloc*rt;
lamda=rt4;
BallNr=i;
}
}
}

if (TestIntersionPlane(pl4,OldPos[i],uveloc,rt,norm))
{
rt4=rt*RestTime/rt2;

if (rt4<=lamda)
{?
if (rt4<=RestTime+ZERO)
if (! ((rt<=ZERO)&&(uveloc.dot(norm)>ZERO)) )
{
normal=norm;
point=OldPos[i]+uveloc*rt;
lamda=rt4;
BallNr=i;
}
}
}

if (TestIntersionPlane(pl5,OldPos[i],uveloc,rt,norm))
{
rt4=rt*RestTime/rt2;

if (rt4<=lamda)
{?
if (rt4<=RestTime+ZERO)
if (! ((rt<=ZERO)&&(uveloc.dot(norm)>ZERO)) )
{
normal=norm;
point=OldPos[i]+uveloc*rt;
lamda=rt4;
BallNr=i;
}
}
}

//測試是否與三個圓柱相碰
if (TestIntersionCylinder(cyl1,OldPos[i],uveloc,rt,norm,Nc))
{
rt4=rt*RestTime/rt2;

if (rt4<=lamda)
{?
if (rt4<=RestTime+ZERO)
if (! ((rt<=ZERO)&&(uveloc.dot(norm)>ZERO)) )
{
normal=norm;
point=Nc;
lamda=rt4;
BallNr=i;
}
}

}
if (TestIntersionCylinder(cyl2,OldPos[i],uveloc,rt,norm,Nc))
{
rt4=rt*RestTime/rt2;

if (rt4<=lamda)
{?
if (rt4<=RestTime+ZERO)
if (! ((rt<=ZERO)&&(uveloc.dot(norm)>ZERO)) )
{
normal=norm;
point=Nc;
lamda=rt4;
BallNr=i;
}
}

}
if (TestIntersionCylinder(cyl3,OldPos[i],uveloc,rt,norm,Nc))
{
rt4=rt*RestTime/rt2;

if (rt4<=lamda)
{?
if (rt4<=RestTime+ZERO)
if (! ((rt<=ZERO)&&(uveloc.dot(norm)>ZERO)) )
{
normal=norm;
point=Nc;
lamda=rt4;
BallNr=i;
}
}

}
}

//計算每個球之間的碰撞，如果碰撞時間小于與上面的碰撞，則替換它們
if (FindBallCol(Pos2,BallTime,RestTime,BallColNr1,BallColNr2))
{
if (sounds)
PlaySound("Data/Explode.wav",NULL,SND_FILENAME|SND_ASYNC);

if ( (lamda==10000) || (lamda>BallTime) )
{
RestTime=RestTime-BallTime;

TVector pb1,pb2,xaxis,U1x,U1y,U2x,U2y,V1x,V1y,V2x,V2y;
double a,b;

pb1=OldPos[BallColNr1]+ArrayVel[BallColNr1]*BallTime;
pb2=OldPos[BallColNr2]+ArrayVel[BallColNr2]*BallTime;
xaxis=(pb2-pb1).unit();

a=xaxis.dot(ArrayVel[BallColNr1]);
U1x=xaxis*a;
U1y=ArrayVel[BallColNr1]-U1x;

xaxis=(pb1-pb2).unit();
b=xaxis.dot(ArrayVel[BallColNr2]);
U2x=xaxis*b;
U2y=ArrayVel[BallColNr2]-U2x;

V1x=(U1x+U2x-(U1x-U2x))*0.5;
V2x=(U1x+U2x-(U2x-U1x))*0.5;
V1y=U1y;
V2y=U2y;

for (j=0;j<NrOfBalls;j++)
ArrayPos[j]=OldPos[j]+ArrayVel[j]*BallTime;

ArrayVel[BallColNr1]=V1x+V1y;
ArrayVel[BallColNr2]=V2x+V2y;

//Update explosion array
for(j=0;j<20;j++)
{
if (ExplosionArray[j]._Alpha<=0)
{
ExplosionArray[j]._Alpha=1;
ExplosionArray[j]._Position=ArrayPos[BallColNr1];
ExplosionArray[j]._Scale=1;
break;
}
}

continue;
}
}

//最后的測試，替換下次碰撞的時間，并更新爆炸效果的數組
if (lamda!=10000)
{?
?RestTime-=lamda;

?for (j=0;j<NrOfBalls;j++)
??ArrayPos[j]=OldPos[j]+ArrayVel[j]*lamda;

?rt2=ArrayVel[BallNr].mag();
?ArrayVel[BallNr].unit();
?ArrayVel[BallNr]=TVector::unit( (normal*(2*normal.dot(-ArrayVel[BallNr]))) + ArrayVel[BallNr] );
?ArrayVel[BallNr]=ArrayVel[BallNr]*rt2;

?for(j=0;j<20;j++)
?{
??if (ExplosionArray[j]._Alpha<=0)
??{
???ExplosionArray[j]._Alpha=1;
???ExplosionArray[j]._Position=point;
???ExplosionArray[j]._Scale=1;
???break;
??}
?}
}
else
?RestTime=0;
}
}
原文及其個版本源代碼下載：

http://nehe.gamedev.net/data/lessons/lesson.asp?lesson=30