Октодеревья применяются для решения множества задач связанных с оптимизацией, визуализацией в компьютерной графике, да и не только. К примеру, знаменитый и всеми любимый 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, забрать бинарники и весь проект можно здесь.
