游戲引擎中碰撞檢測算法研究

摘 要：將碰撞檢測算法應用到游戲引擎中，可以提高引擎系統的執行效率。本文主要介紹了游戲場景中物體之間的碰撞檢測問題，重點闡述了基于層次包圍盒的碰撞檢測算法，并對幾種常見的包圍盒進行了比較。

關鍵詞：游戲引擎；碰撞檢測；包圍盒

中圖分類號：TP391.41 文獻標識碼：A 文章編號：1674-7712 （2014） 04-0000-01

近年來虛擬現實技術和分布式交互仿真技術的應用越來越廣泛，計算機模擬現實世界真實性的需求越來越高，這種真實性的關鍵在于如何自然合理的模擬現實世界中各物體間的相互關系即相互碰撞問題。為了保證計算機模擬環境的真實性，虛擬環境中的對象進行各種運動時必須實時檢測物體間是否發生了碰撞，而且虛擬環境中的其它對象要能夠做出及時地響應，避免現實生活中不可能出現的如物體間的穿透等現象的發生。在游戲引擎軟件中的大規模復雜動態場景中，對象的幾何復雜度直接導致了對象間碰撞檢測計算量大、較為耗時，使得碰撞檢測問題更加復雜，通過對碰撞檢測算法的研究及優化，可以提高碰撞檢測算法的性能、提高碰撞檢測的效率。

一、 游戲引擎

游戲開發的核心技術是游戲引擎，游戲引擎是指通過整理和封裝通用技術細節來形成面向游戲應用的接口函數，游戲開發人員只需調用游戲引擎框架中相關的函數而不用關心底層技術是如何實現的。完整的游戲引擎是由許多游戲功能組件共同來組成的，它具有分明的層次結構，一般包括物理數學支持層、圖形渲染內核、系統層、游戲介質層以及開發工具層。其中最關鍵的部分是圖形渲染內核，包括配置子系統、圖形子系統、聲音子系統、輸入子系統和時效子系統，它們互相配合共同完成游戲中的各種效果?，F在市面上有很多商業引擎，基本上都采用了底層算法思想以及最新的圖形圖像學技術，表現出非常好的開發性和延展性，又各有各的特點，對于特定網絡游戲的開發具有重要的意義。

二、碰撞檢測

碰撞檢測是構建游戲引擎最主要的環節之一，也是衡量一款游戲是否達到預期效果的標準。碰撞檢測問題在計算機圖形學、智能機器人等領域都有著悠久的研究歷史，它是基于“兩個不可穿透的物體不能同時共享相同的空間區域”這個現實生活中廣泛存在的事實設定的。

（一）碰撞檢測概念

碰撞檢測就是對物體在運動過程中可能出現的碰撞進行檢查，避免碰撞的發生，或進行碰撞的響應處理。碰撞檢測的基本任務就是確定兩個物體之間是否發生了接觸或穿透，即兩個多面體的求交測試問題。碰撞檢測是構造虛擬環境的核心部分，游戲中如果不進行碰撞檢測，人物就可以在場景中任意游走，就會出現穿墻過樹等與現實世界不符的行為規則，所以說合理精確的碰撞檢測在游戲中是必不可少的。最簡單的碰撞檢測就是對兩個輸入模型中所有幾何元素進行兩兩相交測試，隨著輸入模型的復雜度越來越高，相交測試數目成幾何級數增長，大大影響游戲運行的效率，因此，如何提高算法的速度以保證游戲中的實時交互性是碰撞檢測的核心。

（二）碰撞檢測分類

碰撞檢測方法可以分為兩類：空間分解法和層次包圍盒法?？臻g分解法是將整個虛擬空間劃分成體積相等的若干小單元格，并且只對同一單元格或相鄰單元格的幾何元素進行相交測試。層次包圍盒法是用體積較大而幾何特性相對簡單的包圍盒來近似描述復雜的幾何元素，先對包圍盒進行相交測試，在此基礎上只需對包圍盒重疊部分進行進一步的相交測試。兩種方法都使用了層次結構模型，都是為了盡可能地減少相交測試的幾何元素數目?？臻g分解法適用于稀疏環境中幾何對象分布比較均勻的碰撞檢測，而層次包圍盒法適用于復雜環境中幾何對象的碰撞檢測，它的應用更為廣泛，本文主要研究的就是基于層次包圍盒的碰撞檢測算法。

三、基于層次包圍盒的碰撞檢測算法

（一）層次包圍盒法原理

層次包圍盒法的基本思想是用體積較大而幾何特性相對簡單的包圍盒來近似地描述復雜的幾何對象，通過構造樹形層次結構可以將包圍盒越來越逼近對象的幾何模型，最終可以獲得與實際對象有著幾乎完全一致的幾何特性的包圍盒，由于包圍盒的相交測試比直接對幾何對象進行相交測試要簡單的多，因此，在對幾何對象進行碰撞檢測時，首先對包圍盒進行相交測試，這樣能夠快速排除許多不相交的幾何對象，如果相交再對包圍盒重疊部分進行進一步的相交測試，提高了算法的執行效率。

（二）常見的包圍盒

通過使用簡單幾何模型包圍復雜對象進行碰撞檢測大大提高了碰撞檢測的效率，但并不是所有幾何模型都可以充當包圍體的，它必須是具有構造簡單、占用內存空間小、有良好的緊密性、相交測試計算量小且能夠快速更新等優勢。常見的包圍盒有以下幾種：（1）軸向包圍盒：包含該對象且各邊與坐標軸平行的最小正六面體。它的簡單性好，緊密性差，當對象旋轉后需要重新進行計算。（2）方向包圍盒：包含該對象且方向任意的最小正六面體。緊密性較好，實時性較高，當對象旋轉后只需對包圍盒進行同樣的旋轉。（3）離散方向多面體包圍盒：包含該對象且有k個固定方向的凸多面體結構。緊密性較好，但需要合理選取平行平面對的個數和方向。（4）球包圍盒：包含該對象的最小球體。簡單性好，緊密性差，當對象旋轉后包圍球不需要作任何改變，當對象變形后需要重新計算。

層次包圍盒法是目前應用最廣泛的碰撞檢測算法，各種包圍盒算法有各自的優劣，針對不同的應用場合選擇不同的方法，以達到簡單、緊密、實時的要求。

（三）層次包圍盒樹

雖然采用包圍盒代替基本幾何對象進行相交測試的方法提高了碰撞檢測性能，但還需進行兩兩包圍盒的相交測試，如果將包圍盒整合到樹形結構中，應用層次包圍盒技術，兩兩包圍盒之間相交測試的時間復雜度可以由平方級降為對數級。在樹形結構中，根節點代表對象本身，所有葉子結點組成對象的基本幾何元素?？梢圆捎米皂斚蛳禄蛘咦缘紫蛏系臉嬙旆椒▉順嬙鞂哟伟鼑袠洹?/p>

四、結束語

隨著虛擬環境的復雜性越來越高，對于碰撞檢測算法的實時性和精確性還要不斷進行深入研究，通過不斷改進優化算法并應用于游戲引擎中，可以有效地解決大型復雜虛擬環境下的碰撞檢測問題。

參考文獻：

[1]黃楊飛.大場景3D游戲引擎技術研究與實現[D].浙江師范大學，2011

[2]姜曉路.碰撞檢測算法研究及其在引擎軟件中的應用[D].江南大學，2012