VTK
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=========================================================================*/
40#ifndef vtkCellTreeLocator_h
41#define vtkCellTreeLocator_h
42
43#include "vtkFiltersGeneralModule.h" // For export macro
45#include <vector> // Needed for internal class
46
47class vtkCellPointTraversal;
48class vtkIdTypeArray;
49class vtkCellArray;
50
51class VTKFILTERSGENERAL_EXPORT vtkCellTreeLocator : public vtkAbstractCellLocator
52{
53 public:
54 class vtkCellTree;
55 class vtkCellTreeNode;
56
58 void PrintSelf(ostream& os, vtkIndent indent) VTK_OVERRIDE;
59
65
70 vtkIdType FindCell(double pos[3], double vtkNotUsed, vtkGenericCell *cell, double pcoords[3],
71 double* weights ) VTK_OVERRIDE;
72
77 int IntersectWithLine(double a0[3], double a1[3], double tol,
78 double& t, double x[3], double pcoords[3],
79 int &subId, vtkIdType &cellId,
80 vtkGenericCell *cell) VTK_OVERRIDE;
81
87 void FindCellsWithinBounds(double *bbox, vtkIdList *cells) VTK_OVERRIDE;
88
89 /*
90 if the borland compiler is ever removed, we can use these declarations
91 instead of reimplementaing the calls in this subclass
92 using vtkAbstractCellLocator::IntersectWithLine;
93 using vtkAbstractCellLocator::FindClosestPoint;
94 using vtkAbstractCellLocator::FindClosestPointWithinRadius;
95 */
96
101 double p1[3], double p2[3], double tol, double& t, double x[3],
102 double pcoords[3], int &subId) VTK_OVERRIDE
103 {
104 return this->Superclass::IntersectWithLine(p1, p2, tol, t, x, pcoords, subId);
105 }
106
114 double p1[3], double p2[3], double tol, double &t, double x[3],
115 double pcoords[3], int &subId, vtkIdType &cellId) VTK_OVERRIDE;
116
121 const double p1[3], const double p2[3],
122 vtkPoints *points, vtkIdList *cellIds) VTK_OVERRIDE
123 {
124 return this->Superclass::IntersectWithLine(p1, p2, points, cellIds);
125 }
126
130 vtkIdType FindCell(double x[3]) VTK_OVERRIDE
131 { return this->Superclass::FindCell(x); }
132
134
137 void FreeSearchStructure() VTK_OVERRIDE;
138 void GenerateRepresentation(int level, vtkPolyData *pd) VTK_OVERRIDE;
139 virtual void BuildLocatorInternal();
140 virtual void BuildLocatorIfNeeded();
141 virtual void ForceBuildLocator();
142 void BuildLocator() VTK_OVERRIDE;
144
146
150 class VTKFILTERSGENERAL_EXPORT vtkCellTree
151 {
152 public:
153 std::vector<vtkCellTreeNode> Nodes;
154 std::vector<unsigned int> Leaves;
155 friend class vtkCellPointTraversal;
156 friend class vtkCellTreeNode;
157 friend class vtkCellTreeBuilder;
159
160 public:
161 float DataBBox[6]; // This store the bounding values of the dataset
162 };
163
174 class VTKFILTERSGENERAL_EXPORT vtkCellTreeNode
175 {
176 public:
177
178 protected:
179 unsigned int Index;
180 float LeftMax; // left max value
181 float RightMin; // right min value
182
183 unsigned int Sz; // size
184 unsigned int St; // start
185
186 friend class vtkCellTree;
187 friend class vtkCellPointTraversal;
188 friend class vtkCellTreeBuilder;
189
190 public:
191 void MakeNode( unsigned int left, unsigned int d, float b[2] );
192 void SetChildren( unsigned int left );
193 bool IsNode() const;
194 unsigned int GetLeftChildIndex() const;
195 unsigned int GetRightChildIndex() const;
196 unsigned int GetDimension() const;
197 const float& GetLeftMaxValue() const;
198 const float& GetRightMinValue() const;
199 void MakeLeaf( unsigned int start, unsigned int size );
200 bool IsLeaf() const;
201 unsigned int Start() const;
202 unsigned int Size() const;
203 };
204
205protected:
207 ~vtkCellTreeLocator() VTK_OVERRIDE;
208
209 // Test ray against node BBox : clip t values to extremes
210 bool RayMinMaxT(const double origin[3],
211 const double dir[3],
212 double &rTmin,
213 double &rTmax);
214
215 bool RayMinMaxT(const double bounds[6],
216 const double origin[3],
217 const double dir[3],
218 double &rTmin,
219 double &rTmax);
220
221 int getDominantAxis(const double dir[3]);
222
223 // Order nodes as near/far relative to ray
224 void Classify(const double origin[3],
225 const double dir[3],
226 double &rDist,
227 vtkCellTreeNode *&near, vtkCellTreeNode *&mid,
228 vtkCellTreeNode *&far, int &mustCheck);
229
230 // From vtkModifiedBSPTRee
231 // We provide a function which does the cell/ray test so that
232 // it can be overriden by subclasses to perform special treatment
233 // (Example : Particles stored in tree, have no dimension, so we must
234 // override the cell test to return a value based on some particle size
235 virtual int IntersectCellInternal( vtkIdType cell_ID, const double p1[3],
236 const double p2[3],
237 const double tol,
238 double &t,
239 double ipt[3],
240 double pcoords[3],
241 int &subId);
242
243
244 int NumberOfBuckets;
245
247
248 friend class vtkCellPointTraversal;
249 friend class vtkCellTreeNode;
250 friend class vtkCellTreeBuilder;
251
252private:
253 vtkCellTreeLocator(const vtkCellTreeLocator&) VTK_DELETE_FUNCTION;
254 void operator=(const vtkCellTreeLocator&) VTK_DELETE_FUNCTION;
255};
256
257#endif
an abstract base class for locators which find cells
object to represent cell connectivity
Definition: vtkCellArray.h:51
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(double a0[3], 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.
int IntersectWithLine(double p1[3], double p2[3], double tol, double &t, double x[3], double pcoords[3], int &subId) override
reimplemented from vtkAbstractCellLocator to support bad compilers
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
vtkIdType FindCell(double x[3]) override
reimplemented from vtkAbstractCellLocator to support bad compilers
~vtkCellTreeLocator() override
int IntersectWithLine(double p1[3], 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 FreeSearchStructure() 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:37
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition: vtkIndent.h:40
represent and manipulate 3D points
Definition: vtkPoints.h:40
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:86
@ points
Definition: vtkX3D.h:446
@ level
Definition: vtkX3D.h:395
@ dir
Definition: vtkX3D.h:324
@ size
Definition: vtkX3D.h:253
int vtkIdType
Definition: vtkType.h:287