Post on 01-May-2015
Computer Graphics
Marco Tarini
Lezione 7: rasterizzazione la fabbrica dei frammenti
Università dell’Insubria
Facoltà di Scienze MFN - Varese
Corso di Laurea in Informatica
Anno Accademico 2006/07
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizziamo!
fram
men
ti(c
andid
ati
pix
els
)
Vert
ici
(punti
in R
3)
pixelfinali
(nello screen-buffer)
Vert
ici
pro
iett
ati
(punti
in R
2)
Z
rasterizer
triangoli
com
puta
zioni
per
fram
mento
set-up
rasterizer
segmenti
set-up
rasterizer
punti
set-up
com
puta
zioni
per
vert
ice
rasterizer
triangolirasterizer
segmenti
rasterizer
puntirasterize
r triangoli
rasterizer
punti
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizzazione Segmenti
• Produrre i frammenti il più vicino possibile alla linea ideale
v0
v1
lavoriamo con coord intere.Arrotondarle prima.
Attenzione agli estremi!Pensare al Line LOOP
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizzazione di segmenti
• Vogliamo avere la sequenza di frammenti che– approssimi al meglio il
segmento
• e quindi– sia il più in linea retta
possibile
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizzazione di segmenti
coefficienti angolari m1
→1 frammento per
colonna
dx=9
dy=
7
Considerando approx di segmentidi circa un pixel di spessore
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizzazione di segmenti
dx=3
dy=
10
coefficienti angolari m>1
→1 frammento per riga
Consideriamo i due casiseparatemente.Ne vediamo uno.(l'altro è simile)
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Scrivo la retta come:
) 1 m (
Bm
xy
Rasterizzazione di segmenti: algoritmo analitico
dx=9
dy=
7
m=dy/dx=7/9
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizziamo da (x0,y0) a (x1,y1)
Rasterizzazione di segmenti: algoritmo analitico
P0
P1
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Algoritmo analitico
Per x che va da x0 a x1
• x ++ • y ← mx + B
• arrotondare y• produrre frammento ( x ,
y )
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Algoritmo analitico
• seleziona sempre il frammento più vicino alla linea ideale
• per trovarlo si devono fare:– un’addizione (un +1 intero)
– una moltiplicazione (float)
– un arrotondamento (da float a int)
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Segmenti di Spessore diverso da uno
es: spessore 3
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Segmenti di Spessore diverso da uno
Chiaramente è solo una approssimazione
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Segmenti di Spessore diverso da uno
void glLineWidth( width );
Non necessariamenteun intero
(se si usa anti-aliasing,vedi poi)
• In OpenGL
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizziamo!
fram
men
ti(c
andid
ati
pix
els
)
Vert
ici
(punti
in R
3)
pixelfinali
(nello screen-buffer)
Vert
ici
pro
iett
ati
(punti
in R
2)
Z
rasterizer
triangoli
com
puta
zioni
per
fram
mento
set-up
rasterizer
segmenti
set-up
rasterizer
punti
set-up
com
puta
zioni
per
vert
ice
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizziamo triangoli
Algoritmo scan-line
Idea Base:1. ordiniamo per y2. per ogni righa da ymin a
ymax
1. trova primo framm dentro
2. trova primo framm fuori
3. produci frammenti da da A incluso a B escluso
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizziamo triangoli
Algoritmo scan-line
Idea Base:1. ordiniamo per y2. per ogni righa da ymin a
ymax
1. trova primo framm dentro
2. trova primo framm fuori
3. produci frammenti da primo dentro a primo fuori (escluso)
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Bresenham
• In ogni riga:– trovare il primo-dentro e primo-fuori è simile
a Bresenham, ma:• un caso solo (sempre per riga, sempre verso l'alto)• arrotondiamo sempre per eccesso• passiamo all'altro segmento quando siamo arrivati
alla riga del punto in termedio sulle y
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
• "Scan-Conversion" = Rasterization (Rasterizzazione)
• "to scan-conver" = to Rasterize• "Span" = intervallo da primo-dentro a primo-
fuori
• "Line-scan" = una riga processata• "Active edges" = i 2 lati attuali• "Edge table " = i 3 lati (precalcolati)
Terminologie circa la rasterizzazione triangoli
3
2
Nel nostro caso (triangoli)!In generale, N e N (poligoni generici)
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Problemi con rasterizzazione di poligoniusando scan-line
• I frammenti vengono prodotti uno alla volta
• Non adatto ad una implementazione parallela– il rasterizzatore deve produrre frammenti
molto velocemente (cioè molti alla volta) se non vogliamo tenere disoccupato il processore di frammenti
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Soluzione
• Produrre frammenti a gruppi– ad es, a gruppi di 2x2 o 4x4 o 4x1 o 8x1...
• Non necessariamente tutti i componenti di un gruppo sono frammenti interni al triangolo
• Testare ogni frammento:– scartare quelli interni
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Test di appartenenza ad un triangolo
• Test di appartenenza ad un semipiano:
SI
NO
p
n
x
knx
npx
0)(
npk con
TEST:
retta definita da punto appartenente pe vettore ortognoale n
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
SI
NO
Test di appartenenza ad un triangolo
• Il semipiano e' definito da un lato:
v0=(x0, y0 )
n
v1=(x1, y1 )
q
funzione dettaEDGE
FUNCTION
(Edge = Lato, Bordo)
n = ( y1 -y0 , - ( x1 -x0 ) )p = (y0 , x0)
f(q) = n‧q - n‧p
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Test di appartenenza ad un triangolo
• Triangolo=interesezione di 3 semipiani
v0
v2
v1
SI
NO
SI
SI
SI
NO
NO
SI
SI
SI
NO
NO
SI
NO
SI
NO
NO
SI
NO
SI
SI
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Test di appartenenza ad un triangolo
• Triangolo=interesezione di 3 semipiani
NO
v0SI
NO
SI
SI
SI
NO
v1
v2
SISI
SI
SI
NO
NO
SI
NO
NO
NO
SI
NO
SI
SI
• Triangoli front-facing (senso anti-orario)
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Test di appartenenza ad un triangolo
• Scambio v1 con v2
v2
v1
v0
• Triangoli BACK-facing (senso anti-orario)
SI
NO
SI
NO
NO
NO
SINONO
NO
NO
SI
SI
NO
SI
SI
SI
NO
SI
NO
NO
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Test di appartenenza ad un triangolo
Tre Edge Functions: (una per lato)• Tutte SI (negative) :
– frammento interno a triangolo front-facing
• Tutte NO (positive):– frammento interno a
triangolo back-facing
• Miste:– frammento esterno
(scartare sempre)
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Esempio: rasterizzazionebasata sul bounding box e edge functions
1. Trovo il bounding box del triangolo
Come si trova il bounding box
di un triangolo?
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Esempio: rasterizzazionebasata sul bounding box e edge functions
1. Trovo il bounding box del triangolo1. arrotondato agli interi...2. ...divisibili per 2
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Esempio: rasterizzazionebasata sul bounding box e edge functions
1. Trovo il bounding box del triangolo1. arrotondato agli interi2. divisibili per 2
2. Processo ogni blocco (es. 2x2)1. Testo ogni frammento
nel blocco2. Se interno al triangolo
lo mando giù nel pipeline
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizziamo!
fram
men
ti(c
andid
ati
pix
els
)
Vert
ici
(punti
in R
3)
pixelfinali
(nello screen-buffer)
Vert
ici
pro
iett
ati
(punti
in R
2)
Z
rasterizer
triangoli
com
puta
zioni
per
fram
mento
set-up
rasterizer
segmenti
set-up
rasterizer
punti
set-up
com
puta
zioni
per
vert
ice
SETUP: trovobounding box
testo gruppi di frammenti(parallelizzato)
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Clipping
• Clipping!
Tutto fuori:CULLED ! no prob.
Screen
Tutto dentro:
Rasterizzo !
(benissimo)
Qualche vertice fuori,ma non tutto il triangolo
Clipping.
HAI!
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Clipping: la vecchia scuola
• Clipping!
Screen
1. Trovo intersezioni2. Unisco intersezioni
A
B
3. Divido poligono in triangoli4. Rasterizzo ogni triangolo
A poi B
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Clipping: la vecchia scuola
• Clipping!
Screen
1. Trovo intersezioni2. Unisco intersezioni
3. Divido poligono in triangoli4. Rasterizzo ogni triangolo
B
C
A
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Clipping: la vecchia scuola
• Clipping!
Screen
2. Unisco intersezioni3. Divido poligono in triangoli4. Rasterizzo ogni triangolo
B
C
A
D
1. Trovo intersezioni
Caso pessimo molto complicato
Malissimo per implementazione HW
L'HW deve prevedere ilcaso pessimo, anche se è raro
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Clipping: come si fa ora
• Clipping!
Screen
1. Trovo bounding box
3. Rasterizzo nel bounding boxcome normale
Come si interseca un bounding box
con lo schermo(cioe' col rettangolo
definito dal ViewPort)?
2. Interseco bounding box con schermo
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Un momento!
• E il clipping contro il far e il near plane?– detti anche "far plane clipping"
e "near plane clipping"
left plane
near plane
bottom plane
view frustumtop plane
far plane
right plane
Soluz: si fa testandola Z di ogni frammento
prodotto dalla rasteizzazione.
(TEST x FRAMMENTO)
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Rasterizzazione triangoli:
• Il metodo basato su bounding box etest di appartenenza (edge functions):– Vantaggi
• fortemente parallelizzabile– (gruppi 4x4)
• clipping diventa facile facile– per i planes UP, DOWN, LEFT e RIGHT
– Svantaggi• Overhead granding
– Si testano molti frammenti inutilmente– Specialmente quando...
M a r c o T a r i n i ‧ C o m p u t e r G r a p h I c s ‧ 2 0 0 6 / 0 7 ‧ U n i v e r s i t à d e l l ’ I n s u b r i a
Un caso sfortunato
Screen
Triangoli:• lunghi e stretti• messi lungo la
direzione diagonale
Sinonimo di MALE in computer graphics:(anche per questo, ma non solo)
lunghi e stretti = malemolti algoritmi portano ad artefatti
(come vedremo)
circa equilateri = benerobusti con praticamente tutti gli
algoritmi