i
i
i
i
i
i
i
i
15.3. Polynomial Pieces 349
The canonical form does not always have convenient coefficients. For prac-
tical purposes, throughout this chapter, we will find sets of basis functions such
that the coefficients are convenient ways to control the curves represented by the
polynomial functions.
To specify a curve embedded in two dimensions, one can either specify two
polynomials in t: one for how x varies with t and one for how y varies with t;
or specify a single polynomial where each of the a
i
is a 2D point. An analogous
situation exists for any curve in an n-dimensional space.
15.3.2 A Line Segment
To introduce the concepts of piecewise polynomial curve representations, we will
discuss line segments. In practice, line segments are so simple that the mathemat-
ical derivations will seem excessive. However, by understanding this simple case,
things will be easier when we move on to more complicated polynomials.
Consider a line segment that connects point p
0
to p
1
. We could write the
parametric function over the unit domain for this line segment as
f(u)=(1− u)p
0
+ up
1
. (15.6)
By writing this in vector form, we have hidden the dimensionality of the points
and the fact that we are dealing with each dimension separately. For example,
were we working in 2D, we could have created separate equations:
f
x
(u)= (1−u)x
0
+ ux
1
,
f
y
(u)= (1− u)y
0
+ uy
1
.
The line that we specify is determined by the two end points, but from now
on we will stick to vector notation since it is cleaner. We will call the vector of
control parameters, p,thecontrol points, and each element of p,acontrol point.
While describing a line segment by the positions of its endpoints is obvious
and usually convenient, there are other ways to describe a line segment. For
example,
1. the position of the center of the line segment, the orientation, and the length;
2. the position of one endpoint and the position of the second point relative to
the first;
3. the position of the middle of the line segment and one endpoint.
i
i
i
i
i
i
i
i
350 15. Curves
It is obvious that given one kind of a description of a line segment, we can switch
to another one.
A different way to describe a line segment is using the canonical form of the
polynomial (as discussed in Section 15.3.1),
f(u)=a
0
+ ua
1
. (15.7)
Any line segment can be represented either by specifying a
0
and a
1
or the end-
points (p
0
and p
1
). It is usually more convenient to specify the endpoints, because
we can compute the other parameters from the endpoints.
To write the canonical form as a vector expression, we defineavectoru that
is a vector of the powers of u:
u =
1 uu
2
u
3
... u
n
,
so that Equation (15.4) can be written as
f(u)=u · a. (15.8)
This vector notation will make transforming between different forms of the curve
easier.
Equation (15.8) describes a curve segment by the set of polynomial coeffi-
cients for the simple form of the polynomial. We call such a representation the
canonical form. We will denote the parameters of the canonical form by a.
While it is mathematically simple, the canonical form is not always the most
convenient way to specify curves. For example, we might prefer to specify a
line segment by the positions of its endpoints. If we want to define p
0
to be the
beginning of the segment (where the segment is when u =0)andp
1
to be the
end of the line segment (where the line segment is at u =1), we can write
p
0
= f (0) = [1 0] ·[a
0
a
1
] ,
p
1
= f (1) = [1 1] ·[a
0
a
1
] .
(15.9)
We can solve these equations for a
0
and a
1
:
a
0
= p
0
,
a
1
= p
1
− p
0
.
Matrix Form for Polynomials
While this first example was easy enough to solve, for more complicatedexamples
it will be easier to write Equation (15.9) in the form
p
0
p
1
=
10
11
a
0
a
1
.
i
i
i
i
i
i
i
i
15.3. Polynomial Pieces 351
Alternatively, we can write
p = Ca, (15.10)
where we call C, the constraint matrix.
1
If having vectors of points bothers you,
you can consider each dimension independently (so that p is [x
0
x
1
] or [y
0
y
1
])
and a is handled correspondingly).
We can solve Equation (15.10) for a by finding the inverse of C. This inverse
matrix which we will denote by B is called the basis matrix. The basis matrix
is very handy since it tells us how to convert between the convenient parameters
p and the canonical form a
,
and, therefore, gives us an easy way to evaluate the
curve
f(u)=uBp.
We can find a basis matrix for whatever form of the curve that we want, providing
that there are no non-linearities in the definition of the parameters. Examples of
non-linearly defined parameters include the length and angle of the line segment.
Now, suppose we want to parameterize the line segment so that p
0
is the half-
way point (u =0.5), and p
1
is the ending point (u =1). To derive the basis
matrix for this parameterization, we set
p
0
= f(0.5) = 1 a
0
+0.5 a
1
,
p
1
= f (1) = 1 a
0
+1a
1
.
So
C =
1 .5
11
,
and therefore
B = C
−1
=
2 −1
−22
.
15.3.3 Beyond Line Segments
Line segments are so simple that finding a basis matrix is trivial. However, it was
good practice for curves of higher degree. First, let’s consider quadratics (curves
of degree two). The advantage of the canonical form (Equation (15.4)) is that it
works for these more complicated curves, just by letting n be a larger number.
1
We assume the form of a vector (row or column) is obvious from the context, and we will skip all
of the transpose symbols for vectors.
i
i
i
i
i
i
i
i
352 15. Curves
A quadratic (a degree-two polynomial) has three coefficients, a
0
, a
1
,anda
2
.
These coefficients are not convenient for describing the shape of the curve. How-
ever, we can use the same basis matrix method to devise more convenient param-
eters. If we know the value of u, Equation (15.4) becomes a linear equation in the
parameters, and the linear algebra from the last section still works.
Suppose that we wanted to describe our curves by the position of the begin-
ning (u =0), middle
2
(u =0.5), and end (u =1). Entering the appropriate
values into Equation (15.4):
p
0
= f(0) = a
0
+0
1
a
1
+0
2
a
2
,
p
1
= f(0.5) = a
0
+0.5
1
a
1
+0.5
2
a
2
,
p
2
= f(1) = a
0
+1
1
a
1
+1
2
a
2
.
So the constraint matrix is
C =
⎡
⎣
10 0
1 .5 .25
11 1
⎤
⎦
,
and the basis matrix is
B = C
−1
=
⎡
⎣
100
−34−1
2 −42
⎤
⎦
.
There is an additional type of constraint (or parameter) that is sometimes con-
venient to specify: the derivative of the curve (with respect to its free parameter)
at a particular value. Intuitively, the derivatives tell us how the curve is changing,
so that the first derivative tells us what direction the curve is going, the second
derivative tells us how quickly the curve is changing direction, etc. We will see
examples of why it is useful to specify derivatives later.
For the quadratic,
f(u)=a
0
+ a
1
u + a
2
u
2
,
the derivatives are simple:
f
(u)=
df
du
= a
1
+2a
2
u,
and
f
(u)=
d
2
f
du
2
=
df
du
=2a
2
.
2
Notice that this is the middle of the parameter space, which might not be the middle of the curve
itself.
i
i
i
i
i
i
i
i
15.3. Polynomial Pieces 353
Or, more generally,
f
(u)=
(
n
i=1
iu
i−1
a
i
,
f
(u)=
(
n
i=2
i(i − 1)u
i−2
a
i
.
For example, consider a case where we want to specify a quadratic curve
segment by the position, first, and second derivative at its middle (u =0.5).
p
0
= f(0.5) = a
0
+0.5
1
a
1
+0.5
2
a
2
,
p
1
= f
(0.5) = a
1
+20.5 a
2
,
p
2
= f
(0.5) = 2 a
2
.
The constraint matrix is
C =
⎡
⎣
1 .5 .25
01 1
00 2
⎤
⎦
,
and the basis matrix is
B = C
−1
=
⎡
⎣
1 −.5 .125
01− .5
00 .5
⎤
⎦
.
15.3.4 Basis Matrices for Cubics
Cubic polynomials are popular in graphics (See Section 15.5). The derivations
for the various forms of cubics are just like the derivations we’ve seen already in
this section. We will work through one more example for practice.
A very useful form of a cubic polynomial is the Hermite form, where we
specify the position and first derivative at the beginning and end, that is,
p
0
= f(0) = a
0
+0
1
a
1
+0
2
a
2
+0
3
a
3
,
p
1
= f
(0) = a
1
+2 0
1
a
2
+30
2
a
3
,
p
2
= f(1) = a
0
+1
1
a
1
+1
2
a
2
+1
3
a
3
,
p
3
= f
(1) = a
1
+2 1
1
a
2
+31
2
a
3
.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.