4.12. Locators

Locators are a special type of structure that allows you to take a point coordinate in space and then find a topological element that contains or is near that coordinate. VTK‑m comes with multiple types of locators, which are categorized by the type of topological element that they find. For example, a cell locator takes a coordinate in world space and finds the cell in a vtkm::cont::DataSet that contains that cell. Likewise, a point locator takes a coordinate in world space and finds a point from a vtkm::cont::CoordinateSystem nearby.

Different locators differ in their interface slightly, but they all follow the same basic operation. First, they are constructed and provided with one or more elements of a vtkm::cont::DataSet. Then they are built with a call to an vtkm::cont::CellLocatorBase::Update() method. The locator can then be passed to a worklet as an ExecObject, which will cause the worklet to get a special execution version of the locator that can do the queries.

Did You Know?

Other visualization libraries, like VTK‑m’s big sister toolkit VTK, provide similar locator structures that allow iterative building by adding one element at a time. VTK‑m explicitly disallows this use case. Although iteratively adding elements to a locator is undoubtedly useful, such an operation will inevitably bottleneck a highly threaded algorithm in critical sections. This makes iterative additions to locators too costly to support in VTK‑m.

4.12.1. Cell Locators

Cell Locators in VTK‑m provide a means of building spatial search structures that can later be used to find a cell containing a certain point. This could be useful in scenarios where the application demands the cell to which a point belongs to to achieve a certain functionality. For example, while tracing a particle’s path through a vector field, after every step we lookup which cell the particle has entered to interpolate the velocity at the new location to take the next step.

Using cell locators is a two step process. The first step is to build the search structure. This is done by instantiating one of the CellLocator classes, providing a cell set and coordinate system (usually from a vtkm::cont::DataSet), and then updating the structure. Once the cell locator is built, it can be used in the execution environment within a filter or worklet.

4.12.1.1. Building a Cell Locator

All cell locators in VTK‑m share the same basic interface for the required features of cell locators. This generic interface provides methods to set the cell set (with vtkm::cont::CellLocatorBase::SetCellSet() and vtkm::cont::CellLocatorBase::GetCellSet()) and to set the coordinate system (with vtkm::cont::CellLocatorBase::SetCoordinates() and vtkm::cont::CellLocatorBase::GetCoordinates()). Once the cell set and coordinates are provided, you may call vtkm::cont::CellLocatorBase::Update() to construct the search structures. Although vtkm::cont::CellLocatorBase::Update() is called from the control environment, the search structure will be built on parallel devices.

Example 4.117 Constructing a CellLocator.
1    vtkm::cont::CellLocatorGeneral cellLocator;
2    cellLocator.SetCellSet(inDataSet.GetCellSet());
3    cellLocator.SetCoordinates(inDataSet.GetCoordinateSystem());
4    cellLocator.Update();

VTK‑m provides multiple implementations of cell locators. All cell locator classes derive the abstract vtkm::cont::CellLocatorBase class.

class CellLocatorBase : public vtkm::cont::ExecutionObjectBase

Base class for all CellLocator classes.

CellLocatorBase subclasses must implement the pure virtual Build() method. They also must provide a PrepareForExecution() method to satisfy the ExecutionObjectBase superclass.

If a derived class changes its state in a way that invalidates its internal search structure, it should call the protected SetModified() method. This will alert the base class to rebuild the structure on the next call to Update().

Subclassed by vtkm::cont::CellLocatorBoundingIntervalHierarchy, vtkm::cont::CellLocatorGeneral, vtkm::cont::CellLocatorRectilinearGrid, vtkm::cont::CellLocatorTwoLevel, vtkm::cont::CellLocatorUniformBins, vtkm::cont::CellLocatorUniformGrid

Public Functions

inline const vtkm::cont::UnknownCellSet &GetCellSet() const

Specify the CellSet defining the structure of the cells being searched.

This is typically retrieved from the vtkm::cont::DataSet::GetCellSet() method.

inline void SetCellSet(const vtkm::cont::UnknownCellSet &cellSet)

Specify the CellSet defining the structure of the cells being searched.

This is typically retrieved from the vtkm::cont::DataSet::GetCellSet() method.

inline const vtkm::cont::CoordinateSystem &GetCoordinates() const

Specify the CoordinateSystem defining the location of the cells.

This is typically retrieved from the vtkm::cont::DataSet::GetCoordinateSystem() method.

inline void SetCoordinates(const vtkm::cont::CoordinateSystem &coords)

Specify the CoordinateSystem defining the location of the cells.

This is typically retrieved from the vtkm::cont::DataSet::GetCoordinateSystem() method.

inline void SetCoordinates(const vtkm::cont::UnknownArrayHandle &coords)

Specify the CoordinateSystem defining the location of the cells.

This is typically retrieved from the vtkm::cont::DataSet::GetCoordinateSystem() method.

void Update() const

Build the search structure used to look up cells.

This method must be called after the cells and coordiantes are specified with SetCellSet() and SetCoordinates(), respectively. The method must also be called before it is used with a worklet. Before building the search structure Update() checks to see if the structure is already built and up to date. If so, the method quickly returns. Thus, it is good practice to call Update() before each use in a worklet.

Although Update() is called from the control environment, it lauches jobs in the execution environment to quickly build the search structure.

The choice of which cell locator to use depends on the structure of the cells and the regularity of the distribution.

4.12.1.1.1. Cell Locators for Structured Cell Sets

If your vtkm::cont::DataSet has a cell set of type vtkm::cont::CellSetStructured, this can give a locator information about the regular nature of the cells to more quickly identify cells. The mechanism to find the cells then becomes dependent on the type of coordinates in the cell set.

If the vtkm::cont::DataSet contains a vtkm::cont::ArrayHandleUniformPointCoordinates as the coordinate system, this is known as a uniform grid. The cells are aligned with the world axes and have uniform spacing between them. In this case, the vtkm::cont::CellLocatorUniformGrid is highly optimized to find cells.

class CellLocatorUniformGrid : public vtkm::cont::CellLocatorBase

A cell locator optimized for finding cells in a uniform grid.

This locator is optimized for structured data that has uniform axis-aligned spacing. For this cell locator to work, it has to be given a cell set of type vtkm::cont::CellSetStructured and a coordinate system using a vtkm::cont::ArrayHandleUniformPointCoordinates for its coordinate system. If the data set matches this structure, then this locator will be faster than any others.

In a related case, if the vtkm::cont::DataSet with structured cells contains a vtkm::cont::ArrayHandleCartesianProduct as the coordinate system, this is known as a rectilinear grid. The cells are aligned with the world axes, but the spacing can vary between them. In this case, the vtkm::cont::CellLocatorRectilinearGrid is best to find cells.

class CellLocatorRectilinearGrid : public vtkm::cont::CellLocatorBase

A cell locator optimized for finding cells in a rectilinear grid.

This locator is optimized for structured data that has nonuniform axis-aligned spacing. For this cell locator to work, it has to be given a cell set of type vtkm::cont::CellSetStructured and a coordinate system using a vtkm::cont::ArrayHandleCartesianProduct for its data.

For a vtkm::cont::DataSet containing any other type of cell set or coordinate types, one of the locators for irregular cell sets described below must be used.

4.12.1.1.2. Cell Locators for Irregular Cell Sets

VTK‑m contains several locating strategies cells in irregular patterns in space. These are typically used for cell sets with explicit connectivity or general positioning of points. Although they will technically work on any type of data, they may be less efficient than those designed for a specific structure of data.

A good performing locator across many distributions of cells is vtkm::cont::CellLocatorTwoLevel. This search structure uses a single level of indirection to adapt to an uneven distribution of cells. This tends to lead to a good balance between the number of ids to trace while finding cells, the number of cells that need to be checked, and the space to store the structure.

class CellLocatorTwoLevel : public vtkm::cont::CellLocatorBase

A locator that uses 2 nested levels of grids.

CellLocatorTwoLevel creates a cell search structure using two levels of structured grids. The first level is a coarse grid that covers the entire region of the data. It is expected that the distributions of dataset cells in this coarse grid will be very uneven. Within each bin of the coarse grid, a second level grid is defined within the spatial bounds of the coarse bin. The size of this second level grid is proportional to the number of cells in the first level. In this way, the second level grids adapt to the distribution of cells being located. The adaption is not perfect, but it is has very good space efficiency and is fast to generate and use.

The algorithm used in CellLocatorTwoLevel is described in the following publication:

Javor Kalojanov, Markus Billeter, and Philipp Slusallek. “Two-Level Grids for Ray Tracing on GPUs.” Computer Graphics Forum, 2011, pages 307-314. DOI 10.1111/j.1467-8659.2011.01862.x

Public Functions

inline void SetDensityL1(vtkm::FloatDefault val)

Specify the desired approximate number of cells per level 1 bin.

The default value is 32.

inline vtkm::FloatDefault GetDensityL1() const

Specify the desired approximate number of cells per level 1 bin.

The default value is 32.

inline void SetDensityL2(vtkm::FloatDefault val)

Specify the desired approximate number of cells per level 2 bin.

This value should be relatively small as it is close to the average number of cells that must be checked for each find. The default value is 2.

inline vtkm::FloatDefault GetDensityL2() const

Specify the desired approximate number of cells per level 2 bin.

This value should be relatively small as it is close to the average number of cells that must be checked for each find. The default value is 2.

void PrintSummary(std::ostream &out) const

Print a summary of the state of this locator.

If you happen to know that the cells are evenly distributed across the bounds of the space, then the indirect reference of vtkm::cont::CellLocatorTwoLevel is unnecessary. Each bin in the grid will have approximately the same number of cells, and thus a single level can be used to remove some indirection in the lookup. This is implemented with vtkm::cont::CellLocatorUniformBins.

class CellLocatorUniformBins : public vtkm::cont::CellLocatorBase

A locator that uses a uniform grid.

CellLocatorUniformBins creates a cell search structure using a single uniform grid. The size of the uniform grid is specified using the SetDims method. In general, the CellLocatorTwoLevel has the better performance. However, there are some cases where this is not the case. One example of this is a uniformly dense triangle grid. In some cases the CellLocatorUniformBins produces a more efficient search structure, especially for GPUs where memory access patterns are critical to performance.

Public Functions

inline void SetDims(const vtkm::Id3 &dims)

Specify the dimensions of the grid used to establish bins.

This locator will establish a grid over the bounds of the input data that contains the number of bins specified by these dimensions in each direction. Larger dimensions will reduce the number of cells in each bin, but will require more memory. SetDims() must be called before Update().

inline vtkm::Id3 GetDims() const

Specify the dimensions of the grid used to establish bins.

This locator will establish a grid over the bounds of the input data that contains the number of bins specified by these dimensions in each direction. Larger dimensions will reduce the number of cells in each bin, but will require more memory. SetDims() must be called before Update().

void PrintSummary(std::ostream &out) const

Print a summary of the state of this locator.

In contrast, a very irregular data set may have multiple orders of magnitude difference in the size of its cells. If the cell distribution is very irregular, the vtkm::cont::CellLocatorTwoLevel can be left with bins containing a large number of cells in a regions with very small cells. In these cases, vtkm::cont::CellLocatorBoundingIntervalHierarchy can be used to capture the diversity in cell distribution. vtkm::cont::CellLocatorBoundingIntervalHierarchy builds a search structure by recursively dividing the space of cells. This creates a deeper structure than vtkm::cont::CellLocatorTwoLevel, so it can take longer to find a containing bin when searching for a cell. However, the deeper structure means that each bin is guaranteed to contain a small number of cells.

class CellLocatorBoundingIntervalHierarchy : public vtkm::cont::CellLocatorBase

A cell locator that performs a recursive division of space.

CellLocatorBoundingIntervalHierarchy creates a search structure by recursively dividing the space in which data lives. It starts by choosing an axis to split and then defines a number of splitting planes (set with SetNumberOfSplittingPlanes()). These splitting planes divide the physical region into partitions, and the cells are divided among these partitions. The algorithm then recurses into each region and repeats the process until the regions are divided to the point where the contain no more than a maximum number of cells (specified with SetMaxLeafSize()).

Public Functions

inline CellLocatorBoundingIntervalHierarchy(vtkm::IdComponent numPlanes = 4, vtkm::IdComponent maxLeafSize = 5)

Construct a CellLocatorBoundingIntervalHierarchy while optionally specifying the number of splitting planes and number of cells in each leaf.

inline void SetNumberOfSplittingPlanes(vtkm::IdComponent numPlanes)

Specify the number of splitting planes to use each time a region is divided.

Larger numbers of splitting planes result in a shallower tree (which is good because it means fewer memory lookups to find a cell), but too many splitting planes could lead to poorly shaped regions that inefficiently partition cells.

The default value is 4.

inline vtkm::IdComponent GetNumberOfSplittingPlanes()

Specify the number of splitting planes to use each time a region is divided.

Larger numbers of splitting planes result in a shallower tree (which is good because it means fewer memory lookups to find a cell), but too many splitting planes could lead to poorly shaped regions that inefficiently partition cells.

The default value is 4.

inline void SetMaxLeafSize(vtkm::IdComponent maxLeafSize)

Specify the number of cells in each leaf.

Larger numbers for the maximum leaf size result in a shallower tree (which is good because it means fewer memory lookups to find a cell), but it also means there will be more cells to check in each leaf (which is bad as checking a cell is slower than decending a tree level).

The default value is 5.

inline vtkm::Id GetMaxLeafSize()

Specify the number of cells in each leaf.

Larger numbers for the maximum leaf size result in a shallower tree (which is good because it means fewer memory lookups to find a cell), but it also means there will be more cells to check in each leaf (which is bad as checking a cell is slower than decending a tree level).

The default value is 5.

4.12.1.1.3. Cell Locators for Unknown Cell Sets

The previously described cell locators require you to know the type of cell set and coordinate system array to build a cell locator. Often, this information is not available. In these cases, VTK‑m provides a couple of classes to choose an appropriate locator.

If you are developing function that is templated on the type of cell set and coordinate system, you can use the vtkm::cont::CellLocatorChooser templated type to automatically choose a locator of an appropriate type.

template<typename CellSetType, typename CoordinateSystemArrayType>
using vtkm::cont::CellLocatorChooser = typename detail::CellLocatorChooserImpl<CellSetType, CoordinateSystemArrayType>::type

A template to select an appropriate CellLocator based on CellSet type.

Given a concrete type for a CellSet subclass and a type of ArrayHandle for the coordinate system, CellLocatorChooser picks an appropriate CellLocator for that type of grid. It is a convenient class to use when you can resolve your templates to discover the type of data set being used for location.

Example 4.118 Using vtkm::cont::CellLocatorChooser to determine the cell locator type.
 1template<typename CellSetType,
 2         typename CoordsType,
 3         typename QueryPointsType,
 4         typename FieldType>
 5void QueryCells(const CellSetType& cellSet,
 6                const CoordsType& coords,
 7                const QueryPointsType& queryPoints,
 8                const FieldType& inField,
 9                const FieldType& interpolatedField)
10{
11  VTKM_IS_CELL_SET(CellSetType);
12  VTKM_IS_ARRAY_HANDLE(CoordsType);
13  VTKM_IS_ARRAY_HANDLE(QueryPointsType);
14  VTKM_IS_ARRAY_HANDLE(FieldType);
15
16  vtkm::cont::CellLocatorChooser<CellSetType, CoordsType> cellLocator;
17  cellLocator.SetCellSet(cellSet);
18  cellLocator.SetCoordinates(coords);
19  cellLocator.Update();
20
21  vtkm::cont::Invoker invoke;
22  invoke(
23    QueryCellsWorklet{}, queryPoints, cellLocator, cellSet, inField, interpolatedField);
24}

There are times when the type of cell locator cannot be easily determined at compile times. In this case, the vtkm::cont::CellLocatorGeneral can be used. This locator will accept any type of cell set and coordinate system. It will then choose at runtime the most appropriate cell locating structure to use.

class CellLocatorGeneral : public vtkm::cont::CellLocatorBase

A CellLocator that works generally well for any supported cell set.

CellLocatorGeneral creates a CellLocator that acts like a multiplexer to switch at runtime to any supported cell set. It is a convenient class to use when the type of CellSet cannot be determined at runtime.

Note that CellLocatorGeneral only supports a finite amount of CellSet types. Thus, it is possible to give it a cell set type that is not supported.

Also note that CellLocatorGeneral can add a significant amount of code inside of worklet that uses it, and this might cause some issues with some compilers.

Example 4.119 Using vtkm::cont::CellLocatorGeneral.
1    vtkm::cont::CellLocatorGeneral cellLocator;
2    cellLocator.SetCellSet(inDataSet.GetCellSet());
3    cellLocator.SetCoordinates(inDataSet.GetCoordinateSystem());
4    cellLocator.Update();

4.12.1.2. Using Cell Locators in a Worklet

The vtkm::cont::CellLocatorBase interface implements vtkm::cont::ExecutionObjectBase. This means that any CellLocator can be used in worklets as an ExecObject argument (as defined in the ControlSignature). See Chapter 4.11 (Execution Objects) for information on ExecObject arguments to worklets.

When a CellLocator class is passed as an ExecObject argument to a worklet vtkm::cont::Invoke, the worklet receives a different object defined in the vtkm::exec namespace. This CellLocator object provides a FindCell() method that identifies a containing cell given a point location in space.

Common Errors

Note that the CellLocator classes in the respective vtkm::cont and vtkm::exec namespaces are different objects with different interfaces despite the similar names.

Below is the documentation for vtkm::exec::CellLocatorUniformGrid, which corresponds to the execution query struct provided by vtkm::cont::CellLocatorUniformGrid. That said, this interface is shared among all the execution query structs provided by all locator types.

class CellLocatorUniformGrid

Structure for locating cells.

Use the FindCell() method to identify which cell contains a point in space. The FindCell() method optionally takes a LastCell object, which is a structure nested in this class. The LastCell object can help speed locating cells for successive finds at nearby points.

This class is provided by vtkm::cont::CellLocatorUniformGrid when passed to a worklet.

Public Functions

inline vtkm::ErrorCode FindCell(const vtkm::Vec3f &point, vtkm::Id &cellId, vtkm::Vec3f &parametric, LastCell &lastCell) const

Locate the cell containing the provided point.

Given the point coordinate point, this method determines which cell contains that point. The identification of the cell is returned in the cellId reference parameter. The method also determines the cell’s parametric coordinates to the point and returns that in the parametric reference parameter. This result can be used in functions like vtkm::exec::CellInterpolate().

FindCell() takes an optional LastCell parameter. This parameter captures the location of the found cell and can be passed to the next call of FindCell(). If the subsequent FindCell() call is for a point that is in or near the same cell, the operation may go faster.

This method will return vtkm::ErrorCode::Success if a cell is found. If a cell is not found, vtkm::ErrorCode::CellNotFound is returned and cellId is set to -1.

inline vtkm::ErrorCode FindCell(const vtkm::Vec3f &point, vtkm::Id &cellId, vtkm::Vec3f &parametric) const

Locate the cell containing the provided point.

Given the point coordinate point, this method determines which cell contains that point. The identification of the cell is returned in the cellId reference parameter. The method also determines the cell’s parametric coordinates to the point and returns that in the parametric reference parameter. This result can be used in functions like vtkm::exec::CellInterpolate().

FindCell() takes an optional LastCell parameter. This parameter captures the location of the found cell and can be passed to the next call of FindCell(). If the subsequent FindCell() call is for a point that is in or near the same cell, the operation may go faster.

This method will return vtkm::ErrorCode::Success if a cell is found. If a cell is not found, vtkm::ErrorCode::CellNotFound is returned and cellId is set to -1.

struct LastCell

Structure capturing the location of a cell in the search structure.

An object of this type is passed to and from the FindCell() method. If FindCell() is called successively with points near each other, the information in this object can reduce the time to find the cell.

The following example defines a simple worklet to get the value of a point field interpolated to a group of query point coordinates provided.

Example 4.120 Using a CellLocator in a worklet.
 1struct QueryCellsWorklet : public vtkm::worklet::WorkletMapField
 2{
 3  using ControlSignature =
 4    void(FieldIn, ExecObject, WholeCellSetIn<Cell, Point>, WholeArrayIn, FieldOut);
 5  using ExecutionSignature = void(_1, _2, _3, _4, _5);
 6
 7  template<typename Point,
 8           typename CellLocatorExecObject,
 9           typename CellSet,
10           typename FieldPortal,
11           typename OutType>
12  VTKM_EXEC void operator()(const Point& point,
13                            const CellLocatorExecObject& cellLocator,
14                            const CellSet& cellSet,
15                            const FieldPortal& field,
16                            OutType& out) const
17  {
18    // Use the cell locator to find the cell containing the point and the parametric
19    // coordinates within that cell.
20    vtkm::Id cellId;
21    vtkm::Vec3f parametric;
22    vtkm::ErrorCode status = cellLocator.FindCell(point, cellId, parametric);
23    if (status != vtkm::ErrorCode::Success)
24    {
25      this->RaiseError(vtkm::ErrorString(status));
26    }
27
28    // Use this information to interpolate the point field to the given location.
29    if (cellId >= 0)
30    {
31      // Get shape information about the cell containing the point coordinate
32      auto cellShape = cellSet.GetCellShape(cellId);
33      auto indices = cellSet.GetIndices(cellId);
34
35      // Make a Vec-like containing the field data at the cell's points
36      auto fieldValues = vtkm::make_VecFromPortalPermute(&indices, &field);
37
38      // Do the interpolation
39      vtkm::exec::CellInterpolate(fieldValues, parametric, cellShape, out);
40    }
41    else
42    {
43      this->RaiseError("Given point outside of the cell set.");
44    }
45  }
46};
47
48//
49// Later in the associated Filter class...
50//
51
52    vtkm::cont::CellLocatorGeneral cellLocator;
53    cellLocator.SetCellSet(inDataSet.GetCellSet());
54    cellLocator.SetCoordinates(inDataSet.GetCoordinateSystem());
55    cellLocator.Update();
56
57    vtkm::cont::ArrayHandle<FieldType> interpolatedField;
58
59    this->Invoke(QueryCellsWorklet{},
60                 this->QueryPoints,
61                 &cellLocator,
62                 inDataSet.GetCellSet(),
63                 inputField,
64                 interpolatedField);

4.12.2. Point Locators

Point Locators in VTK‑m provide a means of building spatial search structures that can later be used to find the nearest neighbor a certain point. This could be useful in scenarios where the closest pairs of points are needed. For example, during halo finding of particles in cosmology simulations, pairs of nearest neighbors within certain linking length are used to form clusters of particles.

Using point locators is a two step process. The first step is to build the search structure. This is done by instantiating one of the PointLocator classes, providing a coordinate system (usually from a vtkm::cont::DataSet) representing the location of points that can later be found through queries, and then updating the structure. Once the point locator is built, it can be used in the execution environment within a filter or worklet.

4.12.2.1. Building a Point Locator

All point locators in VTK‑m share the same basic interface for the required features of point locators. This generic interface provides methods to set the coordinate system (with vtkm::cont::PointLocatorBase::SetCoordinates() and vtkm::cont::PointLocatorBase::GetCoordinates()) of training points. Once the coordinates are provided, you may call vtkm::cont::PointLocatorBase::Update() to construct the search structures. Although vtkm::cont::PointLocatorBase::Update() is called from the control environment, the search structure will be built on parallel devices

Example 4.121 Constructing a PointLocator.
1    vtkm::cont::PointLocatorSparseGrid pointLocator;
2    pointLocator.SetCoordinates(inDataSet.GetCoordinateSystem());
3    pointLocator.Update();

Point locators in VTK‑m derive the abstract vtkm::cont::PointLocatorBase class.

class PointLocatorBase : public vtkm::cont::ExecutionObjectBase

Base class for all PointLocator classes.

PointLocatorBase subclasses must implement the pure virtual Build() method. They also must provide a PrepareForExecution() method to satisfy the ExecutionObjectBase superclass.

If a derived class changes its state in a way that invalidates its internal search structure, it should call the protected SetModified() method. This will alert the base class to rebuild the structure on the next call to Update().

Subclassed by vtkm::cont::PointLocatorSparseGrid

Public Functions

inline vtkm::cont::CoordinateSystem GetCoordinates() const

Specify the CoordinateSystem defining the location of the cells.

This is often retrieved from the vtkm::cont::DataSet::GetCoordinateSystem() method, but it can be any array of size 3 Vecs.

inline void SetCoordinates(const vtkm::cont::CoordinateSystem &coords)

Specify the CoordinateSystem defining the location of the cells.

This is often retrieved from the vtkm::cont::DataSet::GetCoordinateSystem() method, but it can be any array of size 3 Vecs.

inline void SetCoordinates(const vtkm::cont::UnknownArrayHandle &coords)

Specify the CoordinateSystem defining the location of the cells.

This is often retrieved from the vtkm::cont::DataSet::GetCoordinateSystem() method, but it can be any array of size 3 Vecs.

VTK‑m implements a point locator named vtkm::cont::PointLocatorSparseGrid.

class PointLocatorSparseGrid : public vtkm::cont::PointLocatorBase

A locator that bins points in a sparsely stored grid.

PointLocatorSparseGrid creates a very dense logical grid over the region containing the points of the provided data set. Although this logical grid has uniform structure, it is stored sparsely. So, it is expected that most of the bins in the structure will be empty but not explicitly stored. This makes PointLocatorSparseGrid a good representation for unstructured or irregular collections of points.

The algorithm used in PointLocatorSparseGrid is described in the following publication:

Abhishek Yenpure, Hank Childs, and Kenneth Moreland. “Efficient Point Merging Using Data

Parallel Techniques.” In

Eurographics Symposium on Parallel Graphics and Visualization (EGPGV), June 2019. DOI 10.2312/pgv.20191112.

Public Functions

inline void SetRange(const RangeType &range)

Specify the bounds of the space to search for points.

If the spatial range is not set, it will be automatically defined to be the space containing the points.

inline const RangeType &GetRange() const

Specify the bounds of the space to search for points.

If the spatial range is not set, it will be automatically defined to be the space containing the points.

inline void SetNumberOfBins(const vtkm::Id3 &bins)

Specify the number of bins used in the sparse grid to be searched.

Larger dimensions result in smaller bins, which in turn means fewer points are in each bin. This means comparing against fewer points. This is good when searching for coincident points. However, when searching for nearest points a distance away, larger dimensions require searching for more bins.

The default number of bins is 32x32x32.

inline const vtkm::Id3 &GetNumberOfBins() const

Specify the number of bins used in the sparse grid to be searched.

Larger dimensions result in smaller bins, which in turn means fewer points are in each bin. This means comparing against fewer points. This is good when searching for coincident points. However, when searching for nearest points a distance away, larger dimensions require searching for more bins.

The default number of bins is 32x32x32.

4.12.2.2. Using Point Locators in a Worklet

The vtkm::cont::PointLocator::Base interface implements vtkm::cont::ExecutionObjectBase. This means that any PointLocator can be used in worklets as an ExecObject argument (as defined in the ControlSignature). See Chapter 4.11 (Execution Objects) for information on ExecObject arguments to worklets.

When a PointLocator class is passed as an ExecObject argument to a worklet vtkm::cont::Invoke, the worklet receives a different object defined in the vtkm::exec namespace. This PointLocator object provides a FindNearestNeighbor method that identifies the nearest neighbor point given a point location in space.

Common Errors

Note that the PointLocator classes in the respective vtkm::cont and vtkm::exec namespaces are different objects with different interfaces despite the similar names.

Below is the documentation for vtkm::exec::PointLocatorSparseGrid, which corresponds to the execution query struct provided by vtkm::cont::PointLocatorSparseGrid. That said, this interface is shared among all the execution query structs provided by all locator types.

class PointLocatorSparseGrid

Structure for locating point.

Use the FindNearestNeighbor() method to identify which cell contains a point in space.

This class is provided by vtkm::cont::PointLocatorSparseGrid when passed to a worklet.

Public Functions

inline void FindNearestNeighbor(const vtkm::Vec3f &queryPoint, vtkm::Id &nearestNeighborId, vtkm::FloatDefault &distance2) const

Nearest neighbor search using a Uniform Grid.

Parallel search of nearesat neighbor for each point in the queryPoints in the set of coords. Returns neareast neighbot in nearestNeighborIds and distances to nearest neighbor in distances.

Parameters:

  • queryPoint – Point coordinates to query for nearest neighbor.

  • nearestNeighborId – Neareast neighbor in the training dataset for each points in the test set

  • distance2 – Squared distance between query points and their nearest neighbors.

The following example defines a simple worklet that finds points nearest to query locations.

Example 4.122 Using a PointLocator in a worklet.
 1/// Worklet that generates for each input coordinate a unit vector that points
 2/// to the closest point in a locator.
 3struct PointToClosestWorklet : public vtkm::worklet::WorkletMapField
 4{
 5  using ControlSignature = void(FieldIn, ExecObject, WholeArrayIn, FieldOut);
 6  using ExecutionSignature = void(_1, _2, _3, _4);
 7
 8  template<typename Point,
 9           typename PointLocatorExecObject,
10           typename CoordinateSystemPortal,
11           typename OutType>
12  VTKM_EXEC void operator()(const Point& queryPoint,
13                            const PointLocatorExecObject& pointLocator,
14                            const CoordinateSystemPortal& coordinateSystem,
15                            OutType& out) const
16  {
17    // Use the point locator to find the point in the locator closest to the point
18    // given.
19    vtkm::Id pointId;
20    vtkm::FloatDefault distanceSquared;
21    pointLocator.FindNearestNeighbor(queryPoint, pointId, distanceSquared);
22
23    // Use this information to find the nearest point and create a unit vector
24    // pointing to it.
25    if (pointId >= 0)
26    {
27      // Get nearest point coordinate.
28      auto point = coordinateSystem.Get(pointId);
29
30      // Get the vector pointing to this point
31      out = point - queryPoint;
32
33      // Convert to unit vector (if possible)
34      if (distanceSquared > vtkm::Epsilon<vtkm::FloatDefault>())
35      {
36        out = vtkm::RSqrt(distanceSquared) * out;
37      }
38    }
39    else
40    {
41      this->RaiseError("Locator could not find closest point.");
42    }
43  }
44};
45
46//
47// Later in the associated Filter class...
48//
49
50    vtkm::cont::PointLocatorSparseGrid pointLocator;
51    pointLocator.SetCoordinates(inDataSet.GetCoordinateSystem());
52    pointLocator.Update();
53
54    vtkm::cont::ArrayHandle<vtkm::Vec3f> pointDirections;
55
56    this->Invoke(PointToClosestWorklet{},
57                 this->QueryPoints,
58                 &pointLocator,
59                 pointLocator.GetCoordinates(),
60                 pointDirections);