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