source: GTP/trunk/Lib/Vis/Preprocessing/src/TraversalTree.h @ 2176

#ifndef _TraversalTree_H__
#define _TraversalTree_H__

#include <functional>
//

#include "Containers.h"
#include "AxisAlignedBox3.h"
#include "Ray.h"


namespace GtpVisibilityPreprocessor {

  
class TraversalNode;
class TraversalLeaf;
class TraversalInterior;
class Intersectable;
class Beam;

class TraversalTree;
  

// --------------------------------------------------------------
// Static statistics for kd-tree search
// --------------------------------------------------------------
class TraversalTreeStatistics 
{
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;
  // max number of rays per node
  int totalObjectRefs;
  // number of dynamically added ray refs
  int addedRayRefs;
  // number of dynamically removed ray refs
  int removedRayRefs;
  // number of nodes terminated on cost ratio
  int costRatioNodes;

  // Constructor
  TraversalTreeStatistics() 
  {
          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;
          totalObjectRefs = 0;
          addedRayRefs = removedRayRefs = 0;
          costRatioNodes = 0;
  }

  void Print(std::ostream &app) const;

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

  
class TraversalInterior;

/** Abstract class for kd-tree node 
*/
class TraversalNode 
{
public:

        virtual ~TraversalNode(){};
        
        TraversalNode(TraversalInterior *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 
        */
        TraversalInterior *mParent;


        /////////////////// 
        // mailing stuff

public:

        void Mail() 
        { 
                mMailbox = 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; 
        }

        int mMailbox;

        static int sMailId;
        static int sReservedMailboxes;
};


/** Implementation of the kd-tree interior node 
*/
class TraversalInterior : public TraversalNode 
{
public:

        TraversalInterior(TraversalInterior *parent);
        ~TraversalInterior();

        /** \sa TraversalNode::IsLeaf() 
        */
        bool IsLeaf() const;

        void SetupChildLinks(TraversalNode *b, TraversalNode *f);

        void ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild);


        //////////////////////////

        /// 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 
        TraversalNode *mBack;
        /// front node
        TraversalNode *mFront;  
};

  
/** Implementation of the kd-tree leaf node 
*/
class TraversalLeaf : public TraversalNode 
{
public:

        TraversalLeaf(TraversalInterior *parent, const int objects);

        ~TraversalLeaf();

        /** \sa TraversalNode::IsLeaf() 
        */
        virtual bool IsLeaf() const;

        /////////////////////////////////

        // pointers to view cells contained in this node
        ViewCellContainer mViewCells;

        short mDepth;
};


/** TraversalTree for indexing scene entities - occluders/occludees/viewcells 
*/
class TraversalTree 
{

protected:

        struct TraversalData
        {  
                TraversalNode *mNode;
                AxisAlignedBox3 mBox;
                int mDepth;
                float mPriority;

                TraversalData(): mNode(NULL), mPriority(0), mDepth(0) {}

                TraversalData(TraversalNode *n, const float p):
                mNode(n), mPriority(p), mDepth(0)
                {}

                TraversalData(TraversalNode *n,
                                          const AxisAlignedBox3 &b,
                                          const int d):
                mNode(n), mBox(b), mDepth(d) 
                {}


                bool operator<(const TraversalData &b) const 
                {
                        TraversalLeaf *leafa = (TraversalLeaf *) mNode;
                        TraversalLeaf *leafb = (TraversalLeaf *) b.mNode;
                        
                        return 
                                leafa->mViewCells.size() * mBox.SurfaceArea()
                                <
                                leafb->mViewCells.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};

        TraversalTree();

        ~TraversalTree();


        /** Casts line segment into tree.
                @returns intersected view cells.
        */
        int CastLineSegment(const Vector3 &origin,
                                                const Vector3 &termination,
                                                ViewCellContainer &viewcells,
                                                const bool useMailboxing);

        virtual bool Construct(const ViewCellContainer &viewCells);

        /** 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 TraversalNode *Subdivide(const TraversalData &tdata);

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

        AxisAlignedBox3 GetBox() const 
        { 
                return mBox; 
        }

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

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

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

        void CollectLeaves(vector<TraversalLeaf *> &leaves);

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

        AxisAlignedBox3 GetBox(const TraversalNode *node) const;


protected:

        /** Struct for traversing line segment.
        */
        struct LineTraversalData 
        {               
                LineTraversalData () {}
                LineTraversalData (TraversalNode *n, const Vector3 &p, const float maxt):
                mNode(n), mExitPoint(p), mMaxT(maxt) {}

                TraversalNode *mNode;
                Vector3 mExitPoint;
                float mMaxT;
        };

        // --------------------------------------------------------------
        // 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 
                {
                        // view cells usually adjacent 
                        if (EpsilonEqual(value, b.value, 0.001))
                                return (type == BOX_MAX);
                        
                        return value < b.value;
                }*/
        };

        inline static bool iltS(SortableEntry *a, SortableEntry *b)
        {
                // view cells usually adjacent 
                //if (EpsilonEqual(a->value, b->value))
                //      return false;
                //      return (a->type == SortableEntry::BOX_MAX);
                        
                return a->value < b->value;
        }

        // reusable array of split candidates
        vector<SortableEntry *> *splitCandidates;

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

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

        void EvaluateLeafStats(const TraversalData &data);

        TraversalNode *SubdivideNode(TraversalLeaf *leaf,
                                                                 const AxisAlignedBox3 &box,
                                                                 AxisAlignedBox3 &backBBox,
                                                                 AxisAlignedBox3 &frontBBox
                                                                 );

        bool TerminationCriteriaMet(const TraversalLeaf *leaf);

        int SelectPlane(TraversalLeaf *leaf,
                                        const AxisAlignedBox3 &box,
                                        float &position);

        int FindViewCellIntersections(const Vector3 &lStart, 
                                                                  const Vector3 &lEnd,
                                                                  const ViewCellContainer &viewCells,
                                                                  ViewCellContainer &hitViewCells,
                                                                  const bool useMailboxing);

        ////////////////////////

        int mTermMaxNodes;
        float mSplitBorder;
        int mTermMaxDepth;
        int mTermMinCost;
        float mMaxCostRatio;
        float mCt_div_ci;
        int mSplitMethod;
        bool mSahUseFaces;

        /// root of the tree
        TraversalNode *mRoot;
        /// bounding box of the tree root
        AxisAlignedBox3 mBox;
        TraversalTreeStatistics mStat;

};


}

#endif