| ## Public API Reference

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# 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