ROAM Ландшафт


A.Y. AlexG


Опубликовано: 02.10.2009

Источник: http://www.xnadev.ru/articles.php?article_id=81



Вместо предисловия. Только хорошая мотивация может побороть природную лень, собственно ничего не добавить и не прибавить – написать статью описывающую рендеринг ландшафта я собирался давно, собирался, собирался, собирался… И увидев приз – подписку на MSDN наконец собрался.  Еще один disclaimer: статья мной субъективно оценивается как средняя по уровню, я не разжевываю здесь все базовые вещи (например что такое матрица проекции, как организован основной игровой цикл XNA, что такое шейдер и т.п.), так что статья рекомендуется к прочтению людям у которых есть некий опыт программирования в XNA и они наконец задумались о такой насущной в игре вещи как…

Ландшафт

Открытые пространства в современных играх встречаются повсеместно и в самых разных жанрах: RTS, FPS, RPG, MMORPG – в большинстве игр этих жанров действие так или иначе происходит на поверхности. Само слово еще вначале XIX века трактовали как “окружающую наблюдателя  территорию, которую можно осмотреть единым взглядом”. Что-то близкое к геймдеву, не так ли?!
Все, что мы хотим изобразить на мониторе компьютера, должно иметь какую-то математическую модель, возникает закономерный вопрос – как описать местность? Есть несколько вариантов известных мне.

Воксели

articles: Landscape01.png
Увы мне, я не художник, но постарался изобразить некий объем разделенный на равные части и у этих частей образно есть атрибут (назовем это цветом), в нашем случае говорящий заполнена ли часть объема (в нашем случае землей, снегом, водой, да мало ли вариантов) или нет. Как это выглядит в реализации – в простейшем случае у нас есть бооооольшой трехмерный массив, в котором записаны данные. В чем плюсы: можно задать самый замысловатый ландшафт – нависающие арки, скалы с обратным уклоном, гроты и т.д. и т.п… Из минусов нетривиальность исполнения, большой расход памяти.

Воксели + немного мамбо-джамбо

Вообще говоря массив из предыдущего пункта можно рассматривать как результат некой функции v=f(x,y,z) , где область допустимых значений этой функции {-1,0,1} , говоря человеческим языком функция каждой точке трехмерного пространства сопоставляет -1, если эта точка под землей, 0 если точка поверхность земли и 1 если точка над землей. Этот замечательный подход иногда используют при процедурной генерации ландшафта. С другой стороны если вы поклонник математического анализа и разбираетесь в рядах так, что Тейлор и Фурье вам позавидуют, то для вас, наверное, не составит труда сделать обратную операцию, а именно из массива сделать  функцию. Функция эта, учитывая конечность элементов ряда в реальной жизни, будет не совсем тем, что хочется, а с ошибкой, но тут уж как говорится “селяви”, больше членов – больше точность. В общем и целом на этом фронте может быть множество интересных идей и воксели будоражили, и будут будоражить умы энтузиастов с самой эры зарождения компьютерной графики, но в основном мы поговорим о гораздо более часто используемом, простом (здесь, как и везде простота - относительное понятие) в реализации и понимании способе.

Карта высот

Почти все модели в науке и технике упрощены, они позволяют нам представлять некий объект с определенной точностью, но естественно не являются самим объектом, не описывают всех его свойств и поведения. Например, представление о том, от какого полюса к какому движутся электроны, менялось вроде бы не один раз, что не мешало  довольно успешно пользоваться телеграфом, электрической дугой и прочим и прочим.  В нашем случае упрощение тоже имеется, мы будем строить ландшафт по высоте. Т.е. любые две координаты x и z  дают координату y, которая показывает высоту поверхности над абсолютным уровнем, если присмотреться, то видно, что из уравнения общего вида в предыдущем пункте, по сути, исключили одну переменную, теперь оно такое y=f(x,z), что с одной стороны дело существенно упрощает. С другой стороны лишает таких вкусностей как многоуровневость ландшафта, никаких арочек, обратного наклона и прочих радостей без плясок с бубном. Что это означает для реализации, а то, что нужен не трехмерный массив, а двумерный и выполнить его можно с определенной дискретизацией. Если еще проще, пусть у нас есть GPS, берем участок 100x100 метров и дальше обходим его и записываем результаты замеров высоты, если замеры мы будем делать через каждые 10 метров, то у нас получится табличка примерно такого вида:

H(0,0)= 5 метров
H(10,0)= 6.53 метра
…
H(100,0)=12 метров
H(0,10)= 5.2 метра
H(10,10)=5.4 метра
…
H(100,100)=10.5 метров

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

articles: Landscape03.png
Земля целиком

Как нетрудно заметить более высокие места – более светлые. Вот и все общее описание принципа. Для того, чтобы создавать карты высот совершенно не обязательно бросаться к Paint’у и судорожно настраивать цвета в палитре. На текущий момент создано немало инструментов, которые помогут создать собственные карты, достаточно лишь погуглить на предмет “heightmap editor” и вам откроются бездны и бездны, в том числе и 3D редакторы, но мне для начала хватило простенького hme.

Дьявол в деталях

На словах все довольно просто, но когда дело доходит до реализации могут возникнуть определенные сложности и, наверное, одна из самых интересных в этом плане задач, это получение больших ландшафтов, миллион квадратных километров с детализацией скажем в 10 метров, да только хранение такого объема уже гигабайты или небольшие площади, но с огромной детализацией, что в принципе одно и тоже. Но мы спустимся с небес и при вполне земной задаче 1025x1025 точек у нас уже два миллиона треугольников на экране. Пусть даже многие из них будут отсечены при куллинге, поверьте оставшихся хватит для того чтобы притормозить ваш даже очень навороченный комп. А ведь большинство этих треугольников настолько далеки, что куча таких умещается в одном пикселе – шейдеры вхолостую “прокачивают” совершенно ненужные данные. Здесь-то на помощь и приходят множество алгоритмов под общей аббревиатурой LOD (Level Of Detail – уровень детализации). Эти алгоритмы позволяют эффективно отсечь лишнее и аппроксимировать удаленное для адекватного рендеринга. На http://www.vterrain.org/LOD/ можно прочесть кучу небесполезной информации, но она не говоря уже о том, что на английском, что отпугнет часть аудитории, кроме того еще и на мой непритязательный вкус очень академична. При изучении материала мне гораздо больше помогли ссылки присланные ребятами на форуме, за что им огромное спасибо. Итак, для тех, кто хочет отклониться в сторону вот эти ссылки:
Я же тем времен скромно продолжу рассказ о том, как сделать ландшафт с ROAM (Realtime Optimally-Adapting Meshes)  .
Предполагаю, что вы знакомы с построением каркаса приложения на XNA и поэтому думаю следующее действие не вызовет затруднений – в проект в качестве контента мы добавим текстуру, которая является не чем иным как картой высот. У меня она в bitmap формате:
articles: Landscape04.png
Следующим шагом будет создание класса, ответственного за визуализацию ландшафта. Назовем его емко и глубокомысленно – Terrain. В моей архитектуре это просто класс, но в принципе его вполне можно реализовывать как наследника DrawableGameComponent.

Все самое важное мы сделали ? Остались остальные 80 % работы. У нас есть текстура, в которой хранятся данные о высотах, нам нужно при инициализации получить из нее данные.

private float[,] GetHeight()

{
	Color[] colors = new Color[_heightTexture.Width * _heightTexture.Height];

	float[,] heights = new float[TerrainSize,TerrainSize];

	_heightTexture.GetData(colors);
	for(int i=0; i< TerrainSize; i++)

		for(int j=0; j< TerrainSize;j++)

		{
			Color clr = colors[i + j*_heightTexture.Width];

			heights[i, j] = clr.R; //SmoothHeight( clr.R );
		}

	return heights;
}

 

Пресловутая текстура – это  heightTexture, я надеюсь сказать _heightTexture = Game.Content.Load<Texture2D>("heightmap"); вы вполне перед этим сумеете. Итак в вышеописанном  методе мы получаем массив цветов с помощью метода Texture2D.GetData, затем пробегая построчно по массиву (хоть он и одномерный, но мы же ведь знаем размер строчки (i + j*_heightTexture.Width – формула простая, но она будет еще долго фигурировать в работе этого компонента, так что лучше сразу уясните, если вдруг что то не ясно, как из одномерного массива сделать двумерный).  После такого мы обязаны жениться  заполнить вершинный буфер.
private void FillBuffers(float[,] height)

{
	VertexPositionColor[] vertex = new VertexPositionColor[TerrainSize * TerrainSize];

	for(int i=0; i< TerrainSize; i++)

		for (int j = 0; j < TerrainSize; j++)

		{
			Vector3 position = new Vector3(i * Units.HeightMapUnit, height[i, j], j * Units.HeightMapUnit);

			vertex[i + j * TerrainSize] = new VertexPositionColor(position, Color.White);

		}
 
	_vertexBuffer = new VertexBuffer(GameManager.Instance.Game.GraphicsDevice, typeof(VertexPositionColor)

        ,vertex.Length, BufferUsage.WriteOnly);
	_vertexBuffer.SetData(vertex);
}

 

Для  примера я использую стандартный VertexPositionColor, при текстурировании можно и нужно будет использовать  другие форматы вершин, но сейчас этого достаточно. Дальше начинается самое интересное – для прорисовки нам не хватает индексного буфера, он будет заполняться динамически и индексы нам будет помогать определять класс  TerrainTriangle. Для того, чтобы подробно объяснить его логику работы постараюсь для начала описать алгоритм в целом.

Изначально весь регион представляется двумя треугольниками:
articles: Landscape05.png
Если какой либо из треугольников в видимом пространстве занимает больше определенной части размерности экрана (в моем примере eps = 0.1f):
public bool ShouldSplit(Matrix wvp, BoundingFrustum frustum)
{
	bool result = false;

	if (frustum.Contains(vCenter) != ContainmentType.Disjoint 
	|| frustum.Contains(lPos) != ContainmentType.Disjoint

		|| frustum.Contains(rPos) != ContainmentType.Disjoint
		|| frustum.Contains(tPos) != ContainmentType.Disjoint)

	{
		Vector4 lScreenPos = Vector4.Transform(lPos, wvp);
		Vector4 aScreenPos = Vector4.Transform(vCenter, wvp);

		lScreenPos /= lScreenPos.W;
		aScreenPos /= aScreenPos.W;
 

		Vector4 difference = lScreenPos - aScreenPos;
		Vector2 aScreenDifference = new Vector2(difference.X, difference.Y);

 
		float eps = 0.1f;
		if (aScreenDifference.Length() > eps)

		{
			result = true;
		}
	}
	return result;

}

 


Здесь lPos, rPos, tPos, vCenter – соответственно левая, правая, верхняя и центральная координаты треугольника. Вообще говоря на них можно и экономить память, т.е. вычислять эти Vector3 в процессе держа только индексы вершин, потому как сетка эта займет в памяти
articles: Landscape09.png треугольников, однако помним, что экономя на памяти теряем на производительности, так что я так не ухищрялся.
Далее треугольник, который признан слишком толстым  делится пополам, а так же делится его сосед снизу и если не был разделен треугольник являющийся “родоначальным” (треугольник из которого делением пополам образовался этот), то делится и он. т.е.:
articles: Landscape06.png
И этот тоже разделим.  Получим :
articles: Landscape07.png
Здесь показан принцип деления, который отражает метод:
private void PropagateSplitList(ConcurrentStack<TerrainTriangle> splitList)

{
	if (!Split)
	{
		Split = true;

		splitList.Push(this);
		if (bNeigh != null)

			bNeigh.PropagateSplitList(splitList);
		if (parent != null)

			parent.PropagateSplitList(splitList);
	}
}

 


bNeigh – здесь треугольник который является примыкает к стороне разделяемой пополам. А т.к. метод применяется для всех треугольников из изначального набора (напомню их вначале 2), то он охватывает все сегменты.

Из всего этого можно понять, что ROAM обладает таким свойством как инертность, т.е. в самом начале рендеринга нас ждет адаптация (что ясно из названия метода и которая всегда требует некоторого времени) к текущим условиям, впрочем на глаз чаще всего незаметная. Так что если вы планируете пролеты со скоростью пули на тысячу километров над уровнем местности – может стоит подумать о другом методе (или поумерить амбиции), в любом случае об этом свойстве метода стоит помнить.

Следующим шагом мы соберем все треугольники на которых остановилось деление в список:
public void ProcessSplitList(List<TerrainTriangle> drawList)

{
	if (!rChildTriangle.Split)
		drawList.Add(rChildTriangle);

	if (!lChildTriangle.Split)
		drawList.Add(lChildTriangle);

}

 

Теперь  нужно склеить те треугольники, которые слишком удалились и стали слишком мелкими. На возможность склейки вообще проверяет свойство:

private bool CanMerge

{
	get
	{
		bool canNotMerge = false;

		if (lChildTriangle != null)
			canNotMerge |= lChildTriangle.Split;

		if (rChildTriangle != null)
			canNotMerge |= rChildTriangle.Split;

		if (bNeigh != null)
		{
			if (bNeigh.lChildTriangle != null)

			{
				canNotMerge |= bNeigh.lChildTriangle.Split;
			}
 

			if (bNeigh.rChildTriangle != null)
			{
				canNotMerge |= bNeigh.rChildTriangle.Split;

			}
		}
		return !canNotMerge;
	}
}

 

Но комплексную проверку дает метод

private bool CheckMerge(ConcurrentStack<TerrainTriangle> mergeList, Matrix wvp, BoundingFrustum frustum)

{
	bool shouldMerge = false;
	if (!addedToMergeList)

	{
		if (CanMerge)
		{
			if (!ShouldSplit(wvp, frustum))

				shouldMerge = true;
			if (bNeigh != null)

			{
				if (bNeigh.ShouldSplit(wvp, frustum))
					shouldMerge = false;

			}
		}
	}
	if (shouldMerge)
	{

		addedToMergeList = true;
		mergeList.Push(this);
		if (bNeigh != null)

		{
			mergeList.Push(bNeigh);
		}
	}

	return addedToMergeList;
}

 

Пока не стоит обращать внимания на ConcurrentStack<T>, про оптимизацию и многопоточность мы поговорим дальше. Здесь стоит внимательно присмотреться к самой логике проверки на “склеиваемость”, при потенциальной возможности склеить (см. предыдущее свойство) проверяется достаточно ли мал треугольник и не нужно ли дробить его соседа снизу. Если эти условия соблюдены, то в список для склейки добавляются треугольник и его нижний сосед. Только следует иметь в виду, что вся эта проверка и добавление проводятся на родителях конечных треугольников:

public void CreateMergeList(ConcurrentStack<TerrainTriangle> mergeList, 
		ConcurrentStack<TerrainTriangle> leftOverList, Matrix wvp, 

		BoundingFrustum frustum)
{	bool canNotMerge = false;
	if (parent != null)

	{
		canNotMerge = !parent.CheckMerge(mergeList, wvp, frustum);
	}

	if (canNotMerge)
		leftOverList.Push(this);
}

 

Если  у вас ум заходит за разум, ничего – на все требуется время и обстоятельные размышления никому еще не навредили. Пройдитесь по тексту глазами, разберитесь по шагам что к чему. Напоминаю, что у нас остался сухой остаток leftOverList, что делать с ним – все просто, если такой треугольник не является разделенным, то его добавляем к отрисовываемым:
public void ProcessRemainders(List<TerrainTriangle> newTriangleList)

{
	if (!Split)
		newTriangleList.Add(this);

}

 


И это все, что касается непосредственно алгоритма.  Ах, да – старый список заменяем новым:
if (newTriangleList.Count > 0)

{
	_triangleList = newTriangleList;
	_triangleList.TrimExcess();
	UserInterface.UI.TrianglesCount = TrianglesCount;

}

 


Еще поясняю маленький момент с условием, который может ускользнуть от внимания – помните в самом начале у нас было два треугольника, покрывавших весь регион местности, а теперь подумайте, что будет если повернуть камеру “в небо”. Мы можем потерять все треугольники, и в следующей итерации просто не из чего будет строить сетку.

Таким образом, из раза в раз мы адаптируем наш набор треугольников к изменившимся условиям.  Эту операцию естественно не обязательно делать каждый Update, можете обратить внимание -  в проекте, прилагающемуся к статье есть интерфейс IDirected, который предоставляет события PositionChanged и IDirectionChanged, а ICamera является его наследником.  Таким образом апдейт ландшафта можно привязать к изменению состояния наблюдателя (его перемещения или поворота), что существенно скажется на производительности, обязательно поэкспериментируйте на эту тему. Все необходимое для этого есть в примере. Только не забудьте, как это честно сделал я, что нужно убедиться, что сетка адаптировалась до конца, иначе вас ждет довольно забавное поведение вашей местности. Ну и осталась техника… Нам нужно заполнить индексный буфер, здесь нам поможет helper-класс, который мне понадобился больше из-за того, что моя фиговенькая видюшка на работе не позволяла адресовать в индексном буфере больше Int16 точек, а добрая NVidia 8800 GTS уже с 92-ым (могу ошибаться) процессором дома позволяла еще и не такие чудеса:
public class ListConnectedIndexBuffer<T> where T:struct 
{
	private IList<T> _source;

	private DynamicIndexBuffer _buffer;
	private GraphicsDevice _device;
	private int _elementSize;

 
	public ListConnectedIndexBuffer(IList<T> indexList, GraphicsDevice device)
	{
		_source = indexList;

		_device = device;
		_buffer = new DynamicIndexBuffer(device,typeof(T),_source.Count,BufferUsage.WriteOnly);

		_buffer.SetData(_source.ToArray(), 0, _source.Count, SetDataOptions.Discard);

		_buffer.ContentLost += new EventHandler(Buffer_ContentLost);
		_elementSize = Marshal.SizeOf(this.GetType().GetGenericArguments()[0]);

	}
 
	void Buffer_ContentLost(object sender, EventArgs e)
	{

		ResetBuffer();
		_buffer.SetData(_source.ToArray(),0,_source.Count,SetDataOptions.Discard);

	}
 
	private void ResetBuffer()
	{
		_buffer.Dispose();

		_buffer = new DynamicIndexBuffer(_device, typeof(T), _source.Count, BufferUsage.WriteOnly);

	}
 
	public void UpdateBuffer()
	{
		if ( _buffer.SizeInBytes / _elementSize < _source.Count)

		{
			ResetBuffer();
		}
		_buffer.SetData(_source.ToArray(), 0, _source.Count, SetDataOptions.Discard);

	}
 
	public DynamicIndexBuffer Buffer
	{
		get { return _buffer;}

	}
}

 


Сей дженерик-класс позволяет инициализировать индексный буфер изначальным списком вершин, справляется с потерей устройства и позволяет обновлять себя без лишнего геморроя, ну и личный упоминавшийся бонус вряд ли кому еще полезный – возможность выбирать размерность адресации:
_cBuffer = new ListConnectedIndexBuffer <int> (_indexList , GameManager.Instance.Game.GraphicsDevice);

 

Сам же апдейт выглядит так:
private void UpdateIndexBuffer()

{
	_indexList.Clear();
	if (_triangleList.Count > 0)

	{
		foreach (TerrainTriangle triangle in _triangleList)
		{
			triangle.AddIndices(_indexList);

		}
 
		_cBuffer.UpdateBuffer();
	}
}

 

Процесс отрисовки довольно прост, потому что про текстурирование предстоит отдельный большой разговор и это будет следующая статья.
public void Draw(GameTime gameTime, ICamera camera )

{
	if (_triangleList.Count > 0)
	{
		var device = GameManager.Instance.Game.GraphicsDevice;

		BasicEffect eff = new BasicEffect(device, null);
 
		eff.View = camera.View;

		eff.World = MiddleTranslation;
		eff.Projection = camera.Projection;

		device.Indices = _cBuffer.Buffer; //_indexBuffer;
		device.VertexDeclaration = new VertexDeclaration(device, VertexPositionColor.VertexElements);

		device.Vertices[0].SetSource(_vertexBuffer, 0, VertexPositionColor.SizeInBytes);
 

		eff.Begin();
		foreach (EffectPass pass in eff.CurrentTechnique.Passes)

		{
			pass.Begin();
			device.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, TerrainSize*TerrainSize, 0, _triangleList.Count);

			pass.End();
		}
		eff.End();

		device.Indices = null;
	}
}

 

Из кода видно, что всего лишь использую BasicEffect, однако если держать в уме, что сам класс Terrain это не DrawableGameComponent и заглянуть чуть выше по стеку вы увидите метод Draw откуда все это хозяйство вызывается, там происходит любопытная вещь, такая как ResetRenderStates(). Название у нее вполне самоописательное, а нужна вся эта котовасия, потому как вы наверняка будете рисовать что-то поверх свое  - курсор, FPSы ( соответсвующий компонент кстати прилагается -  только имейте в виду, он сделал “честным”, больше чем было вызовов Draw в секунду не покажет).
Теперь несколько слов об еще одном улучшении классики, этот алгоритм я выполнил с помощью библиотеки ParallelFX , что позволило выполнять операции разбиения треугольников и их слияния, задействовав все возможности ваших многоядерных процессоров. Обратите внимание на класс ConcurrentStack<T> , именно он позволяет нам добавлять треугольники из разных потоков без риска, само же использование библиотеки интуитивно просто.  Да, имейте в виду это - CTP, хоть и вполне рабочая превью, но все же превью.
Ну и давайте полюбуемся на результат, мы этого заслужили:
articles: Landscape08.png

Не слишком впечатляющий результат с точки зрения графики? Вы абсолютно правы и именно поэтому в следующей статье (будет, будет, неужто за месяц не напишу, я же хочу прыз) мы будем ландшафт текстурировать, затенять, научимся получать точку на местности по точке экрана, в планах так же эффекты типа указателя на поверхности (кто помнит геймплей WOW или Neverwinter Nights и заклинания по области тот поймет о чем речь), возможно дойдут руки до билбордов и простенькой зелени, ну и мы обязательно украсим сцену каким-нить красивым небом (веротяно пока статичным ). Как видите планов громадье… Если понравилось – пишите, если не понравилось – пишите тоже, с интересом буду ждать комментариев.

Как видим здесь координаты по X и Z умножаются на некий масштабный коэффициент - он и есть Units. HeightMapUnit . Т.е. по сути он означает на сколько растягивается каждый элементарный квадратик сетки в реальном worldspace. На данном этапе реализации это непринципиально, но поскольку на этом каркасе я постараюсь сделать (и уже делаю) еще что то, представляется нелишним иметь данные о масштабировании в одном месте (Units).