Graphics Reference
In-Depth Information
The tridiagonal symmetric matrix S
n
has all positive entries and is
diagonally domi-
nant,
which implies that it has an inverse. In other words, there is a solution to the
cubic spline interpolation problem and this solution is unique. The tridiagonal nature
of the matrix means that the system of equations can be solved very efficiently. One
needs only one forward substitution sweep (row operations starting from the top,
which eliminate the elements below the diagonal and change the diagonal elements to
1) and then one backward substitution sweep starting from the bottom. See [ConD72].
Finally, let us translate the above results to interpolating points in
R
m
with a para-
metric curve. Suppose that we are given distinct real numbers u
0
, u
1
,..., u
n
and
points
p
0
,
p
1
,...,
p
n
in
R
m
, then there is a unique cubic spline p : [u
0
,u
n
] Æ
R
m
sat-
isfying p(u
i
) =
p
i
. The individual cubic curves that make up p(u) are defined by equa-
tion (11.25). All that is needed is to find the tangent vectors
v
i
at the points p(u
i
). Let
1
D
pp p
i
=-
and
d
=
-
.
i
+
1
i
i
uu
i
+
1
i
Then equation (11.30) becomes
(
)
-
2
2
v
v
Ê
3
d
D
p
+
d
D
p
d
v
ˆ
Ê
ˆ
1
0
1
0
0
Á
Á
Á
Á
Á
Á
(
)
˜
˜
˜
˜
˜
˜
Á
Á
Á
Á
Á
Á
˜
˜
˜
˜
˜
˜
2
2
3
d
D
p
+
d
D
p
2
1
2
.
.
.
.
S
n
=
(11.32)
(
)
2
2
v
v
3
d
D
p
+
d
D
p
n
-
2
n
-
3
n
-
2
n
-
3
n
-
2
Ë
¯
(
)
-
Ë
2
2
¯
3
d
D
p
+
d
D
p
d
v
n
-
1
n
-
2
n
-
1
n
-
1
n
n
-
2
n
-
1
The
v
i
are solved for using this equation. The uniform spline case where u
i+1
- u
i
= 1
is of special interest. In that case we need to solve the following system:
(
)
-
410
...
...
000
v
v
3
pp v
-
Ê
ˆ
Ê
ˆ
Ê
ˆ
1
2
0
0
Á
Á
Á
Á
Á
Á
Á
Á
˜
˜
˜
˜
˜
˜
˜
˜
Á
Á
Á
Á
Á
Á
Á
Á
˜
˜
˜
˜
˜
˜
˜
˜
Á
Á
Á
Á
Á
Á
Á
Á
˜
˜
˜
˜
˜
˜
˜
˜
(
)
141
000
3
pp
-
2
3
1
.
.
.
...
.
.
.
.
.
.
.
.
.
=
(11.33)
.
.
.
O
.
.
.
.
.
.
...
.
.
.
(
)
000
...
...
141
v
v
3
pp
pp
-
n
-
2
n
-
1
n
-
3
Ë
¯
Ë
¯
Ë
¯
(
)
-
000
014
3
-
v
n
-
1
n
n
-
2
n
Section 11.5.5 will look at another solution to the spline interpolation problem.
11.3
Cubic Curves
Cubic curves are the most popular in graphics because, as indicated earlier, the degree
is high enough for them to be able to satisfy the typical constraints one wants and yet
