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