劉艷，壽華好，季康松

浙江工業(yè)大學(xué)理學(xué)院，杭州 310023

0 引 言

在CAGD(computer-aided geometric design)和CG(computer graphics)中，點(diǎn)云曲線曲面重建是一個(gè)廣泛研究的問題。通過采樣設(shè)備獲取測量數(shù)據(jù)，并對其進(jìn)行數(shù)據(jù)擬合，可以實(shí)現(xiàn)對原模型進(jìn)行大致的重建及功能恢復(fù)。但有些情況下，獲取的數(shù)據(jù)點(diǎn)可能不只是簡單的坐標(biāo)信息，可能包含一些幾何約束(任浩杰 等，2022)，如在光學(xué)工程領(lǐng)域?qū)Хㄏ蚣s束的數(shù)據(jù)點(diǎn)進(jìn)行光學(xué)反射面設(shè)計(jì)。

與NURBS(non-uniform rational B-splines)相比，細(xì)分允許設(shè)計(jì)高效的、分層的、局部的和自適應(yīng)的算法，用于建模、繪制和操作任意拓?fù)涞淖杂尚螤畹膶ο?。?xì)分是不斷插入新的頂點(diǎn)，更新舊的頂點(diǎn)，從而得到光滑曲線曲面。根據(jù)細(xì)分規(guī)則，細(xì)分曲線可分為線性細(xì)分與非線性細(xì)分。經(jīng)典的線性細(xì)分曲線有Chaikin割角曲線(Chaikin，1974)、4點(diǎn)插值細(xì)分法(Dyn等，1987)及其推廣(Hassan等，2002；鄭紅嬋 等，2004)和單參數(shù)3點(diǎn)ternary插值細(xì)分(鄭紅嬋，2003)。線性細(xì)分通常易于實(shí)現(xiàn)，細(xì)分規(guī)則較為簡單，易分析其收斂性與光滑性，但是產(chǎn)生的極限曲線易有拐點(diǎn)，曲率變化大，并且很難重現(xiàn)圓。

為了克服線性細(xì)分法的缺陷，非線性細(xì)分法得到廣泛關(guān)注。Ding和Hua(2000)提出具有保凸性的非線性4點(diǎn)插值曲線。Yang(2006)提出非線性基于法向量的曲線細(xì)分法，Dyn和Hormann(2012)以及Zhang和Zhang(2010)在此基礎(chǔ)上做了改進(jìn)。Deng和Wang(2010)提出一種基于雙圓弧插值的中心細(xì)分法，Deng和Ma(2012，2014)對其進(jìn)行了改進(jìn)。Mao等人(2016)利用三次Bézier 曲線提出了基于法向量的快速曲線曲面插值細(xì)分方案。在此基礎(chǔ)上，Lipovetsk(2022)提出了基于Bézier平均的非線性細(xì)分法。Zhang等人(2020)提出一種帶張力參數(shù)的任意度非線性廣義細(xì)分法。Bellaihou 和 Ikemakhen(2020)提出一種在空間單位球上生成曲線的非線性幾何細(xì)分法。Lipovetsky和Dyn(2016，2019)提出一種新的基于圓平均的4點(diǎn)非線性細(xì)分法和L-R(Lane-Riesenfeld)算法，并證明了它們的收斂性與連續(xù)性。李彩云等人(2019)提出基于圓平均的帶參數(shù)4點(diǎn)插值細(xì)分與3點(diǎn)逼近細(xì)分。在此基礎(chǔ)上，本文提出基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法與單參數(shù)3點(diǎn)ternary插值細(xì)分法。其中，基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法是基于圓平均的帶參數(shù)4點(diǎn)插值細(xì)分的推廣(李彩云 等，2019)，增加了偏移參數(shù)μ。此外，本文首次提出將圓平均應(yīng)用到ternary插值細(xì)分，這使得細(xì)分過程中控制頂點(diǎn)的增加速度更快。

本文針對有法向量的初始控制頂點(diǎn)，將線性細(xì)分法改寫為點(diǎn)的重復(fù)binary平均，并用圓平均代替線性平均，用加權(quán)測地線平均(Dyn和Sharon，2017)算出的法向量作為新插入頂點(diǎn)的法向量，從而得到兩種基于圓平均的非線性細(xì)分法，并給出了收斂性與連續(xù)性的證明。數(shù)值例子表明，本文的4點(diǎn)細(xì)分法比李彩云等人(2019)提出的4點(diǎn)細(xì)分更加靈活，與相應(yīng)的線性細(xì)分相比，具有更強(qiáng)的曲線造型能力，同時(shí)具有圓的再生力；本文的3點(diǎn)ternary細(xì)分法在實(shí)現(xiàn)插值的同時(shí)，每一次細(xì)分獲得的控制頂點(diǎn)是上一次控制頂點(diǎn)的3倍，這使得細(xì)分過程中控制頂點(diǎn)的增加速度更快，同時(shí)，也具有圓的再生力。

1 理論與方法

1.1 圓平均

1.2 加權(quán)測地線平均

在圓平均中構(gòu)造的新點(diǎn)的法向量nω是n0與n1的加權(quán)測地線平均(Dyn和Sharon，2017)。對于單位法向量n0=(cosα,sinα)與n1=(cosβ,sinβ)的加權(quán)測地線平均定義為G(n0,n1;ω)=(cosγ,sinγ)，其中，α，β，γ是與直角坐標(biāo)系橫坐標(biāo)軸的夾角且γ=(1-ω)α+ωβ。

本文的帶法向約束的圓平均非線性細(xì)分法均是在點(diǎn)—法向量對上進(jìn)行操作，且法向量是基于測地線平均的，獨(dú)立于點(diǎn)的平均。證明本文細(xì)分法的收斂性即證明點(diǎn)和法向量的收斂性，主要依據(jù)下面的引理1(Dyn和Sharon，2017)與引理2(Lipovetsky和Dyn，2016)。

引理1 設(shè)T為適用于流形數(shù)據(jù)的測地線細(xì)分法。如果T有收縮因子，那么T是收斂的。

引理2 細(xì)分法的加細(xì)頂點(diǎn)對于任意的控制頂點(diǎn)收斂，如果任何頂點(diǎn)序列滿足：

2 基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法

2.1 本文的雙參數(shù)4點(diǎn)binary細(xì)分法

(1)

圖1 線性雙參數(shù)4點(diǎn)binary細(xì)分法的細(xì)分過程

(2)

(3)

可以看出，線性雙參數(shù)4點(diǎn)binary細(xì)分法每一次細(xì)分由偏移步與張力步兩步驟組成。用圓平均代替式(2)和式(3)的線性平均，可以得到基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法。與線性雙參數(shù)binary細(xì)分法類似，本文的雙參數(shù)4點(diǎn)binary細(xì)分法每一次細(xì)分也是由偏移步與張力步兩步驟組成，如圖2所示。本法μ=0時(shí)的細(xì)分法是李彩云等人(2019)提出的基于圓平均4點(diǎn)插值細(xì)分法的一個(gè)特例。

圖2 本文的雙參數(shù)4點(diǎn)binary細(xì)分法的細(xì)分過程

算法1 基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法。

輸入：初始控制點(diǎn)及其法向量Pi=(pi,pi),i∈Z。

2)對于k=0,1,2,…,m;

執(zhí)行?i∈Z;

2.2 收斂性

由三角不等式，有

(4)

式中，

(5)

(6)

(7)

(8)

對式(5)和式(8)再次應(yīng)用三角不等式，有

(9)

(10)

由式(4)—(10)，有

由三角不等式，得

(11)

(12)

下面對|sL1sR1|進(jìn)行估計(jì)

因此

(13)

將式(13)代入式(11)，有

證明：由三角不等式，得

(14)

式中，

|sL2sR2|≤ek(1+2B)(李彩云 等，2019)

(15)

將式(13)和式(15)代入式(14)，得

(16)

證明：由引理4和引理5可以得到點(diǎn)的收斂性，再由引理3，可以得到本文的基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法是收斂的。證畢。

2.3 連續(xù)性

圖3 本文的雙參數(shù)4點(diǎn)binary細(xì)分法偏移步中新點(diǎn)與對應(yīng)線性細(xì)分的新點(diǎn)之間的距離

由三角不等式，得

(17)

由Lipovetsky和Dyn(2019)中引理3.2，得

由Zhang等人(2020)中引理4，得

(18)

(19)

將式(12)和式(16)代入式(18)，得

(20)

將式(19)和式(20)代入式(17)，有

又由式(12)和式(16)，可知

(21)

由于當(dāng)張力參數(shù)ω以及偏移參數(shù)μ滿足max{4|μ+2ω|,4ω+|1-4μ-4ω|}<1時(shí)，線性雙參數(shù)binary 4點(diǎn)細(xì)分C1連續(xù)，因此本文提出的細(xì)分法是C1連續(xù)的。證畢。

2.4 數(shù)值圖例

圖4—圖6為基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法的數(shù)值圖例。張力參數(shù)ω刻畫的是新點(diǎn)靠近控制多邊形邊的程度。ω越小，生成的極限曲線越接近初始控制多邊形，如圖4所示。偏移參數(shù)μ刻畫的是細(xì)分過程中第k+1層的新點(diǎn)偏移第k層控制點(diǎn)的程度。μ越小，生成的極限曲線越接近初始控制頂點(diǎn)，如圖5所示。這也充分體現(xiàn)了李彩云等人(2019)的方法是本文基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法的特例，當(dāng)位移參數(shù)μ=0時(shí)，本文方法即為李彩云等人(2019)提出的基于圓平均4點(diǎn)插值細(xì)分法。由于該細(xì)分法在細(xì)分過程中新點(diǎn)的位置與法向量有關(guān)，所以初始控制頂點(diǎn)不同的法向量也會(huì)影響極限曲線，如圖6所示，在初始控制頂點(diǎn)相同，改變其中一個(gè)控制頂點(diǎn)的法向量的情況下，在初始控制頂點(diǎn)的法向量與相鄰2個(gè)控制頂點(diǎn)的法向量相比均變化很大時(shí)，極限曲線出現(xiàn)了自交的情況。因此，選擇合適的法向量可以避免產(chǎn)生的極限曲線。

圖4 不同張力參數(shù)下的基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法的極限曲線

圖5 不同偏移參數(shù)下的基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法的極限曲線

圖6 不同初始點(diǎn)法向量對基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法極限曲線的影響

3 基于圓平均的單參數(shù)3點(diǎn)ternary插值細(xì)分法

3.1 本文的3點(diǎn)細(xì)分法

線性單參數(shù)3點(diǎn)ternary插值細(xì)分法的細(xì)分規(guī)則為

(22)

式中，ω為形狀參數(shù)，細(xì)分進(jìn)程如圖7所示。

圖7 線性單參數(shù)3點(diǎn)ternary細(xì)分法的細(xì)分過程

可以看出，每次細(xì)分過程均由一個(gè)左插步、一個(gè)右插步和一個(gè)插值步組成。當(dāng)1/6<ω<1/3，線性單參數(shù)3點(diǎn)ternary細(xì)分法是收斂的(Zheng，2003)。式(22)可改寫為

(23)

(24)

圖8 本文單參數(shù)3點(diǎn)ternary細(xì)分法的構(gòu)造

算法2 基于圓平均的單參數(shù)3點(diǎn)ternary細(xì)分法

輸入：初始控制點(diǎn)及其法向量Pi=(pi,ni),i∈Z。

2)對于k=0,1,2,…,m;

執(zhí)行?i∈Z;

3.2 收斂性

證明：對于該細(xì)分法法向量的收斂性的證明可參考Dyn和Sharon(2017)與本文引理3的證明，不再給出詳細(xì)證明。下面給出該細(xì)分法點(diǎn)的收斂性證明。

由三角不等式，得

(25)

利用三角不等式對|sL1sR1|進(jìn)行估計(jì)，有

(26)

對θ(sL1,sR1)進(jìn)行估計(jì)，有

(27)

由式(25)—(27)，得

因此，ek+1≤ηkek。其中，

(28)

綜上所述，本文的基于圓平均的單參數(shù)3點(diǎn)ternary插值細(xì)分法是收斂的。證畢。

3.3 連續(xù)性

定理4 當(dāng)形狀參數(shù)滿足2/9<ω<1/3時(shí)，基于圓平均的單參數(shù)3點(diǎn)ternary細(xì)分法是C1連續(xù)的。

證明：與定理2證明過程類似。線性單參數(shù)3點(diǎn)ternary細(xì)分法的每次細(xì)分中，左插步和右插步均可以看做由兩個(gè)內(nèi)插步和一個(gè)平均步組成，如圖8所示。

圖9 本文的單參數(shù)3點(diǎn)ternary細(xì)分法左插步中新點(diǎn)與對應(yīng)線性細(xì)分的新點(diǎn)之間的距離

(29)

由Lipovetsky和Dyn(2019)引理3.2，得

再由引理5，得

(30)

(31)

(32)

將式(26)和式(27)代入式(30)，得

(33)

由式(29)—(33)，有

(34)

由式(27)和式(28)可知

(35)

3.4 實(shí)驗(yàn)與比較

圖10是基于圓平均的單參數(shù)3點(diǎn)ternary插值細(xì)分實(shí)例。如圖10所示，當(dāng)形狀參數(shù)ω分別取0.25，0.275，0.3，0.32時(shí)，基于圓平均的單參數(shù)3點(diǎn)ternary插值細(xì)分生成的極限曲線也不同。該細(xì)分法與初始控制頂點(diǎn)的法向量有關(guān)，如圖11所示，初始控制頂點(diǎn)相同，改變其中一個(gè)控制頂點(diǎn)的法向量，會(huì)出現(xiàn)自交情況，所以選擇合適的法向量可以避免產(chǎn)生極限曲線自交。

圖10 不同參數(shù)ω下的基于圓平均的單參數(shù)3點(diǎn)ternary插值細(xì)分極限曲線

圖11 初始點(diǎn)的法向量對基于圓平均的單參數(shù)3點(diǎn)ternary插值細(xì)分極限曲線的影響(ω=0.325)

實(shí)驗(yàn)將線性雙參數(shù)4點(diǎn)binary細(xì)分法與線性單參數(shù)3點(diǎn)ternary插值細(xì)分法作為線性細(xì)分方案1和線性細(xì)分方案2與本文的兩種細(xì)分法進(jìn)行比較。結(jié)果表明，本文的細(xì)分法具有圓再生力，且生成的極限曲線與傳統(tǒng)方法相比更光滑。

如圖12所示，當(dāng)初始控制頂點(diǎn)從圓采樣，對應(yīng)的法向量為從圓心到頂點(diǎn)指向圓外。方案1與方案2細(xì)分產(chǎn)生的極限曲線都不能重現(xiàn)圓，而基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分法與基于圓平均的單參數(shù)3點(diǎn)ternary插值細(xì)分均能再生圓。

本文提出的基于圓平均的4點(diǎn)細(xì)分與3點(diǎn)細(xì)分的造型能力均比對應(yīng)的線性細(xì)分方法好。實(shí)驗(yàn)選取3個(gè)曲線模型實(shí)例進(jìn)行不同細(xì)分法的曲線重建比較。3個(gè)實(shí)例均是從連續(xù)曲線上采樣獲得的初始控制點(diǎn)及其法向量，生成的曲線均是細(xì)分8次所得。圖13是例1凹形曲線模型的重建，其中，圖13(a)是初始采樣點(diǎn)及其法向量，圖13(b)—(e)分別是線性雙參數(shù)4點(diǎn)binary細(xì)分法、本文的4點(diǎn)細(xì)分法、線性單參數(shù)3點(diǎn)ternary插值細(xì)分法與本文的3點(diǎn)插值細(xì)分法。圖14是例2的曲線模型重建比較，圖15是例3手型曲線模型的重建比較，各子圖含義同圖12。從圖13—圖15可以看出，方案1、方案2和本文方法均能重建曲線，但方案1和方案2生成的曲線都有尖銳點(diǎn)，而本文的4點(diǎn)細(xì)分和3點(diǎn)細(xì)分法生成的曲線都比較光滑，特別是例3，初始控制點(diǎn)與法向量雜亂無章，但用本文方法生成的曲線可更好地重現(xiàn)一張光滑手的形狀。

圖12 不同細(xì)分方法的圓的再生力比較

圖13 例1曲線模型

圖14 例2曲線模型

圖15 例3曲線模型

4 結(jié) 論

本文針對帶法向約束的離散點(diǎn)集重建問題，提出基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分和單參數(shù)3點(diǎn)ternary插值細(xì)分兩種非線性細(xì)分法，利用引理1與引理2 證明了本文兩種細(xì)分法的收斂性與C1連續(xù)性。對基于圓平均的雙參數(shù)4點(diǎn)binary細(xì)分，當(dāng)偏移參數(shù)μ=0時(shí)，可以實(shí)現(xiàn)插值。這也是李彩云等人(2019)提出的基于圓平均的帶參數(shù)4點(diǎn)插值細(xì)分的推廣。對基于圓平均的3點(diǎn)ternary插值細(xì)分，在實(shí)現(xiàn)插值的同時(shí)，每次細(xì)分獲得的控制頂點(diǎn)是上一次控制頂點(diǎn)的3倍，這使得細(xì)分過程中控制頂點(diǎn)的增加速度更快。本文的兩種方法與對應(yīng)的線性細(xì)分法相比，本文方法可以得到更加光滑的曲線，圖像編輯能力強(qiáng)，且具有圓的再生力，克服了線性細(xì)分法容易產(chǎn)生尖銳點(diǎn)、難生成圓的問題。對從3個(gè)封閉連續(xù)曲線實(shí)例上采樣獲得的初始控制點(diǎn)及其法向量的數(shù)據(jù)集，均可以很好地重建。理論證明與數(shù)值實(shí)驗(yàn)表明，本文方法可以較好地解決帶法向約束的離散點(diǎn)集的曲線重建問題。

但是，本文方法仍存在不足之處。當(dāng)離散點(diǎn)集的法向量發(fā)生突變時(shí)，生成的曲線往往會(huì)自交，因此需要選擇合適的法向量避免極限曲線自交。此外，本文方法的參數(shù)滿足什么樣的范圍可達(dá)到C2連續(xù)與C3連續(xù)以及將本文方法推廣到曲面，值得進(jìn)一步探究。