nevrax.org : docs

00001 
+00007 /* Copyright, 2000 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 
+00027 #ifndef NL_BSP_TREE_H
+00028 #define NL_BSP_TREE_H
+00029 
+00030 #include "nel/misc/debug.h"
+00031 #include "nel/misc/vector.h"
+00032 #include "nel/misc/plane.h"
+00033 #include "nel/misc/matrix.h"
+00034 #include "nel/misc/triangle.h"
+00035 #include <list>
+00036 #include <vector>
+00037 
+00038 
+00039 namespace       NL3D
+00040 {
+00041 
+00042 
+00043 
+00051 template<class T>       class   CBSPTree
+00052 {
+00053 
+00054 public:
+00055 
+00057         CBSPTree();
+00058 
+00060         ~CBSPTree();
+00061 
+00062 public:
+00063 
+00064         void insert( NLMISC::CTriangle &tri, T &value );
+00065         sint32 select( CVector &v1, CVector &v2 );
+00066         T getSelection( sint32 i );
+00067         sint32 getNbNode();
+00068 
+00069 private:
+00070 
+00071         class CBSPNode;
+00072         std::vector<CBSPNode*> _Selection;
+00073 
+00074 private:
+00075         
+00076         class CBSPNode
+00077         {
+00078                 CBSPNode *pBack, *pFront;
+00079                 CPlane p;
+00080 
+00081         public:
+00082 
+00083                 T Value;
+00084 
+00085         public:
+00086 
+00087                 CBSPNode( NLMISC::CTriangle &tri, T &val ) : Value(val), pBack(NULL), pFront(NULL) 
+00088                 {
+00089                         p.make( tri.V0, tri.V1, tri.V2 );
+00090                         p.normalize();
+00091                 }
+00092 
+00093                 ~CBSPNode()
+00094                 {
+00095                         if( pBack != NULL )
+00096                                 delete pBack;
+00097                         if( pFront != NULL )
+00098                                 delete pFront;
+00099                 }
+00100 
+00101                 void insert( NLMISC::CTriangle &tri, T &val )
+00102                 {
+00103                         float   f[3];
+00104                         CBSPNode *pCurrent = this;
+00105 
+00106                         while( true )
+00107                         {
+00108                                 f[0] = pCurrent->p*tri.V0;
+00109                                 f[1] = pCurrent->p*tri.V1,
+00110                                 f[2] = pCurrent->p*tri.V2;
+00111                                 if( fabs( f[0] ) < 0.00001 ) f[0] = 0.0f;
+00112                                 if( fabs( f[1] ) < 0.00001 ) f[1] = 0.0f;
+00113                                 if( fabs( f[2] ) < 0.00001 ) f[2] = 0.0f;
+00114                                 if( ( f[0] >= 0.0f ) && ( f[1] >= 0.0f ) && ( f[2] >= 0.0f ) )
+00115                                 {       // All front
+00116                                         if( pCurrent->pFront == NULL )
+00117                                         {
+00118                                                 pCurrent->pFront = new CBSPNode( tri, val );
+00119                                                 return;
+00120                                         }
+00121                                         else
+00122                                         {
+00123                                                 pCurrent = pCurrent->pFront;
+00124                                         }
+00125                                 }
+00126                                 else
+00127                                 if( ( f[0] <= 0.0f ) && ( f[1] <= 0.0f ) && ( f[2] <= 0.0f ) )
+00128                                 {       // All back
+00129                                         if( pCurrent->pBack == NULL )
+00130                                         {
+00131                                                 pCurrent->pBack = new CBSPNode( tri, val );
+00132                                                 return;
+00133                                         }
+00134                                         else
+00135                                         {
+00136                                                 pCurrent = pCurrent->pBack;
+00137                                         }
+00138                                 }
+00139                                 else
+00140                                 {
+00141                                         if( pCurrent->pFront == NULL )
+00142                                         {
+00143                                                 pCurrent->pFront = new CBSPNode( tri, val );
+00144                                         }
+00145                                         else
+00146                                         {
+00147                                                 pCurrent->pFront->insert( tri, val );
+00148                                         }
+00149                                         if( pCurrent->pBack == NULL )
+00150                                         {
+00151                                                 pCurrent->pBack = new CBSPNode( tri, val );
+00152                                         }
+00153                                         else
+00154                                         {
+00155                                                 pCurrent->pBack->insert( tri, val );
+00156                                         }
+00157                                         return;
+00158                                 }
+00159                         }
+00160                 }
+00161 
+00162 
+00163                 sint32 getNbNode()
+00164                 {
+00165                         sint32 nBack = 0, nFront= 0;
+00166                         if( pBack != NULL )
+00167                                 nBack = pBack->getNbNode();
+00168                         if( pFront != NULL )
+00169                                 nFront = pFront->getNbNode();
+00170                         return 1+nBack+nFront;
+00171                 }
+00172 
+00173 
+00174                 void select( std::vector<CBSPNode*> &sel, CVector &v1, CVector &v2 )
+00175                 {
+00176                         float   f[2];
+00177                         CBSPNode *pCurrent = this;
+00178 
+00179                         while( true )
+00180                         {
+00181                                 f[0] = pCurrent->p*v1;
+00182                                 f[1] = pCurrent->p*v2;
+00183                                 if( fabs( f[0] ) < 0.00001 ) f[0] = 0.0;
+00184                                 if( fabs( f[1] ) < 0.00001 ) f[1] = 0.0;
+00185                                 if( ( f[0] >= 0.0 ) && ( f[1] >= 0.0 ) )
+00186                                 {       // All front
+00187                                         if( pCurrent->pFront == NULL )
+00188                                         {
+00189                                                 return;
+00190                                         }
+00191                                         else
+00192                                         {
+00193                                                 pCurrent = pCurrent->pFront;
+00194                                         }
+00195                                 }
+00196                                 else
+00197                                 if( ( f[0] <= 0.0 ) && ( f[1] <= 0.0 ) )
+00198                                 {       // All back
+00199                                         if( pCurrent->pBack == NULL )
+00200                                         {
+00201                                                 return;
+00202                                         }
+00203                                         else
+00204                                         {
+00205                                                 pCurrent = pCurrent->pBack;
+00206                                         }
+00207                                 }
+00208                                 else
+00209                                 {
+00210                                         if( sel.size() == sel.capacity() )
+00211                                                 sel.reserve( sel.size() + 64 );
+00212                                         sel.push_back( this );
+00213                                         if( pCurrent->pFront == NULL )
+00214                                         {
+00215                                         }
+00216                                         else
+00217                                         {
+00218                                                 //CVector newV1 = v1;
+00219                                                 //CVector newV2 = v2;
+00220                                                 //pCurrent->p.clipSegmentFront( newV1, newV2 );
+00221                                                 //pCurrent->pFront->select( sel, newV1, newV2 );
+00222                                                 pCurrent->pFront->select( sel, v1, v2 );
+00223                                         }
+00224                                         if( pCurrent->pBack == NULL )
+00225                                         {
+00226                                         }
+00227                                         else
+00228                                         {
+00229                                                 //CVector newV1 = v1;
+00230                                                 //CVector newV2 = v2;
+00231                                                 //pCurrent->p.clipSegmentBack( newV1, newV2 );
+00232                                                 //pCurrent->pBack->select( sel, newV1, newV2 );
+00233                                                 pCurrent->pBack->select( sel, v1, v2 );                                         
+00234                                         }
+00235                                         return;
+00236                                 }
+00237                         }
+00238                 }
+00239         };
+00240 
+00241 private:
+00242 
+00243         CBSPNode *_Root;
+00244 
+00245 };
+00246 
+00247 // ============================================================================================
+00248 // ============================================================================================
+00249 // Template CBSPTree implementation. Construction/Destruction.
+00250 // ============================================================================================
+00251 // ============================================================================================
+00252 
+00253 template<class T> CBSPTree<T>::CBSPTree() : _Root(NULL)
+00254 {
+00255         _Selection.reserve( 64 );
+00256 }
+00257 
+00258 template<class T> CBSPTree<T>::~CBSPTree()
+00259 {
+00260         if( _Root != NULL )
+00261                 delete _Root;
+00262 }
+00263 
+00264 // ============================================================================================
+00265 // ============================================================================================
+00266 // Template CBSPTree implementation.
+00267 // ============================================================================================
+00268 // ============================================================================================
+00269 
+00270 template<class T> void CBSPTree<T>::insert( NLMISC::CTriangle &tri, T &val )
+00271 {
+00272         if( _Root == NULL )
+00273                 _Root = new CBSPNode( tri, val );
+00274         else
+00275                 _Root->insert( tri, val );
+00276 }
+00277 
+00278 template<class T> sint32 CBSPTree<T>::select( CVector &v1, CVector &v2 )
+00279 {
+00280         _Selection.clear();
+00281         if( _Root != NULL )
+00282         {
+00283                 _Root->select( _Selection, v1, v2 );
+00284                 return _Selection.size();
+00285         }
+00286         else 
+00287                 return 0;
+00288 }
+00289 
+00290 template<class T> T CBSPTree<T>::getSelection( sint32 i )
+00291 {
+00292         return _Selection[i]->Value;
+00293 }
+00294 
+00295 template<class T> sint32 CBSPTree<T>::getNbNode()
+00296 {
+00297         return _Root->getNbNode();
+00298 }
+00299 
+00300 }
+00301 
+00302 #endif // NL_BSP_TREE_H
+
bsp_tree.h
