csgeom/kdtree.h
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 #include "csgeom/vector2.h" 00026 #include "csgeom/math2d.h" 00027 #include "csutil/scfstr.h" 00028 #include "csutil/ref.h" 00029 #include "csutil/blockallocator.h" 00030 #include "iutil/dbghelp.h" 00031 00032 struct iGraphics3D; 00033 class csKDTree; 00034 00057 typedef bool (csKDTreeVisitFunc)(csKDTree* treenode, void* userdata, 00058 uint32 timestamp, uint32& frustum_mask); 00059 00063 class CS_CSGEOM_EXPORT csKDTreeChild 00064 { 00065 private: 00066 friend class csKDTree; 00067 00068 csBox3 bbox; 00069 void* object; // Pointer back to the original object. 00070 csKDTree** leafs; // Leafs that contain this object. 00071 int num_leafs; 00072 int max_leafs; 00073 00074 public: 00075 uint32 timestamp; // Timestamp of last visit to this child. 00076 00077 public: 00078 csKDTreeChild (); 00079 ~csKDTreeChild (); 00080 00082 void AddLeaf (csKDTree* leaf); 00084 void RemoveLeaf (int idx); 00086 void RemoveLeaf (csKDTree* leaf); 00093 void ReplaceLeaf (csKDTree* old_leaf, csKDTree* new_leaf); 00094 00098 int FindLeaf (csKDTree* leaf); 00099 00103 const csBox3& GetBBox () const { return bbox; } 00104 00108 void* GetObject () const { return object; } 00109 }; 00110 00111 #define CS_KDTREE_AXISINVALID -1 00112 #define CS_KDTREE_AXISX 0 00113 #define CS_KDTREE_AXISY 1 00114 #define CS_KDTREE_AXISZ 2 00115 00132 class CS_CSGEOM_EXPORT csKDTree : public iBase 00133 { 00134 private: 00135 static csBlockAllocator<csKDTree> tree_nodes; 00136 static csBlockAllocator<csKDTreeChild> tree_children; 00137 00138 csKDTree* child1; // If child1 is not 0 then child2 will 00139 csKDTree* child2; // also be not 0. 00140 csKDTree* parent; // 0 if this is the root. 00141 00142 csRef<iBase> userobject; // An optional user object for this node. 00143 00144 csBox3 node_bbox; // Bbox of the node itself. 00145 00146 int split_axis; // One of CS_KDTREE_AXIS? 00147 float split_location; // Where is the split? 00148 00149 // Objects in this node. If this node also has children (child1 00150 // and child2) then the objects here have to be moved to these 00151 // children. The 'Distribute()' function will do that. 00152 csKDTreeChild** objects; 00153 int num_objects; 00154 int max_objects; 00155 00156 // Estimate of the total number of objects in this tree including children. 00157 int estimate_total_objects; 00158 00159 // Disallow Distribute(). 00160 // If this flag is true it means that we cannot find a good split 00161 // location for the current list of objects. So in that case we don't 00162 // split at all and set this flag to true so that we will no longer 00163 // attempt to distribute. Whenever objects are added or removed to this 00164 // node this flag will be set to false again so that a new Distribute() 00165 // attempt can be made. This situation should be rare though. 00166 bool disallow_distribute; 00167 00168 // Current timestamp we are using for Front2Back(). Objects that 00169 // have the same timestamp are already visited during Front2Back(). 00170 static uint32 global_timestamp; 00171 00173 void AddObject (csKDTreeChild* obj); 00175 void RemoveObject (int idx); 00177 int FindObject (csKDTreeChild* obj); 00178 00182 void AddObject (const csBox3& bbox, csKDTreeChild* obj); 00183 00194 float FindBestSplitLocation (int axis, float& split_loc); 00195 00201 void DistributeLeafObjects (); 00202 00209 void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func, 00210 void* userdata, uint32 cur_timestamp, uint32 frustum_mask); 00211 00218 void TraverseRandom (csKDTreeVisitFunc* func, 00219 void* userdata, uint32 cur_timestamp, uint32 frustum_mask); 00220 00224 void ResetTimestamps (); 00225 00229 void FlattenTo (csKDTree* node); 00230 00231 public: 00233 csKDTree (); 00235 virtual ~csKDTree (); 00237 void SetParent (csKDTree* p) { parent = p; } 00238 00240 void Clear (); 00241 00242 SCF_DECLARE_IBASE; 00243 00245 iBase* GetUserObject () const { return userobject; } 00246 00252 void SetUserObject (iBase* userobj); 00253 00261 csKDTreeChild* AddObject (const csBox3& bbox, void* object); 00262 00267 void UnlinkObject (csKDTreeChild* object); 00268 00273 void RemoveObject (csKDTreeChild* object); 00274 00278 void MoveObject (csKDTreeChild* object, const csBox3& new_bbox); 00279 00286 void Distribute (); 00287 00291 void FullDistribute (); 00292 00298 void Flatten (); 00299 00305 void TraverseRandom (csKDTreeVisitFunc* func, 00306 void* userdata, uint32 frustum_mask); 00307 00314 void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func, 00315 void* userdata, uint32 frustum_mask); 00316 00324 uint32 NewTraversal (); 00325 00329 csKDTree* GetChild1 () const { return child1; } 00330 00334 csKDTree* GetChild2 () const { return child2; } 00335 00339 int GetObjectCount () const { return num_objects; } 00340 00347 int GetEstimatedObjectCount () { return estimate_total_objects; } 00348 00352 csKDTreeChild** GetObjects () const { return objects; } 00353 00358 const csBox3& GetNodeBBox () const { return node_bbox; } 00359 00360 // Debugging functions. 00361 bool Debug_CheckTree (csString& str); 00362 csPtr<iString> Debug_UnitTest (); 00363 void Debug_Dump (csString& str, int indent); 00364 void Debug_Statistics (int& tot_objects, 00365 int& tot_nodes, int& tot_leaves, int depth, int& max_depth, 00366 float& balance_quality); 00367 csPtr<iString> Debug_Statistics (); 00368 csTicks Debug_Benchmark (int num_iterations); 00369 00370 struct DebugHelper : public iDebugHelper 00371 { 00372 SCF_DECLARE_EMBEDDED_IBASE (csKDTree); 00373 virtual int GetSupportedTests () const 00374 { 00375 return CS_DBGHELP_UNITTEST | CS_DBGHELP_STATETEST | 00376 CS_DBGHELP_TXTDUMP | CS_DBGHELP_BENCHMARK; 00377 } 00378 virtual csPtr<iString> UnitTest () 00379 { 00380 return scfParent->Debug_UnitTest (); 00381 } 00382 virtual csPtr<iString> StateTest () 00383 { 00384 scfString* rc = new scfString (); 00385 if (!scfParent->Debug_CheckTree (rc->GetCsString ())) 00386 return csPtr<iString> (rc); 00387 delete rc; 00388 return 0; 00389 } 00390 virtual csTicks Benchmark (int num_iterations) 00391 { 00392 return scfParent->Debug_Benchmark (num_iterations); 00393 } 00394 virtual csPtr<iString> Dump () 00395 { 00396 scfString* rc = new scfString (); 00397 scfParent->Debug_Dump (rc->GetCsString (), 0); 00398 return csPtr<iString> (rc); 00399 } 00400 virtual void Dump (iGraphics3D* /*g3d*/) 00401 { 00402 } 00403 virtual bool DebugCommand (const char*) 00404 { 00405 return false; 00406 } 00407 } scfiDebugHelper; 00408 }; 00409 00410 #endif // __CS_KDTREE_H__ 00411
Generated for Crystal Space by doxygen 1.2.18