誤差有界的低扭曲非結(jié)構(gòu)T樣條曲面擬合

關(guān)啟超，劉 浩，王遠(yuǎn)成，傅孝明

誤差有界的低扭曲非結(jié)構(gòu)T樣條曲面擬合

關(guān)啟超，劉 浩，王遠(yuǎn)成，傅孝明

(中國科學(xué)技術(shù)大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230000)

為了計(jì)算對于任意復(fù)雜拓?fù)鋽M合域的低扭曲、滿足擬合誤差閾值和較少控制點(diǎn)的非結(jié)構(gòu)T樣條擬合曲面，提出了一種逐步求解的方法。首先，生成與擬合域具有相同拓?fù)涞亩嗔⒎襟w作為參數(shù)域，通過多次重參數(shù)化過程優(yōu)化待擬合表面和參數(shù)域之間的對應(yīng)關(guān)系，得到一個適用于獲得低擬合誤差樣條曲面的低扭曲映射。與此同時(shí)，利用非結(jié)構(gòu)T樣條局部細(xì)分的性質(zhì)對不滿足擬合誤差閾值的區(qū)域進(jìn)行自適應(yīng)局部細(xì)分，得到滿足擬合誤差閾值的低扭曲樣條曲面。接下來，提出一種刪除冗余控制頂點(diǎn)的擬合曲面簡化策略，在滿足擬合誤差閾值和低扭曲的基礎(chǔ)上刪除冗余的控制頂點(diǎn)，得到控制頂點(diǎn)數(shù)量較少的誤差有界的低扭曲非結(jié)構(gòu)T樣條擬合曲面。在各種復(fù)雜模型上證明了此方法的有效性。與最新的方法相比，該方法以更少的控制頂點(diǎn)實(shí)現(xiàn)了更低的參數(shù)化扭曲。

低扭曲；非結(jié)構(gòu)T樣條；曲面擬合；多立方體參數(shù)域；局部細(xì)分

隨著計(jì)算機(jī)造型設(shè)計(jì)技術(shù)和三維采集技術(shù)的發(fā)展，海量的三維幾何模型應(yīng)運(yùn)而生，然而這些模型很少能夠直接用于實(shí)際應(yīng)用，包括逆向工程、3D建模和3D打印。只有經(jīng)過轉(zhuǎn)換，其才能在實(shí)際應(yīng)用中更容易地進(jìn)行二次編輯。由于樣條曲面具有參數(shù)方程和高階連續(xù)性，且表示方法更緊湊，使得樣條曲面在造型設(shè)計(jì)中更有利于光滑形狀的描述和分析。因此，在計(jì)算機(jī)輔助設(shè)計(jì)與制造工業(yè)和工程計(jì)算中，經(jīng)常需要使用樣條曲面擬合技術(shù)將輸入的離散數(shù)據(jù)轉(zhuǎn)換成易于編輯的樣條曲面。

樣條曲面擬合的目標(biāo)是構(gòu)造一個樣條曲面與輸入的離散數(shù)據(jù)的擬合誤差小于給定的閾值，并盡可能使得擬合曲面的扭曲較低、控制點(diǎn)數(shù)量較少。首先，如果樣條曲面與輸入模型之間的擬合誤差越小，對原模型細(xì)節(jié)的保留就越多。其次，擬合結(jié)果的扭曲越低，對擬合曲面進(jìn)行二次設(shè)計(jì)越容易、操作越簡單，同時(shí)使得數(shù)值模擬精度越高。最后，由于較多的控制頂點(diǎn)不僅會占用更多的內(nèi)存空間，還提高設(shè)計(jì)師對于擬合曲面進(jìn)行二次設(shè)計(jì)的難度，因此希望使用較少的控制頂點(diǎn)表示擬合曲面。

然而，求解滿足上述3個目標(biāo)的樣條曲面是非常具有挑戰(zhàn)的，理由有3個：①給定任意復(fù)雜拓?fù)涞哪Ｐ?，生成合適的樣條參數(shù)域滿足上述要求是非平凡的；②參數(shù)域和輸入模型之間的對應(yīng)與近似誤差和扭曲之間是非線性關(guān)系，求解一個適用于獲得低近似誤差、低扭曲的對應(yīng)是困難的；③控制頂點(diǎn)的數(shù)量與低擬合誤差和低扭曲是矛盾的，低擬合誤差和低扭曲需要較多的控制頂點(diǎn)。

現(xiàn)有方法都不能很好地解決上述問題。通用的方法是將輸入模型分割為多個較小的子面片，并對每個子面片獨(dú)立求解，最后將所有子面片拼接在一起[1-2]。雖然在每個子面片上均能得到滿意的結(jié)果，但是將子面片拼接在一起時(shí)為了保證連續(xù)性和擬合誤差，不可避免會增加控制頂點(diǎn)的數(shù)量。為了降低樣條曲面的控制頂點(diǎn)，有學(xué)者提出使用T樣條曲面進(jìn)行擬合[3-5]，T樣條允許自適應(yīng)局部細(xì)分，只對擬合結(jié)果不滿意的區(qū)域進(jìn)行精細(xì)擬合，在處理細(xì)節(jié)分布不均勻的復(fù)雜模型時(shí)具有很大的吸引力。但是上述方法要么對輸入模型的拓?fù)溆邢拗?，要么沒有顯式的建立降低扭曲的優(yōu)化模型，均無法得到滿足上述3個目標(biāo)的樣條曲面。

本文提出了一種非結(jié)構(gòu)T樣條曲面擬合算法，對任意虧格的輸入模型均得到滿足擬合誤差的低扭曲的樣條曲面，并顯著減少了控制點(diǎn)的數(shù)量。采用逐步求解的策略依次滿足3個目標(biāo)。給定一個任意復(fù)雜拓?fù)涞哪Ｐ停褂门c輸入模型具有相同拓?fù)涞亩嗔⒎襟w作為參數(shù)域，并通過同時(shí)優(yōu)化內(nèi)部和邊界來生成一個低扭曲的體映射，從而獲得低扭曲的擬合函數(shù)。接下來，為了使得擬合誤差小于給定的閾值，利用非結(jié)構(gòu)T樣條的局部細(xì)分的性質(zhì)對不滿足擬合誤差的區(qū)域進(jìn)行了自適應(yīng)局部細(xì)分。這時(shí)候，控制頂點(diǎn)的數(shù)量往往較高。為此，本文提出一種擬合曲面簡化策略，在滿足擬合誤差和低扭曲的基礎(chǔ)上逐點(diǎn)的刪除冗余控制頂點(diǎn)。

本文方法對于任意復(fù)雜拓?fù)涞妮斎肽Ｐ途艿玫降团で鷶M合曲面，并且在具有145個復(fù)雜模型的數(shù)據(jù)集上驗(yàn)證了可行性和有效性。與最新的方法相比，本文方法使用更少的控制頂點(diǎn)實(shí)現(xiàn)了更低的參數(shù)化扭曲。

1 相關(guān)工作

樣條曲面在計(jì)算機(jī)輔助設(shè)計(jì)與制造中有著廣泛地應(yīng)用，非均勻有理B樣條已經(jīng)成為行業(yè)標(biāo)準(zhǔn)。通過對結(jié)點(diǎn)向量的細(xì)化和控制點(diǎn)的調(diào)整，其可以用來表示任意復(fù)雜的曲面。有許多學(xué)者使用B樣條或NURBS曲面擬合復(fù)雜模型[6-9]。然而，由于這種張量積曲面表示要求控制網(wǎng)格的每一行和每一列都有相同數(shù)量的控制點(diǎn)，但只允許所謂的結(jié)點(diǎn)向量的全局細(xì)化，往往導(dǎo)致在表示復(fù)雜模型時(shí)出現(xiàn)許多冗余控制點(diǎn)，從而降低擬合速度和后續(xù)許多操作的效率[10-11]。

為解決上述問題，SEDERBERG等[11-12]提出T樣條。通過在控制網(wǎng)格中允許T節(jié)點(diǎn)的存在，實(shí)現(xiàn)了局部細(xì)分，避免了多余的控制點(diǎn)。每次插入一個控制點(diǎn)時(shí)，只需要引入少量的相鄰控制點(diǎn)，而無需整行或整列地增加控制點(diǎn)。局部細(xì)分簡化了曲面的表達(dá)式，節(jié)省了存儲空間，相比于NURBS，更適合進(jìn)行曲面擬合。

T樣條擬合方法首次由ZHENG等[13-14]提出，即利用T樣條重構(gòu)光滑參數(shù)曲面的自動算法。該算法從粗糙表面近似開始，然后在近似精度不滿足要求的區(qū)域逐步細(xì)化。根據(jù)輸入數(shù)據(jù)的局部幾何特征自適應(yīng)地確定生成的T樣條曲面的拓?fù)?，并通過最小二乘法獲得控制點(diǎn)的幾何。除此之外，還提出了幾種新的可用于增強(qiáng)擬合算法的即插即用組件或策略[3]：使用T樣條進(jìn)行擬合、曲率引導(dǎo)策略、合適的重新參數(shù)化和初始樣條節(jié)點(diǎn)重置，并利用這些組件和策略又提出了一種集成這些組件和策略的自適應(yīng)T樣條擬合算法。

在YANG和ZHENG[15]的工作中，提出了一種T樣條曲面蒙皮算法，該算法生成一個T樣條曲面，可以獨(dú)立構(gòu)造樣條曲面的截面曲線和控制曲線，并在相同擬合誤差閾值的情況下生成的樣條曲線通常比傳統(tǒng)放樣樣條曲線具有更少的控制點(diǎn)。LIN和ZHANG[16]提出了一種漸進(jìn)式T樣條數(shù)據(jù)擬合算法，用于擬合具有T樣條表示的大型數(shù)據(jù)集。作為一種迭代方法，其迭代速度穩(wěn)定，對未知T網(wǎng)格頂點(diǎn)數(shù)量的增加不敏感，因此能夠有效地?cái)M合大型數(shù)據(jù)集。

上述方法均未得到低扭曲、低擬合誤差且刪除冗余控制頂點(diǎn)的T樣條擬合曲面，而本文方法得到了滿足此目標(biāo)的擬合曲面，并且使用更少的控制頂點(diǎn)實(shí)現(xiàn)了更低的參數(shù)化扭曲。

2 方 法

2.1 方法概述

2.1.1 問題概述

本文研究誤差有界的低扭曲非結(jié)構(gòu)T樣條曲面擬合問題。輸入為任意復(fù)雜拓?fù)涞娜蔷W(wǎng)格擬合域和擬合誤差，其中擬合域包含一組頂點(diǎn)={v}和一組三角形面={f}。其目標(biāo)是計(jì)算一個非結(jié)構(gòu)T樣條曲面滿足以下條件：

(1) 擬合曲面與擬合域之間的擬合誤差小于；

(2) 擬合曲面的扭曲較低；

(3) 擬合曲面的控制點(diǎn)數(shù)量較少。

2.1.2 非結(jié)構(gòu)T樣條

T樣條的一般表達(dá)為

其中，P為控制點(diǎn)，w為權(quán)重；B(,)為T樣條混合基函數(shù)，其表達(dá)式為

其中，[u]()和[v]()均為三次B樣條基函數(shù)，即

非結(jié)構(gòu)T樣條是傳統(tǒng)T樣條的推廣，通過向網(wǎng)格中添加奇異點(diǎn)使得樣條具有更強(qiáng)的表達(dá)能力。記網(wǎng)格中每個節(jié)點(diǎn)連接邊的數(shù)目為該節(jié)點(diǎn)的度()，()≠4且不為T節(jié)點(diǎn)的節(jié)點(diǎn)稱為奇異點(diǎn)。

一個非結(jié)構(gòu)T樣條的參數(shù)域必須滿足以下3個規(guī)則：

規(guī)則1.一個面內(nèi)相對的2個邊上的節(jié)點(diǎn)間隔必須相等；

規(guī)則2.如果一個面相對的2個邊上都有T節(jié)點(diǎn)，且將其連接起來不違反規(guī)則1，那么這2個T節(jié)點(diǎn)必須用邊連接起來；

規(guī)則3.奇異點(diǎn)的2領(lǐng)域面內(nèi)不能有其他奇異點(diǎn)或者T節(jié)點(diǎn)。

前面2個規(guī)則是T網(wǎng)格的規(guī)則，第3個規(guī)則是針對奇異點(diǎn)的處理，目的是方便計(jì)算奇異點(diǎn)2領(lǐng)域內(nèi)的基函數(shù)。

真實(shí)的參數(shù)域無法在平面上繪制出來，圖1給出了一個非結(jié)構(gòu)T樣條參數(shù)域拓?fù)?，其中，中間的點(diǎn)表示()=3的奇異點(diǎn)，陰影區(qū)域表示奇異點(diǎn)的2領(lǐng)域。

圖1 非結(jié)構(gòu)T樣條參數(shù)域拓?fù)鋄17]

與T樣條相似，在得到非結(jié)構(gòu)T樣條的定義域之后，需要給出每個頂點(diǎn)上的混合函數(shù)，每個混合函數(shù)通過該頂點(diǎn)進(jìn)行局部定義。根據(jù)T樣條混合函數(shù)的定義方法，如果一個區(qū)域可以將其鄰域無扭曲的參數(shù)化到平面上，就可以應(yīng)用平面的T網(wǎng)格定義的方法來定義空間區(qū)域的T樣條。如圖1中不在陰影區(qū)域上的頂點(diǎn)。對于這些頂點(diǎn)，首先需將其局部無扭曲的參數(shù)化到平面，定義基函數(shù)后可以直接映射回多立方體參數(shù)域[17]。

對于奇異點(diǎn)2領(lǐng)域內(nèi)的頂點(diǎn)，本文使用SCOTT等[18]提出的方法計(jì)算每個頂點(diǎn)上的混合函數(shù)。

2.1.3 多立方體參數(shù)域

為了避免因?qū)?fù)雜拓?fù)湫螤钸M(jìn)行分割和拼接而造成的控制點(diǎn)數(shù)量的增加，得到全局統(tǒng)一的樣條表達(dá)，本文使用多立方體作為實(shí)現(xiàn)樣條擬合曲面的參數(shù)域，記為。多立方體提供了一種矩形結(jié)構(gòu)，可以正確表示任意幾何形狀的拓?fù)?，而奇異點(diǎn)只在角點(diǎn)處出現(xiàn)，非常有利于后續(xù)的計(jì)算和分析。

最初始的多立方體參數(shù)域除去需要滿足多立方體的條件之外，還需額外滿足非結(jié)構(gòu)T網(wǎng)格的3個條件。對于任意生成的多立方體形狀，只需對所有面執(zhí)行2次細(xì)分，就可以得到滿足要求的多立方體參數(shù)域，在本文的算法中，初始多立方體參數(shù)域的選擇不會影響最終的擬合精度。

2.1.4 問題挑戰(zhàn)

如前所述，求解滿足上述3個目標(biāo)的樣條曲面是非常具有挑戰(zhàn)的?？蓪⒂?jì)算目標(biāo)樣條曲面表述為以下優(yōu)化問題

其中，E()為映射的扭曲能量；E()為()與之間的擬合近似程度能量；E()為樣條曲面簡化程度能量；和為2個正的權(quán)重，用來平衡扭曲能量、近似程度能量和簡化程度能量。

求解此優(yōu)化問題是一項(xiàng)非常具有挑戰(zhàn)性的事情。第一，很難定義一個適用于優(yōu)化扭曲的近似程度能量和簡化程度能量。第二，由于控制頂點(diǎn)的數(shù)量與低擬合誤差和低扭曲是矛盾的，因此很難定義權(quán)重和的大小。第三，該優(yōu)化問題非凸非線性，在保持?jǐn)M合誤差較低的情況下高效地優(yōu)化扭曲是一件非常困難的事情。

2.1.5 求解思路

針對上述挑戰(zhàn)，考慮到非結(jié)構(gòu)T樣條具有局部細(xì)分的能力，將計(jì)算滿足上述目標(biāo)的樣條曲面分為以下3個步驟：

步驟1.計(jì)算一個低扭曲的擬合映射，此時(shí)不一定滿足擬合誤差；

步驟2.在不滿足擬合誤差閾值的區(qū)域進(jìn)行自適應(yīng)局部細(xì)分；

步驟3.在滿足擬合誤差和低扭曲的基礎(chǔ)上刪除冗余的控制頂點(diǎn)，簡化擬合曲面。

用圖2例子來說明本文求解低扭曲非結(jié)構(gòu)T樣條曲面的重參數(shù)化-擬合步驟。其中黃色表示不滿足擬合誤差閾值的區(qū)域。

圖2 本文系統(tǒng)概覽((a)輸入；(b)與輸入網(wǎng)格具有相同拓?fù)涞亩嗔⒎襟w參數(shù)域；(c)輸入網(wǎng)格參數(shù)化到多立方體參數(shù)域；(d)擬合結(jié)果；(e)自適應(yīng)局部加細(xì)結(jié)果；(f)自適應(yīng)簡化結(jié)果；(g)最終結(jié)果和扭曲)

2.2 低扭曲擬合

給定一個任意復(fù)雜形狀的模型。其生成與輸入模型具有相同拓?fù)涞亩嗔⒎襟w作為參數(shù)域，并通過多次重參數(shù)化過程優(yōu)化待擬合表面和參數(shù)域之間的對應(yīng)關(guān)系，在滿足邊界約束的條件下得到扭曲較低的映射。接下來，利用低扭曲映射的逆映射來擬合樣條曲面，得到低扭曲且光滑的樣條曲面。

2.2.1 計(jì)算低扭曲參數(shù)化

本文需要找到一個有利于擬合操作的低扭曲的表面映射。HU等[19]指出，傳統(tǒng)的平面能量可導(dǎo)致扭曲分布的不均勻，映射后得到狹長的三角形，不利于擬合操作，于是提出使用體能量來驅(qū)動等距優(yōu)化。LIU等[20]使用內(nèi)部和邊界共同優(yōu)化的體能量來獲得低扭曲體參數(shù)化結(jié)果。同樣的，本文將擬合網(wǎng)格映射到多立方體參數(shù)域中，使用內(nèi)部和邊界共同優(yōu)化的體能量來獲得低扭曲的表面映射。

其中，E為三維扭曲能量，該能量限制在邊界上是邊界扭曲能量。

本文使用FU等[22]提出的AMIPS能量和文獻(xiàn)[20]提出的方法將邊界映射限制在參數(shù)域邊界上的硬約束轉(zhuǎn)換為每個邊界頂點(diǎn)在切空間移動的軟約束，然后使用文獻(xiàn)[20]的內(nèi)部和邊界共同優(yōu)化方法來獲得低扭曲體參數(shù)化映射。

2.2.2 非結(jié)構(gòu)T樣條擬合

本文使用非結(jié)構(gòu)T樣條擬合輸入的擬合域，一種常用的方法是最小化插值擬合。此外，為了生成視覺上的光滑曲面，經(jīng)常需要在目標(biāo)函數(shù)中添加光滑函數(shù)項(xiàng)。此時(shí)，優(yōu)化問題變成最小化目標(biāo)函數(shù)

其中，E為擬合誤差項(xiàng)；E為光滑能量項(xiàng)；為一個權(quán)衡常數(shù)。

本文使用一個雙向的能量來表示2個曲面上的采樣誤差

其中，第一項(xiàng)是插值誤差，(v)稱為v對應(yīng)的參數(shù)；第二項(xiàng)是采樣擬合誤差，u是參數(shù)域中的采樣點(diǎn)。在實(shí)驗(yàn)中，采樣點(diǎn)是每個參數(shù)域面中的高斯節(jié)點(diǎn)。

第二項(xiàng)光滑能量項(xiàng)的具體表達(dá)為

其中，為在局部參數(shù)坐標(biāo)系中沿方向的二階導(dǎo)數(shù)。

T網(wǎng)格樣條的導(dǎo)數(shù)為節(jié)點(diǎn)函數(shù)導(dǎo)數(shù)的線性組合，由于在擬合過程中基函數(shù)是固定的，2個能量都可以表述為未知控制點(diǎn)的二次函數(shù)，可以通過求解一個線性方程組得到解。

如圖3所示，對于圖3(a)中復(fù)雜拓?fù)涞哪Ｐ停褂帽疚姆椒ǖ玫綀D3(b)所示的低扭曲、光滑的樣條曲面，其中黃色表示不滿足擬合誤差閾值的區(qū)域，圖3(c)為樣條曲面扭曲分布圖，平均扭曲為1.208。從圖中可以看出，只有很小部分違反擬合誤差的約束。下一階段的目標(biāo)是降低最大擬合誤差。

圖3 低扭曲擬合曲面結(jié)果圖((a)輸入；(b)低扭曲、光滑的樣條曲面；(c)扭曲)

2.3 降低擬合誤差

由于T樣條具有自適應(yīng)局部細(xì)分能力，可以在擬合結(jié)果不令人滿意的區(qū)域進(jìn)行精細(xì)擬合，此方法顯著地減少計(jì)算量，降低計(jì)算成本。

本文通過最大擬合誤差來控制擬合的精度，即

考慮一個參數(shù)域中的矩形域，如果存在映射在中的原網(wǎng)格點(diǎn)v或有采樣點(diǎn)u違反約束，則對R進(jìn)行細(xì)分。

在自適應(yīng)細(xì)化之后，需要重新計(jì)算擬合方程并更新控制點(diǎn)。本文重復(fù)執(zhí)行自適應(yīng)細(xì)化過程直到滿足擬合誤差。

如圖4所示，對于圖4(a)中不滿足擬合誤差閾值的區(qū)域，采用自適應(yīng)局部細(xì)分進(jìn)行精細(xì)擬合，得到圖4(b)滿足擬合誤差的結(jié)果。圖4(c)為樣條曲面扭曲分布圖，平均扭曲為1.247。從圖中可以看出，本文方法在低扭曲的條件下只在不滿足擬合誤差閾值的區(qū)域進(jìn)行局部細(xì)分，顯著地減少了計(jì)算量。但此時(shí)控制頂點(diǎn)的數(shù)目較多，下一階段的目標(biāo)是刪除冗余的控制頂點(diǎn)，簡化樣條曲面。

圖4 降低擬合誤差結(jié)果圖((a)擬合曲面；(b)自適應(yīng)加細(xì)結(jié)果；(c)扭曲)

2.4 簡化曲面

由于刪除一個節(jié)點(diǎn)之后，需要重新計(jì)算擬合方程并更新控制點(diǎn)，所以無法同自適應(yīng)局部細(xì)分一樣，在一次循環(huán)過程中判斷所有采樣點(diǎn)，對所有滿足條件的區(qū)域均進(jìn)行簡化操作。此時(shí)，本文提出一種逐點(diǎn)簡化策略，在滿足擬合誤差和低扭曲的基礎(chǔ)上逐點(diǎn)地刪除冗余控制頂點(diǎn)。

算法步驟如下：

輸入：滿足擬合誤差閾值和低扭曲的T樣條曲面。

輸出：簡化后的滿足擬合誤差閾值和低扭曲的 T 樣條曲面。

步驟1.記樣條曲面的平均扭曲為_，=1.1×_。

步驟2.記多立方體參數(shù)域節(jié)點(diǎn)個數(shù)為，取=0。將T網(wǎng)格上每一個節(jié)點(diǎn)均作為采樣點(diǎn)，計(jì)算擬合誤差||(u)–(u)||2，并排序，記為一個優(yōu)先隊(duì)列，使得(0)為最小值。

步驟3.若=，算法結(jié)束，否則執(zhí)行步驟4。

步驟4.判斷()所對應(yīng)的節(jié)點(diǎn)是否可以刪除。

步驟5.刪除該節(jié)點(diǎn)，重新計(jì)算擬合方程并更新控制點(diǎn)，返回步驟2。

如圖5所示，圖5(a)是2.3節(jié)得到的滿足擬合誤差的低扭曲樣條曲面，此時(shí)控制頂點(diǎn)的數(shù)量為4 880；圖5(b)是使用簡化策略得到的樣條曲面，此時(shí)樣條曲面同樣滿足擬合誤差閾值和低扭曲條件，控制頂點(diǎn)的數(shù)量為3 038；圖5(c)為樣條曲面扭曲分布圖，平均扭曲為1.346。本文的簡化策略在滿足低擬合誤差和低扭曲的基礎(chǔ)上刪除了1 842個冗余控制頂點(diǎn)，簡化率為37.75%。

圖5 簡化前后樣條曲面對比圖((a)簡化前樣條曲面；(b)自適應(yīng)簡化結(jié)果；(c)扭曲)

2.5 實(shí)現(xiàn)細(xì)節(jié)與討論

2.5.1 扭曲的選取

有多種扭曲能量可以被選擇用于參數(shù)化，若選擇共形扭曲，雖然可以很好地保持角度，但如果擬合域的模型中含有狹長的三角形，則可能會引起大的面積變形，不利于擬合操作，導(dǎo)致在變形較大的區(qū)域需要進(jìn)行許多不必要的自適應(yīng)局部細(xì)分才能滿足擬合誤差，對于本文的擬合方法，由于最關(guān)注的是邊界的形狀在優(yōu)化扭曲的同時(shí)不會發(fā)生較大的變形，如果選擇等距扭曲，可以在優(yōu)化扭曲的同時(shí)保持角度和面積，使得輸入擬合域的特征在參數(shù)域中均勻地分布，不會引起較大的變形，避免了在參數(shù)域中特征的集中分布而引起大量的自適應(yīng)局部細(xì)分。因此，本文選擇等距扭曲進(jìn)行優(yōu)化。

2.5.2 采樣擬合誤差的必要性

在使用非結(jié)構(gòu)T樣條擬合過程中，本文方法使用插值誤差和采樣擬合誤差構(gòu)造了一個雙向能量。如果只使用插值誤差能量，當(dāng)網(wǎng)格質(zhì)量很差時(shí)，即當(dāng)輸入網(wǎng)格比較稀疏時(shí)，參數(shù)域中的面可能沒有對應(yīng)的插值點(diǎn)，導(dǎo)致擬合矩陣可能是奇異的，從而導(dǎo)致插值擬合失敗。盡管添加光滑項(xiàng)可以避免奇異問題，但會導(dǎo)致丟失擬合的細(xì)節(jié)。使用本文的雙向能量構(gòu)造的擬合矩陣可以避免奇異性，并且可以提高擬合精度。

2.5.3 優(yōu)化扭曲的同時(shí)擬合樣條曲面

求解低扭曲樣條曲面擬合的一種可能方法是在每次迭代中同時(shí)更新控制點(diǎn)的位置和擬合樣條曲面。此方法有一個主要限制：在優(yōu)化扭曲更新控制點(diǎn)位置時(shí)，需要控制擬合誤差在一定的范圍內(nèi)，否則較大的誤差會導(dǎo)致較多的自適應(yīng)細(xì)分才能滿足給定的誤差閾值，并且有可能無法保證雙射的對應(yīng)關(guān)系，對后續(xù)擬合過程帶來困難。

2.5.4 自適應(yīng)局部細(xì)分的同時(shí)簡化擬合曲面

在構(gòu)造低扭曲非結(jié)構(gòu)T樣條曲面之后，可以考慮在誤差較大的區(qū)域進(jìn)行自適應(yīng)局部細(xì)分的同時(shí)在誤差較小的區(qū)域簡化擬合曲面。然而，此方法有一個較大的問題：在單次重新參數(shù)化-擬合迭代中對誤差較小的區(qū)域進(jìn)行了簡化，刪除了部分冗余的控制頂點(diǎn)。在下次重新參數(shù)化-擬合迭代過程中，由于在優(yōu)化扭曲的過程中更新了頂點(diǎn)位置，在上次迭代過程中誤差較小的區(qū)域此時(shí)可能誤差較大，需要進(jìn)行自適應(yīng)局部細(xì)分，導(dǎo)致在同一個區(qū)域重復(fù)進(jìn)行了自適應(yīng)細(xì)分和刪除冗余控制點(diǎn)的簡化操作，增加了計(jì)算成本。

2.5.5 先構(gòu)造簡化樣條曲面后優(yōu)化扭曲

由于樣條曲面簡化策略是逐點(diǎn)判斷的，并且在刪除一個節(jié)點(diǎn)后需要重新計(jì)算擬合方程并更新控制點(diǎn)，計(jì)算成本高，此時(shí)可以考慮使用文獻(xiàn)[12]的方法先構(gòu)造滿足誤差約束的簡化樣條曲面，再更新頂點(diǎn)位置優(yōu)化扭曲。但該方法存在一定的限制：更新頂點(diǎn)位置后樣條曲面一般不滿足誤差約束，需要重新進(jìn)行自適應(yīng)局部細(xì)分和樣條曲面簡化，計(jì)算成本同樣較高。

3 實(shí)驗(yàn)和比較

為了驗(yàn)證本文方法可以有效生成誤差有界的低扭曲的簡化樣條曲面，進(jìn)行了相關(guān)的實(shí)驗(yàn)。

3.1 與直接使用多立方體映射對比

絕大多數(shù)使用多立方體映射的目標(biāo)是構(gòu)建低扭曲的對應(yīng)關(guān)系。其中，文獻(xiàn)[21]通過基于旋轉(zhuǎn)驅(qū)動的變形方法得到近似軸對齊形狀，并利用近似軸對齊形狀與多立方體結(jié)構(gòu)之間的近似誤差來代替等距扭曲度量，同時(shí)利用帶約束的優(yōu)化方法，生成與輸入擬合域近似程度很高、且扭曲較低的多立方體映射。圖6分別使用文獻(xiàn)[21]多立方體映射和本文方法的平均扭曲分別為1.334和1.331，控制頂點(diǎn)的個數(shù)分別為1 116和915?？梢钥闯?，本文方法在相同擬合誤差閾值的情況下得到了扭曲更低、控制頂點(diǎn)更少的擬合曲面。

圖6 本文方法與文獻(xiàn)[21]方法的對比結(jié)果((a)輸入；(b)多立方體參數(shù)域；(c)文獻(xiàn)[21]的方法；(d)本文方法)

3.2 數(shù)據(jù)集上的結(jié)果

本文使用()表示輸入擬合域的網(wǎng)格頂點(diǎn)數(shù)目，()表示與擬合域具有相同拓?fù)涞亩嗔⒎襟w參數(shù)域的頂點(diǎn)數(shù)目，()表示自適應(yīng)局部細(xì)分后樣條曲面控制頂點(diǎn)的數(shù)目，()表示簡化樣條曲面控制頂點(diǎn)的數(shù)目，d(×10?3)給出了最大擬合誤差，及平均扭曲、簡化率、自適應(yīng)細(xì)分迭代次數(shù)和奇異點(diǎn)數(shù)。

3.2.1 不同多立方體參數(shù)域比較

對于同一個輸入的擬合域，本文使用不同的參數(shù)得到與給定擬合域具有相同拓?fù)涞墓?jié)點(diǎn)個數(shù)不同的多立方體參數(shù)域。不同的參數(shù)域的結(jié)果如圖7所示，其中圖7(a)表示輸入的待擬合模型，圖7(b)～(d)分別表示隨著多立方體參數(shù)域節(jié)點(diǎn)個數(shù)的增加，所得到的自適應(yīng)局部細(xì)分后滿足擬合誤差的低扭曲樣條曲面和扭曲分布，以及簡化的樣條曲面和扭曲分布。其中參數(shù)域的節(jié)點(diǎn)個數(shù)、樣條曲面的控制點(diǎn)數(shù)、簡化樣條曲面的控制點(diǎn)數(shù)、平均扭曲、簡化率、自適應(yīng)細(xì)分迭代次數(shù)、以及奇異點(diǎn)數(shù)見表1。

從表1可以看出，隨著多立方體參數(shù)域慢慢逼近輸入的擬合域，在相同擬合精度的情況下樣條曲面的平均扭曲逐步降低，自適應(yīng)細(xì)分迭代次數(shù)逐步減少，但樣條曲面控制點(diǎn)的數(shù)量和奇異點(diǎn)數(shù)量逐步增加。

3.2.2 部分結(jié)果展示

本文在具有145個例子的數(shù)據(jù)集上測試了擬合的結(jié)果，全部得到了滿足擬合誤差的樣條擬合結(jié)果，圖8展示了數(shù)據(jù)集中的14個例子，每個例子給出了多立方體參數(shù)域、最終擬合結(jié)果扭曲分布圖和誤差分布圖，其中誤差分布圖中黃色區(qū)域表示非結(jié)構(gòu)T樣條擬合曲面與擬合域之間的誤差趨于擬合誤差閾值的區(qū)域。表2給出了相關(guān)例子實(shí)驗(yàn)結(jié)果，從結(jié)果可以看出，對于給定模型和擬合誤差閾值，本文方法均得到低扭曲的簡化樣條曲面。

圖7 不同的多立方體參數(shù)域((a)輸入；(b)～(d)多立方體參數(shù)域、自適應(yīng)加細(xì)的樣條曲面和扭曲、自適應(yīng)簡化的樣條曲面和扭曲)

表1 不同的多立方體參數(shù)域的實(shí)驗(yàn)結(jié)果

圖8 本文結(jié)果展示

表2 實(shí)驗(yàn)結(jié)果

3.2.3 運(yùn)行時(shí)間分析

本文所有實(shí)驗(yàn)是在配備八核十六線程的英特爾酷睿 i7-4790K處理器和16 GB內(nèi)存的臺式電腦上運(yùn)行的，處理器主頻為2.50 GHz，使用Intel Math Kernel Library?進(jìn)行方程求解。由于樣條曲面簡化策略是逐點(diǎn)判斷，并且在刪除一個節(jié)點(diǎn)后需要重新計(jì)算擬合方程并更新控制點(diǎn)，所以運(yùn)行時(shí)間很長，其主要運(yùn)行時(shí)間在簡化樣條曲面。在自適應(yīng)局部細(xì)分過程中，一次迭代過程中對判斷出大于擬合誤差的區(qū)域同時(shí)細(xì)分，所以自適應(yīng)局部細(xì)分次數(shù)較少，運(yùn)行時(shí)間相對較少。在優(yōu)化逆參數(shù)化時(shí)，相比立方體參數(shù)，多立方體參數(shù)域與擬合域較為相似，所以扭曲相對較低，運(yùn)行時(shí)間同樣相對較少。在表2中給出了整體的時(shí)間，其中約70%時(shí)間花費(fèi)在最后的簡化步驟中?？梢钥闯鲞\(yùn)行時(shí)間主要受多立方參數(shù)域網(wǎng)格頂點(diǎn)數(shù)目和幾何形狀復(fù)雜程度影響，因?yàn)榉墙Y(jié)構(gòu)樣條的計(jì)算時(shí)間與參數(shù)域網(wǎng)格頂點(diǎn)數(shù)目正相關(guān)，所以多立方體數(shù)目越多，運(yùn)行時(shí)間長；另一方面，幾何形狀越復(fù)雜，在刪除操作時(shí)就越容易被拒絕，導(dǎo)致運(yùn)行時(shí)間增長。

4 結(jié)束語

本文提出了一種通過多立方體參數(shù)域的重參數(shù)化-擬合方法來改進(jìn)非結(jié)構(gòu)T樣條擬合結(jié)果的方法，可以對任意復(fù)雜拓?fù)涞臄M合域得到滿足擬合誤差閾值且低扭曲的簡化樣條曲面。此方法通過生成與給定擬合域具有相同拓?fù)涞亩嗔⒎襟w參數(shù)域，然后依次通過重新參數(shù)化、自適應(yīng)局部細(xì)分、簡化樣條曲面策略，在包含145個例子的數(shù)據(jù)集上，均得到低扭曲的滿足擬合誤差閾值的簡化的樣條曲面。與直接使用多立方體參數(shù)域的映射結(jié)果相比，本文結(jié)果的扭曲更低，樣條曲面的控制點(diǎn)更少。

本文方法未考慮具有特征的模型的輸入，雖然保持了在所有的采樣點(diǎn)均滿足擬合誤差閾值，但最終擬合結(jié)果會得到平滑的樣條，未保留模型的某些需要的特征，如圖9所示。T樣條具有支持重節(jié)點(diǎn)的特性，一種可能的方法是利用重節(jié)點(diǎn)來定義特征。解決該問題的關(guān)鍵是將網(wǎng)格上的特征邊參數(shù)化到參數(shù)域的邊上，如何構(gòu)建保持特征的參數(shù)化是值得考慮的問題。

圖9 有特征的模型的結(jié)果

此外，本文方法還有一些可以改進(jìn)的地方：

(1) 本文方法不能在優(yōu)化扭曲過程中改變多立方體的形狀，如前所述，與擬合域越接近的多立方體可以獲得越低的扭曲，但代價(jià)是奇異點(diǎn)和擬合曲面控制點(diǎn)數(shù)量的增加，如何自適應(yīng)的平衡控制點(diǎn)的數(shù)目和擬合的扭曲，是一個非常值得研究的問題。

(2) 所得到的擬合曲面雖然刪除了冗余控制點(diǎn)，使T樣條拓?fù)浣Y(jié)構(gòu)更加簡潔，但計(jì)算成本較高，運(yùn)行時(shí)間較長，主要時(shí)間花費(fèi)在簡化樣條曲面。本文已經(jīng)對簡化算法進(jìn)行了部分局部化，在刪除一個頂點(diǎn)時(shí)，只重新計(jì)算局部的混合函數(shù)并進(jìn)行擬合和距離檢查。

但對不同點(diǎn)之間的刪除判斷進(jìn)行并行計(jì)算存在一些困難，原因在于：盡管樣條的基函數(shù)是局部的，但是每次刪除頂點(diǎn)后，參數(shù)域的網(wǎng)格拓?fù)浒l(fā)生了改變，導(dǎo)致相關(guān)的混合函數(shù)都發(fā)生了改變，原本并行無關(guān)的點(diǎn)可能不再無關(guān)，這導(dǎo)致傳統(tǒng)的并行方法不能直接應(yīng)用到該問題上，并且T樣條混合函數(shù)不具備完全統(tǒng)一的表達(dá)方法，也為并行帶來了較大的難度。

不過本文觀察到刪除冗余控制點(diǎn)耗費(fèi)的主要時(shí)間在距離檢測上，并且此時(shí)所有T樣條混合函數(shù)都是固定的，在該階段應(yīng)該可以設(shè)計(jì)合適的并行算法來提高效率。

另一方面，刪除冗余控制點(diǎn)耗時(shí)較長的另一個原因是后期大量刪除被拒絕，導(dǎo)致運(yùn)行時(shí)間較長，如何設(shè)計(jì)一個更合理的待刪除點(diǎn)的篩選算法也是一個值得研究的問題。

[1] LU Y, YONG J H, SHI K L, et al. B-spline surface fitting to mesh vertices[J]. Science China Information Sciences, 2017, 60(7): 078101.

[2] BERTOLINO G, MONTEMURRO M, PERRY N, et al. An efficient hybrid optimization strategy for surface reconstruction[J]. Computer Graphics Forum, 2021, 40(6): 215-241.

[3] WANG Y M, ZHENG J M. Curvature-guided adaptive T[J]. Computer-Aided Design, 2013, 45(8-9): 1095-1107.

[4] FENG C, TAGUCHI Y. FasTFit: a fast T-spline fitting algorithm[J]. Computer-Aided Design, 2017, 92: 11-21.

[5] LU Z H, JIANG X, HUO G Y, et al. A fast T-spline fitting method based on efficient region segmentation[J]. Computational and Applied Mathematics, 2020, 39(2): 55.

[6] LAI Y K, HU S M, POTTMANN H. Surface fitting based on a feature sensitive parametrization[J]. Computer-Aided Design, 2006, 38(7): 800-807.

[7] BO P B, LING R T, WANG W P. A revisit to fitting parametric surfaces to point clouds[J]. Computers & Graphics, 2012, 36(5): 534-540.

[8] ECK M, HOPPE H. Automatic reconstruction of B-spline surfaces of arbitrary topological type[C]//The 23rd Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1996: 325-334.

[9] YOSHIHARA H, YOSHII T, SHIBUTANI T, et al. Topologically robust B-spline surface reconstruction from point clouds using level set methods and iterative geometric fitting algorithms[J]. Computer Aided Geometric Design, 2012, 29(7): 422-434.

[10] PIEGL L, TILLER W. The NURBS Book[M]. Berlin, Springer, 1997.

[11] SEDERBERG T W, ZHENG J M, BAKENOV A, et al. T-splines and T-NURCCs[J]. ACM Transactions on Graphics, 2003, 22(3): 477-484.

[12] SEDERBERG T W, CARDON D L, FINNIGAN G T, et al. T-spline simplification and local refinement[J]. ACM Transactions on Graphics, 2004, 23(3): 276-283.

[13] ZHENG J M, WANG Y M, SEAH H S. Adaptive T-spline surface fitting to z-map models[C]//The 3rd International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia. New York: ACM Press, 2005: 405-411.

[14] WANG Y M, ZHENG J M. Adaptive T-spline surface approximation of triangular meshes[C]//2007 6th International Conference on Information, Communications & Signal Processing. New York: IEEE Press, 2008: 1-5.

[15] YANG X N, ZHENG J M. Approximate-spline surface skinning[J]. Computer-Aided Design, 2012, 44(12): 1269-1276.

[16] LIN H W, ZHANG Z Y. An efficient method for fitting large data sets using T-splines[J]. SIAM Journal on Scientific Computing, 2013, 35(6): A3052-A3068.

[17] WANG W, ZHANG Y, DU X X, et al. An efficient data structure for calculation of unstructured T-spline surfaces[J]. Visual Computing for Industry, Biomedicine, and Art, 2019, 2(1): 2.

[18] SCOTT M A, SIMPSON R N, EVANS J A, et al. Isogeometric boundary element analysis using unstructured T-splines[J]. Computer Methods in Applied Mechanics and Engineering, 2013, 254: 197-221.

[19] HU X, FU X M, LIU L G. Advanced hierarchical spherical parameterizations[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(6): 1930-1941.

[20] LIU H, YANG Y, LIU Y, et al. Simultaneous interior and boundary optimization of volumetric domain parameterizations for IGA[J]. Computer Aided Geometric Design, 2020, 79: 101853.

[21] YANG Y, FU X M, LIU L G. Computing surface PolyCube-maps by constrained voxelization[J]. Computer Graphics Forum, 2019, 38(7): 299-309.

[22] FU X M, LIU Y, GUO B N. Computing locally injective mappings by advanced MIPS[J]. ACM Transactions on Graphics, 2015, 34(4): 1-12.

Error-bounded unstructured T-spline surface fitting with low distortion

GUAN Qi-chao, LIU Hao, WANG Yuan-cheng, FU Xiao-ming

(School of Mathematical Sciences, University of Science and Technology of China, Hefei Anhui 230000, China)

In order to calculate the unstructured T-spline fitting surface with low distortion and meet the fitting error threshold and fewer control points for any complex topology fitting domain, we presented a step-by-step solution method. First, a polycube structure with the same topology as the fitting domain was generated as the parameter domain, and the corresponding relationship between the surface to be fitted and the parameter domain was optimized through multiple re-parameterization processes, thus obtaining a low distortion mapping suitable for the generation of low fitting error spline surfaces. At the same time, with the local subdivision property of the unstructured T-spline, the region, which did not meet the fitting error threshold, was adaptively subdivided, and the low distortion spline surface meeting the fitting error threshold was obtained. Next, a simplification strategy of fitting surface was presented to delete redundant control vertices. On the basis of meeting the fitting error threshold and low distortion, redundant control vertices were deleted, and a low distortion unstructured T-spline fitting surface was obtained with less control vertices and bounded error. The effectiveness of this method was verified on various complex models. Compared with the latest methods, this method could attain lower parametric distortion with fewer control vertices.

low distortion; unstructured T-spline; surface fitting; polycube structures; local subdivision

TP 391

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

A

2095-302X(2022)06-1104-10

2022-07-20；

：2022-10-25

國家自然科學(xué)基金(61802359)

關(guān)啟超(1998-)，男，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)。E-mail：qcguq@mail.ustc.edu.cn

傅孝明(1988-)，男，副教授，博士。主要研究方向?yàn)閹缀翁幚?、?jì)算機(jī)輔助幾何設(shè)計(jì)等。E-mail：fuxm@ustc.edu.cn

20 July，2022；

25 October，2022

National Natural Science Foundation of China (61802359)

GUAN Qi-chao (1998-), master student. His main research interest covers computer-aided geometric design. E-mail：qcguq@mail.ustc.edu.cn

FU Xiao-ming (1988-), associate professor, Ph.D. His main research interests cover geometric processing and computer-aided geometric design, etc. E-mail：fuxm@ustc.edu.cn