基于遗传算法的B样条曲线曲面的生成

基于遗传算法的B样条曲线曲面的生成XX-XXB Spline Curve and Surface Generate Based om Genetic AlgorithmXX-XXAbstract: This thesis mainly studies the reconstruction of B-spline closed curves and hierarchical B spline surfaces in reverse engineering. The main contributions are summarized as follows:1.Based on the analysis to the conventional approaches for B-spline curve fitting, it is pointed out that these approaches are easy to result in data redundancy. In curve fitting based on simple genetic algorithm, though node values and parameter values can be optimized at the same time, the number of control points of B-spline curve should be specified in advance. In order to overcome these deficiencies, a new approach of B-spline closed curve fitting to a set of ordered points is presented based on Messay genetic algorithm. With this approach, a B-spline closed curve satisfying the desired shape fidelity can be generated as long as a set of ordered points and the order of B-spline closed curve are input. This approach has strong adaptive capacity and can be applied in a intelligent curve modeling system. Some experimental results demonstrate its effectiveness.2.In this paper, a local adaptive refinement approach for triangular mesh approximation with hierarchical B-spline surface is proposed.in the region exceeding a given error, genetic algorithm is used to optimize the surface adaptively while the B-spline surfaces at different levels keep C2 continuity. The B-spline surfaces generated by the approach can be used for mufti-level network transmission and progressive show.Key words: least square fitting; B-spline closed curve; hierarchical B-spline surface; genetic algorithm摘要: 文本研究了B样条闭曲线重建和层次B样条曲面重建,主要成果概括如下:一、分析和指出在曲线拟合过程中传统方法容易造成数据冗余,而使用基本遗传算法虽然可以同时优化节点值与参数值,减少数据冗余,但是控制顶点个数需要事先人为确定.针对这些不足,本文提出了一种基于Messay遗传算法的自适应B样条闭曲线拟合方法.该方法只要输入B样条闭曲线的阶数和有序数据点就可以得到一条满足预期的形状的B样条曲线.它有较强的自适应能力,可用于智能曲线拟合系统开发.一些实验结果表明该方法是有效的.二、提出了一种局部自适应细化层次B样条曲面逼近三角网格的方法.即利用遗传算法在误差超限的区域上由粗糙到精细地局部自适应优化曲面,同时保持不同层次B样条曲面的C2连续.该方法可减少控制网格规模,最后获得的层次结构的B样条曲面可以用于网络分层传输与渐渐显示.关键词: 最小二乘拟合;B样条闭曲线;层次B样条曲面;遗传算法1 曲线曲面及遗传算法简介1.1 曲线重建技术曲线重建指从己知的采样点集拟合出一条或多条曲线,反映出该点集的形状和走向.它在逆向工程、计算机视觉等方面都有广泛的应用.曲线拟合面临两个关键问题.一个问题是拟合曲线的表示形式,人们通常采用具有良好分析和计算性质的多项式参数曲线,如B样条曲线;另一个问题是拟合误差的定义,用几何距离定义误差是最优的,但难以解析表示,所以通常采用近似几何距离或代数距离来定义拟合误差.同时对参数曲线模型还有一个重要问题是参数化问题.参数化方法可分为两种:一种是固定参数化方法,简单但自适应程度不高,不能对所有的情况都获得较好的参数化;另外一种是动态参数化,在拟合过程中通过算法调整优化参数值,这种方法自适应程度高,但计算耗费大.下面根据已知采样点集合的性质对有序离散点集的曲线拟合和无序离散点集的曲线拟合进行概述.1.2 曲面重建技术随着激光测距扫描仪、计算机辅助断层扫描等三维数字扫描设备的快速发展,使得获取物体表面的点集采样模型变得日趋简单、便宜与准确.从这些表示某一几何形状的采样点集,重建出其内蕴表示的目标曲面,使得这些点集离该目标曲面在某种度量意义下偏差最小,这个过程称为曲面重建.曲面重建被广泛应用于计算机辅助几何设计、计算机图形学、医学图像处理、计算机视觉等众多领域.曲面重建算法很多,如四边域曲面重建、三边域曲面重建、细分曲面重建和层次模型曲面重建.1.2.1 层次模型曲面重建用张量积B样条曲面拟合具有丰富细节的复杂几何模型,传统上利用插入节点进行局部修改.但是对张量积B 样条曲面,节点插入不是局部的过程.插入一个节点向量,相应的要加入一整行和一整列的控制顶点往往造成冗余,从而导致处理的数据量大大增加,降低了效率.为了解决这个问题国内外学者利用多分辨率技术在不用细节层次上去数据进行处理.1995年,Forsey和日Bartels提出了用一种层次B样条的方法来进行曲面拟合和曲面编辑,这种方法能提供很好的连续性,并且具有修改方便的优点.该算法使用了一个层次结构的控制点网格,一步一步地从一个较粗糙的网格到一个较精细的网格来提高逼近的精度,但是它的应用仅限于规则网格.1997年,seungyong Lee等人从图像变形技术出发,提出了散乱数据的多层次B样条插值方法.该方法对给定的一组散乱数据,通过求解一个不定方程的伪逆矩阵来求解一组控制点,再通过最小二乘法来最终得到控制网格.该算法实现起来非常简单、但它的这些优点部分来自于它处理的点集的规模小,由于不加选择的细化,处理时间上远远不能满足需要.1999年张伟强和唐泽圣在seungyong Lee等人的多层次B样条插值算法以及Forsey等人的层次B样条曲面拟合算法的基础上,用一种自适的算法自动对某些需要细化的区域进行细化,这样大大减少计算量,提高计算效率. Martin Bertram利用基于四叉树聚类的方法划分数据点集,在该层的每个聚类用双线性或双二次贝齐尔张量曲面进行拟合,通过节点去除构成该层次一个的B样条曲面.然后通过该B样条曲面计算每个聚类内的点拟合最大误差,如果某个聚类拟合大于给定的误差,则对该聚类进行一次划分,进入下一层次剩余误差进行拟合.这样不断进行下去,直到某一层的每个聚类的最大误差满足给定的误差为止.2006年,童伟华等人研究了用层次隐式张量积B样条曲面对无结构散乱点数据进行曲面重建,该方法相对显式张量B样条曲面重建,其优点是无需要对散乱点集参数化,缺点是不能进行后继的交互修改.1.3 遗传算法简介遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法.它最早由美国密切安大学的Holland教授提出,起源于60年代对自然和人工自适应系统的研究.遗传算法有效性的理论依据为模式定理和积木块假设.模式定理保证了较优的模式的样本呈指数级增长,从而满足了寻找最优解的必要条件,即遗传算法存在着寻找到全局最优解的可能性.而积木块假设指出,遗传算法具备寻找到全局最优解的能力,即具有低阶、短距、高平均适应度的模式在遗传算子作用下,相互结合,能生成高阶、长距、高平均适应度的模式,最终生成全局最优解.近十年来,遗传算法得到迅速发展.目前,遗传算法在计算机辅助设计、数据分析、动态处理、建模与模拟、机器人学、图像处理、函数优化、组合优化、自动控制、遗传编程、数据挖掘、信息战等领域都得到应用,成为求解全局优化问题的有力工具之一.XX-XX：基于遗传算法的B样条曲线曲面的生成1.3.1 基于遗传算法的基本概要基于对自然界中生物遗传与进化机理的模仿,针对不同的问题,很多学者设计了许多不同的编码方法来表示可行解,开发出了许多种不同的遗传算子来模仿不同环境下的生物遗传特性.这样,有不同的编码方法和不同的遗传算子就构成各种不同的遗传算法.但这些遗传算法都有共同的特点,即通过对生物遗传和进化过程中选择、交叉、变异机制的模拟,来完成对问题最优解的自适应搜索过程.1.3.2 遗传算法的主要步骤及特点遗传算法流程：编码和种群初始化种群适应度评价选择交叉变异图1-1遗传算法流程基本遗传算法的主要步骤如下:(1)随机产生一组初始个体构成初始种群,并评价每一个体的适配值(2)判断算法收敛准则是否满足.若满足则输出搜索结果;否则执行一下步骤(3)根据适配值大小以一定方式执行复制操作(4)按交叉概率执行交叉操作(5)按变异概率执行变异操作(6)返回步骤(2)遗传算法的特点:1.遗传算法对问题参数编码成染色体后进行进化操作,而不是针对参数本身,这使得遗传算法不受函数约束条件的限制,如连续性、可导性等.2.遗传算法的搜索过程是从问题解的一个集合开始的,而不是从单个个体开始的,具有隐含并行搜索特性,从而大大减少了陷入局部极小的可能.3.遗传算法使用的遗传操作均是随机操作,同时遗传算法根据个体的适应值进行搜索,无需其他信息(如导数信息等),具有很好的普适性和易扩充性;同时,可以把搜索范田集中到适应度较高的部分搜索空间中,从而提高了搜索效率和灵活性.4.遗传算法具有全局搜索能力,最善于搜索复杂问题和非线性问题.2 样条曲线2.1 B样条曲线的定义B样条曲线的方程定义为：XX-XX ：基于遗传算法的B 样条曲线曲面的生成∑==ni k i i u N d u P 0,)()( (2.1)其中,i d 为控制顶点,控制顶点的个数为1+n 个,对于二次B 样条曲线至少应有3个控制顶点,三次B 样条曲线至少应有4个控制顶点,以此类推;B 样条控制多边形是由控制顶点顺序连成的;k 为B 样条曲线的次数,1+k 为阶数,即三次B 样条曲线的阶数为4,次数为3;u 是参数且其值取决于节点矢量的选取;)(,u Nki 为B 样条基函数,定义为:⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=--+--=⎩⎨⎧<≤=-++++++-++000)()()(,0,1)(1,11111,,10,规定其他若u N u u u u u N u u u u u N u u u u N k i i k i k i k i i k i i k i i i i (2.2) 其中,u i是节点值,],...,,[110uu u k n U ++=构成了k 次B 样条函数的节点矢量.B 样条曲线按照节点矢量中节点分布情况的不同,主要分为四类：均匀B 样条曲线,准均匀B 样条曲线,分段贝齐尔曲线,一般非均匀B 样条曲线.在实际问题中,若采用数字的方法描述物体轮廓,同时还要尽可能的保留物体轮廓的性质,一般是使用非均匀B 样条曲线.非均匀B 样条曲线的节点矢量的值和间距可以取任何值.在本课题中采用的曲线都是非均匀B 样条曲线.2.2 计算B 样条曲线上的点的德布尔算法定义一条k 次的B 样条曲线,则需要确定控制顶点、节点矢量以及次数k .假设给定曲线定义域内的一个参数值u ,则可以通过定义的方法求取曲线上相对应的点.但对于求取B 样条曲线上的点还有一种更为简捷的方法,称为德布尔算法.德布尔算法的递推公式为[46]：⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧=--=⎪⎩⎪⎨⎧==---=+-==⊂∈====++++-+-++=--=-=∑∑000,,2,1,,1,)1(0],[],[,)()()(1111111,,0规定；，，j k j l j l jl j l j l j l j j l j n k i i kk i li ki j l k j l j k j n j j u u u u a k l l i k i k i j d a d a l d d u u u u u d u N d u N d u P (2.3)用上述递推公式即可求出曲线上的点)(u P .XX-XX ：基于遗传算法的B 样条曲线曲面的生成2.3 轮廓数据的获取在反求工程中,首先要采用一定的测量方法得到能代表物体轮廓本身的实测数据点,然后基于这些数据点通过建模的方法产生出相应的CAD 模型.轮廓数据点的提取是构造参数B 样条曲线过程中非常重要的一步,关系到所构造出的参数B 样条曲线的准确程度,因此提取出的轮廓数据点要尽可能的准确.在本课题中,首先采用轮廓追踪的方法获取物体轮廓,但是在计算过程中不需要用到轮廓上所有的点,而且数据点太多会增加计算量,所以在轮廓追踪获取物体轮廓数据的基础上,采用基于曲线曲率提取特征点的方法来获取最终的轮廓数据点,这些数据点不仅能够代表整个轮廓的信息,且数量要尽可能的少. 2.3.1 轮廓追踪在识别图象中的目标时,往往需要用到轮廓追踪.轮廓追踪是通过顺序找出边界点来获取图像的外部轮廓特征.轮廓追踪的方法主要有两种算法,其基本原理为：算法一：探测准则也称为跟踪准则,是用来寻找目标物体轮廓上的第一个边界像素,其基本过程为：首先按照从上到下,从左到右的顺序搜索,最左上方的边界点便是按照顺序所搜索到的第一个黑点,将其记为A1,并在A1的右、下、右下、左下四个方向进行搜索,找到的边界点记为A2.然后将A2作为起始点,并按照右、右下、下、左下、左、左上、上、右上的顺序依次搜索边界点,并记为A3.搜索到A3后,判断程序是否结束：如果A3就是A1点,则说明已经搜索了一圈,搜索程序结束.如果A3不是A1点,则按照上述的方法继续搜索,直至找到A1为止.算法二：首先找到目标物体轮廓上的最左下方的边界点,即为：按从左到右,从下到上的顺序搜索,最左下方的边界点便是按照顺序所搜索到的第一个黑点,将其记为A1.然后从A1开始,沿其左上方的方向开始搜索,如果左上方的点是黑点,则为边界点,否则顺时针旋转当前的搜索方向,继续搜索,直至搜索到一个黑点.将这个黑点作为新的边界点,并逆时针旋转当前的搜索方向,用上述相同的方法继续搜索,直到返回到最初的边界点为止.其中,判断一个点是否为边界点的方法为：如果这个点的上下左右四个方向的邻点都是黑点则说明这个点不是边界点,否则是边界点. 2.3.2 轮廓数据的采样经过轮廓追踪可以获得目标物体轮廓上所有的点,但是在表示封闭的目标物体轮廓时,根本不需要轮廓上所有的点,而且轮廓数据越多,计算量也会越大,因此为了减小计算量,需要对目标物体轮廓上所有的点进行重采样,只要提取出能够代表整个物体轮廓所有信息的尽可能少的点即可.对于一个具有一定形状的目标物体轮廓,其边界上高曲率的点就可以代表整个轮廓的形状,因为高曲率的点含有丰富的轮廓形状信息,足以描述整个目标物体轮廓的形状,而且一些实验也证明了这一点.本课题在对物体轮廓上的数据进行重采样时,将曲率特征作为主要的依据,采用基于质点平衡原理的局部插值方法来确定能够代表整个物体轮廓信息且数量尽可能少的数据点分布,同时还要保证曲率大的地方采样点密集,而曲率小的地方采样点分布稀疏.质点平衡原理的示意图为图 3.1所示.其基本原理为[48]:21,u u 是平衡质心系中各质点的空间位置,其质量分别为21,m m 且满足2m <1m ,则在u 轴上质点系的质心位置c u 可定义为:212211m m u m u m u c ++=(2.4)XX-XX ：基于遗传算法的B 样条曲线曲面的生成图2-1质点平衡原理的示意图由公式 3.4可以看出,如果1m 越大,则c u 的位置就越接近于1u ;如果2m 越大,则c u 的位置就越接近于2u .因此,在重采样的过程中,只要将各点相对应的曲率值看做是各质点的质量,那么质心的位置将趋于曲率大的部分.对于一个点的曲率可按公式3.5进行计算.2/322)(y xy x y x k +-=(2.5)其中,y x ,是数据点的坐标值,y x y x,,和分别代表一阶微分和二阶微分,而离散的有序数据点的微分值可以用其相对应的差分值来代替.若采用向前差分,则可定义为：i i i i i y y y x x x -=-=++11; i i i i i i y y y y x x x x +-=+-=++++1212;2 (2.6)轮廓数据采样的基本流程为：Step1:通过轮廓追踪获取物体轮廓上连续的点,个数即为1num ;设置采样点的个数为2num .Step2:对于物体轮廓上连续的点,先从第一个点开始,相隔l 个点,设置一个采样点.其中,21/num num l =. Step3:将当前的采样点记为i q ,并以i q为中心取其左右各2/l 个点,记为j i q ,,则新的采样点的位置可过解（2.7）公式来确定.∑-==-2/2/,,0))((l l j j i i ji u u uk(2.7)Step4:判断是否达到所设定的采样点的数目,如果满足,则获得最终的轮廓数据,否则将得到的新采样点作为当前的采样点,转到Step3继续执行.XX-XX ：基于遗传算法的B 样条曲线曲面的生成3 B 样条闭曲线拟合的变长度染色体遗传算法3.1 编码、解码方案及初始种群的选取因为实数编码对函数优化问题最为有效,所以本文采用实数编码.需要选取参数),...,1(m i t i=和节点ui),1,...,1(++=k n i 选取的自由变量仅有n 一k+m 个,所以每个个体有n 一k+m 个基因,其中),...,1(m k n i g i+-=初始化为区间{0,1}中的随机数节点向量U 信息 参数向量T 信息图3-1染色体G 结构但是,要得到我们所需要),...,1(m i t i=和ui),1,...,1(++=k n i 上面染色体G 的值还需要编码,在本文中初始种群取22+⨯=k n ,初种群中每个个体的基因个数都是2++k mG 1 G 2...G N图3-2 规模为N 的初始种群3.2 适应度函数的取法最小二乘拟合简单且稳定性好,被广泛应用于曲线拟合,经简化误差可用下式表示：min )()(=--=SP Q SP Q d T (3.1)其中Q 是数据点序列,P 是控制点序列⎰+++=≤u u dt t y t x len S n k 11)))((())(((2'2'(3.2)用以上两式得到的目标函数,使拟合得到的曲线不会得到不需要的震荡,使闭曲线更光顺.所以我们取len dl D +=1（其中∑=-=m i i i Q t B dl 1)(作为适应值）.g 1.......gkn -gk n 1+-gk n 2+-.......gmk n +-g 1,1....... g kn -,1g k n 1,1+-g k n 2,1+-....... gmk n +-,1g1,2.......gkn -,2gk n 1,2+-gk n 2,2+-....... gmk n +-,2... ....... ... ... ... ..........gN 1,.......gkn N -,gk n N 1,+-gk n N 2,+-.......gmk n N +-,XX-XX ：基于遗传算法的B 样条曲线曲面的生成 3.3 选择算子本文采用轮盘赌选择,若个体G i的适应值为D i ,则G i被选中的概率为∑==N i ii i DD P 13.4 剪切算子和拼接算子剪切和拼接操作使种群中染色体不断变化,不仅产生新的染色休,而且染色体的长度也变化,为B 样条闭曲线拟合过程搜索合适控制点数提供更多选择.对种群中的染色体进行随机配对(如果种群规模N 为奇数,剩余一个不参与剪切拼接操作),在(0,l)内均匀随机地生成一个随机数a ,如果pcs a <(pcs 为剪切拼接概率),对一对染色体剪切拼接操作.剪切拼接操作如下:取剪切点),1(),,1(2211L rL r Rand Rand ==,其中),(m n Rand 表示随机产生的[n,m]中的随机整数.对于父代的染色体G 1和G2分别在r1和r2位置进行剪切,交换剪切的部分,然后进行拼接,产生子代染色休. 3.5 变异算子变异算子通过随机地改变每个个体的某些基因来恢复群体的多样性,使得搜索能够达到整个解空间.群体中的所有个体的每个基因都以事先设定的变异概率Pm 的进行变异.具体过程是:对交叉后得到的群体的每个个体的每个基因,先在(0,l)内均匀随机地生成一个随机数b,如果b<Pm,执行变异操作,即在[0,1]均匀随机的取一个值g ’,赋给该基因g 3.6 算法流程Step1:输入B 样条次数k ,平面有序数据序列Q .Step2:初始化.随机产生N (种群规模)个染色体,长度全部为L (因为1++>k m L ,所以一般2++=k m L ),以它们作为变长度遗传算法的初始种群)0(P .Step3:适应度评价.对变长度的染色进行解码处理后,评价或计算各个个体的适应度. Step4:基本处理阶段.对种群)(t P 施加选择算子,以保留适应度高的个体. Step5:并列处理阶段.对种群)(t P ,以概率pm 施加变异算子、以概率pcs 施加切断算子和拼接算子,以生成新的个体. Step6:1+=t t,重复Step3~Step5步,直到满足条件为止.XX-XX ：基于遗传算法的B 样条曲线曲面的生成3.7 实验实例图3-3 2008奥运会会标曲线拟合4 局部自适应细化层次B 样条曲面拟合4.1 B 样条曲面的定义B 样条曲面是B 样条曲线的二维拓广,是由两个B 样条基函数的张量积来定义的,其方程为[46]:∑∑===m i nj l j k i j i v N u N d v u p 00,,,)()(),((3.2)其中,ji d ,称为控制顶点,由)1()1(+⨯+n m 个控制顶点),,1,0;,,1,0(,n j m i d j i ==组成的空间网格称为B样条曲面的控制网格,也称为特征网格;参数u 和参数v 的次数分别为k 和l;B 样条基函数)(,u N k i 与)(,v N l j 分别由u,XX-XX ：基于遗传算法的B 样条曲线曲面的生成 v 参数轴上的节点矢量],,,[110++=k m u u u U 与],,,[110++=l n v v v V 按照公式2.3决定的.除了变差缩减性质外,B 样条曲线的局部支柱性,凸包行,几何变换不变性等性质都可以推广到B 样条曲面.由于B 样条曲面也具有局部性质,因此定义在子矩阵域11,++≤≤<≤f f e e v v v u u u 上的那部分B 样条子曲面片仅和控制点阵中的部分顶点),,1,;,,1,(,f l f l f j e k e k e i d j i +--=+--=有关,与其他顶点无关.相应上述曲面方程就可改写成分片表示形式:∑∑-=-==e k e i flf j l j k i ji v N u N dv u p )()(),(,,, (3.3)与B 样条曲线的分类一样,B 样条曲面沿u,v 两个参数方向中的任一参数方向按照节点的分布情况的不同,可以分为四类:均匀、准均匀、分片贝齐尔与非均匀B 样条曲面. 4.2 基于遗传算法边界曲线同步拟合 4.2.1 编码、解码方案及初始种群的选取在节点区间[0,1]随机产生数对基因进行编码,这些基因构成一个染色体,且节点向量单调递增,因为是随机产生的,所以需要对染色体进行解码. 4.2.2 适应度的选取min )()(1111111=--=P N R P N R f T(3. 4)min )()(2222222=--=P N R P N R f T 同理可以求得3f 和4f ,则目标函数为31min min f f d +=或者42min min f f d +=最小,则适应度取为dF 1=4.2.3 选择算子本文采用轮盘赌选择,若个体Gi的适应值为Fi,则Gi被选中的概率为∑==N i ii iFF P14.2.4 交叉算子本章采用单点交叉.单点交叉指在个体编码串中只随机设置一个交叉点,然后在该点相互交换两个配对个体的部分染色体. 4.2.5 变异算子变异算子通过随机地改变每个个体的某些基因来恢复群体的多样性,使得搜索能够达到整个解空间.群体中的所有个体的每个基因都以事先设定的变异概率Pm 的进行变异.具体过程是:对交叉后得到的群体的每个个体的每个基因,先在(0,l)内均匀随机地生成一个随机数b,如果b<Pm,执行变异操作,即在[0,1]均匀随机的取一个值g ’,赋给该基因g.边界同步拟合算法流程:Step1:输入两个对边边界数据集G 1∂和G 3∂(G 2∂和G 4∂）Step2:初始化.随机产生N(种群规模)个染色体,以它们作为变长度遗传算法的初始种群P(0)Step3:适应度评价.对变长度的染色进行解码处理后,评价或计算各个个体的适应度Step4:基本处理阶段.对种群)(t P 施加选择算子,以保留适应度高的个体Step5:并列处理阶段.对种群)(t P ,以概率pm 施加变异算子、以概率pc 施加杂交算子,以生成新的个体Step6:重复Step3一Step5步SteP7:若满足给定误差E.,则终止程序,输出节点向量U ,两组控制顶点1D 和3D 否则n==n+1,再执行Step2~ Step7步.4.2.6 实验实例图4-1 两个方向的B样条曲线端点插值拟合在图4-1中,给定误差为0.01,对边界数据经过两次同步拟合,获得四条满足误差且端点插值于四个角点的边界曲线.4.3 基面拟合下面分三步构造第1层B样条曲面(基面):(1)首先利用Roater方法参数化内部三角点;(2)然后对内部三角点进行均匀采样;(3)最后在(1)步中给定的参数化下,用以4.2节获得曲线作为边界约束的张量积B样条曲面在最小二乘意义下逼近在(2)步中计算得到的均匀采样点.在误差范围内保证上下两层C2连续;对参数值落在误差超限的扩展区域的数据点进行非均匀采样.利用遗传算法对插入的节点进行编码,使得两个方向的新插入的节点的个数之和固定,而每个方向的新插入的节点的位置和个数可以自适应调整.同时当误差超限的小节点区域个数小于最小包围盒内的小节点区域总个数的三分之一时,采用新规则保留上一层的一些控制顶点不变,然后对非均匀采样点进行约束最小二乘拟合,形成第k+1层B样条曲面;令k=k+1,然后执行基面拟合,误差搜索和局部细化拟合步骤,直到满足误差为止.最后获得的层次B样条曲面表示成基面B样条曲面加上它上面每一层的局部B样条曲面的控制网格偏移量表示的B样条曲面.。