改進的自適應特征細分方法及其對Catmull-Clark曲面的實時繪制

林金花,王延杰,孫宏海

(1.長春工業(yè)大學 應用技術學院,長春130012;2.中國科學院長春光學精密機械與物理研究所 機械電子工程系,長春130033;3.中國科學院大學 大衍學院,長春130033)

0 引 言

細分曲面自誕生以來已被廣泛應用于三維虛擬現(xiàn)實領域[1-4]。由于細分規(guī)則的計算方法較簡單,使得細分曲面表示方法的兼容性大大提高。盡管如此,細分表面點的計算需要耗費大量的時間和空間性能,限制了細分曲面技術的使用范圍。通用編程圖形處理芯片(GPGPU)的出現(xiàn)拓寬了細分曲面技術的使用范圍,這種參數(shù)化方法提高了細分繪制效率,但是當曲面結構復雜且曲面片規(guī)模較大的情況下,GPGPU的工作性能也隨之受到影響。Niessner等[5]于2012年提出了一種新的網格細分技術,從軟件方面克服了GPGPU的缺陷,直接GPU芯片上進行計算分析操作。然而這種方法以參數(shù)曲面的表示精度作為代價,繪制速度提高的同時,精度也隨之下降。自適應細分方法(FAS)的出現(xiàn)改變了現(xiàn)狀,僅對特征區(qū)域進行細分操作,既提高了細分性能,又保證了復雜曲面的繪制精度。FAS廣泛應用在三維動畫軟件和游戲制作領域,例如:OpenSubdiv,一種由皮克斯動畫工作室采納的開源新方案。

與傳統(tǒng)細分算法相比,FAS僅對不規(guī)則區(qū)域進行細分,不僅保留了不規(guī)則區(qū)域的拓撲特征,還提高了細分速度。然而,當不規(guī)則區(qū)域的數(shù)量大規(guī)模增加時,FAS算法的效率會隨指數(shù)降低,限制了算法的時間性能。

為了改善FAS方法的實時繪制速度,本文對FAS方法進行了改進,提出了一種動態(tài)的自適應特征細分算法,通過構造特征塊處理單元來動態(tài)地提取和細分不規(guī)則塊,實現(xiàn)不規(guī)則區(qū)域的不同細分深度的劃分,得到較少數(shù)量的細分塊,減少渲染塊的數(shù)量,提高繪制速度。此外,本文使用塊緩沖區(qū)來并行地處理所有細分層次產生的塊,提高了細分速度。

1 相關概念和理論

1.1 可編程圖形處理器

GPU是一種單指令流多數(shù)據流模式的并行圖形處理器。本文細分管線使用GPU繪制流程,對GPU進行編程,增加了兩個功能模塊:可編程頂點處理器和可編程塊處理器,如圖1所示。

圖1 可編程圖形流水線Fig.1 GPU rendering pipeline

GPU處理芯片僅對表面點操作,對于上級細分頂點的控制能力較弱。塊處理器彌補這點不足,直接在塊級上對幾何曲面進行計算和光柵化處理,從而可以充分地表現(xiàn)多邊形內部細節(jié)。

塊處理器負責執(zhí)行處理塊參數(shù)值的程序,對通過流水線的每一個塊都執(zhí)行一遍。頂點處理器的輸出緩沖區(qū)中的頂點參數(shù)經過插值后,生成塊參數(shù)傳遞給塊處理器的輸入緩沖區(qū),作為其輸入參數(shù)。程序執(zhí)行后,改變后的塊參數(shù)被寫入到塊處理器的輸出緩沖區(qū)中。本文算法的細分核心部分就是在塊處理器上實現(xiàn)的。

1.2 Catmull-Clark細分規(guī)則

Catmull-Clark細分模式[6]是一種傳統(tǒng)的細分曲面生成方法,通過網格計算規(guī)則來重復遞增地生成雙三次B樣條參數(shù)曲面。本文使用Catmull-Clark細分來初始化特征曲面片。Catmull-Clark細分模式如下所示:

(1)面點:每個面的4個頂點記為V1、V2、V3、V4,面點計算規(guī)則(見圖2(a))如下:

(2)邊點:首先將內部頂點記為V i、V j,此頂點的鄰接面分別記為F1和F2,邊點計算規(guī)則(見圖2(b))如下:

(3)頂點點:點V的鄰接點分為記為V1,V2,…,V2N,頂點點的計算規(guī)則(如圖2(c))如下:

圖2 Catmull-Clark細分規(guī)則Fig.2 Catmull-Clark subdivision rule

1.3 自適應特征細分(FAS)算法

FAS算法是Niessner等[7,8]提出的一種基于GPU的快速曲面繪制方法。該算法包括初始化階段、細分核心部分和分層繪制3個部分。各部分功能詳述如下:

(1)初始化階段。對初始曲面進行分析,定義自適應特征部分,抽取特征塊,生成塊內控制頂點集合。同時進入索引緩沖單元,用于存放數(shù)據,索引緩沖單元主要由信息塊和索引表構成。依據Catmull-Clark細分模式,得出每個層次的細分點的信息,同時存儲到細分表中,即:面點表、邊點表和頂點點表。

不同細分層次下的表面拓撲呈現(xiàn)出不同的網格連接結構,為了實現(xiàn)不同細分層次間曲面片的鏈接,FAS使用轉換塊來實現(xiàn),轉換塊由5種模板組成,分別對應不同細分層級間的表面結構,連接后的表面拓撲結構完整且無縫,如圖3所示。

圖3 FAS轉換塊模板Fig.3 FAS join_patch model

(2)細分核心部分。依據細分模板和細分初始網格模型,對不規(guī)則區(qū)域細分到各自不同的細分深度,得到曲面的關鍵控制頂點。再根據細分表中的內容,計算得出下級細分層次上的頂點數(shù)據,將其存儲到GPU緩存。每個不規(guī)則區(qū)域的細分層級是固定不變的。

(3)分層繪制。將前兩個部分得到的細分結果和表面模型數(shù)據作為本階段的輸入,經過細分后的表面模型,將其存放到對應的GPU存儲單元中。GPU處理器將存儲單元中的待細分數(shù)據完成細分操作,得到頂點和表面拓撲數(shù)據,并將其送入渲染器完成整體模型的繪制過程。

由此可見,FAS對網格模型的全部細分塊使用統(tǒng)一的細分深度,通常會出現(xiàn)GPU緩沖不夠或運行緩慢的現(xiàn)象。本文算法對FAS算法中的不規(guī)則區(qū)域設置了不同的細分深度,對于距離視點較遠且分辨率較低的區(qū)域使用較低的細分層級,簡化了細分計算,保證了模型繪制分辨率,同時提高了GPU繪制速度。

2 改進的算法架構

2.1 改進的數(shù)據結構

本文對傳統(tǒng)FAS算法的數(shù)據結構進行了擴充,如下所示:

(1)細分表結構

本文對FAS的細分表結構進行了改進,如圖4所示,不同的顏色線圈代表不同細分層級下的網絡點,這些網格點的位置信息存放在細分表中,同時為了保證GPU快速讀取這些頂點信息,本文將生成的二維表存放在GPU緩沖中,以便隨時讀入GPU繪制區(qū)域完成實時繪制。

圖4 特征圖(細分深度為3)Fig.4 Feature mapping(subdivision depth 3)

首先,使用Catmull-Clark模板生成曲面模型,存儲為面點表、邊點表和頂點點表,主要存放頂點和前一級別的關鍵點。其次,為所有的坐標點分配各自的編碼,構成細分表中的二元信息數(shù)據。最后,對GPU全局緩存進行實時更新操作,關鍵點被存入GPU的細分表。

改進的細分表結構如圖5所示[9]。與FAS的區(qū)別在于本文僅僅對GPU緩存中存放的少數(shù)關鍵點進行更新操作,并將其存儲在細分表中,節(jié)省了GPU的計算時間,同時減少了存儲單元的占用數(shù)量。

圖5 擴充的細分表Fig.5 Extended subdivision mapping

(2)渲染表

圖6 渲染塊(dv＝3)Fig.6 Rendering patch(depth＝3)

本文將待渲染的數(shù)據存放在渲染表中,主要包括奇異點周圍塊的細分層次dv、鄰接塊的拓撲信息和鄰接頂點的屬性值,FPU接收渲染表中數(shù)據,再送入GPU處理單元進行渲染處理,如圖6所示。換塊被分成3個三角形區(qū)域,不同的細分深、轉換塊具有不同的拓撲縮放,當達到細分因子規(guī)定的深度后,不規(guī)則區(qū)域的自適應細分結束,表示奇異點周圍的不規(guī)則區(qū)的拓撲結構已經到達最逼近真實渲染效果的程度,此時停止細分,將渲染表送入GPU,GPU開始對渲染表中的數(shù)據進行渲染繪制。圖7為渲染塊表緩沖區(qū)。

渲染表中的塊屬性包括特征塊、規(guī)則塊和不規(guī)則塊。特征塊通?？捎糜谶B接周圍塊的拓撲信息,即作為轉換塊出現(xiàn);規(guī)則塊是無需細分的塊;而不規(guī)則塊是本文自適應細分的對象,即要經過不同層級的細分,實現(xiàn)對奇異點區(qū)域的細分繪制。如圖6所示,紅色頂點表示奇異點,第3幅圖表示奇異點周圍塊已被細分3次,而不同細分層次間使用綠色的轉換塊實現(xiàn)塊間的無縫拼接,每個轉

圖7 渲染塊表緩沖區(qū)(dv＝3)Fig.7 Rendering patch table buffer(depth＝3)

2.2 細分因子

本文對FAS的細分因子進行了擴充,生成不規(guī)則塊的細分層次,進而控制奇異點周圍的不規(guī)則區(qū)域的自適應細分過程,下面依據不同的塊屬性,將細分因子生成方式進行了劃分:

(1)規(guī)則塊:使用GPU內部設置的細分層級。

(2)不規(guī)則塊:當不規(guī)則區(qū)域由n個頂點構成時,P＝{p1,p2,…,t,…,p n},t表示奇異點,P對應的特征圖表示為V(P)。k表示初始模型中不規(guī)則塊的頂點,P′＝k∪{P},將P′所對應的特征圖表示為V(P′)。當V(P′)包含t所屬的塊,即奇異點所屬特征塊與k所屬于特征塊之間的最小距離值與真實值相差α時,P的細分因子計算公式如下:

式中:V(t)為t所屬的特征塊的最短距離函數(shù);Area()為特征塊的面積值;,e表示周圍鄰居邊,m表示周圍邊的數(shù)量;表示特征塊的三維變化矩陣,如圖8所示[10,11]。

圖8 特征單元變換過程Fig.8 Feature unit space transformation

2.3 動態(tài)自適應特征細分

圖9 本文算法框圖Fig.9 Block diagram of proposed algorithm

本文算法通過對每個不規(guī)則塊單獨分配不同的細分深度來實現(xiàn)動態(tài)細分過程,進而減少細分產生的計算量。算法流程圖如圖9所示,包含3個模塊:①FPU-特征塊處理單元,用于計算塊的細分層次,并構建細分表;②由Catmall-Clark細分模板,對曲面進行細分,生成關鍵點;③使用GPU繪制渲染表中的不同屬性的塊。

第一階段:特征塊處理單元。由式(1)得到細分因子的確切值,對GPU的處理單元進行編碼,自動生成不同特征塊的各自細分層次。由初始網格模型計算得到的控制頂點數(shù)量作為輸入數(shù)據的索引信息傳送給FPU,FPU經過本文算法管線后得到3張表,分別為細分層次表、細分表和塊渲染表,執(zhí)行FPU的關鍵代碼,如下所示:

本文的FPU計算得到細分表,該細分表用于存儲即將進入GPU的細分頂點,同時存放這些頂點的特征圖,依據不同的頂點輸入將細分表分層3個表結構:面點區(qū)、邊點區(qū)和頂點點區(qū),如圖5所示。FPU同時構建渲染表,依據渲染塊的類型將其分為3個表:規(guī)則表、不規(guī)則表和轉換表。FPU依據細分表生成的細分深度l、塊的細分因子t和GPU緩沖信息繪制索引緩沖區(qū)的內容。

第二階段:細分。算法首先對初始網格進行全局掃描,計算得到全部需要細分的區(qū)域,然后使用Catmull-Clark細分模板和GPU塊處理單元對這些細分數(shù)據進行處理,得到每個細分層級上的頂點信息。本文算法對不規(guī)則區(qū)域周圍的奇異點進行自適應細分,得到不同拓撲結構的網絡表面數(shù)據,并將這些數(shù)據傳輸給GPU進行二次繪制渲染。

第三階段:塊繪制。使用改進的細分因子計算方法得到不同細分層次上的深度數(shù)據,實現(xiàn)對不規(guī)則區(qū)域的自適應細分。而對于規(guī)則塊和細分塊,本文采用FPU渲染管線來處理。GPU根據渲染表和細分表中的數(shù)據,對處理單元中的信息進行并行的光柵化操作,渲染輸出所有細分后生成的塊數(shù)據,實現(xiàn)對不規(guī)則區(qū)域的實時細分,提高塊的繪制精度[12,13]。

3 實驗分析

3.1 實驗的軟件與硬件環(huán)境

操作系統(tǒng)為Windows 8,開發(fā)語言為C＋＋,開發(fā)工具為Microsoft Visual C＋＋6.0,采用高級繪制語言,三維圖形編程接口Direct3D。CPU類型/主頻為INTEL Xeon E5/3.0 GHz,內存為8 Gbit。采用圖形處理器NVIDIA GTX 980,該圖形處理器有11條像素管線,支持OpenGL4.4/Direct X12。

3.2 性能分析

3.2.1 精確性(顯示精度)比較

建立初始控制網格(見圖10(a)),控制網格由四邊形網格組成,具有明顯折痕和尖點等不規(guī)則特性。圖10(b)為采用經典FAS方法對初始控制網格細分繪制之后的效果圖,圖10(c)為采用本文算法對初始控制網格繪制之后的效果圖。圖10(d)、(e)、(f)分別是對前3個效果圖取一個不規(guī)則區(qū)域(河馬背上的小鳥)放大之后的效果圖。由圖10(e)、(f)的局部放大效果圖可以看出,本文算法顯示精確性與FAS方法相近,無法用肉眼辨別出不同。傳統(tǒng)FAS方法使用相同的細分層次對表面模型的不規(guī)則區(qū)域進行細分,渲染輸出的精度較高,存在的弊端是對應每個塊計算相同的細分深度會增加GPU的計算時間,本文算法通過對經典FAS算法進行擴充,對奇異點周圍的不規(guī)則區(qū)域進行了不同層次的細分,能夠較完整地構建曲面模型的表面拓撲結構,同時降低了塊的細分和渲染時間,GPU的渲染精度也更加逼真。

圖10 本文算法與經典FAS算法的比較Fig.10 Proposed method compared with classical method

由圖10(e)、(f)的局部放大效果圖可以看出,本文算法顯示精確性與FAS方法相近,無法用肉眼辨別出不同。經典的FAS算法對初始控制網格的不規(guī)則塊使用統(tǒng)一的細分深度,繪制效果好,但塊計算量較大,本文算法通過對經典FAS算法進行擴充,對不同區(qū)域的不規(guī)則塊使用不同的細分深度,較好地保留了曲面模型的折痕等局部特征,塊計算量較小,繪制效果逼真。

3.2.2 實時性(繪制速度)比較

分別采用FAS算法和本文算法對圖11中的模型進行細分繪制繪制,并根據不規(guī)則塊的數(shù)量不同來比較兩種算法的繪制速度和細分速度,如表1所示。

圖11 復雜度不同的3種模型初始控制網格Fig.11 Primitive grid of three different models

表1 兩種算法繪制曲面模型速度的對比Table 1 Speed comparison of two algorithm with different models

分析表1中數(shù)據可以得出如下結論:

(1)與FAS方法不同,本文算法的細分階段包含了FPU的執(zhí)行時間,盡管如此,本文算法的細分速度仍比FAS算法快。

(2)選取4個具有不同復雜程度的初始網格模型,計算FAS算法與本文算法的速度差,曲面模型包含不規(guī)則塊或點越多,本文算法繪制細分曲面模型的速度越快。

3.2.3 繪制性能比較

采用本文算法與FAS算法在大規(guī)模地形場景上進行繪制性能比較,模型的四邊形面片數(shù)量為805 293個(見圖12)。在較密集特征塊下繪制同一種模型,本文算法繪制速度較快,即當細分密度越是增大時,本文算法繪制速度增快越明顯。圖13給出了兩種算法繪制該場景所需的總體繪制時間比較。本文算法能夠在場景網格上產生均勻的細分密度,適用于大規(guī)模場景的實時繪制。

圖12 本文算法對大規(guī)模地形場景的繪制Fig.12 Proposed algorithm applied to the rendering of large-scale terrain scene

圖13 兩種算法繪制大規(guī)模場景模型時間對比Fig.13 Time comparison of two algorithms for rendering large-scale scene

4 結束語

提出了一種基于GPU的動態(tài)自適應特征細分方法,能夠對表面特征較明顯的三維Catmull-Clark細分曲面模型進行實時繪制,并且通過引入新的細分因子計算方法,構建特征塊處理單元來改進FAS方法的過度細分問題。實驗生成的三維曲面模型顯示分辨率良好,繪制速度與傳統(tǒng)FAS方法相比提高了28%,能夠滿足三維虛擬環(huán)境的實時繪制需求。本文方法還可以應用于其他虛擬環(huán)境中的三維曲面模型的建立,例如Loop曲面模型的動態(tài)自適應繪制,對于用一般方法難于模擬的具有多不規(guī)則表面特征的曲面模型有較好的繪制實時性。

[1]Niessner M,Loop C,Meyer M.Feature-adaptive GPU rendering of Catmull-Clark subdivision surfaces[J].ACM Transactions on Graphics,2012,31(1):1-11.

[2]Doo D,Sabin M.Behaviour of recursive division surface near extraordinary points[J].Computer-Aided Design,1978,10(6):356-360.

[3]Loop C,Schaefer S.Approximating Catmull-Clark subdivision surfaces with bicubic patches[J].ACM Transactions on Graphics,2008,27(1):1-11.

[4]Stam J.Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values[C]∥Proceedings of SIGGRAPH,New York,NY,USA,1998:395-404.

[5]Niessner M,Loop C,Greiner G.Efficient evaluation of semi-smooth creases in Catmull-Clark subdivision surfaces[C]∥Eurographics Proceedings,Cagliari,2012:41-44.

[6]Catmull E,Clark J.Recursively generated B-spline surfaces on arbitrary topological meshes[J].Computer-aided Design,1978,10(6):350-355.

[7]Niesser M,Loop C.Analytic displacement mapping using hardware tessellation[J].ACM Transactions on Graphics,2013,32(3):1-9.

[8]Schafer H,Niessner M,Keinert B.State of the art report on real-time rendering with hardware tessellation[C]∥Eurographics,Strasbourg,France,2014:93-117.

[9]黃韻岑,馮潔青.表驅動的細分曲面GPU繪制[J].計算機輔助設計與圖形學學報,2014,26(10):1567-1575.Huang Yun-cen,Feng Jie-qing.Mapping driving subdivision surface upon GPU rendering[J].Journal of Computer-Aided Design&Computer Graphics,2014,26(10):1567-1575.

[10]Deng C,Ma W.A unified interpolatory subdivision scheme for quadrilateral meshes[J].ACM Transactions on Graphics,2013,32(3):1-10.

[11]李桂清.細分曲面造型及應用[D].北京:中國科學院計算技術研究所,2001.Li Gui-qing.The modeling and application method to subdivision surface[D].Beijing:Institute of Computer Technology,Chinese Academy of Sciences,2001.

[12]Schafer H,Keinert B,Niessner M.Local painting and deformation of meshes on the GPU[J].Computer Graphics Forum,2015,34(1):26-35.

[13]Yuan Ya-zhen,Wang Rui,Huang Jin.Simplified and tessellated mesh for realtime high quality rendering[J].Computer and Graphics,2016,54(10):135-144.