高精度自適應(yīng)的四邊形網(wǎng)格重建

劉 麗 ， 呂 雪， 伯彭波

（1. 山東師范大學(xué)信息科學(xué)與工程學(xué)院，山東 濟(jì)南 250014；2. 山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 濟(jì)南 250014；3. 香港大學(xué)計(jì)算機(jī)科學(xué)系，香港）

隨著計(jì)算機(jī)輔助設(shè)計(jì)與制造技術(shù)的迅速發(fā)展，逆向工程技術(shù)在工業(yè)領(lǐng)域得到越來(lái)越廣泛的應(yīng)用。逆向工程技術(shù)在對(duì)已有的機(jī)械零部件進(jìn)行復(fù)制，特別是在引進(jìn)產(chǎn)品的國(guó)產(chǎn)化和備品備件的制作方面都有重要意義。海量數(shù)據(jù)點(diǎn)集的重構(gòu)方法很多[1-6]，其中網(wǎng)格曲面作為一種曲面表示形式由于具有簡(jiǎn)單、統(tǒng)一的優(yōu)點(diǎn)，已經(jīng)成為重要的曲面表示方法。

Hoppe[7]提出通過(guò)采樣點(diǎn)的局部信息自動(dòng)計(jì)算各點(diǎn)處的法向信息，利用切平面線性逼近待重建曲面的局部模型，建立離散點(diǎn)集的距離場(chǎng)函數(shù)，然后用等值面抽取的MC算法得到三角片逼近曲面。Amenta[8]通過(guò)構(gòu)造采樣點(diǎn)集的三維Voronoi圖，利用Delaunay三角化方法來(lái)重建網(wǎng)格曲面。Bradley[9]提出了一種依賴種子點(diǎn)增長(zhǎng)的網(wǎng)格曲面重建算法。從選定的種子點(diǎn)開(kāi)始，通過(guò)后選點(diǎn)與當(dāng)前網(wǎng)格的可見(jiàn)關(guān)系來(lái)判斷該點(diǎn)是否在網(wǎng)格上以及確定它的連接關(guān)系，最終獲得一張或多張網(wǎng)格曲面。Floater[10]提出了無(wú)網(wǎng)格參數(shù)化的曲面重建算法。首先將原點(diǎn)初始數(shù)據(jù)點(diǎn)集投影到平面上，運(yùn)用平面Delaunay三角化方法將投影點(diǎn)集分割成若干三角形，從而得到點(diǎn)集的連接關(guān)系，最后通過(guò)映射點(diǎn)集的連接關(guān)系確定初始點(diǎn)集的拓?fù)溥B接。

上述算法都是基于三角形網(wǎng)格，為提高有限元分析的精度，出現(xiàn)了四邊形網(wǎng)格的曲面重建。最簡(jiǎn)單的四邊形網(wǎng)格曲面重建算法就是將相鄰對(duì)三角形結(jié)合成一個(gè)四邊形，三角形結(jié)合的順序影響網(wǎng)格的質(zhì)量。Lee等[11-13]就三角形結(jié)合順序給出了幾個(gè)啟發(fā)式的步驟，生成了四邊形占優(yōu)的網(wǎng)格，減少孤立三角形的數(shù)量。這種方法的缺點(diǎn)是存在不規(guī)則節(jié)點(diǎn)，不能保證單元沿邊界排列。Zhu[14]利用波前法生成四邊形網(wǎng)格，首先在邊界產(chǎn)生初始節(jié)點(diǎn)，再利用波前生成三角形網(wǎng)格，然后合并三角形生成四邊形網(wǎng)格。Blacker和Roger等人[15]提出了一種生成四邊形網(wǎng)格的Paving方法，由外向內(nèi)生成成排的單元，在特殊區(qū)域進(jìn)行相交判斷。但是只能解決邊界點(diǎn)為偶數(shù)的有限元網(wǎng)格重建問(wèn)題。

海量數(shù)據(jù)點(diǎn)集的網(wǎng)格重建方法中常用的主要衡量標(biāo)準(zhǔn)：降噪和剔除離群點(diǎn)；保持物體原狀，特別是尖銳特征；封閉的網(wǎng)格拓?fù)?；根?jù)表面的復(fù)雜程度自適應(yīng)調(diào)節(jié)網(wǎng)格分布；網(wǎng)格盡量滿足最優(yōu)原則。根據(jù)這些原則，本文提出了一種新的四邊形網(wǎng)格重建算法，不僅能夠滿足上述網(wǎng)格重建標(biāo)準(zhǔn)，而且可以根據(jù)精度要求調(diào)整網(wǎng)格密度。

1 相關(guān)定義及說(shuō)明

定義1 數(shù)據(jù)點(diǎn)集S內(nèi)任意數(shù)據(jù)點(diǎn)pi，都存在另外數(shù)據(jù)點(diǎn)pj，使成立，則稱數(shù)據(jù)點(diǎn)集S的采樣密度為δ。如果采樣密度為δ的數(shù)據(jù)點(diǎn)集中存在半徑大于δ的球體內(nèi)沒(méi)有數(shù)據(jù)點(diǎn)，則認(rèn)為該區(qū)域?yàn)榭斩础?/p>

為了保證拓?fù)浣Y(jié)構(gòu)正確，體現(xiàn)數(shù)據(jù)點(diǎn)集的空洞，定義立方體邊長(zhǎng)size的取值范圍為

1.1 定義

邊長(zhǎng)size必須控制在一定范圍內(nèi)，這是因?yàn)槿绻⒎襟w邊長(zhǎng)size過(guò)小，相鄰數(shù)據(jù)點(diǎn)可能被劃分在不相鄰的立方體內(nèi)；反之，如果邊長(zhǎng)size過(guò)大，不同區(qū)域的數(shù)據(jù)點(diǎn)，甚至之間存在空洞的數(shù)據(jù)點(diǎn)可能被劃分在相鄰或同一個(gè)立方體內(nèi)。根據(jù)網(wǎng)格的生成規(guī)則，前一種情況中的重建網(wǎng)格不連續(xù)，后一種情況中的重建網(wǎng)格把空洞給填充，改變了數(shù)據(jù)點(diǎn)集的拓?fù)浣Y(jié)構(gòu)。

定義 2 曲面上某點(diǎn)的高斯曲率為該點(diǎn)兩個(gè)主曲率的乘積，反映了曲面局部的彎曲程度。四邊形網(wǎng)格頂點(diǎn)的離散高斯曲率求解，利用離散微分幾何，由直接相連的網(wǎng)格頂點(diǎn)構(gòu)成的三角網(wǎng)格估計(jì)（如圖1），忽略對(duì)角頂點(diǎn)對(duì)其曲率的影響。

圖1 網(wǎng)格頂點(diǎn)的離散曲率

其中，A表示頂點(diǎn)pi所在三角形面積的和，n-1表示頂點(diǎn)pi所在三角形的個(gè)數(shù)。當(dāng)jα為銳角時(shí)，

當(dāng)jα為鈍角時(shí)

1）面片抽取的最小環(huán)原則 在網(wǎng)格中以頂點(diǎn)vi開(kāi)始，沿著多邊形網(wǎng)格的邊vivj尋找到下一個(gè)頂點(diǎn)vj，重復(fù)迭代該過(guò)程，直到回到頂點(diǎn)vi為止。此時(shí)，封閉頂點(diǎn)形成的多邊形即為抽取面片。從頂點(diǎn)vi開(kāi)始再回到頂點(diǎn)vi的封閉路徑很多，這些封閉路徑形成的面片頂點(diǎn)存在包含關(guān)系，尋找最小頂點(diǎn)集合的封閉路徑。

1.2 部分原則

點(diǎn)集S′?S，這就是最小環(huán)原則。在面片抽取過(guò)程中遵循最小環(huán)原則，保證多邊形面片中不能再抽取出邊數(shù)更少的面片，消除面片重疊。

2）局部細(xì)分原則 如果網(wǎng)格頂點(diǎn)pi的離散高斯曲率 k ＞εsub，對(duì)共享該點(diǎn)的面片進(jìn)行局部細(xì)分。需要注意的是尖點(diǎn)及折疊邊上的頂點(diǎn)即使經(jīng)過(guò)多次細(xì)分，曲率變化仍然不是很大，這可能造成細(xì)分無(wú)限延續(xù)，因此定義共享頂點(diǎn)pi的網(wǎng)格進(jìn)行局部細(xì)分的條件為：第一，細(xì)分次數(shù)不大于4；第二，頂點(diǎn)的離散曲率 k ＞εsub。

對(duì)共享頂點(diǎn)pi的面片 fi細(xì)分，新頂點(diǎn)vi表示如下

其中，n表示面片 fi的頂點(diǎn)數(shù)。細(xì)分頂點(diǎn)vi與面片 fi中各個(gè)頂點(diǎn)相連生成三角形面片，刪除共享頂點(diǎn)pi的相鄰面片 fi,fj的公共邊，如圖2所示。

圖2 面片的局部細(xì)分

均勻劃分海量數(shù)據(jù)點(diǎn)集的最小包圍盒，重建網(wǎng)格的密度較為均勻，不能充分體現(xiàn)細(xì)節(jié)特征。通過(guò)對(duì)多邊形網(wǎng)格進(jìn)行自適應(yīng)的局部細(xì)分，增加彎曲程度較大區(qū)域的網(wǎng)格密度。

3）整體細(xì)分原則 為使多邊形網(wǎng)格轉(zhuǎn)化為四邊形網(wǎng)格，對(duì)多邊形網(wǎng)格做整體細(xì)分。其中，網(wǎng)格頂點(diǎn)保持不變，新面點(diǎn)vface和新邊點(diǎn)vedge的計(jì)算如下：

（1）設(shè)面片 f中的網(wǎng)格頂點(diǎn)為 v1, v2,…,vn，則相應(yīng)的新面點(diǎn)為

（2）設(shè)相鄰面片 fi,fj的新面點(diǎn)為vfacei，vfacej，公共邊端點(diǎn)為v1,v2，則相應(yīng)的新邊點(diǎn)為

（3）設(shè)邊界邊的兩端點(diǎn)為v1,v2，則相應(yīng)的新邊點(diǎn)為

將新面點(diǎn)與周?chē)男逻咟c(diǎn)相連，建立新的拓?fù)浣Y(jié)構(gòu)，得到海量數(shù)據(jù)點(diǎn)集的四邊形重建網(wǎng)格。

2 算法實(shí)現(xiàn)

2.1 算法流程

算法采用八叉樹(shù)空間分割的結(jié)構(gòu)，使得對(duì)于點(diǎn)的搜索無(wú)須遍歷整個(gè)點(diǎn)集，只要在當(dāng)前立方體區(qū)域及其鄰域查找，節(jié)省了搜尋時(shí)間。

步驟1 均勻分割與坐標(biāo)軸平行的最小包圍盒，得到l×m× n個(gè)邊長(zhǎng)為size的立方體。設(shè)包圍盒沿X,Y,Z軸方向的最小坐標(biāo)為,，最大坐標(biāo)為，則立方體（i,j,k為立方體沿X,Y,Z軸方向的索引號(hào)）表示為

步驟2 簡(jiǎn)化立方體Bi,j,k內(nèi)的數(shù)據(jù)點(diǎn)集，按一定規(guī)則連接相鄰立方體內(nèi)的簡(jiǎn)化點(diǎn)，生成多邊形網(wǎng)格。計(jì)算網(wǎng)格頂點(diǎn)的離散高斯曲率，刪除頂點(diǎn)離散曲率 k ＜εdel且刪除該點(diǎn)形成的新網(wǎng)格的邊數(shù)小于等于6的頂點(diǎn)（對(duì)于邊數(shù)大于6的網(wǎng)格認(rèn)為是空洞，不予處理）。

步驟3 按照最小環(huán)原則從步驟2中的網(wǎng)格中抽取多邊形面片，計(jì)算網(wǎng)格頂點(diǎn)的離散高斯曲率，對(duì)滿足局部細(xì)分條件的多邊形面片進(jìn)行局部細(xì)分。

步驟4 對(duì)步驟3中的多邊形面片進(jìn)行整體細(xì)分，使之全部轉(zhuǎn)化為四邊形面片，并對(duì)四邊形面片進(jìn)行優(yōu)化，分裂度較大的網(wǎng)格頂點(diǎn)。

2.2 算法拓展

1）數(shù)據(jù)簡(jiǎn)化

在海量數(shù)據(jù)點(diǎn)集的重建過(guò)程中，大量的數(shù)據(jù)點(diǎn)不利于存儲(chǔ)、操作以及重建，嚴(yán)重影響重建算法的效率，因此對(duì)數(shù)據(jù)點(diǎn)集進(jìn)行簡(jiǎn)化。此外，通過(guò)對(duì)數(shù)據(jù)點(diǎn)集的簡(jiǎn)化，減少了采樣噪音對(duì)重建網(wǎng)格的影響。

簡(jiǎn)化立方體內(nèi)數(shù)據(jù)點(diǎn)的方法主要有：第一，每個(gè)立方體內(nèi)離中心最近的數(shù)據(jù)點(diǎn)作為簡(jiǎn)化點(diǎn)，這種方法的好處是重建網(wǎng)格大致均勻，缺點(diǎn)是沒(méi)有充分考慮立方體內(nèi)數(shù)據(jù)點(diǎn)的分布，如圖3(a)所示；第二，每個(gè)立方體內(nèi)數(shù)據(jù)點(diǎn)的平均值點(diǎn)作為簡(jiǎn)化點(diǎn)，這種方法雖然考慮了數(shù)據(jù)點(diǎn)的分布情況，但重建網(wǎng)格往往不均勻，如圖3(b)所示。為了更好地體現(xiàn)立方體內(nèi)數(shù)據(jù)點(diǎn)集的分布，且使網(wǎng)格形狀較為均勻，定義簡(jiǎn)化點(diǎn)Vi,j,k為

圖3 數(shù)據(jù)點(diǎn)簡(jiǎn)化的3種方法

2）網(wǎng)格生成

連接立方體內(nèi)的簡(jiǎn)化點(diǎn)生成多邊形網(wǎng)格，連接規(guī)則如下：如果與立方體V面相鄰的立方體Vface內(nèi)有數(shù)據(jù)點(diǎn)集，則把V內(nèi)的簡(jiǎn)化點(diǎn)與Vface內(nèi)的簡(jiǎn)化點(diǎn)相連；否則如果與立方體V邊相鄰且與立方體Vface面相鄰的立方體Vedge內(nèi)有數(shù)據(jù)點(diǎn)，則把V內(nèi)的簡(jiǎn)化點(diǎn)與Vedge內(nèi)的簡(jiǎn)化點(diǎn)相連。

相鄰立方體內(nèi)數(shù)據(jù)點(diǎn)連接的優(yōu)先級(jí)為面相鄰的優(yōu)先級(jí)大于邊相鄰的優(yōu)先級(jí)。重建網(wǎng)格中大多數(shù)為四邊形，此外還包含了少許的三角形網(wǎng)格、五邊形網(wǎng)格和六邊形網(wǎng)格，以及其他形狀的網(wǎng)格。在這里至多考慮六邊形網(wǎng)格，對(duì)于邊數(shù)大于六邊形的網(wǎng)格區(qū)域認(rèn)為是空洞，不予處理。

由于數(shù)據(jù)點(diǎn)集自身拓?fù)浣Y(jié)構(gòu)的復(fù)雜，以及掃描過(guò)程中的誤差等原因，重建網(wǎng)格可能會(huì)出現(xiàn)懸面（如圖4(a)）和懸邊（如圖4(b)）。產(chǎn)生的懸面無(wú)法判斷是否是掃描物體本身的形狀，因此予以保留。但是，懸邊是不允許出現(xiàn)的，若某個(gè)頂點(diǎn)只有一條邊與之相連，則刪除該頂點(diǎn)及其相連的邊，保證重建網(wǎng)格拓?fù)浣Y(jié)構(gòu)正確。

圖4 懸面和懸邊

3）網(wǎng)格優(yōu)化

根據(jù)生成多邊形網(wǎng)格的連接規(guī)則，每個(gè)簡(jiǎn)化點(diǎn)至多和它周?chē)?個(gè)數(shù)據(jù)點(diǎn)相連。定義網(wǎng)格中頂點(diǎn)v的度是和v相關(guān)聯(lián)的邊的數(shù)目，則多邊形網(wǎng)格頂點(diǎn)的度最多為6。在網(wǎng)格局部細(xì)分的過(guò)程中，每細(xì)分一次，部分網(wǎng)格頂點(diǎn)的度增加1，限制網(wǎng)格局部細(xì)分的次數(shù)不大于4，則網(wǎng)格頂點(diǎn)的度至多為10。對(duì)多邊形網(wǎng)格進(jìn)行整體細(xì)分，原網(wǎng)格頂點(diǎn)的度不變，三角形、四邊形、五邊形和六邊形面片的新細(xì)分頂點(diǎn)的度分別為3，4，5，6，因此整個(gè)四邊形網(wǎng)格頂點(diǎn)的最大度為10。

頂點(diǎn)度過(guò)大會(huì)在頂點(diǎn)周?chē)a(chǎn)生質(zhì)量較差的網(wǎng)格，為改善這些局部區(qū)域的網(wǎng)格質(zhì)量，減少頂點(diǎn)的度，在算法中引入拓?fù)鋬?yōu)化操作，將度較大的頂點(diǎn)分裂為兩個(gè)新頂點(diǎn)。度為nc的網(wǎng)格頂點(diǎn)c，與頂點(diǎn)c相連的頂點(diǎn)a，從頂點(diǎn)a沿順時(shí)針，將頂點(diǎn)c的網(wǎng)格分成兩部分M 和N（如圖5）。分裂網(wǎng)格頂點(diǎn)c，生成新的頂點(diǎn)d, e，連接頂點(diǎn)a, b, d, e生成新的四邊形網(wǎng)格。頂點(diǎn)c分裂后，新網(wǎng)格頂點(diǎn)的度為

網(wǎng)格頂點(diǎn)d, e分別在區(qū)域M, N內(nèi)，位置由所在區(qū)域的多邊形網(wǎng)格決定

其中，m,n分別為區(qū)域M,N內(nèi)共享頂點(diǎn)c的四邊形網(wǎng)格的個(gè)數(shù)，pi為四邊形網(wǎng)格的質(zhì)心。分裂重建的四邊形網(wǎng)格中度較大的頂點(diǎn)，使頂點(diǎn)的度都不大于6（如表1），改善局部區(qū)域的網(wǎng)格質(zhì)量。

圖5 頂點(diǎn)分裂

表1 分裂網(wǎng)格頂點(diǎn)度的變化

3 應(yīng)用實(shí)例

下列是對(duì)文物掃描數(shù)據(jù)點(diǎn)集進(jìn)行四邊形網(wǎng)格重建的例子，掃描數(shù)據(jù)點(diǎn)只有位置信息。圖6全景式地說(shuō)明了四邊形網(wǎng)格生成的主要步驟，其中數(shù)據(jù)點(diǎn)集的個(gè)數(shù)為210963個(gè)。

圖7～圖9是圖中數(shù)據(jù)點(diǎn)集重構(gòu)的例子。圖7中立方體邊長(zhǎng)size適合的范圍為9.2～17.5。圖7(b)中相鄰數(shù)據(jù)點(diǎn)被分割在包圍盒中不相鄰的立方體內(nèi)，連接規(guī)則只連接相鄰數(shù)據(jù)點(diǎn)，因此重構(gòu)的四邊形網(wǎng)格不連續(xù)。圖7(c)是罐子的罐口，由于立方體邊長(zhǎng)size過(guò)大，罐口的數(shù)據(jù)點(diǎn)被分割在包圍盒中相鄰的立方體內(nèi)，根據(jù)連接規(guī)則這些數(shù)據(jù)點(diǎn)相連生成新邊，將罐口的空洞部分封閉起來(lái)，導(dǎo)致拓?fù)浣Y(jié)果錯(cuò)誤。

圖8(a)中數(shù)據(jù)點(diǎn)集的個(gè)數(shù)為96847個(gè)，圖8(b),(c)是圖 8(a)中數(shù)據(jù)點(diǎn)集的不同分辨率的重構(gòu)網(wǎng)格。圖9(a)中數(shù)據(jù)點(diǎn)的個(gè)數(shù)為298353個(gè)，圖9(b)是圖9(a)中數(shù)據(jù)點(diǎn)集的重構(gòu)網(wǎng)格。

圖6 海量數(shù)據(jù)點(diǎn)集網(wǎng)格重構(gòu)的主要步驟

圖7 網(wǎng)格重建實(shí)驗(yàn)結(jié)果之一

圖8 網(wǎng)格重建實(shí)驗(yàn)結(jié)果之二

圖9 網(wǎng)格重建實(shí)驗(yàn)結(jié)果之三

通過(guò)對(duì)實(shí)例中重構(gòu)網(wǎng)格的分析可知，立方體邊長(zhǎng)size在式(1)的范圍內(nèi)，對(duì)復(fù)雜拓?fù)涞暮Ａ繑?shù)據(jù)點(diǎn)集，本文算法都可以重建出拓?fù)浣Y(jié)構(gòu)正量數(shù)據(jù)點(diǎn)集，本文算法都可以重建出拓?fù)浣Y(jié)構(gòu)正確、細(xì)節(jié)特征明顯的多分辨率網(wǎng)格。另外，在實(shí)驗(yàn)中發(fā)現(xiàn)，采樣數(shù)據(jù)點(diǎn)越均勻，重建的四邊形網(wǎng)格質(zhì)量越好。

4 結(jié) 論

本文提出的海量數(shù)據(jù)點(diǎn)集的四邊形網(wǎng)格重建算法，只需給出物體表面數(shù)據(jù)點(diǎn)的位置信息，不需要法向、曲面邊界等附加信息，就可以重建出復(fù)雜拓?fù)涞乃倪呅尉W(wǎng)格。本文算法具有提高重建網(wǎng)格精度，降低構(gòu)造曲面片難度等優(yōu)點(diǎn)，有較大的實(shí)用價(jià)值。今后的工作主要是實(shí)現(xiàn)多視圖、多基點(diǎn)、變分辨率測(cè)量數(shù)據(jù)的坐標(biāo)歸一化，以及根據(jù)重建網(wǎng)格構(gòu)造C1連續(xù)的曲面片。

[1]Kazhdan M. Reconstruction of solid models from oriented point sets [M]. Eurographics Symposium on Geometry Processing, 2005: 73-82.

[2]Zhao H, Osher S, Fedkiw R. Fast surface reconstruction using the level set method [C]//1st IEEE Workshop on Variational and Level Set Methods, 2001: 194-202.

[3]Doi A, Fujiwara S, Matsuda K, et al. 3D Volume extraction and mesh generation using energy minimization techniques [C]//1st IEEE International Symposium on 3D Data Procession Visualization and Transmission, 2002: 83-86.

[4]Lin Hongwei, Tai Chiewlan, Wang Guojin. A mesh reconstruction algorithm driven by an intrinsic property of a point cloud [J]. Computer-Aided Design,2004, 36(1): 1-9.

[5]Sergei A, Anath F. Efficient surface reconstruction method for distributed CAD [J]. Computer Aided Design, 2004, 36(2): 799-808.

[6]Habbib A, Warren J. Edge and vertex insertion for a class of C1 subdivision surfaces [J]. Computer Aided Geometry, 2004, 16(4): 223-247.

[7]Hoppe H, DeRose T, Duchamp T, et al. Surface reconstruction from unorganized points [J]. Computer Graphics, 1992, 26(2): 71-76.

[8]Amenta N, Bern M, Kamvysselis M. A new Voronoi-based surface reconstruction algorithm [C]//Proc of ACM SIGGRAPH’98. Orlando, 1998: 415-421.

[9]Bradley C. Rapid prototyping models generated from machine vision data [J]. Computers in Industry, 2001,41: 159-173.

[10]Floater M S, Riemers M. Meshless parameterization and surface reconstruction [J]. Computer Aided Geometric Design, 2001, 18(3): 77-92.

[11]Lo S H. Generating quadrilateral elements on plane and over curved surfaces [J]. Computers and Structures, 1989, 31(3): 421-426.

[12]Bruce P, John M, Andrew K. Automatic conversion of triangular finite element meshes to quadrilateral elements [J]. International Journal for Numerical Methods in Engineering, 1991, 31: 67-84.

[13]Lee C K, Lo S H. A new scheme for the generation of a graded quadrilateral mesh [J]. Computers and Structures, 1994, 52: 847-857.

[14]Zhu J Z, Zienkiewiez O C. A new approach to the development of automatic quadrilateral mesh generation [J]. International Journal for Numerical Methods in Engineering, 1991, 32: 849-866.

[15]Blacker D. Michael B. Paving: a new approach to automated quadrilateral mesh generation [J].International Journal for Numerical Methods in Engineering, 1991, 32: 811-847.