Sistemi Multimediali II
Lezione 8:
attributi per vertice
Università dell’Insubria
asdad
asdsad
fadf
asdf asdf asdf asd
asdfasdf asd
fasdf asdasdf asd
asdf asd asdf asd
asdf asd
Facoltà di Scienze MFN di Varese
asdad
asdsad
fadf
asdf asdf asdf asd
asdfasdf asd
fasdf asdasdf asd
asdf asd asdf asd
asdf asd
Corso di Laurea in Informatica
Anno Accademico 2004/05
asdad
asdsad
fadf
asdf asdf asdf asd
asdfasdf asd
fasdf asdasdf asd
asdf asd asdf asd
asdf asd
Marco Tarini
Preambolo:
• Le coordinate baricentriche
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 2/40
Cosa è un segmento?
V2
V1
con
v1 , v 2 R
2
o
R
3
o
4
R ...
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 3/40
Cosa è un segmento?
0.0
v+1 +
1vv2
0.1
v
0.9
1
0.66 v1 + 0.33 v2 2
0.5 v1 + 0.5 v2
0.75 v1 + 0.25 v2
≪ x è una
interpolazione
V2
V1
1 v1 + 0 v2
di v1 e v2 ≫
posso definirlo cosi':
un segmento di vertici v1 e v2
é l'insieme di tutti i punti x
esprimibili come
x = a v1 + b v2
a e b scalari positivi con a
+b=1
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 4/40
Parentesi notazione
interpolazione:
V1
x
x = a v1 + b v2
V2
a e b scalari positivi
con a + b = 1
(quindi 0 ≤ a ≤ 1 e 0 ≤ b ≤ 1 )
estrapolazione:
V1
V2
x
x = a v1 + b v2
a e b scalari positivi
con a + b = 1
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 5/40
Cosa è un triangolo?
V3
V2
V1
con
v1 , v 2 , v 3  R
2
o
R
3
o
4
R ...
≪ é l'insieme di tutti i punti x tali che... ≫
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 6/40
Cosa è un triangolo?
V3
p
V1
q
V2
q = k1 v1 + k2 v2
k1 + k2 = 1
k1,k2 > 0
p = h1 v3 + h2 q
h1 + h2 = 1
h1,h2 > 0
esercizio: sostituiamo e...
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 7/40
Cosa è un triangolo?
V3
V2
V1
un triangolo di vertici v1 v2 v3
é l'insieme di tutti i punti x
esprimibili come
x = a1 v1 + a2 v2 + a3 v3
a1 a2 a3 scalari positivi
a1 + a2 + a3 = 1
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 8/40
Per esempio...
0 v1 + 0 v2 + 1 v3
0.33 v1 + 0.33 v2 +0 0.33
v3v2 + 0 v3
v1 + 1
(il baricentro del triangolo)
V
0.5v v+1 +
0.5vv2 + 0 v3
0.65 v +30.2
0.15
1
2
3
(punto in mezzo al lato v1 v2)
V2
V1
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 9/40
Ebbene...
V3
V2
V1
dati a1 a2 a3 scalari tali positivi
con
a1 + a2 + a3 = 1
→
x = a1 v1 + a2 v2 + a3 v3
é un punto del triangolo
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 10/40
Ma anche...
V3
V2
V1
dato un punto p nel triangolo
→
a1 a2 a3 tali che
p = a1 v1 + a2 v2 + a3 v 3
e a1 a2 a3 sono positivi e a somma 1
esistono unici
diciamo che a1
a2 a3 sono le coordinate baricentriche di p
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 11/40
Le coordinate baricentriche
• Concetto
FONDAMENTALE
V3
p
V2
V1
p ha coordinate baricentriche
(a1 a2 a3) sse
p = a1 v1 + a2 v2 + a3 v3
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 12/40
Le coordinate baricentriche
Interpretazione fisica (storica) (buffa)
p ha coordinate baricentriche
(a1 a2 a3) sse
é il baricentro di:
V3
V1
a3 Kg
a1 Kg
p
V2
a2 Kg
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 13/40
Le coordinate baricentriche
Interpretazione geometrica
1
V3
p
k
1
V1
V2
h
p = v1 + h ( v2-v1 ) + k ( v3-v1 )
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 14/40
Coordinate baricentriche:
improtante proprietà
R3
R2
f( v3 )
V3
p
V2
V1
p ha coord.
baricentriche a,b,c
nel triangolo v1 v2 v3
trasformazione affine f
(proiezione compresa)
f(p)
f( v2 )
f( v1 )
f(p) ha coord.
baricentriche a,b,c
nel triangolo f(v1) f(v2) f(v3)
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 15/40
Le coordinate baricentriche
come rapporti fra aree
• Quali sono le coord baricentriche di un punto p?
V3
A1
A2
p
V2
A3
V1
A1
a1 
Atot
p = a1 v1 + a2 v2 + a3 v3
A2
a2 
Atot
A3
a3 
Atot
Atot  A1  A2  A3
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 16/40
Preambolo:
• Le coordinate baricentriche
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 17/40
associamo
degli attributi
ai vertici
che
mandiamo
es: colore RGB
rasterizer
punti
setup
rasterizer
triangoli
setup
rasterizer
segmenti
qui
gli attributi
possono subire
varie
compuatzioni
computazioni
per frammento
setup
Frammenti
& attributi
interpolati
Vertici proiett
& attributi
computati
computazioni
per vertice
Vertici
& loro attributi
Attributi nel pipeline
qui gli attributi
vengono
interpolati
pixel
finali
(nello
screen-buffer)
ogni frammento
avrà
una valore
interpolato
degli attributi
per vertice
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 18/40
Attributi nella rasterizzazione
• Quindi il rasterizer deve fare DUE cose:
1 trovare i frammenti che compongono la primitiva
• e.g. i frammenti interni al triangolo
2 interpolare gli attributi per questi frammenti
• tramite le coordinate baricentriche
• Il rasterizer produce frammenti
CON attributi associati
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 19/40
Attributi nella rasterizzazione
• Idea:
– lavoriamo su R2
R
NOTA: vero solo per le
trasformazioni affini.
E' solo una
approssimazione per la
distorsione prospettica
3
R
2
f( v3 )
V3
p
V2
V1
p ha coord.
baricentriche a,b,c
nel triangolo v1 v2 v3
trasformazione affine f
(proiezione compresa)
f(p)
f( v2 )
f( v1 )
f(p) ha coord.
baricentriche a,b,c
nel triangolo f(v1) f(v2) f(v3)
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 20/40
Scan-line rasterizer & attributi
• Otteniamo gli attributi per frammento
interpolando gli attributi per vertice
lungo segmenti (linearmente)
• Equivalente ad usare
le coordinate baricentriche del frammento
come pesi
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 21/40
Scan-line rasterizer & attributi
• Interpoliamo gli attributi:
– linearmente sui bordi
– e in ogni scanline, tra gli estremi dello span
v1
a1
p
v2
a2
p interpolato
fra a2 e a1
q
q interpolato
fra a0 e a1
f
f interpolato
fra p e q
v0
a0
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 22/40
Scan-line rasterizer & attributi
• Lo stesso per tutti gli attributi
v1
a1, b1, c1...
p
v2
a2, b2, c2...
Ottimaizzatione:
si puo'
calcolare
incrementalme.
vediamo come →
q
f
v0
a0, b0, c0...
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 23/40
Scan-line rasterizer & attributi
Primo frammento prodotto:
ha come attributo a0
ogni volta che mi sposto
1 pixel a dx:
aumento di una costante dx
a2
a1
ogni volta che mi sposto
1 pixel in alto:
aumento di una costante dy
a0
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 24/40
Scan-line rasterizer & attributi
Primo frammento prodotto:
ha come attributo a0
ogni volta che mi sposto
1 pixel a dx:
aumento di una costante dx
a2
8 passi
a1
ogni volta che mi sposto
1 pixel in alto:
aumento di una costante dy
9 dx + 8 dy = a1 - a0
a0
9 passi
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 25/40
Scan-line rasterizer & attributi
Primo frammento prodotto:
ha come attributo a0
ogni volta che mi sposto
1 pixel a dx:
aumento di una costante dx
a2
11 passi
a1
a0
1 passo
ogni volta che mi sposto
1 pixel in alto:
aumento di una costante dy
9 dx + 8 dy = a1 - a0
dx + 11 dy = a2 - a0
risolvo nella fase di
SET-UP di quel triangolo
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 26/40
Edge functions e attributi
• Per i rastertizzatori basati su edge-functions:
– useremo la regola delle aree:
V3
A1
A2
p
V2
A3
V1
A1
a1 
Atot
p = a1 v1 + a2 v2 + a3 v3
A2
a2 
Atot
A3
a3 
Atot
Atot  A1  A2  A3
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 27/40
Parentesi: area di un triangolo
• In R3 posso calcolarla con il prodotto esterno
V3
e nel caso particolare di R2 ?
proviamo...
d1
A
V1
d2
V2
il "diviso due"
lo possimo ignorare.
Tanto ci interessano
solo i rapporti
fra le aree
A = | d1 x d2 | /2
= | (v3 – v1) x (v2 – v1 ) | /2
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 28/40
FlashBack: Edge functions
• La funzione il cui segno ci dice in quale semipiano siamo
n
v0=(x0, y0 )
SI
v2
q
NO
v1=(x1, y1 )
p = (x0 , y0)
n = ( - ( y1 -y0 ) , x1 -x0)
f(q) = n‧q - n‧p
totale: l'edge function
per un lato è
la coord baricentrica
ralativa al vertice opposto
(dopo aver diviso per
la somma delle 3 edge functions)
M a r c o T a r i n i ‧ S i s t e m i M u l t i m e d i a l i I I ‧ 2 0 0 4 / 0 5 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a - 29/40