VTK-m  2.0
OrientPointNormals.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 // This software is distributed WITHOUT ANY WARRANTY; without even
6 // the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
7 // PURPOSE. See the above copyright notice for more information.
8 //
9 // Copyright 2019 National Technology & Engineering Solutions of Sandia, LLC (NTESS).
10 // Copyright 2019 UT-Battelle, LLC.
11 // Copyright 2019 Los Alamos National Security.
12 //
13 // Under the terms of Contract DE-NA0003525 with NTESS,
14 // the U.S. Government retains certain rights in this software.
15 //
16 // Under the terms of Contract DE-AC52-06NA25396 with Los Alamos National
17 // Laboratory (LANL), the U.S. Government retains certain rights in
18 // this software.
19 //============================================================================
20 #ifndef vtkm_m_worklet_OrientPointNormals_h
21 #define vtkm_m_worklet_OrientPointNormals_h
22 
23 #include <vtkm/Range.h>
24 #include <vtkm/Types.h>
25 
26 #include <vtkm/cont/Algorithm.h>
27 #include <vtkm/cont/ArrayHandle.h>
32 #include <vtkm/cont/BitField.h>
33 #include <vtkm/cont/Logging.h>
34 
40 
41 namespace vtkm
42 {
43 namespace worklet
44 {
45 
52 {
53  static constexpr vtkm::Id INVALID_ID = -1;
54 
55  // Returns true if v1 and v2 are pointing in the same hemisphere.
56  template <typename T>
57  VTKM_EXEC static bool SameDirection(const vtkm::Vec<T, 3>& v1, const vtkm::Vec<T, 3>& v2)
58  {
59  return vtkm::Dot(v1, v2) >= 0;
60  }
61 
62  // Ensure that the normal is pointing in the same hemisphere as ref.
63  // Returns true if normal is modified.
64  template <typename T>
65  VTKM_EXEC static bool Align(vtkm::Vec<T, 3>& normal, const vtkm::Vec<T, 3>& ref)
66  {
67  if (!SameDirection(normal, ref))
68  {
69  normal = -normal;
70  return true;
71  }
72  return false;
73  }
74 
75 public:
76  // Locates starting points for BFS traversal of dataset by finding points
77  // on the dataset boundaries. The normals for these points are corrected by
78  // making them point outside of the dataset, and they are marked as both
79  // active and visited.
81  {
82  public:
83  using ControlSignature = void(FieldIn coords,
84  FieldInOut normals,
85  WholeArrayIn ranges,
86  FieldOut activePoints,
87  FieldOut visitedPoints,
88  FieldOut refPoints);
89  using ExecutionSignature =
90  _6(InputIndex pointId, _1 coord, _2 normal, _3 ranges, _4 activePoints, _5 visitedPoints);
91 
92  template <typename CoordT, typename NormalT, typename RangePortal>
94  const vtkm::Vec<CoordT, 3>& point,
95  vtkm::Vec<NormalT, 3>& normal,
96  const RangePortal& ranges,
97  bool& isActive,
98  bool& isVisited) const
99  {
100  for (vtkm::IdComponent dim = 0; dim < 3; ++dim)
101  {
102  const auto& range = ranges.Get(dim);
103  const auto val = static_cast<decltype(range.Min)>(point[dim]);
104  if (val <= range.Min)
105  {
106  vtkm::Vec<NormalT, 3> ref{ static_cast<NormalT>(0) };
107  ref[dim] = static_cast<NormalT>(-1);
108  Align(normal, ref);
109  isActive = true;
110  isVisited = true;
111  return pointId;
112  }
113  else if (val >= range.Max)
114  {
115  vtkm::Vec<NormalT, 3> ref{ static_cast<NormalT>(0) };
116  ref[dim] = static_cast<NormalT>(1);
117  Align(normal, ref);
118  isActive = true;
119  isVisited = true;
120  return pointId;
121  }
122  }
123 
124  isActive = false;
125  isVisited = false;
126  return INVALID_ID;
127  }
128  };
129 
130  // Traverses the active points (via mask) and marks the connected cells as
131  // active. Set the reference point for all adjacent cells to the current
132  // point.
134  {
135  public:
136  using ControlSignature = void(CellSetIn cellSet,
137  // InOut to preserve data on masked indices
138  BitFieldInOut activeCells,
139  BitFieldInOut visitedCells,
140  FieldInOutPoint activePoints);
141  using ExecutionSignature = _4(CellIndices cells, _2 activeCells, _3 visitedCells);
142 
144 
145  // Mark all unvisited cells as active:
146  template <typename CellListT, typename ActiveCellsT, typename VisitedCellsT>
147  VTKM_EXEC bool operator()(const CellListT& cells,
148  ActiveCellsT& activeCells,
149  VisitedCellsT& visitedCells) const
150  {
151  for (vtkm::IdComponent c = 0; c < cells.GetNumberOfComponents(); ++c)
152  {
153  const vtkm::Id cellId = cells[c];
154  bool checkNotVisited = false;
155  if (visitedCells.CompareExchangeBitAtomic(cellId, &checkNotVisited, true))
156  { // This thread is first to visit cell
157  activeCells.SetBitAtomic(cellId, true);
158  }
159  }
160 
161  // Mark the current point as inactive:
162  return false;
163  }
164  };
165 
166  // Traverses the active cells and mark the connected points as active,
167  // propogating the reference pointId.
169  {
170  public:
171  using ControlSignature = void(CellSetIn cellSet,
172  BitFieldInOut activePoints,
173  BitFieldIn visitedPoints,
174  WholeArrayInOut refPoints,
175  FieldInOutCell activeCells);
176  using ExecutionSignature = _5(PointIndices points,
177  _2 activePoints,
178  _3 visitedPoints,
179  _4 refPoints);
180 
182 
183  template <typename PointListT,
184  typename ActivePointsT,
185  typename VisitedPointsT,
186  typename RefPointsT>
187  VTKM_EXEC bool operator()(const PointListT& points,
188  ActivePointsT& activePoints,
189  VisitedPointsT& visitedPoints,
190  RefPointsT& refPoints) const
191  {
192  // Find any point in the cell that has already been visited, and take
193  // its id as the reference for this cell.
194  vtkm::Id refPtId = INVALID_ID;
195  for (vtkm::IdComponent p = 0; p < points.GetNumberOfComponents(); ++p)
196  {
197  const vtkm::Id pointId = points[p];
198  const bool alreadyVisited = visitedPoints.GetBit(pointId);
199  if (alreadyVisited)
200  {
201  refPtId = pointId;
202  break;
203  }
204  }
205 
206  // There must be one valid point in each cell:
207  VTKM_ASSERT("Reference point not found." && refPtId != INVALID_ID);
208 
209  // Propogate the reference point to other cell members
210  for (vtkm::IdComponent p = 0; p < points.GetNumberOfComponents(); ++p)
211  {
212  const vtkm::Id pointId = points[p];
213 
214  // Mark this point as active
215  const bool alreadyVisited = visitedPoints.GetBit(pointId);
216  if (!alreadyVisited)
217  {
218  bool checkNotActive = false;
219  if (activePoints.CompareExchangeBitAtomic(pointId, &checkNotActive, true))
220  { // If we're the first thread to mark point active, set ref point:
221  refPoints.Set(pointId, refPtId);
222  }
223  }
224  }
225 
226  // Mark current cell as inactive:
227  return false;
228  }
229  };
230 
231  // For each point with a refPtId set, ensure that the associated normal is
232  // in the same hemisphere as the reference normal.
233  // This must be done in a separate step from MarkActivePoints since modifying
234  // visitedPoints in that worklet would create race conditions.
236  {
237  public:
238  using ControlSignature = void(FieldIn refIds,
239  WholeArrayInOut normals,
240  // InOut to preserve data on masked indices
241  BitFieldInOut visitedPoints);
242  using ExecutionSignature = void(InputIndex ptId, _1 refPtId, _2 normals, _3 visitedPoints);
243 
245 
246  template <typename NormalsPortal, typename VisitedPointsT>
247  VTKM_EXEC void operator()(const vtkm::Id ptId,
248  const vtkm::Id refPtId,
249  NormalsPortal& normals,
250  VisitedPointsT& visitedPoints) const
251  {
252  visitedPoints.SetBitAtomic(ptId, true);
253 
254  using Normal = typename NormalsPortal::ValueType;
255  Normal normal = normals.Get(ptId);
256  const Normal ref = normals.Get(refPtId);
257  if (Align(normal, ref))
258  {
259  normals.Set(ptId, normal);
260  }
261  }
262  };
263 
264  template <typename CellSetType,
265  typename CoordsCompType,
266  typename CoordsStorageType,
267  typename PointNormalCompType,
268  typename PointNormalStorageType>
269  VTKM_CONT static void Run(
270  const CellSetType& cells,
271  const vtkm::cont::ArrayHandle<vtkm::Vec<CoordsCompType, 3>, CoordsStorageType>& coords,
273  pointNormals)
274  {
275  using RangeType = vtkm::cont::ArrayHandle<vtkm::Range>;
276 
281 
282  const vtkm::Id numCells = cells.GetNumberOfCells();
283 
285  "OrientPointNormals worklet (%lld points, %lld cells)",
286  static_cast<vtkm::Int64>(coords.GetNumberOfValues()),
287  static_cast<vtkm::Int64>(numCells));
288 
289  // active = cells / point to be used in the next worklet invocation mask.
290  vtkm::cont::BitField activePointBits; // Initialized by MarkSourcePoints
291  auto activePoints = vtkm::cont::make_ArrayHandleBitField(activePointBits);
292 
293  vtkm::cont::BitField activeCellBits;
294  activeCellBits.AllocateAndFill(numCells, false);
295  auto activeCells = vtkm::cont::make_ArrayHandleBitField(activeCellBits);
296 
297  // visited = cells / points that have been corrected.
298  vtkm::cont::BitField visitedPointBits; // Initialized by MarkSourcePoints
299  auto visitedPoints = vtkm::cont::make_ArrayHandleBitField(visitedPointBits);
300 
301  vtkm::cont::BitField visitedCellBits;
302  visitedCellBits.AllocateAndFill(numCells, false);
303  auto visitedCells = vtkm::cont::make_ArrayHandleBitField(visitedCellBits);
304 
305  vtkm::cont::ArrayHandle<vtkm::Id> mask; // Allocated as needed
306 
307  // For each point, store a reference alignment point. Allocated by
308  // MarkSourcePoints.
310 
311  // 1) Compute range of coords.
312  const RangeType ranges = vtkm::cont::ArrayRangeCompute(coords);
313 
314  // 2) Label source points for traversal (use those on a boundary).
315  // Correct the normals for these points by making them point towards the
316  // boundary.
317  {
318  MarkSourcePoints dispatcher;
319  dispatcher.Invoke(coords, pointNormals, ranges, activePoints, visitedPoints, refPoints);
320  }
321 
322  for (size_t iter = 1;; ++iter)
323  {
324  // 3) Mark unvisited cells adjacent to active points
325  {
326  vtkm::Id numActive = vtkm::cont::Algorithm::BitFieldToUnorderedSet(activePointBits, mask);
327  (void)numActive;
329  "MarkActiveCells from " << numActive << " active points.");
330  MarkActiveCells dispatcher{ vtkm::worklet::MaskIndices{ mask } };
331  dispatcher.Invoke(cells, activeCellBits, visitedCellBits, activePoints);
332  }
333 
334  // 4) Mark unvisited points in active cells, using ref point from cell.
335  {
336  vtkm::Id numActive = vtkm::cont::Algorithm::BitFieldToUnorderedSet(activeCellBits, mask);
337  (void)numActive;
339  "MarkActivePoints from " << numActive << " active cells.");
340  MarkActivePoints dispatcher{ vtkm::worklet::MaskIndices{ mask } };
341  dispatcher.Invoke(cells, activePointBits, visitedPointBits, refPoints, activeCells);
342  }
343 
344  vtkm::Id numActivePoints =
345  vtkm::cont::Algorithm::BitFieldToUnorderedSet(activePointBits, mask);
346 
347  if (numActivePoints == 0)
348  { // Done!
349  VTKM_LOG_S(vtkm::cont::LogLevel::Perf, "Iteration " << iter << ": Traversal complete.");
350  break;
351  }
352 
354  "Iteration " << iter << ": Processing " << numActivePoints << " normals.");
355 
356  // 5) Correct normals for active points.
357  {
358  ProcessNormals dispatcher{ vtkm::worklet::MaskIndices{ mask } };
359  dispatcher.Invoke(refPoints, pointNormals, visitedPointBits);
360  }
361  }
362  }
363 };
364 }
365 } // end namespace vtkm::worklet
366 
367 
368 #endif // vtkm_m_worklet_OrientPointNormals_h
vtkm::worklet::OrientPointNormals::WorkletProcessNormals::ExecutionSignature
void(InputIndex ptId, _1 refPtId, _2 normals, _3 visitedPoints) ExecutionSignature
Definition: OrientPointNormals.h:242
VTKM_LOG_SCOPE
#define VTKM_LOG_SCOPE(level,...)
Definition: Logging.h:265
vtkm::cont::ArrayHandle
Manages an array-worth of data.
Definition: ArrayHandle.h:283
ArrayHandle.h
vtkm::worklet::OrientPointNormals::WorkletMarkSourcePoints::ControlSignature
void(FieldIn coords, FieldInOut normals, WholeArrayIn ranges, FieldOut activePoints, FieldOut visitedPoints, FieldOut refPoints) ControlSignature
Definition: OrientPointNormals.h:88
VTKM_EXEC
#define VTKM_EXEC
Definition: ExportMacros.h:51
vtkm
Groups connected points that have the same field value.
Definition: Atomic.h:19
vtkm::cont::Algorithm::BitFieldToUnorderedSet
static VTKM_CONT vtkm::Id BitFieldToUnorderedSet(vtkm::cont::DeviceAdapterId devId, const vtkm::cont::BitField &bits, vtkm::cont::ArrayHandle< Id, IndicesStorage > &indices)
Definition: Algorithm.h:389
ArrayRangeCompute.h
Types.h
WorkletMapField.h
VTKM_ASSERT
#define VTKM_ASSERT(condition)
Definition: Assert.h:43
vtkm::worklet::OrientPointNormals::WorkletMarkActivePoints::ExecutionSignature
_5(PointIndices points, _2 activePoints, _3 visitedPoints, _4 refPoints) ExecutionSignature
Definition: OrientPointNormals.h:179
vtkm::worklet::WorkletMapField::FieldOut
A control signature tag for output fields.
Definition: WorkletMapField.h:60
ArrayHandleBitField.h
vtkm::IdComponent
vtkm::Int32 IdComponent
Represents a component ID (index of component in a vector).
Definition: Types.h:168
vtkm::worklet::OrientPointNormals::WorkletMarkActivePoints::ControlSignature
void(CellSetIn cellSet, BitFieldInOut activePoints, BitFieldIn visitedPoints, WholeArrayInOut refPoints, FieldInOutCell activeCells) ControlSignature
Definition: OrientPointNormals.h:175
BitField.h
ArrayHandleTransform.h
vtkm::worklet::OrientPointNormals::WorkletProcessNormals
Definition: OrientPointNormals.h:235
vtkm::worklet::OrientPointNormals::WorkletProcessNormals::operator()
VTKM_EXEC void operator()(const vtkm::Id ptId, const vtkm::Id refPtId, NormalsPortal &normals, VisitedPointsT &visitedPoints) const
Definition: OrientPointNormals.h:247
ArrayHandleConstant.h
vtkm::worklet::OrientPointNormals::Align
static VTKM_EXEC bool Align(vtkm::Vec< T, 3 > &normal, const vtkm::Vec< T, 3 > &ref)
Definition: OrientPointNormals.h:65
vtkm::worklet::OrientPointNormals::WorkletMarkSourcePoints::operator()
VTKM_EXEC vtkm::Id operator()(const vtkm::Id pointId, const vtkm::Vec< CoordT, 3 > &point, vtkm::Vec< NormalT, 3 > &normal, const RangePortal &ranges, bool &isActive, bool &isVisited) const
Definition: OrientPointNormals.h:93
vtkm::worklet::OrientPointNormals::WorkletMarkActiveCells
Definition: OrientPointNormals.h:133
vtkm::worklet::WorkletVisitCellsWithPoints::PointIndices
IncidentElementIndices PointIndices
Definition: WorkletMapTopology.h:269
vtkm::Id
vtkm::Int32 Id
Represents an ID (index into arrays).
Definition: Types.h:191
DispatcherMapField.h
vtkm::worklet::OrientPointNormals::WorkletMarkActiveCells::ControlSignature
void(CellSetIn cellSet, BitFieldInOut activeCells, BitFieldInOut visitedCells, FieldInOutPoint activePoints) ControlSignature
Definition: OrientPointNormals.h:140
MaskIndices.h
vtkm::worklet::OrientPointNormals::SameDirection
static VTKM_EXEC bool SameDirection(const vtkm::Vec< T, 3 > &v1, const vtkm::Vec< T, 3 > &v2)
Definition: OrientPointNormals.h:57
vtkm::worklet::OrientPointNormals
Orients normals to point outside of the dataset.
Definition: OrientPointNormals.h:51
vtkm::worklet::DispatcherMapField
Dispatcher for worklets that inherit from WorkletMapField.
Definition: DispatcherMapField.h:25
vtkm::worklet::WorkletVisitPointsWithCells
Base class for worklets that map from Cells to Points.
Definition: WorkletMapTopology.h:274
Algorithm.h
vtkm::worklet::Normal
Definition: Normalize.h:22
vtkm::worklet::OrientPointNormals::WorkletMarkActivePoints
Definition: OrientPointNormals.h:168
vtkm::worklet::DispatcherMapTopology
Dispatcher for worklets that inherit from WorkletMapTopology.
Definition: DispatcherMapTopology.h:31
vtkm::worklet::WorkletMapField::FieldIn
A control signature tag for input fields.
Definition: WorkletMapField.h:49
vtkm::worklet::OrientPointNormals::INVALID_ID
static constexpr vtkm::Id INVALID_ID
Definition: OrientPointNormals.h:53
vtkm::worklet::WorkletVisitCellsWithPoints
Base class for worklets that map from Points to Cells.
Definition: WorkletMapTopology.h:255
Range.h
VTKM_CONT
#define VTKM_CONT
Definition: ExportMacros.h:57
vtkm::worklet::WorkletMapField::FieldInOut
A control signature tag for input-output (in-place) fields.
Definition: WorkletMapField.h:71
vtkm::cont::make_ArrayHandleBitField
VTKM_CONT vtkm::cont::ArrayHandleBitField make_ArrayHandleBitField(const vtkm::cont::BitField &bitField)
Definition: ArrayHandleBitField.h:196
vtkm::worklet::OrientPointNormals::WorkletMarkActiveCells::operator()
VTKM_EXEC bool operator()(const CellListT &cells, ActiveCellsT &activeCells, VisitedCellsT &visitedCells) const
Definition: OrientPointNormals.h:147
vtkm::cont::BitField::AllocateAndFill
VTKM_CONT void AllocateAndFill(vtkm::Id numberOfBits, ValueType value, vtkm::cont::Token &token) const
Allocate the requested number of bits and fill with the requested bit or word.
Definition: BitField.h:575
vtkm::worklet::WorkletVisitPointsWithCells::CellIndices
IncidentElementIndices CellIndices
Definition: WorkletMapTopology.h:288
VTKM_LOG_S
#define VTKM_LOG_S(level,...)
Writes a message using stream syntax to the indicated log level.
Definition: Logging.h:261
vtkm::Vec< T, 3 >
Definition: Types.h:975
vtkm::Vec
A short fixed-length array.
Definition: Types.h:767
vtkm::cont::BitField
Definition: BitField.h:497
vtkm::worklet::OrientPointNormals::WorkletProcessNormals::ControlSignature
void(FieldIn refIds, WholeArrayInOut normals, BitFieldInOut visitedPoints) ControlSignature
Definition: OrientPointNormals.h:241
vtkm::worklet::OrientPointNormals::WorkletMarkSourcePoints::ExecutionSignature
_6(InputIndex pointId, _1 coord, _2 normal, _3 ranges, _4 activePoints, _5 visitedPoints) ExecutionSignature
Definition: OrientPointNormals.h:90
vtkm::worklet::OrientPointNormals::WorkletMarkActivePoints::operator()
VTKM_EXEC bool operator()(const PointListT &points, ActivePointsT &activePoints, VisitedPointsT &visitedPoints, RefPointsT &refPoints) const
Definition: OrientPointNormals.h:187
vtkm::worklet::MaskIndices
Mask using a given array of indices to include in the output.
Definition: MaskIndices.h:30
Logging.h
Logging utilities.
vtkm::worklet::OrientPointNormals::WorkletMarkSourcePoints
Definition: OrientPointNormals.h:80
vtkm::cont::ArrayRangeCompute
VTKM_CONT_EXPORT vtkm::cont::ArrayHandle< vtkm::Range > ArrayRangeCompute(const vtkm::cont::UnknownArrayHandle &array, vtkm::cont::DeviceAdapterId device=vtkm::cont::DeviceAdapterTagAny{})
Compute the range of the data in an array handle.
DispatcherMapTopology.h
WorkletMapTopology.h
vtkm::worklet::OrientPointNormals::WorkletMarkActiveCells::ExecutionSignature
_4(CellIndices cells, _2 activeCells, _3 visitedCells) ExecutionSignature
Definition: OrientPointNormals.h:141
vtkm::worklet::WorkletVisitPointsWithCells::FieldInOutPoint
FieldInOut FieldInOutPoint
Definition: WorkletMapTopology.h:284
vtkm::exec::arg::InputIndex
The ExecutionSignature tag to use to get the input index.
Definition: InputIndex.h:42
vtkm::cont::LogLevel::Perf
@ Perf
General timing data and algorithm flow information, such as filter execution, worklet dispatches,...
vtkm::worklet::OrientPointNormals::Run
static VTKM_CONT void Run(const CellSetType &cells, const vtkm::cont::ArrayHandle< vtkm::Vec< CoordsCompType, 3 >, CoordsStorageType > &coords, vtkm::cont::ArrayHandle< vtkm::Vec< PointNormalCompType, 3 >, PointNormalStorageType > &pointNormals)
Definition: OrientPointNormals.h:269
vtkm::worklet::WorkletMapField
Base class for worklets that do a simple mapping of field arrays.
Definition: WorkletMapField.h:38
vtkm::worklet::WorkletVisitCellsWithPoints::FieldInOutCell
FieldInOut FieldInOutCell
Definition: WorkletMapTopology.h:265