Appunti completi corso Computer Grafica

Corso di computer graphics

Eccoci nel fighissimo corso di Computer Graphics in cui studieremo la grafica a basso livello (non a livello hardware ma comunque nei dettagli). Useremo WebGL che è quasi identico a OpenGL, ma è facile da installare. Sembrerebbe che OpenGL sia facile da compilare su Windows, difficile su Linux e impossibile sul Mac… Ora iniziamo con il vero contenuto del corso.

Come funziona uno schermo

Per prima cosa dobbiamo capire come funziona uno schermo, se no come possiamo fare grafica tridimensionale? Il graphic adapter è lo strumento che mostra immagini su uno schermo. Si dividono in tre categorie:

• Vector
• Rasted
• Accelerated

Gli adapter di tipo vector non vengono più utilizzati. Funzionano in modo simile agli oscilloscopi, ovvero inviano dei segnali per accendere il laser di un schermo a tubo catodico. Per esempio i primissimi videogiochi (come OXO citato all’inizio o il tennis) erano creati proprio così! Ma sono stati usati per molti decenni: anche le macchinette dei giochi arcade funzionano così. La programmazione ricorda molto il linguaggio LOGO: ci sono solo un comando per dire dove muoversi e uno per accendere o spegnere il laser. Un triangolo lo disegneresti così:

move 20,20
beam on
move 40,60
move 60,20
move 20,20
beam off

L’adapter genera tre segnali che controllano rispettivamente la posizione sull’asse x, la posizione sull’asse y e l’intensità del raggio.

Nel raster lo schermo diventa una matrice di pixel, ad ognuno dei quali puoi assegnare il colore che vuoi. L’adapter ha una sua memoria (VRAM) in cui ogni cella rappresenta un pixel sullo schermo. Un dispositivo apposito (il RAMDAC negli schermi analogici) ci pensa a trasformare la memoria in segnali che effettivamente generano un colore. Un programma per disegnare assegna ad ogni cella il colore che vuole mostrare, per esempio *(0x0040) = 0x21 assegna alla cella 0x0040 il colore 0x21. Questo metodo oggi non si usa più per il fatto che un tempo la memoria costava e l’adapter aveva spazio per mantenere un solo screenshot, ovvero la schermata corrente (ed era pure parecchio compressa). Adesso non ci sono problemi di memoria e l’adapter può tenere più screenshot: ogni programma infatti ha la sua finestra che puoi spostare come ti pare. Per questo si passa al prossimo tipo di adapter.

L’accelerated fa proprio quello che avevamo anticipato. Lo schermo vero e proprio è ancora rappresentato come un array di pixel, ma qui il programmatore NON va ad accedere ai singoli pixel e li assegna. Al contrario nella memoria inseriamo immagini intere e con dei comandi appositi le possiamo combinare. Infatti una schermata ha diversi componenti che si sovrappongono. Quindi si scrivono sulla memoria le immagini e si danno comandi per dire come comporle. Ora tutto funziona così, pure gli schermi dei sistemi embedded. L’unico problema di questo metodo è che, siccome non accedi direttamente alla memoria, utilizzi delle librerie e dei driver che, se non funzionano correttamente, mandano tutto a quel paese. Però quando funzionano permettono di fare tutto quello che vediamo: interfacce con finestre, GUI, effetti grafici, animazioni 3D...

Codifica dei colori

Ora vediamo come codificare i colori. Per rappresentare immagini 3D ciò che servono maggiormente sono proprio la geometria e i colori. Beh conosci bene l’RGB e quello è lo standard. Ma perché proprio quei colori? Innanzitutto noi vediamo solo la luce appartenente ad un certo range di frequenze e naturalmente vediamo gli oggetti di un certo colore perché li riflette. La retina degli occhi ha delle cellule sensibili ai colori che fungono da sensori. Ce ne sono di due tipi: uno sensibile alla luce, e altri tre che sono sensibili ciascuno ad una frequenza diversa. Queste frequenze corrispondono proprio ai colori dell’RGB, che di fatto nello spettro visibile sono il primo colore, l’ultimo e quello in mezzo. Quindi c’è una corrispondenza tra i colori digitali RGB e quelli che i nostri occhi vedono. Diciamo che l’RGB sfrutta l’idea inversa dei nostri occhi, ovvero “emette” luce usando come fonti primarie i colori rosso, verde e blu. Le unioni dei colori sono più insolite:

• Red + Blue = Magenta
• Green + Blue = Cyan
• Green + Red = Yellow
• Red + Green + Blue = White

Non è una cosa strana, perché qua sommi effettivamente le frequenze dei fotoni e quindi l’effetto è che per esempio sommando il verde e il rosso ottieni il giallo, che nello spettro sta nel mezzo. Tuttavia l’RGB può codificare solo una parte di tutti i colori percettibili dall’occhio umano. Quindi uno schermo NON può rappresentare esattamente quello che vedi nella realtà. Ci sono altre codifiche che cercano di coprire più colori.

Di conseguenza per generare i colori, controlliamo i segnali dei tre colori primari. Siccome i nostri colori sono digitali, i livelli dei colori RGB sono quantizzati. Si va da un valore minimo ad uno massimo e i singoli valori sono discreti. Quantizzare i colori rende ancora minore il numero di quelli rappresentabili.

Risoluzione e memoria

La risoluzione è il numero di pixel in orizzontale moltiplicato per i pixel in verticale. Attenzione che non è detto che i pixel siano quadrati: possono essere anche leggermente rettangolari. Un problemone sulle immagini è la quantità di memoria richiesta per memorizzare un’immagine. Prima di tutto serve sapere quanti bit codificano un singolo pixel: se un pixel è codificato da d bit, un’immagine occuperà h * w * d bit. Questo è un valore molto grande: un’immagine in HD a 24 bit occupa 1280*720*24 bit che sono quasi 3 MB. Un tempo era un valore improponibile, oggi non è un grande problema, però è comunque tanto.

Per questo è stato trovato un metodo interessante per ridurre la memoria utilizzata e questa tecnica si usa ancora oggi in alcuni formati (il GIF e alcuni PNG). Si chiama PALETTE e consiste nel ridurre il numero di colori presenti in un’immagine. Tanto l’occhio umano è più sensibile alla risoluzione, ma non a distinguere due colori molto simili. La palette è una lista di colori ammessi nell’immagine: ogni singolo colore è codificato per intero, ma dentro l’immagine i singoli pixel sono codificati solo usando l’indice della palette. Così se la palette contiene per esempio 32 colori, ogni pixel avrà un valore compreso tra 0 e 31, ovvero bastano 5 bit per codificarli. Se la palette contiene d colori e i colori sono codificati con p bit, allora un’immagine occuperà h * w * d + dp * 2 (c’è un po’ di confusione: d è il color depth, cioè i bit necessari per codificare un colore, 2 è il numero di colori codificabili presenti nella palette mentre p è il numero di bit per identificare un colore indipendentemente dal depth).

Color depth e palette

Il numero di bit che codificano un colore è detto COLOR DEPTH. La palette in genere è usata quando la color depth è minore o uguale a 8. Nel calcolo delle dimensioni la palette va inserita perché a volte il suo spazio occupato non è trascurabile rispetto all’immagine.

Grafica 2D

Iniziamo con la grafica 2D per capire quello che ci servirà nel 3D. Vedremo punti, linee e triangoli. I triangoli sono la base della grafica 3D: TUTTO è composto da triangoli. Il graphic adapter è ottimizzato per disegnare triangoli velocemente, quindi qualsiasi cosa vedi alla fine è un triangolo.

Per definire un punto servono due parametri: le coordinate e il colore. Le coordinate sono degli interi in cui il punto (0, 0) sta in alto a sinistra. La x cresce andando verso destra, mentre le y crescono andando verso il basso. Tutto quello che facciamo sarà in sostanza la trasformazione di coordinate. Il fatto che l’asse y vada al contrario rispetto al normale diagramma cartesiano, è dovuto semplicemente a motivi storici: i vecchi televisori a tubo catodico disegnavano l’immagine andando da sinistra a destra e dall’alto al basso, perché è come se scrivessi un libro. Tuttavia le formule matematiche funzionano esattamente come se stessi operando su un piano cartesiano tradizionale.

Quando vogliamo disegnare qualcosa, ci serve sapere le coordinate in cui piazzare l’oggetto. Tuttavia un oggetto potrebbe non starci nello schermo e dobbiamo decidere come comportarci se un pixel è creato fuori dalle dimensioni previste. Tagliare i pezzi che sono fuori dallo schermo visibile è detto CLIPPING. Non controllare il clipping equivale a scrivere fuori da un array in C. Quindi potresti sovrascrivere altre righe oppure scrivere su della memoria non valida e crasha tutto. Per fortuna il clipping è gestito in automatico dal driver del graphic adapter.

Il comando che disegna un punto è chiamato plot(). Com’è implementato? Dipende dall’hardware del graphic adapter. Una scheda grafica Nvidia e una AMD eseguirebbero questa funzione in modo diverso, per questo servono i driver che invece nascondono l’implementazione.

Ci sono un po’ di formule ora… come l’INTERPOLAZIONE LINEARE. Quando hai una funzione in due punti noti x₀ y₀ e x₁ y₁ la possiamo linearizzare in quell’intervallo con la formula y = y₀ + (x – x₀)*(y₁ – y₀)/(x₁ – x₀) con x != x₀. Nella grafica 3D l’interpolazione lineare è importantissima, quindi cerca di impararla a memoria e di non ricavarla ogni volta. Siccome la useremo spesso ci serviremo di questa notazione y = I(x₀, x, x₁, y₀, y₁).

Adesso abbiamo due punti e vogliamo disegnare una linea. Come si fa? Naturalmente ci servono le coordinate dei due punti x₀ y₀ e x₁ y₁ e poi diventa più difficile… Infatti esistono vari algoritmi per farlo. Quelli che vediamo noi sono l’INTERPOLATION e il BRESENHAM. È un problema complesso perché dobbiamo capire quanti e quali pixel dobbiamo colorare tra i due punti affinché il risultato sembri una linea. Affinché ciò avvenga i pixel intermedi devono “toccarsi” almeno per un vertice. Inoltre i pixel da scegliere dipendono anche dall’angolazione della linea. Se questo angolo è minore di 45 gradi, il numero minimo di pixel richiesto è dato dalla differenza delle x. Se è maggiore di 45, allora il numero minimo di pixel è dato dalla differenza lungo l’asse delle y. Per generalizzare, il minimo numero di pixel è dato da max(|x₁ - x₀|, |y₁ - y₀|) + 1.

Vediamo il metodo dell’interpolazione. Metti caso che l’angolo è inferiore a 45 gradi. Ci sarà un ciclo for che itera lungo l’asse x. Per ogni valore di x, calcoliamo la y usando la formula dell’interpolazione. La procedura fa uso della funzione round() per trovare l’intero più vicino di un valore in virgola mobile. Nel caso in cui l’angolo è maggiore di 45 gradi iteri sulla y, ma l’algoritmo è uguale. Inoltre il codice assume che x₀ < x₁ e y₀ < y₁: se questa cosa non è vera swappa i due valori. Il risultato sarà lo stesso.

if (abs(x1 - x0) >= abs(y1 - y0)) { // caso < 45 gradi
    if (x0 > x1) {
        swap(x0, y0, x1, y1);
    }
    y = y0;
    dy = (y1 - y0) / (x1 – x0);
    for (x = x0; x <= x1; x++) {
        plot(x, round(y), c);
        y += dy;
    }
} else { // caso > 45 gradi
    if (y0 > y1) {
        swap(x0, y0, x1, y1);
    }
    x = x0;
    dx = (x1 - x0) / (y1 – y0);
    for (y = y0; y <= y1; y++) {
        plot(round(x), y, c);
        x += dx;
    }
}

L’altro algoritmo, il Bresenham, fa uso di soli calcoli con numeri interi e non di floating point, che su hardware embedded possono essere problematici. Purtroppo questo algoritmo non prevede due casi come il precedente, ma ben otto… Praticamente dividi il cerchio in otto fette da 45 gradi e ognuna di queste è un caso particolare: iniziamo dal caso in cui l’angolo è compreso tra 0 e -45. Il punto iniziale sta in x₀ y₀ e il punto da raggiungere ha coordinate x₁ y₁. Il primo pixel starà senza dubbio in x₀ y₀ mentre il numero di pixel da disegnare sarà dato da x₁ – x₀ + 1 = N.

Il secondo pixel sarà o in x₀+1 y₀ oppure in x₀+1 y₀+1: quale coordinata scegliamo? Dei due pixel si calcola la distanza dal loro centro alla linea e si sceglie il pixel con la distanza minore. Come viene fatto questo calcolo? Stiamo ancora usando numeri in virgola mobile però… Piano piano arriveremo ai numeri interi. Interessante è il fatto che la distanza non viene calcolata da zero ogni volta, ma si calcola solo per il primo pixel e poi si fa dist = dist + dy se la y rimane costante, e dist = dist + dy – 1 se la y decresce di un pixel (almeno in questo caso sugli otto esistenti). Alla fine la y viene incrementata di un pixel se la distanza calcolata è maggiore di 0.5.

dy = (y1 – y0) / (x1 – x0);
dist = 0;
y = y0; // primo pixel disegnato direttamente
plot(x, y, c);
for (x = x0+1; x <= x1; x++) {
    dist += dy;
    if (dist > 0.5) { // se dist > 0.5
        y++; // allora incrementiamo di un pixel la y
        dist = dist – 1; // e aggiorniamo la distanza togliendoci un pixel
    }
    plot(x, y, c);
}

Qui stiamo ancora usando i valori floating point, ma si può facilmente passare ad una versione completamente intera. Il trucco usato è moltiplicare tutti i valori dy, dist e 0.5 per 2*(x₁ – x₀) e si ottiene:

dy = 2*(y1 – y0);
dx = x1 – x0;
idist = 0;
y = y0;
plot(x, y, c);
for (x = x0+1; x <= x1; x++) {
    idist += dy;
    if (idist > dx) {
        y++;
        idist -= 2 * dx;
    }
    plot(x, y, c);
}

Beh poi ti sbizzarrisci con le altre sette versioni. Guarda caso pure le slide sono sbagliate e le hanno corrette di anno in anno. FORSE quest’anno sono corrette. Per eseguire questo algoritmo devi farlo meccanicamente perché a memoria è facile sbagliare. Tutti i casi sono coperti dalle slide che dovrebbero essere libere all’esame.

Grafica bidimensionale e triangoli

Un’altra figura bidimensionale importante è il triangolo, infatti TUTTA la grafica 3D è fatta unicamente di triangoli. Tra l’altro i triangoli più facili da disegnare sono quelli che hanno un lato parallelo all’asse x. E qualsiasi altro triangolo si può spezzare in modo da formarne uno di questo tipo.

Un triangolo con un lato parallelo all’asse x è caratterizzato da cinque parametri:

• Le coordinate x_v y_v del vertice
• Il valore dell’ordinata della base y_B
• Le due coordinate delle ascisse della base x_Bl e x_Br

I due lati non paralleli all’asse x sono di fatti due linee. Per disegnare il triangolo quindi non devi fare altro che disegnare queste due linee. Questo si può fare tutto in un solo loop sfruttando la y che va da y_v a y_B (cioè dal vertice alla base parallela).

dxl = (xBl - xv) / (yB – yv);
dxr = (xBr - xv) / (yB – yv);
xl = xr = xv;
for (y = yv; y <= yB; y++) {
    for (x = round(xl); x <= round(xr); x++) {
        plot(x, y, c);
    }
    xl += dxl;
    xr += dxr;
}

Ora dobbiamo convertire un triangolo generico ad uno nella forma con il lato parallelo. Non ci vuole molto. Innanzitutto ordina i tre punti in modo crescente rispetto all’asse y e puoi capire chi dei tre punti è quello “in mezzo”. Bisogna ora trovare il punto corrispondente nel lato opposto al vertice. Beh si trova per interpolazione. Assumendo che i vertici abbiano coordinate x₁ y₁, x₂ y₂ e x₃ y₃ e il punto medio è x₂ y₂ dobbiamo calcolare un punto x_B y₂. Si trova applicando la formula x_B = I(y₁, y₂, y₃, x₁, x₃).

Coordinate normalizzate

Noi usiamo le coordinate via pixel, che però dipendono dall’hardware. Il software andrebbe a quel paese perché dovrebbe conoscere la risoluzione dello schermo e comportarsi di conseguenza. Ma è un macello perché un display può visualizzare diverse risoluzioni. Dobbiamo trovare un modo per indirizzare i pixel in modo indipendente dalla risoluzione, così l’applicazione può mostrare lo stesso contenuto al di là della risoluzione e delle proporzioni dello schermo (4:3 o 16:9). I driver lavorano con i pixel, mentre le applicazioni usano un altro set di coordinate chiamate NORMALIZZATE. Sono le stesse per tutti, al di là delle proporzioni, dimensioni e risoluzione degli schermi.

Nelle coordinate normalizzate usiamo un grafico cartesiano reale, in cui le y aumentano andando verso l’alto e non verso il basso. Poi tutte le coordinate non sono in pixel, ma sono un valore compreso tra -1 e 1 (o almeno in WebGL). Sarà poi l’hardware a convertire questi numeri in pixel a seconda della risoluzione dello schermo. La conversione da normalizzato n a pixel s si fa così:

x = (sw - 1) * (xn + 1) / 2
y = (sh - 1) * (1 - yn) / 2

Ripetiamo: le applicazioni usano questo sistema di indirizzamento. Sono i driver e le librerie a fare la conversione dipendente dall’hardware.

Introduzione alla grafica 3D

Oggi partiamo con la grafica 3D! Una grande lezione insomma! Per il 2D abbiamo visto due tipi di coordinate (quelle hardware e quelle normalizzate). Ora vogliamo fare il passaggio tridimensionale. Per definire un punto nel mondo tridimensionale dovrebbero servire tre parametri, ma in realtà ne usiamo quattro chiamati x, y, z, w. I primi tre sono le classiche coordinate cartesiane, il quarto parametro è una sorta di scala. Definisce l’unità di scala: una unità lungo x a cosa corrisponde? Dire 4 sulla x può essere metri, millimetri, pollici… Questo sistema è chiamato COORDINATE OMOGENEE. Un’importante conseguenza è che un punto può essere rappresentato da un insieme infinito di coordinate al variare di w. Se un punto ha w = 1 allora i tre parametri x, y, z corrispondono esattamente alla posizione del