OpenVDB  9.1.1
ValueAccessor.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
4 /// @file tree/ValueAccessor.h
5 ///
6 /// When traversing a grid in a spatially coherent pattern (e.g., iterating
7 /// over neighboring voxels), request a @c ValueAccessor from the grid
8 /// (with Grid::getAccessor()) and use the accessor's @c getValue() and
9 /// @c setValue() methods. These will typically be significantly faster
10 /// than accessing voxels directly in the grid's tree.
11 ///
12 /// @par Example:
13 ///
14 /// @code
15 /// FloatGrid grid;
16 /// FloatGrid::Accessor acc = grid.getAccessor();
17 /// // First access is slow:
18 /// acc.setValue(Coord(0, 0, 0), 100);
19 /// // Subsequent nearby accesses are fast, since the accessor now holds pointers
20 /// // to nodes that contain (0, 0, 0) along the path from the root of the grid's
21 /// // tree to the leaf:
22 /// acc.setValue(Coord(0, 0, 1), 100);
23 /// acc.getValue(Coord(0, 2, 0), 100);
24 /// // Slow, because the accessor must be repopulated:
25 /// acc.getValue(Coord(-1, -1, -1));
26 /// // Fast:
27 /// acc.getValue(Coord(-1, -1, -2));
28 /// acc.setValue(Coord(-1, -2, 0), -100);
29 /// @endcode
30 
31 #ifndef OPENVDB_TREE_VALUEACCESSOR_HAS_BEEN_INCLUDED
32 #define OPENVDB_TREE_VALUEACCESSOR_HAS_BEEN_INCLUDED
33 
34 #include <tbb/null_mutex.h>
35 #include <tbb/spin_mutex.h>
36 #include <openvdb/version.h>
37 #include <openvdb/Types.h>
38 #include <cassert>
39 #include <limits>
40 #include <type_traits>
41 
42 namespace openvdb {
44 namespace OPENVDB_VERSION_NAME {
45 namespace tree {
46 
47 // Forward declarations of local classes that are not intended for general use
48 // The IsSafe template parameter is explained in the warning below.
49 template<typename TreeType, bool IsSafe = true>
51 template<typename TreeType, bool IsSafe = true, Index L0 = 0>
53 template<typename TreeType, bool IsSafe = true, Index L0 = 0, Index L1 = 1>
55 template<typename TreeType, bool IsSafe = true, Index L0 = 0, Index L1 = 1, Index L2 = 2>
57 template<typename TreeCacheT, typename NodeVecT, bool AtRoot> class CacheItem;
58 
59 
60 /// @brief This base class for ValueAccessors manages registration of an accessor
61 /// with a tree so that the tree can automatically clear the accessor whenever
62 /// one of its nodes is deleted.
63 ///
64 /// @internal A base class is needed because ValueAccessor is templated on both
65 /// a Tree type and a mutex type. The various instantiations of the template
66 /// are distinct, unrelated types, so they can't easily be stored in a container
67 /// such as the Tree's CacheRegistry. This base class, in contrast, is templated
68 /// only on the Tree type, so for any given Tree, only two distinct instantiations
69 /// are possible, ValueAccessorBase<Tree> and ValueAccessorBase<const Tree>.
70 ///
71 /// @warning If IsSafe = false then the ValueAccessor will not register itself
72 /// with the tree from which it is constructed. While in some rare cases this can
73 /// lead to better performance (since it avoids the small overhead of insertion
74 /// on creation and deletion on destruction) it is also unsafe if the tree is
75 /// modified. So unless you're an expert it is highly recommended to set
76 /// IsSafe = true, which is the default in all derived ValueAccessors defined
77 /// below. However if you know that the tree is no being modifed for the lifespan
78 /// of the ValueAccessor AND the work performed per ValueAccessor is small relative
79 /// to overhead of registering it you should consider setting IsSafe = false. If
80 /// this turns out to improve performance you should really rewrite your code so as
81 /// to better amortize the construction of the ValueAccessor, i.e. reuse it as much
82 /// as possible!
83 template<typename TreeType, bool IsSafe>
85 {
86 public:
87  static const bool IsConstTree = std::is_const<TreeType>::value;
88 
89  /// @brief Return true if this accessor is safe, i.e. registered
90  /// by the tree from which it is constructed. Un-registered
91  /// accessors can in rare cases be faster because it avoids the
92  /// (small) overhead of registration, but they are unsafe if the
93  /// tree is modified. So unless you're an expert it is highly
94  /// recommended to set IsSafe = true (which is the default).
95  static bool isSafe() { return IsSafe; }
96 
97  ValueAccessorBase(TreeType& tree): mTree(&tree)
98  {
99  if (IsSafe) tree.attachAccessor(*this);
100  }
101 
102  virtual ~ValueAccessorBase() { if (IsSafe && mTree) mTree->releaseAccessor(*this); }
103 
104  /// @brief Return a pointer to the tree associated with this accessor.
105  /// @details The pointer will be null only if the tree from which this accessor
106  /// was constructed was subsequently deleted (which generally leaves the
107  /// accessor in an unsafe state).
108  TreeType* getTree() const { return mTree; }
109  /// Return a reference to the tree associated with this accessor.
110  TreeType& tree() const { assert(mTree); return *mTree; }
111 
112  ValueAccessorBase(const ValueAccessorBase& other): mTree(other.mTree)
113  {
114  if (IsSafe && mTree) mTree->attachAccessor(*this);
115  }
116 
118  {
119  if (&other != this) {
120  if (IsSafe && mTree) mTree->releaseAccessor(*this);
121  mTree = other.mTree;
122  if (IsSafe && mTree) mTree->attachAccessor(*this);
123  }
124  return *this;
125  }
126 
127  virtual void clear() = 0;
128 
129 protected:
130  // Allow trees to deregister themselves.
131  template<typename> friend class Tree;
132 
133  virtual void release() { mTree = nullptr; }
134 
135  TreeType* mTree;
136 }; // class ValueAccessorBase
137 
138 
139 ////////////////////////////////////////
140 
141 
142 /// When traversing a grid in a spatially coherent pattern (e.g., iterating
143 /// over neighboring voxels), request a @c ValueAccessor from the grid
144 /// (with Grid::getAccessor()) and use the accessor's @c getValue() and
145 /// @c setValue() methods. These will typically be significantly faster
146 /// than accessing voxels directly in the grid's tree.
147 ///
148 /// A ValueAccessor caches pointers to tree nodes along the path to a voxel (x, y, z).
149 /// A subsequent access to voxel (x', y', z') starts from the cached leaf node and
150 /// moves up until a cached node that encloses (x', y', z') is found, then traverses
151 /// down the tree from that node to a leaf, updating the cache with the new path.
152 /// This leads to significant acceleration of spatially-coherent accesses.
153 ///
154 /// @param _TreeType the type of the tree to be accessed [required]
155 /// @param IsSafe if IsSafe = false then the ValueAccessor will
156 /// not register itself with the tree from which
157 /// it is constructed (see warning).
158 /// @param CacheLevels the number of nodes to be cached, starting from the leaf level
159 /// and not including the root (i.e., CacheLevels < DEPTH),
160 /// and defaulting to all non-root nodes
161 /// @param MutexType the type of mutex to use (see note)
162 ///
163 /// @warning If IsSafe = false then the ValueAccessor will not register itself
164 /// with the tree from which it is constructed. While in some rare cases this can
165 /// lead to better performance (since it avoids the small overhead of insertion
166 /// on creation and deletion on destruction) it is also unsafe if the tree is
167 /// modified. So unless you're an expert it is highly recommended to set
168 /// IsSafe = true, which is the default. However if you know that the tree is no
169 /// being modifed for the lifespan of the ValueAccessor AND the work performed
170 /// per ValueAccessor is small relative to overhead of registering it you should
171 /// consider setting IsSafe = false. If this improves performance you should
172 /// really rewrite your code so as to better amortize the construction of the
173 /// ValueAccessor, i.e. reuse it as much as possible!
174 ///
175 /// @note If @c MutexType is a TBB-compatible mutex, then multiple threads may
176 /// safely access a single, shared accessor. However, it is highly recommended
177 /// that, instead, each thread be assigned its own, non-mutex-protected accessor.
178 template<typename _TreeType,
179  bool IsSafe = true,
180  Index CacheLevels = _TreeType::DEPTH-1,
181  typename MutexType = tbb::null_mutex>
182 class ValueAccessor: public ValueAccessorBase<_TreeType, IsSafe>
183 {
184 public:
185  static_assert(CacheLevels < _TreeType::DEPTH, "cache size exceeds tree depth");
186 
187  using TreeType = _TreeType;
188  using RootNodeT = typename TreeType::RootNodeType;
189  using LeafNodeT = typename TreeType::LeafNodeType;
190  using ValueType = typename RootNodeT::ValueType;
192  using LockT = typename MutexType::scoped_lock;
193  using BaseT::IsConstTree;
194 
195  ValueAccessor(TreeType& tree): BaseT(tree), mCache(*this)
196  {
197  mCache.insert(Coord(), &tree.root());
198  }
199 
200  ValueAccessor(const ValueAccessor& other): BaseT(other), mCache(*this, other.mCache) {}
201 
203  {
204  if (&other != this) {
205  this->BaseT::operator=(other);
206  mCache.copy(*this, other.mCache);
207  }
208  return *this;
209  }
210  ~ValueAccessor() override = default;
211 
212  /// Return the number of cache levels employed by this accessor.
213  static Index numCacheLevels() { return CacheLevels; }
214 
215  /// Return @c true if nodes along the path to the given voxel have been cached.
216  bool isCached(const Coord& xyz) const { LockT lock(mMutex); return mCache.isCached(xyz); }
217 
218  /// Return the value of the voxel at the given coordinates.
219  const ValueType& getValue(const Coord& xyz) const
220  {
221  LockT lock(mMutex);
222  return mCache.getValue(xyz);
223  }
224 
225  /// Return the active state of the voxel at the given coordinates.
226  bool isValueOn(const Coord& xyz) const { LockT lock(mMutex); return mCache.isValueOn(xyz); }
227 
228  /// Return the active state of the voxel as well as its value
229  bool probeValue(const Coord& xyz, ValueType& value) const
230  {
231  LockT lock(mMutex);
232  return mCache.probeValue(xyz,value);
233  }
234 
235  /// Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides,
236  /// or -1 if (x, y, z) isn't explicitly represented in the tree (i.e., if it is
237  /// implicitly a background voxel).
238  int getValueDepth(const Coord& xyz) const
239  {
240  LockT lock(mMutex);
241  return mCache.getValueDepth(xyz);
242  }
243 
244  /// Return @c true if the value of voxel (x, y, z) resides at the leaf level
245  /// of the tree, i.e., if it is not a tile value.
246  bool isVoxel(const Coord& xyz) const { LockT lock(mMutex); return mCache.isVoxel(xyz); }
247 
248  //@{
249  /// Set the value of the voxel at the given coordinates and mark the voxel as active.
250  void setValue(const Coord& xyz, const ValueType& value)
251  {
252  LockT lock(mMutex);
253  mCache.setValue(xyz, value);
254  }
255  void setValueOn(const Coord& xyz, const ValueType& value) { this->setValue(xyz, value); }
256  //@}
257 
258  /// Set the value of the voxel at the given coordinate but don't change its active state.
259  void setValueOnly(const Coord& xyz, const ValueType& value)
260  {
261  LockT lock(mMutex);
262  mCache.setValueOnly(xyz, value);
263  }
264 
265  /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
266  void setValueOff(const Coord& xyz, const ValueType& value)
267  {
268  LockT lock(mMutex);
269  mCache.setValueOff(xyz, value);
270  }
271 
272  /// @brief Apply a functor to the value of the voxel at the given coordinates
273  /// and mark the voxel as active.
274  /// @details See Tree::modifyValue() for details.
275  template<typename ModifyOp>
276  void modifyValue(const Coord& xyz, const ModifyOp& op)
277  {
278  LockT lock(mMutex);
279  mCache.modifyValue(xyz, op);
280  }
281 
282  /// @brief Apply a functor to the voxel at the given coordinates.
283  /// @details See Tree::modifyValueAndActiveState() for details.
284  template<typename ModifyOp>
285  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
286  {
287  LockT lock(mMutex);
288  mCache.modifyValueAndActiveState(xyz, op);
289  }
290 
291  /// Set the active state of the voxel at the given coordinates but don't change its value.
292  void setActiveState(const Coord& xyz, bool on = true)
293  {
294  LockT lock(mMutex);
295  mCache.setActiveState(xyz, on);
296  }
297  /// Mark the voxel at the given coordinates as active but don't change its value.
298  void setValueOn(const Coord& xyz) { this->setActiveState(xyz, true); }
299  /// Mark the voxel at the given coordinates as inactive but don't change its value.
300  void setValueOff(const Coord& xyz) { this->setActiveState(xyz, false); }
301 
302  /// Return the cached node of type @a NodeType. [Mainly for internal use]
303  template<typename NodeType>
304  NodeType* getNode()
305  {
306  LockT lock(mMutex);
307  NodeType* node = nullptr;
308  mCache.getNode(node);
309  return node;
310  }
311 
312  /// Cache the given node, which should lie along the path from the root node to
313  /// the node containing voxel (x, y, z). [Mainly for internal use]
314  template<typename NodeType>
315  void insertNode(const Coord& xyz, NodeType& node)
316  {
317  LockT lock(mMutex);
318  mCache.insert(xyz, &node);
319  }
320 
321  /// If a node of the given type exists in the cache, remove it, so that
322  /// isCached(xyz) returns @c false for any voxel (x, y, z) contained in
323  /// that node. [Mainly for internal use]
324  template<typename NodeType>
325  void eraseNode() { LockT lock(mMutex); NodeType* node = nullptr; mCache.erase(node); }
326 
327  /// @brief Add the specified leaf to this tree, possibly creating a child branch
328  /// in the process. If the leaf node already exists, replace it.
329  void addLeaf(LeafNodeT* leaf)
330  {
331  LockT lock(mMutex);
332  mCache.addLeaf(leaf);
333  }
334 
335  /// @brief Add a tile at the specified tree level that contains voxel (x, y, z),
336  /// possibly deleting existing nodes or creating new nodes in the process.
337  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state)
338  {
339  LockT lock(mMutex);
340  mCache.addTile(level, xyz, value, state);
341  }
342 
343  /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
344  /// If no such node exists, create one, but preserve the values and
345  /// active states of all voxels.
346  /// @details Use this method to preallocate a static tree topology
347  /// over which to safely perform multithreaded processing.
348  LeafNodeT* touchLeaf(const Coord& xyz)
349  {
350  LockT lock(mMutex);
351  return mCache.touchLeaf(xyz);
352  }
353 
354  //@{
355  /// @brief Return a pointer to the node of the specified type that contains
356  /// voxel (x, y, z), or @c nullptr if no such node exists.
357  template<typename NodeT>
358  NodeT* probeNode(const Coord& xyz)
359  {
360  LockT lock(mMutex);
361  return mCache.template probeNode<NodeT>(xyz);
362  }
363  template<typename NodeT>
364  const NodeT* probeConstNode(const Coord& xyz) const
365  {
366  LockT lock(mMutex);
367  return mCache.template probeConstNode<NodeT>(xyz);
368  }
369  template<typename NodeT>
370  const NodeT* probeNode(const Coord& xyz) const
371  {
372  return this->template probeConstNode<NodeT>(xyz);
373  }
374  //@}
375 
376  //@{
377  /// @brief Return a pointer to the leaf node that contains voxel (x, y, z),
378  /// or @c nullptr if no such node exists.
379  LeafNodeT* probeLeaf(const Coord& xyz)
380  {
381  LockT lock(mMutex);
382  return mCache.probeLeaf(xyz);
383  }
384  const LeafNodeT* probeConstLeaf(const Coord& xyz) const
385  {
386  LockT lock(mMutex);
387  return mCache.probeConstLeaf(xyz);
388  }
389  const LeafNodeT* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
390  //@}
391 
392  /// Remove all nodes from this cache, then reinsert the root node.
393  void clear() override
394  {
395  LockT lock(mMutex);
396  mCache.clear();
397  if (this->mTree) mCache.insert(Coord(), &(this->mTree->root()));
398  }
399 
400 private:
401  // Allow nodes to insert themselves into the cache.
402  template<typename> friend class RootNode;
403  template<typename, Index> friend class InternalNode;
404  template<typename, Index> friend class LeafNode;
405  // Allow trees to deregister themselves.
406  template<typename> friend class Tree;
407 
408  /// Prevent this accessor from calling Tree::releaseCache() on a tree that
409  /// no longer exists. (Called by mTree when it is destroyed.)
410  void release() override
411  {
412  LockT lock(mMutex);
413  this->BaseT::release();
414  mCache.clear();
415  }
416 
417  /// Cache the given node, which should lie along the path from the root node to
418  /// the node containing voxel (x, y, z).
419  /// @note This operation is not mutex-protected and is intended to be called
420  /// only by nodes and only in the context of a getValue() or setValue() call.
421  template<typename NodeType>
422  void insert(const Coord& xyz, NodeType* node) { mCache.insert(xyz, node); }
423 
424  // Define a list of all tree node types from LeafNode to RootNode
425  using InvTreeT = typename RootNodeT::NodeChainType;
426  // Remove all tree node types that are excluded from the cache
427  static constexpr int64_t First = CacheLevels;
428  static constexpr int64_t Last = InvTreeT::template Index<RootNodeT>;
429  using SubtreeT = typename InvTreeT::template RemoveByIndex<First, Last-1>;
431 
432  // Private member data
433  mutable CacheItemT mCache;
434  mutable MutexType mMutex;
435 
436 }; // class ValueAccessor
437 
438 
439 /// @brief Template specialization of the ValueAccessor with no mutex and no cache levels
440 /// @details This specialization is provided mainly for benchmarking.
441 /// Accessors with caching will almost always be faster.
442 template<typename TreeType, bool IsSafe>
443 class ValueAccessor<TreeType, IsSafe, 0, tbb::null_mutex>
444  : public ValueAccessor0<TreeType, IsSafe>
445 {
446 public:
447  ValueAccessor(TreeType& tree): ValueAccessor0<TreeType, IsSafe>(tree) {}
448  ValueAccessor(const ValueAccessor& other): ValueAccessor0<TreeType, IsSafe>(other) {}
449  ~ValueAccessor() override = default;
450 };
451 
452 
453 /// Template specialization of the ValueAccessor with no mutex and one cache level
454 template<typename TreeType, bool IsSafe>
455 class ValueAccessor<TreeType, IsSafe, 1, tbb::null_mutex>
456  : public ValueAccessor1<TreeType, IsSafe>
457 {
458 public:
459  ValueAccessor(TreeType& tree): ValueAccessor1<TreeType, IsSafe>(tree) {}
460  ValueAccessor(const ValueAccessor& other): ValueAccessor1<TreeType, IsSafe>(other) {}
461  ~ValueAccessor() override = default;
462 };
463 
464 
465 /// Template specialization of the ValueAccessor with no mutex and two cache levels
466 template<typename TreeType, bool IsSafe>
467 class ValueAccessor<TreeType, IsSafe, 2, tbb::null_mutex>
468  : public ValueAccessor2<TreeType, IsSafe>
469 {
470 public:
471  ValueAccessor(TreeType& tree): ValueAccessor2<TreeType, IsSafe>(tree) {}
472  ValueAccessor(const ValueAccessor& other): ValueAccessor2<TreeType, IsSafe>(other) {}
473  ~ValueAccessor() override = default;
474 };
475 
476 
477 /// Template specialization of the ValueAccessor with no mutex and three cache levels
478 template<typename TreeType, bool IsSafe>
479 class ValueAccessor<TreeType, IsSafe, 3, tbb::null_mutex>: public ValueAccessor3<TreeType, IsSafe>
480 {
481 public:
482  ValueAccessor(TreeType& tree): ValueAccessor3<TreeType, IsSafe>(tree) {}
483  ValueAccessor(const ValueAccessor&) = default;
484  ValueAccessor& operator=(const ValueAccessor&) = default;
485  ~ValueAccessor() override = default;
486 };
487 
488 
489 ////////////////////////////////////////
490 
491 
492 /// @brief This accessor is thread-safe (at the cost of speed) for both reading and
493 /// writing to a tree. That is, multiple threads may safely access a single,
494 /// shared ValueAccessorRW.
495 ///
496 /// @warning Since the mutex-locking employed by the ValueAccessorRW
497 /// can seriously impair performance of multithreaded applications, it
498 /// is recommended that, instead, each thread be assigned its own
499 /// (non-mutex protected) accessor.
500 template<typename TreeType, bool IsSafe = true>
501 class ValueAccessorRW: public ValueAccessor<TreeType, IsSafe, TreeType::DEPTH-1, tbb::spin_mutex>
502 {
503 public:
505  : ValueAccessor<TreeType, IsSafe, TreeType::DEPTH-1, tbb::spin_mutex>(tree)
506  {
507  }
508 };
509 
510 
511 ////////////////////////////////////////
512 
513 
514 //
515 // The classes below are for internal use and should rarely be used directly.
516 //
517 
518 // An element of a compile-time linked list of node pointers, ordered from LeafNode to RootNode
519 template<typename TreeCacheT, typename NodeVecT, bool AtRoot>
520 class CacheItem
521 {
522 public:
523  using NodeType = typename NodeVecT::Front;
524  using ValueType = typename NodeType::ValueType;
525  using LeafNodeType = typename NodeType::LeafNodeType;
526  using CoordLimits = std::numeric_limits<Int32>;
527 
528  CacheItem(TreeCacheT& parent):
529  mParent(&parent),
530  mHash(CoordLimits::max()),
531  mNode(nullptr),
532  mNext(parent)
533  {
534  }
535 
536  //@{
537  /// Copy another CacheItem's node pointers and hash keys, but not its parent pointer.
538  CacheItem(TreeCacheT& parent, const CacheItem& other):
539  mParent(&parent),
540  mHash(other.mHash),
541  mNode(other.mNode),
542  mNext(parent, other.mNext)
543  {
544  }
545 
546  CacheItem& copy(TreeCacheT& parent, const CacheItem& other)
547  {
548  mParent = &parent;
549  mHash = other.mHash;
550  mNode = other.mNode;
551  mNext.copy(parent, other.mNext);
552  return *this;
553  }
554  //@}
555 
556  bool isCached(const Coord& xyz) const
557  {
558  return (this->isHashed(xyz) || mNext.isCached(xyz));
559  }
560 
561  /// Cache the given node at this level.
562  void insert(const Coord& xyz, const NodeType* node)
563  {
564  mHash = (node != nullptr) ? xyz & ~(NodeType::DIM-1) : Coord::max();
565  mNode = node;
566  }
567  /// Forward the given node to another level of the cache.
568  template<typename OtherNodeType>
569  void insert(const Coord& xyz, const OtherNodeType* node) { mNext.insert(xyz, node); }
570 
571  /// Erase the node at this level.
572  void erase(const NodeType*) { mHash = Coord::max(); mNode = nullptr; }
573  /// Erase the node at another level of the cache.
574  template<typename OtherNodeType>
575  void erase(const OtherNodeType* node) { mNext.erase(node); }
576 
577  /// Erase the nodes at this and lower levels of the cache.
578  void clear() { mHash = Coord::max(); mNode = nullptr; mNext.clear(); }
579 
580  /// Return the cached node (if any) at this level.
581  void getNode(const NodeType*& node) const { node = mNode; }
582  void getNode(const NodeType*& node) { node = mNode; }
583  void getNode(NodeType*& node)
584  {
585  // This combination of a static assertion and a const_cast might not be elegant,
586  // but it is a lot simpler than specializing TreeCache for const Trees.
587  static_assert(!TreeCacheT::IsConstTree, "can't get a non-const node from a const tree");
588  node = const_cast<NodeType*>(mNode);
589  }
590  /// Forward the request to another level of the cache.
591  template<typename OtherNodeType>
592  void getNode(OtherNodeType*& node) { mNext.getNode(node); }
593 
594  /// Return the value of the voxel at the given coordinates.
595  const ValueType& getValue(const Coord& xyz)
596  {
597  if (this->isHashed(xyz)) {
598  assert(mNode);
599  return mNode->getValueAndCache(xyz, *mParent);
600  }
601  return mNext.getValue(xyz);
602  }
603 
604  void addLeaf(LeafNodeType* leaf)
605  {
606  static_assert(!TreeCacheT::IsConstTree, "can't add a node to a const tree");
607  if (NodeType::LEVEL == 0) return;
608  if (this->isHashed(leaf->origin())) {
609  assert(mNode);
610  return const_cast<NodeType*>(mNode)->addLeafAndCache(leaf, *mParent);
611  }
612  mNext.addLeaf(leaf);
613  }
614 
615  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state)
616  {
617  static_assert(!TreeCacheT::IsConstTree, "can't add a tile to a const tree");
618  if (NodeType::LEVEL < level) return;
619  if (this->isHashed(xyz)) {
620  assert(mNode);
621  return const_cast<NodeType*>(mNode)->addTileAndCache(
622  level, xyz, value, state, *mParent);
623  }
624  mNext.addTile(level, xyz, value, state);
625  }
626 
627  LeafNodeType* touchLeaf(const Coord& xyz)
628  {
629  static_assert(!TreeCacheT::IsConstTree, "can't get a non-const node from a const tree");
630  if (this->isHashed(xyz)) {
631  assert(mNode);
632  return const_cast<NodeType*>(mNode)->touchLeafAndCache(xyz, *mParent);
633  }
634  return mNext.touchLeaf(xyz);
635  }
636 
637  LeafNodeType* probeLeaf(const Coord& xyz)
638  {
639  static_assert(!TreeCacheT::IsConstTree, "can't get a non-const node from a const tree");
640  if (this->isHashed(xyz)) {
641  assert(mNode);
642  return const_cast<NodeType*>(mNode)->probeLeafAndCache(xyz, *mParent);
643  }
644  return mNext.probeLeaf(xyz);
645  }
646 
647  const LeafNodeType* probeConstLeaf(const Coord& xyz)
648  {
649  if (this->isHashed(xyz)) {
650  assert(mNode);
651  return mNode->probeConstLeafAndCache(xyz, *mParent);
652  }
653  return mNext.probeConstLeaf(xyz);
654  }
655 
656  template<typename NodeT>
657  NodeT* probeNode(const Coord& xyz)
658  {
659  static_assert(!TreeCacheT::IsConstTree, "can't get a non-const node from a const tree");
661  if (this->isHashed(xyz)) {
663  assert(mNode);
664  return reinterpret_cast<NodeT*>(const_cast<NodeType*>(mNode));
665  }
666  return const_cast<NodeType*>(mNode)->template probeNodeAndCache<NodeT>(xyz, *mParent);
667  }
668  return mNext.template probeNode<NodeT>(xyz);
670  }
671 
672  template<typename NodeT>
673  const NodeT* probeConstNode(const Coord& xyz)
674  {
676  if (this->isHashed(xyz)) {
678  assert(mNode);
679  return reinterpret_cast<const NodeT*>(mNode);
680  }
681  return mNode->template probeConstNodeAndCache<NodeT>(xyz, *mParent);
682  }
683  return mNext.template probeConstNode<NodeT>(xyz);
685  }
686 
687  /// Return the active state of the voxel at the given coordinates.
688  bool isValueOn(const Coord& xyz)
689  {
690  if (this->isHashed(xyz)) {
691  assert(mNode);
692  return mNode->isValueOnAndCache(xyz, *mParent);
693  }
694  return mNext.isValueOn(xyz);
695  }
696 
697  /// Return the active state and value of the voxel at the given coordinates.
698  bool probeValue(const Coord& xyz, ValueType& value)
699  {
700  if (this->isHashed(xyz)) {
701  assert(mNode);
702  return mNode->probeValueAndCache(xyz, value, *mParent);
703  }
704  return mNext.probeValue(xyz, value);
705  }
706 
707  int getValueDepth(const Coord& xyz)
708  {
709  if (this->isHashed(xyz)) {
710  assert(mNode);
711  return static_cast<int>(TreeCacheT::RootNodeT::LEVEL) -
712  static_cast<int>(mNode->getValueLevelAndCache(xyz, *mParent));
713  } else {
714  return mNext.getValueDepth(xyz);
715  }
716  }
717 
718  bool isVoxel(const Coord& xyz)
719  {
720  if (this->isHashed(xyz)) {
721  assert(mNode);
722  return mNode->getValueLevelAndCache(xyz, *mParent)==0;
723  } else {
724  return mNext.isVoxel(xyz);
725  }
726  }
727 
728  /// Set the value of the voxel at the given coordinates and mark the voxel as active.
729  void setValue(const Coord& xyz, const ValueType& value)
730  {
731  if (this->isHashed(xyz)) {
732  assert(mNode);
733  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
734  const_cast<NodeType*>(mNode)->setValueAndCache(xyz, value, *mParent);
735  } else {
736  mNext.setValue(xyz, value);
737  }
738  }
739  void setValueOnly(const Coord& xyz, const ValueType& value)
740  {
741  if (this->isHashed(xyz)) {
742  assert(mNode);
743  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
744  const_cast<NodeType*>(mNode)->setValueOnlyAndCache(xyz, value, *mParent);
745  } else {
746  mNext.setValueOnly(xyz, value);
747  }
748  }
749  void setValueOn(const Coord& xyz, const ValueType& value) { this->setValue(xyz, value); }
750 
751  /// @brief Apply a functor to the value of the voxel at the given coordinates
752  /// and mark the voxel as active.
753  /// @details See Tree::modifyValue() for details.
754  template<typename ModifyOp>
755  void modifyValue(const Coord& xyz, const ModifyOp& op)
756  {
757  if (this->isHashed(xyz)) {
758  assert(mNode);
759  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
760  const_cast<NodeType*>(mNode)->modifyValueAndCache(xyz, op, *mParent);
761  } else {
762  mNext.modifyValue(xyz, op);
763  }
764  }
765 
766  /// @brief Apply a functor to the voxel at the given coordinates.
767  /// @details See Tree::modifyValueAndActiveState() for details.
768  template<typename ModifyOp>
769  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
770  {
771  if (this->isHashed(xyz)) {
772  assert(mNode);
773  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
774  const_cast<NodeType*>(mNode)->modifyValueAndActiveStateAndCache(xyz, op, *mParent);
775  } else {
776  mNext.modifyValueAndActiveState(xyz, op);
777  }
778  }
779 
780  /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
781  void setValueOff(const Coord& xyz, const ValueType& value)
782  {
783  if (this->isHashed(xyz)) {
784  assert(mNode);
785  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
786  const_cast<NodeType*>(mNode)->setValueOffAndCache(xyz, value, *mParent);
787  } else {
788  mNext.setValueOff(xyz, value);
789  }
790  }
791 
792  /// Set the active state of the voxel at the given coordinates.
793  void setActiveState(const Coord& xyz, bool on)
794  {
795  if (this->isHashed(xyz)) {
796  assert(mNode);
797  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
798  const_cast<NodeType*>(mNode)->setActiveStateAndCache(xyz, on, *mParent);
799  } else {
800  mNext.setActiveState(xyz, on);
801  }
802  }
803 
804 private:
805  CacheItem(const CacheItem&);
806  CacheItem& operator=(const CacheItem&);
807 
808  bool isHashed(const Coord& xyz) const
809  {
810  return (xyz[0] & ~Coord::ValueType(NodeType::DIM-1)) == mHash[0]
811  && (xyz[1] & ~Coord::ValueType(NodeType::DIM-1)) == mHash[1]
812  && (xyz[2] & ~Coord::ValueType(NodeType::DIM-1)) == mHash[2];
813  }
814 
815  TreeCacheT* mParent;
816  Coord mHash;
817  const NodeType* mNode;
818  using RestT = typename NodeVecT::PopFront;
819  CacheItem<TreeCacheT, RestT, /*AtRoot=*/RestT::Size == 1> mNext;
820 };// end of CacheItem
821 
822 
823 /// The tail of a compile-time list of cached node pointers, ordered from LeafNode to RootNode
824 template<typename TreeCacheT, typename NodeVecT>
825 class CacheItem<TreeCacheT, NodeVecT, /*AtRoot=*/true>
826 {
827 public:
828  using RootNodeType = typename NodeVecT::Front;
829  using ValueType = typename RootNodeType::ValueType;
830  using LeafNodeType = typename RootNodeType::LeafNodeType;
831 
832  CacheItem(TreeCacheT& parent): mParent(&parent), mRoot(nullptr) {}
833  CacheItem(TreeCacheT& parent, const CacheItem& other): mParent(&parent), mRoot(other.mRoot) {}
834 
835  CacheItem& copy(TreeCacheT& parent, const CacheItem& other)
836  {
837  mParent = &parent;
838  mRoot = other.mRoot;
839  return *this;
840  }
841 
842  bool isCached(const Coord& xyz) const { return this->isHashed(xyz); }
843 
844  void insert(const Coord&, const RootNodeType* root) { mRoot = root; }
845 
846  // Needed for node types that are not cached
847  template<typename OtherNodeType>
848  void insert(const Coord&, const OtherNodeType*) {}
849 
850  void erase(const RootNodeType*) { mRoot = nullptr; }
851 
852  void clear() { mRoot = nullptr; }
853 
854  void getNode(RootNodeType*& node)
855  {
856  static_assert(!TreeCacheT::IsConstTree, "can't get a non-const node from a const tree");
857  node = const_cast<RootNodeType*>(mRoot);
858  }
859  void getNode(const RootNodeType*& node) const { node = mRoot; }
860 
861  void addLeaf(LeafNodeType* leaf)
862  {
863  assert(mRoot);
864  static_assert(!TreeCacheT::IsConstTree, "can't add a node to a const tree");
865  const_cast<RootNodeType*>(mRoot)->addLeafAndCache(leaf, *mParent);
866  }
867 
868  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state)
869  {
870  assert(mRoot);
871  static_assert(!TreeCacheT::IsConstTree, "can't add a tile to a const tree");
872  const_cast<RootNodeType*>(mRoot)->addTileAndCache(level, xyz, value, state, *mParent);
873  }
874 
875  LeafNodeType* touchLeaf(const Coord& xyz)
876  {
877  assert(mRoot);
878  static_assert(!TreeCacheT::IsConstTree, "can't get a non-const node from a const tree");
879  return const_cast<RootNodeType*>(mRoot)->touchLeafAndCache(xyz, *mParent);
880  }
881 
882  LeafNodeType* probeLeaf(const Coord& xyz)
883  {
884  assert(mRoot);
885  static_assert(!TreeCacheT::IsConstTree, "can't get a non-const node from a const tree");
886  return const_cast<RootNodeType*>(mRoot)->probeLeafAndCache(xyz, *mParent);
887  }
888 
889  const LeafNodeType* probeConstLeaf(const Coord& xyz)
890  {
891  assert(mRoot);
892  return mRoot->probeConstLeafAndCache(xyz, *mParent);
893  }
894 
895  template<typename NodeType>
896  NodeType* probeNode(const Coord& xyz)
897  {
898  assert(mRoot);
899  static_assert(!TreeCacheT::IsConstTree, "can't get a non-const node from a const tree");
900  return const_cast<RootNodeType*>(mRoot)->
901  template probeNodeAndCache<NodeType>(xyz, *mParent);
902  }
903 
904  template<typename NodeType>
905  const NodeType* probeConstNode(const Coord& xyz)
906  {
907  assert(mRoot);
908  return mRoot->template probeConstNodeAndCache<NodeType>(xyz, *mParent);
909  }
910 
911  int getValueDepth(const Coord& xyz)
912  {
913  assert(mRoot);
914  return mRoot->getValueDepthAndCache(xyz, *mParent);
915  }
916  bool isValueOn(const Coord& xyz)
917  {
918  assert(mRoot);
919  return mRoot->isValueOnAndCache(xyz, *mParent);
920  }
921 
922  bool probeValue(const Coord& xyz, ValueType& value)
923  {
924  assert(mRoot);
925  return mRoot->probeValueAndCache(xyz, value, *mParent);
926  }
927  bool isVoxel(const Coord& xyz)
928  {
929  assert(mRoot);
930  return mRoot->getValueDepthAndCache(xyz, *mParent) ==
931  static_cast<int>(RootNodeType::LEVEL);
932  }
933  const ValueType& getValue(const Coord& xyz)
934  {
935  assert(mRoot);
936  return mRoot->getValueAndCache(xyz, *mParent);
937  }
938 
939  void setValue(const Coord& xyz, const ValueType& value)
940  {
941  assert(mRoot);
942  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
943  const_cast<RootNodeType*>(mRoot)->setValueAndCache(xyz, value, *mParent);
944  }
945  void setValueOnly(const Coord& xyz, const ValueType& value)
946  {
947  assert(mRoot);
948  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
949  const_cast<RootNodeType*>(mRoot)->setValueOnlyAndCache(xyz, value, *mParent);
950  }
951  void setValueOn(const Coord& xyz, const ValueType& value) { this->setValue(xyz, value); }
952 
953  template<typename ModifyOp>
954  void modifyValue(const Coord& xyz, const ModifyOp& op)
955  {
956  assert(mRoot);
957  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
958  const_cast<RootNodeType*>(mRoot)->modifyValueAndCache(xyz, op, *mParent);
959  }
960 
961  template<typename ModifyOp>
962  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
963  {
964  assert(mRoot);
965  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
966  const_cast<RootNodeType*>(mRoot)->modifyValueAndActiveStateAndCache(xyz, op, *mParent);
967  }
968 
969  void setValueOff(const Coord& xyz, const ValueType& value)
970  {
971  assert(mRoot);
972  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
973  const_cast<RootNodeType*>(mRoot)->setValueOffAndCache(xyz, value, *mParent);
974  }
975 
976  void setActiveState(const Coord& xyz, bool on)
977  {
978  assert(mRoot);
979  static_assert(!TreeCacheT::IsConstTree, "can't modify a const tree's values");
980  const_cast<RootNodeType*>(mRoot)->setActiveStateAndCache(xyz, on, *mParent);
981  }
982 
983 private:
984  CacheItem(const CacheItem&);
985  CacheItem& operator=(const CacheItem&);
986 
987  bool isHashed(const Coord&) const { return false; }
988 
989  TreeCacheT* mParent;
990  const RootNodeType* mRoot;
991 };// end of CacheItem specialized for RootNode
992 
993 
994 ////////////////////////////////////////
995 
996 
997 /// @brief ValueAccessor with no mutex and no node caching.
998 /// @details This specialization is provided mainly for benchmarking.
999 /// Accessors with caching will almost always be faster.
1000 template<typename _TreeType, bool IsSafe>
1001 class ValueAccessor0: public ValueAccessorBase<_TreeType, IsSafe>
1002 {
1003 public:
1004  using TreeType = _TreeType;
1005  using ValueType = typename TreeType::ValueType;
1006  using RootNodeT = typename TreeType::RootNodeType;
1007  using LeafNodeT = typename TreeType::LeafNodeType;
1009 
1010  ValueAccessor0(TreeType& tree): BaseT(tree) {}
1011 
1012  ValueAccessor0(const ValueAccessor0& other): BaseT(other) {}
1013 
1014  /// Return the number of cache levels employed by this accessor.
1015  static Index numCacheLevels() { return 0; }
1016 
1018  {
1019  if (&other != this) this->BaseT::operator=(other);
1020  return *this;
1021  }
1022 
1023  ~ValueAccessor0() override = default;
1024 
1025  /// Return @c true if nodes along the path to the given voxel have been cached.
1026  bool isCached(const Coord&) const { return false; }
1027 
1028  /// Return the value of the voxel at the given coordinates.
1029  const ValueType& getValue(const Coord& xyz) const
1030  {
1031  assert(BaseT::mTree);
1032  return BaseT::mTree->getValue(xyz);
1033  }
1034 
1035  /// Return the active state of the voxel at the given coordinates.
1036  bool isValueOn(const Coord& xyz) const
1037  {
1038  assert(BaseT::mTree);
1039  return BaseT::mTree->isValueOn(xyz);
1040  }
1041 
1042  /// Return the active state and, in @a value, the value of the voxel at the given coordinates.
1043  bool probeValue(const Coord& xyz, ValueType& value) const
1044  {
1045  assert(BaseT::mTree);
1046  return BaseT::mTree->probeValue(xyz, value);
1047  }
1048 
1049  /// Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides,
1050  /// or -1 if (x, y, z) isn't explicitly represented in the tree (i.e., if it is
1051  /// implicitly a background voxel).
1052  int getValueDepth(const Coord& xyz) const
1053  {
1054  assert(BaseT::mTree);
1055  return BaseT::mTree->getValueDepth(xyz);
1056  }
1057 
1058  /// Return @c true if the value of voxel (x, y, z) resides at the leaf level
1059  /// of the tree, i.e., if it is not a tile value.
1060  bool isVoxel(const Coord& xyz) const
1061  {
1062  assert(BaseT::mTree);
1063  return BaseT::mTree->getValueDepth(xyz) == static_cast<int>(RootNodeT::LEVEL);
1064  }
1065 
1066  //@{
1067  /// Set the value of the voxel at the given coordinates and mark the voxel as active.
1068  void setValue(const Coord& xyz, const ValueType& value)
1069  {
1070  assert(BaseT::mTree);
1071  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1072  BaseT::mTree->setValue(xyz, value);
1073  }
1074  void setValueOn(const Coord& xyz, const ValueType& value) { this->setValue(xyz, value); }
1075  //@}
1076 
1077  /// Set the value of the voxel at the given coordinate but don't change its active state.
1078  void setValueOnly(const Coord& xyz, const ValueType& value)
1079  {
1080  assert(BaseT::mTree);
1081  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1082  BaseT::mTree->setValueOnly(xyz, value);
1083  }
1084 
1085  /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
1086  void setValueOff(const Coord& xyz, const ValueType& value)
1087  {
1088  assert(BaseT::mTree);
1089  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1090  BaseT::mTree->root().setValueOff(xyz, value);
1091  }
1092 
1093  /// @brief Apply a functor to the value of the voxel at the given coordinates
1094  /// and mark the voxel as active.
1095  /// @details See Tree::modifyValue() for details.
1096  template<typename ModifyOp>
1097  void modifyValue(const Coord& xyz, const ModifyOp& op)
1098  {
1099  assert(BaseT::mTree);
1100  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1101  BaseT::mTree->modifyValue(xyz, op);
1102  }
1103 
1104  /// @brief Apply a functor to the voxel at the given coordinates.
1105  /// @details See Tree::modifyValueAndActiveState() for details.
1106  template<typename ModifyOp>
1107  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
1108  {
1109  assert(BaseT::mTree);
1110  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1111  BaseT::mTree->modifyValueAndActiveState(xyz, op);
1112  }
1113 
1114  /// Set the active state of the voxel at the given coordinates but don't change its value.
1115  void setActiveState(const Coord& xyz, bool on = true)
1116  {
1117  assert(BaseT::mTree);
1118  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1119  BaseT::mTree->setActiveState(xyz, on);
1120  }
1121  /// Mark the voxel at the given coordinates as active but don't change its value.
1122  void setValueOn(const Coord& xyz) { this->setActiveState(xyz, true); }
1123  /// Mark the voxel at the given coordinates as inactive but don't change its value.
1124  void setValueOff(const Coord& xyz) { this->setActiveState(xyz, false); }
1125 
1126  /// Return the cached node of type @a NodeType. [Mainly for internal use]
1127  template<typename NodeT> NodeT* getNode() { return nullptr; }
1128 
1129  /// Cache the given node, which should lie along the path from the root node to
1130  /// the node containing voxel (x, y, z). [Mainly for internal use]
1131  template<typename NodeT> void insertNode(const Coord&, NodeT&) {}
1132 
1133  /// @brief Add the specified leaf to this tree, possibly creating a child branch
1134  /// in the process. If the leaf node already exists, replace it.
1135  void addLeaf(LeafNodeT* leaf)
1136  {
1137  assert(BaseT::mTree);
1138  static_assert(!BaseT::IsConstTree, "can't add a node to a const tree");
1139  BaseT::mTree->root().addLeaf(leaf);
1140  }
1141 
1142  /// @brief Add a tile at the specified tree level that contains voxel (x, y, z),
1143  /// possibly deleting existing nodes or creating new nodes in the process.
1144  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state)
1145  {
1146  assert(BaseT::mTree);
1147  static_assert(!BaseT::IsConstTree, "can't add a tile to a const tree");
1148  BaseT::mTree->root().addTile(level, xyz, value, state);
1149  }
1150 
1151  /// If a node of the given type exists in the cache, remove it, so that
1152  /// isCached(xyz) returns @c false for any voxel (x, y, z) contained in
1153  /// that node. [Mainly for internal use]
1154  template<typename NodeT> void eraseNode() {}
1155 
1156  LeafNodeT* touchLeaf(const Coord& xyz)
1157  {
1158  assert(BaseT::mTree);
1159  static_assert(!BaseT::IsConstTree, "can't get a non-const node from a const tree");
1160  return BaseT::mTree->touchLeaf(xyz);
1161  }
1162 
1163  template<typename NodeT>
1164  NodeT* probeNode(const Coord& xyz)
1165  {
1166  assert(BaseT::mTree);
1167  static_assert(!BaseT::IsConstTree, "can't get a non-const node from a const tree");
1168  return BaseT::mTree->template probeNode<NodeT>(xyz);
1169  }
1170 
1171  template<typename NodeT>
1172  const NodeT* probeConstNode(const Coord& xyz) const
1173  {
1174  assert(BaseT::mTree);
1175  return BaseT::mTree->template probeConstNode<NodeT>(xyz);
1176  }
1177 
1178  LeafNodeT* probeLeaf(const Coord& xyz)
1179  {
1180  return this->template probeNode<LeafNodeT>(xyz);
1181  }
1182 
1183  const LeafNodeT* probeConstLeaf(const Coord& xyz) const
1184  {
1185  return this->template probeConstNode<LeafNodeT>(xyz);
1186  }
1187 
1188  const LeafNodeT* probeLeaf(const Coord& xyz) const
1189  {
1190  return this->probeConstLeaf(xyz);
1191  }
1192 
1193  /// Remove all nodes from this cache, then reinsert the root node.
1194  void clear() override {}
1195 
1196 private:
1197  // Allow trees to deregister themselves.
1198  template<typename> friend class Tree;
1199 
1200  /// Prevent this accessor from calling Tree::releaseCache() on a tree that
1201  /// no longer exists. (Called by mTree when it is destroyed.)
1202  void release() override { this->BaseT::release(); }
1203 
1204 }; // ValueAccessor0
1205 
1206 
1207 /// @brief Value accessor with one level of node caching.
1208 /// @details The node cache level is specified by L0 with the default value 0
1209 /// (defined in the forward declaration) corresponding to a LeafNode.
1210 ///
1211 /// @note This class is for experts only and should rarely be used
1212 /// directly. Instead use ValueAccessor with its default template arguments.
1213 template<typename _TreeType, bool IsSafe, Index L0>
1215 {
1216 public:
1217  static_assert(_TreeType::DEPTH >= 2, "cache size exceeds tree depth");
1218  static_assert(L0 < _TreeType::RootNodeType::LEVEL, "invalid cache level");
1219  using TreeType = _TreeType;
1220  using ValueType = typename TreeType::ValueType;
1221  using RootNodeT = typename TreeType::RootNodeType;
1222  using LeafNodeT = typename TreeType::LeafNodeType;
1224  using InvTreeT = typename RootNodeT::NodeChainType;
1225  using NodeT0 = typename InvTreeT::template Get<L0>;
1226 
1227  /// Constructor from a tree
1228  ValueAccessor1(TreeType& tree) : BaseT(tree), mKey0(Coord::max()), mNode0(nullptr)
1229  {
1230  }
1231 
1232  /// Copy constructor
1233  ValueAccessor1(const ValueAccessor1& other) : BaseT(other) { this->copy(other); }
1234 
1235  /// Return the number of cache levels employed by this ValueAccessor
1236  static Index numCacheLevels() { return 1; }
1237 
1238  /// Assignment operator
1240  {
1241  if (&other != this) {
1242  this->BaseT::operator=(other);
1243  this->copy(other);
1244  }
1245  return *this;
1246  }
1247 
1248  /// Virtual destructor
1249  ~ValueAccessor1() override = default;
1250 
1251  /// Return @c true if any of the nodes along the path to the given
1252  /// voxel have been cached.
1253  bool isCached(const Coord& xyz) const
1254  {
1255  assert(BaseT::mTree);
1256  return this->isHashed(xyz);
1257  }
1258 
1259  /// Return the value of the voxel at the given coordinates.
1260  const ValueType& getValue(const Coord& xyz) const
1261  {
1262  assert(BaseT::mTree);
1263  if (this->isHashed(xyz)) {
1264  assert(mNode0);
1265  return mNode0->getValueAndCache(xyz, this->self());
1266  }
1267  return BaseT::mTree->root().getValueAndCache(xyz, this->self());
1268  }
1269 
1270  /// Return the active state of the voxel at the given coordinates.
1271  bool isValueOn(const Coord& xyz) const
1272  {
1273  assert(BaseT::mTree);
1274  if (this->isHashed(xyz)) {
1275  assert(mNode0);
1276  return mNode0->isValueOnAndCache(xyz, this->self());
1277  }
1278  return BaseT::mTree->root().isValueOnAndCache(xyz, this->self());
1279  }
1280 
1281  /// Return the active state of the voxel as well as its value
1282  bool probeValue(const Coord& xyz, ValueType& value) const
1283  {
1284  assert(BaseT::mTree);
1285  if (this->isHashed(xyz)) {
1286  assert(mNode0);
1287  return mNode0->probeValueAndCache(xyz, value, this->self());
1288  }
1289  return BaseT::mTree->root().probeValueAndCache(xyz, value, this->self());
1290  }
1291 
1292  /// Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides,
1293  /// or -1 if (x, y, z) isn't explicitly represented in the tree (i.e., if it is
1294  /// implicitly a background voxel).
1295  int getValueDepth(const Coord& xyz) const
1296  {
1297  assert(BaseT::mTree);
1298  if (this->isHashed(xyz)) {
1299  assert(mNode0);
1300  return RootNodeT::LEVEL - mNode0->getValueLevelAndCache(xyz, this->self());
1301  }
1302  return BaseT::mTree->root().getValueDepthAndCache(xyz, this->self());
1303  }
1304 
1305  /// Return @c true if the value of voxel (x, y, z) resides at the leaf level
1306  /// of the tree, i.e., if it is not a tile value.
1307  bool isVoxel(const Coord& xyz) const
1308  {
1309  assert(BaseT::mTree);
1310  if (this->isHashed(xyz)) {
1311  assert(mNode0);
1312  return mNode0->getValueLevelAndCache(xyz, this->self()) == 0;
1313  }
1314  return BaseT::mTree->root().getValueDepthAndCache(xyz, this->self()) ==
1315  static_cast<int>(RootNodeT::LEVEL);
1316  }
1317 
1318  //@{
1319  /// Set the value of the voxel at the given coordinates and mark the voxel as active.
1320  void setValue(const Coord& xyz, const ValueType& value)
1321  {
1322  assert(BaseT::mTree);
1323  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1324  if (this->isHashed(xyz)) {
1325  assert(mNode0);
1326  const_cast<NodeT0*>(mNode0)->setValueAndCache(xyz, value, *this);
1327  } else {
1328  BaseT::mTree->root().setValueAndCache(xyz, value, *this);
1329  }
1330  }
1331  void setValueOn(const Coord& xyz, const ValueType& value) { this->setValue(xyz, value); }
1332  //@}
1333 
1334  /// Set the value of the voxel at the given coordinate but preserves its active state.
1335  void setValueOnly(const Coord& xyz, const ValueType& value)
1336  {
1337  assert(BaseT::mTree);
1338  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1339  if (this->isHashed(xyz)) {
1340  assert(mNode0);
1341  const_cast<NodeT0*>(mNode0)->setValueOnlyAndCache(xyz, value, *this);
1342  } else {
1343  BaseT::mTree->root().setValueOnlyAndCache(xyz, value, *this);
1344  }
1345  }
1346 
1347  /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
1348  void setValueOff(const Coord& xyz, const ValueType& value)
1349  {
1350  assert(BaseT::mTree);
1351  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1352  if (this->isHashed(xyz)) {
1353  assert(mNode0);
1354  const_cast<NodeT0*>(mNode0)->setValueOffAndCache(xyz, value, *this);
1355  } else {
1356  BaseT::mTree->root().setValueOffAndCache(xyz, value, *this);
1357  }
1358  }
1359 
1360  /// @brief Apply a functor to the value of the voxel at the given coordinates
1361  /// and mark the voxel as active.
1362  /// @details See Tree::modifyValue() for details.
1363  template<typename ModifyOp>
1364  void modifyValue(const Coord& xyz, const ModifyOp& op)
1365  {
1366  assert(BaseT::mTree);
1367  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1368  if (this->isHashed(xyz)) {
1369  assert(mNode0);
1370  const_cast<NodeT0*>(mNode0)->modifyValueAndCache(xyz, op, *this);
1371  } else {
1372  BaseT::mTree->root().modifyValueAndCache(xyz, op, *this);
1373  }
1374  }
1375 
1376  /// @brief Apply a functor to the voxel at the given coordinates.
1377  /// @details See Tree::modifyValueAndActiveState() for details.
1378  template<typename ModifyOp>
1379  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
1380  {
1381  assert(BaseT::mTree);
1382  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1383  if (this->isHashed(xyz)) {
1384  assert(mNode0);
1385  const_cast<NodeT0*>(mNode0)->modifyValueAndActiveStateAndCache(xyz, op, *this);
1386  } else {
1387  BaseT::mTree->root().modifyValueAndActiveStateAndCache(xyz, op, *this);
1388  }
1389  }
1390 
1391  /// Set the active state of the voxel at the given coordinates but don't change its value.
1392  void setActiveState(const Coord& xyz, bool on = true)
1393  {
1394  assert(BaseT::mTree);
1395  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1396  if (this->isHashed(xyz)) {
1397  assert(mNode0);
1398  const_cast<NodeT0*>(mNode0)->setActiveStateAndCache(xyz, on, *this);
1399  } else {
1400  BaseT::mTree->root().setActiveStateAndCache(xyz, on, *this);
1401  }
1402  }
1403  /// Mark the voxel at the given coordinates as active but don't change its value.
1404  void setValueOn(const Coord& xyz) { this->setActiveState(xyz, true); }
1405  /// Mark the voxel at the given coordinates as inactive but don't change its value.
1406  void setValueOff(const Coord& xyz) { this->setActiveState(xyz, false); }
1407 
1408  /// Return the cached node of type @a NodeType. [Mainly for internal use]
1409  template<typename NodeT>
1410  NodeT* getNode()
1411  {
1412  const NodeT* node = nullptr;
1413  this->getNode(node);
1414  return const_cast<NodeT*>(node);
1415  }
1416 
1417  /// Cache the given node, which should lie along the path from the root node to
1418  /// the node containing voxel (x, y, z). [Mainly for internal use]
1419  template<typename NodeT>
1420  void insertNode(const Coord& xyz, NodeT& node) { this->insert(xyz, &node); }
1421 
1422  /// If a node of the given type exists in the cache, remove it, so that
1423  /// isCached(xyz) returns @c false for any voxel (x, y, z) contained in
1424  /// that node. [Mainly for internal use]
1425  template<typename NodeT>
1426  void eraseNode()
1427  {
1428  const NodeT* node = nullptr;
1429  this->eraseNode(node);
1430  }
1431 
1432  /// @brief Add the specified leaf to this tree, possibly creating a child branch
1433  /// in the process. If the leaf node already exists, replace it.
1434  void addLeaf(LeafNodeT* leaf)
1435  {
1436  assert(BaseT::mTree);
1437  static_assert(!BaseT::IsConstTree, "can't add a node to a const tree");
1438  BaseT::mTree->root().addLeaf(leaf);
1439  }
1440 
1441  /// @brief Add a tile at the specified tree level that contains voxel (x, y, z),
1442  /// possibly deleting existing nodes or creating new nodes in the process.
1443  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state)
1444  {
1445  assert(BaseT::mTree);
1446  static_assert(!BaseT::IsConstTree, "can't add a tile to a const tree");
1447  BaseT::mTree->root().addTile(level, xyz, value, state);
1448  }
1449 
1450  /// @brief @return the leaf node that contains voxel (x, y, z) and
1451  /// if it doesn't exist, create it, but preserve the values and
1452  /// active states of all voxels.
1453  ///
1454  /// Use this method to preallocate a static tree topology over which to
1455  /// safely perform multithreaded processing.
1456  LeafNodeT* touchLeaf(const Coord& xyz)
1457  {
1458  assert(BaseT::mTree);
1459  static_assert(!BaseT::IsConstTree, "can't get a non-const node from a const tree");
1460  if (this->isHashed(xyz)) {
1461  assert(mNode0);
1462  return const_cast<NodeT0*>(mNode0)->touchLeafAndCache(xyz, *this);
1463  }
1464  return BaseT::mTree->root().touchLeafAndCache(xyz, *this);
1465  }
1466 
1467  /// @brief @return a pointer to the node of the specified type that contains
1468  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
1469  template<typename NodeT>
1470  NodeT* probeNode(const Coord& xyz)
1471  {
1472  assert(BaseT::mTree);
1473  static_assert(!BaseT::IsConstTree, "can't get a non-const node from a const tree");
1476  if (this->isHashed(xyz)) {
1477  assert(mNode0);
1478  return reinterpret_cast<NodeT*>(const_cast<NodeT0*>(mNode0));
1479  }
1480  return BaseT::mTree->root().template probeNodeAndCache<NodeT>(xyz, *this);
1481  }
1482  return nullptr;
1484  }
1485  LeafNodeT* probeLeaf(const Coord& xyz)
1486  {
1487  return this->template probeNode<LeafNodeT>(xyz);
1488  }
1489 
1490  /// @brief @return a const pointer to the nodeof the specified type that contains
1491  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
1492  template<typename NodeT>
1493  const NodeT* probeConstNode(const Coord& xyz) const
1494  {
1495  assert(BaseT::mTree);
1498  if (this->isHashed(xyz)) {
1499  assert(mNode0);
1500  return reinterpret_cast<const NodeT*>(mNode0);
1501  }
1502  return BaseT::mTree->root().template probeConstNodeAndCache<NodeT>(xyz, this->self());
1503  }
1504  return nullptr;
1506  }
1507  const LeafNodeT* probeConstLeaf(const Coord& xyz) const
1508  {
1509  return this->template probeConstNode<LeafNodeT>(xyz);
1510  }
1511  const LeafNodeT* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
1512 
1513  /// Remove all the cached nodes and invalidate the corresponding hash-keys.
1514  void clear() override
1515  {
1516  mKey0 = Coord::max();
1517  mNode0 = nullptr;
1518  }
1519 
1520 private:
1521  // Allow nodes to insert themselves into the cache.
1522  template<typename> friend class RootNode;
1523  template<typename, Index> friend class InternalNode;
1524  template<typename, Index> friend class LeafNode;
1525  // Allow trees to deregister themselves.
1526  template<typename> friend class Tree;
1527 
1528  // This private method is merely for convenience.
1529  inline ValueAccessor1& self() const { return const_cast<ValueAccessor1&>(*this); }
1530 
1531  void getNode(const NodeT0*& node) { node = mNode0; }
1532  void getNode(const RootNodeT*& node)
1533  {
1534  node = (BaseT::mTree ? &BaseT::mTree->root() : nullptr);
1535  }
1536  template<typename OtherNodeType> void getNode(const OtherNodeType*& node) { node = nullptr; }
1537  void eraseNode(const NodeT0*) { mKey0 = Coord::max(); mNode0 = nullptr; }
1538  template<typename OtherNodeType> void eraseNode(const OtherNodeType*) {}
1539 
1540  /// Private copy method
1541  inline void copy(const ValueAccessor1& other)
1542  {
1543  mKey0 = other.mKey0;
1544  mNode0 = other.mNode0;
1545  }
1546 
1547  /// Prevent this accessor from calling Tree::releaseCache() on a tree that
1548  /// no longer exists. (Called by mTree when it is destroyed.)
1549  void release() override
1550  {
1551  this->BaseT::release();
1552  this->clear();
1553  }
1554  /// Cache the given node, which should lie along the path from the root node to
1555  /// the node containing voxel (x, y, z).
1556  /// @note This operation is not mutex-protected and is intended to be called
1557  /// only by nodes and only in the context of a getValue() or setValue() call.
1558  inline void insert(const Coord& xyz, const NodeT0* node)
1559  {
1560  assert(node);
1561  mKey0 = xyz & ~(NodeT0::DIM-1);
1562  mNode0 = node;
1563  }
1564 
1565  /// No-op in case a tree traversal attemps to insert a node that
1566  /// is not cached by the ValueAccessor
1567  template<typename OtherNodeType> inline void insert(const Coord&, const OtherNodeType*) {}
1568 
1569  inline bool isHashed(const Coord& xyz) const
1570  {
1571  return (xyz[0] & ~Coord::ValueType(NodeT0::DIM-1)) == mKey0[0]
1572  && (xyz[1] & ~Coord::ValueType(NodeT0::DIM-1)) == mKey0[1]
1573  && (xyz[2] & ~Coord::ValueType(NodeT0::DIM-1)) == mKey0[2];
1574  }
1575  mutable Coord mKey0;
1576  mutable const NodeT0* mNode0;
1577 }; // ValueAccessor1
1578 
1579 
1580 /// @brief Value accessor with two levels of node caching.
1581 /// @details The node cache levels are specified by L0 and L1
1582 /// with the default values 0 and 1 (defined in the forward declaration)
1583 /// corresponding to a LeafNode and its parent InternalNode.
1584 ///
1585 /// @note This class is for experts only and should rarely be used directly.
1586 /// Instead use ValueAccessor with its default template arguments.
1587 template<typename _TreeType, bool IsSafe, Index L0, Index L1>
1589 {
1590 public:
1591  static_assert(_TreeType::DEPTH >= 3, "cache size exceeds tree depth");
1592  static_assert(L0 < L1, "invalid cache level");
1593  static_assert(L1 < _TreeType::RootNodeType::LEVEL, "invalid cache level");
1594 
1595  using TreeType = _TreeType;
1596  using ValueType = typename TreeType::ValueType;
1597  using RootNodeT = typename TreeType::RootNodeType;
1598  using LeafNodeT = typename TreeType::LeafNodeType;
1600  using InvTreeT = typename RootNodeT::NodeChainType;
1601  using NodeT0 = typename InvTreeT::template Get<L0>;
1602  using NodeT1 = typename InvTreeT::template Get<L1>;
1603 
1604  /// Constructor from a tree
1606  mKey0(Coord::max()), mNode0(nullptr),
1607  mKey1(Coord::max()), mNode1(nullptr) {}
1608 
1609  /// Copy constructor
1610  ValueAccessor2(const ValueAccessor2& other) : BaseT(other) { this->copy(other); }
1611 
1612  /// Return the number of cache levels employed by this ValueAccessor
1613  static Index numCacheLevels() { return 2; }
1614 
1615  /// Assignment operator
1617  {
1618  if (&other != this) {
1619  this->BaseT::operator=(other);
1620  this->copy(other);
1621  }
1622  return *this;
1623  }
1624 
1625  /// Virtual destructor
1626  ~ValueAccessor2() override = default;
1627 
1628  /// Return @c true if any of the nodes along the path to the given
1629  /// voxel have been cached.
1630  bool isCached(const Coord& xyz) const
1631  {
1632  assert(BaseT::mTree);
1633  return this->isHashed1(xyz) || this->isHashed0(xyz);
1634  }
1635 
1636  /// Return the value of the voxel at the given coordinates.
1637  const ValueType& getValue(const Coord& xyz) const
1638  {
1639  assert(BaseT::mTree);
1640  if (this->isHashed0(xyz)) {
1641  assert(mNode0);
1642  return mNode0->getValueAndCache(xyz, this->self());
1643  } else if (this->isHashed1(xyz)) {
1644  assert(mNode1);
1645  return mNode1->getValueAndCache(xyz, this->self());
1646  }
1647  return BaseT::mTree->root().getValueAndCache(xyz, this->self());
1648  }
1649 
1650  /// Return the active state of the voxel at the given coordinates.
1651  bool isValueOn(const Coord& xyz) const
1652  {
1653  assert(BaseT::mTree);
1654  if (this->isHashed0(xyz)) {
1655  assert(mNode0);
1656  return mNode0->isValueOnAndCache(xyz, this->self());
1657  } else if (this->isHashed1(xyz)) {
1658  assert(mNode1);
1659  return mNode1->isValueOnAndCache(xyz, this->self());
1660  }
1661  return BaseT::mTree->root().isValueOnAndCache(xyz, this->self());
1662  }
1663 
1664  /// Return the active state of the voxel as well as its value
1665  bool probeValue(const Coord& xyz, ValueType& value) const
1666  {
1667  assert(BaseT::mTree);
1668  if (this->isHashed0(xyz)) {
1669  assert(mNode0);
1670  return mNode0->probeValueAndCache(xyz, value, this->self());
1671  } else if (this->isHashed1(xyz)) {
1672  assert(mNode1);
1673  return mNode1->probeValueAndCache(xyz, value, this->self());
1674  }
1675  return BaseT::mTree->root().probeValueAndCache(xyz, value, this->self());
1676  }
1677 
1678  /// Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides,
1679  /// or -1 if (x, y, z) isn't explicitly represented in the tree (i.e., if it is
1680  /// implicitly a background voxel).
1681  int getValueDepth(const Coord& xyz) const
1682  {
1683  assert(BaseT::mTree);
1684  if (this->isHashed0(xyz)) {
1685  assert(mNode0);
1686  return RootNodeT::LEVEL - mNode0->getValueLevelAndCache(xyz, this->self());
1687  } else if (this->isHashed1(xyz)) {
1688  assert(mNode1);
1689  return RootNodeT::LEVEL - mNode1->getValueLevelAndCache(xyz, this->self());
1690  }
1691  return BaseT::mTree->root().getValueDepthAndCache(xyz, this->self());
1692  }
1693 
1694  /// Return @c true if the value of voxel (x, y, z) resides at the leaf level
1695  /// of the tree, i.e., if it is not a tile value.
1696  bool isVoxel(const Coord& xyz) const
1697  {
1698  assert(BaseT::mTree);
1699  if (this->isHashed0(xyz)) {
1700  assert(mNode0);
1701  return mNode0->getValueLevelAndCache(xyz, this->self())==0;
1702  } else if (this->isHashed1(xyz)) {
1703  assert(mNode1);
1704  return mNode1->getValueLevelAndCache(xyz, this->self())==0;
1705  }
1706  return BaseT::mTree->root().getValueDepthAndCache(xyz, this->self()) ==
1707  static_cast<int>(RootNodeT::LEVEL);
1708  }
1709 
1710  //@{
1711  /// Set the value of the voxel at the given coordinates and mark the voxel as active.
1712  void setValue(const Coord& xyz, const ValueType& value)
1713  {
1714  assert(BaseT::mTree);
1715  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1716  if (this->isHashed0(xyz)) {
1717  assert(mNode0);
1718  const_cast<NodeT0*>(mNode0)->setValueAndCache(xyz, value, *this);
1719  } else if (this->isHashed1(xyz)) {
1720  assert(mNode1);
1721  const_cast<NodeT1*>(mNode1)->setValueAndCache(xyz, value, *this);
1722  } else {
1723  BaseT::mTree->root().setValueAndCache(xyz, value, *this);
1724  }
1725  }
1726  void setValueOn(const Coord& xyz, const ValueType& value) { this->setValue(xyz, value); }
1727  //@}
1728 
1729  /// Set the value of the voxel at the given coordinate but preserves its active state.
1730  void setValueOnly(const Coord& xyz, const ValueType& value)
1731  {
1732  assert(BaseT::mTree);
1733  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1734  if (this->isHashed0(xyz)) {
1735  assert(mNode0);
1736  const_cast<NodeT0*>(mNode0)->setValueOnlyAndCache(xyz, value, *this);
1737  } else if (this->isHashed1(xyz)) {
1738  assert(mNode1);
1739  const_cast<NodeT1*>(mNode1)->setValueOnlyAndCache(xyz, value, *this);
1740  } else {
1741  BaseT::mTree->root().setValueOnlyAndCache(xyz, value, *this);
1742  }
1743  }
1744 
1745  /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
1746  void setValueOff(const Coord& xyz, const ValueType& value)
1747  {
1748  assert(BaseT::mTree);
1749  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1750  if (this->isHashed0(xyz)) {
1751  assert(mNode0);
1752  const_cast<NodeT0*>(mNode0)->setValueOffAndCache(xyz, value, *this);
1753  } else if (this->isHashed1(xyz)) {
1754  assert(mNode1);
1755  const_cast<NodeT1*>(mNode1)->setValueOffAndCache(xyz, value, *this);
1756  } else {
1757  BaseT::mTree->root().setValueOffAndCache(xyz, value, *this);
1758  }
1759  }
1760 
1761  /// @brief Apply a functor to the value of the voxel at the given coordinates
1762  /// and mark the voxel as active.
1763  /// @details See Tree::modifyValue() for details.
1764  template<typename ModifyOp>
1765  void modifyValue(const Coord& xyz, const ModifyOp& op)
1766  {
1767  assert(BaseT::mTree);
1768  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1769  if (this->isHashed0(xyz)) {
1770  assert(mNode0);
1771  const_cast<NodeT0*>(mNode0)->modifyValueAndCache(xyz, op, *this);
1772  } else if (this->isHashed1(xyz)) {
1773  assert(mNode1);
1774  const_cast<NodeT1*>(mNode1)->modifyValueAndCache(xyz, op, *this);
1775  } else {
1776  BaseT::mTree->root().modifyValueAndCache(xyz, op, *this);
1777  }
1778  }
1779 
1780  /// @brief Apply a functor to the voxel at the given coordinates.
1781  /// @details See Tree::modifyValueAndActiveState() for details.
1782  template<typename ModifyOp>
1783  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
1784  {
1785  assert(BaseT::mTree);
1786  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1787  if (this->isHashed0(xyz)) {
1788  assert(mNode0);
1789  const_cast<NodeT0*>(mNode0)->modifyValueAndActiveStateAndCache(xyz, op, *this);
1790  } else if (this->isHashed1(xyz)) {
1791  assert(mNode1);
1792  const_cast<NodeT1*>(mNode1)->modifyValueAndActiveStateAndCache(xyz, op, *this);
1793  } else {
1794  BaseT::mTree->root().modifyValueAndActiveStateAndCache(xyz, op, *this);
1795  }
1796  }
1797 
1798  /// Set the active state of the voxel at the given coordinates without changing its value.
1799  void setActiveState(const Coord& xyz, bool on = true)
1800  {
1801  assert(BaseT::mTree);
1802  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
1803  if (this->isHashed0(xyz)) {
1804  assert(mNode0);
1805  const_cast<NodeT0*>(mNode0)->setActiveStateAndCache(xyz, on, *this);
1806  } else if (this->isHashed1(xyz)) {
1807  assert(mNode1);
1808  const_cast<NodeT1*>(mNode1)->setActiveStateAndCache(xyz, on, *this);
1809  } else {
1810  BaseT::mTree->root().setActiveStateAndCache(xyz, on, *this);
1811  }
1812  }
1813  /// Mark the voxel at the given coordinates as active without changing its value.
1814  void setValueOn(const Coord& xyz) { this->setActiveState(xyz, true); }
1815  /// Mark the voxel at the given coordinates as inactive without changing its value.
1816  void setValueOff(const Coord& xyz) { this->setActiveState(xyz, false); }
1817 
1818  /// Return the cached node of type @a NodeType. [Mainly for internal use]
1819  template<typename NodeT>
1820  NodeT* getNode()
1821  {
1822  const NodeT* node = nullptr;
1823  this->getNode(node);
1824  return const_cast<NodeT*>(node);
1825  }
1826 
1827  /// Cache the given node, which should lie along the path from the root node to
1828  /// the node containing voxel (x, y, z). [Mainly for internal use]
1829  template<typename NodeT>
1830  void insertNode(const Coord& xyz, NodeT& node) { this->insert(xyz, &node); }
1831 
1832  /// If a node of the given type exists in the cache, remove it, so that
1833  /// isCached(xyz) returns @c false for any voxel (x, y, z) contained in
1834  /// that node. [Mainly for internal use]
1835  template<typename NodeT>
1836  void eraseNode()
1837  {
1838  const NodeT* node = nullptr;
1839  this->eraseNode(node);
1840  }
1841 
1842  /// @brief Add the specified leaf to this tree, possibly creating a child branch
1843  /// in the process. If the leaf node already exists, replace it.
1844  void addLeaf(LeafNodeT* leaf)
1845  {
1846  assert(BaseT::mTree);
1847  static_assert(!BaseT::IsConstTree, "can't add a node to a const tree");
1848  if (this->isHashed1(leaf->origin())) {
1849  assert(mNode1);
1850  return const_cast<NodeT1*>(mNode1)->addLeafAndCache(leaf, *this);
1851  }
1852  BaseT::mTree->root().addLeafAndCache(leaf, *this);
1853  }
1854 
1855  /// @brief Add a tile at the specified tree level that contains voxel (x, y, z),
1856  /// possibly deleting existing nodes or creating new nodes in the process.
1857  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state)
1858  {
1859  assert(BaseT::mTree);
1860  static_assert(!BaseT::IsConstTree, "can't add a tile to a const tree");
1861  if (this->isHashed1(xyz)) {
1862  assert(mNode1);
1863  return const_cast<NodeT1*>(mNode1)->addTileAndCache(level, xyz, value, state, *this);
1864  }
1865  BaseT::mTree->root().addTileAndCache(level, xyz, value, state, *this);
1866  }
1867 
1868  /// @brief @return the leaf node that contains voxel (x, y, z) and
1869  /// if it doesn't exist, create it, but preserve the values and
1870  /// active states of all voxels.
1871  ///
1872  /// Use this method to preallocate a static tree topology over which to
1873  /// safely perform multithreaded processing.
1874  LeafNodeT* touchLeaf(const Coord& xyz)
1875  {
1876  assert(BaseT::mTree);
1877  static_assert(!BaseT::IsConstTree, "can't get a non-const node from a const tree");
1878  if (this->isHashed0(xyz)) {
1879  assert(mNode0);
1880  return const_cast<NodeT0*>(mNode0)->touchLeafAndCache(xyz, *this);
1881  } else if (this->isHashed1(xyz)) {
1882  assert(mNode1);
1883  return const_cast<NodeT1*>(mNode1)->touchLeafAndCache(xyz, *this);
1884  }
1885  return BaseT::mTree->root().touchLeafAndCache(xyz, *this);
1886  }
1887  /// @brief @return a pointer to the node of the specified type that contains
1888  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
1889  template<typename NodeT>
1890  NodeT* probeNode(const Coord& xyz)
1891  {
1892  assert(BaseT::mTree);
1893  static_assert(!BaseT::IsConstTree, "can't get a non-const node from a const tree");
1896  if (this->isHashed0(xyz)) {
1897  assert(mNode0);
1898  return reinterpret_cast<NodeT*>(const_cast<NodeT0*>(mNode0));
1899  } else if (this->isHashed1(xyz)) {
1900  assert(mNode1);
1901  return const_cast<NodeT1*>(mNode1)->template probeNodeAndCache<NodeT>(xyz, *this);
1902  }
1903  return BaseT::mTree->root().template probeNodeAndCache<NodeT>(xyz, *this);
1904  } else if ((std::is_same<NodeT, NodeT1>::value)) {
1905  if (this->isHashed1(xyz)) {
1906  assert(mNode1);
1907  return reinterpret_cast<NodeT*>(const_cast<NodeT1*>(mNode1));
1908  }
1909  return BaseT::mTree->root().template probeNodeAndCache<NodeT>(xyz, *this);
1910  }
1911  return nullptr;
1913  }
1914  /// @brief @return a pointer to the leaf node that contains
1915  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
1916  LeafNodeT* probeLeaf(const Coord& xyz) { return this->template probeNode<LeafNodeT>(xyz); }
1917 
1918  /// @brief @return a const pointer to the node of the specified type that contains
1919  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
1920  template<typename NodeT>
1921  const NodeT* probeConstLeaf(const Coord& xyz) const
1922  {
1925  if (this->isHashed0(xyz)) {
1926  assert(mNode0);
1927  return reinterpret_cast<const NodeT*>(mNode0);
1928  } else if (this->isHashed1(xyz)) {
1929  assert(mNode1);
1930  return mNode1->template probeConstNodeAndCache<NodeT>(xyz, this->self());
1931  }
1932  return BaseT::mTree->root().template probeConstNodeAndCache<NodeT>(xyz, this->self());
1933  } else if ((std::is_same<NodeT, NodeT1>::value)) {
1934  if (this->isHashed1(xyz)) {
1935  assert(mNode1);
1936  return reinterpret_cast<const NodeT*>(mNode1);
1937  }
1938  return BaseT::mTree->root().template probeConstNodeAndCache<NodeT>(xyz, this->self());
1939  }
1940  return nullptr;
1942  }
1943  /// @brief @return a const pointer to the leaf node that contains
1944  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
1945  const LeafNodeT* probeConstLeaf(const Coord& xyz) const
1946  {
1947  return this->template probeConstNode<LeafNodeT>(xyz);
1948  }
1949  const LeafNodeT* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
1950 
1951  /// @brief @return a const pointer to the node of the specified type that contains
1952  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
1953  template<typename NodeT>
1954  const NodeT* probeConstNode(const Coord& xyz) const
1955  {
1956  assert(BaseT::mTree);
1959  if (this->isHashed0(xyz)) {
1960  assert(mNode0);
1961  return reinterpret_cast<const NodeT*>(mNode0);
1962  } else if (this->isHashed1(xyz)) {
1963  assert(mNode1);
1964  return mNode1->template probeConstNodeAndCache<NodeT>(xyz, this->self());
1965  }
1966  return BaseT::mTree->root().template probeConstNodeAndCache<NodeT>(xyz, this->self());
1967  } else if ((std::is_same<NodeT, NodeT1>::value)) {
1968  if (this->isHashed1(xyz)) {
1969  assert(mNode1);
1970  return reinterpret_cast<const NodeT*>(mNode1);
1971  }
1972  return BaseT::mTree->root().template probeConstNodeAndCache<NodeT>(xyz, this->self());
1973  }
1974  return nullptr;
1976  }
1977 
1978  /// Remove all the cached nodes and invalidate the corresponding hash-keys.
1979  void clear() override
1980  {
1981  mKey0 = Coord::max();
1982  mNode0 = nullptr;
1983  mKey1 = Coord::max();
1984  mNode1 = nullptr;
1985  }
1986 
1987 private:
1988  // Allow nodes to insert themselves into the cache.
1989  template<typename> friend class RootNode;
1990  template<typename, Index> friend class InternalNode;
1991  template<typename, Index> friend class LeafNode;
1992  // Allow trees to deregister themselves.
1993  template<typename> friend class Tree;
1994 
1995  // This private method is merely for convenience.
1996  inline ValueAccessor2& self() const { return const_cast<ValueAccessor2&>(*this); }
1997 
1998  void getNode(const NodeT0*& node) { node = mNode0; }
1999  void getNode(const NodeT1*& node) { node = mNode1; }
2000  void getNode(const RootNodeT*& node)
2001  {
2002  node = (BaseT::mTree ? &BaseT::mTree->root() : nullptr);
2003  }
2004  template<typename OtherNodeType> void getNode(const OtherNodeType*& node) { node = nullptr; }
2005 
2006  void eraseNode(const NodeT0*) { mKey0 = Coord::max(); mNode0 = nullptr; }
2007  void eraseNode(const NodeT1*) { mKey1 = Coord::max(); mNode1 = nullptr; }
2008  template<typename OtherNodeType> void eraseNode(const OtherNodeType*) {}
2009 
2010  /// Private copy method
2011  inline void copy(const ValueAccessor2& other)
2012  {
2013  mKey0 = other.mKey0;
2014  mNode0 = other.mNode0;
2015  mKey1 = other.mKey1;
2016  mNode1 = other.mNode1;
2017  }
2018 
2019  /// Prevent this accessor from calling Tree::releaseCache() on a tree that
2020  /// no longer exists. (Called by mTree when it is destroyed.)
2021  void release() override
2022  {
2023  this->BaseT::release();
2024  this->clear();
2025  }
2026 
2027  /// Cache the given node, which should lie along the path from the root node to
2028  /// the node containing voxel (x, y, z).
2029  /// @note This operation is not mutex-protected and is intended to be called
2030  /// only by nodes and only in the context of a getValue() or setValue() call.
2031  inline void insert(const Coord& xyz, const NodeT0* node)
2032  {
2033  assert(node);
2034  mKey0 = xyz & ~(NodeT0::DIM-1);
2035  mNode0 = node;
2036  }
2037  inline void insert(const Coord& xyz, const NodeT1* node)
2038  {
2039  assert(node);
2040  mKey1 = xyz & ~(NodeT1::DIM-1);
2041  mNode1 = node;
2042  }
2043  /// No-op in case a tree traversal attemps to insert a node that
2044  /// is not cached by the ValueAccessor
2045  template<typename NodeT> inline void insert(const Coord&, const NodeT*) {}
2046 
2047  inline bool isHashed0(const Coord& xyz) const
2048  {
2049  return (xyz[0] & ~Coord::ValueType(NodeT0::DIM-1)) == mKey0[0]
2050  && (xyz[1] & ~Coord::ValueType(NodeT0::DIM-1)) == mKey0[1]
2051  && (xyz[2] & ~Coord::ValueType(NodeT0::DIM-1)) == mKey0[2];
2052  }
2053  inline bool isHashed1(const Coord& xyz) const
2054  {
2055  return (xyz[0] & ~Coord::ValueType(NodeT1::DIM-1)) == mKey1[0]
2056  && (xyz[1] & ~Coord::ValueType(NodeT1::DIM-1)) == mKey1[1]
2057  && (xyz[2] & ~Coord::ValueType(NodeT1::DIM-1)) == mKey1[2];
2058  }
2059  mutable Coord mKey0;
2060  mutable const NodeT0* mNode0;
2061  mutable Coord mKey1;
2062  mutable const NodeT1* mNode1;
2063 }; // ValueAccessor2
2064 
2065 
2066 /// @brief Value accessor with three levels of node caching.
2067 /// @details The node cache levels are specified by L0, L1, and L2
2068 /// with the default values 0, 1 and 2 (defined in the forward declaration)
2069 /// corresponding to a LeafNode, its parent InternalNode, and its parent InternalNode.
2070 /// Since the default configuration of all typed trees and grids, e.g.,
2071 /// FloatTree or FloatGrid, has a depth of four, this value accessor is the one
2072 /// used by default.
2073 ///
2074 /// @note This class is for experts only and should rarely be used
2075 /// directly. Instead use ValueAccessor with its default template arguments
2076 template<typename _TreeType, bool IsSafe, Index L0, Index L1, Index L2>
2078 {
2079 public:
2080  static_assert(_TreeType::DEPTH >= 4, "cache size exceeds tree depth");
2081  static_assert(L0 < L1, "invalid cache level");
2082  static_assert(L1 < L2, "invalid cache level");
2083  static_assert(L2 < _TreeType::RootNodeType::LEVEL, "invalid cache level");
2084 
2085  using TreeType = _TreeType;
2086  using ValueType = typename TreeType::ValueType;
2087  using RootNodeT = typename TreeType::RootNodeType;
2088  using LeafNodeT = typename TreeType::LeafNodeType;
2090  using InvTreeT = typename RootNodeT::NodeChainType;
2091  using NodeT0 = typename InvTreeT::template Get<L0>;
2092  using NodeT1 = typename InvTreeT::template Get<L1>;
2093  using NodeT2 = typename InvTreeT::template Get<L2>;
2094 
2095  /// Constructor from a tree
2097  mKey0(Coord::max()), mNode0(nullptr),
2098  mKey1(Coord::max()), mNode1(nullptr),
2099  mKey2(Coord::max()), mNode2(nullptr) {}
2100 
2101  /// Copy constructor
2102  ValueAccessor3(const ValueAccessor3& other) : BaseT(other) { this->copy(other); }
2103 
2104  /// Assignment operator
2106  {
2107  if (&other != this) {
2108  this->BaseT::operator=(other);
2109  this->copy(other);
2110  }
2111  return *this;
2112  }
2113 
2114  /// Return the number of cache levels employed by this ValueAccessor
2115  static Index numCacheLevels() { return 3; }
2116 
2117  /// Virtual destructor
2118  ~ValueAccessor3() override = default;
2119 
2120  /// Return @c true if any of the nodes along the path to the given
2121  /// voxel have been cached.
2122  bool isCached(const Coord& xyz) const
2123  {
2124  assert(BaseT::mTree);
2125  return this->isHashed2(xyz) || this->isHashed1(xyz) || this->isHashed0(xyz);
2126  }
2127 
2128  /// Return the value of the voxel at the given coordinates.
2129  const ValueType& getValue(const Coord& xyz) const
2130  {
2131  assert(BaseT::mTree);
2132  if (this->isHashed0(xyz)) {
2133  assert(mNode0);
2134  return mNode0->getValueAndCache(xyz, this->self());
2135  } else if (this->isHashed1(xyz)) {
2136  assert(mNode1);
2137  return mNode1->getValueAndCache(xyz, this->self());
2138  } else if (this->isHashed2(xyz)) {
2139  assert(mNode2);
2140  return mNode2->getValueAndCache(xyz, this->self());
2141  }
2142  return BaseT::mTree->root().getValueAndCache(xyz, this->self());
2143  }
2144 
2145  /// Return the active state of the voxel at the given coordinates.
2146  bool isValueOn(const Coord& xyz) const
2147  {
2148  assert(BaseT::mTree);
2149  if (this->isHashed0(xyz)) {
2150  assert(mNode0);
2151  return mNode0->isValueOnAndCache(xyz, this->self());
2152  } else if (this->isHashed1(xyz)) {
2153  assert(mNode1);
2154  return mNode1->isValueOnAndCache(xyz, this->self());
2155  } else if (this->isHashed2(xyz)) {
2156  assert(mNode2);
2157  return mNode2->isValueOnAndCache(xyz, this->self());
2158  }
2159  return BaseT::mTree->root().isValueOnAndCache(xyz, this->self());
2160  }
2161 
2162  /// Return the active state of the voxel as well as its value
2163  bool probeValue(const Coord& xyz, ValueType& value) const
2164  {
2165  assert(BaseT::mTree);
2166  if (this->isHashed0(xyz)) {
2167  assert(mNode0);
2168  return mNode0->probeValueAndCache(xyz, value, this->self());
2169  } else if (this->isHashed1(xyz)) {
2170  assert(mNode1);
2171  return mNode1->probeValueAndCache(xyz, value, this->self());
2172  } else if (this->isHashed2(xyz)) {
2173  assert(mNode2);
2174  return mNode2->probeValueAndCache(xyz, value, this->self());
2175  }
2176  return BaseT::mTree->root().probeValueAndCache(xyz, value, this->self());
2177  }
2178 
2179  /// Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides,
2180  /// or -1 if (x, y, z) isn't explicitly represented in the tree (i.e., if it is
2181  /// implicitly a background voxel).
2182  int getValueDepth(const Coord& xyz) const
2183  {
2184  assert(BaseT::mTree);
2185  if (this->isHashed0(xyz)) {
2186  assert(mNode0);
2187  return RootNodeT::LEVEL - mNode0->getValueLevelAndCache(xyz, this->self());
2188  } else if (this->isHashed1(xyz)) {
2189  assert(mNode1);
2190  return RootNodeT::LEVEL - mNode1->getValueLevelAndCache(xyz, this->self());
2191  } else if (this->isHashed2(xyz)) {
2192  assert(mNode2);
2193  return RootNodeT::LEVEL - mNode2->getValueLevelAndCache(xyz, this->self());
2194  }
2195  return BaseT::mTree->root().getValueDepthAndCache(xyz, this->self());
2196  }
2197 
2198  /// Return @c true if the value of voxel (x, y, z) resides at the leaf level
2199  /// of the tree, i.e., if it is not a tile value.
2200  bool isVoxel(const Coord& xyz) const
2201  {
2202  assert(BaseT::mTree);
2203  if (this->isHashed0(xyz)) {
2204  assert(mNode0);
2205  return mNode0->getValueLevelAndCache(xyz, this->self())==0;
2206  } else if (this->isHashed1(xyz)) {
2207  assert(mNode1);
2208  return mNode1->getValueLevelAndCache(xyz, this->self())==0;
2209  } else if (this->isHashed2(xyz)) {
2210  assert(mNode2);
2211  return mNode2->getValueLevelAndCache(xyz, this->self())==0;
2212  }
2213  return BaseT::mTree->root().getValueDepthAndCache(xyz, this->self()) ==
2214  static_cast<int>(RootNodeT::LEVEL);
2215  }
2216 
2217  //@{
2218  /// Set the value of the voxel at the given coordinates and mark the voxel as active.
2219  void setValue(const Coord& xyz, const ValueType& value)
2220  {
2221  assert(BaseT::mTree);
2222  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
2223  if (this->isHashed0(xyz)) {
2224  assert(mNode0);
2225  const_cast<NodeT0*>(mNode0)->setValueAndCache(xyz, value, *this);
2226  } else if (this->isHashed1(xyz)) {
2227  assert(mNode1);
2228  const_cast<NodeT1*>(mNode1)->setValueAndCache(xyz, value, *this);
2229  } else if (this->isHashed2(xyz)) {
2230  assert(mNode2);
2231  const_cast<NodeT2*>(mNode2)->setValueAndCache(xyz, value, *this);
2232  } else {
2233  BaseT::mTree->root().setValueAndCache(xyz, value, *this);
2234  }
2235  }
2236  void setValueOn(const Coord& xyz, const ValueType& value) { this->setValue(xyz, value); }
2237  //@}
2238 
2239  /// Set the value of the voxel at the given coordinate but preserves its active state.
2240  void setValueOnly(const Coord& xyz, const ValueType& value)
2241  {
2242  assert(BaseT::mTree);
2243  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
2244  if (this->isHashed0(xyz)) {
2245  assert(mNode0);
2246  const_cast<NodeT0*>(mNode0)->setValueOnlyAndCache(xyz, value, *this);
2247  } else if (this->isHashed1(xyz)) {
2248  assert(mNode1);
2249  const_cast<NodeT1*>(mNode1)->setValueOnlyAndCache(xyz, value, *this);
2250  } else if (this->isHashed2(xyz)) {
2251  assert(mNode2);
2252  const_cast<NodeT2*>(mNode2)->setValueOnlyAndCache(xyz, value, *this);
2253  } else {
2254  BaseT::mTree->root().setValueOnlyAndCache(xyz, value, *this);
2255  }
2256  }
2257 
2258  /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
2259  void setValueOff(const Coord& xyz, const ValueType& value)
2260  {
2261  assert(BaseT::mTree);
2262  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
2263  if (this->isHashed0(xyz)) {
2264  assert(mNode0);
2265  const_cast<NodeT0*>(mNode0)->setValueOffAndCache(xyz, value, *this);
2266  } else if (this->isHashed1(xyz)) {
2267  assert(mNode1);
2268  const_cast<NodeT1*>(mNode1)->setValueOffAndCache(xyz, value, *this);
2269  } else if (this->isHashed2(xyz)) {
2270  assert(mNode2);
2271  const_cast<NodeT2*>(mNode2)->setValueOffAndCache(xyz, value, *this);
2272  } else {
2273  BaseT::mTree->root().setValueOffAndCache(xyz, value, *this);
2274  }
2275  }
2276 
2277  /// @brief Apply a functor to the value of the voxel at the given coordinates
2278  /// and mark the voxel as active.
2279  /// @details See Tree::modifyValue() for details.
2280  template<typename ModifyOp>
2281  void modifyValue(const Coord& xyz, const ModifyOp& op)
2282  {
2283  assert(BaseT::mTree);
2284  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
2285  if (this->isHashed0(xyz)) {
2286  assert(mNode0);
2287  const_cast<NodeT0*>(mNode0)->modifyValueAndCache(xyz, op, *this);
2288  } else if (this->isHashed1(xyz)) {
2289  assert(mNode1);
2290  const_cast<NodeT1*>(mNode1)->modifyValueAndCache(xyz, op, *this);
2291  } else if (this->isHashed2(xyz)) {
2292  assert(mNode2);
2293  const_cast<NodeT2*>(mNode2)->modifyValueAndCache(xyz, op, *this);
2294  } else {
2295  BaseT::mTree->root().modifyValueAndCache(xyz, op, *this);
2296  }
2297  }
2298 
2299  /// @brief Apply a functor to the voxel at the given coordinates.
2300  /// @details See Tree::modifyValueAndActiveState() for details.
2301  template<typename ModifyOp>
2302  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
2303  {
2304  assert(BaseT::mTree);
2305  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
2306  if (this->isHashed0(xyz)) {
2307  assert(mNode0);
2308  const_cast<NodeT0*>(mNode0)->modifyValueAndActiveStateAndCache(xyz, op, *this);
2309  } else if (this->isHashed1(xyz)) {
2310  assert(mNode1);
2311  const_cast<NodeT1*>(mNode1)->modifyValueAndActiveStateAndCache(xyz, op, *this);
2312  } else if (this->isHashed2(xyz)) {
2313  assert(mNode2);
2314  const_cast<NodeT2*>(mNode2)->modifyValueAndActiveStateAndCache(xyz, op, *this);
2315  } else {
2316  BaseT::mTree->root().modifyValueAndActiveStateAndCache(xyz, op, *this);
2317  }
2318  }
2319 
2320  /// Set the active state of the voxel at the given coordinates without changing its value.
2321  void setActiveState(const Coord& xyz, bool on = true)
2322  {
2323  assert(BaseT::mTree);
2324  static_assert(!BaseT::IsConstTree, "can't modify a const tree's values");
2325  if (this->isHashed0(xyz)) {
2326  assert(mNode0);
2327  const_cast<NodeT0*>(mNode0)->setActiveStateAndCache(xyz, on, *this);
2328  } else if (this->isHashed1(xyz)) {
2329  assert(mNode1);
2330  const_cast<NodeT1*>(mNode1)->setActiveStateAndCache(xyz, on, *this);
2331  } else if (this->isHashed2(xyz)) {
2332  assert(mNode2);
2333  const_cast<NodeT2*>(mNode2)->setActiveStateAndCache(xyz, on, *this);
2334  } else {
2335  BaseT::mTree->root().setActiveStateAndCache(xyz, on, *this);
2336  }
2337  }
2338  /// Mark the voxel at the given coordinates as active without changing its value.
2339  void setValueOn(const Coord& xyz) { this->setActiveState(xyz, true); }
2340  /// Mark the voxel at the given coordinates as inactive without changing its value.
2341  void setValueOff(const Coord& xyz) { this->setActiveState(xyz, false); }
2342 
2343  /// Return the cached node of type @a NodeType. [Mainly for internal use]
2344  template<typename NodeT>
2345  NodeT* getNode()
2346  {
2347  const NodeT* node = nullptr;
2348  this->getNode(node);
2349  return const_cast<NodeT*>(node);
2350  }
2351 
2352  /// Cache the given node, which should lie along the path from the root node to
2353  /// the node containing voxel (x, y, z). [Mainly for internal use]
2354  template<typename NodeT>
2355  void insertNode(const Coord& xyz, NodeT& node) { this->insert(xyz, &node); }
2356 
2357  /// If a node of the given type exists in the cache, remove it, so that
2358  /// isCached(xyz) returns @c false for any voxel (x, y, z) contained in
2359  /// that node. [Mainly for internal use]
2360  template<typename NodeT>
2361  void eraseNode()
2362  {
2363  const NodeT* node = nullptr;
2364  this->eraseNode(node);
2365  }
2366 
2367  /// @brief Add the specified leaf to this tree, possibly creating a child branch
2368  /// in the process. If the leaf node already exists, replace it.
2369  void addLeaf(LeafNodeT* leaf)
2370  {
2371  assert(BaseT::mTree);
2372  static_assert(!BaseT::IsConstTree, "can't add a node to a const tree");
2373  if (this->isHashed1(leaf->origin())) {
2374  assert(mNode1);
2375  return const_cast<NodeT1*>(mNode1)->addLeafAndCache(leaf, *this);
2376  } else if (this->isHashed2(leaf->origin())) {
2377  assert(mNode2);
2378  return const_cast<NodeT2*>(mNode2)->addLeafAndCache(leaf, *this);
2379  }
2380  BaseT::mTree->root().addLeafAndCache(leaf, *this);
2381  }
2382 
2383  /// @brief Add a tile at the specified tree level that contains voxel (x, y, z),
2384  /// possibly deleting existing nodes or creating new nodes in the process.
2385  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state)
2386  {
2387  assert(BaseT::mTree);
2388  static_assert(!BaseT::IsConstTree, "can't add a tile to a const tree");
2389  if (this->isHashed1(xyz)) {
2390  assert(mNode1);
2391  return const_cast<NodeT1*>(mNode1)->addTileAndCache(level, xyz, value, state, *this);
2392  } if (this->isHashed2(xyz)) {
2393  assert(mNode2);
2394  return const_cast<NodeT2*>(mNode2)->addTileAndCache(level, xyz, value, state, *this);
2395  }
2396  BaseT::mTree->root().addTileAndCache(level, xyz, value, state, *this);
2397  }
2398 
2399  /// @brief @return the leaf node that contains voxel (x, y, z) and
2400  /// if it doesn't exist, create it, but preserve the values and
2401  /// active states of all voxels.
2402  ///
2403  /// Use this method to preallocate a static tree topology over which to
2404  /// safely perform multithreaded processing.
2405  LeafNodeT* touchLeaf(const Coord& xyz)
2406  {
2407  assert(BaseT::mTree);
2408  static_assert(!BaseT::IsConstTree, "can't get a non-const node from a const tree");
2409  if (this->isHashed0(xyz)) {
2410  assert(mNode0);
2411  return const_cast<NodeT0*>(mNode0);
2412  } else if (this->isHashed1(xyz)) {
2413  assert(mNode1);
2414  return const_cast<NodeT1*>(mNode1)->touchLeafAndCache(xyz, *this);
2415  } else if (this->isHashed2(xyz)) {
2416  assert(mNode2);
2417  return const_cast<NodeT2*>(mNode2)->touchLeafAndCache(xyz, *this);
2418  }
2419  return BaseT::mTree->root().touchLeafAndCache(xyz, *this);
2420  }
2421  /// @brief @return a pointer to the node of the specified type that contains
2422  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
2423  template<typename NodeT>
2424  NodeT* probeNode(const Coord& xyz)
2425  {
2426  assert(BaseT::mTree);
2427  static_assert(!BaseT::IsConstTree, "can't get a non-const node from a const tree");
2430  if (this->isHashed0(xyz)) {
2431  assert(mNode0);
2432  return reinterpret_cast<NodeT*>(const_cast<NodeT0*>(mNode0));
2433  } else if (this->isHashed1(xyz)) {
2434  assert(mNode1);
2435  return const_cast<NodeT1*>(mNode1)->template probeNodeAndCache<NodeT>(xyz, *this);
2436  } else if (this->isHashed2(xyz)) {
2437  assert(mNode2);
2438  return const_cast<NodeT2*>(mNode2)->template probeNodeAndCache<NodeT>(xyz, *this);
2439  }
2440  return BaseT::mTree->root().template probeNodeAndCache<NodeT>(xyz, *this);
2441  } else if ((std::is_same<NodeT, NodeT1>::value)) {
2442  if (this->isHashed1(xyz)) {
2443  assert(mNode1);
2444  return reinterpret_cast<NodeT*>(const_cast<NodeT1*>(mNode1));
2445  } else if (this->isHashed2(xyz)) {
2446  assert(mNode2);
2447  return const_cast<NodeT2*>(mNode2)->template probeNodeAndCache<NodeT>(xyz, *this);
2448  }
2449  return BaseT::mTree->root().template probeNodeAndCache<NodeT>(xyz, *this);
2450  } else if ((std::is_same<NodeT, NodeT2>::value)) {
2451  if (this->isHashed2(xyz)) {
2452  assert(mNode2);
2453  return reinterpret_cast<NodeT*>(const_cast<NodeT2*>(mNode2));
2454  }
2455  return BaseT::mTree->root().template probeNodeAndCache<NodeT>(xyz, *this);
2456  }
2457  return nullptr;
2459  }
2460  /// @brief @return a pointer to the leaf node that contains
2461  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
2462  LeafNodeT* probeLeaf(const Coord& xyz) { return this->template probeNode<LeafNodeT>(xyz); }
2463 
2464  /// @brief @return a const pointer to the node of the specified type that contains
2465  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
2466  template<typename NodeT>
2467  const NodeT* probeConstNode(const Coord& xyz) const
2468  {
2469  assert(BaseT::mTree);
2472  if (this->isHashed0(xyz)) {
2473  assert(mNode0);
2474  return reinterpret_cast<const NodeT*>(mNode0);
2475  } else if (this->isHashed1(xyz)) {
2476  assert(mNode1);
2477  return mNode1->template probeConstNodeAndCache<NodeT>(xyz, this->self());
2478  } else if (this->isHashed2(xyz)) {
2479  assert(mNode2);
2480  return mNode2->template probeConstNodeAndCache<NodeT>(xyz, this->self());
2481  }
2482  return BaseT::mTree->root().template probeConstNodeAndCache<NodeT>(xyz, this->self());
2483  } else if ((std::is_same<NodeT, NodeT1>::value)) {
2484  if (this->isHashed1(xyz)) {
2485  assert(mNode1);
2486  return reinterpret_cast<const NodeT*>(mNode1);
2487  } else if (this->isHashed2(xyz)) {
2488  assert(mNode2);
2489  return mNode2->template probeConstNodeAndCache<NodeT>(xyz, this->self());
2490  }
2491  return BaseT::mTree->root().template probeConstNodeAndCache<NodeT>(xyz, this->self());
2492  } else if ((std::is_same<NodeT, NodeT2>::value)) {
2493  if (this->isHashed2(xyz)) {
2494  assert(mNode2);
2495  return reinterpret_cast<const NodeT*>(mNode2);
2496  }
2497  return BaseT::mTree->root().template probeConstNodeAndCache<NodeT>(xyz, this->self());
2498  }
2499  return nullptr;
2501  }
2502  /// @brief @return a const pointer to the leaf node that contains
2503  /// voxel (x, y, z) and if it doesn't exist, return @c nullptr.
2504  const LeafNodeT* probeConstLeaf(const Coord& xyz) const
2505  {
2506  return this->template probeConstNode<LeafNodeT>(xyz);
2507  }
2508  const LeafNodeT* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
2509 
2510  /// Remove all the cached nodes and invalidate the corresponding hash-keys.
2511  void clear() override
2512  {
2513  mKey0 = Coord::max();
2514  mNode0 = nullptr;
2515  mKey1 = Coord::max();
2516  mNode1 = nullptr;
2517  mKey2 = Coord::max();
2518  mNode2 = nullptr;
2519  }
2520 
2521 private:
2522  // Allow nodes to insert themselves into the cache.
2523  template<typename> friend class RootNode;
2524  template<typename, Index> friend class InternalNode;
2525  template<typename, Index> friend class LeafNode;
2526  // Allow trees to deregister themselves.
2527  template<typename> friend class Tree;
2528 
2529  // This private method is merely for convenience.
2530  inline ValueAccessor3& self() const { return const_cast<ValueAccessor3&>(*this); }
2531 
2532  /// Private copy method
2533  inline void copy(const ValueAccessor3& other)
2534  {
2535  mKey0 = other.mKey0;
2536  mNode0 = other.mNode0;
2537  mKey1 = other.mKey1;
2538  mNode1 = other.mNode1;
2539  mKey2 = other.mKey2;
2540  mNode2 = other.mNode2;
2541  }
2542 
2543  /// Prevent this accessor from calling Tree::releaseCache() on a tree that
2544  /// no longer exists. (Called by mTree when it is destroyed.)
2545  void release() override
2546  {
2547  this->BaseT::release();
2548  this->clear();
2549  }
2550  void getNode(const NodeT0*& node) { node = mNode0; }
2551  void getNode(const NodeT1*& node) { node = mNode1; }
2552  void getNode(const NodeT2*& node) { node = mNode2; }
2553  void getNode(const RootNodeT*& node)
2554  {
2555  node = (BaseT::mTree ? &BaseT::mTree->root() : nullptr);
2556  }
2557  template<typename OtherNodeType> void getNode(const OtherNodeType*& node) { node = nullptr; }
2558 
2559  void eraseNode(const NodeT0*) { mKey0 = Coord::max(); mNode0 = nullptr; }
2560  void eraseNode(const NodeT1*) { mKey1 = Coord::max(); mNode1 = nullptr; }
2561  void eraseNode(const NodeT2*) { mKey2 = Coord::max(); mNode2 = nullptr; }
2562  template<typename OtherNodeType> void eraseNode(const OtherNodeType*) {}
2563 
2564  /// Cache the given node, which should lie along the path from the root node to
2565  /// the node containing voxel (x, y, z).
2566  /// @note This operation is not mutex-protected and is intended to be called
2567  /// only by nodes and only in the context of a getValue() or setValue() call.
2568  inline void insert(const Coord& xyz, const NodeT0* node)
2569  {
2570  assert(node);
2571  mKey0 = xyz & ~(NodeT0::DIM-1);
2572  mNode0 = node;
2573  }
2574  inline void insert(const Coord& xyz, const NodeT1* node)
2575  {
2576  assert(node);
2577  mKey1 = xyz & ~(NodeT1::DIM-1);
2578  mNode1 = node;
2579  }
2580  inline void insert(const Coord& xyz, const NodeT2* node)
2581  {
2582  assert(node);
2583  mKey2 = xyz & ~(NodeT2::DIM-1);
2584  mNode2 = node;
2585  }
2586  /// No-op in case a tree traversal attemps to insert a node that
2587  /// is not cached by the ValueAccessor
2588  template<typename OtherNodeType>
2589  inline void insert(const Coord&, const OtherNodeType*)
2590  {
2591  }
2592  inline bool isHashed0(const Coord& xyz) const
2593  {
2594  return (xyz[0] & ~Coord::ValueType(NodeT0::DIM-1)) == mKey0[0]
2595  && (xyz[1] & ~Coord::ValueType(NodeT0::DIM-1)) == mKey0[1]
2596  && (xyz[2] & ~Coord::ValueType(NodeT0::DIM-1)) == mKey0[2];
2597  }
2598  inline bool isHashed1(const Coord& xyz) const
2599  {
2600  return (xyz[0] & ~Coord::ValueType(NodeT1::DIM-1)) == mKey1[0]
2601  && (xyz[1] & ~Coord::ValueType(NodeT1::DIM-1)) == mKey1[1]
2602  && (xyz[2] & ~Coord::ValueType(NodeT1::DIM-1)) == mKey1[2];
2603  }
2604  inline bool isHashed2(const Coord& xyz) const
2605  {
2606  return (xyz[0] & ~Coord::ValueType(NodeT2::DIM-1)) == mKey2[0]
2607  && (xyz[1] & ~Coord::ValueType(NodeT2::DIM-1)) == mKey2[1]
2608  && (xyz[2] & ~Coord::ValueType(NodeT2::DIM-1)) == mKey2[2];
2609  }
2610  mutable Coord mKey0;
2611  mutable const NodeT0* mNode0;
2612  mutable Coord mKey1;
2613  mutable const NodeT1* mNode1;
2614  mutable Coord mKey2;
2615  mutable const NodeT2* mNode2;
2616 }; // ValueAccessor3
2617 
2618 } // namespace tree
2619 } // namespace OPENVDB_VERSION_NAME
2620 } // namespace openvdb
2621 
2622 #endif // OPENVDB_TREE_VALUEACCESSOR_HAS_BEEN_INCLUDED
const NodeType * probeConstNode(const Coord &xyz)
Definition: ValueAccessor.h:905
void getNode(const RootNodeType *&node) const
Definition: ValueAccessor.h:859
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: ValueAccessor.h:1364
friend class InternalNode
Definition: ValueAccessor.h:1990
bool isCached(const Coord &xyz) const
Definition: ValueAccessor.h:842
ValueAccessorBase(TreeType &tree)
Definition: ValueAccessor.h:97
void modifyValue(const Coord &xyz, const ModifyOp &op)
Definition: ValueAccessor.h:954
typename TreeType::LeafNodeType LeafNodeT
Definition: ValueAccessor.h:2088
void eraseNode()
Definition: ValueAccessor.h:325
CacheItem(TreeCacheT &parent, const CacheItem &other)
Copy another CacheItem&#39;s node pointers and hash keys, but not its parent pointer. ...
Definition: ValueAccessor.h:538
int getValueDepth(const Coord &xyz) const
Definition: ValueAccessor.h:1295
Index32 Index
Definition: Types.h:54
friend class RootNode
Definition: ValueAccessor.h:2523
const LeafNodeT * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z), or nullptr if no such node exists...
Definition: ValueAccessor.h:384
void insertNode(const Coord &xyz, NodeT &node)
Definition: ValueAccessor.h:1830
const NodeT * probeConstNode(const Coord &xyz)
Definition: ValueAccessor.h:673
void setActiveState(const Coord &xyz, bool on)
Set the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:793
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: ValueAccessor.h:1765
bool isVoxel(const Coord &xyz) const
Definition: ValueAccessor.h:1696
void setValueOn(const Coord &xyz, const ValueType &value)
Definition: ValueAccessor.h:951
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don&#39;t change its value.
Definition: ValueAccessor.h:1404
typename TreeType::ValueType ValueType
Definition: ValueAccessor.h:2086
static Index numCacheLevels()
Return the number of cache levels employed by this ValueAccessor.
Definition: ValueAccessor.h:2115
const LeafNodeT * probeConstLeaf(const Coord &xyz) const
Definition: ValueAccessor.h:1183
LeafNodeT * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one, but preserve the values and active states of all voxels.
Definition: ValueAccessor.h:348
const NodeT * probeConstNode(const Coord &xyz) const
Definition: ValueAccessor.h:1172
void insertNode(const Coord &xyz, NodeT &node)
Definition: ValueAccessor.h:1420
void setValueOnly(const Coord &xyz, const ValueType &value)
Definition: ValueAccessor.h:739
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: ValueAccessor.h:1107
ValueAccessor1 & operator=(const ValueAccessor1 &other)
Assignment operator.
Definition: ValueAccessor.h:1239
void addLeaf(LeafNodeT *leaf)
Add the specified leaf to this tree, possibly creating a child branch in the process. If the leaf node already exists, replace it.
Definition: ValueAccessor.h:2369
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Add a tile at the specified tree level that contains voxel (x, y, z), possibly deleting existing node...
Definition: ValueAccessor.h:337
bool isVoxel(const Coord &xyz) const
Definition: ValueAccessor.h:1307
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinate but don&#39;t change its active state.
Definition: ValueAccessor.h:1078
const LeafNodeT * probeLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z), or nullptr if no such node exists...
Definition: ValueAccessor.h:389
CacheItem(TreeCacheT &parent)
Definition: ValueAccessor.h:528
Definition: Tree.h:177
int getValueDepth(const Coord &xyz) const
Definition: ValueAccessor.h:2182
ValueAccessor & operator=(const ValueAccessor &other)
Definition: ValueAccessor.h:202
typename NodeType::ValueType ValueType
Definition: ValueAccessor.h:524
typename RootNodeType::LeafNodeType LeafNodeType
Definition: ValueAccessor.h:830
LeafNodeT * touchLeaf(const Coord &xyz)
Definition: ValueAccessor.h:1874
NodeType * probeNode(const Coord &xyz)
Definition: ValueAccessor.h:896
const ValueType & getValue(const Coord &xyz)
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:595
LeafNodeT * probeLeaf(const Coord &xyz)
Definition: ValueAccessor.h:1916
const ValueType & getValue(const Coord &xyz)
Definition: ValueAccessor.h:933
const LeafNodeT * probeLeaf(const Coord &xyz) const
Definition: ValueAccessor.h:1188
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Definition: ValueAccessor.h:868
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don&#39;t change its value.
Definition: ValueAccessor.h:300
TreeType TreeType
Definition: ValueAccessor.h:1219
void setValueOn(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:1074
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Add a tile at the specified tree level that contains voxel (x, y, z), possibly deleting existing node...
Definition: ValueAccessor.h:1443
bool isVoxel(const Coord &xyz)
Definition: ValueAccessor.h:927
bool isValueOn(const Coord &xyz)
Definition: ValueAccessor.h:916
LeafNodeType * probeLeaf(const Coord &xyz)
Definition: ValueAccessor.h:882
typename tbb::null_mutex::scoped_lock LockT
Definition: ValueAccessor.h:192
Value accessor with two levels of node caching.
Definition: ValueAccessor.h:54
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:1712
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:1637
typename TreeType::ValueType ValueType
Definition: ValueAccessor.h:1596
static Index numCacheLevels()
Return the number of cache levels employed by this ValueAccessor.
Definition: ValueAccessor.h:1613
friend class RootNode
Definition: ValueAccessor.h:402
NodeT * probeNode(const Coord &xyz)
Definition: ValueAccessor.h:1890
typename RootNodeT::NodeChainType InvTreeT
Definition: ValueAccessor.h:1600
void setValueOnly(const Coord &xyz, const ValueType &value)
Definition: ValueAccessor.h:945
friend class InternalNode
Definition: ValueAccessor.h:1523
bool probeValue(const Coord &xyz, ValueType &value) const
Return the active state of the voxel as well as its value.
Definition: ValueAccessor.h:1282
friend class LeafNode
Definition: ValueAccessor.h:1524
void erase(const NodeType *)
Erase the node at this level.
Definition: ValueAccessor.h:572
NodeT * probeNode(const Coord &xyz)
Definition: ValueAccessor.h:657
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:1320
LeafNodeType * probeLeaf(const Coord &xyz)
Definition: ValueAccessor.h:637
LeafNodeType * touchLeaf(const Coord &xyz)
Definition: ValueAccessor.h:875
void addLeaf(LeafNodeType *leaf)
Definition: ValueAccessor.h:604
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active without changing its value.
Definition: ValueAccessor.h:2339
typename TreeType::ValueType ValueType
Definition: ValueAccessor.h:1220
Value accessor with three levels of node caching.
Definition: ValueAccessor.h:56
int getValueDepth(const Coord &xyz) const
Definition: ValueAccessor.h:1681
friend class Tree
Definition: ValueAccessor.h:406
void getNode(const NodeType *&node) const
Return the cached node (if any) at this level.
Definition: ValueAccessor.h:581
void setValueOff(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as inactive.
Definition: ValueAccessor.h:1086
bool isCached(const Coord &xyz) const
Definition: ValueAccessor.h:1253
NodeT * getNode()
Return the cached node of type NodeType. [Mainly for internal use].
Definition: ValueAccessor.h:1127
typename TreeType::LeafNodeType LeafNodeT
Definition: ValueAccessor.h:1222
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinate but don&#39;t change its active state.
Definition: ValueAccessor.h:259
void erase(const RootNodeType *)
Definition: ValueAccessor.h:850
void clear() override
Remove all nodes from this cache, then reinsert the root node.
Definition: ValueAccessor.h:1194
void insertNode(const Coord &, NodeT &)
Definition: ValueAccessor.h:1131
NodeType * getNode()
Return the cached node of type NodeType. [Mainly for internal use].
Definition: ValueAccessor.h:304
void setActiveState(const Coord &xyz, bool on=true)
Set the active state of the voxel at the given coordinates without changing its value.
Definition: ValueAccessor.h:1799
typename TreeType::LeafNodeType LeafNodeT
Definition: ValueAccessor.h:1598
typename TreeType::RootNodeType RootNodeT
Definition: ValueAccessor.h:1006
bool probeValue(const Coord &xyz, ValueType &value) const
Return the active state of the voxel as well as its value.
Definition: ValueAccessor.h:2163
LeafNodeT * probeLeaf(const Coord &xyz)
Definition: ValueAccessor.h:1178
typename NodeType::LeafNodeType LeafNodeType
Definition: ValueAccessor.h:525
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don&#39;t change its value.
Definition: ValueAccessor.h:1406
TreeType * mTree
Definition: ValueAccessor.h:135
This accessor is thread-safe (at the cost of speed) for both reading and writing to a tree...
Definition: ValueAccessor.h:501
void insertNode(const Coord &xyz, NodeT &node)
Definition: ValueAccessor.h:2355
NodeT * probeNode(const Coord &xyz)
Definition: ValueAccessor.h:2424
void setValueOn(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:1726
void addLeaf(LeafNodeT *leaf)
Add the specified leaf to this tree, possibly creating a child branch in the process. If the leaf node already exists, replace it.
Definition: ValueAccessor.h:1434
void erase(const OtherNodeType *node)
Erase the node at another level of the cache.
Definition: ValueAccessor.h:575
bool isVoxel(const Coord &xyz) const
Definition: ValueAccessor.h:2200
bool probeValue(const Coord &xyz, ValueType &value)
Definition: ValueAccessor.h:922
int getValueDepth(const Coord &xyz)
Definition: ValueAccessor.h:911
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:1029
ValueAccessorBase(const ValueAccessorBase &other)
Definition: ValueAccessor.h:112
static Index numCacheLevels()
Return the number of cache levels employed by this accessor.
Definition: ValueAccessor.h:1015
static Index numCacheLevels()
Return the number of cache levels employed by this accessor.
Definition: ValueAccessor.h:213
const NodeT * probeNode(const Coord &xyz) const
Return a pointer to the node of the specified type that contains voxel (x, y, z), or nullptr if no su...
Definition: ValueAccessor.h:370
void eraseNode()
Definition: ValueAccessor.h:1426
void addLeaf(LeafNodeT *leaf)
Add the specified leaf to this tree, possibly creating a child branch in the process. If the leaf node already exists, replace it.
Definition: ValueAccessor.h:329
const NodeT * probeConstNode(const Coord &xyz) const
Definition: ValueAccessor.h:2467
ValueAccessorBase & operator=(const ValueAccessorBase &other)
Definition: ValueAccessor.h:117
NodeT * probeNode(const Coord &xyz)
Definition: ValueAccessor.h:1164
typename NodeVecT::Front RootNodeType
Definition: ValueAccessor.h:828
void addLeaf(LeafNodeT *leaf)
Add the specified leaf to this tree, possibly creating a child branch in the process. If the leaf node already exists, replace it.
Definition: ValueAccessor.h:1844
Value accessor with one level of node caching.
Definition: ValueAccessor.h:52
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:1651
TreeType TreeType
Definition: ValueAccessor.h:187
ValueAccessor2(TreeType &tree)
Constructor from a tree.
Definition: ValueAccessor.h:1605
Definition: ValueAccessor.h:182
int getValueDepth(const Coord &xyz) const
Definition: ValueAccessor.h:1052
void getNode(RootNodeType *&node)
Definition: ValueAccessor.h:854
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: ValueAccessor.h:285
LeafNodeT * touchLeaf(const Coord &xyz)
Definition: ValueAccessor.h:2405
void setActiveState(const Coord &xyz, bool on=true)
Set the active state of the voxel at the given coordinates but don&#39;t change its value.
Definition: ValueAccessor.h:1392
bool isCached(const Coord &) const
Return true if nodes along the path to the given voxel have been cached.
Definition: ValueAccessor.h:1026
CacheItem & copy(TreeCacheT &parent, const CacheItem &other)
Definition: ValueAccessor.h:835
typename RootNodeT::NodeChainType InvTreeT
Definition: ValueAccessor.h:1224
const NodeT * probeConstLeaf(const Coord &xyz) const
Definition: ValueAccessor.h:1921
NodeT * getNode()
Return the cached node of type NodeType. [Mainly for internal use].
Definition: ValueAccessor.h:1820
void insert(const Coord &xyz, const NodeType *node)
Cache the given node at this level.
Definition: ValueAccessor.h:562
bool probeValue(const Coord &xyz, ValueType &value) const
Return the active state of the voxel as well as its value.
Definition: ValueAccessor.h:1665
LeafNodeT * probeLeaf(const Coord &xyz)
Definition: ValueAccessor.h:2462
ValueAccessor(const ValueAccessor &other)
Definition: ValueAccessor.h:200
bool probeValue(const Coord &xyz, ValueType &value) const
Return the active state of the voxel as well as its value.
Definition: ValueAccessor.h:229
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don&#39;t change its value.
Definition: ValueAccessor.h:1122
std::numeric_limits< Int32 > CoordLimits
Definition: ValueAccessor.h:526
const LeafNodeT * probeConstLeaf(const Coord &xyz) const
Definition: ValueAccessor.h:1507
void eraseNode()
Definition: ValueAccessor.h:2361
void getNode(OtherNodeType *&node)
Forward the request to another level of the cache.
Definition: ValueAccessor.h:592
void setValue(const Coord &xyz, const ValueType &value)
Definition: ValueAccessor.h:939
void addLeaf(LeafNodeType *leaf)
Definition: ValueAccessor.h:861
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: ValueAccessor.h:2302
bool probeValue(const Coord &xyz, ValueType &value)
Return the active state and value of the voxel at the given coordinates.
Definition: ValueAccessor.h:698
bool isCached(const Coord &xyz) const
Definition: ValueAccessor.h:1630
TreeType & tree() const
Return a reference to the tree associated with this accessor.
Definition: ValueAccessor.h:110
bool isVoxel(const Coord &xyz) const
Definition: ValueAccessor.h:1060
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:2219
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:2129
ValueAccessor0(const ValueAccessor0 &other)
Definition: ValueAccessor.h:1012
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Definition: ValueAccessor.h:615
void setActiveState(const Coord &xyz, bool on)
Definition: ValueAccessor.h:976
ValueAccessor(TreeType &tree)
Definition: ValueAccessor.h:447
const NodeT * probeConstNode(const Coord &xyz) const
Definition: ValueAccessor.h:1954
friend class Tree
Definition: ValueAccessor.h:1198
LeafNodeT * touchLeaf(const Coord &xyz)
Definition: ValueAccessor.h:1456
Definition: Exceptions.h:13
ValueAccessorRW(TreeType &tree)
Definition: ValueAccessor.h:504
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:1271
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
SIMD Intrinsic Headers.
Definition: Platform.h:115
typename RootNodeType::ValueType ValueType
Definition: ValueAccessor.h:829
static bool isSafe()
Return true if this accessor is safe, i.e. registered by the tree from which it is constructed...
Definition: ValueAccessor.h:95
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:219
const LeafNodeType * probeConstLeaf(const Coord &xyz)
Definition: ValueAccessor.h:889
ValueT value
Definition: GridBuilder.h:1287
void setValueOn(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:255
ValueAccessor3(const ValueAccessor3 &other)
Copy constructor.
Definition: ValueAccessor.h:2102
TreeType TreeType
Definition: ValueAccessor.h:1004
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:729
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: ValueAccessor.h:1097
NodeT * getNode()
Return the cached node of type NodeType. [Mainly for internal use].
Definition: ValueAccessor.h:2345
friend class LeafNode
Definition: ValueAccessor.h:404
ValueAccessor0(TreeType &tree)
Definition: ValueAccessor.h:1010
void setActiveState(const Coord &xyz, bool on=true)
Set the active state of the voxel at the given coordinates but don&#39;t change its value.
Definition: ValueAccessor.h:292
ValueAccessor(TreeType &tree)
Definition: ValueAccessor.h:471
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: ValueAccessor.h:769
const LeafNodeT * probeConstLeaf(const Coord &xyz) const
Definition: ValueAccessor.h:1945
LeafNodeType * touchLeaf(const Coord &xyz)
Definition: ValueAccessor.h:627
friend class InternalNode
Definition: ValueAccessor.h:403
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: ValueAccessor.h:276
ValueAccessor with no mutex and no node caching.
Definition: ValueAccessor.h:50
TreeType TreeType
Definition: ValueAccessor.h:2085
void setActiveState(const Coord &xyz, bool on=true)
Set the active state of the voxel at the given coordinates without changing its value.
Definition: ValueAccessor.h:2321
ValueAccessor2(const ValueAccessor2 &other)
Copy constructor.
Definition: ValueAccessor.h:1610
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: ValueAccessor.h:1783
void getNode(NodeType *&node)
Definition: ValueAccessor.h:583
void clear()
Erase the nodes at this and lower levels of the cache.
Definition: ValueAccessor.h:578
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinate but preserves its active state.
Definition: ValueAccessor.h:1730
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Add a tile at the specified tree level that contains voxel (x, y, z), possibly deleting existing node...
Definition: ValueAccessor.h:2385
LeafNodeT * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z), or nullptr if no such node exists...
Definition: ValueAccessor.h:379
bool probeValue(const Coord &xyz, ValueType &value) const
Return the active state and, in value, the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:1043
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: ValueAccessor.h:755
typename TreeType::RootNodeType RootNodeT
Definition: ValueAccessor.h:2087
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:226
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:1068
ValueAccessor(TreeType &tree)
Definition: ValueAccessor.h:195
bool isVoxel(const Coord &xyz)
Definition: ValueAccessor.h:718
typename TreeType::ValueType ValueType
Definition: ValueAccessor.h:1005
Definition: ValueAccessor.h:57
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don&#39;t change its value.
Definition: ValueAccessor.h:298
const NodeT * probeConstNode(const Coord &xyz) const
Definition: ValueAccessor.h:1493
void getNode(const NodeType *&node)
Definition: ValueAccessor.h:582
void setValueOn(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:2236
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: ValueAccessor.h:1379
ValueAccessor(TreeType &tree)
Definition: ValueAccessor.h:459
void setValueOff(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as inactive.
Definition: ValueAccessor.h:1348
NodeT * getNode()
Return the cached node of type NodeType. [Mainly for internal use].
Definition: ValueAccessor.h:1410
friend class InternalNode
Definition: ValueAccessor.h:2524
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinate but preserves its active state.
Definition: ValueAccessor.h:1335
friend class LeafNode
Definition: ValueAccessor.h:2525
ValueAccessor(const ValueAccessor &other)
Definition: ValueAccessor.h:448
ValueAccessor1(const ValueAccessor1 &other)
Copy constructor.
Definition: ValueAccessor.h:1233
void clear() override
Remove all the cached nodes and invalidate the corresponding hash-keys.
Definition: ValueAccessor.h:1514
friend class RootNode
Definition: ValueAccessor.h:1989
virtual void release()
Definition: ValueAccessor.h:133
typename TreeType::LeafNodeType LeafNodeT
Definition: ValueAccessor.h:189
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:116
friend class Tree
Definition: ValueAccessor.h:1993
virtual ~ValueAccessorBase()
Definition: ValueAccessor.h:102
ValueAccessor(const ValueAccessor &other)
Definition: ValueAccessor.h:472
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: ValueAccessor.h:2281
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:2146
ValueAccessor1(TreeType &tree)
Constructor from a tree.
Definition: ValueAccessor.h:1228
const NodeT * probeConstNode(const Coord &xyz) const
Return a pointer to the node of the specified type that contains voxel (x, y, z), or nullptr if no su...
Definition: ValueAccessor.h:364
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:107
const LeafNodeT * probeConstLeaf(const Coord &xyz) const
Definition: ValueAccessor.h:2504
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive without changing its value.
Definition: ValueAccessor.h:1816
const LeafNodeT * probeLeaf(const Coord &xyz) const
Definition: ValueAccessor.h:1511
ValueAccessor(const ValueAccessor &other)
Definition: ValueAccessor.h:460
friend class RootNode
Definition: ValueAccessor.h:1522
TreeType TreeType
Definition: ValueAccessor.h:1595
void insert(const Coord &xyz, const OtherNodeType *node)
Forward the given node to another level of the cache.
Definition: ValueAccessor.h:569
void setValueOn(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:1331
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Add a tile at the specified tree level that contains voxel (x, y, z), possibly deleting existing node...
Definition: ValueAccessor.h:1144
NodeT * probeNode(const Coord &xyz)
Return a pointer to the node of the specified type that contains voxel (x, y, z), or nullptr if no su...
Definition: ValueAccessor.h:358
void insertNode(const Coord &xyz, NodeType &node)
Definition: ValueAccessor.h:315
typename TreeType::RootNodeType RootNodeT
Definition: ValueAccessor.h:1597
int getValueDepth(const Coord &xyz) const
Definition: ValueAccessor.h:238
void setValueOn(const Coord &xyz, const ValueType &value)
Definition: ValueAccessor.h:749
const LeafNodeType * probeConstLeaf(const Coord &xyz)
Definition: ValueAccessor.h:647
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Definition: ValueAccessor.h:962
void eraseNode()
Definition: ValueAccessor.h:1836
void setValueOff(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as inactive.
Definition: ValueAccessor.h:266
NodeT * probeNode(const Coord &xyz)
Definition: ValueAccessor.h:1470
void setValueOff(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as inactive.
Definition: ValueAccessor.h:1746
bool isCached(const Coord &xyz) const
Definition: ValueAccessor.h:2122
ValueAccessor2 & operator=(const ValueAccessor2 &other)
Assignment operator.
Definition: ValueAccessor.h:1616
int getValueDepth(const Coord &xyz)
Definition: ValueAccessor.h:707
friend class LeafNode
Definition: ValueAccessor.h:1991
void insert(const Coord &, const OtherNodeType *)
Definition: ValueAccessor.h:848
void setValueOff(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as inactive.
Definition: ValueAccessor.h:781
const LeafNodeT * probeLeaf(const Coord &xyz) const
Definition: ValueAccessor.h:2508
void clear() override
Remove all the cached nodes and invalidate the corresponding hash-keys.
Definition: ValueAccessor.h:1979
friend class Tree
Definition: ValueAccessor.h:2527
void setActiveState(const Coord &xyz, bool on=true)
Set the active state of the voxel at the given coordinates but don&#39;t change its value.
Definition: ValueAccessor.h:1115
CacheItem(TreeCacheT &parent)
Definition: ValueAccessor.h:832
typename TreeType::LeafNodeType LeafNodeT
Definition: ValueAccessor.h:1007
typename SubtreeT::Front NodeType
Definition: ValueAccessor.h:523
bool isValueOn(const Coord &xyz)
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:688
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive without changing its value.
Definition: ValueAccessor.h:2341
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:250
CacheItem & copy(TreeCacheT &parent, const CacheItem &other)
Copy another CacheItem&#39;s node pointers and hash keys, but not its parent pointer. ...
Definition: ValueAccessor.h:546
void insert(const Coord &, const RootNodeType *root)
Definition: ValueAccessor.h:844
typename TreeType::RootNodeType RootNodeT
Definition: ValueAccessor.h:188
typename RootNodeT::NodeChainType InvTreeT
Definition: ValueAccessor.h:2090
This base class for ValueAccessors manages registration of an accessor with a tree so that the tree c...
Definition: ValueAccessor.h:84
typename TreeType::RootNodeType RootNodeT
Definition: ValueAccessor.h:1221
typename InvTreeT::template Get< L1 > NodeT1
Definition: ValueAccessor.h:1602
void setValueOff(const Coord &xyz, const ValueType &value)
Definition: ValueAccessor.h:969
CacheItem(TreeCacheT &parent, const CacheItem &other)
Definition: ValueAccessor.h:833
LeafNodeT * probeLeaf(const Coord &xyz)
Definition: ValueAccessor.h:1485
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don&#39;t change its value.
Definition: ValueAccessor.h:1124
bool isCached(const Coord &xyz) const
Definition: ValueAccessor.h:556
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active without changing its value.
Definition: ValueAccessor.h:1814
ValueAccessor(TreeType &tree)
Definition: ValueAccessor.h:482
friend class Tree
Definition: ValueAccessor.h:1526
LeafNodeT * touchLeaf(const Coord &xyz)
Definition: ValueAccessor.h:1156
void setValueOff(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as inactive.
Definition: ValueAccessor.h:2259
void addLeaf(LeafNodeT *leaf)
Add the specified leaf to this tree, possibly creating a child branch in the process. If the leaf node already exists, replace it.
Definition: ValueAccessor.h:1135
typename RootNodeT::ValueType ValueType
Definition: ValueAccessor.h:190
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinate but preserves its active state.
Definition: ValueAccessor.h:2240
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Add a tile at the specified tree level that contains voxel (x, y, z), possibly deleting existing node...
Definition: ValueAccessor.h:1857
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:1036
void clear() override
Remove all nodes from this cache, then reinsert the root node.
Definition: ValueAccessor.h:393
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:202
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:1260
bool isVoxel(const Coord &xyz) const
Definition: ValueAccessor.h:246
static Index numCacheLevels()
Return the number of cache levels employed by this ValueAccessor.
Definition: ValueAccessor.h:1236
TreeType * getTree() const
Return a pointer to the tree associated with this accessor.
Definition: ValueAccessor.h:108
const LeafNodeT * probeLeaf(const Coord &xyz) const
Definition: ValueAccessor.h:1949
ValueAccessor0 & operator=(const ValueAccessor0 &other)
Definition: ValueAccessor.h:1017
void clear() override
Remove all the cached nodes and invalidate the corresponding hash-keys.
Definition: ValueAccessor.h:2511
ValueAccessor3(TreeType &tree)
Constructor from a tree.
Definition: ValueAccessor.h:2096
ValueAccessor3 & operator=(const ValueAccessor3 &other)
Assignment operator.
Definition: ValueAccessor.h:2105
bool isCached(const Coord &xyz) const
Return true if nodes along the path to the given voxel have been cached.
Definition: ValueAccessor.h:216
void eraseNode()
Definition: ValueAccessor.h:1154