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

有效

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

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

本發(fā)明涉及計算機游戲及虛擬現(xiàn)實技術(shù)領(lǐng)域，尤其涉及一種實時碰撞檢測系統(tǒng)的實現(xiàn)方法。

背景技術(shù)

碰撞檢測技術(shù)用于判定一對或多對物體在給定時間域內(nèi)的同一時刻是否占有相同區(qū)域。它是機器人運動規(guī)劃、計算機仿真、虛擬現(xiàn)實、游戲等領(lǐng)域不可回避的問題之一。

在當(dāng)今的大型3D場景游戲中，實時碰撞檢測技術(shù)非常常見，它能夠使游戲中各種效果的表現(xiàn)更加精準(zhǔn)，玩家的體驗更加真實，但是復(fù)雜場景的實時檢測的效率有時還不能令人滿意，影響到游戲的整體性能，影響游戲體驗。而對于一些射擊類的大型網(wǎng)絡(luò)游戲，如果僅僅進行客戶端的檢測，服務(wù)端的碰撞結(jié)果就只能由客戶端返回，但是這樣就給了外掛可乘之機，雖然可能可以通過其他方式避免，但也會相對復(fù)雜。如果在服務(wù)端也進行碰撞檢測，以現(xiàn)有的碰撞檢測技術(shù)而言，服務(wù)端無法承受大數(shù)據(jù)量的碰撞檢測，或者需要性能更高效的服務(wù)器，增加游戲的運營的支出。

基于格子的碰撞系統(tǒng)在早期比較常見，它實現(xiàn)簡單，執(zhí)行效率快，像早期的仙劍奇?zhèn)b傳和其他碰撞怪的角色扮演游戲(RPG)，以及一些推箱子、打磚塊、俄羅斯方塊等游戲，都是基于這種類型的碰撞檢測。基于格子的碰撞檢測系統(tǒng)碰撞的精度不夠，不屬于嚴(yán)格意義上的碰撞檢測。

基于二叉空間分割(BSP)樹的碰撞檢測比較適合復(fù)雜的封閉場景，場景根據(jù)一定的分配策略將空間劃分為2部分，然后再對子結(jié)點進行遞歸劃分，直到達到分配策略的要求。碰撞模型的圖元數(shù)據(jù)都保存在葉子中。這種碰撞的分割策略很重要，技術(shù)已經(jīng)很成熟，效率很高。但是基于BSP樹的碰撞檢測，BSP樹的生成需要很長的預(yù)處理時間，不適合加載時計算；BSP劃分經(jīng)常會產(chǎn)生原多邊形數(shù)三到四倍的多邊形，考慮到不用保存法線、顏色、uv等信息也要增加將近一倍的資源容量，因此不適合處理大型場景的碰撞。在一個大的游戲中將模型資源的容量從200M增加到400M相信是大部分人都不愿接受的。

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

本發(fā)明提供了一種實時碰撞檢測系統(tǒng)的實現(xiàn)方法，能夠?qū)崟r高效的處理大型場景的碰撞。

本發(fā)明實施例提供的一種實時碰撞檢測系統(tǒng)的實現(xiàn)方法包括如下步驟：

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

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

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

較佳地，步驟A所述將場景分割成四叉樹包括：

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

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

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

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

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

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

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

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

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

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

較佳地，所述碰撞模型為場景中物體的渲染模型的簡化模型。

較佳地，步驟A所述繪制場景中需要發(fā)生碰撞的物體的碰撞模型包括：設(shè)置碰撞模型的邏輯等級；

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

較佳地，所述碰撞模型的邏輯等級分成低，中，高共三級。

較佳地，所述四叉樹及結(jié)點信息文件的文件頭部分包括文件標(biāo)識、碰撞模型數(shù)量和四叉樹結(jié)點數(shù)量；文件體中包括N組結(jié)點信息以及結(jié)點包含模型信息，N為四叉樹中的結(jié)點總數(shù)；四叉樹及結(jié)點信息文件還包括結(jié)點關(guān)系信息。