/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkBSPIntersections.cxx

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.

=========================================================================*/

/*----------------------------------------------------------------------------
 Copyright (c) Sandia Corporation
 See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
----------------------------------------------------------------------------*/

#include "vtkBSPIntersections.h"
#include "vtkBSPCuts.h"
#include "vtkCell.h"
#include "vtkKdNode.h"
#include "vtkMath.h"
#include "vtkObjectFactory.h"
#include "vtkPoints.h"

#include <set>

vtkStandardNewMacro(vtkBSPIntersections);

#define REGIONCHECK(err)                                                                           \
  if (this->BuildRegionList())                                                                     \
  {                                                                                                \
    return err;                                                                                    \
  }

#define REGIONIDCHECK_RETURNERR(id, err)                                                           \
  if (this->BuildRegionList())                                                                     \
  {                                                                                                \
    return err;                                                                                    \
  }                                                                                                \
  if (((id) < 0) || ((id) >= this->NumberOfRegions))                                               \
  {                                                                                                \
    vtkErrorMacro(<< "Invalid region ID");                                                         \
    return (err);                                                                                  \
  }

//------------------------------------------------------------------------------

vtkCxxSetObjectMacro(vtkBSPIntersections, Cuts, vtkBSPCuts);

//------------------------------------------------------------------------------

// Don't use vtkSetMacro or vtkBooleanMacro on these.  They will
// update the Mtime, which is incorrect.

void vtkBSPIntersections::SetComputeIntersectionsUsingDataBounds(int c)
{
  this->ComputeIntersectionsUsingDataBounds = (c != 0);
}

void vtkBSPIntersections::ComputeIntersectionsUsingDataBoundsOn()
{
  this->ComputeIntersectionsUsingDataBounds = 1;
}

void vtkBSPIntersections::ComputeIntersectionsUsingDataBoundsOff()
{
  this->ComputeIntersectionsUsingDataBounds = 0;
}

//------------------------------------------------------------------------------
vtkBSPIntersections::vtkBSPIntersections()
{
  this->Cuts = nullptr;
  this->NumberOfRegions = 0;
  this->RegionList = nullptr;
  this->ComputeIntersectionsUsingDataBounds = 0;
  vtkMath::UninitializeBounds(this->CellBoundsCache);
}

//------------------------------------------------------------------------------
vtkBSPIntersections::~vtkBSPIntersections()
{
  this->SetCuts(nullptr);
  delete[] this->RegionList;
}
//------------------------------------------------------------------------------
int vtkBSPIntersections::BuildRegionList()
{
  if ((this->RegionList != nullptr) && (this->RegionListBuildTime > this->GetMTime()))
  {
    return 0;
  }

  delete[] this->RegionList;
  this->RegionList = nullptr;

  vtkKdNode* top = nullptr;
  if (this->Cuts)
  {
    top = this->Cuts->GetKdNodeTree();
  }

  if (!top)
  {
    return 1;
  }

  this->NumberOfRegions = vtkBSPIntersections::NumberOfLeafNodes(top);

  if (this->NumberOfRegions < 1)
  {
    vtkErrorMacro(<< "vtkBSPIntersections::BuildRegionList no cuts in vtkBSPCut object");
    return 1;
  }

  this->RegionList = new vtkKdNode*[this->NumberOfRegions];

  if (!this->RegionList)
  {
    vtkErrorMacro(<< "vtkBSPIntersections::BuildRegionList memory allocation");
    return 1;
  }

  int fail = this->SelfRegister(top);

  if (fail)
  {
    vtkErrorMacro(<< "vtkBSPIntersections::BuildRegionList bad ids in vtkBSPCut object");
    return 1;
  }

  int min = 0;
  int max = 0;

  vtkBSPIntersections::SetIDRanges(top, min, max);

  this->RegionListBuildTime.Modified();

  return 0;
}
//------------------------------------------------------------------------------
int vtkBSPIntersections::SelfRegister(vtkKdNode* kd)
{
  int fail = 0;

  if (kd->GetLeft() == nullptr)
  {
    int id = kd->GetID();

    if ((id < 0) || (id >= this->NumberOfRegions))
    {
      return 1;
    }
    this->RegionList[id] = kd;
  }
  else
  {
    fail = this->SelfRegister(kd->GetLeft());

    if (!fail)
    {
      fail = this->SelfRegister(kd->GetRight());
    }
  }

  return fail;
}
//------------------------------------------------------------------------------
int vtkBSPIntersections::NumberOfLeafNodes(vtkKdNode* kd)
{
  int nLeafNodes = 1;

  if (kd->GetLeft() != nullptr)
  {
    int numLeft = vtkBSPIntersections::NumberOfLeafNodes(kd->GetLeft());
    int numRight = vtkBSPIntersections::NumberOfLeafNodes(kd->GetRight());

    nLeafNodes = numLeft + numRight;
  }

  return nLeafNodes;
}
//------------------------------------------------------------------------------
void vtkBSPIntersections::SetIDRanges(vtkKdNode* kd, int& min, int& max)
{
  int tempMin = 0;
  int tempMax = 0;

  if (kd->GetLeft() == nullptr)
  {
    min = kd->GetID();
    max = kd->GetID();
  }
  else
  {
    vtkBSPIntersections::SetIDRanges(kd->GetLeft(), min, max);
    vtkBSPIntersections::SetIDRanges(kd->GetRight(), tempMin, tempMax);
    max = (tempMax > max) ? tempMax : max;
    min = (tempMin < min) ? tempMin : min;
  }

  kd->SetMinID(min);
  kd->SetMaxID(max);
}
//------------------------------------------------------------------------------
int vtkBSPIntersections::GetBounds(double* bounds)
{
  REGIONCHECK(1);

  this->Cuts->GetKdNodeTree()->GetBounds(bounds);

  return 0;
}
//------------------------------------------------------------------------------
int vtkBSPIntersections::GetNumberOfRegions()
{
  REGIONCHECK(0)

  return this->NumberOfRegions;
}

//------------------------------------------------------------------------------
int vtkBSPIntersections::GetRegionBounds(int regionID, double bounds[6])
{
  REGIONIDCHECK_RETURNERR(regionID, 1)

  vtkKdNode* node = this->RegionList[regionID];

  node->GetBounds(bounds);

  return 0;
}

//------------------------------------------------------------------------------
int vtkBSPIntersections::GetRegionDataBounds(int regionID, double bounds[6])
{
  REGIONIDCHECK_RETURNERR(regionID, 1)

  vtkKdNode* node = this->RegionList[regionID];

  node->GetDataBounds(bounds);

  return 0;
}

//------------------------------------------------------------------------------
//  Query functions ----------------------------------------------------
//    K-d Trees are particularly efficient with region intersection
//    queries, like finding all regions that intersect a view frustum
//
// Intersection with axis-aligned box----------------------------------
//

//------------------------------------------------------------------------------
int vtkBSPIntersections::IntersectsBox(int regionId, double* x)
{
  return this->IntersectsBox(regionId, x[0], x[1], x[2], x[3], x[4], x[5]);
}

//------------------------------------------------------------------------------
int vtkBSPIntersections::IntersectsBox(
  int regionId, double x0, double x1, double y0, double y1, double z0, double z1)
{
  REGIONIDCHECK_RETURNERR(regionId, 0);

  vtkKdNode* node = this->RegionList[regionId];

  return node->IntersectsBox(x0, x1, y0, y1, z0, z1, this->ComputeIntersectionsUsingDataBounds);
}

//------------------------------------------------------------------------------
int vtkBSPIntersections::IntersectsBox(int* ids, int len, double* x)
{
  return this->IntersectsBox(ids, len, x[0], x[1], x[2], x[3], x[4], x[5]);
}

//------------------------------------------------------------------------------
int vtkBSPIntersections::IntersectsBox(
  int* ids, int len, double x0, double x1, double y0, double y1, double z0, double z1)
{
  REGIONCHECK(0);

  int nnodes = 0;

  if (len > 0)
  {
    nnodes = this->IntersectsBox_(this->Cuts->GetKdNodeTree(), ids, len, x0, x1, y0, y1, z0, z1);
  }
  return nnodes;
}

//------------------------------------------------------------------------------
int vtkBSPIntersections::IntersectsBox_(vtkKdNode* node, int* ids, int len, double x0, double x1,
  double y0, double y1, double z0, double z1)
{
  int result, nnodes1, nnodes2, listlen;
  int* idlist;

  result = node->IntersectsBox(x0, x1, y0, y1, z0, z1, this->ComputeIntersectionsUsingDataBounds);

  if (!result)
  {
    return 0;
  }

  if (node->GetLeft() == nullptr)
  {
    ids[0] = node->GetID();
    return 1;
  }

  nnodes1 = IntersectsBox_(node->GetLeft(), ids, len, x0, x1, y0, y1, z0, z1);

  idlist = ids + nnodes1;
  listlen = len - nnodes1;

  if (listlen > 0)
  {
    nnodes2 = IntersectsBox_(node->GetRight(), idlist, listlen, x0, x1, y0, y1, z0, z1);
  }
  else
  {
    nnodes2 = 0;
  }

  return (nnodes1 + nnodes2);
}

//------------------------------------------------------------------------------
// Intersection with a sphere---------------------------------------
//
int vtkBSPIntersections::IntersectsSphere2(
  int regionId, double x, double y, double z, double rSquared)
{
  REGIONIDCHECK_RETURNERR(regionId, 0);

  vtkKdNode* node = this->RegionList[regionId];

  return node->IntersectsSphere2(x, y, z, rSquared, this->ComputeIntersectionsUsingDataBounds);
}

//------------------------------------------------------------------------------
int vtkBSPIntersections::IntersectsSphere2(
  int* ids, int len, double x, double y, double z, double rSquared)
{
  REGIONCHECK(0)

  int nnodes = 0;

  if (len > 0)
  {
    nnodes = this->IntersectsSphere2_(this->Cuts->GetKdNodeTree(), ids, len, x, y, z, rSquared);
  }
  return nnodes;
}

//------------------------------------------------------------------------------
int vtkBSPIntersections::IntersectsSphere2_(
  vtkKdNode* node, int* ids, int len, double x, double y, double z, double rSquared)
{
  int result, nnodes1, nnodes2, listlen;
  int* idlist;

  result = node->IntersectsSphere2(x, y, z, rSquared, this->ComputeIntersectionsUsingDataBounds);

  if (!result)
  {
    return 0;
  }

  if (node->GetLeft() == nullptr)
  {
    ids[0] = node->GetID();
    return 1;
  }

  nnodes1 = IntersectsSphere2_(node->GetLeft(), ids, len, x, y, z, rSquared);

  idlist = ids + nnodes1;
  listlen = len - nnodes1;

  if (listlen > 0)
  {
    nnodes2 = IntersectsSphere2_(node->GetRight(), idlist, listlen, x, y, z, rSquared);
  }
  else
  {
    nnodes2 = 0;
  }

  return (nnodes1 + nnodes2);
}

//------------------------------------------------------------------------------
// Intersection with arbitrary vtkCell -----------------------------
//

//------------------------------------------------------------------------------
int vtkBSPIntersections::IntersectsCell(int regionId, vtkCell* cell, int cellRegion)
{
  REGIONIDCHECK_RETURNERR(regionId, 0);

  vtkKdNode* node = this->RegionList[regionId];

  return node->IntersectsCell(cell, this->ComputeIntersectionsUsingDataBounds, cellRegion);
}
//------------------------------------------------------------------------------
void vtkBSPIntersections::SetCellBounds(vtkCell* cell, double* bounds)
{
  vtkPoints* pts = cell->GetPoints();
  pts->Modified(); // VTK bug - so bounds will be re-calculated
  pts->GetBounds(bounds);
}
//------------------------------------------------------------------------------
int vtkBSPIntersections::IntersectsCell(int* ids, int len, vtkCell* cell, int cellRegion)
{
  REGIONCHECK(0)

  vtkBSPIntersections::SetCellBounds(cell, this->CellBoundsCache);

  return this->IntersectsCell_(this->Cuts->GetKdNodeTree(), ids, len, cell, cellRegion);
}
//------------------------------------------------------------------------------
int vtkBSPIntersections::IntersectsCell_(
  vtkKdNode* node, int* ids, int len, vtkCell* cell, int cellRegion)
{
  int result, nnodes1, nnodes2, listlen, intersects;
  int* idlist;

  intersects = node->IntersectsCell(
    cell, this->ComputeIntersectionsUsingDataBounds, cellRegion, this->CellBoundsCache);

  if (intersects)
  {
    if (node->GetLeft())
    {
      nnodes1 = this->IntersectsCell_(node->GetLeft(), ids, len, cell, cellRegion);

      idlist = ids + nnodes1;
      listlen = len - nnodes1;

      if (listlen > 0)
      {
        nnodes2 = this->IntersectsCell_(node->GetRight(), idlist, listlen, cell, cellRegion);
      }
      else
      {
        nnodes2 = 0;
      }

      result = nnodes1 + nnodes2;
    }
    else
    {
      ids[0] = node->GetID(); // leaf node (spatial region)

      result = 1;
    }
  }
  else
  {
    result = 0;
  }

  return result;
}

//------------------------------------------------------------------------------
void vtkBSPIntersections::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os, indent);

  os << indent << "Cuts: ";
  if (this->Cuts)
  {
    this->Cuts->PrintSelf(os << endl, indent.GetNextIndent());
  }
  else
  {
    os << "(none)" << endl;
  }
  os << indent << "NumberOfRegions: " << this->NumberOfRegions << endl;
  os << indent << "RegionList: " << this->RegionList << endl;
  os << indent << "RegionListBuildTime: " << this->RegionListBuildTime << endl;
  os << indent
     << "ComputeIntersectionsUsingDataBounds: " << this->ComputeIntersectionsUsingDataBounds
     << endl;
  double* d = this->CellBoundsCache;
  os << indent << "CellBoundsCache " << d[0] << " " << d[1] << " " << d[2] << " " << d[3] << " "
     << d[4] << " " << d[5] << " " << endl;
}