LOD技術和最短路徑算法在交通三維地理信息系統中的應用研究

張訓虎，章磊

（國家測繪產品質量檢驗測試中心，北京 100830）

1 引 言

可視化理論與技術用于地圖學與GIS始于90年代初，GIS研究者開始把計算機圖形學的理論和技術引入到空間數據可視化研究中，二維GIS的可視化技術目前已經基本成熟。

可視化是三維GIS的重要研究內容。主要集中在地形表面的重構、房屋建筑幾何模型建立等方面，特別是在地形表達方面尤為突出。早期的多分辨率多采用基于TIN的層次結構三角剖分來生成。

近年來，隨著對三維GIS需求的增加，國內外眾多GIS軟件公司投入研發。如ESRI公司的ArcView 3DAnalyst擴展、Intergarph公司的GeoMedia Terrain模塊、吉奧公司的CCGIS等。它們的功能主要集中在地形和建筑的表達、屬性查詢、可視化觀察、可視化分析、空間量算等方面。在小區域、適當數據量條件下具有較好的應用效果，但對于大范圍、復雜環境及海量數據的逼真、實時可視化還顯得不足。國內外有些學者著手研究大場景、多維度的三維地理信息虛擬現實研究，包括數據存儲、數據顯示，而LOD技術是眾多研究中最為關鍵的技術之一。最短路徑算法是三維地理信息網絡分析的關鍵技術，在路徑分析、選址分析、成本分析中都有廣泛的應用。在交通信息系統中實現LOD技術和最短路徑算法的結合應用是比較新的研究領域之一。

本文依據的軟件平臺是北京英特圖原信息技術有限責任公司三維地理信息系統平臺。具有大數據量空間信息處理能力、仿真效果、數據庫驅動、跨平臺通信、二次開發支持等方面的技術能力，可以提供較好的三維地理信息和虛擬現實解決方案。目前，已經在數字城市、數字社區、小城鎮信息管理、城市綜合管網管理、戰場環境仿真等系統中得到了較為廣泛的應用。

2 關鍵技術分析

LOD技術即Levels of Detail的簡稱，意為多細節層次。LOD技術指根據物體模型的結點在顯示環境中所處的位置和重要度，在不影響畫面視覺效果的條件下，通過逐級簡化細節決定物體渲染的資源分配，減少場景的幾何復雜性，從而提高繪制算法的效率獲得高效率的渲染運算。

2.1 地形LOD技術

2.1.1 LOD技術

LOD技術是通過對場景的多尺度表達，達到數據減少與真實感減損之間的平衡［1］。它依據場景對象模型和視點的距離，選擇合適尺度模型表示來進行繪制。如果模型離視點較遠，且在屏幕空間的投影區域覆蓋較少像素，則用尺度小（粗糙）的模型來進行表示；相反，模型離視點較近，則采用尺度大（精細）的模型來進行表達。

基于地圖知識，設定不同比例尺下的模型是對真實對象的近似，比例尺越大，越接近真實對象。用函數S來表示近似，則S＝f（obj，d）。其中obj為真實對象，d為對象到視點距離。即是S為關于obj與d的函數。顯然，S是距離d的連續減函數。

因為S只是一種對真實對象的近似，所以與真實對象之間存在著誤差δ，用數學模型表示，則有：

其中，f（x）代表真實對象，y代表視點與對象的距離，視域變化范圍為0～D。顯然，δ越小，說明函數S表達下的模型比例尺越接近真實對象，差距越小，反之，則越大。

在實際計算過程中，需要將連續的S離散化。將視域變化范圍劃分為n段，如果距離視點處表示為di，（i＝0，1，…n），即每一段范圍Δdi為：Δdi＝di－di－1（i＝1，2，…n）。在 Δdi上則有對應的Si，且有S0＞S1＞…＞Sn。即距離越遠，相似程度越小。則有：

則誤差函數δ轉化為：

于是LOD問題就轉化為求使得δ＝min的Si和Δdi。由于δ函數是一個廣義上的泛函，求解是十分困難的。通常要結合具體的要求和條件來進行處理［2］。

2.1.2 基于地理特征的地形LOD

如上所述，LOD是對真實對象在不同比例尺上的近似。生成多分辨率的過程是一個簡化和綜合的過程。這種簡化過程不是為了從初始模型中移去粗糙的部分，而是為了保留重要的視覺特征，其理想結果是一個初始模型的簡化序列。因此選擇簡化算法是關鍵。

在地形多尺度模型生成方面，當前應用主要基于3種方法［3-4］：①Hoppe的“Progressive Meshes”法則；②Lindstrom的四叉樹方法；③Duchaineau的ROAM（實時優化自適應網格）法則。

2.2 最短路徑分析

最短路徑問題在計算機中有著廣泛的應用，例如網絡通信中最短路由的選擇，人工智能中搜索算法的研究等。

A＊算法［5］是到目前為止最快的一種計算最短路徑的算法，但它一種“較優”算法，即它一般只能找到較優解，而非最優解，但由于其高效性，使其在實時系統、人工智能等方面應用極其廣泛［6］。A＊算法結合了啟發式方法和形式化方法。它通過一個估價函數（Heuristic Function）來估計圖中的當前點到終點的距離（帶權值），并由此決定它的搜索方向，當這條路徑失敗時，嘗試其他路徑。

f（n）是結點n從初始點到目標點的估價函數，g（n）是在狀態空間中從初始結點到n結點的實際代價，h（n）是從n到目標結點最佳路徑的估計代價。其中h（n）主導著A＊算法的表現方式。有以下幾種情形：

（1）h（n）＝0：A＊算法這時等同Dijkstra算法，并且保證能找到最優路徑；

（2）h（n）＜目前結點到終點的距離：A＊算法保證找到最優路徑，h（n）越小，搜尋深度越深；

（3）h（n）＝目前結點到終點的距離：A＊算法僅會尋找最佳路徑，并且能快速找到結果；

（4）h（n）＞ 目前結點到終點的距離：不保證能找到最優路徑，但計算比較快；

（5）h（n）與g（n）高度相關：A＊ 演算法此時成為BFS（Best First Search）。

本模塊取兩結點間直線距離為估價值，即

這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，結點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。

3 交通領域應用

本文主要探討通過LOD技術實現三維地理信息及路網的生成和實時顯示；利用最短路徑算法確保車輛行駛最優路徑的準確計算，實現車輛導航功能；利用模擬駕駛模塊檢測實時路況，計算車輛行駛狀態，結合導航功能實現模擬駕駛，并將模擬駕駛路線在三維交通信息系統中顯示出來。

3.1 三維路網生成

基于規則格網（GRID）的地形模型構造，結合最短路徑算法并加入人工干預，設定三維路網中的道路、路口及道路周邊建筑及附屬設施的三維模型與顯示（圖1）。

圖1 基于GRID技術的三維路網生成效果圖

通過格網構建三維場景的方法，在實現場景時［7］，需要構建大量的格網，但是當構建大范圍場景時，需要耗費大量的計算機資源。而在實際應用中，并不需要全部顯示整體的三維場景，而是根據漫游的需要，僅僅顯示部分場景。因此采用分批調用場景的技術，把整個場景分成不同的小場景塊，根據漫游者視點的運動變化對這些場景塊進行讀取調用，保證漫游者的視點始終位于讀取場景的中心。具體實現時，將漫游者視覺中心所在的場景塊及周邊相鄰的場景塊調入內存，再根據視線及視點來確定需要顯示的區域，并進行顯示。

要實現以上功能，首先對場景數據按照分塊進行組織，采用規則格網對整個場景按照不同的層次結構進行組織、存儲、管理。通過這種方式解決了數據調用中的分級管理，減少數據的訪問量和調用量。采用結點樹的方式組織數據，自上而下的對分塊數據進行簡化。

圖2 四叉樹結構表示的地形

如圖2所示，將地形模型中的結點數指定為（2n＋1）2，并劃分成不同的層次，使樹中每一結點對應著由四塊格網單元組成的面片。相鄰的子場景，位于相鄰的結點上。在結點樹的葉結點上，包括最終小區域的紋理信息、顏色信息和位置信息等。這種方式每一個結點都表示一塊地形，結點的層次不同，對應的地形面積不同，葉結點的層次最高。其次采用邊刪除、邊插入以及布爾矩陣［8］方式解決因四叉樹結構帶來的相鄰地塊變化時引起的裂縫問題。

在調用的過程中通過考慮視距與地形的粗糙程度作為指標依據實現地形及各項信息的一并調用，并根據需要顯示。三維路網生成功能的實現，為車輛導航可視化提供了技術支持和保障。

在數據庫的支持下結合數據精度分級管理和空間索引技術，對三維場景數據進行動態組織、三維地形數據的動態簡化，從而具備大區域大數據量空間信息的處理能力。系統開發過程中注重對開放數據格式的支持，能夠支持大型的金字塔數據（32層）、融合不同精度的地形數據（圖3）以及對地形進行自動平滑與動態平滑，突破了大數據量的空間信息處理瓶頸問題。

3.2 車輛導航

車輛導航功能是交通地理信息系統的主要功能之一。導航分為靜態導航和動態實時導航。靜態導航是通過輸入出發地和目的地，系統結合A＊算法［9］自動計算出路徑信息。系統實現過程中按照改進的A＊算法［10］，按照臨時標記結點的估值函數：

其中，g（j）是從起點到標記結點的實際距離，h＊（j）是從標記結點到終點的最小距離，h＊（j－1）是從標記結點前一點到目標結點的最小距離，通過這種算法，減少結點的遍歷個數，提高搜索速度，完成路徑計算。然后通知車輛行駛前方應注意事件及抵達目的地的最佳路線和距離。動態導航是利用GPS實時或定時獲取車輛的位置及三維姿態和行駛方向，并根據道路的實際情況，如道路施工、堵塞、走錯路（車輛偏離原計算路徑200m以上時）等，舍去施工、堵塞或原計算路線并計算出新的最短路徑，在顯示屏上進行刷新更正，確保導航功能連續、快速、便捷地實現。同時配合語音提示，使駕駛員耳、目并用，輕松駕駛。

車輛導航，實現了車輛在道路行駛中的位置、路線的準確計算與模擬，為模擬駕駛實現了系統保障。

3.3 模擬駕駛

基于LOD技術實現虛擬三維空間數據的管理和組織，可以便利地實現對現實交通路網的模擬，并在GIS系統中實現視覺特效，完成對真實路況的虛擬實現。模擬駕駛是用電子技術控制汽車進行的仿人駕駛。車輛的行使過程是一個復雜的變加速過程（包括速度的大小和方向），在車輛行使過程中需要考慮的因素很多，其中最主要的是車輛的動力學模型（包括車輛速度模型、方向控制模型［11］、制動力模型、阻力模型［12］），除以上模型之外，還需要一些其他相關技術的支持，如車輛調度系統、通訊系統和人機交互系統等。

采用LOD技術、動力學模型和汽車碰撞模型來實現的模擬駕駛，在設計過程中采用構建線性車輛模型，通過鍵盤、方向盤、手柄等進行車輛控制，調整視角、跟蹤場景等方式實現對車輛的模擬駕駛。模擬過程中提供后視鏡、鷹眼視圖等。碰撞檢測按照包圍盒法實現。該方法用幾何特征簡單但體積略大的包圍盒來描述復雜的幾何對象，通過構造樹狀層次結構逼近模型，在遍歷模型樹的過程中，快速測試包圍盒的相交情況，盡早排除不相交的元素，僅僅對包圍盒的重疊部分元素進行進一步的相交測試，完成碰撞檢測［13］，計算出行駛所需要的相關動力學參數。

模擬駕駛在實際操作上主要表現在加（減）速、并線、轉彎等方面，實現上首先利用LOD技術，實現車輛所在道路的信息加載和顯示，然后根據駕駛車輛的汽車碰撞模型檢測路況并發出相關操作指令進行模擬，一定程度上可實現車輛的無人駕駛。

（1）加（減）速行駛，首先調整視角，利用LOD技術擴大道路信息顯示范圍，然后用碰撞檢測技術判斷車輛與周遍車輛、道路及道路附屬設施的相交測試，依據碰撞檢測得到的距離參數計算加（減）速度，調用速度模型，實現加油、加擋提速（或制動、減擋，減速度），并完成操作。

（2）車輛并線，首先利用LOD技術實現車輛左右車道的詳細信息載入及顯示，利用碰撞檢測技術檢測欲并車道及本車道的相交檢測，計算出本車道安全距離，欲并車道的安全距離，然后根據動力學模型計算車輛并判斷車輛可否并線及并線速度，若在安全閥值內可以實施操作，若不適合并線則等待并重新檢測判定，直至完成并線操作。

（3）車輛轉彎，根據導航模塊系統提示，若需要轉彎時，系統首先利用LOD技術調入相關道路信息，完成碰撞檢測。判斷車輛是否在轉彎車道，計算車輛轉彎半徑和轉彎速度，調用速度模型和方向控制模型，利用碰撞檢測得到的參數，進行減速，控制轉向燈指示轉向，實施轉向操作。

結合模擬駕駛功能，LOD技術和最短路徑技術在交通部公路科學研究所的《基于虛擬現實的道路交通標志標線設計及評價系統》中的實現了相關功能及應用。

4 結束語

LOD技術和最短路徑技術在交通三維地理信息系統中的應用，為解決三維建模、顯示、可視化提供了技術支撐，基于此技術的GIS可以清晰直觀地顯示道路及其附屬設施和周邊環境。結合導航技術以及模擬駕駛技術實現智能車輛交通信息系統可以解決因駕駛員人為因素引起的道路交通安全問題；通過有效的縮短行車間距可以增加道路容量、提高道路的運行效率；可以在特殊情況下替代駕駛員，完成諸如有毒、搶險情況下的車輛安全通行問題。因此隨著LOD技術和最短路徑算法的不斷改進和應用，能夠為智能交通提供更為廣闊的技術保證，從而方便生活。

［1]CLARK J.Hierarchical geometric models for visible surface algorithms［J］.Communications of the ACM，1976，19（10）：547－554.

［2]淮永建，郝重陽.基于LOD實時圖形繪制和加速技術［J］.中國圖像圖形學報，2002，7A（1）：97－101.

［3]譚兵，徐青，周楊.大區域地形可視化技術的研究［J］.中國圖像圖形學報，2003，8A（5）：578－585.

［4]李志林，朱慶.數字高程模型［M］.武漢：武漢大學出版社，2001（7）：3－7.

［5]盧開澄，盧華明.圖論及其應用（第二版）［M］.北京：清華大學出版社，1982.

［6]Tanenbaum A S.Computer networks［M］.3rd ed.Prentice Hall International，Inc，1998.

［7]陳磊.三維模擬車載導航系統的設計與實現［D］.成都：電子科技大學，學位論文，2010.

［8]雷軍環，曾凡喜，吳名星.基于四叉樹的視點相關LOD地形仿真算法研究［J］.制造業自動化，2010（08）：211－214＋228.

［9]白巧霞.基于eSuperMap的車輛導航系統的設計與實現［D］.西安：西北大學，2007.

［10]段莉瓊，朱建軍，王慶社，等.改進的最短路徑搜索 A＊算法的高效實現［J］.海洋測繪，2004（05）：20－22.

［11]蔡忠法.章安元.汽車模擬駕駛模型與仿真的研究［J］.浙江大學學報（工學版），2002，36（3）：327－330.

［12]李安定，尹念東.汽車駕駛模擬器的運動模型研究［J］.黃石理工學院學報，2008，24（2）：26－30.

［13]申玉斌.虛擬環境中的碰撞檢測技術的研究與應用［J］.交通與計算機，2005，23（1）：74－78.