文档库

最新最全的文档下载
当前位置:文档库 > B样条曲线生成原理及实现

B样条曲线生成原理及实现

收稿日期:2008 06 18

基金项目:湖南省教育厅科研项目(07B009)作者简介:王增波(1975 ),男,讲师,西安科技大学计算机应用专业硕士,研究方向:计算机图形学,e mail:wonbo@http://www.wendangku.net/doc/bce2b6befd0a79563c1e7223.html 。

第27卷 第1期2009年2月

石河子大学学报(自然科学版)

Journal of Shihezi University(Natural Science)

Vol.27 No.1Feb.2009

文章编号:1007 7383(2009)01 0118 04

B 样条曲线生成原理及实现

王增波,彭仁忠,宫兆刚

(衡阳师范学院数学系,湖南衡阳421008)

摘要:为了进一步推广B 样条曲线在各领域的应用,本文从B 样条曲线的概念和定义出发,按节点矢量中节点的分布情况把B 样条曲线划分成均匀B 样条曲线、准均匀B 样条曲线、分段贝齐尔曲线、一般非均匀B 样条曲线4种类型,分别对它们的特点和实现方法进行了详细阐述,最后给出了一个完整的各种B 样条曲线生成代码和运行结果,并进行了详细的对比分析。对于在几何造型和其它方面的应用具有一定的实际价值。关键词:B 样条;控制顶点;基函数

中图分类号:TP391 文献标识码:A

计算机辅助几何设计始兴于20世纪60年代,最初始于飞机、船舶的外形放样工艺。在当时计算机发展的影响下,为了利用计算机更高效地进行设计,人们开始寻找研究曲线或曲面的表示方法,其中最著名、最实用的是法国雷诺汽车公司的工程师提出的B zier 技术[1]和美国机械工程师C oons 提出的Coons 技术

[2,3]

。在大多数情况下,描述产品外形的

曲线或曲面只有大概形状或者只知道它所通过的一系列空间点列,这些点称为控制点,这类曲线或曲面叫自由曲线或自由曲面,而计算机辅助几何设计就是研究自由曲线曲面的表示、设计、显示、分析与综合以及处理等问题。B 样条曲线是Bezier 曲线的改进,对于Bezier 曲线来说,特征多边形顶点个数决定了Bezier 曲线的阶次,并且当n 较大时,特征多边形对曲线的控制将会减弱。改变一个控制顶点的位置会影响整个曲线的形状,这不利于对曲线的局部修改,且Bezier 曲线在很多情况下不能反映特征多边形的特点。1972~1974年Gorden 等将Bezier 的基函数换成B 样条函数,从而构造了等距离节点的B 样条曲线,也称为均匀B 样条曲线。

B 样条曲线的应用范围非常广泛,不仅在几何造型方面,还应用到其它许多方面,如应用B 样条函数处理力学问题[4],结合小波方法应用于图像的完整性认证[5],应用于实验数据的压缩[6],应用于一维、二维空间中轨迹的规划[7]

等。B 样条曲线的应

用范围还在不断的扩大,同时也在不断的改进,因此对它的研究具有一定的应用价值和推广价值。

B 样条曲线造型方法的理论基础是B 样条,下面从B 样条的定义和性质,以及各种B 样条曲线的定义和程序实现方法进行阐述。

1 B 样条曲线生成的原理

1.1 B 样条曲线的定义

B 样条的概念是Schoenberg 于20世纪40年代

提出的[8,9],如今由De Boor [10,11]和C ox [12]分别提出的递推定义,由于其递推的性质使得计算非常简便且很稳定,所以得到了普遍认同。由de Boor 和Cox 分别导出的B 样条递推定义,B 样条可表示为

N j,0(x )=

1,t j x t j +1,

0,其他,

N i ,k (x )=x -t i

t i +k -t i N i ,k -1(x )+

t i +k +1-x

t i +

k +1-

t i +

1

N i +1,k -1(x ),k >0,

约定

=0。(1)

式(1)中,k 表示B 样条的幂次,t 为节点,下标i 为

B 样条的序号。

式(1)表明,欲确定第i 个k 次B 样条N i ,k (x )

需用到t i ,t i +1, ,t i +k +1共k +2个节点,方程中n +1个控制顶点d i (i =0,1, ,n)要用到n +1个k 次B 样条基函数N i,k (x )(i =0,1, ,n )。考察B 样条曲线定义在区间x ![t i ,t i +1]上那一曲线段,略去其中基函数取零值的那些项,则可表示为

P (x )=

?i

j =i =k

d j N j ,k (x ),x ![t i ,t i +1],(2)

式(2)表明,k 次B 样条曲线上定义域内参数为

x ![t i ,t i +1]的一点p (x )至多与k +1个顶点d j (j =i -k ,i -k +1, ,i)有关,与其它顶点无关。

1.2 B 样条曲线的种类及主要性质

本文按不同属性对B 样条曲线分类,其中一种分类法是按节点在曲线定义域内是否均匀分布将B 样条曲线划分为均匀与非均匀。决定B 样条曲线性质最重要的属性是节点矢量,ISO 制定的STEP 国际标准正是按照节点矢量中节点的分布情况不同给出B 样条曲线的类型划分。

由于零次与一次B 样条曲线分别就是控制顶点与控制多边形自身,与所取节点矢量无关,所以下述按节点矢量分类的方法,尽管对零次与一次B 样条曲线也适用,但已经没有意义。下面考虑高于一次的B 样条曲线。仍给定控制顶点d j (j =i -k,i -k +1, ,i)与次数k,有节点矢量T =[t 0,t 1 ,t n +

k +1]

。B 样条曲线按节点矢量中节点的分布情

况不同,可划分为以下4种类型:均匀B 样条曲线、准均匀B 样条曲线、分段贝齐尔曲线、一般非均匀B 样条曲线。均匀、准均匀和非均匀3种类型早就存在,STEP 标准支持把分段贝齐尔曲线作为一种特殊类型。

B 样条曲线具有以下主要性质,正是因为这些性质的存在,才使它得到了广泛的应用。

1)递推性。由上述定义表明。

2)局部性质。定义在非零节点区间x ![t i ,t i +1]上的k 次B 样条曲线,由k +l 个控制顶点及相应的B 样条基函数确定,与其它顶点无关。

3)可微性。k 次B 样条曲线在其定义域内的非零节点区间内部是无限次可微的,即是C #的,或者说具有无穷阶连续性;在定义域内重复度为r 的节点处则是k -r 次可微的,即是C k -r 的,或者说是具有k -r 阶连续性。

4)凸包性质。B 样条曲线的凸包是多个曲线段凸包的并集,其凸包区域小于或等于同一组控制顶点定义的B zier 曲线凸包区域,B 样条曲线恒位于其凸包之内。该性质导致顺序k +1个顶点重合

时,由这些顶点定义的k 次B 样条曲线段退化到这一个重合点;顺序k +1个顶点共线时,由这些顶点定义的k 次B 样条曲线段退化为一直线段。

5)变差减少性质。任一平面与B 样条曲线的交点个数不会超过它与控制多边形的交点数,但包含整个控制多边形的平面除外。该性质导致凸性定理成立,即若定义平面B 样条曲线的控制多边形是凸的(指连接首末顶点构成的封闭多边形为凸的,相重边情况除外),则该平面B 样条曲线也是凸的。

6)磨光性质。除共线顶点外,次数越高,B 样条曲线距离定义它的控制多边形越远。同一组控制顶点定义的B 样条曲线,随次数的升高越来越光滑。

7)几何不变性与仿射不变性。

2 B 样条曲线的生成方法

2.1 均匀B 样条曲线

均匀B 样条曲线节点矢量中节点为沿参数轴均匀或等距分布,所有节点区间长度= i =t i +1-t i =常数>0(i =0,1, ,n +k )。这样的节点矢量定义了均匀B 样条基。程序中可以用一维数组t 保存节点矢量值,在VC 编程中使用以下语句对节点矢量进行赋值:

for(i=0;i<=n+k+1;i++) t[i]=i;

2.2 准均匀B 样条曲线

其节点矢量中二端节点具有重复度k +1,即t 0

=t 1= =t k ,t n +1=t n +2= =t n +k +1,所有内节点均匀分布,重复度为1。定义域x ![t k ,t n +1]内节点区间长度 i =常数>0(i =k ,k +1, ,n)与均匀B 样条曲线定义域内节点分布相同,差别仅在于二端节点。这样的节点矢量定义了准均匀B 样条基。

在VC 编程中用以下语句对节点矢量赋值:

for(i=0;i<=k;i++)t[i]=0; for(i=k+1;i

2.3 分段贝齐尔曲线

其节点矢量中二端节点重复度与类型2相同,为k +1。所不同的是,所有内节点重复度为k 。选用该类型有个限制条件,控制顶点数减1必须等于次数的正整数倍,即n/k 正整数。这样的节点矢量定义了分段伯恩斯坦基。

在VC 编程中用以下语句对节点矢量赋值:for(i=0;i<=k;i++)t[i]=0;

for(i=k+1;i

119第1期 王增波,等:B 样条曲线生成原理及实现

for(int j=0;j

2.4 一般非均匀B 样条曲线

任意分布的节点矢量T =[t 0,t 1 ,t n +

k +1]

,只

要在数学上成立(其中节点序列非递减,二端节点重复度 k +1,内节点重复度 k )都可选取。这样的节点矢量定义了一般非均匀B 样条基,前二种类型都可作为这种类型特例。

在VC 编程中用以下语句对节点矢量赋值:L=n-k;

for(i=0;i<=n+k+1;i++) if(i<=k)t[i]=0;else

if(i<=L+k)t[i]=i-k; else t[i]=L+1;

2.5 B 样条曲线的实现及其意义

本文利用VC++6.0开发环境下,利用MFC 的绘图功能,按照前面所论述的各种B 样条曲线在相同控制顶点的前提下进行绘制,绘制效果如图1所

示。图1中的a 、b 、c 、d 分别是均匀B 样条曲线、准均匀B 样条曲线、分段贝齐尔曲线、一般非均匀B 样条曲线在相同控制顶点的情况下的对照图,从图1可见,不同类型的节点矢量分布情形下将得到不

B样条曲线生成原理及实现

同的曲线轨迹。

图1 各种B 样条曲线对照 图2 贝齐尔曲线和B 样条曲线对比

以上所有的插图都按照B 样条曲线原理用VC 程序进行编制实现。其主要功能体现在节点矢量赋值、基函数生成、图形绘制。程序首先通过鼠标交互的方式标记出7个控制顶点,同时按照点击鼠标的顺序用虚线画出相应的控制多边形,然后通过菜单选取的方式选取不同的B 样条曲线,程序就会自动按不同的选择给数组t[]赋不同的值,最后按同一个控制多边形分别画出4种类型的B 样条曲线。程序核心源代码如下:

void CDra wCurveVie w::B spline(int k,int n,double N[][MAX],double u)

{int L=n-k,i,j;double t[MAX]; for(i=0;i<=n+k+1;i++) for(j=0;j<=n+k+1;j++) N[i][j]=0;//基函数初始化

//基函数生成,其中数组t 存储的是节点矢量值,由上述方法根据不同类型选取相应的赋值方法。

bb=t[k];ee=t[n+k+1];

for(i=0;i<=n;i++)

if(t[i]<=u&&u

for(j=1;j<=k;j++) for(i=0;i<=n;i++)

{double n1,n2;

if(t[i+j]==t[i])n1=0;else n1=(u-t[i])/(t[i+j]-t[i])*N[i][j-1];

if(t[i+j+1]==t[i+1])n2=0;else n2=(t[i +j+1]-u)*N[i+1][j-1]/(t[i+j+1]-t[i+1]);

N[i][j]=n1+n2;}}

//图形生成的核心源代码如下(本程序还实现了对控制多边形修改同时曲线自动修改):

bb=t[k];ee=t[n+k+1];

for(u=bb;u<=ee;u+=0.01){//con 为控制多边形点矩阵 x=y=0;

Bspline(k,ROW-1,N,u); for(i=0;i

x=int(x+.5); y=int(y+.5);

if(abs(int(x-con[ROW-1].x))==0&&abs (int(y-con[ROW-1].y))==0)

120

石河子大学学报(自然科学版) 第27卷

{if(!DragOk)pnum=times;times=0;re turn;} else

{if(abs(int(x -con[0].x))==0&&abs(int(y -con[0].y))==0)o=true;

if(bType!=3||bType==3&&o)

if(begin){dc->Move To(int(x),int(y));begin =0;}

else

if(x*y!=0)dc->Line To(int(x),int(y));}}

3 小结

由上述B 样条曲线的定义、性质和实现可见:1)B 样条曲线采用的基函数保持了用控制顶点

定义曲线,从而继承了贝齐尔方法所具有的优良的控制性质,同时,又克服了贝齐尔方法不具有局部性质的缺点,并在参数连续性上轻而易举地解决了贝齐尔方法在描述复杂形状遇到的连接问题。图2显示了在相同控制顶点下绘制出的贝齐尔曲线和B 样条曲线,可以看出B 样条曲线在左起第4个控制点上所展现在连接方面的优势。

2)B 样条曲线划分的4种类型中,均匀、准均匀与分段贝齐尔3种类型都可以看成一般非均匀的特例。均匀B 样条曲线在曲线定义域内各节点区间上具有用局部参数表示的统一的表达式,使得计算与处理简单方便,但用它定义的均匀B 样条曲线没有保留Bezier 曲线端点的几何性质,即样条曲线的首末端点不再是控制多边形的首末端点,如图1a 所示。采用准均匀的B 样条曲线就是为了解决这个问题,使曲线在端点的行为有较好的控制,如图1b 所示。分段Bezier 曲线实例如图1c 所示,B 样条曲

线用分段Bezier 曲线表示后,各曲线段就具有了相对的独立性,移动曲线段内的一个控制顶点只影响该曲线段的形状,对其它曲线段的形状没有影响,并且Bezier 曲线一整套简单有效的算法都可以原封不动地采用。参考文献:

[1]B zier P E.Example of an existing system in motor industry:

the UNISURF system [J].Proc Roy Soc of London,1971,A321:207 218.

[2]Coons S A.Surfaces for computer aided design of space frms

[R].Cambridge Mass:MIT Project MAC TR 255,1964.[3]Coons S A.Surfaces for computer aided design of space forms,

MIT Project

[4]杜双兴,殷学文,李琪华.B SPli ne 高阶元方法在三维水

弹性力学中的应用[J].船舶力学,2000,4(1):17 23.[5]孙玉文,陈伟卿.B 样条技术在RPM 切片数据处理中的

应用[J].航空精密制造技术,2002,38(4):30 32.[6]葛玉琛,程昌年.实验数据的B 样条压缩法[J].天津职

业技术师范学院学报,2000,10(1):15 16.

[7]任 重,杨灿军.陈 鹰.轨迹规划中的B 样条插值算法

[J].机电工程,2001,18(5):38 39.

[8]Schoenberg I J.Contri bu tions to the Problem of Approx i mation

of Equidistant Data by Analytic Functions [J ].Quart Appl Maths,1946,(4):45 99,112 141.

[9]Curry H B,Schoenberg I J.On Spline Distributions and Their

Limits:The Polya Distribution Functions[J].American Mathe matical Soc,1947,53:1114.

[10]De Boor C.On Calculating with B Spline[J].J Approx Theo

ry,1972,(6):50 62.

[11]De Boor C.A Practical Guide of Splines [M ].Newyork:

Springer,1978.

[12]Cox M.G.T he nu merical Evaluation of B Splines[J].J INS T

Maths Application,1972,10:134 149.

The Creating Principle and Realization of B spline Curve

WANG Zeng bo,PENG Ren zhong,GONG Zhao gang

(Hengyang Normal University,Hengyang,Hunan 421008,China)

Abstract:To further promote the application in various fields,this paper described the basic concept and definition of B spline Curve and they were divided into four types under nodes distribution of node vector.The four types are a uniform B spline curve,a quasi uniform B spline curve,a sub B zier curve,and a general non unifor m B spline curve.Four methods have been introduced in detail and analyzed comparatively.Their source codes,running results and a detailed comparative analysis were given.This paper has certain application value to implement the geometric modeling and others.Key words:B spline;c ontrol points;basis function

121第1期 王增波,等:B 样条曲线生成原理及实现