Curve offsetting based on Legendre series

Abstract

1  Introduction

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)-d  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)²+y^¢(t)²}=3t²+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:

• It is difficult to determine where to subdivide a curve such that an offsetting procedure is optimised.
• There is no criterion to determine how many sample points in each span should be used for the convergence check.

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

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

1   ___ Ö1+x =1- 1 2 x+ 1·3 2·4 x2 +¼+(-1)k 1·3¼(2k-1) 2·4¼2k 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 P_k(x). The above series is an alternating series. Therefore, if P_k(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·4¼2(k+1) xk+1 ê ê ê £ 1·3¼(2k+1) 2·4¼2(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:

• If f(x) is analytic on [a,b], can we expand f(x) at x₀ Î [a,b] such that the Taylor series converges to f(x) in the whole interval [a,b]? (The answer is NO in general.)
• If the Taylor series converge to f(x), does it converge to f(x) fast enough?

Theorem 1 [Neumann theorem] Let E_r 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 E_r with r > 1, but not in the interior of any E_r¢ with r^¢ > r. Then,

f(z)= ¥ å k=0  aklk(z)

where l_k(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 E_r. 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 a_k is considered in the following section.

3  Computing coefficients of Legendre series

ó õ +1 -1  f(x)dx @ N å i=0  Aif(xi)

where x_i are zeros of the Legendre polynomial of degree N+1 and A_i 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 A_i by taking f(x) to be 1,x,x²,¼,xⁿ. Since the computation of A_i is independent of f(x), we can thus compute and tabulate them in advance. In fact, the table of x_i and A_i can be found in many mathematic handbooks (Abramowitz and Stegun,1972).

We now consider the computation of a_k (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, x_i are zeros of Legendre polynomial of degree N+1. Let A_i^k=[(2k+1)/2]A_il_k(x_i). Then, a_k @ å_i=0^N A^k_if(x_i). 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 A_i^k is again independent of f(x), we may thus tabulate A_i^k for the purpose of efficiency. As an example, we illustrate the table of x_i and A^k_i 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

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 r_d is analytic on [-1,1] (For detailed discussion on analyticity, one may refer to (Flanigan, 1988)). By the Neumann theorem, r_d(t) can thus be represented by the Legendre series r_d(t)=å_k=0^¥a_kl_k(t), where a_k are determined by (2), i.e.,

ak= 2k+1 2 ó õ +1 -1  lk(t)rd(t)dt.

Since the Legendre series converges geometrically to r_d(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 R_m(t)=||å_k=m+1^¥ a_k l_k(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 P_m(t)=å_k=0^ma_k l_k(t). Accordingly, we can pre-determine the size of the table of A_i^k which is required for efficient computation of the coefficients of a Legendre series. If m is sufficiently large, we should have R_m(t) << e and be able to further truncate P_m(t) to a lower degree polynomial P_n(t) (n < m). Thus, whether P_m(t) can further be truncated becomes a criterion for a convergence test. Since |l_k(t)| £ 1, we have

||Pm(t)-Pn(t)||=|| m å k=n+1  aklk(t)|| £ m å k=n+1  ||ak||.

If å_k=n+1^m||a_k|| < e/l (l > 2), then P_m(t) can be truncated and the truncated Legendre polynomial approximates r_d(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 r_d(t_i) given in (1), where t_i are zeros of Legendre polynomial of degree N+1.
3. Computing a_k=å_i=0^N A^k_i r_d(t_i) with k=0,1,¼,m (m < N).
4. Checking if the finite Legendre series å_k=0^ma_k l_k(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 p₀=(0, 0), p₁=(3, -5), p₂=(6, -5), and p₃=(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

lk(x)= k å i=0  (-1)k-iCki Bi,k(x)

where, B_i,k(x)=C_kⁱ(1-x)^k-ixⁱ. Using this formula in cooperation with degree elevation, we can represent an offset curve r_d(t)=å_k=0^ma_kl_k(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 r_d(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 r_d(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, r_d(t) is approximated by a Bézier spline of degree n with, in general, C⁰ 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 C^n-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 C¹ 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

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.