spline1.pdf computer graphics cad software

spline pdf

1. Curves and Splines

2. Outline
•Hermite Splines
•Catmull-Rom Splines
•Bezier Curves
•Higher Continuity: Natural and B-Splines
•Drawing Splines

3. 3
M
o
d
e
l
i
n
g

C
o
m
p
l
e
x

S
h
a
p
e
s
•
W
e
w
a
n
t
t
o
b
u
i
l
d

m
o
d
e
l
s
o
f
v
e
r
y
c
o
m
p
l
i
c
a
t
e
d
o
b
j
e
c
t
s
•
A
n
e
q
u
a
t
i
o
n
f
o
r
a
s
p
h
e
r
e
i
s
p
o
s
s
i
b
l
e
, b
u
t

h
o
w
a
b
o
u
t
a
n

e
q
u
a
t
i
o
n
f
o
r
a

t
e
l
e
p
h
o
n
e
, o
r
a

f
a
c
e
?
•
C
o
m
p
l
e
x
i
t
y
i
s
a
c
h
i
e
v
e
d
u
s
i
n
g
s
i
m
p
l
e

p
i
e
c
e
s
–
p
o
l
y
g
o
n
s
,
p
a
r
a
m
e
t
r
i
c

c
u
r
v
e
s
a
n
d

s
u
r
f
a
c
e
s
,

o
r

i
m
p
l
i
c
i
t

c
u
r
v
e
s

a
n
d

s
u
r
f
a
c
e
s
–
T
h
i
s

l
e
c
t
u
r
e
:

p
a
r
a
m
e
t
r
i
c
c
u
r
v
e
s

4. 4
W
h
a
t

D
o

W
e

N
e
e
d

F
r
o
m

C
u
r
v
e
s
i
n

C
o
m
p
u
t
e
r

G
r
a
p
h
i
c
s
?
•
L
o
c
a
l

c
o
n
t
r
o
l

o
f

s
h
a
p
e

(
s
o

t
h
a
t

e
a
s
y

t
o

b
u
i
l
d

a
n
d

m
o
d
i
f
y
)
•
S
t
a
b
i
l
i
t
y
•
S
m
o
o
t
h
n
e
s
s

a
n
d

c
o
n
t
i
n
u
i
t
y
•
A
b
i
l
i
t
y

t
o

e
v
a
l
u
a
t
e

d
e
r
i
v
a
t
i
v
e
s
•
E
a
s
e

o
f

r
e
n
d
e
r
i
n
g
D
e
m
o

5. Curve Usage Demo

6. 5
C
u
r
v
e

R
e
p
r
e
s
e
n
t
a
t
i
o
n
s
•
E
x
p
l
i
c
i
t
:


y

=

f
(
x
)
–
E
a
s
y

t
o

g
e
n
e
r
a
t
e

p
o
i
n
t
s
–
M
u
s
t

b
e

a

f
u
n
c
t
i
o
n
:

b
i
g

l
i
m
i
t
a
t
i
o
n
—
v
e
r
t
i
c
a
l

l
i
n
e
s
?
b
m
x
y
+
=
x
y

7. 6
C
u
r
v
e

R
e
p
r
e
s
e
n
t
a
t
i
o
n
s
•
E
x
p
l
i
c
i
t
:


y

=

f
(
x
)
–
E
a
s
y

t
o

g
e
n
e
r
a
t
e

p
o
i
n
t
s
–
M
u
s
t

b
e

a

f
u
n
c
t
i
o
n
:

b
i
g

l
i
m
i
t
a
t
i
o
n
—
v
e
r
t
i
c
a
l

l
i
n
e
s
?
b
m
x
y
+
=
x
y
•
I
m
p
l
i
c
i
t
:


f
(
x
,
y
)

=

0
+
E
a
s
y

t
o

t
e
s
t

i
f

o
n

t
h
e

c
u
r
v
e
–
H
a
r
d

t
o

g
e
n
e
r
a
t
e

p
o
i
n
t
s
0
2
2
2
=
!
+
r
y
x
x
y

8. 7
C
u
r
v
e

R
e
p
r
e
s
e
n
t
a
t
i
o
n
s
•
E
x
p
l
i
c
i
t
:


y

=

f
(
x
)
+

E
a
s
y

t
o

g
e
n
e
r
a
t
e

p
o
i
n
t
s
–
M
u
s
t

b
e

a

f
u
n
c
t
i
o
n
:

b
i
g

l
i
m
i
t
a
t
i
o
n
—
v
e
r
t
i
c
a
l

l
i
n
e
s
?
b
m
x
y
+
=
x
y
•
I
m
p
l
i
c
i
t
:


f
(
x
,
y
)

=

0
+
E
a
s
y

t
o

t
e
s
t

i
f

o
n

t
h
e

c
u
r
v
e
–
H
a
r
d

t
o

g
e
n
e
r
a
t
e

p
o
i
n
t
s
0
2
2
2
=
!
+
r
y
x
x
y
•
P
a
r
a
m
e
t
r
i
c
:


(
x
,
y
)

=

(

f
(
u
)
,

g
(
u
)
)
+
E
a
s
y

t
o

g
e
n
e
r
a
t
e

p
o
i
n
t
s
)
s
i
n
,
(
c
o
s
)
,
(
u
u
y
x
=
u
=
0
u
=
""""
/
2
u
=
""""

9. 8
P
a
r
a
m
e
t
e
r
i
z
a
t
i
o
n

o
f

a

C
u
r
v
e
•
P
a
r
a
m
e
t
e
r
i
z
a
t
i
o
n
o
f
a
c
u
r
v
e
:

h
o
w
a
c
h
a
n
g
e
i
n
u

m
o
v
e
s

y
o
u
a
l
o
n
g
a
g
i
v
e
n
c
u
r
v
e
i
n
x
y
z
s
p
a
c
e
.
•
T
h
e
r
e
a
r
e
a
n
i
n
f
i
n
i
t
e
n
u
m
b
e
r
o
f
p
a
r
a
m
e
t
e
r
i
z
a
t
i
o
n
s
o
f
a

g
i
v
e
n
c
u
r
v
e
. S
l
o
w
, f
a
s
t
, s
p
e
e
d
c
o
n
t
i
n
u
o
u
s
o
r

d
i
s
c
o
n
t
i
n
u
o
u
s
,
c
l
o
c
k
w
i
s
e
(
C
W
)
o
r

C
C
W
…

10. 9
P
o
l
y
n
o
m
i
a
l

I
n
t
e
r
p
o
l
a
t
i
o
n
•
A
n
n
-
t
h
d
e
g
r
e
e

p
o
l
y
n
o
m
i
a
l
f
i
t
s
a
c
u
r
v
e
t
o
n
+
1
p
o
i
n
t
s
–
c
a
l
l
e
d

L
a
g
r
a
n
g
e

I
n
t
e
r
p
o
l
a
t
i
o
n
–
r
e
s
u
l
t

i
s

a

c
u
r
v
e

t
h
a
t
i
s

t
o
o
w
i
g
g
l
y
,

c
h
a
n
g
e
t
o

a
n
y

c
o
n
t
r
o
l
p
o
i
n
t

a
f
f
e
c
t
s

e
n
t
i
r
e

c
u
r
v
e

(
n
o
n
l
o
c
a
l
)

–
t
h
i
s
m
e
t
h
o
d
i
s

p
o
o
r
•
W
e
u
s
u
a
l
l
y
w
a
n
t
t
h
e
c
u
r
v
e
t
o
b
e
a
s
s
m
o
o
t
h
a
s
p
o
s
s
i
b
l
e
–
m
i
n
i
m
i
z
e

t
h
e

w
i
g
g
l
e
s
–
h
i
g
h
-
d
e
g
r
e
e

p
o
l
y
n
o
m
i
a
l
s
a
r
e

b
a
d

11. Linear Interpolation
Chalkboard

12. Spline Interpolation

13. Spine Interpolation
Demo

14. 1
0
S
p
l
i
n
e
s
:

P
i
e
c
e
w
i
s
e

P
o
l
y
n
o
m
i
a
l
s
•
A
s
p
l
i
n
e
i
s
a
p
i
e
c
e
w
i
s
e
p
o
l
y
n
o
m
i
a
l
-
m
a
n
y
l
o
w
d
e
g
r
e
e

p
o
l
y
n
o
m
i
a
l
s
a
r
e
u
s
e
d
t
o
i
n
t
e
r
p
o
l
a
t
e

(
p
a
s
s
t
h
r
o
u
g
h
)

t
h
e

c
o
n
t
r
o
l
p
o
i
n
t
s
•
C
u
b
i
c
p
i
e
c
e
w
i
s
e
p
o
l
y
n
o
m
i
a
l
s
a
r
e
t
h
e

m
o
s
t
c
o
m
m
o
n
:
–
p
i
e
c
e
w
i
s
e

d
e
f
i
n
i
t
i
o
n
g
i
v
e
s

l
o
c
a
l

c
o
n
t
r
o
l

15. 1
1
P
i
e
c
e
w
i
s
e

P
o
l
y
n
o
m
i
a
l
s
•
S
p
l
i
n
e
:

l
o
t
s
o
f
l
i
t
t
l
e
p
o
l
y
n
o
m
i
a
l
s
p
i
e
c
e
d
t
o
g
e
t
h
e
r
•
W
a
n
t

t
o

m
a
k
e
s
u
r
e
t
h
e
y

f
i
t

t
o
g
e
t
h
e
r
n
i
c
e
l
y
C
o
n
t
i
n
u
o
u
s

i
n

p
o
s
i
t
i
o
n
C
o
n
t
i
n
u
o
u
s

i
n

p
o
s
i
t
i
o
n

a
n
d

t
a
n
g
e
n
t

v
e
c
t
o
r
C
o
n
t
i
n
u
o
u
s

i
n

p
o
s
i
t
i
o
n
,
t
a
n
g
e
n
t
,
a
n
d

c
u
r
v
a
t
u
r
e

16. 1
2
S
p
l
i
n
e
s
•
T
y
p
e
s

o
f

s
p
l
i
n
e
s
:
–
H
e
r
m
i
t
e
S
p
l
i
n
e
s
–
C
a
t
m
u
l
l
-
R
o
m

S
p
l
i
n
e
s
–
B
e
z
i
e
r

S
p
l
i
n
e
s
–
N
a
t
u
r
a
l

C
u
b
i
c

S
p
l
i
n
e
s
–
B
-
S
p
l
i
n
e
s
–
N
U
R
B
S

17. 7
H
e
r
m
i
t
e
C
u
r
v
e
s
•
C
u
b
i
c

H
e
r
m
i
t
e
S
p
l
i
n
e
s
T
h
a
t
i
s
, w
e
w
a
n
t
a
w
a
y
t
o
s
p
e
c
i
f
y
t
h
e
e
n
d
p
o
i
n
t
s
a
n
d
t
h
e
s
l
o
p
e
a
t
t
h
e
e
n
d
p
o
i
n
t
s
!
P
o
P
1
P
2

18. 1
3
S
p
l
i
n
e
s
c
h
a
lk
b
o
a
r
d

19. 1
4
T
h
e

C
u
b
i
c

H
e
r
m
i
t
e
S
p
l
i
n
e
E
q
u
a
t
i
o
n
c
o
n
t
r
o
l

m
a
t
r
i
x
(
w
h
a
t

t
h
e

u
s
e
r

g
e
t
s

t
o

p
i
c
k
)
b
a
s
i
s
p
o
i
n
t

t
h
a
t
g
e
t
s

d
r
a
w
n
•
U
s
i
n
g

s
o
m
e

a
l
g
e
b
r
a
,

w
e

o
b
t
a
i
n
:
[
]
!!!! "#
$$$$ %&
!!
!!!! "#
$$$$ %&
"
"
"
"
=
21
21
2
3
0
0
0
1
0
1
0
0
1
2
3
3
1
1
2
2
1
)
(
pp
pp
u
u
u
u
p
•
T
h
i
s

f
o
r
m

t
y
p
i
c
a
l

f
o
r

s
p
l
i
n
e
s
–
b
a
s
i
s

m
a
t
r
i
x
a
n
d

m
e
a
n
i
n
g
o
f
c
o
n
t
r
o
l
m
a
t
r
i
x
c
h
a
n
g
e
w
i
t
h

t
h
e
s
p
l
i
n
e
t
y
p
e

20. 1
5
T
h
e

C
u
b
i
c

H
e
r
m
i
t
e
S
p
l
i
n
e
E
q
u
a
t
i
o
n
c
o
n
t
r
o
l

m
a
t
r
i
x
(
w
h
a
t

t
h
e

u
s
e
r

g
e
t
s

t
o

p
i
c
k
)
b
a
s
i
s
p
o
i
n
t

t
h
a
t
g
e
t
s

d
r
a
w
n
•
U
s
i
n
g

s
o
m
e

a
l
g
e
b
r
a
,

w
e

o
b
t
a
i
n
:
[
]
!!!! "#
$$$$ %&
!!
!!!! "#
$$$$ %&
"
"
"
"
=
21
21
2
3
0
0
0
1
0
1
0
0
1
2
3
3
1
1
2
2
1
)
(
pp
pp
u
u
u
u
p
!!!! "#
$$$$ %&
!!
!!!!! "#
$$$$$ %&
"
+
"
+
"
+
"
=
21
21
2
3
2
3
2
3
2
3
2
3
2
1
3
2
)
(
pp
pp
u
u
u
u
u
u
u
u
u
u
p
4
B
a
s
i
s
F
u
n
c
t
i
o
n
s
T

21. 1
6
E
v
e
r
y

c
u
b
i
c

H
e
r
m
i
t
e
s
p
l
i
n
e
i
s

a
l
i
n
e
a
r

c
o
m
b
i
n
a
t
i
o
n

(
b
l
e
n
d
)
o
f

t
h
e
s
e

4
f
u
n
c
t
i
o
n
s
!!!! "#
$$$$ %&
!!
!!!!! "#
$$$$$ %&
"
+
"
+
"
+
"
=
21
21
2
3
2
3
2
3
2
3
2
3
2
1
3
2
)
(
pp
pp
u
u
u
u
u
u
u
u
u
u
p
4
B
a
s
i
s
F
u
n
c
t
i
o
n
s
F
o
u
r

B
a
s
i
s

F
u
n
c
t
i
o
n
s

f
o
r

H
e
r
m
i
t
e
s
p
l
i
n
e
s
T
u

22. 1
7
P
i
e
c
i
n
g

t
o
g
e
t
h
e
r

H
e
r
m
i
t
e
C
u
r
v
e
s
•
I
t
'
s
e
a
s
y
t
o

m
a
k
e

a

m
u
l
t
i
-
s
e
g
m
e
n
t

H
e
r
m
i
t
e
s
p
l
i
n
e
–
e
a
c
h

p
i
e
c
e

i
s

s
p
e
c
i
f
i
e
d

b
y

a

c
u
b
i
c

H
e
r
m
i
t
e
c
u
r
v
e
–
j
u
s
t

s
p
e
c
i
f
y

t
h
e
p
o
s
i
t
i
o
n

a
n
d

t
a
n
g
e
n
t

a
t

e
a
c
h

“
j
o
i
n
t
”
–
t
h
e

p
i
e
c
e
s

f
i
t

t
o
g
e
t
h
e
r

w
i
t
h

m
a
t
c
h
e
d

p
o
s
i
t
i
o
n
s

a
n
d
f
i
r
s
t

d
e
r
i
v
a
t
i
v
e
s
–
g
i
v
e
s

C
1

c
o
n
t
i
n
u
i
t
y
•
T
h
e
p
o
i
n
t
s
t
h
a
t
t
h
e
c
u
r
v
e
h
a
s

t
o
p
a
s
s
t
h
r
o
u
g
h
a
r
e
c
a
l
l
e
d

k
n
o
t
s
o
r
k
n
o
t
p
o
i
n
t
s

23. Outline
•Hermite Splines
•Catmull-Rom Splines
•Bezier Curves
•Higher Continuity: Natural and B-Splines
•Drawing Splines

24. Problem with Hermite
Splines?
•Must explicitly specify derivatives at each
endpoint!
•How can we solve this?

25. 8
C
a
t
m
u
l
l
-
R
o
m

S
p
l
i
n
e
s
•
U
s
e
f
o
r

t
h
e
r
o
l
l
e
r
-
c
o
a
s
t
e
r
a
s
s
i
g
n
m
e
n
t
•
W
i
t
h

H
e
r
m
i
t
e
s
p
l
i
n
e
s
, t
h
e
d
e
s
i
g
n
e
r

m
u
s
t
s
p
e
c
i
f
y
a
l
l
t
h
e

t
a
n
g
e
n
t
v
e
c
t
o
r
s
•
C
a
t
m
u
l
l
-
R
o
m
:
a
n
i
n
t
e
r
p
o
l
a
t
i
n
g
c
u
b
i
c
s
p
l
i
n
e
w
i
t
h
b
u
i
l
t
-
i
n
C
1
c
o
n
t
i
n
u
i
t
y
.
P
o
P
1
P
2
t
a
n
g
e
n
t

a
t

p
i =

s
(
p
i+
1
-
p
i-
1
)

26. 1
8
C
a
t
m
u
l
l
-
R
o
m

S
p
l
i
n
e
s
•
U
s
e
f
o
r

t
h
e
r
o
l
l
e
r
-
c
o
a
s
t
e
r
(
n
e
x
t
p
r
o
g
r
a
m
m
i
n
g

a
s
s
i
g
n
m
e
n
t
)
•
W
i
t
h

H
e
r
m
i
t
e
s
p
l
i
n
e
s
, t
h
e
d
e
s
i
g
n
e
r

m
u
s
t
a
r
r
a
n
g
e
f
o
r

c
o
n
s
e
c
u
t
i
v
e
t
a
n
g
e
n
t
s

t
o
b
e
c
o
l
l
i
n
e
a
r
, t
o
g
e
t
C
1
c
o
n
t
i
n
u
i
t
y
. T
h
i
s
g
e
t
s
t
e
d
i
o
u
s
.
•
C
a
t
m
u
l
l
-
R
o
m
:
a
n
i
n
t
e
r
p
o
l
a
t
i
n
g
c
u
b
i
c
s
p
l
i
n
e
w
i
t
h
b
u
i
l
t
-
i
n
C
1
c
o
n
t
i
n
u
i
t
y
.
c
h
a
lk
b
o
a
r
d

27. 1
9
C
a
t
m
u
l
l
-
R
o
m

S
p
l
i
n
e
M
a
t
r
i
x
c
o
n
t
r
o
l
v
e
c
t
o
r
C
R

b
a
s
i
s
s
p
l
i
n
e
c
o
e
f
f
i
c
i
e
n
t
s
[
]
!!!! "#
$$$$ %&
!!!! "#
$$$$ %&
!
!
!
!
!
!
!
=
4321
2
3
0
0
1
0
0
0
2
3
3
2
2
2
1
)
(
pppp
s
s
s
s
s
s
s
s
s
s
u
u
u
u
p
•
D
e
r
i
v
e
d

s
i
m
i
l
a
r
l
y

t
o

H
e
r
m
i
t
e
•
P
a
r
a
m
e
t
e
r

s

i
s

t
y
p
i
c
a
l
l
y

s
e
t

t
o

s
=
1
/
2
.

28. 2
0
C
a
t
m
u
l
l
-
R
o
m

S
p
l
i
n
e
M
a
t
r
i
x
[
]
[
]
!!!! "#
$$$$ %&
!!!! "#
$$$$ %&
!
!
!
!
!
!
!
=
4
4
4
3
3
3
2
2
2
1
1
1
2
3
0
0
1
0
0
0
2
3
3
2
2
2
1
z
y
x
z
y
x
z
y
x
z
y
x
s
s
s
s
s
s
s
s
s
s
u
u
u
z
y
x
c
o
n
t
r
o
l
v
e
c
t
o
r
C
R

b
a
s
i
s
s
p
l
i
n
e
c
o
e
f
f
i
c
i
e
n
t
s

29. 9
C
a
t
m
u
l
l
-
R
o
m

S
p
l
i
n
e
s
•
U
s
e
f
o
r

t
h
e
r
o
l
l
e
r
-
c
o
a
s
t
e
r
a
s
s
i
g
n
m
e
n
t
•
W
i
t
h

H
e
r
m
i
t
e
s
p
l
i
n
e
s
, t
h
e
d
e
s
i
g
n
e
r

m
u
s
t
s
p
e
c
i
f
y
a
l
l
t
h
e

t
a
n
g
e
n
t
v
e
c
t
o
r
s
•
C
a
t
m
u
l
l
-
R
o
m
:
a
n
i
n
t
e
r
p
o
l
a
t
i
n
g
c
u
b
i
c
s
p
l
i
n
e
w
i
t
h
b
u
i
l
t
-
i
n
C
1
c
o
n
t
i
n
u
i
t
y
.

30. 1
0
C
a
t
m
u
l
l
-
R
o
m

S
p
l
i
n
e
M
a
t
r
i
x
c
o
n
t
r
o
l
v
e
c
t
o
r
C
R

b
a
s
i
s
[
]
!!!! "#
$$$$ %&
!!!! "#
$$$$ %&
!
!
!
!
!
!
!
=
4321
2
3
0
0
1
0
0
0
2
3
3
2
2
2
1
)
(
pppp
s
s
s
s
s
s
s
s
s
s
u
u
u
u
p
•
D
e
r
i
v
e
d

s
i
m
i
l
a
r
l
y

t
o

H
e
r
m
i
t
e
•
P
a
r
a
m
e
t
e
r

s

i
s

t
y
p
i
c
a
l
l
y

s
e
t

t
o

s
=
1
/
2
.

31. 1
1
C
u
b
i
c

C
u
r
v
e
s

i
n

3
D
•
T
h
r
e
e
c
u
b
i
c

p
o
l
y
n
o
m
i
a
l
s
, o
n
e

f
o
r
e
a
c
h
c
o
o
r
d
i
n
a
t
e
–
x
(
u
)

=

a
x
u
3
+
b
x
u
2
+
c
x
u
+
d
x
–
y
(
u
)

=

a
y
u
3
+
b
y
u
2
+
c
y
u
+
d
y
–
z
(
u
)

=

a
z
u
3
+
b
z
u
2
+
c
zu
+
d
z
•
I
n

m
a
t
r
i
x
n
o
t
a
t
i
o
n
[
]
[
]
!!!! "#
$$$$ %&
=
z
y
x
z
y
x
z
y
x
z
y
x
d
d
d
c
c
c
b
b
b
a
a
a
u
u
u
u
z
u
y
u
x
1
)
(
)
(
)
(
2
3

32. 1
2
C
a
t
m
u
l
l
-
R
o
m

S
p
l
i
n
e
M
a
t
r
i
x

i
n

3
D
[
]
[
]
!!!! "#
$$$$ %&
!!!! "#
$$$$ %&
!
!
!
!
!
!
!
=
4
4
4
3
3
3
2
2
2
1
1
1
2
3
0
0
1
0
0
0
2
3
3
2
2
2
1
)
(
)
(
)
(
z
y
x
z
y
x
z
y
x
z
y
x
s
s
s
s
s
s
s
s
s
s
u
u
u
u
z
u
y
u
x
c
o
n
t
r
o
l
v
e
c
t
o
r
C
R

b
a
s
i
s

33. Outline
•Hermite Splines
•Catmull-Rom Splines
•Bezier Curves
•Higher Continuity: Natural and B-Splines
•Drawing Splines

34. Problem with
Catmull-Rom Splines?
•No control of derivatives at endpoints!
•How can we solve this?
•We want something intuitive.

35. 1
3
B
e
z
i
e
r

C
u
r
v
e
s
*
•
A
n
o
t
h
e
r
v
a
r
i
a
n
t
o
f
t
h
e
s
a
m
e
g
a
m
e
•
I
n
s
t
e
a
d
o
f
e
n
d
p
o
i
n
t
s
a
n
d
t
a
n
g
e
n
t
s
,
f
o
u
r
c
o
n
t
r
o
l
p
o
i
n
t
s
–
p
o
i
n
t
s

P
0

a
n
d

P
3

a
r
e

o
n

t
h
e

c
u
r
v
e
:

P
(
u
=
0
)

=

P
0
,






P
(
u
=
1
)

=

P
3

–
p
o
i
n
t
s

P
1

a
n
d

P
2

a
r
e

o
f
f

t
h
e

c
u
r
v
e
–
P
'
(
u
=
0
)

=

3
(
P
1
-
P
0
)
,


P
'
(
u
=
1
)

=

3
(
P
3

–
P
2
)
•
C
o
n
v
e
x
H
u
l
l
p
r
o
p
e
r
t
y
–
c
u
r
v
e

c
o
n
t
a
i
n
e
d
w
i
t
h
i
n

c
o
n
v
e
x

h
u
l
l
o
f

c
o
n
t
r
o
l

p
o
i
n
t
s

•
G
i
v
e
s

m
o
r
e

c
o
n
t
r
o
l

k
n
o
b
s

(
s
e
r
i
e
s

o
f

p
o
i
n
t
s
)

t
h
a
n

H
e
r
m
i
t
e
•
S
c
a
l
e

f
a
c
t
o
r

(
3
)

i
s

c
h
o
s
e
n

t
o

m
a
k
e

“
v
e
l
o
c
i
t
y
”
a
p
p
r
o
x
i
m
a
t
e
l
y

c
o
n
s
t
a
n
t

36. Bezier Spline Example

37. 1
4
T
h
e

B
e
z
i
e
r

S
p
l
i
n
e
M
a
t
r
i
x
*
[
]
[
]
!!!! "#
$$$$ %&
!!!! "#
$$$$ %&
!
!
!
!
=
4
4
4
3
3
3
2
2
2
1
1
1
2
3
0
0
0
1
0
0
3
3
0
3
6
3
1
3
3
1
1
z
y
x
z
y
x
z
y
x
z
y
x
u
u
u
z
y
x
B
e
z
i
e
r

b
a
s
i
s
B
e
z
i
e
r
c
o
n
t
r
o
l

v
e
c
t
o
r

38. 1
5
B
e
z
i
e
r

B
l
e
n
d
i
n
g

F
u
n
c
t
i
o
n
s
*
A
l
s
o

k
n
o
w
n

a
s

t
h
e

o
r
d
e
r

4
,

d
e
g
r
e
e

3

B
e
r
n
s
t
e
i
n

p
o
l
y
n
o
m
i
a
l
s
N
o
n
n
e
g
a
t
i
v
e
,

s
u
m

t
o

1
T
h
e

e
n
t
i
r
e

c
u
r
v
e

l
i
e
s

i
n
s
i
d
e

t
h
e

p
o
l
y
h
e
d
r
o
n

b
o
u
n
d
e
d

b
y

t
h
e

c
o
n
t
r
o
l

p
o
i
n
t
s

39. Outline
•Hermite Splines
•Catmull-Rom Splines
•Bezier Curves
•Higher Continuity: Natural and B-Splines
•Drawing Splines

40. 1
6
P
i
e
c
e
w
i
s
e

P
o
l
y
n
o
m
i
a
l
s
•
S
p
l
i
n
e
:

l
o
t
s
o
f
l
i
t
t
l
e
p
o
l
y
n
o
m
i
a
l
s
p
i
e
c
e
d
t
o
g
e
t
h
e
r
•
W
a
n
t

t
o

m
a
k
e
s
u
r
e
t
h
e
y

f
i
t

t
o
g
e
t
h
e
r
n
i
c
e
l
y
C
o
n
t
i
n
u
o
u
s

i
n

p
o
s
i
t
i
o
n
C
o
n
t
i
n
u
o
u
s

i
n

p
o
s
i
t
i
o
n

a
n
d

t
a
n
g
e
n
t

v
e
c
t
o
r
C
o
n
t
i
n
u
o
u
s

i
n

p
o
s
i
t
i
o
n
,
t
a
n
g
e
n
t
,
a
n
d

c
u
r
v
a
t
u
r
e

41. 1
7
S
p
l
i
n
e
s
w
i
t
h

M
o
r
e

C
o
n
t
i
n
u
i
t
y
?
•
H
o
w
c
o
u
l
d
w
e
g
e
t
C
2
c
o
n
t
i
n
u
i
t
y
a
t
c
o
n
t
r
o
l
p
o
i
n
t
s
?
•
P
o
s
s
i
b
l
e
a
n
s
w
e
r
s
:
–
U
s
e

h
i
g
h
e
r

d
e
g
r
e
e

p
o
l
y
n
o
m
i
a
l
s
d
e
g
r
e
e

4

=

q
u
a
r
t
i
c
,

d
e
g
r
e
e

5

=

q
u
i
n
t
i
c
,

…
b
u
t

t
h
e
s
e

g
e
t

c
o
m
p
u
t
a
t
i
o
n
a
l
l
y

e
x
p
e
n
s
i
v
e
,

a
n
d

s
o
m
e
t
i
m
e
s

w
i
g
g
l
y
–
G
i
v
e

u
p

l
o
c
a
l

c
o
n
t
r
o
l



n
a
t
u
r
a
l

c
u
b
i
c

s
p
l
i
n
e
s
A

c
h
a
n
g
e

t
o

a
n
y

c
o
n
t
r
o
l

p
o
i
n
t

a
f
f
e
c
t
s

t
h
e

e
n
t
i
r
e

c
u
r
v
e
–
G
i
v
e

u
p

i
n
t
e
r
p
o
l
a
t
i
o
n



c
u
b
i
c

B
-
s
p
l
i
n
e
s
C
u
r
v
e

g
o
e
s

n
e
a
r
,

b
u
t

n
o
t

t
h
r
o
u
g
h
,

t
h
e

c
o
n
t
r
o
l

p
o
i
n
t
s

42. 1
8
C
o
m
p
a
r
i
s
o
n

o
f

B
a
s
i
c

C
u
b
i
c

S
p
l
i
n
e
s
T
y
p
e
L
o
c
a
l
C
o
n
t
r
o
l
C
o
n
t
i
n
u
i
t
y
I
n
t
e
r
p
o
l
a
t
i
o
n
H
e
r
m
i
t
e
Y
E
S
C
1
Y
E
S
B
e
z
i
e
r

Y
E
S


C
1
Y
E
S
C
a
t
m
u
l
l
-
R
o
m
Y
E
S

C
1
Y
E
S
N
a
t
u
r
a
l

N
O
C
2
Y
E
S
B
-
S
p
l
i
n
e
s
Y
E
S
C
2
N
O
•
S
u
m
m
a
r
y
–
C
a
n
’
t

g
e
t

C
2
,
i
n
t
e
r
p
o
l
a
t
i
o
n
a
n
d
l
o
c
a
l

c
o
n
t
r
o
l
w
i
t
h

c
u
b
i
c
s

43. 1
9
N
a
t
u
r
a
l

C
u
b
i
c

S
p
l
i
n
e
s
*
•
I
f
y
o
u
w
a
n
t
2
n
d
d
e
r
i
v
a
t
i
v
e
s
a
t
j
o
i
n
t
s
t
o

m
a
t
c
h
u
p
, t
h
e

r
e
s
u
l
t
i
n
g
c
u
r
v
e
s
a
r
e
c
a
l
l
e
d
n
a
t
u
r
a
l
c
u
b
i
c
s
p
l
i
n
e
s
•
I
t
’
s
a
s
i
m
p
l
e
c
o
m
p
u
t
a
t
i
o
n

t
o
s
o
l
v
e
f
o
r
t
h
e
c
u
b
i
c
s
'

c
o
e
f
f
i
c
i
e
n
t
s
.

(
S
e
e

N
u
m
e
r
i
c
a
l
R
e
c
i
p
e
s
i
n
C
b
o
o
k

f
o
r

c
o
d
e
.)
•
F
i
n
d
i
n
g
a
l
l
t
h
e
r
i
g
h
t
w
e
i
g
h
t
s
i
s
a
g
l
o
b
a
l
c
a
l
c
u
l
a
t
i
o
n

(
s
o
l
v
e
t
r
i
d
i
a
g
o
n
a
l
l
i
n
e
a
r
s
y
s
t
e
m
)

44. 2
0
B
-
S
p
l
i
n
e
s
*
•
G
i
v
e
u
p
i
n
t
e
r
p
o
l
a
t
i
o
n
–
t
h
e
c
u
r
v
e
p
a
s
s
e
s

n
e
a
r
t
h
e
c
o
n
t
r
o
l
p
o
i
n
t
s
–
b
e
s
t
g
e
n
e
r
a
t
e
d
w
i
t
h
i
n
t
e
r
a
c
t
i
v
e
p
l
a
c
e
m
e
n
t

(
b
e
c
a
u
s
e

i
t
’
s

h
a
r
d

t
o

g
u
e
s
s
w
h
e
r
e

t
h
e

c
u
r
v
e

w
i
l
l

g
o
)
•
C
u
r
v
e
o
b
e
y
s
t
h
e
c
o
n
v
e
x
h
u
l
l
p
r
o
p
e
r
t
y
•
C
2
c
o
n
t
i
n
u
i
t
y
a
n
d

l
o
c
a
l

c
o
n
t
r
o
l
a
r
e

g
o
o
d

c
o
m
p
e
n
s
a
t
i
o
n
f
o
r
l
o
s
s
o
f
i
n
t
e
r
p
o
l
a
t
i
o
n

45. 2
1
B
-
S
p
l
i
n
e
B
a
s
i
s
*
•
W
e

a
l
w
a
y
s

n
e
e
d

3

m
o
r
e

c
o
n
t
r
o
l

p
o
i
n
t
s

t
h
a
n

s
p
l
i
n
e
p
i
e
c
e
s
!!!! "#
$$$$ %&
=
!!!! "#
$$$$ %&
!
!
!
!
=
!!! i
iii
B
s
B
s
P
PPP
G
M
i
123
0
1
4
1
0
3
0
3
0
3
6
3
1
3
3
1
61

46. Outline
•Hermite Splines
•Catmull-Rom Splines
•Bezier Curves
•Higher Continuity: Natural and B-Splines
•Drawing Splines

47. 2
2
H
o
w

t
o

D
r
a
w

S
p
l
i
n
e
C
u
r
v
e
s
•
B
a
s
i
s

m
a
t
r
i
x
e
q
n
.
a
l
l
o
w
s
s
a
m
e
c
o
d
e

t
o
d
r
a
w
a
n
y
s
p
l
i
n
e
t
y
p
e
•
M
e
t
h
o
d
1
:

b
r
u
t
e
f
o
r
c
e
–
C
a
l
c
u
l
a
t
e

t
h
e

c
o
e
f
f
i
c
i
e
n
t
s
–
F
o
r

e
a
c
h

c
u
b
i
c

s
e
g
m
e
n
t
,

v
a
r
y

u
f
r
o
m

0
t
o
1
(
f
i
x
e
d

s
t
e
p

s
i
z
e
)
–
P
l
u
g
i
n

u
v
a
l
u
e
,

m
a
t
r
i
x

m
u
l
t
i
p
l
y
t
o

c
o
m
p
u
t
e

p
o
s
i
t
i
o
n
o
n

c
u
r
v
e
–
D
r
a
w
l
i
n
e

s
e
g
m
e
n
t

f
r
o
m

l
a
s
t

p
o
s
i
t
i
o
n

t
o

c
u
r
r
e
n
t

p
o
s
i
t
i
o
n
[
]
[
]
!!!! "#
$$$$ %&
!!!! "#
$$$$ %&
!
!
!
!
!
!
!
=
4
4
4
3
3
3
2
2
2
1
1
1
2
3
0
0
1
0
0
0
2
3
3
2
2
2
1
z
y
x
z
y
x
z
y
x
z
y
x
s
s
s
s
s
s
s
s
s
s
u
u
u
z
y
x
c
o
n
t
r
o
l
v
e
c
t
o
r
C
R

b
a
s
i
s

48. 2
3
H
o
w

t
o

D
r
a
w

S
p
l
i
n
e
C
u
r
v
e
s
•
W
h
a
t
’
s
w
r
o
n
g
w
i
t
h
t
h
i
s
a
p
p
r
o
a
c
h
?
–
D
r
a
w
s
i
n

e
v
e
n

s
t
e
p
s
o
f

u
–
E
v
e
n

s
t
e
p
s

o
f

u




!!!!
e
v
e
n

s
t
e
p
s

o
f
x
–
L
i
n
e

l
e
n
g
t
h
w
i
l
l

v
a
r
y
o
v
e
r

t
h
e

c
u
r
v
e
–
W
a
n
t

t
o

b
o
u
n
d
l
i
n
e
l
e
n
g
t
h
»
t
o
o

l
o
n
g
:


c
u
r
v
e

l
o
o
k
s

j
a
g
g
e
d
»
t
o
o

s
h
o
r
t
:


c
u
r
v
e

i
s

s
l
o
w

t
o

d
r
a
w

49. 2
4
D
r
a
w
i
n
g

S
p
l
i
n
e
s
,

2
•
M
e
t
h
o
d
2
:
r
e
c
u
r
s
i
v
e
s
u
b
d
i
v
i
s
i
o
n
-
v
a
r
y

s
t
e
p

s
i
z
e

t
o

d
r
a
w

s
h
o
r
t

l
i
n
e
s
S
u
b
d
i
v
i
d
e
(
u
0
,
u
1
,
m
a
x
l
i
n
e
l
e
n
g
t
h
)
u
m
i
d
=

(
u
0

+

u
1
)
/
2
x
0

=

P
(
u
0
)
x
1

=

P
(
u
1
)
i
f

|
x
1

-
x
0
|

>

m
a
x
l
i
n
e
l
e
n
g
t
h
S
u
b
d
i
v
i
d
e
(
u
0
,
u
m
i
d
,
m
a
x
l
i
n
e
l
e
n
g
t
h
)
S
u
b
d
i
v
i
d
e
(
u
m
i
d
,
u
1
,
m
a
x
l
i
n
e
l
e
n
g
t
h
)
e
l
s
e

d
r
a
w
l
i
n
e
(
x
0
,
x
1
)
•
V
a
r
i
a
n
t
o
n
M
e
t
h
o
d
2
-
s
u
b
d
i
v
i
d
e

b
a
s
e
d
o
n

c
u
r
v
a
t
u
r
e
–
r
e
p
l
a
c
e

c
o
n
d
i
t
i
o
n

i
n
“
i
f
”
s
t
a
t
e
m
e
n
t

w
i
t
h

s
t
r
a
i
g
h
t
n
e
s
s

c
r
i
t
e
r
i
o
n
–
d
r
a
w
s

f
e
w
e
r

l
i
n
e
s

i
n

f
l
a
t
t
e
r

r
e
g
i
o
n
s

o
f

t
h
e

c
u
r
v
e

50. 2
5
I
n

S
u
m
m
a
r
y
.
.
.
•
S
u
m
m
a
r
y
:
–
p
i
e
c
e
w
i
s
e

c
u
b
i
c

i
s

g
e
n
e
r
a
l
l
y

s
u
f
f
i
c
i
e
n
t
–
d
e
f
i
n
e

c
o
n
d
i
t
i
o
n
s

o
n

t
h
e

c
u
r
v
e
s

a
n
d

t
h
e
i
r

c
o
n
t
i
n
u
i
t
y
•
T
h
i
n
g
s
t
o

k
n
o
w
:
–
b
a
s
i
c

c
u
r
v
e

p
r
o
p
e
r
t
i
e
s

(
w
h
a
t

a
r
e

t
h
e

c
o
n
d
i
t
i
o
n
s
,
c
o
n
t
r
o
l
s
,

a
n
d

p
r
o
p
e
r
t
i
e
s

f
o
r

e
a
c
h

s
p
l
i
n
e
t
y
p
e
)
–
g
e
n
e
r
i
c

m
a
t
r
i
x

f
o
r
m
u
l
a

f
o
r

u
n
i
f
o
r
m

c
u
b
i
c

s
p
l
i
n
e
s
x
(
u
)

=

u
B
G
–
g
i
v
e
n

d
e
f
i
n
i
t
i
o
n
d
e
r
i
v
e

a

b
a
s
i
s

m
a
t
r
i
x