基于向量場(chǎng)距離函數(shù)的網(wǎng)孔模型修復(fù)

王 俐，吳祿慎

(南昌大學(xué)機(jī)電工程學(xué)院，江西南昌330031)

1 引言

逆向工程數(shù)據(jù)采集過(guò)程中，由于測(cè)量技術(shù)(三坐標(biāo)測(cè)量?jī)x、激光掃描儀等)及被測(cè)物體自身形面的復(fù)雜性和材質(zhì)等原因，采集到的物體表面數(shù)據(jù)往往是不完整的，存在著孔洞、間隙、重疊等多種缺陷或數(shù)據(jù)丟失現(xiàn)象，這將給后續(xù)的曲面重構(gòu)帶來(lái)極大地麻煩。

為此，研究者們提出了許多修復(fù)不完整數(shù)據(jù)模型的方法，這些方法主要分成兩大類:基于網(wǎng)孔模型的修復(fù)法(Mesh－based model repair)和體模型修復(fù)法(Volumetric model repair)。基于網(wǎng)孔模型的修復(fù)法直接在多邊形網(wǎng)孔模型上進(jìn)行操作以修復(fù)模型中各種各樣的幾何與拓補(bǔ)缺陷，比如孔洞的填補(bǔ)［1－2］、縫隙的縫合［3－4］等。由于只要對(duì)有缺陷的局部網(wǎng)孔進(jìn)行修復(fù)，網(wǎng)孔模型修復(fù)法的優(yōu)點(diǎn)是能夠最大限度的維持原物體表面的幾何形貌。其缺點(diǎn)是魯棒性差，有時(shí)會(huì)出現(xiàn)拓補(bǔ)結(jié)構(gòu)上的歧義性，且難以確保其輸出網(wǎng)孔模型的封閉性。體模型修復(fù)法將被修復(fù)網(wǎng)孔模型置于某個(gè)3D網(wǎng)格中，得到網(wǎng)孔模型的相應(yīng)體模型數(shù)據(jù)，之后再用MC算法［5］從該網(wǎng)格的體數(shù)據(jù)中重構(gòu)原網(wǎng)孔模型。經(jīng)過(guò)這一系列步驟后，原網(wǎng)孔模型中的缺陷(包括幾何體的重疊和嵌套)均得以自動(dòng)修。體修復(fù)法魯棒性好，且能確保輸出多邊形網(wǎng)孔模型的封閉性和各網(wǎng)孔方向的一致性。其缺點(diǎn)是處理速度慢，體元轉(zhuǎn)換需要大量的存儲(chǔ)空間;可能會(huì)失去原網(wǎng)孔模型中一些尖銳的形貌特征，且輸出的三角形網(wǎng)孔數(shù)量龐大，常常需要做后續(xù)的簡(jiǎn)化處理。無(wú)論使用哪種修復(fù)方法，魯棒性和精確性都是兩重要的修復(fù)指標(biāo)。

本文提出了一種基于向量場(chǎng)距離函數(shù)的網(wǎng)孔模型修復(fù)算法，該算法屬于體修復(fù)方法，但它在保證算法魯棒性的同時(shí)，通過(guò)使用向量場(chǎng)距離函數(shù)及對(duì)MC算法中插補(bǔ)方法的改進(jìn)，最大限度地保留了被修復(fù)網(wǎng)孔模型的原始特征。算法以物體的三角形網(wǎng)孔模型作為輸入，將其置入三維體網(wǎng)格中，創(chuàng)建其體網(wǎng)格模型——向量場(chǎng)距離函數(shù)模型，替代傳統(tǒng)的標(biāo)量場(chǎng)距離函數(shù)模型。最后，采用改進(jìn)的MC算法從網(wǎng)格體模型中提取物體表面輪廓(三角形網(wǎng)孔)作為輸出。對(duì)于任意帶缺陷的輸入網(wǎng)孔模型，該算法總能輸出無(wú)缺陷的準(zhǔn)確、封閉且方向一致的三角形網(wǎng)孔模型，魯棒性好，特別適合于CAD模型的修復(fù)。

2 體修復(fù)算法

2.1 修復(fù)原理

體模型修復(fù)法的基本思想如圖1所示:修復(fù)過(guò)程中關(guān)鍵是輸入模型的體元化，即將多邊形網(wǎng)孔模型轉(zhuǎn)換為體模型。體模型通常用一個(gè)三變量標(biāo)量值場(chǎng)函數(shù)表示，該函數(shù)表征了3D空間中某點(diǎn)到輸入多邊形網(wǎng)孔模型的最短距離。建立體模型后，再用諸如Marching Cube類的等值面提取方法從該體模型重構(gòu)多邊形網(wǎng)孔模型作為輸出。原輸入多邊形網(wǎng)孔模型中存在的各種缺陷會(huì)在體元化及網(wǎng)孔重構(gòu)的過(guò)程中得以自動(dòng)修復(fù)。

圖1 體模型法修復(fù)過(guò)程

2.2輸入模型的體元化

體元化就是將多邊形網(wǎng)孔模型轉(zhuǎn)化為體模型。體模型通常用符號(hào)場(chǎng)距離函數(shù)來(lái)表征，空間任意一點(diǎn)的場(chǎng)距離函數(shù)定義為該點(diǎn)到網(wǎng)孔模型的最短距離，而場(chǎng)距離函數(shù)的符號(hào)決定了該點(diǎn)在被表征網(wǎng)孔模型的內(nèi)部還是外部，這樣，符號(hào)場(chǎng)距離函數(shù)的零水平集即為被表征多邊形網(wǎng)孔模型的逼近。為了能得到一個(gè)封閉的輸出表面，關(guān)鍵是確定3D空間中各網(wǎng)格頂點(diǎn)場(chǎng)距離函數(shù)的符號(hào)，體元化方法也往往取決于場(chǎng)距離函數(shù)符號(hào)的確定方法。

符號(hào)產(chǎn)生的方法很多，較經(jīng)典的是Nooruddin and Turk的奇偶計(jì)數(shù)法和投影法［6］，他們從各網(wǎng)格頂點(diǎn)向模型投射光束，根據(jù)光束與模型交點(diǎn)個(gè)數(shù)的奇偶性或位置來(lái)決定各網(wǎng)格頂點(diǎn)的符號(hào)。但是該符號(hào)產(chǎn)生方法只適合于均勻網(wǎng)格，而且投影是全局性的操作，因此，體模型的分辨率會(huì)受到限制。最普遍的方法是空間劃分法，根據(jù)各網(wǎng)格頂點(diǎn)在網(wǎng)孔模型的內(nèi)部還是外部決定距離函數(shù)的符號(hào)，F(xiàn)risken et al［7］計(jì)算各網(wǎng)格頂點(diǎn)到輸入多邊形的最短符號(hào)距離來(lái)實(shí)現(xiàn)網(wǎng)孔模型的體元化。近幾年，已有人開(kāi)始使用計(jì)算機(jī)圖形硬件來(lái)實(shí)現(xiàn)模型的體元化。G.Passalis，I.A.Kakadiaris［8］利用計(jì)算機(jī)圖形硬件中的深度和模板緩存來(lái)實(shí)現(xiàn)網(wǎng)孔或參數(shù)表面的體元化。Thiago Bastos［9］、Llamas，Ignacio［10］等利用GPU產(chǎn)生符號(hào)場(chǎng)距離函數(shù)實(shí)現(xiàn)網(wǎng)孔模型的體元化。這些方法增加了硬件開(kāi)銷，而且與z緩沖區(qū)垂直的那些三角形面片處會(huì)產(chǎn)生一些小瑕疵，尤其是在網(wǎng)格分辨率較低的情況下。

本文使用空間劃分法建立網(wǎng)孔的體模型，不同于傳統(tǒng)方法的是，表示體模型的場(chǎng)距離函數(shù)不再是標(biāo)量場(chǎng)距離函數(shù)，而是向量場(chǎng)距離函數(shù)。與標(biāo)量場(chǎng)數(shù)據(jù)函數(shù)一樣，常常在3D立方體網(wǎng)格上定義向量場(chǎng)距離函數(shù)。網(wǎng)格中的每個(gè)立方體稱作一個(gè)單元，立方體的各個(gè)頂點(diǎn)則稱作像素，如圖2所示。對(duì)于網(wǎng)格中的每個(gè)像素，尋找三角形網(wǎng)孔模型中離它最近的點(diǎn)，并計(jì)算兩者間的距離。傳統(tǒng)的標(biāo)量場(chǎng)距離函數(shù)表示中，每個(gè)像素只保存該像素到三角形網(wǎng)孔模型最近點(diǎn)間的距離，而在向量場(chǎng)距離函數(shù)表示中，保存的是該像素指向三角形網(wǎng)孔模型上離它最近點(diǎn)的3D向量。此外，還用邏輯量來(lái)表征各個(gè)像素在隱含物體表面的內(nèi)部還是外部，這對(duì)之后用MC算法提取物體表面尤為重要。

圖2 3D立方體網(wǎng)格及其像素

算法中，通過(guò)求取網(wǎng)孔模型上距某像素最近點(diǎn)所在三角形法向量與之前保存的該像素到網(wǎng)孔模型最近點(diǎn)的3D向量的點(diǎn)積，來(lái)判斷該像素位于隱含表面的內(nèi)部還是外部:如果該點(diǎn)積的值為正，則該像素位于表面內(nèi)部(比如圖3(b)中的V5)，否則，位于表面外部(比如圖3(b)中的V1)。

圖3 確定立方體邊與物體表面交點(diǎn)的插補(bǔ)算法

向量場(chǎng)距離函數(shù)不僅記錄了各像素到隱含表面的最短距離，還記錄了各像素到該最短距離點(diǎn)的確切方向，因而比傳統(tǒng)的標(biāo)量場(chǎng)距離函數(shù)更加精確、完善。

2.3 網(wǎng)孔重構(gòu)

理論上，距離函數(shù)的零水平集f(x，y，z)=0即為所表征的曲面。在標(biāo)量場(chǎng)距離函數(shù)中，以距離為0來(lái)提取物體表面，而在向量場(chǎng)距離函數(shù)中則是以向量的幅值為0來(lái)提取物體表面。在實(shí)際應(yīng)用中，由于離散采樣及網(wǎng)格分辨率的緣故，往往要設(shè)定一閾值δ來(lái)表征場(chǎng)距離函數(shù)的零水平集。若≤δ，則點(diǎn)(x，y，z)屬于物體表面。

網(wǎng)孔重構(gòu)就是通過(guò)輪廓提取算法從帶符號(hào)體模型中提取其零等值面作為原三角形網(wǎng)孔模型的逼近。MC算法是最經(jīng)典的輪廓提取算法，但它是基于標(biāo)量場(chǎng)距離函數(shù)設(shè)計(jì)的。本文對(duì)MC算法中相應(yīng)立方體邊上的線性插補(bǔ)算法稍作了改動(dòng)，成功地用它從向量場(chǎng)距離函數(shù)中提取出了體模型的三角形網(wǎng)孔逼近。

根據(jù)MC算法，哪些立方體網(wǎng)格單元需要三角化，其中的哪些邊需要進(jìn)行插補(bǔ)運(yùn)算，取決于立方體網(wǎng)格的各個(gè)頂點(diǎn)(像素)在被重構(gòu)物體表面的內(nèi)部還是外部。對(duì)于那些8個(gè)頂點(diǎn)都位于表面內(nèi)部或外部的立方體網(wǎng)格單元，物體表面是不經(jīng)過(guò)的，無(wú)需三角化。只有那些8個(gè)頂點(diǎn)部分位于隱含表面內(nèi)部，部分位于隱含表面外部的立方體網(wǎng)格才要進(jìn)行插補(bǔ)運(yùn)算以確定三角化三角形的頂點(diǎn)。具體方法是:對(duì)于該立方體網(wǎng)格中的每條邊，若其兩個(gè)頂點(diǎn)都在隱含表面的內(nèi)部或都在隱含表面的外部，則無(wú)需插補(bǔ);若其中一個(gè)頂點(diǎn)位于隱含表面內(nèi)部，另一個(gè)頂點(diǎn)位于隱含表面外部，則該條邊上一定存在一零水平集的點(diǎn)，即該邊與隱含表面一定存在一個(gè)交點(diǎn)，需要用插補(bǔ)算法確定該交點(diǎn)的位置，作為后續(xù)三角化時(shí)的頂點(diǎn)之一。

圖3給出了基于標(biāo)量場(chǎng)距離函數(shù)的插補(bǔ)算法(a)與基于向量場(chǎng)距離函數(shù)的插補(bǔ)算法(b)，并將兩者進(jìn)行了對(duì)比。圖3中V1～V8是需要插補(bǔ)的某立方體網(wǎng)格的8個(gè)頂點(diǎn)，其中V5、V8位于待重構(gòu)表面的內(nèi)部，其余頂點(diǎn)位于待重構(gòu)表面的外部，因此，物體表面必經(jīng)過(guò)邊 V1V5、V5V6、V4V8和 V7V8。以下以V1V5邊為例，介紹兩種不同體模型表征下邊的插補(bǔ)算法。在標(biāo)量場(chǎng)距離函數(shù)表示中，D(V1)、D(V5)分別為像素V1、V5到隱含表面的最短標(biāo)量距離，插補(bǔ)算法用兩者的比值來(lái)初略地確定V1V5邊上插補(bǔ)點(diǎn)I的位置，即;在向量場(chǎng)距離函數(shù)表示中，A、B分別是隱含表面上距離像素V1、V5最近的點(diǎn)，向量即為向量場(chǎng)距離函數(shù)表示中像素V1、V5中所保存的向量。與基于標(biāo)量場(chǎng)距離函數(shù)的MC算法相同，從向量場(chǎng)距離函數(shù)中提取物體表面，也要在邊V1V5上尋找一個(gè)插補(bǔ)點(diǎn)I，不同的是，此處用AB與V1V5的交點(diǎn)作為插補(bǔ)點(diǎn)(如果AB與V1V5在同一平面上的話)，如圖3(b)所示。但在實(shí)際的3D情形中，邊V1V5與線段AB往往是異面的，因此，插補(bǔ)算法在邊V1V5上尋找距離線段AB最近的點(diǎn)作為最終的插補(bǔ)點(diǎn)I。

求以上插補(bǔ)點(diǎn)I的方法很多，典型的方法是投影法，投影法需要確定投影平面，還要進(jìn)行叉積運(yùn)影法，投影法需要確定投影平面，還要進(jìn)行叉積運(yùn)使用向量以及向量間一些簡(jiǎn)單的

點(diǎn)積運(yùn)算，便可算得插補(bǔ)點(diǎn)I分有向線段V1V5所成的比例λ，從而算得插補(bǔ)點(diǎn)I的坐標(biāo)。直線V1V5與AB異面，若表示兩線段上距離最近的點(diǎn)所構(gòu)成的向量，則既垂直于 V1V5，也垂直于 AB，故=0，又考慮到V1V5、AB為線段，根據(jù)文獻(xiàn)［11］推得V1V5上距AB最近的點(diǎn)(即插補(bǔ)點(diǎn)I)分有向線段V1V5所成的比例:

圖3從理論上表明，在同樣的網(wǎng)格分辨率下，基于向量場(chǎng)距離函數(shù)的插補(bǔ)算法算得的插補(bǔ)點(diǎn)I比基于標(biāo)量場(chǎng)距離函數(shù)的插補(bǔ)算法算得的插補(bǔ)點(diǎn)更接近原始曲面與立方體網(wǎng)格邊V1V5的交點(diǎn)，因此更加精確。

為證實(shí)這點(diǎn)，針對(duì)圖4(a)中階梯函數(shù)的三角形網(wǎng)孔，在同樣地網(wǎng)格分辨率及相同的空間坐標(biāo)下，分別采樣、計(jì)算其標(biāo)量場(chǎng)距離函數(shù)數(shù)學(xué)模型與向量場(chǎng)距離函數(shù)數(shù)學(xué)模型，然后用標(biāo)準(zhǔn)的MC算法提取該兩場(chǎng)距離函數(shù)模型所表征的曲面，得到圖4(b)基于標(biāo)量場(chǎng)距離函數(shù)提取的三角形網(wǎng)孔、圖4(c)基于標(biāo)量場(chǎng)距離函數(shù)提取的三角形網(wǎng)孔所示結(jié)果。由圖可見(jiàn):由階梯函數(shù)標(biāo)量場(chǎng)距離函數(shù)提取的三角形網(wǎng)孔，圖4(a)中階梯函數(shù)的四個(gè)特征點(diǎn)A、C、D、F，只有A點(diǎn)被保留下來(lái)，另外，在采樣點(diǎn)B、E處函數(shù)也有些變形;而由階梯函數(shù)向量場(chǎng)距離函數(shù)提取的三角形網(wǎng)孔，除特征點(diǎn)C處由于分辨率低的原因稍有變形外，基本保持了階梯函數(shù)的原樣。可見(jiàn)，向量場(chǎng)距離函數(shù)能更精確地表征物體的形面特征。最后，用誤差估算函數(shù)計(jì)算兩提取結(jié)果(b)、(c)相對(duì)于原始階梯函數(shù)(a)的重構(gòu)誤差，分別為0.433和0.360。顯然，基于向量場(chǎng)距離函數(shù)提取的網(wǎng)孔比基于標(biāo)量場(chǎng)距離函數(shù)提取的網(wǎng)孔要精確約16.8%。

圖4 階梯函數(shù)及其三角化網(wǎng)孔

3 算法的實(shí)現(xiàn)

第一步，體元化，即將三角形網(wǎng)孔模型轉(zhuǎn)換為用向量場(chǎng)距離函數(shù)表示的體模型。具體做法如下:將三角形網(wǎng)孔模型置于具有一定分辨率的均勻3D立方體網(wǎng)格中，對(duì)于網(wǎng)格中各立方體的頂點(diǎn)，尋找三角形網(wǎng)孔模型中距離它最近的一點(diǎn)，用有向線段(由各立方體頂點(diǎn)指向三角形網(wǎng)孔模型中距離它最近的點(diǎn))連接該兩點(diǎn)，便得到立方體網(wǎng)格各頂點(diǎn)處的向量場(chǎng)距離函數(shù)值，從而實(shí)現(xiàn)了三角形網(wǎng)孔模型的體元化。

第二步，網(wǎng)格頂點(diǎn)符號(hào)的確定。網(wǎng)格頂點(diǎn)符號(hào)的確定是確保輸出表面封的中至關(guān)重要的一步，通過(guò)求取輸入網(wǎng)孔模型上距某像素最近的點(diǎn)所在三角形面片的表面法向量與之前保存的該像素到輸入網(wǎng)孔模型最近點(diǎn)的3D向量的點(diǎn)積，來(lái)判斷該像素位于隱含封閉表面的內(nèi)部還是外部:如果該點(diǎn)積的值為正，則該像素位于表面內(nèi)部，否則，位于表面外部。

第三步，確定了3D網(wǎng)格各立方體頂點(diǎn)的符號(hào)后，一個(gè)封閉的將不同符號(hào)的立方體網(wǎng)格頂點(diǎn)分在內(nèi)外兩邊的隱含表面也就確定下來(lái)了。此時(shí)，可用線性插補(bǔ)法計(jì)算各立方體的邊(頂點(diǎn)有符號(hào)變化的)與三角形網(wǎng)孔模型的交點(diǎn)，作為后續(xù)輸出表面三角化的頂點(diǎn)。

第四步，以上步中計(jì)算出的各個(gè)插補(bǔ)點(diǎn)位頂點(diǎn)，用MC算法提取隱含表面的輪廓得到系統(tǒng)的最終輸出——消除了各種缺陷的、封閉且法向量一致的三角形網(wǎng)孔表面模型。

4 實(shí)例(結(jié)果)

圖5為用文中算法對(duì)兔CAD模型修復(fù)的結(jié)果。圖5(a)為用3D掃描儀獲取的兔模型的原始網(wǎng)孔模型，由于模型自身的缺陷和掃描儀的局限性，原始網(wǎng)孔模型中通常都存在間隙、孔洞及自交三角形網(wǎng)孔等缺陷，分別如圖5(b)、圖6(a)和圖5(c)細(xì)節(jié)所示。圖5(d)、(e)為用基于向量場(chǎng)距離函數(shù)的體修復(fù)算法對(duì)兔模型間隙和自交網(wǎng)孔修復(fù)后的結(jié)果，與圖5(a)、(c)相比，原始網(wǎng)孔中的間隙與自交現(xiàn)象都得以消除，得到的是封閉、無(wú)自交的三角形網(wǎng)孔。本算法不僅可以消除間隙，對(duì)于大的孔洞也有很好的修復(fù)效果。圖6(a)為原始兔模型的底部，存在著幾個(gè)較大的孔洞，圖6(b)為用文中算法修復(fù)后的結(jié)果，不僅孔洞被填補(bǔ)上了，而且修復(fù)后的封閉網(wǎng)孔在網(wǎng)格分辨率的允許下盡可能地保存了模型的原貌特征。

圖5 間隙、自交及其修復(fù)

圖6 孔洞的修復(fù)

5 結(jié)論

本文給出了一種基于向量場(chǎng)距離函數(shù)的三角形網(wǎng)孔模型體修復(fù)算法，該方法魯棒性好，對(duì)于任意給定的三角形網(wǎng)孔模型，經(jīng)本方法修復(fù)后，總能得到封閉且法向量一致的表面模型。由于算法中體模型使用向量場(chǎng)距離函數(shù)來(lái)表征，相對(duì)于傳統(tǒng)的標(biāo)量場(chǎng)距離函數(shù)而言，修復(fù)的結(jié)果更能體現(xiàn)形面的原貌特征。

［1］ Jun，Yongtae.A piecewise hole filling algorithm in reverse engineering［J］.CAD Computer Aided Design，2005，37(2):263－270.

［2］ Chen haoho，Sung Chunyi，Chen Tsongyi，et al.An efficient hole－filling approach using adaptive rendering［C］.Proceedings－2012 6th International Conference on Genetic and Evolutionary Computing，2012:336 －339.

［3］ Borodin P，Novotni M，Klein R.Progressive gap closing for mesh repairing［J］.Advances in Modelling，Animation and Rendering，2002:201 －213.

［4］ H T Yau，C C Kuo，C H Yeh.Extension of surface reconstruction algorithm to the global stitching and repairing of STL models［J］.Comput.Aided Design，2003，35:477－486.

［5］ Lorensen W，Cline H.Marching cubes:A high resolution 3d surface construction algorithm［J］.Computer Graphics(Proceedings of ACM SIGGRAPH 87)，ACM Press，1987，21:163 －169.

［6］ NOORUDDIN F S ，TURK G.Simplification and repair of polygonal models using volumetric techniques［J］.IEEE Transactions on Visualization and Computer Graphics.2003，9(2):191 －205.

［7］ Frisken S F，Perry R N，Rockwood A P，et al.Adaptively sampled distance fields:A general representation of shape for computer graphics［C］.Proceedings of ACM SIGGRAPH 2000，ACM SIGGRAPH，New York.E.Fiume，Ed.，Computer Graphics Proceedings，Annual Conference Series，ACM，K.Akeley，Ed.，2000:249 －254.

［8］ Passalis G，Kakadiaris I A，Theoharis T.Efficient hardware voxelization［C］.Proceedings of Computer Graphics International Conference，CGI.2004:374 －377.

［9］ Bastos Thiago，Celes Waldemar.GPU － accelerated adaptively sampled distance fields［C］.IEEE International Conference on Shape Modeling and Applications 2008，Proceedings，SMI.2008:171 －178.

［10］ Llamas，Ignacio.Real－ time voxelization of triangle meshes on the GPU［C］.ACM SIGGRAPH 2007 Sketches，SIGGRAPH’07，2007.

［11］ Math Encyclopedia Compiler Committee.Math encyclopedia［M］.Beijing:Science Publishing Press，1995.(in Chinese)數(shù)學(xué)百科全書(shū)編譯委員會(huì).數(shù)學(xué)百科全書(shū)［M］.北京:科學(xué)出版社，1995.