婁自婷 張亞萍

摘要：針對由存儲帶寬和數(shù)據(jù)訪問速度導致的復雜數(shù)據(jù)集繪制性能低下等問題，提出了一種基于貪心優(yōu)化策略的三角形排布算法，通過對繪制數(shù)據(jù)集進行重排以改善數(shù)據(jù)的空間局部性和時間局部性。該算法首先將頂點分為三類，根據(jù)改進的代價函數(shù)選擇代價度量最小的頂點作為活動頂點；然后繪制（即輸出）其所有未繪制的鄰接三角形，并將相鄰頂點壓入緩存，算法迭代執(zhí)行直到所有頂點的鄰接三角形都繪制完成，得到重新排列后的三角形序列。實驗結(jié)果表明，該算法不僅具備較高的頂點緩存命中率，還提高了渲染速度，減少了排序的時間，有效地解決了圖形處理器的處理速度不斷提升而數(shù)據(jù)訪問速度嚴重滯后的問題。

關(guān)鍵詞：

緩存優(yōu)化；網(wǎng)格排布；貪心優(yōu)化策略；平均緩存失配率；三維網(wǎng)格模型

中圖分類號： TP391.41 文獻標志碼：A

0引言

盡管近年來中央處理器（Central Processing Unit， CPU）與圖形處理器（Graphics Processing Unit， GPU）的處理能力都有了很大的提升，但復雜數(shù)據(jù)集的繪制性能問題仍然存在，這主要是由于存儲帶寬和數(shù)據(jù)訪問速度的增長遠落后于處理能力的增長，數(shù)據(jù)的輸入輸出成為大規(guī)模數(shù)據(jù)處理最主要的瓶頸。為此，現(xiàn)代計算機系統(tǒng)大量采用了緩存機制，使用小容量的高速存儲器為大容量的低速存儲器提供緩存。為了充分利用緩存機制，數(shù)據(jù)應(yīng)該有良好的局部性（locality）。局部性有兩種基本形式：空間局部性（spatial locality）與時間局部性（temporal locality）?？臻g局部性表示與當前訪問的數(shù)據(jù)單元鄰近的數(shù)據(jù)單元很可能會被訪問。時間局部性表示如果一個數(shù)據(jù)單元正在被訪問，那在近期它很可能會被再次訪問[1]。

為了提高CPU和GPU之間的數(shù)據(jù)交換速度，減輕頂點讀取時的帶寬要求，GPU采用頂點緩存機制與紋理緩存機制避免重復的頂點計算以提高緩存性能[2]，目前已有多種優(yōu)化紋理緩存訪問效率的算法[3]，而提高頂點緩存訪問效率的算法屈指可數(shù)。頂點緩存的訪問性能通常用平均緩存失配率（Average Cache Miss Rate， ACMR）來衡量，定義為繪制每個三角形的平均緩存失配次數(shù)，即緩存的總失配次數(shù)與總訪問次數(shù)之比，ACMR的取值范圍為[0.5，3.0]，因為每個頂點至少失配一次，至多失配三次。需要注意的是，ACMR無法達到最小值，主要是因為頂點緩存區(qū)容量的限制。若頂點緩存區(qū)可以裝下所有頂點，則以任何方式組織的三角形都可以使ACMR接近于0.5，但是緩存容量很小，很難裝下所有的頂點，假設(shè)緩存容量為k，三角形頂點個數(shù)為n，k往往小于n，在理想情況下ACMR可以達到的最小值為k/2（k-1）=0.5+Ω（1/k），其中Ω（1/k）是1/k的線性函數(shù)[4]。此外，網(wǎng)格的形狀也會導致ACMR額外的開銷，因此要提高頂點緩存訪問效率，需降低ACMR值，進行緩存優(yōu)化。

1網(wǎng)格排布優(yōu)化

緩存優(yōu)化技術(shù)除了與硬件性能有直接關(guān)系，還與數(shù)據(jù)訪問方式和數(shù)據(jù)排列方式有關(guān)。針對后者，設(shè)計緩存優(yōu)化算法，通過重排技術(shù)來提高緩存訪問性能。重排技術(shù)包括計算重排與數(shù)據(jù)重排[5]：1）計算重排，即根據(jù)重新排列指令順序，提高訪問相同數(shù)據(jù)單元指令的局部性，通常由編譯器對應(yīng)用程序編譯后的指令序列進行重排來完成，對于指令，重新組織程序而不影響程序的正確性；2）數(shù)據(jù)重排，即根據(jù)指令對數(shù)據(jù)單元的訪問方式求解出緩存連貫的數(shù)據(jù)排布，由應(yīng)用程序直接對數(shù)據(jù)進行重排來完成，通過優(yōu)化改善數(shù)據(jù)的空間局部性和時間局部性。

目前基于網(wǎng)格排布的緩存優(yōu)化技術(shù)（以下簡稱網(wǎng)格排布優(yōu)化技術(shù)）是計算機圖形學與可視化領(lǐng)域的重點研究方向之一，該技術(shù)基于數(shù)據(jù)重排。根據(jù)求解技術(shù)手段的不同，網(wǎng)格排布優(yōu)化技術(shù)可分為基于優(yōu)化策略、基于空間填充曲線和基于譜序列三類[1]；根據(jù)網(wǎng)格描述方式的不同，可分為基于三角形、基于三角形條帶、基于三角形扇，每種描述方式又可分為索引形式和三角形形式[6]。因為索引形式只需少量數(shù)據(jù)，傳輸代價小，使之成為目前使用最為普遍的方式，但頂點隨機讀取也帶來了ACMR的增加，因此許多研究者提出對網(wǎng)格圖元的存儲順序進行重新排布，可以減小ACMR，降低頂點處理的運算量，提高渲染速度。

Hoppe[2]提出了基于貪心優(yōu)化策略的條帶算法，沿著逆時針方向生成條帶，進行三角形條帶合并，在合并的過程中不斷檢測預(yù)期的ACMR，以此降低頂點緩存失配率。Bogomjakov等[7]提出了基于空間填充曲線的非條帶算法，該算法使用圖劃分軟件包Metis[8]將網(wǎng)格分成多個三角形簇，保證每個簇內(nèi)三角形序列的ACMR最優(yōu)，從而形成整個網(wǎng)格的ACMR最優(yōu)化。Lin等[9]也提出了一種基于優(yōu)化策略的三角形繪制序列生成算法，應(yīng)用啟發(fā)式條件對網(wǎng)格頂點進行全局搜索，同樣可以得到很低的ACMR。Sander等[10]對Lin等[9]算法進行了改進，該算法只在上一個輸出的三角形環(huán)周圍進行啟發(fā)式搜索。Nehab等[11]提出了一種基于優(yōu)化策略的多功能三角形序列重排算法，該算法不僅可以減小ACMR，還可以減小圖元的重繪率（OVerdraw Ratio， OVR）。除了上述幾種常見算法外，Yoon等[12]提出了一種在未知緩存參數(shù)情況下的網(wǎng)格排布優(yōu)化算法，在不用修改應(yīng)用程序的條件下，該算法對基于視點的繪制、碰撞檢測和等值線提取等幾何應(yīng)用達到了2～20倍的加速比。Liu等 [13]提出了一種基于圖距離函數(shù)的譜序列算法，該算法先為圖中的任意點對計算一個距離值，然后計算圖中的一個高維嵌入，使在嵌入中頂點的距離關(guān)系和最先計算的圖的距離函數(shù)一致，最后將嵌入中的點投影到一個向量上，并對其進行排序。Bartholdi等 [14]提出了一種基于空間填充曲線的三角網(wǎng)格多分辨率索引方法。Limper等[15]提出了一種隔行掃描的網(wǎng)格排布優(yōu)化算法，該算法在繪制過程中會對ACMR產(chǎn)生負面的影響，也影響了整體的渲染性能。

相對于國外，國內(nèi)研究該領(lǐng)域的較少，有熊華[1]、石教英[16]提出的基于三角形排布的緩存優(yōu)化算法，該算法的核心思想是對于與當前緩存中頂點鄰接而本身不在緩存中的頂點，如果將該頂點壓入緩存中，并且不再壓入其他頂點時，計算可以直接輸出最多三角形數(shù)量的頂點作為當前輸出頂點，將其壓入緩存中，并將可輸出的三角形全部輸出。該算法主要優(yōu)點在于計算速度快，ACMR接近于Lin等[9]提出的算法。陳思遠等[4]提出的基于三角形條帶的網(wǎng)格排布優(yōu)化算法，目的在于降低運算時間復雜度，并且使ACMR接近于Hoppe與Lin等[9]算法。算法的基本思想是頂點緩存中駐留的頂點為后續(xù)的三角形條帶提供了公共邊，沿著這些公共邊將三角形以條帶為單位進行遍歷，可以得到理想的ACMR值，并且在遍歷衍生條帶的過程中到達網(wǎng)格的邊界時，需要選擇合適的位置重新初始化新的條帶，在此期間需要考慮減少重新初始化時造成的ACMR開銷。秦愛紅等[6]提出的基于混合模式的緩存優(yōu)化算法，該算法的核心思想是采用優(yōu)化求解傳輸代價方程，通過精確地模擬緩存狀態(tài)變化得到理想的緩存命中率，啟用后進先用的數(shù)據(jù)引用方式重新定義優(yōu)化求解傳輸代價方程，使三角形條帶同時兼顧順時針和逆時針增長方向，極大地提高了三角形條帶內(nèi)部頂點的重用性，使之在任意頂點緩存中可有效地提高頂點緩存命中率。陸揚[17]提出的基于均勻網(wǎng)格的預(yù)處理算法，該算法首先將網(wǎng)格分為大小盡可能相等的多塊子網(wǎng)格，然后采用Sander等[10]提出的算法對頂點進行重排序，該算法對不同拓撲特征、不同網(wǎng)格規(guī)模的模型能產(chǎn)生較低的ACMR。

2基于貪心優(yōu)化策略的網(wǎng)格排布算法

2.1算法分析比較

本文給出了8種常見算法的平均ACMR值，如圖1所示。由圖1可以看出，原先這部分用的人名表示的算法，比較亂，現(xiàn)統(tǒng)一改為文獻幾算法，核實。正確文獻[9]算法與文獻[2]算法平均ACMR值最低，文獻[10]算法、文獻[11]算法與文獻[1] 算法略高于文獻[9]算法與文獻[2]算法，其余算法優(yōu)化效果較差。

如圖2所示為PLY（Polygon File Format）文件格式，主要用以存儲立體掃描結(jié)果的三維數(shù)值，透過多邊形面片的集合掃描三維物體，有純文字（ASCII）與二元碼（binary）兩種版本，其差異在于存儲時是否以ASCII編碼表示元素資訊。該模型表示與其他格式相比較為簡單。表1給出了它們的頂點數(shù)量、三角形數(shù)量和數(shù)據(jù)量大小，其中數(shù)據(jù)量是指ASCII格式的網(wǎng)格文件的大小。

表2給出了五個測試模型使用文獻[9]算法進行網(wǎng)格排布優(yōu)化的ACMR值和執(zhí)行時間，文中的實驗數(shù)據(jù)都在Intel Core i72600 @ 3.40GHz，NVIDIA GeForce GTX 460（1GB） ，4GB內(nèi)存的實驗環(huán)境中測得。從表2中可以看出，該算法在緩存為12時得到的ACMR值最優(yōu)，雖然優(yōu)化時間也最優(yōu)，但還是相對較長，與模型大小、緩存大小成正比關(guān)系。所以本文通過改進文獻[9]算法（LinSort），使ACMR更優(yōu)，同時減少算法的執(zhí)行時間。

2.2基于貪心優(yōu)化策略的三角形排布優(yōu)化算法

為了保證算法效率與優(yōu)化效果，本文對LinSort進行了改進，提出一種基于貪心優(yōu)化策略的三角形排布優(yōu)化算法。該算法的核心思想是將頂點定義為以下3類：1）白色表示頂點不在緩存中。與該頂點鄰接的一部分或所有三角形都沒有被繪制，因此需要在繪制時將頂點放入緩存。2）灰色表示頂點在緩存中。3）黑色表示與該頂點鄰接的所有三角形都已經(jīng)被繪制，該頂點可能在也可能不在緩存中。一旦該頂點離開緩存，在繪制時將不再需要該頂點，也不需要將其壓入緩存中。

在每次迭代執(zhí)行算法時，選擇一個灰色或者白色（緩存為空時）頂點作為活動頂點，將該頂點的所有未繪制的鄰接三角形頂點壓入緩存并進行繪制。一旦頂點連接的所有鄰接三角形都已經(jīng)被繪制，將該頂點標記為黑色。該算法的基本思想是在繪制期間保證算法局部性，即減少每一個頂點的緩存失配次數(shù)（緩存失配率），因此需要在每個繪制階段決定用哪個頂點作為活動頂點，這也決定了最終呈現(xiàn)的繪制序列。

為了達到最優(yōu)繪制效率，減小緩存失配率，賦予每個頂點v一個代價度量，用C（v）表示。在選擇當前頂點時，根據(jù)代價函數(shù)選擇代價度量最小的頂點，在LinSort [9]中，代價函數(shù)表示為：

C（v）=k1C1（v）+其他K1與K3與后面項全是乘，只有k2與C2是除，核實是否正確？正確k2/C2（v）+k3C3（v）

（1）

其中：C1（v）表示繪制完頂點v所有未繪制的鄰接三角形時，需要壓入緩存的頂點數(shù)；C2（v）表示在頂點v標記為黑色之前可以繪制的三角形數(shù)量；C3（v）表示頂點v標記為黑色時在緩存中的位置；k1、k2、k3為權(quán)重系數(shù)，也是影響ACMR的重要因素。在LinSort [9]中，對任意的模型沒有給出特定的權(quán)重，而是憑直覺給出了經(jīng)驗值，當K=12、k1=1、k2=0.5、k3=1.3時得到的ACMR最低。設(shè)置這一組經(jīng)驗值是因為三角形數(shù)通常是頂點數(shù)的2倍，為了保證C1與C2的一致性，設(shè)置k1≈2k2，k3應(yīng)接近于k1與k2，表3即在該條件下測得。而經(jīng)過多次實驗，發(fā)現(xiàn)文獻[9]給出的經(jīng)驗值雖然能得到最優(yōu)的ACMR值，但是在K=12、k1=1保持不變的情況下，設(shè)置k2與k3的值，k2=0.5～6.5、k3=0.1～2.7的范圍內(nèi)得到的ACMR偏差都在0.1內(nèi)，但是對于先進先出（First Input First Output， FIFO）置換策略，需要設(shè)置k3值大于1，因為在此條件下，才能優(yōu)先考慮先進入緩存的頂點，防止頂點再次壓入緩存。

如圖3所示，實心圓點表示該頂點已經(jīng)在緩存中，空心圓點表示頂點還未繪制，C1與C2分別表示需要壓入的頂點數(shù)與可以繪制的三角形數(shù)，同C1（v）與C2（v）。若根據(jù)文獻[9]提出的代價函數(shù)選擇最小代價度量的頂點作為當前活動頂點，選擇K=12、k1=1、k2=0.5、k3=1.3，則圖3（a）為1.25+1.3C3（v），圖3（b）為1.5+1.3C3（v），圖3（c）為2.5+1.3C3（v），圖3（d）為3.17+1.3 C3（v）。根據(jù)當前緩存情況及代價函數(shù)，本文選擇圖3（a）進行繪制，可使本次操作的失配率最低，從而降低總的ACMR。

當只有圖3（c）～（d）兩種情況時，根據(jù)最小代價度量函數(shù)，選擇圖3（c）進行繪制，但是為保證ACMR最優(yōu)，對與當前緩存中頂點鄰接而不在緩存中的頂點，在壓入該頂點到緩存中時，需要選擇可輸出三角形數(shù)最多的頂點。在圖3（a）中，如果將空心圓點壓入緩存中，可以輸出兩個三角形，平均緩存失配率為1/2；在圖3（b）中，如果將空心圓點壓入緩存中，可以輸出一個三角形，平均緩存失配率為1；在圖3（c）中，如果壓入兩個空心圓點到緩存中才能輸出一個三角形，平均緩存失配率為2；在圖3（d）中，如果壓入三個空心圓點到緩存中可以輸出三個三角形，平均緩存失配率為1。所以在只有圖3（c）～（d）兩種情況時，應(yīng)該選擇圖3（d）才能使ACMR最優(yōu)。故此，在Lin等[9]計算最小代價度量的代價函數(shù)基礎(chǔ)上加上平均緩存失配率，即C1（v）/ C2（v），將改進的代價函數(shù)表示為：

C（v）=k1C1（v）+為什么別的項是乘，其他項是除，核實是否正確？正確k2/C2（v）+k3C3（v）+C1（v）/ C2（v）

（2）

根據(jù)改進的代價函數(shù)計算圖3（c）～（d）的最小代價度量，得到圖3（c）為4.5+1.3C3（v），圖3（d）為4.17+1.3C3（v），前者大于后者，證實了選擇圖3（d）進行繪制可以得到更低的ACMR值。

下面給出了算法的偽碼描述，其中V和F分別表示模型的頂點集和面集；M為FIFO緩存模型；Vw、Vg、Vb分別表示白色、灰色和黑色頂點集；Vg表示當前緩存區(qū)的頂點集；Foutput表示生成的三角形繪制序列。當Vg≠時，選擇Vg中代價度量最小的頂點作為活動頂點vfocus，也就是vfocus =arg minv∈Vg C（v）。如果緩存為空，即Vg=，選擇任意一個白色頂點作為活動頂點壓入緩存，并標記為灰色。

Procedure KCacheReorder（V，F(xiàn)，M）。

程序前

1）

Initialization： Vw ← V， Vg ← ， Vb ← ， Foutput ←

2）

While | Vb |<| V|

/*iterate until all vertices turn into black*/

3）

if Vg=

/*buffer is empty*/

4）

vfocus ← any white vertex

5）

else

6）

vfocus ← minimum cost vertex in Vg

7）

F′（vfocus） ←{f∈F ＼ Foutput： vfocus is a vertex of f}

8）

for each f∈F′（vfocus）

9）

V′（f） ←{white vertex（es） of f}

10）

for each v∈V′（f）

11）

if | Vg|=K

/*buffer is full*/

12）

pop_one（M， Vg， f）， v ← first vertex of Vg

13）

Push v： Vw ← Vw＼{v}， Vg ← Vg∪{v}

14）

Output any renderable faces except f

15）

Output f ： Foutput ← Foutput∪{f}

16）

Turn vfocusblack： Vb ← Vb∪{vfocus}

17）

這一句之前在16后面，為什么不單獨列序號？排版時換了16、17、18三句，核實是否有誤？都可以if Vg≠

18）

Vg ← Vg＼{vfocus}

19）

Checking each v∈Vg for the possible turning black and leaving the buffer

程序后

2.3排布算法流程

首先給出該算法的相關(guān)數(shù)據(jù)結(jié)構(gòu)：

程序前

typedef struct VertCachRec{

//頂點在緩存中的記錄

unsigned int nVertIdx；

//頂點索引

byte bFlag；

//頂點標記

}VertCachRec；

typedef struct WhiteVertRec{

//白色頂點記錄

unsigned int nVertIdx；

//白色頂點索引

WhiteVertRec* pNextRec；

//指向下一個白色頂點

}WhiteVertRec；

class CVertexConnRecord{

//頂點鄰接的三角形記錄

std：：dequem_pFaceIdx；//三角形索引列表

byte m_bFlag；

//頂點標記

}；

//頂點鄰接的三角形記錄

CVertexConnRecord* m_pVertexConnRec；

//白色頂點列表

WhiteVertRec** m_pWhiteVertHashMap；

//當前頂點緩存列表

std：：deque m_pVertCacheQue；

程序后

對于算法輸入，采用三角形索引方式，每個三角形包含三個頂點索引。對于算法輸出，內(nèi)容與輸入的序列一樣，只是三角形的位置被重新排列。

下面是該算法的關(guān)鍵步驟：

1）提取三角形頂點信息，掃描三角形頂點列表，將頂點鄰接的所有三角形索引壓入頂點鄰接的三角形記錄的三角形索引列表中，建立三角形之間的連接關(guān)系。然后再次掃描頂點列表，計算每個頂點鄰接的三角形數(shù)，若鄰接三角形為0，表明該頂點為孤立頂點，標記為黑色頂點；否則將該頂點標記為白色頂點，創(chuàng)建白色頂點記錄并將白色頂點壓入白色頂點列表中。

2）初始化網(wǎng)格排布優(yōu)化。此時的緩存為空，若白色頂點列表不為空，遍歷白色頂點列表，選擇任意一個白色頂點作為活動頂點，將白色頂點壓入頂點緩存，并標記為灰色頂點。

3）選擇活動頂點進行繪制。遍歷緩存，分別計算緩存中當前頂點所有未繪制的鄰接三角形，需要壓入緩存的頂點數(shù)及當前在緩存中的位置，然后根據(jù)代價函數(shù)選擇代價度量最小的灰色頂點作為活動頂點進行繪制。當一個頂點的所有鄰接三角形都已經(jīng)被繪制，則將該頂點標記為黑色。

對于需要壓入緩存的頂點數(shù)，首先遍歷頂點鄰接三角形記錄的三角形索引列表，得到當前頂點連接的三角形索引及三角形索引對應(yīng)的所有頂點索引，判斷這些鄰接三角形頂點標記。若鄰接三角形頂點標記為白色，則將該頂點從白色頂點列表中彈出，并壓入緩存列表，將該頂點標記為灰色，從而得到最終需要壓入緩存的頂點數(shù)。若FIFO頂點緩存已滿，彈出緩存頭部的頂點，將活動頂點未繪制的鄰接三角形頂點壓入頂點緩存。若緩存頭部頂點的鄰接三角形還未繪制完，則需要將該頂點再次標記為白色，壓入白色頂點列表中，需要時再次壓入緩存；若該頂點鄰接的所有三角形都已經(jīng)被繪制且該頂點已經(jīng)標記為黑色頂點，則直接將該頂點彈出緩存，且不再需要壓入緩存中。

4）若三角形全部頂點都標記為黑色，表明頂點已經(jīng)全部繪制完，得到重新排列后的三角形繪制序列。

3實驗結(jié)果與比較

表4給出了本文算法與LinSort[9]的優(yōu)化結(jié)果，其中緩存大小為12，k1=1、k2=0.5、k3=1.3，可以看出，本文算法相對于LinSort[9]，ACMR的值更低。圖4（a）表示測試網(wǎng)格模型的原始網(wǎng)格排布，圖4（b）表示模型優(yōu)化后的網(wǎng)格排布，顏色深淺表示圖元順序前后位置。圖5（a）～（b）分別表示模型進行三角形排布優(yōu)化前及優(yōu)化后的緩存失配結(jié)果，黑白印刷，彩色無法體現(xiàn)，請改成灰度描述。已核實黑色表示緩存失配，灰色表示緩存命中。

表5統(tǒng)計了五個測試模型在LinSort [9]和本文算法中的執(zhí)行時間。從表4～5中可見，與LinSort [9]相比，本文算法的ACMR值降低了，優(yōu)化算法時間也相對減少。分析其原因，主要是因為LinSort [9]在初始化網(wǎng)格時選擇頂點鄰接三角形最小的白色頂點作為活動頂點，而本文算法選擇任意白色頂點作為活動頂點。在選擇最小代價度量值時，不僅考慮鄰接的未輸出三角形數(shù)量、繪制完這些鄰接三角形需要壓入緩存的頂點數(shù)及頂點在緩存中的位置三個因素，還考慮了前兩者的權(quán)重，因此在保證網(wǎng)格優(yōu)化質(zhì)量的同時減少了算法的執(zhí)行時間。

為了考察模型大小及模型優(yōu)化后的ACMR對渲染性能的影響，對上述5個模型在LinSort和本文算法下得到的優(yōu)化結(jié)果進行模型交互繪制速率的測試，測試結(jié)果如表6所示。由表6中數(shù)據(jù)可知，模型交互繪制速率與模型大小非常接近于線性反比關(guān)系，模型交互繪制速率隨著模型的增大而降低；單個模型交互繪制速率與ACMR值也成反比關(guān)系，模型交互繪制速率隨著ACMR值的降低而提高。

4結(jié)語

在深入分析LinSort算法的基礎(chǔ)上，本文提出了一種改進的基于貪心優(yōu)化策略的網(wǎng)格排布算法。實驗表明，該算法不僅具備更高的頂點緩存命中率，還提高了渲染速度，減少了排序的時間。具體而言，本文的基于貪心優(yōu)化策略的網(wǎng)格排布優(yōu)化算法具有以下特點：1）對輸入網(wǎng)格模型拓撲結(jié)構(gòu)沒有要求，可以處理非條帶三角形網(wǎng)格； 2）針對三角形序列直接進行重排，便于與其他算法和應(yīng)用系統(tǒng)的集成； 3）代價度量與多個因素相關(guān)，優(yōu)化質(zhì)量高，計算速度快，但該算法只適用于100MB以下的網(wǎng)格模型，而對于大規(guī)模三維網(wǎng)格模型無法直接進行重排，并且本文時間復雜度還沒有成數(shù)量級降低，所以接下來的工作主要針對大規(guī)模網(wǎng)格模型，采用網(wǎng)格分割算法將網(wǎng)格分割成多個子網(wǎng)格，然后對每一個子網(wǎng)格進行并行的緩存優(yōu)化處理，使大規(guī)模三維網(wǎng)格模型能進行網(wǎng)格排布，并且在保證優(yōu)化效果的同時大幅度提高算法執(zhí)行速度。

參考文獻：

[1]

熊華.面向并行環(huán)境的繪制加速技術(shù)研究[D].杭州：浙江大學，2008：71-80. （XIONG H. Research of rendering acceleration techniques for parallel environments [D]. Hangzhou： Zhejiang University， 2008： 71-80.）

[2]

HOPPE H. Optimization of mesh locality for transparent vertex caching [C]// SIGGRAPH99： Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM， 1999： 269-276.

[3]

戴雪峰，熊漢江，龔健雅.一種三維城市模型多紋理自動合并方法[J].武漢大學學報：信息科學版，2015，40（3）：347-352. （DAI X F， XIONG H J， GONG J Y. A multitexture automatic merging approach for the 3D city models [J]. Geomatics and Information Science of Wuhan University， 2015， 40（3）： 347-352.）

[4]

陳思遠，史廣順，王慶人.通過三角形strip衍生實現(xiàn)三維模型數(shù)據(jù)的渲染優(yōu)化[J].計算機輔助設(shè)計與圖形學學報，2009，21（8）：1155-1163.（CHEN S Y， SHI G S， WAND Q R. Data optimization for 3D model rendering by triangle strip deriving [J]. Journal of ComputerAided Design & Computer Graphics， 2009， 21（8）： 1155-1163.）

[5]

YOON SE， LINDSTROM P. Mesh layouts for blockbased caches [J]. IEEE Transactions on Visualization and Computer Graphics， 2006， 12（5）： 1213-1220.

[6]

秦愛紅，石教英.基于混合模式緩存優(yōu)化的三角形條帶化[J].計算機輔助設(shè)計與圖形學學報，2011，23（6）：1006-1012. （QIN A H， SHI J Y. Cachefriendly triangle strip generation based on hybrid model [J]. Journal of ComputerAided Design & Computer Graphics， 2011， 23（6）： 1006-1012.）

[7]

BOGOMJAKOV A， GOTSMAN C. Universal rendering sequences for transparent vertex caching of progressive meshes [J]. Computer Graphics Forum， 2002， 21（2）： 137-148.

[8]

KARYPIS G， KUMAR V. Multilevel kway partitioning scheme for irregular graphs [J]. Journal of Parallel and Distributed Computing， 1998， 48（1）： 96-129.

[9]

LIN G， YU T P Y. An improved vertex caching scheme for 3D mesh rendering [J]. IEEE Transactions on Visualization and Computer Graphics， 2006， 12（4）： 640-648.

[10]

SANDER P V， NEHAB D， BARCZAK J. Fast triangle reordering for vertex locality and reduced overdraw [J]. ACM Transactions on Graphics， 2007， 26（3）： 89-97.

[11]

NEHAB D， BARCZAK J， SANDER P. Triangle order optimization for graphics hardware computation culling [C]// Proceeding of 2006 Symposium on Interactive 3D Graphics and Games. New York： ACM， 2006： 207-211.

[12]

YOON S， LINDSTROM P， PASCUCCI V， et al. Cacheoblivious mesh layouts [J]. ACM Transactions on Graphics， 2005， 24（3）： 886-893.

[13]

LIU R， ZHANG H， VAN KAICK O. Spectral sequencing based on graph distance [C]// GMP 2006： Proceeding of the 4th International Conference on Geometric Modeling and Processing， LNCS 4077. Berlin： Springer， 2006： 632-638.

[14]

BARTHOLDI J J， GOLDSMAN P. Multiresolution indexing of triangulated irregular networks [J]. IEEE Transactions on Visualization and Computer Graphics， 2004， 10（4）： 484-495.

[15]

LIMPER M， JUNG Y， BEHR J， et al. The POP buffer： rapid progressive clustering by geometry quantization [J]. Computer Graphics Forum， 2013， 32（7）： 197-206.

[16]

石教英.分布并行圖形繪制技術(shù)及其應(yīng)用[M].北京：科學出版社，2010：189-274.（SHI J Y. Distributed Parallel Rendering Technique and Its Application [M]. Beijing： Science Press， 2010： 189-274.）

[17]

陸揚.基于CUDA的三角形并行處理[D].合肥：中國科學技術(shù)大學，2010：13-21. （LU Y. Parallel triangle processing with CUDA [D]. Hefei： University of Science and Technology of China， 2010： 13-21.）