i
i
i
i
i
i
i
i
15.5. Cubics 359
endpoints as parameters and shares interior points with its neighbors), or if we
use the dependency scheme (such as the example one with the first endpoint and
midpoint), we end up with n +1controls for an n-segment curve.
Dependency schemes have a more serious problem. A change in one place in
the curve can propagate through the entire curve. This is called a lack of locality.
Locality means that if you move a point on a curve it will only effect a local
region. The local region might be big, but it will be finite. If a curve’s controls do
not have locality, changing a control point may effect points infinitely far away.
To see locality, and the lack thereof, in action, consider two chains of line
segments, as shown in Figure 15.5. One chain has its pieces parameterized by
their endpoints and uses point-sharing to maintain continuity. The other has its
pieces parameterized by an endpoint and midpoint and uses dependency propa-
gation to keep the segments together. The two segment chains can represent the
same curves: they are both a set of n connected line segments. However, because
of locality issues, the endpoint-sharedform is likely to be more convenient for the
user. Consider changing the position of the first control point in each chain. For
the endpoint-shared version, only the first segment will change, while all of the
segments will be affected in the midpoint version, as in Figure 15.5. In fact, for
any point moved in the endpoint-shared version, at most two line segments will
change. In the midpoint version, all segments after the control point that is moved
will change, even if the chain is infinitely long.
In this example, the dependency propagation scheme was the one that did not
have local control. This is not always true. There are direct sharing schemes that
are not local and propagation schemes that are local.
We emphasize that locality is a convenience of control issue. While it is in-
convenient to have the entire curve change every time, the same changes can be
made to the curve. It simply requires moving several points in unison.
15.5 Cubics
In graphics, when we represent curves using piecewise polynomials we usually
use either line segments or cubic polynomials for the pieces. There are a number
of reasons why cubics are popular in computer graphics:
• Piecewise cubic polynomials allow for C
2
continuity, which is generally
sufficient for most visual tasks. The C
1
smoothness that quadratics offer is
often insufficient. The greater smoothness offered by higher-order polyno-
mials is rarely important.
i
i
i
i
i
i
i
i
360 15. Curves
• Cubic curves provide the minimum-curvatureinterpolants to a set of points.
That is, if you have a set of n +3points and define the “smoothest” curve
that passes through them (that is the curve that has the minimum curvature
over its length), this curve can be represented as a piecewise cubic with n
segments.
• Cubic polynomials have a nice symmetry where position and derivative can
be specified at the beginning and end.
• Cubic polynomials have a nice tradeoff between the numerical issues in
computation and the smoothness.
Notice that we do not have to use cubics. They just tend to be a good tradeoff
between the amount of smoothness and complexity. Different applications may
have different tradeoffs. We focus on cubics since they are the most commonly
used.
The canonical form of a cubic polynomial is
f(u)=a
0
+ a
1
u + a
2
u
2
+ a
3
u
3
.
As we discussed in Section 15.3, these canonical form coefficients are not a con-
venient way to describe a cubic segment.
We seek forms of cubic polynomials for which the coefficients are a conve-
nient way to control the resulting curve represented by the cubic. One of the main
conveniences will be to provide ways to insure the connectedness of the pieces
and the continuity between the segments.
Each cubic polynomial piece requires four coefficients or control points. That
means for a piecewise polynomial with n pieces, we may require up to 4n control
points if no sharing between segments is done or dependencies used. More often,
some part of each segment is either shared or depends on an adjacent segment, so
the total number of control points is much lower. Also, note that a control point
might be a position or a derivative of the curve.
Unfortunately, there is no single “best” representation for a piecewise cubic.
It is not possible to have a piecewise polynomial curve representation that has all
of the following desirable properties:
1. each piece of the curve is a cubic;
2. the curve interpolates the control points;
3. the curve has local control;
4. the curve has C
2
continuity.
i
i
i
i
i
i
i
i
15.5. Cubics 361
We can have any three of these properties, but not all four; there are repre-
sentations that have any combination of three. In this book, we will discuss cubic
B-splines that do not interpolate their control points (but have local control and
are C
2
); Cardinal splines and Catmull-Rom splines that interpolate their control
points and offer local control, but are not C
2
; and natural cubics that interpolate
and are C
2
, but do not have local control.
The continuity properties of cubics refer to the continuity between the seg-
ments (at the knot points). The cubic pieces themselves have infinite continuity
in their derivatives (the way we have been talking about continuity so far). Note
that if you have a lot of control points (or knots), the curve can be wiggly, which
might not seem “smooth.”
15.5.1 Natural Cubics
With a piecewise cubic curve, it is possible to create a C
2
curve. To do this, we
need to specify the position and first and second derivative at the beginning of
each segment (so that we can make sure that it is the same as at the end of the
previous segment). Notice, that each curve segment receives three out of its four
parameters from the previous curve in the chain. These C
2
continuous chains of
cubics are sometimes referred to as natural cubic splines.
For one segment of the natural cubic, we need to parameterize the cubic by
the positions of its endpoints and the first and second derivative at the beginning
point. The control points are therefore
p
0
= f(0) = a
0
+0
1
a
1
+0
2
a
2
+0
3
a
3
,
p
1
= f
(0) = 1
1
a
1
+2 0
1
a
2
+3 0
2
a
3
,
p
2
= f
(0) = 2 1
1
a
2
+6 0
1
a
3
,
p
3
= f(1) = a
0
+1
1
a
1
+1
2
a
2
+1
3
a
3
.
Therefore, the constraint matrix is
C =
⎡
⎢
⎢
⎣
1000
0100
0020
1111
⎤
⎥
⎥
⎦
,
and the basis matrix is
B = C
−1
=
⎡
⎢
⎢
⎣
10 00
01 00
00.50
−1 −1 −.51
⎤
⎥
⎥
⎦
.
i
i
i
i
i
i
i
i
362 15. Curves
Given a set of n control points, a natural cubic spline has n−1 cubic segments.
The first segment uses the control points to define its beginning position, ending
position, and first and second derivative at the beginning. A dependency scheme
copies the position, and first and second derivative of the end of the first segment
for use in the second segment.
A disadvantage of natural cubic splines is that they are not local. Any change
in any segment may require the entire curve to change (at least the part after
the change was made). To make matters worse, natural cubic splines tend to be
ill-conditioned: a small change at the beginning of the curve can lead to large
changes later. Another issue is that we only have control over the derivatives of
the curve at its beginning. Segments after the beginning of the curve determine
their derivatives from their beginning point.
15.5.2 Hermite Cubics
Hermite cubic polynomials were introduced in Section 15.3.4. A segment of a
cubic Hermite spline allows the positions and first derivatives of both of its end
points to be specified. A chain of segments can be linked into a C
1
spline by
using the same values for the position and derivative of the end of one segment
and for the beginning of the next.
Given a set of n control points, where every other control point is a derivative
value, a cubic Hermite spline contains (n−2)/2 cubic segments. The spline inter-
polates the points, as shown in Figure 15.6, but can guarantee only C
1
continuity.
Hermite cubics are convenient because they provide local control over the
shape, and provide C
1
continuity. However, since the user must specify both po-
sitions and derivatives, a special interface for the derivatives must be provided.
One possibility is to provide the user with points that represent where the deriva-
tive vectors would end if they were “placed” at the position point.
Figure 15.6. A Hermite cubic spline made up of three segments.
i
i
i
i
i
i
i
i
15.5. Cubics 363
15.5.3 Cardinal Cubics
A cardinal cubic spline is a type of C
1
interpolating spline made up of cubic
polynomial segments. Given a set of n control points, a cardinal cubic spline uses
n −2 cubic polynomial segments to interpolate all of its points except for the first
and last.
Cardinal splines have a parameter called tension that controls how “tight” the
curve is between the points it interpolates. The tension is a number in the range
[0, 1) that controls how the curve bends towards the next control point. For the
important special case of t =0, the splines are called Catmull-Rom splines.
Each segment of the cardinal spline uses four control points. For segment i,
the points used are i, i +1, i +2,andi +3as the segments share three points
with their neighbors. Each segment begins at its second control point and ends at
its third control point. The derivative at the beginning of the curve is determined
p
4
-
p
2
p
1
p
2
p
3
p
4
p
3
-
p
1
Figure 15.7. A segment of
a cardinal cubic spline inter-
polates its second and third
control points (p
2
and p
3
),
and uses its other points to
determine the derivatives at
the beginning and end.
by the vector between the first and third control points, while the derivative at the
end of the curve is given by the vector between the second and forth points, as
shown in Figure 15.7.
The tension parameter adjusts how much the derivatives are scaled. Specif-
ically, the derivatives are scaled by (1 − t)/2. The constraints on the cubic are
therefore
f(0) = p
2
,
f(1) = p
3
,
f
(0) =
1
2
(1 − t)(p
3
− p
1
),
f
(1) =
1
2
(1 − t)(p
4
− p
2
).
Solving these equations for the control points (defining s =(1−t)/2)gives
p
0
= f(1) −
2
1−t
f
(0) = a
0
+(1 −
1
s
) a
1
+ a
2
+ a
3
,
p
1
= f(0) = a
0
,
p
2
= f(1) = a
0
+ a
1
+ a
2
+ a
3
,
p
3
= f(0) +
1
s
f
(1) = a
0
+
1
s
a
1
+2
1
s
a
2
+3
1
s
a
3
.
This yields the cardinal matrix
B = C
−1
=
⎡
⎢
⎢
⎣
01 00
−s 0 s 0
2ss−33− 2s −s
−s 2 − ss−2 s
⎤
⎥
⎥
⎦
.
Since the third point of segment i is the second point of segment i+1, adjacent
segments of the cardinal spline connect. Similarly, the same points are used to
specify the first derivative of each segment, providing C
1
continuity.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.