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

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

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

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

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

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

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

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

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