nevrax.org : docs

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 #ifndef NL_QUAD_GRID_PACS_H
+00027 #define NL_QUAD_GRID_PACS_H
+00028 
+00029 #include "nel/misc/debug.h"
+00030 #include "nel/misc/vector.h"
+00031 #include "nel/misc/plane.h"
+00032 #include "nel/misc/matrix.h"
+00033 #include <list>
+00034 #include <vector>
+00035 
+00036 
+00037 namespace NLPACS
+00038 {
+00039 
+00040 
+00041 using NLMISC::CVector;
+00042 
+00043 
+00044 // ***************************************************************************
+00064 template<class T>       class   CQuadGrid
+00065 {
+00066 public:
+00068         class   CIterator;
+00069         friend class    CIterator;
+00070 
+00071 public:
+00072 
+00074         CQuadGrid();
+00075 
+00077         ~CQuadGrid();
+00078 
+00080 
+00081 
+00096         void                    changeBase(const NLMISC::CMatrix& base);
+00097 
+00104         void                    create(uint size, float eltSize);
+00106 
+00108 
+00109 
+00110         void                    clear();
+00111 
+00118         CIterator               erase(CIterator it);
+00119 
+00126         CIterator               insert(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val);
+00128 
+00129 
+00131 
+00132 
+00134         void                    clearSelection();
+00135 
+00138         void                    selectAll();
+00139 
+00145         void                    select(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax);
+00146 
+00147 
+00150         CIterator               begin();
+00151 
+00154         CIterator               end();
+00156 
+00157 
+00158 // =================
+00159 // =================
+00160 // IMPLEMENTATION.
+00161 // =================
+00162 // =================
+00163 private:// Classes.
+00164 
+00165         class   CBaseNode
+00166         {
+00167         public:
+00168                 CBaseNode       *Prev,*Next;    // For selection.
+00169                 CBaseNode() {Prev= Next= NULL;}
+00170         };
+00171 
+00172         class   CNode : public CBaseNode
+00173         {
+00174         public:
+00175                 T               Elt;
+00176                 uint16  x0,x1;                  // The location of the elt in the grid. Used for erase().
+00177                 uint16  y0,y1;
+00178         };
+00179 
+00180         class   CQuadNode
+00181         {
+00182         public:
+00183                 std::list<CNode*>       Nodes;
+00184         };
+00185 
+00186 private:// Atttributes.
+00187         std::vector<CQuadNode>  _Grid;
+00188         sint                            _Size;
+00189         sint                            _SizePower;
+00190         float                           _EltSize;
+00191         NLMISC::CMatrix         _ChangeBasis;
+00192         // Selection.
+00193         CBaseNode                       _Selection;
+00194 
+00195 
+00196 private:// Methods.
+00197 
+00198         // return the coordinates on the grid of what include the bbox.
+00199         void            selectQuads(CVector bmin, CVector bmax, sint &x0, sint &x1, sint &y0, sint &y1)
+00200         {
+00201                 CVector         bminp, bmaxp;
+00202                 bminp= bmin;
+00203                 bmaxp= bmax;
+00204                 bmin.minof(bminp, bmaxp);
+00205                 bmax.maxof(bminp, bmaxp);
+00206                 bmin/= _EltSize;
+00207                 bmax/= _EltSize;
+00208                 x0= (sint)(floor(bmin.x));
+00209                 x1= (sint)(ceil(bmax.x));
+00210                 y0= (sint)(floor(bmin.y));
+00211                 y1= (sint)(ceil(bmax.y));
+00212 
+00213                 // Very special case where the bbox.size==0 AND position is JUST on an edge of a case.
+00214                 if(x0==x1)
+00215                         x1++;
+00216                 if(y0==y1)
+00217                         y1++;
+00218 
+00219                 // Manage tiling.
+00220                 if(x1-x0>=_Size)
+00221                         x0=0, x1= _Size;
+00222                 else
+00223                 {
+00224                         x0&= _Size-1;
+00225                         x1&= _Size-1;
+00226                         if(x1<=x0)
+00227                                 x1+=_Size;
+00228                 }
+00229                 if(y1-y0>=_Size)
+00230                         y0=0, y1= _Size;
+00231                 else
+00232                 {
+00233                         y0&= _Size-1;
+00234                         y1&= _Size-1;
+00235                         if(y1<=y0)
+00236                                 y1+=_Size;
+00237                 }
+00238         }
+00239 
+00240         // If not done, add the node to the selection.
+00241         void            addToSelection(CNode    *ptr)
+00242         {
+00243                 if(ptr->Prev==NULL)
+00244                 {
+00245                         // Append to front of the list.
+00246                         ptr->Prev= &_Selection;
+00247                         ptr->Next= _Selection.Next;
+00248                         if(_Selection.Next)
+00249                                 _Selection.Next->Prev= ptr;
+00250                         _Selection.Next= ptr;
+00251                 }
+00252         }
+00253 
+00254         // Try to add each node of the quad node list.
+00255         void            addQuadNodeToSelection(CQuadNode        &quad)
+00256         {
+00257                 std::list<CNode*>::iterator     itNode;
+00258                 for(itNode= quad.Nodes.begin();itNode!=quad.Nodes.end();itNode++)
+00259                 {
+00260                         addToSelection(*itNode);
+00261                 }
+00262         }
+00263 
+00264 
+00265 public:
+00266         // CLASS const_iterator.
+00267         class const_iterator
+00268         {
+00269         public:
+00270                 const_iterator()        {_Ptr=NULL;}
+00271                 const_iterator(CNode *p) : _Ptr(p) {}
+00272                 const_iterator(const CIterator& x) : _Ptr(x._Ptr) {}
+00273 
+00274                 const T&        operator*() const
+00275                         {return _Ptr->Elt; }
+00276                 // Doesn't work...
+00277                 /*const T*      operator->() const
+00278                         {return (&**this); }*/
+00279                 const_iterator& operator++()
+00280                         {_Ptr = (CNode*)(_Ptr->Next); return (*this); }
+00281                 const_iterator operator++(int)
+00282                         {const_iterator tmp = *this; ++*this; return (tmp); }
+00283                 const_iterator& operator--()
+00284                         {_Ptr = (CNode*)(_Ptr->Prev); return (*this); }
+00285                 const_iterator operator--(int)
+00286                         {const_iterator tmp = *this; --*this; return (tmp); }
+00287                 bool operator==(const const_iterator& x) const
+00288                         {return (_Ptr == x._Ptr); }
+00289                 bool operator!=(const const_iterator& x) const
+00290                         {return (!(*this == x)); }
+00291         protected:
+00292                 CNode   *_Ptr;
+00293                 friend class CQuadGrid<T>;
+00294                 friend class CIterator;
+00295         };
+00296 
+00297         // CLASS CIterator
+00298         class CIterator : public const_iterator
+00299         {
+00300         public:
+00301                 CIterator()                     {_Ptr=NULL;}
+00302                 CIterator(CNode *p) : const_iterator(p) {}
+00303                 T&      operator*() const
+00304                         {return _Ptr->Elt; }
+00305                 // Doesn't work...
+00306                 /*T*    operator->() const
+00307                         {return (&**this); }*/
+00308                 CIterator& operator++()
+00309                         {_Ptr = (CNode*)(_Ptr->Next); return (*this); }
+00310                 CIterator operator++(int)
+00311                         {CIterator tmp = *this; ++*this; return (tmp); }
+00312                 CIterator& operator--()
+00313                         {_Ptr = (CNode*)(_Ptr->Prev); return (*this); }
+00314                 CIterator operator--(int)
+00315                         {CIterator tmp = *this; --*this; return (tmp); }
+00316                 bool operator==(const const_iterator& x) const
+00317                         {return (_Ptr == x._Ptr); }
+00318                 bool operator!=(const const_iterator& x) const
+00319                         {return (!(*this == x)); }
+00320         protected:
+00321                 friend class CQuadGrid<T>;
+00322         };
+00323 
+00324 
+00325 };
+00326 
+00327 
+00328 // ***************************************************************************
+00329 // ***************************************************************************
+00330 // ***************************************************************************
+00331 // ***************************************************************************
+00332 // Template CQuadGrid implementation.
+00333 // ***************************************************************************
+00334 // ***************************************************************************
+00335 // ***************************************************************************
+00336 // ***************************************************************************
+00337 
+00338 
+00339 // ***************************************************************************
+00340 // Init.
+00341 // ***************************************************************************
+00342 
+00343 
+00344 // ***************************************************************************
+00345 template<class T>       CQuadGrid<T>::CQuadGrid()
+00346 {
+00347         _SizePower=4;
+00348         _Size=1<<_SizePower;
+00349         _EltSize=1;
+00350         _ChangeBasis.identity();
+00351 }
+00352 // ***************************************************************************
+00353 template<class T>       CQuadGrid<T>::~CQuadGrid()
+00354 {
+00355         clear();
+00356 }
+00357 // ***************************************************************************
+00358 template<class T>       void            CQuadGrid<T>::changeBase(const NLMISC::CMatrix& base)
+00359 {
+00360         _ChangeBasis= base;
+00361 }
+00362 // ***************************************************************************
+00363 template<class T>       void            CQuadGrid<T>::create(uint size, float eltSize)
+00364 {
+00365         clear();
+00366 
+00367         nlassert(isPowerOf2(size));
+00368         nlassert(size<=32768);
+00369         _SizePower= getPowerOf2(size);
+00370         _Size=1<<_SizePower;
+00371         _Grid.resize(_Size*_Size);
+00372 
+00373         nlassert(eltSize>0);
+00374         _EltSize= eltSize;
+00375 }
+00376 
+00377 
+00378 // ***************************************************************************
+00379 // insert/erase.
+00380 // ***************************************************************************
+00381 
+00382 
+00383 // ***************************************************************************
+00384 template<class T>       void            CQuadGrid<T>::clear()
+00385 {
+00386         CIterator       it;
+00387         selectAll();
+00388         while( (it=begin())!=end())
+00389         {
+00390                 erase(it);
+00391         }
+00392 
+00393         // Clear the selection...
+00394         _Selection.Next= NULL;
+00395 }
+00396 // ***************************************************************************
+00397 template<class T>       CQuadGrid<T>::CIterator CQuadGrid<T>::erase(CQuadGrid<T>::CIterator it)
+00398 {
+00399         sint    x,y;
+00400         CNode   *ptr= it._Ptr;
+00401 
+00402         if(!ptr)
+00403                 return end();
+00404 
+00405         // First erase all references to it.
+00406         //==================================
+00407         for(y= ptr->y0;y<ptr->y1;y++)
+00408         {
+00409                 sint    xe,ye;
+00410                 ye= y &(_Size-1);
+00411                 for(x= ptr->x0;x<ptr->x1;x++)
+00412                 {
+00413                         xe= x &(_Size-1);
+00414                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
+00415                         std::list<CNode*>::iterator     itNode;
+00416                         for(itNode= quad.Nodes.begin();itNode!=quad.Nodes.end();itNode++)
+00417                         {
+00418                                 if((*itNode)==ptr)
+00419                                 {
+00420                                         quad.Nodes.erase(itNode);
+00421                                         break;
+00422                                 }
+00423                         }
+00424                 }
+00425         }
+00426 
+00427         // Then delete it..., and update selection linked list.
+00428         //=====================================================
+00429         // if selected.
+00430         CBaseNode       *next= NULL;
+00431         if(ptr->Prev)
+00432         {
+00433                 next= ptr->Next;
+00434                 if(next)
+00435                         next->Prev=ptr->Prev;
+00436                 ptr->Prev->Next= next;
+00437         }
+00438         delete ptr;
+00439 
+00440 
+00441         return CIterator((CNode*)next);
+00442 }
+00443 // ***************************************************************************
+00444 template<class T>       CQuadGrid<T>::CIterator CQuadGrid<T>::insert(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val)
+00445 {
+00446         CVector         bmin,bmax;
+00447         bmin= _ChangeBasis*bboxmin;
+00448         bmax= _ChangeBasis*bboxmax;
+00449 
+00450         CNode   *ptr= new CNode;
+00451         ptr->Elt= val;
+00452 
+00453         // Find which quad include the object.
+00454         //===================================
+00455         sint    x0,y0;
+00456         sint    x1,y1;
+00457         selectQuads(bmin, bmax, x0,x1, y0,y1);
+00458 
+00459         ptr->x0= x0;
+00460         ptr->x1= x1;
+00461         ptr->y0= y0;
+00462         ptr->y1= y1;
+00463 
+00464         // Then for all of them, insert the node in their list.
+00465         //=====================================================
+00466         sint    x,y;
+00467         for(y= ptr->y0;y<ptr->y1;y++)
+00468         {
+00469                 sint    xe,ye;
+00470                 ye= y &(_Size-1);
+00471                 for(x= ptr->x0;x<ptr->x1;x++)
+00472                 {
+00473                         xe= x &(_Size-1);
+00474                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
+00475                         quad.Nodes.push_back(ptr);
+00476                 }
+00477         }
+00478 
+00479         return CIterator(ptr);
+00480 }
+00481 
+00482 
+00483 // ***************************************************************************
+00484 // selection.
+00485 // ***************************************************************************
+00486 
+00487 
+00488 // ***************************************************************************
+00489 template<class T>       void                    CQuadGrid<T>::clearSelection()
+00490 {
+00491         CBaseNode       *ptr= _Selection.Next;
+00492         while(ptr)
+00493         {
+00494                 ptr->Prev= NULL;
+00495                 CBaseNode       *next= ptr->Next;
+00496                 ptr->Next= NULL;
+00497                 ptr= next;
+00498         }
+00499 
+00500         _Selection.Next= NULL;
+00501 }
+00502 // ***************************************************************************
+00503 template<class T>       void                    CQuadGrid<T>::selectAll()
+00504 {
+00505         clearSelection();
+00506         for(sint i=0;i<(sint)_Grid.size();i++)
+00507         {
+00508                 CQuadNode       &quad= _Grid[i];
+00509                 addQuadNodeToSelection(quad);
+00510         }
+00511 }
+00512 // ***************************************************************************
+00513 template<class T>       void                    CQuadGrid<T>::select(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax)
+00514 {
+00515         CVector         bmin,bmax;
+00516         bmin= _ChangeBasis*bboxmin;
+00517         bmax= _ChangeBasis*bboxmax;
+00518 
+00519         clearSelection();
+00520 
+00521         // What are the quads to access?
+00522         sint    x0,y0;
+00523         sint    x1,y1;
+00524         selectQuads(bmin, bmax, x0,x1, y0,y1);
+00525 
+00526         sint    x,y;
+00527         for(y= y0;y<y1;y++)
+00528         {
+00529                 sint    xe,ye;
+00530                 ye= y &(_Size-1);
+00531                 for(x= x0;x<x1;x++)
+00532                 {
+00533                         xe= x &(_Size-1);
+00534                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
+00535                         addQuadNodeToSelection(quad);
+00536                 }
+00537         }
+00538 
+00539 }
+00540 // ***************************************************************************
+00541 template<class T>       CQuadGrid<T>::CIterator         CQuadGrid<T>::begin()
+00542 {
+00543         return CIterator((CNode*)(_Selection.Next));
+00544 }
+00545 // ***************************************************************************
+00546 template<class T>       CQuadGrid<T>::CIterator         CQuadGrid<T>::end()
+00547 {
+00548         return CIterator(NULL);
+00549 }
+00550 
+00551 
+00552 } // NLPACS
+00553 
+00554 
+00555 #endif // NL_QUAD_GRID_H
+00556 
+00557 /* End of quad_grid.h */
+