C2 interpolation of spatial data subject to arc-length constraints using Pythagorean–hodograph quintic splines

In order to reconstruct spatial curves from discrete electronic sensor data, two alternative C² Pythagorean–hodograph (PH) quintic spline formulations are proposed, interpolating given spatial data subject to prescribed constraints on the arc length of each spline segment. The first approach is concerned with the interpolation of a sequence of points, while the second addresses the interpolation of derivatives only (without spatial localization). The special structure of PH curves allows the arc-length conditions to be expressed as algebraic constraints on the curve coefficients. The C² PH quintic splines are thus defined through minimization of a quadratic function subject to quadratic constraints, and a close starting approximation to the desired solution is identified in order to facilitate efficient construction by iterative methods. The C² PH spline constructions are illustrated by several computed examples.     

Rational Pythagorean-hodograph space curves

A method for constructing rational Pythagorean-hodograph (PH) curves in R³ is proposed, based on prescribing a field of rational unit tangent vectors. This tangent field, together with its first derivative, defines the orientation of the curve osculating planes. Augmenting this orientation information with a rational support function, that specifies the distance of each osculating plane from the origin, then completely defines a one-parameter family of osculating planes, whose envelope is a developable ruled surface. The rational PH space curve is identified as the edge of regression (or cuspidal edge) of this developable surface. Such curves have rational parametric speed, and also rational adapted frames that satisfy the same conditions as polynomial PH curves in order to be rotation-minimizing with respect to the tangent. The key properties of such rational PH space curves are derived and illustrated by examples, and simple algorithms for their practical construction by geometric Hermite interpolation are also proposed.     

Dual representation of spatial rational Pythagorean-hodograph curves

In this paper, the dual representation of spatial parametric curves and its properties are studied. In particular, rational curves have a polynomial dual representation, which turns out to be both theoretically and computationally appropriate to tackle the main goal of the paper: spatial rational Pythagorean-hodograph curves (PH curves). The dual representation of a rational PH curve is generated here by a quaternion polynomial which defines the Euler–Rodrigues frame of a curve. Conditions which imply low degree dual form representation are considered in detail. In particular, a linear quaternion polynomial leads to cubic or reparameterized cubic polynomial PH curves. A quadratic quaternion polynomial generates a wider class of rational PH curves, and perhaps the most useful is the ten-parameter family of cubic rational PH curves, determined here in the closed form.     

平面插值三次PH样条的构造

讨论平面上三次PH曲线Hermite插值问题.当通过插入满足条件的中间数据来构造段数最少的C1插值PH样条曲线时,对于固定的弦长,如果所给的切矢模长太大或夹角太小,符合C1插值条件的解可能不存在,结合优化手段,给出了适当调整模长的大小,来求得符合G1插值条件的解的方法.拓宽了PH曲线在机器人路径的设计、数控加工的计算等方面的应用范围.     

三点插值的三次PH曲线构造方法

为推广三次PH曲线的实际应用,研究在给定3个平面型值点条件下的三次PH曲线构造方法.三次PH曲线具有鲜明的几何性质和代数特征,采用平面参数曲线的复数表示方法,三次PH曲线的充分必要条件被表述为复代数系统.通过对给定型值点进行参数化,将复代数系统转化为一元二次复方程,求解方程即得三次PH曲线的控制顶点,从而得到2条构造曲线.应用该方法对模拟给定的若干平面型值点数据进行实验,比较了均匀参数化、弦长参数化、弧长参数化方法的不同效果,并计算弧长、弯曲能量、绝对旋转数来选取最优构造曲线.实验结果表明,该方法有效且易于计算,可应用于三次PH样条构造.     

Theoretically-based algorithms for robustly tracking intersection curves of deforming surfaces

This paper applies singularity theory of mappings of surfaces to 3-space and the generic transitions occurring in their deformations to develop algorithms for continuously and robustly tracking the intersection curves of two deforming parametric spline surfaces, when the deformation is represented as a family of generalized offset surfaces. The set of intersection curves of two deforming surfaces over all time is formulated as an implicit 2-manifold I in an augmented (by time domain) parametric space R⁵. Hyperplanes corresponding to some fixed time instants may touchI at some isolated transition points, which delineate transition events, i.e. the topological changes to the intersection curves. These transition points are the 0-dimensional solution to a rational system of five constraints in five variables, and can be computed efficiently and robustly with a rational constraint solver using subdivision and hyper-tangent bounding cones. The actual transition events are computed by contouring the local osculating paraboloids. Away from any transition points, the intersection curves do not change topology and evolve according to a simple evolution vector field that is constructed in the Euclidean space in which the surfaces are embedded.     

Optimal Spline Approximation via ℓ0‐Minimization

Splines are part of the standard toolbox for the approximation of functions and curves in ?^d. Still, the problem of finding the spline that best approximates an input function or curve is ill‐posed, since in general this yields a “spline” with an infinite number of segments. The problem can be regularized by adding a penalty term for the number of spline segments. We show how this idea can be formulated as an ?₀‐regularized quadratic problem. This gives us a notion of optimal approximating splines that depend on one parameter, which weights the approximation error against the number of segments. We detail this concept for different types of splines including B‐splines and composite Bézier curves. Based on the latest development in the field of sparse approximation, we devise a solver for the resulting minimization problems and show applications to spline approximation of planar and space curves and to spline conversion of motion capture data.     

Combined evolution of level sets and B-spline curves for imaging

We propose the evolution of curves in direction of their unit normal using a combined implicit and explicit spline representation according to a given velocity field. In the implicit case we evolve a level set function for segmentation and geometry reconstruction in 2D images. The level set approach allows for topological changes of the evolving curves. The evolution of the explicit B-spline curve is driven by the Mumford–Shah functional. We are mainly concerned with the segmentation of images using active contours. To get satisfactory results from the implicit evolution the optimal stopping time and the correct level of the evolving function has to be estimated. We overcome this problem by using the combined evolution.     

High accuracy spline interpolation for 5-axis machining

This article presents a new algorithm for simultaneous 5-axis spline interpolation. The algorithm basically merges two concepts: (1) the interpolation of the toolpath with Pythagorean Hodograph (PH) curves and (2) the analytic solution of the inverse kinematic problem using the template equation method. The first method allows one to obtain a analytic relation between the arclength and the parameter of the toolpath curve. This one enables one to control the velocity of the tool on the workpiece. The second method allows one to determine the analytic solution of the parameterized inverse kinematic problem that permits us to introduce arbitrary number of geometric parameters. A natural selection of the possible parameters can be the parameters of tool geometry and the workpiece placement. This way, the off-line generated inverse solutions—that transform the cutter contact curve into axis values—can be online compensated, as soon as the exact parameter values are become known. Based on these two approaches, a robust and fast method for the simultaneous 5-axis spline interpolation is developed. The result of this new algorithm is time-dependent axis splines which represent the given toolpath with high accuracy.     

Efficient circular arc interpolation based on active tolerance control

In this paper, we present an efficient sub-optimal algorithm for fitting smooth planar parametric curves by G¹ arc splines. To fit a parametric curve by an arc spline within a prescribed tolerance, we first sample a set of points and tangents on the curve adaptively as well as with enough density, so that an interpolation biarc spline curve can be with any desired high accuracy. Then, we construct new biarc curves interpolating local triarc spirals explicitly based on the control of permitted tolerances. To reduce the segment number of fitting arc spline as much as possible, we replace the corresponding parts of the spline by the new biarc curves and compute active tolerances for new interpolation steps. By applying the local biarc curve interpolation procedure recursively and sequentially, the result circular arcs with no radius extreme are minimax-like approximation to the original curve while the arcs with radius extreme approximate the curve parts with curvature extreme well too, and we obtain a near optimal fitting arc spline in the end. Even more, the fitting arc spline has the same end points and end tangents with the original curve, and the arcs will be jointed smoothly if the original curve is composed of several smooth connected pieces. The algorithm is easy to be implemented and generally applicable to circular arc interpolation problem of all kinds of smooth parametric curves. The method can be used in wide fields such as geometric modeling, tool path generation for NC machining and robot path planning, etc. Several numerical examples are given to show the effectiveness and efficiency of the method.     

插值给定数据点的四次PH曲线构造

目的 PH （Pythagorean hodograph）曲线由于具备有理等距曲线、弧长可精确计算等优良的几何性质,广泛应用于数控加工和路径规划等方面。曲线插值是曲线构造的主要手段之一,虽然对PH曲线的Hermite插值方法进行了广泛研究,但插值给定数据点的构造方法仍有待突破,为推广四次PH曲线的应用范围,提出了一种新的四次PH曲线的3点插值问题解决方法。方法 从四次PH曲线的代数充分必要条件出发,在该曲线的Bézier控制多边形中引入辅助控制顶点,指出其中实参数的几何意义,该实参数可作为形状调节因子对构造曲线进行交互。对给定的3个平面型值点进行参数化确定相应的参数值;通过对四次PH曲线一阶导数积分得到曲线的显式表达,其中包含一个待定复常量,将给定的约束点代入曲线的显式表达式得到关于待定复常量的一元二次复方程,求解该复方程并反求Bézier控制顶点得到符合约束条件的四次PH曲线。结果 实验对通过构造插值给定数据点的四次PH曲线进行比较,当形状调节因此改变时,曲线形状可进行有效交互。每次交互得到两条四次PH曲线,通过弧长、弯曲能量、绝对旋转数的计算得到最优曲线,并构造得到PH曲线的等距线。结论 本文方法给定的形状调节参数具有明确的代数意义和几何意义,本文方法易于实现,可有效进行交互。     

形状可调的5次组合样条及其参数选择

目的 为了克服3次参数B样条在形状调整与局部性方面的不足,提出带参数的5次多项式组合样条。方法 首先构造一组带参数的5次多项式基函数;然后采用与3次B样条曲线相同的组合方式定义带参数的5次多项式组合样条曲线,并讨论基于能量优化法的5次组合样条曲线参数最佳取值问题;最后定义相应的组合样条曲面,并研究利用粒子群算法求解曲面的最佳参数取值。结果 5次组合样条不仅继承了3次B样条的诸多性质,而且还比3次B样条具有更强的局部性及形状可调性。由于5次组合样条仍为多项式模型,因此方程结构相对较为简单,符合实际工程的需要。利用能量优化法可获得光顺的5次组合样条曲线与曲面。结论 所提出5次多项式组合样条克服了3次参数B样条在形状调整与局部性方面的不足,是一种实用的自由曲线曲面造型方法。     

有理三次样条的误差分析及空间闭曲线插值

给出了具有线性分母的有理三次样条函数的误差估计,并在柱面坐标系下对一类空间闭曲线的插值问题进行了研究;通过将柱面展开,把空间闭曲线的插值问题转化为平面中的插值问题,利用具有线性分母的有理三次样条函数进行插值;最终得到的空间曲线能达到曲率连续.对该方法的误差进行了分析,数值例子显示插值效果较好.     

Local and singularity-free G 1 triangular spline surfaces using a minimum degree scheme

We develop a scheme for constructing G ¹ triangular spline surfaces of arbitrary topological type. To assure that the scheme is local and singularity-free, we analyze the selection of scalar weight functions and the construction of the boundary curve network in detail. With the further requirements of interpolating positions, normals, and surface curvatures, we show that the minimum degree of such a triangular spline surface is 6. And we present a method for constructing boundary curves network, which consists of cubic Bézier curves. To deal with certain singular cases, the base mesh must be locally subdivided and we proposed an adaptive subdivision strategy for it. An application of our G ¹ triangular spline surfaces to the approximation of implicit surfaces is described. The visual quality of this scheme is demonstrated by some examples.     

A class of general quartic spline curves with shape parameters

With a support on four consecutive subintervals, a class of general quartic splines are presented for a non-uniform knot vector. The splines have C² continuity at simple knots and include the cubic non-uniform B-spline as a special case. Based on the given splines, piecewise quartic spline curves with three local shape parameters are given. The given spline curves can be C²∩G³ continuous by fixing some values of the curve?s parameters. Without solving a linear system, the spline curves can also be used to interpolate sets of points with C² continuity. The effects of varying the three shape parameters on the shape of the quartic spline curves are determined and illustrated.     

基于C-B 样条的三角形和四边形曲面生成

文章给出了基于C-B 样条的由网格数据产生三角形和四边形曲面片的方 法,C-B 样条是由基底函数{sin t, cos t, t, 1}导出的一种新型样条曲线,它可以克服现在正在 使用的B 样条和有理B 样条为了满足数据网格的拓扑结构而增加多余的控制点,求导求积 分复杂繁琐,阶数过高,从而讨论其连续拼接时增加了困难等缺点,如何将它推广成曲面就 成为一个重要问题。作者利用边-顶点方法构造插值算子,再将这些算子进行凸性组合,将 C-B 样条曲线推广成三角形曲面片和四边形曲面片,它可以用于CAD 的逆向工程中散乱数 据的曲面重构。     

六次PH 曲线G2 Hermite 插值

以其在弧长计算与等距线表示上的优势,PH 曲线成为近年来计算机辅助几何设计 研究的焦点问题之一。为此讨论了六次PH 曲线的G2 Hermite 插值问题。在指定自由参数下,对 两类六次PH 曲线分别进行复分析曲线求解,得到满足G2 插值条件的六次PH 曲线和控制顶点。 通过弧长、能量积分、绝对旋转数的衡量,选取较好的插值曲线。进一步,讨论了用六次PH 曲 线G2 Hermite 插值逼近90°和67°圆弧的问题。在同一个自由参数下,选择插值最好的曲线,可 实现六次C1 Hermite 插值逼近圆弧的效果,且逼近90°圆弧时,优于五次G2 Hermite 插值逼近的 PH 曲线,而逼近67°圆弧时,与最好的五次PH 曲线达到的效果几乎相同。     

Hybrid curve fitting

We consider a parameterized family of closed planar curves and introduce an evolution process for identifying a member of the family that approximates a given unorganized point cloud {p _i } _{i =1,..., N} . The evolution is driven by the normal velocities at the closest (or foot) points (f _i ) to the data points, which are found by approximating the corresponding difference vectors p _i -f _i in the least-squares sense. In the particular case of parametrically defined curves, this process is shown to be equivalent to normal (or tangent) distance minimization, see [3], [19]. Moreover, it can be generalized to very general representations of curves. These include hybrid curves, which are a collection of parametrically and implicitly defined curve segments, pieced together with certain degrees of geometric continuity.     

Spline approximation of offset curves

This paper deals with the approximation of (regular) offset curves (of a given spline curve of degree n) by a spline curve of arbitrarily chosen degree m. The approximating spline curves are determined by geometric continuity conditions and by parameter optimization for minimizing the range of the approximation error.     

基于约束优化的B样条曲线形状修改

B样条曲线广泛应用于计算机辅助几何设计(CAGD),并且与Bézier曲线等其它著名曲线相比,在形状设计方面有其更独特的性质。对曲线的设计和形状的修改是一个重要的课题,也是计算机图形学、CAD/CAM和数控技术领域最重要的研究主题之一。论文运用约束优化的方法,修改均匀B-样条的控制点,使B样条曲线通过调整的控制点,使修改前后曲线的距离范数达到最小,并给出相应的实例说明算法的有效性。