00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
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
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 (csBspNode* node, iFile* cf);
00166
00168 bool ReadFromCache (iFile* cf, csBspNode* node,
00169 csPolygonInt** polygons, int num);
00170
00171 public:
00175 csBspTree (csThing* thing, int mode = BSP_MINIMIZE_SPLITS);
00176
00181 virtual ~csBspTree ();
00182
00186 void Build (csPolygonInt** polygons, int num);
00187
00191 void Build (csPolygonArray& polygons)
00192 {
00193 Build (polygons.GetArray (), polygons.Length ());
00194 }
00195
00197 void* Back2Front (const csVector3& pos, csTreeVisitFunc* func, void* data,
00198 csTreeCullFunc* cullfunc = NULL, void* culldata = NULL);
00200 void* Front2Back (const csVector3& pos, csTreeVisitFunc* func, void* data,
00201 csTreeCullFunc* cullfunc = NULL, void* culldata = NULL);
00202
00204 void Statistics ();
00205
00207 void Statistics (int* num_nodes, int* num_leaves, int* max_depth,
00208 int* tot_polygons, int* max_poly_in_node, int* min_poly_in_node);
00209
00215 int* GetVertices (int& count);
00216
00220 bool IsEmpty () { return root ? root->IsEmpty () : false; }
00221
00223 void Cache (iFile* cf);
00224
00226 bool ReadFromCache (iFile* cf, csPolygonInt** polygons, int num);
00227
00233 int CountPolygons ()
00234 {
00235 if (!root) return 0;
00236 return ((csBspNode*)root)->CountPolygons ();
00237 }
00238 };
00239
00240 #endif // __CS_BSP_H__