龔 俊，朱 慶，章漢武，李曉明，周東波

1.江西師范大學 地理與環(huán)境學院，江西 南昌330022；2.武漢大學 測繪遙感信息工程國家重點實驗室，湖北武漢430079

基于R樹索引的三維場景細節(jié)層次自適應控制方法

龔 俊1，朱 慶2，章漢武1，李曉明2，周東波2

1.江西師范大學 地理與環(huán)境學院，江西 南昌330022；2.武漢大學 測繪遙感信息工程國家重點實驗室，湖北武漢430079

針對大規(guī)模三維城市建模需要，介紹一種基于三維R樹索引的多細節(jié)層次（簡稱LOD）管理方法，從葉節(jié)點層向根節(jié)點自動生成LOD場景，并設計實現(xiàn)LOD檢索的算法。通過試驗分析，證明本文的LOD定義參數能夠定量控制三維場景中的渲染目標數目，進而實現(xiàn)三維場景的自適應可視化方法，尤其適合于建筑物和樹木類型的地物目標。

三維場景；R樹；多細節(jié)層次；自適應

1 概 述

從20世紀80年代起，研究者從數據管理、LOD可視化乃至預測模型等多個角度對三維場景細節(jié)層次的自適應控制方法展開研究。文獻［1］將復雜的建筑物場景以較小的獨立空間單元進行管理，以幀率穩(wěn)定為前提采用一種成本－貢獻判據自適應地選擇合適的離散多細節(jié)層次模型來繪制畫面。文獻［2］基于視點位置和圖像空間誤差實現(xiàn)對大規(guī)模地形數據的實時多細節(jié)層次控制。文獻［3］則從連續(xù)LOD管理的角度提出自適應控制算法。

空間索引是提高空間數據管理效率的重要技術，R樹是應用最為廣泛的空間索引方法之一。R樹擴展至三維空間后，節(jié)點重疊引發(fā)多路查詢激增是效率低下的主要原因。通過改進節(jié)點選擇和節(jié)點分裂，從而改善節(jié)點形狀可以解決三維R樹節(jié)點重疊嚴重問題［4］。為消除空間目標形態(tài)對索引效率影響，有研究者依據拓撲關系制定索引構建規(guī)則，對不規(guī)則三維目標切割成小目標，也可改善節(jié)點重疊現(xiàn)象，然而切割過程增加幾何和語義維護成本［5］。文獻［6］提出全局優(yōu)化的節(jié)點選擇和二分為三的節(jié)點分裂算法減輕節(jié)點重疊現(xiàn)象，三維空間聚簇性增強，三維R樹樹形更趨合理。良好樹形使得R樹的天然層次結構與多細節(jié)層次技術結合成為可能。

筆者從三維模型數據及其實時可視化需求入手，基于三維R樹空間索引特點，提出一種管理和描述大規(guī)模多細節(jié)層次復雜場景的簡便方法，可方便靈活地定量調整場景復雜度，實現(xiàn)三維場景細節(jié)層次自適應控制。

2 基于三維R樹的多細節(jié)層次自適應控制方法

關于R樹和多細節(jié)層次場景結合的已有研究均試圖采用R樹的天然層次結構實現(xiàn)目標查詢和細節(jié)層次查詢的雙重功能［7－8］。已有研究應用R樹節(jié)點包圍盒作為低細節(jié)層次描述，忽略單個目標的LOD描述需求，也不能滿足可視化精度要求。

2.1 多細節(jié)層次生成方法

傳統(tǒng)R樹索引方法僅在葉節(jié)點中管理目標模型，擴展結構使得中間節(jié)點也能管理目標模型。葉節(jié)點層管理全部和最精細的目標，從每個子節(jié)點按照某種規(guī)則挑選一個最有代表性的目標作為較粗層次目標模型集合存于父節(jié)點中，因此上層節(jié)點中的目標數目和子節(jié)點數目相等。舉例說明，從每個子節(jié)點中選擇一個最大高度的目標作為上層節(jié)點的目標，或者二維投影面積最大的目標。本文方法借助R樹的層次結構，葉節(jié)點代表最高的細節(jié)層次，中間節(jié)點代表中等的細節(jié)層次，根節(jié)點代表最低的細節(jié)層次。

各層的適用范圍須合理定義，保證在不同視場范圍下可見的目標數目穩(wěn)定在某個范圍之內。以某個理想三維場景為例，即其中目標分布均勻，各層R樹節(jié)點也分布均勻，保證視線豎直向下，尋找某個臨界視點，如果提高視點將有部分區(qū)域采用下一細節(jié)層次表達，此時整個場景均采用最高細節(jié)層次表達，視點到視錐體邊緣目標距離即最遠視距約等于最高細節(jié)層次的最遠距離d，采用相同方式尋找第二個臨界視點，使得整個場景采用第二細節(jié)層次表達，此時最遠視距約等于第二細節(jié)層次的最遠距離D。R樹的扇出（fanout）參數是節(jié)點包含的子節(jié)點數目，它是一個約束值，存在最小值m和最大值M，因此在某個區(qū)域內，相鄰層的節(jié)點數目比值近似在1∶m～1∶M之間。根據本文方法，任意節(jié)點中的目標數目均滿足扇出系數條件，因此各個節(jié)點中的目標數目大致相等。由于兩個場景覆蓋地域面積的比值為（D／d）2，而節(jié)點數目比值為1∶m～1∶M，因此要保證兩個場景目標數目近似，則要滿足m＜（D／d）2＜M，即因此相鄰層的最遠距離要滿足等比關系，如果m＝4，M＝9，則2＜D／d＜3時，將能保證各種場景下目標繪制數目大致相等。

本文采用三個參數作為多細節(jié)層次定義參數，包括R樹的層數LevelNum、最高細節(jié)層次的最遠距離FarDist和相鄰細節(jié)層次最遠距離的比值DistFactor。假設R樹有4層節(jié)點即Level－Num＝4，令FarDist＝500m，DistFactor＝2，則第一層的作用范圍為0～500m，第二層的作用范圍為500～1 000m，第三層的作用范圍為1 000～ 2 000m，第四層的作用范圍為2 000～4 000m（最后一層的最遠距離也可設為無窮遠）。

2.2 多細節(jié)層次場景的檢索方法

多細節(jié)層次場景生成后，如何高效實現(xiàn)多細節(jié)層次檢索成為本方法實用化的關鍵問題。多細節(jié)層次模型檢索是一個與視點密切相關的功能。根據上節(jié)LOD參數定義方法，隨視點變動三維場景也相應發(fā)生變化，遠目標屬于上層節(jié)點（甚至根節(jié)點）管理，近目標屬于下層節(jié)點（甚至葉節(jié)點）管理，檢索過程以根節(jié)點為入口，借助三維空間查詢技術裁剪視場之外的節(jié)點和目標。本方法生成的場景效果是，全部場景均可見，視點近的區(qū)域目標密度高，視點遠的區(qū)域目標密度低，符合人類視覺感知規(guī)律。以下是基于三維R樹的多細節(jié)層次檢索算法描述。

算法入口：視點和管理多細節(jié)層次場景的三維R樹索引。

算法出口：待繪制的目標集合。

步驟1：設R樹根節(jié)點為Node。

步驟2：判斷Node（最小包圍盒）與視錐體的空間關系。如果相離，終止該分支；如果被視錐體包含，進入步驟3；如果相交，進入步驟5。

步驟3：如果視距大于節(jié)點的細節(jié)層次作用范圍，則終止該分支；如果視距落于節(jié)點的細節(jié)層次作用范圍，則將節(jié)點中的目標全部加入目標集合，并終止該分支；如果視距小于節(jié)點的細節(jié)層次作用范圍，則將該節(jié)點中的目標全部加入目標集合，并進入步驟4。

步驟4：循環(huán)訪問各子節(jié)點（Child0，Child1，Child2，…），將子節(jié)點逐一設為Node并進入步驟3。

步驟5：如果視距大于節(jié)點的細節(jié)層次作用范圍，則終止該分支；如果落于節(jié)點的細節(jié)層次作用范圍，則逐一判斷節(jié)點中的目標與視錐體的空間關系，如果非相離則加入目標集合，并終止該分支；如果小于節(jié)點的細節(jié)層次作用范圍，則將該節(jié)點中不與視錐體相離的目標加入目標集合，并進入步驟6。

步驟6：循環(huán)判斷各子節(jié)點（Child0，Child1，Child2，…）與視錐體的空間關系，如果非相離，則將子節(jié)點設為Node并進入步驟2。

步驟7：如果所有查詢分支均終止，則退出。

2.3 多細節(jié)層次的自適應控制方法

本文方法中，調整最高細節(jié)層次的最遠距離參數（FarDist）即能調整各層的作用范圍，當FarDist增大時，各層的最近距離和最遠距離均增大，且作用范圍的區(qū)間增大。調整FarDist可以改變場景復雜性，F(xiàn)arDist增大則場景復雜，F(xiàn)arDist減小則場景簡化。因此，可以實現(xiàn)三維城市場景自適應控制方法。

下面討論調整參數對于三維場景的影響。令視點接近地表且視線水平，假設最高細節(jié)層次最遠距離為D，且層間倍數為K，視錐體的水平方向夾角為α。Slod1為LOD1作用范圍的面積，Slod2為LOD2作用范圍的面積，計算公式分別見式（1）和式（2），各細節(jié)層次面積均和D2存在正比關系。假定三維場景屬于理想狀態(tài)，即目標分布密度均勻，各層節(jié)點分布密度也基本均勻，則各層覆蓋面積決定了覆蓋范圍內的節(jié)點數目也即目標數目，因此各層次范圍內的目標數目之和與D2存在正比關系。每個目標數據量相等的前提下，目標數目和處理時間也成正比關系，而三維城市場景中的目標數目通常很大，從統(tǒng)計學上講，隨著統(tǒng)計樣本數量增加，平均值趨向穩(wěn)定，進而獲得處理時間和D2成正比的結論。三維場景實時繪制中，根據前幾幀的處理時間在每幀繪制前定量調整D值，應對系統(tǒng)負載變化，在保證穩(wěn)定幀率的前提下提供最為豐富的細節(jié)層次場景。

3 試驗分析

本試驗中的目標模型均采用目標的最小包圍盒表示，便于關注空間索引技術本質，實際單個目標包括幾何和紋理數據量可能超過1M數據量，測試數據為某城市部分城區(qū)的離散目標，總共有23 951個目標，測試環(huán)境配置如下：筆記本電腦，CPU Intel Duo T7500，內存1G。

3.1 多細節(jié)層次可視化的試驗結果

本文方法在三維空間查詢的同時，也能實現(xiàn)多細節(jié)層次場景目標檢索，這種多細節(jié)層次可視化的重要特征是，既能實現(xiàn)目標集合的綜合和簡化，也能支持單個目標的多細節(jié)層次表示（當單個目標存在多細節(jié)層次模型時），可以實現(xiàn)全部場景的多細節(jié)層次描述。

圖1～3是在各種視域條件下啟動與不啟動多細節(jié)層次描述的場景對比。圖1所示的平視場景，二者可視化效果幾乎沒有差別，而目標數目卻相差明顯，這充分體現(xiàn)細節(jié)層次自適應控制的優(yōu)勢，那就是保持了近處目標的詳細特征，而淡化了遠處目標特征。圖2是遠距離俯視場景，二者具有比較明顯的差異，多細節(jié)層次描述仍然能夠保留原有目標分布特點，目標數目也相差明顯，也符合多細節(jié)層次描述要求。圖3是近距離俯視場景，由于視場內目標與視點的距離均在最高細節(jié)層次作用范圍的最遠距離內，全部采用最高細節(jié)層次描述，二者完全相同。

圖1 平視場景Fig.1 Head－up display of scenes

圖2 遠距離俯視場景Fig.2 Overlook of scenes from far distance

圖3 近距離俯視場景Fig.3 Overlook of scenes from near distance

3.2 多細節(jié)層次自適應控制的試驗結果

修改最高細節(jié)層次的最遠作用距離FarDist調整三維場景復雜度是本文自適應控制方法的核心。設計試驗來分析調整參數FarDist會對三維場景多細節(jié)層次描述產生的影響。設定多細節(jié)層次參數中的層間參數為3。圖4是不同參數條件下的三維場景。本試驗設置了6次參數，它們滿足等比系數為1.5的等比序列，即200m、300m、450m、675m、1 000m和1 500m。按照第2.3節(jié)的理論分析，如果目標分布均勻，圖中的6個場景中的目標數目滿足等比參數為2.25（1.52）的等比序列，試驗數據也基本符合理論分析。試驗說明，可以通過調整FarDist參數定量控制多細節(jié)層次場景描繪中的目標數目。

圖4 不同LOD參數條件下的三維場景Fig.4 3Dscenes on the conditions of different LOD parameters

4 結 論

提出一種新的三維場景細節(jié)層次控制方法，利用R樹的層次結構承載多細節(jié)層次目標，通過三個環(huán)節(jié)控制三維場景中渲染目標的數目：一是視錐體查詢裁剪視野外的目標；二是啟動多細節(jié)層次繪制方法；三是調節(jié)多細節(jié)層次控制參數。試驗表明該方法在空間檢索過程中同時完成LOD目標模型檢索功能，實現(xiàn)了完整場景的簡化描述，描繪效果和效率能夠滿足大規(guī)模三維城市模型的實時繪制需求，并且通過調整多細節(jié)層次參數可以定量控制場景中的目標數目和復雜度，實現(xiàn)三維場景的自適應可視化控制，尤其適合建筑物和樹木等尺寸均勻的地物目標。進一步工作將延展到地質和地下管線、不規(guī)則三角網和三維激光掃描點云等數據處理領域。

［1］ FUNKHOUSER T A，SEQUIN C H.Adaptive Display Algorithm for Interactive Frame Rates during Visualization of Complex Virtual Environments［C］∥SIGGRAPH’93 Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques.New York：ACM Publishings，1993：247－254.

［2］ YANG Chongyuan，ZHANG Jixian，LIN Zongjian.The Real－time LOD Algorithm for Rendering the Virtual Terrain Scene［J］.Acta Geodaetica et Cartographica Sinica，2001，30（2）：133－139.（楊崇源，張繼賢，林宗堅.虛擬地形場景繪制中的實時LOD算法［J］.測繪學報，2001，30（2）：133－139.）

［3］ WIMMER M，SCHMALSTIEG D.Load Balancing for Smooth LODs［R］.Vienna：Vienna University of Technology，1998.

［4］ ZHU Qing，GONG Jun.An Improved Full 3DR－tree Spatial Index Method［J］.Geomatics Information Science of Wuhan University，2006，31（4）：340－343.（朱慶，龔俊.一種改進的真三維R樹空間索引方法［J］.武漢大學學報：信息科學版，2006，31（4）：340－343.）

［5］ CHEN Peng，MENG Lingkui，SONG Yang.R－tree Structure Appended with Spatial Topology Restrictions in 3DGIS［J］.Geomatics Information Science of Wuhan University，2007，32（4）：347－349.（陳鵬，孟令奎，宋楊.三維GIS中基于空間拓撲約束條件的R樹研究［J］.武漢大學學報：信息科學版，2007，32（4）：347－349.）

［6］ GONG Jun，ZHU Qing，Zhang Yeting，et al.An Efficient 3DR－tree Extension Method Concerned with Levels of Detail［J］.Acta Geodaetica et Cartographica Sinica，2011，40（2）：249－255.（龔俊，朱慶，張葉廷，等.顧及多細節(jié)層次的三維R樹索引擴展方法［J］.測繪學報，2011，40（2）：249－255.）

［7］ KOFLER M.R－trees for Visualizing and Organizing Large 3DGIS Databases［D］.Graz：Graz University of Technology，1998.

［8］ LI Jun，JING Ning，SUN Maoyin.A Mechanism of Implementing Visualization with Level of Detail at Multi－scale［J］.Journal of Software，2002，13（10）：2037－2043.（李軍，景寧，孫茂印.多比例尺下細節(jié)層次可視化的實現(xiàn)機制［J］.軟件學報，2002，13（10）：2037－2043.）

AnAdaptiveControlMethodofLODsfor3DSceneBasedonR－treeIndex

GONGJun1，ZHUQing2，ZHANGHanwu1，LIXiaoming2，ZHOUDongbo2
1.School of Geography and Environment，Jiangxi Normal University，Nanchang 330022，China；2.State Key Laboratory of Information Engineering in Surveying，Mapping and Remote Sensing，Wuhan 430079，China

Aiming at the requirement of large－scale 3Dcity modelling，a method is puts forward to organize LOD scene based on R－tree’s hierarchical structure.LOD scene can be automatically generated from leaf node layer to root node，and efficient algorithm of LOD search are also designed and implemented.By experimental analysis，it is proved that scene complexity can be quantitatively altered by adjusting one defined LOD parameter，and further adaptively control LOD of 3Dscene，which suits building and tree type especially.

3Dscene；R－tree；levels of detail；adaptive

GONG Jun（1978—），male，PhD，associate professor，majors in theory and application of multidim ensional G IS and 3Dlaser point cloud data processing.

1001－1595（2011）04－0531－04

P208

A

國家自然科學基金（41001222；40871212；40721001）；國家973計劃（2010CB731801）；測繪遙感信息工程國家重點實驗室開放研究基金（（10）重04）

雷秀麗）

2010－10－25

2011－03－18

龔?。?978—），男，博士，副教授，主要從事多維地理信息系統(tǒng)和三維激光點云數據處理的理論與應用研究。

E－mail：gongjunbox＠gmail.com