劉艷,壽華好,季康松
浙江工業大學理學院,杭州 310023
在CAGD(computer-aided geometric design)和CG(computer graphics)中,點云曲線曲面重建是一個廣泛研究的問題。通過采樣設備獲取測量數據,并對其進行數據擬合,可以實現對原模型進行大致的重建及功能恢復。但有些情況下,獲取的數據點可能不只是簡單的坐標信息,可能包含一些幾何約束(任浩杰 等,2022),如在光學工程領域對帶法向約束的數據點進行光學反射面設計。
與NURBS(non-uniform rational B-splines)相比,細分允許設計高效的、分層的、局部的和自適應的算法,用于建模、繪制和操作任意拓撲的自由形狀的對象。細分是不斷插入新的頂點,更新舊的頂點,從而得到光滑曲線曲面。根據細分規則,細分曲線可分為線性細分與非線性細分。經典的線性細分曲線有Chaikin割角曲線(Chaikin,1974)、4點插值細分法(Dyn等,1987)及其推廣(Hassan等,2002;鄭紅嬋 等,2004)和單參數3點ternary插值細分(鄭紅嬋,2003)。線性細分通常易于實現,細分規則較為簡單,易分析其收斂性與光滑性,但是產生的極限曲線易有拐點,曲率變化大,并且很難重現圓。
為了克服線性細分法的缺陷,非線性細分法得到廣泛關注。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)提出一種帶張力參數的任意度非線性廣義細分法。Bellaihou 和 Ikemakhen(2020)提出一種在空間單位球上生成曲線的非線性幾何細分法。Lipovetsky和Dyn(2016,2019)提出一種新的基于圓平均的4點非線性細分法和L-R(Lane-Riesenfeld)算法,并證明了它們的收斂性與連續性。李彩云等人(2019)提出基于圓平均的帶參數4點插值細分與3點逼近細分。在此基礎上,本文提出基于圓平均的雙參數4點binary細分法與單參數3點ternary插值細分法。其中,基于圓平均的雙參數4點binary細分法是基于圓平均的帶參數4點插值細分的推廣(李彩云 等,2019),增加了偏移參數μ。此外,本文首次提出將圓平均應用到ternary插值細分,這使得細分過程中控制頂點的增加速度更快。
本文針對有法向量的初始控制頂點,將線性細分法改寫為點的重復binary平均,并用圓平均代替線性平均,用加權測地線平均(Dyn和Sharon,2017)算出的法向量作為新插入頂點的法向量,從而得到兩種基于圓平均的非線性細分法,并給出了收斂性與連續性的證明。數值例子表明,本文的4點細分法比李彩云等人(2019)提出的4點細分更加靈活,與相應的線性細分相比,具有更強的曲線造型能力,同時具有圓的再生力;本文的3點ternary細分法在實現插值的同時,每一次細分獲得的控制頂點是上一次控制頂點的3倍,這使得細分過程中控制頂點的增加速度更快,同時,也具有圓的再生力。
在圓平均中構造的新點的法向量nω是n0與n1的加權測地線平均(Dyn和Sharon,2017)。對于單位法向量n0=(cosα,sinα)與n1=(cosβ,sinβ)的加權測地線平均定義為G(n0,n1;ω)=(cosγ,sinγ),其中,α,β,γ是與直角坐標系橫坐標軸的夾角且γ=(1-ω)α+ωβ。
本文的帶法向約束的圓平均非線性細分法均是在點—法向量對上進行操作,且法向量是基于測地線平均的,獨立于點的平均。證明本文細分法的收斂性即證明點和法向量的收斂性,主要依據下面的引理1(Dyn和Sharon,2017)與引理2(Lipovetsky和Dyn,2016)。
引理1 設T為適用于流形數據的測地線細分法。如果T有收縮因子,那么T是收斂的。
引理2 細分法的加細頂點對于任意的控制頂點收斂,如果任何頂點序列滿足:
(1)
圖1 線性雙參數4點binary細分法的細分過程
(2)
(3)
可以看出,線性雙參數4點binary細分法每一次細分由偏移步與張力步兩步驟組成。用圓平均代替式(2)和式(3)的線性平均,可以得到基于圓平均的雙參數4點binary細分法。與線性雙參數binary細分法類似,本文的雙參數4點binary細分法每一次細分也是由偏移步與張力步兩步驟組成,如圖2所示。本法μ=0時的細分法是李彩云等人(2019)提出的基于圓平均4點插值細分法的一個特例。
圖2 本文的雙參數4點binary細分法的細分過程
算法1 基于圓平均的雙參數4點binary細分法。
輸入:初始控制點及其法向量Pi=(pi,pi),i∈Z。
2)對于k=0,1,2,…,m;
執行?i∈Z;
由三角不等式,有
(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,可以得到本文的基于圓平均的雙參數4點binary細分法是收斂的。證畢。
圖3 本文的雙參數4點binary細分法偏移步中新點與對應線性細分的新點之間的距離
由三角不等式,得
(17)
由Lipovetsky和Dyn(2019)中引理3.2,得
由Zhang等人(2020)中引理4,得
(18)
(19)
將式(12)和式(16)代入式(18),得
(20)
將式(19)和式(20)代入式(17),有
又由式(12)和式(16),可知
(21)
由于當張力參數ω以及偏移參數μ滿足max{4|μ+2ω|,4ω+|1-4μ-4ω|}<1時,線性雙參數binary 4點細分C1連續,因此本文提出的細分法是C1連續的。證畢。
圖4—圖6為基于圓平均的雙參數4點binary細分法的數值圖例。張力參數ω刻畫的是新點靠近控制多邊形邊的程度。ω越小,生成的極限曲線越接近初始控制多邊形,如圖4所示。偏移參數μ刻畫的是細分過程中第k+1層的新點偏移第k層控制點的程度。μ越小,生成的極限曲線越接近初始控制頂點,如圖5所示。這也充分體現了李彩云等人(2019)的方法是本文基于圓平均的雙參數4點binary細分法的特例,當位移參數μ=0時,本文方法即為李彩云等人(2019)提出的基于圓平均4點插值細分法。由于該細分法在細分過程中新點的位置與法向量有關,所以初始控制頂點不同的法向量也會影響極限曲線,如圖6所示,在初始控制頂點相同,改變其中一個控制頂點的法向量的情況下,在初始控制頂點的法向量與相鄰2個控制頂點的法向量相比均變化很大時,極限曲線出現了自交的情況。因此,選擇合適的法向量可以避免產生的極限曲線。
圖4 不同張力參數下的基于圓平均的雙參數4點binary細分法的極限曲線
圖5 不同偏移參數下的基于圓平均的雙參數4點binary細分法的極限曲線
圖6 不同初始點法向量對基于圓平均的雙參數4點binary細分法極限曲線的影響
線性單參數3點ternary插值細分法的細分規則為
(22)
式中,ω為形狀參數,細分進程如圖7所示。
圖7 線性單參數3點ternary細分法的細分過程
可以看出,每次細分過程均由一個左插步、一個右插步和一個插值步組成。當1/6<ω<1/3,線性單參數3點ternary細分法是收斂的(Zheng,2003)。式(22)可改寫為
(23)
(24)
圖8 本文單參數3點ternary細分法的構造
算法2 基于圓平均的單參數3點ternary細分法
輸入:初始控制點及其法向量Pi=(pi,ni),i∈Z。
2)對于k=0,1,2,…,m;
執行?i∈Z;
證明:對于該細分法法向量的收斂性的證明可參考Dyn和Sharon(2017)與本文引理3的證明,不再給出詳細證明。下面給出該細分法點的收斂性證明。
由三角不等式,得
(25)
利用三角不等式對|sL1sR1|進行估計,有
(26)
對θ(sL1,sR1)進行估計,有
(27)
由式(25)—(27),得
因此,ek+1≤ηkek。其中,
(28)
綜上所述,本文的基于圓平均的單參數3點ternary插值細分法是收斂的。證畢。
定理4 當形狀參數滿足2/9<ω<1/3時,基于圓平均的單參數3點ternary細分法是C1連續的。
證明:與定理2證明過程類似。線性單參數3點ternary細分法的每次細分中,左插步和右插步均可以看做由兩個內插步和一個平均步組成,如圖8所示。
圖9 本文的單參數3點ternary細分法左插步中新點與對應線性細分的新點之間的距離
(29)
由Lipovetsky和Dyn(2019)引理3.2,得
再由引理5,得
(30)
(31)
(32)
將式(26)和式(27)代入式(30),得
(33)
由式(29)—(33),有
(34)
由式(27)和式(28)可知
(35)
圖10是基于圓平均的單參數3點ternary插值細分實例。如圖10所示,當形狀參數ω分別取0.25,0.275,0.3,0.32時,基于圓平均的單參數3點ternary插值細分生成的極限曲線也不同。該細分法與初始控制頂點的法向量有關,如圖11所示,初始控制頂點相同,改變其中一個控制頂點的法向量,會出現自交情況,所以選擇合適的法向量可以避免產生極限曲線自交。
圖10 不同參數ω下的基于圓平均的單參數3點ternary插值細分極限曲線
圖11 初始點的法向量對基于圓平均的單參數3點ternary插值細分極限曲線的影響(ω=0.325)
實驗將線性雙參數4點binary細分法與線性單參數3點ternary插值細分法作為線性細分方案1和線性細分方案2與本文的兩種細分法進行比較。結果表明,本文的細分法具有圓再生力,且生成的極限曲線與傳統方法相比更光滑。
如圖12所示,當初始控制頂點從圓采樣,對應的法向量為從圓心到頂點指向圓外。方案1與方案2細分產生的極限曲線都不能重現圓,而基于圓平均的雙參數4點binary細分法與基于圓平均的單參數3點ternary插值細分均能再生圓。
本文提出的基于圓平均的4點細分與3點細分的造型能力均比對應的線性細分方法好。實驗選取3個曲線模型實例進行不同細分法的曲線重建比較。3個實例均是從連續曲線上采樣獲得的初始控制點及其法向量,生成的曲線均是細分8次所得。圖13是例1凹形曲線模型的重建,其中,圖13(a)是初始采樣點及其法向量,圖13(b)—(e)分別是線性雙參數4點binary細分法、本文的4點細分法、線性單參數3點ternary插值細分法與本文的3點插值細分法。圖14是例2的曲線模型重建比較,圖15是例3手型曲線模型的重建比較,各子圖含義同圖12。從圖13—圖15可以看出,方案1、方案2和本文方法均能重建曲線,但方案1和方案2生成的曲線都有尖銳點,而本文的4點細分和3點細分法生成的曲線都比較光滑,特別是例3,初始控制點與法向量雜亂無章,但用本文方法生成的曲線可更好地重現一張光滑手的形狀。
圖12 不同細分方法的圓的再生力比較
圖13 例1曲線模型
圖14 例2曲線模型
圖15 例3曲線模型
本文針對帶法向約束的離散點集重建問題,提出基于圓平均的雙參數4點binary細分和單參數3點ternary插值細分兩種非線性細分法,利用引理1與引理2 證明了本文兩種細分法的收斂性與C1連續性。對基于圓平均的雙參數4點binary細分,當偏移參數μ=0時,可以實現插值。這也是李彩云等人(2019)提出的基于圓平均的帶參數4點插值細分的推廣。對基于圓平均的3點ternary插值細分,在實現插值的同時,每次細分獲得的控制頂點是上一次控制頂點的3倍,這使得細分過程中控制頂點的增加速度更快。本文的兩種方法與對應的線性細分法相比,本文方法可以得到更加光滑的曲線,圖像編輯能力強,且具有圓的再生力,克服了線性細分法容易產生尖銳點、難生成圓的問題。對從3個封閉連續曲線實例上采樣獲得的初始控制點及其法向量的數據集,均可以很好地重建。理論證明與數值實驗表明,本文方法可以較好地解決帶法向約束的離散點集的曲線重建問題。
但是,本文方法仍存在不足之處。當離散點集的法向量發生突變時,生成的曲線往往會自交,因此需要選擇合適的法向量避免極限曲線自交。此外,本文方法的參數滿足什么樣的范圍可達到C2連續與C3連續以及將本文方法推廣到曲面,值得進一步探究。