二次Bézier曲线的双圆弧样条插值二分算法（清华大学软件学院计算机图形学与辅助设计研究所，北京100084）摘要：在数控加工领域，通常需要用尽量少段数的圆弧样条来对曲线进行拟合。采用二分查找算法，用G1连续的双圆弧样条对二次Bézier曲线进行拟合。该算法在给定误差范围内所需的圆弧段数较少。最后给出了具体的实例说明。关键词：数控加工；二次Bézier曲线；双圆弧样条；二分算法??中图法分类号：TP301.6文献标识码：A：10013695(2006)08016602BisectionAlgorithmsforApproximatingQuadratic??BézierCurvesbyG1BiarcSplines??LU激anbiao，YONGJunhai??(InstituteofComputerGraphicsCAD,SchoolofSoftware,TsinghuaUniversity,Bei激ng100084,China)Abstract:InCNC,itisoftenrequiredtoapproximateBéziercurvesbyG1arcsplineswithasfewarcsegmentsaspossible.AbisectionalgorithmforapproximatingaquadraticBéziercurvebyaG1Biarcsplineispresented.Thenewmethodreducesthenumberofthesegmentsintheresultantarcsplineunderthegivenerrortolerance.Somenumericalresultsaregiventoillustratetheefficiencyofthealgorithm.??Keywords:CNC;QuadraticBézierCurves;BiarcSplines;BisectionAlgorithms?お?在数控加工领域，将二次Bézier曲线拟合为圆弧样条是经常遇到的问题[1～5]，大多数情况下需要将曲线用直线段和圆弧样条进行逼近，而后进行加工。使用G1圆弧样条进行拟合有很多优点，如NC工具所走路径方面，G1圆弧样条可以显著减少CNC机器改变停走转换状态（StopandgoMotion），改善加工物体表面的品质；另一方面，很多实际的机械部件强制要求G1连续，以保证结果曲面的光滑。??当前研究中，用圆弧样条对曲线进行逼近，主要分为单圆弧样条和双圆弧样条两种方法。考虑到连接点处G1连续性的单圆弧样条算法，与双圆弧算法比较而言，其优点是可以减少所使用的圆弧段数。缺点是一旦初始顶点处的切线方向确定，整条圆弧样条就完全唯一地确定下来，从而缺乏灵活性；此外由于除初始确定切线方向的顶点，其他顶点处的切线方向因此也确定下来，因而对多个顶点处有切线方向要求的情况，一般都不适合采用；而且单圆弧样条稳定性不好,改动初始点或初始切向,整条曲线都要跟着变动；用单圆弧来插值闭曲线要经过特殊处理才能实现。而双圆弧样条方法则不存在这些缺点。给定两个端点以及端点处对应的切线方向，可以用双圆弧进行拟合。可用于拟合的双圆弧不唯一，双圆弧中两段圆弧公切点的轨迹是一个圆[2,3]。要唯一确定这段双圆弧，一般还需要附加一个约束条件。在以往研究中，人们给出了很多种约束条件。如选取使得沿双圆弧曲率平方的积分值最小的样条以保持曲率连续[6～8]；又如，D.J.Walton等人在文献[1]中给出了一种用双圆弧样条逼近二次Bézier曲线的方法，以当前被拟合的二次Bézier曲线控制多边形的内心作为单段双圆弧内两段圆弧的公切点，从而唯一地确定用于拟合当前曲线的单段双圆弧。其算法首先计算当前双圆弧与要拟合的二次Bézier曲线之间的误差，如果满足误差要求，则完成当前拟合；否则在插值误差最大处将该段二次Bézier曲线划分后分别进行上述拟合过程，直至完成。此外，人们也提出了一些最优化单段双圆弧拟合方法[2,5]。??本文中采用双圆弧样条进行插值，并使用文献[1]中确定双圆弧的方法。这种选取方式的优点主要包括：保持原曲线的凸凹性，这样确定的单段双圆弧位于其拟合的二次Bézier曲线的控制多边形内部，并且算法相对简单。另一方面，针对文献[1]拟合过程中对原曲线的划分方式给出新的算法，即采用二分查找算法，逐段确定用于拟合的双圆弧样条。从而使得结果所含圆弧数目更少。??1单段双圆弧的确定??本文中以当前被拟合的二次Bézier曲线控制多边形的内心作为单段双圆弧内的公切点，从而唯一地确定用于拟合当前曲线的单段双圆弧。如图1所示，B0,B1,B2为二次Bézier曲线Q(t)的三个控制顶点，I为△B0B1B2的内心，V，W点分别位于线段B0B1B2上，直线VW经过I点且与直线B0B2平行。由三角形内心的性质，可得‖B0V‖=‖VI‖,‖B2W‖=‖IW‖。??其中，符号‖•‖用来表示向量的长度...