劉艷，壽華好，季康松

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

0 引 言

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

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

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

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

1 理論與方法

1.1 圓平均

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

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

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

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

引理2 細分法的加細頂點對于任意的控制頂點收斂，如果任何頂點序列滿足：

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

2.1 本文的雙參數(shù)4點binary細分法

(1)

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

(2)

(3)

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

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

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

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

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

執(zhí)行?i∈Z;

2.2 收斂性

由三角不等式，有

(4)

式中，

(5)

(6)

(7)

(8)

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

(9)

(10)

由式(4)—(10)，有

由三角不等式，得

(11)

(12)

下面對|sL1sR1|進行估計

因此

(13)

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

證明：由三角不等式，得

(14)

式中，

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

(15)

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

(16)

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

2.3 連續(xù)性

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

由三角不等式，得

(17)

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

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

(18)

(19)

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

(20)

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

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

(21)

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

2.4 數(shù)值圖例

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

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

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

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

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

3.1 本文的3點細分法

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

(22)

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

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

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

(23)

(24)

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

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

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

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

執(zhí)行?i∈Z;

3.2 收斂性

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

由三角不等式，得

(25)

利用三角不等式對|sL1sR1|進行估計，有

(26)

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

(27)

由式(25)—(27)，得

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

(28)

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

3.3 連續(xù)性

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

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

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

(29)

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

再由引理5，得

(30)

(31)

(32)

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

(33)

由式(29)—(33)，有

(34)

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

(35)

3.4 實驗與比較

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

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

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

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

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

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

圖12 不同細分方法的圓的再生力比較

圖13 例1曲線模型

圖14 例2曲線模型

圖15 例3曲線模型

4 結(jié) 論

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

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