婁自婷 張亞萍

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

關(guān)鍵詞：

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

中圖分類號(hào)： TP391.41 文獻(xiàn)標(biāo)志碼：A

0引言

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

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

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

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

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

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

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

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

2.1算法分析比較

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

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

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

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

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

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

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

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

（1）

其中：C1（v）表示繪制完頂點(diǎn)v所有未繪制的鄰接三角形時(shí)，需要壓入緩存的頂點(diǎn)數(shù)；C2（v）表示在頂點(diǎn)v標(biāo)記為黑色之前可以繪制的三角形數(shù)量；C3（v）表示頂點(diǎn)v標(biāo)記為黑色時(shí)在緩存中的位置；k1、k2、k3為權(quán)重系數(shù)，也是影響ACMR的重要因素。在LinSort [9]中，對(duì)任意的模型沒(méi)有給出特定的權(quán)重，而是憑直覺(jué)給出了經(jīng)驗(yàn)值，當(dāng)K=12、k1=1、k2=0.5、k3=1.3時(shí)得到的ACMR最低。設(shè)置這一組經(jīng)驗(yàn)值是因?yàn)槿切螖?shù)通常是頂點(diǎn)數(shù)的2倍，為了保證C1與C2的一致性，設(shè)置k1≈2k2，k3應(yīng)接近于k1與k2，表3即在該條件下測(cè)得。而經(jīng)過(guò)多次實(shí)驗(yàn)，發(fā)現(xiàn)文獻(xiàn)[9]給出的經(jīng)驗(yàn)值雖然能得到最優(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)，但是對(duì)于先進(jìn)先出（First Input First Output， FIFO）置換策略，需要設(shè)置k3值大于1，因?yàn)樵诖藯l件下，才能優(yōu)先考慮先進(jìn)入緩存的頂點(diǎn)，防止頂點(diǎn)再次壓入緩存。

如圖3所示，實(shí)心圓點(diǎn)表示該頂點(diǎn)已經(jīng)在緩存中，空心圓點(diǎn)表示頂點(diǎn)還未繪制，C1與C2分別表示需要壓入的頂點(diǎn)數(shù)與可以繪制的三角形數(shù)，同C1（v）與C2（v）。若根據(jù)文獻(xiàn)[9]提出的代價(jià)函數(shù)選擇最小代價(jià)度量的頂點(diǎn)作為當(dāng)前活動(dòng)頂點(diǎn)，選擇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ù)當(dāng)前緩存情況及代價(jià)函數(shù)，本文選擇圖3（a）進(jìn)行繪制，可使本次操作的失配率最低，從而降低總的ACMR。

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

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

（2）

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

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

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后面，為什么不單獨(dú)列序號(hào)？排版時(shí)換了16、17、18三句，核實(shí)是否有誤？都可以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{

//頂點(diǎn)在緩存中的記錄

unsigned int nVertIdx；

//頂點(diǎn)索引

byte bFlag；

//頂點(diǎn)標(biāo)記

}VertCachRec；

typedef struct WhiteVertRec{

//白色頂點(diǎn)記錄

unsigned int nVertIdx；

//白色頂點(diǎn)索引

WhiteVertRec* pNextRec；

//指向下一個(gè)白色頂點(diǎn)

}WhiteVertRec；

class CVertexConnRecord{

//頂點(diǎn)鄰接的三角形記錄

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

byte m_bFlag；

//頂點(diǎn)標(biāo)記

}；

//頂點(diǎn)鄰接的三角形記錄

CVertexConnRecord* m_pVertexConnRec；

//白色頂點(diǎn)列表

WhiteVertRec** m_pWhiteVertHashMap；

//當(dāng)前頂點(diǎn)緩存列表

std：：deque m_pVertCacheQue；

程序后

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

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

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

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

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

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

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

3實(shí)驗(yàn)結(jié)果與比較

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

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1]

熊華.面向并行環(huán)境的繪制加速技術(shù)研究[D].杭州：浙江大學(xué)，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]

戴雪峰，熊漢江，龔健雅.一種三維城市模型多紋理自動(dòng)合并方法[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，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]

陳思遠(yuǎn)，史廣順，王慶人.通過(guò)三角形strip衍生實(shí)現(xiàn)三維模型數(shù)據(jù)的渲染優(yōu)化[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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]

秦愛(ài)紅，石教英.基于混合模式緩存優(yōu)化的三角形條帶化[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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].北京：科學(xué)出版社，2010：189-274.（SHI J Y. Distributed Parallel Rendering Technique and Its Application [M]. Beijing： Science Press， 2010： 189-274.）

[17]

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