Noise Simplex

Simplex brus är en metod för att konstruera en n-dimensionell brusfunktion jämförbar med Perlin -brus ("klassiskt" brus), men med färre riktningsartefakter och, i högre dimensioner, mindre beräkningsoverhead. Ken Perlin utvecklade algoritmen 2001 för att ta itu med begränsningarna i hans klassiska brusfunktion, särskilt i högre dimensioner.

Fördelar med simplexbrus framför Perlin-brus:

Simplex brus har mindre beräkningskomplexitet och kräver färre multiplikationer.
Simplex brus skalar till högre dimensioner (4D, 5D) till mycket lägre beräkningskostnad: komplexitet för storlek istället för för klassiskt brus. $O(n^{2})$ $n$ $O(n2^{n})$
Enkelt brus har inga märkbara riktningsartefakter (visuellt isotropiska ), även om bruset som genereras för olika dimensioner är visuellt distinkt (till exempel har 2D-brus ett annat utseende än 3D-brusskivor och ser gradvis sämre ut för högre dimensioner).
Simplex brus har en väldefinierad och kontinuerlig gradient (nästan) överallt, vilket kan beräknas ganska billigt.
Simplex brus är lätt att implementera i hårdvara. Medan klassiskt brus interpolerar mellan gradienter vid de omgivande hypermesh-ändpunkterna (dvs nordost, nordväst, sydost och sydväst i 2D), delar simplexbrus upp rymden i förenklingar (d.v.s. -dimensionella trianglar). Detta minskar antalet datapunkter. Medan en hyperkub har vinklar i dimensioner, har en simplex endast vinklar i dimensioner. Liksidiga trianglar i 2D, men i högre dimensioner är förenklingarna endast ungefär regelbundna. Till exempel är plattsättningen i 3D-fallet för en funktion orienteringen av en tetragonal difenoid bikaka. Enkelt brus är användbart för datorgrafikapplikationer där bruset vanligtvis beräknas över 2, 3, 4 eller möjligen 5 dimensioner. För högre dimensioner är n -sfärerna runt n - simplex-hörnen inte tillräckligt tätt packade, vilket minskar stödet för funktionen och gör den null i stora delar av rymden. $n$ $n$ $2^{n}$ $n$ ${\displaystyle n+}1$

Algoritmdetaljer

Simplex brus implementeras vanligtvis som en två-, tre- eller fyrdimensionell funktion , men kan definieras för valfritt antal dimensioner. Implementeringen innefattar vanligtvis fyra steg: koordinatavvikelse, uppdelning i förenklingar, gradientval och kärnsummering.

Koordinatavvikelse

Inmatningskoordinaten konverteras med formeln

$x'=x+(x+y+\cdots )*F$

$y'=y+(x+y+\cdots )*F$

$\cdots$

var

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

Detta resulterar i att en koordinat placeras på ett A n * gitter, som i huvudsak är platsen för hörn av en hyperkubisk bikaka , komprimerad längs huvuddiagonalen till avståndet mellan punkterna, medan avståndet mellan punkterna är (0, 0, …, 0) och (1, 1, … , 1) blir lika med avståndet mellan punkterna (0, 0, …, 0) och (1, 0, …, 0). Den resulterande koordinaten (x', y', …) används sedan för att bestämma vilken snedställningscell i enhetens hyperkub inmatningspunkten är, (xb' =golv (x'), yb'= golv (y'), …) och dess inre koordinater (xi'= x'-xb', yi'= y'-yb', …).

Uppdelning i enkla

När ovanstående har bestämts, sorteras de interna koordinatvärdena (xi', yi', …) i fallande ordning för att bestämma i vilket skevt Schläfli ortoschema simplex punkten ligger. Då består den resulterande simplexen av hörn som motsvarar en ordnad korsning av kanter från (0, 0, …, 0) till (1, 1, …, 1), varav n! möjliga, som var och en motsvarar en permutation av koordinaten. Med andra ord, börja vid nollkoordinaten och lägg till enheter sekventiellt, börja med värdet som motsvarar det största värdet på den interna koordinaten och slutar med den minsta.

Till exempel kommer punkten (0,4, 0,5, 0,3) att ligga inuti simplexen med hörn (0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, en) . Yi'-koordinaten är den största, så den läggs till först. Sedan kommer koordinaten xi' och slutligen zi'.

Gradientval

Varje hörn av simplexen läggs tillbaka till baskoordinaten för den avböjda hyperkuben och hashas i riktning mot den pseudo-slumpmässiga gradienten. En hash kan implementeras på många sätt, även om det vanligaste är en permutationstabell eller ett bitmanipuleringsschema.

Försiktighet bör iakttas när du väljer vilken uppsättning gradienter som ska inkluderas för att minimera riktningsartefakter.

Summering av kärnor

Bidraget från var och en av de n+1 hörnen i simplexen tas med i beräkningen genom att summera de radiellt symmetriska kärnorna centrerade runt varje vertex. Först bestäms de icke avböjda koordinaterna för var och en av hörnen av den inversa formeln

${\displaystyle {\displaystyle x=x'-(x'+y'+...)*G))$

${\displaystyle {\displaystyle y=y'-(x'+y'+...)*G))$

var

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

Denna punkt subtraheras från ingångskoordinaten för att erhålla en förskjutningsvektor utan förskjutningar. Denna förspänningsvektor används för två syften:

För att beräkna det extrapolerade gradientvärdet med hjälp av punktprodukten
För att bestämma d 2 , kvadraten på avståndet till en punkt.

Följaktligen bestäms det totala bidraget från kärnan i varje vertex med hjälp av ekvationen

${\displaystyle (max(0,r^{2}-d^{2}))^{4}*(<\Delta x,\Delta y,...>\cdot <grad.x, grad.y,...>)}$

där r2 vanligtvis sätts till 0,5 eller 0,6. 0,5 garanterar ingen rivning, medan 0,6 kan förbättra den visuella kvaliteten i applikationer där rivningen inte märks. 0.6 användes i Ken Perlins ursprungliga referensimplementering.

Rättslig status

Användningen av 3D och högre implementeringar för texturerad bildsyntes täcks av US patent nr 6 867 776 om algoritmen implementeras med användning av de specifika tekniker som beskrivs i något av patentkraven.

Se även

isotropi

Länkar

Ken Perlin, Hårdvara för brus. I realtidsskuggning SIGGRAPH kursanteckningar (2001), Olano M., (Red.). (pdf)
Ken Perlin Baserat på ett föredrag som presenterades på GDCHardcore (9 december 1999). (url)
Kort teknisk artikel med källkod av Stefan Gustavson (PDF)
Animerad demonstration av Perlins "gummiark" simplexbrus
En annan implementering av Simplex Noise i C++ (SimplexNoise1234)