高 勇，劉 家 駿，郭 瀟，鄔 倫

(北京大學(xué)遙感與地理信息系統(tǒng)研究所，北京 100871)

面向大規(guī)模動態(tài)地形可視化的LOD組織與調(diào)度技術(shù)

高 勇，劉 家 駿，郭 瀟，鄔 倫

(北京大學(xué)遙感與地理信息系統(tǒng)研究所，北京 100871)

地貌演化等地表過程的分析模擬實時產(chǎn)生系列地形數(shù)據(jù)，該動態(tài)過程的可視化對性能要求較高，傳統(tǒng)基于預(yù)處理的方法計算量大、繪制延遲明顯。面向大規(guī)模動態(tài)地形可視化，提出一種LOD預(yù)處理與實時更新相結(jié)合的混合調(diào)度技術(shù)，基于場景圖對動態(tài)地形LOD建模與組織，建立多線程模型實現(xiàn)地形瓦片的動態(tài)更新和繪制。對于每次迭代計算產(chǎn)生的新地形，該方法以LOD瓦片的動態(tài)調(diào)度替代傳統(tǒng)的靜態(tài)預(yù)處理方法，與地表過程計算同步更新瓦片，且僅重新計算和渲染當(dāng)前視域和分辨率下地形發(fā)生變化的局部瓦片，通過LOD的局部動態(tài)更新避免可視化數(shù)據(jù)的全局重新生成，顯著降低過程模型計算和結(jié)果更新對渲染過程的影響，提高整體的可視化性能。

地形可視化;細節(jié)層次模型;場景圖;多線程;動態(tài)調(diào)度

0 引言

地形可視化是三維地理信息系統(tǒng)的基礎(chǔ)，是地形分析應(yīng)用中重要的技術(shù)環(huán)節(jié),而在諸如地貌演化、水土流失等地表過程分析和模擬中，更是對地形可視化產(chǎn)生了新的需求。這類基于過程的地形數(shù)值分析和模擬，表現(xiàn)為地形因子，特別是高程h隨時間t的動態(tài)變化過程[1]，即h=f(t)或Δh=f(Δt)。將該過程通過三維可視化的方法實時動態(tài)展現(xiàn)出來，可以更直觀有效地探查、分析和檢驗地形演變過程的規(guī)律和特征，特別是在大規(guī)模地形分析中尤為如此。

當(dāng)前大規(guī)模地形的三維可視化技術(shù)，主要以細節(jié)層次模型(Level of Detail，LOD)為基礎(chǔ)[2,3]，以到觀察點的距離評價地形塊的重要程度，距離觀察點較遠則以粗糙模型顯示，反之則顯示精細模型。在實現(xiàn)中，首先通過LOD算法從原始的地形數(shù)據(jù)生成地形模型，然后在可視化中調(diào)用生成的模型完成顯示。其中比較有代表性的算法有ROAM算法[4]、限制性四叉樹算法[5]、Chunked LOD算法[6]等。從原始地形到地形模型，需要一個處理過程，這個過程不能在一幀的時間內(nèi)完成。因此，大規(guī)模地形可視化所用的地形模型，通常通過預(yù)處理生成。

從地形可視化到面向過程的動態(tài)地形可視化，其技術(shù)挑戰(zhàn)主要來自于LOD生成。預(yù)處理生成的LOD模型是靜態(tài)的，且生成效率通常較低，盡管目前已經(jīng)提出了一些LOD動態(tài)調(diào)度[6,7]、基于GPU的并行模型生成[8-11]等加速技術(shù)，但這些方法仍然是先整體預(yù)處理再渲染的兩階段過程。而地貌演化等地表過程是高程隨時間變化的函數(shù)，其最大的特點是隨時間演替不斷生成新的地形數(shù)據(jù)，即本文所稱的動態(tài)地形。當(dāng)前的可視化方法對每次產(chǎn)生的新地形數(shù)據(jù)都要重新進行預(yù)處理并重新構(gòu)建LOD，然后交給渲染過程，才能顯示新地形的變化。但由于在大數(shù)據(jù)量下預(yù)處理耗時長，很難在地表過程的一個時間步長內(nèi)完成，這就必然會導(dǎo)致地形實時可視化的停頓、更新不及時等性能問題，難以滿足動態(tài)地形流暢漫游的需求。因此，對于動態(tài)地形，需要結(jié)合可視化過程實時生成LOD模型，當(dāng)前已提出了一些局部地形的實時生成和更新方法，用以支持交互式地形編輯和渲染[1]，如結(jié)合體素的混合地形表達[12]、基于時空立方體的地形變形可視化[13]等，但這些方法主要面向局部地形更新，還不能很好處理諸如地貌過程模擬等大規(guī)模全局動態(tài)地形的可視化。

因此，本文提出一種LOD預(yù)處理與實時生成更新相結(jié)合的混合調(diào)度技術(shù)，提高動態(tài)地形過程的可視化性能。先通過預(yù)處理生成基礎(chǔ)的地形模型數(shù)據(jù)，保證可視化時存在可調(diào)用的地形模型。在地形過程計算中，對于新產(chǎn)生的地形數(shù)據(jù)，根據(jù)視點特征，動態(tài)查找需要更新的LOD瓦片，實時生成局部的新的地形模型，并完成該局部地形的動態(tài)繪制。該方法避免了全局地形模型的重新生成，而只進行少量的局部的必要更新，可以較好地解決大規(guī)模動態(tài)地形可視化的性能問題。

1 LOD混合調(diào)度技術(shù)

結(jié)合預(yù)處理與實時生成更新方法進行LOD的混合調(diào)度，在完成地表過程動態(tài)計算的同時，實現(xiàn)動態(tài)地形的實時可視化和流暢漫游。具體的，先通過傳統(tǒng)的預(yù)處理過程生成基礎(chǔ)的地形瓦片，之后的可視化過程與地表過程計算實時結(jié)合，地表過程模型在原始地形數(shù)據(jù)的基礎(chǔ)上不斷迭代產(chǎn)生新的地形數(shù)據(jù)，而在同步的地形可視化漫游中，首先采用與靜態(tài)模型相同的方法加載預(yù)處理生成的地形瓦片，同時動態(tài)判斷在當(dāng)前視域和分辨率下新動態(tài)地形導(dǎo)致變化的瓦片，系統(tǒng)根據(jù)變化后的新地形，實時的為需要更新的地形生成新的瓦片，并替代之前的瓦片進行渲染。在該過程中，僅重新計算和渲染當(dāng)前視域和LOD層次上受新地形影響的局部瓦片，避免了全局的、所有層次上的瓦片更新，因而可以大幅度降低因數(shù)據(jù)準備而導(dǎo)致的渲染延遲。

LOD技術(shù)控制了同屏渲染的三角形的數(shù)量，也使得屏幕中同時出現(xiàn)的地形瓦片不會特別多，即使在大范圍漫游的情況下，實際更新的瓦片數(shù)量也不會很大。因此，新地形模型的生成并不會消耗太多時間，瓦片更新的延遲也不會很大，而且沒有變化的部分仍以基礎(chǔ)瓦片顯示而無需計算，因此完全可以滿足動態(tài)地形的可視化需求。

該LOD混合調(diào)度技術(shù)的實現(xiàn)分為3個步驟：1)動態(tài)地形的計算。讀取當(dāng)前地形，應(yīng)用過程模型Δh=f(Δt)，迭代計算經(jīng)過一定時間步長后的新地形。這部分工作比較常規(guī)，單純使用原始的地形數(shù)據(jù)即可完成，不涉及可視化部分。2)瓦片的生成以及可視化前的準備工作。經(jīng)過過程計算后的新地形，要先更新LOD瓦片才能實施渲染，這可以看作可視化前的準備。準備工作包括但不限于：動態(tài)判定并實時生成受新地形影響而需更新的瓦片，從原始數(shù)據(jù)提取未受影響的瓦片、提前對顯示列表進行編譯、對紋理作提前編譯等。3)可視化。將準備好的數(shù)據(jù)加入渲染流程。

要實現(xiàn)流暢的可視化效果，一幀的渲染需要在至少1/24 s內(nèi)完成，而上述3個步驟不可能在一幀之內(nèi)完成。因此本文使用多線程技術(shù)，將LOD實時生成的第1步和第2步在其他線程完成，只有第3步才在渲染線程中完成。具體的，本文的調(diào)度技術(shù)涉及3個線程：計算線程、渲染準備線程(簡稱“準備線程”)、渲染線程；3組數(shù)據(jù)：地形數(shù)據(jù)、渲染準備任務(wù)列表(簡稱“任務(wù)列表”)、渲染準備結(jié)果列表(簡稱“結(jié)果列表”)。3個線程與3組數(shù)據(jù)之間的基本調(diào)度關(guān)系如圖1所示。

圖1 動態(tài)地形可視化的多線程模型

Fig.1 Multithread model for dynamic terrain visualization

每個線程的具體工作如下：1)計算線程完成第1步動態(tài)地形的迭代計算，并負責(zé)寫入新產(chǎn)生的地形數(shù)據(jù)。2)渲染線程完成第3步可視化的工作，并負責(zé)寫入任務(wù)列表和讀取結(jié)果列表。渲染線程在每次渲染中檢查是否存在新的地形，當(dāng)計算線程完成一次迭代計算并生成新的地形后，渲染線程會檢測到地形發(fā)生了變化，進而根據(jù)當(dāng)前視域和分辨率判斷需要更新的瓦片，并生成渲染準備任務(wù)，并放入任務(wù)列表。渲染線程還將查看提交的任務(wù)是否完成，如果任務(wù)被處理完，在結(jié)果列表就有了新的地形瓦片，渲染線程將用新的瓦片替代原有的瓦片完成渲染工作。這兩項工作通過揀選回調(diào)和更新回調(diào)完成。3)準備線程完成第2步的瓦片生成和準備工作，負責(zé)讀取地形數(shù)據(jù)以及任務(wù)列表，實時生成需要更新的局部瓦片，并將結(jié)果寫入結(jié)果列表。準備線程會不斷地查詢?nèi)蝿?wù)列表，當(dāng)任務(wù)列表中有待完成的任務(wù)時，就取出任務(wù)，并將任務(wù)生成的新瓦片放入結(jié)果列表。

該動態(tài)地形可視化的LOD混合調(diào)度技術(shù)的具體實現(xiàn)細節(jié)將在下文詳述。

2 基于場景圖的LOD組織管理

2.1 動態(tài)地形LOD的場景圖模型

在動態(tài)地形可視化的混合調(diào)度技術(shù)中，地形LOD基于場景圖進行組織管理。場景圖是用于組織場景信息的圖或樹結(jié)構(gòu)。一棵場景樹包含一個根節(jié)點、多級內(nèi)部的組節(jié)點、多個末端的葉子節(jié)點，其中葉子節(jié)點記錄幾何體信息，主要是地形瓦片數(shù)據(jù)。通過修改組節(jié)點上的變換函數(shù)，可直接作用于子節(jié)點，而無需重復(fù)更改子節(jié)點的屬性，因此可以極大簡化修改操作，有利于大規(guī)模場景的變換和管理。

為了支持動態(tài)地形，將其LOD場景圖組織為四叉樹結(jié)構(gòu)，如圖2所示(以3層為例)。其中LOD節(jié)點用于組織外存數(shù)據(jù)，如果其下一層模型的子節(jié)點多于1個(最多4個)，則用一個組節(jié)點組織在一起。與傳統(tǒng)場景圖最大的不同是，該模型擴展了自定義的動態(tài)瓦片節(jié)點代替原有的幾何體節(jié)點，負責(zé)管理動態(tài)地形的LOD瓦片的信息，包括該節(jié)點所對應(yīng)的地形瓦片的地理范圍、分辨率等參數(shù)，以及上次可視化時的幀數(shù)、上次可視化時所用數(shù)據(jù)的地形迭代計算計數(shù)、是否需要更新等過程狀態(tài)，還需記錄地形數(shù)據(jù)和準備數(shù)據(jù)的指針等。這部分新增的節(jié)點信息用于可視化過程中動態(tài)判斷該節(jié)點瓦片是否需要更新。同時，在動態(tài)瓦片節(jié)點上添加更新回調(diào)和揀選回調(diào)，負責(zé)響應(yīng)線程模型的調(diào)度，具體完成對應(yīng)節(jié)點在必要條件下的瓦片更新工作。瓦片更新的判斷和重新生成工作都在單個節(jié)點上完成，可以有效保證其局部性，并且基于場景圖的結(jié)構(gòu)，可以實時的適應(yīng)并匹配當(dāng)前的視域和分辨率。

圖2 動態(tài)地形LOD的場景圖組織

Fig.2 Scene graph model for dynamic terrain LOD

2.2 更新瓦片的選擇

為了實現(xiàn)局部地形模型的實時生成和更新，需要根據(jù)視點特征，動態(tài)查找需要可視化的地形瓦片，僅僅更新該瓦片的地形模型數(shù)據(jù)。

依據(jù)場景圖的四叉樹結(jié)構(gòu)，確定瓦片的可視判斷策略。具體的，從第0層地形模型開始判斷，當(dāng)進入到第l層時，對該層第x行y列的瓦片tl,x,y，判斷視點到該瓦片的距離distancel,x,y。對于給定閾值thresholdl，如果該距離在[thresholdl,∞]內(nèi)，則該瓦片可視，并停止判斷；否則該瓦片不可見，并進入該瓦片的所有子節(jié)點，繼續(xù)判斷。但需要注意，可視距離判斷的區(qū)間是[thresholdl,∞],而非[thresholdl,thresholdl-1]，這是由于tl,x,y與tl-1,x,y的中心并不相同，使用后者進行判斷，會造成某些視點下瓦片顯示不完全。而當(dāng)進入最底層瓦片時，則不需要判斷，直接顯示。

在瓦片的選擇中，需要決定如何設(shè)置距離閾值thresholdl。本文使用屏幕像素作為確定thresholdl的標準，即thresholdl應(yīng)使得地形模型中的n個頂點投影在屏幕上時，正好對應(yīng)屏幕上的n個像素，則：

(1)

式中:fovy為視場在垂直方向的夾角，一般為60°；p為屏幕在fovy相應(yīng)維度的分辨率，一般為列分辨率；rl為l層地形模型的分辨率。

2.3 回調(diào)機制的選擇

對于場景圖的管理，除了執(zhí)行繪制，系統(tǒng)還需要響應(yīng)用戶操作，進而實現(xiàn)視角的調(diào)整、幾何體的更新，并通過揀選優(yōu)化顯示效率。因此，一幀的顯示，執(zhí)行的不只是繪制遍歷，而是更新、揀選、繪制3種遍歷。其中，更新遍歷允許修改場景中的幾何體、更改視點，以實現(xiàn)動態(tài)場景和場景漫游；揀選遍歷從待繪制的大量幾何體中挑選出當(dāng)前視域可見的部分，之后的繪制遍歷只需執(zhí)行這些幾何體的繪制，提高繪制效率；繪制遍歷使用揀選遍歷過程生成的渲染列表，實現(xiàn)幾何體的渲染。對于不同的應(yīng)用場景，三種遍歷的行為也有所不同，可以通過圖形引擎提供的回調(diào)機制，編寫自己的回調(diào)函數(shù)，自定義更新、揀選、繪制遍歷的行為。

在渲染線程中，由于節(jié)點的可視判斷是在更新遍歷中完成，這表明在場景的更新遍歷完成之前還不能確定所有節(jié)點是否可視。所以發(fā)現(xiàn)需要更新的節(jié)點并生成任務(wù)寫入任務(wù)列表的工作，不能通過更新回調(diào)完成。在本文中，這部分工作通過揀選回調(diào)實現(xiàn)。而幾何體的更改必須在更新遍歷中完成，否則后續(xù)流程很有可能產(chǎn)生錯誤，甚至是線程沖突的。因此在本文中，任務(wù)完成后查詢結(jié)果列表并替換渲染幾何體的工作，通過更新回調(diào)實現(xiàn)。

同時還需注意一個任務(wù)組織的問題。由于準備線程會不斷查看任務(wù)列表，并取出待完成任務(wù)。如果任務(wù)的發(fā)起是由單個節(jié)點完成的，那么當(dāng)單個節(jié)點發(fā)出任務(wù)后，就會馬上被準備線程取走，造成任務(wù)的碎片化，影響效率。所以本文中，任務(wù)的發(fā)出以幀為單位，將當(dāng)前幀的所有任務(wù)收集后，再統(tǒng)一放入任務(wù)列表。具體方法為，動態(tài)瓦片葉節(jié)點在其裁剪回調(diào)中生成任務(wù)，并放入臨時任務(wù)列表，在下一幀根節(jié)點的更新回調(diào)中，查看臨時任務(wù)列表，并將其中的任務(wù)放入任務(wù)列表。

回調(diào)功能添加在LOD節(jié)點或葉子節(jié)點中都可以實現(xiàn)?？紤]到葉子節(jié)點的裁減回調(diào)可以更方便明確地獲取需要可視化的節(jié)點，本文選擇在葉子節(jié)點，即動態(tài)地形瓦片節(jié)點上添加更新回調(diào)和揀選回調(diào)。

3 多線程模型

在該多線程模型的實現(xiàn)中，除渲染所用的數(shù)據(jù)外，還需要地形數(shù)據(jù)用于記錄動態(tài)變化的地形，需要準備數(shù)據(jù)用于記錄任務(wù)列表和結(jié)果列表。

(1)計算線程。計算線程不斷調(diào)用地形過程模型進行迭代計算。過程模型在外部定義，計算結(jié)果一般為新的DEM數(shù)據(jù)。每次迭代計算完成后，產(chǎn)生新的地形數(shù)據(jù)，并令迭代計數(shù)增加1。渲染線程可以查看對比自身的迭代計數(shù)，判斷是否需要更新。

(2)渲染線程。渲染線程的工作通過揀選回調(diào)和更新回調(diào)完成。揀選回調(diào)的工作是在當(dāng)前視域和LOD層次的條件下，判斷因新產(chǎn)生的地形數(shù)據(jù)而需要更新的瓦片，將其生成任務(wù)并放入任務(wù)列表。具體的，首先記錄當(dāng)前幀數(shù)，然后判斷當(dāng)前瓦片節(jié)點是否需要更新。在更新判斷過程中，首先比較動態(tài)地形瓦片節(jié)點的范圍與當(dāng)前動態(tài)區(qū)域的范圍是否重合，然后基于迭代計數(shù)判斷該動態(tài)地形瓦片的數(shù)據(jù)是否是最新的地形。如果既重合又不是最新地形，則該瓦片需要更新，這時將一個更新該瓦片的任務(wù)放入準備數(shù)據(jù)的任務(wù)列表，并且設(shè)置更新標記為true。揀選回調(diào)流程如圖3所示。

圖3 揀選回調(diào)流程

Fig.3 Culling callback flow diagram

更新回調(diào)是查看結(jié)果列表中是否存在已完成的瓦片更新任務(wù)的結(jié)果，若存在則用新的瓦片替換舊的瓦片。在判斷瓦片是否需要更新的過程中，先查看更新標記，然后比較上次幀數(shù)和當(dāng)前幀數(shù)，判斷該節(jié)點上一次的渲染是否很接近。如果更新標記為true，同時幀數(shù)也在一定范圍內(nèi)，則需要更新該節(jié)點，否則說明該節(jié)點已經(jīng)不在視野內(nèi)，則不必更新。當(dāng)節(jié)點需要更新時，查看準備數(shù)據(jù)的結(jié)果列表是否存在當(dāng)前節(jié)點的結(jié)果，如果存在則更新該動態(tài)地形瓦片節(jié)點。更新回調(diào)流程如圖4所示。

圖4 更新回調(diào)流程

Fig.4 Updating callback flow diagram

(3)準備線程。準備線程不斷查看準備數(shù)據(jù)的任務(wù)列表，如果不為空，則取出其中的任務(wù)進行處理，根據(jù)任務(wù)信息實時生成相應(yīng)節(jié)點的新瓦片數(shù)據(jù)，并在任務(wù)處理完成后，將結(jié)果放入結(jié)果列表。處理任務(wù)時需要讀取地形數(shù)據(jù)，并利用LOD算法生成局部瓦片。在有些情況下，一些節(jié)點發(fā)出了準備任務(wù)，但是在任務(wù)完成前就離開了視域，而由此生成的結(jié)果則將在結(jié)果列表中滯留，不會被取走，因此準備線程還需要負責(zé)清除這部分滯留的結(jié)果。

4 實驗驗證

4.1 實驗方法

針對本文提出的動態(tài)地形可視化的LOD調(diào)度技術(shù)，開展實驗測試并驗證其性能。實驗硬件環(huán)境使用PC機，主板芯片組Intel HM65，中央處理器Intel Core i7-4700MQ，顯示適配器NVIDIA GeForce GTX 765 M (2 GB)，內(nèi)存16 GB (DDR3-1600 SDRAM)，硬盤Hitachi 750 GB 7200RPM。軟件環(huán)境為操作系統(tǒng)Microsoft Windows 7 Ultimate 64-bit(Service Pack 1)，顯示設(shè)備驅(qū)動版本NVIDIA ForceWare 340.62。圖形開發(fā)環(huán)境為OpenGL 4.40，部分基礎(chǔ)功能在OpenSceneGraph 3.2.0基礎(chǔ)上擴展實現(xiàn)。OpenSceneGraph是一個基于OpenGL的由C實現(xiàn)的開源圖形引擎，以場景圖為核心組織三維場景(http://www.openscenegraph.org/)。

實驗測試用的原始地形數(shù)據(jù)是SRTM 90 m中國南方部分區(qū)域的格網(wǎng)DEM數(shù)據(jù)，經(jīng)緯度范圍是102°～113°E，27°～32°N。將上述地形數(shù)據(jù)重采樣為173 MB、690 MB、1.5 GB、3.4 GB的4份DEM數(shù)據(jù)進行測試。

實驗選擇一個典型的流域地貌演化模型進行動態(tài)過程計算，該模型可簡化表示為[14]：

(2)式中:h為地形高程，t為時間，S為地形坡度；Q為單位寬度徑流量，基于降水量經(jīng)過匯流累積計算獲得，為簡化模型復(fù)雜度，實驗中將降水量簡化為均勻持續(xù)降水；β、m、n、k是不隨高程和時間變化的模型參數(shù)，經(jīng)率定得到β=0.01，m=1.1，n=0.3，k=0.02 m2/a。為增強測試效果，對模型迭代的時間步長進行了夸大。

4.2 實驗結(jié)果

使用上述測試數(shù)據(jù)和過程模型，采用遠近兩種視點、不同大小的動態(tài)地形區(qū)域進行測試。測試中關(guān)閉垂直同步，以便通過幀速率判斷性能。實驗的地貌演化動態(tài)效果如圖5所示。

圖5 動態(tài)地形可視化效果

Fig.5 Visualization results of dynamic terrain

動態(tài)可視化的性能測試結(jié)果如表1所示。另外，使用3.4 GB、動態(tài)范圍為20 000×10 000的DEM數(shù)據(jù)，測得一個典型可視化漫游過程的幀率變化如圖6所示。在各測試環(huán)境中都達到了大于60幀/s的顯示速率，滿足可視化需求。

表1 實驗性能

Table 1 Efficiency of the technology

數(shù)據(jù)量分辨率動態(tài)范圍視角幀率173MB10085×44702000×2000遠1329173MB10085×44702000×2000近324173MB10085×44705000×2000遠1329173MB10085×44705000×2000近329690MB20170×89402000×2000遠1360690MB20170×89402000×2000近273690MB20170×894010000×5000遠1325690MB20170×894010000×5000近2751.5GB30255×134102000×2000遠12671.5GB30255×134102000×2000近2521.5GB30255×1341015000×7000遠12911.5GB30255×1341015000×7000近2413.4GB45382×201152000×2000遠12083.4GB45382×201152000×2000近2103.4GB45382×2011520000×10000遠12813.4GB45382×2011520000×10000近208

圖6 典型漫游下的幀速率

Fig.6 Frame rate under classical roaming

動態(tài)地形的數(shù)據(jù)調(diào)度過程必然會降低渲染效率，因此有必要對本文提出的動態(tài)調(diào)度技術(shù)的性能進行評價。分別在開/關(guān)動態(tài)地形的情況下，對可視化幀率進行測試對比，其結(jié)果如表2所示，其中每行的測試數(shù)據(jù)和參數(shù)與表1對應(yīng)。在測試環(huán)境下，動態(tài)過程造成的可視化性能損失均小于10%，證明本文方法具有很好的性能。

對比近年的已有研究，本文方法具有較好的性能。Koca等在2 048×2 048的DEM數(shù)據(jù)上疊加動態(tài)地形要素，其渲染性能平均可達235幀/s[12]。Kang等提出的多分辨率地形渲染方法，在16 000×16 000和32 000×32 000的DEM數(shù)據(jù)上，平均幀速率達423幀/s[11]。李欽等實現(xiàn)的基于分塊LOD的地形實時渲染算法，對于4 097×4 097的DEM數(shù)據(jù)，在中遠視角下漫游的平均幀速率達877幀/s[15]。而本文方法在考慮動態(tài)地形的情況下，多組測試數(shù)據(jù)上的渲染性能(表1、圖6)平均可達658幀/s，其中近視角下達225幀/s，中遠視角下達875幀/s，可視化性能均達到或高于已有研究成果。

表2 動態(tài)地形可視化的性能損失

Table 2 Efficiency loss of dynamic terrain visualization

動態(tài)幀率非動態(tài)幀率性能損失動態(tài)幀率非動態(tài)幀率性能損失132913572.06%126713002.54%3243301.82%2522571.95%132913572.06%126713002.54%3293300.30%2332579.34%136013640.29%120812745.18%2732792.15%1912109.05%132513642.86%126312740.86%2752791.43%2082100.95%

5 結(jié)論

面向土壤侵蝕、地貌演化等地形過程模擬的應(yīng)用需求，提出了一種預(yù)處理與實時更新相結(jié)合的LOD混合調(diào)度技術(shù)，實現(xiàn)大規(guī)模動態(tài)地形可視化?；趫鼍皥D組織管理大規(guī)模地形的LOD模型，支持動態(tài)地形瓦片的實時查找、更新和繪制，提出并實現(xiàn)LOD瓦片動態(tài)調(diào)度和繪制的多線程模型，利用計算線程和準備線程分別負責(zé)動態(tài)地形的計算和地形瓦片的生成，利用渲染線程發(fā)現(xiàn)需更新的地形瓦片并及時更新。該技術(shù)以LOD瓦片的動態(tài)更新繪制替代靜態(tài)預(yù)處理方法，在地表過程模型迭代計算的同時，同步更新地形瓦片，并且僅更新在當(dāng)前視域和分辨率下發(fā)生變化的局部瓦片，避免了全局更新的大量計算，使得瓦片更新過程不會對渲染速度產(chǎn)生明顯的影響，從而大幅度提高可視化性能。對于GB級以上的DEM數(shù)據(jù)，動態(tài)地形可視化幀速率達60幀/s以上，可有效滿足地形過程模擬可視化的性能需求。在本文的技術(shù)實現(xiàn)中還未加入對紋理的支持，另外在大視野場景下的漫游，會出現(xiàn)輕微的局部新地形的視覺抖動現(xiàn)象，這是下階段需要解決的問題。

[1] SMELIK R M,TUTENEL T,BIDARRA R,et al.A survey on procedural modeling for virtual worlds[J].Computer Graphics Forum,2014,33(6):31-50.

[2] 湯國安，劉學(xué)軍，閭國年.數(shù)字高程模型及地學(xué)分析的原理與方法[M].北京：科學(xué)出版社,2005.

[3] 李清泉，楊必勝，史文中，等.三維空間數(shù)據(jù)的實時獲取、建模與可視化[M].武漢：武漢大學(xué)出版社,2003.

[4] DUCHAINEAU M,WOLINSKYM,SIGETI D E,et al.ROAMing terrain:Real-time optimally adapting meshes[A].Proceedings of the 8th Conference on Visualization′97[C].Washington,DC:IEEE Computer Society Press,1997.81-88.

[5] R?TTGER S,HEIDRICH W,SEIDEL H P.Real-time generation of continuous levels of detail for height fields[A].Proceedings WSCG′98[C].Plzen:Union Agency,1998.315-322.

[6] URLICH T.Rendering massive terrains using chunked level of detail control[A].Proceedings of ACM SIGGRAPH′02[C].San Antonio,TX:ACM Press,2002.

[7] CIGNONI P.Planet-sized Batched Dynamic Adaptive Meshes (P-BDAM)[A].Proceedings of the 14th IEEE Conference on Visualization (VIS′03)[C].Washington,DC:IEEE Computer Society,2003.147-154.

[8] ASIRVATHAM A,HOPPE H.Terrain rendering using GPU-based geometry clipmaps[A].PHARR M,FERNANDO R.GPU Gems 2[C].Boston,MA:Addison-Wesley,2005.46-53.

[9] LIVNY Y,KOGAN Z,EL-SANA J.Seamless patches for GPU-based terrain rendering[J].The Visual Computer,2009,25 (3):197-208.

[10] HU L,SANDER P V,HOPPE H.Parallel view-dependent refinement of progressive meshes[A].Proceedings of the Symposium on Interactive 3D Graphics and Games (I3D′09)[C].Boston,MA.New York:ACM,2009.169-176.

[11] JANG H Y,CHO C S,HAN J H.Multi-resolution terrain rendering with GPU tessellation[J].The Visual Computer,2015,31(4):455-469.

[12] KOCA ,G D KBAY U.A hybrid representation for modeling,interactive editing,and real-time visualization of terrains with volumetric features[J].International Journal of Geographical Information Science,2014,28(9):1821-1847.

[13] TATEOSIAN L,MITASOVA H,THAKUR S,et al.Visualizations of coastal terrain time series[J].Information Visualization,2014,13(3):266-282.

[14] 劉光.基于GIS的現(xiàn)代黃土地貌演化過程動態(tài)仿真研究[D].北京：北京大學(xué)，2003.

[15] 李欽,戴樹嶺,趙永嘉，等.分塊LOD大規(guī)模地形實時渲染算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報， 2013,25(5):708-713.

A LOD Scheduling Method for Massive Dynamic Terrain Visualization

GAO Yong,LIU Jia-jun,GUO Xiao,WU Lun

(Institute of Remote Sensing and Geographical Information System,Peking University,Beijing 100871,China)

The processes modeling and simulation,e.g.geomorphic processes and land processes,will iteratively generate a series of terrain data in real time.This dynamic process needs more efficient visualization technologies.But the traditional preprocessing-based methods cannot fulfill it for the rendering delay caused by huge computation.A hybrid LOD scheduling method is presented integrating preprocessing and real-time update to visualize massive dynamic terrain.The terrain LODs are modeled and managed based on the scene graph,and a multithread model is introduced to update and render the terrain tiles dynamically.Instead of reconstructing the whole visualization data,this method only update and render the necessary local LOD tiles for the new terrain data iteratively.So the visualization efficiency can be improved significantly.

terrain visualization;level of detail model;scene graph;multithread;dynamic scheduling

2015-09-10；

2015-10-16

國家863支持項目(2011AA120301、2011AA120303)

高勇(1974-)，男，博士，副教授，研究方向為高性能地理計算與空間數(shù)據(jù)挖掘。E-mail:gaoyong@pku.edu.cn

10.3969/j.issn.1672-0504.2016.01.002

P208

A

1672-0504(2016)01-0006-06