OpenVDB  3.0.0
InternalNode.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2014 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 //
34 
35 #ifndef OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
36 #define OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
37 
38 #include <boost/shared_array.hpp>
39 #include <boost/static_assert.hpp>
40 #include <boost/mpl/if.hpp>
41 #include <boost/type_traits/is_const.hpp>
42 #include <boost/type_traits/is_pointer.hpp>
43 #include <boost/type_traits/remove_pointer.hpp>
44 #include <openvdb/Platform.h>
45 #include <openvdb/util/NodeMasks.h>
46 #include <openvdb/io/Compression.h> // for io::readData(), etc.
47 #include <openvdb/math/Math.h> // for Abs(), isExactlyEqual()
48 #include <openvdb/version.h>
49 #include <openvdb/Types.h>
50 #include "Iterator.h"
51 #include "NodeUnion.h"
52 
53 
54 namespace openvdb {
56 namespace OPENVDB_VERSION_NAME {
57 namespace tree {
58 
59 template<typename, Index, typename> struct SameInternalConfig; // forward declaration
60 
61 
62 template<typename _ChildNodeType, Index Log2Dim>
64 {
65 public:
66  typedef _ChildNodeType ChildNodeType;
67  typedef typename ChildNodeType::LeafNodeType LeafNodeType;
68  typedef typename ChildNodeType::ValueType ValueType;
71 
72  static const Index
73  LOG2DIM = Log2Dim,
74  TOTAL = Log2Dim + ChildNodeType::TOTAL,
75  DIM = 1 << TOTAL,
76  NUM_VALUES = 1 << (3 * Log2Dim),
77  LEVEL = 1 + ChildNodeType::LEVEL; // level 0 = leaf
78  static const Index64
79  NUM_VOXELS = uint64_t(1) << (3 * TOTAL); // total # of voxels represented by this node
80 
83  template<typename OtherValueType>
84  struct ValueConverter {
85  typedef InternalNode<typename ChildNodeType::template ValueConverter<
86  OtherValueType>::Type, Log2Dim> Type;
87  };
88 
92  template<typename OtherNodeType>
94  static const bool value =
96  };
97 
98 
100 
101  explicit InternalNode(const ValueType& offValue);
102 
103  InternalNode(const Coord&, const ValueType& fillValue, bool active = false);
104 
105 #ifndef OPENVDB_2_ABI_COMPATIBLE
106  InternalNode(PartialCreate, const Coord&, const ValueType& fillValue, bool active = false);
107 #endif
108 
110  InternalNode(const InternalNode&);
111 
113  template<typename OtherChildNodeType>
115 
117  template<typename OtherChildNodeType>
119  const ValueType& background, TopologyCopy);
120 
122  template<typename OtherChildNodeType>
124  const ValueType& offValue, const ValueType& onValue, TopologyCopy);
125 
126  virtual ~InternalNode();
127 
128 protected:
132 
133  // Type tags to disambiguate template instantiations
134  struct ValueOn {}; struct ValueOff {}; struct ValueAll {};
135  struct ChildOn {}; struct ChildOff {}; struct ChildAll {};
136 
137  // The following class templates implement the iterator interfaces specified in Iterator.h
138  // by providing getItem(), setItem() and/or modifyItem() methods.
139 
140  template<typename NodeT, typename ChildT, typename MaskIterT, typename TagT>
142  MaskIterT, ChildIter<NodeT, ChildT, MaskIterT, TagT>, NodeT, ChildT>
143  {
145  ChildIter(const MaskIterT& iter, NodeT* parent): SparseIteratorBase<
146  MaskIterT, ChildIter<NodeT, ChildT, MaskIterT, TagT>, NodeT, ChildT>(iter, parent) {}
147 
148  ChildT& getItem(Index pos) const
149  {
150  assert(this->parent().isChildMaskOn(pos));
151  return *(this->parent().getChildNode(pos));
152  }
153 
154  // Note: setItem() can't be called on const iterators.
155  void setItem(Index pos, const ChildT& c) const { this->parent().resetChildNode(pos, &c); }
156 
157  // Note: modifyItem() isn't implemented, since it's not useful for child node pointers.
158  };// ChildIter
159 
160  template<typename NodeT, typename ValueT, typename MaskIterT, typename TagT>
162  MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>
163  {
165  ValueIter(const MaskIterT& iter, NodeT* parent): SparseIteratorBase<
166  MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>(iter, parent) {}
167 
168  const ValueT& getItem(Index pos) const { return this->parent().mNodes[pos].getValue(); }
169 
170  // Note: setItem() can't be called on const iterators.
171  void setItem(Index pos, const ValueT& v) const { this->parent().mNodes[pos].setValue(v); }
172 
173  // Note: modifyItem() can't be called on const iterators.
174  template<typename ModifyOp>
175  void modifyItem(Index pos, const ModifyOp& op) const
176  {
177  op(this->parent().mNodes[pos].getValue());
178  }
179  };// ValueIter
180 
181  template<typename NodeT, typename ChildT, typename ValueT, typename TagT>
182  struct DenseIter: public DenseIteratorBase<
183  MaskDenseIterator, DenseIter<NodeT, ChildT, ValueT, TagT>, NodeT, ChildT, ValueT>
184  {
187 
189  DenseIter(const MaskDenseIterator& iter, NodeT* parent):
190  DenseIteratorBase<MaskDenseIterator, DenseIter, NodeT, ChildT, ValueT>(iter, parent) {}
191 
192  bool getItem(Index pos, ChildT*& child, NonConstValueT& value) const
193  {
194  if (this->parent().isChildMaskOn(pos)) {
195  child = this->parent().getChildNode(pos);
196  return true;
197  }
198  child = NULL;
199  value = this->parent().mNodes[pos].getValue();
200  return false;
201  }
202 
203  // Note: setItem() can't be called on const iterators.
204  void setItem(Index pos, ChildT* child) const
205  {
206  this->parent().resetChildNode(pos, child);
207  }
208 
209  // Note: unsetItem() can't be called on const iterators.
210  void unsetItem(Index pos, const ValueT& value) const
211  {
212  this->parent().unsetChildNode(pos, value);
213  }
214  };// DenseIter
215 
216 public:
217  // Iterators (see Iterator.h for usage)
224 
231 
232  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(mChildMask.beginOn(), this); }
233  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(mChildMask.beginOff(), this); }
234  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(mChildMask.beginDense(), this); }
235  ChildOnCIter beginChildOn() const { return cbeginChildOn(); }
236  ChildOffCIter beginChildOff() const { return cbeginChildOff(); }
237  ChildAllCIter beginChildAll() const { return cbeginChildAll(); }
238  ChildOnIter beginChildOn() { return ChildOnIter(mChildMask.beginOn(), this); }
239  ChildOffIter beginChildOff() { return ChildOffIter(mChildMask.beginOff(), this); }
240  ChildAllIter beginChildAll() { return ChildAllIter(mChildMask.beginDense(), this); }
241 
242  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(mValueMask.beginOn(), this); }
244  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(mValueMask.beginOff(), this); }
245  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(mChildMask.beginOff(), this); }
246  ValueOnCIter beginValueOn() const { return cbeginValueOn(); }
248  ValueOffCIter beginValueOff() const { return cbeginValueOff(); }
249  ValueAllCIter beginValueAll() const { return cbeginValueAll(); }
250  ValueOnIter beginValueOn() { return ValueOnIter(mValueMask.beginOn(), this); }
252  ValueOffIter beginValueOff() { return ValueOffIter(mValueMask.beginOff(), this); }
253  ValueAllIter beginValueAll() { return ValueAllIter(mChildMask.beginOff(), this); }
254 
255 
256  static Index dim() { return DIM; }
257  static Index getLevel() { return LEVEL; }
258  static void getNodeLog2Dims(std::vector<Index>& dims);
259  static Index getChildDim() { return ChildNodeType::DIM; }
260 
262  static Index coordToOffset(const Coord& xyz);
265  static void offsetToLocalCoord(Index n, Coord& xyz);
267  Coord offsetToGlobalCoord(Index n) const;
268 
270  const Coord& origin() const { return mOrigin; }
272  void setOrigin(const Coord& origin) { mOrigin = origin; }
273 
274  Index32 leafCount() const;
275  Index32 nonLeafCount() const;
276  Index64 onVoxelCount() const;
277  Index64 offVoxelCount() const;
278  Index64 onLeafVoxelCount() const;
279  Index64 offLeafVoxelCount() const;
280  Index64 onTileCount() const;
281 
283  Index64 memUsage() const;
284 
289  void evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels = true) const;
290 
293  CoordBBox getNodeBoundingBox() const { return CoordBBox::createCube(mOrigin, DIM); }
294 
295  bool isEmpty() const { return mChildMask.isOff(); }
296 
300  bool isConstant(ValueType& constValue, bool& state,
301  const ValueType& tolerance = zeroVal<ValueType>()) const;
303  bool isInactive() const { return this->isChildMaskOff() && this->isValueMaskOff(); }
304 
306  bool isValueOn(const Coord& xyz) const;
308  bool isValueOn(Index offset) const { return mValueMask.isOn(offset); }
309 
311  bool hasActiveTiles() const;
312 
313  const ValueType& getValue(const Coord& xyz) const;
314  bool probeValue(const Coord& xyz, ValueType& value) const;
315 
318  Index getValueLevel(const Coord& xyz) const;
319 
322  const ValueType& getFirstValue() const;
325  const ValueType& getLastValue() const;
326 
328  void setActiveState(const Coord& xyz, bool on);
330  void setValueOnly(const Coord& xyz, const ValueType& value);
332  void setValueOn(const Coord& xyz);
334  void setValueOn(const Coord& xyz, const ValueType& value);
336  void setValueOff(const Coord& xyz);
338  void setValueOff(const Coord& xyz, const ValueType& value);
339 
342  template<typename ModifyOp>
343  void modifyValue(const Coord& xyz, const ModifyOp& op);
345  template<typename ModifyOp>
346  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
347 
352  template<typename AccessorT>
353  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
354 
359  template<typename AccessorT>
360  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
361 
366  template<typename AccessorT>
367  void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
368 
373  template<typename AccessorT>
374  void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
375 
381  template<typename ModifyOp, typename AccessorT>
382  void modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
383 
388  template<typename ModifyOp, typename AccessorT>
389  void modifyValueAndActiveStateAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
390 
395  template<typename AccessorT>
396  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
397 
402  template<typename AccessorT>
403  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
404 
410  template<typename AccessorT>
411  bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
412 
419  template<typename AccessorT>
420  Index getValueLevelAndCache(const Coord& xyz, AccessorT&) const;
421 
423  void setValuesOn();
424 
425  //
426  // I/O
427  //
428  void writeTopology(std::ostream&, bool toHalf = false) const;
429  void readTopology(std::istream&, bool fromHalf = false);
430  void writeBuffers(std::ostream&, bool toHalf = false) const;
431  void readBuffers(std::istream&, bool fromHalf = false);
432  void readBuffers(std::istream&, const CoordBBox&, bool fromHalf = false);
433 
434 
435  //
436  // Aux methods
437  //
440  void fill(const CoordBBox& bbox, const ValueType&, bool active = true);
441 
444  void negate();
445 
447  void voxelizeActiveTiles();
448 
456  template<typename DenseT>
457  void copyToDense(const CoordBBox& bbox, DenseT& dense) const;
458 
461  template<MergePolicy Policy>
462  void merge(InternalNode& other, const ValueType& background, const ValueType& otherBackground);
463 
466  template<MergePolicy Policy> void merge(const ValueType& tileValue, bool tileActive);
467 
480  template<typename OtherChildNodeType>
481  void topologyUnion(const InternalNode<OtherChildNodeType, Log2Dim>& other);
482 
496  template<typename OtherChildNodeType>
497  void topologyIntersection(const InternalNode<OtherChildNodeType, Log2Dim>& other,
498  const ValueType& background);
499 
511  template<typename OtherChildNodeType>
512  void topologyDifference(const InternalNode<OtherChildNodeType, Log2Dim>& other,
513  const ValueType& background);
514 
515  template<typename CombineOp>
516  void combine(InternalNode& other, CombineOp&);
517  template<typename CombineOp>
518  void combine(const ValueType& value, bool valueIsActive, CombineOp&);
519 
520  template<typename CombineOp, typename OtherNodeType /*= InternalNode*/>
521  void combine2(const InternalNode& other0, const OtherNodeType& other1, CombineOp&);
522  template<typename CombineOp, typename OtherNodeType /*= InternalNode*/>
523  void combine2(const ValueType& value, const OtherNodeType& other, bool valIsActive, CombineOp&);
524  template<typename CombineOp, typename OtherValueType>
525  void combine2(const InternalNode& other, const OtherValueType&, bool valIsActive, CombineOp&);
526 
532  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
533 
534  template<typename VisitorOp> void visit(VisitorOp&);
535  template<typename VisitorOp> void visit(VisitorOp&) const;
536 
537  template<typename OtherNodeType, typename VisitorOp>
538  void visit2Node(OtherNodeType& other, VisitorOp&);
539  template<typename OtherNodeType, typename VisitorOp>
540  void visit2Node(OtherNodeType& other, VisitorOp&) const;
541  template<typename IterT, typename VisitorOp>
542  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false);
543  template<typename IterT, typename VisitorOp>
544  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false) const;
545 
547  void clip(const CoordBBox&, const ValueType& background);
548 
552  void prune(const ValueType& tolerance = zeroVal<ValueType>());
553 
556  void addLeaf(LeafNodeType* leaf);
557 
560  template<typename AccessorT>
561  void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
562 
571  template<typename NodeT>
572  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
573 
576  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
577 
579  void addTile(Index offset, const ValueType& value, bool state);
580 
583  template<typename AccessorT>
584  void addTileAndCache(Index level, const Coord& xyz, const ValueType&, bool state, AccessorT&);
585 
587  template<typename NodeType> NodeType* probeNode(const Coord& xyz);
590  template<typename NodeType> const NodeType* probeConstNode(const Coord& xyz) const;
592 
594  template<typename NodeType, typename AccessorT>
597  NodeType* probeNodeAndCache(const Coord& xyz, AccessorT&);
598  template<typename NodeType, typename AccessorT>
599  const NodeType* probeConstNodeAndCache(const Coord& xyz, AccessorT&) const;
601 
603  LeafNodeType* probeLeaf(const Coord& xyz);
606  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
607  const LeafNodeType* probeLeaf(const Coord& xyz) const;
609 
611  template<typename AccessorT>
614  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc);
615  template<typename AccessorT>
616  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const;
617  template<typename AccessorT>
618  const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const;
620 
627  LeafNodeType* touchLeaf(const Coord& xyz);
628 
631  template<typename AccessorT>
632  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT&);
633 
635  template<typename ArrayT> void getNodes(ArrayT& array);
658  template<typename ArrayT> void getNodes(ArrayT& array) const;
660 
663  void resetBackground(const ValueType& oldBackground, const ValueType& newBackground);
664 
667  template<typename OtherChildNodeType, Index OtherLog2Dim>
668  bool hasSameTopology(const InternalNode<OtherChildNodeType, OtherLog2Dim>* other) const;
669 
670 protected:
672  friend class IteratorBase<MaskOnIterator, InternalNode>;
675  friend class IteratorBase<MaskOffIterator, InternalNode>;
676  friend class IteratorBase<MaskDenseIterator, InternalNode>;
678 
681  template<typename, Index> friend class InternalNode;
682 
683  // Mask accessors
684 public:
685  bool isValueMaskOn(Index n) const { return mValueMask.isOn(n); }
686  bool isValueMaskOn() const { return mValueMask.isOn(); }
687  bool isValueMaskOff(Index n) const { return mValueMask.isOff(n); }
688  bool isValueMaskOff() const { return mValueMask.isOff(); }
689  bool isChildMaskOn(Index n) const { return mChildMask.isOn(n); }
690  bool isChildMaskOff(Index n) const { return mChildMask.isOff(n); }
691  bool isChildMaskOff() const { return mChildMask.isOff(); }
692  const NodeMaskType& getValueMask() const { return mValueMask; }
693  const NodeMaskType& getChildMask() const { return mChildMask; }
694  NodeMaskType getValueOffMask() const
695  {
696  NodeMaskType mask = mValueMask;
697  mask |= mChildMask;
698  mask.toggle();
699  return mask;
700  }
701  const UnionType* getTable() const { return mNodes; }
702 protected:
704  void setValueMask(Index n, bool on) { mValueMask.set(n, mChildMask.isOn(n) ? false : on); }
708 
709  void makeChildNodeEmpty(Index n, const ValueType& value);
710  void setChildNode( Index i, ChildNodeType* child);//assumes a tile
711  void resetChildNode(Index i, ChildNodeType* child);//checks for an existing child
712  ChildNodeType* unsetChildNode(Index i, const ValueType& value);
713 
714  template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
715  static inline void doVisit(NodeT&, VisitorOp&);
716 
717  template<typename NodeT, typename OtherNodeT, typename VisitorOp,
718  typename ChildAllIterT, typename OtherChildAllIterT>
719  static inline void doVisit2Node(NodeT&, OtherNodeT&, VisitorOp&);
720 
721  template<typename NodeT, typename VisitorOp,
722  typename ChildAllIterT, typename OtherChildAllIterT>
723  static inline void doVisit2(NodeT&, OtherChildAllIterT&, VisitorOp&, bool otherIsLHS);
724 
729  ChildNodeType* getChildNode(Index n);
730  const ChildNodeType* getChildNode(Index n) const;
732 
733 
734  UnionType mNodes[NUM_VALUES];
735  NodeMaskType mChildMask, mValueMask;
737  Coord mOrigin;
738 }; // class InternalNode
739 
740 
742 
743 
745 template<typename ChildT1, Index Dim1, typename NodeT2>
748 struct SameInternalConfig {
749  static const bool value = false;
750 };
751 
752 template<typename ChildT1, Index Dim1, typename ChildT2>
753 struct SameInternalConfig<ChildT1, Dim1, InternalNode<ChildT2, Dim1> > {
754  static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
755 };
757 
758 
760 
761 
762 template<typename ChildT, Index Log2Dim>
763 inline
765 {
766  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
767 }
768 
769 
770 template<typename ChildT, Index Log2Dim>
771 inline
772 InternalNode<ChildT, Log2Dim>::InternalNode(const Coord& origin, const ValueType& val, bool active):
773  mOrigin(origin[0] & ~(DIM - 1), // zero out the low-order bits
774  origin[1] & ~(DIM - 1),
775  origin[2] & ~(DIM - 1))
776 {
777  if (active) mValueMask.setOn();
778  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
779 }
780 
781 
782 #ifndef OPENVDB_2_ABI_COMPATIBLE
783 // For InternalNodes, the PartialCreate constructor is identical to its
784 // non-PartialCreate counterpart.
785 template<typename ChildT, Index Log2Dim>
786 inline
788  const Coord& origin, const ValueType& val, bool active)
789  : mOrigin(origin[0] & ~(DIM-1), origin[1] & ~(DIM-1), origin[2] & ~(DIM-1))
790 {
791  if (active) mValueMask.setOn();
792  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
793 }
794 #endif
795 
796 
797 template<typename ChildT, Index Log2Dim>
798 inline
800  mChildMask(other.mChildMask),
801  mValueMask(other.mValueMask),
802  mOrigin(other.mOrigin)
803 {
804  for (Index i = 0; i < NUM_VALUES; ++i) {
805  if (isChildMaskOn(i)) {
806  mNodes[i].setChild(new ChildNodeType(*(other.mNodes[i].getChild())));
807  } else {
808  mNodes[i].setValue(other.mNodes[i].getValue());
809  }
810  }
811 }
812 
813 
814 // Copy-construct from a node with the same configuration but a different ValueType.
815 template<typename ChildT, Index Log2Dim>
816 template<typename OtherChildNodeType>
817 inline
819  : mChildMask(other.mChildMask)
820  , mValueMask(other.mValueMask)
821  , mOrigin(other.mOrigin)
822 {
823  struct Local {
825  static inline ValueType
826  convertValue(const typename OtherChildNodeType::ValueType& val) { return ValueType(val); }
827  };
828 
829  for (Index i = 0; i < NUM_VALUES; ++i) {
830  if (other.mChildMask.isOff(i)) {
831  mNodes[i].setValue(Local::convertValue(other.mNodes[i].getValue()));
832  } else {
833  mNodes[i].setChild(new ChildNodeType(*(other.mNodes[i].getChild())));
834  }
835  }
836 }
837 
838 
839 template<typename ChildT, Index Log2Dim>
840 template<typename OtherChildNodeType>
841 inline
843  const ValueType& offValue, const ValueType& onValue, TopologyCopy):
844  mChildMask(other.mChildMask),
845  mValueMask(other.mValueMask),
846  mOrigin(other.mOrigin)
847 {
848  for (Index i = 0; i < NUM_VALUES; ++i) {
849  if (isChildMaskOn(i)) {
850  mNodes[i].setChild(new ChildNodeType(*(other.mNodes[i].getChild()),
851  offValue, onValue, TopologyCopy()));
852  } else {
853  mNodes[i].setValue(isValueMaskOn(i) ? onValue : offValue);
854  }
855  }
856 }
857 
858 template<typename ChildT, Index Log2Dim>
859 template<typename OtherChildNodeType>
860 inline
862  const ValueType& background, TopologyCopy):
863  mChildMask(other.mChildMask),
864  mValueMask(other.mValueMask),
865  mOrigin(other.mOrigin)
866 {
867  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
868  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
869  mNodes[iter.pos()].setChild(new ChildNodeType(*(other.mNodes[iter.pos()].getChild()),
870  background, TopologyCopy()));
871  }
872 }
873 
874 
875 template<typename ChildT, Index Log2Dim>
876 inline
878 {
879  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
880  delete mNodes[iter.pos()].getChild();
881  }
882 }
883 
884 
886 
887 
888 template<typename ChildT, Index Log2Dim>
889 inline Index32
891 {
892  if (ChildNodeType::getLevel() == 0) return mChildMask.countOn();
893  Index32 sum = 0;
894  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
895  sum += iter->leafCount();
896  }
897  return sum;
898 }
899 
900 
901 template<typename ChildT, Index Log2Dim>
902 inline Index32
904 {
905  Index32 sum = 1;
906  if (ChildNodeType::getLevel() == 0) return sum;
907  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
908  sum += iter->nonLeafCount();
909  }
910  return sum;
911 }
912 
913 
914 template<typename ChildT, Index Log2Dim>
915 inline Index64
917 {
918  Index64 sum = ChildT::NUM_VOXELS * mValueMask.countOn();
919  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
920  sum += iter->onVoxelCount();
921  }
922  return sum;
923 }
924 
925 
926 template<typename ChildT, Index Log2Dim>
927 inline Index64
929 {
930  Index64 sum = ChildT::NUM_VOXELS * (NUM_VALUES-mValueMask.countOn()-mChildMask.countOn());
931  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
932  sum += iter->offVoxelCount();
933  }
934  return sum;
935 }
936 
937 
938 template<typename ChildT, Index Log2Dim>
939 inline Index64
941 {
942  Index64 sum = 0;
943  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
944  sum += mNodes[iter.pos()].getChild()->onLeafVoxelCount();
945  }
946  return sum;
947 }
948 
949 
950 template<typename ChildT, Index Log2Dim>
951 inline Index64
953 {
954  Index64 sum = 0;
955  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
956  sum += mNodes[iter.pos()].getChild()->offLeafVoxelCount();
957  }
958  return sum;
959 }
960 
961 template<typename ChildT, Index Log2Dim>
962 inline Index64
964 {
965  Index64 sum = mValueMask.countOn();
966  for (ChildOnCIter iter = this->cbeginChildOn(); LEVEL>1 && iter; ++iter) {
967  sum += iter->onTileCount();
968  }
969  return sum;
970 }
971 
972 template<typename ChildT, Index Log2Dim>
973 inline Index64
975 {
976  Index64 sum = NUM_VALUES * sizeof(UnionType) + mChildMask.memUsage()
977  + mValueMask.memUsage() + sizeof(mOrigin);
978  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
979  sum += iter->memUsage();
980  }
981  return sum;
982 }
983 
984 
985 template<typename ChildT, Index Log2Dim>
986 inline void
987 InternalNode<ChildT, Log2Dim>::evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels) const
988 {
989  if (bbox.isInside(this->getNodeBoundingBox())) return;
990 
991  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) {
992  bbox.expand(i.getCoord(), ChildT::DIM);
993  }
994  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) {
995  i->evalActiveBoundingBox(bbox, visitVoxels);
996  }
997 }
998 
999 
1001 
1002 
1003 template<typename ChildT, Index Log2Dim>
1004 inline void
1005 InternalNode<ChildT, Log2Dim>::prune(const ValueType& tolerance)
1006 {
1007  bool state = false;
1008  ValueType value = zeroVal<ValueType>();
1009  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1010  const Index i = iter.pos();
1011  ChildT* child = mNodes[i].getChild();
1012  child->prune(tolerance);
1013  if (child->isConstant(value, state, tolerance)) {
1014  delete child;
1015  mChildMask.setOff(i);
1016  mValueMask.set(i, state);
1017  mNodes[i].setValue(value);
1018  }
1019  }
1020 }
1021 
1022 
1024 
1025 
1026 template<typename ChildT, Index Log2Dim>
1027 template<typename NodeT>
1028 inline NodeT*
1029 InternalNode<ChildT, Log2Dim>::stealNode(const Coord& xyz, const ValueType& value, bool state)
1030 {
1031  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
1032  NodeT::LEVEL > ChildT::LEVEL) return NULL;
1034  const Index n = this->coordToOffset(xyz);
1035  if (mChildMask.isOff(n)) return NULL;
1036  ChildT* child = mNodes[n].getChild();
1037  if (boost::is_same<NodeT, ChildT>::value) {
1038  mChildMask.setOff(n);
1039  mValueMask.set(n, state);
1040  mNodes[n].setValue(value);
1041  }
1042  return (boost::is_same<NodeT, ChildT>::value)
1043  ? reinterpret_cast<NodeT*>(child)
1044  : child->template stealNode<NodeT>(xyz, value, state);
1046 }
1047 
1048 
1050 
1051 
1052 template<typename ChildT, Index Log2Dim>
1053 template<typename NodeT>
1054 inline NodeT*
1056 {
1057  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
1058  NodeT::LEVEL > ChildT::LEVEL) return NULL;
1060  const Index n = this->coordToOffset(xyz);
1061  if (mChildMask.isOff(n)) return NULL;
1062  ChildT* child = mNodes[n].getChild();
1063  return (boost::is_same<NodeT, ChildT>::value)
1064  ? reinterpret_cast<NodeT*>(child)
1065  : child->template probeNode<NodeT>(xyz);
1067 }
1068 
1069 
1070 template<typename ChildT, Index Log2Dim>
1071 template<typename NodeT, typename AccessorT>
1072 inline NodeT*
1073 InternalNode<ChildT, Log2Dim>::probeNodeAndCache(const Coord& xyz, AccessorT& acc)
1074 {
1075  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
1076  NodeT::LEVEL > ChildT::LEVEL) return NULL;
1078  const Index n = this->coordToOffset(xyz);
1079  if (mChildMask.isOff(n)) return NULL;
1080  ChildT* child = mNodes[n].getChild();
1081  acc.insert(xyz, child);
1082  return (boost::is_same<NodeT, ChildT>::value)
1083  ? reinterpret_cast<NodeT*>(child)
1084  : child->template probeNodeAndCache<NodeT>(xyz, acc);
1086 }
1087 
1088 
1089 template<typename ChildT, Index Log2Dim>
1090 template<typename NodeT>
1091 inline const NodeT*
1093 {
1094  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
1095  NodeT::LEVEL > ChildT::LEVEL) return NULL;
1097  const Index n = this->coordToOffset(xyz);
1098  if (mChildMask.isOff(n)) return NULL;
1099  const ChildT* child = mNodes[n].getChild();
1100  return (boost::is_same<NodeT, ChildT>::value)
1101  ? reinterpret_cast<const NodeT*>(child)
1102  : child->template probeConstNode<NodeT>(xyz);
1104 }
1105 
1106 
1107 template<typename ChildT, Index Log2Dim>
1108 template<typename NodeT, typename AccessorT>
1109 inline const NodeT*
1110 InternalNode<ChildT, Log2Dim>::probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const
1111 {
1112  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
1113  NodeT::LEVEL > ChildT::LEVEL) return NULL;
1115  const Index n = this->coordToOffset(xyz);
1116  if (mChildMask.isOff(n)) return NULL;
1117  const ChildT* child = mNodes[n].getChild();
1118  acc.insert(xyz, child);
1119  return (boost::is_same<NodeT, ChildT>::value)
1120  ? reinterpret_cast<const NodeT*>(child)
1121  : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
1123 }
1124 
1125 
1127 
1128 
1129 template<typename ChildT, Index Log2Dim>
1130 inline typename ChildT::LeafNodeType*
1132 {
1133  return this->template probeNode<LeafNodeType>(xyz);
1134 }
1135 
1136 
1137 template<typename ChildT, Index Log2Dim>
1138 template<typename AccessorT>
1139 inline typename ChildT::LeafNodeType*
1140 InternalNode<ChildT, Log2Dim>::probeLeafAndCache(const Coord& xyz, AccessorT& acc)
1141 {
1142  return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
1143 }
1144 
1145 
1146 template<typename ChildT, Index Log2Dim>
1147 template<typename AccessorT>
1148 inline const typename ChildT::LeafNodeType*
1149 InternalNode<ChildT, Log2Dim>::probeLeafAndCache(const Coord& xyz, AccessorT& acc) const
1150 {
1151  return this->probeConstLeafAndCache(xyz, acc);
1152 }
1153 
1154 
1155 template<typename ChildT, Index Log2Dim>
1156 inline const typename ChildT::LeafNodeType*
1158 {
1159  return this->template probeConstNode<LeafNodeType>(xyz);
1160 }
1161 
1162 
1163 template<typename ChildT, Index Log2Dim>
1164 template<typename AccessorT>
1165 inline const typename ChildT::LeafNodeType*
1166 InternalNode<ChildT, Log2Dim>::probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
1167 {
1168  return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
1169 }
1170 
1171 
1173 
1174 
1175 template<typename ChildT, Index Log2Dim>
1176 inline void
1178 {
1179  assert(leaf != NULL);
1180  const Coord& xyz = leaf->origin();
1181  const Index n = this->coordToOffset(xyz);
1182  ChildT* child = NULL;
1183  if (mChildMask.isOff(n)) {
1184  if (ChildT::LEVEL>0) {
1185  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1186  } else {
1187  child = reinterpret_cast<ChildT*>(leaf);
1188  }
1189  this->setChildNode(n, child);
1190  } else {
1191  if (ChildT::LEVEL>0) {
1192  child = mNodes[n].getChild();
1193  } else {
1194  delete mNodes[n].getChild();
1195  child = reinterpret_cast<ChildT*>(leaf);
1196  mNodes[n].setChild(child);
1197  }
1198  }
1199  child->addLeaf(leaf);
1200 }
1201 
1202 
1203 template<typename ChildT, Index Log2Dim>
1204 template<typename AccessorT>
1205 inline void
1206 InternalNode<ChildT, Log2Dim>::addLeafAndCache(LeafNodeType* leaf, AccessorT& acc)
1207 {
1208  assert(leaf != NULL);
1209  const Coord& xyz = leaf->origin();
1210  const Index n = this->coordToOffset(xyz);
1211  ChildT* child = NULL;
1212  if (mChildMask.isOff(n)) {
1213  if (ChildT::LEVEL>0) {
1214  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1215  acc.insert(xyz, child);//we only cache internal nodes
1216  } else {
1217  child = reinterpret_cast<ChildT*>(leaf);
1218  }
1219  this->setChildNode(n, child);
1220  } else {
1221  if (ChildT::LEVEL>0) {
1222  child = mNodes[n].getChild();
1223  acc.insert(xyz, child);//we only cache internal nodes
1224  } else {
1225  delete mNodes[n].getChild();
1226  child = reinterpret_cast<ChildT*>(leaf);
1227  mNodes[n].setChild(child);
1228  }
1229  }
1230  child->addLeafAndCache(leaf, acc);
1231 }
1232 
1233 
1235 
1236 
1237 template<typename ChildT, Index Log2Dim>
1238 inline void
1239 InternalNode<ChildT, Log2Dim>::addTile(Index n, const ValueType& value, bool state)
1240 {
1241  assert(n < NUM_VALUES);
1242  this->makeChildNodeEmpty(n, value);
1243  mValueMask.set(n, state);
1244 }
1245 
1246 
1247 template<typename ChildT, Index Log2Dim>
1248 inline void
1250  const ValueType& value, bool state)
1251 {
1252  if (LEVEL >= level) {
1253  const Index n = this->coordToOffset(xyz);
1254  if (mChildMask.isOff(n)) {// tile case
1255  if (LEVEL > level) {
1256  ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1257  this->setChildNode(n, child);
1258  child->addTile(level, xyz, value, state);
1259  } else {
1260  mValueMask.set(n, state);
1261  mNodes[n].setValue(value);
1262  }
1263  } else {// child branch case
1264  ChildT* child = mNodes[n].getChild();
1265  if (LEVEL > level) {
1266  child->addTile(level, xyz, value, state);
1267  } else {
1268  delete child;
1269  mChildMask.setOff(n);
1270  mValueMask.set(n, state);
1271  mNodes[n].setValue(value);
1272  }
1273  }
1274  }
1275 }
1276 
1277 
1278 template<typename ChildT, Index Log2Dim>
1279 template<typename AccessorT>
1280 inline void
1282  const ValueType& value, bool state, AccessorT& acc)
1283 {
1284  if (LEVEL >= level) {
1285  const Index n = this->coordToOffset(xyz);
1286  if (mChildMask.isOff(n)) {// tile case
1287  if (LEVEL > level) {
1288  ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1289  this->setChildNode(n, child);
1290  acc.insert(xyz, child);
1291  child->addTileAndCache(level, xyz, value, state, acc);
1292  } else {
1293  mValueMask.set(n, state);
1294  mNodes[n].setValue(value);
1295  }
1296  } else {// child branch case
1297  ChildT* child = mNodes[n].getChild();
1298  if (LEVEL > level) {
1299  acc.insert(xyz, child);
1300  child->addTileAndCache(level, xyz, value, state, acc);
1301  } else {
1302  delete child;
1303  mChildMask.setOff(n);
1304  mValueMask.set(n, state);
1305  mNodes[n].setValue(value);
1306  }
1307  }
1308  }
1309 }
1310 
1311 
1313 
1314 
1315 template<typename ChildT, Index Log2Dim>
1316 inline typename ChildT::LeafNodeType*
1318 {
1319  const Index n = this->coordToOffset(xyz);
1320  ChildT* child = NULL;
1321  if (mChildMask.isOff(n)) {
1322  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1323  this->setChildNode(n, child);
1324  } else {
1325  child = mNodes[n].getChild();
1326  }
1327  return child->touchLeaf(xyz);
1328 }
1329 
1330 
1331 template<typename ChildT, Index Log2Dim>
1332 template<typename AccessorT>
1333 inline typename ChildT::LeafNodeType*
1334 InternalNode<ChildT, Log2Dim>::touchLeafAndCache(const Coord& xyz, AccessorT& acc)
1335 {
1336  const Index n = this->coordToOffset(xyz);
1337  if (mChildMask.isOff(n)) {
1338  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), mValueMask.isOn(n)));
1339  }
1340  acc.insert(xyz, mNodes[n].getChild());
1341  return mNodes[n].getChild()->touchLeafAndCache(xyz, acc);
1342 }
1343 
1344 
1346 
1347 
1348 template<typename ChildT, Index Log2Dim>
1349 inline bool
1350 InternalNode<ChildT, Log2Dim>::isConstant(ValueType& constValue, bool& state,
1351  const ValueType& tolerance) const
1352 {
1353  bool allEqual = true, firstValue = true, valueState = true;
1354  ValueType value = zeroVal<ValueType>();
1355  for (Index i = 0; allEqual && i < NUM_VALUES; ++i) {
1356  if (this->isChildMaskOff(i)) {
1357  // If entry i is a value, check if it is within tolerance
1358  // and whether its active state matches the other entries.
1359  if (firstValue) {
1360  firstValue = false;
1361  valueState = isValueMaskOn(i);
1362  value = mNodes[i].getValue();
1363  } else {
1364  allEqual = (isValueMaskOn(i) == valueState)
1365  && math::isApproxEqual(mNodes[i].getValue(), value, tolerance);
1366  }
1367  } else {
1368  // If entry i is a child, check if the child is constant and within tolerance
1369  // and whether its active state matches the other entries.
1370  ValueType childValue = zeroVal<ValueType>();
1371  bool isChildOn = false;
1372  if (mNodes[i].getChild()->isConstant(childValue, isChildOn, tolerance)) {
1373  if (firstValue) {
1374  firstValue = false;
1375  valueState = isChildOn;
1376  value = childValue;
1377  } else {
1378  allEqual = (isChildOn == valueState)
1379  && math::isApproxEqual(childValue, value, tolerance);
1380  }
1381  } else { // child is not constant
1382  allEqual = false;
1383  }
1384  }
1385  }
1386  if (allEqual) {
1387  constValue = value;
1388  state = valueState;
1389  }
1390  return allEqual;
1391 }
1392 
1393 
1395 
1396 
1397 template<typename ChildT, Index Log2Dim>
1398 inline bool
1400 {
1402  const bool anyActiveTiles = !mValueMask.isOff();
1403  if (LEVEL==1 || anyActiveTiles) return anyActiveTiles;
1404  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1405  if (iter->hasActiveTiles()) return true;
1406  }
1407  return false;
1409 }
1410 
1411 
1412 template<typename ChildT, Index Log2Dim>
1413 inline bool
1415 {
1416  const Index n = this->coordToOffset(xyz);
1417  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1418  return mNodes[n].getChild()->isValueOn(xyz);
1419 }
1420 
1421 template<typename ChildT, Index Log2Dim>
1422 template<typename AccessorT>
1423 inline bool
1424 InternalNode<ChildT, Log2Dim>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const
1425 {
1426  const Index n = this->coordToOffset(xyz);
1427  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1428  acc.insert(xyz, mNodes[n].getChild());
1429  return mNodes[n].getChild()->isValueOnAndCache(xyz, acc);
1430 }
1431 
1432 
1433 template<typename ChildT, Index Log2Dim>
1434 inline const typename ChildT::ValueType&
1436 {
1437  const Index n = this->coordToOffset(xyz);
1438  return this->isChildMaskOff(n) ? mNodes[n].getValue()
1439  : mNodes[n].getChild()->getValue(xyz);
1440 }
1441 
1442 template<typename ChildT, Index Log2Dim>
1443 template<typename AccessorT>
1444 inline const typename ChildT::ValueType&
1445 InternalNode<ChildT, Log2Dim>::getValueAndCache(const Coord& xyz, AccessorT& acc) const
1446 {
1447  const Index n = this->coordToOffset(xyz);
1448  if (this->isChildMaskOn(n)) {
1449  acc.insert(xyz, mNodes[n].getChild());
1450  return mNodes[n].getChild()->getValueAndCache(xyz, acc);
1451  }
1452  return mNodes[n].getValue();
1453 }
1454 
1455 
1456 template<typename ChildT, Index Log2Dim>
1457 inline Index
1459 {
1460  const Index n = this->coordToOffset(xyz);
1461  return this->isChildMaskOff(n) ? LEVEL : mNodes[n].getChild()->getValueLevel(xyz);
1462 }
1463 
1464 template<typename ChildT, Index Log2Dim>
1465 template<typename AccessorT>
1466 inline Index
1467 InternalNode<ChildT, Log2Dim>::getValueLevelAndCache(const Coord& xyz, AccessorT& acc) const
1468 {
1469  const Index n = this->coordToOffset(xyz);
1470  if (this->isChildMaskOn(n)) {
1471  acc.insert(xyz, mNodes[n].getChild());
1472  return mNodes[n].getChild()->getValueLevelAndCache(xyz, acc);
1473  }
1474  return LEVEL;
1475 }
1476 
1477 
1478 template<typename ChildT, Index Log2Dim>
1479 inline bool
1480 InternalNode<ChildT, Log2Dim>::probeValue(const Coord& xyz, ValueType& value) const
1481 {
1482  const Index n = this->coordToOffset(xyz);
1483  if (this->isChildMaskOff(n)) {
1484  value = mNodes[n].getValue();
1485  return this->isValueMaskOn(n);
1486  }
1487  return mNodes[n].getChild()->probeValue(xyz, value);
1488 }
1489 
1490 template<typename ChildT, Index Log2Dim>
1491 template<typename AccessorT>
1492 inline bool
1494  ValueType& value, AccessorT& acc) const
1495 {
1496  const Index n = this->coordToOffset(xyz);
1497  if (this->isChildMaskOn(n)) {
1498  acc.insert(xyz, mNodes[n].getChild());
1499  return mNodes[n].getChild()->probeValueAndCache(xyz, value, acc);
1500  }
1501  value = mNodes[n].getValue();
1502  return this->isValueMaskOn(n);
1503 }
1504 
1505 
1506 template<typename ChildT, Index Log2Dim>
1507 inline void
1509 {
1510  const Index n = this->coordToOffset(xyz);
1511  bool hasChild = this->isChildMaskOn(n);
1512  if (!hasChild && this->isValueMaskOn(n)) {
1513  // If the voxel belongs to a constant tile that is active,
1514  // a child subtree must be constructed.
1515  hasChild = true;
1516  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/true));
1517  }
1518  if (hasChild) mNodes[n].getChild()->setValueOff(xyz);
1519 }
1520 
1521 
1522 template<typename ChildT, Index Log2Dim>
1523 inline void
1525 {
1526  const Index n = this->coordToOffset(xyz);
1527  bool hasChild = this->isChildMaskOn(n);
1528  if (!hasChild && !this->isValueMaskOn(n)) {
1529  // If the voxel belongs to a constant tile that is inactive,
1530  // a child subtree must be constructed.
1531  hasChild = true;
1532  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/false));
1533  }
1534  if (hasChild) mNodes[n].getChild()->setValueOn(xyz);
1535 }
1536 
1537 
1538 template<typename ChildT, Index Log2Dim>
1539 inline void
1540 InternalNode<ChildT, Log2Dim>::setValueOff(const Coord& xyz, const ValueType& value)
1541 {
1542  const Index n = InternalNode::coordToOffset(xyz);
1543  bool hasChild = this->isChildMaskOn(n);
1544  if (!hasChild) {
1545  const bool active = this->isValueMaskOn(n);
1546  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1547  // If the voxel belongs to a tile that is either active or that
1548  // has a constant value that is different from the one provided,
1549  // a child subtree must be constructed.
1550  hasChild = true;
1551  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1552  }
1553  }
1554  if (hasChild) mNodes[n].getChild()->setValueOff(xyz, value);
1555 }
1556 
1557 template<typename ChildT, Index Log2Dim>
1558 template<typename AccessorT>
1559 inline void
1561  const ValueType& value, AccessorT& acc)
1562 {
1563  const Index n = InternalNode::coordToOffset(xyz);
1564  bool hasChild = this->isChildMaskOn(n);
1565  if (!hasChild) {
1566  const bool active = this->isValueMaskOn(n);
1567  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1568  // If the voxel belongs to a tile that is either active or that
1569  // has a constant value that is different from the one provided,
1570  // a child subtree must be constructed.
1571  hasChild = true;
1572  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1573  }
1574  }
1575  if (hasChild) {
1576  ChildT* child = mNodes[n].getChild();
1577  acc.insert(xyz, child);
1578  child->setValueOffAndCache(xyz, value, acc);
1579  }
1580 }
1581 
1582 
1583 template<typename ChildT, Index Log2Dim>
1584 inline void
1585 InternalNode<ChildT, Log2Dim>::setValueOn(const Coord& xyz, const ValueType& value)
1586 {
1587  const Index n = this->coordToOffset(xyz);
1588  bool hasChild = this->isChildMaskOn(n);
1589  if (!hasChild) {
1590  const bool active = this->isValueMaskOn(n); // tile's active state
1591  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1592  // If the voxel belongs to a tile that is either inactive or that
1593  // has a constant value that is different from the one provided,
1594  // a child subtree must be constructed.
1595  hasChild = true;
1596  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1597  }
1598  }
1599  if (hasChild) mNodes[n].getChild()->setValueOn(xyz, value);
1600 }
1601 
1602 template<typename ChildT, Index Log2Dim>
1603 template<typename AccessorT>
1604 inline void
1606  const ValueType& value, AccessorT& acc)
1607 {
1608  const Index n = this->coordToOffset(xyz);
1609  bool hasChild = this->isChildMaskOn(n);
1610  if (!hasChild) {
1611  const bool active = this->isValueMaskOn(n);
1612  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1613  // If the voxel belongs to a tile that is either inactive or that
1614  // has a constant value that is different from the one provided,
1615  // a child subtree must be constructed.
1616  hasChild = true;
1617  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1618  }
1619  }
1620  if (hasChild) {
1621  acc.insert(xyz, mNodes[n].getChild());
1622  mNodes[n].getChild()->setValueAndCache(xyz, value, acc);
1623  }
1624 }
1625 
1626 
1627 template<typename ChildT, Index Log2Dim>
1628 inline void
1629 InternalNode<ChildT, Log2Dim>::setValueOnly(const Coord& xyz, const ValueType& value)
1630 {
1631  const Index n = this->coordToOffset(xyz);
1632  bool hasChild = this->isChildMaskOn(n);
1633  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1634  // If the voxel has a tile value that is different from the one provided,
1635  // a child subtree must be constructed.
1636  const bool active = this->isValueMaskOn(n);
1637  hasChild = true;
1638  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1639  }
1640  if (hasChild) mNodes[n].getChild()->setValueOnly(xyz, value);
1641 }
1642 
1643 template<typename ChildT, Index Log2Dim>
1644 template<typename AccessorT>
1645 inline void
1647  const ValueType& value, AccessorT& acc)
1648 {
1649  const Index n = this->coordToOffset(xyz);
1650  bool hasChild = this->isChildMaskOn(n);
1651  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1652  // If the voxel has a tile value that is different from the one provided,
1653  // a child subtree must be constructed.
1654  const bool active = this->isValueMaskOn(n);
1655  hasChild = true;
1656  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1657  }
1658  if (hasChild) {
1659  acc.insert(xyz, mNodes[n].getChild());
1660  mNodes[n].getChild()->setValueOnlyAndCache(xyz, value, acc);
1661  }
1662 }
1663 
1664 
1665 template<typename ChildT, Index Log2Dim>
1666 inline void
1668 {
1669  const Index n = this->coordToOffset(xyz);
1670  bool hasChild = this->isChildMaskOn(n);
1671  if (!hasChild) {
1672  if (on != this->isValueMaskOn(n)) {
1673  // If the voxel belongs to a tile with the wrong active state,
1674  // then a child subtree must be constructed.
1675  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1676  hasChild = true;
1677  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1678  }
1679  }
1680  if (hasChild) mNodes[n].getChild()->setActiveState(xyz, on);
1681 }
1682 
1683 template<typename ChildT, Index Log2Dim>
1684 template<typename AccessorT>
1685 inline void
1686 InternalNode<ChildT, Log2Dim>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc)
1687 {
1688  const Index n = this->coordToOffset(xyz);
1689  bool hasChild = this->isChildMaskOn(n);
1690  if (!hasChild) {
1691  if (on != this->isValueMaskOn(n)) {
1692  // If the voxel belongs to a tile with the wrong active state,
1693  // then a child subtree must be constructed.
1694  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1695  hasChild = true;
1696  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1697  }
1698  }
1699  if (hasChild) {
1700  ChildT* child = mNodes[n].getChild();
1701  acc.insert(xyz, child);
1702  child->setActiveStateAndCache(xyz, on, acc);
1703  }
1704 }
1705 
1706 
1707 template<typename ChildT, Index Log2Dim>
1708 inline void
1710 {
1711  mValueMask = !mChildMask;
1712  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1713  mNodes[iter.pos()].getChild()->setValuesOn();
1714  }
1715 }
1716 
1717 
1718 template<typename ChildT, Index Log2Dim>
1719 template<typename ModifyOp>
1720 inline void
1721 InternalNode<ChildT, Log2Dim>::modifyValue(const Coord& xyz, const ModifyOp& op)
1722 {
1723  const Index n = InternalNode::coordToOffset(xyz);
1724  bool hasChild = this->isChildMaskOn(n);
1725  if (!hasChild) {
1726  // Need to create a child if the tile is inactive,
1727  // in order to activate voxel (x, y, z).
1728  const bool active = this->isValueMaskOn(n);
1729  bool createChild = !active;
1730  if (!createChild) {
1731  // Need to create a child if applying the functor
1732  // to the tile value produces a different value.
1733  const ValueType& tileVal = mNodes[n].getValue();
1734  ValueType modifiedVal = tileVal;
1735  op(modifiedVal);
1736  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1737  }
1738  if (createChild) {
1739  hasChild = true;
1740  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1741  }
1742  }
1743  if (hasChild) mNodes[n].getChild()->modifyValue(xyz, op);
1744 }
1745 
1746 template<typename ChildT, Index Log2Dim>
1747 template<typename ModifyOp, typename AccessorT>
1748 inline void
1749 InternalNode<ChildT, Log2Dim>::modifyValueAndCache(const Coord& xyz, const ModifyOp& op,
1750  AccessorT& acc)
1751 {
1752  const Index n = InternalNode::coordToOffset(xyz);
1753  bool hasChild = this->isChildMaskOn(n);
1754  if (!hasChild) {
1755  // Need to create a child if the tile is inactive,
1756  // in order to activate voxel (x, y, z).
1757  const bool active = this->isValueMaskOn(n);
1758  bool createChild = !active;
1759  if (!createChild) {
1760  // Need to create a child if applying the functor
1761  // to the tile value produces a different value.
1762  const ValueType& tileVal = mNodes[n].getValue();
1763  ValueType modifiedVal = tileVal;
1764  op(modifiedVal);
1765  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1766  }
1767  if (createChild) {
1768  hasChild = true;
1769  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1770  }
1771  }
1772  if (hasChild) {
1773  ChildNodeType* child = mNodes[n].getChild();
1774  acc.insert(xyz, child);
1775  child->modifyValueAndCache(xyz, op, acc);
1776  }
1777 }
1778 
1779 
1780 template<typename ChildT, Index Log2Dim>
1781 template<typename ModifyOp>
1782 inline void
1784 {
1785  const Index n = InternalNode::coordToOffset(xyz);
1786  bool hasChild = this->isChildMaskOn(n);
1787  if (!hasChild) {
1788  const bool tileState = this->isValueMaskOn(n);
1789  const ValueType& tileVal = mNodes[n].getValue();
1790  bool modifiedState = !tileState;
1791  ValueType modifiedVal = tileVal;
1792  op(modifiedVal, modifiedState);
1793  // Need to create a child if applying the functor to the tile
1794  // produces a different value or active state.
1795  if (modifiedState != tileState || !math::isExactlyEqual(modifiedVal, tileVal)) {
1796  hasChild = true;
1797  this->setChildNode(n, new ChildNodeType(xyz, tileVal, tileState));
1798  }
1799  }
1800  if (hasChild) mNodes[n].getChild()->modifyValueAndActiveState(xyz, op);
1801 }
1802 
1803 template<typename ChildT, Index Log2Dim>
1804 template<typename ModifyOp, typename AccessorT>
1805 inline void
1807  const Coord& xyz, const ModifyOp& op, AccessorT& acc)
1808 {
1809  const Index n = InternalNode::coordToOffset(xyz);
1810  bool hasChild = this->isChildMaskOn(n);
1811  if (!hasChild) {
1812  const bool tileState = this->isValueMaskOn(n);
1813  const ValueType& tileVal = mNodes[n].getValue();
1814  bool modifiedState = !tileState;
1815  ValueType modifiedVal = tileVal;
1816  op(modifiedVal, modifiedState);
1817  // Need to create a child if applying the functor to the tile
1818  // produces a different value or active state.
1819  if (modifiedState != tileState || !math::isExactlyEqual(modifiedVal, tileVal)) {
1820  hasChild = true;
1821  this->setChildNode(n, new ChildNodeType(xyz, tileVal, tileState));
1822  }
1823  }
1824  if (hasChild) {
1825  ChildNodeType* child = mNodes[n].getChild();
1826  acc.insert(xyz, child);
1827  child->modifyValueAndActiveStateAndCache(xyz, op, acc);
1828  }
1829 }
1830 
1831 
1833 
1834 
1835 template<typename ChildT, Index Log2Dim>
1836 inline void
1837 InternalNode<ChildT, Log2Dim>::clip(const CoordBBox& clipBBox, const ValueType& background)
1838 {
1839  CoordBBox nodeBBox = this->getNodeBoundingBox();
1840  if (!clipBBox.hasOverlap(nodeBBox)) {
1841  // This node lies completely outside the clipping region. Fill it with background tiles.
1842  this->fill(nodeBBox, background, /*active=*/false);
1843  } else if (clipBBox.isInside(nodeBBox)) {
1844  // This node lies completely inside the clipping region. Leave it intact.
1845  return;
1846  }
1847 
1848  // This node isn't completely contained inside the clipping region.
1849  // Clip tiles and children, and replace any that lie outside the region
1850  // with background tiles.
1851 
1852  for (Index pos = 0; pos < NUM_VALUES; ++pos) {
1853  const Coord xyz = this->offsetToGlobalCoord(pos); // tile or child origin
1854  CoordBBox tileBBox(xyz, xyz.offsetBy(ChildT::DIM - 1)); // tile or child bounds
1855  if (!clipBBox.hasOverlap(tileBBox)) {
1856  // This table entry lies completely outside the clipping region.
1857  // Replace it with a background tile.
1858  this->makeChildNodeEmpty(pos, background);
1859  mValueMask.setOff(pos);
1860  } else if (!clipBBox.isInside(tileBBox)) {
1861  // This table entry does not lie completely inside the clipping region
1862  // and must be clipped.
1863  if (this->isChildMaskOn(pos)) {
1864  mNodes[pos].getChild()->clip(clipBBox, background);
1865  } else {
1866  // Replace this tile with a background tile, then fill the clip region
1867  // with the tile's original value. (This might create a child branch.)
1868  tileBBox.intersect(clipBBox);
1869  const ValueType val = mNodes[pos].getValue();
1870  const bool on = this->isValueMaskOn(pos);
1871  mNodes[pos].setValue(background);
1872  mValueMask.setOff(pos);
1873  this->fill(tileBBox, val, on);
1874  }
1875  } else {
1876  // This table entry lies completely inside the clipping region. Leave it intact.
1877  }
1878  }
1879 }
1880 
1881 
1883 
1884 
1885 template<typename ChildT, Index Log2Dim>
1886 inline void
1887 InternalNode<ChildT, Log2Dim>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1888 {
1889  Coord xyz, tileMin, tileMax;
1890  for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
1891  xyz.setX(x);
1892  for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
1893  xyz.setY(y);
1894  for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
1895  xyz.setZ(z);
1896 
1897  // Get the bounds of the tile that contains voxel (x, y, z).
1898  const Index n = this->coordToOffset(xyz);
1899  tileMin = this->offsetToGlobalCoord(n);
1900  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
1901 
1902  if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
1903  // If the box defined by (xyz, bbox.max()) doesn't completely enclose
1904  // the tile to which xyz belongs, create a child node (or retrieve
1905  // the existing one).
1906  ChildT* child = NULL;
1907  if (this->isChildMaskOff(n)) {
1908  // Replace the tile with a newly-created child that is initialized
1909  // with the tile's value and active state.
1910  child = new ChildT(xyz, mNodes[n].getValue(), this->isValueMaskOn(n));
1911  this->setChildNode(n, child);
1912  } else {
1913  child = mNodes[n].getChild();
1914  }
1915 
1916  // Forward the fill request to the child.
1917  if (child) {
1918  child->fill(CoordBBox(xyz, Coord::minComponent(bbox.max(), tileMax)),
1919  value, active);
1920  }
1921 
1922  } else {
1923  // If the box given by (xyz, bbox.max()) completely encloses
1924  // the tile to which xyz belongs, create the tile (if it
1925  // doesn't already exist) and give it the fill value.
1926  this->makeChildNodeEmpty(n, value);
1927  mValueMask.set(n, active);
1928  }
1929  }
1930  }
1931  }
1932 }
1933 
1934 
1936 
1937 
1938 template<typename ChildT, Index Log2Dim>
1939 template<typename DenseT>
1940 inline void
1941 InternalNode<ChildT, Log2Dim>::copyToDense(const CoordBBox& bbox, DenseT& dense) const
1942 {
1943  typedef typename DenseT::ValueType DenseValueType;
1944 
1945  const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
1946  const Coord& min = dense.bbox().min();
1947  for (Coord xyz = bbox.min(), max; xyz[0] <= bbox.max()[0]; xyz[0] = max[0] + 1) {
1948  for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = max[1] + 1) {
1949  for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = max[2] + 1) {
1950  const Index n = this->coordToOffset(xyz);
1951  // Get max coordinates of the child node that contains voxel xyz.
1952  max = this->offsetToGlobalCoord(n).offsetBy(ChildT::DIM-1);
1953 
1954  // Get the bbox of the interection of bbox and the child node
1955  CoordBBox sub(xyz, Coord::minComponent(bbox.max(), max));
1956 
1957  if (this->isChildMaskOn(n)) {//is a child
1958  mNodes[n].getChild()->copyToDense(sub, dense);
1959  } else {//a tile value
1960  const ValueType value = mNodes[n].getValue();
1961  sub.translate(-min);
1962  DenseValueType* a0 = dense.data() + zStride*sub.min()[2];
1963  for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
1964  DenseValueType* a1 = a0 + x*xStride;
1965  for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
1966  DenseValueType* a2 = a1 + y*yStride;
1967  for (Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z, a2 += zStride) {
1968  *a2 = DenseValueType(value);
1969  }
1970  }
1971  }
1972  }
1973  }
1974  }
1975  }
1976 }
1977 
1978 
1980 
1981 
1982 template<typename ChildT, Index Log2Dim>
1983 inline void
1984 InternalNode<ChildT, Log2Dim>::writeTopology(std::ostream& os, bool toHalf) const
1985 {
1986  mChildMask.save(os);
1987  mValueMask.save(os);
1988 
1989  {
1990  // Copy all of this node's values into an array.
1991  boost::shared_array<ValueType> values(new ValueType[NUM_VALUES]);
1992  const ValueType zero = zeroVal<ValueType>();
1993  for (Index i = 0; i < NUM_VALUES; ++i) {
1994  values[i] = (mChildMask.isOff(i) ? mNodes[i].getValue() : zero);
1995  }
1996  // Compress (optionally) and write out the contents of the array.
1997  io::writeCompressedValues(os, values.get(), NUM_VALUES, mValueMask, mChildMask, toHalf);
1998  }
1999  // Write out the child nodes in order.
2000  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2001  iter->writeTopology(os, toHalf);
2002  }
2003 }
2004 
2005 
2006 template<typename ChildT, Index Log2Dim>
2007 inline void
2008 InternalNode<ChildT, Log2Dim>::readTopology(std::istream& is, bool fromHalf)
2009 {
2010 #ifndef OPENVDB_2_ABI_COMPATIBLE
2011  const ValueType background = (!io::getGridBackgroundValuePtr(is) ? zeroVal<ValueType>()
2012  : *static_cast<const ValueType*>(io::getGridBackgroundValuePtr(is)));
2013 #endif
2014 
2015  mChildMask.load(is);
2016  mValueMask.load(is);
2017 
2019  for (Index i = 0; i < NUM_VALUES; ++i) {
2020  if (this->isChildMaskOn(i)) {
2021  ChildNodeType* child =
2022 #ifdef OPENVDB_2_ABI_COMPATIBLE
2023  new ChildNodeType(offsetToGlobalCoord(i), zeroVal<ValueType>());
2024 #else
2025  new ChildNodeType(PartialCreate(), offsetToGlobalCoord(i), background);
2026 #endif
2027  mNodes[i].setChild(child);
2028  child->readTopology(is);
2029  } else {
2030  ValueType value;
2031  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2032  mNodes[i].setValue(value);
2033  }
2034  }
2035  } else {
2036  const bool oldVersion =
2038  const Index numValues = (oldVersion ? mChildMask.countOff() : NUM_VALUES);
2039  {
2040  // Read in (and uncompress, if necessary) all of this node's values
2041  // into a contiguous array.
2042  boost::shared_array<ValueType> values(new ValueType[numValues]);
2043  io::readCompressedValues(is, values.get(), numValues, mValueMask, fromHalf);
2044 
2045  // Copy values from the array into this node's table.
2046  if (oldVersion) {
2047  Index n = 0;
2048  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
2049  mNodes[iter.pos()].setValue(values[n++]);
2050  }
2051  assert(n == numValues);
2052  } else {
2053  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
2054  mNodes[iter.pos()].setValue(values[iter.pos()]);
2055  }
2056  }
2057  }
2058  // Read in all child nodes and insert them into the table at their proper locations.
2059  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2060 #ifdef OPENVDB_2_ABI_COMPATIBLE
2061  ChildNodeType* child = new ChildNodeType(iter.getCoord(), zeroVal<ValueType>());
2062 #else
2063  ChildNodeType* child = new ChildNodeType(PartialCreate(), iter.getCoord(), background);
2064 #endif
2065  mNodes[iter.pos()].setChild(child);
2066  child->readTopology(is, fromHalf);
2067  }
2068  }
2069 }
2070 
2071 
2073 
2074 
2075 template<typename ChildT, Index Log2Dim>
2076 inline const typename ChildT::ValueType&
2078 {
2079  return (this->isChildMaskOn(0) ? mNodes[0].getChild()->getFirstValue() : mNodes[0].getValue());
2080 }
2081 
2082 
2083 template<typename ChildT, Index Log2Dim>
2084 inline const typename ChildT::ValueType&
2086 {
2087  const Index n = NUM_VALUES - 1;
2088  return (this->isChildMaskOn(n) ? mNodes[n].getChild()->getLastValue() : mNodes[n].getValue());
2089 }
2090 
2091 
2093 
2094 
2095 template<typename ChildT, Index Log2Dim>
2096 inline void
2098 {
2099  for (Index i = 0; i < NUM_VALUES; ++i) {
2100  if (this->isChildMaskOn(i)) {
2101  mNodes[i].getChild()->negate();
2102  } else {
2103  mNodes[i].setValue(math::negative(mNodes[i].getValue()));
2104  }
2105  }
2106 
2107 }
2108 
2109 
2110 template<typename ChildT, Index Log2Dim>
2111 inline void
2113 {
2114  for (ValueOnIter iter = this->beginValueOn(); iter; ++iter) {
2115  this->setChildNode(iter.pos(), new ChildNodeType(iter.getCoord(), iter.getValue(), true));
2116  }
2117  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) iter->voxelizeActiveTiles();
2118 }
2119 
2120 
2122 
2123 
2124 template<typename ChildT, Index Log2Dim>
2125 template<MergePolicy Policy>
2126 inline void
2128  const ValueType& background, const ValueType& otherBackground)
2129 {
2131 
2132  switch (Policy) {
2133 
2134  case MERGE_ACTIVE_STATES:
2135  default:
2136  {
2137  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2138  const Index n = iter.pos();
2139  if (mChildMask.isOn(n)) {
2140  // Merge this node's child with the other node's child.
2141  mNodes[n].getChild()->template merge<MERGE_ACTIVE_STATES>(*iter,
2142  background, otherBackground);
2143  } else if (mValueMask.isOff(n)) {
2144  // Replace this node's inactive tile with the other node's child
2145  // and replace the other node's child with a tile of undefined value
2146  // (which is okay since the other tree is assumed to be cannibalized
2147  // in the process of merging).
2148  ChildNodeType* child = other.mNodes[n].getChild();
2149  other.mChildMask.setOff(n);
2150  child->resetBackground(otherBackground, background);
2151  this->setChildNode(n, child);
2152  }
2153  }
2154 
2155  // Copy active tile values.
2156  for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
2157  const Index n = iter.pos();
2158  if (mValueMask.isOff(n)) {
2159  // Replace this node's child or inactive tile with the other node's active tile.
2160  this->makeChildNodeEmpty(n, iter.getValue());
2161  mValueMask.setOn(n);
2162  }
2163  }
2164  break;
2165  }
2166 
2167  case MERGE_NODES:
2168  {
2169  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2170  const Index n = iter.pos();
2171  if (mChildMask.isOn(n)) {
2172  // Merge this node's child with the other node's child.
2173  mNodes[n].getChild()->template merge<Policy>(*iter, background, otherBackground);
2174  } else {
2175  // Replace this node's tile (regardless of its active state) with
2176  // the other node's child and replace the other node's child with
2177  // a tile of undefined value (which is okay since the other tree
2178  // is assumed to be cannibalized in the process of merging).
2179  ChildNodeType* child = other.mNodes[n].getChild();
2180  other.mChildMask.setOff(n);
2181  child->resetBackground(otherBackground, background);
2182  this->setChildNode(n, child);
2183  }
2184  }
2185  break;
2186  }
2187 
2189  {
2190  // Transfer children from the other tree to this tree.
2191  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2192  const Index n = iter.pos();
2193  if (mChildMask.isOn(n)) {
2194  // Merge this node's child with the other node's child.
2195  mNodes[n].getChild()->template merge<Policy>(*iter, background, otherBackground);
2196  } else {
2197  // Replace this node's tile with the other node's child, leaving the other
2198  // node with an inactive tile of undefined value (which is okay since
2199  // the other tree is assumed to be cannibalized in the process of merging).
2200  ChildNodeType* child = other.mNodes[n].getChild();
2201  other.mChildMask.setOff(n);
2202  child->resetBackground(otherBackground, background);
2203  if (mValueMask.isOn(n)) {
2204  // Merge the child with this node's active tile.
2205  child->template merge<Policy>(mNodes[n].getValue(), /*on=*/true);
2206  mValueMask.setOff(n);
2207  }
2208  mChildMask.setOn(n);
2209  mNodes[n].setChild(child);
2210  }
2211  }
2212 
2213  // Merge active tiles into this tree.
2214  for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
2215  const Index n = iter.pos();
2216  if (mChildMask.isOn(n)) {
2217  // Merge the other node's active tile into this node's child.
2218  mNodes[n].getChild()->template merge<Policy>(iter.getValue(), /*on=*/true);
2219  } else if (mValueMask.isOff(n)) {
2220  // Replace this node's inactive tile with the other node's active tile.
2221  mNodes[n].setValue(iter.getValue());
2222  mValueMask.setOn(n);
2223  }
2224  }
2225  break;
2226  }
2227 
2228  }
2230 }
2231 
2232 
2233 template<typename ChildT, Index Log2Dim>
2234 template<MergePolicy Policy>
2235 inline void
2236 InternalNode<ChildT, Log2Dim>::merge(const ValueType& tileValue, bool tileActive)
2237 {
2239 
2240  if (Policy != MERGE_ACTIVE_STATES_AND_NODES) return;
2241 
2242  // For MERGE_ACTIVE_STATES_AND_NODES, inactive tiles in the other tree are ignored.
2243  if (!tileActive) return;
2244 
2245  // Iterate over this node's children and inactive tiles.
2246  for (ValueOffIter iter = this->beginValueOff(); iter; ++iter) {
2247  const Index n = iter.pos();
2248  if (mChildMask.isOn(n)) {
2249  // Merge the other node's active tile into this node's child.
2250  mNodes[n].getChild()->template merge<Policy>(tileValue, /*on=*/true);
2251  } else {
2252  // Replace this node's inactive tile with the other node's active tile.
2253  iter.setValue(tileValue);
2254  mValueMask.setOn(n);
2255  }
2256  }
2258 }
2259 
2260 
2262 
2263 
2264 template<typename ChildT, Index Log2Dim>
2265 template<typename OtherChildT>
2266 inline void
2268 {
2269  typedef typename InternalNode<OtherChildT, Log2Dim>::ChildOnCIter OtherChildIter;
2270  typedef typename InternalNode<OtherChildT, Log2Dim>::ValueOnCIter OtherValueIter;
2271 
2272  // Loop over other node's child nodes
2273  for (OtherChildIter iter = other.cbeginChildOn(); iter; ++iter) {
2274  const Index i = iter.pos();
2275  if (mChildMask.isOn(i)) {//this has a child node
2276  mNodes[i].getChild()->topologyUnion(*iter);
2277  } else {// this is a tile so replace it with a child branch with identical topology
2278  ChildNodeType* child = new ChildNodeType(*iter, mNodes[i].getValue(), TopologyCopy());
2279  if (mValueMask.isOn(i)) {
2280  mValueMask.isOff(i);//we're replacing the active tile with a child branch
2281  child->setValuesOn();//activate all values since it was an active tile
2282  }
2283  mChildMask.setOn(i);
2284  mNodes[i].setChild(child);
2285  }
2286  }
2287  // Loop over other node's active tiles
2288  for (OtherValueIter iter = other.cbeginValueOn(); iter; ++iter) {
2289  const Index i = iter.pos();
2290  if (mChildMask.isOn(i)) {
2291  mNodes[i].getChild()->setValuesOn();
2292  } else if (mValueMask.isOff(i)) { //inactive tile
2293  mValueMask.setOn(i);
2294  }
2295  }
2296 }
2297 
2298 template<typename ChildT, Index Log2Dim>
2299 template<typename OtherChildT>
2300 inline void
2302  const ValueType& background)
2303 {
2304  // Loop over this node's child nodes
2305  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2306  const Index i = iter.pos();
2307  if (other.mChildMask.isOn(i)) {//other also has a child node
2308  iter->topologyIntersection(*(other.mNodes[i].getChild()), background);
2309  } else if (other.mValueMask.isOff(i)) {//other is an inactive tile
2310  delete mNodes[i].getChild();//convert child to an inactive tile
2311  mNodes[i].setValue(background);
2312  mChildMask.setOff(i);
2313  mValueMask.setOff(i);
2314  }
2315  }
2316 
2317  // Loop over this node's active tiles
2318  for (ValueOnCIter iter = this->cbeginValueOn(); iter; ++iter) {
2319  const Index i = iter.pos();
2320  if (other.mChildMask.isOn(i)) {//other has a child node
2321  ChildNodeType* child = new ChildNodeType(*(other.mNodes[i].getChild()),
2322  *iter, TopologyCopy());
2323  this->setChildNode(i, child);//replace the active tile with a child branch
2324  } else if (other.mValueMask.isOff(i)) {//other is an inactive tile
2325  mValueMask.setOff(i);//convert active tile to an inactive tile
2326  }
2327  }
2328 }
2329 
2330 template<typename ChildT, Index Log2Dim>
2331 template<typename OtherChildT>
2332 inline void
2334  const ValueType& background)
2335 {
2336  typedef typename InternalNode<OtherChildT, Log2Dim>::ChildOnCIter OtherChildIter;
2337  typedef typename InternalNode<OtherChildT, Log2Dim>::ValueOnCIter OtherValueIter;
2338 
2339  // Loop over other node's child nodes
2340  for (OtherChildIter iter = other.cbeginChildOn(); iter; ++iter) {
2341  const Index i = iter.pos();
2342  if (mChildMask.isOn(i)) {//this has a child node
2343  mNodes[i].getChild()->topologyDifference(*iter, background);
2344  } else if (mValueMask.isOn(i)) {// this is an active tile
2345  ChildNodeType* child = new ChildNodeType(iter.getCoord(), mNodes[i].getValue(), true);
2346  child->topologyDifference(*iter, background);
2347  this->setChildNode(i, child);//we're replacing the active tile with a child branch
2348  }
2349  }
2350 
2351  // Loop over other node's active tiles
2352  for (OtherValueIter iter = other.cbeginValueOn(); iter; ++iter) {
2353  const Index i = iter.pos();
2354  if (mChildMask.isOn(i)) {//this has a child node
2355  delete mNodes[i].getChild();//convert child to an inactive tile
2356  mNodes[i].setValue(background);
2357  mChildMask.setOff(i);
2358  mValueMask.setOff(i);
2359  } else if (mValueMask.isOn(i)) {//this is an active tile
2360  mValueMask.setOff(i);//convert active tile to an inactive tile
2361  }
2362  }
2363 }
2364 
2366 
2367 
2368 template<typename ChildT, Index Log2Dim>
2369 template<typename CombineOp>
2370 inline void
2372 {
2373  const ValueType zero = zeroVal<ValueType>();
2374 
2376 
2377  for (Index i = 0; i < NUM_VALUES; ++i) {
2378  if (this->isChildMaskOff(i) && other.isChildMaskOff(i)) {
2379  // Both this node and the other node have constant values (tiles).
2380  // Combine the two values and store the result as this node's new tile value.
2381  op(args.setARef(mNodes[i].getValue())
2382  .setAIsActive(isValueMaskOn(i))
2383  .setBRef(other.mNodes[i].getValue())
2384  .setBIsActive(other.isValueMaskOn(i)));
2385  mNodes[i].setValue(args.result());
2386  mValueMask.set(i, args.resultIsActive());
2387  } else if (this->isChildMaskOn(i) && other.isChildMaskOff(i)) {
2388  // Combine this node's child with the other node's constant value.
2389  ChildNodeType* child = mNodes[i].getChild();
2390  assert(child);
2391  if (child) {
2392  child->combine(other.mNodes[i].getValue(), other.isValueMaskOn(i), op);
2393  }
2394  } else if (this->isChildMaskOff(i) && other.isChildMaskOn(i)) {
2395  // Combine this node's constant value with the other node's child.
2396  ChildNodeType* child = other.mNodes[i].getChild();
2397  assert(child);
2398  if (child) {
2399  // Combine this node's constant value with the other node's child,
2400  // but use a new functor in which the A and B values are swapped,
2401  // since the constant value is the A value, not the B value.
2403  child->combine(mNodes[i].getValue(), isValueMaskOn(i), swappedOp);
2404 
2405  // Steal the other node's child.
2406  other.mChildMask.setOff(i);
2407  other.mNodes[i].setValue(zero);
2408  this->setChildNode(i, child);
2409  }
2410 
2411  } else /*if (isChildMaskOn(i) && other.isChildMaskOn(i))*/ {
2412  // Combine this node's child with the other node's child.
2413  ChildNodeType
2414  *child = mNodes[i].getChild(),
2415  *otherChild = other.mNodes[i].getChild();
2416  assert(child);
2417  assert(otherChild);
2418  if (child && otherChild) {
2419  child->combine(*otherChild, op);
2420  }
2421  }
2422  }
2423 }
2424 
2425 
2426 template<typename ChildT, Index Log2Dim>
2427 template<typename CombineOp>
2428 inline void
2429 InternalNode<ChildT, Log2Dim>::combine(const ValueType& value, bool valueIsActive, CombineOp& op)
2430 {
2432 
2433  for (Index i = 0; i < NUM_VALUES; ++i) {
2434  if (this->isChildMaskOff(i)) {
2435  // Combine this node's constant value with the given constant value.
2436  op(args.setARef(mNodes[i].getValue())
2437  .setAIsActive(isValueMaskOn(i))
2438  .setBRef(value)
2439  .setBIsActive(valueIsActive));
2440  mNodes[i].setValue(args.result());
2441  mValueMask.set(i, args.resultIsActive());
2442  } else /*if (isChildMaskOn(i))*/ {
2443  // Combine this node's child with the given constant value.
2444  ChildNodeType* child = mNodes[i].getChild();
2445  assert(child);
2446  if (child) child->combine(value, valueIsActive, op);
2447  }
2448  }
2449 }
2450 
2451 
2453 
2454 
2455 template<typename ChildT, Index Log2Dim>
2456 template<typename CombineOp, typename OtherNodeType>
2457 inline void
2458 InternalNode<ChildT, Log2Dim>::combine2(const InternalNode& other0, const OtherNodeType& other1,
2459  CombineOp& op)
2460 {
2462 
2463  for (Index i = 0; i < NUM_VALUES; ++i) {
2464  if (other0.isChildMaskOff(i) && other1.isChildMaskOff(i)) {
2465  op(args.setARef(other0.mNodes[i].getValue())
2466  .setAIsActive(other0.isValueMaskOn(i))
2467  .setBRef(other1.mNodes[i].getValue())
2468  .setBIsActive(other1.isValueMaskOn(i)));
2469  // Replace child i with a constant value.
2470  this->makeChildNodeEmpty(i, args.result());
2471  mValueMask.set(i, args.resultIsActive());
2472  } else {
2473  if (this->isChildMaskOff(i)) {
2474  // Add a new child with the same coordinates, etc. as the other node's child.
2475  const Coord& childOrigin = other0.isChildMaskOn(i)
2476  ? other0.mNodes[i].getChild()->origin()
2477  : other1.mNodes[i].getChild()->origin();
2478  this->setChildNode(i, new ChildNodeType(childOrigin, mNodes[i].getValue()));
2479  }
2480 
2481  if (other0.isChildMaskOff(i)) {
2482  // Combine node1's child with node0's constant value
2483  // and write the result into child i.
2484  mNodes[i].getChild()->combine2(other0.mNodes[i].getValue(),
2485  *other1.mNodes[i].getChild(), other0.isValueMaskOn(i), op);
2486  } else if (other1.isChildMaskOff(i)) {
2487  // Combine node0's child with node1's constant value
2488  // and write the result into child i.
2489  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2490  other1.mNodes[i].getValue(), other1.isValueMaskOn(i), op);
2491  } else {
2492  // Combine node0's child with node1's child
2493  // and write the result into child i.
2494  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2495  *other1.mNodes[i].getChild(), op);
2496  }
2497  }
2498  }
2499 }
2500 
2501 
2502 template<typename ChildT, Index Log2Dim>
2503 template<typename CombineOp, typename OtherNodeType>
2504 inline void
2505 InternalNode<ChildT, Log2Dim>::combine2(const ValueType& value, const OtherNodeType& other,
2506  bool valueIsActive, CombineOp& op)
2507 {
2509 
2510  for (Index i = 0; i < NUM_VALUES; ++i) {
2511  if (other.isChildMaskOff(i)) {
2512  op(args.setARef(value)
2513  .setAIsActive(valueIsActive)
2514  .setBRef(other.mNodes[i].getValue())
2515  .setBIsActive(other.isValueMaskOn(i)));
2516  // Replace child i with a constant value.
2517  this->makeChildNodeEmpty(i, args.result());
2518  mValueMask.set(i, args.resultIsActive());
2519  } else {
2520  typename OtherNodeType::ChildNodeType* otherChild = other.mNodes[i].getChild();
2521  assert(otherChild);
2522  if (this->isChildMaskOff(i)) {
2523  // Add a new child with the same coordinates, etc.
2524  // as the other node's child.
2525  this->setChildNode(i, new ChildNodeType(*otherChild));
2526  }
2527  // Combine the other node's child with a constant value
2528  // and write the result into child i.
2529  mNodes[i].getChild()->combine2(value, *otherChild, valueIsActive, op);
2530  }
2531  }
2532 }
2533 
2534 
2535 template<typename ChildT, Index Log2Dim>
2536 template<typename CombineOp, typename OtherValueType>
2537 inline void
2538 InternalNode<ChildT, Log2Dim>::combine2(const InternalNode& other, const OtherValueType& value,
2539  bool valueIsActive, CombineOp& op)
2540 {
2542 
2543  for (Index i = 0; i < NUM_VALUES; ++i) {
2544  if (other.isChildMaskOff(i)) {
2545  op(args.setARef(other.mNodes[i].getValue())
2546  .setAIsActive(other.isValueMaskOn(i))
2547  .setBRef(value)
2548  .setBIsActive(valueIsActive));
2549  // Replace child i with a constant value.
2550  this->makeChildNodeEmpty(i, args.result());
2551  mValueMask.set(i, args.resultIsActive());
2552  } else {
2553  ChildNodeType* otherChild = other.mNodes[i].getChild();
2554  assert(otherChild);
2555  if (this->isChildMaskOff(i)) {
2556  // Add a new child with the same coordinates, etc. as the other node's child.
2557  this->setChildNode(i,
2558  new ChildNodeType(otherChild->origin(), mNodes[i].getValue()));
2559  }
2560  // Combine the other node's child with a constant value
2561  // and write the result into child i.
2562  mNodes[i].getChild()->combine2(*otherChild, value, valueIsActive, op);
2563  }
2564  }
2565 }
2566 
2567 
2569 
2570 
2571 template<typename ChildT, Index Log2Dim>
2572 template<typename BBoxOp>
2573 inline void
2575 {
2576  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) {
2577 #ifdef _MSC_VER
2578  op.operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
2579 #else
2580  op.template operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
2581 #endif
2582  }
2583  if (op.template descent<LEVEL>()) {
2584  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) i->visitActiveBBox(op);
2585  } else {
2586  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) {
2587 #ifdef _MSC_VER
2588  op.operator()<LEVEL>(i->getNodeBoundingBox());
2589 #else
2590  op.template operator()<LEVEL>(i->getNodeBoundingBox());
2591 #endif
2592  }
2593  }
2594 }
2595 
2596 
2597 template<typename ChildT, Index Log2Dim>
2598 template<typename VisitorOp>
2599 inline void
2601 {
2602  doVisit<InternalNode, VisitorOp, ChildAllIter>(*this, op);
2603 }
2604 
2605 
2606 template<typename ChildT, Index Log2Dim>
2607 template<typename VisitorOp>
2608 inline void
2610 {
2611  doVisit<const InternalNode, VisitorOp, ChildAllCIter>(*this, op);
2612 }
2613 
2614 
2615 template<typename ChildT, Index Log2Dim>
2616 template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
2617 inline void
2618 InternalNode<ChildT, Log2Dim>::doVisit(NodeT& self, VisitorOp& op)
2619 {
2620  typename NodeT::ValueType val;
2621  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2622  if (op(iter)) continue;
2623  if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
2624  child->visit(op);
2625  }
2626  }
2627 }
2628 
2629 
2631 
2632 
2633 template<typename ChildT, Index Log2Dim>
2634 template<typename OtherNodeType, typename VisitorOp>
2635 inline void
2636 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op)
2637 {
2638  doVisit2Node<InternalNode, OtherNodeType, VisitorOp, ChildAllIter,
2639  typename OtherNodeType::ChildAllIter>(*this, other, op);
2640 }
2641 
2642 
2643 template<typename ChildT, Index Log2Dim>
2644 template<typename OtherNodeType, typename VisitorOp>
2645 inline void
2646 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op) const
2647 {
2648  doVisit2Node<const InternalNode, OtherNodeType, VisitorOp, ChildAllCIter,
2649  typename OtherNodeType::ChildAllCIter>(*this, other, op);
2650 }
2651 
2652 
2653 template<typename ChildT, Index Log2Dim>
2654 template<
2655  typename NodeT,
2656  typename OtherNodeT,
2657  typename VisitorOp,
2658  typename ChildAllIterT,
2659  typename OtherChildAllIterT>
2660 inline void
2661 InternalNode<ChildT, Log2Dim>::doVisit2Node(NodeT& self, OtherNodeT& other, VisitorOp& op)
2662 {
2663  // Allow the two nodes to have different ValueTypes, but not different dimensions.
2664  BOOST_STATIC_ASSERT(OtherNodeT::NUM_VALUES == NodeT::NUM_VALUES);
2665  BOOST_STATIC_ASSERT(OtherNodeT::LEVEL == NodeT::LEVEL);
2666 
2667  typename NodeT::ValueType val;
2668  typename OtherNodeT::ValueType otherVal;
2669 
2670  ChildAllIterT iter = self.beginChildAll();
2671  OtherChildAllIterT otherIter = other.beginChildAll();
2672 
2673  for ( ; iter && otherIter; ++iter, ++otherIter)
2674  {
2675  const size_t skipBranch = static_cast<size_t>(op(iter, otherIter));
2676 
2677  typename ChildAllIterT::ChildNodeType* child =
2678  (skipBranch & 1U) ? NULL : iter.probeChild(val);
2679  typename OtherChildAllIterT::ChildNodeType* otherChild =
2680  (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
2681 
2682  if (child != NULL && otherChild != NULL) {
2683  child->visit2Node(*otherChild, op);
2684  } else if (child != NULL) {
2685  child->visit2(otherIter, op);
2686  } else if (otherChild != NULL) {
2687  otherChild->visit2(iter, op, /*otherIsLHS=*/true);
2688  }
2689  }
2690 }
2691 
2692 
2694 
2695 
2696 template<typename ChildT, Index Log2Dim>
2697 template<typename OtherChildAllIterType, typename VisitorOp>
2698 inline void
2699 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
2700  VisitorOp& op, bool otherIsLHS)
2701 {
2702  doVisit2<InternalNode, VisitorOp, ChildAllIter, OtherChildAllIterType>(
2703  *this, otherIter, op, otherIsLHS);
2704 }
2705 
2706 
2707 template<typename ChildT, Index Log2Dim>
2708 template<typename OtherChildAllIterType, typename VisitorOp>
2709 inline void
2710 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
2711  VisitorOp& op, bool otherIsLHS) const
2712 {
2713  doVisit2<const InternalNode, VisitorOp, ChildAllCIter, OtherChildAllIterType>(
2714  *this, otherIter, op, otherIsLHS);
2715 }
2716 
2717 
2718 template<typename ChildT, Index Log2Dim>
2719 template<typename NodeT, typename VisitorOp, typename ChildAllIterT, typename OtherChildAllIterT>
2720 inline void
2721 InternalNode<ChildT, Log2Dim>::doVisit2(NodeT& self, OtherChildAllIterT& otherIter,
2722  VisitorOp& op, bool otherIsLHS)
2723 {
2724  if (!otherIter) return;
2725 
2726  const size_t skipBitMask = (otherIsLHS ? 2U : 1U);
2727 
2728  typename NodeT::ValueType val;
2729  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2730  const size_t skipBranch = static_cast<size_t>(
2731  otherIsLHS ? op(otherIter, iter) : op(iter, otherIter));
2732 
2733  typename ChildAllIterT::ChildNodeType* child =
2734  (skipBranch & skipBitMask) ? NULL : iter.probeChild(val);
2735 
2736  if (child != NULL) child->visit2(otherIter, op, otherIsLHS);
2737  }
2738 }
2739 
2740 
2742 
2743 
2744 template<typename ChildT, Index Log2Dim>
2745 inline void
2746 InternalNode<ChildT, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
2747 {
2748  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2749  iter->writeBuffers(os, toHalf);
2750  }
2751 }
2752 
2753 
2754 template<typename ChildT, Index Log2Dim>
2755 inline void
2756 InternalNode<ChildT, Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
2757 {
2758  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2759  iter->readBuffers(is, fromHalf);
2760  }
2761 }
2762 
2763 
2764 template<typename ChildT, Index Log2Dim>
2765 inline void
2767  const CoordBBox& clipBBox, bool fromHalf)
2768 {
2769  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2770  // Stream in the branch rooted at this child.
2771  // (We can't skip over children that lie outside the clipping region,
2772  // because buffers are serialized in depth-first order and need to be
2773  // unserialized in the same order.)
2774  iter->readBuffers(is, clipBBox, fromHalf);
2775  }
2776 
2777  // Get this tree's background value.
2778  ValueType background = zeroVal<ValueType>();
2779  if (const void* bgPtr = io::getGridBackgroundValuePtr(is)) {
2780  background = *static_cast<const ValueType*>(bgPtr);
2781  }
2782  this->clip(clipBBox, background);
2783 }
2784 
2785 
2787 
2788 
2789 template<typename ChildT, Index Log2Dim>
2790 void
2792 {
2793  dims.push_back(Log2Dim);
2794  ChildNodeType::getNodeLog2Dims(dims);
2795 }
2796 
2797 
2798 template<typename ChildT, Index Log2Dim>
2799 inline void
2801 {
2802  assert(n<(1<<3*Log2Dim));
2803  xyz.setX(n >> 2*Log2Dim);
2804  n &= ((1<<2*Log2Dim)-1);
2805  xyz.setY(n >> Log2Dim);
2806  xyz.setZ(n & ((1<<Log2Dim)-1));
2807 }
2808 
2809 
2810 template<typename ChildT, Index Log2Dim>
2811 inline Index
2813 {
2814  return (((xyz[0] & (DIM-1u)) >> ChildNodeType::TOTAL) << 2*Log2Dim)
2815  + (((xyz[1] & (DIM-1u)) >> ChildNodeType::TOTAL) << Log2Dim)
2816  + ((xyz[2] & (DIM-1u)) >> ChildNodeType::TOTAL);
2817 }
2818 
2819 
2820 template<typename ChildT, Index Log2Dim>
2821 inline Coord
2823 {
2824  Coord local;
2825  this->offsetToLocalCoord(n, local);
2826  local <<= ChildT::TOTAL;
2827  return local + this->origin();
2828 }
2829 
2831 
2832 template<typename ChildT, Index Log2Dim>
2833 template<typename ArrayT>
2834 inline void
2836 {
2837  typedef typename ArrayT::value_type T;
2838  BOOST_STATIC_ASSERT(boost::is_pointer<T>::value);
2839  typedef typename boost::mpl::if_<boost::is_const<typename boost::remove_pointer<T>::type>,
2840  const ChildT, ChildT>::type ArrayChildT;
2841  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2843  if (boost::is_same<T, ArrayChildT*>::value) {
2844  array.push_back(reinterpret_cast<T>(mNodes[iter.pos()].getChild()));
2845  } else {
2846  iter->getNodes(array);//descent
2847  }
2849  }
2850 }
2851 
2852 template<typename ChildT, Index Log2Dim>
2853 template<typename ArrayT>
2854 inline void
2856 {
2857  typedef typename ArrayT::value_type T;
2858  BOOST_STATIC_ASSERT(boost::is_pointer<T>::value);
2859  BOOST_STATIC_ASSERT(boost::is_const<typename boost::remove_pointer<T>::type>::value);
2860  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2862  if (boost::is_same<T, const ChildT*>::value) {
2863  array.push_back(reinterpret_cast<T>(mNodes[iter.pos()].getChild()));
2864  } else {
2865  iter->getNodes(array);//descent
2866  }
2868  }
2869 }
2870 
2872 
2873 
2874 template<typename ChildT, Index Log2Dim>
2875 inline void
2876 InternalNode<ChildT, Log2Dim>::resetBackground(const ValueType& oldBackground,
2877  const ValueType& newBackground)
2878 {
2879  if (math::isExactlyEqual(oldBackground, newBackground)) return;
2880  for (Index i = 0; i < NUM_VALUES; ++i) {
2881  if (this->isChildMaskOn(i)) {
2882  mNodes[i].getChild()->resetBackground(oldBackground, newBackground);
2883  } else if (this->isValueMaskOff(i)) {
2884  if (math::isApproxEqual(mNodes[i].getValue(), oldBackground)) {
2885  mNodes[i].setValue(newBackground);
2886  } else if (math::isApproxEqual(mNodes[i].getValue(), math::negative(oldBackground))) {
2887  mNodes[i].setValue(math::negative(newBackground));
2888  }
2889  }
2890  }
2891 }
2892 
2893 template<typename ChildT, Index Log2Dim>
2894 template<typename OtherChildNodeType, Index OtherLog2Dim>
2895 inline bool
2898 {
2899  if (Log2Dim != OtherLog2Dim || mChildMask != other->mChildMask ||
2900  mValueMask != other->mValueMask) return false;
2901  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2902  if (!iter->hasSameTopology(other->mNodes[iter.pos()].getChild())) return false;
2903  }
2904  return true;
2905 }
2906 
2907 
2908 template<typename ChildT, Index Log2Dim>
2909 inline void
2911 {
2912  assert(child);
2913  if (this->isChildMaskOn(i)) {
2914  delete mNodes[i].getChild();
2915  } else {
2916  mChildMask.setOn(i);
2917  mValueMask.setOff(i);
2918  }
2919  mNodes[i].setChild(child);
2920 }
2921 
2922 template<typename ChildT, Index Log2Dim>
2923 inline void
2925 {
2926  assert(child);
2927  assert(mChildMask.isOff(i));
2928  mChildMask.setOn(i);
2929  mValueMask.setOff(i);
2930  mNodes[i].setChild(child);
2931 }
2932 
2933 
2934 template<typename ChildT, Index Log2Dim>
2935 inline ChildT*
2937 {
2938  if (this->isChildMaskOff(i)) {
2939  mNodes[i].setValue(value);
2940  return NULL;
2941  }
2942  ChildNodeType* child = mNodes[i].getChild();
2943  mChildMask.setOff(i);
2944  mNodes[i].setValue(value);
2945  return child;
2946 }
2947 
2948 
2949 template<typename ChildT, Index Log2Dim>
2950 inline void
2952 {
2953  delete this->unsetChildNode(n, value);
2954 }
2955 
2956 template<typename ChildT, Index Log2Dim>
2957 inline ChildT*
2959 {
2960  assert(this->isChildMaskOn(n));
2961  return mNodes[n].getChild();
2962 }
2963 
2964 
2965 template<typename ChildT, Index Log2Dim>
2966 inline const ChildT*
2968 {
2969  assert(this->isChildMaskOn(n));
2970  return mNodes[n].getChild();
2971 }
2972 
2973 } // namespace tree
2974 } // namespace OPENVDB_VERSION_NAME
2975 } // namespace openvdb
2976 
2977 #endif // OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
2978 
2979 // Copyright (c) 2012-2014 DreamWorks Animation LLC
2980 // All rights reserved. This software is distributed under the
2981 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition: InternalNode.h:974
static Index getChildDim()
Definition: InternalNode.h:259
Definition: InternalNode.h:135
bool isValueMaskOn(Index n) const
Definition: InternalNode.h:685
virtual ~InternalNode()
Definition: InternalNode.h:877
Definition: Types.h:424
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:1458
void topologyIntersection(const InternalNode< OtherChildNodeType, Log2Dim > &other, const ValueType &background)
Intersects this tree's set of active values with the active values of the other tree, whose ValueType may be different.
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1646
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:497
const Coord & origin() const
Return the grid index coordinates of this node's local origin.
Definition: InternalNode.h:270
ChildIter< InternalNode, ChildNodeType, MaskOnIterator, ChildOn > ChildOnIter
Definition: InternalNode.h:218
void combine2(const InternalNode &other0, const OtherNodeType &other1, CombineOp &)
Definition: InternalNode.h:2458
bool isValueOn(Index offset) const
Return true if the voxel at the given offset is active.
Definition: InternalNode.h:308
ChildOnCIter cbeginChildOn() const
Definition: InternalNode.h:232
Index32 leafCount() const
Definition: InternalNode.h:890
ValueAllIter beginValueAll()
Definition: InternalNode.h:253
ChildNodeType * unsetChildNode(Index i, const ValueType &value)
Definition: InternalNode.h:2936
void visit2(IterT &otherIter, VisitorOp &, bool otherIsLHS=false)
ChildOffCIter cbeginChildOff() const
Definition: InternalNode.h:233
ChildOffCIter beginChildOff() const
Definition: InternalNode.h:236
NodeMaskType::OnIterator MaskOnIterator
Definition: InternalNode.h:129
NodeUnion< ValueType, ChildNodeType > UnionType
Definition: InternalNode.h:69
ChildIter< const InternalNode, const ChildNodeType, MaskOnIterator, ChildOn > ChildOnCIter
Definition: InternalNode.h:219
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition: InternalNode.h:2746
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition: InternalNode.h:1493
const ValueType & getValue(const Coord &xyz) const
Definition: InternalNode.h:1435
uint64_t Index64
Definition: Types.h:58
static void doVisit(NodeT &, VisitorOp &)
Definition: InternalNode.h:2618
NodeType * probeNode(const Coord &xyz)
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return NULL.
void visit(VisitorOp &)
Definition: InternalNode.h:2600
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...
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition: InternalNode.h:1424
Definition: Types.h:385
ValueIter< const InternalNode, const ValueType, MaskOffIterator, ChildOff > ChildOffCIter
Definition: InternalNode.h:221
Index32 nonLeafCount() const
Definition: InternalNode.h:903
Index pos() const
Identical to offset.
Definition: Iterator.h:94
ValueIter< InternalNode, const ValueType, MaskOffIterator, ChildOff > ChildOffIter
Definition: InternalNode.h:220
void clip(const CoordBBox &, const ValueType &background)
Set all voxels that lie outside the given axis-aligned box to the background.
Definition: InternalNode.h:1837
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates but don't change its active state.
Definition: InternalNode.h:1629
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition: InternalNode.h:1686
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don't change its value.
Definition: InternalNode.h:1524
ValueIter< const InternalNode, const ValueType, MaskOffIterator, ValueAll > ValueAllCIter
Definition: InternalNode.h:230
ValueOnCIter cbeginValueOn() const
Definition: InternalNode.h:242
ChildOnCIter beginChildOn() const
Definition: InternalNode.h:235
bool resultIsActive() const
Definition: Types.h:358
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:293
ChildIter(const MaskIterT &iter, NodeT *parent)
Definition: InternalNode.h:145
ValueOnIter beginValueOn()
Definition: InternalNode.h:250
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition: NodeMasks.h:436
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:987
static const Index NUM_VALUES
Definition: InternalNode.h:76
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:2800
NodeMaskType getValueOffMask() const
Definition: InternalNode.h:694
void fill(const CoordBBox &bbox, const ValueType &, bool active=true)
Set all voxels within an axis-aligned box to a constant value. (The min and max coordinates are inclu...
Definition: InternalNode.h:1887
static void doVisit2(NodeT &, OtherChildAllIterT &, VisitorOp &, bool otherIsLHS)
Definition: InternalNode.h:2721
CombineArgs & setARef(const AValueType &a)
Redirect the A value to a new external source.
Definition: Types.h:347
void combine(InternalNode &other, CombineOp &)
Definition: InternalNode.h:2371
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:1281
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:1029
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 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:369
void makeChildNodeEmpty(Index n, const ValueType &value)
Definition: InternalNode.h:2951
ValueIter()
Definition: InternalNode.h:164
int32_t Int32
Definition: Types.h:61
DenseIter()
Definition: InternalNode.h:188
void visit2Node(OtherNodeType &other, VisitorOp &)
Definition: InternalNode.h:2636
bool isValueMaskOff(Index n) const
Definition: InternalNode.h:687
DenseIter< const InternalNode, const ChildNodeType, ValueType, ChildAll > ChildAllCIter
Definition: InternalNode.h:223
bool isChildMaskOff() const
Definition: InternalNode.h:691
void setActiveState(const Coord &xyz, bool on)
Set the active state of the voxel at the given coordinates but don't change its value.
Definition: InternalNode.h:1667
const NodeMaskType & getValueMask() const
Definition: InternalNode.h:692
ChildNodeType * getChildNode(Index n)
Returns a pointer to the child node at the linear offset n.
Definition: InternalNode.h:2958
static void getNodeLog2Dims(std::vector< Index > &dims)
Definition: InternalNode.h:2791
bool isChildMaskOff(Index n) const
Definition: InternalNode.h:690
const ValueType & getLastValue() const
If the last entry in this node's table is a tile, return the tile's value. Otherwise, return the result of calling getLastValue() on the child.
Definition: InternalNode.h:2085
InternalNode()
Definition: InternalNode.h:99
void combine(FloatTreeT &lhsDist, IntTreeT &lhsIndex, FloatTreeT &rhsDist, IntTreeT &rhsIndex)
Definition: MeshToVolume.h:403
void negate()
Definition: InternalNode.h:2097
Definition: InternalNode.h:134
bool isEmpty() const
Definition: InternalNode.h:295
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:1249
util::NodeMask< Log2Dim > NodeMaskType
Definition: InternalNode.h:70
bool isConstant(ValueType &constValue, bool &state, const ValueType &tolerance=zeroVal< ValueType >()) const
Definition: InternalNode.h:1350
ValueIter< const InternalNode, const ValueType, MaskOnIterator, ValueOn > ValueOnCIter
Definition: InternalNode.h:226
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 NULL.
Definition: InternalNode.h:1157
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:2896
void writeCompressedValues(std::ostream &os, ValueT *srcBuf, Index srcCount, const MaskT &valueMask, const MaskT &childMask, bool toHalf)
Definition: Compression.h:411
DenseIter< InternalNode, ChildNodeType, ValueType, ChildAll > ChildAllIter
Definition: InternalNode.h:222
void setItem(Index pos, const ValueT &v) const
Definition: InternalNode.h:171
#define OPENVDB_VERSION_NAME
Definition: version.h:43
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition: InternalNode.h:1508
const ValueT & getItem(Index pos) const
Definition: InternalNode.h:168
Definition: Types.h:263
OPENVDB_API uint32_t getFormatVersion(std::ios_base &)
Return the file format version number associated with the given input stream.
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1605
void writeTopology(std::ostream &, bool toHalf=false) const
Definition: InternalNode.h:1984
Index32 Index
Definition: Types.h:59
static Index getLevel()
Definition: InternalNode.h:257
void setChildNode(Index i, ChildNodeType *child)
Definition: InternalNode.h:2924
bool isOff(Index32 n) const
Return true if the nth bit is off.
Definition: NodeMasks.h:461
ValueAllCIter beginValueAll() const
Definition: InternalNode.h:249
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:1177
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:309
void setOrigin(const Coord &origin)
Set the grid index coordinates of this node's local origin.
Definition: InternalNode.h:272
ChildAllCIter beginChildAll() const
Definition: InternalNode.h:237
void getNodes(ArrayT &array)
Adds all nodes of a certain type to a container with the following API:
Definition: InternalNode.h:2835
void readCompressedValues(std::istream &is, ValueT *destBuf, Index destCount, const MaskT &valueMask, bool fromHalf)
Definition: Compression.h:309
NodeMaskType mChildMask
Definition: InternalNode.h:735
Definition: NodeMasks.h:236
ChildNodeType::ValueType ValueType
Definition: InternalNode.h:68
Definition: Exceptions.h:39
Coord mOrigin
Global grid index coordinates (x,y,z) of the local origin of this node.
Definition: InternalNode.h:737
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition: Platform.h:121
bool isInactive() const
Return true if this node has no children and only contains inactive values.
Definition: InternalNode.h:303
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
ChildNodeType::LeafNodeType LeafNodeType
Definition: InternalNode.h:67
bool isApproxEqual(const Hermite &lhs, const Hermite &rhs)
Definition: Hermite.h:470
void unsetItem(Index pos, const ValueT &value) const
Definition: InternalNode.h:210
SameConfiguration::value is true if and only if OtherNodeType is the type of an Intern...
Definition: InternalNode.h:93
const UnionType * getTable() const
Definition: InternalNode.h:701
ChildIter()
Definition: InternalNode.h:144
void setItem(Index pos, const ChildT &c) const
Definition: InternalNode.h:155
ChildAllIter beginChildAll()
Definition: InternalNode.h:240
DenseIteratorBase< MaskDenseIterator, DenseIter, NodeT, ChildT, ValueT > BaseT
Definition: InternalNode.h:185
Index64 offVoxelCount() const
Definition: InternalNode.h:928
const AValueType & result() const
Get the output value.
Definition: Types.h:339
Base class for dense iterators over internal and leaf nodes.
Definition: Iterator.h:211
ValueConverter::Type is the type of an InternalNode having the same child hierarchy and dimensions...
Definition: InternalNode.h:84
ValueIter< InternalNode, const ValueType, MaskOnIterator, ValueOn > ValueOnIter
Definition: InternalNode.h:225
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:107
OPENVDB_STATIC_SPECIALIZATION GridType::Ptr clip(const GridType &grid, const BBoxd &)
Clip the given grid against a world-space bounding box and return a new grid containing the result...
Definition: Clip.h:364
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1560
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
Definition: NodeMasks.h:267
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:1749
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &)
Same as touchLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
Base class for sparse iterators over internal and leaf nodes.
Definition: Iterator.h:148
ValueAllCIter cbeginValueAll() const
Definition: InternalNode.h:245
void resetChildNode(Index i, ChildNodeType *child)
Definition: InternalNode.h:2910
ChildOnIter beginChildOn()
Definition: InternalNode.h:238
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...
LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as probeLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
NodeMaskType::DenseIterator MaskDenseIterator
Definition: InternalNode.h:131
void readBuffers(std::istream &, bool fromHalf=false)
Definition: InternalNode.h:2756
ChildAllCIter cbeginChildAll() const
Definition: InternalNode.h:234
Definition: InternalNode.h:63
void setValuesOn()
Mark all values (both tiles and voxels) as active.
Definition: InternalNode.h:1709
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:410
NodeMaskType::OffIterator MaskOffIterator
Definition: InternalNode.h:130
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:122
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:405
bool getItem(Index pos, ChildT *&child, NonConstValueT &value) const
Definition: InternalNode.h:192
ValueOffCIter cbeginValueOff() const
Definition: InternalNode.h:244
static Index coordToOffset(const Coord &xyz)
Return the linear table offset of the given global or local coordinates.
Definition: InternalNode.h:2812
ValueOnCIter beginValueOn() const
Definition: InternalNode.h:246
Definition: NodeMasks.h:205
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:1206
void setItem(Index pos, ChildT *child) const
Definition: InternalNode.h:204
Index64 onTileCount() const
Definition: InternalNode.h:963
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return NULL.
Definition: InternalNode.h:1131
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 NULL.
void modifyItem(Index pos, const ModifyOp &op) const
Definition: InternalNode.h:175
Definition: InternalNode.h:59
Definition: InternalNode.h:135
ValueIter< InternalNode, const ValueType, MaskOffIterator, ValueOff > ValueOffIter
Definition: InternalNode.h:227
ChildOffIter beginChildOff()
Definition: InternalNode.h:239
static void doVisit2Node(NodeT &, OtherNodeT &, VisitorOp &)
Definition: InternalNode.h:2661
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:1721
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
Index64 offLeafVoxelCount() const
Definition: InternalNode.h:952
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition: Math.h:391
Index64 onLeafVoxelCount() const
Definition: InternalNode.h:940
NodeType * probeNodeAndCache(const Coord &xyz, AccessorT &)
Same as probeNode() except, if necessary, update the accessor with pointers to the nodes along the pa...
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: InternalNode.h:1783
_ChildNodeType ChildNodeType
Definition: InternalNode.h:66
void visitActiveBBox(BBoxOp &) const
Calls the templated functor BBoxOp with bounding box information for all active tiles and leaf nodes ...
Definition: InternalNode.h:2574
Index64 onVoxelCount() const
Definition: InternalNode.h:916
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:1317
DenseIter(const MaskDenseIterator &iter, NodeT *parent)
Definition: InternalNode.h:189
const ValueType & getFirstValue() const
If the first entry in this node's table is a tile, return the tile's value. Otherwise, return the result of calling getFirstValue() on the child.
Definition: InternalNode.h:2077
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Definition: NodeMasks.h:304
void voxelizeActiveTiles()
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition: InternalNode.h:2112
ValueOffCIter beginValueOff() const
Definition: InternalNode.h:248
bool hasActiveTiles() const
Return true if this node or any of its child nodes have any active tiles.
Definition: InternalNode.h:1399
BaseT::NonConstValueType NonConstValueT
Definition: InternalNode.h:186
UnionType mNodes[NUM_VALUES]
Definition: InternalNode.h:734
uint32_t Index32
Definition: Types.h:57
void topologyDifference(const InternalNode< OtherChildNodeType, Log2Dim > &other, const ValueType &background)
Difference this node'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.
Definition: Types.h:426
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
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:1005
ValueIter(const MaskIterT &iter, NodeT *parent)
Definition: InternalNode.h:165
ValueIter< const InternalNode, const ValueType, MaskOffIterator, ValueOff > ValueOffCIter
Definition: InternalNode.h:228
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:1467
boost::remove_const< UnsetItemT >::type NonConstValueType
Definition: Iterator.h:217
ValueIter< InternalNode, const ValueType, MaskOffIterator, ValueAll > ValueAllIter
Definition: InternalNode.h:229
void readTopology(std::istream &, bool fromHalf=false)
Definition: InternalNode.h:2008
NodeMaskType mValueMask
Definition: InternalNode.h:735
Coord offsetToGlobalCoord(Index n) const
Return the global coordinates for a linear table offset.
Definition: InternalNode.h:2822
InternalNode< typename ChildNodeType::template ValueConverter< OtherValueType >::Type, Log2Dim > Type
Definition: InternalNode.h:86
Base class for iterators over internal and leaf nodes.
Definition: Iterator.h:58
static Index dim()
Definition: InternalNode.h:256
ChildT & getItem(Index pos) const
Definition: InternalNode.h:148
Definition: InternalNode.h:134
void topologyUnion(const InternalNode< OtherChildNodeType, Log2Dim > &other)
Union this branch's set of active values with the other branch's active values. The value type of the...
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:2127
bool isValueMaskOn() const
Definition: InternalNode.h:686
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:2876
bool isValueOn(const Coord &xyz) const
Return true if the voxel at the given coordinates is active.
Definition: InternalNode.h:1414
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:1941
ValueOffIter beginValueOff()
Definition: InternalNode.h:252
bool isChildMaskOn(Index n) const
Definition: InternalNode.h:689
const NodeMaskType & getChildMask() const
Definition: InternalNode.h:693
bool probeValue(const Coord &xyz, ValueType &value) const
Definition: InternalNode.h:1480
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: InternalNode.h:1806
bool isValueMaskOff() const
Definition: InternalNode.h:688
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:314