Пишем настоящий шум Перлина

По поисковому запросу шум перлина сразу попадается этот перевод на Хабре. Как справедливо заметили в комментариях к публикации, речь идёт вовсе не о шуме Перлина. Возможно, автор перевода и сам был не в курсе.

Чем выгодно отличается шум Перлина, легко можно заметить, если сравнить картинки.

Обычный шум (из той самой статьи):
image

Шум Перлина:
image

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


Отступление


Поразительно, но судя по отзывам в личку и в комментарии оказалось, что далеко не все способны видеть вообще какую-либо разницу между простым сглаженным шумом в градациях серого и шумом Перлина. Но, наверное, из-за этого парадокса и появилась и поимела популярность та самая статья.

Попробую дать наводку:
первая картинка состоит из явно выраженных пикселей (увеличенных) разных оттенков серого:

Вторая же (шум Перлина) выглядит как черно-белые размытые черви.

Вот что получается после несложных операций в графическом редакторе (поиск границ, инвертирование, постеризация):
Перлин:

Картинка из статьи (применены точно те же операции):


Да, во фрактальном шуме, если октав много, то понять, что там лежит в оригинале — Перлин или нет уже и правда сложно. Но это ведь не повод назвать фрактальный шум Шумом Перлина.
На этом закончу с описанием разницы.
Конец отступления.

Рассмотрим двухмерный вариант. Пока напишем только класс-заготовку. Входящие данные — двухмерный вектор или два числа с плавающей точкой: x, y.

Возвращаемое значение — число от -1.0 до 1.0:
public class Perlin2d
{
  public float Noise(float x, float y)
  {
    throw new NotImplementedException();
  }
}

Пару слов об интерполяции


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

Здесь в третьем условном квадрате точка в самом центре после интерполяции будет иметь значение 3:

image

Рассмотрим детальнее как там получается тройка. Координаты точки:
x:2.5,
y:0.5


Целочисленные координаты точки (верхний левый угол квадрата):
x:2,
y:0

получаются округлением в меньшую сторону (функция floor).

Локальные координаты точки внутри квадрата получаются вычитанием:
x = 2.5 – 2 = 0.5,
y = 0.5 – 0 = 0.5


Берём значение левого верхнего угла квадрата (1) и верхнего правого (2). Интерполируем верхнюю грань используя локальную координату x (0.5). Линейная интерполяция выглядит так:
static float Lerp(float a, float b, float t)
{
// return a * (t - 1) + b * t; можно переписать с одним умножением (раскрыть скобки, взять в другие скобки):
  return a + (b - a) * t;
}


Берём значение левого нижнего угла квадрата (2) и нижнего правого (7). Интерполируем нижнюю грань используя всё ту же локальную координату x (0.5).
Результаты:
верхняя: 1.5
нижняя: 4.5


Теперь осталась интерполяция верхней и нижней с использованием локальной координаты y (тоже 0.5):
1.5 * 0.5 + 4.5 * (1 – 0.5) = 3


Билинейная интерполяция самая простая но и результат не самый привлекательный.

Другие варианты интерполяции подразумевают модифицирование локальной координаты (параметра t) перед интерполяцией. Получаются более плавные переходы возле граничных значений (0 и 1).

image

В шуме Перлина задействован первый вариант, он даёт достаточно сильное искривление.
static float QunticCurve(float t)
{
  return t * t * t * (t * (t * 6 - 15) + 10);
}
...
// комбинирование с функцией линейной интерполяции:
Lerp(a, b, QuinticCurve(t))


Главная идея и отличие шума Перлина


Всё очень просто:
1. В узлах сетки — псевдослучайные вектора (двухмерные для двухмерного шума, трехмерные для трехмерного и так далее), а не псевдослучайные числа.
2. Интерполируем между скалярными произведениями a) векторов от вершин квадрата до точки внутри квадрата (куба в трехмерном варианте) и b) псевдослучайных векторов (при описании шума Перлина их называют градиентными векторами).

В своём улучшенном варианте шума Кен Перлин использует всего 12 градиентных векторов. Для двухмерного варианта требуется всего 4 — по количеству граней (у квадрата их 4). Вектора направлены (условно из центра куба/квадрата) в сторону каждой из граней и не нормализованы.

Вот они:
{  1, 0 }
{ -1, 0 }
{  0, 1 }
{  0,-1 }


image

Итак, каждому узлу сетки соответствует один из четырёх векторов. Пусть вектор у нас будет массивом float-ов.
    float[] GetPseudoRandomGradientVector(int x, int y)
    {
        int v = // псевдо-случайное число от 0 до 3 которое всегда неизменно при данных x и y

        switch (v)
        {
            case 0:  return new float[]{  1, 0 };
            case 1:  return new float[]{ -1, 0 };
            case 2:  return new float[]{  0, 1 };
            default: return new float[]{  0,-1 };
        }
    }


Реализация


Нам понадобится скалярное произведение векторов:
    static float Dot(float[] a, float[] b)
    {
        return a[0] * b[0] + a[1] * b[1];
    }


Главный метод:
    public float Noise(float fx, float fy)
    {
        // сразу находим координаты левой верхней вершины квадрата
        int left = (int)System.Math.Floor(fx);
        int top  = (int)System.Math.Floor(fy);

        // а теперь локальные координаты точки внутри квадрата
        float pointInQuadX = fx - left;
        float pointInQuadY = fy - top;

        // извлекаем градиентные векторы для всех вершин квадрата:
        float[] topLeftGradient     = GetPseudoRandomGradientVector(left,   top  );
        float[] topRightGradient    = GetPseudoRandomGradientVector(left+1, top  );
        float[] bottomLeftGradient  = GetPseudoRandomGradientVector(left,   top+1);
        float[] bottomRightGradient = GetPseudoRandomGradientVector(left+1, top+1);

        // вектора от вершин квадрата до точки внутри квадрата:
        float[] distanceToTopLeft     = new float[]{ pointInQuadX,   pointInQuadY   };
        float[] distanceToTopRight    = new float[]{ pointInQuadX-1, pointInQuadY   };
        float[] distanceToBottomLeft  = new float[]{ pointInQuadX,   pointInQuadY-1 };
        float[] distanceToBottomRight = new float[]{ pointInQuadX-1, pointInQuadY-1 };

        // считаем скалярные произведения между которыми будем интерполировать
/*
 tx1--tx2
  |    |
 bx1--bx2
*/
        float tx1 = Dot(distanceToTopLeft,     topLeftGradient);
        float tx2 = Dot(distanceToTopRight,    topRightGradient);
        float bx1 = Dot(distanceToBottomLeft,  bottomLeftGradient);
        float bx2 = Dot(distanceToBottomRight, bottomRightGradient);

        // готовим параметры интерполяции, чтобы она не была линейной:
        pointInQuadX = QunticCurve(pointInQuadX);
        pointInQuadY = QunticCurve(pointInQuadY);

        // собственно, интерполяция:
        float tx = Lerp(tx1, tx2, pointInQuadX);
        float bx = Lerp(bx1, bx2, pointInQuadX);
        float tb = Lerp(tx, bx, pointInQuadY);

        // возвращаем результат:
        return tb;
    }


В качестве бонуса:
мультиоктавный шум
    public float Noise(float fx, float fy, int octaves, float persistence = 0.5f)
    {
        float amplitude = 1; // сила применения шума к общей картине, будет уменьшаться с "мельчанием" шума
        // как сильно уменьшаться - регулирует persistence
        float max = 0; // необходимо для нормализации результата
        float result = 0; // накопитель результата

        while (octaves-- > 0)
        {
            max += amplitude;
            result += Noise(fx, fy) * amplitude;
            amplitude *= persistence;
            fx *= 2; // удваиваем частоту шума (делаем его более мелким) с каждой октавой
            fy *= 2;
        }

        return result/max;
    }



И последнее — использование таблицы со случайными числами. В коде Кена Перлина такая таблица прописана вручную и достаются оттуда значения совсем по-другому. Здесь можно экспериментировать и от этого немало зависит равномерность шума и отсутствие в нём явных паттернов.

Я сделал
так
class Perlin2D
{
    byte[] permutationTable;

    public Perlin2D(int seed = 0)
    {
        var rand = new System.Random(seed);
        permutationTable = new byte[1024];
        rand.NextBytes(permutationTable); // заполняем случайными байтами
    }

    private float[] GetPseudoRandomGradientVector(int x, int y)
    {
// хэш-функция с Простыми числами, обрезкой результата до размера массива со случайными байтами
        int v = (int)(((x * 1836311903) ^ (y * 2971215073) + 4807526976) & 1023);
        v = permutationTable[v]&3;

        switch (v)
        {
            ...


& 3 здесь обрезает любое int32 число до 3, читайте об операции AND на википедии
Операция типа % 3 тоже сработала бы, но намного медленней.


Исходный код целиком (без комментариев)
class Perlin2D
{
    byte[] permutationTable;

    public Perlin2D(int seed = 0)
    {
        var rand = new System.Random(seed);
        permutationTable = new byte[1024];
        rand.NextBytes(permutationTable);
    }

    private float[] GetPseudoRandomGradientVector(int x, int y)
    {
        int v = (int)(((x * 1836311903) ^ (y * 2971215073) + 4807526976) & 1023);
        v = permutationTable[v]&3;

        switch (v)
        {
            case 0:  return new float[]{  1, 0 };
            case 1:  return new float[]{ -1, 0 };
            case 2:  return new float[]{  0, 1 };
            default: return new float[]{  0,-1 };
        }
    }

    static float QunticCurve(float t)
    {
        return t * t * t * (t * (t * 6 - 15) + 10);
    }

    static float Lerp(float a, float b, float t)
    {
        return a + (b - a) * t;
    }

    static float Dot(float[] a, float[] b)
    {
        return a[0] * b[0] + a[1] * b[1];
    }

    public float Noise(float fx, float fy)
    {
        int left = (int)System.Math.Floor(fx);
        int top  = (int)System.Math.Floor(fy);
        float pointInQuadX = fx - left;
        float pointInQuadY = fy - top;

        float[] topLeftGradient     = GetPseudoRandomGradientVector(left,   top  );
        float[] topRightGradient    = GetPseudoRandomGradientVector(left+1, top  );
        float[] bottomLeftGradient  = GetPseudoRandomGradientVector(left,   top+1);
        float[] bottomRightGradient = GetPseudoRandomGradientVector(left+1, top+1);

        float[] distanceToTopLeft     = new float[]{ pointInQuadX,   pointInQuadY   };
        float[] distanceToTopRight    = new float[]{ pointInQuadX-1, pointInQuadY   };
        float[] distanceToBottomLeft  = new float[]{ pointInQuadX,   pointInQuadY-1 };
        float[] distanceToBottomRight = new float[]{ pointInQuadX-1, pointInQuadY-1 };

        float tx1 = Dot(distanceToTopLeft,     topLeftGradient);
        float tx2 = Dot(distanceToTopRight,    topRightGradient);
        float bx1 = Dot(distanceToBottomLeft,  bottomLeftGradient);
        float bx2 = Dot(distanceToBottomRight, bottomRightGradient);

        pointInQuadX = QunticCurve(pointInQuadX);
        pointInQuadY = QunticCurve(pointInQuadY);

        float tx = Lerp(tx1, tx2, pointInQuadX);
        float bx = Lerp(bx1, bx2, pointInQuadX);
        float tb = Lerp(tx, bx, pointInQuadY);

        return tb;
    }

    public float Noise(float fx, float fy, int octaves, float persistence = 0.5f)
    {
        float amplitude = 1;
        float max = 0;
        float result = 0;

        while (octaves-- > 0)
        {
            max += amplitude;
            result += Noise(fx, fy) * amplitude;
            amplitude *= persistence;
            fx *= 2;
            fy *= 2;
        }

        return result/max;
    }
}



Результат:
image
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 18

    0
    исправил ошибку в задании размера массива (было 1023)
      0
      Правда ли, что в вершинах сетки значение шума всегда нулевое? Ведь при интерполяции берётся только значение, полученное из вектора, идущего из точки в эту вершину, а вектор этот для самой вершины равен нулю?
        0
        Да, в узлах всегда ноль. Более того, между узлами можно провести нулевые изолинии.
        0
        В формуле a-b должно быть
          0
          поменял (поменял полную формулу в комментарии)
          0
          // return a * (t - 1) + b * t; можно переписать с одним умножением (раскрыть скобки, взять в другие скобки):
            return a + (b - a) * t;
          

          Вроде должно быть

            return (b + a) * t - a;
          
            +5
            Я не буду описывать достоинства шума Перлина и область его применения, а постараюсь объяснить как он реализован.

            Ну вот как так можно писать статьи? Хочется хоть чуток понять что на картинках и о чём дальше речь идёт. Я вот особой разницы на картинках вообще не увидел.
              +2
              Были другие статьи про генерацию ландшафта, например, не хотелось повторяться.
              В майнкрафто-подобной игре, например, если на лету использовать фрактальный шум это сильно ударит по скорости кадров. А если еще и взять вот такой шум, где куча операций сглаживания на одну октаву так тем более.
              Сам же сырой Перлин уже хорош для простых холмов.

              Кстати, обычный пиксельный шум выглядит намного приличнее, если использовать 2 слоя: второй слой, не меняя масштаб, повернуть на 45 градусов:
              image
              Очень просто реализовывается:
              result = Noise(x, y) + Noise((x - y)*Phi, (y + x)*Phi) - 1
              где Phi = 0.70710678118
              

              Но Перлин2д всё равно чуть быстрее и плавнее вдоль тела «червя».
              0
              получаются округлением в сторону 0 (функция floor).
              floor округляет в меньшую сторону, а не в сторону нуля.
              В дополнение к статье. Шум Перлина + фрактальный шум на базе Перлина на GPU: www.shadertoy.com/view/XdXGW8
              0
              Как справедливо заметили в комментариях к публикации, речь идёт вовсе не о шуме Перлина. Возможно, автор перевода и сам был не в курсе.

              Автор перевёл (коряво, но перевёл а не написал) статью Perlin Noise, которая называется кто бы мог подумать — так как называется и которая попадается в выдаче google первой (до появления этих двух и статьи на вики) с достаточно подробным описанием, на которую ссылается довольно много статей в первую очередь на англоязычных ресурсах.

              Ваше
              если сравнить картинки

              image vs image
              как миниму не корректное и взято явно для «показательной непригодности варианта слева», однако если взять первую октаву другого размера например:
              image
              то различие не такое уж заметное.

              Кроме того, назвав «обычным шумом из той самой статьи» одну октаву со сглаживанием, вы
              видимо не дочитали или разнося в пух и прах не увидели что шумом названо нечто другое:
              image

              Поправьте, если не прав: псевдослучайные числа — это псевдослучайные вектора кто бы мог подумать в одномерном пространстве
              и возможно взяты для упрощения понимания (что задумал автор можно только догадываться). И собственно способ получения этих векторов и является настройкой параметров генерации, можно получать на ходу — дабы не хранить в памяти там где это критично, можно загружать из… да хоть из текстуры это уже не важно, важен принцип.

              Соответственно и принцип работы тоже варьируется.

              Как итог: «та самая статья», фу какая мерзкая, была написана переведена из академического интереса, и как верно замечено в комментариях, код не достаточно эффективен, но при этом даёт представление как сгенерировать некий шум, который кто то назвал шумом перлина, однако чрезвычайно на него похож когда это надо и не похож когда это удобно О_о.

              И кстати «фрактальный шум на базе Перлина»(из комментария выше), ну очень похож на то что названо шумом перлина в «той самой статье», даже больше чем у вас чего бы О_о.
                +2
                как миниму не корректное и взято явно для «показательной непригодности варианта слева», однако если взять первую октаву другого размера например:
                то различие не такое уж заметное.

                Сравнивать «синюю» картинку с грейскейл в данном случае бессмысленное заняните. Различие между синим и серым шумом в распределении вероятностей. Распределение для шума Перлина больше смещено к нулю, в то время как «синий» шум имеет нормальное распределение. Кроме того шум Перлина не может давать максимальные или минимальные значения на протяжении 2-ух «квадратов», ибо узлы в шуме перлина дают 0. То есть ситуация, обведенная красным тут:

                невозможна в шуме Перлина.
                Кроме того, назвав «обычным шумом из той самой статьи» одну октаву со сглаживанием, вы
                видимо не дочитали или разнося в пух и прах не увидели что шумом названо нечто другое:
                А потому что вы тоже путаете шум Перлина и фрактальный шум. Когда шум Перлина используют в фрактальном шуме — то шум Перлина берут за одну октаву. Поэтому сравнение корректное.
                Поправьте, если не прав: псевдослучайные числа — это псевдослучайные вектора кто бы мог подумать в одномерном пространстве
                и возможно взяты для упрощения понимания (что задумал автор можно только догадываться).
                Вы не правы. Для двумерного шума Перлина нужны именно двумерные вектора. Иначе это будет не шум Перлина.
                Как итог: «та самая статья», фу какая мерзкая, была написана переведена из академического интереса, и как верно замечено в комментариях, код не достаточно эффективен, но при этом даёт представление как сгенерировать некий шум, который кто то назвал шумом перлина, однако чрезвычайно на него похож когда это надо и не похож когда это удобно О_о.
                Все верно. В интернетах часто путают шум Перлина с фрактальным шумом (от обычного шума). В этом нет вины переводчика, переводчик переводил статью, и сделал это неплохо.
                И кстати «фрактальный шум на базе Перлина»(из комментария выше), ну очень похож на то что названо шумом перлина в «той самой статье», даже больше чем у вас чего бы О_о.
                У автора статьи в примерах не фрактальный шум, а именно шум перлина. Само собой он визуально различается. Еще раз, не путайте фрактальный шум, шум перлина, и просто нормальный шум.
                  0
                  Сначала попробую убедиться в том что все всё поняли: я прямо не называю шумом перлина ни то что описано в первой статье ни то что во второй, является оно таковым или нет.

                  теперь по существу:
                  речь про сравнение, сравните размерность сравниваемого в статье, речь идёт именно о размерности. можно было с таким же успехом взять монохромное изображение изображение 2х2 px увеличить размерность замылить его и сказать: «оно не похоже на шум перлина чего бы мы не сделали», если приведённую в моём коментарии октаву интерполировать с большим радиусом сглаживания(фактически поменять коэффициенты или способ интерполяции) то получить можно очень даже похожую картинку, а про обведённое тут никто не спорит что это не шум перлина, речь про явное различие сравниваемого

                  Для двумерного шума Перлина нужны именно двумерные вектора

                  Опять же, я не упоминал двумерный шум перлина.
                  Речь идёт о сравнении двумерных векторов и одномерных векторов, причём тут двумерность шума перлина?:
                  1. В узлах сетки — псевдослучайные вектора (двухмерные для двухмерного шума, трехмерные для трехмерного и так далее), а не псевдослучайные числа.

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

                  и сделал это неплохо

                  спасибо конечно, но к сожалению через чур злоупотребил переводчиком, и поторопившись не вычитал хорошенько, из-за чего обоснованно «получил по ушам» в комментариях.
                    0
                    Опять же, я не упоминал двумерный шум перлина.
                    Ну мы же картинки двумерные сравниваем или где?
                    теперь по существу:
                    речь про сравнение, сравните размерность сравниваемого в статье
                    Ну вы же фрактальный шум считали шумом Перлина комментом выше:
                    Кроме того, назвав «обычным шумом из той самой статьи» одну октаву со сглаживанием, вы
                    видимо не дочитали или разнося в пух и прах не увидели что шумом названо нечто другое: (и тут картинка фрактального шума)

                    чем в данном описании псевдослучайные числа отличаются от одномерных векторов, раз уж упоминаются более чем двумерные или принято только в одну сторону размерность менять?
                    Тем, что алгоритм шума Перлина такой и никакой иначе. В нем нужно делать dot(расстояние от узла, случайный вектор в узле). Если у нас двумерная картинка, то и «расстояние от узла» будет двумерным. И в узлах у нас должен быть двумерный вектор. А для трехмерного шума перлина нужны будут трехмерные вектора. А в вашей статье — там скаляр вне зависимости от размера.
                    спасибо конечно, но к сожалению через чур злоупотребил переводчиком, и поторопившись не вычитал хорошенько, из-за чего обоснованно «получил по ушам» в комментариях.
                    Ваша статья (хоть и с ошибкой в названии шума) — гораздо ближе лежит к практике, чем эта. Шум описанный у вас применяется чаще, т.к. он дешевле и проще реализуется. Однако знать разницу между нормальным шумом и шумом Перлина все таки полезно.

                    Дополнение:
                    После обновления статьи добавились картинки «червячков». Не совсем удачные, имхо. Эту
                    image
                    картинку стоило бы увеличить с бикубической интерполяцией, чтобы не было сильно выраженной «квадратности». Тогда на этой картинке тоже были бы «червячки», но! на этой картинке кроме червячков стали бы образовываться острова, у червячков были бы утолщения. К сожалению инструмента под рукой сейчас нет, чтобы создать такую картинку.
                      0
                      Вот:

                      Здесь сырые пиксели увеличены с бикубической интерполяцией. Действительно наблюдаются черви, но с утолщениями и проседаниями.
                      А синяя картинка это уже не просто сырые пиксели, там была интерполяция (линейная) + блюр по ближайшим соседям судя по тексту (думаю, можно заменить блюр кубическим затуханием кривой, результат будет тот же, вот здесь такая интерполяция).
                  +1
                  Исправил статью с учетом ваших замечаний.
                    0
                    Спасибо. Жаль вашей публикации не было раньше.
                    На момент появления того перевода пришлось использовать именно близкое к тому решение.
                  0
                  Для интересующихся процедурной графикой обязательна к прочтению книга «Texturing and Modeling: A Procedural Approach».
                  В ней первый шум назван «Value noise» а шум Перлина — «Gradient noise».

                  Only users with full accounts can post comments. Log in, please.