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_PACS_H #define NL_QUAD_GRID_PACS_H #include "nel/misc/debug.h" #include "nel/misc/vector.h" #include "nel/misc/plane.h" #include "nel/misc/matrix.h" #include <list> #include <vector> namespace NLPACS { using NLMISC::CVector; // *************************************************************************** template<class T> class CQuadGrid { public: class CIterator; friend class CIterator; public: CQuadGrid(); ~CQuadGrid(); void changeBase(const NLMISC::CMatrix& base); void create(uint size, float 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. 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: std::list<CNode*> Nodes; }; private:// Atttributes. std::vector<CQuadNode> _Grid; sint _Size; sint _SizePower; float _EltSize; NLMISC::CMatrix _ChangeBasis; // Selection. CBaseNode _Selection; private:// Methods. // 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(ptr->Prev==NULL) { // Append to front of the list. ptr->Prev= &_Selection; ptr->Next= _Selection.Next; if(_Selection.Next) _Selection.Next->Prev= ptr; _Selection.Next= ptr; } } // Try to add each node of the quad node list. void addQuadNodeToSelection(CQuadNode &quad) { std::list<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() { _SizePower=4; _Size=1<<_SizePower; _EltSize=1; _ChangeBasis.identity(); } // *************************************************************************** template<class T> CQuadGrid<T>::~CQuadGrid() { 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(isPowerOf2(size)); nlassert(size<=32768); _SizePower= getPowerOf2(size); _Size=1<<_SizePower; _Grid.resize(_Size*_Size); 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 selection... _Selection.Next= NULL; } // *************************************************************************** template<class T> CQuadGrid<T>::CIterator CQuadGrid<T>::erase(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]; std::list<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. //===================================================== // if selected. CBaseNode *next= NULL; if(ptr->Prev) { next= ptr->Next; if(next) next->Prev=ptr->Prev; ptr->Prev->Next= next; } delete ptr; return CIterator((CNode*)next); } // *************************************************************************** template<class T> 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; CNode *ptr= new CNode; ptr->Elt= val; // 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= _Selection.Next; while(ptr) { ptr->Prev= NULL; CBaseNode *next= ptr->Next; ptr->Next= NULL; ptr= next; } _Selection.Next= NULL; } // *************************************************************************** template<class T> void CQuadGrid<T>::selectAll() { clearSelection(); for(sint i=0;i<(sint)_Grid.size();i++) { CQuadNode &quad= _Grid[i]; addQuadNodeToSelection(quad); } } // *************************************************************************** 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> CQuadGrid<T>::CIterator CQuadGrid<T>::begin() { return CIterator((CNode*)(_Selection.Next)); } // *************************************************************************** template<class T> CQuadGrid<T>::CIterator CQuadGrid<T>::end() { return CIterator(NULL); } } // NLPACS #endif // NL_QUAD_GRID_H /* End of quad_grid.h */