Визуализация октодерева и алгоритмов работы над его структурой. Часть 1


Октодеревья применяются для решения множества задач связанных с оптимизацией, визуализацией в компьютерной графике, да и не только. К примеру, знаменитый и всеми любимый idSoftware, флагман технологий в области компьютерной графики и всего остального, что относится к компьютерным играм, свой новый и, конечно же, высокотехнологичный движок id Tech 6 реализует с инновационной технологией «Sparse Voxel Octree», в основе которой лежит октодерево. Октодеревья позволяют создавать полностью разрушаемую геометрию моделей, как это сделал когда-то главный программист движка DukeNukem 3D, написав сие творение. Если касаться оптимизации, то эту структуру употребляют в движках моделирования физики, очень облегчает работу камню. Ну, и без трассировки лучей не обойдется, здесь тоже применяют октодеревья.

Под катом много трафика!

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

1 Алгоритмы поиска и создания отктодерева





Создадим дерево. В узел будем заносить геометрические параметры вокселя, его цвет для подсветки. Структура будет иметь вид
struct octTree
	{
		mid midle;         //координаты центра вокселя
		float lenght;      //длина стороны вокселя
		char novusial;   //флаг статуса вокселя:  удален/жив
		RGB_color color;//цвет его граней
	       octTree* up;      //родительский узел верхнего уровня
	       octTree* t1;      //дочерние узлы
		octTree* t2;
		octTree* t3;
		octTree* t4;
		octTree* t5;
		octTree* t6;
		octTree* t7;
		octTree* t8;
	};
      
struct mid     //координаты центра вокселя
{
	float x; float y; float z;
};
struct RGB_color  //цвет вокселя
{
	float R; float G; float B;
};


Далее создаем всю структуру с нуля. Dscr – разрешение куба (октодерева), количество субвокселей всего дерева. Descr должен быть кратен 8. mid midle – координаты его центра, float len – длина стророны куба, octTree* up –родительский узел, в первый запуск функции вставим сюда адрес корня *root, octTree** el – указатель куда сохраним созданный узел, в первый запуск вставим адрес адреса корня **root.
 
	//Создаем октодерево. dscr - количество кубов составляющие el куб.
	  void OctObject::makeTr(octTree** el,int dscr,mid midle,float len,octTree* up)
	{
	  mid setmidle; // сюда будем вычислять центр координат для дочернего узла/вокселя
	  if(*el==NULL)
	  {
		   (*el)=new octTree;
		   (*el)->lenght=len; 
		   (*el)->midle=midle;
		   (*el)->novusial=0;
		   (*el)->color.B=(*el)->color.G=(*el)->color.R=1; //Цвет вокселей.
		    null(*el);
		   (*el)->up=up;
	      
		     if(!(dscr%8))
			 { 
				 (*el)->novusial=1;//Рендерим и обрабатываем все подвоксели.

        //вычисляем центры координат для дочерних узлов
        //и рекурсивно передавая это добро, строим их
				 setmidle.x=(*el)->midle.x-(*el)->lenght/4;  /// 1 - ый подкуб
		  setmidle.y=(*el)->midle.y+(*el)->lenght/4;
		  setmidle.z=(*el)->midle.z+(*el)->lenght/4;
			  this->makeTr(&((*el)->t1),dscr/8,setmidle,(*el)->lenght/2,(*el));

			  setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 2 - ый подкуб
		  setmidle.y=(*el)->midle.y+(*el)->lenght/4;
		  setmidle.z=(*el)->midle.z+(*el)->lenght/4;
			  this->makeTr(&((*el)->t2),dscr/8,setmidle,(*el)->lenght/2,(*el));

			  setmidle.x=(*el)->midle.x-(*el)->lenght/4;/// 3 - ый подкуб
		  setmidle.y=(*el)->midle.y-(*el)->lenght/4;
		  setmidle.z=(*el)->midle.z+(*el)->lenght/4;
			  this->makeTr(&((*el)->t3),dscr/8,setmidle,(*el)->lenght/2,(*el));

			  setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 4 - ый подкуб
		  setmidle.y=(*el)->midle.y-(*el)->lenght/4;
		  setmidle.z=(*el)->midle.z+(*el)->lenght/4;
			  this->makeTr(&((*el)->t4),dscr/8,setmidle,(*el)->lenght/2,(*el));

			  setmidle.x=(*el)->midle.x-(*el)->lenght/4;/// 5 - ый подкуб
		  setmidle.y=(*el)->midle.y+(*el)->lenght/4;
		  setmidle.z=(*el)->midle.z-(*el)->lenght/4;
			  this->makeTr(&((*el)->t5),dscr/8,setmidle,(*el)->lenght/2,(*el));

			  setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 6 - ый подкуб
		  setmidle.y=(*el)->midle.y+(*el)->lenght/4;
		  setmidle.z=(*el)->midle.z-(*el)->lenght/4;
			  this->makeTr(&((*el)->t6),dscr/8,setmidle,(*el)->lenght/2,(*el));

			  setmidle.x=(*el)->midle.x-(*el)->lenght/4;/// 7 - ый подкуб
		  setmidle.y=(*el)->midle.y-(*el)->lenght/4;
		  setmidle.z=(*el)->midle.z-(*el)->lenght/4;
			  this->makeTr(&((*el)->t7),dscr/8,setmidle,(*el)->lenght/2,(*el));

			  setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 8 - ый подкуб
		  setmidle.y=(*el)->midle.y-(*el)->lenght/4;
		  setmidle.z=(*el)->midle.z-(*el)->lenght/4;
			  this->makeTr(&((*el)->t8),dscr/8,setmidle,(*el)->lenght/2,(*el));           
			 }
	  }
	  else
	  if(*el==root) // это если первая итерация 		 
	  {
		  setmidle.x=root->midle.x-root->lenght/4;  /// 1 - ый подкуб
		  setmidle.y=root->midle.y+root->lenght/4;
		  setmidle.z=root->midle.z+root->lenght/4;
			  this->makeTr(&((*el)->t1),dscr/8,setmidle,root->lenght/2,root);

			  setmidle.x=root->midle.x+root->lenght/4;/// 2 - ый подкуб
		  setmidle.y=root->midle.y+root->lenght/4;
		  setmidle.z=root->midle.z+root->lenght/4;
			  this->makeTr(&((*el)->t2),dscr/8,setmidle,root->lenght/2,root);

			  setmidle.x=root->midle.x-root->lenght/4;/// 3 - ый подкуб
		  setmidle.y=root->midle.y-root->lenght/4;
		  setmidle.z=root->midle.z+root->lenght/4;
			  this->makeTr(&((*el)->t3),dscr/8,setmidle,root->lenght/2,root);

			  setmidle.x=root->midle.x+root->lenght/4;/// 4 - ый подкуб
		  setmidle.y=root->midle.y-root->lenght/4;
		  setmidle.z=root->midle.z+root->lenght/4;
			  this->makeTr(&((*el)->t4),dscr/8,setmidle,root->lenght/2,root);

			  setmidle.x=root->midle.x-root->lenght/4;/// 5 - ый подкуб
		  setmidle.y=root->midle.y+root->lenght/4;
		  setmidle.z=root->midle.z-root->lenght/4;
			  this->makeTr(&((*el)->t5),dscr/8,setmidle,root->lenght/2,root);

			  setmidle.x=root->midle.x+root->lenght/4;/// 6 - ый подкуб
		  setmidle.y=root->midle.y+root->lenght/4;
		  setmidle.z=root->midle.z-root->lenght/4;
			  this->makeTr(&((*el)->t6),dscr/8,setmidle,root->lenght/2,root);

			  setmidle.x=root->midle.x-root->lenght/4;/// 7 - ый подкуб
		  setmidle.y=root->midle.y-root->lenght/4;
		  setmidle.z=root->midle.z-root->lenght/4;
			  this->makeTr(&((*el)->t7),dscr/8,setmidle,root->lenght/2,root);

			  setmidle.x=root->midle.x+root->lenght/4;/// 8 - ый подкуб
		  setmidle.y=root->midle.y-root->lenght/4;
		  setmidle.z=root->midle.z-root->lenght/4;
			  this->makeTr(&((*el)->t8),dscr/8,setmidle,root->lenght/2,root);
	  }
	 
	 return; 
	}
	

Как видно функция рекурсивная.
Для визуального выделения субвокселя при повороте камеры создадим алгоритм поиска элемента в октодереве.

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

X,y,z – координаты вектора луча в текущий момент времени. octTree *el – узел в котором ищем пересечение.


	//ищем включение в объем вокселя,точки с полученными координатами.
	  octTree* OctObject::seach(float x, float y, float z,octTree *el)
	{

		if(el->t1==NULL)
		 if(el->novusial!=1) //воксел больше не делится и не является удаленным, зачит мы нашли включение.
		  return el;
		 else
			 return NULL;
	   else
	   {
		   if(((el->midle.z+el->lenght/2)>=z)&&(el->midle.z<=z))//1 -я половина по oz - передняя
		   {
			   if(((el->midle.y+el->lenght/2)>=y)&&(el->midle.y<=y))// 1- я половина по oy- нижняя
			   {
				   if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 - я половинна по ox- левая
				   {				  
					   return seach(x,y,z,el->t1);
				   }
				   else
					   if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2- я пловина по ox- правая
					   {					   
						   return seach(x,y,z,el->t2);
					   }
					   else return NULL; // нет включений
			   }
			   else	
			   {
				 if(((el->midle.y-el->lenght/2)<=y)&&(el->midle.y>=y))// 2- половина по oy - верхняя  
				 {
	               if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 - я половинна по ox- левая
				   {                   
					   return seach(x,y,z,el->t3);
				   }
				   else
					   if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2- я пловина по ox- правая
					   {
						   return seach(x,y,z,el->t4);
					   }
					   else return NULL; // нет включений
				 }
				 else return NULL; // нет включений
			   }
			   
		   }
		   else
		   {
			 if(((el->midle.z-el->lenght/2)<=z)&&(el->midle.z>=z))//2 -я половина по oz - задняя    
			 {
				if(((el->midle.y+el->lenght/2)>=y)&&(el->midle.y<=y))// 1- я половина по oy- нижняя
			   {
				   if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 - я половинна по ox- левая
				   {
					  return seach(x,y,z,el->t5);
				   }
				   else
					   if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2- я пловина по ox- правая
					   {					   
						   return seach(x,y,z,el->t6);
					   }
					   else return NULL; // нет включений
			   }
			   else	
			   {
				 if(((el->midle.y-el->lenght/2)<=y)&&(el->midle.y>=y))// 2- половина по oy - верхняя  
				 {
	               if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 - я половинна по ox- левая
				   {				   
					   return seach(x,y,z,el->t7);
				   }
				   else
					   if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2- я пловина по ox- правая
					   {					   
						   return seach(x,y,z,el->t8);
					   }
					   else return NULL; // нет включений
				 }
				 else return NULL; // нет включений
			   }  
			 }
			 else
				 return NULL; //нет включений
		   }
	   }
	  
	}
	


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



	//по проекциям радиус вектора камеры, создаем уравнение прямой и ищем ее пересечение с вокселем.
	  octTree* OctObject::FindVoxeloutside(float a, float b,float c)
	{
	  float x,y,z; octTree *ret;
	 
	     
	  z=(fabs(x=(fabs(a)>=fabs(b) ? a : b))>=fabs(c) ? x : c);//вычисляем одну из восьми областей объема вокселя, с которой,возможно, будет пересекаться наша прямая.
	  if(z==a)
	  {
		   x=a;
// трассируем луч
		  do{
			  if(fabs(a)>=fabs(x))
			  {
				  y=x/a*b; z=x/a*c;//Находим корни уравнения прямой. И проверяем их на включение в объем вокселя.

				  if((ret=seach(x,y,z,root))!=NULL)
				  {			  
	                return ret;
				  }
				  x+=eps*(a>0 ? -1 : 1);
			  }else
				  return NULL;
		  }while(true);
	  }
	  else
	  if(z==b)
	  {
		  y=b;
// трассируем луч
		  do{
			  if(fabs(b)>=fabs(y))
			  {
				  x=y/b*a; z=y/b*c;//Находим корни уравнения прямой. И проверяем их на включение в объем вокселя.

				  if((ret=seach(x,y,z,root))!=NULL)
				  {
	                            return ret;
				  }
				  y+=eps*(b>0 ? -1 : 1);
			  }else
				  return NULL;
		  }while(true);
	  }
	  else
	  if(z==c)
	  {
		  z=c;
// трассируем луч
		  do{
			  if(fabs(c)>=fabs(z))
			  {
				  x=z/c*a; y=z/c*b;//Находим корни уравнения прямой. И проверяем их на включение в объем вокселя.

				  if((ret=seach(x,y,z,root))!=NULL)
				  {
	                return ret;
				  }
				  z+=eps*(c>0 ? -1 : 1);
			  }else
				  return NULL;
		  }while(true);
	  }
	return NULL;  
	}
	


2 Удаление узла



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


	//функция удаления отображения вокселя(отбражения его 6 граней и 6 граней "верхних" вокселей содержащих данный).
	  void OctObject::del(octTree *el)
		{
			if(el==NULL) 
			{
				 return;
			}
			else
			{
				el->novusial=1;// воксел не должен отображаться(удаляем). 
				if(el->up==NULL)//если достигли корня.				
					return;
				if(el->up->novusial)//если верхний уровень/воксел содержащий в себе наш el, 
					return;         //содержит novusial==1,то и все последующие, верхние уровни будут novusial==1, т.е. прекращаем выставление флага.
				del(el->up);
			}
		return;}
	



Далее, надеюсь, в «части 2» расскажу и покажу как все это замутить на OpenGL.

Посмотреть остальную часть кода раскручивающую данный проект в OpenGL, забрать бинарники и весь проект можно здесь.
Поделиться публикацией

Похожие публикации

Комментарии 3

    0
    Ох, а почему t1..t8, а не [8], или даже [3][3]? В первом фрагменте кода цикл так и просится.
      0
      Чтобы не усложнять. Все делалось глубокой ночью, иногда проще многое разложить по полочкам, отдельно. Не писать дополнительный код, как например, цикл с работающей зависимостью от счетчика. Баги ищутся быстрее, да и код нагляден, хоть и громоздок.
        0
        В первом фрагменте кода нужно вывести зависимость арифметических знаков ± для конкретного подкуба, т.е. сделать, грубо говоря, вывести уравнение от счетчика цикла для массивов. Моя цель была не нормализация, а быстрое написание работающей программы. Такие места обычно создают доп. баги, попробуй потом отловить глюк в таком цикле — это время, а время — деньги

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

      Самое читаемое