% -*- 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 \textcode{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}

\index{locator!cell|(}
\index{cell locator|(}

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 \textidentifier{CellLocator} classes, 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 share the same basic interface for the required features of cell locators.
This generic interface provides methods to set the cell set (with \classmember*{CellLocator}{SetCellSet} and \classmember*{CellLocator}{GetCellSet}) and to set the coordinate system (with \classmember*{CellLocator}{SetCoordinates} and \classmember*{CellLocator}{GetCoordinates}).
Once the cell set and coordinates are provided, you may call \classmember*{CellLocator}{Update} to construct the search structures.
Although \classmember*{CellLocator}{Update} is called from the control environment, the search structure will be built on parallel devices.

\vtkmlisting{Constructing a \textidentifier{CellLocator}.}{ConstructCellLocator.cxx}

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

\begin{description}
\item[\vtkmcont{CellLocatorGeneral}] \index{cell locator!general}
  This locator will automatically select another locator to use as its implementation.
  \textidentifier{CellLocatorGeneral} allows you to automatically select cell locators optimized for certain cell structures without knowing the cell set type.
  You can change how \textidentifier{CellLocatorGeneral} selects a \textidentifier{CellLocator} by providing a function to the \classmember*{CellLocatorGeneral}{SetConfigurator} method.
  If no configurator is set, then a default one is used.
\item[\vtkmcont{CellLocatorUniformGrid}] \index{cell locator!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 \textidentifier{CellSetStructured} and a coordinate system using an \textidentifier{ArrayHandleUniformPointCoordinates} for its data.
\item[\vtkmcont{CellLocatorRectilinearGrid}] \index{cell locator!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 \textidentifier{CellSetStructured} and a coordinate system using an \textidentifier{ArrayHandleCartesianProduct} for its data.
\item[\vtkmcont{CellLocatorTwoLevel}] \index{cell locator!two level}
  This locator builds a 2-level hierarchy of uniform bins.
  The first level is a coarse partitioning of the space.
  Each bin in the first level has a second grid who's size depends on the number of cells in the first level.
  The density (number of cells expected in each bin) for each level can be set with \classmember*{CellLocatorTwoLevel}{SetDensityL1} and \classmember*{CellLocatorTwoLevel}{SetDensityL2}.
  Their default values are 32 and 2, respectively.
\item[\vtkmcont{CellLocatorBoundingIntervalHierarchy}] \index{cell locator!bounding interval hierarchy}
  This locator is based on the bounding interval hierarchy spatial search structure.
  \textidentifier{CellLocatorBoundingIntervalHierarchy} 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 set through the \classmember*{CellLocatorBoundingIntervalHierarchy}{SetNumberOfPlanes} and \classmember*{CellLocatorBoundingIntervalHierarchy}{SetMaxLeafSize} methods.
\item[\vtkmcont{CellLocatorChooser}] \index{cell locator!chooser} %
  This locator is similar to \textidentifier{CellLocatorGeneral} in that it automatically selects an appropriate locator based on the type of cell structure being used.
  However, unlike the other locator, \textidentifier{CellLocatorChooser} is a templated class that chooses the correct locator based on the cell set type and the coordinates array type provided as template arguments.
  This means that you have to know the data types at compile time.
  \textidentifier{CellLocatorChooser} is a good choice in applications where you know your \textidentifier{DataSet} is of a particular type.
\end{description}

\subsection{Using Cell Locators in a Worklet}

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

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

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

The \classmember{CellLocator}{FindCell} method takes 3 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).
\classmember*{CellLocator}{FindCell} returns an \textidentifier{ErrorCode} to indicate the status of the query.
If the cell and the location within the cell are found, \classmember{ErrorCode}{Success} is returned.
If the point is not inside any cell, \classmember{ErrorCode}{CellNotFound} is likely to be returned.

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

\vtkmlisting{Using a \textidentifier{CellLocator} in a worklet.}{UseCellLocator.cxx}

\index{cell locator|)}
\index{locator!cell|)}

\section{Point Locators}

\index{locator!point|(}
\index{point locator|(}

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 point locators is a two step process.
The first step is to build the search structure.
This is done by instantiating one of the \vtkmcont{PointLocator} classes, 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 point 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 share the same basic interface for the required features of point locators.
This generic interface provides methods to set the coordinate system (with \classmember*{PointLocator}{SetCoordinates} and \classmember*{PointLocator}{GetCoordinates}) of training points.
Once the coordinates are provided, you may call \classmember*{PointLocator}{Update} to construct the search structures.
Although \classmember*{PointLocator}{Update} is called from the control environment, the search structure will be built on parallel devices

\vtkmlisting{Constructing a \textidentifier{PointLocator}.}{ConstructPointLocator.cxx}

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

\begin{description}
\item[\vtkmcont{PointLocatorSparseGrid}] \index{point locator!sparse grid}
  This 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 size of the grid used by the locator to partition the space can be set with \classmember*{PointLocatorSparseGrid}{SetNumberOfBins}.
  By default, \textidentifier{PointLocatorSparseGrid} uses a $32^3$ grid.
  It is also possible to set the physical space over which the search space is constructed with the \classmember*{PointLocatorSparseGrid}{SetRange} method. If the range is not set, it will automatically be set to the space of the coordinates.
\end{description}


\subsection{Using Point Locators in a Worklet}

The \textidentifier{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 Chapter \ref{chap:ExecutionObjects} for information on \sigtag{ExecObject} arguments to worklets.

When a \vtkmcont{PointLocator} class is passed as an \sigtag{ExecObject} argument to a worklet \textcode{Invoke}, the worklet receives a different object defined in the \vtkmexec{} namespace.
This \vtkmexec{PointLocator} object provides a \classmember*{PointLocator}{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 \classmember*{PointLocator}{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 no nearby point is 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.

\vtkmlisting{Using a \textidentifier{PointLocator} in a worklet.}{UsePointLocator.cxx}

\index{point locator|)}
\index{locator!point|)}
