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

#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"

namespace GtpVisibilityPreprocessor {

  
  class KdNode;
  class KdLeaf;
  class KdInterior;
  class Intersectable;
  //class KdViewCell;
  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 mailID;
  int mailbox;
  
  void Mail() { mailbox = mailID; }
  static void NewMail() { mailID++; }
  bool Mailed() const { return mailbox == mailID; }

  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;
  int mDepth;
};

/** 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 SplitCandidate;
  
/** 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;

  /** Objects that are part of several leaves.
  */
  ObjectContainer mMultipleObjects;

  /// universal counter
  int mCounter;
        
  /** 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.
  // ViewCellPvs mViewCellPvs;
  SplitCandidate *mSplitCandidate;

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

  

/** 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;
  }

  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;
  }
        
  KdNode *
  FindRandomNeighbor(KdNode *n,
                                         bool onlyUnmailed
                                         );
  
  KdNode *
  KdTree::GetRandomLeaf(const Plane3 &halfspace);

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

  int
  CollectLeafPvs();

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
  SortSplitCandidates(
                      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
              );


  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;
  
};
  



}

#endif