VTK  9.0.2
vtkCellTreeLocator.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkCellTreeLocator.h
5 
6  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7  All rights reserved.
8  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9 
10  This software is distributed WITHOUT ANY WARRANTY; without even
11  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12  PURPOSE. See the above copyright notice for more information.
13 
14 =========================================================================*/
37 #ifndef vtkCellTreeLocator_h
38 #define vtkCellTreeLocator_h
39 
40 #include "vtkAbstractCellLocator.h"
41 #include "vtkFiltersGeneralModule.h" // For export macro
42 #include <vector> // Needed for internal class
43 
44 class vtkCellPointTraversal;
45 class vtkIdTypeArray;
46 class vtkCellArray;
47 
48 class VTKFILTERSGENERAL_EXPORT vtkCellTreeLocator : public vtkAbstractCellLocator
49 {
50 public:
51  class vtkCellTree;
52  class vtkCellTreeNode;
53 
55  void PrintSelf(ostream& os, vtkIndent indent) override;
56 
63 
68  vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell* cell, double pcoords[3],
69  double* weights) override;
70 
75  int IntersectWithLine(const double a0[3], const double a1[3], double tol, double& t, double x[3],
76  double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
77 
83  void FindCellsWithinBounds(double* bbox, vtkIdList* cells) override;
84 
85  /*
86  if the borland compiler is ever removed, we can use these declarations
87  instead of reimplementaing the calls in this subclass
88  using vtkAbstractCellLocator::IntersectWithLine;
89  using vtkAbstractCellLocator::FindClosestPoint;
90  using vtkAbstractCellLocator::FindClosestPointWithinRadius;
91  */
92 
96  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
97  double pcoords[3], int& subId) override
98  {
99  return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
100  }
101 
108  int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
109  double pcoords[3], int& subId, vtkIdType& cellId) override;
110 
115  const double p1[3], const double p2[3], vtkPoints* points, vtkIdList* cellIds) override
116  {
117  return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
118  }
119 
123  vtkIdType FindCell(double x[3]) override { return this->Superclass::FindCell(x); }
124 
126 
129  void FreeSearchStructure() override;
130  void GenerateRepresentation(int level, vtkPolyData* pd) override;
131  virtual void BuildLocatorInternal();
132  virtual void BuildLocatorIfNeeded();
133  virtual void ForceBuildLocator();
134  void BuildLocator() override;
136 
138 
142  class VTKFILTERSGENERAL_EXPORT vtkCellTree
143  {
144  public:
145  std::vector<vtkCellTreeNode> Nodes;
146  std::vector<unsigned int> Leaves;
147  friend class vtkCellPointTraversal;
148  friend class vtkCellTreeNode;
149  friend class vtkCellTreeBuilder;
151 
152  public:
153  float DataBBox[6]; // This store the bounding values of the dataset
154  };
155 
166  class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
167  {
168  public:
169  protected:
170  unsigned int Index;
171  float LeftMax; // left max value
172  float RightMin; // right min value
173 
174  unsigned int Sz; // size
175  unsigned int St; // start
176 
177  friend class vtkCellTree;
178  friend class vtkCellPointTraversal;
179  friend class vtkCellTreeBuilder;
180 
181  public:
182  void MakeNode(unsigned int left, unsigned int d, float b[2]);
183  void SetChildren(unsigned int left);
184  bool IsNode() const;
185  unsigned int GetLeftChildIndex() const;
186  unsigned int GetRightChildIndex() const;
187  unsigned int GetDimension() const;
188  const float& GetLeftMaxValue() const;
189  const float& GetRightMinValue() const;
190  void MakeLeaf(unsigned int start, unsigned int size);
191  bool IsLeaf() const;
192  unsigned int Start() const;
193  unsigned int Size() const;
194  };
195 
196 protected:
199 
200  // Test ray against node BBox : clip t values to extremes
201  bool RayMinMaxT(const double origin[3], const double dir[3], double& rTmin, double& rTmax);
202 
203  bool RayMinMaxT(const double bounds[6], const double origin[3], const double dir[3],
204  double& rTmin, double& rTmax);
205 
206  int getDominantAxis(const double dir[3]);
207 
208  // Order nodes as near/far relative to ray
209  void Classify(const double origin[3], const double dir[3], double& rDist, vtkCellTreeNode*& near,
210  vtkCellTreeNode*& mid, vtkCellTreeNode*& far, int& mustCheck);
211 
212  // From vtkModifiedBSPTRee
213  // We provide a function which does the cell/ray test so that
214  // it can be overridden by subclasses to perform special treatment
215  // (Example : Particles stored in tree, have no dimension, so we must
216  // override the cell test to return a value based on some particle size
217  virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
218  const double tol, double& t, double ipt[3], double pcoords[3], int& subId);
219 
221 
223 
224  friend class vtkCellPointTraversal;
225  friend class vtkCellTreeNode;
226  friend class vtkCellTreeBuilder;
227 
228 private:
229  vtkCellTreeLocator(const vtkCellTreeLocator&) = delete;
230  void operator=(const vtkCellTreeLocator&) = delete;
231 };
232 
233 #endif
an abstract base class for locators which find cells
object to represent cell connectivity
Definition: vtkCellArray.h:180
This class is the basic building block of the cell tree.
void MakeLeaf(unsigned int start, unsigned int size)
unsigned int GetRightChildIndex() const
const float & GetLeftMaxValue() const
unsigned int GetDimension() const
const float & GetRightMinValue() const
void SetChildren(unsigned int left)
void MakeNode(unsigned int left, unsigned int d, float b[2])
unsigned int GetLeftChildIndex() const
Internal classes made public to allow subclasses to create customized some traversal algorithms.
std::vector< unsigned int > Leaves
std::vector< vtkCellTreeNode > Nodes
This class implements the data structures, construction algorithms for fast cell location presented i...
void FindCellsWithinBounds(double *bbox, vtkIdList *cells) override
Return a list of unique cell ids inside of a given bounding box.
int IntersectWithLine(const double p1[3], const double p2[3], vtkPoints *points, vtkIdList *cellIds) override
reimplemented from vtkAbstractCellLocator to support bad compilers
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
Return intersection point (if any) AND the cell which was intersected by the finite line.
vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell *cell, double pcoords[3], double *weights) override
Test a point to find if it is inside a cell.
bool RayMinMaxT(const double bounds[6], const double origin[3], const double dir[3], double &rTmin, double &rTmax)
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
static vtkCellTreeLocator * New()
Constructor sets the maximum number of cells in a leaf to 8 and number of buckets to 5.
int IntersectWithLine(const double p1[3], const double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId) override
reimplemented from vtkAbstractCellLocator to support bad compilers
int getDominantAxis(const double dir[3])
void Classify(const double origin[3], const double dir[3], double &rDist, vtkCellTreeNode *&near, vtkCellTreeNode *&mid, vtkCellTreeNode *&far, int &mustCheck)
virtual void BuildLocatorIfNeeded()
vtkIdType FindCell(double x[3]) override
reimplemented from vtkAbstractCellLocator to support bad compilers
virtual void ForceBuildLocator()
~vtkCellTreeLocator() override
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)
bool RayMinMaxT(const double origin[3], const double dir[3], double &rTmin, double &rTmax)
virtual void BuildLocatorInternal()
void FreeSearchStructure() override
Satisfy vtkLocator abstract interface.
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
Return intersection point (if any) AND the cell which was intersected by the finite line.
void GenerateRepresentation(int level, vtkPolyData *pd) override
Method to build a representation at a particular level.
void BuildLocator() override
Build the locator from the input dataset.
provides thread-safe access to cells
list of point or cell ids
Definition: vtkIdList.h:31
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition: vtkIndent.h:34
represent and manipulate 3D points
Definition: vtkPoints.h:34
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:85
@ points
Definition: vtkX3D.h:452
@ level
Definition: vtkX3D.h:401
@ dir
Definition: vtkX3D.h:330
@ size
Definition: vtkX3D.h:259
int vtkIdType
Definition: vtkType.h:338