[C# / C++]Generazione procedurale

[TheEnigmist]

Salve a todos, da un po' di tempo ho il pallino di creare una mappa bella grande che sia la più naturale possibile partendo da una heightmap e poi implementarla come mesh o altro. Sto provando libnoise sia in C++ che una versione C#, ma non lo so, le immagini 2D che vengon fuori non sono ben dettagliate e impiego circa 6 secondi per una sola immagine 513x513 (c'è da dire che uso anche un 100aio di moduli). Per farvi un'esempio vi mostro 10 immagini generate con libnoise simulando una sorta di zoom stile google:
http://imgur.com/a/muRd3#0


Dove voglio arrivare? Tenete presente Outerra (http://www.outerra.com/wfeatures.html)?
Ora non voglio creare l'intero pianeta e duplicare il loro engine, però il livello di dettaglio del mondo è fighissimo, cioè la parte della generazione del territorio è quella che cerco. Veloce e "naturale" (con montagne, laghi, fiumi, strade, colline ecc).

Per quanto riguarda la velocità ho capito che il mio algoritmo di libnoise è eseguito dalla CPU, quindi devo solo capire come trasportare l'intero peso alla GPU e avrò una velocità molto maggiore.

Per la generazione di una heightmap decente invece non riesco proprio a venirne a capo. Ho provato a simulare questo:
http://libnoise.sourceforge.net/examples/complexplanet/index.html
E le immagini che avete visto sono frutto della trasposizione in C# di quell'algoritmo (6 secondi per ogni immagine 513x513, 2s se cambio dei moduli, ma il risultato cambia).

Le mie domande sono 2:
- Dove posso leggere e apprendere come fare i calcoli direttamente sulal GPU senza dare peso alla CPU?
- Per le tecniche di generazione procedural,e voi avete in mente algoritmi migliori in termini di tempo e risultato finale? Dove posso leggere e apprendere nuove tecniche che fanno al caso mio?

[Tommo]

EDIT: ok in realtà avevi già fatto tutto, non mi sono degnato di aprire l'immagine :asd:

comunque: ho scritto un Perlin Noise che genera mappe 512x512 come la tua in meno di 16 ms su iPhone 4 (in realtà genera un mondo infinito fatto di blocchi 512x512 man mano che sposti la telecamera), quindi prima di passare alla GPU fai funzionare la CPU :D

Io uso direttamente il Perlin Noise scritto da Perlin (http://mrl.nyu.edu/~perlin/noise/) senza passare per libnoise, proprio per tenere sotto controllo le performances.

[TheEnigmist]

EDIT: ok in realtà avevi già fatto tutto, non mi sono degnato di aprire l'immagine :asd:

comunque: ho scritto un Perlin Noise che genera mappe 512x512 come la tua in meno di 16 ms su iPhone 4 (in realtà genera un mondo infinito fatto di blocchi 512x512 man mano che sposti la telecamera), quindi prima di passare alla GPU fai funzionare la CPU :D

Io uso direttamente il Perlin Noise scritto da Perlin (http://mrl.nyu.edu/~perlin/noise/) senza passare per libnoise, proprio per tenere sotto controllo le performances.

Il problema è che libnoise permette di utilizzare i moduli di modifica per rendere più figo l'output. Comunque è vero, mi sa che il problema è sui 100 e passa moduli del libnoise. Mi sa che di solo Perlin non si riesce a generare un buon "mondo", oppure si?
Potresti postare una immagine creata dal tuo sistema? Giusto per farmi un'idea :)


Effettivamente andando alla ricerca del "migliore" algoritmo sono andato a finire in implementazioni troppo sporche e complesse che rallentano l'intero processo. Vediamo cosa posso tirar fuori dal Simplex Noise di Ken

[Tommo]

si, è piuttosto simile

https://dl.dropbox.com/u/4786082/linked%20somewhere/desert.png

è poco frastagliato di proposito, comunque mi pare usasse sulle 10 armoniche.

4 per continenti+isole+colline+roba,
2 per creare una "precipitation map" per decidere dove è secco, moderato o umido,
e 2 per la "temperature map" per il calore di ogni pixel.

incrociando le 3 mappe che genera piazzo foreste (con un'armonica di noise molto fitto per "spargere" gli alberi), deserti, tundra e scogli.
Le righe grige che vedi sono dirupi, e sono fatti elevando alla 5a il noise delle montagne.

Le spiagge poi le piazzo usando l'"elevazione continentale" ( i primi 2 noise) e non l'heightmap completa, perchè altrimenti compaiono spiaggette lontano dal mare :D

[TheEnigmist]

si, è piuttosto simile

https://dl.dropbox.com/u/4786082/linked%20somewhere/desert.png

è poco frastagliato di proposito, comunque mi pare usasse sulle 10 armoniche.

4 per continenti+isole+colline+roba,
2 per creare una "precipitation map" per decidere dove è secco, moderato o umido,
e 2 per la "temperature map" per il calore di ogni pixel.

incrociando le 3 mappe che genera piazzo foreste (con un'armonica di noise molto fitto per "spargere" gli alberi), deserti, tundra e scogli.
Le righe grige che vedi sono dirupi, e sono fatti elevando alla 5a il noise delle montagne.

Le spiagge poi le piazzo usando l'"elevazione continentale" ( i primi 2 noise) e non l'heightmap completa, perchè altrimenti compaiono spiaggette lontano dal mare :D


Uhm bene, a quanto pare usare il simplex noise è molto meglio xD
Quindi in totale crei 3 heightmap da 512x512 quindi per fare quel territorio ci metti più o meno 50ms (16ms*3). Beh un risultato perfetto oserei dire! Devo vedere se riesco a fare qualcosa di decente anche io :) Grazie delle risposte.

[Tommo]

Di niente :D

comunque non ne creo 3, ne creo finchè la cam si muove!
Si può sfruttare la località di perlin noise per creare mappe sempre uguali salvando solo il seed... la cosa funziona così:

-la telecamera determina il quad che contiene tutto il terreno che può vedere in coordinate delle caselle singole
-fa una query usando il quad verso una Chunk Cache, che chiede al Generatore tutti i Chunk che non sono nella cache
-il Generatore spawna un Generate Task che sarà eseguito da un thread nel Threadpool
-il thread usa l'algoritmo con Perlin per creare il Chunk, oppure se trova il file lo carica da disco (non proprio disco, è un filesystem virtuale tipo-VRAM, un'altra cache in pratica, che poi finisce su disco)
-nel frattempo ChunkCache restituisce una View, cioè un array di dimensioni fisse di puntatori a Chunk (da notare che alcune View potrebbero essere ancora "in flight" nei worker threads, quindi non si vedranno subito)

la faccenda della View serve perchè dato che devo cercare il Chunk ogni volta che devo accedere a una casella, e la Cache è una std::map, ogni accesso è O(logn) (ai tempi non avevo unordered_map). Con una View invece ho un array m x n e trovare il chunk sono un 5 istruzioni macchina :read:

C'è un sacco da ottimizzare, ma fai conto che tutta sta trafila poi mi girava fluida su iPod 4 :D
Aiuta anche molto generare tutto pixel-per-pixel senza tornare sui pixel del chunk più di una volta, riduce enormemente il cache trashing.