source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktb8b.cpp @ 2592

// ===================================================================
// $Id: $
//
// ktb.cpp
//
//     KDB - trees for ray tracing, special version for SCCG 2006
//
// REPLACEMENT_STRING
//
// Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
// Initial coding by Vlasta Havran, 1998-2001.

// GOLEM library
#include "ktb8b.h"
#include "Environment.h"

// standard headers
#include <algorithm>

namespace GtpVisibilityPreprocessor {

// default constructor
CKTB8BNodeIterator::CKTB8BNodeIterator()
{

}
  
//-------------------------------------------------------------
// class CKTB8BNodeIterator .. implementation

// test all objects in the leaf for intersection with ray
// and returns the pointer to closest one if exists
// and passing through parameter returns in tmax
int
CKTB8BNodeIterator::TestFullLeaf(const SimpleRay &ray, const SKTBNode *p)
{
  ObjectContainer *list = GetObjList(p);  
  if (!list) // no object 
    return 0;
  ObjectContainer::iterator sc_end = list->end();

  int intersected = 0;
  // iterate the whole list and find out the nearest intersection
  for (ObjectContainer::iterator sc = list->begin(); sc != sc_end; sc++) {
    // if the intersection realy lies in the node        
    if ((*sc)->CastSimpleRay(ray)) {
      intersected = 1;
    }
  } // for all objects

  return intersected;
}

int
CKTB8BNodeIterator::TestFullLeaf(const SimpleRay &ray, const SKTBNode *p,
                                 int indexRay)
{
  ObjectContainer *list = GetObjList(p);  
  if (!list) // no object 
    return 0;
  ObjectContainer::iterator sc_end = list->end();

  float tclosest = Limits::Infinity;
  int intersected = 0;
  indexRay += rayOffset;
  // iterate the whole list and find out the nearest intersection
  for (ObjectContainer::iterator sc = list->begin(); sc != sc_end; sc++) {
    // if the intersection realy lies in the node        
    if ((*sc)->CastSimpleRay(ray, indexRay)) {
      // update tclosest !!!!!!!!!!!!!!!!!!!!!!!!!!!!
      // tclosest = ray.
      intersected = 1;
    }
  } // for all objects

  return intersected;
}
  
// test all objects in the leaf for intersection with ray
// and find any if exist .. returns this object, otherwise 0
int
CKTB8BNodeIterator::HitAnyObj(const SimpleRay &ray, const SKTBNode *p)
{
  ObjectContainer *list = GetObjList(p);  
  if (!list) // no object 
    return 0;
  ObjectContainer::iterator sc_end = list->end();

  float tclosest = Limits::Infinity;
  int intersected = 0;
  // iterate the whole list and find out the nearest intersection
  for (ObjectContainer::iterator sc = list->begin(); sc != sc_end; sc++) {
    Intersectable *is = (*sc);
    // if the intersection realy lies in the node        
    if (is->CastSimpleRay(ray)) {
      // update tclosest !!!!!!!!!!!!!!!!!!!!!!!!!!!!
      // tclosest = ray.
      return 1; // intersected
    }
  } // for all objects

  return 0;
}

const CKTB8BNodeAbstract::SKTBNode*
CKTB8BNodeIterator::Locate(const Vector3 & /*position*/)
{
  cerr << "Locate vector - Not yet implemented" << endl;
  return (CKTB8BNodeAbstract::SKTBNode*)0;
}


// ---------------------------------------------------------------------
// Allocator for KTB tree

// forget the content that is created by previous kd-tree construction
// or just init for the first use.
void
CKTB8BAllocMan::InitForConstructor()
{
#ifdef _KTB_CONSTR_STATS
  _stats_interiorCount = 0;
  _stats_bboxCount = 0;
  _stats_leafNodeCount = 0;
  _stats_emptyLeftNodeCount = 0;
  // Aggregate statistics
  _sumLeafDepth = 0;
  _sumFullLeafDepth = 0;
  // The count of object references in leaves
  _sumObjectRefCount = 0;
  // The maximum number of object references in a leaf
  _maxObjectRefInLeaf = 0;
  // surface areas
  _sumSurfaceAreaLeaves = 0.f;
  _sumSurfaceAreaMULcntLeaves = 0.f;
  _sumSurfaceAreaInteriorNodes = 0.f;
#endif
  
  // This is the statistics
  _currDepth = 0;
  _maxDepth = -1;
  InitPars();
}

// init the stack of auxiliary variables from min to max
void
CKTB8BAllocMan::InitAux(int /*min*/, int /*maxD*/, int maxItemsAtOnce)
{
  // The size of one entry
  int sizeEntryV = sizeof(SKTBNode);
  // The number of entries to be allocated at once in a block
  // (=size of the block)
  int numEntriesInBlock = 1024;
  // the allignment
  int allignEntrySizeV = sizeof(SKTBNode);
  int allignBlockSizeV = 128;

  // Create an allocator in DFS order
  alloc2 = new CAllocContinuous(sizeEntryV, numEntriesInBlock,
                                maxItemsAtOnce,
                                allignEntrySizeV,
                                allignBlockSizeV);
  assert(alloc2);
  // the first allocation is enabled by this command
  alloc2->AllocNewBlock();
  return;
}

// Read some basic parameters from the environment file
void
CKTB8BAllocMan::InitPars()
{
  Environment::GetSingleton()->GetIntValue("BSP.maxListLength",
                                           maxListLength);
  Environment::GetSingleton()->GetIntValue("BSP.maxDepthAllowed",
                                           maxDepthAllowed);
}

void
CKTB8BAllocMan::PostBuild()
{
  // Here it can be some postprocessing of the tree, such as branches
  // collapsing for the same content of leaves etc.
}

void
CKTB8BAllocMan::Remove()
{
  // Release the all memory by blocks, so all the interior nodes
  // and leaves representations. This should be fast.
  alloc2->ReleaseMemory();
}


// Create the representation of the interior node
SKTBNodeT*
CKTB8BAllocMan::AllocInteriorNode(int axis, float position,
                                  int cntLeft, int cntRight)
{
#ifdef _DEBUG
  nodeToLink = 0;
#endif

#ifdef _KTB_CONSTR_STATS
  _stats_interiorCount++;
#endif
  
  // Just to satisfy the compiler
  cntLeft = cntLeft;
  cntRight = cntRight;
  
  // Alloc a single node
  SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(1));
  nodeToLink = n;
  if (n == 0) {
    // we have to insert a special node that links only
    nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
    assert(nodeToLink);
    nodeToLink->offset = CKTBAxes::EE_Link;
    n = (SKTBNodeT*)(alloc2->NewEntryInNewBlock(1));
    // This is the link
    nodeToLink->linkedNode = n;    
  } // if n

  assert(n);
  assert(nodeToLink);

  // Set the interior node
  assert((axis >=0) && (axis < 3));
  n->offset = axis;
  n->splitPlane = position;

#ifdef _DEBUG_ALLOCATION  
  cout << "AllocInterior node adr = " << (void*)n << endl;
#endif // _DEBUG_ALLOCATION
  // Return the setupped node, but do not forget to
  // use in the parent node to use nodeToLink !!!!
  return n;
}

// Create the representation of the interior node with box
SKTBNodeT*
CKTB8BAllocMan::AllocInteriorNodeWithBox(int axis, float position,
                                         int cntLeft, int cntRight,
                                         const SBBox &tsbox,
                                         SKTBNodeT* prevMinBoxNode,
                                         int depthStore)
{
#ifdef _DEBUG
  nodeToLink = 0;
  if ( (position < tsbox.Min(axis)) ||
    (position > tsbox.Max(axis)) ) {
    cerr << "Something wrong with the tree axis = " << axis;
    cerr << " Min(axis) = " << tsbox.Min(axis)
          << " splitValue = " << position
          << " Max(axis) = " << tsbox.Max(axis) << endl;
    abort();;
  }  
#endif

#ifdef _KTB_CONSTR_STATS
  _stats_interiorCount++;
  _stats_minbboxCount++;
#endif
  
  // Just to satisfy the compiler
  cntLeft = cntLeft;
  cntRight = cntRight;

#ifdef _SHORT_FORM_MINBOX  
  // Alloc two nodes = 2*8 Bytes = 16 Bytes
  SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(2));
  nodeToLink = n;
  if (n == 0) {
    // we have to insert a special node that links only
    nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
    assert(nodeToLink);
    nodeToLink->offset = CKTBAxes::EE_Link;
    n = (SKTBNodeT*)(alloc2->NewEntryInNewBlock(2));
    // This is the link
    nodeToLink->linkedNode = n;    
  } // if n

  assert(n);
  assert(nodeToLink);

  // Set the interior node
  assert((axis >=0) && (axis < 3));
  n->offset = (int)CKTBAxes::EE_X_axisBox + axis;
  n->splitPlane = position;

  // Set the box
  // and the address to the parent min box node
  (n+1)->parentBoxNode = prevMinBoxNode;

  // Here we simply allocate the box for the address
  SBBox *badr = new SBBox; 
  assert(badr);
  (n+1)->pointer = (unsigned char *)badr;

  // Note that we cannot store the depth here !
  depthStore = depthStore; // to satisfy the compiler
#else // _SHORT_FORM_MINBOX
  // Alloc two single nodes (16 Bytes) + box (24 Bytes) = 40 Bytes
  SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(5));
  nodeToLink = n;
  if (n == 0) {
    // we have to insert a special node that links only
    nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
    assert(nodeToLink);
    nodeToLink->offset = CKTBAxes::EE_Link;
    n = (SKTBNodeT*)(alloc2->NewEntryInNewBlock(5));
    // This is the link
    nodeToLink->linkedNode = n;    
  } // if n

  assert(n);
  assert(nodeToLink);

  // Set the interior node
  assert((axis >=0) && (axis < 3));
  n->offset = (int)CKTBAxes::EE_X_axisBox + axis;
  n->splitPlane = position;

  // Set the box itself
  // and the address to the parent min box node
  (n+1)->parentBoxNode = prevMinBoxNode;
  // here we set the depth of the node (suited for debugging)
  (n+1)->depth = depthStore;
  
  // This is not very nice, we use the address in already allocated
  //item, but this saves memory of 4 Bytes, which allows allingment to 32 Bytes
  //for this entry
  SBBox *badr = (SBBox*)(((char*)n)+16);  
#endif // _SHORT_FORM_MINBOX

  // and copy the box content from the function parameters
  *(badr) = tsbox;
  
#ifdef _DEBUG_ALLOCATION  
  cout << "AllocInterior node adr = " << (void*)n << endl;
#endif // _DEBUG_ALLOCATION
  // Return the setupped node, but do not forget to
  // use in the parent node to use nodeToLink !!!!
  return n;
}
  
// Set the pointers to children for the interior node
void
CKTB8BAllocMan::SetInteriorNodeLinks(SKTBNodeT *node,
                                     SKTBNodeT *leftChild,
                                     SKTBNodeT *rightChild)
{
  leftChild = leftChild; // to satisfy the compiler

#if 1
  if (! ((node+1 == leftChild) || (node+2 == leftChild) ||
         (node+5 == leftChild))) {

    cout << "Problem with left node linking " << endl;
  }

#endif      
  // Check on correctness of DFS order
  assert( (node+1 == leftChild) || (node+2 == leftChild) || (node+5 == leftChild) );

#ifdef _DEBUG_ALLOCATION  
  cout << "SetInteriorNode adr = " << (void*)node
       << " right = " << (void*)rightChild << endl;
#endif
  
#ifdef _DEBUG
  // Check if last 3 bits of the address are really zero
  // and hence they can be used for different purposes
  if ( ( ((unsigned int)rightChild) & CKTBAxes::EE_Mask) != 0) {
    // The bug in implementation of DFS order allocator or so
    // This should never happen.
    cerr << "cerr error, node is not 8Bytes aligned, it cannot be linked in DFS" << endl;
    abort();;
  }
#endif

  // Bitwise OR should work correctly
  assert(node->offset <= CKTBAxes::EE_Z_axisBox);
  //assert(node->offset >= 0);
  //(unsigned long)node->offset |= (unsigned long)rightChild;
  node->offset = node->offset | (unsigned int)rightChild;
#ifdef _DEBUG
  // Compute right child
  SKTBNodeT *p = GetRight(node);
  if (p != rightChild) {
    cerr << "Problem with implementation of setting right child" << endl;
    abort();;
  } 
#endif

  return;
}

// Set the pointers to children for the interior node
void
CKTB8BAllocMan::SetInteriorNodeLeft(SKTBNodeT *node,
                                    SKTBNodeT *leftChild)
{
  leftChild = leftChild; // to satisfy the compiler

#if 1
  if (! ((node+1 == leftChild) || (node+2 == leftChild) ||
         (node+5 == leftChild))) {

    cout << "Problem with left node linking " << endl;
    abort();
  }

#endif      
  // Check on correctness of DFS order
  assert( (node+1 == leftChild) || (node+2 == leftChild) || (node+5 == leftChild) );

  // Nothing to do - left link is linked automatically
  return;
}

// Set the pointers to children for the interior node
void
CKTB8BAllocMan::SetInteriorNodeRight(SKTBNodeT *node,
                                     SKTBNodeT *rightChild)
{
  assert(node->offset <= CKTBAxes::EE_Z_axisBox);
  //assert(node->offset >= 0);
  //(unsigned long)node->offset |= (unsigned long)rightChild;
  node->offset = node->offset | (unsigned int)rightChild;
#ifdef _DEBUG
  // Compute right child
  SKTBNodeT *p = GetRight(node);
  if (p != rightChild) {
    cerr << "Problem with implementation of setting right child" << endl;
    abort();;
  } 
#endif

  return;
}

  
// 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*
CKTB8BAllocMan::AllocLeaf(int cntObjects)
{
#ifdef _DEBUG
  nodeToLink = 0;
#endif

#ifdef _KTB_CONSTR_STATS
  _stats_leafNodeCount++;
  _sumLeafDepth += _currDepth;
  if (cntObjects) {
    _sumFullLeafDepth += _currDepth;
    // The count of object references in leaves
    _sumObjectRefCount += cntObjects;
    // The maximum number of object references in a leaf
    if (cntObjects > _maxObjectRefInLeaf)
      _maxObjectRefInLeaf = cntObjects;
  }
  else
    _stats_emptyLeftNodeCount++;
#endif
  
  // Alloc a single node
  SKTBNodeT *n = (SKTBNodeT*)(alloc2->New(1));
  nodeToLink = n;
  if (n == 0) {
    // we have to insert a special node that links only
    n = nodeToLink = (SKTBNodeT*)alloc2->NewLastEntry(1);
    assert(nodeToLink);
    // Allocate a new block for the next allocation
    alloc2->AllocNewBlock();
  } // if n

  n->offset = CKTBAxes::EE_Leaf;
  n->objlist = 0;

#ifdef _DEBUG_ALLOCATION  
  cout << "AllocLeaf adr = " << (void*)n << endl;
#endif
  
  // Return the node
  return n;
}

// if active node is empty, then is replaced by full leaf with
// the object list. In success returns 0, for failure returns 1.
// The object list is used as it is .. it is not copied !!
int
CKTB8BAllocMan::SetFullLeaf(SKTBNodeT *node, const ObjectContainer *objlist)
{
  assert(node);
  assert(IsLeaf_(node));

#ifdef _DEBUG_ALLOCATION  
  cout << "SetFullLeaf adr = " << (void*)node << endl;
#endif
  
  if ( (objlist == NULL) ||
       (objlist->size() == 0) ) {
    node->objlist = 0;
  }
  else {
    // Set the pointer to the list of objects
    node->objlist = (ObjectContainer *) objlist;
  }

  return 0;
}

}