# Home    # nevrax.com   
Nevrax
Nevrax.org
#News
#Mailing-list
#Documentation
#CVS
#Bugs
#License
Docs
 
Documentation  
Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages   Search  

bsp_tree.h

Go to the documentation of this file.
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