Home

nevrax.com

Nevrax.org News Mailing-list Documentation CVS Bugs License

Documentation                       Search   static_quad_grid.h Go to the documentation of this file. /* Copyright, 2000-2002 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_STATIC_QUAD_GRID_H #define NL_STATIC_QUAD_GRID_H #include "nel/misc/types_nl.h" #include "3d/quad_grid.h" namespace NL3D { // *************************************************************************** template<class T> class CStaticQuadGrid { public: CStaticQuadGrid(); ~CStaticQuadGrid(); void build(CQuadGrid<T> &quadGrid); void clear(); const T *select(const NLMISC::CVector &point, uint &numElts); // **************************** private: class CQuadNode { public: T *Nodes; uint NumNodes; CQuadNode() { Nodes= NULL; NumNodes=0; } }; private:// Atttributes. // The big continous array of list of elements. std::vector<T> _Elements; std::vector<CQuadNode> _Grid; sint _Size; sint _SizePower; float _EltSize; NLMISC::CMatrix _ChangeBasis; // return the coordinates on the grid of what include the bbox. void selectPoint(CVector point, sint &x0, sint &y0) { point/= _EltSize; x0= (sint)(floor(point.x)); y0= (sint)(floor(point.y)); x0&= _Size-1; y0&= _Size-1; } }; // *************************************************************************** // *************************************************************************** // *************************************************************************** // *************************************************************************** // Template CStaticQuadGrid implementation. // *************************************************************************** // *************************************************************************** // *************************************************************************** // *************************************************************************** // *************************************************************************** // Init. // *************************************************************************** // *************************************************************************** template<class T> CStaticQuadGrid<T>::CStaticQuadGrid() { _SizePower=4; _Size=1<<_SizePower; _EltSize=1; _ChangeBasis.identity(); _Grid.resize(_Size * _Size); } // *************************************************************************** template<class T> CStaticQuadGrid<T>::~CStaticQuadGrid() { clear(); } // *************************************************************************** template<class T> void CStaticQuadGrid<T>::clear() { // Just clear all vectors _Elements.clear(); _Grid.clear(); // reset _SizePower=4; _Size=1<<_SizePower; _EltSize=1; _ChangeBasis.identity(); _Grid.resize(_Size * _Size); } // *************************************************************************** template<class T> void CStaticQuadGrid<T>::build(CQuadGrid<T> &quadGrid) { clear(); contReset(_Grid); // Copy from quadGrid, and init quads _Size= quadGrid.getSize(); _SizePower= getPowerOf2(_Size); _EltSize= quadGrid.getEltSize(); _ChangeBasis= quadGrid.getBasis(); _Grid.resize(_Size * _Size); NLMISC::CMatrix invBasis= _ChangeBasis.inverted(); // Count number of elements per cell, and total copies of elements uint totalDupElt= 0; sint x,y; for(y=0; y<_Size; y++) { for(x=0; x<_Size; x++) { // Select the center of the case CVector pos; pos.x= (x+0.5f)*_EltSize; pos.y= (y+0.5f)*_EltSize; pos.z= 0.f; // mul by invBasis pos= invBasis * pos; quadGrid.select(pos, pos); // Count elements. uint n= 0; CQuadGrid<T>::CIterator it; for(it= quadGrid.begin(); it!=quadGrid.end(); it++) { n++; } // store. _Grid[y*_Size + x].NumNodes= n; totalDupElt+= n; } } // Resize array copy. _Elements.resize(totalDupElt); // Then reparse all array, filling _Elements and setup quadNodes ptr. uint curDupElt= 0; for(y=0; y<_Size; y++) { for(x=0; x<_Size; x++) { // Select the center of the case CVector pos; pos.x= (x+0.5f)*_EltSize; pos.y= (y+0.5f)*_EltSize; pos.z= 0.f; // mul by invBasis pos= invBasis * pos; quadGrid.select(pos, pos); // Setup quadNode ptr. if (curDupElt < _Elements.size()) _Grid[y*_Size + x].Nodes= &_Elements[curDupElt]; // For all elements. CQuadGrid<T>::CIterator it; for(it= quadGrid.begin(); it!=quadGrid.end(); it++) { // Copy elt in array. _Elements[curDupElt]= *it; // Next elt in array. curDupElt++; } } } // clean up. quadGrid.clearSelection(); } // *************************************************************************** template<class T> const T *CStaticQuadGrid<T>::select(const NLMISC::CVector &pointIn, uint &numElts) { CVector point= _ChangeBasis * pointIn; // Select the case. sint x, y; selectPoint(point, x, y); // get ref on the selection CQuadNode &quadNode= _Grid[y*_Size + x]; numElts= quadNode.NumNodes; return quadNode.Nodes; } } // NL3D #endif // NL_STATIC_QUAD_GRID_H /* End of static_quad_grid.h */