[發(fā)明專(zhuān)利]一種基于經(jīng)緯度的碰撞檢測(cè)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201610497328.8
• 申請(qǐng)日: 2016-06-30
• 公開(kāi)（公告）號(hào): CN106202247B
• 公開(kāi)（公告）日: 2017-10-13
• 發(fā)明（設(shè)計(jì)）人: 王沫楠;毛志勇;李榮鵬;陳少勇
• 申請(qǐng)（專(zhuān)利權(quán)）人: 哈爾濱理工大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 哈爾濱市松花江專(zhuān)利商標(biāo)事務(wù)所23109
• 代理人: 岳泉清

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)檢測(cè)技術(shù)領(lǐng)域，具體涉及一種基于經(jīng)緯度的碰撞檢測(cè)方法。

背景技術(shù)

隨著計(jì)算機(jī)硬件技術(shù)的不斷發(fā)展，虛擬手術(shù)已成為計(jì)算機(jī)科學(xué)的一個(gè)重要研究領(lǐng)域，在虛擬手術(shù)環(huán)境中，由于虛擬手術(shù)刀具的移動(dòng)，與人體的肌肉等網(wǎng)格模型經(jīng)常可能發(fā)生碰撞。為了保持后續(xù)的軟組織形變，需要系統(tǒng)及時(shí)檢測(cè)到這些碰撞，并作相應(yīng)的碰撞反應(yīng)，同時(shí)在計(jì)算完畢后快速更新數(shù)據(jù)。

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

發(fā)明內(nèi)容

本發(fā)明提供了一種基于經(jīng)緯度的碰撞檢測(cè)方法，通過(guò)利用經(jīng)緯度使得空間的所有三角形的三維坐標(biāo)成為了二維坐標(biāo)，然后對(duì)各個(gè)維度分配一個(gè)跳表結(jié)構(gòu)，經(jīng)度則為跳表排序的關(guān)鍵字，使得碰撞檢測(cè)與更新速度都能達(dá)到跳表所能有的高效，提高了碰撞的查詢(xún)效率，同時(shí)增強(qiáng)了查詢(xún)效率的穩(wěn)定性，提高了更新節(jié)點(diǎn)的效率。

一種基于經(jīng)緯度的碰撞檢測(cè)方法，包括如下步驟。

（1）對(duì)場(chǎng)景中待碰撞的剛體或者軟組織物體的邊界三角面片信息進(jìn)行預(yù)處理，獲取三角面片形心的z坐標(biāo)最大值Zmax與z坐標(biāo)最小值Zmin,以及所有三角面片的平均邊長(zhǎng)length_avg，初始化經(jīng)緯度數(shù)據(jù)結(jié)構(gòu)中維度與跳表數(shù)組下表的對(duì)應(yīng)關(guān)系，同時(shí)動(dòng)態(tài)申請(qǐng)三角面片數(shù)量大小的動(dòng)態(tài)指針數(shù)組，初始化都為NULL,用于存儲(chǔ)跳表中的單元地址。

（2）遍歷三角面片集合，得到各個(gè)維度的所有三角面片形心的平均值（中心坐標(biāo)），記錄到經(jīng)緯度數(shù)據(jù)結(jié)構(gòu)中。

（3）遍歷所有的三角面片，每個(gè)三角面片都計(jì)算得到形心坐標(biāo)，根據(jù)形心坐標(biāo)得到所處的維度，根據(jù)該維度的中心坐標(biāo)，獲取經(jīng)度，存入對(duì)應(yīng)維度的跳表中。

（4）對(duì)外部三角面片集合進(jìn)行碰撞檢測(cè)時(shí)候，計(jì)算外部三角面片的形心坐標(biāo)，根據(jù)z坐標(biāo)得到維度，根據(jù)維度得到維度中心坐標(biāo)，計(jì)算經(jīng)度后在該維度的跳表中查詢(xún)最近的經(jīng)度的三角面片，進(jìn)行兩個(gè)三角面片進(jìn)行精確碰撞檢測(cè)。

（5）某個(gè)三角面片在外力的作用下發(fā)生變形，拓?fù)渲貥?gòu)的過(guò)程只需要對(duì)該三角面片進(jìn)行刪除后再插入即完成更新。

所述的步驟（1）中，初始化經(jīng)緯度數(shù)據(jù)結(jié)構(gòu)中維度與跳表數(shù)組下表的對(duì)應(yīng)關(guān)系的實(shí)現(xiàn)過(guò)程為：首先計(jì)算維度最大值Dimension_Max = (int)((Zmax-Zmin)/ length_avg)+1；然后申請(qǐng)Dimension_Max大小的跳表結(jié)構(gòu)數(shù)組；最后得到跳表的下表i與維度的關(guān)系則是i = Dimension-1。

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

所述的步驟（3）中，當(dāng)?shù)趍個(gè)三角面片插入時(shí)，由該m號(hào)三角面片的形心坐標(biāo)，得到維度為w，得到經(jīng)度為p，那么使用跳表數(shù)組的w-1號(hào)跳表，則按照經(jīng)度p作為該跳表的關(guān)鍵字，按照從小到大的排序方式，找到對(duì)應(yīng)的插入位置，申請(qǐng)一個(gè)結(jié)構(gòu)體的內(nèi)存空間，內(nèi)部存放當(dāng)前三角面片的序號(hào)，插入其中。

所述的步驟（4）中，進(jìn)行兩個(gè)三角面片進(jìn)行精確碰撞檢測(cè)的實(shí)現(xiàn)過(guò)程為：首先進(jìn)行包圍盒的檢測(cè)，然后進(jìn)行穿越算法進(jìn)行檢測(cè)。

所述的步驟（5）中，對(duì)于發(fā)生變形的三角面片，根據(jù)存儲(chǔ)著其跳表中地址的動(dòng)態(tài)數(shù)組，根據(jù)三角面片的下標(biāo)得到其跳表中的地址，可以快速進(jìn)行刪除，然后重新計(jì)算三角面片的形心，重新計(jì)算其維度與經(jīng)度，加入到對(duì)應(yīng)維度的跳表中。