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

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

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

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

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

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

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