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_KDTREE_H__
00020 #define __CS_KDTREE_H__
00021
00022 #include "csextern.h"
00023
00024 #include "csgeom/box.h"
00025
00026 #include "csutil/blockallocator.h"
00027 #include "csutil/ref.h"
00028 #include "csutil/scfstr.h"
00029 #include "csutil/scf_implementation.h"
00030
00031 #include "iutil/dbghelp.h"
00032
00039 struct iGraphics3D;
00040 struct iString;
00041 class csKDTree;
00042 class csKDTreeChild;
00043
00050 struct iKDTreeObjectDescriptor : public virtual iBase
00051 {
00052 SCF_INTERFACE (iKDTreeObjectDescriptor, 0, 0, 1);
00053
00054 virtual csPtr<iString> DescribeObject (csKDTreeChild* child) = 0;
00055 };
00056
00062 struct iKDTreeUserData : public virtual iBase
00063 {
00064 SCF_INTERFACE (iKDTreeUserData, 0, 0, 1);
00065 };
00066
00089 typedef bool (csKDTreeVisitFunc)(csKDTree* treenode, void* userdata,
00090 uint32 timestamp, uint32& frustum_mask);
00091
00095 class CS_CRYSTALSPACE_EXPORT csKDTreeChild
00096 {
00097 private:
00098 friend class csKDTree;
00099
00100 csBox3 bbox;
00101 void* object;
00102 csKDTree** leafs;
00103 int num_leafs;
00104 int max_leafs;
00105
00106 public:
00107 uint32 timestamp;
00108
00109 public:
00110 csKDTreeChild ();
00111 ~csKDTreeChild ();
00112
00114 void AddLeaf (csKDTree* leaf);
00116 void RemoveLeaf (int idx);
00118 void RemoveLeaf (csKDTree* leaf);
00125 void ReplaceLeaf (csKDTree* old_leaf, csKDTree* new_leaf);
00126
00130 int FindLeaf (csKDTree* leaf);
00131
00135 inline const csBox3& GetBBox () const { return bbox; }
00136
00140 inline void* GetObject () const { return object; }
00141 };
00142
00143 enum
00144 {
00145 CS_KDTREE_AXISINVALID = -1,
00146 CS_KDTREE_AXISX = 0,
00147 CS_KDTREE_AXISY = 1,
00148 CS_KDTREE_AXISZ = 2
00149 };
00150
00167 class CS_CRYSTALSPACE_EXPORT csKDTree :
00168 public scfImplementation1<csKDTree, iDebugHelper>
00169 {
00170 public:
00171
00172 csRef<iKDTreeObjectDescriptor> descriptor;
00173 void DumpObject (csKDTreeChild* object, const char* msg);
00174 void DumpNode ();
00175 void DumpNode (const char* msg);
00176 static void DebugExit ();
00177
00178 private:
00179 csKDTree* child1;
00180 csKDTree* child2;
00181 csKDTree* parent;
00182
00183 csRef<iKDTreeUserData> userobject;
00184
00185 csBox3 node_bbox;
00186
00187 int split_axis;
00188 float split_location;
00189
00190
00191
00192
00193 csKDTreeChild** objects;
00194 int num_objects;
00195 int max_objects;
00196
00197
00198 int estimate_total_objects;
00199
00200
00201 int min_split_objects;
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211 #define DISALLOW_DISTRIBUTE_TIME 20
00212 int disallow_distribute;
00213
00214
00215
00216 static uint32 global_timestamp;
00217
00219 void AddObject (csKDTreeChild* obj);
00221 void RemoveObject (int idx);
00223 int FindObject (csKDTreeChild* obj);
00224
00228 void AddObjectInt (csKDTreeChild* obj);
00229
00240 float FindBestSplitLocation (int axis, float& split_loc);
00241
00247 void DistributeLeafObjects ();
00248
00255 void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func,
00256 void* userdata, uint32 cur_timestamp, uint32 frustum_mask);
00257
00264 void TraverseRandom (csKDTreeVisitFunc* func,
00265 void* userdata, uint32 cur_timestamp, uint32 frustum_mask);
00266
00270 void ResetTimestamps ();
00271
00275 void FlattenTo (csKDTree* node);
00276
00277 public:
00279 csKDTree ();
00281 virtual ~csKDTree ();
00283 void SetParent (csKDTree* p) { parent = p; }
00284
00286 void SetObjectDescriptor (iKDTreeObjectDescriptor* descriptor)
00287 {
00288 csKDTree::descriptor = descriptor;
00289 }
00290
00295 void SetMinimumSplitAmount (int m) { min_split_objects = m; }
00296
00298 void Clear ();
00299
00301 inline iKDTreeUserData* GetUserObject () const { return userobject; }
00302
00308 void SetUserObject (iKDTreeUserData* userobj);
00309
00317 csKDTreeChild* AddObject (const csBox3& bbox, void* object);
00318
00323 void UnlinkObject (csKDTreeChild* object);
00324
00329 void RemoveObject (csKDTreeChild* object);
00330
00334 void MoveObject (csKDTreeChild* object, const csBox3& new_bbox);
00335
00342 void Distribute ();
00343
00347 void FullDistribute ();
00348
00354 void Flatten ();
00355
00361 void TraverseRandom (csKDTreeVisitFunc* func,
00362 void* userdata, uint32 frustum_mask);
00363
00370 void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func,
00371 void* userdata, uint32 frustum_mask);
00372
00380 uint32 NewTraversal ();
00381
00385 inline csKDTree* GetChild1 () const { return child1; }
00386
00390 inline csKDTree* GetChild2 () const { return child2; }
00391
00395 inline int GetObjectCount () const { return num_objects; }
00396
00403 inline int GetEstimatedObjectCount () { return estimate_total_objects; }
00404
00408 inline csKDTreeChild** GetObjects () const { return objects; }
00409
00414 inline const csBox3& GetNodeBBox () const { return node_bbox; }
00415
00416
00417 bool Debug_CheckTree (csString& str);
00418 void Debug_Dump (csString& str, int indent);
00419 void Debug_Statistics (int& tot_objects,
00420 int& tot_nodes, int& tot_leaves, int depth, int& max_depth,
00421 float& balance_quality);
00422 csPtr<iString> Debug_Statistics ();
00423 csTicks Debug_Benchmark (int num_iterations);
00424
00425 virtual int GetSupportedTests () const
00426 {
00427 return CS_DBGHELP_STATETEST |
00428 CS_DBGHELP_TXTDUMP | CS_DBGHELP_BENCHMARK;
00429 }
00430
00431 virtual csPtr<iString> StateTest ()
00432 {
00433 scfString* rc = new scfString ();
00434 if (!Debug_CheckTree (rc->GetCsString ()))
00435 return csPtr<iString> (rc);
00436 delete rc;
00437 return 0;
00438 }
00439
00440 virtual csTicks Benchmark (int num_iterations)
00441 {
00442 return Debug_Benchmark (num_iterations);
00443 }
00444
00445 virtual csPtr<iString> Dump ()
00446 {
00447 scfString* rc = new scfString ();
00448 Debug_Dump (rc->GetCsString (), 0);
00449 return csPtr<iString> (rc);
00450 }
00451
00452 virtual void Dump (iGraphics3D* ) { }
00453 virtual bool DebugCommand (const char*) { return false; }
00454 };
00455
00458 #endif // __CS_KDTREE_H__
00459