1 // Copyright Contributors to the OpenVDB Project 2 // SPDX-License-Identifier: MPL-2.0 3 // 4 /// @file tree/TreeIterator.h 5 6 #ifndef OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED 7 #define OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED 8 9 #include <tbb/blocked_range.h> 10 #include <tbb/parallel_for.h> 11 #include <openvdb/version.h> 12 #include <openvdb/Types.h> 13 #include <algorithm> 14 #include <sstream> 15 #include <string> 16 #include <type_traits> 17 18 // Prior to 0.96.1, depth-bounded value iterators always descended to the leaf level 19 // and iterated past leaf nodes. Now, they never descend past the maximum depth. 20 // Comment out the following line to restore the older, less-efficient behavior: 21 #define ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION 22 23 24 namespace openvdb { 25 OPENVDB_USE_VERSION_NAMESPACE 26 namespace OPENVDB_VERSION_NAME { 27 namespace tree { 28 29 namespace iter { 30 31 template<typename HeadT, int HeadLevel> 32 struct InvertedTree { 33 using SubtreeT = typename InvertedTree<typename HeadT::ChildNodeType, HeadLevel-1>::Type; 34 using Type = typename SubtreeT::template Append<HeadT>; 35 }; 36 template<typename HeadT> 37 struct InvertedTree<HeadT, /*HeadLevel=*/1> { 38 using Type = TypeList<typename HeadT::ChildNodeType, HeadT>; 39 }; 40 41 } // namespace iter 42 43 44 //////////////////////////////////////// 45 46 47 /// IterTraits provides the following for iterators of the standard types, 48 /// i.e., for {Child,Value}{On,Off,All}{Iter,CIter}: 49 /// - a NodeConverter template to convert an iterator for one type of node 50 /// to an iterator of the same type for another type of node; for example, 51 /// IterTraits<RootNode, RootNode::ValueOnIter>::NodeConverter<LeafNode>::Type 52 /// is synonymous with LeafNode::ValueOnIter. 53 /// - a begin(node) function that returns a begin iterator for a node of arbitrary type; 54 /// for example, IterTraits<LeafNode, LeafNode::ValueOnIter>::begin(leaf) returns 55 /// leaf.beginValueOn() 56 /// - a getChild() function that returns a pointer to the child node to which the iterator 57 /// is currently pointing (always null if the iterator is a Value iterator) 58 template<typename NodeT, typename IterT> 59 struct IterTraits 60 { 61 template<typename ChildT> static ChildT* getChild(const IterT&) { return nullptr; } 62 }; 63 64 template<typename NodeT> 65 struct IterTraits<NodeT, typename NodeT::ChildOnIter> 66 { 67 using IterT = typename NodeT::ChildOnIter; 68 static IterT begin(NodeT& node) { return node.beginChildOn(); } 69 template<typename ChildT> static ChildT* getChild(const IterT& iter) { 70 return &iter.getValue(); 71 } 72 template<typename OtherNodeT> struct NodeConverter { 73 using Type = typename OtherNodeT::ChildOnIter; 74 }; 75 }; 76 77 template<typename NodeT> 78 struct IterTraits<NodeT, typename NodeT::ChildOnCIter> 79 { 80 using IterT = typename NodeT::ChildOnCIter; 81 static IterT begin(const NodeT& node) { return node.cbeginChildOn(); } 82 template<typename ChildT> static const ChildT* getChild(const IterT& iter) { 83 return &iter.getValue(); 84 } 85 template<typename OtherNodeT> struct NodeConverter { 86 using Type = typename OtherNodeT::ChildOnCIter; 87 }; 88 }; 89 90 template<typename NodeT> 91 struct IterTraits<NodeT, typename NodeT::ChildOffIter> 92 { 93 using IterT = typename NodeT::ChildOffIter; 94 static IterT begin(NodeT& node) { return node.beginChildOff(); } 95 template<typename OtherNodeT> struct NodeConverter { 96 using Type = typename OtherNodeT::ChildOffIter; 97 }; 98 }; 99 100 template<typename NodeT> 101 struct IterTraits<NodeT, typename NodeT::ChildOffCIter> 102 { 103 using IterT = typename NodeT::ChildOffCIter; 104 static IterT begin(const NodeT& node) { return node.cbeginChildOff(); } 105 template<typename OtherNodeT> struct NodeConverter { 106 using Type = typename OtherNodeT::ChildOffCIter; 107 }; 108 }; 109 110 template<typename NodeT> 111 struct IterTraits<NodeT, typename NodeT::ChildAllIter> 112 { 113 using IterT = typename NodeT::ChildAllIter; 114 static IterT begin(NodeT& node) { return node.beginChildAll(); } 115 template<typename ChildT> static ChildT* getChild(const IterT& iter) { 116 typename IterT::NonConstValueType val; 117 return iter.probeChild(val); 118 } 119 template<typename OtherNodeT> struct NodeConverter { 120 using Type = typename OtherNodeT::ChildAllIter; 121 }; 122 }; 123 124 template<typename NodeT> 125 struct IterTraits<NodeT, typename NodeT::ChildAllCIter> 126 { 127 using IterT = typename NodeT::ChildAllCIter; 128 static IterT begin(const NodeT& node) { return node.cbeginChildAll(); } 129 template<typename ChildT> static ChildT* getChild(const IterT& iter) { 130 typename IterT::NonConstValueType val; 131 return iter.probeChild(val); 132 } 133 template<typename OtherNodeT> struct NodeConverter { 134 using Type = typename OtherNodeT::ChildAllCIter; 135 }; 136 }; 137 138 template<typename NodeT> 139 struct IterTraits<NodeT, typename NodeT::ValueOnIter> 140 { 141 using IterT = typename NodeT::ValueOnIter; 142 static IterT begin(NodeT& node) { return node.beginValueOn(); } 143 template<typename OtherNodeT> struct NodeConverter { 144 using Type = typename OtherNodeT::ValueOnIter; 145 }; 146 }; 147 148 template<typename NodeT> 149 struct IterTraits<NodeT, typename NodeT::ValueOnCIter> 150 { 151 using IterT = typename NodeT::ValueOnCIter; 152 static IterT begin(const NodeT& node) { return node.cbeginValueOn(); } 153 template<typename OtherNodeT> struct NodeConverter { 154 using Type = typename OtherNodeT::ValueOnCIter; 155 }; 156 }; 157 158 template<typename NodeT> 159 struct IterTraits<NodeT, typename NodeT::ValueOffIter> 160 { 161 using IterT = typename NodeT::ValueOffIter; 162 static IterT begin(NodeT& node) { return node.beginValueOff(); } 163 template<typename OtherNodeT> struct NodeConverter { 164 using Type = typename OtherNodeT::ValueOffIter; 165 }; 166 }; 167 168 template<typename NodeT> 169 struct IterTraits<NodeT, typename NodeT::ValueOffCIter> 170 { 171 using IterT = typename NodeT::ValueOffCIter; 172 static IterT begin(const NodeT& node) { return node.cbeginValueOff(); } 173 template<typename OtherNodeT> struct NodeConverter { 174 using Type = typename OtherNodeT::ValueOffCIter; 175 }; 176 }; 177 178 template<typename NodeT> 179 struct IterTraits<NodeT, typename NodeT::ValueAllIter> 180 { 181 using IterT = typename NodeT::ValueAllIter; 182 static IterT begin(NodeT& node) { return node.beginValueAll(); } 183 template<typename OtherNodeT> struct NodeConverter { 184 using Type = typename OtherNodeT::ValueAllIter; 185 }; 186 }; 187 188 template<typename NodeT> 189 struct IterTraits<NodeT, typename NodeT::ValueAllCIter> 190 { 191 using IterT = typename NodeT::ValueAllCIter; 192 static IterT begin(const NodeT& node) { return node.cbeginValueAll(); } 193 template<typename OtherNodeT> struct NodeConverter { 194 using Type = typename OtherNodeT::ValueAllCIter; 195 }; 196 }; 197 198 199 //////////////////////////////////////// 200 201 202 /// @brief An IterListItem is an element of a compile-time linked list of iterators 203 /// to nodes of different types. 204 /// 205 /// The list is constructed by traversing the template hierarchy of a Tree in reverse order, 206 /// so typically the elements will be a LeafNode iterator of some type (e.g., ValueOnCIter), 207 /// followed by one or more InternalNode iterators of the same type, followed by a RootNode 208 /// iterator of the same type. 209 /// 210 /// The length of the list is fixed at compile time, and because it is implemented using 211 /// nested, templated classes, much of the list traversal logic can be optimized away. 212 template<typename PrevItemT, typename NodeVecT, size_t VecSize, Index _Level> 213 class IterListItem 214 { 215 public: 216 /// The type of iterator stored in the previous list item 217 using PrevIterT = typename PrevItemT::IterT; 218 /// The type of node (non-const) whose iterator is stored in this list item 219 using _NodeT = typename NodeVecT::Front; 220 /// The type of iterator stored in this list item (e.g., InternalNode::ValueOnCIter) 221 using IterT = typename IterTraits<typename PrevIterT::NonConstNodeType, PrevIterT>::template 222 NodeConverter<_NodeT>::Type; 223 224 /// The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>) 225 using NodeT = typename IterT::NodeType; 226 /// The type of the node with const qualifiers removed ("Non-Const") 227 using NCNodeT = typename IterT::NonConstNodeType; 228 /// The type of value (with const qualifiers removed) to which the iterator points 229 using NCValueT = typename IterT::NonConstValueType; 230 /// NodeT's child node type, with the same constness (e.g., const InternalNode<...>) 231 using ChildT = typename CopyConstness<NodeT, typename NodeT::ChildNodeType>::Type; 232 /// NodeT's child node type with const qualifiers removed 233 using NCChildT = typename CopyConstness<NCNodeT, typename NCNodeT::ChildNodeType>::Type; 234 using ITraits = IterTraits<NCNodeT, IterT>; 235 /// NodeT's level in its tree (0 = LeafNode) 236 static const Index Level = _Level; 237 238 IterListItem(PrevItemT* prev): mNext(this), mPrev(prev) {} 239 240 IterListItem(const IterListItem& other): 241 mIter(other.mIter), mNext(other.mNext), mPrev(nullptr) {} 242 IterListItem& operator=(const IterListItem& other) 243 { 244 if (&other != this) { 245 mIter = other.mIter; 246 mNext = other.mNext; 247 mPrev = nullptr; ///< @note external call to updateBackPointers() required 248 } 249 return *this; 250 } 251 252 void updateBackPointers(PrevItemT* prev) { mPrev = prev; mNext.updateBackPointers(this); } 253 254 void setIter(const IterT& iter) { mIter = iter; } 255 template<typename OtherIterT> 256 void setIter(const OtherIterT& iter) { mNext.setIter(iter); } 257 258 /// Return the node over which this list element's iterator iterates. 259 void getNode(Index lvl, NodeT*& node) const 260 { 261 node = (lvl <= Level) ? mIter.getParentNode() : nullptr; 262 } 263 /// Return the node over which one of the following list elements' iterator iterates. 264 template<typename OtherNodeT> 265 void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); } 266 267 /// @brief Initialize the iterator for level @a lvl of the tree with the node 268 /// over which the corresponding iterator of @a otherListItem is iterating. 269 /// 270 /// For example, if @a otherListItem contains a LeafNode::ValueOnIter, 271 /// initialize this list's leaf iterator with the same LeafNode. 272 template<typename OtherIterListItemT> 273 void initLevel(Index lvl, OtherIterListItemT& otherListItem) 274 { 275 if (lvl == Level) { 276 const NodeT* node = nullptr; 277 otherListItem.getNode(lvl, node); 278 mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node)); 279 } else { 280 // Forward to one of the following list elements. 281 mNext.initLevel(lvl, otherListItem); 282 } 283 } 284 285 /// Return The table offset of the iterator at level @a lvl of the tree. 286 Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : mNext.pos(lvl); } 287 288 /// Return @c true if the iterator at level @a lvl of the tree has not yet reached its end. 289 bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : mNext.test(lvl); } 290 291 /// Increment the iterator at level @a lvl of the tree. 292 bool next(Index lvl) { return (lvl == Level) ? mIter.next() : mNext.next(lvl); } 293 294 /// @brief If the iterator at level @a lvl of the tree points to a child node, 295 /// initialize the next iterator in this list with that child node. 296 bool down(Index lvl) 297 { 298 if (lvl == Level && mPrev != nullptr && mIter) { 299 if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) { 300 mPrev->setIter(PrevItemT::ITraits::begin(*child)); 301 return true; 302 } 303 } 304 return (lvl > Level) ? mNext.down(lvl) : false; 305 } 306 307 /// @brief Return the global coordinates of the voxel or tile to which the iterator 308 /// at level @a lvl of the tree is currently pointing. 309 Coord getCoord(Index lvl) const 310 { 311 return (lvl == Level) ? mIter.getCoord() : mNext.getCoord(lvl); 312 } 313 Index getChildDim(Index lvl) const 314 { 315 return (lvl == Level) ? NodeT::getChildDim() : mNext.getChildDim(lvl); 316 } 317 /// Return the number of (virtual) voxels spanned by a tile value or child node 318 Index64 getVoxelCount(Index lvl) const 319 { 320 return (lvl == Level) ? ChildT::NUM_VOXELS : mNext.getVoxelCount(lvl); 321 } 322 323 /// Return @c true if the iterator at level @a lvl of the tree points to an active value. 324 bool isValueOn(Index lvl) const 325 { 326 return (lvl == Level) ? mIter.isValueOn() : mNext.isValueOn(lvl); 327 } 328 329 /// Return the value to which the iterator at level @a lvl of the tree points. 330 const NCValueT& getValue(Index lvl) const 331 { 332 if (lvl == Level) return mIter.getValue(); 333 return mNext.getValue(lvl); 334 } 335 336 /// @brief Set the value (to @a val) to which the iterator at level @a lvl 337 /// of the tree points and mark the value as active. 338 /// @note Not valid when @c IterT is a const iterator type 339 void setValue(Index lvl, const NCValueT& val) const 340 { 341 if (lvl == Level) mIter.setValue(val); else mNext.setValue(lvl, val); 342 } 343 /// @brief Set the value (to @a val) to which the iterator at level @a lvl of the tree 344 /// points and mark the value as active if @a on is @c true, or inactive otherwise. 345 /// @note Not valid when @c IterT is a const iterator type 346 void setValueOn(Index lvl, bool on = true) const 347 { 348 if (lvl == Level) mIter.setValueOn(on); else mNext.setValueOn(lvl, on); 349 } 350 /// @brief Mark the value to which the iterator at level @a lvl of the tree points 351 /// as inactive. 352 /// @note Not valid when @c IterT is a const iterator type 353 void setValueOff(Index lvl) const 354 { 355 if (lvl == Level) mIter.setValueOff(); else mNext.setValueOff(lvl); 356 } 357 358 /// @brief Apply a functor to the item to which this iterator is pointing. 359 /// @note Not valid when @c IterT is a const iterator type 360 template<typename ModifyOp> 361 void modifyValue(Index lvl, const ModifyOp& op) const 362 { 363 if (lvl == Level) mIter.modifyValue(op); else mNext.modifyValue(lvl, op); 364 } 365 366 private: 367 using RestT = typename NodeVecT::PopFront; // NodeVecT minus its first item 368 using NextItem = IterListItem<IterListItem, RestT, VecSize - 1, Level + 1>; 369 370 IterT mIter; 371 NextItem mNext; 372 PrevItemT* mPrev; 373 }; 374 375 376 /// The initial element of a compile-time linked list of iterators to nodes of different types 377 template<typename PrevItemT, typename NodeVecT, size_t VecSize> 378 class IterListItem<PrevItemT, NodeVecT, VecSize, /*Level=*/0U> 379 { 380 public: 381 /// The type of iterator stored in the previous list item 382 using PrevIterT = typename PrevItemT::IterT; 383 /// The type of node (non-const) whose iterator is stored in this list item 384 using _NodeT = typename NodeVecT::Front; 385 /// The type of iterator stored in this list item (e.g., InternalNode::ValueOnCIter) 386 using IterT = typename IterTraits<typename PrevIterT::NonConstNodeType, PrevIterT>::template 387 NodeConverter<_NodeT>::Type; 388 389 /// The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>) 390 using NodeT = typename IterT::NodeType; 391 /// The type of the node with const qualifiers removed ("Non-Const") 392 using NCNodeT = typename IterT::NonConstNodeType; 393 /// The type of value (with const qualifiers removed) to which the iterator points 394 using NCValueT = typename IterT::NonConstValueType; 395 using ITraits = IterTraits<NCNodeT, IterT>; 396 /// NodeT's level in its tree (0 = LeafNode) 397 static const Index Level = 0; 398 399 IterListItem(PrevItemT*): mNext(this), mPrev(nullptr) {} 400 401 IterListItem(const IterListItem& other): 402 mIter(other.mIter), mNext(other.mNext), mPrev(nullptr) {} 403 IterListItem& operator=(const IterListItem& other) 404 { 405 if (&other != this) { 406 mIter = other.mIter; 407 mNext = other.mNext; 408 mPrev = nullptr; 409 } 410 return *this; 411 } 412 413 void updateBackPointers(PrevItemT* = nullptr) 414 { 415 mPrev = nullptr; mNext.updateBackPointers(this); 416 } 417 418 void setIter(const IterT& iter) { mIter = iter; } 419 template<typename OtherIterT> 420 void setIter(const OtherIterT& iter) { mNext.setIter(iter); } 421 422 void getNode(Index lvl, NodeT*& node) const 423 { 424 node = (lvl == 0) ? mIter.getParentNode() : nullptr; 425 } 426 template<typename OtherNodeT> 427 void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); } 428 429 template<typename OtherIterListItemT> 430 void initLevel(Index lvl, OtherIterListItemT& otherListItem) 431 { 432 if (lvl == 0) { 433 const NodeT* node = nullptr; 434 otherListItem.getNode(lvl, node); 435 mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node)); 436 } else { 437 mNext.initLevel(lvl, otherListItem); 438 } 439 } 440 441 Index pos(Index lvl) const { return (lvl == 0) ? mIter.pos() : mNext.pos(lvl); } 442 443 bool test(Index lvl) const { return (lvl == 0) ? mIter.test() : mNext.test(lvl); } 444 445 bool next(Index lvl) { return (lvl == 0) ? mIter.next() : mNext.next(lvl); } 446 447 bool down(Index lvl) { return (lvl == 0) ? false : mNext.down(lvl); } 448 449 Coord getCoord(Index lvl) const 450 { 451 return (lvl == 0) ? mIter.getCoord() : mNext.getCoord(lvl); 452 } 453 Index getChildDim(Index lvl) const 454 { 455 return (lvl == 0) ? NodeT::getChildDim() : mNext.getChildDim(lvl); 456 } 457 458 Index64 getVoxelCount(Index lvl) const 459 { 460 return (lvl == 0) ? 1 : mNext.getVoxelCount(lvl); 461 } 462 463 bool isValueOn(Index lvl) const 464 { 465 return (lvl == 0) ? mIter.isValueOn() : mNext.isValueOn(lvl); 466 } 467 468 const NCValueT& getValue(Index lvl) const 469 { 470 if (lvl == 0) return mIter.getValue(); 471 return mNext.getValue(lvl); 472 } 473 474 void setValue(Index lvl, const NCValueT& val) const 475 { 476 if (lvl == 0) mIter.setValue(val); else mNext.setValue(lvl, val); 477 } 478 void setValueOn(Index lvl, bool on = true) const 479 { 480 if (lvl == 0) mIter.setValueOn(on); else mNext.setValueOn(lvl, on); 481 } 482 void setValueOff(Index lvl) const 483 { 484 if (lvl == 0) mIter.setValueOff(); else mNext.setValueOff(lvl); 485 } 486 487 template<typename ModifyOp> 488 void modifyValue(Index lvl, const ModifyOp& op) const 489 { 490 if (lvl == 0) mIter.modifyValue(op); else mNext.modifyValue(lvl, op); 491 } 492 493 private: 494 using RestT = typename NodeVecT::PopFront; // NodeVecT minus its first item 495 using NextItem = IterListItem<IterListItem, RestT, VecSize - 1, /*Level=*/1>; 496 497 IterT mIter; 498 NextItem mNext; 499 PrevItemT* mPrev; 500 }; 501 502 503 /// The final element of a compile-time linked list of iterators to nodes of different types 504 template<typename PrevItemT, typename NodeVecT, Index _Level> 505 class IterListItem<PrevItemT, NodeVecT, /*VecSize=*/1, _Level> 506 { 507 public: 508 using _NodeT = typename NodeVecT::Front; 509 /// The type of iterator stored in the previous list item 510 using PrevIterT = typename PrevItemT::IterT; 511 /// The type of iterator stored in this list item (e.g., RootNode::ValueOnCIter) 512 using IterT = typename IterTraits<typename PrevIterT::NonConstNodeType, PrevIterT>::template 513 NodeConverter<_NodeT>::Type; 514 515 /// The type of node over which IterT iterates (e.g., const RootNode<...>) 516 using NodeT = typename IterT::NodeType; 517 /// The type of the node with const qualifiers removed ("Non-Const") 518 using NCNodeT = typename IterT::NonConstNodeType; 519 /// The type of value (with const qualifiers removed) to which the iterator points 520 using NCValueT = typename IterT::NonConstValueType; 521 /// NodeT's child node type, with the same constness (e.g., const InternalNode<...>) 522 using ChildT = typename CopyConstness<NodeT, typename NodeT::ChildNodeType>::Type; 523 /// NodeT's child node type with const qualifiers removed 524 using NCChildT = typename CopyConstness<NCNodeT, typename NCNodeT::ChildNodeType>::Type; 525 using ITraits = IterTraits<NCNodeT, IterT>; 526 /// NodeT's level in its tree (0 = LeafNode) 527 static const Index Level = _Level; 528 529 IterListItem(PrevItemT* prev): mPrev(prev) {} 530 531 IterListItem(const IterListItem& other): mIter(other.mIter), mPrev(nullptr) {} 532 IterListItem& operator=(const IterListItem& other) 533 { 534 if (&other != this) { 535 mIter = other.mIter; 536 mPrev = nullptr; ///< @note external call to updateBackPointers() required 537 } 538 return *this; 539 } 540 541 void updateBackPointers(PrevItemT* prev) { mPrev = prev; } 542 543 // The following method specializations differ from the default template 544 // implementations mainly in that they don't forward. 545 546 void setIter(const IterT& iter) { mIter = iter; } 547 548 void getNode(Index lvl, NodeT*& node) const 549 { 550 node = (lvl <= Level) ? mIter.getParentNode() : nullptr; 551 } 552 553 template<typename OtherIterListItemT> 554 void initLevel(Index lvl, OtherIterListItemT& otherListItem) 555 { 556 if (lvl == Level) { 557 const NodeT* node = nullptr; 558 otherListItem.getNode(lvl, node); 559 mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node)); 560 } 561 } 562 563 Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : Index(-1); } 564 565 bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : false; } 566 567 bool next(Index lvl) { return (lvl == Level) ? mIter.next() : false; } 568 569 bool down(Index lvl) 570 { 571 if (lvl == Level && mPrev != nullptr && mIter) { 572 if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) { 573 mPrev->setIter(PrevItemT::ITraits::begin(*child)); 574 return true; 575 } 576 } 577 return false; 578 } 579 580 Coord getCoord(Index lvl) const { return (lvl == Level) ? mIter.getCoord() : Coord(); } 581 Index getChildDim(Index lvl) const { return (lvl == Level) ? NodeT::getChildDim() : 0; } 582 Index64 getVoxelCount(Index lvl) const { return (lvl == Level) ? ChildT::NUM_VOXELS : 0; } 583 584 bool isValueOn(Index lvl) const { return (lvl == Level) ? mIter.isValueOn() : false; } 585 586 const NCValueT& getValue(Index lvl) const 587 { 588 assert(lvl == Level); 589 (void)lvl; // avoid unused variable warning in optimized builds 590 return mIter.getValue(); 591 } 592 593 void setValue(Index lvl, const NCValueT& val) const { if (lvl == Level) mIter.setValue(val); } 594 void setValueOn(Index lvl, bool on = true) const { if (lvl == Level) mIter.setValueOn(on); } 595 void setValueOff(Index lvl) const { if (lvl == Level) mIter.setValueOff(); } 596 597 template<typename ModifyOp> 598 void modifyValue(Index lvl, const ModifyOp& op) const 599 { 600 if (lvl == Level) mIter.modifyValue(op); 601 } 602 603 private: 604 IterT mIter; 605 PrevItemT* mPrev; 606 }; 607 608 609 //////////////////////////////////////// 610 611 612 //#define DEBUG_TREE_VALUE_ITERATOR 613 614 /// @brief Base class for tree-traversal iterators over tile and voxel values 615 template<typename _TreeT, typename _ValueIterT> 616 class TreeValueIteratorBase 617 { 618 public: 619 using TreeT = _TreeT; 620 using ValueIterT = _ValueIterT; 621 using NodeT = typename ValueIterT::NodeType; 622 using ValueT = typename ValueIterT::NonConstValueType; 623 using ChildOnIterT = typename NodeT::ChildOnCIter; 624 static const Index ROOT_LEVEL = NodeT::LEVEL; 625 static_assert(ValueIterT::NodeType::LEVEL == ROOT_LEVEL, "invalid value iterator node type"); 626 static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL; 627 628 TreeValueIteratorBase(TreeT&); 629 630 TreeValueIteratorBase(const TreeValueIteratorBase& other); 631 TreeValueIteratorBase& operator=(const TreeValueIteratorBase& other); 632 633 /// Specify the depth of the highest level of the tree to which to ascend (depth 0 = root). 634 void setMinDepth(Index minDepth); 635 /// Return the depth of the highest level of the tree to which this iterator ascends. 636 Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); } 637 /// Specify the depth of the lowest level of the tree to which to descend (depth 0 = root). 638 void setMaxDepth(Index maxDepth); 639 /// Return the depth of the lowest level of the tree to which this iterator ascends. 640 Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); } 641 642 //@{ 643 /// Return @c true if this iterator is not yet exhausted. 644 bool test() const { return mValueIterList.test(mLevel); } 645 operator bool() const { return this->test(); } 646 //@} 647 648 /// @brief Advance to the next tile or voxel value. 649 /// Return @c true if this iterator is not yet exhausted. 650 bool next(); 651 /// Advance to the next tile or voxel value. 652 TreeValueIteratorBase& operator++() { this->next(); return *this; } 653 654 /// @brief Return the level in the tree (0 = leaf) of the node to which 655 /// this iterator is currently pointing. 656 Index getLevel() const { return mLevel; } 657 /// @brief Return the depth in the tree (0 = root) of the node to which 658 /// this iterator is currently pointing. 659 Index getDepth() const { return ROOT_LEVEL - mLevel; } 660 static Index getLeafDepth() { return LEAF_DEPTH; } 661 662 /// @brief Return in @a node a pointer to the node over which this iterator is 663 /// currently iterating or one of that node's parents, as determined by @a NodeType. 664 /// @return a null pointer if @a NodeType specifies a node at a lower level 665 /// of the tree than that given by getLevel(). 666 template<typename NodeType> 667 void getNode(NodeType*& node) const { mValueIterList.getNode(mLevel, node); } 668 669 /// @brief Return the global coordinates of the voxel or tile to which 670 /// this iterator is currently pointing. 671 Coord getCoord() const { return mValueIterList.getCoord(mLevel); } 672 /// @brief Return in @a bbox the axis-aligned bounding box of 673 /// the voxel or tile to which this iterator is currently pointing. 674 /// @return false if the bounding box is empty. 675 bool getBoundingBox(CoordBBox&) const; 676 /// @brief Return the axis-aligned bounding box of the voxel or tile to which 677 /// this iterator is currently pointing. 678 CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; } 679 680 /// Return the number of (virtual) voxels corresponding to the value 681 Index64 getVoxelCount() const { return mValueIterList.getVoxelCount(mLevel);} 682 683 /// Return @c true if this iterator is currently pointing to a (non-leaf) tile value. 684 bool isTileValue() const { return mLevel != 0 && this->test(); } 685 /// Return @c true if this iterator is currently pointing to a (leaf) voxel value. 686 bool isVoxelValue() const { return mLevel == 0 && this->test(); } 687 /// Return @c true if the value to which this iterator is currently pointing is active. 688 bool isValueOn() const { return mValueIterList.isValueOn(mLevel); } 689 690 //@{ 691 /// Return the tile or voxel value to which this iterator is currently pointing. 692 const ValueT& getValue() const { return mValueIterList.getValue(mLevel); } 693 const ValueT& operator*() const { return this->getValue(); } 694 const ValueT* operator->() const { return &(this->operator*()); } 695 //@} 696 697 /// @brief Change the tile or voxel value to which this iterator is currently pointing 698 /// and mark it as active. 699 void setValue(const ValueT& val) const { mValueIterList.setValue(mLevel, val); } 700 /// @brief Change the active/inactive state of the tile or voxel value to which 701 /// this iterator is currently pointing. 702 void setActiveState(bool on) const { mValueIterList.setValueOn(mLevel, on); } 703 /// Mark the tile or voxel value to which this iterator is currently pointing as inactive. 704 void setValueOff() const { mValueIterList.setValueOff(mLevel); } 705 706 /// @brief Apply a functor to the item to which this iterator is pointing. 707 /// (Not valid for const iterators.) 708 /// @param op a functor of the form <tt>void op(ValueType&) const</tt> that modifies 709 /// its argument in place 710 /// @see Tree::modifyValue() 711 template<typename ModifyOp> 712 void modifyValue(const ModifyOp& op) const { mValueIterList.modifyValue(mLevel, op); } 713 714 /// Return a pointer to the tree over which this iterator is iterating. 715 TreeT* getTree() const { return mTree; } 716 717 /// Return a string (for debugging, mainly) describing this iterator's current state. 718 std::string summary() const; 719 720 private: 721 bool advance(bool dontIncrement = false); 722 723 using InvTreeT = typename iter::InvertedTree<NodeT, NodeT::LEVEL>::Type; 724 struct PrevChildItem { using IterT = ChildOnIterT; }; 725 struct PrevValueItem { using IterT = ValueIterT; }; 726 727 IterListItem<PrevChildItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mChildIterList; 728 IterListItem<PrevValueItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mValueIterList; 729 Index mLevel; 730 int mMinLevel, mMaxLevel; 731 TreeT* mTree; 732 }; // class TreeValueIteratorBase 733 734 735 template<typename TreeT, typename ValueIterT> 736 inline 737 TreeValueIteratorBase<TreeT, ValueIterT>::TreeValueIteratorBase(TreeT& tree): 738 mChildIterList(nullptr), 739 mValueIterList(nullptr), 740 mLevel(ROOT_LEVEL), 741 mMinLevel(int(LEAF_LEVEL)), 742 mMaxLevel(int(ROOT_LEVEL)), 743 mTree(&tree) 744 { 745 mChildIterList.setIter(IterTraits<NodeT, ChildOnIterT>::begin(tree.root())); 746 mValueIterList.setIter(IterTraits<NodeT, ValueIterT>::begin(tree.root())); 747 this->advance(/*dontIncrement=*/true); 748 } 749 750 751 template<typename TreeT, typename ValueIterT> 752 inline 753 TreeValueIteratorBase<TreeT, ValueIterT>::TreeValueIteratorBase(const TreeValueIteratorBase& other): 754 mChildIterList(other.mChildIterList), 755 mValueIterList(other.mValueIterList), 756 mLevel(other.mLevel), 757 mMinLevel(other.mMinLevel), 758 mMaxLevel(other.mMaxLevel), 759 mTree(other.mTree) 760 { 761 mChildIterList.updateBackPointers(); 762 mValueIterList.updateBackPointers(); 763 } 764 765 766 template<typename TreeT, typename ValueIterT> 767 inline TreeValueIteratorBase<TreeT, ValueIterT>& 768 TreeValueIteratorBase<TreeT, ValueIterT>::operator=(const TreeValueIteratorBase& other) 769 { 770 if (&other != this) { 771 mChildIterList = other.mChildIterList; 772 mValueIterList = other.mValueIterList; 773 mLevel = other.mLevel; 774 mMinLevel = other.mMinLevel; 775 mMaxLevel = other.mMaxLevel; 776 mTree = other.mTree; 777 mChildIterList.updateBackPointers(); 778 mValueIterList.updateBackPointers(); 779 } 780 return *this; 781 } 782 783 784 template<typename TreeT, typename ValueIterT> 785 inline void 786 TreeValueIteratorBase<TreeT, ValueIterT>::setMinDepth(Index minDepth) 787 { 788 mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth 789 if (int(mLevel) > mMaxLevel) this->next(); 790 } 791 792 793 template<typename TreeT, typename ValueIterT> 794 inline void 795 TreeValueIteratorBase<TreeT, ValueIterT>::setMaxDepth(Index maxDepth) 796 { 797 // level = ROOT_LEVEL - depth 798 mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth())); 799 if (int(mLevel) < mMinLevel) this->next(); 800 } 801 802 803 template<typename TreeT, typename ValueIterT> 804 inline bool 805 TreeValueIteratorBase<TreeT, ValueIterT>::next() 806 { 807 do { 808 if (!this->advance()) return false; 809 } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel); 810 return true; 811 } 812 813 814 template<typename TreeT, typename ValueIterT> 815 inline bool 816 TreeValueIteratorBase<TreeT, ValueIterT>::advance(bool dontIncrement) 817 { 818 bool recurse = false; 819 do { 820 recurse = false; 821 Index 822 vPos = mValueIterList.pos(mLevel), 823 cPos = mChildIterList.pos(mLevel); 824 if (vPos == cPos && mChildIterList.test(mLevel)) { 825 /// @todo Once ValueOff iterators properly skip child pointers, remove this block. 826 mValueIterList.next(mLevel); 827 vPos = mValueIterList.pos(mLevel); 828 } 829 if (vPos < cPos) { 830 if (dontIncrement) return true; 831 if (mValueIterList.next(mLevel)) { 832 if (mValueIterList.pos(mLevel) == cPos && mChildIterList.test(mLevel)) { 833 /// @todo Once ValueOff iterators properly skip child pointers, 834 /// remove this block. 835 mValueIterList.next(mLevel); 836 } 837 // If there is a next value and it precedes the next child, return. 838 if (mValueIterList.pos(mLevel) < cPos) return true; 839 } 840 } else { 841 // Advance to the next child, which may or may not precede the next value. 842 if (!dontIncrement) mChildIterList.next(mLevel); 843 } 844 #ifdef DEBUG_TREE_VALUE_ITERATOR 845 std::cout << "\n" << this->summary() << std::flush; 846 #endif 847 848 // Descend to the lowest level at which the next value precedes the next child. 849 while (mChildIterList.pos(mLevel) < mValueIterList.pos(mLevel)) { 850 #ifdef ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION 851 if (int(mLevel) == mMinLevel) { 852 // If the current node lies at the lowest allowed level, none of its 853 // children can be visited, so just advance its child iterator. 854 mChildIterList.next(mLevel); 855 if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel) 856 && mChildIterList.test(mLevel)) 857 { 858 /// @todo Once ValueOff iterators properly skip child pointers, 859 /// remove this block. 860 mValueIterList.next(mLevel); 861 } 862 } else 863 #endif 864 if (mChildIterList.down(mLevel)) { 865 --mLevel; // descend one level 866 mValueIterList.initLevel(mLevel, mChildIterList); 867 if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel) 868 && mChildIterList.test(mLevel)) 869 { 870 /// @todo Once ValueOff iterators properly skip child pointers, 871 /// remove this block. 872 mValueIterList.next(mLevel); 873 } 874 } else break; 875 #ifdef DEBUG_TREE_VALUE_ITERATOR 876 std::cout << "\n" << this->summary() << std::flush; 877 #endif 878 } 879 // Ascend to the nearest level at which one of the iterators is not yet exhausted. 880 while (!mChildIterList.test(mLevel) && !mValueIterList.test(mLevel)) { 881 if (mLevel == ROOT_LEVEL) return false; 882 ++mLevel; 883 mChildIterList.next(mLevel); 884 dontIncrement = true; 885 recurse = true; 886 } 887 } while (recurse); 888 return true; 889 } 890 891 892 template<typename TreeT, typename ValueIterT> 893 inline bool 894 TreeValueIteratorBase<TreeT, ValueIterT>::getBoundingBox(CoordBBox& bbox) const 895 { 896 if (!this->test()) { 897 bbox = CoordBBox(); 898 return false; 899 } 900 bbox.min() = mValueIterList.getCoord(mLevel); 901 bbox.max() = bbox.min().offsetBy(mValueIterList.getChildDim(mLevel) - 1); 902 return true; 903 } 904 905 906 template<typename TreeT, typename ValueIterT> 907 inline std::string 908 TreeValueIteratorBase<TreeT, ValueIterT>::summary() const 909 { 910 std::ostringstream ostr; 911 for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) { 912 if (lvl == 0) ostr << "leaf"; 913 else if (lvl == int(ROOT_LEVEL)) ostr << "root"; 914 else ostr << "int" << (ROOT_LEVEL - lvl); 915 ostr << " v" << mValueIterList.pos(lvl) 916 << " c" << mChildIterList.pos(lvl); 917 if (lvl > int(mLevel)) ostr << " / "; 918 } 919 if (this->test() && mValueIterList.pos(mLevel) < mChildIterList.pos(mLevel)) { 920 if (mLevel == 0) { 921 ostr << " " << this->getCoord(); 922 } else { 923 ostr << " " << this->getBoundingBox(); 924 } 925 } 926 return ostr.str(); 927 } 928 929 930 //////////////////////////////////////// 931 932 933 /// @brief Base class for tree-traversal iterators over all nodes 934 template<typename _TreeT, typename RootChildOnIterT> 935 class NodeIteratorBase 936 { 937 public: 938 using TreeT = _TreeT; 939 using RootIterT = RootChildOnIterT; 940 using RootNodeT = typename RootIterT::NodeType; 941 using NCRootNodeT = typename RootIterT::NonConstNodeType; 942 static const Index ROOT_LEVEL = RootNodeT::LEVEL; 943 using InvTreeT = typename iter::InvertedTree<NCRootNodeT, ROOT_LEVEL>::Type; 944 static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL; 945 946 using RootIterTraits = IterTraits<NCRootNodeT, RootIterT>; 947 948 NodeIteratorBase(); 949 NodeIteratorBase(TreeT&); 950 951 NodeIteratorBase(const NodeIteratorBase& other); 952 NodeIteratorBase& operator=(const NodeIteratorBase& other); 953 954 /// Specify the depth of the highest level of the tree to which to ascend (depth 0 = root). 955 void setMinDepth(Index minDepth); 956 /// Return the depth of the highest level of the tree to which this iterator ascends. 957 Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); } 958 /// Specify the depth of the lowest level of the tree to which to descend (depth 0 = root). 959 void setMaxDepth(Index maxDepth); 960 /// Return the depth of the lowest level of the tree to which this iterator ascends. 961 Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); } 962 963 //@{ 964 /// Return @c true if this iterator is not yet exhausted. 965 bool test() const { return !mDone; } 966 operator bool() const { return this->test(); } 967 //@} 968 969 /// @brief Advance to the next tile or voxel value. 970 /// @return @c true if this iterator is not yet exhausted. 971 bool next(); 972 /// Advance the iterator to the next leaf node. 973 void increment() { this->next(); } 974 NodeIteratorBase& operator++() { this->increment(); return *this; } 975 /// Increment the iterator n times. 976 void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} } 977 978 /// @brief Return the level in the tree (0 = leaf) of the node to which 979 /// this iterator is currently pointing. 980 Index getLevel() const { return mLevel; } 981 /// @brief Return the depth in the tree (0 = root) of the node to which 982 /// this iterator is currently pointing. 983 Index getDepth() const { return ROOT_LEVEL - mLevel; } 984 static Index getLeafDepth() { return LEAF_DEPTH; } 985 986 /// @brief Return the global coordinates of the voxel or tile to which 987 /// this iterator is currently pointing. 988 Coord getCoord() const; 989 /// @brief Return in @a bbox the axis-aligned bounding box of 990 /// the voxel or tile to which this iterator is currently pointing. 991 /// @return false if the bounding box is empty. 992 bool getBoundingBox(CoordBBox& bbox) const; 993 /// @brief Return the axis-aligned bounding box of the voxel or tile to which 994 /// this iterator is currently pointing. 995 CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; } 996 997 //@{ 998 /// @brief Return the node to which the iterator is pointing. 999 /// @note This iterator doesn't have the usual dereference operators (* and ->), 1000 /// because they would have to be overloaded by the returned node type. 1001 template<typename NodeT> 1002 void getNode(NodeT*& node) const { node = nullptr; mIterList.getNode(mLevel, node); } 1003 template<typename NodeT> 1004 void getNode(const NodeT*& node) const { node = nullptr; mIterList.getNode(mLevel, node); } 1005 //@} 1006 1007 TreeT* getTree() const { return mTree; } 1008 1009 std::string summary() const; 1010 1011 private: 1012 struct PrevItem { using IterT = RootIterT; }; 1013 1014 IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList; 1015 Index mLevel; 1016 int mMinLevel, mMaxLevel; 1017 bool mDone; 1018 TreeT* mTree; 1019 }; // class NodeIteratorBase 1020 1021 1022 template<typename TreeT, typename RootChildOnIterT> 1023 inline 1024 NodeIteratorBase<TreeT, RootChildOnIterT>::NodeIteratorBase(): 1025 mIterList(nullptr), 1026 mLevel(ROOT_LEVEL), 1027 mMinLevel(int(LEAF_LEVEL)), 1028 mMaxLevel(int(ROOT_LEVEL)), 1029 mDone(true), 1030 mTree(nullptr) 1031 { 1032 } 1033 1034 1035 template<typename TreeT, typename RootChildOnIterT> 1036 inline 1037 NodeIteratorBase<TreeT, RootChildOnIterT>::NodeIteratorBase(TreeT& tree): 1038 mIterList(nullptr), 1039 mLevel(ROOT_LEVEL), 1040 mMinLevel(int(LEAF_LEVEL)), 1041 mMaxLevel(int(ROOT_LEVEL)), 1042 mDone(false), 1043 mTree(&tree) 1044 { 1045 mIterList.setIter(RootIterTraits::begin(tree.root())); 1046 } 1047 1048 1049 template<typename TreeT, typename RootChildOnIterT> 1050 inline 1051 NodeIteratorBase<TreeT, RootChildOnIterT>::NodeIteratorBase(const NodeIteratorBase& other): 1052 mIterList(other.mIterList), 1053 mLevel(other.mLevel), 1054 mMinLevel(other.mMinLevel), 1055 mMaxLevel(other.mMaxLevel), 1056 mDone(other.mDone), 1057 mTree(other.mTree) 1058 { 1059 mIterList.updateBackPointers(); 1060 } 1061 1062 1063 template<typename TreeT, typename RootChildOnIterT> 1064 inline NodeIteratorBase<TreeT, RootChildOnIterT>& 1065 NodeIteratorBase<TreeT, RootChildOnIterT>::operator=(const NodeIteratorBase& other) 1066 { 1067 if (&other != this) { 1068 mLevel = other.mLevel; 1069 mMinLevel = other.mMinLevel; 1070 mMaxLevel = other.mMaxLevel; 1071 mDone = other.mDone; 1072 mTree = other.mTree; 1073 mIterList = other.mIterList; 1074 mIterList.updateBackPointers(); 1075 } 1076 return *this; 1077 } 1078 1079 1080 template<typename TreeT, typename RootChildOnIterT> 1081 inline void 1082 NodeIteratorBase<TreeT, RootChildOnIterT>::setMinDepth(Index minDepth) 1083 { 1084 mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth 1085 if (int(mLevel) > mMaxLevel) this->next(); 1086 } 1087 1088 1089 template<typename TreeT, typename RootChildOnIterT> 1090 inline void 1091 NodeIteratorBase<TreeT, RootChildOnIterT>::setMaxDepth(Index maxDepth) 1092 { 1093 // level = ROOT_LEVEL - depth 1094 mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth())); 1095 if (int(mLevel) < mMinLevel) this->next(); 1096 } 1097 1098 1099 template<typename TreeT, typename RootChildOnIterT> 1100 inline bool 1101 NodeIteratorBase<TreeT, RootChildOnIterT>::next() 1102 { 1103 do { 1104 if (mDone) return false; 1105 1106 // If the iterator over the current node points to a child, 1107 // descend to the child (depth-first traversal). 1108 if (int(mLevel) > mMinLevel && mIterList.test(mLevel)) { 1109 if (!mIterList.down(mLevel)) return false; 1110 --mLevel; 1111 } else { 1112 // Ascend to the nearest ancestor that has other children. 1113 while (!mIterList.test(mLevel)) { 1114 if (mLevel == ROOT_LEVEL) { 1115 // Can't ascend higher than the root. 1116 mDone = true; 1117 return false; 1118 } 1119 ++mLevel; // ascend one level 1120 mIterList.next(mLevel); // advance to the next child, if there is one 1121 } 1122 // Descend to the child. 1123 if (!mIterList.down(mLevel)) return false; 1124 --mLevel; 1125 } 1126 } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel); 1127 return true; 1128 } 1129 1130 1131 template<typename TreeT, typename RootChildOnIterT> 1132 inline Coord 1133 NodeIteratorBase<TreeT, RootChildOnIterT>::getCoord() const 1134 { 1135 if (mLevel != ROOT_LEVEL) return mIterList.getCoord(mLevel + 1); 1136 RootNodeT* root = nullptr; 1137 this->getNode(root); 1138 return root ? root->getMinIndex() : Coord::min(); 1139 } 1140 1141 1142 template<typename TreeT, typename RootChildOnIterT> 1143 inline bool 1144 NodeIteratorBase<TreeT, RootChildOnIterT>::getBoundingBox(CoordBBox& bbox) const 1145 { 1146 if (mLevel == ROOT_LEVEL) { 1147 RootNodeT* root = nullptr; 1148 this->getNode(root); 1149 if (root == nullptr) { 1150 bbox = CoordBBox(); 1151 return false; 1152 } 1153 root->getIndexRange(bbox); 1154 return true; 1155 } 1156 bbox.min() = mIterList.getCoord(mLevel + 1); 1157 bbox.max() = bbox.min().offsetBy(mIterList.getChildDim(mLevel + 1) - 1); 1158 return true; 1159 } 1160 1161 1162 template<typename TreeT, typename RootChildOnIterT> 1163 inline std::string 1164 NodeIteratorBase<TreeT, RootChildOnIterT>::summary() const 1165 { 1166 std::ostringstream ostr; 1167 for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) { 1168 if (lvl == 0) ostr << "leaf"; 1169 else if (lvl == int(ROOT_LEVEL)) ostr << "root"; 1170 else ostr << "int" << (ROOT_LEVEL - lvl); 1171 ostr << " c" << mIterList.pos(lvl); 1172 if (lvl > int(mLevel)) ostr << " / "; 1173 } 1174 CoordBBox bbox; 1175 this->getBoundingBox(bbox); 1176 ostr << " " << bbox; 1177 return ostr.str(); 1178 } 1179 1180 1181 //////////////////////////////////////// 1182 1183 1184 /// @brief Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) 1185 template<typename TreeT, typename RootChildOnIterT> 1186 class LeafIteratorBase 1187 { 1188 public: 1189 using RootIterT = RootChildOnIterT; 1190 using RootNodeT = typename RootIterT::NodeType; 1191 using NCRootNodeT = typename RootIterT::NonConstNodeType; 1192 static const Index ROOT_LEVEL = RootNodeT::LEVEL; 1193 using InvTreeT = typename iter::InvertedTree<NCRootNodeT, ROOT_LEVEL>::Type; 1194 using NCLeafNodeT = typename InvTreeT::Front; 1195 using LeafNodeT = typename CopyConstness<RootNodeT, NCLeafNodeT>::Type; 1196 static const Index LEAF_LEVEL = 0, LEAF_PARENT_LEVEL = LEAF_LEVEL + 1; 1197 1198 using RootIterTraits = IterTraits<NCRootNodeT, RootIterT>; 1199 1200 LeafIteratorBase(): mIterList(nullptr), mTree(nullptr) {} 1201 1202 LeafIteratorBase(TreeT& tree): mIterList(nullptr), mTree(&tree) 1203 { 1204 // Initialize the iterator list with a root node iterator. 1205 mIterList.setIter(RootIterTraits::begin(tree.root())); 1206 // Descend along the first branch, initializing the node iterator at each level. 1207 Index lvl = ROOT_LEVEL; 1208 for ( ; lvl > 0 && mIterList.down(lvl); --lvl) {} 1209 // If the first branch terminated above the leaf level, backtrack to the next branch. 1210 if (lvl > 0) this->next(); 1211 } 1212 1213 LeafIteratorBase(const LeafIteratorBase& other): mIterList(other.mIterList), mTree(other.mTree) 1214 { 1215 mIterList.updateBackPointers(); 1216 } 1217 LeafIteratorBase& operator=(const LeafIteratorBase& other) 1218 { 1219 if (&other != this) { 1220 mTree = other.mTree; 1221 mIterList = other.mIterList; 1222 mIterList.updateBackPointers(); 1223 } 1224 return *this; 1225 } 1226 1227 //@{ 1228 /// Return the leaf node to which the iterator is pointing. 1229 LeafNodeT* getLeaf() const 1230 { 1231 LeafNodeT* n = nullptr; 1232 mIterList.getNode(LEAF_LEVEL, n); 1233 return n; 1234 } 1235 LeafNodeT& operator*() const { return *this->getLeaf(); } 1236 LeafNodeT* operator->() const { return this->getLeaf(); } 1237 //@} 1238 1239 bool test() const { return mIterList.test(LEAF_PARENT_LEVEL); } 1240 operator bool() const { return this->test(); } 1241 1242 //@{ 1243 /// Advance the iterator to the next leaf node. 1244 bool next(); 1245 void increment() { this->next(); } 1246 LeafIteratorBase& operator++() { this->increment(); return *this; } 1247 //@} 1248 /// Increment the iterator n times. 1249 void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} } 1250 1251 TreeT* getTree() const { return mTree; } 1252 1253 private: 1254 struct PrevItem { using IterT = RootIterT; }; 1255 1256 /// @note Even though a LeafIterator doesn't iterate over leaf voxels, 1257 /// the first item of this linked list of node iterators is a leaf node iterator, 1258 /// whose purpose is only to provide access to its parent leaf node. 1259 IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList; 1260 TreeT* mTree; 1261 }; // class LeafIteratorBase 1262 1263 1264 template<typename TreeT, typename RootChildOnIterT> 1265 inline bool 1266 LeafIteratorBase<TreeT, RootChildOnIterT>::next() 1267 { 1268 // If the iterator is valid for the current node one level above the leaf level, 1269 // advance the iterator to the node's next child. 1270 if (mIterList.test(LEAF_PARENT_LEVEL) && mIterList.next(LEAF_PARENT_LEVEL)) { 1271 mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator 1272 return true; 1273 } 1274 1275 Index lvl = LEAF_PARENT_LEVEL; 1276 while (!mIterList.test(LEAF_PARENT_LEVEL)) { 1277 if (mIterList.test(lvl)) { 1278 mIterList.next(lvl); 1279 } else { 1280 do { 1281 // Ascend to the nearest level at which 1282 // one of the iterators is not yet exhausted. 1283 if (lvl == ROOT_LEVEL) return false; 1284 ++lvl; 1285 if (mIterList.test(lvl)) mIterList.next(lvl); 1286 } while (!mIterList.test(lvl)); 1287 } 1288 // Descend to the lowest child, but not as far as the leaf iterator. 1289 while (lvl > LEAF_PARENT_LEVEL && mIterList.down(lvl)) --lvl; 1290 } 1291 mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator 1292 return true; 1293 } 1294 1295 1296 //////////////////////////////////////// 1297 1298 1299 /// An IteratorRange wraps a tree or node iterator, giving the iterator TBB 1300 /// splittable range semantics. 1301 template<typename IterT> 1302 class IteratorRange 1303 { 1304 public: 1305 IteratorRange(const IterT& iter, size_t grainSize = 8): 1306 mIter(iter), 1307 mGrainSize(grainSize), 1308 mSize(0) 1309 { 1310 mSize = this->size(); 1311 } 1312 IteratorRange(IteratorRange& other, tbb::split): 1313 mIter(other.mIter), 1314 mGrainSize(other.mGrainSize), 1315 mSize(other.mSize >> 1) 1316 { 1317 other.increment(mSize); 1318 } 1319 1320 /// @brief Return a reference to this range's iterator. 1321 /// @note The reference is const, because the iterator should not be 1322 /// incremented directly. Use this range object's increment() instead. 1323 const IterT& iterator() const { return mIter; } 1324 1325 bool empty() const { return mSize == 0 || !mIter.test(); } 1326 bool test() const { return !this->empty(); } 1327 operator bool() const { return !this->empty(); } 1328 1329 /// @brief Return @c true if this range is splittable (i.e., if the iterator 1330 /// can be advanced more than mGrainSize times). 1331 bool is_divisible() const { return mSize > mGrainSize; } 1332 1333 /// Advance the iterator @a n times. 1334 void increment(Index n = 1) { for ( ; n > 0 && mSize > 0; --n, --mSize, ++mIter) {} } 1335 /// Advance the iterator to the next item. 1336 IteratorRange& operator++() { this->increment(); return *this; } 1337 /// @brief Advance the iterator to the next item. 1338 /// @return @c true if the iterator is not yet exhausted. 1339 bool next() { this->increment(); return this->test(); } 1340 1341 private: 1342 Index size() const { Index n = 0; for (IterT it(mIter); it.test(); ++n, ++it) {} return n; } 1343 1344 IterT mIter; 1345 size_t mGrainSize; 1346 /// @note mSize is only an estimate of the number of times mIter can be incremented 1347 /// before it is exhausted (because the topology of the underlying tree could change 1348 /// during iteration). For the purpose of range splitting, though, that should be 1349 /// sufficient, since the two halves need not be of exactly equal size. 1350 Index mSize; 1351 }; 1352 1353 1354 //////////////////////////////////////// 1355 1356 1357 /// @brief Base class for tree-traversal iterators over real and virtual voxel values 1358 /// @todo class TreeVoxelIteratorBase; 1359 1360 } // namespace tree 1361 } // namespace OPENVDB_VERSION_NAME 1362 } // namespace openvdb 1363 1364 #endif // OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED 1365