Informatica Grafica Algoritmi 2D1 Grafica Raster l La grafica in 2D con coordinate intere viene...

Algoritmi 2D 1Informatica Grafica

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 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.


Scan Converting LinesAssumiamo: 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.


Basic Incremental Algorithm

M= Y/X (X0,Y0) uno degli end-points

IDEA: illuminare in ogni colonna il pixel più vicino allaintersezione. Calcolare il nuovo punto incrementalmente.


Implementazionevoid 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: 1) Round non é efficiente.2) Y e M sono variabili reali. Le operazioni

sui reali sono più lente.


Midpoint Line Algorithm Assume pendenza tra 0 e

1. Avendo scelto P ilprossimo può essere E o NE. Eq. della retta:F(X,Y)= Y*X-X*Y +B*X=0 Y = Y1-Y0

X = X1-X0

B = intersezione con X=0


Calcolo di dd = F(M) = F(Xp+1,Yp+1/2)

E: dnew = F(M’) = F(Xp+2,Yp+1/2) =

= Y(Xp+2) - X(Yp+1/2) + B*X =

= Y + Y(Xp+1) - X(Yp+1/2) + B*X = Y+dold

NE: dnew = F(M’’) = F(Xp+2,Yp+3/2) =

= Y(Xp+2) - X(Yp+3/2) + B*X =

= Y - X + Y(Xp+1) - X(Yp+1/2) + B*X =

= Y-X+dold

All’inizio: (Xp,Yp) = (X0,Y0)d = F(X0+1,Y0+1/2) =

= F(X0,Y0) + Y - X/2 = Y - X/2


ImplementazioneIDEA: Per non usare variabili reali moltiplico tutte le grandezze

per 2. Quindi inizializzo d= 2*Y - X

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 */}

}


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.


Intersezione con Clip Rectangle

Nel caso (a) bisognainizializzare d conF(M). Nel caso (b) bisognatrovare il punto B cheha valore:Round ((X(Ymin-1/2)) ,Ymin)


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)


Disegno Di Circonferenze

EQ: X2 + Y

2= R

2 assumendo centro nell’origine

incrementando X di 1 e prendendo la Y corrispondente:

Metodo costoso e non di buona qualitàMeglio : (Rcos , Rsin )

con 0 < < 90ºma computazionalmente inefficiente


Osservazione Per disegnare una

circonferenza basta unottavo (45º). Generalmente si sceglie ilsecondo ottante.

void CirclePoints (float x, float y, int val);{

WritePixel(x,y,val);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);

}

Si genera il resto con unaprocedura che replica i punti.


Algoritmo Mid Point

Dato P devo scegliere tra E ed SE

F(X,Y)=X2+Y2-R2 vale: 0 sul cerchio+ fuori- dentro


Calcolo di dd=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 2 =

= 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

se d>0 (scelgo SE)dnew = dold+(2 Xp -2 Yp +5)

all’inizio

(X0,Y0)=(0,R) dstart = 5/4-R


Implementazione Midpointcirclevoid 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++; } /* Select E */else{ d += (x - y)*2.0 + 5; x++; y--; } /* Select SE */CirclePoints(x, y, value);

} }

PROBLEMA: D é reale SOLUZIONE: prendere H = D - 1/4 e sostituirlo a DD<0 <=> H< - 1/4 <=> H<0 Poiché H sarà sempre

intero.


Variante Interavoid 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.


Ulteriore Miglioramento Elimina tutte le moltiplicazioni dal corpo. Calcola E e SE 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);

}}


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 SEnella regione 2 il prossimo sarà SE o S

Applichiamo il metodo del Midpoint.


FillingIdea: 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 BASEPer 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


Esempi

Nota: a è accesod è spento

a) punti ottenuti con MidPoint.

b) Punti interni.


Casi ParticolariProblema: 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.

1

2

3


Esempio

Trattamento delle righe orizzontali


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.


Calcolo IntersezioniServono strutture dati efficienti: edge table (ET)

active-edge table (AET)

ALGORITMO1) trova il minimo y in ET2) vuota AET3) 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 pixel3.3) elimina da AET gli elementi con Ymax = Y

3.4) aumenta Y di 1 ed X di conseguenza


Strutture Dati

Sorted Edge tableActive Edge Table


Filling Con Patterns Complicazione

Addizionale:ricerca del pattern.

Per disegni che si ripetono può convenire generare bitmaps.

Disegno con pattern e trasparenza


Spessore

Vedremo 2 metodi fondamentali:

1) Replica di colonne.

2) Uso di penne spesse.


Replica di Colonne

Efficiente, ma non

molto preciso.


Penna Rettangolare

Più spesso dove lapendenza é maggiore.


Clipping

Caratteristica fondamentale necessaria: Efficienza3 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)


Clipping di LineeIdea: 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.


Algoritmo Cohen-Sutherland

Idea: Assegnare ad ogni estremo un codice di 4 bit

Esempio:Prendo i codici dei due estremi

0 0 0 11 0 0 1 AND bit a bit0 0 0 1

se <> 0 0 0 0 si può scartare. Se non si può scartare allora divido la linea in 2 segmenti.


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.


Algoritmo Parametrico Cyrus-Beck

valore di t alla intersezione con il lato di PEi :

t={ N i [ Pø - PEi ]} / (-N i D) con D vettore PøP1

Eq. parametrica linea:P(t)=Pø+(P1-Pø)t

N I normale verso l’esterno del clip rectangle.

PEipunto arbitrario sul

clip rectangle.


Calcolo di tN 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


Calcolo Intersezioni

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 )

PE= potentially entering PL= potentially leaving


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;

}}}


Clipping di Poligoni

Caso critico: (a) connesso non connessoclipping

Molte situazioni diverse:


AlgoritmoSutherland-Hodgman

Ad ogni passo clippa il poligono contro la retta del clip rectangle.Si applica anche ad aree di clipping non rettangolari.

Ripeti il clipping per tutti i lati del clip rectangle


Clip Lato-Retta

Devo generare i nuovi vertici :1: output P 2: output I3: no output 4: output I,P

S nodo analizzato al passo precedente S-P lato del poligono analizzato


Antialiasing

Problema: effettoscalini (staircasing).Risolto solo in partedall’aumento dellarisoluzione.

Idea: 1) retta = rettangolo.2) Accensione

parziale dei pixels.


Intensità Pixels

Intensità proporzionale all’area coperta


Sampling non Pesato

Calcola l’area dell’intersezione di ogni pixel con il rettangolo di spessore 1.


Sampling Pesato

Calcola l’area dell’intersezione, ma pesando in funzione della distanza dal centro del pixel.

Informatica Grafica Algoritmi 2D1 Grafica Raster l La grafica in 2D con coordinate intere viene...

Documents

Transcript of Informatica Grafica Algoritmi 2D1 Grafica Raster l La grafica in 2D con coordinate intere viene...