Algoritm de scanare a liniei
Scan Line este un algoritm pentru rasterizarea eficientă a poligoanelor.
Dat fiind un poligon , exprimat sub formă de segmente (x min , y min , x max , Y max ), este posibil să se determine punctele interne ale poligonului trasând linii paralele cu axa x și calculând intersecțiile cu segmentele a poligonului. Ori de câte ori o linie de scanare intersectează un segment al poligonului, putem considera punctele ulterioare, până la următoarea intersecție, ca fiind interne. Aceste grupuri de puncte se numesc întinderi și reprezintă pixelii care trebuie să fie colorați în interiorul imaginii.
Există trei pași în procesul de determinare a intervalelor:
- Determinați intersecțiile dintre linia de scanare și poligoane
- Ordonați aceste intersecții în funcție de axa x
- Determinați punctele interne folosind intersecțiile de pe linia calculată anterior
Algoritmul
Înainte de a începe, trebuie să creăm un tabel pentru a salva punctele de intersecție dintre segmentele poligonului. Acest tabel se numește ET (Edge Table), este format din (y max - y min ) rânduri și conține, în fiecare rând, o listă de segmente care au ca y min valoarea y a liniei de scanare. Un segment din listă este reprezentat cu coordonata y max a segmentului (extremă cu cel mai mare y), coordonata x min a segmentului și inversul pantei.
Acum suntem gata să determinăm întinderile pentru fiecare linie de scanare: inițializăm o altă listă goală, numită AET (Active Edge Table) pentru a reprezenta marginile active la fiecare linie de scanare.
Începând de la prima linie a listei ET, această linie este adăugată la AET, calculând întinderile folosind regula par-impar. Regula constă în împărțirea punctelor liniei de scanare în interne și externe: la început punctele sunt externe și, la fiecare intersecție cu laturile poligonului, acestea se schimbă în interior (sau invers, trecând de la intern la extern ). Laturile paralele cu linia de scanare și nici cel mai mic sau cel mai mare vârf al poligonului în ceea ce privește coordonata y nu ar trebui să fie luate în considerare în regulă.
Ulterior, tabelul AET este actualizat adăugând inversul pantei la coordonata x a segmentului, pentru a obține poziția x corectă pentru următoarea linie de scanare.
O notă merită alegerea rotunjirii punctelor pentru a fi considerate ca fiind interne: în AET punctele x, obținute ca suma x min cu inversul pantei, nu vor presupune valori întregi. Prin urmare, pentru a aplica regula impar-pare, este necesar să se rotunjească punctele x ale intersecțiilor liniei de scanare cu segmentele poligonului. În special, dacă treceți de la punctele interne la cele externe, coordonata x a punctului este rotunjită la cel mai mare număr întreg, în timp ce dacă treceți de la punctele interne la cele externe, aceasta este rotunjită la cel mai mic număr întreg.
Colorarea continuă până când ET este gol
linkuri externe
- medialab.di.unipi.it , http://medialab.di.unipi.it/web/IUM/Fondamenti/cap4.htm .
