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

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

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

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

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

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

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