source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktb.h @ 2592

// ===================================================================
// $Id: $
//
// ktb.h
//      definition of classes for CKTB tree building up and traversal
//
// Class: CKTBNodeAbstract, SKTBNode, CKTBAllocMan, CKTBNodeIterator
//
// REPLACEMENT_STRING
//
// Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
// Initial coding by Vlasta Havran, February 2007

#ifndef __KTB_H__
#define __KTB_H__

// GOLEM headers
#include "configh.h"
#include "AxisAlignedBox3.h"
#include "Intersectable.h"
#include "Containers.h"
#include "allocgo2.h"
#include "ktbconf.h"
#include "sbbox.h"
#include "Vector3.h"

// standard headers
#include <vector>

namespace GtpVisibilityPreprocessor {

// Forward declarations
class CRayPacket2x2;

// 12 Bytes representation of the node
// This is only due to writing simplification
#undef SKTBNodeT
#define SKTBNodeT CKTBNodeAbstract::SKTBNode

//===============================================
// Representation of one node of CKTB
class CKTBNodeAbstract
{
public:
  // maximal height of the CKTB tree
  enum { MAX_HEIGHT = 32 };

  // the basic element of CKTB tree .. node of tree
  // it must be accessible by more classes

  // but must be declared because of compilation
  struct SKTBNode {
    // the axis, where cut is performed or type of node in general
    CKTBAxes::Axes  nodeType;

    union {
      float splitPlane; // the position of splitting plane
      ObjectContainer *objlist; // object list for a leaf or tagged interior node
      SKTBNodeT *parentBoxNode; // the pointer to the same node type
      int        depth; // the depth of the node (useful only for minBoxes)
    };
    
    // SKTBNode *left; // pointer to the left child is implict in DFS order
    union {
      Intersectable *object; // the pointer to the object, if only one object
      SKTBNodeT  *right; // pointer to the right child
      SBBox     *encbox; // enclosing bounding box for this node
      SBBox     *minbox; // minimum bounding box for this node
    };

    bool IsLeaf() const {
      return ( nodeType == CKTBAxes::EE_Leaf);
    }
    bool IsEmptyLeaf() const {
      return (this == 0);
    }
  }; // struct SKTBNode

public:

  // It was _KTB_R2
  // default constructor
  CKTBNodeAbstract() { }
  // default destructor
  virtual ~CKTBNodeAbstract() { }

  bool IsEmptyLeaf_(const SKTBNode *p) const {
    assert(p->nodeType == CKTBAxes::EE_Leaf);
    return (p->objlist == NULL);
  }

  bool IsFullLeaf_(const SKTBNode *p) const {
    return ((p->nodeType == CKTBAxes::EE_Leaf) &&
            (p->objlist != NULL));
  }
  
  bool IsLeaf_(const SKTBNode *p) const
  { return (p->nodeType == CKTBAxes::EE_Leaf); }
  
  bool HasMinBox_(const SKTBNode *p) const
  { return ( p->nodeType >= CKTBAxes::EE_X_axisBox); }

  // ------------------------------------------------------
  // Common functions for iterator and allocator

  CKTBAxes::Axes GetNodeType(const SKTBNode *nodep) const {
    return nodep->nodeType;
  }
  SKTBNode* GetLeft(const SKTBNode *nodep) const {
    return (SKTBNode*)(nodep+1); // We assume linking in DFS order
  }
  // We assume linking in DFS order, this is for EncBox
  SKTBNode* GetLeftLong(const SKTBNode *nodep) const {
    return (SKTBNode*)(((char*)nodep) + 3*sizeof(SKTBNode)); 
  }
  SKTBNode* GetRight(const SKTBNode *nodep) const {
    return nodep->right;
  }
  SKTBNodeT* GetLinkNode(const SKTBNodeT *nodep) const {
    return nodep->right;
  }  
  ObjectContainer* GetObjList(const SKTBNode *nodep) const {
    return nodep->objlist;
  }

  SKTBNode* GetParentBoxNode(const SKTBNode *nodep) const {
    return (SKTBNode*)(nodep+1)->parentBoxNode;
  }

  // This can be used only for nodes X_AxisBox, Y_AxisBox, Z_AxisBox
  int GetDepth(const SKTBNode *nodep) const {
    return (int)((nodep+1)->nodeType);
  }
#ifdef _SHORT_FORM_MINBOX
  SKTBNode* GetLeftMinBox(const SKTBNode *nodep) const {
    return (SKTBNode*)(nodep+2);
  }
#else
  SKTBNode* GetLeftMinBox(const SKTBNode *nodep) const {
    return (SKTBNode*)(((char*)nodep) + 4*sizeof(SKTBNode)); 
  }  
#endif // _SHORT_FORM_MINBOX

}; // CKTBNodeAbstract

//----------------------------------------------------------------
// this class should be used as the base class for allocating
// and connecting the nodes in the CKTB tree and for
// for manipulating the nodes during building up
class CKTBAllocMan:
  public CKTBNodeAbstract
{
protected:
#ifdef LEAVES_ARRAYS
  CObjectArray arrayAlloc;
#endif
  
  // the direction of traversal through CKTB tree
  enum EDirection { LEFT = 0, RIGHT = 1, NOWHERE = 2 };

//#ifdef _KTB_R2
  SKTBNode* _AllocEmptyLeaf() {
#ifdef _KTB_CONSTR_STATS
    _stats_emptyLeftNodeCount++;
#endif
    return (SKTBNode*)0;
  }
protected:
  // data required as the input parameter for construction of CKTB tree
  int maxDepthAllowed; // maximal depth of CKTB tree
  int maxListLength; // maximal list length of CKTB tree  
public:
  // default constructor
  CKTBAllocMan() { InitForConstructor(); }

  // default destructor
  virtual ~CKTBAllocMan() { }

  // init the stack of auxiliary variables from min to max
  virtual void InitAux(int min, int max, int maxItemsAtOnce);
  
  // forget the content that is created by previous kd-tree construction
  // or just init for the first use.
  void InitForConstructor();
  
  // the function, which reads the parameters from envinroment/commandline
  virtual void InitPars();
  
  // -------------------------------------------------------
  // allocate and free functions for SKTBNode
  CAllocContinuous *alloc2; // the allocator saving space
  SKTBNodeT *root; // this is the root node of the whole tree
  
  // This is the node to return from the allocation functions
  // Here it can be implemented some linking when DFS order allocation,
  // so the node can be different than the representation of the real
  // node with the information
  SKTBNodeT *nodeToLink;

  // Create the representation of the interior node
  SKTBNodeT* AllocInteriorNode(int axis, float position,
                               int cntLeft, int cntRight);

  // Create the representation of the interior node with box, where box
  // can be used during the traversal
  SKTBNodeT* AllocInteriorNodeWithBox(int axis, float position,
                                      int cntLeft, int cntRight,
                                      const SBBox &tsbox,
                                      SKTBNodeT* prevMinBoxNode,
                                      int depthStore);
  
  // Create the representation of the node with the bounding box
  SKTBNodeT* AllocEncBoxNode(const SBBox &sbox);
  
  // Create the representation of the leaf. Note that possibly there
  // can be special cases, such as 0, 1, 2, or 3 objects, or in general
  // N objects.
  SKTBNodeT* AllocLeaf(int cntObjects);
  
  // -------------------------------------------------------
  // linking and setting functions for CKTB tree

  // Set the pointers to children for the interior node
  void SetInteriorNodeLinks(SKTBNodeT *node,
                            SKTBNodeT *leftChild,
                            SKTBNodeT *rightChild);
  void SetInteriorNodeLeft(SKTBNodeT *node,
                           SKTBNodeT *leftChild);
  void SetInteriorNodeRight(SKTBNodeT *node,
                            SKTBNodeT *rightChild);

  // Set the objects list to the leaf. The object list is used as it is
  // ... it is not copied !!
  virtual int SetFullLeaf(SKTBNodeT *node, const ObjectContainer *objlist);

  // -------------------------------------------------------
  // inquiry functions for CKTB tree nodes for current node

  // returns the pointer to the root node of tree
  virtual SKTBNode *GetRootNode() { return root;}

  // postprocessing of CKTB tree after its initial construction
  virtual void PostBuild();

  // provides the information on the method used for CKTB tree
  // and some setting parameters to given stream
  virtual void ProvideID(ostream &app) = 0;
  
  // ---- Get Statistical Data ---------------------------------
  void GetKTBTreeStats(int &nodes, int &leaves, int &emptyLeaves)
  {
#ifdef _KTB_CONSTR_STATS
    nodes = _stats_interiorCount + _stats_bboxCount + _stats_minbboxCount
      + _stats_leafNodeCount + _stats_emptyLeftNodeCount;
    leaves = _stats_leafNodeCount + _stats_emptyLeftNodeCount;
    emptyLeaves = _stats_emptyLeftNodeCount;
#endif
  }

  // constructs the CKTB tree for given objectlist and given bounding box
  virtual SKTBNodeT* BuildUp(ObjectContainer &objlist,
                             const AxisAlignedBox3 &box,
                             bool verbose = true) = 0;

  // deletes all the structure starting from the root node
  virtual void Remove();

  // The current depth in the tree
  inline int GetDepth() const {return _currDepth;}
  void IncDepth() {_currDepth++;}
  void DecDepth() {_currDepth--;}
  
  // --------------------------------------------------------------
  // Statistics
public:
#ifdef _KTB_CONSTR_STATS
  int _stats_interiorCount;
  int _stats_bboxCount;
  int _stats_minbboxCount;
  int _stats_leafNodeCount;
  int _stats_emptyLeftNodeCount;

  // maximal depth of the currently built path during building up
  int _maxDepth;  
  // Sum of depths of leaf nodes (empty + full)
  unsigned long int _sumLeafDepth;
  // Sum of depths of empty leaves
  unsigned long int _sumFullLeafDepth;
  // The count of object references in leaves
  unsigned long int _sumObjectRefCount;
  // The maximum number of object references in a leaf
  unsigned long int _maxObjectRefInLeaf;
  // Surface area of leaves and interior nodes
  float _sumSurfaceAreaLeaves;
  float _sumSurfaceAreaMULcntLeaves;
  float _sumSurfaceAreaInteriorNodes;
#endif // _KTB_CONSTR_STATS

  // General statistics on the depth of current node
  // the depth of the currently accessed node during building up
  int _currDepth;
};

//------------------------------------------------------
// class which enables to use some functions with direct
// access to the members of the tree
// traversal classes should be derived from this class
class CKTBNodeIterator:
  public CKTBNodeAbstract
{
protected:
  int rayOffset;  
public:
  // default constructor
  CKTBNodeIterator() { }
  // default destructor
  ~CKTBNodeIterator() { }

  ObjectContainer* GetObjList(const SKTBNode *nodep) const {
    return nodep->objlist;
  }
  
  float GetSplitValue(const SKTBNode *nodep) const {
    return nodep->splitPlane;
  }
    
#ifdef _SHORT_FORM_MINBOX
  SBBox* GetMinBox(const SKTBNodeT *nodep) const {
    return (nodep+1)->minbox;
  }  
#else // _SHORT_FORM_MINBOX
  SBBox* GetMinBox(const SKTBNodeT *nodep) const {
    // Here is the overlapping to save some memory !!! 
    return (SBBox*)(((char*)nodep)+24);
  }  
#endif // _SHORT_FORM_MINBOX
  
  ObjectContainer* GetTagObjList(const SKTBNode *node) const {
    return node->objlist;
  }

  // test the objects in the full leaf p and if finds the closest intersection
  // with object so tmin<= t <= tmax, returns the pointer to that
  // object, t is returned in tmax
  int TestFullLeaf(const SimpleRay &ray, const SKTBNode *p);
  int TestFullLeaf(const SimpleRay &ray, const SKTBNode *p, int rayIndex);

  // test the objects in the full leaf and finds out any intersection
  // in this case returns the pointer to the object, otherwise NULL
  int HitAnyObj(const SimpleRay &ray, const SKTBNode *p);

  // ------------------------------------------------------------------------
  // Only abstract functions to simplify the interface

  // this resets the nesting to start from the zero depth (root)
  virtual void ResetTraversalDepth() = 0;

  // sets the bbox and the root node for this traversal class
  virtual void Setup(const AxisAlignedBox3 &box, SKTBNodeT *Nroot) = 0;

  // Find the minimum box on containg a point or leaf, if there are
  // no boxes on the way from a point to the leaf containing the point
  virtual const SKTBNode* Locate(const Vector3 &point);
}; // class CKTBNodeIterator

}

#endif // __KTB_H__