4.2 Implementazione degli algoritmi base
4.2.4 Riempimento poligoni
Per la libreria messa appunto, il passo fondamentale adesso sar`a di dare la possibilit`a di riempire le forme espresse tramite linee e curve, come ac- cennato nel capitolo 2 esistono infatti vari modi per fare questo: possiamo usare un algoritmo ricorsivo come la Flood Fill, ma `e alquanto inefficiente, come risultato `e molto limitato in quanto non pu`o riempire forme come il numero otto in una sola chiamata, avevamo accennato del Fill-rule e infine la ”Scan Conversion” che sar`a quello utilizzato nella maggior parte dei test effettuati. Ho esplorato l’implementazione anche di un altro metodo basato sulla bitmap, questo metodo segue il riempimento in base alla forma impressa nella sequenza di bit, ma visto che `e meno efficiente (in quanto ha bisogno di passare la bitmap con il disegno da riempire) si `e poi deciso di utilizzare la Scan Conversion come metodo di default.
4.3
MultiSampling (MSAA)
Il MultiSampling, si basa sulla stessa filosofia del SSAA, ma rispetto a quest’ultimo risulta molto meno costoso, perch´e effettua i calcoli solo ai bordi delle geometrie. Prima considerazione da fare per la fase implementativa del MSAA `e l’ordine di disegno, perch´e esso potrebbe influire negativamente
4.3 MultiSampling (MSAA) 39
Figura 4.3: MSAA 16x
sulla resa finale, ad esempio se il bordo di un poligono `e coperto da un altro, quando andiamo ad applicare il filtro sul disegno che sta dietro, dobbiamo ricordarci di tagliare il poligono per non applicare l’effetto dove non dovuto, oppure applicare il filtro subito dopo il disegno cos`ı da sovrascrivere le parti non visibili al nostro disegno successivo. Dato che applichiamo la stessa filosofia del SSAA ma solo ai bordi, avremo bisogno del poligono calcolato a risoluzione maggiore ma anche quello a dimensioni normali, una variabile (intera per semplicit`a) che indica la scalatura dalla geometria originale ed il colore del poligono da renderizzare.
Possiamo suddividere in pi`u fasi l’applicazione di questa tecnica:
4.3.1
Valori di input
In questa prima fase dato in input il poligono a risoluzione corrente ci ricaviamo quello a risoluzione maggiore. Abbiamo usato le curve di B´ezier cubiche, che dati i control point generano la curva con approssimazione al
40 4. Sperimentazione Numerica
Figura 4.4: Sulla sinistra troviamo una definizione di linee nel verso antiorario, e sulla destra nel verso orario
pixel, le linee generate dal nostro algoritmo di B´ezier devono essere ordinate, una propriet`a che ci viene comoda nelle fasi successive. Inoltre `e possibile applicare alla curva trasformazioni geometriche come traslazione, rotazione, scala ed `e grazie a queste propriet`a di cui gode che riusciamo facilmente a generare la nostra curva alla risoluzione maggiore, applicando la trasforma- zione di scala ai control point e chiamando da questo punto la creazione della curva.
4.3.2
Supporto al campionamento
Come seconda fase, creiamo il supporto per la fase di campionamento, quello di cui abbiamo bisogno `e un meccanismo che permetta di valutare se il punto campione che stiamo attuamente considerando sia dentro il poligono (a risoluzione maggiore) o sia all’esterno, cos`ı da permettere di determinare la media del colore finale a risoluzione normale. Per il supporto alla fase di campionamento possiamo optare per una triangolazione del poligono, abbia- mo scelto una via di mezzo dove triangoliamo solo i bordi del poligono e lo facciamo mantenedone l’ordine cos`ı da riuscire ad indicizzare approssimati- vamente la posizione di dove si trova il triangolo per valutare la copertura
4.3 MultiSampling (MSAA) 41
dei campioni.
4.3.3
Triangolazione bordi
Figura 4.5: Esempio di triangolazione dei bordi interni ed esterni In questa fase vogliamo, dato un poligono in formato di linee (Lines) ordinate, ricavarci una serie di triangoli che approssimano la parte piena del bordo. Il focalizzarci sul bordo permette prima di tutto di ridurre la complessit`a a quello che sar`a la vicinanza di essa, data la necessit`a di avere le linee ordinate ne sfruttiamo la propriet`a per ridurre le soluzioni a due tipi di inserimenti bordi , Destra o Sinistra, quello che stiamo andando a creare `e un triangolatore di bordi per il campionamento, i triangoli di cui abbiamo bisogno si trovano o al di fuori del poligono o all’interno; stabilendo adesso che un poligono definito in ”Counter Clock Wise” (CCW) sar`a pieno alla sua sinistra durante tutto il suo percorso, al contrario se `e espresso in senso orario ”Clock Wise” (CW) il triangolo sar`a a destra.
Per l’implementazione si `e deciso di valutare ogni linea guardando al- la linea successiva, di valutare se siamo in CCW o CW e se quindi stiamo riempendo a destra o sinistra. data la specularit`a dell’implementazione se definiamo un poligono CCW riempiamo a sinistra se combacia con quello set- tato da noi, altrimenti crea i triangoli del lato opposto. Come prima funzione
42 4. Sperimentazione Numerica
utile alla risposta se la prossima curva `e a destra o a sinistra, ci avvaliamo nel valutare l’angolo di direzione delle due linee prese in considerazione: A1 `e l’angolo della linea 1, A2 `e l’angolo di direzione della linea 2, il test si occupa principalmente di misurare le distanze.
boolean LEF T orRIGHT (angolo1(A1), anglolo2(A2))
Figura 4.6: Rappresentazione della funzione LEFTorRIGHT
La funzione LEFTorRIGHT prende in input l’angolo a cui punta la linea 1 e la 2 (A1, A2) e ritorna un valore booleano che indica se ci troviamo di fronte ad una linea verso sinistra o una linea verso destra.
4.3 MultiSampling (MSAA) 43
Generiamo come primo elemento il punto ad una distanza c con angolo A2 dall’origine (della seconda linea),
pA2x = c ∗ cos(A2) pA2y = c ∗ sin(A2)
qu`ı vogliamo trovare i punti intersecanti la circonferenza con la retta perpen- dicolare della linea 1 (retta passante per l’origine), a questo punto possiamo proseguire creando l’angolo che rappresenta la retta, per fare questo possia- mo aggiungere π/2 ( 90◦ ) per ricavare l’angolo verso sinistra , e -π/2 (90◦) verso destra.
nA = π/2
pLef tx = c ∗ cos(A2 + nA) pLef ty = c ∗ sin(A2 + nA)
pRightx = c ∗ cos(A2 − nA) pRighty = c ∗ sin(A2 − nA)
i due punti trovati dovranno essere valutati con pA2, chi avr`a distanza minore decider`a il risultato determinando se siamo di fronte ad una svolta a sinistra o a destra.
dR = distance(pRightx, pRighty, pA2x, pA2y) dL = distance(pLef tx, pLef ty, pA2x, pA2y)
Se dL < dR allora siamo in presenza di una direzione verso sinistra altrimenti se dR < dL allora siamo in presenza di una direzione verso destra.
La distanza tra due punti la calcoliamo semplicemente chiamando la funzione f loat distance(pt1, pt2)come segue:
x = |p1X − p2X| y = |p1Y − p2Y |
d =px2+ y2
Per l’angolo tra i due punti invece la funzione `e f loat angle(pt1, pt2) a = arctanpt2y − pt1y
44 4. Sperimentazione Numerica
se il risultato `e pt2x − pt1x < 0 al risultato aggiungiamo (180◦) a = a + π. La nostra funzione ha uno sviluppo speculare, che cambia in base a dove vogliamo riempire se `e a sinistra (+nA = P i/2) o a destra (−nA = P i/2), possiamo quindi dividere i cicli in maniera simmetrica, se siamo in una curva verso sinistra generiamo i triangoli a sinistra in una curva definita in CCW, a destra se CW, se siamo in una curva verso destra riempiamo a sinistra in CCW altrimenti a destra, come possiamo notare dal codice di esempio i vari casi saranno gestiti nei seguenti rami (*1,*2,*3,*4 sono i vari casi gestiti dal triangolatore).
Listing 4.1: Pseudo codice, ”Triangolatore bordi”
// s i a m o in d i r e z i o n e v e r s o s i n i s t r a if ( L E F T o r R I G H T ( A1 , A2 )== L e f t ) { if ( CCW ) { T r i a n g o l i a m o a s i n i s t r a } // *1 e l s e if (! CCW ) { T r i a n g o l i a m o a d e s t r a } // *2 } // s i a m o in d i r e z i o n e v e r s o d e s t r a e l s e if ( L E F T o r R I G H T ( A1 , A2 )== R i g h t ){ if ( CCW ) { T r i a n g o l i a m o a s i n i s t r a } // *3 e l s e if (! CCW ) { T r i a n g o l i a m o a d e s t r a } // *4 }
4.3.4
Riempimento a sinistra (*1)
Con v1, v2, v3, v4 le linee che fanno parte di quel pezzo l1(v1, v2) e l2(v3, v4) valutiamo il punto medio m1 = (v1 + v2) ∗ 0.5, e m2 = (v3 + v4) ∗ 0.5.
Creiamo la funzione che ritorna un punto del triangolo con spessore verso l’angolo di una normale positiva (sinistra) o negativa (destra) dal punto m1 e m2 con la nA1 = A1 + π/2 perch´e triangoliamo a sinistra:
4.3 MultiSampling (MSAA) 45
Non fa altro che ritornare il punto (x, y) traslato di uno spessore verso l’angolo (a).
resultX = pointX+(spessore∗cos(a)) resultY = pointY +(spessore∗sin(a))
Ci troviamo ad applicare uno spessore verso sinistra quindi chiameremo la funzione gen() nella normale positiva ,
g1 = gen(m1, spessore, A1 + nA) stessa cosa per la linea 2:
g2 = gen(m2, spessore, A2 + nA)
qui si creano due casi uno quando siamo in presenza di un angolo estre- mamente stretto (acuto) o un caso normale:
1. Riempimento a sinistra in curva a sinistra (angolo acuto)
Figura 4.7: Triangolazione dei bordi verso sinistra con riempimento a sinistra (angolo acuto)
Con un angolo acuto abbiamo meno triangoli ma dobbiamo triangolare con il punto medio (m3) tra g1 e g2 con particolare attenzione che alla prossima iterazione ricordiamo questo punto e non ne generiamo uno nuovo t1(v1, v2, m3).
46 4. Sperimentazione Numerica
2. Riempimento a sinistra in curva a sinistra (angolo normale)
Figura 4.8: Triangolazione dei bordi verso sinistra con riempimento a sinistra (angolo normale)
Con angolo non stretto creiamo due triangoli nella seguente aggregazione t1(v1, v2, g1), t2(v2, g2, g1).
4.3.5
Riempimento a destra (*2)
con v1, v2, v3, v4 le linee che fanno parte del pezzo l1(v1, v2) e l2(v3, v4) valutiamo il punto medio m1 = (v1 + v2) ∗ 0.5 , e m2 = (v3 + v4) ∗ 0.5 qui generiamo molti pi`u punti di spessore, 2 per ogni angolo, creiamo come sempre g1, g2 per`o con la −nA, ma ci calcoliamo anche g3 e g4 con angolo (A1 − nA) e (A2 − nA) dai rispettivi punti v2 e v3.
Anche qui si creano due casi uno con angolo stretto (acuto) e il caso normale:
1. Riempimento a destra in curva a sinistra (angolo stretto)
Nel caso con angolo acuto calcoliamo g5 e g6 chiamando la funzione gen(conv2, s, A1, ev3, s, A2) ci troveremo il punto medio (m4) e sar`a cos`ı triangolato t1(v1, v2, g1), t2(g1, g3, v2), t3(g3, m3, v2), t4(m3, g4, v3), t5(g4, g2, v3).
4.3 MultiSampling (MSAA) 47
Figura 4.9: Triangolazione dei bordi verso sinistra con riempimento a destra (angolo acuto)
2. Riempimento a destra in curva a sinistra (angolo normale)
Figura 4.10: Triangolazione dei bordi verso sinistra con riempimento a destra (angolo normale)
Nel caso in cui siamo in presenza di un angolo normale aggiungeremo i seguenti triangoli t1(v1, v2, g1), t2(g1, g3, v2), t3(g3, g4, v3), t4(g4, g2, v3).
I casi sono in poche parole applicabili in maniera opposta nella direzione verso destra(∗3 come ∗2, ∗4 come ∗1).
Ricordiamoci sempre di iniziare un p`o prima dell’inizio (iniziare dagli ultimo elemento) e di fermarsi un p`o dopo(finire sui primi elementi), con un
48 4. Sperimentazione Numerica
entrata a vuoto per configurare se siamo in presenza di angoli acuti o meno, successivamente il ciclo di connessioni ognuno guardando se stesso con il prossimo lato (se stesso con lato(i) con il prossimo lato(i + 1)), creando una striscia continua di triangoli che approssima i bordi interni o esterni da poter controllare quando siamo nella fase di campionamento.
4.3.6
Campionamento
Figura 4.11: Nella figura possiamo vedere l’applicazione dell’MSAA solo ai bordi, verificando la copertura dei punti campioni sulla serie di triangoli creati a risoluzione maggiore (di colore viola)
Nella fase di campionamento come abbiamo accennato in precedenza cir- cumnavigheremo tutto il bordo del poligono a risoluzione normale eseguendo i sotto-campionamenti con quello a risoluzione maggiore (come in figura 4.11), per questa fase ho scelto di utilizzare l’algoritmo di Bresenham modifican- do alcune sue parti, quando si rasterizza una linea verticale effettuiamo il
4.3 MultiSampling (MSAA) 49
campionamento non solo al pixel in questione ma anche agli adiacenti (x, y), (x + 1, y), (x − 1, y)
lo stesso vale per la rasterizzazione in orizzontale dove applichiamo i calcoli anche agli adiacenti
(x, y), (x, y + 1), (x, x − 1)
perch´e non sappiamo a priori su quale dei tre pixel avverr`a l’effettiva modi- fica.
La nostra implementazione prevede una scalatura per un valore x, valu- tando un numero di campioni (xx) che calcoliamo nel seguente modo, xx = x2
dove x > 1, quindi per x = 2 il nostro numero di campioni `e xx = 4 (4 sotto- campionamenti), per x = 3 allora xx = 9 (9 sotto-campionamenti), e via via procedendo. Per il posizionamento dei campioni, si dispone ogni sotto-
Figura 4.12: Punti campione per MSAA 4x
campione ruotato leggermente dal centro (media delle posizioni dei sotto- campioni), in seguito non facciamo altro che contare quanti sotto-campioni (sc) si trovano all’interno del poligono su un totale di sotto-campioni (tc).
Nell’esempio il poligono p1 copre due sotto-campioni su un totale di 4, allora come valore di campionamento avremo
campionamento = sc tc = 2 4 = 1 2
50 4. Sperimentazione Numerica
Figura 4.13: Esempio di copertura dei sotto-campioni (MSAA)
4.3.7
Bilanciamento colori
Infine possiamo applicare il valore calcolato dal campionamento nel colore della geometria, che verr`a usato per disegnare sul framebuffer, modifichiamo il canale alpha con il valore risultante dal campionamento cos`ı da applicare una trasparenza con il colore che si trova al di sotto. Per facilitare la compren- sione possiamo immaginare di avere un colore di sfondo (back) e uno della geometria (front), a questo punto possiamo decidere se applicare lo sfondo (back) alla geometria (front) o il contrario, nel primo caso il valore che andre- mo ad inserire nel canale alpha del componente back `e 1 − Campionamento, e nel secondo `e semplicemente il Campionamento (Campionamento `e un va- lore compreso da 0 a 1, ed indica la quantit`a della componente colore che comparir`a in quel determinato pixel).
4.3.8
Considerazioni finali
Il multisampling `e un evoluzione del supersampling, punta a calcolare so- lo le aree dove `e possibile trovare aliasing quindi ai bordi delle geometrie e ne fa un sottocampionamento, le tecniche descritte nei vari articoli sono per la maggior parte incentrati sul rendering in real time (grafica raster), quindi si `e deciso di seguire la tecnica del Multisampling ma di fare le valutazioni
4.3 MultiSampling (MSAA) 51
Figura 4.14: MSAA 16x
del campionamento su una geometria generata a risoluzione superiore (per semplicit`a il nostro campionamento sar`a sempre disposto come una griglia quadrata di sub-pixel) cos`ı da raggiungere una profondit`a di dettaglio mag- giore nella fase di campionamento (altrimenti la combinazione di colore del campionamento della geometria se fatto sulla stessa solamente scalata ma senza l’aggiunta di dettagli apparirebbe molto sagomata e non sfrutterebbe le potenzialit`a offerte da una grafica vettoriale).
52 4. Sperimentazione Numerica