∗

Comparing Offset Curve Approximation Methods

Gershon Elber+ , In-Kwon Lee∗ , and Myung-Soo Kim∗
+
Department of Computer Science, Technion, IIT, Haifa 32000, Israel
∗
Department of Computer Science, POSTECH, Pohang 790-784, Korea

Offset curves have diverse engineering applica- a constant radius d, is defined by:
tions, which have consequently motivated extensive
research concerning various offset techniques. Offset Cd (t) = C(t) + d · N (t), (1)
research in the early 1980s focused on approximation
techniques to solve immediate application problems where N (t) is the unit normal vector of C(t):
in practice. This trend continued until 1988, when
Hoschek [1, 2] applied non-linear optimization tech- (y
(t), −x
(t))
niques to the offset approximation problem. Since N (t) =
. (2)
then, it has become quite difficult to improve the x
(t)2 + y
(t)2
state-of-the-art of offset approximation.
Offset research in the 1990s has been more theoret- The regularity condition of C(t) guarantees that
ical. The foundational work of Farouki and Neff [3] (x
(t), y
(t)) = (0, 0) and N (t) is well defined on the
clarified the fundamental difficulty of exact offset curve C(t). Equation (2) has a square root term in
computation. Farouki and Sakkalis [4] suggested the the denominator. Therefore, even if the given curve
Pythagorean Hodograph curves which allow simple C(t) is a polynomial curve, its offset is not a polyno-
rational representation of their exact offset curves. mial or rational curve, in general. This fundamental
Although many useful plane curves such as conics deficiency has motivated the development of various
do not belong to this class, the Pythagorean Hodo- polynomial and rational approximation techniques
graph curves may have much potential in practice, of Cd (t). While the offset to a polynomial or ra-
especially when they are used for offset approxima- tional parametric curve must be approximated, it is
tion. somewhat counter-intuitive that a close cousin of the
In a recent paper [5] on offset curve approxima- offset, the evolute, is indeed always representable as
tion, the authors suggested a new approach based a rational curve (see Sidebar on Evolute).
on approximating the offset circle, instead of ap- Most offset approximation techniques are based
proximating the offset curve itself. To demonstrate on an iterative process of fitting an approximation
the effectiveness of this approach, we have made ex- curve, measuring the accuracy, and subdividing the
tensive comparisons with previous methods. To our problem into smaller problems if the approximation
surprise, the simple method of Tiller and Hanson error is larger than the tolerance. This divide and
[6] outperforms all the other methods for offsetting conquer approach exploits the subdivision property
(piecewise) quadratic curves, even though its perfor- of the base curve C(t). Henceforth, we assume C(t)
mance is not as good for high degree curves. is represented by a Bézier or NURBS curve.
The experimental results have revealed other in- Traditionally, the offset approximation error has
teresting facts, too. If these details had been re- been measured only at finite sample points along
ported several years ago, we believe, offset approx- C(t), computing i = C(ti )−Cda (ti )−d. Elber and
imation research might have developed somewhat Cohen [7] proposed a symbolic method which com-
differently. This paper is intended to fill in an im- putes the global error between squared distances:
portant gap in the literature. Qualitative as well
2
as quantitative comparisons are conducted employ- (t) = C(t) − Cda (t) − d2 . (3)
ing a whole variety of contemporary offset approx-
imation methods for freeform curves in the plane. The error function (t) is obtained by symbolically
The efficiency of the offset approximation is mea- computing the difference and inner product of Bézier
sured in terms of the number of control points gen- or NURBS curves (see Sidebar on Symbolic Compu-
erated while the approximations are made within a tation and Reference [8]). Therefore, it can be rep-
prescribed tolerance. resented as a Bézier or NURBS scalar function. As
a scalar field, the largest coefficient of (t) globally
bounds the maximal possible error due to the con-
Offset of Planar Curves vex hull property of Bézier or NURBS formulation.
In this article, we exploit the error functional (t)
Given a regular parametric curve, C(t) = of Equation (3) to measure all the offset approxima-
(x(t), y(t)), in the plane, its offset curve Cd (t) by tion errors. This provides not only a global bound
∗ IEEE Computer Graphics and Applications, Vol. 17, for each method, but also an equal basis for the com-
No. 3, pp. 62–71, May/June 1997 parison of different methods.

1
 Evolute
The evolute of C(t) is defined as:

N (t) (a)
E(t) = C(t) + , E(t)
κ(t)

where κ(t) is the curvature of C(t) = (x(t), y(t)):

x (t)y  (t) − x (t)y  (t)

κ(t) = .
(x (t)2 + y  (t)2 )3/2 C(t)
That is, E(t) is a variable radius offset with offset radius
1
d(t) = κ(t) . Figure 1 shows two examples of evolute
curves. Quite surprisingly, E(t) is a rational curve, pro-
vided C(t) is a rational or polynomial curve:

N (t)
E(t) = C(t) +
κ(t) 20 × E(t)
(y
(t),−x
(t))
(x
(t)2 +y
(t)2 )1/2
= C(t) + x
(t)y

(t)−x

(t)y
(t)
(x
(t)2 +y
(t)2 )3/2 (b)
x (t)2 + y  (t)2
= C(t) +  · (y  (t), −x (t)). C(t)
x (t)y  (t) − x (t)y  (t)

In contrast to the offset computation in Equation (1),

there is no square root term in the representation of
E(t). In Figure 1, the curves and their evolutes are both
Figure 1: In (a), a B-spline curve, C(t), in light
represented as B-spline curves. curve, is shown along with its evolute, E(t), in bold
curve. In (b), the evolute E(t) for a cubic polyno-
mial approximation of a circle, C(t), is shown. E(t)
is scaled up by a factor of 20.

Qualitative Comparisons high degree curves, this simple method has a similar
performance to that of Cobb [9].
Control Polygon Based Methods Coquillart [10] solved the under-estimating prob-
lem. The distance between Pi and C(ξi ), and the
Let C(t) be a B-spline curve with k control points curvature κ(ξi ) of C(t) at ξi are taken into account.
of order n and defined over a knot sequence τ = Numerical approximation is also taken to compute
{ti } , 0 ≤ i < n + k. The i-th node parameter value the closest point of C(t) to the control point Pi , while
ξi of C(t) is defined as: using C(ξi ) as an initial solution. With all these en-
i+n−1 hancements, Coquillart [10] was able to offset the
j=i+1 tj linear and circular segments exactly.
ξi = , (7)
n−1 Elber and Cohen [11] took a different approach
that exactly computes the offsets of linear and cir-
for 0 ≤ i < k. Hence, a node parameter value is an cular elements. Using the values of (t) (in Equa-
average of n−1 consecutive knots in τ . Each control tion (3)) at t = ξ0 , . . . , ξn , the error in the neigh-
point, Pi , of C(t), is associated with one node, ξi . borhood of each control point, Pi , is estimated and
C(ξi ) is typically close to Pi ; however, it is not the used to adjust the translational distance applied to
closest point of C(t) to Pi , in general. Pi . This perturbation based approach is an iter-
Cobb [9] translated each control point, Pi , by d · ative method that converges to the exact circular
N (ξi ), whereas Tiller and Hanson [6] translated each offset segment. For general curves, when the re-
edge of the control polygon into the edge normal sult of Cobb [9] is used as an initial solution, the
direction by a distance d. Unfortunately, Cobb [9] perturbation process typically reduces the offset ap-
always under-estimates the offset; i.e., (t) ≤ 0, for proximation error of [9] by an order of magnitude.
all t. (For the proof and related issues, see Sidebar In principle, this method can be applied to any off-
on Under and Over-Estimation.) set approximation method that produces piecewise
Tiller and Hanson [6] do not under-estimate the polynomial curves.
offset curve. In addition to computing the exact lin- Most traditional techniques subdivide C(t) at the
ear and circular offset curves, their method outper- middle of the parametric domain; however, a bet-
forms all the other methods for the case of offsetting ter candidate is the parameter of the location with
(piecewise) quadratic curves. However, for offsetting the maximum error. Since (t) represents the exact

2
 Symbolic Computation The product of two Bernstein Bézier basis functions is:
   
In this article, we have employed (t) (in Equa- k i l j
tion (3)) and m (t) (in Equation (11)) to estimate Bik (t)Bjl (t) = t (1 − t)k−i t (1 − t)l−j
i j
the offset approximation error. Furthermore, we   
also need to compute the composition of U (s(t)) (in k l i+j
= t (1 − t)k+l−i−j
Equation (10)). The symbolic computation of these i j
equations involves the difference, product, and sum k l 
m
of (piecewise) scalar polynomial or n
rational curves. = k+l Bi+j
i j k+l
(t). (5)
Let C1 (t) = i=0 Pi Bi,τ (t) and C2 (t) = j=0 Pj Bj,η (t)
i+j
be two (piecewise) polynomial regular parametric curves,
in the Bézier or NURBS representations. The computa- Therefore, we have:
tion of C1 (t) ± C2 (t) can be accomplished by elevating
both C1 (t) and C2 (t) to a common function space. The  m
m
 n

order of the common function space is equal to the max- C 1 (t)C 2 (t) = P i Bi (t) Pj Bjn (t)
imal order of C1 (t) and C2 (t). If either C1 (t) or C2 (t) is i=0 j=0
a B-spline curve, the common function space is defined  m
n
by considering both knot vectors τ and η and preserving = Pi Pj Bim (t)Bjn (t)
the lowest degree of continuity at each knot. Once the i=0 j=0
common function space is determined, both C1 (t) and mn
C2 (t) are elevated to this space via degree raising and  m  n

Pi Pj m+n Bi+j
i j m+n
= (t)
refinement. (See [8] for more details as well as the ex-
i=0 j=0 i+j
tension to rationals.)

m+n
The computation of C1 (t)C2 (t) is somewhat more in- = Qk Bkm+n (t), (6)
volved. Here, we consider only the case of Bézier poly- k=0
nomial curves. (See [8] for the more general cases of
piecewise polynomials and rationals.) The i-th Bern- where Qk accumulates all the combinatorial terms
stein Bézier basis function of degree k is defined by: (mi)(nj)
Pi Pj m+n , for k = i + j. Hence, C1 (t)C2 (t) is rep-
  ( i+j )
k i resented as a Bézier polynomial curve of degree m + n.
Bik (t) = t (1 − t)k−i . (4)
i

squared error function, one can find the parameter efficiency, only finite samples of Cd (t) are used in the
location of the maximal error and subdivide C(t) optimization.
there. Alternatively, instead of subdividing C(t), Hoschek and Wissel [2] used a general non-linear
one can insert new knots into C(t) at the param- optimization technique to approximate a high degree
eter locations with error larger than the allowed tol- spline curve with low degree spline curves. They
erance. Elber and Cohen [7] took this refinement applied the same technique to approximate an exact
approach. offset curve with low degree spline curves.
The least squares based methods [1, 2] are ex-
Interpolation Methods pected to perform better than other methods. How-
ever, there still remains a question about whether
Klass [12] used a cubic Hermite curve to approxi- the least squares solution is optimal when searching
mate the offset curve. The cubic Hermite curve is for the smallest number of (say cubic) curve seg-
determined by interpolating the position and veloc- ments to approximate an exact offset curve. The
ity of the exact offset curve at both endpoints. The answer is negative, in general. In the special case
numerical approximation procedure of Klass [12] is of offsetting quadratic curves, the simple method of
quite unstable when the offset curve becomes almost Tiller and Hanson [6] performs much better than the
flat. Therefore, instead of using the original algo- least squares methods [1, 2].
rithm [12], we compute the first derivative of the off-
set curve based on the following simple closed form It is important to question how this unexpected re-
equation (see also [3]): sult could be obtained. The answer might be quite
useful in improving the accuracy of offset approxi-
Cd
(t) = (1 + d · κ(t))C
(t), (8) mation. The least squares solution optimizes the in-
tegrated summation of the least squares errors in the
where κ(t) is the curvature of C(t). approximation. Therefore, even if a small portion of
Hoschek [1] suggested a least squares solution for the approximation curve has a large error, as long
the determination of Cd
(t) at the curve endpoints. as the rest of the curve tightly approximates the ex-
That is, at each endpoint of Cd (t), the direction of act curve, the overall least squares error can be very
Cd
(t) is maintained to be parallel to C
(t); however, small. That is, the least squares solution provides an
instead of using Equation (8), their lengths are de- optimal solution with respect to an L2 norm. When
termined so that the cubic Hermite curve best fits this L2 optimal solution is further evaluated with re-
Cd (t) in the least squares sense. For computational spect to the L∞ norm (of Equation (3)), the optimal-

3
 Under and Over-Estimation If N (ξi ) = N (ξj ), for some 0 ≤ i, j ≤ n, we have
min V (t) < 1, and this results in an error in the off-
The offset approximation of Cobb [9] is formally defined set approximation. Hence, this method always under-
as follows: estimates the exact offset. Figure 2(a) shows a quartic
Bézier curve C(t) and its offset approximation Cda (t). In
 n
Figure 2(b), the difference vector field D(t) = C(t) −
Cda (t) = (Pi + dN (ξi )) Bi (t) Cda (t) is completely contained in a disk of radius d. All
i=0 the control points of D(t) are on the circumference of
 n n
the disk.
= Pi Bi (t) + d N (ξi )Bi (t)
i=0 i=0 Under-estimation of offsets may lead to undesirable
= C(t) + dV (t). results. For example, in NC machining, the under-
estimation leads to gouging. Assume the under-
where N (ξi )= 1, for i = 0, . . . , n. The vector field estimation of the offset is bounded from below by:
n
curve V (t) = i=0 N (ξi )Bi (t) has all its control points
N (ξi ) on the unit circle S 1 . By the convex hull property, dmin = min(dV (t)).
we have V (t) ≤ 1 and When we translate control point P in the direction of
i
d
C(t) − Cda (t) = dV (t) = dV (t) ≤ d. N (ξi ), by a distance d dmin , the resulting curve com-
pletely over-estimates the exact offset (see Figure 3):
   
 d   d 
(a) C(t) − Cda (t) = d V (t) ≥ 
d V (t)
 = d.
dmin dV (t)
d
One can reduce the relative error in the offset approxima-
Cda (t) tion by alternating the under and over-estimations. This
can be done by adjusting the offset distance at each con-
D(t) trol point appropriately. Figure 4 shows an example of
C(t) this approach. We use the same quartic Bézier curve as
in Figures 2 and 3. The quartic Bézier offset approxima-
(b) tion curve interpolates the exact offset at five discrete lo-
cations, corresponding to the node values, 4i , 0 ≤ i ≤ 4.

d
Figure 2: In (a), an offset approximation Cda (t) com-
puted by translating the control points of the orig-
inal curve C(t) (dashed lines) by an amount equal
to the offset distance will always under-estimate the D(t)
real offset. In (b), D(t) = C(t) − Cda (t) is found to
be fully contained in a circle of the offset radius size,
d. Cda (t)
(b)

Cda (t)
C(t)
D(t) d C(t)

(b) (a)
(a)
Figure 4: In (a), an offset approximation Cda (t) of a
quartic Bézier curve C(t) (dashed lines) is computed
Figure 3: In (a), an offset approximation Cda (t) of a by enforcing Cda (t) to interpolate at five locations on
quartic Bézier curve C(t) (dashed lines) is computed the exact offset curve computed at the node values
by forcing Cda (t) to over-estimate the error. D(t) = on Cda (t). D(t) = C(t) − Cda (t) is shown in (b).
C(t)−Cda (t) is shown in (b). Compare with Figure 2. Compare with Figures 2 and 3.

4
ity is no longer guaranteed. This is an important ob- to rational quadratic curves. (There are some ratio-
servation which suggests possible improvements over nal quadratic curves which have no exact rational
the nearly optimal solutions [1, 2]. parametrization of their offset curves.)
Pham [13] suggested a simple B-spline interpola- One can attempt to globally approximate s(t) by
tion method to approximate the offset curve. Fi- maximizing the constraint energy:
nite sample points are generated on the exact off-
set curve, and they are interpolated by a piecewise t1

C
(t), U
(s(t))
cubic B-spline curve. It is also interesting to note max dt. (10)
s(t) t0 C
(t) U
(s(t))
that this simple method also performs pretty well.
In many examples, its performance is only slightly This approach was taken in Lee et al. [14], in which
worse than and sometimes even better than the local the composition of U (s(t)) = (U ◦ s)(t) is carried
least squares methods [1, 2]. out symbolically [8] (see also Sidebar on Symbolic
Computation).
Circle Approximation Methods The offset approximation in [5] depends on the
method used for the piecewise quadratic approxi-
Assume the base curve C(t), t0 ≤ t ≤ t1 , is a poly- mation to the circle. The error in the offset ap-
nomial curve with no inflection point, and a unit proximation stems only from the quadratic polyno-
circular arc U (s), s0 ≤ s ≤ s1 , is parameterized so mial approximation of the circular arc, scaled by
that: the offset radius d. Lee et al. [5] used five differ-
ent circle approximation methods. Two of the five
C
(t0 )  U
(s0 ) and C
(t1 )  U
(s1 ). methods generate G1 -continuous circle approxima-
tions with quadratic Bézier curve segments. In the
If one can compute a reparameterization s(t) so that:
first method, the unit circle U (s) is totally contained
C
(t)  U
(s(t)), in the closed convex region bounded by the quadratic
curve segments. The corresponding offset curve ap-
the offset curve is then computable as: proximation completely over-estimates the exact off-
set curve. In the second method, the quadratic curve
Cd (t) = C(t) + d · U (s(t)). (9) segments pass through both the interior and exte-
rior of the unit circle U (s). Therefore, the offset
The offset curve is not a polynomial or ratio- approximation curve both over and under-estimates
nal curve; therefore, we have to approximate U (s) the exact offset curve, while the approximation er-
and/or s(t) by a polynomial or rational. ror is reduced by half from the over-estimating first
Lee et al. [5] approximated the unit circle U (s) method. We use this second method, referred to as
with piecewise quadratic polynomial curve segments Lee in the next section, for comparison with other
Qj (s), j = 0, . . . , n. The Hodograph curve Q
j (s) is methods.
piecewise linear; therefore, the parallel constraint: In contrast, Lee et al. [14] approximated the
reparametrization s(t), while representing the cir-
C
(t)  Q
(s(t)) cle U (s) exactly by a rational quadratic curve. In
this method, the error stems only from the inac-
provides the reparameterization of s(t) as a rational curate reparameterization function s(t), which re-
polynomial of degree d − 1, where d is the degree sults in a mismatch in the parallel constraint of
of C(t). For a polynomial curve C(t) of degree d, C
(t)  U
(s(t)). To the authors’ knowledge, this is
the resulting offset approximation (computed as in the only offset approximation method for which the
Equation (9)) is a rational curve of degree 3d − 2. use of (t) is completely ineffective in the global error
(For a rational curve C(t) of degree d, the offset bound. The term (t) is always equal to zero. Lee
approximation curve is of degree 5d − 4.) et al. [14] measured the angular deviation of U (s(t))
For a quadratic polynomial curve C(t), this tech- from the exact offset direction N (t) by using the fol-
nique also provides a simple method to represent the lowing error function:
exact offset curve Cd (t) as a rational curve of degree 2
six. Assume that the exact circle, Q(s), 0 ≤ s ≤ 1,
C(t) − Cda (t), C
(t)
m (t) = 2 . (11)
is represented by a rational quadratic curve. Then, d2 C
(t)
the parallel constraint:
The error is equal to zero if orthogonality is pre-
C
(t(s))  Q
(s) served. Otherwise, it is equal to cos2 θ, where θ is
the angle between U (s(t)) and C
(t).
provides the reparameterization of t(s) as a rational
polynomial of degree two. Therefore, the exact offset
curve Cd (t) is a rational curve of degree six. Even Quantitative Comparisons
with the high degree of six, the exact offset capabil-
ity suggests this method as the method of choice for We consider how efficiently each method approxi-
offsetting (piecewise) quadratic polynomial curves, mates the offset curve, given a prescribed tolerance.
especially for high precision offset approximation. Several examples of Bézier and B-spline curves are
However, this exact offset capability does not extend given, both in polynomial and rational forms. All

5
the methods (compared in this article) are imple- Traditionally, the offset approximation error has
mented using the IRIT [15] solid modeling system been measured only at finite sample points of C(t)
that has been developed at the Technion, Israel, and Cda (t). As previously mentioned, we adopt the
with some of the offset approximation methods im- symbolic approach of error estimation [7]. There-
plemented at POSTECH, Korea. fore, we can provide an L∞ global upper bound on
the offset approximation error for each of the meth-
Methods under Comparison ods under comparison. The global error bound is
derived by symbolically computing the error func-
We quantitatively compare the following methods: tion (t) (in Equation (3)). Because of the convex
hull property of the Bézier or NURBS representation
• Cob: The simple method of Cobb [9] in which of the scalar function (t), we can easily determine
the control points are translated by the offset its upper bound as the maximum coefficient of the
distance. This method always creates under- Bézier or NURBS basis functions.
estimated offsets. (See Sidebar on Under and
Over-Estimation.)
Comparison Results and Remarks
• Elb: An adaptive offset refinement approach
that was suggested in Elber and Cohen [7]. In- Figures 5–6 show the results of offsetting (piecewise)
stead of subdividing the base curve, whenever quadratic curves. We compare the number of control
the error is too large, the offset curve is refined points with respect to the accuracy of offset approxi-
to yield a better approximation (by using more mation. In these examples, the method of Tiller and
control points). The error analysis of (t) is ex- Hanson [6] outperforms all the other methods even
ploited to find better candidate locations for re- if the base curve has sharp corners with high cur-
finement. This method also under-estimates the vature (Figure 6). This surprising result has never
offset curves. been reported in the literature. In fact, we have as-
sumed that the least squares methods provide near
• Coq: The enhancement suggested by Coquil- optimal solutions to the offset approximation prob-
lart [10] that allows the exact offset represen- lem. However, the superior performance of Tiller
tation of linear as well as circular segments. and Hanson [6] tells us that this is not true, in gen-
• Til: The method of Tiller and Hanson [6] in eral. At this moment, we have no clear explanation
which the edges of the control polygon, rather of the underlying geometric properties of this un-
than the control points, are translated. usual phenomenon. Nevertheless, it is not difficult
to point out at least two possible sources of the non-
• Klass: The method of Klass [12] that fits a cu- optimality in the current least squares methods:
bic Bézier curve to each offset curve segment to
interpolate the boundary points and velocities • As discussed above, the least squares methods
of the exact offset curve. provide the optimal solutions in an L2 norm,
which may be quite different from the optimal
• Pham: The method of Pham [13] that interpo- solutions in an L∞ norm.
lates a sequence of finite sample points on the
exact offset curve by a non-uniform piecewise • The least squares optimization procedure solves
cubic B-spline curve. (The original method of an over-constrained problem, the solution of
Pham [13] uses a uniform B-spline curve; how- which depends on the distribution of finite sam-
ever, we have modified the method.) Whenever ple points on the offset curve. In some degen-
the offset approximation error is larger than the erate cases, the least squares solution may have
prescribed tolerance, more sample offset points large variation depending on the distribution of
are used for a better fit. data points.
Further investigations are required to eliminate these
• Lst: The global least squares approximation
limitations, and this may advance the state-of-the-
that fits a uniform piecewise cubic B-spline
art of offset curve approximation.
curve to the offset curve. Whenever the off-
Figures 7, 9, and 10 show other examples of offset-
set approximation error is larger than the pre-
ting (piecewise) cubic B-spline curves. Throughout
scribed tolerance, more control points are used
the conducted tests, we have observed the following
for a better fit.
consistent results:
• Hos: The least squares method of Hoschek [1, 2] • The under-estimating offset approximation
that fits a cubic Bézier curve to each offset curve method, Cob, is doing quite poorly.
segment. Whenever the error is larger than the
tolerance, the base curve is subdivided into two • The adaptive offset refinement approach, Elb, is
subsegments and the offset approximation is re- better than Cob, especially when high precision
peated recursively. is desired.
• Lee: The approach suggested by Lee et al. [5] • In the case of offsetting (piecewise) quadratic
that approximates the curve of the convolution curve segments, the simple method of Tiller and
between C(t) and the offset circle d · U (s) of Hanson [6] outperforms all the other methods,
radius d. especially when high precision is required.

6
  Cob Elb Coq Til Kla Phm Lst Hos Lee
10−0 8 8 8 8 30 8 8 8 33
10−1 15 8 19 11 93 10 11 15 33
10−2 41 29 37 21 132 22 39 35 45
10−3 115 92 119 39 185 52 79 63 73
10−4 363 313 357 71 267 130 161 131 97
10−5 1191 948 1013 127 451 270 332 277 157
 Cob Elb Coq Til Kla Phm Lst Hos Lee
10−0 12 12 29 73 21 12 30 12 93
10−1 127 22 127 95 167 78 58 129 101
Cob 10−2 223 162 219 155 239 140 362 185 169
10−3 527 436 591 217 399 268 654 337 237
1 Elb
10−4 1497 1316 1803 313 783 530 1234 659 397
Coq
10−5 4763 3878 5587 505 1651 1162 1650 1367 681
Til
10;1 Kla
Phm Phm
Offset Error

10;2 Lst
Hos Cob
Lee 1 Elb
10;3 Coq
Til
10;1
10;4 Kla
Phm
Offset Error

Cob 10;2 Lst

10;5 Til Kla
Lee Hos Lst Elb Coq Hos
Lee
10;3
10 100 1000
Number of control points 10;4 Kla
Lst Coq
10;5 Til LeePhm Hos Elb
Cob
Figure 5: An offset approximation (light curve) for a
quadratic polynomial B-spline curve with eight con- 10 100 1000
trol points. Number of control points

• In the case of offsetting (piecewise) cubic curve Figure 6: An offset approximation (light curve) for
segments, the least squares methods, Lst and a quadratic polynomial with sharp corners.
Hos, perform much better than all the other
methods, especially when high precision is re-
quired. that is available. For example, for data storage sav-
ing, we can store only the subdivision locations of
• In many examples, the local cubic B-spline in- the curve, instead of all the control points that are
terpolation method, Pham, has similar – and generated. We then use the local methods to gen-
sometimes even better – performance to Hos. erate the control points (on the fly) by considering
However, its performance deteriorates when the only local data. In this case, Hos and Pham are the
base curve has a radius of curvature similar to methods of choice.
the offset radius. As discussed in the above observation, the perfor-
mance of Pham is closely related to the radius of cur-
• The only geometrical method that approaches vature of the base curve. When the radius of curva-
the efficiency of the least squares methods is Lee ture is similar to the offset radius, the sample offset
followed not so closely by Elb. points are clustered together. The B-spline interpo-
lation of these clustered points generates undulation,
For the case of offsetting (piecewise) cubic curves, which is the main source of large approximation er-
the global least squares method, Lst, outperforms ror. In this case, it is better to use a smaller number
all the other methods, while it is closely followed of data points for the interpolation. Figures 11–12
by the local least squares method, Hos, and also by exemplify this phenomenon by comparing the rel-
the local cubic B-spline interpolation method, Pham. ative performances of different offset approximation
Many practical situations require the production of methods. Given a fixed base curve, by increasing the
local optimal solutions based only on the local data offset radius gradually, we can observe that Pham’s

7
  Cob Elb Coq Til Kla Phm Lst Hos Lee
 Cob Elb Coq Til Kla Phm Lst Hos Lee 10−0 9 9 9 9 10 9 9 9 25
10−0 4 4 4 7 4 4 4 4 15 10−1 17 13 9 9 17 9 9 9 25
10−1 10 9 10 10 13 13 8 10 15 10−2 33 53 9 9 49 9 13 17 61
10−2 31 22 25 22 22 19 17 22 36 10−3 129 69 9 9 113 47 24 49 73
10−3 73 53 58 73 43 31 26 31 43 10−4 497 261 9 9 417 107 46 97 121
10−4 226 156 175 226 76 79 42 64 78 10−5 1025 524 9 9 1345 221 98 209 229
10−5 679 490 538 715 139 157 68 106 127

Cob
Cob 1 Elb
1 Elb Coq
Coq Til
Til 10;1 Kla
10;1 Kla Phm
Offset Error

Phm 10;2 Lst

Offset Error

10;2 Lst Hos

Hos Lee
10;3
Lee
10;3
10;4
10;4
Lee Kla
Til 10;5 Lst Hos Phm Elb
Hos Phm Cob
10;5 Til
Lst Lee Kla Coq Cob
Coq
Elb
10 100 1000
10 100 1000
Number of control points
Number of control points

Figure 8: An offset approximation (light curve) for

Figure 7: An offset approximation (light curve) for a rational quadratic B-spline circle with nine control
a polynomial cubic Bézier curve. points.

method has the worst relative performance near the cussed above. The limitation resulting from the L2
offset distance which starts to develop cusps in the norm seems more serious. To resolve this problem,
offset curve. For a better visualization of the rela- we need to develop an efficient algorithm to compute
tive performance, only four methods are shown in and optimize the L∞ norm of the offset approxima-
the graphs of Figures 11–12. tion error; that is, the maximum of the error function
There is another source of undulation we have to (t) (in Equation (3)):
consider in Pham’s method. That is, the mismatch

2
in speeds between the two curves, i.e., the base curve max C(t) − Cda (t) − d2 , (12)
and the offset curve, also cause deterioration in the t
quality of the offset approximation. For the imple-
or a more precise geometric distance measure based
mentation of Pham, we use a non-uniform cubic B-
on the following Hausdorff metric:
spline curve, in which the data points of the offset in-
herit the knot values of the base curve points. When 

2
the offset data points are clustered, their knot val- max max min C(s) − Cda (t) − d2 , (13)
t s
ues are much sparser compared with the offset curve

2
length. This unnatural assignment of knot values max min C(s) − Cda (t) − d2
s t
generates undulation. Therefore, for a better offset
approximation, it is also important to rearrange the where s is assumed to be a local perturbation of the
knot values of the offset data points. parameter t.
The superior performance (in the quadratic case) Note that the method of Cobb [9] essentially mod-
of the simple method, Til, suggests the possibility els the L∞ norm of Equation (12) in terms of the
of improvement over the current least squares meth- maximum and minimum magnitudes of the distance
ods. This improvement may be achieved by resolv- curve, D(t) = C(t) − Cda (t), in Figures 2–4. Let’s
ing the limitations of least squares methods as dis- consider a variant of Cobb [9] which uses the least

8
  Cob Elb Coq Til Kla Phm Lst Hos Lee
10−0 13 13 13 13 386 13 13 13 99
10−1 27 16 24 13 415 16 14 27 99
10−2 69 67 60 51 418 67 37 57 127
10−3 177 236 165 171 445 112 66 99 162
10−4 543 380 525 546 496 181 109 183 246
10−5 1746 1129 1518 1788 607 295 180 312 365  Cob Elb Coq Til Kla Phm Lst Hos Lee
10−0 7 7 7 7 13 7 7 7 50
10−1 9 7 13 7 13 7 7 9 57
10−2 25 27 49 25 25 19 10 25 71
Cob 10−3 97 143 145 97 49 52 19 49 99
10−4 385 147 433 385 73 82 35 49 148
1 Elb
10−5 1033 742 1537 1081 121 121 69 97 239
Coq
Til
10;1 Kla
Phm
Offset Error

10;2 Lst Cob

Hos 1 Elb
Lee Coq
10;3 Til
10;1 Kla
10;4 Phm
Offset Error

10;2 Lst
Lee Cob Hos
10;5 Lst
Phm Hos Kla Elb Coq Til Lee
10;3

10 100 1000 10;4

Number of control points Phm
10;5 Lst Kla Elb CobTil Coq
Lee
Hos
Figure 9: An offset approximation (light curve) for
10 100 1000
a cubic polynomial B-spline curve with 13 control
points. Number of control points

Figure 10: An offset approximation (light curve) for

squares technique to optimize the offset distance at a cubic polynomial periodic B-spline curve with four
each control point so that the distance curve D(t) is control points.
a best fit to the offset circle of radius d. This method
measures the offset error in the L∞ sense of Equa-
tion (12). (Note that the approximation of D(t) to sentations of the offset approximation error (in cer-
an offset circle still has the limitation of L2 norm.) tain L∞ norms), whereas none of the current least
Although we have not provided all the details of Lee squares methods have such geometric interpretation
in this article, the method of Lee et al. [5] actually of their respective error bounds. We also pointed out
measures the offset approximation error under the two limitations of the current least squares meth-
L∞ norm of Equation (13), which is more precise ods: (i) the L2 norm employed in these methods
than the L∞ norm of Equation (12). We expect and (ii) the dependency on the finite sample points
that future offset approximation techniques (while used in the optimization. The B-spline interpola-
incorporating these L∞ norms into their optimiza- tion method also needs further investigation to elim-
tion procedures) may provide more accurate results inate the curve undulation resulting from the curve
than the current least squares methods. speed mismatch between the base curve and the off-
set curve. In this respect, there are still many ways
to improve the current state-of-the-art of offset curve
Conclusion approximation. We hope that the experimental re-
sults reported in this article and the related remarks
We have compared several contemporary offset ap- will serve as useful guidelines for future research.
proximation techniques for freeform curves in the
plane. In general, the least squares methods per-
form very well. However, for the case of offsetting
quadratic curves, the simple method of Tiller and References
Hanson [6] is the method of choice. Therefore, the
least squares methods need further improvement to [1] Hoschek, J., (1988), “Spline Approximation of
produce near-optimal solutions in all cases. Some of Offset Curves,” Computer Aided Geometric De-
the current methods [5, 7, 9] have geometric repre- sign, Vol. 5, pp. 33–40.

9
 d Cob Elb Coq Til Kla Phm Lst Hos Lee
0.1 279 256 153 279 127 178 115 129 190
0.2 369 337 195 351 163 181 115 165 197
0.3 483 424 255 483 163 196 127 171 204
0.4 549 499 267 579 175 202 139 189 204
0.5 627 547 303 621 187 175 151 207 218
0.6 663 580 333 657 199 187 163 213 232

d Cob Elb Coq Til Kla Phm Lst Hos Lee 0.6
0.1 531 483 417 519 217 198 181 237 288 Cob
0.2 765 660 477 759 253 258 217 279 330 0.55
0.3 909 867 723 927 307 333 217 297 351 Elb
0.4 1029 933 783 1029 325 333 253 315 358 0.5 Coq
0.5 1113 978 843 1125 325 396 253 327 379
0.6 1371 1197 867 1377 325 399 271 327 400
Til
0.7 1431 1269 903 1449 325 366 307 345 442 0.45 Kla
0.8 1503 1344 921 1515 361 390 307 345 442 Offset Distance Phm
0.9 1569 1416 927 1569 361 423 325 363 463 0.4
1.0 1647 1491 945 1695 379 423 325 375 463 Lst
1.1 1749 1641 1095 1761 397 429 325 399 463
0.35 Hos
1.2 1821 1740 1401 1845 397 447 325 399 463
Lee
0.3
0.25
1.2 0.2
Cob 0.15
Elb
1 Coq 0.1
Til 200 500 1000
Kla Number of control points
Offset Distance

0.8
Phm Figure 12: Pham’s method has the worst perfor-
Lst
Hos mance for the offset distances around 0.4. Base curve
0.6
Lee is a cubic B-spline curve. Tolerance of 0.001 is used
0.4
for offset approximation error.

0.2
[5] Lee, I.-K., Kim, M.-S., and Elber, G., (1995),
0
“Planar Curve Offset Based on Circle Approxi-
200 1000 2000 mation,” to appear in Computer-Aided Design.
Number of control points
Figure 11: Pham’s method has the worst relative [6] Tiller, W., and Hanson, E., (1984), “Offsets
performance for the offset distances between 0.4 and of Two Dimensional Profiles,” IEEE Computer
0.6. Base curve is a cubic B-spline curve. Tolerance Graphics & Application, Vol. 4, pp. 36–46.
of 0.0001 is used for offset approximation error.
[7] Elber, G., and Cohen, E., (1991), “Error
Bounded Variable Distance Offset Operator for
[2] Hoschek, J., and Wissel, N., (1988), “Opti- Free Form Curves and Surfaces,” International
mal Approximate Conversion of Spline Curves Journal of Computational Geometry and Appli-
and Spline Approximation of Offset Curves,” cations, Vol. 1, No. 1, pp. 67–78.
Computer-Aided Design, Vol. 20, No. 8, [8] Elber, G., (1992). “Free Form Surface Analysis
pp. 475–483. using a Hybrid of Symbolic and Numeric Com-
putation,” Ph.D. thesis, University of Utah,
[3] Farouki, R., and Neff, C., (1990), “Analytic Computer Science Department.
Properties of Plane Offset Curves” & “Alge-
braic Properties of Plane Offset Curves,” Com- [9] Cobb, B., (1984), Design of Sculptured Surfaces
puter Aided Geometric Design, Vol. 7, pp. 83–99 Using The B-spline Representation, Ph.D. the-
& pp. 101–127. sis, University of Utah, Computer Science De-
partment.
[4] Farouki, R., and Sakkalis, T., (1990), [10] Coquillart, S., (1987), “Computing Offset
“Pythagorean Hodograph,” IBM J. Res. De- of B-spline Curves,” Computer-Aided Design,
velop., 34, pp 736-752. Vol. 19, No. 6, pp. 305–309.

10
[11] Elber, G., and Cohen, E., (1992), “Offset Ap-
proximation Improvement by Control Points
Perturbation.” Mathematical Methods in Com-
puter Aided Geometric Design II, Tom Lyche
and Larry L. Schumaker, Academic Press, pp
229-237.
[12] Klass, R., (1983), “An Offset Spline Approx-
imation for Plane Cubic Splines,” Computer-
Aided Design, Vol. 15, No. 4, pp. 297–299.
[13] Pham, B., (1988), “Offset Approximation of
Uniform B-splines,” Computer-Aided Design,
Vol. 20, No. 8, pp. 471–474.
[14] Lee, I.-K., Kim, M.-S., and Elber, G.,
(1995), “Planar Curve Offset by Curve Tangent
Matching,” Technical Report, CS-CG-TR-95-
007, Dept. of Computer Science, POSTECH,
November, 1995.
[15] IRIT solid modeller (1995), IRIT 5.0 User’s
Manual, Technion.

11