Шум Перлина

Шум Перлина — это тип градиентного шума, разработанный Кеном Перлином в 1983 году. Он имеет множество применений, включая, но не ограничиваясь: процедурное создание рельефа , применение псевдослучайных изменений к переменной и помощь в создании текстур изображения . Чаще всего он реализуется в двух, трех или четырех измерениях , но может быть определен для любого количества измерений.

Кен Перлин разработал шум Перлина в 1983 году в результате своего разочарования «машиноподобным» видом компьютерно-генерируемых изображений (CGI) в то время. ^[1] Он официально описал свои выводы в статье SIGGRAPH в 1985 году под названием «Синтезатор изображений». ^[2] Он разработал его после работы над компьютерным анимационным научно-фантастическим фильмом Disney «Трон» (1982) для анимационной компании Mathematical Applications Group (MAGI). ^[3] В 1997 году Перлин был награжден премией «Оскар» за технические достижения за создание алгоритма, цитата для которого гласила: ^{[4] [5] [6] [7]}

Кену Перлину за разработку шума Перлина, техники, используемой для создания естественных текстур на компьютерных поверхностях для визуальных эффектов в кинофильмах. Разработка шума Перлина позволила художникам компьютерной графики лучше представлять сложность природных явлений в визуальных эффектах для киноиндустрии.

Перлин не подавал заявки на патенты на алгоритм, но в 2001 году ему был выдан патент на использование 3D+ реализаций симплексного шума для синтеза текстур . Симплексный шум имеет ту же цель, но использует более простую сетку заполнения пространства. Симплексный шум устраняет некоторые проблемы с «классическим шумом» Перлина, среди которых вычислительная сложность и визуально значимые направленные артефакты. ^[8]

Шум Перлина — это примитив процедурной текстуры , тип градиентного шума, используемый художниками визуальных эффектов для повышения реалистичности в компьютерной графике . Функция имеет псевдослучайный вид, но все ее визуальные детали имеют одинаковый размер. Это свойство позволяет ей быть легко управляемой; несколько масштабированных копий шума Перлина могут быть вставлены в математические выражения для создания большого разнообразия процедурных текстур. Синтетические текстуры, использующие шум Перлина, часто используются в CGI, чтобы сделать визуальные элементы, сгенерированные компьютером, такие как поверхности объектов, огонь, дым или облака, более естественными, имитируя контролируемое случайное появление текстур в природе.

Он также часто используется для генерации текстур, когда память крайне ограничена, например, в демонстрациях . Его последователи, такие как фрактальный шум и симплексный шум , стали практически повсеместными в графических процессорах как для графики в реальном времени , так и для нереальновременных процедурных текстур во всех видах компьютерной графики.

Он часто используется в видеоиграх для создания процедурно сгенерированной местности , которая выглядит естественно. Этот успех отчасти обусловлен иерархической структурой шума Перлина, которая имитирует естественные иерархические структуры, и поэтому также оказалась полезной в приложениях экологической науки. ^[9]

Шум Перлина чаще всего реализуется как двух-, трех- или четырехмерная функция , но может быть определен для любого числа измерений. Реализация обычно включает три шага: определение сетки случайных векторов градиента, вычисление скалярного произведения между векторами градиента и их смещениями и интерполяция между этими значениями. ^[7]

Определим n -мерную сетку, в которой каждое пересечение сетки имеет связанный с ним фиксированный случайный n -мерный вектор градиента единичной длины, за исключением одномерного случая, когда градиенты являются случайными скалярами между −1 и 1.

Для вычисления значения любой точки-кандидата сначала найдите уникальную ячейку сетки, в которой лежит точка. Затем определите 2 ⁿ углов этой ячейки и связанные с ними векторы градиента. Затем для каждого угла вычислите вектор смещения. Вектор смещения — это вектор смещения от этого угла до точки-кандидата.

Для каждого угла мы берем скалярное произведение между его вектором градиента и вектором смещения к точке-кандидату. Это скалярное произведение будет равно нулю, если точка-кандидат находится точно в углу сетки.

Обратите внимание, что влияние вектора градиента растет с расстоянием, чего можно избежать, нормализуя сначала вектор смещения до длины 1. Это приведет к заметным резким изменениям, если только расстояние не будет учтено на следующем шаге интерполяции. Однако нормализация вектора смещения не является общепринятой практикой.

Для точки в двумерной сетке это потребует вычисления четырех векторов смещения и скалярных произведений, тогда как в трех измерениях это потребует восьми векторов смещения и восьми скалярных произведений. В общем случае алгоритм имеет сложность O (2 ⁿ ) в n измерениях.

Последний шаг — интерполяция между 2 ⁿ скалярными произведениями. Интерполяция выполняется с использованием функции, которая имеет нулевую первую производную (и, возможно, также вторую производную) в 2 ⁿ узлах сетки. Поэтому в точках, близких к узлам сетки, выход будет аппроксимировать скалярное произведение вектора градиента узла и вектора смещения к узлу. Это означает, что функция шума будет проходить через 0 в каждом узле, придавая шуму Перлина его характерный вид.

Если n = 1 , то примером функции, которая интерполирует между значением a ₀ в узле сетки 0 и значением a ₁ в узле сетки 1, является

${\displaystyle f(x)=a_{0}+\operatorname {smoothstep} (x)\cdot (a_{1}-a_{0})\quad {\text{for }}0\leq x\leq 1}$

где использовалась функция smoothstep .

Функции шума, используемые в компьютерной графике, обычно выдают значения в диапазоне [–1,0, 1,0] и могут быть соответствующим образом масштабированы.

В оригинальной реализации Кена Перлина он использовал простую схему хеширования для определения того, какой вектор градиента связан с каждым пересечением сетки. ^[10] Предварительно вычисленная таблица перестановок используется для превращения заданной координаты сетки в случайное число. Оригинальная реализация работала на сетке из 256 узлов и поэтому включала следующую таблицу перестановок:

перестановка целых чисел [] = { 151 , 160 , 137 , 91 , 90 , 15 , 131 , 13 , 201 , 95 , 96 , 53 , 194 , 233 , 7 , 225 , 140 , 36 , 103 , 30 , 69 , 142 , 8 , 99 , 37 , 240 , 21 , 10 , 23 , 190 , 6 , 148 , 247 , 120 , 234 , 75 , 0 , 26 , 197 , 62 , 94 , 252 , 219 , 203 , 117 , 35 , 11 , 32 , 57 , 177 , 33 , 88 , 237 , 149 , 56 , 87 , 174 , 20 , 125 , 136 , 171 , 168 , 68 , 175 , 74 , 165 , 71 , 134 , 139 , 48 , 27 , 166 , 77 , 146 , 158 , 231 , 83 , 111 , 229 , 122 , 60 , 211 , 133 , 230 , 220 , 105 , 92 , 41 , 55 , 46 , 245 , 40 , 244 , 102 , 143 , 54 , 65 , 25 , 63 ,                                                                                                       161 , 1 , 216 , 80 , 73 , 209 , 76 , 132 , 187 , 208 , 89 , 18 , 169 , 200 , 196 , 135 , 130 , 116 , 188 , 159 , 86 , 164 , 100 , 109 , 198 , 173 , 186 , 3 , 64 , 52 , 217 , 226 , 250 , 124 , 123 , 5 , 202 , 38 , 147 , 118 , 126 , 255 , 82 , 85 , 212 , 207 , 206 , 59 , 227 , 47 , 16 , 58 , 17 , 182 , 189 , 28 , 42 , 223 , 183 , 170 , 213 , 119 , 248 , 152 , 2 , 44 , 154 , 163 , 70 , 221 , 153 , 101 , 155 , 167 , 43 , 172 , 9 , 129 , 22 , 39 , 253 , 19 , 98 , 108 , 110 , 79 , 113 , 224 , 232 , 178 , 185 , 112 , 104 , 218 , 246 , 97 , 228 , 251 , 34 , 242 , 193 ,                                                                                                     238 , 210 , 144 , 12 , 191 , 179 , 162 , 241 , 81 , 51 , 145 , 235 , 249 , 14 , 239 , 107 , 49 , 192 , 214 , 31 , 181 , 199 , 106 , 157 , 184 , 84 , 204 , 176 , 115 , 121 , 50 , 45 , 127 , 4 , 150 , 254 , 138 , 236 , 205 , 93 , 222 , 114 , 67 , 29 , 24 , 72 , 243 , 141 , 128 , 195 , 78 , 66 , 215 , 61 , 156 , 180 };                                                        

Эта конкретная перестановка не является абсолютно обязательной, хотя она требует рандомизированного массива целых чисел от 0 до 255. При создании новой таблицы перестановок следует позаботиться о том, чтобы обеспечить равномерное распределение значений. ^[11]

Чтобы получить вектор градиента с помощью таблицы перестановок, координаты точки сетки последовательно ищутся в таблице перестановок, добавляя значение каждой координаты к перестановке предыдущей координаты. Так, например, исходная реализация делала это в 3D следующим образом:

// Значения выше 255 обрабатывались путем повторения таблицы перестановок дважды. static final int p [] = new int [ 512 ]; static { for ( int i = 0 ; i < 256 ; i ++ ) p [ 256 + i ] = p [ i ] = permutation [ i ]; }                     int хэш = p [ p [ p [ X ] + Y ] + Z ];       

Затем алгоритм просматривает нижние 4 бита выходного хэша, чтобы выбрать 1 из 12 векторов градиента для этой точки сетки.

Для каждой оценки функции шума скалярное произведение векторов положения и градиента должно быть оценено в каждом узле содержащей ячейки сетки. Таким образом, шум Перлина масштабируется со сложностью O (2 ⁿ ) для n измерений. Альтернативы шуму Перлина, дающие похожие результаты с улучшенным масштабированием сложности, включают симплексный шум и шум OpenSimplex .

• Шум ценности
• Шум моделирования
• Симплексный шум

На Викискладе есть медиафайлы по теме «шум Перлина».

• Часто задаваемые вопросы о математике шума Перлина Мэтта Цукера
• Учебник Роба Фарбера, демонстрирующий генерацию и визуализацию шума Перлина на графических процессорах с поддержкой CUDA
• Обширная библиотека C++ Джейсона Бевинса для генерации сложных, когерентных значений шума
• Реализация PHP (GitHub)
• Подробное объяснение шума Перлина (с исходным кодом C++)
• Книга шейдеров Патрисио Гонсалеса Виво и Джен Лоу
• Онлайн-генератор шума Перлина
• Пакет Python для создания шума Перлина
• Генерация случайного рельефа и шума Перлина с помощью SDL