Computer Graphics
Lezione 7:
rasterizzazione
la fabbrica dei frammenti
Università dell’Insubria
Facoltà di Scienze MFN - Varese
Corso di Laurea in Informatica
Anno Accademico 2006/07
Marco Tarini
setup
rasterizer
triangoli
setup
rasterizer
segmenti
computazioni
per frammento
rasterizer
punti
frammenti
(punti in R2)
setup
(candidati pixels)
Z
Vertici
proiettati
computazioni
per vertice
Vertici
(punti in R3)
Rasterizziamo!
pixel
finali
(nello
screen-buffer)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Rasterizzazione Segmenti
v1
v0
• Produrre i frammenti
il più vicino possibile
alla linea ideale
lavoriamo con coord intere.
Arrotondarle prima.
Attenzione agli estremi!
Pensare al Line LOOP
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Rasterizzazione di segmenti
• Vogliamo avere la
sequenza di frammenti
che
– approssimi al meglio il
segmento
• e quindi
– sia il più in linea retta
possibile
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Rasterizzazione di segmenti
coefficienti angolari m1
→
dy=7
1 frammento per colonna
dx=9
Considerando approx di segmenti
di circa un pixel di spessore
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Rasterizzazione di segmenti
coefficienti angolari m>1
→
dy=10
1 frammento per riga
dx=3
Consideriamo i due casi
separatemente.
Ne vediamo uno.
(l'altro è simile)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Rasterizzazione di segmenti:
algoritmo analitico
Scrivo la retta come:
dy=7
m=dy/dx=7/9
y  mx  B
( m 1)
dx=9
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Rasterizzazione di segmenti:
algoritmo analitico
Rasterizziamo da (x0,y0)
a (x1,y1)
P1
P0
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Algoritmo analitico
Per x che va da x0 a x1
•
•
x ++
y ← mx + B
•
•
arrotondare y
produrre frammento ( x , y )
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
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)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Segmenti di Spessore diverso da uno
es: spessore 3
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Segmenti di Spessore diverso da uno
Chiaramente è solo una approssimazione
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Segmenti di Spessore diverso da uno
• In OpenGL
void glLineWidth( width );
Non necessariamente
un intero
(se si usa anti-aliasing,
vedi poi)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
setup
rasterizer
triangoli
setup
rasterizer
segmenti
computazioni
per frammento
rasterizer
punti
frammenti
(punti in R2)
setup
(candidati pixels)
Z
Vertici
proiettati
computazioni
per vertice
Vertici
(punti in R3)
Rasterizziamo!
pixel
finali
(nello
screen-buffer)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Rasterizziamo triangoli
Algoritmo scan-line
Idea Base:
1. ordiniamo per y
2. 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
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Rasterizziamo triangoli
Algoritmo scan-line
Idea Base:
1. ordiniamo per y
2. 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)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
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
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Terminologie circa la rasterizzazione triangoli
• "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 22 lati attuali
"Edge table " = i 3 lati (precalcolati)
Nel nostro caso (triangoli)!
In generale, N e N (poligoni generici)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Problemi con rasterizzazione di poligoni
usando 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
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
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
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Test di appartenenza ad un triangolo
• Test di appartenenza ad un semipiano:
SI
n
NO
p
x
retta definita
da punto appartenente p
e vettore ortognoale n
TEST:
( x  p)  n  0
xn  k
con
k  pn
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Test di appartenenza ad un triangolo
• Il semipiano e' definito da un lato:
n
v0=(x0, y0 )
SI
v1=(x1, y1 )
NO
q
p = (y0 , x0)
n = ( y1 -y0 , - ( x1 -x0 ) )
f(q) = n‧q - n‧p
funzione
detta
EDGE
FUNCTION
(Edge = Lato, Bordo)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Test di appartenenza ad un triangolo
• Triangolo=interesezione di 3 semipiani
NO
SI
NO
SI
NO
NO
SI
SI
NO
v0
NO
SI
SI
v2
SI
SI
SI
v1
SI
NO
SI
NO
NO
SI
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Test di appartenenza ad un triangolo
• Triangolo=interesezione di 3 semipiani
• Triangoli front-facing (senso anti-orario)
NO
SI
NO
SI
NO
NO
SI
SI
NO
v0
NO
SI
SI
v2
SI
SI
SI
v1
SI
NO
SI
NO
NO
SI
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Test di appartenenza ad un triangolo
• Scambio v1 con v2
• Triangoli BACK-facing (senso anti-orario)
SI
NO
SI
NO
SI
SI
NO
NO
SI
v2
SI
NO
NO
v0
NO
NO
NO
v1
NO
SI
NO
SI
SI
NO
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
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)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Esempio: rasterizzazione
basata sul bounding box e edge functions
Come si trova il
bounding box
di un triangolo?
1.
Trovo il bounding box del triangolo
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Esempio: rasterizzazione
basata sul bounding box e edge functions
1.
Trovo il bounding box del triangolo
1. arrotondato agli interi...
2. ...divisibili per 2
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Esempio: rasterizzazione
basata sul bounding box e edge functions
1.
Trovo il bounding box del triangolo
1. arrotondato agli interi
2. divisibili per 2
2.
Processo ogni blocco (es. 2x2)
1. Testo ogni frammento
nel blocco
2. Se interno al triangolo
lo mando giù nel pipeline
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
setup
rasterizer
triangoli
setup
rasterizer
segmenti
SETUP: trovo
bounding box
computazioni
per frammento
rasterizer
punti
frammenti
(punti in R2)
setup
(candidati pixels)
Z
Vertici
proiettati
computazioni
per vertice
Vertici
(punti in R3)
Rasterizziamo!
pixel
finali
(nello
screen-buffer)
testo gruppi di frammenti
(parallelizzato)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Clipping
• Clipping!
Screen
Qualche
vertice fuori,
ma non tutto
il triangolo
Clipping.
Tutto dentro:
Rasterizzo !
HAI!
Tutto fuori:
CULLED !
 no prob.
(benissimo)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Clipping: la vecchia scuola
• Clipping!
Screen
A
B
1.
2.
3.
4.
Trovo intersezioni
Unisco intersezioni
Divido poligono in triangoli
Rasterizzo ogni triangolo
A poi B
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Clipping: la vecchia scuola
• Clipping!
Screen
A
B
C
1.
2.
3.
4.
Trovo intersezioni
Unisco intersezioni
Divido poligono in triangoli
Rasterizzo ogni triangolo
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Clipping: la vecchia scuola
Caso pessimo molto complicato
• Clipping!
Malissimo per implementazione HW
L'HW deve prevedere il
caso pessimo, anche se è raro
Screen
D
B
C
A
1.
2.
3.
4.
Trovo intersezioni
Unisco intersezioni
Divido poligono in triangoli
Rasterizzo ogni triangolo
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Clipping: come si fa ora
• Clipping!
Screen
Come si interseca un
bounding box
con lo schermo
(cioe' col rettangolo
definito dal ViewPort)?
1. Trovo bounding box
2. Interseco bounding box
con schermo
3. Rasterizzo nel bounding box
come normale
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Un momento!
• E il clipping contro il far e il near plane?
– detti anche "far plane clipping"
e "near plane clipping"
view frustum
top plane
left plane
near plane
right plane
far plane
bottom plane
Soluz: si fa testando
la Z di ogni frammento
prodotto dalla
rasteizzazione.
(TEST x FRAMMENTO)
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Rasterizzazione triangoli:
• Il metodo basato su bounding box e
test 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...
Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria
Un caso sfortunato
Sinonimo di MALE
in computer graphics:
(anche per questo, ma non solo)
lunghi e stretti = male
Screen
molti algoritmi portano ad artefatti
(come vedremo)
circa equilateri = bene
robusti con praticamente tutti gli algoritmi
Triangoli:
• lunghi e stretti
• messi lungo la
direzione diagonale

Marco Tarini ‧ Computer GraphIcs ‧ 2006/07 ‧ Università dell’Insubria