|
|
|
cignoni@iei.pi.cnr.it |
|
http://vcg.iei.pi.cnr.it/~cignoni |
|
|
|
|
|
|
|
Algoritmi raster 2D |
|
La scan-conversion di linee |
|
Algoritmo di Bresenham per segmenti |
|
Rasterizzazione di poligoni |
|
|
|
|
L’algoritmo di rasterizzazione di un segmento di
retta deve calcolare le coordinate dei pixel che giacciono sulla linea
ideale o che sono il più vicino possibile ad essa |
|
|
|
|
|
Vogliamo avere la sequenza di pixel che |
|
approssima al meglio il segmento |
|
e quindi |
|
sia il più in linea retta possibile |
|
|
|
|
Consideriamo un’approssimazione della retta
larga un pixel |
|
Per coefficienti angolari |m|£1 la rasterizzazione
conterrà un pixel per ogni colonna |
|
|
|
|
Consideriamo un’approssimazione della retta
larga un pixel |
|
Per coefficienti |m|>1 conterrà un pixel per ogni riga |
|
Noi considereremo solo il caso di m£1: gli algoritmi
sviluppati in questo caso possono essere facilmente estesi agli altri |
|
|
|
|
La funzione analitica che rappresenta la retta è |
|
|
|
|
Vogliamo rasterizzare il segmento che va dal
punto P0 di coordinate (x0,y0) al punto P1
di coordinate (x1,y1) |
|
Entrambi i punti hanno coordinate intere |
|
|
|
|
|
1. Partendo dal pixel con coordinata x minima x0: |
|
2.1 Incrementare x a passo 1 |
|
2.2 "xi calcolare yi come mxi
+ B |
|
2.3 Arrotondare quindi yi |
|
|
|
|
In questa maniera si seleziona sempre il pixel
che è più vicino alla linea ideale, quello cioè che ha distanza minima
dalla linea |
|
Per identificare ogni pixel si devono fare 3
operazioni: un’addizione, una moltiplicazione ed un arrotondamento |
|
|
|
|
Si può eliminare la moltiplicazione usando una
tecnica incrementale, che consiste nel calcolare un punto della retta sulla
base del punto precedente |
|
L’algoritmo che si ottiene prende il nome di algoritmo
DDA (digital differential analyzer) |
|
|
|
|
|
Questo vale per tutti i punti della linea: |
|
|
|
Ad ogni passo si deve fare una operazione di
arrotondamento e le variabili utilizzate (e quindi l’aritmetica) sono reali |
|
Usare aritmetica reale vuol dire introdurre
errori di arrotondamento |
|
|
|
|
|
Alla base dell’algoritmo di Bresenham (detto
anche algoritmo del punto di mezzo) c’è il tentativo di usare solo
operazioni in aritmetica intera |
|
|
|
|
|
|
Alla base dell’algoritmo di Bresenham c’è l’idea
di usare solo aritmetica intera |
|
L’ultimo pixel facente parte della nostra
rasterizzazione è il pixel P di coordinate (xp, yp) |
|
|
|
|
Il prossimo pixel della rasterizzazione sarà o
quello immediatamente a destra di P (E, per east pixel) o quello in alto a
destra (NE, per north-east pixel) |
|
|
|
|
Chiamiamo Q il punto in cui la linea da
convertire interseca la colonna x = xp + 1: sceglieremo come prossimo pixel quello, tra E e NE,
che minimizza la distanza da Q |
|
|
|
|
Detto M il punto di mezzo del segmento E-NE,
dobbiamo scegliere il punto che sta dalla stessa parte di Q rispetto ad M |
|
Dobbiamo quindi calcolare da che parte di M sta
Q |
|
|
|
|
Dobbiamo calcolare da che parte di M sta Q |
|
Come facciamo? |
|
Conviene utilizzare la forma implicita dell’equazione
della retta: |
|
|
|
|
|
Poiché |
|
m = dy/dx |
|
dx = x1 - x0 |
|
dy = y1 - y0 |
|
la forma esplicita si può riscrivere |
|
|
|
|
|
|
La funzione F: |
|
vale 0 per tutti i punti della retta |
|
assume valori positivi sotto la retta |
|
assume valori negativi sopra la retta |
|
E’ chiaro che F(Q)=0 |
|
|
|
|
A questo punto una maniera semplice per decidere
se scegliere E o NE, consiste nel calcolare |
|
|
|
e vederne il segno |
|
|
|
|
Poiché la nostra decisione si basa sul segno di
F(M), chiamiamo questa variabile variabile di decisione d |
|
Quindi |
|
|
|
|
d < 0 |
|
M sta sopra la retta |
|
Scegliamo E come prossimo pixel della
rasterizzazione |
|
|
|
|
d > 0 |
|
M sta sotto la retta |
|
Scegliamo NE come prossimo pixel della
rasterizzazione |
|
|
|
|
d = 0 |
|
M sta sulla retta (QºM) |
|
Scegliamo come prossimo pixel della
rasterizzazione uno qualsiasi dei due |
|
Diciamo che scegliamo E |
|
|
|
|
Se voglio che anche il valore di d sia costruito
in maniera incrementale mi devo chiedere qual è il prossimo M, e quindi
quanto vale d, al prossimo passo (sulla prossima colonna) sulla base della
scelta fatta a questo passo |
|
|
|
|
Se l’ultimo pixel selezionato è stato E |
|
|
|
|
Se l’ultimo pixel selezionato è stato E |
|
|
|
poiché |
|
|
|
|
Se l’ultimo pixel selezionato è stato E |
|
|
|
poiché |
|
|
|
sottraendo si ha |
|
|
|
|
L’incremento da aggiungere a d dopo aver scelto
E lo chiamiamo DE |
|
|
|
Questo è un risultato generico e vale per ogni
passo della rasterizzazione |
|
|
|
|
Se invece l’ultimo pixel selezionato è stato NE |
|
|
|
|
Se invece l’ultimo pixel selezionato è stato NE |
|
|
|
e |
|
|
|
|
Se invece l’ultimo pixel selezionato è stato NE |
|
|
|
e |
|
|
|
da cui |
|
|
|
|
|
Cosa abbiamo quindi costruito? |
|
Un algoritmo che |
|
ad ogni passo sceglie il prossimo pixel tra due
possibili candidati basandosi sul valore corrente di una variabile (detta
di decisione) |
|
ricalcola il valore della variabile di decisione
incrementalmente aggiungendo al suo valore corrente una quantità fissa
predefinita (DE o DNE) |
|
|
|
|
A questo punto ci serve solo un valore di
inizializzazione della variabile d |
|
Il valore iniziale è |
|
|
|
|
A questo punto ci serve solo un valore di
inizializzazione della variabile d |
|
Il valore iniziale è |
|
|
|
(x0, y0) appartiene alla
retta e F(x0, y0) = 0 |
|
|
|
|
|
|
Vogliamo un algoritmo generico capace di
rasterizzare poligoni di qualunque tipo: |
|
Convesso |
|
|
|
|
|
Vogliamo un algoritmo generico capace di
rasterizzare poligoni di qualunque tipo: |
|
Convesso |
|
Concavo |
|
|
|
|
|
Vogliamo un algoritmo generico capace di
rasterizzare poligoni di qualunque tipo: |
|
Convesso |
|
Concavo |
|
Intrecciato |
|
|
|
|
|
Vogliamo un algoritmo generico capace di
rasterizzare poligoni di qualunque tipo: |
|
Convesso |
|
Concavo |
|
Intrecciato |
|
Contorni multipli |
|
|
|
|
L’algoritmo che vedremo ha queste
caratteristiche |
|
Per ottenere questo risultato si ricavano una
dopo l’altra le span di pixel che stanno dentro il poligono |
|
I punti estremi delle span sono calcolati per
mezzo di un algoritmo incrementale, simile a quello visto per i segmenti |
|
|
|
|
|
L’algoritmo di filling consiste nella soluzione
di due problemi successivi: |
|
Rasterizzare i contorni del poligono |
|
Rasterizzare l’interno basandosi sulla
rasterizzazione dei contorni |
|
I due passi possono essere eseguiti anche non in
successione stretta |
|
|
|
|
La maniera più immediata di calcolare le
intersezioni è utilizzare l’algoritmo di scan-conversion delle linee su
ogni spigolo del poligono |
|
|
|
|
L’algoritmo che consideriamo lavora invece
incrementalmente sulle scan-line |
|
Una volta operato filling del poligono su una
scan-line (identificati i pixel della scan-line che appartengono al
poligono) adopera le informazioni trovate per aggiornare incrementalmente
le intersezioni e fare filling sulla scan-line successiva |
|
|
|
|
|
L’operazione di filling di una singola scan-line
si svolge in 3 passi: |
|
Trovare le intersezioni della scan-line con
tutti gli spigoli del poligono |
|
Ordinare le intersezioni sulla coordinata x |
|
Selezionare tutti i pixel, tra coppie di
intersezioni, che sono interni al poligono, usando per la determinazione di
quali pixel sono interni, la regola odd-parity |
|
|
|
|
Si attiva un bit detto di parità che può
assumere valore pari o dispari |
|
La parità è inizialmente pari, ogni intersezione
cambia il bit di parità, si disegnano i pixel quando la parità è dispari,
non si disegnano quando la parità è pari |
|
|
|
|
Prima di passare ad analizzare i problemi di
intersezione e sorting, vediamo come si definisce, in tutti i casi
particolari che possono sorgere, se un pixel è interno o meno al poligono |
|
I casi da prendere in considerazione sono 4 |
|
|
|
|
Data un’intersezione con un valore generico
della x razionale, come determino quale dei due pixel sui lati
dell’intersezione è quello cercato? |
|
|
|
Se stiamo incontrando un’intersezione provenendo
da dentro il poligono (il parity bit è dispari) arrotondiamo all’intero
minore per rimanere dentro |
|
Se siamo fuori dal poligono (il parity bit è
pari) arrotondiamo all’intero maggiore per entrare dentro |
|
|
|
|
Se stiamo incontrando un’intersezione provenendo
da dentro il poligono (il parity bit è dispari) arrotondiamo all’intero
minore per rimanere dentro |
|
|
|
|
Se stiamo incontrando un’intersezione provenendo
da dentro il poligono (il parity bit è dispari) arrotondiamo all’intero
minore per rimanere dentro |
|
Se siamo fuori dal poligono (il parity bit è
pari) arrotondiamo all’intero maggiore per entrare dentro |
|
|
|
|
Come tratto il caso speciale dell’intersezione a
coordinate intere? |
|
|
|
Per evitare conflitti di attribuzione di spigoli
condivisi, si definisce che un’intersezione a coordinate intere all’estremo
sinistro della span di pixel è interna al poligono, all’estremo destro è
esterna |
|
|
|
|
Per evitare conflitti di attribuzione di spigoli
condivisi, si definisce che un’intersezione a coordinate intere all’estremo
sinistro della span di pixel è interna al poligono, all’estremo destro è
esterna |
|
|
|
|
E se l’intersezione a coordinate intere riguarda
un vertice? |
|
|
|
Nel calcolo del parity bit, si considera solo il
vertice ymin e non il vertice ymax |
|
|
|
|
Nel calcolo del parity bit, si considera solo il
vertice ymin e non il vertice ymax |
|
Nella figura il vertice A è considerato solo
come vertice ymin dello spigolo FA e non come vertice ymax
dello spigolo AB |
|
|
|
|
Come si tratta il caso speciale di vertici che
definiscono uno spigolo orizzontale? |
|
Basta considerare i vertici di una linea
orizzontale come non influenti nel calcolo del parity bit e si ottiene
automaticamente che i lati orizzontali in basso vengano disegnati e quelli
in alto no |
|
|
|
|
Basta considerare i vertici di una linea
orizzontale come non influenti nel calcolo del parity bit e si ottiene
automaticamente che i lati orizzontali in basso vengano disegnati e quelli
in alto no |
|
|
|
|
Per calcolare le intersezioni vogliamo evitare
di fare un test che verifichi l’intersezione tra la scan-line ed ogni
spigolo del poligono |
|
Ci piacerebbe avere un metodo più furbo
(efficiente) |
|
|
|
|
Notando che molti spigoli che intersecano la
scan-line i intersecano anche la scan-line i+1, si può utilizzare un
approccio incrementale molto simile a quello dell’algoritmo di
scan-conversion per le linee |
|
Il valore dell’intersezione con la scan-line i
mi serve per calcolarla al passo i+1 |
|
|
|
|
La differenza tra questo algoritmo e quello di
rasterizzazione di segmenti consiste nel fatto che nel caso della
rasterizzazione di linee devo selezionare il pixel più vicino alla linea
ideale, mentre in questo caso devo tenere conto del dentro e del fuori e
arrotondare per restare dentro il poligono |
|
|
|
|
Conoscendo le intersezioni per una scan-line,
quando passo alla scan-line successiva le intersezioni si ricalcoleranno
con la formula |
|
|
|
|
|
Dove |
|
|
|
|
|
è il coefficiente angolare della
linea-spigolo |
|
|
|
|
Anziché utilizzare aritmetica reale per
calcolare gli incrementi 1/m considero l’incremento come numero razionale,
e uso il suo numeratore e il suo denominatore |
|
|
|
|
Linea-spigolo sinistra |
|
Coefficiente angolare m>1 |
|
xmin=3 |
|
m=5/2 |
|
|
|
|
La sequenza di valori della x sarà: |
|
|
|
|
|
|
Ad ogni iterazione quando la parte frazionaria
eccede 1 si incrementa x (la parte intera) di 1 e si sottrae 1 dalla parte
frazionaria muovendosi quindi di 1 pixel verso destra |
|
|
|
|
|
Le sequenze di valori delle variabili sono: |
|
increment x |
|
5 3 |
|
|
|
|
|
|
Le sequenze di valori delle variabili sono: |
|
increment x |
|
5 3 |
|
7®2 4 |
|
|
|
|
|
|
Le sequenze di valori delle variabili sono: |
|
increment x |
|
5 3 |
|
7®2 4 |
|
4 4 |
|
|
|
|
|
|
Le sequenze di valori delle variabili sono: |
|
increment x |
|
5 3 |
|
7®2 4 |
|
4 4 |
|
6®1 5 |
|
|
|
|
|
|
Le sequenze di valori delle variabili sono: |
|
increment x |
|
5 3 |
|
7®2 4 |
|
4 4 |
|
6®1 5 |
|
3 5 |
|
|
|
|
|
|
Le sequenze di valori delle variabili sono: |
|
increment x |
|
5 3 |
|
7®2 4 |
|
4 4 |
|
6®1 5 |
|
3 5 |
|
5 5 |
|
|
|
|
Il calcolo incrementale dei valori delle linee
spigolo non avviene in un’unica soluzione ma deve essere interrotto
salvando i valori calcolati al passo precedente |
|
|
|
|
|
Per far questo abbiamo necessità di una
struttura dati adeguata che consenta di: |
|
Trovare le intersezioni della scan-line con
tutti gli spigoli del poligono |
|
Ordinare le intersezioni sulla coordinata x |
|
Selezionare tutti i pixel, tra coppie di
intersezioni, che sono interni al poligono |
|
|
|
|
La struttura dati che utilizzeremo a questo
scopo sarà una lista che chiamiamo |
|
Active Edge Table (tabella degli spigoli
attivi) nella quale inseriamo le informazioni a partire da un’altra
struttura dati, la Edge Table (tabella degli spigoli) |
|
|
|
|
La Edge Table viene costruita all’inizio
dell’esecuzione dell’algoritmo e contiene tutte le informazioni necessarie
per la rasterizzazione degli spigoli |
|
E’ un array di liste, con tante celle per quante
sono le scan-line dello schermo |
|
|
|
|
|
Ogni elemento della lista contiene 4 campi |
|
ymax |
|
xmin |
|
1/m |
|
puntatore al prossimo |
|
|
|
|
|
|
Si inseriscono elementi solo se nella scan-line
c’è un punto di ymin |
|
|
|
|
|
|
|
|
|
La Active Edge Table viene costruita e
modificata copiando elementi della lista dalla Edge Table |
|
Inizialmente sarà vuota |
|
|
|
|
Non appena, scandendo la ET, si trova una cella
non vuota la AET viene inizializzata e la procedura di rasterizzazione ha
effettivo inizio |
|
|
|
|
Nella AET il secondo valore non rappresenta xmin
bensi’ il valore della x corrente da usare per la rasterizzazione |
|
|
|
|
|
|
Settare y al minimo y non vuoto della ET |
|
Inizializzare la AET (vuota) |
|
Ripetere, fino allo svuotamento di AET e ET: |
|
Muovere dal bucket di ET al corrispondente di
AET gli edge per cui ymin = y, quindi fare sorting su AET per x |
|
Disegnare i pixel della scan-line pescando
coppie di coordinate x dalla AET |
|
Rimuovere dalla AET gli edge per cui ymax = y
(quelli che non intersecano la prossima scan-line) |
|
Incrementare y di 1 |
|
Per ogni edge non verticale nella AET,
aggiornare x per il nuovo y |
|
|
|
|
|