一種基于多線程加速的大規模群體仿真方法

傅正揚 姜忠鼎

(復旦大學上海市數據科學重點實驗室 上海 201203)(復旦大學軟件學院 上海 201203)

0 引 言

近年來，隨著計算機技術和硬件水平的不斷提高，計算機可以在虛擬場景中進行規模更加龐大的群體仿真。大規模群體仿真技術可以提高虛擬場景的臨場感和趣味性，在游戲娛樂、演習訓練、建筑設計等領域具有重要的應用價值。

游戲引擎是為游戲研發設計的集成化開發工具，包含一系列游戲開發和場景制作常用的功能模塊，開發者可以使用這些功能模塊加快游戲和虛擬場景的開發速度。游戲引擎通常內置動畫系統、導航系統和物理系統等功能模塊，可以實現小規模的群體仿真。但隨著群體數量的不斷增加，游戲引擎內置功能模塊的計算量也大幅度增加，導致游戲引擎內置的功能模塊難以高效地實現大規模群體仿真，場景幀率難以滿足應用的需求。

大規模群體仿真技術包括群體動畫渲染和群體行為模擬兩個方面。對于大規模群體動畫渲染，層級細節技術(LOD)的研究和應用最為廣泛。層級細節技術利用了觀察者和顯示設備的分辨極限，根據模型占據觀察者可視區域的大小，動態更變繪制模型的復雜程度，提升實時渲染效率[1]。但是層級細節技術無法降低CPU計算模型蒙皮動畫的消耗，隨著場景群體模型數量增多，CPU的蒙皮動畫計算會成為大規模群體動畫渲染的瓶頸[2]。遮擋剔除技術(Culling)計算場景中觀察者視錐區域和模型之間的遮擋關系，不繪制場景中完全被遮擋的模型。在游戲引擎中，可以使用層級數據結構加速計算模型的遮擋關系[3]。如果觀察者視錐區域存在大量未被完全遮擋的群體模型，遮擋剔除技術難以有效地提升渲染效率。對于共用一套網格與動畫的群體，GPU蒙皮渲染(GPU Skinning Instancing)[4]預采樣這套網格與動畫的所有數據，在實時渲染中利用著色器的系統變量(System Variables)為群體中的個體設置動畫狀態。GPU蒙皮渲染在一次Draw Call中使用GPU批處理大量個體的蒙皮動畫計算和渲染，大幅度降低了CPU在蒙皮動畫計算上的消耗。

大規模群體行為模擬一直是國內外研究的熱點。自主性群體行為算法(Autonomous boids)是學術界和工業界應用比較廣泛地群體行為算法[5]，該方法引入了聚合性(Cohesion)、分離性(Separation)、隊列性(Alignment)三個群體行為基準，使用力模型表示這三個群體行為基準來模擬群體行為。自主性群體行為模擬仿真結果逼真，但是隨著群體數量增加，群體之間發生碰撞的概率也大幅度增加?；谒俣饶Ｐ偷淖顑灮ハ嗯鲎脖茏屗惴?ORCA)可以有效地降低群體仿真中碰撞發生的次數[6]，最優互相碰撞避讓算法獨立計算群體中每個個體的碰撞避讓策略，可以利用多線程并行加速計算，當群體數量較大時，最優互相碰撞避讓算法也能在極短的時間內完成個體的碰撞避讓計算[7]。近年來，國內外許多研究者在最優互相碰撞避讓算法上不斷改進，以適應一些復雜的應用場景。文獻[8]在最優互相碰撞避讓算法基礎上提出一種適用于超大規模人群碰撞避讓模擬的算法，將場景區域劃分為多個矩形區域，以矩形區域為單位進行算法計算，犧牲局部矩形區域的碰撞避讓精度，提高了算法對于超大規模人群碰撞避讓的運算速度。文獻[9]通過動態平衡短時間和長時間內碰撞發生的概率，提高最優互相碰撞避讓算法對障礙物躲避的精準性，但是算法耗時也有所增加。文獻[10]在最優互相碰撞避讓算法的基礎上引入多邊形旋轉的概念，使得改進后的RRVO算法在群體擁堵的情況下更快地擺脫群體死鎖不動的僵局。文獻[11]對三維空間下的最優互相碰撞避讓算法進行改進，將改進后的算法應用于無人機實時躲避其他無人機和靜態障礙物。

基于以上分析，本文在GPU蒙皮渲染、自主性群體行為和最優互相碰撞避讓算法上加入多線程優化，提出一種大規模群體仿真的方法，提升大規模群體仿真的群體動畫渲染和群體行為模擬性能。針對群體動畫渲染，本文在GPU蒙皮渲染算法上加入了群體動畫狀態的多線程計算，加速群體動畫狀態和蒙皮動畫計算；針對群體行為模擬，將自主性群體行為的力模型算法改進為速度模型算法，計算個體的初始速度，再將初始速度作為多線程優化后的最優互相碰撞避讓算法輸入，實現群體行為的碰撞避讓，同時利用多線程提升群體行為模擬的計算速度。最后，在一款基于Unity游戲引擎[12]和HTC Vive[13]開發的虛擬現實游戲中使用本方法進行實驗，證明本方法可以與游戲引擎結合，應用于邏輯復雜的大規模群體仿真場景，提升大規模群體仿真的效率。

1 基于多線程加速的大規模群體仿真方法概述

大規模群體仿真包括群體動畫渲染、群體行為模擬。這兩個部分的計算相互獨立、互不影響，可以分別優化。本文對已有的群體動畫渲染和群體行為模擬算法分別進行改進，提出一種基于多線程加速的大規模群體仿真方法，用以提升大規模群體仿真的性能。基于多線程加速的大規模群體仿真方法流程如圖1所示。

圖1 基于多線程加速的大規模群體仿真流程圖

在群體動畫渲染方面，由于群體數量龐大，使用CPU計算群體蒙皮動畫的方法會大幅度增加CPU的負荷，導致大規模群體仿真場景幀率過低，難以滿足應用需求。本文對GPU蒙皮渲染算法[4]進行改進，加入了多線程并行計算，提出了基于GPU蒙皮渲染的多線程加速算法。該算法利用GPU高并行計算能力加速計算群體的蒙皮動畫，并且利用CPU多線程加速計算群體的動畫狀態，提升群體動畫渲染的性能。

在群體行為模擬方面，需要提升群體行為模擬和群體碰撞避讓的計算性能。本文對基于自主性群體行為算法[6]和最優互相碰撞避讓算法[7]進行改進，提出基于自主性群體行為和最優互相碰撞避讓的多線程加速算法。該算法首先使用自主性群體行為算法模擬個體跟隨群體的行為，并且將自主性群體行為算法的力模型改為速度模型，使得群體在運動過程中能極快地改變速度，以避讓場景中障礙物；其次，該算法在最優互相碰撞避讓算法的基礎上加入了多線程加速，使用改進后的基于多線程加速的最優互相碰撞避讓算法加速計算群體之間的碰撞避讓行為，進一步提升群體碰撞避讓的計算效率。

2 基于GPU蒙皮渲染多線程加速算法

在很多情況下，大規模群體使用同一套模型網格和骨骼動畫，除了空間信息，繪制群體中每個個體的區別僅在于它們當前播放的骨骼動畫種類與幀數是不同的。GPU蒙皮渲染算法[4]可以利用GPU的高并行計算能力加速相同個體的蒙皮動畫計算。本文在GPU蒙皮渲染算法的基礎上，加入了群體動畫狀態的多線程計算，進一步提升群體動畫渲染的效率。

使用骨骼動畫的模型包含骨骼層次框架，模型網格的每個頂點V與一個或者多個骨骼B綁定，每個骨骼B的初始姿勢綁定矩陣是BP，對頂點V的影響權重為w。骨骼動畫每一幀都包含所有模型骨骼的變換矩陣M，以變換模型骨骼B的方式改變模型網格的每個頂點V，實現骨骼動畫的播放。網格頂點V位置的計算公式如下：

(1)

根據式(1)可知，模型預采樣的數據包括以下幾點：模型骨骼的層次框架、模型網格頂點與模型骨骼的綁定關系、模型骨骼的初始姿勢綁定矩陣、以及所有骨骼動畫對模型骨骼的變換矩陣。其中，所有骨骼動畫對模型骨骼的變換矩陣數據十分龐大，需要以紋理的格式保存采樣的數據結果，方便上傳至GPU并行計算蒙皮動畫。骨骼動畫紋理相關的數據結構如下：

Struct AnimationTexture

//骨骼動畫紋理結構

{

//骨骼動畫數量

int animationCount;

//骨骼動畫數組

Animation anims[animationCount];

……

}

Struct Animation

//骨骼動畫結構

{

//骨骼動畫幀總數

int frameCount;

//骨骼動畫幀數組

AnimationFrame frames[frameCount];

……

}

Struct AnimationFrame

//骨骼動畫幀結構

{

//骨骼數量

int boneCount;

//骨骼變換矩陣數組

Matrix4x4 mats[boneCount];

……

}

在虛擬場景中，群體中每個個體會因為場景邏輯發生變化而更變播放的骨骼動畫種類，例如駐立、行走、攻擊等骨骼動畫，個體播放的骨骼動畫種類由邏輯線程控制。其他工作線程根據個體當前骨骼動畫已經播放的時間，計算個體當前播放的骨骼動畫幀數。在大規模場景中，群體數量十分龐大，這里需要充分利用其他工作線程并行加速計算。在進行場景渲染時，渲染線程將所有個體的骨骼動畫狀態，以及預采樣的模型和骨骼動畫數據上傳至GPU，由GPU批處理完成群體的蒙皮動畫計算與渲染。其中，渲染線程為每個個體設置一個四維向量，表示個體的骨骼動畫狀態，標記個體使用的骨骼動畫紋理數據片段。這個四維向量上傳至GPU后作為著色器的系統變量，為每個個體的著色器設置一個不同的參數，表示個體當前的骨骼動畫狀態。基于GPU蒙皮渲染的多線程加速算法流程如圖2所示。

圖2 基于GPU蒙皮渲染的多線程加速算法流程圖

本文提出基于GPU蒙皮渲染的多線程加速算法，利用GPU高并行能力完成場景中大規模群體動畫的蒙皮計算和渲染，同時加入CPU多線程技術提升群體動畫狀態的計算速度，大幅度降低CPU在蒙皮動畫計算上的性能消耗，為CPU模擬大規模群體行為騰出了大量的性能空間。

3 基于自主性群體行為和最優互相碰撞避讓的多線程加速算法

在場景中模擬大規模群體行為時，首先需要根據場景的布局以及群體的目標移動位置，使用尋路算法確定個體的初始移動速度；其次，所有個體以一個整體運動；最后，個體還要避免與其他個體以及場景障礙物發生碰撞。本文假設每個個體能夠獲取其他個體以及場景障礙物當前的位置和速度，先將自主性群體行為算法的力模型改進為速度模型，模擬個體跟隨群體的運動，使得個體能根據周圍環境極快地改變自身運動速度，再對個體使用多線程加速后的最優互相碰撞避讓算法，實現群體行為的碰撞避讓。基于自主性群體行為和最優互相碰撞避讓的多線程加速算法流程如圖3所示。

圖3 基于自主性群體行為和最優互相碰撞避讓 的多線程加速算法流程圖

3.1 基于自主性群體行為的速度模型算法

vc=Pcenter-Px

(2)

(3)

(4)

(5)

結合個體的尋路速度v0與群體速度偏量v′，考慮個體的最大移動速度vmax，個體的理想速度vpref的計算公式如下所示：

(6)

3.2 基于最優相互碰撞避讓的多線程加速算法

在大規模群體仿真場景中，由于群體數量非常多，個體以vpref作為最終速度模擬運動會造成個體之間頻繁發生碰撞。若使用物理引擎利用碰撞體模擬個體的碰撞，CPU將花費大量時間模擬個體的頻繁碰撞，導致大規模群體場景幀率很低。

為了降低CPU在碰撞模擬上的性能損耗，本文使用最優互相碰撞避讓算法代替物理引擎的碰撞模擬，實現大規模群體的碰撞避讓行為。同時，本文在最優互相碰撞避讓算法基礎上加入了多線程優化，加入了所有個體、障礙物的Kd-Tree并行計算優化。本文使用的最優互相碰撞避讓算法流程如圖4所示。

圖4 最優互相碰撞避讓的多線程加速算法流程圖

最優互相碰撞避讓算法[7]需要設置群體中每個個體的初始移動速度作為個體避讓的初始速度，本文使用個體的理想速度vpref作為最優互相碰撞避讓算法的輸入。最優互相碰撞避讓算法假設每個個體都知道其他個體的當前速度和位置，因此能夠預測個體何時會發生碰撞。對于個體之間的碰撞避讓，最優互相碰撞避讓算法將碰撞避讓的行為平分給每對個體，個體以最低限度的速度調整完成每對個體之間的碰撞避讓。對于個體和場景中靜態障礙物的碰撞避讓，最優互相碰撞避讓算法將由個體完全承擔碰撞避讓邏輯；對于個體和場景中動態障礙物的碰撞避讓，本文將動態障礙物當作最優互相碰撞避讓算法中的個體求解，與個體之間的碰撞避讓不同，個體和動態障礙物的碰撞避讓行為完全由個體來承擔。

最優互相碰撞避讓算法[7]需要先構建所有個體和障礙物的Kd-Tree，再計算每個個體的避讓速度。為了提升算法的運算速度，本文在最優互相碰撞避讓算法上加入了多線程優化，使用一個工作線程以固定頻率構建所有個體和障礙物的Kd-Tree，其他工作線程根據最近一次構建完成的Kd-Tree計算每個個體的避讓速度(見圖4)。這種改進會略微降低最優互相碰撞避讓算法的精度，導致場景中個體碰撞發生的次數提高，但是其他工作線程無需等待所有個體和障礙物的Kd-Tree構建完成，即可計算所有個體的避讓速度，提高最優互相碰撞避讓算法的運算效率。

4 實驗結果與分析

4.1 應用實例

本文在一款虛擬現實第一人稱射擊游戲中，應用基于多線程加速的大規模群體仿真方法。該游戲是基于Unity游戲引擎[12]和HTC Vive[13]頭戴式虛擬現實設備開發的，游戲場景包含大規模蟲群陷阱關卡，當玩家踏入陷阱區域，大規模蟲群從四周墻壁爬落，匯集成一個團隊，避開場景中的障礙物向玩家移動并攻擊，當蟲群靠近玩家后，蟲群會隨機向玩家飛躍進行空中攻擊。玩家可以使用槍械射擊或者腳踩的方式攻擊蟲子。游戲大規模蟲群陷阱的示意見圖5和圖6。

圖5 大規模蟲群陷阱(HTC Vive玩家視角)

圖6 大規模蟲群陷阱(Unity場景視角)

4.2 實驗環境

實驗使用1臺PC作為虛擬現實游戲運行的節點，連接HTC Vive頭戴式虛擬現實設備運行游戲。PC的硬件配置為Intel(R) Core(TM) i7- 6700HQ CPU @ 2.60 GHz，16 GB內存，NVIDIA GeForce GTX 1070圖形顯示卡。虛擬現實游戲的開發和運行環境為Microsoft Windows 10- 64 bit操作系統，Unity 5.5.1- 64 bit版本，HTC Vive虛擬現實設備。

4.3 實驗結果

本節從群體動畫渲染、群體行為模擬兩個方面與Unity游戲引擎進行對比實驗，驗證大規模群體仿真方法的可行性。通過對比最優互相碰撞避讓算法多線程加速前后的性能和碰撞次數，驗證最優互相碰撞避讓多線程加速算法的有效性。

對于群體動畫渲染，本文在實驗中分別使用Unity游戲引擎的Mecanim動畫系統[14]，以及基于GPU蒙皮渲染的多線程加速算法渲染蟲群，根據蟲群渲染的CPU與GPU耗時證明方法的可行性。

表1給出蟲群數量為200、400、600、800、1 000五種情況下，使用Unity Mecanim動畫系統，以及GPU蒙皮渲染多線程加速算法實現蟲群動畫渲染的CPU耗時統計表。在CPU耗時統計中，Unity Mecanim動畫系統比GPU蒙皮渲染的多線程加速算法多了蒙皮動畫計算的步驟。

表1 蟲群動畫渲染CPU耗時統計表 ms

圖7、圖8分別給出了蟲群數量為200、400、600、800、1 000五種情況下，使用Unity Mecanim動畫系統，以及GPU蒙皮渲染多線程加速算法渲染蟲群動畫的CPU和GPU耗時折線圖。

圖7 蟲群動畫渲染CPU耗時折線圖

圖8 蟲群動畫渲染GPU耗時折線圖

由圖7可知，GPU蒙皮渲染多線程加速算法的CPU耗時遠低于Unity Mecanium動畫系統。這是因為GPU蒙皮渲染多線程加速算法將蟲群動畫的蒙皮計算由CPU轉交給GPU處理，同時利用CPU多線程加速計算動畫狀態，因此GPU蒙皮渲染多線程加速算法的CPU耗時大幅度降低，大約只有Unity Mecanim動畫系統的20%。

由圖8可知，在蟲群數量較小時，Unity Mecanim動畫系統在GPU上的耗時略低于GPU蒙皮渲染多線程加速算法。這是因為GPU蒙皮渲染多線程加速算法需要在GPU完成蟲群動畫的蒙皮計算。隨著蟲群數量增多，GPU蒙皮渲染多線程加速算法充分利用GPU高并行計算的特性，GPU耗時基本不變；Unity Mecanim動畫系統逐個渲染蟲群，GPU耗時隨著蟲群數量的增加線性上升，逐漸超過GPU蒙皮渲染多線程加速算法的GPU耗時。

綜合分析可知，基于GPU蒙皮渲染的多線程加速算法應用于大規模群體仿真時，可以顯著降低CPU與GPU在群體動畫計算和渲染上的耗時。

對于群體行為模擬，本文在實驗中分別使用Unity游戲引擎內置的物理系統[15]、導航系統[16]，以及基于自主性行為、最優互相碰撞避讓的多線程加速算法模擬蟲群行為，根據蟲群行為模擬的CPU耗時與蟲群碰撞次數證明方法的可行性。

表2給出蟲群數量為200、400、600、800、1 000五種情況下，使用Unity游戲引擎內置的物理系統、導航系統，以及基于自主性群體行為、最優互相碰撞避讓的多線程優化算法的CPU耗時統計表。其中，前者包括Unity導航系統和Unity物理系統兩個步驟：Unity導航系統完成每個個體到目標點的尋路計算；Unity物理系統完成群體之間的碰撞模擬計算。本文使用的群體行為模擬算法分為自主性群體行為的速度模型算法和最優互相碰撞避讓多線程加速算法兩個步驟。自主性群體行為的速度模型算法完成群體行為的模擬計算，最優互相碰撞避讓多線程加速算法完成群體避讓行為的模擬計算。

表2 蟲群行為模擬CPU耗時統計表 ms

圖9、圖10分別給出蟲群數量為200、400、600、800、1 000五種情況下，使用Unity物理系統、導航系統，以及基于自主性群體行為、最優互相碰撞避讓多線程加速算法的CPU耗時和碰撞發生次數折線圖。

圖9 蟲群行為模擬CPU耗時折線圖

圖10 蟲群行為模擬碰撞發生次數折線圖

由圖9可知，使用Unity物理系統和導航系統模擬蟲群行為的CPU耗時，隨著蟲群數量的增加而大幅度增長。使用基于自主性群體行為和最優互相碰撞避讓的多線程加速算法模擬蟲群行為的CPU耗時，隨著蟲群數量的增加而線性增長，且遠低于使用Unity物理系統和導航系統的方法，可以在虛擬場景中高幀率模擬大規模的群體行為。

結合圖9和圖10可知，使用Unity物理引擎和導航系統的方法，在群體數量較多的情況下，CPU耗時和碰撞發生次數都很高，而基于自主性群體行為和最優互相碰撞避讓的多線程加速算法在保證場景高幀率的前提下，場景中群體每幀發生碰撞的次數也很少，證明方法的高精度性和高效性。

最后，本文通過實驗比對最優互相碰撞避讓算法多線程加速前后的CPU耗時和蟲群碰撞次數，證明本文改進最優互相碰撞避讓算法的可行性。圖11、圖12分別給出蟲群數量為200、400、600、800、1 000五種情況下，最優互相碰撞避讓算法多線程加速前后CPU耗時和碰撞發生次數折線圖。

圖11 最優互相碰撞避讓算法多線程加速前后 CPU耗時折線圖

圖12 最優互相碰撞避讓算法多線程加速前后 碰撞發生次數折線圖

結合圖11和圖12可知，本文提出的最優互相碰撞避讓多線程加速算法，以降低碰撞避讓的精度為代價，有效地提升了算法效率。最優互相碰撞避讓多線程的加速算法，無需等待所有個體和障礙物的Kd-Tree構建，算法耗時大約為改進前的60%。雖然碰撞避讓的精度有所下降，碰撞發生次數大約是原始算法的2倍，但是碰撞次數與蟲群數量的比例仍然很低，碰撞發生次數的增多幾乎不影響群體仿真的效果。

5 結 語

面向大規模群體場景，本文設計并實現了一種基于多線程加速的群體仿真方法，提升大規模群體仿真中，群體動畫渲染和群體行為模擬的性能。針對群體動畫渲染，本文改進GPU蒙皮渲染算法，在使用GPU加速群體蒙皮動畫計算的基礎上，利用CPU多線程加速群體的動畫狀態計算，進一步提升群體動畫渲染的效率；針對群體行為模擬，本文將自主性群體行為算法修改為速度模型，結合多線程優化后的最優互相碰撞避讓算法，實現群體之間的碰撞避讓，提升群體行為模擬的效率。實驗結果表明，本文提出的基于多線程加速的大規模群體仿真方法可以很好地與游戲引擎結合，在復雜場景中高效地實現大規模群體仿真。未來方法將繼續優化，以適應群體規模更大，邏輯更加復雜的應用場景。