source: GTP/trunk/Lib/Vis/Preprocessing/include/KdTree.h @ 68

#ifndef _KdTree_H__
#define _KdTree_H__

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

namespace GtpVisibilityPreprocessor {
  
  class KdNode;
  /** KdTree for indexing scene entities - occluders/occludees/viewcells */
  class KdTree {
  public:

    /** Insert occluder into the tree */
    virtual void InsertOccluder(Mesh *occluder) {
      //      mRoot->mOccluders.push_back(occluder);
    }

    /** Insert occludee into the tree */
    virtual void InsertOccludee(Mesh *occludee) {
      //      mRoot->mOccludees.push_back(occludee);
    }
    
    /** Insert view cell into the tree */
    virtual void InsertViewCell(ViewCell *viewCell) {
      //      mRoot->mViewcells.push_back(viewCell);
    }
    
    /** 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 bool Subdivide(KdNode *subtree);

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

  protected:
    /// root of the tree
    KdNode *mRoot;
    /// bounding box of the tree root
    AxisAlignedBox3 mBox;
  };
  
  
  class KdInterior;
  /** Abstract class for kd-tree node */
  class KdNode {

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

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

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

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

  protected:
    /** splitting axis */
    int axis;
    /** splitting position, absolute position within the bounding box of this node */
    float mPosition;

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

  };
  
  
  /** Implementation of the kd-tree leaf node */
  class KdLeaf : public KdNode {
  public:
    /** \sa KdNode::IsLeaf() */
    virtual bool IsLeaf() const { return true; }

  protected:
    /** pointers to occluders contained in this node */
    MeshContainer mOccluders;
    /** pointers to occludees contained in this node */
    MeshContainer mOccludees;
    /** pointers to viewcells contained in this node */
    ViewCellContainer mViewCells;
  };
  
  
  
};




#endif