algoritmscanline

5/14/2018 algoritmScanline - slidepdf.com

http://slidepdf.com/reader/full/algoritmscanline 1/53

Cuprins Notiuni generale Algoritm scan line de umplere

Filling - Umplerea poligoanelor

Marian Ioan MUNTEANU

Al.I.Cuza University of Iasi, Romaniawebpage: http://www.math.uaic.ro/∼munteanu

5 Noiembrie 2009

http://goforward/

http://find/

http://goback/




Cuprins

1 Notiuni generale

2 Algoritm scan line de umplere

http://find/




O caracteristica importanta a graficii raster fata de graficavectoriala este posibilitatea utilizarii elementelor grafice pline , adicasolide.

Procesul se bazeaza pe o carenta a sistemului vizual uman sianume: integrarea spatiala ıntre obiecte pe care ochiul nu este ın

stare sa le distinga din cauza absentei rezolutiei.

Numarul receptorilor vizuali fiind limitat, daca se deseneazaelemente grafice distincte dar suficient de aproape (cum ar fi doipixeli pe un monitor CRT) - ochiul va putea sa le perceapa ca pe

un singur obiect.O multime de pixeli de aceeasi culoare, unul langa altul, va fiasadar vazuta, de catre ochiul uman, ca o singura figura coloratauniform.

http://goforward/

http://find/

http://goback/









C

http://goforward/

http://find/

http://goback/









C i N i i l Al i li d l

http://goforward/

http://find/

http://goback/




O caracteristica importanta a graficii raster fata de grafica

vectoriala este posibilitatea utilizarii elementelor grafice pline , adicasolide.





C i N ti i l Al it li d l

http://goforward/

http://find/

http://goback/




Problema

Se considera un poligon dat prin intermediul varfurilor sale.Sa se deseneze pixelii care apartin acestuia.

Va trebui sa individualizam secventele orizontale de pixeli continuteın primitiva, algoritm numit de scan-line . Ideea este de a ”misca” olinie orizontala din pozitia cea mai de jos care intersecteazapoligonul catre pozitia cea mai de sus (cu o unitate la fiecare pas)

si de a aplica un algoritm de scan-conversion pe linie, de fiecaredata.


http://goforward/

http://find/

http://goback/




Exemplu

Pentru a desena un dreptunghi plin, cu laturile paralele cu axele de

coordonate, vor trebui iluminati pixelii interiori dreptunghiului

for y from y min to y max of the rectangle (y scan-line)for x from x min to x max (pixel cu pixel ın span)

putpixel (x , y , color )


http://goforward/

http://find/

http://goback/



Cuprins Notiuni generale lgoritm scan line de umplere

Problema generala

Scopul nostru este de a construi un algoritm generic capabil safaca ”filling” pentru poligoane de orice tip: concave, convexe, culaturi care se intersecteaza:


http://goforward/

http://find/

http://goback/



p ¸ g g p

Regula par – impar

Se afla un punct ın interiorul unui poligon?

• dintr-un punct arbitrar P se deseneaza o semidreapta• se numara intersectiile cu laturile• punctul P este interior daca numarul de intersectii este impar.


http://goforward/

http://find/

http://goback/



g g





http://goforward/

http://find/

http://goback/







http://goforward/

http://find/

http://goback/




Se afla un punct ın interiorul unui poligon?• dintr-un punct arbitrar P se deseneaza o semidreapta• se numara intersectiile cu laturile• punctul P este interior daca numarul de intersectii este impar.


http://goforward/

http://find/

http://goback/



Exemplu:


http://goforward/

http://find/

http://goback/



Modalitatea cea mai la ındemana de a calcula intersectiile este sase utilizeze scan-conversion pentru liniile corespunzatoare fiecareilaturi a poligonului.

Aceasta aproximatie poate sa produca rezultate incorecte deoarece

algoritmul de rasterizare pentru linii nu are not iunea conceptului deınauntru (interior) si ın afara (exterior) si astfel pot fi selectionatipixeli care se afle ın afara poligonului.

Aceasta este ın particular de nedorit cand avem de convertit

poligoane de culori diferite cu laturi comune: ın acesta maniera vorexista pixeli ai unui poligon care ”invadeaza” alt poligon generandastfel un efect vizual incorect.


http://goforward/

http://find/

http://goback/









http://goforward/

http://find/

http://goback/


http://slidepdf.com/reader/full/algoritmscanline 21/53Cuprins Notiuni generale Algoritm scan line de umplere

http://goforward/

http://find/

http://goback/



Descrierea algoritmului

Operatia de filling pentru o singura scan-line consta ın 3 pasi:

1. Se calculeaza intersectiile dintre scan-line si toate laturilepoligonului.

2. Se ordoneaza intersectiile dupa abscisa x.3. Se aprind pixelii ıntre perechi de intersectii care sunt interioarepoligonului, utilizand, pentru a determina care pixel este interior,asa-numita regula odd-parity care spune:

a) paritatea init iala este para;

b) fiecare intersectie schimba paritatea;c) se deseneaza pixelii cand paritatea este impara;d) nu se deseneaza nimic cand paritatea este para.


http://goforward/

http://find/

http://goback/










http://goforward/

http://find/

http://goback/








b) fiecare intersectie schimba paritatea;c) se deseneaza pixelii cand paritatea este impara;

d) nu se deseneaza nimic cand paritatea este para.


http://goforward/

http://find/

http://goback/










http://goforward/

http://find/

http://goback/



Probleme care apar

Inainte de a analiza problemele de intersectie si sorting, sa vedemcum se defineste, ın diferite situatii, daca un pixel este interior saunu poligonului.

Va trebui sa raspundem la cateva ıntrebari:

A. Daca o intersectie cu o valoare generica a lui x esterationala, cum determinam care dintre cei doi pixeli de peorizontala (care ıncadreaza punctul ideal) este cel cautat?

• daca ıntalnim o intersectie cand venim din interiorul

poligonului (paritatea - parity bit - este impara) rotunjim laıntregul mai mic pentru a ramane tot ınauntru;

• daca venim din afara (exteriorul) poligonului (paritatea estepara), rotunjim la ıntregul urmator pentru a intra ınauntru.


http://goforward/

http://find/

http://goback/



Probleme care apar








http://goforward/

http://find/

http://goback/



Probleme care apar

B. Cum se trateaza cazul special al unei intersectii cucoordonate ıntregi? Pentru a evita conflicte de atributie pentrulaturi adiacente se defineste ca o intersectie cu coordonate ıntregila limita din stanga pentru span de pixeli este interna poligonului,

iar la limita din dreapta este externa.

C. Si daca intersectia cu coordonate ıntregi se refera la unvarf? In calculul paritatii se va considera doar varful y min nu siy max al unei laturi.

D. Cum se trateaza cazul special al varfurilor care definesclaturi orizontale? Este de ajuns sa consideram ca varfurile uneilinii orizontale nu influenteaza calculul paritatii si se obtineautomat ca laturile orizontale de jos vor fi desenate, cele de sus nu.


http://goforward/

http://find/

http://goback/



Probleme care apar


iar la limita din dreapta este externa.C. Si daca intersectia cu coordonate ıntregi se refera la unvarf? In calculul paritatii se va considera doar varful y min nu siy max al unei laturi.



http://goforward/

http://find/

http://goback/



In figura considerata, la scan-line 6 avem urmatoarea situatie:

Initial paritatea este para. Cand ajungem ın punctul (2, 6) avem

intersectie la limita din stanga, deci paritatea se schimba si devineimpara. Se ıncepe aprinderea pixelilor. Ajungem ın F care estey min pentru (FG ) si (EF ) deci paritatea se schimba de doua ori siastfel ramane impara. Se continua aprinderea pixelilor. Ajungemın C care este maxim pentru (BC ) (nu influenteaza paritatea), iar

latura (CD ) fiind orizontala, din nou nu schimb paritatea.

Continuam desenarea pixelilor.Ajung ın D care este minim pentru

(DE ), astfel paritatea devine para.Se ınceteaza desenarea pixelilor.(Asadar, pe segmentul orizontal(CD ) paritatea este impara si prinurmare, segmentul se traseaza.)


http://goforward/

http://find/

http://goback/










http://goforward/

http://find/

http://goback/



Algoritmul

Fie x [k ], y [k ] coordonatele varfului P k al poligonului si n numarulde laturi. Fie nr int numarul de intersectii pe o anumita scan line.

Fie de asemenea x int[k] abscisa intersectiei k cu scan line.

int x[100], y[100]; // coordonatele varfurilorfloat x int[100]; // coordonata x a intersectiilorint u, k, n, nr int, ymin, ymax;


http://goforward/

http://find/

http://goback/



Algoritmul

/* functie de calcul a marginii din stanga */int stg(float z){ /* daca z este intreg, il returneaza

daca z este rational, il rotunjeste la intregul urmator */if (z == int (z)) return z;

else return int (z) + 1;}

/* functie de calcul a marginii din dreapta */int dr(float z)

{ /* daca z este intreg, returneaza z-1daca z este rational, il rotunjeste la intregul precedent */if (z == int (z)) return z-1;

else return int (z);}


http://goforward/

http://find/

http://goback/



Algoritmul

/* functie de sortare */float *qsort (float *a, int L, int R){

int h, j;float temp;

for(h=L; h<=R-1; h++)for(j=h+1; j<=R; j++)if (a[h]>a[j]){

temp=a[h];

a[h]=a[j];a[j]=temp;

}return a;

}


Al i l

http://goforward/

http://find/

http://goback/



Algoritmul

/* algoritmul de fill pe scan line */void scanline(int y0){int i;nr int= 0;

for (i=1; i <=n; i++){

if ((y [i + 1] − y 0) ∗ (y 0 − y [i ]) > 0)/* linia scan taie interiorul segmentului */

{nr int++;x int[nr

int]=(y0−y[i])∗float((x[i+1]−x[i]))/float((y[i+1]−y[i]))+x[i];}


Al i l

http://goforward/

http://find/

http://goback/



Algoritmul

else if (y[i]==y0)/* linia scan trece printr-un varf al poligonului */

if ((y[i-1]>y0) && (y[i+1]>y0)){ /* avem situatia \/ pentru varfuri */

nr int+=2; /* consider varful Pi de doua ori */

x int[nr int-1]=x[i];x int[nr int]=x[i];}else if ((y[i-1]−y0)∗(y[i+1]−y0)< 0)

/* avem situatia laturilor una in continuarea celeilalte */{nr int ++;x int[nr int]=x[i];}


Al it l

http://goforward/

http://find/

http://goback/



Algoritmul

else if (y[i+1]==y0) /* avem latura orizontala */if ((y[i+2]>y0) && (y[i-1]>y0)){ /* avem situatia \ / */

nr int +=2;

x int[nr int-1]=x[i];x int[nr int]=x[i+1];} else

if ((y[i+2]<y0)&&(y[i-1]>y0)){ /* avem cazul y[i]=y[i+1] intre y[i-1] > y[i+2] */

nr int++;x int[nr int]=x[i];} else


Al it l

http://goforward/

http://find/

http://goback/



Algoritmul

if ((y[i+2]>y0)&&(y[i-1]<y0)){ /* avem cazul y[i]=y[i+1] intre y[i-1] < y[i+2] */

nr int++;x int[nr int]=x[i+1];}

} //end for

/* reamintim ca liniile orizontale se deseneaza daca sunt inferioare

si nu se deseneaza daca sunt linii orizontale superioare */

qsort(x int, 1, nr int);// se sorteaza crescator abscisele intersectiilor


Al it l

http://goforward/

http://find/

http://goback/



Algoritmul

k=1;while (k < nr int){

delay(10);line(stg(x int[k]), y0, dr(x int[k+1]), y0);k +=2;

}

} // end functie scanline


Algoritmul

http://goforward/

http://find/

http://goback/



Algoritmul

void main ( ) {clrscr( );cout<<”Introduceti numarul de laturi:”<<endl;cout<<”n=”;cin>>n;

cout<<”Introduceti coordonatele varfurilor:”<<endl;for(k=1; k<=n; k++){cout<<”x[”<<k<<”]=”; cin>>x[k];cout<<”y[”<<k<<”]=”; cin>>y[k];

cout<<endl;}

x[0]=x[n]; y[0]=y[n];x[n+1]=x[1]; y[n+1]=y[1];x[n+2]=x[2]; y[n+2]=y[2];


Algoritmul

http://goforward/

http://find/

http://goback/



Algoritmul

for(k=1; k<=n; k++)line(x[k], y[k], x[k+1], y[k+1]);

/* aflarea minimului si maximului pentru scan line */ymin=x[1]; ymax=y[1];

for (k=1; k<=n; k++) if (y[k] > ymax) ymax=y[k];for (k=1; k<=n; k++) if (y[k] < ymin) ymin=y[k];

/* fill pe scan line de la ymin la ymax */for (u=ymin; u <= ymax; u++)

{setcolor(u%5+1); // umplerea se face cu 5 culoriscanline(u);}

http://goforward/

http://find/

http://goback/

algoritmscanline

Documents