% -*- latex -*-

\chapter{Generating Cell Sets}
\label{chap:GeneratingCellSets}

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

This chapter describes techniques for designing algorithms in \VTKm that generate cell sets to be inserted in a \vtkmcont{DataSet}.
Although Chapter~\ref{chap:DataSets} on data sets describes how to create a data set, including defining its set of cells, these are serial functions run in the control environment that are not designed for computing geometric structures.
Rather, they are designed for specifying data sets built from existing data arrays, from inherently slow processes (such as file I/O), or for small test data.
In this chapter we discuss how to write worklets that create new mesh topologies by writing data that can be incorporated into a \vtkmcont{CellSet}.

This chapter is constructed as a set of patterns that are commonly employed to build cell sets.
These techniques apply the worklet structures documented in Chapter \ref{chap:WorkletTypeReference}.
Although it is possible for these worklets to generate data of its own, the algorithms described here follow the more common use case of deriving one topology from another input data set.
This chapter is not (and cannot be) completely comprehensive by covering every possible mechanism for building cell sets.
Instead, we provide the basic and common patterns used in scientific visualization.


\section{Single Cell Type}
\label{sec:GeneratingCellSets:SingleType}

\index{CellSetSingleType!generate|(}

For our first example of algorithms that generate cell sets is one that creates a set of cells in which all the cells are of the same shape and have the same number of points.
Our motivating example is an algorithm that will extract all the edges from a cell set.
The resulting cell set will comprise a collection of line cells that represent the edges from the original cell set.
Since all cell edges can be represented as lines with two endpoints, we know all the output cells will be of the same type.
As we will see later in the example, we can use a \vtkmcont{CellSetSingleType} to represent the data.

It is rare that an algorithm generating a cell set will generate exactly one output cell for each input cell.
Thus, the first step in an algorithm generating a cell set is to count the number of cells each input item will create.
In our motivating example, this is the the number of edges for each input cell.

\vtkmlisting[ex:GenerateMeshConstantShapeCount]{A simple worklet to count the number of edges on each cell.}{GenerateMeshConstantShapeCount.cxx}

This count array generated in Example~\ref{ex:GenerateMeshConstantShapeCount} can be used in a \vtkmworklet{ScatterCounting} of a subsequent worklet that generates the output cells.
(See Section~\ref{sec:WorkletScatter} for information on using a scatter with a worklet.)
We will see this momentarily.

\begin{didyouknow}
  If you happen to have an operation that you know will have the same count for every input cell, then you can skip the count step and use a \vtkmworklet{ScatterUniform} instead of \textidentifier{ScatterCount}.
  Doing so will simplify the code and skip some computation.
  We cannot use \textidentifier{ScatterUniform} in this example because different cell shapes have different numbers of edges and therefore different counts.
  However, if we were theoretically to make an optimization for 3D structured grids, we know that each cell is a hexahedron with 12 edges and could use a \textidentifier{ScatterUniform}\tparams{12} for that.
\end{didyouknow}

The second and final worklet we need to generate our wireframe cells is one that outputs the indices of an edge.
The worklet parenthesis' operator takes information about the input cell (shape and point indices) and an index of which edge to output.
The aforementioned \textidentifier{ScatterCounting} provides a \sigtag{VisitIndex} that signals which edge to output.
The worklet parenthesis operator returns the two indices for the line in, naturally enough, a \vtkm{Id2}.

\vtkmlisting[ex:GenerateMeshConstantShapeGenIndices]{A worklet to generate indices for line cells.}{GenerateMeshConstantShapeGenIndices.cxx}

Our ultimate goal is to fill a \vtkmcont{CellSetSingleType} object with the generated line cells.
A \textidentifier{CellSetSingleType} requires 4 items: the number of points, the constant cell shape, the constant number of points in each cell, and an array of connection indices.
The first 3 items are trivial.
The number of points can be taken from the input cell set as they are the same.
The cell shape and number of points are predetermined to be line and 2, respectively.
The last item, the array of connection indices, is what we are creating with the worklet in Example~\ref{ex:GenerateMeshConstantShapeGenIndices}.

However, there is a complication.
The connectivity array for \textidentifier{CellSetSingleType} is expected to be a flat array of \vtkm{Id} indices, not an array of \textidentifier{Vec} objects.
We could jump through some hoops adjusting the \textidentifier{ScatterCounting} to allow the worklet to output only one index of one cell rather than all indices of one cell.
But that would be overly complicated and inefficient.

A simpler approach is to use the \vtkmcont{ArrayHandleGroupVec} fancy array handle (described in Section~\ref{sec:GroupedVectorArrays}) to make a flat array of indices look like an array of \textidentifier{Vec} objects.
The following example shows what the \classmember*{FilterDataSet}{DoExecute} method in the associated filter would look like.
Note the use \textidentifier{make\_ArrayHandleGroupVec} when calling \classmember*{FilterDataSet}{Invoke} on line \ref{ex:GenerateMeshConstantShapeInvoke.cxx:InvokeEdgeIndices} to make this conversion.

\vtkmlisting[ex:GenerateMeshConstantShapeInvoke]{Invoking worklets to extract edges from a cell set.}{GenerateMeshConstantShapeInvoke.cxx}

Another feature to note in Example~\ref{ex:GenerateMeshConstantShapeInvoke} is that the method calls \classmember*{ScatterCounting}{GetOutputToInputMap} on the \textidentifier{Scatter} object it creates and squirrels the map array away for later use.
The reason for this behavior is to implement mapping fields that are attached on the input cells to the indices of the output.
In practice, \classmember*{FilterDataSet}{DoExecute} is called on \textidentifier{DataSet} objects to create new \textidentifier{DataSet} objects.
The method in Example \ref{ex:GenerateMeshConstantShapeInvoke} creates a new \textidentifier{CellSet}, but we also need a method to transform the \textidentifier{Field}s on the data set.
The saved \textcode{OutputToInputCellMap} array allows us to transform input fields to output fields.

The following example shows the implementation of \classmember*{FilterDataSet}{DoMapField} in the associated filter that takes this saved \textcode{OutputToInputCellMap} array and converts an array from an input cell field to an output cell field array.
Note that we can do this by using the \textcode{OutputToInputCellMap} as an index array in a \vtkmcont{ArrayHandlePermutation}.

\vtkmlisting[ex:GenerateMeshConstantShapeMapCellField]{Converting cell fields using a simple permutation.}{GenerateMeshConstantShapeMapCellField.cxx}


\section{Combining Like Elements}
\label{sec:GeneratingCellSets:CombiningLikeElements}

Our motivating example in Section~\ref{sec:GeneratingCellSets:SingleType} created a cell set with a line element representing each edge in some input data set.
However, on close inspection there is a problem with our algorithm: it is generating a lot of duplicate elements.
The cells in a typical mesh are connected to each other.
As such, they share edges with each other.
That is, the edge of one cell is likely to also be part of one or more other cells.
When multiple cells contain the same edge, the algorithm we created in Section~\ref{sec:GeneratingCellSets:SingleType} will create multiple overlapping lines, one for each cell using the edge, as demonstrated in Figure~\ref{fig:DuplicateEdges}.
What we really want is to have one line for every edge in the mesh rather than many overlapping lines.

\begin{figure}[htb]
  \centering
  \includegraphics{images/DuplicateEdges}
  \caption[Duplicate lines from extracted edges.]{
    Duplicate lines from extracted edges.
    Consider the small mesh at the left comprising a square and a triangle.
    If we count the edges in this mesh, we would expect to get 6.
    However, our na\"{i}ve implementation in Section~\ref{sec:GeneratingCellSets:SingleType} generates 7 because the shared edge (highlighted in red in the wireframe in the middle) is duplicated.
    As seen in the exploded view at right, one line is created for the square and one for the triangle.
  }
  \label{fig:DuplicateEdges}
\end{figure}

In this section we will re-implement the algorithm to generate a wireframe by creating a line for each edge, but this time we will merge duplicate edges together.
Our first step is the same as before.
We need to count the number of edges in each input cell and use those counts to create a \vtkmworklet{ScatterCounting} for subsequent worklets.
Counting the edges is a simple worklet.

\vtkmlisting[ex:GenerateMeshCombineLikeCount]{A simple worklet to count the number of edges on each cell.}{GenerateMeshCombineLikeCount.cxx}

In our previous version, we used the count to directly write out the lines.
However, before we do that, we want to identify all the unique edges and identify which cells share this edge.
\index{worklet types!reduce by key}
\index{reduce by key worklet}
This grouping is exactly the function that the reduce by key worklet type (described in Section~\ref{sec:ReduceByKey}) is designed to accomplish.
The principal idea is to write a ``key'' that uniquely identifies the edge.
The reduce by key worklet can then group the edges by the key and allow you to combine the data for the edge.

Thus, our goal of finding duplicate edges hinges on producing a key where two keys are identical if and only if the edges are the same.
One straightforward key is to use the coordinates in 3D space by, say, computing the midpoint of the edge.
The main problem with using this point coordinates approach is that a computer can hold a point coordinate only with floating point numbers of limited precision.
Computer floating point computations are notorious for providing slightly different answers when the results should be the same.
For example, if an edge has endpoints at $p_1$ and $p_2$ and two different cells compute the midpoint as $(p_1+p_2)/2$ and $(p_2+p_1)/2$, respectively, the answer is likely to be slightly different.
When this happens, the keys will not be the same and we will still produce 2 edges in the output.

Fortunately, there is a better choice for keys based on the observation that in the original cell set each edge is specified by endpoints that each have unique indices.
We can combine these 2 point indices to form a ``canonical'' descriptor of an edge (correcting for order).%
\footnote{Using indices to find common mesh elements is described by Miller et al. in ``Finely-Threaded History-Based Topology Computation'' (in \emph{Eurographics Symposium on Parallel Graphics and Visualization}, June 2014).}
\VTKm comes with a helper function, \vtkmexec{CellEdgeCanonicalId}, defined in \vtkmheader{vtkm/exec}{CellEdge.h}, to produce these unique edge keys as \vtkm{Id2}s.
Our second worklet produces these canonical edge identifiers.

\vtkmlisting[ex:GenerateMeshCombineLikeGenIds]{Worklet generating canonical edge identifiers.}{GenerateMeshCombineLikeGenIds.cxx}

Our third and final worklet generates the line cells by outputting the indices of each edge.
As hinted at earlier, this worklet is a reduce by key worklet (inheriting from \vtkmworklet{WorkletReduceByKey}).
When the worklet is invoked, \VTKm will collect the unique keys and call the worklet once for each unique edge.
Because there is no longer a consistent mapping from the generated lines to the elements of the input cell set, we need pairs of indices identifying the cells/edges from which the edge information comes.
We use these indices along with a connectivity structure produced by a \sigtag{WholeCellSetIn} to find the information about the edge.
As shown later, these indices of cells and edges can be extracted from the \textidentifier{ScatterCounting} used to execute the worklet back in Example~\ref{ex:GenerateMeshCombineLikeGenIds}.

As we did in Section~\ref{sec:GeneratingCellSets:SingleType}, this worklet writes out the edge information in a \vtkm{Id2} (which in some following code will be created with an \textidentifier{ArrayHandleGroupVec}).

\vtkmlisting[ex:GenerateMeshCombineLikeGenIndices]{A worklet to generate indices for line cells from combined edges.}{GenerateMeshCombineLikeGenIndices.cxx}

\begin{didyouknow}
  It so happens that the \vtkm{Id2}s generated by \textidentifier{CellEdgeCanonicalId} contain the point indices of the two endpoints, which is enough information to create the edge.
  Thus, in this example it would be possible to forgo the steps of looking up indices through the cell set.
  That said, this is more often not the case, so for the purposes of this example we show how to construct cells without depending on the structure of the keys.
\end{didyouknow}

With these 3 worklets, it is now possible to generate all the information we need to fill a \vtkmcont{CellSetSingleType} object.
A \textidentifier{CellSetSingleType} requires 4 items: the number of points, the constant cell shape, the constant number of points in each cell, and an array of connection indices.
The first 3 items are trivial.
The number of points can be taken from the input cell set as they are the same.
The cell shape and number of points are predetermined to be line and 2, respectively.

The last item, the array of connection indices, is what we are creating with the worklet in Example~\ref{ex:GenerateMeshCombineLikeGenIndices}.
The connectivity array for \textidentifier{CellSetSingleType} is expected to be a flat array of \vtkm{Id} indices, but the worklet needs to provide groups of indices for each cell (in this case as a \textidentifier{Vec} object).
To reconcile what the worklet provides and what the connectivity array must look like, we use the \vtkmcont{ArrayHandleGroupVec} fancy array handle (described in Section~\ref{sec:GroupedVectorArrays}) to make a flat array of indices look like an array of \textidentifier{Vec} objects.
The following example shows what the \classmember*{FilterDataSet}{DoExecute} method in the associated filter would look like.
Note the use of \textidentifier{make\_ArrayHandleGroupVec} when calling \classmember*{FilterDataSet}{Invoke} on line \ref{ex:GenerateMeshCombineLikeInvoke.cxx:InvokeEdgeIndices} to make this conversion.

\vtkmlisting[ex:GenerateMeshCombineLikeInvoke]{Invoking worklets to extract unique edges from a cell set.}{GenerateMeshCombineLikeInvoke.cxx}

Another feature to note in Example~\ref{ex:GenerateMeshCombineLikeInvoke} is that the method calls \classmember*{ScatterCounting}{GetOutputToInputMap} on the \textidentifier{Scatter} object it creates and squirrels it away for later use.
It also saves the \vtkmworklet{Keys} object created for later use.
The reason for this behavior is to implement mapping fields that are attached on the input cells to the indices of the output.
In practice, \classmember*{FilterDataSet}{DoExecute} is called on \textidentifier{DataSet} objects to create new \textidentifier{DataSet} objects.
The method in Example \ref{ex:GenerateMeshCombineLikeInvoke} creates a new \textidentifier{CellSet}, but we also need a method to transform the \textidentifier{Field}s on the data set.
The saved \textcode{OutputToInputCellMap} array and \textidentifier{Keys} object allow us to transform input fields to output fields.

The following example shows the implementation of \classmember*{FilterDataSet}{DoMapField} in the associated filter that takes these saved objects and converts an array from an input cell field to an output cell field array.
Because in general there are several cells that contribute to each edge/line in the output, we need a method to combine all these cell values to one.
The most appropriate combination is likely an average of all the values.
Because this is a common operation, \VTKm provides the \vtkmworklet{AverageByKey} class to help perform exactly this operation.
\textidentifier{AverageByKey} provides a \textcode{Run} method that takes a \textidentifier{Keys} object, an array of in values, and a device adapter tag and produces and array of values averaged by key.

\vtkmlisting[ex:GenerateMeshCombineLikeMapCellField]{Converting cell fields that average collected values.}{GenerateMeshCombineLikeMapCellField.cxx}


\section{Faster Combining Like Elements with Hashes}
\label{sec:GeneratingCellSets:FasterCombiningLikeElements}

In the previous two sections we constructed worklets that took a cell set and created a new set of cells that represented the edges of the original cell set, which can provide a wireframe of the mesh.
In Section~\ref{sec:GeneratingCellSets:SingleType} we provided a pair of worklets that generate one line per edge per cell.
In Section ~\ref{sec:GeneratingCellSets:CombiningLikeElements} we improved on this behavior by using a reduce by key worklet to find and merge shared edges.

If we were to time all the operations run in the later implementation to generate the wireframe (i.e. the operations in Example~\ref{ex:GenerateMeshCombineLikeInvoke}), we would find that the vast majority of the time is not spent in the actual worklets.
Rather, the majority of the time is spent in collecting the like keys, which happens in the constructor of the \vtkmworklet{Keys} object.
Internally, keys are collected by sorting them.
The most fruitful way to improve the performance of this algorithm is to improve the sorting behavior.

The details of how the sort works is dependent on the inner workings of the device adapter.
It turns out that the performance of the sort of the keys is highly dependent on the data type of the keys.
For example, sorting numbers stored in a 32-bit integer is often much faster than sorting groups of 2 or 3 64-bit integer.
This is particularly true when the sort is capable of performing a radix-based sort.

An easy way to convert collections of indices like those returned from \vtkmexec{CellEdgeCanonicalId} to a 32-bit integer is to use a hash function.
To facilitate the creation of hash values, \VTKm comes with a simple \vtkm{Hash} function (in the \vtkmheader{vtkm}{Hash.h} header file).
\textidentifier{Hash} takes a \textidentifier{Vec} or \Veclike object of integers and returns a value of type \vtkm{HashType} (an alias for a 32-bit integer).
This hash function uses the FNV-1a algorithm that is designed to create hash values that are quasi-random but deterministic.
This means that hash values of two different identifiers are unlikely to be the same.

That said, hash collisions can happen and become increasingly likely on larger data sets.
Therefore, if we wish to use hash values, we also have to add conditions that manage collisions when they happen.
Resolving hash value collisions adds overhead, but the time saved in faster sorting of hash values generally outweighs the overhead added by resolving collisions.%
\footnote{A comparison of the time required for completely unique keys and hash keys with collisions is studied by Lessley, et al. in ``Techniques for Data-Parallel Searching for Duplicate Elements'' (in \emph{IEEE Symposium on Large Data Analysis and Visualization}, October 2017).}
In this section we will improve on the implementation given in Section~\ref{sec:GeneratingCellSets:CombiningLikeElements} by using hash values for keys and resolving for collisions.

As always, our first step is to count the number of edges in each input cell.
These counts are used to create a \vtkmworklet{ScatterCounting} for subsequent worklets.

\vtkmlisting[ex:GenerateMeshHashCount]{A simple worklet to count the number of edges on each cell.}{GenerateMeshHashCount.cxx}

Our next step is to generate keys that can be used to find like elements.
As before, we will use the \vtkmexec{CellEdgeCanonicalId} function to create a unique representation for each edge.
However, rather than directly use the value from \textidentifier{CellEdgeCanonicalId}, which is a \vtkm{Id2}, we will instead use that to generate a hash value.

\vtkmlisting[ex:GenerateMeshHashGenHashes]{Worklet generating hash values.}{GenerateMeshHashGenHashes.cxx}

The hash values generated by the worklet in Example~\ref{ex:GenerateMeshHashGenHashes} will be the same for two identical edges.
However, it is no longer guaranteed that two distinct edges will have different keys, and collisions of this nature become increasingly common for larger cell sets.
Thus, our next step is to resolve any such collisions.

The following example provides a worklet that goes through each group of edges associated with the same hash value (using a reduce by key worklet).
It identifies which edges are actually the same as which other edges, marks a local identifier for each unique edge group, and returns the number of unique edges associated with the hash value.

\vtkmlisting[ex:GenerateMeshHashResolveCollisions]{Worklet to resolve hash collisions occurring on edge identifiers.}{GenerateMeshHashResolveCollisions.cxx}

With all hash collisions correctly identified, we are ready to generate the connectivity array for the line elements.
This worklet uses a reduce by key worklet like the previous example, but this time we use a \textidentifier{ScatterCounting} to run the worklet multiple times for hash values that contain multiple unique edges.
The worklet takes all the information it needs to reference back to the edges in the original mesh including a \sigtag{WholeCellSetIn}, look back indices for the cells and respective edges, and the unique edge group indicators produced by Example~\ref{ex:GenerateMeshHashGenHashes}.

As in the previous sections, this worklet writes out the edge information in a \vtkm{Id2} (which in some following code will be created with an \textidentifier{ArrayHandleGroupVec}).

\vtkmlisting[ex:GenerateMeshHashGenIndices]{A worklet to generate indices for line cells from combined edges and potential collisions.}{GenerateMeshHashGenIndices.cxx}

With these 3 worklets, it is now possible to generate all the information we need to fill a \vtkmcont{CellSetSingleType} object.
A \textidentifier{CellSetSingleType} requires 4 items: the number of points, the constant cell shape, the constant number of points in each cell, and an array of connection indices.
The first 3 items are trivial.
The number of points can be taken from the input cell set as they are the same.
The cell shape and number of points are predetermined to be line and 2, respectively.

The last item, the array of connection indices, is what we are creating with the worklet in Example \ref{ex:GenerateMeshHashGenIndices}.
The connectivity array for \textidentifier{CellSetSingleType} is expected to be a flat array of \vtkm{Id} indices, but the worklet needs to provide groups of indices for each cell (in this case as a \textidentifier{Vec} object).
To reconcile what the worklet provides and what the connectivity array must look like, we use the \vtkmcont{ArrayHandleGroupVec} fancy array handle (described in Section~\ref{sec:GroupedVectorArrays}) to make a flat array of indices look like an array of \textidentifier{Vec} objects.

The following example shows what the \classmember*{FilterDataSet}{DoExecute} method in the associated filter would look like.

\vtkmlisting[ex:GenerateMeshHashInvoke]{Invoking worklets to extract unique edges from a cell set using hash values.}{GenerateMeshHashInvoke.cxx}

As noted in Section~\ref{sec:GeneratingCellSets:CombiningLikeElements}, in practice \classmember*{FilterDataSet}{DoExecute} is called on \textidentifier{DataSet} objects to create new \textidentifier{DataSet} objects.
Although Example~\ref{ex:GenerateMeshHashInvoke} creates a new \textidentifier{CellSet}, we also need a method to transform the \textidentifier{Field}s on the data set.
To do this, we need to save some information.
This includes the map from the edge of each cell to its origin cell (\textcode{OutputToInputCellMap}), a \textidentifier{Keys} object on the hash values (\textcode{CellToEdgeKeys}), an array of indices resolving collisions (\textcode{LocalEdgeIndices}), and a \textidentifier{ScatterCounting} to repeat edge outputs when unique edges collide on a hash (\textcode{HashCollisionScatter}).

\begin{commonerrors}
  Note that \textcode{HashCollisionScatter} is an object of type \vtkmworklet{ScatterCounting}, which does not have a default constructor.
  That can be a problem since you do not have the data to construct \textcode{HashCollisionScatter} until \classmember*{FilterDataSet}{DoExecute} is called.
  To get around this chicken-and-egg issue, it is best to store the \textidentifier{ScatterCounter} as a pointer.
  It is best practice to use a smart pointer, like \textcode{std::shared\_ptr} to manage it.
\end{commonerrors}

In Section~\ref{sec:GeneratingCellSets:CombiningLikeElements} we used a convenience method to average a field attached to cells on the input to each unique edge in the output.
Unfortunately, that function does not take into account the collisions that can occur on the keys.
Instead we need a custom worklet to average those values that match the same unique edge.

\vtkmlisting[ex:GenerateMeshHashAverageField]{A worklet to average values with the same key, resolving for collisions.}{GenerateMeshHashAverageField.cxx}

With this worklet, it is straightforward to process cell fields.

\vtkmlisting[ex:GenerateMeshHashMapCellField]{Invoking the worklet to process cell fields, resolving for collisions.}{GenerateMeshHashMapCellField.cxx}

\index{CellSetSingleType!generate|)}


\section{Variable Cell Types}
\label{sec:GeneratingCellSets:VariableCellTypes}

\index{CellSetExplicit!generate|(}

So far in our previous examples we have demonstrated creating a cell set where every cell is the same shape and number of points (i.e. a \textidentifier{CellSetSingleType}).
However, it can also be the case where an algorithm must create cells of a different type (into a \vtkmcont{CellSetExplicit}).
The procedure for generating cells of different shapes is similar to that of creating a single shape.
There is, however, an added step of counting the size (in number of points) of each shape to build the appropriate structure for storing the cell connectivity.

Our motivating example is a filter that extracts all the unique faces in a cell set and stores them in a cell set of polygons.
This problem is similar to the one addressed in Sections \ref{sec:GeneratingCellSets:SingleType}, \ref{sec:GeneratingCellSets:CombiningLikeElements}, and \ref{sec:GeneratingCellSets:FasterCombiningLikeElements}.
In both cases it is necessary to find all subelements of each cell (in this case the faces instead of the edges).
It is also the case that we expect many faces to be shared among cells in the same way edges are shared among cells.
We will use the hash-based approach demonstrated in Section~\ref{sec:GeneratingCellSets:FasterCombiningLikeElements} except this time applied to faces instead of edges.

The main difference between the two extraction tasks is that whereas all edges are lines with two points, faces can come in different sizes.
A tetrahedron has triangular faces whereas a hexahedron has quadrilateral faces.
Pyramid and wedge cells have both triangular and quadrilateral faces.
Thus, in general the algorithm must be capable of outputting multiple cell types.

Our algorithm for extracting unique cell faces follows the same algorithm as that in Section~\ref{sec:GeneratingCellSets:FasterCombiningLikeElements}.
We first need three worklets (used in succession) to count the number of faces in each cell, to generate a hash value for each face, and to resolve hash collisions.
These are essentially the same as Examples \ref{ex:GenerateMeshHashCount}, \ref{ex:GenerateMeshHashGenHashes}, and \ref{ex:GenerateMeshHashResolveCollisions}, respectively, with superficial changes made (like changing \textcode{Edge} to \textcode{Face}).
To make it simpler to follow the discussion, the code is not repeated here.

When extracting edges, these worklets provide everything necessary to write out line elements.
However, before we can write out polygons of different sizes, we first need to count the number of points in each polygon.
The following example does just that.
This worklet also writes out the identifier for the shape of the face, which we will eventually require to build a \textidentifier{CellSetExplicit}.
Also recall that we have to work with the information returned from the collision resolution to report on the appropriate unique cell face.

\vtkmlisting[ex:GenerateMeshVariableShapeCountPointsInFace]{A worklet to count the points in the final cells of extracted faces}{GenerateMeshVariableShapeCountPointsInFace.cxx}

When extracting edges, we converted a flat array of connectivity information to an array of \textidentifier{Vec}s using an \textidentifier{ArrayHandleGroupVec}.
However, \textidentifier{ArrayHandleGroupVec} can only create \textidentifier{Vec}s of a constant size.
Instead, for this use case we need to use \vtkmcont{ArrayHandleGroupVecVariable}.
As described in Section~\ref{sec:GroupedVectorArrays}, \textidentifier{ArrayHandleGroupVecVariable} takes a flat array of values and an index array of offsets that points to the beginning of each group to represent as a \Veclike.
The worklet in Example~\ref{ex:GenerateMeshVariableShapeCountPointsInFace} does not actually give us the array of offsets we need.
Rather, it gives us the count of each group.
We can get the offsets from the counts by using the \vtkmcont{ConvertNumComponentsToOffsets} convenience function.

\vtkmlisting[ex:GenerateMeshVariableShapeOffsetsArray]{Converting counts of connectivity groups to offsets for \textidentifier{ArrayHandleGroupVecVariable}.}{GenerateMeshVariableShapeOffsetsArray.cxx}

Once we have created an \textidentifier{ArrayHandleGroupVecVariable}, we can pass that to a worklet that produces the point connections for each output polygon.
The worklet is very similar to the one for creating edge lines (shown in Example~\ref{ex:GenerateMeshHashGenIndices}), but we have to correctly handle the \Veclike of unknown type and size.

\vtkmlisting[ex:GenerateMeshVariableShapeGenIndices]{A worklet to generate indices for polygon cells of different sizes from combined edges and potential collisions.}{GenerateMeshVariableShapeGenIndices.cxx}

With these worklets in place, we can implement a filter \classmember*{FilterDataSet}{DoExecute} as follows.

\vtkmlisting[ex:GenerateMeshVariableShapeInvoke]{Invoking worklets to extract unique faces from a cell set.}{GenerateMeshVariableShapeInvoke.cxx}

As noted previously, in practice \classmember*{FilterDataSet}{DoExecute} is called on \textidentifier{DataSet} objects to create new \textidentifier{DataSet} objects.
The process for doing so is no different from our previous algorithm as described at the end of Section~\ref{sec:GeneratingCellSets:FasterCombiningLikeElements} (Examples \ref{ex:GenerateMeshHashAverageField} and \ref{ex:GenerateMeshHashMapCellField}).

\index{CellSetExplicit!generate|)}

\index{data set!generate|)}
\index{cell set!generate|)}
