有效率的複雜模型之連續碰撞偵測

Abstract

我們提出一個有效率的演算法來處理複雜模型之連續碰撞偵測。給定兩個模型及他們的起使及終點設定，我們使用線性內插來計算中間的動作並且檢查這兩個模型是否產生碰撞。我們的演算法由三個階段組成，這三個階段會構成一個流水線：(1)使用模型之包圍球來做碰撞偵測。(2)使用階層式包圍容積之上部分階層執行保守前進。(3)使用兩模型間之精確距離執行保守前進。在我們的系統中使用者可以設定一距離上限，如果兩物件的距離小於此上限的話，我們的系統會宣告這兩個物件產生碰撞。在我們的演算法執行完畢後，如果兩物件有碰撞的話，我們會得到碰撞時間及兩模型的碰撞資訊。我們在不同的情形下測試我們的演算法，並且和FAST做比較，我們的演算法效能好兩到四倍。我們的演算法所需的記憶體空間比FAST少三到四倍。所有的測試在 Pentium 4 2.8GHz 的PC上執行。

We present an efficient algorithm to perform continuous collision detection for complex-shaped models. Given two models and their initial and final configurations, we use linear interpolation to calculate their in-between motion and examine if there exists collision between the two objects. Our algorithm is composed of three stages:(1) dynamic collision detection with bounding spheres of models;(2) conservative advancement with upper levels of bounding volume hierarchy; (3)conservative advancement with exact distance between two models. Moreover, in our system, user can assign a distance threshold, and our system will claim the collision of two objects if the distance between two objects is below the threshold. The output of our algorithm is the time of contact and colliding feature of two models if there exists collision. We tested our algorithm in several scenarios and compared with the method proposed by Zhang. The performance of our algorithm is 2 ~ 4 times faster. Furthermore, the required memory of our algorithm is less than Zhang's method by a factor of 3 ~ 4 on a Pentium4 2.8GHz PC for complex-shaped models composed of 10k ~ 70k triangles.