劉 麗 ， 呂 雪， 伯彭波

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

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

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

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

海量數(shù)據(jù)點集的網(wǎng)格重建方法中常用的主要衡量標(biāo)準(zhǔn)：降噪和剔除離群點；保持物體原狀，特別是尖銳特征；封閉的網(wǎng)格拓撲；根據(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)定義及說明

定義1 數(shù)據(jù)點集S內(nèi)任意數(shù)據(jù)點pi，都存在另外數(shù)據(jù)點pj，使成立，則稱數(shù)據(jù)點集S的采樣密度為δ。如果采樣密度為δ的數(shù)據(jù)點集中存在半徑大于δ的球體內(nèi)沒有數(shù)據(jù)點，則認為該區(qū)域為空洞。

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

1.1 定義

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

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

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

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

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

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

1.2 部分原則

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

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

對共享頂點pi的面片 fi細分，新頂點vi表示如下

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

圖2 面片的局部細分

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

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

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

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

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

將新面點與周圍的新邊點相連，建立新的拓撲結(jié)構(gòu)，得到海量數(shù)據(jù)點集的四邊形重建網(wǎng)格。

2 算法實現(xiàn)

2.1 算法流程

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

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

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

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

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

2.2 算法拓展

1）數(shù)據(jù)簡化

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

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

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

2）網(wǎng)格生成

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

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

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

圖4 懸面和懸邊

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

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

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

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

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

圖5 頂點分裂

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

3 應(yīng)用實例

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

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

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

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

圖7 網(wǎng)格重建實驗結(jié)果之一

圖8 網(wǎng)格重建實驗結(jié)果之二

圖9 網(wǎng)格重建實驗結(jié)果之三

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

4 結(jié) 論

本文提出的海量數(shù)據(jù)點集的四邊形網(wǎng)格重建算法，只需給出物體表面數(shù)據(jù)點的位置信息，不需要法向、曲面邊界等附加信息，就可以重建出復(fù)雜拓撲的四邊形網(wǎng)格。本文算法具有提高重建網(wǎng)格精度，降低構(gòu)造曲面片難度等優(yōu)點，有較大的實用價值。今后的工作主要是實現(xiàn)多視圖、多基點、變分辨率測量數(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.