Main Page | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | File List | Namespace Members | Data Fields | Globals | Related Pages | Search for 

NL3D::CQuadTree< T >::CQuadNode Class Reference

template<class T>
class NL3D::CQuadTree< T >::CQuadNode


Public Member Functions

void addElement (CNode *newNode)
void clear ()
 CQuadNode ()
bool includeBoxQuad (const NLMISC::CVector &boxmin, const NLMISC::CVector &boxmax)
void insert (const NLMISC::CVector &boxmin, const NLMISC::CVector &boxmax, uint wantdepth, CNode *newNode)
bool intersectBox (std::vector< NLMISC::CPlane > &BVolume)
bool intersectBox (const NLMISC::CVector &boxmin, const NLMISC::CVector &boxmax)
bool intersectBoxQuad (const NLMISC::CVector &boxmin, const NLMISC::CVector &boxmax)
bool isLeaf ()
void select (CBaseNode &selroot, std::vector< NLMISC::CPlane > &BVolume)
void select (CBaseNode &selroot, const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax)
void selectAll (CBaseNode &selroot)
void selectLocalNodes (CBaseNode &selroot)
void split ()

Data Fields

NLMISC::CVector BBoxMax
NLMISC::CVector BBoxMin
bool BBoxNeverRescale
uint Level
uint ListIndex
CBaseNode RootNode
CQuadNode * Sons [4]

Constructor & Destructor Documentation

template<class T>
NL3D::CQuadTree< T >::CQuadNode::CQuadNode (   )  [inline]
 

Definition at line 310 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::BBoxNeverRescale, and NL3D::CQuadTree< T >::CQuadNode::ListIndex. 

00311                 {
00312                         Level=0; Sons[0]= Sons[1]= Sons[2]= Sons[3]= NULL;
00313                         ListIndex= 0;
00314                         BBoxNeverRescale=true;
00315                 }

Member Function Documentation

template<class T>
void NL3D::CQuadTree< T >::CQuadNode::addElement (  CNode *  newNode  )  [inline]
 

Definition at line 432 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::ListIndex, nlassert, NL3D::CQuadTree< T >::CBaseNode::QuadNexts, and NL3D::CQuadTree< T >::CBaseNode::QuadPrevs.

Referenced by NL3D::CQuadTree< T >::CQuadNode::insert(). 

00433                 {
00434                         nlassert(newNode->QuadNexts[ListIndex]==NULL);
00435                         newNode->QuadPrevs[ListIndex]= &RootNode;
00436                         newNode->QuadNexts[ListIndex]= RootNode.QuadNexts[ListIndex];
00437                         if(RootNode.QuadNexts[ListIndex])
00438                                 RootNode.QuadNexts[ListIndex]->QuadPrevs[ListIndex]= newNode;
00439                         RootNode.QuadNexts[ListIndex]= newNode;
00440                 }

template<class T>
void NL3D::CQuadTree< T >::CQuadNode::clear (  void   )  [inline]
 

Definition at line 322 of file quad_tree.h.

References NL3D::CQuadTree< T >::CBaseNode::clear(), NL3D::CQuadTree< T >::CQuadNode::ListIndex, NL3D::CQuadTree< T >::CBaseNode::QuadNexts, and uint.

Referenced by NL3D::CQuadTree< T >::clear(). 

00323                 {
00324                         // Deletons les element dans ce quad node.
00325                         CBaseNode       *p;
00326                         while( (p=RootNode.QuadNexts[ListIndex]) )
00327                         {
00328                                 p->clear();     // On clear les links. => RootNode.QuadNexts[ListIndex] modifié implicitement.
00329                                 delete p;       // On delete cet element!!
00330                         }
00331 
00332                         // Deletons les quad fils.
00333                         for(uint i=0;i<4;i++)
00334                         {
00335                                 if(Sons[i])
00336                                 {
00337                                         Sons[i]->clear();
00338                                         delete Sons[i];
00339                                         Sons[i]= NULL;
00340                                 }
00341                         }
00342                 }

template<class T>
bool NL3D::CQuadTree< T >::CQuadNode::includeBoxQuad (  const NLMISC::CVector &  boxmin,
const NLMISC::CVector &  boxmax
)  [inline]
 

Definition at line 374 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::BBoxMax, NL3D::CQuadTree< T >::CQuadNode::BBoxMin, NLMISC::CVector::x, and NLMISC::CVector::z.

Referenced by NL3D::CQuadTree< T >::CQuadNode::insert(). 

00375                 {
00376                         if( BBoxMin.x<= boxmin.x && BBoxMax.x>= boxmax.x && 
00377                                 BBoxMin.z<= boxmin.z && BBoxMax.z>= boxmax.z)
00378                                 return true;
00379                         else
00380                                 return false;
00381                 }

template<class T>
void NL3D::CQuadTree< T >::CQuadNode::insert (  const NLMISC::CVector &  boxmin,
const NLMISC::CVector &  boxmax,
uint  wantdepth,
CNode *  newNode
)  [inline]
 

Definition at line 443 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::addElement(), NL3D::CQuadTree< T >::CQuadNode::BBoxMax, NL3D::CQuadTree< T >::CQuadNode::BBoxMin, NL3D::CQuadTree< T >::CQuadNode::BBoxNeverRescale, NL3D::CQuadTree< T >::CQuadNode::includeBoxQuad(), NL3D::CQuadTree< T >::CQuadNode::intersectBoxQuad(), NL3D::CQuadTree< T >::CQuadNode::isLeaf(), min, NL3D::CQuadTree< T >::CQuadNode::split(), uint, and NLMISC::CVector::y.

Referenced by NL3D::CQuadTree< T >::insert(). 

00444                 {
00445                         if(Level==0)
00446                         {
00447                                 // Tous les elements qui sortent du quadtree sont forcément dans le noeud root.
00448                                 if(!includeBoxQuad(boxmin, boxmax))
00449                                 {
00450                                         // Il faut agrandir la BBox en Y du quadnode.
00451                                         if(BBoxNeverRescale)
00452                                         {
00453                                                 BBoxMin.y= boxmin.y;
00454                                                 BBoxMax.y= boxmax.y;
00455                                                 BBoxNeverRescale= false;
00456                                         }
00457                                         else
00458                                         {
00459                                                 BBoxMin.y= std::min(boxmin.y, BBoxMin.y);
00460                                                 BBoxMax.y= std::max(boxmax.y, BBoxMax.y);
00461                                         }
00462                                         addElement(newNode);
00463                                         return;
00464                                 }
00465                         }
00466 
00467                         // Si au moins une partie de l'element n'est pas dans le noeud de ce quad, exit.
00468                         if(!intersectBoxQuad(boxmin, boxmax))
00469                                 return;
00470 
00471                         // Que l'on insere ici ou dans les fils, il faut agrandir la BBox en Y du quadnode.
00472                         if(BBoxNeverRescale)
00473                         {
00474                                 BBoxMin.y= boxmin.y;
00475                                 BBoxMax.y= boxmax.y;
00476                                 BBoxNeverRescale= false;
00477                         }
00478                         else
00479                         {
00480                                 BBoxMin.y= std::min(boxmin.y, BBoxMin.y);
00481                                 BBoxMax.y= std::max(boxmax.y, BBoxMax.y);
00482                         }
00483 
00484                         // Si on est au bon, niveau, on a plus qu'à l'insérer dans ce node.
00485                         if(wantdepth==Level)
00486                         {
00487                                         addElement(newNode);
00488                         }
00489                         else
00490                         {
00491                                 // Si le quad est une feuille, il faut le splitter (car on est pas encore arrivé au bon niveau).
00492                                 if(isLeaf())
00493                                         split();
00494 
00495                                 // Et on cherche à mettre l'élément dans un de ces noeuds.
00496                                 Sons[0]->insert(boxmin, boxmax, wantdepth, newNode);
00497                                 Sons[1]->insert(boxmin, boxmax, wantdepth, newNode);
00498                                 Sons[2]->insert(boxmin, boxmax, wantdepth, newNode);
00499                                 Sons[3]->insert(boxmin, boxmax, wantdepth, newNode);
00500                         }
00501 
00502                 }

template<class T>
bool NL3D::CQuadTree< T >::CQuadNode::intersectBox (  std::vector< NLMISC::CPlane > &  BVolume  )  [inline]
 

Definition at line 405 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::BBoxMax, NL3D::CQuadTree< T >::CQuadNode::BBoxMin, sint, NLMISC::CVector::x, NLMISC::CVector::y, and NLMISC::CVector::z. 

00406                 {
00407                         const   NLMISC::CVector &b1=BBoxMin;
00408                         const   NLMISC::CVector &b2=BBoxMax;
00409 
00410                         for(sint i=0;i<(int)BVolume.size();i++)
00411                         {
00412                                 const   NLMISC::CPlane  &plane=BVolume[i];
00413                                 // If only one of the box vertex is IN the plane, then all the box is IN this plane.
00414                                 if(plane* NLMISC::CVector(b1.x, b1.y, b1.z)<=0) continue;
00415                                 if(plane* NLMISC::CVector(b1.x, b1.y, b2.z)<=0) continue;
00416                                 if(plane* NLMISC::CVector(b1.x, b2.y, b1.z)<=0) continue;
00417                                 if(plane* NLMISC::CVector(b1.x, b2.y, b2.z)<=0) continue;
00418                                 if(plane* NLMISC::CVector(b2.x, b1.y, b1.z)<=0) continue;
00419                                 if(plane* NLMISC::CVector(b2.x, b1.y, b2.z)<=0) continue;
00420                                 if(plane* NLMISC::CVector(b2.x, b2.y, b1.z)<=0) continue;
00421                                 if(plane* NLMISC::CVector(b2.x, b2.y, b2.z)<=0) continue;
00422                                 // If ALL box vertices are OUT of this plane, then the box is OUT of the entire volume.
00423                                 return false;
00424                         }
00425                         // TODO. This is a simple box detection. The box is not really clipped and sometimes, the box will said
00426                         // it intersect but it is not the case... Here, We should test the real box volume, against BVolume.
00427                         // But this is more expensive...
00428                         return true;
00429                 }

template<class T>
bool NL3D::CQuadTree< T >::CQuadNode::intersectBox (  const NLMISC::CVector &  boxmin,
const NLMISC::CVector &  boxmax
)  [inline]
 

Definition at line 393 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::BBoxMax, NL3D::CQuadTree< T >::CQuadNode::BBoxMin, NLMISC::CVector::x, NLMISC::CVector::y, and NLMISC::CVector::z.

Referenced by NL3D::CQuadTree< T >::CQuadNode::select(). 

00394                 {
00395                         // inequality and equality is very important, to ensure that a element box will not fit in too many quad boxes.
00396                         if(boxmin.x > BBoxMax.x)        return false;
00397                         if(boxmin.y > BBoxMax.y)        return false;
00398                         if(boxmin.z > BBoxMax.z)        return false;
00399                         if(boxmax.x <= BBoxMin.x)       return false;
00400                         if(boxmax.y <= BBoxMin.y)       return false;
00401                         if(boxmax.z <= BBoxMin.z)       return false;
00402                         return true;
00403                 }

template<class T>
bool NL3D::CQuadTree< T >::CQuadNode::intersectBoxQuad (  const NLMISC::CVector &  boxmin,
const NLMISC::CVector &  boxmax
)  [inline]
 

Definition at line 383 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::BBoxMax, NL3D::CQuadTree< T >::CQuadNode::BBoxMin, NLMISC::CVector::x, and NLMISC::CVector::z.

Referenced by NL3D::CQuadTree< T >::CQuadNode::insert(). 

00384                 {
00385                         // inequality and equality is very important, to ensure that a element box will not fit in too many quad boxes.
00386                         if(boxmin.x > BBoxMax.x)        return false;
00387                         if(boxmin.z > BBoxMax.z)        return false;
00388                         if(boxmax.x <= BBoxMin.x)       return false;
00389                         if(boxmax.z <= BBoxMin.z)       return false;
00390                         return true;
00391                 }

template<class T>
bool NL3D::CQuadTree< T >::CQuadNode::isLeaf (   )  [inline]
 

Definition at line 317 of file quad_tree.h.

Referenced by NL3D::CQuadTree< T >::CQuadNode::insert(), NL3D::CQuadTree< T >::CQuadNode::select(), NL3D::CQuadTree< T >::CQuadNode::selectAll(), and NL3D::CQuadTree< T >::CQuadNode::split(). 

00318                 {
00319                         return Sons[0]==NULL;
00320                 }

template<class T>
void NL3D::CQuadTree< T >::CQuadNode::select (  CBaseNode &  selroot,
std::vector< NLMISC::CPlane > &  BVolume
)  [inline]
 

Definition at line 552 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::intersectBox(), NL3D::CQuadTree< T >::CQuadNode::isLeaf(), NL3D::CQuadTree< T >::CQuadNode::select(), and NL3D::CQuadTree< T >::CQuadNode::selectLocalNodes(). 

00553                 {
00554                         // TODO:
00555                         // ya un bug avec le level0: en effet la bbox n'a pas été agrandie pour contenir les elements.
00556                         if(!intersectBox(BVolume))
00557                                 return;
00558                         selectLocalNodes(selroot);
00559                         if(!isLeaf())
00560                         {
00561                                 Sons[0]->select(selroot, BVolume);
00562                                 Sons[1]->select(selroot, BVolume);
00563                                 Sons[2]->select(selroot, BVolume);
00564                                 Sons[3]->select(selroot, BVolume);
00565                         }
00566                 }

template<class T>
void NL3D::CQuadTree< T >::CQuadNode::select (  CBaseNode &  selroot,
const NLMISC::CVector &  bboxmin,
const NLMISC::CVector &  bboxmax
)  [inline]
 

Definition at line 536 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::intersectBox(), NL3D::CQuadTree< T >::CQuadNode::isLeaf(), and NL3D::CQuadTree< T >::CQuadNode::selectLocalNodes().

Referenced by NL3D::CQuadTree< T >::select(), and NL3D::CQuadTree< T >::CQuadNode::select(). 

00537                 {
00538                         // TODO:
00539                         // ya un bug avec le level0: en effet la bbox n'a pas été agrandie pour contenir les elements.
00540                         if(!intersectBox(bboxmin, bboxmax))
00541                                 return;
00542                         selectLocalNodes(selroot);
00543                         if(!isLeaf())
00544                         {
00545                                 Sons[0]->select(selroot, bboxmin, bboxmax);
00546                                 Sons[1]->select(selroot, bboxmin, bboxmax);
00547                                 Sons[2]->select(selroot, bboxmin, bboxmax);
00548                                 Sons[3]->select(selroot, bboxmin, bboxmax);
00549                         }
00550                 }

template<class T>
void NL3D::CQuadTree< T >::CQuadNode::selectAll (  CBaseNode &  selroot  )  [inline]
 

Definition at line 524 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::isLeaf(), and NL3D::CQuadTree< T >::CQuadNode::selectLocalNodes().

Referenced by NL3D::CQuadTree< T >::selectAll(). 

00525                 {
00526                         selectLocalNodes(selroot);
00527                         if(!isLeaf())
00528                         {
00529                                 Sons[0]->selectAll(selroot);
00530                                 Sons[1]->selectAll(selroot);
00531                                 Sons[2]->selectAll(selroot);
00532                                 Sons[3]->selectAll(selroot);
00533                         }
00534                 }

template<class T>
void NL3D::CQuadTree< T >::CQuadNode::selectLocalNodes (  CBaseNode &  selroot  )  [inline]
 

Definition at line 507 of file quad_tree.h.

References NL3D::CQuadTree< T >::CBaseNode::isSelected(), NL3D::CQuadTree< T >::CQuadNode::ListIndex, NL3D::CQuadTree< T >::CBaseNode::Next, NL3D::CQuadTree< T >::CBaseNode::Prev, and NL3D::CQuadTree< T >::CBaseNode::QuadNexts.

Referenced by NL3D::CQuadTree< T >::CQuadNode::select(), and NL3D::CQuadTree< T >::CQuadNode::selectAll(). 

00508                 {
00509                         CBaseNode       *p= RootNode.QuadNexts[ListIndex];
00510                         while(p)
00511                         {
00512                                 if(!p->isSelected())
00513                                 {
00514                                         p->Prev= &selroot;
00515                                         p->Next= selroot.Next;
00516                                         if(selroot.Next)
00517                                                 selroot.Next->Prev= p;
00518                                         selroot.Next= p;
00519                                 }
00520                                 p=p->QuadNexts[ListIndex];
00521                         }
00522                 }

template<class T>
void NL3D::CQuadTree< T >::CQuadNode::split (   )  [inline]
 

Definition at line 344 of file quad_tree.h.

References NL3D::CQuadTree< T >::CQuadNode::BBoxMax, NL3D::CQuadTree< T >::CQuadNode::BBoxMin, NL3D::CQuadTree< T >::CQuadNode::isLeaf(), NL3D::CQuadTree< T >::CQuadNode::Level, NL3D::CQuadTree< T >::CQuadNode::ListIndex, nlassert, sint, NLMISC::CVector::x, and NLMISC::CVector::z.

Referenced by NL3D::CQuadTree< T >::CQuadNode::insert(). 

00345                 {
00346                         nlassert(isLeaf());
00347                         sint    i;
00348 
00349                         for(i=0;i<4;i++)
00350                         {
00351                                 Sons[i]= new CQuadNode;
00352                                 Sons[i]->Level= Level+1;
00353                                 Sons[i]->ListIndex= i;
00354                         }
00355                         // Middle compute.
00356                         NLMISC::CVector         MidLeft(0,0,0), MidRight(0,0,0), MidTop(0,0,0), MidBottom(0,0,0), Middle(0,0,0);
00357                         MidLeft.x  = BBoxMin.x; MidLeft.z       = (BBoxMin.z + BBoxMax.z)/2;
00358                         MidRight.x = BBoxMax.x; MidRight.z      = (BBoxMin.z + BBoxMax.z)/2;
00359                         MidTop.x   = (BBoxMin.x + BBoxMax.x)/2; MidTop.z   = BBoxMin.z;
00360                         MidBottom.x= (BBoxMin.x + BBoxMax.x)/2; MidBottom.z= BBoxMax.z;
00361                         Middle.x   = MidTop.x; Middle.z = MidLeft.z;
00362                         // Sons compute.
00363                         // Don't care of Y.
00364                         Sons[0]->BBoxMin = BBoxMin; Sons[0]->BBoxMax = Middle; 
00365                         Sons[1]->BBoxMin = MidTop ; Sons[1]->BBoxMax = MidRight; 
00366                         Sons[2]->BBoxMin = MidLeft; Sons[2]->BBoxMax = MidBottom; 
00367                         Sons[3]->BBoxMin = Middle;  Sons[3]->BBoxMax = BBoxMax;
00368 
00369                 }

Field Documentation

template<class T>
NLMISC::CVector NL3D::CQuadTree< T >::CQuadNode::BBoxMax
 

Definition at line 296 of file quad_tree.h.

Referenced by NL3D::CQuadTree< T >::CQuadTree(), NL3D::CQuadTree< T >::create(), NL3D::CQuadTree< T >::CQuadNode::includeBoxQuad(), NL3D::CQuadTree< T >::CQuadNode::insert(), NL3D::CQuadTree< T >::CQuadNode::intersectBox(), NL3D::CQuadTree< T >::CQuadNode::intersectBoxQuad(), and NL3D::CQuadTree< T >::CQuadNode::split().

template<class T>
NLMISC::CVector NL3D::CQuadTree< T >::CQuadNode::BBoxMin
 

Definition at line 296 of file quad_tree.h.

Referenced by NL3D::CQuadTree< T >::CQuadTree(), NL3D::CQuadTree< T >::create(), NL3D::CQuadTree< T >::CQuadNode::includeBoxQuad(), NL3D::CQuadTree< T >::CQuadNode::insert(), NL3D::CQuadTree< T >::CQuadNode::intersectBox(), NL3D::CQuadTree< T >::CQuadNode::intersectBoxQuad(), and NL3D::CQuadTree< T >::CQuadNode::split().

template<class T>
bool NL3D::CQuadTree< T >::CQuadNode::BBoxNeverRescale
 

Definition at line 297 of file quad_tree.h.

Referenced by NL3D::CQuadTree< T >::CQuadNode::CQuadNode(), and NL3D::CQuadTree< T >::CQuadNode::insert().

template<class T>
uint NL3D::CQuadTree< T >::CQuadNode::Level
 

Definition at line 295 of file quad_tree.h.

Referenced by NL3D::CQuadTree< T >::CQuadNode::split().

template<class T>
uint NL3D::CQuadTree< T >::CQuadNode::ListIndex
 

Definition at line 300 of file quad_tree.h.

Referenced by NL3D::CQuadTree< T >::CQuadNode::addElement(), NL3D::CQuadTree< T >::CQuadNode::clear(), NL3D::CQuadTree< T >::CQuadNode::CQuadNode(), NL3D::CQuadTree< T >::CQuadNode::selectLocalNodes(), and NL3D::CQuadTree< T >::CQuadNode::split().

template<class T>
CBaseNode NL3D::CQuadTree< T >::CQuadNode::RootNode
 

Definition at line 299 of file quad_tree.h.

template<class T>
CQuadNode* NL3D::CQuadTree< T >::CQuadNode::Sons[4]
 

Definition at line 298 of file quad_tree.h.

The documentation for this class was generated from the following file:
Generated on Tue Mar 16 07:36:04 2004 for NeL by doxygen 1.3.6