vtkModifiedBSPTree.h

Go to the documentation of this file.

/*=========================================================================
 
  Program:   Visualization Toolkit
  Module:    vtkModifiedBSPTree.h
 
  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.
 
=========================================================================*/
 
/*=========================================================================
  This code is derived from an earlier work and is distributed
  with permission from, and thanks to
 
  ------------------------------------------
  Copyright (C) 1997-2000 John Biddiscombe
  Rutherford Appleton Laboratory,
  Chilton, Oxon, England
  ------------------------------------------
  Copyright (C) 2000-2004 John Biddiscombe
  Skipping Mouse Software Ltd,
  Blewbury, England
  ------------------------------------------
  Copyright (C) 2004-2009 John Biddiscombe
  CSCS - Swiss National Supercomputing Centre
  Galleria 2 - Via Cantonale
  CH-6928 Manno, Switzerland
  ------------------------------------
=========================================================================*/
#ifndef vtkModifiedBSPTree_h
#define vtkModifiedBSPTree_h
 
#include "vtkAbstractCellLocator.h"
#include "vtkFiltersFlowPathsModule.h" // For export macro
#include "vtkSmartPointer.h"           // required because it is nice
 
class Sorted_cell_extents_Lists;
class BSPNode;
class vtkGenericCell;
class vtkIdList;
class vtkIdListCollection;
 
class VTKFILTERSFLOWPATHS_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator
{
public:
 
  vtkTypeMacro(vtkModifiedBSPTree, vtkAbstractCellLocator);
  void PrintSelf(ostream& os, vtkIndent indent) override;
 
  static vtkModifiedBSPTree* New();
 
  // Re-use any superclass signatures that we don't override.
  using vtkAbstractCellLocator::FindCell;
  using vtkAbstractCellLocator::IntersectWithLine;
 
  void FreeSearchStructure() override;
 
  void BuildLocator() override;
 
  void GenerateRepresentation(int level, vtkPolyData* pd) override;
 
  virtual void GenerateRepresentationLeafs(vtkPolyData* pd);
 
  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
    double pcoords[3], int& subId, vtkIdType& cellId) override;
 
  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
    double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
 
  virtual int IntersectWithLine(const double p1[3], const double p2[3], const double tol,
    vtkPoints* points, vtkIdList* cellIds);
 
  vtkIdType FindCell(
    double x[3], double tol2, vtkGenericCell* GenCell, double pcoords[3], double* weights) override;
 
  bool InsideCellBounds(double x[3], vtkIdType cell_ID) override;
 
  vtkIdListCollection* GetLeafNodeCellInformation();
 
protected:
  vtkModifiedBSPTree();
  ~vtkModifiedBSPTree() override;
  //
  BSPNode* mRoot; // bounding box root node
  int npn;
  int nln;
  int tot_depth;
 
  //
  // The main subdivision routine
  void Subdivide(BSPNode* node, Sorted_cell_extents_Lists* lists, vtkDataSet* dataSet,
    vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int& MaxDepth);
 
  // We provide a function which does the cell/ray test so that
  // it can be overridden by subclasses to perform special treatment
  // (Example : Particles stored in tree, have no dimension, so we must
  // override the cell test to return a value based on some particle size
  virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
    const double tol, double& t, double ipt[3], double pcoords[3], int& subId);
 
  void BuildLocatorIfNeeded();
  void ForceBuildLocator();
  void BuildLocatorInternal();
 
private:
  vtkModifiedBSPTree(const vtkModifiedBSPTree&) = delete;
  void operator=(const vtkModifiedBSPTree&) = delete;
};
 
// BSP Node
// A BSP Node is a BBox - axis aligned etc etc
#ifndef DOXYGEN_SHOULD_SKIP_THIS
 
class BSPNode
{
public:
  // Constructor
  BSPNode(void)
  {
    mChild[0] = mChild[1] = mChild[2] = nullptr;
    for (int i = 0; i < 6; i++)
      sorted_cell_lists[i] = nullptr;
    for (int i = 0; i < 3; i++)
    {
      this->Bounds[i * 2] = VTK_FLOAT_MAX;
      this->Bounds[i * 2 + 1] = -VTK_FLOAT_MAX;
    }
  }
  // Destructor
  ~BSPNode(void)
  {
    for (int i = 0; i < 3; i++)
      delete mChild[i];
    for (int i = 0; i < 6; i++)
      delete[] sorted_cell_lists[i];
  }
  // Set min box limits
  void setMin(double minx, double miny, double minz)
  {
    this->Bounds[0] = minx;
    this->Bounds[2] = miny;
    this->Bounds[4] = minz;
  }
  // Set max box limits
  void setMax(double maxx, double maxy, double maxz)
  {
    this->Bounds[1] = maxx;
    this->Bounds[3] = maxy;
    this->Bounds[5] = maxz;
  }
  //
  bool Inside(double point[3]) const;
  // BBox
  double Bounds[6];
 
protected:
  // The child nodes of this one (if present - nullptr otherwise)
  BSPNode* mChild[3];
  // The axis we subdivide this voxel along
  int mAxis;
  // Just for reference
  int depth;
  // the number of cells in this node
  int num_cells;
  // 6 lists, sorted after the 6 dominant axes
  vtkIdType* sorted_cell_lists[6];
  // Order nodes as near/mid far relative to ray
  void Classify(const double origin[3], const double dir[3], double& rDist, BSPNode*& Near,
    BSPNode*& Mid, BSPNode*& Far) const;
  // Test ray against node BBox : clip t values to extremes
  bool RayMinMaxT(const double origin[3], const double dir[3], double& rTmin, double& rTmax) const;
  //
  friend class vtkModifiedBSPTree;
  friend class vtkParticleBoxTree;
 
public:
  static bool VTKFILTERSFLOWPATHS_EXPORT RayMinMaxT(const double bounds[6], const double origin[3],
    const double dir[3], double& rTmin, double& rTmax);
  static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
};
 
#endif /* DOXYGEN_SHOULD_SKIP_THIS */
 
#endif