Каково качество случайности алгоритмов Perlin/Simplex Noise?
Каково качество случайности алгоритма Perlin Noise и Simplex Noise?
Какой алгоритм из двух имеет лучшую случайность?
Имеет ли смысл использовать Perlin/Simplex в качестве генератора случайных чисел по сравнению со стандартными псевдослучайными генераторами?
Обновление: я знаю, для чего используется шум Perlin/Simplex. Мне только любопытно свойства случайности.
3 ответа
Как указано в "Статистике случайных чисел", AI Game Wisdom 2, вопрос о том, какая случайность дает "лучшую" случайность, зависит от того, для чего вы ее используете. Как правило, качество PRNG сравнивается с помощью тестовых батарей. На момент публикации автор указывает, что наиболее известными и наиболее широко используемыми тестовыми батареями для проверки случайности PRNG являются ЛОР и Diehard. Также см. Связанные вопросы о том, как тестировать случайные числа и почему статистические тесты на случайность кажутся специальными.
Помимо стандартных проблем тестирования типичных PRNG, тестирование Perlin Noise или Simplex Noise в качестве PRNG более сложное, потому что:
- Оба внутренне требуют PRNG, таким образом, на случайность их выхода влияет основной PRNG.
- Большинство PRNG не имеют настраиваемых параметров. Напротив, шум Перлина является суммированием одной или нескольких функций когерентного шума (октав) с постоянно увеличивающимися частотами и постоянно уменьшающимися амплитудами. Поскольку окончательное изображение зависит от количества и характера используемых октав, качество случайности будет соответственно меняться. libnoise: изменение параметров модуля Noise
- Аргумент, аналогичный #2, справедлив для изменения количества измерений, используемых в симплексном шуме, поскольку "трехмерная часть симплексного шума 4D отличается от трехмерного симплексного шума". Симплексный шум Стефана Густавсона демистифицирован.
Шум Перлина и симплексный шум предназначены для создания полезного шума, а не для того, чтобы быть полностью случайным. Эти алгоритмы обычно используются для создания процедурно сгенерированных ландшафтов и т.п. Например, он может генерировать ландшафт, такой как этот (изображение отсюда):
На этом изображении шум генерирует двухмерную карту высот, такую как эта (изображение отсюда):
Цвет каждого пикселя представляет высоту. После создания карты высот средство визуализации используется для создания ландшафта, соответствующего "высотам" (цветам) изображения.
Следовательно, результаты алгоритма не являются "случайными"; как вы можете видеть, существует множество легко различимых шаблонов.
Симплекс, предположительно, выглядит немного "лучше", что подразумевает меньшую случайность, но его основная цель заключается в том, что он производит похожий шум, но лучше масштабируется до более высоких размеров. То есть, если бы мы производили 3D,4D,5D шум, симплексный шум превосходил бы шум Перлина и давал бы аналогичные результаты.
Если вам нужен обычный генератор псевдослучайных чисел, посмотрите на твистер Мерсенна или другие prngs. Будьте осторожны, по отношению к криптографии, prngs могут быть полны предостережений.
Обновить:
(ответ на ОП обновленный вопрос)
Что касается случайных свойств этих шумовых функций, я знаю, что перлин-шум использует входной сигнал (очень) плохого человека и выполняет некоторое сглаживание / интерполяцию между соседними "случайными" пикселями. Входная случайность - это просто псевдослучайное индексирование в предварительно вычисленный случайный вектор.
Индекс вычисляется с использованием простых целочисленных операций, ничего особенного. Например, проект noise++ использует предварительно вычисленные "randomVectors" (см. Здесь) для получения исходного шума и интерполирует различные значения из этого вектора. Он генерирует "случайный" индекс в этот вектор с помощью нескольких простых целочисленных операций, добавляя небольшое количество псевдослучайности. Вот фрагмент:
int vIndex = (NOISE_X_FACTOR * ix + NOISE_Y_FACTOR * iy + NOISE_Z_FACTOR * iz + NOISE_SEED_FACTOR * seed) & 0xffffffff;
vIndex ^= (vIndex >> NOISE_SHIFT);
vIndex &= 0xff;
const Real xGradient = randomVectors3D[(vIndex<<2)];
...
Несколько случайный шум затем сглаживается и фактически смешивается с соседними пикселями, создавая шаблоны.
После создания начального шума перлин / симплексный шум имеет понятие октав шума; то есть, повторно смешивая шум в себя в различных масштабах. Это производит еще больше скороговорок. Таким образом, исходное качество шума, вероятно, так же хорошо, как предварительно вычисленные случайные массивы, плюс эффект псевдослучайной индексации. Но после всего того, что делает с этим шум перлина, кажущаяся случайность значительно уменьшается (я думаю, что она действительно распространяется на более широкую область).
Я думаю, что вы в замешательстве.
Perlin и Simplex берут случайные числа из какого-то другого источника и делают их менее случайными, чтобы они больше походили на природные ландшафты (одни только случайные числа не похожи на природные ландшафты).
поэтому они не являются источником случайных чисел - они являются способом обработки случайных чисел откуда-то еще.
и даже если бы они были источником, они не были бы хорошим источником (цифры сильно коррелируют).
НЕ используйте перлин или симплекс для случайности. они не предназначены для этого. они / приложение / случайности.
люди выбирают их из-за их визуальной привлекательности, которая еще недостаточно обсуждалась, поэтому я сосредоточусь на этом.
perlin / simplex с smoothstep идеально гладкие. независимо от того, насколько сильно вы увеличиваете масштаб, они всегда будут градиентом, а не вершиной или ребром.
диапазон вывода составляет (+/- 1/2 x #dimensions), поэтому вам необходимо компенсировать это, чтобы получить диапазон от 0 до 1 или от -1 до 1 по мере необходимости. это стандартное исправление. добавление октав увеличит этот диапазон на коэффициент масштабирования октавы (обычно это половина большей октавы, конечно).
Перлин / симплексный шум имеет странное качество коричневого шума при увеличении и синего шума при уменьшении. Ни один, ни средний зум не особенно подходят для целей prng, но они отлично подходят для имитации естественных явлений (которые на самом деле не случайны и / имеют / пространственно смещены).
как перлин, так и симплексный шум имеют тенденцию иметь некоторое смещение по осям, и у перлина есть еще несколько проблем в этой области. edit: уйти от еще большей предвзятости в трех измерениях очень сложно. сложно (невозможно?) создать на сфере большое количество несмещенных точек.
Результаты Perlin имеют тенденцию быть круглыми с восьмиугольным смещением, в то время как симплексный метод имеет тенденцию генерировать овалы с шестиугольным смещением.
срез симплекса более высокой размерности не похож на симплекс более низкой размерности. но 2d фрагмент 3d perlin выглядит почти так же, как 2d perlin.
Большинство людей считают, что симплекс не может обрабатывать более высокие измерения - он имеет тенденцию "выглядеть все хуже и хуже" для более высоких измерений. Перлин якобы не имеет этой проблемы (хотя он все еще имеет предвзятость).
Я считаю, что после "октавирования" они оба имеют одинаковое треугольное распределение вывода при наложении (похоже на бросание двух кубиков) (люблю, если бы кто-то мог дважды проверить это для меня.) и поэтому оба выигрывают от плавного шага. это стандарт. (можно смещать результаты для равного вывода, но при этом все равно будут иметь место смещения размеров, которые не пройдут тесты качества prng из-за высокой пространственной корреляции, которая является / функцией /, а не ошибкой.)
обратите внимание, что техника октав не является частью определения перлина или симплекса. это просто уловка, часто используемая вместе с ними. градиенты перлина и симплекса смешиваются в равномерно распределенных точках. октавы этого шума объединяются для создания больших и меньших структур. это также часто используется в "шуме значений", который использует в основном белый шум, эквивалентный этой концепции, вместо шума Перлина. Величина шума с октавами также будет демонстрировать (даже хуже) восьмиугольное смещение. поэтому предпочтительны перлин или симплекс.
симплекс быстрее во всех случаях - / особенно / в более высоких измерениях.
so simplex решает проблемы Perlin как с производительностью, так и с визуализацией, но вносит свои собственные проблемы.