[發明專利]一種基于非共線剔除的柔性場景連續碰撞檢測方法

無效

• 申請號: 201210159761.2
• 申請日: 2012-05-18
• 公開（公告）號: CN102708017A
• 公開（公告）日: 2012-10-03
• 發明（設計）人: 杜鵬;唐敏;童若鋒;趙杰伊
• 申請（專利權）人: 浙江大學
• 主分類號: G06F11/00
• 分類號: G06F11/00
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

技術領域

本發明屬于計算機檢測技術領域，具體涉及一種基于非共線剔除的柔性場景連續碰撞檢測方法。

背景技術

基于三角形網格的連續碰撞檢測被廣泛應用于不同的技術領域，包括機器人運動路徑規劃、物理仿真、視頻游戲等，它使用勻速線性插值軌跡，檢測物體在兩個離散位置間可能發生的碰撞情況。

目前應用最廣泛的連續碰撞檢測方法是利用包圍盒層次結構（BVH），先對整個場景進行包圍盒重疊測試，當檢測到兩個包圍盒不相交時，停止遍歷該節點的子節點。各種BVH，如球（Sphere）樹，軸對齊包圍盒（AABB）樹，定向包圍盒（OBB）樹，離散定向多面體（k-DOP）樹等，這些層次結構通常采用自頂向下的方法進行構造，被廣泛應用于剛體或柔性物體的碰撞檢測。對于柔性物體，除了需要考慮包圍盒的緊湊性外，包圍盒整理和重構的效率也至關重要。圖1為AABB、8-DOP和OBB三種包圍盒的示意圖，對于簡單的包圍盒，如Sphere、AABB，其整理和構造十分快捷，但緊湊性較差；對于復雜的包圍盒，如OBB，雖然較為緊湊，但整理和構造的計算量較大；作為折中選擇，k-DOP兼具緊湊性和高效性，因此常被用于柔性物體的包圍盒層次結構，但即使使用了最緊湊的包圍盒，剔除率仍然不高。

因此，對于包圍盒重疊測試輸出的存在重疊的包圍盒對，傳統方法通過精確碰撞檢測來判斷包圍盒對所對應的三角形對是否發生了碰撞，精確碰撞檢測過程可分解為15種碰撞情況的檢測：6種頂點/三角形之間碰撞檢測和9種邊/邊之間碰撞檢測。而每個元素測試至少需要求解一個三次方程的根，15種情況需要求解15個三次方程以及一些附加的判斷條件，因此這個過程需要耗費大量的計算時間。

發明內容

針對現有技術所存在的上述技術缺陷，本發明提供了一種基于非共線剔除的柔性場景連續碰撞檢測方法，通過在精確碰撞檢測階段，利用非共線剔除相應的碰撞情況，減少了精確碰撞檢測的次數，提高了碰撞檢測的速度。

一種基于非共線剔除的柔性場景連續碰撞檢測方法，包括如下步驟：

（1）對待檢測的三角形網格柔性場景模型中的每個三角形構造對應的包圍盒，進而建立三角形網格柔性場景模型的包圍盒層次結構；

（2）根據所述的包圍盒層次結構，構建包圍盒測試樹（BVTT）；對所述的包圍盒測試樹進行包圍盒重疊測試，輸出存在包圍盒重疊的葉節點；

（3）對輸出的葉節點對應的三角形對進行非共線剔除檢測，對剔除后保留的碰撞情況進行精確碰撞檢測。

所述的非共線剔除檢測包括點/面非共線剔除檢測和邊/邊非共線剔除檢測。

所述的點/面非共線剔除檢測的方法過程為：

1）獲取待檢測三角形和待檢測點P的三維信息，令a、b、c分別為待檢測三角形的三個頂點；所述的三維信息包括前一時刻和當前時刻待檢測三角形各頂點的三維坐標、待檢測點P的三維坐標、待檢測三角形的法向量；

2）在前一時刻至當前時刻的整個運動過程中，根據所述的三維信息判斷在待檢測三角形所在的投影平面中頂點c是否始終在待檢測三角形ab邊的一側：若是，進入步驟3）進行判斷；若否，保留待檢測三角形和待檢測點的碰撞情況；

3）根據所述的三維信息判斷在待檢測三角形所在的投影平面中待檢測點P是否在ab邊的另一側：若是，則剔除待檢測三角形和待檢測點的碰撞情況；若否，進入步驟4）進行判斷；

4）根據所述的三維信息判斷在待檢測三角形所在的投影平面中待檢測點P是否在bc邊相對于頂點a的另一側：若是，則剔除待檢測三角形和待檢測點的碰撞情況；若否，進入步驟5）進行判斷；

5）根據所述的三維信息判斷在待檢測三角形所在的投影平面中待檢測點P是否在ac邊相對于頂點b的另一側：若是，則剔除待檢測三角形和待檢測點的碰撞情況；若否，保留待檢測三角形和待檢測點的碰撞情況。

所述的邊/邊非共線剔除檢測的方法過程為：

1）獲取兩條待檢測邊的三維信息，令a和b分別為一條待檢測邊的兩個端點，c和d分別為另一條待檢測邊的兩個端點，端點a、b、c構成的平面為投影平面；所述的三維信息包括前一時刻和當前時刻待檢測邊各端點的三維坐標；

2）在前一時刻至當前時刻的整個運動過程中，根據所述的三維信息判斷在所述的投影平面中端點a、b是否均在cd邊的同一側：若是，則剔除兩條待檢測邊的碰撞情況；若否，進入步驟3）進行判斷；