|
octree.h00001 /* 00002 Copyright (C) 1998,2000 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_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 iCacheManager; 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 uint16 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 uint16 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 (iCacheManager* cache_mgr); 00345 00350 bool ReadFromCache (iCacheManager* cache_mgr, 00351 csPolygonInt** polygons, int num); 00352 }; 00353 00354 #endif // __CS_OCTREE_H__ 00355 Generated for Crystal Space by doxygen 1.2.5 written by Dimitri van Heesch, ©1997-2000 |