Proiectarea formelorFuncii de aproximare

Functii de aproximareCURBE SPLINEIn procesul generarii formelor sunt utilizate o serie de curbe si suprafete trasate pe baza unui set de puncte furnizate de utilizatorAproximarea presupune divizarea unui anume interval intr-o serie de subintervale pentru care se construiesc curbe de aproximareFiecare curba de aproximare are propria expresie analiticaCurburile acestora nu trebuie sa aiba variatii excesive (trebuie sa fie aviate)Cele mai multe dintre functiile de interpolare polinomiala au tendinta de a oscila in jurul punctelor initialeIn general o curba este dificil sa fie definita printr-o singura functie analitica

A. Functii spline cubice

Functii de aproximareFunctii spline cubiceCurba spline are semnificatia fizica a unui flexibil elastic utilizat la trasarea unei curbe printr-un set de puncte dateFortarea flexibilului sa treaca prin punctele date se realizeaza prin intermediul unor greutati (motani)Maniera de fixare a flexibilului poate fi considerata a fi una fixaAnsamblul format din flexibil si motani este asimilat unei grinzi elastice simplu sprijinite

Din teoria liniara a grinzilor se stie ca:Deformata grinzii intre reazeme poate fi reprezentata printr-un polinom de gradul trei Momentele incovoietoare, care sunt proportionale cu derivatele de ordinul al doilea ale deformatei, sunt continue de-a lungul curbei spline, ceea ce inseamna ca spline-ul este o functie continua

Functii de aproximareDerivatele de ordinul al treilea in dreptul reazemelor sunt discontinue, cu exceptia cazului in care fortele din reazeme sunt nuleAceasta caracteristica a functiilor spline cubice este cunoscuta drept proprietatea de curbura minima

Dintre toate curbele de interpolare y(x), spline-ul cubic este curba care minimizeaza integrala

Semnificatia fizica a functiei spline este aceea a unei grinzi elastice, care satisface ecuatia lui Euler:

Functii de aproximareR(x) este raza de curbura a barei elastice:

Deformatia barei (a functiei spline) este presupusa a fi neglijabila (y

Functii de aproximarePrin substituirea lui M(x) in ecuatia lui y(x) se obtine:

Prin integrarea lui y de doua ori, se obtine:

Se da un set de puncte [ti, yi] cu i=1,2n:

Functii de aproximareIn fiecare punct al offset-ului spline-ul cubic se defineste prin [S(ti)=yi].

Fig.40 Curba spline cubica alcatuita din n-1 segmente polinomiale

Rezulta ca pentru cele n puncte exista n-1 intervale. Interpolarea cu spline-uri cubice presupune existenta unei curbe continue care trece prin punctele date si care este compusa din n-1 polinoame de ordinul al treilea cu coeficientii:

Functii de aproximarePentru ca sunt n intervale si patru coeficienti pentru fiecare, este nevoie de un total de 4(n-1) parametri pentru definirea functiei spline S(x). Pentru aceasta trebuie formulate 4(n-1) conditii independente. Prin fortarea polinomului cubic sa aiba valorile din tabel la capetele fiecarui interval, se obtin doua conditii pentru fiecare interval :

Aceste conditii rezulta intr-o serie de functii continue. Mai este nevoie de inca 2n conditii. Pentru ca se doreste ca functiile sa fie aviate, se impune conditia ca prima si a doua derivata sa fie continue:

Aceste conditii se impun pentru i=2,,n-1 si rezulta in 2(n-2) restrictii. Prin urmare este nevoie de inca doua conditii pentru a defini complet spline-ul:

Functii de aproximarePentru fiecare interval [ti, ti+1] distributia derivatei a doua S poate fi reprezentata printr-un segment cu valorile de capat zi respectiv zi+1:

Prin urmare, distributia derivatei a doua poate fi reprezentata prin segmentul:

Functii de aproximareEcuatia anterioara poate fi pusa sub forma:

In final, prin integrare dubla se poate obtine ecuatia spline-ului cubic:

unde C si D sunt constante de integrare care se determina prin impunerea conditiilor de capat . Prin urmare:

in care reprezinta fiecare interval.

Functii de aproximareMai avem o conditie suplimentara care impune ca primele derivate sa fie continue in fiecare din punctele off-setului:

Fig. 41 Continuitatea primelor derivate

Functii de aproximareCoeficientii zi se determina impunand conditia de continuitate a derivatelor in fiecare din punctele (ti) ale off-setului:

Din aceste ecuatii rezulta:

care reprezinta un sistem de (n-2) ecuatii liniare de forma:

Functii de aproximareunde:

Functii de aproximareChiar daca functiile spline sunt utilizate pe scara larga in aplicatiile navale, ele prezinta o serie de neajunsuri: Spline-urile cubice parametrice nu se pot reduce exact la conice;Functiile spline nu aproximeaza bine curbele asimptotice (pot prezenta oscilatii) ex.: ansamblul format dintr-un segment de dreapta si un arc de cerc; Functiile spline cubice sunt influentate de toate punctele care le definesc. O modificare cat de mica a coordonatelor unuia dintre punctele care definesc segmentele functiei determina modificarea intregii functii. In consecinta, controlul curburii functiei de aproximare se poate pierde foarte usor;Derivatele de ordinul III sunt functii continue pe portiuni. Discontinuitatile in derivatele de ordinul III pot determina puncte de inflexiune de-a lungul curbei spline. Fig.42 prezinta patru aplicatii tipice ale aproximarii cu functii spline cubice. (fig. evidentiaza problemele de aproximare la jonctiunea dintre zonele drepre si cele curbe)

Functii de aproximareFig. 42 Aproximari cu functii Spline cubice

Functii de aproximareB. Functii spline tensionate Avantajele aproximarii cu funcii spline cubice sunt uneori limitate de unele efecte nedorite care i fac apariia ndeosebi n cazul funciilor cu variaii semnificative pe intervale relativ mici. Variaiile pot conduce la oscilaiile interpolantului s-a introdus conceptul de spline tensionat Reprezentarea matematic a funciei spline tensionate are la baz o ecuaie diferenial a crei formulare implic cunoaterea valorilor derivatelor de ordinul al doilea n noduri Pe de alt parte, reprezentarea soluiei implic i cunoaterea valorilor funciei n respectivele noduri. Prin impunerea condiiei de continuitate, rezult un sistem de ecuaii tridiagonal avnd ca necunoscute valorile derivatelor de ordinul al doilea Fie un set de puncte

unde: xi sunt coordonatele distincte i dispuse n ordine cresctoare, iar yi sunt valorile funciei n punctele xi.

Functii de aproximareSe va defini funcia spline tensionat. Se ncearc definirea unei funcii reale avnd primele dou derivate continue i care ndeplinete condiia:

Presupunnd n plus existena unei constante nenule, , numit factor de tensionare, se va ncerca s se obin funcia de interpolare astfel nct funcia (necesar continu) s admit o variaie liniar pe fiecare dintre intervalele

Asta nseamn c pentru

unde

Functii de aproximareinnd cont c soluia ecuaiei difereniale este de forma:

pentru

Funcia i derivatele sale sunt continue pe intervalul

Difereniind de dou ori funcia fi i impunnd condiia de egalitate a derivatelor la stnga i la dreapta n punctele xi, pentru i=1,2...,n, se obine:

Functii de aproximare

(*)

Rezult astfel n2 ecuaii cu n necunoscutePentru a obine un sistem determinat, trebuie formulate condiii suplimentare. Pentru nceput se presupun cunoscute y1 i yn. Derivnd o singur dat pe f(x) i impunnd pe rnd condiiile

se obin urmtoarele condiii suplimentare:

Functii de aproximare

si respectiv (**)

Dac se presupune acum c funcia f este una periodic, rezult c sunt ndeplinite condiiile

care, odat impuse, conduc la:

Functii de aproximare

si respectiv (***)

Matricea sistemului definit de ecuaiile (*) i (**) sau de ecuaiile (**) i (***) este una diagonal dominant strict, ceea ce implic o soluie unic pentru oricare dintre sisteme

Functii de aproximareC. Functii B-splineFunctiile B-spline pot fi obtinute si exprimate sub diferite forme. Cea mai convenabila definitie apartine lui Cox (1971) si de Boor (1972).Formula recursiva a functiei B-spline de ordinul k, normalizate de i ori este de forma:

Din relatia recursiva Cox-de Boor se poate observa ca pentru a calcula baza de functii de ordinul k, trebuie calculate toate bazele de functii de ordin inferior, pana la 1. In acest fel, dependenta determina o forma triunghiulara asa cum se arata in Fig.43.

Functii de aproximareFig. 43 Dependenta functiilor B-spline de baza

Functii de aproximareValorile xi din functiile B-spline normalizate sunt elemente ale vectorului nodurilor care satisface relatia xixi+1, (serie monoton crescatoare de numere reale).Vectorul nodurilor notat cu X determina parameterizarea functiei de baza, lucru care ii afecteaza proprietatile. Elementele vectorului nodurilor X sunt valori ale parametrului t si acestea variaza de la tmin la tmax de-a lungul curbei. Functiile de baza B-spline normalizate sunt pozitive. Proprietatile lor pot fi exprimate matematic sub forma:

Functii de aproximareAlegerea vectorului nodurilor are o influenta semnificativa asupra bazei Ni,k de functii B-spline, si deci, asupra curbei rezultante. Prin urmare, bazele de functii B-spline sunt clasificate dupa tipul vectorului nodurilor: a) Baze de functii B-spline uniforme sau neuniforme b) Baze de functii B-spline periodice sau neperiodice.Prima clasificare descrie tipul parametrizarii, in timp ce a doua determina caracterul deschis sau inchis al curbei rezultanteIn general, vectorii nodurilor uniforme contin elemente echi-spatiate, incep cu zero si contin elemente care sunt incrementate pana la valoarea maxima sau sunt normalizate crescator intre 0 si 1, e.g., X=[0, 0.25, 0.50, 0.75, 1.0]Un vector al nodurilor deschis este caracterizat prin valorile multiple ale valorilor nodurilor la capete (valori egale cu ordinul k al functiei B-spline), e.g., X=[0, 0, 0, 1, 2 , 3, 3, 3] pentru k=3

Nodurile unui vector deschis de noduri uniforme pot fi calculate cu ajutorul expresiilor:

Functii de aproximare

Bazele de functii B-spline deschise, uniforme se calculeaza prin utilizarea relatiilor recursive de mai sus si expresia vectorului nodurilor deschis Fig.44 prezinta un exemplu pentru o functie de ordinul trei (k=3) si pentru patru noduri care definesc poligonul (n+1=4).

Vectorul nodurilor se obtine ca fiind:X=[0, 0, 0, 1, 2 , 2, 2]Fig. 44 Baza de functii B-spine deschise (nepreriodice) k=3, n+1=4

Functii de aproximareEste important sa se retina ca atunci cand numarul nodurilor poligonului de definire este egal cu ordinul bazei de functii B-spline, si cand se utilizeaza un vector al nodurilor deschis si uniform, baza de functii B-spline se reduce la baza Bernstein. Daca se considera un poligon cu patru noduri si daca ordinul functiei este patru (k =4), se obtine o curba cubica Bezier/B-spline, iar vectorul nodurilor devine: X=[0, 0, 0, 0, 1, 1, 1, 1]Vectorii nodurilor neuniforme sunt constituiti din valori ale parametrilor distribuiti neuniform. Acestia pot avea noduri interne cu valori multiple. Fig.45 prezinta un exemplu pentru o baza de functii neuniforma de ordinul trei (k=3) si pentru cinci noduri care definesc poligonul (n+1=5).

Fig. 45 Baza de functii B-spine deschise neuniforme k=3, n+1=5

Functii de aproximareVectorul nodurilor se obtine ca fiind:X=[0, 0, 0, 1, 1 , 3, 3, 3]Vectorul deschis al nodurilor neuniforme se poate calcula cu ajutorul relatiilor:

unde

in care Bi sunt punctele de control ale poligonului

Functii de aproximareAtat vectorii cu noduri uniforme cat si cei cu noduri neuniforme pot fi periodici (inchisi). In acest caz, valorile nodurilor variaza in general de la 0 la tmax=n+k, iar numarul valorilor nodurilor este n+k+1, e.g., pentru k = 3 si pentru patru noduri poligonale n+1 = 4, vectorul nodurilor pentru baza de functii periodice este X = [0 1 2 3 4 5 6]

Pentru un anume ordin k, vectorul nodurilor uniforme determina baze de functii periodice care satisfac relatia:

Aceasta proprietate a bazei de functii periodice este ilustrata in Fig. 46

Functii de aproximare

Fig. 46 Baza de functii B-spine inchise uniforme k=4, n+1=4Algoritmul De Boor Permite calculul punctelor unei curbe B-spline fr a fi necesar cunoaterea bazei de funcii descrise anterior Algoritmul reprezint o generalizare a algoritmului Casteljau care este utilizat la obinerea curbelor Bezier Baza algoritmului este aceea a definirii punctelor curbei B-spline prin definirea punctelor unui poligon de control, numite n continuare puncte de Boor Algoritmul De Boor, care conduce la obinerea punctelor curbei B-spline pentru o anumit valoare a parametrului t, este definit de urmtoarea expresie recursiv: