一種結(jié)合平面投影和區(qū)域生長(zhǎng)的曲面重建算法

馮 丹，蘇鐵明，華順剛

(大連理工大學(xué) 機(jī)械工程學(xué)院，遼寧 大連 116024)

0 引言

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

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

1 法向量估算

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

(1)

(2)

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

若點(diǎn)的σj大于C,則標(biāo)記為1，若小于C標(biāo)記為0。對(duì)標(biāo)記為1的點(diǎn)，判斷其k鄰域點(diǎn)，若有超過(guò)k/2個(gè)點(diǎn)標(biāo)記為1，則將此點(diǎn)與其鄰域點(diǎn)均標(biāo)記為2，在后續(xù)步驟，用來(lái)判斷邊是否需要生長(zhǎng)。

2 點(diǎn)云重建

2.1 平面投影與生長(zhǎng)步驟

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

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

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

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

2.2 面夾角最大準(zhǔn)則

因?yàn)槿S點(diǎn)與二維點(diǎn)的不同，在使用平面投影法時(shí)，二維平面的三角形還原到三維空間存在不符合棱邊結(jié)構(gòu)的三角形，所以在上述第(3)步生長(zhǎng)過(guò)程需要采用面夾角準(zhǔn)則對(duì)三角形進(jìn)行優(yōu)化，讓其可以與周?chē)切谓M成棱邊結(jié)構(gòu)。當(dāng)前邊生長(zhǎng)完成后，若調(diào)換以當(dāng)前生長(zhǎng)邊為公共邊的三角形合成的四邊形的對(duì)角線后，生成的三角形與四邊形邊共邊的三角形二面夾角更大，則選擇調(diào)換對(duì)角線，形成新的三角形。

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

圖1 面夾角判斷實(shí)例

2.3 剩余點(diǎn)的重建

上述操作結(jié)束后，仍剩余的點(diǎn)多數(shù)為奇異點(diǎn)情況，可分為相鄰曲面以及薄壁特征，如圖2所示。相鄰曲面處會(huì)因?yàn)榍婢嚯x過(guò)近出現(xiàn)面片重疊現(xiàn)象，而薄壁特征處曲率突然變化，細(xì)節(jié)處重建效果較差，薄壁特征周?chē)殡S相鄰曲面。

本文對(duì)剩余點(diǎn)采用區(qū)域生長(zhǎng)法進(jìn)行生長(zhǎng)，每條生長(zhǎng)邊的候選點(diǎn)由邊的兩個(gè)頂點(diǎn)的k鄰域點(diǎn)組成，可通過(guò)以下原則對(duì)點(diǎn)進(jìn)行篩選：①最小內(nèi)角最大；②二面夾角最大；③最大邊長(zhǎng)限制。同時(shí)因?yàn)橄噜徢婢嚯x太小，在對(duì)每個(gè)點(diǎn)選取k鄰域時(shí)，會(huì)選到其他曲面的點(diǎn)，所以在區(qū)域生長(zhǎng)篩選過(guò)程中，可以先將大多數(shù)屬于其他曲面的點(diǎn)篩掉。

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

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

圖2 奇異點(diǎn)情況

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

圖7 點(diǎn)云模型重建示例

4 結(jié)束語(yǔ)

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

(2)在區(qū)域生長(zhǎng)過(guò)程時(shí)使用面夾角準(zhǔn)則，對(duì)于棱邊、棱角等尖銳特征處，重建結(jié)果良好。