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 nonrational and hence incompatible with Bspline
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 Bspline 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
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 xy plane. Then, the offset
of r(t) with signed distance is explicitly given by

ì ï ï ï ï ï ï í
ï ï ï ï ï ï î


x_{d}(t)=x(t)d 
y^{¢}(t)
 Ö 
x^{¢}(t)^{2}+y^{¢}(t)^{2} 


 y_{d}(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(t^{2}1), y(t)=t(t^{2}1) 

is a PH curve since Ö{x^{¢}(t)^{2}+y^{¢}(t)^{2}}=3t^{2}+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 Bspline 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 Bspline 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.
Recently, Lee et al proposed a quasidirect 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 quasidirect 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 x_{0} in [a,b] the Taylor series of f(x) at x_{0} converges for all
x such that xx_{0} < d for some d > 0.
In other words, if f is analytic on [a,b] then, for each point
x_{0} Î [a,b], we can form the Taylor expansion that converges to f(x) in
some neighbourhood of x_{0}. Accordingly, a partial sum of this Taylor series
may be used to compute f(x) for xx_{0} < p(x_{0}). For example, expanding
1/Ö[(1+x)] at x_{0}=0 gives

1

=1 
1 2

x+ 
1·3 2·4

x^{2} +¼+(1)^{k} 
1·3¼(2k1) 2·4¼2k

x^{k}+¼, 

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)  P_{k}(x) < 
ê ê
ê

1·3¼(2k+1) 2·4¼2(k+1)

x^{k+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_{0} Î [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?
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 E_{r} be an ellipse on the complex plane with the centre at
(0,0), the major semiaxis, a=(r+1/r)/2, on the axis of real numbers,
and the minor semiaxis, b=(r1/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

a_{k}l_{k}(z) 

where l_{k}(z) are Legendre polynomials of degree k and
a_{k}= 
2k+1 2


ó õ

+1
1

l_{k}(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®¥

supa_{k}^{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=(2xba)/(ba) 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

a_{k}l_{k}(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
Referring to (2), we note that computation of the coefficients of a Legendre
series involves an integration. We thus start by considering the GaussLegendre
integration. Integrating f(x) with respect to x Î [1,1] by the
GaussLegendre method gives (Phillips and Taylor, 1973):

ó õ

+1
1

f(x)dx @ 
N å
i=0

A_{i}f(x_{i}) 

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^{2},¼,x^{n}. 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 GaussLegendre integration method gives
a_{k}= 
2k+1 2


ó õ

+1
1

l_{k}(x)f(x)dx @ 
2k+1 2


N å
i=0

A_{i}l_{k}(x_{i})f(x_{i}) = 
N å
i=0


æ ç
è

2k+1 2

A_{i}l_{k}(x_{i}) 
ö ÷
ø

f(x_{i}) 

where, x_{i} are zeros of Legendre polynomial of degree N+1. Let
A_{i}^{k}=[(2k+1)/2]A_{i}l_{k}(x_{i}). Then,
a_{k} @ å_{i=0}^{N} A^{k}_{i}f(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:
x_{i}  A_{i}  A^{0}_{i}  A^{1}_{i}  A^{2}_{i}  A^{3}_{i} 
±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: GaussLegendre 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 nonrational 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_{k}l_{k}(t), where
a_{k} are determined by (2), i.e.,
a_{k}= 
2k+1 2


ó õ

+1
1

l_{k}(t)r_{d}(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
r_{d}(t) 
m å
k=0

a_{k} l_{k}(t) =  
¥ å
k=m+1

a_{k} l_{k}(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}^{m}a_{k} l_{k}(t). Accordingly, we can predetermine 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
P_{m}(t)P_{n}(t)= 
m å
k=n+1

a_{k}l_{k}(t) £ 
m å
k=n+1

a_{k}. 

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:
 Converting r(t) into a canonical curve defined over [1,1].
 Computing r_{d}(t_{i}) given in (1), where t_{i} are zeros of
Legendre polynomial of degree N+1.
 Computing a_{k}=å_{i=0}^{N} A^{k}_{i} r_{d}(t_{i}) with k=0,1,¼,m
(m < N).
 Checking if the finite Legendre series å_{k=0}^{m}a_{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, 0),
p_{1}=(3, 5), p_{2}=(6, 5), and p_{3}=(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 Bspline curve is a piecewise polynomial (rational) curve. For each Bspline
segment, we may convert it into a canonical curve defined over t Î [1,1].
Therefore, offsetting a Bspline curve is carried out as offsetting a number
of polynomial (rational) curves.
5 Conversion from Legendre to Bspline
In many CAD/CAM systems, curves are represented in either Bézier or Bspline
form. In this section we discuss the conversion from Legendre to Bspline.
Representing a Legendre polynomial of degree k in the Bézier form gives
(Malosse, 1994):
l_{k}(x)= 
k å
i=0

(1)^{ki}C_{k}^{i} B_{i,k}(x) 

where, B_{i,k}(x)=C_{k}^{i}(1x)^{ki}x^{i}. Using this formula in cooperation with
degree elevation, we can represent an offset curve
r_{d}(t)=å_{k=0}^{m}a_{k}l_{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 Bspline 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^{0} 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 (n1)st derivatives continuity, we can thus remove all
interior multiple knots and obtain a Bspline curve of degree n with
C^{n1} 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 Bspline curve with d=1.0. The original
curve has 25 control points and a very small loop.
Figure 2: Offsetting a cubic Bspline 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
Bspline 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 Bspline 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 Bspline curve. 
We require the offset curve to have at least C^{1} 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 quasidirect method which avoids sampling a large amount of
data points. Finally, the stability comes from a welldefined error bound for
truncating a Legendre series.
Although we did not discuss offsetting 3D curves in this paper, it should be
pointed out that extension of our algorithm to 3D cases is straight forward if
a normal of a 3D curve is defined.
Currently, the bottleneck of our approach is the conversion from Legendre to
Bspline 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 Bspline bases.
Acknowledgement
We wish to express our thanks to JJ 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), PythagoreanHodograph 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, 639644.
 Flanigan, F.J. (1988), Complex VariablesHarmonic 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, ComputerAided Design 28, 617630.
 Li, Y.M. and Cripps, R.J. (1997), Identification of inflection points and
cusps on rational curves, Computer Aided Geometric Design 14,
491497.
 Lü, W. (1995), Offsetrational parametric plane curves, Computer
Aided Geometric Design 12, 601616.
 Malosse, JJ (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 TwoDimensional Profiles,
IEEE Computer Graphics and Applications, 3646.
 Watkins, M.A. and Worsey, A.J. (1988), Degree reduction of Bézier
curves, ComputerAided Design 20, 398405.
RETURN