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

#ifndef _KdTree_H__
#define _KdTree_H__

#include <functional>
//

#include "Containers.h"
#include "AxisAlignedBox3.h"
#include "Ray.h"
//#include "ObjectPvs.h"
#include "ViewCell.h"
#include "VssRay.h"
//#include "IntersectableWrapper.h"
#include "gzstream.h"

namespace GtpVisibilityPreprocessor {

class KdNode;
class KdLeaf;
class KdInterior;
class Intersectable;
class KdIntersectable;
class Beam;
class KdTree;
//class KdViewCell;
  
  //  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(std::ostream &app) const;

  friend std::ostream &operator<<(std::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;

  static int sMailId2;
  static int sReservedMailboxes2;
  int mMailbox2;

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


  ////////////
  //-- hack!!: second mail for a machine with 2 cores

  static void NewMail2(const int reserve = 1) 
  {
          sMailId2 += sReservedMailboxes;
          sReservedMailboxes2 = reserve;
  }

  void Mail2() { mMailbox2 = sMailId2; }
  bool Mailed2() const { return mMailbox2 == sMailId2; }
 
  void Mail2(const int mailbox) { mMailbox2 = sMailId2 + mailbox; }
  bool Mailed2(const int mailbox) const { return mMailbox2 == sMailId2 + 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;
  int mNumObjects;
};


/** 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), mVboId(-1),
          mIndexBufferStart(0), mIndexBufferSize(0) {
    mObjects.reserve(objects);
  }
  
  void AddPassingRay(const Ray &ray, const int contributions) {
    mPassingRays.AddRay(ray, contributions);
                //              Debug << "adding passing ray" << endl;
  }

  ~KdLeaf();
        
  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;
  /// pointer to view cell.
  KdViewCell *mViewCell;
  /// rays intersecting this leaf
  VssRayContainer mVssRays;
   /// Objects that are referenced in more than one leaf.
  ObjectContainer mMultipleObjects;
  /// universal counter
  int mCounter;

  /// hack
  unsigned int mVboId;

  unsigned int mIndexBufferStart;
  unsigned int mIndexBufferSize;
};


/** 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
    std::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);

  // old version
  int CastLineSegment2(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.
  */
  KdIntersectable *GetOrCreateKdIntersectable(KdNode *node);


  void
  SetPvsTerminationNodes(const float maxArea);

  float
  GetPvsArea() const;
  
  KdNode *
  GetPvsNode(const Vector3 &point) const;
  
 KdNode *
  GetPvsNodeCheck(const Vector3 &point, Intersectable *obj) const;

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

  /** colect objects which are in the bounding box by explictly specifying the
      allowed size of the boxes. If this size is smaller than size used for pvs entries
          filtering will be more precise.
  */
  void
  CollectSmallKdObjects(const AxisAlignedBox3 &box,
                                                ObjectContainer &objects,
                                                const float maxArea
                                                );

  /** warning - uses mailing.
  */
  void CollectObjects(KdNode *n, ObjectContainer &objects);
  /** Sets the number of objects under the current subtree for each node.
          warning - uses mailing.
  */
  void SetNumObjects(KdNode *root);
  /** Returns the number of objects under the curretn subtree.
  */
  int GetNumObjects(KdNode *node) const;
  /** Collects objects with dublicates (no mailing going on)
  */
  void CollectObjectsWithDublicates(KdNode *n, ObjectContainer &objects) const;
  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 *
  GetRandomLeaf(const Plane3 &halfspace);

  KdNode *
  GetRandomLeaf(const bool onlyUnmailed = false);


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

  void GetBoxIntersections(const AxisAlignedBox3 &box, 
                           vector<KdLeaf *> &leaves);

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

  bool ExportBinTree(const std::string &filename);
  /** loads kd tree from disk. note: sorts objects by id
  */
  bool ImportBinTree(const std::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;
    }
    
  };

  inline static bool iltS(SortableEntry *a, SortableEntry *b)
  {
          return a->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;


  //////////
  // binary import / export
  
  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 *ImportNextNode(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;
  float mKdPvsArea;
  /// 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