Создание пиксельной туманности при помощи шума и Median Cut

Я хотел, чтобы в моей игре The Last Boundary была туманность. Они потрясающе выглядят и космос без них не космос, а просто разбросанные по фону белые пиксели. Но так как игру я делаю в стиле «пиксель-арт», то мне нужно было как-то заставить мою библиотеку шума генерировать пикселизированные изображения.

Вот несколько примеров:




В одноцветных примера используется 8 цветов, а в других — 16 цветов. В этой статье я расскажу, как создавал пикселизированную туманность для The Last Boundary.

Когда мы работаем с библиотекой шума, например LibNoise, то какой бы движок вы не использовали (или написали свой), то значения обычно распределяются в интервале от -1 до 1. Теоретически вероятнее, что 2D-шум будет находиться в интервале от -0.7 до 0.7, но некоторые реализации масштабируют результат, переводя его в интервал от -1 до 1. Для работы с 2D-текстурами он обычно преобразуется в интервал от 0 до 1, а затем оказывается в пределах значений от RGB(0,0,0) до RGB(255,255,255).


Шум Перлина, сгенерированный из координаты x,y каждого пикселя, отмасштабированной на 0.3f

Затем можно использовать дробное броуновское движение для придания изображению ощущения пышности облаков.


Шум Перлина подвергнут дробному броуновскому движению с 8 октавами, частотой 0.01, регулярностью 0.5 и лакунарностью 2.0.

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

Давайте представим, что хотим создать эффект дыма, то есть такое решение нам подойдёт. Но наша пиксель-артная игра выглядела бы странно, если бы в ней появилась целая куча новых цветов от RGB(0,0,0) до RGB(255,255,255). Внезапно в игре появилось бы 255 новых градаций серого.

Нам нужно преобразовать их в ограниченное количество цветов. Именно этим мы займёмся позже. А пока…

Генерируем случайную туманность

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

Возможно, вы сможете повторять за мной шаг за шагом или вам придётся внести в код дополнения, которые повлияют на ваш шум. Я объясню всё, за исключением изначальной генерации шума и fBm, чтобы вы смогли написать код самостоятельно; думаю, вполне можно предположить, что у вас уже есть возможность генерации шума и fBm.

Для начала покажу результат генерации туманности:


Готовый результат

Важно заметить, что она пока не пикселизирована. Она имеет полный диапазон цветов с пиксельным звёздным небом. Туманность мы пикселизируем позже.

Первое, что нужно сделать — сгенерировать пять разных текстур: Red, Green, Blue, Alpha и Mask. Текстуры Red, Green и Blue нужны для соответствующих каналов конечного цвета. На самом деле я генерирую только один или два цветовых каналов, потому что выяснилось, что при использовании всех трёх получается безумно цветастая туманность, которая выглядит некрасиво. Хорошо подойдёт любой одиночный цвет или сочетание двух цветов.

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


Готовый альфа-канал из нашего примера

Чем белее область, тем значение ближе к 1.0, что даёт нам значение альфы 255. Чем чернее область, тем она прозрачнее. Если взглянуть на пример, то можно увидеть, что чёрные области соответствуют областям, в которых видно звёздное небо.


Пример звёздного неба

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

Моя библиотека шума состоит из модулей, по примеру Lib Noise. В этой библиотеке всё является «модулями», которые можно соединять в цепочки. Некоторые модули генерируют новые значения (Perlin Module, Constant Value), другие соединяют их (Multiply, Add), а некоторые просто выполняют операции над значением (Lerp, Clamp).

Цветовые каналы

Не важно, работаем ли мы с одним, двумя или тремя цветами — каналы Red, Green и Blue генерируются одинаково; я просто использую для них разное значение seed. У меня значения seed зависят от текущего системного времени.

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

1. Шум Перлина

Как и было выше, начальной точкой станет шум Перлина. Если хотите, можете использовать симплексный шум, кажется, его 2D-реализация не принадлежит Кену Перлину, но я могу ошибаться. С точки зрения математики, симплексный шум использует меньше инструкций, поэтому генерация аналогичной туманности будет выполняться быстрее. Так как вместо сетки в нём используются симплексы, он создаёт немного более красивый шум, но мы не будем с ним много работать, так что это не особо важно.

Ниже показан не настоящий код, потому что в реальных исходниках значения x,y изменены fBm на этапе 3. Это просто координата x,y изображения, умноженная на статический коэффициент масштабирования.


Шум Перлина, сгенерированный из координаты x,y каждого пикселя, отмасштабированной на 0.3f. Т.е. PixelValue = PerlinNoise(x * 0.3f, y * 0.3f)

Создаваемые шумом Перлина значения приблизительно находятся в интервале от -1 до 1, поэтому для создания показанного выше обычного изображения в градациях серого мы преобразуем их в интервал от 0 до 1. Я протестировал область определения значений, чтобы при преобразовании получился наибольший контраст (наименьшее значение соответствует 0, наибольшее — 1).

2. Умножение (Multiply)

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

Здесь мне нечего показать, потому что в процессе преобразования значений из интервала от -5 до 5 в интервал от 0 до 1 результат никак не меняется.

3. Дробное броуновское движение (fBM)

Этот этап превращает шум в то, что многие люди считают настоящим «эффектом шума». Здесь мы выполняем октавы всё более мелких сэмплов из функции шума (в нашем случае функцией является perlin(x,y)) для придания пушистости.


Дробное броуновское движение показанного выше шума Перлина. 8 октав, частота .01f, регулярность .5f и лакунарность 2.5f

Уже можно увидеть зарождение чего-то интересного. Показанное выше изображение не сгенерировано масштабированием координат x,y пикселей, этим занимается fBM. Повторюсь, эти значения обратно преобразованы в интервал от 0 до 1 в возможный интервал от -5 до 5.

4. Ограничение (Clamp)

Теперь я ограничу значения интервалом от -1 до 1. Всё за пределами этого интервала будет полностью отброшено.


То же самое fBm, ограниченное интервалом от -1 до 1

Задача этой операции — преобразование значений в меньший интервал с одновременным созданием более резких градиентов и увеличением площадей полностью белого или чёрного цвета. Эти мёртвые или пустые площади важны для эффекта туманности, которым мы займёмся позже. Если бы мы сначала не умножили на 5, то clamp ничего бы не изменил.

5. Прибавляем 1

Теперь мы возьмём значения из clamp и прибавим к ним 1. Таким образом мы перенесём значения в интервал от 0 до 2. После преобразования результаты будут выглядеть так же, как и раньше.

6. Разделим на 2

Вы наверно догадываетесь, что будет, когда я разделю результат на 2 (умножу на .5). В изображении снова ничего не изменится.

Этапы 5 и 6 преобразуют значения в интервал от 0 до 1.

7. Создаём текстуру искажения

Следующим этапом я создам текстуру искажения. Я сделаю это с помощью шума Перлина (с новым значением seed) > умножу на 4 > выполню fBm. В данном случае fBm использует 5 октав, частоту 0.025, регулярность 0.5 и лакунарность 1.5.


Текстура искажения

Эта текстура нужна для того, чтобы создать больше деталей, чем в уже существующей текстуре туманности. Туманность — это довольно большое волнистое облако, а эта текстура внесёт в неё небольшие изменения. Через неё начнёт проступать сеточная природа шума Перлина.

8. Смещаем текстуру цвета при помощи текстуры смещения

Далее я возьму эти две текстуры и использую одну для смещения координат другой на коэффициент. В нашем случае сочетание выглядит так:


Результат смещения

Текстура искажения используется для изменения координат x,y, которые мы ищем в данных исходного шума.

Не забывайте, что показанные выше изображения нужны только для иллюстрации. На каждом из этапов у нас на самом деле есть только функция шума. Мы передаём ей значение x,y, и она возвращает число. На отдельных этапах интервал этого числа может быть разным, но выше мы преобразовали его обратно в градации серого, чтобы создать изображение. Изображение создаётся благодаря использованию каждой координаты x,y изображения как x,y, передаваемых функции шума.

То есть когда мы говорим:

Верни мне значение для пикселя левого верхнего угла с X = 0 и Y = 0

функция возвращает нам число. Если мы просим об этом функцию Перлина, то знаем, что оно будет между -1 и 1, если, как выше, мы применим clamp, сложение и умножение, то получим значение между 0 и 1.

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

Верни мне значение для пикселя в левом верхнем углу с pixel X = 0 и Y = 0

модуль смещения сначала запросит у функции смещения значение в координатах x,y. Результат этого находится в интервале от -1 и 1 (как это было выше). Затем он умножается на 40 (это выбранный мной коэффициент). Результатом будет значение в интервале от -40 до 40.

Затем мы берём это значение и прибавляем его к координатам to the x,y, которые мы искали, и используем этот результат для поиска по текстуре цвета. Отрицательные значения мы отсекли при помощи clamp до 0, потому что в функциях шума невозможно искать отрицательные координаты x,y (по крайней мере, в моей библиотеке шума).

То есть в целом это выглядит так:

ColourFunction(x,y) = значение в интервале от 0 до 1

DisplaceFunction(x,y) = значение в интервале от -1 до 1

DoDisplace(x,y) = {
    v = DisplaceFunction(x,y) * factor
    clamp(v,0,40)
    x = x + v;
    y = y + v;
    if x < 0 then x = 0
    if y < 0 then y = 0
    return ColourFunction(x,y)
}

Надеюсь, вам это понятно. По сути, мы смотрим не на x,y, в которых мы были, а на смещение. И поскольку величина — это тоже плавный градиент, она плавно сдвигается.

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

Вот и всё. Мы повторяем описанные выше операции три раза, используя для каждого канала цвета новые значения seed. Можно создать один или два канала. Я не думаю, что стоит создавать третий.

Альфа-канал

Альфа-канал создаётся примерно таким же образом, как и цветовые каналы:

1. Начинаем с шума Перлина
2. Умножаем на 5
3. fBM с 8 октавами, частотой 0.005, регулярностью 0.5 и лакунарностью 2.5
4. Ограничиваем с помощью Clamp результаты интервалом от -1 до 1, прибавляем 1, делим на 2 (т.е. смещаем интервал от -1 до 1 к интервалу от 0 до 1.
5. Сдвигаем результат на небольшую величину в отрицательном направлении. Я смещаю на 0.4. Благодаря этому всё становится немного темнее.
6. Ограничиваем результаты интервалом от 0 до 1. Так как мы всё сдвинули, сделав немного темнее, то по сути создали больше областей с 0, а некоторые области ушли в отрицательные значения.

Результатом является текстура альфа-канала.


Альфа-текстура

Как я уже говорил, чёрные области будут прозрачными, а белые — непрозрачными.

Канал маски

Это последняя текстура, которая используется для создания теней, накладываемых поверх всего остального. Она начинается так же, как и все другие текстуры:

1. Шум Перлина
2. Умножаем на 5
3. Выполняем fBm, 5 октав, частота 0.01, регулярность 0.1, лакунарность 0.1. Регулярность маленькая, поэтому облако получается менее плотным
4. Выполняем сдвиг интервала от -1 до 1 к интервалу от 0 до 1

Но мы создаём две такие текстуры:


Маска A


Маска B

Эти две текстуры мы подвергаем тому, что я называю модулем Select. По сути мы используем значение из модуля A или модуля B. Выбор зависит от значения модуля C. Для него требуется ещё два значения — Select Point и Falloff.

Если значение в точке x,y модуля C больше или равно SelectPoint, то мы используем значение в точке x,y модуля B. Если значение меньше или равно SelectPoint - Falloff, то мы используем значение в x,y модуля A.

Если оно находится между SelectPoint - Falloff и SelectPoint, то мы выполняем линейную интерполяцию между значениями x,y модуля A и модуля B.

float select(x, y, moduleA, moduleB, moduleC, selectPoint, falloff)
{
    float s = moduleC(x,y);
    if(s >= selectPoint)
        return moduleB(x,y);
    else if(s <= selectPoint - falloff)
        return moduleA(x,y);
    else
    {
        float a = moduleA(x,y);
        float b = moduleB(x,y);
        return lerp(a, b, (1.0 / ((selectPoint - (selectPoint-falloff)) / (selectPoint - s)));
    }
}

В нашем случае модуль A — это модуль Constant со значением 0. Модуль B — это первая текстура маски A, а модуль Selector (модуль C) — это вторая маска B. SelectPoint будет равно 0.4, а Falloff будет равно 0.1. В результате получаем:


Окончательная маска

Увеличивая или уменьшая SelectPoint, мы уменьшаем или увеличиваем величину чёрного в маске. Увеличивая или уменьшая falloff, мы увеличиваем или уменьшаем мягкие края масок. Вместо одной из масок я мог использовать модуль Constant со значением 1, но мне хотелось добавить немного случайности в «немаскированные» области.

Смешение цветового канала и маски

Теперь нам нужно применить маску к каждому из цветовых каналов. Это выполняется при помощи модуля Blending. Он комбинирует проценты значений из двух модулей так, чтобы сумма значений была равна 100%.

То есть мы можем взять 50% значения в x,y модуля A и 50% значения в x,y модуля B. Или 75% и 25%, и т.п. Процент, который мы берём из каждого модуля зависит от ещё одного модуля — модуля C. Если значение в x,y модуля C равно 0, то мы возьмём 100% из модуля A и 0% из модуля B. Если оно равно 1, то берутся обратные значения.

Выполняем комбинирование для каждой текстуры цвета.

• Модуль A — постоянное значение 0
• Модуль B — цветовой канал, который мы уже видели
• Модуль C — результат маски

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

Вот результат для нашего примера:


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

Сравните это с оригиналом до применения смешения с помощью маски.


До смешения при помощи маски

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

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

Комбинируем всё вместе

Наш исходный готовый пример:


Готовый пример

В нём используются каналы Red, Green и Alpha:


Красный канал


Зелёный канал


Альфа-канал

А затем мы просто накладываем их поверх нашего звёздного неба.

Всё теперь выглядит довольно хорошо, но не очень подходит для пиксель-артной игры. Нам необходимо снизить количество цветов…

Median Cut

Эту часть статьи можно применить к чему угодно. Допустим, вы генерируете текстуру мрамора и хотите снизить количество цветов. Именно здесь пригодится алгоритм median cut. Мы воспользуемся им для снижения количества цветов в показанной выше туманности.

Это происходит перед тем, как она накладывается на звёздное небо. Количество цветов абсолютно произвольно.

Алгоритм Median Cut по описанию из Википедии:

Допустим, у нас имеется изображение с произвольным количеством пикселей и мы хотим сгенерировать палитру из 16 цветов. Поместим все пиксели изображения (то есть их RGB-значения) в корзину. Выясним, какой цветовой канал (красный, зелёный или синий) среди всех пикселей в корзине имеет наибольший интервал значений, а затем отсортируем пиксели согласно значениям этого канала. Например, если наибольший интервал значений имеет синий канал, то пиксель с RGB-значением (32, 8, 16) меньше пикселя с RGB-значением (1, 2, 24), потому что 16 < 24. После сортировки корзины поместим верхнюю половину пикселей в новую корзину. (Именно этот шаг дал название алгоритму median cut; корзины делятся пополам по медиане списка пикселей.) Повторим процесс для обеих корзин, что даст нам 4 корзины, затем повторим для всех 4 корзин, получим 8 корзин, затем повторим для 8 корзин, получим 16 корзин. Усредним пиксели в каждой из корзин и получим палитру из 16 цветов. Поскольку количество корзин удваивается при каждой итерации, алгоритм может генерировать только такие палитры, число цветов в которых является степенью двойки. Допустим, для генерации 12-цветной палитры потребуется сначала сгенерировать 16-цветную палитру, а затем каким-то образом объединить некоторые цвета.

Источник: https://en.wikipedia.org/wiki/Median_cut

Это объяснение показалось мне довольно плохим и не особо полезным. При реализации алгоритма таким образом получаются достаточно уродливые изображения. Я реализовал его с некоторыми изменениями:

1. Храним контейнер boxes вместе со значением, обозначающим интервал (подробнее об этом ниже). В box просто хранится некое динамическое количество пикселей из исходного изображения.
2. Добавляем все пиксели из исходного изображения как первый ящик и используем интервал 0
3. Пока общее количество ящиков меньше нужного количества цветов, продолжаем следующие шаги.
4. Если значение интервала равно 0, то для каждого текущего ящика определяем основной цветовой канал этого box, а затем сортируем пиксели в этом box по этому цвету. Основной канал — это тот из Red, Green, Blue и Alpha, который имеет самый широкий интервал. Например, redRange = Max(Red) - Min(Red). Сортировка просто выполняется сравнением значений каждого пикселя в этом основном канале, все остальные каналы при этом игнорируются.
5. Запоминаем интервал этих основных каналов и сохраняем его вместе с box в контейнере boxes. Делаем это частично, чтобы не приходилось повторно вычислять уже полученные box.
6. После того, как мы выполним шаги 4 и 5 для каждого box, сортируем контейнер boxes по наибольшему интервалу. Это отличается от объяснения в Википедии, потому что мы берём наибольший интервал и подразделяем его, а не подразделяем ящики, имеющие только небольшой интервал пикселей. Мы всегда подразделяем наибольший ящик, потому что в нём с наибольшей вероятностью находится слишком много цветов, которые будут представлены одним цветом палитры.
7. Берём самый большой box (большой == с наибольшим интервалом) и удаляем его из контейнера boxes. Разделяем этот ящик на две равные половины и возвращаем их в контейнер с интервалом 0 (чтобы он заново пересчитался позже). Не забывайте, что на предыдущем шаге пиксели в нём были упорядочены, поэтому в одной половине находятся большие значения, а в другой — меньшие. Это позволяет другим цветовым каналам взять верх при повторном вычислении основного канала.

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

Вот изображение, которое объяснит всё нагляднее. Для демонстрации я использую только RGB, потому что альфу показать трудно.


Давайте применим этот метод к нашему примеру изображения.


Оригинал


Median Cut до 16 цветов

Я выяснил, что при использовании двух цветовых каналов хороший эффект получается при 16 цветах. Но учтите, что здесь мы используем и альфа-канал, который тоже участвует в вычислении расстояния между цветами. Так что если вас не волнует прозрачность, то можно использовать и меньше цветов. Так как мой median cut, в отличие от примера из Википедии может использовать произвольное количество цветов (а не только степени двойки), то можно настроить его под свои потребности.


С 16 до 2 цветов

Мы выбирали цвет из каждого box, просто усредняя все значения. Однако это не единственный способ. Возможно вы заметили, что наш результат по сравнению с оригиналом не такой яркий. Если вам это нужно, то можно отдавать предпочтение в верхних интервалах, добавив определению интервалов веса. Или же можно легко выбрать 1, 2 или 3 самых ярких цвета в изображении и добавить их в палитру. Поэтому если вам нужны 16 цветов, генерируйте палитру из 13 цветов и вручную добавляйте свои яркие цвета.


Палитра с тремя самыми яркими цветами

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

Дизеринг

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

Я реализовал простой алгоритм дизеринга Флойда-Стейнберга. Никаких неприятных сюрпризов при этом не возникло. Однако эффект оказался довольно сильным. Вот ещё раз наш пример:


Оригинал

Затем мы урезали палитру до 16 цветов:


Значения сопоставлены с 16-цветной палитрой

А теперь дизеринг с последующим преобразованием в палитру:


Готовый результат с дизерингом