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

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

3、GPU 實現部分的原理、采用的數據結構以及實現的方法。關鍵字：GPU人群，運動規劃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 全文結構 1 HYPERLINK l bookmark8 o Current Document 第 2 章 相關技

12、術 2 HYPERLINK l bookmark10 o Current Document 2.1人群運動仿真 2人群運動建模 3人群運動可視化 3 HYPERLINK l bookmark12 o Current Document 2.3 Direct 3D概述5 HYPERLINK l bookmark14 o Current Document 第3章 基于流體力學的全局人群規劃算法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 動態勢場建設 13快速行進法 13有限差分法 14動態勢場 15 HYPERLINK l bookmark24 o Current Document 第 4 章全局人群規劃算法的實現 16 HYPERLINK l bookmark26 o Current Document GPU上實現人工智能路徑尋找 16全局路徑尋找 16局部導航和回避 20 HYPERLIN

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、速度。在通常情況下，人移動的最高速度需要考慮到一些環境條件。例如， 居住在城市里的市民就可以隨性的按通常速度步行，而一支部隊里的戰士可能需要以一個更 快的速度來沖鋒。所以環境可以在許多方面影響速度：如斜率的大小使人們增加減小移動 速度，而實際的影響程度我們無法準確的獲知，這里我們采用一些參數來使它對速度影響接 近真實情況，這種某人在某地向某方向僅受地形影響的速度，我們稱之為地形速度；另外, 人群移動的困難程度和當地人群的密度是成正比的,當人多的時候，人群的移動速度取決于 在你前方那個人的移動速度，因為碰撞在此處是不允許的，所以人只能跟隨前方的人行動, 這種高密度人群中的移動速度我們稱之為流動速

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

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

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

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

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

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

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

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

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

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

43、格即確定其該點勢場，再根據當前網格的勢場構建新的激活該網格，如此循環，即可得到矩陣中每個方格的勢場。該算法的時間復雜度為0( N log N)0如下圖3-4-1-1 :1 13.4.2有限差分法微分方程和積分微分方程數值解的方法?；舅枷胧前堰B續的定解區域用有限個離散點構成的網格來代替，這些離散點稱作網格的節點；把連續定解區域上的連續變量的函數用在網格上定義的離散變量函數來近似；把原方程和積分用積分和來近似，于是原微分方程和 即有限差分方程組，解此方程組就可 然后再利用插值方法便可以從離散解得到定解條件中的微商用差商來近似， 定解條件就近似地代之以代數方程組, 以得到原問題在離散點上的近似解。

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

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

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

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

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

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

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

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

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

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

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

55、主 體的速度以及位置來計算主體速度。這個回避模型是基于速度障礙規劃我們的模型， 我們現在把每個人比作一個光盤。 每個主體 因此有個位置 一個速度 ，一個圓周半徑r，一個最大速度 ，一個由全局解決方案提供的全 局目標方向 。我們從 中設定一個方向 來假定主體的方向是面向 的。在我 們的應用程序中，所有的主體都有一個相似的半徑，同時因此r 是所有主題的一個常數。就像大多數的局部模型， 為 更新 和 需要一些已知量， 也就是屬于 的和，這里 ，這里是一定范圍內的所有主體。通過新的 GPU 分區來進行空間查詢為了確定局部動態障礙的位置和速度，我們需要一個空間數據結構來包含仿真中的所有障礙信息。我們開發

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

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

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

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

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