李 松 馬聰聰 陸 帆 曹菁菁 周 勇

武漢理工大學(xué)物流工程學(xué)院，武漢，430063

0 引言

文物受自然環(huán)境、人為活動的影響，表面極易出現(xiàn)孔洞、殘缺。為減少傳統(tǒng)接觸式修復(fù)方法對文物的二次破壞，人們采用三維掃描系統(tǒng)對文物模型進(jìn)行數(shù)據(jù)采集，以指導(dǎo)后面的修復(fù)。受測量技術(shù)與精度的限制、文物自身形狀與缺陷等因素的影響，被掃描物體的點(diǎn)云模型易出現(xiàn)孔洞?？锥雌茐牧宋奈锏耐暾?，對后續(xù)數(shù)據(jù)的處理也產(chǎn)生較大影響，因此，對模型孔洞進(jìn)行修補(bǔ)是逆向工程中十分重要的環(huán)節(jié)。

針對網(wǎng)格模型孔洞的修補(bǔ)，研究人員進(jìn)行了大量研究。PERNOT等[1]提出曲率最小化原則，在孔洞周邊區(qū)域曲率最小化的前提下通過新增三角面修補(bǔ)孔洞。GIRSHICK等[2]采用非均勻有理B樣條(NURBS)曲面生成補(bǔ)丁、修補(bǔ)孔洞。ARGUDO等[3]提出雙諧波場的網(wǎng)格修補(bǔ)算法，可以較好地修補(bǔ)復(fù)雜孔洞和島嶼孔洞。謝倩茹等[4]采用波前法使孔洞區(qū)域不斷縮小，根據(jù)曲率特征細(xì)分網(wǎng)格。劉云華等[5]基于區(qū)域生長的方法對尖銳特征丟失的孔洞進(jìn)行修補(bǔ)，獲得了較好的效果。晏海平等[6]通過建立徑向基函數(shù)的隱式曲面完成孔洞修復(fù)。袁天然等[7]通過構(gòu)建拉格朗日方程對復(fù)雜孔洞進(jìn)行修補(bǔ)。張立國等[8]基于徑向基函數(shù)對島嶼孔洞進(jìn)行修補(bǔ)，提升修補(bǔ)速度。

對于島嶼孔洞的修補(bǔ)，上述方法均難以得到理想的修補(bǔ)效果：直接刪除島嶼面片將其變?yōu)槠胀ǚ忾]孔洞會造成特征信息丟失；在曲面擬合過程中將島嶼三角面作為控制點(diǎn)會引起網(wǎng)格相交。為了有效實(shí)現(xiàn)島嶼孔洞的修補(bǔ)，本文提出一種基于改進(jìn)波前法的多向波前法，以有效提升島嶼類孔洞的修補(bǔ)效果。

1 多向波前法概述

三角網(wǎng)格模型表面的孔洞可以分為封閉孔洞、半封閉孔洞和島嶼孔洞[9]。本文算法的實(shí)驗(yàn)?zāi)Ｐ蜑榉忾]的網(wǎng)格模型。封閉模型中不可能存在半封閉孔洞，因此下面僅對封閉孔洞與島嶼孔洞進(jìn)行研究。

封閉孔洞是最常見的孔洞，其邊界連接成一個(gè)封閉環(huán)。島嶼孔洞是指在一個(gè)較大孔洞內(nèi)有少量孤立的三角面孔洞。將島嶼孔洞中范圍最大的邊界定義為孔洞邊界，將孔洞邊界內(nèi)的三角面集合稱為島嶼面片，將島嶼面片對應(yīng)的邊界定義為島嶼邊界。圖1為三角網(wǎng)格模型封閉孔洞與島嶼孔洞示意圖。

圖1 網(wǎng)格模型孔洞類型Fig.1 Hole type of grid model

孔洞修補(bǔ)就是從孔洞邊界開始不斷向孔洞區(qū)域插入離散點(diǎn)與三角面，從而使孔洞不斷縮小。波前法可控性高、網(wǎng)格生成速度快[4]，是孔洞修補(bǔ)中常用的方法。該方法首先要檢測孔洞邊界，并以此作為初始波前，按照一定的規(guī)則在孔洞區(qū)域插入新增點(diǎn)與三角面片，每完成一次插入，孔洞邊界就會發(fā)生變化，需調(diào)整波前，循環(huán)上述過程直至完成孔洞修補(bǔ)。

圖2 多向波前法原理Fig.2 Principle of multi-directional advancing method

封閉孔洞與島嶼孔洞的區(qū)別在于波前的組成。傳統(tǒng)波前法針對只有一條邊界的孔洞。多向波前法原理如圖2所示，將孔洞邊界與島嶼邊界同時(shí)作為初始波前，插入離散點(diǎn)。以波前與插入的離散點(diǎn)為基礎(chǔ)，不斷向孔洞區(qū)域內(nèi)新增三角面，逐漸縮小孔洞區(qū)域。孔洞邊界發(fā)生變化時(shí)，調(diào)整更新波前。重復(fù)上述過程直至修補(bǔ)結(jié)束。

2 算法詳細(xì)步驟

2.1 孔洞邊界識別

封閉的三角網(wǎng)格包含邊界邊與內(nèi)部邊。每條邊都有鄰接三角形，只有1個(gè)鄰接三角形的為邊界邊，有2個(gè)鄰接三角形的為內(nèi)部邊。邊界識別原理如圖3所示，遍歷模型的所有邊，找到邊界邊AB并令其為種子邊，從種子邊的2個(gè)頂點(diǎn)開始尋找鄰接邊，可以快速找到邊界邊。當(dāng)邊界邊首尾相連、構(gòu)成封閉的空間多邊形ABCDEFGHIJK時(shí)，完成一個(gè)完整的孔洞邊界搜索。

圖3 邊界邊識別原理Fig.3 Principle of boundary recognition

對于島嶼孔洞，由于在大的孔洞內(nèi)部存在島嶼面片，因此會搜索出多個(gè)邊界，利用孔洞邊界頂點(diǎn)、根據(jù)最小二乘法[10]擬合最小二乘平面，將孔洞邊界投影到擬合的平面上，組成目標(biāo)區(qū)域。將孔洞邊界頂點(diǎn)的一階鄰域也投影到擬合的最小二乘平面上，若投影點(diǎn)位于目標(biāo)區(qū)域內(nèi)，則為島嶼邊界，反之，則為孔洞邊界。

2.2 孔洞邊界預(yù)處理

孔洞邊界邊的長度相差較大，會影響離散點(diǎn)的插入，而且后續(xù)網(wǎng)格化的過程會產(chǎn)生狹長的三角面片，降低網(wǎng)格質(zhì)量。因此在新增離散點(diǎn)之前，需要對孔洞邊界進(jìn)行預(yù)處理，使其均勻化。

計(jì)算所有孔洞邊長度及其平均值lavg[11]，令閾值為1.5lavg，孔洞頂點(diǎn)以Vi(i=1，2，…)表示，當(dāng)某條邊ViVi+1的長度l>1.5lavg時(shí)，計(jì)算邊ViVi+1的中點(diǎn)Vnew。刪除原有孔洞邊和對應(yīng)鄰接三角形，孔洞邊更新為ViVnew和Vi+1Vnew，孔洞三角形更新為ViVnewVj以及VnewVi+1Vj。

2.3 離散點(diǎn)三角面插入

對島嶼孔洞進(jìn)行修補(bǔ)時(shí)，島嶼面片的邊界最小角θmin往往會大于180°，傳統(tǒng)波前法并未對此進(jìn)行考慮，會生成狹長三角面，降低網(wǎng)格質(zhì)量。因此，本文對傳統(tǒng)波前法中新增點(diǎn)插入規(guī)則進(jìn)行改進(jìn)，改進(jìn)的插入規(guī)則如下：

(1)以孔洞邊界和島嶼邊界為初始波前。

(2)計(jì)算兩兩孔洞邊的夾角，得到最小夾角∠Vi-1ViVi+1。

(3)將夾角最小的孔洞頂點(diǎn)作為初始填充位置，根據(jù)θmin的大小設(shè)置不同的頂點(diǎn)與三角面插入準(zhǔn)則，具體準(zhǔn)則如下：①0°<θmin<30°時(shí)(圖4a)，θmin屬于狹小角，直接連接兩頂點(diǎn)會產(chǎn)生狹長的三角面單元，此時(shí)應(yīng)合并該三角面，刪除原有頂點(diǎn)Vi+1、Vi-1，計(jì)算Vi+1Vi-1的中點(diǎn)Vnew，如圖4b所示，以Vnew為新頂點(diǎn)，重新建立三角面，如圖4c所示。②30°<θmin<80°時(shí)(圖5a)，直接連接點(diǎn)Vi-1、Vi+1，新增一個(gè)三角面。③80°<θmin<150°時(shí)(圖5b)，在θmin的角平分線方向上，在孔洞邊Vi-1Vi和ViVi+1邊長的均值處添加新點(diǎn)Vnew，再連接Vi-1Vnew以及Vi+1Vnew，新增2個(gè)三角面。④150°<θmin<210°時(shí)(圖5c)，在θmin的三等分線方向上，在孔洞邊Vi-1Vi和ViVi+1邊長的均值處添加新點(diǎn)Vnew1、Vnew2，連接Vi-1Vnew1、Vnew1Vnew2、Vi+1Vnew2，新增3個(gè)三角面。⑤210°<θmin<270°以及270°<θmin<360°時(shí)，按上述方式分別新增4個(gè)和5個(gè)三角面。

(4)按步驟(3)向孔洞區(qū)域內(nèi)插入頂點(diǎn)與三角面后，更新波前。

(5)重復(fù)步驟(2)～步驟(4)，當(dāng)邊界內(nèi)頂點(diǎn)數(shù)為3時(shí)，結(jié)束網(wǎng)格生長，完成孔洞修補(bǔ)。

圖4 夾角過小時(shí)剖分準(zhǔn)則Fig.4 Split criterion under relatively small angle

圖5 最小角度原則新增點(diǎn)規(guī)則Fig.5 New point rule of minimum angle principle

2.4 新增頂點(diǎn)和新增面檢驗(yàn)

使用波前法常會出現(xiàn)狹長三角形以及由不合理新增點(diǎn)引起的錯(cuò)誤三角形，因此需要對新增頂點(diǎn)和新增三角面進(jìn)行檢驗(yàn)。

三維空間中的合理性檢驗(yàn)比較復(fù)雜，可將空間三角形投影至二維平面完成檢驗(yàn)。創(chuàng)建過點(diǎn)Vi且以n0=(n1+n2)/2(n1、n2為點(diǎn)Vi的兩鄰接三角形的法向量)為法矢的平面，將孔洞三角形投影至該平面，形成目標(biāo)區(qū)域。若新增點(diǎn)的投影不在目標(biāo)區(qū)域內(nèi)，說明新增點(diǎn)出現(xiàn)在角平分線的反向延長線上，則該點(diǎn)為不合理點(diǎn)，應(yīng)將其沿角平分線方向移動到頂點(diǎn)Vi的對稱位置。

Delaunay三角剖分算法將三角網(wǎng)格中的最小角最大化，以預(yù)防狹長三角面的產(chǎn)生，提高網(wǎng)格質(zhì)量[12]。平面Delaunay檢驗(yàn)利用“空圓準(zhǔn)則”即四點(diǎn)不共圓準(zhǔn)則[13]，如果2個(gè)三角形不滿足Delaunay準(zhǔn)則，則根據(jù)“最大化最小角”原則將2個(gè)三角形的對角線進(jìn)行交換，使其滿足Delaunay準(zhǔn)則，從而避免產(chǎn)生狹長三角形。

2.5 基于法矢與曲率的頂點(diǎn)調(diào)整

2.5.1法矢與曲率計(jì)算

為獲得更好的曲面孔洞修補(bǔ)效果，利用頂點(diǎn)法矢和曲率調(diào)整新增頂點(diǎn)位置，使新增三角面最大程度地?cái)M合孔洞原有表面特征。

三角網(wǎng)格模型頂點(diǎn)Vi的鄰接三角形如圖6所示，其中，Ni為Vi的單位法矢，fik為Vi的一個(gè)鄰接三角面，Nik為fik的單位法矢，αk是fik在Vi處的頂角，ei,j和ei,j+1是頂角αk的2條邊，gk為fik的質(zhì)心，Gk為Vi到gk的距離。

圖6 頂點(diǎn)Vi的鄰接三角形Fig.6 Adjacent triangles of vertex Vi

三角網(wǎng)格模型中某三角面片fik的單位法矢為

(1)

頂點(diǎn)法矢為該點(diǎn)所有鄰接三角面片法矢的加權(quán)平均，若頂點(diǎn)有n個(gè)鄰接三角面，令三角面fik的權(quán)重為wk，則頂點(diǎn)Vi的單位法矢為

(2)

權(quán)重wk由三角形形狀因子λ和質(zhì)心距Gk計(jì)算得到，λ的計(jì)算公式為

(3)

其中，a、b、c為三角形的邊長。λ(0,1]，λ越大，三角形的規(guī)整程度越高[14]。λ與質(zhì)心距Gk可以較好地評價(jià)三角形幾何特性，將式(2)變形為

(4)

利用式(4)對點(diǎn)Vi的單位法矢進(jìn)行計(jì)算，為了估算結(jié)果的準(zhǔn)確性，在孔洞頂點(diǎn)的法矢計(jì)算之前，先將缺失部分補(bǔ)齊。

(5)

將新增點(diǎn)Vnew替換點(diǎn)Vj，點(diǎn)Vi處沿方向T的法曲率為

(6)

2.5.2頂點(diǎn)調(diào)整

由Vi指向新增點(diǎn)Vnew構(gòu)成向量nnew，nnew的單位向量為nb，nb與頂點(diǎn)法矢Ni共同確定平面Π。將新增點(diǎn)在平面Π上進(jìn)行調(diào)整，得到V′new，V′new與Vj組成的向量的單位向量為nB，如圖7所示。

圖7 新增頂點(diǎn)調(diào)整示意圖Fig.7 New vertex adjustment diagrammatic sketch

若不進(jìn)行頂點(diǎn)調(diào)整，則利用波前法求得新增點(diǎn)坐標(biāo)：

Vnew=Vi+(|Vi-1Vi|+|ViVi+1|)nb/2

(7)

根據(jù)曲率ki(T)對頂點(diǎn)進(jìn)行調(diào)整。ki(T)>0時(shí)，曲面在點(diǎn)Vi沿T方向處為凸，應(yīng)將nb沿法向方向旋轉(zhuǎn)θ角；ki(T)<0時(shí)，曲面在點(diǎn)Vi沿T方向處為凹，應(yīng)將nb沿法向的反方向旋轉(zhuǎn)θ角；ki(T)=0時(shí)，無需調(diào)整。聯(lián)立式(4)、式(5)得調(diào)整角度θ以及nB：

(8)

θ=arccos(nB·nb)

(9)

調(diào)整后的坐標(biāo)Vnew=Vi+(|Vi-1Vi|+|ViVi+1|)nB/2，將所有新增點(diǎn)按該過程完成調(diào)整。

本文算法在修補(bǔ)孔洞過程中基于波前法，以孔洞邊界與島嶼邊界為基礎(chǔ)增加頂點(diǎn)與三角面，并基于法矢與曲率進(jìn)行自適應(yīng)調(diào)整，使新增區(qū)域盡可能擬合缺失部分的原有幾何形狀，使孔洞區(qū)域與非孔洞區(qū)域能光滑銜接，不斷更新波前信息，有效減小修補(bǔ)痕跡。

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

為驗(yàn)證本文方法的有效性，選擇3組網(wǎng)格數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為VS2013，采用OpenGL庫驗(yàn)證算法。首先驗(yàn)證該算法對普通封閉孔洞的修補(bǔ)效果，采用帶有孔洞的兔子模型進(jìn)行實(shí)驗(yàn)。圖8a所示模型的孔洞為狹長孔洞，利用文獻(xiàn)[1]算法和文獻(xiàn)[4]算法對其進(jìn)行修補(bǔ)，得到的效果圖分別為圖8b、圖8c，利用本文算法得到的結(jié)果如圖8d所示，本文算法明顯優(yōu)于前兩種算法。

手模型1中的孔洞為島嶼孔洞，圖9a所示為孔洞模型，圖9b為文獻(xiàn)[1]算法的修補(bǔ)效果圖，利用文獻(xiàn)[4]算法得到的效果如圖9c所示，本文算法對島嶼孔洞修補(bǔ)后的效果如圖9d所示。對比發(fā)現(xiàn)，利用本文所提算法得到的新增面片與非孔洞區(qū)域過渡自然，保留了原有曲面特征，修補(bǔ)效果明顯優(yōu)于前兩種算法。

圖9 手模型1孔洞不同算法修補(bǔ)效果Fig.9 Repair effect of different algorithms for Hand 1 model

手模型2孔洞的實(shí)驗(yàn)結(jié)果如圖10所示，圖10a所示為島嶼孔洞模型，可以看出該孔洞既包含大規(guī)模島嶼面片，也有較小的島嶼面片。利用文獻(xiàn)[1]算法和文獻(xiàn)[4]算法得到的修補(bǔ)效果分別如圖10b、圖10c所示。圖10d所示為本文算法的修補(bǔ)結(jié)果，多向波前法在較大程度上保留了原有特征，過渡自然，無明顯修補(bǔ)痕跡，效果較前兩種算法更理想。

圖10 手模型2孔洞不同算法修補(bǔ)效果Fig.10 Repair effect of different algorithms for Hand 2 model

采用形狀因子定量評價(jià)修補(bǔ)效果，由2.5.1節(jié)可知，形狀因子越接近于1，三角形面片越規(guī)整。表1所示為運(yùn)用不同算法進(jìn)行修補(bǔ)得到的新增三角網(wǎng)格平均形狀因子，利用本文算法進(jìn)行修補(bǔ)得到的平均因子超過0.85，在3種算法中效果最好，網(wǎng)格質(zhì)量更高。

表1 新增網(wǎng)格平均形狀因子

由上述3組實(shí)驗(yàn)可知，本文算法修補(bǔ)效果明顯優(yōu)于其他算法，采用本文所提多向波前法對青銅古劍模型(圖11)進(jìn)行修復(fù)。使用手持式三維掃描儀Artec Space Spider獲得文物表面點(diǎn)云數(shù)據(jù)，對數(shù)據(jù)進(jìn)行濾波、精簡等預(yù)處理后，采用本文提出的多向波前法對孔洞進(jìn)行修補(bǔ)?？锥粗饕霈F(xiàn)在劍柄與尾端部分，圖12所示為劍柄部分孔洞修補(bǔ)前后的效果，劍尾部分孔洞修補(bǔ)前后的效果如圖13所示，可以看出，利用本文算法進(jìn)行孔洞修補(bǔ)后，文物表面能夠與非孔洞區(qū)域自然過渡，很好地還原文物表面特征，并且較為復(fù)雜的島嶼與大范圍孔洞也能得到較為理想的修補(bǔ)效果。

圖12 劍柄部分孔洞修復(fù)前后對比Fig.12 Comparison of the sword hilt before and after repair

圖13 劍尾部分孔洞修復(fù)前后對比Fig.13 Comparison of the sword tail before and after repair

使用聯(lián)泰Lite600HD工業(yè)級3D打印機(jī)，采用光固化成形技術(shù)，以白色光敏樹脂為材料，按1∶1的比例打印修補(bǔ)后的古劍模型，如圖14所示?？梢钥吹?，經(jīng)本文算法修補(bǔ)后進(jìn)行打印的3D模型表面光滑，孔洞區(qū)域與非孔洞區(qū)域銜接光順，也從側(cè)面反映本文算法的優(yōu)勢。

圖14 3D打印實(shí)物模型Fig.14 Physical model of 3D printing

4 結(jié)論

本文針對島嶼孔洞問題提出了多向波前法。首先識別孔洞邊界并對其進(jìn)行預(yù)處理，改進(jìn)傳統(tǒng)波前規(guī)則，完成離散點(diǎn)與三角面片的插入。對新增頂點(diǎn)與三角面片進(jìn)行檢驗(yàn)與優(yōu)化，減少狹長三角面片。采用法矢與曲率信息完成對新增頂點(diǎn)的調(diào)整，使新增三角面最大程度地?cái)M合原有表面特征，實(shí)現(xiàn)島嶼孔洞的修補(bǔ)。采用多組網(wǎng)格數(shù)據(jù)進(jìn)行實(shí)驗(yàn)并對文物模型進(jìn)行修復(fù)，結(jié)果表明本文算法生成網(wǎng)格質(zhì)量較高，可以有效完成島嶼孔洞修補(bǔ)?？锥葱扪a(bǔ)算法的適用范圍受原有模型的曲面復(fù)雜程度影響較大，當(dāng)孔洞原有區(qū)域形狀不規(guī)整、不均勻且孔洞部分過大時(shí)，利用孔洞修補(bǔ)算法難以得到理想的修補(bǔ)效果。對于曲面復(fù)雜度不同的孔洞，本文算法的適用范圍將作為下一步的研究重點(diǎn)。