00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CS_OCTREE_H__
00020 #define __CS_OCTREE_H__
00021
00022 #include "csgeom/math3d.h"
00023 #include "csgeom/box.h"
00024 #include "csengine/polytree.h"
00025 #include "csengine/bsp.h"
00026
00027 class csPolygonInt;
00028 class csOctree;
00029 class csOctreeNode;
00030 class csBspTree;
00031 class csThing;
00032 struct iVFS;
00033 struct iFile;
00034
00035 #define OCTREE_FFF 0
00036 #define OCTREE_FFB 1
00037 #define OCTREE_FBF 2
00038 #define OCTREE_FBB 3
00039 #define OCTREE_BFF 4
00040 #define OCTREE_BFB 5
00041 #define OCTREE_BBF 6
00042 #define OCTREE_BBB 7
00043
00049 class csOctreeNode : public csPolygonTreeNode
00050 {
00051 friend class csOctree;
00052
00053 private:
00055 csPolygonTreeNode* children[8];
00057 csBox3 bbox;
00059 csVector3 center;
00060
00065 UShort solid_masks[6];
00066
00072 bool leaf;
00073
00080 csPolygonIntArray unsplit_polygons;
00081
00083 csBspTree* minibsp;
00084
00092 int* minibsp_verts;
00093
00095 int minibsp_numverts;
00096
00097 private:
00099 csOctreeNode ();
00100
00104 virtual ~csOctreeNode ();
00105
00107 void SetBox (const csVector3& bmin, const csVector3& bmax)
00108 {
00109 bbox.Set (bmin, bmax);
00110 center = (bmin + bmax) / 2;
00111 }
00112
00114 void SetMiniBsp (csBspTree* mbsp);
00115
00117 void BuildVertexTables ();
00118
00119 public:
00121 bool IsEmpty ();
00122
00124 bool IsLeaf () { return leaf; }
00125
00127 const csVector3& GetCenter () const { return center; }
00128
00130 const csVector3& GetMinCorner () const { return bbox.Min (); }
00131
00133 const csVector3& GetMaxCorner () const { return bbox.Max (); }
00134
00136 const csBox3& GetBox () { return bbox; }
00137
00139 csOctreeNode* GetChild (int i) { return (csOctreeNode*)children[i]; }
00140
00145 UShort GetSolidMask (int idx) { return solid_masks[idx]; }
00146
00154 csPolygonIntArray& GetUnsplitPolygons () { return unsplit_polygons; }
00155
00157 csBspTree* GetMiniBsp () const { return minibsp; }
00158
00160 int* GetMiniBspVerts () const { return minibsp_verts; }
00161
00163 int GetMiniBspVertexCount () const { return minibsp_numverts; }
00164
00166 int Type () { return NODE_OCTREE; }
00167
00169 int CountChildren ();
00170
00176 int CountPolygons ();
00177
00183 void* InitSolidPolygonIterator (int side);
00184
00189 bool NextSolidPolygon (void* vspit, csPoly3D& poly);
00190
00194 void CleanupSolidPolygonIterator (void* vspit);
00195 };
00196
00200 class csOctree : public csPolygonTree
00201 {
00202 private:
00204 csBox3 bbox;
00206 int bsp_num;
00208 int mode;
00209
00210 private:
00212 void Build (csOctreeNode* node, const csVector3& bmin, const csVector3& bmax,
00213 csPolygonInt** polygons, int num);
00214
00216 void* Back2Front (csOctreeNode* node, const csVector3& pos,
00217 csTreeVisitFunc* func, void* data, csTreeCullFunc* cullfunc,
00218 void* culldata);
00220 void* Front2Back (csOctreeNode* node, const csVector3& pos,
00221 csTreeVisitFunc* func, void* data, csTreeCullFunc* cullfunc,
00222 void* culldata);
00223
00228 void ProcessTodo (csOctreeNode* node);
00229
00233 void ChooseBestCenter (csOctreeNode* node, csPolygonInt** polygons, int num);
00234
00238 void Statistics (csOctreeNode* node, int depth,
00239 int* num_oct_nodes, int* max_oct_depth, int* num_bsp_trees,
00240 int* tot_bsp_nodes, int* min_bsp_nodes, int* max_bsp_nodes,
00241 int* tot_bsp_leaves, int* min_bsp_leaves, int* max_bsp_leaves,
00242 int* tot_max_depth, int* min_max_depth, int* max_max_depth,
00243 int* tot_tot_poly, int* min_tot_poly, int* max_tot_poly,
00244 int* num_pvs_leaves,
00245 int* tot_pvs_vis_nodes, int* min_pvs_vis_nodes, int* max_pvs_vis_nodes,
00246 int* tot_pvs_vis_poly, int* min_pvs_vis_poly, int* max_pvs_vis_poly);
00247
00251 void CalculateSolidMasks (csOctreeNode* node);
00252
00254 void Cache (csOctreeNode* node, iFile* cf);
00255
00257 bool ReadFromCache (iFile* cf, csOctreeNode* node,
00258 const csVector3& bmin, const csVector3& bmax,
00259 csPolygonInt** polygons, int num);
00260
00264 csOctreeNode* GetNodeFromPath (csOctreeNode* node,
00265 unsigned char* path, int path_len);
00266
00272 void GetNodePath (csOctreeNode* node, csOctreeNode* child,
00273 unsigned char* path, int& path_len);
00274
00275 public:
00281 csOctree (csThing* thing, const csVector3& min_bbox,
00282 const csVector3& max_bbox, int bsp_num, int mode = BSP_MINIMIZE_SPLITS);
00283
00288 virtual ~csOctree ();
00289
00293 csOctreeNode* GetRoot () { return (csOctreeNode*)root; }
00294
00298 void Build (csPolygonInt** polygons, int num);
00299
00303 void Build (const csPolygonArray& polygons);
00304
00306 void* Back2Front (const csVector3& pos, csTreeVisitFunc* func, void* data,
00307 csTreeCullFunc* cullfunc = NULL, void* culldata = NULL);
00309 void* Front2Back (const csVector3& pos, csTreeVisitFunc* func, void* data,
00310 csTreeCullFunc* cullfunc = NULL, void* culldata = NULL);
00311
00320 void GetConvexOutline (csOctreeNode* node, const csVector3& pos,
00321 csVector3* array, int& num_array, bool bVisible = false)
00322 {
00323 node->bbox.GetConvexOutline (pos, array, num_array, bVisible);
00324 }
00325
00329 csOctreeNode* GetLeaf (const csVector3& pos);
00330
00336 void BuildVertexTables () { if (root) ((csOctreeNode*)root)->BuildVertexTables (); }
00337
00339 void Statistics ();
00340
00344 void Cache (iVFS* vfs, const char* name);
00345
00350 bool ReadFromCache (iVFS* vfs, const char* name,
00351 csPolygonInt** polygons, int num);
00352
00356 void CachePVS (iVFS* vfs, const char* name);
00357
00362 bool ReadFromCachePVS (iVFS* vfs, const char* name);
00363 };
00364
00365 #endif // __CS_OCTREE_H__