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_H
+00027 #define NL_QUAD_GRID_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 "nel/misc/stl_block_list.h"
+00034 #include "nel/misc/common.h"
+00035 #include <vector>
+00036 
+00037 
+00038 namespace NL3D 
+00039 {
+00040 
+00041 
+00042 using NLMISC::CVector;
+00043 
+00044 // ***************************************************************************
+00045 // Default Size of a block for allocation of elements and elements node list in the grid.
+00046 #define NL3D_QUAD_GRID_ALLOC_BLOCKSIZE  16
+00047 
+00048 
+00049 // ***************************************************************************
+00076 template<class T>       class   CQuadGrid
+00077 {
+00078 public:
+00080         class   CIterator;
+00081         friend class    CIterator;
+00082 
+00083 public:
+00084 
+00086         CQuadGrid(uint memoryBlockSize= NL3D_QUAD_GRID_ALLOC_BLOCKSIZE);
+00087 
+00089         ~CQuadGrid();
+00090 
+00092 
+00093 
+00108         void                    changeBase(const NLMISC::CMatrix& base);
+00109 
+00116         void                    create(uint size, float eltSize);
+00117 
+00118         // Get creation parameters.
+00119         const NLMISC::CMatrix   &getBasis() const {return _ChangeBasis;}
+00120         uint                                    getSize() const {return _Size;}
+00121         float                                   getEltSize() const {return _EltSize;}
+00123 
+00125 
+00126 
+00129         void                    clear();
+00130 
+00138         CIterator               erase(CIterator it);
+00139 
+00165         CIterator               insert(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val);
+00167 
+00168 
+00170 
+00171 
+00174         void                    clearSelection();
+00175 
+00179         void                    selectAll();
+00180 
+00187         void                    select(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax);
+00188 
+00189 
+00193         CIterator               begin();
+00194 
+00198         CIterator               end();
+00200 
+00201 
+00202 // =================
+00203 // =================
+00204 // IMPLEMENTATION.
+00205 // =================
+00206 // =================
+00207 private:// Classes.
+00208 
+00209         class   CBaseNode
+00210         {
+00211         public:
+00212                 CBaseNode       *Prev,*Next;    // For selection.
+00213                 bool            Selected;               // true if owned by _SelectedList, or by _UnSelectedList.
+00214                 CBaseNode() {Prev= Next= NULL;}
+00215         };
+00216 
+00217         class   CNode : public CBaseNode
+00218         {
+00219         public:
+00220                 T               Elt;
+00221                 uint16  x0,x1;                  // The location of the elt in the grid. Used for erase().
+00222                 uint16  y0,y1;
+00223         };
+00224 
+00225         class   CQuadNode
+00226         {
+00227         public:
+00228                 NLMISC::CSTLBlockList<CNode*>   Nodes;
+00229 
+00230                 CQuadNode(NLMISC::CBlockMemory<CNode*, false> *bm) : Nodes(bm) {}
+00231         };
+00232 
+00233 private:// Atttributes.
+00234         std::vector<CQuadNode>  _Grid;
+00235         sint                            _Size;
+00236         sint                            _SizePower;
+00237         float                           _EltSize;
+00238         NLMISC::CMatrix         _ChangeBasis;
+00239         // Selection. Elements are either in _SelectedList or in _UnSelectedList
+00240         CBaseNode                       _SelectedList;          // list of elements selected.
+00241         CBaseNode                       _UnSelectedList;        // circular list of elements not selected
+00242         // The memory for nodes
+00243         NLMISC::CBlockMemory<CNode>                                     _NodeBlockMemory;
+00244         // The memory for node list
+00245         NLMISC::CBlockMemory<CNode*, false>                     _NodeListBlockMemory;
+00246 
+00247 
+00248 private:// Methods.
+00249 
+00250         // link a node to a root: Selected or UnSelected list
+00251         void            linkToRoot(CBaseNode &root, CBaseNode *ptr)
+00252         {
+00253                 ptr->Prev= &root;
+00254                 ptr->Next= root.Next;
+00255                 ptr->Prev->Next= ptr;
+00256                 if(ptr->Next)
+00257                         ptr->Next->Prev= ptr;
+00258         }
+00259 
+00260         // return the coordinates on the grid of what include the bbox.
+00261         void            selectQuads(CVector bmin, CVector bmax, sint &x0, sint &x1, sint &y0, sint &y1)
+00262         {
+00263                 CVector         bminp, bmaxp;
+00264                 bminp= bmin;
+00265                 bmaxp= bmax;
+00266                 bmin.minof(bminp, bmaxp);
+00267                 bmax.maxof(bminp, bmaxp);
+00268                 bmin/= _EltSize;
+00269                 bmax/= _EltSize;
+00270                 x0= (sint)(floor(bmin.x));
+00271                 x1= (sint)(ceil(bmax.x));
+00272                 y0= (sint)(floor(bmin.y));
+00273                 y1= (sint)(ceil(bmax.y));
+00274 
+00275                 // Very special case where the bbox.size==0 AND position is JUST on an edge of a case.
+00276                 if(x0==x1)
+00277                         x1++;
+00278                 if(y0==y1)
+00279                         y1++;
+00280 
+00281                 // Manage tiling.
+00282                 if(x1-x0>=_Size)
+00283                         x0=0, x1= _Size;
+00284                 else
+00285                 {
+00286                         x0&= _Size-1;
+00287                         x1&= _Size-1;
+00288                         if(x1<=x0)
+00289                                 x1+=_Size;
+00290                 }
+00291                 if(y1-y0>=_Size)
+00292                         y0=0, y1= _Size;
+00293                 else
+00294                 {
+00295                         y0&= _Size-1;
+00296                         y1&= _Size-1;
+00297                         if(y1<=y0)
+00298                                 y1+=_Size;
+00299                 }
+00300         }
+00301 
+00302         // If not done, add the node to the selection.
+00303         void            addToSelection(CNode    *ptr)
+00304         {
+00305                 // if not selected
+00306                 if(!ptr->Selected)
+00307                 {
+00308                         // remove from the unselected list.
+00309                         ptr->Prev->Next= ptr->Next;
+00310                         if(ptr->Next)
+00311                                 ptr->Next->Prev= ptr->Prev;
+00312 
+00313                         // Append to front of the _Selected list.
+00314                         linkToRoot(_SelectedList, ptr);
+00315 
+00316                         // mark it
+00317                         ptr->Selected= true;
+00318                 }
+00319         }
+00320 
+00321         // Try to add each node of the quad node list.
+00322         void            addQuadNodeToSelection(CQuadNode        &quad)
+00323         {
+00324                 typename NLMISC::CSTLBlockList<CNode*>::iterator        itNode;
+00325                 for(itNode= quad.Nodes.begin();itNode!=quad.Nodes.end();itNode++)
+00326                 {
+00327                         addToSelection(*itNode);
+00328                 }
+00329         }
+00330 
+00331 
+00332 public:
+00333         // CLASS const_iterator.
+00334         class const_iterator
+00335         {
+00336         public:
+00337                 const_iterator()        {_Ptr=NULL;}
+00338                 const_iterator(CNode *p) : _Ptr(p) {}
+00339                 const_iterator(const CIterator& x) : _Ptr(x._Ptr) {}
+00340 
+00341                 const T&        operator*() const
+00342                         {return _Ptr->Elt; }
+00343                 // Doesn't work...
+00344                 /*const T*      operator->() const
+00345                         {return (&**this); }*/
+00346                 const_iterator& operator++()
+00347                         {_Ptr = (CNode*)(_Ptr->Next); return (*this); }
+00348                 const_iterator operator++(int)
+00349                         {const_iterator tmp = *this; ++*this; return (tmp); }
+00350                 const_iterator& operator--()
+00351                         {_Ptr = (CNode*)(_Ptr->Prev); return (*this); }
+00352                 const_iterator operator--(int)
+00353                         {const_iterator tmp = *this; --*this; return (tmp); }
+00354                 bool operator==(const const_iterator& x) const
+00355                         {return (_Ptr == x._Ptr); }
+00356                 bool operator!=(const const_iterator& x) const
+00357                         {return (!(*this == x)); }
+00358         protected:
+00359                 CNode   *_Ptr;
+00360                 friend class CQuadGrid<T>;
+00361                 friend class CIterator;
+00362         };
+00363 
+00364         // CLASS CIterator
+00365         class CIterator : public const_iterator
+00366         {
+00367         public:
+00368                 CIterator()                     {_Ptr=NULL;}
+00369                 CIterator(CNode *p) : const_iterator(p) {}
+00370                 T&      operator*() const
+00371                         {return _Ptr->Elt; }
+00372                 // Doesn't work...
+00373                 /*T*    operator->() const
+00374                         {return (&**this); }*/
+00375                 CIterator& operator++()
+00376                         {_Ptr = (CNode*)(_Ptr->Next); return (*this); }
+00377                 CIterator operator++(int)
+00378                         {CIterator tmp = *this; ++*this; return (tmp); }
+00379                 CIterator& operator--()
+00380                         {_Ptr = (CNode*)(_Ptr->Prev); return (*this); }
+00381                 CIterator operator--(int)
+00382                         {CIterator tmp = *this; --*this; return (tmp); }
+00383                 bool operator==(const const_iterator& x) const
+00384                         {return (_Ptr == x._Ptr); }
+00385                 bool operator!=(const const_iterator& x) const
+00386                         {return (!(*this == x)); }
+00387         protected:
+00388                 friend class CQuadGrid<T>;
+00389         };
+00390 
+00391 
+00392 };
+00393 
+00394 
+00395 // ***************************************************************************
+00396 // ***************************************************************************
+00397 // ***************************************************************************
+00398 // ***************************************************************************
+00399 // Template CQuadGrid implementation.
+00400 // ***************************************************************************
+00401 // ***************************************************************************
+00402 // ***************************************************************************
+00403 // ***************************************************************************
+00404 
+00405 
+00406 // ***************************************************************************
+00407 // Init.
+00408 // ***************************************************************************
+00409 
+00410 
+00411 // ***************************************************************************
+00412 template<class T>       CQuadGrid<T>::CQuadGrid(uint memoryBlockSize) : 
+00413         _NodeBlockMemory(memoryBlockSize), _NodeListBlockMemory(memoryBlockSize)
+00414 {
+00415         _SizePower=4;
+00416         _Size=1<<_SizePower;
+00417         _EltSize=1;
+00418         _ChangeBasis.identity();
+00419 }
+00420 // ***************************************************************************
+00421 template<class T>       CQuadGrid<T>::~CQuadGrid()
+00422 {
+00423         clear();
+00424         // must clear the array, before _NodeListBlockMemory.purge() is called.
+00425         _Grid.clear();
+00426 }
+00427 // ***************************************************************************
+00428 template<class T>       void            CQuadGrid<T>::changeBase(const NLMISC::CMatrix& base)
+00429 {
+00430         _ChangeBasis= base;
+00431 }
+00432 // ***************************************************************************
+00433 template<class T>       void            CQuadGrid<T>::create(uint size, float eltSize)
+00434 {
+00435         clear();
+00436 
+00437         nlassert(NLMISC::isPowerOf2(size));
+00438         nlassert(size<=32768);
+00439         _SizePower= NLMISC::getPowerOf2(size);
+00440         _Size=1<<_SizePower;
+00441         _Grid.resize(_Size*_Size, CQuadNode(&_NodeListBlockMemory));
+00442 
+00443         nlassert(eltSize>0);
+00444         _EltSize= eltSize;
+00445 }
+00446 
+00447 
+00448 // ***************************************************************************
+00449 // insert/erase.
+00450 // ***************************************************************************
+00451 
+00452 
+00453 // ***************************************************************************
+00454 template<class T>       void            CQuadGrid<T>::clear()
+00455 {
+00456         CIterator       it;
+00457         selectAll();
+00458         while( (it=begin())!=end())
+00459         {
+00460                 erase(it);
+00461         }
+00462 
+00463         // Clear the 2 selection...
+00464         _SelectedList.Next= NULL;
+00465         _UnSelectedList.Next= NULL;
+00466 }
+00467 // ***************************************************************************
+00468 template<class T>       typename CQuadGrid<T>::CIterator        CQuadGrid<T>::erase(typename CQuadGrid<T>::CIterator it)
+00469 {
+00470         sint    x,y;
+00471         CNode   *ptr= it._Ptr;
+00472 
+00473         if(!ptr)
+00474                 return end();
+00475 
+00476         // First erase all references to it.
+00477         //==================================
+00478         for(y= ptr->y0;y<ptr->y1;y++)
+00479         {
+00480                 sint    xe,ye;
+00481                 ye= y &(_Size-1);
+00482                 for(x= ptr->x0;x<ptr->x1;x++)
+00483                 {
+00484                         xe= x &(_Size-1);
+00485                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
+00486                         typename NLMISC::CSTLBlockList<CNode*>::iterator        itNode;
+00487                         for(itNode= quad.Nodes.begin();itNode!=quad.Nodes.end();itNode++)
+00488                         {
+00489                                 if((*itNode)==ptr)
+00490                                 {
+00491                                         quad.Nodes.erase(itNode);
+00492                                         break;
+00493                                 }
+00494                         }
+00495                 }
+00496         }
+00497 
+00498         // Then delete it..., and update selection linked list.
+00499         //=====================================================
+00500         // remove it from _SelectedList or _UnSelectedList
+00501         CBaseNode       *next= NULL;
+00502         next= ptr->Next;
+00503         if(next)
+00504                 next->Prev=ptr->Prev;
+00505         ptr->Prev->Next= next;
+00506         // if not selected, then must return NULL
+00507         if(!ptr->Selected)
+00508                 next= NULL;
+00509         // delete the object.
+00510         _NodeBlockMemory.free(ptr);
+00511 
+00512 
+00513         return CIterator((CNode*)next);
+00514 }
+00515 // ***************************************************************************
+00516 template<class T>       typename CQuadGrid<T>::CIterator        CQuadGrid<T>::insert(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val)
+00517 {
+00518         CVector         bmin,bmax;
+00519         bmin= _ChangeBasis*bboxmin;
+00520         bmax= _ChangeBasis*bboxmax;
+00521 
+00522         // init the object.
+00523         CNode   *ptr= _NodeBlockMemory.allocate();
+00524         ptr->Elt= val;
+00525         // Link to _Unselected list.
+00526         linkToRoot(_UnSelectedList, ptr);
+00527         // mark as not selected.
+00528         ptr->Selected= false;
+00529 
+00530 
+00531         // Find which quad include the object.
+00532         //===================================
+00533         sint    x0,y0;
+00534         sint    x1,y1;
+00535         selectQuads(bmin, bmax, x0,x1, y0,y1);
+00536 
+00537         ptr->x0= x0;
+00538         ptr->x1= x1;
+00539         ptr->y0= y0;
+00540         ptr->y1= y1;
+00541 
+00542         // Then for all of them, insert the node in their list.
+00543         //=====================================================
+00544         sint    x,y;
+00545         for(y= ptr->y0;y<ptr->y1;y++)
+00546         {
+00547                 sint    xe,ye;
+00548                 ye= y &(_Size-1);
+00549                 for(x= ptr->x0;x<ptr->x1;x++)
+00550                 {
+00551                         xe= x &(_Size-1);
+00552                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
+00553                         quad.Nodes.push_back(ptr);
+00554                 }
+00555         }
+00556 
+00557         return CIterator(ptr);
+00558 }
+00559 
+00560 
+00561 // ***************************************************************************
+00562 // selection.
+00563 // ***************************************************************************
+00564 
+00565 
+00566 // ***************************************************************************
+00567 template<class T>       void                    CQuadGrid<T>::clearSelection()
+00568 {
+00569         CBaseNode       *ptr= _SelectedList.Next;
+00570         while(ptr)
+00571         {
+00572                 // next selected.
+00573                 CBaseNode       *nextSelected= ptr->Next;
+00574 
+00575                 // Link to _Unselected list.
+00576                 linkToRoot(_UnSelectedList, ptr);
+00577 
+00578                 // mark as not selected.
+00579                 ptr->Selected= false;
+00580 
+00581                 // next.
+00582                 ptr= nextSelected;
+00583         }
+00584 
+00585         // the selected list is now empty.
+00586         _SelectedList.Next= NULL;
+00587 }
+00588 // ***************************************************************************
+00589 template<class T>       void                    CQuadGrid<T>::selectAll()
+00590 {
+00591         // This is the opposite of clearSelection(). get all that are in _UnSelectedList,
+00592         // and put them in _SelectedList
+00593         CBaseNode       *ptr= _UnSelectedList.Next;
+00594         while(ptr)
+00595         {
+00596                 // next selected.
+00597                 CBaseNode       *nextUnSelected= ptr->Next;
+00598 
+00599                 // Link to _Selected list.
+00600                 linkToRoot(_SelectedList, ptr);
+00601 
+00602                 // mark as selected.
+00603                 ptr->Selected= true;
+00604 
+00605                 // next.
+00606                 ptr= nextUnSelected;
+00607         }
+00608 
+00609         // the Unselected list is now empty.
+00610         _UnSelectedList.Next= NULL;
+00611 }
+00612 // ***************************************************************************
+00613 template<class T>       void                    CQuadGrid<T>::select(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax)
+00614 {
+00615         CVector         bmin,bmax;
+00616         bmin= _ChangeBasis*bboxmin;
+00617         bmax= _ChangeBasis*bboxmax;
+00618 
+00619         clearSelection();
+00620 
+00621         // What are the quads to access?
+00622         sint    x0,y0;
+00623         sint    x1,y1;
+00624         selectQuads(bmin, bmax, x0,x1, y0,y1);
+00625 
+00626         sint    x,y;
+00627         for(y= y0;y<y1;y++)
+00628         {
+00629                 sint    xe,ye;
+00630                 ye= y &(_Size-1);
+00631                 for(x= x0;x<x1;x++)
+00632                 {
+00633                         xe= x &(_Size-1);
+00634                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
+00635                         addQuadNodeToSelection(quad);
+00636                 }
+00637         }
+00638 
+00639 }
+00640 // ***************************************************************************
+00641 template<class T>       typename CQuadGrid<T>::CIterator                CQuadGrid<T>::begin()
+00642 {
+00643         return CIterator((CNode*)(_SelectedList.Next));
+00644 }
+00645 // ***************************************************************************
+00646 template<class T>       typename CQuadGrid<T>::CIterator                CQuadGrid<T>::end()
+00647 {
+00648         return CIterator(NULL);
+00649 }
+00650 
+00651 
+00652 } // NL3D
+00653 
+00654 
+00655 #endif // NL_QUAD_GRID_H
+00656 
+00657 /* End of quad_grid.h */
+