Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CS_KDTREEX_H__
00020 #define __CS_KDTREEX_H__
00021
00022 #include "csextern.h"
00023
00024 #include "csgeom/box.h"
00025 #include "csgeom/sphere.h"
00026 #include "csgeom/kdtree.h"
00027
00028 #include "csutil/blockallocator.h"
00029 #include "csutil/ref.h"
00030 #include "csutil/scfstr.h"
00031 #include "csutil/scf_implementation.h"
00032
00033 #include "iutil/dbghelp.h"
00034
00041 struct iGraphics3D;
00042 struct iString;
00043
00044 namespace CS
00045 {
00046 namespace Geometry
00047 {
00048
00049 class KDTree;
00050 class KDTreeChild;
00051
00058 struct iObjectDescriptor : public virtual iBase
00059 {
00060 SCF_INTERFACE (CS::Geometry::iObjectDescriptor, 0, 0, 1);
00061
00062 virtual csPtr<iString> DescribeObject (KDTreeChild* child) = 0;
00063 };
00064
00065
00088 typedef bool (KDTreeVisitFunc)(KDTree* treenode, void* userdata,
00089 uint32 timestamp, uint32& frustum_mask);
00090
00094 class KDTreeChild
00095 {
00096 private:
00097 friend class KDTree;
00098
00099 csSphere bsphere;
00100 void* object;
00101 KDTree** leafs;
00102 int num_leafs;
00103 int max_leafs;
00104
00105 public:
00106 uint32 timestamp;
00107
00108 public:
00109 KDTreeChild ();
00110 ~KDTreeChild ();
00111
00113 void AddLeaf (KDTree* leaf);
00115 void RemoveLeaf (int idx);
00117 void RemoveLeaf (KDTree* leaf);
00124 void ReplaceLeaf (KDTree* old_leaf, KDTree* new_leaf);
00125
00129 int FindLeaf (KDTree* leaf);
00130
00134 inline const csSphere& GetBSphere () const { return bsphere; }
00135
00139 inline void* GetObject () const { return object; }
00140 };
00141
00142 enum
00143 {
00144 CS_KDTREE_AXISINVALID = -1,
00145 CS_KDTREE_AXISX = 0,
00146 CS_KDTREE_AXISY = 1,
00147 CS_KDTREE_AXISZ = 2
00148 };
00149
00166 class CS_CRYSTALSPACE_EXPORT KDTree :
00167 public scfImplementation1<KDTree, iDebugHelper>
00168 {
00169 public:
00170
00171 csRef<iObjectDescriptor> descriptor;
00172 void DumpObject (KDTreeChild* object, const char* msg);
00173 void DumpNode ();
00174 void DumpNode (const char* msg);
00175 static void DebugExit ();
00176
00177 private:
00178 KDTree* child1;
00179 KDTree* child2;
00180 KDTree* parent;
00181
00182 csRef<iKDTreeUserData> userobject;
00183
00184 csBox3 node_bbox;
00185
00186 int split_axis;
00187 float split_location;
00188
00189
00190
00191
00192 KDTreeChild** objects;
00193 int num_objects;
00194 int max_objects;
00195
00196
00197 int estimate_total_objects;
00198
00199
00200 int min_split_objects;
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210 #define DISALLOW_DISTRIBUTE_TIME 20
00211 int disallow_distribute;
00212
00213
00214
00215 static uint32 global_timestamp;
00216
00218 void AddObject (KDTreeChild* obj);
00220 void RemoveObject (int idx);
00222 int FindObject (KDTreeChild* obj);
00223
00227 void AddObjectInt (KDTreeChild* obj);
00228
00239 float FindBestSplitLocation (int axis, float& split_loc);
00240
00246 void DistributeLeafObjects ();
00247
00254 void Front2Back (const csVector3& pos, KDTreeVisitFunc* func,
00255 void* userdata, uint32 cur_timestamp, uint32 frustum_mask);
00256
00263 void TraverseRandom (KDTreeVisitFunc* func,
00264 void* userdata, uint32 cur_timestamp, uint32 frustum_mask);
00265
00269 void ResetTimestamps ();
00270
00274 void FlattenTo (KDTree* node);
00275
00276 public:
00278 KDTree ();
00280 virtual ~KDTree ();
00282 void SetParent (KDTree* p) { parent = p; }
00283
00285 void SetObjectDescriptor (iObjectDescriptor* descriptor)
00286 {
00287 KDTree::descriptor = descriptor;
00288 }
00289
00294 void SetMinimumSplitAmount (int m) { min_split_objects = m; }
00295
00297 void Clear ();
00298
00300 inline iKDTreeUserData* GetUserObject () const { return userobject; }
00301
00307 void SetUserObject (iKDTreeUserData* userobj);
00308
00316 KDTreeChild* AddObject (const csSphere& bsphere, void* object);
00317
00322 void UnlinkObject (KDTreeChild* object);
00323
00328 void RemoveObject (KDTreeChild* object);
00329
00333 void MoveObject (KDTreeChild* object, const csSphere& new_bsphere);
00334
00341 void Distribute ();
00342
00346 void FullDistribute ();
00347
00353 void Flatten ();
00354
00360 void TraverseRandom (KDTreeVisitFunc* func,
00361 void* userdata, uint32 frustum_mask);
00362
00369 void Front2Back (const csVector3& pos, KDTreeVisitFunc* func,
00370 void* userdata, uint32 frustum_mask);
00371
00379 uint32 NewTraversal ();
00380
00384 inline KDTree* GetChild1 () const { return child1; }
00385
00389 inline KDTree* GetChild2 () const { return child2; }
00390
00394 inline int GetObjectCount () const { return num_objects; }
00395
00402 inline int GetEstimatedObjectCount () { return estimate_total_objects; }
00403
00407 inline KDTreeChild** GetObjects () const { return objects; }
00408
00413 inline const csBox3& GetNodeBBox () const { return node_bbox; }
00414
00415
00416 bool Debug_CheckTree (csString& str);
00417 void Debug_Dump (csString& str, int indent);
00418 void Debug_Statistics (int& tot_objects,
00419 int& tot_nodes, int& tot_leaves, int depth, int& max_depth,
00420 float& balance_quality);
00421 csPtr<iString> Debug_Statistics ();
00422 csTicks Debug_Benchmark (int num_iterations);
00423
00424 virtual int GetSupportedTests () const
00425 {
00426 return CS_DBGHELP_STATETEST |
00427 CS_DBGHELP_TXTDUMP | CS_DBGHELP_BENCHMARK;
00428 }
00429
00430 virtual csPtr<iString> StateTest ()
00431 {
00432 scfString* rc = new scfString ();
00433 if (!Debug_CheckTree (rc->GetCsString ()))
00434 return csPtr<iString> (rc);
00435 delete rc;
00436 return 0;
00437 }
00438
00439 virtual csTicks Benchmark (int num_iterations)
00440 {
00441 return Debug_Benchmark (num_iterations);
00442 }
00443
00444 virtual csPtr<iString> Dump ()
00445 {
00446 scfString* rc = new scfString ();
00447 Debug_Dump (rc->GetCsString (), 0);
00448 return csPtr<iString> (rc);
00449 }
00450
00451 virtual void Dump (iGraphics3D* ) { }
00452 virtual bool DebugCommand (const char*) { return false; }
00453 };
00454
00455 }
00456 }
00457
00460 #endif // __CS_KDTREEX_H__
00461