source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktball.h @ 2608

// ===================================================================
// $Id: $
//
// ktball.h
//      CKTB accelerating data structure for ray-shooting
//
// Class: CKTB
//
// REPLACEMENT_STRING
//
// Initial coding by Vlasta Havran

#ifndef __KTBALL_H__
#define __KTBALL_H__

// GOLEM headers
#include "configh.h"
#include "ktbconf.h"
//#include "ktbi.h"
#include "ktbai.h"
#include "ktbtrav.h"
#include "gzstream.h"

namespace GtpVisibilityPreprocessor {

// forward declarations
class CKTBAllocMan;
class RayPacket2x2;

// ----------------------------------------------------------
// ----------------------------------------------------------
// ----------------------------------------------------------
// the CASDS describing CKTB itself, the interface object to
// the other objects for CKTB tree building up and traversing
class CKTB
//  : public CASDS_BB
{
protected:
  // True if the data structure is built up
  bool builtUp;
  
  // the box bounding the whole scene
  AxisAlignedBox3 bbox;
  
  // the number of objects in the case the object list is
  // not copied to this->objlist
  int countObjects;

  // precomputed cost for intersection of kd-tree with arbitrary ray
  float _expectedIntersectionCost;
  
  // the class which serves as builder of CKTB tree
  CKTBAllocManPredecessor *buildClass;

  // the class that provides traversing through CKTB tree
  CKTBNodeIteratorPredecessor *traversalClass;

  // if we use min boxes enhancement
  bool makeMinBoxes;
  // if we want to make boxing with only tight boxes
  bool makeTightMinBoxes;

  // the size of 2D buffer
  int size2D;
  int index2D;
  // the indices in the buffer
  int indexRead, indexWrite;
  // the distance between two rays, where a new buffer of box nodes is written
  int distSLCTS;

  // Whether we use SLCTS boxes for FindNearest
  bool useSLCTS;
  
  // construct traversal class for CKTB Trees
  void AllocTraversalClass();

  // provide the parameters for construction of CKTB tree to stream
  void ProvidePars(ostream &app);

  // builds up CKTB tree without unbounded objects. The 'boxToInclude
  // is a box that can be optionally given and the kd-tree constructed
  // must contain such a box. The 'boxToBoundObjects' when given, is
  // a box to which the objects boxes are bounded. This is used for special
  // cases such a multilevel kd-trees.
  void BuildingUp(ObjectContainer& objlist,
                  const AxisAlignedBox3 *boxToInclude = 0,
                  const AxisAlignedBox3 *boxToBoundObjects = 0,
                  bool verbose = true);

  // create the array of pointers to objects addressable by object uniqueID
  void CreatePointerArray(ObjectContainer &arrobjlist,
                          int objCounterOffset);

  // checks the boxes of all objects if they are not flat somehow
  bool CheckBoxes(ObjectContainer& objlist);  

protected:
  // statistics
  int numElemCells;
  int numEmptyElemCells;
  float emptyVolume;
  float nonEmptyVolume;
  int numSolidsInElemCells;
  int actMaxListLen;
  int numHierCells;
  int actMaxDepth;
  float sumSurfaceAreaLeaves;
  float sumSurfaceAreaMULcntLeaves;
  float sumSurfaceAreaInteriorNodes;
  
public:
  // default constructor
  CKTB();

  // default destructor
  ~CKTB();

  void BuildUp(const ObjectContainer &objlist);

  // functions that allows correctly traverse recursively allowing to have
  // the same traversal stack
  void TraversalReset();

  void StatsReset() {
    if (traversalClass)
      traversalClass->DynamicStatsReset();
  }
  
  bool HandleUnboundeds() const { return true;}
  
  void GetBBox(AxisAlignedBox3 &box) { box = bbox;}
    
  void PrintStats();

  // Delete all the data structures
  void Remove();
  
  void ProvideID(ostream &app);
  
  float ExpectecteRayIntersectionCost() const {
    return _expectedIntersectionCost;
  }
  
  // describe the toplogy of CKTB to a given stream
  void DescribeTopology(const string &filename,
                        int objCounterOffset,
                        int format) { }
  
  // Not yet implemented
  bool RestoreTopology(const string &filename,
                       long int streamOffset,
                       const ObjectContainer &objects,
                       int objCounterOffset,
                       int format) { return true; }
  
  // allocate new build class and return it
  static CKTBAllocManPredecessor* AllocBuildClass();
  
  CKTBNodeIteratorPredecessor* GetTraversalClass() {
    return traversalClass;
  }
  
  CKTBAllocManPredecessor* GetBuildClass() {
    return buildClass;
  }
  void SetBuildClass(CKTBAllocManPredecessor *build) {
    buildClass = build;
  }
  void DeleteBuildClass();
  
  // Here are the functions required from CASDS interface
  void GatherStats(bool itself = false);
  void GatherPostStats();
  void* Locate(const Vector3 &loc);
  
  int FindNearestI(const SimpleRay &ray);
  int FindNearestI(const SimpleRay &ray, const Vector3 &boxMin, const Vector3 &boxMax);
  void SetOffset(int offset) { traversalClass->SetOffset(offset); }
  int FindNearestI_16oneDir(SimpleRayContainer &rays, int offset, int copyOffset) {
    return traversalClass->FindNearestI_16oneDir(rays, offset, copyOffset);
  }
  int FindNearestI_16oneDirNoSSE(SimpleRayContainer &rays, int offset) {
    return traversalClass->FindNearestI_16oneDirNoSSE(rays, offset);
  }
  int FindNearestI_16twoDir(SimpleRayContainer &rays) {
    return traversalClass->FindNearestI_16twoDir(rays);
  }
  
#ifdef __SSE__
#ifdef _USE_HAVRAN_SSE  
  // The same operations for packets of rays, if implemented by
  // a particular ASDS, otherwise it is emulated by decomposition
  // of a packet to individual rays and traced individually.
  void FindNearestI(RayPacket2x2 &raypack);
  void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin, const Vector3 &boxMax);
#endif
#else
  void FindNearestI(RayPacket2x2 &raypack) { }
  void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin, const Vector3 &boxMax) { }
#endif // __SSE__

  // Loading and saving
  void ExportBinLeaf(OUT_STREAM &stream, SKTBNodeT *leaf);
  SKTBNodeT* ImportBinLeaf(IN_STREAM &stream, 
                           SKTBNodeT **nodeToLink,
                           const ObjectContainer &objects);

  void ExportBinInterior(OUT_STREAM &stream, SKTBNodeT *interior);
  SKTBNodeT *ImportBinInterior(IN_STREAM  &stream,
                               SKTBNodeT **nodeToLink);  

  SKTBNodeT * ImportNextNode(IN_STREAM &stream, 
                             SKTBNodeT **nodeToLink,
                             const ObjectContainer &objects);

  bool ExportBinTree(const string &filename);
  bool ImportBinTree(const string &filename, ObjectContainer &objects);

  
protected:  
  // The 2D array of pointers to the interior nodes with boxes.
  SKTBNodeT ***buffer;
  int sizeBuffer, size1D;
  void AllocBuffer(int size2D, int size1Dv);

  struct STraversalData
  {  
    SKTBNodeT *mNode;
    int        dir;
    int        depth;
    STraversalData() {}

    STraversalData(SKTBNodeT *n): mNode(n)
    { }
    
    STraversalData(SKTBNodeT *n, int ndir, int ndepth):
      mNode(n), dir(ndir), depth(ndepth) { }
  };
};

}

#endif // __KTBALL_H__