Sviluppo di una libreria orientata agli oggetti per il calcolo di NURBS - Presentazione

18
Sviluppo di una libreria orientata agli oggetti per il calcolo di NURBS con applicazioni alla grafica 2D e 3D Antonio Sanfelice Universit` a degli Studi di Salerno Corso di laurea in Informatica Relatore: Dott. Mario Annunziato A.A. 2009 - 2010

description

Presentazione che ho utilizzato per discutere la mia tesi di laurea nei 5 minuti che mi sono stati concessi.

Transcript of Sviluppo di una libreria orientata agli oggetti per il calcolo di NURBS - Presentazione

Sviluppo di una libreria orientata aglioggetti per il calcolo di NURBS con

applicazioni alla grafica 2D e 3D

Antonio Sanfelice

Universita degli Studi di SalernoCorso di laurea in Informatica

Relatore: Dott. Mario Annunziato

A.A. 2009 - 2010

NURBSCosa sono?

Modello matematico per la rappresentazione dicurve e superfici

Sviluppo iniziato negli anni ’50 per esigenzeindustriali

Comunemente usate nei software di computergrafica

28/10/2010 Made with LATEX 2/18

NURBSDefinizione

Equazioni in forma parametricaOgni coordinata e definita come funzione di unparametro esterno

Generalizzazione di B-Spline e Bezier splineTutte sono combinazioni lineari di un insieme di puntidetti punti di controlloI pesi utilizzati per le combinazioni sono le funzioni dibase (o blending functions) che sono caratteristichedel tipo di spline.

28/10/2010 Made with LATEX 3/18

NURBSFunzioni di Base

Bezier

Jn,i =

(n

i

)ui(1− u)n−i

B-Spline Ni,1(u) =

{1 se xi ≤ u < xi+1

0 altrimenti

Ni,k(u) =(u− xi)Ni,k−1(u)

xi+k−1 − xi+

(xi+k − u)Ni+1,k−1(u)

xi+k − xi+1

B-Spline Razionali

Ri,k(u) =hiNi,k(u)n∑

i=0

hiNi,k(u)

28/10/2010 Made with LATEX 4/18

NURBSVettore dei nodi

x ∈ Rn+k+1 : xi ≤ xi+1 ∀i ∈ [1, n+ k]

Periodico o Uniforme: Gli elementi del vettore sonoequispaziati;

Aperto: Valori ripetuti all’inizio e alla fine del vettore;

Non uniforme: Nessuna condizione a parte l’ordine nondecrescente.

NURBS ⇒ Non Uniform Rational B-SplineB-Spline razionale che utilizza un vettore dei nodi non

uniforme

28/10/2010 Made with LATEX 5/18

Libreria

Poche librerie disponibili on-linenurbs++openNURBS

Sviluppata in Pythonportabilesemplice e veloceSe ci credono Google e la NASA un pensiero ce lo faccioanche io

Orientata agli oggettiRiutilizzo di codiceFacile da estendere e personalizzare

28/10/2010 Made with LATEX 6/18

SviluppoFunzionalita

Calcolo di curve e superficiBezierB-SplineNURBS

Concatenazione di curve

Approssimazione e interpolazione di curve e superficitramite B-Spline

28/10/2010 Made with LATEX 7/18

SviluppoAlgoritmo naive per il calcolo di curve

C(u) =n∑

i=0

pi bi(u)

1: for all u do2: C(u)← (0, 0)3: for i = 0→ n do4: Determina bi(u)5: C(u)← C(u) + pibi(u)6: end for7: end for

Veloce

Facile daimplementare

Numericamenteinstabile

28/10/2010 Made with LATEX 8/18

SviluppoAlgoritmo di de Casteljau

Calcolo ricorsivo di combinazioni convesse

Facile da implementare

Piu stabile

Complessita computazionale piu alta ∼ O(n2)

P ← pfor i = 0→ n do

for j = 0→ n− i doPj = (1− u)Pj + uPj+1

end forend forreturn P0

28/10/2010 Made with LATEX 9/18

SviluppoClass Diagram: Curve

28/10/2010 Made with LATEX 10/18

SviluppoClass Diagram: Superfici

28/10/2010 Made with LATEX 11/18

Grafica 2DEsempi B-Spline

28/10/2010 Made with LATEX 12/18

Grafica 2DApprossimazione di curva

Originale su cartaOutput della libreria

28/10/2010 Made with LATEX 13/18

Grafica 3DApprossimazione di superficie

Punti da approssimare Output della libreria

28/10/2010 Made with LATEX 14/18

Grafica 3DApprossimazione di superficie

Punti da approssimare Output della libreria

28/10/2010 Made with LATEX 15/18

Possibili Applicazioni

Scanner 3D

Simulazione meccanica dei muscoli

Ricostruzione paesaggiApplicazioni anche al di fuori della grafica

Path planning robot mobili ed industrialiSignal ProcessingReti Neurali

28/10/2010 Made with LATEX 16/18

Test sui Tempi di esecuzioneBreve confronto con il modulo NURBS di Octave

Misurazioni dei tempi di esecuzione eseguite tramitela funzione time della bash;

Test: Calcolo di 200 punti di una curva B-Splineperiodica di ordine 4 ottenuta da 19 punti dicontrollo.

Strumento real user sys user + sysLa mia libreria 1.484s 0.352s 0.116s 0.468s

Octave 0.758s 0.664s 0.092s 0.756s

28/10/2010 Made with LATEX 17/18

Grazie

28/10/2010 Made with LATEX 18/18