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