VTK-m  2.2
exec/PointLocatorSparseGrid.h
Go to the documentation of this file.
1 //============================================================================
2 // Copyright (c) Kitware, Inc.
3 // All rights reserved.
4 // See LICENSE.txt for details.
5 //
6 // This software is distributed WITHOUT ANY WARRANTY; without even
7 // the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8 // PURPOSE. See the above copyright notice for more information.
9 //============================================================================
10 #ifndef vtk_m_exec_PointLocatorSparseGrid_h
11 #define vtk_m_exec_PointLocatorSparseGrid_h
12 
14 
15 #include <vtkm/VectorAnalysis.h>
16 
17 namespace vtkm
18 {
19 namespace exec
20 {
21 
29 {
30 public:
31  using CoordPortalType =
32  typename vtkm::cont::CoordinateSystem::MultiplexerArrayType::ReadPortalType;
34 
35 
37  const vtkm::Vec3f& max,
38  const vtkm::Id3& dims,
39  const CoordPortalType& coords,
40  const IdPortalType& pointIds,
41  const IdPortalType& cellLower,
42  const IdPortalType& cellUpper)
43  : Min(min)
44  , Dims(dims)
45  , Dxdydz((max - Min) / Dims)
46  , Coords(coords)
47  , PointIds(pointIds)
48  , CellLower(cellLower)
49  , CellUpper(cellUpper)
50  {
51  }
52 
63  VTKM_EXEC void FindNearestNeighbor(const vtkm::Vec3f& queryPoint,
64  vtkm::Id& nearestNeighborId,
65  vtkm::FloatDefault& distance2) const
66  {
67  //std::cout << "FindNeareastNeighbor: " << queryPoint << std::endl;
68  vtkm::Id3 ijk = (queryPoint - this->Min) / this->Dxdydz;
69  ijk = vtkm::Max(ijk, vtkm::Id3(0));
70  ijk = vtkm::Min(ijk, this->Dims - vtkm::Id3(1));
71 
72  nearestNeighborId = -1;
73  distance2 = vtkm::Infinity<vtkm::FloatDefault>();
74 
75  this->FindInCell(queryPoint, ijk, nearestNeighborId, distance2);
76 
77  // TODO: This might stop looking before the absolute nearest neighbor is found.
78  vtkm::Id maxLevel = vtkm::Max(vtkm::Max(this->Dims[0], this->Dims[1]), this->Dims[2]);
79  vtkm::Id level;
80  for (level = 1; (nearestNeighborId < 0) && (level < maxLevel); ++level)
81  {
82  this->FindInBox(queryPoint, ijk, level, nearestNeighborId, distance2);
83  }
84 
85  // Search one more level out. This is still not guaranteed to find the closest point
86  // in all cases (past level 2), but it will catch most cases where the closest point
87  // is just on the other side of a cell boundary.
88  this->FindInBox(queryPoint, ijk, level, nearestNeighborId, distance2);
89  }
90 
91 private:
95 
97 
101 
102  VTKM_EXEC void FindInCell(const vtkm::Vec3f& queryPoint,
103  const vtkm::Id3& ijk,
104  vtkm::Id& nearestNeighborId,
105  vtkm::FloatDefault& nearestDistance2) const
106  {
107  vtkm::Id cellId = ijk[0] + (ijk[1] * this->Dims[0]) + (ijk[2] * this->Dims[0] * this->Dims[1]);
108  vtkm::Id lower = this->CellLower.Get(cellId);
109  vtkm::Id upper = this->CellUpper.Get(cellId);
110  for (vtkm::Id index = lower; index < upper; index++)
111  {
112  vtkm::Id pointid = this->PointIds.Get(index);
113  vtkm::Vec3f point = this->Coords.Get(pointid);
114  vtkm::FloatDefault distance2 = vtkm::MagnitudeSquared(point - queryPoint);
115  if (distance2 < nearestDistance2)
116  {
117  nearestNeighborId = pointid;
118  nearestDistance2 = distance2;
119  }
120  }
121  }
122 
123  VTKM_EXEC void FindInBox(const vtkm::Vec3f& queryPoint,
124  const vtkm::Id3& boxCenter,
125  vtkm::Id level,
126  vtkm::Id& nearestNeighborId,
127  vtkm::FloatDefault& nearestDistance2) const
128  {
129  if ((boxCenter[0] - level) >= 0)
130  {
131  this->FindInXPlane(
132  queryPoint, boxCenter - vtkm::Id3(level, 0, 0), level, nearestNeighborId, nearestDistance2);
133  }
134  if ((boxCenter[0] + level) < this->Dims[0])
135  {
136  this->FindInXPlane(
137  queryPoint, boxCenter + vtkm::Id3(level, 0, 0), level, nearestNeighborId, nearestDistance2);
138  }
139 
140  if ((boxCenter[1] - level) >= 0)
141  {
142  this->FindInYPlane(
143  queryPoint, boxCenter - vtkm::Id3(0, level, 0), level, nearestNeighborId, nearestDistance2);
144  }
145  if ((boxCenter[1] + level) < this->Dims[1])
146  {
147  this->FindInYPlane(
148  queryPoint, boxCenter + vtkm::Id3(0, level, 0), level, nearestNeighborId, nearestDistance2);
149  }
150 
151  if ((boxCenter[2] - level) >= 0)
152  {
153  this->FindInZPlane(
154  queryPoint, boxCenter - vtkm::Id3(0, 0, level), level, nearestNeighborId, nearestDistance2);
155  }
156  if ((boxCenter[2] + level) < this->Dims[2])
157  {
158  this->FindInZPlane(
159  queryPoint, boxCenter + vtkm::Id3(0, 0, level), level, nearestNeighborId, nearestDistance2);
160  }
161  }
162 
163  VTKM_EXEC void FindInPlane(const vtkm::Vec3f& queryPoint,
164  const vtkm::Id3& planeCenter,
165  const vtkm::Id3& div,
166  const vtkm::Id3& mod,
167  const vtkm::Id3& origin,
168  vtkm::Id numInPlane,
169  vtkm::Id& nearestNeighborId,
170  vtkm::FloatDefault& nearestDistance2) const
171  {
172  for (vtkm::Id index = 0; index < numInPlane; ++index)
173  {
174  vtkm::Id3 ijk = planeCenter + vtkm::Id3(index) / div +
175  vtkm::Id3(index % mod[0], index % mod[1], index % mod[2]) + origin;
176  if ((ijk[0] >= 0) && (ijk[0] < this->Dims[0]) && (ijk[1] >= 0) && (ijk[1] < this->Dims[1]) &&
177  (ijk[2] >= 0) && (ijk[2] < this->Dims[2]))
178  {
179  this->FindInCell(queryPoint, ijk, nearestNeighborId, nearestDistance2);
180  }
181  }
182  }
183 
184  VTKM_EXEC void FindInXPlane(const vtkm::Vec3f& queryPoint,
185  const vtkm::Id3& planeCenter,
186  vtkm::Id level,
187  vtkm::Id& nearestNeighborId,
188  vtkm::FloatDefault& nearestDistance2) const
189  {
190  vtkm::Id yWidth = (2 * level) + 1;
191  vtkm::Id zWidth = (2 * level) + 1;
192  vtkm::Id3 div = { yWidth * zWidth, yWidth * zWidth, yWidth };
193  vtkm::Id3 mod = { 1, yWidth, 1 };
194  vtkm::Id3 origin = { 0, -level, -level };
195  vtkm::Id numInPlane = yWidth * zWidth;
196  this->FindInPlane(
197  queryPoint, planeCenter, div, mod, origin, numInPlane, nearestNeighborId, nearestDistance2);
198  }
199 
200  VTKM_EXEC void FindInYPlane(const vtkm::Vec3f& queryPoint,
201  vtkm::Id3 planeCenter,
202  vtkm::Id level,
203  vtkm::Id& nearestNeighborId,
204  vtkm::FloatDefault& nearestDistance2) const
205  {
206  vtkm::Id xWidth = (2 * level) - 1;
207  vtkm::Id zWidth = (2 * level) + 1;
208  vtkm::Id3 div = { xWidth * zWidth, xWidth * zWidth, xWidth };
209  vtkm::Id3 mod = { xWidth, 1, 1 };
210  vtkm::Id3 origin = { -level + 1, 0, -level };
211  vtkm::Id numInPlane = xWidth * zWidth;
212  this->FindInPlane(
213  queryPoint, planeCenter, div, mod, origin, numInPlane, nearestNeighborId, nearestDistance2);
214  }
215 
216  VTKM_EXEC void FindInZPlane(const vtkm::Vec3f& queryPoint,
217  vtkm::Id3 planeCenter,
218  vtkm::Id level,
219  vtkm::Id& nearestNeighborId,
220  vtkm::FloatDefault& nearestDistance2) const
221  {
222  vtkm::Id xWidth = (2 * level) - 1;
223  vtkm::Id yWidth = (2 * level) - 1;
224  vtkm::Id3 div = { xWidth * yWidth, xWidth, xWidth * yWidth };
225  vtkm::Id3 mod = { xWidth, 1, 1 };
226  vtkm::Id3 origin = { -level + 1, -level + 1, 0 };
227  vtkm::Id numInPlane = xWidth * yWidth;
228  this->FindInPlane(
229  queryPoint, planeCenter, div, mod, origin, numInPlane, nearestNeighborId, nearestDistance2);
230  }
231 };
232 
233 } // vtkm::exec
234 } // vtkm
235 
236 #endif // vtk_m_exec_PointLocatorSparseGrid_h
vtkm::exec::PointLocatorSparseGrid
Structure for locating point.
Definition: exec/PointLocatorSparseGrid.h:28
vtkm::exec::PointLocatorSparseGrid::FindInYPlane
void FindInYPlane(const vtkm::Vec3f &queryPoint, vtkm::Id3 planeCenter, vtkm::Id level, vtkm::Id &nearestNeighborId, vtkm::FloatDefault &nearestDistance2) const
Definition: exec/PointLocatorSparseGrid.h:200
VTKM_EXEC
#define VTKM_EXEC
Definition: ExportMacros.h:51
vtkm
Groups connected points that have the same field value.
Definition: Atomic.h:19
vtkm::exec::PointLocatorSparseGrid::IdPortalType
typename vtkm::cont::ArrayHandle< vtkm::Id >::ReadPortalType IdPortalType
Definition: exec/PointLocatorSparseGrid.h:33
vtkm::exec::PointLocatorSparseGrid::FindInCell
void FindInCell(const vtkm::Vec3f &queryPoint, const vtkm::Id3 &ijk, vtkm::Id &nearestNeighborId, vtkm::FloatDefault &nearestDistance2) const
Definition: exec/PointLocatorSparseGrid.h:102
vtkm::exec::PointLocatorSparseGrid::CellLower
IdPortalType CellLower
Definition: exec/PointLocatorSparseGrid.h:99
vtkm::exec::PointLocatorSparseGrid::CellUpper
IdPortalType CellUpper
Definition: exec/PointLocatorSparseGrid.h:100
CoordinateSystem.h
vtkm::cont::ArrayHandle::ReadPortalType
typename StorageType::ReadPortalType ReadPortalType
The type of portal used when accessing data in a read-only mode.
Definition: ArrayHandle.h:312
VectorAnalysis.h
vtkm::MagnitudeSquared
detail::FloatingPointReturnType< T >::Type MagnitudeSquared(const T &x)
Returns the square of the magnitude of a vector.
Definition: VectorAnalysis.h:64
vtkm::exec::PointLocatorSparseGrid::FindInXPlane
void FindInXPlane(const vtkm::Vec3f &queryPoint, const vtkm::Id3 &planeCenter, vtkm::Id level, vtkm::Id &nearestNeighborId, vtkm::FloatDefault &nearestDistance2) const
Definition: exec/PointLocatorSparseGrid.h:184
vtkm::exec::PointLocatorSparseGrid::Min
vtkm::Vec3f Min
Definition: exec/PointLocatorSparseGrid.h:92
vtkm::exec::PointLocatorSparseGrid::FindInZPlane
void FindInZPlane(const vtkm::Vec3f &queryPoint, vtkm::Id3 planeCenter, vtkm::Id level, vtkm::Id &nearestNeighborId, vtkm::FloatDefault &nearestDistance2) const
Definition: exec/PointLocatorSparseGrid.h:216
vtkm::exec::PointLocatorSparseGrid::FindNearestNeighbor
void FindNearestNeighbor(const vtkm::Vec3f &queryPoint, vtkm::Id &nearestNeighborId, vtkm::FloatDefault &distance2) const
Nearest neighbor search using a Uniform Grid.
Definition: exec/PointLocatorSparseGrid.h:63
vtkm::exec::PointLocatorSparseGrid::FindInPlane
void FindInPlane(const vtkm::Vec3f &queryPoint, const vtkm::Id3 &planeCenter, const vtkm::Id3 &div, const vtkm::Id3 &mod, const vtkm::Id3 &origin, vtkm::Id numInPlane, vtkm::Id &nearestNeighborId, vtkm::FloatDefault &nearestDistance2) const
Definition: exec/PointLocatorSparseGrid.h:163
vtkm::Id
vtkm::Int64 Id
Base type to use to index arrays.
Definition: Types.h:227
vtkm::exec::PointLocatorSparseGrid::Dims
vtkm::Id3 Dims
Definition: exec/PointLocatorSparseGrid.h:93
vtkm::Id3
vtkm::Vec< vtkm::Id, 3 > Id3
Id3 corresponds to a 3-dimensional index for 3d arrays.
Definition: Types.h:1044
vtkm::exec::PointLocatorSparseGrid::Dxdydz
vtkm::Vec3f Dxdydz
Definition: exec/PointLocatorSparseGrid.h:94
vtkm::Vec< vtkm::FloatDefault, 3 >
vtkm::FloatDefault
vtkm::Float32 FloatDefault
The floating point type to use when no other precision is specified.
Definition: Types.h:236
vtkm::exec::PointLocatorSparseGrid::PointIds
IdPortalType PointIds
Definition: exec/PointLocatorSparseGrid.h:98
VTKM_ALWAYS_EXPORT
#define VTKM_ALWAYS_EXPORT
Definition: ExportMacros.h:89
vtkm::exec::PointLocatorSparseGrid::FindInBox
void FindInBox(const vtkm::Vec3f &queryPoint, const vtkm::Id3 &boxCenter, vtkm::Id level, vtkm::Id &nearestNeighborId, vtkm::FloatDefault &nearestDistance2) const
Definition: exec/PointLocatorSparseGrid.h:123
vtkm::exec::PointLocatorSparseGrid::Coords
CoordPortalType Coords
Definition: exec/PointLocatorSparseGrid.h:96
vtkm::exec::PointLocatorSparseGrid::PointLocatorSparseGrid
PointLocatorSparseGrid(const vtkm::Vec3f &min, const vtkm::Vec3f &max, const vtkm::Id3 &dims, const CoordPortalType &coords, const IdPortalType &pointIds, const IdPortalType &cellLower, const IdPortalType &cellUpper)
Definition: exec/PointLocatorSparseGrid.h:36
vtkm::exec::PointLocatorSparseGrid::CoordPortalType
typename vtkm::cont::CoordinateSystem::MultiplexerArrayType::ReadPortalType CoordPortalType
Definition: exec/PointLocatorSparseGrid.h:32