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] |
|
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 } |
|
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 } |
|
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 } |
|
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().
|
|
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 } |
|
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 } |
|
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 } |
|
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 } |
|
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 } |
|
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 } |
|
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 } |
|
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().
|
|
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 } |
|
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 } |
|
|
|
Definition at line 297 of file quad_tree.h. Referenced by NL3D::CQuadTree< T >::CQuadNode::CQuadNode(), and NL3D::CQuadTree< T >::CQuadNode::insert(). |
|
Definition at line 295 of file quad_tree.h. Referenced by NL3D::CQuadTree< T >::CQuadNode::split(). |
|
|
Definition at line 299 of file quad_tree.h. |
|
Definition at line 298 of file quad_tree.h. |