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 "csgeom/box.h" 00023 #include "csgeom/vector2.h" 00024 #include "csgeom/math2d.h" 00025 #include "csutil/scfstr.h" 00026 #include "csutil/blockallocator.h" 00027 #include "iutil/dbghelp.h" 00028 00029 struct iGraphics3D; 00030 class csKDTree; 00031 00054 typedef bool (csKDTreeVisitFunc)(csKDTree* treenode, void* userdata, 00055 uint32 timestamp, uint32& frustum_mask); 00056 00060 class csKDTreeChild 00061 { 00062 private: 00063 friend class csKDTree; 00064 00065 csBox3 bbox; 00066 void* object; // Pointer back to the original object. 00067 csKDTree** leafs; // Leafs that contain this object. 00068 int num_leafs; 00069 int max_leafs; 00070 00071 public: 00072 uint32 timestamp; // Timestamp of last visit to this child. 00073 00074 public: 00075 csKDTreeChild (); 00076 ~csKDTreeChild (); 00077 00079 void AddLeaf (csKDTree* leaf); 00081 void RemoveLeaf (int idx); 00083 void RemoveLeaf (csKDTree* leaf); 00090 void ReplaceLeaf (csKDTree* old_leaf, csKDTree* new_leaf); 00091 00095 int FindLeaf (csKDTree* leaf); 00096 00100 const csBox3& GetBBox () const { return bbox; } 00101 00105 void* GetObject () const { return object; } 00106 }; 00107 00108 #define CS_KDTREE_AXISINVALID -1 00109 #define CS_KDTREE_AXISX 0 00110 #define CS_KDTREE_AXISY 1 00111 #define CS_KDTREE_AXISZ 2 00112 00129 class csKDTree : public iBase 00130 { 00131 private: 00132 static csBlockAllocator<csKDTree> tree_nodes; 00133 static csBlockAllocator<csKDTreeChild> tree_children; 00134 00135 csKDTree* child1; // If child1 is not 0 then child2 will 00136 csKDTree* child2; // also be not 0. 00137 csKDTree* parent; // 0 if this is the root. 00138 00139 iBase* userobject; // An optional user object for this node. 00140 00141 csBox3 node_bbox; // Bbox of the node itself. 00142 00143 int split_axis; // One of CS_KDTREE_AXIS? 00144 float split_location; // Where is the split? 00145 00146 // Objects in this node. If this node also has children (child1 00147 // and child2) then the objects here have to be moved to these 00148 // children. The 'Distribute()' function will do that. 00149 csKDTreeChild** objects; 00150 int num_objects; 00151 int max_objects; 00152 00153 // Estimate of the total number of objects in this tree including children. 00154 int estimate_total_objects; 00155 00156 // Disallow Distribute(). 00157 // If this flag is true it means that we cannot find a good split 00158 // location for the current list of objects. So in that case we don't 00159 // split at all and set this flag to true so that we will no longer 00160 // attempt to distribute. Whenever objects are added or removed to this 00161 // node this flag will be set to false again so that a new Distribute() 00162 // attempt can be made. This situation should be rare though. 00163 bool disallow_distribute; 00164 00165 // Current timestamp we are using for Front2Back(). Objects that 00166 // have the same timestamp are already visited during Front2Back(). 00167 static uint32 global_timestamp; 00168 00170 void AddObject (csKDTreeChild* obj); 00172 void RemoveObject (int idx); 00174 int FindObject (csKDTreeChild* obj); 00175 00179 void AddObject (const csBox3& bbox, csKDTreeChild* obj); 00180 00191 float FindBestSplitLocation (int axis, float& split_loc); 00192 00198 void DistributeLeafObjects (); 00199 00206 bool Front2Back (const csVector3& pos, csKDTreeVisitFunc* func, 00207 void* userdata, uint32 cur_timestamp, uint32 frustum_mask); 00208 00212 void ResetTimestamps (); 00213 00217 void FlattenTo (csKDTree* node); 00218 00219 public: 00221 csKDTree (); 00223 virtual ~csKDTree (); 00225 void SetParent (csKDTree* p) { parent = p; } 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 00308 int GetEstimatedObjectCount () { return estimate_total_objects; } 00309 00313 csKDTreeChild** GetObjects () const { return objects; } 00314 00319 const csBox3& GetNodeBBox () const { return node_bbox; } 00320 00321 // Debugging functions. 00322 bool Debug_CheckTree (csString& str); 00323 csPtr<iString> Debug_UnitTest (); 00324 void Debug_Dump (csString& str, int indent); 00325 void Debug_Statistics (int& tot_objects, 00326 int& tot_nodes, int& tot_leaves, int depth, int& max_depth, 00327 float& balance_quality); 00328 csPtr<iString> Debug_Statistics (); 00329 csTicks Debug_Benchmark (int num_iterations); 00330 00331 struct DebugHelper : public iDebugHelper 00332 { 00333 SCF_DECLARE_EMBEDDED_IBASE (csKDTree); 00334 virtual int GetSupportedTests () const 00335 { 00336 return CS_DBGHELP_UNITTEST | CS_DBGHELP_STATETEST | 00337 CS_DBGHELP_TXTDUMP | CS_DBGHELP_BENCHMARK; 00338 } 00339 virtual csPtr<iString> UnitTest () 00340 { 00341 return scfParent->Debug_UnitTest (); 00342 } 00343 virtual csPtr<iString> StateTest () 00344 { 00345 scfString* rc = new scfString (); 00346 if (!scfParent->Debug_CheckTree (rc->GetCsString ())) 00347 return csPtr<iString> (rc); 00348 delete rc; 00349 return 0; 00350 } 00351 virtual csTicks Benchmark (int num_iterations) 00352 { 00353 return scfParent->Debug_Benchmark (num_iterations); 00354 } 00355 virtual csPtr<iString> Dump () 00356 { 00357 scfString* rc = new scfString (); 00358 scfParent->Debug_Dump (rc->GetCsString (), 0); 00359 return csPtr<iString> (rc); 00360 } 00361 virtual void Dump (iGraphics3D* /*g3d*/) 00362 { 00363 } 00364 virtual bool DebugCommand (const char*) 00365 { 00366 return false; 00367 } 00368 } scfiDebugHelper; 00369 }; 00370 00371 #endif // __CS_KDTREE_H__ 00372
Generated for Crystal Space by doxygen 1.2.18