魏子衿，肖麗

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

2.北京應(yīng)用物理與計(jì)算數(shù)學(xué)研究所，北京100094

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

基于區(qū)域分解的并行動(dòng)態(tài)LOD構(gòu)建算法

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

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

2.北京應(yīng)用物理與計(jì)算數(shù)學(xué)研究所，北京100094

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

CNKI網(wǎng)絡(luò)出版：2017-04-01,http://kns.cnki.net/kcms/detail/11.2127.TP.20170401.0914.054.html

1 引言

在可視化領(lǐng)域，大規(guī)模數(shù)據(jù)的高速乃至實(shí)時(shí)繪制問題一直是學(xué)者們關(guān)注的熱點(diǎn)。近年來，高性能計(jì)算機(jī)性能不斷攀升、使用日益廣泛，導(dǎo)致應(yīng)用領(lǐng)域產(chǎn)生的可視數(shù)據(jù)規(guī)模越來越大。例如在一個(gè)基于數(shù)千上萬核上的數(shù)值模擬問題中，單時(shí)步產(chǎn)生的模擬結(jié)果數(shù)據(jù)量已可達(dá)GB量級(jí)，完整模擬過程產(chǎn)生的結(jié)果數(shù)據(jù)更是可達(dá)TB量級(jí)[1]。如何快速有效地繪制如此規(guī)模的可視數(shù)據(jù)，已成為可視化領(lǐng)域的一項(xiàng)重大挑戰(zhàn)。

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

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

2 相關(guān)工作

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

直接性能優(yōu)化法面向LOD構(gòu)建與調(diào)度過程中的不同階段，或特定的數(shù)據(jù)類型及應(yīng)用場景，設(shè)計(jì)了各種不同的非并行優(yōu)化算法。一些學(xué)者研究了LOD構(gòu)建中關(guān)鍵技術(shù)的優(yōu)化，即網(wǎng)格簡化技術(shù)的優(yōu)化。Nan等設(shè)計(jì)了以頂點(diǎn)聚類為元操作的簡化算法[3]，相比基于幾何元素刪除的簡化算法，有效地提高了算法中元操作的執(zhí)行速率。Boubekeur等則在頂點(diǎn)聚類算法的基礎(chǔ)上引入了基于隨機(jī)采樣的預(yù)處理策略[4]，進(jìn)一步提升了算法的時(shí)間性能。Li等在頂點(diǎn)聚類算法的基礎(chǔ)上引入了八叉樹結(jié)構(gòu)[5]，在提升算法性能的同時(shí)克服了頂點(diǎn)聚類算法保拓?fù)淠芰Σ畹娜秉c(diǎn)。Zhao等[6]在研究點(diǎn)云數(shù)據(jù)快速處理與繪制時(shí)，設(shè)計(jì)了一種基于Retinex理論的點(diǎn)采樣算法，用于加速點(diǎn)云數(shù)據(jù)網(wǎng)格的簡化過程。還有一些學(xué)者研究了面向特定數(shù)據(jù)類型與應(yīng)用場景的優(yōu)化技術(shù)。Zinsmaier等研究了構(gòu)建點(diǎn)線圖的LOD表示的相關(guān)算法[7]，提出了基于點(diǎn)聚類與邊聚類的LOD構(gòu)建算法及相應(yīng)的模型調(diào)度準(zhǔn)則，有效地提高了點(diǎn)線圖LOD構(gòu)建與調(diào)度的速率。Filip等[8]研究了數(shù)字高程模型的連續(xù)LOD構(gòu)建與表示。Biljecki等[9]則研究了LOD技術(shù)在城市三維場景繪制中的應(yīng)用問題。

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

3 算法概述

在靜態(tài)LOD構(gòu)建中，較為常用且發(fā)展較為成熟的技術(shù)是網(wǎng)格簡化技術(shù)，該技術(shù)之所以只用于靜態(tài)LOD構(gòu)建中，是因?yàn)樵摷夹g(shù)為保持模型的拓?fù)浣Y(jié)構(gòu)，需完成大量復(fù)雜的計(jì)算過程，以確定模型在當(dāng)次迭代步中最適合刪除的幾何元素（點(diǎn)、邊、面）。然而這一計(jì)算過程卻是算法時(shí)間開銷的主要組成部分。將網(wǎng)格簡化算法直接用于動(dòng)態(tài)LOD構(gòu)建中，則由于算法本身的時(shí)間開銷過大，導(dǎo)致模型切換所需的時(shí)間過長，從而出現(xiàn)畫面停滯或空白間斷的問題，無法滿足應(yīng)用需求。

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

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

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

4 漸進(jìn)網(wǎng)格方法

如第3章所述，漸進(jìn)網(wǎng)格方法實(shí)質(zhì)上是網(wǎng)格簡化算法應(yīng)用于LOD構(gòu)建中的一種優(yōu)化策略。它包含兩個(gè)主要的過程：（1）基于網(wǎng)格簡化的預(yù)處理；（2）網(wǎng)格重構(gòu)。在預(yù)處理過程中，采用不同的網(wǎng)格簡化方法將導(dǎo)致不同的漸進(jìn)網(wǎng)格表示，本文實(shí)現(xiàn)了基于QEM網(wǎng)格簡化算法的漸進(jìn)網(wǎng)格方法，從而改變了傳統(tǒng)的漸進(jìn)網(wǎng)格法基于能量函數(shù)優(yōu)化法的實(shí)現(xiàn)。本章將依次介紹漸進(jìn)網(wǎng)格法的基本流程、表示及兩個(gè)主要過程。

4.1 基本流程

漸進(jìn)網(wǎng)格法的基本執(zhí)行流程如圖1所示，算法首先通過基于網(wǎng)格簡化的預(yù)處理過程提取出原始模型的漸進(jìn)網(wǎng)格表示，然后在動(dòng)態(tài)LOD調(diào)度過程中利用漸進(jìn)網(wǎng)格表示完成實(shí)時(shí)的網(wǎng)格重建。

圖1 漸進(jìn)網(wǎng)格方法的基本執(zhí)行流程圖

4.2 改進(jìn)的漸進(jìn)網(wǎng)格表示

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

Hoppe在提出漸進(jìn)網(wǎng)格時(shí)使用基于能量函數(shù)的邊折疊算法[22]作為網(wǎng)格簡化算法，因此采用邊折疊算子描述漸進(jìn)網(wǎng)格表示。而漸進(jìn)網(wǎng)格則是基于QEM算法實(shí)現(xiàn)，該算法用于改變模型拓?fù)涞幕静僮魇敲麨辄c(diǎn)對收縮的操作，因此本章采用點(diǎn)對收縮算子來給出漸進(jìn)網(wǎng)格表示的具體描述。

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

圖2 點(diǎn)對收縮的示意圖

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

4.3 預(yù)處理與重構(gòu)過程

漸進(jìn)網(wǎng)格法的預(yù)處理過程即利用某種網(wǎng)格簡化算法對原始模型執(zhí)行一個(gè)極大程度簡化，并記錄每一個(gè)迭代步對網(wǎng)格拓?fù)湫薷乃鑸?zhí)行的操作。記原始模型為M，點(diǎn)對收縮算子為vconi，同時(shí)沿用4.2節(jié)的記號(hào)，則預(yù)處理過程如圖3所示。

圖3 漸進(jìn)網(wǎng)格方法的預(yù)處理過程

重構(gòu)過程則是一個(gè)相反的過程，它相當(dāng)于對基準(zhǔn)網(wǎng)格M0執(zhí)行一系列點(diǎn)分裂操作。且重構(gòu)過程往往根據(jù)需求執(zhí)行有限步操作以獲取所需精度下的簡化模型，記執(zhí)行了k次點(diǎn)分裂操作所得到的簡化模型為Mk，并記點(diǎn)分裂算子為vspliti，同時(shí)沿用上文已給出的記號(hào)，則重構(gòu)過程如圖4所示。

圖4 漸進(jìn)網(wǎng)格方法的重構(gòu)過程

此外，在預(yù)處理過程中，保持人類可識(shí)別出模型的最低精度通常與模型本身的數(shù)據(jù)規(guī)模、形狀等因素有關(guān)，而這些因素的分析是拓?fù)鋵W(xué)中的一項(xiàng)難題。因此用于描述極大程度的因子在實(shí)際應(yīng)用中往往根據(jù)經(jīng)驗(yàn)人為指定。

4.4 簡化率計(jì)算

在動(dòng)態(tài)構(gòu)建LOD模型時(shí)，需根據(jù)當(dāng)前視點(diǎn)信息確定模型重構(gòu)所需達(dá)到的精度。簡化率便是用于間接描述該精度的一個(gè)小數(shù)。簡化率ε用于描述LOD模型較原始模型的簡化程度，其定義為LOD模型中的單元總數(shù)除以原始模型中的單元總數(shù)，ε的計(jì)算結(jié)果是一個(gè)小數(shù)，其取值在閉區(qū)間[0，1]中。

簡化率需根據(jù)當(dāng)前視點(diǎn)的信息完成計(jì)算，本文沿用了文獻(xiàn)[15]中給出的計(jì)算方法，即利用視錐、表面法向與屏幕空間幾何誤差三重評判標(biāo)準(zhǔn)的計(jì)算方法。具體可查閱該文獻(xiàn)，本文不再贅述。

5 自適應(yīng)區(qū)域分解算法

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

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

5.1 基于平面分割的區(qū)域分解

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

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

5.2 模型包圍盒

在介紹自適應(yīng)區(qū)域分解算法之前，首先介紹模型包圍盒（bounding box）的概念，它是自適應(yīng)區(qū)域分解算法計(jì)算分割面的依據(jù)。

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

圖5 飛機(jī)模型的包圍盒示意圖

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

5.3 自適應(yīng)區(qū)域分解算法

本文設(shè)計(jì)的區(qū)域分解算法可根據(jù)模型的包圍盒信息與相關(guān)輸入?yún)?shù)自動(dòng)計(jì)算分割面，并產(chǎn)生所需的分解結(jié)果。在分割面計(jì)算中，將求出三個(gè)分割面集合S1、S2、S3，這三個(gè)集合實(shí)際上分別對應(yīng)了法向量與坐標(biāo)軸Ox,Oy,Oz相平行的所有分割面，因此在同一集合中，全部平面的法向量是相同的，而在不同集合中，平面之間的法向量則是相互垂直的。

記Ox,Oy,Oz方向上的分割參數(shù)分別為m,n,p，沿用5.2節(jié)給出的記號(hào)，描述具體的分割面計(jì)算方法如下：

算法自適應(yīng)分割面計(jì)算算法

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

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

算法描述：

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

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

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

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

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

圖6 航母模型區(qū)域分解結(jié)果示意圖

6 并行動(dòng)態(tài)LOD構(gòu)建算法

前文已經(jīng)分別描述了動(dòng)態(tài)LOD構(gòu)建的核心算法——漸進(jìn)網(wǎng)格法，以及形成有效并行計(jì)算區(qū)域劃分的自適應(yīng)區(qū)域分解算法。本章將給出由上述兩種方法結(jié)合所形成的并行動(dòng)態(tài)LOD構(gòu)建算法的完整描述。

6.1 并行動(dòng)態(tài)LOD構(gòu)建算法

本節(jié)給出完整的并行動(dòng)態(tài)LOD構(gòu)建算法的描述，該算法由兩個(gè)算法組成。其中算法1是預(yù)處理過程的并行化算法，即利用網(wǎng)格簡化算法并行地生成原始模型的漸進(jìn)網(wǎng)格表示，該算法為每個(gè)子模型生成一個(gè)獨(dú)立的漸進(jìn)網(wǎng)格表示；算法2是重構(gòu)過程的并行化算法，即在實(shí)際LOD應(yīng)用場景中，基于原始模型的漸進(jìn)網(wǎng)格表示的并行LOD模型重構(gòu)過程。

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

算法1并行預(yù)處理算法

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

輸出：m×n×p個(gè)子漸進(jìn)網(wǎng)格PMi,i=1,2,…,m×n×p。

算法描述：

（1）根據(jù)并行參數(shù)，求出3個(gè)分割面集合S1、S2、S3。

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

（3）采用6.2節(jié)中描述的負(fù)載分配算法，將m×n×p個(gè)子模型分配至k個(gè)CPU核上，并行生成子模型的漸進(jìn)網(wǎng)格表示PMi。

（4）并行保存每個(gè)PMi。

算法2并行LOD模型重構(gòu)算法

輸入：并行核數(shù)k、視點(diǎn)信息、m×n×p個(gè)漸進(jìn)網(wǎng)格表示PMi。

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

算法描述：

（1）在0號(hào)CPU核上，根據(jù)視點(diǎn)信息，計(jì)算出簡化率ε。

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

6.2 負(fù)載分配

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

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

6.3 算法優(yōu)勢

本文提出的并行動(dòng)態(tài)LOD控制算法實(shí)質(zhì)上是一種數(shù)據(jù)級(jí)并行算法，相比功能級(jí)并行與流水線式并行算法[24]，數(shù)據(jù)級(jí)并行算法在實(shí)際應(yīng)用中具有較強(qiáng)的優(yōu)勢。

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

7 實(shí)驗(yàn)結(jié)果

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

7.1 模型效果

本章將依次展示模型的基準(zhǔn)網(wǎng)格及動(dòng)態(tài)LOD構(gòu)建生成模型的繪制效果，并做相應(yīng)的統(tǒng)計(jì)分析。將看到區(qū)域分解給模型帶來的影響。

7.1.1 基準(zhǔn)網(wǎng)格繪制效果

由前文可知，區(qū)域分解技術(shù)在分割模型時(shí)會(huì)做一系列邊界縫合操作，使得分割獲得的子模型相互之間不存在數(shù)據(jù)依賴關(guān)系的同時(shí)保持了邊界閉合性質(zhì)，從而保證了模型整體的幾何構(gòu)型不發(fā)生變化。然而對原始模型做不同程度的區(qū)域分解，除產(chǎn)生不同的分解結(jié)果之外，還導(dǎo)致了子區(qū)域的邊界發(fā)生變化。這種分割結(jié)果及子區(qū)域邊界的變化，卻直接導(dǎo)致了為子模型生成的基準(zhǔn)網(wǎng)格的變化。

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

圖7 航母模型在不同程度區(qū)域分解下的基準(zhǔn)網(wǎng)格

對比圖7（b）～（i）可以看出，在不同的區(qū)域分解結(jié)果所生成的基準(zhǔn)網(wǎng)格的拓?fù)浣Y(jié)構(gòu)之間存在明顯的差異，且這一差異的分布恰好與區(qū)域分解所形成的子區(qū)域分布相對應(yīng)。事實(shí)上，在子區(qū)域數(shù)d固定時(shí)，選取不同的分割面也會(huì)產(chǎn)生不同的效果。然而實(shí)際應(yīng)用中為盡可能確保分配給每個(gè)區(qū)域的網(wǎng)格單元數(shù)目的接近，往往會(huì)根據(jù)對原始模型的直觀觀察人為選取適合的分割面，即人為指定參數(shù)m、n、p的值，而圖7中展示的結(jié)果便是人為選定較優(yōu)的參數(shù)所形成的結(jié)果。

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

7.1.2 動(dòng)態(tài)LOD模型繪制效果

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

表1 航母模型在不同程度區(qū)域分解下的統(tǒng)計(jì)信息

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

圖8 飛機(jī)模型在d=64時(shí)ε取不同值的效果圖

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

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

圖10 兩種模型網(wǎng)格單元數(shù)的折線統(tǒng)計(jì)圖

7.2 并行性能測試

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

其中ap為并行加速比、Ep為并行效率、p為并行計(jì)算使用的CPU核數(shù)、T1為串行算法執(zhí)行時(shí)間、Tp為使用p個(gè)CPU核的并行算法執(zhí)行時(shí)間。

表2 飛機(jī)模型的動(dòng)態(tài)LOD模型網(wǎng)格單元數(shù)統(tǒng)計(jì)結(jié)果

表3 航母模型的動(dòng)態(tài)LOD模型網(wǎng)格單元數(shù)統(tǒng)計(jì)結(jié)果

分析漸進(jìn)網(wǎng)格方法不難發(fā)現(xiàn)，算法執(zhí)行的最壞情形是ε=1的情形，即直接由基準(zhǔn)網(wǎng)格M0重構(gòu)出原始模型網(wǎng)格M的情形，此時(shí)算法做了最多次點(diǎn)分裂操作，為證明算法具有較高的時(shí)間性能，需完成該情形下的測試。此外選擇ε=0.5、ε=0.25的兩個(gè)情形做了測試。

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

從表4中可以發(fā)現(xiàn)，隨著CPU核數(shù)p的增加，算法的執(zhí)行時(shí)間明顯降低。該規(guī)律表明本文的并行算法是有效的。根據(jù)表4，計(jì)算了算法的加速比及并行效率，并做了相應(yīng)的統(tǒng)計(jì)圖。圖11、12分別給出了算法的加速比及并行效率的折線統(tǒng)計(jì)圖。

表4 算法并行執(zhí)行時(shí)間統(tǒng)計(jì)表s

圖11 ε取不同值時(shí)算法的加速比

圖12 ε取不同值時(shí)算法的效率

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

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

圖13 功能級(jí)并行算法框架圖

7.3 并行算法性能對比

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

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

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

該方法同樣分解了傳統(tǒng)的重構(gòu)過程，并將頂點(diǎn)恢復(fù)與單元恢復(fù)操作進(jìn)一步分解為多個(gè)相同的子過程，從而增加了流水線的節(jié)點(diǎn)數(shù)。同時(shí)該方法需要模型的區(qū)域分解結(jié)果作為支撐，使得p個(gè)節(jié)點(diǎn)能同時(shí)工作。

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

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

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

此外，從圖中可發(fā)現(xiàn)功能級(jí)并行算法的執(zhí)行時(shí)間又比流水線式并行算法的執(zhí)行時(shí)間快一些，即功能級(jí)并行算法中串行模塊的時(shí)間開銷小于流水線式并行算法中的節(jié)點(diǎn)通信開銷。導(dǎo)致這一現(xiàn)象的原因是在動(dòng)態(tài)LOD算法中，頂點(diǎn)恢復(fù)與單元恢復(fù)兩個(gè)子操作占據(jù)了算法的相當(dāng)大部分的時(shí)間開銷，從而使得功能級(jí)并行算法中串行模塊的執(zhí)行時(shí)間占比小于流水線式并行算法中的通信時(shí)間占比。事實(shí)上，在其他一些問題的并行化算法中，流水線式并行算法的時(shí)間開銷也會(huì)高于功能級(jí)并行算法的時(shí)間開銷，這與所面對的問題及算法的設(shè)計(jì)等因素有關(guān)。

表5 三種并行算法執(zhí)行時(shí)間統(tǒng)計(jì)表s

圖15 三種算法執(zhí)行時(shí)間柱狀統(tǒng)計(jì)圖

8 總結(jié)與展望

本文面向大規(guī)?？茖W(xué)數(shù)據(jù)的高速繪制問題，改進(jìn)傳統(tǒng)的基于漸進(jìn)網(wǎng)格的動(dòng)態(tài)LOD構(gòu)建算法，研究并實(shí)現(xiàn)了一種基于區(qū)域分解技術(shù)的并行動(dòng)態(tài)LOD構(gòu)建算法。

本文主要做了如下貢獻(xiàn)：

（1）實(shí)現(xiàn)了一種基于QEM網(wǎng)格簡化法的漸進(jìn)網(wǎng)格方法。

（2）提出了一種自適應(yīng)區(qū)域分解算法。

（3）設(shè)計(jì)并實(shí)現(xiàn)了一種基于區(qū)域分解的并行動(dòng)態(tài)LOD構(gòu)建算法。

實(shí)驗(yàn)結(jié)果表明，本文提出的算法主要具備如下幾點(diǎn)優(yōu)勢：

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

（2）適用于較大的問題規(guī)模，具備良好的可擴(kuò)放性。

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

（4）不受視點(diǎn)變換的影響，適用于動(dòng)態(tài)LOD環(huán)境。

在未來的工作中，還可展開兩點(diǎn)研究：

（1）現(xiàn)階段的重構(gòu)算法所重構(gòu)的模型是視獨(dú)立的模型，即模型全局基于相同的精度。未來可研究視相關(guān)的重構(gòu)算法，即重構(gòu)所得的模型在距離視點(diǎn)越近，精度越高。在實(shí)際應(yīng)用中，單一模型往往生成視獨(dú)立LOD模型較多，而視相關(guān)LOD模型往往面向復(fù)雜場景或地形數(shù)據(jù)而構(gòu)建。

（2）進(jìn)一步挖掘漸進(jìn)網(wǎng)格生成與重構(gòu)算法中的功能并行性，研究數(shù)據(jù)與功能兩級(jí)混合并行算法。

[1] 王弘堃，肖麗，邵京云，等.面向大規(guī)?？茖W(xué)計(jì)算的可視分析模式[J].計(jì)算機(jī)工程與科學(xué)，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] 徐權(quán)，崔濤，劉青凱，等.基于區(qū)域分解技術(shù)的并行四面體網(wǎng)格生成算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2014，35（1）：153-157.

[24] 奎因，陳文光，武永衛(wèi).MPI與OpenMP并行程序設(shè)計(jì)：C語言版——世界著名計(jì)算機(jī)教材精選[M].北京：清華大學(xué)出版社，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

面向大規(guī)?？梢晹?shù)據(jù)的高速繪制問題，提出了一種基于區(qū)域分解的并行動(dòng)態(tài)LOD（level-of-detail，層次細(xì)節(jié)模型）構(gòu)建算法。算法首先改進(jìn)了傳統(tǒng)的漸進(jìn)網(wǎng)格方法，實(shí)現(xiàn)了基于二次誤差測度網(wǎng)格簡化算法的漸進(jìn)網(wǎng)格方法；接著提出了一種基于模型包圍盒的區(qū)域分解算法，實(shí)現(xiàn)了原始模型的自適應(yīng)區(qū)域分解；在每個(gè)子區(qū)域上，并行地執(zhí)行漸進(jìn)網(wǎng)格方法，實(shí)現(xiàn)了模型的并行動(dòng)態(tài)LOD構(gòu)建。實(shí)驗(yàn)結(jié)果表明，該算法可生成高質(zhì)量的LOD模型，具備理想的加速比和可擴(kuò)放性；與串行算法相比，該算法有效地提高了算法的執(zhí)行效率。

可視化；層次細(xì)節(jié)模型（LOD）；漸進(jìn)網(wǎng)格；區(qū)域分解；并行計(jì)算

2016-10-24

2017-01-05

1002-8331（2018）06-0168-10

A

TP391.41

10.3778/j.issn.1002-8331.1610-0260

國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（No.2016YFB0201302）；計(jì)算物理重點(diǎn)實(shí)驗(yàn)室基金（No.9140C690504150C69001）。

魏子衿（1991—），男，碩士研究生，研究方向?yàn)榭茖W(xué)計(jì)算可視化，E-mail：18618316878@163.com；肖麗（1971—），通訊作者，女，研究員，研究方向?yàn)榭茖W(xué)計(jì)算可視化。