Google

Main Page   Class Hierarchy   Compound List   File List   Compound Members  

octree.h

00001 /*
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