OpenVDB  2.1.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 = dense.zStride();
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() + zStride*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, a2 += zStride) {
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/ )
bool isValueMaskOn(Index n) const
Definition: InternalNode.h:656
void pruneInactive()
Reduce the memory footprint of this tree by replacing with background tiles any nodes whose values ar...
Definition: InternalNode.h:946
bool isConstant(ValueType &constValue, bool &state, const ValueType &tolerance=zeroVal< ValueType >()) const
Definition: InternalNode.h:1279
ValueIter(const MaskIterT &iter, NodeT *parent)
Definition: InternalNode.h:139
ValueIter< InternalNode, const ValueType, MaskOffIterator, ValueAll > ValueAllIter
Definition: InternalNode.h:199
void unsetItem(Index pos, const ValueT &value) const
Definition: InternalNode.h:180
ValueIter< const InternalNode, const ValueType, MaskOffIterator, ChildOff > ChildOffCIter
Definition: InternalNode.h:191
Index64 onLeafVoxelCount() const
Definition: InternalNode.h:837
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:395
InternalNode()
Definition: InternalNode.h:84
NodeUnion< ValueType, ChildNodeType > UnionType
Definition: InternalNode.h:63
Definition: InternalNode.h:113
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...
DenseIter< InternalNode, ChildNodeType, ValueType, ChildAll > ChildAllIter
Definition: InternalNode.h:192
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
#define OPENVDB_DEPRECATED
Definition: Platform.h:47
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1532
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
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
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.
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
ChildOffIter beginChildOff()
Definition: InternalNode.h:209
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition: InternalNode.h:1420
static void doVisit2Node(NodeT &, OtherNodeT &, VisitorOp &)
Definition: InternalNode.h:2575
Index64 offVoxelCount() const
Definition: InternalNode.h:825
void readBuffers(std::istream &, bool fromHalf=false)
Definition: InternalNode.h:2670
void setValuesOn()
Mark all values (both tiles and voxels) as active.
Definition: InternalNode.h:1636
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1573
static const Index NUM_VALUES
Definition: InternalNode.h:70
ChildOffCIter beginChildOff() const
Definition: InternalNode.h:206
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition: InternalNode.h:871
OPENVDB_DEPRECATED Coord getOrigin() const
Return the grid index coordinates of this node&#39;s local origin.
Definition: InternalNode.h:240
ValueOffCIter beginValueOff() const
Definition: InternalNode.h:216
void negate()
Definition: InternalNode.h:2011
ValueOffIter beginValueOff()
Definition: InternalNode.h:219
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition: InternalNode.h:2660
bool isEmpty() const
Definition: InternalNode.h:266
const Coord & origin() const
Return the grid index coordinates of this node&#39;s local origin.
Definition: InternalNode.h:237
boost::remove_const< UnsetItemT >::type NonConstValueType
Definition: Iterator.h:217
void writeCompressedValues(std::ostream &os, ValueT *srcBuf, Index srcCount, const MaskT &valueMask, const MaskT &childMask, bool toHalf)
Definition: Compression.h:378
Definition: NodeMasks.h:189
ChildT & getItem(Index pos) const
Definition: InternalNode.h:126
UnionType mNodes[NUM_VALUES]
Definition: InternalNode.h:690
Helper class for use with Tree::pruneOp() to replace constant branches (to within the provided tolera...
Definition: tree/Util.h:47
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &)
Same as touchLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
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
Index32 leafCount() const
Definition: InternalNode.h:787
ChildAllCIter cbeginChildAll() const
Definition: InternalNode.h:204
static Index getChildDim()
Definition: InternalNode.h:226
Helper class for use with Tree::pruneOp() to replace inactive branches with more memory-efficient ina...
Definition: tree/Util.h:74
InternalNode< typename ChildNodeType::template ValueConverter< OtherValueType >::Type, Log2Dim > Type
Definition: InternalNode.h:80
static Index coordToOffset(const Coord &xyz)
Return the linear table offset of the given global or local coordinates.
Definition: InternalNode.h:2704
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.
util::NodeMask< Log2Dim > NodeMaskType
Definition: InternalNode.h:64
const ValueType & getValue(const Coord &xyz) const
Definition: InternalNode.h:1362
void setItem(Index pos, ChildT *child) const
Definition: InternalNode.h:174
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Definition: NodeMasks.h:288
ValueIter< InternalNode, const ValueType, MaskOffIterator, ChildOff > ChildOffIter
Definition: InternalNode.h:190
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
Index32 Index
Definition: Types.h:56
void combine(InternalNode &other, CombineOp &)
Definition: InternalNode.h:2285
ChildOnIter beginChildOn()
Definition: InternalNode.h:208
LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as probeLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
void combine(FloatTreeT &lhsDist, IntTreeT &lhsIndex, FloatTreeT &rhsDist, IntTreeT &rhsIndex)
Definition: MeshToVolume.h:396
ValueIter< const InternalNode, const ValueType, MaskOnIterator, ValueOn > ValueOnCIter
Definition: InternalNode.h:196
void visitActiveBBox(BBoxOp &) const
Calls the templated functor BBoxOp with bounding box information for all active tiles and leaf nodes ...
Definition: InternalNode.h:2488
DenseIter< const InternalNode, const ChildNodeType, ValueType, ChildAll > ChildAllCIter
Definition: InternalNode.h:193
ChildIter< const InternalNode, const ChildNodeType, MaskOnIterator, ChildOn > ChildOnCIter
Definition: InternalNode.h:189
Definition: InternalNode.h:112
Definition: Types.h:190
Base class for sparse iterators over internal and leaf nodes.
Definition: Iterator.h:148
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
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
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
ValueOffCIter cbeginValueOff() const
Definition: InternalNode.h:213
void voxelizeActiveTiles()
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition: InternalNode.h:2026
DenseIter()
Definition: InternalNode.h:162
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition: InternalNode.h:1351
void setOrigin(const Coord &origin)
Set the grid index coordinates of this node&#39;s local origin.
Definition: InternalNode.h:242
ChildAllCIter beginChildAll() const
Definition: InternalNode.h:207
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
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:482
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
void makeChildNodeEmpty(Index n, const ValueType &value)
Definition: InternalNode.h:2804
ValueIter< const InternalNode, const ValueType, MaskOffIterator, ValueAll > ValueAllCIter
Definition: InternalNode.h:200
bool isValueMaskOff() const
Definition: InternalNode.h:659
bool isChildMaskOff(Index n) const
Definition: InternalNode.h:661
void setItem(Index pos, const ValueT &v) const
Definition: InternalNode.h:145
ChildIter(const MaskIterT &iter, NodeT *parent)
Definition: InternalNode.h:123
This struct collects both input and output arguments to &quot;grid combiner&quot; functors used with the tree::...
Definition: Types.h:232
Definition: InternalNode.h:113
ChildOffCIter cbeginChildOff() const
Definition: InternalNode.h:203
ChildIter< InternalNode, ChildNodeType, MaskOnIterator, ChildOn > ChildOnIter
Definition: InternalNode.h:188
#define OPENVDB_VERSION_NAME
Definition: version.h:45
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 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
OPENVDB_DEPRECATED void evalActiveVoxelBoundingBox(CoordBBox &bbox) const
Definition: InternalNode.h:884
Definition: InternalNode.h:57
bool probeValue(const Coord &xyz, ValueType &value) const
Definition: InternalNode.h:1407
ChildNodeType::LeafNodeType LeafNodeType
Definition: InternalNode.h:61
ValueAllIter beginValueAll()
Definition: InternalNode.h:220
Base class for iterators over internal and leaf nodes.
Definition: Iterator.h:58
Index64 onTileCount() const
Definition: InternalNode.h:860
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: InternalNode.h:1487
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
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition: Math.h:360
uint32_t Index32
Definition: Types.h:54
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
bool hasActiveTiles() const
Return true if this node or any of its child nodes have any active tiles.
Definition: InternalNode.h:1328
void readCompressedValues(std::istream &is, ValueT *destBuf, Index destCount, const MaskT &valueMask, bool fromHalf)
Definition: Compression.h:276
void setItem(Index pos, const ChildT &c) const
Definition: InternalNode.h:129
uint64_t Index64
Definition: Types.h:55
int32_t Int32
Definition: Types.h:58
void writeTopology(std::ostream &, bool toHalf=false) const
Definition: InternalNode.h:1861
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition: Platform.h:96
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 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
ValueConverter&lt;T&gt;::Type is the type of an InternalNode having the same child hierarchy and dimensions...
Definition: InternalNode.h:78
void readTopology(std::istream &, bool fromHalf=false)
Definition: InternalNode.h:1885
Base class for dense iterators over internal and leaf nodes.
Definition: Iterator.h:211
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: InternalNode.h:1733
CombineArgs & setARef(const ValueType &a)
Redirect the A value to a new external source.
Definition: Types.h:269
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
ValueOnCIter cbeginValueOn() const
Definition: InternalNode.h:212
NodeMaskType::OffIterator MaskOffIterator
Definition: InternalNode.h:108
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
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
virtual ~InternalNode()
Definition: InternalNode.h:774
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:367
void modifyItem(Index pos, const ModifyOp &op) const
Definition: InternalNode.h:149
static Index dim()
Definition: InternalNode.h:223
void combine2(const InternalNode &other0, const InternalNode &other1, CombineOp &)
Definition: InternalNode.h:2372
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
void setOn(Index32 n)
Set the nth bit on.
Definition: NodeMasks.h:390
bool isValueMaskOn() const
Definition: InternalNode.h:657
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
ValueAllCIter beginValueAll() const
Definition: InternalNode.h:217
void resetChildNode(Index i, ChildNodeType *child)
Definition: InternalNode.h:2763
bool isChildMaskOff() const
Definition: InternalNode.h:662
ChildNodeType * unsetChildNode(Index i, const ValueType &value)
Definition: InternalNode.h:2789
static void doVisit2(NodeT &, OtherChildAllIterT &, VisitorOp &, bool otherIsLHS)
Definition: InternalNode.h:2635
static void getNodeLog2Dims(std::vector< Index > &dims)
Definition: InternalNode.h:2683
bool isValueMaskOff(Index n) const
Definition: InternalNode.h:658
bool isValueOn(const Coord &xyz) const
Return true if the voxel at the given coordinates is active.
Definition: InternalNode.h:1341
static Index getLevel()
Definition: InternalNode.h:224
Definition: Types.h:307
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
ValueIter< InternalNode, const ValueType, MaskOffIterator, ValueOff > ValueOffIter
Definition: InternalNode.h:197
ValueIter< InternalNode, const ValueType, MaskOnIterator, ValueOn > ValueOnIter
Definition: InternalNode.h:195
const ValueType & result() const
Get the output value.
Definition: Types.h:261
ValueOnCIter beginValueOn() const
Definition: InternalNode.h:215
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:97
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: InternalNode.h:1710
Coord offsetToGlobalCoord(Index n) const
Return the global coordinates for a linear table offset.
Definition: InternalNode.h:2714
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.
bool getItem(Index pos, ChildT *&child, NonConstValueT &value) const
Definition: InternalNode.h:166
ChildNodeType * getChildNode(Index n)
Definition: InternalNode.h:2811
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
const LeafNodeType * probeConstLeafAndCache(const Coord &xyz, AccessorT &acc) const
Same as probeLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
bool isApproxEqual(const Hermite &lhs, const Hermite &rhs)
Definition: Hermite.h:470
DenseIteratorBase< MaskDenseIterator, DenseIter, NodeT, ChildT, ValueT > BaseT
Definition: InternalNode.h:159
bool isInactive() const
Return true if this node has no children and only contains inactive values.
Definition: InternalNode.h:274
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
ChildOnCIter cbeginChildOn() const
Definition: InternalNode.h:202
NodeMaskType::OnIterator MaskOnIterator
Definition: InternalNode.h:107
NodeType * probeNodeAndCache(const Coord &xyz, AccessorT &)
Same as probeNode() except, if necessary, update the accessor with pointers to the nodes along the pa...
Index pos() const
Identical to offset.
Definition: Iterator.h:94
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
Definition: Types.h:346
ChildOnCIter beginChildOn() const
Definition: InternalNode.h:205
bool isNegative(const Type &x)
Return true if x is less than zero.
Definition: Math.h:313
const ValueT & getItem(Index pos) const
Definition: InternalNode.h:142
BaseT::NonConstValueType NonConstValueT
Definition: InternalNode.h:160
Definition: NodeMasks.h:220
bool resultIsActive() const
Definition: Types.h:280
Definition: NodeMasks.h:251
ValueAllCIter cbeginValueAll() const
Definition: InternalNode.h:214
ValueOnIter beginValueOn()
Definition: InternalNode.h:218
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:67
bool isChildMaskOn(Index n) const
Definition: InternalNode.h:660
ChildNodeType::ValueType ValueType
Definition: InternalNode.h:62
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 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
ChildAllIter beginChildAll()
Definition: InternalNode.h:210
static void doVisit(NodeT &, VisitorOp &)
Definition: InternalNode.h:2532
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
void visit2(IterT &otherIter, VisitorOp &, bool otherIsLHS=false)
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:107
NodeMaskType mValueMask
Definition: InternalNode.h:691
void topologyUnion(const InternalNode< OtherChildNodeType, Log2Dim > &other)
Union this branch&#39;s set of active values with the other branch&#39;s active values. The value type of the...
void merge(InternalNode &other, const ValueType &background, const ValueType &otherBackground)
Efficiently merge another tree into this tree using one of several schemes.
Definition: InternalNode.h:2041
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition: InternalNode.h:1613
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
void visit2Node(OtherNodeType &other, VisitorOp &)
Definition: InternalNode.h:2550
NodeMaskType mChildMask
Definition: InternalNode.h:691
NodeMaskType::DenseIterator MaskDenseIterator
Definition: InternalNode.h:109
Index64 offLeafVoxelCount() const
Definition: InternalNode.h:849
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
Index64 onVoxelCount() const
Definition: InternalNode.h:813
ChildIter()
Definition: InternalNode.h:122
OPENVDB_IMPORT uint32_t getFormatVersion(std::istream &)
Return the file format version number associated with the given input stream.
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()
Definition: InternalNode.h:138
Coord mOrigin
Global grid index coordinates (x,y,z) of the local origin of this node.
Definition: InternalNode.h:693
DenseIter(const MaskDenseIterator &iter, NodeT *parent)
Definition: InternalNode.h:163
_ChildNodeType ChildNodeType
Definition: InternalNode.h:60
Definition: InternalNode.h:112
ValueIter< const InternalNode, const ValueType, MaskOffIterator, ValueOff > ValueOffCIter
Definition: InternalNode.h:198
void setChildNode(Index i, ChildNodeType *child)
Definition: InternalNode.h:2777
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