Curve e Superfici




Il mondo non è fatto di rette e poligoni.
Non é sempre ragionevole approssimare curve con
spezzate.
Moltissime le rappresentazioni proposte:
polygon mesh
superfici parametriche (curve)
superfici quadriche
Cominciamo con modellazione di curve e superfici,
poi vedremo modellazione solida.
Curve e Superfici
Informatica Grafica
1
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).
Curve e Superfici
Informatica Grafica
2
Rappresentazione di Polygon Mesh
Aspetto fondamentale: efficienza spazio / tempo.
Per ottimizzare bisogna individuare quali sono le
operazioni più frequenti.
Noi vedremo 3 rappresentazioni:
Esplicita
Con puntatori ai vertici
Con puntatori ai lati
Ognuna ha vantaggi e svantaggi. La scelta dipende
dalle operazioni richieste.
Curve e Superfici
Informatica Grafica
3
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.
Curve e Superfici
Informatica Grafica
4
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.
Curve e Superfici
Informatica Grafica
5
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 = 0
si possono trovare calcolando l’area delle proiezioni
sui piani coordinati. Per esempio, il valore di C per un
triangolo è dato da:
Curve e Superfici
Informatica Grafica
6
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 ruotiamo
non adatto a curve con tangente verticale
Curve e Superfici
Informatica Grafica
7
Equazioni Implicite
Curva definita implicitamente f(X,Y,Z) = 0.
Problemi:

difficile rappresentare mezza circonferenza.

difficile calcolare la tangente.

difficile congiungere più segmenti.
Curve e Superfici
Informatica Grafica
8
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 e Superfici
Informatica Grafica
9
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
Curve e Superfici
Informatica Grafica
10
Esempio in 2D
2 segmenti 2D congiunti.
Notate che la curva nel
piano xy non è una funzione
nè di x nè di y.
Curve e Superfici
Informatica Grafica
11
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 continuity
Se dnQ(t)/dt n uguali
C n continuity
(d Q / dt é la velocità d2 Q /dt2 é l’ accelerazione)
Curve e Superfici
Informatica Grafica
12
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 solo
se la derivata in t è significativa.
Le derivate rispetto a t sono invisibili
Y1(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
Curve e Superfici
Informatica Grafica
13
Tipi Curve Parametriche
Tipi curve: Hermite
Bezier
Splines
2 (estremi + vettori tangenti).
2 estremi + 2 punti di controllo.
4 punti di controllo
Riscriviamo l’ equazione di Q(t) = G * M * T
M è 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 e Superfici
Informatica Grafica
14
Curve di Hermite
Geometry vector : G = [P1 P4 R1 R4]
2 estremi
2 vettori tangenti
La base matrix viene :
2 -3 0 1
MH = -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.
Curve e Superfici
Informatica Grafica
15
Hermite Blending Functions
Riscrivendo Q ottengo
4 blending functions
Curve e Superfici
Informatica Grafica
16
Esempi Hermite
P1,P4,R4 fissi.
R1 stessa direzione
ma ampiezze
diverse.
P1,P4,R4 fissi.
R1 ampiezza fissa
cambia direzione.
Curve e Superfici
Informatica Grafica
17
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 e Superfici
Informatica Grafica
18
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)
Curve e Superfici
Informatica Grafica
19
Polinomi di Bernstein
Blending functions per Bezier:
sempre positive 0 <= t <= 1
BB1+BB2+BB3+BB4 = 1
Quindi hanno la proprietà del
convex hull
Continuità:
se
P3-P4-P5 allineati
se
P4-P3=P5-P4
Curve e Superfici
G1
C1
Informatica Grafica
20
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.
Curve e Superfici
Informatica Grafica
21
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)
Curve e Superfici
Informatica Grafica
22
B-Splines Uniformi
Uniforme 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.
Curve e Superfici
Informatica Grafica
23
Base Matrix

La matrice di base vale:
-1
MBS = 1/6 * 3
-3
1
Curve e Superfici
3
-6
3
0
-3
0
3
0
1
4
1
0
Informatica Grafica
24
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.
Curve e Superfici
Informatica Grafica
25
(S)Vantaggi
Vantaggi: alta continuità C0, C1, C2.
Svantaggi: difficili da controllare poiché non
interpolano alcun punto.
Per migliorare il controllo: duplico punti di controllo
attenzione: posso perdere in continuità G1.
Curve e Superfici
Informatica Grafica
26
Non Uniform B-Splines
Differenze: 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.
Curve e Superfici
Informatica Grafica
27
Nonuniform B-Splines (2)
Ogni segmento è definito da
Q 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.
Curve e Superfici
Informatica Grafica
28
Multiple Knots
Aumentare la molteplicità dei knots ha due effetti:
1) Si aumenta il controllo sul knot
2) 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à.
Curve e Superfici
Informatica Grafica
29
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.).
Curve e Superfici
Informatica Grafica
30
Riconoscimento Curve
Le curve viste sono
facilmente utilizzabili
per descrivere profili
risultanti dalla
digitalizzazione di
disegni e figure.
Per esempio, usando
Bezier otteniamo:
Curve e Superfici
Informatica Grafica
31
Superfici Parametriche Bicubiche
Superfici definite da equazioni con 2 parametri: s, t
Se 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 * GiT
L’equazione complessiva è:
Q(s,t) = TT * MT * G * M * S
dove G è una matrice 4*4.
Curve e Superfici
Informatica Grafica
32
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.
Curve e Superfici
Informatica Grafica
33
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.
Curve e Superfici
Informatica Grafica
34
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
Curve e Superfici
Informatica Grafica
35
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.
Curve e Superfici
Informatica Grafica
36
Disegno di Superfici
Metodo di valutazione
iterativa:
per tutti i valori di s
per tutti i valori di t
calcola il punto Q(s,t)
Il costo computazionale è
elevato.
Spesso si usano tecniche di
forward-difference.
Curve e Superfici
Informatica Grafica
37
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 normale
2) Verifca di appartenenza di un punto alla superficie
3) Calcolo di z dati x ed y
4) Calcolo intersezioni con altra superfice
Gli svantaggi sono quelli legati alle equazioni implicite.
Curve e Superfici
Informatica Grafica
38
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
Curve e Superfici
Informatica Grafica
39
Modelli Frattali
Basati sull’idea di self-similarity. Partendo da una
semplice figura iniziale, ogni segmento viene
rimpiazzato da una copia ridotta dell’originale.
Curve e Superfici
Informatica Grafica
40
Julia-Fatou set
Curve e Superfici
Informatica Grafica
41
Mandelbrot Set
Curve e Superfici
Informatica Grafica
42
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.
Curve e Superfici
Informatica Grafica
43
Grammatiche Estese

Usando grammatiche più estese si possono
ottenere modelli per oggetti come:
Curve e Superfici
Informatica Grafica
44