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.     

G 2 blends of linear segments with cubics and Pythagorean-hodograph quintics

Fillets, also known as blend arcs, are used in CNC machining to round corners. Fillets are normally circular arcs, which have G ¹ contact with the straight line segments to which they are joined. Recent advances in machining technology allow NURBS, including Pythagorean-hodograph (PH) curve segments, to be incorporated in CNC tool paths. This article examines the use of cubic and PH quintic Bézier curve segments that have a single curvature extremum, and which have G ² contact with the straight line segments to which they are joined, as fillets. It is shown how the extreme circle of curvature can be determined. The point of curvature extremum and the corresponding value of the curvature can be changed by adjusting the joining points of the blending curve with the neighbouring straight lines. These blending curves can also be incorporated in computer-aided design packages for curve or surface design.     

Hermite interpolation with simple planar PH curves by speed reparametrization

We introduce a new method of solving C¹ Hermite interpolation problems, which makes it possible to use a wider range of PH curves with potentially better shapes. By characterizing PH curves by roots of their hodographs in the complex representation, we introduce PH curves of type K(t−c)²ⁿ⁺¹+d. Next, we introduce a speed reparametrization. Finally, we show that, for C¹ Hermite data, we can use PH curves of type K(t−c)²ⁿ⁺¹+d or strongly regular PH quintics satisfying the G¹ reduction of C¹ data, and use these curves to solve the original C¹ Hermite interpolation problem.     

Equivalence of distinct characterizations for rational rotation-minimizing frames on quintic space curves

A rotation-minimizing frame on a space curve r(t) is an orthonormal basis (f₁,f₂,f₃) for R³, where f₁=r^′/|r^′| is the curve tangent, and the normal-plane vectors f₂,f₃ exhibit no instantaneous rotation about f₁. Such frames are useful in spatial path planning, swept surface design, computer animation, robotics, and related applications. The simplest curves that have rational rotation-minimizing frames (RRMF curves) comprise a subset of the quintic Pythagorean-hodograph (PH) curves, and two quite different characterizations of them are currently known: (a) through constraints on the PH curve coefficients; and (b) through a certain polynomial divisibility condition. Although (a) is better suited to the formulation of constructive algorithms, (b) has the advantage of remaining valid for curves of any degree. A proof of the equivalence of these two different criteria is presented for PH quintics, together with comments on the generalization to higher-order curves. Although (a) and (b) are both sufficient and necessary criteria for a PH quintic to be an RRMF curve, the (non-obvious) proof presented here helps to clarify the subtle relationships between them.     

Path planning with obstacle avoidance by G1 PH quintic splines

We propose a two-step approach for the construction of planar smooth collision-free navigation paths. Obstacle avoidance techniques that rely on classical data structures are initially considered for the identification of piecewise linear paths having no intersection with the obstacles of a given scenario. Variations of the shortest piecewise linear path with angle-based criteria are proposed and discussed. In the second part of the scheme we rely on spline interpolation algorithms with tension parameters to provide a smooth planar control strategy. In particular, we consider the class of curves with Pythagorean structures, because they provide an exact computation of fundamental geometric quantities. A selection of test cases demonstrates the quality of the new motion planning scheme.     

Bisector curves of planar rational curves

This paper presents a simple and robust method for computing the bisector of two planar rational curves. We represent the correspondence between the foot points on two planar rational curves C₁(t) and C₂(r) as an implicit curve (t,r)=0, where (t,r) is a bivariate polynomial B-spline function. Given two rational curves of degree m in the xy-plane, the curve (t,r)=0 has degree 4m−2, which is considerably lower than that of the corresponding bisector curve in the xy-plane.     

Efficient generation of secure elliptic curves

In many cryptographic applications it is necessary to generate elliptic curves (ECs) whose order possesses certain properties. The method that is usually employed for the generation of such ECs is the so-called Complex Multiplication method. This method requires the use of the roots of certain class field polynomials defined on a specific parameter called the discriminant. The most commonly used polynomials are the Hilbert and Weber ones. The former can be used to generate directly the EC, but they are characterized by high computational demands. The latter have usually much lower computational requirements, but they do not directly construct the desired EC. This can be achieved if transformations of their roots to the roots of the corresponding (generated by the same discriminant) Hilbert polynomials are provided. In this paper we present a variant of the Complex Multiplication method that generates ECs of cryptographically strong order. Our variant is based on the computation of Weber polynomials. We present in a simple and unifying manner a complete set of transformations of the roots of a Weber polynomial to the roots of its corresponding Hilbert polynomial for all values of the discriminant. In addition, we prove a theoretical estimate of the precision required for the computation of Weber polynomials for all values of the discriminant. We present an extensive experimental assessment of the computational efficiency of the Hilbert and Weber polynomials along with their precision requirements for various discriminant values and we compare them with the theoretical estimates. We further investigate the time efficiency of the new Complex Multiplication variant under different implementations of a crucial step of the variant. Our results can serve as useful guidelines to potential implementers of EC cryptosystems involving generation of ECs of a desirable order on resource limited hardware devices or in systems operating under strict timing response constraints. This work was partially supported by the IST Programme of EC under contract no. IST-2001-33116 (FLAGS), and by the Action IRAKLITOS (Fellowships for Research in the University of Patras) with matching funds from ESF (European Social Fund) and the Greek Ministry of Education.     

Estimating derivatives and curvature of open curves

This article presents an effective spectral approach to estimate derivatives and curvature of open parametric curves. As the method is based on the discrete Fourier transform, the discontinuities of the curve (as well as of its derivatives) must be controlled to minimize the Gibbs phenomenon. We address this problem by obtaining a smooth extension of the curve in such a way as to suitably close it, which is done through a variational approach taking into account the spectral energy of differentiated versions of the extended curves. This novel method presents potential for applications in a broad class of problems, ranging from applied and experimental physics to image analysis.     

Triangular Bernstein moment-based identification of algebraic curves

Extending our previous results, in this paper we present a theoretical improvement of a strategy for the identification of binary images with algebraic boundaries. Such identification is obtained from few samples and it is based on a representation of the image shape in terms of non-separable bivariate Bernstein polynomials piecewisely defined over triangular domains.     

Curvature of singular Bézier curves and surfaces

This paper presents a general approach for finding the limit curvature at a singular endpoint of a rational Bézier curve and the singular corner of a rational Bézier surface patch. Conditions for finite Gaussian and mean limit curvatures are expressed in terms of the rank of a matrix.     

Multi-degree reduction of NURBS curves based on their explicit matrix representation and polynomial approximation theory

NURBS curve is one of the most commonly used tools in CAD systems and geometric modeling for its various specialties, which means that its shape is locally adjustable as well as its continuity order, and it can represent a conic curve precisely. But how to do degree reduction of NURBS curves in a fast and efficient way still remains a puzzling problem. By applying the theory of the best uniform approximation of Chebyshev polynomials and the explicit matrix representation of NURBS curves, this paper gives the necessary and sufficient condition for degree reducible NURBS curves in an explicit form. And a new way of doing degree reduction of NURBS curves is also presented, including the multi-degree reduction of a NURBS curve on each knot span and the multi-degree reduction of a whole NURBS curve. This method is easy to carry out, and only involves simple calculations. It provides a new way of doing degree reduction of NURBS curves, which can be widely used in computer graphics and industrial design.     

Construction of Bézier surface patches with Bézier curves as geodesic boundaries

Given four polynomial or rational Bézier curves defining a curvilinear rectangle, we consider the problem of constructing polynomial or rational tensor-product Bézier patches bounded by these curves, such that they are geodesics of the constructed surface. The existence conditions and interpolation scheme, developed in a general context in earlier studies, are adapted herein to ensure that the geodesic-bounded surface patches are compatible with the usual polynomial/rational representation schemes of CAD systems. Precise conditions for four Bézier curves to constitute geodesic boundaries of a polynomial or rational surface patch are identified, and an interpolation scheme for the construction of such surfaces is presented when these conditions are satisfied. The method is illustrated with several computed examples.     

Identification of spatial PH quintic Hermite interpolants with near-optimal shape measures

The problem of specifying the two free parameters that arise in spatial Pythagorean-hodograph (PH) quintic interpolants to given first-order Hermite data is addressed. Conditions on the data that identify when the “ordinary” cubic interpolant becomes a PH curve are formulated, since it is desired that the selection procedure should reproduce such curves whenever possible. Moreover, it is shown that the arc length of the interpolants depends on only one of the parameters, and that four (general) helical PH quintic interpolants always exist, corresponding to extrema of the arc length. Motivated by the desire to improve the fairness of interpolants to general data at reasonable computational cost, three selection criteria are proposed. The first criterion is based on minimizing a bivariate function that measures how “close” the PH quintic interpolants are to a PH cubic. For the second criterion, one of the parameters is fixed by first selecting interpolants of extremal arc length, and the other parameter is then determined by minimizing the distance measure of the first method, considered as a univariate function. The third method employs a heuristic but efficient procedure to select one parameter, suggested by the circumstances in which the “ordinary” cubic interpolant is a PH curve, and the other parameter is then determined as in the second method. After presenting the theory underlying these three methods, a comparison of empirical results from their implementation is described, and recommendations for their use in practical design applications are made.     

Approximate G continuous interpolation of a rectangular network of rational cubic curves

The problem of spanning a rectangular network of rational cubic curves with a smooth surface is discussed in this paper. Provided the network is compatible with a smooth surface, then algorithms for patch construction, optimization and subdivision are developed to construct an ‘approximately smooth’ surface, that is, G¹ continuous to within some tolerance, composed of rational bicubic patches. The algorithms have been applied in the die and mould industry. The toolmaker constructs a wireframe model of an EDM (electro-discharge machining) electrode and the algorithms automatically construct the surface model. For toolmaking companies, this simplifies the surface modelling process making a highly-specialized and time-consuming task virtually automatic.