CrystalSpace

Public API Reference

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.7.6.1