VTK  9.1.0
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=========================================================================*/
56#ifndef vtkCellTreeLocator_h
57#define vtkCellTreeLocator_h
58
60#include "vtkFiltersGeneralModule.h" // For export macro
61#include <vector> // Needed for internal class
62
63class vtkCellPointTraversal;
64class vtkIdTypeArray;
65class vtkCellArray;
66
67class VTKFILTERSGENERAL_EXPORT vtkCellTreeLocator : public vtkAbstractCellLocator
68{
69public:
70 class vtkCellTree;
71 class vtkCellTreeNode;
72
74 void PrintSelf(ostream& os, vtkIndent indent) override;
75
82
87 vtkIdType FindCell(double pos[3], double vtkNotUsed(tol2), vtkGenericCell* cell,
88 double pcoords[3], double* weights) override;
89
94 int IntersectWithLine(const double a0[3], const double a1[3], double tol, double& t, double x[3],
95 double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
96
102 void FindCellsWithinBounds(double* bbox, vtkIdList* cells) override;
103
104 /*
105 if the borland compiler is ever removed, we can use these declarations
106 instead of reimplementaing the calls in this subclass
107 using vtkAbstractCellLocator::IntersectWithLine;
108 using vtkAbstractCellLocator::FindClosestPoint;
109 using vtkAbstractCellLocator::FindClosestPointWithinRadius;
110 */
111
115 int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
116 double pcoords[3], int& subId) override
117 {
118 return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
119 }
120
127 int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
128 double pcoords[3], int& subId, vtkIdType& cellId) override;
129
134 const double p1[3], const double p2[3], vtkPoints* points, vtkIdList* cellIds) override
135 {
136 return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
137 }
138
142 vtkIdType FindCell(double x[3]) override { return this->Superclass::FindCell(x); }
143
145
148 void FreeSearchStructure() override;
149 void GenerateRepresentation(int level, vtkPolyData* pd) override;
150 virtual void BuildLocatorInternal();
151 virtual void BuildLocatorIfNeeded();
152 virtual void ForceBuildLocator();
153 void BuildLocator() override;
155
157
161 class VTKFILTERSGENERAL_EXPORT vtkCellTree
162 {
163 public:
164 std::vector<vtkCellTreeNode> Nodes;
165 std::vector<unsigned int> Leaves;
166 friend class vtkCellPointTraversal;
167 friend class vtkCellTreeNode;
168 friend class vtkCellTreeBuilder;
170
171 public:
172 float DataBBox[6]; // This store the bounding values of the dataset
173 };
174
185 class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
186 {
187 public:
188 protected:
189 unsigned int Index;
190 float LeftMax; // left max value
191 float RightMin; // right min value
192
193 unsigned int Sz; // size
194 unsigned int St; // start
195
196 friend class vtkCellTree;
197 friend class vtkCellPointTraversal;
198 friend class vtkCellTreeBuilder;
199
200 public:
201 void MakeNode(unsigned int left, unsigned int d, float b[2]);
202 void SetChildren(unsigned int left);
203 bool IsNode() const;
204 unsigned int GetLeftChildIndex() const;
205 unsigned int GetRightChildIndex() const;
206 unsigned int GetDimension() const;
207 const float& GetLeftMaxValue() const;
208 const float& GetRightMinValue() const;
209 void MakeLeaf(unsigned int start, unsigned int size);
210 bool IsLeaf() const;
211 unsigned int Start() const;
212 unsigned int Size() const;
213 };
214
215protected:
218
219 // Test ray against node BBox : clip t values to extremes
220 bool RayMinMaxT(const double origin[3], const double dir[3], double& rTmin, double& rTmax);
221
222 bool RayMinMaxT(const double bounds[6], const double origin[3], const double dir[3],
223 double& rTmin, double& rTmax);
224
225 int getDominantAxis(const double dir[3]);
226
227 // Order nodes as near/far relative to ray
228 void Classify(const double origin[3], const double dir[3], double& rDist, vtkCellTreeNode*& near,
229 vtkCellTreeNode*& mid, vtkCellTreeNode*& far, int& mustCheck);
230
231 // From vtkModifiedBSPTRee
232 // We provide a function which does the cell/ray test so that
233 // it can be overridden by subclasses to perform special treatment
234 // (Example : Particles stored in tree, have no dimension, so we must
235 // override the cell test to return a value based on some particle size
236 virtual int IntersectCellInternal(vtkIdType cell_ID, const double p1[3], const double p2[3],
237 const double tol, double& t, double ipt[3], double pcoords[3], int& subId);
238
240
242
243 friend class vtkCellPointTraversal;
244 friend class vtkCellTreeNode;
245 friend class vtkCellTreeBuilder;
246
247private:
248 vtkCellTreeLocator(const vtkCellTreeLocator&) = delete;
249 void operator=(const vtkCellTreeLocator&) = delete;
250};
251
252#endif
an abstract base class for locators which find cells
object to represent cell connectivity
Definition: vtkCellArray.h:290
This class is the basic building block of the cell tree.
void MakeLeaf(unsigned int start, unsigned int size)
unsigned int GetRightChildIndex() 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])
const float & GetLeftMaxValue() const
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.
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.
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()
Satisfy vtkLocator abstract interface.
vtkIdType FindCell(double x[3]) override
reimplemented from vtkAbstractCellLocator to support bad compilers
virtual void ForceBuildLocator()
Satisfy vtkLocator abstract interface.
~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()
Satisfy vtkLocator abstract interface.
vtkIdType FindCell(double pos[3], double vtkNotUsed(tol2), vtkGenericCell *cell, double pcoords[3], double *weights) override
Test a point to find if it is inside a cell.
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
Satisfy vtkLocator abstract interface.
void BuildLocator() override
Satisfy vtkLocator abstract interface.
static vtkCellTreeLocator * New()
Constructor sets the maximum number of cells in a leaf to 8 and number of buckets to 5.
provides thread-safe access to cells
list of point or cell ids
Definition: vtkIdList.h:140
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition: vtkIndent.h:113
represent and manipulate 3D points
Definition: vtkPoints.h:143
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:195
int vtkIdType
Definition: vtkType.h:332