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 "vtkAbstractCellLocator.h"
#include "vtkFiltersGeneralModule.h" // For export macro
#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(tol2), 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