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=========================================================================*/
37#ifndef vtkCellTreeLocator_h
38#define vtkCellTreeLocator_h
39
41#include "vtkFiltersGeneralModule.h" // For export macro
42#include <vector> // Needed for internal class
43
44class vtkCellPointTraversal;
45class vtkIdTypeArray;
46class vtkCellArray;
47
48class VTKFILTERSGENERAL_EXPORT vtkCellTreeLocator : public vtkAbstractCellLocator
49{
50public:
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(tol2), vtkGenericCell* cell,
69 double pcoords[3], 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
196protected:
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
228private:
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:181
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: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:86
int vtkIdType
Definition: vtkType.h:332