[發(fā)明專(zhuān)利]一種實(shí)時(shí)碰撞檢測(cè)系統(tǒng)的實(shí)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201110289671.0
• 申請(qǐng)日: 2011-09-27
• 公開(kāi)（公告）號(hào): CN102509317A
• 公開(kāi)（公告）日: 2012-06-20
• 發(fā)明（設(shè)計(jì)）人: 張明陽(yáng);龔靜
• 申請(qǐng)（專(zhuān)利權(quán)）人: 北京像素軟件科技股份有限公司
• 主分類(lèi)號(hào): G06T11/00
• 分類(lèi)號(hào): G06T11/00
• 代理公司: 北京德琦知識(shí)產(chǎn)權(quán)代理有限公司 11018
• 代理人: 牛崢;王麗琴

1.一種實(shí)時(shí)碰撞檢測(cè)方法，其特征在于，包括如下步驟：

A、將場(chǎng)景分割成四叉樹(shù)，制作場(chǎng)景中需要發(fā)生碰撞的物體的碰撞模型，生成碰撞模型的模型數(shù)據(jù)文件以及場(chǎng)景的四叉樹(shù)及結(jié)點(diǎn)信息文件；

B、讀取所述四叉樹(shù)及結(jié)點(diǎn)信息文件，創(chuàng)建管理模型的四叉樹(shù)；讀取模型數(shù)據(jù)文件，根據(jù)碰撞模型的數(shù)量讀取碰撞模型中的三角形數(shù)據(jù)，創(chuàng)建保存三角形數(shù)據(jù)的數(shù)組，并生成碰撞模型的沿軸排列包圍盒AABB，根據(jù)最長(zhǎng)坐標(biāo)軸對(duì)碰撞模型進(jìn)行排序，然后建立AABB樹(shù)；

C、在客戶(hù)端和服務(wù)器側(cè)檢測(cè)在射線(xiàn)檢測(cè)距離內(nèi)的射線(xiàn)與四叉樹(shù)的碰撞，以及射線(xiàn)與四叉樹(shù)葉結(jié)點(diǎn)、AABB樹(shù)及三角形的碰撞，其中在客戶(hù)端測(cè)試最近的碰撞點(diǎn)，在服務(wù)器側(cè)判斷是否碰撞。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，步驟A所述將場(chǎng)景分割成四叉樹(shù)包括：

A1、判斷場(chǎng)景中是否存在根節(jié)點(diǎn)，若是，執(zhí)行步驟A2，否則結(jié)束本流程；

A2、判斷場(chǎng)景中模型的AABB與當(dāng)前節(jié)點(diǎn)的xz平面是否發(fā)生碰撞，若是執(zhí)行步驟A3，否則結(jié)束本流程；

A3、判斷當(dāng)前節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)且當(dāng)前節(jié)點(diǎn)包含的模型數(shù)目小于N，若是執(zhí)行步驟A5，否則執(zhí)行步驟A4；

A4、判斷當(dāng)前節(jié)點(diǎn)是否為最深節(jié)點(diǎn)，若是，執(zhí)行步驟A5，否則執(zhí)行步驟A6；

A5、在當(dāng)前節(jié)點(diǎn)中添加模型數(shù)據(jù)的索引，然后結(jié)束本流程；

A6、判斷是否遍歷完四叉樹(shù)的四個(gè)子節(jié)點(diǎn)，若是，執(zhí)行步驟A7，否則執(zhí)行步驟A10；

A7、判斷是否遍歷完當(dāng)前節(jié)點(diǎn)包含的模型數(shù)據(jù)，若是執(zhí)行步驟A8，否則返回步驟A6；

A8、判斷是否到達(dá)最上層結(jié)點(diǎn)，若是，結(jié)束本流程，否則執(zhí)行步驟A9；

A9、返回上一層結(jié)點(diǎn)，并繼續(xù)執(zhí)行步驟A6；

A10、設(shè)置當(dāng)前結(jié)點(diǎn)的子結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，并繼續(xù)執(zhí)行步驟A2。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述碰撞模型為場(chǎng)景中物體的渲染模型的簡(jiǎn)化模型。

4.根據(jù)權(quán)利要求1所述的方法，其特征在于，步驟A所述繪制場(chǎng)景中需要發(fā)生碰撞的物體的碰撞模型包括：設(shè)置碰撞模型的邏輯等級(jí)；

所述檢測(cè)射線(xiàn)與四叉樹(shù)葉結(jié)點(diǎn)、AABB樹(shù)及三角形的碰撞符合如下原則：射線(xiàn)僅與高于自身邏輯等級(jí)的碰撞模型對(duì)應(yīng)的AABB發(fā)生碰撞。

5.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述碰撞模型的邏輯等級(jí)分成低，中，高共三級(jí)。

6.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述四叉樹(shù)及結(jié)點(diǎn)信息文件的文件頭部分包括文件標(biāo)識(shí)、碰撞模型數(shù)量和四叉樹(shù)結(jié)點(diǎn)數(shù)量；文件體中包括N組結(jié)點(diǎn)信息以及結(jié)點(diǎn)包含模型信息，N為四叉樹(shù)中的結(jié)點(diǎn)總數(shù)；四叉樹(shù)及結(jié)點(diǎn)信息文件還包括結(jié)點(diǎn)關(guān)系信息。

7.根據(jù)權(quán)利要求6所述的方法，其特征在于，所述四叉樹(shù)及結(jié)點(diǎn)信息文件中的第i組結(jié)點(diǎn)信息的具體內(nèi)容包括：第i個(gè)結(jié)點(diǎn)的X軸最小值、Z軸最小值、X軸最大值、Z軸最大值、該節(jié)點(diǎn)的深度以及結(jié)點(diǎn)標(biāo)識(shí)，i為自然數(shù)，且1≤i≤N。

8.根據(jù)權(quán)利要求6所述的方法，其特征在于，所述四叉樹(shù)及結(jié)點(diǎn)信息文件中的第i組結(jié)點(diǎn)包含模型信息包括：結(jié)點(diǎn)包含碰撞模型數(shù)量以及該結(jié)點(diǎn)包含的全部碰撞模型索引。

9.根據(jù)權(quán)利要求6所述的方法，其特征在于，所述四叉樹(shù)及結(jié)點(diǎn)信息文件中的結(jié)點(diǎn)關(guān)系信息包括結(jié)點(diǎn)索引、孩子標(biāo)志、孩子結(jié)點(diǎn)索引以及1至4個(gè)孩子結(jié)點(diǎn)。

10.根據(jù)權(quán)利要求6至9任一項(xiàng)所述的方法，其特征在于，所述模型數(shù)據(jù)文件的文件頭包括文件標(biāo)識(shí)和三角形網(wǎng)格數(shù)量，文件體包括三角形信息和模型數(shù)據(jù)信息；所述三角形信息中包括多于1個(gè)三角形網(wǎng)格信息，每個(gè)三角形網(wǎng)格信息中包括該三角形網(wǎng)格中包含的三角形數(shù)量、三角形信息；模型數(shù)據(jù)信息中包括每一個(gè)碰撞模型的模型AABB、碰撞邏輯等級(jí)、三角形網(wǎng)格索引、三角形數(shù)量以及轉(zhuǎn)換矩陣。

11.根據(jù)權(quán)利要求10所述的方法，其特征在于，步驟C所述在客戶(hù)端測(cè)試最近的碰撞點(diǎn)包括：客戶(hù)端測(cè)試所有與射線(xiàn)發(fā)生碰撞的模型的三角形數(shù)據(jù)，計(jì)算最近的碰撞點(diǎn)，并返回碰撞測(cè)試結(jié)果。

12.根據(jù)權(quán)利要求10所述的方法，其特征在于，步驟C所述在服務(wù)器側(cè)判斷是否碰撞包括：當(dāng)服務(wù)器檢測(cè)到射線(xiàn)與某一個(gè)三角形發(fā)生碰撞時(shí)，立即返回測(cè)試成功。