VTK-m  2.0
CellSetDualGraph.h
Go to the documentation of this file.
1 //============================================================================
2 // Copyright (c) Kitware, Inc.
3 // All rights reserved.
4 // See LICENSE.txt for details.
5 //
6 // This software is distributed WITHOUT ANY WARRANTY; without even
7 // the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8 // PURPOSE. See the above copyright notice for more information.
9 //============================================================================
10 #ifndef vtk_m_worklet_connectivity_CellSetDualGraph_h
11 #define vtk_m_worklet_connectivity_CellSetDualGraph_h
12 
13 #include <vtkm/cont/Algorithm.h>
15 #include <vtkm/exec/CellEdge.h>
21 
22 namespace vtkm
23 {
24 namespace worklet
25 {
26 namespace connectivity
27 {
28 namespace detail
29 {
30 struct EdgeCount : public vtkm::worklet::WorkletVisitCellsWithPoints
31 {
32  using ControlSignature = void(CellSetIn, FieldOutCell numEdgesInCell);
33 
34  using ExecutionSignature = void(CellShape, PointCount, _2);
35 
36  using InputDomain = _1;
37 
38  template <typename CellShapeTag>
39  VTKM_EXEC void operator()(CellShapeTag cellShape,
40  vtkm::IdComponent pointCount,
41  vtkm::IdComponent& numEdges) const
42  {
43  vtkm::exec::CellEdgeNumberOfEdges(pointCount, cellShape, numEdges);
44  }
45 };
46 
47 struct EdgeExtract : public vtkm::worklet::WorkletVisitCellsWithPoints
48 {
49  using ControlSignature = void(CellSetIn, FieldOutCell cellIndices, FieldOutCell edgeIndices);
50 
51  using ExecutionSignature = void(CellShape, InputIndex, PointIndices, VisitIndex, _2, _3);
52 
53  using InputDomain = _1;
54 
55  using ScatterType = vtkm::worklet::ScatterCounting;
56 
57  template <typename CellShapeTag,
58  typename CellIndexType,
59  typename PointIndexVecType,
60  typename EdgeIndexVecType>
61  VTKM_EXEC void operator()(CellShapeTag cellShape,
62  CellIndexType cellIndex,
63  const PointIndexVecType& pointIndices,
64  vtkm::IdComponent visitIndex,
65  CellIndexType& cellIndexOut,
66  EdgeIndexVecType& edgeIndices) const
67  {
68  cellIndexOut = cellIndex;
69  vtkm::exec::CellEdgeCanonicalId(
70  pointIndices.GetNumberOfComponents(), visitIndex, cellShape, pointIndices, edgeIndices);
71  }
72 };
73 
74 struct CellToCellConnectivity : public vtkm::worklet::WorkletMapField
75 {
76  using ControlSignature = void(FieldIn index,
77  WholeArrayIn cells,
78  WholeArrayOut from,
79  WholeArrayOut to);
80 
81  using ExecutionSignature = void(_1, InputIndex, _2, _3, _4);
82 
83  using InputDomain = _1;
84 
85  template <typename ConnectivityPortalType, typename CellIdPortalType>
86  VTKM_EXEC void operator()(vtkm::Id offset,
87  vtkm::Id index,
88  const CellIdPortalType& cells,
89  ConnectivityPortalType& from,
90  ConnectivityPortalType& to) const
91  {
92  from.Set(index * 2, cells.Get(offset));
93  to.Set(index * 2, cells.Get(offset + 1));
94  from.Set(index * 2 + 1, cells.Get(offset + 1));
95  to.Set(index * 2 + 1, cells.Get(offset));
96  }
97 };
98 } // vtkm::worklet::connectivity::detail
99 
101 {
103 
107  {
108  // Get number of edges for each cell and use it as scatter count.
111  edgesPerCellDisp.Invoke(cellSet, numEdgesPerCell);
112 
113  // Get uncompress Cell to Edge mapping
114  vtkm::worklet::ScatterCounting scatter{ numEdgesPerCell };
116  edgeExtractDisp.Invoke(cellSet, cellIds, cellEdges);
117  }
118 
119 public:
120  struct degree2
121  {
122  VTKM_EXEC
123  bool operator()(vtkm::Id degree) const { return degree >= 2; }
124  };
125 
126  static void Run(const vtkm::cont::UnknownCellSet& cellSet,
127  vtkm::cont::ArrayHandle<vtkm::Id>& numIndicesArray,
128  vtkm::cont::ArrayHandle<vtkm::Id>& indexOffsetArray,
129  vtkm::cont::ArrayHandle<vtkm::Id>& connectivityArray)
130  {
131  // calculate the uncompressed Edge to Cell connectivity from Point to Cell connectivity
132  // in the CellSet
135  EdgeToCellConnectivity(cellSet, cellIds, cellEdges);
136 
137  // sort cell ids by cell edges, this groups cells by cell edges
138  Algorithm::SortByKey(cellEdges, cellIds);
139 
140  // count how many times an edge is shared by cells.
142  vtkm::cont::ArrayHandle<vtkm::Id> uniqueEdgeDegree;
144  cellEdges,
146  uniqueEdges,
147  uniqueEdgeDegree,
148  vtkm::Add());
149 
150  // Extract edges shared by two cells
152  Algorithm::CopyIf(uniqueEdges, uniqueEdgeDegree, sharedEdges, degree2());
153 
154  // find shared edges within all the edges.
156  Algorithm::LowerBounds(cellEdges, sharedEdges, lb);
157 
158  // take each shared edge and the cells to create 2 edges of the dual graph
161  connFrom.Allocate(sharedEdges.GetNumberOfValues() * 2);
162  connTo.Allocate(sharedEdges.GetNumberOfValues() * 2);
164  c2cDisp.Invoke(lb, cellIds, connFrom, connTo);
165 
166  // Turn dual graph into Compressed Sparse Row format
167  Algorithm::SortByKey(connFrom, connTo);
168  Algorithm::Copy(connTo, connectivityArray);
169 
170  vtkm::cont::ArrayHandle<vtkm::Id> dualGraphVertices;
172  connFrom,
174  dualGraphVertices,
175  numIndicesArray,
176  vtkm::Add());
177  Algorithm::ScanExclusive(numIndicesArray, indexOffsetArray);
178  }
179 };
180 }
181 }
182 }
183 
184 #endif //vtk_m_worklet_connectivity_CellSetDualGraph_h
vtkm::cont::ArrayHandle::GetNumberOfValues
VTKM_CONT vtkm::Id GetNumberOfValues() const
Returns the number of entries in the array.
Definition: ArrayHandle.h:448
vtkm::cont::Algorithm::SortByKey
static VTKM_CONT void SortByKey(vtkm::cont::DeviceAdapterId devId, vtkm::cont::ArrayHandle< T, StorageT > &keys, vtkm::cont::ArrayHandle< U, StorageU > &values)
Definition: Algorithm.h:993
vtkm::cont::ArrayHandle< vtkm::Id >
VTKM_EXEC
#define VTKM_EXEC
Definition: ExportMacros.h:51
vtkm
Groups connected points that have the same field value.
Definition: Atomic.h:19
WorkletMapField.h
vtkm::cont::ArrayHandle::Allocate
VTKM_CONT void Allocate(vtkm::Id numberOfValues, vtkm::CopyFlag preserve, vtkm::cont::Token &token) const
Allocates an array large enough to hold the given number of values.
Definition: ArrayHandle.h:465
vtkm::IdComponent
vtkm::Int32 IdComponent
Represents a component ID (index of component in a vector).
Definition: Types.h:168
vtkm::worklet::connectivity::CellSetDualGraph
Definition: CellSetDualGraph.h:100
vtkm::cont::Algorithm::LowerBounds
static VTKM_CONT void LowerBounds(vtkm::cont::DeviceAdapterId devId, const vtkm::cont::ArrayHandle< T, CIn > &input, const vtkm::cont::ArrayHandle< T, CVal > &values, vtkm::cont::ArrayHandle< vtkm::Id, COut > &output)
Definition: Algorithm.h:604
vtkm::cont::Algorithm::Copy
static VTKM_CONT bool Copy(vtkm::cont::DeviceAdapterId devId, const vtkm::cont::ArrayHandle< T, CIn > &input, vtkm::cont::ArrayHandle< U, COut > &output)
Definition: Algorithm.h:410
vtkm::cont::UnknownCellSet
A CellSet of an unknown type.
Definition: UnknownCellSet.h:48
vtkm::worklet::connectivity::CellSetDualGraph::Run
static void Run(const vtkm::cont::UnknownCellSet &cellSet, vtkm::cont::ArrayHandle< vtkm::Id > &numIndicesArray, vtkm::cont::ArrayHandle< vtkm::Id > &indexOffsetArray, vtkm::cont::ArrayHandle< vtkm::Id > &connectivityArray)
Definition: CellSetDualGraph.h:126
vtkm::Id
vtkm::Int32 Id
Represents an ID (index into arrays).
Definition: Types.h:191
DispatcherMapField.h
ScatterCounting.h
vtkm::worklet::connectivity::CellSetDualGraph::EdgeToCellConnectivity
static void EdgeToCellConnectivity(const vtkm::cont::UnknownCellSet &cellSet, vtkm::cont::ArrayHandle< vtkm::Id > &cellIds, vtkm::cont::ArrayHandle< vtkm::Id2 > &cellEdges)
Definition: CellSetDualGraph.h:104
vtkm::Add
Definition: Types.h:222
vtkm::worklet::ScatterCounting
A scatter that maps input to some numbers of output.
Definition: ScatterCounting.h:44
vtkm::worklet::DispatcherMapField
Dispatcher for worklets that inherit from WorkletMapField.
Definition: DispatcherMapField.h:25
Algorithm.h
vtkm::worklet::DispatcherMapTopology
Dispatcher for worklets that inherit from WorkletMapTopology.
Definition: DispatcherMapTopology.h:31
vtkm::cont::Algorithm::ScanExclusive
static VTKM_CONT T ScanExclusive(vtkm::cont::DeviceAdapterId devId, const vtkm::cont::ArrayHandle< T, CIn > &input, vtkm::cont::ArrayHandle< T, COut > &output)
Definition: Algorithm.h:816
vtkm::worklet::WorkletVisitCellsWithPoints
Base class for worklets that map from Points to Cells.
Definition: WorkletMapTopology.h:255
vtkm::cont::Algorithm::CopyIf
static VTKM_CONT void CopyIf(vtkm::cont::DeviceAdapterId devId, const vtkm::cont::ArrayHandle< T, CIn > &input, const vtkm::cont::ArrayHandle< U, CStencil > &stencil, vtkm::cont::ArrayHandle< T, COut > &output)
Definition: Algorithm.h:435
vtkm::cont::ArrayHandleConstant
An array handle with a constant value.
Definition: ArrayHandleConstant.h:63
vtkm::cont::Algorithm
Definition: Algorithm.h:385
vtkm::cont::Algorithm::ReduceByKey
static VTKM_CONT void ReduceByKey(vtkm::cont::DeviceAdapterId devId, const vtkm::cont::ArrayHandle< T, CKeyIn > &keys, const vtkm::cont::ArrayHandle< U, CValIn > &values, vtkm::cont::ArrayHandle< T, CKeyOut > &keys_output, vtkm::cont::ArrayHandle< U, CValOut > &values_output, BinaryFunctor binary_functor)
Definition: Algorithm.h:697
CellEdge.h
CellSetSingleType.h
DispatcherMapTopology.h
WorkletMapTopology.h
vtkm::worklet::connectivity::CellSetDualGraph::degree2::operator()
VTKM_EXEC bool operator()(vtkm::Id degree) const
Definition: CellSetDualGraph.h:123
vtkm::worklet::WorkletMapField
Base class for worklets that do a simple mapping of field arrays.
Definition: WorkletMapField.h:38
vtkm::worklet::connectivity::CellSetDualGraph::degree2
Definition: CellSetDualGraph.h:120