CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

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