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 "csgeom/box.h"
00023 #include "csgeom/vector2.h"
00024 #include "csgeom/math2d.h"
00025 #include "csutil/scfstr.h"
00026 #include "iutil/dbghelp.h"
00027
00028 struct iGraphics3D;
00029 class csKDTree;
00030
00053 typedef bool (csKDTreeVisitFunc)(csKDTree* treenode, void* userdata,
00054 uint32 timestamp, uint32& frustum_mask);
00055
00059 class csKDTreeChild
00060 {
00061 private:
00062 friend class csKDTree;
00063
00064 csBox3 bbox;
00065 void* object;
00066 csKDTree** leafs;
00067 int num_leafs;
00068 int max_leafs;
00069
00070 public:
00071 uint32 timestamp;
00072
00073 public:
00074 csKDTreeChild ();
00075 ~csKDTreeChild ();
00076
00078 void AddLeaf (csKDTree* leaf);
00080 void RemoveLeaf (int idx);
00082 void RemoveLeaf (csKDTree* leaf);
00089 void ReplaceLeaf (csKDTree* old_leaf, csKDTree* new_leaf);
00090
00094 int FindLeaf (csKDTree* leaf);
00095
00099 const csBox3& GetBBox () const { return bbox; }
00100
00104 void* GetObject () const { return object; }
00105 };
00106
00107 #define CS_KDTREE_AXISINVALID -1
00108 #define CS_KDTREE_AXISX 0
00109 #define CS_KDTREE_AXISY 1
00110 #define CS_KDTREE_AXISZ 2
00111
00128 class csKDTree : public iBase
00129 {
00130 private:
00131 csKDTree* child1;
00132 csKDTree* child2;
00133 csKDTree* parent;
00134
00135 iBase* userobject;
00136
00137 bool obj_bbox_valid;
00138 csBox3 obj_bbox;
00139 csBox3 node_bbox;
00140
00141 int split_axis;
00142 float split_location;
00143
00144
00145
00146
00147 csKDTreeChild** objects;
00148 int num_objects;
00149 int max_objects;
00150
00151
00152
00153
00154
00155
00156
00157
00158 bool disallow_distribute;
00159
00160
00161
00162 static uint32 global_timestamp;
00163
00165 void AddObject (csKDTreeChild* obj);
00167 void RemoveObject (int idx);
00169 int FindObject (csKDTreeChild* obj);
00170
00174 void AddObject (const csBox3& bbox, csKDTreeChild* obj);
00175
00186 int FindBestSplitLocation (int axis, float& split_loc);
00187
00193 void DistributeLeafObjects ();
00194
00200 void UpdateBBox (const csBox3& bbox);
00201
00208 bool Front2Back (const csVector3& pos, csKDTreeVisitFunc* func,
00209 void* userdata, uint32 cur_timestamp, uint32 frustum_mask);
00210
00214 void ResetTimestamps ();
00215
00219 void FlattenTo (csKDTree* node);
00220
00221 public:
00223 csKDTree (csKDTree* parent);
00225 virtual ~csKDTree ();
00226
00228 void Clear ();
00229
00230 SCF_DECLARE_IBASE;
00231
00233 iBase* GetUserObject () const { return userobject; }
00234
00240 void SetUserObject (iBase* userobj);
00241
00249 csKDTreeChild* AddObject (const csBox3& bbox, void* object);
00250
00255 void UnlinkObject (csKDTreeChild* object);
00256
00261 void RemoveObject (csKDTreeChild* object);
00262
00266 void MoveObject (csKDTreeChild* object, const csBox3& new_bbox);
00267
00274 void Distribute ();
00275
00279 void FullDistribute ();
00280
00286 void Flatten ();
00287
00294 void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func,
00295 void* userdata, uint32 frustum_mask);
00296
00300 int GetObjectCount () const { return num_objects; }
00301
00305 csKDTreeChild** GetObjects () const { return objects; }
00306
00310 const csBox3& GetObjectBBox ();
00311
00316 const csBox3& GetNodeBBox () const { return node_bbox; }
00317
00318
00319 bool Debug_CheckTree (csString& str);
00320 csPtr<iString> Debug_UnitTest ();
00321 void Debug_Dump (csString& str, int indent);
00322 void Debug_Statistics (int& tot_objects,
00323 int& tot_nodes, int& tot_leaves, int depth, int& max_depth,
00324 float& balance_quality);
00325 csPtr<iString> Debug_Statistics ();
00326 csTicks Debug_Benchmark (int num_iterations);
00327
00328 struct DebugHelper : public iDebugHelper
00329 {
00330 SCF_DECLARE_EMBEDDED_IBASE (csKDTree);
00331 virtual int GetSupportedTests () const
00332 {
00333 return CS_DBGHELP_UNITTEST | CS_DBGHELP_STATETEST |
00334 CS_DBGHELP_TXTDUMP | CS_DBGHELP_BENCHMARK;
00335 }
00336 virtual csPtr<iString> UnitTest ()
00337 {
00338 return scfParent->Debug_UnitTest ();
00339 }
00340 virtual csPtr<iString> StateTest ()
00341 {
00342 scfString* rc = new scfString ();
00343 if (!scfParent->Debug_CheckTree (rc->GetCsString ()))
00344 return csPtr<iString> (rc);
00345 delete rc;
00346 return 0;
00347 }
00348 virtual csTicks Benchmark (int num_iterations)
00349 {
00350 return scfParent->Debug_Benchmark (num_iterations);
00351 }
00352 virtual csPtr<iString> Dump ()
00353 {
00354 scfString* rc = new scfString ();
00355 scfParent->Debug_Dump (rc->GetCsString (), 0);
00356 return csPtr<iString> (rc);
00357 }
00358 virtual void Dump (iGraphics3D* )
00359 {
00360 }
00361 virtual bool DebugCommand (const char*)
00362 {
00363 return false;
00364 }
00365 } scfiDebugHelper;
00366 };
00367
00368 #endif // __CS_KDTREE_H__
00369