梁子

（四川大學計算機學院，成都 610065）

0 引言

計算機圖形學在電子游戲、虛擬現(xiàn)實、視覺仿真等領域應用廣泛，通過實時繪制系統(tǒng)的構建，完成不同領域的繪制需求。近年來，隨著這些領域的不斷發(fā)展，不同應用領域?qū)φ鎸嵏袖秩咎岢隽烁叩囊?，這使得實時繪制系統(tǒng)需要包含更為復雜的繪制算法以滿足上述需求，如全局光照、物理仿真等繪制算法。每種繪制算法將通過若干算法參數(shù)控制實時繪制系統(tǒng)的渲染效果，同時這些繪制參數(shù)也直接影響實時繪制系統(tǒng)的繪制效率。

本文在基于文獻[1]的基礎上，重點關注全局最優(yōu)劃分解決方案的確定。即：利用遺傳算法完成繪制特征空間的全局最優(yōu)劃分以及對應空間下性能瓶頸的識別。文獻[1]提出從繪制系統(tǒng)提供的大量繪制性能數(shù)據(jù)中挖掘信息，以自動識別繪制系統(tǒng)中的性能瓶頸。繪制性能數(shù)據(jù)是指：繪制系統(tǒng)中所有與繪制算法相關的算法參數(shù)其有效取值與對應繪制時間構成的數(shù)據(jù)集；性能瓶頸是指：參與挖掘分析的若干算法參數(shù)中，參數(shù)數(shù)值的微小變化導致系統(tǒng)繪制效率急劇下降的參數(shù)。在完成上述工作的同時，針對在整體數(shù)據(jù)空間下無法確定性能瓶頸的情況，進一步提出基于子空間劃分思想的方法，完成子空間下性能瓶頸的自動識別。

文獻[1]采用局部最優(yōu)的貪心算法完成子空間的劃分，即：以當前所在數(shù)據(jù)空間為基準，嘗試所有的劃分策略并選擇本次最優(yōu)的劃分方式。針對這種方式無法保證全局最優(yōu)的空間劃分，以及劃分結果不穩(wěn)定的缺點，本文提出基于遺傳算法的劃分方式以實現(xiàn)全局最優(yōu)劃分方式的確定，同時提高劃分結果的穩(wěn)定性。

1 算法實現(xiàn)

1.1 基本思想

空間劃分方式仍然建立在文獻[1]的基礎上，完成設定次數(shù)的隨機劃分方案，根據(jù)不同的劃分方案可以將數(shù)據(jù)空間進行不同的劃分得到劃分結果，某個劃分結果稱為“個體”，而將對應的劃分方案進行編碼得到該個體的“染色體”，染色體是唯一能夠確定個體的屬性，因此算法的操作都將關注于染色體，所有個體共同構成遺傳算法的“種群”。本文的基本思想是：通過優(yōu)勝劣汰的方式保留更適應生存的個體，同時，利用優(yōu)質(zhì)個體擁有的優(yōu)質(zhì)染色體，通過遺傳的方式完成更優(yōu)個體探索尋找，以此不斷迭代直到種群趨于收斂。本算法提出“適應度函數(shù)”（具體參見1.3.3）以完成對個體（即：空間劃分樹）對環(huán)境的適應度評估。

1.2 算法實現(xiàn)

不失一般性，我們在繪制系統(tǒng)R中采集得到當前繪制場景的性能數(shù)據(jù)集s，我們將利用該性能數(shù)據(jù)集S完成對當前繪制場景中性能瓶頸的識別工作，具體算法如下：

（1）根據(jù)完整性能數(shù)據(jù)集S建立評估模型F（本文采用隨機森林模型）；

（2）不失一般性，我們稱S集合的任意子集為Sk，利用F可以計算當前Sk數(shù)據(jù)空間中，參數(shù)集P中各個參數(shù)pi的變量重要性I(pi)；

（3）根據(jù)瓶頸判定機制（具體參見1.3.1）確定當前數(shù)據(jù)空間Sk下是否存在性能瓶頸，如果存在，停止Sk的劃分，輸出識別到的瓶頸集合，即計算得到的瓶頸集合就是當前數(shù)據(jù)空間Sk下識別到的瓶頸，否則，執(zhí)行步驟（4）；

（4）判斷Sk是否滿足繼續(xù)劃分的條件，如果滿足，執(zhí)行步驟（5），否則，停止Sk的劃分；

（5）針對當前數(shù)據(jù)空間Sk進行二分劃分（參見文獻[1]）：利用數(shù)據(jù)空間劃分機制（具體參見1.3.2）完成Sk的劃分，生成新的子空間，遍歷S分別執(zhí)行步驟（2）；

（6）遍歷步驟（2-5）劃分得到的數(shù)據(jù)空間二叉樹，進行染色體的編碼工作（具體參見1.3.4），并完成對該二叉樹（劃分結果）的個體適應度評估（具體參見1.3.3）；

（7）按照預設種群規(guī)模重復執(zhí)行步驟（2-6）得到N個個體共同構成遺傳算法的初始種群G0；

（8）完成種群Gi的選擇、交叉、變異算子（具體參見1.3.5），生成新的種群Gi+1，不斷迭代該步驟直到Gi、Gi+1的種群適應度（具體參見1.3.5）差距小于判定閾值，結束整個算法。

1.3 實現(xiàn)細節(jié)

（1）瓶頸判定機制

在數(shù)據(jù)空間Sk下，計算參數(shù)集P所有參數(shù)pi的變量重要性I(pi)，以其中的最大值為范圍上界將參數(shù)的變量重要性范圍進行三分，分為上中下三部分區(qū)域，如圖1（a）（b）所示，如果變量重要性落在上部分區(qū)域的參數(shù)個數(shù)小于等于設定閾值（閾值為2），同時，其余參數(shù)的變量重要性均落在下部分區(qū)域，則我們稱之為Sk數(shù)據(jù)空間下已經(jīng)識別到瓶頸。為了更清晰地描述問題，參見圖1（c）中落在上部區(qū)域的參數(shù)個數(shù)過多，（d）中落在中部區(qū)域的參數(shù)個數(shù)過多，因此（c）、（d）均沒有識別到瓶頸。

圖1 瓶頸判定示意圖

（2）數(shù)據(jù)空間劃分機制

本文基于參數(shù)變量重要性的啟發(fā)式方法完成種群的初始化工作。具體來說：I(pi)數(shù)值越高的參數(shù) pi應該在數(shù)據(jù)劃分過程中擁有更高的影響力，換言之，為了使得一個參數(shù)擁有更高的影響力，它就應該在被選擇成為空間劃分屬性時擁有更高的概率。

基于上述思想，我們使用如下策略完成針對某劃分空間二叉樹的一個非葉節(jié)點n（節(jié)點深度為d）其劃分屬性（參數(shù)）和劃分位置（參數(shù)數(shù)值）的確定：

①決定劃分參數(shù)

在某數(shù)據(jù)空間Sk下，計算參數(shù)集P所有參數(shù)pi的變量重要性I(pi)，之后，基于的輪盤賭策略將被采用以選擇劃分參數(shù)進行節(jié)點n的劃分。從該策略中可以看出：擁有更高I(pi)的參數(shù)將更有機會被選為劃分參數(shù)，但隨著劃分層數(shù)的加深，這種影響力將逐漸減弱，各個參數(shù)被選中的概率趨于一致。

②計算劃分位置

一旦劃分參數(shù)確定后，具體的劃分位置應該被確定成為該空間的劃分超平面（文獻[1]）?？紤]到當數(shù)據(jù)空間的規(guī)模減小到一定程度時，通過隨機森林計算得到的變量重要性I(pi)將變得不穩(wěn)定，因此本文方法傾向于將數(shù)據(jù)空間進行更為均衡的劃分，即：盡量不使兩個子空間中任何一個子空間的數(shù)據(jù)量過少。假設參數(shù)p的有效取值范圍是[pmin,pmax]，Ns個候選劃分位置由公式（1）生成，其中 i=1,2,...,N。s對于每個候選位置pican的劃分超平面，假設和是劃分后兩個子節(jié)點中數(shù)據(jù)的個數(shù)，候選位置的選取基于的正態(tài)分布原則。

（3）適應度評估

適應度函數(shù)在遺傳算法中起到至關重要的作用，它指導著種群的進化方向，如公式（2）所示，適應度函數(shù)F(·)描述數(shù)據(jù)空間S被劃分成n個子集S1,S2,...,Sn的好壞，即：某個空間劃分樹的適應程度。

其中f(Sk)是某個子空間的適應度函數(shù)，F(xiàn)(·)稱為劃分適應度函數(shù)。

本文遵循如下原則用來設計 f(Sk)：

圖2

圖2即使（a）（b）中沒有識別到瓶頸，我們認為情況（b）要優(yōu)于情況（a），因為（b）中紅色區(qū)域所標注的最大落差大于（a）中最大落差。

圖3

圖3即使（a）（b）中均識別到瓶頸，我們認為情況（b）要優(yōu)于情況（a），因為（b）中瓶頸個數(shù)小于（a）中瓶頸個數(shù)。

因此我們需要設計出滿足如下條件的函數(shù)：

①F(·)應該是一個連續(xù)性的函數(shù)以保證可以用來比較任何兩種劃分結果的好壞；

②變量重要性I(pi)的值應該影響 f(Sk)。具體包括兩個方面：（a）重要的參數(shù)（位于I(pi)上部分區(qū)域的參數(shù)）個數(shù)越少，f(Sk)值越高；（b）不重要參數(shù)（位于I(pi)下部分區(qū)域的參數(shù)）個數(shù)越多，f(Sk)值越高；

③劃分出的子空間總個數(shù)也應該被考慮，以保證不會將原始數(shù)據(jù)空間S劃分成過多的子區(qū)域；

基于上述三方面的考慮，f(Sk)可以由公式（3）表示：

其中f1(Sk),f2(Sk),f3(Sk)是影響f的三個不同的因子，公式（4）具體闡述了其具體計算公式：

其中，Nsig是落在上部區(qū)域的參數(shù)個數(shù)，Nmid表示中部區(qū)域的，Ntri表示下部區(qū)域的；Isaigvg是落在上部區(qū)域的參數(shù)其變量重要性的平均值，Itarvig表示下部區(qū)域的；|*|表示數(shù)據(jù)空間中數(shù)據(jù)量；而w1，w1，w1是控制三個分量的比重因子，由用戶指定。

（4）染色體編碼

遺傳算法要求所有的個體擁有一個統(tǒng)一格式的染色體編碼方式使得遺傳算子能夠順利地操作于不同的個體上。但由于我們有數(shù)量龐大的不同劃分方式來實現(xiàn)原始數(shù)據(jù)空間的劃分，同時，不同劃分結果所包含的子空間個數(shù)也不盡相同，這使得對空間劃分結果進行染色體編碼成為一件極富挑戰(zhàn)的工作。

受計算機圖形學領域廣泛應用的分層數(shù)據(jù)結構（如光線跟蹤技術中的KD-Tree[2]）的啟發(fā)，我們提出使用偽滿二叉樹表示任意維度的劃分過程以及劃分結果。其關鍵思想如下：

①采用二叉樹表示空間劃分的過程和結果；

②每個非葉節(jié)點n可以被認為隱式地生成分裂超平面，將數(shù)據(jù)集劃分為兩部分。節(jié)點n與參數(shù)pi∈P關聯(lián)并且生成的超平面與 pi對應的軸垂直。如圖4所示，節(jié)點n記錄一個信息對（pi,piv），其中 piv是參數(shù) pi軸上的一個有效取值；

③我們在該二叉樹中引入空節(jié)點進而將其轉(zhuǎn)化為偽滿二叉樹。如果所有的偽滿二叉樹被要求擁有相同的深度，則所有的劃分結果均可以被表示為一個統(tǒng)一的形式；

圖4 二叉樹表示數(shù)據(jù)劃分過程，與光線跟蹤技術中的KD-Tree相似

圖5 編碼后的染色體

所有位于偽滿二叉樹中的節(jié)點通過上述方式可被儲存在一維數(shù)組中。根節(jié)點的索引下標為0，節(jié)點索引下標為i時，其左右孩子節(jié)點將分別被儲存在下標為2i+1和2i+2，如圖5所示。最終該一維數(shù)組即為本文所述的染色體。

（5）遺傳算子

①選擇算子

該算子的目標是從本代種群中選擇優(yōu)質(zhì)個體以生成新子代個體。我們采用輪盤賭策略來完成選擇任務。具有較高適應性的候選個體具有更高被選擇的可能性用來培育新一代。

②交叉算子

為了產(chǎn)生新的子代個體，通過交叉算子，本代種群中的一對個體將作為父代進行交叉以產(chǎn)生新的子代個體，為了加速收斂，我們通過公式（5）計算交叉發(fā)生的概率 Pc，同時，一個隨機數(shù) t∈[0,1]生成，當 t＞Pc時，交叉操作應用于兩個選定的父代。

其中Fmax，F(xiàn)min分別是當前一代的最大和最小適應度，Icur和Imax分別是當前一代和最大一代的數(shù)量，是當前一代的適應度方差，F(xiàn)more是來自兩個選定的父候選解決方案的較大適應值，而Fless是另一個父親的適應值。公式（5）表明交叉的可能性受以下三個因素的影響：第一個因素是Pc在進化的早期階段會更大；第二，它與當前一代的適應度方差正相關；最后，Pc會隨著兩個父母之間的適應度差異的增加而增加。所有這些策略都旨在提高GA（遺傳算法種群）的收斂速度。

③變異算子

變異算子的目的是避免GA收斂到某些局部最優(yōu)解。它有助于維持人口的遺傳多樣性。在我們的工作中，我們將隨機選擇一些候選解決方案，并在一些隨機位置改變它們的染色體。

2 實驗結果

2.1 實驗環(huán)境

PC配置：Intel Core i7-6900k3.2GHz CPU，32G 內(nèi)存，NVIDIA GeForce GTX-1080顯卡；

場景配置：54011個三角面片的DiningRoom模型，分布有300個動態(tài)光源，25個透明物體。

參數(shù)空間說明：繪制系統(tǒng)基于延遲渲染框架，執(zhí)行Light-Linked-List（LLL）算法[3]產(chǎn)生大規(guī)模動態(tài)光源光照效果，執(zhí)行 Order-Independent-Transparency（OIT）算法[4]實現(xiàn)場景透明物體，執(zhí)行SSAO算法[5]基于屏幕空間優(yōu)化繪制效果。

本文算法中參數(shù)集P采用的參數(shù)列表：

表1

為了采集場景性能數(shù)據(jù)集，我們在場景中隨機漫游采集到150,000條數(shù)據(jù)構成整個性能數(shù)據(jù)集。

2.2 實驗結果

第一個實驗用來驗證使用本文提出的方法生成初始種群的有效性，種群規(guī)模為200個個體。圖6展示了隨著種群的不斷迭代，種群平均適應度的變化情況，其中藍色折線表示采用我們提出的方法進行初始種群的生成，橙色折線表示完全隨機的生成初始種群個體。圖中可以看出，利用本文的方法確實能夠提高初始準群的質(zhì)量進而進一步加速迭代的收斂；同時也證明了本文遺傳算法策略對于提高種群的適應度是有效的。

圖6

實驗二中，我們比較了本文方法與BAT方法[1]的結果。圖7（a）（b）分別展示了本文方法和BAT方法對于同一個場景處理的結果，由圖可知，由于我們的方法可以在任一局部數(shù)據(jù)空間中確定單個的瓶頸，因此具有更好的處理結果。同時，再次考慮劃分結果的適應度，本文方法所得到的最終結果其適應度分數(shù)為0.86262，要高于BAT方法得到的得分0.771819。

圖7

3 結語

本文提出一種復雜繪制系統(tǒng)算法級別的性能瓶頸識別方法，針對復雜性更高的繪制系統(tǒng)越有可能出現(xiàn)不存在全局瓶頸的情況，進一步改進了繪制數(shù)據(jù)空間劃分的算法，提出利用遺傳算法進行全劇最優(yōu)的數(shù)據(jù)空間劃分算法，旨在合理劃分全局數(shù)據(jù)空間到不同子空間，使得在各個子空間中識別到局部性能瓶頸。