TIGHT LINEAR ENVELOPES FOR SPLINES

DAVID LUTTERKORT AND JÖRG PETERS

Abstract. A sharp bound on the distance between a spline and its B-spline control polygon is derived. The bound yields a piecewise linear envelope enclosing spline and polygon. This envelope is particularly simple for uniform splines and splines in Bernstein-Bézier form and shrinks by a factor of 4 for each uniform subdivision step. The envelope can be easily and efficiently implemented due to its explicit and constructive nature.

1. Introduction & main results

B-splines are routinely used as approximating functions and to represent geometry for numerical calculations. A central feature that allows reasoning about these nonlinear piecewise polynomials is the fact that the spline is closely outlined by its control polygon, line segments connecting the control points. The efficiency of many applications, for example rendering or intersection testing, hinges on a tight quantitative estimate of the maximal distance of the spline from its control polygon. However, apart from the convex hull and the min–max bound, no quantitive estimates exist to date.

Figure 1. A quadratic spline over the knot sequence (0, 0, 0, 1, 3, 4, 7, 8, 8, 8) with control points (0, 2, 4, 2, 0, 2, 3). The spline is shown in black. The envelope according to Corollary 2 is shown in grey. The control polygon is covered by the envelope.

This paper shows how to bound the maximal distance between a spline and its B–spline control polygon in terms of second differences of the control points and linear interpolants of special piecewise convex and nonnegative splines that depend only on the knot sequence. The bounds yield piecewise linear envelopes consisting of a positive and a negative offset of the control polygon (cf. Figures 1 and 2).

Date: October 8, 1999.

To appear in Numerische Mathematik.

In most practical applications, the control points are varied far more often than the knot sequence. For fixed knot sequences, including the important cases of Bernstein polynomials and uniform splines, the bounds require only forming the scalar product of the vector of second differences of the control points and a precomputed vector.

The envelopes are as narrow as possible at each control point that corresponds to a convex or concave polynomial piece: one envelope polyline matches that control point while the other envelope polyline touches the spline. This ensures quadratic convergence of the envelope to the spline under subdivision as the number of inflection points of a spline stays fixed while more and more pieces without inflection points are produced.

The computation of the envelopes can be further simplified to yield coarser envelopes expressed in terms of second differences of the control polygon and the values of one nonnegative, convex spline that depends only on the knot sequence.

Figure 2. A quintic spline and its envelope according to Corollary 2 . The knots are at (0, 1, 3, 7) and the control points are (0, 1, 2, 0, 0, 1, 1, 0). The first and last knot have multiplicity 6.

2. Notation

A piecewise polynomial p of degree d is in B–Spline form if

p(t) = ∑_{k∈ℤ} b_{k}N_{k}^{d}(t)

where the control points b_{k} are real numbers and the B–Spline basis functions N_{k}^{d} are defined recursively based on a nondecreasing sequence of real numbers, the knots t_{k} [dB93]. We may assume that p is at least continuous since otherwise we can treat p as two seperate splines. This implies that any knot can appear with multiplicity at most d, except for the first and last knot which can have multiplicity d + 1. Therefore the Greville abscissae t_{k}^{∗},

t_{k}^{∗} := \frac{1}{d} ∑_{i=k+1}^{k+d} t_{i},

are distinct. We denote the line segment from (t_{k}^{∗}, a_{1}) to (t_{k+1}^{∗}, a_{2}) by

L_{k}(t | a_{1}, a_{2}) = a_{1} \frac{t_{k+1}^{∗} − t}{t_{k+1}^{∗} − t_{k}^{∗}} + a_{2} \frac{t − t_{k}^{∗}}{t_{k+1}^{∗} − t_{k}^{∗}} .

and the linear interpolant of the function f at t_{k}^{∗} and t_{k+1}^{∗} as L_{k} (f) = L_{k}( · | f(t_{k}^{∗}), f(t_{k+1}^{∗})). The control polygon ℓ(p) of p is the piecewise linear interpolant to control points (t_{k}^{∗}, b_{k}). That is, over the interval [t_{k}^{∗}, t_{k+1}^{∗}] the k–th piece ℓ_{k}(p) of the control polygon ℓ(p) is given by

ℓ_{k}(p)(t) = L_{k}(t | b_{k}, b_{k+1}).

We abbreviate ℓ(p) to ℓ if the spline p is understood from the context. The first and second divided differences of b are

b′_{i} = \frac{b_{i} − b_{i−1}}{t_{i}^{∗} − t_{i−1}^{∗}} b′′_{i} = (d − 1)\frac{b′_{i} − b′_{i−1}}{t_{i+d−1} − t_{i}} .

They are the B–spline control points of the first and second derivatives of p. The centered second differences of b are defined as

Δ_{2}b_{i} = b′_{i+1} − b′_{i}.

Only finitely many B–spline basis functions have support on some part of [t_{k}^{∗}, t_{k+1}^{∗}]. Let \underline{k} and \overline{k} be the index of the first and the last B–spline basis function that are nonzero on some part of [t_{k}^{∗}, t_{k+1}^{∗}]. There will be more than d + 1 such basis functions if [t_{k}^{∗}, t_{k+1}^{∗}] contains one or more knots in its interior. Since t_{k}^{∗} ≤ t_{k+d} ≤ t_{k+d+1} ≤ t_{k+1}^{∗}, \underline{k} and \overline{k} are related to k by \underline{k} ≤ k < \overline{k}.

3. Tight envelopes for arbitrary knot sequences

The key to deriving the bounds in this paper is to factor the difference between a spline and its B–spline control polygon into two parts: the second differences of the control polygon and nonnegative splines β_{ki} that only depend on the knot sequence. The β_{ki} are piecewise convex and therefore well suited for piecewise linear approximations. This observation is made precise in the following theorem.

Theorem 1. Let t ∈ [t_{k}^{∗}, t_{k+1}^{∗}] and functions β_{ki} defined as

β_{ki} = \begin{cases}∑\overline{k} ; j=i(t_{j}^{∗} − t_{i}^{∗})N_{j}^{d} & i > k \\ ∑_{j=\underline{k}}^{i}(t_{i}^{∗} − t_{j}^{∗})N_{j}^{d} & i ≤ k. \end{cases} (3.1)

The difference between the spline p and its B–spline control polygon ℓ is

p − ℓ = ∑_{i=\underline{k}}^{\overline{k}} Δ_{2}b_{i} β_{ki}. (3.2)

The functions β_{ki} are nonnegative and convex.

Proof. We write p − ℓ_{k} over [t_{k}^{∗}, t_{k+1}^{∗}] as

∑_{i} b_{i} α_{ki} = ∑_{i} b_{i} (N_{i}^{d}(t) − L_{k}(t | δ_{ik}, δ_{i,k+1})) ,

where δ_{ik} = 1 if i = k and 0 otherwise. Only the α_{ki} with \underline{k} ≤ i ≤ \overline{k} can be nonzero on [t_{k}^{∗}, t_{k+1}^{∗}].

We show that α_{ki} = Δ_{2}β_{ki}: the partition of unity ∑_{i} N_{i}^{d} = 1 implies that ∑_{i} α_{ki} = 0 and the linear precision of B–Splines, ∑_{i} t_{i}^{∗}N_{i}^{d} = t implies on the interval [t_{k}^{∗}, t_{k+1}^{∗}] that ∑_{i} t_{i}^{∗}α_{ki} = 0. Hence, for any i, ∑\overline{k} ; j=\underline{k}(t_{j}^{∗} − t_{i}^{∗})α_{kj} = 0.

For i > k,

β_{ki} = ∑_{j=i+1}^{\overline{k}}(t_{j}^{∗} − t_{i}^{∗})N_{j}^{d} − ∑_{j=\underline{k}}^{\overline{k}}(t_{j}^{∗} − t_{i}^{∗})α_{kj} = ∑_{j=\underline{k}}^{i}(t_{i}^{∗} − t_{j}^{∗})α_{kj}

so that β_{ki} = ∑_{j=\underline{k}}^{i}(t_{i}^{∗} − t_{j}^{∗})α_{kj} for any i. It is now straightforward to verify that Δ_{2}β_{ki} = α_{ki}. Summation by parts then completes the proof of (3.2),

p − ℓ_{k} = ∑_{i=\underline{k}}^{\overline{k}} b_{i} α_{ki} = ∑_{i=\underline{k}}^{\overline{k}} b_{i} Δ_{2}β_{ki} = ∑_{i=\underline{k}}^{\overline{k}} Δ_{2}b_{i} β_{ki}.

The functions β_{ki} are nonnegative since their B–spline coefficients are nonnegative by (3.1).

The convexity of the β_{ki} over [t_{k}^{∗}, t_{k+1}^{∗}] follows from the convexity of their B– spline control polygons: for i > k, the part of the control polygon of β_{ki} that influences β_{ki} over [t_{k}^{∗}, t_{k+1}^{∗}] lies on the function max{· − t_{i}^{∗}, 0} while for i ≤ k it lies on max{t_{i}^{∗} − ·, 0}. In both cases, the control polygon of β_{ki}, and hence β_{ki}, is nonnegative and convex.

The characterization of p−ℓ from Theorem 1 gives us a piecewise linear envelope for p that improves in practice on the convex hull, for example for the splines in Figures 1 and 2.

Corollary 2. Over the interval [t_{k}^{∗}, t_{k+1}^{∗}], the spline p is enveloped by

ℓ + L_{k} (∑_{i=\underline{k}}^{\overline{k}} Δ_{2}^{−}b_{i} β_{ki}) ≤ p ≤ ℓ + L_{k} (∑_{i=\underline{k}}^{\overline{k}} Δ_{2}^{+}b_{i} β_{ki}) , (3.3)

where Δ_{2}^{+}b_{i} = max{Δ_{2}b_{i}, 0} and Δ_{2}^{−}b_{i} = min{Δ_{2}b_{i}, 0}.

Proof. We have from Theorem 1

p − ℓ = ∑_{i=\underline{k}}^{\overline{k}} Δ_{2}b_{i} β_{ki} = ∑_{i=\underline{k}}^{\overline{k}} Δ_{2}^{+}b_{i} β_{ki} + ∑_{i=\underline{k}}^{\overline{k}} Δ_{2}^{−}b_{i} β_{ki}.

The positivity of the β_{ki} implies that the first sum on the right–hand side is positive and the second is negative and that therefore

∑_{i=\underline{k}}^{\overline{k}} Δ_{2}^{−}b_{i} β_{ki} ≤ p − ℓ ≤ ∑_{i=\underline{k}}^{\overline{k}} Δ_{2}^{+}b_{i} β_{ki}.

Since the β_{ki} are convex over [t_{k}^{∗}, t_{k+1}^{∗}], they can be bounded linearly to yield (3.3).

3.1. Implementation. The envelopes of Corollary 2 depend on the control points b_{i}, their second differences Δ_{2}b_{i}, and the values β_{ki}(t_{k}^{∗}). In evaluating the sum in equation (3.3) for some t, specifically at t_{k}^{∗} and t_{k+1}^{∗}, it suffices to sum over all i ∈ I(t) with

I(t) = { i | β_{ki}(t) > 0 } , (3.4)

which is a subset of the integers between \underline{k} and \overline{k}.

We determine I(t) by inspecting equation (3.1): let t ∈ [t_{k}^{∗}, t_{k+1}^{∗}] and let t_{l} < t ≤ t_{l+1} be the knots immediately to the left and right of t (see Figure 3). Since N_{j}^{d}(t) can only be non-zero if l − d ≤ j ≤ l and since β_{k,l−d}(t) = β_{kl}(t) = 0, the set I(t) is

I(t) = { i | l − d < i < l for t_{l} < t ≤ t_{l+1} } .

t\underline{k} t^{k+1} t∗ k t^{l} t t^{l+1}  t\overline{k} t{∗ \atop k+1} t^{k+d+1}

Figure 3. For a given t ∈ [t_{k}^{∗}, t_{k+1}^{∗}], the set I(t) = { i | β_{ki}(t) > 0 } is determined by the positions of the displayed knots relative to one another.

For an efficient implementation, we precompute the I(t_{k}^{∗}) and the values β_{ki}(t_{k}^{∗}), i ∈ I(t_{k}^{∗}). Computing the lower and upper envelope from Corollary 2 for any p over the fixed knot sequence (t_{k}) then only requires computing one second difference and one scalar product with d − 1 terms for each Greville abscissa t_{k}^{∗}.

3.2. Sharpness and convergence. The envelope from Corollary 2 is sharp in the sense that the upper (lower) part of the envelope equals p at t_{k}^{∗} if Δ_{2}b_{i} ≥ 0 (Δ_{2}b_{i} ≤ 0) for all i ∈ I(t_{k}^{∗}). This is the case if the whole polynomial piece of p on which p(t_{k}^{∗}) lies is convex (concave). In particular, the envelope is sharp for splines of degree 2 since I(t_{k}^{∗}) contains only one element.

Sharpness implies that, under subdivison, the width of the envelope shrinks quadratically in the distance of the knots: since the envelope consists of linear pieces, the maximum width is attained at the break points. Since a spline has only finitely many inflection points almost all pieces generated by subdivision are either concave or convex for which the width of the envelope equals the distance of the spline to the control polygon which is known to decrease quadratically [CS85, Dah86].

4. Coarse envelopes

The envelope in Corollary 2 requires the evaluation of d − 1 splines β_{ki} at each Greville abscissa t_{k}^{∗}. We can reduce the computational cost to just one evaluation per Greville abscissa by subsuming the values of the β_{ki} into one spline ζ and estimating its values. The resulting envelopes, though very simple to compute, are in general considerably larger than the ones from Corollary 2.

Theorem 3. The difference between the spline p and its B–spline control polygon ℓ(p) over the interval [t_{k}^{∗}, t_{k+1}^{∗}] is bounded by

|p − ℓ_{k}(p)| ≤ M |ζ − ℓ_{k}(ζ)| = M z. (4.5)

where M(t) = max { |Δ_{2}b_{i}| | i ∈ I(t) }. The splines ζ,

ζ = ∑_{j} ζ_{j}N_{j}^{d} where ζ_{j} = jt_{j}^{∗} + ∑_{i=j}^{\overline{k}} t_{i}^{∗}, (4.6)

and z = ζ − ℓ(ζ) are nonnegative and convex.

Proof. Using Theorem 1, we have

|p − ℓ_{k}(p)| = |∑_{i=\underline{k}}^{\overline{k}} Δ_{2}b_{i} β_{ki}| ≤ M |∑_{i=\underline{k}}^{\overline{k}} β_{ki}| = M ∑_{i=\underline{k}}^{\overline{k}} β_{ki}.

Figure 4. The function z for cubic splines over the knot sequence (0, 0, 0, 0, 1, 2, 4, 4, 4, 4). The grey lines indicate the position of the Greville abscissae. Knots are shown as ticks on the x–axis. The values of z range from 0 to 0.26.

Equation (4.5) follows if we can show that ∑_{i} β_{ki} = z.

\begin{aligned}∑_{i=\underline{k}}^{\overline{k}} β_{ki} & = ∑_{i=\underline{k}}^{\overline{k}} ∑_{j=\underline{k}}^{i}(t_{i}^{∗} − t_{j}^{∗})α_{kj} = ∑_{j=\underline{k}}^{\overline{k}} ∑_{i=j}^{\overline{k}}(t_{i}^{∗} − t_{j}^{∗})α_{kj} \\ & = ∑_{j=\underline{k}}^{\overline{k}} [∑_{i=j}^{\overline{k}} t_{i}^{∗} − (\overline{k} − j + 1)t_{j}^{∗}] α_{kj} = ∑_{j=\underline{k}}^{\overline{k}} [jt_{j}^{∗} + ∑_{i=j}^{\overline{k}} t_{i}^{∗}] α_{kj} \\ & = ∑_{j=\underline{k}}^{\overline{k}} ζ_{j} α_{kj} = ∑_{j=\underline{k}}^{\overline{k}} ζ_{j}N_{j}^{d} − L_{k}( · | ζ_{k}, ζ_{k+1}) = z. \end{aligned} (4.7)

It is easily checked that ζ′′_{j} > 0. The functions ζ and z = ζ − ℓ(ζ) are therefore strictly convex on [t_{k}^{∗}, t_{k+1}^{∗}]. The coefficients of ζ and z are nonnegative.

Corollary 4. The difference between p and its control polygon ℓ over the interval [t_{k}^{∗}, t_{k+1}^{∗}] is bounded by

|p − ℓ| ≤ L_{k} (Mz) .

Proof. By Theorem 1 and the convexity of the β_{ki}, we have

|p − ℓ| ≤ ∑_{i=\underline{k}}^{\overline{k}} |Δ_{2}b_{i}| β_{ki} ≤ L_{k} (∑_{i=\underline{k}}^{\overline{k}} |Δ_{2}b_{i}| β_{ki}) .

The definition of M and equation (4.7) in the proof of Theorem 3 show that

L_{k} (∑_{i=\underline{k}}^{\overline{k}} |Δ_{2}b_{i}| β_{ki}) ≤ L_{k} (M ∑_{i=\underline{k}}^{\overline{k}} β_{ki}) = L_{k} (Mz) .

Figure 5. A cubic spline and its envelope according to Corollary 2 (top) and Corollary 4 (bottom) over the knot sequence (0, 0, 0, 0, 1, 2, 4, 4, 4, 4) with control points (0, 1, 3, 0, 3, 2).

4.1. Bounding with a quadratic spline. The same considerations as in Theorem 3 but with divided instead of centered second differences yield a quadratic bounding spline.

Corollary 5. The difference between the spline p and its control polygon ℓ(p) over the interval [t_{k}^{∗}, t_{k+1}^{∗}] is bounded by

|p − ℓ(p)| ≤ M̂(t) |η − ℓ(η)|

where M̂(t) = max { |b′′_{i}| | i ∈ I(t) }. The function η = ∑ η_{j}N_{j}^{d} is a quadratic spline with η′′ = 1.

Proof. Using divided second differences b′′_{i}, equation (3.2) becomes

p − ℓ = ∑_{i=\underline{k}}^{\overline{k}} b′′_{i+1} \frac{t_{i+d} − t_{i+1}}{d − 1} β_{ki}.

Since, in analogy to the proof of Theorem 3,

η − ℓ(η) = ∑_{i=\underline{k}}^{\overline{k}} \frac{t_{i+d} − t_{i+1}}{d − 1} β_{ki},

η is given by

η = ∑_{i=\underline{k}}^{\overline{k}} ∑_{j=\underline{k}}^{i} \frac{t_{i+d} − t_{i+1}}{d − 1} (t_{i}^{∗} − t_{j}^{∗})N_{j}^{d}

= ∑_{j=\underline{k}}^{\overline{k}} ∑_{i=j}^{\overline{k}} \frac{t_{i+d} − t_{i+1}}{d − 1} (t_{i}^{∗} − t_{j}^{∗})N_{j}^{d}.

It is now easy to verify that η′′_{j} = 1.

4.2. Implementation. The envelope from Corollary 4 requires M(t_{k}^{∗}) and z(t_{k}^{∗}) for finite knot sequences (t_{0}, …, t_{m+d}) and corresponding Greville abscissae t_{0}^{∗}, …, t_{m}^{∗}.

The definition of the coefficients ζ_{j} in equation (4.6) seems particular to the interval [t_{k}^{∗}, t_{k+1}^{∗}] since it involves \overline{k}. However, we can extend the upper limit of summation in this definition to m, since only the values of z = ζ − ℓ(ζ) are needed which are not affected by this change.

An efficient implementation of the bound of Corollary 4 stores the values t_{k}^{∗}, z(t_{k}^{∗}), I(t_{k}^{∗}) together with the knot sequence, so that only the maximal second difference M(t_{k}^{∗}) needs to be recomputed whenever the control points of a spline change.

4.3. Sharpness. The proof of Theorem 3 contains only one inequality,

| ∑_{i∈I(t)} Δ_{2}b_{i} β_{ki}(t)| ≤ M(t) | ∑_{i∈I(t)} β_{ki}(t)| .

This is an equality exactly when all the second differences Δ_{2}b_{i}, i ∈ I(t), are equal to one another. The splines with this property are the linear polynomials and ζ.

Similarly, the bound from Corollary 5 is sharp for the linear polynomials and η, and therefore for all quadratic polynomials.

5. A Bound for Bernstein Polynomials

The B–splines N_{j}^{d} of degree d over the knot sequence (t_{0}, …, t_{2d}) with t_{i} = 1 for i > d and t_{i} = 0 else are called the Bernstein polynomials B_{j}^{d} of degree d. An explicit bound for the Bernstein polynomials was already given in [NPL99, Theorem 3.1]; we give an alternate proof for this theorem, showing how it can be derived from the more general exposition in this paper.

For Bernstein polynomials, the Greville abscissae are t_{i}^{∗} = i/d and the coefficients ζ_{j} are

ζ_{j} = \frac{j(j + 1) + d(d + 1)}{2d}.

Thus,

z = ∑_{j} ζ_{j}α_{kj} = \frac{1}{d} ∑_{j} \binom{j}{2}α_{kj} = \frac{1}{d} (∑_{j} \binom{j}{2}B_{j}^{d} − \frac{k(2dt − k − 1)}{2})

= \frac{d − 1}{2}t^{2} − \frac{k(2dt − k − 1)}{2d}

and

z(t_{k}^{∗}) = \frac{k(d − k)}{2d^{2}}, z(t_{k+1}^{∗}) = \frac{(k + 1)(d − (k + 1))}{2d^{2}}

at the endpoints of the interval [t_{k}^{∗}, t_{k+1}^{∗}]. The maximal value z(t_{k}^{∗}) over all k is taken on for k = ⌊d/2⌋. Since Δ_{2}b_{i} = d(b_{i−1} − 2b_{i} + b_{i+1}) the main theorem from [NPL99] follows:

Theorem 6 ([NPL99, Theorem 3.1]). Let p = ∑_{i=0}^{d} b_{i}B_{i}^{d} be a polynomial of degree d in Bernstein–Bézier form. The distance between p and its control polygon ℓ is uniformly bounded by

|p − ℓ| ≤ \frac{⌊d/2⌋ ⌈d/2⌉}{2d} max_{i=1}^{d−1} |Δ_{2}b_{i}|

where Δ_{2}b_{i} = b_{i−1} − 2b_{i} + b_{i+1}.

This bound decreases by a factor of 4 under subdivision at 1/2 [NPL99, Lemma 6.1].

6. A Bound for Uniform Splines

A spline is uniform if the knots are all equidistant. Without loss of generality, we choose t_{k} = k. The uniform B–spline basis functions N_{j}^{d} are shifts of one another and we define N^{d} = N_{0}^{d} so that N_{j}^{d}(t) = N^{d}(t − j). The corresponding Greville abscissae are

t_{k}^{∗} = \frac{1}{d} ∑_{i=k+1}^{k+d} i = k + \frac{d + 1}{2}

and ζ has the B–spline coefficients

ζ_{j} = j(j + \frac{d + 1}{2}) + ∑_{i=j}^{m} (i + \frac{d + 1}{2}) = (m + 1)(j + \frac{d + 1}{2}) + \binom{j − m}{2}.

According to Equation (4.7), z = ∑_{j} ζ_{j}α_{kj}. For uniform splines this simplifies to

z = ∑_{j} ζ_{j}α_{kj} = ∑_{j=\underline{k}}^{\overline{k}} [(m + 1)(j + \frac{d + 1}{2}) + \binom{j − m}{2}] α_{kj}

= ∑_{j} \binom{j − m}{2}α_{kj} = ∑_{j} \binom{j − k}{2}N_{j}^{d}.

Regardless of the degree of p, z is a quadratic polynomial and has the monomial form

z(t) = \frac{1}{2} (t^{2} − (t_{k}^{∗} + t_{k+1}^{∗})t + (\frac{t_{k}^{∗} + t_{k+1}^{∗}}{2} )^{2} + \frac{d − 2}{12}) .

Since z is a positive and convex function, it attains its maximum over [t_{k}^{∗}, t_{k+1}^{∗}] at one of the endpoints of the interval. Its values there are

z(t_{k}^{∗}) = z(t_{k+1}^{∗}) = \frac{d + 1}{24}.

This proves the following simplified version of Corollary 4:

Corollary 7. Let p = ∑_{j} b_{j}N_{j}^{d} be a uniform spline over the knot sequence t_{k} = k. Over the interval [t_{k}^{∗}, t_{k+1}^{∗}], the difference between p and its control polygon ℓ is bounded by

|p − ℓ| ≤ \frac{d + 1}{24}L_{k} (M) .

For uniform splines, the set I(t_{k}^{∗}) from equation (3.4) is

I(t_{k}^{∗}) = { i | k − ⌊d/2⌋ < i < k + ⌊d/2⌋ } .

Since z(t_{k}^{∗}) = (d + 1)/24 and I(t_{k}^{∗}) = {k} for d = 2 or d = 3, Corollary 2 reduces for quadratic and cubic uniform splines to

\frac{d + 1}{24}L_{k}(· | Δ_{2}^{−}b_{k}, Δ_{2}^{−}b_{k+1}) ≤ p − ℓ ≤ \frac{d + 1}{24}L_{k}(· | Δ_{2}^{+}b_{k}, Δ_{2}^{+}b_{k+1}). (6.8)

7. Uniform refinement

For uniform splines, we consider the refinement of the knot sequence t_{k} = k to the sequence t̂_{k} = k/2. We now have two representations for p,

p(t) = ∑_{k} b_{k}N^{d}(t − k) = ∑_{k} b̂_{k}N^{d}(2t − k),

where the new control points b̂_{k} are

b̂_{2i} = 2^{−d} ∑_{j=0}^{⌈d/2⌉} \binom{d + 1}{2j}b_{i−j},  b̂_{2i+1} = 2^{−d} ∑_{j=0}^{⌈d/2⌉} \binom{d + 1}{2j + 1}b_{i−j}. (7.9)

Since a′′_{i} = Δ_{2}a_{i−1}, we can use the B–spline representation of p′′ together with equation (7.9) to relate the centered second differences of the new control polygon to those of the old control polygon as

2^{d}Δ_{2}b̂_{2i} = ∑_{j} \binom{d − 1}{2j − 1}Δ_{2}b_{i−j} 2^{d}Δ_{2}b̂_{2i+1} = ∑_{j} \binom{d − 1}{2j}Δ_{2}b_{i−j}.

The equality ∑_{j} \binom{d−1}{j} = 2^{d−1} and the symmetry of the binomial coefficients imply

∑_{j} \binom{d − 1}{2j} = ∑_{j} \binom{d − 1}{2j − 1} = 2^{d−2},

so that

max_{i} |Δ_{2}b̂_{i}| ≤ \frac{1}{4} max_{i} |Δ_{2}b_{i}|.

This ensures that the bound from Corollary 7 converges quadratically to zero under repeated uniform refinement. Figure 6 illustrates this for a cubic uniform spline.

7.1. Examples. For quadratic splines, uniform refinement is called Chaikin’s algorithm and

b̂_{2i} = 2^{−2}(3b_{i−1} + b_{i}),  b̂_{2i+1} = 2^{−2}(b_{i−1} + 3b_{i}).

This yields

Δ_{2}b̂_{2i} = Δ_{2}b̂_{2i−1} = \frac{1}{4}Δ_{2}b_{i−1}.

Since every second difference decreases by a factor of four, subsequent envelopes are contained in one another.

Figure 6. A uniform cubic spline with control points (0, 1, 3, 0, 3, 2). Shown are the envelope according to equation (6.8) (top) and the envelope after one step of uniform refinement (bottom).

Similarly, for cubic splines we have

b̂_{2i} = 2^{−3}(b_{i−2} + 6b_{i−1} + b_{i}),  b̂_{2i+1} = 2^{−3}(4b_{i−1} + 4b_{i}).

and therefore

Δ_{2}b̂_{2i} = \frac{1}{4}Δ_{2}b_{i−1}, Δ_{2}b̂_{2i+1} = \frac{1}{8}(Δ_{2}b_{i−1} + Δ_{2}b_{i}).

8. Conclusion

We only considered envelopes for spline functions. The extension to parametric curves, though, is a simple two step process: first, the coordinate functions of the curve are enveloped separately at each control point, yielding axis–aligned boxes around the control points. The union of the convex hulls of any two consecutive control points is guaranteed to contain the curve by the linearity of the envelopes.

The envelopes developed in this paper can be generalized to tensorproduct splines and other bivariate bases commonly used in CAGD. The construction follows the principles outlined in this paper: rewrite p − ℓ in terms of second differences in a new basis and estimate the range of the basis functions at the Greville abscissae. Separating the vector of second differences of p into a negative and a positive part gives then simple envelopes as piecewise offsets of the control polygon. The details of this construction will be reported in a forthcoming paper.

References

[CS85] Elaine Cohen and Larry L. Schumaker. Rates of convergence of control polygons. Comput. Aided Geom. Design, 2(1-3):229–235, 1985. Surfaces in CAGD ’84 (Oberwolfach, 1984).

[Dah86] Wolfgang Dahmen. Subdivision algorithms converge quadratically. J. Comput. Appl. Math., 16(2):145–158, 1986.

[dB93] Carl de Boor. B(asic)–spline basics. In Fundamental Developments of Computer Aided Geometric Modeling, pages 27–49. Academic Press, London, 1993. ed. by Les Piegl.

[NPL99] D. Nairn, J. Peters, and D. Lutterkort. Sharp, quantitative bounds on the distance between a polynomial piece and its Bézier control polygon. Computer Aided Geometric Design, 16(7):613–631, 1999.