Шум Перлина - Perlin noise

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

Шум Перлина это тип градиентный шум разработан Кен Перлин.

История

Кен Перлин развил шум Перлина в 1983 году в результате его разочарования в "машинном" виде компьютерные изображения (CGI) в то время.^[1] Он официально описал свои выводы в СИГГРАФ газета 1985 г. называлась Синтезатор изображений.^[2] Он разработал это в Mathematical Applications Group, Inc. (MAGI) для Дисней с компьютерная анимация научно-фантастический кинофильм Трон (1982). В 1997 году Перлин был удостоен награды Премия Оскар за технические достижения для создания алгоритма.^[3] В 1997 году он выиграл Премия Оскар за технические достижения от Академия кинематографических искусств и наук за этот вклад в CGI.^[4]^[5]^[6]

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

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

Использует

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

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

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

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

Деталь алгоритма

Шум Перлина масштабирован и добавлен в себя для создания фрактальный шум.

Perlin Noise - это функция, которая возвращает число от 0,0 до 1,0 для заданной координаты в N-измерениях. ^[8]

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

Определение сетки

Двумерная сетка градиентных векторов

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

Скалярное произведение

Точечный продукт каждой точки с ее ближайшим значением градиента узла сетки. Скалярное произведение с тремя другими узлами в ячейке не показано.

Для определения значения любой точки-кандидата сначала находится уникальная ячейка сетки, в которой находится точка. Затем ${ Displaystyle 2 ^ {п}}$ углы этой ячейки и связанные с ними векторы градиента идентифицируются. Затем для каждого угла вычисляется вектор смещения, представляющий собой вектор смещения от точки-кандидата к этому углу.

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

Для точки в двумерной сетке это потребует вычисления 4 векторов смещения и скалярных произведений, в то время как для трех измерений потребуется 8 векторов смещения и 8 скалярных произведений. В целом алгоритм имеет ${ Displaystyle О (2 ^ {п})}$ масштабирование сложности.

Интерполяция

Окончательный интерполированный результат

Последний шаг - интерполяция между ${ Displaystyle 2 ^ {п}}$ точечные произведения. Интерполяция выполняется с помощью функции, которая сначала имеет ноль. производная (и, возможно, также вторая производная) на ${ Displaystyle 2 ^ {п}}$ узлы сетки. Следовательно, в точках, близких к узлам сетки, выходные данные будут аппроксимировать точечное произведение вектора градиента узла и вектора смещения к узлу. Это означает, что функция шума будет проходить через ноль в каждом узле, придавая шуму Перлина характерный вид.

Если ${ Displaystyle п = 1}$ , пример функции, которая интерполирует значение ${ displaystyle a_ {0}}$ в узле сетки 0 и значении ${ displaystyle a_ {1}}$ в узле сетки 1

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

где плавный шаг функция была использована.

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

Выполнение

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

Первоначальная эталонная реализация Perlin была написана на Java с основными отличиями:

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

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

#включают <math.h>/ * Функция для линейной интерполяции между a0 и a1 * Вес w должен быть в диапазоне [0,0, 1,0]. */плавать интерполировать(плавать а0, плавать а1, плавать ш) {    / * // Вы можете захотеть зажать, вставив:     * если (0.0> w) return a0;     * если (1.0      */    возвращаться (а1 - а0) * ш + а0;    / * // Вместо этого используйте эту кубическую интерполяцию [[Smoothstep]] для гладкого внешнего вида:     * return (a1 - a0) * (3.0 - w * 2.0) * w * w + a0;     *     * // Используйте [[Smootherstep]] для еще более гладкого результата со второй производной, равной нулю на границах:     * return (a1 - a0) * (x * (w * 6.0 - 15.0) * w * w * w + 10.0) + a0;     */}typedef структура {    плавать Икс, у;} vector2;/ * Создаем случайный вектор направления */vector2 randomGradient(int ix, int иу) {    // Случайное число с плавающей запятой. Отсутствие предварительно вычисленных градиентов означает, что это работает для любого количества координат сетки    плавать случайный = 2920.f * грех(ix * 21942.f + иу * 171324.f + 8912.f) * потому что(ix * 23157.f * иу * 217832.f + 9758.f);    возвращаться (vector2) { .Икс = потому что(случайный), .у = грех(случайный) };}// Вычисляет скалярное произведение векторов расстояния и градиента.плавать dotGridGradient(int ix, int иу, плавать Икс, плавать у) {    // Получаем градиент из целочисленных координат    vector2 градиент = randomGradient(ix, иу);    // Вычислить вектор расстояния    плавать dx = Икс - (плавать)ix;    плавать dy = у - (плавать)иу;    // Вычислить скалярное произведение    возвращаться (dx*градиент.Икс + dy*градиент.у);}// Вычислить шум Перлина в координатах x, yплавать Перлин(плавать Икс, плавать у) {    // Определение координат ячейки сетки    int x0 = (int)Икс;    int x1 = x0 + 1;    int y0 = (int)у;    int y1 = y0 + 1;    // Определяем веса интерполяции    // Здесь также можно использовать полином / s-кривую более высокого порядка    плавать sx = Икс - (плавать)x0;    плавать сы = у - (плавать)y0;    // Интерполяция градиентов точек сетки    плавать n0, n1, ix0, ix1, ценить;    n0 = dotGridGradient(x0, y0, Икс, у);    n1 = dotGridGradient(x1, y0, Икс, у);    ix0 = интерполировать(n0, n1, sx);    n0 = dotGridGradient(x0, y1, Икс, у);    n1 = dotGridGradient(x1, y1, Икс, у);    ix1 = интерполировать(n0, n1, sx);    ценить = интерполировать(ix0, ix1, сы);    возвращаться ценить;}

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

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

Сложность

Для каждой оценки функции шума скалярное произведение векторов положения и градиента должно оцениваться в каждом узле содержащейся ячейки сетки. Поэтому шум Перлина масштабируется со сложностью ${ Displaystyle О (2 ^ {п})}$ за ${ displaystyle n}$ размеры. Альтернативы шуму Перлина, дающему аналогичные результаты с улучшенным масштабированием сложности, включают симплексный шум и OpenSimplex шум.

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

внешняя ссылка

[ken_powerpoint-1] Перлин, Кен. "Шуметь". noisemachine.com. Кен Перлин. Архивировано из оригинал 8 октября 2007 г.

[Perlin:1985:IS:325165.325247-2] Перлин, Кен (июль 1985). «Синтезатор изображений». SIGGRAPH Comput. График. 19 (97–8930): 287–296. Дои:10.1145/325165.325247.

[kens_aa-3] Оригинальный исходный код

[4] Керман, Филипп. Macromedia Flash 8 @work: проекты и методы для выполнения работы. Самс Паблишинг. 2006 г. ISBN 9780672328282.

[5] В архиве 2018-05-01 в Wayback Machine функции когерентного шума Кена Перлина

[6] Густавсон, Стефан. "Демистификация симплексного шума" (PDF). Получено 24 апреля 2019.

[7] Патент США 6867776, Кеннет Перлин, «Стандарт шума Перлина», выпущенный 15 марта 2005 г., передан Kenneth Perlin и Wsou Investments LLC.

[8] Шум Перлина, Брайан Макклейн

[9] Густавсон, Стефан. "Демистификация симплексного шума" (PDF). Получено 24 апреля 2019.

[10] Перлин, Кен. "Шум Перлина". Получено 26 августа 2020.

[11] "Шум Перлина: Часть 2". Получено 26 августа 2020.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]