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