Szum simplex - Simplex noise

Szum simplex jest metodą konstruowania funkcji szumu n- wymiarowego, porównywalnej z szumem Perlina ( szum „klasyczny”), ale z mniejszą liczbą artefaktów kierunkowych i, w większych wymiarach, z mniejszym narzutem obliczeniowym. Ken Perlin zaprojektował algorytm w 2001 roku, aby sprostać ograniczeniom jego klasycznej funkcji szumu, szczególnie w wyższych wymiarach.

Zalety szumu simplex nad szumem Perlina:

Szum simplex ma mniejszą złożoność obliczeniową i wymaga mniejszej liczby mnożeń.
Simplex Wagi szumu do wyższych wymiarów (4D, 5D) ze znacznie mniejszym kosztem obliczeniowej: złożoność jest dla wymiarów zamiast klasycznego hałasu. ${\ Displaystyle O (n ^ {2})}$ ${\ displaystyle n}$ ${\ Displaystyle O (n \, 2 ^ {n})}$
Szum simplex nie ma zauważalnych artefaktów kierunkowych (jest wizualnie izotropowy ), chociaż szum generowany dla różnych wymiarów jest wizualnie inny (np. Szum 2D ma inny wygląd niż wycinki szumu 3D w 2D i wygląda coraz gorzej przy większych wymiarach).
Szum simplex ma dobrze zdefiniowany i ciągły gradient (prawie) wszędzie, który można obliczyć dość tanio.
Szum simplex jest łatwy do implementacji sprzętowej.

Podczas gdy szum klasyczny interpoluje między gradientami w otaczających punktach końcowych hipersieci (tj. Północno-wschodni, północny zachód, południowy wschód i południowy zachód w 2D), szum simplex dzieli przestrzeń na prostoty (tj. Trójkąty wymiarowe). Zmniejsza to liczbę punktów danych. Podczas gdy hipersześcian w wymiarach ma rogi, simplex w wymiarach ma tylko rogi. Trójkąty są równoboczne w 2D, ale w wyższych wymiarach prostoty są tylko w przybliżeniu regularne. Na przykład kafelkowanie w przypadku funkcji 3D jest orientacją tetragonalnego, nieregularnego plastra miodu . ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle 2 ^ {n}}$ ${\ displaystyle n}$ ${\ displaystyle n + 1}$

Szum simplex jest przydatny w aplikacjach grafiki komputerowej, w których szum jest zwykle obliczany na 2, 3, 4 lub 5 wymiarach. W przypadku większych wymiarów n- sfer wokół n - rogów simplex nie jest wystarczająco gęsto upakowanych, co zmniejsza obsługę funkcji i powoduje jej zerowanie w dużych częściach przestrzeni.

Szczegóły algorytmu

Szum simplex jest najczęściej implementowany jako funkcja dwu-, trój- lub czterowymiarowa , ale można go zdefiniować dla dowolnej liczby wymiarów. Implementacja zazwyczaj obejmuje cztery etapy: pochylenie współrzędnych, prostszy podział, wybór gradientu i sumowanie jądra.

Współrzędna pochylenie

Współrzędna wejściowa jest przekształcana za pomocą wzoru

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

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

{\ displaystyle \ cdots,}

gdzie

{\ Displaystyle F = {\ Frac {{\ sqrt {n + 1}} - 1} {n}}.}

Ma to wpływ na umieszczenie współrzędnej na A ^*
_n kraty, która jest w zasadzie układ wierzchołek o strukturze plastra miodu, hypercubic który został zgnietli wzdłuż głównej przekątnej do odległości pomiędzy punktami (0, 0, ..., 0) i (1, 1, ..., 1) staje równa odległości między punktami (0, 0, ..., 0) i (1, 0, ..., 0).

Wynikowa współrzędna ( x ' , y ' , ...) jest następnie używana do określenia, w której skośnej jednostkowej komórce hipersześcianu znajduje się punkt wejściowy, ( x _b ' = floor ( x ' ), y _b ' = floor ( y ' ), ...) i jego wewnętrzne współrzędne ( x _i ' = x ' - x _b ' , y _i ' = y ' - y _b ' , ...).

Podział uproszczony

Po ustaleniu powyższego wartości współrzędnych wewnętrznych ( x _i ' , y _i ' , ...) są sortowane w kolejności malejącej, aby określić, w którym skośnym prostokącie Schläfli'ego simplex znajduje się punkt. Następnie otrzymany simplex składa się z wierzchołki odpowiadające uporządkowanemu przechodzeniu przez krawędź od (0, 0, ..., 0) do (1, 1, ..., 1), których jest n ! możliwości, z których każda odpowiada pojedynczej permutacji współrzędnej. Innymi słowy, zacznij od zerowej współrzędnej i sukcesywnie dodawaj te, zaczynając od wartości odpowiadającej największej wartości współrzędnej wewnętrznej, a kończąc na najmniejszej.

Na przykład punkt (0,4, 0,5, 0,3) znajdowałby się wewnątrz simplexu z wierzchołkami (0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1) . R _I ' współrzędnych jest największy, tak, że najpierw dodaje się. Następnie następuje współrzędna x _i ' , a na końcu z _i ' .

Wybór gradientu

Każdy wierzchołek simplex jest dodawany z powrotem do współrzędnej bazowej skośnego hipersześcianu i haszowany w kierunku pseudolosowego gradientu. Hash można zaimplementować na wiele sposobów, choć najczęściej używa się tabeli permutacji lub schematu manipulacji bitami.

Należy zachować ostrożność przy wyborze zestawu gradientów do uwzględnienia, aby ograniczyć do minimum artefakty kierunkowe.

Sumowanie jądra

Udział każdego z n + 1 wierzchołków symetrii jest uwzględniany przez sumowanie promieniowo symetrycznych jąder wyśrodkowanych wokół każdego wierzchołka. Najpierw nieskrzywiona współrzędna każdego z wierzchołków jest określana za pomocą wzoru odwrotnego

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

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

{\ displaystyle \ cdots,}

gdzie

{\ Displaystyle G = {\ Frac {1-1 / {\ sqrt {n + 1}}} {n}}.}

Ten punkt jest odejmowany od współrzędnej wejściowej w celu uzyskania nieskrzywionego wektora przemieszczenia. Ten nieskrzywiony wektor przemieszczenia jest używany do dwóch celów:

Aby obliczyć ekstrapolowaną wartość gradientu za pomocą iloczynu skalarnego .
Aby określić d ² , kwadrat odległości do punktu.

Stamtąd sumaryczny wkład jądra każdego wierzchołka jest określany za pomocą równania

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

gdzie r ² jest zwykle ustawione na 0,5 lub 0,6: wartość 0,5 zapewnia brak nieciągłości, podczas gdy 0,6 może zwiększyć jakość wizualną w zastosowaniach, w których nieciągłości nie są zauważalne; 0.6 był używany w oryginalnej implementacji referencyjnej Kena Perlina.

Status prawny

Zastosowania implementacji w 3D i wyższych do syntezy teksturowanego obrazu są objęte patentem USA 6,867,776 , jeśli algorytm jest implementowany przy użyciu określonych technik opisanych w którymkolwiek z zastrzeżeń patentowych. Oczekuje się, że patent wygaśnie 8 stycznia 2022 r.

Zobacz też

Bibliografia

^ Ken Perlin, sprzęt Noise. In Real-Time Shading SIGGRAPH Course Notes (2001), Olano M., (red.). (pdf)
^ Ken Perlin, hałasowanie. Na podstawie przemówienia wygłoszonego na GDCHardcore (9 grudnia 1999). (url)
^ "przetwarzanie obrazu - dlaczego zwiększenie wymiaru szumu simplex wymazuje go?" . Wymiana stosu grafiki komputerowej . Źródło 2021-03-10 .

Linki zewnętrzne

[1] Ken Perlin, sprzęt Noise. In Real-Time Shading SIGGRAPH Course Notes (2001), Olano M., (red.). (pdf)

[2] Ken Perlin, hałasowanie. Na podstawie przemówienia wygłoszonego na GDCHardcore (9 grudnia 1999). (url)

[3] "przetwarzanie obrazu - dlaczego zwiększenie wymiaru szumu simplex wymazuje go?" . Wymiana stosu grafiki komputerowej . Źródło 2021-03-10 .

Languages

In other projects