source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktb8b.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 __KTB8B_H__
#define __KTB8B_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 "Ray.h"

// standard headers
#include <vector>


namespace GtpVisibilityPreprocessor {

// Forward declarations

// Use 8 Bytes representation
#undef  SKTBNodeT
#define SKTBNodeT CKTB8BNodeAbstract::SKTBNode

//===============================================
// Representation of one node of CKTB
class CKTB8BNodeAbstract
{
public:
  // maximal height of the CKTB tree
  enum { MAX_HEIGHT = 32, MaskForOffset = 0xFFFFFFF8 };

  // 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 {
    // SKTBNode *left; // pointer to the left child is implict in DFS order
    union {
      // here is the compressed version of the axis
      unsigned char *pointer;
      unsigned int offset;
      int depth;
    };
    union {
      float splitPlane; // the position of splitting plane
      ObjectContainer *objlist; // object list for a leaf or tagged interior node
      Intersectable *object; // the pointer to the object, if only one object
      SBBox     *encbox; // enclosing bounding box for this node
      SBBox     *minbox; // minimum bounding box for this node
      SKTBNodeT *linkedNode; // the linked node
      SKTBNodeT *parentBoxNode; // the pointer to the same node type
    };

    bool IsLeaf() const {
      return ( CKTBAxes::Axes(offset & CKTBAxes::EE_Mask) == CKTBAxes::EE_Leaf);
    }
    bool IsEmptyLeaf() const {
      return (this == 0);
    }
  }; // struct SKTBNode

public:

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

  bool IsEmptyLeaf_(const SKTBNodeT *p) const {
    assert(( CKTBAxes::Axes(p->offset & CKTBAxes::EE_Mask) == CKTBAxes::EE_Leaf));
    return (p->objlist == NULL);
  }

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

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

  float GetSplitValue(const SKTBNodeT *nodep) const {
    return nodep->splitPlane;
  }
  
  CKTBAxes::Axes GetNodeType(const SKTBNodeT *nodep) const {
    return (CKTBAxes::Axes)(nodep->offset & 0x7);
  }
  SKTBNodeT* GetLeft(const SKTBNode *nodep) const {
    return (SKTBNodeT*)(nodep+1); // We assume linking in DFS order
  }
  SKTBNodeT* GetRight(const SKTBNodeT *nodep) const {
    // We assume 8-Bytes aligned nodes in memory in 32-Bits environment
    // This has to be checked during node linking.
    return (SKTBNodeT*)(nodep->offset & MaskForOffset);
  }

  SKTBNodeT* GetLinkNode(const SKTBNodeT *nodep) const {
    // We assume 8-Bytes aligned nodes in memory in 32-Bits environment
    // This has to be checked during node linking.
    return (SKTBNodeT*)(nodep->linkedNode);
  }
  // We assume linking in DFS order, this is for EncBox
  SKTBNodeT* GetLeftLong(const SKTBNodeT *nodep) const {
    return (SKTBNodeT*)(((char*)nodep) + 4*sizeof(SKTBNode)); 
  }
  SKTBNode* GetParentBoxNode(const SKTBNode *nodep) const {
    return (SKTBNode*)(nodep+1)->parentBoxNode;
  }
  
#ifdef _SHORT_FORM_MINBOX
  SKTBNode* GetLeftMinBox(const SKTBNode *nodep) const {
    return (SKTBNode*)(nodep+2);
  }
  int GetDepth(const SKTBNode * /*nodep*/) const {
    return 0; // depth was not stored
  }
#else
  SKTBNode* GetLeftMinBox(const SKTBNode *nodep) const {
    return (SKTBNode*)(((char*)nodep) + 5*sizeof(SKTBNode)); 
  }  
  int GetDepth(const SKTBNode *nodep) const {
    return (int)((nodep+1)->depth);
  }
#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 CKTB8BAllocMan:
  public CKTB8BNodeAbstract
{
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
  SKTBNodeT* _AllocEmptyLeaf() {
#ifdef _KTB_CONSTR_STATS
    _stats_emptyLeftNodeCount++;
#endif
    return (SKTBNodeT*)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
  CKTB8BAllocMan() { InitForConstructor(); }

  // default destructor
  ~CKTB8BAllocMan() { }

  // init the stack of auxiliary variables from min to max
  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
  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);

  ObjectContainer* GetObjList(const SKTBNodeT *nodep) const {
    return nodep->objlist;
  }

  // -------------------------------------------------------
  // 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 !!
  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
  SKTBNodeT* 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
  
  // 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 CKTB8BNodeIterator:
  public CKTB8BNodeAbstract
{
protected:
  int rayOffset;  
public:
  // default constructor
  CKTB8BNodeIterator();
  // default destructor
  ~CKTB8BNodeIterator() { }

  float GetSplitValue(const SKTBNodeT *nodep) const {
    return nodep->splitPlane;
  }
    
  ObjectContainer* GetObjList(const SKTBNodeT *nodep) const {
    return nodep->objlist;
  }
  SBBox* GetEncBox(const SKTBNodeT *nodep) const {
    // Here is the overlapping to save some memory !!! 
    return (SBBox*)(((char*)nodep)+8);
  }

#ifdef _SHORT_FORM_MINBOX
  SBBox* GetMinBox(const SKTBNodeT *nodep) const {
    return (SBBox*)((nodep+1)->pointer);
  }  
#else // _SHORT_FORM_MINBOX
  SBBox* GetMinBox(const SKTBNodeT *nodep) const {
    // Here is the overlapping to save some memory !!! 
    return (SBBox*)(((char*)nodep)+16);
  }
#endif // _SHORT_FORM_MINBOX
  
  // 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 SKTBNodeT *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 SKTBNodeT *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 a leaf or the minimum box containg a point.
  virtual const SKTBNode* Locate(const Vector3& /*position*/);
}; // class CKTBNodeIterator

}

#endif // __KTB8B_H__