Введение

Метод генерации карт высот для компьютерной графики

Алгоритм "алмаз-квадрат" — это метод генерации карт высот для компьютерной графики. Он является несколько более эффективным алгоритмом, чем трёхмерная реализация алгоритма смещения середины, который создаёт двухмерные ландшафты. Он также известен как фрактал случайного смещения середины, облачный фрактал или плазменный фрактал из-за эффекта плазмы, возникающего при его применении. Идея была впервые представлена Фурнье, Фусселом и Карпентером на SIGGRAPH в 1982 году. Алгоритм "алмаз-квадрат" начинается с двумерной сетки, а затем случайным образом генерирует высоту рельефа из четырёх начальных значений, расположенных в виде сетки точек, так, чтобы вся плоскость была покрыта квадратами.

Описание

Алгоритм алмазного квадрата начинается с двухмерного квадратного массива шириной и высотой 2n + 1. Четыре угловые точки массива должны быть сначала заданы начальными значениями. Затем шаги "алмаз" и "квадрат" выполняются поочередно, пока не будут заданы все значения массива. Шаг "алмаз": для каждого квадрата в массиве задайте середину этого квадрата как среднее арифметическое четырех угловых точек плюс случайное значение. Шаг "квадрат": для каждого "алмаза" в массиве задайте середину этого "алмаза" как среднее арифметическое четырех угловых точек плюс случайное значение. Каждое случайное значение умножается на масштабный коэффициент, который уменьшается с каждой итерацией в 2−h раз, где h – значение между 0.0 и 1.0 (меньшие значения создают более шероховатую поверхность). Во время шагов "квадрат" точки, расположенные на границах массива, будут иметь только три соседних заданных значения, а не четыре. Существует несколько способов решения этой проблемы – самый простой заключается в вычислении среднего арифметического только из этих трех соседних значений. Другой вариант – использовать "замыкание", беря четвертое значение с противоположной стороны массива. При использовании согласованных начальных значений углов этот метод также позволяет объединять сгенерированные фракталы без разрывов.

Визуализация

На изображении ниже показаны шаги выполнения алгоритма «алмазный квадрат» для массива 5 × 5.

Приложения

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

Артефакты и расширения

Алгоритм алмазного квадрата был проанализирован Гэвином С. П. Миллером на SIGGRAPH 1986 года, который описал его как имеющий недостатки, поскольку алгоритм создает заметные вертикальные и горизонтальные "складки" из-за того, что наибольшие возмущения происходят в прямоугольной сетке. Артефакты сетки были устранены в обобщенном алгоритме, представленном Дж. П. Льюисом. В этом варианте веса соседних точек определяются путем решения небольшой линейной системы, основанной на теории оценки, а не задаются фиксированными значениями. Алгоритм Льюиса также позволяет синтезировать не фрактальные карты высот, такие как пологие холмы или океанские волны. С помощью синтеза Фурье можно эффективно получить аналогичные результаты, хотя теряется возможность адаптивного уточнения. Алгоритм алмазного квадрата и его усовершенствования рассматриваются в книге Пейтгена и Саупа "Наука фрактальных изображений".