LOD技術(shù)和最短路徑算法在交通三維地理信息系統(tǒng)中的應(yīng)用研究

張訓(xùn)虎，章磊

（國家測繪產(chǎn)品質(zhì)量檢驗測試中心，北京 100830）

1 引 言

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

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

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

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

2 關(guān)鍵技術(shù)分析

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

2.1 地形LOD技術(shù)

2.1.1 LOD技術(shù)

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

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

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

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

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

則誤差函數(shù)δ轉(zhuǎn)化為：

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

2.1.2 基于地理特征的地形LOD

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

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

2.2 最短路徑分析

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

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

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

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

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

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

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

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

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

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

3 交通領(lǐng)域應(yīng)用

本文主要探討通過LOD技術(shù)實現(xiàn)三維地理信息及路網(wǎng)的生成和實時顯示；利用最短路徑算法確保車輛行駛最優(yōu)路徑的準確計算，實現(xiàn)車輛導(dǎo)航功能；利用模擬駕駛模塊檢測實時路況，計算車輛行駛狀態(tài)，結(jié)合導(dǎo)航功能實現(xiàn)模擬駕駛，并將模擬駕駛路線在三維交通信息系統(tǒng)中顯示出來。

3.1 三維路網(wǎng)生成

基于規(guī)則格網(wǎng)（GRID）的地形模型構(gòu)造，結(jié)合最短路徑算法并加入人工干預(yù)，設(shè)定三維路網(wǎng)中的道路、路口及道路周邊建筑及附屬設(shè)施的三維模型與顯示（圖1）。

圖1 基于GRID技術(shù)的三維路網(wǎng)生成效果圖

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

要實現(xiàn)以上功能，首先對場景數(shù)據(jù)按照分塊進行組織，采用規(guī)則格網(wǎng)對整個場景按照不同的層次結(jié)構(gòu)進行組織、存儲、管理。通過這種方式解決了數(shù)據(jù)調(diào)用中的分級管理，減少數(shù)據(jù)的訪問量和調(diào)用量。采用結(jié)點樹的方式組織數(shù)據(jù)，自上而下的對分塊數(shù)據(jù)進行簡化。

圖2 四叉樹結(jié)構(gòu)表示的地形

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

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

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

3.2 車輛導(dǎo)航

車輛導(dǎo)航功能是交通地理信息系統(tǒng)的主要功能之一。導(dǎo)航分為靜態(tài)導(dǎo)航和動態(tài)實時導(dǎo)航。靜態(tài)導(dǎo)航是通過輸入出發(fā)地和目的地，系統(tǒng)結(jié)合A＊算法［9］自動計算出路徑信息。系統(tǒng)實現(xiàn)過程中按照改進的A＊算法［10］，按照臨時標記結(jié)點的估值函數(shù)：

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

車輛導(dǎo)航，實現(xiàn)了車輛在道路行駛中的位置、路線的準確計算與模擬，為模擬駕駛實現(xiàn)了系統(tǒng)保障。

3.3 模擬駕駛

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

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

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

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

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

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

結(jié)合模擬駕駛功能，LOD技術(shù)和最短路徑技術(shù)在交通部公路科學(xué)研究所的《基于虛擬現(xiàn)實的道路交通標志標線設(shè)計及評價系統(tǒng)》中的實現(xiàn)了相關(guān)功能及應(yīng)用。

4 結(jié)束語

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

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

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

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

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

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

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

［7]陳磊.三維模擬車載導(dǎo)航系統(tǒng)的設(shè)計與實現(xiàn)［D］.成都：電子科技大學(xué)，學(xué)位論文，2010.

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

［9]白巧霞.基于eSuperMap的車輛導(dǎo)航系統(tǒng)的設(shè)計與實現(xiàn)［D］.西安：西北大學(xué)，2007.

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

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

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

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