摘  要： 在分析LOD內(nèi)在并行性的基礎(chǔ)上，利用通用的并行編程環(huán)境OpenMP對(duì)其進(jìn)行線程化，提出了一種基于四叉樹網(wǎng)格劃分的并行簡化算法，并在四核計(jì)算機(jī)上應(yīng)用Intel parallel amplifier分析器按函數(shù)查看性能變化，對(duì)比優(yōu)化前后的數(shù)據(jù)，結(jié)果表明并行化后的加速比和計(jì)算效率有了顯著提高。
關(guān)鍵詞： 多核；并行；LOD；四叉樹；OpenMP ；Intel parallel amplifier

　計(jì)算機(jī)體系結(jié)構(gòu)正向多處理器以及多核架構(gòu)方向發(fā)展，多核平臺(tái)應(yīng)用越來越普及。因此，多核并行計(jì)算技術(shù)及其應(yīng)用已成為計(jì)算機(jī)領(lǐng)域新的發(fā)展趨勢(shì)，充分利用多核硬件可以有效提高系統(tǒng)應(yīng)用程序的性能。計(jì)算機(jī)硬件繪圖技術(shù)一直在高速發(fā)展，特別強(qiáng)調(diào)實(shí)時(shí)性、低延遲、穩(wěn)定的圖像速度以及圖像清晰度，但是現(xiàn)有技術(shù)仍然不能滿足3D場景的實(shí)時(shí)繪制。
    地形是自然界最復(fù)雜的景物之一，要實(shí)時(shí)模擬具有真實(shí)感的大范圍三維地形，最大的難點(diǎn)是如何精簡并有效地組織地形數(shù)據(jù)，以達(dá)到高速度、高精確度的可視化目的。為了獲得高效和理想的視覺效果和計(jì)算機(jī)處理的速度，需要采用一種技術(shù)對(duì)場景中的模型進(jìn)行有效的處理。細(xì)節(jié)層次模型LOD（Level of Detail）是一種可以解決簡化地形、加快渲染速度的繪制方法。然而大部分圖形系統(tǒng)或其他類型的應(yīng)用程序仍然使用單線程，這就使多核系統(tǒng)平臺(tái)的資源并不能得到完全的利用。針對(duì)細(xì)節(jié)層次模型采用四叉樹（Quad Tree）的數(shù)據(jù)結(jié)構(gòu)、待處理的數(shù)據(jù)量和計(jì)算量都非常大的特點(diǎn)，本文提出了一種在多核計(jì)算機(jī)上基于四叉樹劃分的并行模型簡化算法，對(duì)三維地形系統(tǒng)進(jìn)行優(yōu)化。
1 多核并行程序設(shè)計(jì)
    多核并行計(jì)算技術(shù)是當(dāng)前計(jì)算機(jī)領(lǐng)域的研究熱點(diǎn)，在未來數(shù)年內(nèi)，隨著芯片內(nèi)核數(shù)量持續(xù)增長，多核計(jì)算將成為一種廣泛普及的計(jì)算模式[1]。要想真正獲得多核處理器帶來的高效率，軟件的發(fā)展必須跟上硬件的步伐，而當(dāng)前多核處理器軟件總體滯后于硬件。多核處理器為實(shí)施計(jì)算任務(wù)的細(xì)粒度并行機(jī)制提供了必要的硬件基礎(chǔ)，只有在算法設(shè)計(jì)及軟件開發(fā)能夠充分利用多核處理器的特性時(shí)，其優(yōu)勢(shì)才能真正體現(xiàn)出來。并行計(jì)算是指同時(shí)對(duì)多個(gè)任務(wù)或多條指令，或多個(gè)數(shù)據(jù)項(xiàng)進(jìn)行處理[2]。目前適應(yīng)多核處理器并行算法的可行的解決方案是多線程化計(jì)算任務(wù)，并使計(jì)算負(fù)載能盡量均衡地分配到各個(gè)內(nèi)核上。而計(jì)算任務(wù)的線程化存在的兩個(gè)難點(diǎn)是尋找任務(wù)中可并行計(jì)算成分與線程化工具的選擇。
    OpenMP為共享地址空間的并行計(jì)算提供支持，具有使用簡單的特點(diǎn)。它由一組小型的編譯器命令集組成，包括一套編譯指令和一個(gè)用來支持它的函數(shù)庫，對(duì)于同步共享變量、合理分配負(fù)載等任務(wù)，都提供了有效支持，具有簡單通用、開發(fā)快速的特點(diǎn)。Intel Parallel Amplifier是Intel新推出的性能測(cè)試工具，使用Intel Parallel Amplifier可以簡單快速找到多核性能瓶頸。生成應(yīng)用程序后，用Parallel Amplifier可對(duì)多種類型函數(shù)進(jìn)行分析，收集不同類型的性能數(shù)據(jù)，查看結(jié)果并深入觀察造成某個(gè)問題的相關(guān)源代碼。其中熱點(diǎn)分析功能可識(shí)別出最耗時(shí)的函數(shù)以及是否有效利用了所有處理器內(nèi)核。

    LOD細(xì)節(jié)層次是指對(duì)同一場景或場景中的物體，使用具有不同細(xì)節(jié)的描述方法得到一組模型，供繪制時(shí)選擇使用[3]。LOD層次細(xì)節(jié)簡化作為一種通用而有效的四叉樹算法，已在地理信息系統(tǒng)、虛擬現(xiàn)實(shí)、災(zāi)害仿真和戰(zhàn)場環(huán)境仿真等領(lǐng)域中有著重要的應(yīng)用。大規(guī)模地形LOD模型的預(yù)處理系統(tǒng)是一個(gè)完整、穩(wěn)定的算法框架，內(nèi)含的剖分、劃點(diǎn)、連線等操作都是一些并行性非常強(qiáng)的運(yùn)算過程，滿足并行化的要求。在多核處理器計(jì)算環(huán)境中將這些操作進(jìn)行線程并行化，可使LOD的運(yùn)行效率得到極大提高，使系統(tǒng)資源得到充分利用。
2 LOD模型簡化
    為了滿足大規(guī)模虛擬地形應(yīng)用在渲染速度和顯示分辨率等方面的要求，應(yīng)采取一定的算法來簡化地形數(shù)據(jù)。細(xì)節(jié)層次LOD是一種非常有效的控制場景復(fù)雜度的方法。該方法由Clark于1976年提出[4]，其基本思想是用具有多層次結(jié)構(gòu)要素的集合描述目標(biāo)。其基本原理是在不影響場景視覺效果的基礎(chǔ)上，通過逐級(jí)簡化景物的表面細(xì)節(jié)來減少場景的幾何復(fù)雜度，以提高繪制算法的效率。當(dāng)物體覆蓋較小區(qū)域時(shí)，可以使用該物體描述較粗的模型并給出一個(gè)用于可見面判斷算法的幾何層次模型，以便對(duì)復(fù)雜場景進(jìn)行快速的繪制。在場景的動(dòng)態(tài)顯示中，當(dāng)視點(diǎn)距離某一物體很近時(shí)，它的圖像在屏幕上占據(jù)較多的像素，而當(dāng)視點(diǎn)距離它很遠(yuǎn)時(shí)，圖像在屏幕上占據(jù)很少的像素，甚至是一個(gè)像素。在這種情況下用大量的三角形網(wǎng)格去精確地表示物體已經(jīng)沒有必要，可以適當(dāng)合并一些三角形，而不損失畫面的視覺效果。這樣既保證場景的視覺效果，又能提高場景的繪制幀速，改善系統(tǒng)的實(shí)時(shí)性。
    LOD建模是采用一定的算法思想將原有的網(wǎng)格地形數(shù)據(jù)重組，得到一種更加便于實(shí)時(shí)繪制使用的數(shù)據(jù)結(jié)構(gòu)。本文所用到的LOD細(xì)節(jié)層次模型采用四叉樹的數(shù)據(jù)結(jié)構(gòu)，逐級(jí)劃分四叉樹直到某一種條件得到滿足為止。在用來描述地形的數(shù)據(jù)結(jié)構(gòu)中，四叉樹非常有效，它的每個(gè)節(jié)點(diǎn)（除葉子節(jié)點(diǎn)外）都有4個(gè)子節(jié)點(diǎn)，這4個(gè)子節(jié)點(diǎn)平均地劃分它們的父節(jié)點(diǎn)所占據(jù)的區(qū)域，依次類推，直到葉子節(jié)點(diǎn)[5]。葉子節(jié)點(diǎn)是渲染和貼圖的最小單位。分割的深度越大，得到的分辨率就會(huì)越高，即分割深度每提高一層，采樣的密度便提高一倍[6]。本文實(shí)驗(yàn)程序選用的四叉樹的深度為8，即采樣的密度為256×256個(gè)網(wǎng)格空間，算法空間剖分如圖1所示。圖中每一個(gè)正方形為四叉樹的一個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)保存了一定區(qū)域的信息，包括經(jīng)緯度、中心點(diǎn)的高度、邊節(jié)點(diǎn)的高度等。

3 LOD多線程并行模型生成
3.1 四叉樹的構(gòu)建
    在利用四叉樹方法進(jìn)行LOD建模的過程中，其關(guān)鍵就在于怎樣對(duì)原有的網(wǎng)格數(shù)據(jù)進(jìn)行四叉樹分層。四叉樹分層方法是從整個(gè)完整的地形出發(fā)，遞歸地把地形不斷地分割成相等的四個(gè)區(qū)域，分割的深度越大，則得到的分辨率越高。在進(jìn)行四叉樹分層的過程中，由于四叉樹分層是針對(duì)(2n+1)×(2n+1)的規(guī)則網(wǎng)格而言的，數(shù)據(jù)格式應(yīng)盡量滿足規(guī)則網(wǎng)格的要求，即網(wǎng)格數(shù)據(jù)必須是間隔均勻的正方形區(qū)域。如果網(wǎng)格數(shù)據(jù)的大小不滿足該條件，則需要擴(kuò)展其幾何圖形，擴(kuò)展部分的像素用空值填充。其次在四叉樹分層過程中，還必須滿足四叉樹中相鄰的兩個(gè)節(jié)點(diǎn)的層次最大不能相差1，否則在LOD模型連續(xù)拼接的地方就會(huì)出現(xiàn)裂縫。其基本思路是先把地形一分為四，用遞歸的方法對(duì)每個(gè)網(wǎng)格渲染。對(duì)每個(gè)網(wǎng)格，如果達(dá)到最高精度，則退出，如果不在視野內(nèi)也退出；再對(duì)符合條件的網(wǎng)格遞歸下去。本文實(shí)驗(yàn)利用OpenGL實(shí)現(xiàn)的地形場景渲染效果如圖2所示，對(duì)應(yīng)的地形網(wǎng)格模型如圖3所示。

3.2 模型生成并行化
    OpenMP應(yīng)用程序接口是針對(duì)共享內(nèi)存多處理器體系結(jié)構(gòu)的可移植并行編程模型，能夠支持并行計(jì)算時(shí)對(duì)線程和變量的靈活設(shè)置和控制。OpenMP經(jīng)常用于循環(huán)層并行，但它同樣支持函數(shù)層并行，在并行繪制系統(tǒng)中存在一些函數(shù)調(diào)用，可使用OpenMP提供的sections子句進(jìn)行函數(shù)級(jí)并行化，前提是并行的函數(shù)之間無依賴性。
    LOD并行模型簡化算法需要考慮的因素主要是模型的剖分。對(duì)模型進(jìn)行適當(dāng)?shù)钠史?，從而?shí)現(xiàn)各模型分塊的并行簡化、任務(wù)分配與負(fù)載平衡，合理的任務(wù)分配能充分發(fā)揮并行計(jì)算的優(yōu)勢(shì)。為了使簡化后的模型在LOD顯示時(shí)方便地調(diào)用，直接應(yīng)用四叉樹對(duì)模型進(jìn)行并行剖分成為一種選擇。本文采用多線程的方法在初始化階段將地形模型進(jìn)行剖分，四叉樹每個(gè)葉子節(jié)點(diǎn)所對(duì)應(yīng)的分塊內(nèi)的模型即為一個(gè)元任務(wù)塊。每個(gè)四叉樹節(jié)點(diǎn)對(duì)應(yīng)一個(gè)任務(wù)塊，由主節(jié)點(diǎn)按照任務(wù)分配策略將一個(gè)個(gè)元任務(wù)塊發(fā)送給子節(jié)點(diǎn)進(jìn)行并行簡化。實(shí)驗(yàn)環(huán)境選用的是四核計(jì)算機(jī)，且采用四叉樹結(jié)構(gòu)對(duì)原始模型進(jìn)行平均剖分；根據(jù)線程數(shù)等于CPU核數(shù)時(shí)性能最好原則，設(shè)定為4線程。在四叉樹第一層剖分時(shí)把原任務(wù)塊平均分成四個(gè)子塊，分別獨(dú)立地在四個(gè)工作區(qū)線程上完成指定深度的剖分任務(wù)，即把整個(gè)地形的工作量分配到四個(gè)處理核上同時(shí)工作。
3.3 OpenMP分塊設(shè)置過程
    在并行構(gòu)造中，可以設(shè)置條件決定是否對(duì)可并行區(qū)域中的代碼塊作并行。OpenMP提供了if 子句來實(shí)現(xiàn)條件并行。設(shè)置條件并行先給每個(gè)線程平均分配一個(gè)任務(wù)塊，把整個(gè)區(qū)域的地形平均地分成四塊工作區(qū)，再用if 子句把地形分成四個(gè)均等的任務(wù)塊。sections和section命令是OpenMP里用來設(shè)置分區(qū)的一種方式，先用sections定義一個(gè)區(qū)塊，然后用section將區(qū)塊劃分成幾個(gè)不同的段，每段都并行執(zhí)行。在每一個(gè)并行區(qū)域中都會(huì)有一個(gè)隱含的同步屏障，執(zhí)行此并行區(qū)域的線程組在執(zhí)行完本區(qū)域代碼之前需要同步并行區(qū)域的所有線程。因此要充分考慮任務(wù)分塊的均衡，以免浪費(fèi)CPU資源。并行劃分程序部分代碼如下：
    #pragma omp parallel sections  if(i==1) num_threads(4)
    //定義一個(gè)生成四叉樹的并行區(qū)域
        {
            #pragma omp section
            西北分區(qū)塊NORTH WEST（NW）
            #pragma omp section
            東北分區(qū)塊NORTH EAST（NE）
            #pragma omp section
            西南分區(qū)塊SOUTH WEST（SW）
            #pragma omp section
            東南分區(qū)塊SOUTH EAST（SE）
        }
4 實(shí)驗(yàn)結(jié)果
    實(shí)驗(yàn)環(huán)境：Intel(R)Core(TM) 2 Quad CPU Q9400 @
2.66 GHz(4 CPUs) ，3.00 GB內(nèi)存； Microsoft Visual Studio 2008，Intel Parallel Amplifier(并行放大器)，OpenGL圖形庫，DirectX應(yīng)用程序接口。
    實(shí)驗(yàn)數(shù)據(jù)為256 bit×256 bit的地形高度圖，以分析draw、draw_point、setup_quadtree函數(shù)為例，測(cè)出單線程、雙線程和四線程的運(yùn)行時(shí)間。對(duì)優(yōu)化前后的結(jié)果進(jìn)行比較，獲得加速比和CPU效率。函數(shù)運(yùn)行測(cè)試數(shù)據(jù)如表1所示，分析比較結(jié)果如圖4所示。

    從實(shí)驗(yàn)結(jié)果可以看出，四叉樹算法的場景渲染函數(shù)經(jīng)過多線程優(yōu)化后執(zhí)行時(shí)間有很大的改進(jìn)，性能得到了較大的提升?？偟膩碚f，系統(tǒng)不僅實(shí)現(xiàn)了高分辨率的顯示效果，而且實(shí)現(xiàn)了渲染速度的顯著提高。將工作任務(wù)平均地分配到四個(gè)線程上，加速比和CPU利用率都得到了改進(jìn)，也看出多線程程序設(shè)計(jì)對(duì)于大型三維場景創(chuàng)建來說是加快運(yùn)行速度、提高效率的很好的方法。
    本算法提高了三維地形場景渲染系統(tǒng)生成的速度，實(shí)現(xiàn)了高真實(shí)度的三維地形場景的可視化和快速漫游，并采用了OpenGL編程實(shí)現(xiàn)了這個(gè)算法。通過實(shí)驗(yàn)說明了該方法充分利用了多核平臺(tái)的優(yōu)勢(shì)，有效提高了系統(tǒng)的性能。在LOD技術(shù)中，多核平臺(tái)的應(yīng)用將越來越廣泛，還有很多內(nèi)容需要進(jìn)一步研究，例如物體表面屬性色彩、紋理等的統(tǒng)一處理，多分辨率模型的管理，視點(diǎn)和視區(qū)有關(guān)的LOD生成和繪制算法，模型近似誤差度量標(biāo)準(zhǔn)以及多分辨率模型簡化的并行化研究等，因此本文的方法具有廣闊的應(yīng)用前景。
參考文獻(xiàn)
[1] 周偉明.多核計(jì)算與程序設(shè)計(jì)[M].武漢:華中科技大學(xué)出版社,2009.
[2] 張林波，遲學(xué)斌,莫?jiǎng)t堯，等.并行計(jì)算導(dǎo)論[M].北京：清華大學(xué)出版社,2006.
[3] 宋雙柱,薛群,孫立鐫.SLOPE法線生成算法的LOD技術(shù)在地形渲染中的應(yīng)用[J].哈爾濱理工大學(xué)學(xué)報(bào),2009,10
(5):63-65.
[4] CLARK J H.Hierarchical geometric models for visible surface algorithms[J].Communications of the ACM,1976,19(10):547-554.
[5] 李勝,俊峰.超大規(guī)模地形場景的高性能漫游[J].軟件學(xué)報(bào), 2006,17(3):535-545.
[6] 王磊，毛利民，李騫.基于LOD的三維地形可視化[J].計(jì)算機(jī)與信息技術(shù), 2007，15（7）：39-41.