nevrax.org : docs

00001 
+00007 /* Copyright, 2001 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_CUBE_GRID_H
+00027 #define NL_CUBE_GRID_H
+00028 
+00029 #include "nel/misc/types_nl.h"
+00030 #include "nel/misc/triangle.h"
+00031 #include "nel/misc/plane.h"
+00032 #include "3d/quad_grid.h"
+00033 #include "3d/static_quad_grid.h"
+00034 
+00035 
+00036 namespace NL3D {
+00037 
+00038 
+00039 // ***************************************************************************
+00051 template <class TCell>
+00052 class CCubeGrid
+00053 {
+00054 public:
+00055 
+00056         CCubeGrid ();
+00057         ~CCubeGrid ();
+00058 
+00062         void            create (const CVector &center, int nSize);
+00063         void            insert (const NLMISC::CTriangle &tri, const TCell &cell);
+00065         void            compile();
+00066 
+00067         // Selection. CubeGrid must be compilated. NB: it clear old selection.
+00068         void            select (const NLMISC::CVector &v);
+00069         TCell           getSel ();
+00070         void            nextSel ();
+00071         bool            isEndSel ();
+00072 
+00073 // ************************
+00074 private:
+00075 
+00076         NLMISC::CVector         _Center;
+00077 
+00078         enum gridPos { kUp = 0, kDown, kLeft, kRight, kFront, kBack };
+00079         // This is temp used at element insertion. freed at compile() time
+00080         NL3D::CQuadGrid<TCell> _Grids[6];
+00081         // For fast selection, and minimum memory overhead.
+00082         NL3D::CStaticQuadGrid<TCell> _StaticGrids[6];
+00083 
+00084 
+00085         bool                                    _Compiled;
+00086 
+00087         // Selection.
+00088         const TCell                             *_Selection;
+00089         uint                                    _CurSel;
+00090         uint                                    _NumSels;
+00091 
+00092 private:
+00093 
+00094         void project    (const NLMISC::CTriangle &tri, NLMISC::CPlane pyr[4], NLMISC::CPlane &gridPlane, 
+00095                                         sint32 nGridNb, const TCell &cell);
+00096 
+00097 };
+00098 
+00099 
+00100 // ***************************************************************************
+00101 // ***************************************************************************
+00102 // Implementation
+00103 // ***************************************************************************
+00104 // ***************************************************************************
+00105 
+00106 
+00107 // ***************************************************************************
+00108 template<class TCell>   
+00109 CCubeGrid<TCell>::CCubeGrid ()
+00110 {
+00111         NLMISC::CMatrix tmp;
+00112         NLMISC::CVector I, J, K;
+00113 
+00114         // grids[kUp].changeBase(  );
+00115         I = NLMISC::CVector(  1,  0,  0 );
+00116         J = NLMISC::CVector(  0, -1,  0 );
+00117         K = NLMISC::CVector(  0,  0, -1 );
+00118         tmp.identity(); tmp.setRot( I, J, K, true );
+00119         _Grids[kDown].changeBase( tmp );
+00120 
+00121         I = NLMISC::CVector(  0,  0,  1 );
+00122         J = NLMISC::CVector(  0,  1,  0 );
+00123         K = NLMISC::CVector( -1,  0,  0 );
+00124         tmp.identity(); tmp.setRot( I, J, K, true);
+00125         _Grids[kLeft].changeBase( tmp );
+00126 
+00127         I = NLMISC::CVector(  0,  0, -1 );
+00128         J = NLMISC::CVector(  0,  1,  0 );
+00129         K = NLMISC::CVector(  1,  0,  0 );
+00130         tmp.identity(); tmp.setRot( I, J, K, true);
+00131         _Grids[kRight].changeBase( tmp );
+00132 
+00133         I = NLMISC::CVector(  1,  0,  0 );
+00134         J = NLMISC::CVector(  0,  0,  1 );
+00135         K = NLMISC::CVector(  0, -1,  0 );
+00136         tmp.identity(); tmp.setRot( I, J, K, true);
+00137         _Grids[kFront].changeBase( tmp );
+00138 
+00139         I = NLMISC::CVector(  1,  0,  0 );
+00140         J = NLMISC::CVector(  0,  0, -1 );
+00141         K = NLMISC::CVector(  0,  1,  0 );
+00142         tmp.identity(); tmp.setRot( I, J, K, true);
+00143         _Grids[kBack].changeBase( tmp );
+00144 
+00145 
+00146         _Compiled= false;
+00147 }
+00148 
+00149 // ***************************************************************************
+00150 template<class TCell>   
+00151 CCubeGrid<TCell>::~CCubeGrid ()
+00152 {
+00153 }
+00154 
+00155 // ***************************************************************************
+00156 template<class TCell>   
+00157 void CCubeGrid<TCell>::create (const CVector &center, int nSize)
+00158 {
+00159         nlassert(!_Compiled);
+00160         _Center= center;
+00161 
+00162         _Grids[kUp].create              ( nSize, 1.0f / ((float)nSize) );
+00163         _Grids[kDown].create    ( nSize, 1.0f / ((float)nSize) );
+00164         _Grids[kLeft].create    ( nSize, 1.0f / ((float)nSize) );
+00165         _Grids[kRight].create   ( nSize, 1.0f / ((float)nSize) );
+00166         _Grids[kFront].create   ( nSize, 1.0f / ((float)nSize) );
+00167         _Grids[kBack].create    ( nSize, 1.0f / ((float)nSize) );
+00168 }
+00169 
+00170 // ***************************************************************************
+00171 template<class TCell>   
+00172 void CCubeGrid<TCell>::insert (const NLMISC::CTriangle &triIn, const TCell &cell)
+00173 {
+00174         nlassert(!_Compiled);
+00175         // Center triangle on _Center.
+00176         NLMISC::CTriangle tri= triIn;
+00177         tri.V0-= _Center;
+00178         tri.V1-= _Center;
+00179         tri.V2-= _Center;
+00180 
+00181         NLMISC::CPlane p[4], gp;
+00182         // Construct clip pyramid for grid : UP
+00183         p[0].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,-1,+1 ), NLMISC::CVector( +1,-1,+1 ) );
+00184         p[1].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,-1,+1 ), NLMISC::CVector( +1,+1,+1 ) );
+00185         p[2].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,+1,+1 ), NLMISC::CVector( -1,+1,+1 ) );
+00186         p[3].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,+1,+1 ), NLMISC::CVector( -1,-1,+1 ) );
+00187         gp.make( NLMISC::CVector(0,0,1), NLMISC::CVector(0,0,0.5) );
+00188         project( tri, p, gp, kUp, cell );
+00189         // Construct clip pyramid for grid : DOWN
+00190         p[0].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,-1,-1 ), NLMISC::CVector( -1,-1,-1 ) );
+00191         p[1].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,-1,-1 ), NLMISC::CVector( -1,+1,-1 ) );
+00192         p[2].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,+1,-1 ), NLMISC::CVector( +1,+1,-1 ) );
+00193         p[3].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,+1,-1 ), NLMISC::CVector( +1,-1,-1 ) );
+00194         gp.make( NLMISC::CVector(0,0,-1), NLMISC::CVector(0,0,-0.5) );
+00195         project( tri, p, gp, kDown, cell );
+00196         // Construct clip pyramid for grid : LEFT
+00197         p[0].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,-1,-1 ), NLMISC::CVector( -1,-1,+1 ) );
+00198         p[1].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,-1,+1 ), NLMISC::CVector( -1,+1,+1 ) );
+00199         p[2].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,+1,+1 ), NLMISC::CVector( -1,+1,-1 ) );
+00200         p[3].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,+1,-1 ), NLMISC::CVector( -1,-1,-1 ) );
+00201         gp.make( NLMISC::CVector(-1,0,0), NLMISC::CVector(-0.5,0,0) );
+00202         project( tri, p, gp, kLeft, cell );
+00203         // Construct clip pyramid for grid : RIGHT
+00204         p[0].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,-1,+1 ), NLMISC::CVector( +1,-1,-1 ) );
+00205         p[1].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,-1,-1 ), NLMISC::CVector( +1,+1,-1 ) );
+00206         p[2].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,+1,-1 ), NLMISC::CVector( +1,+1,+1 ) );
+00207         p[3].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,+1,+1 ), NLMISC::CVector( +1,-1,+1 ) );
+00208         gp.make( NLMISC::CVector(1,0,0), NLMISC::CVector(0.5,0,0) );
+00209         project( tri, p, gp, kRight, cell );
+00210         // Construct clip pyramid for grid : FRONT
+00211         p[0].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,-1,-1 ), NLMISC::CVector( +1,-1,-1 ) );
+00212         p[1].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,-1,-1 ), NLMISC::CVector( +1,-1,+1 ) );
+00213         p[2].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,-1,+1 ), NLMISC::CVector( -1,-1,+1 ) );
+00214         p[3].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,-1,+1 ), NLMISC::CVector( -1,-1,-1 ) );
+00215         gp.make( NLMISC::CVector(0,-1,0), NLMISC::CVector(0,-0.5,0) );
+00216         project( tri, p, gp, kFront, cell );
+00217         // Construct clip pyramid for grid : BACK
+00218         p[0].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,+1,+1 ), NLMISC::CVector( +1,+1,-1 ) );
+00219         p[1].make( NLMISC::CVector(0,0,0), NLMISC::CVector( +1,+1,-1 ), NLMISC::CVector( -1,+1,-1 ) );
+00220         p[2].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,+1,-1 ), NLMISC::CVector( -1,+1,+1 ) );
+00221         p[3].make( NLMISC::CVector(0,0,0), NLMISC::CVector( -1,+1,+1 ), NLMISC::CVector( +1,+1,+1 ) );
+00222         gp.make( NLMISC::CVector(0,1,0), NLMISC::CVector(0,0.5,0) );
+00223         project( tri, p, gp, kBack, cell );
+00224 }
+00225 
+00226 
+00227 // ***************************************************************************
+00228 template<class TCell>   
+00229 void CCubeGrid<TCell>::compile()
+00230 {
+00231         nlassert(!_Compiled);
+00232         // For all Grids.
+00233         uint    i;
+00234         for(i=0; i<6; i++)
+00235         {
+00236                 // build the _StaticGrid
+00237                 _StaticGrids[i].build(_Grids[i]);
+00238                 // And reset the grid. contReset is necessary to clean the CBlockMemory.
+00239                 contReset(_Grids[i]);
+00240         }
+00241 
+00242         // done
+00243         _Compiled= true;
+00244 
+00245         // Clear the Selection
+00246         _Selection= NULL;
+00247         _CurSel= 0;
+00248         _NumSels= 0;
+00249 }
+00250 
+00251 // ***************************************************************************
+00252 template<class TCell>   
+00253 void CCubeGrid<TCell>::select (const NLMISC::CVector &vIn)
+00254 {
+00255         nlassert(_Compiled);
+00256         // Center triangle on _Center.
+00257         NLMISC::CVector v= vIn-_Center;
+00258 
+00259 
+00260         sint    nSelGrid= -1;
+00261         NLMISC::CPlane gp;
+00262         // Get the plane
+00263         if( ( -v.z <= v.x ) && ( v.x <= v.z ) &&
+00264                 ( -v.z <= v.y ) && ( v.y <= v.z ) &&
+00265                 ( 0.0f <= v.z ) )
+00266         {
+00267                 nSelGrid = kUp;
+00268                 gp.make( NLMISC::CVector(0,0,1), NLMISC::CVector(0,0,0.5) );
+00269         }
+00270         if( ( v.z <= v.x ) && ( v.x <= -v.z ) &&
+00271                 ( v.z <= v.y ) && ( v.y <= -v.z ) &&
+00272                 ( v.z <= 0.0f ) )
+00273         {
+00274                 nSelGrid = kDown;
+00275                 gp.make( NLMISC::CVector(0,0,-1), NLMISC::CVector(0,0,-0.5) );
+00276         }
+00277         if( ( v.x <= 0.0f ) &&
+00278                 ( v.x <= v.y ) && ( v.y <= -v.x ) &&
+00279                 ( v.x <= v.z ) && ( v.z <= -v.x ) )
+00280         {
+00281                 nSelGrid = kLeft;
+00282                 gp.make( NLMISC::CVector(-1,0,0), NLMISC::CVector(-0.5,0,0) );
+00283         }
+00284         if( ( 0.0f <= v.x ) &&
+00285                 ( -v.x <= v.y ) && ( v.y <= v.x ) &&
+00286                 ( -v.x <= v.z ) && ( v.z <= v.x ) )
+00287         {
+00288                 nSelGrid = kRight;
+00289                 gp.make( NLMISC::CVector(1,0,0), NLMISC::CVector(0.5,0,0) );
+00290         }
+00291         if( ( v.y <= v.x ) && ( v.x <= -v.y ) &&
+00292                 ( v.y <= 0.0f ) &&
+00293                 ( v.y <= v.z ) && ( v.z <= -v.y ) )
+00294         {
+00295                 nSelGrid = kFront;
+00296                 gp.make( NLMISC::CVector(0,-1,0), NLMISC::CVector(0,-0.5,0) );
+00297         }
+00298         if( ( -v.y <= v.x ) && ( v.x <= v.y ) &&
+00299                 ( 0.0f <= v.y ) &&
+00300                 ( -v.y <= v.z ) && ( v.z <= v.y ) )
+00301         {
+00302                 nSelGrid = kBack;
+00303                 gp.make( NLMISC::CVector(0,1,0), NLMISC::CVector(0,0.5,0) );
+00304         }
+00305         nlassert(nSelGrid!=-1);
+00306         NLMISC::CVector newV = gp.intersect( NLMISC::CVector(0,0,0), v );
+00307         _Selection= _StaticGrids[nSelGrid].select(newV, _NumSels);
+00308         _CurSel = 0;
+00309 }
+00310 
+00311 // ***************************************************************************
+00312 template<class TCell>   
+00313 TCell CCubeGrid<TCell>::getSel ()
+00314 {
+00315         nlassert(_Compiled);
+00316         return _Selection[_CurSel];
+00317 }
+00318 
+00319 // ***************************************************************************
+00320 template<class TCell>   
+00321 void CCubeGrid<TCell>::nextSel ()
+00322 {
+00323         nlassert(_Compiled);
+00324         ++_CurSel;
+00325 }
+00326 
+00327 // ***************************************************************************
+00328 template<class TCell>   
+00329 bool CCubeGrid<TCell>::isEndSel ()
+00330 {
+00331         nlassert(_Compiled);
+00332         return (_CurSel == _NumSels);
+00333 }
+00334 
+00335 // ***************************************************************************
+00336 template<class TCell>   
+00337 void CCubeGrid<TCell>::project (const NLMISC::CTriangle &tri, NLMISC::CPlane pyr[4], NLMISC::CPlane &gridPlane, sint32 nGridNb, const TCell &cell)
+00338 {
+00339         NLMISC::CVector vIn[7], vOut[7];
+00340         sint32 i, nOut;
+00341         vIn[0] = tri.V0; vIn[1] = tri.V1; vIn[2] = tri.V2;
+00342         nOut = pyr[0].clipPolygonFront( vIn, vOut, 3 );
+00343         if( nOut == 0 ) return;
+00344         for( i = 0; i < nOut; ++i ) vIn[i] = vOut[i];
+00345         nOut = pyr[1].clipPolygonFront( vIn, vOut, nOut );
+00346         if( nOut == 0 ) return;
+00347         for( i = 0; i < nOut; ++i ) vIn[i] = vOut[i];
+00348         nOut = pyr[2].clipPolygonFront( vIn, vOut, nOut );
+00349         if( nOut == 0 ) return;
+00350         for( i = 0; i < nOut; ++i ) vIn[i] = vOut[i];
+00351         nOut = pyr[3].clipPolygonFront( vIn, vOut, nOut );
+00352         if( nOut >= 3 )
+00353         {
+00354                 NLMISC::CVector vMin(1, 1, 1), vMax(-1, -1, -1);
+00355                 for( i = 0; i < nOut; ++i )
+00356                 {
+00357                         vOut[i] = gridPlane.intersect( NLMISC::CVector(0, 0, 0), vOut[i] );
+00358                         if( vMin.x > vOut[i].x ) vMin.x = vOut[i].x;
+00359                         if( vMin.y > vOut[i].y ) vMin.y = vOut[i].y;
+00360                         if( vMin.z > vOut[i].z ) vMin.z = vOut[i].z;
+00361                         if( vMax.x < vOut[i].x ) vMax.x = vOut[i].x;
+00362                         if( vMax.y < vOut[i].y ) vMax.y = vOut[i].y;
+00363                         if( vMax.z < vOut[i].z ) vMax.z = vOut[i].z;
+00364                 }
+00365                 // Create the bbox
+00366                 _Grids[nGridNb].insert( vMin, vMax, cell );
+00367         }
+00368 }
+00369 
+00370 
+00371 
+00372 } // NL3D
+00373 
+00374 
+00375 #endif // NL_CUBE_GRID_H
+00376 
+00377 /* End of cube_grid.h */
+