% -*- latex -*-

\chapter{Data Sets}
\label{chap:DataSets}
\label{chap:DataSet}

\index{data set|(}

A \keyterm{data set}, implemented with the \vtkmcont{DataSet} class,
contains and manages the geometric data structures that VTK-m operates on.
A data set comprises the following 3 data structures.

\begin{description}
\item[Cell Set] \index{cell set} A cell set describes topological
  connections. A cell set defines some number of points in space and how
  they connect to form cells, filled regions of space. A data set must have
  at least one cell set, but can have more than one cell set defined. This
  makes it possible to define groups of cells with different properties.
  For example, a simulation might model some subset of elements as boundary
  that contain properties the other elements do not. Another example is the
  representation of a molecule that requires atoms and bonds, each having
  very different properties associated with them.
\item[Field] \index{field} A field describes numerical data associated with
  the topological elements in a cell set. The field is represented as an
  array, and each entry in the field array corresponds to a topological
  element (point, edge, face, or cell). Together the cell set topology and
  discrete data values in the field provide an interpolated function
  throughout the volume of space covered by the data set. A cell set can
  have any number of fields.
\item[Coordinate System] \index{coordinate system} A coordinate system is a
  special field that describes the physical location of the points in a
  data set. Although it is most common for a data set to contain a single
  coordinate system, VTK-m supports data sets with no coordinate system
  such as abstract data structures like graphs that might not have
  positions in a space. \textidentifier{DataSet} also supports multiple
  coordinate systems for data that have multiple representations for
  position. For example, geospatial data could simultaneously have
  coordinate systems defined by 3D position, latitude-longitude, and any
  number of 2D projections.
\end{description}

In addition to the base \vtkmcont{DataSet}, \VTKm provides \vtkmcont{MultiBlock} to represent multi-block data sets.
A \textidentifier{MultiBlock} is implemented as a collection of \textidentifier{DataSet} objects.
Multi-block data sets are described later in Section~\ref{sec:DataSets:MultiBlock}.

\section{Building Data Sets}
\label{sec:DataSets:Building}

\index{data set!building|(}

Before we go into detail on the cell sets, fields, and coordinate systems
that make up a data set in VTK-m, let us first discuss how to build a data
set. One simple way to build a data set is to load data from a file using
the \vtkmio{} module. Reading files is discussed in detail in
Chapter~\ref{chap:FileIO}.

This section describes building data sets of different types using a set of
classes named \textidentifier{DataSetBuilder*}, which provide a convenience layer
on top of \vtkmcont{DataSet} to make it easier to create data sets.

\subsection{Creating Uniform Grids}

\index{uniform grid}
\index{regular grid}
\index{image}

Uniform grids are meshes that have a regular array structure with points
uniformly spaced parallel to the axes. Uniform grids are also sometimes
called regular grids or images.

The \vtkmcont{DataSetBuilderUniform} class can be used to easily create 2-
or 3-dimensional uniform grids. \textidentifier{DataSetBuilderUniform} has
several versions of a method named \classmember{Create} that takes the number
of points in each dimension, the origin, and the spacing. The origin is the
location of the first point of the data (in the lower left corner), and the
spacing is the distance between points in the x, y, and z directions. The
\classmember{Create} methods also take an optional name for the coordinate
system and an optional name for the cell set.

The following example creates a \vtkmcont{DataSet} containing a uniform
grid of $101 \times 101 \times 26$ points.

\vtkmlisting{Creating a uniform grid.}{CreateUniformGrid.cxx}

If not specified, the origin will be at the coordinates $(0,0,0)$ and the
spacing will be $1$ in each direction. Thus, in the previous example the
width, height, and depth of the mesh in physical space will be $100$,
$100$, and $25$, respectively, and the mesh will be centered at $(50, 50,
12.5)$. Let us say we actually want a mesh of the same dimensions, but we
want the $z$ direction to be stretched out so that the mesh will be the
same size in each direction, and we want the mesh centered at the origin.

\vtkmlisting{Creating a uniform grid with custom origin and spacing.}{CreateUniformGridCustomOriginSpacing.cxx}

\subsection{Creating Rectilinear Grids}

\index{rectilinear grid}

A rectilinear grid is similar to a uniform grid except that a rectilinear
grid can adjust the spacing between adjacent grid points. This allows the
rectilinear grid to have tighter sampling in some areas of space, but the
points are still constrained to be aligned with the axes and each other. The
irregular spacing of a rectilinear grid is specified by providing a
separate array each for the x, y, and z coordinates.

The \vtkmcont{DataSetBuilderRectilinear} class can be used to easily create
2- or 3-dimensional rectilinear grids.
\textidentifier{DataSetBuilderRectilinear} has several versions of a method
named \classmember{Create} that takes these coordinate arrays and builds a
\vtkmcont{DataSet} out of them. The arrays can be supplied as either
standard C arrays or as \textcode{std::vector} objects, in which case the
data in the arrays are copied into the \textidentifier{DataSet}. These
arrays can also be passed as \textidentifier{ArrayHandle} objects, in which
case the data are shallow copied.

The following example creates a \vtkmcont{DataSet} containing a rectilinear
grid with $201 \times 201 \times 101$ points with different irregular
spacing along each axis.

\vtkmlisting{Creating a rectilinear grid.}{CreateRectilinearGrid.cxx}

\subsection{Creating Explicit Meshes}

\index{explicit mesh}
\index{unstructured grid}

An explicit mesh is an arbitrary collection of cells with arbitrary
connections. It can have multiple different types of cells. Explicit meshes
are also known as unstructured grids.

The cells of an explicit mesh are defined by providing the shape, number of
indices, and the points that comprise it for each cell. These three things
are stored in separate arrays. Figure~\ref{fig:ExplicitMesh} shows an
example of an explicit mesh and the arrays that can be used to define it.

\begin{figure}[htb]
  \centering
  \includegraphics{images/ExplicitCellConnections}
  \caption{An example explicit mesh.}
  \label{fig:ExplicitMesh}
\end{figure}

The \vtkmcont{DataSetBuilderExplicit} class can be used to create data sets
with explicit meshes. \textidentifier{DataSetBuilderExplicit} has several
versions of a method named \classmember{Create}. Generally, these methods take
the shapes, number of indices, and connectivity arrays as well as an array
of point coordinates. These arrays can be given in \textcode{std::vector}
objects, and the data are copied into the \textidentifier{DataSet} created.

The following example creates a mesh like the one shown in
Figure~\ref{fig:ExplicitMesh}.

\vtkmlisting{Creating an explicit mesh with \textidentifier{DataSetBuilderExplicit}.}{CreateExplicitGrid.cxx}

Often it is awkward to build your own arrays and then pass them to
\textidentifier{DataSetBuilderExplicit}. There also exists an alternate
builder class named \vtkmcont{DataSetBuilderExplicitIterative} that allows
you to specify each cell and point one at a time rather than all at once.
This is done by calling one of the versions of \classmember{AddPoint} and one
of the versions of \classmember{AddCell} for each point and cell,
respectively. The next example also builds the mesh shown in
Figure~\ref{fig:ExplicitMesh} except this time using
\textidentifier{DataSetBuilderExplicitIterative}.

\vtkmlisting{Creating an explicit mesh with \textidentifier{DataSetBuilderExplicitIterative}.}{CreateExplicitGridIterative.cxx}

\subsection{Add Fields}

In addition to creating the geometric structure of a data set, it is
usually important to add fields to the data. Fields describe numerical data
associated with the topological elements in a cell. They often represent a
physical quantity (such as temperature, mass, or volume fraction) but can
also represent other information (such as indices or classifications).

The easiest way to define fields in a data set is to use the
\vtkmcont{DataSetFieldAdd} class. This class works on
\textidentifier{DataSet}s of any type. It has methods named
\classmember{AddPointField} and \classmember{AddCellField} that define a field
for either points or cells. Every field must have an associated field name.

Both \classmember{AddPointField} and \classmember{AddCellField} are overloaded to
accept arrays of data in different structures. Field arrays can be passed
as standard C arrays or as \textcode{std::vector}s, in which case the data
are copied. Field arrays can also be passed in a
\textidentifier{ArrayHandle}, in which case the data are not copied.

The following (somewhat contrived) example defines fields for a uniform
grid that identify which points and cells are on the boundary of the mesh.

\vtkmlisting{Adding fields to a \textidentifier{DataSet}.}{AddFieldData.cxx}

\index{data set!building|)}

\section{Cell Sets}
\label{sec:DataSets:CellSets}

\index{cell set|(}
\index{data set!cell set|see{cell set}}

A cell set determines the topological structure of the data in a data set.
Fundamentally, any cell set is a collection of cells, which typically (but
not always) represent some region in space. 3D cells are made up of
\index{point}\index{shape!point}\index{cell!point}points,
\index{edge}\index{shape!edge}\index{cell!edge}edges, and
\index{face}\index{shape!face}\index{cell!face}faces. (2D cells have only points and edges,
and 1D cells have only points.) Figure~\ref{fig:CellTopology} shows the
relationship between a cell's shape and these topological elements. The
arrangement of these points, edges, and faces is defined by the
\index{shape}\index{cell set!shape}\index{cell shape}\keyterm{shape} of the
cell, which prescribes a specific ordering of each. The basic cell shapes
provided by VTK-m are discussed in detail in
Section~\ref{sec:CellShapeTagsIds} starting on
page~\pageref{sec:CellShapeTagsIds}.

\begin{figure}[htb]
  \centering
  \includegraphics{images/CellConstituents}
  \caption{The relationship between a cell shape and its topological
    elements (points, edges, and faces).}
  \label{fig:CellTopology}
\end{figure}

There are multiple ways to express the connections of a cell set, each with
different benefits and restrictions. These different cell set types are
managed by different cell set classes in VTK-m. All VTK-m cell set classes
inherit from \vtkmcont{CellSet}. The two basic types of cell sets are
structured and explicit, and there are several variations of these types.

\subsection{Structured Cell Sets}

\index{cell set!structured|(}
\index{structured cell set|(}

A \vtkmcont{CellSetStructured} defines a 1-, 2-, or 3-dimensional grid of
points with lines, quadrilaterals, or hexahedra, respectively, connecting
them. The topology of a \textidentifier{CellSetStructured} is specified by
simply providing the dimensions, which is the number of points in the $i$,
$j$, and $k$ directions of the grid of points. The number of points is
implicitly $i \times j \times k$ and the number of cells is implicitly
$(i-1) \times (j-1) \times (k-1)$ (for 3D grids).
Figure~\ref{fig:CellSetStructured} demonstrates this arrangement.

\begin{figure}[htb]
  \centering
  \includegraphics{images/StructuredCellSet}
  \caption{The arrangement of points and cells in a 3D structured grid.}
  \label{fig:CellSetStructured}
\end{figure}

The big advantage of using \vtkmcont{CellSetStructured} to define a cell
set is that it is very space efficient because the entire topology can be
defined by the three integers specifying the dimensions. Also algorithms
can be optimized for \textidentifier{CellSetStructured}'s regular nature.
However, \textidentifier{CellSetStructured}'s strictly regular grid
structure also limits its applicability. A structured cell set can only be
a dense grid of lines, quadrilaterals, or hexahedra. It cannot represent
irregular data well.

Many data models in other software packages, such as the one for VTK, make
a distinction between uniform, rectilinear, and curvilinear grids. VTK-m's
cell sets do not. All three of these grid types are represented by
\textidentifier{CellSetStructured}. This is because in a VTK-m data set the
cell set and the coordinate system are defined independently and used
interchangeably. A structured cell set with uniform point coordinates makes
a uniform grid. A structured cell set with point coordinates defined
irregularly along coordinate axes makes a rectilinear grid. And a
structured cell set with arbitrary point coordinates makes a curvilinear
grid. The point coordinates are defined by the data set's coordinate system,
which is discussed in Section~\ref{sec:DataSets:CoordinateSystems} starting
on page~\pageref{sec:DataSets:CoordinateSystems}.

\index{structured cell set|)}
\index{cell set!structured|)}

\subsection{Explicit Cell Sets}
\label{sec:ExplicitCellSets}

\index{explicit cell set|(}
\index{cell set!explicit|(}

A \vtkmcont{CellSetExplicit} defines an irregular collection of cells. The
cells can be of different types and connected in arbitrary ways. This is
done by explicitly providing for each cell a sequence of points that
defines the cell.

An explicit cell set is defined with a minimum of three arrays. The first
array identifies the shape of each cell. (Cell shapes are discussed in
detail in Section~\ref{sec:CellShapeTagsIds} starting on
page~\pageref{sec:CellShapeTagsIds}.) The second array identifies how many
points are in each cell. The third array has a sequence of point indices
that make up each cell. Figure~\ref{fig:CellSetExplicit} shows a simple
example of an explicit cell set.

\begin{figure}[htb]
  \centering
  \includegraphics{images/ExplicitCellConnections}
  \caption{Example of cells in a \textidentifier{CellSetExplict} and the
    arrays that define them.}
  \label{fig:CellSetExplicit}
\end{figure}

An explicit cell set may also have other topological arrays such as an
array of offsets of each cell into the connectivity array or an array of
cells incident on each point. Although these arrays can be provided, they
are optional and can be internally derived from the shape, num indices, and
connectivity arrays.

\vtkmcont{ExplicitCellSet} is a powerful representation for a cell set
because it can represent an arbitrary collection of cells. However, because
all connections must be explicitly defined,
\textidentifier{ExplicitCellSet} requires a significant amount of memory to
represent the topology.

\index{cell set!single type|(}
\index{explicit cell set!single type|(}
\index{single type cell set|(}

An important specialization of an explicit cell set is
\vtkmcont{CellSetSingleType}. \textidentifier{CellSetSingleType} is an
explicit cell set constrained to contain cells that all have the same shape
and all have the same number of points. So for example if you are creating
a surface that you know will contain only triangles,
\textidentifier{CellSetSingleType} is a good representation for these data.

Using \textidentifier{CellSetSingleType} saves memory because the array of
cell shapes and the array of point counts no longer need to be stored.
\textidentifier{CellSetSingleType} also allows VTK-m to skip some
processing and other storage required for general explicit cell sets.

\index{single type cell set|)}
\index{explicit cell set!single type|)}
\index{cell set!single type|)}

\index{cell set!explicit|)}
\index{explicit cell set|)}

\subsection{Cell Set Permutations}

\index{permutation cell set|(}
\index{cell set!permutation|(}

A \vtkmcont{CellSetPermutation} rearranges the cells of one cell set to
create another cell set. This restructuring of cells is not done by copying
data to a new structure. Rather, \textidentifier{CellSetPermutation}
establishes a look-up from one cell structure to another. Cells are permuted
on the fly while algorithms are run.

A \textidentifier{CellSetPermutation} is established by providing a mapping
array that for every cell index provides the equivalent cell index in the
cell set being permuted. \textidentifier{CellSetPermutation} is most often
used to mask out cells in a data set so that algorithms will skip over
those cells when running.

\begin{didyouknow}
  Although \textidentifier{CellSetPermutation} can mask cells, it cannot
  mask points. All points from the original cell set are available in the
  permuted cell set regardless of whether they are used.
\end{didyouknow}

The following example uses \vtkmcont{CellSetPermutation} with a counting
array to expose every tenth cell. This provides a simple way to subsample a
data set.

\vtkmlisting{Subsampling a data set with \textidentifier{CellSetPermutation}.}{CreateCellSetPermutation.cxx}

\index{cell set!permutation|)}
\index{permutation cell set|)}

\subsection{Dynamic Cell Sets}

\index{dynamic cell set|(}
\index{cell set!dynamic|(}

\vtkmcont{DataSet} must hold an arbitrary collection of \vtkmcont{CellSet}
objects, which it cannot do while knowing their types at compile time. To
manage storing \textidentifier{CellSet}s without knowing their types,
\textidentifier{DataSet} actually holds references using
\vtkmcont{DynamicCellSet}.

\textidentifier{DynamicCellSet} is similar in nature to
\textidentifier{DynamicArrayHandle} except that it, of course, holds
\textidentifier{CellSet}s instead of \textidentifier{ArrayHandle}s. The
interface for the two classes is similar, and you should review the
documentation for \textidentifier{DynamicArrayHandle} (in
Chapter~\ref{chap:DynamicArrayHandle} starting on
page~\pageref{chap:DynamicArrayHandle}) to understand
\textidentifier{DynamicCellSet}.

\vtkmcont{DynamicCellSet} has a method named \classmember{CastToBase} that
returns a const reference to the held cell set as the abstract
\textidentifier{CellSet} class. This can be used to easily access the
virtual methods in the \textidentifier{CellSet} interface. You can also
create a new instance of a cell set with the same type using the
\classmember{NewInstance} method.

The \classmember*[DynamicCellSet]{IsType} method can be used to determine whether the cell set held in the dynamic cell set is of a given type.
If the cell set type is known, \classmember*[DynamicCellSet]{Cast} can be used to safely downcast the cell set object, or \classmember[DynamicCellSet]{CopyTo} can be used to safely copy to a reference of the appropriate type.

When a typed version of the cell set stored in the
\textidentifier{DynamicCellSet} is needed but the type is not known, which
happens regularly in the internal workings of VTK-m, the
\classmember{CastAndCall} method can be used to make this transition.
\classmember{CastAndCall} works by taking a functor and calls it with the
appropriately cast cell set object.

The \classmember{CastAndCall} method works by attempting to cast to a known
set of types. This set of types used is defined by the macro
\vtkmmacro{VTKM\_DEFAULT\_CELL\_SET\_LIST\_TAG}, which is declared in
\vtkmheader{vtkm/cont}{CellSetListTag.h}. This list can be overridden
globally by defining the \vtkmmacro{VTKM\_DEFAULT\_CELL\_SET\_LIST\_TAG}
macro \emph{before} any VTK-m headers are included.

The set of types used in a \classmember{CastAndCall} can also be changed only
for a particular instance of a dynamic cell set by calling its
\classmember{ResetCellSetList}. This method takes a list of cell types and
returns a new dynamic array handle of a slightly different type that will
use this new list of cells for dynamic casting.

\index{cell set!dynamic|)}
\index{dynamic cell set|}

\subsection{Blocks and Assemblies}

Rather than just one cell set, a \vtkmcont{DataSet} can hold multiple cell
sets. This can be used to construct multiblock data structures or
assemblies of parts. Multiple cell sets can also be used to represent
subsets of the data with particular properties such as all cells filled
with a material of a certain type. Or these multiple cells might represent
particular features in the data, such as the set of faces representing a
boundary in the simulation.

\subsection{Zero Cell Sets}

It is also possible to construct a \vtkmcont{DataSet} that contains no cell
set objects whatsoever. This can be used to manage data that does not
contain any topological structure. For example, a collection of series that
come from columns in a table could be stored as multiple fields in a data
set with no cell set.

\index{cell set|)}

\section{Fields}
\label{sec:DataSets:Fields}

\index{field|(}
\index{data set!field|see{field}}

A field on a data set provides a value on every point in space on the mesh.
Fields are often used to describe physical properties such as pressure,
temperature, mass, velocity, and much more. Fields are represented in a
VTK-m data set as an array where each value is associated with a particular
element type of a mesh (such as points or cells). This association of field
values to mesh elements and the structure of the cell set determines how
the field is interpolated throughout the space of the mesh.

Fields are manged by the \vtkmcont{Field} class. \textidentifier{Field}
holds its data with a \textidentifier{DynamicArrayHandle}, which itself is
a container for an \textidentifier{ArrayHandle}. \textidentifier{Field}
also maintains the association and, optionally, the name of a cell set for
which the field is valid.

The data array can be retrieved as a \textidentifier{DynamicArrayHandle}
using the \classmember{GetData} method of \textidentifier{Field}.
\index{range!field}\textidentifier{Field} also has a convenience method named
\classmember{GetRange} that finds the range of values stored in the field
array.
The returned value of \classmember{GetRange} is an \textidentifier{ArrayHandle} containing \vtkm{Range} values.
The \textidentifier{ArrayHandle} will have as many values as components in the field.
So, for example, calling \classmember{GetRange} on a scalar field will return an \textidentifier{ArrayHandle} with exactly 1 entry in it.
Calling \classmember{GetRange} on a field of 3D vectors will return an \textidentifier{ArrayHandle} with exactly 3 entries corresponding to each of the components in the range.

\index{field|}

\section{Coordinate Systems}
\label{sec:DataSets:CoordinateSystems}

\index{coordinate system|(}
\index{data set!coordinate system|see{coordinate system}}

A coordinate system determines the location of a mesh's elements in space.
The spatial location is described by providing a 3D vector at each point
that gives the coordinates there. The point coordinates can then be
interpolated throughout the mesh.

Coordinate systems are managed by the \vtkmcont{CoordinateSystem} class. In
actuality, a coordinate system is just a field with a special meaning, and
so the \textidentifier{CoordinateSystem} class inherits from the
\textidentifier{Field} class. \textidentifier{CoordinateSystem} constrains
the field to be associated with points and typically has 3D floating point
vectors for values.

In addition to all the methods provided by the \textidentifier{Field} superclass, the \textidentifier{CoordinateSystem} also provides a \classmember{GetBounds} convenience method that returns a \vtkm{Bounds} object giving the spatial bounds of the coordinate system.

It is typical for a \textidentifier{DataSet} to have one coordinate system
defined, but it is possible to define multiple coordinate systems. This is
helpful when there are multiple ways to express coordinates. For example,
positions in geographic may be expressed as Cartesian coordinates or as
latitude-longitude coordinates. Both are valid and useful in different
ways.

It is also valid to have a \textidentifier{DataSet} with no coordinate
system. This is useful when the structure is not rooted in physical space.
For example, if the cell set is representing a graph structure, there might
not be any physical space that has meaning for the graph.

\index{coordinate system|)}


\section{Multi-Block Data}
\label{sec:DataSets:MultiBlock}

\index{multiblock|(}
\index{data set!multiblock|see{multiblock}}

A multi-block data set, implemented with \vtkmcont{MultiBlock}, comprises a set of \vtkmcont{DataSet} objects.
The \textidentifier{MultiBlock} interface allows for adding, inserting, and replacing \textidentifier{DataSet}s in its list with the \classmember{AddBlock} (or \classmember{AddBlocks}), \classmember{InsertBlock}, and \classmember{ReplaceBlock} methods, respectively.
The \classmember{GetBlocks} method returns a list of \textidentifier{DataSet} objects in a \textcode{std::vector}.

The following example creates a \vtkmcont{MultiBlock} containing two uniform grid data sets.

\vtkmlisting{Creating a \textidentifier{MultiBlock}.}{CreateMultiBlock.cxx}

It is always possible to retrieve the independent blocks in a \textidentifier{MultiBlock}, from which you can iterate and get information about the data.
However, \VTKm provides several helper functions to collect metadata information about the collection as a whole.
However, \textidentifier{MultiBlock} also offers several helper methods to collect metadata information about the collection as a whole.
Each function is in its own respective header file.

\begin{description}
\item[\vtkmcont{BoundsCompute}]
  Queries the bounds of all the \textidentifier{DataSet}s contained in the given \textidentifier{MultiBlock} and returns a \vtkm{Bounds} object encompassing the conglomerate data.
\item[\vtkmcont{BoundsGlobalCompute}]
  An MPI version of \textidentifier{BoundsCompute} that also finds the bounds around the conglomerate data across all processes.
  All MPI processes must call this method.
\item[\vtkmcont{FieldRangeCompute}]
  Given a \textidentifier{MultiBlock}, the name of a field, and (optionally) an association of the field, returns the minimum and maximum value of that field over all the contained blocks.
  The result is returned in a \textidentifier{ArrayHandle} of \vtkm{Range} objects in the same manner as the \vtkmcont{Field}[GetRange] method (see Section~\ref{sec:DataSets:Fields}).
\item[\vtkmcont{FieldRangeGlobalCompute}]
  An MPI version of \textidentifier{FieldRangeCompute} that also finds the field ranges over all blocks on all processes.
  All MPI processes must call this method.
\end{description}

The following example illustrates a spatial bounds query and a field range query on a \vtkm{MultiBlock}.

\vtkmlisting{Queries on a \textidentifier{MultiBlock}.}{QueryMultiBlock.cxx}

\begin{didyouknow}
  The aforementioned functions for querying a \textidentifier{MultiBlock} object also work on \textidentifier{DataSet} objects.
  This is particularly useful with the \textidentifier{BoundsGlobalCompute} and \textidentifier{FieldRangeGlobalCompute} to manage distributed parallel objects.
\end{didyouknow}

Filters can be executed on \textidentifier{MultiBlock} objects in a similar way they are executed on \textidentifier{DataSet} objects.
In both cases, the \classmember{Execute} method is called on the filter giving data object as an argument.

\vtkmlisting{Applying a filter to multi block data.}{FilterMultiBlock.cxx}

\index{multiblock|)}

\index{data set|)}
