vtkCellTreeLocator.h

Go to the documentation of this file.

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

  Program:   Visualization Toolkit
  Module:    vtkCellTreeLocator.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.

=========================================================================*/
#ifndef vtkCellTreeLocator_h
#define vtkCellTreeLocator_h

#include "vtkFiltersGeneralModule.h" // For export macro
#include "vtkAbstractCellLocator.h"
#include <vector> // Needed for internal class

class vtkCellPointTraversal;
class vtkIdTypeArray;
class vtkCellArray;

class VTKFILTERSGENERAL_EXPORT vtkCellTreeLocator : public vtkAbstractCellLocator
{
  public:
    class vtkCellTree;
    class vtkCellTreeNode;

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

    static vtkCellTreeLocator *New();

    vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell *cell,  double pcoords[3],
                       double* weights ) override;

    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;

    void FindCellsWithinBounds(double *bbox, vtkIdList *cells) override;

    /*
      if the borland compiler is ever removed, we can use these declarations
      instead of reimplementaing the calls in this subclass
      using vtkAbstractCellLocator::IntersectWithLine;
      using vtkAbstractCellLocator::FindClosestPoint;
      using vtkAbstractCellLocator::FindClosestPointWithinRadius;
    */

    int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
      double pcoords[3], int &subId) override
    {
      return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
    }

    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],
      vtkPoints *points, vtkIdList *cellIds) override
    {
      return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
    }

    vtkIdType FindCell(double x[3]) override
    { return this->Superclass::FindCell(x); }


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


    class VTKFILTERSGENERAL_EXPORT vtkCellTree
    {
      public:
        std::vector<vtkCellTreeNode>  Nodes;
        std::vector<unsigned int> Leaves;
        friend class vtkCellPointTraversal;
        friend class vtkCellTreeNode;
        friend class vtkCellTreeBuilder;

      public:
        float DataBBox[6]; // This store the bounding values of the dataset
    };

    class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
    {
      public:

      protected:
        unsigned int Index;
        float LeftMax;  // left max value
        float RightMin;  // right min value

        unsigned int Sz; // size
        unsigned int St; // start

        friend class vtkCellTree;
        friend class vtkCellPointTraversal;
        friend class vtkCellTreeBuilder;

      public:
        void MakeNode( unsigned int left, unsigned int d, float b[2] );
        void SetChildren( unsigned int left );
        bool IsNode() const;
        unsigned int GetLeftChildIndex() const;
        unsigned int GetRightChildIndex() const;
        unsigned int GetDimension() const;
        const float& GetLeftMaxValue() const;
        const float& GetRightMinValue() const;
        void MakeLeaf( unsigned int start, unsigned int size );
        bool IsLeaf() const;
        unsigned int Start() const;
        unsigned int Size() const;
    };

protected:
     vtkCellTreeLocator();
    ~vtkCellTreeLocator() override;

   // Test ray against node BBox : clip t values to extremes
  bool RayMinMaxT(const double origin[3],
    const double dir[3],
    double &rTmin,
    double &rTmax);

  bool RayMinMaxT(const double bounds[6],
    const double origin[3],
    const double dir[3],
    double &rTmin,
    double &rTmax);

  int getDominantAxis(const double dir[3]);

  // Order nodes as near/far relative to ray
  void Classify(const double origin[3],
    const double dir[3],
    double &rDist,
    vtkCellTreeNode *&near, vtkCellTreeNode *&mid,
    vtkCellTreeNode *&far, int &mustCheck);

  // From vtkModifiedBSPTRee
  // 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);


    int NumberOfBuckets;

    vtkCellTree* Tree;

    friend class vtkCellPointTraversal;
    friend class vtkCellTreeNode;
    friend class vtkCellTreeBuilder;

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

#endif