基于Shader 的CSG 幾何體的實時渲染*

陳國軍 尹 鵬 裴利強 尹 沖

（中國石油大學（華東）計算機科學與技術學院 青島 266580）

1 引言

隨著計算機圖形應用的發展，布爾運算在建模系統中扮演了關鍵的角色［1］。經過數十年的研究和發展，二維圖形和三維實體布爾運算已經成為了計算機圖形學方面非常熱門的研究方向之一［2］。布爾運算是通過對兩個以上的物體進行并集、差集、交集的運算，從而得到新的物體［3～4］。其運算方式有并集、交集和差集。目前基于物體空間的布爾運算算法已有相當的研究成果。根據維度布爾運算分成二維布爾運算和三維布爾運算［5～6］。

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

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

2 布爾運算基元建模

2.1 基元模型構建

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

1）參數化建模

模型參數為centerPos（中心點坐標）。變換參數為length（長度）、angle（旋轉角）、radius（半徑）、height（高度）。

2）離散化

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

球體曲面建立是通過對球體沿著Z 坐標軸旋轉“分片（slices）”，在每片上再進行“分塊（stacks）”。如圖1 所示，分別展示了圓柱體底面分片和球體分片、分區的過程。

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

每個三維模型表面都通過密集的三角片進行逼近，并且保證基元模型在每個二維坐標系下的投影都是規范圖形，使得在考慮誤差時可以通過數學計算減小誤差。

2.2 基元模型中點與幾何體位置關系判斷

對于三維幾何體，當基元模型為立方體時，設立方體X、Y、Z 坐標系中的最大值和最小值分別為maxX、maxY、maxZ 和minX、minY、minZ。對于任意空間一點P（x，y），滿足點P在立方體內部或表面的條件為

圖2 點與曲面體位置關系判斷圖

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

由線段長度比較得到該點所在的位置：

3 CSG幾何體的渲染

要實現CSG相對應幾何體的渲染，首先要解析CSG 樹，形成一個可判斷的邏輯公式［15］，然后將解析結果傳遞到Shader（著色器）中，實現實時繪制。

3.1 布爾運算表達式解析

解析布爾運算表達式的基礎是解析兩個布爾基元的運算。首先針對立方體、球體、圓柱體這三種布爾運算基元，定義S1、S2、S3 分別為空間任一點與立方體、球體、圓柱體的位置關系值。例如球體，當S2=0 時，指該點在球體內部；當S2=1 時，指該點在球體表面；當S2=2 時，指該點在球體外部。將這種關系與式（5）結合，點與球體關系如式（6）所示：

當出現兩個基元布爾運算時，比如立方體與球體，其交、并、差的表達式可以解析邏輯表達式。邏輯式（7）、（8）、（9）分別表示了立方體與球體的交、并、差運算。

布爾表達式中運算符，按照優先級分為括號和邏輯運算符。邏輯運算符交、并、差即可表示成”∧”、”∨”、”?”的形式。布爾運算文法如下：

布爾表達式的解析類似算術表達式解析，其三中邏輯運算可以做以下等價解釋：

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

解析入口為（101），其出口為（106）和（107），Q1為“真”出口，對應的操作為“繪制”；Q2為“假”出口，對應的操作為“丟棄”。即表達式狀態只有兩種：TURE 或FALSE，當為TURE 時，說明該點（像素）是符合表達式要求的，則進行渲染；當為FALSE時，說明該點（像素）是不符合表達式要求的，則進行丟棄（不進行渲染）。最后渲染的結果就是表達式的結果。

3.2 Shader著色器的工作流程

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

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

圖3 Shader處理數據流程圖

首先在片段Shader 中定義點與幾何體的位置關系判斷函數即幾何函數，當表達式解析完畢并生成相應的四元式后，將四元式中的操作數集合S｛S1，S2，S3……｝與球體、立方體、圓柱體幾何函數對應，其映射關系可以通過uniform 變量實現，uniform 變量可以將程序內定義的每個操作數類型傳遞到片段Shader中。

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

4 實驗結果與分析

實驗平臺為Intel（R）Core（TM）i3 CPU 550，主頻為3.20GHz，系統內存為8GB 顯卡為NVIDIA Ge-Force 730，顯卡內存為1GB，操作系統為Windows 10，實驗開發環境為Visual Studio 2015。實驗對比了OpenCSG 和Shader-CSG 的幾何圖形布爾運算的渲染結果。

4.1 布爾運算效果比較

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

如圖4、圖5所示，左為OpenCSG實現的立方體與球體交、差運算的渲染效果，右為Shader-CSG 實現的立方體與球體交、差運算的渲染效果。

圖4 交運算效果圖對比

圖5 差運算效果圖對比

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

圖6 Shader-CSG布爾表達式渲染效果

渲染效果表明，Shader-CSG 方法渲染效果可與OpenCSG 渲染效果相一致，能準確地呈現表達式的結果。

4.2 布爾運算效率比較

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

圖7 不同幾何體數量渲染效率趨勢

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

然后選擇表達式“A∩B-C”，通過改變三角片數量來統計兩種方法的渲染效率。其渲染效率對比和趨勢如圖8所示。

圖8 不同三角片數量渲染效率趨勢

通過圖8 可以得出，當幾何體數量固定，三角片數量增加時，Shader-CSG 的渲染效率大大優于OpenCSG的渲染效率，當三角片個數達到百萬級別時，其效率差距呈降低趨勢。

結果表明，Shader-CSG 方法在渲染效果上具有很高的精確度，能穩定地將布爾表達式的結果直接的呈現出來。同時，由于其GPU 編程的特性Shader-CSG 方法在渲染效率上優于OpenCSG 的渲染效率，減少了渲染時間。

5 結語

針對傳統幾何圖形的布爾運算的穩定性不足和繪制效率低下問題，本文提出一種基于Shader的CSG 幾何體的實時渲染，通過參數化建模，用離散化的三角片繪制基元模型，并計算每個點與幾何體位置關系，最后對布爾運算表達式解析將布爾運算的最終結果繪制。實驗表明，該方法在繪制效果與繪制效率上具有良好的表現，并在繪制效率上優于經典的CSG（構造實體幾何）繪制方式。