[發明專利]一種基于厚度的柔性場景連續碰撞檢測方法

有效

• 申請號: 201310211619.2
• 申請日: 2013-05-30
• 公開（公告）號: CN103337091A
• 公開（公告）日: 2013-10-02
• 發明（設計）人: 杜鵬;王毅剛;唐敏;童若鋒
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06T17/00
• 分類號: G06T17/00
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 杜軍

技術領域

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

背景技術

基于三角形網格的離散碰撞檢測（DCD）檢測在固定時刻物體之間是否存在接觸，但是對于高速碰撞的物體，采用該方法會遺漏碰撞。為了解決這個問題，我們引入了連續碰撞檢測（CCD）。

CCD通過插值獲得物體在兩個位置之間的運動路徑，進而檢測在這個運動過程中哪些部位發生了碰撞。該方法首先利用包圍盒重疊測試輸出存在重疊的包圍盒對，然后通過精確碰撞檢測來判斷包圍盒所對應的三角形是否發生了碰撞，而三角形對的精確碰撞檢測過程又可分解為6個頂點/三角形之間碰撞檢測。該方法被廣泛地應用于物理現象仿真、虛擬現實、人工智能等多個領域。

但是，目前的連續碰撞檢測方法沒有考慮模型厚度對檢測結果的影響，這是因為傳統的基于模型厚度的連續碰撞檢測方法需要求解1個一元六次方程，非常耗時。但是，在很多場合下，模型厚度對碰撞檢測的結果影響很大，比如柔性物體之間碰撞。

發明內容

針對現有技術所存在的上述技術缺陷，本發明提供了一種基于厚度的柔性場景連續碰撞檢測方法，利用求解1個基于厚度的3次方程，實現了對三角形對進行精確連續碰撞檢測的目標，提高了碰撞檢測的準確性和效率。

一種基于厚度的柔性場景連續碰撞檢測方法，包括如下步驟：

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

步驟(2)根據包圍盒層次結構，構建包圍盒測試樹，進而輸出存在包圍盒重疊的葉節點；

步驟(3)對步驟(2)輸出的葉節點對應的三角形對進行精確連續碰撞檢測。

所述的步驟（1）中，為三角形網格柔性場景模型建立包圍盒層次結構，包括如下步驟：

1-1.計算出三角形網格柔性場景模型中每個三角形的中心；

1-2.通過采用坐標軸投影分割法對所有三角形中心進行劃分：將所有三角形中心分別投影到三維坐標系的x、y、z軸上，?

1-2-1.選取軸上相距最遠的兩個三角形中心投影之間的距離，將其中距離最大的軸作為投影軸，將投影軸上相距最遠的兩個三角形中心投影為端點的線段，平分成兩個子線段；?若該子線段對應的三角形網格柔性場景模型的局部只有一個三角形中心或沒有三角形中心，則跳轉到步驟1-3；

1-2-2.將子線段對應的三角形網格柔性場景模型的局部繼續投影到三維坐標系的x、y、z軸上,?選取軸上相距最遠的兩個三角形中心投影之間的距離，將其中距離最大的軸作為投影軸，將投影軸上相距最遠的兩個三角形中心投影為端點的線段，平分成兩個子線段；?

1-2-3.若步驟1-2-2的子線段對應的三角形網格柔性場景模型的局部只有一個三角形中心或沒有三角形中心，則進入步驟1-3，否則重復步驟1-2-2；

1-3.采用自底向上的方法為整個三角形網格柔性場景模型建立對應的包圍盒層次結構。

所述的步驟（2）中，當進行第n次碰撞檢測時，包圍盒層次結構是根據第n次碰撞檢測時刻每個三角形更新后的空間位置，對上一次碰撞檢測過程的包圍盒層次結構中最底層的包圍盒進行重構，進而自底向上對上一次碰撞檢測過程的包圍盒層次結構進行整理更新而成的，n為大于1的自然數。

所述的步驟(3)中，基于厚度的連續碰撞檢測方法包括如下步驟：

3-1.將輸出的葉節點對應的三角形對分解為六個點/三角形測試對，獲取前一時刻和當前時刻待檢測三角形三個頂點的三維坐標、待檢測點的三維坐標、待檢測三角形的法向量、三角形網格柔性場景模型厚度；?

3-2.計算滿足???????????????????????????????????????????????的值，如果，則進一步判斷待檢測點在三角形所在平面投影是否在三角形內部，若是，則判定待檢測點和三角形發生了碰撞；其中：，，，，

，，，，分別為前一時刻待檢測三角形三個頂點的三維坐標，分別為當前時刻待檢測三角形三個頂點的三維坐標，和分別為前一時刻和當前時刻待檢測三角形的法向量，為三角形網格柔性場景模型厚度，和分別為前一時刻和當前時刻待檢測點的三維坐標，為誤差修正值。

所述的包圍盒優選為16-DOP包圍盒。

本發明有益效果如下：

本發明提供了一種基于厚度的柔性場景連續碰撞檢測方法，通過求解1個基于厚度的3次方程，實現了對三角形對進行精確連續碰撞檢測的目標，提高了碰撞檢測的準確性和效率。