基于區域分解的并行動態LOD構建算法

魏子衿，肖麗

1.中國工程物理研究院研究生部，北京100088

2.北京應用物理與計算數學研究所，北京100094

3.中國工程物理研究院高性能數值模擬軟件中心，北京100088

基于區域分解的并行動態LOD構建算法

魏子衿1，2，3，肖麗2，3

1.中國工程物理研究院研究生部，北京100088

2.北京應用物理與計算數學研究所，北京100094

3.中國工程物理研究院高性能數值模擬軟件中心，北京100088

CNKI網絡出版：2017-04-01,http://kns.cnki.net/kcms/detail/11.2127.TP.20170401.0914.054.html

1 引言

在可視化領域，大規模數據的高速乃至實時繪制問題一直是學者們關注的熱點。近年來，高性能計算機性能不斷攀升、使用日益廣泛，導致應用領域產生的可視數據規模越來越大。例如在一個基于數千上萬核上的數值模擬問題中，單時步產生的模擬結果數據量已可達GB量級，完整模擬過程產生的結果數據更是可達TB量級[1]。如何快速有效地繪制如此規模的可視數據，已成為可視化領域的一項重大挑戰。

在眾多繪制加速技術中，層次細節模型（Level-Of-Detail，LOD）技術是其中較為有效的一種，其相關的理論基礎早在科學可視化以串行計算為主的時期便已提出。LOD技術處理的對象是網格模型，其基本思想是在滿足觀察者對分辨率要求的前提下，構建網格模型的簡化模型替代原始模型予以顯示，從而降低圖形硬件處理的可視數據量，提高模型的繪制速率。常見的LOD技術分為靜態與動態兩種[2]。靜態LOD技術預先生成模型的多級層次細節表示，僅在繪制階段調用所需顯示的模型，該策略往往在繪制階段效率較高，但多級模型的存儲導致了較高的存儲開銷。動態LOD技術則在繪制中根據視點需求實時生成簡化模型，避免了多級模型存儲導致的高存儲空間占用，但實時的模型生成帶來了較大的時間開銷，導致動態LOD技術在實際場景中的繪制效率較低，甚至難以滿足應用需求。

可視化技術發展至今，已逐步邁入并行可視化的時代，這為提高動態LOD技術的時間性能提供了機遇，即，將動態LOD構建算法并行化，從而大幅提高實時模型生成的速率，使之可滿足實際應用場景下的交互幀率繪制需求。為此，本文提出并實現了一種基于區域分解技術的并行動態LOD構建算法，本文將系統地介紹該算法的設計與實現原理，并在最后對算法的應用效果及性能做分析與評測。實驗結果表明，相比串行動態LOD構建算法，該算法在保證LOD模型及其圖像的質量的前提下，大幅度地提高了動態LOD構建的時間性能，且具備較為理想的并行加速比及可擴放性，能滿足動態LOD構建環境下的應用需求。

2 相關工作

近年來誕生了許多有關LOD技術性能優化的研究成果，大致可分為兩類，一類是非并行的直接性能優化方法，另一類則是將串行過程并行化的并行優化方法。

直接性能優化法面向LOD構建與調度過程中的不同階段，或特定的數據類型及應用場景，設計了各種不同的非并行優化算法。一些學者研究了LOD構建中關鍵技術的優化，即網格簡化技術的優化。Nan等設計了以頂點聚類為元操作的簡化算法[3]，相比基于幾何元素刪除的簡化算法，有效地提高了算法中元操作的執行速率。Boubekeur等則在頂點聚類算法的基礎上引入了基于隨機采樣的預處理策略[4]，進一步提升了算法的時間性能。Li等在頂點聚類算法的基礎上引入了八叉樹結構[5]，在提升算法性能的同時克服了頂點聚類算法保拓撲能力差的缺點。Zhao等[6]在研究點云數據快速處理與繪制時，設計了一種基于Retinex理論的點采樣算法，用于加速點云數據網格的簡化過程。還有一些學者研究了面向特定數據類型與應用場景的優化技術。Zinsmaier等研究了構建點線圖的LOD表示的相關算法[7]，提出了基于點聚類與邊聚類的LOD構建算法及相應的模型調度準則，有效地提高了點線圖LOD構建與調度的速率。Filip等[8]研究了數字高程模型的連續LOD構建與表示。Biljecki等[9]則研究了LOD技術在城市三維場景繪制中的應用問題。

并行優化法同樣面向LOD構建與調度中的不同階段，以及特定的數據類型及應用場景，挖掘算法中可并行化的點并轉化為有效的并行程序。與非并行化優化研究的關注點相類似，面向LOD構建中網格簡化技術的并行化研究是其中一個重要的研究方向。Lu等研究了基于分布式集群的并行網格簡化技術，提出了面向分布式集群的核外并行網格簡化框架[10-11]，并成功應用到了多個實際模型中。Lee等面向GPU級并行優化，提出了一種基于嵌入式樹的并行網格簡化算法[12]，有效提高了多核GPU的利用率。Ozaki等改進了基于QEM的點對合并式網格簡化法，實現了一種核外并行簡化算法[13]，Odaker等則改進了基于半邊折疊的網格簡化法，成功實現了算法在GPU上的并行化[14]，上述這些算法均成功實現了網格簡化速率的大幅提升。此外還有一些面向LOD構建全階段的研究，Hu[15]和Derzapf[16]均研究了視相關漸進網格方法在LOD模型預處理、構建、調度全部三個主要階段的相關并行技術，Peng等[17]則研究了核外動態LOD模型三個階段中的并行技術。除以上兩方面，還存在一些面向特定數據類型與應用的研究。Rizzi等研究了面向粒子模擬數據的并行LOD可視化技術[18]，Goswami等則研究了面向地形數據的并行LOD可視化技術[19]。

3 算法概述

在靜態LOD構建中，較為常用且發展較為成熟的技術是網格簡化技術，該技術之所以只用于靜態LOD構建中，是因為該技術為保持模型的拓撲結構，需完成大量復雜的計算過程，以確定模型在當次迭代步中最適合刪除的幾何元素（點、邊、面）。然而這一計算過程卻是算法時間開銷的主要組成部分。將網格簡化算法直接用于動態LOD構建中，則由于算法本身的時間開銷過大，導致模型切換所需的時間過長，從而出現畫面停滯或空白間斷的問題，無法滿足應用需求。

1996年，Hoppe在網格簡化技術的基礎上提出了漸進網格（Progressive Mesh，PM）方法，克服了傳統網格簡化方法的困難，將動態LOD技術推入了實用化。該方法包含兩個主要過程：（1）基于網格簡化的預處理：對原始模型執行一次極大程度的網格簡化，并記錄簡化算法每一次迭代中的有效信息，以及最終得到的最簡化網格。（2）網格重建：根據記錄的操作信息，在最簡化網格基礎上重構所需精度的網格。所謂極大程度的網格簡化，是指將網格簡化至能保持人類可識別出該模型的最低精度，即得到了最終的最簡化網格。而有效信息則是指網格簡化算法經過大量計算而最終得到的對模型幾何元素做出修改的信息，如某次迭代中要刪除或修改的點、線、面等。

在動態LOD技術中，漸進網格法采用網格重建的手段實時生成LOD模型，避免了直接使用網格簡化算法所需完成的大量計算，有效地降低了算法的時間開銷。在串行計算環境下，漸進網格法使得一些較小規模（包含105以下量級三角面單元）的網格模型的在交互幀率下的動態LOD模型構建成為可能。然而在面對大規模網格模型（包含105及以上量級三角面單元）時，卻仍無法滿足交互幀率繪制需求。

為改善漸進網格法在面向大規模數據時的時間性能，本文基于漸進網格動態LOD構建算法，結合三維模型區域分解技術，提出了一種有效的并行動態LOD構建算法。算法主要包含以下三個步驟：（1）原始模型的區域分解；（2）基于網格簡化的并行預處理；（3）并行網格重建。算法主要具備如下優勢：（1）可取得理想的次線性加速比，具備一定的實用性；（2）適用于較大的問題規模，具備良好的可擴放性；（3）不受視點變換的影響，適用于動態LOD環境。關于這三點優勢的分析將在第6章中給出。此外，本文并沒有采用傳統的基于能量評估函數的漸進網格方法，而是實現了基于二次誤差測度（Quadric Error Metric，QEM）網格簡化算法[20]的漸進網格方法。

4 漸進網格方法

如第3章所述，漸進網格方法實質上是網格簡化算法應用于LOD構建中的一種優化策略。它包含兩個主要的過程：（1）基于網格簡化的預處理；（2）網格重構。在預處理過程中，采用不同的網格簡化方法將導致不同的漸進網格表示，本文實現了基于QEM網格簡化算法的漸進網格方法，從而改變了傳統的漸進網格法基于能量函數優化法的實現。本章將依次介紹漸進網格法的基本流程、表示及兩個主要過程。

4.1 基本流程

漸進網格法的基本執行流程如圖1所示，算法首先通過基于網格簡化的預處理過程提取出原始模型的漸進網格表示，然后在動態LOD調度過程中利用漸進網格表示完成實時的網格重建。

圖1 漸進網格方法的基本執行流程圖

4.2 改進的漸進網格表示

漸進網格PM表示為由一個極大程度簡化的基準網格M0和一個用于重建網格的記錄R={r1,r2,…,rn}所構成的整體，其中每條記錄ri由具體采用的網格簡化算法來決定。例如采用的簡化算法是點刪除與三角化結合的方法[21]，則ri={vri,T}，T={t1,t2,…,tm}，其中vri表示第i次迭代操作刪除的點，即在網格重建中需恢復的點。集合T則表示本次迭代中對產生的多邊形洞孔三角化產生的三角面單元集合，即在網格重建中需刪除的三角形面單元構成的集合。

Hoppe在提出漸進網格時使用基于能量函數的邊折疊算法[22]作為網格簡化算法，因此采用邊折疊算子描述漸進網格表示。而漸進網格則是基于QEM算法實現，該算法用于改變模型拓撲的基本操作是名為點對收縮的操作，因此本章采用點對收縮算子來給出漸進網格表示的具體描述。

首先給出點對收縮操作的定義。如圖2所示，點對收縮即一對頂點收縮為一個頂點的過程，可簡潔地表示為公式(v1,v2)→vˉ，該公式包含了以下步驟：（1）將頂點v1與v2合并為一個新的頂點vˉ，并為vˉ選擇合適的位置；（2）將所有原本以v1、v2為頂點的三角面的相應頂點指向vˉ；（3）刪除全部退化的三角面。在QEM算法中，點對收縮可人為允許距離限定范圍下的無邊點對收縮，此時將獲得較高的時間性能，而模型的拓撲改變會較為嚴重。

圖2 點對收縮的示意圖

每條記錄ri用于記錄點對收縮操作中的有效信息，可形式化表示為ri={v1,v2,vˉ,T1,T2}，Ti={ti1,ti2,…,tin}，i=1,2。其中v1、v2為收縮前的點，vˉ為收縮后的點，T1為需更改頂點指向的三角面集合，T2為退化三角面的集合。

4.3 預處理與重構過程

漸進網格法的預處理過程即利用某種網格簡化算法對原始模型執行一個極大程度簡化，并記錄每一個迭代步對網格拓撲修改所需執行的操作。記原始模型為M，點對收縮算子為vconi，同時沿用4.2節的記號，則預處理過程如圖3所示。

圖3 漸進網格方法的預處理過程

重構過程則是一個相反的過程，它相當于對基準網格M0執行一系列點分裂操作。且重構過程往往根據需求執行有限步操作以獲取所需精度下的簡化模型，記執行了k次點分裂操作所得到的簡化模型為Mk，并記點分裂算子為vspliti，同時沿用上文已給出的記號，則重構過程如圖4所示。

圖4 漸進網格方法的重構過程

此外，在預處理過程中，保持人類可識別出模型的最低精度通常與模型本身的數據規模、形狀等因素有關，而這些因素的分析是拓撲學中的一項難題。因此用于描述極大程度的因子在實際應用中往往根據經驗人為指定。

4.4 簡化率計算

在動態構建LOD模型時，需根據當前視點信息確定模型重構所需達到的精度。簡化率便是用于間接描述該精度的一個小數。簡化率ε用于描述LOD模型較原始模型的簡化程度，其定義為LOD模型中的單元總數除以原始模型中的單元總數，ε的計算結果是一個小數，其取值在閉區間[0，1]中。

簡化率需根據當前視點的信息完成計算，本文沿用了文獻[15]中給出的計算方法，即利用視錐、表面法向與屏幕空間幾何誤差三重評判標準的計算方法。具體可查閱該文獻，本文不再贅述。

5 自適應區域分解算法

在計算機輔助設計與圖形學領域，區域分解是指將二維或三維模型采用一種或多種分割技術切分為多個相互獨立且邊界閉合的子模型的過程[23]。其中較為常用的一種分割技術是基于幾何曲面的切割技術，幾何曲面可為隱式或顯式的各種自定義曲面，較為實用的曲面則是簡單的球面或平面。

本文的工作是利用區域分解技術將原始模型分割為多個互不依賴的子區域，使得算法可在這些子區域上并行執行。為切合并行算法，本文采用了基于平面切割的區域分解方法。本章將簡要介紹區域分解的概念，并介紹一種基于模型包圍盒的自適應區域分解算法。

5.1 基于平面分割的區域分解

基于平面分割的區域分解技術是利用一系列切割平面，將原始模型分割為多塊子區域的技術[20]。該技術主要包括兩個過程：（1）分割面計算；（2）平面剪裁。

過程（1）采用手動或自動的算法選取一系列由方程Ax+By+Cz+D=0確定的平面。過程（2）則依次利用每個分割面對當前模型執行平面剪裁操作。需要注意的是，平面剪裁操作除完成單元與分割面求交、單元分割、邊界縫合等基本操作外，還需完成正確識別并劃分切割所得各個子區域的過程。這一過程也是保證并行算法得以正確執行的關鍵。

5.2 模型包圍盒

在介紹自適應區域分解算法之前，首先介紹模型包圍盒（bounding box）的概念，它是自適應區域分解算法計算分割面的依據。

包圍盒是一個能包羅整個模型的最小長方體。在三維歐式空間中，取模型中Ox,Oy,Oz方向上最大的三個值xmax、ymax、zmax，及最小的三個值xmin、ymin、zmin，根據這些值建立兩個點vmax=(xmax,ymax,zmax)、vmin=(xmin,ymin,zmin)。由這兩個點所構造的長方體即包圍該模型的最小長方體，也即模型的包圍盒。圖5給出了一個飛機模型的包圍盒（bounding box）示意圖，圖中包羅整個飛機模型的長方體即包圍盒。

圖5 飛機模型的包圍盒示意圖

在本文的區域分解算法中，利用包圍盒可精確確定模型所處的有效范圍，從而能夠快速確定所需分割面的法向量。

5.3 自適應區域分解算法

本文設計的區域分解算法可根據模型的包圍盒信息與相關輸入參數自動計算分割面，并產生所需的分解結果。在分割面計算中，將求出三個分割面集合S1、S2、S3，這三個集合實際上分別對應了法向量與坐標軸Ox,Oy,Oz相平行的所有分割面，因此在同一集合中，全部平面的法向量是相同的，而在不同集合中，平面之間的法向量則是相互垂直的。

記Ox,Oy,Oz方向上的分割參數分別為m,n,p，沿用5.2節給出的記號，描述具體的分割面計算方法如下：

算法自適應分割面計算算法

輸入：分割參數m,n,p、原始模型。

輸出：分割面集合S1、S2、S3。

算法描述：

（1）求出原始模型的包圍盒最大最小點vmax、vmin。

（2）作向量vminvmax，求出其分別在Ox,Oy,Oz上的分量，記為nx、ny、nz。

（3）求解集合S1。先求出線段xminxmax的m-1個m等分點v11、v12、…、v1(m-1)，分別用這m-1個點與法向量nx結合，求得m-1個分割面s11、s12、…、s1(m-1)，加入集合S1中。

（4）用同樣的方法，求出線段yminymax的n-1個n等分點、線段zminzmax的p-1個p等分點，并分別結合法向量ny、nz，求得n-1個分割面加入集合S2，及p-1個分割面加入集合S3。

求得了所需的分割面，算法將逐一利用每個分割面對原始模型做平面剪裁。根據不同分割面集合中的平面相互正交的性質不難看出，原始模型被剖分為m×n×p個子區域。圖6給出了一個對航母模型做簡單區域分解的結果示意圖，在該圖中m、n、p取值均為2。

圖6 航母模型區域分解結果示意圖

6 并行動態LOD構建算法

前文已經分別描述了動態LOD構建的核心算法——漸進網格法，以及形成有效并行計算區域劃分的自適應區域分解算法。本章將給出由上述兩種方法結合所形成的并行動態LOD構建算法的完整描述。

6.1 并行動態LOD構建算法

本節給出完整的并行動態LOD構建算法的描述，該算法由兩個算法組成。其中算法1是預處理過程的并行化算法，即利用網格簡化算法并行地生成原始模型的漸進網格表示，該算法為每個子模型生成一個獨立的漸進網格表示；算法2是重構過程的并行化算法，即在實際LOD應用場景中，基于原始模型的漸進網格表示的并行LOD模型重構過程。

下面給出算法1及算法2的具體描述，其中沿用了第4章、第5章所給出的記號。

算法1并行預處理算法

輸入：并行參數m,n,p、并行核數k、原始模型M。

輸出：m×n×p個子漸進網格PMi,i=1,2,…,m×n×p。

算法描述：

（1）根據并行參數，求出3個分割面集合S1、S2、S3。

（2）根據集合S1、S2、S3，將M劃分成m×n×p個子模型Mi。

（3）采用6.2節中描述的負載分配算法，將m×n×p個子模型分配至k個CPU核上，并行生成子模型的漸進網格表示PMi。

（4）并行保存每個PMi。

算法2并行LOD模型重構算法

輸入：并行核數k、視點信息、m×n×p個漸進網格表示PMi。

輸出：原始模型的LOD模型。

算法描述：

（1）在0號CPU核上，根據視點信息，計算出簡化率ε。

（2）在k個CPU核上，采用6.2節中描述的負載分配算法，根據簡化率ε，并行為每個PMi生成LOD模型。

6.2 負載分配

在并行程序中，子數據塊個數與CPU核數往往是不相等的。因此并行算法需解決將m塊數據分配給n個CPU核的問題。

本文采用了一種均勻負載分配的策略，該策略描述如下：（1）當m=n時，為每個CPU分配一個基準網格；（2）當m＜n時，為前m個CPU各分配一個基準網格，后n-m個CPU不分配基準網格；（3）當m＞n時，設i=m/n,p=m mod n，首先為每個CPU分配i個基準網格，余下的p個基準網格分配給前p個CPU。在實際應用中很少出現m＜n的情形。此時一種更為有效的做法是將數據繼續劃分為n塊。

6.3 算法優勢

本文提出的并行動態LOD控制算法實質上是一種數據級并行算法，相比功能級并行與流水線式并行算法[24]，數據級并行算法在實際應用中具有較強的優勢。

面對特定的應用領域，只要能找出一種有效劃分原始數據的算法，并充分顧及子數據塊之間的相互影響，便能設計出有效的并行程序，這導致了數據級并行算法是較為容易設計與實現的。此外，并行程序旨在應用于數據規模較大的情形，而對于實際應用中的許多數據，在數據規模較大時，往往能劃分為較高數目的子數據塊，從而使得數據級并行算法能利用較高數目的CPU核實現并行計算。相比之下，功能級并行算法往往只能將串行算法流程中有限的程序塊并行化，如果該程序塊本身只占據算法執行時間的一小部分，亦或該程序塊只能取得較小的并行度，則直接導致了該并行算法的性能低下。而流水線式并行更是取決于算法步驟的劃分及步驟之間的依賴關系，在所有并行算法中設計難度最高。此外，上述兩種并行算法因設計難度高，往往不具備高穩定性，導致難以適用于CPU核數較多的情形。

7 實驗結果

本章將從LOD模型的繪制效果和算法的并行性能分析兩個角度對算法作出評價。實驗中使用的環境為浪潮TS10K集群，該機包含16個計算節點，每個節點包含2顆E5-2600系列處理器，每個處理器包含12顆Intel Xeon E5-2692v2（2.20 GHz）/8.0GT/30ML3/1866 CPU核，節點內存為8 GB。

7.1 模型效果

本章將依次展示模型的基準網格及動態LOD構建生成模型的繪制效果，并做相應的統計分析。將看到區域分解給模型帶來的影響。

7.1.1 基準網格繪制效果

由前文可知，區域分解技術在分割模型時會做一系列邊界縫合操作，使得分割獲得的子模型相互之間不存在數據依賴關系的同時保持了邊界閉合性質，從而保證了模型整體的幾何構型不發生變化。然而對原始模型做不同程度的區域分解，除產生不同的分解結果之外，還導致了子區域的邊界發生變化。這種分割結果及子區域邊界的變化，卻直接導致了為子模型生成的基準網格的變化。

圖7給出了將一個包含96 537個三角面單元的航母模型，做不同程度的區域分解所產生的基準網格的繪制效果圖。其中圖7（a）是未簡化的原始網格模型，圖7（b）是對未做區域分解的模型直接生成基準網格的結果，圖7（c）～（i）則是在人為指定區域分解參數m、n、p的情況下，將原始模型做不同程度區域分解并生成基準網格的結果。生成所有基準網格預設的簡化率均為0.002。

圖7 航母模型在不同程度區域分解下的基準網格

對比圖7（b）～（i）可以看出，在不同的區域分解結果所生成的基準網格的拓撲結構之間存在明顯的差異，且這一差異的分布恰好與區域分解所形成的子區域分布相對應。事實上，在子區域數d固定時，選取不同的分割面也會產生不同的效果。然而實際應用中為盡可能確保分配給每個區域的網格單元數目的接近，往往會根據對原始模型的直觀觀察人為選取適合的分割面，即人為指定參數m、n、p的值，而圖7中展示的結果便是人為選定較優的參數所形成的結果。

表1中給出了對這些參數取值的一個統計。從m、n、p值的統計中可以看出，隨著子區域數的增長，m、n、p參數的取值具備一定的變化規律，即首先增加n的值，然后增加m的取值，而p的取值則始終為1。如前文所述，選取這些參數值是根據對該模型的直觀觀察，選取確保能產生較均衡負載分配的分割平面。根據人的直觀觀察往往是快速而有效的，例如可以很容易發現，在子區域數d=2時，沿航母模型的對稱線一分為二是最合理的分割方法。隨著所需分割區域數的增長，總是會人為確定參數m、n、p的取值，這是一種較為便捷的方式，同時也避免了隨意選取參數導致較差的計算結果帶來的計算資源的浪費。此外，從三角單元數一欄可發現，隨著子區域數d的增加，基準網格模型的單元數出現小幅度的增加。這是因為所做的分割操作越多，縫合邊界所形成的新單元就越多。隨著簡化率逐漸減小，這一差距會逐漸加大，但這一影響在LOD模型重構過程中是幾乎可忽略的，將在7.1.2小節給出相應的分析。

7.1.2 動態LOD模型繪制效果

分別對飛機模型和航母模型做了動態LOD模型構建生成實驗，對每個模型，將模型分別分解為1、2、4、8、16、32、64、128個子區域，并為每種劃分分別生成4組具有較高展示度的結果模型。這里所說的高展示度，是指能讓用戶通過對比明顯地看出模型之間具有不同的精度的一組結果，因此這里ε的取值只是為了形成具有一定對比度的繪制結果。此外，原始的飛機模型包含252 725個三角面單元，原始的航母模型包含96 537個三角面單元。

表1 航母模型在不同程度區域分解下的統計信息

因篇幅限制，圖8、9僅給出了兩種模型分解為64個子區域時的繪制效果圖。其中圖（a）展示原始模型，圖（b）～（e）展示不同簡化率下的LOD模型，圖（f）展示模型在圖（e）中LOD模型的面填充繪制結果。在圖8（b）～（e）及圖9（b）～（e）這8幅子圖中存在區域分解對網格模型產生的剖分線，較為容易識別的是圖8（e）中飛機兩翼上的剖分線，而航母模型的剖分線則難以同模型本身簡化產生的網格線相區分。對比圖（b）～（e）可以看出，隨著簡化率ε的增長，LOD模型的網格越來越簡潔，但模型的基本結構依然保持較好，這是因為預處理過程中采用網格簡化算法最大限度地保持了模型的拓撲結構。當兩種模型簡化到圖（e）所對應的簡化率時，模型的填充圖依然可以提供較好的繪制效果。

圖8 飛機模型在d=64時ε取不同值的效果圖

圖9 航母模型在d=64時ε取不同值的效果圖

表2、表3則給出了分別對兩個模型所做的8組完整實驗的統計，統計的是在子區域數d取不同值時，生成的LOD模型所包含的三角單元數。橫向觀察表格的每一行，可發現模型的單元數具有隨d的增加而增長的規律，但增長幅度非常小。圖10中直觀地展示了三角單元數隨d增加的變化趨勢，隨著d的增大，單元數始終呈增長的趨勢，但增長幅度極小，幾乎可忽略不計。導致這一現象的原因是模型都是表面型網格模型，因而區域分解中邊界縫合操作增加了模型的單元數目，但并沒有增加太多的單元，與7.1.1小節中分析的結論一致。

圖10 兩種模型網格單元數的折線統計圖

7.2 并行性能測試

本節將測試算法的時間性能，包括并行加速比a和并行效率E。并行加速比和效率的定義如下：

其中ap為并行加速比、Ep為并行效率、p為并行計算使用的CPU核數、T1為串行算法執行時間、Tp為使用p個CPU核的并行算法執行時間。

表2 飛機模型的動態LOD模型網格單元數統計結果

表3 航母模型的動態LOD模型網格單元數統計結果

分析漸進網格方法不難發現，算法執行的最壞情形是ε=1的情形，即直接由基準網格M0重構出原始模型網格M的情形，此時算法做了最多次點分裂操作，為證明算法具有較高的時間性能，需完成該情形下的測試。此外選擇ε=0.5、ε=0.25的兩個情形做了測試。

實驗中選取了分別包含三角單元數為252 725、1 263 625、6 318 125的三個真實航母模型做測試算例，分別基于8個指數級增長的CPU數在上述3個簡化率下執行了算法，其區域分解參數設置與表1中設置的相同。算法的執行時間統計在表4中。其中，n代表模型包含的三角單元數，p代表并行算法使用的CPU核數，ε仍表示簡化率。

從表4中可以發現，隨著CPU核數p的增加，算法的執行時間明顯降低。該規律表明本文的并行算法是有效的。根據表4，計算了算法的加速比及并行效率，并做了相應的統計圖。圖11、12分別給出了算法的加速比及并行效率的折線統計圖。

表4 算法并行執行時間統計表s

圖11 ε取不同值時算法的加速比

圖12 ε取不同值時算法的效率

單獨觀察圖11中的每幅子圖可以看出，在簡化率ε取不同值的情況下，隨著CPU核數p的增加，算法的加速比也得到了適當增大，但加速比增長趨勢逐漸變緩。然而規模n較大的算例的加速比總是大于規模較小的算例，說明算法適用于問題規模較大的情形。對比圖11中的三幅子圖則發現，隨著簡化率ε的增加，加速比并無發生明顯的變化，也即視點變換不會對算法性能造成影響，說明算法適用于任意精度的兩個LOD模型之間的轉換。實際上ε取不同的值僅僅影響算法執行的元操作的個數，因此ε不應影響算法的性能。

單獨觀察圖12中的每幅子圖可以看出，在每種簡化率取值下，隨著CPU核數p的增加，算法的并行效率逐漸降低，這與算法加速比隨著p的增加而增長逐漸變緩相符合。同時對于規模n較大的算法，并行效率近似總是大于規模較小的算例，同樣說明了算法適用于問題規模較大的情形。對比圖12中的三幅子圖則發現，簡化率ε的增加對并行效率并無明顯的影響，與加速比中的相關分析也相吻合。

圖13 功能級并行算法框架圖

7.3 并行算法性能對比

本節將給出本文算法與功能級并行算法及流水線式并行算法性能的分析對比。首先給出功能級并行算法與流水線式并行算法的概述。顧名思義，兩種算法均是通過改進算法的執行流程來達到并行效果。功能級并行算法框架大致如圖13所示。

該方法改變了傳統重構過程的思路，將元操作中的兩個主要子操作（頂點恢復、單元恢復）分離出來，在相應串行模塊中消除操作之間的依賴，從而可將這兩個子操作分別并行化執行。兩個并行模塊所能達到的最高并行度由傳統算法中的元操作數目決定。流水線式并行算法架構大致如圖14所示。

圖14 流水線式并行算法框架圖

該方法同樣分解了傳統的重構過程，并將頂點恢復與單元恢復操作進一步分解為多個相同的子過程，從而增加了流水線的節點數。同時該方法需要模型的區域分解結果作為支撐，使得p個節點能同時工作。

先給出理論上的對比分析。在輸入數據及使用CPU核數目相同的前提下，本文提出的數據級并行算法可對p個CPU核上的數據實現算法全階段的并行化處理，相比之下，功能級并行算法只是對算法的部分階段實現了并行處理，其余階段繼續保持串行執行。而流水線式并行算法雖是全階段并行化算法，但卻因節點間的通信而引入了許多通信開銷。因此可認為本文提出的數據級并行算法結合了另兩種算法的優點，具備最好的時間性能。下面將通過一組實驗進行驗證。

實驗中依然選取了分別包含三角單元數為252 725、1 263 625、6 318 125的三個真實航母模型做測試算例，分別基于8個指數級增長的CPU核數在簡化率為0.5的條件下執行了三種不同的并行算法，且區域分解參數設置仍與表1相同。三種算法的執行時間統計如表5所示。

直接觀察表5可以看出，在相同規模n與CPU核數p下，幾乎總是本文算法的執行時間最快，而流水線式并行算法的執行時間最慢。在圖15中，對三種算法在不同問題規模下的執行時間做出了柱狀統計圖。從圖中可以看到，在不同問題規模及CPU核數下，本文算法的執行時間總是優于另外兩種算法，和上述理論分析的結果相一致。

此外，從圖中可發現功能級并行算法的執行時間又比流水線式并行算法的執行時間快一些，即功能級并行算法中串行模塊的時間開銷小于流水線式并行算法中的節點通信開銷。導致這一現象的原因是在動態LOD算法中，頂點恢復與單元恢復兩個子操作占據了算法的相當大部分的時間開銷，從而使得功能級并行算法中串行模塊的執行時間占比小于流水線式并行算法中的通信時間占比。事實上，在其他一些問題的并行化算法中，流水線式并行算法的時間開銷也會高于功能級并行算法的時間開銷，這與所面對的問題及算法的設計等因素有關。

表5 三種并行算法執行時間統計表s

圖15 三種算法執行時間柱狀統計圖

8 總結與展望

本文面向大規模科學數據的高速繪制問題，改進傳統的基于漸進網格的動態LOD構建算法，研究并實現了一種基于區域分解技術的并行動態LOD構建算法。

本文主要做了如下貢獻：

（1）實現了一種基于QEM網格簡化法的漸進網格方法。

（2）提出了一種自適應區域分解算法。

（3）設計并實現了一種基于區域分解的并行動態LOD構建算法。

實驗結果表明，本文提出的算法主要具備如下幾點優勢：

（1）可取得理想的次線性加速比，具備一定的實用性。

（2）適用于較大的問題規模，具備良好的可擴放性。

（3）相比功能級并行算法和流水線式并行算法，本文算法具備更好的時間性能。

（4）不受視點變換的影響，適用于動態LOD環境。

在未來的工作中，還可展開兩點研究：

（1）現階段的重構算法所重構的模型是視獨立的模型，即模型全局基于相同的精度。未來可研究視相關的重構算法，即重構所得的模型在距離視點越近，精度越高。在實際應用中，單一模型往往生成視獨立LOD模型較多，而視相關LOD模型往往面向復雜場景或地形數據而構建。

（2）進一步挖掘漸進網格生成與重構算法中的功能并行性，研究數據與功能兩級混合并行算法。

[1] 王弘堃，肖麗，邵京云，等.面向大規模科學計算的可視分析模式[J].計算機工程與科學，2012，34（8）：142-146.

[2] Luebke D，Reddy M，Cohen J D，et al.Level of detail for 3D graphics[M].[S.l.]：Elsevier Science Inc，2002.

[3] Nan L，Gao P，Lu Y，et al.A new adaptive mesh simplification method using vertex clustering with topologyand-detail preserving[C]//International Symposium on Information Science and Engineering，2008：150-153.

[4] Boubekeur T，Alexa M.Mesh simplification by stochastic sampling and topological clustering[J].Computers&Graphics，2009，33（3）：241-249.

[5] Li J，Chen Y.A fast mesh simplification algorithm based on octree with quadratic approximation[C]//International Conference for Young Computer Scientists（ICYCS 2008），2008：775-780.

[6] Zhao Y，Liu Y，Song R，et al.A retinex theory based points sampling method for mesh simplification[J].IEEE Signal Processing Society，2011：230-235.

[7] Zinsmaier M，Brandes U，Deussen O，et al.Interactive levelof-detail rendering of large graphs[J].IEEE Transactions on Visualization&Computer Graphics，2012，18（12）：2486-2495.

[8] Strugar F.Continuous distance-dependent level of detail for rendering heightmaps[J].Journal of Graphics GPU&Game Tools，2011，14（14）：57-74.

[9] Biljecki F，Ledoux H，Stoter J，et al.Formalisation of the level of detail in 3D city modelling[J].Computers Environment&Urban Systems，2014，48（16）：1-15.

[10] Lu Y，Gao P，Chu Q，et al.Parallel implementation of mesh simplification on a beowulf cluster[C]//International Symposium on Distributed Computing and Applications to Business，Engineering and Science，2010：160-164.

[11] Lu Y，Li N，Gao P，et al.A parallel memory efficient framework for out-of-core mesh simplification[C]//IEEE International Conference on High Performance Computing and Communications（HPCC 2009），Seoul，Korea，2009：666-671.

[12] Lee H，Kyung M H.Parallel mesh simplification using embedded tree collapsing[J].Visual Computer，2016：1-10.

[13] Ozaki H，Kyota F，Kanai T.Out-of-core framework for QEM-based mesh simplification[C]//Eurographics Symposium on Parallel Graphics and Visualization，Eurographics Association，2015.

[14] Odaker T.GPU-accelerated real-time mesh simplification using parallel half edge collapses[M]//Mathematical and Engineering Methods in Computer Science.[S.l.]：Springer International Publishing，2015.

[15] Hu L，Sander P V，Hoppe H.Parallel view-dependent level-of-detail control[J].IEEE Transactions on Visualization&Computer Graphics，2010，16（5）：718-728.

[16] Derzapf E，Menzel N，Guthe M，et al.Parallel viewdependent out-of-core progressive meshes[C]//Vision，Modeling，and Visualization Workshop 2010，Siegen，Germany，2010：25-32.

[17] Peng C，Mi P，Cao Y.Load balanced parallel GPU outof-core for continuous LOD model visualization[C]//Proceedings of the 2012 SC Companion：High Performance Computing，Networking Storage and Analysis，2012：215-223.

[18] Rizzi S，Hereld M，Insley J，et al.Large-scale parallel visualization of particle-based simulations using point sprites and level-of-detail[C]//Eurographics Symposium on Parallel Graphics&Visualization，2015：1-10.

[19] Goswami P，Makhinya M，B?sch J，et al.Scalable parallel out-of-core terrain rendering[C]//Proceedings of the EurographicsConferenceonParallelGraphicsand Visualization，2010：63-71.

[20] Garland M.Surface simplification using quadric error metrics[J].ACM Siggraph Computer Graphics，2015，1997：209-216.

[21] Schroeder W J.Decimation of triangle meshes[J].ACM Siggraph Computer Graphics，1992，26（2）：65-70.

[22] Hoppe H.Mesh optimization[J].ACM Siggraph Computer Graphics，1993，27：19-26.

[23] 徐權，崔濤，劉青凱，等.基于區域分解技術的并行四面體網格生成算法[J].計算機工程與設計，2014，35（1）：153-157.

[24] 奎因，陳文光，武永衛.MPI與OpenMP并行程序設計：C語言版——世界著名計算機教材精選[M].北京：清華大學出版社，2004.

WEI Zijin,XIAO Li.Parallel dynamic level-of-detail construct algorithm based on domain decomposition.Computer Engineering andApplications,2018,54（6）：168-177.

WEI Zijin1，2，3,XIAO Li2，3

1.Graduate School of ChinaAcademy of Engineering Physics,Beijing 100088,China
2.Institute ofApplied Physics and Computational Mathematics,Beijing 100094,China
3.CAEP Software Center for High Performance Numerical Simulation,Beijing 100088,China

To solve the problem of fast rendering large-scale visual data,a parallel dynamic level-of-detail construct algorithm based on domain decomposition is presented.The main contributions of this article are presented as follows.Firstly,the traditional progressive mesh algorithm is improved by using quadric error metric method,to provide faster implementation.Then,a self-adaptive domain decomposition algorithm based on model’s bounding box is put forward for cutting the original model into several blocks for parallel computing.Finally,a parallel dynamic level-of-detail construct algorithm by executing progressive mesh algorithm on the blocks in parallel is presented.As a result,this algorithm can generate high-qualified level-of-detail models,and has ideal speed-up ratio and expansibility.Compared to serial algorithms,this algorithm greatly reduces the execution time.

visualization;Level-Of-Detail（LOD）;progressive mesh;domain decomposition;parallel computing

面向大規模可視數據的高速繪制問題，提出了一種基于區域分解的并行動態LOD（level-of-detail，層次細節模型）構建算法。算法首先改進了傳統的漸進網格方法，實現了基于二次誤差測度網格簡化算法的漸進網格方法；接著提出了一種基于模型包圍盒的區域分解算法，實現了原始模型的自適應區域分解；在每個子區域上，并行地執行漸進網格方法，實現了模型的并行動態LOD構建。實驗結果表明，該算法可生成高質量的LOD模型，具備理想的加速比和可擴放性；與串行算法相比，該算法有效地提高了算法的執行效率。

可視化；層次細節模型（LOD）；漸進網格；區域分解；并行計算

2016-10-24

2017-01-05

1002-8331（2018）06-0168-10

A

TP391.41

10.3778/j.issn.1002-8331.1610-0260

國家重點研發計劃項目（No.2016YFB0201302）；計算物理重點實驗室基金（No.9140C690504150C69001）。

魏子衿（1991—），男，碩士研究生，研究方向為科學計算可視化，E-mail：18618316878@163.com；肖麗（1971—），通訊作者，女，研究員，研究方向為科學計算可視化。