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