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

Question

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

Вот изображение проблемы

И это может быть лучше видно, когда я установил очень высокую плавность

А вот и мой код -

private void CreateHeights()
    {
        if (cbUseLand.Checked == false) 
            return;
        int
            Size = Convert.ToInt32(System.Math.Pow(2, int.Parse(tbDetail.Text)) + 1),
            SideLength = Size - 1,
            d = 1025 / (Size - 1),
            HalfSide;
        Heights = new Point3D[Size, Size];
        float
            r = float.Parse(tbHeight.Text),
            Roughness = float.Parse(RoughnessBox.Text);

        //seeding all the points
        for (int x = 0; x < Size; x++)
            for (int y = 0; y < Size; y++)
                Heights[x, y] = Make3DPoint(x * d, 740, y * d);

        while (SideLength >= 2)
        {
            HalfSide = SideLength / 2;

            for (int x = 0; x < Size - 1; x = x + SideLength)
            {
                for (int y = 0; y < Size - 1; y = y + SideLength)
                {
                    Heights[x + HalfSide, y + HalfSide].y =
                      (Heights[x, y].y +
                      Heights[x + SideLength, y].y +
                      Heights[x, y + SideLength].y +
                      Heights[x + SideLength, y + SideLength].y) / 4 - r + ((float)(random.NextDouble() * r) * 2);
                }
            }

            for (int x = 0; x < Size - 1; x = x + SideLength)
            {
                for (int y = 0; y < Size - 1; y = y + SideLength)
                {
                    if (y != 0)
                        Heights[x + HalfSide, y].y = (Heights[x, y].y + Heights[x + SideLength, y].y + Heights[x + HalfSide, y + HalfSide].y + Heights[x + HalfSide, y - HalfSide].y) / 4 - r + ((float)(random.NextDouble() * r) * 2); 
                    if (x != 0)
                        Heights[x, y + HalfSide].y = (Heights[x, y].y + Heights[x, y + SideLength].y + Heights[x + HalfSide, y + HalfSide].y + Heights[x - HalfSide, y + HalfSide].y) / 4 - r + ((float)(random.NextDouble() * r) * 2);
                }
            }
            SideLength = SideLength / 2;
            r = r / Roughness;
        }
    }

Answer 1

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

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

Можно выполнить одно из следующих действий:

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

Итак, вместо

r = r / Roughness;

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

r = r / 2;