From 0ea5fc66924303d1bf73ba283a383e2aadee02f2 Mon Sep 17 00:00:00 2001 From: neodarz Date: Sat, 11 Aug 2018 20:21:34 +0200 Subject: Initial commit --- docs/doxygen/nel/quad__tree_8h-source.html | 845 +++++++++++++++++++++++++++++ 1 file changed, 845 insertions(+) create mode 100644 docs/doxygen/nel/quad__tree_8h-source.html (limited to 'docs/doxygen/nel/quad__tree_8h-source.html') diff --git a/docs/doxygen/nel/quad__tree_8h-source.html b/docs/doxygen/nel/quad__tree_8h-source.html new file mode 100644 index 00000000..90bd7e41 --- /dev/null +++ b/docs/doxygen/nel/quad__tree_8h-source.html @@ -0,0 +1,845 @@ + + + + nevrax.org : docs + + + + + + + + + + + + + + +
# Home   # nevrax.com   
+ + + + +
Nevrax
+ + + + + + + + + + +
+ + +
+ Nevrax.org
+ + + + + + + +
#News
#Mailing-list
#Documentation
#CVS
#Bugs
#License
+
+ + + 		+ + +
+Docs + +
+  + + + + + +
Documentation 
+ +
+Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages   Search  
+

quad_tree.h

Go to the documentation of this file.
00001 
+00007 /* Copyright, 2000 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+00024  */
+00025 
+00026 
+00027 #ifndef NL_QUAD_TREE_H
+00028 #define NL_QUAD_TREE_H
+00029 
+00030 #include "nel/misc/debug.h"
+00031 #include "nel/misc/vector.h"
+00032 #include "nel/misc/plane.h"
+00033 #include "nel/misc/matrix.h"
+00034 #include <list>
+00035 #include <vector>
+00036 
+00037 
+00038 namespace       NL3D
+00039 {
+00040 
+00041 
+00042 
+00096 template<class T>       class   CQuadTree
+00097 {
+00098 
+00099 public:
+00101         class   CIterator;
+00102         friend class    CIterator;
+00104         class   CConstIterator;
+00105         friend class    CConstIterator;
+00106 
+00107 public:
+00108 
+00110         CQuadTree();
+00111 
+00113         ~CQuadTree();
+00114 
+00116 
+00117 
+00132         void changeBase(const NLMISC::CMatrix& base);
+00133 
+00140         void            create(uint DepthMax, const NLMISC::CVector& center, float size);
+00142 
+00143 
+00145 
+00146 
+00147         void            clear();
+00148 
+00151         void            eraseAll();
+00152 
+00157         void            erase(CIterator it);
+00158 
+00165         CIterator       insert(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val);
+00167 
+00168 
+00170 
+00171 
+00173         void            clearSelection();
+00174 
+00177         void            selectAll();
+00178 
+00184         void            select(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax);
+00185 
+00191         void            select(const std::vector<NLMISC::CPlane> &BVolume);
+00192 
+00198         void            selectRay(const NLMISC::CVector& source, const NLMISC::CVector& dir);
+00199 
+00205         void            selectSegment(const NLMISC::CVector& source, const NLMISC::CVector& dest);
+00206 
+00209         CIterator       begin();
+00210 
+00213         CIterator       end();
+00215 
+00216 
+00217 
+00218 // =================
+00219 // =================
+00220 // IMPLEMENTATION.
+00221 // =================
+00222 // =================
+00223 private:// Classes.
+00224 
+00225 
+00226         // =================
+00227         // =================
+00228         // CBaseNode.
+00229         // =================
+00230         // =================
+00231         // Links fo an element node class.
+00232         class                   CBaseNode
+00233         {
+00234         public:
+00235                 // for the Selection list.
+00236                 CBaseNode       *Prev, *Next;
+00237                 // for the quadnode list. A node MAY be pointed by 4 quad (each having the same level).
+00238                 CBaseNode       *QuadPrevs[4];
+00239                 CBaseNode       *QuadNexts[4];
+00240 
+00241 
+00242         public:
+00243                 CBaseNode()
+00244                 {
+00245                         Prev=Next=NULL;
+00246                         QuadPrevs[0]= QuadPrevs[1]= QuadPrevs[2]= QuadPrevs[3]= NULL;
+00247                         QuadNexts[0]= QuadNexts[1]= QuadNexts[2]= QuadNexts[3]= NULL;
+00248                 }
+00249                 virtual ~CBaseNode() {}         // Empty destructor, but declare it as virtual...
+00250                 void    clear()                         // update links.
+00251                 {
+00252                         // On le retire de la selection.
+00253                         if(Prev)        Prev->Next= Next;
+00254                         if(Next)        Next->Prev= Prev;
+00255                         Prev=Next=NULL;
+00256                         // On le retire des listes dans les quads.
+00257                         for(uint i=0;i<4;i++)
+00258                         {
+00259                                 if(QuadPrevs[i])        {nlassert(QuadPrevs[i]->QuadNexts[i]==this); QuadPrevs[i]->QuadNexts[i]= QuadNexts[i];}
+00260                                 if(QuadNexts[i])        {nlassert(QuadNexts[i]->QuadPrevs[i]==this); QuadNexts[i]->QuadPrevs[i]= QuadPrevs[i];}
+00261                                 QuadPrevs[i]=NULL;
+00262                                 QuadNexts[i]=NULL;
+00263                         }
+00264                 }
+00265                 bool    isSelected()    // return true if Prev is not NULL!!!
+00266                 {
+00267                         return Prev!=NULL;
+00268                 }
+00269         };
+00270 
+00271 
+00272         // =================
+00273         // =================
+00274         // CNode.
+00275         // =================
+00276         // =================
+00277         // An element node class.
+00278         class                   CNode : public CBaseNode
+00279         {
+00280         public:
+00281                 // A base node, plus the Value.
+00282                 T                       Value;
+00283                 CNode(const T &val) : Value(val) {}
+00284         };
+00285 
+00286 
+00287         // =================
+00288         // =================
+00289         // CQuadNode.
+00290         // =================
+00291         // =================
+00292         class                           CQuadNode
+00293         {
+00294         public:
+00295                 uint                    Level;
+00296                 NLMISC::CVector                 BBoxMin, BBoxMax;
+00297                 bool                    BBoxNeverRescale;
+00298                 CQuadNode               *Sons[4];
+00299                 CBaseNode               RootNode;               // First element of the element list in this quad.
+00300                 uint                    ListIndex;              // [0,3]. index of wich list to follow in "Node.QuadNexts[]".
+00301                 /* Topology of sons (top view: axe x/z):
+00302                         0--1
+00303                         |  |
+00304                         2--3
+00305                 */
+00306                 
+00307 
+00308         public:
+00309                 // ============================================================================================
+00310                 CQuadNode()
+00311                 {
+00312                         Level=0; Sons[0]= Sons[1]= Sons[2]= Sons[3]= NULL;
+00313                         ListIndex= 0;
+00314                         BBoxNeverRescale=true;
+00315                 }
+00316                 // ============================================================================================
+00317                 bool    isLeaf()
+00318                 {
+00319                         return Sons[0]==NULL;
+00320                 }
+00321                 // ============================================================================================
+00322                 void    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                 }
+00343                 // ============================================================================================
+00344                 void    split()
+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                 }
+00370 
+00371 
+00372                 // ============================================================================================
+00373                 // This is a quadtree, so those tests just test against x/z. (the base of the box).
+00374                 bool    includeBoxQuad(const NLMISC::CVector &boxmin, const NLMISC::CVector &boxmax)
+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                 }
+00382                 // ============================================================================================
+00383                 bool    intersectBoxQuad(const NLMISC::CVector &boxmin, const NLMISC::CVector &boxmax)
+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                 }
+00392                 // ============================================================================================
+00393                 bool    intersectBox(const NLMISC::CVector &boxmin, const NLMISC::CVector &boxmax)
+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                 }
+00404                 // ============================================================================================
+00405                 bool    intersectBox(std::vector<NLMISC::CPlane> &BVolume)
+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                 }
+00430 
+00431                 // ============================================================================================
+00432                 void    addElement(CNode *newNode)
+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                 }
+00441                 // ============================================================================================
+00442                 // Insertion of a node in this quad node, or his sons...
+00443                 void    insert(const NLMISC::CVector &boxmin, const NLMISC::CVector &boxmax, uint wantdepth, CNode *newNode)
+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                 }
+00503 
+00504                 
+00505                 // ============================================================================================
+00506                 // Selection.
+00507                 void    selectLocalNodes(CBaseNode      &selroot)
+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                 }
+00523                 // ============================================================================================
+00524                 void    selectAll(CBaseNode     &selroot)
+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                 }
+00535                 // ============================================================================================
+00536                 void    select(CBaseNode &selroot, const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax)
+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                 }
+00551                 // ============================================================================================
+00552                 void            select(CBaseNode &selroot, std::vector<NLMISC::CPlane> &BVolume)
+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                 }
+00567         };
+00568 
+00569 
+00570 
+00571 // =================
+00572 // =================
+00573 // Attributes/Methods/iterators..
+00574 // =================
+00575 // =================
+00576 private:// Attributes.
+00577         CQuadNode       _QuadRoot;
+00578         CBaseNode       _Selection;
+00579         uint            _DepthMax;
+00580         float           _Size;
+00581         NLMISC::CMatrix         _ChangeBasis;
+00582 
+00583 private:// Methods.
+00584 
+00585 
+00586 
+00587 public:
+00588         // CLASS const_iterator.
+00589         class const_iterator
+00590         {
+00591         public:
+00592                 const_iterator()        {_Ptr=NULL;}
+00593                 const_iterator(CNode *p) : _Ptr(p) {}
+00594                 const_iterator(const CIterator& x) : _Ptr(x._Ptr) {}
+00595 
+00596                 const T&        operator*() const
+00597                         {return _Ptr->Value; }
+00598                 // Doesn't work...
+00599                 /*const T*      operator->() const
+00600                         {return (&**this); }*/
+00601                 const_iterator& operator++()
+00602                         {_Ptr = (CNode*)(_Ptr->Next); return (*this); }
+00603                 const_iterator operator++(int)
+00604                         {const_iterator tmp = *this; ++*this; return (tmp); }
+00605                 const_iterator& operator--()
+00606                         {_Ptr = (CNode*)(_Ptr->Prev); return (*this); }
+00607                 const_iterator operator--(int)
+00608                         {const_iterator tmp = *this; --*this; return (tmp); }
+00609                 bool operator==(const const_iterator& x) const
+00610                         {return (_Ptr == x._Ptr); }
+00611                 bool operator!=(const const_iterator& x) const
+00612                         {return (!(*this == x)); }
+00613         protected:
+00614                 CNode   *_Ptr;
+00615                 friend class CQuadTree<T>;
+00616                 friend class CIterator;
+00617         };
+00618 
+00619         // CLASS CIterator
+00620         class CIterator : public const_iterator
+00621         {
+00622         public:
+00623                 CIterator()                     {_Ptr=NULL;}
+00624                 CIterator(CNode *p) : const_iterator(p) {}
+00625                 T&      operator*() const
+00626                         {return _Ptr->Value; }
+00627                 // Doesn't work...
+00628                 /*T*    operator->() const
+00629                         {return (&**this); }*/
+00630                 CIterator& operator++()
+00631                         {_Ptr = (CNode*)(_Ptr->Next); return (*this); }
+00632                 CIterator operator++(int)
+00633                         {CIterator tmp = *this; ++*this; return (tmp); }
+00634                 CIterator& operator--()
+00635                         {_Ptr = (CNode*)(_Ptr->Prev); return (*this); }
+00636                 CIterator operator--(int)
+00637                         {CIterator tmp = *this; --*this; return (tmp); }
+00638                 bool operator==(const const_iterator& x) const
+00639                         {return (_Ptr == x._Ptr); }
+00640                 bool operator!=(const const_iterator& x) const
+00641                         {return (!(*this == x)); }
+00642         protected:
+00643                 friend class CQuadTree<T>;
+00644         };
+00645 
+00646 };
+00647 
+00648 
+00649 
+00650 // ============================================================================================
+00651 // ============================================================================================
+00652 // Template CQuadTree implementation. Construction/Destruction.
+00653 // ============================================================================================
+00654 // ============================================================================================
+00655 
+00656                 
+00657 // ============================================================================================
+00658 template<class T>       CQuadTree<T>::CQuadTree()
+00659 {
+00660         _Selection.Next= NULL;
+00661         _DepthMax= 0;
+00662         _QuadRoot.BBoxMin.set(-0.5, 0, -0.5);
+00663         _QuadRoot.BBoxMax.set( 0.5, 0,  0.5);
+00664         _Size=1;
+00665 
+00666         _ChangeBasis.identity();
+00667 }
+00668 // ============================================================================================
+00669 template<class T>       void CQuadTree<T>::changeBase(const NLMISC::CMatrix& base)
+00670 {
+00671         _ChangeBasis=base;
+00672 }
+00673 // ============================================================================================
+00674 template<class T>       CQuadTree<T>::~CQuadTree<T>()
+00675 {
+00676         clear();
+00677 }
+00678 // ============================================================================================
+00679 template<class T>       void            CQuadTree<T>::clear()
+00680 {
+00681         _QuadRoot.clear();
+00682         _Selection.Next= NULL;
+00683 }
+00684 // ============================================================================================
+00685 template<class T>       void            CQuadTree<T>::create(uint DepthMax, const NLMISC::CVector& center, float size)
+00686 {
+00687         NLMISC::CVector mycenter=_ChangeBasis*center;
+00688         clear();
+00689         _DepthMax= DepthMax;
+00690         _Size= size;
+00691         _QuadRoot.BBoxMin= mycenter-NLMISC::CVector(size/2, 0 , size/2);
+00692         _QuadRoot.BBoxMax= mycenter+NLMISC::CVector(size/2, 0 , size/2);
+00693 }
+00694 
+00695 
+00696 // ============================================================================================
+00697 // ============================================================================================
+00698 // Template CQuadTree implementation.  Element Insertion/Deletion.
+00699 // ============================================================================================
+00700 // ============================================================================================
+00701 
+00702 
+00703 // ============================================================================================
+00704 template<class T>       void            CQuadTree<T>::eraseAll()
+00705 {
+00706         CIterator                               it;
+00707         std::vector<CIterator>  its;
+00708 
+00709         // First, make a copy of all elements.
+00710         selectAll();
+00711         for(it= begin();it!=end();it++)
+00712         {
+00713                 its.push_back(it);
+00714         }
+00715 
+00716         // Then erase them. Must do it OUTSIDE the select loop.
+00717         for(sint i=0;i<(sint)its.size();i++)
+00718         {
+00719                 erase(its[i]);
+00720         }
+00721 }
+00722 // ============================================================================================
+00723 template<class T>       void            CQuadTree<T>::erase(CIterator it)
+00724 {
+00725         CNode   *p=it._Ptr;
+00726         if(p)
+00727         {
+00728                 // Clear links.
+00729                 p->clear();
+00730 
+00731                 // delete it!!
+00732                 delete p;
+00733         }
+00734 }
+00735 // ============================================================================================
+00736 template<class T>       CQuadTree<T>::CIterator CQuadTree<T>::insert(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val)
+00737 {
+00738         NLMISC::CVector myboxmin2=_ChangeBasis*bboxmin;
+00739         NLMISC::CVector myboxmax2=_ChangeBasis*bboxmax;
+00740         NLMISC::CVector myboxmin (std::min (myboxmin2.x, myboxmax2.x), std::min (myboxmin2.y, myboxmax2.y), std::min (myboxmin2.z, myboxmax2.z));
+00741         NLMISC::CVector myboxmax (std::max (myboxmin2.x, myboxmax2.x), std::max (myboxmin2.y, myboxmax2.y), std::max (myboxmin2.z, myboxmax2.z));
+00742 
+00743         CNode   *newNode=new CNode(val);
+00744 
+00745         nlassert(myboxmax.x>=myboxmin.x);
+00746         nlassert(myboxmax.y>=myboxmin.y);
+00747         nlassert(myboxmax.z>=myboxmin.z);
+00748 
+00749         float   boxsize= std::max(myboxmax.x-myboxmin.x, myboxmax.z-myboxmin.z );
+00750         // Prevent float precision problems. Increase bbox size a little.
+00751         boxsize*=1.01f;
+00752         // We must find the level quad which is just bigger.
+00753         float   wantsize=_Size;
+00754         uint    wantdepth=0;
+00755         while(boxsize<wantsize/2 && wantdepth<_DepthMax)
+00756         {
+00757                 wantsize/=2;
+00758                 wantdepth++;
+00759         }
+00760 
+00761         _QuadRoot.insert(myboxmin, myboxmax, wantdepth, newNode);
+00762 
+00763         return CIterator(newNode);
+00764 }
+00765 
+00766 
+00767 // ============================================================================================
+00768 // ============================================================================================
+00769 // Template CQuadTree implementation. Quad Selection, element iteration.
+00770 // ============================================================================================
+00771 // ============================================================================================
+00772 
+00773 
+00774 // ============================================================================================
+00775 template<class T>       void            CQuadTree<T>::clearSelection()
+00776 {
+00777         CBaseNode       *p;
+00778         while(p=_Selection.Next)
+00779         {
+00780                 // On retire ce noeud de la selection. Ce qui va modifier implicitement _Selection.Next.
+00781                 if(p->Prev)     p->Prev->Next= p->Next;
+00782                 if(p->Next)     p->Next->Prev= p->Prev;
+00783                 p->Prev=p->Next=NULL;
+00784         }
+00785 }
+00786 // ============================================================================================
+00787 template<class T>       void            CQuadTree<T>::selectAll()
+00788 {
+00789         clearSelection();
+00790         _QuadRoot.selectAll(_Selection);
+00791 }
+00792 // ============================================================================================
+00793 template<class T>       void            CQuadTree<T>::select(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax)
+00794 {
+00795         NLMISC::CVector myboxmin2=_ChangeBasis*bboxmin;
+00796         NLMISC::CVector myboxmax2=_ChangeBasis*bboxmax;
+00797         NLMISC::CVector bboxminCopy (std::min (myboxmin2.x, myboxmax2.x), std::min (myboxmin2.y, myboxmax2.y), std::min (myboxmin2.z, myboxmax2.z));
+00798         NLMISC::CVector bboxmaxCopy (std::max (myboxmin2.x, myboxmax2.x), std::max (myboxmin2.y, myboxmax2.y), std::max (myboxmin2.z, myboxmax2.z));
+00799 
+00800         clearSelection();
+00801         _QuadRoot.select(_Selection, bboxminCopy, bboxmaxCopy);
+00802 }
+00803 // ============================================================================================
+00804 template<class T>       void            CQuadTree<T>::select(const std::vector<NLMISC::CPlane> &BVolume)
+00805 {
+00806         std::vector<NLMISC::CPlane> BVolumeCopy;
+00807         BVolumeCopy.resize (BVolume.size());
+00808         for (int i=0; i<(int)BVolumeCopy.size(); i++)
+00809         {
+00810                 BVolumeCopy[i]=BVolume[i]*((_ChangeBasis).inverted());
+00811         }
+00812 
+00813         clearSelection();
+00814         _QuadRoot.select(_Selection, BVolumeCopy);
+00815 }
+00816 // ============================================================================================
+00817 template<class T>       void            CQuadTree<T>::selectRay(const NLMISC::CVector& source, const NLMISC::CVector& dir)
+00818 {
+00819         NLMISC::CMatrix mat;
+00820         mat.identity ();
+00821 
+00822         // Set a wrong matrix
+00823         NLMISC::CVector vTmp=dir^((fabs(vTmp*CVector(1,0,0))>0.f)?CVector(1,0,0):CVector(0,1,0));
+00824         mat.setRot (dir, vTmp, dir^vTmp);
+00825 
+00826         // Normalize it Yoyo!
+00827         mat.normalize (NLMISC::CMatrix::XYZ);
+00828 
+00829         // Get the planes..
+00830         std::vector<NLMISC::CPlane> BVolume;
+00831         BVolume.reserve (4);
+00832         
+00833         // Setup the planes
+00834         NLMISC::CPlane plane;
+00835         plane.make (mat.getJ(), source);
+00836         BVolume.push_back (plane);
+00837         plane.make (mat.getK(), source);
+00838         BVolume.push_back (plane);
+00839         plane.make (-mat.getJ(), source);
+00840         BVolume.push_back (plane);
+00841         plane.make (-mat.getK(), source);
+00842         BVolume.push_back (plane);
+00843 
+00844         // Select the nodes
+00845         select (BVolume);
+00846 }
+00847 // ============================================================================================
+00848 template<class T>       void            CQuadTree<T>::selectSegment(const NLMISC::CVector& source, const NLMISC::CVector& dest)
+00849 {
+00850         NLMISC::CMatrix mat;
+00851         mat.identity ();
+00852 
+00853         // Set a wrong matrix
+00854         CVector dir=dest-source;
+00855         NLMISC::CVector vTmp=dir^((fabs(vTmp*CVector(1,0,0))>0.f)?CVector(1,0,0):CVector(0,1,0));
+00856         mat.setRot (dir, vTmp, dir^vTmp);
+00857 
+00858         // Normalize it Yoyo!
+00859         mat.normalize (NLMISC::CMatrix::XYZ);
+00860 
+00861         // Get the planes..
+00862         std::vector<NLMISC::CPlane> BVolume;
+00863         BVolume.reserve (4);
+00864         
+00865         // Setup the planes
+00866         NLMISC::CPlane plane;
+00867         plane.make (mat.getJ(), source);
+00868         BVolume.push_back (plane);
+00869         plane.make (mat.getK(), source);
+00870         BVolume.push_back (plane);
+00871         plane.make (-mat.getJ(), source);
+00872         BVolume.push_back (plane);
+00873         plane.make (-mat.getK(), source);
+00874         BVolume.push_back (plane);
+00875         plane.make (mat.getI(), dest);
+00876         BVolume.push_back (plane);
+00877         plane.make (-mat.getI(), source);
+00878         BVolume.push_back (plane);
+00879 
+00880         // Select the nodes
+00881         select (BVolume);
+00882 }
+00883 // ============================================================================================
+00884 template<class T>       CQuadTree<T>::CIterator CQuadTree<T>::begin()
+00885 {
+00886         return (CNode*)(_Selection.Next);
+00887 }
+00888 // ============================================================================================
+00889 template<class T>       CQuadTree<T>::CIterator CQuadTree<T>::end()
+00890 {
+00891         return CIterator(NULL);
+00892 }
+00893 
+00894 
+00895 }
+00896 
+00897 #endif
+00898 
+
+ + +
                                                                                                                                                                    +
+ + -- cgit v1.2.1