高精度自適應的四邊形網格重建

劉 麗 ， 呂 雪， 伯彭波

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

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

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

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

海量數據點集的網格重建方法中常用的主要衡量標準：降噪和剔除離群點；保持物體原狀，特別是尖銳特征；封閉的網格拓撲；根據表面的復雜程度自適應調節網格分布；網格盡量滿足最優原則。根據這些原則，本文提出了一種新的四邊形網格重建算法，不僅能夠滿足上述網格重建標準，而且可以根據精度要求調整網格密度。

1 相關定義及說明

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

為了保證拓撲結構正確，體現數據點集的空洞，定義立方體邊長size的取值范圍為

1.1 定義

邊長size必須控制在一定范圍內，這是因為如果立方體邊長size過小，相鄰數據點可能被劃分在不相鄰的立方體內；反之，如果邊長size過大，不同區域的數據點，甚至之間存在空洞的數據點可能被劃分在相鄰或同一個立方體內。根據網格的生成規則，前一種情況中的重建網格不連續，后一種情況中的重建網格把空洞給填充，改變了數據點集的拓撲結構。

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

圖1 網格頂點的離散曲率

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

當jα為鈍角時

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

1.2 部分原則

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

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

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

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

圖2 面片的局部細分

均勻劃分海量數據點集的最小包圍盒，重建網格的密度較為均勻，不能充分體現細節特征。通過對多邊形網格進行自適應的局部細分，增加彎曲程度較大區域的網格密度。

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

（1）設面片 f中的網格頂點為 v1, v2,…,vn，則相應的新面點為

（2）設相鄰面片 fi,fj的新面點為vfacei，vfacej，公共邊端點為v1,v2，則相應的新邊點為

（3）設邊界邊的兩端點為v1,v2，則相應的新邊點為

將新面點與周圍的新邊點相連，建立新的拓撲結構，得到海量數據點集的四邊形重建網格。

2 算法實現

2.1 算法流程

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

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

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

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

步驟4 對步驟3中的多邊形面片進行整體細分，使之全部轉化為四邊形面片，并對四邊形面片進行優化，分裂度較大的網格頂點。

2.2 算法拓展

1）數據簡化

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

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

圖3 數據點簡化的3種方法

2）網格生成

連接立方體內的簡化點生成多邊形網格，連接規則如下：如果與立方體V面相鄰的立方體Vface內有數據點集，則把V內的簡化點與Vface內的簡化點相連；否則如果與立方體V邊相鄰且與立方體Vface面相鄰的立方體Vedge內有數據點，則把V內的簡化點與Vedge內的簡化點相連。

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

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

圖4 懸面和懸邊

3）網格優化

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

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

網格頂點d, e分別在區域M, N內，位置由所在區域的多邊形網格決定

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

圖5 頂點分裂

表1 分裂網格頂點度的變化

3 應用實例

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

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

圖8(a)中數據點集的個數為96847個，圖8(b),(c)是圖 8(a)中數據點集的不同分辨率的重構網格。圖9(a)中數據點的個數為298353個，圖9(b)是圖9(a)中數據點集的重構網格。

圖6 海量數據點集網格重構的主要步驟

圖7 網格重建實驗結果之一

圖8 網格重建實驗結果之二

圖9 網格重建實驗結果之三

通過對實例中重構網格的分析可知，立方體邊長size在式(1)的范圍內，對復雜拓撲的海量數據點集，本文算法都可以重建出拓撲結構正量數據點集，本文算法都可以重建出拓撲結構正確、細節特征明顯的多分辨率網格。另外，在實驗中發現，采樣數據點越均勻，重建的四邊形網格質量越好。

4 結 論

本文提出的海量數據點集的四邊形網格重建算法，只需給出物體表面數據點的位置信息，不需要法向、曲面邊界等附加信息，就可以重建出復雜拓撲的四邊形網格。本文算法具有提高重建網格精度，降低構造曲面片難度等優點，有較大的實用價值。今后的工作主要是實現多視圖、多基點、變分辨率測量數據的坐標歸一化，以及根據重建網格構造C1連續的曲面片。

[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.