nevrax.org : docs

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 */
+