并行人群仿真關(guān)鍵算法研究.pdf

1、人群仿真在社會群體安全、建筑設(shè)計、緊急疏散、教育培訓(xùn)、軍事演練、數(shù)字娛樂、歷史場景重現(xiàn)等方面具有廣泛的應(yīng)用價值。越來越多從事虛擬人研究的學(xué)者開始關(guān)注人群仿真技術(shù)及相關(guān)算法的研究。
　　大規(guī)模人群仿真的研究具有重要的社會意義，主要包括兩個方面的研究目標：如何提高人群仿真的真實性(包括行為真實性和動畫視覺真實性)和如何提高人群仿真的實時性(即在擴大人群規(guī)模的同時提高仿真的效率)。前者可以通過對虛擬環(huán)境建模、人群行為模型、人群運動建模等

2、問題的研究來實現(xiàn)，后者則可通過對人群實時渲染技術(shù)、人群仿真系統(tǒng)結(jié)構(gòu)設(shè)計、并行人群仿真相關(guān)算法等問題的研究來實現(xiàn)。
　　在某一特定仿真真實性的前提下實現(xiàn)大規(guī)模人群仿真的實時性是當前面臨的難題。為此，本文采用并行計算的理論方法，利用現(xiàn)有的多核 CPU及多核GPU的硬件環(huán)境，實現(xiàn)了高性能的并行人群仿真。論文主要從并行人群仿真的任務(wù)劃分算法研究、并行人群動畫研究和并行人群仿真體系結(jié)構(gòu)研究三個方面對高性能人群仿真技術(shù)進行了深入的研究。

3、>　?。?）任務(wù)劃分算法研究是并行人群仿真的關(guān)鍵問題之一，主要分為兩個研究分支：基于個體分組的任務(wù)劃分方法和基于空間區(qū)域分割的任務(wù)劃分方法。
　　本文提出了兩種基于圖分割的個體分組的任務(wù)劃分方法：（a）在基于MST的連通圖方法中，首先通過個體的興趣區(qū)域交叉構(gòu)建無向連通圖子圖集，對Agent平面坐標點集生成的最小生成樹進行冗余邊剔除，求得子圖間的最小連通邊集；然后通過合并子圖集與最小連通邊集得到子圖集的最小無向連通圖；最后對無向連通

4、圖進行 K路分割以達到任務(wù)劃分目標。該算法通過最小生成樹構(gòu)建連通圖可有效減少任務(wù)劃分的運算量，使用 GPU求解又能保證算法的性能，可以在保證較低的分區(qū)代價的前提下達到較高的運算性能，同時可克服傾斜分布的群體分區(qū)執(zhí)行性能較均勻分布偏低的不足。（b）在基于Delaunay的連通圖方法中，首先通過 GPU計算 K-AOI邊集，接著通過Delaunay算法求得平面?zhèn)€體頂點集的Delaunay邊集，然后通過合并 K-AOI邊集和 Delaunay

5、邊集的方法構(gòu)建無向連通圖。最后采用 K路無向圖分割方法實現(xiàn)任務(wù)的劃分。兩種方法相較現(xiàn)有其他個體分組方法都具有較好的劃分代價及執(zhí)行性能。兩種算法能夠有效應(yīng)用于平坦開闊場景的并行人群仿真。
　　本文提出一種基于環(huán)境結(jié)構(gòu)理解的空間區(qū)域分割的任務(wù)劃分方法，以解決現(xiàn)有基于區(qū)域的任務(wù)劃分算法將環(huán)境視為平面，不適合于復(fù)雜多層次仿真場景的問題。通過采用基于區(qū)域的劃分思路，引入環(huán)境結(jié)構(gòu)因素，使得所提自適應(yīng)任務(wù)劃分算法適用于多層次復(fù)雜環(huán)境，首先自動讀

6、取場景模型并通過理解轉(zhuǎn)換為連通鄰接區(qū)域集，然后對區(qū)域進行快速粗粒度劃分，自然消除了被障礙隔離的相鄰區(qū)域個體間的關(guān)聯(lián)計算，大大減少了節(jié)點間通信量，使之更適合于大規(guī)模人群仿真應(yīng)用。
　?。?）在并行人群動畫方面，本文提出了一種基于運動捕捉的GPU人群動畫方法。高質(zhì)量的人群渲染效果是大規(guī)模人群實時仿真的關(guān)鍵研究內(nèi)容，仿真的最終目的是呈現(xiàn)給用戶感性的視覺認知。個體模型高度復(fù)雜的人群動畫渲染成為大規(guī)模人群仿真面臨的問題。通過對運動文件的預(yù)處

7、理使得運動數(shù)據(jù)在個體的運動狀態(tài)更新和幾何變換運算方面適合在 GPU環(huán)境下進行并行處理，通過采用細分曲面的方式自動生成運動捕捉模型骨架對應(yīng)的不同細分層次的幾何網(wǎng)格模型，實驗結(jié)果顯示方法對復(fù)雜幾何模型個體表示的大規(guī)模人群具有高效的渲染速度。
　?。?）本文提出一種混合式并行人群仿真體系結(jié)構(gòu)，其中包括 CN計算節(jié)點、CC主控節(jié)點和Viewer視景節(jié)點，并設(shè)計了三種節(jié)點各自承擔的任務(wù)及相互之間的通訊關(guān)系。并行群體仿真體系結(jié)構(gòu)主要包括四種：

8、基于 CPU的多線程并行，基于GPU的流式并行，基于分布式的多機并行以及基于GPU與分布式的混合并行方式。混合并行既滿足可擴展性需求，又能充分挖掘每個計算節(jié)點的性能,已成為并行群體仿真領(lǐng)域的重要研究分支。群體仿真研究可基于Agent或流體進行，考慮到基于 Agent的群體能夠更豐富的表達個體的特性和行為方式，相關(guān) AI算法亦可用于提高 Agent的智能，因此本文基于 Agent方式進行群體仿真研究。分布式仿真實驗表明，混合式體系結(jié)構(gòu)對室