Curves

Polylines: Piecewise linear approximation to curves

Not Smooth
 Curves

High degree approximation

• Explicit
y=f(x)
• Implicit
f(x,y)=0
• Parametric
x=x(t), y=y(t)
 Curves
Explicit Representation
• y  f (x )

• Essentially a function plot over some interval

x  a,b

• Simple to compute and plot

• Simple to check whether point lies on curve
• Cannot represent closed and multi-value curves
 Curves
Implicit Representation
• Define curves implicitly as solution of equation
system
○ Stra line in : ax  by  c  0
ight 2D
○ Circle of R in 2D : x  y 2  R 2  0
radius 2

○ Conic : Ax 2   Cy  2D  2Ey  F  0
Section 2Bxy 2
x

• Simple to check whether point lies on curve

• Can represent closed and multi-value curves
 Curves
Parametric Curves
• Describe position on the curve by a parameter
uR
b
 2D c(u)  {x(u), y(u)}
Curve
e.g.,line : c(u)  (1 u)a  ub
u
a
0 1

• Hard to check whether point lies on curve

• Simple to render
• Can represent closed and multi-value curves
 Curves
Parametric Curves
Parametric curves form a rich variety of free form
smooth curves
They are modeled as piecewise polynomials and
have two aspects:
• Interpolation
• Approximation

“Splines”
 Curves
Parametric Curves
Splines
 Curves
Parametric Curves
Cubic Splines
P(t )  B1   B3t  B4t t1   t2
B2 t 2 3
t
4
 B t i 1
i i
1

x(t ) 4
  Bi t i 1
i x
1
4
y(t )  B t i 1
i
 y
i 1 4
P'(t )   Bi
(i
i 1  1)t i   t 1  3B4t 2
2
B2 2B3
 Curves
Parametric Curves
Cubic Splines
P 2’

P2 t2
P 1’

P1 t 1 Let t1=0
P(0)=P1, P(t2)=P2
P'(0)=P1’, P’(t2)=P2’
 Curves
Parametric Curves
Cubic Splines
P 2’
P(0)  B1  P1
4
2 P(t2 ) 
P2 t  Bit i
i t t2
1 1
P 1’ BBt1Bt2Bt3P
1 2 2 3 2 4 2 2

4
P'(0) 
 Bi  1)t i   P1'
2
(i t B2
i 1 0
4
P1 t 1 P'(t2 )   Bi  1)t i
2 t t2
(i
i 1
 B  2B t 1  3B t 2  P '
2 3 2 4 2 2
 Curves
Parametric Curves
Cubic Splines
P 2’ Solving fo B B B and B
1 2 3 4
r

P2  P1 ,
tB  P1' ,
P 1’ 2
1
- P1 2P
B2 3(P
 2
' P2'
t) -t
- t
B3 1
2
2 2 2
' '
2(P1 - P2 ) P1 P2
B4  3
 2  2
t2 t2 t2
P1 t 1
Here P1 and P2 give the position of the endpoints
and P1’ and P2’ give the direction of the tangent vectors.
 Curves
Parametric Curves
Cubic Splines
P 2’

P2 t2
 3(P2  P1) 2P1' P2 '  2
P(t )
P 1’  P1  P1' t     t
2
 t2 t2 t2 
 2(P1  P2 ) P1' P2 '  3
P1 t 1  3  2  2 
 t2 2 t 2 t
t
Thus, given the two end-points and the tangent vectors
one can compute the cubic spline.
 Curves
Parametric Curves
Cubic Splines
t3

t2
t1
Joining of Segments
2 SEGMENTS: P1 P2 P3 (Points)
P1’ P2’ P3’ (Tangents)
P2’ is determined through the continuity condition
 Curves
Parametric Curves
Cubic Splines
t3

t2
t1
Piecewise Spline of degree k has continuity
of order (k-1) at the internal joints.

Thus Cubic Splines have second order continuity

i.e. P2”(t) is continuous over the joint
 Curves
Parametric Curves
Cubic Splines
t3
4
P''(t )  (i  1)  2)Bit i t1   t2
3
(i t
i 1

at t  t2
t2 First segment
t1 P''  6B4t2  2B3
Second segment
P''  2B3
So, 6B4t2  2B3 seg1  2B3 seg 2

Substitute the expressions for B4 and B3

 Curves
Parametric Curves
Cubic Splines
t3

t2
t1
tP
'2(t
 t )P 't P ' 
3
t 2
(P  P )  t P) 
2
(P
3 1 3 2 2 2 3 2 3 2 3 2 1
t2t3
P1'
t 2(t  t
)
t
2
 P '   3 t 2
(P  P )  t P) 
(P
3 3 2 2  2  t t
2 3 2 3 2 1
 2 3
P3 '
 Curves
Parametric Curves
Cubic Splines

In general, for the kth and (k+1)th segment (1 k n-2)

 Pk ' 
 tk 2(tk 1  tk 2 tk Pk 1'
2 ) 1 
 
Pk 2 '
3 2
  t (P  P )  t 2 (P P) 
t t k k k k k 1 k
1 2 1 2
k 1 k 2

Set of n-2 equations form a linear system for the tangent vectors Pk’
 Curves
Parametric Curves
Cubic Splines
t 3 2(t2  t3 ) t2 0 P 1 ' 


… 
0 t4 2(t3  t4 ) t3  P ' 
   2
    
 n1 n1  n
 2(tn   P ' 
 ……… n ) t
t t

2
3
t 2
(P  P )  t P)  
(P
 t t 2 3 3 2 1 
2
2 3


 3
t 2
(P 3
4
 P )  t 2(P  P )  
 t3t4 3 4 3 2
 
 
 3
 t P 
2 (P t
)(P
2 P ) 
 n2 
tn1tn
n1 n1 n n1

n
 Curves
Parametric Curves
Cubic Splines

1 0 ……   P1' 
t  P ' 
3 2(t2  t3 ) t2
   2 
 t4 2(t3  t4 ) t3   
   
 
  


 2(tn  tn1) tn Pn1'
1   P ' 
tn …… 0 1 n 
  P1' 
 


3 2
t (P  P )  t 2(P  P ) 
 2 2 3 2 1 
t 2t 3
3 
  
 



3 2
2
 
tn1tn t n1(Pn


 Pn1 )  t n (Pn1  Pn2 ) 
 Pn ' 
 Curves
Parametric Curves
Cubic Splines

Solving
fo B1 B3 and B4
r B2

B1k  P ,
k
B2k  Pk' ,
3(P - P 2P '
B3k  k 1 k ' P
) - k 1
- tk 1
2
t k 1 k
tk
1
2(Pk - Pk 1 ) P' 1
P'
B4k  2k  k2
t k3 tk t k 1
1 1
 Curves
Parametric Curves
Cubic Splines

B1k
   1 0 0 0   Pk 
B2k     P 
 B  30/ t 1 2 0 0

t 2/ 3/t 
t 1/  P k 
2 '
   k k 1 k 1 k 1  k 1 
3k
 1
  2/t 1/ t
2 2/t
3 1/ t 
2  
B 3 P '
 4k   k k 1 k 1 k 1   k 1 
1

P (t )  4 1i 0   tk 1
t t
B
k  1kn1
ik
i 1
 
 1t t2 t3  B2 B3 B4k 
T

B1k k k
 Curves
Parametric Curves
Cubic Splines

Pk (t )

 1 0 0   Pk 
 1t t
t3   0 0  P ' 
2
1 0   k 
0
 3 / t 2k 2/k 2
3 / k1  1/ k Pk 1 
1
1
 1 t t
2/t3 1/ t
2 2/t
3 1/ t  P '
2

 k 1 k 1 k 1 k 1   k 1 


 (1 3t 2 /
k  2t 3 / t 3 ) (t  2t 2 / k  t 3 / t 3 )
1
t2 1 t
k k
1 1
 k k
2 2
(3t / t

1 1
Pk '
T
k  2t 3 / t 3 ) (t 3 / t t 2 / k ) Pk Pk
3
1 t 1
Pk ' 1 1
 Curves
Parametric Curves
Cubic Splines
Substituting u=t/tk+1 rearranging
P (u)  F (u) F (u) F (u) F (u) P P ' P  '
T
P 
k 1 2 3 4 k k 1 k k1
0u1
1 n1
F1(u) 2u3  3u 2  k
 1
F2 (u)   3u F1 ,F2 ,F3 ,F4 are called the
2
2u3
F3 (u)   2u  1)tk Blending Functions
u(u2 1
F4  u(u2  u)tk 1
(u)
 Curves
Parametric Curves
Cubic Splines

Pk(u)=[F][G]

Where F is the Blending function matrix and G Is the

geometric information.
 Curves
Parametric Curves
Cubic Splines

1
F1 F2 • F1(0)=1,F2(0)=0,F3(0)=0,F4(0)=0
curve passes P1
F3 • F1(1)=0,F2(1)=1,F3(1)=0,F4(1)=0
t=0 curve passes P2
t=1 • F2=1-F1,F4=1-F3
F4 • Relative magnitudes of F1,F2 > F3,F4
 Curves
Parametric Curves
Cubic Splines

Piecewise Cubic Splines are determined by position vectors,

tangent vectors and parameter value tk .

The value of tk can be chosen using either Chord

Length parameterization or Uniform Parameterization.

If tk=1 for all k then the Spline is called Normalized Spline.

 Curves
Parametric Curves
Cubic Splines
Normalized Cubic Splines: tk=1 for all segments
The blending functions thus become
F1(t) = 2t3-3t2+1, F2(t) =
-2t3+3t2 F3(t) = t3-2t2+t , F4(t)
= t3-t2
These are called Hermite Polynomial Blending functions

F1(t )   2 2 1
F (t )  3 3  2 11
 
2 3 2
  t t t 1  
F3(t ) 0 0 1 0
 
 
F (t ) 1 0 0 0
 4   
 Curves
Parametric Curves
Cubic Splines

The tridiagonal system for getting P’ becomes

1 0   P1'   P1' 
  
…… 
  P2 '   3  (P  P 2 )   P )  
 1
1 4 1      3 (P2 
 1 4 1     
      
 

 1 4 1 Pn1'  Pn1)  (Pn1  Pn2 )

3(Pn
    
 1 P '    
…… 0
Pn '


 Curves
Parametric Curves
Cubic Splines
End Conditions as:

• Clamped: P1’,Pn’ known

• Relaxed/Natural: P”(0) = 0
P”(tn)=0
• Cyclic: P1’(0)=Pn’(tn)
P1”(0)=Pn”(tn)

• Anticyclic: P1’(0) = -Pn’(tn)

P1”(0) = -Pn”(tn)