VTK-m  2.0
SetTriangleSuperarcId.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_process_contourtree_inc_set_triangle_superarc_id_h
54 #define vtk_m_worklet_contourtree_augmented_process_contourtree_inc_set_triangle_superarc_id_h
55 
58 
59 namespace vtkm
60 {
61 namespace worklet
62 {
63 namespace contourtree_augmented
64 {
65 namespace process_contourtree_inc
66 {
67 
68 /*
69  * This code is taken from vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ComputeRegularStructure_LocateSuperarcs
70  * The only changes that were made are annotated with the @peter comment.
71  * The difference with the original workelet is that this one only identifies the superacs using two endpoints and an isovalue,
72  * that is it can work with regular values (not necessarily vertices).
73  */
75 {
76 public:
77  typedef void ControlSignature(
78  // The endpoints are given in terms of their meshIndex, not CtNodeIndex
79  WholeArrayIn endpoints, // (input)
80  WholeArrayIn dataField, // (input)
81  WholeArrayIn isovalue, // (input)
82  WholeArrayIn sortOrder, // (input)
83  WholeArrayIn sortIndices, // (input)
84  WholeArrayIn contourTreeSuperparents, // (input)
85  WholeArrayIn contourTreeWhenTransferred, // (input)
86  WholeArrayIn contourTreeHyperparents, // (input)
87  WholeArrayIn contourTreeHyperarcs, // (input)
88  WholeArrayIn contourTreeHypernodes, // (input)
89  WholeArrayIn contourTreeSupernodes, // (input)
90  WholeArrayIn meshExtremaPeaks, // (input)
91  WholeArrayIn meshExtremaPits, // (input)
92  WholeArrayOut superarcIds // (output)
93  ); // (input)
94 
95  typedef void
96  ExecutionSignature(InputIndex, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14);
97  using InputDomain = _1;
98 
99  vtkm::Id numHypernodes; // contourTree.Hypernodes.GetNumberOfValues()
100  vtkm::Id numSupernodes; // contourTree.Supernodes.GetNumberOfValues()
101 
102  // Default Constructor
104  SetTriangleSuperarcId(vtkm::Id NumHypernodes, vtkm::Id NumSupernodes)
105  : numHypernodes(NumHypernodes)
106  , numSupernodes(NumSupernodes)
107  {
108  }
109 
110  template <typename EndpointsArrayPortalType,
111  typename InFieldArrayPortalType,
112  typename InArrayPortalType,
113  typename OutArrayPortalType>
114  VTKM_EXEC void operator()(const vtkm::Id node,
115  const EndpointsArrayPortalType& endpointsPortal,
116  const InFieldArrayPortalType& fieldPortal,
117  const InFieldArrayPortalType& isovaluePortal,
118  const InArrayPortalType& sortOrder,
119  const InArrayPortalType& sortIndices,
120  const InArrayPortalType& contourTreeSuperparentsPortal,
121  const InArrayPortalType& contourTreeWhenTransferredPortal,
122  const InArrayPortalType& contourTreeHyperparentsPortal,
123  const InArrayPortalType& contourTreeHyperarcsPortal,
124  const InArrayPortalType& contourTreeHypernodesPortal,
125  const InArrayPortalType& contourTreeSupernodesPortal,
126  const InArrayPortalType& meshExtremaPeaksPortal,
127  const InArrayPortalType& meshExtremaPitsPortal,
128  const OutArrayPortalType& superarcIdsPortal) const
129  {
130 
131  using namespace std;
132  using namespace vtkm;
133  using namespace vtkm::worklet::contourtree_augmented;
134 
135  // Unpack Data
136  Float32 isovalue = isovaluePortal.Get(node);
137 
138  //vtkm::Id edgeEndpointA = sortIndices.Get(triangle.representativeEdge[0]);
139  //vtkm::Id edgeEndpointB = sortIndices.Get(triangle.representativeEdge[1]);
140 
141  vtkm::Id edgeEndpointA = sortIndices.Get(endpointsPortal.Get(node)[0]);
142  vtkm::Id edgeEndpointB = sortIndices.Get(endpointsPortal.Get(node)[1]);
143 
144  // Have to make sure that A is smaller than B, otherwise the path will have redudant edges
145  // This is because we take the peak of A and pit of B, if we do it the other way we get incorrect labeling
146  if (edgeEndpointA < edgeEndpointB)
147  {
148  vtkm::Id temp = edgeEndpointA;
149  edgeEndpointA = edgeEndpointB;
150  edgeEndpointB = temp;
151  }
152 
153  // we will need to prune top and bottom until one of them prunes past the node
154  vtkm::Id top = meshExtremaPeaksPortal.Get(edgeEndpointA);
155  vtkm::Id bottom = meshExtremaPitsPortal.Get(edgeEndpointB);
156 
157  // these are the regular IDs of supernodes, so their superparents are already set
158  vtkm::Id topSuperparent = contourTreeSuperparentsPortal.Get(MaskedIndex(top));
159  vtkm::Id bottomSuperparent = contourTreeSuperparentsPortal.Get(MaskedIndex(bottom));
160 
161  // and we can also find out when they transferred
162  vtkm::Id topWhen = contourTreeWhenTransferredPortal.Get(topSuperparent);
163  vtkm::Id bottomWhen = contourTreeWhenTransferredPortal.Get(bottomSuperparent);
164 
165  // and their hyperparent
166  vtkm::Id topHyperparent = contourTreeHyperparentsPortal.Get(topSuperparent);
167  vtkm::Id bottomHyperparent = contourTreeHyperparentsPortal.Get(bottomSuperparent);
168 
169  // our goal is to work out the true hyperparent of the node
170  vtkm::Id hyperparent = (vtkm::Id)NO_SUCH_ELEMENT;
171 
172  //printf ("We are starting at node %llu for arc between %llu and %llu with top %llu, bottom %llu, topSuperparent %llu, bottomSuperparent %llu, topWhen %llu, bottomWhen %llu, topHyperparent %llu, bottomHyperparent %llu. \n", node, edgeEndpointA, edgeEndpointB, MaskedIndex(top), MaskedIndex(bottom), MaskedIndex(topSuperparent), MaskedIndex(bottomSuperparent), MaskedIndex(topWhen), MaskedIndex(bottomWhen), MaskedIndex(topHyperparent), MaskedIndex(bottomHyperparent));
173 
174  // now we loop until one of them goes past the vertex
175  // the invariant here is that the first direction to prune past the vertex prunes it
176  while (NoSuchElement(hyperparent))
177  { // loop to find pruner
178 
179  // we test the one that prunes first
180  if (MaskedIndex(topWhen) < MaskedIndex(bottomWhen))
181  { // top pruned first
182 
183  // we prune down to the bottom of the hyperarc in either case, by updating the top superparent
184  topSuperparent = contourTreeHyperarcsPortal.Get(MaskedIndex(topHyperparent));
185  top = contourTreeSupernodesPortal.Get(MaskedIndex(topSuperparent));
186 
187  topWhen = contourTreeWhenTransferredPortal.Get(MaskedIndex(topSuperparent));
188 
189  // test to see if we've passed the node
190  // @ORIGINAL
191  //if (top < node)
192  // @PETER HRISTOV
193  if (fieldPortal.Get(sortOrder.Get(MaskedIndex(top))) < isovalue)
194  { // just pruned past
195  hyperparent = topHyperparent;
196  } // just pruned past
197  // == is not possible, since node is regular
198  else // top < node
199  { // not pruned past
200  topHyperparent = contourTreeHyperparentsPortal.Get(MaskedIndex(topSuperparent));
201  } // not pruned past
202  } // top pruned first
203  else if (MaskedIndex(topWhen) > MaskedIndex(bottomWhen))
204  { // bottom pruned first
205  // we prune up to the top of the hyperarc in either case, by updating the bottom superparent
206  bottomSuperparent = contourTreeHyperarcsPortal.Get(MaskedIndex(bottomHyperparent));
207  bottom = contourTreeSupernodesPortal.Get(MaskedIndex(bottomSuperparent));
208  bottomWhen = contourTreeWhenTransferredPortal.Get(MaskedIndex(bottomSuperparent));
209  // test to see if we've passed the node
210  // @ORIGINAL
211  //if (bottom > node)
212  // @PETER
213  if (fieldPortal.Get(sortOrder.Get(MaskedIndex(bottom))) > isovalue)
214  { // just pruned past
215  hyperparent = bottomHyperparent;
216  } // just pruned past
217  // == is not possible, since node is regular
218  else // bottom > node
219  { // not pruned past
220  bottomHyperparent = contourTreeHyperparentsPortal.Get(MaskedIndex(bottomSuperparent));
221  } // not pruned past
222  } // bottom pruned first
223  else
224  { // both prune simultaneously
225  // this can happen when both top & bottom prune in the same pass because they belong to the same hyperarc
226  // but this means that they must have the same hyperparent, so we know the correct hyperparent & can check whether it ascends
227  hyperparent = bottomHyperparent;
228  } // both prune simultaneously
229  } // loop to find pruner
230 
231  // we have now set the hyperparent correctly, so we retrieve it's hyperarc to find whether it ascends or descends
232  if (IsAscending(contourTreeHyperarcsPortal.Get(hyperparent)))
233  { // ascending hyperarc
234 
235  // the supernodes on the hyperarc are in sorted low-high order
236  vtkm::Id lowSupernode = contourTreeHypernodesPortal.Get(hyperparent);
237  vtkm::Id highSupernode;
238  // if it's at the right hand end, take the last supernode in the array
239  if (MaskedIndex(hyperparent) == numHypernodes - 1)
240  highSupernode = numSupernodes - 1;
241  // otherwise, take the supernode just before the next hypernode
242  else
243  highSupernode = contourTreeHypernodesPortal.Get(MaskedIndex(hyperparent) + 1) - 1;
244  // now, the high supernode may be lower than the element, because the node belongs
245  // between it and the high end of the hyperarc
246  // @ORIGINAL
247  //if (contourTreeSupernodesPortal.Get(highSupernode) < node)
248  // @PETER
249  if (fieldPortal.Get(sortOrder.Get(
250  MaskedIndex(contourTreeSupernodesPortal.Get(MaskedIndex(highSupernode))))) < isovalue)
251  // @ORIGINAL
252  //contourTreeSuperparentsPortal.Set(node, highSupernode);
253  // @PETER
254  //triangle.superarcId = highSupernode;
255  superarcIdsPortal.Set(node, highSupernode);
256  // otherwise, we do a binary search of the superarcs
257  else
258  { // node between high & low
259  // keep going until we span exactly
260  while (highSupernode - lowSupernode > 1)
261  { // binary search
262  // find the midway supernode
263  vtkm::Id midSupernode = (lowSupernode + highSupernode) / 2;
264  // test against the node
265  // @ORIGINAL
266  //if (contourTreeSupernodesPortal.Get(midSupernode) > node)
267  // @PETER
268  if (fieldPortal.Get(sortOrder.Get((contourTreeSupernodesPortal.Get((midSupernode))))) >
269  isovalue)
270  highSupernode = midSupernode;
271  // == can't happen since node is regular
272  else
273  lowSupernode = midSupernode;
274  } // binary search
275 
276  // now we can use the low node as the superparent
277  // @ORIGINAL
278  //contourTreeSuperparentsPortal.Set(node, lowSupernode);
279  // @PETER
280  //triangle.superarcId = lowSupernode;
281  superarcIdsPortal.Set(node, lowSupernode);
282  } // node between high & low
283  } // ascending hyperarc
284  else
285  { // descending hyperarc
286  // the supernodes on the hyperarc are in sorted high-low order
287  vtkm::Id highSupernode = contourTreeHypernodesPortal.Get(hyperparent);
288  vtkm::Id lowSupernode;
289  // if it's at the right hand end, take the last supernode in the array
290  if (MaskedIndex(hyperparent) == numHypernodes - 1)
291  { // last hyperarc
292  lowSupernode = numSupernodes - 1;
293  } // last hyperarc
294  // otherwise, take the supernode just before the next hypernode
295  else
296  { // other hyperarc
297  lowSupernode = contourTreeHypernodesPortal.Get(MaskedIndex(hyperparent) + 1) - 1;
298  } // other hyperarc
299  // now, the low supernode may be higher than the element, because the node belongs
300  // between it and the low end of the hyperarc
301  // @ORIGINAL
302  //if (contourTreeSupernodesPortal.Get(lowSupernode) > node)
303  // @PETER
304  if (fieldPortal.Get(sortOrder.Get(
305  MaskedIndex(contourTreeSupernodesPortal.Get(MaskedIndex(lowSupernode))))) > isovalue)
306  // @ORIGINAL
307  //contourTreeSuperparentsPortal.Set(node, lowSupernode);
308  // @PETER
309  //triangle.superarcId = lowSupernode;
310  superarcIdsPortal.Set(node, lowSupernode);
311  // otherwise, we do a binary search of the superarcs
312  else
313  { // node between low & high
314  // keep going until we span exactly
315  while (lowSupernode - highSupernode > 1)
316  { // binary search
317  // find the midway supernode
318  vtkm::Id midSupernode = (highSupernode + lowSupernode) / 2;
319  // test against the node
320  // @ORIGINAL
321  //if (contourTreeSupernodesPortal.Get(midSupernode) > node)
322  // @PETER
323  if (fieldPortal.Get(sortOrder.Get(MaskedIndex(
324  contourTreeSupernodesPortal.Get(MaskedIndex(midSupernode))))) > isovalue)
325  highSupernode = midSupernode;
326  // == can't happen since node is regular
327  else
328  lowSupernode = midSupernode;
329  } // binary search
330  // now we can use the high node as the superparent
331  // @ORIGINAL
332  //contourTreeSuperparentsPortal.Set(node, highSupernode);
333  // @PETER
334  //triangle.superarcId = highSupernode;
335  superarcIdsPortal.Set(node, highSupernode);
336  } // node between low & high
337  } // descending hyperarc
338 
339  //mcTriangles.Set(node, triangle);
340  }
341 };
342 
343 } // process_contourtree_inc
344 } // namespace contourtree_augmented
345 } // namespace worklet
346 } // namespace vtkm
347 
348 #endif
vtkm::worklet::contourtree_augmented::IsAscending
VTKM_EXEC_CONT bool IsAscending(vtkm::Id flaggedIndex)
Definition: filter/scalar_topology/worklet/contourtree_augmented/Types.h:121
vtkm::worklet::contourtree_augmented::process_contourtree_inc::SetTriangleSuperarcId::InputDomain
_1 InputDomain
Definition: SetTriangleSuperarcId.h:97
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::process_contourtree_inc::SetTriangleSuperarcId::operator()
VTKM_EXEC void operator()(const vtkm::Id node, const EndpointsArrayPortalType &endpointsPortal, const InFieldArrayPortalType &fieldPortal, const InFieldArrayPortalType &isovaluePortal, const InArrayPortalType &sortOrder, const InArrayPortalType &sortIndices, const InArrayPortalType &contourTreeSuperparentsPortal, const InArrayPortalType &contourTreeWhenTransferredPortal, const InArrayPortalType &contourTreeHyperparentsPortal, const InArrayPortalType &contourTreeHyperarcsPortal, const InArrayPortalType &contourTreeHypernodesPortal, const InArrayPortalType &contourTreeSupernodesPortal, const InArrayPortalType &meshExtremaPeaksPortal, const InArrayPortalType &meshExtremaPitsPortal, const OutArrayPortalType &superarcIdsPortal) const
Definition: SetTriangleSuperarcId.h:114
vtkm::worklet::contourtree_augmented::process_contourtree_inc::SetTriangleSuperarcId::ControlSignature
void ControlSignature(WholeArrayIn endpoints, WholeArrayIn dataField, WholeArrayIn isovalue, WholeArrayIn sortOrder, WholeArrayIn sortIndices, WholeArrayIn contourTreeSuperparents, WholeArrayIn contourTreeWhenTransferred, WholeArrayIn contourTreeHyperparents, WholeArrayIn contourTreeHyperarcs, WholeArrayIn contourTreeHypernodes, WholeArrayIn contourTreeSupernodes, WholeArrayIn meshExtremaPeaks, WholeArrayIn meshExtremaPits, WholeArrayOut superarcIds)
Definition: SetTriangleSuperarcId.h:77
vtkm::worklet::contourtree_augmented
Definition: BuildChainsWorklet.h:63
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::Id
vtkm::Int32 Id
Represents an ID (index into arrays).
Definition: Types.h:191
vtkm::worklet::contourtree_augmented::process_contourtree_inc::SetTriangleSuperarcId
Definition: SetTriangleSuperarcId.h:74
vtkm::worklet::contourtree_augmented::NoSuchElement
VTKM_EXEC_CONT bool NoSuchElement(vtkm::Id flaggedIndex)
Definition: filter/scalar_topology/worklet/contourtree_augmented/Types.h:97
Types.h
vtkm::worklet::contourtree_augmented::process_contourtree_inc::SetTriangleSuperarcId::SetTriangleSuperarcId
VTKM_EXEC_CONT SetTriangleSuperarcId(vtkm::Id NumHypernodes, vtkm::Id NumSupernodes)
Definition: SetTriangleSuperarcId.h:104
vtkm::worklet::contourtree_augmented::process_contourtree_inc::SetTriangleSuperarcId::numHypernodes
vtkm::Id numHypernodes
Definition: SetTriangleSuperarcId.h:99
vtkm::worklet::contourtree_augmented::process_contourtree_inc::SetTriangleSuperarcId::numSupernodes
vtkm::Id numSupernodes
Definition: SetTriangleSuperarcId.h:100
vtkm::Float32
float Float32
Definition: Types.h:154
vtkm::exec::arg::InputIndex
The ExecutionSignature tag to use to get the input index.
Definition: InputIndex.h:42
vtkm::worklet::contourtree_augmented::NO_SUCH_ELEMENT
constexpr vtkm::Id NO_SUCH_ELEMENT
Definition: filter/scalar_topology/worklet/contourtree_augmented/Types.h:73
vtkm::worklet::WorkletMapField
Base class for worklets that do a simple mapping of field arrays.
Definition: WorkletMapField.h:38
vtkm::worklet::contourtree_augmented::process_contourtree_inc::SetTriangleSuperarcId::ExecutionSignature
void ExecutionSignature(InputIndex, _1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14)
Definition: SetTriangleSuperarcId.h:96