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.

12

Splineurile Bezier se obţin prin joncţiunea de curbe Bezier.

P1

P2 P3

P4Q1

Q2

Q3

Q4

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