OpenVDB  7.0.0
InternalNode.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
7 
8 #ifndef OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
9 #define OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
10 
11 #include <openvdb/Platform.h>
12 #include <openvdb/util/NodeMasks.h>
13 #include <openvdb/io/Compression.h> // for io::readCompressedValues(), etc.
14 #include <openvdb/math/Math.h> // for math::isExactlyEqual(), etc.
15 #include <openvdb/version.h>
16 #include <openvdb/Types.h>
17 #include "Iterator.h"
18 #include "NodeUnion.h"
19 #include <tbb/parallel_for.h>
20 #include <memory>
21 #include <type_traits>
22 
23 
24 namespace openvdb {
26 namespace OPENVDB_VERSION_NAME {
27 namespace tree {
28 
29 template<typename, Index, typename> struct SameInternalConfig; // forward declaration
30 
31 
32 template<typename _ChildNodeType, Index Log2Dim>
34 {
35 public:
36  using ChildNodeType = _ChildNodeType;
37  using LeafNodeType = typename ChildNodeType::LeafNodeType;
38  using ValueType = typename ChildNodeType::ValueType;
39  using BuildType = typename ChildNodeType::BuildType;
42 
43  static const Index
44  LOG2DIM = Log2Dim, // log2 of tile count in one dimension
45  TOTAL = Log2Dim + ChildNodeType::TOTAL, // log2 of voxel count in one dimension
46  DIM = 1 << TOTAL, // total voxel count in one dimension
47  NUM_VALUES = 1 << (3 * Log2Dim), // total voxel count represented by this node
48  LEVEL = 1 + ChildNodeType::LEVEL; // level 0 = leaf
49  static const Index64
50  NUM_VOXELS = uint64_t(1) << (3 * TOTAL); // total voxel count represented by this node
51 
54  template<typename OtherValueType>
55  struct ValueConverter {
56  using Type = InternalNode<typename ChildNodeType::template ValueConverter<
57  OtherValueType>::Type, Log2Dim>;
58  };
59 
63  template<typename OtherNodeType>
65  static const bool value =
67  };
68 
69 
73 
76  explicit InternalNode(const ValueType& offValue);
77 
82  InternalNode(const Coord& origin, const ValueType& fillValue, bool active = false);
83 
84  InternalNode(PartialCreate, const Coord&, const ValueType& fillValue, bool active = false);
85 
89  InternalNode(const InternalNode&);
90 
94  template<typename OtherChildNodeType>
96 
100  template<typename OtherChildNodeType>
102  const ValueType& background, TopologyCopy);
103 
107  template<typename OtherChildNodeType>
109  const ValueType& offValue, const ValueType& onValue, TopologyCopy);
110 
111 #if OPENVDB_ABI_VERSION_NUMBER < 5
112  virtual ~InternalNode();
113 #else
114  ~InternalNode();
115 #endif
116 
117 protected:
121 
122  // Type tags to disambiguate template instantiations
123  struct ValueOn {}; struct ValueOff {}; struct ValueAll {};
124  struct ChildOn {}; struct ChildOff {}; struct ChildAll {};
125 
126  // The following class templates implement the iterator interfaces specified in Iterator.h
127  // by providing getItem(), setItem() and/or modifyItem() methods.
128 
129  // Sparse iterator that visits child nodes of an InternalNode
130  template<typename NodeT, typename ChildT, typename MaskIterT, typename TagT>
132  MaskIterT, ChildIter<NodeT, ChildT, MaskIterT, TagT>, NodeT, ChildT>
133  {
135  ChildIter(const MaskIterT& iter, NodeT* parent): SparseIteratorBase<
136  MaskIterT, ChildIter<NodeT, ChildT, MaskIterT, TagT>, NodeT, ChildT>(iter, parent) {}
137 
138  ChildT& getItem(Index pos) const
139  {
140  assert(this->parent().isChildMaskOn(pos));
141  return *(this->parent().getChildNode(pos));
142  }
143 
144  // Note: setItem() can't be called on const iterators.
145  void setItem(Index pos, const ChildT& c) const { this->parent().resetChildNode(pos, &c); }
146 
147  // Note: modifyItem() isn't implemented, since it's not useful for child node pointers.
148  };// ChildIter
149 
150  // Sparse iterator that visits tile values of an InternalNode
151  template<typename NodeT, typename ValueT, typename MaskIterT, typename TagT>
153  MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>
154  {
156  ValueIter(const MaskIterT& iter, NodeT* parent): SparseIteratorBase<
157  MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>(iter, parent) {}
158 
159  const ValueT& getItem(Index pos) const { return this->parent().mNodes[pos].getValue(); }
160 
161  // Note: setItem() can't be called on const iterators.
162  void setItem(Index pos, const ValueT& v) const { this->parent().mNodes[pos].setValue(v); }
163 
164  // Note: modifyItem() can't be called on const iterators.
165  template<typename ModifyOp>
166  void modifyItem(Index pos, const ModifyOp& op) const
167  {
168  op(this->parent().mNodes[pos].getValue());
169  }
170  };// ValueIter
171 
172  // Dense iterator that visits both tiles and child nodes of an InternalNode
173  template<typename NodeT, typename ChildT, typename ValueT, typename TagT>
174  struct DenseIter: public DenseIteratorBase<
175  MaskDenseIterator, DenseIter<NodeT, ChildT, ValueT, TagT>, NodeT, ChildT, ValueT>
176  {
179 
181  DenseIter(const MaskDenseIterator& iter, NodeT* parent):
182  DenseIteratorBase<MaskDenseIterator, DenseIter, NodeT, ChildT, ValueT>(iter, parent) {}
183 
184  bool getItem(Index pos, ChildT*& child, NonConstValueT& value) const
185  {
186  if (this->parent().isChildMaskOn(pos)) {
187  child = this->parent().getChildNode(pos);
188  return true;
189  }
190  child = nullptr;
191  value = this->parent().mNodes[pos].getValue();
192  return false;
193  }
194 
195  // Note: setItem() can't be called on const iterators.
196  void setItem(Index pos, ChildT* child) const
197  {
198  this->parent().resetChildNode(pos, child);
199  }
200 
201  // Note: unsetItem() can't be called on const iterators.
202  void unsetItem(Index pos, const ValueT& value) const
203  {
204  this->parent().unsetChildNode(pos, value);
205  }
206  };// DenseIter
207 
208 public:
209  // Iterators (see Iterator.h for usage)
216 
223 
224  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(mChildMask.beginOn(), this); }
225  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(mChildMask.beginOff(), this); }
226  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(mChildMask.beginDense(), this); }
227  ChildOnCIter beginChildOn() const { return cbeginChildOn(); }
228  ChildOffCIter beginChildOff() const { return cbeginChildOff(); }
229  ChildAllCIter beginChildAll() const { return cbeginChildAll(); }
230  ChildOnIter beginChildOn() { return ChildOnIter(mChildMask.beginOn(), this); }
231  ChildOffIter beginChildOff() { return ChildOffIter(mChildMask.beginOff(), this); }
232  ChildAllIter beginChildAll() { return ChildAllIter(mChildMask.beginDense(), this); }
233 
234  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(mValueMask.beginOn(), this); }
236  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(mValueMask.beginOff(), this); }
237  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(mChildMask.beginOff(), this); }
238  ValueOnCIter beginValueOn() const { return cbeginValueOn(); }
240  ValueOffCIter beginValueOff() const { return cbeginValueOff(); }
241  ValueAllCIter beginValueAll() const { return cbeginValueAll(); }
242  ValueOnIter beginValueOn() { return ValueOnIter(mValueMask.beginOn(), this); }
244  ValueOffIter beginValueOff() { return ValueOffIter(mValueMask.beginOff(), this); }
245  ValueAllIter beginValueAll() { return ValueAllIter(mChildMask.beginOff(), this); }
246 
247 
250  static Index dim() { return DIM; }
253  static Index getLevel() { return LEVEL; }
256  static void getNodeLog2Dims(std::vector<Index>& dims);
260  static Index getChildDim() { return ChildNodeType::DIM; }
261 
263  static Index coordToOffset(const Coord& xyz);
266  static void offsetToLocalCoord(Index n, Coord& xyz);
268  Coord offsetToGlobalCoord(Index n) const;
269 
271  const Coord& origin() const { return mOrigin; }
273  void setOrigin(const Coord& origin) { mOrigin = origin; }
274 
275  Index32 leafCount() const;
276  void nodeCount(std::vector<Index32> &vec) const;
277  Index32 nonLeafCount() const;
278  Index64 onVoxelCount() const;
279  Index64 offVoxelCount() const;
280  Index64 onLeafVoxelCount() const;
281  Index64 offLeafVoxelCount() const;
282  Index64 onTileCount() const;
283 
285  Index64 memUsage() const;
286 
291  void evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels = true) const;
292 
295  CoordBBox getNodeBoundingBox() const { return CoordBBox::createCube(mOrigin, DIM); }
296 
298  bool isEmpty() const { return mChildMask.isOff(); }
299 
305  bool isConstant(ValueType& firstValue, bool& state,
306  const ValueType& tolerance = zeroVal<ValueType>()) const;
307 
322  bool isConstant(ValueType& minValue, ValueType& maxValue,
323  bool& state, const ValueType& tolerance = zeroVal<ValueType>()) const;
324 
326  bool isInactive() const { return this->isChildMaskOff() && this->isValueMaskOff(); }
327 
329  bool isValueOn(const Coord& xyz) const;
331  bool isValueOn(Index offset) const { return mValueMask.isOn(offset); }
332 
334  bool hasActiveTiles() const;
335 
336  const ValueType& getValue(const Coord& xyz) const;
337  bool probeValue(const Coord& xyz, ValueType& value) const;
338 
341  Index getValueLevel(const Coord& xyz) const;
342 
345  const ValueType& getFirstValue() const;
348  const ValueType& getLastValue() const;
349 
351  void setActiveState(const Coord& xyz, bool on);
353  void setValueOnly(const Coord& xyz, const ValueType& value);
355  void setValueOn(const Coord& xyz);
357  void setValueOn(const Coord& xyz, const ValueType& value);
359  void setValueOff(const Coord& xyz);
361  void setValueOff(const Coord& xyz, const ValueType& value);
362 
365  template<typename ModifyOp>
366  void modifyValue(const Coord& xyz, const ModifyOp& op);
368  template<typename ModifyOp>
369  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
370 
375  template<typename AccessorT>
376  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
377 
382  template<typename AccessorT>
383  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
384 
389  template<typename AccessorT>
390  void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
391 
396  template<typename AccessorT>
397  void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
398 
404  template<typename ModifyOp, typename AccessorT>
405  void modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
406 
411  template<typename ModifyOp, typename AccessorT>
412  void modifyValueAndActiveStateAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
413 
418  template<typename AccessorT>
419  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
420 
425  template<typename AccessorT>
426  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
427 
433  template<typename AccessorT>
434  bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
435 
442  template<typename AccessorT>
443  Index getValueLevelAndCache(const Coord& xyz, AccessorT&) const;
444 
446  void setValuesOn();
447 
448  //
449  // I/O
450  //
451  void writeTopology(std::ostream&, bool toHalf = false) const;
452  void readTopology(std::istream&, bool fromHalf = false);
453  void writeBuffers(std::ostream&, bool toHalf = false) const;
454  void readBuffers(std::istream&, bool fromHalf = false);
455  void readBuffers(std::istream&, const CoordBBox&, bool fromHalf = false);
456 
457 
458  //
459  // Aux methods
460  //
461 
463  void negate();
464 
473  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
474 
482  void denseFill(const CoordBBox& bbox, const ValueType& value, bool active = true);
483 
487  void voxelizeActiveTiles(bool threaded = true);
488 
496  template<typename DenseT>
497  void copyToDense(const CoordBBox& bbox, DenseT& dense) const;
498 
501  template<MergePolicy Policy>
502  void merge(InternalNode& other, const ValueType& background, const ValueType& otherBackground);
503 
506  template<MergePolicy Policy> void merge(const ValueType& tileValue, bool tileActive);
507 
520  template<typename OtherChildNodeType>
521  void topologyUnion(const InternalNode<OtherChildNodeType, Log2Dim>& other);
522 
536  template<typename OtherChildNodeType>
537  void topologyIntersection(const InternalNode<OtherChildNodeType, Log2Dim>& other,
538  const ValueType& background);
539 
551  template<typename OtherChildNodeType>
552  void topologyDifference(const InternalNode<OtherChildNodeType, Log2Dim>& other,
553  const ValueType& background);
554 
555  template<typename CombineOp>
556  void combine(InternalNode& other, CombineOp&);
557  template<typename CombineOp>
558  void combine(const ValueType& value, bool valueIsActive, CombineOp&);
559 
560  template<typename CombineOp, typename OtherNodeType /*= InternalNode*/>
561  void combine2(const InternalNode& other0, const OtherNodeType& other1, CombineOp&);
562  template<typename CombineOp, typename OtherNodeType /*= InternalNode*/>
563  void combine2(const ValueType& value, const OtherNodeType& other, bool valIsActive, CombineOp&);
564  template<typename CombineOp, typename OtherValueType>
565  void combine2(const InternalNode& other, const OtherValueType&, bool valIsActive, CombineOp&);
566 
572  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
573 
574  template<typename VisitorOp> void visit(VisitorOp&);
575  template<typename VisitorOp> void visit(VisitorOp&) const;
576 
577  template<typename OtherNodeType, typename VisitorOp>
578  void visit2Node(OtherNodeType& other, VisitorOp&);
579  template<typename OtherNodeType, typename VisitorOp>
580  void visit2Node(OtherNodeType& other, VisitorOp&) const;
581  template<typename IterT, typename VisitorOp>
582  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false);
583  template<typename IterT, typename VisitorOp>
584  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false) const;
585 
587  void clip(const CoordBBox&, const ValueType& background);
588 
592  void prune(const ValueType& tolerance = zeroVal<ValueType>());
593 
596  void addLeaf(LeafNodeType* leaf);
597 
600  template<typename AccessorT>
601  void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
602 
611  template<typename NodeT>
612  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
613 
620  bool addChild(ChildNodeType* child);
621 
624  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
625 
627  void addTile(Index offset, const ValueType& value, bool state);
628 
631  template<typename AccessorT>
632  void addTileAndCache(Index level, const Coord& xyz, const ValueType&, bool state, AccessorT&);
633 
635  template<typename NodeType> NodeType* probeNode(const Coord& xyz);
638  template<typename NodeType> const NodeType* probeConstNode(const Coord& xyz) const;
640 
642  template<typename NodeType, typename AccessorT>
645  NodeType* probeNodeAndCache(const Coord& xyz, AccessorT&);
646  template<typename NodeType, typename AccessorT>
647  const NodeType* probeConstNodeAndCache(const Coord& xyz, AccessorT&) const;
649 
651  LeafNodeType* probeLeaf(const Coord& xyz);
654  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
655  const LeafNodeType* probeLeaf(const Coord& xyz) const;
657 
659  template<typename AccessorT>
662  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc);
663  template<typename AccessorT>
664  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const;
665  template<typename AccessorT>
666  const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const;
668 
675  LeafNodeType* touchLeaf(const Coord& xyz);
676 
679  template<typename AccessorT>
680  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT&);
681 
683  template<typename ArrayT>
706  void getNodes(ArrayT& array);
707  template<typename ArrayT>
708  void getNodes(ArrayT& array) const;
710 
734  template<typename ArrayT>
735  void stealNodes(ArrayT& array, const ValueType& value, bool state);
736 
739  void resetBackground(const ValueType& oldBackground, const ValueType& newBackground);
740 
743  template<typename OtherChildNodeType, Index OtherLog2Dim>
744  bool hasSameTopology(const InternalNode<OtherChildNodeType, OtherLog2Dim>* other) const;
745 
746 protected:
748  friend class IteratorBase<MaskOnIterator, InternalNode>;
751  friend class IteratorBase<MaskOffIterator, InternalNode>;
752  friend class IteratorBase<MaskDenseIterator, InternalNode>;
754 
757  template<typename, Index> friend class InternalNode;
758 
759  // Mask accessors
760 public:
761  bool isValueMaskOn(Index n) const { return mValueMask.isOn(n); }
762  bool isValueMaskOn() const { return mValueMask.isOn(); }
763  bool isValueMaskOff(Index n) const { return mValueMask.isOff(n); }
764  bool isValueMaskOff() const { return mValueMask.isOff(); }
765  bool isChildMaskOn(Index n) const { return mChildMask.isOn(n); }
766  bool isChildMaskOff(Index n) const { return mChildMask.isOff(n); }
767  bool isChildMaskOff() const { return mChildMask.isOff(); }
768  const NodeMaskType& getValueMask() const { return mValueMask; }
769  const NodeMaskType& getChildMask() const { return mChildMask; }
771  {
772  NodeMaskType mask = mValueMask;
773  mask |= mChildMask;
774  mask.toggle();
775  return mask;
776  }
777  const UnionType* getTable() const { return mNodes; }
778 protected:
780  void setValueMask(Index n, bool on) { mValueMask.set(n, mChildMask.isOn(n) ? false : on); }
784 
785  void makeChildNodeEmpty(Index n, const ValueType& value);
786  void setChildNode( Index i, ChildNodeType* child);//assumes a tile
787  void resetChildNode(Index i, ChildNodeType* child);//checks for an existing child
788  ChildNodeType* unsetChildNode(Index i, const ValueType& value);
789 
790  template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
791  static inline void doVisit(NodeT&, VisitorOp&);
792 
793  template<typename NodeT, typename OtherNodeT, typename VisitorOp,
794  typename ChildAllIterT, typename OtherChildAllIterT>
795  static inline void doVisit2Node(NodeT&, OtherNodeT&, VisitorOp&);
796 
797  template<typename NodeT, typename VisitorOp,
798  typename ChildAllIterT, typename OtherChildAllIterT>
799  static inline void doVisit2(NodeT&, OtherChildAllIterT&, VisitorOp&, bool otherIsLHS);
800 
805  ChildNodeType* getChildNode(Index n);
806  const ChildNodeType* getChildNode(Index n) const;
808 
811  struct VoxelizeActiveTiles;
812  template<typename OtherInternalNode> struct DeepCopy;
813  template<typename OtherInternalNode> struct TopologyCopy1;
814  template<typename OtherInternalNode> struct TopologyCopy2;
815  template<typename OtherInternalNode> struct TopologyUnion;
816  template<typename OtherInternalNode> struct TopologyDifference;
817  template<typename OtherInternalNode> struct TopologyIntersection;
819 
820  UnionType mNodes[NUM_VALUES];
823  Coord mOrigin;
824 }; // class InternalNode
825 
826 
828 
829 
831 template<typename ChildT1, Index Dim1, typename NodeT2>
834 struct SameInternalConfig {
835  static const bool value = false;
836 };
837 
838 template<typename ChildT1, Index Dim1, typename ChildT2>
839 struct SameInternalConfig<ChildT1, Dim1, InternalNode<ChildT2, Dim1> > {
840  static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
841 };
843 
844 
846 
847 
848 template<typename ChildT, Index Log2Dim>
849 inline
851 {
852  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
853 }
854 
855 
856 template<typename ChildT, Index Log2Dim>
857 inline
858 InternalNode<ChildT, Log2Dim>::InternalNode(const Coord& origin, const ValueType& val, bool active):
859  mOrigin(origin[0] & ~(DIM - 1), // zero out the low-order bits
860  origin[1] & ~(DIM - 1),
861  origin[2] & ~(DIM - 1))
862 {
863  if (active) mValueMask.setOn();
864  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
865 }
866 
867 
868 // For InternalNodes, the PartialCreate constructor is identical to its
869 // non-PartialCreate counterpart.
870 template<typename ChildT, Index Log2Dim>
871 inline
873  const Coord& origin, const ValueType& val, bool active)
874  : mOrigin(origin[0] & ~(DIM-1), origin[1] & ~(DIM-1), origin[2] & ~(DIM-1))
875 {
876  if (active) mValueMask.setOn();
877  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
878 }
879 
880 template<typename ChildT, Index Log2Dim>
881 template<typename OtherInternalNode>
882 struct InternalNode<ChildT, Log2Dim>::DeepCopy
883 {
884  DeepCopy(const OtherInternalNode* source, InternalNode* target) : s(source), t(target) {
885  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
886  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//serial
887  }
888  void operator()(const tbb::blocked_range<Index> &r) const {
889  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
890  if (s->mChildMask.isOff(i)) {
891  t->mNodes[i].setValue(ValueType(s->mNodes[i].getValue()));
892  } else {
893  t->mNodes[i].setChild(new ChildNodeType(*(s->mNodes[i].getChild())));
894  }
895  }
896  }
897  const OtherInternalNode* s;
899 };// DeepCopy
900 
901 template<typename ChildT, Index Log2Dim>
902 inline
904  mChildMask(other.mChildMask),
905  mValueMask(other.mValueMask),
906  mOrigin(other.mOrigin)
907 {
908  DeepCopy<InternalNode<ChildT, Log2Dim> > tmp(&other, this);
909 }
910 
911 
912 // Copy-construct from a node with the same configuration but a different ValueType.
913 template<typename ChildT, Index Log2Dim>
914 template<typename OtherChildNodeType>
915 inline
917  : mChildMask(other.mChildMask)
918  , mValueMask(other.mValueMask)
919  , mOrigin(other.mOrigin)
920 {
922 }
923 
924 template<typename ChildT, Index Log2Dim>
925 template<typename OtherInternalNode>
926 struct InternalNode<ChildT, Log2Dim>::TopologyCopy1
927 {
928  TopologyCopy1(const OtherInternalNode* source, InternalNode* target,
929  const ValueType& background) : s(source), t(target), b(background) {
930  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
931  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//serial
932  }
933  void operator()(const tbb::blocked_range<Index> &r) const {
934  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
935  if (s->isChildMaskOn(i)) {
936  t->mNodes[i].setChild(new ChildNodeType(*(s->mNodes[i].getChild()),
937  b, TopologyCopy()));
938  } else {
939  t->mNodes[i].setValue(b);
940  }
941  }
942  }
943  const OtherInternalNode* s;
945  const ValueType &b;
946 };// TopologyCopy1
947 
948 template<typename ChildT, Index Log2Dim>
949 template<typename OtherChildNodeType>
950 inline
952  const ValueType& background, TopologyCopy):
953  mChildMask(other.mChildMask),
954  mValueMask(other.mValueMask),
955  mOrigin(other.mOrigin)
956 {
957  TopologyCopy1<InternalNode<OtherChildNodeType, Log2Dim> > tmp(&other, this, background);
958 }
959 
960 template<typename ChildT, Index Log2Dim>
961 template<typename OtherInternalNode>
962 struct InternalNode<ChildT, Log2Dim>::TopologyCopy2
963 {
964  TopologyCopy2(const OtherInternalNode* source, InternalNode* target,
965  const ValueType& offValue, const ValueType& onValue)
966  : s(source), t(target), offV(offValue), onV(onValue) {
967  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
968  }
969  void operator()(const tbb::blocked_range<Index> &r) const {
970  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
971  if (s->isChildMaskOn(i)) {
972  t->mNodes[i].setChild(new ChildNodeType(*(s->mNodes[i].getChild()),
973  offV, onV, TopologyCopy()));
974  } else {
975  t->mNodes[i].setValue(s->isValueMaskOn(i) ? onV : offV);
976  }
977  }
978  }
979  const OtherInternalNode* s;
981  const ValueType &offV, &onV;
982  };// TopologyCopy2
983 
984 template<typename ChildT, Index Log2Dim>
985 template<typename OtherChildNodeType>
986 inline
988  const ValueType& offValue,
989  const ValueType& onValue, TopologyCopy):
990  mChildMask(other.mChildMask),
991  mValueMask(other.mValueMask),
992  mOrigin(other.mOrigin)
993 {
994  TopologyCopy2<InternalNode<OtherChildNodeType, Log2Dim> > tmp(&other, this, offValue, onValue);
995 }
996 
997 
998 template<typename ChildT, Index Log2Dim>
999 inline
1001 {
1002  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1003  delete mNodes[iter.pos()].getChild();
1004  }
1005 }
1006 
1007 
1009 
1010 
1011 template<typename ChildT, Index Log2Dim>
1012 inline Index32
1014 {
1015  if (ChildNodeType::getLevel() == 0) return mChildMask.countOn();
1016  Index32 sum = 0;
1017  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1018  sum += iter->leafCount();
1019  }
1020  return sum;
1021 }
1022 
1023 template<typename ChildT, Index Log2Dim>
1024 inline void
1025 InternalNode<ChildT, Log2Dim>::nodeCount(std::vector<Index32> &vec) const
1026 {
1027  assert(vec.size() > ChildNodeType::LEVEL);
1028  const auto count = mChildMask.countOn();
1029  if (ChildNodeType::LEVEL > 0 && count > 0) {
1030  for (auto iter = this->cbeginChildOn(); iter; ++iter) iter->nodeCount(vec);
1031  }
1032  vec[ChildNodeType::LEVEL] += count;
1033 }
1034 
1035 
1036 template<typename ChildT, Index Log2Dim>
1037 inline Index32
1039 {
1040  Index32 sum = 1;
1041  if (ChildNodeType::getLevel() == 0) return sum;
1042  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1043  sum += iter->nonLeafCount();
1044  }
1045  return sum;
1046 }
1047 
1048 
1049 template<typename ChildT, Index Log2Dim>
1050 inline Index64
1052 {
1053  Index64 sum = ChildT::NUM_VOXELS * mValueMask.countOn();
1054  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1055  sum += iter->onVoxelCount();
1056  }
1057  return sum;
1058 }
1059 
1060 
1061 template<typename ChildT, Index Log2Dim>
1062 inline Index64
1064 {
1065  Index64 sum = ChildT::NUM_VOXELS * (NUM_VALUES-mValueMask.countOn()-mChildMask.countOn());
1066  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1067  sum += iter->offVoxelCount();
1068  }
1069  return sum;
1070 }
1071 
1072 
1073 template<typename ChildT, Index Log2Dim>
1074 inline Index64
1076 {
1077  Index64 sum = 0;
1078  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
1079  sum += mNodes[iter.pos()].getChild()->onLeafVoxelCount();
1080  }
1081  return sum;
1082 }
1083 
1084 
1085 template<typename ChildT, Index Log2Dim>
1086 inline Index64
1088 {
1089  Index64 sum = 0;
1090  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
1091  sum += mNodes[iter.pos()].getChild()->offLeafVoxelCount();
1092  }
1093  return sum;
1094 }
1095 
1096 template<typename ChildT, Index Log2Dim>
1097 inline Index64
1099 {
1100  Index64 sum = mValueMask.countOn();
1101  for (ChildOnCIter iter = this->cbeginChildOn(); LEVEL>1 && iter; ++iter) {
1102  sum += iter->onTileCount();
1103  }
1104  return sum;
1105 }
1106 
1107 template<typename ChildT, Index Log2Dim>
1108 inline Index64
1110 {
1111  Index64 sum = NUM_VALUES * sizeof(UnionType) + mChildMask.memUsage()
1112  + mValueMask.memUsage() + sizeof(mOrigin);
1113  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1114  sum += iter->memUsage();
1115  }
1116  return sum;
1117 }
1118 
1119 
1120 template<typename ChildT, Index Log2Dim>
1121 inline void
1122 InternalNode<ChildT, Log2Dim>::evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels) const
1123 {
1124  if (bbox.isInside(this->getNodeBoundingBox())) return;
1125 
1126  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) {
1127  bbox.expand(i.getCoord(), ChildT::DIM);
1128  }
1129  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) {
1130  i->evalActiveBoundingBox(bbox, visitVoxels);
1131  }
1132 }
1133 
1134 
1136 
1137 
1138 template<typename ChildT, Index Log2Dim>
1139 inline void
1141 {
1142  bool state = false;
1143  ValueType value = zeroVal<ValueType>();
1144  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1145  const Index i = iter.pos();
1146  ChildT* child = mNodes[i].getChild();
1147  child->prune(tolerance);
1148  if (child->isConstant(value, state, tolerance)) {
1149  delete child;
1150  mChildMask.setOff(i);
1151  mValueMask.set(i, state);
1152  mNodes[i].setValue(value);
1153  }
1154  }
1155 }
1156 
1157 
1159 
1160 
1161 template<typename ChildT, Index Log2Dim>
1162 template<typename NodeT>
1163 inline NodeT*
1164 InternalNode<ChildT, Log2Dim>::stealNode(const Coord& xyz, const ValueType& value, bool state)
1165 {
1166  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1167  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1169  const Index n = this->coordToOffset(xyz);
1170  if (mChildMask.isOff(n)) return nullptr;
1171  ChildT* child = mNodes[n].getChild();
1172  if (std::is_same<NodeT, ChildT>::value) {
1173  mChildMask.setOff(n);
1174  mValueMask.set(n, state);
1175  mNodes[n].setValue(value);
1176  }
1177  return (std::is_same<NodeT, ChildT>::value)
1178  ? reinterpret_cast<NodeT*>(child)
1179  : child->template stealNode<NodeT>(xyz, value, state);
1181 }
1182 
1183 
1185 
1186 
1187 template<typename ChildT, Index Log2Dim>
1188 template<typename NodeT>
1189 inline NodeT*
1191 {
1192  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1193  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1195  const Index n = this->coordToOffset(xyz);
1196  if (mChildMask.isOff(n)) return nullptr;
1197  ChildT* child = mNodes[n].getChild();
1198  return (std::is_same<NodeT, ChildT>::value)
1199  ? reinterpret_cast<NodeT*>(child)
1200  : child->template probeNode<NodeT>(xyz);
1202 }
1203 
1204 
1205 template<typename ChildT, Index Log2Dim>
1206 template<typename NodeT, typename AccessorT>
1207 inline NodeT*
1208 InternalNode<ChildT, Log2Dim>::probeNodeAndCache(const Coord& xyz, AccessorT& acc)
1209 {
1210  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1211  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1213  const Index n = this->coordToOffset(xyz);
1214  if (mChildMask.isOff(n)) return nullptr;
1215  ChildT* child = mNodes[n].getChild();
1216  acc.insert(xyz, child);
1217  return (std::is_same<NodeT, ChildT>::value)
1218  ? reinterpret_cast<NodeT*>(child)
1219  : child->template probeNodeAndCache<NodeT>(xyz, acc);
1221 }
1222 
1223 
1224 template<typename ChildT, Index Log2Dim>
1225 template<typename NodeT>
1226 inline const NodeT*
1228 {
1229  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1230  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1232  const Index n = this->coordToOffset(xyz);
1233  if (mChildMask.isOff(n)) return nullptr;
1234  const ChildT* child = mNodes[n].getChild();
1235  return (std::is_same<NodeT, ChildT>::value)
1236  ? reinterpret_cast<const NodeT*>(child)
1237  : child->template probeConstNode<NodeT>(xyz);
1239 }
1240 
1241 
1242 template<typename ChildT, Index Log2Dim>
1243 template<typename NodeT, typename AccessorT>
1244 inline const NodeT*
1245 InternalNode<ChildT, Log2Dim>::probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const
1246 {
1247  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1248  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1250  const Index n = this->coordToOffset(xyz);
1251  if (mChildMask.isOff(n)) return nullptr;
1252  const ChildT* child = mNodes[n].getChild();
1253  acc.insert(xyz, child);
1254  return (std::is_same<NodeT, ChildT>::value)
1255  ? reinterpret_cast<const NodeT*>(child)
1256  : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
1258 }
1259 
1260 
1262 
1263 
1264 template<typename ChildT, Index Log2Dim>
1265 inline typename ChildT::LeafNodeType*
1267 {
1268  return this->template probeNode<LeafNodeType>(xyz);
1269 }
1270 
1271 
1272 template<typename ChildT, Index Log2Dim>
1273 template<typename AccessorT>
1274 inline typename ChildT::LeafNodeType*
1275 InternalNode<ChildT, Log2Dim>::probeLeafAndCache(const Coord& xyz, AccessorT& acc)
1276 {
1277  return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
1278 }
1279 
1280 
1281 template<typename ChildT, Index Log2Dim>
1282 template<typename AccessorT>
1283 inline const typename ChildT::LeafNodeType*
1284 InternalNode<ChildT, Log2Dim>::probeLeafAndCache(const Coord& xyz, AccessorT& acc) const
1285 {
1286  return this->probeConstLeafAndCache(xyz, acc);
1287 }
1288 
1289 
1290 template<typename ChildT, Index Log2Dim>
1291 inline const typename ChildT::LeafNodeType*
1293 {
1294  return this->template probeConstNode<LeafNodeType>(xyz);
1295 }
1296 
1297 
1298 template<typename ChildT, Index Log2Dim>
1299 template<typename AccessorT>
1300 inline const typename ChildT::LeafNodeType*
1301 InternalNode<ChildT, Log2Dim>::probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
1302 {
1303  return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
1304 }
1305 
1306 
1308 
1309 
1310 template<typename ChildT, Index Log2Dim>
1311 inline void
1313 {
1314  assert(leaf != nullptr);
1315  const Coord& xyz = leaf->origin();
1316  const Index n = this->coordToOffset(xyz);
1317  ChildT* child = nullptr;
1318  if (mChildMask.isOff(n)) {
1319  if (ChildT::LEVEL>0) {
1320  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1321  } else {
1322  child = reinterpret_cast<ChildT*>(leaf);
1323  }
1324  this->setChildNode(n, child);
1325  } else {
1326  if (ChildT::LEVEL>0) {
1327  child = mNodes[n].getChild();
1328  } else {
1329  delete mNodes[n].getChild();
1330  child = reinterpret_cast<ChildT*>(leaf);
1331  mNodes[n].setChild(child);
1332  }
1333  }
1334  child->addLeaf(leaf);
1335 }
1336 
1337 
1338 template<typename ChildT, Index Log2Dim>
1339 template<typename AccessorT>
1340 inline void
1342 {
1343  assert(leaf != nullptr);
1344  const Coord& xyz = leaf->origin();
1345  const Index n = this->coordToOffset(xyz);
1346  ChildT* child = nullptr;
1347  if (mChildMask.isOff(n)) {
1348  if (ChildT::LEVEL>0) {
1349  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1350  acc.insert(xyz, child);//we only cache internal nodes
1351  } else {
1352  child = reinterpret_cast<ChildT*>(leaf);
1353  }
1354  this->setChildNode(n, child);
1355  } else {
1356  if (ChildT::LEVEL>0) {
1357  child = mNodes[n].getChild();
1358  acc.insert(xyz, child);//we only cache internal nodes
1359  } else {
1360  delete mNodes[n].getChild();
1361  child = reinterpret_cast<ChildT*>(leaf);
1362  mNodes[n].setChild(child);
1363  }
1364  }
1365  child->addLeafAndCache(leaf, acc);
1366 }
1367 
1368 
1370 
1371 
1372 template<typename ChildT, Index Log2Dim>
1373 inline bool
1375 {
1376  assert(child);
1377  const Coord& xyz = child->origin();
1378  // verify that the child belongs in this internal node
1379  if (Coord((xyz & ~(DIM-1))) != this->origin()) return false;
1380  // compute the offset and insert the child node
1381  const Index n = this->coordToOffset(xyz);
1382  // this also deletes an existing child node
1383  this->resetChildNode(n, child);
1384  return true;
1385 }
1386 
1387 
1388 template<typename ChildT, Index Log2Dim>
1389 inline void
1391 {
1392  assert(n < NUM_VALUES);
1393  this->makeChildNodeEmpty(n, value);
1394  mValueMask.set(n, state);
1395 }
1396 
1397 
1398 template<typename ChildT, Index Log2Dim>
1399 inline void
1401  const ValueType& value, bool state)
1402 {
1403  if (LEVEL >= level) {
1404  const Index n = this->coordToOffset(xyz);
1405  if (mChildMask.isOff(n)) {// tile case
1406  if (LEVEL > level) {
1407  ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1408  this->setChildNode(n, child);
1409  child->addTile(level, xyz, value, state);
1410  } else {
1411  mValueMask.set(n, state);
1412  mNodes[n].setValue(value);
1413  }
1414  } else {// child branch case
1415  ChildT* child = mNodes[n].getChild();
1416  if (LEVEL > level) {
1417  child->addTile(level, xyz, value, state);
1418  } else {
1419  delete child;
1420  mChildMask.setOff(n);
1421  mValueMask.set(n, state);
1422  mNodes[n].setValue(value);
1423  }
1424  }
1425  }
1426 }
1427 
1428 
1429 template<typename ChildT, Index Log2Dim>
1430 template<typename AccessorT>
1431 inline void
1433  const ValueType& value, bool state, AccessorT& acc)
1434 {
1435  if (LEVEL >= level) {
1436  const Index n = this->coordToOffset(xyz);
1437  if (mChildMask.isOff(n)) {// tile case
1438  if (LEVEL > level) {
1439  ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1440  this->setChildNode(n, child);
1441  acc.insert(xyz, child);
1442  child->addTileAndCache(level, xyz, value, state, acc);
1443  } else {
1444  mValueMask.set(n, state);
1445  mNodes[n].setValue(value);
1446  }
1447  } else {// child branch case
1448  ChildT* child = mNodes[n].getChild();
1449  if (LEVEL > level) {
1450  acc.insert(xyz, child);
1451  child->addTileAndCache(level, xyz, value, state, acc);
1452  } else {
1453  delete child;
1454  mChildMask.setOff(n);
1455  mValueMask.set(n, state);
1456  mNodes[n].setValue(value);
1457  }
1458  }
1459  }
1460 }
1461 
1462 
1464 
1465 
1466 template<typename ChildT, Index Log2Dim>
1467 inline typename ChildT::LeafNodeType*
1469 {
1470  const Index n = this->coordToOffset(xyz);
1471  ChildT* child = nullptr;
1472  if (mChildMask.isOff(n)) {
1473  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1474  this->setChildNode(n, child);
1475  } else {
1476  child = mNodes[n].getChild();
1477  }
1478  return child->touchLeaf(xyz);
1479 }
1480 
1481 
1482 template<typename ChildT, Index Log2Dim>
1483 template<typename AccessorT>
1484 inline typename ChildT::LeafNodeType*
1485 InternalNode<ChildT, Log2Dim>::touchLeafAndCache(const Coord& xyz, AccessorT& acc)
1486 {
1487  const Index n = this->coordToOffset(xyz);
1488  if (mChildMask.isOff(n)) {
1489  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), mValueMask.isOn(n)));
1490  }
1491  acc.insert(xyz, mNodes[n].getChild());
1492  return mNodes[n].getChild()->touchLeafAndCache(xyz, acc);
1493 }
1494 
1495 
1497 
1498 
1499 template<typename ChildT, Index Log2Dim>
1500 inline bool
1502  const ValueType& tolerance) const
1503 {
1504  if (!mChildMask.isOff() || !mValueMask.isConstant(state)) return false;// early termination
1505 
1506  firstValue = mNodes[0].getValue();
1507  for (Index i = 1; i < NUM_VALUES; ++i) {
1508  if (!math::isApproxEqual(mNodes[i].getValue(), firstValue, tolerance)) {
1509  return false; // early termination
1510  }
1511  }
1512  return true;
1513 }
1514 
1515 
1517 
1518 
1519 template<typename ChildT, Index Log2Dim>
1520 inline bool
1522  ValueType& maxValue,
1523  bool& state,
1524  const ValueType& tolerance) const
1525 {
1526 
1527  if (!mChildMask.isOff() || !mValueMask.isConstant(state)) return false;// early termination
1528  minValue = maxValue = mNodes[0].getValue();
1529  for (Index i = 1; i < NUM_VALUES; ++i) {
1530  const ValueType& v = mNodes[i].getValue();
1531  if (v < minValue) {
1532  if ((maxValue - v) > tolerance) return false;// early termination
1533  minValue = v;
1534  } else if (v > maxValue) {
1535  if ((v - minValue) > tolerance) return false;// early termination
1536  maxValue = v;
1537  }
1538  }
1539  return true;
1540 }
1541 
1542 
1544 
1545 
1546 template<typename ChildT, Index Log2Dim>
1547 inline bool
1549 {
1551  const bool anyActiveTiles = !mValueMask.isOff();
1552  if (LEVEL==1 || anyActiveTiles) return anyActiveTiles;
1553  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1554  if (iter->hasActiveTiles()) return true;
1555  }
1556  return false;
1558 }
1559 
1560 
1561 template<typename ChildT, Index Log2Dim>
1562 inline bool
1564 {
1565  const Index n = this->coordToOffset(xyz);
1566  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1567  return mNodes[n].getChild()->isValueOn(xyz);
1568 }
1569 
1570 template<typename ChildT, Index Log2Dim>
1571 template<typename AccessorT>
1572 inline bool
1573 InternalNode<ChildT, Log2Dim>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const
1574 {
1575  const Index n = this->coordToOffset(xyz);
1576  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1577  acc.insert(xyz, mNodes[n].getChild());
1578  return mNodes[n].getChild()->isValueOnAndCache(xyz, acc);
1579 }
1580 
1581 
1582 template<typename ChildT, Index Log2Dim>
1583 inline const typename ChildT::ValueType&
1585 {
1586  const Index n = this->coordToOffset(xyz);
1587  return this->isChildMaskOff(n) ? mNodes[n].getValue()
1588  : mNodes[n].getChild()->getValue(xyz);
1589 }
1590 
1591 template<typename ChildT, Index Log2Dim>
1592 template<typename AccessorT>
1593 inline const typename ChildT::ValueType&
1594 InternalNode<ChildT, Log2Dim>::getValueAndCache(const Coord& xyz, AccessorT& acc) const
1595 {
1596  const Index n = this->coordToOffset(xyz);
1597  if (this->isChildMaskOn(n)) {
1598  acc.insert(xyz, mNodes[n].getChild());
1599  return mNodes[n].getChild()->getValueAndCache(xyz, acc);
1600  }
1601  return mNodes[n].getValue();
1602 }
1603 
1604 
1605 template<typename ChildT, Index Log2Dim>
1606 inline Index
1608 {
1609  const Index n = this->coordToOffset(xyz);
1610  return this->isChildMaskOff(n) ? LEVEL : mNodes[n].getChild()->getValueLevel(xyz);
1611 }
1612 
1613 template<typename ChildT, Index Log2Dim>
1614 template<typename AccessorT>
1615 inline Index
1616 InternalNode<ChildT, Log2Dim>::getValueLevelAndCache(const Coord& xyz, AccessorT& acc) const
1617 {
1618  const Index n = this->coordToOffset(xyz);
1619  if (this->isChildMaskOn(n)) {
1620  acc.insert(xyz, mNodes[n].getChild());
1621  return mNodes[n].getChild()->getValueLevelAndCache(xyz, acc);
1622  }
1623  return LEVEL;
1624 }
1625 
1626 
1627 template<typename ChildT, Index Log2Dim>
1628 inline bool
1630 {
1631  const Index n = this->coordToOffset(xyz);
1632  if (this->isChildMaskOff(n)) {
1633  value = mNodes[n].getValue();
1634  return this->isValueMaskOn(n);
1635  }
1636  return mNodes[n].getChild()->probeValue(xyz, value);
1637 }
1638 
1639 template<typename ChildT, Index Log2Dim>
1640 template<typename AccessorT>
1641 inline bool
1643  ValueType& value, AccessorT& acc) const
1644 {
1645  const Index n = this->coordToOffset(xyz);
1646  if (this->isChildMaskOn(n)) {
1647  acc.insert(xyz, mNodes[n].getChild());
1648  return mNodes[n].getChild()->probeValueAndCache(xyz, value, acc);
1649  }
1650  value = mNodes[n].getValue();
1651  return this->isValueMaskOn(n);
1652 }
1653 
1654 
1655 template<typename ChildT, Index Log2Dim>
1656 inline void
1658 {
1659  const Index n = this->coordToOffset(xyz);
1660  bool hasChild = this->isChildMaskOn(n);
1661  if (!hasChild && this->isValueMaskOn(n)) {
1662  // If the voxel belongs to a constant tile that is active,
1663  // a child subtree must be constructed.
1664  hasChild = true;
1665  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/true));
1666  }
1667  if (hasChild) mNodes[n].getChild()->setValueOff(xyz);
1668 }
1669 
1670 
1671 template<typename ChildT, Index Log2Dim>
1672 inline void
1674 {
1675  const Index n = this->coordToOffset(xyz);
1676  bool hasChild = this->isChildMaskOn(n);
1677  if (!hasChild && !this->isValueMaskOn(n)) {
1678  // If the voxel belongs to a constant tile that is inactive,
1679  // a child subtree must be constructed.
1680  hasChild = true;
1681  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/false));
1682  }
1683  if (hasChild) mNodes[n].getChild()->setValueOn(xyz);
1684 }
1685 
1686 
1687 template<typename ChildT, Index Log2Dim>
1688 inline void
1690 {
1691  const Index n = InternalNode::coordToOffset(xyz);
1692  bool hasChild = this->isChildMaskOn(n);
1693  if (!hasChild) {
1694  const bool active = this->isValueMaskOn(n);
1695  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1696  // If the voxel belongs to a tile that is either active or that
1697  // has a constant value that is different from the one provided,
1698  // a child subtree must be constructed.
1699  hasChild = true;
1700  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1701  }
1702  }
1703  if (hasChild) mNodes[n].getChild()->setValueOff(xyz, value);
1704 }
1705 
1706 template<typename ChildT, Index Log2Dim>
1707 template<typename AccessorT>
1708 inline void
1710  const ValueType& value, AccessorT& acc)
1711 {
1712  const Index n = InternalNode::coordToOffset(xyz);
1713  bool hasChild = this->isChildMaskOn(n);
1714  if (!hasChild) {
1715  const bool active = this->isValueMaskOn(n);
1716  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1717  // If the voxel belongs to a tile that is either active or that
1718  // has a constant value that is different from the one provided,
1719  // a child subtree must be constructed.
1720  hasChild = true;
1721  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1722  }
1723  }
1724  if (hasChild) {
1725  ChildT* child = mNodes[n].getChild();
1726  acc.insert(xyz, child);
1727  child->setValueOffAndCache(xyz, value, acc);
1728  }
1729 }
1730 
1731 
1732 template<typename ChildT, Index Log2Dim>
1733 inline void
1735 {
1736  const Index n = this->coordToOffset(xyz);
1737  bool hasChild = this->isChildMaskOn(n);
1738  if (!hasChild) {
1739  const bool active = this->isValueMaskOn(n); // tile's active state
1740  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1741  // If the voxel belongs to a tile that is either inactive or that
1742  // has a constant value that is different from the one provided,
1743  // a child subtree must be constructed.
1744  hasChild = true;
1745  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1746  }
1747  }
1748  if (hasChild) mNodes[n].getChild()->setValueOn(xyz, value);
1749 }
1750 
1751 template<typename ChildT, Index Log2Dim>
1752 template<typename AccessorT>
1753 inline void
1755  const ValueType& value, AccessorT& acc)
1756 {
1757  const Index n = this->coordToOffset(xyz);
1758  bool hasChild = this->isChildMaskOn(n);
1759  if (!hasChild) {
1760  const bool active = this->isValueMaskOn(n);
1761  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1762  // If the voxel belongs to a tile that is either inactive or that
1763  // has a constant value that is different from the one provided,
1764  // a child subtree must be constructed.
1765  hasChild = true;
1766  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1767  }
1768  }
1769  if (hasChild) {
1770  acc.insert(xyz, mNodes[n].getChild());
1771  mNodes[n].getChild()->setValueAndCache(xyz, value, acc);
1772  }
1773 }
1774 
1775 
1776 template<typename ChildT, Index Log2Dim>
1777 inline void
1779 {
1780  const Index n = this->coordToOffset(xyz);
1781  bool hasChild = this->isChildMaskOn(n);
1782  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1783  // If the voxel has a tile value that is different from the one provided,
1784  // a child subtree must be constructed.
1785  const bool active = this->isValueMaskOn(n);
1786  hasChild = true;
1787  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1788  }
1789  if (hasChild) mNodes[n].getChild()->setValueOnly(xyz, value);
1790 }
1791 
1792 template<typename ChildT, Index Log2Dim>
1793 template<typename AccessorT>
1794 inline void
1796  const ValueType& value, AccessorT& acc)
1797 {
1798  const Index n = this->coordToOffset(xyz);
1799  bool hasChild = this->isChildMaskOn(n);
1800  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1801  // If the voxel has a tile value that is different from the one provided,
1802  // a child subtree must be constructed.
1803  const bool active = this->isValueMaskOn(n);
1804  hasChild = true;
1805  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1806  }
1807  if (hasChild) {
1808  acc.insert(xyz, mNodes[n].getChild());
1809  mNodes[n].getChild()->setValueOnlyAndCache(xyz, value, acc);
1810  }
1811 }
1812 
1813 
1814 template<typename ChildT, Index Log2Dim>
1815 inline void
1817 {
1818  const Index n = this->coordToOffset(xyz);
1819  bool hasChild = this->isChildMaskOn(n);
1820  if (!hasChild) {
1821  if (on != this->isValueMaskOn(n)) {
1822  // If the voxel belongs to a tile with the wrong active state,
1823  // then a child subtree must be constructed.
1824  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1825  hasChild = true;
1826  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1827  }
1828  }
1829  if (hasChild) mNodes[n].getChild()->setActiveState(xyz, on);
1830 }
1831 
1832 template<typename ChildT, Index Log2Dim>
1833 template<typename AccessorT>
1834 inline void
1835 InternalNode<ChildT, Log2Dim>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc)
1836 {
1837  const Index n = this->coordToOffset(xyz);
1838  bool hasChild = this->isChildMaskOn(n);
1839  if (!hasChild) {
1840  if (on != this->isValueMaskOn(n)) {
1841  // If the voxel belongs to a tile with the wrong active state,
1842  // then a child subtree must be constructed.
1843  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1844  hasChild = true;
1845  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1846  }
1847  }
1848  if (hasChild) {
1849  ChildT* child = mNodes[n].getChild();
1850  acc.insert(xyz, child);
1851  child->setActiveStateAndCache(xyz, on, acc);
1852  }
1853 }
1854 
1855 
1856 template<typename ChildT, Index Log2Dim>
1857 inline void
1859 {
1861  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1862  mNodes[iter.pos()].getChild()->setValuesOn();
1863  }
1864 }
1865 
1866 
1867 template<typename ChildT, Index Log2Dim>
1868 template<typename ModifyOp>
1869 inline void
1870 InternalNode<ChildT, Log2Dim>::modifyValue(const Coord& xyz, const ModifyOp& op)
1871 {
1872  const Index n = InternalNode::coordToOffset(xyz);
1873  bool hasChild = this->isChildMaskOn(n);
1874  if (!hasChild) {
1875  // Need to create a child if the tile is inactive,
1876  // in order to activate voxel (x, y, z).
1877  const bool active = this->isValueMaskOn(n);
1878  bool createChild = !active;
1879  if (!createChild) {
1880  // Need to create a child if applying the functor
1881  // to the tile value produces a different value.
1882  const ValueType& tileVal = mNodes[n].getValue();
1883  ValueType modifiedVal = tileVal;
1884  op(modifiedVal);
1885  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1886  }
1887  if (createChild) {
1888  hasChild = true;
1889  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1890  }
1891  }
1892  if (hasChild) mNodes[n].getChild()->modifyValue(xyz, op);
1893 }
1894 
1895 template<typename ChildT, Index Log2Dim>
1896 template<typename ModifyOp, typename AccessorT>
1897 inline void
1898 InternalNode<ChildT, Log2Dim>::modifyValueAndCache(const Coord& xyz, const ModifyOp& op,
1899  AccessorT& acc)
1900 {
1901  const Index n = InternalNode::coordToOffset(xyz);
1902  bool hasChild = this->isChildMaskOn(n);
1903  if (!hasChild) {
1904  // Need to create a child if the tile is inactive,
1905  // in order to activate voxel (x, y, z).
1906  const bool active = this->isValueMaskOn(n);
1907  bool createChild = !active;
1908  if (!createChild) {
1909  // Need to create a child if applying the functor
1910  // to the tile value produces a different value.
1911  const ValueType& tileVal = mNodes[n].getValue();
1912  ValueType modifiedVal = tileVal;
1913  op(modifiedVal);
1914  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1915  }
1916  if (createChild) {
1917  hasChild = true;
1918  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1919  }
1920  }
1921  if (hasChild) {
1922  ChildNodeType* child = mNodes[n].getChild();
1923  acc.insert(xyz, child);
1924  child->modifyValueAndCache(xyz, op, acc);
1925  }
1926 }
1927 
1928 
1929 template<typename ChildT, Index Log2Dim>
1930 template<typename ModifyOp>
1931 inline void
1933 {
1934  const Index n = InternalNode::coordToOffset(xyz);
1935  bool hasChild = this->isChildMaskOn(n);
1936  if (!hasChild) {
1937  const bool tileState = this->isValueMaskOn(n);
1938  const ValueType& tileVal = mNodes[n].getValue();
1939  bool modifiedState = !tileState;
1940  ValueType modifiedVal = tileVal;
1941  op(modifiedVal, modifiedState);
1942  // Need to create a child if applying the functor to the tile
1943  // produces a different value or active state.
1944  if (modifiedState != tileState || !math::isExactlyEqual(modifiedVal, tileVal)) {
1945  hasChild = true;
1946  this->setChildNode(n, new ChildNodeType(xyz, tileVal, tileState));
1947  }
1948  }
1949  if (hasChild) mNodes[n].getChild()->modifyValueAndActiveState(xyz, op);
1950 }
1951 
1952 template<typename ChildT, Index Log2Dim>
1953 template<typename ModifyOp, typename AccessorT>
1954 inline void
1956  const Coord& xyz, const ModifyOp& op, AccessorT& acc)
1957 {
1958  const Index n = InternalNode::coordToOffset(xyz);
1959  bool hasChild = this->isChildMaskOn(n);
1960  if (!hasChild) {
1961  const bool tileState = this->isValueMaskOn(n);
1962  const ValueType& tileVal = mNodes[n].getValue();
1963  bool modifiedState = !tileState;
1964  ValueType modifiedVal = tileVal;
1965  op(modifiedVal, modifiedState);
1966  // Need to create a child if applying the functor to the tile
1967  // produces a different value or active state.
1968  if (modifiedState != tileState || !math::isExactlyEqual(modifiedVal, tileVal)) {
1969  hasChild = true;
1970  this->setChildNode(n, new ChildNodeType(xyz, tileVal, tileState));
1971  }
1972  }
1973  if (hasChild) {
1974  ChildNodeType* child = mNodes[n].getChild();
1975  acc.insert(xyz, child);
1976  child->modifyValueAndActiveStateAndCache(xyz, op, acc);
1977  }
1978 }
1979 
1980 
1982 
1983 
1984 template<typename ChildT, Index Log2Dim>
1985 inline void
1986 InternalNode<ChildT, Log2Dim>::clip(const CoordBBox& clipBBox, const ValueType& background)
1987 {
1988  CoordBBox nodeBBox = this->getNodeBoundingBox();
1989  if (!clipBBox.hasOverlap(nodeBBox)) {
1990  // This node lies completely outside the clipping region. Fill it with background tiles.
1991  this->fill(nodeBBox, background, /*active=*/false);
1992  } else if (clipBBox.isInside(nodeBBox)) {
1993  // This node lies completely inside the clipping region. Leave it intact.
1994  return;
1995  }
1996 
1997  // This node isn't completely contained inside the clipping region.
1998  // Clip tiles and children, and replace any that lie outside the region
1999  // with background tiles.
2000 
2001  for (Index pos = 0; pos < NUM_VALUES; ++pos) {
2002  const Coord xyz = this->offsetToGlobalCoord(pos); // tile or child origin
2003  CoordBBox tileBBox(xyz, xyz.offsetBy(ChildT::DIM - 1)); // tile or child bounds
2004  if (!clipBBox.hasOverlap(tileBBox)) {
2005  // This table entry lies completely outside the clipping region.
2006  // Replace it with a background tile.
2007  this->makeChildNodeEmpty(pos, background);
2008  mValueMask.setOff(pos);
2009  } else if (!clipBBox.isInside(tileBBox)) {
2010  // This table entry does not lie completely inside the clipping region
2011  // and must be clipped.
2012  if (this->isChildMaskOn(pos)) {
2013  mNodes[pos].getChild()->clip(clipBBox, background);
2014  } else {
2015  // Replace this tile with a background tile, then fill the clip region
2016  // with the tile's original value. (This might create a child branch.)
2017  tileBBox.intersect(clipBBox);
2018  const ValueType val = mNodes[pos].getValue();
2019  const bool on = this->isValueMaskOn(pos);
2020  mNodes[pos].setValue(background);
2021  mValueMask.setOff(pos);
2022  this->fill(tileBBox, val, on);
2023  }
2024  } else {
2025  // This table entry lies completely inside the clipping region. Leave it intact.
2026  }
2027  }
2028 }
2029 
2030 
2032 
2033 
2034 template<typename ChildT, Index Log2Dim>
2035 inline void
2036 InternalNode<ChildT, Log2Dim>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
2037 {
2038  auto clippedBBox = this->getNodeBoundingBox();
2039  clippedBBox.intersect(bbox);
2040  if (!clippedBBox) return;
2041 
2042  // Iterate over the fill region in axis-aligned, tile-sized chunks.
2043  // (The first and last chunks along each axis might be smaller than a tile.)
2044  Coord xyz, tileMin, tileMax;
2045  for (int x = clippedBBox.min().x(); x <= clippedBBox.max().x(); x = tileMax.x() + 1) {
2046  xyz.setX(x);
2047  for (int y = clippedBBox.min().y(); y <= clippedBBox.max().y(); y = tileMax.y() + 1) {
2048  xyz.setY(y);
2049  for (int z = clippedBBox.min().z(); z <= clippedBBox.max().z(); z = tileMax.z() + 1) {
2050  xyz.setZ(z);
2051 
2052  // Get the bounds of the tile that contains voxel (x, y, z).
2053  const Index n = this->coordToOffset(xyz);
2054  tileMin = this->offsetToGlobalCoord(n);
2055  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2056 
2057  if (xyz != tileMin || Coord::lessThan(clippedBBox.max(), tileMax)) {
2058  // If the box defined by (xyz, clippedBBox.max()) doesn't completely enclose
2059  // the tile to which xyz belongs, create a child node (or retrieve
2060  // the existing one).
2061  ChildT* child = nullptr;
2062  if (this->isChildMaskOff(n)) {
2063  // Replace the tile with a newly-created child that is initialized
2064  // with the tile's value and active state.
2065  child = new ChildT{xyz, mNodes[n].getValue(), this->isValueMaskOn(n)};
2066  this->setChildNode(n, child);
2067  } else {
2068  child = mNodes[n].getChild();
2069  }
2070 
2071  // Forward the fill request to the child.
2072  if (child) {
2073  const Coord tmp = Coord::minComponent(clippedBBox.max(), tileMax);
2074  child->fill(CoordBBox(xyz, tmp), value, active);
2075  }
2076 
2077  } else {
2078  // If the box given by (xyz, clippedBBox.max()) completely encloses
2079  // the tile to which xyz belongs, create the tile (if it
2080  // doesn't already exist) and give it the fill value.
2081  this->makeChildNodeEmpty(n, value);
2082  mValueMask.set(n, active);
2083  }
2084  }
2085  }
2086  }
2087 }
2088 
2089 
2090 template<typename ChildT, Index Log2Dim>
2091 inline void
2092 InternalNode<ChildT, Log2Dim>::denseFill(const CoordBBox& bbox, const ValueType& value, bool active)
2093 {
2094  auto clippedBBox = this->getNodeBoundingBox();
2095  clippedBBox.intersect(bbox);
2096  if (!clippedBBox) return;
2097 
2098  // Iterate over the fill region in axis-aligned, tile-sized chunks.
2099  // (The first and last chunks along each axis might be smaller than a tile.)
2100  Coord xyz, tileMin, tileMax;
2101  for (int x = clippedBBox.min().x(); x <= clippedBBox.max().x(); x = tileMax.x() + 1) {
2102  xyz.setX(x);
2103  for (int y = clippedBBox.min().y(); y <= clippedBBox.max().y(); y = tileMax.y() + 1) {
2104  xyz.setY(y);
2105  for (int z = clippedBBox.min().z(); z <= clippedBBox.max().z(); z = tileMax.z() + 1) {
2106  xyz.setZ(z);
2107 
2108  // Get the table index of the tile that contains voxel (x, y, z).
2109  const auto n = this->coordToOffset(xyz);
2110 
2111  // Retrieve the child node at index n, or replace the tile at index n with a child.
2112  ChildT* child = nullptr;
2113  if (this->isChildMaskOn(n)) {
2114  child = mNodes[n].getChild();
2115  } else {
2116  // Replace the tile with a newly-created child that is filled
2117  // with the tile's value and active state.
2118  child = new ChildT{xyz, mNodes[n].getValue(), this->isValueMaskOn(n)};
2119  this->setChildNode(n, child);
2120  }
2121 
2122  // Get the bounds of the tile that contains voxel (x, y, z).
2123  tileMin = this->offsetToGlobalCoord(n);
2124  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2125 
2126  // Forward the fill request to the child.
2127  child->denseFill(CoordBBox{xyz, clippedBBox.max()}, value, active);
2128  }
2129  }
2130  }
2131 }
2132 
2133 
2135 
2136 
2137 template<typename ChildT, Index Log2Dim>
2138 template<typename DenseT>
2139 inline void
2140 InternalNode<ChildT, Log2Dim>::copyToDense(const CoordBBox& bbox, DenseT& dense) const
2141 {
2142  using DenseValueType = typename DenseT::ValueType;
2143 
2144  const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2145  const Coord& min = dense.bbox().min();
2146  for (Coord xyz = bbox.min(), max; xyz[0] <= bbox.max()[0]; xyz[0] = max[0] + 1) {
2147  for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = max[1] + 1) {
2148  for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = max[2] + 1) {
2149  const Index n = this->coordToOffset(xyz);
2150  // Get max coordinates of the child node that contains voxel xyz.
2151  max = this->offsetToGlobalCoord(n).offsetBy(ChildT::DIM-1);
2152 
2153  // Get the bbox of the interection of bbox and the child node
2154  CoordBBox sub(xyz, Coord::minComponent(bbox.max(), max));
2155 
2156  if (this->isChildMaskOn(n)) {//is a child
2157  mNodes[n].getChild()->copyToDense(sub, dense);
2158  } else {//a tile value
2159  const ValueType value = mNodes[n].getValue();
2160  sub.translate(-min);
2161  DenseValueType* a0 = dense.data() + zStride*sub.min()[2];
2162  for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
2163  DenseValueType* a1 = a0 + x*xStride;
2164  for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
2165  DenseValueType* a2 = a1 + y*yStride;
2166  for (Int32 z = sub.min()[2], ez = sub.max()[2]+1;
2167  z < ez; ++z, a2 += zStride)
2168  {
2169  *a2 = DenseValueType(value);
2170  }
2171  }
2172  }
2173  }
2174  }
2175  }
2176  }
2177 }
2178 
2179 
2181 
2182 
2183 template<typename ChildT, Index Log2Dim>
2184 inline void
2185 InternalNode<ChildT, Log2Dim>::writeTopology(std::ostream& os, bool toHalf) const
2186 {
2187  mChildMask.save(os);
2188  mValueMask.save(os);
2189 
2190  {
2191  // Copy all of this node's values into an array.
2192  std::unique_ptr<ValueType[]> valuePtr(new ValueType[NUM_VALUES]);
2193  ValueType* values = valuePtr.get();
2194  const ValueType zero = zeroVal<ValueType>();
2195  for (Index i = 0; i < NUM_VALUES; ++i) {
2196  values[i] = (mChildMask.isOff(i) ? mNodes[i].getValue() : zero);
2197  }
2198  // Compress (optionally) and write out the contents of the array.
2199  io::writeCompressedValues(os, values, NUM_VALUES, mValueMask, mChildMask, toHalf);
2200  }
2201  // Write out the child nodes in order.
2202  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2203  iter->writeTopology(os, toHalf);
2204  }
2205 }
2206 
2207 
2208 template<typename ChildT, Index Log2Dim>
2209 inline void
2210 InternalNode<ChildT, Log2Dim>::readTopology(std::istream& is, bool fromHalf)
2211 {
2212  const ValueType background = (!io::getGridBackgroundValuePtr(is) ? zeroVal<ValueType>()
2213  : *static_cast<const ValueType*>(io::getGridBackgroundValuePtr(is)));
2214 
2215  mChildMask.load(is);
2216  mValueMask.load(is);
2217 
2219  for (Index i = 0; i < NUM_VALUES; ++i) {
2220  if (this->isChildMaskOn(i)) {
2221  ChildNodeType* child =
2222  new ChildNodeType(PartialCreate(), offsetToGlobalCoord(i), background);
2223  mNodes[i].setChild(child);
2224  child->readTopology(is);
2225  } else {
2226  ValueType value;
2227  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2228  mNodes[i].setValue(value);
2229  }
2230  }
2231  } else {
2232  const bool oldVersion =
2234  const Index numValues = (oldVersion ? mChildMask.countOff() : NUM_VALUES);
2235  {
2236  // Read in (and uncompress, if necessary) all of this node's values
2237  // into a contiguous array.
2238  std::unique_ptr<ValueType[]> valuePtr(new ValueType[numValues]);
2239  ValueType* values = valuePtr.get();
2240  io::readCompressedValues(is, values, numValues, mValueMask, fromHalf);
2241 
2242  // Copy values from the array into this node's table.
2243  if (oldVersion) {
2244  Index n = 0;
2245  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
2246  mNodes[iter.pos()].setValue(values[n++]);
2247  }
2248  assert(n == numValues);
2249  } else {
2250  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
2251  mNodes[iter.pos()].setValue(values[iter.pos()]);
2252  }
2253  }
2254  }
2255  // Read in all child nodes and insert them into the table at their proper locations.
2256  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2257  ChildNodeType* child = new ChildNodeType(PartialCreate(), iter.getCoord(), background);
2258  mNodes[iter.pos()].setChild(child);
2259  child->readTopology(is, fromHalf);
2260  }
2261  }
2262 }
2263 
2264 
2266 
2267 
2268 template<typename ChildT, Index Log2Dim>
2269 inline const typename ChildT::ValueType&
2271 {
2272  return (this->isChildMaskOn(0) ? mNodes[0].getChild()->getFirstValue() : mNodes[0].getValue());
2273 }
2274 
2275 
2276 template<typename ChildT, Index Log2Dim>
2277 inline const typename ChildT::ValueType&
2279 {
2280  const Index n = NUM_VALUES - 1;
2281  return (this->isChildMaskOn(n) ? mNodes[n].getChild()->getLastValue() : mNodes[n].getValue());
2282 }
2283 
2284 
2286 
2287 
2288 template<typename ChildT, Index Log2Dim>
2289 inline void
2291 {
2292  for (Index i = 0; i < NUM_VALUES; ++i) {
2293  if (this->isChildMaskOn(i)) {
2294  mNodes[i].getChild()->negate();
2295  } else {
2297  }
2298  }
2299 
2300 }
2301 
2302 
2304 
2305 
2306 template<typename ChildT, Index Log2Dim>
2308 {
2309  VoxelizeActiveTiles(InternalNode &node) : mNode(&node) {
2310  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2311  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2312 
2313  node.mChildMask |= node.mValueMask;
2314  node.mValueMask.setOff();
2315  }
2316  void operator()(const tbb::blocked_range<Index> &r) const
2317  {
2318  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2319  if (mNode->mChildMask.isOn(i)) {// Loop over node's child nodes
2320  mNode->mNodes[i].getChild()->voxelizeActiveTiles(true);
2321  } else if (mNode->mValueMask.isOn(i)) {// Loop over node's active tiles
2322  const Coord &ijk = mNode->offsetToGlobalCoord(i);
2323  ChildNodeType *child = new ChildNodeType(ijk, mNode->mNodes[i].getValue(), true);
2324  child->voxelizeActiveTiles(true);
2325  mNode->mNodes[i].setChild(child);
2326  }
2327  }
2328  }
2330 };// VoxelizeActiveTiles
2331 
2332 template<typename ChildT, Index Log2Dim>
2333 inline void
2335 {
2336  if (threaded) {
2337  VoxelizeActiveTiles tmp(*this);
2338  } else {
2339  for (ValueOnIter iter = this->beginValueOn(); iter; ++iter) {
2340  this->setChildNode(iter.pos(),
2341  new ChildNodeType(iter.getCoord(), iter.getValue(), true));
2342  }
2343  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter)
2344  iter->voxelizeActiveTiles(false);
2345  }
2346 }
2347 
2348 
2350 
2351 
2352 template<typename ChildT, Index Log2Dim>
2353 template<MergePolicy Policy>
2354 inline void
2356  const ValueType& background, const ValueType& otherBackground)
2357 {
2359 
2360  switch (Policy) {
2361 
2362  case MERGE_ACTIVE_STATES:
2363  default:
2364  {
2365  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2366  const Index n = iter.pos();
2367  if (mChildMask.isOn(n)) {
2368  // Merge this node's child with the other node's child.
2369  mNodes[n].getChild()->template merge<MERGE_ACTIVE_STATES>(*iter,
2370  background, otherBackground);
2371  } else if (mValueMask.isOff(n)) {
2372  // Replace this node's inactive tile with the other node's child
2373  // and replace the other node's child with a tile of undefined value
2374  // (which is okay since the other tree is assumed to be cannibalized
2375  // in the process of merging).
2376  ChildNodeType* child = other.mNodes[n].getChild();
2377  other.mChildMask.setOff(n);
2378  child->resetBackground(otherBackground, background);
2379  this->setChildNode(n, child);
2380  }
2381  }
2382 
2383  // Copy active tile values.
2384  for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
2385  const Index n = iter.pos();
2386  if (mValueMask.isOff(n)) {
2387  // Replace this node's child or inactive tile with the other node's active tile.
2388  this->makeChildNodeEmpty(n, iter.getValue());
2389  mValueMask.setOn(n);
2390  }
2391  }
2392  break;
2393  }
2394 
2395  case MERGE_NODES:
2396  {
2397  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2398  const Index n = iter.pos();
2399  if (mChildMask.isOn(n)) {
2400  // Merge this node's child with the other node's child.
2401  mNodes[n].getChild()->template merge<Policy>(*iter, background, otherBackground);
2402  } else {
2403  // Replace this node's tile (regardless of its active state) with
2404  // the other node's child and replace the other node's child with
2405  // a tile of undefined value (which is okay since the other tree
2406  // is assumed to be cannibalized in the process of merging).
2407  ChildNodeType* child = other.mNodes[n].getChild();
2408  other.mChildMask.setOff(n);
2409  child->resetBackground(otherBackground, background);
2410  this->setChildNode(n, child);
2411  }
2412  }
2413  break;
2414  }
2415 
2417  {
2418  // Transfer children from the other tree to this tree.
2419  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2420  const Index n = iter.pos();
2421  if (mChildMask.isOn(n)) {
2422  // Merge this node's child with the other node's child.
2423  mNodes[n].getChild()->template merge<Policy>(*iter, background, otherBackground);
2424  } else {
2425  // Replace this node's tile with the other node's child, leaving the other
2426  // node with an inactive tile of undefined value (which is okay since
2427  // the other tree is assumed to be cannibalized in the process of merging).
2428  ChildNodeType* child = other.mNodes[n].getChild();
2429  other.mChildMask.setOff(n);
2430  child->resetBackground(otherBackground, background);
2431  if (mValueMask.isOn(n)) {
2432  // Merge the child with this node's active tile.
2433  child->template merge<Policy>(mNodes[n].getValue(), /*on=*/true);
2434  mValueMask.setOff(n);
2435  }
2436  mChildMask.setOn(n);
2437  mNodes[n].setChild(child);
2438  }
2439  }
2440 
2441  // Merge active tiles into this tree.
2442  for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
2443  const Index n = iter.pos();
2444  if (mChildMask.isOn(n)) {
2445  // Merge the other node's active tile into this node's child.
2446  mNodes[n].getChild()->template merge<Policy>(iter.getValue(), /*on=*/true);
2447  } else if (mValueMask.isOff(n)) {
2448  // Replace this node's inactive tile with the other node's active tile.
2449  mNodes[n].setValue(iter.getValue());
2450  mValueMask.setOn(n);
2451  }
2452  }
2453  break;
2454  }
2455 
2456  }
2458 }
2459 
2460 
2461 template<typename ChildT, Index Log2Dim>
2462 template<MergePolicy Policy>
2463 inline void
2464 InternalNode<ChildT, Log2Dim>::merge(const ValueType& tileValue, bool tileActive)
2465 {
2467 
2468  if (Policy != MERGE_ACTIVE_STATES_AND_NODES) return;
2469 
2470  // For MERGE_ACTIVE_STATES_AND_NODES, inactive tiles in the other tree are ignored.
2471  if (!tileActive) return;
2472 
2473  // Iterate over this node's children and inactive tiles.
2474  for (ValueOffIter iter = this->beginValueOff(); iter; ++iter) {
2475  const Index n = iter.pos();
2476  if (mChildMask.isOn(n)) {
2477  // Merge the other node's active tile into this node's child.
2478  mNodes[n].getChild()->template merge<Policy>(tileValue, /*on=*/true);
2479  } else {
2480  // Replace this node's inactive tile with the other node's active tile.
2481  iter.setValue(tileValue);
2482  mValueMask.setOn(n);
2483  }
2484  }
2486 }
2487 
2488 
2490 
2491 
2492 template<typename ChildT, Index Log2Dim>
2493 template<typename OtherInternalNode>
2495 {
2496  using W = typename NodeMaskType::Word;
2497  struct A { inline void operator()(W &tV, const W& sV, const W& tC) const
2498  { tV = (tV | sV) & ~tC; }
2499  };
2500  TopologyUnion(const OtherInternalNode* source, InternalNode* target) : s(source), t(target) {
2501  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2502  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2503 
2504  // Bit processing is done in a single thread!
2505  t->mChildMask |= s->mChildMask;//serial but very fast bitwise post-process
2506  A op;
2507  t->mValueMask.foreach(s->mValueMask, t->mChildMask, op);
2508  assert((t->mValueMask & t->mChildMask).isOff());//no overlapping active tiles or child nodes
2509  }
2510  void operator()(const tbb::blocked_range<Index> &r) const {
2511  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2512  if (s->mChildMask.isOn(i)) {// Loop over other node's child nodes
2513  const typename OtherInternalNode::ChildNodeType& other = *(s->mNodes[i].getChild());
2514  if (t->mChildMask.isOn(i)) {//this has a child node
2515  t->mNodes[i].getChild()->topologyUnion(other);
2516  } else {// this is a tile so replace it with a child branch with identical topology
2517  ChildT* child = new ChildT(other, t->mNodes[i].getValue(), TopologyCopy());
2518  if (t->mValueMask.isOn(i)) child->setValuesOn();//activate all values
2519  t->mNodes[i].setChild(child);
2520  }
2521  } else if (s->mValueMask.isOn(i) && t->mChildMask.isOn(i)) {
2522  t->mNodes[i].getChild()->setValuesOn();
2523  }
2524  }
2525  }
2526  const OtherInternalNode* s;
2528 };// TopologyUnion
2529 
2530 template<typename ChildT, Index Log2Dim>
2531 template<typename OtherChildT>
2532 inline void
2534 {
2536 }
2537 
2538 template<typename ChildT, Index Log2Dim>
2539 template<typename OtherInternalNode>
2540 struct InternalNode<ChildT, Log2Dim>::TopologyIntersection
2541 {
2542  using W = typename NodeMaskType::Word;
2543  struct A { inline void operator()(W &tC, const W& sC, const W& sV, const W& tV) const
2544  { tC = (tC & (sC | sV)) | (tV & sC); }
2545  };
2546  TopologyIntersection(const OtherInternalNode* source, InternalNode* target,
2547  const ValueType& background) : s(source), t(target), b(background) {
2548  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2549  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2550 
2551  // Bit processing is done in a single thread!
2552  A op;
2553  t->mChildMask.foreach(s->mChildMask, s->mValueMask, t->mValueMask, op);
2554 
2555  t->mValueMask &= s->mValueMask;
2556  assert((t->mValueMask & t->mChildMask).isOff());//no overlapping active tiles or child nodes
2557  }
2558  void operator()(const tbb::blocked_range<Index> &r) const {
2559  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2560  if (t->mChildMask.isOn(i)) {// Loop over this node's child nodes
2561  ChildT* child = t->mNodes[i].getChild();
2562  if (s->mChildMask.isOn(i)) {//other also has a child node
2563  child->topologyIntersection(*(s->mNodes[i].getChild()), b);
2564  } else if (s->mValueMask.isOff(i)) {//other is an inactive tile
2565  delete child;//convert child to an inactive tile
2566  t->mNodes[i].setValue(b);
2567  }
2568  } else if (t->mValueMask.isOn(i) && s->mChildMask.isOn(i)) {//active tile -> a branch
2569  t->mNodes[i].setChild(new ChildT(*(s->mNodes[i].getChild()),
2570  t->mNodes[i].getValue(), TopologyCopy()));
2571  }
2572  }
2573  }
2574  const OtherInternalNode* s;
2576  const ValueType& b;
2577 };// TopologyIntersection
2578 
2579 template<typename ChildT, Index Log2Dim>
2580 template<typename OtherChildT>
2581 inline void
2583  const InternalNode<OtherChildT, Log2Dim>& other, const ValueType& background)
2584 {
2585  TopologyIntersection<InternalNode<OtherChildT, Log2Dim> > tmp(&other, this, background);
2586 }
2587 
2588 template<typename ChildT, Index Log2Dim>
2589 template<typename OtherInternalNode>
2590 struct InternalNode<ChildT, Log2Dim>::TopologyDifference
2591 {
2592  using W = typename NodeMaskType::Word;
2593  struct A {inline void operator()(W &tC, const W& sC, const W& sV, const W& tV) const
2594  { tC = (tC & (sC | ~sV)) | (tV & sC); }
2595  };
2596  struct B {inline void operator()(W &tV, const W& sC, const W& sV, const W& tC) const
2597  { tV &= ~((tC & sV) | (sC | sV)); }
2598  };
2599  TopologyDifference(const OtherInternalNode* source, InternalNode* target,
2600  const ValueType& background) : s(source), t(target), b(background) {
2601  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2602  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2603 
2604  // Bit processing is done in a single thread!
2605  const NodeMaskType oldChildMask(t->mChildMask);//important to avoid cross pollution
2606  A op1;
2607  t->mChildMask.foreach(s->mChildMask, s->mValueMask, t->mValueMask, op1);
2608 
2609  B op2;
2610  t->mValueMask.foreach(t->mChildMask, s->mValueMask, oldChildMask, op2);
2611  assert((t->mValueMask & t->mChildMask).isOff());//no overlapping active tiles or child nodes
2612  }
2613  void operator()(const tbb::blocked_range<Index> &r) const {
2614  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2615  if (t->mChildMask.isOn(i)) {// Loop over this node's child nodes
2616  ChildT* child = t->mNodes[i].getChild();
2617  if (s->mChildMask.isOn(i)) {
2618  child->topologyDifference(*(s->mNodes[i].getChild()), b);
2619  } else if (s->mValueMask.isOn(i)) {
2620  delete child;//convert child to an inactive tile
2621  t->mNodes[i].setValue(b);
2622  }
2623  } else if (t->mValueMask.isOn(i)) {//this is an active tile
2624  if (s->mChildMask.isOn(i)) {
2625  const typename OtherInternalNode::ChildNodeType& other =
2626  *(s->mNodes[i].getChild());
2627  ChildT* child = new ChildT(other.origin(), t->mNodes[i].getValue(), true);
2628  child->topologyDifference(other, b);
2629  t->mNodes[i].setChild(child);//replace the active tile with a child branch
2630  }
2631  }
2632  }
2633  }
2634  const OtherInternalNode* s;
2636  const ValueType& b;
2637 };// TopologyDifference
2638 
2639 template<typename ChildT, Index Log2Dim>
2640 template<typename OtherChildT>
2641 inline void
2643  const ValueType& background)
2644 {
2645  TopologyDifference<InternalNode<OtherChildT, Log2Dim> > tmp(&other, this, background);
2646 }
2647 
2648 
2650 
2651 
2652 template<typename ChildT, Index Log2Dim>
2653 template<typename CombineOp>
2654 inline void
2656 {
2657  const ValueType zero = zeroVal<ValueType>();
2658 
2660 
2661  for (Index i = 0; i < NUM_VALUES; ++i) {
2662  if (this->isChildMaskOff(i) && other.isChildMaskOff(i)) {
2663  // Both this node and the other node have constant values (tiles).
2664  // Combine the two values and store the result as this node's new tile value.
2665  op(args.setARef(mNodes[i].getValue())
2666  .setAIsActive(isValueMaskOn(i))
2667  .setBRef(other.mNodes[i].getValue())
2668  .setBIsActive(other.isValueMaskOn(i)));
2669  mNodes[i].setValue(args.result());
2670  mValueMask.set(i, args.resultIsActive());
2671  } else if (this->isChildMaskOn(i) && other.isChildMaskOff(i)) {
2672  // Combine this node's child with the other node's constant value.
2673  ChildNodeType* child = mNodes[i].getChild();
2674  assert(child);
2675  if (child) {
2676  child->combine(other.mNodes[i].getValue(), other.isValueMaskOn(i), op);
2677  }
2678  } else if (this->isChildMaskOff(i) && other.isChildMaskOn(i)) {
2679  // Combine this node's constant value with the other node's child.
2680  ChildNodeType* child = other.mNodes[i].getChild();
2681  assert(child);
2682  if (child) {
2683  // Combine this node's constant value with the other node's child,
2684  // but use a new functor in which the A and B values are swapped,
2685  // since the constant value is the A value, not the B value.
2687  child->combine(mNodes[i].getValue(), isValueMaskOn(i), swappedOp);
2688 
2689  // Steal the other node's child.
2690  other.mChildMask.setOff(i);
2691  other.mNodes[i].setValue(zero);
2692  this->setChildNode(i, child);
2693  }
2694 
2695  } else /*if (isChildMaskOn(i) && other.isChildMaskOn(i))*/ {
2696  // Combine this node's child with the other node's child.
2698  *child = mNodes[i].getChild(),
2699  *otherChild = other.mNodes[i].getChild();
2700  assert(child);
2701  assert(otherChild);
2702  if (child && otherChild) {
2703  child->combine(*otherChild, op);
2704  }
2705  }
2706  }
2707 }
2708 
2709 
2710 template<typename ChildT, Index Log2Dim>
2711 template<typename CombineOp>
2712 inline void
2713 InternalNode<ChildT, Log2Dim>::combine(const ValueType& value, bool valueIsActive, CombineOp& op)
2714 {
2716 
2717  for (Index i = 0; i < NUM_VALUES; ++i) {
2718  if (this->isChildMaskOff(i)) {
2719  // Combine this node's constant value with the given constant value.
2720  op(args.setARef(mNodes[i].getValue())
2721  .setAIsActive(isValueMaskOn(i))
2722  .setBRef(value)
2723  .setBIsActive(valueIsActive));
2724  mNodes[i].setValue(args.result());
2725  mValueMask.set(i, args.resultIsActive());
2726  } else /*if (isChildMaskOn(i))*/ {
2727  // Combine this node's child with the given constant value.
2728  ChildNodeType* child = mNodes[i].getChild();
2729  assert(child);
2730  if (child) child->combine(value, valueIsActive, op);
2731  }
2732  }
2733 }
2734 
2735 
2737 
2738 
2739 template<typename ChildT, Index Log2Dim>
2740 template<typename CombineOp, typename OtherNodeType>
2741 inline void
2742 InternalNode<ChildT, Log2Dim>::combine2(const InternalNode& other0, const OtherNodeType& other1,
2743  CombineOp& op)
2744 {
2746 
2747  for (Index i = 0; i < NUM_VALUES; ++i) {
2748  if (other0.isChildMaskOff(i) && other1.isChildMaskOff(i)) {
2749  op(args.setARef(other0.mNodes[i].getValue())
2750  .setAIsActive(other0.isValueMaskOn(i))
2751  .setBRef(other1.mNodes[i].getValue())
2752  .setBIsActive(other1.isValueMaskOn(i)));
2753  // Replace child i with a constant value.
2754  this->makeChildNodeEmpty(i, args.result());
2755  mValueMask.set(i, args.resultIsActive());
2756  } else {
2757  if (this->isChildMaskOff(i)) {
2758  // Add a new child with the same coordinates, etc. as the other node's child.
2759  const Coord& childOrigin = other0.isChildMaskOn(i)
2760  ? other0.mNodes[i].getChild()->origin()
2761  : other1.mNodes[i].getChild()->origin();
2762  this->setChildNode(i, new ChildNodeType(childOrigin, mNodes[i].getValue()));
2763  }
2764 
2765  if (other0.isChildMaskOff(i)) {
2766  // Combine node1's child with node0's constant value
2767  // and write the result into child i.
2768  mNodes[i].getChild()->combine2(other0.mNodes[i].getValue(),
2769  *other1.mNodes[i].getChild(), other0.isValueMaskOn(i), op);
2770  } else if (other1.isChildMaskOff(i)) {
2771  // Combine node0's child with node1's constant value
2772  // and write the result into child i.
2773  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2774  other1.mNodes[i].getValue(), other1.isValueMaskOn(i), op);
2775  } else {
2776  // Combine node0's child with node1's child
2777  // and write the result into child i.
2778  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2779  *other1.mNodes[i].getChild(), op);
2780  }
2781  }
2782  }
2783 }
2784 
2785 
2786 template<typename ChildT, Index Log2Dim>
2787 template<typename CombineOp, typename OtherNodeType>
2788 inline void
2789 InternalNode<ChildT, Log2Dim>::combine2(const ValueType& value, const OtherNodeType& other,
2790  bool valueIsActive, CombineOp& op)
2791 {
2793 
2794  for (Index i = 0; i < NUM_VALUES; ++i) {
2795  if (other.isChildMaskOff(i)) {
2796  op(args.setARef(value)
2797  .setAIsActive(valueIsActive)
2798  .setBRef(other.mNodes[i].getValue())
2799  .setBIsActive(other.isValueMaskOn(i)));
2800  // Replace child i with a constant value.
2801  this->makeChildNodeEmpty(i, args.result());
2802  mValueMask.set(i, args.resultIsActive());
2803  } else {
2804  typename OtherNodeType::ChildNodeType* otherChild = other.mNodes[i].getChild();
2805  assert(otherChild);
2806  if (this->isChildMaskOff(i)) {
2807  // Add a new child with the same coordinates, etc.
2808  // as the other node's child.
2809  this->setChildNode(i, new ChildNodeType(*otherChild));
2810  }
2811  // Combine the other node's child with a constant value
2812  // and write the result into child i.
2813  mNodes[i].getChild()->combine2(value, *otherChild, valueIsActive, op);
2814  }
2815  }
2816 }
2817 
2818 
2819 template<typename ChildT, Index Log2Dim>
2820 template<typename CombineOp, typename OtherValueType>
2821 inline void
2822 InternalNode<ChildT, Log2Dim>::combine2(const InternalNode& other, const OtherValueType& value,
2823  bool valueIsActive, CombineOp& op)
2824 {
2826 
2827  for (Index i = 0; i < NUM_VALUES; ++i) {
2828  if (other.isChildMaskOff(i)) {
2829  op(args.setARef(other.mNodes[i].getValue())
2830  .setAIsActive(other.isValueMaskOn(i))
2831  .setBRef(value)
2832  .setBIsActive(valueIsActive));
2833  // Replace child i with a constant value.
2834  this->makeChildNodeEmpty(i, args.result());
2835  mValueMask.set(i, args.resultIsActive());
2836  } else {
2837  ChildNodeType* otherChild = other.mNodes[i].getChild();
2838  assert(otherChild);
2839  if (this->isChildMaskOff(i)) {
2840  // Add a new child with the same coordinates, etc. as the other node's child.
2841  this->setChildNode(i,
2842  new ChildNodeType(otherChild->origin(), mNodes[i].getValue()));
2843  }
2844  // Combine the other node's child with a constant value
2845  // and write the result into child i.
2846  mNodes[i].getChild()->combine2(*otherChild, value, valueIsActive, op);
2847  }
2848  }
2849 }
2850 
2851 
2853 
2854 
2855 template<typename ChildT, Index Log2Dim>
2856 template<typename BBoxOp>
2857 inline void
2859 {
2860  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) {
2861 #ifdef _MSC_VER
2862  op.operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
2863 #else
2864  op.template operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
2865 #endif
2866  }
2867  if (op.template descent<LEVEL>()) {
2868  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) i->visitActiveBBox(op);
2869  } else {
2870  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) {
2871 #ifdef _MSC_VER
2872  op.operator()<LEVEL>(i->getNodeBoundingBox());
2873 #else
2874  op.template operator()<LEVEL>(i->getNodeBoundingBox());
2875 #endif
2876  }
2877  }
2878 }
2879 
2880 
2881 template<typename ChildT, Index Log2Dim>
2882 template<typename VisitorOp>
2883 inline void
2885 {
2886  doVisit<InternalNode, VisitorOp, ChildAllIter>(*this, op);
2887 }
2888 
2889 
2890 template<typename ChildT, Index Log2Dim>
2891 template<typename VisitorOp>
2892 inline void
2894 {
2895  doVisit<const InternalNode, VisitorOp, ChildAllCIter>(*this, op);
2896 }
2897 
2898 
2899 template<typename ChildT, Index Log2Dim>
2900 template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
2901 inline void
2902 InternalNode<ChildT, Log2Dim>::doVisit(NodeT& self, VisitorOp& op)
2903 {
2904  typename NodeT::ValueType val;
2905  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2906  if (op(iter)) continue;
2907  if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
2908  child->visit(op);
2909  }
2910  }
2911 }
2912 
2913 
2915 
2916 
2917 template<typename ChildT, Index Log2Dim>
2918 template<typename OtherNodeType, typename VisitorOp>
2919 inline void
2920 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op)
2921 {
2922  doVisit2Node<InternalNode, OtherNodeType, VisitorOp, ChildAllIter,
2923  typename OtherNodeType::ChildAllIter>(*this, other, op);
2924 }
2925 
2926 
2927 template<typename ChildT, Index Log2Dim>
2928 template<typename OtherNodeType, typename VisitorOp>
2929 inline void
2930 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op) const
2931 {
2932  doVisit2Node<const InternalNode, OtherNodeType, VisitorOp, ChildAllCIter,
2933  typename OtherNodeType::ChildAllCIter>(*this, other, op);
2934 }
2935 
2936 
2937 template<typename ChildT, Index Log2Dim>
2938 template<
2939  typename NodeT,
2940  typename OtherNodeT,
2941  typename VisitorOp,
2942  typename ChildAllIterT,
2943  typename OtherChildAllIterT>
2944 inline void
2945 InternalNode<ChildT, Log2Dim>::doVisit2Node(NodeT& self, OtherNodeT& other, VisitorOp& op)
2946 {
2947  // Allow the two nodes to have different ValueTypes, but not different dimensions.
2948  static_assert(OtherNodeT::NUM_VALUES == NodeT::NUM_VALUES,
2949  "visit2() requires nodes to have the same dimensions");
2950  static_assert(OtherNodeT::LEVEL == NodeT::LEVEL,
2951  "visit2() requires nodes to be at the same tree level");
2952 
2953  typename NodeT::ValueType val;
2954  typename OtherNodeT::ValueType otherVal;
2955 
2956  ChildAllIterT iter = self.beginChildAll();
2957  OtherChildAllIterT otherIter = other.beginChildAll();
2958 
2959  for ( ; iter && otherIter; ++iter, ++otherIter)
2960  {
2961  const size_t skipBranch = static_cast<size_t>(op(iter, otherIter));
2962 
2963  typename ChildAllIterT::ChildNodeType* child =
2964  (skipBranch & 1U) ? nullptr : iter.probeChild(val);
2965  typename OtherChildAllIterT::ChildNodeType* otherChild =
2966  (skipBranch & 2U) ? nullptr : otherIter.probeChild(otherVal);
2967 
2968  if (child != nullptr && otherChild != nullptr) {
2969  child->visit2Node(*otherChild, op);
2970  } else if (child != nullptr) {
2971  child->visit2(otherIter, op);
2972  } else if (otherChild != nullptr) {
2973  otherChild->visit2(iter, op, /*otherIsLHS=*/true);
2974  }
2975  }
2976 }
2977 
2978 
2980 
2981 
2982 template<typename ChildT, Index Log2Dim>
2983 template<typename OtherChildAllIterType, typename VisitorOp>
2984 inline void
2985 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
2986  VisitorOp& op, bool otherIsLHS)
2987 {
2988  doVisit2<InternalNode, VisitorOp, ChildAllIter, OtherChildAllIterType>(
2989  *this, otherIter, op, otherIsLHS);
2990 }
2991 
2992 
2993 template<typename ChildT, Index Log2Dim>
2994 template<typename OtherChildAllIterType, typename VisitorOp>
2995 inline void
2996 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
2997  VisitorOp& op, bool otherIsLHS) const
2998 {
2999  doVisit2<const InternalNode, VisitorOp, ChildAllCIter, OtherChildAllIterType>(
3000  *this, otherIter, op, otherIsLHS);
3001 }
3002 
3003 
3004 template<typename ChildT, Index Log2Dim>
3005 template<typename NodeT, typename VisitorOp, typename ChildAllIterT, typename OtherChildAllIterT>
3006 inline void
3007 InternalNode<ChildT, Log2Dim>::doVisit2(NodeT& self, OtherChildAllIterT& otherIter,
3008  VisitorOp& op, bool otherIsLHS)
3009 {
3010  if (!otherIter) return;
3011 
3012  const size_t skipBitMask = (otherIsLHS ? 2U : 1U);
3013 
3014  typename NodeT::ValueType val;
3015  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
3016  const size_t skipBranch = static_cast<size_t>(
3017  otherIsLHS ? op(otherIter, iter) : op(iter, otherIter));
3018 
3019  typename ChildAllIterT::ChildNodeType* child =
3020  (skipBranch & skipBitMask) ? nullptr : iter.probeChild(val);
3021 
3022  if (child != nullptr) child->visit2(otherIter, op, otherIsLHS);
3023  }
3024 }
3025 
3026 
3028 
3029 
3030 template<typename ChildT, Index Log2Dim>
3031 inline void
3032 InternalNode<ChildT, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
3033 {
3034  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
3035  iter->writeBuffers(os, toHalf);
3036  }
3037 }
3038 
3039 
3040 template<typename ChildT, Index Log2Dim>
3041 inline void
3042 InternalNode<ChildT, Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
3043 {
3044  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
3045  iter->readBuffers(is, fromHalf);
3046  }
3047 }
3048 
3049 
3050 template<typename ChildT, Index Log2Dim>
3051 inline void
3053  const CoordBBox& clipBBox, bool fromHalf)
3054 {
3055  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
3056  // Stream in the branch rooted at this child.
3057  // (We can't skip over children that lie outside the clipping region,
3058  // because buffers are serialized in depth-first order and need to be
3059  // unserialized in the same order.)
3060  iter->readBuffers(is, clipBBox, fromHalf);
3061  }
3062 
3063  // Get this tree's background value.
3064  ValueType background = zeroVal<ValueType>();
3065  if (const void* bgPtr = io::getGridBackgroundValuePtr(is)) {
3066  background = *static_cast<const ValueType*>(bgPtr);
3067  }
3068  this->clip(clipBBox, background);
3069 }
3070 
3071 
3073 
3074 
3075 template<typename ChildT, Index Log2Dim>
3076 void
3078 {
3079  dims.push_back(Log2Dim);
3080  ChildNodeType::getNodeLog2Dims(dims);
3081 }
3082 
3083 
3084 template<typename ChildT, Index Log2Dim>
3085 inline void
3087 {
3088  assert(n<(1<<3*Log2Dim));
3089  xyz.setX(n >> 2*Log2Dim);
3090  n &= ((1<<2*Log2Dim)-1);
3091  xyz.setY(n >> Log2Dim);
3092  xyz.setZ(n & ((1<<Log2Dim)-1));
3093 }
3094 
3095 
3096 template<typename ChildT, Index Log2Dim>
3097 inline Index
3099 {
3100  return (((xyz[0] & (DIM-1u)) >> ChildNodeType::TOTAL) << 2*Log2Dim)
3101  + (((xyz[1] & (DIM-1u)) >> ChildNodeType::TOTAL) << Log2Dim)
3102  + ((xyz[2] & (DIM-1u)) >> ChildNodeType::TOTAL);
3103 }
3104 
3105 
3106 template<typename ChildT, Index Log2Dim>
3107 inline Coord
3109 {
3110  Coord local;
3111  this->offsetToLocalCoord(n, local);
3112  local <<= ChildT::TOTAL;
3113  return local + this->origin();
3114 }
3115 
3116 
3118 
3119 
3120 template<typename ChildT, Index Log2Dim>
3121 template<typename ArrayT>
3122 inline void
3124 {
3125  using T = typename ArrayT::value_type;
3126  static_assert(std::is_pointer<T>::value, "argument to getNodes() must be a pointer array");
3127  using ArrayChildT = typename std::conditional<
3128  std::is_const<typename std::remove_pointer<T>::type>::value, const ChildT, ChildT>::type;
3129  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
3131  if (std::is_same<T, ArrayChildT*>::value) {
3132  array.push_back(reinterpret_cast<T>(mNodes[iter.pos()].getChild()));
3133  } else {
3134  iter->getNodes(array);//descent
3135  }
3137  }
3138 }
3139 
3140 template<typename ChildT, Index Log2Dim>
3141 template<typename ArrayT>
3142 inline void
3144 {
3145  using T = typename ArrayT::value_type;
3146  static_assert(std::is_pointer<T>::value, "argument to getNodes() must be a pointer array");
3147  static_assert(std::is_const<typename std::remove_pointer<T>::type>::value,
3148  "argument to getNodes() must be an array of const node pointers");
3149  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
3151  if (std::is_same<T, const ChildT*>::value) {
3152  array.push_back(reinterpret_cast<T>(mNodes[iter.pos()].getChild()));
3153  } else {
3154  iter->getNodes(array);//descent
3155  }
3157  }
3158 }
3159 
3160 
3162 
3163 
3164 template<typename ChildT, Index Log2Dim>
3165 template<typename ArrayT>
3166 inline void
3167 InternalNode<ChildT, Log2Dim>::stealNodes(ArrayT& array, const ValueType& value, bool state)
3168 {
3169  using T = typename ArrayT::value_type;
3170  static_assert(std::is_pointer<T>::value, "argument to stealNodes() must be a pointer array");
3171  using ArrayChildT = typename std::conditional<
3172  std::is_const<typename std::remove_pointer<T>::type>::value, const ChildT, ChildT>::type;
3174  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
3175  const Index n = iter.pos();
3176  if (std::is_same<T, ArrayChildT*>::value) {
3177  array.push_back(reinterpret_cast<T>(mNodes[n].getChild()));
3178  mValueMask.set(n, state);
3179  mNodes[n].setValue(value);
3180  } else {
3181  iter->stealNodes(array, value, state);//descent
3182  }
3183  }
3184  if (std::is_same<T, ArrayChildT*>::value) mChildMask.setOff();
3186 }
3187 
3188 
3190 
3191 
3192 template<typename ChildT, Index Log2Dim>
3193 inline void
3195  const ValueType& newBackground)
3196 {
3197  if (math::isExactlyEqual(oldBackground, newBackground)) return;
3198  for (Index i = 0; i < NUM_VALUES; ++i) {
3199  if (this->isChildMaskOn(i)) {
3200  mNodes[i].getChild()->resetBackground(oldBackground, newBackground);
3201  } else if (this->isValueMaskOff(i)) {
3202  if (math::isApproxEqual(mNodes[i].getValue(), oldBackground)) {
3203  mNodes[i].setValue(newBackground);
3204  } else if (math::isApproxEqual(mNodes[i].getValue(), math::negative(oldBackground))) {
3205  mNodes[i].setValue(math::negative(newBackground));
3206  }
3207  }
3208  }
3209 }
3210 
3211 template<typename ChildT, Index Log2Dim>
3212 template<typename OtherChildNodeType, Index OtherLog2Dim>
3213 inline bool
3216 {
3217  if (Log2Dim != OtherLog2Dim || mChildMask != other->mChildMask ||
3218  mValueMask != other->mValueMask) return false;
3219  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
3220  if (!iter->hasSameTopology(other->mNodes[iter.pos()].getChild())) return false;
3221  }
3222  return true;
3223 }
3224 
3225 
3226 template<typename ChildT, Index Log2Dim>
3227 inline void
3229 {
3230  assert(child);
3231  if (this->isChildMaskOn(i)) {
3232  delete mNodes[i].getChild();
3233  } else {
3234  mChildMask.setOn(i);
3235  mValueMask.setOff(i);
3236  }
3237  mNodes[i].setChild(child);
3238 }
3239 
3240 template<typename ChildT, Index Log2Dim>
3241 inline void
3243 {
3244  assert(child);
3245  assert(mChildMask.isOff(i));
3246  mChildMask.setOn(i);
3247  mValueMask.setOff(i);
3248  mNodes[i].setChild(child);
3249 }
3250 
3251 
3252 template<typename ChildT, Index Log2Dim>
3253 inline ChildT*
3255 {
3256  if (this->isChildMaskOff(i)) {
3257  mNodes[i].setValue(value);
3258  return nullptr;
3259  }
3260  ChildNodeType* child = mNodes[i].getChild();
3261  mChildMask.setOff(i);
3262  mNodes[i].setValue(value);
3263  return child;
3264 }
3265 
3266 
3267 template<typename ChildT, Index Log2Dim>
3268 inline void
3270 {
3271  delete this->unsetChildNode(n, value);
3272 }
3273 
3274 template<typename ChildT, Index Log2Dim>
3275 inline ChildT*
3277 {
3278  assert(this->isChildMaskOn(n));
3279  return mNodes[n].getChild();
3280 }
3281 
3282 
3283 template<typename ChildT, Index Log2Dim>
3284 inline const ChildT*
3286 {
3287  assert(this->isChildMaskOn(n));
3288  return mNodes[n].getChild();
3289 }
3290 
3291 } // namespace tree
3292 } // namespace OPENVDB_VERSION_NAME
3293 } // namespace openvdb
3294 
3295 #endif // OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:489
static void doVisit(NodeT &, VisitorOp &)
Definition: InternalNode.h:2902
Base class for sparse iterators over internal and leaf nodes.
Definition: Iterator.h:114
DenseIter< InternalNode, ChildNodeType, ValueType, ChildAll > ChildAllIter
Definition: InternalNode.h:214
void resetBackground(const ValueType &oldBackground, const ValueType &newBackground)
Change inactive tiles or voxels with value oldBackground to newBackground or -oldBackground to -newBa...
Definition: InternalNode.h:3194
void topologyUnion(const InternalNode< OtherChildNodeType, Log2Dim > &other)
Union this branch&#39;s set of active values with the other branch&#39;s active values. The value type of the...
ValueIter()
Definition: InternalNode.h:155
ChildAllCIter beginChildAll() const
Definition: InternalNode.h:229
void addLeaf(LeafNodeType *leaf)
Add the specified leaf to this node, possibly creating a child branch in the process. If the leaf node already exists, replace it.
Definition: InternalNode.h:1312
ValueOnCIter cbeginValueOn() const
Definition: InternalNode.h:234
Definition: InternalNode.h:33
InternalNode * t
Definition: InternalNode.h:898
ChildIter()
Definition: InternalNode.h:134
ChildNodeType * getChildNode(Index n)
Returns a pointer to the child node at the linear offset n.
Definition: InternalNode.h:3276
void setValuesOn()
Mark all values (both tiles and voxels) as active.
Definition: InternalNode.h:1858
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition: InternalNode.h:3032
typename NodeMaskType::Word W
Definition: InternalNode.h:2542
void operator()(W &tV, const W &sC, const W &sV, const W &tC) const
Definition: InternalNode.h:2596
bool isChildMaskOff() const
Definition: InternalNode.h:767
typename NodeMaskType::DenseIterator MaskDenseIterator
Definition: InternalNode.h:120
ChildIter(const MaskIterT &iter, NodeT *parent)
Definition: InternalNode.h:135
bool isApproxEqual(const Type &a, const Type &b)
Return true if a is equal to b to within the default floating-point comparison tolerance.
Definition: Math.h:351
TopologyCopy2(const OtherInternalNode *source, InternalNode *target, const ValueType &offValue, const ValueType &onValue)
Definition: InternalNode.h:964
const NodeMaskType & getChildMask() const
Definition: InternalNode.h:769
Index32 countOn() const
Return the total number of on bits.
Definition: NodeMasks.h:424
Definition: Types.h:507
Base class for iterators over internal and leaf nodes.
Definition: Iterator.h:29
Definition: Types.h:506
static const Index NUM_VALUES
Definition: InternalNode.h:47
void merge(InternalNode &other, const ValueType &background, const ValueType &otherBackground)
Efficiently merge another tree into this tree using one of several schemes.
Definition: InternalNode.h:2355
bool addChild(ChildNodeType *child)
Add the given child node at this level deducing the offset from it&#39;s origin. If a child node with thi...
Definition: InternalNode.h:1374
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
const LeafNodeType * probeConstLeafAndCache(const Coord &xyz, AccessorT &acc) const
Same as probeLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
const NodeType * probeConstNode(const Coord &xyz) const
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return nullptr.
void visit2(IterT &otherIter, VisitorOp &, bool otherIsLHS=false)
Definition: InternalNode.h:29
InternalNode * t
Definition: InternalNode.h:2635
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: InternalNode.h:1164
static Index getChildDim()
Definition: InternalNode.h:260
bool isEmpty() const
Definition: InternalNode.h:298
const OtherInternalNode * s
Definition: InternalNode.h:979
bool resultIsActive() const
Definition: Types.h:631
uint32_t Index32
Definition: Types.h:29
Base class for dense iterators over internal and leaf nodes.
Definition: Iterator.h:178
void setValue(const ValueT &val)
Definition: NodeUnion.h:47
InternalNode * mNode
Definition: InternalNode.h:2329
Definition: InternalNode.h:124
Index getValueLevel(const Coord &xyz) const
Return the level of the tree (0 = leaf) at which the value at the given coordinates resides...
Definition: InternalNode.h:1607
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: InternalNode.h:1778
void setItem(Index pos, ChildT *child) const
Definition: InternalNode.h:196
ChildT & getItem(Index pos) const
Definition: InternalNode.h:138
Definition: InternalNode.h:123
Definition: InternalNode.h:123
const OtherInternalNode * s
Definition: InternalNode.h:2574
ValueOffCIter beginValueOff() const
Definition: InternalNode.h:240
bool getItem(Index pos, ChildT *&child, NonConstValueT &value) const
Definition: InternalNode.h:184
Definition: NodeMasks.h:251
typename ChildNodeType::BuildType BuildType
Definition: InternalNode.h:39
UnionType mNodes[NUM_VALUES]
Definition: InternalNode.h:817
ValueOnIter beginValueOn()
Definition: InternalNode.h:242
ChildAllCIter cbeginChildAll() const
Definition: InternalNode.h:226
const AValueType & result() const
Get the output value.
Definition: Types.h:612
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition: InternalNode.h:1835
static Index dim()
Definition: InternalNode.h:250
void operator()(W &tC, const W &sC, const W &sV, const W &tV) const
Definition: InternalNode.h:2593
const UnionType * getTable() const
Definition: InternalNode.h:777
typename NodeMaskType::Word W
Definition: InternalNode.h:2592
TopologyIntersection(const OtherInternalNode *source, InternalNode *target, const ValueType &background)
Definition: InternalNode.h:2546
CombineArgs & setARef(const AValueType &a)
Redirect the A value to a new external source.
Definition: Types.h:620
static const Index LEVEL
Definition: InternalNode.h:48
ChildOffCIter cbeginChildOff() const
Definition: InternalNode.h:225
bool isChildMaskOff(Index n) const
Definition: InternalNode.h:766
bool isValueMaskOn(Index n) const
Definition: InternalNode.h:761
ValueConverter<T>::Type is the type of an InternalNode having the same child hierarchy and dimensions...
Definition: InternalNode.h:55
static void offsetToLocalCoord(Index n, Coord &xyz)
Return the local coordinates for a linear table offset, where offset 0 has coordinates (0...
Definition: InternalNode.h:3086
bool isValueOn(const Coord &xyz) const
Return true if the voxel at the given coordinates is active.
Definition: InternalNode.h:1563
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Definition: NodeMasks.h:288
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: InternalNode.h:3167
Definition: InternalNode.h:124
void setChild(ChildT *child)
Definition: NodeUnion.h:43
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:81
Definition: InternalNode.h:131
void operator()(const tbb::blocked_range< Index > &r) const
Definition: InternalNode.h:2558
ValueIter(const MaskIterT &iter, NodeT *parent)
Definition: InternalNode.h:156
void topologyIntersection(const InternalNode< OtherChildNodeType, Log2Dim > &other, const ValueType &background)
Intersects this tree&#39;s set of active values with the active values of the other tree, whose ValueType may be different.
bool isValueMaskOff() const
Definition: InternalNode.h:764
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Add a tile at the specified tree level that contains voxel (x, y, z), possibly creating a parent bran...
Definition: InternalNode.h:1400
void readBuffers(std::istream &, bool fromHalf=false)
Definition: InternalNode.h:3042
const NodeMaskType & getValueMask() const
Definition: InternalNode.h:768
bool hasSameTopology(const InternalNode< OtherChildNodeType, OtherLog2Dim > *other) const
Return true if the given tree branch has the same node and active value topology as this tree branch ...
Definition: InternalNode.h:3214
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: InternalNode.h:1932
const ValueT & getItem(Index pos) const
Definition: InternalNode.h:159
void readCompressedValues(std::istream &is, ValueT *destBuf, Index destCount, const MaskT &valueMask, bool fromHalf)
Definition: Compression.h:465
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:433
InternalNode * t
Definition: InternalNode.h:944
void readTopology(std::istream &, bool fromHalf=false)
Definition: InternalNode.h:2210
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
Index32 leafCount() const
Definition: InternalNode.h:1013
const ValueType & getFirstValue() const
If the first entry in this node&#39;s table is a tile, return the tile&#39;s value. Otherwise, return the result of calling getFirstValue() on the child.
Definition: InternalNode.h:2270
void save(std::ostream &os) const
Definition: NodeMasks.h:546
ChildAllIter beginChildAll()
Definition: InternalNode.h:232
ValueAllCIter beginValueAll() const
Definition: InternalNode.h:241
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:438
NodeMaskType mValueMask
Definition: InternalNode.h:821
Index64 onLeafVoxelCount() const
Definition: InternalNode.h:1075
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1709
void writeTopology(std::ostream &, bool toHalf=false) const
Definition: InternalNode.h:2185
void modifyItem(Index pos, const ModifyOp &op) const
Definition: InternalNode.h:166
bool probeValue(const Coord &xyz, ValueType &value) const
Definition: InternalNode.h:1629
Definition: InternalNode.h:123
bool isValueMaskOff(Index n) const
Definition: InternalNode.h:763
static Index coordToOffset(const Coord &xyz)
Return the linear table offset of the given global or local coordinates.
Definition: InternalNode.h:3098
Index32 countOff() const
Return the total number of on bits.
Definition: NodeMasks.h:431
static const Index DIM
Definition: InternalNode.h:46
void copyToDense(const CoordBBox &bbox, DenseT &dense) const
Copy into a dense grid the values of the voxels that lie within a given bounding box.
Definition: InternalNode.h:2140
Index64 offLeafVoxelCount() const
Definition: InternalNode.h:1087
static Index32 memUsage()
Return the byte size of this NodeMask.
Definition: NodeMasks.h:422
ValueAllCIter cbeginValueAll() const
Definition: InternalNode.h:237
void voxelizeActiveTiles(bool threaded=true)
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition: InternalNode.h:2334
typename BaseT::NonConstValueType NonConstValueT
Definition: InternalNode.h:178
void unsetItem(Index pos, const ValueT &value) const
Definition: InternalNode.h:202
ChildOnCIter beginChildOn() const
Definition: InternalNode.h:227
void addLeafAndCache(LeafNodeType *leaf, AccessorT &)
Same as addLeaf() except, if necessary, update the accessor with pointers to the nodes along the path...
Definition: InternalNode.h:1341
Coord mOrigin
Global grid index coordinates (x,y,z) of the local origin of this node.
Definition: InternalNode.h:823
InternalNode * t
Definition: InternalNode.h:2575
ValueAllIter beginValueAll()
Definition: InternalNode.h:245
Coord offsetToGlobalCoord(Index n) const
Return the global coordinates for a linear table offset.
Definition: InternalNode.h:3108
const ValueType & onV
Definition: InternalNode.h:981
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:102
DenseIter< const InternalNode, const ChildNodeType, ValueType, ChildAll > ChildAllCIter
Definition: InternalNode.h:215
void evalActiveBoundingBox(CoordBBox &bbox, bool visitVoxels=true) const
Expand the specified bounding box so that it includes the active tiles of this internal node as well ...
Definition: InternalNode.h:1122
NodeMaskType getValueOffMask() const
Definition: InternalNode.h:770
int32_t Int32
Definition: Types.h:33
static void doVisit2Node(NodeT &, OtherNodeT &, VisitorOp &)
Definition: InternalNode.h:2945
const ValueType & getValue(const Coord &xyz) const
Definition: InternalNode.h:1584
Definition: InternalNode.h:152
void set(Index32 n, bool On)
Set the nth bit to the specified state.
Definition: NodeMasks.h:443
ChildOnCIter cbeginChildOn() const
Definition: InternalNode.h:224
typename ChildNodeType::ValueType ValueType
Definition: InternalNode.h:38
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: InternalNode.h:1140
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: InternalNode.h:1266
void operator()(const tbb::blocked_range< Index > &r) const
Definition: InternalNode.h:969
NodeType * probeNodeAndCache(const Coord &xyz, AccessorT &)
Same as probeNode() except, if necessary, update the accessor with pointers to the nodes along the pa...
NodeUnion< ValueType, ChildNodeType > UnionType
Definition: InternalNode.h:40
DeepCopy(const OtherInternalNode *source, InternalNode *target)
Definition: InternalNode.h:884
void operator()(const tbb::blocked_range< Index > &r) const
Definition: InternalNode.h:2510
Index64 onVoxelCount() const
Definition: InternalNode.h:1051
ChildNodeType * unsetChildNode(Index i, const ValueType &value)
Definition: InternalNode.h:3254
typename std::remove_const< UnsetItemT >::type NonConstValueType
Definition: Iterator.h:184
void combine2(const InternalNode &other0, const OtherNodeType &other1, CombineOp &)
Definition: InternalNode.h:2742
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
void addTileAndCache(Index level, const Coord &xyz, const ValueType &, bool state, AccessorT &)
Same as addTile() except, if necessary, update the accessor with pointers to the nodes along the path...
Definition: InternalNode.h:1432
Definition: Exceptions.h:13
typename ChildNodeType::LeafNodeType LeafNodeType
Definition: InternalNode.h:37
void setItem(Index pos, const ValueT &v) const
Definition: InternalNode.h:162
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
SIMD Intrinsic Headers.
Definition: Platform.h:114
Definition: InternalNode.h:124
void setOrigin(const Coord &origin)
Set the grid index coordinates of this node&#39;s local origin.
Definition: InternalNode.h:273
void visit2Node(OtherNodeType &other, VisitorOp &)
Definition: InternalNode.h:2920
void operator()(const tbb::blocked_range< Index > &r) const
Definition: InternalNode.h:2316
TopologyDifference(const OtherInternalNode *source, InternalNode *target, const ValueType &background)
Definition: InternalNode.h:2599
bool isOn(Index32 n) const
Return true if the nth bit is on.
Definition: NodeMasks.h:483
void combine(InternalNode &other, CombineOp &)
Definition: InternalNode.h:2655
typename NodeMaskType::OffIterator MaskOffIterator
Definition: InternalNode.h:119
void operator()(W &tC, const W &sC, const W &sV, const W &tV) const
Definition: InternalNode.h:2543
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition: InternalNode.h:1109
Index32 nonLeafCount() const
Definition: InternalNode.h:1038
void clip(const CoordBBox &, const ValueType &background)
Set all voxels that lie outside the given axis-aligned box to the background.
Definition: InternalNode.h:1986
void operator()(const tbb::blocked_range< Index > &r) const
Definition: InternalNode.h:933
Definition: NodeMasks.h:220
DenseIter()
Definition: InternalNode.h:180
typename NodeMaskType::OnIterator MaskOnIterator
Definition: InternalNode.h:118
const ValueType & b
Definition: InternalNode.h:945
SameConfiguration<OtherNodeType>::value is true if and only if OtherNodeType is the type of an Intern...
Definition: InternalNode.h:64
const ValueType & getLastValue() const
If the last entry in this node&#39;s table is a tile, return the tile&#39;s value. Otherwise, return the result of calling getLastValue() on the child.
Definition: InternalNode.h:2278
ChildT * getChild() const
Definition: NodeUnion.h:42
void makeChildNodeEmpty(Index n, const ValueType &value)
Definition: InternalNode.h:3269
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:681
Library and file format version numbers.
void operator()(const tbb::blocked_range< Index > &r) const
Definition: InternalNode.h:888
const OtherInternalNode * s
Definition: InternalNode.h:2634
void setChildNode(Index i, ChildNodeType *child)
Definition: InternalNode.h:3242
void writeCompressedValues(std::ostream &os, ValueT *srcBuf, Index srcCount, const MaskT &valueMask, const MaskT &childMask, bool toHalf)
Definition: Compression.h:645
void operator()(W &tV, const W &sV, const W &tC) const
Definition: InternalNode.h:2497
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1754
void setItem(Index pos, const ChildT &c) const
Definition: InternalNode.h:145
InternalNode()
Default constructor.
Definition: InternalNode.h:72
const Coord & origin() const
Return the grid index coordinates of this node&#39;s local origin.
Definition: InternalNode.h:271
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don&#39;t change its value.
Definition: InternalNode.h:1673
static void getNodeLog2Dims(std::vector< Index > &dims)
Populated an stil::vector with the dimension of all the nodes in the branch starting with this node...
Definition: InternalNode.h:3077
Index32 Index
Definition: Types.h:31
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:115
OPENVDB_API uint32_t getFormatVersion(std::ios_base &)
Return the file format version number associated with the given input stream.
NodeType * probeNode(const Coord &xyz)
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return nullptr.
static void doVisit2(NodeT &, OtherChildAllIterT &, VisitorOp &, bool otherIsLHS)
Definition: InternalNode.h:3007
~InternalNode()
Definition: InternalNode.h:1000
bool hasActiveTiles() const
Return true if this node or any of its child nodes have any active tiles.
Definition: InternalNode.h:1548
Index64 Word
Definition: NodeMasks.h:297
ChildOnIter beginChildOn()
Definition: InternalNode.h:230
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: InternalNode.h:1292
Definition: InternalNode.h:812
TopologyUnion(const OtherInternalNode *source, InternalNode *target)
Definition: InternalNode.h:2500
bool isChildMaskOn(Index n) const
Definition: InternalNode.h:765
void operator()(const tbb::blocked_range< Index > &r) const
Definition: InternalNode.h:2613
InternalNode * t
Definition: InternalNode.h:2527
void resetChildNode(Index i, ChildNodeType *child)
Definition: InternalNode.h:3228
CoordBBox getNodeBoundingBox() const
Return the bounding box of this node, i.e., the full index space spanned by the node regardless of it...
Definition: InternalNode.h:295
void modifyValueAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: InternalNode.h:1898
const ValueType & b
Definition: InternalNode.h:2576
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:102
InternalNode * t
Definition: InternalNode.h:980
ValueOffIter beginValueOff()
Definition: InternalNode.h:244
Definition: Types.h:658
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &)
Same as touchLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
const NodeType * probeConstNodeAndCache(const Coord &xyz, AccessorT &) const
Same as probeNode() except, if necessary, update the accessor with pointers to the nodes along the pa...
void negate()
Change the sign of all the values represented in this node and its child nodes.
Definition: InternalNode.h:2290
Tag dispatch class that distinguishes constructors during file input.
Definition: Types.h:683
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition: InternalNode.h:1642
_ChildNodeType ChildNodeType
Definition: InternalNode.h:36
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: InternalNode.h:1816
ChildOffCIter beginChildOff() const
Definition: InternalNode.h:228
uint64_t Index64
Definition: Types.h:30
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition: InternalNode.h:1573
VoxelizeActiveTiles(InternalNode &node)
Definition: InternalNode.h:2309
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition: Math.h:388
const ValueT & getValue() const
Definition: NodeUnion.h:45
TopologyCopy1(const OtherInternalNode *source, InternalNode *target, const ValueType &background)
Definition: InternalNode.h:928
ValueOnCIter beginValueOn() const
Definition: InternalNode.h:238
const OtherInternalNode * s
Definition: InternalNode.h:897
Definition: InternalNode.h:174
void visitActiveBBox(BBoxOp &) const
Calls the templated functor BBoxOp with bounding box information for all active tiles and leaf nodes ...
Definition: InternalNode.h:2858
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:154
ValueOffCIter cbeginValueOff() const
Definition: InternalNode.h:236
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:567
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
const OtherInternalNode * s
Definition: InternalNode.h:2526
const ValueType & b
Definition: InternalNode.h:2636
bool isConstant(ValueType &firstValue, bool &state, const ValueType &tolerance=zeroVal< ValueType >()) const
Definition: InternalNode.h:1501
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
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: InternalNode.h:1870
bool isValueMaskOn() const
Definition: InternalNode.h:762
NodeMaskType mChildMask
Definition: InternalNode.h:821
static Index getLevel()
Definition: InternalNode.h:253
Index64 onTileCount() const
Definition: InternalNode.h:1098
bool isValueOn(Index offset) const
Return true if the voxel at the given offset is active.
Definition: InternalNode.h:331
Level getLevel()
Return the current logging level.
Definition: logging.h:138
bool isInactive() const
Return true if this node has no children and only contains inactive values.
Definition: InternalNode.h:326
DenseIter(const MaskDenseIterator &iter, NodeT *parent)
Definition: InternalNode.h:181
void load(std::istream &is)
Definition: NodeMasks.h:550
ValueType combine(const ValueType &v0, const ValueType &v1, const ValueType &v2, const openvdb::Vec3d &w)
Combine different value types.
Definition: AttributeTransferUtil.h:141
bool isConstant(bool &isOn) const
Definition: NodeMasks.h:507
void nodeCount(std::vector< Index32 > &vec) const
Definition: InternalNode.h:1025
LeafNodeType * touchLeaf(const Coord &xyz)
Return the leaf node that contains voxel (x, y, z). If no such node exists, create one...
Definition: InternalNode.h:1468
typename NodeMaskType::Word W
Definition: InternalNode.h:2496
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:503
Definition: NodeMasks.h:189
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: InternalNode.h:2092
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don&#39;t change its value.
Definition: InternalNode.h:1657
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: InternalNode.h:1955
Index64 offVoxelCount() const
Definition: InternalNode.h:1063
LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as probeLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:464
ChildOffIter beginChildOff()
Definition: InternalNode.h:231
void topologyDifference(const InternalNode< OtherChildNodeType, Log2Dim > &other, const ValueType &background)
Difference this node&#39;s set of active values with the active values of the other node, whose ValueType may be different. So a resulting voxel will be active only if the original voxel is active in this node and inactive in the other node.
const OtherInternalNode * s
Definition: InternalNode.h:943
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:106
void visit(VisitorOp &)
Definition: InternalNode.h:2884
OPENVDB_API const void * getGridBackgroundValuePtr(std::ios_base &)
Return a pointer to the background value of the grid currently being read from or written to the give...
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: InternalNode.h:2036
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1795
Index getValueLevelAndCache(const Coord &xyz, AccessorT &) const
Return the level of the tree (0 = leaf) at which the value at the given coordinates resides...
Definition: InternalNode.h:1616
void getNodes(ArrayT &array)
Adds all nodes of a certain type to a container with the following API:
Definition: InternalNode.h:3123