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

韓力文， 楊玉婷， 邱志宇

（1. 河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，河北 石家莊 050024；2. 河北省計(jì)算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050024；3. 沙城中學(xué)，河北 張家口 075400）

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

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

（1. 河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，河北 石家莊 050024；2. 河北省計(jì)算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050024；3. 沙城中學(xué)，河北 張家口 075400）

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

計(jì)算機(jī)輔助幾何設(shè)計(jì)；細(xì)分；開花；B樣條；非均勻；節(jié)點(diǎn)插入

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

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

圖1 開花的多仿射性質(zhì)（左圖）和等價(jià)意義下的簡(jiǎn)寫（右圖）

1 任意次非均勻B樣條的細(xì)分算法

1.1 開花方法

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

（1） 對(duì)稱性：

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

（2） 多仿射性：

（3） 對(duì)角線性質(zhì)：

1.2 任意次非均勻B樣條的細(xì)分算法

B樣條的開花多項(xiàng)式具有對(duì)偶泛函性質(zhì)，即對(duì)于由節(jié)點(diǎn)向量τ決定的B樣條P(t)，第i個(gè)控制頂點(diǎn)Pi滿足：。

給定兩個(gè)開花多項(xiàng)式，若對(duì)應(yīng)節(jié)點(diǎn)序列至多有一個(gè)不相同，則可利用多仿射性質(zhì)實(shí)現(xiàn)節(jié)點(diǎn)x的插入，如下式：

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

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

當(dāng) i≡ λ(mod 2)時(shí)：

當(dāng) i- 1 ≡ λ(mod 2)時(shí)：

當(dāng) i≡ λ(mod 2)時(shí)：

當(dāng) i- 1 ≡ λ(mod 2)時(shí)：

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

2 算法正確性的證明

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

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

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

引理 1對(duì)滿足的奇數(shù)δ，第δ層的控制頂點(diǎn)滿足：

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

一般的，下標(biāo)改變后，算法不變。故對(duì)于細(xì)分過程中控制頂點(diǎn)有以下結(jié)論成立：

即式(7)成立。

由式(4)得：

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

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

定理1對(duì)于奇次d，加細(xì)后控制頂點(diǎn)滿足：

證明：令由式(5)得：

關(guān)于偶次算法，也能得到類似的定理，可通過引入兩個(gè)與函數(shù) rd(m , i )類似形式的開花多項(xiàng)式，證明算法對(duì)于偶次情況的正確性。

3 時(shí)間復(fù)雜度分析

對(duì)于次數(shù)為 d，初始控制頂點(diǎn)的個(gè)數(shù)為 n+1的B樣條曲線，現(xiàn)對(duì)4種任意次的細(xì)分算法從加法計(jì)算量和乘法計(jì)算角度作比較，如表1所示。

由表1可知：任意次均勻B樣條細(xì)分算法：Lane-Riesenfeld算法，該算法的加法和乘法計(jì)算量分別為和。本文算法，Schaefer算法，Cashman算法都是任意次非均勻B樣條的細(xì)分算法，這些算法的細(xì)分過程不同，但是其極限曲線相同。當(dāng)初始控制頂點(diǎn)個(gè)數(shù)較多時(shí)，可忽略次數(shù)對(duì)計(jì)算量的影響，此時(shí)本文算法的加法和乘法計(jì)算量約為L(zhǎng)ane-Riesenfeld算法的加法和乘法計(jì)算量的一半，本文算法與Schaefer算法，Cashman算法的計(jì)算量相當(dāng)。

表1 不同算法所需加法和乘法的計(jì)算次數(shù)

4 結(jié) 論

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

重節(jié)點(diǎn)會(huì)帶來細(xì)分后節(jié)點(diǎn)重?cái)?shù)的增加，當(dāng)節(jié)點(diǎn)重?cái)?shù)超過B樣條曲線的次數(shù)時(shí)，需要把極限曲線在重節(jié)點(diǎn)處一分為二，由此又會(huì)產(chǎn)生相應(yīng)的邊界問題，這些都是我們需要進(jìn)一步討論的問題。

[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

國(guó)家自然科學(xué)基金資助項(xiàng)目（61170107）；河北省教育廳自然科學(xué)研究項(xiàng)目（Q2012041）

韓力文（1974-），女，河北石家莊人，副教授，博士，主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)，數(shù)字幾何處理。

E-mail：hanliwen@sina.com