Method BreadthFirstDivide

Filters/Parallel/vtkPKdTree.cxx:628–703

  } while (false)

int vtkPKdTree::BreadthFirstDivide(double* volBounds)
{
  SCOPETIMER("BreadthFirstDivide");

  int returnVal = 0;

  std::queue<vtkNodeInfo> Queue;

  if (this->AllocateDoubleBuffer())
  {
    VTKERROR("memory allocation for double buffering");
    return 1;
  }

  this->AllocateSelectBuffer();

  vtkKdNode* kd = this->Top = vtkKdNode::New();

  kd->SetBounds(volBounds[0], volBounds[1], volBounds[2], volBounds[3], volBounds[4], volBounds[5]);

  kd->SetNumberOfPoints(this->TotalNumCells);

  kd->SetDataBounds(
    volBounds[0], volBounds[1], volBounds[2], volBounds[3], volBounds[4], volBounds[5]);

  int midpt = this->DivideRegion(kd, 0, 0, 0x00000001);

  if (midpt >= 0)
  {
    ENQUEUE(kd->GetLeft(), 0, 1, 0x00000002);
    ENQUEUE(kd->GetRight(), midpt, 1, 0x00000003);
  }
  else if (midpt < -1)
  {
    this->FreeSelectBuffer();
    this->FreeDoubleBuffer();

    return 1;
  }

  while (!Queue.empty())
  {
    vtkNodeInfo info = Queue.front();
    Queue.pop();

    kd = info->kd;
    int L = info->L;
    int level = info->level;
    int tag = info->tag;

    midpt = this->DivideRegion(kd, L, level, tag);

    if (midpt >= 0)
    {
      ENQUEUE(kd->GetLeft(), L, level + 1, tag << 1);

      ENQUEUE(kd->GetRight(), midpt, level + 1, (tag << 1) | 1);
    }