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