HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
RootNode.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 RootNode.h
5 ///
6 /// @brief The root node of an OpenVDB tree
7 
8 #ifndef OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
9 #define OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
10 
11 #include <openvdb/Exceptions.h>
12 #include <openvdb/Types.h>
13 #include <openvdb/io/Compression.h> // for truncateRealToHalf()
14 #include <openvdb/math/Math.h> // for isZero(), isExactlyEqual(), etc.
15 #include <openvdb/math/BBox.h>
16 #include <openvdb/util/NodeMasks.h> // for backward compatibility only (see readTopology())
17 #include <openvdb/version.h>
18 #include <tbb/parallel_for.h>
19 #include <map>
20 #include <set>
21 #include <sstream>
22 #include <vector>
23 
24 
25 namespace openvdb {
27 namespace OPENVDB_VERSION_NAME {
28 namespace tree {
29 
30 // Forward declarations
31 template<typename HeadType, int HeadLevel> struct NodeChain;
32 template<typename, typename> struct SameRootConfig;
33 template<typename, typename, bool> struct RootNodeCopyHelper;
34 template<typename, typename, typename, bool> struct RootNodeCombineHelper;
35 
36 
37 template<typename ChildType>
38 class RootNode
39 {
40 public:
41  using ChildNodeType = ChildType;
42  using LeafNodeType = typename ChildType::LeafNodeType;
43  using ValueType = typename ChildType::ValueType;
44  using BuildType = typename ChildType::BuildType;
45 
46  static const Index LEVEL = 1 + ChildType::LEVEL; // level 0 = leaf
47 
48  /// NodeChainType is a list of this tree's node types, from LeafNodeType to RootNode.
50  static_assert(NodeChainType::Size == LEVEL + 1,
51  "wrong number of entries in RootNode node chain");
52 
53  /// @brief ValueConverter<T>::Type is the type of a RootNode having the same
54  /// child hierarchy as this node but a different value type, T.
55  template<typename OtherValueType>
56  struct ValueConverter {
58  };
59 
60  /// @brief SameConfiguration<OtherNodeType>::value is @c true if and only if
61  /// OtherNodeType is the type of a RootNode whose ChildNodeType has the same
62  /// configuration as this node's ChildNodeType.
63  template<typename OtherNodeType>
66  };
67 
68 
69  /// Construct a new tree with a background value of 0.
70  RootNode();
71 
72  /// Construct a new tree with the given background value.
73  explicit RootNode(const ValueType& background);
74 
75  RootNode(const RootNode& other) { *this = other; }
76 
77  /// @brief Construct a new tree that reproduces the topology and active states
78  /// of a tree of a different ValueType but the same configuration (levels,
79  /// node dimensions and branching factors). Cast the other tree's values to
80  /// this tree's ValueType.
81  /// @throw TypeError if the other tree's configuration doesn't match this tree's
82  /// or if this tree's ValueType is not constructible from the other tree's ValueType.
83  template<typename OtherChildType>
84  explicit RootNode(const RootNode<OtherChildType>& other) { *this = other; }
85 
86  /// @brief Construct a new tree that reproduces the topology and active states of
87  /// another tree (which may have a different ValueType), but not the other tree's values.
88  /// @details All tiles and voxels that are active in the other tree are set to
89  /// @a foreground in the new tree, and all inactive tiles and voxels are set to @a background.
90  /// @param other the root node of a tree having (possibly) a different ValueType
91  /// @param background the value to which inactive tiles and voxels are initialized
92  /// @param foreground the value to which active tiles and voxels are initialized
93  /// @throw TypeError if the other tree's configuration doesn't match this tree's.
94  template<typename OtherChildType>
96  const ValueType& background, const ValueType& foreground, TopologyCopy);
97 
98  /// @brief Construct a new tree that reproduces the topology and active states of
99  /// another tree (which may have a different ValueType), but not the other tree's values.
100  /// All tiles and voxels in the new tree are set to @a background regardless of
101  /// their active states in the other tree.
102  /// @param other the root node of a tree having (possibly) a different ValueType
103  /// @param background the value to which inactive tiles and voxels are initialized
104  /// @note This copy constructor is generally faster than the one that takes both
105  /// a foreground and a background value. Its main application is in multithreaded
106  /// operations where the topology of the output tree exactly matches the input tree.
107  /// @throw TypeError if the other tree's configuration doesn't match this tree's.
108  template<typename OtherChildType>
110 
111  /// @brief Copy a root node of the same type as this node.
112  RootNode& operator=(const RootNode& other);
113  /// @brief Copy a root node of the same tree configuration as this node
114  /// but a different ValueType.
115  /// @throw TypeError if the other tree's configuration doesn't match this tree's.
116  /// @note This node's ValueType must be constructible from the other node's ValueType.
117  /// For example, a root node with values of type float can be assigned to a root node
118  /// with values of type Vec3s, because a Vec3s can be constructed from a float.
119  /// But a Vec3s root node cannot be assigned to a float root node.
120  template<typename OtherChildType>
122 
123  ~RootNode() { this->clear(); }
124 
125 private:
126  struct Tile {
127  Tile(): value(zeroVal<ValueType>()), active(false) {}
128  Tile(const ValueType& v, bool b): value(v), active(b) {}
130  bool active;
131  };
132 
133  // This lightweight struct pairs child pointers and tiles.
134  struct NodeStruct {
135  ChildType* child;
136  Tile tile;
137 
138  NodeStruct(): child(nullptr) {}
139  NodeStruct(ChildType& c): child(&c) {}
140  NodeStruct(const Tile& t): child(nullptr), tile(t) {}
141  NodeStruct(const NodeStruct&) = default;
142  NodeStruct& operator=(const NodeStruct&) = default;
143  ~NodeStruct() {} ///< @note doesn't delete child
144 
145  bool isChild() const { return child != nullptr; }
146  bool isTile() const { return child == nullptr; }
147  bool isTileOff() const { return isTile() && !tile.active; }
148  bool isTileOn() const { return isTile() && tile.active; }
149 
150  void set(ChildType& c) { delete child; child = &c; }
151  void set(const Tile& t) { delete child; child = nullptr; tile = t; }
152  ChildType& steal(const Tile& t) { ChildType* c=child; child=nullptr; tile=t; return *c; }
153  };
154 
155  using MapType = std::map<Coord, NodeStruct>;
156  using MapIter = typename MapType::iterator;
157  using MapCIter = typename MapType::const_iterator;
158 
159  using CoordSet = std::set<Coord>;
160  using CoordSetIter = typename CoordSet::iterator;
161  using CoordSetCIter = typename CoordSet::const_iterator;
162 
163  static void setTile(const MapIter& i, const Tile& t) { i->second.set(t); }
164  static void setChild(const MapIter& i, ChildType& c) { i->second.set(c); }
165  static Tile& getTile(const MapIter& i) { return i->second.tile; }
166  static const Tile& getTile(const MapCIter& i) { return i->second.tile; }
167  static ChildType& getChild(const MapIter& i) { return *(i->second.child); }
168  static const ChildType& getChild(const MapCIter& i) { return *(i->second.child); }
169  static ChildType& stealChild(const MapIter& i, const Tile& t) {return i->second.steal(t);}
170  static const ChildType& stealChild(const MapCIter& i,const Tile& t) {return i->second.steal(t);}
171 
172  static bool isChild(const MapCIter& i) { return i->second.isChild(); }
173  static bool isChild(const MapIter& i) { return i->second.isChild(); }
174  static bool isTile(const MapCIter& i) { return i->second.isTile(); }
175  static bool isTile(const MapIter& i) { return i->second.isTile(); }
176  static bool isTileOff(const MapCIter& i) { return i->second.isTileOff(); }
177  static bool isTileOff(const MapIter& i) { return i->second.isTileOff(); }
178  static bool isTileOn(const MapCIter& i) { return i->second.isTileOn(); }
179  static bool isTileOn(const MapIter& i) { return i->second.isTileOn(); }
180 
181  struct NullPred {
182  static inline bool test(const MapIter&) { return true; }
183  static inline bool test(const MapCIter&) { return true; }
184  };
185  struct ValueOnPred {
186  static inline bool test(const MapIter& i) { return isTileOn(i); }
187  static inline bool test(const MapCIter& i) { return isTileOn(i); }
188  };
189  struct ValueOffPred {
190  static inline bool test(const MapIter& i) { return isTileOff(i); }
191  static inline bool test(const MapCIter& i) { return isTileOff(i); }
192  };
193  struct ValueAllPred {
194  static inline bool test(const MapIter& i) { return isTile(i); }
195  static inline bool test(const MapCIter& i) { return isTile(i); }
196  };
197  struct ChildOnPred {
198  static inline bool test(const MapIter& i) { return isChild(i); }
199  static inline bool test(const MapCIter& i) { return isChild(i); }
200  };
201  struct ChildOffPred {
202  static inline bool test(const MapIter& i) { return isTile(i); }
203  static inline bool test(const MapCIter& i) { return isTile(i); }
204  };
205 
206  template<typename _RootNodeT, typename _MapIterT, typename FilterPredT>
207  class BaseIter
208  {
209  public:
210  using RootNodeT = _RootNodeT;
211  using MapIterT = _MapIterT; // either MapIter or MapCIter
212 
213  bool operator==(const BaseIter& other) const
214  {
215  return (mParentNode == other.mParentNode) && (mIter == other.mIter);
216  }
217  bool operator!=(const BaseIter& other) const { return !(*this == other); }
218 
219  RootNodeT* getParentNode() const { return mParentNode; }
220  /// Return a reference to the node over which this iterator iterates.
221  RootNodeT& parent() const
222  {
223  if (!mParentNode) OPENVDB_THROW(ValueError, "iterator references a null parent node");
224  return *mParentNode;
225  }
226 
227  bool test() const { assert(mParentNode); return mIter != mParentNode->mTable.end(); }
228  operator bool() const { return this->test(); }
229 
230  void increment() { if (this->test()) { ++mIter; } this->skip(); }
231  bool next() { this->increment(); return this->test(); }
232  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
233 
234  /// @brief Return this iterator's position as an offset from
235  /// the beginning of the parent node's map.
236  Index pos() const
237  {
238  return !mParentNode ? 0U : Index(std::distance(mParentNode->mTable.begin(), mIter));
239  }
240 
241  bool isValueOn() const { return RootNodeT::isTileOn(mIter); }
242  bool isValueOff() const { return RootNodeT::isTileOff(mIter); }
243  void setValueOn(bool on = true) const { mIter->second.tile.active = on; }
244  void setValueOff() const { mIter->second.tile.active = false; }
245 
246  /// Return the coordinates of the item to which this iterator is pointing.
247  Coord getCoord() const { return mIter->first; }
248  /// Return in @a xyz the coordinates of the item to which this iterator is pointing.
249  void getCoord(Coord& xyz) const { xyz = this->getCoord(); }
250 
251  protected:
252  BaseIter(): mParentNode(nullptr) {}
253  BaseIter(RootNodeT& parent, const MapIterT& iter): mParentNode(&parent), mIter(iter) {}
254 
255  void skip() { while (this->test() && !FilterPredT::test(mIter)) ++mIter; }
256 
257  RootNodeT* mParentNode;
258  MapIterT mIter;
259  }; // BaseIter
260 
261  template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ChildNodeT>
262  class ChildIter: public BaseIter<RootNodeT, MapIterT, FilterPredT>
263  {
264  public:
265  using BaseT = BaseIter<RootNodeT, MapIterT, FilterPredT>;
266  using NodeType = RootNodeT;
267  using ValueType = NodeType;
268  using ChildNodeType = ChildNodeT;
269  using NonConstNodeType = typename std::remove_const<NodeType>::type;
270  using NonConstValueType = typename std::remove_const<ValueType>::type;
271  using NonConstChildNodeType = typename std::remove_const<ChildNodeType>::type;
272  using BaseT::mIter;
273 
274  ChildIter() {}
275  ChildIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
276 
277  ChildIter& operator++() { BaseT::increment(); return *this; }
278 
279  ChildNodeT& getValue() const { return getChild(mIter); }
280  ChildNodeT& operator*() const { return this->getValue(); }
281  ChildNodeT* operator->() const { return &this->getValue(); }
282  }; // ChildIter
283 
284  template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ValueT>
285  class ValueIter: public BaseIter<RootNodeT, MapIterT, FilterPredT>
286  {
287  public:
288  using BaseT = BaseIter<RootNodeT, MapIterT, FilterPredT>;
289  using NodeType = RootNodeT;
290  using ValueType = ValueT;
291  using NonConstNodeType = typename std::remove_const<NodeType>::type;
292  using NonConstValueType = typename std::remove_const<ValueT>::type;
293  using BaseT::mIter;
294 
295  ValueIter() {}
296  ValueIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
297 
298  ValueIter& operator++() { BaseT::increment(); return *this; }
299 
300  ValueT& getValue() const { return getTile(mIter).value; }
301  ValueT& operator*() const { return this->getValue(); }
302  ValueT* operator->() const { return &(this->getValue()); }
303 
304  void setValue(const ValueT& v) const { assert(isTile(mIter)); getTile(mIter).value = v; }
305 
306  template<typename ModifyOp>
307  void modifyValue(const ModifyOp& op) const
308  {
309  assert(isTile(mIter));
310  op(getTile(mIter).value);
311  }
312  }; // ValueIter
313 
314  template<typename RootNodeT, typename MapIterT, typename ChildNodeT, typename ValueT>
315  class DenseIter: public BaseIter<RootNodeT, MapIterT, NullPred>
316  {
317  public:
318  using BaseT = BaseIter<RootNodeT, MapIterT, NullPred>;
319  using NodeType = RootNodeT;
320  using ValueType = ValueT;
321  using ChildNodeType = ChildNodeT;
322  using NonConstNodeType = typename std::remove_const<NodeType>::type;
323  using NonConstValueType = typename std::remove_const<ValueT>::type;
324  using NonConstChildNodeType = typename std::remove_const<ChildNodeT>::type;
325  using BaseT::mIter;
326 
327  DenseIter() {}
328  DenseIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) {}
329 
330  DenseIter& operator++() { BaseT::increment(); return *this; }
331 
332  bool isChildNode() const { return isChild(mIter); }
333 
334  ChildNodeT* probeChild(NonConstValueType& value) const
335  {
336  if (isChild(mIter)) return &getChild(mIter);
337  value = getTile(mIter).value;
338  return nullptr;
339  }
340  bool probeChild(ChildNodeT*& child, NonConstValueType& value) const
341  {
342  child = this->probeChild(value);
343  return child != nullptr;
344  }
345  bool probeValue(NonConstValueType& value) const { return !this->probeChild(value); }
346 
347  void setChild(ChildNodeT& c) const { RootNodeT::setChild(mIter, c); }
348  void setChild(ChildNodeT* c) const { assert(c != nullptr); RootNodeT::setChild(mIter, *c); }
349  void setValue(const ValueT& v) const
350  {
351  if (isTile(mIter)) getTile(mIter).value = v;
352  /// @internal For consistency with iterators for other node types
353  /// (see, e.g., InternalNode::DenseIter::unsetItem()), we don't call
354  /// setTile() here, because that would also delete the child.
355  else stealChild(mIter, Tile(v, /*active=*/true));
356  }
357  }; // DenseIter
358 
359 public:
360  using ChildOnIter = ChildIter<RootNode, MapIter, ChildOnPred, ChildType>;
361  using ChildOnCIter = ChildIter<const RootNode, MapCIter, ChildOnPred, const ChildType>;
362  using ChildOffIter = ValueIter<RootNode, MapIter, ChildOffPred, const ValueType>;
363  using ChildOffCIter = ValueIter<const RootNode, MapCIter, ChildOffPred, ValueType>;
364  using ChildAllIter = DenseIter<RootNode, MapIter, ChildType, ValueType>;
365  using ChildAllCIter = DenseIter<const RootNode, MapCIter, const ChildType, const ValueType>;
366 
367  using ValueOnIter = ValueIter<RootNode, MapIter, ValueOnPred, ValueType>;
368  using ValueOnCIter = ValueIter<const RootNode, MapCIter, ValueOnPred, const ValueType>;
369  using ValueOffIter = ValueIter<RootNode, MapIter, ValueOffPred, ValueType>;
370  using ValueOffCIter = ValueIter<const RootNode, MapCIter, ValueOffPred, const ValueType>;
371  using ValueAllIter = ValueIter<RootNode, MapIter, ValueAllPred, ValueType>;
372  using ValueAllCIter = ValueIter<const RootNode, MapCIter, ValueAllPred, const ValueType>;
373 
374 
375  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(*this, mTable.begin()); }
376  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(*this, mTable.begin()); }
377  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(*this, mTable.begin()); }
381  ChildOnIter beginChildOn() { return ChildOnIter(*this, mTable.begin()); }
382  ChildOffIter beginChildOff() { return ChildOffIter(*this, mTable.begin()); }
383  ChildAllIter beginChildAll() { return ChildAllIter(*this, mTable.begin()); }
384 
385  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this, mTable.begin()); }
386  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this, mTable.begin()); }
387  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this, mTable.begin()); }
391  ValueOnIter beginValueOn() { return ValueOnIter(*this, mTable.begin()); }
392  ValueOffIter beginValueOff() { return ValueOffIter(*this, mTable.begin()); }
393  ValueAllIter beginValueAll() { return ValueAllIter(*this, mTable.begin()); }
394 
395  /// Return the total amount of memory in bytes occupied by this node and its children.
396  Index64 memUsage() const;
397 
398  /// @brief Expand the specified bbox so it includes the active tiles of
399  /// this root node as well as all the active values in its child
400  /// nodes. If visitVoxels is false LeafNodes will be approximated
401  /// as dense, i.e. with all voxels active. Else the individual
402  /// active voxels are visited to produce a tight bbox.
403  void evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels = true) const;
404 
405  /// Return the bounding box of this RootNode, i.e., an infinite bounding box.
406  static CoordBBox getNodeBoundingBox() { return CoordBBox::inf(); }
407 
408  /// Return the transient data value.
409  Index32 transientData() const { return mTransientData; }
410  /// Set the transient data value.
412 
413  /// @brief Change inactive tiles or voxels with a value equal to +/- the
414  /// old background to the specified value (with the same sign). Active values
415  /// are unchanged.
416  ///
417  /// @param value The new background value
418  /// @param updateChildNodes If true the background values of the
419  /// child nodes is also updated. Else only the background value
420  /// stored in the RootNode itself is changed.
421  ///
422  /// @note Instead of setting @a updateChildNodes to true, consider
423  /// using tools::changeBackground or
424  /// tools::changeLevelSetBackground which are multi-threaded!
425  void setBackground(const ValueType& value, bool updateChildNodes);
426 
427  /// Return this node's background value.
428  const ValueType& background() const { return mBackground; }
429 
430  /// Return @c true if the given tile is inactive and has the background value.
431  bool isBackgroundTile(const Tile&) const;
432  //@{
433  /// Return @c true if the given iterator points to an inactive tile with the background value.
434  bool isBackgroundTile(const MapIter&) const;
435  bool isBackgroundTile(const MapCIter&) const;
436  //@}
437 
438  /// Return the number of background tiles.
439  size_t numBackgroundTiles() const;
440  /// @brief Remove all background tiles.
441  /// @return the number of tiles removed.
442  size_t eraseBackgroundTiles();
443  inline void clear();
444 
445  /// Return @c true if this node's table is either empty or contains only background tiles.
446  bool empty() const { return mTable.size() == numBackgroundTiles(); }
447 
448  /// @brief Expand this node's table so that (x, y, z) is included in the index range.
449  /// @return @c true if an expansion was performed (i.e., if (x, y, z) was not already
450  /// included in the index range).
451  bool expand(const Coord& xyz);
452 
453  static Index getLevel() { return LEVEL; }
454  static void getNodeLog2Dims(std::vector<Index>& dims);
455  static Index getChildDim() { return ChildType::DIM; }
456 
457  /// Return the number of entries in this node's table.
458  Index getTableSize() const { return static_cast<Index>(mTable.size()); }
459 
460  Index getWidth() const { return this->getMaxIndex()[0] - this->getMinIndex()[0]; }
461  Index getHeight() const { return this->getMaxIndex()[1] - this->getMinIndex()[1]; }
462  Index getDepth() const { return this->getMaxIndex()[2] - this->getMinIndex()[2]; }
463 
464  /// Return the smallest index of the current tree.
465  Coord getMinIndex() const;
466  /// Return the largest index of the current tree.
467  Coord getMaxIndex() const;
468  /// Return the current index range. Both min and max are inclusive.
469  void getIndexRange(CoordBBox& bbox) const;
470 
471  /// @brief Return @c true if the given tree has the same node and active value
472  /// topology as this tree (but possibly a different @c ValueType).
473  template<typename OtherChildType>
474  bool hasSameTopology(const RootNode<OtherChildType>& other) const;
475 
476  /// Return @c false if the other node's dimensions don't match this node's.
477  template<typename OtherChildType>
478  static bool hasSameConfiguration(const RootNode<OtherChildType>& other);
479 
480  /// Return @c true if values of the other node's ValueType can be converted
481  /// to values of this node's ValueType.
482  template<typename OtherChildType>
483  static bool hasCompatibleValueType(const RootNode<OtherChildType>& other);
484 
485  Index32 leafCount() const;
486  Index32 nonLeafCount() const;
487  Index32 childCount() const;
488  Index64 onVoxelCount() const;
489  Index64 offVoxelCount() const;
490  Index64 onLeafVoxelCount() const;
491  Index64 offLeafVoxelCount() const;
492  Index64 onTileCount() const;
493  void nodeCount(std::vector<Index32> &vec) const;
494 
495  bool isValueOn(const Coord& xyz) const;
496 
497  /// Return @c true if this root node, or any of its child nodes, have active tiles.
498  bool hasActiveTiles() const;
499 
500  const ValueType& getValue(const Coord& xyz) const;
501  bool probeValue(const Coord& xyz, ValueType& value) const;
502 
503  /// @brief Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
504  /// @details If (x, y, z) isn't explicitly represented in the tree (i.e.,
505  /// it is implicitly a background voxel), return -1.
506  int getValueDepth(const Coord& xyz) const;
507 
508  /// Set the active state of the voxel at the given coordinates but don't change its value.
509  void setActiveState(const Coord& xyz, bool on);
510  /// Set the value of the voxel at the given coordinates but don't change its active state.
511  void setValueOnly(const Coord& xyz, const ValueType& value);
512  /// Set the value of the voxel at the given coordinates and mark the voxel as active.
513  void setValueOn(const Coord& xyz, const ValueType& value);
514  /// Mark the voxel at the given coordinates as inactive but don't change its value.
515  void setValueOff(const Coord& xyz);
516  /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
517  void setValueOff(const Coord& xyz, const ValueType& value);
518 
519  /// @brief Apply a functor to the value of the voxel at the given coordinates
520  /// and mark the voxel as active.
521  template<typename ModifyOp>
522  void modifyValue(const Coord& xyz, const ModifyOp& op);
523  /// Apply a functor to the voxel at the given coordinates.
524  template<typename ModifyOp>
525  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
526 
527  //@{
528  /// @brief Set all voxels within a given axis-aligned box to a constant value.
529  /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box
530  /// @param value the value to which to set voxels within the box
531  /// @param active if true, mark voxels within the box as active,
532  /// otherwise mark them as inactive
533  /// @note This operation generates a sparse, but not always optimally sparse,
534  /// representation of the filled box. Follow fill operations with a prune()
535  /// operation for optimal sparseness.
536  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
537  void sparseFill(const CoordBBox& bbox, const ValueType& value, bool active = true)
538  {
539  this->fill(bbox, value, active);
540  }
541  //@}
542 
543  /// @brief Set all voxels within a given axis-aligned box to a constant value
544  /// and ensure that those voxels are all represented at the leaf level.
545  /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box.
546  /// @param value the value to which to set voxels within the box.
547  /// @param active if true, mark voxels within the box as active,
548  /// otherwise mark them as inactive.
549  /// @sa voxelizeActiveTiles()
550  void denseFill(const CoordBBox& bbox, const ValueType& value, bool active = true);
551 
552  /// @brief Densify active tiles, i.e., replace them with leaf-level active voxels.
553  ///
554  /// @param threaded if true, this operation is multi-threaded (over the internal nodes).
555  ///
556  /// @warning This method can explode the tree's memory footprint, especially if it
557  /// contains active tiles at the upper levels (in particular the root level)!
558  ///
559  /// @sa denseFill()
560  void voxelizeActiveTiles(bool threaded = true);
561 
562  /// @brief Copy into a dense grid the values of all voxels, both active and inactive,
563  /// that intersect a given bounding box.
564  /// @param bbox inclusive bounding box of the voxels to be copied into the dense grid
565  /// @param dense dense grid with a stride in @e z of one (see tools::Dense
566  /// in tools/Dense.h for the required API)
567  template<typename DenseT>
568  void copyToDense(const CoordBBox& bbox, DenseT& dense) const;
569 
570 
571  //
572  // I/O
573  //
574  bool writeTopology(std::ostream&, bool toHalf = false) const;
575  bool readTopology(std::istream&, bool fromHalf = false);
576 
577  void writeBuffers(std::ostream&, bool toHalf = false) const;
578  void readBuffers(std::istream&, bool fromHalf = false);
579  void readBuffers(std::istream&, const CoordBBox&, bool fromHalf = false);
580 
581 
582  //
583  // Voxel access
584  //
585  /// Return the value of the voxel at the given coordinates and, if necessary, update
586  /// the accessor with pointers to the nodes along the path from the root node to
587  /// the node containing the voxel.
588  /// @note Used internally by ValueAccessor.
589  template<typename AccessorT>
590  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
591  /// Return @c true if the voxel at the given coordinates is active and, if necessary,
592  /// update the accessor with pointers to the nodes along the path from the root node
593  /// to the node containing the voxel.
594  /// @note Used internally by ValueAccessor.
595  template<typename AccessorT>
596  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
597 
598  /// Change the value of the voxel at the given coordinates and mark it as active.
599  /// If necessary, update the accessor with pointers to the nodes along the path
600  /// from the root node to the node containing the voxel.
601  /// @note Used internally by ValueAccessor.
602  template<typename AccessorT>
603  void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
604 
605  /// Set the value of the voxel at the given coordinates without changing its active state.
606  /// If necessary, update the accessor with pointers to the nodes along the path
607  /// from the root node to the node containing the voxel.
608  /// @note Used internally by ValueAccessor.
609  template<typename AccessorT>
610  void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
611 
612  /// Apply a functor to the value of the voxel at the given coordinates
613  /// and mark the voxel as active.
614  /// If necessary, update the accessor with pointers to the nodes along the path
615  /// from the root node to the node containing the voxel.
616  /// @note Used internally by ValueAccessor.
617  template<typename ModifyOp, typename AccessorT>
618  void modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
619 
620  /// Apply a functor to the voxel at the given coordinates.
621  /// If necessary, update the accessor with pointers to the nodes along the path
622  /// from the root node to the node containing the voxel.
623  /// @note Used internally by ValueAccessor.
624  template<typename ModifyOp, typename AccessorT>
625  void modifyValueAndActiveStateAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
626 
627  /// Change the value of the voxel at the given coordinates and mark it as inactive.
628  /// If necessary, update the accessor with pointers to the nodes along the path
629  /// from the root node to the node containing the voxel.
630  /// @note Used internally by ValueAccessor.
631  template<typename AccessorT>
632  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
633 
634  /// Set the active state of the voxel at the given coordinates without changing its value.
635  /// If necessary, update the accessor with pointers to the nodes along the path
636  /// from the root node to the node containing the voxel.
637  /// @note Used internally by ValueAccessor.
638  template<typename AccessorT>
639  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
640 
641  /// Return, in @a value, the value of the voxel at the given coordinates and,
642  /// if necessary, update the accessor with pointers to the nodes along
643  /// the path from the root node to the node containing the voxel.
644  /// @return @c true if the voxel at the given coordinates is active
645  /// @note Used internally by ValueAccessor.
646  template<typename AccessorT>
647  bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
648 
649  /// Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
650  /// If (x, y, z) isn't explicitly represented in the tree (i.e., it is implicitly
651  /// a background voxel), return -1. If necessary, update the accessor with pointers
652  /// to the nodes along the path from the root node to the node containing the voxel.
653  /// @note Used internally by ValueAccessor.
654  template<typename AccessorT>
655  int getValueDepthAndCache(const Coord& xyz, AccessorT&) const;
656 
657  /// Set all voxels that lie outside the given axis-aligned box to the background.
658  void clip(const CoordBBox&);
659 
660  /// @brief Reduce the memory footprint of this tree by replacing with tiles
661  /// any nodes whose values are all the same (optionally to within a tolerance)
662  /// and have the same active state.
663  ///
664  /// @note Consider instead using tools::prune which is multi-threaded!
665  void prune(const ValueType& tolerance = zeroVal<ValueType>());
666 
667  /// @brief Add the given leaf node to this tree, creating a new branch if necessary.
668  /// If a leaf node with the same origin already exists, replace it.
669  void addLeaf(LeafNodeType* leaf);
670 
671  /// @brief Same as addLeaf() but, if necessary, update the given accessor with pointers
672  /// to the nodes along the path from the root node to the node containing the coordinate.
673  template<typename AccessorT>
674  void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
675 
676  /// @brief Return a pointer to the node of type @c NodeT that contains voxel (x, y, z)
677  /// and replace it with a tile of the specified value and state.
678  /// If no such node exists, leave the tree unchanged and return @c nullptr.
679  ///
680  /// @note The caller takes ownership of the node and is responsible for deleting it.
681  ///
682  /// @warning Since this method potentially removes nodes and branches of the tree,
683  /// it is important to clear the caches of all ValueAccessors associated with this tree.
684  template<typename NodeT>
685  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
686 
687  /// @brief Add the given child node at the root level.
688  /// If a child node with the same origin already exists, delete the old node and add
689  /// the new node in its place (i.e. ownership of the new child node is transferred
690  /// to this RootNode).
691  /// @return @c true (for consistency with InternalNode::addChild)
692  bool addChild(ChildType* child);
693 
694  /// @brief Add a tile containing voxel (x, y, z) at the root level,
695  /// deleting the existing branch if necessary.
696  void addTile(const Coord& xyz, const ValueType& value, bool state);
697 
698  /// @brief Add a tile containing voxel (x, y, z) at the specified tree level,
699  /// creating a new branch if necessary. Delete any existing lower-level nodes
700  /// that contain (x, y, z).
701  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
702 
703  /// @brief Same as addTile() but, if necessary, update the given accessor with pointers
704  /// to the nodes along the path from the root node to the node containing the coordinate.
705  template<typename AccessorT>
706  void addTileAndCache(Index level, const Coord& xyz, const ValueType&, bool state, AccessorT&);
707 
708  /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
709  /// If no such node exists, create one that preserves the values and
710  /// active states of all voxels.
711  /// @details Use this method to preallocate a static tree topology
712  /// over which to safely perform multithreaded processing.
713  LeafNodeType* touchLeaf(const Coord& xyz);
714 
715  /// @brief Same as touchLeaf() but, if necessary, update the given accessor with pointers
716  /// to the nodes along the path from the root node to the node containing the coordinate.
717  template<typename AccessorT>
718  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT& acc);
719 
720  //@{
721  /// @brief Return a pointer to the node that contains voxel (x, y, z).
722  /// If no such node exists, return @c nullptr.
723  template <typename NodeT>
724  NodeT* probeNode(const Coord& xyz);
725  template <typename NodeT>
726  const NodeT* probeConstNode(const Coord& xyz) const;
727  //@}
728 
729  //@{
730  /// @brief Same as probeNode() but, if necessary, update the given accessor with pointers
731  /// to the nodes along the path from the root node to the node containing the coordinate.
732  template<typename NodeT, typename AccessorT>
733  NodeT* probeNodeAndCache(const Coord& xyz, AccessorT& acc);
734  template<typename NodeT, typename AccessorT>
735  const NodeT* probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const;
736  //@}
737 
738  //@{
739  /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
740  /// If no such node exists, return @c nullptr.
741  LeafNodeType* probeLeaf(const Coord& xyz);
742  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
743  const LeafNodeType* probeLeaf(const Coord& xyz) const;
744  //@}
745 
746  //@{
747  /// @brief Same as probeLeaf() but, if necessary, update the given accessor with pointers
748  /// to the nodes along the path from the root node to the node containing the coordinate.
749  template<typename AccessorT>
750  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc);
751  template<typename AccessorT>
752  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const;
753  template<typename AccessorT>
754  const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const;
755  //@}
756 
757 
758  //
759  // Aux methods
760  //
761 
762  //@{
763  /// @brief Adds all nodes of a certain type to a container with the following API:
764  /// @code
765  /// struct ArrayT {
766  /// using value_type = ...;// defines the type of nodes to be added to the array
767  /// void push_back(value_type nodePtr);// method that add nodes to the array
768  /// };
769  /// @endcode
770  /// @details An example of a wrapper around a c-style array is:
771  /// @code
772  /// struct MyArray {
773  /// using value_type = LeafType*;
774  /// value_type* ptr;
775  /// MyArray(value_type* array) : ptr(array) {}
776  /// void push_back(value_type leaf) { *ptr++ = leaf; }
777  ///};
778  /// @endcode
779  /// @details An example that constructs a list of pointer to all leaf nodes is:
780  /// @code
781  /// std::vector<const LeafNodeType*> array;//most std contains have the required API
782  /// array.reserve(tree.leafCount());//this is a fast preallocation.
783  /// tree.getNodes(array);
784  /// @endcode
785  template<typename ArrayT> void getNodes(ArrayT& array);
786  template<typename ArrayT> void getNodes(ArrayT& array) const;
787  //@}
788 
789  //@{
790  /// @brief Steals all nodes of a certain type from the tree and
791  /// adds them to a container with the following API:
792  /// @code
793  /// struct ArrayT {
794  /// using value_type = ...;// defines the type of nodes to be added to the array
795  /// void push_back(value_type nodePtr);// method that add nodes to the array
796  /// };
797  /// @endcode
798  /// @details An example of a wrapper around a c-style array is:
799  /// @code
800  /// struct MyArray {
801  /// using value_type = LeafType*;
802  /// value_type* ptr;
803  /// MyArray(value_type* array) : ptr(array) {}
804  /// void push_back(value_type leaf) { *ptr++ = leaf; }
805  ///};
806  /// @endcode
807  /// @details An example that constructs a list of pointer to all leaf nodes is:
808  /// @code
809  /// std::vector<const LeafNodeType*> array;//most std contains have the required API
810  /// array.reserve(tree.leafCount());//this is a fast preallocation.
811  /// tree.stealNodes(array);
812  /// @endcode
813  template<typename ArrayT>
814  void stealNodes(ArrayT& array, const ValueType& value, bool state);
815  template<typename ArrayT>
816  void stealNodes(ArrayT& array) { this->stealNodes(array, mBackground, false); }
817  //@}
818 
819  /// @brief Efficiently merge another tree into this tree using one of several schemes.
820  /// @details This operation is primarily intended to combine trees that are mostly
821  /// non-overlapping (for example, intermediate trees from computations that are
822  /// parallelized across disjoint regions of space).
823  /// @note This operation is not guaranteed to produce an optimally sparse tree.
824  /// Follow merge() with prune() for optimal sparseness.
825  /// @warning This operation always empties the other tree.
826  template<MergePolicy Policy> void merge(RootNode& other);
827 
828  /// @brief Union this tree's set of active values with the active values
829  /// of the other tree, whose @c ValueType may be different.
830  /// @details The resulting state of a value is active if the corresponding value
831  /// was already active OR if it is active in the other tree. Also, a resulting
832  /// value maps to a voxel if the corresponding value already mapped to a voxel
833  /// OR if it is a voxel in the other tree. Thus, a resulting value can only
834  /// map to a tile if the corresponding value already mapped to a tile
835  /// AND if it is a tile value in other tree.
836  ///
837  /// @note This operation modifies only active states, not values.
838  /// Specifically, active tiles and voxels in this tree are not changed, and
839  /// tiles or voxels that were inactive in this tree but active in the other tree
840  /// are marked as active in this tree but left with their original values.
841  ///
842  /// @note If preserveTiles is true, any active tile in this topology
843  /// will not be densified by overlapping child topology.
844  template<typename OtherChildType>
845  void topologyUnion(const RootNode<OtherChildType>& other, const bool preserveTiles = false);
846 
847  /// @brief Intersects this tree's set of active values with the active values
848  /// of the other tree, whose @c ValueType may be different.
849  /// @details The resulting state of a value is active only if the corresponding
850  /// value was already active AND if it is active in the other tree. Also, a
851  /// resulting value maps to a voxel if the corresponding value
852  /// already mapped to an active voxel in either of the two grids
853  /// and it maps to an active tile or voxel in the other grid.
854  ///
855  /// @note This operation can delete branches in this grid if they
856  /// overlap with inactive tiles in the other grid. Likewise active
857  /// voxels can be turned into inactive voxels resulting in leaf
858  /// nodes with no active values. Thus, it is recommended to
859  /// subsequently call prune.
860  template<typename OtherChildType>
862 
863  /// @brief Difference this tree's set of active values with the active values
864  /// of the other tree, whose @c ValueType may be different. So a
865  /// resulting voxel will be active only if the original voxel is
866  /// active in this tree and inactive in the other tree.
867  ///
868  /// @note This operation can delete branches in this grid if they
869  /// overlap with active tiles in the other grid. Likewise active
870  /// voxels can be turned into inactive voxels resulting in leaf
871  /// nodes with no active values. Thus, it is recommended to
872  /// subsequently call prune.
873  template<typename OtherChildType>
874  void topologyDifference(const RootNode<OtherChildType>& other);
875 
876  template<typename CombineOp>
877  void combine(RootNode& other, CombineOp&, bool prune = false);
878 
879  template<typename CombineOp, typename OtherRootNode /*= RootNode*/>
880  void combine2(const RootNode& other0, const OtherRootNode& other1,
881  CombineOp& op, bool prune = false);
882 
883 #if OPENVDB_ABI_VERSION_NUMBER >= 10
884  /// Return the grid index coordinates of this node's local origin.
885  const Coord& origin() const { return mOrigin; }
886  /// @brief change the origin on this root node
887  /// @param origin the index coordinates of the new alignment
888  ///
889  /// @warning This method will throw if the origin is non-zero, since
890  /// other tools do not yet support variable offsets.
891  void setOrigin(const Coord &origin);
892 #endif
893 
894 private:
895  /// During topology-only construction, access is needed
896  /// to protected/private members of other template instances.
897  template<typename> friend class RootNode;
898 
899  template<typename, typename, bool> friend struct RootNodeCopyHelper;
900  template<typename, typename, typename, bool> friend struct RootNodeCombineHelper;
901 
902  /// Currently no-op, but can be used to define empty and delete keys for mTable
903  void initTable() {}
904  //@{
905  /// @internal Used by doVisit2().
906  void resetTable(MapType& table) { mTable.swap(table); table.clear(); }
907  void resetTable(const MapType&) const {}
908  //@}
909 
910  Index getChildCount() const;
911  Index getTileCount() const;
912  Index getActiveTileCount() const;
913  Index getInactiveTileCount() const;
914 
915 #if OPENVDB_ABI_VERSION_NUMBER < 10
916  /// Static method that returns a MapType key for the given coordinates.
917  static Coord coordToKey(const Coord& xyz) {return xyz & ~(ChildType::DIM - 1); }
918 #else
919  /// Return a MapType key for the given coordinates, offset by the mOrigin.
920  Coord coordToKey(const Coord& xyz) const { return (xyz - mOrigin) & ~(ChildType::DIM - 1); }
921 #endif
922 
923  /// Insert this node's mTable keys into the given set.
924  void insertKeys(CoordSet&) const;
925 
926  /// Return @c true if this node's mTable contains the given key.
927  bool hasKey(const Coord& key) const { return mTable.find(key) != mTable.end(); }
928  //@{
929  /// @brief Look up the given key in this node's mTable.
930  /// @return an iterator pointing to the matching mTable entry or to mTable.end().
931  MapIter findKey(const Coord& key) { return mTable.find(key); }
932  MapCIter findKey(const Coord& key) const { return mTable.find(key); }
933  //@}
934  //@{
935  /// @brief Convert the given coordinates to a key and look the key up in this node's mTable.
936  /// @return an iterator pointing to the matching mTable entry or to mTable.end().
937  MapIter findCoord(const Coord& xyz) { return mTable.find(coordToKey(xyz)); }
938  MapCIter findCoord(const Coord& xyz) const { return mTable.find(coordToKey(xyz)); }
939  //@}
940  /// @brief Convert the given coordinates to a key and look the key up in this node's mTable.
941  /// @details If the key is not found, insert a background tile with that key.
942  /// @return an iterator pointing to the matching mTable entry.
943  MapIter findOrAddCoord(const Coord& xyz);
944 
945  /// @brief Verify that the tree rooted at @a other has the same configuration
946  /// (levels, branching factors and node dimensions) as this tree, but allow
947  /// their ValueTypes to differ.
948  /// @throw TypeError if the other tree's configuration doesn't match this tree's.
949  template<typename OtherChildType>
950  static void enforceSameConfiguration(const RootNode<OtherChildType>& other);
951 
952  /// @brief Verify that @a other has values of a type that can be converted
953  /// to this node's ValueType.
954  /// @details For example, values of type float are compatible with values of type Vec3s,
955  /// because a Vec3s can be constructed from a float. But the reverse is not true.
956  /// @throw TypeError if the other node's ValueType is not convertible into this node's.
957  template<typename OtherChildType>
958  static void enforceCompatibleValueTypes(const RootNode<OtherChildType>& other);
959 
960  template<typename CombineOp, typename OtherRootNode /*= RootNode*/>
961  void doCombine2(const RootNode&, const OtherRootNode&, CombineOp&, bool prune);
962 
963  MapType mTable;
964  ValueType mBackground;
965 #if OPENVDB_ABI_VERSION_NUMBER >= 10
966  Coord mOrigin;
967 #endif
968  /// Transient Data (not serialized)
969  Index32 mTransientData = 0;
970 }; // end of RootNode class
971 
972 
973 ////////////////////////////////////////
974 
975 
976 /// @brief NodeChain<RootNodeType, RootNodeType::LEVEL>::Type is a openvdb::TypeList
977 /// that lists the types of the nodes of the tree rooted at RootNodeType in reverse order,
978 /// from LeafNode to RootNode.
979 /// @details For example, if RootNodeType is
980 /// @code
981 /// RootNode<InternalNode<InternalNode<LeafNode> > >
982 /// @endcode
983 /// then NodeChain::Type is
984 /// @code
985 /// openvdb::TypeList<
986 /// LeafNode,
987 /// InternalNode<LeafNode>,
988 /// InternalNode<InternalNode<LeafNode> >,
989 /// RootNode<InternalNode<InternalNode<LeafNode> > > >
990 /// @endcode
991 ///
992 /// @note Use the following to get the Nth node type, where N=0 is the LeafNodeType:
993 /// @code
994 /// NodeChainType::Get<N>;
995 /// @endcode
996 template<typename HeadT, int HeadLevel>
997 struct NodeChain {
998  using SubtreeT = typename NodeChain<typename HeadT::ChildNodeType, HeadLevel-1>::Type;
999  using Type = typename SubtreeT::template Append<HeadT>;
1000 };
1001 
1002 /// Specialization to terminate NodeChain
1003 template<typename HeadT>
1004 struct NodeChain<HeadT, /*HeadLevel=*/1> {
1006 };
1007 
1008 
1009 ////////////////////////////////////////
1010 
1011 
1012 //@{
1013 /// Helper metafunction used to implement RootNode::SameConfiguration
1014 /// (which, as an inner class, can't be independently specialized)
1015 template<typename ChildT1, typename NodeT2>
1016 struct SameRootConfig {
1017  static const bool value = false;
1018 };
1019 
1020 template<typename ChildT1, typename ChildT2>
1021 struct SameRootConfig<ChildT1, RootNode<ChildT2> > {
1022  static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
1023 };
1024 //@}
1025 
1026 
1027 ////////////////////////////////////////
1028 
1029 
1030 template<typename ChildT>
1031 inline
1033  : mBackground(zeroVal<ValueType>())
1035  , mOrigin(0, 0, 0)
1036 #endif
1037 {
1038  this->initTable();
1039 }
1040 
1041 
1042 template<typename ChildT>
1043 inline
1045  : mBackground(background)
1047  , mOrigin(0, 0, 0)
1048 #endif
1049 {
1050  this->initTable();
1051 }
1052 
1053 
1054 template<typename ChildT>
1055 template<typename OtherChildType>
1056 inline
1058  const ValueType& backgd, const ValueType& foregd, TopologyCopy)
1059  : mBackground(backgd)
1061  , mOrigin(other.mOrigin)
1062 #endif
1063  , mTransientData(other.mTransientData)
1064 {
1065  using OtherRootT = RootNode<OtherChildType>;
1066 
1067 #if OPENVDB_ABI_VERSION_NUMBER >= 10
1068  if (mOrigin != Coord(0,0,0)) {
1069  OPENVDB_THROW(ValueError, "RootNode::RootNode: non-zero offsets are currently not supported");
1070  }
1071 #endif
1072 
1073  enforceSameConfiguration(other);
1074 
1075  const Tile bgTile(backgd, /*active=*/false), fgTile(foregd, true);
1076  this->initTable();
1077 
1078  for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1079  mTable[i->first] = OtherRootT::isTile(i)
1080  ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1081  : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, foregd, TopologyCopy())));
1082  }
1083 }
1084 
1085 
1086 template<typename ChildT>
1087 template<typename OtherChildType>
1088 inline
1090  const ValueType& backgd, TopologyCopy)
1091  : mBackground(backgd)
1093  , mOrigin(other.mOrigin)
1094 #endif
1095  , mTransientData(other.mTransientData)
1096 {
1097  using OtherRootT = RootNode<OtherChildType>;
1098 
1099 #if OPENVDB_ABI_VERSION_NUMBER >= 10
1100  if (mOrigin != Coord(0,0,0)) {
1101  OPENVDB_THROW(ValueError, "RootNode::RootNode: non-zero offsets are currently not supported");
1102  }
1103 #endif
1104 
1105  enforceSameConfiguration(other);
1106 
1107  const Tile bgTile(backgd, /*active=*/false), fgTile(backgd, true);
1108  this->initTable();
1109  for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1110  mTable[i->first] = OtherRootT::isTile(i)
1111  ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1112  : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, TopologyCopy())));
1113  }
1114 }
1115 
1116 
1117 ////////////////////////////////////////
1118 
1119 
1120 // This helper class is a friend of RootNode and is needed so that assignment
1121 // with value conversion can be specialized for compatible and incompatible
1122 // pairs of RootNode types.
1123 template<typename RootT, typename OtherRootT, bool Compatible = false>
1124 struct RootNodeCopyHelper
1125 {
1126  static inline void copyWithValueConversion(RootT& self, const OtherRootT& other)
1127  {
1128  // If the two root nodes have different configurations or incompatible ValueTypes,
1129  // throw an exception.
1130  self.enforceSameConfiguration(other);
1131  self.enforceCompatibleValueTypes(other);
1132  // One of the above two tests should throw, so we should never get here:
1133  std::ostringstream ostr;
1134  ostr << "cannot convert a " << typeid(OtherRootT).name()
1135  << " to a " << typeid(RootT).name();
1136  OPENVDB_THROW(TypeError, ostr.str());
1137  }
1138 };
1139 
1140 // Specialization for root nodes of compatible types
1141 template<typename RootT, typename OtherRootT>
1142 struct RootNodeCopyHelper<RootT, OtherRootT, /*Compatible=*/true>
1143 {
1144  static inline void copyWithValueConversion(RootT& self, const OtherRootT& other)
1145  {
1146  using ValueT = typename RootT::ValueType;
1147  using ChildT = typename RootT::ChildNodeType;
1148  using NodeStruct = typename RootT::NodeStruct;
1149  using Tile = typename RootT::Tile;
1150  using OtherValueT = typename OtherRootT::ValueType;
1151  using OtherMapCIter = typename OtherRootT::MapCIter;
1152  using OtherTile = typename OtherRootT::Tile;
1153 
1154  struct Local {
1155  /// @todo Consider using a value conversion functor passed as an argument instead.
1156  static inline ValueT convertValue(const OtherValueT& val) { return ValueT(val); }
1157  };
1158 
1159  self.mBackground = Local::convertValue(other.mBackground);
1160 #if OPENVDB_ABI_VERSION_NUMBER >= 10
1161  if (other.mOrigin != Coord(0,0,0)) {
1162  OPENVDB_THROW(ValueError, "RootNodeCopyHelper::copyWithValueConversion: non-zero offsets are currently not supported");
1163  }
1164  self.mOrigin = other.mOrigin;
1165 #endif
1166  self.mTransientData = other.mTransientData;
1167 
1168  self.clear();
1169  self.initTable();
1170 
1171  for (OtherMapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1172  if (other.isTile(i)) {
1173  // Copy the other node's tile, but convert its value to this node's ValueType.
1174  const OtherTile& otherTile = other.getTile(i);
1175  self.mTable[i->first] = NodeStruct(
1176  Tile(Local::convertValue(otherTile.value), otherTile.active));
1177  } else {
1178  // Copy the other node's child, but convert its values to this node's ValueType.
1179  self.mTable[i->first] = NodeStruct(*(new ChildT(other.getChild(i))));
1180  }
1181  }
1182  }
1183 };
1184 
1185 
1186 // Overload for root nodes of the same type as this node
1187 template<typename ChildT>
1188 inline RootNode<ChildT>&
1190 {
1191  if (&other != this) {
1192  mBackground = other.mBackground;
1193 #if OPENVDB_ABI_VERSION_NUMBER >= 10
1194  mOrigin = other.mOrigin;
1195  if (mOrigin != Coord(0,0,0)) {
1196  OPENVDB_THROW(ValueError, "RootNode::operator=: non-zero offsets are currently not supported");
1197  }
1198 #endif
1199  mTransientData = other.mTransientData;
1200 
1201  this->clear();
1202  this->initTable();
1203 
1204  for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1205  mTable[i->first] =
1206  isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(new ChildT(getChild(i))));
1207  }
1208  }
1209  return *this;
1210 }
1211 
1212 // Overload for root nodes of different types
1213 template<typename ChildT>
1214 template<typename OtherChildType>
1215 inline RootNode<ChildT>&
1217 {
1218  using OtherRootT = RootNode<OtherChildType>;
1219  using OtherValueT = typename OtherRootT::ValueType;
1220  static const bool compatible = (SameConfiguration<OtherRootT>::value
1221  && CanConvertType</*from=*/OtherValueT, /*to=*/ValueType>::value);
1223  return *this;
1224 }
1225 
1226 
1227 ////////////////////////////////////////
1228 
1229 template<typename ChildT>
1230 inline void
1231 RootNode<ChildT>::setBackground(const ValueType& background, bool updateChildNodes)
1232 {
1233  if (math::isExactlyEqual(background, mBackground)) return;
1234 
1235  if (updateChildNodes) {
1236  // Traverse the tree, replacing occurrences of mBackground with background
1237  // and -mBackground with -background.
1238  for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1239  ChildT *child = iter->second.child;
1240  if (child) {
1241  child->resetBackground(/*old=*/mBackground, /*new=*/background);
1242  } else {
1243  Tile& tile = getTile(iter);
1244  if (tile.active) continue;//only change inactive tiles
1245  if (math::isApproxEqual(tile.value, mBackground)) {
1246  tile.value = background;
1247  } else if (math::isApproxEqual(tile.value, math::negative(mBackground))) {
1248  tile.value = math::negative(background);
1249  }
1250  }
1251  }
1252  }
1253  mBackground = background;
1254 }
1255 
1256 template<typename ChildT>
1257 inline bool
1258 RootNode<ChildT>::isBackgroundTile(const Tile& tile) const
1259 {
1260  return !tile.active && math::isApproxEqual(tile.value, mBackground);
1261 }
1262 
1263 template<typename ChildT>
1264 inline bool
1265 RootNode<ChildT>::isBackgroundTile(const MapIter& iter) const
1266 {
1267  return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
1268 }
1269 
1270 template<typename ChildT>
1271 inline bool
1272 RootNode<ChildT>::isBackgroundTile(const MapCIter& iter) const
1273 {
1274  return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
1275 }
1276 
1277 
1278 template<typename ChildT>
1279 inline size_t
1281 {
1282  size_t count = 0;
1283  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1284  if (this->isBackgroundTile(i)) ++count;
1285  }
1286  return count;
1287 }
1288 
1289 
1290 template<typename ChildT>
1291 inline size_t
1293 {
1294  std::set<Coord> keysToErase;
1295  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1296  if (this->isBackgroundTile(i)) keysToErase.insert(i->first);
1297  }
1298  for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
1299  mTable.erase(*i);
1300  }
1301  return keysToErase.size();
1302 }
1303 
1304 
1305 ////////////////////////////////////////
1306 
1307 
1308 template<typename ChildT>
1309 inline void
1310 RootNode<ChildT>::insertKeys(CoordSet& keys) const
1311 {
1312  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1313  keys.insert(i->first);
1314  }
1315 }
1316 
1317 
1318 template<typename ChildT>
1319 inline typename RootNode<ChildT>::MapIter
1320 RootNode<ChildT>::findOrAddCoord(const Coord& xyz)
1321 {
1322  const Coord key = coordToKey(xyz);
1323  std::pair<MapIter, bool> result = mTable.insert(
1324  typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
1325  return result.first;
1326 }
1327 
1328 
1329 template<typename ChildT>
1330 inline bool
1331 RootNode<ChildT>::expand(const Coord& xyz)
1332 {
1333  const Coord key = coordToKey(xyz);
1334  std::pair<MapIter, bool> result = mTable.insert(
1335  typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
1336  return result.second; // return true if the key did not already exist
1337 }
1338 
1339 
1340 ////////////////////////////////////////
1341 
1342 
1343 template<typename ChildT>
1344 inline void
1345 RootNode<ChildT>::getNodeLog2Dims(std::vector<Index>& dims)
1346 {
1347  dims.push_back(0); // magic number; RootNode has no Log2Dim
1348  ChildT::getNodeLog2Dims(dims);
1349 }
1350 
1351 
1352 template<typename ChildT>
1353 inline Coord
1355 {
1356  return mTable.empty() ? Coord(0) : mTable.begin()->first;
1357 }
1358 
1359 template<typename ChildT>
1360 inline Coord
1362 {
1363  return mTable.empty() ? Coord(0) : mTable.rbegin()->first + Coord(ChildT::DIM - 1);
1364 }
1365 
1366 
1367 template<typename ChildT>
1368 inline void
1370 {
1371  bbox.min() = this->getMinIndex();
1372  bbox.max() = this->getMaxIndex();
1373 }
1374 
1375 
1376 ////////////////////////////////////////
1377 
1378 
1379 template<typename ChildT>
1380 template<typename OtherChildType>
1381 inline bool
1383 {
1384  using OtherRootT = RootNode<OtherChildType>;
1385  using OtherMapT = typename OtherRootT::MapType;
1386  using OtherIterT = typename OtherRootT::MapIter;
1387  using OtherCIterT = typename OtherRootT::MapCIter;
1388 
1389  if (!hasSameConfiguration(other)) return false;
1390 
1391  // Create a local copy of the other node's table.
1392  OtherMapT copyOfOtherTable = other.mTable;
1393 
1394  // For each entry in this node's table...
1395  for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
1396  if (this->isBackgroundTile(thisIter)) continue; // ignore background tiles
1397 
1398  // Fail if there is no corresponding entry in the other node's table.
1399  OtherCIterT otherIter = other.findKey(thisIter->first);
1400  if (otherIter == other.mTable.end()) return false;
1401 
1402  // Fail if this entry is a tile and the other is a child or vice-versa.
1403  if (isChild(thisIter)) {//thisIter points to a child
1404  if (OtherRootT::isTile(otherIter)) return false;
1405  // Fail if both entries are children, but the children have different topology.
1406  if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter))) return false;
1407  } else {//thisIter points to a tile
1408  if (OtherRootT::isChild(otherIter)) return false;
1409  if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active) return false;
1410  }
1411 
1412  // Remove tiles and child nodes with matching topology from
1413  // the copy of the other node's table. This is required since
1414  // the two root tables can include an arbitrary number of
1415  // background tiles and still have the same topology!
1416  copyOfOtherTable.erase(otherIter->first);
1417  }
1418  // Fail if the remaining entries in copyOfOtherTable are not all background tiles.
1419  for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1420  if (!other.isBackgroundTile(i)) return false;
1421  }
1422  return true;
1423 }
1424 
1425 
1426 template<typename ChildT>
1427 template<typename OtherChildType>
1428 inline bool
1430 {
1431  std::vector<Index> thisDims, otherDims;
1432  RootNode::getNodeLog2Dims(thisDims);
1434  return (thisDims == otherDims);
1435 }
1436 
1437 
1438 template<typename ChildT>
1439 template<typename OtherChildType>
1440 inline void
1442 {
1443  std::vector<Index> thisDims, otherDims;
1444  RootNode::getNodeLog2Dims(thisDims);
1446  if (thisDims != otherDims) {
1447  std::ostringstream ostr;
1448  ostr << "grids have incompatible configurations (" << thisDims[0];
1449  for (size_t i = 1, N = thisDims.size(); i < N; ++i) ostr << " x " << thisDims[i];
1450  ostr << " vs. " << otherDims[0];
1451  for (size_t i = 1, N = otherDims.size(); i < N; ++i) ostr << " x " << otherDims[i];
1452  ostr << ")";
1453  OPENVDB_THROW(TypeError, ostr.str());
1454  }
1455 }
1456 
1457 
1458 template<typename ChildT>
1459 template<typename OtherChildType>
1460 inline bool
1462 {
1463  using OtherValueType = typename OtherChildType::ValueType;
1464  return CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value;
1465 }
1466 
1467 
1468 template<typename ChildT>
1469 template<typename OtherChildType>
1470 inline void
1472 {
1473  using OtherValueType = typename OtherChildType::ValueType;
1475  std::ostringstream ostr;
1476  ostr << "values of type " << typeNameAsString<OtherValueType>()
1477  << " cannot be converted to type " << typeNameAsString<ValueType>();
1478  OPENVDB_THROW(TypeError, ostr.str());
1479  }
1480 }
1481 
1482 
1483 ////////////////////////////////////////
1484 
1485 
1486 template<typename ChildT>
1487 inline Index64
1489 {
1490  Index64 sum = sizeof(*this);
1491  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1492  if (const ChildT *child = iter->second.child) {
1493  sum += child->memUsage();
1494  }
1495  }
1496  return sum;
1497 }
1498 
1499 
1500 template<typename ChildT>
1501 inline void
1503 {
1504  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1505  delete i->second.child;
1506  }
1507  mTable.clear();
1508 }
1509 
1510 
1511 template<typename ChildT>
1512 inline void
1514 {
1515  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1516  if (const ChildT *child = iter->second.child) {
1517  child->evalActiveBoundingBox(bbox, visitVoxels);
1518  } else if (isTileOn(iter)) {
1519  bbox.expand(iter->first, ChildT::DIM);
1520  }
1521  }
1522 }
1523 
1524 
1525 template<typename ChildT>
1526 inline Index
1528  return this->childCount();
1529 }
1530 
1531 
1532 template<typename ChildT>
1533 inline Index
1534 RootNode<ChildT>::getTileCount() const
1535 {
1536  Index sum = 0;
1537  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1538  if (isTile(i)) ++sum;
1539  }
1540  return sum;
1541 }
1542 
1543 
1544 template<typename ChildT>
1545 inline Index
1546 RootNode<ChildT>::getActiveTileCount() const
1547 {
1548  Index sum = 0;
1549  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1550  if (isTileOn(i)) ++sum;
1551  }
1552  return sum;
1553 }
1554 
1555 
1556 template<typename ChildT>
1557 inline Index
1558 RootNode<ChildT>::getInactiveTileCount() const
1559 {
1560  Index sum = 0;
1561  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1562  if (isTileOff(i)) ++sum;
1563  }
1564  return sum;
1565 }
1566 
1567 
1568 template<typename ChildT>
1569 inline Index32
1571 {
1572  Index32 sum = 0;
1573  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1574  if (isChild(i)) sum += getChild(i).leafCount();
1575  }
1576  return sum;
1577 }
1578 
1579 
1580 template<typename ChildT>
1581 inline Index32
1583 {
1584  Index32 sum = 1;
1585  if (ChildT::LEVEL != 0) {
1586  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1587  if (isChild(i)) sum += getChild(i).nonLeafCount();
1588  }
1589  }
1590  return sum;
1591 }
1592 
1593 
1594 template<typename ChildT>
1595 inline Index32
1597 {
1598  Index sum = 0;
1599  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1600  if (isChild(i)) ++sum;
1601  }
1602  return sum;
1603 }
1604 
1605 
1606 template<typename ChildT>
1607 inline Index64
1609 {
1610  Index64 sum = 0;
1611  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1612  if (isChild(i)) {
1613  sum += getChild(i).onVoxelCount();
1614  } else if (isTileOn(i)) {
1615  sum += ChildT::NUM_VOXELS;
1616  }
1617  }
1618  return sum;
1619 }
1620 
1621 
1622 template<typename ChildT>
1623 inline Index64
1625 {
1626  Index64 sum = 0;
1627  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1628  if (isChild(i)) {
1629  sum += getChild(i).offVoxelCount();
1630  } else if (isTileOff(i) && !this->isBackgroundTile(i)) {
1631  sum += ChildT::NUM_VOXELS;
1632  }
1633  }
1634  return sum;
1635 }
1636 
1637 
1638 template<typename ChildT>
1639 inline Index64
1641 {
1642  Index64 sum = 0;
1643  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1644  if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1645  }
1646  return sum;
1647 }
1648 
1649 
1650 template<typename ChildT>
1651 inline Index64
1653 {
1654  Index64 sum = 0;
1655  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1656  if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1657  }
1658  return sum;
1659 }
1660 
1661 template<typename ChildT>
1662 inline Index64
1664 {
1665  Index64 sum = 0;
1666  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1667  if (isChild(i)) {
1668  sum += getChild(i).onTileCount();
1669  } else if (isTileOn(i)) {
1670  sum += 1;
1671  }
1672  }
1673  return sum;
1674 }
1675 
1676 template<typename ChildT>
1677 inline void
1678 RootNode<ChildT>::nodeCount(std::vector<Index32> &vec) const
1679 {
1680  assert(vec.size() > LEVEL);
1681  Index32 sum = 0;
1682  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1683  if (isChild(i)) {
1684  ++sum;
1685  getChild(i).nodeCount(vec);
1686  }
1687  }
1688  vec[LEVEL] = 1;// one root node
1689  vec[ChildNodeType::LEVEL] = sum;
1690 }
1691 
1692 ////////////////////////////////////////
1693 
1694 
1695 template<typename ChildT>
1696 inline bool
1697 RootNode<ChildT>::isValueOn(const Coord& xyz) const
1698 {
1699  MapCIter iter = this->findCoord(xyz);
1700  if (iter == mTable.end() || isTileOff(iter)) return false;
1701  return isTileOn(iter) ? true : getChild(iter).isValueOn(xyz);
1702 }
1703 
1704 template<typename ChildT>
1705 inline bool
1707 {
1708  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1709  if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active) return true;
1710  }
1711  return false;
1712 }
1713 
1714 template<typename ChildT>
1715 template<typename AccessorT>
1716 inline bool
1717 RootNode<ChildT>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const
1718 {
1719  MapCIter iter = this->findCoord(xyz);
1720  if (iter == mTable.end() || isTileOff(iter)) return false;
1721  if (isTileOn(iter)) return true;
1722  acc.insert(xyz, &getChild(iter));
1723  return getChild(iter).isValueOnAndCache(xyz, acc);
1724 }
1725 
1726 
1727 template<typename ChildT>
1728 inline const typename ChildT::ValueType&
1729 RootNode<ChildT>::getValue(const Coord& xyz) const
1730 {
1731  MapCIter iter = this->findCoord(xyz);
1732  return iter == mTable.end() ? mBackground
1733  : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1734 }
1735 
1736 template<typename ChildT>
1737 template<typename AccessorT>
1738 inline const typename ChildT::ValueType&
1739 RootNode<ChildT>::getValueAndCache(const Coord& xyz, AccessorT& acc) const
1740 {
1741  MapCIter iter = this->findCoord(xyz);
1742  if (iter == mTable.end()) return mBackground;
1743  if (isChild(iter)) {
1744  acc.insert(xyz, &getChild(iter));
1745  return getChild(iter).getValueAndCache(xyz, acc);
1746  }
1747  return getTile(iter).value;
1748 }
1749 
1750 
1751 template<typename ChildT>
1752 inline int
1753 RootNode<ChildT>::getValueDepth(const Coord& xyz) const
1754 {
1755  MapCIter iter = this->findCoord(xyz);
1756  return iter == mTable.end() ? -1
1757  : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1758 }
1759 
1760 template<typename ChildT>
1761 template<typename AccessorT>
1762 inline int
1763 RootNode<ChildT>::getValueDepthAndCache(const Coord& xyz, AccessorT& acc) const
1764 {
1765  MapCIter iter = this->findCoord(xyz);
1766  if (iter == mTable.end()) return -1;
1767  if (isTile(iter)) return 0;
1768  acc.insert(xyz, &getChild(iter));
1769  return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1770 }
1771 
1772 
1773 template<typename ChildT>
1774 inline void
1776 {
1777  MapIter iter = this->findCoord(xyz);
1778  if (iter != mTable.end() && !isTileOff(iter)) {
1779  if (isTileOn(iter)) {
1780  setChild(iter, *new ChildT(xyz, getTile(iter).value, /*active=*/true));
1781  }
1782  getChild(iter).setValueOff(xyz);
1783  }
1784 }
1785 
1786 
1787 template<typename ChildT>
1788 inline void
1789 RootNode<ChildT>::setActiveState(const Coord& xyz, bool on)
1790 {
1791  ChildT* child = nullptr;
1792  MapIter iter = this->findCoord(xyz);
1793  if (iter == mTable.end()) {
1794  if (on) {
1795  child = new ChildT(xyz, mBackground);
1796  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1797  } else {
1798  // Nothing to do; (x, y, z) is background and therefore already inactive.
1799  }
1800  } else if (isChild(iter)) {
1801  child = &getChild(iter);
1802  } else if (on != getTile(iter).active) {
1803  child = new ChildT(xyz, getTile(iter).value, !on);
1804  setChild(iter, *child);
1805  }
1806  if (child) child->setActiveState(xyz, on);
1807 }
1808 
1809 template<typename ChildT>
1810 template<typename AccessorT>
1811 inline void
1812 RootNode<ChildT>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc)
1813 {
1814  ChildT* child = nullptr;
1815  MapIter iter = this->findCoord(xyz);
1816  if (iter == mTable.end()) {
1817  if (on) {
1818  child = new ChildT(xyz, mBackground);
1819  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1820  } else {
1821  // Nothing to do; (x, y, z) is background and therefore already inactive.
1822  }
1823  } else if (isChild(iter)) {
1824  child = &getChild(iter);
1825  } else if (on != getTile(iter).active) {
1826  child = new ChildT(xyz, getTile(iter).value, !on);
1827  setChild(iter, *child);
1828  }
1829  if (child) {
1830  acc.insert(xyz, child);
1831  child->setActiveStateAndCache(xyz, on, acc);
1832  }
1833 }
1834 
1835 
1836 template<typename ChildT>
1837 inline void
1838 RootNode<ChildT>::setValueOff(const Coord& xyz, const ValueType& value)
1839 {
1840  ChildT* child = nullptr;
1841  MapIter iter = this->findCoord(xyz);
1842  if (iter == mTable.end()) {
1843  if (!math::isExactlyEqual(mBackground, value)) {
1844  child = new ChildT(xyz, mBackground);
1845  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1846  }
1847  } else if (isChild(iter)) {
1848  child = &getChild(iter);
1849  } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1850  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1851  setChild(iter, *child);
1852  }
1853  if (child) child->setValueOff(xyz, value);
1854 }
1855 
1856 template<typename ChildT>
1857 template<typename AccessorT>
1858 inline void
1859 RootNode<ChildT>::setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1860 {
1861  ChildT* child = nullptr;
1862  MapIter iter = this->findCoord(xyz);
1863  if (iter == mTable.end()) {
1864  if (!math::isExactlyEqual(mBackground, value)) {
1865  child = new ChildT(xyz, mBackground);
1866  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1867  }
1868  } else if (isChild(iter)) {
1869  child = &getChild(iter);
1870  } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1871  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1872  setChild(iter, *child);
1873  }
1874  if (child) {
1875  acc.insert(xyz, child);
1876  child->setValueOffAndCache(xyz, value, acc);
1877  }
1878 }
1879 
1880 
1881 template<typename ChildT>
1882 inline void
1883 RootNode<ChildT>::setValueOn(const Coord& xyz, const ValueType& value)
1884 {
1885  ChildT* child = nullptr;
1886  MapIter iter = this->findCoord(xyz);
1887  if (iter == mTable.end()) {
1888  child = new ChildT(xyz, mBackground);
1889  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1890  } else if (isChild(iter)) {
1891  child = &getChild(iter);
1892  } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1893  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1894  setChild(iter, *child);
1895  }
1896  if (child) child->setValueOn(xyz, value);
1897 }
1898 
1899 template<typename ChildT>
1900 template<typename AccessorT>
1901 inline void
1902 RootNode<ChildT>::setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1903 {
1904  ChildT* child = nullptr;
1905  MapIter iter = this->findCoord(xyz);
1906  if (iter == mTable.end()) {
1907  child = new ChildT(xyz, mBackground);
1908  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1909  } else if (isChild(iter)) {
1910  child = &getChild(iter);
1911  } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1912  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1913  setChild(iter, *child);
1914  }
1915  if (child) {
1916  acc.insert(xyz, child);
1917  child->setValueAndCache(xyz, value, acc);
1918  }
1919 }
1920 
1921 
1922 template<typename ChildT>
1923 inline void
1924 RootNode<ChildT>::setValueOnly(const Coord& xyz, const ValueType& value)
1925 {
1926  ChildT* child = nullptr;
1927  MapIter iter = this->findCoord(xyz);
1928  if (iter == mTable.end()) {
1929  child = new ChildT(xyz, mBackground);
1930  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1931  } else if (isChild(iter)) {
1932  child = &getChild(iter);
1933  } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1934  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1935  setChild(iter, *child);
1936  }
1937  if (child) child->setValueOnly(xyz, value);
1938 }
1939 
1940 template<typename ChildT>
1941 template<typename AccessorT>
1942 inline void
1943 RootNode<ChildT>::setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1944 {
1945  ChildT* child = nullptr;
1946  MapIter iter = this->findCoord(xyz);
1947  if (iter == mTable.end()) {
1948  child = new ChildT(xyz, mBackground);
1949  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1950  } else if (isChild(iter)) {
1951  child = &getChild(iter);
1952  } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1953  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1954  setChild(iter, *child);
1955  }
1956  if (child) {
1957  acc.insert(xyz, child);
1958  child->setValueOnlyAndCache(xyz, value, acc);
1959  }
1960 }
1961 
1962 
1963 template<typename ChildT>
1964 template<typename ModifyOp>
1965 inline void
1966 RootNode<ChildT>::modifyValue(const Coord& xyz, const ModifyOp& op)
1967 {
1968  ChildT* child = nullptr;
1969  MapIter iter = this->findCoord(xyz);
1970  if (iter == mTable.end()) {
1971  child = new ChildT(xyz, mBackground);
1972  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1973  } else if (isChild(iter)) {
1974  child = &getChild(iter);
1975  } else {
1976  // Need to create a child if the tile is inactive,
1977  // in order to activate voxel (x, y, z).
1978  bool createChild = isTileOff(iter);
1979  if (!createChild) {
1980  // Need to create a child if applying the functor
1981  // to the tile value produces a different value.
1982  const ValueType& tileVal = getTile(iter).value;
1983  ValueType modifiedVal = tileVal;
1984  op(modifiedVal);
1985  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1986  }
1987  if (createChild) {
1988  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1989  setChild(iter, *child);
1990  }
1991  }
1992  if (child) child->modifyValue(xyz, op);
1993 }
1994 
1995 template<typename ChildT>
1996 template<typename ModifyOp, typename AccessorT>
1997 inline void
1998 RootNode<ChildT>::modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT& acc)
1999 {
2000  ChildT* child = nullptr;
2001  MapIter iter = this->findCoord(xyz);
2002  if (iter == mTable.end()) {
2003  child = new ChildT(xyz, mBackground);
2004  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2005  } else if (isChild(iter)) {
2006  child = &getChild(iter);
2007  } else {
2008  // Need to create a child if the tile is inactive,
2009  // in order to activate voxel (x, y, z).
2010  bool createChild = isTileOff(iter);
2011  if (!createChild) {
2012  // Need to create a child if applying the functor
2013  // to the tile value produces a different value.
2014  const ValueType& tileVal = getTile(iter).value;
2015  ValueType modifiedVal = tileVal;
2016  op(modifiedVal);
2017  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
2018  }
2019  if (createChild) {
2020  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2021  setChild(iter, *child);
2022  }
2023  }
2024  if (child) {
2025  acc.insert(xyz, child);
2026  child->modifyValueAndCache(xyz, op, acc);
2027  }
2028 }
2029 
2030 
2031 template<typename ChildT>
2032 template<typename ModifyOp>
2033 inline void
2034 RootNode<ChildT>::modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
2035 {
2036  ChildT* child = nullptr;
2037  MapIter iter = this->findCoord(xyz);
2038  if (iter == mTable.end()) {
2039  child = new ChildT(xyz, mBackground);
2040  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2041  } else if (isChild(iter)) {
2042  child = &getChild(iter);
2043  } else {
2044  const Tile& tile = getTile(iter);
2045  bool modifiedState = tile.active;
2046  ValueType modifiedVal = tile.value;
2047  op(modifiedVal, modifiedState);
2048  // Need to create a child if applying the functor to the tile
2049  // produces a different value or active state.
2050  if (modifiedState != tile.active || !math::isExactlyEqual(modifiedVal, tile.value)) {
2051  child = new ChildT(xyz, tile.value, tile.active);
2052  setChild(iter, *child);
2053  }
2054  }
2055  if (child) child->modifyValueAndActiveState(xyz, op);
2056 }
2057 
2058 template<typename ChildT>
2059 template<typename ModifyOp, typename AccessorT>
2060 inline void
2062  const Coord& xyz, const ModifyOp& op, AccessorT& acc)
2063 {
2064  ChildT* child = nullptr;
2065  MapIter iter = this->findCoord(xyz);
2066  if (iter == mTable.end()) {
2067  child = new ChildT(xyz, mBackground);
2068  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2069  } else if (isChild(iter)) {
2070  child = &getChild(iter);
2071  } else {
2072  const Tile& tile = getTile(iter);
2073  bool modifiedState = tile.active;
2074  ValueType modifiedVal = tile.value;
2075  op(modifiedVal, modifiedState);
2076  // Need to create a child if applying the functor to the tile
2077  // produces a different value or active state.
2078  if (modifiedState != tile.active || !math::isExactlyEqual(modifiedVal, tile.value)) {
2079  child = new ChildT(xyz, tile.value, tile.active);
2080  setChild(iter, *child);
2081  }
2082  }
2083  if (child) {
2084  acc.insert(xyz, child);
2085  child->modifyValueAndActiveStateAndCache(xyz, op, acc);
2086  }
2087 }
2088 
2089 
2090 template<typename ChildT>
2091 inline bool
2092 RootNode<ChildT>::probeValue(const Coord& xyz, ValueType& value) const
2093 {
2094  MapCIter iter = this->findCoord(xyz);
2095  if (iter == mTable.end()) {
2096  value = mBackground;
2097  return false;
2098  } else if (isChild(iter)) {
2099  return getChild(iter).probeValue(xyz, value);
2100  }
2101  value = getTile(iter).value;
2102  return isTileOn(iter);
2103 }
2104 
2105 template<typename ChildT>
2106 template<typename AccessorT>
2107 inline bool
2108 RootNode<ChildT>::probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT& acc) const
2109 {
2110  MapCIter iter = this->findCoord(xyz);
2111  if (iter == mTable.end()) {
2112  value = mBackground;
2113  return false;
2114  } else if (isChild(iter)) {
2115  acc.insert(xyz, &getChild(iter));
2116  return getChild(iter).probeValueAndCache(xyz, value, acc);
2117  }
2118  value = getTile(iter).value;
2119  return isTileOn(iter);
2120 }
2121 
2122 
2123 ////////////////////////////////////////
2124 
2125 
2126 template<typename ChildT>
2127 inline void
2128 RootNode<ChildT>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
2129 {
2130  if (bbox.empty()) return;
2131 
2132  // Iterate over the fill region in axis-aligned, tile-sized chunks.
2133  // (The first and last chunks along each axis might be smaller than a tile.)
2134  Coord xyz, tileMax;
2135  for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
2136  xyz.setX(x);
2137  for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
2138  xyz.setY(y);
2139  for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
2140  xyz.setZ(z);
2141 
2142  // Get the bounds of the tile that contains voxel (x, y, z).
2143  Coord tileMin = coordToKey(xyz);
2144  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2145 
2146  if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
2147  // If the box defined by (xyz, bbox.max()) doesn't completely enclose
2148  // the tile to which xyz belongs, create a child node (or retrieve
2149  // the existing one).
2150  ChildT* child = nullptr;
2151  MapIter iter = this->findKey(tileMin);
2152  if (iter == mTable.end()) {
2153  // No child or tile exists. Create a child and initialize it
2154  // with the background value.
2155  child = new ChildT(xyz, mBackground);
2156  mTable[tileMin] = NodeStruct(*child);
2157  } else if (isTile(iter)) {
2158  // Replace the tile with a newly-created child that is filled
2159  // with the tile's value and active state.
2160  const Tile& tile = getTile(iter);
2161  child = new ChildT(xyz, tile.value, tile.active);
2162  mTable[tileMin] = NodeStruct(*child);
2163  } else if (isChild(iter)) {
2164  child = &getChild(iter);
2165  }
2166  // Forward the fill request to the child.
2167  if (child) {
2168  const Coord tmp = Coord::minComponent(bbox.max(), tileMax);
2169  child->fill(CoordBBox(xyz, tmp), value, active);
2170  }
2171  } else {
2172  // If the box given by (xyz, bbox.max()) completely encloses
2173  // the tile to which xyz belongs, create the tile (if it
2174  // doesn't already exist) and give it the fill value.
2175  MapIter iter = this->findOrAddCoord(tileMin);
2176  setTile(iter, Tile(value, active));
2177  }
2178  }
2179  }
2180  }
2181 }
2182 
2183 
2184 template<typename ChildT>
2185 inline void
2186 RootNode<ChildT>::denseFill(const CoordBBox& bbox, const ValueType& value, bool active)
2187 {
2188  if (bbox.empty()) return;
2189 
2190  if (active && mTable.empty()) {
2191  // If this tree is empty, then a sparse fill followed by (threaded)
2192  // densification of active tiles is the more efficient approach.
2193  sparseFill(bbox, value, active);
2194  voxelizeActiveTiles(/*threaded=*/true);
2195  return;
2196  }
2197 
2198  // Iterate over the fill region in axis-aligned, tile-sized chunks.
2199  // (The first and last chunks along each axis might be smaller than a tile.)
2200  Coord xyz, tileMin, tileMax;
2201  for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
2202  xyz.setX(x);
2203  for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
2204  xyz.setY(y);
2205  for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
2206  xyz.setZ(z);
2207 
2208  // Get the bounds of the tile that contains voxel (x, y, z).
2209  tileMin = coordToKey(xyz);
2210  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2211 
2212  // Retrieve the table entry for the tile that contains xyz,
2213  // or, if there is no table entry, add a background tile.
2214  const auto iter = findOrAddCoord(tileMin);
2215 
2216  if (isTile(iter)) {
2217  // If the table entry is a tile, replace it with a child node
2218  // that is filled with the tile's value and active state.
2219  const auto& tile = getTile(iter);
2220  auto* child = new ChildT{tileMin, tile.value, tile.active};
2221  setChild(iter, *child);
2222  }
2223  // Forward the fill request to the child.
2224  getChild(iter).denseFill(bbox, value, active);
2225  }
2226  }
2227  }
2228 }
2229 
2230 
2231 ////////////////////////////////////////
2232 
2233 
2234 template<typename ChildT>
2235 inline void
2237 {
2238  // There is little point in threading over the root table since each tile
2239  // spans a huge index space (by default 4096^3) and hence we expect few
2240  // active tiles if any at all. In fact, you're very likely to run out of
2241  // memory if this method is called on a tree with root-level active tiles!
2242  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2243  if (this->isTileOff(i)) continue;
2244  ChildT* child = i->second.child;
2245  if (child == nullptr) {
2246  // If this table entry is an active tile (i.e., not off and not a child node),
2247  // replace it with a child node filled with active tiles of the same value.
2248  child = new ChildT{i->first, this->getTile(i).value, true};
2249  i->second.child = child;
2250  }
2251  child->voxelizeActiveTiles(threaded);
2252  }
2253 }
2254 
2255 
2256 ////////////////////////////////////////
2257 
2258 
2259 template<typename ChildT>
2260 template<typename DenseT>
2261 inline void
2262 RootNode<ChildT>::copyToDense(const CoordBBox& bbox, DenseT& dense) const
2263 {
2264  using DenseValueType = typename DenseT::ValueType;
2265 
2266  const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2267  const Coord& min = dense.bbox().min();
2268  CoordBBox nodeBBox;
2269  for (Coord xyz = bbox.min(); xyz[0] <= bbox.max()[0]; xyz[0] = nodeBBox.max()[0] + 1) {
2270  for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = nodeBBox.max()[1] + 1) {
2271  for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = nodeBBox.max()[2] + 1) {
2272 
2273  // Get the coordinate bbox of the child node that contains voxel xyz.
2274  nodeBBox = CoordBBox::createCube(coordToKey(xyz), ChildT::DIM);
2275 
2276  // Get the coordinate bbox of the interection of inBBox and nodeBBox
2277  CoordBBox sub(xyz, Coord::minComponent(bbox.max(), nodeBBox.max()));
2278 
2279  MapCIter iter = this->findKey(nodeBBox.min());
2280  if (iter != mTable.end() && isChild(iter)) {//is a child
2281  getChild(iter).copyToDense(sub, dense);
2282  } else {//is background or a tile value
2283  const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value;
2284  sub.translate(-min);
2285  DenseValueType* a0 = dense.data() + zStride*sub.min()[2];
2286  for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
2287  DenseValueType* a1 = a0 + x*xStride;
2288  for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
2289  DenseValueType* a2 = a1 + y*yStride;
2290  for (Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z, a2 += zStride) {
2291  *a2 = DenseValueType(value);
2292  }
2293  }
2294  }
2295  }
2296  }
2297  }
2298  }
2299 }
2300 
2301 ////////////////////////////////////////
2302 
2303 
2304 template<typename ChildT>
2305 inline bool
2306 RootNode<ChildT>::writeTopology(std::ostream& os, bool toHalf) const
2307 {
2308  if (!toHalf) {
2309  os.write(reinterpret_cast<const char*>(&mBackground), sizeof(ValueType));
2310  } else {
2311  ValueType truncatedVal = io::truncateRealToHalf(mBackground);
2312  os.write(reinterpret_cast<const char*>(&truncatedVal), sizeof(ValueType));
2313  }
2314  io::setGridBackgroundValuePtr(os, &mBackground);
2315 
2316  const Index numTiles = this->getTileCount(), numChildren = this->childCount();
2317  os.write(reinterpret_cast<const char*>(&numTiles), sizeof(Index));
2318  os.write(reinterpret_cast<const char*>(&numChildren), sizeof(Index));
2319 
2320  if (numTiles == 0 && numChildren == 0) return false;
2321 
2322  // Write tiles.
2323  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2324  if (isChild(i)) continue;
2325  os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
2326  os.write(reinterpret_cast<const char*>(&getTile(i).value), sizeof(ValueType));
2327  os.write(reinterpret_cast<const char*>(&getTile(i).active), sizeof(bool));
2328  }
2329  // Write child nodes.
2330  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2331  if (isTile(i)) continue;
2332  os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
2333  getChild(i).writeTopology(os, toHalf);
2334  }
2335 
2336  return true; // not empty
2337 }
2338 
2339 
2340 template<typename ChildT>
2341 inline bool
2342 RootNode<ChildT>::readTopology(std::istream& is, bool fromHalf)
2343 {
2344  // Delete the existing tree.
2345  this->clear();
2346 
2348  // Read and convert an older-format RootNode.
2349 
2350  // For backward compatibility with older file formats, read both
2351  // outside and inside background values.
2352  is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
2353  ValueType inside;
2354  is.read(reinterpret_cast<char*>(&inside), sizeof(ValueType));
2355 
2356  io::setGridBackgroundValuePtr(is, &mBackground);
2357 
2358  // Read the index range.
2359  Coord rangeMin, rangeMax;
2360  is.read(reinterpret_cast<char*>(rangeMin.asPointer()), 3 * sizeof(Int32));
2361  is.read(reinterpret_cast<char*>(rangeMax.asPointer()), 3 * sizeof(Int32));
2362 
2363  this->initTable();
2364  Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
2365  Int32 offset[3];
2366  for (int i = 0; i < 3; ++i) {
2367  offset[i] = rangeMin[i] >> ChildT::TOTAL;
2368  rangeMin[i] = offset[i] << ChildT::TOTAL;
2369  log2Dim[i] = 1 + util::FindHighestOn((rangeMax[i] >> ChildT::TOTAL) - offset[i]);
2370  tableSize += log2Dim[i];
2371  rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
2372  }
2373  log2Dim[3] = log2Dim[1] + log2Dim[2];
2374  tableSize = 1U << tableSize;
2375 
2376  // Read masks.
2377  util::RootNodeMask childMask(tableSize), valueMask(tableSize);
2378  childMask.load(is);
2379  valueMask.load(is);
2380 
2381  // Read child nodes/values.
2382  for (Index i = 0; i < tableSize; ++i) {
2383  // Compute origin = offset2coord(i).
2384  Index n = i;
2385  Coord origin;
2386  origin[0] = (n >> log2Dim[3]) + offset[0];
2387  n &= (1U << log2Dim[3]) - 1;
2388  origin[1] = (n >> log2Dim[2]) + offset[1];
2389  origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
2390  origin <<= ChildT::TOTAL;
2391 
2392  if (childMask.isOn(i)) {
2393  // Read in and insert a child node.
2394  ChildT* child = new ChildT(PartialCreate(), origin, mBackground);
2395  child->readTopology(is);
2396  mTable[origin] = NodeStruct(*child);
2397  } else {
2398  // Read in a tile value and insert a tile, but only if the value
2399  // is either active or non-background.
2400  ValueType value;
2401  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2402  if (valueMask.isOn(i) || (!math::isApproxEqual(value, mBackground))) {
2403  mTable[origin] = NodeStruct(Tile(value, valueMask.isOn(i)));
2404  }
2405  }
2406  }
2407  return true;
2408  }
2409 
2410  // Read a RootNode that was stored in the current format.
2411 
2412  is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
2413  io::setGridBackgroundValuePtr(is, &mBackground);
2414 
2415  Index numTiles = 0, numChildren = 0;
2416  is.read(reinterpret_cast<char*>(&numTiles), sizeof(Index));
2417  is.read(reinterpret_cast<char*>(&numChildren), sizeof(Index));
2418 
2419  if (numTiles == 0 && numChildren == 0) return false;
2420 
2421  Int32 vec[3];
2422  ValueType value;
2423  bool active;
2424 
2425  // Read tiles.
2426  for (Index n = 0; n < numTiles; ++n) {
2427  is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
2428  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2429  is.read(reinterpret_cast<char*>(&active), sizeof(bool));
2430  mTable[Coord(vec)] = NodeStruct(Tile(value, active));
2431  }
2432 
2433  // Read child nodes.
2434  for (Index n = 0; n < numChildren; ++n) {
2435  is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
2436  Coord origin(vec);
2437  ChildT* child = new ChildT(PartialCreate(), origin, mBackground);
2438  child->readTopology(is, fromHalf);
2439  mTable[Coord(vec)] = NodeStruct(*child);
2440  }
2441 
2442  return true; // not empty
2443 }
2444 
2445 
2446 template<typename ChildT>
2447 inline void
2448 RootNode<ChildT>::writeBuffers(std::ostream& os, bool toHalf) const
2449 {
2450  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2451  if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
2452  }
2453 }
2454 
2455 
2456 template<typename ChildT>
2457 inline void
2458 RootNode<ChildT>::readBuffers(std::istream& is, bool fromHalf)
2459 {
2460  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2461  if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
2462  }
2463 }
2464 
2465 
2466 template<typename ChildT>
2467 inline void
2468 RootNode<ChildT>::readBuffers(std::istream& is, const CoordBBox& clipBBox, bool fromHalf)
2469 {
2470  const Tile bgTile(mBackground, /*active=*/false);
2471 
2472  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2473  if (isChild(i)) {
2474  // Stream in and clip the branch rooted at this child.
2475  // (We can't skip over children that lie outside the clipping region,
2476  // because buffers are serialized in depth-first order and need to be
2477  // unserialized in the same order.)
2478  ChildT& child = getChild(i);
2479  child.readBuffers(is, clipBBox, fromHalf);
2480  }
2481  }
2482  // Clip root-level tiles and prune children that were clipped.
2483  this->clip(clipBBox);
2484 }
2485 
2486 
2487 ////////////////////////////////////////
2488 
2489 
2490 template<typename ChildT>
2491 inline void
2493 {
2494  const Tile bgTile(mBackground, /*active=*/false);
2495 
2496  // Iterate over a copy of this node's table so that we can modify the original.
2497  // (Copying the table copies child node pointers, not the nodes themselves.)
2498  MapType copyOfTable(mTable);
2499  for (MapIter i = copyOfTable.begin(), e = copyOfTable.end(); i != e; ++i) {
2500  const Coord& xyz = i->first; // tile or child origin
2501  CoordBBox tileBBox(xyz, xyz.offsetBy(ChildT::DIM - 1)); // tile or child bounds
2502  if (!clipBBox.hasOverlap(tileBBox)) {
2503  // This table entry lies completely outside the clipping region. Delete it.
2504  setTile(this->findCoord(xyz), bgTile); // delete any existing child node first
2505  mTable.erase(xyz);
2506  } else if (!clipBBox.isInside(tileBBox)) {
2507  // This table entry does not lie completely inside the clipping region
2508  // and must be clipped.
2509  if (isChild(i)) {
2510  getChild(i).clip(clipBBox, mBackground);
2511  } else {
2512  // Replace this tile with a background tile, then fill the clip region
2513  // with the tile's original value. (This might create a child branch.)
2514  tileBBox.intersect(clipBBox);
2515  const Tile& origTile = getTile(i);
2516  setTile(this->findCoord(xyz), bgTile);
2517  this->sparseFill(tileBBox, origTile.value, origTile.active);
2518  }
2519  } else {
2520  // This table entry lies completely inside the clipping region. Leave it intact.
2521  }
2522  }
2523  this->prune(); // also erases root-level background tiles
2524 }
2525 
2526 
2527 ////////////////////////////////////////
2528 
2529 
2530 template<typename ChildT>
2531 inline void
2533 {
2534  bool state = false;
2535  ValueType value = zeroVal<ValueType>();
2536  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2537  if (this->isTile(i)) continue;
2538  this->getChild(i).prune(tolerance);
2539  if (this->getChild(i).isConstant(value, state, tolerance)) {
2540  this->setTile(i, Tile(value, state));
2541  }
2542  }
2543  this->eraseBackgroundTiles();
2544 }
2545 
2546 
2547 ////////////////////////////////////////
2548 
2549 
2550 template<typename ChildT>
2551 template<typename NodeT>
2552 inline NodeT*
2553 RootNode<ChildT>::stealNode(const Coord& xyz, const ValueType& value, bool state)
2554 {
2555  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2556  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2558  MapIter iter = this->findCoord(xyz);
2559  if (iter == mTable.end() || isTile(iter)) return nullptr;
2561  ? reinterpret_cast<NodeT*>(&stealChild(iter, Tile(value, state)))
2562  : getChild(iter).template stealNode<NodeT>(xyz, value, state);
2564 }
2565 
2566 
2567 ////////////////////////////////////////
2568 
2569 
2570 template<typename ChildT>
2571 inline void
2573 {
2574  if (leaf == nullptr) return;
2575  ChildT* child = nullptr;
2576  const Coord& xyz = leaf->origin();
2577  MapIter iter = this->findCoord(xyz);
2578  if (iter == mTable.end()) {
2579  if (ChildT::LEVEL>0) {
2580  child = new ChildT(xyz, mBackground, false);
2581  } else {
2582  child = reinterpret_cast<ChildT*>(leaf);
2583  }
2584  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2585  } else if (isChild(iter)) {
2586  if (ChildT::LEVEL>0) {
2587  child = &getChild(iter);
2588  } else {
2589  child = reinterpret_cast<ChildT*>(leaf);
2590  setChild(iter, *child);//this also deletes the existing child node
2591  }
2592  } else {//tile
2593  if (ChildT::LEVEL>0) {
2594  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2595  } else {
2596  child = reinterpret_cast<ChildT*>(leaf);
2597  }
2598  setChild(iter, *child);
2599  }
2600  child->addLeaf(leaf);
2601 }
2602 
2603 
2604 template<typename ChildT>
2605 template<typename AccessorT>
2606 inline void
2608 {
2609  if (leaf == nullptr) return;
2610  ChildT* child = nullptr;
2611  const Coord& xyz = leaf->origin();
2612  MapIter iter = this->findCoord(xyz);
2613  if (iter == mTable.end()) {
2614  if (ChildT::LEVEL>0) {
2615  child = new ChildT(xyz, mBackground, false);
2616  } else {
2617  child = reinterpret_cast<ChildT*>(leaf);
2618  }
2619  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2620  } else if (isChild(iter)) {
2621  if (ChildT::LEVEL>0) {
2622  child = &getChild(iter);
2623  } else {
2624  child = reinterpret_cast<ChildT*>(leaf);
2625  setChild(iter, *child);//this also deletes the existing child node
2626  }
2627  } else {//tile
2628  if (ChildT::LEVEL>0) {
2629  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2630  } else {
2631  child = reinterpret_cast<ChildT*>(leaf);
2632  }
2633  setChild(iter, *child);
2634  }
2635  acc.insert(xyz, child);
2636  child->addLeafAndCache(leaf, acc);
2637 }
2638 
2639 template<typename ChildT>
2640 inline bool
2641 RootNode<ChildT>::addChild(ChildT* child)
2642 {
2643  if (!child) return false;
2644  const Coord& xyz = child->origin();
2645  MapIter iter = this->findCoord(xyz);
2646  if (iter == mTable.end()) {//background
2647  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2648  } else {//child or tile
2649  setChild(iter, *child);//this also deletes the existing child node
2650  }
2651  return true;
2652 }
2653 
2654 #if OPENVDB_ABI_VERSION_NUMBER >= 10
2655 template<typename ChildT>
2656 inline void
2657 RootNode<ChildT>::setOrigin(const Coord &origin)
2658 {
2659  mOrigin = origin;
2660  if (mOrigin != Coord(0,0,0)) {
2661  OPENVDB_THROW(ValueError, "RootNode::setOrigin: non-zero offsets are currently not supported");
2662  }
2663 }
2664 #endif
2665 
2666 template<typename ChildT>
2667 inline void
2668 RootNode<ChildT>::addTile(const Coord& xyz, const ValueType& value, bool state)
2669 {
2670  MapIter iter = this->findCoord(xyz);
2671  if (iter == mTable.end()) {//background
2672  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2673  } else {//child or tile
2674  setTile(iter, Tile(value, state));//this also deletes the existing child node
2675  }
2676 }
2677 
2678 template<typename ChildT>
2679 inline void
2681  const ValueType& value, bool state)
2682 {
2683  if (LEVEL >= level) {
2684  MapIter iter = this->findCoord(xyz);
2685  if (iter == mTable.end()) {//background
2686  if (LEVEL > level) {
2687  ChildT* child = new ChildT(xyz, mBackground, false);
2688  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2689  child->addTile(level, xyz, value, state);
2690  } else {
2691  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2692  }
2693  } else if (isChild(iter)) {//child
2694  if (LEVEL > level) {
2695  getChild(iter).addTile(level, xyz, value, state);
2696  } else {
2697  setTile(iter, Tile(value, state));//this also deletes the existing child node
2698  }
2699  } else {//tile
2700  if (LEVEL > level) {
2701  ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2702  setChild(iter, *child);
2703  child->addTile(level, xyz, value, state);
2704  } else {
2705  setTile(iter, Tile(value, state));
2706  }
2707  }
2708  }
2709 }
2710 
2711 
2712 template<typename ChildT>
2713 template<typename AccessorT>
2714 inline void
2715 RootNode<ChildT>::addTileAndCache(Index level, const Coord& xyz, const ValueType& value,
2716  bool state, AccessorT& acc)
2717 {
2718  if (LEVEL >= level) {
2719  MapIter iter = this->findCoord(xyz);
2720  if (iter == mTable.end()) {//background
2721  if (LEVEL > level) {
2722  ChildT* child = new ChildT(xyz, mBackground, false);
2723  acc.insert(xyz, child);
2724  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2725  child->addTileAndCache(level, xyz, value, state, acc);
2726  } else {
2727  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2728  }
2729  } else if (isChild(iter)) {//child
2730  if (LEVEL > level) {
2731  ChildT* child = &getChild(iter);
2732  acc.insert(xyz, child);
2733  child->addTileAndCache(level, xyz, value, state, acc);
2734  } else {
2735  setTile(iter, Tile(value, state));//this also deletes the existing child node
2736  }
2737  } else {//tile
2738  if (LEVEL > level) {
2739  ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2740  acc.insert(xyz, child);
2741  setChild(iter, *child);
2742  child->addTileAndCache(level, xyz, value, state, acc);
2743  } else {
2744  setTile(iter, Tile(value, state));
2745  }
2746  }
2747  }
2748 }
2749 
2750 
2751 ////////////////////////////////////////
2752 
2753 
2754 template<typename ChildT>
2755 inline typename ChildT::LeafNodeType*
2757 {
2758  ChildT* child = nullptr;
2759  MapIter iter = this->findCoord(xyz);
2760  if (iter == mTable.end()) {
2761  child = new ChildT(xyz, mBackground, false);
2762  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2763  } else if (isChild(iter)) {
2764  child = &getChild(iter);
2765  } else {
2766  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2767  setChild(iter, *child);
2768  }
2769  return child->touchLeaf(xyz);
2770 }
2771 
2772 
2773 template<typename ChildT>
2774 template<typename AccessorT>
2775 inline typename ChildT::LeafNodeType*
2776 RootNode<ChildT>::touchLeafAndCache(const Coord& xyz, AccessorT& acc)
2777 {
2778  ChildT* child = nullptr;
2779  MapIter iter = this->findCoord(xyz);
2780  if (iter == mTable.end()) {
2781  child = new ChildT(xyz, mBackground, false);
2782  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2783  } else if (isChild(iter)) {
2784  child = &getChild(iter);
2785  } else {
2786  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2787  setChild(iter, *child);
2788  }
2789  acc.insert(xyz, child);
2790  return child->touchLeafAndCache(xyz, acc);
2791 }
2792 
2793 
2794 ////////////////////////////////////////
2795 
2796 
2797 template<typename ChildT>
2798 template<typename NodeT>
2799 inline NodeT*
2801 {
2802  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2803  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2805  MapIter iter = this->findCoord(xyz);
2806  if (iter == mTable.end() || isTile(iter)) return nullptr;
2807  ChildT* child = &getChild(iter);
2809  ? reinterpret_cast<NodeT*>(child)
2810  : child->template probeNode<NodeT>(xyz);
2812 }
2813 
2814 
2815 template<typename ChildT>
2816 template<typename NodeT>
2817 inline const NodeT*
2818 RootNode<ChildT>::probeConstNode(const Coord& xyz) const
2819 {
2820  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2821  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2823  MapCIter iter = this->findCoord(xyz);
2824  if (iter == mTable.end() || isTile(iter)) return nullptr;
2825  const ChildT* child = &getChild(iter);
2827  ? reinterpret_cast<const NodeT*>(child)
2828  : child->template probeConstNode<NodeT>(xyz);
2830 }
2831 
2832 
2833 template<typename ChildT>
2834 inline typename ChildT::LeafNodeType*
2836 {
2837  return this->template probeNode<LeafNodeType>(xyz);
2838 }
2839 
2840 
2841 template<typename ChildT>
2842 inline const typename ChildT::LeafNodeType*
2843 RootNode<ChildT>::probeConstLeaf(const Coord& xyz) const
2844 {
2845  return this->template probeConstNode<LeafNodeType>(xyz);
2846 }
2847 
2848 
2849 template<typename ChildT>
2850 template<typename AccessorT>
2851 inline typename ChildT::LeafNodeType*
2852 RootNode<ChildT>::probeLeafAndCache(const Coord& xyz, AccessorT& acc)
2853 {
2854  return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
2855 }
2856 
2857 
2858 template<typename ChildT>
2859 template<typename AccessorT>
2860 inline const typename ChildT::LeafNodeType*
2861 RootNode<ChildT>::probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
2862 {
2863  return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
2864 }
2865 
2866 
2867 template<typename ChildT>
2868 template<typename AccessorT>
2869 inline const typename ChildT::LeafNodeType*
2870 RootNode<ChildT>::probeLeafAndCache(const Coord& xyz, AccessorT& acc) const
2871 {
2872  return this->probeConstLeafAndCache(xyz, acc);
2873 }
2874 
2875 
2876 template<typename ChildT>
2877 template<typename NodeT, typename AccessorT>
2878 inline NodeT*
2879 RootNode<ChildT>::probeNodeAndCache(const Coord& xyz, AccessorT& acc)
2880 {
2881  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2882  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2884  MapIter iter = this->findCoord(xyz);
2885  if (iter == mTable.end() || isTile(iter)) return nullptr;
2886  ChildT* child = &getChild(iter);
2887  acc.insert(xyz, child);
2889  ? reinterpret_cast<NodeT*>(child)
2890  : child->template probeNodeAndCache<NodeT>(xyz, acc);
2892 }
2893 
2894 
2895 template<typename ChildT>
2896 template<typename NodeT,typename AccessorT>
2897 inline const NodeT*
2898 RootNode<ChildT>::probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const
2899 {
2900  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2901  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2903  MapCIter iter = this->findCoord(xyz);
2904  if (iter == mTable.end() || isTile(iter)) return nullptr;
2905  const ChildT* child = &getChild(iter);
2906  acc.insert(xyz, child);
2908  ? reinterpret_cast<const NodeT*>(child)
2909  : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
2911 }
2912 
2913 
2914 ////////////////////////////////////////
2915 
2916 template<typename ChildT>
2917 template<typename ArrayT>
2918 inline void
2920 {
2921  using NodePtr = typename ArrayT::value_type;
2922  static_assert(std::is_pointer<NodePtr>::value,
2923  "argument to getNodes() must be a pointer array");
2924  using NodeType = typename std::remove_pointer<NodePtr>::type;
2925  using NonConstNodeType = typename std::remove_const<NodeType>::type;
2926  static_assert(NodeChainType::template Contains<NonConstNodeType>,
2927  "can't extract non-const nodes from a const tree");
2928  using ArrayChildT = typename std::conditional<
2929  std::is_const<NodeType>::value, const ChildT, ChildT>::type;
2930 
2931  for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2932  if (ChildT* child = iter->second.child) {
2935  array.push_back(reinterpret_cast<NodePtr>(iter->second.child));
2936  } else {
2937  child->getNodes(array);//descent
2938  }
2940  }
2941  }
2942 }
2943 
2944 template<typename ChildT>
2945 template<typename ArrayT>
2946 inline void
2947 RootNode<ChildT>::getNodes(ArrayT& array) const
2948 {
2949  using NodePtr = typename ArrayT::value_type;
2950  static_assert(std::is_pointer<NodePtr>::value,
2951  "argument to getNodes() must be a pointer array");
2952  using NodeType = typename std::remove_pointer<NodePtr>::type;
2953  static_assert(std::is_const<NodeType>::value,
2954  "argument to getNodes() must be an array of const node pointers");
2955  using NonConstNodeType = typename std::remove_const<NodeType>::type;
2956  static_assert(NodeChainType::template Contains<NonConstNodeType>,
2957  "can't extract non-const nodes from a const tree");
2958 
2959  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2960  if (const ChildNodeType *child = iter->second.child) {
2963  array.push_back(reinterpret_cast<NodePtr>(iter->second.child));
2964  } else {
2965  child->getNodes(array);//descent
2966  }
2968  }
2969  }
2970 }
2971 
2972 ////////////////////////////////////////
2973 
2974 template<typename ChildT>
2975 template<typename ArrayT>
2976 inline void
2977 RootNode<ChildT>::stealNodes(ArrayT& array, const ValueType& value, bool state)
2978 {
2979  using NodePtr = typename ArrayT::value_type;
2980  static_assert(std::is_pointer<NodePtr>::value,
2981  "argument to stealNodes() must be a pointer array");
2982  using NodeType = typename std::remove_pointer<NodePtr>::type;
2983  using NonConstNodeType = typename std::remove_const<NodeType>::type;
2984  static_assert(NodeChainType::template Contains<NonConstNodeType>,
2985  "can't extract non-const nodes from a const tree");
2986  using ArrayChildT = typename std::conditional<
2987  std::is_const<NodeType>::value, const ChildT, ChildT>::type;
2988 
2989  for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2990  if (ChildT* child = iter->second.child) {
2993  array.push_back(reinterpret_cast<NodePtr>(&stealChild(iter, Tile(value, state))));
2994  } else {
2995  child->stealNodes(array, value, state);//descent
2996  }
2998  }
2999  }
3000 }
3001 
3002 
3003 ////////////////////////////////////////
3004 
3005 
3006 template<typename ChildT>
3007 template<MergePolicy Policy>
3008 inline void
3010 {
3012 
3013  switch (Policy) {
3014 
3015  default:
3016  case MERGE_ACTIVE_STATES:
3017  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3018  MapIter j = mTable.find(i->first);
3019  if (other.isChild(i)) {
3020  if (j == mTable.end()) { // insert other node's child
3021  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3022  child.resetBackground(other.mBackground, mBackground);
3023  mTable[i->first] = NodeStruct(child);
3024  } else if (isTile(j)) {
3025  if (isTileOff(j)) { // replace inactive tile with other node's child
3026  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3027  child.resetBackground(other.mBackground, mBackground);
3028  setChild(j, child);
3029  }
3030  } else { // merge both child nodes
3031  getChild(j).template merge<MERGE_ACTIVE_STATES>(getChild(i),
3032  other.mBackground, mBackground);
3033  }
3034  } else if (other.isTileOn(i)) {
3035  if (j == mTable.end()) { // insert other node's active tile
3036  mTable[i->first] = i->second;
3037  } else if (!isTileOn(j)) {
3038  // Replace anything except an active tile with the other node's active tile.
3039  setTile(j, Tile(other.getTile(i).value, true));
3040  }
3041  }
3042  }
3043  break;
3044 
3045  case MERGE_NODES:
3046  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3047  MapIter j = mTable.find(i->first);
3048  if (other.isChild(i)) {
3049  if (j == mTable.end()) { // insert other node's child
3050  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3051  child.resetBackground(other.mBackground, mBackground);
3052  mTable[i->first] = NodeStruct(child);
3053  } else if (isTile(j)) { // replace tile with other node's child
3054  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3055  child.resetBackground(other.mBackground, mBackground);
3056  setChild(j, child);
3057  } else { // merge both child nodes
3058  getChild(j).template merge<MERGE_NODES>(
3059  getChild(i), other.mBackground, mBackground);
3060  }
3061  }
3062  }
3063  break;
3064 
3066  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3067  MapIter j = mTable.find(i->first);
3068  if (other.isChild(i)) {
3069  if (j == mTable.end()) {
3070  // Steal and insert the other node's child.
3071  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3072  child.resetBackground(other.mBackground, mBackground);
3073  mTable[i->first] = NodeStruct(child);
3074  } else if (isTile(j)) {
3075  // Replace this node's tile with the other node's child.
3076  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3077  child.resetBackground(other.mBackground, mBackground);
3078  const Tile tile = getTile(j);
3079  setChild(j, child);
3080  if (tile.active) {
3081  // Merge the other node's child with this node's active tile.
3082  child.template merge<MERGE_ACTIVE_STATES_AND_NODES>(
3083  tile.value, tile.active);
3084  }
3085  } else /*if (isChild(j))*/ {
3086  // Merge the other node's child into this node's child.
3087  getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(getChild(i),
3088  other.mBackground, mBackground);
3089  }
3090  } else if (other.isTileOn(i)) {
3091  if (j == mTable.end()) {
3092  // Insert a copy of the other node's active tile.
3093  mTable[i->first] = i->second;
3094  } else if (isTileOff(j)) {
3095  // Replace this node's inactive tile with a copy of the other's active tile.
3096  setTile(j, Tile(other.getTile(i).value, true));
3097  } else if (isChild(j)) {
3098  // Merge the other node's active tile into this node's child.
3099  const Tile& tile = getTile(i);
3100  getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(
3101  tile.value, tile.active);
3102  }
3103  } // else if (other.isTileOff(i)) {} // ignore the other node's inactive tiles
3104  }
3105  break;
3106  }
3107 
3108  // Empty the other tree so as not to leave it in a partially cannibalized state.
3109  other.clear();
3110 
3112 }
3113 
3114 
3115 ////////////////////////////////////////
3116 
3117 
3118 template<typename ChildT>
3119 template<typename OtherChildType>
3120 inline void
3121 RootNode<ChildT>::topologyUnion(const RootNode<OtherChildType>& other, const bool preserveTiles)
3122 {
3123  using OtherRootT = RootNode<OtherChildType>;
3124  using OtherCIterT = typename OtherRootT::MapCIter;
3125 
3126  enforceSameConfiguration(other);
3127 
3128  for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3129  MapIter j = mTable.find(i->first);
3130  if (other.isChild(i)) {
3131  if (j == mTable.end()) { // create child branch with identical topology
3132  mTable[i->first] = NodeStruct(
3133  *(new ChildT(other.getChild(i), mBackground, TopologyCopy())));
3134  } else if (this->isChild(j)) { // union with child branch
3135  this->getChild(j).topologyUnion(other.getChild(i), preserveTiles);
3136  } else {// this is a tile so replace it with a child branch with identical topology
3137  if (!preserveTiles || this->isTileOff(j)) { // force child topology
3138  ChildT* child = new ChildT(
3139  other.getChild(i), this->getTile(j).value, TopologyCopy());
3140  if (this->isTileOn(j)) child->setValuesOn();//this is an active tile
3141  this->setChild(j, *child);
3142  }
3143  }
3144  } else if (other.isTileOn(i)) { // other is an active tile
3145  if (j == mTable.end()) { // insert an active tile
3146  mTable[i->first] = NodeStruct(Tile(mBackground, true));
3147  } else if (this->isChild(j)) {
3148  this->getChild(j).setValuesOn();
3149  } else if (this->isTileOff(j)) {
3150  this->setTile(j, Tile(this->getTile(j).value, true));
3151  }
3152  }
3153  }
3154 }
3155 
3156 template<typename ChildT>
3157 template<typename OtherChildType>
3158 inline void
3160 {
3161  using OtherRootT = RootNode<OtherChildType>;
3162  using OtherCIterT = typename OtherRootT::MapCIter;
3163 
3164  enforceSameConfiguration(other);
3165 
3166  std::set<Coord> tmp;//keys to erase
3167  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3168  OtherCIterT j = other.mTable.find(i->first);
3169  if (this->isChild(i)) {
3170  if (j == other.mTable.end() || other.isTileOff(j)) {
3171  tmp.insert(i->first);//delete child branch
3172  } else if (other.isChild(j)) { // intersect with child branch
3173  this->getChild(i).topologyIntersection(other.getChild(j), mBackground);
3174  }
3175  } else if (this->isTileOn(i)) {
3176  if (j == other.mTable.end() || other.isTileOff(j)) {
3177  this->setTile(i, Tile(this->getTile(i).value, false));//turn inactive
3178  } else if (other.isChild(j)) { //replace with a child branch with identical topology
3179  ChildT* child =
3180  new ChildT(other.getChild(j), this->getTile(i).value, TopologyCopy());
3181  this->setChild(i, *child);
3182  }
3183  }
3184  }
3185  for (std::set<Coord>::iterator i = tmp.begin(), e = tmp.end(); i != e; ++i) {
3186  MapIter it = this->findCoord(*i);
3187  setTile(it, Tile()); // delete any existing child node first
3188  mTable.erase(it);
3189  }
3190 }
3191 
3192 template<typename ChildT>
3193 template<typename OtherChildType>
3194 inline void
3196 {
3197  using OtherRootT = RootNode<OtherChildType>;
3198  using OtherCIterT = typename OtherRootT::MapCIter;
3199 
3200  enforceSameConfiguration(other);
3201 
3202  for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3203  MapIter j = mTable.find(i->first);
3204  if (other.isChild(i)) {
3205  if (j == mTable.end() || this->isTileOff(j)) {
3206  //do nothing
3207  } else if (this->isChild(j)) { // difference with child branch
3208  this->getChild(j).topologyDifference(other.getChild(i), mBackground);
3209  } else if (this->isTileOn(j)) {
3210  // this is an active tile so create a child node and descent
3211  ChildT* child = new ChildT(j->first, this->getTile(j).value, true);
3212  child->topologyDifference(other.getChild(i), mBackground);
3213  this->setChild(j, *child);
3214  }
3215  } else if (other.isTileOn(i)) { // other is an active tile
3216  if (j == mTable.end() || this->isTileOff(j)) {
3217  // do nothing
3218  } else if (this->isChild(j)) {
3219  setTile(j, Tile()); // delete any existing child node first
3220  mTable.erase(j);
3221  } else if (this->isTileOn(j)) {
3222  this->setTile(j, Tile(this->getTile(j).value, false));
3223  }
3224  }
3225  }
3226 }
3227 
3228 ////////////////////////////////////////
3229 
3230 
3231 template<typename ChildT>
3232 template<typename CombineOp>
3233 inline void
3234 RootNode<ChildT>::combine(RootNode& other, CombineOp& op, bool prune)
3235 {
3237 
3238  CoordSet keys;
3239  this->insertKeys(keys);
3240  other.insertKeys(keys);
3241 
3242  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3243  MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
3244  if (isTile(iter) && isTile(otherIter)) {
3245  // Both this node and the other node have constant values (tiles).
3246  // Combine the two values and store the result as this node's new tile value.
3247  op(args.setARef(getTile(iter).value)
3248  .setAIsActive(isTileOn(iter))
3249  .setBRef(getTile(otherIter).value)
3250  .setBIsActive(isTileOn(otherIter)));
3251  setTile(iter, Tile(args.result(), args.resultIsActive()));
3252 
3253  } else if (isChild(iter) && isTile(otherIter)) {
3254  // Combine this node's child with the other node's constant value.
3255  ChildT& child = getChild(iter);
3256  child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
3257 
3258  } else if (isTile(iter) && isChild(otherIter)) {
3259  // Combine this node's constant value with the other node's child,
3260  // but use a new functor in which the A and B values are swapped,
3261  // since the constant value is the A value, not the B value.
3263  ChildT& child = getChild(otherIter);
3264  child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
3265 
3266  // Steal the other node's child.
3267  setChild(iter, stealChild(otherIter, Tile()));
3268 
3269  } else /*if (isChild(iter) && isChild(otherIter))*/ {
3270  // Combine this node's child with the other node's child.
3271  ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
3272  child.combine(otherChild, op);
3273  }
3274  if (prune && isChild(iter)) getChild(iter).prune();
3275  }
3276 
3277  // Combine background values.
3278  op(args.setARef(mBackground).setBRef(other.mBackground));
3279  mBackground = args.result();
3280 
3281  // Empty the other tree so as not to leave it in a partially cannibalized state.
3282  other.clear();
3283 }
3284 
3285 
3286 ////////////////////////////////////////
3287 
3288 
3289 // This helper class is a friend of RootNode and is needed so that combine2
3290 // can be specialized for compatible and incompatible pairs of RootNode types.
3291 template<typename CombineOp, typename RootT, typename OtherRootT, bool Compatible = false>
3292 struct RootNodeCombineHelper
3293 {
3294  static inline void combine2(RootT& self, const RootT&, const OtherRootT& other1,
3295  CombineOp&, bool)
3296  {
3297  // If the two root nodes have different configurations or incompatible ValueTypes,
3298  // throw an exception.
3299  self.enforceSameConfiguration(other1);
3300  self.enforceCompatibleValueTypes(other1);
3301  // One of the above two tests should throw, so we should never get here:
3302  std::ostringstream ostr;
3303  ostr << "cannot combine a " << typeid(OtherRootT).name()
3304  << " into a " << typeid(RootT).name();
3305  OPENVDB_THROW(TypeError, ostr.str());
3306  }
3307 };
3308 
3309 // Specialization for root nodes of compatible types
3310 template<typename CombineOp, typename RootT, typename OtherRootT>
3311 struct RootNodeCombineHelper<CombineOp, RootT, OtherRootT, /*Compatible=*/true>
3312 {
3313  static inline void combine2(RootT& self, const RootT& other0, const OtherRootT& other1,
3314  CombineOp& op, bool prune)
3315  {
3316  self.doCombine2(other0, other1, op, prune);
3317  }
3318 };
3319 
3320 
3321 template<typename ChildT>
3322 template<typename CombineOp, typename OtherRootNode>
3323 inline void
3324 RootNode<ChildT>::combine2(const RootNode& other0, const OtherRootNode& other1,
3325  CombineOp& op, bool prune)
3326 {
3327  using OtherValueType = typename OtherRootNode::ValueType;
3328  static const bool compatible = (SameConfiguration<OtherRootNode>::value
3329  && CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value);
3331  *this, other0, other1, op, prune);
3332 }
3333 
3334 
3335 template<typename ChildT>
3336 template<typename CombineOp, typename OtherRootNode>
3337 inline void
3338 RootNode<ChildT>::doCombine2(const RootNode& other0, const OtherRootNode& other1,
3339  CombineOp& op, bool prune)
3340 {
3341  enforceSameConfiguration(other1);
3342 
3343  using OtherValueT = typename OtherRootNode::ValueType;
3344  using OtherTileT = typename OtherRootNode::Tile;
3345  using OtherNodeStructT = typename OtherRootNode::NodeStruct;
3346  using OtherMapCIterT = typename OtherRootNode::MapCIter;
3347 
3349 
3350  CoordSet keys;
3351  other0.insertKeys(keys);
3352  other1.insertKeys(keys);
3353 
3354  const NodeStruct bg0(Tile(other0.mBackground, /*active=*/false));
3355  const OtherNodeStructT bg1(OtherTileT(other1.mBackground, /*active=*/false));
3356 
3357  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3358  MapIter thisIter = this->findOrAddCoord(*i);
3359  MapCIter iter0 = other0.findKey(*i);
3360  OtherMapCIterT iter1 = other1.findKey(*i);
3361  const NodeStruct& ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0;
3362  const OtherNodeStructT& ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
3363  if (ns0.isTile() && ns1.isTile()) {
3364  // Both input nodes have constant values (tiles).
3365  // Combine the two values and add a new tile to this node with the result.
3366  op(args.setARef(ns0.tile.value)
3367  .setAIsActive(ns0.isTileOn())
3368  .setBRef(ns1.tile.value)
3369  .setBIsActive(ns1.isTileOn()));
3370  setTile(thisIter, Tile(args.result(), args.resultIsActive()));
3371  } else {
3372  if (!isChild(thisIter)) {
3373  // Add a new child with the same coordinates, etc. as the other node's child.
3374  const Coord& childOrigin =
3375  ns0.isChild() ? ns0.child->origin() : ns1.child->origin();
3376  setChild(thisIter, *(new ChildT(childOrigin, getTile(thisIter).value)));
3377  }
3378  ChildT& child = getChild(thisIter);
3379 
3380  if (ns0.isTile()) {
3381  // Combine node1's child with node0's constant value
3382  // and write the result into this node's child.
3383  child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
3384  } else if (ns1.isTile()) {
3385  // Combine node0's child with node1's constant value
3386  // and write the result into this node's child.
3387  child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
3388  } else {
3389  // Combine node0's child with node1's child
3390  // and write the result into this node's child.
3391  child.combine2(*ns0.child, *ns1.child, op);
3392  }
3393  }
3394  if (prune && isChild(thisIter)) getChild(thisIter).prune();
3395  }
3396 
3397  // Combine background values.
3398  op(args.setARef(other0.mBackground).setBRef(other1.mBackground));
3399  mBackground = args.result();
3400 }
3401 
3402 
3403 } // namespace tree
3404 } // namespace OPENVDB_VERSION_NAME
3405 } // namespace openvdb
3406 
3407 #endif // OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
const AValueType & result() const
Get the output value.
Definition: Types.h:613
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:504
typedef int(APIENTRYP RE_PFNGLXSWAPINTERVALSGIPROC)(int)
static void combine2(RootT &self, const RootT &other0, const OtherRootT &other1, CombineOp &op, bool prune)
Definition: RootNode.h:3313
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1859
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition: RootNode.h:1144
cvex test(vector P=0;int unbound=3;export float s=0;export vector Cf=0;)
Definition: test.vfl:11
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:568
bool addChild(ChildType *child)
Add the given child node at the root level. If a child node with the same origin already exists...
LeafNodeType * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one that preserves the values and active states of all voxels.
Definition: RootNode.h:2756
Coord getMaxIndex() const
Return the largest index of the current tree.
Definition: RootNode.h:1361
bool empty() const
Return true if this node's table is either empty or contains only background tiles.
Definition: RootNode.h:446
Signed (i, j, k) 32-bit integer coordinate class, similar to openvdb::math::Coord.
Definition: NanoVDB.h:1282
LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as probeLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
void topologyIntersection(const RootNode< OtherChildType > &other)
Intersects this tree's set of active values with the active values of the other tree, whose ValueType may be different.
Definition: RootNode.h:3159
ValueIter< const RootNode, MapCIter, ChildOffPred, ValueType > ChildOffCIter
Definition: RootNode.h:363
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition: Math.h:443
void setBackground(const ValueType &value, bool updateChildNodes)
Change inactive tiles or voxels with a value equal to +/- the old background to the specified value (...
Definition: RootNode.h:1231
int getValueDepthAndCache(const Coord &xyz, AccessorT &) const
Definition: RootNode.h:1763
RootNode & operator=(const RootNode &other)
Copy a root node of the same type as this node.
Definition: RootNode.h:1189
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:128
void skip(T &in, int n)
Definition: ImfXdr.h:613
const GLdouble * v
Definition: glcorearb.h:837
bool probeValue(const Coord &xyz, ValueType &value) const
Definition: RootNode.h:2092
DenseIter< RootNode, MapIter, ChildType, ValueType > ChildAllIter
Definition: RootNode.h:364
void getIndexRange(CoordBBox &bbox) const
Return the current index range. Both min and max are inclusive.
Definition: RootNode.h:1369
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
GLsizei const GLfloat * value
Definition: glcorearb.h:824
bool hasSameTopology(const RootNode< OtherChildType > &other) const
Return true if the given tree has the same node and active value topology as this tree (but possibly ...
Definition: RootNode.h:1382
GLdouble GLdouble GLdouble z
Definition: glcorearb.h:848
const ValueType & background() const
Return this node's background value.
Definition: RootNode.h:428
GLint level
Definition: glcorearb.h:108
ValueConverter<T>::Type is the type of a RootNode having the same child hierarchy as this node but a ...
Definition: RootNode.h:56
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:239
void merge(RootNode &other)
Efficiently merge another tree into this tree using one of several schemes.
Definition: RootNode.h:3009
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition: RootNode.h:1488
bool isBackgroundTile(const Tile &) const
Return true if the given tile is inactive and has the background value.
Definition: RootNode.h:1258
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1943
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: RootNode.h:2061
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: RootNode.h:2034
**But if you need a or simply need to know when the task has note that the like this
Definition: thread.h:617
const NodeT * probeConstNodeAndCache(const Coord &xyz, AccessorT &acc) const
Same as probeNode() but, if necessary, update the given accessor with pointers to the nodes along the...
Definition: RootNode.h:2898
GLint y
Definition: glcorearb.h:103
Index32 transientData() const
Return the transient data value.
Definition: RootNode.h:409
**But if you need a result
Definition: thread.h:613
__hostdev__ void setValue(uint32_t offset, bool v)
Definition: NanoVDB.h:5750
void stealNodes(ArrayT &array)
Steals all nodes of a certain type from the tree and adds them to a container with the following API:...
Definition: RootNode.h:816
void prune(const ValueType &tolerance=zeroVal< ValueType >())
Reduce the memory footprint of this tree by replacing with tiles any nodes whose values are all the s...
Definition: RootNode.h:2532
void combine(RootNode &other, CombineOp &, bool prune=false)
Definition: RootNode.h:3234
typename NodeChain< RootNode, LEVEL >::Type NodeChainType
NodeChainType is a list of this tree's node types, from LeafNodeType to RootNode. ...
Definition: RootNode.h:49
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition: RootNode.h:2108
uint64 value_type
Definition: GA_PrimCompat.h:29
Tag dispatch class that distinguishes constructors during file input.
Definition: Types.h:689
typename NodeChain< typename HeadT::ChildNodeType, HeadLevel-1 >::Type SubtreeT
Definition: RootNode.h:998
#define OPENVDB_ABI_VERSION_NUMBER
The ABI version that OpenVDB was built with.
Definition: version.h:74
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
Definition: NodeMasks.h:159
SameConfiguration<OtherNodeType>::value is true if and only if OtherNodeType is the type of a RootNode ...
Definition: RootNode.h:64
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2835
ValueIter< RootNode, MapIter, ValueAllPred, ValueType > ValueAllIter
Definition: RootNode.h:371
static void getNodeLog2Dims(std::vector< Index > &dims)
Definition: RootNode.h:1345
void setTransientData(Index32 transientData)
Set the transient data value.
Definition: RootNode.h:411
static bool hasSameConfiguration(const RootNode< OtherChildType > &other)
Return false if the other node's dimensions don't match this node's.
Definition: RootNode.h:1429
bool isValueOn(const Coord &xyz) const
Definition: RootNode.h:1697
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
typename ChildType::ValueType ValueType
Definition: RootNode.h:43
constexpr T zeroVal()
Return the value of type T that corresponds to zero.
Definition: Math.h:70
typename SubtreeT::template Append< HeadT > Type
Definition: RootNode.h:999
GLdouble n
Definition: glcorearb.h:2008
void setActiveState(const Coord &xyz, bool on)
Set the active state of the voxel at the given coordinates but don't change its value.
Definition: RootNode.h:1789
Index getTableSize() const
Return the number of entries in this node's table.
Definition: RootNode.h:458
GLintptr offset
Definition: glcorearb.h:665
static bool hasCompatibleValueType(const RootNode< OtherChildType > &other)
Definition: RootNode.h:1461
ImageBuf OIIO_API sub(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
bool isApproxEqual(const Type &a, const Type &b, const Type &tolerance)
Return true if a is equal to b to within the given tolerance.
Definition: Math.h:406
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as touchLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
ValueIter< const RootNode, MapCIter, ValueOnPred, const ValueType > ValueOnCIter
Definition: RootNode.h:368
T truncateRealToHalf(const T &val)
Return the given value truncated to 16-bit float precision.
Definition: Compression.h:216
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates but don't change its active state.
Definition: RootNode.h:1924
typename ChildType::BuildType BuildType
Definition: RootNode.h:44
BBox< Coord > CoordBBox
Definition: NanoVDB.h:2516
RootNode()
Construct a new tree with a background value of 0.
Definition: RootNode.h:1032
typename ChildType::LeafNodeType LeafNodeType
Definition: RootNode.h:42
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
static void combine2(RootT &self, const RootT &, const OtherRootT &other1, CombineOp &, bool)
Definition: RootNode.h:3294
__hostdev__ void setOrigin(const T &ijk)
Definition: NanoVDB.h:5762
bool hasActiveTiles() const
Return true if this root node, or any of its child nodes, have active tiles.
Definition: RootNode.h:1706
const ValueType & getValue(const Coord &xyz) const
Definition: RootNode.h:1729
ValueIter< const RootNode, MapCIter, ValueOffPred, const ValueType > ValueOffCIter
Definition: RootNode.h:370
NodeT * stealNode(const Coord &xyz, const ValueType &value, bool state)
Return a pointer to the node of type NodeT that contains voxel (x, y, z) and replace it with a tile o...
Definition: RootNode.h:2553
void combine2(const RootNode &other0, const OtherRootNode &other1, CombineOp &op, bool prune=false)
Definition: RootNode.h:3324
IMATH_HOSTDEVICE constexpr Color4< T > operator*(S a, const Color4< T > &v) IMATH_NOEXCEPT
Reverse multiplication: S * Color4.
Definition: ImathColor.h:732
LeafFnBase< CoordT, MaskT, LOG2DIM > BaseT
Definition: NanoVDB.h:5564
const LeafNodeType * probeConstLeafAndCache(const Coord &xyz, AccessorT &acc) const
Same as probeLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
void topologyDifference(const RootNode< OtherChildType > &other)
Difference this tree's set of active values with the active values of the other tree, whose ValueType may be different. So a resulting voxel will be active only if the original voxel is active in this tree and inactive in the other tree.
Definition: RootNode.h:3195
bool expand(const Coord &xyz)
Expand this node's table so that (x, y, z) is included in the index range.
Definition: RootNode.h:1331
void addLeaf(LeafNodeType *leaf)
Add the given leaf node to this tree, creating a new branch if necessary. If a leaf node with the sam...
Definition: RootNode.h:2572
void addTile(const Coord &xyz, const ValueType &value, bool state)
Add a tile containing voxel (x, y, z) at the root level, deleting the existing branch if necessary...
Definition: RootNode.h:2668
GLuint const GLchar * name
Definition: glcorearb.h:786
void stealNodes(ArrayT &array, const ValueType &value, bool state)
Steals all nodes of a certain type from the tree and adds them to a container with the following API:...
Definition: RootNode.h:2977
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition: RootNode.h:1812
DenseIter< const RootNode, MapCIter, const ChildType, const ValueType > ChildAllCIter
Definition: RootNode.h:365
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
Coord getMinIndex() const
Return the smallest index of the current tree.
Definition: RootNode.h:1354
GLint GLenum GLint x
Definition: glcorearb.h:409
bool writeTopology(std::ostream &, bool toHalf=false) const
Definition: RootNode.h:2306
GLenum GLenum GLsizei void * table
Definition: glad.h:5129
that also have some descendant prim *whose name begins with which in turn has a child named baz where *the predicate active
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition: Platform.h:140
GLdouble t
Definition: glad.h:2397
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition: RootNode.h:1775
ChildIter< RootNode, MapIter, ChildOnPred, ChildType > ChildOnIter
Definition: RootNode.h:360
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition: RootNode.h:1126
void denseFill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value and ensure that those voxels are a...
Definition: RootNode.h:2186
void readBuffers(std::istream &, bool fromHalf=false)
Definition: RootNode.h:2458
CanConvertType<FromType, ToType>::value is true if a value of type ToType can be constructed from a v...
Definition: Types.h:403
GLint j
Definition: glad.h:2733
OPENVDB_API void setGridBackgroundValuePtr(std::ios_base &, const void *background)
Specify (a pointer to) the background value of the grid currently being read from or written to the g...
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition: RootNode.h:2448
Library and file format version numbers.
RootNode(const RootNode< OtherChildType > &other)
Construct a new tree that reproduces the topology and active states of a tree of a different ValueTyp...
Definition: RootNode.h:84
size_t eraseBackgroundTiles()
Remove all background tiles.
Definition: RootNode.h:1292
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1902
size_t numBackgroundTiles() const
Return the number of background tiles.
Definition: RootNode.h:1280
const NodeT * probeConstNode(const Coord &xyz) const
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2818
void sparseFill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition: RootNode.h:537
GLuint GLfloat * val
Definition: glcorearb.h:1608
GA_API const UT_StringHolder N
ValueIter< RootNode, MapIter, ChildOffPred, const ValueType > ChildOffIter
Definition: RootNode.h:362
if(num_boxed_items<=0)
Definition: UT_RTreeImpl.h:697
void copyToDense(const CoordBBox &bbox, DenseT &dense) const
Copy into a dense grid the values of all voxels, both active and inactive, that intersect a given bou...
Definition: RootNode.h:2262
const LeafNodeType * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2843
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: RootNode.h:1966
**If you just want to fire and args
Definition: thread.h:609
ValueIter< RootNode, MapIter, ValueOnPred, ValueType > ValueOnIter
Definition: RootNode.h:367
CombineArgs & setARef(const AValueType &a)
Redirect the A value to a new external source.
Definition: Types.h:621
void modifyValueAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: RootNode.h:1998
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:141
bool readTopology(std::istream &, bool fromHalf=false)
Definition: RootNode.h:2342
Definition: core.h:1131
NodeT * probeNodeAndCache(const Coord &xyz, AccessorT &acc)
Same as probeNode() but, if necessary, update the given accessor with pointers to the nodes along the...
Definition: RootNode.h:2879
Fp4 BuildType
Definition: NanoVDB.h:5565
void voxelizeActiveTiles(bool threaded=true)
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition: RootNode.h:2236
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:683
bool operator!=(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:165
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:335
void topologyUnion(const RootNode< OtherChildType > &other, const bool preserveTiles=false)
Union this tree's set of active values with the active values of the other tree, whose ValueType may ...
Definition: RootNode.h:3121
SIM_API const UT_StringHolder distance
type
Definition: core.h:1059
ChildIter< const RootNode, MapCIter, ChildOnPred, const ChildType > ChildOnCIter
Definition: RootNode.h:361
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: RootNode.h:1883
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER IMATH_HOSTDEVICE IMATH_CONSTEXPR14 T clip(const T &p, const Box< T > &box) IMATH_NOEXCEPT
Definition: ImathBoxAlgo.h:29
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:119
bool ValueType
Definition: NanoVDB.h:5729
OPENVDB_API uint32_t getFormatVersion(std::ios_base &)
Return the file format version number associated with the given input stream.
A list of types (not necessarily unique)
Definition: TypeList.h:577
void evalActiveBoundingBox(CoordBBox &bbox, bool visitVoxels=true) const
Expand the specified bbox so it includes the active tiles of this root node as well as all the active...
Definition: RootNode.h:1513
static CoordBBox getNodeBoundingBox()
Return the bounding box of this RootNode, i.e., an infinite bounding box.
Definition: RootNode.h:406
int getValueDepth(const Coord &xyz) const
Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
Definition: RootNode.h:1753
void nodeCount(std::vector< Index32 > &vec) const
Definition: RootNode.h:1678
ValueIter< RootNode, MapIter, ValueOffPred, ValueType > ValueOffIter
Definition: RootNode.h:369
void addTileAndCache(Index level, const Coord &xyz, const ValueType &, bool state, AccessorT &)
Same as addTile() but, if necessary, update the given accessor with pointers to the nodes along the p...
Definition: RootNode.h:2715
GLint GLsizei count
Definition: glcorearb.h:405
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
void addLeafAndCache(LeafNodeType *leaf, AccessorT &)
Same as addLeaf() but, if necessary, update the given accessor with pointers to the nodes along the p...
Definition: RootNode.h:2607
void fill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition: RootNode.h:2128
ValueIter< const RootNode, MapCIter, ValueAllPred, const ValueType > ValueAllCIter
Definition: RootNode.h:372
NodeChain<RootNodeType, RootNodeType::LEVEL>::Type is a openvdb::TypeList that lists the types of the...
Definition: RootNode.h:31
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition: RootNode.h:1717
void getNodes(ArrayT &array)
Adds all nodes of a certain type to a container with the following API:
Definition: RootNode.h:2919
void clip(const CoordBBox &)
Set all voxels that lie outside the given axis-aligned box to the background.
Definition: RootNode.h:2492
shared_ptr< Node > NodePtr
A shared pointer to a Node.
Definition: Node.h:24
NodeT * probeNode(const Coord &xyz)
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2800