Informatica Grafica Curve e Superfici1 l Il mondo non è fatto di rette e poligoni. l Non é sempre...

Curve e Superfici 1Informatica Grafica

Curve e Superfici

Il mondo non è fatto di rette e poligoni. Non é sempre ragionevole approssimare curve

con spezzate. Moltissime le rappresentazioni proposte:

polygon meshsuperfici parametriche (curve)superfici quadriche

Cominciamo con modellazione di curve e superfici, poi vedremo modellazione solida.


Polygon Mesh

Insieme di superfici poligonali planari limitate: rappresentano esattamente alcune figure,

approssimano bene altre (fig. sinistra).Buone approssimazioni sono sempre possibili ma

spesso sono costose (fig. destra per una sezione).


Rappresentazione di Polygon Mesh

Aspetto fondamentale: efficienza spazio / tempo.Per ottimizzare bisogna individuare quali sono le

operazioni più frequenti.Noi vedremo 3 rappresentazioni:

EsplicitaCon puntatori ai verticiCon puntatori ai lati

Ognuna ha vantaggi e svantaggi. La scelta dipende dalle operazioni richieste.


Rappresentazione Esplicita

Polygon Mesh: lista di poligoni. Poligono: lista di vertici.

Problemi:- Spreco spazio per duplicazione vertici.- Dispendioso trovare tutti i poligoni che hanno un determinato vertice. Questo richiede di ordinare tutte le liste e cercare un elemento in tutte le liste.


Rappresentazioni con Puntatori

Puntatori a lista di vertici: rappresentazione piu usata

Problemi: inefficiente trovare i poligoni con un lato in comune. Lati in comune sono disegnati 2 volte.

Puntatori a lista di lati:Problemi: 2 poligoni per lato

va bene per molte figure, ma può essere maggiore.


Equazioni del Piano

Usando polygon meshes un’operazione fondamentale e’ di calcolare il piano di un poligono. I coefficienti dell’EQ:

Ax + By + Cz + D = 0si possono trovare calcolando l’area delle proiezioni sui piani coordinati. Per esempio, il valore di C per un triangolo è dato da:


Curve di Grado Superiore

Buone approssimazioni con polylines richiedono molti punti.

Alternativa : approssimare con funzioni di grado superiore.

Molti metodi possibili. Il più semplice consiste nell’avere Y e Z come funzioni esplicite di x :

Y=f(x) Z=f(x)Problemi : non adatto a cerchi, ellissi, ..…

non si preserva se ruotiamonon adatto a curve con tangente

verticale


Equazioni Implicite

Curva definita implicitamente f(X,Y,Z) = 0.Problemi:

difficile rappresentare mezza circonferenza.

difficile calcolare la tangente.

difficile congiungere più segmenti.


Rappresentazioni Parametriche

Rappresentazioni implicite, con X, Y e Z funzioni di un parametro t. Normalmente t va da 0 a 1.

X=X(t) Y=Y(t) Z=Z(t)

Una curva è una lista di segmenti dove ogni segmento è definito da 3 funzioni parametriche (cubiche in t).

Cubiche perchè si possono fissare 2 endpoints con relative derivate e le curve non sono necessariamente planari.


Curve Cubiche Parametriche

Curve di grado più alto (>4) sono difficili da controllare, e usate solo in poche applicazioni.

Forma generale (cubica) Q(t) = [x(t) y(t) z(t)]T =x(t) = ax t3 + bx t2 + cx t + dx

y(t) = ay t3 + by t2 + cy t + dy

z(t) = az t3 + bz t2 + cz t + dz

In forma matriciale: Q(t) = C*T dove T=[t3 t2 t 1]T

e ax bx cx dx

C = ay by cy dy

az bz cz dz


Esempio in 2D

2 segmenti 2D congiunti.Notate che la curva nelpiano xy non è una funzionenè di x nè di y.


Continuità tra Segmenti

Se 2 segmenti si incontrano: G0 geometric continuity.Se hanno anche la stessa tangente nel punto di

contatto: G1 geometric continuity.Se vettori tangenti uguali C1 continuitySe dnQ(t)/dt n uguali C n continuity(d Q / dt é la velocità d2 Q /dt2 é l’ accelerazione)


Differenze C-G

In generale C1 implica G1 poichè impone stessa direzione e grandezza dei vettori tangenti

La differenza tra continuità C1

e continuità G1 è importante solose la derivata in t è significativa.Le derivate rispetto a t sono invisibiliY1(t) =4t2+2t+1 0<t<1

Y2 (t) =16t2+4t+1 0<t<1/2

[dY1 / dt ] t=0 = 2 [dY2/ dt ] t=0 = 4


Tipi Curve Parametriche

Tipi curve:Hermite 2 (estremi + vettori tangenti).Bezier 2 estremi + 2 punti di controllo.Splines 4 punti di controllo

Riscriviamo l’ equazione di Q(t) = G * M * TM è la basis matrix e G è il geometry vector. G contiene le specifiche dei vincoli geometrici, mentre M è costante per ogni tipo. Le 3 funzioni risultanti dal prodotto M * T vengono chiamate blending functions


Curve di Hermite

Geometry vector : G = [P1 P4 R1 R4]

2 estremi2 vettori tangenti

La base matrix viene : 2 -3 0 1MH = -2 3 0 0

1 -2 1 0 1 -1 0 0

Si ottiene imponendo che ogni componente (x, y o z) soddisfi i vincoli geometrici.


Hermite Blending Functions

Riscrivendo Q ottengo4 blending functions


Esempi Hermite

P1,P4,R4 fissi.

R1 stessa direzione ma ampiezze diverse.

P1,P4,R4 fissi.

R1 ampiezza fissa

cambia direzione.


Disegno Curve Parametriche

typedef float CoefficientArray[4];void DrawCurve(CoefficientArray cx, CoefficientArray cy,

CoefficientArray cz, int n){ float x, y, z, delta, t, t2, t3; int i;

MoveAbs3(cx[3], cy[3], cz[3]); delta = 1.0/n;for( i = 1; i <= n; i++ ){ t = i*delta; t2 = t*t; t3 = t2*t;

x = cx[0]*t3 + cx[1]*t2 + cx[2]*t + cx[3];y = cy[0]*t3 + cy[1]*t2 + cy[2]*t + cy[3];z = cz[0]*t3 + cz[1]*t2 + cz[2]*t + cz[3];DrawAbs3(x, y ,z);}

}


Curve di Bezier

Fisso i 2 estremi + 2 punti di controllo.

Estremi: P1 P4

Punti di controllo: P2 P3

Relazione con Hermite:R1 = 3(P2 - P1)

R2 = 3(P4 - P3)


Polinomi di Bernstein

Blending functions per Bezier:sempre positive 0 <= t <= 1BB1

+BB2+BB3

+BB4 = 1

Quindi hanno la proprietà delconvex hull

Continuità:se P3-P4-P5 allineati G1

se P4-P3=P5-P4 C1


Uniform Nonrational B-Splines

Natural cubic splines: curva che interpola i control points con continuità C0, C1, C 2. Ottima continuità, ma non hanno la proprietà di località. Ogni tratto della curva dipende da tutti i punti di controllo.

B-splines: splines con controllo locale e stessa continuità (C2). Però non interpolano nessuno dei punti di controllo.


Uniform Nonrational B-Splines

Punti di controllo condivisi tra segmenti adiacenti:m +1 control points P0 P1 ....Pm

m-2 segmenti Q3 Q4 ...Qm

un solo t t i <= t < t i + 1 per Q i

punti di contatto knot per t = t3 , t 4, t 5... t m-1 , t m

(o estremi)


B-Splines UniformiUniforme vuol dire che ti+1-ti è costante. Possiamo

assumere t 3= 0 e t i+1 - ti =1.

Il segmento Qi é definito dai punti P i-3 , P i-2, P i-1 , Pi che sono il suo geometry vector.

Definendo Ti=[(t-ti)3 (t-ti) 2 (t-ti) 1]T

abbiamo per ogni segmento:Qi(t) = GBSi

* MBS * Ti

Spostando un control point modifico al più 4 segmenti.


Base Matrix

La matrice di base vale:

-1 3 -3 1MBS = 1/6 * 3 -6 0 4

-3 3 3 1 1 0 0 0


B-Spline Blending Functions

Moltiplicando M * T ottengo le blending functions [(1-t)3]/6 [3t3-6t2+4]/6 [-3t3+3t2+3t+1]/6 t3/6

Nota : La somma è pari a 1 e sono tutte non negative quindi vale la proprietà del convex hull.


(S)Vantaggi

Vantaggi: alta continuità C0, C1, C2.Svantaggi: difficili da controllare

poiché non interpolano alcun punto.Per migliorare il controllo: duplico punti di controlloattenzione: posso perdere in continuità G1.


Non Uniform B-SplinesDifferenze: ti+1-ti non è costante.

Vantaggi: si può controllare la continuità (da C2 a nessuna continuità)si possono interpolare punti (solo se C0)si possono interpolare estremi

Control points P0.........Pm Knots t0.......tm+4

I knots possono ripetersi. Unico vincolo è che i valori di t siano non decrescenti.


Nonuniform B-Splines (2)

Ogni segmento è definito daQ i(t) = P i-3 *B i-3,4(t)+P i-2*B i-2,4(t)+P i-1*B i-1,4(t)+P i*B i,4(t)

ti <= t < ti+1 3 <= i <= m

Bi,J= funzione di blending di ordine j per il punto Pi definita con delle equazioni di ricorrenza (vedi libro pg 347).

Le B-Splines non uniformi hanno ancora la proprietà del convex hull.


Multiple Knots

Aumentare la molteplicità dei knots ha due effetti:1)Si aumenta il controllo sul knot2) Si riduce la continuità

Se ti = ti+1 allora il knot sta sul segmento congiungente Pi-2 e Pi-1 e la continuità scende a C1.

Se ti = ti+1 = ti+2 allora il knot coincide con Pi-1 e la continuità scende a C0.

Se ti = ti+1 = ti+2 = ti+3 allora la curva si interrompe e si perde la continuità.


Nonuniform Rational B-Splines NURBS

Rational significa che le equazioni sono rapporti di 2 polinomi:x(t) = X(t)/W(t); y(t) = Y(t)/W(t); z(t) = Z(t)/W(t)

In coordinate omogenee: Q(t) = [X(t) Y(t) Z(t) W(t)]T

Vantaggi:1) Le NURBS sono invarianti rispetto a: rotazioni,

scalamenti, traslazioni e trasformazioni prospettiche

2) Con le NURBS possiamo definire precisamente le coniche (ellissi, cerchi etc.).


Riconoscimento Curve

Le curve viste sonofacilmente utilizzabiliper descrivere profilirisultanti dalladigitalizzazione didisegni e figure.Per esempio, usandoBezier otteniamo:


Superfici Parametriche Bicubiche

Superfici definite da equazioni con 2 parametri: s, tSe si ha dipendenza cubica da s e t allora sono

dette bicubiche.Forma generale: Q(s,t)=[G1(t) G2(t) G3(t) G4(t)]*M*S

dove Gi(t) è a sua volta una curva parametrica cubica. Quindi Gi (t) = Gi * M * T

Trasponendo otteniamo GiT (t) = TT * MT * Gi

T

L’equazione complessiva è:Q(s,t) = TT * MT * G * M * S

dove G è una matrice 4*4.


Superfici di Hermite

Caratterizzate da:P1(t) P4(t) 2 curve estreme

R1 (t) R4(t) 2 curve tangenti

Ogni coordinata può essere scritta:

x(t) = TT * MHT * GHx * MH * S

y(t) = TT * MHT * GHy * MH * S

z(t) = TT * MHT * GHz * MH * S

GHx GHy GHz sono costanti ed

hanno il ruolo di GH per le curve.


Congiungere Patches

Ogni superfici così definita si chiama patch.

Congiungere patches è come congiungere due segmenti di curva. Proprietà fondamentale è la continuità alla giunzione.

Possiamo ottenere continuità C1 e G1 imponendo restrizioni alle matrici G.


Superfici di Bezier

Le informazioni sono ora 16 control points. Alla congiunzione ho continuità G1 se:

P13-P14-P15 P23-P24-P25 P33-P34-P35 P43-P44-P45

sono collineari


Normali

Trovare le normali ad una superfice non è matematicamente difficile:

Per trovare la nomale basta calcolare dQ(s,t)/ds e dQ(s,t)/dt.

Dal loro prodotto vettoriale otteniamo la tangente.

Purtroppo l’equazione della normale è un polinomio di quinto grado nelle due variabili s e t.

Questo rende il suo calcolo abbastanza costoso.


Disegno di Superfici

Metodo di valutazione iterativa:

per tutti i valori di sper tutti i valori di t

calcola il punto Q(s,t)

Il costo computazionale è elevato.Spesso si usano tecniche di forward-difference.


Superfici Quadriche

Definite da equazioni implicite:f(x,y) = ax2 + by2 + cz2 + 2dxy + 2eyz + 2f xz + 2gx + 2hy + 2jz +k = 0

o in alternativa: PT * Q * P = 0.Vantaggi: Sono semplificate le operazioni di:1) Calcolo della normale2) Verifca di appartenenza di un punto alla superficie3) Calcolo di z dati x ed y4) Calcolo intersezioni con altra superficeGli svantaggi sono quelli legati alle equazioni

implicite.


Modelli Specializzati

I modelli visti sinora sono generali, ma non permettono rappresentazioni molto accurate di oggetti complessi del mondo reale. Vediamo brevemente 2 metodi specializzati adatti ad alcune situazioni particolari:

Modelli frattali

Modelli basati su una grammatica


Modelli Frattali

Basati sull’idea di self-similarity. Partendo da una semplice figura iniziale, ogni segmento viene rimpiazzato da una copia ridotta dell’originale.


Julia-Fatou set


Mandelbrot Set


Modelli Frattali (2)

Modelli frattali sono stati spesso utilizzati per modellare il profilo delle montagne. In modelli 2D ad ogni passo il segmento viene diviso in 2 ed il punto centrale viene alzato di una quantità random.


Grammatiche Estese

Usando grammatiche più estese si possono ottenere modelli per oggetti come:

Informatica Grafica Curve e Superfici1 l Il mondo non è fatto di rette e poligoni. l Non é sempre...

Documents

Transcript of Informatica Grafica Curve e Superfici1 l Il mondo non è fatto di rette e poligoni. l Non é sempre...