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.     

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.     

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.     

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.     

Approximate convolution with pairs of cubic Bézier LN curves

In this paper we present an approximation method for the convolution of two planar curves using pairs of compatible cubic Bézier curves with linear normals (LN). We characterize the necessary and sufficient conditions for two compatible cubic Bézier LN curves with the same linear normal map to exist. Using this characterization, we obtain the cubic spline approximation of the convolution curve. As illustration, we apply our method to the approximation of a font where the letters are constructed as the Minkowski sum of two planar curves. We also present numerical results using our approximation method for offset curves and compare our method to previous results.     

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.     

Computation of the minimum distance between two Bézier curves/surfaces

We present an efficient and robust method based on the culling approach for computing the minimum distance between two Bézier curves or Bézier surfaces. Our contribution is a novel dynamic subdivision scheme that enables our method to converge faster than previous methods based on binary subdivision.     

利用距离与内能极小平滑链接Bézier曲线

目的 对于满足低阶连续的链接Bézier曲线,提高曲线之间的连续性以达到平滑的目的,需要对曲线的控制顶点进行相应调整。因此,可根据具体的目标对需要调整的控制顶点进行优化选取,使得平滑后的链接曲线满足相应的要求。针对这一问题,给出了3种目标下优化调整控制顶点的方法。方法 首先对讨论的问题进行描述,分别指出链接Bézier曲线从C⁰连续平滑为C¹连续和从C¹连续平滑为C²连续两种情形需调整的控制顶点;然后分别给出两种情形下,以新旧控制顶点距离极小为目标、曲线内能极小为目标、新旧控制顶点距离与曲线内能同时极小为目标,对链接Bézier曲线进行平滑的方法,最后对3种极小化方法进行对比,并指出了不同方法的适用场合。结果 数值算例表明,距离极小化方法调整后的控制顶点偏离原控制顶点的距离相对较小,适合于控制顶点取自于实物时的应用场合;内能极小化方法获得的链接曲线内能相对较小,适合于要求曲线能量尽可能小的应用场合;距离与内能同时极小化方法兼顾了新旧控制顶点的距离和链接曲线的内能,适合于对两个目标都有要求的应用场合。结论 提出的方法为链接Bézier曲线的平滑提供了3种有效手段,且易于实现,对其他类型链接曲线的平滑具有参考价值。     

G1 continuous approximate curves on NURBS surfaces

Curves on surfaces play an important role in computer aided geometric design. In this paper, we present a parabola approximation method based on the cubic reparameterization of rational Bézier surfaces, which generates G¹ continuous approximate curves lying completely on the surfaces by using iso-parameter curves of the reparameterized surfaces. The Hausdorff distance between the approximate curve and the exact curve is controlled under the user-specified tolerance. Examples are given to show the performance of our algorithm.     

Curve fitting and fairing using conic splines

We present an efficient geometric algorithm for conic spline curve fitting and fairing through conic arc scaling. Given a set of planar points, we first construct a tangent continuous conic spline by interpolating the points with a quadratic Bézier spline curve or fitting the data with a smooth arc spline. The arc spline can be represented as a piecewise quadratic rational Bézier spline curve. For parts of the G¹ conic spline without an inflection, we can obtain a curvature continuous conic spline by adjusting the tangent direction at the joint point and scaling the weights for every two adjacent rational Bézier curves. The unwanted curvature extrema within conic segments or at some joint points can be removed efficiently by scaling the weights of the conic segments or moving the joint points along the normal direction of the curve at the point. In the end, a fair conic spline curve is obtained that is G² continuous at convex or concave parts and G¹ continuous at inflection points. The main advantages of the method lies in two aspects, one advantage is that we can construct a curvature continuous conic spline by a local algorithm, the other one is that the curvature plot of the conic spline can be controlled efficiently. The method can be used in the field where fair shape is desired by interpolating or approximating a given point set. Numerical examples from simulated and real data are presented to show the efficiency of the new method.     

An approximation approach of the clothoid curve defined in the interval [0, π/2] and its offset by free-form curves

We propose an algorithm to approximate the clothoid curve defined in the interval [0, π/2] and its offset curves with Bézier curves and the approximation errors converge to zero as the degree of the Bézier curves is increased. Secondly, we discuss how to approximate the clothoid curve by B-spline curves of low degrees. By employing our method, the clothoid curve and its offset can be efficiently incorporated into CAD/CAM systems, which are important for the development of 3D civil engineering CAD systems, especially for 3D highway road design systems. The proposed method has been implemented on AutoCAD R14.     

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

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

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.     

Progressive iterative approximation for triangular Bézier surfaces

Recently, for the sake of fitting scattered data points, an important method based on the PIA (progressive iterative approximation) property of the univariate NTP (normalized totally positive) bases has been effectively adopted. We extend this property to the bivariate Bernstein basis over a triangle domain for constructing triangular Bézier surfaces, and prove that this good property is satisfied with the triangular Bernstein basis in the case of uniform parameters. Due to the particular advantages of triangular Bézier surfaces or rational triangular Bézier surfaces in CAD (computer aided design), it has wide application prospects in reverse engineering.     

Medial axis of a planar region by offset self-intersections

The medial axis (MA) of a planar region is the locus of those maximal disks contained within its boundary. This entity has many CAD/CAM applications. Approximations based on the Voronoi diagram are efficient for linear-arc boundaries, but such constructions are more difficult if the boundary is free. This paper proposes an algorithm for free-form boundaries that uses the relation between MA and offsets. It takes the curvature information from the boundary in order to find the self-intersections of successive offset curves. These self-intersection points belong to the MA and can be interpolated to obtain an approximation in Bézier form. This method also approximates the medial axis transform by using the offset distance to each self-intersection.     

Localized construction of curved surfaces from polygon meshes: A simple and practical approach on GPU

We present a method for refining n-sided polygons on a given piecewise linear model by using local computation, where the curved polygons generated by our method interpolate the positions and normals of vertices on the input model. Firstly, we construct a Bézier curve for each silhouette edge. Secondly, we employ a new method to obtain C¹ continuous cross-tangent functions that are constructed on these silhouette curves. An important feature of our method is that the cross tangent functions are produced solely by their corresponding facet parameters. Gregory patches can therefore be locally constructed on every polygon while preserving G¹ continuity between neighboring patches. To provide a flexible shape control, several local schemes are provided to modify the cross-tangent functions so that the sharp features can be retained on the resultant models. Because of the localized construction, our method can be easily accelerated by graphics hardware and fully run on the Graphics Processing Unit (GPU).     

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螺线更为简单高效。     

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

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

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.     

On Bézier surfaces in three-dimensional Minkowski space

In this paper, we study Bézier surfaces in three-dimensional Minkowski space. In particular, we focus on timelike and spacelike cases for Bézier surfaces. We also deal with the Plateau–Bézier problem in , obtaining conditions over the control net to be extremal of the Dirichlet function for both timelike and spacelike Bézier surfaces. Moreover, we provide interesting examples showing the behavior of the Plateau–Bézier problem in and illustrating the relationship between it and the corresponding Plateau–Bézier problem in the Euclidean space R³.