一种基于切向估计的低误差B样条插值方法

2024-01-20胡家豪陈小雕

杭州电子科技大学学报(自然科学版) 2023年5期

胡家豪,陈小雕

(杭州电子科技大学计算机学院,浙江杭州 310018)

0 引言

曲线插值问题是计算机辅助几何设计和计算机图形学中的基本问题之一。大多数方法先计算样条曲线对应的节点,然后再求解对应的控制点信息。均匀节点法是一种简单的选择,其中节点等距分布。当连续数据点之间的距离变化很大时,统一参数化方法通常会导致结果不理想。弦长法[1-3]中使用的累积弦长是累积弧长的合理近似值。向心法[4]和Foley法[5]是弦长法的两种变体,更多的相关讨论可参见参考文献[6]。文献[7]利用能量优化方法来确定节点,Park讨论了闭合B样条曲线的节点选择[8]。文献[9]在节点向量与参数化相一致的情况下通过指定曲线段相对于所在弦的高度来确定节点值,能获得令人满意的结果,但相对高度的获取在工程上并不容易。文献[10]以插值点的切向作为约束,利用二次B样条曲线本身的几何性质进行参数化,使曲线在每个插值点上都满足指定的切向,可以直观地控制插值曲线的形状以达到预期效果。文献[11]指出,在插值误差方面,上述三种弦长类型方法都没有比其他方法具有明显优势。与通过求解全局方程获得二次精度的方法[12]不同,Zhang等人[12]还提出了一种局部计算方法,可以二次多项式形式再现参数曲线,并且具有二次精度。文献[13]通过优化曲线的弯曲和拉伸能量来确定曲线的自由度,使曲线的变化尽可能小来获得更好的曲线形状。文献[14]通过最小化三次多项式曲线的三次系数来确定自由度,并采用三次多项式曲线对四个相邻点进行插值。本文使用局部插值二次曲线估计二次B样条的节点,从而得到最终的二次B样条插值曲线。理论上,一旦从二次曲线中采样得到插值点,得到的插值曲线可以完全重构出原始的二次曲线,即本文方法也具有二次精度。数值算例表明,新方法可以获得比现有方法更小的插值误差。

1 一种基于切向估计的低误差B样条插值方法

1.1 插值4个平面点的二次Bézier曲线

(1)

式中,A=(x1y3-y1x3)(x1y3-x2y3-y1x3+y2x3),B=(x1y3-y1x3)(y1x2-x1y2),C=(x1y2-y1x2)(x1y2-y2x3-y1x2+x2y3),那么剩下的ta、ai和bi可以表示为

(2)

式中,i=0,1,2,3和j=0,1,2,“×”表示两个平面向量之间的叉积。

1.2 插值三个平面点和一个切向的二次Bézier曲线

P0=q0,P2=q2,P1=(α0s0,α0t0)

1.3 估计闭曲线情形下插值点的切向

(3)

(4)

认知灵活性指顺应改变的情境而转换到另一种思维或行为，以符合新情境的需要的能力反映思维和行为的适应能力。Ajilore等[24]研究发现，双相障碍Ⅰ型稳定期患者(n=22)认知灵活性与健康对照人群(n=20)比较差异无统计学意义。刘传朋[25]研究显示青少年双相抑郁患者无论是在急性期还是缓解期均存在认知灵活性等方面的缺陷。

α=1-tb,1β=tb,2-ta,2

(5)

α=tb,3-ta,3β=ta,4。

(6)

图1 切向估计的示例

1.4 估计开曲线情形下插值点的切向

两个切向量Tn-2和Tn-1可以用相同的方式估计。

1.5 构造二次B样条插值曲线

1.6 时间复杂度讨论

第一,给定n个插值点处的切向估计可以在线性时间内完成。首先,求解一条二次Bézier插值曲线的过程与输入的插值点数n无关,可在常数时间内完成。然后,计算一条Bézier曲线在一点处的切向,也可以在常数时间内完成。从而,在某插值点处的切向估计可以在常数时间0(1)内完成。因此,所有插值点的切向估计可在0(n)时间内完成。

第二,得到插值点处的切向后,利用unclamping技术[15]来转换为对应的B样条形式的过程可在线性时间内完成。对于二次B样条的unclamping,每增加一个点,对应的转换过程可在常数时间内完成[15]。因此,采用增量式的方式,一个点一个点地增加,完成所有插值点的转换过程,可以在0(n)时间内完成。

综上两点所述,求解插值二次B样条的整个过程可以在线性时间内完成。

2 实例分析

为了评估算法性能,使用参考文献[13]中的两个测试实例,并与文献[1-3]、文献[4]、文献[5]、文献[13]中的方法进行比较。

其中n=10,20,…,100。令Gn(t)为对应于n的二次B样条曲线。最大绝对误差表示给定曲线F(ξ)和插值曲线Gn(t)之间的单边Hausdorff距离,定义为

图2 椭圆和30个插值点

表1列出了不同方法的最大误差。表1中,对于n=10的情况,最好的结果3.6e-3来自向心法[4]。对于n=40的情况,最好的结果2.0e-5来自张的方法[13],与新方法2.1e-5的结果非常接近。新方法在其他情况下最大误差最小,明显优于其它方法。

表1 例1中,不同算法的最大绝对误差比较

例2如图3所示的8次Bézier曲线,其控制点为{(0,0),(19,24),(39,43),(58,37),(78,0),(98,50),(141,81),(164,64),(188,0)}。为了防止在端点q1和qn附近出现较大的误差,还给出了q1和qn处的切向。在前面的五种方法中,在两个端点处引入的方向切线约束会导致产生三次样条。在这种情况下,新方法中得到的曲线仍然是二次B样条曲线。插值误差如表2所示,当n=20时,新方法的结果为4.5e-3,与张方法[13]的最佳结果4.3e-3非常接近,也远优于三种弦长类型方法[1-3]。对于n≠20的情况,新方法的最大误差始终优于其他五种方法。可以预期,一旦在新方法中使用三次B样条代替二次B样条,相应的插值误差可以得到进一步改善。