00001
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
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:
00104
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
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
00133
00134
00135
00136
00137
00138
00139
00140
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
00167 _Elements.clear();
00168 _Grid.clear();
00169
00170
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
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
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
00203 CVector pos;
00204 pos.x= (x+0.5f)*_EltSize;
00205 pos.y= (y+0.5f)*_EltSize;
00206 pos.z= 0.f;
00207
00208 pos= invBasis * pos;
00209 quadGrid.select(pos, pos);
00210
00211
00212 uint n= 0;
00213 CQuadGrid<T>::CIterator it;
00214 for(it= quadGrid.begin(); it!=quadGrid.end(); it++)
00215 {
00216 n++;
00217 }
00218
00219
00220 _Grid[y*_Size + x].NumNodes= n;
00221 totalDupElt+= n;
00222 }
00223 }
00224
00225
00226 _Elements.resize(totalDupElt);
00227
00228
00229
00230 uint curDupElt= 0;
00231 for(y=0; y<_Size; y++)
00232 {
00233 for(x=0; x<_Size; x++)
00234 {
00235
00236 CVector pos;
00237 pos.x= (x+0.5f)*_EltSize;
00238 pos.y= (y+0.5f)*_EltSize;
00239 pos.z= 0.f;
00240
00241 pos= invBasis * pos;
00242 quadGrid.select(pos, pos);
00243
00244
00245 if (curDupElt < _Elements.size())
00246 _Grid[y*_Size + x].Nodes= &_Elements[curDupElt];
00247
00248
00249 CQuadGrid<T>::CIterator it;
00250 for(it= quadGrid.begin(); it!=quadGrid.end(); it++)
00251 {
00252
00253 _Elements[curDupElt]= *it;
00254
00255
00256 curDupElt++;
00257 }
00258 }
00259 }
00260
00261
00262
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
00274 sint x, y;
00275 selectPoint(point, x, y);
00276
00277
00278 CQuadNode &quadNode= _Grid[y*_Size + x];
00279 numElts= quadNode.NumNodes;
00280
00281 return quadNode.Nodes;
00282 }
00283
00284
00285 }
00286
00287
00288 #endif // NL_STATIC_QUAD_GRID_H
00289
00290