[發明專利]基于自頂向下的多層次虛擬環境建模方法

無效

• 申請號: 200810062017.4
• 申請日: 2008-05-23
• 公開（公告）號: CN101419722A
• 公開（公告）日: 2009-04-29
• 發明（設計）人: 孫守遷;王鑫;侯易
• 申請（專利權）人: 浙江大學
• 主分類號: G06T15/70
• 分類號: G06T15/70
• 代理公司: 杭州求是專利事務所有限公司
• 代理人: 林懷禹

技術領域

本發明涉及計算機動畫與環境建模的交叉領域，尤其涉及一種基于自頂向下的多層次虛擬環境建模方法。

背景技術

虛擬人與虛擬環境的交互非常重要，主要包括了感知環境、遍歷環境以及環境中的路徑規劃等交互行為。最初的虛擬環境建模主要存在于機器人技術中，輔助機器人仿真中的遍歷行為。隨著計算機動畫領域的不斷發展，自主智能體與行為動畫開始走入人們的視線，對于人群動畫中虛擬環境建模的需求也越來越引起人們的重視。

在機器人技術中的環境建模技術中，Metric?maps地圖繪制技術將真實世界中的距離信息與地圖中的距離信息成一定的比例關系，可以在地圖上方便的找到路徑長度、建筑物尺寸以及物體的精確位置信息。這種地圖就是我們常常見到的量度圖，如中華人民共和國的地圖。主要包括兩種：Grid?map與featuremap。Elfes與Moravec在1987年首次提出前者[1]，將機器人所處的環境表示為具有固定分辨率的多維網格。該網格的每一個單元都記錄了對應地圖單位的空間占有狀態，這種表示方法簡單有效，可以利用有限的資源表示豐富的環境信息，但也存在兩大缺點，網格不能直觀的表示出環境中各個區域之間的拓撲關系，而且在查詢環境細節時，所需要的時間及空間代價都比較大。feature?map技術[2]將環境表示為一些具有參數特性的幾何元素，如點、線、柱體等，并具有顏色、位置等性質。機器人的傳感器很容易感知到這些特性，使得它在感知數據的可視化處理過程中非常有效；但同時也不適用于非結構化的環境，不容易找到清晰的區域劃分方式。Topological?approach拓撲方法[3]利用圖這一數據結構來表示環境，圖的節點與邊表示了區域之間的連通性與鄰接性關系。與Metric?map不同的是，拓撲地圖并不提供詳細的坐標信息，環境中區域之間與物體之間的距離是無從知曉的，它所注重的是表達出區域之間的連接關系。這種方法與今天流行的環境表示方法比較相似，方便解決路徑規劃等問題。但是因為它缺少環境對象的絕對坐標等關鍵細節信息，不太支持更為細致的環境遍歷過程。

在計算機動畫領域中，隨著動畫角色變得越來越智能化，對動畫中的環境建模也越來越重要了。Lamarche與Donikian提出了一個基本模型[4]，用于重建虛擬人在虛擬環境中的遍歷行為。基于此模型，能進一步實現相應的可見性計算，鄰域檢測，碰撞避讓以及最優化路徑算法等。這種方法能夠同時仿真出數以百計的行人在戶內戶外環境中的活動場景。它從虛擬環境的幾何元素數據庫中得到了十分精確的多層次拓撲結構信息，并基于這種結構創建了一個最優化的路徑規劃算法。Noser等人提出將合成視覺應用到虛擬人的遍歷過程中去[5]，在處理遍歷問題時，它提出了兩種方法。在全局方法中，使用動態的八叉樹作為全局的三維可視化內存，虛擬人能夠借此記憶它所看到的環境信息，并適應不斷改變的動態環境。在本地方法中，利用了更低層次的視覺感知，本地遍歷模型使用視覺環境中直接輸入的信息來達到指定的目標或子目標。

[1]Elfes，A.，Sonar-basedreal-world?mapping?and?navigation.Roboticsand?Automation，IEEE?Journal?of[legacy，pre-1988]，1987.3(3)：p.249-265.

[2]Leonard，J.J.and?H.F.Durrant-Whyte，Mobile?robot?localization?bytracking?geometric?beacons.Robotics?and?Automation，IEEE?Transactionson，1991.7(3)：p.376-382.

[3]Kuipers，B.and?Y.T.Byun，A?robot?exploration?and?mapping?strategybased?on?a?semantic?hierarchy?of?spatial?representations.Toward?LearningRobots.MIT?Press，Cambridge，Massachusetts，1993：p.473.

[4]Lamarche，F.and?S.Donikian，Crowd?of?Virtual?Humans：a?New?Approachfor?Real?Time?Navigation?in?Complex?and?Structured?Environments.ComputerGraphics?Forum，2004.23(3)：p.509-518.