B-Spline Curve Library in Open Cascade
Open Cascade中的B样条曲线库
摘要Abstract：简要介绍Open Cascade中的B样条曲线库BSplCLib的使用方法，并且结合源程序来对Open Cascade中的B样条曲线的组成部分如节点矢量、重复度等概念进行介绍，以及通过对计算B样条基函数的算法进行分析，加深对B样条曲线概念的理解。
关键字Key Word：B Spline Curve、Open Cascade、Knot Vector、Multiplicity
一、 概述 Overview
1946年由Schoenberg提出了B样条理论，给出了B样条的差分表达式；1972年de Boor和Cox分别独立给出了关于B样条的标准算法。Gordon和Riesenfeld又把B样条理论用于形状描述，最终提出了B样条方法。用B样条基替代了Bernstein基，构造出B样条曲线，这种方法继承了Bezier方法的一切优点，克服了Bezier方法存在的缺点，较成功地解决了局部控制问题，又轻而易举地在参数连续性基础上解决了连接问题，从而使自由曲线曲面形状的描述问题得到较好解决。
p次B样条曲线的定义为：
其中：
l Pi是控制顶点（control point）；
l Ni,p(u)是定义在非周期节点矢量上的p次B样条基函数；
有很多方法可以用来定义B样条基函数以及证明它的一些重要性质。例如，可以采用截尾幂函数的差商定义，开花定义，以及由de Boor和Cox等人提出的递推公式等来定义。我们这里采用的是递推定义方法，因为这种方法在计算机实现中是最有效的。
令U={u0,u1,…,um}是一个单调不减的实数序列，即ui<=ui+1，i=0,1,…,m-1。其中，ui称为节点，U称为节点矢量，用Ni,p(u)表示第i个p次B样条基函数，其定义为：
B样条基有如下性质：
a) 递推性；
b) 局部支承性；
c) 规范性；
d) 可微性；
根据B样条曲线定义可知，给定控制顶点Pi（control points），曲线次数p（degree）及节点矢量U（knot vectors），B样曲线也就确定。对于有理B样条曲线，还需要参数权重（weights）。
二、 OCC中的B样条曲线库 BSplCLib in OCC
在Open Cascade中的工具箱（Toolkit）TKMath中的包（package）BSplCLib是B样条曲线库，为B样条曲线曲面的计算提供了支持。它提供了三方面的功能：
l 对节点矢量（knot vectors）及重复度（multiplicities）的管理；
l 对多维样条的支持，即B样条方法中控制顶点的维数可以是任意维数（dimension）；
l 二维和三维样条曲线的方法；
Open Cascade中的B样条曲线由下列数据项定义：
| 定义 |
变量类型 |
变量名称 |
| 控制顶点control points |
TColgp_Array1OfPnt |
Poles |
| 权重weights |
TColStd_Array1OfReal |
Weights |
| 节点knots |
TColStd_Array1OfReal |
Knots |
| 重数multiplicities |
TColStd_Array1OfInteger |
Mults |
| 次数degree |
Standard_Integer |
Degree |
| 周期性periodicity |
Standard_Boolean |
Periodic |
B样条曲线库BSplCLib提供了一些基本几何算法：
l B样条基函数及其导数的计算BSplCLib::EvalBsplineBasis()；
l 节点插入BSplCLib::InsertKnot()；
l 节点去除BSplCLib::RemoveKnot()；
l 升阶BSplCLib::IncreaseDegree()；
l 降阶；
结合《The NURBS Book》和Open Cascade中的BSplCLib的源程序，可以高效的学习NURBS。《The NURBS Book》中有详细的理论推导及算法描述，而Open Cascade中有可以用来实际使用的程序。理论联系实际，有助于快速理解NURBS的有关概念及其应用。
三、 OCC中B样条曲线库的节点和重数Knots and Multiplicity in BSplCLib
由B样条曲线的可微性可知，节点的重数与B样条曲线的连续性相关。在节点区间内部，Ni,p(u)是无限次可微的，因在每个节点区间内部，它是一个多项式。在节点处Ni,p(u)是p-k次连续的，其中k是节点的重复度（multiplicity，有时也称为重数）。因此，增加次数p将提高曲线的连续性，而增加节点的重复度则使连续性降低。
重复度（multiplicity，有时也称为重数）有两种不同的理解方式：
l 节点在节点矢量中的重复度；
l 节点相对于一个特定的基函数的重复度；
在Open Cascade中对重复度的理解是前者，即节点在节点矢量中的重复度。下面结合源程序来进行说明。
函数BSplCLib::Knots()用来将给定的节点矢量（节点序列knot sequence）转换为节点的重复度不大于1的Knots数组和每个节点对应的重复度Mults数组，且数据Knots和Mults的长度必由函数BSplCLib::KnotsLength()得到。Knots()函数的源程序如下所示：
//
=======================================================================
//
function : Knots
//
purpose : Computes the sequence of knots Knots without repetition
//
of the knots of multiplicity greater than 1.
//
Length of <Knots> and <Mults> must be KnotsLength(KnotSequence,Periodic).
//
=======================================================================
void
BSplCLib::Knots(
const
TColStd_Array1OfReal
&
SeqKnots, TColStd_Array1OfReal
&
knots, TColStd_Array1OfInteger
&
mult,
//
const Standard_Boolean Periodic)
const
Standard_Boolean ) 
{ 
Standard_Real val = SeqKnots(1); Standard_Integer kk=1; knots(kk) = val; mult(kk) = 1; for (Standard_Integer jj=2;jj<=SeqKnots.Length();jj++) 
{ // test on strict equality on nodes if (SeqKnots(jj)!=val) { val = SeqKnots(jj); kk++; knots(kk) = val; mult(kk) = 1; 
} else { mult(kk)++; } } 
}
从上述代码可知，直接使用了不等于来判断两个节点的值是否相同，而没有采用误差处理，即严格的相等比较。程序将节点重复度不大于1的节点及其相应的重复度分别保存到knots和mult中。
四、 B样条曲线的分类 B Spline Curve Type
B样条曲线一般按定义基函数的节点序列是否等距（均匀）分为均匀B样条曲线（Uniform B-Spline Curve）和非均匀B样条曲线（Non Uniform B-Spline Curve）。
B样条曲线按节点序列中节点分布情况不同，又分为四种类型：均匀B样条曲线、准均匀B样条曲线、分段Bezier曲线、一般非均匀B样条曲线。设给定特征多边形顶点Vi，i=0,1,…,n，曲线次数k，则有：
l 均匀B样条曲线（uniform B-Spline curve）：节点序列中节点沿参数轴均匀或等距分布，即所有节点区间长度为大于零的常数（constant）：
l 准均匀B样曲线（quasi-uniform B-Spline curve）：其节点序列中两端节点具有重复度k+1，而所有内节点均匀分布，具有重复度1。
l 分段Bezier曲线（piecewise Bezier curve）：其节点序列中两端节点重复度与准均匀B样条曲线的相同，所不同的是所有内节点重复度为k。
l 非均匀B样条曲线（general non-uniform B-Spline curve）：这是对任意分布的节点序列，只要在数学上成立，即节点序列非递减，都可取。
在基础类模块（Module FoundationClasses）的工具箱（Toolkit TKMath）中的包（GeomAbs）中有对B样样条曲线类型的定义，源程序如下所示：
enum GeomAbs_BSplKnotDistribution {
GeomAbs_NonUniform,
GeomAbs_Uniform,
GeomAbs_QuasiUniform,
GeomAbs_PiecewiseBezier
};
而类BSplCLib主要是用来管理节点和重复度的，所有将节点和重复度也进行了分类。根据节点矢量是否均匀分布，将节点分配方式（Knot Distribution）分为：均匀（BSplCLib_Uniform）和非均匀（BSplCLib_NonUniform）。源程序如下所示：
BSplCLib_NonUniform,
BSplCLib_Uniform
};
根据重复度数组将重复度的分配方式分为如下三种类型：
n BSplCLib_Constant：重复度都相同；
n BSplCLib_QuasiConstant：首、尾节点的重复度与内部节点的重复度不同；
n BSplClib_NonConstant：其它情况；
源程序如下所示：
BSplCLib_NonConstant,
BSplCLib_Constant,
BSplCLib_QuasiConstant
};
判断节点矢量和重复度矢量类型分别由下列函数实现：
l BSplCLib::KnotForm()；
l BSplCLib::MultForm()；
具体的判断方法可以查看源程序。
将节点分布方式与重复度的分布方式进行组合，可以得出B样条曲线的那几种类型。
五、 B样条基函数的计算 Evaluate the B-Spline Basis
B样条基函数的计算主要使用了B样条基了函数的递推公式（Cox-deBoor公式）的局部支撑性质，如下所示：
直接由定义可知：
l Ni,0(u)是一个阶梯函数，它在半开区间u∈[ui, ui+1)外都为零；
l 当次数p>0时，Ni,p(u)是两个p-1次基函数的线性组合；
l 计算一组基函数需要事先指定节点矢量U和次数p；
l 半开区间[ui,ui+1)称为第i个节点区间（knot span），它的长度可以为零，因为相邻节点可以是相同的；
l 计算p次基函数的过程可以生成一个如下形式的三角形陈列：
B样条有局部支撑性，即若u不在区间[ui, ui+p+1)，则Ni,p(u)=0。可从下面的三角形中看出N1,3是N1,0、N2,0、N3,0和N4,0的线性组合，而N1,0在区间[u1, u2)上非零，N2,0在区间[u2,u3)上非零，N3,0在区间[u3,u4)上非零，N4,0在区间[u4,u5)上非零，所以N1,3仅在区间[u1,u5)上非零。
在任意给定的节点区间[uj,uj+1)内，最多有p+1个是非零的，它们是Nj-p,p、Nj-p+1、…、Nj,p。例如，在[u3,u4)上，零次基函数中只有N3,0是非零的，一次基函数只有N2,1和N3,1是非零的，非零的三次基函数只有N0,3、N1,3、N2,3、N3,3。这个性质如下图所示：
上面两幅图中右边的图中所示的推算过程表明，给定节点序列U及B样条曲线的次数p，给出任意一个u值，找出其所在的节点区间[ui,ui+1)上，最多有Ni-p,p，Ni-p+1,p，…，Ni,p个非零的基函数。
例如我们根据递推公式写出二次基函数的一般形式，如下所示：
当给定的u值在区间[u3,u4)上即（i=3）时，根据上面的三角形，得出下列重要结论：
即这两项不需要计算。另外一个重要结论就是图中用相同颜色框中的部分是相同的，也就是下面程序中的变量temp表示的内容。
我们引入下面符号：
由二次基函数推出的三个公式可写为：
上述推导过程为《The NURBS Book》中的算法，算法代码如下所示：
理解了变量temp的意义之后，整个程序就很好理解了。
将Open Cascade中计算基函数的算法是不同的，将其源程序摘抄如下所示：
// function : Build BSpline Matrix
// purpose : Builds the Bspline Matrix
// =======================================================================
Standard_Integer
BSplCLib::EvalBsplineBasis
// (const Standard_Integer Side, // = 1 rigth side, -1 left side
( const Standard_Integer , // = 1 rigth side, -1 left side
const Standard_Integer DerivativeRequest,
const Standard_Integer Order,
const TColStd_Array1OfReal & FlatKnots,
const Standard_Real Parameter,
Standard_Integer & FirstNonZeroBsplineIndex,
math_Matrix & BsplineBasis)
{
// the matrix must have at least DerivativeRequest + 1
// row and Order columns
// the result are stored in the following way in
// the Bspline matrix
// Let i be the FirstNonZeroBsplineIndex and
// t be the parameter value, k the order of the
// knot vector, r the DerivativeRequest :
//
// B (t) B (t) B (t)
// i i+1 i+k-1
//
// (1) (1) (1)
// B (t) B (t) B (t)
// i i+1 i+k-1
//
//
//
//
// (r) (r) (r)
// B (t) B (t) B (t)
// i i+1 i+k-1
//
Standard_Integer
ReturnCode,
ii,
pp,
qq,
ss,
NumPoles,
LocalRequest ;
// ,Index ;
Standard_Real NewParameter,
Inverse,
Factor,
LocalInverse,
Saved ;
// , *FlatKnotsArray ;
ReturnCode = 0 ;
FirstNonZeroBsplineIndex = 0 ;
LocalRequest = DerivativeRequest ;
if (DerivativeRequest >= Order) {
LocalRequest = Order - 1 ;
}
if (BsplineBasis.LowerCol() != 1 ||
BsplineBasis.UpperCol() < Order ||
BsplineBasis.LowerRow() != 1 ||
BsplineBasis.UpperRow() <= LocalRequest) {
ReturnCode = 1 ;
goto FINISH ;
}
NumPoles = FlatKnots.Upper() - FlatKnots.Lower() + 1 - Order ;
BSplCLib::LocateParameter(Order - 1 ,
FlatKnots,
Parameter,
Standard_False,
Order,
NumPoles + 1 ,
ii,
NewParameter) ;
FirstNonZeroBsplineIndex = ii - Order + 1 ;
BsplineBasis( 1 , 1 ) = 1.0e0 ;
LocalRequest = DerivativeRequest ;
if (DerivativeRequest >= Order) {
LocalRequest = Order - 1 ;
}
for (qq = 2 ; qq <= Order - LocalRequest ; qq ++ ) {
BsplineBasis( 1 ,qq) = 0.0e0 ;
for (pp = 1 ; pp <= qq - 1 ; pp ++ ) {
//
// this should be always invertible if ii is correctly computed
//
Factor = (Parameter - FlatKnots(ii - qq + pp + 1 ))
/ (FlatKnots(ii + pp) - FlatKnots(ii - qq + pp + 1 )) ;
Saved = Factor * BsplineBasis( 1 ,pp) ;
BsplineBasis( 1 ,pp) *= ( 1.0e0 - Factor) ;
BsplineBasis( 1 ,pp) += BsplineBasis( 1 ,qq) ;
BsplineBasis( 1 ,qq) = Saved ;
}
}
for (qq = Order - LocalRequest + 1 ; qq <= Order ; qq ++ ) {
for (pp = 1 ; pp <= qq - 1 ; pp ++ ) {
BsplineBasis(Order - qq + 2 ,pp) = BsplineBasis( 1 ,pp) ;
}
BsplineBasis( 1 ,qq) = 0.0e0 ;
for (ss = Order - LocalRequest + 1 ; ss <= qq ; ss ++ ) {
BsplineBasis(Order - ss + 2 ,qq) = 0.0e0 ;
}
for (pp = 1 ; pp <= qq - 1 ; pp ++ ) {
Inverse = 1.0e0 / (FlatKnots(ii + pp) - FlatKnots(ii - qq + pp + 1 )) ;
Factor = (Parameter - FlatKnots(ii - qq + pp + 1 )) * Inverse ;
Saved = Factor * BsplineBasis( 1 ,pp) ;
BsplineBasis( 1 ,pp) *= ( 1.0e0 - Factor) ;
BsplineBasis( 1 ,pp) += BsplineBasis( 1 ,qq) ;
BsplineBasis( 1 ,qq) = Saved ;
LocalInverse = (Standard_Real) (qq - 1 ) * Inverse ;
for (ss = Order - LocalRequest + 1 ; ss <= qq ; ss ++ ) {
Saved = LocalInverse * BsplineBasis(Order - ss + 2 , pp) ;
BsplineBasis(Order - ss + 2 , pp) *= - LocalInverse ;
BsplineBasis(Order - ss + 2 , pp) += BsplineBasis(Order - ss + 2 ,qq) ;
BsplineBasis(Order - ss + 2 ,qq) = Saved ;
}
}
}
FINISH :
return (ReturnCode) ;
}
函数的作用是用来计算所有的基函数及其导数，并将结果以矩阵（数组）的形式保存。结合二次基函数的推导方法，将述代码写成公式的形式。函数的参数及其描述如下表所示：
| 变量 |
描述 |
| DerivativeRequest |
导数的次数 |
| Order |
B样条基函数的阶数(次数+1) |
| FlatKnots |
节点矢量 |
| Parameter |
参数 |
| FirstNonZeroBspline |
第一个非零基函数的索引值 |
| BsplineBasis |
基函数值矩阵 |
当导数次数DerivativeRequest大于B样条基的阶数Order时，将计算导数的次数设置为B样条基的次数（Order-1）。程序代码如下所示：
if (DerivativeRequest >= Order) {
LocalRequest = Order - 1 ;
}
对B样条基数计算结果矩阵BsplineBasis存储空间进行检查。若存储空间不足，则会退出，程序代码如下所示：
BsplineBasis.UpperCol() < Order ||
BsplineBasis.LowerRow() != 1 ||
BsplineBasis.UpperRow() <= LocalRequest) {
ReturnCode = 1 ;
goto FINISH ;
}
确定参数Parameter所在的节点区间的下标（索引值），程序代码如下所示：
BSplCLib::LocateParameter(Order - 1 ,
FlatKnots,
Parameter,
Standard_False,
Order,
NumPoles + 1 ,
ii,
NewParameter) ;
确定参数Parameter所在区间的算法是用二分法搜索得到。程序代码如下所示：
// function : Hunt
// purpose :
// =======================================================================
void BSplCLib::Hunt ( const Array1OfReal & XX,
const Standard_Real X,
Standard_Integer & Ilc)
{
// replaced by simple dichotomy (RLE)
Ilc = XX.Lower();
const Standard_Real * px = & XX(Ilc);
px -= Ilc;
if (X < px[Ilc]) {
Ilc -- ;
return ;
}
Standard_Integer Ihi = XX.Upper();
if (X > px[Ihi]) {
Ilc = Ihi + 1 ;
return ;
}
Standard_Integer Im;
while (Ihi - Ilc != 1 ) {
Im = (Ihi + Ilc) >> 1 ;
if (X > px[Im]) Ilc = Im;
else Ihi = Im;
}
}
确定参数所在区间[ui,ui+1)后，可得到第一个非零基函数的索引值为i-p；
FirstNonZeroBsplineIndex = ii - Order + 1 ;
基函数计算的主要算法代码如下所示：
for (qq = 2 ; qq <= Order - LocalRequest ; qq ++ ) {
BsplineBasis( 1 ,qq) = 0.0e0 ;
for (pp = 1 ; pp <= qq - 1 ; pp ++ ) {
//
// this should be always invertible if ii is correctly computed
//
Factor = (Parameter - FlatKnots(ii - qq + pp + 1 ))
/ (FlatKnots(ii + pp) - FlatKnots(ii - qq + pp + 1 )) ;
Saved = Factor * BsplineBasis( 1 ,pp) ;
BsplineBasis( 1 ,pp) *= ( 1.0e0 - Factor) ;
BsplineBasis( 1 ,pp) += BsplineBasis( 1 ,qq) ;
BsplineBasis( 1 ,qq) = Saved ;
}
}
其中：
为节点区间[ui,ui+1)上的基函数左边部分的系数；
为节点区间[ui-1,ui)上的基函数右边部分的系数；
六、 程序示例 Sample Codes
将上述内容以一个简单示例程序来验证，程序代码如下所示：
* Copyright (c) 2013 eryar All Rights Reserved.
*
* File : Main.cpp
* Author : eryar@163.com
* Date : 2013-03-09
* Version :
*
* Description : Learn the B-Spline Curve library in the Open Cascade.
*
*/
#include < BSplCLib.hxx >
#include < math_Matrix.hxx >
#include < TColStd_Array1OfReal.hxx >
#include < TColStd_Array1OfInteger.hxx >
#include < Geom2d_BSplineCurve.hxx >
#pragma comment(lib, " TKernel.lib " )
#pragma comment(lib, " TKMath.lib " )
#pragma comment(lib, " TKG2d.lib " )
int main( int argc, char * argv[])
{
// Knot vector: [0,0,0,1,2,3,4,4,5,5,5]
TColStd_Array1OfReal knotSeq( 1 , 11 );
knotSeq.Init( 0 );
knotSeq.SetValue( 1 , 0 );
knotSeq.SetValue( 2 , 0 );
knotSeq.SetValue( 3 , 0 );
knotSeq.SetValue( 4 , 1 );
knotSeq.SetValue( 5 , 2 );
knotSeq.SetValue( 6 , 3 );
knotSeq.SetValue( 7 , 4 );
knotSeq.SetValue( 8 , 4 );
knotSeq.SetValue( 9 , 5 );
knotSeq.SetValue( 10 , 5 );
knotSeq.SetValue( 11 , 5 );
cout << " Knot Sequence: [ " ;
for (Standard_Integer i = 1 ; i <= knotSeq.Length(); i ++ )
{
cout << knotSeq.Value(i) << " " ;
}
cout << " ] " << endl;
Standard_Integer knotsLen = BSplCLib::KnotsLength(knotSeq);
TColStd_Array1OfReal knots( 1 , knotsLen);
TColStd_Array1OfInteger mults( 1 , knotsLen);
// Test Knots, Mults and Knot sequence of BSplCLib.
BSplCLib::Knots(knotSeq, knots, mults);
cout << " Knots: [ " ;
for (Standard_Integer i = 1 ; i <= knots.Length(); i ++ )
{
cout << knots.Value(i) << " " ;
}
cout << " ] " << endl;
cout << " Multiplicity: [ " ;
for (Standard_Integer i = 1 ; i <= mults.Length(); i ++ )
{
cout << mults.Value(i) << " " ;
}
cout << " ] " << endl;
if (BSplCLib::KnotForm(knots, 1 , knotsLen) == BSplCLib_Uniform)
{
cout << " Knots is uniform. " << endl;
}
else
{
cout << " Knots is non-uniform. " << endl;
}
Standard_Real rValue = 2.5 ;
Standard_Integer iOrder = 2 + 1 ;
Standard_Integer iFirstNonZeroIndex = 0 ;
math_Matrix bSplineBasis( 1 , 1 , 1 , iOrder, 0 );
BSplCLib::EvalBsplineBasis( 1 , 0 , iOrder, knotSeq, rValue, iFirstNonZeroIndex, bSplineBasis);
cout << " First Non-Zero Basis index: " << iFirstNonZeroIndex << endl;
cout << bSplineBasis << endl;
return 0 ;
}
上述代码对节点矢量、重复度的概念的验证，并以一个实例计算所有非零基函数的值。程序输出为：
Knot Sequence: [ 0 0 0 1 2 3 4 4 5 5 5 ]
Knots: [ 0 1 2 3 4 5 ]
Multiplicity: [ 3 1 1 1 2 3 ]
Knots is uniform.
First Non-Zero Basis index: 3
math_Matrix of RowNumber = 1 and ColNumber = 3
math_Matrix ( 1, 1 ) = 0.125
math_Matrix ( 1, 2 ) = 0.75
math_Matrix ( 1, 3 ) = 0.125
Press any key to continue . . .
七、 结论 Conclusion
通过学习《The NURBS Book》并给合Open Cascade的源程序，理论联系实际，使对NURBS的学习更轻松。
根据B样条基的递推公式，B样条曲线的局部性是通过节点来具体实现的。与Bezier曲线不同的就是增加了节点这个参数。根据Cox-deBoor递推公式亲自推导出一次、二次、三次B样条基函数，可以加深对B样条曲线的理解。
计算给定节点矢量、次数及参数，计算参数所在区间上所有非零基函数算法的步骤为：
l 通过二分法查找出参数所在的节点区间；
l 根据B样条基的局部支撑性，计算出所在节点区间上所有非零基函数；
八、 致谢 Acknowledgments
感谢晓天的支持与鼓励。
九、 参考文献 Bibliography
1． 赵罡，穆国旺，王拉柱译Les Piegl，Wayne Tiller The NURBS Book(Second Edition) 2010 清华大学出版社
2． 莫容，常智勇 计算机辅助几何造型技术 2009 科学出版社
3． 王仁宏，李崇君，朱春钢 计算几何教程 2008 科学出版社
