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