Grafica Raster

La grafica in 2D con coordinate intere viene detta grafica
raster.

In questa parte tratteremo le operazioni fondamentali
per disegnare su dispositivi raster come lo schermo.
Algoritmi 2D
Informatica Grafica
1
Algoritmi Fondamentali in 2D

Problemi per implementare le operazioni di OpenGL,
Java e di sistemi più complessi.

Disegno di linee e curve.

Filling di primitive.

Algoritmi di clipping.

Tecniche di antialiasing.
Algoritmi 2D
Informatica Grafica
2
Scan Converting Lines
Assumiamo:
 pendenza tra -1 ed 1
altrimenti vale
ragionamento analogo.
 spessore della linea
unitario.
 uguale spaziatura
orizzontale e verticale.
 Solo un pixel per colonna
deve essere illuminato.
Algoritmi 2D
Informatica Grafica
3
Basic Incremental Algorithm
M= DY/DX
(X0,Y0) uno degli end-points
IDEA: illuminare in ogni colonna il pixel più vicino alla
intersezione. Calcolare il nuovo punto
incrementalmente.
Algoritmi 2D
Informatica Grafica
4
Implementazione
void Line(int x0, int y0, int x1, int y1, int value)
{
/* Assumes -1<=m<=1, x0<x1 */
int x;
/* x runs from x0 to x1 in unit
increments.*/
float dy, dx, y, m;
dy=y1-y0; dx=x1-x0; m=dy/dx; y=y0;
for( x=x0; x<=x1; x++ ){
WritePixel(x,(int)floor(y+0.5),value);/* Set pixel to value */
y+=m;
}
/* Step y by slope m */
}
Problemi:
Algoritmi 2D
1) Round non é efficiente.
2) Y e M sono variabili reali. Le operazioni sui
reali sono più lente.
Informatica Grafica
5
Midpoint Line Algorithm
Assume pendenza tra 0 e 1.
 Avendo scelto P il
prossimo può essere E o NE.
 Eq. della retta:
F(X,Y)= DY*X-DX*Y +B*DX=0
DY = Y1-Y0
DX = X1-X0
B = intersezione con X=0

Algoritmi 2D
Informatica Grafica
6
Calcolo di d
d = F(M) = F(Xp+1,Yp+1/2)
E: dnew = F(M’) = F(Xp+2,Yp+1/2) =
= DY(Xp+2) - DX(Yp+1/2) + B*DX =
= DY + DY(Xp+1) - DX(Yp+1/2) + B*DX = DY+dold
NE: dnew = F(M’’) = F(Xp+2,Yp+3/2) =
= DY(Xp+2) - DX(Yp+3/2) + B*DX =
= DY - DX + DY(Xp+1) - DX(Yp+1/2) + B*DX =
= DY-DX+dold
All’inizio: (Xp,Yp) = (X0,Y0)
d = F(X0+1,Y0+1/2) =
= F(X0,Y0) + DY - DX/2 = DY - DX/2
Algoritmi 2D
Informatica Grafica
7
Implementazione
IDEA: Per non usare variabili reali moltiplico tutte le grandezze
per 2. Quindi inizializzo d= 2*DY - DX
void MidpointLine(int x0, int y0, int x1, int y1, int value)
{ int dx, dy, incrE, incrNE, d, x, y; /* Only integer variables */
dx = x1 - x0; dy = y1 - y0;
d = dy*2 - dx; incrE = dy*2; /* Initial value of d and Increment used for E */
incrNE = (dy-dx)*2;
/* Increment used for move to NE */
x = x0; y = y0; WritePixel(x, y, value); /* The start pixel */
while(x < x1){
if (d <= 0) {d += incrE; x++;}
/* Choose E */
else {d += incrNE; x++; y++; } /* Choose NE */
WritePixel(x, y, value); /* The selected pixel closest to the line */
}
}
Algoritmi 2D
Informatica Grafica
8
Esempio di Midpoint
Problemi: 1) linee da P0 a P1 e da P1 a P0 possono non
coincidere se si attraversa esattamente un midpoint.
2) linee “clippate” possono risultare sfalsate.
3) differenze di intensità di linee con pendenze
diverse.
Algoritmi 2D
Informatica Grafica
9
Intersezione con Clip Rectangle
Nel caso (a) bisogna
inizializzare d con
F(M).
 Nel caso (b) bisogna
trovare il punto B che
ha valore:

Round ((X(Ymin-1/2)) ,Ymin)
Algoritmi 2D
Informatica Grafica
10
Variazioni Di Intensità
Linea A lunghezza 10.
 Linea B lunghezza 10 * SQRT(2) ma stesso numero di
pixel.
Soluzione: intensità legata alla pendenza ( solo su schermi
antialiasing
non BW)

Algoritmi 2D
Informatica Grafica
11
Disegno Di Circonferenze
2
2
2
EQ: X + Y = R
assumendo centro nell’origine
incrementando X di 1 e prendendo la Y corrispondente:
 Metodo costoso e non di
buona qualità
Meglio : (Rcos a, Rsin a )
con 0 < a < 90º
ma computazionalmente
inefficiente
Algoritmi 2D
Informatica Grafica
12
Osservazione
Per disegnare una
 Si genera il resto con una
circonferenza basta un
procedura che replica i punti.
ottavo (45º).
void CirclePoints (float x, float y,
 Generalmente si sceglie il int val);
{
secondo ottante.
WritePixel(x,y,val);

}
Algoritmi 2D
WritePixel(y,x,val);
WritePixel(y,-x,val);
WritePixel(x,-y,val);
WritePixel(-x,-y,val);
WritePixel(-y,-x,val);
WritePixel(-y,x,val);
WritePixel(-x,y,val);
Informatica Grafica
13
Algoritmo Mid Point
Dato P devo scegliere tra E ed SE
F(X,Y)=X2+Y2-R2
vale: 0
+
Algoritmi 2D
Informatica Grafica
sul cerchio
fuori
dentro
14
Calcolo di d
d=F(M)= F(Xp+1,Yp-1/2)
se d<0 ( scelgo E)
dnew= F(Xp+2,Yp-1/2)=(Xp+2)2+(Yp-1/2)2 -R
= Xp 2 +4Xp+4+Yp 2 -Yp+1/4-R 2 =
= 2Xp+3+(Xp+1) 2 +(Yp-1/2) 2 -R 2=
= 2Xp+3+dold
2
=
se d>0 (scelgo SE)
dnew = dold+(2 Xp -2 Yp +5)
all’inizio
(X0,Y0)=(0,R)
Algoritmi 2D
dstart = 5/4-R
Informatica Grafica
15
Implementazione Midpointcircle
void MidpointCircle(int radius, int value)
{ int x, y;
float d;
/* Initialization */
x = 0;
y = radius;
d = 5.0/4 - radius; CirclePoints(x, y, value);
while(y > x){
if (d < 0) { d += x*2.0 + 3; x++; }
else{ d += (x - y)*2.0 + 5; x++; y--; }
CirclePoints(x, y, value);
}}
/* Select E */
/* Select SE */
PROBLEMA: D é reale
SOLUZIONE: prendere H = D - 1/4 e sostituirlo a D
D<0 <=> H< - 1/4 <=> H<0 Poiché H sarà sempre intero.
Algoritmi 2D
Informatica Grafica
16
Variante Intera
void MidpointCircle(int radius, int value)
{ int x, y, d;
x = 0; y = radius; d = 1 - radius;
/* Initialization */
CirclePoints(x, y, value);
while(y > x)
{
if (d < 0) { d += x*2 + 3; x++; }
/* Select E */
else { d += (x -y )*2 + 5; x++; y--;} /* Select SE */
CirclePoints(x, y, value);
}
}
In questo modo si usano solo variabili intere.
Algoritmi 2D
Informatica Grafica
17
Ulteriore Miglioramento


Elimina tutte le moltiplicazioni dal corpo.
Calcola DE e DSE incrementalmente.
void MidpointCircle(int radius, int value)
{ int x, y, d, deltaE, deltaSE;
x = 0; y = radius; d = 1 - radius;
/* Initialization */
deltaE = 3; deltaSE = 5 - radius * 2; CirclePoints(x, y, value);
while (y > x)
{
if (d < 0) { d += deltaE; deltaE += 2; deltaSE += 2; x++; }
else
{d += deltaSE; deltaE += 2; deltaSE += 4; x++; y--;}
CirclePoints(x, y, value);
}
}
Algoritmi 2D
Informatica Grafica
18
Disegno Di Ellissi
EQ: B2X2+A2Y2-A2B2 =0



Disegnamo un quadrante(altri per simmetria).
Dividiamo il quadrante in 2 regioni, regione 1 da (0,B)
fino al punto a derivata pari a -1 e regione 2 da questo
punto fino ad (A,0).
nella regione 1 il prossimo sarà E o SE
nella regione 2 il prossimo sarà SE o S
Applichiamo il metodo del Midpoint.
Algoritmi 2D
Informatica Grafica
19
Filling
Idea: individuare le sequenze orizzontali di pixels contenuti
nella primitiva (ovvio per rettangoli, più complesso per i
poligoni).
Problema: la frontiera fa parte della primitiva ?
Soluzione: solo la frontiera sinistra ed inferiore.
ALGORITMO BASE
Per ogni scan-line:
1) trova le intersezioni con i lati.
2) ordina le intersezioni per x crescenti.
3) riempi i pixels tra coppie di intersezioni.
Usa la regola pari/dispari
Algoritmi 2D
Informatica Grafica
20
Esempi
a) punti ottenuti con MidPoint.
b) Punti interni.
Nota: a è acceso
d è spento
Algoritmi 2D
Informatica Grafica
21
Casi Particolari
1
2
Problema: come distinguere i 3
casi?
Soluzione: sommare 1 per ogni
segmento che ha y
minima nel vertice.
1) sommo 1, cambio parità.
2) sommo 2, scrivo il pixel ma non
cambio parità.
3) sommo 0. nessuna operazione.
3
Algoritmi 2D
Informatica Grafica
22
Esempio
Trattamento delle righe orizzontali
Algoritmi 2D
Informatica Grafica
23
Slivers





Poligoni molto “stretti” possono
dare problemi.
Vertici: (0,0) (3,12) (5,12) (0,0)
Le scan lines per y=1 ed y=2 non
incontrano nessun pixel.
Nessuna buona soluzione.
Parzialmente risolto usando
Antialiasing.
Algoritmi 2D
Informatica Grafica
24
Calcolo Intersezioni
Servono strutture dati efficienti: edge table (ET)
active-edge table (AET)
ALGORITMO
1) trova il minimo y in ET
2) vuota AET
3) ripeti fino a che (AET vuota) and (ET vuota)
3.1) muovi la lista Y=Ymin da ET a AET e ordina AET
3.2) accendi i pixel
3.3) elimina da AET gli elementi con Ymax = Y
3.4) aumenta Y di 1 ed X di conseguenza
Algoritmi 2D
Informatica Grafica
25
Strutture Dati
Sorted Edge table
Algoritmi 2D
Active Edge Table
Informatica Grafica
26
Filling Con Patterns

Complicazione
Addizionale:
ricerca del pattern.

Per disegni che si
ripetono può convenire
generare bitmaps.
Disegno con pattern e trasparenza
Algoritmi 2D
Informatica Grafica
27
Spessore

Vedremo 2 metodi fondamentali:
1) Replica di colonne.
2) Uso di penne spesse.
Algoritmi 2D
Informatica Grafica
28
Replica di Colonne
Efficiente, ma non
molto preciso.
Algoritmi 2D
Informatica Grafica
29
Penna Rettangolare
Più spesso dove la
pendenza é maggiore.
Algoritmi 2D
Informatica Grafica
30
Clipping
Caratteristica fondamentale necessaria: Efficienza
3 modi diversi:
1) Clipping analitico.
2) Clipping durante scan conversion.
3) Attraverso Canvas e Copy_pixel.
1) Applicabile a packages grafici interi e virgola mobile,
2D e 3D
2) - 3) solo interi e 2D (grafica raster)
Algoritmi 2D
Informatica Grafica
31
Clipping di Linee
Idea: analizziamo solo gli estremi. Semplice se i 2 estremi
(od anche uno solo ) sono nel clip rectangle.
Soluzione semplice ma inefficiente: calcolare le
intersezioni con le 4 linee del clip rectangle.
Algoritmi 2D
Informatica Grafica
32
Algoritmo
Cohen-Sutherland
Idea: Assegnare ad ogni estremo un codice di 4 bit
Esempio:
Prendo i codici dei due estremi
0001
1 0 0 1 AND bit a bit
0001
se <> 0 0 0 0 si può scartare. Se
non si può scartare allora divido
la linea in 2 segmenti.
Algoritmi 2D
Informatica Grafica
33
Dividere una Linea


Scelgo un estremo esterno e calcolo l’ intersezione con un
lato del clip rectangle.
Ordine dei lati del clip rectangle: top-bottom-right-left.
Algoritmi 2D
Informatica Grafica
34
Algoritmo Parametrico
Cyrus-Beck
Eq. parametrica linea:
P(t)=Pø+(P1-Pø)t
N I normale verso
l’esterno del clip
rectangle.
PEi punto arbitrario
sul clip rectangle.
valore di t alla intersezione con il lato di PEi :
t={ N i  [ Pø - PEi ]} / (-N i  D)
con D vettore PøP1
Algoritmi 2D
Informatica Grafica
35
Calcolo di t
N i x [ P(t) - PEi ] = 0
N i x [ Pø +(P1-Pø)t - PEi ] = 0
N i x [ Pø - PEi ] + N i x (P1-Pø) t =0
t = { N i x [ Pø - PEi ]} / (-N i x D)
Quali intersezioni sono interessanti?
se t non appartiene a [0,1] allora si scarta se t appartiene a [0,1] non é detto
(per es. linea 1 e 2 nella slide seguente).
Etichetto le intersezioni come: PE potentially entering
PL potentially leaving
Algoritmi 2D
Informatica Grafica
36
Calcolo Intersezioni
PE= potentially entering PL= potentially leaving
Se Ni • D < 0 => PE
Ni • D > 0 => PL
Dobbiamo trovare una sequenza (PE , PL)
calcolo tE = massimo t tale che P(tE) = PE (uno dei)
calcolo tL = minimo t tale che P(tL) = PL (uno dei )
Algoritmi 2D
Informatica Grafica
37
Implementazione
{precalculate Ni and select a PEi for each edge
for ( each line segment to be clipped ) {
if (P1 = P0) line is degenerate so clip as a point;
else{ tE = 0; tL = 1;
for( each candidate intersection with a clip edge ){
if( Ni . D !=0 ) /* Ignore edges parallel to line */
{
calculate t;
use sign of Ni . D to categorize as PE or PL;
if( PE ) tE = max(tE, t); if( PL ) tL = min(tL, t);}
}
if(tE > tL) return nil;
else return P(tE) and P(tL) as true clip intersections;
}}
}
Algoritmi 2D
Informatica Grafica
38
Clipping di Poligoni
Molte situazioni diverse:
Caso critico: (a) connesso  non connesso
clipping
Algoritmi 2D
Informatica Grafica
39
Algoritmo
Sutherland-Hodgman
Ripeti il clipping per tutti i lati del clip rectangle
Ad ogni passo clippa il poligono contro la retta del clip
rectangle.
Si applica anche ad aree di clipping non rettangolari.
Algoritmi 2D
Informatica Grafica
40
Clip Lato-Retta
S nodo analizzato al passo precedente
 S-P lato del poligono analizzato

Devo generare i nuovi vertici :
1: output P
2: output I
3: no output
4: output I,P
Algoritmi 2D
Informatica Grafica
41
Antialiasing
Problema: effetto
scalini (staircasing).
Risolto solo in parte
dall’aumento della
risoluzione.
Idea:
1) retta = rettangolo.
2) Accensione parziale
dei pixels.
Algoritmi 2D
Informatica Grafica
42
Intensità Pixels
Intensità proporzionale all’area coperta
Algoritmi 2D
Informatica Grafica
43
Sampling non Pesato
Calcola l’area dell’intersezione di ogni pixel con il
rettangolo di spessore 1.
Algoritmi 2D
Informatica Grafica
44
Sampling Pesato
Calcola l’area dell’intersezione, ma pesando in
funzione della distanza dal centro del pixel.
Algoritmi 2D
Informatica Grafica
45