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 00079 typedef bool (csKDTreeVisitFunc)(csKDTree* treenode, void* userdata, 00080 uint32 timestamp, uint32& frustum_mask); 00081 00085 class CS_CRYSTALSPACE_EXPORT csKDTreeChild 00086 { 00087 private: 00088 friend class csKDTree; 00089 00090 csBox3 bbox; 00091 void* object; // Pointer back to the original object. 00092 csKDTree** leafs; // Leafs that contain this object. 00093 int num_leafs; 00094 int max_leafs; 00095 00096 public: 00097 uint32 timestamp; // Timestamp of last visit to this child. 00098 00099 public: 00100 csKDTreeChild (); 00101 ~csKDTreeChild (); 00102 00104 void AddLeaf (csKDTree* leaf); 00106 void RemoveLeaf (int idx); 00108 void RemoveLeaf (csKDTree* leaf); 00115 void ReplaceLeaf (csKDTree* old_leaf, csKDTree* new_leaf); 00116 00120 int FindLeaf (csKDTree* leaf); 00121 00125 inline const csBox3& GetBBox () const { return bbox; } 00126 00130 inline void* GetObject () const { return object; } 00131 }; 00132 00133 enum 00134 { 00135 CS_KDTREE_AXISINVALID = -1, 00136 CS_KDTREE_AXISX = 0, 00137 CS_KDTREE_AXISY = 1, 00138 CS_KDTREE_AXISZ = 2 00139 }; 00140 00157 class CS_CRYSTALSPACE_EXPORT csKDTree : 00158 public scfImplementation1<csKDTree, iDebugHelper> 00159 { 00160 public: 00161 // This is used for debugging. 00162 csRef<iKDTreeObjectDescriptor> descriptor; 00163 void DumpObject (csKDTreeChild* object, const char* msg); 00164 void DumpNode (); 00165 void DumpNode (const char* msg); 00166 void DebugExit (); 00167 00168 private: 00169 static csBlockAllocator<csKDTree> tree_nodes; 00170 static csBlockAllocator<csKDTreeChild> tree_children; 00171 00172 csKDTree* child1; // If child1 is not 0 then child2 will 00173 csKDTree* child2; // also be not 0. 00174 csKDTree* parent; // 0 if this is the root. 00175 00176 csRef<iBase> userobject; // An optional user object for this node. 00177 00178 csBox3 node_bbox; // Bbox of the node itself. 00179 00180 int split_axis; // One of CS_KDTREE_AXIS? 00181 float split_location; // Where is the split? 00182 00183 // Objects in this node. If this node also has children (child1 00184 // and child2) then the objects here have to be moved to these 00185 // children. The 'Distribute()' function will do that. 00186 csKDTreeChild** objects; 00187 int num_objects; 00188 int max_objects; 00189 00190 // Estimate of the total number of objects in this tree including children. 00191 int estimate_total_objects; 00192 00193 // Disallow Distribute(). 00194 // If this flag > 0 it means that we cannot find a good split 00195 // location for the current list of objects. So in that case we don't 00196 // split at all and set this flag to DISALLOW_DISTRIBUTE_TIME so 00197 // that we will no longer attempt to distribute for a while. Whenever 00198 // objects are added or removed to this node this flag will be decreased 00199 // so that when it becomes 0 we can make a new Distribute() attempt can 00200 // be made. This situation should be rare though. 00201 #define DISALLOW_DISTRIBUTE_TIME 20 00202 int disallow_distribute; 00203 00204 // Current timestamp we are using for Front2Back(). Objects that 00205 // have the same timestamp are already visited during Front2Back(). 00206 static uint32 global_timestamp; 00207 00209 void AddObject (csKDTreeChild* obj); 00211 void RemoveObject (int idx); 00213 int FindObject (csKDTreeChild* obj); 00214 00218 void AddObject (const csBox3& bbox, csKDTreeChild* obj); 00219 00230 float FindBestSplitLocation (int axis, float& split_loc); 00231 00237 void DistributeLeafObjects (); 00238 00245 void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func, 00246 void* userdata, uint32 cur_timestamp, uint32 frustum_mask); 00247 00254 void TraverseRandom (csKDTreeVisitFunc* func, 00255 void* userdata, uint32 cur_timestamp, uint32 frustum_mask); 00256 00260 void ResetTimestamps (); 00261 00265 void FlattenTo (csKDTree* node); 00266 00267 public: 00269 csKDTree (); 00271 virtual ~csKDTree (); 00273 void SetParent (csKDTree* p) { parent = p; } 00274 00276 void SetObjectDescriptor (iKDTreeObjectDescriptor* descriptor) 00277 { 00278 csKDTree::descriptor = descriptor; 00279 } 00280 00282 void Clear (); 00283 00285 inline iBase* GetUserObject () const { return userobject; } 00286 00292 void SetUserObject (iBase* userobj); 00293 00301 csKDTreeChild* AddObject (const csBox3& bbox, void* object); 00302 00307 void UnlinkObject (csKDTreeChild* object); 00308 00313 void RemoveObject (csKDTreeChild* object); 00314 00318 void MoveObject (csKDTreeChild* object, const csBox3& new_bbox); 00319 00326 void Distribute (); 00327 00331 void FullDistribute (); 00332 00338 void Flatten (); 00339 00345 void TraverseRandom (csKDTreeVisitFunc* func, 00346 void* userdata, uint32 frustum_mask); 00347 00354 void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func, 00355 void* userdata, uint32 frustum_mask); 00356 00364 uint32 NewTraversal (); 00365 00369 inline csKDTree* GetChild1 () const { return child1; } 00370 00374 inline csKDTree* GetChild2 () const { return child2; } 00375 00379 inline int GetObjectCount () const { return num_objects; } 00380 00387 inline int GetEstimatedObjectCount () { return estimate_total_objects; } 00388 00392 inline csKDTreeChild** GetObjects () const { return objects; } 00393 00398 inline const csBox3& GetNodeBBox () const { return node_bbox; } 00399 00400 // Debugging functions. 00401 bool Debug_CheckTree (csString& str); 00402 csPtr<iString> Debug_UnitTest (); 00403 void Debug_Dump (csString& str, int indent); 00404 void Debug_Statistics (int& tot_objects, 00405 int& tot_nodes, int& tot_leaves, int depth, int& max_depth, 00406 float& balance_quality); 00407 csPtr<iString> Debug_Statistics (); 00408 csTicks Debug_Benchmark (int num_iterations); 00409 00410 virtual int GetSupportedTests () const 00411 { 00412 return CS_DBGHELP_UNITTEST | CS_DBGHELP_STATETEST | 00413 CS_DBGHELP_TXTDUMP | CS_DBGHELP_BENCHMARK; 00414 } 00415 00416 virtual csPtr<iString> UnitTest () 00417 { 00418 return Debug_UnitTest (); 00419 } 00420 00421 virtual csPtr<iString> StateTest () 00422 { 00423 scfString* rc = new scfString (); 00424 if (!Debug_CheckTree (rc->GetCsString ())) 00425 return csPtr<iString> (rc); 00426 delete rc; 00427 return 0; 00428 } 00429 00430 virtual csTicks Benchmark (int num_iterations) 00431 { 00432 return Debug_Benchmark (num_iterations); 00433 } 00434 00435 virtual csPtr<iString> Dump () 00436 { 00437 scfString* rc = new scfString (); 00438 Debug_Dump (rc->GetCsString (), 0); 00439 return csPtr<iString> (rc); 00440 } 00441 00442 virtual void Dump (iGraphics3D* /*g3d*/) { } 00443 virtual bool DebugCommand (const char*) { return false; } 00444 }; 00445 00448 #endif // __CS_KDTREE_H__ 00449
Generated for Crystal Space by doxygen 1.4.6