-

[GUIDA] Generazione di Frattali: l'insieme di Mandelbrot

511
303
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#1
Frattali: insieme di Mandelbrot

Questa volta voglio parlare di qualcosa di insolito rispetto al mio target. Anni fa scrissi un piccolissimo generatore di frattali, che pubblicai più avanti su Github, appartenendi all'insieme di Mandelbrot. Nulla di particolarmente avanzato e senza l'utilizzo di tecniche particolari di colorazione, sia chiaro; circa 1 mese fa ho aggiunto il supporto al multithreading.
Ho deciso di scrivere un brevissimo articolo solo per incuriosire chi magari non programma da molto tempo e non conosce i frattali. Spero anche di suscitare l'interese dei i più navigati, ovviamente!

Si trattava di una partecipazione ad un topic su un forum quella che mi fece scrivere queste due righe, quindi decisi come altri di avere poche dipendenze. Le immagini vengono generate in PPM; quelle che vedete nell'articolo sono quindi state tutte convertite.



L'articolo avrà il seguente svolgimento:
  • Immagini PPM: cosa sono?
  • Insieme di Mandelbrot
  • Operazioni sui numeri complessi
  • Generare Frattali
  • Ottimizzazioni: multithreading
  • Color Palette


Immagini PPM: cosa sono?
Portable pixmap format, conosciuto anche come PPM, è un formato di immagine definito nel progetto Netpbm: allo stesso progetto appartengono PGM e PBM rispettivamente immagini in scala di grigi e in bianco e nero. PPM invece permette di rappresentare immagini a colori (0-255) in formato RGB. Sono molto semplici da gestire e possono essere in ASCII o binarie.

Codice:
P6
# commento
w h
255
quello riportato qui sopra è l'header di un'immagine PPM rappresentata in binario (P6) larga w pixel e alta h pixel; ogni pixel dell'immagine ha una profondità di 24bit (8 * 3, dove 3 sono i canali di colore, RGB).

Il codice che si occupa della scrittura dell'header e dell'array di pixel è molto semplice:
C:
void save_image(char *imageName, char* pixels, size_t w, size_t h)
{  
  FILE *file = fopen(imageName, "wb");
  fprintf(file, "%s%d%s%d%s", "P6\n#DispatchCode PPMImageLib\n", w, " ", h, "\n255\n");
  fwrite(pixels, sizeof(char), 3+(w*h*3), file);
  
  fclose(file);
}
Insieme di Mandelbrot

Cos'è un frattale appartenente all'insieme di Mandelbrot?




Esprimibile con la successione:




che ci dice se il numero complesso c appartiene al set (l'insieme di Mandelbrot) quando Zn tende all'infinito. Se appartiene al set viene tipicamente colorato di nero, altrimenti di bianco. Al bianco ci sono alternative, e lo si può colorare anche in base al numero di iterazioni (nell'immagine qui sopra viene privilegiato il blu e la colorazione dipende dalle iterazioni).

Nella formula Z e C appartengono all'insieme dei numeri complessi: essi sono composti da due parti, una reale ed una immaginaria. In rete si trovano numerose risorse a riguardo (e spiegate certamente meglio di quanto potrei fare io), mi limito solo a dire che consentono ad esempio di dare un valore alle radici negative; infatti sqrt(-1) = i, vale a dire l'unità immaginaria, esprimibile anche come la coppia ordinata (0, 1i). In questo caso 0 è la componente reale, mentre 1i è la componente immaginaria del numero.

Ne segue che Z = a + ib. A questo punto occorre però limitare la serie se vogliamo scrivere un algoritmo; ecco che sempre la matematica ci viene in soccorso: fissato un numero N di iterazioni, possiamo dire che se il valore assoluto di Z è > di 2, allora non tornerà più inferiore a 2, ed il loop si può interrompere; in tal caso verrà applicato un colore in quanto c non apparterrà all'insieme.

Operazioni sui numeri complessi
Come detto nel paragrafo precedente, se abs(Zn) <= 2, allora C appartiene al set, e verrà quindi utilizzato il colore nero; diversamente verrà applicato un altro colore. Non sarà però sfuggito che le operazioni effettuate sono su numeri complessi e non su numeri reali.

La moltiplicazione tra due numeri complessi a e b avviene con questa formula:
C:
re = a.re * b.re - a.im * b.im;
im = a.re * b.im + a.im * b.re;
La somma tra due numeri complessi a e b, avviene in questo modo:
C:
re = a.re + b.re;
im = a.im + b.im;
Il valore assoluto di un numero invece lo si ottiene in questo modo (teorema di Pitagora):
C:
abs = sqrt(a.re * a.re + a.im * a.im)
a questo punto però possiamo evitare un calcolo dispendioso come la radice quadrata e confrontare abs(Z) non più con 2, bensì con 4.

Generare Frattali
Il frattale mostrato ad inizio articolo è stato generato dal codice qui sotto riportato.

Il cuore dell'algoritmo si compone di poco codice:
C:
void *calc(_square_coords *coords)
{
    for(int i = coords->start_y; i < coords->end_y; i++)
    {
        double scaled_y = Y1 + (((double)i * DIFF_Y) / (double)coords->h);
        for(int j = coords->start_x; j<coords->end_x; j++)
        {
            double scaled_x = X1 + (((double)j * DIFF_X) / (double)coords->w);

            complex z, c;
            z.re = scaled_x;
            z.im = scaled_y;

            c.re = scaled_x;
            c.im = scaled_y;

            int k;
            double abs=0.0;
            for(k = 0; k < coords->max_iterations; k++)
            {
                z   = complex_sum(complex_mul(z, z), c);
                abs = complex_abs(z);

                if(abs > 4.0) {
                    break;
                }
            }

            int index = linear_index(j, i, coords->w);

            if(abs <= 4.0 )
            {
                pixels[index]   = 0;
                pixels[index+1] = 0;
                pixels[index+2] = 0;
            }
            else
            {
                int r =  k >> 2;
                int g =  k >> 1;
                int b =  k << 3;

                r = (r > 128) ? 128 : r;
                g = (g > 128) ? 128 : g;
                b = (b > 255) ? 255 : b;

                pixels[index    ] = r;
                pixels[index + 1] = g;
                pixels[index + 2] = b;

            }
        }
    }
}
C:
double scaled_y = Y1 + (((double)i * DIFF_Y) / (double)coords->h);
double scaled_x = X1 + (((double)j * DIFF_X) / (double)coords->w);
dopo aver ottenuto le coordinate "scalate", si procede con lo scoprire se C appartiene o no al set:

C:
complex z, c;
z.re = scaled_x;
z.im = scaled_y;

c.re = scaled_x;
c.im = scaled_y;

int k;
double abs=0.0;
for(k = 0; k < coords->max_iterations; k++)
{
    z   = complex_sum(complex_mul(z, z), c);
    abs = complex_abs(z);

    if(abs > 4.0) {
        break;
    }
}
In base al valore di abs sappiamo quindi se C appartiene o no al set. A questo punto si sceglie il colore:

C:
int index = linear_index(j, i, coords->w);

if(abs <= 4.0 )
{
    pixels[index]   = 0;
    pixels[index+1] = 0;
    pixels[index+2] = 0;
}
else
{
    int r =  k >> 2;
    int g =  k >> 1;
    int b =  k << 3;

    r = (r > 128) ? 128 : r;
    g = (g > 128) ? 128 : g;
    b = (b > 255) ? 255 : b;

    pixels[index    ] = r;
    pixels[index + 1] = g;
    pixels[index + 2] = b;

}
l'algoritmo in questo modo privilegia il colore blu sugli altri.

Tra le prime righe del file mandelbrot.c del mio piccolo progetto compaiono alcune direttive:

C:
#define   X0   (2.0)
#define   Y0   (1.7)
#define   X1   (-2.0)
#define   Y1   (-1.7)


#define   DIFF_Y (Y0-Y1)
#define   DIFF_X (X0-X1)
in questo modo si può scegliere su quale parte andare a "zoomare". Il precedente frattale è stato generato con i valori riportati sopra (ma ritoccando un pò i colori, privilegiando verde e blu, ulteriormente).

Una zona interessante è la "seahorse valley", e la si può osservare settando questi valori:
C:
#define   X0   (0.37)
#define   Y0   (0.21)
#define   X1   (0.40)
#define   Y1   (0.26)



Modificando i colori, privilegiando il verde invece del blu, e modificando anche il colore nero, si ottiene questo:




In una precedente versione un menu consentiva di impostare tutti i parametri; con l'ultimo aggiornamento ho apportato qualche modifica, e non ho ancora consentito una buona personalizzazione.

Ottimizzazioni: multithreading

Ciascun px di un frattale viene calcolato indipendentemente e questo rende piuttosto semplice suddividere l'immagine in parti più piccole e lasciare a più thread il compito di effettuare i calcoli.
Ho così implementato una funzione che consente di avere N quadranti, calcolando le coordinate di inizio e fine di ciascuno di essi.

Successivamente vengono avviati N thread; di default 4, ed il consiglio è di non superare i core fisici della macchina. Io ho un Notebook dotato di CPU Intel i7 6700HQ, con 4 core e 8 threads.

C:
void generation(mandelbrot_info mandelbrot, char *filename)
{
    pixels = (char*) calloc(3 + (mandelbrot.w * mandelbrot.h * 3), 8);

    pthread_t square[mandelbrot.n_quadrants];

    for(int i=0; i<mandelbrot.n_quadrants; i++)
        pthread_create(&square[i], NULL, (void*) calc, (void*)&mandelbrot.coords[i]);

    for(int i=0; i<mandelbrot.n_quadrants; i++)
        pthread_join(square[i], NULL);

    free(mandelbrot.coords);

    save_image(filename, pixels, mandelbrot.w, mandelbrot.h);
    free(pixels);
}
il punto di ingresso di ciascun thread è proprio la funzione calc() già analizzata in precedenza.

Con l'introduzione del multithreading i tempi di generazione si sono ridotti in modo considerevole:

1-thread 4-thread (x0, x1, y0, y1)
166.30s 57.37s (0.37, 0.40, 0.21, 0.16)
198.322s 111.56s (0.37, 0.40, 0.21, 0.26)
46.11s 21.60s (2.0, -2.0, 1.7, -1.7)


Color Palette

La colorazione mostrata nel paragrafo precedente è in realtà incompleta; ho omesso una parte di codice:

C:
#ifndef PALETTE
    int r =  k >> 2;
    int g =  k >> 1;
    int b =  k << 3;

    r = (r > 128) ? 128 : r;
    g = (g > 128) ? 128 : g;
    b = (b > 255) ? 255 : b;

    pixels[index    ] = r;
    pixels[index + 1] = g;
    pixels[index + 2] = b;
#else
    uint32_t color = palette[k % palette_size];

    pixels[index    ] = get_channel(color,16);
    pixels[index + 1] = get_channel(color,8);
    pixels[index + 2] = get_channel(color,0);
#endif
E' possibile abilitare delle palette di colore; queste vengono caricate da un file di testo passato in input, composto semplicemente in questo modo:
Codice:
length
r,g,b
r,g,b
...
la lunghezza è relativa alle righe del file, i colori sono espressi in decimale. Al momento della lettura del file questi valori vengono memorizzati in un 32bit (che è l'array chiamato palette); al momento della lettura del colore vengono quindi ottenute le 3 componenti richiamando get_channel().

Un esempio pratico può essere questo:
Codice:
16
66,30,15
25,7,26
9,1,47
4,4,73
0,7,100
12,44,138
24,82,177
57, 125,209
134,181,229
211,236,248
241,233,191
248,201,95
255,170,0
204,128,0
153,87,0
106,52,3
Si tratta dei colori che compongono l'immagine mostrata da Wikipedia. Decommentando la direttiva PALETTE in mandelbrot.h, si abilita questa funzionalità.
Il risultato è mostrato qui sotto:



Conclusione

Spero sia stato un viaggio breve ma interessante!
Il "progetto" lo trovate sul mio GitHub, sotto il nome di fraCtal.

Ovviamente qualora voleste scrivere una vostra versione in qualsiasi linguaggio e pubblicarla in questo topic, assieme magari a qualche immagine, sarebbe ben accetta. :)
 
3,339
948
Hardware Utente
CPU
AMD Ryzen 5 2600x - Intel i5 6400
Dissipatore
stock - Arctic Freezer 11LP
Scheda Madre
Asrock Fatal1ty 4K - Asus H110M
Hard Disk
Samsung 970evo - vari
RAM
16GB G.Skill TridentZ 3000 - 8GB CORSAIR Vengeance LPX 2400
Scheda Video
ATI Firepro V7900 2GB - Asus R9 280x 3Gb
Monitor
DELL 2419P 2K + Benq 19'' - Acer 24" FHD
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
#2
Bravo, hai risvegliato un vecchissimo argomento! Mi rendo conto solo ora che l'ultimo Mandelbrot che ho calcolato era in Turbo Pascal per una super VGA 800x600 256c probabilmente su un Pentium 60 o qualcosa di simile: pixel per pixel riempiva il video in alcune ore!

Devo proprio provare a vedere quanto ci mette il mio Ryzen!.. e colgo il suggerimento del multithread!!!

Inviato dal mio Nexus 5 utilizzando Tapatalk
 
Mi Piace: DispatchCode
511
303
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#3
Ciò che speravo di ottenere in effetti! :)

Avrai sicuro un bel guadagno in termini di tempo allora. In realtà visti i tempi non sarebbe male usare ad esempio Vulkan.
 

Andretti60

Utente Attivo
3,014
1,941
Hardware Utente
#4
Ottimo lavoro, bravo.

Bella l'idea di parallelizzare l'algoritmo in quattro quadranti usando 4 threads, comunque l'ottimizzazione dipendera' poi dal "peso" diverso di ogni quadrante, ovvio che non si ottimizzera' nulla se il lavoro piu' oneroso e' fatto in un quadrante solo. Una ulteriore ottimizzazione e' quella di non calcolare ogni volta il valore delle componenti RGB, bensi' di utilizzare una tavola di lookup lunga max_iterations (in genere il valore di 100 e' sufficiente) e calcolarla una volta sola. Ovvio poi che non occorra usare pthread_join, se si voglia tenere il programma responsivo (per esempio se si voglia creare una applicazione con user-interface).

E parlando di tavole di lookup, il bello delle immagini frattali e' che cambiano drammaticamente proprio cambiando tale tavola. Quindi e' molto meglio salvare il file in formato 8bits (invece che RGB) per poi caricare dinamicamente diverse tavole di lookup. Una tabella molto usata e' quella che crea una rampa unica per un colore e un dente di sega per un altro, tipo:
C:
uchar r[256], g[256], b[256];
int k;
int nr = 8; // numero dei denti di sega
int kmod = 255 / nr;

for(k = 0; k < 256; k++)
{
    g[k] = k;
    r[k] = (uchar)((double)(k % kmod) * 255.0 / kmod);
    b[k] = 0;
}
 
3,339
948
Hardware Utente
CPU
AMD Ryzen 5 2600x - Intel i5 6400
Dissipatore
stock - Arctic Freezer 11LP
Scheda Madre
Asrock Fatal1ty 4K - Asus H110M
Hard Disk
Samsung 970evo - vari
RAM
16GB G.Skill TridentZ 3000 - 8GB CORSAIR Vengeance LPX 2400
Scheda Video
ATI Firepro V7900 2GB - Asus R9 280x 3Gb
Monitor
DELL 2419P 2K + Benq 19'' - Acer 24" FHD
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
#5
Si, una bella idea i quadranti: come fanno i motori di render ray-trace (tipo vray, a differenza dei più potenti unbiased).. ora che ci penso è perché quando era venuta fuori la possibilità di calcolare un grafico di Mandelbrot con un personal computer non c'erano ancora CPU multicores! :) :) :)

Inviato dal mio Nexus 5 utilizzando Tapatalk
 
511
303
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#6
Ottimo lavoro, bravo.

Bella l'idea di parallelizzare l'algoritmo in quattro quadranti usando 4 threads, comunque l'ottimizzazione dipendera' poi dal "peso" diverso di ogni quadrante, ovvio che non si ottimizzera' nulla se il lavoro piu' oneroso e' fatto in un quadrante solo. Una ulteriore ottimizzazione e' quella di non calcolare ogni volta il valore delle componenti RGB, bensi' di utilizzare una tavola di lookup lunga max_iterations (in genere il valore di 100 e' sufficiente) e calcolarla una volta sola. Ovvio poi che non occorra usare pthread_join, se si voglia tenere il programma responsivo (per esempio se si voglia creare una applicazione con user-interface).

E parlando di tavole di lookup, il bello delle immagini frattali e' che cambiano drammaticamente proprio cambiando tale tavola. Quindi e' molto meglio salvare il file in formato 8bits (invece che RGB) per poi caricare dinamicamente diverse tavole di lookup. Una tabella molto usata e' quella che crea una rampa unica per un colore e un dente di sega per un altro, tipo:
C:
uchar r[256], g[256], b[256];
int k;
int nr = 8; // numero dei denti di sega
int kmod = 255 / nr;

for(k = 0; k < 256; k++)
{
    g[k] = k;
    r[k] = (uchar)((double)(k % kmod) * 255.0 / kmod);
    b[k] = 0;
}
Grazie!
Non avevo pensato ad una tabella costruita in quel modo. Ottimo spunto, appena mi sarà possibile magari apporto qualche modifica per includere colorazioni simili.

Si, una bella idea i quadranti: come fanno i motori di render ray-trace (tipo vray, a differenza dei più potenti unbiased).. ora che ci penso è perché quando era venuta fuori la possibilità di calcolare un grafico di Mandelbrot con un personal computer non c'erano ancora CPU multicores! :) :) :)

Inviato dal mio Nexus 5 utilizzando Tapatalk
In quegli anni in effetti si poteva sfruttare solo lo switch tra processi.
Ora invece sfruttiamo le GPU per questi calcoli, pensa come sono cambiate le cose...

A me l'idea è venuta non appena ho fatto caso al fatto che il calcolo dei px non era dipendente da alcun fattore, se non al limite la distanza o numero di interazioni (ed avendo messo mano anni fa alle immagini sapevo sarebbe stato semplice da implementare). Solo dopo ho saputo che anche Blender, quando usa solo la CPU, fa una cosa molto simile se non la stessa (ormai la GPU la fa da padrona però). :)
 
Mi Piace: Andretti60
#7
Grande thread... inteso sia che come discussione, che come processo di calcolo ;-D
Ho sempre avuto la passione per i frattali... da tempo immemorabile!

Pensa che avevo preso ad usare l'insieme di Mandelbrot come personalissimo "Hello World" per l'esplorazione delle nuove tecnologie grafiche e/o strutturali... come MMX, SSE... i primi multicore, anche con OpenMP... etc... e cosi' quando tempo addietro debbutto' WebGL, avevo fatto il solito programmino Mandelbrot (e Julia) che utilizza la GPU... e che risiede a questo link dal lontano 2012/2013:
https://www.michelemorrone.eu/WebGL/Julia/Julia.html
(non ho problemi a mettere online i sorgenti se qualcuno fosse interessato)

Intanto, per queto thread, visto che e' stato tirato fuori il discorso GPU, avevo pensato che potesse essere utile un "breve" esempio via OpenGL 4.5, utilizzando il completo parallelismo delle GPU.
L'ho volutamente scritto in C (non lasciatevi fuorviare dall'estensione .cpp) e nel modo piu' elementare possibile.
Ho evitato anche i vari check di errore per non perdere di vista il contenuto, ed anche i 2 shaders li ho integrati nell'unico file sorgente
(sebbene e' una cosa che odi avere gli shaders, come stringa, all'interno del sorgente).
Il tutto e' poco piu' di 200 righe di codice, compreso #ifdef per gli utenti OS X e OpenGL 4.1

Trovate tutto quanto sulla mia pagina github, con le direttive per la compilazione:
https://github.com/BrutPitt/glslMandel

Ho fatto sia la versione singola precisione Mandelf.cpp, sia la versione doppia precisione Mandeld.cpp.
Su alcune schede grafiche la differenza di prestazioni, fra float e double, e' notevole
C'e' anche una differenza di iterazioni (256 contro 512) per poter avere scene piu' definite, in profondita'... ma quello potete facilemnte variarlo da sorgente.

Come palette ho usato una semplice conversione HSLtoRGB realtime, (senza voler/dover creare una texture e passarla allo shader) in cui uso H come tonalita' del valore di uscita ciclo.

Unici controlli:
Tasto Sinistro -> Zoom In
Tasto Destro -> Zoom Out

Ho inserito anche una versione WebGL / WebAssembly visibile online, a questo indirizzo: glslMandel (per chi non vuole compilare)
Ovviamente il browser deve supportare WebGL 2 e WebAssembly ed attualmente solo FireFox e Chromium based (Chrome, Opera, Vivaldi, etc) supportano tali features.
Piccola annotazione: WebGL supporta solo i float, per cui, ben presto lo zoom perde di risoluzione
 

Andretti60

Utente Attivo
3,014
1,941
Hardware Utente
#8
In quegli anni in effetti si poteva sfruttare solo lo switch tra processi.
..
Che non aiutava nulla, anzi rendeva il processo più lento.
Il mio primo Mandelbrot lo scrissi per una Sun Workstation 2 monocromatica, in C, l'unica ottimizzazione che feci fu di fare creare il codice 68000 al compilatore, solo del "kernel" (ossia il loop che genera il valore di un punto date le sue coordinate) e poi ho ottimizzato quello. Altri tempi, adesso i compilatori sono molto più avanzati e furbi. Erano altri tempi anche per me, ero studente allora e a volte passavo la notte intera in laboratorio.
 
511
303
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
#9
Grande thread... inteso sia che come discussione, che come processo di calcolo ;-D
Ho sempre avuto la passione per i frattali... da tempo immemorabile!

Pensa che avevo preso ad usare l'insieme di Mandelbrot come personalissimo "Hello World" per l'esplorazione delle nuove tecnologie grafiche e/o strutturali... come MMX, SSE... i primi multicore, anche con OpenMP... etc... e cosi' quando tempo addietro debbutto' WebGL, avevo fatto il solito programmino Mandelbrot (e Julia) che utilizza la GPU... e che risiede a questo link dal lontano 2012/2013:
https://www.michelemorrone.eu/WebGL/Julia/Julia.html
(non ho problemi a mettere online i sorgenti se qualcuno fosse interessato)

Intanto, per queto thread, visto che e' stato tirato fuori il discorso GPU, avevo pensato che potesse essere utile un "breve" esempio via OpenGL 4.5, utilizzando il completo parallelismo delle GPU.
L'ho volutamente scritto in C (non lasciatevi fuorviare dall'estensione .cpp) e nel modo piu' elementare possibile.
Ho evitato anche i vari check di errore per non perdere di vista il contenuto, ed anche i 2 shaders li ho integrati nell'unico file sorgente
(sebbene e' una cosa che odi avere gli shaders, come stringa, all'interno del sorgente).
Il tutto e' poco piu' di 200 righe di codice, compreso #ifdef per gli utenti OS X e OpenGL 4.1

Trovate tutto quanto sulla mia pagina github, con le direttive per la compilazione:
https://github.com/BrutPitt/glslMandel

Ho fatto sia la versione singola precisione Mandelf.cpp, sia la versione doppia precisione Mandeld.cpp.
Su alcune schede grafiche la differenza di prestazioni, fra float e double, e' notevole
C'e' anche una differenza di iterazioni (256 contro 512) per poter avere scene piu' definite, in profondita'... ma quello potete facilemnte variarlo da sorgente.

Come palette ho usato una semplice conversione HSLtoRGB realtime, (senza voler/dover creare una texture e passarla allo shader) in cui uso H come tonalita' del valore di uscita ciclo.

Unici controlli:
Tasto Sinistro -> Zoom In
Tasto Destro -> Zoom Out

Ho inserito anche una versione WebGL / WebAssembly visibile online, a questo indirizzo: glslMandel (per chi non vuole compilare)
Ovviamente il browser deve supportare WebGL 2 e WebAssembly ed attualmente solo FireFox e Chromium based (Chrome, Opera, Vivaldi, etc) supportano tali features.
Piccola annotazione: WebGL supporta solo i float, per cui, ben presto lo zoom perde di risoluzione
Davvero notevole, molto interessante, specie il primo link.
In una precedente versione consentivo la scelta tra Mandelbrot/Julia, magari la reintrodurrò anche io.

Che non aiutava nulla, anzi rendeva il processo più lento.
Il mio primo Mandelbrot lo scrissi per una Sun Workstation 2 monocromatica, in C, l'unica ottimizzazione che feci fu di fare creare il codice 68000 al compilatore, solo del "kernel" (ossia il loop che genera il valore di un punto date le sue coordinate) e poi ho ottimizzato quello. Altri tempi, adesso i compilatori sono molto più avanzati e furbi. Erano altri tempi anche per me, ero studente allora e a volte passavo la notte intera in laboratorio.
Oh si, immagino la lentezza (ho avuto 1 solo pc con una CPU, il primo, con Windows 98).
Poi c'è da dire che già senza ottimizzazioni i compilatori attualmente fanno molto; se poi si usano flag come O2, il codice generato muta notevolmente.

Quanti anni hai Andretti, se posso chiedere?
 
Mi Piace: Andretti60
3,339
948
Hardware Utente
CPU
AMD Ryzen 5 2600x - Intel i5 6400
Dissipatore
stock - Arctic Freezer 11LP
Scheda Madre
Asrock Fatal1ty 4K - Asus H110M
Hard Disk
Samsung 970evo - vari
RAM
16GB G.Skill TridentZ 3000 - 8GB CORSAIR Vengeance LPX 2400
Scheda Video
ATI Firepro V7900 2GB - Asus R9 280x 3Gb
Monitor
DELL 2419P 2K + Benq 19'' - Acer 24" FHD
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
#10
Io mi riferivo al mio ultimo Mandelbrot... il primo deve essere stato con Amiga 500, parliamo della fine anni Ottanta e comunque pur sempre un 68000, non diverso dalla ws sun 2 di cinque sei anni prima.

D'altra parte prima non si potevano nemmeno implementare questi algoritmi.. anzi prima ancora neanche esistevano.
Lo studio dell'insieme di Mandelbrot è stato reso possibile dai calcolatori.

Inviato dal mio Nexus 5 utilizzando Tapatalk
 
Ultima modifica:
Mi Piace: Andretti60

Andretti60

Utente Attivo
3,014
1,941
Hardware Utente
#11
Io programmai il kernel di Mandelbrot e Julia sulle prime calcolatrici tascabili programmabili, una Texas Ti58 c e una HP (credo la 25C) e poi riportavo i grafici su carta. Dovrei averli ancora da qualche parte.
Adesso i frattali che vedo calcolare su un normale PC, anche tridimensionali, sono spettacolari.

PS io ho smesso di ottimizzare dopo l'introduzione delle architetture RISC, ormai i compilatori sono fantastici e programmare a mano in assembler non ne vale piu' la pena (a meno ovviamente che non sia per lavoro)
 
Mi Piace: DispatchCode
3,339
948
Hardware Utente
CPU
AMD Ryzen 5 2600x - Intel i5 6400
Dissipatore
stock - Arctic Freezer 11LP
Scheda Madre
Asrock Fatal1ty 4K - Asus H110M
Hard Disk
Samsung 970evo - vari
RAM
16GB G.Skill TridentZ 3000 - 8GB CORSAIR Vengeance LPX 2400
Scheda Video
ATI Firepro V7900 2GB - Asus R9 280x 3Gb
Monitor
DELL 2419P 2K + Benq 19'' - Acer 24" FHD
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
#12
Scusa, ma che senso ha senza la grafica e l'assegnazione dei colori? Dal punto di vista matematico si tratta di operazioni piuttosto semplici, l'effetto è dato dalla reiterazione del calcolo e dalla rappresentazione.

Inviato dal mio Nexus 5 utilizzando Tapatalk
 

Andretti60

Utente Attivo
3,014
1,941
Hardware Utente
#13
Scusa, ma che senso ha senza la grafica e l'assegnazione dei colori? Dal punto di vista matematico si tratta di operazioni piuttosto semplici, l'effetto è dato dalla reiterazione del calcolo e dalla rappresentazione.

Inviato dal mio Nexus 5 utilizzando Tapatalk
Semplice, definisci un "confine" ossia un specifico valore del valore dell'insieme (soglia). Per ogni pixel assegni il valore '1' se almeno due pixel adiacenti hanno un valore inferiore e uno superiore a quella soglia. Puoi anche definire un insieme di queste soglie. In pratica produci una rappresentazione "planimetrica" dell'insieme, con curve dello stesso livello (ossia simile alle cartine geografiche)

Una semplice infarinatura qui:
https://en.wikipedia.org/wiki/Contour_line
 
Mi Piace: DispatchCode
3,339
948
Hardware Utente
CPU
AMD Ryzen 5 2600x - Intel i5 6400
Dissipatore
stock - Arctic Freezer 11LP
Scheda Madre
Asrock Fatal1ty 4K - Asus H110M
Hard Disk
Samsung 970evo - vari
RAM
16GB G.Skill TridentZ 3000 - 8GB CORSAIR Vengeance LPX 2400
Scheda Video
ATI Firepro V7900 2GB - Asus R9 280x 3Gb
Monitor
DELL 2419P 2K + Benq 19'' - Acer 24" FHD
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
#14
Si. "Quelle" delle cartine geografiche.. si chiamano isoipse.
Stento ad immaginare quanto possano essere "affascinanti" o anche solo "interessanti". Inoltre, essendo un frattale, si ripeteranno sempre, per ogni valore di soglia.

Inviato dal mio Nexus 5 utilizzando Tapatalk
 
#15
Sun Workstation 2, TI 58c (quella con le "striscette" magnetiche, vero?), Amiga 500... vedo che abbiamo tutti, me compreso, esperienza da vendere (leggasi: una certa eta' :-D )

Semplice, definisci un "confine" ossia un specifico valore del valore dell'insieme (soglia). Per ogni pixel assegni il valore '1' se almeno due pixel adiacenti hanno un valore inferiore e uno superiore a quella soglia. Puoi anche definire un insieme di queste soglie. In pratica produci una rappresentazione "planimetrica" dell'insieme, con curve dello stesso livello (ossia simile alle cartine geografiche)
C'era Fractint che, tra i vari metodi usati per risparmiare tempo in elaborazioni, utilizzava proprio quello descritto da te:
Cercava i contorni di isovalori, e quando "chiudeva" un'area, la "riempiva" di colore... cosi' evitava di calcolare ogni singolo punto di quell'area.
E ricordo che era anche spettacolare vedere come veniva composta l'immagine

Un altro metodo che veniva usato per tracciare una "mappa" dei bordi significativi di un insieme e' l'IIM (Inverse Iteration Method)
Ossia, invece di calcolare il valore di fc(z) = z^2 + c, si calcola il suo inverso, ossia fc^-1 = sqrt(z-c).
Brevemente e in modo (anche troppo) elementare:
Mentre il metodo classico DE (Distance Estimatior) e' "repulsivo", infatti il "colore" lo diamo alla velocita' di fuga... l'altro e' "attrattivo", nel senso che dato un punto qualsiasi nello spazio C (complesso), l'equazione fc^-1 = sqrt(z-c) fara' si' che questo punto tendera' a raggiungere il "bordo"... sara' attratto da esso.
Cosi', mentre con il DE bisogna esplorare, punto per punto, una determinata area del piano, con l'IIM bastano molte meno iterazioni per dare un'idea (anche se molto meno dettagliata) del contorno (soprattutto in un'epoca in cui c'era poco "colore" e tanto bisogno di risparmiare calcoli).
Ci sarebbero da osservare un altro paio di cose riguardo questo metodo, ma temo di andar fuori tema.
Comunque visto che lo sto usando in un programma, per chi volesse approfondire, lo descrivo qui:
https://www.michelemorrone.eu/glchaosp/Hypercomplex.html
(in modo semplice, ma un po' meno elementare, anche se in e' inglese)
 
Ultima modifica:

Discussioni Simili


Entra

Guarda il video live di tomshardwareita su www.twitch.tv