Graphics Reference
In-Depth Information
11.2 looks at some old interpolation problems beginning with two classical
approaches to curve fitting. Section 11.3 translates the results on Hermite interpola-
tion into matrices. We then discuss the popular Bézier and B-spline curves from
their “classical” point of view in Sections 11.4 and 11.5.1, respectively. The material
up to this point is really intended as a warm up. It is in Section 11.5.2 that we describe
the modern treatment of the curves defined in the earlier sections. We introduce
the easy but fundamentally new idea of multiaffine maps that is the elegant basis for
most of the curves and surfaces that are used in CAGD. From a high-level standpoint,
we really should have started with Section 11.5.2, but doing so without the back-
ground of the curves described in the earlier sections might have left a reader some-
what overwhelmed by the simple but yet technical nature of multiaffine maps.
Furthermore, the facts themselves are worthwhile knowing. The only thing missing
was a uniform framework. After defining rational B-spline and NURBS curves in
Section 11.5.3, we present some algorithms in Section 11.5.4 that compute B-spline
and NURBS curves efficiently. Section 11.5.5 describes some aspects of B-spline inter-
polation. We finish the discussion of splines in Section 11.6 with nonlinear splines.
Section 11.7 defines superellipses, an interesting special class of curves. Section 11.8
discusses the subdivision problem. The problem of piecing together curves in such a
way that one gets a globally smooth curve in the end is discussed briefly in Section
11.9. Section 11.10 looks at some issues related to the shape of curves. Section 11.11
defines hodographs and Section 11.12 explains the fairing of curves along with some
comments on interpolation with fair curves. Section 11.13 introduces parallel trans-
port frames on curves, which are the sometimes useful alternative to Frenet frames.
Finally, switching from smooth curves to polygonal curves, Section 11.14 discusses
an algorithm that can be thought of as either as a way of smoothing the latter or as
defining an entirely new class of curves. Section 11.15 summarizes the main points
of the chapter.
11.2
Early Historical Developments
11.2.1
Lagrange Interpolation
The simplest form of interpolation is Lagrange interpolation.
The Lagrange interpolation problem:
Given points (x
0
,y
0
), (x
1
,y
1
),..., and (x
n
,y
n
), find
a polynomial p(x), so that p(x
i
) = y
i
for i = 0,1,..., n.
11.2.1.1
Theorem.
There is a unique such polynomial p(x) of degree n called the
Lagrange polynomial
.
Proof.
Define polynomials
n
xx
xx
-
-
j
'
()
=
(
)
=
LxLxxx
;
,
,...,
x
.
(11.2)
in
,
in
,
01
n
i
j
j
=π
0
,
j i
