Algoritmo scan line: differenze tra le versioni

Versione delle 18:44, 6 nov 2014

Versione attuale delle 19:50, 19 feb 2019

(13 versioni intermedie di 9 utenti non mostrate)

Riga 1:

{{W|geometria|novembre 2014}}

'''Scan Line''' è un algoritmo per il filling efficente di poligoni.<br />

<br />

Dato un poligono, espresso sotto forma di segmenti (x_min,y_min,x<nowiki>_max</nowiki>,Y_max) , è possibile determinare i punti interni del poligono tracciando delle linee parallele all'asse x e calcolando le intersezioni con i segmenti del poligono. Ogni volta che una linea di scansione interseca un segmento del poligono, possiamo considerare i punti successivi, fino alla prossima intersezione, come interni. Tali gruppi di punti sono chiamati span, e rappresentano i pixel da colorare all'interno dell'immagine.<br />

<br />

I passi del processo per determinare gli span sono tre:<br />

[[File:Scan-line algorithm.svg|miniatura|destra|Esempio di Algoritmo scan-line]]

'''Scan Line''' è un [[algoritmo]] per illa filling[[rasterizzazione]] efficenteefficiente di poligoni.<br />

Dato un [[poligono]], espresso sotto forma di segmenti (x_min,y_min,x<nowiki>_max</nowiki>,Y_max) , è possibile determinare i punti interni del poligono tracciando delle linee parallele all'asse x e calcolando le intersezioni con i segmenti del poligono. Ogni volta che una linea di scansione interseca un segmento del poligono, possiamo considerare i punti successivi, fino alla prossima intersezione, come interni. Tali gruppi di punti sono chiamati span, e rappresentano i [[pixel]] da colorare all'interno dell'immagine.<br />

I passi del processo per determinare gli span sono tre:<br />

# Determinare le intersezioni tra la scan-line e i poligoni

# Ordinare tali intersezioni secondo l'asse x

# Determinare i punti interni sfruttando le intersezioni sulla linea calcolate precedentemente

<br />

== L'Algoritmoalgoritmo ==

Prima di iniziare, dobbiamo creare una tabella per salvare i punti di intersezione tra i segmenti del poligono. Tale tabella è chiamata ET (Edge Table), è formata da (y_max - y_min) righe e contiene, ad ogni riga, una lista di segmenti che hanno come y_min il valore y della scan-line. Un segmento all'interno della lista è rappresentato con la coordinata y_max del segmento (l'estremo con y più grande), la coordinata x_min del segmento e l'inverso della pendenza.<br />

<br>

Prima di iniziare, dobbiamo creare una tabella per salvare i punti di intersezione tra i segmenti del poligono. Tale tabella è chiamata ET (Edge Table), è formata da (y_max - y_min) righe e contiene, ad ogni riga, una lista di segmenti che hanno come y_min il valore y della scan-line. Un segmento all'interno della lista è rappresentato con la coordinata y_max del segmento (l'estremo con y più grande), la coordinata x_min del segmento e l'inverso della pendenza.<br />

<br />

Ora siamo pronti a determinare gli span per ogni scan-line: Si inizializza un'altra lista vuota, chiamata AET (Active Edge Table) per rappresentare gli spigoli attivi ad ogni scan-line.

<br />

Partendo dalla prima riga della lista ET, si aggiunge alla AET tale riga, calcolando gli span tramite la regola even-odd. La regola consiste in suddividere i punti della scan-line in interni ed esterni: all'inizio i punti sono esterni e, ad ogni intersezione con i lati del poligono, cambiano in interni (o viceversa, cambiando da interni a esterni). Non vanno considerati nella regola i lati parallele alla scan-line, ne il vertice più piccolo o più grande del poligono rispetto alla coordinata y<br />

Partendo dalla prima riga della lista ET, si aggiunge alla AET tale riga, calcolando gli span tramite la regola even-odd. La regola consiste in suddividere i punti della scan-line in interni ed esterni: all'inizio i punti sono esterni e, ad ogni intersezione con i lati del poligono, cambiano in interni (o viceversa, cambiando da interni a esterni). Non vanno considerati nella regola i lati parallele alla scan-line, ne il vertice più piccolo o più grande del poligono rispetto alla coordinata y<br />.

Successivamente si aggiorna la tabella AET sommando l'inverso della pendenza alla coordinata x del segmento, per ottenere la giusta posizione x per la scan-line successiva.<br />

Una nota la merita la scelta dell'arrotondamento dei punti da considerare come interni: nella AET i punti x, ottenuti come somma di x_min con l'inverso della pendenza, non assumeranno valori interi. Per applicare la regola even-odd, dunque, è necessario arrotondare i punti x delle intersezioni della scan-line con i segmenti del poligono. In particolare, se si passa da punti interni ad esterni, si arrotonda la coordinata x del punto all'intero più grande, mentre se si passa da punti interni a punti esterni, si arrotonda all'intero più piccolo<br />.

La colorazione prosegue finchèfinché ET è vuota

==Collegamenti esterni==

<ref>*{{cita web|url=http://medialab.di.unipi.it/web/IUM/Fondamenti/cap4.htm</ref>|titolo=}}

{{Portale|matematica}}

[[Categoria:Computer grafica]]

La colorazione prosegue finchè ET è vuota

[[Categoria:Algoritmi geometrici|Scan line]]

<br />

==Bibliografia==

<ref>http://medialab.di.unipi.it/web/IUM/Fondamenti/cap4.htm</ref>