OpenVDB  2.0.0
InternalNode.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2013 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 <openvdb/Platform.h>
41 #include <openvdb/util/NodeMasks.h>
42 #include <openvdb/io/Compression.h> // for io::readData(), etc.
43 #include <openvdb/math/Math.h> // for Abs(), isExactlyEqual()
44 #include <openvdb/version.h>
45 #include <openvdb/Types.h>
46 #include "Iterator.h"
47 #include "NodeUnion.h"
48 #include "Util.h"
49 
50 
51 namespace openvdb {
53 namespace OPENVDB_VERSION_NAME {
54 namespace tree {
55 
56 template<typename _ChildNodeType, Index Log2Dim>
58 {
59 public:
60  typedef _ChildNodeType ChildNodeType;
61  typedef typename ChildNodeType::LeafNodeType LeafNodeType;
62  typedef typename ChildNodeType::ValueType ValueType;
65 
66  static const Index
67  LOG2DIM = Log2Dim,
68  TOTAL = Log2Dim + ChildNodeType::TOTAL,
69  DIM = 1 << TOTAL,
70  NUM_VALUES = 1 << (3 * Log2Dim),
71  LEVEL = 1 + ChildNodeType::LEVEL; // level 0 = leaf
72  static const Index64
73  NUM_VOXELS = uint64_t(1) << (3 * TOTAL); // total # of voxels represented by this node
74 
77  template<typename OtherValueType>
78  struct ValueConverter {
79  typedef InternalNode<typename ChildNodeType::template ValueConverter<
80  OtherValueType>::Type, Log2Dim> Type;
81  };
82 
83 
85 
86  explicit InternalNode(const ValueType& offValue);
87 
88  InternalNode(const Coord&, const ValueType& value, bool active = false);
89 
91  InternalNode(const InternalNode&);
92 
94  template<typename OtherChildNodeType>
96  const ValueType& background, TopologyCopy);
97 
99  template<typename OtherChildNodeType>
101  const ValueType& offValue, const ValueType& onValue,
102  TopologyCopy);
103 
104  virtual ~InternalNode();
105 
106 protected:
110 
111  // Type tags to disambiguate template instantiations
112  struct ValueOn {}; struct ValueOff {}; struct ValueAll {};
113  struct ChildOn {}; struct ChildOff {}; struct ChildAll {};
114 
115  // The following class templates implement the iterator interfaces specified in Iterator.h
116  // by providing getItem(), setItem() and/or modifyItem() methods.
117 
118  template<typename NodeT, typename ChildT, typename MaskIterT, typename TagT>
120  MaskIterT, ChildIter<NodeT, ChildT, MaskIterT, TagT>, NodeT, ChildT>
121  {
123  ChildIter(const MaskIterT& iter, NodeT* parent): SparseIteratorBase<
124  MaskIterT, ChildIter<NodeT, ChildT, MaskIterT, TagT>, NodeT, ChildT>(iter, parent) {}
125 
126  ChildT& getItem(Index pos) const { return *(this->parent().getChildNode(pos)); }
127 
128  // Note: setItem() can't be called on const iterators.
129  void setItem(Index pos, const ChildT& c) const { this->parent().resetChildNode(pos, &c); }
130 
131  // Note: modifyItem() isn't implemented, since it's not useful for child node pointers.
132  };// ChildIter
133 
134  template<typename NodeT, typename ValueT, typename MaskIterT, typename TagT>
136  MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>
137  {
139  ValueIter(const MaskIterT& iter, NodeT* parent): SparseIteratorBase<
140  MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>(iter, parent) {}
141 
142  const ValueT& getItem(Index pos) const { return this->parent().mNodes[pos].getValue(); }
143 
144  // Note: setItem() can't be called on const iterators.
145  void setItem(Index pos, const ValueT& v) const { this->parent().mNodes[pos].setValue(v); }
146 
147  // Note: modifyItem() can't be called on const iterators.
148  template<typename ModifyOp>
149  void modifyItem(Index pos, const ModifyOp& op) const
150  {
151  op(this->parent().mNodes[pos].getValue());
152  }
153  };// ValueIter
154 
155  template<typename NodeT, typename ChildT, typename ValueT, typename TagT>
156  struct DenseIter: public DenseIteratorBase<
157  MaskDenseIterator, DenseIter<NodeT, ChildT, ValueT, TagT>, NodeT, ChildT, ValueT>
158  {
161 
163  DenseIter(const MaskDenseIterator& iter, NodeT* parent):
164  DenseIteratorBase<MaskDenseIterator, DenseIter, NodeT, ChildT, ValueT>(iter, parent) {}
165 
166  bool getItem(Index pos, ChildT*& child, NonConstValueT& value) const
167  {
168  child = this->parent().getChildNode(pos);
169  if (!child) value = this->parent().mNodes[pos].getValue();
170  return (child != NULL);
171  }
172 
173  // Note: setItem() can't be called on const iterators.
174  void setItem(Index pos, ChildT* child) const
175  {
176  this->parent().resetChildNode(pos, child);
177  }
178 
179  // Note: unsetItem() can't be called on const iterators.
180  void unsetItem(Index pos, const ValueT& value) const
181  {
182  this->parent().unsetChildNode(pos, value);
183  }
184  };// DenseIter
185 
186 public:
187  // Iterators (see Iterator.h for usage)
194 
201 
202  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(mChildMask.beginOn(), this); }
203  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(mChildMask.beginOff(), this); }
204  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(mChildMask.beginDense(), this); }
205  ChildOnCIter beginChildOn() const { return cbeginChildOn(); }
206  ChildOffCIter beginChildOff() const { return cbeginChildOff(); }
207  ChildAllCIter beginChildAll() const { return cbeginChildAll(); }
208  ChildOnIter beginChildOn() { return ChildOnIter(mChildMask.beginOn(), this); }
209  ChildOffIter beginChildOff() { return ChildOffIter(mChildMask.beginOff(), this); }
210  ChildAllIter beginChildAll() { return ChildAllIter(mChildMask.beginDense(), this); }
211 
212  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(mValueMask.beginOn(), this); }
213  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(mValueMask.beginOff(), this); }
214  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(mChildMask.beginOff(), this); }
215  ValueOnCIter beginValueOn() const { return cbeginValueOn(); }
216  ValueOffCIter beginValueOff() const { return cbeginValueOff(); }
217  ValueAllCIter beginValueAll() const { return cbeginValueAll(); }
218  ValueOnIter beginValueOn() { return ValueOnIter(mValueMask.beginOn(), this); }
219  ValueOffIter beginValueOff() { return ValueOffIter(mValueMask.beginOff(), this); }
220  ValueAllIter beginValueAll() { return ValueAllIter(mChildMask.beginOff(), this); }
221 
222 
223  static Index dim() { return DIM; }
224  static Index getLevel() { return LEVEL; }
225  static void getNodeLog2Dims(std::vector<Index>& dims);
226  static Index getChildDim() { return ChildNodeType::DIM; }
227 
229  static Index coordToOffset(const Coord& xyz);
232  static void offsetToLocalCoord(Index n, Coord& xyz);
234  Coord offsetToGlobalCoord(Index n) const;
235 
237  const Coord& origin() const { return mOrigin; }
240  OPENVDB_DEPRECATED Coord getOrigin() const { return mOrigin; }
242  void setOrigin(const Coord& origin) { mOrigin = origin; }
243 
244  Index32 leafCount() const;
245  Index32 nonLeafCount() const;
246  Index64 onVoxelCount() const;
247  Index64 offVoxelCount() const;
248  Index64 onLeafVoxelCount() const;
249  Index64 offLeafVoxelCount() const;
250  Index64 onTileCount() const;
251 
253  Index64 memUsage() const;
254 
259  void evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels = true) const;
260  OPENVDB_DEPRECATED void evalActiveVoxelBoundingBox(CoordBBox& bbox) const;
261 
264  CoordBBox getNodeBoundingBox() const { return CoordBBox::createCube(mOrigin, DIM); }
265 
266  bool isEmpty() const { return mChildMask.isOff(); }
267 
271  bool isConstant(ValueType& constValue, bool& state,
272  const ValueType& tolerance = zeroVal<ValueType>()) const;
274  bool isInactive() const { return this->isChildMaskOff() && this->isValueMaskOff(); }
275 
277  bool isValueOn(const Coord& xyz) const;
279  bool isValueOn(Index offset) const { return mValueMask.isOn(offset); }
280 
282  bool hasActiveTiles() const;
283 
284  const ValueType& getValue(const Coord& xyz) const;
285  bool probeValue(const Coord& xyz, ValueType& value) const;
286 
289  Index getValueLevel(const Coord& xyz) const;
290 
293  const ValueType& getFirstValue() const;
296  const ValueType& getLastValue() const;
297 
299  void setActiveState(const Coord& xyz, bool on);
301  void setValueOnly(const Coord& xyz, const ValueType& value);
303  void setValueOn(const Coord& xyz);
305  void setValueOn(const Coord& xyz, const ValueType& value);
307  void setValueOff(const Coord& xyz);
309  void setValueOff(const Coord& xyz, const ValueType& value);
310 
313  template<typename ModifyOp>
314  void modifyValue(const Coord& xyz, const ModifyOp& op);
316  template<typename ModifyOp>
317  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
318 
323  template<typename AccessorT>
324  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
325 
330  template<typename AccessorT>
331  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
332 
337  template<typename AccessorT>
338  void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
339 
344  template<typename AccessorT>
345  void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
346 
352  template<typename ModifyOp, typename AccessorT>
353  void modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
354 
359  template<typename ModifyOp, typename AccessorT>
360  void modifyValueAndActiveStateAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
361 
366  template<typename AccessorT>
367  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
368 
373  template<typename AccessorT>
374  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
375 
381  template<typename AccessorT>
382  bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
383 
390  template<typename AccessorT>
391  Index getValueLevelAndCache(const Coord& xyz, AccessorT&) const;
392 
394  void setValuesOn();
395 
396 
397  //
398  // I/O
399  //
400  void writeTopology(std::ostream&, bool toHalf = false) const;
401  void readTopology(std::istream&, bool fromHalf = false);
402  void writeBuffers(std::ostream&, bool toHalf = false) const;
403  void readBuffers(std::istream&, bool fromHalf = false);
404 
405 
406  //
407  // Aux methods
408  //
411  void fill(const CoordBBox& bbox, const ValueType&, bool active = true);
412 
418  void signedFloodFill(const ValueType& background);
419 
425  void signedFloodFill(const ValueType& outside, const ValueType& inside);
426 
429  void negate();
430 
432  void voxelizeActiveTiles();
433 
441  template<typename DenseT>
442  void copyToDense(const CoordBBox& bbox, DenseT& dense) const;
443 
446  template<MergePolicy Policy>
447  void merge(InternalNode& other, const ValueType& background, const ValueType& otherBackground);
448 
451  template<MergePolicy Policy> void merge(const ValueType& tileValue, bool tileActive);
452 
465  template<typename OtherChildNodeType>
466  void topologyUnion(const InternalNode<OtherChildNodeType, Log2Dim>& other);
467 
481  template<typename OtherChildNodeType>
482  void topologyIntersection(const InternalNode<OtherChildNodeType, Log2Dim>& other,
483  const ValueType& background);
484 
496  template<typename OtherChildNodeType>
497  void topologyDifference(const InternalNode<OtherChildNodeType, Log2Dim>& other,
498  const ValueType& background);
499 
500  template<typename CombineOp>
501  void combine(InternalNode& other, CombineOp&);
502  template<typename CombineOp>
503  void combine(const ValueType& value, bool valueIsActive, CombineOp&);
504 
505  template<typename CombineOp>
506  void combine2(const InternalNode& other0, const InternalNode& other1, CombineOp&);
507  template<typename CombineOp>
508  void combine2(const ValueType& value, const InternalNode& other, bool valIsActive, CombineOp&);
509  template<typename CombineOp>
510  void combine2(const InternalNode& other, const ValueType& val, bool valIsActive, CombineOp&);
511 
517  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
518 
519  template<typename VisitorOp> void visit(VisitorOp&);
520  template<typename VisitorOp> void visit(VisitorOp&) const;
521 
522  template<typename OtherNodeType, typename VisitorOp>
523  void visit2Node(OtherNodeType& other, VisitorOp&);
524  template<typename OtherNodeType, typename VisitorOp>
525  void visit2Node(OtherNodeType& other, VisitorOp&) const;
526  template<typename IterT, typename VisitorOp>
527  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false);
528  template<typename IterT, typename VisitorOp>
529  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false) const;
530 
537  template<typename PruneOp> void pruneOp(PruneOp&);
538 
542  void prune(const ValueType& tolerance = zeroVal<ValueType>());
543 
546  void pruneInactive(const ValueType&);
547 
550  void pruneInactive();
551 
554  void addLeaf(LeafNodeType* leaf);
555 
558  template<typename AccessorT>
559  void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
560 
569  template<typename NodeT>
570  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
571 
574  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
575 
577  void addTile(Index offset, const ValueType& value, bool state);
578 
581  template<typename AccessorT>
582  void addTileAndCache(Index level, const Coord& xyz, const ValueType&, bool state, AccessorT&);
583 
585  template<typename NodeType> NodeType* probeNode(const Coord& xyz);
588  template<typename NodeType> const NodeType* probeConstNode(const Coord& xyz) const;
590 
592  template<typename NodeType, typename AccessorT>
595  NodeType* probeNodeAndCache(const Coord& xyz, AccessorT&);
596  template<typename NodeType, typename AccessorT>
597  const NodeType* probeConstNodeAndCache(const Coord& xyz, AccessorT&) const;
599 
601  LeafNodeType* probeLeaf(const Coord& xyz);
604  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
605  const LeafNodeType* probeLeaf(const Coord& xyz) const;
607 
609  template<typename AccessorT>
612  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc);
613  template<typename AccessorT>
614  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const;
615  template<typename AccessorT>
616  const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const;
618 
625  LeafNodeType* touchLeaf(const Coord& xyz);
626 
629  template<typename AccessorT>
630  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT&);
631 
634  void resetBackground(const ValueType& oldBackground, const ValueType& newBackground);
635 
638  template<typename OtherChildNodeType, Index OtherLog2Dim>
639  bool hasSameTopology(const InternalNode<OtherChildNodeType, OtherLog2Dim>* other) const;
640 
641 protected:
643  friend class IteratorBase<MaskOnIterator, InternalNode>;
649 
652  template<typename, Index> friend class InternalNode;
653 
654  // Mask accessors
655 public:
656  bool isValueMaskOn(Index n) const { return mValueMask.isOn(n); }
657  bool isValueMaskOn() const { return mValueMask.isOn(); }
658  bool isValueMaskOff(Index n) const { return mValueMask.isOff(n); }
659  bool isValueMaskOff() const { return mValueMask.isOff(); }
660  bool isChildMaskOn(Index n) const { return mChildMask.isOn(n); }
661  bool isChildMaskOff(Index n) const { return mChildMask.isOff(n); }
662  bool isChildMaskOff() const { return mChildMask.isOff(); }
663 protected:
665  void setValueMask(Index n, bool on) { mValueMask.set(n, mChildMask.isOn(n) ? false : on); }
669 
670  void makeChildNodeEmpty(Index n, const ValueType& value);
671  void setChildNode( Index i, ChildNodeType* child);//assumes a tile
672  void resetChildNode(Index i, ChildNodeType* child);//checks for an existing child
673  ChildNodeType* unsetChildNode(Index i, const ValueType& value);
674 
675  template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
676  static inline void doVisit(NodeT&, VisitorOp&);
677 
678  template<typename NodeT, typename OtherNodeT, typename VisitorOp,
679  typename ChildAllIterT, typename OtherChildAllIterT>
680  static inline void doVisit2Node(NodeT&, OtherNodeT&, VisitorOp&);
681 
682  template<typename NodeT, typename VisitorOp,
683  typename ChildAllIterT, typename OtherChildAllIterT>
684  static inline void doVisit2(NodeT&, OtherChildAllIterT&, VisitorOp&, bool otherIsLHS);
685 
686  ChildNodeType* getChildNode(Index n);
687  const ChildNodeType* getChildNode(Index n) const;
688 
689 
690  UnionType mNodes[NUM_VALUES];
693  Coord mOrigin;
694 }; // class InternalNode
695 
696 
698 
699 
700 template<typename ChildT, Index Log2Dim>
701 inline
703 {
704  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
705 }
706 
707 
708 template<typename ChildT, Index Log2Dim>
709 inline
710 InternalNode<ChildT, Log2Dim>::InternalNode(const Coord& origin, const ValueType& val, bool active):
711  mOrigin(origin[0] & ~(DIM - 1), // zero out the low-order bits
712  origin[1] & ~(DIM - 1),
713  origin[2] & ~(DIM - 1))
714 {
715  if (active) mValueMask.setOn();
716  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
717 }
718 
719 
720 template<typename ChildT, Index Log2Dim>
721 inline
723  mChildMask(other.mChildMask),
724  mValueMask(other.mValueMask),
725  mOrigin(other.mOrigin)
726 {
727  for (Index i = 0; i < NUM_VALUES; ++i) {
728  if (isChildMaskOn(i)) {
729  mNodes[i].setChild(new ChildNodeType(*(other.mNodes[i].getChild())));
730  } else {
731  mNodes[i].setValue(other.mNodes[i].getValue());
732  }
733  }
734 }
735 
736 template<typename ChildT, Index Log2Dim>
737 template<typename OtherChildNodeType>
738 inline
740  const ValueType& offValue, const ValueType& onValue, TopologyCopy):
741  mChildMask(other.mChildMask),
742  mValueMask(other.mValueMask),
743  mOrigin(other.mOrigin)
744 {
745  for (Index i = 0; i < NUM_VALUES; ++i) {
746  if (isChildMaskOn(i)) {
747  mNodes[i].setChild(new ChildNodeType(*(other.mNodes[i].getChild()),
748  offValue, onValue, TopologyCopy()));
749  } else {
750  mNodes[i].setValue(isValueMaskOn(i) ? onValue : offValue);
751  }
752  }
753 }
754 
755 template<typename ChildT, Index Log2Dim>
756 template<typename OtherChildNodeType>
757 inline
759  const ValueType& background, TopologyCopy):
760  mChildMask(other.mChildMask),
761  mValueMask(other.mValueMask),
762  mOrigin(other.mOrigin)
763 {
764  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
765  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
766  mNodes[iter.pos()].setChild(new ChildNodeType(*(other.mNodes[iter.pos()].getChild()),
767  background, TopologyCopy()));
768  }
769 }
770 
771 
772 template<typename ChildT, Index Log2Dim>
773 inline
775 {
776  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
777  delete mNodes[iter.pos()].getChild();
778  }
779 }
780 
781 
783 
784 
785 template<typename ChildT, Index Log2Dim>
786 inline Index32
788 {
789  if (ChildNodeType::getLevel() == 0) return mChildMask.countOn();
790  Index32 sum = 0;
791  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
792  sum += iter->leafCount();
793  }
794  return sum;
795 }
796 
797 
798 template<typename ChildT, Index Log2Dim>
799 inline Index32
801 {
802  Index32 sum = 1;
803  if (ChildNodeType::getLevel() == 0) return sum;
804  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
805  sum += iter->nonLeafCount();
806  }
807  return sum;
808 }
809 
810 
811 template<typename ChildT, Index Log2Dim>
812 inline Index64
814 {
815  Index64 sum = ChildT::NUM_VOXELS * mValueMask.countOn();
816  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
817  sum += iter->onVoxelCount();
818  }
819  return sum;
820 }
821 
822 
823 template<typename ChildT, Index Log2Dim>
824 inline Index64
826 {
827  Index64 sum = ChildT::NUM_VOXELS * (NUM_VALUES-mValueMask.countOn()-mChildMask.countOn());
828  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
829  sum += iter->offVoxelCount();
830  }
831  return sum;
832 }
833 
834 
835 template<typename ChildT, Index Log2Dim>
836 inline Index64
838 {
839  Index64 sum = 0;
840  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
841  sum += mNodes[iter.pos()].getChild()->onLeafVoxelCount();
842  }
843  return sum;
844 }
845 
846 
847 template<typename ChildT, Index Log2Dim>
848 inline Index64
850 {
851  Index64 sum = 0;
852  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
853  sum += mNodes[iter.pos()].getChild()->offLeafVoxelCount();
854  }
855  return sum;
856 }
857 
858 template<typename ChildT, Index Log2Dim>
859 inline Index64
861 {
862  Index64 sum = mValueMask.countOn();
863  for (ChildOnCIter iter = this->cbeginChildOn(); LEVEL>1 && iter; ++iter) {
864  sum += iter->onTileCount();
865  }
866  return sum;
867 }
868 
869 template<typename ChildT, Index Log2Dim>
870 inline Index64
872 {
873  Index64 sum = NUM_VALUES * sizeof(UnionType) + mChildMask.memUsage()
874  + mValueMask.memUsage() + sizeof(mOrigin);
875  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
876  sum += iter->memUsage();
877  }
878  return sum;
879 }
880 
881 // Deprecated
882 template<typename ChildT, Index Log2Dim>
883 inline void
885 {
886  if (bbox.isInside(this->getNodeBoundingBox())) return;
887 
888  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) bbox.expand(i.getCoord(), ChildT::DIM);
889 
890  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) i->evalActiveVoxelBoundingBox(bbox);
891 }
892 
893 template<typename ChildT, Index Log2Dim>
894 inline void
895 InternalNode<ChildT, Log2Dim>::evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels) const
896 {
897  if (bbox.isInside(this->getNodeBoundingBox())) return;
898 
899  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) bbox.expand(i.getCoord(), ChildT::DIM);
900 
901  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) i->evalActiveBoundingBox(bbox, visitVoxels);
902 }
903 
904 
906 
907 
908 template<typename ChildT, Index Log2Dim>
909 template<typename PruneOp>
910 inline void
912 {
913  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
914  const Index i = iter.pos();
915  ChildT* child = mNodes[i].getChild();
916  if (!op(*child)) continue;
917  delete child;
918  mChildMask.setOff(i);
919  mValueMask.set(i, op.state);
920  mNodes[i].setValue(op.value);
921  }
922 
923 }
924 
925 
926 template<typename ChildT, Index Log2Dim>
927 inline void
929 {
930  TolerancePrune<ValueType> op(tolerance);
931  this->pruneOp(op);
932 }
933 
934 
935 template<typename ChildT, Index Log2Dim>
936 inline void
938 {
940  this->pruneOp(op);
941 }
942 
943 
944 template<typename ChildT, Index Log2Dim>
945 inline void
947 {
948  this->pruneInactive(this->getBackground());
949 }
950 
951 
953 
954 
955 template<typename ChildT, Index Log2Dim>
956 template<typename NodeT>
957 inline NodeT*
958 InternalNode<ChildT, Log2Dim>::stealNode(const Coord& xyz, const ValueType& value, bool state)
959 {
960  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
961  NodeT::LEVEL > ChildT::LEVEL) return NULL;
963  const Index n = this->coordToOffset(xyz);
964  if (mChildMask.isOff(n)) return NULL;
965  ChildT* child = mNodes[n].getChild();
966  if (boost::is_same<NodeT, ChildT>::value) {
967  mChildMask.setOff(n);
968  mValueMask.set(n, state);
969  mNodes[n].setValue(value);
970  }
971  return (boost::is_same<NodeT, ChildT>::value)
972  ? reinterpret_cast<NodeT*>(child)
973  : child->template stealNode<NodeT>(xyz, value, state);
975 }
976 
977 
979 
980 
981 template<typename ChildT, Index Log2Dim>
982 template<typename NodeT>
983 inline NodeT*
985 {
986  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
987  NodeT::LEVEL > ChildT::LEVEL) return NULL;
989  const Index n = this->coordToOffset(xyz);
990  if (mChildMask.isOff(n)) return NULL;
991  ChildT* child = mNodes[n].getChild();
992  return (boost::is_same<NodeT, ChildT>::value)
993  ? reinterpret_cast<NodeT*>(child)
994  : child->template probeNode<NodeT>(xyz);
996 }
997 
998 
999 template<typename ChildT, Index Log2Dim>
1000 template<typename NodeT, typename AccessorT>
1001 inline NodeT*
1002 InternalNode<ChildT, Log2Dim>::probeNodeAndCache(const Coord& xyz, AccessorT& acc)
1003 {
1004  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
1005  NodeT::LEVEL > ChildT::LEVEL) return NULL;
1007  const Index n = this->coordToOffset(xyz);
1008  if (mChildMask.isOff(n)) return NULL;
1009  ChildT* child = mNodes[n].getChild();
1010  acc.insert(xyz, child);
1011  return (boost::is_same<NodeT, ChildT>::value)
1012  ? reinterpret_cast<NodeT*>(child)
1013  : child->template probeNodeAndCache<NodeT>(xyz, acc);
1015 }
1016 
1017 
1018 template<typename ChildT, Index Log2Dim>
1019 template<typename NodeT>
1020 inline const NodeT*
1022 {
1023  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
1024  NodeT::LEVEL > ChildT::LEVEL) return NULL;
1026  const Index n = this->coordToOffset(xyz);
1027  if (mChildMask.isOff(n)) return NULL;
1028  const ChildT* child = mNodes[n].getChild();
1029  return (boost::is_same<NodeT, ChildT>::value)
1030  ? reinterpret_cast<const NodeT*>(child)
1031  : child->template probeConstNode<NodeT>(xyz);
1033 }
1034 
1035 
1036 template<typename ChildT, Index Log2Dim>
1037 template<typename NodeT, typename AccessorT>
1038 inline const NodeT*
1039 InternalNode<ChildT, Log2Dim>::probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const
1040 {
1041  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
1042  NodeT::LEVEL > ChildT::LEVEL) return NULL;
1044  const Index n = this->coordToOffset(xyz);
1045  if (mChildMask.isOff(n)) return NULL;
1046  const ChildT* child = mNodes[n].getChild();
1047  acc.insert(xyz, child);
1048  return (boost::is_same<NodeT, ChildT>::value)
1049  ? reinterpret_cast<const NodeT*>(child)
1050  : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
1052 }
1053 
1054 
1056 
1057 
1058 template<typename ChildT, Index Log2Dim>
1059 inline typename ChildT::LeafNodeType*
1061 {
1062  return this->template probeNode<LeafNodeType>(xyz);
1063 }
1064 
1065 
1066 template<typename ChildT, Index Log2Dim>
1067 template<typename AccessorT>
1068 inline typename ChildT::LeafNodeType*
1069 InternalNode<ChildT, Log2Dim>::probeLeafAndCache(const Coord& xyz, AccessorT& acc)
1070 {
1071  return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
1072 }
1073 
1074 
1075 template<typename ChildT, Index Log2Dim>
1076 template<typename AccessorT>
1077 inline const typename ChildT::LeafNodeType*
1078 InternalNode<ChildT, Log2Dim>::probeLeafAndCache(const Coord& xyz, AccessorT& acc) const
1079 {
1080  return this->probeConstLeafAndCache(xyz, acc);
1081 }
1082 
1083 
1084 template<typename ChildT, Index Log2Dim>
1085 inline const typename ChildT::LeafNodeType*
1087 {
1088  return this->template probeConstNode<LeafNodeType>(xyz);
1089 }
1090 
1091 
1092 template<typename ChildT, Index Log2Dim>
1093 template<typename AccessorT>
1094 inline const typename ChildT::LeafNodeType*
1095 InternalNode<ChildT, Log2Dim>::probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
1096 {
1097  return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
1098 }
1099 
1100 
1102 
1103 
1104 template<typename ChildT, Index Log2Dim>
1105 inline void
1107 {
1108  assert(leaf != NULL);
1109  const Coord& xyz = leaf->origin();
1110  const Index n = this->coordToOffset(xyz);
1111  ChildT* child = NULL;
1112  if (mChildMask.isOff(n)) {
1113  if (ChildT::LEVEL>0) {
1114  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1115  } else {
1116  child = reinterpret_cast<ChildT*>(leaf);
1117  }
1118  this->setChildNode(n, child);
1119  } else {
1120  if (ChildT::LEVEL>0) {
1121  child = mNodes[n].getChild();
1122  } else {
1123  delete mNodes[n].getChild();
1124  child = reinterpret_cast<ChildT*>(leaf);
1125  mNodes[n].setChild(child);
1126  }
1127  }
1128  child->addLeaf(leaf);
1129 }
1130 
1131 
1132 template<typename ChildT, Index Log2Dim>
1133 template<typename AccessorT>
1134 inline void
1136 {
1137  assert(leaf != NULL);
1138  const Coord& xyz = leaf->origin();
1139  const Index n = this->coordToOffset(xyz);
1140  ChildT* child = NULL;
1141  if (mChildMask.isOff(n)) {
1142  if (ChildT::LEVEL>0) {
1143  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1144  acc.insert(xyz, child);//we only cache internal nodes
1145  } else {
1146  child = reinterpret_cast<ChildT*>(leaf);
1147  }
1148  this->setChildNode(n, child);
1149  } else {
1150  if (ChildT::LEVEL>0) {
1151  child = mNodes[n].getChild();
1152  acc.insert(xyz, child);//we only cache internal nodes
1153  } else {
1154  delete mNodes[n].getChild();
1155  child = reinterpret_cast<ChildT*>(leaf);
1156  mNodes[n].setChild(child);
1157  }
1158  }
1159  child->addLeafAndCache(leaf, acc);
1160 }
1161 
1162 
1164 
1165 
1166 template<typename ChildT, Index Log2Dim>
1167 inline void
1169 {
1170  assert(n < NUM_VALUES);
1171  this->makeChildNodeEmpty(n, value);
1172  mValueMask.set(n, state);
1173 }
1174 
1175 
1176 template<typename ChildT, Index Log2Dim>
1177 inline void
1179  const ValueType& value, bool state)
1180 {
1181  if (LEVEL >= level) {
1182  const Index n = this->coordToOffset(xyz);
1183  if (mChildMask.isOff(n)) {// tile case
1184  if (LEVEL > level) {
1185  ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1186  this->setChildNode(n, child);
1187  child->addTile(level, xyz, value, state);
1188  } else {
1189  mValueMask.set(n, state);
1190  mNodes[n].setValue(value);
1191  }
1192  } else {// child branch case
1193  ChildT* child = mNodes[n].getChild();
1194  if (LEVEL > level) {
1195  child->addTile(level, xyz, value, state);
1196  } else {
1197  delete child;
1198  mChildMask.setOff(n);
1199  mValueMask.set(n, state);
1200  mNodes[n].setValue(value);
1201  }
1202  }
1203  }
1204 }
1205 
1206 
1207 template<typename ChildT, Index Log2Dim>
1208 template<typename AccessorT>
1209 inline void
1211  const ValueType& value, bool state, AccessorT& acc)
1212 {
1213  if (LEVEL >= level) {
1214  const Index n = this->coordToOffset(xyz);
1215  if (mChildMask.isOff(n)) {// tile case
1216  if (LEVEL > level) {
1217  ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1218  this->setChildNode(n, child);
1219  acc.insert(xyz, child);
1220  child->addTileAndCache(level, xyz, value, state, acc);
1221  } else {
1222  mValueMask.set(n, state);
1223  mNodes[n].setValue(value);
1224  }
1225  } else {// child branch case
1226  ChildT* child = mNodes[n].getChild();
1227  if (LEVEL > level) {
1228  acc.insert(xyz, child);
1229  child->addTileAndCache(level, xyz, value, state, acc);
1230  } else {
1231  delete child;
1232  mChildMask.setOff(n);
1233  mValueMask.set(n, state);
1234  mNodes[n].setValue(value);
1235  }
1236  }
1237  }
1238 }
1239 
1240 
1242 
1243 
1244 template<typename ChildT, Index Log2Dim>
1245 inline typename ChildT::LeafNodeType*
1247 {
1248  const Index n = this->coordToOffset(xyz);
1249  ChildT* child = NULL;
1250  if (mChildMask.isOff(n)) {
1251  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1252  this->setChildNode(n, child);
1253  } else {
1254  child = mNodes[n].getChild();
1255  }
1256  return child->touchLeaf(xyz);
1257 }
1258 
1259 
1260 template<typename ChildT, Index Log2Dim>
1261 template<typename AccessorT>
1262 inline typename ChildT::LeafNodeType*
1263 InternalNode<ChildT, Log2Dim>::touchLeafAndCache(const Coord& xyz, AccessorT& acc)
1264 {
1265  const Index n = this->coordToOffset(xyz);
1266  if (mChildMask.isOff(n)) {
1267  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), mValueMask.isOn(n)));
1268  }
1269  acc.insert(xyz, mNodes[n].getChild());
1270  return mNodes[n].getChild()->touchLeafAndCache(xyz, acc);
1271 }
1272 
1273 
1275 
1276 
1277 template<typename ChildT, Index Log2Dim>
1278 inline bool
1280  const ValueType& tolerance) const
1281 {
1282  bool allEqual = true, firstValue = true, valueState = true;
1283  ValueType value = zeroVal<ValueType>();
1284  for (Index i = 0; allEqual && i < NUM_VALUES; ++i) {
1285  if (this->isChildMaskOff(i)) {
1286  // If entry i is a value, check if it is within tolerance
1287  // and whether its active state matches the other entries.
1288  if (firstValue) {
1289  firstValue = false;
1290  valueState = isValueMaskOn(i);
1291  value = mNodes[i].getValue();
1292  } else {
1293  allEqual = (isValueMaskOn(i) == valueState)
1294  && math::isApproxEqual(mNodes[i].getValue(), value, tolerance);
1295  }
1296  } else {
1297  // If entry i is a child, check if the child is constant and within tolerance
1298  // and whether its active state matches the other entries.
1299  ValueType childValue = zeroVal<ValueType>();
1300  bool isChildOn = false;
1301  if (mNodes[i].getChild()->isConstant(childValue, isChildOn, tolerance)) {
1302  if (firstValue) {
1303  firstValue = false;
1304  valueState = isChildOn;
1305  value = childValue;
1306  } else {
1307  allEqual = (isChildOn == valueState)
1308  && math::isApproxEqual(childValue, value, tolerance);
1309  }
1310  } else { // child is not constant
1311  allEqual = false;
1312  }
1313  }
1314  }
1315  if (allEqual) {
1316  constValue = value;
1317  state = valueState;
1318  }
1319  return allEqual;
1320 }
1321 
1322 
1324 
1325 
1326 template<typename ChildT, Index Log2Dim>
1327 inline bool
1329 {
1330  const bool anyActiveTiles = !mValueMask.isOff();
1331  if (LEVEL==1 || anyActiveTiles) return anyActiveTiles;
1332  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1333  if (iter->hasActiveTiles()) return true;
1334  }
1335  return false;
1336 }
1337 
1338 
1339 template<typename ChildT, Index Log2Dim>
1340 inline bool
1342 {
1343  const Index n = this->coordToOffset(xyz);
1344  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1345  return mNodes[n].getChild()->isValueOn(xyz);
1346 }
1347 
1348 template<typename ChildT, Index Log2Dim>
1349 template<typename AccessorT>
1350 inline bool
1351 InternalNode<ChildT, Log2Dim>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const
1352 {
1353  const Index n = this->coordToOffset(xyz);
1354  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1355  acc.insert(xyz, mNodes[n].getChild());
1356  return mNodes[n].getChild()->isValueOnAndCache(xyz, acc);
1357 }
1358 
1359 
1360 template<typename ChildT, Index Log2Dim>
1361 inline const typename ChildT::ValueType&
1363 {
1364  const Index n = this->coordToOffset(xyz);
1365  return this->isChildMaskOff(n) ? mNodes[n].getValue()
1366  : mNodes[n].getChild()->getValue(xyz);
1367 }
1368 
1369 template<typename ChildT, Index Log2Dim>
1370 template<typename AccessorT>
1371 inline const typename ChildT::ValueType&
1372 InternalNode<ChildT, Log2Dim>::getValueAndCache(const Coord& xyz, AccessorT& acc) const
1373 {
1374  const Index n = this->coordToOffset(xyz);
1375  if (this->isChildMaskOn(n)) {
1376  acc.insert(xyz, mNodes[n].getChild());
1377  return mNodes[n].getChild()->getValueAndCache(xyz, acc);
1378  }
1379  return mNodes[n].getValue();
1380 }
1381 
1382 
1383 template<typename ChildT, Index Log2Dim>
1384 inline Index
1386 {
1387  const Index n = this->coordToOffset(xyz);
1388  return this->isChildMaskOff(n) ? LEVEL : mNodes[n].getChild()->getValueLevel(xyz);
1389 }
1390 
1391 template<typename ChildT, Index Log2Dim>
1392 template<typename AccessorT>
1393 inline Index
1394 InternalNode<ChildT, Log2Dim>::getValueLevelAndCache(const Coord& xyz, AccessorT& acc) const
1395 {
1396  const Index n = this->coordToOffset(xyz);
1397  if (this->isChildMaskOn(n)) {
1398  acc.insert(xyz, mNodes[n].getChild());
1399  return mNodes[n].getChild()->getValueLevelAndCache(xyz, acc);
1400  }
1401  return LEVEL;
1402 }
1403 
1404 
1405 template<typename ChildT, Index Log2Dim>
1406 inline bool
1408 {
1409  const Index n = this->coordToOffset(xyz);
1410  if (this->isChildMaskOff(n)) {
1411  value = mNodes[n].getValue();
1412  return this->isValueMaskOn(n);
1413  }
1414  return mNodes[n].getChild()->probeValue(xyz, value);
1415 }
1416 
1417 template<typename ChildT, Index Log2Dim>
1418 template<typename AccessorT>
1419 inline bool
1421  ValueType& value, AccessorT& acc) const
1422 {
1423  const Index n = this->coordToOffset(xyz);
1424  if (this->isChildMaskOn(n)) {
1425  acc.insert(xyz, mNodes[n].getChild());
1426  return mNodes[n].getChild()->probeValueAndCache(xyz, value, acc);
1427  }
1428  value = mNodes[n].getValue();
1429  return this->isValueMaskOn(n);
1430 }
1431 
1432 
1433 template<typename ChildT, Index Log2Dim>
1434 inline void
1436 {
1437  const Index n = this->coordToOffset(xyz);
1438  bool hasChild = this->isChildMaskOn(n);
1439  if (!hasChild && this->isValueMaskOn(n)) {
1440  // If the voxel belongs to a constant tile that is active,
1441  // a child subtree must be constructed.
1442  hasChild = true;
1443  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/true));
1444  }
1445  if (hasChild) mNodes[n].getChild()->setValueOff(xyz);
1446 }
1447 
1448 
1449 template<typename ChildT, Index Log2Dim>
1450 inline void
1452 {
1453  const Index n = this->coordToOffset(xyz);
1454  bool hasChild = this->isChildMaskOn(n);
1455  if (!hasChild && !this->isValueMaskOn(n)) {
1456  // If the voxel belongs to a constant tile that is inactive,
1457  // a child subtree must be constructed.
1458  hasChild = true;
1459  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/false));
1460  }
1461  if (hasChild) mNodes[n].getChild()->setValueOn(xyz);
1462 }
1463 
1464 
1465 template<typename ChildT, Index Log2Dim>
1466 inline void
1468 {
1469  const Index n = InternalNode::coordToOffset(xyz);
1470  bool hasChild = this->isChildMaskOn(n);
1471  if (!hasChild) {
1472  const bool active = this->isValueMaskOn(n);
1473  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1474  // If the voxel belongs to a tile that is either active or that
1475  // has a constant value that is different from the one provided,
1476  // a child subtree must be constructed.
1477  hasChild = true;
1478  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1479  }
1480  }
1481  if (hasChild) mNodes[n].getChild()->setValueOff(xyz, value);
1482 }
1483 
1484 template<typename ChildT, Index Log2Dim>
1485 template<typename AccessorT>
1486 inline void
1488  const ValueType& value, AccessorT& acc)
1489 {
1490  const Index n = InternalNode::coordToOffset(xyz);
1491  bool hasChild = this->isChildMaskOn(n);
1492  if (!hasChild) {
1493  const bool active = this->isValueMaskOn(n);
1494  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1495  // If the voxel belongs to a tile that is either active or that
1496  // has a constant value that is different from the one provided,
1497  // a child subtree must be constructed.
1498  hasChild = true;
1499  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1500  }
1501  }
1502  if (hasChild) {
1503  ChildT* child = mNodes[n].getChild();
1504  acc.insert(xyz, child);
1505  child->setValueOffAndCache(xyz, value, acc);
1506  }
1507 }
1508 
1509 
1510 template<typename ChildT, Index Log2Dim>
1511 inline void
1513 {
1514  const Index n = this->coordToOffset(xyz);
1515  bool hasChild = this->isChildMaskOn(n);
1516  if (!hasChild) {
1517  const bool active = this->isValueMaskOn(n); // tile's active state
1518  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1519  // If the voxel belongs to a tile that is either inactive or that
1520  // has a constant value that is different from the one provided,
1521  // a child subtree must be constructed.
1522  hasChild = true;
1523  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1524  }
1525  }
1526  if (hasChild) mNodes[n].getChild()->setValueOn(xyz, value);
1527 }
1528 
1529 template<typename ChildT, Index Log2Dim>
1530 template<typename AccessorT>
1531 inline void
1533  const ValueType& value, AccessorT& acc)
1534 {
1535  const Index n = this->coordToOffset(xyz);
1536  bool hasChild = this->isChildMaskOn(n);
1537  if (!hasChild) {
1538  const bool active = this->isValueMaskOn(n);
1539  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1540  // If the voxel belongs to a tile that is either inactive or that
1541  // has a constant value that is different from the one provided,
1542  // a child subtree must be constructed.
1543  hasChild = true;
1544  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1545  }
1546  }
1547  if (hasChild) {
1548  acc.insert(xyz, mNodes[n].getChild());
1549  mNodes[n].getChild()->setValueAndCache(xyz, value, acc);
1550  }
1551 }
1552 
1553 
1554 template<typename ChildT, Index Log2Dim>
1555 inline void
1557 {
1558  const Index n = this->coordToOffset(xyz);
1559  bool hasChild = this->isChildMaskOn(n);
1560  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1561  // If the voxel has a tile value that is different from the one provided,
1562  // a child subtree must be constructed.
1563  const bool active = this->isValueMaskOn(n);
1564  hasChild = true;
1565  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1566  }
1567  if (hasChild) mNodes[n].getChild()->setValueOnly(xyz, value);
1568 }
1569 
1570 template<typename ChildT, Index Log2Dim>
1571 template<typename AccessorT>
1572 inline void
1574  const ValueType& value, AccessorT& acc)
1575 {
1576  const Index n = this->coordToOffset(xyz);
1577  bool hasChild = this->isChildMaskOn(n);
1578  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1579  // If the voxel has a tile value that is different from the one provided,
1580  // a child subtree must be constructed.
1581  const bool active = this->isValueMaskOn(n);
1582  hasChild = true;
1583  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1584  }
1585  if (hasChild) {
1586  acc.insert(xyz, mNodes[n].getChild());
1587  mNodes[n].getChild()->setValueOnlyAndCache(xyz, value, acc);
1588  }
1589 }
1590 
1591 
1592 template<typename ChildT, Index Log2Dim>
1593 inline void
1595 {
1596  const Index n = this->coordToOffset(xyz);
1597  bool hasChild = this->isChildMaskOn(n);
1598  if (!hasChild) {
1599  if (on != this->isValueMaskOn(n)) {
1600  // If the voxel belongs to a tile with the wrong active state,
1601  // then a child subtree must be constructed.
1602  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1603  hasChild = true;
1604  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1605  }
1606  }
1607  if (hasChild) mNodes[n].getChild()->setActiveState(xyz, on);
1608 }
1609 
1610 template<typename ChildT, Index Log2Dim>
1611 template<typename AccessorT>
1612 inline void
1613 InternalNode<ChildT, Log2Dim>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc)
1614 {
1615  const Index n = this->coordToOffset(xyz);
1616  bool hasChild = this->isChildMaskOn(n);
1617  if (!hasChild) {
1618  if (on != this->isValueMaskOn(n)) {
1619  // If the voxel belongs to a tile with the wrong active state,
1620  // then a child subtree must be constructed.
1621  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1622  hasChild = true;
1623  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1624  }
1625  }
1626  if (hasChild) {
1627  ChildT* child = mNodes[n].getChild();
1628  acc.insert(xyz, child);
1629  child->setActiveStateAndCache(xyz, on, acc);
1630  }
1631 }
1632 
1633 
1634 template<typename ChildT, Index Log2Dim>
1635 inline void
1637 {
1638  mValueMask = !mChildMask;
1639  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1640  mNodes[iter.pos()].getChild()->setValuesOn();
1641  }
1642 }
1643 
1644 
1645 template<typename ChildT, Index Log2Dim>
1646 template<typename ModifyOp>
1647 inline void
1648 InternalNode<ChildT, Log2Dim>::modifyValue(const Coord& xyz, const ModifyOp& op)
1649 {
1650  const Index n = InternalNode::coordToOffset(xyz);
1651  bool hasChild = this->isChildMaskOn(n);
1652  if (!hasChild) {
1653  // Need to create a child if the tile is inactive,
1654  // in order to activate voxel (x, y, z).
1655  const bool active = this->isValueMaskOn(n);
1656  bool createChild = !active;
1657  if (!createChild) {
1658  // Need to create a child if applying the functor
1659  // to the tile value produces a different value.
1660  const ValueType& tileVal = mNodes[n].getValue();
1661  ValueType modifiedVal = tileVal;
1662  op(modifiedVal);
1663  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1664  }
1665  if (createChild) {
1666  hasChild = true;
1667  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1668  }
1669  }
1670  if (hasChild) mNodes[n].getChild()->modifyValue(xyz, op);
1671 }
1672 
1673 template<typename ChildT, Index Log2Dim>
1674 template<typename ModifyOp, typename AccessorT>
1675 inline void
1676 InternalNode<ChildT, Log2Dim>::modifyValueAndCache(const Coord& xyz, const ModifyOp& op,
1677  AccessorT& acc)
1678 {
1679  const Index n = InternalNode::coordToOffset(xyz);
1680  bool hasChild = this->isChildMaskOn(n);
1681  if (!hasChild) {
1682  // Need to create a child if the tile is inactive,
1683  // in order to activate voxel (x, y, z).
1684  const bool active = this->isValueMaskOn(n);
1685  bool createChild = !active;
1686  if (!createChild) {
1687  // Need to create a child if applying the functor
1688  // to the tile value produces a different value.
1689  const ValueType& tileVal = mNodes[n].getValue();
1690  ValueType modifiedVal = tileVal;
1691  op(modifiedVal);
1692  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1693  }
1694  if (createChild) {
1695  hasChild = true;
1696  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1697  }
1698  }
1699  if (hasChild) {
1700  ChildNodeType* child = mNodes[n].getChild();
1701  acc.insert(xyz, child);
1702  child->modifyValueAndCache(xyz, op, acc);
1703  }
1704 }
1705 
1706 
1707 template<typename ChildT, Index Log2Dim>
1708 template<typename ModifyOp>
1709 inline void
1711 {
1712  const Index n = InternalNode::coordToOffset(xyz);
1713  bool hasChild = this->isChildMaskOn(n);
1714  if (!hasChild) {
1715  const bool tileState = this->isValueMaskOn(n);
1716  const ValueType& tileVal = mNodes[n].getValue();
1717  bool modifiedState = !tileState;
1718  ValueType modifiedVal = tileVal;
1719  op(modifiedVal, modifiedState);
1720  // Need to create a child if applying the functor to the tile
1721  // produces a different value or active state.
1722  if (modifiedState != tileState || !math::isExactlyEqual(modifiedVal, tileVal)) {
1723  hasChild = true;
1724  this->setChildNode(n, new ChildNodeType(xyz, tileVal, tileState));
1725  }
1726  }
1727  if (hasChild) mNodes[n].getChild()->modifyValueAndActiveState(xyz, op);
1728 }
1729 
1730 template<typename ChildT, Index Log2Dim>
1731 template<typename ModifyOp, typename AccessorT>
1732 inline void
1734  const Coord& xyz, const ModifyOp& op, AccessorT& acc)
1735 {
1736  const Index n = InternalNode::coordToOffset(xyz);
1737  bool hasChild = this->isChildMaskOn(n);
1738  if (!hasChild) {
1739  const bool tileState = this->isValueMaskOn(n);
1740  const ValueType& tileVal = mNodes[n].getValue();
1741  bool modifiedState = !tileState;
1742  ValueType modifiedVal = tileVal;
1743  op(modifiedVal, modifiedState);
1744  // Need to create a child if applying the functor to the tile
1745  // produces a different value or active state.
1746  if (modifiedState != tileState || !math::isExactlyEqual(modifiedVal, tileVal)) {
1747  hasChild = true;
1748  this->setChildNode(n, new ChildNodeType(xyz, tileVal, tileState));
1749  }
1750  }
1751  if (hasChild) {
1752  ChildNodeType* child = mNodes[n].getChild();
1753  acc.insert(xyz, child);
1754  child->modifyValueAndActiveStateAndCache(xyz, op, acc);
1755  }
1756 }
1757 
1758 
1760 
1761 
1762 template<typename ChildT, Index Log2Dim>
1763 inline void
1764 InternalNode<ChildT, Log2Dim>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1765 {
1766  Coord xyz, tileMin, tileMax;
1767  for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
1768  xyz.setX(x);
1769  for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
1770  xyz.setY(y);
1771  for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
1772  xyz.setZ(z);
1773 
1774  // Get the bounds of the tile that contains voxel (x, y, z).
1775  const Index n = this->coordToOffset(xyz);
1776  tileMin = this->offsetToGlobalCoord(n);
1777  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
1778 
1779  if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
1780  // If the box defined by (xyz, bbox.max()) doesn't completely enclose
1781  // the tile to which xyz belongs, create a child node (or retrieve
1782  // the existing one).
1783  ChildT* child = NULL;
1784  if (this->isChildMaskOff(n)) {
1785  // Replace the tile with a newly-created child that is initialized
1786  // with the tile's value and active state.
1787  child = new ChildT(xyz, mNodes[n].getValue(), this->isValueMaskOn(n));
1788  this->setChildNode(n, child);
1789  } else {
1790  child = mNodes[n].getChild();
1791  }
1792 
1793  // Forward the fill request to the child.
1794  if (child) {
1795  child->fill(CoordBBox(xyz, Coord::minComponent(bbox.max(), tileMax)),
1796  value, active);
1797  }
1798 
1799  } else {
1800  // If the box given by (xyz, bbox.max()) completely encloses
1801  // the tile to which xyz belongs, create the tile (if it
1802  // doesn't already exist) and give it the fill value.
1803  this->makeChildNodeEmpty(n, value);
1804  mValueMask.set(n, active);
1805  }
1806  }
1807  }
1808  }
1809 }
1810 
1811 
1813 
1814 
1815 template<typename ChildT, Index Log2Dim>
1816 template<typename DenseT>
1817 inline void
1818 InternalNode<ChildT, Log2Dim>::copyToDense(const CoordBBox& bbox, DenseT& dense) const
1819 {
1820  typedef typename DenseT::ValueType DenseValueType;
1821 
1822  const size_t xStride = dense.xStride(), yStride = dense.yStride();// zStride=1
1823  const Coord& min = dense.bbox().min();
1824  for (Coord xyz = bbox.min(), max; xyz[0] <= bbox.max()[0]; xyz[0] = max[0] + 1) {
1825  for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = max[1] + 1) {
1826  for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = max[2] + 1) {
1827  const Index n = this->coordToOffset(xyz);
1828  // Get max coordinates of the child node that contains voxel xyz.
1829  max = this->offsetToGlobalCoord(n).offsetBy(ChildT::DIM-1);
1830 
1831  // Get the bbox of the interection of bbox and the child node
1832  CoordBBox sub(xyz, Coord::minComponent(bbox.max(), max));
1833 
1834  if (this->isChildMaskOn(n)) {//is a child
1835  mNodes[n].getChild()->copyToDense(sub, dense);
1836  } else {//a tile value
1837  const ValueType value = mNodes[n].getValue();
1838  sub.translate(-min);
1839  DenseValueType* a0 = dense.data() + sub.min()[2];
1840  for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
1841  DenseValueType* a1 = a0 + x*xStride;
1842  for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
1843  DenseValueType* a2 = a1 + y*yStride;
1844  for (Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z) {
1845  *a2++ = DenseValueType(value);
1846  }
1847  }
1848  }
1849  }
1850  }
1851  }
1852  }
1853 }
1854 
1855 
1857 
1858 
1859 template<typename ChildT, Index Log2Dim>
1860 inline void
1861 InternalNode<ChildT, Log2Dim>::writeTopology(std::ostream& os, bool toHalf) const
1862 {
1863  mChildMask.save(os);
1864  mValueMask.save(os);
1865 
1866  {
1867  // Copy all of this node's values into an array.
1868  boost::shared_array<ValueType> values(new ValueType[NUM_VALUES]);
1869  const ValueType zero = zeroVal<ValueType>();
1870  for (Index i = 0; i < NUM_VALUES; ++i) {
1871  values[i] = (mChildMask.isOff(i) ? mNodes[i].getValue() : zero);
1872  }
1873  // Compress (optionally) and write out the contents of the array.
1874  io::writeCompressedValues(os, values.get(), NUM_VALUES, mValueMask, mChildMask, toHalf);
1875  }
1876  // Write out the child nodes in order.
1877  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1878  iter->writeTopology(os, toHalf);
1879  }
1880 }
1881 
1882 
1883 template<typename ChildT, Index Log2Dim>
1884 inline void
1885 InternalNode<ChildT, Log2Dim>::readTopology(std::istream& is, bool fromHalf)
1886 {
1887  mChildMask.load(is);
1888  mValueMask.load(is);
1889 
1891  for (Index i = 0; i < NUM_VALUES; ++i) {
1892  if (this->isChildMaskOn(i)) {
1893  ChildNodeType* child =
1894  new ChildNodeType(offsetToGlobalCoord(i), zeroVal<ValueType>());
1895  mNodes[i].setChild(child);
1896  child->readTopology(is);
1897  } else {
1898  ValueType value;
1899  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
1900  mNodes[i].setValue(value);
1901  }
1902  }
1903  } else {
1904  const bool oldVersion =
1906  const Index numValues = (oldVersion ? mChildMask.countOff() : NUM_VALUES);
1907  {
1908  // Read in (and uncompress, if necessary) all of this node's values
1909  // into a contiguous array.
1910  boost::shared_array<ValueType> values(new ValueType[numValues]);
1911  io::readCompressedValues(is, values.get(), numValues, mValueMask, fromHalf);
1912 
1913  // Copy values from the array into this node's table.
1914  if (oldVersion) {
1915  Index n = 0;
1916  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
1917  mNodes[iter.pos()].setValue(values[n++]);
1918  }
1919  assert(n == numValues);
1920  } else {
1921  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
1922  mNodes[iter.pos()].setValue(values[iter.pos()]);
1923  }
1924  }
1925  }
1926  // Read in all child nodes and insert them into the table at their proper locations.
1927  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1928  ChildNodeType* child = new ChildNodeType(iter.getCoord(), zeroVal<ValueType>());
1929  mNodes[iter.pos()].setChild(child);
1930  child->readTopology(is, fromHalf);
1931  }
1932  }
1933 }
1934 
1935 
1937 
1938 
1939 template<typename ChildT, Index Log2Dim>
1940 inline const typename ChildT::ValueType&
1942 {
1943  return (this->isChildMaskOn(0) ? mNodes[0].getChild()->getFirstValue() : mNodes[0].getValue());
1944 }
1945 
1946 
1947 template<typename ChildT, Index Log2Dim>
1948 inline const typename ChildT::ValueType&
1950 {
1951  const Index n = NUM_VALUES - 1;
1952  return (this->isChildMaskOn(n) ? mNodes[n].getChild()->getLastValue() : mNodes[n].getValue());
1953 }
1954 
1955 
1957 
1958 
1959 template<typename ChildT, Index Log2Dim>
1960 inline void
1962 {
1963  this->signedFloodFill(background, math::negative(background));
1964 }
1965 
1966 
1967 template<typename ChildT, Index Log2Dim>
1968 inline void
1970  const ValueType& insideValue)
1971 {
1972  // First, flood fill all child nodes.
1973  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1974  iter->signedFloodFill(outsideValue, insideValue);
1975  }
1976  const Index first = mChildMask.findFirstOn();
1977  if (first < NUM_VALUES) {
1978  bool xInside = math::isNegative(mNodes[first].getChild()->getFirstValue()),
1979  yInside = xInside, zInside = xInside;
1980  for (Index x = 0; x != (1 << Log2Dim); ++x) {
1981  const int x00 = x << (2 * Log2Dim); // offset for block(x, 0, 0)
1982  if (isChildMaskOn(x00)) {
1983  xInside = math::isNegative(mNodes[x00].getChild()->getLastValue());
1984  }
1985  yInside = xInside;
1986  for (Index y = 0; y != (1 << Log2Dim); ++y) {
1987  const Index xy0 = x00 + (y << Log2Dim); // offset for block(x, y, 0)
1988  if (isChildMaskOn(xy0)) {
1989  yInside = math::isNegative(mNodes[xy0].getChild()->getLastValue());
1990  }
1991  zInside = yInside;
1992  for (Index z = 0; z != (1 << Log2Dim); ++z) {
1993  const Index xyz = xy0 + z; // offset for block(x, y, z)
1994  if (isChildMaskOn(xyz)) {
1995  zInside = math::isNegative(mNodes[xyz].getChild()->getLastValue());
1996  } else {
1997  mNodes[xyz].setValue(zInside ? insideValue : outsideValue);
1998  }
1999  }
2000  }
2001  }
2002  } else {//no child nodes exist simply use the sign of the first tile value.
2003  const ValueType v = math::isNegative(mNodes[0].getValue()) ? insideValue : outsideValue;
2004  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(v);
2005  }
2006 }
2007 
2008 
2009 template<typename ChildT, Index Log2Dim>
2010 inline void
2012 {
2013  for (Index i = 0; i < NUM_VALUES; ++i) {
2014  if (this->isChildMaskOn(i)) {
2015  mNodes[i].getChild()->negate();
2016  } else {
2017  mNodes[i].setValue(math::negative(mNodes[i].getValue()));
2018  }
2019  }
2020 
2021 }
2022 
2023 
2024 template<typename ChildT, Index Log2Dim>
2025 inline void
2027 {
2028  for (ValueOnIter iter = this->beginValueOn(); iter; ++iter) {
2029  this->setChildNode(iter.pos(), new ChildNodeType(iter.getCoord(), iter.getValue(), true));
2030  }
2031  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) iter->voxelizeActiveTiles();
2032 }
2033 
2034 
2036 
2037 
2038 template<typename ChildT, Index Log2Dim>
2039 template<MergePolicy Policy>
2040 inline void
2042  const ValueType& background, const ValueType& otherBackground)
2043 {
2045 
2046  switch (Policy) {
2047 
2048  case MERGE_ACTIVE_STATES:
2049  default:
2050  {
2051  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2052  const Index n = iter.pos();
2053  if (mChildMask.isOn(n)) {
2054  // Merge this node's child with the other node's child.
2055  mNodes[n].getChild()->template merge<MERGE_ACTIVE_STATES>(*iter,
2056  background, otherBackground);
2057  } else if (mValueMask.isOff(n)) {
2058  // Replace this node's inactive tile with the other node's child
2059  // and replace the other node's child with a tile of undefined value
2060  // (which is okay since the other tree is assumed to be cannibalized
2061  // in the process of merging).
2062  ChildNodeType* child = other.mNodes[n].getChild();
2063  other.mChildMask.setOff(n);
2064  child->resetBackground(otherBackground, background);
2065  this->setChildNode(n, child);
2066  }
2067  }
2068 
2069  // Copy active tile values.
2070  for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
2071  const Index n = iter.pos();
2072  if (mValueMask.isOff(n)) {
2073  // Replace this node's child or inactive tile with the other node's active tile.
2074  this->makeChildNodeEmpty(n, iter.getValue());
2075  mValueMask.setOn(n);
2076  }
2077  }
2078  break;
2079  }
2080 
2081  case MERGE_NODES:
2082  {
2083  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2084  const Index n = iter.pos();
2085  if (mChildMask.isOn(n)) {
2086  // Merge this node's child with the other node's child.
2087  mNodes[n].getChild()->template merge<Policy>(*iter, background, otherBackground);
2088  } else {
2089  // Replace this node's tile (regardless of its active state) with
2090  // the other node's child and replace the other node's child with
2091  // a tile of undefined value (which is okay since the other tree
2092  // is assumed to be cannibalized in the process of merging).
2093  ChildNodeType* child = other.mNodes[n].getChild();
2094  other.mChildMask.setOff(n);
2095  child->resetBackground(otherBackground, background);
2096  this->setChildNode(n, child);
2097  }
2098  }
2099  break;
2100  }
2101 
2103  {
2104  // Transfer children from the other tree to this tree.
2105  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2106  const Index n = iter.pos();
2107  if (mChildMask.isOn(n)) {
2108  // Merge this node's child with the other node's child.
2109  mNodes[n].getChild()->template merge<Policy>(*iter, background, otherBackground);
2110  } else {
2111  // Replace this node's tile with the other node's child, leaving the other
2112  // node with an inactive tile of undefined value (which is okay since
2113  // the other tree is assumed to be cannibalized in the process of merging).
2114  ChildNodeType* child = other.mNodes[n].getChild();
2115  other.mChildMask.setOff(n);
2116  child->resetBackground(otherBackground, background);
2117  if (mValueMask.isOn(n)) {
2118  // Merge the child with this node's active tile.
2119  child->template merge<Policy>(mNodes[n].getValue(), /*on=*/true);
2120  mValueMask.setOff(n);
2121  }
2122  mChildMask.setOn(n);
2123  mNodes[n].setChild(child);
2124  }
2125  }
2126 
2127  // Merge active tiles into this tree.
2128  for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
2129  const Index n = iter.pos();
2130  if (mChildMask.isOn(n)) {
2131  // Merge the other node's active tile into this node's child.
2132  mNodes[n].getChild()->template merge<Policy>(iter.getValue(), /*on=*/true);
2133  } else if (mValueMask.isOff(n)) {
2134  // Replace this node's inactive tile with the other node's active tile.
2135  mNodes[n].setValue(iter.getValue());
2136  mValueMask.setOn(n);
2137  }
2138  }
2139  break;
2140  }
2141 
2142  }
2144 }
2145 
2146 
2147 template<typename ChildT, Index Log2Dim>
2148 template<MergePolicy Policy>
2149 inline void
2150 InternalNode<ChildT, Log2Dim>::merge(const ValueType& tileValue, bool tileActive)
2151 {
2153 
2154  if (Policy != MERGE_ACTIVE_STATES_AND_NODES) return;
2155 
2156  // For MERGE_ACTIVE_STATES_AND_NODES, inactive tiles in the other tree are ignored.
2157  if (!tileActive) return;
2158 
2159  // Iterate over this node's children and inactive tiles.
2160  for (ValueOffIter iter = this->beginValueOff(); iter; ++iter) {
2161  const Index n = iter.pos();
2162  if (mChildMask.isOn(n)) {
2163  // Merge the other node's active tile into this node's child.
2164  mNodes[n].getChild()->template merge<Policy>(tileValue, /*on=*/true);
2165  } else {
2166  // Replace this node's inactive tile with the other node's active tile.
2167  iter.setValue(tileValue);
2168  mValueMask.setOn(n);
2169  }
2170  }
2172 }
2173 
2174 
2176 
2177 
2178 template<typename ChildT, Index Log2Dim>
2179 template<typename OtherChildT>
2180 inline void
2182 {
2183  typedef typename InternalNode<OtherChildT, Log2Dim>::ChildOnCIter OtherChildIter;
2184  typedef typename InternalNode<OtherChildT, Log2Dim>::ValueOnCIter OtherValueIter;
2185 
2186  // Loop over other node's child nodes
2187  for (OtherChildIter iter = other.cbeginChildOn(); iter; ++iter) {
2188  const Index i = iter.pos();
2189  if (mChildMask.isOn(i)) {//this has a child node
2190  mNodes[i].getChild()->topologyUnion(*iter);
2191  } else {// this is a tile so replace it with a child branch with identical topology
2192  ChildNodeType* child = new ChildNodeType(*iter, mNodes[i].getValue(), TopologyCopy());
2193  if (mValueMask.isOn(i)) {
2194  mValueMask.isOff(i);//we're replacing the active tile with a child branch
2195  child->setValuesOn();//activate all values since it was an active tile
2196  }
2197  mChildMask.setOn(i);
2198  mNodes[i].setChild(child);
2199  }
2200  }
2201  // Loop over other node's active tiles
2202  for (OtherValueIter iter = other.cbeginValueOn(); iter; ++iter) {
2203  const Index i = iter.pos();
2204  if (mChildMask.isOn(i)) {
2205  mNodes[i].getChild()->setValuesOn();
2206  } else if (mValueMask.isOff(i)) { //inactive tile
2207  mValueMask.setOn(i);
2208  }
2209  }
2210 }
2211 
2212 template<typename ChildT, Index Log2Dim>
2213 template<typename OtherChildT>
2214 inline void
2216  const ValueType& background)
2217 {
2218  // Loop over this node's child nodes
2219  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2220  const Index i = iter.pos();
2221  if (other.mChildMask.isOn(i)) {//other also has a child node
2222  iter->topologyIntersection(*(other.mNodes[i].getChild()), background);
2223  } else if (other.mValueMask.isOff(i)) {//other is an inactive tile
2224  delete mNodes[i].getChild();//convert child to an inactive tile
2225  mNodes[i].setValue(background);
2226  mChildMask.setOff(i);
2227  mValueMask.setOff(i);
2228  }
2229  }
2230 
2231  // Loop over this node's active tiles
2232  for (ValueOnCIter iter = this->cbeginValueOn(); iter; ++iter) {
2233  const Index i = iter.pos();
2234  if (other.mChildMask.isOn(i)) {//other has a child node
2235  ChildNodeType* child = new ChildNodeType(*(other.mNodes[i].getChild()),
2236  *iter, TopologyCopy());
2237  this->setChildNode(i, child);//replace the active tile with a child branch
2238  } else if (other.mValueMask.isOff(i)) {//other is an inactive tile
2239  mValueMask.setOff(i);//convert active tile to an inactive tile
2240  }
2241  }
2242 }
2243 
2244 template<typename ChildT, Index Log2Dim>
2245 template<typename OtherChildT>
2246 inline void
2248  const ValueType& background)
2249 {
2250  typedef typename InternalNode<OtherChildT, Log2Dim>::ChildOnCIter OtherChildIter;
2251  typedef typename InternalNode<OtherChildT, Log2Dim>::ValueOnCIter OtherValueIter;
2252 
2253  // Loop over other node's child nodes
2254  for (OtherChildIter iter = other.cbeginChildOn(); iter; ++iter) {
2255  const Index i = iter.pos();
2256  if (mChildMask.isOn(i)) {//this has a child node
2257  mNodes[i].getChild()->topologyDifference(*iter, background);
2258  } else if (mValueMask.isOn(i)) {// this is an active tile
2259  ChildNodeType* child = new ChildNodeType(iter.getCoord(), mNodes[i].getValue(), true);
2260  child->topologyDifference(*iter, background);
2261  this->setChildNode(i, child);//we're replacing the active tile with a child branch
2262  }
2263  }
2264 
2265  // Loop over other node's active tiles
2266  for (OtherValueIter iter = other.cbeginValueOn(); iter; ++iter) {
2267  const Index i = iter.pos();
2268  if (mChildMask.isOn(i)) {//this has a child node
2269  delete mNodes[i].getChild();//convert child to an inactive tile
2270  mNodes[i].setValue(background);
2271  mChildMask.setOff(i);
2272  mValueMask.setOff(i);
2273  } else if (mValueMask.isOn(i)) {//this is an active tile
2274  mValueMask.setOff(i);//convert active tile to an inactive tile
2275  }
2276  }
2277 }
2278 
2280 
2281 
2282 template<typename ChildT, Index Log2Dim>
2283 template<typename CombineOp>
2284 inline void
2286 {
2287  const ValueType zero = zeroVal<ValueType>();
2288 
2290 
2291  for (Index i = 0; i < NUM_VALUES; ++i) {
2292  if (this->isChildMaskOff(i) && other.isChildMaskOff(i)) {
2293  // Both this node and the other node have constant values (tiles).
2294  // Combine the two values and store the result as this node's new tile value.
2295  op(args.setARef(mNodes[i].getValue())
2296  .setAIsActive(isValueMaskOn(i))
2297  .setBRef(other.mNodes[i].getValue())
2298  .setBIsActive(other.isValueMaskOn(i)));
2299  mNodes[i].setValue(args.result());
2300  mValueMask.set(i, args.resultIsActive());
2301  } else if (this->isChildMaskOn(i) && other.isChildMaskOff(i)) {
2302  // Combine this node's child with the other node's constant value.
2303  ChildNodeType* child = mNodes[i].getChild();
2304  assert(child);
2305  if (child) {
2306  child->combine(other.mNodes[i].getValue(), other.isValueMaskOn(i), op);
2307  }
2308  } else if (this->isChildMaskOff(i) && other.isChildMaskOn(i)) {
2309  // Combine this node's constant value with the other node's child.
2310  ChildNodeType* child = other.mNodes[i].getChild();
2311  assert(child);
2312  if (child) {
2313  // Combine this node's constant value with the other node's child,
2314  // but use a new functor in which the A and B values are swapped,
2315  // since the constant value is the A value, not the B value.
2317  child->combine(mNodes[i].getValue(), isValueMaskOn(i), swappedOp);
2318 
2319  // Steal the other node's child.
2320  other.mChildMask.setOff(i);
2321  other.mNodes[i].setValue(zero);
2322  this->setChildNode(i, child);
2323  }
2324 
2325  } else /*if (isChildMaskOn(i) && other.isChildMaskOn(i))*/ {
2326  // Combine this node's child with the other node's child.
2328  *child = mNodes[i].getChild(),
2329  *otherChild = other.mNodes[i].getChild();
2330  assert(child);
2331  assert(otherChild);
2332  if (child && otherChild) {
2333  child->combine(*otherChild, op);
2334  }
2335  }
2336  }
2337 }
2338 
2339 
2340 template<typename ChildT, Index Log2Dim>
2341 template<typename CombineOp>
2342 inline void
2343 InternalNode<ChildT, Log2Dim>::combine(const ValueType& value, bool valueIsActive, CombineOp& op)
2344 {
2346 
2347  for (Index i = 0; i < NUM_VALUES; ++i) {
2348  if (this->isChildMaskOff(i)) {
2349  // Combine this node's constant value with the given constant value.
2350  op(args.setARef(mNodes[i].getValue())
2351  .setAIsActive(isValueMaskOn(i))
2352  .setBRef(value)
2353  .setBIsActive(valueIsActive));
2354  mNodes[i].setValue(args.result());
2355  mValueMask.set(i, args.resultIsActive());
2356  } else /*if (isChildMaskOn(i))*/ {
2357  // Combine this node's child with the given constant value.
2358  ChildNodeType* child = mNodes[i].getChild();
2359  assert(child);
2360  if (child) child->combine(value, valueIsActive, op);
2361  }
2362  }
2363 }
2364 
2365 
2367 
2368 
2369 template<typename ChildT, Index Log2Dim>
2370 template<typename CombineOp>
2371 inline void
2373  CombineOp& op)
2374 {
2376 
2377  for (Index i = 0; i < NUM_VALUES; ++i) {
2378  if (other0.isChildMaskOff(i) && other1.isChildMaskOff(i)) {
2379  op(args.setARef(other0.mNodes[i].getValue())
2380  .setAIsActive(other0.isValueMaskOn(i))
2381  .setBRef(other1.mNodes[i].getValue())
2382  .setBIsActive(other1.isValueMaskOn(i)));
2383  // Replace child i with a constant value.
2384  this->makeChildNodeEmpty(i, args.result());
2385  mValueMask.set(i, args.resultIsActive());
2386  } else {
2387  ChildNodeType* otherChild = other0.isChildMaskOn(i)
2388  ? other0.mNodes[i].getChild() : other1.mNodes[i].getChild();
2389  assert(otherChild);
2390  if (this->isChildMaskOff(i)) {
2391  // Add a new child with the same coordinates, etc. as the other node's child.
2392  this->setChildNode(i, new ChildNodeType(otherChild->origin(), mNodes[i].getValue()));
2393  }
2394 
2395  if (other0.isChildMaskOff(i)) {
2396  // Combine node1's child with node0's constant value
2397  // and write the result into child i.
2398  mNodes[i].getChild()->combine2(other0.mNodes[i].getValue(),
2399  *other1.mNodes[i].getChild(), other0.isValueMaskOn(i), op);
2400  } else if (other1.isChildMaskOff(i)) {
2401  // Combine node0's child with node1's constant value
2402  // and write the result into child i.
2403  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2404  other1.mNodes[i].getValue(), other1.isValueMaskOn(i), op);
2405  } else {
2406  // Combine node0's child with node1's child
2407  // and write the result into child i.
2408  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2409  *other1.mNodes[i].getChild(), op);
2410  }
2411  }
2412  }
2413 }
2414 
2415 
2416 template<typename ChildT, Index Log2Dim>
2417 template<typename CombineOp>
2418 inline void
2420  bool valueIsActive, CombineOp& op)
2421 {
2423 
2424  for (Index i = 0; i < NUM_VALUES; ++i) {
2425  if (other.isChildMaskOff(i)) {
2426  op(args.setARef(value)
2427  .setAIsActive(valueIsActive)
2428  .setBRef(other.mNodes[i].getValue())
2429  .setBIsActive(other.isValueMaskOn(i)));
2430  // Replace child i with a constant value.
2431  this->makeChildNodeEmpty(i, args.result());
2432  mValueMask.set(i, args.resultIsActive());
2433  } else {
2434  ChildNodeType* otherChild = other.mNodes[i].getChild();
2435  assert(otherChild);
2436  if (this->isChildMaskOff(i)) {
2437  // Add a new child with the same coordinates, etc.
2438  // as the other node's child.
2440  this->setChildNode(i, new ChildNodeType(*otherChild));
2441  }
2442  // Combine the other node's child with a constant value
2443  // and write the result into child i.
2444  mNodes[i].getChild()->combine2(value, *otherChild, valueIsActive, op);
2445  }
2446  }
2447 }
2448 
2449 
2450 template<typename ChildT, Index Log2Dim>
2451 template<typename CombineOp>
2452 inline void
2454  bool valueIsActive, CombineOp& op)
2455 {
2457 
2458  for (Index i = 0; i < NUM_VALUES; ++i) {
2459  if (other.isChildMaskOff(i)) {
2460  op(args.setARef(other.mNodes[i].getValue())
2461  .setAIsActive(other.isValueMaskOn(i))
2462  .setBRef(value)
2463  .setBIsActive(valueIsActive));
2464  // Replace child i with a constant value.
2465  this->makeChildNodeEmpty(i, args.result());
2466  mValueMask.set(i, args.resultIsActive());
2467  } else {
2468  ChildNodeType* otherChild = other.mNodes[i].getChild();
2469  assert(otherChild);
2470  if (this->isChildMaskOff(i)) {
2471  // Add a new child with the same coordinates, etc. as the other node's child.
2472  this->setChildNode(i, new ChildNodeType(otherChild->origin(), mNodes[i].getValue()));
2473  }
2474  // Combine the other node's child with a constant value
2475  // and write the result into child i.
2476  mNodes[i].getChild()->combine2(*otherChild, value, valueIsActive, op);
2477  }
2478  }
2479 }
2480 
2481 
2483 
2484 
2485 template<typename ChildT, Index Log2Dim>
2486 template<typename BBoxOp>
2487 inline void
2489 {
2490  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) {
2491 #ifdef _MSC_VER
2492  op.operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
2493 #else
2494  op.template operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
2495 #endif
2496  }
2497  if (op.template descent<LEVEL>()) {
2498  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) i->visitActiveBBox(op);
2499  } else {
2500  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) {
2501 #ifdef _MSC_VER
2502  op.operator()<LEVEL>(i->getNodeBoundingBox());
2503 #else
2504  op.template operator()<LEVEL>(i->getNodeBoundingBox());
2505 #endif
2506  }
2507  }
2508 }
2509 
2510 
2511 template<typename ChildT, Index Log2Dim>
2512 template<typename VisitorOp>
2513 inline void
2515 {
2516  doVisit<InternalNode, VisitorOp, ChildAllIter>(*this, op);
2517 }
2518 
2519 
2520 template<typename ChildT, Index Log2Dim>
2521 template<typename VisitorOp>
2522 inline void
2524 {
2525  doVisit<const InternalNode, VisitorOp, ChildAllCIter>(*this, op);
2526 }
2527 
2528 
2529 template<typename ChildT, Index Log2Dim>
2530 template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
2531 inline void
2532 InternalNode<ChildT, Log2Dim>::doVisit(NodeT& self, VisitorOp& op)
2533 {
2534  typename NodeT::ValueType val;
2535  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2536  if (op(iter)) continue;
2537  if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
2538  child->visit(op);
2539  }
2540  }
2541 }
2542 
2543 
2545 
2546 
2547 template<typename ChildT, Index Log2Dim>
2548 template<typename OtherNodeType, typename VisitorOp>
2549 inline void
2550 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op)
2551 {
2552  doVisit2Node<InternalNode, OtherNodeType, VisitorOp, ChildAllIter,
2553  typename OtherNodeType::ChildAllIter>(*this, other, op);
2554 }
2555 
2556 
2557 template<typename ChildT, Index Log2Dim>
2558 template<typename OtherNodeType, typename VisitorOp>
2559 inline void
2560 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op) const
2561 {
2562  doVisit2Node<const InternalNode, OtherNodeType, VisitorOp, ChildAllCIter,
2563  typename OtherNodeType::ChildAllCIter>(*this, other, op);
2564 }
2565 
2566 
2567 template<typename ChildT, Index Log2Dim>
2568 template<
2569  typename NodeT,
2570  typename OtherNodeT,
2571  typename VisitorOp,
2572  typename ChildAllIterT,
2573  typename OtherChildAllIterT>
2574 inline void
2575 InternalNode<ChildT, Log2Dim>::doVisit2Node(NodeT& self, OtherNodeT& other, VisitorOp& op)
2576 {
2577  // Allow the two nodes to have different ValueTypes, but not different dimensions.
2578  BOOST_STATIC_ASSERT(OtherNodeT::NUM_VALUES == NodeT::NUM_VALUES);
2579  BOOST_STATIC_ASSERT(OtherNodeT::LEVEL == NodeT::LEVEL);
2580 
2581  typename NodeT::ValueType val;
2582  typename OtherNodeT::ValueType otherVal;
2583 
2584  ChildAllIterT iter = self.beginChildAll();
2585  OtherChildAllIterT otherIter = other.beginChildAll();
2586 
2587  for ( ; iter && otherIter; ++iter, ++otherIter)
2588  {
2589  const size_t skipBranch = static_cast<size_t>(op(iter, otherIter));
2590 
2591  typename ChildAllIterT::ChildNodeType* child =
2592  (skipBranch & 1U) ? NULL : iter.probeChild(val);
2593  typename OtherChildAllIterT::ChildNodeType* otherChild =
2594  (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
2595 
2596  if (child != NULL && otherChild != NULL) {
2597  child->visit2Node(*otherChild, op);
2598  } else if (child != NULL) {
2599  child->visit2(otherIter, op);
2600  } else if (otherChild != NULL) {
2601  otherChild->visit2(iter, op, /*otherIsLHS=*/true);
2602  }
2603  }
2604 }
2605 
2606 
2608 
2609 
2610 template<typename ChildT, Index Log2Dim>
2611 template<typename OtherChildAllIterType, typename VisitorOp>
2612 inline void
2613 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
2614  VisitorOp& op, bool otherIsLHS)
2615 {
2616  doVisit2<InternalNode, VisitorOp, ChildAllIter, OtherChildAllIterType>(
2617  *this, otherIter, op, otherIsLHS);
2618 }
2619 
2620 
2621 template<typename ChildT, Index Log2Dim>
2622 template<typename OtherChildAllIterType, typename VisitorOp>
2623 inline void
2624 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
2625  VisitorOp& op, bool otherIsLHS) const
2626 {
2627  doVisit2<const InternalNode, VisitorOp, ChildAllCIter, OtherChildAllIterType>(
2628  *this, otherIter, op, otherIsLHS);
2629 }
2630 
2631 
2632 template<typename ChildT, Index Log2Dim>
2633 template<typename NodeT, typename VisitorOp, typename ChildAllIterT, typename OtherChildAllIterT>
2634 inline void
2635 InternalNode<ChildT, Log2Dim>::doVisit2(NodeT& self, OtherChildAllIterT& otherIter,
2636  VisitorOp& op, bool otherIsLHS)
2637 {
2638  if (!otherIter) return;
2639 
2640  const size_t skipBitMask = (otherIsLHS ? 2U : 1U);
2641 
2642  typename NodeT::ValueType val;
2643  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2644  const size_t skipBranch = static_cast<size_t>(
2645  otherIsLHS ? op(otherIter, iter) : op(iter, otherIter));
2646 
2647  typename ChildAllIterT::ChildNodeType* child =
2648  (skipBranch & skipBitMask) ? NULL : iter.probeChild(val);
2649 
2650  if (child != NULL) child->visit2(otherIter, op, otherIsLHS);
2651  }
2652 }
2653 
2654 
2656 
2657 
2658 template<typename ChildT, Index Log2Dim>
2659 inline void
2660 InternalNode<ChildT, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
2661 {
2662  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2663  iter->writeBuffers(os, toHalf);
2664  }
2665 }
2666 
2667 
2668 template<typename ChildT, Index Log2Dim>
2669 inline void
2670 InternalNode<ChildT, Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
2671 {
2672  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2673  iter->readBuffers(is, fromHalf);
2674  }
2675 }
2676 
2677 
2679 
2680 
2681 template<typename ChildT, Index Log2Dim>
2682 void
2684 {
2685  dims.push_back(Log2Dim);
2686  ChildNodeType::getNodeLog2Dims(dims);
2687 }
2688 
2689 
2690 template<typename ChildT, Index Log2Dim>
2691 inline void
2693 {
2694  assert(n<(1<<3*Log2Dim));
2695  xyz.setX(n >> 2*Log2Dim);
2696  n &= ((1<<2*Log2Dim)-1);
2697  xyz.setY(n >> Log2Dim);
2698  xyz.setZ(n & ((1<<Log2Dim)-1));
2699 }
2700 
2701 
2702 template<typename ChildT, Index Log2Dim>
2703 inline Index
2705 {
2706  return (((xyz[0]&DIM-1u)>>ChildNodeType::TOTAL)<<2*Log2Dim)
2707  + (((xyz[1]&DIM-1u)>>ChildNodeType::TOTAL)<< Log2Dim)
2708  + ((xyz[2]&DIM-1u)>>ChildNodeType::TOTAL);
2709 }
2710 
2711 
2712 template<typename ChildT, Index Log2Dim>
2713 inline Coord
2715 {
2716  Coord local;
2717  this->offsetToLocalCoord(n, local);
2718  local <<= ChildT::TOTAL;
2719  return local + this->origin();
2720 }
2721 
2722 
2724 
2725 
2726 template<typename ChildT, Index Log2Dim>
2727 inline void
2729  const ValueType& newBackground)
2730 {
2731  if (math::isExactlyEqual(oldBackground, newBackground)) return;
2732  for (Index i = 0; i < NUM_VALUES; ++i) {
2733  if (this->isChildMaskOn(i)) {
2734  mNodes[i].getChild()->resetBackground(oldBackground, newBackground);
2735  } else if (this->isValueMaskOff(i)) {
2736  if (math::isApproxEqual(mNodes[i].getValue(), oldBackground)) {
2737  mNodes[i].setValue(newBackground);
2738  } else if (math::isApproxEqual(mNodes[i].getValue(), math::negative(oldBackground))) {
2739  mNodes[i].setValue(math::negative(newBackground));
2740  }
2741  }
2742  }
2743 }
2744 
2745 
2746 template<typename ChildT, Index Log2Dim>
2747 template<typename OtherChildNodeType, Index OtherLog2Dim>
2748 inline bool
2751 {
2752  if (Log2Dim != OtherLog2Dim || mChildMask != other->mChildMask ||
2753  mValueMask != other->mValueMask) return false;
2754  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2755  if (!iter->hasSameTopology(other->mNodes[iter.pos()].getChild())) return false;
2756  }
2757  return true;
2758 }
2759 
2760 
2761 template<typename ChildT, Index Log2Dim>
2762 inline void
2764 {
2765  assert(child);
2766  if (this->isChildMaskOn(i)) {
2767  delete mNodes[i].getChild();
2768  } else {
2769  mChildMask.setOn(i);
2770  mValueMask.setOff(i);
2771  }
2772  mNodes[i].setChild(child);
2773 }
2774 
2775 template<typename ChildT, Index Log2Dim>
2776 inline void
2778 {
2779  assert(child);
2780  assert(mChildMask.isOff(i));
2781  mChildMask.setOn(i);
2782  mValueMask.setOff(i);
2783  mNodes[i].setChild(child);
2784 }
2785 
2786 
2787 template<typename ChildT, Index Log2Dim>
2788 inline ChildT*
2790 {
2791  if (this->isChildMaskOff(i)) {
2792  mNodes[i].setValue(value);
2793  return NULL;
2794  }
2795  ChildNodeType* child = mNodes[i].getChild();
2796  mChildMask.setOff(i);
2797  mNodes[i].setValue(value);
2798  return child;
2799 }
2800 
2801 
2802 template<typename ChildT, Index Log2Dim>
2803 inline void
2805 {
2806  delete this->unsetChildNode(n, value);
2807 }
2808 
2809 template<typename ChildT, Index Log2Dim>
2810 inline ChildT*
2812 {
2813  return (this->isChildMaskOn(n) ? mNodes[n].getChild() : NULL);
2814 }
2815 
2816 
2817 template<typename ChildT, Index Log2Dim>
2818 inline const ChildT*
2820 {
2821  return (this->isChildMaskOn(n) ? mNodes[n].getChild() : NULL);
2822 }
2823 
2824 } // namespace tree
2825 } // namespace OPENVDB_VERSION_NAME
2826 } // namespace openvdb
2827 
2828 #endif // OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
2829 
2830 // Copyright (c) 2012-2013 DreamWorks Animation LLC
2831 // All rights reserved. This software is distributed under the
2832 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
ValueIter(const MaskIterT &iter, NodeT *parent)
Definition: InternalNode.h:139
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:1060
OPENVDB_DEPRECATED Coord getOrigin() const
Return the grid index coordinates of this node&#39;s local origin.
Definition: InternalNode.h:240
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...
bool isValueMaskOn() const
Definition: InternalNode.h:657
void unsetItem(Index pos, const ValueT &value) const
Definition: InternalNode.h:180
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
const Coord & origin() const
Return the grid index coordinates of this node&#39;s local origin.
Definition: InternalNode.h:237
ChildNodeType * unsetChildNode(Index i, const ValueType &value)
Definition: InternalNode.h:2789
void visitActiveBBox(BBoxOp &) const
Calls the templated functor BBoxOp with bounding box information for all active tiles and leaf nodes ...
Definition: InternalNode.h:2488
NodeMaskType::OnIterator MaskOnIterator
Definition: InternalNode.h:107
ChildIter< const InternalNode, const ChildNodeType, MaskOnIterator, ChildOn > ChildOnCIter
Definition: InternalNode.h:189
ChildOffCIter cbeginChildOff() const
Definition: InternalNode.h:203
void signedFloodFill(const ValueType &background)
Overwrite each inactive value in this node and in any child nodes with a new value whose magnitude is...
Definition: InternalNode.h:1961
#define OPENVDB_DEPRECATED
Definition: Platform.h:47
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don&#39;t change its value.
Definition: InternalNode.h:1451
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:1385
Definition: InternalNode.h:113
int32_t Int32
Definition: Types.h:58
Definition: Types.h:190
ChildT & getItem(Index pos) const
Definition: InternalNode.h:126
ValueOffIter beginValueOff()
Definition: InternalNode.h:219
ChildNodeType * getChildNode(Index n)
Definition: InternalNode.h:2811
bool isValueMaskOff() const
Definition: InternalNode.h:659
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...
ValueAllIter beginValueAll()
Definition: InternalNode.h:220
bool isChildMaskOff(Index n) const
Definition: InternalNode.h:661
ValueIter< const InternalNode, const ValueType, MaskOffIterator, ChildOff > ChildOffCIter
Definition: InternalNode.h:191
ChildOnCIter cbeginChildOn() const
Definition: InternalNode.h:202
Index pos() const
Identical to offset.
Definition: Iterator.h:94
ChildOffCIter beginChildOff() const
Definition: InternalNode.h:206
NodeUnion< ValueType, ChildNodeType > UnionType
Definition: InternalNode.h:63
InternalNode()
Definition: InternalNode.h:84
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...
ChildOnCIter beginChildOn() const
Definition: InternalNode.h:205
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:1556
Definition: NodeMasks.h:220
This struct collects both input and output arguments to &quot;grid combiner&quot; functors used with the tree::...
Definition: Types.h:232
uint32_t Index32
Definition: Types.h:54
DenseIter< const InternalNode, const ChildNodeType, ValueType, ChildAll > ChildAllCIter
Definition: InternalNode.h:193
NodeType * probeNode(const Coord &xyz)
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return NULL.
void fill(const CoordBBox &bbox, const ValueType &, bool active=true)
Set all voxels within an axis-aligned box to a constant value. (The min and max coordinates are inclu...
Definition: InternalNode.h:1764
void visit(VisitorOp &)
Definition: InternalNode.h:2514
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition: InternalNode.h:1351
ValueIter< InternalNode, const ValueType, MaskOffIterator, ChildOff > ChildOffIter
Definition: InternalNode.h:190
void visit2(IterT &otherIter, VisitorOp &, bool otherIsLHS=false)
void combine(InternalNode &other, CombineOp &)
Definition: InternalNode.h:2285
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:1210
Definition: Types.h:346
Definition: Types.h:307
void makeChildNodeEmpty(Index n, const ValueType &value)
Definition: InternalNode.h:2804
ValueOnCIter cbeginValueOn() const
Definition: InternalNode.h:212
void setItem(Index pos, ChildT *child) const
Definition: InternalNode.h:174
void negate()
Definition: InternalNode.h:2011
bool isValueMaskOn(Index n) const
Definition: InternalNode.h:656
virtual ~InternalNode()
Definition: InternalNode.h:774
void visit2Node(OtherNodeType &other, VisitorOp &)
Definition: InternalNode.h:2550
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition: InternalNode.h:1613
bool isEmpty() const
Definition: InternalNode.h:266
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.
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:2692
Base class for sparse iterators over internal and leaf nodes.
Definition: Iterator.h:148
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:395
bool isChildMaskOff() const
Definition: InternalNode.h:662
ChildIter< InternalNode, ChildNodeType, MaskOnIterator, ChildOn > ChildOnIter
Definition: InternalNode.h:188
static void doVisit2(NodeT &, OtherChildAllIterT &, VisitorOp &, bool otherIsLHS)
Definition: InternalNode.h:2635
Index32 leafCount() const
Definition: InternalNode.h:787
Coord mOrigin
Global grid index coordinates (x,y,z) of the local origin of this node.
Definition: InternalNode.h:693
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1532
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:958
DenseIter()
Definition: InternalNode.h:162
Definition: InternalNode.h:112
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:482
void readCompressedValues(std::istream &is, ValueT *destBuf, Index destCount, const MaskT &valueMask, bool fromHalf)
Definition: Compression.h:276
static Index getLevel()
Definition: InternalNode.h:224
void setChildNode(Index i, ChildNodeType *child)
Definition: InternalNode.h:2777
ValueIter< const InternalNode, const ValueType, MaskOffIterator, ValueAll > ValueAllCIter
Definition: InternalNode.h:200
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:264
util::NodeMask< Log2Dim > NodeMaskType
Definition: InternalNode.h:64
const ValueType & getValue(const Coord &xyz) const
Definition: InternalNode.h:1362
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:107
Definition: InternalNode.h:57
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:2749
bool isNegative(const Type &x)
Return true if x is less than zero.
Definition: Math.h:306
OPENVDB_IMPORT uint32_t getFormatVersion(std::istream &)
Return the file format version number associated with the given input stream.
void setItem(Index pos, const ValueT &v) const
Definition: InternalNode.h:145
static void getNodeLog2Dims(std::vector< Index > &dims)
Definition: InternalNode.h:2683
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:1949
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &)
Same as touchLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
void writeTopology(std::ostream &, bool toHalf=false) const
Definition: InternalNode.h:1861
#define OPENVDB_VERSION_NAME
Definition: version.h:45
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:1178
void setOrigin(const Coord &origin)
Set the grid index coordinates of this node&#39;s local origin.
Definition: InternalNode.h:242
ChildIter(const MaskIterT &iter, NodeT *parent)
Definition: InternalNode.h:123
ChildAllCIter beginChildAll() const
Definition: InternalNode.h:207
static const Index NUM_VALUES
Definition: InternalNode.h:70
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don&#39;t change its value.
Definition: InternalNode.h:1435
Base class for iterators over internal and leaf nodes.
Definition: Iterator.h:58
Index64 onTileCount() const
Definition: InternalNode.h:860
bool isInactive() const
Return true if this node has no children and only contains inactive values.
Definition: InternalNode.h:274
ValueAllCIter beginValueAll() const
Definition: InternalNode.h:217
void resetChildNode(Index i, ChildNodeType *child)
Definition: InternalNode.h:2763
void setItem(Index pos, const ChildT &c) const
Definition: InternalNode.h:129
ValueConverter&lt;T&gt;::Type is the type of an InternalNode having the same child hierarchy and dimensions...
Definition: InternalNode.h:78
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
bool isValueMaskOff(Index n) const
Definition: InternalNode.h:658
Index64 offLeafVoxelCount() const
Definition: InternalNode.h:849
ValueIter< const InternalNode, const ValueType, MaskOnIterator, ValueOn > ValueOnCIter
Definition: InternalNode.h:196
ChildAllCIter cbeginChildAll() const
Definition: InternalNode.h:204
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition: Platform.h:96
NodeMaskType::OffIterator MaskOffIterator
Definition: InternalNode.h:108
Base class for dense iterators over internal and leaf nodes.
Definition: Iterator.h:211
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:1594
void voxelizeActiveTiles()
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition: InternalNode.h:2026
ValueOnCIter beginValueOn() const
Definition: InternalNode.h:215
ChildNodeType::ValueType ValueType
Definition: InternalNode.h:62
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.
void modifyItem(Index pos, const ModifyOp &op) const
Definition: InternalNode.h:149
LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as probeLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
Helper class for use with Tree::pruneOp() to replace inactive branches with more memory-efficient ina...
Definition: tree/Util.h:74
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:1394
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition: Math.h:353
bool isConstant(ValueType &constValue, bool &state, const ValueType &tolerance=zeroVal< ValueType >()) const
Definition: InternalNode.h:1279
NodeMaskType::DenseIterator MaskDenseIterator
Definition: InternalNode.h:109
Index64 onLeafVoxelCount() const
Definition: InternalNode.h:837
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:1086
NodeType * probeNodeAndCache(const Coord &xyz, AccessorT &)
Same as probeNode() except, if necessary, update the accessor with pointers to the nodes along the pa...
DenseIter< InternalNode, ChildNodeType, ValueType, ChildAll > ChildAllIter
Definition: InternalNode.h:192
InternalNode< typename ChildNodeType::template ValueConverter< OtherValueType >::Type, Log2Dim > Type
Definition: InternalNode.h:80
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:1941
ValueIter< InternalNode, const ValueType, MaskOnIterator, ValueOn > ValueOnIter
Definition: InternalNode.h:195
ValueOffCIter cbeginValueOff() const
Definition: InternalNode.h:213
Definition: NodeMasks.h:189
Index32 Index
Definition: Types.h:56
OPENVDB_DEPRECATED void evalActiveVoxelBoundingBox(CoordBBox &bbox) const
Definition: InternalNode.h:884
bool isValueOn(const Coord &xyz) const
Return true if the voxel at the given coordinates is active.
Definition: InternalNode.h:1341
Helper class for use with Tree::pruneOp() to replace constant branches (to within the provided tolera...
Definition: tree/Util.h:47
const NodeType * probeConstNode(const Coord &xyz) const
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return NULL.
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:390
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:97
ValueAllCIter cbeginValueAll() const
Definition: InternalNode.h:214
ValueIter< const InternalNode, const ValueType, MaskOffIterator, ValueOff > ValueOffCIter
Definition: InternalNode.h:198
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:1106
bool probeValue(const Coord &xyz, ValueType &value) const
Definition: InternalNode.h:1407
static void doVisit2Node(NodeT &, OtherNodeT &, VisitorOp &)
Definition: InternalNode.h:2575
ValueIter< InternalNode, const ValueType, MaskOffIterator, ValueAll > ValueAllIter
Definition: InternalNode.h:199
bool getItem(Index pos, ChildT *&child, NonConstValueT &value) const
Definition: InternalNode.h:166
void pruneOp(PruneOp &)
Call the PruneOp functor for each child node and, if the functor returns true, prune the node and rep...
Definition: InternalNode.h:911
boost::remove_const< UnsetItemT >::type NonConstValueType
Definition: Iterator.h:217
NodeMaskType mValueMask
Definition: InternalNode.h:691
Index64 offVoxelCount() const
Definition: InternalNode.h:825
void readBuffers(std::istream &, bool fromHalf=false)
Definition: InternalNode.h:2670
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: InternalNode.h:1710
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition: InternalNode.h:871
Coord offsetToGlobalCoord(Index n) const
Return the global coordinates for a linear table offset.
Definition: InternalNode.h:2714
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1487
ValueOffCIter beginValueOff() const
Definition: InternalNode.h:216
DenseIteratorBase< MaskDenseIterator, DenseIter, NodeT, ChildT, ValueT > BaseT
Definition: InternalNode.h:159
const ValueType & result() const
Get the output value.
Definition: Types.h:261
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
NodeMaskType mChildMask
Definition: InternalNode.h:691
bool hasActiveTiles() const
Return true if this node or any of its child nodes have any active tiles.
Definition: InternalNode.h:1328
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:1676
const ValueT & getItem(Index pos) const
Definition: InternalNode.h:142
BaseT::NonConstValueType NonConstValueT
Definition: InternalNode.h:160
CombineArgs & setARef(const ValueType &a)
Redirect the A value to a new external source.
Definition: Types.h:269
ChildNodeType::LeafNodeType LeafNodeType
Definition: InternalNode.h:61
bool isChildMaskOn(Index n) const
Definition: InternalNode.h:660
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:1648
ValueIter< InternalNode, const ValueType, MaskOffIterator, ValueOff > ValueOffIter
Definition: InternalNode.h:197
ChildOffIter beginChildOff()
Definition: InternalNode.h:209
ChildAllIter beginChildAll()
Definition: InternalNode.h:210
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:310
void setValuesOn()
Mark all values (both tiles and voxels) as active.
Definition: InternalNode.h:1636
bool resultIsActive() const
Definition: Types.h:280
Definition: NodeMasks.h:251
ChildIter()
Definition: InternalNode.h:122
_ChildNodeType ChildNodeType
Definition: InternalNode.h:60
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:56
static Index getChildDim()
Definition: InternalNode.h:226
bool isApproxEqual(const Hermite &lhs, const Hermite &rhs)
Definition: Hermite.h:470
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:1246
void pruneInactive()
Reduce the memory footprint of this tree by replacing with background tiles any nodes whose values ar...
Definition: InternalNode.h:946
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition: InternalNode.h:2660
uint64_t Index64
Definition: Types.h:55
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:2728
void combine2(const InternalNode &other0, const InternalNode &other1, CombineOp &)
Definition: InternalNode.h:2372
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Definition: NodeMasks.h:288
UnionType mNodes[NUM_VALUES]
Definition: InternalNode.h:690
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:2041
ChildOnIter beginChildOn()
Definition: InternalNode.h:208
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:1818
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:928
void writeCompressedValues(std::ostream &os, ValueT *srcBuf, Index srcCount, const MaskT &valueMask, const MaskT &childMask, bool toHalf)
Definition: Compression.h:378
void readTopology(std::istream &, bool fromHalf=false)
Definition: InternalNode.h:1885
Definition: InternalNode.h:113
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: InternalNode.h:1733
bool isValueOn(Index offset) const
Return true if the voxel at the given offset is active.
Definition: InternalNode.h:279
Index32 nonLeafCount() const
Definition: InternalNode.h:800
void combine(FloatTreeT &lhsDist, IntTreeT &lhsIndex, FloatTreeT &rhsDist, IntTreeT &rhsIndex)
Definition: MeshToVolume.h:396
Index64 onVoxelCount() const
Definition: InternalNode.h:813
ValueIter()
Definition: InternalNode.h:138
static Index coordToOffset(const Coord &xyz)
Return the linear table offset of the given global or local coordinates.
Definition: InternalNode.h:2704
DenseIter(const MaskDenseIterator &iter, NodeT *parent)
Definition: InternalNode.h:163
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition: InternalNode.h:1420
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:1135
Definition: InternalNode.h:112
ValueOnIter beginValueOn()
Definition: InternalNode.h:218
static Index dim()
Definition: InternalNode.h:223
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:895
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1573
static void doVisit(NodeT &, VisitorOp &)
Definition: InternalNode.h:2532