CrystalSpace

Public API Reference

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 
00062 struct iKDTreeUserData : public virtual iBase
00063 {
00064   SCF_INTERFACE (iKDTreeUserData, 0, 0, 1);
00065 };
00066 
00089 typedef bool (csKDTreeVisitFunc)(csKDTree* treenode, void* userdata,
00090         uint32 timestamp, uint32& frustum_mask);
00091 
00095 class CS_CRYSTALSPACE_EXPORT csKDTreeChild
00096 {
00097 private:
00098   friend class csKDTree;
00099 
00100   csBox3 bbox;
00101   void* object;                 // Pointer back to the original object.
00102   csKDTree** leafs;             // Leafs that contain this object.
00103   int num_leafs;
00104   int max_leafs;
00105 
00106 public:
00107   uint32 timestamp;             // Timestamp of last visit to this child.
00108 
00109 public:
00110   csKDTreeChild ();
00111   ~csKDTreeChild ();
00112 
00114   void AddLeaf (csKDTree* leaf);
00116   void RemoveLeaf (int idx);
00118   void RemoveLeaf (csKDTree* leaf);
00125   void ReplaceLeaf (csKDTree* old_leaf, csKDTree* new_leaf);
00126 
00130   int FindLeaf (csKDTree* leaf);
00131 
00135   inline const csBox3& GetBBox () const { return bbox; }
00136 
00140   inline void* GetObject () const { return object; }
00141 };
00142 
00143 enum
00144 {
00145   CS_KDTREE_AXISINVALID = -1,
00146   CS_KDTREE_AXISX = 0,
00147   CS_KDTREE_AXISY = 1,
00148   CS_KDTREE_AXISZ = 2
00149 };
00150 
00167 class CS_CRYSTALSPACE_EXPORT csKDTree :
00168   public scfImplementation1<csKDTree, iDebugHelper>
00169 {
00170 public:
00171   // This is used for debugging.
00172   csRef<iKDTreeObjectDescriptor> descriptor;
00173   void DumpObject (csKDTreeChild* object, const char* msg);
00174   void DumpNode ();
00175   void DumpNode (const char* msg);
00176   void DebugExit ();
00177 
00178 private:
00179   csKDTree* child1;             // If child1 is not 0 then child2 will
00180   csKDTree* child2;             // also be not 0.
00181   csKDTree* parent;             // 0 if this is the root.
00182 
00183   csRef<iKDTreeUserData> userobject; // An optional user object for this node.
00184 
00185   csBox3 node_bbox;             // Bbox of the node itself.
00186 
00187   int split_axis;               // One of CS_KDTREE_AXIS?
00188   float split_location;         // Where is the split?
00189 
00190   // Objects in this node. If this node also has children (child1
00191   // and child2) then the objects here have to be moved to these
00192   // children. The 'Distribute()' function will do that.
00193   csKDTreeChild** objects;
00194   int num_objects;
00195   int max_objects;
00196 
00197   // Estimate of the total number of objects in this tree including children.
00198   int estimate_total_objects;
00199 
00200   // Disallow Distribute().
00201   // If this flag > 0 it means that we cannot find a good split
00202   // location for the current list of objects. So in that case we don't
00203   // split at all and set this flag to DISALLOW_DISTRIBUTE_TIME so
00204   // that we will no longer attempt to distribute for a while. Whenever
00205   // objects are added or removed to this node this flag will be decreased
00206   // so that when it becomes 0 we can make a new Distribute() attempt can
00207   // be made. This situation should be rare though.
00208 #define DISALLOW_DISTRIBUTE_TIME 20
00209   int disallow_distribute;
00210 
00211   // Current timestamp we are using for Front2Back(). Objects that
00212   // have the same timestamp are already visited during Front2Back().
00213   static uint32 global_timestamp;
00214 
00216   void AddObject (csKDTreeChild* obj);
00218   void RemoveObject (int idx);
00220   int FindObject (csKDTreeChild* obj);
00221 
00225   void AddObjectInt (csKDTreeChild* obj);
00226 
00237   float FindBestSplitLocation (int axis, float& split_loc);
00238 
00244   void DistributeLeafObjects ();
00245 
00252   void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func,
00253         void* userdata, uint32 cur_timestamp, uint32 frustum_mask);
00254 
00261   void TraverseRandom (csKDTreeVisitFunc* func,
00262         void* userdata, uint32 cur_timestamp, uint32 frustum_mask);
00263 
00267   void ResetTimestamps ();
00268 
00272   void FlattenTo (csKDTree* node);
00273 
00274 public:
00276   csKDTree ();
00278   virtual ~csKDTree ();
00280   void SetParent (csKDTree* p) { parent = p; }
00281 
00283   void SetObjectDescriptor (iKDTreeObjectDescriptor* descriptor)
00284   {
00285     csKDTree::descriptor = descriptor;
00286   }
00287 
00289   void Clear ();
00290 
00292   inline iKDTreeUserData* GetUserObject () const { return userobject; }
00293 
00299   void SetUserObject (iKDTreeUserData* userobj);
00300 
00308   csKDTreeChild* AddObject (const csBox3& bbox, void* object);
00309 
00314   void UnlinkObject (csKDTreeChild* object);
00315 
00320   void RemoveObject (csKDTreeChild* object);
00321 
00325   void MoveObject (csKDTreeChild* object, const csBox3& new_bbox);
00326 
00333   void Distribute ();
00334 
00338   void FullDistribute ();
00339 
00345   void Flatten ();
00346 
00352   void TraverseRandom (csKDTreeVisitFunc* func,
00353         void* userdata, uint32 frustum_mask);
00354 
00361   void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func,
00362         void* userdata, uint32 frustum_mask);
00363 
00371   uint32 NewTraversal ();
00372 
00376   inline csKDTree* GetChild1 () const { return child1; }
00377 
00381   inline csKDTree* GetChild2 () const { return child2; }
00382 
00386   inline int GetObjectCount () const { return num_objects; }
00387 
00394   inline int GetEstimatedObjectCount () { return estimate_total_objects; }
00395 
00399   inline csKDTreeChild** GetObjects () const { return objects; }
00400 
00405   inline const csBox3& GetNodeBBox () const { return node_bbox; }
00406 
00407   // Debugging functions.
00408   bool Debug_CheckTree (csString& str);
00409   csPtr<iString> Debug_UnitTest ();
00410   void Debug_Dump (csString& str, int indent);
00411   void Debug_Statistics (int& tot_objects,
00412         int& tot_nodes, int& tot_leaves, int depth, int& max_depth,
00413         float& balance_quality);
00414   csPtr<iString> Debug_Statistics ();
00415   csTicks Debug_Benchmark (int num_iterations);
00416 
00417   virtual int GetSupportedTests () const
00418   {
00419     return CS_DBGHELP_UNITTEST | CS_DBGHELP_STATETEST |
00420       CS_DBGHELP_TXTDUMP | CS_DBGHELP_BENCHMARK;
00421   }
00422 
00423   virtual csPtr<iString> UnitTest ()
00424   {
00425     return Debug_UnitTest ();
00426   }
00427 
00428   virtual csPtr<iString> StateTest ()
00429   {
00430     scfString* rc = new scfString ();
00431     if (!Debug_CheckTree (rc->GetCsString ()))
00432       return csPtr<iString> (rc);
00433     delete rc;
00434     return 0;
00435   }
00436 
00437   virtual csTicks Benchmark (int num_iterations)
00438   {
00439     return Debug_Benchmark (num_iterations);
00440   }
00441 
00442   virtual csPtr<iString> Dump ()
00443   {
00444     scfString* rc = new scfString ();
00445     Debug_Dump (rc->GetCsString (), 0);
00446     return csPtr<iString> (rc);
00447   }
00448 
00449   virtual void Dump (iGraphics3D* /*g3d*/) { }
00450   virtual bool DebugCommand (const char*) { return false; }
00451 };
00452 
00455 #endif // __CS_KDTREE_H__
00456 

Generated for Crystal Space 1.0.2 by doxygen 1.4.7