% -*- latex -*-

\chapter{Locators}
\label{chap: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.
\VTKm comes with multiple types of locators, which are categorized by the type of topological element that they find.
For example, a \index{cell locator}\keyterm{cell locator} takes a coordinate in world space and finds the cell in a \vtkmcont{DataSet} that contains that cell.
Likewise, a \index{point locator}\keyterm{point locator} takes a coordinate in world space and finds a point from a \vtkmcont{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 \vtkmcont{DataSet}.
Then they are built with a call to an \classmember{Update} method.
The locator can then be passed to a worklet as an \sigtag{ExecObject}, which will cause the worklet to get a special execution version of the locator that can do the queries.

\begin{didyouknow}
  Other visualization libraries, like \VTKm's big sister toolkit VTK, provide similar locator structures that allow iterative building by adding one element at a time.
  \VTKm 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 \VTKm.
\end{didyouknow}


\section{Cell Locators}
\label{sec:CellLocators}

Cell Locators in \VTKm 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 subclasses of \vtkmcont{CellLocator}, providing a cell set and coordinate system (usually from a \vtkmcont{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.

\subsection{Building a Cell Locator}

All Cell Locators in \VTKm inherit from \vtkmcont{CellLocator}, which provides the basic interface for the required features of cell locators.
This generic interface provides methods to set the cell set (with \classmember{SetCellSet} and \classmember{GetCellSet}) and to set the coordinate system (with \classmember{SetCoordinates} and \classmember{GetCoordinates}).
Once the cell set and coordinates are provided, you may call \classmember{Update} to construct the search structures.
Although \classmember{Update} is called from the control environment, the search structure will be built on parallel devices.

\VTKm currently exposes the implementations of the following Cell Locators.

\subsubsection{Bounding Interval Hierarchy}

The \vtkmcont{BoundingIntervalHierarchy} cell locator is based on the bounding interval hierarchy spatial search structure.
The implementation in \VTKm takes two parameters: the number of splitting planes used to split the cells uniformly along an axis at each level and the maximum leaf size, which determines if a node needs to be split further.
These parameters can be provided as parameters for the constructor or through the \classmember{SetNumberOfPlanes} and \classmember{SetMaxLeafSize} methods.

\fix{TODO: Compile this example.}
\begin{vtkmexample}{Building a \protect\vtkmcont{BoundingIntervalHierarchy}.}
// Create a locator that will use 5 splitting places, 
// and will have a maximum of 10 cells per leaf node.
vtkm::cont::BoundingIntervalHierarchy locator(5, 10):
// Provides the CellSet required for the locator 
locator.SetCellSet(cellSet)
// Provides the coordinate system required for the locator 
locator.SetCoordinates(coords)
// Build the search structure (using a parallel device)
locator.Update();
\end{vtkmexample}

\subsection{Using Cell Locators in a Worklet}

The \vtkmcont{CellLocator} interface implements \vtkmcont{ExecutionObjectBase}.
This means that any CellLocator can be used in worklets as an \sigtag{ExecObject} argument (as defined in the ControlSignature).
See Section~\ref{sec:ExecutionObjects} for information on \sigtag{ExecObject} arguments to worklets.

When a \vtkmcont{CellLocator} class is passed as an \sigtag{ExecObject} argument to a worklet \classmember{Invoke}, the worklet receives a pointer to a \vtkmexec{CellLocator} object.
\vtkmexec{CellLocator} provides a \classmember{FindCell} method that identifies a containing cell given a point location in space.

\begin{commonerrors}
  Note that \vtkmcont{CellLocator} and \vtkmexec{CellLocator} are different objects with different interfaces despite the similar names.
\end{commonerrors}

The \classmember*[CellLocator]{FindCell}() method takes 4 arguments.
The first argument is an input query point.
The second argument is used to return the id of the cell containing this point (or -1 if the point is not found in any cell).
The third argument is used to return the parametric coordinates for the point within the cell (assuming it is found in any cell).
The fourth argument is a reference to the calling worklet (used for error reporting purposes).
The following example defines a simple worklet to get the containing cell id and parametric coordinates of a collection of world coordinates.

\fix{TODO: Compile this example.}

\begin{vtkmexample}{Using a \textidentifier{CellLocator} in a worklet.}
struct QueryCellIds : public vtkm::worklet::WorkletMapField                     
{                                                                               
  using ControlSignature = void (FieldIn<>,
                                 ExecObject,
                                 FieldOut<>,
                                 FieldOut<>);
  using ExecutionSignature = void (_1, _2, _3, _4);
                                                                                
  template <typename Point, typename BoundingIntervalHierarchyExecObject>       
  VTKM_EXEC vtkm::IdComponent operator()(
      const Point& point,                    
      BoundingIntervalHierarchyExecObject locator,
      vtkm::Id& cellId,                      
      vtkm::Vec<vtkm::FloatDefault, 3>& parametric) const
  {                                                                             
    locator->FindCell(point, cellId, parametric, *this);                        
  }                                                                             
}; // struct QueryCellIds                                                       
                                                                                
void QueryPointsInDataset(
    vtkm::cont::DataSet& dataSet,                          
    vtkm::cont::ArrayHandle<vtkm::Vec<vtkm::FloatDefault, 3>>& queryPoints;
    vtkm::IdComponent numPlanes,                          
    vtkm::IdComponent maxLeadNodes)                       
{                                                                               
  using DeviceAdapter = VTKM_DEFAULT_DEVICE_ADAPTER_TAG;                        
  using Algorithms = vtkm::cont::DeviceAdapterAlgorithm<DeviceAdapter>;         
  using Timer = vtkm::cont::Timer<DeviceAdapter>;                               
                                                                                
  // Extract the data needed to build the locator from the DataSet              
  vtkm::cont::DynamicCellSet cellSet = dataSet.GetCellSet();                    
  vtkm::cont::ArrayHandleVirtualCoordinates vertices =
      dataSet.GetCoordinateSystem().GetData();

  // Construct the search structure by providing the required data,
  // and then executing the Build method on the locator object.
  vtkm::cont::BoundingIntervalHierarchy locator =
      vtkm::cont::BoundingIntervalHierarchy(numPlanes, maxLeafNodes);
  locator.SetCellSet(cellSet);             
  locator.SetCoordinates(dataSet.GetCoordinateSystem());
  locator.Update();

  // Define the arrays for storing the output of queries                        
  vtkm::cont::ArrayHandle<vtkm::Id> cellIds;
  vtkm::cont::ArrayHandle<vtkm::Vec<vtkm::FlaotDefault, 3>> parametric;
                                                                                
  // Invoke the worklet by providing the locator as an ExecObject
  vtkm::worklet::DispatcherMapField<QueryCellIds>().Invoke(queryPoints,
                                                           locator,
                                                           cellIds,
                                                           parametric);
  // Continue to Process
}
\end{vtkmexample}


\section{Point Locators}

Point Locators in \VTKm 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 cell locators is a two step process.
The first step is to build the search structure.
This is done by instantiating one of the subclasses of \vtkmcont{PointLocator}, providing a coordinate system (usually from a \vtkmcont{DataSet}) representing the location of points that can later be found through queries, and then updating the structure.
Once the cell locator is built, it can be used in the execution environment within a filter or worklet.

\subsection{Building Point Locators}

All point Locators in \VTKm inherit from \vtkmcont{PointLocator}, which provides the basic interface for the required features of point locators.
This generic interface provides methods to set the coordinate system (with SetCoordinates and GetCoordinates) of training points.
Once the coordinates are provided, you may call Update to construct the search structures.
Although Update is called from the control environment, the search structure will be built on parallel devices

\VTKm currently exposes the implementations of the following Point Locators.

\subsubsection{Uniform Grid Point Locator}

The \vtkmcont{PointLocatorUniformGrid} point locator is based on the uniform grid search structure.
It divides the search space into a uniform grid of bins.
A search for a point near a given coordinate starts in the bin containing the search coordinates.
If a candidate point is not found in that bin, points are searched in an expanding neighborhood of grid bins.
The constructor of \vtkmcont{PointLocatorUniformGrid} takes three parameters: the minimum position of the bounding box of the search space, the maximum position of the bounding box, and the number of grid cells to divide the search space.

\fix{TODO: Compile this example.}
\begin{vtkmexample}{Building a \protect\vtkmcont{PointLocatorUniformGrid}.}
// Create a PointLocatorUniformGrid with bounding box of 0, 0, 0 to
// 10, 10, 10 and divide the space into a 5 by 5 by 5 3D grid.
vtkm::cont::PointLocatorUniformGrid locator(
      { 0.0f, 0.0f, 0.0f }, { 10.0f, 10.0f, 10.0f }, { 5, 5, 5 });
// Set the position training points    
locator.SetCoords(coord);
// Build the search structure
locator.Build();
\end{vtkmexample}

\subsection{Using Point Locators in a Worklet}

The \vtkmcont{PointLocator} interface implements \vtkmcont{ExecutionObjectBase}.
This means that any \textidentifier{PointLocator} can be used in worklets as an \sigtag{ExecObject} argument (as defined in the \controlsignature).
See Section~\ref{sec:ExecutionObjects} for information on \sigtag{ExecObject} arguments to worklets.

When a \vtkmcont{PointLocator} class is passed as an \sigtag{ExecObject} argument to a worklet \classmember{Invoke}, the worklet receives a pointer to a \vtkmexec{PointLocator} object.
\vtkmexec{PointLocator} provides a \classmember{FindNearestNeighbor} method that identifies the nearest neighbor point given a coordinate in space.

\begin{commonerrors}
  Note that \vtkmcont{PointLocator} and \vtkmexec{PointLocator} are different objects with different interfaces despite the similar names.
\end{commonerrors}

The \vtkmexec*{CellLocator}[FindNearestNeighbor] method takes 3 arguments.
The first argument is an input query point.
The second argument is used to return the id of the nearest neighbor point (or -1 if the point is not found, for example, in the case of an empty set of data set points).
The third argument is used to return the squared distance for the query point to its nearest neighbor.

\fix{TODO: Compile this example.}
\begin{vtkmexample}{Using a \textidentifier{PointLocator} in a worklet.}
class PointLocatorUniformGridWorklet : public vtkm::worklet::WorkletMapField
{
public:
  using ControlSignature = void (FieldIn<> qcIn,
                                 ExecObject locator,
                                 FieldOut<> nnIdOut,
                                 FieldOut<> nnDistOut);

  using ExecutionSignature = void (_1, _2, _3, _4);

  VTKM_CONT
  PointLocatorUniformGridWorklet() {}

  template <typename CoordiVecType,
            typename Locator,
            typename IndexType,
            typename CoordiType>
  VTKM_EXEC void operator()(const CoordiVecType& qc,
                            const Locator& locator,
                            IndexType& nnIdOut,
                            CoordiType& nnDis) const
  {
    locator->FindNearestNeighbor(qc, nnIdOut, nnDis);
  }
};
///// randomly generate testing points/////
std::vector<vtkm::Vec<vtkm::Float32, 3>> qcVec;
for (vtkm::Int32 i = 0; i < nTestingPoint; i++)
{
  qcVec.push_back(vtkm::make_Vec(dr(dre), dr(dre), dr(dre)));
}
auto qc_Handle = vtkm::cont::make_ArrayHandle(qcVec);

vtkm::cont::ArrayHandle<vtkm::Id> nnId_Handle;
vtkm::cont::ArrayHandle<vtkm::Float32> nnDis_Handle;

PointLocatorUniformGridWorklet pointLocatorUniformGridWorklet;
vtkm::worklet::DispatcherMapField<PointLocatorUniformGridWorklet, DeviceAdapter>
  locatorDispatcher(pointLocatorUniformGridWorklet);
locatorDispatcher.Invoke(qc_Handle, locator, nnId_Handle, nnDis_Handle);
\end{vtkmexample}
