source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktbs.h @ 2632

// ============================================================================
// $Id: $
//
// ktbai.h
//     classes for building up the different KD-trees
//
// Class: CKTBBuildUp, CKTBBuildUp_new
//
// REPLACEMENT_STRING
//
// Initial coding by Vlasta Havran, January 2008

#ifndef __KTBS_H__
#define __KTBS_H__

// GOLEM headers
#include "configh.h"
#include "ktbconf.h"
#include "ktb.h"
#include "ktb8b.h"
#include "ktbai.h"
#include "Containers.h"
#include "IntersectableWrapper.h"

namespace GtpVisibilityPreprocessor {

// forward declarations
class SKTBNode;

#ifndef _KTB8Bytes
// Use 12 Bytes representation
#define CKTBAllocManPredecessor CKTBAllocMan
#undef  SKTBNodeT
#define SKTBNodeT CKTBNodeAbstract::SKTBNode
#else
// Use 8 Bytes representation per node
#define CKTBAllocManPredecessor CKTB8BAllocMan
#undef  SKTBNodeT
#define SKTBNodeT CKTB8BNodeAbstract::SKTBNode
#endif

#ifndef INFINITY
#define INFINITY 10e10
#endif

// ---------------------------------------------------------------  
// The base class for KD-tree with irregular change of axes, where
// the splitting plane can be positioned.
class CKTBSBuildUp:
  public CKTBAllocManPredecessor
{
protected:
  struct SSplitState
  {
    // counts
    int   cntAll;       // the number of all objects in the bounding box
    int   cntLeft;      // the count of bounding boxes on the left
    int   cntRight;     // the count of bounding boxes on the right
    int   thickness;    // the count of bounding boxes straddling the splitting plane

    // The buckets
    int   bucketN; // the number of buckets
    int   *bucketMin; // the buckets for left (minimum) boundaries
    int   *bucketMax; // the buckets for right (max) boundaries

    CKTBAxes::Axes  axis;  // the axis, where the splitting is proposed
    float sizeb[3];     // the size of the box for x, y, and z
    SBBox box;          // the box, that is subdivided

    // derived values from basic ones
    float width;        // the size of bounding box along the axis
    float frontw;       // the size of the bounding box in another axis (depth)
    float topw;         // the size of the bounding box in next next axis (height)
    float areaSplitPlane; // the area of the splitting plane
    float areaSumLength; // the size of the bounding as sum of height and depth
    float areaWholeSA2; // the half of the surface area of the whole box for this node

    // The position for this splitting plane to be evaluated
    float position; // the distance from the left boundary of the box for this node
    // The position for the next position, makes sense only for free interval (thickness=0)
    float position2; // the distance from the left boundary of the box for this node
    
    // The evaluation best cost until now
    float bestCost;
    // The position to be used
    float bestPosition;
    // The second best position - NOT USED AT THE MOMENT FOR SAMPLING !!!
    float bestPosition2;
    // Which mechanism to be used for splitting, either 0,1, or 2 splitting planes
    int   bestTwoSplits;

    // setting the evaluation for split cases that must not be done
    float WorstEvaluation() const { return MAXFLOAT;}
    
    // The initialization for the first axis to be tested.
    void InitXaxis(int cnt, const SBBox &box);
    void InitYaxis(int cnt, const SBBox &box);
    void InitZaxis(int cnt, const SBBox &box);

    // Normalize the best cost by surface area of the box
    void NormalizeCostBySA2() { bestCost /= areaWholeSA2;}

    SSplitState():bucketN(0), bucketMin(0), bucketMax(0) { }
    ~SSplitState() { delete []bucketMin; delete []bucketMax;}

    void InitBuckets() {
      assert(bucketMin);
      assert(bucketMax);
      for (int i = 0; i < bucketN; i++) {
        bucketMin[i] = 0;
        bucketMax[i] = 0;
      } // for
    }
  };

  // splitting state for current search
  SSplitState state;
  
  // structure for prefered and required params for evaluation functions
  // and the termination criteria
  struct SReqPrefParams
  {
    //if any position on required axis is preferred for next subdivision step
    float reqPosition; // then reqPosition>0
    // if any axis is prefered for next step
    bool  useReqAxis;
    // the prescribed axis for the next subdivision
    CKTBAxes::Axes reqAxis;

    // -------------- AUTOMATIC TERMINATION CRITERIA ---------------------
    // the ratio of improvement for the cost by subdivision and not-subdividing
    // for the previous subdivision
    float ratioLast;
    // the ratio of improvement for the subdivision in the previous step
    float ratioLastButOne;
    // the number of subdivision from the root node, where the improvement
    // in the cost failed
    int   failedSubDivCount;
    void Init() {
      reqPosition = Limits::Infinity;
      useReqAxis = false;
      reqAxis = CKTBAxes::EE_Leaf;
  
      ratioLast = 1000.0;
      ratioLastButOne = 1000.0;
      failedSubDivCount = 0;
    }
  };

  // initialize required and preferenced parameters before first subdivision
  void InitReqPref(SReqPrefParams *pars);

  // the array of preferred parameters used as a stack
  SReqPrefParams *pars;
  
  // --------------------------------------------------------------------
  bool verbose;

  // ---------------------------------
  // The selection of the axis
  int _algorithmForAxisSelection;
  
  //  ---- termination criteria -----
  int algorithmAutoTermination; // the algorithm for automatic termination criteria
  int maxDepthAllowed; // maximal depth of CKTB tree
  int maxListLength; // maximal list length of CKTB tree
  int maxCountTrials; // maximum number of trials for automatic termination criteria
  // the cutting off empty space in leaves
  bool cutEmptySpace; // if to cut off empty space in leaves in postprocessing
  int absMaxAllowedDepth; // maximal depth from the root - mut not be surpassed
  // maximal depth allowed for cutting within the leaf .. cut off empty space
  int maxEmptyCutDepth; // must be <0,1,2,3,4,5,6> since six planes are enough
  // This is working variable, denoting the depth of the leaf to be created.
  int startEmptyCutDepth;

  // Biasing the empty cuts (no objects are split). The cost is multiplied
  // by the coefficient which is assumed to be 0.8-0.9
  float  biasFreeCuts;
  
  // flag if to put minimum enclosing boxes sparsely during the construction
  bool    makeMinBoxes;
  // if we make tight boxes if we put min box !
  bool    makeTightMinBoxes;
  // parameters to drive the minboxes construction
  int     minObjectsToCreateMinBox, minDepthDistanceBetweenMinBoxes;
  float   minSA2ratioMinBoxes;
  // Make min box here
  bool   makeMinBoxHere;

  // two next axes are stored in oaxes for each axis
  static const CKTBAxes::Axes oaxes[3][2];  

  // for some functions it is necessary to have determined the following costs
  float       Ct; // traversal cost - going in given direction != decision
  float       Ci; // intersection cost - average intersection cost with object
  
  // ------ data to create the tree --------------------
  int         initcnt;      // initial number of objects
  SBBox       wBbox; // the box of the world in float values
  Vector3   boxSize;   // the size of world bounding box in float
  float       wholeBoxArea; // the surface area of the scene bounding box

  // if to print out the tree during construction
  bool _printCuts;

  // ------------------------------------------------------
  // A structure for a single step of subdivision
  struct SInputData {
    // the list of objects associated with the interior node
    ObjectContainer *objlist;
    
    // the traversal bounding box of the scene (not necessarily tight)
    SBBox box;
    // the box, which is tight and it lies inside the traversal box
    SBBox tightbox;
    
    // the number of objects in the node (= number_of_boundaries/2)
    int count;

    // ----------------------------
    // The mode of subdivision
    ESubdivMode modeSubDiv;

    // Some prescribed parameters to be used
    SReqPrefParams pars;

    // ----------------------------------
    // Axis to be used if prescribed
    CKTBAxes::Axes axis;
    // the position to be used for MakeOneCut
    float position;
    float position2;

    // if 1 or 2 splits
    int twoSplits;
    // the best cost
    float bestCost;

    // if to make subdivision on the left node
    int makeSubdivisionLeft;
    // if to make subdivision on the right node
    int makeSubdivisionRight;

    // -----------------------------------
    // When the min boxes was inserted as the first one
    int lastDepthForMinBoxes;
    // The surface area for the last minimum box inserted
    float lastMinBoxSA2;
    // The pointer to the last inserted minimum box
    SKTBNodeT* lastMinBoxNode;
  private:
    void Init() {
      objlist = 0;
      box.Initialize();
      tightbox.Initialize();
      count = 0;
      pars.Init();
      makeSubdivisionLeft = makeSubdivisionRight = 1;
      lastDepthForMinBoxes = 0;
      lastMinBoxSA2 = INFINITY;
      lastMinBoxNode = 0;
    }
    
  public:

    // -----------------------------------
    // Implicit constructor
    SInputData() {
      Init();
    }
    ~SInputData() {
      Free();
    }

    void Free() {
      delete objlist;
      objlist = 0;
    }
    
    void CopyBasicData(SInputData *d) {
      box = d->box;
      count = 0;
      modeSubDiv = d->modeSubDiv;
      pars = d->pars;
      axis = d->axis;
      position = d->position;
      // added 12/2007 VH
      position2 = d->position2;
      //
      makeSubdivisionLeft = d->makeSubdivisionLeft;
      makeSubdivisionRight = d->makeSubdivisionRight;      
      // Intentionally, do not copy vectors of items
      lastDepthForMinBoxes = d->lastDepthForMinBoxes;
      lastMinBoxSA2 = d->lastMinBoxSA2;
      lastMinBoxNode = d->lastMinBoxNode;
    }
  };

  // Stack of data to be used
  SInputData *stackID;
  // current index
  int         stackIndex;
  // the maximum depth of tree
  int         maxTreeDepth;
  // the depth of the stack
  int         stackDepth;
  
  SInputData* AllocNewData() {
    int i = stackIndex;
    stackIndex++;
    assert(stackIndex < stackDepth);
    return &(stackID[i]);
  }
  // Free the last data allocated
  void FreeLastData() { stackIndex--; }

  // returns a box enclosing all the objects in the node
  void GetTightBox(const SInputData &i, SBBox &tbox);

  // Compute if to subdivide and where
  SKTBNodeT* SubDiv(SInputData *d);
  // creates one cut inside CKTB tree
  SKTBNodeT* MakeOneCut(SInputData *i);

  SInputData* Init(ObjectContainer *objlist, const AxisAlignedBox3 &box);

  // make the full leaf from current node
  SKTBNodeT* MakeLeaf(SInputData *d);

  // It goes through the splitting plane positions and computes the cost
  void GetSplitPlaneOpt(SInputData *d, int axisToTest);

  // Given the splitting plane position, it computes the cost
  void EvaluateCost(SSplitState &state);
  void EvaluateCostFreeCut(SSplitState &state);

  // setting the evaluation for split cases that must not be done
  float WorstEvaluation() const { return MAXFLOAT;}

  // update the best value for evaluation
  int UpdateEvaluation(float &eval, const float &newEval);

public:
  // default constructor
  CKTBSBuildUp();

  // default destructor
  virtual ~CKTBSBuildUp();

  // provide info about construction method
  virtual void ProvideID(ostream &app);  
  
  // constructs the KD-tree for given objectlist and given bounding box
  // returns NULL in case of failure, in case of success returns
  // the pointer to the root node of constructed KD-tree.
  virtual SKTBNodeT* BuildUp(ObjectContainer &objlist,
                             const AxisAlignedBox3 &box,
                             bool verbose = true);
};

}

#endif // __KTBS_H__