Шум Перлина

Двовимірний переріз тривимірного шуму Перліна при z=0.

Шум Перліна належить до градієнтних шумів і є розроблений Кеном Перліном у 1983 році як результат його розчарування у «машинному» вигляді комп'ютерної графіки тих часів. У 1997 році Перлін отримав Академічну Нагороду за Технічні Досягнення:

Перлін не патентував алгоритм, але у 2001 році йому надали патент на використання 3D+ реалізації симплекс шуму для генерації текстур. У симплекс шуму те ж призначення, але він використовує простішу сітку заповнення. Симплекс шум згладжує певні проблеми «класичного шуму» Перліна, такі як складність обчислень і візуально помітні артефакти.

Використання

Шум Перліна — це примітив процедурних текстур, що належить до градієнтних шумів. Художники використовують його, щоб зробити комп'ютерну графіку реалістичнішою. Результат алгоритму є псевдовипадковим, але всі візуальні деталі мають однаковий розмір. Завдяки цьому алгоритм має широке застосування; масштабовані копії шуму Перліна можна підставити у математичний вираз, що дозволить створити різноманітні процедурні текстури. Такі текстури часто використовують у CGI, щоб зробити більш реалістичним вигляд комп'ютерних ефектів, таких як вогонь, дим чи хмари, імітуючи випадковий характер вигляду природних явищ. Також шум Перліна використовують за умов дуже обмеженої пам'яті, наприклад у демосценах, чи у графіці реального часу в іграх.

Розробка

Шум Перліна створений Кеном Перліном у Mathematical Applications Group для Діснеївського фільму 1982 року Трон. У 1997 році Перлін отримав Академічну Нагороду за Технічні Досягнення від Академії кінематографічних мистецтв і наук за його внесок у CGI.

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

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

Визначення сітки

Визначити n-вимірну сітку. Кожній координаті сітки присвоїти n-вимірний одиничний вектор. У випадку одновимірної сітки кожній координаті буде присвоєно значення +1 або −1, для двовимірної сітки кожній координаті буде присвоєно випадковий вектор з одиничного кола, і так далі для більшої кількості вимірів.

Визначення випадкових градієнтів для одного чи двох вимірів є тривіальним. Для більшої кількості вимірів пропонується наближення Монте Карло, де випадкові Картезіанські координати вибираються з одиничного куба, а точки за межами одиничної сфери відкидаються. Процес продовжується, поки не отримаємо необхідну кількість випадкових градієнтів. Далі отримані вектори нормалізують.

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

Скалярний добуток

Другий крок алгоритму — це визначення, в яку комірку сітки потрапляє окрема точка. Для кожного вузла сітки визначаємо вектор відстані між точкою і координатами вузла. Далі обчислюємо скалярні добутки векторів відстані та градієнтних векторів кожного вузла комірки.

Для кожної точки у двовимірній сітці процес вимагатиме 4 операції, у тривимірній — 8. Звідси випливає складність $O(2^n)$.

Інтерполяція

Фінальний крок — інтерполяція значень скалярних добутків, обчислених для кожного вузла. Інтерполяція виконується з використанням функції, що має нульову першу похідну (і, можливо, другу похідну також) на обох кінцевих точках. Лінійна функція, для кінцевих точок на 0 та 1, зі значеннями a₀ та a₁, може бути такою:

$f(x)=a_0(1-x)+a_{1}x$

Функції шуму, використовувані у комп'ютерній графіці, зазвичай мають значення у проміжку [−1.0, 1.0]. Щоб результати шуму Перліна залишалися у цьому проміжку, інтерпольовані значення мають коригуватись з допомогою масштабувального множника.

Псевдокод

Псевдокод двовимірної реалізації Класичного Шуму Перліна:

// Функція лінійної інтерполяції між a0 й a1
 // Вага w має бути у межах [0.0, 1.0]
 function lerp(float a0, float a1, float w) {
     return (1.0 - w)*a0 + w*a1;
 }
 
 // Обчислення скалярний добуток між відстанню і градієнтним вектором.
 function dotGridGradient(int ix, int iy, float x, float y) {
 
     // Попередньо обчислені градієнтні вектори
     extern float Gradient[Y][X][2];
 
     // Обчислення вектора відстані
     float dx = x - (double)ix;
     float dy = y - (double)iy;
 
     // Обчислення скалярного добутку
     return (dx*Gradient[iy][ix][0] + dy*Gradient[iy][ix][1]);
 }
 
 // обчислення шуму Перліна для координат x, y
 function perlin(float x, float y) {
 
     // Визначення координат комірки сітки
     int x0 = (x > 0.0 ? (int)x : (int)x - 1);
     int x1 = x0 + 1;
     int y0 = (y > 0.0 ? (int)y : (int)y - 1);
     int y1 = y0 + 1;
 
     // Визначення ваг інтерполяції
     // Також можна використати поліноміальну криву вищого порядку
     float sx = x - (double)x0;
     float sy = y - (double)y0;
 
     // Інтерполяція між градієнтами
     float n0, n1, ix0, ix1, value;
     n0 = dotGridGradient(x0, y0, x, y);
     n1 = dotGridGradient(x1, y0, x, y);
     ix0 = lerp(n0, n1, sx);
     n0 = dotGridGradient(x0, y1, x, y);
     n1 = dotGridGradient(x1, y1, x, y);
     ix1 = lerp(n0, n1, sx);
     value = lerp(ix0, ix1, sy);
 
     return value;
 }

Складність

При кожному виклику функції має бути обчислений скалярний добуток відстані та градієнта для кожного вузла. За додавання виміру кількість вузлів подвоюється, тому шум Перліна оцінюється як $O(2^n)$ для $n$ вимірів. Альтернативою для шуму Перліна є симплекс та OpenSimplex, що мають кращу складність.