利用代數(shù)方法求解碰撞檢測問題.pdf

1、碰撞檢測問題是計(jì)算機(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、種碰撞檢測方法，但主要分為兩大類：一類是離散的碰撞檢測，如基于計(jì)算幾何的方法、基于分離平面的方法、基于圖形硬件的方法等：一類是連續(xù)碰撞檢測，如掃描卷方法、基于對偶和Minkowski和的方法、基于KDS (Kinetic Data Structure) 的方法、代數(shù)方法等。離散的碰撞檢測方法是對兩運(yùn)動物體在時間軸上采樣，在每個采樣時刻判斷兩靜態(tài)物體是否碰撞。在離散的碰撞檢測方法中，如果物體運(yùn)動速度很快或者物體很小，有可能會檢測不到取樣時

3、間間隔之內(nèi)發(fā)生的碰撞；縮短采樣的時間間隔可以提高精度，但是會降低效率。連續(xù)碰撞檢測的方法對物體的運(yùn)動過程進(jìn)行建模，構(gòu)造出一條連續(xù)的路徑，基于路徑判斷物體間的碰撞情況。本文研究的是利用代數(shù)方法進(jìn)行連續(xù)的碰撞檢測，提出了兩個算法，一個是對兩個運(yùn)動的平面多邊形進(jìn)行碰撞檢測，另外一個是對兩個運(yùn)動的LSS (Linearly Swept Spheres) 進(jìn)行碰撞檢測以及距離信息的計(jì)算。 代數(shù)方法的求解過程是把兩個物體靜止時的碰撞條件表達(dá)

4、成一個代數(shù)條件，然后通過對物體的運(yùn)動進(jìn)行建模，將物體的運(yùn)動表示成關(guān)于時間的函數(shù)，根據(jù)靜止時碰撞的代數(shù)條件和運(yùn)動函數(shù)將兩個運(yùn)動物體的碰撞條件表示成關(guān)于時間的代數(shù)條件，通過求解這個代數(shù)條件得到兩個運(yùn)動物體的碰撞時間。 已有的利用代數(shù)方法求解碰撞檢測問題是針對橢圓盤和橢球的。平面上運(yùn)動的橢圓盤的碰撞檢測，不能直接用來解決曲線多邊形的碰撞檢測問題。橢球作為一種包圍體對某些物體的包圍不夠緊，某些物體，如人的手臂，用L,SS包圍體進(jìn)行包圍效

5、果會更好。 已有的對兩個運(yùn)動的平面多邊形的碰撞檢測，如基于圖形硬件的方法和基于KDS的方法，是針對直線段多邊形的，其中基于圖形硬件的方法使用的是重復(fù)檢測方法，而基于KDS的方法在解決一般的有理運(yùn)動時需要將運(yùn)動在各個方向上進(jìn)行分解，增加了算法的復(fù)雜性。 本文主要研究內(nèi)容有：用二次曲線段集合表示曲線多邊形；利用有理運(yùn)動表示二維和三維空間中的運(yùn)動；通過對控制點(diǎn)處的動力學(xué)鏡像進(jìn)行插值計(jì)算得到物體的運(yùn)動方程；提出兩段二次曲線段在有

6、理運(yùn)動下的碰撞條件；提出直接利用曲線邊進(jìn)行平面多邊形碰撞檢測的算法；利用多項(xiàng)式的Bemstein形式進(jìn)行求解；利用包圍盒技術(shù)提高算法的效率；利用距離公式將兩個LSS在三維空間做有理運(yùn)動的碰撞條件轉(zhuǎn)化成9個多項(xiàng)式，計(jì)算9個多項(xiàng)式并對求出的交點(diǎn)進(jìn)行可用性檢驗(yàn)；利用多項(xiàng)式的Bemstein形式進(jìn)行求解；得到發(fā)生碰撞的情況中，兩個運(yùn)動物體的最近穿刺距離和未發(fā)生碰撞情況中，兩物體在運(yùn)動過程中的最近分離距離。 本文的主要貢獻(xiàn)： 1)