Perlinův hluk - Perlin noise

Dvourozměrný řez 3D Perlinovým šumem při z = 0

Perlinský šum je typem gradientního šumu vyvinutého Kenem Perlinem .

Dějiny

Ken Perlin vyvinul perlinový hluk v roce 1983 v důsledku své frustrace z tehdejšího „strojového“ vzhledu počítačově generovaných snímků (CGI). Svá zjištění formálně popsal v příspěvku SIGGRAPH v roce 1985 s názvem An image Synthesizer . Ho vyvinut na matematické Applications Group, Inc. (MAGI) pro Disney ‚s počítačem animovaný sci-fi filmu Tron (1982). V roce 1997 získal Perlin Oscara za technické úspěchy za vytvoření algoritmu.

Kenovi Perlinovi za vývoj Perlin Noise, techniky používané k výrobě přirozeně se objevujících textur na počítačem generovaných plochách pro vizuální efekty filmu. Vývoj Perlin Noise umožnil umělcům počítačové grafiky lépe reprezentovat komplexnost přírodních jevů ve vizuálních efektech pro filmový průmysl.

Perlin nepožádal o žádné patenty na algoritmus, ale v roce 2001 mu byl udělen patent na použití 3D+ implementací simplexního šumu pro syntézu textur . Jednostranný šum má stejný účel, ale používá jednodušší mřížku vyplňující prostor. Jednostranný šum zmírňuje některé problémy s Perlinovým „klasickým šumem“, mezi nimi výpočetní složitost a vizuálně významné směrové artefakty.

Využití

Virtuální krajina generovaná pomocí Perlinova šumu

Perlinský šum je primitivní procedurální textura , typ gradientního šumu používaného umělci vizuálních efektů ke zvýšení vzhledu realismu v počítačové grafice . Funkce má pseudonáhodný vzhled, ale všechny její vizuální detaily jsou stejně velké. Tato vlastnost umožňuje, aby byla snadno ovladatelná; do matematických výrazů lze vložit více zmenšených kopií Perlinova šumu a vytvořit tak celou řadu procedurálních textur. Syntetické textury využívající Perlinův šum se v CGI často používají k tomu, aby počítačem generované vizuální prvky-jako povrchy předmětů, oheň, kouř nebo oblaka-vypadaly přirozeněji, napodobováním kontrolovaného náhodného vzhledu textur v přírodě.

Organický povrch generovaný Perlinovým šumem

Často se také používá ke generování textur, když je paměť extrémně omezená, například v ukázkách . Jeho nástupci, jako je fraktální šum a simplexní šum , se stali téměř všudypřítomnými v jednotkách pro zpracování grafiky jak pro grafiku v reálném čase, tak pro procedurální textury ve všech typech počítačové grafiky, které nejsou v reálném čase.

Detail algoritmu

Perlinův šum se změnil a přidal se do sebe, aby vytvořil fraktální šum.

Perlinův šum je nejčastěji implementován jako dvou-, tří- nebo čtyřrozměrná funkce , ale lze jej definovat pro libovolný počet dimenzí. Implementace obvykle zahrnuje tři kroky: definování mřížky náhodných přechodových vektorů, výpočet bodového součinu mezi gradientními vektory a jejich offsety a interpolace mezi těmito hodnotami.

Definice mřížky

2-rozměrná mřížka vektorů s přechodem

Definujte n -rozměrnou mřížku, kde s ní každý průnik mřížky spojil pevný náhodný n -rozměrný vektorový gradient s jednotkovou délkou, kromě jednorozměrného případu, kdy jsou přechody náhodné skaláry mezi -1 a 1.

Tečkovaný produkt

Tečkový součin každého bodu s jeho nejbližší hodnotou přechodu uzlu mřížky. Tečkový součin s dalšími třemi uzly v buňce není zobrazen.

Pro výpočet hodnoty libovolného kandidátského bodu nejprve najděte jedinečnou buňku mřížky, ve které bod leží. Poté identifikujte rohy této buňky a jejich související přechodové vektory. Dále pro každý roh vypočítejte ofsetový vektor. Ofsetový vektor je vektor posunutí z kandidátského bodu do tohoto rohu. ${\ displaystyle 2^{n}}$

Pro každý roh vezmeme součin bodů mezi jeho gradientovým vektorem a ofsetovým vektorem do kandidátského bodu. Tento bodový součin bude nula, pokud je kandidátský bod přesně v rohu mřížky.

Vliv gradientového vektoru roste se vzdáleností, čemuž se lze vyhnout normalizací ofsetového vektoru na první délku . To by přineslo znatelné ostré změny, kromě toho, že vzdálenost je zohledněna v následujícím kroku interpolace. Normalizace ofsetového vektoru však není běžnou praxí. ${\ displaystyle 1}$

Pro bod v dvojrozměrné mřížce to bude vyžadovat výpočet 4 ofsetových vektorů a bodových produktů, zatímco ve třech rozměrech bude vyžadovat 8 offsetových vektorů a 8 bodových produktů. Algoritmus má obecně složitost , kde je počet dimenzí. ${\ displaystyle O (2^{n})}$ ${\ displaystyle n}$

Interpolace

Konečný interpolovaný výsledek

Posledním krokem je interpolace mezi tečkovanými produkty. Interpolace se provádí pomocí funkce, která má v uzlech mřížky nulovou první derivaci (a případně i druhou derivaci) . Proto v bodech blízko uzlů mřížky bude výstup aproximovat bodový součin vektoru přechodu uzlu a posunutého vektoru k uzlu. To znamená, že funkce šumu projde nulou v každém uzlu, což Perlinovu šumu dodá charakteristický vzhled. ${\ displaystyle 2^{n}}$${\ displaystyle 2^{n}}$

Pokud je příkladem funkce, která interpoluje mezi hodnotou v uzlu mřížky 0 a hodnotou v uzlu mřížky 1 ${\ displaystyle n = 1}$${\ displaystyle a_ {0}}$${\ displaystyle a_ {1}}$

${\ Displaystyle f (x) = a_ {0}+\ operatorname {smoothstep} (x) \ cdot (a_ {1} -a_ {0}) \ \ {\ text {for}} 0 \ leq x \ leq 1 }$

kde byla použita funkce smoothstep .

Funkce šumu pro použití v počítačové grafice obvykle vytvářejí hodnoty v rozmezí [-1,0,1,0] a lze je odpovídajícím způsobem škálovat.

Implementace

Následuje dvourozměrná implementace Classical Perlin Noise, napsaná v C.

Původní referenční implementace Perlin byla napsána v Javě, s velkými rozdíly:

• používá trojrozměrný přístup interpolací mezi 8 rohy krychle místo 4 rohů čtverce níže.
• směr náhodného přechodu zamíchá bity celočíselných souřadnic rohů, což je mnohem rychlejší než míchání pomocí interference při vysokých frekvencích otáčení celočíselných souřadnic rohů, sloučeno a znovu otáčeno vysokou frekvencí součinem: rotace nejsou rovnoměrné distribuován.
• Perlinova metoda rozdělila celočíselný prostor na krychle 256x256x256 a poté použila náhodnou permutaci těchto kostek k jejich zamíchání a poté bylo každému rohu pozice krychle přiřazen jeden ze dvanácti směrů k sousedním nepermutovaným kostkám v prostoru dlažby 4x4x4: to vyžaduje pouze celočíselné operace, ale zachovává rovnoměrné rozložení směrů.
• interpolační funkce je hladší 4stupňový Smootherstep (s prvními třemi derivacemi rovnými nule na hranicích upnutí) a ne základní lineární krok. Tím se zabrání viditelným artefaktům, zejména podél vrcholů nebo diagonál spojujících rohy vzorkování, kde by výsledek byl viditelně anizotropní (zabarvení požadovaného bílého šumu do růžového šumu ; pokud by byl šum použit ke generování pevného krystalu, nebyl by zcela černý a neprůhledné pro světlo, ale částečně průhledné a barevné v některých diskrétních směrech pozorování).

Všimněte si, že níže uvedený kód je velmi základní, pouze pro ilustraci, bude pomalý a nebude použitelný v aplikacích.

#include <math.h>

/* Function to linearly interpolate between a0 and a1
 * Weight w should be in the range [0.0, 1.0]
 */
float interpolate(float a0, float a1, float w) {
    /* // You may want clamping by inserting:
     * if (0.0 > w) return a0;
     * if (1.0 < w) return a1;
     */
    return (a1 - a0) * w + a0;
    /* // Use this cubic interpolation [[Smoothstep]] instead, for a smooth appearance:
     * return (a1 - a0) * (3.0 - w * 2.0) * w * w + a0;
     *
     * // Use [[Smootherstep]] for an even smoother result with a second derivative equal to zero on boundaries:
     * return (a1 - a0) * ((w * (w * 6.0 - 15.0) + 10.0) * w * w * w) + a0;
     */
}

typedef struct {
    float x, y;
} vector2;

/* Create pseudorandom direction vector
 */
vector2 randomGradient(int ix, int iy) {
    // No precomputed gradients mean this works for any number of grid coordinates
    const unsigned w = 8 * sizeof(unsigned);
    const unsigned s = w / 2; // rotation width
    unsigned a = ix, b = iy;
    a *= 3284157443; b ^= a << s | a >> w-s;
    b *= 1911520717; a ^= b << s | b >> w-s;
    a *= 2048419325;
    float random = a * (3.14159265 / ~(~0u >> 1)); // in [0, 2*Pi]
    vector2 v;
    v.x = sin(random); v.y = cos(random);
    return v;
}

// Computes the dot product of the distance and gradient vectors.
float dotGridGradient(int ix, int iy, float x, float y) {
    // Get gradient from integer coordinates
    vector2 gradient = randomGradient(ix, iy);

    // Compute the distance vector
    float dx = x - (float)ix;
    float dy = y - (float)iy;

    // Compute the dot-product
    return (dx*gradient.x + dy*gradient.y);
}

// Compute Perlin noise at coordinates x, y
float perlin(float x, float y) {
    // Determine grid cell coordinates
    int x0 = (int)x;
    int x1 = x0 + 1;
    int y0 = (int)y;
    int y1 = y0 + 1;

    // Determine interpolation weights
    // Could also use higher order polynomial/s-curve here
    float sx = x - (float)x0;
    float sy = y - (float)y0;

    // Interpolate between grid point gradients
    float n0, n1, ix0, ix1, value;

    n0 = dotGridGradient(x0, y0, x, y);
    n1 = dotGridGradient(x1, y0, x, y);
    ix0 = interpolate(n0, n1, sx);

    n0 = dotGridGradient(x0, y1, x, y);
    n1 = dotGridGradient(x1, y1, x, y);
    ix1 = interpolate(n0, n1, sx);

    value = interpolate(ix0, ix1, sy);
    return value;
}

Permutace

Mnoho implementací Perlinova šumu používá stejnou sadu permutací, jakou použil Ken Perlin ve své původní implementaci. Tato implementace je následující:

int permutation[] = { 151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 
                      103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 
                      26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237, 149, 56, 
                      87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71, 134, 139, 48, 27, 166, 
                      77, 146, 158, 231, 83, 111, 229, 122, 60, 211, 133, 230, 220, 105, 92, 41, 55, 
                      46, 245, 40, 244, 102, 143, 54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 
                      187, 208, 89, 18, 169, 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 
                      198, 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118, 126, 
                      255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189, 28, 42, 223, 183, 
                      170, 213, 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101, 155, 167, 43, 
                      172, 9, 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232, 178, 185, 112, 
                      104, 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 
                      241, 81, 51, 145, 235, 249, 14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 
                      157, 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205, 
                      93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180 };

Tato specifická permutace není absolutně vyžadována, přestože vyžaduje randomizované pole hodnot [0–255] (včetně). Při vytváření nové permutační tabulky je třeba dbát na rovnoměrné rozdělení hodnot.

Složitost

Pro každé vyhodnocení funkce šumu musí být bodový součin vektorů polohy a gradientu vyhodnocen v každém uzlu buňky obsahující mřížky. Perlinův šum se proto u rozměrů stupňuje komplexně . Alternativy k Perlinovu šumu produkujícím podobné výsledky s vylepšeným škálováním složitosti zahrnují simplexní šum a šum OpenSimplex . ${\ displaystyle O (2^{n})}$${\ displaystyle n}$

Viz také

• Hodnotný hluk
• Simulační hluk
• Jednoduchý hluk

Reference

externí odkazy

• Matematika Zuckera Perlinova hluková matematika Časté dotazy
• Výukový program Roba Farbera, který ukazuje generování a vizualizaci šumu Perlin na grafických procesorech s podporou CUDA
• Rozsáhlá C ++ knihovna Jasona Bevinse pro generování komplexních, souvislých hodnot hluku
• Implementace PHP (github)
• Hluk Perlin vysvětlen v hloubce (se zdrojovým kódem C ++)
• Kniha Shaders od Patricia Gonzaleze Viva a Jen Lowe
• Online generátor šumu Perlin