室內外無縫導航定位移動三維客戶端設計

李 赟，李 凍，左志權，劉正軍，畢京學,3

(1.中國測繪科學研究院，北京 100830；2.蘭州交通大學，蘭州 730070；3.山東科技大學，山東 青島 266590)

1 引言

隨著社會的快速發展和信息時代的到來，移動定位導航應用服務正逐漸影響人們的日常生活。網絡地理信息系統(web geographic information system，WebGIS)的廣泛應用以及移動智能終端的普及，使得人們在陌生環境中尋找特定的地點或目標時，利用定位導航服務可以用最短的時間達到目的地[1]。室外環境中的導航技術近年來發展較快，截至目前已經形成了較為成熟的商業體系，比如室外車載導航系統、手機導航系統等[2]。室外環境下的定位導航系統主要采用全球定位系統(global positioning system，GPS)衛星信號或蜂窩信號來進行定位，將GPS和電子地圖配合使用，并結合相關的導航軟件，在電子地圖上顯示實時位置及路線信息，完成導航服務[3]。室內環境下的定位導航研究主要集中在以下兩類[4-5]：一是研發室內定位系統，比較突出的研究包括室內感知系統、上下文感知環境等；二是用移動機器人控制和實現導航服務，這種類型注重系統硬件的實現，對導航系統本身關注不多。

目前廣泛采用的導航地圖都是二維的，隨著移動終端設備計算能力的突飛猛進，使得在移動端進行高效的三維渲染成為可能[6]。虛擬現實技術近年來在計算機領域也引起了廣泛的關注。它能夠利用計算機生成較為真實的模擬環境，使用戶沉浸在虛擬環境中，同時通過人機交互接口，實現用戶與虛擬環境的直接交互[7]。

Unity3D作為一種三維虛擬現實游戲平臺，對DirectX和OpenGL擁有高度優化的圖形渲染管道，支持常見的文件格式，并能和大部分相關應用程序協同工作，可以充分、實時的處理大量的三維模型[8]。值得關注的是，Unity3D是一個跨平臺性非常好的三維引擎，從桌面系統到移動平臺和游戲主機，幾乎涵蓋了所有平臺。利用Unity3D進行三維應用程序的開發，便可以實現“開發一次，多處使用”的理想目標。因此，本文在系統實現中選用Unity3D作為開發工具。

隨著網絡帶寬和移動終端性能的大幅提升，云技術和移動網絡技術的快速普及，以及大型建筑內部導航和定位的需求與日俱增，基于三維的導航定位服務應運而生。合理整合現有的各種硬件資源，軟件資源和信息資源，設計一套滿足當前應用環境下的系統成為本文以及今后繼續研究的重點。

2 客戶端設計框架

2.1 客戶端需求分析

移動客戶端程序是運行在移動終端設備(如智能手機)上的應用程序，是用戶與室內外導航定位系統進行交互的唯一接口。良好的導航定位移動客戶端程序需要具備以下要素：

(1)提供良好的交互界面方便用戶使用；

(2)與后臺位置服務通信，實時獲取用戶位置數據；

(3)管理和調度本地或遠程服務器上的三維模型數據，優化三維場景渲染，使客戶端程序在移動終端設備上能同時滿足流暢、美觀和低能耗的要求；

(4)具備三維場景中路徑規劃的能力，能滿足用戶在室內外進行定位、導航的需求。

2.2 客戶端的組成模塊

本文根據室內外導航定位系統的功能需求，采用模塊化設計方法，將移動客戶端應用程序分解為四大組成模塊，分別是：客戶端用戶接口、導航與空間查詢模塊、定位模塊和三維模型調度模塊(見圖1)。

圖1 客戶端結構框圖

2.2.1 客戶端用戶接口

用戶接口(user interface，UI)是為人機交互提供幫助的功能集合。作為運行在移動終端上的定位導航系統，UI主要應為用戶提供基于觸摸屏的常用手勢操作，定位與空間查詢、路徑規劃等功能。在三維場景瀏覽方式方面，可以提供兩種不同的視角，即第一人稱視角(見圖2(a))和鳥瞰視角(第三人稱視角，見圖2(b))。兩種視角用于不同場合，第一人稱視角適合作為導航視角，為用戶帶來“沉浸式”導航體驗；鳥瞰視角用于大面積場景瀏覽，查看生成路徑的全貌等。另外，第一人稱視角也更適合于室內導航的應用。

圖2 客戶端程序的兩種視角

2.2.2 導航與空間查詢模塊

導航與空間查詢模塊負責處理用戶的輸入，通過位置服務模塊獲取用戶位置，然后利用空間數據庫和空間數據服務器進行查詢和計算最優化路徑，并將結果作為導航路徑可視化和三維數據調度模塊的依據。

2.2.3 定位模塊

定位模塊包含室內定位和室外定位兩個組成部分。其中室外定位主要依靠GPS衛星或蜂窩數據、位置服務器和移動終端操作系統提供的定位應用程序接口(application programming interface，API)來實現。室內定位利用室內場景中布設的無線保真(wireless fidelity，WiFi)熱點和預先采集的WiFi指紋庫，采用指紋庫匹配和內插技術得到室內位置信息。難點在于定位方式是室內還是室外的判別，因此需要設計一個智能化的判別器來判別當前的定位方式。判別器的判別結果將作為導航模塊，三維模型調度模塊的輸入。

2.2.4 三維模型調度模塊

三維模型調度模塊作為可視化的核心需要精心的設計[6，9-12]。衡量三維應用程序性能的一個重要指標是幀率(每秒鐘生成的畫面數)，需要繪制的數據量越大，消耗的時間也越多。對于復雜場景的三維模型，通常包含大量數據，如果將數據全部加載，即使有足夠的內存容納它們，也沒有辦法流暢的繪制畫面[9]。精細模型的真實感渲染可以給人帶來愉悅的視覺享受，但提高渲染畫面效果的同時給硬件系統帶來了過量的計算負荷，使得渲染達到滿足交互需要的幀率成為奢望。因此，需要對模型數據進行合理的組織，創建空間索引[10]，利用相機位置和視椎體對模型數據進行視椎體裁剪、遮擋剔除和細節層次模型(level of detail，LOD)[13]等技術的調度，合理的控制內存中的數據量和送入圖形處理單元(graphic processing unit，GPU)渲染的數據量。該模塊接收位置模塊和導航模塊的輸出結果以及用戶的操作，控制相機的運動。

3 關鍵技術

3.1 室內模型組織和管理

室內模型主要分為兩類，一類是建筑物本身，另一類是其附屬物。具體分類原則為：將樓體建筑物(包括樓板、框架、外墻、樓梯)作為建筑物模型；剩余的都屬于附屬物(如商場建筑物中的單個小商鋪、衛生間、服務臺、倉庫等等，以及它們的分隔物如內墻、隔板等)。模型采用面向對象的方法管理和調度，每個單獨的物體都作為單一模型，保存為單獨的模型文件，它們同時具有3種以上不同分辨率。

用大型商場的室內模型來舉例，模型文件的目錄按圖3所示的層級結構組織。

圖3 樓層及附屬物模型示意圖

模型的存放位置應符合以上層級結構，如：整個建筑的外框模型應存放在“建筑名稱或編號”文件夾中，每個樓層的整體建筑模型應放在“樓層編號i”(i表示樓層數)文件夾中，樓層的附屬物包括商鋪、電梯(樓梯)、洗手間、服務臺、倉庫等每一個存放在一個單獨的“商鋪編號i”文件夾中，該文件夾中只存放某一個樓層附屬設施不同分辨率的模型文件。紋理文件放在對應模型所在文件夾中，單獨存放在名為“Texture”的文件夾中。

全部商鋪信息匯總為一個文件(.xls 或 .txt)，該文件存放在“建筑名稱或編號”文件夾中。每一條商鋪記錄包括：建筑編號、樓層編號、商鋪編號、商鋪屬性(包括商鋪名稱，在該建筑局部坐標系中的起始坐標，分類，如：餐飲、服裝、家居、樓梯、服務臺、洗手間等，商鋪屬性分類后續再做詳細分類)。

在Unity3D中將每一個模型文件單獨打包成Asset Bundle文件(一種Unity3D支持的可在本地或遠程動態加載的文件格式)，將打包后的文件按原來的層級保存在數據模型服務器上供遠程下載。

這樣的模型組織方式便于調度和管理，程序只需讀取模型的屬性信息，然后生成空間索引用于調度。

3.2 室內環境下三維路徑的生成

二維地圖上采用基于圖論的最短路徑算法生成需要查找的路徑。將地圖上的關鍵點作為節點，根據地圖上點的連通性將相應的節點連接成邊，并輔以權值就形成了二維問題的圖。

室內導航有個明顯的特征，即在某個樓層內的導航問題仍屬于二維問題。如果將相鄰樓層通過某種途徑連接就能夠使得樓層之間的圖連通，而樓層之間的物理連接樓梯或電梯剛好提供了這樣的途徑。因此，將樓梯和電梯作為節點加入圖中就可以構造整個建筑室內環境的三維圖，然后采用傳統的最短路生成算法即可生成室內環境下的三維路徑[14]。

3.3 基于四叉樹的室外模型調度

每一個區域的室外模型都有一個屬性描述文件，該文件記錄了每個建筑模型的ID，參考點坐標，包圍盒等信息。讀取該文件可以構建一顆四叉樹：①將所有模型的參考點作為點群，計算該點群在x-z平面(Unity3D中y軸向上)的包圍盒；②將得到的包圍盒各邊向外擴展距離d，該距離可以取包圍盒邊長平均值的0.1倍，得到一個包含所有點的矩形區域；③將該矩形作為根節點，設四叉樹節點能保存點數的最大值為N，設根節點為當前節點。比較當前節點包圍盒中的點數n0與N的大小，若n0>N，則將當前節點進行四叉剖分，再將每個子節點作為當前節點重復步驟③；④經過幾步遞歸后，全部葉子節點的包圍盒中點數都小于N，得到一顆四叉樹。

四叉樹的節點中應保存位于該節點中的建筑模型文件路徑，模型ID，葉子節點包含節點包圍盒。節點包圍盒指包含節點內所有建筑模型的最小包圍立方體。

模型調度過程是在每一次畫面更新前，判斷相機視椎體和四叉樹葉子節點包圍盒的拓撲關系，若包圍盒與視椎體相交或位于視椎體內部，則從緩存池讀取該節點所包含的全部建筑模型，將它們添加到要渲染的模型數組中；否則若該節點包含的模型在渲染模型數組中，則將他們從數組中刪除。

4 結束語

本文提出了室內外無縫定位與導航的移動客戶端設計思路，詳細探討了移動客戶端的實現框架、功能模塊，闡述了設計過程中的關鍵技術并且提供了可行的解決思路。城市空間信息化，無線網絡和移動智能終端日益普及，基于位置服務和室內外定位信息可視化由二維轉向三維，在這樣的背景下，逐步實現和豐富模塊功能是今后的研究重點。室內外無縫定位中的內、外環境的識別與切換是難點，也是今后系統設計中要解決的主要問題。

[1] 干建松.基于Unity3d的室內漫游仿真系統[J].淮陰師范學院學報：自然科學版，2011，10(6)：515-518.

[2] 李德仁，劉強，朱慶.數碼城市GIS中建筑物室外與室內三維一體化表示與漫游[J].武漢大學學報：信息科學版，2003，25(3)：253-258.

[3] 李慧.室內外融合導航系統的設計與實現[D].北京：北京郵電大學，2011.

[4] 張紅平.樓宇三維尋徑分析研究[D].南京：南京師范大學，2011.

[5] 杜建庚.樓宇三維路徑的生成、規劃及表達[D].北京：北京交通大學，2008.

[6] 閆金金，尚建嘎，余芳文，等.一種面向室內定位的3D建筑模型構建方法[J].計算機應用與軟件，2013，30(10)：16-20.

[7] 卞鋒，江漫清，桑永英.虛擬現實及其應用進展[J].計算機仿真，2007(6)：1-4+12.

[8] 龍艷軍，俞佳曦.Unity3D游戲開發中的版本控制研究[J].軟件導刊，2012，11(11)：12-14.

[9] 楊衛軍.海量三維城市模型的調度與場景管理[D].武漢：武漢大學，2005.

[10] 傅由甲.動態八叉樹在復雜場景設計中的應用[J].系統仿真學報，2006，18(S2)：408-410.

[11] 唐桂文，張慶娟，王功明，等.基于三維GIS的海量地形數據存儲和調度的研究[J].測繪科學，2008，33(3)：110-112+120.

[12] 王冬，王曉華.三維GIS中海量模型調度與存儲[J].地理空間信息，2012，10(1)：109-111+4.

[13] HOLLIMAN N.Review of "Level of Detail for 3D Graphics" by David Luebke，Martin Reddy，Jonathan D.Cohen，Amitabh Varshney，Benjamin Watson，and Robert Heubner.Morgan Kaufmann[J].Presence：Teleoperators and Virtual Environments，2003，12(4)：441-442.

[14] 艾海舟，張錢.移動機器人路徑規劃算法的實驗研究[C]//第一屆人工智能聯合會學術會議論文集.長春：吉林大學出版社，1990：400-405.