source: GTP/trunk/Lib/Vis/Preprocessing/src/KdTree.h @ 1989

#ifndef _KdTree_H__
#define _KdTree_H__

#include <functional>
using namespace std;

#include "Containers.h"
#include "AxisAlignedBox3.h"
#include "Ray.h"
#include "Pvs.h"
#include "Viewcell.h"
#include "VssRay.h"
#include "IntersectableWrapper.h"


namespace GtpVisibilityPreprocessor {

  
  class KdNode;
  class KdLeaf;
  class KdInterior;
  class Intersectable;
  class Beam;

  class KdTree;
  
  //  KdTree *SceneKdTree;

// --------------------------------------------------------------
// Static statistics for kd-tree search
// --------------------------------------------------------------
class KdTreeStatistics 
{
public:  
  // total number of nodes
  int nodes;
  // number of splits along each of the axes
  int splits[7];
  // totals number of rays
  int rays;
  // total number of query domains
  int queryDomains;
  // total number of ray references
  int rayRefs;
  // refs in non empty leafs
  int rayRefsNonZeroQuery;
  // total number of query references
  int objectRefs;
  // nodes with zero queries
  int zeroQueryNodes;
  // max depth nodes
  int maxDepthNodes;
  // max depth nodes
  int minCostNodes;
  // max number of rays per node
  int maxObjectRefs;
  // number of dynamically added ray refs
  int addedRayRefs;
  // number of dynamically removed ray refs
  int removedRayRefs;
  
  // Constructor
  KdTreeStatistics() {
    Reset();
  }

  int Nodes() const {return nodes;}
  int Interior() const { return nodes / 2; }
  int Leaves() const { return (nodes / 2) + 1; }

  void Reset() {
    nodes = 0;
    for (int i=0; i<7; i++)
      splits[i] = 0;
    rays = queryDomains = 0;
    rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
    zeroQueryNodes = 0;
    maxDepthNodes = 0;
    minCostNodes = 0;
    maxObjectRefs = 0;
    addedRayRefs = removedRayRefs = 0;
  }

  void
  Print(ostream &app) const;

  friend ostream &operator<<(ostream &s, const KdTreeStatistics &stat) {
    stat.Print(s);
    return s;
  }
  
};

  
class KdInterior;
/** Abstract class for kd-tree node */
class KdNode {
public:
  
  static int sMailId;
  static int sReservedMailboxes;
  int mMailbox;

  KdIntersectable *mIntersectable;
  
  void Mail() { mMailbox = sMailId; }
  //static void NewMail() { sMailId ++; }
  bool Mailed() const { return mMailbox == sMailId; }
 
  static void NewMail(const int reserve = 1) {
                sMailId += sReservedMailboxes;
                sReservedMailboxes = reserve;
        }
        void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
        bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }

  virtual ~KdNode(){};
  KdNode(KdInterior *parent);

  /** Determines whether this node is a leaf or interior node
      @return true if leaf
  */
  virtual bool IsLeaf() const = 0;

  /** Determines whether this node is the root of the tree
      @return true if root
  */
  virtual bool IsRoot() const {
    return mParent == NULL;
  }

  /** Parent of the node - the parent is a little overhead for maintanance of the tree,
      but allows various optimizations of tree traversal algorithms */
  KdInterior *mParent;
  short mDepth;
  short mPvsTermination;
};

/** Implementation of the kd-tree interior node */
class KdInterior : public KdNode {

public:
    
  KdInterior(KdInterior *parent):KdNode(parent), mBack(NULL), mFront(NULL) {}

  ~KdInterior();

  /** \sa KdNode::IsLeaf() */
  virtual bool IsLeaf() const { return false; }

  /** splitting axis */
  int mAxis;
  /** splitting position, absolute position within the bounding box of this node */
  float mPosition;
  /** bounding box of interior node */
  AxisAlignedBox3 mBox;

  /** back node */
  KdNode *mBack;
  /** front node */
  KdNode *mFront;

  void SetupChildLinks(KdNode *b, KdNode *f) {
    mBack = b;
    mFront = f;
    b->mParent = f->mParent = this;
  }
  
  void ReplaceChildLink(KdNode *oldChild, KdNode *newChild) {
    if (mBack == oldChild)
      mBack = newChild;
    else
      mFront = newChild;
  }
  
  
};
  
class SubdivisionCandidate;
  
/** Implementation of the kd-tree leaf node */
class KdLeaf : public KdNode {
public:
  KdLeaf(KdInterior *parent, const int objects):
          KdNode(parent), mViewCell(NULL) {
    mObjects.reserve(objects);
  }
  
  void AddPassingRay(const Ray &ray, const int contributions) {
    mPassingRays.AddRay(ray, contributions);
                //              Debug << "adding passing ray" << endl;
  }

  ~KdLeaf() { DEL_PTR(mViewCell);  }
        
        void AddPassingRay2(const Ray &ray,
                                                const int objects,
                                                const int viewcells
                                                ) {
    mPassingRays.AddRay2(ray, objects, viewcells);
                //              Debug << "adding passing ray" << endl;
  }

  /** \sa KdNode::IsLeaf() */
  virtual bool IsLeaf() const { return true; }


  /** pointers to occluders contained in this node */
  ObjectContainer mObjects;

  /** Ray set description of the rays passing through this node */
  PassingRaySet mPassingRays;
        
  /** PVS consisting of visible KdTree nodes */
  KdPvs mKdPvs;

  /// pvs of view cells seeing this node.
  SubdivisionCandidate *mSubdivisionCandidate;

  /// pointer to view cell.
  KdViewCell *mViewCell;

  VssRayContainer mVssRays;

   /// Objects that are referenced in more than one leaf.
  ObjectContainer mMultipleObjects;

  /// universal counter
  int mCounter;
};


/** KdTree for indexing scene entities - occluders/occludees/viewcells */
class KdTree {
  
protected:
  struct TraversalData
  {  
    KdNode *mNode;
    AxisAlignedBox3 mBox;
    int mDepth;
    float mPriority;
    
    TraversalData() {}

    TraversalData(KdNode *n, const float p):
      mNode(n), mPriority(p)
    {}
    
    TraversalData(KdNode *n,
                   const AxisAlignedBox3 &b,
                   const int d):
      mNode(n), mBox(b), mDepth(d) {}
    

    bool operator<(
                                   const TraversalData &b) const {
      KdLeaf *leafa = (KdLeaf *) mNode;
      KdLeaf *leafb = (KdLeaf *) b.mNode;
      return 
                leafa->mObjects.size()*mBox.SurfaceArea()
                <
                leafb->mObjects.size()*b.mBox.SurfaceArea();
    }


    // comparator for the 
    struct less_priority : public
    binary_function<const TraversalData, const TraversalData, bool> {
      
      bool operator()(const TraversalData a, const TraversalData b) {
                                return a.mPriority < b.mPriority;
      }
      
    };

  };

  

public:

  enum {SPLIT_OBJECT_MEDIAN,
        SPLIT_SPATIAL_MEDIAN,
        SPLIT_SAH};
  
  KdTree();

  ~KdTree();
    
  /** Insert view cell into the tree */
  virtual void InsertViewCell(ViewCell *viewCell) {
    //      mRoot->mViewcells.push_back(viewCell);
  }

  virtual bool Construct();

  /** Check whether subdivision criteria are met for the given subtree.
      If not subdivide the leafs of the subtree. The criteria are specified in
      the environment as well as the subdivision method. By default surface area
      heuristics is used.
        
      @param subtree root of the subtree

      @return true if subdivision was performed, false if subdivision criteria
      were already met
  */
  virtual KdNode *Subdivide(const TraversalData &tdata);

  /** Get the root of the tree */
  KdNode *GetRoot() const {
    return mRoot;
  }


  AxisAlignedBox3 GetBox() const { return mBox; }

  int
  CastRay(
                  Ray &ray
                  );
  

  int
  CastBeam(
                   Beam &beam
                   );
  
  
  /** Casts line segment into tree.
          @returns intersected view cells.
  */
  int CastLineSegment(const Vector3 &origin,
                                          const Vector3 &termination,
                                          vector<ViewCell *> &viewcells);


  const KdTreeStatistics &GetStatistics() const {
    return mStat;
  }

  /** Returns or creates a new intersectable for use in a kd based pvs.
          The OspTree is responsible for destruction of the intersectable.
  */
  KdIntersectable *GetOrCreateKdIntersectable(KdNode *node);


  void
  SetPvsTerminationNodes(
                                                 const float maxArea);
  
  KdNode *
  GetPvsNode(const Vector3 &point) const;
  

  void
  CollectKdObjects(const AxisAlignedBox3 &box,
                                   ObjectContainer &objects
                                   );

  void
  CollectObjects(KdNode *n, ObjectContainer &objects);

  void
  CollectObjects(const AxisAlignedBox3 &box,
                                 ObjectContainer &objects);

  void
  CollectLeaves(vector<KdLeaf *> &leaves);
        
  /** If the kd tree is used as view cell container, this
          methods creates the view cells.
          @returns the newly created view cells in a view cell container
  */
  void
  CreateAndCollectViewCells(ViewCellContainer &viewCells) const;

  AxisAlignedBox3 GetBox(const KdNode *node) const {
    KdInterior *parent = node->mParent;
    if (parent == NULL)
      return mBox;
    
    if (!node->IsLeaf())
      return ((KdInterior *)node)->mBox;
    
    AxisAlignedBox3 box(parent->mBox);
    if (parent->mFront == node)
      box.SetMin(parent->mAxis, parent->mPosition);
    else
      box.SetMax(parent->mAxis, parent->mPosition);
    return box;
  }

  float GetSurfaceArea(const KdNode *node) const {
        return GetBox(node).SurfaceArea();
  }

  
  KdNode *
  FindRandomNeighbor(KdNode *n,
                                         bool onlyUnmailed
                                         );
  
  KdNode *
  KdTree::GetRandomLeaf(const Plane3 &halfspace);

  KdNode *
  GetRandomLeaf(const bool onlyUnmailed = false);


  KdNode *
  GetNode(const Vector3 &point, const float maxArea) const;

  int
  FindNeighbors(KdNode *n,
                                vector<KdNode *> &neighbors,
                                bool onlyUnmailed
                                );

  int
  CollectLeafPvs();

  bool ExportBinTree(const string &filename);
  bool LoadBinTree(const string &filename, ObjectContainer &object);

protected:

  struct RayData {
    // pointer to the actual ray
    Ray *ray;
    
    // endpoints  - do we need them?
#if USE_FIXEDPOINT_T
    short tmin, tmax;
#else
    float tmin, tmax;
#endif

    RayData():ray(NULL) {}
    RayData(Ray *r):ray(r), tmin(0),

#if USE_FIXEDPOINT_T
#define FIXEDPOINT_ONE 0x7FFE
                          //                      tmax(0xFFFF)
                          tmax(FIXEDPOINT_ONE)
#else
      tmax(1.0f)
#endif
    {}

    RayData(Ray *r,
            const float _min,
            const float _max
            ):ray(r) {
      SetTMin(_min);
      SetTMax(_max);
    }

    RayData(Ray *r,
            const short _min,
            const float _max
            ):ray(r), tmin(_min) {
      SetTMax(_max);
    }

    RayData(Ray *r,
            const float _min,
            const short _max
            ):ray(r), tmax(_max) {
      SetTMin(_min);
    }

    friend bool operator<(const RayData &a, const RayData &b) {
      return a.ray < b.ray;
    }
    
    
    float ExtrapOrigin(const int axis) const {
      return ray->GetLoc(axis) + GetTMin()*ray->GetDir(axis);
    }
    
    float ExtrapTermination(const int axis) const {
      return ray->GetLoc(axis) + GetTMax()*ray->GetDir(axis);
    }
    
#if USE_FIXEDPOINT_T
    float GetTMin () const { return tmin/(float)(FIXEDPOINT_ONE); }
    float GetTMax () const { return tmax/(float)(FIXEDPOINT_ONE); }

    void SetTMin (const float t) {
      tmin = (short) (t*(float)(FIXEDPOINT_ONE));
    }
    
    void SetTMax (const float t) {
      tmax = (short) (t*(float)(FIXEDPOINT_ONE));
      tmax++;
      //      if (tmax!=0xFFFF)
      //        tmax++;
    }
#else
    float GetTMin () const { return tmin; }
    float GetTMax () const { return tmax; }

    void SetTMin (const float t) { tmin = t; }
    void SetTMax (const float t) { tmax = t; }
#endif 
  };

  struct RayTraversalData {
    KdNode *mNode;
    Vector3 mExitPoint;
    float mMaxT;
    
    RayTraversalData() {}
    RayTraversalData(KdNode *n,
                     const Vector3 &p,
                     const float maxt):
      mNode(n), mExitPoint(p), mMaxT(maxt) {}
  };

  // --------------------------------------------------------------
  // For sorting objects
  // --------------------------------------------------------------
  struct  SortableEntry
  {
    enum {
      BOX_MIN,
      BOX_MAX
    };
    
    int type;
    float value;
    Intersectable *intersectable;
    
    SortableEntry() {}
    SortableEntry(const int t, const float v, Intersectable *i):type(t),
                                                                value(v),
                                                                intersectable(i) {}
    
    bool operator<(const SortableEntry &b) const {
      return value < b.value;
    }
    
  };
  
  // reusable array of split candidates
  vector<SortableEntry> *splitCandidates;

  float
  BestCostRatio(
                KdLeaf *node,
                const AxisAlignedBox3 &box,
                const int axis,
                float &position,
                int &objectsBack,
                int &objectsFront
                );

  void
  SortSubdivisionCandidates(
                      KdLeaf *node,
                      const int axis
                      );

  void
  EvaluateLeafStats(const TraversalData &data);

  KdNode *
  SubdivideNode(
                KdLeaf *leaf,
                const AxisAlignedBox3 &box,
                AxisAlignedBox3 &backBBox,
                AxisAlignedBox3 &frontBBox
                );

  bool
  TerminationCriteriaMet(const KdLeaf *leaf);
  
  int
  SelectPlane(KdLeaf *leaf,
              const AxisAlignedBox3 &box,
              float &position
              );

        /** does some post processing on the objects in the new child leaves.
        */
        void ProcessMultipleRefs(KdLeaf *leaf) const;

        void ExportBinLeaf(OUT_STREAM  &stream, KdLeaf *leaf);
        void ExportBinInterior(OUT_STREAM &stream, KdInterior *interior);
        KdLeaf *ImportBinLeaf(IN_STREAM &stream, KdInterior *parent, const ObjectContainer &objects);
        KdInterior *ImportBinInterior(IN_STREAM  &stream, KdInterior *parent);
        KdNode *LoadNextNode(IN_STREAM  &stream, KdInterior *parent, const ObjectContainer &objects);
        
        /** Adds this objects to the kd leaf objects.
                @warning: Can corrupt the tree
        */
        void InsertObjects(KdNode *node, const ObjectContainer &objects);

  int mTermMaxNodes;
  float mSplitBorder;
  int mTermMaxDepth;
  int mTermMinCost;
  float mMaxCostRatio;
  float mCt_div_ci;
  int mSplitMethod;
  bool mSahUseFaces;
  /// root of the tree
  KdNode *mRoot;
  /// bounding box of the tree root
  AxisAlignedBox3 mBox;
  KdTreeStatistics mStat;
public:
  /// stores the kd node intersectables used for pvs
  vector<KdIntersectable *> mKdIntersectables;
  
};


}

#endif