HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Morphology.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
4 /// @file Morphology.h
5 ///
6 /// @authors Ken Museth, Nick Avramoussis
7 ///
8 /// @brief Implementation of morphological dilation and erosion.
9 ///
10 /// @note By design the morphological operations only change the
11 /// state of voxels, not their values. If one desires to
12 /// change the values of voxels that change state an efficient
13 /// technique is to construct a boolean mask by performing a
14 /// topology difference between the original and final grids.
15 
16 #ifndef OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
17 #define OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
18 
19 #include "Activate.h" // backwards compatibility
20 #include "Prune.h"
21 #include "ValueTransformer.h"
22 #include "openvdb/Types.h"
23 #include "openvdb/Grid.h"
26 
27 #include <tbb/task_arena.h>
28 #include <tbb/enumerable_thread_specific.h>
29 #include <tbb/parallel_for.h>
30 
31 #include <type_traits>
32 #include <vector>
33 
34 
35 namespace openvdb {
37 namespace OPENVDB_VERSION_NAME {
38 namespace tools {
39 
40 /// @brief Voxel topology of nearest neighbors
41 /// @details
42 /// <dl>
43 /// <dt><b>NN_FACE</b>
44 /// <dd>face adjacency (6 nearest neighbors, defined as all neighbor
45 /// voxels connected along one of the primary axes)
46 ///
47 /// <dt><b>NN_FACE_EDGE</b>
48 /// <dd>face and edge adjacency (18 nearest neighbors, defined as all
49 /// neighbor voxels connected along either one or two of the primary axes)
50 ///
51 /// <dt><b>NN_FACE_EDGE_VERTEX</b>
52 /// <dd>face, edge and vertex adjacency (26 nearest neighbors, defined
53 /// as all neighbor voxels connected along either one, two or all
54 /// three of the primary axes)
55 /// </dl>
57 
58 /// @brief Different policies when dilating trees with active tiles
59 /// @details
60 /// <dl>
61 /// <dt><b>IGNORE_TILES</b>
62 /// <dd>Active tiles are ignores. For dilation, only active voxels are
63 /// dilated. For erosion, active tiles still appear as neighbouring
64 /// activity however will themselves not be eroded.
65 ///
66 /// <dt><b>EXPAND_TILES</b>
67 /// <dd>For dilation and erosion, active tiles are voxelized (expanded),
68 /// dilated or eroded and left in their voxelized state irrespective of
69 /// their final state.
70 ///
71 /// <dt><b>PRESERVE_TILES</b>
72 /// <dd>For dilation, active tiles remain unchanged but they still
73 /// contribute to the dilation as if they were active voxels. For
74 /// erosion, active tiles are only eroded should the erosion wavefront
75 /// reach them, otherwise they are left unchanged. Additionally, dense
76 /// or empty nodes with constant values are pruned.
77 /// </dl>
79 
80 /// @brief Topologically dilate all active values (i.e. both voxels
81 /// and tiles) in a tree using one of three nearest neighbor
82 /// connectivity patterns.
83 /// @details If the input is *not* a MaskTree OR if tiles are being
84 /// preserved, this algorithm will copy the input tree topology onto a
85 /// MaskTree, performs the dilation on the mask and copies the resulting
86 /// topology back. This algorithm guarantees topology preservation
87 /// (non-pruned leaf nodes will persists) EXCEPT for direct MaskTree
88 /// dilation. MaskTree dilation is optimised for performance and may
89 /// replace existing leaf nodes i.e. any held leaf node pointers may
90 /// become invalid. See the Morphology class for more granular control.
91 /// @note This method is fully multi-threaded and support active tiles,
92 /// however only the PRESERVE_TILES policy ensures a pruned topology.
93 /// The values of any voxels are unchanged.
94 ///
95 /// @param tree tree or leaf manager to be dilated. The leaf
96 /// manager will be synchronized with the result.
97 /// @param iterations number of iterations to apply the dilation
98 /// @param nn connectivity pattern of the dilation: either
99 /// face-adjacent (6 nearest neighbors), face- and edge-adjacent
100 /// (18 nearest neighbors) or face-, edge- and vertex-adjacent (26
101 /// nearest neighbors).
102 /// @param mode Defined the policy for handling active tiles
103 /// (see above for details)
104 /// @param threaded Whether to multi-thread execution
105 template<typename TreeOrLeafManagerT>
106 inline void dilateActiveValues(TreeOrLeafManagerT& tree,
107  const int iterations = 1,
108  const NearestNeighbors nn = NN_FACE,
110  const bool threaded = true);
111 
112 /// @brief Topologically erode all active values (i.e. both voxels
113 /// and tiles) in a tree using one of three nearest neighbor
114 /// connectivity patterns.
115 /// @details If tiles are being preserve, this algorithm will copy the input
116 /// tree topology onto a MaskTree, performs the erosion on the mask and
117 /// intersects the resulting topology back. This algorithm guarantees
118 /// topology preservation (non-pruned leaf nodes will persists). See the
119 /// Morphology class for more granular control.
120 /// @note This method is fully multi-threaded and support active tiles,
121 /// however only the PRESERVE_TILES policy ensures a pruned topology.
122 /// The values of any voxels are unchanged. Erosion by NN_FACE neighbours
123 /// is usually faster than other neighbour schemes. NN_FACE_EDGE and
124 /// NN_FACE_EDGE_VERTEX operate at comparable dilation speeds.
125 ///
126 /// @param tree tree or leaf manager to be eroded. The leaf
127 /// manager will be synchronized with the result.
128 /// @param iterations number of iterations to apply the erosion
129 /// @param nn connectivity pattern of the erosion: either
130 /// face-adjacent (6 nearest neighbors), face- and edge-adjacent
131 /// (18 nearest neighbors) or face-, edge- and vertex-adjacent (26
132 /// nearest neighbors).
133 /// @param mode Defined the policy for handling active tiles
134 /// (see above for details)
135 /// @param threaded Whether to multi-thread execution
136 template<typename TreeOrLeafManagerT>
137 inline void erodeActiveValues(TreeOrLeafManagerT& tree,
138  const int iterations = 1,
139  const NearestNeighbors nn = NN_FACE,
141  const bool threaded = true);
142 
143 
144 ////////////////////////////////////////
145 
146 
147 namespace morphology {
148 
149 /// @brief Dilation/Erosion operations over a Trees leaf level voxel topology.
150 template<typename TreeType>
152 {
153 public:
154  using LeafType = typename TreeType::LeafNodeType;
155  using MaskType = typename LeafType::NodeMaskType;
156  using ValueType = typename TreeType::ValueType;
157  using MaskTreeT = typename TreeType::template ValueConverter<ValueMask>::Type;
158  using MaskLeafT = typename MaskTreeT::LeafNodeType;
160 
161  Morphology(TreeType& tree)
162  : mManagerPtr(new tree::LeafManager<TreeType>(tree))
163  , mManager(*mManagerPtr)
164  , mThreaded(true) {}
165 
167  : mManagerPtr(nullptr)
168  , mManager(tree)
169  , mThreaded(true) {}
170 
171  /// @brief Return whether this class is using multi-threading.
172  bool getThreaded() const { return mThreaded; }
173  /// @brief Set whether to use multi-threading.
174  /// @note The grain size is not exposed
175  inline void setThreaded(const bool threaded) { mThreaded = threaded; }
176 
177  /// @brief Return a const reference to the leaf manager
178  inline const tree::LeafManager<TreeType>& leafManager() const { return mManager; }
179 
180  /// @brief Topologically erode all voxels by the provided nearest neighbour
181  /// scheme and optionally collapse constant leaf nodes
182  /// @details Inactive Tiles contribute to the erosion but active tiles are
183  /// not modified.
184  /// @param iter Number of erosion iterations
185  /// @param nn Connectivity pattern of the erosion
186  /// @param prune Whether to collapse constant leaf nodes after the erosion
187  void erodeVoxels(const size_t iter,
188  const NearestNeighbors nn,
189  const bool prune = false);
190 
191  /// @brief Topologically dilate all voxels by the provided nearest neighbour
192  /// scheme and optionally collapse constant leaf nodes
193  /// @details Voxel values are unchanged and only leaf nodes are used to
194  /// propagate the dilation.
195  /// @param iter Number of dilation iterations
196  /// @param nn Connectivity pattern of the dilation
197  /// @param prune Whether to collapse constant leaf nodes after the dilation
198  /// @param preserveMaskLeafNodes When dilating mask trees, the default behaviour
199  /// chooses to steal the mask nodes rather than copy them. Although faster,
200  /// this means that leaf nodes may be re-allocated. Set this to true if you
201  /// need the original topology pointers to be preserved.
202  void dilateVoxels(const size_t iter,
203  const NearestNeighbors nn,
204  const bool prune = false,
205  const bool preserveMaskLeafNodes = false);
206 
207 
208  /// @brief Copy the current node masks onto the provided vector. The vector
209  /// is resized if necessary.
210  /// @param masks The vector of NodeMasks to copy onto
211  void copyMasks(std::vector<MaskType>& masks) const
212  {
213  if (masks.size() < mManager.leafCount()) {
214  masks.resize(mManager.leafCount());
215  }
216 
217  if (this->getThreaded()) {
218  // @note this is marginally faster than using leafRange or foreach
219  tbb::parallel_for(mManager.getRange(),
220  [&](const tbb::blocked_range<size_t>& r){
221  for (size_t idx = r.begin(); idx < r.end(); ++idx)
222  masks[idx] = mManager.leaf(idx).getValueMask();
223  });
224  }
225  else {
226  for (size_t idx = 0; idx < mManager.leafCount(); ++idx) {
227  masks[idx] = mManager.leaf(idx).getValueMask();
228  }
229  }
230  }
231 
232 public:
233  /// @brief Node Mask dilation/erosion operations for individual leaf nodes on
234  /// a given tree. The leaf node may optionally belong to a different tree
235  /// than the provided accessor, which will have the effect of dilating the
236  /// leaf node mask into a different tree, or eroding the node mask based
237  /// on corresponding neighbours in a different tree.
238  struct NodeMaskOp
239  {
240  static const Int32 DIM = static_cast<Int32>(LeafType::DIM);
241  static const Int32 LOG2DIM = static_cast<Int32>(LeafType::LOG2DIM);
242 
243  // Select the storage size based off the dimensions of the leaf node
244  using Word = typename std::conditional<LOG2DIM == 3, uint8_t,
245  typename std::conditional<LOG2DIM == 4, uint16_t,
246  typename std::conditional<LOG2DIM == 5, uint32_t,
247  typename std::conditional<LOG2DIM == 6, uint64_t,
249 
250  static_assert(!std::is_same<Word, void>::value,
251  "Unsupported Node Dimension for node mask dilation/erosion");
252 
254  const NearestNeighbors op)
255  : mOrigin(nullptr)
256  , mNeighbours(NodeMaskOp::ksize(op), nullptr)
257  , mAccessor(&accessor)
258  , mOnTile(true)
259  , mOffTile(false)
260  , mOp(op) {}
261 
262  /// @brief Dilate a single leaf node by the current spatial scheme
263  /// stored on the instance of this NodeMaskOp. Neighbour leaf
264  /// nodes are also updated.
265  /// @details Unlike erode, dilate is expected to be called in a
266  /// single threaded context as it will update the node masks
267  /// of neighbouring leaf nodes as well as the provided leaf.
268  /// @param leaf The leaf to dilate. The leaf's origin and value mask
269  /// are used to calculate the result of the dilation.
270  inline void dilate(LeafType& leaf)
271  {
272  // copy the mask
273  const MaskType mask = leaf.getValueMask();
274  this->dilate(leaf, mask);
275  }
276 
277  /// @brief Dilate a single leaf node by the current spatial scheme
278  /// stored on the instance of this NodeMaskOp. The provided
279  /// mask is used in place of the actual leaf's node mask and
280  /// applied to the leaf afterwards. Neighbour leaf nodes are
281  /// also updated.
282  /// @details Unlike erode, dilate is expected to be called in a
283  /// single threaded context as it will update the node masks
284  /// of neighbouring leaf nodes as well as the provided leaf.
285  /// @param leaf The leaf to dilate. The leaf's origin is used to
286  /// calculate the result of the dilation.
287  /// @param mask The node mask to use in place of the current leaf
288  /// node mask.
289  inline void dilate(LeafType& leaf, const MaskType& mask)
290  {
291  this->clear();
292  mNeighbours[0] = &(leaf.getValueMask());
293  this->setOrigin(leaf.origin());
294  switch (mOp) {
295  case NN_FACE_EDGE : { this->dilate18(mask); return; }
296  case NN_FACE_EDGE_VERTEX : { this->dilate26(mask); return; }
297  case NN_FACE : { this->dilate6(mask); return; }
298  default : {
299  assert(false && "Unknown op during dilation."); return;
300  }
301  }
302  }
303 
304  /// @brief Erode a single leaf node by the current spatial scheme
305  /// stored on the instance of this NodeMaskOp.
306  /// @details Unlike dilate, this method updates the provided mask
307  /// and does not apply the result to the leaf node. The
308  /// leaf node is simply used to infer the position in the
309  /// tree to find it's neighbours. This allows erode to be
310  /// called from multiple threads
311  /// @param leaf The leaf to erode. The leaf's origin is used to
312  /// calculate the result of the erosion.
313  /// @return The eroded mask
314  inline MaskType erode(const LeafType& leaf)
315  {
316  // copy the mask
317  MaskType mask = leaf.getValueMask();
318  this->erode(leaf, mask);
319  return mask;
320  }
321 
322  /// @brief Erode a single leaf node by the current spatial scheme
323  /// stored on the instance of this NodeMaskOp. The provided
324  /// mask is used in place of the actual leaf's node mask and
325  /// stores the erosion result.
326  /// @details Unlike dilate, this method updates the provided mask
327  /// and does not apply the result to the leaf node. The
328  /// leaf node is simply used to infer the position in the
329  /// tree to find it's neighbours.
330  /// @param leaf The leaf to erode. The leaf's origin is used to
331  /// calculate the result of the erosion.
332  /// @param mask The node mask to use in place of the current leaf
333  /// node mask.
334  inline void erode(const LeafType& leaf, MaskType& mask)
335  {
336  this->clear();
337  // @note leaf mask will not be modified through gather methods
338  mNeighbours[0] = const_cast<MaskType*>(&leaf.getValueMask());
339  this->setOrigin(leaf.origin());
340  switch (mOp) {
341  case NN_FACE_EDGE : { this->erode18(mask); return; }
342  case NN_FACE_EDGE_VERTEX : { this->erode26(mask); return; }
343  case NN_FACE : { this->erode6(mask); return; }
344  default : {
345  assert(false && "Unknown op during erosion."); return;
346  }
347  }
348  }
349 
350  private:
351  static size_t ksize(const NearestNeighbors op) {
352  switch (op) {
353  case NN_FACE_EDGE : return 19;
354  case NN_FACE_EDGE_VERTEX : return 27;
355  case NN_FACE : return 7;
356  default : return 7;
357  }
358  }
359 
360  void dilate6(const MaskType& mask);
361  void dilate18(const MaskType& mask);
362  void dilate26(const MaskType& mask);
363  void erode6(MaskType& mask);
364 
365  /// @note Forward API for erosion of 18/26 trees is to use erodeActiveValues
366  /// which falls back to an inverse dilation
367  /// @todo It may still be worth investigating more optimal gathering
368  /// techniques
369  inline void erode18(MaskType&) { OPENVDB_THROW(NotImplementedError, "erode18 is not implemented yet!"); }
370  inline void erode26(MaskType&) { OPENVDB_THROW(NotImplementedError, "erode26 is not implemented yet!"); }
371 
372  inline void setOrigin(const Coord& origin) { mOrigin = &origin; }
373  inline const Coord& getOrigin() const { return *mOrigin; }
374  inline void clear() { std::fill(mNeighbours.begin(), mNeighbours.end(), nullptr); }
375 
376  inline void scatter(size_t n, int indx)
377  {
378  assert(n < mNeighbours.size());
379  assert(mNeighbours[n]);
380  mNeighbours[n]->template getWord<Word>(indx) |= mWord;
381 
382  }
383  template<int DX, int DY, int DZ>
384  inline void scatter(size_t n, int indx)
385  {
386  assert(n < mNeighbours.size());
387  if (!mNeighbours[n]) {
388  mNeighbours[n] = this->getNeighbour<DX,DY,DZ,true>();
389  }
390  assert(mNeighbours[n]);
391  this->scatter(n, indx - (DIM - 1)*(DY + DX*DIM));
392  }
393  inline Word gather(size_t n, int indx)
394  {
395  assert(n < mNeighbours.size());
396  return mNeighbours[n]->template getWord<Word>(indx);
397  }
398  template<int DX, int DY, int DZ>
399  inline Word gather(size_t n, int indx)
400  {
401  assert(n < mNeighbours.size());
402  if (!mNeighbours[n]) {
403  mNeighbours[n] = this->getNeighbour<DX,DY,DZ,false>();
404  }
405  return this->gather(n, indx - (DIM -1)*(DY + DX*DIM));
406  }
407 
408  void scatterFacesXY(int x, int y, int i1, int n, int i2);
409  void scatterEdgesXY(int x, int y, int i1, int n, int i2);
410  Word gatherFacesXY(int x, int y, int i1, int n, int i2);
411  /// @note Currently unused
412  Word gatherEdgesXY(int x, int y, int i1, int n, int i2);
413 
414  template<int DX, int DY, int DZ, bool Create>
415  inline MaskType* getNeighbour()
416  {
417  const Coord xyz = mOrigin->offsetBy(DX*DIM, DY*DIM, DZ*DIM);
418  auto* leaf = mAccessor->probeLeaf(xyz);
419  if (leaf) return &(leaf->getValueMask());
420  if (mAccessor->isValueOn(xyz)) return &mOnTile;
421  if (!Create) return &mOffTile;
422  leaf = mAccessor->touchLeaf(xyz);
423  return &(leaf->getValueMask());
424  }
425 
426  private:
427  const Coord* mOrigin;
428  std::vector<MaskType*> mNeighbours;
429  AccessorType* const mAccessor;
430  Word mWord;
431  MaskType mOnTile, mOffTile;
432  const NearestNeighbors mOp;
433  };// NodeMaskOp
434 
435 private:
436  std::unique_ptr<tree::LeafManager<TreeType>> mManagerPtr;
437  tree::LeafManager<TreeType>& mManager;
438  bool mThreaded;
439 };// Morphology
440 
441 
442 template <typename TreeT>
444  typename TreeT::template ValueConverter<ValueMask>::Type*>::type
445 getMaskTree(TreeT& tree) { return &tree; }
446 
447 template <typename TreeT>
449  typename TreeT::template ValueConverter<ValueMask>::Type*>::type
450 getMaskTree(TreeT&) { return nullptr; }
451 
452 
453 template <typename TreeType>
454 void Morphology<TreeType>::erodeVoxels(const size_t iter,
455  const NearestNeighbors nn,
456  const bool prune)
457 {
458  if (iter == 0) return;
459  const size_t leafCount = mManager.leafCount();
460  if (leafCount == 0) return;
461  auto& tree = mManager.tree();
462 
463  // If the nearest neighbour mode is not FACE, fall back to an
464  // inverse dilation scheme which executes over a mask topology
465  if (nn != NN_FACE) {
466  // This method 1) dilates the input topology, 2) reverse the node masks,
467  // 3) performs a final dilation and 4) subtracts the result from the original
468  // topology. A cache of the original leaf pointers is required which tracks
469  // the original leaf nodes in a mask topology. These will need their
470  // masks updated in the original tree. The first dilation may create new leaf
471  // nodes in two instances. The first is where no topology existed before. The
472  // second is where an active tile overlaps with dilated topology. These
473  // tiles will be expanded to a dense leaf nodes by topologyUnion. We need
474  // to make sure these tiles are properly turned off.
475 
476  MaskTreeT mask(tree, false, TopologyCopy());
477 
478  // Create a new morphology class to perform dilation over the mask
479  tree::LeafManager<MaskTreeT> manager(mask);
480  Morphology<MaskTreeT> m(manager);
481  m.setThreaded(this->getThreaded());
482 
483  // perform a single dilation using the current scheme. Necessary to
484  // create edge leaf nodes and compute the active wavefront. Note that
485  // the cached array pointers will continue to be valid
486  m.dilateVoxels(1, nn, /*prune=*/false);
487 
488  // compute the wavefront. If the leaf previously existed, compute the
489  // xor activity result which is guaranteed to be equal to but slightly
490  // faster than a subtraction
491  auto computeWavefront = [&](const size_t idx) {
492  auto& leaf = manager.leaf(idx);
493  auto& nodemask = leaf.getValueMask();
494  if (const auto* original = tree.probeConstLeaf(leaf.origin())) {
495  nodemask ^= original->getValueMask();
496  }
497  else {
498  // should never have a dense leaf if it didn't exist in the
499  // original tree (it was previous possible when dilateVoxels()
500  // called topologyUnion without the preservation of active
501  // tiles)
502  assert(!nodemask.isOn());
503  }
504  };
505 
506  if (this->getThreaded()) {
507  tbb::parallel_for(manager.getRange(),
508  [&](const tbb::blocked_range<size_t>& r){
509  for (size_t idx = r.begin(); idx < r.end(); ++idx) {
510  computeWavefront(idx);
511  }
512  });
513  }
514  else {
515  for (size_t idx = 0; idx < manager.leafCount(); ++idx) {
516  computeWavefront(idx);
517  }
518  }
519 
520  // perform the inverse dilation
521  m.dilateVoxels(iter, nn, /*prune=*/false);
522 
523  // subtract the inverse dilation from the original node masks
524  auto subtractTopology = [&](const size_t idx) {
525  auto& leaf = mManager.leaf(idx);
526  const auto* maskleaf = mask.probeConstLeaf(leaf.origin());
527  assert(maskleaf);
528  leaf.getValueMask() -= maskleaf->getValueMask();
529  };
530 
531  if (this->getThreaded()) {
532  tbb::parallel_for(mManager.getRange(),
533  [&](const tbb::blocked_range<size_t>& r){
534  for (size_t idx = r.begin(); idx < r.end(); ++idx) {
535  subtractTopology(idx);
536  }
537  });
538  }
539  else {
540  for (size_t idx = 0; idx < leafCount; ++idx) {
541  subtractTopology(idx);
542  }
543  }
544  }
545  else {
546  // NN_FACE erosion scheme
547 
548  // Save the value masks of all leaf nodes.
549  std::vector<MaskType> nodeMasks;
550  this->copyMasks(nodeMasks);
551 
552  if (this->getThreaded()) {
553  const auto range = mManager.getRange();
554  for (size_t i = 0; i < iter; ++i) {
555  // For each leaf, in parallel, gather neighboring off values
556  // and update the cached value mask
558  [&](const tbb::blocked_range<size_t>& r) {
559  AccessorType accessor(tree);
560  NodeMaskOp cache(accessor, nn);
561  for (size_t idx = r.begin(); idx < r.end(); ++idx) {
562  const auto& leaf = mManager.leaf(idx);
563  if (leaf.isEmpty()) continue;
564  // original bit-mask of current leaf node
565  MaskType& newMask = nodeMasks[idx];
566  cache.erode(leaf, newMask);
567  }
568  });
569 
570  // update the masks after all nodes have been eroded
572  [&](const tbb::blocked_range<size_t>& r){
573  for (size_t idx = r.begin(); idx < r.end(); ++idx)
574  mManager.leaf(idx).setValueMask(nodeMasks[idx]);
575  });
576  }
577  }
578  else {
579  AccessorType accessor(tree);
580  NodeMaskOp cache(accessor, nn);
581  for (size_t i = 0; i < iter; ++i) {
582  // For each leaf, in parallel, gather neighboring off values
583  // and update the cached value mask
584  for (size_t idx = 0; idx < leafCount; ++idx) {
585  const auto& leaf = mManager.leaf(idx);
586  if (leaf.isEmpty()) continue;
587  // original bit-mask of current leaf node
588  MaskType& newMask = nodeMasks[idx];
589  cache.erode(leaf, newMask);
590  }
591 
592  for (size_t idx = 0; idx < leafCount; ++idx) {
593  mManager.leaf(idx).setValueMask(nodeMasks[idx]);
594  }
595  }
596  }
597  }
598 
599  // if prune, replace any inactive nodes
600  if (prune) {
601  tools::prune(mManager.tree(),
602  zeroVal<typename TreeType::ValueType>(),
603  this->getThreaded());
604  mManager.rebuild(!this->getThreaded());
605  }
606 }
607 
608 template <typename TreeType>
609 void Morphology<TreeType>::dilateVoxels(const size_t iter,
610  const NearestNeighbors nn,
611  const bool prune,
612  const bool preserveMaskLeafNodes)
613 {
614  if (iter == 0) return;
615 
616  const bool threaded = this->getThreaded();
617 
618  // Actual dilation op. main implementation is single threaded. Note that this
619  // is templated (auto-ed) as the threaded implemenation may call this with a
620  // different value type to the source morphology class
621  // @note GCC 6.4.0 crashes trying to compile this lambda with [&] capture
622  auto dilate = [iter, nn, threaded](auto& manager, const bool collapse) {
623 
624  using LeafManagerT = typename std::decay<decltype(manager)>::type;
625  using TreeT = typename LeafManagerT::TreeType;
626  using ValueT = typename TreeT::ValueType;
627  using LeafT = typename TreeT::LeafNodeType;
628 
629  // this is only used for the impl of copyMasks
630  Morphology<TreeT> m(manager);
631  m.setThreaded(threaded);
632 
633  TreeT& tree = manager.tree();
634  tree::ValueAccessor<TreeT> accessor(tree);
635 
636  // build cache objects
637  typename Morphology<TreeT>::NodeMaskOp cache(accessor, nn);
638  std::vector<MaskType> nodeMasks;
639  std::vector<std::unique_ptr<LeafT>> nodes;
640  const ValueT& bg = tree.background();
641  const bool steal = iter > 1;
642 
643  for (size_t i = 0; i < iter; ++i) {
644  if (i > 0) manager.rebuild(!threaded);
645  // If the leaf count is zero, we can stop dilation
646  const size_t leafCount = manager.leafCount();
647  if (leafCount == 0) return;
648 
649  // Copy the masks. This only resizes if necessary. As we're stealing/replacing
650  // dense nodes, it's possible we don't need to re-allocate the cache.
651  m.copyMasks(nodeMasks);
652 
653  // For each node, dilate the mask into itself and neighbouring leaf nodes.
654  // If the node was originally dense (all active), steal/replace it so
655  // subsequent iterations are faster
656  manager.foreach([&](LeafT& leaf, const size_t idx) {
657  // original bit-mask of current leaf node
658  const MaskType& oldMask = nodeMasks[idx];
659  const bool dense = oldMask.isOn();
660  cache.dilate(leaf, oldMask);
661  if (!dense) return;
662  // This node does not need to be visited again - replace or steal
663  if (collapse) {
664  // if collapse, replace this dense leaf with an active background tile
665  accessor.addTile(1, leaf.origin(), bg, true);
666  }
667  else if (steal) {
668  // otherwise, temporarily steal this node
669  nodes.emplace_back(
670  tree.template stealNode<LeafT>(leaf.origin(),
671  zeroVal<ValueT>(), true));
672  }
673  }, false);
674  }
675 
676  if (nodes.empty()) return;
677  // Add back all dense nodes
678  for (auto& node : nodes) {
679  accessor.addLeaf(node.release());
680  }
681  };
682 
683  //
684 
685  if (!threaded) {
686  // single threaded dilation. If it's a mask tree we can collapse
687  // nodes during the dilation, otherwise we must call prune afterwards
688  constexpr bool isMask = std::is_same<TreeType, MaskTreeT>::value;
689  dilate(mManager, isMask && prune);
690  if (!isMask && prune) {
691  tools::prune(mManager.tree(),
692  zeroVal<typename TreeType::ValueType>(),
693  threaded);
694  }
695  }
696  else {
697  // multi-threaded dilation
698 
699  // Steal or create mask nodes that represent the current leaf nodes.
700  // If the input is a mask tree, optionally re-allocate the nodes if
701  // preserveMaskLeafNodes is true. This ensures that leaf node
702  // pointers are not changed in the source tree. Stealing the mask
703  // nodes is significantly faster as it also avoids a post union.
704  std::vector<MaskLeafT*> array;
705  MaskTreeT* mask = getMaskTree(mManager.tree());
706 
707  if (!mask) {
709  topology.topologyUnion(mManager.tree());
710  array.reserve(mManager.leafCount());
711  topology.stealNodes(array);
712  }
713  else if (preserveMaskLeafNodes) {
714  mask = nullptr; // act as if theres no mask tree
715  array.resize(mManager.leafCount());
716  tbb::parallel_for(mManager.getRange(),
717  [&](const tbb::blocked_range<size_t>& r){
718  for (size_t idx = r.begin(); idx < r.end(); ++idx) {
719  array[idx] = new MaskLeafT(mManager.leaf(idx));
720  }
721  });
722  }
723  else {
724  array.reserve(mManager.leafCount());
725  mask->stealNodes(array);
726  }
727 
728  // @note this grain size is used for optimal threading
729  const size_t numThreads = size_t(tbb::this_task_arena::max_concurrency());
730  const size_t subTreeSize = math::Max(size_t(1), array.size()/(2*numThreads));
731 
732  // perform recursive dilation to sub trees
733  tbb::enumerable_thread_specific<std::unique_ptr<MaskTreeT>> pool;
734  MaskLeafT** start = array.data();
735  tbb::parallel_for(tbb::blocked_range<MaskLeafT**>(start, start + array.size(), subTreeSize),
736  [&](const tbb::blocked_range<MaskLeafT**>& range) {
737  std::unique_ptr<MaskTreeT> mask(new MaskTreeT);
738  for (MaskLeafT** it = range.begin(); it != range.end(); ++it) mask->addLeaf(*it);
739  tree::LeafManager<MaskTreeT> manager(*mask, range.begin(), range.end());
740  dilate(manager, prune);
741  auto& subtree = pool.local();
742  if (!subtree) subtree = std::move(mask);
743  else subtree->merge(*mask, MERGE_ACTIVE_STATES);
744  });
745 
746  if (!pool.empty()) {
747  auto piter = pool.begin();
748  MaskTreeT& subtree = mask ? *mask : **piter++;
749  for (; piter != pool.end(); ++piter) subtree.merge(**piter);
750  // prune, ensures partially merged nodes that may have become
751  // dense are converted to tiles
752  if (prune) tools::prune(subtree, zeroVal<typename MaskTreeT::ValueType>(), threaded);
753  // copy final topology onto dest. If mask exists, then this
754  // has already been handled by the above subtree merges
755  if (!mask) mManager.tree().topologyUnion(subtree, /*preserve-active-tiles*/true);
756  }
757  }
758 
759  // sync
760  mManager.rebuild(!threaded);
761 }
762 
763 
764 template <typename TreeType>
765 inline void
767 {
768  for (int x = 0; x < DIM; ++x) {
769  for (int y = 0, n = (x << LOG2DIM); y < DIM; ++y, ++n) {
770  // Extract the portion of the original mask that corresponds to a row in z.
771  if (Word& w = mask.template getWord<Word>(n)) {
772  // erode in two z directions (this is first since it uses the original w)
773  w = Word(w &
774  (Word(w<<1 | (this->template gather<0,0,-1>(1, n)>>(DIM-1))) &
775  Word(w>>1 | (this->template gather<0,0, 1>(2, n)<<(DIM-1)))));
776  w = Word(w & this->gatherFacesXY(x, y, 0, n, 3));
777  }
778  }// loop over y
779  }//loop over x
780 }
781 
782 template <typename TreeType>
783 inline void
784 Morphology<TreeType>::NodeMaskOp::dilate6(const MaskType& mask)
785 {
786  for (int x = 0; x < DIM; ++x ) {
787  for (int y = 0, n = (x << LOG2DIM);
788  y < DIM; ++y, ++n) {
789  // Extract the portion of the original mask that corresponds to a row in z.
790  if (const Word w = mask.template getWord<Word>(n)) {
791  // Dilate the current leaf in the +z and -z direction
792  this->mWord = Word(w | (w>>1) | (w<<1));
793  this->scatter(0, n);
794  // Dilate into neighbor leaf in the -z direction
795  if ( (this->mWord = Word(w<<(DIM-1))) ) {
796  this->template scatter< 0, 0,-1>(1, n);
797  }
798  // Dilate into neighbor leaf in the +z direction
799  if ( (this->mWord = Word(w>>(DIM-1))) ) {
800  this->template scatter< 0, 0, 1>(2, n);
801  }
802  // Dilate in the xy-face directions relative to the center leaf
803  this->mWord = w;
804  this->scatterFacesXY(x, y, 0, n, 3);
805  }
806  }// loop over y
807  }//loop over x
808 }
809 
810 template <typename TreeType>
811 inline void
812 Morphology<TreeType>::NodeMaskOp::dilate18(const MaskType& mask)
813 {
814  //origins of neighbor leaf nodes in the -z and +z directions
815  const Coord origin = this->getOrigin();
816  const Coord orig_mz = origin.offsetBy(0, 0, -DIM);
817  const Coord orig_pz = origin.offsetBy(0, 0, DIM);
818  for (int x = 0; x < DIM; ++x ) {
819  for (int y = 0, n = (x << LOG2DIM); y < DIM; ++y, ++n) {
820  if (const Word w = mask.template getWord<Word>(n)) {
821  {
822  this->mWord = Word(w | (w>>1) | (w<<1));
823  this->setOrigin(origin);
824  this->scatter(0, n);
825  this->scatterFacesXY(x, y, 0, n, 3);
826  this->mWord = w;
827  this->scatterEdgesXY(x, y, 0, n, 3);
828  }
829  if ( (this->mWord = Word(w<<(DIM-1))) ) {
830  this->setOrigin(origin);
831  this->template scatter< 0, 0,-1>(1, n);
832  this->setOrigin(orig_mz);
833  this->scatterFacesXY(x, y, 1, n, 11);
834  }
835  if ( (this->mWord = Word(w>>(DIM-1))) ) {
836  this->setOrigin(origin);
837  this->template scatter< 0, 0, 1>(2, n);
838  this->setOrigin(orig_pz);
839  this->scatterFacesXY(x, y, 2, n, 15);
840  }
841  }
842  }// loop over y
843  }//loop over x
844 }
845 
846 
847 template <typename TreeType>
848 inline void
849 Morphology<TreeType>::NodeMaskOp::dilate26(const MaskType& mask)
850 {
851  //origins of neighbor leaf nodes in the -z and +z directions
852  const Coord origin = this->getOrigin();
853  const Coord orig_mz = origin.offsetBy(0, 0, -DIM);
854  const Coord orig_pz = origin.offsetBy(0, 0, DIM);
855  for (int x = 0; x < DIM; ++x) {
856  for (int y = 0, n = (x << LOG2DIM); y < DIM; ++y, ++n) {
857  if (const Word w = mask.template getWord<Word>(n)) {
858  {
859  this->mWord = Word(w | (w>>1) | (w<<1));
860  this->setOrigin(origin);
861  this->scatter(0, n);
862  this->scatterFacesXY(x, y, 0, n, 3);
863  this->scatterEdgesXY(x, y, 0, n, 3);
864  }
865  if ( (this->mWord = Word(w<<(DIM-1))) ) {
866  this->setOrigin(origin);
867  this->template scatter< 0, 0,-1>(1, n);
868  this->setOrigin(orig_mz);
869  this->scatterFacesXY(x, y, 1, n, 11);
870  this->scatterEdgesXY(x, y, 1, n, 11);
871  }
872  if ( (this->mWord = Word(w>>(DIM-1))) ) {
873  this->setOrigin(origin);
874  this->template scatter< 0, 0, 1>(2, n);
875  this->setOrigin(orig_pz);
876  this->scatterFacesXY(x, y, 2, n, 19);
877  this->scatterEdgesXY(x, y, 2, n, 19);
878  }
879  }
880  }// loop over y
881  }//loop over x
882 }
883 
884 template<typename TreeType>
885 inline void
886 Morphology<TreeType>::NodeMaskOp::scatterFacesXY(int x, int y, int i1, int n, int i2)
887 {
888  // dilate current leaf or neighbor in the -x direction
889  if (x > 0) {
890  this->scatter(i1, n-DIM);
891  } else {
892  this->template scatter<-1, 0, 0>(i2, n);
893  }
894  // dilate current leaf or neighbor in the +x direction
895  if (x < DIM-1) {
896  this->scatter(i1, n+DIM);
897  } else {
898  this->template scatter< 1, 0, 0>(i2+1, n);
899  }
900  // dilate current leaf or neighbor in the -y direction
901  if (y > 0) {
902  this->scatter(i1, n-1);
903  } else {
904  this->template scatter< 0,-1, 0>(i2+2, n);
905  }
906  // dilate current leaf or neighbor in the +y direction
907  if (y < DIM-1) {
908  this->scatter(i1, n+1);
909  } else {
910  this->template scatter< 0, 1, 0>(i2+3, n);
911  }
912 }
913 
914 
915 template<typename TreeType>
916 inline void
917 Morphology<TreeType>::NodeMaskOp::scatterEdgesXY(int x, int y, int i1, int n, int i2)
918 {
919  if (x > 0) {
920  if (y > 0) {
921  this->scatter(i1, n-DIM-1);
922  } else {
923  this->template scatter< 0,-1, 0>(i2+2, n-DIM);
924  }
925  if (y < DIM-1) {
926  this->scatter(i1, n-DIM+1);
927  } else {
928  this->template scatter< 0, 1, 0>(i2+3, n-DIM);
929  }
930  } else {
931  if (y < DIM-1) {
932  this->template scatter<-1, 0, 0>(i2 , n+1);
933  } else {
934  this->template scatter<-1, 1, 0>(i2+7, n );
935  }
936  if (y > 0) {
937  this->template scatter<-1, 0, 0>(i2 , n-1);
938  } else {
939  this->template scatter<-1,-1, 0>(i2+4, n );
940  }
941  }
942  if (x < DIM-1) {
943  if (y > 0) {
944  this->scatter(i1, n+DIM-1);
945  } else {
946  this->template scatter< 0,-1, 0>(i2+2, n+DIM);
947  }
948  if (y < DIM-1) {
949  this->scatter(i1, n+DIM+1);
950  } else {
951  this->template scatter< 0, 1, 0>(i2+3, n+DIM);
952  }
953  } else {
954  if (y > 0) {
955  this->template scatter< 1, 0, 0>(i2+1, n-1);
956  } else {
957  this->template scatter< 1,-1, 0>(i2+6, n );
958  }
959  if (y < DIM-1) {
960  this->template scatter< 1, 0, 0>(i2+1, n+1);
961  } else {
962  this->template scatter< 1, 1, 0>(i2+5, n );
963  }
964  }
965 }
966 
967 
968 template<typename TreeType>
970 Morphology<TreeType>::NodeMaskOp::gatherFacesXY(int x, int y, int i1, int n, int i2)
971 {
972  // erode current leaf or neighbor in negative x-direction
973  Word w = x > 0 ?
974  this->gather(i1, n - DIM) :
975  this->template gather<-1,0,0>(i2, n);
976 
977  // erode current leaf or neighbor in positive x-direction
978  w = Word(w & (x < DIM - 1 ?
979  this->gather(i1, n + DIM) :
980  this->template gather<1,0,0>(i2 + 1, n)));
981 
982  // erode current leaf or neighbor in negative y-direction
983  w = Word(w & (y > 0 ?
984  this->gather(i1, n - 1) :
985  this->template gather<0,-1,0>(i2 + 2, n)));
986 
987  // erode current leaf or neighbor in positive y-direction
988  w = Word(w & (y < DIM - 1 ?
989  this->gather(i1, n + 1) :
990  this->template gather<0,1,0>(i2+3, n)));
991 
992  return w;
993 }
994 
995 
996 template<typename TreeType>
998 Morphology<TreeType>::NodeMaskOp::gatherEdgesXY(int x, int y, int i1, int n, int i2)
999 {
1000  Word w = ~Word(0);
1001 
1002  if (x > 0) {
1003  w &= y > 0 ? this->gather(i1, n-DIM-1) :
1004  this->template gather< 0,-1, 0>(i2+2, n-DIM);
1005  w &= y < DIM-1 ? this->gather(i1, n-DIM+1) :
1006  this->template gather< 0, 1, 0>(i2+3, n-DIM);
1007  } else {
1008  w &= y < DIM-1 ? this->template gather<-1, 0, 0>(i2 , n+1):
1009  this->template gather<-1, 1, 0>(i2+7, n );
1010  w &= y > 0 ? this->template gather<-1, 0, 0>(i2 , n-1):
1011  this->template gather<-1,-1, 0>(i2+4, n );
1012  }
1013  if (x < DIM-1) {
1014  w &= y > 0 ? this->gather(i1, n+DIM-1) :
1015  this->template gather< 0,-1, 0>(i2+2, n+DIM);
1016  w &= y < DIM-1 ? this->gather(i1, n+DIM+1) :
1017  this->template gather< 0, 1, 0>(i2+3, n+DIM);
1018  } else {
1019  w &= y > 0 ? this->template gather< 1, 0, 0>(i2+1, n-1):
1020  this->template gather< 1,-1, 0>(i2+6, n );
1021  w &= y < DIM-1 ? this->template gather< 1, 0, 0>(i2+1, n+1):
1022  this->template gather< 1, 1, 0>(i2+5, n );
1023  }
1024 
1025  return w;
1026 }
1027 
1028 } // namespace morphology
1029 
1030 
1031 /////////////////////////////////////////////////////////////////////
1032 /////////////////////////////////////////////////////////////////////
1033 
1034 /// @cond OPENVDB_DOCS_INTERNAL
1035 
1036 namespace morph_internal {
1037 template <typename T> struct Adapter {
1038  using TreeType = T;
1039  static TreeType& get(T& tree) { return tree; }
1040  static void sync(T&) {} // no-op
1041 };
1042 template <typename T>
1043 struct Adapter<openvdb::tree::LeafManager<T>> {
1044  using TreeType = T;
1045  static TreeType& get(openvdb::tree::LeafManager<T>& M) { return M.tree(); }
1046  static void sync(openvdb::tree::LeafManager<T>& M) { M.rebuild(); }
1047 };
1048 }
1049 
1050 /// @endcond
1051 
1052 template<typename TreeOrLeafManagerT>
1053 inline void dilateActiveValues(TreeOrLeafManagerT& treeOrLeafM,
1054  const int iterations,
1055  const NearestNeighbors nn,
1056  const TilePolicy mode,
1057  const bool threaded)
1058 {
1059  using AdapterT = morph_internal::Adapter<TreeOrLeafManagerT>;
1060  using TreeT = typename AdapterT::TreeType;
1061  using MaskT = typename TreeT::template ValueConverter<ValueMask>::Type;
1062 
1063  if (iterations <= 0) return;
1064 
1065  if (mode == IGNORE_TILES) {
1066  morphology::Morphology<TreeT> morph(treeOrLeafM);
1067  morph.setThreaded(threaded);
1068  // This will also sync the leaf manager
1069  morph.dilateVoxels(static_cast<size_t>(iterations), nn, /*prune=*/false);
1070  return;
1071  }
1072 
1073  // The following branching optimises from the different tree types
1074  // and TilePolicy combinations
1075 
1076  auto& tree = AdapterT::get(treeOrLeafM);
1077 
1078  // If the input is a mask tree, don't copy the topology - voxelize
1079  // it directly and let the morphology class directly steal/prune
1080  // its nodes
1081  constexpr bool isMask = std::is_same<TreeT, MaskT>::value;
1082 
1083  if (isMask || mode == EXPAND_TILES) {
1084  tree.voxelizeActiveTiles();
1085  AdapterT::sync(treeOrLeafM);
1086  morphology::Morphology<TreeT> morph(treeOrLeafM);
1087  morph.setThreaded(threaded);
1088 
1089  if (mode == PRESERVE_TILES) {
1090  morph.dilateVoxels(static_cast<size_t>(iterations), nn, /*prune=*/true);
1091  }
1092  else {
1093  assert(mode == EXPAND_TILES);
1094  morph.dilateVoxels(static_cast<size_t>(iterations), nn, /*prune=*/false);
1095  }
1096  return;
1097  }
1098 
1099  // If the tree TreeType being dilated is not a MaskTree, always copy
1100  // the topology over onto a MaskTree, perform the required dilation
1101  // and copy the final topology back. This technique avoids unnecessary
1102  // allocation with tile expansion and correctly preserves the tree
1103  // topology.
1104  //
1105  // Note that we also always use a mask if the tile policy is PRESERVE_TILES
1106  // due to the way the underlying dilation only works on voxels.
1107  // @todo Investigate tile based dilation
1108  assert(mode == PRESERVE_TILES);
1109 
1110  MaskT topology;
1111  topology.topologyUnion(tree);
1112  topology.voxelizeActiveTiles();
1113 
1114  morphology::Morphology<MaskT> morph(topology);
1115  morph.setThreaded(threaded);
1116  morph.dilateVoxels(static_cast<size_t>(iterations), nn, /*prune=*/true);
1117 
1118  tree.topologyUnion(topology, /*preserve-tiles*/true);
1119  topology.clear();
1120 
1121  // @note this is necessary to match the behaviour of mask tree dilation
1122  // where source partial leaf nodes that become dense are also
1123  // converted into tiles, not simply newly created dense nodes
1124  tools::prune(tree, zeroVal<typename TreeT::ValueType>(), threaded);
1125  AdapterT::sync(treeOrLeafM);
1126 }
1127 
1128 
1129 template<typename TreeOrLeafManagerT>
1130 inline void erodeActiveValues(TreeOrLeafManagerT& treeOrLeafM,
1131  const int iterations,
1132  const NearestNeighbors nn,
1133  const TilePolicy mode,
1134  const bool threaded)
1135 {
1136  using AdapterT = morph_internal::Adapter<TreeOrLeafManagerT>;
1137  using TreeT = typename AdapterT::TreeType;
1138  using MaskT = typename TreeT::template ValueConverter<ValueMask>::Type;
1139 
1140  if (iterations <= 0) return;
1141 
1142  // If the tile policiy is PRESERVE_TILES, peform the erosion on a
1143  // voxelized mask grid followed by a topology intersection such that
1144  // the original uneroded topology is preserved.
1145  if (mode == PRESERVE_TILES) {
1146  auto& tree = AdapterT::get(treeOrLeafM);
1147  MaskT topology;
1148  topology.topologyUnion(tree);
1149  topology.voxelizeActiveTiles();
1150 
1151  {
1152  morphology::Morphology<MaskT> morph(topology);
1153  morph.setThreaded(threaded);
1154  morph.erodeVoxels(static_cast<size_t>(iterations), nn, /*prune=*/false);
1155  }
1156 
1157  // prune to ensure topologyIntersection does not expand tiles
1158  // which have not been changed
1159  tools::prune(topology, zeroVal<typename MaskT::ValueType>(), threaded);
1160  tree.topologyIntersection(topology);
1161  AdapterT::sync(treeOrLeafM);
1162  return;
1163  }
1164 
1165  if (mode == EXPAND_TILES) {
1166  // if expanding, voxelize everything first if there are active tiles
1167  // @note check first to avoid any unnecessary rebuilds
1168  auto& tree = AdapterT::get(treeOrLeafM);
1169  if (tree.hasActiveTiles()) {
1170  tree.voxelizeActiveTiles();
1171  AdapterT::sync(treeOrLeafM);
1172  }
1173  }
1174 
1175  // ignoring tiles. They won't be eroded
1176  morphology::Morphology<TreeT> morph(treeOrLeafM);
1177  morph.setThreaded(threaded);
1178  morph.erodeVoxels(static_cast<size_t>(iterations), nn, /*prune=*/false);
1179 }
1180 
1181 
1182 /////////////////////////////////////////////////////////////////////
1183 /////////////////////////////////////////////////////////////////////
1184 
1185 
1186 /// @brief Topologically dilate all leaf-level active voxels in a tree
1187 /// using one of three nearest neighbor connectivity patterns.
1188 /// @warning This method is NOT multi-threaded and ignores active tiles!
1189 ///
1190 /// @param tree tree to be dilated
1191 /// @param iterations number of iterations to apply the dilation
1192 /// @param nn connectivity pattern of the dilation: either
1193 /// face-adjacent (6 nearest neighbors), face- and edge-adjacent
1194 /// (18 nearest neighbors) or face-, edge- and vertex-adjacent (26
1195 /// nearest neighbors).
1196 ///
1197 /// @note The values of any voxels are unchanged.
1198 template<typename TreeType>
1199 OPENVDB_DEPRECATED_MESSAGE("Switch to tools::dilateActiveValues. Use tools::IGNORE_TILES to maintain same (but perhaps unintended) behaviour")
1200 inline void dilateVoxels(TreeType& tree,
1201  int iterations = 1,
1203 {
1204  if (iterations <= 0) return;
1206  morph.setThreaded(false); // backwards compatible
1207  // This will also sync the leaf manager
1208  morph.dilateVoxels(static_cast<size_t>(iterations), nn, /*prune=*/false);
1209 }
1210 
1211 /// @brief Topologically dilate all leaf-level active voxels in a tree
1212 /// using one of three nearest neighbor connectivity patterns.
1213 /// @warning This method is NOT multi-threaded and ignores active tiles!
1214 ///
1215 /// @param manager LeafManager containing the tree to be dilated.
1216 /// On exit it is updated to include all the leaf
1217 /// nodes of the dilated tree.
1218 /// @param iterations number of iterations to apply the dilation
1219 /// @param nn connectivity pattern of the dilation: either
1220 /// face-adjacent (6 nearest neighbors), face- and edge-adjacent
1221 /// (18 nearest neighbors) or face-, edge- and vertex-adjacent (26
1222 /// nearest neighbors).
1223 ///
1224 /// @note The values of any voxels are unchanged.
1225 template<typename TreeType>
1226 OPENVDB_DEPRECATED_MESSAGE("Switch to tools::dilateActiveValues. Use tools::IGNORE_TILES to maintain same (but perhaps unintended) behaviour")
1227 inline void dilateVoxels(tree::LeafManager<TreeType>& manager,
1228  int iterations = 1,
1230 {
1231  if (iterations <= 0) return;
1232  morphology::Morphology<TreeType> morph(manager);
1233  morph.setThreaded(false);
1234  morph.dilateVoxels(static_cast<size_t>(iterations), nn, /*prune=*/false);
1235 }
1236 
1237 //@{
1238 /// @brief Topologically erode all leaf-level active voxels in the given tree.
1239 /// @details That is, shrink the set of active voxels by @a iterations voxels
1240 /// in the +x, -x, +y, -y, +z and -z directions, but don't change the values
1241 /// of any voxels, only their active states.
1242 /// @todo Currently operates only on leaf voxels; need to extend to tiles.
1243 template<typename TreeType>
1244 OPENVDB_DEPRECATED_MESSAGE("Switch to tools::erodeActiveValues. Use tools::IGNORE_TILES to maintain same (but perhaps unintended) behaviour")
1245 inline void erodeVoxels(TreeType& tree,
1246  int iterations=1,
1248 {
1249  if (iterations > 0) {
1251  morph.setThreaded(true);
1252  morph.erodeVoxels(static_cast<size_t>(iterations), nn, /*prune=*/false);
1253  }
1254 
1255  tools::pruneLevelSet(tree); // matches old behaviour
1256 }
1257 
1258 template<typename TreeType>
1259 OPENVDB_DEPRECATED_MESSAGE("Switch to tools::erodeActiveValues. Use tools::IGNORE_TILES to maintain same (but perhaps unintended) behaviour")
1260 inline void erodeVoxels(tree::LeafManager<TreeType>& manager,
1261  int iterations = 1,
1263 {
1264  if (iterations <= 0) return;
1265  morphology::Morphology<TreeType> morph(manager);
1266  morph.setThreaded(true);
1267  morph.erodeVoxels(static_cast<size_t>(iterations), nn, /*prune=*/false);
1268  tools::pruneLevelSet(manager.tree()); // matches old behaviour
1269 }
1270 //@}
1271 
1272 } // namespace tools
1273 } // namespace OPENVDB_VERSION_NAME
1274 } // namespace openvdb
1275 
1276 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
type
Definition: core.h:977
void parallel_for(int64_t start, int64_t end, std::function< void(int64_t index)> &&task, parallel_options opt=parallel_options(0, Split_Y, 1))
Definition: parallel.h:127
bool getThreaded() const
Return whether this class is using multi-threading.
Definition: Morphology.h:172
void dilate(LeafType &leaf)
Dilate a single leaf node by the current spatial scheme stored on the instance of this NodeMaskOp...
Definition: Morphology.h:270
GLuint start
Definition: glcorearb.h:474
Morphology(tree::LeafManager< TreeType > &tree)
Definition: Morphology.h:166
#define OPENVDB_DEPRECATED_MESSAGE(msg)
Definition: Platform.h:123
typename std::conditional< LOG2DIM==3, uint8_t, typename std::conditional< LOG2DIM==4, uint16_t, typename std::conditional< LOG2DIM==5, uint32_t, typename std::conditional< LOG2DIM==6, uint64_t, void >::type >::type >::type >::type Word
Definition: Morphology.h:248
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:178
void erodeActiveValues(TreeOrLeafManagerT &tree, const int iterations=1, const NearestNeighbors nn=NN_FACE, const TilePolicy mode=PRESERVE_TILES, const bool threaded=true)
Topologically erode all active values (i.e. both voxels and tiles) in a tree using one of three neare...
Definition: Morphology.h:1130
**But if you need a or simply need to know when the task has note that the like this
Definition: thread.h:623
void addLeaf(LeafNodeT *leaf)
Add the specified leaf to this tree, possibly creating a child branch in the process. If the leaf node already exists, replace it.
void dilateActiveValues(TreeOrLeafManagerT &tree, const int iterations=1, const NearestNeighbors nn=NN_FACE, const TilePolicy mode=PRESERVE_TILES, const bool threaded=true)
Topologically dilate all active values (i.e. both voxels and tiles) in a tree using one of three near...
Definition: Morphology.h:1053
GLint GLenum GLint x
Definition: glcorearb.h:408
GLubyte GLubyte GLubyte GLubyte w
Definition: glcorearb.h:856
size_t leafCount() const
Return the number of leaf nodes.
Definition: LeafManager.h:287
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Add a tile at the specified tree level that contains voxel (x, y, z), possibly deleting existing node...
GLenum array
Definition: glew.h:9108
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
NearestNeighbors
Voxel topology of nearest neighbors.
Definition: Morphology.h:56
ImageBuf OIIO_API dilate(const ImageBuf &src, int width=3, int height=-1, ROI roi={}, int nthreads=0)
GLint GLuint mask
Definition: glcorearb.h:123
GT_API const UT_StringHolder topology
Implementation of topological activation/deactivation.
Defined various multi-threaded utility functions for trees.
LeafNodeT * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one, but preserve the values and active states of all voxels.
void dilate(LeafType &leaf, const MaskType &mask)
Dilate a single leaf node by the current spatial scheme stored on the instance of this NodeMaskOp...
Definition: Morphology.h:289
Node Mask dilation/erosion operations for individual leaf nodes on a given tree. The leaf node may op...
Definition: Morphology.h:238
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:342
LeafNodeT * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z), or nullptr if no such node exists...
void erodeVoxels(const size_t iter, const NearestNeighbors nn, const bool prune=false)
Topologically erode all voxels by the provided nearest neighbour scheme and optionally collapse const...
Definition: Morphology.h:454
std::enable_if< std::is_same< TreeT, typename TreeT::template ValueConverter< ValueMask >::Type >::value, typename TreeT::template ValueConverter< ValueMask >::Type * >::type getMaskTree(TreeT &tree)
Definition: Morphology.h:445
GLenum mode
Definition: glcorearb.h:98
GLdouble n
Definition: glcorearb.h:2007
void dilateVoxels(const size_t iter, const NearestNeighbors nn, const bool prune=false, const bool preserveMaskLeafNodes=false)
Topologically dilate all voxels by the provided nearest neighbour scheme and optionally collapse cons...
Definition: Morphology.h:609
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
void setThreaded(const bool threaded)
Set whether to use multi-threading.
Definition: Morphology.h:175
TilePolicy
Different policies when dilating trees with active tiles.
Definition: Morphology.h:78
const GLdouble * m
Definition: glew.h:9166
GLsizei const GLfloat * value
Definition: glcorearb.h:823
typename TreeType::template ValueConverter< ValueMask >::Type MaskTreeT
Definition: Morphology.h:157
MaskType erode(const LeafType &leaf)
Erode a single leaf node by the current spatial scheme stored on the instance of this NodeMaskOp...
Definition: Morphology.h:314
GLenum GLint * range
Definition: glcorearb.h:1924
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:560
void erodeVoxels(TreeType &tree, int iterations=1, NearestNeighbors nn=NN_FACE)
Topologically erode all leaf-level active voxels in the given tree.
Definition: Morphology.h:1245
A LeafManager manages a linear array of pointers to a given tree's leaf nodes, as well as optional au...
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:318
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:334
void pruneLevelSet(TreeT &tree, bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing nodes whose values are all inactive with inactive ...
Definition: Prune.h:389
GLboolean r
Definition: glcorearb.h:1221
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:114
void dilateVoxels(TreeType &tree, int iterations=1, NearestNeighbors nn=NN_FACE)
Topologically dilate all leaf-level active voxels in a tree using one of three nearest neighbor conne...
Definition: Morphology.h:1200
const Type & Max(const Type &a, const Type &b)
Return the maximum of two values.
Definition: Math.h:598
GLint y
Definition: glcorearb.h:102
NodeMaskOp(AccessorType &accessor, const NearestNeighbors op)
Definition: Morphology.h:253
void erode(const LeafType &leaf, MaskType &mask)
Erode a single leaf node by the current spatial scheme stored on the instance of this NodeMaskOp...
Definition: Morphology.h:334
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
**Note that the tasks the is the thread number *for the pool
Definition: thread.h:643
const tree::LeafManager< TreeType > & leafManager() const
Return a const reference to the leaf manager.
Definition: Morphology.h:178
Dilation/Erosion operations over a Trees leaf level voxel topology.
Definition: Morphology.h:151
void copyMasks(std::vector< MaskType > &masks) const
Copy the current node masks onto the provided vector. The vector is resized if necessary.
Definition: Morphology.h:211
FMT_NOINLINE OutputIt fill(OutputIt it, size_t n, const fill_t< Char > &fill)
Definition: format.h:1483