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
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 2/53
Cuprins Notiuni generale Algoritm scan line de umplere
Cuprins
1 Notiuni generale
2 Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 3/53
Cuprins Notiuni generale Algoritm scan line de umplere
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.
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 4/53
Cuprins Notiuni generale Algoritm scan line de umplere
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.
C
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 5/53
Cuprins Notiuni generale Algoritm scan line de umplere
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.
C i N i i l Al i li d l
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 6/53
Cuprins Notiuni generale Algoritm scan line de umplere
O caracteristica importanta a graficii raster fata de grafica
vectoriala 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.
C i N ti i l Al it li d l
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 7/53
Cuprins Notiuni generale Algoritm scan line de umplere
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 8/53
Cuprins Notiuni generale Algoritm scan line de umplere
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 9/53
Cuprins Notiuni generale Algoritm scan line de umplere
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 )
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 10/53
Cuprins Notiuni generale Algoritm scan line de umplere
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 )
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 11/53
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:
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 12/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 13/53
g g
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 14/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 15/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 16/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 17/53
Exemplu:
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 18/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 19/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 20/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 21/53Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 22/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 23/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 24/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 25/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 26/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 27/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 28/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 29/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 30/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 31/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 32/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 33/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 34/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 35/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 36/53
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.
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 37/53
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.)
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 38/53
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.)
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 39/53
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.)
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 40/53
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.)
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 41/53
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.)
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 42/53
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.)
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 43/53
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.)
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 44/53
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;
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 45/53
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);}
Cuprins Notiuni generale Algoritm scan line de umplere
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 46/53
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;
}
Cuprins Notiuni generale Algoritm scan line de umplere
Al i l
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 47/53
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];}
Cuprins Notiuni generale Algoritm scan line de umplere
Al i l
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 48/53
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];}
Cuprins Notiuni generale Algoritm scan line de umplere
Al it l
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 49/53
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
Cuprins Notiuni generale Algoritm scan line de umplere
Al it l
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 50/53
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
Cuprins Notiuni generale Algoritm scan line de umplere
Al it l
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 51/53
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
Cuprins Notiuni generale Algoritm scan line de umplere
Algoritmul
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 52/53
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];
Cuprins Notiuni generale Algoritm scan line de umplere
Algoritmul
5/14/2018 algoritmScanline - slidepdf.com
http://slidepdf.com/reader/full/algoritmscanline 53/53
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);}