Procedural Landscape on XNA Game Studio 3.0

Динамический ландшафт



Демонстрация:



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

Закончил эту часть работы давно. Даже успели обсудить на xnadev.ru . Сейчас данный проект уже несколько раз преобразился. Возможно, в скором времени, дойдут руки сделать новое видео. Как раз будет повод рассказать о том, что из себя представляет «Terrain Geomorphing in the Vertex Shader» и с чем его едят. Пока расскажу об этом этапе.

Как это делалось?

Описал представление слоев детализации и данных о вершинах.
Карта логики представления слоев детализации выглядит так:



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



На обеих картинках цвета слоев не совпадают. Лень переделывать. Просто остались наработанные картинки, которые изначально не предназначались для статьи.

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

private void backgroundWorker_DoWork
(object sender, DoWorkEventArgs e)
{
PartitionLevels();
geometry.InitIndex();
geometry.GenNormal();
}

- разбиение слоев детализации, добавление новых вершин (и корректировка их высот) в единый массив вершин;
- инициализация единого массива индексов, связывающих все треугольники (вершины), всех слоев детализации.
- генерация нормалей.

На пальцах все это выглядит просто, для оценки реализации приведу пример рекурсивного метода, рассчитывающего интервал значений индексного массива, соответствующего ветке дерева визуализации нулевого слоя детализации.
Честное слово, мне проще код писать, чем слова в предложения собирать. Не ругайте сильно, но по другому мне сложно коротко сформулировать ту кучу "каракуль", которыми я исписал свой блокнот, занимаясь данной темой.
Нулевым в данном случае является слой наименьшей детализации. Что бы окончательно Вас запутать. Скажу что понятия уровней детализации и дерева детализации тесно сплетены между собой. Дерево это восходящие, из слоя нулевой детализации, ветви связей перпендикулярно пересекающие по иерархии старшинства следующие уровни (плоскости) детализации, разделяясь в точке пересечения на четыре наследника. Потому Quad tree. Зачем все так сложно? Зачем представление в виде дерева и плоскостей? Все просто. Каждое представление для выполнения различных задач. Каждые задачи наиболее быстро выполняются только в одном из представлений. Плоскости для линейных задач, дерево для рекурсивных и отслеживания наследственных связей. Выше упомянутый обещанный рекурсивный метод возвращает все индексы всех треугольников ограниченных габаритами одной ветки нулевого слоя детализации.

Блок схема обещанного метода:



Блок схема автоматически сгенерирована примочкой к Visual Studio под названием «Microsoft Visual Studio Learning Pack 2.0»

Код метода:

Код метода:
/// 
/// Рекурсивная сборка индексов отдельной ветки дерава уровней детализации ландшафта
/// 
private void InitNodeIndex (gplNode inNode, ref int inIndex)
{
// --- уровень детализации ---------------------------------------
int l = inNode.Level;
// --- индекс активной ветки --------------------------------------
int i = inNode.Index;
// --- размеры активного уровня детализации -----------------------
int w = levelInfo[l].W;
int h = levelInfo[l].H;
// --- признаки соединение со слоем более низкой детализации ------
bool bLeft = false;
bool bRight = false;
bool bUp = false;
bool bDown = false;
// --- индексные направления слоя для псевдодвухмерной карты ------
gxplTrends trends = new gxplTrends();
trends.NewTrends(i, w);
// --- если ветка не разбита ----------------------------------------------------------------------------------------
if (inNode.NodeChildren == null)
{
// --------------------------------------------------------------------------------------------------------------
#region --- собираем два треугольника ---------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
// - 1й треугольник -----------------------
indices[inIndex + 0] = trends.Center;
indices[inIndex + 1] = trends.Right;
indices[inIndex + 2] = trends.Down;
// - 2й треугольник -----------------------
indices[inIndex + 3] = trends.Down;
indices[inIndex + 4] = trends.Right;
indices[inIndex + 5] = trends.DownRight;
inIndex += 6;
// --------------------------------------------------------------------------------------------------------------
#endregion ------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
}
// --- если разбита -------------------------------------------------------------------------------------------------
else
{
// --------------------------------------------------------------------------------------------------------------
#region --- определение режима соединения с соседними ветками ---------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
// --- check left join --------------------------------------------
//if (!bNoLeft)
bLeft = (inNode.Coord.X > levelInfo[l].SX0) ?
map[trends.Left].NodeChildren == null : true;
// --- check right join -------------------------------------------
//if (!bNoRight)
bRight = (inNode.Coord.X < levelInfo[l].SX0 + levelInfo[l].W - 1) ?
map[trends.Right].NodeChildren == null : true;
// --- check up join ----------------------------------------------
//if (!bNoUp)
bUp = (inNode.Coord.Y > levelInfo[l].SY0) ?
map[trends.Up].NodeChildren == null : true;
// --- check down join --------------------------------------------
//if (!bNoDown)
bDown = (inNode.Coord.Y < levelInfo[l].SY0 + levelInfo[l].H - 1) ?
map[trends.Down].NodeChildren == null : true;
// --------------------------------------------------------------------------------------------------------------
#endregion ------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
#region --- сборка всех треугольников с учетом связей различных слоев детализации -------------------------------
// --------------------------------------------------------------------------------------------------------------
// --- индексные направления слоя +1 для псевдодвухмерной карты -------------------------
gxplTrends trends4x3 = new gxplTrends(inNode.NodeChildren[3].Index, levelInfo[l + 1].W);
// --------------------------------------------------------------------------------------------------------------
#region --- если с лева соединение с более высокой детализацией --------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
if (bLeft)
{
indices[inIndex + 0] = trends.Center;
indices[inIndex + 1] = trends4x3.Center;
indices[inIndex + 2] = trends.Down;
inIndex += 3;
// --- если с верху нет! соединения с более высокой детализацией (добавочный треугольник)
if (!bUp)
{
indices[inIndex + 0] = trends.Center;
indices[inIndex + 1] = trends4x3.Up;
indices[inIndex + 2] = trends4x3.Center;
inIndex += 3;
}
// --- если с низу нет! соединения с более высокой детализацией (добавочный треугольник)
if (!bDown)
{
indices[inIndex + 0] = trends.Down;
indices[inIndex + 1] = trends4x3.Center;
indices[inIndex + 2] = trends4x3.Down;
inIndex += 3;
}
}
else // если нет соединение с более высокой детализацией, то переходим к следующему уровню детализации
{
if (!bUp) // Х0
InitNodeIndex(inNode.NodeChildren[0], ref inIndex); // 00

if (!bDown) // 00
InitNodeIndex(inNode.NodeChildren[2], ref inIndex); // Х0
}
// --------------------------------------------------------------------------------------------------------------
#endregion ------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
#region --- если с права соединение с более высокой детализацией ------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
if (bRight)
{
indices[inIndex + 0] = trends.Right;
indices[inIndex + 1] = trends.DownRight;
indices[inIndex + 2] = trends4x3.Center;
inIndex += 3;
// --- если с верху нет! соединения с более высокой детализацией (добавочный треугольник)
if (!bUp)
{
indices[inIndex + 0] = trends4x3.Center;
indices[inIndex + 1] = trends4x3.Up;
indices[inIndex + 2] = trends.Right;
inIndex += 3;
}
// --- если с низу нет! соединения с более высокой детализацией (добавочный треугольник)
if (!bDown)
{
indices[inIndex + 0] = trends4x3.Center;
indices[inIndex + 1] = trends.DownRight;
indices[inIndex + 2] = trends4x3.Down;
inIndex += 3;
}
}
else // если нет соединение с более высокой детализацией, то переходим к следующему уровню детализации
{
if (!bUp) // 0Х
InitNodeIndex(inNode.NodeChildren[1], ref inIndex); // 00

if (!bDown) // 00
InitNodeIndex(inNode.NodeChildren[3], ref inIndex); // 0Х
}
// --------------------------------------------------------------------------------------------------------------
#endregion ------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
#region --- если с верху соединение с более высокой детализацией ------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
if (bUp)
{
indices[inIndex + 0] = trends.Center;
indices[inIndex + 1] = trends.Right;
indices[inIndex + 2] = trends4x3.Center;
inIndex += 3;
// --- если с лева нет! соединения с более высокой детализацией (добавочный треугольник)
if (!bLeft)
{
indices[inIndex + 0] = trends.Center;
indices[inIndex + 1] = trends4x3.Center;
indices[inIndex + 2] = trends4x3.Left;
inIndex += 3;
}
// --- если с права нет! соединения с более высокой детализацией (добавочный треугольник)
if (!bRight)
{
indices[inIndex + 0] = trends4x3.Center;
indices[inIndex + 1] = trends.Right;
indices[inIndex + 2] = trends4x3.Right;
inIndex += 3;
}
}
// --------------------------------------------------------------------------------------------------------------
#endregion ------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
#region --- если с низу соединение с более высокой детализацией -------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
if (bDown)
{
indices[inIndex + 0] = trends.Down;
indices[inIndex + 1] = trends4x3.Center;
indices[inIndex + 2] = trends.DownRight;
inIndex += 3;
// --- если с лева нет! соединения с более высокой детализацией (добавочный треугольник)
if (!bLeft)
{
indices[inIndex + 0] = trends4x3.Center;
indices[inIndex + 1] = trends.Down;
indices[inIndex + 2] = trends4x3.Left;
inIndex += 3;
}
// --- если с права нет! соединения с более высокой детализацией (добавочный треугольник)
if (!bRight)
{
indices[inIndex + 0] = trends4x3.Center;
indices[inIndex + 1] = trends4x3.Right;
indices[inIndex + 2] = trends.DownRight;
inIndex += 3;
}
}
//else
//{
//
//}
// --------------------------------------------------------------------------------------------------------------
#endregion ------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
#endregion ------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------------
}
}

Свои задачи данная разработка уже выполнила. Для себя дальнейшие пути развития данной идеи я вижу два:
1) Растачивать дальше в этом направлении. Реализовать динамическую подгруздку данных о высотах с диска. Есть расчетные таблицы. Разработан алгоритм быстрого обновления кэшей высот к уровням детализации, без смещения (move) данных. Это позволит работать с ландшафтами огромного размера. Приведу пример расчета размеров LOD’ов для карты 1310.72^2 км с максимальной детализацией до 10^2 м:



2) Для игр. Придется переделать исходную коллекцию массивов высот в один. И реализовать новую выборку.

Вот как то так.

Оригинальный блог