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