Шум — это просто набор случайных значений. Но в процедурной генерации его используют как функцию: берёшь координаты, получаешь число. Если взять обычный rand() и завести в него координаты пикселей, получится хаотичная каша — никаких паттернов. Гораздо интереснее coherent noise: одинаковые входы дают одинаковый выход, маленькое изменение координат плавно меняет результат, а большое — даёт случайный скачок. Самый известный алгоритм coherent noise — Perlin noise.
Кен Перлин разработал его в 1983 году, когда работал над диссертацией в MAGI, участвовавшей в создании Tron. Ему надоел «машиноподобный» CGI того времени. В 1985 году он представил алгоритм на SIGGRAPH, а в 1997 получил «Оскар» за техническое достижение.
Суть алгоритма для 2D такая. У нас есть точка P с координатами (x, y). Она лежит внутри квадрата, углы которого — ближайшие целые числа. Для каждого из четырёх углов алгоритм заранее берёт случайный единичный вектор (градиент) из таблицы на 256 векторов. Чтобы не повторяться слишком часто, используется permutation table — перемешанный массив из 256 чисел, а самих векторов хранят 512 (дублируют первые 256 во вторую половину), чтобы не выйти за границы при суммировании индексов.
Дальше для каждого угла считают вектор от угла до точки P и берут скалярное произведение этого вектора с градиентом. Получаются четыре числа. Их нужно смешать: сначала линейно интерполировать (Lerp) по оси X, потом по оси Y. Но если интерполировать напрямую, стыки будут резкими. Перлин применил сглаживающую кривую (y = x^2 (3 - 2x)) — плавный S-образный переход на отрезке [0,1]. Пропустив через неё относительные координаты внутри квадрата (rx0, ry0), получают финальное интерполированное значение. Это и есть оригинальный Perlin noise — характерная текстура с размытыми пятнами.
Позже Перлин улучшил алгоритм: сменил кривую сглаживания и способ расчёта градиентов. Но это уже тема следующей статьи.