Генерация шума
Автор: FordPerfect
В данной статье описываются подходы генерации шума, подробнее рассматривается набор наиболее популярных методов и даётся сопутствутствующая терминология. Статья во многом обзорная, и содержит достаточно много (поверхностно изложенной) теории, целью которой является дать читателю наводки для дальнейшего самостоятельного изучения.
Все приведённые отрывки кода, если явно не указано обратное, находятся в общем доступе.
Шумы находят широкое применение в разработке игр.
Примерами их использования являются:
Рис. 1. elevated by Rgba & TBC, 4k demo. Ландшафт и текстура сгенерированы с использованием процедурного шума.
Определения
Источники шума
"Цвета" шума
Категории процедурного шума
Октавы интерполированного численного шума
Шум Перлина
Sparse Convolution Noise
Демонстрация возможностей
Примеры с shadertoy
Литература:
Определения
Шум — беспорядочные колебания различной физической природы, отличающиеся сложностью временной и спектральной структуры.
( https://ru.wikipedia.org/wiki/Шум ).
Данная статья не вдаётся в философские проблемы определения случайности, и предполагает, что читатель имеет интуитивное представление о понятиях "случайное событие" и "вероятность". Также, предполагается наличие общего представления о распределении вероятности и независимости случайных величин. Интересующиеся формализацией этих понятий отсылаются к определениям, содержащимся в учебниках по теории вероятностей.
Последовательность независимых случайных величин (не обязательно равномерно распределённых) называется также дискретным белым шумом.
В дальнейшем в статье под случайными числами будут чаще всего пониматься, без явного указания на это, псевдослучайные числа, т. е. генерируемые детерминированным образом, но "выглядящие" как случайные, в частности с т. з. некоторого набора статистических тестов.
https://ru.wikipedia.org/wiki/Псевдослучайная_последовательность
https://ru.wikipedia.org/wiki/Генератор_псевдослучайных_чисел
Источники шума
В программировании часто встречаются 2 объекта, связанных с генерацией шума:
1. Генератор случайных чисел (ГСЧ (англ. RNG - random number generator), или ГПСЧ - генератор псевдослучайных чисел; в данной статье под ГСЧ подразумевается именно ГПСЧ). При вызове ГСЧ выдаёт следующий элемент в последовательности (псевдо)случайных чисел.
2. Шумовая функция (англ. Noise function). Чистая функция, которая аргументу сопоставляет результат, ведущий себя, в некотором смысле, как шум. Аргумент может быть как дискретным, так и непрерывным, одно- или многомерным.
Для непрерывного случая чаще всего нас интересует когерентная шумовая функция:
Coherent noise is generated by a coherent-noise function, which has three important properties:
Passing in the same input value will always return the same output value.
A small change in the input value will produce a small change in the output value.
A large change in the input value will produce a random change in the output value.
An n-dimensional coherent-noise function requires an n-dimensional input value. Its output value is always a scalar.
http://libnoise.sourceforge.net/glossary/index.html#coherentnoise
Примером ГСЧ является функция rand стандартной библиотеки C. Для многих целей данная конкретная функция является неудачной, т. к. её состояние (определяющее следующий элемент) - невидимая глобальная переменная. Соответственно несколько использующих её подсистем будут влиять друг на друга.
Более удобными в этом смысле являются объекты генераторов, которые хранят своё состояние, например генераторы, определённые в заголовочном файле <random> стандартной библиотеки C++ (<random> присутствует в стандартной библиотеке начиная с C++11).
Шумовую функцию от дискретного аргумента концептуально можно реализовать через ГСЧ, отбросив соответствующее количество начальных значений, например так:
float noise(int i)
{
std::minstd_rand rng(0); // Initialize RNG with the internal state of 0.
rng.discard((unsigned long long)i); // Advance the internal state by i steps.
return std::uniform_real_distribution<float>(0.0f,1.0f)(rng);
}Но с практической точки зрения это не очень удачный код, т. к. вычисления слишком медленны, причём время работы зависит от аргумента.
Примечание: теоретически, n-й результат LCG (реализованного в minstd_rand) может быть вычислен за O(log n) действий (что, впрочем, тоже медленно), но ни одна из тестированных реализаций стандартной библиотеки этого не делала.
Поэтому обычно шумовые функции вычисляют с помощью явных формул.
Шумовыми функциями часто удобно оперировать на концептуальном уровне (т. к. они являются функциями в обычном математическом смысле ("чистыми функциями" в программистской терминологии), и манипуляции с ними можно проводить по обычным правилам). Для практических целей во многих случаях достаточно прямого использования ГСЧ для получения последовательных значений, т. е. лёгкое получение значения по аргументу (а иногда и вообще повторяемость) не требуется. Использование ГСЧ в подобных случаях может оказаться более эффективным.
"Цвета" шума
Спектр шума является важной его характеристикой, т. к. он сильно влияет на воспринимаемый характер шума и при этом имеет удобное математическое описание.
Под спектром чаще всего понимают "спектральную плотность" - квадрат модуля (амплитуды) Фурье-преобразования (это определение "спектральной плотности энергии"; определение спектральной плотности мощности использует автокорреляционную функцию), реже - саму амплитуду (т. к. амплитуда в общем случае является комплексной величиной, иногда кроме модуля представляет интерес также и фаза).
Белый шум — стационарный шум, спектральные составляющие которого равномерно распределены по всему диапазону задействованных частот.
https://ru.wikipedia.org/wiki/Белый_шум
Назван он так по аналогии с белым светом, также содержащим цвета всех частот (оптического диапазона).
Непрерывный идеальный белый шум (для которого два значения нескоррелированы, если они не одновременны) физически некорректен, т. к. имеет бесконечную мощность. Для дискретного белого шума эта проблема отсутствует.
Также по аналогии с оптикой вводят розовый (с преобладанием низких частот) и синий (с преобладанием высоких частот). Часто используют более узкие определения: красным, розовым, синим и фиолетовым называют шумы со спектральными мощностями, зависящими от частоты как 1/f^2, 1/f, f, f^2 соответственно.
См. https://ru.wikipedia.org/wiki/Цвета_шума .
Одним из методов получения дискретного шума с заданными спектральными характеристиками является перемножение спектра дискретного белого шума и заданной спектральной огибающей (Fourier Spectral Synthesis):
Пусть \(\mathbf{X}=\{x_i\}\) - дискретный белый шум. Тогда шум с огибающей (в частотном пространстве) \(w(f)\) можно получить как
\(\mathbf{Y}=\mathcal{F}^{-1}\{w(f) \cdot \mathcal{F}\{\mathbf{X}\}\}\)
что выглядит как
\(y_j=\frac{1}{n}\sum_{k=0}^{n-1} w_k e^{2 \pi i \frac{j k}{n}} \tilde{x}_k\)
где
\(\tilde{x}_k=\sum_{j=0}^{n-1} e^{-2 \pi i \frac{j k}{n}} x_j\)
Пример:
Рис. 2. Слева направо - белый шум, его Фурье-образ (зелёным обозначена действительная часть, синим - мнимая), фильтр в частотном пространстве, действительная часть от обратного преобразования Фурье от произведения Фурье-образа белого шума и фильтра. Эффект затенения вызван асимметричностью фильтра (его величина близка к 0 для отрицательных частот).
Примечание: для дискретного случая может быть практичнее использование дискретного косинусного преобразования (англ. discrete cosine transform (DCT)).
Этот метод естественно обобщается на большее количество измерений.
В силу существования быстрого преобразования Фурье этот подход в некоторых случаях практичен по времени.
Примечание: Для дискретного белого шума с гауссовым распределением значений, его Фурье-преобразованием является также дискретный белый шум с гауссовым распределением значений (в частотном пространстве).
Примеры использования розового шума (в широком смысле слова) встречаются далее в статье.
Синий шум часто применяют в ситуациях, когда нужно получить случайно выглядящую регулярную структуру, а белый шум кажется слишком кластеризованным. Примеры: Poisson disk ( http://devmag.org.za/2009/05/03/poisson-disk-sampling/ , https://www.jasondavies.com/poisson-disc/ ), random dithering и другие.
Категории процедурного шума
За обзором разных методов генерации процедурного шума читатель отсылается к
http://physbam.stanford.edu/cs448x/old/Procedural_Noise%282f%29Categories.html а также замечательной статье State of the Art in Procedural Noise Functions
Далее приводится сжатое изложение некоторых из них.
Один метод - Fourier Spectral Synthesis уже был рассмотрен выше.
Шумы на решётке (Lattice Noises) являются, возможно, наиболее популярными. В них задаются случайные значения в узлах решётки, исходя из которых находится значения в произвольных точках (т. е. строится непрерывная шумовая функция). Их наиболее известные классы:
1. Численный шум (value noise) - в каждом узле решётки задаётся (детерминированным образом) псевдослучайное число. Значением шумовой функции является интерполяция (чаще всего линейная или кубическая) между значениями в углах ячейки, куда попадает аргумент.
Рис. 3. Двумерный численный шум. Слева - одна октава (с билинейной интерполяцией), справа - сумма 5 октав (с билинейной интерполяцией, и коэффициентом 0.73).
2. Градиентный шум (gradient noise) - в каждом узле решётки задаётся (детерминированным образом) псевдослучайный вектор (называемый градиентом). Значение шумовой функции получается исходя из значений в углах ячейки и направлений на эти узлы. Наиболее известным представителем является шум Перлина.
Рис. 4. Двумерный срез трёхмерного шума Перлина.
Midpoint displacement method (напр. http://en.wikipedia.org/wiki/Diamond-square_algorithm ).
Рис. 5. Plasma fractal, сгенерированный Diamond-square algorithm.
Вейвлет-шум ( http://en.wikipedia.org/wiki/Wavelet_noise ). Состоит в генерации заполненного случайным образом изображения R (белый шум), и вычитания из него upsample(downsample(R)), убирая таким образом детали, представимые в уменьшенном разрешении.
Рис. 6. Иллюстрация алгоритма Wavelet noise. Рисунок из статьи Wavelet Noise, Robert L. Cook, Tony DeRose, Pixar Animation Studios.
Sparse Convolution Noise. Представляет собой свёртку каким-либо образом выбранного ядра и Пуассоновского шумового процесса (Poisson process noise). Пуассоновский шумовой процесс - это набор нескоррелированных по амплитуде импульсов, расположенных в случайно выбранных точках. Таким образом, данный вид шума представляет собой суперпозицию ядер с центрами и интенсивностями, задаваемыми случайным набором импульсов, наподобие интерференционной картины. Наиболее известный представитель - Gabor Noise:
http://graphics.cs.kuleuven.be/publications/LLDD09PNSGC/
http://graphics.cs.kuleuven.be/publications/GLLD12GNBE/
Рис. 7. Gabor Noise.
Рис. 8. Примеры из Gabor Noise by Example.
Шум Уорли ( http://en.wikipedia.org/wiki/Worley_noise ). Предложен Стивеном Уорли в 1996 г. в статье A cellular texture basis function. Представляет собой диаграмму Вороного n-го порядка для случайного набора точек, т. е. значением функции является расстояние до n-й ближайшей точки (расстояние не обязательно использует евклидовскую метрику, иногда применяется, например, манхэттенская). Часто используется для создания ячеистых текстур (комбинация 1-го и 2-го порядков). Хорошее описание эффективных алгоритмов построения ячеистых текстур можно найти в статьях:
http://www.blackpawn.com/texts/cellular/default.html
https://fgiesen.wordpress.com/2010/03/28/how-to-generate-cellular-textures/
https://fgiesen.wordpress.com/2010/03/29/how-to-generate-cellular-textures-2/
Существуют разные способы генерации набора точек для шума Уорли. Jittered grid (регулярная сетка с детерминированным образом определённым случайным смещением вершин) является довольно популярной, но приводит к анизотропии. Уорли в статье использовал метод с разбиением пространства на кубы и генерации для куба случайных точек количеством, определяемым распределением Пуассона; метод похож на приведённый в подпункте Sparse Convolution Noise (см. ниже).
Рис. 9. Ячеистая текстура (cellular texture).
Многие из этих методов производят шум в довольно узком диапазоне частот (другими словами - с определённым характерным размером деталей). Он может быть не очень интересен сам по себе, но является удобным строительным блоком для комбинаций, реализующих более интересный шум.
Очень частым подходом является суммирование октав шума:
\(f_{\Sigma}(\mathbf{x})=
\frac{1}{\sum_{k=0}^{n-1} a^k}
\sum_{k=0}^{n-1} a^k f(b^k \mathbf{x})\)
Коэффициент \(a\) носит разные названия. Библиотека libnoise использует термин Persistence, как и статья Хьюго Элиаса, где упоминается, что термин persistence в отношении шума был введён Бенуа Мандельбротом с обратным смыслом (т. е. \(1/a\)).
Коэффициент \(b\) в libnoise назван Lacunarity, и в большинстве случаев выбирается равным 2.
См. http://libnoise.sourceforge.net/glossary/ .
Коэффициент \(a\) чаще всего выбирают в диапазоне [0;1], хотя это и не обязательно.
Примечание: для случая \(0 \leq a < 1\) ряд сходится для бесконечного количества октав, и каждая новая вносит всё меньшую поправку. Это не обязательно справедливо для производных, см. функцию Вейерштрасса.
Такой метод даёт розовый шум, который находит много применений.
Этот подход часто называют фрактальным броуновским движением (fractal Brownian motion) или сокращённо, fBm, даже в случаях когда он, строго говоря, не соответствует определению fBm.
