1

Scan conversione di poligoni

Daniele Marini

2

Test interno-esternoScan conversione di un poligono = decidere se pixel interno

Test di intersezione: • se p è interno ogni semiretta da p interseca il poligono un numero dispari di volte• se p è esterno le intersezioni sono pari

3

4

OpenGL

OGL garantisce la scan conversione di poligoni convessi

• creare modelli solo convessi• triangolare (o tassellare)

• non troppo sottili o troppo lunghi• più equilateri possibile (Delaunay)

5

GLUtesselator * una_tassellazione;

una_tassellazione = gluNewTess();

gluTessBeginPolygon(una_tassellazione, NULL);

gluTessBeginContour(una_tassellazione);for (i=0; i<nvertici;i++)

glTessVertex(una_tassellazione,vertex[i], vertex[i]);gluTessEndContour();gluTessEndPolygon(una_tassellazione);

Tassellazione: struttura generale

6

gluTessBeginPolygon(tess, NULL); gluTessBeginContour(tess); gluTessVertex(tess, v1, v1); gluTessVertex(tess, v2, v2); gluTessVertex(tess, v3, v3); gluTessVertex(tess, v4, v4); gluTessEndContour(tess); gluNextContour(tess, GLU_INTERIOR); gluTessBeginContour(tess); gluTessVertex(tess, v5, v5); gluTessVertex(tess, v6, v6); gluTessVertex(tess, v7, v7); gluTessEndContour(tess); gluTessEndPolygon(tess);

v1 v2

v3v4

v5 v6

v7

7

v1 v2

v3v4

v5 v6

v7

v1 v2

v3v4

v5

v6

v7

8

Scan Conversione e z-buffer

Vertici e normali non clippate, trasformate per proiezione prospettica, (z esiste ancora!), computo del colore ai vertici …. resta da fare:

Proiezione ortografica, rimozione superfici nascoste, shading: integrato tutto in z-buffer!

Si procede per linee di scansione per ogni poligono, incrementando y e x in coordinate NDC e incrementando z in funzione dell’equazione del piano

9

A ogni incremento di x e y si procede con interpolazione bilineare (Gouraud o Phong)

Durante questa fase si possono applicare texture.

10

Metodi alternativi

• Flood fill– Scan conversione dei bordi con Brasenham– Dato un punto iniziale (seme) esplorare

ricorsivamente il vicinato per decidere se i pixel sono esterni o interni

• Scan line– Itera per y decrescenti (crescenti) decidi i

poligoni attivi e il test interno-esterno

11

Flood fill

flood-fill(int x, int y);{

if(read_pixel(x,y)==WHITE){

write_pixel(x,y,BLACK);flood_fill(x-1,y);flood_fill(x+1,y);flood_fill(x,y-1);flood_fill(x,y+1);

}}

12

Scan Line

La regola interno-esterno permette di determinare “span”, tutti i pixel di uno span assumono lo stesso colore (o vengono interpolati per shading)

I poligoni si organizzano in una lista di poligoni attivi e i bordi di un poligono attivo vengono organizzati in lista di bordi attivi

13

Scan conversione di linee

Convertire un segmento i cui estremi sono espressi comecoppie di numeri reali, in una serie di PIXEL sullo schermodel computer.

Problema di conversione da numero reale a intero e dicampionamento su una griglia regolare di punti.

Un metodo inadeguato dà luogo a “alias” molto evidenti;Aliasing è comunque sempre presente.

14

Requisiti

• Velocità

• luminosità uniforme

• stile linea

• antialiasing

15

Algoritmo base

• Calcola rapporto incrementale dy/dx

• genera punti sulla retta con l’equazione esplicita: yi = mxi +b

• ad ogni passo arrotonda i valori all’intero prossimo: Round(yi)=Floor(0.5+yi)

• complessità alta: 1 moltiplicazione, 1 somma, 1 arrotondamento ad ogni passo

16

(xi,yi)

(xi+1, yi+m)(xi, Round(yi))

(xi+1, Round(yi+m))

17

• L’algoritmo opera su rette con |m|<=1, e incrementa ad ogni passo x di una unità (rette con pendenza compresa tra -45° e +45°)

• Per |m|>1 si applica l’equazione x=f(y) e si incrementa (o decrementa) y di una unità

18

19

Metodo incrementale

• Si evita il prodotto

• yi+1 = mxi+1 + b = m(xi + dx) + b = yi + mdx

• Se dx=1 allora yi+1 = yi + m

• questo metodo è chiamato DDA, Digital Differential Analyzer

20

Algoritmo DDA

procedure line(x0,y0,x1,y1:float; value:integer);var x:integer; dx,dy,y,m: float;begin dy:=y1-y0;

dx:=x1-x0;m:=dy/dx;y:=y0;for x:=x0 to x1 do

beginWritePixel(x,Round(y),value);y:=y+mend

end.

21

Il metodo di Brasenham

• Niente prodotti: solo somme e confronti semplici

• si basa sulla valutazione dell’errore

• sfrutta la conoscenza passata

cfr. Foley, Van Dam et al.

22

Si assume 0<= m <=1

(xp,yp)

E

NE

MQ

L’algoritmo valuta NE-Q e E-Q, il segno decide seattivare E o NE

23

• Per il segno e’ sufficiente vedere da che lato è M rispetto al segmento

• valutare l’equazione implicita della retta nel punto M: F(x,y): ax+by+c=0

• dy=y1-y0, dx=x1-x0 quindi la F(x,y) è:

dy.x + dx.y + dx = 0

• occorre valutare la F(x,y) in (xp+1, yp+1/2)

• si adotta la variabile di decisione d:

d = dy(xp+1)+ dx(yp+1/2) + dx

24

• Se d>0 seleziona NE

• Se d<=0 seleziona E

• Al passo successivo p+1 la scelta dipende dalla precedente:

• caso E - al passo prec. si è scelto E si incrementa M di una unità, la variabile di decisione si modifica:

dnew = dold + dy

25

• Caso NE - al passo prec. si è scelto NE, si incrementa M sia in y sia in x:

dnew = dold +dy-dx

26

Algoritmo di Brasenham (MidPointLine)Procedure MidPointLine(x0,y0,x1,y1:float;value:integer);var dx,dy,deltaE,deltaNE,d,x,y:integer;begin

dx:=x1-x0; dy:=y1-y0; d:= 2*dy - dx; {d_start}deltaE:=2*dy; deltaNE:=2*(dy-dx);x:=x0; y:=y0;WritePixel(x0,y0,value);while x<x1 do

begin if d<=0 then

begind:=d+deltaE;x:=x+1end

elsebegind:=d+deltaNE; x:=x+1; y:=y+1;end;

WritePixel(x,y,value);end {while}

end.