3D 模型均勻細(xì)分算法及其GPU 實(shí)現(xiàn)方法研究

劉軒　黃海于

摘要：3D模型的細(xì)分是計(jì)算機(jī)圖形學(xué)重要的研究內(nèi)容，在對(duì)較為復(fù)雜的3D模型進(jìn)行高精度細(xì)分時(shí)，需要進(jìn)行大量的計(jì)算，CPU并不能很好地完成該任務(wù)，GPU具有并行架構(gòu)，計(jì)算能力十分強(qiáng)大，因此選擇使用GPU對(duì)細(xì)分算法進(jìn)行加速，可以極大地提高模型細(xì)分的速度。文章設(shè)計(jì)了一種3D模型的均勻細(xì)分算法：掃描線-柵格填充法。對(duì)存儲(chǔ)模型信息的文件進(jìn)行預(yù)處理，提取出細(xì)分所需要的數(shù)據(jù)，把對(duì)模型的均勻細(xì)分轉(zhuǎn)化為對(duì)三維空間中若干封閉圖形的均勻細(xì)分，將整個(gè)填充區(qū)域柵格化，利用掃描線算法對(duì)每個(gè)柵格進(jìn)行填充。文章討論了該算法在GPU上的實(shí)現(xiàn)方法，展示了細(xì)分后的網(wǎng)格化3D模型，對(duì)比評(píng)估了該算法在CPU和GPU上的性能表現(xiàn)，探討了如何在GPU上獲得更好性能的方法。

關(guān)鍵詞： 圖形處理；模型細(xì)分；GPU并行處理；掃描線-柵格法；網(wǎng)格化模型

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2024）13-0027-04 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID） ：

0 引言

隨著科技的不斷進(jìn)步，三維建模技術(shù)在計(jì)算機(jī)模擬領(lǐng)域的作用也越來越重要[1]。在工業(yè)制造領(lǐng)域，利用三維建模技術(shù)對(duì)其進(jìn)行仿真模擬，可以真實(shí)地反映切削加工過程，清晰呈現(xiàn)工件加工后的形態(tài)，提高了生產(chǎn)效率，保證了加工質(zhì)量[2]。在模擬加工過程中，需要對(duì)刀具和工件之間的碰撞進(jìn)行檢測(cè)，涉及大量的運(yùn)算[3]。若工件模型中三角面的大小各不相同，會(huì)嚴(yán)重影響模擬加工的速度，因此對(duì)工件模型按加工精細(xì)度進(jìn)行均勻細(xì)分是非常必要的。

對(duì)3D模型進(jìn)行均勻細(xì)分時(shí)，傳統(tǒng)的掃描線法在填充較為復(fù)雜的圖形時(shí)效果不佳[4]。文獻(xiàn)[5]提出了基于柵格的任意復(fù)雜區(qū)域自動(dòng)填充算法，但該算法的細(xì)分精度和效率無法滿足工業(yè)加工的要求。本文結(jié)合掃描線和柵格填充算法，提出了一種掃描線-柵格的填充方法。將整個(gè)模型拆分為若干個(gè)三維空間中的超平面，將超平面轉(zhuǎn)化為二維平面上的封閉多邊形并使其所在區(qū)域柵格化，再利用掃描線算法對(duì)各柵格進(jìn)行填充，實(shí)現(xiàn)圖形的均勻細(xì)分。該算法在CPU上實(shí)現(xiàn)比較容易，但工業(yè)加工領(lǐng)域中所采用的模型都比較復(fù)雜，對(duì)精細(xì)度的要求非常高，CPU無法滿足對(duì)處理速度的要求。GPU采用大規(guī)模并行處理架構(gòu)[6]，能同時(shí)處理多個(gè)柵格，從而快速完成復(fù)雜模型的均勻細(xì)分。

1 掃描線-柵格算法

本文使用的3D模型以STL文件格式存儲(chǔ)。STL 文件包含了模型中每個(gè)三角形的幾何信息[7]。在進(jìn)行3D模型細(xì)分前，先對(duì)模型文件進(jìn)行預(yù)處理，將共面三角形合并為封閉多邊形，然后將其轉(zhuǎn)換到XY平面上。在細(xì)分時(shí)，求出封閉多邊形的最小矩形包圍框，按所給精細(xì)度將矩形包圍框分為若干柵格；計(jì)算掃描線與圖形的交點(diǎn)和所在柵格的序號(hào)；以相鄰兩柵格作為待填充區(qū)域進(jìn)行填充。對(duì)所有封閉圖形采用上述方法進(jìn)行細(xì)分，就能實(shí)現(xiàn)對(duì)三維模型的均勻細(xì)分。

1.1 圖形預(yù)處理

1.1.1 共面三角形的合并

利用從STL文件中得到的三角形鄰接信息求共面三角形，使用種子生長法，需要用到一個(gè)代表當(dāng)前平面號(hào)的整型變量numTri（初值為-1） 、記錄各三角形所在平面號(hào)的數(shù)組sur和一個(gè)循環(huán)隊(duì)列。算法如下：

1） 選擇一個(gè)初始三角形作為種子，將其入隊(duì)列并標(biāo)記，使numTri的值加1，將數(shù)組sur中對(duì)應(yīng)此三角形的元素值設(shè)為numTri；

2） 將種子三角形出隊(duì)列，判斷其鄰接三角形是否未標(biāo)記且與它共面，是則將這些三角形入隊(duì)列并標(biāo)記，并且把數(shù)組sur中對(duì)應(yīng)這些三角形的元素值設(shè)為numTri，否則不對(duì)這些三角形和數(shù)組sur做任何處理；

3） 將隊(duì)列中三角形依次出隊(duì)列，判斷其鄰接三角形是否未標(biāo)記且與它共面，是則將這些三角形入隊(duì)列并標(biāo)記，并且把數(shù)組sur中對(duì)應(yīng)這些三角形的元素值設(shè)為numTri，否則不對(duì)這些三角形和數(shù)組sur做任何處理；

4） 當(dāng)隊(duì)列為空時(shí)，得到一個(gè)共面三角形的信息；

5） 返回第1步，重新尋找下一個(gè)種子三角形；

6） 重復(fù)第2～5步，直到所有三角形均被標(biāo)記，算法結(jié)束，此時(shí)數(shù)組sur中的每個(gè)元素值就代表了各三角形所在的平面序號(hào)。

1.1.2 圖形邊緣的提取

將各三角形按所在平面序號(hào)加入所屬的空間平面，就得到了若干封閉圖形。這些圖形包含內(nèi)部邊和邊緣上的邊，而掃描線算法只要求保留圖形邊緣。圖形邊緣上的三角形一定有一條邊沒有鄰接三角形，通過三角形鄰接信息求出所有符合條件的邊，只保留這些邊，就能得到圖形的邊緣。

1.1.3 坐標(biāo)轉(zhuǎn)換

在得到各空間平面上的封閉圖形后，把每個(gè)封閉圖形都轉(zhuǎn)換到XY平面上，根據(jù)某封閉圖形所在的空間平面上任意一點(diǎn)和法向量構(gòu)建局部坐標(biāo)系。

設(shè)P =（Px，Py，Pz，1） ，n =（nx，ny，nz，0） 為空間平面上一點(diǎn)和法向量（用作z 軸）相對(duì)于世界坐標(biāo)系的齊次坐標(biāo)，則任取一個(gè)與n 正交的向量u =（ux，uy，uz，0） 作為x軸，再用u 和n 的叉乘結(jié)果v =（vx，vy，vz，0） 作為y 軸。這樣從局部坐標(biāo)系至世界坐標(biāo)系的坐標(biāo)變換矩陣為：

初始狀態(tài)下，封閉圖形上所有點(diǎn)都用世界坐標(biāo)系的坐標(biāo)表示，要將它轉(zhuǎn)換到XY平面上，使用W的逆矩陣對(duì)所有點(diǎn)進(jìn)行坐標(biāo)變換即可。

1.2 掃描線求交

將封閉多邊形轉(zhuǎn)換到XY平面后，計(jì)算它在x 軸和y 軸上的最大值和最小值，得到該圖形的一個(gè)長方形包圍框，將此包圍框橫向縱向按照所給精度均勻分為m 行n 列，使用m 條分別處于每行正中間且和x軸平行的直線作為掃描線。

設(shè)有一條掃描線y = ys，依次判斷封閉圖形各條邊和它的相交情況并記錄交點(diǎn)信息。設(shè)封閉圖形中某條邊的兩個(gè)端點(diǎn)的坐標(biāo)為（xi，yi） 和（xi+1，yi+1） ，則：

1） 當(dāng)yi = yi+1，即該邊與掃描線平行時(shí)，沒有任何交點(diǎn)，直接略過該邊。

2） 當(dāng)（ys - yi）（ys - yi+1） < 0時(shí)，該邊與掃描線有一個(gè)交點(diǎn)，由式（2） 得出它的橫坐標(biāo)：

3） 當(dāng)ys = yi或ys = yi+1，此時(shí)會(huì)出現(xiàn)角點(diǎn)問題，針對(duì)這種情況，可對(duì)圖形中各邊采用上閉下開的原則[8]，在一條邊的兩個(gè)端點(diǎn)中，上端點(diǎn)采用閉區(qū)間，可計(jì)算此處與掃描線的交點(diǎn)；下端點(diǎn)采用開區(qū)間，不計(jì)算此處與掃描線的交點(diǎn)。此原則能保證每條掃描線上的交點(diǎn)個(gè)數(shù)為偶數(shù)，此時(shí)交點(diǎn)坐標(biāo)已知，無須計(jì)算。

1.3 特殊情況的處理

各條掃描線的間距是固定的，在許多情況下，掃描線和圖形中各邊無法匹配，這會(huì)使某些掃描線和圖形邊界的交點(diǎn)數(shù)被誤記為0。針對(duì)此類問題，需要做近似化處理，當(dāng)某條非水平邊有一個(gè)端點(diǎn)和某條掃描線的距離足夠近時(shí)，就認(rèn)為它們相交。圖1（a） 是由共面三角形合并生成的一個(gè)封閉圖形，圖1（b） 為保留其邊緣部分后得到的圖形。在圖1（c） 中，對(duì)該圖形使用本算法進(jìn)行均勻細(xì)分時(shí)產(chǎn)生了上述問題，圖形上出現(xiàn)了空洞。在近似化處理后，如圖1（d） 所示，模型上的空洞問題得到解決。

1.4 使用柵格進(jìn)行圖形均勻細(xì)分

本文將掃描線法與柵格法結(jié)合，將一條掃描線與一行柵格對(duì)應(yīng)，從而使傳統(tǒng)區(qū)域填充算法中對(duì)像素點(diǎn)的填充轉(zhuǎn)變?yōu)閷?duì)柵格的填充。

在得到了一條掃描線上與封閉圖形的所有交點(diǎn)之后，按照橫坐標(biāo)值從小到大依次排列，將它們兩兩視為一組，作為一段待填充區(qū)域。對(duì)于一組交點(diǎn)，分別計(jì)算兩個(gè)點(diǎn)所在的方格序號(hào)，其中行序號(hào)與掃描線所在行相同，列序號(hào)可由式（3） 求得：

其中，x 為交點(diǎn)橫坐標(biāo)值，left是封閉圖形矩形包圍框最左端的橫坐標(biāo)值，tessellation為給定的精細(xì)度，┌ ┐為向上取整符號(hào)。

計(jì)算出兩個(gè)交點(diǎn)所在的方格序號(hào)后，對(duì)它們之間的每個(gè)方格使用兩個(gè)大小相同的三角形進(jìn)行填充即可。對(duì)整個(gè)封閉圖形完成填充后，就實(shí)現(xiàn)了對(duì)該圖形的均勻細(xì)分。

2 算法在GPU 中的實(shí)現(xiàn)

機(jī)械加工過程中所涉及的模型比較復(fù)雜，對(duì)精細(xì)度的要求也比較高，導(dǎo)致填充過程中涉及大量的計(jì)算。GPU適合處理計(jì)算密集型任務(wù)[9]，將填充任務(wù)交給GPU來執(zhí)行，可以大大提高細(xì)分的速度。

2.1 在GPU 上的實(shí)現(xiàn)過程

對(duì)于每組交點(diǎn)，前面的算法已分別求出它們所在柵格單元號(hào)。GPU將對(duì)兩柵格和它們之間的柵格進(jìn)行填充，每次向GPU傳送一對(duì)柵格信息，經(jīng)GPU處理后將目標(biāo)區(qū)域中的柵格填充并輸出。

繪制時(shí)每次的輸入是掃描行上的一對(duì)柵格信息，輸出是對(duì)應(yīng)區(qū)間內(nèi)的若干三角形構(gòu)成的柵格。因此，將填充任務(wù)交給GPU端的幾何著色器（GS） 完成，GS 能夠接收完整的圖元（如單個(gè)點(diǎn)、線段的兩個(gè)點(diǎn)、三角形的三個(gè)點(diǎn)），處理后可以輸出指定的圖元，適合處理本文中的柵格填充操作。

為了向GPU中的GS傳送待填充的柵格信息，設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)十分重要。柵格信息除了所在列號(hào)和行號(hào)外，還應(yīng)包含所在封閉圖形平面的法向量、細(xì)分精細(xì)度，以及二維到三維空間的轉(zhuǎn)換矩陣信息等。本文在Direct3D 12環(huán)境下進(jìn)行圖形程序開發(fā)，向GPU傳輸數(shù)據(jù)時(shí)，要將它們包裝為4個(gè)一組的向量形式，由于每對(duì)相鄰的柵格都在同一平面上，它們除了列號(hào)之外的信息均相同，因此每次使用一個(gè)結(jié)構(gòu)體變量表示一對(duì)柵格，結(jié)構(gòu)體定義如下：

其中DirectX：：XMFLOAT4為DirectX中的一種向量類型，可存儲(chǔ)4個(gè)float類型的分量數(shù)據(jù)。Pos存儲(chǔ)第一個(gè)柵格列號(hào)、第二個(gè)柵格列號(hào)、柵格行號(hào)和細(xì)分精細(xì)度；Nor存儲(chǔ)柵格所在平面的法向量；Matrix0、Ma? trix1、Matrix2、Matrix3分別存儲(chǔ)4x4的轉(zhuǎn)換矩陣每一行的數(shù)據(jù)。

將模型各超平面上的所有柵格對(duì)求出來之后，把它們依次按上述格式封裝并傳輸至GPU。一對(duì)柵格數(shù)據(jù)被GS接收后，判斷它們所在的列號(hào)是否相同，若相同則只計(jì)算填充一個(gè)柵格所需的兩個(gè)三角形的頂點(diǎn)信息；若不同，則計(jì)算填充兩個(gè)柵格之間所有柵格的若干三角形頂點(diǎn)信息。此時(shí)，各頂點(diǎn)還處于XY平面上，要將各頂點(diǎn)用轉(zhuǎn)換矩陣W進(jìn)行變換，使其回到原位置。最后，將各頂點(diǎn)以三角形帶的形式輸出，即可完成對(duì)一塊目標(biāo)區(qū)域的填充。

GS每次處理一對(duì)柵格，輸入為一個(gè)代表柵格對(duì)的pieceVertex類型變量gin，輸出為填充柵格區(qū)域的三角形頂點(diǎn)集合triStream。上述算法的偽代碼如下：

輸入：待填充的柵格對(duì)信息gin

輸出：用于填充柵格區(qū)域的三角形集合triStream

1） function GS<（gin，triStream）

2）column1<-gin.Pos[0];

3）column2<-gin.Pos[1];

4）y<-gin.Pos[2];

5）tes<-gin.Pos[3];

6）nor<-gin.Nor;

7）trans<-（gin.Matrix0，gin.Matrix1，gin.Matrix2，gin.Matrix3）

8）for column<-column 1 to column 2 do //填充一個(gè)或若干柵格

9）v[0]<-（column*tes，y+0.5*tes，0，1）//計(jì)算此柵格的四個(gè)頂點(diǎn)位置

10）v[1]<-（（column+1）*tes，y+0.5*tes，0，1）

11）v[2]<-（column*tes，y-0.5*tes，0，1）

12）v[3]<-（（column+1）*tes，y-0.5*tes，0，1）

13）for i<- 0 to 3 do

14）v[i]<- mul（v[i]，trans）//將頂點(diǎn)位置轉(zhuǎn)換回三維空間

15）triStream<-（v[0]，v[2]，v[1]）//將兩個(gè)三角形加入結(jié)果集中

16） triStream <- （v[1]， v[2]， v[3]）

17） end function

2.2 在GPU 上獲得更好的性能

一對(duì)柵格之間的柵格數(shù)是不確定的，二者的距離和細(xì)分的精細(xì)度都會(huì)影響這個(gè)數(shù)量。而GPU出于對(duì)GS性能方面的考量，限制了GS每次能輸出的標(biāo)量數(shù)，此個(gè)數(shù)為每次輸出元素的頂點(diǎn)數(shù)量和輸出元素個(gè)數(shù)的乘積。每個(gè)柵格包括2個(gè)三角形，每個(gè)三角形有3 個(gè)頂點(diǎn)，因此每輸出一個(gè)柵格時(shí)標(biāo)量數(shù)為6。GS每次輸出的標(biāo)量數(shù)在大于40時(shí)，性能就會(huì)開始下降，考慮到該項(xiàng)限制，本文選擇將最大輸出標(biāo)量數(shù)定為84，每次最多填充并輸出14個(gè)連續(xù)的柵格。需要在向GPU 傳輸前進(jìn)行判斷，若一對(duì)柵格間的柵格數(shù)不超過14，則直接傳輸；若大于14，則要將這對(duì)柵格進(jìn)行分割，使分割后的每個(gè)子段中需要填充的柵格數(shù)不超過14。

將每對(duì)柵格經(jīng)過上述的檢查處理后，在不超過GS 規(guī)定的情況下盡可能每次填充一行上較多的柵格，在后續(xù)的具體實(shí)驗(yàn)中得到了較好的效果。

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

3.1 細(xì)分結(jié)果分析

對(duì)一個(gè)STL模型使用本文算法進(jìn)行均勻細(xì)分，將細(xì)分的精細(xì)度分別設(shè)置為1、0.5、0.2，單位均為cm，如圖2所示。結(jié)果表明，精細(xì)度越高，網(wǎng)格越密集，細(xì)分效果越好。

3.2 細(xì)分效率分析

為測(cè)試該算法在GPU中的優(yōu)勢(shì)，對(duì)2個(gè)STL文件大?。▎挝唬篕B） 不同的模型使用不同精度（單位：cm） 進(jìn)行均勻細(xì)分，對(duì)比它們?cè)贑PU和GPU中進(jìn)行細(xì)分任務(wù)時(shí)所花費(fèi)的時(shí)間（單位：s） ，結(jié)果見圖3（a） 。結(jié)果表明，本文算法在GPU上的性能表現(xiàn)遠(yuǎn)遠(yuǎn)超過了在CPU 上的版本。在模型越復(fù)雜、精細(xì)度越高時(shí)，GPU中的算法優(yōu)勢(shì)越大。

為測(cè)試GPU中的算法在處理不同模型時(shí)的效率表現(xiàn)，對(duì)3個(gè)STL文件大?。▎挝唬篕B） 不同的模型使用多種精細(xì)度（單位：cm） 進(jìn)行均勻細(xì)分，對(duì)比它們?cè)贕PU中進(jìn)行細(xì)分任務(wù)時(shí)所花費(fèi)的時(shí)間（單位：s） ，結(jié)果見圖3（b） 。結(jié)果表明，在精度要求較低時(shí)，模型的文件大小對(duì)GPU中算法的處理速度幾乎沒有影響，這是因?yàn)镚PU中對(duì)數(shù)據(jù)的處理和運(yùn)算是并發(fā)進(jìn)行的，在精細(xì)度情況下，不同模型對(duì)應(yīng)的計(jì)算量的差距不是非常大，因此在GPU中經(jīng)過并行處理所耗費(fèi)的時(shí)間也相差不大；在模型間的復(fù)雜度差距很大或要求使用較高的精細(xì)度時(shí)，GPU中的處理時(shí)間才會(huì)有明顯差距。

4 結(jié)束語

針對(duì)傳統(tǒng)細(xì)分方法無法均勻細(xì)分模型的問題，提出了一種基于掃描線算法和柵格的均勻細(xì)分模型的算法。通過從模型STL文件中得到的信息，將對(duì)模型的每個(gè)三維空間面的處理轉(zhuǎn)化為對(duì)二維平面上封閉圖形的處理，對(duì)每個(gè)圖形用柵格作為單位進(jìn)行區(qū)域填充，實(shí)現(xiàn)對(duì)整個(gè)模型的均勻細(xì)分，最后將填充任務(wù)交由GPU處理。經(jīng)過測(cè)試，該方法可以正確地將模型按精細(xì)度均勻細(xì)分，得益于GPU強(qiáng)大的計(jì)算能力，算法效率有較大的提升。

參考文獻(xiàn)：

[1] 欒悉道，應(yīng)龍，謝毓湘，等. 三維建模技術(shù)研究進(jìn)展[J]. 計(jì)算機(jī)科學(xué)，2008，35（2）：208-210，229.

[2] 李志鵬. 論三維建模技術(shù)在機(jī)械產(chǎn)品設(shè)計(jì)中的應(yīng)用[J]. 內(nèi)燃機(jī)與配件，2021（21）：216-218.

[3] 項(xiàng)立富. 信息時(shí)代背景下數(shù)控加工仿真技術(shù)與軟件的開發(fā)路徑[J]. 南方農(nóng)機(jī)，2019，50（22）：194.

[4] 石燕.淺析區(qū)域填充算法[J]. 計(jì)算機(jī)光盤軟件與應(yīng)用，2014，17（9）：131-132.

[5] 邱國清. 基于柵格的任意復(fù)雜區(qū)域自動(dòng)填充算法[J]. 圖學(xué)學(xué)報(bào)，2018，39（3）：419-423.

[6] 董犖，葛萬成，陳康力. CUDA并行計(jì)算的應(yīng)用研究[J]. 信息技術(shù)，2010，34（4）：11-15.

[7] 朱虎，楊忠鳳，張偉. STL文件的應(yīng)用與研究進(jìn)展[J]. 機(jī)床與液壓，2009，37（6）：186-189.

[8] 李慧賢，馬創(chuàng)新，馬良. 增材制造中GPU并行掃描線填充算法[J]. 熱加工工藝，2023（13）：100-104，113.

[9] 田衛(wèi)明，劉富強(qiáng)，謝鑫，等. 基于GPU粗細(xì)粒度和混合精度的SAR后向投影算法的并行加速研究[J]. 信號(hào)處理，2023，39（12）：2213-2224.

【通聯(lián)編輯：光文玲】