Home

nevrax.com

Nevrax.org News Mailing-list Documentation CVS Bugs License

Documentation                       Search   quad_grid.h Go to the documentation of this file. /* Copyright, 2000 Nevrax Ltd. * * This file is part of NEVRAX NEL. * NEVRAX NEL is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2, or (at your option) * any later version. * NEVRAX NEL is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * You should have received a copy of the GNU General Public License * along with NEVRAX NEL; see the file COPYING. If not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ #ifndef NL_QUAD_GRID_H #define NL_QUAD_GRID_H #include "nel/misc/debug.h" #include "nel/misc/vector.h" #include "nel/misc/plane.h" #include "nel/misc/matrix.h" #include "nel/misc/stl_block_list.h" #include "nel/misc/common.h" #include <vector> namespace NL3D { using NLMISC::CVector; // *************************************************************************** // Default Size of a block for allocation of elements and elements node list in the grid. #define NL3D_QUAD_GRID_ALLOC_BLOCKSIZE 16 // *************************************************************************** template<class T> class CQuadGrid { public: class CIterator; friend class CIterator; public: CQuadGrid(uint memoryBlockSize= NL3D_QUAD_GRID_ALLOC_BLOCKSIZE); ~CQuadGrid(); void changeBase(const NLMISC::CMatrix& base); void create(uint size, float eltSize); // Get creation parameters. const NLMISC::CMatrix &getBasis() const {return _ChangeBasis;} uint getSize() const {return _Size;} float getEltSize() const {return _EltSize;} void clear(); CIterator erase(CIterator it); CIterator insert(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val); void clearSelection(); void selectAll(); void select(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax); CIterator begin(); CIterator end(); // ================= // ================= // IMPLEMENTATION. // ================= // ================= private:// Classes. class CBaseNode { public: CBaseNode *Prev,*Next; // For selection. bool Selected; // true if owned by _SelectedList, or by _UnSelectedList. CBaseNode() {Prev= Next= NULL;} }; class CNode : public CBaseNode { public: T Elt; uint16 x0,x1; // The location of the elt in the grid. Used for erase(). uint16 y0,y1; }; class CQuadNode { public: NLMISC::CSTLBlockList<CNode*> Nodes; CQuadNode(NLMISC::CBlockMemory<CNode*, false> *bm) : Nodes(bm) {} }; private:// Atttributes. std::vector<CQuadNode> _Grid; sint _Size; sint _SizePower; float _EltSize; NLMISC::CMatrix _ChangeBasis; // Selection. Elements are either in _SelectedList or in _UnSelectedList CBaseNode _SelectedList; // list of elements selected. CBaseNode _UnSelectedList; // circular list of elements not selected // The memory for nodes NLMISC::CBlockMemory<CNode> _NodeBlockMemory; // The memory for node list NLMISC::CBlockMemory<CNode*, false> _NodeListBlockMemory; private:// Methods. // link a node to a root: Selected or UnSelected list void linkToRoot(CBaseNode &root, CBaseNode *ptr) { ptr->Prev= &root; ptr->Next= root.Next; ptr->Prev->Next= ptr; if(ptr->Next) ptr->Next->Prev= ptr; } // return the coordinates on the grid of what include the bbox. void selectQuads(CVector bmin, CVector bmax, sint &x0, sint &x1, sint &y0, sint &y1) { CVector bminp, bmaxp; bminp= bmin; bmaxp= bmax; bmin.minof(bminp, bmaxp); bmax.maxof(bminp, bmaxp); bmin/= _EltSize; bmax/= _EltSize; x0= (sint)(floor(bmin.x)); x1= (sint)(ceil(bmax.x)); y0= (sint)(floor(bmin.y)); y1= (sint)(ceil(bmax.y)); // Very special case where the bbox.size==0 AND position is JUST on an edge of a case. if(x0==x1) x1++; if(y0==y1) y1++; // Manage tiling. if(x1-x0>=_Size) x0=0, x1= _Size; else { x0&= _Size-1; x1&= _Size-1; if(x1<=x0) x1+=_Size; } if(y1-y0>=_Size) y0=0, y1= _Size; else { y0&= _Size-1; y1&= _Size-1; if(y1<=y0) y1+=_Size; } } // If not done, add the node to the selection. void addToSelection(CNode *ptr) { // if not selected if(!ptr->Selected) { // remove from the unselected list. ptr->Prev->Next= ptr->Next; if(ptr->Next) ptr->Next->Prev= ptr->Prev; // Append to front of the _Selected list. linkToRoot(_SelectedList, ptr); // mark it ptr->Selected= true; } } // Try to add each node of the quad node list. void addQuadNodeToSelection(CQuadNode &quad) { typename NLMISC::CSTLBlockList<CNode*>::iterator itNode; for(itNode= quad.Nodes.begin();itNode!=quad.Nodes.end();itNode++) { addToSelection(*itNode); } } public: // CLASS const_iterator. class const_iterator { public: const_iterator() {_Ptr=NULL;} const_iterator(CNode *p) : _Ptr(p) {} const_iterator(const CIterator& x) : _Ptr(x._Ptr) {} const T& operator*() const {return _Ptr->Elt; } // Doesn't work... /*const T* operator->() const {return (&**this); }*/ const_iterator& operator++() {_Ptr = (CNode*)(_Ptr->Next); return (*this); } const_iterator operator++(int) {const_iterator tmp = *this; ++*this; return (tmp); } const_iterator& operator--() {_Ptr = (CNode*)(_Ptr->Prev); return (*this); } const_iterator operator--(int) {const_iterator tmp = *this; --*this; return (tmp); } bool operator==(const const_iterator& x) const {return (_Ptr == x._Ptr); } bool operator!=(const const_iterator& x) const {return (!(*this == x)); } protected: CNode *_Ptr; friend class CQuadGrid<T>; friend class CIterator; }; // CLASS CIterator class CIterator : public const_iterator { public: CIterator() {_Ptr=NULL;} CIterator(CNode *p) : const_iterator(p) {} T& operator*() const {return _Ptr->Elt; } // Doesn't work... /*T* operator->() const {return (&**this); }*/ CIterator& operator++() {_Ptr = (CNode*)(_Ptr->Next); return (*this); } CIterator operator++(int) {CIterator tmp = *this; ++*this; return (tmp); } CIterator& operator--() {_Ptr = (CNode*)(_Ptr->Prev); return (*this); } CIterator operator--(int) {CIterator tmp = *this; --*this; return (tmp); } bool operator==(const const_iterator& x) const {return (_Ptr == x._Ptr); } bool operator!=(const const_iterator& x) const {return (!(*this == x)); } protected: friend class CQuadGrid<T>; }; }; // *************************************************************************** // *************************************************************************** // *************************************************************************** // *************************************************************************** // Template CQuadGrid implementation. // *************************************************************************** // *************************************************************************** // *************************************************************************** // *************************************************************************** // *************************************************************************** // Init. // *************************************************************************** // *************************************************************************** template<class T> CQuadGrid<T>::CQuadGrid(uint memoryBlockSize) : _NodeBlockMemory(memoryBlockSize), _NodeListBlockMemory(memoryBlockSize) { _SizePower=4; _Size=1<<_SizePower; _EltSize=1; _ChangeBasis.identity(); } // *************************************************************************** template<class T> CQuadGrid<T>::~CQuadGrid() { clear(); // must clear the array, before _NodeListBlockMemory.purge() is called. _Grid.clear(); } // *************************************************************************** template<class T> void CQuadGrid<T>::changeBase(const NLMISC::CMatrix& base) { _ChangeBasis= base; } // *************************************************************************** template<class T> void CQuadGrid<T>::create(uint size, float eltSize) { clear(); nlassert(NLMISC::isPowerOf2(size)); nlassert(size<=32768); _SizePower= NLMISC::getPowerOf2(size); _Size=1<<_SizePower; _Grid.resize(_Size*_Size, CQuadNode(&_NodeListBlockMemory)); nlassert(eltSize>0); _EltSize= eltSize; } // *************************************************************************** // insert/erase. // *************************************************************************** // *************************************************************************** template<class T> void CQuadGrid<T>::clear() { CIterator it; selectAll(); while( (it=begin())!=end()) { erase(it); } // Clear the 2 selection... _SelectedList.Next= NULL; _UnSelectedList.Next= NULL; } // *************************************************************************** template<class T> typename CQuadGrid<T>::CIterator CQuadGrid<T>::erase(typename CQuadGrid<T>::CIterator it) { sint x,y; CNode *ptr= it._Ptr; if(!ptr) return end(); // First erase all references to it. //================================== for(y= ptr->y0;y<ptr->y1;y++) { sint xe,ye; ye= y &(_Size-1); for(x= ptr->x0;x<ptr->x1;x++) { xe= x &(_Size-1); CQuadNode &quad= _Grid[(ye<<_SizePower)+xe]; typename NLMISC::CSTLBlockList<CNode*>::iterator itNode; for(itNode= quad.Nodes.begin();itNode!=quad.Nodes.end();itNode++) { if((*itNode)==ptr) { quad.Nodes.erase(itNode); break; } } } } // Then delete it..., and update selection linked list. //===================================================== // remove it from _SelectedList or _UnSelectedList CBaseNode *next= NULL; next= ptr->Next; if(next) next->Prev=ptr->Prev; ptr->Prev->Next= next; // if not selected, then must return NULL if(!ptr->Selected) next= NULL; // delete the object. _NodeBlockMemory.free(ptr); return CIterator((CNode*)next); } // *************************************************************************** template<class T> typename CQuadGrid<T>::CIterator CQuadGrid<T>::insert(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val) { CVector bmin,bmax; bmin= _ChangeBasis*bboxmin; bmax= _ChangeBasis*bboxmax; // init the object. CNode *ptr= _NodeBlockMemory.allocate(); ptr->Elt= val; // Link to _Unselected list. linkToRoot(_UnSelectedList, ptr); // mark as not selected. ptr->Selected= false; // Find which quad include the object. //=================================== sint x0,y0; sint x1,y1; selectQuads(bmin, bmax, x0,x1, y0,y1); ptr->x0= x0; ptr->x1= x1; ptr->y0= y0; ptr->y1= y1; // Then for all of them, insert the node in their list. //===================================================== sint x,y; for(y= ptr->y0;y<ptr->y1;y++) { sint xe,ye; ye= y &(_Size-1); for(x= ptr->x0;x<ptr->x1;x++) { xe= x &(_Size-1); CQuadNode &quad= _Grid[(ye<<_SizePower)+xe]; quad.Nodes.push_back(ptr); } } return CIterator(ptr); } // *************************************************************************** // selection. // *************************************************************************** // *************************************************************************** template<class T> void CQuadGrid<T>::clearSelection() { CBaseNode *ptr= _SelectedList.Next; while(ptr) { // next selected. CBaseNode *nextSelected= ptr->Next; // Link to _Unselected list. linkToRoot(_UnSelectedList, ptr); // mark as not selected. ptr->Selected= false; // next. ptr= nextSelected; } // the selected list is now empty. _SelectedList.Next= NULL; } // *************************************************************************** template<class T> void CQuadGrid<T>::selectAll() { // This is the opposite of clearSelection(). get all that are in _UnSelectedList, // and put them in _SelectedList CBaseNode *ptr= _UnSelectedList.Next; while(ptr) { // next selected. CBaseNode *nextUnSelected= ptr->Next; // Link to _Selected list. linkToRoot(_SelectedList, ptr); // mark as selected. ptr->Selected= true; // next. ptr= nextUnSelected; } // the Unselected list is now empty. _UnSelectedList.Next= NULL; } // *************************************************************************** template<class T> void CQuadGrid<T>::select(const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax) { CVector bmin,bmax; bmin= _ChangeBasis*bboxmin; bmax= _ChangeBasis*bboxmax; clearSelection(); // What are the quads to access? sint x0,y0; sint x1,y1; selectQuads(bmin, bmax, x0,x1, y0,y1); sint x,y; for(y= y0;y<y1;y++) { sint xe,ye; ye= y &(_Size-1); for(x= x0;x<x1;x++) { xe= x &(_Size-1); CQuadNode &quad= _Grid[(ye<<_SizePower)+xe]; addQuadNodeToSelection(quad); } } } // *************************************************************************** template<class T> typename CQuadGrid<T>::CIterator CQuadGrid<T>::begin() { return CIterator((CNode*)(_SelectedList.Next)); } // *************************************************************************** template<class T> typename CQuadGrid<T>::CIterator CQuadGrid<T>::end() { return CIterator(NULL); } } // NL3D #endif // NL_QUAD_GRID_H /* End of quad_grid.h */