一種任意次非均勻B樣條的細分算法

韓力文， 楊玉婷， 邱志宇

（1. 河北師范大學數學與信息科學學院，河北 石家莊 050024；2. 河北省計算數學與應用重點實驗室，河北 石家莊 050024；3. 沙城中學，河北 張家口 075400）

一種任意次非均勻B樣條的細分算法

韓力文1,2， 楊玉婷3， 邱志宇1

（1. 河北師范大學數學與信息科學學院，河北 石家莊 050024；2. 河北省計算數學與應用重點實驗室，河北 石家莊 050024；3. 沙城中學，河北 張家口 075400）

類似于經典的、應用于任意次均勻B樣條的Lane-Riesenfeld細分算法，提出了一種任意次非均勻 B樣條的細分算法，算法包含加細和光滑兩個步驟，可生成任意次非均勻B樣條曲線。算法是基于于開花方法提出的，不同于以均勻B樣條基函數的卷積公式為基礎的 Lane-Riesenfeld細分算法。通過引入兩個開花多項式，給出了算法正確性的詳細證明。算法的時間復雜度優于經典的任意次均勻 B樣條細分算法，與已有的任意次非均勻B樣條細分算法的計算量相當。

計算機輔助幾何設計；細分；開花；B樣條；非均勻；節點插入

細分方法是簡單高效的離散化幾何造型方法，適用于任意拓撲結構，已在計算機輔助設計和計算機圖形學界得到深入研究和廣泛應用。大量細分方法是基于樣條或是樣條細分的推廣。以B樣條細分為例：1974 年Chaikin提出一種快速光滑曲線生成方法[1]，即二次均勻B樣條細分算法。1980年Lane和Riesenfeld將Chaikin算法推廣到任意次 B樣條細分上，提出任意次均勻 B樣條細分算法[2]。Lane-Riesenfeld算法的第一步是加細，即雙寫控制頂點，第二步是光滑，即d層的中點平均，其中d是曲線次數，該算法為任意次均勻 B樣條曲面細分方法[3-6]的研究提供了理論基礎。Boehm和Cohen et al.分別給出了任意次非均勻節點插入算法，其中 Boehm節點插入算法[7]是在一個節點區間中插入一個節點，在均勻節點情況下 Boehm 算法的計算量低于Lane-Riesenfeld算法；Oslo算法[8]是在一個區間中同時插入多個節點，但是當進行細分時，我們只需要在每個連續的節點區間中插入一個新節點，此時Oslo算法退化為Boehm算法。

開花由Ramshaw[9]提出，現已成為研究樣條理論的強有力工具，如樣條理論中的升階、降階、細分算法、節點插入算法等都可以統一在開花這一工具下進行。2007年Vouga和Goldman給出了 Lane-Riesenfeld算法基于開花方法的兩種證明[10]，該方法比基于B樣條基函數的連續卷積的標準證明[2]和基于de Boor算法的證明[11]更簡單和容易理解。d次非均勻的B樣條曲線細分也可以統一在開花方法下，如 2009年 Schaefer與Goldman 基于開花方法提出類似于Lane-Riesenfeld算法的任意次非均勻B樣條曲線細分算法[12]，以下稱為Schaefer算法，該算法分為加細（雙寫控制頂點）和d層的非均勻光滑；2009年Cashman等基于開花方法，提出一種任意次對稱的非均勻B樣條細分算法[13]，以下稱為Cashman算法，該算法對于奇偶次算法有不同的細分規則，分為加細和層的非均勻光滑。本文基于開花方法提出一種任意次非均勻B樣條的細分算法，該算法第一步為加細：雙寫控制頂點，第二步為層的非均勻光滑。通過引入兩個開花多項式給出了該算法正確性的詳細證明。

圖1 開花的多仿射性質（左圖）和等價意義下的簡寫（右圖）

1 任意次非均勻B樣條的細分算法

1.1 開花方法

本文算法是基于開花方法給出的，首先介紹開花的定義如下。

（1） 對稱性：

其中，σ是對{1,…,n}的任意置換。

（2） 多仿射性：

（3） 對角線性質：

1.2 任意次非均勻B樣條的細分算法

B樣條的開花多項式具有對偶泛函性質，即對于由節點向量τ決定的B樣條P(t)，第i個控制頂點Pi滿足：。

給定兩個開花多項式，若對應節點序列至多有一個不相同，則可利用多仿射性質實現節點x的插入，如下式：

下面詳細介紹任意次非均勻 B樣條的細分算法，算法分為加細和光滑兩步。

第1步是加細，即雙寫控制頂點。為了使最后得到的控制頂點的層數表示一致，將奇偶次加細后的控制頂點分別記為：… ,n，d為偶數；為奇數。

當 i≡ λ(mod 2)時：

當 i- 1 ≡ λ(mod 2)時：

當 i≡ λ(mod 2)時：

當 i- 1 ≡ λ(mod 2)時：

本文算法是任意次的非均勻 B樣條細分算法，圖2給出次數d=5和d=6的算法圖示。算法包含兩種類型的新頂點計算方法，一種是不經過計算直接將上一層的控制頂點作為下一層的控制頂點，如奇次算法最后一層中的雙線箭頭；另一種是由兩個相鄰的舊控制頂點經過多仿射組合得到下一層的新控制頂點。本文未考慮邊界條件和重節點的影響。

2 算法正確性的證明

對于任意次數d，本文所提出的細分算法在細分過程中生成的控制頂點序列的極限為 d次的 B樣條曲線。下面對于奇次的算法給出詳細的證明。

對于函數 rd(m , i)，m個參數為插入節點，d-m個參數為初始節點，且要求。跟據靠近中心原則，將m個插入節點盡可能靠近中心的插入到初始節點向量中，并保證中心節點右側的插入節點比中心節點左側的插入節點多一個。若m為偶數，則中心節點為插入節點，若m為奇數，則中心節點為初始節點，例如：

圖2 次數 d= 5的B樣條細分算法圖示(a)和 d= 6的B樣條細分算法圖示(b)

引理 1對滿足的奇數δ，第δ層的控制頂點滿足：

證明：若初始控制頂點為 n+1個，加細后為2 n+ 2個控制頂點。對于本文所提出的細分算法，當進行前層光滑操作時，每進行一層操作就減少2個控制頂點，層后剩余個控制頂點，且為偶數個。由本文算法可知，在層光滑操作后，其中一半的控制頂點的開花形式中的參數有個插入節點，形如函數另一半控制頂點的開花形式中的參數同樣有個插入節點，形如函數

一般的，下標改變后，算法不變。故對于細分過程中控制頂點有以下結論成立：

即式(7)成立。

由式(4)得：

即式(8)成立。綜上可得：對于任意δ（1 ≤ δ＜d，δ是奇數)，式(7)、式(8)成立。

在前(d - 1)/2步光滑操作滿足引理1的基礎上，要證明奇次算法的正確性，我們只需證明最后一層光滑操作滿足：

定理1對于奇次d，加細后控制頂點滿足：

證明：令由式(5)得：

關于偶次算法，也能得到類似的定理，可通過引入兩個與函數 rd(m , i )類似形式的開花多項式，證明算法對于偶次情況的正確性。

3 時間復雜度分析

對于次數為 d，初始控制頂點的個數為 n+1的B樣條曲線，現對4種任意次的細分算法從加法計算量和乘法計算角度作比較，如表1所示。

由表1可知：任意次均勻B樣條細分算法：Lane-Riesenfeld算法，該算法的加法和乘法計算量分別為和。本文算法，Schaefer算法，Cashman算法都是任意次非均勻B樣條的細分算法，這些算法的細分過程不同，但是其極限曲線相同。當初始控制頂點個數較多時，可忽略次數對計算量的影響，此時本文算法的加法和乘法計算量約為Lane-Riesenfeld算法的加法和乘法計算量的一半，本文算法與Schaefer算法，Cashman算法的計算量相當。

表1 不同算法所需加法和乘法的計算次數

4 結 論

基于開花方法，提出一種任意次非均勻B樣條的細分算法，該算法第一步為加細，雙寫控制頂點，第二步為層的光滑。通過引入兩個開花多項式，證明了算法的正確性。該算法計算量與已有的任意次非均勻 B樣條細分算法計算量相當。

重節點會帶來細分后節點重數的增加，當節點重數超過B樣條曲線的次數時，需要把極限曲線在重節點處一分為二，由此又會產生相應的邊界問題，這些都是我們需要進一步討論的問題。

[1] Chaikin G. An algorithm for high speed curve generation [J]. Computer Graphics and Image Processing, 1974, 3(4): 346-349.

[2] Lane J, Riesenfeld R. A theoretical development for the computer generation and display of piecewise polynomial surfaces [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1980, 2(1): 35-46.

[3] Prautzsch H. Smoothness of subdivision surfaces at extraordinary points [J]. Advances in Computational Mathematics, 1998, 9: 377-390.

[4] Stam J. On subdivision schemes generalizing uniform B-spline surfaces of arbitrary degree [J]. Computer Aided Geometric Design, 2001, 18(5): 383-396.

[5] Warren J. Weimer H. Subdivision methods for geometric design: a constructive approach [M]. Morgan Kaufmann Publishers, 2001.

[6] Zorin D, Schr?der P. A unified framework for primal/dual quadrilateral subdivision schemes [J]. Computer Aided Geometric Design, 2001, 18(5): 429-454.

[7] Boehm W. Inserting new knots into B-spline curves [J]. Computer Aided Design, 1980, 12(4): 199-201.

[8] Cohen E, Lyche T, Riesenfeld R. Discrete B-splines and subdivision techniques in computer-aided geometric design and computer graphics [J]. Computer Graphics and Image Processing, 1980, 14(2): 87-111.

[9] Ramshaw L. Blossoms are polar forms [J]. Computer Aided Geometric Design, 1989, 6(4): 323-358.

[10] Vouga E, Goldman R. Two blossoming proofs of the Lane-Riesenfeld algorithm [J]. Computing, 2007, 79(3): 153-162.

[11] Goldman R, Warren J. An extension of Chaikin’s algorithm to B-spline curves with knots in geometric progression [J]. Graphical Models and Processing, 1993, 55(1): 58-62.

[12] Schaefer S, Goldman R. Non-uniform subdivision for B-spline of arbitrary degree [J]. Computer Aided Geometric Design, 2009, 26(1): 75-81.

[13] Cashman T J, Dodgson N A, Sabin M A. A symmetric, non-uniform, refine and smooth subdivision algorithm for general degree B-spline [J]. Computer Aided Geometric Design, 2009, 26(4): 94-104.

A Subdivision Algorithm for Non-uniform B-Splines of Arbitrary Degree

Han Liwen1,2, Yang Yuting3, Qiu Zhiyu1
( 1. College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang Hebei 050024, China; 2. Hebei Key Laboratory of Computational mathematics and Applications, Shijiazhuang Hebei 050024, China; 3. Shacheng Senior Middle School, Zhangjiakou Hebei 075400, China )

A subdivision algorithm is presented for non-uniform B-splines of arbitrary degree in a manner similar to the Lane-Riesenfeld subdivision algorithm for uniform B-splines of arbitrary degree. The algorithm contains two steps: refining and smoothing, and achieves non-uniform B-Splines curve of arbitrary degree. The algorithm is based on blossoming rather than the continuous convolution formula for the uniform B-spline basis functions. Two blossoming polynomials are introduced to verify the correctness of the subdivision algorithm. The subdivision algorithm is more efficient than the classical uniform subdivision algorithm for B-splines of arbitrary degree, and as efficient as those currently available non-uniform subdivision algorithms for B-splines of arbitrary degree.

computer aided geometric design; subdivision; blossoming; B-splines; non-uniform; knot insertion

O 241.5

A

2095-302X (2013)04-0056-06

2012-09-08；定稿日期：2012-11-05

國家自然科學基金資助項目（61170107）；河北省教育廳自然科學研究項目（Q2012041）

韓力文（1974-），女，河北石家莊人，副教授，博士，主要研究方向為計算機輔助幾何設計，數字幾何處理。

E-mail：hanliwen@sina.com