bsp.h Source File

00001 /*
00002     Copyright (C) 1998 by Jorrit Tyberghein
00003 
00004     This library is free software; you can redistribute it and/or
00005     modify it under the terms of the GNU Library General Public
00006     License as published by the Free Software Foundation; either
00007     version 2 of the License, or (at your option) any later version.
00008 
00009     This library is distributed in the hope that it will be useful,
00010     but WITHOUT ANY WARRANTY; without even the implied warranty of
00011     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012     Library General Public License for more details.
00013 
00014     You should have received a copy of the GNU Library General Public
00015     License along with this library; if not, write to the Free
00016     Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00017 */
00018 
00019 #ifndef __CS_BSP_H__
00020 #define __CS_BSP_H__
00021 
00022 #include "csgeom/math3d.h"
00023 #include "csengine/polytree.h"
00024 #include "csengine/polyint.h"
00025 #include "csengine/arrays.h"
00026 
00027 class csBspTree;
00028 class csPolygonArrayNoFree;
00029 struct iFile;
00030 
00031 // The BSP tree can be build using the following criteria:
00032 #define BSP_MINIMIZE_SPLITS 1           // Minimize the number of polygon splits
00033 #define BSP_MOST_ON_SPLITTER 2          // Splitter with most coplanar polygons
00034 #define BSP_RANDOM 3                    // Choose a random splitter
00035 #define BSP_ALMOST_MINIMIZE_SPLITS 4    // Select a number of polygons and choose minimal split
00036 #define BSP_BALANCED 5                  // Try to create a balanced tree
00037 #define BSP_ALMOST_BALANCED 6           // Try to create an approximation of a balanced tree
00038 #define BSP_BALANCE_AND_SPLITS 7        // Combine balanced tree and few splits.
00039 #define BSP_ALMOST_BALANCE_AND_SPLITS 8 // Combine balanced tree and few splits.
00040 
00044 class csBspNode : public csPolygonTreeNode
00045 {
00046   friend class csBspTree;
00047 private:
00054   csPolygonIntArray polygons;
00055 
00060   bool polygons_on_splitter;
00061 
00063   csPlane3 splitter;
00064 
00066   csBspNode* front;
00068   csBspNode* back;
00069 
00070 private:
00072   csBspNode ();
00073 
00078   virtual ~csBspNode ();
00079 
00083   void AddPolygon (csPolygonInt* poly);
00084 
00091   int CountVertices ();
00092 
00098   void FetchVertices (int* array, int& cur_idx);
00099 
00100 public:
00102   bool IsEmpty ()
00103   {
00104     return polygons.GetPolygonCount () == 0 &&
00105         (!front || front->IsEmpty ()) &&
00106         (!back || back->IsEmpty ());
00107   }
00108 
00110   int Type () { return NODE_BSPTREE; }
00111 
00117   int CountPolygons ();
00118 };
00119 
00123 class csBspTree : public csPolygonTree
00124 {
00125 private:
00127   int mode;
00128 
00129 private:
00133   void Build (csBspNode* node, csPolygonInt** polygons, int num);
00134 
00138   int SelectSplitter (csPolygonInt** polygons, int num);
00139 
00141   void* Back2Front (csBspNode* node, const csVector3& pos,
00142         csTreeVisitFunc* func, void* data, csTreeCullFunc* cullfunc,
00143         void* culldata);
00145   void* Front2Back (csBspNode* node, const csVector3& pos,
00146         csTreeVisitFunc* func, void* data, csTreeCullFunc* cullfunc,
00147         void* culldata);
00148 
00150   void Statistics (csBspNode* node, int depth, int* num_nodes,
00151         int* num_leaves, int* max_depth,
00152         int* tot_polygons, int* max_poly_in_node, int* min_poly_in_node);
00153 
00155   void* HandleObjects (csBspNode* node, const csVector3& pos,
00156         csTreeVisitFunc* func, void* data);
00157 
00162   void ProcessTodo (csBspNode* node);
00163 
00165   void Cache (iFile* cf, csBspNode* node,
00166         csPolygonInt** polygons, int num);
00167 
00169   bool ReadFromCache (iFile* cf, csBspNode* node,
00170         csPolygonInt** polygons, int num);
00171 
00172 public:
00176   csBspTree (csThing* thing, int mode = BSP_MINIMIZE_SPLITS);
00177 
00182   virtual ~csBspTree ();
00183 
00187   void Build (csPolygonInt** polygons, int num);
00188 
00192   void Build (csPolygonArray& polygons)
00193   {
00194     Build (polygons.GetArray (), polygons.Length ());
00195   }
00196 
00198   void* Back2Front (const csVector3& pos, csTreeVisitFunc* func, void* data,
00199         csTreeCullFunc* cullfunc = NULL, void* culldata = NULL);
00201   void* Front2Back (const csVector3& pos, csTreeVisitFunc* func, void* data,
00202         csTreeCullFunc* cullfunc = NULL, void* culldata = NULL);
00203 
00205   void Statistics ();
00206 
00208   void Statistics (int* num_nodes, int* num_leaves, int* max_depth,
00209         int* tot_polygons, int* max_poly_in_node, int* min_poly_in_node);
00210 
00216   int* GetVertices (int& count);
00217 
00221   bool IsEmpty () { return root ? root->IsEmpty () : false; }
00222 
00224   void Cache (iFile* cf, csPolygonInt** polygons, int num);
00225 
00227   bool ReadFromCache (iFile* cf, csPolygonInt** polygons, int num);
00228 
00234   int CountPolygons ()
00235   {
00236     if (!root) return 0;
00237     return ((csBspNode*)root)->CountPolygons ();
00238   }
00239 };
00240 
00241 #endif // __CS_BSP_H__