vtkModifiedBSPTree.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-FileCopyrightText: Copyright (c) 1997-2009 John Biddiscombe
// SPDX-License-Identifier: BSD-3-Clause
#ifndef vtkModifiedBSPTree_h
#define vtkModifiedBSPTree_h

#include "vtkAbstractCellLocator.h"
#include "vtkFiltersFlowPathsModule.h" // For export macro
#include "vtkSmartPointer.h"           // required because it is nice

#include <vector> // For std::vector

VTK_ABI_NAMESPACE_BEGIN
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();

  // Reuse any superclass signatures that we don't override.
  using vtkAbstractCellLocator::FindCell;
  using vtkAbstractCellLocator::FindCellsAlongLine;
  using vtkAbstractCellLocator::IntersectWithLine;

  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;

  int IntersectWithLine(const double p1[3], const double p2[3], double tol, vtkPoints* points,
    vtkIdList* cellIds, vtkGenericCell* cell) override;

  vtkIdType FindCell(double x[3], double tol2, vtkGenericCell* GenCell, int& subId,
    double pcoords[3], double* weights) override;

  vtkIdListCollection* GetLeafNodeCellInformation();

  virtual void GenerateRepresentationLeafs(vtkPolyData* pd);


  void GenerateRepresentation(int level, vtkPolyData* pd) override;
  void FreeSearchStructure() override;
  void BuildLocator() override;
  void ForceBuildLocator() override;

  void ShallowCopy(vtkAbstractCellLocator* locator) override;

protected:
  vtkModifiedBSPTree();
  ~vtkModifiedBSPTree() override;

  void BuildLocatorInternal() override;
  // Flat storage for all leaf cell ID lists, allocated once during build.
  // Each leaf occupies a contiguous slice of size 6 * node->num_cells starting
  // at node->LeavesStart. Within a leaf, the 6 sorted lists are laid out as
  // [axis 0 mins | axis 0 maxs | axis 1 mins | ... | axis 2 maxs].
  std::shared_ptr<std::vector<vtkIdType>> Leaves;
  std::shared_ptr<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,
    std::vector<uint8_t>& cellPart);

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()
  {
    mChild[0] = mChild[1] = mChild[2] = 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()
  {
    for (int i = 0; i < 3; i++)
    {
      delete mChild[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 = 0;
  // Just for reference
  int depth = 0;
  // split-plane position along mAxis (parents only). Used in FindCell to
  // short-circuit the Inside() test on side children when x is clearly on
  // the opposite side of the split plane.
  double pDiv = 0;
  // the number of cells in this node
  int num_cells = 0;
  // Offset into vtkModifiedBSPTree::Leaves where this leaf's 6 sorted cell
  // lists begin. Each list has length num_cells; layout is contiguous as
  // [mins[0] | maxs[0] | mins[1] | maxs[1] | mins[2] | maxs[2]].
  vtkIdType LeavesStart = 0;
  // 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;
  friend class vtkModifiedBSPTree;

public:
  static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
};

#endif /* DOXYGEN_SHOULD_SKIP_THIS */

VTK_ABI_NAMESPACE_END
#endif