OpenVDB  12.0.0
PointGroupImpl.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: Apache-2.0
3 
4 /// @author Dan Bailey
5 ///
6 /// @file PointGroupImpl.h
7 ///
8 
9 #ifndef OPENVDB_POINTS_POINT_GROUP_IMPL_HAS_BEEN_INCLUDED
10 #define OPENVDB_POINTS_POINT_GROUP_IMPL_HAS_BEEN_INCLUDED
11 
12 namespace openvdb {
14 namespace OPENVDB_VERSION_NAME {
15 namespace points {
16 
17 /// @cond OPENVDB_DOCS_INTERNAL
18 
19 namespace point_group_internal {
20 
21 
22 /// Copy a group attribute value from one group offset to another
23 template<typename PointDataTreeType>
24 struct CopyGroupOp {
25 
26  using LeafManagerT = typename tree::LeafManager<PointDataTreeType>;
27  using LeafRangeT = typename LeafManagerT::LeafRange;
28  using GroupIndex = AttributeSet::Descriptor::GroupIndex;
29 
30  CopyGroupOp(const GroupIndex& targetIndex,
31  const GroupIndex& sourceIndex)
32  : mTargetIndex(targetIndex)
33  , mSourceIndex(sourceIndex) { }
34 
35  void operator()(const typename LeafManagerT::LeafRange& range) const {
36 
37  for (auto leaf = range.begin(); leaf; ++leaf) {
38 
39  GroupHandle sourceGroup = leaf->groupHandle(mSourceIndex);
40  GroupWriteHandle targetGroup = leaf->groupWriteHandle(mTargetIndex);
41 
42  for (auto iter = leaf->beginIndexAll(); iter; ++iter) {
43  const bool groupOn = sourceGroup.get(*iter);
44  targetGroup.set(*iter, groupOn);
45  }
46  }
47  }
48 
49  //////////
50 
51  const GroupIndex mTargetIndex;
52  const GroupIndex mSourceIndex;
53 };
54 
55 
56 /// Set membership on or off for the specified group
57 template <typename PointDataTreeT, bool Member>
58 struct SetGroupOp
59 {
60  using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
61  using GroupIndex = AttributeSet::Descriptor::GroupIndex;
62 
63  SetGroupOp(const AttributeSet::Descriptor::GroupIndex& index)
64  : mIndex(index) { }
65 
66  void operator()(const typename LeafManagerT::LeafRange& range) const
67  {
68  for (auto leaf = range.begin(); leaf; ++leaf) {
69 
70  // obtain the group attribute array
71 
72  GroupWriteHandle group(leaf->groupWriteHandle(mIndex));
73 
74  // set the group value
75 
76  group.collapse(Member);
77  }
78  }
79 
80  //////////
81 
82  const GroupIndex& mIndex;
83 }; // struct SetGroupOp
84 
85 
86 template <typename PointDataTreeT, typename PointIndexTreeT, bool Remove>
87 struct SetGroupFromIndexOp
88 {
89  using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
90  using LeafRangeT = typename LeafManagerT::LeafRange;
91  using PointIndexLeafNode = typename PointIndexTreeT::LeafNodeType;
93  using GroupIndex = AttributeSet::Descriptor::GroupIndex;
94  using MembershipArray = std::vector<short>;
95 
96  SetGroupFromIndexOp(const PointIndexTreeT& indexTree,
97  const MembershipArray& membership,
98  const GroupIndex& index)
99  : mIndexTree(indexTree)
100  , mMembership(membership)
101  , mIndex(index) { }
102 
103  void operator()(const typename LeafManagerT::LeafRange& range) const
104  {
105  for (auto leaf = range.begin(); leaf; ++leaf) {
106 
107  // obtain the PointIndexLeafNode (using the origin of the current leaf)
108 
109  const PointIndexLeafNode* pointIndexLeaf = mIndexTree.probeConstLeaf(leaf->origin());
110 
111  if (!pointIndexLeaf) continue;
112 
113  // obtain the group attribute array
114 
115  GroupWriteHandle group(leaf->groupWriteHandle(mIndex));
116 
117  // initialise the attribute storage
118 
119  Index64 index = 0;
120 
121  const IndexArray& indices = pointIndexLeaf->indices();
122 
123  for (const Index64 i: indices) {
124  if (Remove) {
125  group.set(static_cast<Index>(index), mMembership[i]);
126  } else if (mMembership[i] == short(1)) {
127  group.set(static_cast<Index>(index), short(1));
128  }
129  index++;
130  }
131 
132  // attempt to compact the array
133 
134  group.compact();
135  }
136  }
137 
138  //////////
139 
140  const PointIndexTreeT& mIndexTree;
141  const MembershipArray& mMembership;
142  const GroupIndex& mIndex;
143 }; // struct SetGroupFromIndexOp
144 
145 
146 template <typename PointDataTreeT, typename FilterT, typename IterT = typename PointDataTreeT::LeafNodeType::ValueAllCIter>
147 struct SetGroupByFilterOp
148 {
149  using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
150  using LeafRangeT = typename LeafManagerT::LeafRange;
151  using LeafNodeT = typename PointDataTreeT::LeafNodeType;
152  using GroupIndex = AttributeSet::Descriptor::GroupIndex;
153 
154  SetGroupByFilterOp( const GroupIndex& index, const FilterT& filter)
155  : mIndex(index)
156  , mFilter(filter) { }
157 
158  void operator()(const typename LeafManagerT::LeafRange& range) const
159  {
160  for (auto leaf = range.begin(); leaf; ++leaf) {
161 
162  // obtain the group attribute array
163 
164  GroupWriteHandle group(leaf->groupWriteHandle(mIndex));
165 
166  auto iter = leaf->template beginIndex<IterT, FilterT>(mFilter);
167 
168  for (; iter; ++iter) {
169  group.set(*iter, true);
170  }
171 
172  // attempt to compact the array
173 
174  group.compact();
175  }
176  }
177 
178  //////////
179 
180  const GroupIndex& mIndex;
181  const FilterT& mFilter; // beginIndex takes a copy of mFilter
182 }; // struct SetGroupByFilterOp
183 
184 
185 ////////////////////////////////////////
186 
187 
188 } // namespace point_group_internal
189 
190 /// @endcond
191 
192 ////////////////////////////////////////
193 
194 
195 inline void deleteMissingPointGroups( std::vector<std::string>& groups,
196  const AttributeSet::Descriptor& descriptor)
197 {
198  for (auto it = groups.begin(); it != groups.end();) {
199  if (!descriptor.hasGroup(*it)) it = groups.erase(it);
200  else ++it;
201  }
202 }
203 
204 
205 ////////////////////////////////////////
206 
207 
208 template <typename PointDataTreeT>
209 inline void appendGroup(PointDataTreeT& tree, const Name& group)
210 {
211  if (group.empty()) {
212  OPENVDB_THROW(KeyError, "Cannot use an empty group name as a key.");
213  }
214 
215  auto iter = tree.cbeginLeaf();
216 
217  if (!iter) return;
218 
219  const AttributeSet& attributeSet = iter->attributeSet();
220  auto descriptor = attributeSet.descriptorPtr();
221 
222  // don't add if group already exists
223 
224  if (descriptor->hasGroup(group)) return;
225 
226  const bool hasUnusedGroup = descriptor->unusedGroups() > 0;
227 
228  // add a new group attribute if there are no unused groups
229 
230  if (!hasUnusedGroup) {
231 
232  // find a new internal group name
233 
234  const Name groupName = descriptor->uniqueName("__group");
235 
236  descriptor = descriptor->duplicateAppend(groupName, GroupAttributeArray::attributeType());
237  const size_t pos = descriptor->find(groupName);
238 
239  // insert new group attribute
240 
241  tree::LeafManager<PointDataTreeT> leafManager(tree);
242  leafManager.foreach(
243  [&](typename PointDataTreeT::LeafNodeType& leaf, size_t /*idx*/) {
244  auto expected = leaf.attributeSet().descriptorPtr();
245  leaf.appendAttribute(*expected, descriptor, pos);
246  }, /*threaded=*/true
247  );
248  }
249  else {
250  // make the descriptor unique before we modify the group map
251 
252  makeDescriptorUnique(tree);
253  descriptor = attributeSet.descriptorPtr();
254  }
255 
256  // ensure that there are now available groups
257 
258  OPENVDB_ASSERT(descriptor->unusedGroups() > 0);
259 
260  // find next unused offset
261 
262  const size_t offset = descriptor->unusedGroupOffset();
263 
264  // add the group mapping to the descriptor
265 
266  descriptor->setGroup(group, offset);
267 
268  // if there was an unused group then we did not need to append a new attribute, so
269  // we must manually clear membership in the new group as its bits may have been
270  // previously set
271 
272  if (hasUnusedGroup) setGroup(tree, group, false);
273 }
274 
275 
276 ////////////////////////////////////////
277 
278 
279 template <typename PointDataTreeT>
280 inline void appendGroups(PointDataTreeT& tree,
281  const std::vector<Name>& groups)
282 {
283  // TODO: could be more efficient by appending multiple groups at once
284  // instead of one-by-one, however this is likely not that common a use case
285 
286  for (const Name& name : groups) {
287  appendGroup(tree, name);
288  }
289 }
290 
291 
292 ////////////////////////////////////////
293 
294 
295 template <typename PointDataTreeT>
296 inline void dropGroup(PointDataTreeT& tree, const Name& group, const bool compact)
297 {
298  using Descriptor = AttributeSet::Descriptor;
299 
300  if (group.empty()) {
301  OPENVDB_THROW(KeyError, "Cannot use an empty group name as a key.");
302  }
303 
304  auto iter = tree.cbeginLeaf();
305 
306  if (!iter) return;
307 
308  const AttributeSet& attributeSet = iter->attributeSet();
309 
310  // make the descriptor unique before we modify the group map
311 
312  makeDescriptorUnique(tree);
313  Descriptor::Ptr descriptor = attributeSet.descriptorPtr();
314 
315  // now drop the group
316 
317  descriptor->dropGroup(group);
318 
319  if (compact) {
320  compactGroups(tree);
321  }
322 }
323 
324 
325 ////////////////////////////////////////
326 
327 
328 template <typename PointDataTreeT>
329 inline void dropGroups( PointDataTreeT& tree,
330  const std::vector<Name>& groups)
331 {
332  for (const Name& name : groups) {
333  dropGroup(tree, name, /*compact=*/false);
334  }
335 
336  // compaction done once for efficiency
337 
338  compactGroups(tree);
339 }
340 
341 
342 ////////////////////////////////////////
343 
344 
345 template <typename PointDataTreeT>
346 inline void dropGroups( PointDataTreeT& tree)
347 {
348  using Descriptor = AttributeSet::Descriptor;
349 
350  auto iter = tree.cbeginLeaf();
351 
352  if (!iter) return;
353 
354  const AttributeSet& attributeSet = iter->attributeSet();
355 
356  // make the descriptor unique before we modify the group map
357 
358  makeDescriptorUnique(tree);
359  Descriptor::Ptr descriptor = attributeSet.descriptorPtr();
360 
361  descriptor->clearGroups();
362 
363  // find all indices for group attribute arrays
364 
365  std::vector<size_t> indices = attributeSet.groupAttributeIndices();
366 
367  // drop these attributes arrays
368 
369  dropAttributes(tree, indices);
370 }
371 
372 
373 ////////////////////////////////////////
374 
375 
376 template <typename PointDataTreeT>
377 inline void compactGroups(PointDataTreeT& tree)
378 {
379  using Descriptor = AttributeSet::Descriptor;
380  using GroupIndex = Descriptor::GroupIndex;
381  using LeafManagerT = typename tree::template LeafManager<PointDataTreeT>;
382 
383  using point_group_internal::CopyGroupOp;
384 
385  auto iter = tree.cbeginLeaf();
386 
387  if (!iter) return;
388 
389  const AttributeSet& attributeSet = iter->attributeSet();
390 
391  // early exit if not possible to compact
392 
393  if (!attributeSet.descriptor().canCompactGroups()) return;
394 
395  // make the descriptor unique before we modify the group map
396 
397  makeDescriptorUnique(tree);
398  Descriptor::Ptr descriptor = attributeSet.descriptorPtr();
399 
400  // generate a list of group offsets and move them (one-by-one)
401  // TODO: improve this algorithm to move multiple groups per array at once
402  // though this is likely not that common a use case
403 
404  Name sourceName;
405  size_t sourceOffset, targetOffset;
406 
407  while (descriptor->requiresGroupMove(sourceName, sourceOffset, targetOffset)) {
408 
409  const GroupIndex sourceIndex = attributeSet.groupIndex(sourceOffset);
410  const GroupIndex targetIndex = attributeSet.groupIndex(targetOffset);
411 
412  CopyGroupOp<PointDataTreeT> copy(targetIndex, sourceIndex);
413  LeafManagerT leafManager(tree);
414  tbb::parallel_for(leafManager.leafRange(), copy);
415 
416  descriptor->setGroup(sourceName, targetOffset);
417  }
418 
419  // drop unused attribute arrays
420 
421  const std::vector<size_t> indices = attributeSet.groupAttributeIndices();
422 
423  const size_t totalAttributesToDrop = descriptor->unusedGroups() / descriptor->groupBits();
424 
425  OPENVDB_ASSERT(totalAttributesToDrop <= indices.size());
426 
427  const std::vector<size_t> indicesToDrop(indices.end() - totalAttributesToDrop,
428  indices.end());
429 
430  dropAttributes(tree, indicesToDrop);
431 }
432 
433 
434 ////////////////////////////////////////
435 
436 
437 template <typename PointDataTreeT, typename PointIndexTreeT>
438 inline void setGroup( PointDataTreeT& tree,
439  const PointIndexTreeT& indexTree,
440  const std::vector<short>& membership,
441  const Name& group,
442  const bool remove)
443 {
444  using Descriptor = AttributeSet::Descriptor;
445  using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
446  using point_group_internal::SetGroupFromIndexOp;
447 
448  auto iter = tree.cbeginLeaf();
449  if (!iter) return;
450 
451  const AttributeSet& attributeSet = iter->attributeSet();
452  const Descriptor& descriptor = attributeSet.descriptor();
453 
454  if (!descriptor.hasGroup(group)) {
455  OPENVDB_THROW(LookupError, "Group must exist on Tree before defining membership.");
456  }
457 
458  {
459  // Check that that the largest index in the PointIndexTree is smaller than the size
460  // of the membership vector. The index tree will be used to lookup membership
461  // values. If the index tree was constructed with nan positions, this index will
462  // differ from the PointDataTree count
463 
464  using IndexTreeManager = tree::LeafManager<const PointIndexTreeT>;
465  IndexTreeManager leafManager(indexTree);
466 
467  const int64_t max = tbb::parallel_reduce(leafManager.leafRange(), -1,
468  [](const typename IndexTreeManager::LeafRange& range, int64_t value) -> int64_t {
469  for (auto leaf = range.begin(); leaf; ++leaf) {
470  auto it = std::max_element(leaf->indices().begin(), leaf->indices().end());
471  value = std::max(value, static_cast<int64_t>(*it));
472  }
473  return value;
474  },
475  [](const int64_t a, const int64_t b) {
476  return std::max(a, b);
477  }
478  );
479 
480  if (max != -1 && membership.size() <= static_cast<size_t>(max)) {
481  OPENVDB_THROW(IndexError, "Group membership vector size must be larger than "
482  " the maximum index within the provided index tree.");
483  }
484  }
485 
486  const Descriptor::GroupIndex index = attributeSet.groupIndex(group);
487  LeafManagerT leafManager(tree);
488 
489  // set membership
490 
491  if (remove) {
492  SetGroupFromIndexOp<PointDataTreeT, PointIndexTreeT, true>
493  set(indexTree, membership, index);
494  tbb::parallel_for(leafManager.leafRange(), set);
495  }
496  else {
497  SetGroupFromIndexOp<PointDataTreeT, PointIndexTreeT, false>
498  set(indexTree, membership, index);
499  tbb::parallel_for(leafManager.leafRange(), set);
500  }
501 }
502 
503 
504 ////////////////////////////////////////
505 
506 
507 template <typename PointDataTreeT>
508 inline void setGroup( PointDataTreeT& tree,
509  const Name& group,
510  const bool member)
511 {
512  using Descriptor = AttributeSet::Descriptor;
513  using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
514 
515  using point_group_internal::SetGroupOp;
516 
517  auto iter = tree.cbeginLeaf();
518 
519  if (!iter) return;
520 
521  const AttributeSet& attributeSet = iter->attributeSet();
522  const Descriptor& descriptor = attributeSet.descriptor();
523 
524  if (!descriptor.hasGroup(group)) {
525  OPENVDB_THROW(LookupError, "Group must exist on Tree before defining membership.");
526  }
527 
528  const Descriptor::GroupIndex index = attributeSet.groupIndex(group);
529  LeafManagerT leafManager(tree);
530 
531  // set membership based on member variable
532 
533  if (member) tbb::parallel_for(leafManager.leafRange(), SetGroupOp<PointDataTreeT, true>(index));
534  else tbb::parallel_for(leafManager.leafRange(), SetGroupOp<PointDataTreeT, false>(index));
535 }
536 
537 
538 ////////////////////////////////////////
539 
540 
541 template <typename PointDataTreeT, typename FilterT>
542 inline void setGroupByFilter( PointDataTreeT& tree,
543  const Name& group,
544  const FilterT& filter)
545 {
546  using Descriptor = AttributeSet::Descriptor;
547  using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
548 
549  using point_group_internal::SetGroupByFilterOp;
550 
551  auto iter = tree.cbeginLeaf();
552 
553  if (!iter) return;
554 
555  const AttributeSet& attributeSet = iter->attributeSet();
556  const Descriptor& descriptor = attributeSet.descriptor();
557 
558  if (!descriptor.hasGroup(group)) {
559  OPENVDB_THROW(LookupError, "Group must exist on Tree before defining membership.");
560  }
561 
562  const Descriptor::GroupIndex index = attributeSet.groupIndex(group);
563 
564  // set membership using filter
565 
566  SetGroupByFilterOp<PointDataTreeT, FilterT> set(index, filter);
567  LeafManagerT leafManager(tree);
568 
569  tbb::parallel_for(leafManager.leafRange(), set);
570 }
571 
572 
573 ////////////////////////////////////////
574 
575 
576 template <typename PointDataTreeT>
577 inline void setGroupByRandomTarget( PointDataTreeT& tree,
578  const Name& group,
579  const Index64 targetPoints,
580  const unsigned int seed = 0)
581 {
583 
584  RandomFilter filter(tree, targetPoints, seed);
585 
586  setGroupByFilter<PointDataTreeT, RandomFilter>(tree, group, filter);
587 }
588 
589 
590 ////////////////////////////////////////
591 
592 
593 template <typename PointDataTreeT>
594 inline void setGroupByRandomPercentage( PointDataTreeT& tree,
595  const Name& group,
596  const float percentage = 10.0f,
597  const unsigned int seed = 0)
598 {
600 
601  const int currentPoints = static_cast<int>(pointCount(tree));
602  const int targetPoints = int(math::Round((percentage * float(currentPoints))/100.0f));
603 
604  RandomFilter filter(tree, targetPoints, seed);
605 
606  setGroupByFilter<PointDataTreeT, RandomFilter>(tree, group, filter);
607 }
608 
609 } // namespace points
610 } // namespace OPENVDB_VERSION_NAME
611 } // namespace openvdb
612 
613 
614 #endif // OPENVDB_POINTS_POINT_GROUP_IMPL_HAS_BEEN_INCLUDED
Definition: Exceptions.h:60
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
Definition: Exceptions.h:57
void deleteMissingPointGroups(std::vector< std::string > &groups, const AttributeSet::Descriptor &descriptor)
Delete any group that is not present in the Descriptor.
Definition: PointGroupImpl.h:195
uint64_t Index64
Definition: Types.h:53
AttributeSet::Descriptor::Ptr makeDescriptorUnique(PointDataTreeT &tree)
Deep copy the descriptor across all leaf nodes.
Definition: PointDataGrid.h:1586
void dropAttributes(PointDataTreeT &tree, const std::vector< size_t > &indices)
Drops attributes from the VDB tree.
Definition: PointAttributeImpl.h:238
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:110
void appendGroup(PointDataTreeT &tree, const Name &group)
Appends a new empty group to the VDB tree.
Definition: PointGroupImpl.h:209
void appendGroups(PointDataTreeT &tree, const std::vector< Name > &groups)
Appends new empty groups to the VDB tree.
Definition: PointGroupImpl.h:280
void setGroupByRandomTarget(PointDataTreeT &tree, const Name &group, const Index64 targetPoints, const unsigned int seed=0)
Definition: PointGroupImpl.h:577
void setGroupByRandomPercentage(PointDataTreeT &tree, const Name &group, const float percentage=10.0f, const unsigned int seed=0)
Definition: PointGroupImpl.h:594
void dropGroups(PointDataTreeT &tree, const std::vector< Name > &groups)
Drops existing groups from the VDB tree, the tree is compacted after dropping.
Definition: PointGroupImpl.h:329
#define OPENVDB_ASSERT(X)
Definition: Assert.h:41
void compactGroups(PointDataTreeT &tree)
Compacts existing groups of a VDB Tree to use less memory if possible.
Definition: PointGroupImpl.h:377
Index64 pointCount(const PointDataTreeT &tree, const FilterT &filter=NullFilter(), const bool inCoreOnly=false, const bool threaded=true)
Count the total number of points in a PointDataTree.
Definition: PointCountImpl.h:18
DescriptorPtr descriptorPtr() const
Return a pointer to this attribute set&#39;s descriptor, which might be shared with other sets...
Definition: AttributeSet.h:109
Definition: Exceptions.h:13
void setGroup(PointDataTreeT &tree, const PointIndexTreeT &indexTree, const std::vector< short > &membership, const Name &group, const bool remove=false)
Sets group membership from a PointIndexTree-ordered vector.
Definition: PointGroupImpl.h:438
Definition: IndexFilter.h:229
void dropGroup(PointDataTreeT &tree, const Name &group, const bool compact=true)
Drops an existing group from the VDB tree.
Definition: PointGroupImpl.h:296
void foreach(const LeafOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to each leaf node in the LeafManager.
Definition: LeafManager.h:484
void setGroupByFilter(PointDataTreeT &tree, const Name &group, const FilterT &filter)
Sets group membership based on a provided filter.
Definition: PointGroupImpl.h:542
std::vector< size_t > groupAttributeIndices() const
Return the indices of the attribute arrays which are group attribute arrays.
This class manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional auxil...
Definition: LeafManager.h:85
Descriptor & descriptor()
Return a reference to this attribute set&#39;s descriptor, which might be shared with other sets...
Definition: AttributeSet.h:103
std::string Name
Definition: Name.h:19
Util::GroupIndex groupIndex(const Name &groupName) const
Return the group index from the name of the group.
Ordered collection of uniquely-named attribute arrays.
Definition: AttributeSet.h:39
float Round(float x)
Return x rounded to the nearest integer.
Definition: Math.h:819
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
std::vector< Index > IndexArray
Definition: PointMoveImpl.h:88
Definition: Exceptions.h:59
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:218