Шум перлина в фотошопе
1. Рекомендация использования косинусоидальной интерполяции.
2. Двумерная функция Noise1 использует одномерную функцию с индексом n = x + y * 57. Т. к. 57 - составное число, то это приводит к заметным визуальным артефактам.
3. Используется подход через шумовую функцию, без упоминания о том, что для заполнения текстуры (что является основным упоминаемым в статье использованием) может быть достаточно ГСЧ, что улучшает производительность. Шумовая функция позволяет, впрочем, не хранить текстуру явно.
Также использованная функция шума на решётке (Noise1) при прямолинейном переводе с Pascal на C приводит к коду, который содержит undefined behavior (signed arithmetic overflow):
(пример взят из библиотеки libnoise)
что, впрочем, не является виной автора.
Вкратце, суть метода:
1. В узлах решётки (точках с целочисленными координатами) детерминированным образом задаются псевдослучайные числа в диапазоне [-1;+1].
2. Определяется функция от вещественных координат, как интерполяция между значениями функции из п.1, в зависимости от дробной части координат.
3. Шумовая функция определяется как сумма заданного числа октав функции из п.2 с заданным коэффициентом a.
Метод может быть использован для произвольного количества измерений.
Наиболее частыми функциями интерполяциями являются: линейная (или би-, трилинейная, и т. д. для пространств более высокой размерности), кубическая (Catmull–Rom spline), S-curve (3-й и 5-й степени).
Их формулы для одномерного случая:
Линейная:
\(x=x_0 (1-t)+x_1 t\)
обеспечивает непрерывность функции.
Кубическая (Катмулл-Ром):
\(\begin x=\frac( & (-t^3+2 t^2-t) & x_ & + \\ & (3 t^3-5 t^2+2) & x_ & + \\ & (-3 t^3+4 t^2+t) & x_ & + \\ & (t^3-t^2) & x_ & ) \end\)
обеспечивает непрерывность функции и её 1-й производной.
Кубическая S-curve:
\(x=x_0 (1-(3 t^2-2 t^3))+x_1 (3 t^2-2 t^3)\)
обеспечивает непрерывность функции и её 1-й производной.
S-curve 5-й степени:
\(x=x_0 (1-(6 t^5-15 t^4+10 t^3))+x_1 (6 t^5-15 t^4+10 t^3)\)
обеспечивает непрерывность функции и её 1-й и 2-й производной.
Примечание:
В отличие от остальных приведённых функций интерполяции, Catmull–Rom spline:
1. Требует 4 контрольные точки, а не 2.
2. Может давать значения, выходящие за диапазон входных данных (например, последовательность [0,1,1,0] в центре даёт 1.25).
Пример реализации для двумерного случая и линейной интерполяции (диапазон значений [-1;+1]):
Пример демонстрационный и является сильно неоптимальным по производительности (т. к. оптимизировалась в нём понятность).
Замер времени его работы на машинах ideone дал следующие результаты (не стоит на них полагаться, т. к. качество экспериментальной методики вызывает вопросы):
octaves_of_value_noise:
| octaves | tacts per call |
| 1 | 337 |
| 2 | 613 |
| 3 | 894 |
| 4 | 1171 |
| 5 | 1466 |
grid_value_noise: 32 tacts.
Для получения текстур предлагается использовать самплинг данной функции. Следует заметить, что в таком виде функция даёт текстуры, не являющиеся бесшовными, что впрочем легко исправляется (добавлением модуля в grid_value_noise).
Однако если целью является однократное получение статической текстуры с линейной интерполяцией, то возможности шумовой функции (которая позволяет, например, элементарно получать масштабированные/смещённые/повёрнутые версии одной и той же текстуры) являются избыточными, и тот же подход можно реализовать эффективнее: генерируем серию текстур, размера size/2^(octaves-1), size/2^(octaves-2), . size - первая заполнена белым шумом, каждая следующая - суммой белого шума и upscale-версии предыдущей текстуры с весами, соответствующими параметру a.
Впрочем, обобщение этого способа на другие функции интерполяции не является очевидным.
Рассматриваемый в этом пункте шум имеет некоторые недостатки. В частности, особенно при низком количестве октав, он обладает хорошо заметной анизотропией.
Интерполяция 0-го порядка.
Билинейная (т. е. 1-го порядка) интерполяция. Справа - полученная по ней карта высот.
Интерполяция S-curve 3-го порядка. Справа - полученная по ней карта высот.
Интерполяция S-curve 5-го порядка. Справа - полученная по ней карта высот.
Для сравнения текстуры градиентного шума (тоже 1 октава):
Градиентный шум. Справа - полученная по нему карта высот.
Шум Перлина
Алгоритм нахождения значения функции в заданной точке следующий:
1. В узлах решётки (точках с целочисленными координатами) детерминированным образом задаются псевдослучайные n-мерные единичные (или, по крайней мере, одинаковые по длине) векторы (называемые градиентами, о причинах - см. далее).
2. Для точки находится целочисленная ячейка (единичный гиперкуб с целочисленными вершинами), которая её содержит.
3. Для каждого угла ячейки строится вектор из этого угла в точку, и находится его скалярное произведение с градиентом в этом угле.
4. Полученные скалярные произведения интерполируют (линейная интерполяция с весами, соответствующим S-curve от дробных частей координат: важно, чтобы 1-е производные от функции интерполяции были равны 0 на краях). Такая интерполяция сепарабельна. С практической точки зрения, вычисляются n значений S-curve (по 1 для каждой координаты) и 2^-1 раз проводится линейная интерполяция (2^ по первой координате, затем 2^ - по 2-й для результатов предыдущего шага, и т. д.).
Пусть имеются 8 посчитанных значений скалярного произведения в углах куба:
\(s_,\,s_,\,s_,\,s_,\,s_,\,s_,\,s_,\,s_\)
Сначала проинтерполируем по x:
\(s_=s_ (1 - t_0)+s_ t_0\)
\(s_=s_ (1 - t_0)+s_ t_0\)
\(s_=s_ (1 - t_0)+s_ t_0\)
\(s_=s_ (1 - t_0)+s_ t_0\)
где
\(t_0=3 x^2-2 x^3\)
Дальше - по y:
\(s_<**0>=s_ (1-t_1)+s_ t_1\)
\(s_<**1>=s_ (1-t_1)+s_ t_1\)
где
\(t_1=3 y^2-2 y^3\)
И окончательно, по z:
\(s_<***>=s_ <**0>(1-t_2)+s_ <**1>t_2\)
где
\(t_2=3 z^2-2 z^3\)
Легко убедиться, что интерполяция сепарабельна, т. е. результат не зависит (с точностью до погрешностей округления при работе с числами с плавающей точкой) от порядка, в котором мы обрабатываем оси.
То же самое, более формально:
1. \(\vec(\vec): \vec \in \mathbb^n, \vec(\vec) \in \mathbb^n, \vec(\vec) \cdot \vec(\vec) = 1\) — градиенты в узлах решётки.
2. \(\vec
=\vec+\vec, \vec \in \mathbb^n, \vec \in [0;1]^n\) — целочисленная и дробная части координат.
3. \(s_>=s_>=\left(\vec(\vec+\vec) \right) \cdot (\vec-\vec), i_q \in \\) — скалярные произведения в углах ячейки.
4.
\(\mathrm(\vec
)= \sum_ \in \^n> s_> \left( \prod_^ 1-(3 r_q^2 - 2 r_q^3) \right)\) — интерполяция.
Легко показать, что если условие равенства 0 производной на краях выполнено, то градиент получившейся скалярной функции в целочисленных точках будет равен заданным там векторам.
Данная функция несколько медленнее интерполяции численного шума, рассмотренной в предыдущем пункте, но даёт более качественный шум. Несмотря на то, что шум Перлина не является изотропным, его анизотропия гораздо менее ярко выражена, чем у численного шума на декартовой сетке.
Слева - шум Перлина с осями "вправо/вверх", справа - его поворот на 37°.
perlin/noise/ ) и процедура выбора тоже несколько отличается.
Также шум Перлина реализован в составе библиотеки libnoise.
Sparse Convolution Noise
Этот вид шума был предложен Джоном Питером Льюисом в 1989 г. в статье Algorithms for Solid Noise Synthesis.
Он представляет собой свёртку некоторым образом выбранного ядра (англ. kernel) \(h\) с Пуассоновским шумовым процессом:
\(N(\vec)=\left[ h * \gamma \right] (\vec)\)
другими словами:
\(N(\vec)=\int_<\mathbb^n> h(\vec') \gamma(\vec-\vec') dr'^n\)
Пуассоновский шумовой процесс - это сумма (обычно - бесконечного числа) точечных импульсов в случайно выбранных равномерно распределённых точках со случайными нескореллированными амплитудами:
\(\gamma(\vec)=\sum_i w_i \delta(\vec-\vec_i)\) ,
где \(\delta(\vec)\) - дельта-функция Дирака.
Название отражает тот факт, что количество импульсов в отдельно выбранном элементе пространства описывается распределением Пуассона.
Из этого следует, что:
\(N(\vec)=\sum_i w_i h(\vec-\vec_i)\)
Эта сумма содержит, в общем случае, бесконечное количество слагаемых.
Для того, чтобы её вычисление занимало конечное время, выбирают ядро, являющееся финитной функцией (т. е. функцией с ограниченным носителем; примечание: в \(\mathbb^n\) понятия ограниченный носитель и компактный носитель тожественны), а следовательно - обращающееся в 0 на некотором расстоянии от начала координат (радиусе ядра).
Льюис использовал ядро
\(h(\vec)= \left\ \frac+\frac \cos(\pi |r|) & , |r|<1 \\ 0 & , |r| \geq 1 \end\right.\)
В статье Procedural Noise using Sparse Gabor Convolution бесконечное ядро обрезается по
5% максимума. Функция при этом получается разрывной, что, по утверждениям авторов, не приводит к визуальным артефактам даже для производных. При желании разрыв можно убрать использованием оконной функции.
Для ядра радиуса \(R\) алгоритм разбивает пространство на ячейки ребром \(R\) . Тогда значение шумовой функции в точке зависит только от импульсов, содержащихся в ячейке, содержащей эту точку, и её непосредственных соседях.
Импульсы в ячейке генерируются ГСЧ с зерном (начальным состоянием) являющимся хеш-функцией от координат ячейки. Хранить их явным образом не требуется.
Это приводит к примерно следующей реализации для 2-мерного случая (оптимизировалась понятность, а не эффективность):
Berlin Noise - это шум, предложенный Кеном Перлином в 1983 году. Он используется для имитации естественных текстур, таких как водяные волны, ручная роспись, пламя, мрамор и другие текстуры, а также может создавать различные общие специальные эффекты, такие как динамический дым.
По методу генерации компьютерного шума его можно разделить на градиентный шум и числовой шум, и берлинский шум является одним из наиболее типичных представителей градиентного шума. Алгоритмы и идеи этой статьи взяты из следующего блога: если вам интересно, вы можете поближе познакомиться с содержанием этого блога.
[Графика] говорить о шуме
Следующее представляет реализацию Perlin Noise в 1D, 2D и более высоких измерениях.
1. Двумерный берлинский шум
Двумерный берлинский шум - основа берлинского шума. Понимание двумерного берлинского шума помогает быстрее реализовать другие измерения шума.
Идея алгоритма заключается в следующем:
На следующем рисунке представлена реализация алгоритма:
Рассчитайте эффект градиента 4 угловых точек на точке:
В реальных вычислениях целая точка используется как точка решетки для генерации каждого вектора градиента. Где u, v представляет дробную часть расчетной точки, а именно x-floor (x) и y-floor (y). Затем используйте вектор направления и значение градиента соответствующих четырех угловых точек, чтобы сделать произведение точек для генерации n00, n10, n01 и n11. n00 представляет произведение точек с точкой градиента нижнего левого угла прямоугольника, n10 представляет произведение точек нижнего правого угла прямоугольника, n01 представляет произведение точек левого верхнего угла прямоугольника, и n11 представляет произведение точек верхнего правого угла прямоугольника. g представляет вектор градиента каждой соответствующей угловой точки.
Следующие четыре значения взвешены. Взвешивание сначала взвешивается по x, а затем по y. То есть сначала используйте n00 и n10 для взвешивания n0, затем используйте n01 и n11 для взвешивания n1, этот шаг является x-взвешенным, затем используйте n0 и n1 для взвешивания n, этот шаг является y-взвешенным. Весовая формула:
Normal f ( u ) принимать f ( 0 ) = 0 ， f ( 0.5 ) = 0.5 ， f ( 1 ) = 1 Функция нижнего порядка может принять f ( u ) = u Более высокий порядок может занять:
f ( u ) = 3 u 2 − 2 u 3 или f ( u ) = 6 u 5 − 15 u 4 + 10 u 3 Чем выше порядок, тем лучше плавность изображения, но тем больше объем вычислений.
Затем прикрепите код Matlab
Метод, на который ссылается вышеуказанная функция:
Схема конечного эффекта выглядит следующим образом:
2. Фрактальный шум на основе двумерного перлин-шума
Фактически, фрактальный шум можно понимать как основной шум различных масштабов, наложенных друг на друга.
Этот вид шума обычно имеет более тонкую текстуру и определенную степень самоподобия, имеет хорошую случайность как в деталях, так и в большом масштабе.
Ниже приведен шум различных масштабов, создаваемый перлин-шумом в разделе 1. Выше были изменены верхние пределы лимкс и известняк.
Реализация типизированного шума заключается в сложении каждого изображения на приведенном выше изображении с определенным весовым соотношением. Чтобы обеспечить аддитивность матрицы zmat в разных масштабах, конечное число точек расчета должно быть одинаковым, то есть изменение limx и dx должно увеличиваться в одинаковом кратном размере. Ниже приведен код реализации шума при печати с использованием функции simplexnoise2f.m из первого раздела.
График окончательного результата показан ниже:
Это когда вес равен 0,5, от начального изображения до конечного детали изображения разделения
Это когда вес установлен равным 1, от исходного изображения до конечного изображения детали разделения
Вы можете видеть, что даже изменение весов может сделать окончательную графику совершенно другой.
3. Бесшовное шумы Берлина
Создание изображений берлинского шума связано только с начальным вектором случайного градиента. Таким образом, если начальный вектор градиента является постоянным, шум также является постоянным, если случайный вектор градиента повторяется в одном направлении, конечное изображение также будет повторяться непрерывно.
Поэтому идея мозаичного берлинского шума в этой статье состоит в том, чтобы повторить предыдущую границу на границе, то есть левая граница и правая граница имеют одинаковый градиент, а верхняя граница и нижняя граница имеют одинаковый градиент. Далее следует код для мозаичного шума. За исключением того, что определения uxmat и uymat по сравнению с предыдущим изменились, остальные коды клавиш те же.
На следующем рисунке показана реализация мозаичного изображения. Мозаика в направлениях x и y удваивается:
4. Реализация одномерного шума
4.1 Одномерный берлинский шум
По сравнению с двумерным берлинским шумом, одномерный шум имеет только две случайные градиентные точки (точки решетки) на расчетную точку, и случайный градиент также является одномерным.
По сравнению с 2D это все еще 6 основных ссылок:
1. Установить сетку расчетных точек
2. Установить координаты сетки градиента и соответствующие случайные градиенты
3. Установить пустую матрицу для хранения расчетных точек
4. Рассчитать стоимость каждой расчетной точки
5. Найти скалярное произведение вектора направления и вектора градиента
6. Взвешенные итоговые результаты расчета
Код выглядит следующим образом
Изображение как показано
4.2 Динамический одномерный берлинский шум
Для берлинского шума весь динамический n-мерный шум может быть реализован с n + 1-мерным берлинским шумом. Конкретный способ реализации заключается в использовании первых n измерений в качестве изображения и n + 1-го измерения в качестве временной оси для преобразования.
В matlab, если известна двумерная матрица берлинского шума zmat, изображения каждого ряда матрицы могут быть нарисованы для реализации одномерного шума. Схематический код выглядит следующим образом:
Тот же принцип применим к динамическому двумерному шуму.
5. Высокомерный берлинский шум и его недостатки
Для одномерного шума Перлина можно рассчитать только 2 градиентные точки для каждой расчетной точки, для двумерного шума Перлина каждую расчетную точку необходимо рассчитать с помощью прямоугольных 4 угловых точек, окружающих эту точку, для трехмерных требуется 8 точек. Рассчитайте градиент углов куба, для n измерений необходимо 2 ^ n углов, чтобы вычислить значение каждой точки, что значительно увеличивает объем вычислений.
Поэтому в 2002 году Перлин сам представил новый метод расчета градиентного шума, названный Симплексный шум. Симплексный шум предлагается для решения задачи экспоненциального увеличения расчетного количества шума Перлина в высоких широтах, решение которого заключается в превращении квадратной сетки в треугольную. Например, для 2D-графики существует 4 квадратных сетки шума Perlin, но есть только 3 сетки треугольных сеток для симплекс-шума, для 3D-графики есть 8 квадратных сеток шума Perlin, но для Simplex Noise Треугольная сетка имеет только 4 точки сетки (ее сетка представляет собой правильную треугольную пирамиду), для n-мерной графики есть 2 ^ n квадратных точек сетки для шума Перлина, но треугольная сетка для симплексного шума имеет только n + 1 точек сетки.
Поэтому в следующей статье я, вероятно, постараюсь сделать симплексный шум и копать
На конференции GDC 2017 выступил Шон Мюррей (Sean Murray), создатель No Man's Sky — игры c процедурной генерацией контента. Он рассказал, как это работает на конкретных математических примерах.
DTF публикует пересказ выступления.
Мюррей начинал в студии Criterion, сейчас принадлежащей EA. Тогда она славилась своими движками и технологиями. В основном Мюррей писал код. Потом он трудился над Burnout Paradise и Black, получившими (особенно за графику) хорошие отзывы.
Отдельно стоит упомянуть, что Мюррей участвовал в создании движка Renderware — он использовался в GTA, Call of Duty, Bully и других проектах. Разработчик даже оставил в них что-то вроде «авторской подписи»: баг, из-за которого у персонажей при определённых условиях отваливались руки.
По мнению Шона, движок игры определяет её дизайн. Сам выбор «мотора» — первый шаг в геймдизайне. К началу разработки No Man’s Sky Мюррей успел поучаствовать в создании семи игровых движков, так что и для неё решил сделать собственный.
Поначалу работа над No Man’s Sky была для него просто увлечением. Но существовавшие игровые движки казались слишком скучными, и он захотел сделать нечто принципиально новое.
No Man’s Sky перестала быть хобби после выхода первого трейлера. На момент выпуска видео игра настолько отличалась от всего, что было на рынке, что разработчикам было негде искать примеры решения проблем.
А их было немало: создание 3D-ландшафта с пещерами и нависающими частями, процедурное текстурирование, леса, строения и существа, горы высотой в несколько километров, планеты площадью в миллионы квадратных километров, разнообразные формы планет, NPC под управлением ИИ, способные путешествовать между небесными телами. К тому же, контент генерировался процедурно, так что его невозможно было протестировать.
В No Man’s Sky нельзя ничего «запечь» или рассчитать заранее. Простой пример: в любой другой игре, чтобы поставить маркер на крышу здания, достаточно расположить на карте строение, создать маркер и переместить его. А в No Man’s Sky движок должен учитывать изгиб планеты, иначе здание может оказаться под землёй или на другом её конце. Затем нужно разместить маркер на горизонте, потому что иначе его не будет видно. При этом ось Y не обозначает «высоту», поскольку планета — это реальный физический объект, так что нужно высчитывать тангенсы и касательные, а также расстояние до полюса планеты.
Итак, маркер на нужной высоте. Но что, если его нужно поставить на другую планету? Или, что ещё хуже, на её обратную сторону? А если между планетой игрока и планетой с маркером окажется ещё одна? Маркер должен всегда быть на горизонте и менять своё положение с изменением точки обзора.
При этом здания в этот момент вообще не существует, поскольку оно, как и всё остальное, генерируется процедурно. Так что движок ищет ближайшее строение необходимого типа, для чего нужно начать генерировать местоположение зданий, что тоже сложный процесс, поэтому включается многопоточность.
Затем нужно сгенерировать основы ландшафта, на котором стоят эти здания. И это тоже сложный процесс, так что приходится вводить дополнительные переменные. Потом нужно учитывать, может ли здание находиться в этом месте — может быть, оно под водой или на слишком крутом склоне. Словом, процесс очень сложный, а ведь речь только о маркерах и зданиях.
Но Мюррею нравится работать со всеми этими проблемами. No Man’s Sky стала идеальным полем экспериментов для человека, которому наскучила стандартная разработка движков.
No Man’s Sky — одновременно большая и маленькая игра. Во время релиза объём билда, скачиваемого в Steam, составлял всего два гигабайта, полтора из которых ушло на аудиоматериалы. Движок, отвечающий за весь мир игры, «весил» примерно 300 мегабайт. Отчасти из-за низкого объёма исходных файлов Мюррей считает процедурную генерацию очень перспективной сферой для веб-игр.
Проект разрабатывала небольшая команда — в среднем над ним единовременно работало шесть человек.
Сначала генерируется шум, то есть части ландшафта, население планет и так далее. Затем это превращается в воксели и полигонизируется, после чего рендерится и обсчитывается физически.
Главной проблемой (и одновременно — целью) было создание разнообразных миров, которые удивляли бы людей и даже своего создателя, но были бы играбельными и предсказуемыми — нужно было понимать, сколько памяти они будут занимать.
Впервые Мюррей попытался решить эту проблему, скопировав Minecraft (популярный подход в то время). Он использовал тот же метод генерации мира: трилинейное фильтрованное поле шума Перлина низкой плотности.
Поскольку разработчик хотел, чтобы игра выглядела реалистично, этот способ в итоге не подошёл — он хорошо подходит только генерации миров из кубиков.
При написании данной статьи я не делал своей целью перевод англоязычных статей на эту тему, которых я перечитал довольно много в интернете или создание супер-мега-классного плагина для 3DSM с классной фотореалистичной графикой облаков, которая тем не менее рендерится минут 5, я хотел сделать динамичные красивые облака (возможно даже фейковые), которые можно использовать в играх , не сильно влияя на ФПС.
В этой статье я расскажу о 2-мерном случае, но это можно легко расширить до n-мерного случая. Шум Перлина использует псевдо-рандомный генератор случайных чисел, который возвращает число от –1 до 1 по заданных параметрах
Причем это число постоянное для конкретных параметров.
Обратите внимание на количество параметров, их 2 поскольку шум двухмерный, но их может быть и 1, и 3 и больше. Постарайтесь это понять, так что функция возвращает для 2-х параметров число в плоскости, для трех в пространстве и. т.д., может это и неверно с математической точки зрения, но именно это помогло мне понять “How does it work”.
Следующей важнейшей вещью есть формула интерполяции, которая используется для сглаживания значений шума. Чаще всего эта функция принимает 3 параметра – a и b – два параметра, между которыми мы производим интерполяцию и х – число от 0 до 1, от которого и зависит результат. Если х=0, то возвращается a, если х=1, возвращается b, в ином случае возвращается некоторое значение между а и b.
Есть несколько формул, которые мы можем использовать, но те которые дают хорошие результаты используют больше системных ресурсов. Наиболее популярной формулой есть
result= a*(1-x) + b*x
Есть еще формула кубической интерполяции, но ввиду того, что облака генерируется в рилтайме, а ее результаты ввиду своей ресурсоемкости не сильно отличаются от косинусной интерполяции, я ее здесь не навожу.
И также функция сглаживания, которая возвращает цвет пикселя в зависимости от исходного цвета и цвета соседних пикселей :
В следующей функции, основной с точки зрения определения параметров текстуры, мы познакомимся с несколькими новыми понятиями. Октава – каждая выполненная функция шума. Дело в том что каждая последующая функция шума принимает удвоенное значение частоты, вспомните уроки пения :) ). Persistence (настойчивость, инерционность), от этого и зависит как бы насыщенность облаков и значение амплитуды.
Пример интересных текстур:
Следующая функция принимает массив, который она заполняет шумом исходя из размера(псевдокод)
Читайте также: