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

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

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

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

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

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

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