# Home    # nevrax.com   
Nevrax
Nevrax.org
#News
#Mailing-list
#Documentation
#CVS
#Bugs
#License
Docs
 
Documentation  
Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages   Search  

static_quad_grid.h

Go to the documentation of this file.
00001 
00007 /* Copyright, 2000-2002 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_STATIC_QUAD_GRID_H
00027 #define NL_STATIC_QUAD_GRID_H
00028 
00029 #include "nel/misc/types_nl.h"
00030 #include "3d/quad_grid.h"
00031 
00032 
00033 namespace NL3D 
00034 {
00035 
00036 
00037 // ***************************************************************************
00050 template<class T>
00051 class CStaticQuadGrid
00052 {
00053 public:
00054 
00056         CStaticQuadGrid();
00058         ~CStaticQuadGrid();
00059 
00060 
00062 
00063 
00067         void                    build(CQuadGrid<T> &quadGrid);
00068 
00071         void                    clear();
00072 
00074 
00075 
00077 
00078 
00085         const T                 *select(const NLMISC::CVector &point, uint &numElts);
00087 
00088 
00089 // ****************************
00090 private:
00091         class   CQuadNode
00092         {
00093         public:
00094                 T                               *Nodes;
00095                 uint                    NumNodes;
00096 
00097                 CQuadNode() 
00098                 {
00099                         Nodes= NULL; NumNodes=0; 
00100                 }
00101         };
00102 
00103 private:// Atttributes.
00104         // The big continous array of list of elements.
00105         std::vector<T>                  _Elements;
00106         std::vector<CQuadNode>  _Grid;
00107         sint                            _Size;
00108         sint                            _SizePower;
00109         float                           _EltSize;
00110         NLMISC::CMatrix         _ChangeBasis;
00111 
00112 
00113         // return the coordinates on the grid of what include the bbox.
00114         void            selectPoint(CVector point, sint &x0, sint &y0)
00115         {
00116                 point/= _EltSize;
00117                 x0= (sint)(floor(point.x));
00118                 y0= (sint)(floor(point.y));
00119 
00120                 x0&= _Size-1;
00121                 y0&= _Size-1;
00122         }
00123 
00124 
00125 };
00126 
00127 
00128 // ***************************************************************************
00129 // ***************************************************************************
00130 // ***************************************************************************
00131 // ***************************************************************************
00132 // Template CStaticQuadGrid implementation.
00133 // ***************************************************************************
00134 // ***************************************************************************
00135 // ***************************************************************************
00136 // ***************************************************************************
00137 
00138 
00139 // ***************************************************************************
00140 // Init.
00141 // ***************************************************************************
00142 
00143 
00144 // ***************************************************************************
00145 template<class T>       
00146 CStaticQuadGrid<T>::CStaticQuadGrid()
00147 {
00148         _SizePower=4;
00149         _Size=1<<_SizePower;
00150         _EltSize=1;
00151         _ChangeBasis.identity();
00152         _Grid.resize(_Size * _Size);
00153 }
00154 // ***************************************************************************
00155 template<class T>       
00156 CStaticQuadGrid<T>::~CStaticQuadGrid()
00157 {
00158         clear();
00159 }
00160 
00161 
00162 // ***************************************************************************
00163 template<class T>       
00164 void                    CStaticQuadGrid<T>::clear()
00165 {
00166         // Just clear all vectors
00167         _Elements.clear();
00168         _Grid.clear();
00169 
00170         // reset
00171         _SizePower=4;
00172         _Size=1<<_SizePower;
00173         _EltSize=1;
00174         _ChangeBasis.identity();
00175         _Grid.resize(_Size * _Size);
00176 }
00177 
00178 
00179 // ***************************************************************************
00180 template<class T>       
00181 void                    CStaticQuadGrid<T>::build(CQuadGrid<T> &quadGrid)
00182 {
00183         clear();
00184         contReset(_Grid);
00185 
00186         // Copy from quadGrid, and init quads
00187         _Size= quadGrid.getSize();
00188         _SizePower= getPowerOf2(_Size);
00189         _EltSize= quadGrid.getEltSize();
00190         _ChangeBasis= quadGrid.getBasis();
00191         _Grid.resize(_Size * _Size);
00192 
00193         NLMISC::CMatrix         invBasis= _ChangeBasis.inverted();
00194 
00195         // Count number of elements per cell, and total copies of elements
00196         uint    totalDupElt= 0;
00197         sint    x,y;
00198         for(y=0; y<_Size; y++)
00199         {
00200                 for(x=0; x<_Size; x++)
00201                 {
00202                         // Select the center of the case
00203                         CVector pos;
00204                         pos.x= (x+0.5f)*_EltSize;
00205                         pos.y= (y+0.5f)*_EltSize;
00206                         pos.z= 0.f;
00207                         // mul by invBasis
00208                         pos= invBasis * pos;
00209                         quadGrid.select(pos, pos);
00210 
00211                         // Count elements.
00212                         uint    n= 0;
00213                         CQuadGrid<T>::CIterator it;
00214                         for(it= quadGrid.begin(); it!=quadGrid.end(); it++)
00215                         {
00216                                 n++;
00217                         }
00218 
00219                         // store.
00220                         _Grid[y*_Size + x].NumNodes= n;
00221                         totalDupElt+= n;
00222                 }
00223         }
00224 
00225         // Resize array copy.
00226         _Elements.resize(totalDupElt);
00227 
00228 
00229         // Then reparse all array, filling _Elements and setup quadNodes ptr.
00230         uint    curDupElt= 0;
00231         for(y=0; y<_Size; y++)
00232         {
00233                 for(x=0; x<_Size; x++)
00234                 {
00235                         // Select the center of the case
00236                         CVector pos;
00237                         pos.x= (x+0.5f)*_EltSize;
00238                         pos.y= (y+0.5f)*_EltSize;
00239                         pos.z= 0.f;
00240                         // mul by invBasis
00241                         pos= invBasis * pos;
00242                         quadGrid.select(pos, pos);
00243 
00244                         // Setup quadNode ptr.
00245                         if (curDupElt < _Elements.size())
00246                                 _Grid[y*_Size + x].Nodes= &_Elements[curDupElt];
00247 
00248                         // For all elements.
00249                         CQuadGrid<T>::CIterator it;
00250                         for(it= quadGrid.begin(); it!=quadGrid.end(); it++)
00251                         {
00252                                 // Copy elt in array.
00253                                 _Elements[curDupElt]= *it;
00254 
00255                                 // Next elt in array.
00256                                 curDupElt++;
00257                         }
00258                 }
00259         }
00260 
00261 
00262         // clean up.
00263         quadGrid.clearSelection();
00264 }
00265 
00266 
00267 // ***************************************************************************
00268 template<class T>       
00269 const T                 *CStaticQuadGrid<T>::select(const NLMISC::CVector &pointIn, uint &numElts)
00270 {
00271         CVector         point= _ChangeBasis * pointIn;
00272 
00273         // Select the case.
00274         sint    x, y;
00275         selectPoint(point, x, y);
00276 
00277         // get ref on the selection
00278         CQuadNode       &quadNode= _Grid[y*_Size + x];
00279         numElts= quadNode.NumNodes;
00280 
00281         return quadNode.Nodes;
00282 }
00283 
00284 
00285 } // NL3D
00286 
00287 
00288 #endif // NL_STATIC_QUAD_GRID_H
00289 
00290 /* End of static_quad_grid.h */