Проблема сглаживания алгоритмом Diamond-Square

Гэвин С.П. Миллер выступил на SIGGRAPH '86 с докладом о фундаментальных недостатках исходного алгоритма Фурнье, Фуссела и Карпентера. Итак, то, что вы видите, нормально для любой наивной реализации алгоритма Алмазного квадрата. Вам потребуется отдельный подход для сглаживания, либо опубликуйте каждый составной шаг ромба-квадрата, либо в качестве постобработки для всех итераций ромба-квадрата (или обоих). Миллер обратился к этому. Взвешивание и прямоугольная или гауссовская фильтрация являются одним из вариантов; заполнение исходного массива в большей степени, чем только начальные 4 точки (т. е. воспроизведение наборов результатов первых нескольких шагов ромбовидного квадрата либо вручную, либо с использованием некоторого встроенного интеллекта, но вместо этого предоставление несмещенных значений); чем больше исходной информации вы дадите массиву перед увеличением детализации с помощью алмазного квадрата, тем лучше будут ваши результаты.

Причина, по-видимому, в том, как выполняется квадратный шаг. На шаге «ромб» мы взяли среднее значение четырех углов квадрата, чтобы получить центр этого квадрата. Затем, на следующем шаге Square, мы берем среднее значение четырех ортогонально соседних соседей, один из которых является центральной точкой квадрата, который мы только что создали. Вы видите проблему? Эти первоначальные значения высоты угла слишком сильно влияют на последующую итерацию ромбовидного квадрата, потому что они вносят свой вклад как за счет своего собственного влияния, так и за счет созданной ими средней точки. Это вызывает шпили (экструзивные и интрузивные), потому что локальные точки имеют более сильную тенденцию к этим ранним точкам... и поскольку (обычно 3) другие точки делают то же самое, это создает "круговые" влияния вокруг этих точек, когда вы итерируете на большие глубины с помощью Diamond-Square. Таким образом, эти виды проблем с «алиасингом» появляются только тогда, когда начальное состояние массива не определено; на самом деле возникающие артефакты можно рассматривать как прямое геометрическое следствие использования только 4 точек для начала.

Вы можете сделать одно из следующих действий:

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

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

В вашем коде изменение высоты пропорционально r, поэтому вы должны сохранить его пропорциональным размеру вашего текущего размера сетки. Другими словами: умножьте r на шероховатость перед циклом и разделите r на 2 на каждой итерации.

Итак, вместо

r = r / Roughness;

ты должен написать

r = r / 2;

Фактическим недостатком вышеприведенного алгоритма является ошибка в концептуализации и реализации. Алмазный квадрат как алгоритм имеет некоторые артефакты, но это артефакты, основанные на диапазоне. Таким образом, технический максимум для некоторых пикселей выше, чем для некоторых других пикселей. Некоторым пикселям напрямую присваиваются значения в результате случайности, в то время как другие получают свои значения с помощью процессов интерполяции средней точки ромба и квадрата.

Ошибка здесь в том, что вы начали с нуля. И неоднократно добавлял значение к текущему значению. Это приводит к тому, что диапазон квадрата ромба начинается с нуля и расширяется вверх. На самом деле он должен начинаться с нуля и идти как вверх, так и вниз в зависимости от случайности. Так что высший диапазон не имеет значения. Но если вы этого не понимаете и наивно реализуете все как добавленное к значению, а не начинаете с нуля и колеблетесь оттуда, вы обнаружите скрытые артефакты.

Заметки Миллера были правильными, но недостаток обычно скрывается в шуме. Эта реализация показывает эти проблемы. Это НЕ нормально. И исправить можно несколькими способами. Это была одна из причин, почему после того, как я расширил этот алгоритм, убрав все ограничения памяти и ограничения размера и сделав его бесконечным и детерминированным1, я тогда еще отошел от основной идеи здесь (проблемы с расширением на 3d и оптимизацией под GPU тоже сыграли свою роль.2

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