Симплексный шум

Симплексный шум является результатом n -мерной шумовой функции, сравнимой с шумом Перлина («классическим» шумом), но с меньшим количеством направленных артефактов , в более высоких размерностях и с меньшими вычислительными затратами. Кен Перлин разработал алгоритм в 2001 году. ^[1] чтобы устранить ограничения его классической функции шума, особенно в высших измерениях.

Преимущества симплексного шума перед шумом Перлина:

Симплексный шум имеет меньшую вычислительную сложность и требует меньшего количества умножений.
Симплексный шум масштабируется до более высоких измерений (4D, 5D) с гораздо меньшими вычислительными затратами: сложность $O(n^{2})$ для $n$ размеры вместо $O(n\,2^{n})$ классического нойза. ^[2]
Симплексный шум не имеет заметных направленных артефактов (визуально изотропен ), хотя шум, генерируемый для разных измерений, визуально различен (например, 2D-шум выглядит иначе, чем 2D-срезы 3D-шума, и он выглядит все хуже для более высоких измерений). ^[3]).
Симплексный шум имеет четко определенный и непрерывный градиент (почти) везде, который можно вычислить довольно дешево.
Симплексный шум легко реализовать аппаратно.

В то время как классический шум интерполирует градиенты в окружающих конечных точках гиперсетки (т. е. северо-восток, северо-запад, юго-восток и юго-запад в 2D ^{[ нужна ссылка ]}), симплексный шум делит пространство на симплексы (т. е. $n$ -мерные треугольники). Это уменьшает количество точек данных. В то время как гиперкуб в $n$ размеры имеет $2^{n}$ углы, симплекс в $n$ размеры имеет только $n+1$ углы. Треугольники равносторонние в 2D, но в более высоких измерениях симплексы являются лишь приблизительно правильными. Например, замощение в трехмерном случае функции представляет собой ориентацию тетрагональных дисфеноидных сот .

Симплексный шум полезен для приложений компьютерной графики, где шум обычно вычисляется по 2, 3, 4 или, возможно, 5 измерениям. Для более высоких размерностей n -сфер вокруг n - углов симплекса упакованы недостаточно плотно, что снижает поддержку функции и делает ее нулевой на больших участках пространства.

Подробности алгоритма

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

Координатный перекос

Входная координата преобразуется по формуле

x'=x+(x+y+\cdots )\cdot F,

y'=y+(x+y+\cdots )\cdot F,

\cdots ,

где

F={\frac {{\sqrt {n+1}}-1}{n}}.

Это приводит к размещению координаты на букве A. ^*
_n- решетка, которая по сути представляет собой расположение вершин , гиперкубической соты сжатой вдоль ее главной диагонали до расстояния между точками (0, 0, ..., 0) и (1, 1, ..., 1) становится равным расстоянию между точками (0, 0, ..., 0) и (1, 0, ..., 0).

Полученная координата ( x ' , y ' , ...) затем используется для определения, в какой асимметричной единичной ячейке гиперкуба находится входная точка, ( x _b ' = Floor( x ' ), y _b ' = Floor( y ' ), ...) и его внутренние координаты ( x _i ' = x ' - x _b ' , y _i ' = y ' - y _b ' , ...).

Упрощенное подразделение

После определения вышеизложенного значения внутренней координаты ( x _i ' , y _i ' , ...) сортируются в порядке убывания, чтобы определить, в каком симплексе перекошенной ортосхемы Шлефли находится точка. Затем полученный симплекс состоит из вершины, соответствующие упорядоченному обходу ребра от (0, 0, ..., 0) до (1, 1, ..., 1), которых имеется n ! возможностей, каждая из которых соответствует одной перестановке координаты. Другими словами, начните с нулевой координаты и последовательно добавляйте единицы, начиная со значения, соответствующего наибольшему значению внутренней координаты, и заканчивая наименьшим.

Например, точка (0,4, 0,5, 0,3) будет лежать внутри симплекса с вершинами (0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1). . Координата y _' является самой большой, поэтому она добавляется первой. Затем следует координата x _i ' и, наконец, z _i ' .

Выбор градиента

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

Следует проявлять осторожность при выборе набора градиентов, чтобы свести к минимуму артефакты направления.

Суммирование ядра

Вклад каждой из n + 1 вершин симплекса учитывается путем суммирования радиально-симметричных ядер, сосредоточенных вокруг каждой вершины. Сначала определяется неперекошенная координата каждой из вершин по обратной формуле

x=x'-(x'+y'+\cdots )\cdot G,

y=y'-(x'+y'+\cdots )\cdot G,

\cdots ,

где

G={\frac {1-1/{\sqrt {n+1}}}{n}}.

Эта точка вычитается из входной координаты, чтобы получить нескошенный вектор смещения. Этот нескошенный вектор смещения используется для двух целей:

Чтобы вычислить экстраполированное значение градиента, используя скалярное произведение .
Чтобы определить д ², квадрат расстояния до точки.

Отсюда суммарный вклад ядра каждой вершины определяется с помощью выражения

{\big (}\max(0,r^{2}-d^{2}){\big )}^{4}\cdot {\big (}\langle \Delta x,\Delta y,\dots \rangle \cdot \langle \operatorname {grad} x,\operatorname {grad} y,\dots \rangle {\big )},

где р ² обычно устанавливается на 0,5 или 0,6: значение 0,5 гарантирует отсутствие разрывов, тогда как значение 0,6 может повысить качество изображения в приложениях, для которых разрывы не заметны; Версия 0.6 использовалась в исходной эталонной реализации Кена Перлина.

Юридический статус

Использование реализаций в 3D и выше для синтеза текстурированных изображений подпадало под действие патента США № 6,867,776 , если алгоритм был реализован с использованием конкретных методов, описанных в любой из заявок на патент, срок действия которого истек 8 января 2022 года.

См. также

Ссылки

^ Кен Перлин, Шумовое оборудование. В примечаниях к курсу SIGGRAPH по затенению в реальном времени (2001), Олано М. (ред.). (pdf)
^ Кен Перлин, Шуметь. На основе доклада, представленного на GDCHardcore (9 декабря 1999 г.). (URL-адрес)
^ «Обработка изображений. Почему увеличение размерности симплексного шума размывает его?» . Обмен стеками компьютерной графики . Проверено 10 марта 2021 г.

Внешние ссылки

[1] Кен Перлин, Шумовое оборудование. В примечаниях к курсу SIGGRAPH по затенению в реальном времени (2001), Олано М. (ред.). (pdf)

[2] Кен Перлин, Шуметь. На основе доклада, представленного на GDCHardcore (9 декабря 1999 г.). (URL-адрес)

[3] «Обработка изображений. Почему увеличение размерности симплексного шума размывает его?» . Обмен стеками компьютерной графики . Проверено 10 марта 2021 г.

[1]

[2]

[3]