CrystalSpace

Public API Reference

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

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 "iutil/dbghelp.h"
00027 
00028 struct iGraphics3D;
00029 class csKDTree;
00030 
00053 typedef bool (csKDTreeVisitFunc)(csKDTree* treenode, void* userdata,
00054         uint32 timestamp, uint32& frustum_mask);
00055 
00059 class csKDTreeChild
00060 {
00061 private:
00062   friend class csKDTree;
00063 
00064   csBox3 bbox;
00065   void* object;                 // Pointer back to the original object.
00066   csKDTree** leafs;             // Leafs that contain this object.
00067   int num_leafs;
00068   int max_leafs;
00069 
00070 public:
00071   uint32 timestamp;             // Timestamp of last visit to this child.
00072 
00073 public:
00074   csKDTreeChild ();
00075   ~csKDTreeChild ();
00076 
00078   void AddLeaf (csKDTree* leaf);
00080   void RemoveLeaf (int idx);
00082   void RemoveLeaf (csKDTree* leaf);
00089   void ReplaceLeaf (csKDTree* old_leaf, csKDTree* new_leaf);
00090 
00094   int FindLeaf (csKDTree* leaf);
00095 
00099   const csBox3& GetBBox () const { return bbox; }
00100 
00104   void* GetObject () const { return object; }
00105 };
00106 
00107 #define CS_KDTREE_AXISINVALID -1
00108 #define CS_KDTREE_AXISX 0
00109 #define CS_KDTREE_AXISY 1
00110 #define CS_KDTREE_AXISZ 2
00111 
00128 class csKDTree : public iBase
00129 {
00130 private:
00131   csKDTree* child1;             // If child1 is not 0 then child2 will
00132   csKDTree* child2;             // also be not 0.
00133   csKDTree* parent;             // 0 if this is the root.
00134 
00135   iBase* userobject;            // An optional user object for this node.
00136 
00137   bool obj_bbox_valid;          // If false obj_bbox is not valid.
00138   csBox3 obj_bbox;              // Bbox of all objects in this node.
00139   csBox3 node_bbox;             // Bbox of the node itself.
00140 
00141   int split_axis;               // One of CS_KDTREE_AXIS?
00142   float split_location;         // Where is the split?
00143 
00144   // Objects in this node. If this node also has children (child1
00145   // and child2) then the objects here have to be moved to these
00146   // children. The 'Distribute()' function will do that.
00147   csKDTreeChild** objects;
00148   int num_objects;
00149   int max_objects;
00150 
00151   // Disallow Distribute().
00152   // If this flag is true it means that we cannot find a good split
00153   // location for the current list of objects. So in that case we don't
00154   // split at all and set this flag to true so that we will no longer
00155   // attempt to distribute. Whenever objects are added or removed to this
00156   // node this flag will be set to false again so that a new Distribute()
00157   // attempt can be made. This situation should be rare though.
00158   bool disallow_distribute;
00159 
00160   // Current timestamp we are using for Front2Back(). Objects that
00161   // have the same timestamp are already visited during Front2Back().
00162   static uint32 global_timestamp;
00163 
00165   void AddObject (csKDTreeChild* obj);
00167   void RemoveObject (int idx);
00169   int FindObject (csKDTreeChild* obj);
00170 
00174   void AddObject (const csBox3& bbox, csKDTreeChild* obj);
00175 
00186   int FindBestSplitLocation (int axis, float& split_loc);
00187 
00193   void DistributeLeafObjects ();
00194 
00200   void UpdateBBox (const csBox3& bbox);
00201 
00208   bool Front2Back (const csVector3& pos, csKDTreeVisitFunc* func,
00209         void* userdata, uint32 cur_timestamp, uint32 frustum_mask);
00210 
00214   void ResetTimestamps ();
00215 
00219   void FlattenTo (csKDTree* node);
00220 
00221 public:
00223   csKDTree (csKDTree* parent);
00225   virtual ~csKDTree ();
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 
00305   csKDTreeChild** GetObjects () const { return objects; }
00306 
00310   const csBox3& GetObjectBBox ();
00311 
00316   const csBox3& GetNodeBBox () const { return node_bbox; }
00317 
00318   // Debugging functions.
00319   bool Debug_CheckTree (csString& str);
00320   csPtr<iString> Debug_UnitTest ();
00321   void Debug_Dump (csString& str, int indent);
00322   void Debug_Statistics (int& tot_objects,
00323         int& tot_nodes, int& tot_leaves, int depth, int& max_depth,
00324         float& balance_quality);
00325   csPtr<iString> Debug_Statistics ();
00326   csTicks Debug_Benchmark (int num_iterations);
00327 
00328   struct DebugHelper : public iDebugHelper
00329   {
00330     SCF_DECLARE_EMBEDDED_IBASE (csKDTree);
00331     virtual int GetSupportedTests () const
00332     {
00333       return CS_DBGHELP_UNITTEST | CS_DBGHELP_STATETEST |
00334         CS_DBGHELP_TXTDUMP | CS_DBGHELP_BENCHMARK;
00335     }
00336     virtual csPtr<iString> UnitTest ()
00337     {
00338       return scfParent->Debug_UnitTest ();
00339     }
00340     virtual csPtr<iString> StateTest ()
00341     {
00342       scfString* rc = new scfString ();
00343       if (!scfParent->Debug_CheckTree (rc->GetCsString ()))
00344         return csPtr<iString> (rc);
00345       delete rc;
00346       return 0;
00347     }
00348     virtual csTicks Benchmark (int num_iterations)
00349     {
00350       return scfParent->Debug_Benchmark (num_iterations);
00351     }
00352     virtual csPtr<iString> Dump ()
00353     {
00354       scfString* rc = new scfString ();
00355       scfParent->Debug_Dump (rc->GetCsString (), 0);
00356       return csPtr<iString> (rc);
00357     }
00358     virtual void Dump (iGraphics3D* /*g3d*/)
00359     {
00360     }
00361     virtual bool DebugCommand (const char*)
00362     {
00363       return false;
00364     }
00365   } scfiDebugHelper;
00366 };
00367 
00368 #endif // __CS_KDTREE_H__
00369 

Generated for Crystal Space by doxygen 1.2.14