Simplexní hluk - Simplex noise

Abstraktní kompozice ve 3D generovaná pomocí OpenSimplex hluk algoritmus generování.

Simplexní hluk je metoda pro konstrukci n-dimenzionální hluk funkce srovnatelná s Perlinův hluk („klasický“ šum), ale s menším počtem směrové artefakty a ve vyšších dimenzích nižší výpočetní režie. Ken Perlin navrhl algoritmus v roce 2001^[1] řešit omezení jeho klasické funkce šumu, zejména ve vyšších dimenzích.

Výhody simplexního šumu oproti šumu Perlin:

Simplexní šum má nižší výpočetní složitost a vyžaduje méně násobení.
Simplexní škálování šumu do vyšších dimenzí (4D, 5D) s mnohem menšími výpočetními náklady: složitost je ${displaystyle O (n ^ {2})}$ pro ${displaystyle n}$ rozměry místo ${displaystyle O (n, 2 ^ {n})}$ klasického hluku.^[2]
Simplexní šum nemá žádné znatelné směrové artefakty (je vizuálně izotropní ), i když šum generovaný pro různé dimenze je vizuálně odlišný (např. 2D šum má jiný vzhled než plátky 3D šumu a pro vyšší dimenze vypadá stále horší)^{[Citace je zapotřebí ]}).
Simplexní hluk má dobře definovaný a spojitý gradient (téměř) všude, kde lze vypočítat docela levně.
Simplexní šum je snadno implementovatelný v hardwaru.

Zatímco klasický šum interpoluje mezi přechody na okolních koncových bodech hypergridu (tj. na severovýchod, severozápad, jihovýchod a jihozápad ve 2D^{[Citace je zapotřebí ]}), simplexní hluk rozdělí prostor na jednoduchosti (tj., ${displaystyle n}$ -dimenzionální trojúhelníky). Tím se sníží počet datových bodů. Zatímco hyperkrychle v ${displaystyle n}$ rozměry má ${displaystyle 2 ^ {n}}$ rohy, jednostranný vstup ${displaystyle n}$ rozměry má pouze ${displaystyle n + 1}$ rohy. Trojúhelníky jsou rovnostranný ve 2D, ale ve vyšších dimenzích jsou jednoduchosti pouze přibližně pravidelné. Například obklady ve 3D případě funkce jsou orientací tetragonální disphenoid voštinový.

Simplexní šum je užitečný pro aplikace počítačové grafiky, kde se hluk obvykle počítá ve 2, 3, 4 nebo případně 5 rozměrech. U vyšších rozměrů n- koule kolem n-zjednodušené rohy nejsou dostatečně hustě zabalené, což snižuje podporu funkce a ve velkých částech prostoru ji činí nulovou.

Detail algoritmu

Simplexní šum je nejčastěji implementován jako dvou-, tří- nebo čtyřrozměrný funkce, ale lze jej definovat pro libovolný počet rozměrů. Implementace obvykle zahrnuje čtyři kroky: zkosení souřadnic, jednoduché dělení, výběr přechodu a součet jádra.

Zkosení souřadnic

Vstupní souřadnice se transformuje pomocí vzorce

{displaystyle x '= x + (x + y + cdots) * F}

{displaystyle y '= y + (x + y + cdots) * F}

{displaystyle ...}

kde

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

To má za následek umístění souřadnice na A.^*
_n mříž, což je v podstatě uspořádání vrcholů a hyperkubický plástev který byl zmáčknut podél své hlavní úhlopříčky, dokud se vzdálenost mezi body (0, 0, ..., 0) a (1, 1, ..., 1) nestane rovnou vzdálenosti mezi body (0, 0, ..., 0) a (1, 0, ..., 0).

Výsledná souřadnice (x ', y', ...) se poté použije k určení, ve které zkosené jednotce hyperkrychlové buňky leží vstupní bod, (xb '= floor (x'), yb '= floor (y') , ...) a jeho vnitřní souřadnice (xi '= x'-xb', yi '= y'-yb', ...).

Zjednodušené dělení

Jakmile je určeno výše, jsou hodnoty vnitřní souřadnice (xi ', yi', ...) seřazeny v sestupném pořadí, aby se určilo, které zkosené Schläfli orthoscheme simplex bod leží dovnitř. Výsledný simplex se potom skládá z vrcholů odpovídajících uspořádanému přechodu hran od (0, 0, ..., 0) do (1, 1, ..., 1), kterých je n! možnosti, z nichž každá odpovídá jedné permutaci souřadnice. Jinými slovy, začněte s nulovou souřadnicí a postupně přidávejte ty, které začínají v hodnotě odpovídající hodnotě největší vnitřní souřadnice a končí nejmenší.

Například bod (0,4; 0,5; 0,3) by ležel uvnitř simplexu s vrcholy (0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1) . Souřadnice yi 'je největší, takže se přidává jako první. Poté následuje souřadnice xi 'a nakonec zi'.

Výběr přechodu

Každý simplexní vrchol je přidán zpět do základní souřadnice zkosené hyperkrychle a hashován do pseudonáhodného směru přechodu. Hash lze implementovat mnoha způsoby, ačkoli nejčastěji používá permutační tabulku nebo schéma bitové manipulace.

Při výběru sady přechodů, které mají být zahrnuty, je třeba věnovat pozornost, aby se směrové artefakty udržovaly na minimu.

Souhrn jádra

Příspěvek z každého z n + 1 vrcholů simplexu je započítán do součtu radiálně symetrických jader soustředěných kolem každého vrcholu. Nejprve se pomocí inverzního vzorce určí nekontrolovaná souřadnice každého z vrcholů

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

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

{displaystyle ...}

kde

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

Tento bod se odečte od vstupní souřadnice, aby se získal neomezený vektor posunutí. Tento neomezený vektor posunutí se používá pro dva účely:

Chcete-li vypočítat extrapolovanou hodnotu přechodu pomocí a Tečkovaný produkt
K určení d², čtvercová vzdálenost k bodu.

Odtud se pomocí rovnice určí souhrnný příspěvek jádra každého vrcholu

{displaystyle (max (0, r ^ {2} -d ^ {2})) ^ {4} * ( cdot )}

kde r² je obvykle nastavena na 0,5 nebo 0,6. 0.5 zajišťuje žádné diskontinuity, zatímco 0.6 může zvýšit vizuální kvalitu v aplikacích, u kterých diskontinuity nejsou patrné. V původní referenční implementaci Kena Perlina byla použita 0,6.

Právní status

Použití implementací v 3D a vyšší pro syntéza texturovaného obrazu jsou pokryty US patent 6 867 776 , pokud je algoritmus implementován pomocí specifických technik popsaných v kterémkoli z patentových nároků.

Viz také

Reference

^ Ken Perlin, Noise hardware. In Real-Time Shading SIGGRAPH Course Notes (2001), Olano M., (Ed.). (pdf)
^ Ken Perlin, Dělám hluk. Na základě přednášky prezentované na GDCHardcore (9. prosince 1999). (url)

externí odkazy

[1] Ken Perlin, Noise hardware. In Real-Time Shading SIGGRAPH Course Notes (2001), Olano M., (Ed.). (pdf)

[2] Ken Perlin, Dělám hluk. Na základě přednášky prezentované na GDCHardcore (9. prosince 1999). (url)

[1]

[2]