csgeom/kdtree.h
Go to the documentation of this file.00001 /* 00002 Copyright (C) 2002 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_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; // Pointer back to the original object. 00102 csKDTree** leafs; // Leafs that contain this object. 00103 int num_leafs; 00104 int max_leafs; 00105 00106 public: 00107 uint32 timestamp; // Timestamp of last visit to this child. 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 // This is used for debugging. 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; // If child1 is not 0 then child2 will 00180 csKDTree* child2; // also be not 0. 00181 csKDTree* parent; // 0 if this is the root. 00182 00183 csRef<iKDTreeUserData> userobject; // An optional user object for this node. 00184 00185 csBox3 node_bbox; // Bbox of the node itself. 00186 00187 int split_axis; // One of CS_KDTREE_AXIS? 00188 float split_location; // Where is the split? 00189 00190 // Objects in this node. If this node also has children (child1 00191 // and child2) then the objects here have to be moved to these 00192 // children. The 'Distribute()' function will do that. 00193 csKDTreeChild** objects; 00194 int num_objects; 00195 int max_objects; 00196 00197 // Estimate of the total number of objects in this tree including children. 00198 int estimate_total_objects; 00199 00200 // Minimum amount of objects in this tree before we consider splitting. 00201 int min_split_objects; 00202 00203 // Disallow Distribute(). 00204 // If this flag > 0 it means that we cannot find a good split 00205 // location for the current list of objects. So in that case we don't 00206 // split at all and set this flag to DISALLOW_DISTRIBUTE_TIME so 00207 // that we will no longer attempt to distribute for a while. Whenever 00208 // objects are added or removed to this node this flag will be decreased 00209 // so that when it becomes 0 we can make a new Distribute() attempt can 00210 // be made. This situation should be rare though. 00211 #define DISALLOW_DISTRIBUTE_TIME 20 00212 int disallow_distribute; 00213 00214 // Current timestamp we are using for Front2Back(). Objects that 00215 // have the same timestamp are already visited during Front2Back(). 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 // Debugging functions. 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* /*g3d*/) { } 00453 virtual bool DebugCommand (const char*) { return false; } 00454 }; 00455 00458 #endif // __CS_KDTREE_H__ 00459
Generated for Crystal Space 2.0 by doxygen 1.6.1