csgeom/kdtreex.h
Go to the documentation of this file.00001 /* 00002 Copyright (C) 2011 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_KDTREEX_H__ 00020 #define __CS_KDTREEX_H__ 00021 00022 #include "csextern.h" 00023 00024 #include "csgeom/box.h" 00025 #include "csgeom/sphere.h" 00026 #include "csgeom/kdtree.h" 00027 00028 #include "csutil/blockallocator.h" 00029 #include "csutil/ref.h" 00030 #include "csutil/scfstr.h" 00031 #include "csutil/scf_implementation.h" 00032 00033 #include "iutil/dbghelp.h" 00034 00041 struct iGraphics3D; 00042 struct iString; 00043 00044 namespace CS 00045 { 00046 namespace Geometry 00047 { 00048 00049 class KDTree; 00050 class KDTreeChild; 00051 00058 struct iObjectDescriptor : public virtual iBase 00059 { 00060 SCF_INTERFACE (CS::Geometry::iObjectDescriptor, 0, 0, 1); 00061 00062 virtual csPtr<iString> DescribeObject (KDTreeChild* child) = 0; 00063 }; 00064 00065 00088 typedef bool (KDTreeVisitFunc)(KDTree* treenode, void* userdata, 00089 uint32 timestamp, uint32& frustum_mask); 00090 00094 class KDTreeChild 00095 { 00096 private: 00097 friend class KDTree; 00098 00099 csSphere bsphere; 00100 void* object; // Pointer back to the original object. 00101 KDTree** leafs; // Leafs that contain this object. 00102 int num_leafs; 00103 int max_leafs; 00104 00105 public: 00106 uint32 timestamp; // Timestamp of last visit to this child. 00107 00108 public: 00109 KDTreeChild (); 00110 ~KDTreeChild (); 00111 00113 void AddLeaf (KDTree* leaf); 00115 void RemoveLeaf (int idx); 00117 void RemoveLeaf (KDTree* leaf); 00124 void ReplaceLeaf (KDTree* old_leaf, KDTree* new_leaf); 00125 00129 int FindLeaf (KDTree* leaf); 00130 00134 inline const csSphere& GetBSphere () const { return bsphere; } 00135 00139 inline void* GetObject () const { return object; } 00140 }; 00141 00142 enum 00143 { 00144 CS_KDTREE_AXISINVALID = -1, 00145 CS_KDTREE_AXISX = 0, 00146 CS_KDTREE_AXISY = 1, 00147 CS_KDTREE_AXISZ = 2 00148 }; 00149 00166 class CS_CRYSTALSPACE_EXPORT KDTree : 00167 public scfImplementation1<KDTree, iDebugHelper> 00168 { 00169 public: 00170 // This is used for debugging. 00171 csRef<iObjectDescriptor> descriptor; 00172 void DumpObject (KDTreeChild* object, const char* msg); 00173 void DumpNode (); 00174 void DumpNode (const char* msg); 00175 static void DebugExit (); 00176 00177 private: 00178 KDTree* child1; // If child1 is not 0 then child2 will 00179 KDTree* child2; // also be not 0. 00180 KDTree* parent; // 0 if this is the root. 00181 00182 csRef<iKDTreeUserData> userobject; // An optional user object for this node. 00183 00184 csBox3 node_bbox; // Bbox of the node itself. 00185 00186 int split_axis; // One of CS_KDTREE_AXIS? 00187 float split_location; // Where is the split? 00188 00189 // Objects in this node. If this node also has children (child1 00190 // and child2) then the objects here have to be moved to these 00191 // children. The 'Distribute()' function will do that. 00192 KDTreeChild** objects; 00193 int num_objects; 00194 int max_objects; 00195 00196 // Estimate of the total number of objects in this tree including children. 00197 int estimate_total_objects; 00198 00199 // Minimum amount of objects in this tree before we consider splitting. 00200 int min_split_objects; 00201 00202 // Disallow Distribute(). 00203 // If this flag > 0 it means that we cannot find a good split 00204 // location for the current list of objects. So in that case we don't 00205 // split at all and set this flag to DISALLOW_DISTRIBUTE_TIME so 00206 // that we will no longer attempt to distribute for a while. Whenever 00207 // objects are added or removed to this node this flag will be decreased 00208 // so that when it becomes 0 we can make a new Distribute() attempt can 00209 // be made. This situation should be rare though. 00210 #define DISALLOW_DISTRIBUTE_TIME 20 00211 int disallow_distribute; 00212 00213 // Current timestamp we are using for Front2Back(). Objects that 00214 // have the same timestamp are already visited during Front2Back(). 00215 static uint32 global_timestamp; 00216 00218 void AddObject (KDTreeChild* obj); 00220 void RemoveObject (int idx); 00222 int FindObject (KDTreeChild* obj); 00223 00227 void AddObjectInt (KDTreeChild* obj); 00228 00239 float FindBestSplitLocation (int axis, float& split_loc); 00240 00246 void DistributeLeafObjects (); 00247 00254 void Front2Back (const csVector3& pos, KDTreeVisitFunc* func, 00255 void* userdata, uint32 cur_timestamp, uint32 frustum_mask); 00256 00263 void TraverseRandom (KDTreeVisitFunc* func, 00264 void* userdata, uint32 cur_timestamp, uint32 frustum_mask); 00265 00269 void ResetTimestamps (); 00270 00274 void FlattenTo (KDTree* node); 00275 00276 public: 00278 KDTree (); 00280 virtual ~KDTree (); 00282 void SetParent (KDTree* p) { parent = p; } 00283 00285 void SetObjectDescriptor (iObjectDescriptor* descriptor) 00286 { 00287 KDTree::descriptor = descriptor; 00288 } 00289 00294 void SetMinimumSplitAmount (int m) { min_split_objects = m; } 00295 00297 void Clear (); 00298 00300 inline iKDTreeUserData* GetUserObject () const { return userobject; } 00301 00307 void SetUserObject (iKDTreeUserData* userobj); 00308 00316 KDTreeChild* AddObject (const csSphere& bsphere, void* object); 00317 00322 void UnlinkObject (KDTreeChild* object); 00323 00328 void RemoveObject (KDTreeChild* object); 00329 00333 void MoveObject (KDTreeChild* object, const csSphere& new_bsphere); 00334 00341 void Distribute (); 00342 00346 void FullDistribute (); 00347 00353 void Flatten (); 00354 00360 void TraverseRandom (KDTreeVisitFunc* func, 00361 void* userdata, uint32 frustum_mask); 00362 00369 void Front2Back (const csVector3& pos, KDTreeVisitFunc* func, 00370 void* userdata, uint32 frustum_mask); 00371 00379 uint32 NewTraversal (); 00380 00384 inline KDTree* GetChild1 () const { return child1; } 00385 00389 inline KDTree* GetChild2 () const { return child2; } 00390 00394 inline int GetObjectCount () const { return num_objects; } 00395 00402 inline int GetEstimatedObjectCount () { return estimate_total_objects; } 00403 00407 inline KDTreeChild** GetObjects () const { return objects; } 00408 00413 inline const csBox3& GetNodeBBox () const { return node_bbox; } 00414 00415 // Debugging functions. 00416 bool Debug_CheckTree (csString& str); 00417 void Debug_Dump (csString& str, int indent); 00418 void Debug_Statistics (int& tot_objects, 00419 int& tot_nodes, int& tot_leaves, int depth, int& max_depth, 00420 float& balance_quality); 00421 csPtr<iString> Debug_Statistics (); 00422 csTicks Debug_Benchmark (int num_iterations); 00423 00424 virtual int GetSupportedTests () const 00425 { 00426 return CS_DBGHELP_STATETEST | 00427 CS_DBGHELP_TXTDUMP | CS_DBGHELP_BENCHMARK; 00428 } 00429 00430 virtual csPtr<iString> StateTest () 00431 { 00432 scfString* rc = new scfString (); 00433 if (!Debug_CheckTree (rc->GetCsString ())) 00434 return csPtr<iString> (rc); 00435 delete rc; 00436 return 0; 00437 } 00438 00439 virtual csTicks Benchmark (int num_iterations) 00440 { 00441 return Debug_Benchmark (num_iterations); 00442 } 00443 00444 virtual csPtr<iString> Dump () 00445 { 00446 scfString* rc = new scfString (); 00447 Debug_Dump (rc->GetCsString (), 0); 00448 return csPtr<iString> (rc); 00449 } 00450 00451 virtual void Dump (iGraphics3D* /*g3d*/) { } 00452 virtual bool DebugCommand (const char*) { return false; } 00453 }; 00454 00455 } 00456 } 00457 00460 #endif // __CS_KDTREEX_H__ 00461
Generated for Crystal Space 2.0 by doxygen 1.6.1