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

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

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

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

為了計(jì)算對(duì)于任意復(fù)雜拓?fù)鋽M合域的低扭曲、滿足擬合誤差閾值和較少控制點(diǎn)的非結(jié)構(gòu)T樣條擬合曲面，提出了一種逐步求解的方法。首先，生成與擬合域具有相同拓?fù)涞亩嗔⒎襟w作為參數(shù)域，通過(guò)多次重參數(shù)化過(guò)程優(yōu)化待擬合表面和參數(shù)域之間的對(duì)應(yīng)關(guān)系，得到一個(gè)適用于獲得低擬合誤差樣條曲面的低扭曲映射。與此同時(shí)，利用非結(jié)構(gòu)T樣條局部細(xì)分的性質(zhì)對(duì)不滿足擬合誤差閾值的區(qū)域進(jìn)行自適應(yīng)局部細(xì)分，得到滿足擬合誤差閾值的低扭曲樣條曲面。接下來(lái)，提出一種刪除冗余控制頂點(diǎn)的擬合曲面簡(jiǎ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)過(guò)轉(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)造一個(gè)樣條曲面與輸入的離散數(shù)據(jù)的擬合誤差小于給定的閾值，并盡可能使得擬合曲面的扭曲較低、控制點(diǎn)數(shù)量較少。首先，如果樣條曲面與輸入模型之間的擬合誤差越小，對(duì)原模型細(xì)節(jié)的保留就越多。其次，擬合結(jié)果的扭曲越低，對(duì)擬合曲面進(jìn)行二次設(shè)計(jì)越容易、操作越簡(jiǎn)單，同時(shí)使得數(shù)值模擬精度越高。最后，由于較多的控制頂點(diǎn)不僅會(huì)占用更多的內(nèi)存空間，還提高設(shè)計(jì)師對(duì)于擬合曲面進(jìn)行二次設(shè)計(jì)的難度，因此希望使用較少的控制頂點(diǎn)表示擬合曲面。

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

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

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

本文方法對(duì)于任意復(fù)雜拓?fù)涞妮斎肽Ｐ途艿玫降团で鷶M合曲面，并且在具有145個(gè)復(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)。通過(guò)對(duì)結(jié)點(diǎn)向量的細(xì)化和控制點(diǎn)的調(diào)整，其可以用來(lái)表示任意復(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]。

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

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

在YANG和ZHENG[15]的工作中，提出了一種T樣條曲面蒙皮算法，該算法生成一個(gè)T樣條曲面，可以獨(dú)立構(gòu)造樣條曲面的截面曲線和控制曲線，并在相同擬合誤差閾值的情況下生成的樣條曲線通常比傳統(tǒng)放樣樣條曲線具有更少的控制點(diǎn)。LIN和ZHANG[16]提出了一種漸進(jìn)式T樣條數(shù)據(jù)擬合算法，用于擬合具有T樣條表示的大型數(shù)據(jù)集。作為一種迭代方法，其迭代速度穩(wěn)定，對(duì)未知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 問(wèn)題概述

本文研究誤差有界的低扭曲非結(jié)構(gòu)T樣條曲面擬合問(wèn)題。輸入為任意復(fù)雜拓?fù)涞娜蔷W(wǎng)格擬合域和擬合誤差，其中擬合域包含一組頂點(diǎn)={v}和一組三角形面={f}。其目標(biāo)是計(jì)算一個(gè)非結(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樣條的推廣，通過(guò)向網(wǎng)格中添加奇異點(diǎn)使得樣條具有更強(qiáng)的表達(dá)能力。記網(wǎng)格中每個(gè)節(jié)點(diǎn)連接邊的數(shù)目為該節(jié)點(diǎn)的度()，()≠4且不為T節(jié)點(diǎn)的節(jié)點(diǎn)稱為奇異點(diǎn)。

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

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

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

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

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

真實(shí)的參數(shù)域無(wú)法在平面上繪制出來(lái)，圖1給出了一個(gè)非結(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樣條的定義域之后，需要給出每個(gè)頂點(diǎn)上的混合函數(shù)，每個(gè)混合函數(shù)通過(guò)該頂點(diǎn)進(jìn)行局部定義。根據(jù)T樣條混合函數(shù)的定義方法，如果一個(gè)區(qū)域可以將其鄰域無(wú)扭曲的參數(shù)化到平面上，就可以應(yīng)用平面的T網(wǎng)格定義的方法來(lái)定義空間區(qū)域的T樣條。如圖1中不在陰影區(qū)域上的頂點(diǎn)。對(duì)于這些頂點(diǎn)，首先需將其局部無(wú)扭曲的參數(shù)化到平面，定義基函數(shù)后可以直接映射回多立方體參數(shù)域[17]。

對(duì)于奇異點(diǎn)2領(lǐng)域內(nèi)的頂點(diǎn)，本文使用SCOTT等[18]提出的方法計(jì)算每個(gè)頂點(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個(gè)條件。對(duì)于任意生成的多立方體形狀，只需對(duì)所有面執(zhí)行2次細(xì)分，就可以得到滿足要求的多立方體參數(shù)域，在本文的算法中，初始多立方體參數(shù)域的選擇不會(huì)影響最終的擬合精度。

2.1.4 問(wèn)題挑戰(zhàn)

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

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

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

2.1.5 求解思路

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

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

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

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

用圖2例子來(lái)說(shuō)明本文求解低扭曲非結(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ǎn)化結(jié)果；(g)最終結(jié)果和扭曲)

2.2 低扭曲擬合

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

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

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

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

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

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

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

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

本文使用一個(gè)雙向的能量來(lái)表示2個(gè)曲面上的采樣誤差

其中，第一項(xiàng)是插值誤差，(v)稱為v對(duì)應(yīng)的參數(shù)；第二項(xiàng)是采樣擬合誤差，u是參數(shù)域中的采樣點(diǎn)。在實(shí)驗(yàn)中，采樣點(diǎn)是每個(gè)參數(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ù)的線性組合，由于在擬合過(guò)程中基函數(shù)是固定的，2個(gè)能量都可以表述為未知控制點(diǎn)的二次函數(shù)，可以通過(guò)求解一個(gè)線性方程組得到解。

如圖3所示，對(duì)于圖3(a)中復(fù)雜拓?fù)涞哪Ｐ?，使用本文方法得到圖3(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ì)算成本。

本文通過(guò)最大擬合誤差來(lái)控制擬合的精度，即

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

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

如圖4所示，對(duì)于圖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)，簡(jiǎn)化樣條曲面。

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

2.4 簡(jiǎn)化曲面

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

算法步驟如下：

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

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

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

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

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

步驟4.判斷()所對(duì)應(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)是使用簡(jiǎn)化策略得到的樣條曲面，此時(shí)樣條曲面同樣滿足擬合誤差閾值和低扭曲條件，控制頂點(diǎn)的數(shù)量為3 038；圖5(c)為樣條曲面扭曲分布圖，平均扭曲為1.346。本文的簡(jiǎn)化策略在滿足低擬合誤差和低扭曲的基礎(chǔ)上刪除了1 842個(gè)冗余控制頂點(diǎn)，簡(jiǎn)化率為37.75%。

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

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

2.5.1 扭曲的選取

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

2.5.2 采樣擬合誤差的必要性

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

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

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

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

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

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

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

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

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

3.1 與直接使用多立方體映射對(duì)比

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

圖6 本文方法與文獻(xiàn)[21]方法的對(duì)比結(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ù)目，()表示簡(jiǎn)化樣條曲面控制頂點(diǎn)的數(shù)目，d(×10?3)給出了最大擬合誤差，及平均扭曲、簡(jiǎn)化率、自適應(yīng)細(xì)分迭代次數(shù)和奇異點(diǎn)數(shù)。

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

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

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

3.2.2 部分結(jié)果展示

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

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

表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)存的臺(tái)式電腦上運(yùn)行的，處理器主頻為2.50 GHz，使用Intel Math Kernel Library?進(jìn)行方程求解。由于樣條曲面簡(jiǎn)化策略是逐點(diǎn)判斷，并且在刪除一個(gè)節(jié)點(diǎn)后需要重新計(jì)算擬合方程并更新控制點(diǎn)，所以運(yùn)行時(shí)間很長(zhǎng)，其主要運(yùn)行時(shí)間在簡(jiǎn)化樣條曲面。在自適應(yīng)局部細(xì)分過(guò)程中，一次迭代過(guò)程中對(duì)判斷出大于擬合誤差的區(qū)域同時(shí)細(xì)分，所以自適應(yīng)局部細(xì)分次數(shù)較少，運(yùn)行時(shí)間相對(duì)較少。在優(yōu)化逆參數(shù)化時(shí)，相比立方體參數(shù)，多立方體參數(shù)域與擬合域較為相似，所以扭曲相對(duì)較低，運(yùn)行時(shí)間同樣相對(duì)較少。在表2中給出了整體的時(shí)間，其中約70%時(shí)間花費(fèi)在最后的簡(jiǎn)化步驟中。可以看出運(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í)間長(zhǎng)；另一方面，幾何形狀越復(fù)雜，在刪除操作時(shí)就越容易被拒絕，導(dǎo)致運(yùn)行時(shí)間增長(zhǎng)。

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

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

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

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

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

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

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

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

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

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

國(guó)家自然科學(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