Algoritmo scan line

Esempio di Algoritmo scan-line

Scan Line è un algoritmo per la rasterizzazione efficiente di poligoni.

Dato un poligono, espresso sotto forma di segmenti (x_min,y_min,x_max,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.

I passi del processo per determinare gli span sono tre:

1. Determinare le intersezioni tra la scan-line e i poligoni
2. Ordinare tali intersezioni secondo l'asse x
3. Determinare i punti interni sfruttando le intersezioni sulla linea calcolate precedentemente

L'algoritmo

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.

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.

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.

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.

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.

La colorazione prosegue finché ET è vuota

Collegamenti esterni

• medialab.di.unipi.it, http://medialab.di.unipi.it/web/IUM/Fondamenti/cap4.htm.