復(fù)合圓錐體的碰撞檢測.pdf

1、碰撞檢測問題是計算機(jī)仿真、CAD、機(jī)器人中的一個基本問題，主要用于提高虛擬場景的真實(shí)感或進(jìn)行機(jī)器人的路徑規(guī)劃等。不同的碰撞檢測基于不同的應(yīng)用，因此提供的信息也不同。有的應(yīng)用需要碰撞檢測算法給出兩物體沿各自運(yùn)動路徑運(yùn)動過程中是否發(fā)生碰撞，有的應(yīng)用則需要碰撞檢測算法不僅給出兩物體運(yùn)動過程中是否碰撞，還需要提供距離信息，即兩物體發(fā)生碰撞時它們之間的最短穿刺距離，或者兩個在運(yùn)動路徑上沒有碰撞的物體，它們之間的最短分離距離。 目前已有很多

2、種碰撞檢測方法，但主要分為兩大類：一類是離散的碰撞檢測，如基于計算幾何的方法、基于分離平面的方法、基于圖形硬件的方法等：一類是連續(xù)碰撞檢測，如掃描卷方法、基于對偶和Minkowski和的方法、代數(shù)方法等。離散的碰撞檢測方法是對兩運(yùn)動物體在時間軸上采樣，在每個采樣時刻判斷兩靜態(tài)物體是否碰撞。在離散的碰撞檢測方法中，如果物體運(yùn)動速度很快或者物體很小，有可能會檢測不到取樣時間間隔之內(nèi)發(fā)生的碰撞；縮短采樣的時間間隔可以提高精度，但是會降低效率。

3、連續(xù)碰撞檢測的方法對物體的運(yùn)動過程進(jìn)行建模，構(gòu)造出一條連續(xù)的路徑，基于路徑判斷物體間的碰撞情況。本文提出了兩個算法，一個是研究利用代數(shù)方法進(jìn)行連續(xù)的碰撞檢測，對兩個運(yùn)動的復(fù)合圓錐體進(jìn)行碰撞檢測，另外一個是用幾何方法計算兩個運(yùn)動的復(fù)合圓錐體的最近距離并進(jìn)行碰撞檢測。 代數(shù)方法的求解過程是把兩個物體靜止時的碰撞條件表達(dá)成一個代數(shù)條件，然后通過對物體的運(yùn)動進(jìn)行建模，將物體的運(yùn)動表示成關(guān)于時間的函數(shù)，根據(jù)靜止時碰撞的代數(shù)條件和運(yùn)動函數(shù)將

4、兩個運(yùn)動物體的碰撞條件表示成關(guān)于時間的代數(shù)條件，通過求解這個代數(shù)條件得到兩個運(yùn)動物體的碰撞時間。 代數(shù)法可以給出碰撞點(diǎn)的位置信息和發(fā)生碰撞的時間等，但是當(dāng)兩物體不發(fā)生碰撞時無法給出最近距離信息，也就是在這一段路徑下兩物體何時距離最近。計算兩個物體之間的最近距離在很多領(lǐng)域里有重要的應(yīng)用，如機(jī)器人技術(shù)，CAD/CAM，計算機(jī)圖形學(xué)等。在機(jī)器人路徑規(guī)劃中，計算相互作用力和補(bǔ)償函數(shù)都需要距離信息。在計算機(jī)圖形學(xué)中，距離信息對于碰撞檢測和

5、動態(tài)仿真也是非常重要的。已經(jīng)有很多方法來計算兩個多面體之間的距離，對于一般形狀的物體，這些方法是用多個多面體來近似模擬，多面體數(shù)量很多時就需要很多存儲空間，而且難以滿足實(shí)時的要求。有一些方法是直接考慮兩個曲面是否相交，如果相交，則它們之間的距離為零。也有文章直接計算曲面的最近距離[2][3]，他們利用了這樣一個幾何性質(zhì)：兩個曲面上距離最近的兩個點(diǎn)，它們的法線方向互相平行，這可以稱為幾何方法，這些方法最后都需要解一個高次方程或方程組，因而

6、只能求靜止的兩個曲面的距離，對于運(yùn)動情況則采用采樣的方法，這可能會引起誤差。在這篇文章中我們提出了一種用幾何的方法計算兩個運(yùn)動的復(fù)合圓錐體的最近距離的方法，把最近距離看作隨時間變化的連續(xù)函數(shù)，當(dāng)圓錐體運(yùn)動的路徑已知時，該方法不僅可以計算每個時刻兩圓錐體的距離，還可以計算出它們在整個運(yùn)動過程中的最近距離。 本文主要研究內(nèi)容有：利用有理運(yùn)動表示物體在三維空間中的運(yùn)動：通過對控制點(diǎn)處的動力學(xué)鏡像進(jìn)行插值計算得到物體的運(yùn)動方程；提出兩個