利用代數(shù)方法求解碰撞檢測問題.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ù)碰撞檢測，如掃描卷方法、基于對(duì)偶和Minkowski和的方法、基于KDS (Kinetic Data Structure) 的方法、代數(shù)方法等。離散的碰撞檢測方法是對(duì)兩運(yùn)動(dòng)物體在時(shí)間軸上采樣，在每個(gè)采樣時(shí)刻判斷兩靜態(tài)物體是否碰撞。在離散的碰撞檢測方法中，如果物體運(yùn)動(dòng)速度很快或者物體很小，有可能會(huì)檢測不到取樣時(shí)

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

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

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

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