Шум Перлина

Тип градиентного шума в компьютерной графике

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

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

История

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

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

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

Использование

Виртуальный ландшафт, созданный с использованием шума Перлина.

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

Виртуальная органическая поверхность, созданная с помощью шума Перлина.

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

Его часто используют в видеоиграх, чтобы процедурно сгенерированный ландшафт выглядел естественно. Этот успех отчасти обусловлен иерархическим структурированием шума Перлина, который имитирует естественные иерархические структуры и, следовательно, также оказался полезным в приложениях науки об окружающей среде. ^[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] и могут соответствующим образом масштабироваться.

Выполнение

Ниже приведена двумерная реализация классического шума Перлина, написанная на C.

Исходная эталонная реализация Perlin имела существенные отличия ^{[ нужна цитация ]} :

• он использует трехмерный подход путем интерполяции между 8 углами куба вместо 4 углов квадрата, показанного ниже.
• случайное направление градиента перемешивает биты целочисленных координат углов, что намного быстрее, чем перетасовка с использованием интерференции при высокой частоте вращений целочисленных координат углов, объединенных и снова повернутых с высокой частотой продуктом: вращения не являются равномерными распределено.
• Метод Перлина разбивает целочисленное пространство на кубы размером 256 × 256 × 256 , а затем использует случайную перестановку этих кубов для их перетасовки, а затем каждому углу позиции куба присваивается одно из двенадцати направлений соседним неперестановленным кубам в пространстве 4 × 4. × 4 пространства для укладки: для этого требуются только целочисленные операции, но сохраняется равномерное распределение направлений.
• интерполяционная функция представляет собой более плавный шаг на 4 степени (с первыми тремя производными, равными нулю на границах фиксации), а не основной линейный шаг. Это позволяет избежать видимых артефактов, особенно вдоль вершин или диагоналей, соединяющих углы выборки, где результат будет явно анизотропным (превратив желаемый белый шум в розовый шум ; если бы шум использовался для создания твердого кристалла, он не был бы полностью черным и непрозрачен для света, но частично прозрачен и окрашен в некоторых дискретных направлениях наблюдения).

#include <math.h> /* Функция для линейной интерполяции между a0 и a1 * Вес w должен находиться в диапазоне [0.0, 1.0] */ float interpolate ( float a0 , float a1 , float w ) { /* // Вы можете захотеть ограничиться, вставив:  * если (0,0 > w) вернуть a0;  * если (1.0 < w) вернуть a1;  */ return ( a1 - a0 ) * w + a0 ; /* // Вместо этого используйте кубическую интерполяцию [[Smoothstep]] для гладкого вида:  * return (a1 - a0) * (3.0 - w * 2.0) * w * w + a0;  *  * // Используйте [[Smootherstep]] для еще более гладкого результата со второй производной, равной нулю на границах:  * return (a1 - a0) * ((w * (w * 6.0 - 15.0) + 10.0) * w * ш*ш)+а0;  */ }                 typedef struct { float x , y ; } вектор2 ;      /* Создаем псевдослучайный вектор направления */ Vector2 randomGradient ( int ix , int iy ) { // Отсутствие предварительно вычисленных градиентов означает, что это работает для любого количества координат сетки const unsigned w = 8 * sizeof ( unsigned ); const без знака s = w / 2 ; // ширина поворота unsigned a = ix , b = iy ; а *= 3284157443 ; б ^= а << s | а >> ш - с ; б *= 1911520717 ; а ^= б << s | б >> ш - с ; а *= 2048419325 ; float random = a * ( 3.14159265 / ~ ( ~ 0u >> 1 )); // в [0, 2*Pi] вектор2 v ; в . х = потому что ( случайный ); в . y = грех ( случайный ); вернуть v ; }                                                                            // Вычисляет скалярное произведение векторов расстояния и градиента. float dotGridGradient ( int ix , int iy , float x , float y ) { // Получаем градиент из целочисленных координат вектор2 градиент = randomGradient ( ix , iy );                // Вычисляем вектор расстояния float dx = x - ( float ) ix ; float dy = y - ( float ) iy ;             // Вычисляем результат скалярного произведения ( dx * градиент . x + dy * градиент . y ); }    // Вычисляем шум Перлина в координатах x, y float perlin ( float x , float y ) { // Определяем координаты ячейки сетки int x0 = ( int ) floor ( x ); интервал х1 = х0 + 1 ; int y0 = ( int ) пол ( y ); интервал y1 = y0 + 1 ;                           // Определить веса интерполяции // Здесь также можно использовать полином более высокого порядка/s-кривую float sx = x - ( float ) x0 ; float sy = y - ( float ) y0 ;              // Интерполировать между градиентами точек сетки float n0 , n1 , ix0 , ix1 , value ;       n0 = dotGridGradient ( x0 , y0 , x , y ); n1 = dotGridGradient ( x1 , y0 , x , y ); ix0 = интерполировать ( n0 , n1 , sx );                 n0 = dotGridGradient ( x0 , y1 , x , y ); n1 = dotGridGradient ( x1 , y1 , x , y ); ix1 = интерполировать ( n0 , n1 , sx );                 значение = интерполировать ( ix0 , ix1 , sy ); возвращаемое значение ; // Возвращает диапазон от -1 до 1. Чтобы получить диапазон от 0 до 1, умножьте на 0,5 и прибавьте 0,5 }       

перестановка

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

int перестановка [] = { 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 , 9 , 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]

Сложность

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

Смотрите также

• Шум значений
• Моделирование шума
• Симплексный шум

Рекомендации

1. Перлин, Кен. "Шуметь". Noisemachine.com . Кен Перлин. Архивировано из оригинала 8 октября 2007 года.
2. Перлин, Кен (июль 1985 г.). «Синтезатор изображений». ACM SIGGRAPH Компьютерная графика . 19 (97–8930): 287–296. дои : 10.1145/325165.325247.
3. Перлин, Кен. «В начале: Редактор Pixel Stream» (PDF) . Проверено 31 мая 2022 г.
4. Таннер, Майк. «Оскар — награда волшебника Форекс». Проводной . ISSN  1059-1028 . Проверено 31 мая 2022 г.
5. Исходный исходный код
6. «Архивная копия». Архивировано из оригинала 01 мая 2018 г. Проверено 29 мая 2011 г.{{cite web}}: CS1 maint: archived copy as title (link) CS1 maint: bot: original URL status unknown (link)«функции когерентного шума» Кена Перлина
7. Густавсон, Стефан. «Разоблачение симплексного шума» (PDF) . Архивировано из оригинала (PDF) 21 марта 2023 года . Проверено 24 апреля 2019 г.
8. Патент США 6867776, Кеннет Перлин, «Стандарт шума Перлина», выдан 15 марта 2005 г., передан Кеннету Перлину и Wsou Investments LLC. 
9. Этерингтон, Томас Р. (2022). «Шум Перлина как иерархическая нейтральная модель ландшафта». Веб-экология . 22 (1): 1–6. doi : 10.5194/ср-22-1-2022 .
10. Перлин, Кен. «Шум Перлина» . Проверено 26 августа 2020 г.
11. «Шум Перлина: Часть 2» . Архивировано из оригинала 17 февраля 2023 года . Проверено 26 августа 2020 г.

Внешние ссылки

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