馮 丹，蘇鐵明，華順剛

(大連理工大學 機械工程學院，遼寧 大連 116024)

0 引言

逆向工程已被廣泛應用于機械制造、文物保護、醫(yī)療與虛擬現(xiàn)實等多領域[1，2]。而三維點云曲面重建作為逆向工程的一部分，已經(jīng)成為當今科研領域的研究熱點。近些年，國內(nèi)外學者提出了許多點云曲面重建的算法，主要包括四面體法、隱函數(shù)法、平面投影法、區(qū)域生長法。隱函數(shù)法是通過表面擬合的方法構(gòu)造一個描述模型表面的隱函數(shù)，常用的有泊松算法[3]和徑向基函數(shù)算法[4]，重建的曲面在細節(jié)特征處可能不夠精確，如Edelsbrunner等[5]提出的四面體法是建立包圍點集的立方體盒子，用空外接球法依次插入其他點，得到包含所有點集的凸多面體，該方法涉及到大量的計算，且需要后續(xù)算法對四面體進行提取。區(qū)域生長算法[6]是從種子三角形開始，按照某種原則不斷地選擇第三點和生長邊組成新的三角形等，該方法重建精度良好，但重建結(jié)果依賴于第三點的篩選結(jié)果。平面投影法是將三維點云投影到二維平面內(nèi)進行Delaunay三角剖分[7]，該方法重建速度快但會出現(xiàn)面片重疊以及形狀失真的情況。

本文將平面投影法和區(qū)域生長法進行結(jié)合。首先需要估算每個點的法向量，之后根據(jù)平面投影法對每個點及k鄰域進行投影和生成三角形操作，計算每個點的法向量與k鄰域所有點法向量的夾角，若夾角都小于某閾值，將該點平面投影法生成的三角形存于確定三角形集合T1,否則存于待定三角形集合T2。對T1中的可生長邊，在T2中找到滿足要求的三角形，使其逐步生長成三角網(wǎng)。同時，為保證具有尖銳特征的曲面重建效果良好，使用面夾角準則對生長過程中的三角形進行判斷調(diào)整。上述操作完成后，對仍剩余的點采用區(qū)域生長法進行生長重建。

1 法向量估算

本文采用最小二乘法計算法向量，遍歷點云中的每個點，假設點p的k鄰域可擬合成一平面，設平面方程為ax+by+cz+d=0，其中(a,b,c)為擬合平面的法向量。三維點的坐標為(xi,yi,zi)，可得到矩陣如下：

(1)

(2)

其中：N為點云的數(shù)目。

若點的σj大于C,則標記為1，若小于C標記為0。對標記為1的點，判斷其k鄰域點，若有超過k/2個點標記為1，則將此點與其鄰域點均標記為2，在后續(xù)步驟，用來判斷邊是否需要生長。

2 點云重建

2.1 平面投影與生長步驟

利用上述方法估算出點云法向量后，根據(jù)平面投影法對每個點及k鄰域點進行生成Delaunay三角形操作，保留每個與當前點相連的三角形。接下來需要對三角形分別進行存儲，并進行生長操作。具體算法步驟如下：

(1)對任一點，計算其法向量與k鄰域法向量的夾角，若夾角均小于35°，將這個點根據(jù)平面投影法生成的三角形存于確定三角形集合T1，否則，其生成的三角形存于待定三角形集合T2。其中，若點在計算法向量時被標記為1或2，其平面投影法得到的三角形也存于T2。

(2)在第(1)步中，為防止出現(xiàn)三角面片重疊現(xiàn)象，需要對加入T1的三角形按以下原則進行篩選：①三角形中不包含內(nèi)點(包含此點的邊均不為可生長邊)；②三角形不包含不可生長邊；③最小內(nèi)角大于10°；④二面夾角大于50°。

(3)在T1中找到生長邊，根據(jù)其在T2中滿足要求的相鄰三角形，對其向外生長生成三角形。在生長過程中，先尋找面夾角最大的三角形，若存在與最大面夾角相近的三角形，則選擇邊長更短的三角形。其中，若生長邊兩頂點均為在法向量估算時被標記為2，則此邊不進行生長。

2.2 面夾角最大準則

因為三維點與二維點的不同，在使用平面投影法時，二維平面的三角形還原到三維空間存在不符合棱邊結(jié)構(gòu)的三角形，所以在上述第(3)步生長過程需要采用面夾角準則對三角形進行優(yōu)化，讓其可以與周圍三角形組成棱邊結(jié)構(gòu)。當前邊生長完成后，若調(diào)換以當前生長邊為公共邊的三角形合成的四邊形的對角線后，生成的三角形與四邊形邊共邊的三角形二面夾角更大，則選擇調(diào)換對角線，形成新的三角形。

面夾角判斷如圖1所示，幾個三角形形成棱邊結(jié)構(gòu)，當前生長邊為AD，生長邊所在的四邊形為ABCD。若調(diào)換對角線AD，連接BC，相比于△ABD，△ABC與△ABE的面夾角更大。同樣的，相比于△ADC，△ABC與△AFC面夾角也更大，且更符合棱邊結(jié)構(gòu)。則選擇調(diào)換對角線AD，形成新的三角形△ABC和△BCD來代替原來的三角形。

圖1 面夾角判斷實例

2.3 剩余點的重建

上述操作結(jié)束后，仍剩余的點多數(shù)為奇異點情況，可分為相鄰曲面以及薄壁特征，如圖2所示。相鄰曲面處會因為曲面距離過近出現(xiàn)面片重疊現(xiàn)象，而薄壁特征處曲率突然變化，細節(jié)處重建效果較差，薄壁特征周圍往往伴隨相鄰曲面。

本文對剩余點采用區(qū)域生長法進行生長，每條生長邊的候選點由邊的兩個頂點的k鄰域點組成，可通過以下原則對點進行篩選：①最小內(nèi)角最大；②二面夾角最大；③最大邊長限制。同時因為相鄰曲面距離太小，在對每個點選取k鄰域時，會選到其他曲面的點，所以在區(qū)域生長篩選過程中，可以先將大多數(shù)屬于其他曲面的點篩掉。

將生長邊與候選點組成的三角形分為向內(nèi)生長三角形與向外生長三角形，可以通過計算生長邊所在三角形的法向量n與生長邊與候選點組成的三角形之間的角度來判斷。若角度小于90°，生成的三角形為向外生長；否則，為向內(nèi)生長。

如圖3所示，BC為生長邊，D為候選點，需要計算△ABC的法向量n1與△BCD之間的角度，可以通過計算n1與△BCD的高(即向量ED)之間的夾角來獲得。而對于如圖2(a)所示的相鄰曲面，其三角形生長情況如圖4所示，△ABC為向內(nèi)生長三角形，△ABD為向外生長三角形。把大部分可以形成向外生長三角形的候選點篩掉，可以防止選到其他曲面的點，生成錯誤的拓撲結(jié)構(gòu)。

圖2 奇異點情況

圖3 向外、向內(nèi)生長判別示例 圖4 相鄰曲面三角形生長情況

3 實驗及結(jié)果分析

采用平面投影法和本文算法的cat重建如圖5所示。由圖5可以看出：與圖5(a)相比，圖5(b)中cat點云尾巴處重建效果良好,沒有三角面片重疊。

圖5 采用平面投影法和本文算法的cat重建

采用平面投影法和本文算法的part重建如圖6所示。從圖6可以看出：part點云在使用平面投影方法重建時有邊緣凹陷現(xiàn)象，而使用本文算法重建的各個棱邊結(jié)構(gòu)明顯，無錯誤連接。

圖6 采用平面投影法和本文算法的part重建

采用本文算法重建的其他點云模型如圖7所示。由圖7可以看出，采用本文算法所重建的各點云模型效果良好。

圖7 點云模型重建示例

4 結(jié)束語

(1)本算法結(jié)合了平面投影法與區(qū)域生長的優(yōu)點，重建速度相比區(qū)域生長要快，而重建精度要比平面投影法高。

(2)在區(qū)域生長過程時使用面夾角準則，對于棱邊、棱角等尖銳特征處，重建結(jié)果良好。