[發(fā)明專利]一種基于錯(cuò)切變形的并行體繪制系統(tǒng)

無效

• 申請?zhí)枺?/td>: 201010535263.4
• 申請日: 2010-11-03
• 公開（公告）號: CN102034263A
• 公開（公告）日: 2011-04-27
• 發(fā)明（設(shè)計(jì)）人: 何兵;吉志峰;趙沁平;郝愛民;王莉莉
• 申請（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號: G06T15/08
• 分類號: G06T15/08;H04L29/08
• 代理公司: 北京科迪生專利代理有限責(zé)任公司 11251
• 代理人: 李新華

1.基于錯(cuò)切變形的并行體繪制方法，其特征在于以速度最快的錯(cuò)切變形(Shear-Warp)體繪制算法為基礎(chǔ)，構(gòu)造分布式的并行體繪制系統(tǒng)，該系統(tǒng)由一個(gè)主節(jié)點(diǎn)和若干從節(jié)點(diǎn)構(gòu)成，主節(jié)點(diǎn)和從節(jié)點(diǎn)均采用普通PC機(jī)，節(jié)點(diǎn)間通過局域網(wǎng)連接；該并行體繪制系統(tǒng)借助基于掃描線及負(fù)載均衡原則的任務(wù)劃分方法和基于AIAMD思想的自適應(yīng)幀率控制策略，在保證可視化圖像質(zhì)量品質(zhì)的前提下，進(jìn)一步提高節(jié)點(diǎn)間的負(fù)載均衡性及繪制速度。具體包括以下步驟：

(1)啟動(dòng)主節(jié)點(diǎn)作為服務(wù)器端，以監(jiān)聽從從節(jié)點(diǎn)作為客戶端的連接請求，啟動(dòng)從節(jié)點(diǎn)作為客戶端；

(2)處理從節(jié)點(diǎn)的動(dòng)態(tài)加入及退出請求；

(3)主節(jié)點(diǎn)接收用戶交互操作，取得視點(diǎn)、模型位置和/或視線方向信息，計(jì)算繪制參數(shù)；

(4)主節(jié)點(diǎn)根據(jù)第(3)步獲得的繪制參數(shù)及各從節(jié)點(diǎn)上一幀的繪制時(shí)間、數(shù)據(jù)場可視化所需進(jìn)行的掃描線數(shù)量、及各從節(jié)點(diǎn)上一幀的繪制時(shí)間，重新為各從節(jié)點(diǎn)分配繪制任務(wù)，所述繪制任務(wù)為下一幀所需計(jì)算的掃描線數(shù)量和序號，并分發(fā)給各個(gè)已連接的從節(jié)點(diǎn)；

(5)主節(jié)點(diǎn)更新與各從節(jié)點(diǎn)相關(guān)的AIAMD時(shí)間預(yù)測模型參數(shù)；

(6)主節(jié)點(diǎn)計(jì)算各從節(jié)點(diǎn)下一幀繪制的開始時(shí)刻，并分發(fā)給各從節(jié)點(diǎn)，各從節(jié)點(diǎn)根據(jù)所述開始時(shí)刻控制本節(jié)點(diǎn)的繪制幀頻；

(7)各從節(jié)點(diǎn)根據(jù)掃描線任務(wù)劃分并依據(jù)錯(cuò)切變形算法進(jìn)行局部掃描線的可視化計(jì)算，形成局部圖像，并將局部圖像數(shù)據(jù)傳給主節(jié)點(diǎn)；

(8)主節(jié)點(diǎn)按掃描線序合并各從節(jié)點(diǎn)局部圖像數(shù)據(jù)，合成最終圖像并輸出。

2.根據(jù)權(quán)利要求1所述的基于錯(cuò)切變形的并行體繪制方法，其特征在于：所述步驟(5)中的AIAMD時(shí)間預(yù)測參數(shù)更新為自適應(yīng)動(dòng)態(tài)更新，具體包括：

(5.1)主節(jié)點(diǎn)接收到各從節(jié)發(fā)送來的每幀繪制信息，包括：

第i節(jié)點(diǎn)在第j幀的繪制時(shí)間：RT_i(j)，i＝1，2，…，N，j＝1，2，…；

第i節(jié)點(diǎn)在第j幀的數(shù)據(jù)傳送時(shí)間：ST_i(j)，i＝1，2，…，N，j＝1，2，…；

同時(shí)計(jì)算得到第i節(jié)點(diǎn)第j幀繪制任務(wù)完成的總時(shí)間：

TT_i(j)＝RT_i(j)+ST_i(j)，i＝1，2，…，N，j＝1，2，…；

從而求得當(dāng)前幀的所有節(jié)點(diǎn)總時(shí)間中的最大的總時(shí)間：

TTmax(j)=maxi{TTi(j)},]]>i＝1，2，…，N，j＝1，2，…；

(5.2)根據(jù)相鄰兩幀時(shí)間信息之間的變化情況對第j幀采用的時(shí)間預(yù)測參數(shù)α_j、β_j進(jìn)行取值范圍界定，分四種情況：

情況1；TT_max(j)＜TT_max(j-1)，則α_j＜0；β_j＝1

情況2：TT_max(j)＝TT_max(j-1)，則α_j＝0；β_j＝1

情況3：TT_max(j)＞TT_max(j-1)

且存在第i個(gè)節(jié)點(diǎn)RT_i(j)-RT_i(j-1)＞ST_i(j)-ST_i(j-1)

則α_j＞0；β_j＞1

情況3：TT_max(j)＞TT_max(j-1)

且存在第i個(gè)節(jié)點(diǎn)RT_i(j)-RT_i(j-1)＜ST_i(j)-ST_i(j-1)

則α_j＞0；β_j無約束

根據(jù)上述方法可以構(gòu)造第j幀對應(yīng)的α_j、β_j二階矩陣

X_2×1(j)＝[β_j??α_j]^T；

(5.3)構(gòu)造第j幀對應(yīng)的時(shí)間矩陣

T2×2(j)=TTmax(j)1×sign(αj)-TTmax(j)-1×sign(αj);]]>

構(gòu)造第j幀對應(yīng)的常數(shù)約束矩陣b_2×1(j)，其中C＝0.001為固定常數(shù)

b2×1(j)=TTmax(j)+CC-TTmax(j);]]>

(5.4)構(gòu)造第j幀對應(yīng)的關(guān)系約束函數(shù)T_2×2(j)X_2×1(j)≤b_2×1(j)，并在該約束條件下，求解α_j、β_j使得目標(biāo)函數(shù)最小，即

min?Z：T(j)＝α_j+β_j·TT_max(j-1)，j∈{1，2，…}

由此α_j、β_j的自適應(yīng)預(yù)測問題轉(zhuǎn)化為在給定范圍內(nèi)求解最優(yōu)α_j、β_j值，使目標(biāo)函數(shù)最小的問題，即典型的線性規(guī)劃問題，利用單純形算法完成上述問題的求解；具體的步驟如下：

1)設(shè)定α_j、β_j的取值范圍，構(gòu)造約束方程T_2×2(j)X_2×1(j)≤b_2×1(j)，設(shè)定目標(biāo)函數(shù)Z＝{TT_max(j)-[α_j+β_j·TT_max(j-1)]}²；

2)根據(jù)T_2×2(j)X_2×1(j)≤b_2×1(j)列出包含2個(gè)約束方程的系數(shù)矩陣；

3)找出上述系數(shù)矩陣中2個(gè)線性獨(dú)立的約束系數(shù)向量構(gòu)成的基；

4)根據(jù)第一個(gè)基找出對應(yīng)的基變量；

5)令系數(shù)矩陣中非基變量系數(shù)全為零，求出一個(gè)基可行解，同時(shí)得到第一個(gè)目標(biāo)函數(shù)值；

6)分析非基變量所在列的檢驗(yàn)數(shù)，若還存在正檢驗(yàn)數(shù)的非基變量，表示目標(biāo)函數(shù)值可能還有增加的可能，此時(shí)需要將某個(gè)非基變量與上次確定的某個(gè)基變量進(jìn)行對換，以便求出更優(yōu)的目標(biāo)函數(shù)值；

7)選擇具有最優(yōu)值的檢驗(yàn)數(shù)對應(yīng)的非基變量記為x，作為新的基變量換入；

8)確定需要從基中換出的變量，使之成為非基變量；

9)重復(fù)步驟5)、6)、7)、8)，直至非基變量列的檢驗(yàn)數(shù)中不存在正數(shù)為止；

10)與最大的目標(biāo)函數(shù)值對應(yīng)的各決策變量值就是該線性規(guī)劃問題的最優(yōu)解。

3.根據(jù)權(quán)利要求1所述的基于錯(cuò)切變形的并行體繪制方法，其特征在于：所述步驟(6)中的各從節(jié)點(diǎn)根據(jù)所述開始時(shí)刻控制本節(jié)點(diǎn)的繪制幀頻，具體為：

(6.1)主節(jié)點(diǎn)將統(tǒng)計(jì)得到的TT_max(j)交與幀頻管理器進(jìn)行處理，以便得到下一幀的時(shí)間塊T(j+1)，并根據(jù)第j幀的時(shí)間信息動(dòng)態(tài)預(yù)測第j+1幀的總的時(shí)間信息，其中α_j，β_j是第j幀采用的自適應(yīng)繪制時(shí)間預(yù)測參數(shù)，每幀動(dòng)態(tài)調(diào)整，針對T(j+1)的預(yù)測，本發(fā)明分以下三種情況加以處理：

情況1：當(dāng)?shù)趈幀的總時(shí)間小于第j-1幀時(shí)，采取加性減少策略溫和地減少第j+1幀的總時(shí)間：

T(j+1)＝TT_max(j)-|α_j|，j＝1，2，…為繪制幀號；

情況2：當(dāng)?shù)趈幀的總時(shí)間與第j-1幀的總時(shí)間相等時(shí)，當(dāng)前參數(shù)不變，第j+1幀總時(shí)間保持不變；

T(j+1)＝TT_max(j)，j＝1，2，…為繪制幀號；

情況3：當(dāng)?shù)趈幀的總時(shí)間大于第j-1幀的總時(shí)間時(shí)，如果繪制時(shí)間大于網(wǎng)絡(luò)傳送時(shí)間，則采取加性增加的策略增加第j+1幀的總時(shí)間：

T(j+1)＝TT_max(j)+|α_j|，j＝1，2，…為繪制幀號；

如果網(wǎng)絡(luò)傳送時(shí)間大于繪制時(shí)間，則說明網(wǎng)絡(luò)的負(fù)載量增加，采取了乘性增加的策略：

T(j+1)＝β_j·TT_max(j)，j＝1，2，…為繪制幀號；

(6.2)各從節(jié)點(diǎn)收到第j+1幀的預(yù)測時(shí)間塊后，根據(jù)第i節(jié)點(diǎn)的掃描線任務(wù)劃分開始基于錯(cuò)切變形的可視化計(jì)算，同時(shí)統(tǒng)計(jì)第i節(jié)點(diǎn)第j+1幀的繪制時(shí)間RT_i(j+1)及傳送時(shí)間ST_i(j+1)，計(jì)算j+1幀實(shí)際花費(fèi)的總時(shí)間TT_i(j+1)并與主節(jié)點(diǎn)設(shè)定的總時(shí)間T(j+1)比較，如果TT_i(j+1)≥T(j+1)，則立即轉(zhuǎn)入下一幀的繪制工作；反之，如果TT_i(j+1)＜T(j+1)，休眠到T(j+1)時(shí)間塊滿，然后轉(zhuǎn)入下一幀的繪制工作。