Mandelbrot Set

Da quando ho sentito parlare dei frattali portati come esempio di programmazione “imbarazzantemente parallela”, la mia curiosità mi ha portato ad informarmi un po’ sui frattali, e nello specifico il “Mandelbrot set”. E ovviamente salta fuori che si tratta di una visualizzazione grafica realizzata a partire da una equazione matematica.

Wait, is it all math?
Always has been 🔫

Ma ancora una volta si scopre che, come tutte le cose matematiche, una volta che si supera il primo impatto, le cose sono in realtà piuttosto semplici: in poche parole, basta costruire un sistema di assi cartesiani in modo che le $x \in [-2.5, 1]$ e $y \in [-1, 1]$.
Successivamente, per ogni punto $(x, y)$, si considera un numero immaginario $z$ tale che $\mathfrak R = x$ e $\mathfrak I = y$.
Per definizione, appartengono al set di Mandelbrot tutti i punti $z \cdot n+1 = z_n^2 + x + iy$ per cui $|z \cdot n+1| \le 2$ $\forall n \ge 0$.

Sebbene possa sembrare un po’ complicato, in realtà il tutto si può tradurre in uno pseudo-codice molto semplice (preso pari pari da wikipedia)

for each pixel (Px, Py) on the screen do
    x0 := scaled x coordinate of pixel (scaled to lie in the Mandelbrot X scale (-2.5, 1))
    y0 := scaled y coordinate of pixel (scaled to lie in the Mandelbrot Y scale (-1, 1))
    x := 0.0
    y := 0.0
    iteration := 0
    max_iteration := 1000
    while (x*x + y*y ≤ 2*2 AND iteration < max_iteration) do
        xtemp := x*x - y*y + x0
        y := 2*x*y + y0
        x := xtemp
        iteration := iteration + 1

Apparterranno al Mandelbrot set tutti i punti per cui iteration == max_iteration, e si può usare proprio il valore finale di iteration per colorare ciascun punto.
Ci sono vari modi per ottenere un bell’effetto, e personalmente io ho scelto di andare per lo schema di colori HSV con:

• H = iteration (normalizzata su max_iteration)
• V = 1
• S = 1 se iteration < max_iteration, 0 altrimenti

Il risultato è questo:

Il fatto che il codice fosse piuttosto semplice mi ha portato a realizzare una piccola versione di prova in processing, che ho completato in poco tempo. Ovviamente era piuttosto limitato: non si poteva zoomare, la finestra era 1200x800 e ci stava qualche secondo a caricare.

Recentemente, però, abbiamo affrontato CUDA in GPGPU, e mi è venuta l’idea di riprendere quel piccolo esperimento, ma stavolta sfruttando il calcolo parallelo per migliorare le prestazioni.
Pensavo sarebbe stato sufficiente fare un semplicissimo porting del codice, ma mi sbagliavo! Intanto dovevo scegliere una libreria per gestire il lato grafico, e dopo qualche ricerca, ho deciso di scegliere SFML. Sono immediatamente finito in un rabbit-hole infinito, per cui ho dovuto affrontare tantissimi problemi di linking fra CUDA e SFML, il che mi ha portato via un sacco di tempo, ma mi ha insegnato un sacco di cose che conoscevo nella teoria e che mi sono trovato a dover mettere in pratica.

Alla fine la mia dedizione ha pagato, e sono riuscito a realizzare una soluzione in Visual Studio che soddisfi il requisito di essere migliore della precedente: in questa versione, infatti si può zoomare, ci si può muovere nelle quattro direzioni e ovviamente le prestazioni sono nettamente migliorate, nonostante ora la schermata sia ufficialmente in full HD (1920x1080).

Ecco il risultato su Github.