技術領域

本發明屬于計算機檢測技術領域，具體涉及一種基于經緯度的碰撞檢測方法。

背景技術

隨著計算機硬件技術的不斷發展，虛擬手術已成為計算機科學的一個重要研究領域，在虛擬手術環境中，由于虛擬手術刀具的移動，與人體的肌肉等網格模型經?？赡馨l生碰撞。為了保持后續的軟組織形變，需要系統及時檢測到這些碰撞，并作相應的碰撞反應，同時在計算完畢后快速更新數據。

通常碰撞檢測基于空間域的角度可以分為基于實體空間碰撞檢測方法與基于圖像空間碰撞檢測方法兩種。由于圖像空間碰撞檢測本身是空間離散采樣的，其精度受圖形分辨率的約束，從而影響碰撞檢測的經度，而且該類方法只能適用于圖面，因此在虛擬手術系統中的碰撞檢測對圖形空間碰撞檢測不作考慮。而實體空間碰撞檢測目前研究最多使用最廣泛的則是基于層次包圍體樹的檢測方法。但是該類方法的高效檢測則是基于建立一個較為平衡的包圍體樹的前提下，如果包圍體樹建立的不平衡，會導致部分節點查詢的效率低下。同時，對于節點更新則需要重新自底向上或者自頂向下掃描包圍體樹，從而達到更新包圍體樹，這個更新包圍體樹的過程，幾乎就是重新構建一個新樹，會嚴重降低虛擬手術在切割變形操作后的再次碰撞的速度。

發明內容

本發明提供了一種基于經緯度的碰撞檢測方法，通過利用經緯度使得空間的所有三角形的三維坐標成為了二維坐標，然后對各個維度分配一個跳表結構，經度則為跳表排序的關鍵字，使得碰撞檢測與更新速度都能達到跳表所能有的高效，提高了碰撞的查詢效率，同時增強了查詢效率的穩定性，提高了更新節點的效率。

一種基于經緯度的碰撞檢測方法，包括如下步驟。

（1）對場景中待碰撞的剛體或者軟組織物體的邊界三角面片信息進行預處理，獲取三角面片形心的z坐標最大值Zmax與z坐標最小值Zmin,以及所有三角面片的平均邊長length_avg，初始化經緯度數據結構中維度與跳表數組下表的對應關系，同時動態申請三角面片數量大小的動態指針數組，初始化都為NULL,用于存儲跳表中的單元地址。

（2）遍歷三角面片集合，得到各個維度的所有三角面片形心的平均值（中心坐標），記錄到經緯度數據結構中。

（3）遍歷所有的三角面片，每個三角面片都計算得到形心坐標，根據形心坐標得到所處的維度，根據該維度的中心坐標，獲取經度，存入對應維度的跳表中。

（4）對外部三角面片集合進行碰撞檢測時候，計算外部三角面片的形心坐標，根據z坐標得到維度，根據維度得到維度中心坐標，計算經度后在該維度的跳表中查詢最近的經度的三角面片，進行兩個三角面片進行精確碰撞檢測。

（5）某個三角面片在外力的作用下發生變形，拓撲重構的過程只需要對該三角面片進行刪除后再插入即完成更新。

所述的步驟（1）中，初始化經緯度數據結構中維度與跳表數組下表的對應關系的實現過程為：首先計算維度最大值Dimension_Max = (int)((Zmax-Zmin)/ length_avg)+1；然后申請Dimension_Max大小的跳表結構數組；最后得到跳表的下表i與維度的關系則是i = Dimension-1。

所述的步驟（2）中，得到各個維度的所有三角面片形心的平均值（中心坐標）的實現過程為：首先申請維度最大值Dimension_Max大小的三個double數組,分別代表各個維度的x,y,z的累加；然后遍歷被檢測物體的所有的表面三角面片，每個三角面片都計算其形心坐標(x,y,z)，得到對應的維度w=(int)((Zmax-z)/length_avg)+1,在三個double數組的下標為w-1的位置，分別累加x,y,z的值，最后三個數組的每個元素都除以三角面片的集合的個數。

所述的步驟（3）中，當第m個三角面片插入時，由該m號三角面片的形心坐標，得到維度為w，得到經度為p，那么使用跳表數組的w-1號跳表，則按照經度p作為該跳表的關鍵字，按照從小到大的排序方式，找到對應的插入位置，申請一個結構體的內存空間，內部存放當前三角面片的序號，插入其中。

所述的步驟（4）中，進行兩個三角面片進行精確碰撞檢測的實現過程為：首先進行包圍盒的檢測，然后進行穿越算法進行檢測。

所述的步驟（5）中，對于發生變形的三角面片，根據存儲著其跳表中地址的動態數組，根據三角面片的下標得到其跳表中的地址，可以快速進行刪除，然后重新計算三角面片的形心，重新計算其維度與經度，加入到對應維度的跳表中。