Проблема сглаживания с алгоритмом Diamond-Square
Я использую алгоритм алмазного квадрата для генерации случайной местности. Это работает хорошо, за исключением того, что я получаю эти большие конические формы, торчащие из или в местности. Проблема, кажется, в том, что время от времени точка устанавливается слишком высоко или слишком низко.
Вот картина проблемы
И это может быть лучше видно, когда я установил действительно высокую плавность
И вот мой код -
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;
}
}
4 ответа
Гевин С.П. Миллер выступил с докладом SIGGRAPH '86 о том, как оригинальный алгоритм Фурнеля, Фасселя и Карпентера был в корне ошибочным. То, что вы видите, является нормальным для любой наивной реализации алгоритма Diamond Square. Вам потребуется отдельный подход для сглаживания: либо опубликовать каждый составной шаг с ромбовидным квадратом, либо в качестве последующей обработки на всех итерациях с ромбовидным квадратом (или обоих). Миллер обратился к этому. Взвешивание и блочная или гауссова фильтрация - один из вариантов; заполнение исходного массива в большей степени, чем просто начальные 4 точки (то есть, репликация наборов результатов первых нескольких шагов алмазного квадрата либо вручную, либо с использованием некоторого встроенного интеллекта, но вместо этого предоставление несмещенных значений); чем больше исходной информации вы передадите массиву, прежде чем увеличивать детализацию с помощью ромбовидной формы, тем лучше будут ваши результаты.
Кажется, причина в том, как выполняется шаг Square. На шаге Diamond мы взяли среднее значение четырех углов квадрата, чтобы получить центр этого квадрата. Затем на следующем шаге квадрата мы берем среднее значение четырех соседних ортогонально соседей, один из которых является центральной точкой квадрата, которую мы только что создали. Вы видите проблему? Эти исходные значения высоты угла вносят слишком большой вклад в последующую итерацию квадрата бриллианта, поскольку они вносят свой вклад как через свое собственное влияние, так и через созданную ими среднюю точку. Это приводит к появлению шпилей (экструзионных и навязчивых), потому что локально полученные точки имеют более сильную тенденцию к этим ранним точкам... и поскольку (как правило, 3) другие точки также делают это, это создает "круговые" влияния вокруг этих точек, когда вы выполняете итерацию на большие глубины, используя Diamond-Square. Таким образом, подобные проблемы с "псевдонимами" появляются только тогда, когда начальное состояние массива не указано; фактически возникновение артефакта можно рассматривать как прямое геометрическое следствие использования только 4 точек для начала.
Вы можете сделать одно из следующего:
- Делать локальную фильтрацию - вообще дорого.
- Предварительно отсеять начальный массив более тщательно - требует некоторого интеллекта.
- Никогда не сглаживайте слишком много шагов вниз от заданного набора начальных точек - что применимо, даже если вы начнете заполнять исходный массив, это всего лишь вопрос относительной глубины в сочетании с вашими собственными параметрами максимального смещения.
Я считаю, что размер смещения r в каждой итерации должен быть пропорционален размеру текущего прямоугольника. Логика этого заключается в том, что фрактальная поверхность масштабно инвариантна, поэтому изменение высоты в любом прямоугольнике должно быть пропорционально размеру этого прямоугольника.
В вашем коде изменение высоты пропорционально r, поэтому вы должны держать его пропорционально размеру вашего текущего размера сетки. Другими словами: умножьте r на шероховатость перед циклом и разделите r на 2 в каждой итерации.
Итак, вместо
r = r / Roughness;
ты должен написать
r = r / 2;
Вместо того, чтобы просто сглаживать среднее значение, вы можете использовать двухмерный медианный фильтр, чтобы вывести крайние значения. Он прост в реализации и обычно генерирует желаемый эффект с большим количеством шума.
Фактическим недостатком вышеупомянутого алгоритма является ошибка в концептуализации и реализации. Алмазный квадрат как алгоритм имеет некоторые артефакты, но это артефакты, основанные на расстоянии. Таким образом, технический максимум для некоторых пикселей выше, чем для некоторых других пикселей. Некоторым пикселям присваиваются значения по случайности, в то время как другие получают свои значения в процессе интерполяции ромбовидной и квадратной срединной точки.
Ошибка здесь в том, что вы начали с нуля. И неоднократно добавлял значение к текущему значению. Это приводит к тому, что диапазон квадрата алмаза начинается с нуля и расширяется вверх. На самом деле он должен начинаться с нуля и идти как вверх, так и вниз в зависимости от случайности. Так что вещь верхнего диапазона не будет иметь значения. Но, если вы не понимаете этого и наивно реализуете все как добавленное к значению, а не начинаете с нуля и не колеблетесь оттуда, вы обнаружите скрытые артефакты.
Записи Миллера были правы, но недостаток обычно скрыт в шуме. Эта реализация показывает эти проблемы. Это НЕ нормально. И можно исправить несколькими разными способами. Это было одной из причин, почему после того, как я расширил этот алгоритм, чтобы убрать все ограничения памяти и ограничения размера и сделал его бесконечным и детерминированным 1, я все же отказался от основной идеи (проблемы с расширением его до 3d и оптимизацией для графических процессоров). также сыграло свою роль. 2
