Автор: Артем Мерец «Scart»

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

Изменено: 05.02.2008

Постоянная ссылка

Комментарии [5]

Алгоритм Octree (часть 2)


Автор продолжает разбор популярного метода сортировки - октарное дерево (Octree) для оптимизации скорости работы 3D приложений. Как обычно прилагается пример практической реализации на DirectX API.



Страницы: 1 2

Содержание

1. От Автора
2. Доработки
3. Особенности реализации
4. Исходный код

1. От Автора

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

Ну что ж, кое-что мы теперь умеем. Пора двигаться дальше.

2. Доработки

Какие недостатки имеет наш класс восьмеричного дерева?
Возможна ситуация, когда мы будем отрисовывать один и тот же объект дважды. Это та ситуация, когда объем объекта (а в нашем случае - точка) принадлежит двум (или более) листам.

Как от этого избавиться? Во-первых, если положение объектов не имеет принципиального значения, то их можно несколько смещать. Таким образом, объект будет относиться только к одному узлу. В случае если объект – материальная точка, проблем не возникнет, однако это довольно редкий случай, и, как правило, объекты имею свои габариты, порой достаточно большие. Если рассматривать в качестве объекта деревце или колодец, то смещение будет заметным, а если объекты типа зданий, то данный способ использовать просто не рекомендуется. Во-вторых, можно привязывать объект только к одному листу изменив условие в функции определения попадания условного объема в куб узла (с ">=" и "<=" на ">" и "<" соответственно), то есть, объект будет относиться к узлу только если его позиция расположена внутри ограничивающего бокс узла. Но тогда объект, лежащий точно на ребре бокса, просто не будет считаться объектом, принадлежащим дереву, а следовательно и рисоваться. Хоть таких объектов, скорее всего, относительно мало, лишаться их не стоит.

И, наконец, наиболее грамотный вариант – запоминать уже отрисованные объекты. Таким образом, объект будет рисоваться при попадании бокса одного из листьев, содержащих оного, в пирамиду видимости, а при попадании второго рисовать их не будем. Различать отрисованные и не отрисованные объекты мы будем при помощи дополнительного bool-флага в структуре Object.


На рисунке объект относится к двум узлам. Сначала мы рисуем все объекты первого узла,
то есть рисуем данный объект и отмечаем в его характеристиках факт рисования.
Потом рисуются все объекты второго узла. Перед непосредственным вызовом функции
рисования мы проверяем флаг объект. Так как только что сфера была отрисована,
то ее флаг будет содержать положительное значение, следовательно, еще раз
рисовать его мы не будем.

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

Раньше мы использовали массив объектов. Это не совсем правильно. Нужно использовать массив указателей. Давайте, опять же, рассмотрим ситуацию с одним объектом в двух и более листах. Если мы зафиксировали факт попадания объекта в бокс листа, то добавляем данный объект в массив нашего листа, то есть при хранении объектов (а не ссылок на них) мы фактически создаем копию объекта для одного листа и его копию для другого. Таким образом, у нас будут два объекта, с совершенно одинаковыми свойствами. А если после этой процедуры игрок захочет переместить объект (ведь именно для динамики мы модернизируем дерево)? Он его переместит, а что произойдет на экране? Правильно, будет нарисовано два объекта (один - тот, который мы только что переместили, а второй – объект-копия, созданный при добавлении в массив). То есть количество объектов будет постоянно расти. При использовании указателей этого не произойдет. Объектов будет ровно столько, сколько мы их создавали, а добавляться в массив будет ссылки на них. Кроме того, если не использовать указатели, то и флаг рисования ставить бессмысленно, ведь поставив флаг “отрисованного” объекта мы будем знать, что данный объект уже нарисован на экране, но второй объект, полученный в результате копирования (при добавлении в массив), не имеет ничего общего с текущим (с точки зрения игры у них одинаковые визуальные и игровые параметры, но с точки зрения программы – ничего), а значит он тоже будет нарисован. В общем, от использования массива объектов мы отказываемся в пользу массива указателей на эти объекты.

3. Особенности реализации

Теперь займемся самой реализацией.

struct BBOX
{
	BBOX()
	{
		min = D3DXVECTOR3(0.0f,0.0f,0.0f);
		max = D3DXVECTOR3(1.0f,1.0f,1.0f);
	}
	float GetDiagonal()
	{
		return D3DXVec3Length( &(max-min) );
	}
	BBOX(D3DXVECTOR3 _min, D3DXVECTOR3 _max) {min = _min; max = _max;}
	D3DXVECTOR3 min;
	D3DXVECTOR3 max;
	D3DXVECTOR3 CalcCenter()
	{ 
		float tmpx = (max.x-min.x)/2.0f; 
		float tmpy = (max.y-min.y)/2.0f; 
		float tmpz = (max.z-min.z)/2.0f; 
		return D3DXVECTOR3(min.x+tmpx, min.y+tmpy, min.z+tmpz);
	}
	bool PointInBox(D3DXVECTOR3 *pos)
	{
		if (min.x <= pos->x && max.x >= pos->x)
		{
			if (min.z <= pos->z && max.z >= pos->z)
			{
				if (min.y <= pos->y && max.y >= pos->y)
				{return true;}
				else {return false;}
			}
			else 
			{
				return false;
			}
		}
		else 
		{
			return false;
		}
		return false;
	}
};

Вот и первые изменения. Мы добавляем метод GetDiagonal. Как понятно из названия он будет возвращать нам диагональ бокса, а точнее - ее длину. Нужен нам этот метод для определения глубины дерева.

struct Object
{
  ID3DXMesh* pMesh;
  D3DXVECTOR3 pos;
  //флаг, который при true говорит, что объект уже отрисован на данном кадре
  bool bDrawed;
  //если позиция изменилась, то нужно пропустить объект через октри заново
  bool bChangePos;
  Object()
    {
    pos = D3DXVECTOR3(0.0f,0.0f,0.0f);
    pMesh = NULL;
    bChangePos=false;
    bDrawed=false;
  }
  void Draw()
  {
    pMesh->DrawSubset(0);
    bDrawed=true;
  }
};

Добавлены два флага: первый bDrawed следит за рисованием объекта (в функции рендеринга устанавливаем его значение в истину), второй bChangePos следит за перемещением объекта. Если объект не был перемещен, то нам не нужно проверять вышел ли он за пределы бокса. Этот флаг устанавливаем в истину тогда, когда объект изменил свою позицию. Здесь целесообразно сделать данную переменную приватной (private), скрыв от остального кода программы, в то же время, добавив метод для изменения позиции в котором и изменять значение флага. Таким образом, мы не забудем поменять данный флаг при изменении позиции объекта.

struct FrustumPlane
{
	D3DXVECTOR3 normal;
	float distance;
	inline void Normalize()
	{
		float tmp = 1 / sqrtf((normal.x*normal.x) +normal.y*normal.y)+(normal.z*normal.z);
		normal.x = normal.x * tmp;
		normal.y = normal.y * tmp;
		normal.z = normal.z * tmp;
		distance = distance * tmp;
	}
	inline float DistanceToPoint(D3DXVECTOR3 *pnt) 
	{
		return D3DXVec3Dot(&normal, pnt) + distance;
	}
};

struct FRUSTUM
{
	FrustumPlane frustumPlanes[6];
	bool BBoxInFrustum(BBOX *box)
	{
		D3DXVECTOR3 min = box->min, max = box->max;
		int p;
		for ( p = 0; p < 6; p++ )
		{
		if (frustumPlanes[p].normal.x*(min.x) + frustumPlanes[p].normal.y*(min.y) +
			frustumPlanes[p].normal.z*(min.z) + frustumPlanes[p].distance>0) continue;
		if (frustumPlanes[p].normal.x*(max.x) + frustumPlanes[p].normal.y*(min.y) +
			frustumPlanes[p].normal.z*(min.z) + frustumPlanes[p].distance>0) continue;
		if (frustumPlanes[p].normal.x*(min.x) + frustumPlanes[p].normal.y*(max.y) +
			frustumPlanes[p].normal.z*(min.z) + frustumPlanes[p].distance>0) continue;
		if (frustumPlanes[p].normal.x*(max.x) + frustumPlanes[p].normal.y*(max.y) +
			frustumPlanes[p].normal.z*(min.z) + frustumPlanes[p].distance>0) continue;
		if (frustumPlanes[p].normal.x*(min.x) + frustumPlanes[p].normal.y*(min.y) +
			frustumPlanes[p].normal.z*(max.z) + frustumPlanes[p].distance>0) continue;
		if (frustumPlanes[p].normal.x*(max.x) + frustumPlanes[p].normal.y*(min.y) +
			frustumPlanes[p].normal.z*(max.z) + frustumPlanes[p].distance>0) continue;
		if (frustumPlanes[p].normal.x*(min.x) + frustumPlanes[p].normal.y*(max.y) +
			frustumPlanes[p].normal.z*(max.z) + frustumPlanes[p].distance>0) continue;
		if (frustumPlanes[p].normal.x*(max.x) + frustumPlanes[p].normal.y*(max.y) +
			frustumPlanes[p].normal.z*(max.z) + frustumPlanes[p].distance>0) continue;
		return false;
		}
		return true;
	}
	void RefreshFrustum()
	{
		D3DXMATRIX Matrix, _invViewMatrix, MatrixView, MatrixProjection;
		D3DDevice->GetTransform(D3DTS_PROJECTION, &MatrixProjection);
		D3DDevice->GetTransform(D3DTS_VIEW, &MatrixView);
		D3DXMatrixInverse(&_invViewMatrix, 0, &MatrixView);
		D3DXMATRIXA16 matComb;
		D3DXMatrixMultiply(&matComb, &MatrixView, &MatrixProjection);
		frustumPlanes[0].normal.x = matComb._14 + matComb._11;
		frustumPlanes[0].normal.y = matComb._24 + matComb._21;
		frustumPlanes[0].normal.z = matComb._34 + matComb._31;
		frustumPlanes[0].distance = matComb._44 + matComb._41;
		frustumPlanes[1].normal.x = matComb._14 - matComb._11;
		frustumPlanes[1].normal.y = matComb._24 - matComb._21;
		frustumPlanes[1].normal.z = matComb._34 - matComb._31;
		frustumPlanes[1].distance = matComb._44 - matComb._41;
		frustumPlanes[2].normal.x = matComb._14 - matComb._12;
		frustumPlanes[2].normal.y = matComb._24 - matComb._22;
		frustumPlanes[2].normal.z = matComb._34 - matComb._32;
		frustumPlanes[2].distance = matComb._44 - matComb._42;
		frustumPlanes[3].normal.x = matComb._14 + matComb._12;
		frustumPlanes[3].normal.y = matComb._24 + matComb._22;
		frustumPlanes[3].normal.z = matComb._34 + matComb._32;
		frustumPlanes[3].distance = matComb._44 + matComb._42;
		frustumPlanes[4].normal.x = matComb._13;
		frustumPlanes[4].normal.y = matComb._23;
		frustumPlanes[4].normal.z = matComb._33;
		frustumPlanes[4].distance = matComb._43;
		frustumPlanes[5].normal.x = matComb._14 - matComb._13;
		frustumPlanes[5].normal.y = matComb._24 - matComb._23;
		frustumPlanes[5].normal.z = matComb._34 - matComb._33;
		frustumPlanes[5].distance = matComb._44 - matComb._43;
	}
};

Структура FrustumPlane остается без изменений, как и FRUSTUM.

Далее, мы вводим новую глобальную переменную iOctDep. Она будет хранить текущую глубину Octree. Зачем нам это? Мы в первой статье рассматривали несколько условий, для того, чтобы остановить деление дерева. Выбор пал на количество объектов в листе. А теперь мы добавим еще пару возможностей остановки дробления – фиксирование глубины Octree и ограничение по размеру узла.

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

int iMaxObj;		//максимальное допустимое кол-во объектов на лист
int iDepthBoder;	//граница по глубине дерева
int iOctDep = 1;
BBOX bbCurrentBoxVolume( D3DXVECTOR3(0.0f,0.0f,0.0f), D3DXVECTOR3(0.0f,0.0f,0.0f) );
BBOX bbMinBox( D3DXVECTOR3(0.0f,0.0f,0.0f), D3DXVECTOR3(0.0f,0.0f,0.0f) );
BBOX WORLD;

Одновременно с этой переменной мы вводим переменную bbCurrentBoxVolume типа BBOX. Она нужна для корректного определения глубины дерева. Как ее вообще можно определить? Первое, что бросается в глаза – это то, что в зависимости от глубины изменяется и бокс узла (его размеры). Так вот, в этой переменной мы будем хранить бокс узла соответствующий глубине, хранящейся в iOctDep. Например, когда iOctDep равен единице - bbCurrentBoxVolume равен боксу игрового мира (то есть корню дерева) и так далее.

struct LineVertex
{
	D3DXVECTOR3 pos;
	DWORD col;
};

Структура LineVertex тоже не изменилась.

class COCTREE
{
private:
	bool	bChild;
	COCTREE *pParent;		//ссылка на родителя
    	COCTREE	*poChildOctree[8];
	BBOX bbNodeBox;
    vector vObjects;	//массив ссылок на объекты для каждого узла
	void SetChildBox(BBOX *nodes);
	LPDIRECT3DVERTEXBUFFER9	VBOctree;
    	void CreateVBForBox();
	void RenderingObjects();
	void RenderingBoxWire();
public:
bool CreateOctree(const vector &BBObjectArray, const BBOX &nodesize); //здесь создаем октри
    COCTREE();
   ~COCTREE();
   void DrawObjects(FRUSTUM *fr);
   bool AddToOctree(Object* Obj); //добавляем ссылку на новый объект в дерево
   void DrawBoxWire();
   void AllObjectsPass();
   void Release();
   void Init(int _maxObjectInNode, int _iDepthBoder, BBOX _minBox, BBOX _bbCurrentBoxVolume);
};

Сам класс Octree, естественно, претерпел изменения. Добавлена ссылка на родительский узел (pParent). Это нужно для того, чтобы если объект вышел за пределы узла, мы передали его родительскому узлу, пусть он решает что делать дальше. Передавать будем через метод AddToOctree (через этот же метод можно просто добавлять объекты в дерево).


Первый кадр – объект находится внутри одного из узлов


Второй кадр – объект уходит из узла, но его объем все еще не покидает узел.
Пока ничего не делаем.


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

Примечание:
Если в качестве описывающего объема вы будете использовать бокс или сферу, то придется делать более сложную проверку. Функция проверки пересечения объема с узлом должна будет возвращать не true или false, а некоторое значение, полностью описывающее отношение узел-объем. Например, если возвращается значение 0, то объект лежит за пределами бокса, если 1, то одна из вершин ограничивающего бокса лежит внутри объема узла, другие нет и т.д. И возвращающая N, если все вершина объема лежат внутри бокса. Так мы сможем определить момент, когда объект начнет выходить за пределы узла и сразу начать определять бокс, в который он направляется.

 
Страницы: 1 2