Шум Перлина

Шум Перлина — это тип градиентного шума, разработанный Кеном Перлином в 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. н$ узлы сетки. Следовательно, в точках, близких к узлам сетки, выходные данные будут аппроксимировать скалярное произведение вектора градиента узла и вектора смещения до узла. Это означает, что функция шума будет проходить через 0 в каждом узле, придавая шуму Перлина характерный вид.

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

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>

/* Function to linearly interpolate between a0 and a1
 * Weight w should be in the range [0.0, 1.0]
 */
float interpolate(float a0, float a1, float w) {
    /* // You may want clamping by inserting:
     * if (0.0 > w) return a0;
     * if (1.0 < w) return a1;
     */
    return (a1 - a0) * w + a0;
    /* // Use this cubic interpolation [[Smoothstep]] instead, for a smooth appearance:
     * return (a1 - a0) * (3.0 - w * 2.0) * w * w + a0;
     *
     * // Use [[Smootherstep]] for an even smoother result with a second derivative equal to zero on boundaries:
     * return (a1 - a0) * ((w * (w * 6.0 - 15.0) + 10.0) * w * w * w) + a0;
     */
}

typedef struct {
    float x, y;
} vector2;

/* Create pseudorandom direction vector
 */
vector2 randomGradient(int ix, int iy) {
    // No precomputed gradients mean this works for any number of grid coordinates
    const unsigned w = 8 * sizeof(unsigned);
    const unsigned s = w / 2; // rotation width
    unsigned a = ix, b = iy;
    a *= 3284157443; b ^= a << s | a >> w-s;
    b *= 1911520717; a ^= b << s | b >> w-s;
    a *= 2048419325;
    float random = a * (3.14159265 / ~(~0u >> 1)); // in [0, 2*Pi]
    vector2 v;
    v.x = cos(random); v.y = sin(random);
    return v;
}

// Computes the dot product of the distance and gradient vectors.
float dotGridGradient(int ix, int iy, float x, float y) {
    // Get gradient from integer coordinates
    vector2 gradient = randomGradient(ix, iy);

    // Compute the distance vector
    float dx = x - (float)ix;
    float dy = y - (float)iy;

    // Compute the dot-product
    return (dx*gradient.x + dy*gradient.y);
}

// Compute Perlin noise at coordinates x, y
float perlin(float x, float y) {
    // Determine grid cell coordinates
    int x0 = (int)floor(x);
    int x1 = x0 + 1;
    int y0 = (int)floor(y);
    int y1 = y0 + 1;

    // Determine interpolation weights
    // Could also use higher order polynomial/s-curve here
    float sx = x - (float)x0;
    float sy = y - (float)y0;

    // Interpolate between grid point gradients
    float n0, n1, ix0, ix1, value;

    n0 = dotGridGradient(x0, y0, x, y);
    n1 = dotGridGradient(x1, y0, x, y);
    ix0 = interpolate(n0, n1, sx);

    n0 = dotGridGradient(x0, y1, x, y);
    n1 = dotGridGradient(x1, y1, x, y);
    ix1 = interpolate(n0, n1, sx);

    value = interpolate(ix0, ix1, sy);
    return value; // Will return in range -1 to 1. To make it in range 0 to 1, multiply by 0.5 and add 0.5
}

Перестановка [ править ]

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

int permutation[] = { 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]

Сложность [ править ]

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

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

[ken_powerpoint-1] Перлин, Кен. «Создание шума» . Noisemachine.com . Кен Перлин. Архивировано из оригинала 8 октября 2007 года.

[Perlin:1985:IS:325165.325247-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 г.

[kens_aa-5] Исходный исходный код

[6] «Архивная копия» . Архивировано из оригинала 01 мая 2018 г. Проверено 29 мая 2011 г. {{cite web}}: CS1 maint: архивная копия в качестве заголовка ( ссылка ) CS1 maint: бот: исходный статус URL неизвестен ( ссылка ) «функции когерентного шума» Кена Перлина

[gustavson-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 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]