Симплекс-шум

Симплекс-шум (англ. Simplex noise) — метод побудови n-вимірної функції шуму, подібно до шуму Перлина («класичного шуму»), але з меншою кількістю артефактів і кращою продуктивністю. Кен Перлин розробив алгоритм у 2001 році щоб усунути обмеження класичної функції шуму, особливо за великої кількості вимірів.

Переваги симплекс-шуму над шумом Перлина:

• Симплекс-шум має меншу обчислювальну складність і вимагає менше операцій множення.
• За більшої кількості вимірів (4D, 5D) симплекс-шум є продуктивнішим, складність — ${\displaystyle O(n^{2})}$ для ${\displaystyle n}$ вимірів, в той час як у класичного шуму — ${\displaystyle O(2^{n})}$.
• Симплекс-шум не має помітних артефактів (візуально вони ізотропні), проте шум, згенерований для різних вимірів візуально відрізняється (наприклад, двовимірний шум виглядає інакше, ніж переріз тривимірного шуму; вигляд погіршується зі збільшенням кількості вимірів).
• Симплекс-шум має добре визначений неперервний градієнт, який обчислюється доволі швидко.
• Симплекс-шум легко реалізувати на машинному рівні.

В той час як класичний шум інтерполює значення градієнтів вузлових точок сітки (тобто північно-східного, північно-західного, південно-східного й південно-західного для двовимірної сітки), симплекс-шум поділяє простір на симплекси (тобто ${\displaystyle n}$-вимірні трикутники). Це зменшує кількість вузлів. Гіперкуб у ${\displaystyle n}$ вимірах має ${\displaystyle 2^{n}}$ кутів, симплекс — лише ${\displaystyle n+1}$. У 2D трикутники рівносторонні, але за більшої кількості вимірів симплекси лиш близькі до правильної форми.

Симплекс-шум корисний для програм комп'ютерної графіки, які будують шуми для двох, трьох, чотирьох чи п'яти вимірів. За більшої кількості вимірів n-вимірні сфери навколо кутів симплекса знаходяться недостатньо щільно, тим самим занулюючи функцію на вільних ділянках простору.

Деталі алгоритму

Симплекс-шум зазвичай реалізують як дво-, три-, чи чотиривимірну функцію, проте він може бути визначений для довільної скінченної кількості вимірів. Реалізація складається з чотирьох кроків: відхилення координат, поділ на симплекси, вибір градієнта і сумування ядер.

Відхилення координат

Вхідні координати трансформують за допомогою формули:

${\displaystyle x'=x+(x+y+...)*F}$

${\displaystyle y'=y+(x+y+...)*F}$

${\displaystyle ...}$

де

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

Результатом є розміщення координати на решітці A^*_n, яка, по суті, є розміщенням вершин стільникового гіперкуба, розплющеного вздовж своєї головної діагоналі настільки, щоб відстань між точками (0, 0, …, 0) і (1, 1, …, 1) дорівнювала відстані між (0, 0, …, 0) і (1, 0, …, 0).

Вихідні координати (x', y', …) дозволяють визначити, в яку комірку зміщеного одиничного гіперкуба потрапляє вхідна точка, (xb'=floor(x'), yb'=floor(y'), …), і її внутрішні координати (xi'=x'-xb', yi'=y'-yb', …).

Поділ на симплекси

Коли вищезгадане визначено, значення внутрішніх координат (xi', yi', …) сортуються за спаданням, щоб визначити, якій ортосхемі Шлефлі симплекса належить точка. Тоді результуючий симплекс складають з вершин, що відповідають впорядкованому обходу від (0,0, …, 0) до (1, 1, …, 1), і є n! варіантів, що можуть відповідати одній перестановці координат. Іншими словами, починаємо від нульової координати, потім послідовно додаємо ті, що відповідають найбільшому значенню внутрішньої координати, закінчуючи відповідником найменшого значення.

Наприклад, точка (0.4, 0.5, 0,3) буде лежати всередині симплекса з вершинами (0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1). Значення по осі ординат найбільше, тому визначення координат симплекса починатимемо з нього. Потім збільшуємо значення по осі абсцис, і так далі.

Вибір градієнта

Кожна вершина симплекса додається до базової координати відхиленого гіперкуба, потім хешується у псевдовипадковий градієнтний вектор. Хеш можна реалізувати багатьма способами.

Варто звертати увагу на вибір множини градієнтів, щоб мінімізувати появу артефактів.

Сумування ядер

Внесок кожної з n+1 вершин симплекса враховується за допомогою суми радіально симетричних ядер з центром у кожній вершині. Спочатку за допомогою оберненої формули визначаються невідхилені координати:

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

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

${\displaystyle ...}$

де

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

Ця точка віднімається від вхідних координат, щоб отримати невідхилений вектор переміщення. Цей вектор потрібен для двох цілей:

• Порахувати екстрапольоване значення градієнта з використанням скалярного добутку
• Визначити d², квадрат відстані до точки

Далі внесок ядра кожної суми визначається з рівняння

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

де r² зазвичай обирають рівним 0,5 чи 0,6. 0,5 забезпечує відсутність розривів, в той час як 0,6 може покращити зовнішній вигляд у застосунках, де розриви непомітні. 0,6 використовувався у оригінальній реалізації Кена Перлина.

Правовий статус

Використання реалізації у 3D and higher для textured image synthesis покривається патентом U.S. Patent 6 867 776, якщо алгоритм реалізований з використанням специфічних методик, описаних у будь-якому з пунктів патенту.

Див. також

• Шум Перлина

Посилання

1. Ken Perlin, Making noise. Based on a talk presented at GDCHardcore (Dec 9, 1999). (url) [ 17 лютого 2015 у Wayback Machine.]