插值與逼近混合的三重細分法

檀結慶，朱星辰，黃丙耀，蔡蒙琪，曹寧寧

（合肥工業大學數學學院，安徽合肥230601）

細分是一種構造光滑曲線曲面的有效方法，由于其具有算法簡單、易于實現的優點，被廣泛運用于計算機輔助幾何設計、計算機圖形學、動漫制作等領域。通常分插值型細分和逼近型細分2種。插值型細分的極限曲線曲面精確地經過所有控制頂點，逼近型細分的極限曲線曲面通常不通過控制頂點。 插值型細分方便形狀控制，DYN等［1］提出了經典的四點插值細分法，并證明了生成的極限曲線是C1連續的。DESLAURIERS 等［2］利用插值多項式得到了2n點b重細分法。 HASSAN等［3］構造了C2連續四點三重插值細分格式。在曲面情形，KOBBELT［4］提出了任意拓撲結構開四邊形網格上的插值細分法。DYN等［5］構造了三角形網格上的一種蝶形細分法。 LI等［6］在Kobbelt插值細分法的基礎上進行改進，提出了一種新的插值型細分法，其正則情形與Kobbelt細分保持一致。相關理論被推廣到三重曲面細分，LI等［7］提出了插值三重曲面細分法。另一方面，逼近型細分可以達到高階連續，HASSAN等［8］構造了三點三重逼近細分格式，SIDDIQI等［9］提出了極限曲線可以達到C6連續的逼近細分格式。 LANE等［10］指出對控制多邊形進行局部平均操作可以得到任意次均勻B-樣條。 將其推廣到曲面情形，STAM［11］提出了生成任意次均勻B-樣條曲面的細分法。類似方法運用到三角形網格，OSWALD等［12］提出了細分法。然而，存在一類帶參數的混合細分格式，通過參數的不同取值，該細分既可以成為插值型細分又可以成為逼近型細分。鄭紅嬋等［13］將單參數的四點插值細分法擴展為雙參數四點二重細分法，既能構造光滑插值曲線，又能構造光滑逼近曲線。PAN等［14］利用松弛技術將插值型細分和逼近型細分相結合，構造了一類C2連續的插值與逼近型細分相結合的細分格式。檀結慶等［15］在插值細分法中引入偏移變量，提出了基于插值細分的逼近細分法。 REHAN等［16］給出了組合型四點三重細分格式。 NOVARA等［17］對組合型四點三重C2和C3收斂的范圍進行了完整的描述。關于曲面情形，MAILLOT等［18］介紹了用push-back操作來漸進插值控制點。文獻［19-20］通過逼近型細分來構造插值型細分。

本文提出了一種新的四點三重插值曲線細分法和一種含參數的三次B-樣條曲線細分法，基于此得到了一種插值與逼近相混合的三重曲線細分法。這種混合細分法使得插值細分和逼近細分統一為同一格式。本文將這種方法推廣到曲面曲線，提出了四邊形網格上的1-9插值曲面細分法和張量積三次B-樣條曲面細分法，利用提出的插值曲面細分法和張量積三次B-樣條曲面細分法，得到了一種插值與逼近相混合的三重曲面細分法。

1 三重曲線細分法

1.1 新的四點三重插值曲線細分法

1.2 含參數的三次B-樣條曲線細分法

1.3 插值與逼近混合的三重曲線細分法

令

式（1）可改寫為

式（2）可改寫為

構造示意圖見圖1。插值與逼近混合的三重曲線細分格式定義如下：

圖1 構造混合三重曲線細分法的幾何示意圖Fig.1 The geometric sketch of constructing blending ternary subdivision scheme

注2 當α=0時，式（7）為插值型曲線細分格式；當α≠0時，式（7）為逼近型曲線細分格式。 特別地，當時，式（7）為D-D四點三重插值格式；當時，式（7）為Hassan四點三重插值細分格式；當α=0，β=0，γ=0時，式（7）為線性B-樣條細分格式；當時，式（7）為二次B-樣條細分格式；當時，式（7）為三次 B-樣條細分格式；當時，式（7）為四次 B-樣條細分格式。

定理1 插值與逼近混合的三重曲線細分法可以達到C3連續。

證明 插值與逼近混合的三重曲線細分格式（7）的掩模

生成的多項式為

易知式（7）的j(j=1,2,3,4)階差商格式的掩模為

可得

式（7）是C2連續的；

2 三重曲面細分法

2.1 四邊形網格上的四點三重插值細分法

基于1.1節新的四點三重插值曲線細分法，本節將其推廣到曲面情形，得到正則四邊形網格上的1-9插值細分法。

給定初始控制網格P0，設Pk為第k次細分后得到的正則四邊形網格，其上的一個4×4子網格

如圖2所示，定義1-9插值細分規則如下：

圖2 正則四邊形網格Pk的一個4×4子網格Fig.2 A4×4sub-mesh of the regular quadrilateral mesh

新頂點的生成規則為

新邊點的生成規則為

生成的示意圖見圖3。

新面點的生成規則為

圖4 生成新面點的示意圖Fig.4 The sketch of computing new face vertices

從而一個四邊形格子分為9個四邊形格子，見圖5，即為1-9插值細分法。

圖5 1-9插值細分法Fig.5 The 1-9 interpolating subdivision scheme

2.2 張量積三次B-樣條細分法

基于1.2節含參數的三次B-樣條曲線細分法，本節將其推廣到曲面情形，得到張量積三次B-樣條曲面細分法。

給定初始控制網格P0，設Pk為第k次細分后得到的正則四邊形網格。

新頂點的生成規則為

生成的示意圖見圖6。

新邊點的生成規則為

生成的示意圖見7。

新面點的生成規則為

生成的示意圖見8。

如此得到了張量積三次B-樣條細分法，見圖9。

2.3 插值與逼近混合的三重曲面細分法

給定初始控制網格P0，設Pk為第k次細分后得到的正則四邊形網格，插值與逼近混合的三重曲面細分規則定義如下：

新頂點的生成規則為

新面點的生成規則為

注3 當α=0時，得到插值型曲面細分法；當α≠0時，得到逼近型曲面細分法。特別地，當時，得到第2.1節1-9插值曲面細分法；當時，得到第2.2節張量積B-樣條曲面細分法。

定理2 插值與逼近混合的三重曲面細分法可以達到C3連續。

證明 由定理1知，插值與逼近混合的三重曲面細分法的生成多項式為式（8），

則由張量積形式推廣得到的插值與逼近混合的三重曲面細分法的生成多項式為

易知，

其中，

其中，

其中，

3 數值實例

利用四點三重插值曲線細分法和三次B-樣條曲線細分法得到了一種插值與逼近混合的三重曲線細分法。這種混合細分法使得插值細分與逼近細分統一為一個格式。將此方法推廣到曲面情形，提出四邊形網格上一種1-9插值曲面細分法和一種張量積B-樣條曲面細分法，利用此兩種曲面細分法得到了一種插值與逼近相混合的三重混合曲面細分法。這些混合細分法所生成的極限曲線曲面，能同時達到插值細分法和逼近細分法生成曲線曲面的效果。其中，參數的取值決定了極限曲線曲面的形狀。在給定初始控制頂點集的情況下，可通過選擇適當的參數來調整和控制曲線曲面。圖10～圖13為利用本文方法生成的極限曲線曲面的數值實例。

圖10為在給定初始控制頂點下分別由插值細分法和逼近細分法生成的極限曲線。其中，（a）為新的四點三重插值曲線細分格式（1）在時生成的極限曲線；（b）為含參數的三次B-樣條曲線細分格式（2）在時生成的極限曲線。

圖10 由插值細分法和逼近細分法生成的極限曲線Fig.10 Limit curves generated by interpolating subdivision scheme and approximating subdivision scheme

圖11顯示的是當初始控制多邊形為正六邊形時，插值與逼近混合的三重曲線細分格式（7）中α,β,γ取不同值時對極限曲線的影響。 其中，（a）所示的極限曲線與控制多邊形完全重合，此時，

圖11 參數取不同值時，式（7）生成的極限曲線Fig.11 Limit curves generated by the formula（7）when the parameter takes different values

（b）所示的極限曲線與控制多邊形相切，此時，

（c）所示的極限曲線精確地通過控制頂點，此時，

（d）所示的極限曲線逼近控制多邊形，此時，

圖11足以說明，混合型三重曲線格式（7）既可生成插值型極限曲線，也可生成逼近型極限曲線；適當選取參數可控制極限曲線的形狀。

在給定的初始控制網格下分別由插值細分法和逼近細分法生成的曲面如圖12所示。其中，（a）為初始控制網格；（b）為當時，四邊形網格上的四點三重插值細分法細分2次后生成的曲面；（c）為細分3次后生成的極限曲面；（d）為當時，張量積B-樣條曲面細分法細分2次后生成的曲面；（e）為細分3次后生成的極限曲面。

圖13為在給定初始控制網格時，插值與逼近混合的三重細分法生成的曲面。其中，（a）為初始控制網格；（b）為當時生成的 極 限 曲 面 ；（c）為 當時生成的極限曲面；（d）為當α=時生成的極限曲面。

4 結 論

給出了一種新的四點三重插值曲線細分法和一種含參數的三次B-樣條曲線細分法，基于此得到了一種插值與逼近相混合的三重曲線細分法。這種混合細分法使得插值細分和逼近細分統一為同一格式。本文將這種方法推廣到曲面曲線，提出了四邊形網格上的1-9插值曲面細分法和張量積三次B-樣條曲面細分法，利用提出的曲面細分法，得到了一種插值與逼近相混合的三重曲面細分法。證明了其極限曲線曲面可以達到C3連續，較于文獻［12-17］提出的細分法生成的極限曲線，具有更高的連續性。最后，用數值實例說明各參數對極限曲線曲面的影響。未來，筆者將進一步研究混合型細分法，得到更高階連續與其他優良性質相統一的細分格式，探究非正則網格上的曲線曲面細分法。