Rumore simplex - Simplex noise

Il rumore simplex è un metodo per costruire una funzione di rumore n- dimensionale paragonabile al rumore Perlin ( rumore "classico") ma con meno artefatti direzionali e, in dimensioni maggiori, un sovraccarico computazionale inferiore. Ken Perlin ha progettato l'algoritmo nel 2001 per affrontare i limiti della sua classica funzione di rumore, specialmente nelle dimensioni superiori.

I vantaggi del rumore simplex rispetto al rumore Perlin:

Il rumore simplex ha una complessità computazionale inferiore e richiede meno moltiplicazioni.
Il rumore simplex scala a dimensioni maggiori (4D, 5D) con un costo di calcolo molto inferiore: la complessità è per le dimensioni invece del rumore classico. ${\ displaystyle O (n ^ {2})}$ ${\ displaystyle n}$ ${\ displaystyle O (n \, 2 ^ {n})}$
Il rumore simplex non ha artefatti direzionali evidenti (è visivamente isotropo ), sebbene il rumore generato per dimensioni diverse sia visivamente distinto (ad es. Il rumore 2D ha un aspetto diverso rispetto a sezioni 2D di rumore 3D e sembra sempre peggiore per dimensioni superiori).
Il rumore simplex ha un gradiente ben definito e continuo (quasi) ovunque che può essere calcolato abbastanza a buon mercato.
Il rumore simplex è facile da implementare nell'hardware.

Mentre il rumore classico interpola tra i gradienti in corrispondenza dei punti finali dell'ipergriglia circostante (cioè nord-est, nord-ovest, sud-est e sud-ovest in 2D), il rumore simplex divide lo spazio in semplici (cioè triangoli -dimensionali). Ciò riduce il numero di punti dati. Mentre un ipercubo nelle dimensioni ha angoli, un simplex nelle dimensioni ha solo angoli. I triangoli sono equilateri in 2D, ma nelle dimensioni superiori i semplici sono solo approssimativamente regolari. Ad esempio, la piastrellatura nel caso 3D della funzione è un orientamento del favo disenoide tetragonale . ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle 2 ^ {n}}$ ${\ displaystyle n}$ ${\ displaystyle n + 1}$

Il rumore simplex è utile per le applicazioni di grafica per computer, dove il rumore viene solitamente calcolato su 2, 3, 4 o possibilmente 5 dimensioni. Per dimensioni superiori, le n- sfere attorno agli n - angoli simplex non sono sufficientemente compatte, riducendo il supporto della funzione e rendendola nulla in grandi porzioni di spazio.

Dettaglio algoritmo

Il rumore simplex è più comunemente implementato come una funzione bidimensionale , tridimensionale o quadridimensionale , ma può essere definito per qualsiasi numero di dimensioni. Un'implementazione prevede in genere quattro passaggi: inclinazione delle coordinate, suddivisione simpliciale, selezione del gradiente e sommatoria del kernel.

Inclinazione delle coordinate

Una coordinata di input viene trasformata utilizzando la formula

{\ displaystyle x '= x + (x + y + \ cdots) \ cdot F,}

{\ displaystyle y '= y + (x + y + \ cdots) \ cdot F,}

{\ displaystyle \ cdots,}

dove

{\ displaystyle F = {\ frac {{\ sqrt {n + 1}} - 1} {n}}.}

Questo ha l'effetto di posizionare la coordinata su una A ^*
_n reticolo, che è essenzialmente la disposizione dei vertici di un nido d'ape ipercubico che è stato schiacciato lungo la sua diagonale principale fino a quando la distanza tra i punti (0, 0, ..., 0) e (1, 1, ..., 1) diventa uguale alla distanza tra i punti (0, 0, ..., 0) e (1, 0, ..., 0).

La coordinata risultante ( x ' , y ' , ...) viene quindi utilizzata per determinare in quale cella dell'ipercubo unitario inclinato si trova il punto di input, ( x _b ' = floor ( x ' ), y _b ' = floor ( y ' ), ...) e le sue coordinate interne ( x _i ' = x ' - x _b ' , y _i ' = y ' - y _b ' , ...).

Suddivisione simpliciale

Una volta determinato quanto sopra, i valori della coordinata interna ( x _i ' , y _i ' , ...) vengono ordinati in ordine decrescente, per determinare in quale Schläfli orthoscheme simplex inclinato si trova il punto. Quindi il simplesso risultante è composto da i vertici corrispondenti ad un attraversamento ordinato del bordo da (0, 0, ..., 0) a (1, 1, ..., 1), di cui ci sono n ! possibilità, ciascuna delle quali corrisponde a una singola permutazione della coordinata. In altre parole, inizia con la coordinata zero e successivamente aggiungi quelle che iniziano nel valore corrispondente al valore della coordinata interna più grande, terminando con il più piccolo.

Ad esempio, il punto (0.4, 0.5, 0.3) si troverebbe all'interno del simplex con i vertici (0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1) . Il y _i ' coordinare è il più grande, quindi viene aggiunto prima. È quindi seguito dalla coordinata x _i ' e infine z _i ' .

Selezione gradiente

Ogni vertice simplex viene aggiunto di nuovo alla coordinata di base dell'ipercubo inclinato e sottoposto a hash in una direzione del gradiente pseudo-casuale. L'hash può essere implementato in numerosi modi, sebbene il più delle volte utilizzi una tabella di permutazione o uno schema di manipolazione dei bit.

È necessario prestare attenzione nella selezione del set di gradienti da includere, al fine di mantenere al minimo gli artefatti direzionali.

Somma del kernel

Il contributo di ciascuno degli n + 1 vertici del simplex è preso in considerazione da una somma di kernel radialmente simmetrici centrati attorno a ciascun vertice. Innanzitutto, la coordinata non allineata di ciascuno dei vertici viene determinata utilizzando la formula inversa

{\ Displaystyle x = x '- (x' + y '+ \ cdots) \ cdot G,}

{\ Displaystyle y = y '- (x' + y '+ \ cdots) \ cdot G,}

{\ displaystyle \ cdots,}

dove

{\ displaystyle G = {\ frac {1-1 / {\ sqrt {n + 1}}} {n}}.}

Questo punto viene sottratto dalla coordinata di input per ottenere il vettore di spostamento non allineato. Questo vettore di spostamento non sbilanciato viene utilizzato per due scopi:

Per calcolare il valore del gradiente estrapolato utilizzando un prodotto scalare .
Per determinare d ² , la distanza al quadrato dal punto.

Da lì, il contributo del kernel sommato di ogni vertice viene determinato utilizzando l'equazione

{\ displaystyle {\ big (} \ max (0, r ^ {2} -d ^ {2}) {\ big)} ^ {4} \ cdot {\ big (} \ langle \ Delta x, \ Delta y , \ dots \ rangle \ cdot \ langle \ operatorname {grad} x, \ operatorname {grad} y, \ dots \ rangle {\ big)},}

dove r ² è normalmente impostato su 0,5 o 0,6: il valore 0,5 garantisce l'assenza di discontinuità, mentre 0,6 può aumentare la qualità visiva nelle applicazioni per le quali le discontinuità non sono evidenti; 0.6 è stato utilizzato nell'implementazione di riferimento originale di Ken Perlin.

Status giuridico

Gli usi delle implementazioni in 3D e superiori per la sintesi di immagini testurizzate sono coperti dal brevetto US 6,867,776 , se l'algoritmo è implementato utilizzando le tecniche specifiche descritte in una qualsiasi delle rivendicazioni di brevetto. Il brevetto dovrebbe scadere l'8 gennaio 2022.

Guarda anche

Riferimenti

^ Ken Perlin, hardware Noise. In Real-Time Shading Note del corso SIGGRAPH (2001), Olano M., (a cura di). (PDF)
^ Ken Perlin, Making noise. Basato su un discorso presentato al GDCHardcore (9 dicembre 1999). (url)
^ "elaborazione dell'immagine - Perché l'aumento della dimensione del rumore simplex lo sbiadisce?" . Scambio di stack di computer grafica . Estratto 2021-03-10 .

link esterno

[1] Ken Perlin, hardware Noise. In Real-Time Shading Note del corso SIGGRAPH (2001), Olano M., (a cura di). (PDF)

[2] Ken Perlin, Making noise. Basato su un discorso presentato al GDCHardcore (9 dicembre 1999). (url)

[3] "elaborazione dell'immagine - Perché l'aumento della dimensione del rumore simplex lo sbiadisce?" . Scambio di stack di computer grafica . Estratto 2021-03-10 .

Languages

In other projects