An approximation of circular arcs by quartic Bézier curves

In this paper we propose an approximation method for circular arcs by quartic Bézier curves. Using an alternative error function, we give the closed form of the Hausdorff distance between the circular arc and the quartic Bézier curve. We also show that the approximation order is eight. By subdivision of circular arcs with equi-length, our method yields the curvature continuous spline approximation of the circular arc. We confirm that the approximation proposed in this paper has a smaller error than previous quartic Bézier approximations.     

Interpolating G Bézier surfaces over irregular curve networks for ship hull design

We propose a local method of constructing piecewise G¹ Bézier patches to span an irregular curve network, without modifying the given curves at odd- and 4-valent node points. Topologically irregular regions of the network are approximated by implicit surfaces, which are used to generate split curves, which subdivide the regions into triangular and/or rectangular sub-regions. The subdivided regions are then interpolated with Bézier patches. We analyze various singular cases of the G¹ condition that is to be met by the interpolation and propose a new G¹ continuity condition using linear and quartic scalar weight functions. Using this condition, a curve network can be interpolated without modification at 4-valent nodes with two collinear tangent vectors, even in the presence of singularities. We demonstrate our approach in a ship hull.     

C 1 NURBS representations of G 1 composite rational Bézier curves

This paper is concerned with the re-representation of a G ¹ composite rational Bézier curve. Although the rational Bézier curve segments that form the composite curve are G ¹ continuous at their joint points, their homogeneous representations may not be even C ⁰ continuous in the homogeneous space. In this paper, an algorithm is presented to convert the G ¹ composite rational Bézier curve into a NURBS curve whose nonrational homogeneous representation is C ¹ continuous in the homogeneous space. This re-representation process involves reparameterization using Möbius transformations, smoothing multiplication and parameter scaling transformations. While the previous methods may fail in some situations, the method proposed in this paper always works.     

参数曲面上的插值与混合

如何表示曲面上的曲线,在处理诸如数控加工中的路径设计以及CAD/CAM等领域频繁出现的曲面裁剪问题时显得日益重要.给出了数据点的切方向(切方向及曲率向量或测地曲率值)指定而G¹连续(G²连续)插值曲面上任意点列的方法.作为曲面上曲线插值问题的特例,还讨论了曲面上曲线的混合问题.基本思想是借助于微分几何的有关结论,曲面上曲线的插值问题被转化为其参数平面上类似的曲线插值问题.该方法能够用二维隐式方程来表示曲面上的插值曲线,从而把在显示该曲线时所面对的曲面求交的几何问题转化为计算隐式曲线的代数问题.实验证明该方法是可行的,而且适用于CAD/CAM及计算机图形学等领域.     

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.     

Finding the best conic approximation to the convolution curve of two compatible conics based on Hausdorff distance

We consider the convolution of two compatible conic segments. First, we find an exact parametric expression for the convolution curve, which is not rational in general, and then we find the conic approximation to the convolution curve with the minimum error. The error is expressed as a Hausdorff distance which measures the square of the maximal collinear normal distance between the approximation and the exact convolution curve. For this purpose, we identify the necessary and sufficient conditions for the conic approximation to have the minimum Haudorff distance from the convolution curve. Then we use an iterative process to generate a sequence of weights for the rational quadratic Bézier curves which we use to represent conic approximations. This sequence converges to the weight of the rational quadratic Bézier curve with the minimum Hausdorff distance, within a given tolerance. We verify our method with several examples.     

Constrained approximation of rational Bézier curves based on a matrix expression of its end points continuity condition

For high order interpolations at both end points of two rational Bézier curves, we introduce the concept of C^(v,u)-continuity and give a matrix expression of a necessary and sufficient condition for satisfying it. Then we propose three new algorithms, in a unified approach, for the degree reduction of Bézier curves, approximating rational Bézier curves by Bézier curves and the degree reduction of rational Bézier curves respectively; all are in L₂ norm and C^(v,u)-continuity is satisfied. The algorithms for the first and second problems can get the best approximation results, and for the third one, resorting to the steepest descent method in numerical optimization obtains a series of degree reduced curves iteratively with decreasing approximation errors. Compared to some well-known algorithms for the degree reduction of rational Bézier curves, such as the uniformizing weights algorithm, canceling the best linear common divisor algorithm and shifted Chebyshev polynomials algorithm, the new one presented here can give a better approximation error, do multiple degrees of reduction at a time and preserve high order interpolations at both end points.     

Adaptive patch-based mesh fitting for reverse engineering

In this paper,  we propose a novel adaptive mesh fitting algorithm that fits a triangular model with G¹ smoothly stitching bi-quintic Bézier patches. Our algorithm first segments the input mesh into a set of quadrilateral patches, whose boundaries form a quadrangle mesh. For each boundary of each quadrilateral patch, we construct a normal curve and a boundary-fitting curve, which fit the normal and position of its boundary vertices respectively. By interpolating the normal and boundary-fitting curves of each quadrilateral patch with a Bézier patch, an initial G¹ smoothly stitching Bézier patches is generated. We perform this patch-based fitting scheme in an adaptive fashion by recursively subdividing the underlying quadrilateral into four sub-patches. The experimental results show that our algorithm achieves precision-ensured Bézier patches with G¹ continuity and meets the requirements of reverse engineering.     

对可调控Bézier曲线的改进

目的 在用Bézier曲线表示复杂形状时,相邻曲线的控制顶点间必须满足一定的光滑性条件。一般情况下,对光滑度的要求越高,条件越复杂。通过改进文献中的“可调控Bézier曲线”,以构造具有多种优点的自动光滑分段组合曲线。方法 首先给出了两条位置连续的曲线G^l连续的一个充分条件,进而证明了“可调控Bézier曲线”在普通Bézier曲线的G^l光滑拼接条件下可达G^l(l为曲线中的参数)光滑拼接。然后对“可调控Bézier基”进行改进得到了一组新的基函数,利用该基函数按照Bézier曲线的定义方式构造了一种新曲线。分析了该曲线的光滑拼接条件,并根据该条件定义了一种分段组合曲线。结果 对于新曲线而言,只要前一条曲线的最后一条控制边与后一条曲线的第1条控制边重合,两条曲线便自动光滑连接,并且在连接点处的光滑度可以简单地通过改变参数的值来自由调整。由新曲线按照特殊方式构成的分段组合曲线具有类似于B样条曲线的自动光滑性和局部控制性。不同的是,组合曲线的各条曲线段可以由不同数量的控制顶点定义,选择合适的参数,可以使曲线在各个连接点处达到任何期望的光滑度。另外,改变一个控制顶点,至多只会影响两条曲线段的形状,改变一条曲线段中的参数,只会影响当前曲线段的形状,以及至多两个连接点处的光滑度。结论 本文给出了构造易于拼接的曲线的通用方法,极大简化了曲线的拼接条件。此基础上,提出的一种新的分段组合曲线定义方法,无需对控制顶点附加任何条件,所得曲线自动光滑,且其形状、光滑度可以或整体或局部地进行调整。本文方法具有一般性,为复杂曲线的设计创造了条件。     

Curvature continuous offset approximation based on circle approximation using quadratic Bézier biarcs

We present a method for G² end-point interpolation of offset curves using rational Bézier curves. The method is based on a G² end-point interpolation of circular arcs using quadratic Bézier biarcs. We also prove the invariance of the Hausdorff distance between two compatible curves under convolution. Using this result, we obtain the exact Hausdorff distance between an offset curve and its approximation by our method. We present the approximation algorithm and give numerical examples.     

3个控制顶点的类三次Bézier螺线

目的 为了使得过渡曲线的设计更为简单高效。提出基于3个控制顶点的类三次Bézier螺线。方法 通过对基函数的研究首先构造了3条在一定条件下曲率单调递减的类三次Bézier曲线,并由参数的对称性得另3条曲率单调递增的曲线。它们具有端点性、凸包性、几何不变性等三次Bézier曲线的基本性质,特点是只有3个控制顶点。接着严格地证明了此类曲线曲率单调的充分条件。 结果 有两条曲线比三次Bézier曲线的曲率单调条件范围大,且类三次Bézier螺线与三次Bézier螺线存在一定的位置关系。这6条曲线中有4条曲线的一个端点处曲率为零,可组合成4对类三次Bézier螺线来构造两圆弧间半径比例不受限制的S型和C型G²连续过渡曲线;剩下的两条曲线在两圆弧半径相差较大的情况下都可做不含曲率极值点的过渡曲线。最后用实例表明了此类曲线的有效性。结论 在过渡曲线设计中基于3个控制顶点的类三次Bézier螺线比三次Bézier螺线更为简单高效。     

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.     

G 2 interpolation and blending on surfaces

We introduce a method for curvature-continuous (G ²) interpolation of an arbitrary sequence of points on a surface (implicit or parametric) with prescribed tangent and geodesic curvature at every point. The method can also be used forG ² blending of curves on surfaces. The interpolation/blending curve is the intersection curve of the given surface with a functional spline (implicit) surface. For the construction of blending curves, we derive the necessary formulas for the curvature of the surfaces. The intermediate results areG ² interpolation/blending methods in IR².     

Automatic G arc spline interpolation for closed point set

A method for generating an interpolation closed G¹ arc spline on a given closed point set is presented. For the odd case, i.e. when the number of the given points is odd, this paper disproves the traditional opinion that there is only one closed G¹ arc spline interpolating the given points. In fact, the number of the resultant closed G¹ arc splines fulfilling the interpolation condition for the odd case is exactly two. We provide an evaluation method based on the arc length as well such that the choice between those two arc splines is made automatically. For the even case, i.e. when the number of the given points is even, the points are automatically moved based on weight functions such that the interpolation condition for generating closed G¹ arc splines is satisfied, and that the adjustment is small. And then, the G¹ arc spline is constructed such that the radii of the arcs in the spline are close to each other. Examples are given to illustrate the method.     

Constructing up to G 2 continuous curve on freeform surface

This paper presents new methods for G ¹ and G ² continuous interpolation of an arbitrary sequence of points on an implicit or parametric surface with prescribed tangent direction and both tangent direction and curvature vector, respectively, at every point. We design a G ¹ or G ² continuous curve in three-dimensional space, construct a so-called directrix vector field using the space curve and then project a special straight line segment onto the given surface along the directrix vector field. With the techniques in classical differential geometry, we derive a system of differential equations for the projection curve. The desired interpolation curve is just the projection curve, which can be obtained by numerically solving the initial-value problems for a system of first-order ordinary differential equations in the parametric domain associated to the surface representation for the parametric case or in three-dimensional space for the implicit case. Several shape parameters are introduced into the resulting curve, which can be used in subsequent interactive modification such that the shape of the resulting curve meets our demand. The presented method is independent of the geometry and parameterization of the base surface, and numerical experiments demonstrate that it is effective and potentially useful in patterns design on surface.     

Cubic Bézier approximation of a digitized curve

In this paper we present an efficient technique for piecewise cubic Bézier approximation of digitized curve. An adaptive breakpoint detection method divides a digital curve into a number of segments and each segment is approximated by a cubic Bézier curve so that the approximation error is minimized. Initial approximated Bézier control points for each of the segments are obtained by interpolation technique i.e. by the reverse recursion of De Castaljau's algorithm. Two methods, two-dimensional logarithmic search algorithm (TDLSA) and an evolutionary search algorithm (ESA), are introduced to find the best-fit Bézier control points from the approximate interpolated control points. ESA based refinement is proved to be better experimentally. Experimental results show that Bézier approximation of a digitized curve is much more accurate and uses less number of points compared to other approximation techniques.     

GC 1 multisided Bézier surfaces

This paper presents a new method for generating a tangent-plane continuous (GC¹) multisided surface with an arbitrary number of sides. The method generates piecewise biquintic tensor product Bézier patches which join each other with G¹-continuity and which interpolate the given vector-valued first order cross-derivative functions along the boundary curves. The problem of the twist-compatibility of the surface patches at the center points is solved through the construction of normal-curvature continuous starlines and by the way the twists of surface patches are generated. This avoids the inter-relationship among the starlines and the twists of surface patches at the center points. The generation of the center points and the starlines has many degrees of freedom which can be used to modify and improve the quality of the resulting surface patches. The method can be used in various geometric modeling applications such as filling n-sided holes, smoothing vertices of polyhedral solids, blending multiple surfaces, and modeling surface over irregular polyhedral line and curve meshes.     

Simple determination via complex arithmetic of geometric characteristics of Bézier conics

We show how to compute in a straightforward manner the geometric characteristics of a conic segment in rational Bézier form, by employing complex arithmetic. For a central conic, a simple quadratic equation defines the foci location, and its solution furnishes not only an explicit formula for the foci, but also for the center, axis direction and linear eccentricity.     

Analysis and avoidance of singularities for local G 1 surface interpolation of Bézier curve network with 4-valent nodes

We propose a local method of constructing piecewise G ¹ Bézier patches to span a Bézier curve network with odd- and 4-valent node points. We analyze all possible singular cases of the G ¹ condition that is to be met by the curve network interpolation and propose a new G ¹ continuity condition using linear and quartic scalar weight functions. Using this condition, a curve network can be interpolated without modification at 4-valent nodes with two collinear tangent vectors, even in the presence of singularities. We demonstrate our approach by generating G ¹ surfaces over the curve network which includes singularities at its node vertices and edges.     

Approximation by fat arcs and fat biarcs

A general discussion of the including approximation of a curve by a fat arc is given followed by an algorithm for constructing an including fat arc for a parametric Bézier curve. An example of applying the algorithm is given. The results for a fat arc are then used to develop an including approximation for a curve segment using a fat biarc. An algorithm for a fat biarc including approximation is provided followed by examples of Bézier curves being included by a fat biarc.