Шум Перлина

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Двовимірний переріз тривимірного шуму Перліна при z=0.

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

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, для двовимірної сітки кожній координаті буде присвоєно випадковий вектор з одиничного кола, і так далі для більшої кількості вимірів.

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

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

Скалярний добуток[ред.ред. код]

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

Для кожнох точки у двовимірній сітці процес вимагатиме 4 операції, у тривимірній - 8. Звідси випливає складність .

Інтерполяція[ред.ред. код]

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

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

Псевдокод[ред.ред. код]

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

// Функція лінійної інтерполяції між 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;
 }

Складність[ред.ред. код]

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

Посилання[ред.ред. код]

  1. Making Noise Ken Perlin talk on noise
  2. а б в libnoise