一種三角網(wǎng)格模型的輪廓生成方法

秦 宇，曹 力,2，吳 垚，李 琳,2

一種三角網(wǎng)格模型的輪廓生成方法

秦 宇1，曹 力1,2，吳 垚1，李 琳1,2

(1. 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230601； 2.工業(yè)安全與應(yīng)急技術(shù)安徽省重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230009)

從三維網(wǎng)格模型中提取輪廓信息是一個(gè)具有挑戰(zhàn)性的過程?，F(xiàn)有的方法一般是基于局部形狀特征分析，如曲面的曲率和相鄰面法向之間的夾角，但其特性通常對模型中的局部特征變化敏感。為了解決這個(gè)問題，提出一種基于三維形狀幾何近似的輪廓提取方法。利用完善的變分幾何分割算法來得到一套完整的描述性特征曲線，首先基于變分幾何近似方法劃分模型為若干分片；其次提取所有分片的內(nèi)部特征曲線，并過濾較短的特征曲線；然后將分片的邊界曲線平滑化；最后合并分片邊界曲線與特征曲線，并延伸曲線得到閉合的輪廓。該方法的優(yōu)點(diǎn)是：在幾何近似的基礎(chǔ)上結(jié)合特征提取方法，使輪廓能夠體現(xiàn)三維形狀的全局結(jié)構(gòu)。通過在各類網(wǎng)格模型上進(jìn)行實(shí)驗(yàn)和比較表明，該方法在提取模型輪廓的正確性和完整性方面優(yōu)于現(xiàn)有方法。

網(wǎng)格模型處理；變分形狀近似；幾何分割；輪廓線提取；特征提取

三維模型的輪廓抽象地描述了物體的幾何形狀，是計(jì)算機(jī)圖形學(xué)應(yīng)用中的一個(gè)重要因素，被廣泛應(yīng)用于幾何處理中，例如形狀設(shè)計(jì)[1]、表面重構(gòu)[2]、形狀編輯[3]。在逆向工程領(lǐng)域，三維物體在數(shù)字化過程中不可避免地會產(chǎn)生一些缺陷，如噪聲、表面細(xì)節(jié)缺失、某些區(qū)域過于光滑等，降低了三維模型的適用性。DEY和WANG[4]提出了一種獲取高質(zhì)量三維物體的表面模型的方法，該方法從掃描的點(diǎn)云數(shù)據(jù)中提取特征曲線，并使用其重建更好的表面。但由于點(diǎn)云中存在噪聲、離群點(diǎn)以及數(shù)據(jù)和拓?fù)湫畔⑷笔У葐栴}，很難提供可靠的特征曲線。因此，獲得高質(zhì)量重建的模型顯得尤為重要[2]。

從點(diǎn)云或多邊形網(wǎng)格中提取特征曲線，在許多文獻(xiàn)中得到了廣泛的研究。在大多數(shù)研究中，提取特征線的幾何標(biāo)準(zhǔn)是曲率張量或曲率導(dǎo)數(shù)[5-7]。通過局部或全局方式擬合網(wǎng)格頂點(diǎn)，然后估算曲率來提取特征曲線。YANG和ZHENG[8]提出了一種新的曲率張量估計(jì)算法，通過分段曲面插值在三角形網(wǎng)格上進(jìn)行曲率張量估計(jì)，比曲面擬合的方法有更精確的結(jié)果。WEINKAUF和GüNTHER[9]利用曲面的主曲率提取拓?fù)涔羌?，并且引入分界持久性概念以正確區(qū)分顯著特征邊緣和非顯著特征邊緣。TORRENTE等[10]將Hough變換擴(kuò)展到三維形狀領(lǐng)域，用代數(shù)方法識別三維網(wǎng)格上的小特征。LAI等[11]引入特征敏感度量識別特征，并使用數(shù)學(xué)形態(tài)學(xué)的思想對特征進(jìn)一步分類。KIM等[12]采用張量投票理論特征提取，求解頂點(diǎn)的法向投票張量矩陣的特征值，再根據(jù)特征值將特征分類為角點(diǎn)、銳邊、邊界。除此之外，一些研究中還引入了二面角[13]、離散微分幾何[14]、移動最小二乘[15]，避免了估計(jì)曲率張量或曲率導(dǎo)數(shù)時(shí)巨大的計(jì)算量。

上述研究專注于特征提取技術(shù)，且未生成連續(xù)的特征曲線，無法直接用于模型的重建工作。通常將離散的特征曲線連接為連通封閉的輪廓線需要用戶的交互。LU等[16]提出一種自動檢測特征網(wǎng)絡(luò)的方法，結(jié)合曲線曲率和曲面擬合誤差提取特征曲線，然后對曲線擴(kuò)展生成連通的模型輪廓。CAO等[17]通過曲率估算的方法提取特征曲線，保留明顯和較長的曲線進(jìn)一步生成模型分片布局。對于高質(zhì)量的網(wǎng)格，這種基于局部曲面分析的方法能提取有效的特征曲線。但在含有噪聲的網(wǎng)格上、稀疏的網(wǎng)格上曲面擬合產(chǎn)生的誤差大，估算的微分量不準(zhǔn)確，一些重要的特征曲線常常被忽略。在含有尖銳邊緣的CAD模型上，用光滑的曲面擬合也是不合理的。網(wǎng)格分割方法為輪廓線的獲取提供了另一種解決方案：從分割結(jié)果中提取分片的邊界作為輪廓線。NIESER等[18]擴(kuò)展平面區(qū)域劃分網(wǎng)格，然后將區(qū)域邊界作為特征邊、區(qū)域相交點(diǎn)作為特征點(diǎn)生成網(wǎng)格的特征圖。變分形狀近似(variational shape approximation，VSA)方法基于平面近似將網(wǎng)格劃分為多個(gè)區(qū)域[19]。在此基礎(chǔ)上，WU和KOBBELT[20]擴(kuò)展了變分形狀近似技術(shù)，引入球體、柱體作為近似的基本元素進(jìn)行劃分。YAN等[21-22]進(jìn)一步擴(kuò)展為二次曲面近似，依據(jù)二次曲面擬合誤差進(jìn)行劃分。VSA底層采用的度量距離是一個(gè)非微分性質(zhì)的量，加上聚類的約束，使得提取的特征線不會隨著噪聲的增多而有所改變，在特征提取上更加魯棒，能處理很多特殊情況下的網(wǎng)格。

本文提出了一種結(jié)合幾何近似和曲面曲率的方法，可以從網(wǎng)格模型中生成最佳的描述性輪廓。該方法是基于完善的變分幾何劃分策略。其首先利用VSA算法獲得分片集合，分片邊界作為初始輪廓。然后，采用特征檢測方法提取分片內(nèi)部特征曲線，過濾，獲得內(nèi)部細(xì)節(jié)特征。最后通過平滑、合并、擴(kuò)展等步驟優(yōu)化曲線，得到最終的輪廓。與現(xiàn)有的方法相比，該方法可以生成一組完整的特征輪廓，將其進(jìn)一步平滑后轉(zhuǎn)換為輸入模型的完整輪廓線。

1 輪廓生成流程

本文方法輸入一組三角形組成的網(wǎng)格模型，通過一系列操作步驟，輸出描述三維模型形狀特征的高質(zhì)量輪廓線。輪廓線提取流程如圖1所示，首先基于VSA方法，將原始網(wǎng)格模型劃分為若干分片，并使用最優(yōu)劃分方案，根據(jù)輸入網(wǎng)格模型的復(fù)雜程度確定分片的個(gè)數(shù)，降低VSA方法隨機(jī)劃分帶來的弊端。保留每個(gè)分片的邊界曲線作為初始輪廓等待進(jìn)一步連接。其次，對于網(wǎng)格的每一個(gè)分片，采用特征檢測方法識別內(nèi)部區(qū)域的局部特征，生成內(nèi)部特征線，借助過濾步驟，去除大量短小的特征曲線。然后，提出邊緣平滑方法，處理分片的所有邊緣曲線。最后，將邊界曲線和每個(gè)分片內(nèi)部的局部特征曲線進(jìn)行合并，擴(kuò)展某些尚未連通的曲線，從而生成一個(gè)封閉的輪廓。一個(gè)連接良好的輪廓，可以用來重建光滑的網(wǎng)格模型以供進(jìn)一步使用。

如圖1所示，輪廓信息生成的核心步驟為：

步驟1. 對網(wǎng)格模型進(jìn)行VSA劃分；

步驟2. 對分片內(nèi)部進(jìn)行特征提取并過濾；

步驟3. 對分片邊緣平滑處理，提取邊緣輪廓；

步驟4. 合并步驟2和3獲取輪廓曲線；

步驟5. 檢查輪廓的完整性，擴(kuò)展不連通曲線；

步驟6. 輸出輪廓數(shù)據(jù)。

圖1 本文方法流程圖

2 輪廓線生成過程

2.1 分片信息提取

VSA方法[19]基于聚類的思想將網(wǎng)格劃分為若干片，不需要計(jì)算局部微分系數(shù)。但是VSA方法在劃分過程中隨機(jī)選取種子點(diǎn)，可使得劃分結(jié)果不理想。種子點(diǎn)數(shù)量過少，丟失過多幾何信息，最終提取的輪廓無法描述原模型的形狀。種子點(diǎn)數(shù)量過多，增加了輪廓的復(fù)雜度。因此，在原有的VSA方法的基礎(chǔ)上，本文采用優(yōu)化策略進(jìn)行合理的分片劃分。

(1) 合并分片。通過VSA操作獲得分片集。由于種子初始位置的隨機(jī)性，一些平坦的區(qū)域可能會被分割成多個(gè)分片，增加不必要的輪廓。因此，需要將這些分片合并為一個(gè)。通過計(jì)算相鄰分片間的2,1距離值衡量分片之間的相似程度，確定是否需要合并。如果2分片的代理間2,1的距離值小于閾值，則需要合并分片。其中，閾值的選擇依據(jù)文獻(xiàn)[23]所提出的種子點(diǎn)優(yōu)化采樣算法，即

其中，R為需要被擴(kuò)展的分片；P為分片的代理；分片為R內(nèi)的頂點(diǎn)；()為頂點(diǎn)的法向量；為第個(gè)分片的法向量。

(2) 劃分分片。一些局部變化明顯的區(qū)域，需要更多的分片來表示，對于每個(gè)VSA劃分分片的結(jié)果，計(jì)算分片中所有三角形法向量的方差。設(shè)置一個(gè)閾值，如果方差大于閾值，則表明該區(qū)域特征變化明顯，需要將該分片進(jìn)行再次劃分，直到滿足閾值。否則，由少數(shù)VSA分塊得到的邊界曲線不能很好地生成重建結(jié)果，甚至可能無法重建。

(3) 邊界區(qū)域處理。一些三角形由于頂點(diǎn)的平均法線而被錯(cuò)誤地聚類到鄰接分片中。因此，需要檢查每個(gè)分片的邊界區(qū)域的三角形。通過計(jì)算這些三角形和附近分片之間的2,1距離，以找到正確的分類(見第1節(jié)的步驟1)。

2.2 特征提取和過濾

僅獲得分片的邊界作為輪廓是不夠的，為了獲得更詳細(xì)的模型結(jié)構(gòu)特征，還需要進(jìn)一步對分片內(nèi)部的特征線進(jìn)行提取。對于一般的網(wǎng)格模型，邊界信息和小特征都會導(dǎo)致其微分系數(shù)值的變化。這些也是現(xiàn)有解決方案中確定小特征的標(biāo)準(zhǔn)。大多數(shù)特征感知方法采用微分系數(shù)對分片法線進(jìn)行過濾，從而去除小特征。特征保持方法的關(guān)鍵步驟是識別不同分片的小特征。本文方法采用了一種改進(jìn)的特征提取方法[6]，基于局部曲面擬合技術(shù)估算頂點(diǎn)曲率，獲得特征點(diǎn)。對于分片的每一個(gè)頂點(diǎn)，用一個(gè)三階多項(xiàng)式方程擬合頂點(diǎn)的小曲面。根據(jù)曲率極值捕獲特征點(diǎn)，然后連接成特征曲線。特征曲線表示為一組有序的特征點(diǎn)，即={0,1,2,···,v}。

由于特征提取過程中產(chǎn)生了大量的特征線，有些特征強(qiáng)度非常小，表現(xiàn)為短小的特征曲線，這些特征曲線不僅會增加計(jì)算量，還會導(dǎo)致最終無法提取到完整的輪廓線。因此，需要將這些曲線濾除。與DFN (detecting feature networks)方法[17]的過濾方案相同，定義尺度無關(guān)量來度量特征線的強(qiáng)度。通過對設(shè)定閾值過濾掉強(qiáng)度不高的特征線，從而保留顯著、較長的特征線。通常通過模型的復(fù)雜度和局部特征來設(shè)置合理的閾值。如圖2所示，大量短小的特征線被過濾掉(見第1節(jié)中的步驟2)。

2.3 邊界平滑

在分片劃分的過程中，VSA劃分的分片可能會存在鋸齒邊界，這是由于邊界由三角形的邊緣組成所引起的。對于具有小特征的網(wǎng)格，這種情況更為嚴(yán)重。多數(shù)情況下，小特征的分布是稀疏的和局部連通的。為了解決該問題，本文提出了一種邊緣平滑方法，如圖3所示。其主要步驟如下：

步驟1.根據(jù)分片所包含的三角形數(shù)量對所有分片進(jìn)行排序。

步驟2. 從包含三角形數(shù)量最少的分片開始，搜索其邊界附近三角形，如果存在另外一個(gè)分片中有2個(gè)以上的三角形與該分片中的三角形有相同的邊，則該三角形將被合并，然后遞歸搜索相鄰的三角形，直到?jīng)]有這樣的三角形。

步驟3. 通過不斷迭代圖3(a)和(b)得到光滑的分片邊界。

圖3 網(wǎng)格細(xì)分前后對比((a)網(wǎng)格細(xì)分前；(b)網(wǎng)格細(xì)分后)

圖3需要說明的是：如果初始網(wǎng)格三角面較少，且質(zhì)量不高(有大量狹長的三角形)，需要進(jìn)行保邊界的細(xì)分，變成稠密網(wǎng)格后才能進(jìn)行處理，否則本文方法流程可能無法給出理想的結(jié)果(見第1節(jié)中的步驟3)。

2.4 輪廓擴(kuò)展和合并

上述步驟中的邊界和內(nèi)部特征曲線將繼續(xù)用來完成特征線合并和延伸的工作。相鄰分片之間會存在公共的邊界，導(dǎo)致在合并過程中一些邊界線段是冗余的。所以有必要去除這些冗余邊界，生成簡潔的輪廓。

還有一些特征曲線之間互不連通，需要進(jìn)行處理，將其與附近的曲線連接。針對這種情況，本文提出了一種新的解決方案。擴(kuò)展曲線的端點(diǎn)生成候選點(diǎn)，其來自于端點(diǎn)附近的網(wǎng)格頂點(diǎn)。在搜索候選點(diǎn)的過程中，首先添加端點(diǎn)的1鄰域的頂點(diǎn)，如果1鄰域中未滿足條件的頂點(diǎn)，進(jìn)一步擴(kuò)大搜索范圍，在本文中設(shè)置最大搜索鄰域?yàn)?。對于這些候選點(diǎn)，本文設(shè)計(jì)了一個(gè)權(quán)重函數(shù)來選擇最合適的候選點(diǎn)作為新的端點(diǎn)。將選定的端點(diǎn)逐漸添加到線段，直到所有線段都相互連通或者候選點(diǎn)集為空，形成閉合的輪廓，即

其中，權(quán)重函數(shù)包含2項(xiàng)，為候選點(diǎn)的曲率影響因子，max和min分別為候選集中每個(gè)頂點(diǎn)的最大主曲率值中的最大值和最小值。|N→max|為候選頂點(diǎn)的最大主曲率，其范圍為[0,1]。為角度影響因子，即候選頂點(diǎn)和端點(diǎn)的方向與特征線方向之間的角度，其范圍為[-1,1]。用于控制不同網(wǎng)格兩項(xiàng)的權(quán)重(見第1節(jié)中的步驟4和5)。

經(jīng)過以上各步操作，最終可以獲得三維模型的簡潔、閉合的輪廓表達(dá)。

3 結(jié)果與討論

用實(shí)驗(yàn)結(jié)果來驗(yàn)證本文提出方法的有效性。相關(guān)的實(shí)驗(yàn)在如下配置的臺式機(jī)上完成：主頻為4.4 GHz的CPU，16 GB內(nèi)存，1080Ti顯卡。程序通過C++編程實(shí)現(xiàn)。其中，三維模型的數(shù)據(jù)均來自于文獻(xiàn)[24]中提供的模型數(shù)據(jù)庫。

3.1 對比試驗(yàn)

實(shí)驗(yàn)選取了多個(gè)網(wǎng)格模型在該方法上進(jìn)行測試。如圖4所示，Torch模型中按鈕區(qū)域的短特征線由于其長度較短、曲率變化不明顯，在使用谷脊線提取的方法處理時(shí)會被過濾掉，但本文方法可以被保留。這是由于本文方法基于VSA的劃分結(jié)果，在生成輪廓線的過程中可以結(jié)合模型的全局信息進(jìn)行處理。

同樣，在Vase模型的輪廓線提取中，由于底部的曲率變化不明顯，在這些位置的輪廓線缺乏特殊描述，會在特征過濾的步驟中被移除。FCNE (feature curve network extraction)方法[16]雖然可以連通所有提取的特征線，給出比DFN[17]方法更好的結(jié)果。但是FCNE的方法也未得到完整的輪廓，如圖5(b)所示。而本文的方法利用分片收集模型的全局結(jié)構(gòu)信息，可以得到更完整的輪廓，如圖5(c)所示。

為了進(jìn)一步驗(yàn)證本文方法，實(shí)驗(yàn)采用ZHUANG等[25]提出的重建方法對每個(gè)模型生成的輪廓重建曲面。該方法輸入模型的輪廓線信息即可自動構(gòu)建三角網(wǎng)格模型。圖6～9給出了每個(gè)模型的原始網(wǎng)格、基于VSA方法劃分后的結(jié)果、本文方法生成的輪廓線和使用文獻(xiàn)[25]算法重建后的網(wǎng)格曲面。結(jié)果表明，本文方法可以獲得較優(yōu)的VSA劃分結(jié)果，再結(jié)合其他優(yōu)化步驟進(jìn)一步生成完整、簡潔的輪廓線，利用生成的輪廓線可以重建出光滑的曲面。

圖4 Torch模型的輪廓線

圖5 Vase模型的輪廓線((a)原始網(wǎng)格；(b) FCNE方法生成的輪廓線；(c)本文方法生成的輪廓線)

圖6 Block模型的輪廓及處理中間結(jié)果((a)原始網(wǎng)格；(b) VSA分割結(jié)果；(c)輪廓線；(d)重建模型)

圖7 Joint模型的輪廓及處理中間結(jié)果((a)原始網(wǎng)格；(b) VSA分割結(jié)果；(c)輪廓線；(d)重建模型)

圖8 Torch 模型的輪廓表達(dá)及中間處理結(jié)果((a)原始網(wǎng)格；(b) VSA分割結(jié)果；(c)輪廓線；(d)重建模型)

圖9 Vase模型的輪廓及處理中間結(jié)果((a)原始網(wǎng)格；(b) VSA分割結(jié)果；(c)輪廓線；(d)重建模型)

3.2 對比分析

FCNE[16]和FDN[17]方法與本文的研究密切相關(guān)，為了分析本文方法生成的輪廓線的性能，實(shí)驗(yàn)將本文方法與這2種方法進(jìn)行比較。實(shí)驗(yàn)選取多個(gè)模型，并分別用DFN、FCNE和本文方法生成輪廓線，然后利用生成的輪廓線重建模型表面。一般來說，重建結(jié)果更好的輪廓線被認(rèn)為是性能較好的輪廓線。因此，通過比較重建后的曲面來分析輪廓線的性能。豪斯多夫(Hausdorff)距離[26]描述了重建后的模型與原始模型的最大誤差。豪斯多夫距離常被用來度量重建結(jié)果的好壞。距離越小代表重建效果越好。表1給出了測試模型在3種方法上生成的輪廓線重建后的評估數(shù)據(jù)，表1中，本文方法與FCNE方法相比，總體上可以減少5%的重構(gòu)誤差；對于FanDisk和Vase模型，甚至可以減少18%以上的誤差。本文提出的方法也可以處理一些不能用DFN和FCNE處理的模型，在表1中，N.A.對應(yīng)的方法無法完成模型重建。從這些模型的實(shí)驗(yàn)中，可以看出，本文方法提取的輪廓線的整體質(zhì)量優(yōu)于這2種方法。這是因?yàn)镈FN和FCNE方法的基礎(chǔ)是谷脊線提取[6]，通過微分量估計(jì)計(jì)算特征線的方法應(yīng)用在特征輪廓的生成中有一定的缺陷。首先提取的特征是少量的，由于特征輪廓曲線相較于提取的特征曲線還是比較多的，DFN和FCNE方法需要延伸的部分很多，延伸是一種基于規(guī)則的操作，其準(zhǔn)確性不能保證，延伸的越深其結(jié)果的可靠性越無法保證。其次，谷脊線方法提取的特征線中并沒有太多描述曲面信息的曲線，這部分信息的丟失自然會導(dǎo)致描述的重建網(wǎng)格時(shí)信息不充足，重建的網(wǎng)格質(zhì)量比較差。

表1 不同方法的重建結(jié)果Hausdorff距離

注：N.A.表示無法完成模型重建

3.3 方法的局限性

對于某些類型的網(wǎng)格模型，例如，具有許多不對稱特征的模型，用本文方法尚不能很好地獲得其輪廓。在這些情況下，因?yàn)楹茈y平衡計(jì)算成本與精度，所以分片數(shù)量的選擇是一個(gè)難題。為此，在后續(xù)的工作中，將進(jìn)一步改進(jìn)所提出的方法，以便在保持良好結(jié)果的同時(shí)，減少分片數(shù)量。

4 總 結(jié)

在輪廓線提取工作中，本文提出了一種基于幾何近似的三角網(wǎng)格模型輪廓生成方法。該方法利用一個(gè)成熟的變分幾何分割算法來獲得一組用于提供初步輪廓信息的分片，并對每個(gè)分片進(jìn)一步分析，得到相對較小的局部特征曲線。該方案的優(yōu)點(diǎn)是，可靠的特征過濾機(jī)制可以固有地融入到幾何近似步驟中，從而產(chǎn)生能夠捕獲三維全局形狀結(jié)構(gòu)的描述性輪廓。通過在各種網(wǎng)格模型的實(shí)驗(yàn)表明，該方法在提取輪廓曲線的正確性和完整性方面要比現(xiàn)有的一些方法更好。對于具有掃描曲面或復(fù)雜結(jié)構(gòu)的網(wǎng)格，能生成較好的輪廓，從而在重建過程中產(chǎn)生較小的重建誤差。完整的三維模型的輪廓曲線可以用來完成各種應(yīng)用，如重網(wǎng)格劃分、簡化、渲染等。本文方法可以為這些應(yīng)用提供高質(zhì)量的輪廓信息，進(jìn)而更好地表達(dá)原始網(wǎng)格。

[1] XU B X, CHANG W, SHEFFER A, et al. True2Form: 3D curve networks from 2D sketches via selective regularization[J]. ACM Transactions on Graphics, 2014, 33(4): 131:1-131:13.

[2] CAO Y H, NAN L L, WONKA P. Curve networks for surface reconstruction[EB/OL]. [2021-02-07]. https://arxiv.org/abs/ 1603.08753.

[3] GAL R, SORKINE O, MITRA N J, et al. iWIRES[J]. ACM Transactions on Graphics, 2009, 28(3): 1-10.

[4] DEY T K, WANG L. Voronoi-based feature curves extraction for sampled singular surfaces[J]. Computers & Graphics, 2013, 37(6): 659-668.

[5] STYLIANOU G, FARIN G. Crest lines for surface segmentation and flattening[J]. IEEE Transactions on Visualization and Computer Graphics, 2004, 10(5): 536-544.

[6] YOSHIZAWA S, BELYAEV A, SEIDEL H P. Fast and robust detection of crest lines on meshes[C]//2005 ACM Symposium on Solid and Physical Modeling - SPM '05. New York: ACM Press, 2005: 227-232.

[7] ARHID K, UNIVERSITY H S, ZAKANI F, et al. An efficient hierarchical 3D mesh segmentation using negative curvature and dihedral angle[J]. International Journal of Intelligent Engineering and Systems, 2017, 10(5): 143-152.

[8] YANG X N, ZHENG J M. Curvature tensor computation by piecewise surface interpolation[J]. Computer-Aided Design, 2013, 45(12): 1639-1650.

[9] WEINKAUF T, GüNTHER D. Separatrix persistence: extraction of salient edges on surfaces using topological methods[J]. Computer Graphics Forum, 2009, 28(5): 1519-1528.

[10] TORRENTE M L, BIASOTTI S, FALCIDIENO B. Recognition of feature curves on 3D shapes using an algebraic approach to Hough transforms[J]. Pattern Recognition, 2018, 73: 111-130.

[11] LAI Y K, ZHOU Q Y, HU S M, et al. Robust feature classification and editing[J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(1): 34-45.

[12] KIM H S, CHOI H K, LEE K H. Feature detection of triangular meshes based on tensor voting theory[J]. Computer-Aided Design, 2009, 41(1): 47-58.

[13] ARHID K, UNIVERSITY H S, ZAKANI F, et al. An efficient hierarchical 3D mesh segmentation using negative curvature and dihedral angle[J]. International Journal of Intelligent Engineering and Systems, 2017, 10(5): 143-152.

[14] HILDEBRANDT K, POLTHIER K, WARDETZKY M. Smooth feature lines on surface meshes[C]//The 3rd Eurographics Symposium on Geometry Processing. New York: ACM Press, 2005: 85

[15] KIM S K, KIM C H. Finding ridges and valleys in a discrete surface using a modified MLS approximation[J]. Computer-Aided Design, 2006, 38(2): 173-180.

[16] LU Z D, GUO J W, XIAO J, et al. Feature curve network extraction via quadric surface fitting[C]//2019 Pacific Conference on Computer Graphics and Applications (PG 2019). Goslar: The Eurographics Association, 2019: 47-52.

[17] CAO Y H, YAN D M, WONKA P. Patch layout generation by detecting feature networks[J]. Computers & Graphics, 2015, 46: 275-282.

[18] NIESER M, SCHULZ C, POLTHIER K. Patch layout from feature graphs[J]. Computer-Aided Design, 2010, 42(3): 213-220.

[19] COHEN-STEINER D, ALLIEZ P, DESBRUN M. Variational shape approximation[J]. ACM Transactions on Graphics, 2004, 23(3): 905-914.

[20] WU J H, KOBBELT L. Structure recovery via hybrid variational surface approximation[J]. Computer Graphics Forum, 2005, 24(3): 277-284.

[21] YAN D M, LIU Y, WANG W P. Quadric surface extraction by variational shape approximation[C]//The 4th International Conference on Geometric Modeling and Processing - GMP 2006. Heidelberg: Springer, 2006: 73-86.

[22] YAN D M, WANG W P, LIU Y, et al. Variational mesh segmentation via quadric surface fitting[J]. Computer-Aided Design, 2012, 44(11): 1072-1082.

[23] 徐源廷. 面向三角網(wǎng)格分割的幾何處理技術(shù)研究[D]. 合肥: 合肥工業(yè)大學(xué), 2020.

XU Y T. Research on geometry processing technology for triangular mesh segmentation[D]. Hefei: Hefei University of Technology, 2020 (in Chinese).

[24] GAO X F, SHEN H X, PANOZZO D. Feature preserving octree-based hexahedral meshing[J]. Computer Graphics Forum, 2019, 38(5): 135-149.

[25] ZHUANG Y X, ZOU M, CARR N, et al. A general and efficient method for finding cycles in 3D curve networks[J]. ACM Transactions on Graphics, 2013, 32(6): 180: 1-180: 10.

[26] DUBUISSON M P, JAIN A K. A modified Hausdorff distance for object matching[C]//The 12th International Conference on Pattern Recognition. New York: IEEE Press, 1994: 566-568.

A novel wire frame generation for triangle meshes

QIN Yu1, CAO Li1,2, WU Yao1, LI Lin1,2

(1. School of Computer and Information, Hefei University of Technology, Hefei Anhui 230601, China; 2. Anhui Province Key Laboratory of Industry Safety and Emergency Technology, Hefei Anhui 230009, China)

Extracting wire frame from 3D models is a challenge. Existing methods are typically based on the analysis of local shape properties, such as surface curvatures and angles between faces, which are generally sensitive to small features in the model. In order to solve this problem, we proposed a wire frame extraction method based on geometric approximation of 3D shapes. This method employed a well-established variational geometric segmentation algorithm to derive a complete set of descriptive feature curves. Firstly, the model was divided into several patches based on the variational geometry approximation method. Secondly, the internal characteristic curves of all patches were extracted, and the short characteristic curves were filtered. Then, the boundary curves of patches were smoothed. Finally, the patch boundary curves and characteristic curves were merged, and the closed wireframe network was obtained by extending the curves. The advantage of the proposed method was that descriptive wire frames can capture the global structures of the 3D shapes using a reliable feature filtering mechanism that was inherently incorporated in the geometric approximation step. Experiments on various kinds of meshes have been carried out and the results demonstrate that our method is superior to existing approaches in terms of correctness and completeness of the extracted wire frame.

mesh model processing; variational shape approximation; geometric segmentation; wire frame extraction; feature extraction

TP 391

10.11996/JG.j.2095-302X.2021060963

A

2095-302X(2021)06-0963-07

2021-04-13；

2021-05-21

國家自然科學(xué)基金項(xiàng)目(61602146)；安徽省自然基金青年基金資助項(xiàng)目(1708085QF137)；中國高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(JZ2019YYPY0011)

秦 宇(1996–)，女，山西呂梁人，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。E-mail：18856329235@163.com

曹 力(1982–)，男，安徽蕪湖人，副教授，博士。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、幾何分析等。E-mail：lcao@hfut.edu.cn

13 April，2021；

21 May，2021

National Natural Science Foundation of China (61602146);Youth Fund of Anhui Provincial Natural Science Foundation (1708085QF137); Fundamental Research Funds for the Central Universities (JZ2019YYPY0011)

QIN Yu (1996–), female, master student. Her main research interest covers computer graphics. E-mail：18856329235@163.com

CAO Li (1982–), male, associate professor, Ph.D. His main research interests cover computer graphics, geometric analysis. E-mail：lcao@hfut.edu.cn