forked from Kitware/VTK
-
Notifications
You must be signed in to change notification settings - Fork 0
/
vtkCellLocator.h
223 lines (193 loc) · 8.54 KB
/
vtkCellLocator.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
/*=========================================================================
Program: Visualization Toolkit
Module: vtkCellLocator.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.
=========================================================================*/
/**
* @class vtkCellLocator
* @brief octree-based spatial search object to quickly locate cells
*
* vtkCellLocator is a spatial search object to quickly locate cells in 3D.
* vtkCellLocator uses a uniform-level octree subdivision, where each octant
* (an octant is also referred to as a bucket) carries an indication of
* whether it is empty or not, and each leaf octant carries a list of the
* cells inside of it. (An octant is not empty if it has one or more cells
* inside of it.) Typical operations are intersection with a line to return
* candidate cells, or intersection with another vtkCellLocator to return
* candidate cells.
*
* @warning
* Many other types of spatial locators have been developed, such as
* variable depth octrees and kd-trees. These are often more efficient
* for the operations described here. vtkCellLocator has been designed
* for subclassing; so these locators can be derived if necessary.
*
* @sa
* vtkLocator vtkPointLocator vtkOBBTree
*/
#ifndef vtkCellLocator_h
#define vtkCellLocator_h
#include "vtkCommonDataModelModule.h" // For export macro
#include "vtkAbstractCellLocator.h"
class vtkNeighborCells;
class VTKCOMMONDATAMODEL_EXPORT vtkCellLocator : public vtkAbstractCellLocator
{
public:
vtkTypeMacro(vtkCellLocator,vtkAbstractCellLocator);
void PrintSelf(ostream& os, vtkIndent indent) override;
/**
* Construct with automatic computation of divisions, averaging
* 25 cells per bucket.
*/
static vtkCellLocator *New();
/**
* Specify the average number of cells in each octant.
*/
void SetNumberOfCellsPerBucket(int N)
{ this->SetNumberOfCellsPerNode(N); }
int GetNumberOfCellsPerBucket()
{ return this->NumberOfCellsPerNode; }
// Re-use any superclass signatures that we don't override.
using vtkAbstractCellLocator::IntersectWithLine;
using vtkAbstractCellLocator::FindCell;
using vtkAbstractCellLocator::FindClosestPoint;
using vtkAbstractCellLocator::FindClosestPointWithinRadius;
/**
* Return intersection point (if any) AND the cell which was intersected by
* the finite line. The cell is returned as a cell id and as a generic
* cell. For other IntersectWithLine signatures, see
* vtkAbstractCellLocator. Note this is currently not thread-safe.
*/
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 the closest point and the cell which is closest to the point x.
* The closest point is somewhere on a cell, it need not be one of the
* vertices of the cell. This version takes in a vtkGenericCell
* to avoid allocating and deallocating the cell. This is much faster than
* the version which does not take a *cell, especially when this function is
* called many times in a row such as by a for loop, where the allocation and
* deallocation can be done only once outside the for loop. If a cell is
* found, "cell" contains the points and ptIds for the cell "cellId" upon
* exit.
*/
void FindClosestPoint(
const double x[3], double closestPoint[3],
vtkGenericCell *cell, vtkIdType &cellId,
int &subId, double& dist2) override;
/**
* Return the closest point within a specified radius and the cell which is
* closest to the point x. The closest point is somewhere on a cell, it
* need not be one of the vertices of the cell. This method returns 1 if a
* point is found within the specified radius. If there are no cells within
* the specified radius, the method returns 0 and the values of
* closestPoint, cellId, subId, and dist2 are undefined. This version takes
* in a vtkGenericCell to avoid allocating and deallocating the cell. This
* is much faster than the version which does not take a *cell, especially
* when this function is called many times in a row such as by a for loop,
* where the allocation and dealloction can be done only once outside the
* for loop. If a closest point is found, "cell" contains the points and
* ptIds for the cell "cellId" upon exit. If a closest point is found,
* inside returns the return value of the EvaluatePosition call to the
* closest cell; inside(=1) or outside(=0). For other
* FindClosestPointWithinRadius signatures, see vtkAbstractCellLocator.
*/
vtkIdType FindClosestPointWithinRadius(
double x[3], double radius, double closestPoint[3],
vtkGenericCell *cell, vtkIdType &cellId,
int &subId, double& dist2, int &inside) override;
/**
* Get the cells in a particular bucket.
*/
virtual vtkIdList *GetCells(int bucket);
/**
* Return number of buckets available. Insure that the locator has been
* built before attempting to access buckets (octants).
*/
virtual int GetNumberOfBuckets(void);
/**
* Find the cell containing a given point. returns -1 if no cell found
* the cell parameters are copied into the supplied variables, a cell must
* be provided to store the information.
*/
vtkIdType FindCell(
double x[3], double tol2, vtkGenericCell *GenCell,
double pcoords[3], double *weights) override;
/**
* Return a list of unique cell ids inside of a given bounding box. The
* user must provide the vtkIdList to populate. This method returns data
* only after the locator has been built.
*/
void FindCellsWithinBounds(double *bbox, vtkIdList *cells) override;
/**
* Given a finite line defined by the two points (p1,p2), return the list
* of unique cell ids in the buckets containing the line. It is possible
* that an empty cell list is returned. The user must provide the vtkIdList
* to populate. This method returns data only after the locator has been
* built.
*/
void FindCellsAlongLine(const double p1[3], const double p2[3],
double tolerance, vtkIdList *cells) override;
//@{
/**
* Satisfy vtkLocator abstract interface.
*/
void FreeSearchStructure() override;
void BuildLocator() override;
virtual void BuildLocatorIfNeeded();
virtual void ForceBuildLocator();
virtual void BuildLocatorInternal();
void GenerateRepresentation(int level, vtkPolyData *pd) override;
//@}
protected:
vtkCellLocator();
~vtkCellLocator() override;
void GetBucketNeighbors(int ijk[3], int ndivs, int level);
void GetOverlappingBuckets(const double x[3], int ijk[3], double dist,
int prevMinLevel[3], int prevMaxLevel[3]);
void ClearCellHasBeenVisited();
void ClearCellHasBeenVisited(vtkIdType id);
double Distance2ToBucket(const double x[3], int nei[3]);
double Distance2ToBounds(const double x[3], double bounds[6]);
int NumberOfOctants; // number of octants in tree
double Bounds[6]; // bounding box root octant
int NumberOfParents; // number of parent octants
double H[3]; // width of leaf octant in x-y-z directions
int NumberOfDivisions; // number of "leaf" octant sub-divisions
vtkIdList **Tree; // octree
void MarkParents(void*, int, int, int, int, int);
void GetChildren(int idx, int level, int children[8]);
int GenerateIndex(int offset, int numDivs, int i, int j, int k,
vtkIdType &idx);
void GenerateFace(int face, int numDivs, int i, int j, int k,
vtkPoints *pts, vtkCellArray *polys);
vtkNeighborCells *Buckets;
unsigned char *CellHasBeenVisited;
unsigned char QueryNumber;
void ComputeOctantBounds(int i, int j, int k);
double OctantBounds[6]; //the bounds of the current octant
int IsInOctantBounds(const double x[3], double tol = 0.0)
{
if ( this->OctantBounds[0]-tol <= x[0] && x[0] <= this->OctantBounds[1]+tol &&
this->OctantBounds[2]-tol <= x[1] && x[1] <= this->OctantBounds[3]+tol &&
this->OctantBounds[4]-tol <= x[2] && x[2] <= this->OctantBounds[5]+tol )
{
return 1;
}
else
{
return 0;
}
}
private:
vtkCellLocator(const vtkCellLocator&) = delete;
void operator=(const vtkCellLocator&) = delete;
};
#endif