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 "vtkFiltersFlowPathsModule.h" // For export macro
#include "vtkAbstractCellLocator.h"
#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::IntersectWithLine;
  using vtkAbstractCellLocator::FindCell;

  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