基于Shader 的CSG 幾何體的實(shí)時(shí)渲染*

陳國軍 尹 鵬 裴利強(qiáng) 尹 沖

（中國石油大學(xué)（華東）計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 青島 266580）

1 引言

隨著計(jì)算機(jī)圖形應(yīng)用的發(fā)展，布爾運(yùn)算在建模系統(tǒng)中扮演了關(guān)鍵的角色［1］。經(jīng)過數(shù)十年的研究和發(fā)展，二維圖形和三維實(shí)體布爾運(yùn)算已經(jīng)成為了計(jì)算機(jī)圖形學(xué)方面非常熱門的研究方向之一［2］。布爾運(yùn)算是通過對(duì)兩個(gè)以上的物體進(jìn)行并集、差集、交集的運(yùn)算，從而得到新的物體［3～4］。其運(yùn)算方式有并集、交集和差集。目前基于物體空間的布爾運(yùn)算算法已有相當(dāng)?shù)难芯砍晒８鶕?jù)維度布爾運(yùn)算分成二維布爾運(yùn)算和三維布爾運(yùn)算［5～6］。

二維布爾運(yùn)算方法大多將幾何體看成一個(gè)或多個(gè)環(huán)的組合。Feito and Rivero 將復(fù)雜多邊形分解為多個(gè)三角形的組合，采用簡單塊鏈表達(dá)每一個(gè)多邊形，但是涉及到奇異情況時(shí)，算法無法保證布爾運(yùn)算系統(tǒng)的穩(wěn)定性［7］。目前三維布爾運(yùn)算主要通過構(gòu)造實(shí)體幾何（CSG）的方式完成布爾運(yùn)算。構(gòu)造實(shí)體幾何（CSG）的基本思想是通過對(duì)基本圖元如球、圓柱體、立方體等進(jìn)行剛性變換和布爾運(yùn)算生成復(fù)雜的模型［8～9］。Jansen 等提出了模型的陰影計(jì)算算法，他對(duì)每一個(gè)CSG體元相對(duì)CSG樹生成一個(gè)陰影樹，而整體CSG構(gòu)造的物體產(chǎn)生的陰影則是整個(gè)陰影樹的并集，這樣可以使由CSG構(gòu)造方法生成的三維物體在虛擬環(huán)境中更加真實(shí)［10］。V.S.Alagar 等提出了作為應(yīng)用最為廣泛的CSG 樹實(shí)體建模法在CAD 系統(tǒng)中的重要性，并且表述了利用CSG 樹的方法來構(gòu)建實(shí)體模型的方法［11］。但由于表示受體素的種類和對(duì)體素操作的種類的限制，使得它表示形體的覆蓋域有較大的局限性，穩(wěn)定性較差。OpenCSG 是目前使用最為廣泛的基于圖像CSG的庫，CSG使用OpenGL渲染［1，9］。

綜上所述，目前幾何圖形布爾運(yùn)算在判斷兩幾何體相交或者重合的臨界交點(diǎn)上容易出現(xiàn)誤差，計(jì)算穩(wěn)定性較差；當(dāng)數(shù)據(jù)量較大時(shí)，頂點(diǎn)或者三角片數(shù)據(jù)龐大，會(huì)使得運(yùn)算的計(jì)算效率降低［12］。針對(duì)以上問題，提出基于Shader 的CSG 幾何體的實(shí)時(shí)渲染，利用GPU 的并行運(yùn)算能力［13～14］，通過Shader 著色器處理待渲染數(shù)據(jù)。在三維運(yùn)算過程中使用CSG 基元模型進(jìn)行布爾運(yùn)算，稱之為Shader-CSG算法，可以有效解決布爾運(yùn)算渲染過程出現(xiàn)的穩(wěn)定性和實(shí)時(shí)性問題。

2 布爾運(yùn)算基元建模

2.1 基元模型構(gòu)建

CSG 的基元模型為球體、立方體、圓柱體等相對(duì)規(guī)則的形體。首先通過對(duì)基元模型設(shè)立通用參數(shù)來控制體元的位置、大小等屬性，改變其參數(shù)可以得到基元模型的各種尺寸方向的效果。然后通過離散化，以密集三角片逼近模型的表面。

1）參數(shù)化建模

模型參數(shù)為centerPos（中心點(diǎn)坐標(biāo)）。變換參數(shù)為length（長度）、angle（旋轉(zhuǎn)角）、radius（半徑）、height（高度）。

2）離散化

對(duì)于立方體，其六個(gè)表面分別由兩個(gè)大小相同的三角片組成。圓柱體曲面部分是通過對(duì)圓柱底面的圓進(jìn)行“分片（slices）”，每片都為角度相同的扇形，然后連接底面與頂面扇形，側(cè)面為長方形，分成兩個(gè)三角片。

球體曲面建立是通過對(duì)球體沿著Z 坐標(biāo)軸旋轉(zhuǎn)“分片（slices）”，在每片上再進(jìn)行“分塊（stacks）”。如圖1 所示，分別展示了圓柱體底面分片和球體分片、分區(qū)的過程。

圖1 基元模型離散化示意圖

每個(gè)三維模型表面都通過密集的三角片進(jìn)行逼近，并且保證基元模型在每個(gè)二維坐標(biāo)系下的投影都是規(guī)范圖形，使得在考慮誤差時(shí)可以通過數(shù)學(xué)計(jì)算減小誤差。

2.2 基元模型中點(diǎn)與幾何體位置關(guān)系判斷

對(duì)于三維幾何體，當(dāng)基元模型為立方體時(shí)，設(shè)立方體X、Y、Z 坐標(biāo)系中的最大值和最小值分別為maxX、maxY、maxZ 和minX、minY、minZ。對(duì)于任意空間一點(diǎn)P（x，y），滿足點(diǎn)P在立方體內(nèi)部或表面的條件為

圖2 點(diǎn)與曲面體位置關(guān)系判斷圖

聯(lián)立方程（2）和方程（3），即可求出點(diǎn)解出x，y，z，得到交點(diǎn)V（x，y，z），通過比較VO與PO的長度：

由線段長度比較得到該點(diǎn)所在的位置：

3 CSG幾何體的渲染

要實(shí)現(xiàn)CSG相對(duì)應(yīng)幾何體的渲染，首先要解析CSG 樹，形成一個(gè)可判斷的邏輯公式［15］，然后將解析結(jié)果傳遞到Shader（著色器）中，實(shí)現(xiàn)實(shí)時(shí)繪制。

3.1 布爾運(yùn)算表達(dá)式解析

解析布爾運(yùn)算表達(dá)式的基礎(chǔ)是解析兩個(gè)布爾基元的運(yùn)算。首先針對(duì)立方體、球體、圓柱體這三種布爾運(yùn)算基元，定義S1、S2、S3 分別為空間任一點(diǎn)與立方體、球體、圓柱體的位置關(guān)系值。例如球體，當(dāng)S2=0 時(shí)，指該點(diǎn)在球體內(nèi)部；當(dāng)S2=1 時(shí)，指該點(diǎn)在球體表面；當(dāng)S2=2 時(shí)，指該點(diǎn)在球體外部。將這種關(guān)系與式（5）結(jié)合，點(diǎn)與球體關(guān)系如式（6）所示：

當(dāng)出現(xiàn)兩個(gè)基元布爾運(yùn)算時(shí)，比如立方體與球體，其交、并、差的表達(dá)式可以解析邏輯表達(dá)式。邏輯式（7）、（8）、（9）分別表示了立方體與球體的交、并、差運(yùn)算。

布爾表達(dá)式中運(yùn)算符，按照優(yōu)先級(jí)分為括號(hào)和邏輯運(yùn)算符。邏輯運(yùn)算符交、并、差即可表示成”∧”、”∨”、”?”的形式。布爾運(yùn)算文法如下：

布爾表達(dá)式的解析類似算術(shù)表達(dá)式解析，其三中邏輯運(yùn)算可以做以下等價(jià)解釋：

對(duì)于布爾運(yùn)算表達(dá)式“Q=A∩B-C”，設(shè)A、B、C 分別代指立方體、球體和圓柱體，S1、S2、S3 分別代表空間任一點(diǎn)與立方體、球體、圓柱體的位置關(guān)系值。通過式（7）、（8）、（9）其表達(dá)式可翻譯為“Q=S1 ＜2 ∧S2 ＜2 ∧S3 ≥1”，設(shè)該表達(dá)式有兩個(gè)出口Q1、Q2，經(jīng)過解析，可得四元式序列：

解析入口為（101），其出口為（106）和（107），Q1為“真”出口，對(duì)應(yīng)的操作為“繪制”；Q2為“假”出口，對(duì)應(yīng)的操作為“丟棄”。即表達(dá)式狀態(tài)只有兩種：TURE 或FALSE，當(dāng)為TURE 時(shí)，說明該點(diǎn)（像素）是符合表達(dá)式要求的，則進(jìn)行渲染；當(dāng)為FALSE時(shí)，說明該點(diǎn)（像素）是不符合表達(dá)式要求的，則進(jìn)行丟棄（不進(jìn)行渲染）。最后渲染的結(jié)果就是表達(dá)式的結(jié)果。

3.2 Shader著色器的工作流程

基元模型繪制是通過GLSL 繪制管線來完成的。GLSL 渲染管線也稱為渲染流水線，是顯示芯片內(nèi)部處理圖形信號(hào)相互獨(dú)立的并行處理單元。一個(gè)流水線是一序列可以并行和按照固定順序進(jìn)行的階段。

在OpenGL 中，會(huì)用到不同的四種不同的著色階段，其中最常用的就是頂點(diǎn)著色器和片源著色器，前者處理頂點(diǎn)數(shù)據(jù)，后者處理光柵化的片元數(shù)據(jù)。Shader（著色器）實(shí)際上就是一小段程序，頂點(diǎn)Shader是處理頂點(diǎn)數(shù)據(jù)的著色器，內(nèi)存中的頂點(diǎn)數(shù)據(jù)通過綁定VBO（頂點(diǎn)緩存對(duì)象）和VAO（頂點(diǎn)數(shù)組對(duì)象）傳遞到頂點(diǎn)Shader 中，以指定的方式和輸入的貼圖或者顏色等組合起來，然后輸出。經(jīng)過處理的頂點(diǎn)數(shù)據(jù)在光柵化后會(huì)以片段的形式傳輸?shù)狡蜸hader中，通過在片段Shader中定義一系列片段處理操作最終輸出片段的顏色。其流程如圖3所示。

圖3 Shader處理數(shù)據(jù)流程圖

首先在片段Shader 中定義點(diǎn)與幾何體的位置關(guān)系判斷函數(shù)即幾何函數(shù)，當(dāng)表達(dá)式解析完畢并生成相應(yīng)的四元式后，將四元式中的操作數(shù)集合S｛S1，S2，S3……｝與球體、立方體、圓柱體幾何函數(shù)對(duì)應(yīng)，其映射關(guān)系可以通過uniform 變量實(shí)現(xiàn)，uniform 變量可以將程序內(nèi)定義的每個(gè)操作數(shù)類型傳遞到片段Shader中。

然后對(duì)于每一個(gè)四元式操作，都生成一個(gè)暫時(shí)的bool 類型變量T｛T1，T2，T3……｝，該變量不作為片段Shader 的輸出，只作為計(jì)算過程中的數(shù)據(jù)傳遞。其最終運(yùn)算結(jié)果即為所有中間變量的“與”運(yùn)算，令Q 為最終結(jié)果即“Q=T1&T2&T3&…Tn” 。由于是bool 類型數(shù)據(jù)運(yùn)算，結(jié)果為0 或者1。當(dāng)結(jié)果為0，則丟棄該片段；當(dāng)結(jié)果為1，則輸出該片段，作為要繪制的片段部分。

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)平臺(tái)為Intel（R）Core（TM）i3 CPU 550，主頻為3.20GHz，系統(tǒng)內(nèi)存為8GB 顯卡為NVIDIA Ge-Force 730，顯卡內(nèi)存為1GB，操作系統(tǒng)為Windows 10，實(shí)驗(yàn)開發(fā)環(huán)境為Visual Studio 2015。實(shí)驗(yàn)對(duì)比了OpenCSG 和Shader-CSG 的幾何圖形布爾運(yùn)算的渲染結(jié)果。

4.1 布爾運(yùn)算效果比較

選用OpenCSG 中基本幾何基元立方體、球體和圓柱體作為布爾運(yùn)算的基元模型，對(duì)比OpenCSG方法和Shader-CSG 方法的基本布爾運(yùn)算：交和差，并對(duì)其他復(fù)雜表達(dá)式進(jìn)行了渲染。交、差運(yùn)算渲染效果對(duì)比如圖4、圖5所示。

如圖4、圖5所示，左為OpenCSG實(shí)現(xiàn)的立方體與球體交、差運(yùn)算的渲染效果，右為Shader-CSG 實(shí)現(xiàn)的立方體與球體交、差運(yùn)算的渲染效果。

圖4 交運(yùn)算效果圖對(duì)比

圖5 差運(yùn)算效果圖對(duì)比

通過以上的渲染效果比較可以看出，當(dāng)通過參數(shù)化建模時(shí)，基于Shader的幾何圖形布爾運(yùn)算的渲染效果和OpenCSG 基本基元布爾運(yùn)算的效果相同。圖6 為幾種布爾表達(dá)式下Shader-CSG 的渲染效果。

圖6 Shader-CSG布爾表達(dá)式渲染效果

渲染效果表明，Shader-CSG 方法渲染效果可與OpenCSG 渲染效果相一致，能準(zhǔn)確地呈現(xiàn)表達(dá)式的結(jié)果。

4.2 布爾運(yùn)算效率比較

本實(shí)驗(yàn)比較OpenCSG 布爾運(yùn)算和Shader-CSG布爾運(yùn)算的渲染效率。 首先固定三角片數(shù)量，球體和圓柱體三角片數(shù)為100*100，通過增加參與布爾運(yùn)算的幾何體數(shù)量來統(tǒng)計(jì)兩種方法的渲染效率。其渲染效率對(duì)比和趨勢如圖7所示。

圖7 不同幾何體數(shù)量渲染效率趨勢

通過圖7 可以得出，當(dāng)三角片數(shù)量固定，幾何體數(shù)量增加時(shí)，Shader-CSG 的渲染優(yōu)于OpenCSG的渲染效率，其效率差距隨著幾何體數(shù)量增長而變大，表明在此條件下GPU 處理布爾運(yùn)算的渲染速度更快。

然后選擇表達(dá)式“A∩B-C”，通過改變?nèi)瞧瑪?shù)量來統(tǒng)計(jì)兩種方法的渲染效率。其渲染效率對(duì)比和趨勢如圖8所示。

圖8 不同三角片數(shù)量渲染效率趨勢

通過圖8 可以得出，當(dāng)幾何體數(shù)量固定，三角片數(shù)量增加時(shí)，Shader-CSG 的渲染效率大大優(yōu)于OpenCSG的渲染效率，當(dāng)三角片個(gè)數(shù)達(dá)到百萬級(jí)別時(shí)，其效率差距呈降低趨勢。

結(jié)果表明，Shader-CSG 方法在渲染效果上具有很高的精確度，能穩(wěn)定地將布爾表達(dá)式的結(jié)果直接的呈現(xiàn)出來。同時(shí)，由于其GPU 編程的特性Shader-CSG 方法在渲染效率上優(yōu)于OpenCSG 的渲染效率，減少了渲染時(shí)間。

5 結(jié)語

針對(duì)傳統(tǒng)幾何圖形的布爾運(yùn)算的穩(wěn)定性不足和繪制效率低下問題，本文提出一種基于Shader的CSG 幾何體的實(shí)時(shí)渲染，通過參數(shù)化建模，用離散化的三角片繪制基元模型，并計(jì)算每個(gè)點(diǎn)與幾何體位置關(guān)系，最后對(duì)布爾運(yùn)算表達(dá)式解析將布爾運(yùn)算的最終結(jié)果繪制。實(shí)驗(yàn)表明，該方法在繪制效果與繪制效率上具有良好的表現(xiàn)，并在繪制效率上優(yōu)于經(jīng)典的CSG（構(gòu)造實(shí)體幾何）繪制方式。