B 样条曲线的等距算法及应用

朱朝艳， 陈小雕

（1. 浙江大学宁波理工学院，浙江 宁波 315100； 2. 杭州电子科技大学计算机学院，浙江 杭州 310018）

等距曲线、曲面的计算是几何计算的一个重要问题。它除了应用于传统的CNC 加工，还广泛应用于CAD 中的诸如图案设计等领域[1]。等距曲线、曲面的计算主要有两大类方法，一种是精确的方法，另一种是近似的方法。Farouki 等人讨论了可以用有理形式精确表示的曲线[2-5]。不幸的是，很多曲线的等距曲线是不能用有理形式精确表示的。在近似方法上，有很多文章讨论了平面曲线的等距曲线[6-7]。主要有两类方法，第一种是基于曲线逼近的方法[8,18]，这类方法中，或者用更加简单曲线，如直线段或圆弧等逼近原始曲线，并借助逼近曲线的等距曲线来近似原始曲线的等距曲线，同时用来去除等距曲线的自交，降低了求交计算的复杂度，但最终得到的等距曲线的段数较多；另一种则是基于自由曲线控制点的方法[1,9-15,19-20]，这种方法得到的段数相对较少，但往往有自交情况，去除自交的计算量将随着曲线的复杂化而变得很大。

保持等距曲线的正确的拓扑结构非常重要。在传统的CNC 加工中，等距曲线的正确拓扑结构对于刀具的路径设计有着决定性的作用。在图案设计等应用中，等距曲线的不正确的拓扑结构，可能导致最终得到的双侧等距曲线或者因缺失一段曲线不封闭，或者因多出一段曲线而出现悬边。图1 表示了单边等距曲线的示意图。图1(a)中，多出来一段，若继续作另一边的等距曲线，会导致出现悬边；图1(b)中，缺少一段，若继续作另一边的等距曲线，会导致双侧的等距曲线不封闭；图1(c)中的等距曲线具有正确的拓扑结构，对应的双侧等距曲线也是封闭的。

图 1 等距曲线拓扑结构的示意图

本文讨论B样条曲线的等距曲线的近似计算方法。首先，用双圆弧逼近的原始曲线的等距曲线，同时提出了基于单调圆序列的方法来计算等距曲线的近似自交点，并以此为初值迭代到精确的自交点。其次，根据前面计算的自交点作为等距曲线上的关键分段点并进行各个分段曲线的取舍。最后，应用文献[14-15]中的方法计算各个分段的等距曲线，同时保持段与段之间的拓扑关系，得到最终的等距曲线。本文方法得到的等距曲线可以保持正确的拓扑结构，最后得到的B样条表示的等距曲线具有较少的控制点。

1 求解B 样条曲线的等距曲线

一般的n 次B 样条曲线可以表示为

其中 )(tN 为曲线 )(tC 在参数t 处的单位法 向。一般地，n 次B 样条的等距曲线不再是n 次B 样条，甚至不能精确地表示为有理形式，人们 通常用近似的方法求解原始曲线 )(tC 的近似等 距曲线。在CNC 加工中，要求刀具在行进的过程中避免干涉，它所要求的结果等距曲线就是由式子(2)确定的等距曲线上，所有到原始曲线的最近距离恰好等于有向等距距离d 的绝对值的点的集合

其中 Dis ( Rd(t)，C)表示点 Rd(t)到曲线C 的最近距离。这种应用下，仅仅去除单侧自交点，可能会或增加或减少等距曲线段（见图1）。本文的算法专门针对式子(3)确定的应用，是对原先等距方法的补充。不失一般性，下面只考虑d＞0的情况，d＜0的情况可以同样处理。

1.1 样条曲线的自适应离散采样

在实际应用中，样条曲线的自适应离散采样，可以采用基于曲率的方法[1]。本文用双圆弧逼近的方法直接对相应的等距曲线进行自适应离散采样。实践表明，在给定的精度下，基于圆弧逼近的离散方法，得到的采样点数目往往要少于基于折线段逼近离散的方法。本文采用的双圆弧逼近的方法，主要参考了Yang[16]的算法。实践证明，双圆弧求交得到的近似交点，比用折线段求交得到的交点，更为接近原始曲线的精确交点；基于双圆弧离散的方法得到的等距曲线上的近似自交点比基于折线段离散的方法得到的相应的近似自交点具有更高的精度。

1.2 等距曲线的关键段点的定位与分段的取舍

由上文提及的等距曲线的概念容易得知，最后得到的去掉自交后的结果等距曲线是由若干段连续的曲线组成。为了方便起见，本文称各段 结果等距曲线段的端点为段点，并记χ 为结果等距曲线的所有段点的集合，+μ 为原始曲线的正向等距曲线，−μ 为原始曲线的负向等距曲线，+Ω 为+μ 的所有自交点的集合，−Ω 为所有+μ 与−μ 交点的集合，并记 Ω = Ω+∪Ω−。

定理1 ∈χ Ω 。

根据定理1，求出Ω 对应的分划A，并由此决定由A 确定的每一个小区间的取舍，最后得到的，就是结果等距曲线（段）对应在原始曲线的若干个参数小区间，并且这些小区间对应的等距曲线，不存在自交的现象，可以用已有的各种方法去求解。

首先讨论关键段点的定位，并由此得到Ω 对应的分划A。这个过程就是求解所有的交点集合Ω 。直接应用等距曲线之间求交，一般比较 费时间。利用逼近等距曲线后得到的双圆弧序列来估计交点，可以降低求交计算的复杂度与计算量，同时，得到交点比折线段方法更加接近精确的交点。

本文应用单调列技术消除圆弧序列的自交问题，并应用包围盒等技术来求解两列圆弧序列之间的交。首先，分别依次取所有控制点坐标的x 分量与y 分量，得到两个坐标序列，根据每列相邻坐标分量的差组成的数列的变号数，选择变号数小的，不妨设该坐标分量为x 分量。然后，对每段双圆弧增加点，使得每一段简单圆弧都是 关于该坐标分量单调。依次选择连续的多个圆弧组成的，关于x 分量单调的子序列，作为一个单调列，这样可以得到若干个单调列，并且每一个单调列内的圆弧，两两不相交。

确定分划A 之后，就需要确定小区间的取舍。小区间的准确取舍，对于最后等距曲线的拓扑结构是至关重要的。等距曲线上相邻两段单调列的交点，利用向量点积判断的方法，速度很快，可以用来去除局部环（如图2）。但是，该方法去除全局环，效率是不够的，容易发生误判。利用求解点到逼近折线段，或者点到逼近圆弧的距离，常因为段数的影响速度变得比较慢，而且由于逼近的误差，在临界状态下也容易发生误判，特别的，当所取的点不在精确等距曲线上的时候，误判几率更大。本文综合了上述这两种方法的优点进行了判断处理。首先，利用向量点积的判断方法，排除到原始曲线距离明显小于等距距离的小区间。在余下的区间，选取相邻两个交点所确定的小区间内的精确等距曲线上的点作为基准点，来求解点到原始曲线的距离，避免了逼近误差引发的临界问题。基准点的选取，可以分为两种情况，如果相邻的交点分别属于不同序号的双圆弧，则直接选取两个交点之间的双圆弧的端点作为基准点；否则，取两交点对应的参数的中间值对应在精确等距曲线上的点，作为基准点。然后，计算基准点到原始曲线的最近距离，如果距离在容差的范围内等于d，则保留，否则舍去该小区间。

图2 局部环与全局环处理结果

一般的，可以用双侧等距曲线的封闭性来帮助检验等距曲线的拓扑稳定性。图3 是一个样条曲线双侧等距的实例, 其中，3(a)是原始曲线，3(b)是AutoCAD 软件局部放大的结果，3(c)是OpenCAD 软件局部放大的结果。可以看出，本文的方法的结果，有更好的拓扑稳定性。当自交点的参数估计没收敛到精确自交点（实例中没出现这样的情况），图4 演示的本文的闭合处理方法也能保证最后得到的双侧等距曲线是闭合的。

图3 取舍的实例与比较

图4 闭合处理方法的比较

1.3 各个分段的等距曲线的最后处理

最后结果样条的处理上，可以直接用三次样条插值前面得到的采样点。这种方法的好处，结果曲线比较简单，在精度范围内也能保证插值后各段样条之间两两不相交，同时还能在全局交点处能保持连续，这种算法可以应用于图案设计。一般地，前面离散过程中得到的采样点数目可能比较大，有时候由于精度等原因，甚至还需要对采样点进行加密，相应的，最后结果样条的段数比较多，这是工程应用上的一大忌讳。直接用基于控制点调整的方法，对估计出来的小区间作等距曲线，段数相对来说少一些，但是不能保证插值后各段样条之间两两不相交，特别地，在全局交点处还可能不连续，这种情况的一个直接表现是继续作另外一侧的等距曲线，两侧等距曲线在原本应该闭合的情况下，不能闭合（见图4）。用求交的方法可以处理相交的情况，但是比较耗时间；Lee[8]针对参数小区间端点的参数值迭代求精的方法，在一定程度上可以改善，但是它依赖于迭代算法收敛的具体状况。

本文的处理方法，应用类似Yang[17]的基于控制点调整的逼近方法，对上面估计得到的参数小区间，直接求解等距曲线的逼近曲线。如图4所示，它预先指定了每一段逼近曲线的端点，就是上面求解得到的交点，这样，减少了段数，同时也避免了在全局交点处可能不连续的情况，可以同时应用于图案设计与CNC 等多种工程应用。

2 实例与结论

将本文的算法应用到商业软件OpenCAD中，并用 3 个实例与同类的国外著名软件AutoCAD2004, AutoCAD2005 就样条曲线的双侧等距功能作比较。为方便起见，分别将AutoCAD2004，AutoCAD2005 以及OpenCAD 分别得到的3 个结果简称为结果A2，A4与B。

例1 图5是针对闭合的，自交的曲线进行双侧等距的结果比较，结果A2, A4分别给出部分等距，B给出了所有的等距曲线段，在视觉上具有更好的美感。曲线为三次样条曲线，控制点与节点向量分别为：(456.2347,218.4149)(449.6793,295.0248) (577.9684,484.1168) (964.6972,235.6098) (479.0472,178.5197) (584.1964, 515.6817) (855.0988,486.1700) (996.1325,252.3531) (727.8244,37.1056) (666.6469,449.5623) (1117.0048,489.0262) (1047.2378,-13.7901) (646.8361,-10.8984) (462.4325,145.9829) (456.2347,218.4149)与 {0.0,0.0,0.0,0.0, 230.6695, 474.8459,725.8914, 924.3524,1158.021,1381.021,1572.056,1809.599, 2095.662,2406.339,2813.724,3031.814,3031.814, 3031.814,3031.814}。等距偏移量为20。

图5 闭合自交曲线双侧等距结果曲线比较

例2 图6是针对开的，自交的曲线进行双侧等距的结果比较，结果A2, A4均漏掉了一段等距曲线段，B给出所有了的等距曲线段。曲线为三次样条曲线，控制点与节点向量分别为：

(744.1808,508.8816) (776.7853,617.1998)

(833.3231,805.0285) (1078.0127,477.1051)

(648.0156,613.3402) (904.6993,768.0031)

(1050.8365,683.1869)(1053.8494,416.9693)

(692.1974,641.8598) (1057.0341,807.6433)

(1130.0377,608.4000) (1146.8524,404.0772)

(905.6308,403.5530) (881.9587,626.8380)

(1034.5717,575.1042) (1005.0188,465.7295)

(851.9888,419.3761) (794.0705,602.0181)

(925.0642,738.1799) (708.6746,770.5750)

(679.8814,704.0337) (674.9950,692.7413)与

{0.0,0.0,0.0,0.0,232.64907,403.42409,621.36462,

795.97228,929.19622,1091.2253,1307.7149,

1555.8348,1688.0376,1878.5677,2042.7598,

2179.7761,2274.3395,2341.8718,2459.9235,

2639.7297,2725.5404,2902.8505,2939.0912,

2939.0912,2939.0912,2939.0912}。等距距离为20。

图6 开自交曲线双侧等距结果曲线比较

例3 利用例2 中的数据，选取其中两段等距曲线段进行控制点数目比较，结果A2, A4得到两段等距曲线段的控制点数目分别为68 与74，结果B 得到的数目分别为14 与16（见图7）。

图7 两段等距曲线段控制点数目比较

本文讨论了B 样条曲线的等距算法，提出了基于双圆弧逼近和单调圆序列技术的自交消除算法，同时综合了基于控制点调整的曲线逼近等技术，并在此基础上提出了一种关于B 样条曲线的统一的、鲁棒的等距算法。本文的算法具有保持拓扑稳定，以及生成的等距曲线段数较少等特点。它已应用于商业软件OpenCAD 中，适用于处理自交，闭合等任意类型的样条曲线的等距，它还可以应用于图案设计等领域。实例也表明了本文的算法结果可以具有更精确的拓扑结构和较少的段数。

[1] Piegl L, Tiller W. Computing offsets of nurbs curves and surfaces [J]. Computer-Aided Design, 1999, 31： 147-156.

[2] Farouki R T, Neff C A. Analytic properties of plane offset curves [J]. Computer Aided Geometric Design, 1990, 7(1-4)： 83-99.

[3] Farouki R T, Neff C A. Algebraic properties of plane offset curves [J]. Computer Aided Geometric Design, 1990, 7(1-4)： 101-127.

[4] Farouki R T, Sederberg T W. Analysis of the offset to a parabola [J]. Computer Aided Geometric Design, 1995, 12(6)： 639-645.

[5] Pottmann H. Rational curves and surfaces with rational offsets [J]. Computer Aided Geometric Design, 1995, 12： 175-192.

[6] Pham B. Offset curves and surfaces： A brief survey [J]. Computer-Aided Design, 1992, 24(4)： 223-229.

[7] Maekawa T. An overview of offset curves and surfaces [J]. Computer-Aided Design, 1999, 31： 165-173.

[8] Lee I K, Kim M S, Elber G. Planar curve offset based on circle approximation [J]. Computer-Aided Design, 1996, 28(8)： 617-630.

[9] Hoschek J. Spline approximation of offset curves [J]. Computer Aided Geometric Design, 1988, 5(1)： 33-40.

[10] Meek D S, Walton D J. Offset curves of clothoidal splines [J]. Computer-Aided Design, 1990, 22(4)： 199-201.

[11] Sederberg T W, Buehler D B. Offsets of polynomial Bezier curves： Hermite approximation with error bounds [C]//Lyche T, Schumaker L L, editors. Mathematical Methods in Computer Aided Geometric Design, Volume II, Academic Press, 1992： 549-558.

[12] Coquillart S. Computing offsets of B-spline curves [J]. Computer-Aided Design, 1987, 19(6)： 305-309.

[13] Klass R. An offset spline approximation for plane cubic splines [J]. Computer-Aided Design, 1993, 25(5)： 297-299.

[14] Kumar R, Shastry K G, Prakash B G. Computing constant offsets of a NURBS B-Rep [J]. Computer-Aided Design, 2003, 35： 935-944.

[15] Tiller W, Hanson E G. Offsets of two-dimensional profiles [J]. IEEE Computer Graphics and Applications, 1984, 4(9)： 36-46.

[16] Yang X N. Efficient circular arc interpolation based on active tolerance control [J]. Computer-Aided Design, 2002, 34： 1037-1046.

[17] Yang H P, Wang W P, Sun J G. Control point adjustment for B-spline curve approximation [J]. Computer-Aided Design, 2004, 36(7)： 639-652.

[18] 汪国平, 孙家广. 平面NURBS 曲线及其Offset 的双圆弧逼近[J]. 软件学报, 2000, 11(10)： 1368-1374.

[19] 刘利刚, 王国瑾. 基于控制顶点偏移的等距曲线最优逼近[J]. 软件学报, 2002, 13(3)： 398-403.

[20] 汪国平, 陈玉健, 孙家广. 基于控制顶点扰动的平面Offset 曲线的NURBS 逼近[J]. 计算机学报, 1999, 22(12)： 59-66.