基于手勢的交互式三維場景并行光線跟蹤繪制研究

蔣聰，陳純毅

（長春理工大學(xué)　計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春　130022）

?

基于手勢的交互式三維場景并行光線跟蹤繪制研究

蔣聰，陳純毅

（長春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春130022）

摘要：利用光線跟蹤可以繪制出高質(zhì)量的真實(shí)感場景畫面，但計(jì)算量很大，難以實(shí)現(xiàn)實(shí)時(shí)交互式繪制。為此，三維真實(shí)感場景的實(shí)時(shí)交互式繪制往往需要用到集群，但集群的繪制速度是由繪制速度最慢的節(jié)點(diǎn)決定的，如果節(jié)點(diǎn)之間的任務(wù)沒有被劃分均勻，集群的繪制效率就會(huì)下降。為了滿足實(shí)時(shí)交互式繪制的要求、提高集群的繪制效率，設(shè)計(jì)了在粗粒度和細(xì)粒度兩個(gè)層次上同時(shí)實(shí)現(xiàn)并行計(jì)算的集群繪制系統(tǒng)，并針對(duì)集群的負(fù)載均衡問題提出了基于像素遞歸深度的負(fù)載均衡方法。該方法首先統(tǒng)計(jì)出每個(gè)像素的遞歸深度從而得到整個(gè)場景的遞歸深度圖，然后對(duì)上一幀按遞歸深度進(jìn)行均衡劃分。根據(jù)連續(xù)兩幀所對(duì)應(yīng)的場景具有的時(shí)空相關(guān)性，上一幀的劃分結(jié)果可作為下一幀劃分的依據(jù)。本算法的優(yōu)勢在于能夠快速實(shí)現(xiàn)三維動(dòng)態(tài)場景下的集群負(fù)載均衡。實(shí)驗(yàn)表明，該集群繪制系統(tǒng)可以高效地實(shí)現(xiàn)基于Kinect的實(shí)時(shí)交互式繪制。

關(guān)鍵詞：集群；光線跟蹤；負(fù)載均衡；遞歸深度；實(shí)時(shí)交互

近年來，實(shí)時(shí)交互式真實(shí)感圖形繪制是計(jì)算機(jī)圖形學(xué)研究的熱點(diǎn)。為了使繪制結(jié)果更加真實(shí)，往往采用光線跟蹤進(jìn)行繪制。如果繪制的場景包含較多的鏡面材質(zhì)對(duì)象，則系統(tǒng)需要對(duì)大量的二次光線和陰影探測光線進(jìn)行處理，這會(huì)使繪制效率大大降低，而無法滿足實(shí)時(shí)交互的要求。針對(duì)此問題，大致有兩種解決方案：第一，優(yōu)化現(xiàn)有的算法，設(shè)計(jì)高效的場景加速結(jié)構(gòu)［1，2］；第二，采用并行光線跟蹤進(jìn)行繪制，如集群繪制。

集群繪制是實(shí)現(xiàn)實(shí)時(shí)交互式繪制的一種有效途徑，但集群繪制的速度是由繪制速度最慢的節(jié)點(diǎn)決定的，如果節(jié)點(diǎn)之間的任務(wù)分配不均勻，集群繪制的效率就會(huì)下降，甚至失去并行加速的作用。目前的負(fù)載均衡算法雖然實(shí)現(xiàn)了較好的負(fù)載均衡效果，但都很難滿足實(shí)時(shí)交互式繪制的要求。

已有的負(fù)載均衡策略包括基于PBT樹的自適應(yīng)劃分方法［3，4］和基于像素開銷［5］的方法?；赑BT樹的自適應(yīng)劃分方法利用場景繪制時(shí)前后幀所對(duì)應(yīng)場景的時(shí)空相關(guān)性，以上一幀的繪制時(shí)間開銷為參考，通過合并任務(wù)較輕的節(jié)點(diǎn)、分割任務(wù)較重的節(jié)點(diǎn)的方式對(duì)下一幀進(jìn)行預(yù)估劃分。但此方法無法使系統(tǒng)快速達(dá)到負(fù)載平衡狀態(tài)，以至于不能滿足三維動(dòng)態(tài)場景的實(shí)時(shí)交互式繪制要求?；谙袼亻_銷算法的基本思想是系統(tǒng)首先根據(jù)像素開銷圖把場景劃分成一定數(shù)量的塊，然后平均分配給各個(gè)節(jié)點(diǎn)，各節(jié)點(diǎn)再用一個(gè)棧存儲(chǔ)分到的任務(wù)塊。在繪制過程中率先完成繪制任務(wù)的節(jié)點(diǎn)通過任務(wù)竊取機(jī)制［6］從其它未完成繪制任務(wù)的節(jié)點(diǎn)分擔(dān)一些繪制任務(wù)。該方法計(jì)算復(fù)雜、網(wǎng)絡(luò)通信負(fù)擔(dān)重，而且節(jié)點(diǎn)內(nèi)部不是并行的。

本文設(shè)計(jì)了在粗粒度和細(xì)粒度兩個(gè)層次上同時(shí)實(shí)現(xiàn)并行計(jì)算的集群繪制系統(tǒng)以實(shí)現(xiàn)基于Kinect的自然人機(jī)交互繪制。同時(shí)針對(duì)集群的負(fù)載均衡問題提出了按像素遞歸深度對(duì)場景進(jìn)行劃分的負(fù)載均衡方法。

1　集群系統(tǒng)設(shè)計(jì)

1.1并行光線跟蹤繪制

并行光線跟蹤的并行設(shè)計(jì)方式分為粗粒度并行和細(xì)粒度并行，如圖1所示［7］。粗粒度并行是節(jié)點(diǎn)間的并行，其光線跟蹤設(shè)計(jì)兩種不同的設(shè)計(jì)方案：基于物體空間的并行和基于屏幕空間的并行［8］?；谖矬w空間的并行設(shè)計(jì)是把場景中的物體分配給各繪制節(jié)點(diǎn)?；谄聊豢臻g的并行是把場景按屏幕尺寸劃分成若干像素塊，然后分配給各繪制子節(jié)點(diǎn)。細(xì)粒度并行是節(jié)點(diǎn)內(nèi)的并行，本文利用NVIDIA 的OptiX引擎實(shí)現(xiàn)繪制節(jié)點(diǎn)內(nèi)部的并行。集群節(jié)點(diǎn)之間的并行設(shè)計(jì)采用的是基于屏幕空間的并行方案。

并行光線跟蹤的執(zhí)行流程由場景劃分與合并、網(wǎng)絡(luò)通信、幀同步、數(shù)據(jù)壓縮和負(fù)載平衡等環(huán)節(jié)組成，其中負(fù)載均衡是難點(diǎn)也是關(guān)鍵點(diǎn)。

圖1　粗粒度并行與細(xì)粒度并行

1.2系統(tǒng)運(yùn)行流程

本文的集群繪制系統(tǒng)設(shè)計(jì)基于客戶/服務(wù)器架構(gòu)，系統(tǒng)工作流程如圖2所示。服務(wù)器首先讀取配置文件，得到各個(gè)繪制節(jié)點(diǎn)的繪制參數(shù)，包括這些節(jié)點(diǎn)的IP地址、監(jiān)聽端口、場景的初始劃分參數(shù)等；然后啟動(dòng)處于監(jiān)聽狀態(tài)的繪制節(jié)點(diǎn)，將相應(yīng)的繪制參數(shù)發(fā)送給各個(gè)節(jié)點(diǎn)?？蛻舳艘恢碧幱诒O(jiān)聽狀態(tài)，當(dāng)接收到服務(wù)器發(fā)來的繪制任務(wù)后，調(diào)用OptiX引擎執(zhí)行繪制。繪制完成后，子節(jié)點(diǎn)對(duì)數(shù)據(jù)進(jìn)行壓縮并發(fā)送往服務(wù)器。服務(wù)器收到客戶端發(fā)來的結(jié)果之后再反饋回去一個(gè)信號(hào)，客戶端收到反饋信號(hào)之后再繪制下一幀，以此實(shí)現(xiàn)同步繪制。在繪制過程中，服務(wù)器可以隨時(shí)檢測人機(jī)交互指令并將指令發(fā)往客戶端。

圖2　系統(tǒng)工作流程圖

1.3場景劃分與合并

本文中，場景被劃分成的塊數(shù)與繪制節(jié)點(diǎn)數(shù)目一致，這樣不僅可以降低網(wǎng)絡(luò)通信開銷，而且便于邏輯控制。系統(tǒng)產(chǎn)生的初始光線與屏幕上的像素一一對(duì)應(yīng)，都有確定的坐標(biāo)索引（屏幕像素坐標(biāo)）。服務(wù)器把坐標(biāo)索引作為任務(wù)參數(shù)發(fā)給繪制子節(jié)點(diǎn)，子節(jié)點(diǎn)只繪制指定的像素塊，然后把結(jié)果數(shù)據(jù)發(fā)往服務(wù)器，如圖3所示。

圖3　場景劃分，四臺(tái)繪制worker示例

2　負(fù)載均衡

在集群繪制系統(tǒng)中，由于任務(wù)分配不均勻，不同節(jié)點(diǎn)完成繪制任務(wù)的時(shí)間開銷不同，這樣完成時(shí)間早的節(jié)點(diǎn)就會(huì)閑置等待繪制完成時(shí)間晚的節(jié)點(diǎn)，從而造成系統(tǒng)資源浪費(fèi)，繪制效率低下。這就是集群普遍存在的負(fù)載不均衡問題［7］。

在負(fù)載均衡過程中，一個(gè)重要的環(huán)節(jié)就是統(tǒng)計(jì)場景各個(gè)部分的繪制時(shí)間，以量化子節(jié)點(diǎn)的繪制任務(wù)。在利用光線跟蹤進(jìn)行繪制時(shí)，光線與物體的遍歷求交計(jì)算占據(jù)了絕大部分的繪制時(shí)間，所以場景中繪制任務(wù)較重的一定是產(chǎn)生二次光線較多的部分［6］。因此可用像素的遞歸深度值作為對(duì)場景進(jìn)行劃分的標(biāo)準(zhǔn)。由于動(dòng)態(tài)場景的變化是一種連續(xù)的變化，因此，連續(xù)兩幀對(duì)應(yīng)的場景具有時(shí)間和空間上的相關(guān)性：連續(xù)兩幀的同一個(gè)像素所繪制的場景點(diǎn)的空間位置和繪制該像素所花費(fèi)的時(shí)間具有一致性?；诶L制同一像素時(shí)的時(shí)空相關(guān)性，系統(tǒng)首先記錄每個(gè)像素產(chǎn)生的二次光線數(shù)量，從而得到整個(gè)場景的遞歸深度圖，然后利用連續(xù)兩幀所對(duì)應(yīng)場景的時(shí)空相關(guān)性，對(duì)場景按遞歸深度進(jìn)行劃分，并把劃分結(jié)果作為下一幀劃分的依據(jù)。

對(duì)場景的劃分是沿軸進(jìn)行交替劃分的，系統(tǒng)每次都按遞歸深度把當(dāng)前塊劃分成大致相等的兩塊。劃分過程如圖4所示，先把當(dāng)前塊按行或列降維，即把每行或每列所有遞歸深度值的和存儲(chǔ)為一維數(shù)組的一個(gè)元素。這樣就把劃分整塊圖像的問題轉(zhuǎn)化為均衡劃分一維數(shù)組的問題?？梢约僭O(shè)有一個(gè)天平，分別從數(shù)組的兩端取數(shù)，放到天平對(duì)應(yīng)的兩個(gè)托盤中。在取放過程中，根據(jù)天平的平衡狀態(tài)，實(shí)時(shí)調(diào)節(jié)取數(shù)的位置，以維持天平的平衡。最終天平會(huì)在某一次取放操作達(dá)到最佳平衡狀態(tài)。此時(shí)根據(jù)指針在一維數(shù)組中的位置，把當(dāng)前塊劃分為均衡的兩塊。

圖4　基于天平平衡的負(fù)載均衡思想示意圖

算法描述如下：

（1）遞歸深度統(tǒng)計(jì)算法

設(shè)變量depth代表像素的遞歸深度，初始值為0，系統(tǒng)每檢測到一次鏡面反射，depth就累加1。由于要在交點(diǎn)處還需要向光源發(fā)射一條陰影探測光線，再加上初始光線和初始陰影探測光線，系統(tǒng)實(shí)際產(chǎn)生的光線總數(shù)為2depth+2。

（2）場景自適應(yīng)劃分算法

服務(wù)器根據(jù)繪制子節(jié)點(diǎn)發(fā)來的遞歸深度數(shù)據(jù)得到整個(gè)場景的遞歸深度圖，然后基于遞歸深度值把場景均衡地劃分成份。算法過程如算法1所示。

算法1基于遞歸深度自適應(yīng)劃分算法

算法以遞歸深度圖C，迭代次數(shù)n，兩個(gè)雙端隊(duì)列Q和P作為輸入?yún)?shù)，用Q存儲(chǔ)即將被劃分的數(shù)據(jù)塊，用P存儲(chǔ)新劃分好的數(shù)據(jù)塊。在每次迭代中，系統(tǒng)會(huì)選取軸或軸把當(dāng)前數(shù)據(jù)塊劃分成接近相等的兩塊，系統(tǒng)最終會(huì)把場景沿著、軸劃分成塊。CreateTile（）用于創(chuàng)建初始場景塊；Enqueue（）負(fù)責(zé)把新生成的場景塊入隊(duì)；Dequeue（）使即將待劃分的場景塊出隊(duì)；SplitX（T）把當(dāng)前場景塊T沿著X軸劃分成均衡的兩塊；SplitY（T）把當(dāng)前場景塊T沿Y軸劃分成均衡的兩塊。

圖5　場景1組織結(jié)構(gòu)圖

1.設(shè)置標(biāo)定量Axis←0；

2.初始場景塊Enqueue（P，CreatTile（））；

3.開始迭代for i←0 to n do

4.交換Q=P；

5.清空P，Clear（P）；

6.While Q非空do

7.出隊(duì)待劃分場景塊T=Dequeue（Q）；

8.if Axis=0 then

9.沿X軸劃分（T1，T2）←SplitX（T）；

10.else

11.沿Y軸劃分（T1，T2）←SplitY（T）；

12.Q空end

13.入隊(duì)新數(shù)據(jù)塊Enqueue（P，T1）；

14.入隊(duì)新數(shù)據(jù)塊Enqueue（P，T2）；

15.end

16.Axis=1-Axis；

17.迭代結(jié)束end

3　基于Kinect的自然人機(jī)交互設(shè)計(jì)與實(shí)現(xiàn)

3.1場景繪制

場景繪制是用OptiX引擎實(shí)現(xiàn)的，該引擎是基于CUDA［9］的面向?qū)ο蟮目删幊獭⒉⑿袖秩究蚣?。OptiX程序由兩部分組成：（1）基于主機(jī)的API，用于定義基于光線跟蹤的數(shù)據(jù)結(jié)構(gòu)；（2）一個(gè)基于CUDA C的程序系統(tǒng)，用于產(chǎn)生光線、光線與物體求交計(jì)算、創(chuàng)建包圍盒和著色等。OptiX程序的主要組成對(duì)象是Context、Program、Variable、Buffer、Textur Sampler、Geometry、Material、GeometryInstance、Group、GeometryGroup和Acceleration等。

OptiX各對(duì)象模型之間有著嚴(yán)格的從屬關(guān)系。三維場景的創(chuàng)建就是把這些對(duì)象模型按照設(shè)計(jì)者的需求組織成一棵場景樹。本文用OptiX引擎繪制的場景1的場景結(jié)構(gòu)圖，如圖5所示。

3.2交互實(shí)現(xiàn)過程

（1）人體骨骼點(diǎn)數(shù)據(jù)采集

本文主要利用Kinect的人體骨骼追蹤系統(tǒng)進(jìn)行交互設(shè)計(jì)。Kinect通過內(nèi)置攝像機(jī)以每秒30幀的速率對(duì)人體25個(gè)部位的骨骼點(diǎn)進(jìn)行實(shí)時(shí)捕捉。捕捉到的數(shù)據(jù)以數(shù)據(jù)幀（frame）的形式存儲(chǔ)起來，以供相關(guān)庫函數(shù)調(diào)用。

骨骼數(shù)據(jù)是以骨骼空間坐標(biāo)系下的三維坐標(biāo)的形式存在的。骨骼空間坐標(biāo)系是以傳感器為坐標(biāo)原點(diǎn)的右手坐標(biāo)系，骨骼數(shù)據(jù)就是該坐標(biāo)系下的值，如圖6所示。

圖6　骨骼空間坐標(biāo)系

（2）手勢識(shí)別

本文用Kinect提取出了人體六個(gè)部位的骨骼點(diǎn)，分別為：右手腕Hright、左手腕Hleft、右肘Eright、左肘Eleft、右肩Sright、左肩Sleft?；谝陨瞎趋傈c(diǎn)定義四個(gè)向量：Vright、Rright、Vleft、Rleft。

右臂招手的過程如圖7所示。定義角度α為向量Vright和Rright的夾角；角度β為向量-Rright與y軸負(fù)方向的夾角。為了模擬手臂的自然抬升過程，本文針對(duì)夾角α、β和關(guān)鍵骨骼點(diǎn)間的位置關(guān)系設(shè)置了幾個(gè)參考量：當(dāng)且僅當(dāng)夾角β依次大于5°、15°、30°，且夾角α小于45°，右手腕關(guān)節(jié)點(diǎn)y坐標(biāo)大于右肩關(guān)節(jié)點(diǎn)y坐標(biāo)時(shí)視為有效招手過程。

圖7　右臂招手過程

左手臂揮手動(dòng)作如圖8所示。定義角度γ為Vleft與Rleft的夾角。為模擬自然揮手的過程，檢測角度依次小于120°、90°、60°，并隨后依次大于80°、100°、120°。設(shè)左肩、左肘和左手腕組成的三角形ABC，向量是從肘關(guān)節(jié)點(diǎn)A為起點(diǎn)，垂直于BC的向量。有效的左臂揮手動(dòng)作，除了滿足針對(duì)γ設(shè)置的一些臨界值，還要滿足左肘關(guān)節(jié)點(diǎn)的y坐標(biāo)大于左肩的y坐標(biāo)，且向量V的y坐標(biāo)為負(fù)值。手勢識(shí)別的正確率如表1所示。

圖8　左臂揮手過程

表1　手勢識(shí)別正確率統(tǒng)計(jì)

4　交互事件設(shè)計(jì)

4.1運(yùn)動(dòng)狀態(tài)設(shè)計(jì)

在場景2中一共設(shè)計(jì)了3種運(yùn)動(dòng)狀態(tài)：（1）螺旋上升；（2）飛向場景中心；（3）繞某一特定軸旋轉(zhuǎn)。仙子模型首先進(jìn)入運(yùn)動(dòng)狀態(tài)1，運(yùn)動(dòng)狀態(tài)1結(jié)束之后，仙子模型調(diào)整姿態(tài)進(jìn)入運(yùn)動(dòng)狀態(tài)2，待運(yùn)動(dòng)狀態(tài)2結(jié)束之后，仙子調(diào)整姿態(tài)進(jìn)入運(yùn)動(dòng)狀態(tài)3，運(yùn)動(dòng)狀態(tài)3結(jié)束之后，進(jìn)入運(yùn)動(dòng)狀態(tài)1，如此循環(huán)往復(fù)。在任意時(shí)刻，仙子模型都可以對(duì)交互請(qǐng)求作出響應(yīng)。仙子模型的運(yùn)動(dòng)軌跡如圖9所示。

圖9　仙子模型運(yùn)動(dòng)軌跡

模型是由三角形或四邊形面片組成的，這些平片圖形又是由三維空間中的點(diǎn)組成的。空間中的任意一點(diǎn)P，可以用它的齊次坐標(biāo)來表示，即P（x，y，z，1），x，y，z分別表示點(diǎn)在三維空間中的實(shí)際坐標(biāo)。通過對(duì)點(diǎn)P施加一個(gè)變換矩陣，就能把點(diǎn)P變換到指定的位置。因此，模型的運(yùn)動(dòng)狀態(tài)可以通過矩陣變換進(jìn)行控制。任何復(fù)雜的運(yùn)動(dòng)都可以由初等變換（平移變換、縮放變換、旋轉(zhuǎn)變換）矩陣復(fù)合而成［7］。齊次變換矩陣如式5所示，它表示繞Y軸旋轉(zhuǎn)θ角并平移（x0，y0，z0）。

仙子模型的運(yùn)動(dòng)狀態(tài)如算法2所示。

算法2仙子模型運(yùn)動(dòng)狀態(tài)控制

首先從狀態(tài)1開始；運(yùn)動(dòng)狀態(tài)1結(jié)束后，進(jìn)入運(yùn)動(dòng)狀態(tài)2，置停運(yùn)動(dòng)狀態(tài)1的所有運(yùn)動(dòng)參數(shù)；依次類推進(jìn)入運(yùn)動(dòng)狀態(tài)3，；運(yùn)動(dòng)狀態(tài)3結(jié)束后，所有運(yùn)動(dòng)參數(shù)置0，并回到初始的運(yùn)動(dòng)狀態(tài)，如此循環(huán)下去。

1.場景幀刷新While UpdateScene

2.開始運(yùn)動(dòng)狀態(tài)1MoveState1（）；

3.狀態(tài)1結(jié)束if（state1_end）

4.置停運(yùn)動(dòng)狀態(tài)1Stop_MoveState1（）；

5.狀態(tài)調(diào)整State_adjustment1（）；

6.開始運(yùn)動(dòng)狀態(tài)2MoveState2（）；

7.運(yùn)動(dòng)狀態(tài)2結(jié)束if（state2_end）

8.置停運(yùn)動(dòng)狀態(tài)2Stope_MoveState2（）；

9.運(yùn)動(dòng)狀態(tài)調(diào)整State_adjustment2（）；

10.開始運(yùn)動(dòng)狀態(tài)3MoveState3（）；

11.運(yùn)動(dòng)狀態(tài)3結(jié)束if（state3_end）

12.state1_end=flase；

13.state2_end=flase；

14.state3_end=flase；

15.end

16.end

17. end

18.end

4.2交互響應(yīng)

本文只針對(duì)場景2進(jìn)行了交互設(shè)計(jì)，在場景2中，分別設(shè)計(jì)了兩個(gè)交互動(dòng)作：右臂招手和左臂揮手。招手時(shí)，仙子模型即刻調(diào)整姿態(tài)向視點(diǎn)飛來；揮手時(shí)，仙子模型調(diào)整姿態(tài)并返回到原來的運(yùn)動(dòng)軌跡上去。仙子模型在任意狀態(tài)下均可響應(yīng)交互請(qǐng)求，交互嵌入流程圖如圖10所示，運(yùn)動(dòng)狀態(tài)1、運(yùn)動(dòng)狀態(tài)2和運(yùn)動(dòng)狀態(tài)3如運(yùn)動(dòng)狀態(tài)設(shè)計(jì)模塊所述。如果系統(tǒng)沒有檢測到交互指令，模型按預(yù)定的運(yùn)動(dòng)方案依次循環(huán)執(zhí)行三個(gè)運(yùn)動(dòng)狀態(tài)；若期間檢測到交互指令，則首先記錄當(dāng)前模型位置，然后觸發(fā)相應(yīng)的交互事件。

圖10　交互嵌入流程圖

在交互處理模塊，仙子模型也需要實(shí)時(shí)檢測用戶的交互請(qǐng)求，并做出相應(yīng)的處理。該模塊對(duì)用戶交互請(qǐng)求響應(yīng)相對(duì)簡單，只需要模型做一次轉(zhuǎn)身調(diào)整，飛向觀察者或返回原來的運(yùn)動(dòng)狀態(tài)。交互處理模塊的流程設(shè)計(jì)如圖11所示。在交互處理模塊，仙子模型只有飛向視點(diǎn)和返回原來位置兩種運(yùn)動(dòng)狀態(tài)。

當(dāng)檢測到招手指令時(shí)，仙子模型繼續(xù)保持飛向視點(diǎn)的運(yùn)動(dòng)姿態(tài)；當(dāng)檢測到揮手時(shí)，立刻停止原來的運(yùn)動(dòng)狀態(tài)（指飛向視點(diǎn)的運(yùn)動(dòng)姿態(tài)），然后進(jìn)行直立轉(zhuǎn)身狀態(tài)調(diào)整并飛回初始位置。

圖11　交互處理模塊設(shè)計(jì)圖

算法3描述了交互嵌入流程和交互處理模塊的具體實(shí)現(xiàn)。

算法3交互嵌入流程和交互處理算法

算法實(shí)時(shí)監(jiān)測是否有交互請(qǐng)求：beckon（招手）和wave_away（揮手）。如果有交互請(qǐng)求，算法就把相應(yīng)的標(biāo)記變量賦值，這些變量去觸發(fā)相應(yīng)的交互處理模塊。在招手處理模塊中，仙子模型首先調(diào)用State_adjust（）進(jìn)行直立矯正，然后轉(zhuǎn)身調(diào)整，接著飛向試點(diǎn)。在揮手模塊中，也是首先進(jìn)行直立矯正，然后轉(zhuǎn)身背向試點(diǎn)，返回原來離開時(shí)的位置。整個(gè)交互過程需要調(diào)用preprocessing（）對(duì)原來的運(yùn)動(dòng)狀態(tài)做預(yù)處理。

1.更新場景While（UpdateScene）

2.如果招手if（beckon），設(shè)置標(biāo)記變量fiary_ come←true，fiary_return←false，state_adjust_bool ←true，state_adjust_bool←true，bool_arrive=true；

3.招手變量標(biāo)記完成end；

4.如果揮手if（wave_away），fiary_return←true，fiary_come←false，state_adjust_bool2←true，bool_ arrive=false；

5.揮手變量標(biāo)記完成end；

6.if（fiary_come）index++；

7.交互相應(yīng)預(yù)處理proprecessing（）；

8.if（state_adjust_bool and index＞=2）

9.如果模型傾斜，則直立矯正

10.狀態(tài)調(diào)整State_adjust（）；

11.state_adjust_bool←false；

12.記錄離開時(shí)的位置；

13.if（index＞3 and bool_arive），身體前傾并飛向觀察者，end；

14.如果到達(dá)指定位置，bool_arrive←false，直立矯正；

15.如果招手if（fiary_return）index2++；

16.交互預(yù)處理preprocessing（）；

17.返回原來的位置；

18.if（state_adjust_bool2），直立矯正，end；

19.if（state_adjust2 and index2＞=2），轉(zhuǎn)身調(diào)整，State_adjust_bool2←false，end；

20.if已返回，清除所有交互參數(shù)CleanAll（），end；end；end；

5　實(shí)驗(yàn)分析

本文使用的微機(jī)基本配置：Intel（R）Xeon（R）E3-1255 v3 CPU，4GB主存，NV Quadro K600 GPU。編譯環(huán)境：win8.1 64位操作系統(tǒng)，VS2013、OptiX3.8.0、CUDA7.5。

本次實(shí)驗(yàn)一共繪制了兩個(gè)場景，如圖12所示。上面兩圖是場景1：地板材質(zhì)是鏡面材質(zhì)、球表面材質(zhì)是高光材質(zhì)，其它為漫反射材質(zhì)，視點(diǎn)可以通過鼠標(biāo)和鍵盤的控制在場景中漫游，魚可以自由游動(dòng)。下面兩圖是場景2：在任意時(shí)刻人向Kinect招手，仙子模型就立刻停止原來的運(yùn)動(dòng)狀態(tài)并調(diào)整姿態(tài)向視點(diǎn)飛來，在此過程中也可隨時(shí)揮手讓仙子模型返回到原來的運(yùn)動(dòng)狀態(tài)。

圖12　場景繪制效果圖

在場景1中，物體具有不同的運(yùn)動(dòng)狀態(tài)和材質(zhì)，場景比較復(fù)雜，本文主要用場景1驗(yàn)證系統(tǒng)的負(fù)載均衡效果。圖13顯示了場景1分別在1臺(tái)、2臺(tái)、4臺(tái)機(jī)器上繪制時(shí)，繪制每幀所用的時(shí)間（負(fù)載均衡之后的結(jié)果），由圖可知，隨著機(jī)器臺(tái)數(shù)的增加，場景繪制效率大幅增加。但是由于機(jī)器之間的固有差異和網(wǎng)絡(luò)傳輸?shù)纫蛩?，繪制效率并不是線性增加的，不過已經(jīng)接近比較理想的狀態(tài)。

圖13　多節(jié)點(diǎn)繪制對(duì)比圖

圖14顯示了場景1負(fù)載均衡之前和之后的效果。在采取負(fù)載均衡之前，場景的劃分方式為按屏幕尺寸把場景均分為四份，由于場景不同部分的繪制時(shí)間開銷相差較大，所以劃分的結(jié)果一定是不均衡的。采取負(fù)載均衡之后，服務(wù)器會(huì)實(shí)時(shí)地根據(jù)子節(jié)點(diǎn)發(fā)來的像素遞歸深度數(shù)據(jù)，對(duì)場景進(jìn)行均衡地劃分。實(shí)驗(yàn)表明，該方法可以達(dá)到很好的集群負(fù)載均衡效果。

圖14　負(fù)載均衡效果圖

圖15　不同分辨率下的壓縮加速比

集群繪制中存在大量的數(shù)據(jù)傳輸。假設(shè)繪制的場景尺寸為1024×768，每個(gè)像素由R、G、B三個(gè)分量組成，場景繪制的幀率為20幀/秒，則系統(tǒng)需要每秒傳輸1024×768×3×20=45MB的數(shù)據(jù)量，這對(duì)系統(tǒng)來說是一個(gè)相當(dāng)大的負(fù)擔(dān)，因此節(jié)點(diǎn)有必要對(duì)結(jié)果數(shù)據(jù)進(jìn)行壓縮之后再傳送。本文分別統(tǒng)計(jì)了不同分辨率下的壓縮加速比，如圖15所示。從圖中可以看到，采取數(shù)據(jù)壓縮的方法可以大幅度減少網(wǎng)絡(luò)通信負(fù)擔(dān)，提高繪制效率。隨著分辨率的增加，壓縮加速比逐漸減小，這是因?yàn)榇蠓直娴膱鼍皵?shù)據(jù)量很大，即便對(duì)數(shù)據(jù)進(jìn)行了壓縮處理，網(wǎng)絡(luò)負(fù)擔(dān)仍然很重。

6　結(jié)論

為了實(shí)現(xiàn)實(shí)時(shí)交互式繪制，本文設(shè)計(jì)了一種在粗粒度和細(xì)粒度兩個(gè)層次上同時(shí)實(shí)現(xiàn)并行計(jì)算的集群繪制系統(tǒng)，然后基于Kinect的骨骼追蹤系統(tǒng)設(shè)計(jì)了一套交互手勢。針對(duì)集群繪制的負(fù)載均衡問題，提出了基于像素遞歸深度的實(shí)時(shí)負(fù)載均衡算法。該算法通過統(tǒng)計(jì)每一個(gè)像素實(shí)際產(chǎn)生的二次光線數(shù)量，得到整個(gè)場景的遞歸深度圖，從而量化了場景各個(gè)部分的繪制負(fù)擔(dān)。由于每個(gè)像素的遞歸深度是已知的，而且連續(xù)兩幀所對(duì)應(yīng)的場景具有一致性，因此該算法可以使系統(tǒng)快速實(shí)現(xiàn)負(fù)載均衡。

參考文獻(xiàn)

［1］Kun Zhou，Qi Ming Hou，Rui Wang，et al.Real-time k-D tree construction on graphics hardware. In Proc ［C］. SIGGRAPH Asia（2008），27（3）：1-11.

［2］Kirill Garanzha，Jacopo Pantaleoni，David McAllister. Simpler and faster HLBVH with work queues［C］. In Proceedings of the ACM SIGGRAPH Symposiumon High Performance Graphics，NewYork，（USA），2011.

［3］Cosenza B，Cordasco G，De Chiara R，et al.Load balancing in mesh-like computations using prediction binary trees［C］：2008 International Symposium on Parallel and Distributed Computing，Salerno（Italy），2011.IEEE.

［4］Biagio Cosenza，Gennaro Cordasco，Rosario De Chiara，et al. On estimating the effectiveness of temporal and spatial coherence in parallel ray tracing［C］. In Eurographics Italian Chapter Conference，Salerno （Italy），2008.

［5］Alan Chalmers，Erik Reinhard. Pratical parallel rendering［M］. A. K.Peters，Ltd.，2002：20-35.

［6］Biagio Cosenza，Carsten Dachsbacher，Ugo Erra. GPU cost estimation for load balancing in parallel ray tracing［C］. 8th International Conference on Computer Graphics Theory and Applications，Barcelona（Spain）2013.

［7］任崇輝.基于GPU的高真實(shí)感集群渲染系統(tǒng)［D］.杭州：浙江大學(xué)，2011：21-25，30.

［8］孔令德.計(jì)算機(jī)圖形學(xué)基礎(chǔ)教程［M］.北京：清華大學(xué)出版社，2008：113-115.

Study on Gesture-based Interactive 3D Scene Rendering Using Parallel Ray Tracing

JIANG Cong，CHEN Chunyi
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

Abstract：High quality realistic scenes can be rendered by ray tracing. However，it is always time-consuming，which makes it difficult to achieve real-time interaction. Cluster of workstations is often used for real-time interactive rendering，but it always has a problem of load balancing. In order to meet the requirements of real-time interaction and improve the efficiency of the cluster rendering，this paper designs a cluster rendering system which is parallel both in coarse-grained and fine-grained level. On the phenomenon of load imbalance，it also presents a real-time solution based on the recursion depth of the pixel. This method firstly counts the recursion depth of each pixel to get the recursion depth map of the entire scene and then divides the scene evenly according to the recursion depth. Due to the spatial and temporal coherence of two consecutive frames，the division result of the previous frame can be used as the estimation of the next frame. The advantage of this method is the ability to quickly realize the cluster load balance to support real time interactive rendering. Experiment shows that this cluster rendering system can efficiently perform Kinect-based real-time interactive rendering.

Key words：cluster；ray tracing；load banlancing；recursion depth；real-time interaction

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1672-9870（2016）02-0090-08

收稿日期：2015-10-30

基金項(xiàng)目：吉林省重點(diǎn)科技攻關(guān)項(xiàng)目（20140204009GX）；長春市重大科技攻關(guān)（14KG008）

作者簡介：蔣聰（1990-），男，碩士研究生，E-mail：jaingcong0303@hotmail.com

通訊作者：陳純毅（1981-），男，博士，副教授，博士生導(dǎo)師，E-mail：chenchunyi@hotmail.com