摘  要： 在分析LOD內在并行性的基礎上，利用通用的并行編程環境OpenMP對其進行線程化，提出了一種基于四叉樹網格劃分的并行簡化算法，并在四核計算機上應用Intel parallel amplifier分析器按函數查看性能變化，對比優化前后的數據，結果表明并行化后的加速比和計算效率有了顯著提高。
關鍵詞： 多核；并行；LOD；四叉樹；OpenMP ；Intel parallel amplifier

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

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

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

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

    從實驗結果可以看出，四叉樹算法的場景渲染函數經過多線程優化后執行時間有很大的改進，性能得到了較大的提升?？偟膩碚f，系統不僅實現了高分辨率的顯示效果，而且實現了渲染速度的顯著提高。將工作任務平均地分配到四個線程上，加速比和CPU利用率都得到了改進，也看出多線程程序設計對于大型三維場景創建來說是加快運行速度、提高效率的很好的方法。
    本算法提高了三維地形場景渲染系統生成的速度，實現了高真實度的三維地形場景的可視化和快速漫游，并采用了OpenGL編程實現了這個算法。通過實驗說明了該方法充分利用了多核平臺的優勢，有效提高了系統的性能。在LOD技術中，多核平臺的應用將越來越廣泛，還有很多內容需要進一步研究，例如物體表面屬性色彩、紋理等的統一處理，多分辨率模型的管理，視點和視區有關的LOD生成和繪制算法，模型近似誤差度量標準以及多分辨率模型簡化的并行化研究等，因此本文的方法具有廣闊的應用前景。
參考文獻
[1] 周偉明.多核計算與程序設計[M].武漢:華中科技大學出版社,2009.
[2] 張林波，遲學斌,莫則堯，等.并行計算導論[M].北京：清華大學出版社,2006.
[3] 宋雙柱,薛群,孫立鐫.SLOPE法線生成算法的LOD技術在地形渲染中的應用[J].哈爾濱理工大學學報,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] 李勝,俊峰.超大規模地形場景的高性能漫游[J].軟件學報, 2006,17(3):535-545.
[6] 王磊，毛利民，李騫.基于LOD的三維地形可視化[J].計算機與信息技術, 2007，15（7）：39-41.