|
|
Создание
Quad Tree.
Содержание статьи:
Вступление.
Класс квада.
Класс листа
квада.
Quad tree.
Вступление.
к началу статьи
Приветствую всех, кто обратил внимание на эту статью. Вам на ум, наверное, уже приходят различные oct tree, BSP и прочие чудеса алгоритмической мысли, и Вы начинаете потихоньку сомневаться, а стоит ли эта статья Вашего внимания? Так ли полезно будет quad дерево в Вашей игре? Уверяю, польза будет и очень большая. Этим типом деревьев стоит заняться хотя бы из-за того, что очень просто написать весь необходимый программный код и внедрить его. Тем более что в некоторых случаях использовать oct деревья нецелесообразно, а BSP просто нереально (например, когда у Вас есть большая карта, которую не хочется сильно мелко дробить по вертикали). Посему на сцену выходит QUAD TREE.
Класс квада.
к началу статьи
Для начала создадим класс, который реализовывал бы собственно сам квад:
|
#define Q_XY 1
#define Q_YZ 2
#define Q_ZX 3
class cQuad{
public:
cVector4 V1 , V2;
int MODE;
cQuad( cPolygon4 , int );
cQuad( void ){}
bool operator&&( cQuad );
bool operator<<=( cVector4 );
bool operator<<=( cQuad );
void GetRestVertexes( cVector4 & , cVector4 & );
};
|
Сразу обращаю Ваше внимание на три константы – Q_XY, Q_YZ, Q_ZX. Они используются при создании квада и указывают, в какой плоскости он лежит. Дело в том, что я не знал, какая ось у Вас направлена вверх. OY как у меня, или, может OZ. В любом случае мне хотелось сделать этот класс как можно более функциональным.
Наш квад определяется двумя вершинами – V1 и V2, как показано на рисунке. Соответственно, если все координаты точки >= всех координат V1 и <= всех координат V2, то такая точка принадлежит кваду. Отсюда получаем способ создания квада по полигону:
|
cQuad::cQuad( cPolygon4 p , int _MODE ){
MODE = _MODE;
V1.x = _Min( p.v1.x , p.v2.x , p.v3.x );
V1.y = _Min( p.v1.y , p.v2.y , p.v3.y );
V1.z = _Min( p.v1.z , p.v2.z , p.v3.z );
V2.x = _Max( p.v1.x , p.v2.x , p.v3.x );
V2.y = _Max( p.v1.y , p.v2.y , p.v3.y );
V2.z = _Max( p.v1.z , p.v2.z , p.v3.z );
switch( MODE ){
case( Q_XY ):V1.z = 0;V2.z=0;break;
case( Q_YZ ):V1.x = 0;V2.x=0;break;
case( Q_ZX ):V1.y = 0;V2.y=0;break;
}
}
| |
А реализация функции проверки точки на принадлежность кваду выглядит следующим образом:
|
bool cQuad::operator <<=( cVector4 v ){
if( V1 <= v && v <= V2 )
return( 1 );
return( 0 );
}
| |
На базе этого метода создадим метод проверки принадлежности вершин одного квада, другому кваду:
|
bool cQuad::operator<<=( cQuad quad ){
cVector4 V3 , V4;
quad.GetRestVertexes( V3 , V4 );
if( V1 <= quad.V1 && quad.V1 <= V2 )
return( 1 );
if( V1 <= quad.V2 && quad.V2 <= V2 )
return( 1 );
if( V1 <= V3 && V3 <= V2 )
return( 1 );
if( V1 <= V4 && V4 <= V2 )
return( 1 );
return( 0 );
}
| |
Теперь можно писать проверку пересечения квадов.
|
bool cQuad::operator&&( cQuad quad ){
if( *this <<= quad )
return( 1 );
if( quad <<= *this )
return( 1 );
switch( MODE ){
case( Q_XY ):
if( V1.x < quad.V1.x && V2.x > quad.V1.x ){
if( V1.y > quad.V1.y && V1.y < quad.V2.y ){
return( 1 );
}
}
if( quad.V1.x < V1.x && quad.V2.x > V1.x ){
if( V1.y < quad.V1.y && V2.y > quad.V1.y ){
return( 1 );
}
}
break;
case( Q_YZ ):
if( V1.y < quad.V1.y && V2.y > quad.V1.y ){
if( V1.z > quad.V1.z && V1.z < quad.V2.z ){
return( 1 );
}
}
if( quad.V1.x < V1.x && quad.V2.x > V1.x ){
if( V1.y < quad.V1.y && V2.y > quad.V1.y ){
return( 1 );
}
}
break;
case( Q_ZX ):
if( V1.x < quad.V1.x && V2.x > quad.V1.x ){
if( V1.z > quad.V1.z && V1.z < quad.V2.z ){
return( 1 );
}
}
if( quad.V1.x < V1.x && quad.V2.x > V1.x ){
if( V1.z < quad.V1.z && V2.z > quad.V1.z ){
return( 1 );
}
}
break;
}
return( 0 );
}
|
Первые два условных оператора сделаны для того, чтобы корректно обрабатывать ситуации, когда один квад вложен в другой. А вот следующий switch нужно объяснить подробнее: два квада могут пересекаться крест на крест (рисунок 2). Поэтому сначала проверяем V1.x < quad.V1.x && V2.x > quad.V1.x, т.е. вершины квада *this по оси X лежат по разные стороны квада quad и соответственно V1.z > quad.V1.z && V1.z < quad.V2.z – вершины квада quad лежат по оси Z по разные стороны от квада quad. Потом рассматривается симметричный случай. Хочу дополнительно обратить Ваше внимание на то, что следующие две строчки кода эквивалентны (естественно в контексте функции cQuad::operator&&( cQuad quad )): «V1.x < quad.V1.x && V2.x > quad.V1.x» и «V1.x < quad.V1.x && V2.x > quad.V2.x». Действия, когда квад лежит в других плоскостях, аналогичны.
На данном этапе нам осталось разобраться со служебной функцией, которая просто возвращает вершины V3 и V4 (см. рисунок 1).
|
void cQuad::GetRestVertexes( cVector4 &V3 , cVector4 &V4 ){
switch( MODE ){
case( Q_XY ):
V3 = V1;
V3.y = V2.y;
V4 = V1;
V4.x = V2.x;
break;
case( Q_YZ ):
V3 = V1;
V3.z = V2.z;
V4 = V1;
V4.y = V2.y;
break;
case( Q_ZX ):
V3 = V1;
V3.x = V2.x;
V4 = V1;
V4.z = V2.z;
break;
}
}
|
Класс узла дерева.
к началу статьи
|
class cQuadNode{
cArray<cPolygon4> *PArray;
cQuadNode *LowerLeft ,
*UpperLeft ,
*UpperRight ,
*LowerRight;
public:
cQuad Quad;
cQuadNode( void ){
PArray=NULL;
LowerLeft=NULL;
UpperLeft=NULL;
UpperRight=NULL;
LowerRight=NULL;
}
cQuadNode( cPolygon4 , int );
void CreateQuadNode( cVector4 , cVector4 , int );
void SubDivideQuadNode( int );
void operator<<( cPolygon4 );
void RenderQuad( LPDIRECT3DDEVICE8 );
void RenderQuadPolygons( LPDIRECT3DDEVICE8 , cVector4 );
};
| |
Здесь не очень много функций, которые достойны вашего пристального внимания, поэтому остановимся только на самых важных.
|
void cQuadNode::CreateQuadNode( cVector4 _v1 , cVector4 _v2 , int _MODE ){
Quad.V1 = _v1;
Quad.V2 = _v2;
Quad.MODE = _MODE;
switch( _MODE ){
case( Q_XY ):
Quad.V1.z = 0;
Quad.V2.z = 0;
break;
case( Q_YZ ):
Quad.V1.x = 0;
Quad.V2.x = 0;
break;
case( Q_ZX ):
Quad.V1.y = 0;
Quad.V2.y = 0;
break;
}
}
| |
Следующая функция делит исходный квад, и создает подквады, количество которых зависит от константы Level (с каждым новым вызовом, она декрементируется и проверяется на равенство нулю, если обнулилась, то стоп, иначе продолжаем делить).
|
void cQuadNode::SubDivideQuadNode( int Level ){
if( Level ){
cVector4 V3,V4;
Quad.GetRestVertexes( V3 , V4 );
LowerLeft = new cQuadNode;
LowerLeft->CreateQuadNode( Quad.V1 , 0.5 * ( Quad.V1 + Quad.V2 ) , Quad.MODE );
LowerLeft->SubDivideQuadNode( Level - 1 );
UpperLeft = new cQuadNode;
UpperLeft->CreateQuadNode( 0.5 * ( Quad.V1 + V3 ) ,
0.5 * ( V3 + Quad.V2 ) , Quad.MODE );
UpperLeft->SubDivideQuadNode( Level - 1 );
UpperRight = new cQuadNode;
UpperRight->CreateQuadNode( 0.5 * ( Quad.V1 +
Quad.V2 ) , Quad.V2 , Quad.MODE );
UpperRight->SubDivideQuadNode( Level - 1 );
LowerRight = new cQuadNode;
LowerRight->CreateQuadNode( 0.5 * ( Quad.V1 + V4 ) ,
0.5 * ( V4 + Quad.V2 ) , Quad.MODE );
LowerRight->SubDivideQuadNode( Level - 1 );
}
}
| |
Следующая функция отвечает за прогонку полигона по всем вложенным квадам и определение, кода его поместить. Всю саму сложную работы мы выполнили, поэтому расслабимся и насладимся результатами нашего труда:
|
void cQuadNode::operator<< ( cPolygon4 p ){
//у нас есть все четыре листа на каждом уровне
cQuad PQuad( p , Quad.MODE );
if( LowerLeft ){
if( PQuad && LowerLeft->Quad ){
*LowerLeft << p;
}
if( PQuad && UpperLeft->Quad ){
*UpperLeft << p;
}
if( PQuad && UpperRight->Quad ){
*UpperRight << p;
}
if( PQuad && LowerRight->Quad ){
*LowerRight << p;
}
}
else{
if( !PArray ){
PArray = new cArray<cPolygon4>;
}
PArray->AddEnd( p );
}
}
|
Заметьте, что не смотря на то, что PArray (указатель на массив полигонов) есть в каждом узле, полигоны хранятся только в листьях.
Quad tree.
к началу статьи
Настал час Х – можно приступать к созданию собственно дерева, хотя по правде говоря все нужное уже создано, и нам только осталось создать более менее удобные интерфейсы.
|
class cQuadTree{
cQuadNode *RootQuadNode;
public:
cQuadTree( void ){RootQuadNode = NULL;}
void operator<<( cArray<cPolygon4> & );
void operator<<( cPolygon4 );
void CreateTree( cVector4 , cVector4 , int , int );
void RenderQuads( LPDIRECT3DDEVICE8 );
void RenderQuadPolygons( LPDIRECT3DDEVICE8 , cVector4 );
};
cPolygon4 Proj( cPolygon4 p , int MODE ){
switch( MODE ){
case( Q_XY ):
p.v1.z = 0;
p.v2.z = 0;
p.v3.z = 0;
return( p );
break;
case( Q_YZ ):
p.v1.x = 0;
p.v2.x = 0;
p.v3.x = 0;
return( p );
break;
case( Q_ZX ):
p.v1.y = 0;
p.v2.y = 0;
p.v3.y = 0;
return( p );
break;
}
}
void cQuadTree::RenderQuads( LPDIRECT3DDEVICE8 D3DDevice ){
if( RootQuadNode ){
RootQuadNode->RenderQuad( D3DDevice );
}
else{
MessageBox( 0 , "Quad was not built" , 0 , 0 );
exit( 0 );
}
}
void cQuadTree::RenderQuadPolygons( LPDIRECT3DDEVICE8 D3DDevice ,
cVector4 pos ){
if( RootQuadNode ){
switch( RootQuadNode->Quad.MODE ){
case( Q_XY ):pos.z = 0;break;
case( Q_YZ ):pos.x = 0;break;
case( Q_ZX ):pos.y = 0;break;
}
RootQuadNode->RenderQuadPolygons( D3DDevice , pos );
}
else{
MessageBox( 0 , "Quad was not built" , 0 , 0 );
exit( 0 );
}
}
void cQuadTree::CreateTree( cVector4 V1 , cVector4 V2 ,
int MODE , int Level ){
if( RootQuadNode ){
MessageBox( 0 , "Quad tree was already created." , 0 , 0 );
exit( 0 );
}
else{
RootQuadNode = new cQuadNode;
RootQuadNode->CreateQuadNode( V1 , V2 , MODE );
RootQuadNode->SubDivideQuadNode( Level - 1 );
}
}
void cQuadTree::operator<<( cPolygon4 p ){
if( RootQuadNode ){
*RootQuadNode << Proj( p , RootQuadNode->Quad.MODE );
}
else{
MessageBox( 0 , "Quad tree was not built" , 0 , 0 );
exit( 0 );
}
}
void cQuadTree::operator<<( cArray<cPolygon4> &PolyArray ){
if( RootQuadNode ){
for( int i( 0 ) ; i < PolyArray.Cursor ; i++ )
*RootQuadNode << Proj( PolyArray[ i ] , RootQuadNode->Quad.MODE );
}
else{
MessageBox( 0 , "Quad tree was not built" , 0 , 0 );
exit( 0 );
}
}
| |
Я позволю оставить без комментариев приведенный только что код, т.к. он очень прост. Лучше я приведу пример использования созданной конструкции:
|
cQuadTree QuadTree;
//создали все квады и разбили их до нужного уровня
QuadTree.CreateTree( cVector4( -1 , 0 , -1 ) , cVector4( 1 , 0 , 1 ) , Q_ZX , 4 );
//теперь можно закидывать полигоны
QuadTree<<cPolygon4( cVector4( -0.5 , 0 , -0.5 ),
cVector4( -0.5 , 0 , 0.5 ),cVector4( 0.5 , 0 , 0.5 ) );
//собственно теперь можно работать с деревом... как? ну думаю сами разберетесь :)
| |
Вот и подошла к концу статья. Хотя она и не была очень сложной, я все-таки оставляю свой адресок, на всякий случай... мало ли что: dodonov_a_a (_AT__) inbox.ru.
До встречи!
Исходные коды.
|
|
|
