B-Spline(九):打断(Subdividing)以及折线化(Tesslelation)

Bezier曲线的打断方法类似,B样条的打断利用了de Boor算法。并且结合B样条的强凸包性,我们可以推算出一种有效的B样条折线化方法。因此,本节是对前面几节内容的一个综合应用,后面,我的分享也主要面向应用。

1)B样条的打断

给定参数u,希望在u处将b样条分为两部分。这个过程与Bezier曲线的打断非常相似。只不过,Bezier的打断是在所有的控制点上进行“切角”,而对于\(u\in[u_k,u_{k+1})\),仅\(P_{k-p},…,P_k\)p+1个控制点被切角(其实Bezier曲线也是p+1个控制点…)。下图以三阶B样条为例,展示打断过程:

我分别用Q,R,S代表三次“切角”。de Boor算法最后计算出的C(u)即\(S_k\)。绿色的点\(P_{k-3},Q_{k-2},R_{k-1},S_{k}\)为打断后左边的B样条的新控制点,\(S_{k},R_{k},Q_{k},P_{k}\)为打断后右侧的B样条的新控制点。

我的C++版本的打断实现如下:

下图是打断算法对某一样条在\(u=3000\)处打断的效果。为了方便展示,两段打断后的样条曲线都经过了移动。

2)B样条的折线化

B样条的折线化也是最常用的功能之一。比如曲线转换成折线,曲线渲染等等都需要将用一系列离散点代表B样条曲线。因此也可以把这个过程称之为曲线的细分(Tesselation)。一种简单的(naive)想法是均匀细分,即将节点区间均匀的划分为k份,然后对新节点分别求值,算出曲线上的点代替原曲线。如下图示:

这种划分比较简单,但是缺点也比较明显,即参数的步长不好确定。步长过大对于弯曲的曲线容易造成折线折角过大,步长过小会造成数据冗余。因此,我们需要一个自适应的方法。回想B样条的一个性质是“强凸包性”,说的是B样条曲线严格包含在控制点构成的凸包之内。因此,我们可以通过凸包的形状预测曲线的形状。当凸包形状逼近直线时,曲线的形状也逼近直线。自适应算法采用“分而治之”的思路,递归的将曲线分成两部分做细分运算:

  1. 给定节点首尾 \(u_{beg},u_{end}\),计算所有控制点到首、尾控制点的最高高度,如果最高高度小于阈值d,那么曲线足够直,计算终止,输出折线化结果。
  2. 如果不满足阈值,将曲线在 \(u_{mid}=(u_{beg}+u_{end})/2\)处打断,分成两部分,并且分别将两个部分执行步骤1。

我的算法的C++的实现是:

下图是对某条3阶B样条曲线进行torlerance =1 的折线化局部效果,可以看到:折线在弯曲的地方点比较密,而平直的地方点比较少,所以具备较好的自适应的特点。

3)折线化算法分析:

上述的算法与AutoCAD 样条曲线“转换为多段线”功能的对比:同样一段样条曲线,在AutoCAD中,AutoCAD的样条曲线“转换为多段线”功能转出的多段线相对来说更加均匀,可能没有考虑到“自适应”问题。如下图,我使用AutoCAD“转换为多段线”功能与我计算的多段线在近似效果相近的程度下进行比较(AutoCAD使用0-99的相对精度,我使用“弦高”的概念,二者无法直接对照。AutoCAD使用精度90,我使用容差1,目测二者差别接近),我的效果是254个点,AutoCAD是267个点。


本文参考: Dartmouth College 某个关于样条曲线的ppt给出了大体的思想,但是网页链接找不到了。

发表评论

电子邮件地址不会被公开。