Algoritmo Cohen-Sutherland
L'algoritmo Cohen-Sutherland è un algoritmo di clipping per segmenti lineari che serve a determinare se un segmento, o parte di esso, deve essere visualizzato all'interno dell'area di clipping.
Ad esempio potremmo trovarci in una situazione come quella mostrata in figura 1.
In questa figura ci sono tre segmenti (1-2, 3-4, 5-6). Questi segmenti devono essere elaborati in modo differente, poiché il segmento 1-2 attraversa tutta l'area di clipping (quella color azzurro scuro) e deve essere "tagliato", mentre il segmento 3-4 al contrario si trova completamente all'interno, e deve quindi essere visualizzato per intero.
Procedimento
modificaLa prima fase di questo algoritmo prevede il calcolo dell'outcode, un codice di 4 bit, per ogni punto (x, y) estremo del segmento in considerazione (quindi per ogni segmento avremo due outcode).
Si immagini che le linee dei bordi dell'area di clipping si estendano all'infinito, come in figura 2.
Con questa "estensione" possiamo individuare 9 aree (A, B, C, D, E, F, G, H, I), a ognuna delle quali è associato un codice binario.
| 1001 | 1000 | 1010 |
| 0001 | 0000 | 0010 |
| 0101 | 0100 | 0110 |
Se il nostro punto (x, y) cade in una di queste aree, l'outcode sarà quello relativo alla sua area. Ad esempio, se il nostro punto appartiene all'area F, il suo outcode sarà 0010.
Il calcolo dell'outcode è piuttosto semplice: i primi due bit sono determinati da un confronto delle coordinate y, gli altri due da un confronto delle coordinate x.
Per i primi due bit, prendiamo in considerazione i bordi superiori e inferiori dell'area di clipping (Y min e Y max, ricordiamo che in grafica l'origine è in alto a sinistra e i valori dell'asse y aumentano scendendo), come in figura 3.
Se la nostra y è minore di Y min, allora il primo bit sarà posto a uno, altrimenti a zero. Se la nostra y è maggiore di Y max, allora il secondo bit sarà posto a uno, altrimenti a zero.
Stesso procedimento per gli ultimi due bit, determinati dalle coordinate x. In questo caso si prendono in considerazione i bordi sinistro e destro dell'area di clipping (X min e X max), mostrati in figura 4.
Se la nostra x è maggiore di X max, allora il terzo bit sarà posto a uno, altrimenti a zero. Se la nostra x è minore di X min, allora il quarto bit sarà posto a uno, altrimenti a zero.
Alla fine di questo procedimento, applicato a entrambi i punti estremi di un segmento, potremmo avere fondamentalmente quattro casi interessanti:
- entrambi gli outcode sono uguali a 0000: questo indica che il segmento si trova completamente all'interno dell'area di clipping (ne è un esempio il segmento 3-4 in figura 1).
- uno dei due outcode è uguale a 0000: vuol dire che un lato del segmento dovrà essere accorciato (segmento 5-6 in figura 1).
- gli outcode sono identici (è sufficiente confrontarli con un'operazione logica AND): vuol dire che il segmento rimane all'interno di una stessa area situata all'esterno dell'area di clipping. Il segmento verrà rifiutato.
- gli outcode sono diversi fra loro e nessuno è uguale a 0000: in questo caso bisogna determinare se il segmento interseca effettivamente l'area di clipping (ad esempio calcolando il punto di intersezione, calcolando il suo outcode e verificando che questo sia o meno 0000).
Altri progetti
modifica
Wikimedia Commons contiene immagini o altri file su algoritmo Cohen-Sutherland
