B样条曲线的光顺设计 - 浙江大学本科生毕业论文

毕业论文

样法和曲尺卡样法。

3.2.1回弹法

由公式（1）可知，当曲线的一阶导数绝对值较小时，其曲率可以近似为其二阶 导数。令Pi(xi,yi) ，i?1,...n 表示插值点，向量PiPi?1（i?2,...n?1 ）分别与向量 P0P1 构成拐角?i ，??max?i 称作这一系列点的最大拐角。当最大拐角不超过120 度时，三次函数样条的曲率与其二阶导数十分接近，可以互相替代。而三次函数样

条的二阶导数可以用追赶法得到，从而得到插值点处的二阶导数ci

，与ei??（i?1...n ）

ci ? 1 ?ci xi ? 1 ?xi

（i ? 2...n ）。

回弹法的过程如下： （1）初始化i?1，转（2）；

；否则转（5）； （2）如果eiei?1?0 ，转（3）（3）求得最小的?i

所得的值，转（4）；

，使eiei ? =0 成立，其中ei 为yi ??i 代入后的重新计算

1

（4）?? min(?,0.5?i)，?为预设的最大偏移量。更新 （5）如果i

； yi ?yi ???，转（5）

3.2.2直尺卡样法

直尺卡样法的目的是减少多余的拐点，其分为三种应对不同情况的过程。其过程一如下：

（1）初始化i?2，转（2）；

；否则转（5）； （2）如果ci-1ci??0且cici?1??0 ，转（3）（3）求得最小的?i

的值，转（4）；

，使ci ? 0 成立，其中ci 为yi ??i

代入后的重新计算所得

（4）?? min(?,?i)，?为预设的最大偏移量。更新 （5）如果i

； yi ?yi ???，转（5）

其过程二如下： （1）初始化i ? 2

，转（2）；

，转（3）；否则转（5）；

6

（2）如果ci-1ci?0、cici?1?0且ci?1ci?2?0

毕业论文

（3）求得最小的?i

得的值；求得最小的?i+1 算所得的值，转（4）；

（4）如果|?i|?|?i?1|

，使 ，使

成立，其中ci 为yi c? 0 ??i ci i +1 ? 0

代入后的重新计算所

代入后的重新计

成立，其中ci为yi+1??i+1

，则yi?yi??i ，否则yi ?1?yi?1??i?1；然后在使用过程

一中的方法，去除拐点；转（5）；

（5）如果i

其过程三的主要面对的情况是ci?1ci?0,cici?1?0,...,cici?k?1?0,cici?k?0， k>2，一般认为k<=5。首先，利用回弹法修改插值点使ei+1 ?0,...,ei ?k ? 2=0 。这 样，相当于将中间的插值点Pi?1,...,Pi?k?2 去除。

删除，于是可以用过程二的方法将拐点给

3.2.3曲尺卡样法

我们将直尺卡样法中的c 都用e 来替代，就是曲尺卡样法。即曲尺卡样法就是对曲率线的直尺卡样法，而曲尺卡样法一般只执行过程一和过程二。

其过程一如下：

（1）初始化i?2，转（2）；

；否则转（5）； （2）如果ei-1ei??0且eiei?1??0 ，转（3）（3）求得最小的?i

的值，转（4）；

，使ei ? 0 成立，其中ei为yi??i

代入后的重新计算所得 ； yi ?yi ???，转（5）

（4）?? min(?,?i)，?为预设的最大偏移量。更新 （5）如果i

（1）初始化i?2，转（2）；

；否则转（5）； （2）如果ei-1ei ?0、eiei ? 1 ?0且ei ?1ei ? 2 ? 0 ，转（3）（3）求得最小的?i

得的值；求得最小的?i+1 计算所得的值，转（4）；

（4）如果|?i|?|?i?1|

，则yi?yi??i

，否则yi ?1?yi?1??i?1；然后在使用过程

一中的方法，去除拐点；转（5）；

（5）如果i

，使 ei ? 0 成立，其中ei为yi??i 代入后的重新计算所

，使ei +1 ?0 成立，其中ei+1为yi+1??i+1 代入后的重新

7

毕业论文

3.2.4一般曲线的光顺设计算法

在实际生产过程中，我们遇到的曲线很多都不是函数型曲线。尽管三次函数样条还有二次导数平方的积分最小这样良好的性质，它面对最大拐角大于120度的插值点序列时，上述的光顺方法就显得也无能为力了。

因此，我们需要对插值点进行分段，逐段进行光顺，然后将结果拼接在一起。为了避免拼接后两段之间有明显的差异，处理的方法是相邻的两段间共用4到5个插值点。比如，1到10为一段，下一段为7到15，这样7、8、9、10四个点是共用的插值点。分段光顺后，被共用的点可能对应有有两个不同的新位置，这两个新位置的中间点的位置为该共用点的新位置，这个步骤称之为混合。

图4该线分成了两段（红与绿），黑色部分为共用点

其算法的主要过程如下：

（1）将Pi(xi,yi)分段，每相邻两段有4到5个共用点，且每一段满足该段的插值点列最大拐角不超过120 度；

（2）对于每一段，分别对其依次使用：回弹法、直尺卡样法、曲尺卡样法进行光顺。

（3）每一段得到的光顺后的结果，在共用点处进行混合。

图5 对图4 所示曲线的光顺结果的曲率线图，蓝色为原曲率线，红色为光顺后曲率线。左图为分段

后没有共用点所得的结果，右图为分段共用4 个点并混合后所得的结果，右图的拐点显然比左图少。

8

毕业论文

3.3 实验结果示例

图6 鞋印，左图是原曲线，右图是曲率线。红色为光顺后，蓝色为光顺前。

图7

图8

3.4算法的局限性

如3.2.4所述，对于一般曲线，这套方法需要先分段再混合。这样，在相邻两段

9