4.14. Generating Cell Sets
This chapter describes techniques for designing algorithms in Viskores that generate cell sets to be inserted in a viskores::cont::DataSet.
Although Chapter 2.4 (Data Sets) 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 viskores::cont::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 4.3 (Worklet Types). 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.
4.14.1. Single Cell Type
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 viskores::cont::CellSetSingleType to represent the cell connections.
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.
1struct CountEdgesWorklet : viskores::worklet::WorkletVisitCellsWithPoints
2{
3 using ControlSignature = void(CellSetIn cellSet, FieldOut numEdges);
4 using ExecutionSignature = _2(CellShape, PointCount);
5 using InputDomain = _1;
6
7 template<typename CellShapeTag>
8 VISKORES_EXEC_CONT viskores::IdComponent operator()(
9 CellShapeTag cellShape,
10 viskores::IdComponent numPointsInCell) const
11 {
12 viskores::IdComponent numEdges;
13 viskores::ErrorCode status =
14 viskores::exec::CellEdgeNumberOfEdges(numPointsInCell, cellShape, numEdges);
15 if (status != viskores::ErrorCode::Success)
16 {
17 // There is an error in the cell. As good as it would be to return an
18 // error, we probably don't want to invalidate the entire run if there
19 // is just one malformed cell. Instead, ignore the cell.
20 return 0;
21 }
22 return numEdges;
23 }
24};
This count array generated in Example 4.132 can be used in a viskores::worklet::ScatterCounting of a subsequent worklet that generates the output cells.
(See Section 4.13.1 (Scatter) for information on using a scatter with a worklet.)
We will see this momentarily.
Did You Know?
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 viskores::worklet::ScatterUniform instead of viskores::worklet::ScatterCounting.
Doing so will simplify the code and skip some computation.
We cannot use viskores::worklet::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 viskores::worklet::ScatterUniform<12> for that.
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 viskores::worklet::ScatterCounting provides a VisitIndex that signals which edge to output.
The worklet parenthesis operator returns the two indices for the line in, naturally enough, a viskores::Id2.
1class EdgeIndicesWorklet : public viskores::worklet::WorkletVisitCellsWithPoints
2{
3public:
4 using ControlSignature = void(CellSetIn cellSet, FieldOut connectivityOut);
5 using ExecutionSignature = void(CellShape, PointIndices, _2, VisitIndex);
6 using InputDomain = _1;
7
8 using ScatterType = viskores::worklet::ScatterCounting;
9
10 template<typename CellShapeTag, typename PointIndexVecType>
11 VISKORES_EXEC void operator()(CellShapeTag cellShape,
12 const PointIndexVecType& globalPointIndicesForCell,
13 viskores::Id2& connectivityOut,
14 viskores::IdComponent edgeIndex) const
15 {
16 viskores::IdComponent numPointsInCell =
17 globalPointIndicesForCell.GetNumberOfComponents();
18
19 viskores::ErrorCode status;
20 viskores::IdComponent pointInCellIndex0;
21 status = viskores::exec::CellEdgeLocalIndex(
22 numPointsInCell, 0, edgeIndex, cellShape, pointInCellIndex0);
23 if (status != viskores::ErrorCode::Success)
24 {
25 this->RaiseError(viskores::ErrorString(status));
26 return;
27 }
28 viskores::IdComponent pointInCellIndex1;
29 status = viskores::exec::CellEdgeLocalIndex(
30 numPointsInCell, 1, edgeIndex, cellShape, pointInCellIndex1);
31 if (status != viskores::ErrorCode::Success)
32 {
33 this->RaiseError(viskores::ErrorString(status));
34 return;
35 }
36
37 connectivityOut[0] = globalPointIndicesForCell[pointInCellIndex0];
38 connectivityOut[1] = globalPointIndicesForCell[pointInCellIndex1];
39 }
40};
Our ultimate goal is to fill a viskores::cont::CellSetSingleType object with the generated line cells.
A viskores::cont::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 4.133.
However, there is a complication.
The connectivity array for viskores::cont::CellSetSingleType is expected to be a flat array of viskores::Id indices, not an array of viskores::Id2 objects.
We could jump through some hoops adjusting the viskores::worklet::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 viskores::cont::ArrayHandleGroupVec fancy array handle, described in Section 4.9.12 (Grouped Vector Arrays), to make a flat array of indices look like an array of Vec objects.
The following example shows what the viskores::filter::Filter::DoExecute() method in the associated filter would look like.
Note the use viskores::cont::make_ArrayHandleGroupVec() when calling viskores::filter::Filter::Invoke() on Example 4.134, line 15 to make this conversion.
1inline VISKORES_CONT viskores::cont::DataSet ExtractEdges::DoExecute(
2 const viskores::cont::DataSet& inData)
3{
4 auto inCellSet = inData.GetCellSet();
5
6 // Count number of edges in each cell.
7 viskores::cont::ArrayHandle<viskores::IdComponent> edgeCounts;
8 this->Invoke(viskores::worklet::CountEdgesWorklet{}, inCellSet, edgeCounts);
9
10 // Build the scatter object (for non 1-to-1 mapping of input to output)
11 viskores::worklet::ScatterCounting scatter(edgeCounts);
12 auto outputToInputCellMap = scatter.GetOutputToInputMap(inCellSet.GetNumberOfCells());
13
14 viskores::cont::ArrayHandle<viskores::Id> connectivityArray;
15 this->Invoke(viskores::worklet::EdgeIndicesWorklet{},
16 scatter,
17 inCellSet,
18 viskores::cont::make_ArrayHandleGroupVec<2>(connectivityArray));
19
20 viskores::cont::CellSetSingleType<> outCellSet;
21 outCellSet.Fill(
22 inCellSet.GetNumberOfPoints(), viskores::CELL_SHAPE_LINE, 2, connectivityArray);
23
24 // This lambda function maps an input field to the output data set. It is
25 // used with the CreateResult method.
26 auto fieldMapper =
27 [&](viskores::cont::DataSet& outData, const viskores::cont::Field& inputField)
28 {
29 if (inputField.IsCellField())
30 {
31 viskores::filter::MapFieldPermutation(inputField, outputToInputCellMap, outData);
32 }
33 else
34 {
35 outData.AddField(inputField); // pass through
36 }
37 };
38
39 return this->CreateResult(inData, outCellSet, fieldMapper);
40}
Another feature to note in Example 4.134 is that the method calls viskores::worklet::ScatterCounting::GetOutputToInputMap() on the scatter object it creates and squirrels the map array away for later use (Example 4.134, line 12).
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, viskores::filter::Filter::DoExecute() is called on viskores::cont::DataSet objects to create new viskores::cont::DataSet objects.
The method in Example 4.134 creates a new viskores::cont::CellSet, but we also need a method to transform the fields on the data set.
The saved outputToInputCellMap array allows us to transform input fields to output fields.
The lambda function starting at Example 4.134, line 26 uses this saved outputToInputCellMap array and converts an array from an input cell field to an output cell field array.
It does this using the viskores::filter::MapFieldPermutation() helper function while using the outputToInputCellMap as the permutation array.
4.14.2. Combining Like Elements
Our motivating example in Section 4.14.1 (Single Cell Type) 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 4.14.1 (Single Cell Type) will create multiple overlapping lines, one for each cell using the edge, as demonstrated in Figure 4.4. What we really want is to have one line for every edge in the mesh rather than many overlapping lines.
Figure 4.4 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ïve implementation in Section 4.14.1 (Single Cell Type) 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.
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 viskores::worklet::ScatterCounting for subsequent worklets.
Counting the edges is a simple worklet.
1struct CountEdgesWorklet : viskores::worklet::WorkletVisitCellsWithPoints
2{
3 using ControlSignature = void(CellSetIn cellSet, FieldOut numEdges);
4 using ExecutionSignature = _2(CellShape, PointCount);
5 using InputDomain = _1;
6
7 template<typename CellShapeTag>
8 VISKORES_EXEC_CONT viskores::IdComponent operator()(
9 CellShapeTag cellShape,
10 viskores::IdComponent numPointsInCell) const
11 {
12 viskores::IdComponent numEdges;
13 viskores::ErrorCode status =
14 viskores::exec::CellEdgeNumberOfEdges(numPointsInCell, cellShape, numEdges);
15 if (status != viskores::ErrorCode::Success)
16 {
17 // There is an error in the cell. As good as it would be to return an
18 // error, we probably don't want to invalidate the entire run if there
19 // is just one malformed cell. Instead, ignore the cell.
20 return 0;
21 }
22 return numEdges;
23 }
24};
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. This grouping is exactly the function that the reduce by key worklet type, described in Section 4.3.4 (Reduce by Key), 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).
(See Using indices to find common mesh elements is described by Miller et al. in “Finely-Threaded History-Based Topology Computation” in Eurographics Symposium on Parallel Graphics and Visualization, June 2014 for details on using indices to find common mesh elements.)
Viskores comes with a helper function, viskores::exec::CellEdgeCanonicalId(), defined in viskores/exec/CellEdge.h, to produce these unique edge keys as viskores::Id2’s.
Our second worklet produces these canonical edge identifiers.
1class EdgeIdsWorklet : public viskores::worklet::WorkletVisitCellsWithPoints
2{
3public:
4 using ControlSignature = void(CellSetIn cellSet, FieldOut canonicalIds);
5 using ExecutionSignature = void(CellShape cellShape,
6 PointIndices globalPointIndices,
7 VisitIndex localEdgeIndex,
8 _2 canonicalIdOut);
9 using InputDomain = _1;
10
11 using ScatterType = viskores::worklet::ScatterCounting;
12
13 template<typename CellShapeTag, typename PointIndexVecType>
14 VISKORES_EXEC void operator()(CellShapeTag cellShape,
15 const PointIndexVecType& globalPointIndicesForCell,
16 viskores::IdComponent localEdgeIndex,
17 viskores::Id2& canonicalIdOut) const
18 {
19 viskores::IdComponent numPointsInCell =
20 globalPointIndicesForCell.GetNumberOfComponents();
21
22 viskores::ErrorCode status =
23 viskores::exec::CellEdgeCanonicalId(numPointsInCell,
24 localEdgeIndex,
25 cellShape,
26 globalPointIndicesForCell,
27 canonicalIdOut);
28 if (status != viskores::ErrorCode::Success)
29 {
30 this->RaiseError(viskores::ErrorString(status));
31 }
32 }
33};
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 viskores::worklet::WorkletReduceByKey.
When the worklet is invoked, Viskores 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 WholeCellSetIn to find the information about the edge.
As shown later, these indices of cells and edges can be extracted from the viskores::worklet::ScatterCounting used to execute the worklet back in Example 4.136.
As we did in Section 4.14.1 (Single Cell Type), this worklet writes out the edge information in a viskores::Id2 (which in some following code will be created with an viskores::cont::ArrayHandleGroupVec).
1class EdgeIndicesWorklet : public viskores::worklet::WorkletReduceByKey
2{
3public:
4 using ControlSignature = void(KeysIn keys,
5 WholeCellSetIn<> inputCells,
6 ValuesIn originCells,
7 ValuesIn originEdges,
8 ReducedValuesOut connectivityOut);
9 using ExecutionSignature = void(_2 inputCells,
10 _3 originCell,
11 _4 originEdge,
12 _5 connectivityOut);
13 using InputDomain = _1;
14
15 template<typename CellSetType, typename OriginCellsType, typename OriginEdgesType>
16 VISKORES_EXEC void operator()(const CellSetType& cellSet,
17 const OriginCellsType& originCells,
18 const OriginEdgesType& originEdges,
19 viskores::Id2& connectivityOut) const
20 {
21 // Regardless of how many cells are sharing the edge we are generating, we
22 // know that each cell/edge given to us by the reduce-by-key refers to the
23 // same edge, so we can just look at the first cell to get the edge.
24 viskores::IdComponent numPointsInCell = cellSet.GetNumberOfIndices(originCells[0]);
25 viskores::IdComponent edgeIndex = originEdges[0];
26 auto cellShape = cellSet.GetCellShape(originCells[0]);
27
28 viskores::IdComponent pointInCellIndex0;
29 viskores::exec::CellEdgeLocalIndex(
30 numPointsInCell, 0, edgeIndex, cellShape, pointInCellIndex0);
31 viskores::IdComponent pointInCellIndex1;
32 viskores::exec::CellEdgeLocalIndex(
33 numPointsInCell, 1, edgeIndex, cellShape, pointInCellIndex1);
34
35 auto globalPointIndicesForCell = cellSet.GetIndices(originCells[0]);
36 connectivityOut[0] = globalPointIndicesForCell[pointInCellIndex0];
37 connectivityOut[1] = globalPointIndicesForCell[pointInCellIndex1];
38 }
39};
Did You Know?
It so happens that the viskores::Id2’s generated by viskores::exec::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.
With these 3 worklets, it is now possible to generate all the information we need to fill a viskores::cont::CellSetSingleType object.
A viskores::cont::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 4.137.
The connectivity array for viskores::cont::CellSetSingleType is expected to be a flat array of viskores::Id indices, but the worklet needs to provide groups of indices for each cell (in this case as a viskores::Vec object).
To reconcile what the worklet provides and what the connectivity array must look like, we use the viskores::cont::ArrayHandleGroupVec fancy array handle, described in Section 4.9.12 (Grouped Vector Arrays), to make a flat array of indices look like an array of viskores::Vec objects.
The following example shows what the viskores::filter::Filter::DoExecute() method in the associated filter would look like.
Note the use of viskores::cont::make_ArrayHandleGroupVec() when calling viskores::filter::Filter::Invoke() at Example 4.138, line 25 to make this conversion.
1inline VISKORES_CONT viskores::cont::DataSet ExtractEdges::DoExecute(
2 const viskores::cont::DataSet& inData)
3{
4 auto inCellSet = inData.GetCellSet();
5
6 // First, count the edges in each cell.
7 viskores::cont::ArrayHandle<viskores::IdComponent> edgeCounts;
8 this->Invoke(CountEdgesWorklet{}, inCellSet, edgeCounts);
9
10 // Second, using these counts build a scatter that repeats a cell's visit
11 // for each edge in the cell.
12 viskores::worklet::ScatterCounting scatter(edgeCounts);
13 viskores::worklet::ScatterCounting::VisitArrayType outputToInputEdgeMap =
14 scatter.GetVisitArray(inCellSet.GetNumberOfCells());
15
16 // Third, for each edge, extract a canonical id.
17 viskores::cont::ArrayHandle<viskores::Id2> canonicalIds;
18 this->Invoke(EdgeIdsWorklet{}, scatter, inCellSet, canonicalIds);
19
20 // Fourth, construct a Keys object to combine all like edge ids.
21 viskores::worklet::Keys<viskores::Id2> cellToEdgeKeys(canonicalIds);
22
23 // Fifth, use a reduce-by-key to extract indices for each unique edge.
24 viskores::cont::ArrayHandle<viskores::Id> connectivityArray;
25 this->Invoke(EdgeIndicesWorklet{},
26 cellToEdgeKeys,
27 inCellSet,
28 scatter.GetOutputToInputMap(inCellSet.GetNumberOfCells()),
29 outputToInputEdgeMap,
30 viskores::cont::make_ArrayHandleGroupVec<2>(connectivityArray));
31
32 // Sixth, use the created connectivity array to build a cell set.
33 viskores::cont::CellSetSingleType<> outCellSet;
34 outCellSet.Fill(
35 inCellSet.GetNumberOfPoints(), viskores::CELL_SHAPE_LINE, 2, connectivityArray);
36
37 // Finally, we need to create an output data set. A lambda expression is one
38 // of the easiest ways to map fields from the input to the output with the
39 // CreateResult method.
40 auto fieldMapper =
41 [&](viskores::cont::DataSet& outData, const viskores::cont::Field& inField)
42 {
43 if (inField.IsCellField())
44 {
45 // New cells were created. Need to find cells that created the output.
46 // First, the cells were subselected with a scatter. Use the
47 // output-to-input array from the scatter to permute the array.
48 viskores::cont::Field subselectionField;
49 viskores::filter::MapFieldPermutation(
50 inField,
51 scatter.GetOutputToInputMap(inCellSet.GetNumberOfCells()),
52 subselectionField);
53 // Next, coicident edges are combined together. Use the keys object
54 // for combining the cells to average out the cell values.
55 viskores::filter::MapFieldMergeAverage(subselectionField, cellToEdgeKeys, outData);
56 }
57 else
58 {
59 outData.AddField(inField); // Pass through
60 }
61 };
62
63 return this->CreateResult(inData, outCellSet, fieldMapper);
64}
Another feature to note in Example 4.138 is that because the cells returned in the output data are not the same as the input, the output cell fields must be similarly converted.
This is done by creating a lambda function in lines 37 – 61 to convert the fields that is then passed to viskores::filter::Filter::CreateResult(), called at Example 4.138, line 63.
The mapping process reuses the object from before to extract the edges from the cells.
It first uses viskores::worklet::ScatterCounting::GetOutputToInputMap() on the scatter object it creates with a convenience function named viskores::filter::MapFieldPermutation() that duplicates the cell values for each edge.
It then uses the viskores::worklet::Keys object from the duplicate edge removal with a convenience function named viskores::filter::MapFieldMergeAverage() that averages cell values for edges of adjacent cells.
Did You Know?
For simplicity, Example 4.138 is creating an intermediate array to hold the permutation. It would be possible to remove this temporary array for saved performance and memory, but this requires building a custom mapping function, which adds complexity. We will show an example of such a function in the following section.
4.14.3. Faster Combining Like Elements with Hashes
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 4.14.1 (Single Cell Type) we provided a pair of worklets that generate one line per edge per cell. In Section 4.14.2 (Combining Like Elements) 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 such as the operations in Example 4.138, 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 viskores::worklet::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 integers. 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 viskores::exec::CellEdgeCanonicalId() to a 32-bit integer is to use a hash function.
To facilitate the creation of hash values, Viskores comes with a simple viskores::Hash() function (in the vtkm/Hash.h header file).
viskores::Hash() takes a viskores::Vec or Vec-like object of integers and returns a value of type viskores::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.
-
template<typename InVecType>
inline viskores::HashType viskores::Hash(const InVecType &inVec) Returns a 32-bit hash on a group of integer-type values.
The input to the hash is expected to be a viskores::Vec or a Vec-like object. The values can be either 32-bit integers or 64-bit integers (signed or unsigned). Regardless, the resulting hash is an unsigned 32-bit integer.
The hash is designed to minimize the probability of collisions, but collisions are always possible. Thus, when using these hashes there should be a contingency for dealing with collisions.
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 as studied by Lessley, et al. in “Techniques for Data-Parallel Searching for Duplicate Elements” in IEEE Symposium on Large Data Analysis and Visualization, October 2017. In this section we will improve on the implementation given in Section 4.14.2 (Combining Like Elements) 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 viskores::worklet::ScatterCounting for subsequent worklets.
1struct CountEdgesWorklet : viskores::worklet::WorkletVisitCellsWithPoints
2{
3 using ControlSignature = void(CellSetIn cellSet, FieldOut numEdges);
4 using ExecutionSignature = _2(CellShape, PointCount);
5 using InputDomain = _1;
6
7 template<typename CellShapeTag>
8 VISKORES_EXEC_CONT viskores::IdComponent operator()(
9 CellShapeTag cellShape,
10 viskores::IdComponent numPointsInCell) const
11 {
12 viskores::IdComponent numEdges;
13 viskores::ErrorCode status =
14 viskores::exec::CellEdgeNumberOfEdges(numPointsInCell, cellShape, numEdges);
15 if (status != viskores::ErrorCode::Success)
16 {
17 // There is an error in the cell. As good as it would be to return an
18 // error, we probably don't want to invalidate the entire run if there
19 // is just one malformed cell. Instead, ignore the cell.
20 return 0;
21 }
22 return numEdges;
23 }
24};
Our next step is to generate keys that can be used to find like elements.
As before, we will use the viskores::exec::CellEdgeCanonicalId() function to create a unique representation for each edge.
However, rather than directly use the value from viskores::exec::CellEdgeCanonicalId(), which is a viskores::Id2, we will instead use that to generate a hash value.
1class EdgeHashesWorklet : public viskores::worklet::WorkletVisitCellsWithPoints
2{
3public:
4 using ControlSignature = void(CellSetIn cellSet, FieldOut hashValues);
5 using ExecutionSignature = _2(CellShape cellShape,
6 PointIndices globalPointIndices,
7 VisitIndex localEdgeIndex);
8 using InputDomain = _1;
9
10 using ScatterType = viskores::worklet::ScatterCounting;
11
12 template<typename CellShapeTag, typename PointIndexVecType>
13 VISKORES_EXEC viskores::HashType operator()(
14 CellShapeTag cellShape,
15 const PointIndexVecType& globalPointIndicesForCell,
16 viskores::IdComponent localEdgeIndex) const
17 {
18 viskores::IdComponent numPointsInCell =
19 globalPointIndicesForCell.GetNumberOfComponents();
20 viskores::Id2 canonicalId;
21 viskores::ErrorCode status =
22 viskores::exec::CellEdgeCanonicalId(numPointsInCell,
23 localEdgeIndex,
24 cellShape,
25 globalPointIndicesForCell,
26 canonicalId);
27 if (status != viskores::ErrorCode::Success)
28 {
29 this->RaiseError(viskores::ErrorString(status));
30 return viskores::HashType(-1);
31 }
32 return viskores::Hash(canonicalId);
33 }
34};
The hash values generated by the worklet in Example 4.140 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.
1class EdgeHashCollisionsWorklet : public viskores::worklet::WorkletReduceByKey
2{
3public:
4 using ControlSignature = void(KeysIn keys,
5 WholeCellSetIn<> inputCells,
6 ValuesIn originCells,
7 ValuesIn originEdges,
8 ValuesOut localEdgeIndices,
9 ReducedValuesOut numEdges);
10 using ExecutionSignature = _6(_2 inputCells,
11 _3 originCells,
12 _4 originEdges,
13 _5 localEdgeIndices);
14 using InputDomain = _1;
15
16 template<typename CellSetType,
17 typename OriginCellsType,
18 typename OriginEdgesType,
19 typename localEdgeIndicesType>
20 VISKORES_EXEC viskores::IdComponent operator()(
21 const CellSetType& cellSet,
22 const OriginCellsType& originCells,
23 const OriginEdgesType& originEdges,
24 localEdgeIndicesType& localEdgeIndices) const
25 {
26 viskores::IdComponent numEdgesInHash = localEdgeIndices.GetNumberOfComponents();
27
28 // Sanity checks.
29 VISKORES_ASSERT(originCells.GetNumberOfComponents() == numEdgesInHash);
30 VISKORES_ASSERT(originEdges.GetNumberOfComponents() == numEdgesInHash);
31
32 // Clear out localEdgeIndices
33 for (viskores::IdComponent index = 0; index < numEdgesInHash; ++index)
34 {
35 localEdgeIndices[index] = -1;
36 }
37
38 // Count how many unique edges there are and create an id for each;
39 viskores::IdComponent numUniqueEdges = 0;
40 for (viskores::IdComponent firstEdgeIndex = 0; firstEdgeIndex < numEdgesInHash;
41 ++firstEdgeIndex)
42 {
43 if (localEdgeIndices[firstEdgeIndex] == -1)
44 {
45 viskores::IdComponent edgeId = numUniqueEdges;
46 localEdgeIndices[firstEdgeIndex] = edgeId;
47 // Find all matching edges.
48 viskores::Id firstCellIndex = originCells[firstEdgeIndex];
49 viskores::Id2 canonicalEdgeId;
50 viskores::exec::CellEdgeCanonicalId(cellSet.GetNumberOfIndices(firstCellIndex),
51 originEdges[firstEdgeIndex],
52 cellSet.GetCellShape(firstCellIndex),
53 cellSet.GetIndices(firstCellIndex),
54 canonicalEdgeId);
55 for (viskores::IdComponent laterEdgeIndex = firstEdgeIndex + 1;
56 laterEdgeIndex < numEdgesInHash;
57 ++laterEdgeIndex)
58 {
59 viskores::Id laterCellIndex = originCells[laterEdgeIndex];
60 viskores::Id2 otherCanonicalEdgeId;
61 viskores::exec::CellEdgeCanonicalId(cellSet.GetNumberOfIndices(laterCellIndex),
62 originEdges[laterEdgeIndex],
63 cellSet.GetCellShape(laterCellIndex),
64 cellSet.GetIndices(laterCellIndex),
65 otherCanonicalEdgeId);
66 if (canonicalEdgeId == otherCanonicalEdgeId)
67 {
68 localEdgeIndices[laterEdgeIndex] = edgeId;
69 }
70 }
71 ++numUniqueEdges;
72 }
73 }
74
75 return numUniqueEdges;
76 }
77};
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 viskores::worklet::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 WholeCellSetIn, look-back indices for the cells and respective edges, and the unique edge group indicators produced by Example 4.140.
As in the previous sections, this worklet writes out the edge information in a viskores::Id2 (which in some following code will be created with an viskores::cont::ArrayHandleGroupVec).
1class EdgeIndicesWorklet : public viskores::worklet::WorkletReduceByKey
2{
3public:
4 using ControlSignature = void(KeysIn keys,
5 WholeCellSetIn<> inputCells,
6 ValuesIn originCells,
7 ValuesIn originEdges,
8 ValuesIn localEdgeIndices,
9 ReducedValuesOut connectivityOut);
10 using ExecutionSignature = void(_2 inputCells,
11 _3 originCell,
12 _4 originEdge,
13 _5 localEdgeIndices,
14 VisitIndex localEdgeIndex,
15 _6 connectivityOut);
16 using InputDomain = _1;
17
18 using ScatterType = viskores::worklet::ScatterCounting;
19
20 template<typename CellSetType,
21 typename OriginCellsType,
22 typename OriginEdgesType,
23 typename LocalEdgeIndicesType>
24 VISKORES_EXEC void operator()(const CellSetType& cellSet,
25 const OriginCellsType& originCells,
26 const OriginEdgesType& originEdges,
27 const LocalEdgeIndicesType& localEdgeIndices,
28 viskores::IdComponent localEdgeIndex,
29 viskores::Id2& connectivityOut) const
30 {
31 // Find the first edge that matches the index given and return it.
32 for (viskores::IdComponent edgeIndex = 0;; ++edgeIndex)
33 {
34 if (localEdgeIndices[edgeIndex] == localEdgeIndex)
35 {
36 viskores::Id cellIndex = originCells[edgeIndex];
37 viskores::IdComponent numPointsInCell = cellSet.GetNumberOfIndices(cellIndex);
38 viskores::IdComponent edgeInCellIndex = originEdges[edgeIndex];
39 auto cellShape = cellSet.GetCellShape(cellIndex);
40
41 viskores::IdComponent pointInCellIndex0;
42 viskores::exec::CellEdgeLocalIndex(
43 numPointsInCell, 0, edgeInCellIndex, cellShape, pointInCellIndex0);
44 viskores::IdComponent pointInCellIndex1;
45 viskores::exec::CellEdgeLocalIndex(
46 numPointsInCell, 1, edgeInCellIndex, cellShape, pointInCellIndex1);
47
48 auto globalPointIndicesForCell = cellSet.GetIndices(cellIndex);
49 connectivityOut[0] = globalPointIndicesForCell[pointInCellIndex0];
50 connectivityOut[1] = globalPointIndicesForCell[pointInCellIndex1];
51
52 break;
53 }
54 }
55 }
56};
With these 3 worklets, it is now possible to generate all the information we need to fill a viskores::cont::CellSetSingleType object.
A viskores::cont::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 4.142.
The connectivity array for viskores::cont::CellSetSingleType is expected to be a flat array of viskores::Id indices, but the worklet needs to provide groups of indices for each cell (in this case as a viskores::Vec object).
To reconcile what the worklet provides and what the connectivity array must look like, we use the viskores::cont::ArrayHandleGroupVec fancy array handle, described in Section 4.9.12 (Grouped Vector Arrays), to make a flat array of indices look like an array of viskores::Vec objects.
The following example shows what the viskores::filter::Filter::DoExecute() method in the associated filter would look like.
1inline VISKORES_CONT viskores::cont::DataSet ExtractEdges::DoExecute(
2 const viskores::cont::DataSet& inData)
3{
4 auto inCellSet = inData.GetCellSet();
5
6 // First, count the edges in each cell.
7 viskores::cont::ArrayHandle<viskores::IdComponent> edgeCounts;
8 this->Invoke(CountEdgesWorklet{}, inCellSet, edgeCounts);
9
10 // Second, using these counts build a scatter that repeats a cell's visit
11 // for each edge in the cell.
12 viskores::worklet::ScatterCounting scatter(edgeCounts);
13 viskores::worklet::ScatterCounting::OutputToInputMapType outputToInputCellMap =
14 scatter.GetOutputToInputMap(inCellSet.GetNumberOfCells());
15 viskores::worklet::ScatterCounting::VisitArrayType outputToInputEdgeMap =
16 scatter.GetVisitArray(inCellSet.GetNumberOfCells());
17
18 // Third, for each edge, extract a hash.
19 viskores::cont::ArrayHandle<viskores::HashType> hashValues;
20 this->Invoke(EdgeHashesWorklet{}, scatter, inCellSet, hashValues);
21
22 // Fourth, use a Keys object to combine all like hashes.
23 viskores::worklet::Keys<viskores::HashType> cellToEdgeKeys(hashValues);
24
25 // Fifth, use a reduce-by-key to collect like hash values, resolve collisions,
26 // and count the number of unique edges associated with each hash.
27 viskores::cont::ArrayHandle<viskores::IdComponent> numUniqueEdgesInEachHash;
28 viskores::cont::ArrayHandle<viskores::IdComponent> localEdgeIndices;
29 this->Invoke(EdgeHashCollisionsWorklet{},
30 cellToEdgeKeys,
31 inCellSet,
32 outputToInputCellMap,
33 outputToInputEdgeMap,
34 localEdgeIndices,
35 numUniqueEdgesInEachHash);
36
37 // Sixth, use a reduce-by-key to extract indices for each unique edge.
38 viskores::worklet::ScatterCounting hashCollisionScatter(numUniqueEdgesInEachHash);
39
40 viskores::cont::ArrayHandle<viskores::Id> connectivityArray;
41 this->Invoke(EdgeIndicesWorklet{},
42 hashCollisionScatter,
43 cellToEdgeKeys,
44 inCellSet,
45 outputToInputCellMap,
46 outputToInputEdgeMap,
47 localEdgeIndices,
48 viskores::cont::make_ArrayHandleGroupVec<2>(connectivityArray));
49
50 // Seventh, use the created connectivity array to build a cell set.
51 viskores::cont::CellSetSingleType<> outCellSet;
52 outCellSet.Fill(
53 inCellSet.GetNumberOfPoints(), viskores::CELL_SHAPE_LINE, 2, connectivityArray);
54
55 auto fieldMapper =
56 [&](viskores::cont::DataSet& dataset, const viskores::cont::Field& inField)
57 {
58 MapCellEdgesField(dataset,
59 inField,
60 outputToInputCellMap,
61 cellToEdgeKeys,
62 localEdgeIndices,
63 hashCollisionScatter);
64 };
65 return this->CreateResult(inData, outCellSet, fieldMapper);
66}
As noted in Section 4.14.2 (Combining Like Elements), in practice viskores::filter::Filter::DoExecute() is called on viskores::cont::DataSet objects to create new viskores::cont::DataSet objects.
Because Example 4.143 creates a new viskores::cont::CellSet, it also needs a mechanism to transform the fields on the data set.
To do this, we need to repurpose some of the data generated earlier in the algorithm.
This includes the outputToInputCellMap retrieved from the scatter object to replicate the cells for each edge, the cellToEdgeKeys viskores::worklet::Keys object to find like hash values, the localEdgeIndices array used to identify edges in colliding hashes, and the hashCollisionScatter viskores::worklet::ScatterCounting object used to separate edges from colliding hashes.
In Section 4.14.2 (Combining Like Elements) 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.
1class AverageCellEdgesFieldWorklet : public viskores::worklet::WorkletReduceByKey
2{
3public:
4 using ControlSignature = void(KeysIn keys,
5 ValuesIn inFieldValues,
6 ValuesIn localEdgeIndices,
7 ReducedValuesOut averagedField);
8 using ExecutionSignature = void(_2 inFieldValues,
9 _3 localEdgeIndices,
10 VisitIndex localEdgeIndex,
11 _4 averagedField);
12 using InputDomain = _1;
13
14 using ScatterType = viskores::worklet::ScatterCounting;
15
16 template<typename InFieldValuesType,
17 typename LocalEdgeIndicesType,
18 typename OutFieldValuesType>
19 VISKORES_EXEC void operator()(const InFieldValuesType& inFieldValues,
20 const LocalEdgeIndicesType& localEdgeIndices,
21 viskores::IdComponent localEdgeIndex,
22 OutFieldValuesType& averageField) const
23 {
24 using FieldType = typename InFieldValuesType::ComponentType;
25
26 viskores::IdComponent numValues = 0;
27 for (viskores::IdComponent reduceIndex = 0;
28 reduceIndex < inFieldValues.GetNumberOfComponents();
29 ++reduceIndex)
30 {
31 if (localEdgeIndices[reduceIndex] == localEdgeIndex)
32 {
33 FieldType fieldValue = inFieldValues[reduceIndex];
34 if (numValues == 0)
35 {
36 averageField = fieldValue;
37 }
38 else
39 {
40 averageField = averageField + fieldValue;
41 }
42 ++numValues;
43 }
44 }
45 VISKORES_ASSERT(numValues > 0);
46 averageField = averageField / numValues;
47 }
48};
49
50void MapCellEdgesField(
51 viskores::cont::DataSet& dataset,
52 const viskores::cont::Field& inField,
53 const viskores::worklet::ScatterCounting::OutputToInputMapType& cellPermutationMap,
54 const viskores::worklet::Keys<viskores::HashType>& cellToEdgeKeys,
55 const viskores::cont::ArrayHandle<viskores::IdComponent>& localEdgeIndices,
56 const viskores::worklet::ScatterCounting& hashCollisionScatter)
57{
58 if (inField.IsCellField())
59 {
60 viskores::cont::Invoker invoke;
61 viskores::cont::UnknownArrayHandle inArray = inField.GetData();
62 viskores::cont::UnknownArrayHandle outArray = inArray.NewInstanceBasic();
63
64 auto doMap = [&](auto& concreteInput)
65 {
66 using T = typename std::decay_t<decltype(concreteInput)>::ValueType::ComponentType;
67 auto concreteOutput =
68 outArray.ExtractArrayFromComponents<T>(viskores::CopyFlag::Off);
69 invoke(
70 AverageCellEdgesFieldWorklet{},
71 hashCollisionScatter,
72 cellToEdgeKeys,
73 viskores::cont::make_ArrayHandlePermutation(cellPermutationMap, concreteInput),
74 localEdgeIndices,
75 concreteOutput);
76 };
77 inArray.CastAndCallWithExtractedArray(doMap);
78
79 dataset.AddCellField(inField.GetName(), outArray);
80 }
81 else
82 {
83 dataset.AddField(inField); // pass through
84 }
85}
With this helper function, it is straightforward to process cell fields as demonstrated in Example 4.143 lines 55 – 64.
4.14.4. Variable Cell Types
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 viskores::cont::CellSetSingleType).
However, it can also be the case where an algorithm must create cells of different types (into a viskores::cont::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 Section 4.14.1 (Single Cell Type), Section 4.14.2 (Combining Like Elements), and Section 4.14.3 (Faster Combining Like Elements with Hashes). In all 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 4.14.3 (Faster Combining Like Elements with Hashes) 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 4.14.3 (Faster Combining Like Elements with Hashes).
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 Example 4.139, Example 4.140, and Example 4.141, respectively, with superficial changes made such as changing Edge to 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 viskores::cont::CellSetExplicit.
Also recall that we have to work with the information returned from the collision resolution to report on the appropriate unique cell face.
1class CountPointsInFaceWorklet : public viskores::worklet::WorkletReduceByKey
2{
3public:
4 using ControlSignature = void(KeysIn keys,
5 WholeCellSetIn<> inputCells,
6 ValuesIn originCells,
7 ValuesIn originFaces,
8 ValuesIn localFaceIndices,
9 ReducedValuesOut faceShape,
10 ReducedValuesOut numPointsInEachFace);
11 using ExecutionSignature = void(_2 inputCells,
12 _3 originCell,
13 _4 originFace,
14 _5 localFaceIndices,
15 VisitIndex localFaceIndex,
16 _6 faceShape,
17 _7 numPointsInFace);
18 using InputDomain = _1;
19
20 using ScatterType = viskores::worklet::ScatterCounting;
21
22 template<typename CellSetType,
23 typename OriginCellsType,
24 typename OriginFacesType,
25 typename LocalFaceIndicesType>
26 VISKORES_EXEC void operator()(const CellSetType& cellSet,
27 const OriginCellsType& originCells,
28 const OriginFacesType& originFaces,
29 const LocalFaceIndicesType& localFaceIndices,
30 viskores::IdComponent localFaceIndex,
31 viskores::UInt8& faceShape,
32 viskores::IdComponent& numPointsInFace) const
33 {
34 // Find the first face that matches the index given.
35 for (viskores::IdComponent faceIndex = 0;; ++faceIndex)
36 {
37 if (localFaceIndices[faceIndex] == localFaceIndex)
38 {
39 viskores::Id cellIndex = originCells[faceIndex];
40 viskores::exec::CellFaceShape(
41 originFaces[faceIndex], cellSet.GetCellShape(cellIndex), faceShape);
42 viskores::exec::CellFaceNumberOfPoints(
43 originFaces[faceIndex], cellSet.GetCellShape(cellIndex), numPointsInFace);
44 break;
45 }
46 }
47 }
48};
When extracting edges, we converted a flat array of connectivity information to an array of viskores::Vec’s using an viskores::cont::ArrayHandleGroupVec.
However, viskores::cont::ArrayHandleGroupVec can only create viskores::Vec’s of a constant size.
Instead, for this use case we need to use viskores::cont::ArrayHandleGroupVecVariable.
As described in Section 4.9.12 (Grouped Vector Arrays), viskores::cont::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 Vec-like.
The worklet in Example 4.145 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 viskores::cont::ConvertNumComponentsToOffsets() convenience function.
viskores::cont::ArrayHandleGroupVecVariable.1 viskores::cont::ArrayHandle<viskores::Id> offsets;
2 viskores::Id connectivityArraySize;
3 viskores::cont::ConvertNumComponentsToOffsets(
4 numPointsInEachFace, offsets, connectivityArraySize);
5
6 viskores::cont::CellSetExplicit<>::ConnectivityArrayType connectivityArray;
7 connectivityArray.Allocate(connectivityArraySize);
8 auto connectivityArrayVecs =
9 viskores::cont::make_ArrayHandleGroupVecVariable(connectivityArray, offsets);
Once we have created an viskores::cont::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 4.142, but we have to correctly handle the Vec-like of unknown type and size.
1class FaceIndicesWorklet : public viskores::worklet::WorkletReduceByKey
2{
3public:
4 using ControlSignature = void(KeysIn keys,
5 WholeCellSetIn<> inputCells,
6 ValuesIn originCells,
7 ValuesIn originFaces,
8 ValuesIn localFaceIndices,
9 ReducedValuesOut connectivityOut);
10 using ExecutionSignature = void(_2 inputCells,
11 _3 originCell,
12 _4 originFace,
13 _5 localFaceIndices,
14 VisitIndex localFaceIndex,
15 _6 connectivityOut);
16 using InputDomain = _1;
17
18 using ScatterType = viskores::worklet::ScatterCounting;
19
20 template<typename CellSetType,
21 typename OriginCellsType,
22 typename OriginFacesType,
23 typename LocalFaceIndicesType,
24 typename ConnectivityVecType>
25 VISKORES_EXEC void operator()(const CellSetType& cellSet,
26 const OriginCellsType& originCells,
27 const OriginFacesType& originFaces,
28 const LocalFaceIndicesType& localFaceIndices,
29 viskores::IdComponent localFaceIndex,
30 ConnectivityVecType& connectivityOut) const
31 {
32 // Find the first face that matches the index given and return it.
33 for (viskores::IdComponent faceIndex = 0;; ++faceIndex)
34 {
35 if (localFaceIndices[faceIndex] == localFaceIndex)
36 {
37 viskores::Id cellIndex = originCells[faceIndex];
38 viskores::IdComponent faceInCellIndex = originFaces[faceIndex];
39 auto cellShape = cellSet.GetCellShape(cellIndex);
40 viskores::IdComponent numPointsInFace = connectivityOut.GetNumberOfComponents();
41
42 auto globalPointIndicesForCell = cellSet.GetIndices(cellIndex);
43 for (viskores::IdComponent localPointI = 0; localPointI < numPointsInFace;
44 ++localPointI)
45 {
46 viskores::IdComponent pointInCellIndex;
47 viskores::exec::CellFaceLocalIndex(
48 localPointI, faceInCellIndex, cellShape, pointInCellIndex);
49 connectivityOut[localPointI] = globalPointIndicesForCell[pointInCellIndex];
50 }
51
52 break;
53 }
54 }
55 }
56};
With these worklets in place, we can implement a filter viskores::filter::Filter::DoExecute() as follows.
1inline VISKORES_CONT viskores::cont::DataSet ExtractFaces::DoExecute(
2 const viskores::cont::DataSet& inData)
3{
4
5 auto inCellSet = inData.GetCellSet();
6
7 // First, count the faces in each cell.
8 viskores::cont::ArrayHandle<viskores::IdComponent> faceCounts;
9 this->Invoke(CountFacesWorklet{}, inCellSet, faceCounts);
10
11 // Second, using these counts build a scatter that repeats a cell's visit
12 // for each edge in the cell.
13 viskores::worklet::ScatterCounting scatter(faceCounts);
14 viskores::worklet::ScatterCounting::OutputToInputMapType outputToInputCellMap =
15 scatter.GetOutputToInputMap(inCellSet.GetNumberOfCells());
16 viskores::worklet::ScatterCounting::VisitArrayType outputToInputFaceMap =
17 scatter.GetVisitArray(inCellSet.GetNumberOfCells());
18
19 // Third, for each face, extract a hash.
20 viskores::cont::ArrayHandle<viskores::HashType> hashValues;
21 this->Invoke(FaceHashesWorklet{}, scatter, inCellSet, hashValues);
22
23 // Fourth, use a Keys object to combine all like hashes.
24 viskores::worklet::Keys<viskores::HashType> cellToFaceKeys(hashValues);
25
26 // Fifth, use a reduce-by-key to collect like hash values, resolve collisions,
27 // and count the number of unique faces associated with each hash.
28 viskores::cont::ArrayHandle<viskores::IdComponent> localFaceIndices;
29 viskores::cont::ArrayHandle<viskores::IdComponent> numUniqueFacesInEachHash;
30 this->Invoke(FaceHashCollisionsWorklet{},
31 cellToFaceKeys,
32 inCellSet,
33 outputToInputCellMap,
34 outputToInputFaceMap,
35 localFaceIndices,
36 numUniqueFacesInEachHash);
37
38 // Sixth, use a reduce-by-key to count the number of points in each unique face.
39 // Also identify the shape of each face.
40 viskores::worklet::ScatterCounting hashCollisionScatter(numUniqueFacesInEachHash);
41
42 viskores::cont::CellSetExplicit<>::ShapesArrayType shapeArray;
43 viskores::cont::ArrayHandle<viskores::IdComponent> numPointsInEachFace;
44
45 this->Invoke(CountPointsInFaceWorklet{},
46 hashCollisionScatter,
47 cellToFaceKeys,
48 inCellSet,
49 outputToInputCellMap,
50 outputToInputFaceMap,
51 localFaceIndices,
52 shapeArray,
53 numPointsInEachFace);
54
55 // Seventh, convert the numPointsInEachFace array to an offsets array and use that
56 // to create an ArrayHandleGroupVecVariable.
57 viskores::cont::ArrayHandle<viskores::Id> offsets;
58 viskores::Id connectivityArraySize;
59 viskores::cont::ConvertNumComponentsToOffsets(
60 numPointsInEachFace, offsets, connectivityArraySize);
61
62 viskores::cont::CellSetExplicit<>::ConnectivityArrayType connectivityArray;
63 connectivityArray.Allocate(connectivityArraySize);
64 auto connectivityArrayVecs =
65 viskores::cont::make_ArrayHandleGroupVecVariable(connectivityArray, offsets);
66
67 // Eigth, use a reduce-by-key to extract indices for each unique face.
68 this->Invoke(FaceIndicesWorklet{},
69 hashCollisionScatter,
70 cellToFaceKeys,
71 inCellSet,
72 outputToInputCellMap,
73 outputToInputFaceMap,
74 localFaceIndices,
75 connectivityArrayVecs);
76
77 // Ninth, use the created connectivity array and others to build a cell set.
78 viskores::cont::CellSetExplicit<> outCellSet;
79 outCellSet.Fill(inCellSet.GetNumberOfPoints(), shapeArray, connectivityArray, offsets);
80
81 auto fieldMapper =
82 [&](viskores::cont::DataSet& dataset, const viskores::cont::Field& inField)
83 {
84 MapCellEdgesField(dataset,
85 inField,
86 outputToInputCellMap,
87 cellToFaceKeys,
88 localFaceIndices,
89 hashCollisionScatter);
90 };
91 return this->CreateResult(inData, outCellSet, fieldMapper);
92}
As noted previously, in practice viskores::filter::Filter::DoExecute() is called on viskores::cont::DataSet objects to create new viskores::cont::DataSet objects.
The process for doing so is no different from our previous algorithm as described at the end of Section 4.14.3 (Faster Combining Like Elements with Hashes) in Example 4.144.