Public API Reference

csgeom/kdtree.h

Go to the documentation of this file.

/*
    Copyright (C) 2002 by Jorrit Tyberghein

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifndef __CS_KDTREE_H__
#define __CS_KDTREE_H__

#include "csextern.h"

#include "csgeom/box.h"

#include "csutil/blockallocator.h"
#include "csutil/ref.h"
#include "csutil/scfstr.h"
#include "csutil/scf_implementation.h"

#include "iutil/dbghelp.h"

struct iGraphics3D;
struct iString;
class csKDTree;
class csKDTreeChild;

struct iKDTreeObjectDescriptor : public virtual iBase
{
  SCF_INTERFACE (iKDTreeObjectDescriptor, 0, 0, 1);

  virtual csPtr<iString> DescribeObject (csKDTreeChild* child) = 0;
};

struct iKDTreeUserData : public virtual iBase
{
  SCF_INTERFACE (iKDTreeUserData, 0, 0, 1);
};

typedef bool (csKDTreeVisitFunc)(csKDTree* treenode, void* userdata,
        uint32 timestamp, uint32& frustum_mask);

class CS_CRYSTALSPACE_EXPORT csKDTreeChild
{
private:
  friend class csKDTree;

  csBox3 bbox;
  void* object;                 // Pointer back to the original object.
  csKDTree** leafs;             // Leafs that contain this object.
  int num_leafs;
  int max_leafs;

public:
  uint32 timestamp;             // Timestamp of last visit to this child.

public:
  csKDTreeChild ();
  ~csKDTreeChild ();

  void AddLeaf (csKDTree* leaf);
  void RemoveLeaf (int idx);
  void RemoveLeaf (csKDTree* leaf);
  void ReplaceLeaf (csKDTree* old_leaf, csKDTree* new_leaf);

  int FindLeaf (csKDTree* leaf);

  inline const csBox3& GetBBox () const { return bbox; }

  inline void* GetObject () const { return object; }
};

enum
{
  CS_KDTREE_AXISINVALID = -1,
  CS_KDTREE_AXISX = 0,
  CS_KDTREE_AXISY = 1,
  CS_KDTREE_AXISZ = 2
};

class CS_CRYSTALSPACE_EXPORT csKDTree :
  public scfImplementation1<csKDTree, iDebugHelper>
{
public:
  // This is used for debugging.
  csRef<iKDTreeObjectDescriptor> descriptor;
  void DumpObject (csKDTreeChild* object, const char* msg);
  void DumpNode ();
  void DumpNode (const char* msg);
  void DebugExit ();

private:
  csKDTree* child1;             // If child1 is not 0 then child2 will
  csKDTree* child2;             // also be not 0.
  csKDTree* parent;             // 0 if this is the root.

  csRef<iKDTreeUserData> userobject; // An optional user object for this node.

  csBox3 node_bbox;             // Bbox of the node itself.

  int split_axis;               // One of CS_KDTREE_AXIS?
  float split_location;         // Where is the split?

  // Objects in this node. If this node also has children (child1
  // and child2) then the objects here have to be moved to these
  // children. The 'Distribute()' function will do that.
  csKDTreeChild** objects;
  int num_objects;
  int max_objects;

  // Estimate of the total number of objects in this tree including children.
  int estimate_total_objects;

  // Disallow Distribute().
  // If this flag > 0 it means that we cannot find a good split
  // location for the current list of objects. So in that case we don't
  // split at all and set this flag to DISALLOW_DISTRIBUTE_TIME so
  // that we will no longer attempt to distribute for a while. Whenever
  // objects are added or removed to this node this flag will be decreased
  // so that when it becomes 0 we can make a new Distribute() attempt can
  // be made. This situation should be rare though.
#define DISALLOW_DISTRIBUTE_TIME 20
  int disallow_distribute;

  // Current timestamp we are using for Front2Back(). Objects that
  // have the same timestamp are already visited during Front2Back().
  static uint32 global_timestamp;

  void AddObject (csKDTreeChild* obj);
  void RemoveObject (int idx);
  int FindObject (csKDTreeChild* obj);

  void AddObjectInt (csKDTreeChild* obj);

  float FindBestSplitLocation (int axis, float& split_loc);

  void DistributeLeafObjects ();

  void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func,
        void* userdata, uint32 cur_timestamp, uint32 frustum_mask);

  void TraverseRandom (csKDTreeVisitFunc* func,
        void* userdata, uint32 cur_timestamp, uint32 frustum_mask);

  void ResetTimestamps ();

  void FlattenTo (csKDTree* node);

public:
  csKDTree ();
  virtual ~csKDTree ();
  void SetParent (csKDTree* p) { parent = p; }

  void SetObjectDescriptor (iKDTreeObjectDescriptor* descriptor)
  {
    csKDTree::descriptor = descriptor;
  }

  void Clear ();

  inline iKDTreeUserData* GetUserObject () const { return userobject; }

  void SetUserObject (iKDTreeUserData* userobj);

  csKDTreeChild* AddObject (const csBox3& bbox, void* object);

  void UnlinkObject (csKDTreeChild* object);

  void RemoveObject (csKDTreeChild* object);

  void MoveObject (csKDTreeChild* object, const csBox3& new_bbox);

  void Distribute ();

  void FullDistribute ();

  void Flatten ();

  void TraverseRandom (csKDTreeVisitFunc* func,
        void* userdata, uint32 frustum_mask);

  void Front2Back (const csVector3& pos, csKDTreeVisitFunc* func,
        void* userdata, uint32 frustum_mask);

  uint32 NewTraversal ();

  inline csKDTree* GetChild1 () const { return child1; }

  inline csKDTree* GetChild2 () const { return child2; }

  inline int GetObjectCount () const { return num_objects; }

  inline int GetEstimatedObjectCount () { return estimate_total_objects; }

  inline csKDTreeChild** GetObjects () const { return objects; }

  inline const csBox3& GetNodeBBox () const { return node_bbox; }

  // Debugging functions.
  bool Debug_CheckTree (csString& str);
  csPtr<iString> Debug_UnitTest ();
  void Debug_Dump (csString& str, int indent);
  void Debug_Statistics (int& tot_objects,
        int& tot_nodes, int& tot_leaves, int depth, int& max_depth,
        float& balance_quality);
  csPtr<iString> Debug_Statistics ();
  csTicks Debug_Benchmark (int num_iterations);

  virtual int GetSupportedTests () const
  {
    return CS_DBGHELP_UNITTEST | CS_DBGHELP_STATETEST |
      CS_DBGHELP_TXTDUMP | CS_DBGHELP_BENCHMARK;
  }

  virtual csPtr<iString> UnitTest ()
  {
    return Debug_UnitTest ();
  }

  virtual csPtr<iString> StateTest ()
  {
    scfString* rc = new scfString ();
    if (!Debug_CheckTree (rc->GetCsString ()))
      return csPtr<iString> (rc);
    delete rc;
    return 0;
  }

  virtual csTicks Benchmark (int num_iterations)
  {
    return Debug_Benchmark (num_iterations);
  }

  virtual csPtr<iString> Dump ()
  {
    scfString* rc = new scfString ();
    Debug_Dump (rc->GetCsString (), 0);
    return csPtr<iString> (rc);
  }

  virtual void Dump (iGraphics3D* /*g3d*/) { }
  virtual bool DebugCommand (const char*) { return false; }
};

#endif // __CS_KDTREE_H__

---