VTK-m  2.0
ContourTreeMaker.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_contourtreemaker_h
54 #define vtk_m_worklet_contourtree_augmented_contourtreemaker_h
55 
56 #include <iomanip>
57 
58 // local includes
66 
67 // contourtree_maker_inc includes
88 
90 
91 
92 //VTKM includes
93 #include <vtkm/Types.h>
94 #include <vtkm/cont/Algorithm.h>
101 #include <vtkm/cont/Error.h>
102 #include <vtkm/cont/Invoker.h>
103 
104 
105 
108 
109 namespace vtkm
110 {
111 namespace worklet
112 {
113 namespace contourtree_augmented
114 {
115 
116 
118 { // class MergeTree
119 public:
121 
122  // the contour tree, join tree & split tree to use
126 
127  // vectors of up and down degree kept during the computation
130 
131  // vectors for tracking merge superarcs
134 
135  // vector for the active set of supernodes
137 
138  // constructor does the real work does the real work but mostly, it just calls the following two routines
139  ContourTreeMaker(ContourTree& theContourTree, MergeTree& joinTree, MergeTree& splitTree);
140 
141  // computes the hyperarcs in the contour tree
143 
144  // computes the regular arcs in the contour tree. Augment the contour tree with all regular vertices.
145  void ComputeRegularStructure(MeshExtrema& meshExtrema);
146 
147  // compute the parital regular arcs by augmenting the contour tree with the relevant vertices on the boundary
148  template <class Mesh, class MeshBoundaryExecObj>
150  const Mesh& mesh,
151  const MeshBoundaryExecObj& meshBoundary);
152 
153  // routine that augments the join & split tree with each other's supernodes
154  // the augmented trees will be stored in the joinSuperarcs / mergeSuperarcs arrays
155  // the sort IDs will be stored in the ContourTree's arrays, &c.
156  void AugmentMergeTrees();
157 
158  // routine to transfer leaf chains to contour tree
159  void TransferLeafChains(bool isJoin);
160 
161  // routine to collapse regular vertices
162  void CompressTrees();
163 
164  // compresses active set of supernodes
166 
167  // finds the degree of each supernode from the merge trees
168  void FindDegrees();
169 
170  // debug routine
171  void DebugPrint(const char* message, const char* fileName, long lineNum);
172 
173 }; // class ContourTreeMaker
174 
175 
176 // TODO we should add an Init function to move the heavy-weight computions out of the constructor
177 // constructor
179  MergeTree& joinTree,
180  MergeTree& splitTree)
181  : ContourTreeResult(contourTree)
182  , JoinTree(joinTree)
183  , SplitTree(splitTree)
184  , Updegree()
185  , Downdegree()
186  , AugmentedJoinSuperarcs()
187  , AugmentedSplitSuperarcs()
188  , ActiveSupernodes()
189 { // constructor
190 } //MakeContourTree()
191 
192 
194 { // ComputeHyperAndSuperStructure()
195 
196  // augment the merge trees & establish the list of supernodes
198 
199  // track how many iterations it takes
201 
202  // loop until no arcs remaining to be found
203  // tree can end with either 0 or 1 vertices unprocessed
204  // 0 means the last edge was pruned from both ends
205  // 1 means that there were two final edges meeting at a vertex
206  vtkm::Id maxNumIterations = this->ActiveSupernodes.GetNumberOfValues();
207  while (this->ActiveSupernodes.GetNumberOfValues() > 1)
208  { // loop until no active vertices remaining
209  // recompute the vertex degrees
210  FindDegrees();
211 
212  // alternate iterations between upper & lower
213  if (this->ContourTreeResult.NumIterations % 2 == 0)
214  TransferLeafChains(true);
215  else
216  TransferLeafChains(false);
217 
218  // compress join & split trees
219  CompressTrees();
220  // compress the active list of supernodes
223 
224  // Check to make sure we are not iterating too long
225  // this can happen if we are given a bad mesh that defines
226  // a forest of contour trees, rather than a single tree.
227  // Raise error if we have done more itertions than there are active nodes to remove
228  if (this->ContourTreeResult.NumIterations >= maxNumIterations)
229  {
230  throw new vtkm::cont::ErrorInternal("Bad iteration. This can happen if the input mesh "
231  "defines a contour forest rather than a simple tree.");
232  }
233  } // loop until no active vertices remaining
234 
235  // test for final edges meeting
236  if (this->ActiveSupernodes.GetNumberOfValues() == 1)
237  { // meet at a vertex
238  vtkm::Id superID = ArrayGetValue(0, this->ActiveSupernodes);
239  this->ContourTreeResult.Superarcs.WritePortal().Set(superID,
240  static_cast<vtkm::Id>(NO_SUCH_ELEMENT));
241  this->ContourTreeResult.Hyperarcs.WritePortal().Set(superID,
242  static_cast<vtkm::Id>(NO_SUCH_ELEMENT));
243  this->ContourTreeResult.Hyperparents.WritePortal().Set(superID, superID);
245  superID, this->ContourTreeResult.NumIterations | IS_HYPERNODE);
246  } // meet at a vertex
247 #ifdef DEBUG_PRINT
248  DebugPrint("Contour Tree Constructed. Now Swizzling", __FILE__, __LINE__);
249 #endif
250 
251  // next, we have to set up the hyper and super structure arrays one at a time
252  // at present, all superarcs / Hyperarcs are expressed in terms of supernode IDs
253  // but we will want to move supernodes around.
254  // the first step is therefore to find the new order of supernodes by sorting
255  // we will use the hypernodes array for this, as we will want a copy to end up there
256 
257  // create linear sequence of numbers 0, 1, .. NumSupernodes
258  vtkm::cont::ArrayHandleIndex initContourTreeHypernodes(
260  vtkm::cont::Algorithm::Copy(initContourTreeHypernodes, this->ContourTreeResult.Hypernodes);
261 
262  // now we sort hypernodes array with a comparator
265  this->ContourTreeResult.Hyperparents,
266  this->ContourTreeResult.Supernodes,
267  this->ContourTreeResult.WhenTransferred));
268 
269  // we have to permute a bunch of arrays, so let's have some temporaries to store them
270  IdArrayType permutedHyperparents;
271  PermuteArray<vtkm::Id>(
272  this->ContourTreeResult.Hyperparents, this->ContourTreeResult.Hypernodes, permutedHyperparents);
273  IdArrayType permutedSupernodes;
274  PermuteArray<vtkm::Id>(
275  this->ContourTreeResult.Supernodes, this->ContourTreeResult.Hypernodes, permutedSupernodes);
276  IdArrayType permutedSuperarcs;
277  PermuteArray<vtkm::Id>(
278  this->ContourTreeResult.Superarcs, this->ContourTreeResult.Hypernodes, permutedSuperarcs);
279 
280  // now we establish the reverse index array
281  IdArrayType superSortIndex;
282  superSortIndex.Allocate(this->ContourTreeResult.Supernodes.GetNumberOfValues());
283  // The following copy is equivalent to
284  // for (vtkm::Id supernode = 0; supernode < this->ContourTreeResult.Supernodes.size(); supernode++)
285  // superSortIndex[this->ContourTreeResult.Hypernodes[supernode]] = supernode;
286 
287  //typedef vtkm::cont::ArrayHandlePermutation<IdArrayType, vtkm::cont::ArrayHandleIndex> PermuteArrayHandleIndex;
289  this->ContourTreeResult.Hypernodes, // index array
290  superSortIndex); // value array
293  this->ContourTreeResult.Supernodes.GetNumberOfValues()), // source value array
294  permutedSuperSortIndex); // target array
295 
296  // we then copy the supernodes & hyperparents back to the main array
297  vtkm::cont::Algorithm::Copy(permutedSupernodes, this->ContourTreeResult.Supernodes);
298  vtkm::cont::Algorithm::Copy(permutedHyperparents, this->ContourTreeResult.Hyperparents);
299 
300 
301  // we need an extra permutation to get the superarcs correct
303  this->Invoke(permuteSuperarcsWorklet,
304  permutedSuperarcs, // (input)
305  superSortIndex, // (input)
306  this->ContourTreeResult.Superarcs); // (output)
307 
308  // we will permute the hyperarcs & copy them back with the new supernode target IDs
309  IdArrayType permutedHyperarcs;
310  PermuteArray<vtkm::Id>(
311  this->ContourTreeResult.Hyperarcs, this->ContourTreeResult.Hypernodes, permutedHyperarcs);
313  this->Invoke(
314  permuteHyperarcsWorklet, permutedHyperarcs, superSortIndex, this->ContourTreeResult.Hyperarcs);
315 
316  // now swizzle the WhenTransferred value
317  IdArrayType permutedWhenTransferred;
318  PermuteArray<vtkm::Id>(this->ContourTreeResult.WhenTransferred,
319  this->ContourTreeResult.Hypernodes,
320  permutedWhenTransferred);
321  vtkm::cont::Algorithm::Copy(permutedWhenTransferred, this->ContourTreeResult.WhenTransferred);
322 
323  // now we compress both the hypernodes & Hyperarcs
324  IdArrayType newHypernodePosition;
325  OneIfHypernode oneIfHypernodeFunctor;
326  auto oneIfHypernodeArrayHandle = vtkm::cont::ArrayHandleTransform<IdArrayType, OneIfHypernode>(
327  this->ContourTreeResult.WhenTransferred, oneIfHypernodeFunctor);
328  vtkm::cont::Algorithm::ScanExclusive(oneIfHypernodeArrayHandle, newHypernodePosition);
329 
330  vtkm::Id nHypernodes =
331  ArrayGetValue(newHypernodePosition.GetNumberOfValues() - 1, newHypernodePosition) +
332  oneIfHypernodeFunctor(
334  this->ContourTreeResult.WhenTransferred));
335 
336  IdArrayType newHypernodes;
337  newHypernodes.Allocate(nHypernodes);
338  IdArrayType newHyperarcs;
339  newHyperarcs.Allocate(nHypernodes);
340 
342  setNewHypernodesAndArcsWorklet;
343  this->Invoke(setNewHypernodesAndArcsWorklet,
345  this->ContourTreeResult.WhenTransferred,
346  this->ContourTreeResult.Hypernodes,
347  this->ContourTreeResult.Hyperarcs,
348  newHypernodePosition,
349  newHypernodes,
350  newHyperarcs);
351  // swap in the new computed arrays.
352  // vtkm ArrayHandles are smart so we can just swap the new data in here rather than copy
353  //vtkm::cont::Algorithm::Copy(newHypernodes, this->ContourTreeResult.Hypernodes);
354  //vtkm::cont::Algorithm::Copy(newHyperarcs, this->ContourTreeResult.Hyperarcs);
356  this->ContourTreeResult.Hypernodes = newHypernodes;
358  this->ContourTreeResult.Hyperarcs = newHyperarcs;
359 
360 
361  // now reuse the superSortIndex array for hypernode IDs
362  // The following copy is equivalent to
363  // for (vtkm::Id hypernode = 0; hypernode < this->ContourTreeResult.Hypernodes.size(); hypernode++)
364  // superSortIndex[this->ContourTreeResult.Hypernodes[hypernode]] = hypernode;
365  // source data array is a simple linear index from 0 to #Hypernodes
366  vtkm::cont::ArrayHandleIndex tempHypernodeIndexArray(
368  // target data array for the copy operation is superSortIndex permuted by this->ContourTreeResult.Hypernodes
370  this->ContourTreeResult.Hypernodes, superSortIndex);
371  vtkm::cont::Algorithm::Copy(tempHypernodeIndexArray, permutedSuperSortIndex);
372 
373  // loop through the hyperparents array, setting the first one for each
375  hypernodesSetFirstSuperchildWorklet;
376  this->Invoke(hypernodesSetFirstSuperchildWorklet,
378  superSortIndex,
379  this->ContourTreeResult.Hypernodes);
380 
381  // do a separate loop to reset the hyperparent's ID
382  // This does the following
383  // for (vtkm::Id supernode = 0; supernode < this->ContourTreeResult.Supernodes.size(); supernode++)
384  // this->ContourTreeResult.Hyperparents[supernode] = superSortIndex[MaskedIndex(this->ContourTreeResult.Hyperparents[supernode])];
386  resetHyperparentsIdWorklet;
387  this->Invoke(resetHyperparentsIdWorklet, superSortIndex, this->ContourTreeResult.Hyperparents);
388 
389  // set up the array which tracks which supernodes to deal with on which iteration:
390  // it's plus 2 because there's an "extra" iteration for the root
391  // and it's useful to store the size as one beyond that
392  // initalize with 0's to be safe
395  this->ContourTreeResult.FirstSupernodePerIteration);
396  {
398  setFirstSupernodePerIterationWorklet;
399  auto tempSupernodesIndex =
401  this->Invoke(setFirstSupernodePerIterationWorklet,
402  tempSupernodesIndex, // loopindex
403  this->ContourTreeResult.WhenTransferred, // input
404  this->ContourTreeResult.FirstSupernodePerIteration // output
405  );
406  }
407 
408  // TODO The following loop should be safe in parallel since there should never be two zeros in sequence, i.e., the next
409  // entry after a zero will always be valid, regardless of execution order. Because this is safe if could be implemented
410  // as a worklet. The number of iterations in the loop is small, so it may not be necessary for performance.
411  auto firstSupernodePerIterationPortal =
413  for (vtkm::Id iteration = 1; iteration < this->ContourTreeResult.NumIterations; ++iteration)
414  {
415  if (firstSupernodePerIterationPortal.Get(iteration) == 0)
416  {
417  firstSupernodePerIterationPortal.Set(iteration,
418  firstSupernodePerIterationPortal.Get(iteration + 1));
419  }
420  }
421  // set the sentinels at the end of the array
422  firstSupernodePerIterationPortal.Set(this->ContourTreeResult.NumIterations,
423  this->ContourTreeResult.Supernodes.GetNumberOfValues() - 1);
424  firstSupernodePerIterationPortal.Set(this->ContourTreeResult.NumIterations + 1,
425  this->ContourTreeResult.Supernodes.GetNumberOfValues());
426 
427  // now use that array to construct a similar array for hypernodes: it's plus 2 because there's an "extra" iteration for the root
428  // and it's useful to store the size as one beyond that
430  this->ContourTreeResult.NumIterations + 2);
431  {
432  // permute the ContourTree.Hyperpartens by the ContourTreeFirstSupernodePerIteration
433  auto tempContourTreeHyperparentsPermuted = vtkm::cont::make_ArrayHandlePermutation(
434  this->ContourTreeResult.FirstSupernodePerIteration, this->ContourTreeResult.Hyperparents);
435  vtkm::cont::Algorithm::CopySubRange(tempContourTreeHyperparentsPermuted,
436  0, // start index
437  this->ContourTreeResult.NumIterations, // stop index
438  this->ContourTreeResult.FirstHypernodePerIteration // target
439  );
440  }
441 
444  this->ContourTreeResult.Hypernodes.GetNumberOfValues() - 1);
447  this->ContourTreeResult.Hypernodes.GetNumberOfValues());
448 #ifdef DEBUG_PRINT
449  DebugPrint("Contour Tree Super Structure Constructed", __FILE__, __LINE__);
450 #endif
451 } // ComputeHyperAndSuperStructure()
452 
453 
454 // computes the regular arcs in the contour tree
456 { // ComputeRegularStructure()
457  // First step - use the superstructure to set the superparent for all supernodes
458  auto supernodesIndex =
460  .GetNumberOfValues()); // Counting array of length #supernodes to
461  auto permutedSuperparents = vtkm::cont::make_ArrayHandlePermutation(
463  this->ContourTreeResult.Superparents); // superparents array permmuted by the supernodes array
464  vtkm::cont::Algorithm::Copy(supernodesIndex, permutedSuperparents);
465  // The above copy is equivlant to
466  // for (indexType supernode = 0; supernode < this->ContourTreeResult.supernodes.size(); supernode++)
467  // this->ContourTreeResult.superparents[this->ContourTreeResult.Supernodes[supernode]] = supernode;
468 
469  // Second step - for all remaining (regular) nodes, locate the superarc to which they belong
472  this->ContourTreeResult.Supernodes.GetNumberOfValues());
473  this->Invoke(locateSuperarcsWorklet,
474  this->ContourTreeResult.Superparents, // (input/output)
475  this->ContourTreeResult.WhenTransferred, // (input)
476  this->ContourTreeResult.Hyperparents, // (input)
477  this->ContourTreeResult.Hyperarcs, // (input)
478  this->ContourTreeResult.Hypernodes, // (input)
479  this->ContourTreeResult.Supernodes, // (input)
480  meshExtrema.Peaks, // (input)
481  meshExtrema.Pits); // (input)
482 
483  // We have now set the superparent correctly for each node, and need to sort them to get the correct regular arcs
486  this->ContourTreeResult.Nodes);
487 
489  this->ContourTreeResult.Nodes,
490  contourtree_maker_inc_ns::ContourTreeNodeComparator(this->ContourTreeResult.Superparents,
491  this->ContourTreeResult.Superarcs));
492 
493  // now set the arcs based on the array
496  this->Invoke(setArcsWorklet,
497  this->ContourTreeResult.Nodes, // (input) arcSorter array
498  this->ContourTreeResult.Superparents, // (input)
499  this->ContourTreeResult.Superarcs, // (input)
500  this->ContourTreeResult.Supernodes, // (input)
501  this->ContourTreeResult.Arcs); // (output)
502 #ifdef DEBUG_PRINT
503  DebugPrint("Regular Structure Computed", __FILE__, __LINE__);
504 #endif
505 } // ComputeRegularStructure()
506 
508 {
509  template <typename T>
510  VTKM_EXEC_CONT bool operator()(const T& x) const
511  {
512  return (!NoSuchElement(x));
513  }
514 };
515 
517 {
518  idArray.Allocate(size);
519 
521  vtkm::cont::Algorithm::Copy(noSuchElementArray, idArray);
522 }
523 
524 template <class Mesh, class MeshBoundaryExecObj>
526  MeshExtrema& meshExtrema,
527  const Mesh& mesh,
528  const MeshBoundaryExecObj& meshBoundaryExecObj)
529 { // ComputeRegularStructure()
530  // First step - use the superstructure to set the superparent for all supernodes
531  auto supernodesIndex =
533  IdArrayType superparents;
534  InitIdArrayTypeNoSuchElement(superparents, mesh.GetNumberOfVertices());
535  // superparents array permmuted by the supernodes array
536  auto permutedSuperparents =
538  vtkm::cont::Algorithm::Copy(supernodesIndex, permutedSuperparents);
539  // The above copy is equivlant to
540  // for (indexType supernode = 0; supernode < this->ContourTreeResult.Supernodes.size(); supernode++)
541  // superparents[this->ContourTreeResult.Supernodes[supernode]] = supernode;
542 
543  // Second step - for all remaining (regular) nodes, locate the superarc to which they belong
545  locateSuperarcsOnBoundaryWorklet(this->ContourTreeResult.Hypernodes.GetNumberOfValues(),
546  this->ContourTreeResult.Supernodes.GetNumberOfValues());
547  this->Invoke(locateSuperarcsOnBoundaryWorklet,
548  superparents, // (input/output)
549  this->ContourTreeResult.WhenTransferred, // (input)
550  this->ContourTreeResult.Hyperparents, // (input)
551  this->ContourTreeResult.Hyperarcs, // (input)
552  this->ContourTreeResult.Hypernodes, // (input)
553  this->ContourTreeResult.Supernodes, // (input)
554  meshExtrema.Peaks, // (input)
555  meshExtrema.Pits, // (input)
556  mesh.SortOrder, // (input)
557  meshBoundaryExecObj); // (input)
558 
559  // We have now set the superparent correctly for each node, and need to sort them to get the correct regular arcs
560  // DAVID "ContourTreeMaker.h" line 338
561  IdArrayType node;
563  this->ContourTreeResult.Augmentnodes);
566  superparents,
569 
570  IdArrayType toCompressed;
571  InitIdArrayTypeNoSuchElement(toCompressed, superparents.GetNumberOfValues());
574  auto permutedToCompressed =
576  toCompressed); // value array
577  vtkm::cont::Algorithm::Copy(node, // source value array
578  permutedToCompressed); // target array
579 
580  // Make superparents correspond to nodes
581  IdArrayType tmpsuperparents;
583  superparents, superparents, tmpsuperparents, ContourTreeNoSuchElementSuperParents());
584  vtkm::cont::Algorithm::Copy(tmpsuperparents, superparents);
585 
586  // Create array for sorting
587  IdArrayType augmentnodes_sorted;
590  augmentnodes_sorted);
591 
592  // use a comparator to do the sort
593  vtkm::cont::Algorithm::Sort(augmentnodes_sorted,
595  superparents, this->ContourTreeResult.Superarcs));
596  // now set the arcs based on the array
598  this->ContourTreeResult.Augmentnodes.GetNumberOfValues());
601  this->Invoke(setAugmentArcsWorklet,
602  augmentnodes_sorted, // (input) arcSorter array
603  superparents, // (input)
604  this->ContourTreeResult.Superarcs, // (input)
605  this->ContourTreeResult.Supernodes, // (input)
606  toCompressed, // (input)
607  this->ContourTreeResult.Augmentarcs); // (output)
608 #ifdef DEBUG_PRINT
609  DebugPrint("Regular Boundary Structure Computed", __FILE__, __LINE__);
610 #endif
611 } // ComputeRegularStructure()
612 
613 
614 // routine that augments the join & split tree with each other's supernodes
615 // the augmented trees will be stored in the joinSuperarcs / mergeSuperarcs arrays
616 // the sort IDs will be stored in the ContourTree's arrays, &c.
618 { // ContourTreeMaker::AugmentMergeTrees()
619  // in this version, we know that only connectivity-critical points are used
620  // so we want to combine the lists of supernodes.
621  // but they are not in sorted order, so some juggling is required.
622 
623  // NOTE: The following code block is a direct port from the original PPP2 code using std::set_union
624  // In the main code below we replaced steps 1-4 with a combination of VTKM copy, sort, and union operators instead
625  /*
626  // 1. Allocate an array that is guaranteed to be big enough
627  // - the sum of the sizes of the trees or the total size of the data
628  vtkm::Id nJoinSupernodes = this->JoinTree.Supernodes.GetNumberOfValues();
629  vtkm::Id nSplitSupernodes = this->SplitTree.Supernodes.GetNumberOfValues();
630  vtkm::Id nSupernodes = nJoinSupernodes + nSplitSupernodes;
631  if (nSupernodes > this->JoinTree.Arcs.GetNumberOfValues())
632  nSupernodes = this->JoinTree.Arcs.GetNumberOfValues();
633  this->ContourTreeResult.Supernodes.Allocate(nSupernodes);
634 
635  // 2. Make copies of the lists of join & split supernodes & sort them
636  IdArrayType joinSort;
637  joinSort.Allocate(nJoinSupernodes);
638  vtkm::cont::Algorithm::Copy(this->JoinTree.Supernodes, joinSort);
639  vtkm::cont::Algorithm::Sort(joinSort);
640  IdArrayType splitSort;
641  splitSort.Allocate(nSplitSupernodes);
642  vtkm::cont::Algorithm::Copy(this->SplitTree.Supernodes, splitSort);
643  vtkm::cont::Algorithm::Sort(splitSort);
644 
645  // 3. Use set_union to combine the lists
646  auto contTreeSuperNodesBegin = vtkm::cont::ArrayPortalToIteratorBegin(this->ContourTreeResult.Supernodes.WritePortal());
647  auto tail = std::set_union(vtkm::cont::ArrayPortalToIteratorBegin(joinSort.WritePortal()),
648  vtkm::cont::ArrayPortalToIteratorEnd(joinSort.WritePortal()),
649  vtkm::cont::ArrayPortalToIteratorBegin(splitSort.WritePortal()),
650  vtkm::cont::ArrayPortalToIteratorEnd(splitSort.WritePortal()),
651  contTreeSuperNodesBegin);
652  // compute the true number of supernodes
653  nSupernodes = tail - contTreeSuperNodesBegin;
654  // and release the memory
655  joinSort.ReleaseResources();
656  splitSort.ReleaseResources();
657 
658  // 4. Resize the supernode array accordingly
659  this->ContourTreeResult.Supernodes.Allocate(nSupernodes, vtkm::CopyFlag::On);
660  */
661 
662  // 1. Allocate an array that is guaranteed to be big enough
663  // - the sum of the sizes of the trees or the total size of the data
664  vtkm::Id nJoinSupernodes = this->JoinTree.Supernodes.GetNumberOfValues();
665  vtkm::Id nSplitSupernodes = this->SplitTree.Supernodes.GetNumberOfValues();
666  vtkm::Id nSupernodes = nJoinSupernodes + nSplitSupernodes;
667 
668  // TODO Check whether this replacement for Step 2 to 4 is a problem in terms of performance
669  // Step 2 - 4 in original PPP2. Create a sorted list of all unique supernodes from the Join and Split tree.
670  this->ContourTreeResult.Supernodes.Allocate(nSupernodes);
672  this->JoinTree.Supernodes, 0, nJoinSupernodes, this->ContourTreeResult.Supernodes, 0);
674  0,
675  nSplitSupernodes,
676  this->ContourTreeResult.Supernodes,
677  nJoinSupernodes);
678 
679  // Need to sort before Unique because VTKM only guarantees to find neighboring duplicates
680  // TODO/FIXME: It would be more efficient to do a merge of two sorted lists here, but that operation
681  // is currently missing in vtk-m
685  nSupernodes = this->ContourTreeResult.Supernodes.GetNumberOfValues();
686 
687  // 5. Create lookup arrays for the join & split supernodes' new IDs
688  IdArrayType newJoinID;
689  newJoinID.Allocate(nJoinSupernodes);
690  IdArrayType newSplitID;
691  newSplitID.Allocate(nSplitSupernodes);
692 
693  // 6. Each supernode is listed by it's regular ID, so we can use the regular arrays
694  // to look up the corresponding supernode IDs in the merge trees, and to transfer
695  // the superparent for each
696  IdArrayType joinSuperparents;
697  joinSuperparents.Allocate(nSupernodes);
698  IdArrayType splitSuperparents;
699  splitSuperparents.Allocate(nSupernodes);
700 
702  initNewJoinSplitIDAndSuperparentsWorklet;
703  this->Invoke(initNewJoinSplitIDAndSuperparentsWorklet,
704  this->ContourTreeResult.Supernodes, //input
705  this->JoinTree.Superparents, //input
706  this->SplitTree.Superparents, //input
707  this->JoinTree.Supernodes, //input
708  this->SplitTree.Supernodes, //input
709  joinSuperparents, //output
710  splitSuperparents, //output
711  newJoinID, //output
712  newSplitID); //output
713 
714  // 7. use the active supernodes array for sorting
715  // create linear sequence of numbers 0, 1, .. nSupernodes
716  vtkm::cont::ArrayHandleIndex initActiveSupernodes(nSupernodes);
717  vtkm::cont::Algorithm::Copy(initActiveSupernodes, this->ActiveSupernodes);
718 
719  // 8. Once we have got the superparent for each, we can sort by superparents and set
720  // the augmented superarcs. We start with the join superarcs
722  this->ActiveSupernodes,
724 
725  // 9. Set the augmented join superarcs
726  this->AugmentedJoinSuperarcs.Allocate(nSupernodes);
728  this->Invoke(setAugmentedJoinArcsWorklet,
729  this->ActiveSupernodes, // (input domain)
730  joinSuperparents, // (input)
731  this->JoinTree.Superarcs, // (input)
732  newJoinID, // (input)
733  this->AugmentedJoinSuperarcs); // (output)
734 
735  // 10. Now we repeat the process for the split superarcs
736  vtkm::cont::Algorithm::Copy(initActiveSupernodes, this->ActiveSupernodes);
737  // now sort by the split superparent
739  this->ActiveSupernodes,
741 
742  // 11. Set the augmented split superarcs
743  this->AugmentedSplitSuperarcs.Allocate(nSupernodes);
745  this->Invoke(setAugmentedSplitArcsWorklet,
746  this->ActiveSupernodes, // (input domain)
747  splitSuperparents, // (input)
748  this->SplitTree.Superarcs, // (input)
749  newSplitID, // (input)
750  this->AugmentedSplitSuperarcs); // (output)
751 
752  // 12. Lastly, we can initialise all of the remaining arrays
754  nSupernodes);
755  vtkm::cont::Algorithm::Copy(noSuchElementArray, this->ContourTreeResult.Superarcs);
757  vtkm::cont::Algorithm::Copy(noSuchElementArray, this->ContourTreeResult.Hypernodes);
758  vtkm::cont::Algorithm::Copy(noSuchElementArray, this->ContourTreeResult.Hyperarcs);
760 
761  // TODO We should only need to allocate the this->Updegree/Downdegree arrays. We initialize them with 0 here to ensure consistency of debug output
762  //this->Updegree.Allocate(nSupernodes);
763  //this->Downdegree.Allocate(nSupernodes);
765  this->Updegree);
767  this->Downdegree);
768 #ifdef DEBUG_PRINT
769  DebugPrint("Supernodes Found", __FILE__, __LINE__);
770 #endif
771 } // ContourTreeMaker::AugmentMergeTrees()
772 
773 
774 
775 namespace details
776 {
777 
779 {
781  const bool isJoin,
782  const IdArrayType& outdegree,
783  const IdArrayType& indegree,
784  const IdArrayType& outbound,
785  const IdArrayType& inbound,
786  const IdArrayType& inwards)
787  : NumIterations(nIterations)
788  , IsJoin(isJoin)
789  , Outdegree(outdegree)
790  , Indegree(indegree)
791  , Outbound(outbound)
792  , Inbound(inbound)
793  , Inwards(inwards)
794  {
795  }
796 
797  template <typename DeviceAdapter, typename... Args>
798  inline bool operator()(DeviceAdapter device, Args&&... args) const
799  {
800  vtkm::cont::Token token;
802  this->NumIterations, // (input)
803  this->IsJoin, // (input)
804  this->Outdegree, // (input)
805  this->Indegree, // (input)
806  this->Outbound, // (input)
807  this->Inbound, // (input)
808  this->Inwards, // (input)
809  device,
810  token);
811  vtkm::worklet::DispatcherMapField<decltype(worklet)> dispatcher(worklet);
812  dispatcher.SetDevice(device);
813  dispatcher.Invoke(std::forward<Args>(args)...);
814  return true;
815  }
816 
817 
819  const bool IsJoin;
825 };
826 }
827 
828 // routine to transfer leaf chains to contour tree
829 inline void ContourTreeMaker::TransferLeafChains(bool isJoin)
830 { // ContourTreeMaker::TransferLeafChains()
831  // we need to compute the chains in both directions, so we have two vectors:
832  // TODO below we initialize the outbound and inbound arrays with 0 to ensure consistency of debug output. Check if this is needed.
833  IdArrayType outbound;
836  outbound);
837  //outbound.Allocate(this->ContourTreeResult.Supernodes.GetNumberOfValues());
838  IdArrayType inbound;
839  //inbound.Allocate(this->ContourTreeResult.Supernodes.GetNumberOfValues());
842  inbound);
843 
844 
845  // a reference for the inwards array we use to initialise
846  IdArrayType& inwards = isJoin ? this->AugmentedJoinSuperarcs : this->AugmentedSplitSuperarcs;
847  // and references for the degrees
848  IdArrayType& indegree = isJoin ? this->Downdegree : this->Updegree;
849  IdArrayType& outdegree = isJoin ? this->Updegree : this->Downdegree;
850 
851  // loop to each active node to copy join/split to outbound and inbound arrays
853  this->Invoke(initInAndOutboundWorklet,
854  this->ActiveSupernodes, // (input)
855  inwards, // (input)
856  outdegree, // (input)
857  indegree, // (input)
858  outbound, // (output)
859  inbound); // (output)
860 #ifdef DEBUG_PRINT
861  DebugPrint("Init in and outbound -- Step 1", __FILE__, __LINE__);
862 #endif
863  // Compute the number of log steps required in this pass
864  vtkm::Id numLogSteps = 1;
865  for (vtkm::Id shifter = this->ActiveSupernodes.GetNumberOfValues(); shifter != 0; shifter >>= 1)
866  {
867  numLogSteps++;
868  }
869 
870 
871  // loop to find the now-regular vertices and collapse past them without altering
872  // the existing join & split arcs
873  for (vtkm::Id iteration = 0; iteration < numLogSteps; iteration++)
874  { // per iteration
875  // loop through the vertices, updating outbound
877  this->Invoke(collapsePastRegularWorklet,
878  this->ActiveSupernodes, // (input)
879  outbound, // (input/output)
880  inbound); // (input/output)
881 
882  } // per iteration
883 #ifdef DEBUG_PRINT
884  DebugPrint("Init in and outbound -- Step 2", __FILE__, __LINE__);
885 #endif
886  // at this point, the outbound vector chains everything outwards to the leaf
887  // any vertices on the last outbound leaf superarc point to the leaf
888  // and the leaf itself will point to its saddle, identifying the hyperarc
889 
890  // what we want to do is:
891  // a. for leaves (tested by degree),
892  // i. we use inbound as the hyperarc
893  // ii. we use inwards as the superarc
894  // iii.we use self as the hyperparent
895  // b. for regular vertices pointing to a leaf (test by outbound's degree),
896  // i. we use outbound as the hyperparent
897  // ii. we use inwards as the superarc
898  // c. for all other vertics
899  // ignore
900 
901 
902  // loop through the active vertices
903  // Note: there are better and safer ways to pass these arrays (e.g. in/outdegree) to
904  // a worklet. You could pass them as WholeArrayIn ControlSignature arguments. Or
905  // you could build a subclass of vtkm::cont::ExecutionObjectBase and pass that in
906  // as an ExecObject.
908  isJoin, // (input)
909  outdegree, // (input)
910  indegree, // (input)
911  outbound, // (input)
912  inbound, // (input)
913  inwards); // (input)
915  this->ActiveSupernodes, // (input)
916  this->ContourTreeResult.Hyperparents, // (output)
917  this->ContourTreeResult.Hyperarcs, // (output)
918  this->ContourTreeResult.Superarcs, // (output)
919  this->ContourTreeResult.WhenTransferred); // (output)
920 #ifdef DEBUG_PRINT
921  DebugPrint(isJoin ? "Upper Regular Chains Transferred" : "Lower Regular Chains Transferred",
922  __FILE__,
923  __LINE__);
924 #endif
925 } // ContourTreeMaker::TransferLeafChains()
926 
927 
928 // routine to compress trees by removing regular vertices as well as Hypernodes
930 { // ContourTreeMaker::CompressTrees()
931 
932  // Compute the number of log steps required in this pass
933  vtkm::Id numLogSteps = 1;
934  for (vtkm::Id shifter = this->ActiveSupernodes.GetNumberOfValues(); shifter != 0; shifter >>= 1)
935  {
936  numLogSteps++;
937  }
938 
939  // loop to update the merge trees
940  for (vtkm::Id logStep = 0; logStep < numLogSteps; logStep++)
941  { // iteration log times
942  contourtree_maker_inc_ns::CompressTrees_Step compressTreesStepWorklet;
943  this->Invoke(compressTreesStepWorklet,
944  this->ActiveSupernodes, // (input)
945  this->ContourTreeResult.Superarcs, // (input)
946  this->AugmentedJoinSuperarcs, // (input/output)
947  this->AugmentedSplitSuperarcs // (input/output)
948  );
949 
950  } // iteration log times
951 #ifdef DEBUG_PRINT
952  DebugPrint("Trees Compressed", __FILE__, __LINE__);
953 #endif
954 } // ContourTreeMaker::CompressTrees()
955 
956 
957 // compresses trees to remove transferred vertices
959 { // ContourTreeMaker::CompressActiveSupernodes()
960  // copy only if this->ContourTreeResult.WhenTransferred has been set
961  IdArrayType compressedActiveSupernodes;
962 
963  // Transform the WhenTransferred array to return 1 if the index was not transferred and 0 otherwise
964  auto wasNotTransferred =
967  // Permute the wasNotTransferred array handle so that the lookup is based on the value of the indices in the active supernodes array
968  auto notTransferredActiveSupernodes =
970  // Keep only the indices of the active supernodes that have not been transferred yet
972  this->ActiveSupernodes, notTransferredActiveSupernodes, compressedActiveSupernodes);
973  // Copy the data into the active supernodes
976  compressedActiveSupernodes; // vtkm ArrayHandles are smart, so we can just swap it in without having to copy
977 #ifdef DEBUG_PRINT
978  DebugPrint("Active Supernodes Compressed", __FILE__, __LINE__);
979 #endif
980 } // ContourTreeMaker::CompressActiveSupernodes()
981 
982 
984 { // ContourTreeMaker::FindDegrees()
986 
987  // retrieve the size to register for speed
988  vtkm::Id nActiveSupernodes = this->ActiveSupernodes.GetNumberOfValues();
989 
990  // reset the Updegree & Downdegree
992  this->Invoke(
993  resetUpAndDowndegreeWorklet, this->ActiveSupernodes, this->Updegree, this->Downdegree);
994 #ifdef DEBUG_PRINT
995  DebugPrint("Degrees Set to 0", __FILE__, __LINE__);
996 #endif
997  // now we loop through every join & split arc, updating degrees
998  // to minimise memory footprint, we will do two separate loops
999  // but we could combine the two into paired loops
1000  // first we establish an array of destination vertices (since outdegree is always 1)
1001  IdArrayType inNeighbour;
1002  //inNeighbour.Allocate(nActiveSupernodes);
1003  //PermuteIndexArray permuteInNeighbour(this->ActiveSupernodes, inNeighbour);
1004  PermuteIndexArray permuteAugmentedJoinSuperarcs(this->ActiveSupernodes,
1005  this->AugmentedJoinSuperarcs);
1006  vtkm::cont::Algorithm::Copy(permuteAugmentedJoinSuperarcs, inNeighbour);
1007  // now sort to group copies together
1008  vtkm::cont::Algorithm::Sort(inNeighbour,
1010 
1011  // there's probably a smarter scatter-gather solution to this, but this should work
1012  // find the RHE of each segment
1013  contourtree_maker_inc_ns::FindDegrees_FindRHE joinFindRHEWorklet(nActiveSupernodes);
1014  this->Invoke(joinFindRHEWorklet, inNeighbour, this->Updegree);
1015 
1016  // now subtract the LHE to get the size
1018  this->Invoke(joinSubractLHEWorklet, inNeighbour, this->Updegree);
1019 
1020  // now repeat the same process for the split neighbours
1021  PermuteIndexArray permuteAugmentedSplitSuperarcs(this->ActiveSupernodes,
1022  this->AugmentedSplitSuperarcs);
1023  vtkm::cont::Algorithm::Copy(permuteAugmentedSplitSuperarcs, inNeighbour);
1024  // now sort to group copies together
1025  vtkm::cont::Algorithm::Sort(inNeighbour,
1027 
1028  // there's probably a smarter scatter-gather solution to this, but this should work
1029  // find the RHE of each segment
1030  contourtree_maker_inc_ns::FindDegrees_FindRHE splitFindRHEWorklet(nActiveSupernodes);
1031  this->Invoke(splitFindRHEWorklet, inNeighbour, this->Downdegree);
1032 
1033  // now subtract the LHE to get the size
1035  this->Invoke(splitSubractLHEWorklet, inNeighbour, this->Downdegree);
1036 #ifdef DEBUG_PRINT
1037  DebugPrint("Degrees Computed", __FILE__, __LINE__);
1038 #endif
1039 } // ContourTreeMaker::FindDegrees()
1040 
1041 
1042 
1043 inline void ContourTreeMaker::DebugPrint(const char* message, const char* fileName, long lineNum)
1044 { // ContourTreeMaker::DebugPrint()
1045  std::string childString = std::string(message);
1046  std::cout
1047  << "==========================================================================================="
1048  "==============================================="
1049  << "=============================================="
1050  << //============================================================================================" <<
1051  "=============================================================================================="
1052  "============================================"
1053  << std::endl;
1054  std::cout
1055  << "==========================================================================================="
1056  "==============================================="
1057  << "=============================================="
1058  << //============================================================================================" <<
1059  "=============================================================================================="
1060  "============================================"
1061  << std::endl;
1062  std::cout
1063  << "==========================================================================================="
1064  "==============================================="
1065  << "=============================================="
1066  << //============================================================================================" <<
1067  "=============================================================================================="
1068  "============================================"
1069  << std::endl;
1070  std::cout << std::setw(30) << std::left << fileName << ":" << std::right << std::setw(4)
1071  << lineNum << std::endl;
1072  std::cout << std::left << std::string(message) << std::endl;
1073 
1074  // this->JoinTree.DebugPrint((childString + std::string(": Join Tree")).c_str(), fileName, lineNum);
1075  // this->SplitTree.DebugPrint((childString + std::string(": Split Tree")).c_str(), fileName, lineNum);
1076  std::cout << this->ContourTreeResult.DebugPrint(
1077  (childString + std::string(": Contour Tree")).c_str(), fileName, lineNum);
1078  std::cout
1079  << "==========================================================================================="
1080  "==============================================="
1081  << "=============================================="
1082  << //============================================================================================" <<
1083  "=============================================================================================="
1084  "============================================"
1085  << std::endl;
1086 
1087  // std::cout << "------------------------------------------------------" << std::endl;
1088  std::cout << std::setw(30) << std::left << fileName << ":" << std::right << std::setw(4)
1089  << lineNum << std::endl;
1090  std::cout << std::left << std::string(message) << std::endl;
1091  std::cout << "Contour Tree Maker Contains: " << std::endl;
1092  std::cout << "------------------------------------------------------" << std::endl;
1093  std::cout << "NumIterations: " << this->ContourTreeResult.NumIterations << std::endl;
1094 
1096  PrintIndices("Updegree", this->Updegree);
1097  PrintIndices("Downdegree", this->Downdegree);
1098  PrintIndices("Aug Join SArcs", this->AugmentedJoinSuperarcs);
1099  PrintIndices("Aug Split SArcs", this->AugmentedSplitSuperarcs);
1100 
1102  PrintIndices("Active SNodes", this->ActiveSupernodes);
1103 } // ContourTreeMaker::DebugPrint()
1104 
1105 
1106 } // namespace contourtree_augmented
1107 } // worklet
1108 } // vtkm
1109 
1110 #endif
vtkm::worklet::contourtree_augmented::OneIfHypernode
Definition: ArrayTransforms.h:144
vtkm::worklet::contourtree_augmented::ContourTreeMaker::FindDegrees
void FindDegrees()
Definition: ContourTreeMaker.h:983
FindDegrees_FindRHE.h
vtkm::cont::ArrayHandle::GetNumberOfValues
VTKM_CONT vtkm::Id GetNumberOfValues() const
Returns the number of entries in the array.
Definition: ArrayHandle.h:448
vtkm::worklet::contourtree_augmented::ContourTree::Hyperparents
IdArrayType Hyperparents
Definition: augmented/ContourTree.h:136
vtkm::worklet::contourtree_augmented::details::LeafChainsToContourTree::operator()
bool operator()(DeviceAdapter device, Args &&... args) const
Definition: ContourTreeMaker.h:798
vtkm::worklet::contourtree_augmented::ContourTreeMaker::Downdegree
IdArrayType Downdegree
Definition: ContourTreeMaker.h:129
vtkm::cont::ArrayHandle< vtkm::Id >
vtkm::worklet::contourtree_augmented::ContourTree::DebugPrint
std::string DebugPrint(const char *message, const char *fileName, long lineNum) const
Definition: augmented/ContourTree.h:230
vtkm::worklet::contourtree_augmented::ContourTree::Hyperarcs
IdArrayType Hyperarcs
Definition: augmented/ContourTree.h:149
vtkm
Groups connected points that have the same field value.
Definition: Atomic.h:19
vtkm::worklet::contourtree_augmented::ContourTree::Supernodes
IdArrayType Supernodes
Definition: augmented/ContourTree.h:125
ArrayHandleCast.h
Types.h
vtkm::worklet::contourtree_augmented::details::LeafChainsToContourTree::LeafChainsToContourTree
LeafChainsToContourTree(const vtkm::Id nIterations, const bool isJoin, const IdArrayType &outdegree, const IdArrayType &indegree, const IdArrayType &outbound, const IdArrayType &inbound, const IdArrayType &inwards)
Definition: ContourTreeMaker.h:780
vtkm::worklet::contourtree_augmented::ContourTree
Definition: augmented/ContourTree.h:106
VTKM_EXEC_CONT
#define VTKM_EXEC_CONT
Definition: ExportMacros.h:52
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::worklet::contourtree_augmented::contourtree_maker_inc::CompressTrees_Step
Definition: CompressTrees_Step.h:69
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ComputeRegularStructure_LocateSuperarcs
Definition: ComputeRegularStructure_LocateSuperarcs.h:70
AugmentMergeTrees_SetAugmentedMergeArcs.h
vtkm::worklet::contourtree_augmented::details::LeafChainsToContourTree::Indegree
const IdArrayType & Indegree
Definition: ContourTreeMaker.h:821
ComputeRegularStructure_SetArcs.h
vtkm::worklet::contourtree_augmented::ContourTreeMaker::TransferLeafChains
void TransferLeafChains(bool isJoin)
Definition: ContourTreeMaker.h:829
vtkm::worklet::contourtree_augmented::ContourTree::Superparents
IdArrayType Superparents
Definition: augmented/ContourTree.h:118
vtkm::worklet::contourtree_augmented::ContourTree::Hypernodes
IdArrayType Hypernodes
Definition: augmented/ContourTree.h:144
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::FindDegrees_FindRHE
Definition: FindDegrees_FindRHE.h:70
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::TransferLeafChains_InitInAndOutbound
Definition: TransferLeafChains_InitInAndOutbound.h:69
ArrayHandleTransform.h
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ContourTreeSuperNodeComparator
Definition: ContourTreeSuperNodeComparator.h:126
vtkm::worklet::contourtree_augmented::MeshExtrema::Pits
IdArrayType Pits
Definition: MeshExtrema.h:85
vtkm::worklet::contourtree_augmented::ContourTree::Nodes
IdArrayType Nodes
Definition: augmented/ContourTree.h:112
MergeTree.h
vtkm::cont::Algorithm::CopySubRange
static VTKM_CONT bool CopySubRange(vtkm::cont::DeviceAdapterId devId, const vtkm::cont::ArrayHandle< T, CIn > &input, vtkm::Id inputStartIndex, vtkm::Id numberOfElementsToCopy, vtkm::cont::ArrayHandle< U, COut > &output, vtkm::Id outputIndex=0)
Definition: Algorithm.h:472
AugmentMergeTrees_InitNewJoinSplitIDAndSuperparents.h
vtkm::worklet::contourtree_augmented::AssertArrayHandleNoFlagsSet
VTKM_CONT void AssertArrayHandleNoFlagsSet(const vtkm::cont::ArrayHandle< vtkm::Id, S > &ah)
Definition: filter/scalar_topology/worklet/contourtree_augmented/Types.h:149
vtkm::cont::Algorithm::Sort
static VTKM_CONT void Sort(vtkm::cont::DeviceAdapterId devId, vtkm::cont::ArrayHandle< T, Storage > &values)
Definition: Algorithm.h:965
vtkm::worklet::contourtree_augmented::MeshExtrema
Definition: MeshExtrema.h:79
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ComputeRegularStructure_SetArcs
Definition: ComputeRegularStructure_SetArcs.h:69
ArrayHandleConstant.h
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ComputeHyperAndSuperStructure_SetFirstSupernodePerIterationWorklet
Definition: ComputeHyperAndSuperStructure_SetFirstSupernodePerIterationWorklet.h:69
vtkm::cont::ArrayGetValue
VTKM_CONT T ArrayGetValue(vtkm::Id id, const vtkm::cont::ArrayHandle< T, S > &data)
Obtain a small set of values from an ArrayHandle with minimal device transfers.
Definition: ArrayGetValues.h:264
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
PrintVectors.h
Invoker.h
ArrayTransforms.h
vtkm::worklet::contourtree_augmented::MergeTree::Supernodes
IdArrayType Supernodes
Definition: augmented/MergeTree.h:98
vtkm::worklet::contourtree_augmented::details::LeafChainsToContourTree::IsJoin
const bool IsJoin
Definition: ContourTreeMaker.h:819
vtkm::worklet::contourtree_augmented::ContourTreeMaker::ContourTreeMaker
ContourTreeMaker(ContourTree &theContourTree, MergeTree &joinTree, MergeTree &splitTree)
Definition: ContourTreeMaker.h:178
TransferLeafChains_TransferToContourTree.h
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ContourTreeNodeComparator
Definition: ContourTreeNodeComparator.h:114
vtkm::worklet::contourtree_augmented::ContourTreeMaker::ActiveSupernodes
IdArrayType ActiveSupernodes
Definition: ContourTreeMaker.h:136
vtkm::worklet::contourtree_augmented::ContourTreeMaker::ComputeHyperAndSuperStructure
void ComputeHyperAndSuperStructure()
Definition: ContourTreeMaker.h:193
TransferLeafChains_InitInAndOutbound.h
vtkm::Id
vtkm::Int32 Id
Represents an ID (index into arrays).
Definition: Types.h:191
vtkm::worklet::contourtree_augmented::active_graph_inc
Definition: BuildChainsWorklet.h:65
vtkm::worklet::contourtree_augmented::ContourTree::Augmentarcs
IdArrayType Augmentarcs
Definition: augmented/ContourTree.h:133
vtkm::worklet::contourtree_augmented::details::LeafChainsToContourTree::NumIterations
const vtkm::Id NumIterations
Definition: ContourTreeMaker.h:818
vtkm::worklet::contourtree_augmented::ContourTreeMaker::ComputeBoundaryRegularStructure
void ComputeBoundaryRegularStructure(MeshExtrema &meshExtrema, const Mesh &mesh, const MeshBoundaryExecObj &meshBoundary)
Definition: ContourTreeMaker.h:525
vtkm::cont::Token
A token to hold the scope of an ArrayHandle or other object.
Definition: Token.h:35
vtkm::worklet::contourtree_augmented::ContourTree::Superarcs
IdArrayType Superarcs
Definition: augmented/ContourTree.h:129
vtkm::worklet::contourtree_augmented::MergeTree::IsJoinTree
bool IsJoinTree
Definition: augmented/MergeTree.h:81
vtkm::worklet::contourtree_augmented::ContourTree::NumIterations
vtkm::Id NumIterations
Definition: augmented/ContourTree.h:153
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::FindDegrees_ResetUpAndDowndegree
Definition: FindDegrees_ResetUpAndDowndegree.h:71
SuperArcNodeComparator.h
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::WasNotTransferred
Definition: WasNotTransferred.h:70
vtkm::worklet::contourtree_augmented::NoSuchElement
VTKM_EXEC_CONT bool NoSuchElement(vtkm::Id flaggedIndex)
Definition: filter/scalar_topology/worklet/contourtree_augmented/Types.h:97
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::FindDegrees_SubtractLHE
Definition: FindDegrees_SubtractLHE.h:70
vtkm::worklet::contourtree_augmented::ContourTreeMaker::AugmentedSplitSuperarcs
IdArrayType AugmentedSplitSuperarcs
Definition: ContourTreeMaker.h:133
ComputeHyperAndSuperStructure_PermuteArcs.h
vtkm::cont::ErrorInternal
This class is thrown when VTKm detects an internal state that should never be reached.
Definition: ErrorInternal.h:26
ComputeHyperAndSuperStructure_HypernodesSetFirstSuperchild.h
vtkm::cont::Algorithm::Unique
static VTKM_CONT void Unique(vtkm::cont::DeviceAdapterId devId, vtkm::cont::ArrayHandle< T, Storage > &values)
Definition: Algorithm.h:1063
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ComputeRegularStructure_SetAugmentArcs
Definition: ComputeRegularStructure_SetArcs.h:180
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::TransferLeafChains_TransferToContourTree
Definition: TransferLeafChains_TransferToContourTree.h:78
vtkm::worklet::contourtree_augmented::ContourTreeMaker::DebugPrint
void DebugPrint(const char *message, const char *fileName, long lineNum)
Definition: ContourTreeMaker.h:1043
vtkm::worklet::DispatcherMapField
Dispatcher for worklets that inherit from WorkletMapField.
Definition: DispatcherMapField.h:25
vtkm::worklet::contourtree_augmented::active_graph_inc::SuperArcNodeComparator
Definition: SuperArcNodeComparator.h:119
ArrayHandlePermutation.h
Algorithm.h
ArrayHandleIndex.h
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::MoveNoSuchElementToBackComparator
Definition: MoveNoSuchElementToBackComparator.h:68
vtkm::worklet::contourtree_augmented::ContourTreeMaker::ComputeRegularStructure
void ComputeRegularStructure(MeshExtrema &meshExtrema)
Definition: ContourTreeMaker.h:455
vtkm::worklet::contourtree_augmented::ContourTreeMaker
Definition: ContourTreeMaker.h:117
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
ContourTreeSuperNodeComparator.h
vtkm::cont::ArrayHandlePermutation
Implicitly permutes the values in an array.
Definition: ArrayHandlePermutation.h:227
Error.h
vtkm::worklet::contourtree_augmented::ContourTreeMaker::ContourTreeResult
ContourTree & ContourTreeResult
Definition: ContourTreeMaker.h:123
DataSetMesh.h
vtkm::cont::Invoker
Allows launching any worklet without a dispatcher.
Definition: Invoker.h:41
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ComputeHyperAndSuperStructure_SetNewHypernodesAndArcs
Definition: ComputeHyperAndSuperStructure_SetNewHypernodesAndArcs.h:69
vtkm::worklet::contourtree_augmented::contourtree_maker_inc
Definition: AugmentMergeTrees_InitNewJoinSplitIDAndSuperparents.h:66
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::worklet::contourtree_augmented::ContourTreeMaker::CompressTrees
void CompressTrees()
Definition: ContourTreeMaker.h:929
Types.h
vtkm::worklet::contourtree_augmented::details::LeafChainsToContourTree
Definition: ContourTreeMaker.h:778
vtkm::cont::ArrayHandle::WritePortal
VTKM_CONT WritePortalType WritePortal() const
Get an array portal that can be used in the control environment.
Definition: ArrayHandle.h:435
vtkm::cont::ArrayHandleTransform
Implicitly transform values of one array to another with a functor.
Definition: ArrayHandleTransform.h:437
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ComputeHyperAndSuperStructure_ResetHyperparentsId
Definition: ComputeHyperAndSuperStructure_ResetHyperparentsId.h:69
vtkm::worklet::contourtree_augmented::ContourTreeMaker::Invoke
vtkm::cont::Invoker Invoke
Definition: ContourTreeMaker.h:120
vtkm::cont::ArrayHandleConstant
An array handle with a constant value.
Definition: ArrayHandleConstant.h:63
vtkm::worklet::contourtree_augmented::ContourTreeNoSuchElementSuperParents
Definition: ContourTreeMaker.h:507
MeshExtrema.h
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::AugmentMergeTrees_InitNewJoinSplitIDAndSuperparents
Definition: AugmentMergeTrees_InitNewJoinSplitIDAndSuperparents.h:70
vtkm::worklet::contourtree_augmented::MergeTree::Superarcs
IdArrayType Superarcs
Definition: augmented/MergeTree.h:102
vtkm::worklet::contourtree_augmented::ContourTreeMaker::SplitTree
MergeTree & SplitTree
Definition: ContourTreeMaker.h:125
ComputeRegularStructure_LocateSuperarcs.h
vtkm::cont::make_ArrayHandlePermutation
VTKM_CONT vtkm::cont::ArrayHandlePermutation< IndexArrayHandleType, ValueArrayHandleType > make_ArrayHandlePermutation(IndexArrayHandleType indexArray, ValueArrayHandleType valueArray)
make_ArrayHandleTransform is convenience function to generate an ArrayHandleTransform.
Definition: ArrayHandlePermutation.h:279
ComputeHyperAndSuperStructure_SetNewHypernodesAndArcs.h
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::TransferLeafChains_CollapsePastRegular
Definition: TransferLeafChains_CollapsePastRegular.h:71
vtkm::worklet::contourtree_augmented::MergeTree
Definition: augmented/MergeTree.h:77
FindDegrees_ResetUpAndDowndegree.h
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ComputeRegularStructure_LocateSuperarcsOnBoundary
Definition: ComputeRegularStructure_LocateSuperarcs.h:405
vtkm::worklet::contourtree_augmented::ContourTree::Arcs
IdArrayType Arcs
Definition: augmented/ContourTree.h:115
vtkm::worklet::contourtree_augmented::ContourTree::FirstHypernodePerIteration
IdArrayType FirstHypernodePerIteration
Definition: augmented/ContourTree.h:157
vtkm::worklet::contourtree_augmented::ContourTreeMaker::JoinTree
MergeTree & JoinTree
Definition: ContourTreeMaker.h:124
TransferLeafChains_CollapsePastRegular.h
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::AugmentMergeTrees_SetAugmentedMergeArcs
Definition: AugmentMergeTrees_SetAugmentedMergeArcs.h:69
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ComputeHyperAndSuperStructure_PermuteArcs
Definition: ComputeHyperAndSuperStructure_PermuteArcs.h:69
FindDegrees_SubtractLHE.h
vtkm::worklet::contourtree_augmented::ContourTreeMaker::AugmentMergeTrees
void AugmentMergeTrees()
Definition: ContourTreeMaker.h:617
ContourTreeNodeComparator.h
vtkm::worklet::contourtree_augmented::PrintIndices
void PrintIndices(std::string label, const vtkm::cont::ArrayHandle< T > &iVec, vtkm::Id nIndices=-1, std::ostream &outStream=std::cout)
Definition: augmented/PrintVectors.h:253
vtkm::worklet::contourtree_augmented::PrintHeader
void PrintHeader(vtkm::Id howMany, std::ostream &outStream=std::cout)
Definition: augmented/PrintVectors.h:151
ComputeHyperAndSuperStructure_SetFirstSupernodePerIterationWorklet.h
ArrayHandleImplicit.h
ComputeHyperAndSuperStructure_ResetHyperparentsId.h
vtkm::worklet::contourtree_augmented::ContourTreeMaker::CompressActiveSupernodes
void CompressActiveSupernodes()
Definition: ContourTreeMaker.h:958
vtkm::worklet::contourtree_augmented::details::LeafChainsToContourTree::Inwards
const IdArrayType & Inwards
Definition: ContourTreeMaker.h:824
MoveNoSuchElementToBackComparator.h
ContourTree.h
vtkm::worklet::contourtree_augmented::InitIdArrayTypeNoSuchElement
void InitIdArrayTypeNoSuchElement(IdArrayType &idArray, vtkm::Id size)
Definition: ContourTreeMaker.h:516
vtkm::worklet::contourtree_augmented::ContourTreeMaker::Updegree
IdArrayType Updegree
Definition: ContourTreeMaker.h:128
vtkm::cont::ArrayHandle::ReleaseResources
VTKM_CONT void ReleaseResources() const
Releases all resources in both the control and execution environments.
Definition: ArrayHandle.h:559
vtkm::worklet::contourtree_augmented::ContourTree::FirstSupernodePerIteration
IdArrayType FirstSupernodePerIteration
Definition: augmented/ContourTree.h:156
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::contourtree_augmented::details::LeafChainsToContourTree::Outdegree
const IdArrayType & Outdegree
Definition: ContourTreeMaker.h:820
vtkm::worklet::contourtree_augmented::MeshExtrema::Peaks
IdArrayType Peaks
Definition: MeshExtrema.h:84
vtkm::worklet::contourtree_augmented::IS_HYPERNODE
constexpr vtkm::Id IS_HYPERNODE
Definition: filter/scalar_topology/worklet/contourtree_augmented/Types.h:76
vtkm::worklet::contourtree_augmented::ContourTreeNoSuchElementSuperParents::operator()
VTKM_EXEC_CONT bool operator()(const T &x) const
Definition: ContourTreeMaker.h:510
vtkm::worklet::contourtree_augmented::details::LeafChainsToContourTree::Outbound
const IdArrayType & Outbound
Definition: ContourTreeMaker.h:822
vtkm::worklet::contourtree_augmented::ContourTreeMaker::AugmentedJoinSuperarcs
IdArrayType AugmentedJoinSuperarcs
Definition: ContourTreeMaker.h:132
vtkm::cont::ArrayHandleIndex
An implicit array handle containing the its own indices.
Definition: ArrayHandleIndex.h:54
CompressTrees_Step.h
vtkm::worklet::contourtree_augmented::ContourTree::WhenTransferred
IdArrayType WhenTransferred
Definition: augmented/ContourTree.h:139
WasNotTransferred.h
vtkm::worklet::contourtree_augmented::contourtree_maker_inc::ComputeHyperAndSuperStructure_HypernodesSetFirstSuperchild
Definition: ComputeHyperAndSuperStructure_HypernodesSetFirstSuperchild.h:69
vtkm::cont::TryExecute
VTKM_CONT bool TryExecute(Functor &&functor, Args &&... args)
Try to execute a functor on a set of devices until one succeeds.
Definition: TryExecute.h:244
vtkm::worklet::contourtree_augmented::ContourTree::Augmentnodes
IdArrayType Augmentnodes
Definition: augmented/ContourTree.h:132
vtkm::worklet::contourtree_augmented::details::LeafChainsToContourTree::Inbound
const IdArrayType & Inbound
Definition: ContourTreeMaker.h:823