Трехмерными ландшафтами сегодня в компьютерных играх уже давно никого не удивишь. Вспомнить хотя бы такие игры как WarHammer: Dark Omen, Аллоды 3, или какую-нибудь современную стратегию в 3D. А задумывались ли вы, как эти ландшафты представляются в компьютере, строятся в памяти или отрисовываются на экране монитора? В данной статье я постараюсь рассмотреть тему построения трехмерных ландшафтов, некоторые концепции и идеи.

Первым пунктом мы коснемся способов представления данных о структуре ландшафта на компьютере. Потом проанализируем различные алгоритмы построения (генерации) ландшафтов. И, напоследок, речь пойдет об алгоритмах и приемах визуализации уже построенных ландшафтов. Ну что, поскакали?

Существует несколько основных принципов представления данных для хранения информации о ландшафтах:

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

Рассмотрим первый вариант - использование карты высот

Данные представлены в виде двухмерного массива. Уже заданы две координаты (x, y - по высоте и ширине массива), и третья координата задается значением в конкретной ячейке, это высота.

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

Например, вот карта высот и получившийся ландшафт (построено при помощи программы ReLife3D 2 - найти можно на моем сайте):

С помощью этого способа можно представить достаточно обширные пространства. Но у него есть один существенный недостаток - слишком много описаний для точек, а также, в некоторых случаях, наблюдается избыточность данных (например, когда у вас задается простая плоскость, то, в этом случае, для построения простой плоскости будет использоваться множество точек, хотя можно бы было обойтись тремя - надеюсь, геометрию все помнят :-)). Хотя и эта самая избыточность может пойти нам на пользу, например, при вертексном освещении.

У этого метода существует и несколько плюсов:

• наглядность, в любой программе просмотра графических файлов можно сразу увидеть всю информацию;
• простота изменения этих самых данных, так каксуществует множество программ для работы с растровой графикой;
• и еще одно, в таких картах можно хранить не только данные о высоте. Например, предположим, что для хранения высоты мы используем 16 бит, т.е. две цветовые компоненты, это получается 256x256=65536 градаций высоты. Остальные 8 бит мы можем использовать для хранения информации о каких-либо особенностях ландшафта, например, расположение зданий, строений, мостов, растительности и так далее.
• Еще одна идея использования карт высот. Будем хранить, также числовые, значения, но теперь не высот, а блоков (назовем их ландшафтными). Можно заранее создать некоторое количество карт высот небольшого размера (скажем 8x8 или 16x16 пикселей), а в нашей карте блоков высот хранить идентификатор существующего блока. Это дает нам значительно больший размер карты и, следовательно, ландшафта. Правда тут нужно будет обратить особое внимание на места соединения блоков. То есть, получается, что у нас первый способ представления данных для построения ландшафта плавно перекочевал в третий!
• Из некоторых других плюсов можно упомянуть легкость нахождения координат (и высоты!) на карте.
• И еще один плюс - так как вершинные точки расположены регулярно и достаточно близко, можно более правильно и достаточно аккуратно производить динамическое освещение (зачастую, освещенность вершины напрямую зависит от расстояния от этой вершины до источника освещения). Это и есть та самая польза от избыточности данных.

Теперь второй способ - иррегулярная сетка

Еще один способ представления данных для ландшафтов - иррегулярная сетка вершин и связей их соединяющих. Зачастую такие решения применяются в специализированных пакетах для игр (например, редактор уровней для Серьезного дядюшки Сэма) или специальных пакетах для работы с трехмерной графикой (типа 3Dmax, Maya и иже с ними). И хранятся в виде трехмерных моделей. Это дает основной выигрыш по сравнению с картами высот:

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

Но кроме плюсов у этого способа имеется и множество недостатков:

• алгоритмы построения ландшафтов в основном предназначены для регулярных карт высот. Оптимизация таких алгоритмов под этот способ потребует значительных усилий;
• Сложности при динамическом освещении - вершины расположены достаточно далеко друг от друга и неравномерно;
• Хранение, просмотр, модификация такого ландшафта также представляет сложности. При использовании карт высот вы пользуетесь достаточно простыми и "стандартными" средствами пиксельной графики. Хотя бы тем же MS Paint'ом. Тут же вам потребуются более навороченные и "весомые" пакеты.

Да, а вот и картинка изображающая данный принцип:

Способ третий - посегментная карта высот

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

• Возможность представления огромнейших открытых пространств;
• Кроме самих ландшафтов в таких блоках можно хранить и информацию о зданиях, строениях, растениях, специфических ландшафтных решениях (например, пещеры или скалы, нависающие друг над другом);
• Возможность создания нескольких вариантов одного и того же сегмента, но при разной степени детализации. В зависимости от скорости или загруженности компьютера можно выбирать более или менее детализованные варианты (так называемые LOD ландшафты - LOD - Level Of Detail).

Минусов у такого способа тоже хватает:

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

Текстуры для ландшафтов

Текстуры для ландшафтов можно разделить на три части примерно стиалогичным образом.

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

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

При использовании для текстуризации одиночной текстуры, мы имеем два возможных варианта:

• Размер текстуры меньше, либо равен, размеру ландшафта (при этом лучше, чтобы эти размеры были равными, или на худой конец, кратными друг другу).
• Размер текстуры больше размеров ландшафта.

Это дает возможность выбора формата вершин для ландшафта. Во втором случае нам однозначно придется использовать текстурированные вершины. В первом же случае все намного интереснее: мы можем использовать не текстурированные вершины, а окрашенные. При этом текстуру мы используем как ресурс, хранилище информации о цветах конкретных вершин. Это может дать нам большой прирост скорости, а при использовании огромных (именно огромных, а не больших около 500x500 пикселей и более) ландшафтов и текстур позволит добиться большей детализации (хотя в таком случае скорость будет сильно зависеть от размера, ведь при размере в 500 на 500 единиц для хранения ландшафта потребуется 500x500=25000000 вершин умножить на объем памяти для одной вершины равный 36 байт, 12 на три координаты - тип float, + 24 на цвет, тип DWORD. Получаем, что для хранения информации о таком ландшафте нам потребуется 25000000x36=900000000 байт!!! Это примерно 900 мб! При этом ландшафт у нас представлен 49980002 полигонами! Поэтому, пока лучше такими огромными ландшафтами не пользоваться).

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

Сгенерируем ландшафт

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

Вот использованный мной алгоритм:

• Создаем двухмерный массив необходимого размера;
• Генерируем в этот массив (во все ячейки) случайные значения;
• Проходимся простым сглаживающим фильтром:
  • Берем точку (все по порядку);
  • Вокруг этой точки берем значения всех восьми точек + значение выбранной точки;
  • Суммируем все эти девять значений;
  • Делим полученное значение на 9 (количество точек - простое усреднение);
  • Полученный результат записываем в исходную точку;
  • Пробегам весь массив;
• Далее заполняем случайными значениями еще несколько точек в исходном массиве (примерное количество точек всего - tsize*tsize, нужно заполнить tsiza*10 точек), конкретная точка выбирается случайным образом;
• Заново проходимся сглаживающим фильтром.

На что здесь следует обратить внимание. На втором шаге мы заполняем массив случайными значениями - я выбирал их пределы примерно от -300 до +300. В предпоследнем шаге мы опять используем случайные значения - в данном случае я брал их в пределе от -500 до +500. Это позволяет добиться достаточно изрезанного ландшафта. Вот скриншот, показывающий применение этого алгоритма в моей будущей игре:

Это простейший алгоритм, и, я думаю, запрограммировать его проблем не будет.

Теперь рассмотрим еще несколько алгоритмов.

Генерация ландшафтов с использованием Холмового алгоритма (Hill Algoritm)

Это простой итерационный алгоритм, основанный на нескольких входных параметрах. Алгоритм изложен в следующих шагах:

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

Как сгенерировать один холм

Первый, второй и четвертый шаги тривиальны, пятый и шестой мы рассмотрим далее. Теперь же займемся третьим шагом. Что же означает "поднять" холм? Фактически холм - это в нашем случае половина шара, чем больше радиус - тем больше холм (и выше). Математически это похоже на перевернутую параболу. Что бы не быть голословным покажу как это выглядит:

здесь (x1, y1) - заданная точка, r - выбранный радиус, (x2, y2) - высота холма. Вот как выглядит одиночный холм:

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

Теперь у нас уже есть построенный ландшафт. Теперь пойдем далее - к нормализации полученого результата.

Нормализация Ландшафта

При генерации значений для ландшафта мы не учитывали выходы этих значений за некоторые пределы (например - если у нас потом ландшафт будет храниться в монохромной картинке, то нам необходимо, чтобы все значения находились в пределе от 0 до 256). Для этого нам необходимо произвести нормализацию значений. Математически нормализация - это процесс получения значений из одного предела, и перевод его в другие пределы. Вот как это выглядит графически:

Чтобы нам это сделать мы производим следующие действия:

• сперва проходим по всему массиву и запоминаем наибольшее и наименьшее значения;
• после того, как мы узнали эти значения, мы заново проходим по всему ландшафту и производим нормализацию конкретных значений в пределы от 0 до 1. В виде формулы это выглядит так:

После этого мы имеем готовый ландшафт, нормализованный и готовый к дальнейшему использованию. Теперь перейдем к вопросу о "долинизации" ландшафта.

"Долинизация" ландшафта

Вообще говоря, данный ландшафт уже можно использовать. Что же мне еще не нравится? Конечно, ландшафт уже готов, но если присмотреться, то в нем достаточно мало долин. Склоны холмов излишне крутые, хочется сделать их более пологими. В этом нам поможет наш предыдущий шаг - нормализация. Все значения у нас сейчас находятся в пределах от 0 до 1. Идея "долинизации" состоит в следующем - взять от каждого значения квадратный корень. Это в большей степени влияет на средние значения, практически не затрагивая минимумов и максимумов. Графически это выглядит так:

А вот, как это повлияло на наш ландшафт:

Теперь с эти алгоритмом можно закончить.

В основном, рассмотренные нами алгоритмы предназначены для создания простого холмистого или гористого ландшафта. Но существуют и другие типы ландшафтов. Например, острова (точнее группы островов), озерные ландшафты. Их можно реализовать достаточно просто:

• создаем простой, достаточно холмистый ландшафт;
• затем перемещаем уровень воды вверх или вниз. (при этом следует оговориться, что мы примем за уровень воды, я обычно имею в виду нулевой уровень, там где координаты у=0).

Практически мы просто проходим весь массив высот и смещаем их на какое-то значение.

Теперь рассмотрим еще один тип ландшафтов - одиночные острова или горные плато (как часто показывают в американских фильмах), в зависимости от того, где мы затем "разместим" воду.

Модификация холмового алгоритма для островов

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

В исходном алгоритме мы выбирали центральную точку случайным образом, и она могла располагаться в любой части ландшафта. Теперь же нам интересно, чтобы холмы были расположены ближе к центру. Чтобы сделать это, введем две переменных (которые потом будем случайным образом изменять), назовем их расстояние и угол. Расстояние будет означать, как далеко от центра находится центральная точка для одиночного холма. Оно может изменяться от ноля (прямо по центру карты высот) до половины величины карты высот минус радиус холма. Это позволит нам избежать ситуаций пересечения холмов с краем карты высот. Угол будет показывать, в каком направлении от центра нам нужно будет поставить холм. Изменяется в пределах от 0 до двух Пи. Используя эти два значения, мы можем получить значения (x, y) для центральной точки конкретного холма и использовать их как и в простом алгоритме. Вот как нам можно получить значения для x и y:

здесь size - размер карты высот, distance - расстояние, theta - угол. Помните - радиус должен быть меньше половины размера карты высот.

Поработав с этими величинами, мы можем получить довольно прилично выглядящий остров:

Вот и весь алгоритм. Все предельно просто, и остров действительно похож на остров. Хотя нет, чего-то не хватает. Ну конечно же - остров-то где расположен? В воде…

Вот мы и рассмотрели некоторые алгоритмы построения карт высот для ландшафтов. Рассмотрим еще некоторые сопутствующие операции:

• Сглаживание (или по-другому - размытие). Низкочастотный фильтр для уменьшения эффектов угловатости. При многократном применении позволяет добиться очень гладких очертаний ландшафта. (Есть аналог в программе Adode Photoshop - фильтр Blur). Как это делается я уже показывал в первом алгоритме;
• Превращение гористой местности в холмистую. Я их различаю по очертанию вертикальных разрезов у вторых более пологие края. Как это делается я уже показывал ("долинизация" ландшафта);
• Создание пляжей и отмелей в случае с островами и берегами. Для этого места соприкосновения с водой сглаживают. Хотя могут существовать и скалистые пляжи и просто скалы.

Еще одна немаловажная деталь, но это уже при рендеринге ландшафтов, а не при генерации. Для правильного освещения полученного ландшафта вам необходимо будет найти нормали к каждой вершине. Это достаточно тривиальная задача и она выходит за рамки данной статьи. Если же вам все-таки это важно, то приглашаю на мой сайт: http://www.vvsu.ru/dkcsc/.

В заключение

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

P.S. При подготовке материала использовался пакет для триангуляции и визуализации ландшафтов - ReLife3D 2 (найти его можно на моем сайте - http://www.vvsu.ru/dkcsc/).

Надеюсь, вам помогают мои советы и примеры. Следите за последующими обновлениями.