畢業(yè)論文設(shè)計(jì)基于流體力學(xué)的全局人群規(guī)劃算法

1、 II摘要隨著數(shù)字化人體運(yùn)動仿真技術(shù)的日趨成熟，尤其是其應(yīng)用的迅速推廣，大規(guī)模人群運(yùn)動 仿真技術(shù)開始成為這一研究領(lǐng)域的熱點(diǎn)。大規(guī)模人群運(yùn)動仿真技術(shù)包括：人群運(yùn)動建模和人 群運(yùn)動計(jì)算機(jī)可視化兩部分。本文展現(xiàn)了一個(gè)基于流體力學(xué)的實(shí)時(shí)全局人群運(yùn)動模型，在本 模型中，一個(gè)動態(tài)的勢場同時(shí)解決了全局運(yùn)動規(guī)劃和移動的障礙物的問題，這個(gè)方法對于處 理不需要精確的碰撞回避的大規(guī)模人群行動特別有效。在大規(guī)模人群仿真問題中，對大量虛擬人的路徑進(jìn)行規(guī)劃占用大量的計(jì)算資源，通常無 法實(shí)現(xiàn)實(shí)時(shí)的處理。GPU編程技術(shù)的出現(xiàn)提供了解決這個(gè)問題的計(jì)算平臺。同時(shí)，為了充 分利用GPU的并行處理能力，需要重新設(shè)計(jì)人群路徑規(guī)劃的算法

2、。近年來，這種基于流體 力學(xué)的人群路徑規(guī)劃算法被發(fā)現(xiàn)適用于并行處理。通過將人群路徑規(guī)劃問題轉(zhuǎn)換為計(jì)算一個(gè) 流場的勢能分布，我們可以給出對于一組虛擬人中的每個(gè)個(gè)體的最優(yōu)化路徑。其移動的路徑 取決于地勢、人群密度、心理因素等多個(gè)因素。本課題的目的是實(shí)現(xiàn)一個(gè)針對大規(guī)模人群仿 真問題的人群全局路徑規(guī)劃算法。提供一個(gè)簡明的編輯界面，用于對虛擬環(huán)境和人群行為進(jìn) 行編輯。本文主要進(jìn)行了以下工作：分析了決定人群流向的勢場中幾個(gè)決定性因素：在流場的勢能分布計(jì)算中，環(huán)境和心 理等因素對路徑的選擇有著明顯的作用，其中地形速度、人群速度、環(huán)境和心理所決定路徑 的不爽度以及前進(jìn)的消耗都通過一定的計(jì)算對勢場作用。介紹了

3、GPU 實(shí)現(xiàn)部分的原理、采用的數(shù)據(jù)結(jié)構(gòu)以及實(shí)現(xiàn)的方法。關(guān)鍵字：GPU人群，運(yùn)動規(guī)劃AbstractWith the digital human motion simulation technology matures, particularly in the rapid promotion of its application, large-scale population movements that simulation technology has become a hot area of research. Simulation technique of large-scale pop

4、ulation movement, including: population movement sporting computer modeling and visualization of the crowd in two parts. This article shows a real-time based on fluid dynamics model of the overall population movement, in this model, a dynamic potential field at the same time addressing the global mo

5、tion planning and the problem of moving obstacles, this method does not require precise handling to avoid a big collision Action effective population size. The crowd in the large-scale simulation problems, a large number of virtual people to plan the path occupied by a large number of computing reso

6、urces, often can not deal with real-time. GPU programming technology provides a solution to the problem of computing platforms. At the same time, in order to take full advantage of GPU parallel processing capabilit,ythe need to re-design crowd path planning algorithms. In recent years, groups of peo

7、ple based on CFD was found in the path planning algorithm for parallel processing. Path through the planning groups for the purpose of calculating a conversion of potential energy distribution of the flow field, we can give to a group of virtual people in the optimization of each individual path. De

8、pends on its path of movement of the terrain, population density , a number of factors such as psychological factors. The purpose of this project is to achieve a massive crowd for crowd simulation algorithm for global path planning. Editors provide a concise interface for virtual environment and edi

9、t the crowd behavior.In this paper, the following work:1 Analysis of the decision of the potential flow of the crowd of several decisive factors: the potential energy in the flow field of distributed computing, environmental and psychological factors such as the choice of the path there was a clear

10、role, in which the speed of the terrain, people speed, determined by environmental and psychological degrees of sorts, as well as the path forward through the consumption of a certain role in the calculation of the potential field.2 introduced the GPU to achieve some of the principles of the data st

11、ructure used and the methodsto achieve.Keywords: GPU, Crowd，s Motion Planning II I目錄 TOC o 1-5 h z HYPERLINK l bookmark2 o Current Document 第 1 章 引言 1 HYPERLINK l bookmark4 o Current Document 1.1論文背景 1 HYPERLINK l bookmark6 o Current Document 全文結(jié)構(gòu) 1 HYPERLINK l bookmark8 o Current Document 第 2 章 相關(guān)技

12、術(shù) 2 HYPERLINK l bookmark10 o Current Document 2.1人群運(yùn)動仿真 2人群運(yùn)動建模 3人群運(yùn)動可視化 3 HYPERLINK l bookmark12 o Current Document 2.3 Direct 3D概述5 HYPERLINK l bookmark14 o Current Document 第3章 基于流體力學(xué)的全局人群規(guī)劃算法6 HYPERLINK l bookmark16 o Current Document 算法概述 6 HYPERLINK l bookmark18 o Current Document 速度方程 9人群密度場

13、10地形速度 11流動速度 12中密度速度 12 HYPERLINK l bookmark20 o Current Document 單元消耗場 12 HYPERLINK l bookmark22 o Current Document 動態(tài)勢場建設(shè) 13快速行進(jìn)法 13有限差分法 14動態(tài)勢場 15 HYPERLINK l bookmark24 o Current Document 第 4 章全局人群規(guī)劃算法的實(shí)現(xiàn) 16 HYPERLINK l bookmark26 o Current Document GPU上實(shí)現(xiàn)人工智能路徑尋找 16全局路徑尋找 16局部導(dǎo)航和回避 20 HYPERLIN

14、K l bookmark28 o Current Document 檢驗(yàn)與對比 26 HYPERLINK l bookmark30 o Current Document 算法檢驗(yàn) 26高地檢驗(yàn) 26高密度人群分散檢驗(yàn) 29 HYPERLINK l bookmark32 o Current Document 第 5 章 結(jié)論與展望 33 HYPERLINK l bookmark34 o Current Document 結(jié)論 33 HYPERLINK l bookmark36 o Current Document 展望 34致謝錯. 誤！未定義書簽。 HYPERLINK l bookmark38

15、 o Current Document 參考文獻(xiàn) 34 第 1 章 引言論文背景在真實(shí)世界中，人群是無處不在的，在模擬現(xiàn)實(shí)的仿真中，他們是必要互動環(huán)境。對于 人群模型的研究同樣應(yīng)用于計(jì)算機(jī)圖形以外的學(xué)科，例如心理學(xué)、交通運(yùn)輸學(xué)，以及建筑學(xué)。 在本文中，我們側(cè)重一定規(guī)模的人群的路徑研究，人群具有相同的目標(biāo)，那些擁有不同目標(biāo) 的問題不在本文的研究范圍以內(nèi)。由于人群的行為是復(fù)雜和微妙的，例如人對路徑的偏好，以及環(huán)境對人們選擇路徑的影 響，所以實(shí)時(shí)人群仿真是比較困難的。一個(gè)人群模型要考慮到諸多限制性因素，這里有自身 以及環(huán)境上的，如邊界和人與人之間的擁擠度的影響。另外，該模型還要考慮到智能路徑規(guī) 劃，

16、即通過不斷變化的環(huán)境因素，以及其他人運(yùn)動的位置，來實(shí)時(shí)的調(diào)整自己的路線，以此 來解決路徑上的阻塞等問題。目前，幾乎所有的前期工作都是基于主體模型的，也就是說，運(yùn)動的計(jì)算分別針對每一 個(gè)個(gè)體?；谥黧w模型有吸引力的理由有以下幾個(gè)因素：1 真正的人群運(yùn)動中，每個(gè)個(gè)體的 運(yùn)動都由自身決定。這種方式可以解決每個(gè)人所遇到的獨(dú)特的情況，如：在能見度范圍里的 人群擁擠度、突然顯現(xiàn)的障礙物和其他環(huán)境性因素。2 不同的仿真參數(shù)可以為群體中的個(gè)體、 復(fù)雜多變的行為提供定義。但是，基于主體的模型也有缺點(diǎn)，全文結(jié)構(gòu)本文分三部分對主題進(jìn)行了討論： 在第二章中，介紹了算法和其實(shí)現(xiàn)的相關(guān)技術(shù)，首先討論了人群運(yùn)動仿真中的建模

17、和可 視化。在第三章中，具體的介紹了基于流體力學(xué)的全局人群規(guī)劃算法，首先我們對算法進(jìn)行了 概述，然后，針對幾種控制方程中的主要對象進(jìn)行了討論，接著介紹了單元消耗場的由來和 作用，隨后介紹了如何構(gòu)建出一個(gè)動態(tài)勢場。在第四章中，介紹了全局人群規(guī)劃算法的GPI實(shí)現(xiàn)方式，在此簡要的引入了一些CPUt的實(shí)現(xiàn)方式，然后介紹了群居路徑尋找和一些導(dǎo)航和不爽區(qū)域回避的問題第 2 章 相關(guān)技術(shù)人群運(yùn)動仿真大規(guī)模人群運(yùn)動仿真，就是研究人群在各種環(huán)境、情節(jié)下的運(yùn)動特征與規(guī)律，建立大規(guī) 模人群運(yùn)動的仿真模型，并在計(jì)算機(jī)生成空間（虛擬環(huán)境）中以三維的方式逼真地展示大規(guī) 模人群的運(yùn)動過程。大規(guī)模人群運(yùn)動仿真技術(shù)，提供了人群

18、運(yùn)動的分析和演示工具，可應(yīng)用 的領(lǐng)域相當(dāng)廣泛。作為一種分析工具，大規(guī)模人群運(yùn)動仿真技術(shù)可以應(yīng)用于公共安全領(lǐng)域，如船舶、飛機(jī) 等大型交通工具的設(shè)計(jì)，體育場館、地鐵站等大型公共設(shè)施的設(shè)計(jì)等等。以體育場館為例， 應(yīng)用大規(guī)模人群運(yùn)動仿真技術(shù)，可以根據(jù)體育場館的設(shè)計(jì)規(guī)模，模擬球迷退場等常規(guī)情景下 的大規(guī)模人群運(yùn)動，輔助分析場館的走廊寬度、出口數(shù)目和出口位置等設(shè)計(jì)是否合理；可以 模擬球迷發(fā)生沖突、火災(zāi)、恐怖襲擊等非常規(guī)情景下的人群運(yùn)動，輔助建立緊急情況下人員 的疏散方案、合理布置消防器材、分配警力；還可以作為場館管理人員進(jìn)行消防、反恐等安 全方案預(yù)演及培訓(xùn)的輔助工具。與傳統(tǒng)方法相比，以大規(guī)模人群運(yùn)動仿真技

19、術(shù)作為人群運(yùn)動 的分析工具，具有直觀、靈活、高效、經(jīng)濟(jì)和無人員安全風(fēng)險(xiǎn)等諸多優(yōu)點(diǎn)。作為一種演示工具，大規(guī)模人群運(yùn)動仿真技術(shù)能夠生成逼真的人群運(yùn)動動畫，如地鐵站、 商場中的人流，體育場館中歡呼雀躍的人群等，提高虛擬場景的視覺逼真性。因此，可以應(yīng) 用于娛樂游戲、電影電視媒體、國防研究等等。實(shí)現(xiàn)大規(guī)模人群運(yùn)動仿真，需要解決兩項(xiàng)關(guān)鍵技術(shù)問題。其一是，研究并建立大規(guī)模人 群運(yùn)動的仿真模型，實(shí)現(xiàn)對人群運(yùn)動的模擬；其二是，研究大規(guī)模人群運(yùn)動的可視化技術(shù)， 即如何將大規(guī)模人群運(yùn)動以三維的方式逼真地展現(xiàn)到虛擬場景中。大規(guī)模人群運(yùn)動仿真模型的研究工作才剛剛起步，還處于初步的探索階段。由于人群運(yùn) 動的機(jī)制相當(dāng)復(fù)雜，

20、并伴有一定的不確定性，目前還沒有完整、通用的人群運(yùn)動仿真模型。大規(guī)模人群運(yùn)動可視化技術(shù)，主要涉及大規(guī)模三維數(shù)據(jù)的實(shí)時(shí)渲染。雖然目前計(jì)算機(jī)硬件，尤其是圖形硬件的性能在以很快的速度增長，但隨著人群規(guī)模和場景規(guī)模的擴(kuò)大，實(shí)時(shí) 渲染大規(guī)模模型仍然相當(dāng)困難。國內(nèi)外許多研究者曾試圖通過細(xì)節(jié)層次技術(shù)、點(diǎn)渲染技術(shù)等 嘗試解決這個(gè)問題。人群運(yùn)動建模人群運(yùn)動模型，是對現(xiàn)實(shí)世界中人群行為特征的抽象和數(shù)學(xué)描述。建立通用的人群運(yùn)動 模型具有很大難度。一方面，人是自然界最復(fù)雜的智能體，日常生活中的每一件小動作，如 喝水、購物，其背后都隱含著復(fù)雜的感知和決策過程，在這些方面人類對于自身認(rèn)識還相當(dāng) 不夠；另一方面，現(xiàn)實(shí)世界人

21、群中的每個(gè)人都是一個(gè)獨(dú)立的智能體，即使擁有共同的目標(biāo)， 每個(gè)人的立場、性格也不相同，甚至對于共同目標(biāo)的認(rèn)識也不盡相同，因此，很難抽象出隱 藏在復(fù)雜現(xiàn)象背后的共性特征。人群運(yùn)動可視化大規(guī)模人群運(yùn)動仿真，需要在計(jì)算機(jī)中以三維的方式逼真地繪制人群運(yùn)動的仿真結(jié)果。 逼真的三維人體模型至少包含5,000個(gè)面片，利用常規(guī)方法渲染成百上千，甚至上萬個(gè)三維 人體模型，在現(xiàn)有機(jī)器硬件條件下幾乎不可能。然而，大規(guī)模三維數(shù)據(jù)的實(shí)時(shí)渲染是計(jì)算機(jī) 圖形學(xué)領(lǐng)域研究較為成熟的分支之一，其中的很多技術(shù)可以借鑒。下面本文將介紹幾種能夠 用于人群運(yùn)動可視化的技術(shù)。1 細(xì)節(jié)層次技術(shù)細(xì)節(jié)層次技術(shù)（LOD是通過降低單個(gè)模型的幾何復(fù)雜度

22、，從而降低單個(gè)模型的幾何渲 染時(shí)間，以達(dá)到提升可渲染的模型規(guī)模的目的。通過建模軟件得來的人體模型，目前只有固 定的幾何復(fù)雜度。雖然可以通過人工的方式，將復(fù)雜度做得很低，但是，由于人體視覺的苛 刻要求，當(dāng)模型離人眼很近的時(shí)候，簡單模型的真實(shí)感不夠強(qiáng)，而當(dāng)模型離人眼很遠(yuǎn)，模型 的復(fù)雜度卻還可以更低（但不可以消失）。有一種比較簡單的做法是針對同一個(gè)模型，存儲 幾個(gè)具有不同幾何復(fù)雜度的代替品，然后根據(jù)場景中模型與視點(diǎn)間的距離來判斷在該場景應(yīng)當(dāng)使用哪一個(gè)，這種做法就是靜態(tài)LOD技術(shù)。靜態(tài)LOD的方式比較簡單，但存儲多個(gè)代替 品的方法對內(nèi)存提出了苛刻要求。而且，在不同的代替品切換的時(shí)候，往往會有視覺上的突

23、 變（Pop-up現(xiàn)象，不夠連續(xù)和真實(shí)。動態(tài)LOD技術(shù)則可以避免這些問題。它對單個(gè)模型通 過計(jì)算，建立一個(gè)具有多級復(fù)雜度的、新的模型表達(dá)方式多分辨率模型，以“原始模型計(jì)算記錄算法”的方式構(gòu)成。給定一種復(fù)雜度，就能夠找到對應(yīng)的合適的代替品。而且 在相鄰的代替品之間進(jìn)行切換的時(shí)候，可以做到視覺和幾何數(shù)據(jù)的平滑過渡。動態(tài)LOD技術(shù)的突出代表漸進(jìn)網(wǎng)格（ProgressivesheS，是90年代中后期由微軟的 Huges Hopp等人在格網(wǎng)（mesh優(yōu)化的基礎(chǔ)上提出。主要想法是，對一個(gè)由三角面片建模 出來的幾何模型，每次通過去除這個(gè)模型當(dāng)中的三角形的一條邊（刪除因此而消失的頂點(diǎn)和 面片）、并對剩下的簡化

24、幾何體進(jìn)行優(yōu)化，持續(xù)操作并形成一個(gè)多分辨率模型。除去特定的 優(yōu)化部分，這種思想被許多人采納，并形成了許多其它種類的LOD算法。1997年，卡內(nèi)基 梅隆大學(xué)（CMU的Garland & Heckbe等人就在這種思想的指導(dǎo)下，使用一種二次誤差測 度（quadric error metric作為指導(dǎo)模型簡化和優(yōu)化的工具，獲得了很好的時(shí)空效率，簡化效 果也非常好，具有很高的研究價(jià)值和實(shí)用價(jià)值7,8。其他LOD算法參見文獻(xiàn)6,21,10,17,2,24,14在人群運(yùn)動仿真中，人群在場景中的位置通常情況下具有很大的流動性丄OD技術(shù)不僅 降低了模型的復(fù)雜度，而且動態(tài)LOD技術(shù)還提供了平滑的視覺過渡和對模型的

25、動態(tài)控制， 非常適合應(yīng)用于人群運(yùn)動的三維可視化。此外，動態(tài)LOD技術(shù)發(fā)展了許多年，其中許多成 熟的算法稍加修改即可應(yīng)用的人群模型上。利用動態(tài)LOD技術(shù)，在當(dāng)前主流PC機(jī)上，可渲 染的人群規(guī)模大約在100左右。2 圖像渲染技術(shù)圖像渲染與普通的基于實(shí)體造型的渲染方式不同，它以一系列場景的圖像為輸入，通過 合成產(chǎn)生不同視角的新圖像輸出?；趫D像的渲染技術(shù)在目前來說，比基于實(shí)體造型的技術(shù) 有很多優(yōu)勢。它與場景的復(fù)雜度無關(guān)，使得復(fù)雜場景的實(shí)時(shí)交互問題得到解決；此外，由于 它使用的是預(yù)先渲染好的圖像，或者是真實(shí)場景的照片，對于那些通過實(shí)體幾何造型難以得 到的或者根本就不可能得到的真實(shí)場景，不管其復(fù)雜度有多

26、高，圖像渲染都能工作。然而， 由于當(dāng)前的圖像渲染技術(shù)依賴于對已有圖像的采樣和插值產(chǎn)生新的圖像，當(dāng)這種采樣不充分 的時(shí)候，就會發(fā)生不可思議的錯誤。例如，如果圖像過少，就難以產(chǎn)生在場景里面的高頻部 分，比如說高光效果理論上利用圖像渲染技術(shù)以2.5維的方式對人群運(yùn)動仿真結(jié)果進(jìn)行三維可視化表達(dá)，可渲染的人群規(guī)模不受限制，雖然視覺逼真性不夠，并且需要作較多的預(yù)處理工作。3點(diǎn)渲染技術(shù)點(diǎn)渲染技術(shù)（PSR打破了模型只用多邊形（尤其是三角形）進(jìn)行渲染的模式。在點(diǎn)渲染技 術(shù)中，模型是以一系列緊密的面的采樣點(diǎn)來表示的。這些采樣點(diǎn)從相互正交的方向采樣獲得， 包含顏色信息、深度信息、法線信息，并允許同Z緩存復(fù)合、Pho

27、 ng光照和陰影等技術(shù)共存。 同圖像渲染相似的是，它根據(jù)物體的多個(gè)方向的采樣數(shù)據(jù)，合成各種新視角下的幾何模型和 渲染結(jié)果。不同之處在于，點(diǎn)渲染中，每個(gè)頂點(diǎn)攜帶了比圖像象素更多的信息，而且，采樣 點(diǎn)的顏色與采樣的視角方向無關(guān)（view-i ndepe ndent）使用點(diǎn)作為渲染的圖元是因?yàn)檫@種方法簡單、速度快。頂點(diǎn)能夠很快地被畫出來，不需 要多邊形剪切，掃描轉(zhuǎn)換，紋理映射或凹凸貼圖，從而避免了多邊形渲染時(shí)大量的計(jì)算開銷。 而且采樣點(diǎn)很少有冗余，不像圖像渲染中的渲染圖元往往需要采樣多次，所以點(diǎn)渲染的方式 既使用了大量內(nèi)存，又充分有效地利用了這些內(nèi)存?；邳c(diǎn)渲染的算法包括點(diǎn)采樣和渲染兩個(gè)部分。點(diǎn)采樣

28、的目標(biāo)是從合適的模型表面位置， 抽取出合適數(shù)目和合適信息的點(diǎn)；而渲染部分解決點(diǎn)的可視化剪切，從三維點(diǎn)到二維圖像上 的映射，陰影計(jì)算，及尋找和修補(bǔ)點(diǎn)畫的方式帶來的“視覺漏洞”等問題。實(shí)際中的點(diǎn)渲染，在現(xiàn)在的硬件設(shè)施上，速度比多邊形渲染高出幾個(gè)數(shù)量級，與圖像渲 染相比，視覺效果更為逼真。Direct 3D 概述Direct 3E是基于微軟的通用對象模式COM（Common Object Mode的3D圖形AP。它 是由微軟（Microsoft 手樹立的3D AP規(guī)范。Direct3D是微軟公司DirectX SD集成開發(fā)包 中的重要組成部分，適合多媒體、娛樂、即使3D動畫等廣泛和實(shí)用的3D圖形計(jì)算

29、0 Direct3D 可以被看做是應(yīng)用程序和圖形設(shè)備（3D硬件）之間的中介。應(yīng)用程序、Direct3D和圖形設(shè)備 之間的關(guān)系如圖2-3-1。圖中Direct3D所表示的是Direct3D中已定義的供程序員使用的 Direct3D接 口和函數(shù)的集合。這些接口和函數(shù)代表了當(dāng)前版本的Direct3D所支持的全部特性。 但是Direct3D支持某種特性，并不意味著圖形硬件（顯卡）也能支持它。圖 2-3-1如上圖所示，在Direct3和圖形硬件之間有一層中介 硬件抽象層（HAL Hardware Abstraction Lay。Direct3D不能直接作用于圖形設(shè)備，因?yàn)槭忻嫔系娘@卡種類太多，并且 每種

30、顯卡都又有不同的性能和處理事件的方式。例如，兩種不同顯卡實(shí)現(xiàn)清屏的方式是可能 不同的。因此，Direct3D要求設(shè)備制造廠商實(shí)現(xiàn)HAL HAL是一組只是設(shè)備執(zhí)行某種操作的 特殊設(shè)備代碼的集合。用這種方法，Direct3D避免了必須去了解某個(gè)設(shè)備的特殊細(xì)節(jié)，能夠 獨(dú)立于設(shè)備硬件。設(shè)備制造商在HAL中實(shí)現(xiàn)他們的產(chǎn)品所支持的所有特性。HAL將不會實(shí)現(xiàn)那些Direct3D 支持但硬件產(chǎn)品不支持的特性。調(diào)用一個(gè)HAL中沒有實(shí)現(xiàn)的Direct3D的函數(shù)將會出錯，除非 它是定點(diǎn)處理操作，因?yàn)檫@個(gè)功能可以由軟件模擬來實(shí)現(xiàn)。因此當(dāng)使用某些僅由市面上少數(shù) 顯卡所支持的高級特性時(shí)，必須檢測一下設(shè)備是否支持。第3章基

31、于流體力學(xué)的全局人群規(guī)劃算法3.1算法概述在本章節(jié),我們來概述如何建立一個(gè)人群動態(tài)的數(shù)學(xué)模型。那么，我們通過一個(gè)例子來引出在本模型中我們所要涉及到的一些環(huán)境因素和將要解決的問 題。首先，人群流動的首要動力是人們要有一個(gè)目的地或者目標(biāo)，目標(biāo)可以是具體的，例如 某大街某號，目標(biāo)也可以是動態(tài)的，如追蹤某個(gè)目標(biāo)。人群的運(yùn)動若是沒有定義一個(gè)目標(biāo) 如在大街上漫無目的的閑逛這種情況并不適合本模型。這里，目標(biāo)的選擇是由操作者設(shè)定 的一個(gè)外部的參數(shù)，也就是以后要談及的零勢能點(diǎn)。第二，當(dāng)每個(gè)人在一個(gè)RX R大小的地 理環(huán)境中行動時(shí)，隨著人群要向某個(gè)已經(jīng)設(shè)定的地理目標(biāo)運(yùn)動的過程中，下一個(gè)最重要的需 要考慮的是他們的

32、速度。在通常情況下，人移動的最高速度需要考慮到一些環(huán)境條件。例如， 居住在城市里的市民就可以隨性的按通常速度步行，而一支部隊(duì)里的戰(zhàn)士可能需要以一個(gè)更 快的速度來沖鋒。所以環(huán)境可以在許多方面影響速度：如斜率的大小使人們增加減小移動 速度，而實(shí)際的影響程度我們無法準(zhǔn)確的獲知，這里我們采用一些參數(shù)來使它對速度影響接 近真實(shí)情況，這種某人在某地向某方向僅受地形影響的速度，我們稱之為地形速度；另外, 人群移動的困難程度和當(dāng)?shù)厝巳旱拿芏仁浅烧鹊?當(dāng)人多的時(shí)候，人群的移動速度取決于 在你前方那個(gè)人的移動速度，因?yàn)榕鲎苍诖颂幨遣辉试S的，所以人只能跟隨前方的人行動, 這種高密度人群中的移動速度我們稱之為流動速

33、度;當(dāng)人群密度介于多和少之間時(shí)，也就是 人在人群中可以一定程度上避免碰撞的按自身速度移動時(shí)，我們暫稱其為中密度速度。假設(shè) 人按可能移動的最高速度（地形速度）時(shí)，那么就有此時(shí)單位矢量的速度，一個(gè)人從位置 向B方向移動，則有速率：0 e（3-1）在本論文中，0=00是指單位向量指向 方向。但是，當(dāng)人群在暢通無阻的情況下，他們也會更加青睞于一些特定的路徑。例如在過馬路時(shí)，更傾向于走人行橫道。 此外，人們也喜歡走他們常走的路線， 即使這條路比較長。此時(shí)，我們引入一個(gè)新的場一一不爽場g,不爽場是本模型的外源型因素。 如人行橫道的不爽度要遠(yuǎn)低于車輛川流的馬路，人們熟悉的路徑會有較低的不爽，這樣，我們可以更

34、加準(zhǔn)確的仿真人群的移動。同時(shí)，不 爽度也可以提高人們之間的碰撞避免和其他運(yùn)動阻礙，例如兩個(gè)相向的人， 他們極度接近時(shí)會產(chǎn)生極大的不爽，直接影響其路徑選擇的方向?，F(xiàn)在，我們綜合上面的敘述， 來說明人群是如何選擇路徑的。通常情況下，我們都會采用最短路徑算法來到達(dá)目的地，但真實(shí)中，人群更趨向于避免擁擠和避開一些環(huán)境不好的路段（即高度不爽度的區(qū)域），這樣可以保證權(quán)衡典型的條件和實(shí)現(xiàn)時(shí)間所需的最小化。因此，我們通過人群選擇的以下三個(gè)方面最小的線性組合來總結(jié)這些問題：1路徑長度2到達(dá)目的地所需的時(shí)間3路徑上每個(gè)單位時(shí)間的不爽度例如，P作為x到一些目標(biāo)路徑上的一些點(diǎn)。假設(shè)速度場f，不爽場g，目標(biāo)G都是固定的

35、，一個(gè)人位于 x將選擇P n的最小路徑a p lds+B p ldt + 丫 pgdt (3-2)在這里，a , B ,丫是不同的權(quán)重；ds代表著路徑長度方面的積分，同時(shí)dt代表著時(shí)間方面的積分。這兩個(gè)變量的關(guān)聯(lián)是ds=fdt ，這里f是速度等價(jià)的，我們也可以重寫公式2為：a+-+-(3-3)可以簡化為,where C = (3-4)是單位消耗的區(qū)域。所以，我們更加細(xì)致的總結(jié)上述問題，從中提取一些必要的量來執(zhí)行我們 本次任務(wù)的工作。在本模型中，一個(gè)動態(tài)勢場模型的建立需要以下幾個(gè)關(guān)鍵部分：1理想路徑規(guī)劃2密度場與速度場的計(jì)算3控制方程3.1最大速度場3.2不爽場3.3單元消耗場4離散的網(wǎng)格結(jié)構(gòu)4

36、.1密度轉(zhuǎn)換4.2單元消耗場4.3動態(tài)勢場的構(gòu)建以下是由上述幾個(gè)關(guān)鍵部分來闡述的程序流程圖：載入 矩網(wǎng)格X輸入地冊l載入人群信息匸龍機(jī)的 分布在地圏某處附近廠訐算密度場k.JWf計(jì)算地彫謹(jǐn)度計(jì)聲濟(jì)動謹(jǐn) 度計(jì)尊中密度人群邃度計(jì)算單元 消耗場L_計(jì)算俱場牛體單位人的移納圖 3-1-13.2速度方程在上述提綱中我把最優(yōu)路徑計(jì)算放在了第一位，但是為了更加清晰的了解 它，我需要在介紹完其他問題后再介紹最優(yōu)路徑。在本節(jié)中，我們將談?wù)撋婕?到速度的2個(gè)場（速度場、密度場）以及 3種速度（地形速度、中密度速度、 流動速度）的計(jì)算。圖 3-2-1速度場f意味著每個(gè)點(diǎn)的每個(gè)方向在領(lǐng)域中的最大速度。我們的速度模型

37、是特定的，但計(jì)算起來十分簡單，它提供了實(shí)際可行的人群行為。我們開始一 個(gè)直觀的描述。速度是一個(gè)密度依賴的變量。在人群密度低的情況下，速度受 地形支配，其余因素就是地面的平坦度和地面的斜率，即地形速度。在高密度 人群的情況下，速度開始受到周圍人群行動的影響：運(yùn)動受對流的抑制，但不 被順流所影響，即流動速度。當(dāng)人群密度介于高低之間時(shí)，運(yùn)動受到周圍人群 運(yùn)動的影響沒有高密度時(shí)那么大，但也會受到抑制，即中密度速度。3.2.1人群密度場由于速度密度相依賴，我們首先介紹人群密度場p。我們指定 為第i個(gè)人的密度場。這個(gè)場應(yīng)該是以最高峰的第i個(gè)人為中心并放射性的向周圍衰減。方程特定的形式是不重要的，只要它不低

38、于特定的閾值的半徑r的圓周邊界內(nèi)，并且不比外部的大。人群密度p只是簡單的每一個(gè)人密度區(qū)域的總和。當(dāng)我們計(jì)算這個(gè)場的時(shí)候，我們同時(shí)可以計(jì)算平均速度場，并通過 來標(biāo)明每個(gè)人所處的密度，說明整體速度和人群方向：(3-5)，and這里 指第i個(gè)人的速度。所有的總計(jì)都來自所有小組總的所有人d圖 3-2-1-1我們有兩個(gè)密度轉(zhuǎn)換方程的要求。首先，密度場必須不斷地指出人的位置。否則動作會造成密度明顯的不連續(xù)，并且速度也會這樣。其次，每個(gè)人的貢獻(xiàn) 不應(yīng)該低于他們自己網(wǎng)絡(luò)單元的，但是要低于周圍網(wǎng)絡(luò)單元的。直覺上,這要求確保每一個(gè)人都不會影響自己對密度領(lǐng)域的貢獻(xiàn)。第一項(xiàng)要求是標(biāo)準(zhǔn)，可滿足任何數(shù)量的splatt i

39、ng技術(shù)，包括雙線性和高斯。第二個(gè)要求是不尋常的，而且我們已經(jīng)確定了新的密度轉(zhuǎn)換技術(shù)，以滿足 它。對于每個(gè)人，我們發(fā)現(xiàn)最接近單元中心的坐標(biāo)都小于那個(gè)人所占據(jù)的空間。 我們之后計(jì)算這個(gè)人相對于單元中心的坐標(biāo) x, y，就像圖3-2-1-1所示人的密度添加到網(wǎng)格后就是： TOC o 1-5 h z 入入入入這里密度指數(shù) 入確定密度下降的速度。這個(gè)密度轉(zhuǎn)換方法是持續(xù)關(guān)系到每個(gè) 人的位置，并且確定每個(gè)人至少對網(wǎng)格單元貢獻(xiàn)，但并沒有超過相鄰單元的，這里。這樣，我們的要求得到滿足。當(dāng)我們計(jì)算密度領(lǐng)域p，我們同時(shí)通過方程式P =， and 來計(jì)算平均速度。322地形速度在密度非常低的地區(qū) （p p max就

40、定為p max)，速度f就等于流動速度(x, e ) =(x+ rn e )? n e (3-7)流動速度 本質(zhì)上是在距離 x的r處對平均速度的估計(jì)。某些阻力使得人們對 將要進(jìn)入的區(qū)域進(jìn)行平均速度的估計(jì)。事實(shí)上，如果不是這些阻力，一個(gè)人的 速度就主要受他先前的速度所影響，一個(gè)不良的結(jié)果。此外，流動速度固定是 非負(fù)的，暗示著人群可以減速，但是不能倒退。3.2.4中密度速度在中等密度( p min p p max )地區(qū)，我們線性的加入地形和流動 速度：f(x, e )= (x, e)+(e)(ee請注意，像流動的速度，密度p由一些阻力e來估計(jì)，再次以相同的理由：我們不指望一個(gè)人自己對密度場自我妨

41、礙他們運(yùn)動的貢獻(xiàn)。因此，我們認(rèn)為一個(gè)人對密度場沒有作用。在圓半徑r以外的大于p的，我們可以肯定，在低擁擠的環(huán)境中，人群的速度將等于他們的地形速度，只要 p min。3.3單元消耗場我們用兩步去計(jì)算單元消耗場C。我們首先通過方程f(x,e ) = (x, e) +()X (99 計(jì)算速度場 f，然后用方程,whereA來計(jì)算消耗場C。由于這些場的各異性，所以我們計(jì)算它們時(shí)不僅要涉及迭代到每個(gè)單元網(wǎng)絡(luò)，而且迭代每個(gè)網(wǎng)格的四個(gè)方向。例如，在圖3-3-1中的方格M,我們必須計(jì)算 和 ，這里i E,N,W,S。我們通過評估人如 果選擇那個(gè)方向并將要移動的方格中的速度和不爽來為行人預(yù)測前方的障礙。舉個(gè)例子

42、，在案例 ，我們將密度、不爽 和平均速度 加到方程f(x, 9 )9=(x,9 ) + () X (99 中。3.4動態(tài)勢場建設(shè)3.4.1快速行進(jìn)法構(gòu)建動態(tài)勢場是該算法中最復(fù)雜和時(shí)間消耗最多的步驟。方程| (x)|=C 定義了勢的一個(gè)固有光程函數(shù)方程，因此不可以直接算出來。然而有效 的方法已經(jīng)制定用來解決這種類型的方程，尤其是快速行進(jìn)法和快速掃除法。 在此，我們選擇了前者，因?yàn)楹笳弋?dāng)最佳路徑必須遵守迂回路線時(shí)效率會變得十分低下(例如，由于各種障礙的存在)?？焖傩羞M(jìn)法的基本思想是在傳播邊界外圍構(gòu)造一圈激活網(wǎng)格，激活的點(diǎn)的 勢場未定，利用逆向格式將當(dāng)前的邊界向外傳播，如同水波擴(kuò)散一樣，擴(kuò)散到 的網(wǎng)

43、格即確定其該點(diǎn)勢場，再根據(jù)當(dāng)前網(wǎng)格的勢場構(gòu)建新的激活該網(wǎng)格，如此循環(huán)，即可得到矩陣中每個(gè)方格的勢場。該算法的時(shí)間復(fù)雜度為0( N log N)0如下圖3-4-1-1 :1 13.4.2有限差分法微分方程和積分微分方程數(shù)值解的方法。基本思想是把連續(xù)的定解區(qū)域用有限個(gè)離散點(diǎn)構(gòu)成的網(wǎng)格來代替，這些離散點(diǎn)稱作網(wǎng)格的節(jié)點(diǎn)；把連續(xù)定解區(qū)域上的連續(xù)變量的函數(shù)用在網(wǎng)格上定義的離散變量函數(shù)來近似；把原方程和積分用積分和來近似，于是原微分方程和 即有限差分方程組，解此方程組就可 然后再利用插值方法便可以從離散解得到定解條件中的微商用差商來近似， 定解條件就近似地代之以代數(shù)方程組, 以得到原問題在離散點(diǎn)上的近似解。

44、定解問題在整個(gè)區(qū)域上的近似解。有限差分法是數(shù)值計(jì)算中應(yīng)用得最早而又相當(dāng)簡單、直觀的一種方法。應(yīng) 用有限差分法通常所采取的步驟是:采用一定的網(wǎng)格分割方式離散化場域。 進(jìn)行差分離散化處理。用離散的、只含有限個(gè)未知數(shù)的差分方程組，來近似代替場域內(nèi)具有連續(xù)變量的偏微分方程以及邊界上的邊界條件（也包括場域內(nèi)不同媒質(zhì)分界面上的銜接條件)。 結(jié)合選定的代數(shù)方程組的解法，編制計(jì)算機(jī)程序，求解由上面所得對 應(yīng)于待求邊值問題的差分方程組，所得解答即為該邊值問題的數(shù)值解?，F(xiàn)在，以本勢場就采用這種方法：( =1 3.4.3動態(tài)勢場通過采用快速行進(jìn)法和有限差分法，我們開始為已知的網(wǎng)格列表分配勢場0,在目標(biāo)點(diǎn)處，我們分配

45、勢場值為0;所有其它位置的網(wǎng)格都設(shè)為。按照快速行進(jìn)法，我們將那些臨近已知的網(wǎng)格都列為候選的激活網(wǎng)格，我們首先找到沿X和丫軸成本較低的臨近網(wǎng)絡(luò)單元格：0 0然后通過求解這個(gè)有限差分近似方程：0 0(如果 或者 沒有定義，由于相鄰的會有無窮的消耗，當(dāng)或者 其中的一個(gè)遠(yuǎn)遠(yuǎn)的于另一個(gè)時(shí)，女口較小時(shí)，0 = 0 + 。當(dāng)周圍單元格只有一個(gè)可知時(shí)，則 0= 0已知+該方向的消耗。第 4 章 全局人群規(guī)劃算法的實(shí)現(xiàn)GPU 上實(shí)現(xiàn)人工智能路徑尋找4.1.1 全局路徑尋找現(xiàn)在很多人群仿真系統(tǒng)都是基于主體模型，在行動中為每個(gè)人分別計(jì)算。 這種方法雖然有一定的優(yōu)勢 （為每個(gè)主體有獨(dú)立的判斷， 獨(dú)立的能見度和環(huán)境 信

46、息），他同時(shí)挑戰(zhàn)性的為那些主體去開發(fā)行為規(guī)則，結(jié)果是一個(gè)一致和現(xiàn)實(shí) 的整體人流。 為大量的主體擴(kuò)大基于主體的方法是需要大量的計(jì)算， 使人們望 而卻步，如關(guān)注一個(gè)互動情景，如視頻游戲。我們的人群仿真解決方案， 我們選擇了一個(gè)基于連續(xù)的辦法， 類似于 Treuill 的連續(xù)性人群的工作。 這種方法將行動規(guī)劃轉(zhuǎn)換成一個(gè)優(yōu)化的問題， 使用眾所 周知的數(shù)值方法，并從普通物理學(xué)和光學(xué)來獲取穩(wěn)定的導(dǎo)航解決方案。這種方法特別適用于模擬大量的主體，因?yàn)樗怯?jì)算的空間，而不是每個(gè) 主體，并且結(jié)果是平滑順利的，沒有所謂死角。此外，一個(gè)連續(xù)方法的結(jié)果是 實(shí)際上的大量人群像流體一樣運(yùn)動。 全局模型只是一個(gè)包含充分可見性

47、和決策 邏輯的近似準(zhǔn)確的長期規(guī)劃， 因此增加了局部碰撞回避問題。連同這些方法產(chǎn) 生順利進(jìn)行和現(xiàn)實(shí)的人流，特別是在密集地區(qū)的交通擠塞。在這基于連續(xù)的人群仿真中，環(huán)境被制定為一個(gè)消耗函數(shù)（有時(shí)被稱為速 度方程）。這個(gè)消耗函數(shù)由于所處環(huán)境中的位置，應(yīng)包含地形速度（基于地形 坡度，等等）和避免碰撞因素（基于主體密度，大規(guī)模的障礙，等等） 。這個(gè) 消耗方程被形容了旅行時(shí)間， 即從一個(gè)位置移動到相鄰的位置， 并用來評估最 優(yōu)路徑。這個(gè)消耗函數(shù)稍后用來輸入一個(gè)求解計(jì)算總旅程時(shí)間（勢 ）從一些位置到最鄰近的目標(biāo)。這個(gè)勢（ ）是被計(jì)算出來的，他滿足eikonal方程：II （ x） |=FF是在方向梯度 （ x

48、）評估中消耗方程的積極值。它直觀的看到方程可以通過沿著從每個(gè)位置 x 的最短路徑的整合消耗方程來構(gòu)造。 在本文中， 我 們可以把全局的人群行為看作是計(jì)算一個(gè)波的向前傳播， 跟隨阻力最小的路徑 按照梯度所產(chǎn)生的勢場，主體們保證始終是沿著最短路徑移動到全局的目 標(biāo)，這里考慮到了速度，主體的移動是基于地形特點(diǎn)、障礙和主體密度的（擁 堵）。4.1.1.1全局路徑尋找 CPU的執(zhí)行一種快速，能夠被簡單理解的算法近似的計(jì)算并解決了 eikonal 方程的是 快速行進(jìn)法，我們將在這里總結(jié)。因?yàn)槲ㄒ恢赖膭蔹c(diǎn)是目標(biāo)位置，我們初始 設(shè)置目標(biāo)單元 =0并且將這個(gè)單元添加到已知單元中。所有其他的單元都被 加到一個(gè)未

49、知的列表中，并且設(shè)置他們的勢為。該算法的過程如下：1）將所有臨近已知單元的未知單元都添加到一個(gè)鄰居表中2）每個(gè)相鄰單元的勢的計(jì)算采用基于相鄰已知單元的勢和已知單元到達(dá) 相鄰單元的消耗來解決問題3） 更新相鄰單元并且將在步驟2 中找到的擁有最小勢的單元添加到已知 單元中去4）重復(fù)直到所有單元都在已知列表中。請注意，上述算法是和 Dijkstra 的方法相同的。 Dijkstra 方法和快速行進(jìn)法 的不同是步驟 2 中勢的計(jì)算方式不同。采用 Dijkstra 方法在一個(gè)離散的網(wǎng)格上 求解連續(xù)的 eikonal 方程將不會收斂；我們將始終從你完善的網(wǎng)格構(gòu)架中獲得 階梯式的人工環(huán)境。N*WM*ES圖

50、4-1-1-1-1Tsitsiklis為連續(xù)的eikonal方程提供了有限差分近似值，這樣消除了階梯式前進(jìn)的問題。首先，前進(jìn)方向被確定為在相鄰x和y方向中最低的消耗(另見圖 4-1-1-1-1): (2)有限差分方程通過 在二次方程中的最大解來計(jì)算： (=1(3) 在用例中 和 都是未定義的(任何一個(gè)沿著中心線的都是未知的)，然后從方程中消除術(shù)語中包含的軸。一旦 在所有的網(wǎng)格中形成，則梯度 可 以被很容易的計(jì)算。然而，快速行進(jìn)法是一個(gè)串行算法并且不可并行，同時(shí)推而廣之，不是非 常適合高效的 GPU計(jì)算。4.1.1.2全局GPU路徑尋找的執(zhí)行情況幸運(yùn)的是，這里存在一個(gè)可以并行解決eikonal方

51、程的方法?？焖俚ú?用相同的在321.1章節(jié)中提及的有限差分近似，但是不需要制定數(shù)據(jù)結(jié)構(gòu)去 存儲已知和未知列表，等等。這個(gè)想法只是更新活躍的網(wǎng)格的勢函數(shù)。在實(shí)踐 中，一組獨(dú)立激活的網(wǎng)格不需要保留。直觀的，激活方塊的列表被初始化來包含擁有源的方塊。我們總結(jié)了算法如下：n次迭代所有激活了的方格比較被激活方格中的每一個(gè)單元來預(yù)先計(jì)算這些單元的勢值。如果差別實(shí)在比較小的閾中，標(biāo)記它為收斂的。對于每一個(gè)激活的方塊，執(zhí)行一個(gè)在聚合結(jié)果上的衰減來決定整個(gè)方格是收斂的在臨近這個(gè)方塊的所有方塊上執(zhí)行一個(gè)迭代來決定步驟三中的聚合是否存在一些單元的值有所改變；更新激活的方塊列表來影響所有的方塊，因?yàn)槲醇せ畹挠捎?/p>

52、聚合或者在步驟4中被定義為重激活的。然而，由于我們的執(zhí)行，我們能夠進(jìn)一步簡化這個(gè)算法，因?yàn)槲覀兊南?方程的復(fù)雜度不是非常大，并且我們的單元網(wǎng)格與作者工作中使用的龐大的數(shù) 據(jù)集是低相關(guān)的。由于我們的數(shù)據(jù)集比較小(128*128或256*256)，由于收斂權(quán)重大于揀選計(jì)算和性能消極的影響不斷執(zhí)行測試的開銷。在其他方面，我們的算法和上面的相似。為了確保我們求解的收斂性，我們需要一個(gè)對需要迭代次數(shù)的保守估計(jì)數(shù)。在我們的求解程序中，采用的迭代次數(shù)按我們的經(jīng)驗(yàn)是由最嚴(yán)重的檢驗(yàn)一一用例消耗函數(shù)的復(fù)雜性來決定。4.1.1.3構(gòu)建消耗方程圖 4-1-1-3-1從左向右分別為：消耗函數(shù)，勢能，勢能梯度。目標(biāo)是在

53、藍(lán)色標(biāo)記的中心。求解 eikonal 方程需要一個(gè)消耗方程來評估每個(gè)單元。在 Froblins demo 中 由于環(huán)境的消耗方程的計(jì)算如下：F(x) = aT(x)+bD(x)+cA(x)其中 F 是最終的消耗方程， T 是靜態(tài)運(yùn)動的消耗(包括地形移動消耗也就 是斜度和大型靜止物體，例如建筑物) ， D 是主體的密度， A 是相關(guān)的動態(tài)損 害。a, b和c是權(quán)重，他們可以依據(jù)當(dāng)前的情況來使移動方選擇不同的路徑。 舉個(gè)例子， 這個(gè)可以主觀的增加主體密度的消耗值當(dāng)接近一個(gè)目標(biāo)時(shí)，以防止在目標(biāo)處過度的擁擠。一旦標(biāo)量消耗方程 F(x)被構(gòu)造(圖4-1-1-3-1)，它可以提供給 eikonal方程 來

54、求解 (x)。梯度 (x)是由中心差分來計(jì)算的。4.1.2 局部導(dǎo)航和回避不幸運(yùn)的是， 解決 eikonal 方程在一個(gè)分辨率足夠高的大規(guī)模主體人群中來 回避彼此，如果實(shí)時(shí)應(yīng)用程序中不需要高昂的消耗，那么這是可接受的。為了 使我們的人物有一個(gè)準(zhǔn)確的行為模式， 我們用一個(gè)局部回避模型以便解決這些 細(xì)粒度的障礙，來擴(kuò)大我們的全局 eikonal 解決方案。局部模型的基本目標(biāo)提供每個(gè)單獨(dú)的主體一個(gè)速度，以防止和附近的主體 發(fā)生碰撞，并繞過障礙，使主體通向其理想的目的地。這通常是由一個(gè)連續(xù)的實(shí)時(shí)檢驗(yàn)附近環(huán)境和基于探索信息的反應(yīng)程序來解決。方法我們的局部導(dǎo)航和回避模型來通過由全局模型確定的行動方向和附近

55、主 體的速度以及位置來計(jì)算主體速度。這個(gè)回避模型是基于速度障礙規(guī)劃我們的模型， 我們現(xiàn)在把每個(gè)人比作一個(gè)光盤。 每個(gè)主體 因此有個(gè)位置 一個(gè)速度 ，一個(gè)圓周半徑r，一個(gè)最大速度 ，一個(gè)由全局解決方案提供的全 局目標(biāo)方向 。我們從 中設(shè)定一個(gè)方向 來假定主體的方向是面向 的。在我 們的應(yīng)用程序中，所有的主體都有一個(gè)相似的半徑，同時(shí)因此r 是所有主題的一個(gè)常數(shù)。就像大多數(shù)的局部模型， 為 更新 和 需要一些已知量， 也就是屬于 的和，這里 ，這里是一定范圍內(nèi)的所有主體。通過新的 GPU 分區(qū)來進(jìn)行空間查詢?yōu)榱舜_定局部動態(tài)障礙的位置和速度，我們需要一個(gè)空間數(shù)據(jù)結(jié)構(gòu)來包含仿真中的所有障礙信息。我們開發(fā)

56、了一個(gè)新的多路算法來直接通過GPU分類主體到各自的空間存儲器中。我們的算法采用一個(gè)2D 深度紋理數(shù)組和一個(gè)簡單2D 色彩緩沖來構(gòu)造一個(gè)數(shù)據(jù)結(jié)構(gòu)，他們用來分配主體到存儲器中。這個(gè)深度 紋理數(shù)組來充當(dāng)我們主體 ID 的陣列。 一個(gè)給出的 2D 紋理元素地址在這個(gè)陣列 中充當(dāng)一個(gè)容器。一個(gè)單獨(dú)的容器是一個(gè) 1D 數(shù)組的材質(zhì)部分。這個(gè)容器數(shù)組 通過連續(xù)的紋理元素?cái)?shù)組部分衰減。每個(gè)材質(zhì)數(shù)組部分包含一個(gè)主體ID （容器元素）。主體的那些 ID 在容器中按照 ID 的升序來存儲。主體進(jìn)入容器的數(shù) 量要低于容器的承受能力（這個(gè)是由深度數(shù)組部分的數(shù)值來定義的）。為了有效的查詢在被給出容器的數(shù)組中的主體ID，我們

57、使用一種容器計(jì)數(shù)器。容器計(jì)數(shù)器是一個(gè) 2D色彩緩沖區(qū)，它記錄著讀取的在主體ID數(shù)組中的每個(gè)容器。要查找一個(gè)臨近世界空間的特定位置的所有主體，這個(gè)位置被轉(zhuǎn)換為一個(gè)2D容器地址。任何轉(zhuǎn)換方程都可能被使用。我們的世界領(lǐng)域是一個(gè)正方形的，所以一個(gè)簡單的統(tǒng)一制式網(wǎng)格被用于為全局空間位置的容器分配空間。一旦容器的地址是已知的， 容器的負(fù)載就可以從容器計(jì)數(shù)器中讀取。 這個(gè)給我們提供 了我們所感關(guān)注的內(nèi)容，那就是主體的數(shù)量。最后，容器中每個(gè)主體的ID 都從主體 ID 列表中獲取。這個(gè)數(shù)據(jù)結(jié)構(gòu)必須在主體在全局中移動時(shí)更新每個(gè)幀。這些更新采用了迭 代的算法，首先所有的主體 ID 放在一個(gè)緩沖區(qū)中，這被稱作工作集。

58、每次迭代，當(dāng)主體被放入容器中，他們將從工作集中被移除。這個(gè)算法持續(xù)迭代，知道工作集中歸零Agent Po&itionsBin CounterAgent ID Array0%詢ic Point Rmt;2f1131-562TI】圖 4-1-2-2-1主體位置被轉(zhuǎn)化為圖層至一個(gè)容器計(jì)數(shù)器中，同時(shí)，一個(gè)數(shù)組包含了容器中的主體ID。我們從容器計(jì)數(shù)器清零開始來指明這些容器是空的，并且所有的主體ID數(shù)組部分都被清為1.0。為了第一次迭代，主體ID數(shù)組最頂部的部分被綁定為當(dāng)前深度緩沖區(qū)，并且容器計(jì)數(shù)器被綁定為當(dāng)前色彩的目標(biāo)。工作集中，包 含所有的主體ID，被綁定為輸入頂點(diǎn)緩沖區(qū)并且每個(gè)元素被光柵化為一個(gè)單

59、一的原點(diǎn)。隨著每個(gè)點(diǎn)通過定點(diǎn)著色器，這個(gè)點(diǎn)的屏幕空間位置將被設(shè)為映射在相關(guān)的主體世界位置，也就是上面提出的容器地址。規(guī)范的主體ID被存儲為這個(gè)點(diǎn)的深度值。GPU的深度測試單元被配置用來傳遞片段，以便更燒得 深度值存儲在深度緩沖區(qū)中。其結(jié)果是，所有被標(biāo)定在容器中的主體，只有擁 有最低ID （對應(yīng)點(diǎn)最低深度值）的主體被放入容器中。由于我們只可以寫出 一個(gè)簡單的主體來給予容器一次迭代，像素渲染間的輸出結(jié)果1在容器計(jì)數(shù)器中，容器計(jì)數(shù)器被這位 1當(dāng)接收到一個(gè)主體。沒有接收任何主體的容器將繼續(xù) 設(shè)置他們的初始值0。如果有多個(gè)代理被標(biāo)定在一個(gè)容器中，擁有最低ID的主體將被寫入，同時(shí)其他的主體當(dāng)在隨后的通過中

60、將被拒絕被處理。第二次迭代算法，第二部分的主體ID數(shù)組將被設(shè)置為當(dāng)前深度對象并且主體們將被再次處理。沒有主體被從第一次通過的工作集中移除，所以第二次迭代再次執(zhí)行將輸入一個(gè)工作集，這個(gè)工作集將包含所有的主體。這一次，頂ID 少于或等于先前存儲在主體點(diǎn)渲染器做了一些額外的工作，如果它的主體ID 數(shù)組部分的 ID ，那么它將拒絕當(dāng)前的原點(diǎn)。點(diǎn)被標(biāo)記為“被拒絕的”是通 過設(shè)置他們的深度值為一些超出有效深度的范圍。 深度單元仍舊被配置為少于 功能，所以，就像深入剝離，我們有效的實(shí)施一個(gè)雙重深度緩沖，這些的結(jié)果 是擁有最低 ID 的點(diǎn)將大于所有放入容器中的 ID 然后通過。 在頂點(diǎn)渲染中執(zhí)行 “大于”測試