1
Interpolare cu funcţii spline
Curbele pot fi reprezentate în plan prin: _________________ ________________
• ecuaţii explicite: De exemplu y=(r2-x2) şi y=-(r2-x2)
reprezintă un cerc cu centrul în origine, de rază r
• ecuaţii implicite: x2+y2=r2
• ecuaţii parametrice: x(t)=r cos t şi y(t)=r sin t
Reprezentarea prin ecuaţii explicite, de forma y=f(x) şi nici ecuaţiile implicite nu
asigură reprezentarea curbelor având mai multe valori într-un punct (nu sunt funcţii).
f(p)=f(x,y)=0 nu tratează corect tangentele verticale la curbă.
Forma parametrică:
• este mult mai flexibilă
• permite reprezentarea de curbe care nu sunt funcţii (au mai multe valori într-un
punct)
• este independentă de coordonate
Specificarea unei curbe se face prin:
• puncte de control – mulţime de puncte care influienţează forma curbei
• noduri – puncte de control care se află pe curbă
Un spline este o curbă parametrică definită prin puncte de control.
• Un spline este o funcţie S:[a, b) R, definită local pe mai multe intervale
prin Pi:[ti, ti+1) R, cu a=t0 < t1 <...< tk-1 =b
S(t)=P0(t), t0 t < t1
S(t)=P1(t), t1 t < t2
S(t)=Pk-2(t), tk-2 t < tk-1
• Funcţiile pi(t) sunt de regulă polinoame de grad 3
• Nodurile ti se aleg deobicei echidistante, definind un spline uniform
• Dacă în vecinătatea nodurilor ti, SCri, atunci spline-ul are netezimea Cri.
(adică spline-urile Pi-1 şi Pi au aceleaşi derivate de ordin 0 până la ri)
• Splineul de grad 0 este splineul treaptă, cel de ordin 1 este spline liniar şi
coincide cu poligonul punctelor de control.
• Un spline utilizat – spline-ul cubic natural are gradul 3 şi continuitatea C2. În
plus, la capete: S”(a)= S”(b) = 0.
• Splineurile de grad n utilizate în analiza numerică au continuitatea S(t)Cn-1 [a,b]
• Splineurile utilizate în Adobe şi PostScript au continuitatea S(t) C1[a,b]
• Pentru asigurarea continuităţii C2, funcţiile spline trebuie să aibă cel puţin gradul 3
• Funcţiile spline pot fi:
• funcţii spline de interpolare – care trec prin toate punctele de control
• funcţii spline de aproximare – care nu trec prin toate punctele de control
tyy
txx)t(p
2
Funcţii spline de interpolare în clasă C1.
Vom alege polinoame de interpolare de grad mic, valabile pe subintervale
x0 < x1 < … < xn
f(x0),f(x1),…,f(xn)
şi vom considera funcţii de interpolare liniare, locale pe subintervalele
[x0,x1],[x1,x2],…,[xn-1,xn]
pi(x)=aix+bi, i=0:n-1
în care cei 2n parametri se determină din condiţiile de interpolare:
pi(xi)=f(xi), i=0:n-1
pn-1(xn)=f(xn)
şi a condiţiilor de racordare (continuitate în punctele interioare):
pi(xi+1)=pi+1(xi+1), i=0:n-2
Interpolarea liniară prezintă dezavantajul discontinuităţii derivatelor în punctele
interioare.
Prin alegerea unor funcţii de interpolare de gradul 3 se poate realiza o interpolare
Hermite, care presupune şi fixarea valorii derivatelor pe suportul interpolării:
f’(x0),f’(x1),…,f’(xn)
O funcţie spline cubică se exprimă sub forma:
1n:0i,
xx
xfxfa
i1i
i1i
i
i1i
1iii1i
ixx
xfxxfxb
3
Si(x)=ai+bi(x-xi)+ci(x-xi)2+di(x-xi)
3
sau parametric
Si(t)=ai+bihit+cihi2t2+dihi
3t3, t[0,1]
în care s-a notat hi=xi+1-xi şi s-a efectuat schimbarea de variabilă:
Baza Bernstein : cu t [0,1]
reduce volumul de calcule necesar determinării coeficienţilor.
Avem 2n+2 condiţii de interpolare de tip Hermite:
si(xi)=f(xi)
s’i(xi)=f’(xi), i=0:n
şi 2n-2 condiţii de racordare (continuitate şi derivabilitate în punctele interioare):
si(xi+1)=si+1(xi+1)
s’i(xi+1)=s’i+1(xi+1), i=0:n-2
Eroarea interpolării pentru funcţiile spline în clasă C1 este:
Funcţii spline de interpolare în clasă C2.
Considerăm numai n+1 condiţii de interpolare de tip Lagrange:
si(xi)=f(xi), i=0:n-1
sn-1(xn)=f(xn)
rezultă:
ai=f(xi), i=0:n-1
i
i
i1i
i
h
xx
xx
xxt
3223t,t1t3,t1t3,t1
3
i
2
i
2
i
3
ii tdt1tc3t1tb3t1ats
ii xfa
i
i
ii xf3
hxfb
1ii xfd
1i
i
1ii xf3
hxfc
3
1i
2
1i1i
2
iii
3
ii tyt1tyhy3t1tyhy3t1yts
ξf
!2n2
xxxxxE
2n2
2
n
2
0
24
ξfht1tξf
!4
xxxxxE
4422
4
2
1
2
0
384
hM
24
ξfh2/12/1xE
4
4
4422
nn
3
1n1n
2
1n1n1n1n1n axfhdhchba
n:0i,xfa ii
4
Dispunem de mai multe grade de libertate pentru condiţiile de racordare: continuitatea
valorilor şi a derivatelor de ordinul 1 şi 2 în punctele interioare
pe care o prelungim cu i=0:n-1, introducând notaţia
s-au obţinut astfel 4n-2 relaţii, mai putem impune 2 condiţii suplimentare
care definesc funcţiile spline naturale
pentru funcţii spline tensionate.
1i1i1ii xsxs
3
ii
2
iiiii1i hdhchbaa 2n:0i
2iiiiii xxd3xxc2bxs
1i1i1ii xsxs
2n:0i
2
iiiii1i hd3hc2bb
iiii xxd6c2xs
1i1i1ii xsxs
iii1i hd3cc
1n1n1nn hd3cc
0xS,0xS n1n00
nn1n000 xfxS,xfxS
1n:0i,xfa ii
1n:0i,h3
ccd
i
i1i
i
1n:1i,h3
c2c
h
aab 1i
i1i
1i
1ii
i
1i
1ii
i
i1i
1iiii1i1i1ih
aa3
h
aa3chchh2ch
0c0xxd6c2xS 0000000
0c0c2hd6c2xS nn1n1n1nn1n
n
1n
1
0
n
1n
1
0
1n
1n1n2n2n
1100
0
g
g
g
g
c
c
c
c
h00
hhh2h
0hhh2h
000h
3
1n1n
2
1n1n1n1n1nn hdhchbaa
2
1n1n1n1n1nn hd3hc2bb
5
0
h
aa3
h
aa3
h
aa3
h
aa30
g
g
g
g
2n
2n1n
1n
1nn
0
01
1
12
n
1n
1
0
00
2
000000000 xfbxxd3xxc2bxS
010
0
0
01
0 xfcc23
h
h
aab
0
01
01000h
aaxf3chch2
nn
2
1n1n1n1n1nn1n xfbhd3hc2bxS
,chchcc23
h
h
aa
hcchc2bxfb
n1n1n1nn1n
1n
1n
1nn
1n1nn1n1n1nnn
1nn
1n
nn1n1n1n aah
3xf3ch2ch
n
1n
1
0
n
1n
1
0
1n1n
1n1n2n2n
1100
00
g
g
g
g
c
c
c
c
h2h0
hhh2h
0hhh2h
00hh2
1n
1nn
n
2n
2n1n
1n
1nn
0
01
1
12
0
0
01
n
1n
1
0
h
aa3xf3
h
aa3
h
aa3
h
aa3
h
aa3
xf3h
aa3
g
g
g
g
6
Curbe Hermite.
O curbă Hermite este o cubică exprimată parametric prin:
• Q(t)= at3+bt2+ct +d
d
c
b
a
ttt 123
• Q’(t)=3at2+2bt+c
d
c
b
a
tt 1230 2
Vom impune ca restricţii valorile la capete (Q(0)=P1, Q(1)=P2) şi valorile derivatelor
la capete ( 21 10 PQPQ , )
Vectorul de control (sau geometria) este :
Q(0)=d a=2P1-2P2+P1’+P2’
Q(1)=a+b+c+d b=-3P1+3P2-2P1’-P2’
Q’(0)=c c=P1’
Q’(1)=3a+2b d=P1
Q(t)=(2t3-3t2+1)P1+(-2t3+3t2)P2+(t
3-2t2+t)P1’+(t3-t2)P2’
Ultima expresie evidenţiază contribuţia fiecărui punct de control asupra formei curbei,
prin intermediul unor funcţii de îmbinare (blending functions):
'
'
2
1
2
1
P
P
P
P
GH
d
c
b
a
tttdctbtattQ 12323
HH
T
controlde
vectorM
baza
GMT
P
P
P
P
ttttQ
H
'
'
2
1
2
1
23
0001
0100
1233
1122
1
'
'
2
1
2
1
23232323 232132
P
P
P
P
ttttttttttQ
7
Spline Hermite.
Reprezintă curbe Hermite alăturate, în punctele de joncţiune asigurându-se continuitate
C0 şi C1. Aceasta reduce numărul gradelor de libertate în alegerea punctelor de control.
Astfel dacă considerăm două curbe Hermite cu geometriile (P1, P2, P’1, P’2) şi
(Q1, Q2, Q’1, Q’2) continuitatea în joncţiune impune Q1=P2, iar derivabilitatea
Q’1=P’2, deci a doua curbă are numai două puncte de control independente.
Polinoame Bernstein.
Sunt generate din dezvoltarea [t+(1-t)]n
Proprietăţile polinoamelor Bernstein:
• Nenegativitatea
• Partiţia unităţii
n
i
n
i tB0
1
• Simetria
• Maxim unic t=i/n în [0,1]
• Formula de recurenţă
• Derivare
n:0i,t1ti
ntB
inin
i
]1,0(t,0Bn
i
t1BtBn
in
n
i
n:0i,tBttBt1tB1n
1i
1n
i
n
i
nitnB
ni0tBtBn
0inB
tBdt
d
1n
1n
1n
i
1n
1i
1n
i
n
i
8
Curbe Bézier
Curba Bézier de grad n este definită pentru n+1 puncte de control: P0, P1,...,Pn prin:
în care funcţiile de îmbinare sunt polinoame Bernstein.
Poligonul punctelor de control P0P1...Pn se numeşte poligon Bézier . Poligonul Bézier
conţine în interiorul lui curba Bézier
Proprietăţi ale curbelor Bézier:
• proprietatea punctelor de capăt – curba începe în P0 şi se termină în Pn
• curba Bézier este lineară numai dacă punctele de control sunt coliniare
• curba Bézier este tangentă segmentelor P0P1 şi Pn-1Pn.
• o curbă Bézier este conţinută complet în înfăşurătoarea convexă a punctelor de
control.
• O curbă Bézier poate fi separată în alte două curbe Bézier.
• Transformările afine (translaţia şi rotaţia) aplicată punctelor de control are acelaşi
efect cu aplicarea transformării afine asupra curbei
Curba Bézier cubică are forma parametrică:
Q(t)= P0(1-t)3+3P1t(1-t)
2+3P2t2(1-t)+ P3t
3, t[0,1]
3
2
1
0
23
0001
0033
0363
1331
1
P
P
P
P
ttttQ
Postscript şi GIMP folosesc pentru reprezentarea literelor curbe Bézier cubice.
Curba Bézier cubică este determinată de 4 puncte de control.
Spline-urile cubice Bézier folosesc în locul derivatelor două puncte suplimentare de
control.
Punctele de control suplimentare determină derivatele, şi asigură un control mai eficient
decât cel prin derivate
Derivatele la capete (în P0 şi P3)se exprimă se exprimă folosind celelalte două puncte de
control prin:
P1’=3(P1-P0)
100
,,
ttBPtBn
i
n
ii
9
P2’=3(P3-P2)
Putem face trecerea între vectorii de control Hermite şi Bézier:
BezierHermite GG
P
P
P
P
P
P
P
P
3
2
1
0
2
1
2
1
3300
0033
1000
0001
BezierHermite
GM
P
P
P
P
d
c
b
a
3
2
1
0
3300
0033
1000
0001
0001
0100
1233
1122
BezierBezier
GM
P
P
P
P
d
c
b
a
3
2
1
0
0001
0033
0363
1331
Funcţiile de îmbinare pentru spline-ul Bézier sunt polinoamele Bernstein B3i, i=0:3
3
2
1
0
3
2
2
3
13
13
1
P
P
P
P
t
tt
tt
t
tp
T
Polinoamele Bernstein au proprietăţile:
• sunt pozitive în [0,1]
• au suma egală cu 1
• curba este o combinaţie convexă a punctelor de control
Dându-se două puncte P0 şi P1, orice punct de pe segmentul P0P1 reprezintă o curbă
Bézier liniară,definită prin:
B1(P0,P1,t)=(1-t)P0+tP1, t[0,1]
Curba Bézier pătratică, determinată de punctele P0şi P2 ca puncte de interpolare şi P1 ca
punct de aproximare se poate calcula, pentru fiecare t prin 3 interpolări liniare:
Pa=B1(P0,P1,t)
Pb=B1(P1,P2,t)
B2(P0,P1,P2,t)=B1(Pa,Pb,t)=B1(B1(P0,P1,t), B1(P1,P2,t),t)
B2(P0,P1,P2,t)=B1[(1-t)P0+tP1, (1-t)P1+tP2]
B2(P0,P1,P2,t)=(1-t)[(1-t)P0+tP1]+t[(1-t)P1+tP2]
B2(P0,P1,P2,t)=(1-t)2P0+2t(1-t)P1+t
2P2, t[0,1]
10
Fonturile TrueType folosesc curbe Bézier pătratice.
Curbele Bézier modelează curbele netede în grafica pe calculator. Cele mai folosite sunt
curbele Bézier pătratice şi cubice. Acestea sunt folosite ca splineuri Bézier pentru a
aproxima alte funcţii
Desenarea curbelor Bézier.
Determinarea unui punct de pe curba Bézier se poate face direct prin aplicarea relaţiei
pentru t şi punctele de control date
unde n
iB este baza polinoamelor Bernstein.
Metoda nu este stabilă numeric, datorită erorilor în evaluarea polinoamelor Bernstein.
Algoritmul De Casteljau utilizează relaţia de recurenţă
cu B(t0)=P0(n)
Fie P0i,i=0:n poligonul punctelor de control P0i şi P0i+1 două puncte succesive şi P1i un
punct care împarte segmentul P0iP0i+1 în raportul t/(1-t):
P1i=P0i+t(P
0i+1-P
0i)=(1-t)P
0i+tP
0i+1
• Se formează în acest fel poligonul P1i, i=0:n-1.
• Se aplică algoritmul noului poligon acelaşi algoritm obţinându-se poligonul
P2i,i=0:n-2. Repetând procesul de n ori se obţine un singur punct Pn0. Acest
punct este punctul cerut
n
i
n
ii tBPtB0
niPP ii :, 00
njjnitPtPP
j
i
j
i
j
i :,:, 101 01
101
11
Algoritmul De Casteljau.
Calculul poate fi exprimat recursiv prin relaţia:
Pij=(1-t)Pi-1
j+tPi-1j+1, i=1 : n, j=0:n-i
şi implementat ineficient prin:
function b=Castrec(P, u, i, j)
if i==1
b=P(1,j);
else
b=(1-u)*Castrec(P,u,i-1,j)+u*Castrec(P,u,i-1,j+1);
Ineficienţa provine din apelurile recursive repetate. Acestea pot fi evitate urmărind
schema de calcul pentru puncte de control succesive.
13
Continuitate C0: P4 = Q1
Continuitate C1 P’4 = Q’1 P4 – P3 = Q2 – Q1
Continuitate C2 P”4 = Q”1 P2-2P3+P4 = Q1-2Q2+Q3
Din cele 3 condiţii rezultă: Q1 = P4
Q2 = 2P4 – P3
Q3 = P2 – 4P3 + 4P4
Cu alte cuvinte pentru cel de-al doilea spline avem un singur grad de libertate.
Spline B
Curbele Bezier nu asigură un control local efectiv, în sensul că modificarea punctelor de
control afectează în mod global forma curbei.
Splineurile B asigură un control local mai bun decât splineurile Bezier.
Splineurile B sunt precizate prin:
m+1 puncte de control P0, P1,…,Pm
m-2 curbe spline B: Q3,…,Qm
Splineul Qi(t) determinat de punctele de control Pi-3, Pi-2, Pi-1, Pi în intervalul
t[ti, ti+1).
Splineurile B uniforme consideră ti+1 = ti + 1.
Un punct de control influienţează cel mult 4 curbe. Astfel avem:
Curba puncte de control Interval Q3 P0, P1, P2, P3 t3=0 t4=1
Q4 P1, P2, P3, P4 t4=1 t5=2
Q5 P2, P3, P4, P5 t5=2 t6=3
Q6 P3, P4, P5, P6 t6=3 t7=4
. . .
Qm Pm-3,Pm-2,Pm-1,Pm tm=m-3 tm+1=m-2
Pentru baza: 123
iii
T
i ttttttT
,BsBs
T
ii GMTtQ t[ti, ti+1), i=3:m
În cazul splineurilor uniforme, obţinerea matricei de transformare MBs se face impunând
condiţii de continuitate pentru: Qi(t)=a(t-ti)
3+b(t-ti)2+c(t-ti)+d
Q’i(t)=3a(t-ti)2+2b(t-ti)+c
Q”i(t)=6a(t-ti)+2b
Q’i(ti)=c=(Pi-1-Pi-3)/2
Q’i(ti+1)=3a+2b+c=(Pi-Pi-2)/2
Q”i(ti)=2b=(Pi-Pi-2)-(Pi-1-Pi-3)
Q”i(ti+1)=6a+2b=(Pi-Pi-1)-(Pi-1-Pi-2)
de unde rezultă:
6
33 123 iii PPP
a
6
363 123 iii PPP
b
14
6
33 13 ii PP
c
Pentru determinarea lui d se impune condiţia suplimentară:
6
4 123 iii
i
PPPdtQ
i
i
i
i
P
P
P
P
d
c
b
a
1
2
3
0141
0303
0363
1331
6
1
i
i
i
i
P
P
P
P
ttttQ1
2
3
23
0141
0303
0363
1331
6
11
splineBB
BsM
0141
0303
0363
1331
6
1
Funcţiile de îmbinare sunt:
32323313334631
6
1tttttttMTB Bs
T
Bs
3
2
132323313334631
6
1
k
k
k
k
P
P
P
P
ttttttttQ
Proprietăţile splineurilor B:
1. control local mai bun – fiecare punct de control are efect local
2. continuitate – curba de grad n este Cn-1 continuă
3. aproximare – un spline B nu trece prin nici un punct de control
4. curba este conţinută în poligonul P1P2...Pn+1
Se pot defini funcţii spline B de ordin superior:
tNtt
tttN
tt
tttN 1k,1i
1iki
ki
1k,i
i1ki
i
ik
contrarcazin0
ttt1tN
1ii
1i
15
NURBS (Spline B Raţionale NeUniforme).
Se definesc prin relaţiile:
n
0j
1d,jj
1d,kk
k
tNw
tNwtR
În care:
Nk,d – este baza funcţiilor B spline
wk – sunt ponderi (sau parametri de formă)
Proprietăţi:
1. interpolează la capete
2. asigură reprezentări exacte curbelor canonice (cerc, elipsă)
3. sunt invariante la proiecţia perspectivă
Spline cardinale. Sunt spline Hermite, care nu folosesc derivate, care sunt înlocuite prin diferenţele:
Ti=a(Pi+1-Pi-1)
p(0)=Pk
p(1)=Pk+1
p’(0)=a(Pk+1 – Pk-1)
p’(1)=a(Pk+2 – Pk)
CHC
G
k
k
k
k
M
k
k
k
k
H
P
P
P
P
aa
aa
P
P
P
P
G
2
1
1
1
1
00
00
0100
0010
P(t)=T(t).MH.GH=T(t).MH.MHC.GC
2
1
1
23
00
00
0100
0010
0001
0100
1233
1122
1
k
k
k
k
P
P
P
P
aa
aattttp
2
1
1
23
0010
00
2332
22
1
k
k
k
k
P
P
P
P
aa
aaaa
aaaa
ttttp
Spline Catmull-Rom.
Sunt spline cardinale cu a=0.5 Ti=0.5(Pi+1-Pi-1)
Spline-ul Catmull-Rom are proprietăţile:
• trece prin toate punctele de control (spline de interpolare)
16
• este C1 continuu
2
1
1
23
0020
0101
1452
1331
12
1
k
k
k
k
P
P
P
P
ttttp
Spline Kochanek – Bartels Sunt spline Hermite, folosite de 3d-Studio Max cu control mai bun asupra animaţiei.
Calculul tangentelor se face cu relaţiile:
2
1
1
23232323 4325322
1
k
k
k
k
P
P
P
P
tttttttttttq
i1i1iii PP2
b1c1t1PP
2
b1c1t1TS
i1i1iii PP2
b1c1t1PP
2
b1c1t1TD