vtkOBBTree.h

Go to the documentation of this file.

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

#include "vtkAbstractCellLocator.h"
#include "vtkFiltersGeneralModule.h" // For export macro

VTK_ABI_NAMESPACE_BEGIN
class vtkMatrix4x4;

// Special class defines node for the OBB tree
class VTKFILTERSGENERAL_EXPORT vtkOBBNode
{ //;prevent man page generation
public:
  vtkOBBNode();
  ~vtkOBBNode();

  double Corner[3];   // center point of this node
  double Axes[3][3];  // the axes defining the OBB - ordered from long->short
  vtkOBBNode* Parent; // parent node; nullptr if root
  vtkOBBNode** Kids;  // two children of this node; nullptr if leaf
  vtkIdList* Cells;   // list of cells in node
  void DebugPrintTree(int level, double* leaf_vol, int* minCells, int* maxCells);

private:
  vtkOBBNode(const vtkOBBNode& other) = delete;
  vtkOBBNode& operator=(const vtkOBBNode& rhs) = delete;
};

class VTKFILTERSGENERAL_EXPORT vtkOBBTree : public vtkAbstractCellLocator
{
public:

  vtkTypeMacro(vtkOBBTree, vtkAbstractCellLocator);
  void PrintSelf(ostream& os, vtkIndent indent) override;

  static vtkOBBTree* New();

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

  int IntersectWithLine(const double a0[3], const double a1[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;

  static void ComputeOBB(
    vtkPoints* pts, double corner[3], double max[3], double mid[3], double min[3], double size[3]);

  void ComputeOBB(vtkDataSet* input, double corner[3], double max[3], double mid[3], double min[3],
    double size[3]);

  int InsideOrOutside(const double point[3], double tol = 0);

  int DisjointOBBNodes(
    vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* XformBtoA, double tol = 0);

  int LineIntersectsNode(vtkOBBNode* pA, const double b0[3], const double b1[3], double tol = 0);

  int TriangleIntersectsNode(vtkOBBNode* pA, double p0[3], double p1[3], double p2[3],
    vtkMatrix4x4* XformBtoA, double tol = 0);

  int IntersectWithOBBTree(vtkOBBTree* OBBTreeB, vtkMatrix4x4* XformBtoA,
    int (*function)(vtkOBBNode* nodeA, vtkOBBNode* nodeB, vtkMatrix4x4* Xform, void* arg),
    void* data_arg, double tol = 0);


  void FreeSearchStructure() override;
  void BuildLocator() override;
  void ForceBuildLocator() override;

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

protected:
  vtkOBBTree();
  ~vtkOBBTree() override;

  void BuildLocatorInternal() override;

  // Compute an OBB from the list of cells given.  This used to be
  // public but should not have been.  A public call has been added
  // so that the functionality can be accessed.
  void ComputeOBB(vtkIdList* cells, double corner[3], double max[3], double mid[3], double min[3],
    double size[3]);

  vtkOBBNode* Tree;
  void BuildTree(vtkIdList* cells, vtkOBBNode* parent, int level);
  vtkPoints* PointsList;
  int* InsertedPoints;
  int OBBCount;

  void DeleteTree(vtkOBBNode* OBBptr);
  void GeneratePolygons(
    vtkOBBNode* OBBptr, int level, int repLevel, vtkPoints* pts, vtkCellArray* polys);

private:
  vtkOBBTree(const vtkOBBTree&) = delete;
  void operator=(const vtkOBBTree&) = delete;
};

VTK_ABI_NAMESPACE_END
#endif