1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3
4 /// @author Dan Bailey
5 ///
6 /// @file points/PointGroup.h
7 ///
8 /// @brief Point group manipulation in a VDB Point Grid.
9
10 #ifndef OPENVDB_POINTS_POINT_GROUP_HAS_BEEN_INCLUDED
11 #define OPENVDB_POINTS_POINT_GROUP_HAS_BEEN_INCLUDED
12
13 #include <openvdb/openvdb.h>
14
15 #include "IndexIterator.h" // FilterTraits
16 #include "IndexFilter.h" // FilterTraits
17 #include "AttributeSet.h"
18 #include "PointDataGrid.h"
19 #include "PointAttribute.h"
20 #include "PointCount.h"
21
22 #include <tbb/parallel_reduce.h>
23
24 #include <algorithm>
25 #include <random>
26 #include <string>
27 #include <vector>
28
29 namespace openvdb {
30 OPENVDB_USE_VERSION_NAMESPACE
31 namespace OPENVDB_VERSION_NAME {
32 namespace points {
33
34 /// @brief Delete any group that is not present in the Descriptor.
35 ///
36 /// @param groups the vector of group names.
37 /// @param descriptor the descriptor that holds the group map.
38 inline void deleteMissingPointGroups( std::vector<std::string>& groups,
39 const AttributeSet::Descriptor& descriptor);
40
41 /// @brief Appends a new empty group to the VDB tree.
42 ///
43 /// @param tree the PointDataTree to be appended to.
44 /// @param group name of the new group.
45 template <typename PointDataTreeT>
46 inline void appendGroup(PointDataTreeT& tree,
47 const Name& group);
48
49 /// @brief Appends new empty groups to the VDB tree.
50 ///
51 /// @param tree the PointDataTree to be appended to.
52 /// @param groups names of the new groups.
53 template <typename PointDataTreeT>
54 inline void appendGroups(PointDataTreeT& tree,
55 const std::vector<Name>& groups);
56
57 /// @brief Drops an existing group from the VDB tree.
58 ///
59 /// @param tree the PointDataTree to be dropped from.
60 /// @param group name of the group.
61 /// @param compact compact attributes if possible to reduce memory - if dropping
62 /// more than one group, compacting once at the end will be faster
63 template <typename PointDataTreeT>
64 inline void dropGroup( PointDataTreeT& tree,
65 const Name& group,
66 const bool compact = true);
67
68 /// @brief Drops existing groups from the VDB tree, the tree is compacted after dropping.
69 ///
70 /// @param tree the PointDataTree to be dropped from.
71 /// @param groups names of the groups.
72 template <typename PointDataTreeT>
73 inline void dropGroups( PointDataTreeT& tree,
74 const std::vector<Name>& groups);
75
76 /// @brief Drops all existing groups from the VDB tree, the tree is compacted after dropping.
77 ///
78 /// @param tree the PointDataTree to be dropped from.
79 template <typename PointDataTreeT>
80 inline void dropGroups( PointDataTreeT& tree);
81
82 /// @brief Compacts existing groups of a VDB Tree to use less memory if possible.
83 ///
84 /// @param tree the PointDataTree to be compacted.
85 template <typename PointDataTreeT>
86 inline void compactGroups(PointDataTreeT& tree);
87
88 /// @brief Sets group membership from a PointIndexTree-ordered vector.
89 ///
90 /// @param tree the PointDataTree.
91 /// @param indexTree the PointIndexTree.
92 /// @param membership @c 1 if the point is in the group, 0 otherwise.
93 /// @param group the name of the group.
94 /// @param remove if @c true also perform removal of points from the group.
95 ///
96 /// @note vector<bool> is not thread-safe on concurrent write, so use vector<short> instead
97 template <typename PointDataTreeT, typename PointIndexTreeT>
98 inline void setGroup( PointDataTreeT& tree,
99 const PointIndexTreeT& indexTree,
100 const std::vector<short>& membership,
101 const Name& group,
102 const bool remove = false);
103
104 /// @brief Sets membership for the specified group for all points (on/off).
105 ///
106 /// @param tree the PointDataTree.
107 /// @param group the name of the group.
108 /// @param member true / false for membership of the group.
109 template <typename PointDataTreeT>
110 inline void setGroup( PointDataTreeT& tree,
111 const Name& group,
112 const bool member = true);
113
114 /// @brief Sets group membership based on a provided filter.
115 ///
116 /// @param tree the PointDataTree.
117 /// @param group the name of the group.
118 /// @param filter filter data that is used to create a per-leaf filter
119 template <typename PointDataTreeT, typename FilterT>
120 inline void setGroupByFilter( PointDataTreeT& tree,
121 const Name& group,
122 const FilterT& filter);
123
124
125 ////////////////////////////////////////
126
127 /// @cond OPENVDB_DOCS_INTERNAL
128
129 namespace point_group_internal {
130
131
132 /// Copy a group attribute value from one group offset to another
133 template<typename PointDataTreeType>
134 struct CopyGroupOp {
135
136 using LeafManagerT = typename tree::LeafManager<PointDataTreeType>;
137 using LeafRangeT = typename LeafManagerT::LeafRange;
138 using GroupIndex = AttributeSet::Descriptor::GroupIndex;
139
CopyGroupOpCopyGroupOp140 CopyGroupOp(const GroupIndex& targetIndex,
141 const GroupIndex& sourceIndex)
142 : mTargetIndex(targetIndex)
143 , mSourceIndex(sourceIndex) { }
144
operatorCopyGroupOp145 void operator()(const typename LeafManagerT::LeafRange& range) const {
146
147 for (auto leaf = range.begin(); leaf; ++leaf) {
148
149 GroupHandle sourceGroup = leaf->groupHandle(mSourceIndex);
150 GroupWriteHandle targetGroup = leaf->groupWriteHandle(mTargetIndex);
151
152 for (auto iter = leaf->beginIndexAll(); iter; ++iter) {
153 const bool groupOn = sourceGroup.get(*iter);
154 targetGroup.set(*iter, groupOn);
155 }
156 }
157 }
158
159 //////////
160
161 const GroupIndex mTargetIndex;
162 const GroupIndex mSourceIndex;
163 };
164
165
166 /// Set membership on or off for the specified group
167 template <typename PointDataTreeT, bool Member>
168 struct SetGroupOp
169 {
170 using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
171 using GroupIndex = AttributeSet::Descriptor::GroupIndex;
172
SetGroupOpSetGroupOp173 SetGroupOp(const AttributeSet::Descriptor::GroupIndex& index)
174 : mIndex(index) { }
175
operatorSetGroupOp176 void operator()(const typename LeafManagerT::LeafRange& range) const
177 {
178 for (auto leaf = range.begin(); leaf; ++leaf) {
179
180 // obtain the group attribute array
181
182 GroupWriteHandle group(leaf->groupWriteHandle(mIndex));
183
184 // set the group value
185
186 group.collapse(Member);
187 }
188 }
189
190 //////////
191
192 const GroupIndex& mIndex;
193 }; // struct SetGroupOp
194
195
196 template <typename PointDataTreeT, typename PointIndexTreeT, bool Remove>
197 struct SetGroupFromIndexOp
198 {
199 using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
200 using LeafRangeT = typename LeafManagerT::LeafRange;
201 using PointIndexLeafNode = typename PointIndexTreeT::LeafNodeType;
202 using IndexArray = typename PointIndexLeafNode::IndexArray;
203 using GroupIndex = AttributeSet::Descriptor::GroupIndex;
204 using MembershipArray = std::vector<short>;
205
SetGroupFromIndexOpSetGroupFromIndexOp206 SetGroupFromIndexOp(const PointIndexTreeT& indexTree,
207 const MembershipArray& membership,
208 const GroupIndex& index)
209 : mIndexTree(indexTree)
210 , mMembership(membership)
211 , mIndex(index) { }
212
operatorSetGroupFromIndexOp213 void operator()(const typename LeafManagerT::LeafRange& range) const
214 {
215 for (auto leaf = range.begin(); leaf; ++leaf) {
216
217 // obtain the PointIndexLeafNode (using the origin of the current leaf)
218
219 const PointIndexLeafNode* pointIndexLeaf = mIndexTree.probeConstLeaf(leaf->origin());
220
221 if (!pointIndexLeaf) continue;
222
223 // obtain the group attribute array
224
225 GroupWriteHandle group(leaf->groupWriteHandle(mIndex));
226
227 // initialise the attribute storage
228
229 Index64 index = 0;
230
231 const IndexArray& indices = pointIndexLeaf->indices();
232
233 for (const Index64 i: indices) {
234 if (Remove) {
235 group.set(static_cast<Index>(index), mMembership[i]);
236 } else if (mMembership[i] == short(1)) {
237 group.set(static_cast<Index>(index), short(1));
238 }
239 index++;
240 }
241
242 // attempt to compact the array
243
244 group.compact();
245 }
246 }
247
248 //////////
249
250 const PointIndexTreeT& mIndexTree;
251 const MembershipArray& mMembership;
252 const GroupIndex& mIndex;
253 }; // struct SetGroupFromIndexOp
254
255
256 template <typename PointDataTreeT, typename FilterT, typename IterT = typename PointDataTreeT::LeafNodeType::ValueAllCIter>
257 struct SetGroupByFilterOp
258 {
259 using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
260 using LeafRangeT = typename LeafManagerT::LeafRange;
261 using LeafNodeT = typename PointDataTreeT::LeafNodeType;
262 using GroupIndex = AttributeSet::Descriptor::GroupIndex;
263
SetGroupByFilterOpSetGroupByFilterOp264 SetGroupByFilterOp( const GroupIndex& index, const FilterT& filter)
265 : mIndex(index)
266 , mFilter(filter) { }
267
operatorSetGroupByFilterOp268 void operator()(const typename LeafManagerT::LeafRange& range) const
269 {
270 for (auto leaf = range.begin(); leaf; ++leaf) {
271
272 // obtain the group attribute array
273
274 GroupWriteHandle group(leaf->groupWriteHandle(mIndex));
275
276 auto iter = leaf->template beginIndex<IterT, FilterT>(mFilter);
277
278 for (; iter; ++iter) {
279 group.set(*iter, true);
280 }
281
282 // attempt to compact the array
283
284 group.compact();
285 }
286 }
287
288 //////////
289
290 const GroupIndex& mIndex;
291 const FilterT& mFilter; // beginIndex takes a copy of mFilter
292 }; // struct SetGroupByFilterOp
293
294
295 ////////////////////////////////////////
296
297
298 } // namespace point_group_internal
299
300 /// @endcond
301
302 ////////////////////////////////////////
303
304
deleteMissingPointGroups(std::vector<std::string> & groups,const AttributeSet::Descriptor & descriptor)305 inline void deleteMissingPointGroups( std::vector<std::string>& groups,
306 const AttributeSet::Descriptor& descriptor)
307 {
308 for (auto it = groups.begin(); it != groups.end();) {
309 if (!descriptor.hasGroup(*it)) it = groups.erase(it);
310 else ++it;
311 }
312 }
313
314
315 ////////////////////////////////////////
316
317
318 template <typename PointDataTreeT>
appendGroup(PointDataTreeT & tree,const Name & group)319 inline void appendGroup(PointDataTreeT& tree, const Name& group)
320 {
321 if (group.empty()) {
322 OPENVDB_THROW(KeyError, "Cannot use an empty group name as a key.");
323 }
324
325 auto iter = tree.cbeginLeaf();
326
327 if (!iter) return;
328
329 const AttributeSet& attributeSet = iter->attributeSet();
330 auto descriptor = attributeSet.descriptorPtr();
331
332 // don't add if group already exists
333
334 if (descriptor->hasGroup(group)) return;
335
336 const bool hasUnusedGroup = descriptor->unusedGroups() > 0;
337
338 // add a new group attribute if there are no unused groups
339
340 if (!hasUnusedGroup) {
341
342 // find a new internal group name
343
344 const Name groupName = descriptor->uniqueName("__group");
345
346 descriptor = descriptor->duplicateAppend(groupName, GroupAttributeArray::attributeType());
347 const size_t pos = descriptor->find(groupName);
348
349 // insert new group attribute
350
351 tree::LeafManager<PointDataTreeT> leafManager(tree);
352 leafManager.foreach(
353 [&](typename PointDataTreeT::LeafNodeType& leaf, size_t /*idx*/) {
354 auto expected = leaf.attributeSet().descriptorPtr();
355 leaf.appendAttribute(*expected, descriptor, pos);
356 }, /*threaded=*/true
357 );
358 }
359 else {
360 // make the descriptor unique before we modify the group map
361
362 makeDescriptorUnique(tree);
363 descriptor = attributeSet.descriptorPtr();
364 }
365
366 // ensure that there are now available groups
367
368 assert(descriptor->unusedGroups() > 0);
369
370 // find next unused offset
371
372 const size_t offset = descriptor->unusedGroupOffset();
373
374 // add the group mapping to the descriptor
375
376 descriptor->setGroup(group, offset);
377
378 // if there was an unused group then we did not need to append a new attribute, so
379 // we must manually clear membership in the new group as its bits may have been
380 // previously set
381
382 if (hasUnusedGroup) setGroup(tree, group, false);
383 }
384
385
386 ////////////////////////////////////////
387
388
389 template <typename PointDataTreeT>
appendGroups(PointDataTreeT & tree,const std::vector<Name> & groups)390 inline void appendGroups(PointDataTreeT& tree,
391 const std::vector<Name>& groups)
392 {
393 // TODO: could be more efficient by appending multiple groups at once
394 // instead of one-by-one, however this is likely not that common a use case
395
396 for (const Name& name : groups) {
397 appendGroup(tree, name);
398 }
399 }
400
401
402 ////////////////////////////////////////
403
404
405 template <typename PointDataTreeT>
dropGroup(PointDataTreeT & tree,const Name & group,const bool compact)406 inline void dropGroup(PointDataTreeT& tree, const Name& group, const bool compact)
407 {
408 using Descriptor = AttributeSet::Descriptor;
409
410 if (group.empty()) {
411 OPENVDB_THROW(KeyError, "Cannot use an empty group name as a key.");
412 }
413
414 auto iter = tree.cbeginLeaf();
415
416 if (!iter) return;
417
418 const AttributeSet& attributeSet = iter->attributeSet();
419
420 // make the descriptor unique before we modify the group map
421
422 makeDescriptorUnique(tree);
423 Descriptor::Ptr descriptor = attributeSet.descriptorPtr();
424
425 // now drop the group
426
427 descriptor->dropGroup(group);
428
429 if (compact) {
430 compactGroups(tree);
431 }
432 }
433
434
435 ////////////////////////////////////////
436
437
438 template <typename PointDataTreeT>
dropGroups(PointDataTreeT & tree,const std::vector<Name> & groups)439 inline void dropGroups( PointDataTreeT& tree,
440 const std::vector<Name>& groups)
441 {
442 for (const Name& name : groups) {
443 dropGroup(tree, name, /*compact=*/false);
444 }
445
446 // compaction done once for efficiency
447
448 compactGroups(tree);
449 }
450
451
452 ////////////////////////////////////////
453
454
455 template <typename PointDataTreeT>
dropGroups(PointDataTreeT & tree)456 inline void dropGroups( PointDataTreeT& tree)
457 {
458 using Descriptor = AttributeSet::Descriptor;
459
460 auto iter = tree.cbeginLeaf();
461
462 if (!iter) return;
463
464 const AttributeSet& attributeSet = iter->attributeSet();
465
466 // make the descriptor unique before we modify the group map
467
468 makeDescriptorUnique(tree);
469 Descriptor::Ptr descriptor = attributeSet.descriptorPtr();
470
471 descriptor->clearGroups();
472
473 // find all indices for group attribute arrays
474
475 std::vector<size_t> indices = attributeSet.groupAttributeIndices();
476
477 // drop these attributes arrays
478
479 dropAttributes(tree, indices);
480 }
481
482
483 ////////////////////////////////////////
484
485
486 template <typename PointDataTreeT>
compactGroups(PointDataTreeT & tree)487 inline void compactGroups(PointDataTreeT& tree)
488 {
489 using Descriptor = AttributeSet::Descriptor;
490 using GroupIndex = Descriptor::GroupIndex;
491 using LeafManagerT = typename tree::template LeafManager<PointDataTreeT>;
492
493 using point_group_internal::CopyGroupOp;
494
495 auto iter = tree.cbeginLeaf();
496
497 if (!iter) return;
498
499 const AttributeSet& attributeSet = iter->attributeSet();
500
501 // early exit if not possible to compact
502
503 if (!attributeSet.descriptor().canCompactGroups()) return;
504
505 // make the descriptor unique before we modify the group map
506
507 makeDescriptorUnique(tree);
508 Descriptor::Ptr descriptor = attributeSet.descriptorPtr();
509
510 // generate a list of group offsets and move them (one-by-one)
511 // TODO: improve this algorithm to move multiple groups per array at once
512 // though this is likely not that common a use case
513
514 Name sourceName;
515 size_t sourceOffset, targetOffset;
516
517 while (descriptor->requiresGroupMove(sourceName, sourceOffset, targetOffset)) {
518
519 const GroupIndex sourceIndex = attributeSet.groupIndex(sourceOffset);
520 const GroupIndex targetIndex = attributeSet.groupIndex(targetOffset);
521
522 CopyGroupOp<PointDataTreeT> copy(targetIndex, sourceIndex);
523 LeafManagerT leafManager(tree);
524 tbb::parallel_for(leafManager.leafRange(), copy);
525
526 descriptor->setGroup(sourceName, targetOffset);
527 }
528
529 // drop unused attribute arrays
530
531 const std::vector<size_t> indices = attributeSet.groupAttributeIndices();
532
533 const size_t totalAttributesToDrop = descriptor->unusedGroups() / descriptor->groupBits();
534
535 assert(totalAttributesToDrop <= indices.size());
536
537 const std::vector<size_t> indicesToDrop(indices.end() - totalAttributesToDrop,
538 indices.end());
539
540 dropAttributes(tree, indicesToDrop);
541 }
542
543
544 ////////////////////////////////////////
545
546
547 template <typename PointDataTreeT, typename PointIndexTreeT>
setGroup(PointDataTreeT & tree,const PointIndexTreeT & indexTree,const std::vector<short> & membership,const Name & group,const bool remove)548 inline void setGroup( PointDataTreeT& tree,
549 const PointIndexTreeT& indexTree,
550 const std::vector<short>& membership,
551 const Name& group,
552 const bool remove)
553 {
554 using Descriptor = AttributeSet::Descriptor;
555 using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
556 using point_group_internal::SetGroupFromIndexOp;
557
558 auto iter = tree.cbeginLeaf();
559 if (!iter) return;
560
561 const AttributeSet& attributeSet = iter->attributeSet();
562 const Descriptor& descriptor = attributeSet.descriptor();
563
564 if (!descriptor.hasGroup(group)) {
565 OPENVDB_THROW(LookupError, "Group must exist on Tree before defining membership.");
566 }
567
568 {
569 // Check that that the largest index in the PointIndexTree is smaller than the size
570 // of the membership vector. The index tree will be used to lookup membership
571 // values. If the index tree was constructed with nan positions, this index will
572 // differ from the PointDataTree count
573
574 using IndexTreeManager = tree::LeafManager<const PointIndexTreeT>;
575 IndexTreeManager leafManager(indexTree);
576
577 const int64_t max = tbb::parallel_reduce(leafManager.leafRange(), -1,
578 [](const typename IndexTreeManager::LeafRange& range, int64_t value) -> int64_t {
579 for (auto leaf = range.begin(); leaf; ++leaf) {
580 auto it = std::max_element(leaf->indices().begin(), leaf->indices().end());
581 value = std::max(value, static_cast<int64_t>(*it));
582 }
583 return value;
584 },
585 [](const int64_t a, const int64_t b) {
586 return std::max(a, b);
587 }
588 );
589
590 if (max != -1 && membership.size() <= static_cast<size_t>(max)) {
591 OPENVDB_THROW(IndexError, "Group membership vector size must be larger than "
592 " the maximum index within the provided index tree.");
593 }
594 }
595
596 const Descriptor::GroupIndex index = attributeSet.groupIndex(group);
597 LeafManagerT leafManager(tree);
598
599 // set membership
600
601 if (remove) {
602 SetGroupFromIndexOp<PointDataTreeT, PointIndexTreeT, true>
603 set(indexTree, membership, index);
604 tbb::parallel_for(leafManager.leafRange(), set);
605 }
606 else {
607 SetGroupFromIndexOp<PointDataTreeT, PointIndexTreeT, false>
608 set(indexTree, membership, index);
609 tbb::parallel_for(leafManager.leafRange(), set);
610 }
611 }
612
613
614 ////////////////////////////////////////
615
616
617 template <typename PointDataTreeT>
setGroup(PointDataTreeT & tree,const Name & group,const bool member)618 inline void setGroup( PointDataTreeT& tree,
619 const Name& group,
620 const bool member)
621 {
622 using Descriptor = AttributeSet::Descriptor;
623 using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
624
625 using point_group_internal::SetGroupOp;
626
627 auto iter = tree.cbeginLeaf();
628
629 if (!iter) return;
630
631 const AttributeSet& attributeSet = iter->attributeSet();
632 const Descriptor& descriptor = attributeSet.descriptor();
633
634 if (!descriptor.hasGroup(group)) {
635 OPENVDB_THROW(LookupError, "Group must exist on Tree before defining membership.");
636 }
637
638 const Descriptor::GroupIndex index = attributeSet.groupIndex(group);
639 LeafManagerT leafManager(tree);
640
641 // set membership based on member variable
642
643 if (member) tbb::parallel_for(leafManager.leafRange(), SetGroupOp<PointDataTreeT, true>(index));
644 else tbb::parallel_for(leafManager.leafRange(), SetGroupOp<PointDataTreeT, false>(index));
645 }
646
647
648 ////////////////////////////////////////
649
650
651 template <typename PointDataTreeT, typename FilterT>
setGroupByFilter(PointDataTreeT & tree,const Name & group,const FilterT & filter)652 inline void setGroupByFilter( PointDataTreeT& tree,
653 const Name& group,
654 const FilterT& filter)
655 {
656 using Descriptor = AttributeSet::Descriptor;
657 using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
658
659 using point_group_internal::SetGroupByFilterOp;
660
661 auto iter = tree.cbeginLeaf();
662
663 if (!iter) return;
664
665 const AttributeSet& attributeSet = iter->attributeSet();
666 const Descriptor& descriptor = attributeSet.descriptor();
667
668 if (!descriptor.hasGroup(group)) {
669 OPENVDB_THROW(LookupError, "Group must exist on Tree before defining membership.");
670 }
671
672 const Descriptor::GroupIndex index = attributeSet.groupIndex(group);
673
674 // set membership using filter
675
676 SetGroupByFilterOp<PointDataTreeT, FilterT> set(index, filter);
677 LeafManagerT leafManager(tree);
678
679 tbb::parallel_for(leafManager.leafRange(), set);
680 }
681
682
683 ////////////////////////////////////////
684
685
686 template <typename PointDataTreeT>
687 inline void setGroupByRandomTarget( PointDataTreeT& tree,
688 const Name& group,
689 const Index64 targetPoints,
690 const unsigned int seed = 0)
691 {
692 using RandomFilter = RandomLeafFilter<PointDataTreeT, std::mt19937>;
693
694 RandomFilter filter(tree, targetPoints, seed);
695
696 setGroupByFilter<PointDataTreeT, RandomFilter>(tree, group, filter);
697 }
698
699
700 ////////////////////////////////////////
701
702
703 template <typename PointDataTreeT>
704 inline void setGroupByRandomPercentage( PointDataTreeT& tree,
705 const Name& group,
706 const float percentage = 10.0f,
707 const unsigned int seed = 0)
708 {
709 using RandomFilter = RandomLeafFilter<PointDataTreeT, std::mt19937>;
710
711 const int currentPoints = static_cast<int>(pointCount(tree));
712 const int targetPoints = int(math::Round((percentage * float(currentPoints))/100.0f));
713
714 RandomFilter filter(tree, targetPoints, seed);
715
716 setGroupByFilter<PointDataTreeT, RandomFilter>(tree, group, filter);
717 }
718
719
720 ////////////////////////////////////////
721
722
723 } // namespace points
724 } // namespace OPENVDB_VERSION_NAME
725 } // namespace openvdb
726
727
728 #endif // OPENVDB_POINTS_POINT_GROUP_HAS_BEEN_INCLUDED
729