Шум Перлина

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

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

To Ken Perlin for the development of Perlin Noise, a technique used to produce natural appearing textures on computer generated surfaces for motion picture visual effects. The development of Perlin Noise has allowed computer graphics artists to better represent the complexity of natural phenomena in visual effects for the motion picture industry.

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

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

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

Розробка

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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; } 

Складність

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

Посилання

1. Making Noise Ken Perlin talk on noise
2. libnoise