样条曲线拟合(通用7篇)
样条曲线拟合 篇1
0引言
B样条曲线曲面拟合是计算机辅助几何设计、逆向工程、再制造工程的基础性问题。传统上,为得到B样条曲线需要解算线性方程组来反求控制点,但这种全局性插值方法,一个插值点的微小变化,会引起反求过程的重新进行和反求结果的全部变动,失去了B样条曲线局部性特点[1]。 基于此,Akemi、周国华等人[2-3]提出了一种用遗传算法对数据点参数化和节点矢量进行优化配置的方法,与传统算法相比,同样精度时用遗传算法的控制点数要少很多,但存在收敛速度慢而导致的计算速度慢问题。齐东旭等[4-5]直接迭代计算插值曲线曲面的控制点,提出了样条曲线拟合的盈亏修正方法,并给出了均匀B样条曲线迭代格式。 蔺宏伟[6]提出了非均匀B-spline曲线曲面的迭代拟合算法,并用矩阵理论证明了迭代极限曲线曲面插值于给定数据点集,算法具有局部性、收敛性、保凸性等优点。史利民等[7]基于文献[6]提出了NURBS曲线曲面拟合数据点的迭代算法。这些迭代算法的计算速度快,对于复杂曲面的拟合优势明显。
B样条拟合曲线往往是在曲线拟合完成之后再去对其进行光顺处理,这就牺牲了曲线拟合精度[8]。本文提出一种B样条曲线迭代算法,即在迭代非均匀B样条曲线算法基础上,加入曲线闭合和二阶几何连续性等约束条件,拟合与光顺处理同步进行,得到一条二阶连续且闭合的非均匀B样条曲线。
1 B-spline G2曲线几何连续性条件
1.1 B-spline曲线表达式
k次B样条曲线定义为:
其中:di(i=0,1,…,n)为控制点;Ni,k(u)(i=0,1,…, n)为k次B样条基函数;节点矢量U满足:u0≤u1≤…≤un+k+1。
1.2计算节点矢量
型值点为qi(i=0,1,…,n),向心弦长参数化能适应数据点的急剧变化,更适合叶片类截面线的拟合[9]。故令所有弦长之和为:给每一型值点qi赋予相应参数值,使其形成一个严格递增序列Δu:
故节点矢量U定义为:
1.3几何连续性条件
本文在处理曲线光顺性问题上采用与参数选取无关的几何连续性来度量。采用Beta约束定义曲线几何连续性,即:
其中:p+(n)与p-(n)分别为公共点处的两侧n阶导矢; βi(i=1,2,…,n)为形状参数,且β1>0。仅仅改变形状参数可改变曲线的形状,对应Gn连续性就存在n个形状参数。
首先,要满足G0连续,就要满足曲线首尾控制点重合,即:
然后,要满足G1连续,k次B样条曲线首尾连接点切矢量为:
将式(2)、式(3)和式(4)代入式(1)中,得到B样条曲线G1连续性条件为:
其次,要满足G2连续,B样条曲线在首尾连接处二阶导矢为:
将式(3)、式(4)、式(5)、式(6)和式(7)代入式(1) 中,得到闭合B样条曲线G2连续性条件为:
其中:δi(i=1,2,…,6)由节点矢量和曲线次数组成,分别为:
2连续闭合曲线的迭代重构算法
2.1算法描述
为了拟合闭合且二阶连续的B样条曲线,在迭代算法中加入闭合和G2连续性条件。具体迭代过程如下:
(1)迭代之初,令:
首尾连接点d00和dn0应满足以下迭代格式:
以{di0}i=0n为控制点集,作一条非均匀B样条曲线:
(2)进一步,记第j个控制顶点首次调整量为:
首尾连接点d01和dn1应满足以下迭代格式:
通过上面的条件得到控制点为{di1}i=0n,以此控制点集拟合非均匀B样条得到:
(3)依次类推,如果已得到第t次迭代后的B样曲线pt(u),记第j个控制顶点的第t+1次调整量为:
同理,首尾连接点d0t+1和dnt+1应满足以下迭代格式:
以{dit+1}i=0n为控制点集,拟合非均匀B样条:
在迭代过程中通过调整β1和β2的取值和迭代次数来得到曲线,既保证了迭代精度又保证了G2曲线连续。
2.2算法修正
在迭代中,发现曲线首尾连接点d0和dn左右分别受两对控制点(d1,dn-1)和(d2,dn-2)的影响,导致这些点误差变大,影响拟合结果。具体分析如下:
由式(19)、式(20)和式(21)知第j个控制点djt+1由Δjt决定,而Δjt又由基函数Ni,k(uj+2)决定;当j=1时,Ni,k(u1+2)(i=0,1,…,n)为:N0,k(u1+2)=1, N1,k(u1+2)=0,…,Nn,k(u1+2)=0,则:
那么,Δ1t=d1t-pt(uj+2)=d1t-d0t,将两个不对应点相减求误差值势必影响d1t+1精确度,同理,其他几个点dn-1t+1、d2t+1和dn-2t+1也存在类似问题。
基于上述不足,将算法作如下调整,即在每一次迭代中,令:
其中:j=3,4,…,n-3。下标j由原来的从1到n-1改变为从3到n-3,而令Δjt=0.001,其中j=1,2,n- 1,n-2。这样就避免了这些控制点误差过大,使曲线拟合精度更高。
3实例验证
本文以扭曲叶片截面轮廓线为实例,取其横截面轮廓线上45个测点,用Visual C++编写该算法计算B样条曲线控制点,并拟合B样条曲线,最后用Imageware检测拟合曲线与原始模型的误差。
图1、图2分别为扭曲叶片横截面轮廓线原始图形和用本文算法迭代20次后拟合的叶片横截面轮廓线。
图3是在Imageware中检测迭代20次后拟合曲线与原曲线之间的误差对比。结果表明迭代20次后曲线拟合最大误差为0.033 1mm,最小误差为0.005mm, 平均误差为0.006 5mm。
将得到的IGES文件格式导入UG,以检验生成的IGES文件是否满足二阶连续性要求。图4为截面线首尾连接处的曲率梳,从图4可以看出,拟合的扭曲叶片截面线曲率梳平滑过渡。
4结论
本文提出了一种迭代拟合非均匀B样条曲线的算法。算法中,加入了曲线首尾闭合及几何连续的二阶Beta约束条件,并基于误差约束对迭代算法做了修正,提高了拟合曲线精度。最后,用扭曲叶片横截面轮廓测点进行了曲线拟合,验证了此算法的有效性。
样条曲线拟合 篇2
1 基于样条曲线拟合的图形图像矢量化处理
图形图像的设计中,在对一幅原始的设计图进行数字矢量化处理时,因信息提取的过程很容易受到外界各种因素的影响,从而影响着数字矢量化处理的效果。在外界因素的影响下,数字矢量化处理会造成图形图像部分数据的丢失,会产生不合理的噪音处理效果等,所以为了保证图形图像的数字矢量化处理效果,需要其他的技术等进行辅助处理[2]。首先结合样条曲线拟合进行图形图像的数字矢量化处理。在信息数据提取时,需要保证样条曲线可以快速地提取,并保证其清晰、准确,以便在图形图像数据提取的过程中,保证矢量化信息处理的功能,进而保证矢量数据处理信息的完整和丰富等。数字矢量化对图形图像进行信息的提取、编辑,都是为了引导图形的处理,保证输入的图形的信息尽可能少地受到外界因素的影响和干扰,对图形图像进行预处理,可以产生较为清晰的轮廓线,为样条曲线的提取做准备[3]。
进行图形图像的预处理之后,还需要进行平滑,消除图像中的震荡信息,保证图像的平滑等,完成平滑之后,需要对图形图像进行图像增强处理。平滑去除了噪声的干扰,也使得图形图像的色彩更加的均匀。在平滑的基础上,对图形图像进行增强处理,可以达到更好的视觉效果,将图形图像的可懂程度提升。图形图像的增强处理,并不会增加原始图像中没有的信息,其只是增强了数字矢量化处理中某种信息的辨别能力[4]。
数字化样条曲线拟合中主要是由于曲线的形态各异,使用全局逼近的数学描述,存在较大的难度,而为了可以使用全局逼近的方法,适合各种曲线、直线的处理,则需要采用曲线拟合:
式中:Rk是k次序号参变量样条的模拟曲线矢量;ri为曲线控制节点的矢量;η为序号参变量;i为曲线节点序号;n为曲线节点数;Ωk是k次样条基函数:
k次样条基函数不仅可以呈现出k阶连续导数的光滑性,以任何精度通过曲线的节点,还具有保尖性。从式(1)中的参变量η的取值进行分析,在对其取值范围进行计算的过程中,可以将封闭曲线的节点数自然的顺延一个,也就是在n-1 时,初始节点则设置为n个节点,即节点0与节点n同点,有相同的几个特性,如图1所示。
从图1 中的信息可以得出,边界点的延拓可以分为两种形式:一种是开式曲线,一种是封闭曲线。为了获得曲线节点的样条曲线,需要对控制节点进行逐次的逼近磨光。通过相应的处理,最终可得出下式:
式中:i = 0,1,2,⋯,n。
从以上分析可以知道,ri是可以满足逼近要求的控制节点。
2 计算机技术辅助下的图形图像数字矢量化
在工程图形图像的设计中,其图形图像具有复杂性,所以单独使用矢量化处理还存在着一定的不足。为了保证数字矢量化图形图像的处理更加的清晰、准确,保证矢量化的过程中各项工作的顺利进行,需要结合计算机技术,共同完成图形图像的数字矢量化处理[5]。
使用计算机技术辅助数字矢量化处理,在原始的图形图像曲线上,选择合适的节点,使用鼠标进行选取,在完成原图的曲线拟合后,实施数字化曲线的绘制,通过对原始曲线和所绘制的曲线的吻合程度,判断其是否满足需求,或者是否需要重新进行采集。如果对数值的拟合和逼近有一定的认识和了解,可以通过一次采集、二次采集,达到满意的效果,但是如果对于数值的拟合和逼近不够了解,则需要反复的操作,才可以达到满意的效果。
使用计算机的鼠标,选择的曲线的节点(xp,yp),在曲线上的位置,可以表现为以下情况:
(1)g(xp-1+k,yp-1+k)=max[g(xp-1+i,yp-1+j)];其中0≤i≤2,0≤j≤2。
(2)在k≠1 时,可以得出
为了保证曲线上最小节点数,以及其位置的合理性,在计算机显示器上使用鼠标,选择第一个节点,并以直线显示鼠标的指针,到择取点间的直线;在选择第二个节点后,则以开式的2 次序号参变量样条曲线函数对择取点间的曲线段进行描述,同理对以下的节点参变量的样条曲线函数进行描述。数字矢量化处理的步骤为:
(1)按照上述公式,对相邻和其前面的选择节点进行样条曲线拟合;
(2)拟合后的样条曲线使用笔绘出,并对其节点矢量进行控制和标记;
(3)使用计算机的鼠标,移动到新的位置,使用相反颜色的笔进行重新的标记曲线绘制,将上次绘制的曲线擦除;
(4)对随着鼠标的指针移动而发生变化的拟合曲线,与原图像的曲线吻合情况进行观察,吻合则按下鼠标,进行曲线节点的选择,由于样条曲线为局部逼近曲线,沿着整条曲线依次选择变化部分的节点,形成节点之间的曲线;
(5)在整个曲线节点选择完后,点击鼠标右键,将节点选择时绘制的曲线擦除,并进行重新的曲线形态绘制,之后进行样条曲线的拟合,并进行绘制。
在图形图像的信息处理中,采用数字矢量化的方法,对参变量进行逼近磨光处理,使得样条曲线的节点可以以较大的间距进行曲线的拟合,又可以通过实时计算机动态鼠标演示,保证了选择的节点绘制的曲线。使用数字矢量化进行图形图像的处理,其数字化程度高,信息的处理速度非常快,且实际的操作非常简单[6]。本文针对高级光栅图形矢量化软件系统(R2V)与数字矢量化处理的结果进行分析,结果如图2 所示。
R2V处理的误差频率分布如图3 所示,其中1 个像素点的误差曲线点数>50%,2 个像素点的误差曲线点数>20%,由此得出R2V矢量化处理方法的误差较大。
3 结语
从本次的研究结果可以得出,在对图形图像进行矢量化处理的过程中,通过样条曲线拟合和计算机技术辅助完成图形图像的数字矢量化处理,可以提高图形图像数字化的清晰度、精确度,提高处理速度等,有显著的应用优势。为此可以将其应用在今后的工程设计中,针对图形图像的处理,采用数字矢量化处理,并结合计算机技术等提高其处理效果。
参考文献
[1]张旗,卢朝阳.图形矢量化中直线拟合与合并算法[J].现代电子技术,2002,25(3):19-21.
[2]朱婧.图像矢量化方法研究[D].杭州:杭州电子科技大学,2011.
[3]任洪丽.光栅图像矢量化技术探析[J].品牌月刊,2015(2):171.
[4]肖荣健,邹强.CASS软件支持下的数字影像图矢量化的应用[J].湖北农业科学,2009,48(8):1996-1997.
[5]赵锟.基于多级对象的图像矢量化研究[D].上海:上海大学,2011.
样条曲线拟合 篇3
本文主要是利用三次样条平滑的方法, 基于R统计软件对数据进行拟合及预测, 并根据结果给出对该种方法的评价。在具体的拟合及预测过程中, 我们发现参数的选择对结果会产生一定的影响, 比如随机干扰项e的标准差sd, 数据量n的大小, 结点数knots的多少等。另外, 对于来自不同函数的数据的拟合及预测效果也不尽相同。针对这些不同情形, 我们做了全面细致的对比分析, 找出了影响效果的重要因素, 并以图表的形式一一呈现。
2 理论及模拟方法
关于数据拟合的方法多种多样, 三次样条平滑是其中最重要和常见的一种。其原理是通过构造一系列三次样条函数来对实际数据进行拟合。三次样条函数定义为:设有一组结点, 且在每个小区间上都是三次多项式, 则称fi (t) 是结点上的三次样条函数。
记为基函数, C为样条系数矩阵, 则F=C×T。设为实际数据。利用加权最小二乘法便可以求出样条参数的估计, 即最小化目标函数, 其中W为权重。可以解得。由此可得。。
关于数据拟合的方法多种多样, 三次样条平滑是其中最重要和常见的一种。其原理是通过构造一系列三次样条函数来对实际数据进行拟合。三次样条函数定义为:设有一组结点, 且在每个小区间上都是三次多项式, 则称是结点上的三次样条函数。
记为基函数, C为样条系数矩阵, 则F=C×T。设为实际数据。利用加权最小二乘法便可以求出样条参数的估计, 即最小化目标函数, 其中W为权重。可以解得。由此可得。。
假设数据量保持不变, n=50, 我们分别选取knots=5, knots=6, knots=10, knots=30, 这四种情形。可以看出, 只有当knots=5的时候, 效果不是很好, 其他情况的拟合都非常令人满意。当然, 预测的效果只在短期内近似有效。所以, 当数据量比较适中的时候, 选择knots的数量稍大即可, 但是不能太小。
3.2 随机干扰项e的标准差对拟合及预测效果的影响
基于前面的分析, 我们假设数据量和结点数均保持不变, n=50, knots=50。并且, 仍然是利用函数y=3*sin (0.8*t) +e, 并且e服从均值为0的正态分布, 但是改变e的标准差, 观察当sd=0.1, sd=1, sd=3, sd=5的情形。发现标准差sd越小, 拟合及预测的效果越好, 反之, 标准差sd越大, 拟合及预测的效果越差。尤其是当sd=0.1的时候, 拟合效果相当好, 而sd=5的时候, 拟合的图形变为一条直线, 已经没有了实际意义, 完全不能反映出原始函数的周期性。
3.3 不同函数对拟合及预测效果的影响
数据来自于不同的函数, 对于拟合及预测效果也是有影响的。我们分别采用了指数函数和多项式函数重新对前面的方法进行模拟运算, 并且假定数据量n=50, 结点数knots=50。从模拟运行的结果可以看出, 该方法对于这两类函数的拟合及预测效果都是比较令人满意的。
4 发现
经过反复的模拟测试, 我们发现总的来说, 用三次样条平滑方法对数据进行拟合及预测的效果还是不错的, 在多数时候结果具有较强的可信度。特别是结合统计软件R的使用, 实现起来是相当容易的。不过具体说来, 各种参数如数据量的大小, 结点数的多少, 随机干扰项e的标准差等对运行结果都有一定的影响, 归纳如下:
对于正弦函数等周期函数, 可以达到很好的拟合效果, 但是预测效果较差;
数据量越大, 效果越好;
当数据量较小时, 结点数哪怕取最大, 拟合效果也不好。而当数据量很大时, 结点数太少也会影响效果。所以, 对于结点数而言, 只要不是很少 (对于我们这里涉及的情形一般大于或等于6) , 对结果的影响都不大;
标准差越小, 拟合及预测的效果就会越好, 反之, 如果标准差较大, 函数的信息几乎都被掩盖了, 这个时候所做的拟合及预测本身都已经没有了意义;
对于指数函数以及多项式函数等, 拟合效果较好, 预测的效果也可以达到很好的水平。
摘要:在证券投资分析中, 常常需要对证券价格、成交量等时间序列数据进行拟合及预测, 本文给出了基于R统计软件平台, 利用三次样条平滑得到的数据拟合及预测的原理、方法和应用举例。R统计软件的功能强大, 使用简便, 是进行证券数据分析的重要工具之一。
关键词:R统计软件,三次样条平滑,证券投资,数据拟合
参考文献
[1]何书元.应用时间序列分析[M].北京:北京大学出版社, 2009.
[2]贾俊平, 何晓群, 金勇进等.统计学[M].北京:中国人民大学出版社, 2000.
[3]郑思齐.住房需求的微观经济分析[M].北京:中国建筑工业出版社, 2007.
B样条曲线的绘制算法及其实现 篇4
1、B样条曲线定义
B样条曲线由分段曲线组成, 具有Bezier曲线的优点, 以克服了其不具备局部性质的缺点。p次B样条曲线的数学方程[1]为:
其中Pi为控制顶点, 曲线有n-k+1段;Ni, p (u) 称为B样条基函数, 由节点矢量确定.B样条基函数Ni, p (u) 由德布尔-考克斯递推公式计算[1]:
2、计算曲线上点的算法
已知节点向量给定参数u, p次B样条曲线的基函数可由式 (2) 递推得到。其matlab算法如下:
算法1
其中i表示参数u所在的区间[Ui%, Ui+1], u为所求参数, p为B样条曲线的次数, U为节点向量, 返回值N表示在区间[Ui, Ui+1]上, 参数u对应的p+1个基函数值。由算法1容易求得参数u所对应的B样条曲线上的点。
3、参数选取
从算法1可知, 只要给出参数, 就可以计算得到B曲线上对应的点。通常的绘制方法是用在参数上均匀取点, 计算得到对应的曲线上的点, 然后连线得到直线段来近似代替原曲线。这种方法得到的直线与原曲线的误差较大。本文提出参数选取的方法, 就是使得直线段与原曲线的误差限制在一定的误差值tol内。主要思想是:用节点插入方法[1]把B样条曲线分解成几段Bezier曲线Qi (u) 。计算每段Qi (u) 到其两端点连线Q0Qp的最大距离是比较耗时的.由Bezier曲线的凸包性可知:
max (d (Qi, Q0Qp) , i=1, …, p-1) 表示顶点到边Q0Qp最大的距离, 是容易计算的。因此, 当max (d (Qi, Q0Qp) , i=1, …p-1) ≤tol时, 参数的分割终止。否则, 在该参数区间中点插入节点, 直至满足误差小于tol的要求时终止。算法过程如下:
算法2
1.利用节点插入方法的B样条曲线分解成几段Bézier曲线.
2.对每段Bézier曲线B (Q0, …, Qp)
用曲线B (Q0, …, Qp) 初始化栈;
while栈非空 do
曲线B出栈;
if B控制顶点误差<tol then保存参数u;
else在参数的中点插入节点, 分成两段Bézier曲线;
把两段Bézier曲线再存入栈;
End
4、数值例子
例采用本文所述算法编程, 对平面3次B样条曲线在不同误差下绘制。控制顶点为 (-3.5, 0) , (-2.0, -47) , (0, 10.7) , (2.0, -4.7) , (3.5, 0) ;节点向量为 (0, 0, 00, 0.5, 1, 1, 1, 1) .图1为tol=0.1时, 得到对应折线段数为16.图2为tol=0.01时, 得到对应折线段数为46.从图1和2看出, 在曲线较平的地方, 折线分割较少;在曲线弯曲的地方, 折线较密集。表1列出了误差tol取不同值下的折线段数, 折线段数随着tol取值的减少而增加。
5、结论
本文实现了一种绘制B样条曲线的方法, 提出在指定误差限内绘制平面或三维空间中的B样条曲线。数值例子显示本文方法优于等分参数区间方法, 程序是高效、实用的。按照文中提供的方法可推广到有理B样条曲线绘制, 由于篇幅有限, 本文不再赘述。
摘要:B样条曲线是广泛流行的形状数学描述方法。本文对B样条曲线原理进行研究, 并给出算法终止条件。最后用matlab语言设计和实现了B样条曲线.数值例子显示本文程序是稳定和实用的。
关键词:B样条曲线,算法,Matlab
参考文献
[1]Piegl, Tiller.The NURBS book[M].2nd ed..New York:SpringerVerlag, 1997.
[2]孙家广.计算机图形学 (第三版) [M].清华大学出版社, 2003.
[3]施法中.计算机辅助几何设计与非均匀有理B样条[M].高等教育出版社, 2001.
[4]张玉连.Bezier曲线的一种快速绘制算法及其实现[J].燕山大学学报, 2000;24 (3) .
代数曲线的有理二次B样条逼近 篇5
曲线的参数和代数表示在几何造型中各有优缺点,CAGD中同时采用曲线的两种表示法,两种形式间的转换成为必须解决的课题。参数曲线的代数化[1]总是可以实现的,但大部分代数曲线都不能精确参数化,近似参数化问题由此产生。
相关研究工作已取得一些有价值的成果。如线性逼近方法[2];多边形逼近技术[3],可变的B样条曲线逼近方案[4],特殊情形的有理逼近手段[5],分段有理逼近途径[6],区间三次Bézier曲线逼近算法[7],分段有理二次曲线逼近理论[8]。
经过对比分析不难发现,有些逼近算法的计算复杂度较高,有些计算必须构造数值方法才能解决,如“肩点”等问题的计算。这里提出的有理二次B样条逼近算法侧重于曲线段“中点”的信息,规避了复杂的“肩点”计算问题。同时,逼近曲线保持了原始曲线的一些重要几何性质,如凹凸性,单调性和G1连续性;递归调用逼近算法,可以将误差控制在指定的范围之内。
1 代数曲线分段
1.1 曲线的凹凸和单调区间分段
已知代数曲线
假定根据凹凸性将区间[a0,an]分割为n段
[a0,an]=[a0,a1]∪[a1,a2]∪…∪[an-1,an] (2)
这里,ai∈[a0,an] i=1,2,…,n-1表示曲线拐点的横坐标。
在凹凸区间
[ai,ai+1] i=0,1,…,n-1 (3)
上,第i段曲线表示为:
设曲线段(4)在区间(3)上的极值点为ami,将区间(3)进一步分割(若已经单调,则不再分割)为如下形式:
[ai,ami]∪[ami,ai+1] i=0,1,…,n-1 (5)
则曲线段(4)表现为两段:
这样,所给代数曲线在每个分段区间上具有固定的凹凸性和单调性。
1.2 曲线段的三角形凸包假定分割后的某条代数曲线段为
A:F(x,y)=0 x∈[a,b] (7)
设它的两个端点为V0,V2,求出曲线段在两端点处切线,记为:
容易证明,切线T0,T2必相交于一点。
记交点为V1。这样,由三点V0,V1,V2形成了曲线段A的三角形凸包(如图1)。
例如,给定一条平面代数曲线段(如图2(a)):
C:x6+y6+3x4y2+3x2y4-x4-y4+2x2y2=0 (9)
它的右四分之一(如图2(b))分割为四段(如图3(a)),各段曲线的三角形凸包如图3(b)所示,其中A,B,C,D四点坐标依次为
2 曲线段的有理二次B样条逼近
2.1 有理二次B样条曲线
设控制顶点为:
Qi(xi,yi) i=0,1,2
权因子为:
wi(>0) i=0,1,2
则有理二次B样条曲线[4,5,6,7]P(u)u∈[0,1]可以表示为:
它的基本性质是:起始点P0=P(0)和终止点P1=P(1)分别位于Q0Q1,Q1Q2上,并和Q0Q1,Q1Q2相切。要确定与分段曲线A对应的B样条曲线段P(u),首先必须确定控制顶点和权因子。
根据Farin和Worsey提出的B样条曲线的参数化标准形式[8],当曲线首末两端的权因子为1时,曲线具有较好的参数化效果。这里取
w0=w2=1 (11)
2.2 控制多边形的确定
已知A的三角形凸包V0V1V2,设:
取控制顶点 Q1=V1 (12)
则
即有:
这样,控制顶点将借助于下文的权因子w1的确定而确定(如图4),曲线P(u)中的w1的自由变化对应代数曲线段A的逼近曲线族(如图5)。
2.3 “中点”到“中点”的最小距离逼近
这里,A上的“中点”是指SF(x(a+b)/2,y(a+b)/2);B样条曲线P(u)上的“中点”是指P(1/2),记作S1/2。“中点”到“中点”的最小距离逼近的条件:
即:
将(13)、(14)代入(16)可以得到关于w1的方程,求出w1,并由(12)、(13) 、(14)确定控制顶点为:
Qi(xi,yi) i=0,1,2
最后由(10)确定P(u)。
2.4 逼近曲线的性质
1) 保持原有曲线的凹凸性不变;
2) 保持原有曲线的单调性不变;
3) 在曲线的分段点处保持G1连续性[6];
4) 逼近曲线段的“中点”到原始曲线段的“中点”距离最小。
3 分段逼近算法
3.1 逼近误差
在几何学中,曲线段C和它的近似表示Ca之间的误差经常使用Hausdorff距离来描述
这种距离便于理论分析但不便于计算。
设A为代数曲线段,P(u)为逼近曲线段,下面给出一种易于计算的误差概念。
定义1 在参数域[0,1]上任意取一点
ui=i/n 0≤i≤n n∈N
记P(u)上的对应点为(x(ui),y(ui)),A上的对应点为
3.2 算法描述及其说明
输入代数曲线
1) 由(1)至(6)式对原始代数曲线进行分段(涉及拐点和极值点的计算);
2) 计算曲线段A两端切线T0,T2及其交点V1,确定三角形凸包V0V1V2;
3) 根据(13)、(14)、(16)式确定权因子w1;
4) 由(12)、(13)、(14)式确定Q0,Q1,Q2;
5) 依据(10)式计算逼近曲线P(u);
6) 若逼近误差e(A,P(u))<δ,则计算过程中止;否则,采用逐步二分分段区间的方法,递归调用上述分段逼近算法,直至满足给定的误差要求。
3.3 算法的收敛性
定理1 在上述算法的实施过程中,A和P(u)之间的Hausdorff距离收敛于0。即如果设二分k次后的Hausdorff距离为Ek(A,P(u)),则
证明:如图6,由代数曲线的分段方法及其凸包形成过程可知,△V0V1V2是确定的。设:
∠V1V0V2=α,∠V1V2V0=β 0<α,β≤π/2
记边V0V2的高为h,则:
h=V0V1sinα h=V2V1sinβ
记“中点”SF到边V0V2的距离为d。设经过SF的切线分别和V0V1、V2V1相交于P1,P2,自P1,P2分别向V0SF、V2SF引垂线,记P1H1=d11,P2H2=d12。
又设∠P1V0SF=α1,∠P2V2SF=β1 0<α1,β1<π/2。
显然E0(F,P(u))<d<h,经过在“中点”处一次分割后,
d11=P1V0sinα1=a1V1V0sinα1 0<a1<1
d12=P2V2sinβ1=b1V1V2sinβ1 0<b1<1
经过k次分割后,
dk1=a1a2…akV1V0sinαk 0<ai<1,i=1,2,…,k
dk2=b1b2…bkV1V2sinβk 0<bj<1,j=1,2,…,k
设
从而,
4 实验结果
逼近算法的求解(参见(15)或(16)式)不存在实质性的困难,算法容易实施。
图3中曲线C的右四分之一分段一步有理二次B样条曲线的逼近结果参见图7,图8为误差函数图形,一步逼近误差
5 结 论
代数曲线的有理二次B样条逼近算法计算简单,保持了原始曲线的一些重要几何性质,通过算法的递归调用,可以将逼近误差控制在指定的范围之内。
参考文献
[1] Sederberg T,Zheng J.Algebraic methods for computer aided geometric design.In:Farin G,Hoschek J,Kim M s.Handbook of Computer Aided Geometric Design.North-Holland,Amsterdam,2002.
[2] Ihm I,Naylor B.Piecewise linear approximations of digitized space curves with applications.In:Patrikalakis,N.Scientific Visualization of Physical Phenomena.Springer-Verlag,Berlin,1991:545-569.
[3]Farouki R.Hierarchical segmentations of algebraic curves and some ap-plications.In:Lyche T,Sshumaker LL.Math.Methods in Computer Ai-ded Geometric Design.Academic Press,Boston,MA,1989:239-248.
[4] Pottmann H,Leopoldseder S,Hofer M.Approximation with active B-spline curves and surfaces.In:Coquillart S,Shum H,Hu S M.Proc.of Pacific Graphics 2002.IEEE press,Los Alamitos,CA,2002:8-25.
[5] Sederberg T,Zhao J,Zundel A.Rational approximation of algebraic curves.In:Strasser W,Seidel H.Theory and Practice of Geometric Modeling.Springer-Verlag,Berlin,1989:33-54.
[6] Bajaj C,Xu G L.Piecewise rational approximations of real algebraic curves.J Computational,1997,15(1):55-71.
[7]Chen F,L.Interval parametrization of planar algebraic curves,In:Li ZM,Sit W.Proceeding of the 6th Asian Symposium on Computer Mathe-matics.World Scientific,Singapore,2003:64-76.
[8] Xiao Shan Gao,Ming Li.Rational quadratic approximation to real algebraic curves.Computer Aided Geometric Design,2004,21:805-828.
[9] Les Piegl ,Wayne Tiller,The NURBS Book [M].New York:Springer,1997.
C1插值二次B样条曲线曲面 篇6
参数曲线曲面是CAGD研究的主要内容[1,2,3],其中的Bézier方法、B样条方法,NURBS方法因其良好的光顺性、凸包性、形状可调性等,而受到人们的重视,并广泛应用于机械、汽车、航天等各个领域。
然而这几种方法在插值方面却有不足之处,Bézier方法的光滑拼接条件苛刻,B样条方法和NURBS方法不具有插值功能。传统的方法是反算控制顶点[3,4,5],这种方法需解大型线性方程,计算费用较大,且曲线的形状难以局部修改,不利于实际曲线曲面造型,并且修改一个数据点将影响整个曲线或曲面;或者是通过构造辅助点进行分段拼接[6,7];或者是用迭代法近似计算B样条的控制顶点[8,9]。
本文介绍一种具有保凸的均匀二次B样条和均匀三次B样条插值曲线。在给定的控制多边形的每2个顶点之间插人2个deBoor点,由这些deBoor点形成一个新的控制多边形,由此所产生的均匀B样条曲线插值于给定的控制多边形的所有顶点。进一步建立相邻四个插值点与新的控制顶点的关系,从而构造一组插值基函数,插值曲线由所构造的基函数和型值点直接表示,插值曲线具有保凸性和C1连续性。
1 均匀B样条曲线及其性质
给定n+1(n≥k)个空间点Vi(i=0,1,…,n),它对应的k次均匀B样条曲线可分段表示为[5]
式中Ei,k(u)是均匀k次B样条基函数,且有:
特别的当k=2时,相应的二次均匀B样条曲线的分段表示为
其中Ei,2(u)是均匀二次B样条曲线的基函数。
该二次均匀B样条曲线段具有如下端点性质
2 保形插值二次均匀B样条曲线
设有平面控制多边形
在首末端点处各取一个延伸点P0,Pn+1,且
记控制多边形
则:a0=(a1-a2)/4,a0×a1=a1×a2/4,可知由P0,P1,P2,P3构成的三边形是凸的,过P1,P2的插值曲线没有拐点,同理可证Pn-2,Pn-1,Pn,Pn+1构成的三边形也是凸的,从而可保证插值曲线在首尾不会出现多余的拐点。
待构造的保形均匀二次B样条插值曲线在给定的控制多边形的每个顶点Pi(i=1,2,…,n)处的切矢量为
式中0
对于相邻四点Pi-1,Pi,Pi+1,Pi+2,下面构造deBoor点V2i-1,
式中λi,λi+1>0是V2i-1,V2i,V2i+1,V2i+2的位置调整参数。将Ti中的ai=Pi+1-P i代入上式整理得到
由V2i-1,V2i,V2i+1,V2i+2,可生成插值于Pi,Pi+1的二次均匀B样条曲线Pi(t)
iP(t)(0≤t≤2)由两段曲线iP1(t)(0≤t≤1)和iP2(t)(1≤t≤2)组成。将上式整理得
将上式中Pi-1,Pi,Pi+1,Pi+2的系数函数分别记为
因而Pi(t)可表示为
易知
由此有Pi1(0)=Pi,Pi2(1)=Pi+1,即iP(t)由插值Pi,Pi+1。同理可知Pi(0)=Pi′1(0)=2λi Ti,P i(1)=Pi′2(1)=2λi+1 Ti+1
所以由Pi(t)(i=1,2,…,n)构成的曲线P(t)插值Pi(i=1,2,…,n),且是C1连续的。接下来确定iλ的范围,使得插值二次B样条曲线是P(t)保形的。当ai-1×ai和ai×ai+1有相同的方向,则Pi-1,Pi,Pi+1,Pi+2构成的三边形是凸的。易知过Pi以Pi点处的切矢Ti为方向的切线与过Pi+1以Pi+1点处的切矢Ti+1为方向的切线相交,其交点记为
当ai-1×ai和ai×ai+1方向相反时,则Pi-1,Pi,Pi+1,Pi+2构成的三边形有一条拐向边,这时记
取
则可保证V2i-1,V2i,V2i+1,V2i+2构成的三边形与Pi-1,Pi,Pi+1,Pi+2构成的三边形有相同的凸性(即要么是凸的,要么有唯一的拐点)。由B样条曲线的变差减少性质可知:当三边形
由Ti式可知,ti将影响插值曲线在Pi点的切矢方向Ti。而由(8)式可知,调整λi将矢插值二次B样条的控制顶点V2i-1,V2i在过Pi点的切线上移动,因而可以在不调整插值点的情况下间接调整插值曲线,这给插值曲线的生成和修改带来更多的灵活性。对同一组型值点,当λ2由0.2调整为0.3时,插值曲线的变化如图1。
3 C1插值二次均匀B样条曲面
由上节构造的插值二次均匀B样条曲线,按张量积扩张到插值二次均匀B样条曲面。给定空间点阵Pi,j(i=1,2,(43),m,j=1,2,(43),n)和两个参数方向的形状控制参数(αiu,αjv)(i=1,2,(43),m,j=1,2,(43),n)。接下来构造插值于Pi,j的二次均匀B样条曲面S(u,v),它是由曲面片Si,j(u,v)是C1连接而成的,且
即
由B样条曲面得性质可知:由(10)式定义的插值二次均匀B样条曲面是C1连续的。
4 数值实例
实例是在Visual C++.NET环境下实现的。由保形二次均匀B样条插值曲线算法生成的的插值曲线如图2所示。
由(10)式生成的插值二次均匀B样条曲面如图3所示。
摘要:利用二次均匀B样条曲线的端点性质,导出了构造插值二次均匀B样条曲线曲面的一种新的基函数―BB基函数。由BB基函数构造了C1保形插值二次均匀B样条曲线,构造了C1双二次均匀B样条插值曲面。
关键词:二次均匀B样条,BB基函数,曲线曲面,插值,保形
参考文献
[1]Bohemtal W,A survey of curve and surface methods in CAGD[J].CAGD,1984,(1):1-60
[2]Tgoodman T N,Ong B H.Shape preserving interpolation by space curve[J].CAGD,1997,15:1-17
[3]施法中.计算机辅助几何设计与非均匀有理B样条[M].北京:高等教育出版社,2001
[4]王天军.一个反求Bézier曲线控制点的算法[J].计算机辅助设计与图形学学报,1992,4(3):36-40
[5]方逵.曲线曲面的设计技术与显示原理[M].长沙:国防科技出版社,1997
[6]邓四清.C1插值三次样条曲线曲面[J].计算机工程与应用,2010,Vol.46,No.34:158-160
[7]方逵,赵军,谭建荣.带有给定切线多边形的保形有理三次B样条曲线[J].工程图学学报,1996,No.2:99-105
[8]Yamagushi,F.A new curve fitting method using a CRT computer display[J].Graphics and Processing,1978,7:425437
[9]阑宏伟,王国瑾,董辰世.用迭代非均匀B-Spline曲线(曲面)拟合给定点集[J].中国科学,2003,Vol.33No.10
[10]方逵,欧新良.计算机辅助几何设计中的凸性分析理论及算法[M].长沙:湖南科技出版社,2011
空间有理三次B样条曲线的参数化 篇7
曲线, 曲面的参数变换技术在计算机辅助几何设计 (CAGD) 中, 有非常重要的作用, 其中不改变参数曲线形状的是正则参数变换, 它只会改变曲线上的点与参数值的映射关系。本文在不改变控制点的条件下, 研究了有理三次样条曲线中, 权因子变化和曲线参数化的关系, 得出了一个相对来说比较简单的权因子计算公式, 它充分体现了权因子的几何含义, 另外, 它更易于计算机的实现。
2 空间有理三次B样条曲线的参数化
定义1:给出四个控制顶点, 对应的权因子为:w0, w1, w2, w3。其中:w1≥1, i= (0, 1, 2, 3) 。定义了一条空间有理三次B样条曲线如下:
其中:是B样条的基函数, 曲线上的点与参数t∈[0, 1]有了一一对应关系。
定义2:在不改变曲线形状的前提下, 对曲线上的点与参数域内的点的对应关系进行改变, 叫做曲线的重新参数化。
其中, 点的重心坐标表示为:
其中, ai为的重心坐标, 且。
联立 (2) , (3) 两式, 比较的系数, 得到:
综上整理得:
由 (5) 式可以看出, 曲线上的点的参数t, 可由该点的重心坐标和控制顶点的权因子来表示。
3 不改变空间有理三次B样条曲线形状的充要条件
定理:设是三维欧式空间R3中的一组点, 其中是两组正实数。于是在R3中存在两条有理三次B样条曲线如下:
表示同一条曲线的的充要条件是:
证明: (1) 充分性的证明:由 (6) 式整理可以得到:
其中, 假设上面 (7) 式的比值为k。则有:
对曲线作变换, 得到
因此, 充分性得以证明。
(2) 必要性的证明:在u=0和u=1两端点的曲率分别为:
在v=0和v=1两端点的曲率分别为:
因此, 必要性得以证明。
4 权因子改变与参数化之间的关系
空间有理三次B样条曲线上有一点
其对应的参数为, 现将通过权因子wi (i=0, 1, 2, 3) 为wi- (i=0, 1, 2, 3) , 使得对应的参数变为, 并且不改变曲线的形状。
由 (5) 式得:
由新参数及任意给定W0- (或W3-) , 可以确定另一个W3- (或W0-) 。
利用定理
决定的新权因子W1-, W2-为:
因此, 可以由 (8) , (9) 三个式子就能计算出新的权因子, 因而可以对空间有理三次B样条曲线进行重新参数化。由以上计算公式可以很方便地算出新权因子wi- (i=0, 1, 2, 3) 。曲线的重新参数化容就很容易实现了。
5 结论
根据权因子的改变和曲线参数的关系, 得到一个权因子定量计算公式, 它能够更方便的对空间有理B样条曲线来进行参数调整。在调整某段曲线的参数时, 并不影响到其它段曲线的参数。除此之外, 它更便于计算机造型中对曲线来进行调整。另外, 由于方法相对来说比较简单, 所以它更易于计算机的实现。
摘要:本文主要来研究在保持曲线形状不变的前提下, 通过改变空间有理三次B样条曲线的权因子, 来使得曲线重新参数化, 进而达到与正则参数变换相同的效果。
关键词:控制点,有理三次B样条曲线权因子,参数化,重心坐标
参考文献
[1]施法中.计算机辅助几何设计与非均匀有理B样条[M].北京:北京航空航天大学出版社, 1994.h.
[2]韩西安, 蒋大为, 黄希利.空间有理三次B样条曲线参数化[J].航空计算技术, 1996 (2) .
[3]苏步青.关于三次参数样条曲线的一些标注记[M]。北京:高等教育出版社, 1995.
[4]许伟.有理B样条曲线中权因子的性质研究, 计算数学[J].浙江:浙江大学出版社, 1992.