淺析虛擬現(xiàn)實應(yīng)用中的并行渲染技術(shù)

淺析虛擬現(xiàn)實應(yīng)用中的并行渲染技術(shù)

論文關(guān)健詞：虛擬現(xiàn)實并行渲染負(fù)載平衡歸屬判斷

論文摘要：虛擬現(xiàn)實應(yīng)用要求圖形系統(tǒng)具備實時渲染復(fù)雜、精細(xì)場景的能力?；赑C機(jī)群的并行渲染系統(tǒng)具有性價比高、擴(kuò)展性好的特點，適合虛擬現(xiàn)實應(yīng)用。該文針對虛擬現(xiàn)實應(yīng)用設(shè)汁并實現(xiàn)了一個保留模式的sort—first并行實時渲染系統(tǒng)，對影響渲染性能的關(guān)鍵因素進(jìn)行研究，給出具體實現(xiàn)步驟、試驗驗證數(shù)據(jù)和結(jié)論。應(yīng)用表明，該方法能夠?qū)崿F(xiàn)系統(tǒng)的高效并行計算及虛擬現(xiàn)實應(yīng)用中的復(fù)雜場景實時處理。

1概述

虛擬現(xiàn)實技術(shù)已廣泛應(yīng)用于車輛仿真、建筑預(yù)排、計算機(jī)輔助設(shè)計以及科學(xué)可視化等領(lǐng)域。隨著圖形圖像硬件和軟件的發(fā)展，人們對應(yīng)用的交互性和現(xiàn)實感提出了越來越高的要求：在滿足實時性(每秒30幀)和低延遲的同時，需要構(gòu)造更加逼真、精細(xì)的三維復(fù)雜場景，其數(shù)據(jù)規(guī)模日益膨脹，有時還需要滿足多通道輸出等特殊的應(yīng)用要求。

基于PC機(jī)群的并行渲染技術(shù)以其性價比高、兼容性好、擴(kuò)展靈活等特點，成為虛擬現(xiàn)實實時顯示研究的新方向。隨著PC系統(tǒng)上圖形卡渲染能力的提高和千兆網(wǎng)絡(luò)的出現(xiàn)，建立在高速網(wǎng)絡(luò)連接的PC工作站集群上的并行渲染系統(tǒng)具有良好的性價比和更好的可擴(kuò)展性，得到越來越廣泛的應(yīng)用。

圖形計算任務(wù)的描述非常簡單：給定一個環(huán)境下所有物體的數(shù)學(xué)模型，系統(tǒng)計算每個模型對于給定可視面上每個像素的作用，這就是圖形流水線。Sutherland，Sproull和Schurnacher于1974年提出從數(shù)據(jù)分配(sorting)角度對并行渲染進(jìn)行研究。依據(jù)從對象空間到屏幕空間轉(zhuǎn)換過程中的渲染任務(wù)發(fā)生時間點，文獻(xiàn)【1】將并行渲染方法分為3類：sort—firstsort—middle和sort—last，該理論成為并行圖形渲染和分布圖形渲染研究的里程碑。

sort—first方式在圖形流水線的開始階段就將圖元分配到各渲染節(jié)點；sort—middle在幾何變換與光柵化之間重新分布圖元；sort—last則在流水線的最后重新分布像素。sort—middle和sort—last方式都在一定程度上符合圖形流水線的自然形態(tài)，因此，適合硬件實現(xiàn)，如SGI的RealityEngine和InfiniteReality是sort—middle系統(tǒng)，HP與UNC合作的PixelFlow是典型的sort、last系統(tǒng)J。sort—first方式能充分利用已有的渲染資源，相對其他2種方式通信量較小，因此適合軟件實現(xiàn)，構(gòu)建基于機(jī)群的分布式并行渲染系統(tǒng)。浙江大學(xué)CAD&CG國家重點實驗室開發(fā)的AnyGL是一個sort—first和sort—last混合的支持大規(guī)模分布的并行渲染系統(tǒng)。

2系統(tǒng)結(jié)構(gòu)

本文設(shè)計了一個基于PC機(jī)群的保留模式sortfirst并行渲染系統(tǒng)。該系統(tǒng)的各個節(jié)點均配有高端普通圖形顯示卡，采用千兆以太網(wǎng)交換機(jī)進(jìn)行互連，期望以較低的成本達(dá)到大型專有系統(tǒng)的性能，并且具有更強(qiáng)的靈活性和可擴(kuò)展性。其基本工作模式為“歸屬判斷一渲染一同步顯示”。這種設(shè)計能充分利用幀問相似性，減少網(wǎng)絡(luò)開銷。與另2種方式相比，sortfirst最大的特點是對圖形流水線介入較淺。

圖1為系統(tǒng)硬件結(jié)構(gòu)，系統(tǒng)由一個用戶服務(wù)節(jié)點和一個圖形計算機(jī)子系統(tǒng)組成。后者包含很多處理節(jié)點，這些節(jié)點實時處理圖像。

(1)用戶服務(wù)節(jié)點：負(fù)責(zé)渲染節(jié)點之間的協(xié)調(diào)，接收用戶輸入，傳送命令，執(zhí)行負(fù)載平衡任務(wù)。

(2)渲染節(jié)點：擁有全部場景數(shù)據(jù)。根據(jù)視點的改變和負(fù)載平衡計算結(jié)果自適應(yīng)地判斷面片歸屬，根據(jù)統(tǒng)一位姿指令執(zhí)行渲染任務(wù)，提取圖像像素數(shù)據(jù)并發(fā)送給圖像服務(wù)節(jié)點。

(3)圖像服務(wù)節(jié)點：接收渲染節(jié)點輸入像素數(shù)據(jù)，合成像素數(shù)據(jù)，輸出圖像信息到投影設(shè)備。

系統(tǒng)在原始數(shù)據(jù)輸入后及頂點變換前對計算任務(wù)進(jìn)行分配。其工作模式

Stepl用戶服務(wù)節(jié)點執(zhí)行負(fù)載平衡計算。

Step2根據(jù)負(fù)載平衡結(jié)果，渲染節(jié)點確定圖元歸屬。

Step3渲染節(jié)點執(zhí)行渲染服務(wù)，提取像素數(shù)據(jù)并發(fā)送。

Step4圖像處理節(jié)點接收像素數(shù)據(jù)，執(zhí)行圖像拼合。

Step5輸出到投影設(shè)備并顯示。

負(fù)載平衡是sort—first架構(gòu)面對的最大問題。在實際應(yīng)用中，圖元的屏幕劃分是高度可變的，為了達(dá)到很好的負(fù)載平衡效果，必須深入研究渲染節(jié)點的屏幕分配策略。另外，圖元的跨屏幕分布帶來的重復(fù)渲染也會導(dǎo)致渲染效率的降低。為了便于討論，以一臺應(yīng)用主機(jī)和一個圖形計算子系統(tǒng)為例。后者由幾個渲染節(jié)點及一個圖像處理節(jié)點組成，渲染節(jié)點實時渲染圖像，圖像處理節(jié)點負(fù)責(zé)顯示。顯示模型數(shù)據(jù)庫開始即被分配到所有渲染節(jié)點，因此，為保留模式。

3關(guān)鍵技術(shù)

3．1系統(tǒng)并行性

多邊形渲染是一種“近似易并行”的計算，其特點是適合并行，但需要計算任務(wù)的分布和收集計算結(jié)果，并用某種方式加以組合。對多邊形渲染算法引入并行的方法有2種：功能并行和數(shù)據(jù)并行。

3．1．1數(shù)據(jù)并行

并行渲染應(yīng)用要求在圖形流水線的幾何轉(zhuǎn)換和光柵化階段都進(jìn)行并行化。對于sort—first，一旦確定了圖元歸屬，渲染節(jié)點只要計算它負(fù)責(zé)的那部分屏幕的最終圖像，節(jié)點之間幾乎沒有干涉，現(xiàn)有的多種并行渲染加速算法都能得到應(yīng)用因此，系統(tǒng)具有很好的擴(kuò)展性。

數(shù)據(jù)并行方式將數(shù)據(jù)剖分成多個獨立的數(shù)據(jù)流(datastreams)，在一些相同的處理單元上同時對這些數(shù)據(jù)流進(jìn)行處理。這種方式的并行效果不受渲染流水線級數(shù)的限制，但受制于相同的處理單元的數(shù)目和系統(tǒng)內(nèi)部的通信帶寬。由于多邊形渲染算法數(shù)據(jù)問的相關(guān)性很弱，因此數(shù)據(jù)并行方式有較大的潛力。

3．1．2功能并行

渲染節(jié)點內(nèi)流程主要分為圖形渲染、數(shù)據(jù)通信和同步等待3個功能階段。其中，圖形渲染和數(shù)據(jù)通信耗時較多，也最有可能成為系統(tǒng)的瓶頸；系統(tǒng)同步等待本身花費不大，主要與節(jié)點的渲染和通信直接相關(guān)。為了有效地提高系統(tǒng)效率，在渲染節(jié)點主要實現(xiàn)圖形渲染和數(shù)據(jù)通信的同步。

3．2負(fù)載平衡技術(shù)

對sort—first并行渲染系統(tǒng)而言，渲染任務(wù)分布策略一般基于屏幕的任務(wù)劃分，負(fù)載平衡問題的研究焦點是屏幕的劃分和屏幕分配的算法。根據(jù)屏幕劃分是否固定，這些算法主要分為靜態(tài)的和適應(yīng)性的。對于靜態(tài)算法，圖形應(yīng)用的有效性并沒有得到保證；目前適應(yīng)性負(fù)載平衡算法主要有：Roble算法，median—cut算法，Whitman自頂向下分解算法，MADH算法l。J。這些算法都是基于圖元數(shù)據(jù)分析的，將任務(wù)的負(fù)載用屏幕區(qū)域內(nèi)的幾何圖元分布特性來度量。

上述適應(yīng)性算法的缺點是節(jié)點需要遍歷圖元，遍歷的過程中還需要同步，且算法本身耗時，這需要較大的時間開銷，導(dǎo)致效率降低和延遲增加。此外，采用圖元數(shù)據(jù)作為衡量負(fù)載的標(biāo)準(zhǔn)雖然能夠精確地衡量負(fù)載，但在實際應(yīng)用中，由于渲染節(jié)點計算能力的差異，或者即使計算能力相同而節(jié)點本身狀態(tài)不同，都會導(dǎo)致渲染相同數(shù)量幾何圖元的時間不同，因此這些算法并不能很好地解決負(fù)載平衡問題。

下面結(jié)合基于圖元數(shù)據(jù)分析算法的屏幕劃分精細(xì)網(wǎng)格思想提出一種基于網(wǎng)格劃分的時間衡量負(fù)載算法。該算法以渲染時間直接衡量負(fù)載，利用仿真應(yīng)用的幀問連續(xù)性，結(jié)合節(jié)點歷史渲染時間數(shù)據(jù)，同時兼顧節(jié)點本身處理圖元數(shù)據(jù)能力，建立渲染時間到屏幕區(qū)域負(fù)載權(quán)重的映射，計算屏幕區(qū)域負(fù)載權(quán)重表。以該屏幕區(qū)域負(fù)載權(quán)重表為依據(jù)進(jìn)行任務(wù)分配。

圖2顯示了2種算法的不同工作模式?；趲缀螖?shù)據(jù)分析算法的共同模式可表示成圖2(a)，負(fù)載平衡控制模塊輸入幾何數(shù)據(jù)和當(dāng)前幀的幾何變換矩陣(通常從客戶端獲得)，運算出新的屏幕剖分方式，作為重新分配渲染任務(wù)的依據(jù)?；跁r間分析的算法如圖2(b)所示，不考慮幾何數(shù)據(jù)，實時捕捉渲染節(jié)點渲染一幀的時間，結(jié)合前一幀的剖分方式，快速計算出新的剖分方式，控制下一幀的渲染。

由于避免了龐大的幾何數(shù)據(jù)計算，因此這種算法花費很小，測試結(jié)果證明其非常實用和有效。另外，從圖2可以看出，由于增加了反饋回路控制，因此有利于快速達(dá)到平衡。負(fù)載平衡的根本目的是縮短各渲染節(jié)點渲染時間并使彼此盡可能接近，因此，以渲染時問衡量負(fù)載的平衡算法比基于幾何數(shù)據(jù)分析的負(fù)載平衡算法更加接近問題的本質(zhì)。

負(fù)載平衡模塊運行在系統(tǒng)客戶端的流程

(1)用戶服務(wù)節(jié)點發(fā)送統(tǒng)一位姿信息和屏幕劃分方案到渲染節(jié)點，啟動第k幀渲染。

(2)渲染節(jié)點完成渲染，輸出像素數(shù)據(jù)到圖像服務(wù)節(jié)點。

(3)渲染節(jié)點記錄自身渲染時間，發(fā)送給負(fù)載平衡節(jié)點。

(4)負(fù)載平衡節(jié)點匯總渲染時問，判斷負(fù)載平衡條件，負(fù)載平衡系數(shù)(最重載／最輕載)是否超過限定值(根據(jù)試驗確定)：未超過(表明負(fù)載平衡)，采用屏幕劃分方案；否則看作負(fù)載不平衡，根據(jù)各節(jié)點渲染時間計算屏幕區(qū)域負(fù)載權(quán)值表，并確定屏幕劃分方案。

(5)圖像服務(wù)節(jié)點匯總像素數(shù)據(jù)，拼接輸出。算法要點：

(1)屏幕劃分為大小一致的精細(xì)網(wǎng)格(圖3)，每個網(wǎng)格賦初始權(quán)值1(網(wǎng)格負(fù)載權(quán)重總值等于網(wǎng)格數(shù))，以網(wǎng)格作為屏幕分配的單元。

(2)以渲染時間作為衡量渲染節(jié)點負(fù)載的指標(biāo)，并作為計算區(qū)域負(fù)載權(quán)重表的依據(jù)。

(3)負(fù)載平衡模塊根據(jù)區(qū)域負(fù)載權(quán)重表進(jìn)行負(fù)載平衡計算，確定屏幕劃分方案。屏幕以與mediancut相同的層次方法沿著單元邊界被劃分。單元總計表允許通過二分查找操作決定劃分的位置?；蛘?，該算法可以通過選擇合適的劃分比率來允許使用非2的整數(shù)次冪的處理器數(shù)，而不是每次等份劃分，見圖3。

(4)各渲染節(jié)點根據(jù)屏幕劃分方案執(zhí)行渲染任務(wù)，記錄本幀渲染時間并反饋給負(fù)載平衡模塊作為負(fù)載平衡計算的依據(jù)。這借鑒了反饋控制的思想。

(5)在負(fù)載平衡計算過程中以網(wǎng)格負(fù)載權(quán)重總值對網(wǎng)格負(fù)載權(quán)值進(jìn)行歸一化計算的依據(jù)。

3．3圖元歸屬判斷和模型預(yù)處理

圖形系統(tǒng)把大量圖元組織在圖元集中，采用各種優(yōu)化措施提高圖元處理速度。在并行渲染系統(tǒng)中，流水線是以圖元集為單元根據(jù)屏幕位置進(jìn)行裁減的，如果圖元集包含圖元過多，會帶來重復(fù)渲染的問題。如圖4所示，分配方案已定，每個子屏幕分配給一個渲染節(jié)點。由于該模型只有一個圖元集，雖然屏幕區(qū)域2，4和7并未完全包含模型，因此它們?nèi)匀灰獙φ麄€模型進(jìn)行渲染計算。在實際的并行渲染應(yīng)用中，重復(fù)渲染會導(dǎo)致嚴(yán)重的效率損失。

為了解決這類問題，本文對模型進(jìn)行預(yù)分割，將含有大量面片的圖元集分割為含有較少面片的多個圖元集，以減少圖元集橫跨多個屏幕的概率，從而減少渲染節(jié)點重復(fù)渲染的面片數(shù)量，充分發(fā)揮屏幕裁減功能的效用。模型預(yù)處理流程為：輸入渲染模型文件結(jié)構(gòu)樹和邊界條件——圖元最大面片數(shù)，輸出分割后的模型樹結(jié)構(gòu)，子節(jié)點大小均勻。

工作流程有如下4步：

(1)遍歷自定義的結(jié)構(gòu)樹，對每個葉子節(jié)點進(jìn)行判斷，如果滿足條件(如面片數(shù)大于某一值)，依據(jù)該葉子節(jié)點的包圍盒進(jìn)行空間八叉分割。

(2)如果子空間不為空，則新生成一個葉子節(jié)點，掛在當(dāng)前節(jié)點下，當(dāng)前節(jié)點改為枝干節(jié)點。

(3)對新生成的葉子節(jié)點繼續(xù)進(jìn)行分割，直到條件不再滿足(如面片數(shù)小于某一值)。

(4)保存結(jié)果模型文件。實驗證明，模型預(yù)分割辦法能很好地解決模型圖元集包含過多面片數(shù)帶來的重復(fù)渲染問題。

4試驗結(jié)果與分析

原型系統(tǒng)利用千兆交換機(jī)連接5個PC節(jié)點。PC配置AMDAthlon64X2DualCore4000+2，11GHz，2GB內(nèi)存，NVIDIAGeForce7900GS圖形加速卡，千兆網(wǎng)卡。

4．1通信能力測試

本測試是在2個節(jié)點之間進(jìn)行的，測試了單次發(fā)送數(shù)據(jù)量從100Byte~50。Byte時的傳輸速度。經(jīng)測試，傳輸能力最高約為900Mb／s。考慮應(yīng)用中采用1027x768的分辨率，每幀接收1024x768x3=2359296Byt數(shù)據(jù)，網(wǎng)絡(luò)應(yīng)用大概為83％，傳輸能力約為740Mb／s，單次傳輸約需26ms。

4．2并行性分析

系統(tǒng)模式：1個顯示節(jié)點，2個渲染節(jié)點；模型面片總數(shù)400萬。這里取1000幀數(shù)據(jù)的統(tǒng)計平均值進(jìn)行分析。讀幀緩存時問即渲染時間，發(fā)送的數(shù)據(jù)都是像素數(shù)據(jù)。采用時間測量函數(shù)精確度達(dá)到了微秒級。功能并行后效率提高了35％左右提升較明顯。

從表1和表2可以看出，2種渲染方式花在讀幀緩存上的時間差不多；未并行時，渲染節(jié)點有很多同步等待花費，圖像處理節(jié)點是瓶頸(同步等待時間最少)；并行后渲染節(jié)點2的渲染階段是瓶頸；理想的情況是渲染節(jié)點與圖像處理節(jié)點的同步等待花費最小。

4．3基于渲染時間分析的負(fù)載平衡

可能影響負(fù)載平衡計算的因素主要有網(wǎng)格的劃分、場景運動速度、模型面片數(shù)及負(fù)載平衡條件系數(shù)的選擇。筆者對每一項進(jìn)行了測試：測試幀數(shù)200；取各指標(biāo)平均值進(jìn)行分析，同時給出了數(shù)據(jù)的標(biāo)準(zhǔn)偏差。主要考察指標(biāo)有：最重載、最輕載比，標(biāo)準(zhǔn)偏差，負(fù)載平衡計算頻率以及最重載、最輕載的分布。

模型選擇：100個模型在場景中隨機(jī)分布，每個模型分別取0．5，1，2及3個單位進(jìn)行測試(44800面片／單位)。由試驗數(shù)據(jù)曲線(圖5)可以看出，渲染節(jié)點渲染時間與模型面片數(shù)呈近似線性關(guān)系，負(fù)載平衡效果隨模型的增大變好；網(wǎng)格劃分更精細(xì)對負(fù)載平衡改善不是很大，這與傳統(tǒng)的網(wǎng)格劃分算法相悖，這是因為采用屏幕區(qū)域權(quán)重的方式衡量負(fù)載遠(yuǎn)沒有圖元分析方法精確，只是一種近似(1~lJ使重載子屏幕也存在輕載區(qū)域，而該輕載區(qū)域權(quán)重系數(shù)與重載子屏幕其他部分一樣)。

場景變化越劇烈，負(fù)載越不平衡，這與直觀相符；負(fù)載平衡條件系數(shù)越大，對負(fù)載平衡計算限制越小，負(fù)載平衡計算次數(shù)越少，當(dāng)負(fù)載平衡條件系數(shù)選擇得很小(如13)時，宣魯統(tǒng)頻繁地進(jìn)行負(fù)載平衡計算，效果反而不好。通過圖6的效果圖得出，采用基于網(wǎng)格劃分的時問衡量負(fù)載算法，負(fù)載平衡比達(dá)到1．5，能夠充分滿足并行渲染系統(tǒng)的需要。

由于采用屏幕區(qū)域權(quán)重的方式衡量負(fù)載只是對負(fù)載的一種近似，因此有時負(fù)載平衡計算效果不是很好。另外，視點變化劇烈也會對負(fù)載平衡效率造成很大影響。

4．4模型分割

應(yīng)用本文提出的方法進(jìn)行測試，測試模型面片數(shù)為422928。經(jīng)測試，分割后圖元集增加了7倍；每個圖元集包含的圖元數(shù)為原來的1／8；每個圖元包含的三角形面片約為分割前的1／3。經(jīng)過模型預(yù)處理和分割，通過增加圖元集數(shù)目，有效地減小了單個圖元集的規(guī)模，從而降低了重復(fù)渲染的概率。

5結(jié)束語

并行渲染的目的是充分利用多臺Pc的資源提高系統(tǒng)處理能力。數(shù)據(jù)分布型的sort—first并行渲染系統(tǒng)能有效利用幀問相似性，降低并行開銷，適合分布式交互圖形應(yīng)用。原型系統(tǒng)證明本文提出的方法可以構(gòu)建高性能、低開銷的并行圖形渲染系統(tǒng)。渲染流水線本身固有的數(shù)據(jù)和功能并行性為構(gòu)造高性能并行渲染系統(tǒng)提供了有效的保證。負(fù)載平衡是并行系統(tǒng)的核心技術(shù)，筆者在前人工作的基礎(chǔ)上，提出了一種新的負(fù)載平衡算法并應(yīng)用于原型系統(tǒng)，通過試驗數(shù)據(jù)分析證明其具有良好的效果。

參考文獻(xiàn)

[11MolnarS，CoxM，EllsworthD，eta1．ASortingClassificationofParallel