VTK-m  2.0
InitializeActiveEdges.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 // Copyright (c) 2018, The Regents of the University of California, through
11 // Lawrence Berkeley National Laboratory (subject to receipt of any required approvals
12 // from the U.S. Dept. of Energy). All rights reserved.
13 //
14 // Redistribution and use in source and binary forms, with or without modification,
15 // are permitted provided that the following conditions are met:
16 //
17 // (1) Redistributions of source code must retain the above copyright notice, this
18 // list of conditions and the following disclaimer.
19 //
20 // (2) Redistributions in binary form must reproduce the above copyright notice,
21 // this list of conditions and the following disclaimer in the documentation
22 // and/or other materials provided with the distribution.
23 //
24 // (3) Neither the name of the University of California, Lawrence Berkeley National
25 // Laboratory, U.S. Dept. of Energy nor the names of its contributors may be
26 // used to endorse or promote products derived from this software without
27 // specific prior written permission.
28 //
29 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
30 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
31 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
32 // IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
33 // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
34 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
36 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
37 // OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
38 // OF THE POSSIBILITY OF SUCH DAMAGE.
39 //
40 //=============================================================================
41 //
42 // This code is an extension of the algorithm presented in the paper:
43 // Parallel Peak Pruning for Scalable SMP Contour Tree Computation.
44 // Hamish Carr, Gunther Weber, Christopher Sewell, and James Ahrens.
45 // Proceedings of the IEEE Symposium on Large Data Analysis and Visualization
46 // (LDAV), October 2016, Baltimore, Maryland.
47 //
48 // The PPP2 algorithm and software were jointly developed by
49 // Hamish Carr (University of Leeds), Gunther H. Weber (LBNL), and
50 // Oliver Ruebel (LBNL)
51 //==============================================================================
52 
53 #ifndef vtk_m_worklet_contourtree_augmented_active_graph_initialize_active_edges_h
54 #define vtk_m_worklet_contourtree_augmented_active_graph_initialize_active_edges_h
55 
56 #include <vtkm/exec/arg/BasicArg.h>
59 
60 namespace vtkm
61 {
62 namespace worklet
63 {
64 namespace contourtree_augmented
65 {
66 namespace active_graph_inc
67 {
68 
69 
70 // Worklet for computing the sort indices from the sort order
71 template <class MeshClassType>
73 {
74 public:
76  //struct _10 : vtkm::exec::arg::BasicArg<10> { };
77  //struct _11 : vtkm::exec::arg::BasicArg<11> { };
78 
79  typedef void ControlSignature(
80  FieldIn outdegree, // (input) outdegree
81  ExecObject meshStructure, // (input) execution object with the mesh structure
82  FieldIn firstEdge, // (input)
83  FieldIn globalIndex, // (input) ActiveGraph.GlobalIndex
84  WholeArrayIn extrema, // (input)
85  WholeArrayIn neighbourhoodMasks, // (input)
86  WholeArrayOut edgeNear, // (output) edgeNear
87  WholeArrayOut edgeFar, // (output) edgeFar
88  WholeArrayOut activeEdges); // (output) activeEdges
89  typedef void ExecutionSignature(_1, InputIndex, _2, _3, _4, _5, _6, _7, _8, _9);
90 
91  using InputDomain = _1;
92 
93  // Default Constructor
96 
97  template <typename MeshStructureType, typename InFieldPortalType, typename OutFieldPortalType>
98  VTKM_EXEC void operator()(const vtkm::Id& outdegree,
99  const vtkm::Id activeIndex,
100  const MeshStructureType& meshStructure,
101  const vtkm::Id& firstEdgeIndex,
102  const vtkm::Id& sortIndex, // = GlobalIndex.Get(activeIndex)
103  const InFieldPortalType& extrema,
104  const InFieldPortalType& neighbourhoodMasks,
105  const OutFieldPortalType& edgeNear,
106  const OutFieldPortalType& edgeFar,
107  const OutFieldPortalType& activeEdges) const
108  {
109  if (outdegree != 0)
110  {
111  // temporary array for storing edges
112  vtkm::Id neigbourComponents[MeshClassType::MAX_OUTDEGREE];
113  int currNbrNo = 0;
114  for (vtkm::Id nbrNo = 0; nbrNo < meshStructure.GetMaxNumberOfNeighbours(); ++nbrNo)
115  if (neighbourhoodMasks.Get(sortIndex) & (static_cast<vtkm::Id>(1) << nbrNo))
116  {
117  neigbourComponents[currNbrNo++] = meshStructure.GetNeighbourIndex(sortIndex, nbrNo);
118  }
119 
120 
121  // arcs stores the ID from the join tree - i.e. the chain extremum
122  // we cannot store the correct ID yet, because it may not have been assigned yet
123  // in serial, we could hack around this by processing the vertices in a given order
124  // but in parallel we can't, so we have two stages:
125  // in this stage, we store the join tree ID (after suppressing flags)
126  // in a later stage, we convert it to an active graph ID
127  // firstEdge / outdegree / edgeNear / edgeFar are straightforward
128  // as with earlier versions, the parallel equivalent will need to use stream compression
129  // but the serial version can be expressed more simply.
130 
131  for (vtkm::Id edge = 0; edge < outdegree; edge++)
132  { // per edge
133  // compute the edge index in the edge arrays
134  vtkm::Id edgeID = firstEdgeIndex + edge;
135 
136  // now set the low and high ends
137  edgeNear.Set(edgeID, activeIndex);
138  edgeFar.Set(edgeID, MaskedIndex(extrema.Get(neigbourComponents[edge])));
139 
140  // and save the edge itself
141  activeEdges.Set(edgeID, edgeID);
142  } // per edge
143  }
144 
145  // This operator implements the following loop from the serial code
146  /*for (indexType activeIndex = 0; activeIndex < nCriticalPoints; ++activeIndex)
147  {
148  indexType outdegree = outdegree[activeIndex];
149  if (outdegree != 0)
150  {
151  indexType sortIndex = globalIndex[activeIndex];
152 
153  // temporary array for storing edges
154  indexType neigbourComponents[Mesh::MAX_OUTDEGREE];
155  int currNbrNo = 0;
156  for (vtkm::Int32 nbrNo = 0; nbrNo < mesh.GetMaxNumberOfNeighbours(); ++nbrNo)
157  if (neighbourhoodMasks[sortIndex] & 1 << nbrNo)
158  {
159  neigbourComponents[currNbrNo++] = mesh.GetNeighbourIndex(sortIndex, nbrNo);
160  }
161 
162 
163  // arcs stores the ID from the join tree - i.e. the chain extremum
164  // we cannot store the correct ID yet, because it may not have been assigned yet
165  // in serial, we could hack around this by processing the vertices in a given order
166  // but in parallel we can't, so we have two stages:
167  // in this stage, we store the join tree ID (after suppressing flags)
168  // in a later stage, we convert it to an active graph ID
169  // firstEdge / outdegree / edgeNear / edgeFar are straightforward
170  // as with earlier versions, the parallel equivalent will need to use stream compression
171  // but the serial version can be expressed more simply.
172 
173  for (indexType edge = 0; edge < outdegree; edge++)
174  { // per edge
175  // compute the edge index in the edge arrays
176  indexType edgeID = firstEdge[activeIndex] + edge;
177 
178  // now set the low and high ends
179  edgeNear[edgeID] = activeIndex;
180  edgeFar[edgeID] = MaskedIndex(extrema[neigbourComponents[edge]]);
181 
182  // and save the edge itself
183  activeEdges[edgeID] = edgeID;
184  } // per edge
185  }
186  } // per activeIndex*/
187  }
188 }; // Mesh2D_DEM_VertexStarter
189 
190 
191 } // namespace mesh_dem_triangulation_worklets
192 } // namespace contourtree_augmented
193 } // namespace worklet
194 } // namespace vtkm
195 
196 #endif
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeActiveEdges::operator()
VTKM_EXEC void operator()(const vtkm::Id &outdegree, const vtkm::Id activeIndex, const MeshStructureType &meshStructure, const vtkm::Id &firstEdgeIndex, const vtkm::Id &sortIndex, const InFieldPortalType &extrema, const InFieldPortalType &neighbourhoodMasks, const OutFieldPortalType &edgeNear, const OutFieldPortalType &edgeFar, const OutFieldPortalType &activeEdges) const
Definition: InitializeActiveEdges.h:98
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_EXEC_CONT
#define VTKM_EXEC_CONT
Definition: ExportMacros.h:52
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeActiveEdges::InputDomain
_1 InputDomain
Definition: InitializeActiveEdges.h:91
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeActiveEdges::InitializeActiveEdges
VTKM_EXEC_CONT InitializeActiveEdges()
Definition: InitializeActiveEdges.h:95
vtkm::worklet::contourtree_augmented::MaskedIndex
VTKM_EXEC_CONT vtkm::Id MaskedIndex(vtkm::Id flaggedIndex)
Definition: filter/scalar_topology/worklet/contourtree_augmented/Types.h:127
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeActiveEdges::ExecutionSignature
void ExecutionSignature(_1, InputIndex, _2, _3, _4, _5, _6, _7, _8, _9)
Definition: InitializeActiveEdges.h:89
vtkm::Id
vtkm::Int32 Id
Represents an ID (index into arrays).
Definition: Types.h:191
MAX_OUTDEGREE
#define MAX_OUTDEGREE
Definition: Mesh2D_DEM_Triangulation_Macros.h:76
vtkm::worklet::WorkletMapField::FieldIn
A control signature tag for input fields.
Definition: WorkletMapField.h:49
Types.h
BasicArg.h
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeActiveEdges
Definition: InitializeActiveEdges.h:72
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeActiveEdges::ControlSignature
void ControlSignature(FieldIn outdegree, ExecObject meshStructure, FieldIn firstEdge, FieldIn globalIndex, WholeArrayIn extrema, WholeArrayIn neighbourhoodMasks, WholeArrayOut edgeNear, WholeArrayOut edgeFar, WholeArrayOut activeEdges)
Additional basic execution argument tags.
Definition: InitializeActiveEdges.h:79
vtkm::exec::arg::InputIndex
The ExecutionSignature tag to use to get the input index.
Definition: InputIndex.h:42
vtkm::worklet::WorkletMapField
Base class for worklets that do a simple mapping of field arrays.
Definition: WorkletMapField.h:38