Шум Симплекс

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

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

• Симплексный шум имеет меньшую вычислительную сложность и требует меньшего количества умножений.
• Симплексный шум масштабируется до более высоких измерений (4D, 5D) с гораздо меньшими вычислительными затратами: сложность $O(n^{2})$ для $n$ размеров вместо $O(n2^{n})$ для классического шума.
• Симплексный шум не имеет заметных направленных артефактов (визуально изотропен), хотя шум, генерируемый для разных измерений, визуально различен (например, 2D-шум имеет другой вид, чем срезы 3D-шума, и он выглядит все хуже для более высоких измерений).
• Симплексный шум имеет четко определённый и непрерывный градиент (почти) везде, который можно довольно дёшево вычислить.
• Симплексный шум легко реализовать аппаратно. В то время как классический шум интерполируется между градиентами в окружающих конечных точках гиперсетки (то есть На северо-востоке, северо-западе, юго-востоке и юго-западе в 2D), симплексный шум делит пространство на симплексы (то есть, $n$-мерные треугольники). Это уменьшает количество точек данных. В то время как у гиперкуба в $n$ измерениях есть $2^{n}$ углов, у симплекса в $n$ измерениях есть только ${\displaystyle n+}1$ углов. Равносторонние треугольники в 2D, но в более высоких измерениях симплексы только приблизительно правильные. Например, мозаика в трехмерном случае функции — это ориентация тетрагональной дифеноидный соты. Симплексный шум полезен для приложений компьютерной графики, где шум обычно вычисляется по 2, 3, 4 или, возможно, 5 измерениям. Для более высоких измерений n-сфер вокруг n-симплексных углов недостаточно плотно упакованы, что снижает поддержку функции и делает её нулевой в больших частях пространства.

Детали алгоритма

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

Отклонение координат

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

$x'=x+(x+y+\cdots )*F$

$y'=y+(x+y+\cdots )*F$

$\cdots$

где

$\displaystyle F={\frac {{\sqrt {n+1}}-1}{n}}$

Это приводит к размещению координаты на A_n^* решетки, который является по существу расположение вершин из гиперкубической соты, сжатой по главной диагонали до расстояния между точками, пока расстояние между точками (0, 0, …, 0) и (1, 1, …, 1) становится равное расстоянию между точками (0, 0, …, 0) и (1, 0, …, 0). Результирующая координата (x', y', …) затем используется для определения, в какой наклонной ячейке единичного гиперкуба находится входная точка, (xb' =floor (x'), yb'= floor (y'), …) и его внутренние координаты (xi'= x'-xb', yi'= y'-yb', …).

Разделение на симплексы

Как только указанное выше определено, значения внутренней координаты (xi', yi', …) сортируются в порядке убывания, чтобы определить, в каком симплексе ортосхемы Шлефли с перекосом лежит точка. Затем полученный симплекс состоит из вершин соответствующий упорядоченному обходу ребер от (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). Координата yi' самая большая, поэтому она добавляется первой. Затем следует координата xi' и, наконец, zi'.

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

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

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

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

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

${\displaystyle x=x'-(x'+y'+...)*G}$

${\displaystyle y=y'-(x'+y'+...)*G}$

где

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

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

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

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

${\displaystyle (max(0,r^{2}-d^{2}))^{4}*(<\Delta x,\Delta y,...>\cdot <grad.x,grad.y,...>)}$

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

Правовой статус

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

См. также

• Изотропия

Ссылки

• Ken Perlin, Noise hardware. In Real-Time Shading SIGGRAPH Course Notes (2001), Olano M., (Ed.). (pdf)
• Ken Perlin, Making noise. Based on a talk presented at GDCHardcore (Dec 9, 1999). (url)
• Краткая техническая статья с исходным кодом Стефана Густавсона (PDF)
• Анимированная демонстрация симплексного шума «резинового листа» Перлина
• Другая реализация Симплекс шума на C++ (SimplexNoise1234)