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