Алгоритм ромба-квадрата

Анимированный плазменный фрактал с циклическим изменением цвета

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

Идея была впервые предложена Фурнье , Фасселлом и Карпентером в SIGGRAPH в 1982 году. ^[1]

Алгоритм «ромб-квадрат» начинается с двумерной сетки, затем случайным образом генерирует высоту местности из четырех начальных значений, расположенных в сетке точек так, чтобы вся плоскость была покрыта квадратами.

Описание

Алгоритм «ромб-квадрат» начинается с двумерного квадратного массива шириной и высотой 2. ^н + 1. Для четырех угловых точек массива сначала необходимо установить начальные значения.Затем шаги ромба и квадрата выполняются поочередно, пока не будут установлены все значения массива.

Шаг ромба: для каждого квадрата в массиве установите среднюю точку этого квадрата как среднее арифметическое четырех угловых точек плюс случайное значение.
Шаг квадрата: для каждого ромба в массиве установите среднюю точку этого ромба как среднее арифметическое четырех угловых точек плюс случайное значение.

Каждое случайное значение умножается на масштабную константу, которая уменьшается с каждой итерацией в 2 раза. ^−ч, где h — значение от 0,0 до 1,0 (более низкие значения создают более пересеченную местность). ^[2]

Во время квадратных шагов для точек, расположенных на краях массива, будут установлены только три соседних значения, а не четыре. Есть несколько способов справиться с этой сложностью: самый простой — взять среднее значение только трех соседних значений. Другой вариант — «перейти», взяв четвертое значение с другой стороны массива. При использовании с постоянными начальными значениями углов этот метод также позволяет сшивать сгенерированные фракталы без разрывов.

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

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

Приложения

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

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

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

Ссылки

^ Фурнье, Ален; Фассел, Дон; Карпентер, Лорен (июнь 1982 г.). «Компьютерная визуализация стохастических моделей» . Коммуникации АКМ . 25 (6): 371–384. дои : 10.1145/358523.358553 . ISSN 0001-0782 .
^ «Генерация случайного фрактального ландшафта» . 20 апреля 2006 г. Архивировано из оригинала 20 апреля 2006 г. Проверено 13 декабря 2022 г.
^ Миллер, Гэвин С.П. (август 1986 г.). «Определение и отрисовка карт местности». ACM SIGGRAPH Компьютерная графика . 20 (4): 39–48. дои : 10.1145/15886.15890 .
^ Льюис, JP (1 июля 1987 г.). «Обобщенное стохастическое подразделение». Транзакции ACM с графикой . 6 (3): 167–190. CiteSeerX 10.1.1.21.3719 . дои : 10.1145/35068.35069 . S2CID 14994949 .
^ Jump up to: Перейти обратно: ^а ^б Пейтген, Хайнц-Отто, Дитмар Саупе (1988). Наука фрактальных изображений . Нью-Йорк: Springer-Verlag. ISBN 978-0-387-96608-3 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

Внешние ссылки

Простой модуль карты высот с открытым исходным кодом для Lua, использующий алгоритм ромба-квадрата.
Генерация случайного фрактального ландшафта: алгоритм ромба-квадрата от GameProgrammer.com
Плазменный фрактал с веб-страницы Джастина Сейстера
Плазменные фракталы с домашней страницы Патрика Хана
Учебное пособие по ландшафту от Lighthouse3d.com
Случайное смещение средней точки с помощью холста
Метод случайного смещения средней точки
Алгоритм ромба и квадрата на Github (PHP)
Пример тестирования реализации алгоритма в блоге дяди Боба Clean Coder.
Xmountains Классическая реализация X11 с боковой прокруткой . Подробности алгоритма .
Реализация Python , короткая и понятная. Обрабатывает как фиксированные, так и периодические граничные условия.

[fournier-1] Фурнье, Ален; Фассел, Дон; Карпентер, Лорен (июнь 1982 г.). «Компьютерная визуализация стохастических моделей» . Коммуникации АКМ . 25 (6): 371–384. дои : 10.1145/358523.358553 . ISSN 0001-0782 .

[2] «Генерация случайного фрактального ландшафта» . 20 апреля 2006 г. Архивировано из оригинала 20 апреля 2006 г. Проверено 13 декабря 2022 г.

[miller-3] Миллер, Гэвин С.П. (август 1986 г.). «Определение и отрисовка карт местности». ACM SIGGRAPH Компьютерная графика . 20 (4): 39–48. дои : 10.1145/15886.15890 .

[4] Льюис, JP (1 июля 1987 г.). «Обобщенное стохастическое подразделение». Транзакции ACM с графикой . 6 (3): 167–190. CiteSeerX 10.1.1.21.3719 . дои : 10.1145/35068.35069 . S2CID 14994949 .

[PeitgenSaupe-5] Jump up to: Перейти обратно: ^а ^б Пейтген, Хайнц-Отто, Дитмар Саупе (1988). Наука фрактальных изображений . Нью-Йорк: Springer-Verlag. ISBN 978-0-387-96608-3 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[1]

[2]

[3]

[4]

[5]