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

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

Изменено: 05.02.2008

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

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

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





Страницы: 1 2

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

Конструктор и деструктор выглядят так:

COCTREE::COCTREE()
{
	for (int i=0; i<8; i++)poChildOctree[i] = NULL;
	VBOctree = NULL;
	pParent=NULL;
	bChild=false;
}

COCTREE::~COCTREE()
{
for (int i=0; i<8; i++)
    	{
		if (poChildOctree[i] != NULL)
        	{
			delete poChildOctree[i];
			poChildOctree[i] = NULL;
		}
	}
	vObjects.clear();
	if (VBOctree != NULL)
	{
		VBOctree->Release();
		VBOctree=NULL;
	}
}

В конструкторе мы обнуляем ссылки на 8 детей и на родителя, обнуляем вершинный буфер и говорим, что у узла нет детей (bChild = false).

В деструкторе мы сначала вызываем деструкторы всех существующих детей и очищаем от них память (delete poChildOctree[i]), после чего очищаем вектор объектов данного узла и удаляем данные из вершинного буфера.

void COCTREE::Init(int _maxObjectInNode, int _iDepthBoder, BBOX _minBox, BBOX _bbCurrentBoxVolume)
{
	bbMinBox           = _minBox;
	bbCurrentBoxVolume = _bbCurrentBoxVolume;
	iDepthBoder        = _iDepthBoder;
	iMaxObj            = _maxObjectInNode;
	WORLD              = _bbCurrentBoxVolume;
}

Отдельно добавляем функцию инициализации дерева. В ней мы задаем параметры, которые у всего дерева будут одинаковыми (а храним мы их глобально). Это bbMinBox (бокс, меньше которого мы делить уже не будем), bbCurrentBoxVolume (хранит размеры минимального бокса, который есть в дереве – для вычисления глубины), iDepthBorder (хранит предельную глубину; если данный узел глубже, чем значение iDepthBorder, то деление прекращаем), iMaxObj (максимальное количество объектов на лист) и WORLD (бокс виртуального мира).

int CalcDepth(BBOX *box)
{
	float MinDiag = WORLD.GetDiagonal();
	for (int i=0; i<iDepthBoder; i++)
	{
		MinDiag /= 2.0f;
		if ( MinDiag<=box->GetDiagonal() )
		{
			return i;
		}
	}
	return 1;
}

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

Далее, немного изменена функция CreateOctree.

bool COCTREE::CreateOctree(const vector<Object*> &BBObjectArray, const BBOX &nodesize)
{
	bbNodeBox = nodesize;
	if ( bbNodeBox.GetDiagonal()<bbCurrentBoxVolume.GetDiagonal() )
	{
		iOctDep++;
		bbCurrentBoxVolume = bbNodeBox;
	}

	CreateVBForBox();

	int ObjectCount = (int)BBObjectArray.size();
	if (	ObjectCount <= iMaxObj ||
		CalcDepth(&bbNodeBox) >= iDepthBoder ||
		bbMinBox.GetDiagonal() >= bbNodeBox.GetDiagonal() )
	{
		for (int i=0; i<ObjectCount; i++) 
		{
			vObjects.push_back(BBObjectArray[i]);
		}
        return true;
	}

	BBOX bbchildnodes[8];
	SetChildBox(bbchildnodes);
    	vector<Object*> bbchildarray[8];

	for (int i=0; i<ObjectCount; i++)
    	{
		for (int j=0; j<8; j++)
        	{	
			if (bbchildnodes[j].PointInBox(&BBObjectArray[i]->pos) == true)
			{
				bbchildarray[j].push_back(BBObjectArray[i]);
			}
		}
	}
	
	for (int i=0; i<8; i++)
	{
		if ( !bbchildarray[i].empty() )
		{
			poChildOctree[i] = new COCTREE;
			if (poChildOctree[i] == NULL) return false;
			if (!poChildOctree[i]->CreateOctree(bbchildarray[i], bbchildnodes[i])) 
				return false;
			poChildOctree[i]->pParent = this;
			this->bChild = true;
		}
	}
	return true;
}

А вот первая абсолютно новая функция AddToOctree. С ее помощью мы будем добавлять объекты в наше дерево. Что она должна сделать?
* Получить объект.
* Проверить находится ли объект в боксе данного узла.
* Если да, то либо добавить объект в данный узел, либо [создать ребенка]/[добавить к существующему ребенку]
* Если нет, то если есть родитель ( = данный узел не корень, в противном случае ничего не делаем – объект ушел за пределы игрового мира), то добавить объект родителю.

bool COCTREE::AddToOctree(Object* Obj)
{
  if ( bbNodeBox.PointInBox( &Obj->pos ) == true )
  {
    int size = (int)vObjects.size();
    if (	bChild == false && (iMaxObj-size>=1  ||
		CalcDepth(&bbNodeBox) >= iDepthBoder ||
		bbMinBox.GetDiagonal() >= (bbNodeBox.GetDiagonal())) )
    {
      vObjects.push_back( Obj );
      return true;
    }
    else
    {
      BBOX bbchildnodes[8];
      SetChildBox(bbchildnodes);
      vector<Object*> bbchildarray[8];
      vObjects.push_back(Obj);
      int VectorSize = (int)vObjects.size();
      for (int i=0; i<8; i++ )
      {
        for (int ObjNum=0; ObjNum<VectorSize; ObjNum++)
        {
          if ( poChildOctree[i] != NULL )
          {
            bChild = true;
            if ( poChildOctree[i]->bbNodeBox.PointInBox( &vObjects[ObjNum]->pos ) == true )
            {
              poChildOctree[i]->AddToOctree( vObjects[ObjNum] );
            }
          }
          else
          {
            if ( bbchildnodes[i].PointInBox(&vObjects[ObjNum]->pos) == true )
            {
              bbchildarray[i].push_back(vObjects[ObjNum]);
            }
          }
        }
        if (poChildOctree[i] == NULL && (!bbchildarray[i].empty()) )
        {
          poChildOctree[i] = new COCTREE;
          if (!poChildOctree[i]->CreateOctree(bbchildarray[i], bbchildnodes[i])) 
              return false;
          poChildOctree[i]->pParent = this;
          this->bChild = true;
        }
      }
      vObjects.clear();
    }
  }
  else if ( pParent != NULL )
  {
    return (pParent->AddToOctree(Obj));
  }
  return true;
}

Функции SetChildBox, DrawBoxWire, DrawObjects, RenderingObjects остаются без изменений.

void COCTREE::SetChildBox(BBOX *nodes)
{
  D3DXVECTOR3 center = bbNodeBox.CalcCenter();
  // верхний левый, ближний;
  nodes[0].min = D3DXVECTOR3( bbNodeBox.min.x, center.y, bbNodeBox.min.z);
  nodes[0].max = D3DXVECTOR3( center.x, bbNodeBox.max.y, center.z);
  // верхний правый, ближний;
  nodes[1].min = D3DXVECTOR3( center.x, center.y, bbNodeBox.min.z);
  nodes[1].max = D3DXVECTOR3( bbNodeBox.max.x, bbNodeBox.max.y, center.z);
  // нижний левый, ближний;
  nodes[2].min = D3DXVECTOR3( bbNodeBox.min.x, bbNodeBox.min.y, bbNodeBox.min.z);
  nodes[2].max = D3DXVECTOR3( center.x, center.y, center.z);
  // нижний правый, ближний;
  nodes[3].min = D3DXVECTOR3( center.x, bbNodeBox.min.y, bbNodeBox.min.z);
  nodes[3].max = D3DXVECTOR3( bbNodeBox.max.x, center.y, center.z);
  // верхний левый, дальний;
  nodes[4].min = D3DXVECTOR3( bbNodeBox.min.x, center.y, center.z);
  nodes[4].max = D3DXVECTOR3( center.x, bbNodeBox.max.y, bbNodeBox.max.z);
  // верхний правый, дальний;
  nodes[5].min = D3DXVECTOR3( center.x, center.y, center.z);
  nodes[5].max = D3DXVECTOR3( bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.max.z);
  // нижний левый, дальний;
  nodes[6].min = D3DXVECTOR3( bbNodeBox.min.x, bbNodeBox.min.y,	center.z);
  nodes[6].max = D3DXVECTOR3( center.x, center.y, bbNodeBox.max.z);
  // нижний правый, дальний;
  nodes[7].min = D3DXVECTOR3( center.x, bbNodeBox.min.y, center.z);
  nodes[7].max = D3DXVECTOR3( bbNodeBox.max.x, center.y, bbNodeBox.max.z);
}

void COCTREE::DrawBoxWire()
{
  for (int i=0; i<8; i++)
  {
    if (poChildOctree[i] != NULL)
    {
      poChildOctree[i]->DrawBoxWire();
    }
  }
  COCTREE::RenderingBoxWire();
}

void COCTREE::DrawObjects(FRUSTUM *fr)
{
  bool bInFrustum = fr->BBoxInFrustum(&bbNodeBox);
  if (bInFrustum)
  {
    for (int i=0; i<8; i++)
    {
      if (poChildOctree[i] != NULL)
      {
         poChildOctree[i]->DrawObjects(fr);
      }
    }
  }
  if (bInFrustum == true && vObjects.size()!=0) COCTREE::RenderingObjects();
}

void COCTREE::RenderingObjects()
{
  extern int NumDrawObject;
  int count = (int)vObjects.size();
  for (int i=0; i<count; i++)
  {
    if (vObjects[i]->bDrawed == false)
    {
      D3DXMATRIX MATRIX_WORLD, scale, rotatex, rotatey, rotatez, rot;
      D3DXMatrixScaling(&scale, 0.3f,0.3f,0.3f);
      D3DXMatrixRotationX(& rotatex, (float)(rand()%3));
      D3DXMatrixRotationY(& rotatey, (float)(rand()%3));
      D3DXMatrixRotationZ(& rotatez, (float)(rand()%3));
      rot = rotatex*rotatey*rotatez;
      D3DXMatrixTranslation(&MATRIX_WORLD, vObjects[i]->pos.x,vObjects[i]->pos.y,vObjects[i]->pos.z);
      MATRIX_WORLD=rot*scale*MATRIX_WORLD;
      D3DDevice->SetTransform(D3DTS_WORLD, &MATRIX_WORLD);
      vObjects[i]->Draw();
      NumDrawObject++;
    }
  }
}

Маленькое дополнение в CreateVBForBox – цвет будем менять в зависимости от размера бокса. Исключительно для удобства и наглядности.

void COCTREE::CreateVBForBox()
{
  D3DDevice->CreateVertexBuffer(19*sizeof(LineVertex),
				D3DUSAGE_WRITEONLY,
				OCTREE_FVF,
				D3DPOOL_MANAGED,
				&VBOctree,
				NULL);
  DWORD color = 0x11ffdd;
  float x = D3DXVec3Length(&(bbNodeBox.CalcCenter() - bbNodeBox.min));
  color *= x;
  LineVertex v[] =
  {
	{ D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.min.y, bbNodeBox.min.z),color,},
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.min.y, bbNodeBox.min.z),color,},
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.min.z),color,}, 
	{ D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.max.y, bbNodeBox.min.z),color,},
	{ D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.min.y, bbNodeBox.min.z),color,}, 
	{ D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.min.y, bbNodeBox.max.z),color,}, 
	{ D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.max.y, bbNodeBox.max.z),color,}, 
	{ D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.max.y, bbNodeBox.min.z),color,},
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.min.z),color,}, 
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.min.z),color,},
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.min.z),color,}, 
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.max.z),color,},
	{ D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.max.y, bbNodeBox.max.z),color,}, 
	{ D3DXVECTOR3(bbNodeBox.min.x, bbNodeBox.min.y, bbNodeBox.max.z),color,},
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.min.y, bbNodeBox.max.z),color,}, 
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.min.y, bbNodeBox.min.z),color,}, 
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.min.z),color,}, 
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.max.y, bbNodeBox.max.z),color,},
	{ D3DXVECTOR3(bbNodeBox.max.x, bbNodeBox.min.y, bbNodeBox.max.z),color,}, 
  };

  void * pBuf;
  VBOctree->Lock( 0, 19 * sizeof(LineVertex), &pBuf, 0 );
  memcpy( pBuf, v, 19 * sizeof(LineVertex));
  VBOctree->Unlock();
}

RenderingBoxWire также без изменений.

void COCTREE::RenderingBoxWire()
{
	D3DXMATRIX MATRIX_WORLD, scale;
	D3DXMatrixTranslation(&MATRIX_WORLD, 0.0f, 0.0f, 0.0f);
	D3DDevice -> SetTransform(D3DTS_WORLD,&MATRIX_WORLD);
	D3DDevice -> SetTexture(0,NULL);
	D3DDevice -> SetStreamSource( 0, VBOctree, 0, sizeof(LineVertex) );
	D3DDevice -> SetFVF( OCTREE_FVF );
	D3DDevice -> DrawPrimitive( D3DPT_LINESTRIP, 0, 18);
}

А вот и вторая абсолютно новая функция. Вызывать ее мы будем каждый кадр. Что она должна делать? Она должна следить за всеми объектами.

В ней мы проходим по всем узлам и по всем объектам:
* Проверяем, не изменил ли объект своего положения (флаг Object::bChangePos).
* Если изменил, то проверяем, вышел ли объект за пределы данного узла.
* Если вышел, то отправляем к родителю.
* Если же нет, то ничего не делаем.
* И в конце небольшие махинации по удалению пустых узлов, а также проверка узла на существование детей.

void COCTREE::AllObjectsPass()
{
// Эту переменную (DRIVER) мы используем как вспомогательную 
// по нажатию на Shift останавливаем и вновь запускаем перемещение объектов
	extern bool DRIVER;
	if (DRIVER)
	for (int i=0; i<8; i++)
    	{
		if (poChildOctree[i] != NULL)
		{
			poChildOctree[i]->AllObjectsPass();
		}
	}

	vector<Object*>::iterator id = vObjects.begin();

	for (; id!=vObjects.end();)
	{
		if ( (*id)->bChangePos == true )
		{
			if (bbNodeBox.PointInBox( &(*id)->pos ) == false )
			{
				if (pParent!=NULL)
				{
					pParent->AddToOctree( (*id) );
				}
				id = vObjects.erase(id);
			}
			else
			{
				id++;
			}
		}
	}
	if (vObjects.empty() )
	{
		for (int y=0; y<8; y++)
		{
			if (poChildOctree[y] != NULL )
			{
				if (poChildOctree[y]->vObjects.empty() )
				{
					if (poChildOctree[y]->bChild == false)
					{
						delete poChildOctree[y];
						poChildOctree[y] = NULL;
					}
				}
			}
		}
		this->bChild = false;
		for (int dsdf=0;dsdf<8; dsdf++) 
			{
			if (poChildOctree[dsdf] != NULL) this->bChild = true;
			}
	}
}

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

#include "OctreeClass.h"	// Подключаем OctreeClass.h к проекту
#define NUMOBJ 100		// Число объектов в массиве
#define BOXSIZE 300		// Размер игрового мира (bbox)
#define OBJINLIST 1		// Максимальное число объектов на один лист

COCTREE Octree;			// Создаем глобальный объект нашего класса Octree
vector<Object> Objects;		// Создаем массив объектов
FRUSTUM Frustum;		// Создаем объект типа FRUSTUM

В функцию инициализации приложения добавляем следующий код:

ЗАПОЛНЯЕМ_ВЕКТОР_Objects_ВСЕМИ_ОБЪЕКТАМИ
// Бокс для игрового мира
BBOX sizeworld;
sizeworld.min = _БЛИЖНИЙ_ЛЕВЫЙ_НИЖНИЙ_УГОЛ_МИРА_;
sizeworld.max = _ДАЛЬНИЙ_ПРАВЙ_ВЕРХНИЙ_УГОЛ_МИРА_;
vector<Object*> tmpArray;	//создаем временный массив указателей
int num=(int)Objects.size();	//для передачи данных в octree
for (int i=0; i<num; i++)
  {
  tmpArray.push_back( &Objects[i]);
  }
BBOX _bbMinBox(_БОКС_МЕНЬШЕ_КОТОРОГО_СОЗДАВАТЬ_УЗЛЫ_НЕ_БУДЕМ);
Octree.Init(OBJINLIST, _ГЛУБИНА_-1_, _bbMinBox, sizeworld);
Octree.CreateOctree(tmpArray, sizeworld);	//строим octree

В функции рисования:

_МЕНЯЕМ_ПОЗИЦИИ_ОБЪЕКТОВ_
Frustum.RefreshFrustum();			//Обновляем пирамиду видимости
Octree.AllObjectsPass();			//проходим по всем объектам
Octree.DrawObjects(&Frustum);			//Рисуем видимые объекты
Octree.DrawBoxWire();				//Рисуем ребра дерева

Вот и все!
Надеюсь, у вас все получится!

4. Исходный код

Исполняемый файл и исходники (DirectX, C++): octree2.zip (0.1 Мб)

 


 

Статья участвует в конкурсе статей по программированию #2 (2007).

 

Страницы: 1 2