Curve offsetting based on Legendre series

Abstract

Curve offsetting is one of the most important geometric operations in CAD/CAM systems due to its immediate applications to NC machining. Although offset curves to Pythagorean hodograph curves are rational, offset curves to generic rational curves are non-rational and hence incompatible with B-spline representation. For this reason, approximation techniques have been widely used for curve offsetting. From the Neumann theorem it is known that an analytic function defined over [-1,1] has a converging Legendre series. Based on the use of the Legendre series, we present a stable and efficient method for offsetting planar B-spline curves. Our approach provides users with easy control of approximation accuracy and flexibility to determine the degree of an offset curve.

1  Introduction

An offset curve is a curve that is a constant distance d from the given initial curve. Thus, an offset of a planar parametric (rational) curve r is given by

rd(t) = r(t)+d n(t)
where n(t) is the unit normal of r at t and is uniquely defined. For a given orientation of n(t), d can be either positive or negative so that an offset can lie on either side of the initial curve. Without loss of generality, we may assume r(t) is in the x-y plane. Then, the offset of r(t) with signed distance is explicitly given by















xd(t)=x(t)- y(t)



x(t)2+y(t)2
yd(t) = y(t)+d  x(t)



x(t)2+y(t)2
(1)
Because of the radical (or square root) incurred in normalising the normal, the offset curve is in general not rational. Farouki (Farouki, 1992) proved that there exists a class of special polynomial curves, namely, the Pythagorean hodograph (PH) curves whose hodographs r(t) have polynomial norms. Therefore, the offsets of PH curves are rational. For example, a parametric curve

x(t)=3(t2-1),    y(t)=t(t2-1)
is a PH curve since {x(t)2+y(t)2}=3t2+1. Lü proved that there exists a wider class of rational curves whose offset curves are rational (Lü, 1995). However, offsets to generic rational curves are not rational and hence incompatible with a B-spline representation - the standard in most CAD systems. For this reason, approximation methods are still a feasible practical solution to curve offsetting.

It is not our purpose to survey all approximation methods used for curve offsetting since such a topic is already covered in several publications (Lee et al, 1996; Hoschek and Lasser, 1993). At Intergraph, we implemented and tested extensively the method proposed by Tiller and Hanson (Tiller and Hanson, 1984). Their method is based on subdivision and offsetting the control polygon of Bézier or B-spline curves. There are some advantages with their algorithm: Polynomial and rational curves are handled with one algorithm; offsets of lines and circles are obtained precisely with one iteration. However, since their approach is basically an experimental method, there are some disadvantages:

Recently, Lee et al proposed a quasi-direct approximation method (Lee et al, 1996). In their approach, an offset circle with radius d is approximated by piecewise quadratic Bézier curves within some tolerance. Then, the offset curve is created by the convolution of r(t) with the quadratic Bézier curves. Their method offers a good control of approximation accuracy. However, Lee's method results in an offset curve of relatively high degree and large number of control points.

In this paper, we shall propose a quasi-direct and hence efficient method for curve offsetting. Our method is based on the use of the Legendre series, which converges to any analytic function f on [-1,1].

2  Convergence of Legendre series for analytic function

We start our discussion with analytic functions (Flanigan, 1988). Definition 1 Let f(x) be in C[a,b]. Then, f(x) is analytic on [a,b] if for every x0 in [a,b] the Taylor series of f(x) at x0 converges for all x such that |x-x0| < d for some d > 0.

In other words, if f is analytic on [a,b] then, for each point x0 [a,b], we can form the Taylor expansion that converges to f(x) in some neighbourhood of x0. Accordingly, a partial sum of this Taylor series may be used to compute f(x) for |x-x0| < p(x0). For example, expanding 1/[(1+x)] at x0=0 gives

1
  ___
1+x
=1- 1
2
x+ 1·3
2·4
x2 ++(-1)k 1·3(2k-1)
2·42k
xk+,
which is valid for x (-1,1]. The (k+1)st finite sum of the power series is a canonical polynomial of degree k, denoted by Pk(x). The above series is an alternating series. Therefore, if Pk(x) is used to approximate f(x) on the interval (-1,1], the error incurred is less than the absolute value of the (k+1)th term, i.e.,

|f(x) - Pk(x)| <

1·3(2k+1)
2·42(k+1)
xk+1

1·3(2k+1)
2·42(k+1)
The above example indicates that, if f(x) has a converging Taylor series, we may use the partial sum of the series to approximate f(x). However, in order to use the Taylor series to represent f(x) on [a,b], we need to resolve at least the following two questions:

These obstacles lead us to look for the Legendre series which, by the following theorem, has a promising property in approximation theory.

Theorem 1 [Neumann theorem] Let Er be an ellipse on the complex plane with the centre at (0,0), the major semi-axis, a=(r+1/r)/2, on the axis of real numbers, and the minor semi-axis, b=(r-1/r)/2, on the axis of imaginary numbers. Let f(z) be analytic in the interior of Er with r > 1, but not in the interior of any Er with r > r. Then,
f(z)=

k=0 
aklk(z)
where lk(z) are Legendre polynomials of degree k and

ak= 2k+1
2

+1

-1 
lk(x)f(x)dx
(2)
That is to say there exists a Legendre series converging absolutely and uniformly to f(z) on any closed set in the interior of Er. Moreover,

lim
k 
sup|ak|1/k= 1
r
.

Proof of the above theorem may be found in (Davis, 1975). In real analysis, we are concerned with analytic functions f on a real interval [-1,1] (If f is defined in an arbitrary interval [a,b], we can reparametrise f(x) by t=(2x-b-a)/(b-a) such that t [-1,1]). Then, by the Neumann theorem, there exists a Legendre series converging absolutely and uniformly to f on [-1,1]. Further, the converging speed is determined by r. Therefore, problems with respect to the use of a Taylor series are avoided if a Legendre series is used.

An infinite Legendre series cannot be represented in a computer. We need to consider the truncation of the Legendre series. It is noted that the Legendre series converges absolutely and uniformly to f(x) on [-1,1]. Therefore, given an arbitrarily small number e > 0, there exists M such that when m > M we have


f(x)- m

k=0 
aklk(x)
< e.
Accordingly, we can use a partial sum of Legendre series to approximate f(x). The computation of ak is considered in the following section.

3  Computing coefficients of Legendre series

Referring to (2), we note that computation of the coefficients of a Legendre series involves an integration. We thus start by considering the Gauss-Legendre integration. Integrating f(x) with respect to x [-1,1] by the Gauss-Legendre method gives (Phillips and Taylor, 1973):


+1

-1 
f(x)dx @ N

i=0 
Aif(xi)
where xi are zeros of the Legendre polynomial of degree N+1 and Ai are the Gauss integration coefficients. If f(x) is a polynomial of degree less or equal to 2N+1, the sum of the right side gives an exact solution. From this fact, we can determine Ai by taking f(x) to be 1,x,x2,,xn. Since the computation of Ai is independent of f(x), we can thus compute and tabulate them in advance. In fact, the table of xi and Ai can be found in many mathematic handbooks (Abramowitz and Stegun,1972).

We now consider the computation of ak (k=0,1,m) given in (2). Using the Gauss-Legendre integration method gives

ak= 2k+1
2

+1

-1 
lk(x)f(x)dx @ 2k+1
2
N

i=0 
Ailk(xi)f(xi) = N

i=0 


2k+1
2
Ailk(xi)

f(xi)
where, xi are zeros of Legendre polynomial of degree N+1. Let Aik=[(2k+1)/2]Ailk(xi). Then, ak @ i=0N Akif(xi). In order to obtain a good approximation, we require N > m. For detailed discussion on error bound, one may refer to (Malosse, 1994). Since the computation of Aik is again independent of f(x), we may thus tabulate Aik for the purpose of efficiency. As an example, we illustrate the table of xi and Aki when N=3:

xi Ai A0i A1i A2i A3i
0.8611363 0.3478548 0.1739274 0.4493257 0.5325080 0.3710270
0.3398810 0.6521452 0.3260726 0.3325755 -0.5325080 -0.9397725

Table 1: Gauss-Legendre integration coefficients.

4  Offsetting polynomial curve

Let r be a planar parametric curve defined over t [-1,1]. If r(t) 0 in the given interval, then r(t) is a regular curve and its unit normal is well defined. For a properly parametrised curve, r(t)=0 indicates the occurrence of a cusp (Li and Cripps, 1997). In the case where r(t) has a cusp, we may subdivide the curve at the cusp so that a subdivided curve is regular. Therefore, we assume in the subsequent sections that r is a regular curve.

Referring to equation (1), it known that an offset to a generic rational curve r is non-rational due to the square root incurred in normalising the normal. If r(t) 0 "t [-1,1], the offset rd is analytic on [-1,1] (For detailed discussion on analyticity, one may refer to (Flanigan, 1988)). By the Neumann theorem, rd(t) can thus be represented by the Legendre series rd(t)=k=0aklk(t), where ak are determined by (2), i.e.,

ak= 2k+1
2

+1

-1 
lk(t)rd(t)dt.
Since the Legendre series converges geometrically to rd(t), for any given distance tolerance e > 0 there exists M such that when m > M

||rd(t)- m

k=0 
ak lk(t)|| = ||

k=m+1 
ak lk(t)|| < e
where, || || denotes the Euclidean norm. Let Rm(t)=||k=m+1 ak lk(t)||. Although it is possible to compute r (cf. Neumann theorem) based on the complex roots of an analytic function and hence to estimate M (Malosse, 1994), it is preferred to using a fixed m (e.g., m=20) to construct a finite Legendre series Pm(t)=k=0mak lk(t). Accordingly, we can pre-determine the size of the table of Aik which is required for efficient computation of the coefficients of a Legendre series. If m is sufficiently large, we should have Rm(t) << e and be able to further truncate Pm(t) to a lower degree polynomial Pn(t) (n < m). Thus, whether Pm(t) can further be truncated becomes a criterion for a convergence test. Since |lk(t)| 1, we have
||Pm(t)-Pn(t)||=|| m

k=n+1 
aklk(t)|| m

k=n+1 
||ak||.
If k=n+1m||ak|| < e/l (l > 2), then Pm(t) can be truncated and the truncated Legendre polynomial approximates rd(t) within the given tolerance. Otherwise, we subdivide the curve r(t) and construct the finite Legendre series for each subdivided segment. This process may need repeating several times until a converged finite Legendre series is obtained. We summarise the procedures as follows:

  1. Converting r(t) into a canonical curve defined over [-1,1].
  2. Computing rd(ti) given in (1), where ti are zeros of Legendre polynomial of degree N+1.
  3. Computing ak=i=0N Aki rd(ti) with k=0,1,,m (m < N).
  4. Checking if the finite Legendre series k=0mak lk(t) can be truncated further. If so, terminate. Otherwise, subdivide r(t) and goto step 2.

We now look at an example.

Example 1: Offsetting a cubic Bézier curve with d=4.0 and e = 10-4. The control points of the Bézier curve are p0=(0, 0), p1=(3, -5), p2=(6, -5), and p3=(0,10).

We choose m=15 and N=19 to construct Legendre series. After truncation, the two offsets are polynomial curves of degree 9 and illustrated in Figure 1.

 

Figure 1: Offsetting a cubic Bézier curve.

A B-spline curve is a piecewise polynomial (rational) curve. For each B-spline segment, we may convert it into a canonical curve defined over t [-1,1]. Therefore, offsetting a B-spline curve is carried out as offsetting a number of polynomial (rational) curves.

5  Conversion from Legendre to B-spline

In many CAD/CAM systems, curves are represented in either Bézier or B-spline form. In this section we discuss the conversion from Legendre to B-spline. Representing a Legendre polynomial of degree k in the Bézier form gives (Malosse, 1994):

lk(x)= k

i=0 
(-1)k-iCki Bi,k(x)
where, Bi,k(x)=Cki(1-x)k-ixi. Using this formula in cooperation with degree elevation, we can represent an offset curve rd(t)=k=0maklk(t) in the Bézier form. However, this simple conversion method does not provide flexibility to control the degree of an offset curve. Thus, it is of interest to derive a generic algorithm that converts rd(t) in the Legendre basis into a B-spline curve of any degree.

To reduce the degree of an offset curve of degree m, we may subdivide rd(t) represented in the Legendre basis such that each subdivided segment can be approximated by a Bézier curve of degree n (n < m). Consequently, rd(t) is approximated by a Bézier spline of degree n with, in general, C0 continuity at joints. This approach is similar to degree reduction of Bézier curve discussed in (Watkins and Worsey, 1988). If we add constraints to this degree reduction scheme such that any two adjacent Bézier curves have up to (n-1)st derivatives continuity, we can thus remove all interior multiple knots and obtain a B-spline curve of degree n with Cn-1 continuity everywhere (Malosse, 1994). Obviously, adding constraints will increase levels of subdivision.

We end our discussion by illustrating a few more examples. The comparison results are based on our implementation of three methods: offsetting control polygons (method 1), discrete least squares approximation (method 2), and Legendre series (method 3). It should be noted that no optimisation procedures are implemented in both method 1 and 2.

Example 2: Offsetting a cubic B-spline curve with d=1.0. The original curve has 25 control points and a very small loop.

 

Figure 2: Offsetting a cubic B-spline curve with a loop.

In this case, an approximation method based on offsetting control polygons or the discrete least squares method would experience difficulties in determining a choice of sample points in the vicinity of the loop. Accordingly, both methods spend much more CPU time than our method. Detailed comparison results are given in Table 2.

Method e Control points CPU
1 10-3 146 1.95s
2 10-3 152 1.25s
3 10-3 142 0.27s

Table 2: Curve offsetting results of Example 2.

Example 3: Offsetting a unit circle represented by a rational quadratic B-spline curve with d=1.5.

 

Figure 3: Offsetting a unit circle.

We require an offset to be a polynomial curve of degree 3 with approximation accuracy e = 10-4. The results of three methods are given in Table 3.

Method e Control points CPU
1 10-4 7 0.02s
2 10-4 45 0.10s
3 10-4 32 0.07s

Table 3: Curve offsetting results of Example 3.

Since the method of offsetting control polygons is exact for a circle, method 1 yields the least control points. However, our method results in fewer control points than that of method 2. This experimental example can also be found in (Lee et al, 1996).

Example 4: Offsetting a cubic B-spline curve with d=0.5 and e = 10-3. The control points of the curve are (-3.01619,2.34143), (-3.97193,-2.20842), (-1.07045,0.0722807), (0.319568,-2.77522), (-0.152767,2.299), (2.92416,-0.939865), and (2.8027,3.02775) (This example can be found in Lee at al's paper).

 

Figure 4: Offsetting a cubic B-spline curve.

We require the offset curve to have at least C1 continuity at joints. Detailed results are given in Table 4 (a).

Method e Control points CPU
1 10-3 88 0.85s
2 10-3 74 0.23s
3 10-3 97 0.15s

Table 4 (a): Curve offsetting results of Example 4.

In terms of the number of control points, methods 1 and 2 are better than our method. However, if the approximation accuracy increases, our method is superior to other methods in terms of stability, CPU time, and the number of control points. Detailed results are given below:

Method e Control points CPU
1 10-4 144 1.76s
2 10-4 112 0.5s
3 10-4 102 0.17s

Table 4 (b): Curve offsetting results of Example 4.

If e = 10-5, our method uses 0.3s of CPU time to generate an offset curve that has 135 control points. Since our implementation of other two methods failed to generate an offset curve within the required tolerance, one may want to check the results in (Lee at al, 1996). According to their results, our method still yields the least number of control points for e = 10-5.

6  Conclusions

We have seen significant improvement in terms of easy control of approximation accuracy, efficiency and stability over other approximation methods of curve offsetting. The easy control of approximation accuracy is achieved because of the simple criterion of convergence test. The efficiency is accomplished due to our approach is a quasi-direct method which avoids sampling a large amount of data points. Finally, the stability comes from a well-defined error bound for truncating a Legendre series.

Although we did not discuss offsetting 3-D curves in this paper, it should be pointed out that extension of our algorithm to 3-D cases is straight forward if a normal of a 3-D curve is defined.

Currently, the bottle-neck of our approach is the conversion from Legendre to B-spline basis of any degree as it takes significant amount of total processing time. Therefore, it is of importance to carry out further research on the conversion between Legendre and B-spline bases.

Acknowledgement

We wish to express our thanks to J-J Malosse for his valuable comments and criticism. Our special thanks also go to the referees of this paper for their helpful suggestions and comments.

References

Abramowitz, M. and Stegun, I. (1972), Handbook of Mathematical Functions, Dover Pub., Inc.
Davis, P.J. (1975), Interpolation & Approximation, Dover Pub., Inc.
Farouki, R.T. (1992), Pythagorean-Hodograph Curves in Practical Use, in R.E. Barnhill eds. Geometry Processing for Design and Manufacturing, SIAM press.
Farouki, R.T. and Sederberg, T.W. (1995), Analysis of the offset to a parabola, Computer Aided Geometric Design 12, 639-644.
Flanigan, F.J. (1988), Complex Variables-Harmonic and Analytic Functions, Dover Pub., Inc.
Hoschek, J. and Lasser, D. (1993), Fundamentals of Computer Aided Geometric Design, A K Peter, Ltd.
Lee, I.K. et al (1996), Planar curve offset based on circle approximation, Computer-Aided Design 28, 617-630.
Li, Y.M. and Cripps, R.J. (1997), Identification of inflection points and cusps on rational curves, Computer Aided Geometric Design 14, 491-497.
Lü, W. (1995), Offset-rational parametric plane curves, Computer Aided Geometric Design 12, 601-616.
Malosse, J-J (1994), Parametrisation of implicit elliptic curves by rational functions, in R.B. Fisher ed. Design and Application of Curves and Surfaces: The Mathematics of Surfaces V, Oxford Univ. Press.
Phillips, G.M. and Taylor, P.J. (1973), Numerical Analysis, Academic Press, London.
Tiller, W. and Hanson, E.G. (1984), Offsets of Two-Dimensional Profiles, IEEE Computer Graphics and Applications, 36-46.
Watkins, M.A. and Worsey, A.J. (1988), Degree reduction of Bézier curves, Computer-Aided Design 20, 398-405.

RETURN