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