本發(fā)明涉及圖形渲染技術(shù)領(lǐng)域，尤其涉及一種自動生成網(wǎng)格與著色器多層次細節(jié)的方法。

背景技術(shù)：

在各種計算機圖形應用中，實時渲染出復雜而真實模型的問題都是非常受關(guān)注的。然而，就算以當前最新的圖形硬件配置來看，模型本身復雜程度的增長仍然比硬件渲染能力的提升要快很多。這種壓力催生了很多平衡模型復雜度與渲染效率的研究。多層次細節(jié)(Level-of-detail,LOD)就是其中被使用得非常廣泛的一種技術(shù)。

多層次細節(jié)的基本思想就是使用一些簡化表示代替遠處較小的模型或者模型的不重要部分。目前已經(jīng)在不同方面有各種表示方法被研究出來。Luebke在2003年提出基于網(wǎng)格簡化方法的幾何層面多層次細節(jié)技術(shù)，并催生了許多相關(guān)的優(yōu)秀算法。隨著圖形處理單元(Graphics Process Unit,GPU)的發(fā)展，很多相關(guān)應用都廣泛使用著色器技術(shù)來加強模型顯示的保真度。迎合這個趨勢的發(fā)展，近來的一些工作，比如Olano、He等人研究的自動生成簡化著色器多層次細節(jié)的方法，以及在各距離下平衡渲染效率與質(zhì)量的技術(shù)也正在開展。但是這些研究都沒有考慮同時簡化網(wǎng)格與著色器。

技術(shù)實現(xiàn)要素：

針對現(xiàn)有技術(shù)的不足，本發(fā)明提供了一種自動生成網(wǎng)格與著色器多層次細節(jié)的方法。

一種自動生成網(wǎng)格與著色器多層次細節(jié)的方法，包括：

1)使用基于表面信號擬合的著色器自動簡化方法，對原始渲染程序進行簡化，得到一系列簡化渲染程序；

2)使用原始渲染程序來進行渲染，基于圖像空間的偏差，對原始網(wǎng)格進行簡化，得到一系列不同簡化程度的簡化網(wǎng)格；

3)在輸入的最近與最遠距離之間插入n個距離值，在各距離上搜索所有的簡化渲染程序與簡化網(wǎng)格，從中找到渲染效率最高的一對網(wǎng)格與渲染程序，作為當前距離的層次細節(jié)結(jié)果，并按距離增序排列組織成多層次細節(jié)；所述的n個距離值呈非均勻分布，保證在距離從小到大排列時，網(wǎng)格繪制并呈現(xiàn)在屏幕上的像素個數(shù)是等比減少的。

4)在多層次細節(jié)中超出過渡偏差閾值的相鄰層次間插入新的層次細節(jié)，加入多層次細節(jié)中，再對其中小于過渡偏差閾值的相鄰層次進行合并，得到最終的多層次細節(jié)結(jié)果。

本發(fā)明中所述的渲染程序是指進行渲染時輸入的著色器代碼。本發(fā)明中所述的原始渲染程序中僅包括頂點著色器和像素著色器，且各著色器代碼都是使用HLSL語言編寫的。

本發(fā)明中原始網(wǎng)格、簡化網(wǎng)格都是用OBJ格式編碼的模型信息，為簡化方法提供模型的頂點以及面數(shù)據(jù)，簡化后的模型依然使用OBJ格式編碼并保存，用于渲染。

本發(fā)明中的每個層次細節(jié)，包括一個網(wǎng)格與相機的距離值，一個簡化網(wǎng)格，以及一個被用于渲染該網(wǎng)格的簡化渲染程序。

本發(fā)明中的圖像空間的偏差，是指給定的兩張圖片逐像素顏色的歐氏距離之和，在本發(fā)明中所有圖像偏差都默認是在多個視角計算并取平均值的結(jié)果，視角根據(jù)用戶設定可以是六個或者十二個，前者是將網(wǎng)格放置在正方體中心位置，分別從六個面的中心點觀察正方體中心所得到的六個觀察視角，而后者是將網(wǎng)格放置在正二十面體的中心，分別從十二個頂點觀察正二十面體中心所得到的十二個觀察視角。

本發(fā)明所述的步驟1)包括如下步驟：

1-1)將輸入的原始渲染程序的代碼轉(zhuǎn)換成抽象語法樹與程序依賴圖；

1-2)根據(jù)程序依賴圖，在抽象語法樹上對著色器的所有計算操作綜合應用三條簡化規(guī)則，分別是操作移除，代碼移動以及移動到參數(shù)，得到一系列簡化后著色器的抽象語法樹，輸出它們各自的渲染程序代碼；

1-3)在輸入的最近距離下使用步驟1-2)輸出的所有簡化渲染程序渲染原始網(wǎng)格，得到它們的渲染效率與圖像偏差，根據(jù)渲染效率和圖像偏差選擇所有滿足帕累托最優(yōu)的簡化渲染程序；

1-4)在輸入的最遠距離下使用步驟1-2)輸出的所有簡化渲染程序渲染原始網(wǎng)格，得到它們的渲染效率與圖像偏差，根據(jù)渲染效率和圖像偏差選擇所有滿足帕累托最優(yōu)的簡化渲染程序；

1-5)求1-3)與1-4)中得到的簡化渲染程序的并集，結(jié)果即最優(yōu)的一系列簡化渲染程序。

步驟1-2)中所述的操作移除規(guī)則是指刪除某次計算操作，比如刪除a＝a+b計算中的加法以加速計算；代碼移動規(guī)則是指將原來位于像素著色器中的計算代碼移動到頂點著色器或者細分著色器中，以減少該代碼的運行次數(shù)；移動到參數(shù)規(guī)則是指將原來在像素著色器中計算的變量值擬合成常量值存儲在CPU端，在渲染時直接將其作為參數(shù)傳入以減少計算。

本發(fā)明所述的步驟2)包括如下步驟：

2-1)使用原始渲染程序渲染原始網(wǎng)格得到原始圖片I_o，并使用原始圖片作為當前圖片I_c；

2-2)對原始網(wǎng)格的每一條邊，使用原始渲染程序渲染并計算該邊簡化后與簡化前相比的圖像偏差增量，并將其放入以該增量為排序依據(jù)升序排列的優(yōu)先隊列Q中；

2-3)根據(jù)需要采樣的簡化網(wǎng)格個數(shù)，原始面片數(shù)以及目標面片數(shù)，求出面片數(shù)步進s；

2-4)拋出優(yōu)先隊列Q中的第一條邊并簡化，同時更新該邊周圍受影響的所有邊的圖像偏差增量，重新按序放到優(yōu)先隊列Q中，并更新當前圖片I_c，每當簡化面片數(shù)達到步進s即輸出一個簡化網(wǎng)格；

2-5)重復步驟2-4)直至當前網(wǎng)格面片數(shù)少于目標面片數(shù)。

步驟2-3)中所述的需要采樣的簡化網(wǎng)格個數(shù)是指，在本次多層次細節(jié)生成時，需要采樣多少個簡化網(wǎng)格樣本代表所有可能的簡化網(wǎng)格。

步驟2-1)中所述的邊簡化后與簡化前相比的圖像偏差增量的計算按如下步驟進行：

a1)求出在網(wǎng)格上，與該邊的任意頂點相接的所有面{F}，再求出與{F}所有頂點相接的邊{E}，使用{E}的所有頂點所在的屏幕空間包圍盒H作為受該邊簡化影響的屏幕像素范圍；

a2)使用原始渲染程序渲染網(wǎng)格所有在H中或者與H有重疊部分的面片，得到簡化圖片I_e；

a3)使用計算著色器分別計算在H所包含的像素范圍內(nèi)，I_e與I_o的圖像空間偏差e以及I_c與I_o的圖像空間偏差e’，e與e’的差即為該邊的圖像偏差增量。

本發(fā)明中所述的步驟3)中距離值呈指數(shù)分布，保證在距離從小到大排列時，網(wǎng)格繪制并呈現(xiàn)在屏幕上的像素個數(shù)是等比減少的，距離公式為：

其中i表示第幾個距離值，d_min與d_max分別為輸入的網(wǎng)格與相機間的最近和最遠距離，l表示插入后距離值的總個數(shù)，包括最近與最遠距離。

本發(fā)明所述的步驟3)通過以下步驟找到指定距離下渲染效率最高的一對網(wǎng)格與渲染程序：

b1)計算當前距離下的圖像偏差閾值E，并按引入的圖像偏差大小升序分別排列簡化網(wǎng)格與簡化渲染程序；

b2)從最后一個簡化網(wǎng)格開始逐步往前遞進，使用原始渲染程序渲染途經(jīng)的每一個簡化網(wǎng)格，直到找到第一個在閾值E內(nèi)的簡化網(wǎng)格，將該網(wǎng)格-渲染程序?qū)ψ鳛楫斍敖Y(jié)果S，測量該組合在多個視角下的平均渲染時間t_min；

b3)從上一次選中的簡化網(wǎng)格開始繼續(xù)往前遞進，使用下一個簡化渲染程序渲染途經(jīng)的每一個簡化網(wǎng)格，直到找到第一個在閾值E內(nèi)的簡化網(wǎng)格，測量該網(wǎng)格-渲染程序?qū)υ诙鄠€視角下的平均渲染時間t，若t小于t_min則將t_min值改為t，并將當前結(jié)果S改為本次選出的網(wǎng)格-渲染程序?qū)Γ?/p>

b4)重復步驟b3)直到遍歷所有簡化渲染程序或者簡化網(wǎng)格，最終S即為該距離下渲染效率最高的一對網(wǎng)格與渲染程序。

步驟b1)中所述的當前距離下的圖像偏差閾值是指，使用簡化網(wǎng)格及簡化渲染程序允許產(chǎn)生的最大圖像偏差值，其計算公式為：

其中d為當前距離，d_min與d_max分別為輸入的最近與最遠距離，Q為輸入的質(zhì)量系數(shù)，范圍是0到1，max_error為輸入的在距離d_max下的最大圖像偏差閾值。

設簡化網(wǎng)格數(shù)量為M，簡化渲染程序數(shù)量為N，如果不使用線性搜索的方法，則需要遍歷所有簡化網(wǎng)格與簡化渲染程序的組合，時間消耗為O(MN)，而使用如上線性搜索的方法，消耗的時間是O(M+N)，因為線性搜索的方法每次僅在簡化網(wǎng)格序列中往前步進1，或者在簡化渲染程序序列中往后步進1，所以只需要線性的時間消耗，故使用線性搜索能夠大大加快尋找最優(yōu)網(wǎng)格與渲染程序?qū)Φ男?。由于對任意渲染程序，網(wǎng)格面片數(shù)越少，渲染效率越高，而線性搜索的方法保證遍歷了每個簡化渲染程序使用其圖像偏差閾值內(nèi)最簡化的網(wǎng)格的情況，所以也保證了線性搜索方法的正確性。

本發(fā)明所述的步驟4)包括以下步驟：

4-1)插入新的層次細節(jié)。

從最近的層次細節(jié)開始到最遠的層次細節(jié)，為每個層次細節(jié)P_i計算與下一層P_i+1之間的過渡偏差值，如果超過了在P_i+1的距離d_i+1下求出的過渡偏差閾值，那么就在P_i與P_i+1之間插入一個距離值，使得插入距離值后，所述的n個距離值呈非均勻分布，且保證在距離從小到大排列時，網(wǎng)格繪制并呈現(xiàn)在屏幕上的像素個數(shù)是等比減少；并按b1)到b4)所述步驟得到該距離下的網(wǎng)格-渲染程序?qū)Γ瑢⑵渥鳛樾碌膶哟渭毠?jié)插入多層次細節(jié)中；

4-2)合并多余的層次細節(jié)。

從最近的層次細節(jié)開始到最遠的層次細節(jié)，為每個層次細節(jié)P_i計算與其后第二層P_i+2的過渡偏差值，如果小于在P_i+2的距離d_i+2下求出的過渡偏差閾值，那么就在多層次細節(jié)中將層次P_i+1刪除，即表示將層次P_i+1往層次P_i+2合并；

4-3)從最近的層次細節(jié)開始到最遠的層次細節(jié)，輸出每一個層次細節(jié)的距離、簡化網(wǎng)格以及簡化渲染程序的代碼。

步驟4-1)到步驟4-3)中所述的過渡偏差值是指，將兩層次的網(wǎng)格均放置在兩層次中較遠的距離上，分別使用各自的渲染程序渲染，并計算它們的圖像偏差所得到的值。而過渡偏差閾值則是指允許兩層次之間的最大過渡偏差值，過渡偏差閾值的計算公式為：

其中Q′為輸入的過渡質(zhì)量系數(shù)，max_bound為輸入的在距離d_max下的最大過渡偏差閾值。

與現(xiàn)有技術(shù)相比，本發(fā)明的優(yōu)點在于：

a)提出了一種新的多分辨率下的模型表示，即簡化網(wǎng)格與簡化渲染程序的組合表示，相比單純的網(wǎng)格或者著色器簡化方法，本發(fā)明可以在各分辨率下平衡渲染效率的瓶頸，在產(chǎn)生相同圖像偏差的基礎(chǔ)上最大化渲染效率；

b)可以根據(jù)不同需要在渲染效率與質(zhì)量之間做權(quán)衡，自動生成過渡平滑的多層次細節(jié)；

c)簡化網(wǎng)格及著色器的效率高，而且提出并使用了線性搜索的方法，大大加速了在每個層次細節(jié)找出最優(yōu)簡化網(wǎng)格及渲染程序組合的過程，多層次細節(jié)生成效率更高，質(zhì)量更好。

附圖說明

圖1為本實施例自動生成網(wǎng)格與著色器多層次細節(jié)方法的總體流程圖；

圖2為本實施例在多個距離上生成層次細節(jié)的子流程圖；

圖3為本實施例在指定距離上計算層次細節(jié)結(jié)果的子流程圖；

圖4為本實施例對多層次細節(jié)結(jié)果進行插入與合并的子流程圖。

具體實施方式

下面將結(jié)合具體實施例和附圖對本發(fā)明進行詳細說明。

一種自動生成網(wǎng)格與著色器多層次細節(jié)的方法，如圖1總體流程圖所示，包括：

1)使用基于表面信號擬合的著色器自動簡化方法，對原始渲染程序S_o進行簡化，得到80個最優(yōu)的簡化渲染程序{S}，步驟如下；

1-1)將輸入的原始渲染程序S_o的代碼轉(zhuǎn)換成抽象語法樹T與程序依賴圖G；

1-2)根據(jù)程序依賴圖G，在抽象語法樹T上對著色器的所有計算操作綜合應用三條簡化規(guī)則，分別是操作移除，代碼移動以及移動到參數(shù)，得到2000個簡化后著色器的抽象語法樹，輸出成各簡化渲染程序的代碼{S_s}；

1-3)在最近距離d_min下使用{S_s}中所有渲染程序渲染原始網(wǎng)格，得到它們的渲染效率與圖像偏差，根據(jù)渲染效率和圖像偏差選擇所有滿足帕累托最優(yōu)的簡化渲染程序{S_near}有50個；

1-4)在最遠距離d_max下使用{S_s}中所有渲染程序渲染原始網(wǎng)格，得到它們的渲染效率與圖像偏差，根據(jù)渲染效率和圖像偏差選擇所有滿足帕累托最優(yōu)的簡化渲染程序；{S_far}有40個；

1-5)計算{S_near}與{S_far}的并集即得最優(yōu)的80個簡化渲染程序{S}。

2)使用原始渲染程序S_o來進行渲染，基于圖像空間的偏差，對原始網(wǎng)格M_o進行簡化，從原始的20000個面片簡化到1000個面片，并采樣簡化過程中的1000個簡化網(wǎng)格{M}，表示用這些樣本代表所有可能的簡化網(wǎng)格，其步驟包括：

2-1)使用原始渲染程序渲染原始網(wǎng)格得到原始圖片I_o，并使用原始圖片作為當前圖片I_c；

2-2)對原始網(wǎng)格M_o的每一條邊，使用原始渲染程序S_o渲染并計算該邊簡化后與簡化前相比的圖像偏差增量e_i，并將其放入優(yōu)先隊列Q中，Q以圖像偏差增量升序排列；

2-3)根據(jù)需要采樣的簡化網(wǎng)格個數(shù)1000，M_o面片數(shù)20000，以及目標面片數(shù)1000，計算面片數(shù)步進s＝(20000-1000)/1000＝19，表示每簡化掉19個面片即輸出當前簡化網(wǎng)格到{M}中，將累計簡化面片數(shù)Acc賦為0；

2-4)拋出優(yōu)先隊列Q中的第一條邊并簡化，同時更新該邊周圍受影響的所有邊的圖像偏差增量，重新按序放到優(yōu)先隊列Q中，并更新當前圖片I_c，設本次簡化掉的面片數(shù)為c_i，Acc＝Acc+c_i，如果Acc大于步進19，則輸出當前簡化網(wǎng)格M_i到{M}，且Acc＝Acc-19；

2-5)重復步驟2-4)直至當前網(wǎng)格面片數(shù)少于或等于目標面片數(shù)1000。

在步驟2-1)中圖像偏差增量e_i的計算按如下步驟進行：

a1)求出在網(wǎng)格上，與該邊的任意頂點相接的所有面{F}，再求出與{F}所有頂點相接的邊{E}，使用{E}的所有頂點所在的屏幕空間包圍盒H作為受該邊簡化影響的屏幕像素范圍；

a2)使用原始渲染程序S_o渲染M_o所有在H中或者與H有重疊部分的面片，得到簡化圖片I_e；

a3)使用計算著色器分別計算在H所包含的像素范圍內(nèi)，I_e與I_o的圖像空間偏差e'₀以及I_c與I_o的圖像空間偏差e’₁，e'₀與e’₁的差即為該邊的圖像偏差增量e_i。

3)在輸入的最近與最遠距離間生成8個層次細節(jié){P}，如圖2子流程1所示，其步驟包括：

3-1)在最近距離d_min＝1.7與最遠距離d_max＝20間設置8個距離值xv3r9jzsqg，距離公式為：

其中i表示第幾個距離值，l表示距離值的個數(shù)8(包括最近與最遠距離)；

3-2)在xv3r9jzsqg中的每一個距離d_i下，求取渲染效率最高的一對簡化網(wǎng)格與簡化渲染程序。

步驟3-2)通過以下步驟使用找到指定距離下渲染效率最高的一對網(wǎng)格與渲染程序，如圖3子流程2所示：

b1)計算當前距離d_i下的圖像偏差閾值E_i，并按引入的圖像偏差大小分別升序排列1000個簡化網(wǎng)格{M}與80個簡化渲染程序{S}；

b2)從{M}中最后一個簡化網(wǎng)格M₉₉₉開始逐步往前遞進，使用原始渲染程序S_o渲染途經(jīng)的每一個簡化網(wǎng)格，直到找到第一個在閾值e內(nèi)的簡化網(wǎng)格M_k，將該網(wǎng)格M_k與渲染程序S_o對作為當前結(jié)果S，測量該組合在多個視角下的平均渲染時間t_min；

b3)從上一次選中的簡化網(wǎng)格開始繼續(xù)往前遞進，使用下一個簡化渲染程序渲染途經(jīng)的每一個簡化網(wǎng)格，直到找到第一個在閾值E_i內(nèi)的簡化網(wǎng)格，測量該網(wǎng)格-渲染程序?qū)υ诙鄠€視角下的平均渲染時間t，若t小于t_min則將t_min值改為t，并將當前結(jié)果S改為本次選出的網(wǎng)格-渲染程序?qū)Γ?/p>

b4)重復b3)直到遍歷所有簡化渲染程序或所有簡化網(wǎng)格，最終S即為距離d_i下渲染效率最高的一對網(wǎng)格與渲染程序。

在步驟b1)中所述的當前距離的圖像偏差閾值是指，使用簡化網(wǎng)格及簡化渲染程序允許產(chǎn)生的最大圖像偏差值，其計算公式為：

其中d為當前距離，為輸入的簡化質(zhì)量系數(shù)，范圍是0到1，max_error為輸入的在距離d_max下的最大圖像偏差閾值。

4)在{P}中過渡不夠平滑的相鄰層次間插入新層次，并合并多余的層次細節(jié)，如圖4子流程3所示，其步驟包括：

4-1)將8個層次細節(jié){P}按距離大小升序排列，{P’}為插入的新層次細節(jié)集合，初始值為空集；

4-2)從P₀開始，在{P}中為每個層次細節(jié)P_i計算與下一層P_i+1之間的過渡偏差值，如果超過了在P_i+1的距離d_i+1下求出的過渡偏差閾值，那么就在P_i與P_i+1之間插入一個距離值，使得插入距離值后，所述的n個距離值呈非均勻分布，且保證在距離從小到大排列時，網(wǎng)格繪制并呈現(xiàn)在屏幕上的像素個數(shù)是等比減少；并按b1)到b4)所述步驟得到該距離下的網(wǎng)格-渲染程序?qū)Γ瑢⑵渥鳛樾碌膶哟渭毠?jié)加入{P’}；

4-3)將{P’}中的層次細節(jié)按距離大小升序插入到{P}中，插入后共有12個層次細節(jié)；

4-4)從P₀開始，為{P}中每個層次細節(jié)P_i計算與其后第二層P_i+2的過渡偏差值，如果小于在P_i+2的距離d_i+2下求出的過渡偏差閾值，那么就在{P}中將層次P_i+1刪除，即表示將層次P_i+1往層次P_i+2合并；

4-5)合并完成后{P}中最終有5個層次細節(jié)，從頭至尾輸出每一個層次細節(jié)的距離、簡化網(wǎng)格以及簡化渲染程序。

步驟4-1)到步驟4-4)中所述的過渡偏差值是指將兩層次的網(wǎng)格均放置在兩層次中較遠的距離上，分別使用各自的渲染程序渲染，并計算它們在圖像空間的偏差所得到的值。而過渡偏差閾值則是指允許兩層次之間的最大過渡偏差值，過渡偏差閾值的計算公式為：

其中Q′為輸入的過渡質(zhì)量系數(shù)，max_bound為輸入的在距離d_max下的最大過渡偏差閾值。