source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktbtrav.h @ 2629

// ===================================================================
// $Id: $
//
// ktbtrav.h
//      Traversal class for CKTB structures
//
// Class: CKTBTraversal
//
// REPLACEMENT_STRING
//
// Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
// Initial coding by Vlasta Havran, 2006

#ifndef __KTBTRAV_H__
#define __KTBTRAV_H__

// GOLEM headers
#include "configh.h"
#include "ktbconf.h"
#include "ktb.h"
#include "ktb8b.h"
#include "raypack.h"
// From the framework of Jiri Bittner et al. GTP
#include "SimpleRay.h"


#ifdef __SSE__
#include <xmmintrin.h>
#endif

namespace GtpVisibilityPreprocessor {
  
//#define TRV000
//#define TRV001
//#define TRV002
//#define TRV003
//#define TRV004
//#define TRV005
//#define TRV006
//#define TRV007
#define TRV00F

// forward declarations
class SKTBNode;

// This is debugging of traversal for a new traversal variant
//#define _DEBUGKTB

// This is debugging of traversal storing depth at the stack
//#define _KTBEXTSTACK
  
// VERSION1 - the version, where we prepare a sequence of boxes
//            which never overlap (file ktbmtrav.cpp)
// VERSION2 - the sequence of boxes can overlap and we solve which
//            boxes to traverse online during the traversal (file ktbm2trv.cpp)
// VERSION3 - the stackless algorithm based on interval tracking
//            keeping entry and exit point (file ktbm3trv.cpp)
// VERSION4 - the stack-based algorithm rewritten from ktbm3trv.cpp
//            by adding the stack (file ktbm4trv.cpp)
// VERSION5 - another stackless algorithm based on a single point and
//            virtual box tracking (file ktbm5trv.cpp)
// VERSION6 - simple sequential traversal algorithm without stack (TA_A)
//            published originally already in year 1985 by Kaplan
//            (file ktbm6trv.cpp)

// //#define _KTBTRAV_VERSION0
//#define _KTBTRAV_VERSION1
//#define _KTBTRAV_VERSION2
//#define _KTBTRAV_VERSION3
//#define _KTBTRAV_VERSION4
#define _KTBTRAV_VERSION5
//#define _KTBTRAV_VERSION6

// We cull away the nodes to be visited if they would be the same
// as the next box in the sequence of nodes with boxes
#define _CULL_IN_INTERIOR_NODES

// If this macro is defined, then we extract the sequence of boxes to
// the output buffer when visiting a leaf. When this macro is disabled,
// we make test upon visiting a box node, which can be faster, as the
// number of box nodes is smaller than the number of leaves visited 
#define EXTRACTSEQENENCEINLEAVES

// This is special development debug
#define _DEBUG_SAMELEAF

// Pseudo visualization
#define VIS_TRAVERSEDNODED

// If this macro is defined, we use increment of
// the signed distance to avoid visiting the same node again
// by multiplication and addition
// Otherwise (macro commented) we use a special function for that
// based on IEEE754 representation of floating-point
//#define INCTMIN

// These are constants to increase signed distance when exiting leaf
#define onePlusEps 1.000008f
#define epsAdd 0.000008f

//#define onePlusEps 1.00005f
//#define epsAdd 0.0001f
//const float onePlusEps = 1.0001f;
//const float epsAdd = 0.0001f;
//const float onePlusEps = 1.00008f;
//const float epsAdd = 0.00005f;        
//const float onePlusEps = 1.000008f; 
//const float epsAdd = 0.000008f;             
//const float onePlusEps = 1.0000008f;
//const float epsAdd = 0.00001f;        

// Here are the macros to avoid traversing the same leaf again
#define _DEBUGULPS
#define INCULPS 1

#ifndef _KTB8Bytes
// 12 Bytes representation
#undef  SKTBNodeT
#define SKTBNodeT CKTBNodeAbstract::SKTBNode
#else
// 8 Bytes representation
#undef  SKTBNodeT
#define SKTBNodeT CKTB8BNodeAbstract::SKTBNode
#endif

// 12 Bytes representation
class CKTBNodeIteratorPredecessor:
#ifndef _KTB8Bytes
  public CKTBNodeIterator
#else
  public CKTB8BNodeIterator
#endif
{
public:
  virtual int FindNearestI(const SimpleRay &ray) { return 0; }
  virtual int FindNearestI(const SimpleRay &ray, const AxisAlignedBox3 &localbox) { return 0;}
  void SetOffset(int offset) { rayOffset = offset; }
  virtual int FindNearestI_16oneDir(SimpleRayContainer &rays) { return 0; }
  virtual int FindNearestI_16oneDir(SimpleRayContainer &rays,
                                    int offset, int copyOffset) { return 0; } 
  virtual int FindNearestI_16oneDirNoSSE(SimpleRayContainer &rays, int offset) { return 0; }
  virtual int FindNearestI_16twoDir(SimpleRayContainer &rays) { return 0; }

  // the number of nested kd-trees at most
  enum { MAX_NESTING = 2};
  
#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.
  virtual void FindNearestI(RayPacket2x2 &raypack) { }
  virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin,
                            const Vector3 &boxMax) { }
#endif
  
  virtual void PrintStatsTR(ostream &) { }
  virtual void DynamicStatsReset() { }
};

// ---------------------------------------------------------------------------
// Note on the usage:
// Allow only one macro from the tree: _KTBTRAV_JANSEN86, _KTBTRAV_JGT98
// and  _KTBTRAV_OPTIMIZED86

// macro for using algorithm for traversal CKTB trees as stated by Jansen86,
// Arvo88, and Kelving/Sung92 in Gems III. 
//#define _KTBTRAV_JANSEN86

// Faster and robust algorithm is used, published in JGT 98
// by Havran+Bittner+Kopal+Zara. It is fastest at the moment, measured in year 2005/6
#define _KTBTRAV_JGT98

// Modified algorithm from Jansen86 (Arvo88, Kelving/Sung92), optimized for
// modern processors.
//#define _KTBTRAV_OPTIMIZED86

// ------------------------------------------------------------
#undef _COMPUTE_INVERTED_DIR_KTB
// This avoids the division when computed signed distance by precomputation
// of the inverse of ray.dir for all three components
#define _COMPUTE_INVERTED_DIR_KTB

// Check if the only traversal algorithm was used.
#ifdef _KTBTRAV_JANSEN86
#if (defined(_KTBTRAV_JGT98) || defined(_KTBTRAV_OPTIMIZED86))
#error "Allow only one of macros  _KTBTRAV_OPTIMIZED86, _KTBTRAV_JGT98, _KTBTRAV_OPTIMIZED86"
#endif
#endif
//-------------------------
#ifdef _KTBTRAV_JGT98
#if (defined(_KTBTRAV_JANSEN86) || defined(_KTBTRAV_OPTIMIZED86))
#error "Allow only one of macros  _KTBTRAV_OPTIMIZED86, _KTBTRAV_JGT98, _KTBTRAV_OPTIMIZED86"
#endif
#endif
//-------------------------
#ifdef _KTBTRAV_OPTIMIZED86
#if (defined(_KTBTRAV_JANSEN86) || defined(_KTBTRAV_JGT98))
#error "Allow only one of macros  _KTBTRAV_OPTIMIZED86, _KTBTRAV_JGT98, _KTBTRAV_OPTIMIZED86"
#endif
#endif

// -------------------------------------------------------------------
// robust statistically optimized algorithm for CKTB ray-traversal
// version 025
// This version appeared in JGT(Journal of Graphics Tools, Vol. 2, No.4,
// 1997, pp.15-23. with title:
// "FAST Robust KD-Tree Traversal Algorithm for Ray Tracing"

class CKTBTraversal:
  public CKTBNodeIteratorPredecessor
{
public:
  // maximal height of the CKTB tree for nesting
  enum { MAX_TRAVERSAL_HEIGHT = (MAX_HEIGHT * MAX_NESTING) };

protected:
  // the stack element for CKTB tree traversal 
  struct SStackElem {
    SKTBNodeT *nodep;  // pointer to the node
    // Vector3 point;  // entry/exit point
    float    x,y,z;  // entry/exit point
    float    t;      // signed distance of the point
    SStackElem *prev;
    SKTBNodeT *lastBoxNode; // here is the alingment
#ifdef _KTBEXTSTACK
    int       dummy; // storing the depth here
#endif    
  };

  // the stack element for CKTB tree traversal 
  struct SStackElem2 {
    SKTBNodeT *nodep;  // pointer to the node
    int      dummy;
    float    tmin;      // entry signed distance
    float    tmax;      // exit signed distance
  };
  struct SStackElem3 {
    SKTBNodeT *nodep;  // pointer to the node
    float    tmax;     // exit signed distance
  };

  struct SStackElem4 {
    SKTBNodeT *nodep;  // pointer to the node
    int      mask;     // mask
    int      pad[2];   // alignment to 16 bytes
    union { float tmin4[4];
#ifdef __SSE__
      __m128 tmin_4;
#endif
    };
    union { float tmax4[4];
#ifdef __SSE__
      __m128 tmax_4;
#endif
    };
  };

  
  // the stack of elems - declared as static not to allocate it every time
  static struct SStackElem stack[MAX_TRAVERSAL_HEIGHT];
  static struct SStackElem2 stack2[MAX_TRAVERSAL_HEIGHT];
  static struct SStackElem3 stack3[MAX_TRAVERSAL_HEIGHT];
  static struct SStackElem4 stack4[MAX_TRAVERSAL_HEIGHT];

#define cntMaxRays 16
  static struct CKTBTraversal::SStackElem3 stackA[cntMaxRays * MAX_HEIGHT];

  // the axis aligned box for CKTB tree space
  AxisAlignedBox3 bbox;
  // root node of the CKTB tree
  SKTBNodeT *root;
  // the small epsilon that is computed from the size of the whole box
  float epsilon;

  // sets the stack pointers that are used for the traversal.
  void GetStackPointers(struct SStackElem *&entryPointer,
                        struct SStackElem *&exitPointer);
  void GetStartStackPointer(struct SStackElem *&exitPointer);
  
  // this function should be called when exiting from the traversal function
  // to keep the track on the traversalDepth (of kd-trees, when they are nested).
  void RestoreStackPointers();

  // the depth of traversal when kd-trees are nested. The global (the highest
  // level) kd-tree is at the depth 0.
  static int traversalDepth;

#ifdef __TRAVERSAL_STATISTICS
  long unsigned int _allNodesTraversed;
  long unsigned int _fullLeavesTraversed;
  long unsigned int _emptyLeavesTraversed;
#endif

public:
  // default constructor
  CKTBTraversal();

  // destructor
  virtual ~CKTBTraversal() {}

  // sets the bbox and the root node for this traversal class
  virtual void Setup(const AxisAlignedBox3 &box, SKTBNodeT *Nroot)
    { bbox = box; root = Nroot; epsilon=(float)(1e-6*Magnitude(bbox.Size())); }

  // potentionally, sets the list of unbounded objects if required
  virtual void Setup2(CObjectList *) { // int count = unboundeds->ListCount();
  }

  virtual int FindNearestI(const SimpleRay &ray);
  virtual int FindNearestI(const SimpleRay &ray, const AxisAlignedBox3 &localbox);
  virtual int FindNearestI_16oneDir(SimpleRayContainer &rays,
                                    int offset, int copyOffset)
#ifdef _USE_HAVRAN_SSE  
    ; // this is implemented with SSE in ktbftrav.cpp !
#else
  { return 0;}
#endif
    
  virtual int FindNearestI_16oneDirNoSSE(SimpleRayContainer &rays, int offset);

  int PrecomputeData(SimpleRayContainer &rays);
  void ReverseRay(const int indexA);
  virtual int FindNearestI_16twoDir(SimpleRayContainer &rays);

#ifdef _USE_HAVRAN_SSE  
#ifdef __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.
  virtual void FindNearestI(RayPacket2x2 &raypack);
  virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin,
                            const Vector3 &boxMax);
#endif // __SSE__
#endif // _USE_HAVRAN_SSE  
  
  virtual void PrintStatsTR(ostream &) { }

  void AssignIDs(SKTBNodeT *node = NULL);

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

  // Here we find the node (preferably minbox node) containing
  // the point
  virtual const SKTBNode* Locate(const Vector3 &position);
};

#if 0
// The version taking into account min boxes sparsely distributed in
// the kd-tree.
class CKTBMinBoxesTraversal:
  public CKTBNodeIteratorPredecessor
{
protected:
  // the stack element for CKTB tree traversal 
  struct SStackElem {
    SKTBNodeT *nodep;  // pointer to the node
    // Vector3 point;  // entry/exit point
    float    x,y,z;  // entry/exit point
    float    t;      // signed distance of the point
    SStackElem *prev;
    SKTBNodeT *lastBoxNode; // here is the alingment
//#ifdef _KTBEXTSTACK
    int       dummy; // storing the depth here
//#endif    
  };

  // maximal height of the CKTB tree for nesting
  enum { MAX_TRAVERSAL_HEIGHT = (MAX_HEIGHT * MAX_NESTING) };
  
  // the stack of elems - declared as static not to allocate it every time
  static struct SStackElem stack[MAX_TRAVERSAL_HEIGHT];

  // the axis aligned box for CKTB tree space
  AxisAlignedBox3 bbox;
  // root node of the CKTB tree
  SKTBNodeT *root;
  // the small epsilon that is computed from the size of the whole box
  float epsilon;
  // size of the write buffer
  int size1D;

  // sets the stack pointers that are used for the traversal.
  void GetStackPointers(struct SStackElem *&entryPointer,
                        struct SStackElem *&exitPointer);
  void GetStartStackPointer(struct SStackElem *&exitPointer);
  
  // this function should be called when exiting from the traversal function
  // to keep the track on the traversalDepth (of kd-trees, when they are nested).
  void RestoreStackPointers();

  // the depth of traversal when kd-trees are nested. The global (the highest
  // level) kd-tree is at the depth 0.
  static int traversalDepth;

#ifdef __TRAVERSAL_STATISTICS
  long unsigned int _allNodesTraversed;
  long unsigned int _fullLeavesTraversed;
  long unsigned int _emptyLeavesTraversed;
#endif
  
public:
  // default constructor
  CKTBMinBoxesTraversal(int size1Dv);

  // destructor
  virtual ~CKTBMinBoxesTraversal();

  // sets the bbox and the root node for this traversal class
  virtual void Setup(const AxisAlignedBox3 &box, SKTBNodeT *Nroot)
    { bbox = box; root = Nroot; epsilon=(float)(1e-6*Magnitude(bbox.Size())); }

  // potentionally, sets the list of unbounded objects if required
  virtual void Setup2(CObjectList *) { // int count = unboundeds->ListCount();
  }

  virtual int FindNearestI(SimpleRay &ray);

#ifdef _USE_HAVRAN_SSE  
#ifdef __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.
  virtual void FindNearestI(RayPacket2x2 &raypack);
  virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin,
                            const Vector3 &boxMax);
#endif // __SSE__
#endif // _USE_HAVRAN_SSE  

  virtual void DynamicStatsReset();
  
  virtual void PrintStatsTR(ostream &);

  void AssignIDs(SKTBNodeT *node = NULL);

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

#ifdef __TRAVERSAL_STATISTICS
  unsigned long int statsMB_UpTraversals;
  unsigned long int statsMB_DownTraversals;
  unsigned long int statsMB_cntRays;
  unsigned long int statsMB_cntRaysHB;
  unsigned long int statsMB_UseTraversals;
  unsigned long int statsMB_UseValidTraversals;
  unsigned long int statsMB_allNodesTraversed;
  unsigned long int statsMB_fullLeavesTraversed;
  unsigned long int statsMB_emptyLeavesTraversed;
  unsigned long int bugTheSameLeaf;
  unsigned long int statsMB_writtenBoxes;
  unsigned long int statsMB_readBoxes;
  unsigned long int statsMB_cntWrittenBoxSequenceEvent;
  unsigned long int statsMB_cntReadBoxSequenceEvent;
#endif

  // Here we find the node (preferably minbox node) containing
  // the point
  virtual const SKTBNode* Locate(const Vector3 &position);
};
#endif
  
} // namespace

#endif // __KTBTRAV_H__