OpenVDB  1.2.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() and setItem() methods for active values and/or inactive values.
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().setChildNode(pos, &c); }
130  };// ChildIter
131 
132  template<typename NodeT, typename ValueT, typename MaskIterT, typename TagT>
134  MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>
135  {
137  ValueIter(const MaskIterT& iter, NodeT* parent): SparseIteratorBase<
138  MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>(iter, parent) {}
139 
140  const ValueT& getItem(Index pos) const { return this->parent().mNodes[pos].getValue(); }
141 
142  // Note: setItem() can't be called on const iterators.
143  void setItem(Index pos, const ValueT& v) const { this->parent().mNodes[pos].setValue(v); }
144  };// ValueIter
145 
146  template<typename NodeT, typename ChildT, typename ValueT, typename TagT>
147  struct DenseIter: public DenseIteratorBase<
148  MaskDenseIterator, DenseIter<NodeT, ChildT, ValueT, TagT>, NodeT, ChildT, ValueT>
149  {
152 
154  DenseIter(const MaskDenseIterator& iter, NodeT* parent):
155  DenseIteratorBase<MaskDenseIterator, DenseIter, NodeT, ChildT, ValueT>(iter, parent) {}
156 
157  bool getItem(Index pos, ChildT*& child, NonConstValueT& value) const
158  {
159  child = this->parent().getChildNode(pos);
160  if (!child) value = this->parent().mNodes[pos].getValue();
161  return (child != NULL);
162  }
163 
164  // Note: setItem() can't be called on const iterators.
165  void setItem(Index pos, ChildT* child) const
166  {
167  this->parent().setChildNode(pos, child);
168  }
169 
170  // Note: unsetItem() can't be called on const iterators.
171  void unsetItem(Index pos, const ValueT& value) const
172  {
173  this->parent().unsetChildNode(pos, value);
174  }
175  };// DenseIter
176 
177 public:
178  // Iterators (see Iterator.h for usage)
185 
192 
193  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(mChildMask.beginOn(), this); }
194  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(mChildMask.beginOff(), this); }
195  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(mChildMask.beginDense(), this); }
196  ChildOnCIter beginChildOn() const { return cbeginChildOn(); }
197  ChildOffCIter beginChildOff() const { return cbeginChildOff(); }
198  ChildAllCIter beginChildAll() const { return cbeginChildAll(); }
199  ChildOnIter beginChildOn() { return ChildOnIter(mChildMask.beginOn(), this); }
200  ChildOffIter beginChildOff() { return ChildOffIter(mChildMask.beginOff(), this); }
201  ChildAllIter beginChildAll() { return ChildAllIter(mChildMask.beginDense(), this); }
202 
203  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(mValueMask.beginOn(), this); }
204  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(mValueMask.beginOff(), this); }
205  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(mChildMask.beginOff(), this); }
206  ValueOnCIter beginValueOn() const { return cbeginValueOn(); }
207  ValueOffCIter beginValueOff() const { return cbeginValueOff(); }
208  ValueAllCIter beginValueAll() const { return cbeginValueAll(); }
209  ValueOnIter beginValueOn() { return ValueOnIter(mValueMask.beginOn(), this); }
210  ValueOffIter beginValueOff() { return ValueOffIter(mValueMask.beginOff(), this); }
211  ValueAllIter beginValueAll() { return ValueAllIter(mChildMask.beginOff(), this); }
212 
213 
214  static Index dim() { return DIM; }
215  static Index getLevel() { return LEVEL; }
216  static void getNodeLog2Dims(std::vector<Index>& dims);
217  static Index getChildDim() { return ChildNodeType::DIM; }
218 
219  static Index coord2offset(const Coord& xyz);
220  static void offset2coord(Index n, Coord& xyz);
221  Coord offset2globalCoord(Index n) const;
222 
223  Coord getOrigin() const { return mOrigin; }
224 
225  Index32 leafCount() const;
226  Index32 nonLeafCount() const;
227  Index64 onVoxelCount() const;
228  Index64 offVoxelCount() const;
229  Index64 onLeafVoxelCount() const;
230  Index64 offLeafVoxelCount() const;
231 
233  Index64 memUsage() const;
234 
237  void evalActiveVoxelBoundingBox(CoordBBox& bbox) const;
238 
241  CoordBBox getNodeBoundingBox() const { return CoordBBox::createCube(mOrigin, DIM); }
242 
243  bool isEmpty() const { return mChildMask.isOff(); }
244 
248  bool isConstant(ValueType& constValue, bool& state,
249  const ValueType& tolerance = zeroVal<ValueType>()) const;
251  bool isInactive() const { return this->isChildMaskOff() && this->isValueMaskOff(); }
252 
254  bool isValueOn(const Coord& xyz) const;
256  bool isValueOn(Index offset) const { return mValueMask.isOn(offset); }
257 
259  bool hasActiveTiles() const;
260 
261  const ValueType& getValue(const Coord& xyz) const;
262  bool probeValue(const Coord& xyz, ValueType& value) const;
263 
266  Index getValueLevel(const Coord& xyz) const;
267 
270  const ValueType& getFirstValue() const;
273  const ValueType& getLastValue() const;
274 
276  void setActiveState(const Coord& xyz, bool on);
277 
279  void setValueOff(const Coord& xyz);
281  void setValueOff(const Coord& xyz, const ValueType& value);
282 
283  void setValueOn(const Coord& xyz);
284  void setValueOn(const Coord& xyz, const ValueType& value);
285  void setValueOnly(const Coord& xyz, const ValueType& value);
286  void setValueOnMin(const Coord& xyz, const ValueType& value);
287  void setValueOnMax(const Coord& xyz, const ValueType& value);
288  void setValueOnSum(const Coord& xyz, const ValueType& value);
289 
292  void fill(const CoordBBox& bbox, const ValueType&, bool active = true);
293 
303  template<typename DenseT>
304  void copyToDense(const CoordBBox& bbox, DenseT& dense) const;
305 
310  template<typename AccessorT>
311  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
312 
317  template<typename AccessorT>
318  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
319 
324  template<typename AccessorT>
325  void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
326 
331  template<typename AccessorT>
332  void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
333 
339  template<typename AccessorT>
340  void setValueOnSumAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
341 
346  template<typename AccessorT>
347  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
348 
353  template<typename AccessorT>
354  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
355 
360  template<typename AccessorT>
361  bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
362 
369  template<typename AccessorT>
370  Index getValueLevelAndCache(const Coord& xyz, AccessorT&) const;
371 
373  void setValuesOn();
374 
375  //
376  // I/O
377  //
378  void writeTopology(std::ostream&, bool toHalf = false) const;
379  void readTopology(std::istream&, bool fromHalf = false);
380  void writeBuffers(std::ostream&, bool toHalf = false) const;
381  void readBuffers(std::istream&, bool fromHalf = false);
382 
393  void signedFloodFill(const ValueType& background);
394 
401  void signedFloodFill(const ValueType& outside, const ValueType& inside);
402 
405  void negate();
406 
408  void voxelizeActiveTiles();
409 
414  void merge(InternalNode& other, const ValueType& background, const ValueType& otherBackground);
415 
428  template<typename OtherChildNodeType>
429  void topologyUnion(const InternalNode<OtherChildNodeType, Log2Dim>& other);
430 
431  template<typename CombineOp>
432  void combine(InternalNode& other, CombineOp&);
433  template<typename CombineOp>
434  void combine(const ValueType& value, bool valueIsActive, CombineOp&);
435 
436  template<typename CombineOp>
437  void combine2(const InternalNode& other0, const InternalNode& other1, CombineOp&);
438  template<typename CombineOp>
439  void combine2(const ValueType& value, const InternalNode& other,
440  bool valueIsActive, CombineOp&);
441  template<typename CombineOp>
442  void combine2(const InternalNode& other, const ValueType& value,
443  bool valueIsActive, CombineOp&);
444 
450  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
451 
452  template<typename VisitorOp> void visit(VisitorOp&);
453  template<typename VisitorOp> void visit(VisitorOp&) const;
454 
455  template<typename OtherNodeType, typename VisitorOp>
456  void visit2Node(OtherNodeType& other, VisitorOp&);
457  template<typename OtherNodeType, typename VisitorOp>
458  void visit2Node(OtherNodeType& other, VisitorOp&) const;
459  template<typename IterT, typename VisitorOp>
460  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false);
461  template<typename IterT, typename VisitorOp>
462  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false) const;
463 
470  template<typename PruneOp> void pruneOp(PruneOp&);
471 
475  void prune(const ValueType& tolerance = zeroVal<ValueType>());
476 
479  void pruneInactive(const ValueType&);
480 
483  void pruneInactive();
484 
487  void addLeaf(LeafNodeType* leaf);
488 
491  template<typename AccessorT>
492  void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
493 
502  template<typename NodeT>
503  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
504 
507  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
508 
511  template<typename AccessorT>
512  void addTileAndCache(Index level, const Coord& xyz, const ValueType& value,
513  bool state, AccessorT&);
514 
517  template <typename NodeType>
518  NodeType* probeNode(const Coord& xyz);
519  template <typename NodeType>
520  const NodeType* probeConstNode(const Coord& xyz) const;
521  template<typename NodeType, typename AccessorT>
522  NodeType* probeNodeAndCache(const Coord& xyz, AccessorT&);
523  template<typename NodeType, typename AccessorT>
524  const NodeType* probeConstNodeAndCache(const Coord& xyz, AccessorT&) const;
525 
529  {
530  return this->template probeNode<LeafNodeType>(xyz);
531  }
532 
535  const LeafNodeType* probeConstLeaf(const Coord& xyz) const
536  {
537  return this->template probeConstNode<LeafNodeType>(xyz);
538  }
539  const LeafNodeType* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
540 
543  template<typename AccessorT>
544  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc)
545  {
546  return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
547  }
548 
551  template<typename AccessorT>
552  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
553  {
554  return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
555  }
557  template<typename AccessorT>
558  const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const
559  {
560  return this->probeConstLeafAndCache(xyz, acc);
561  }
562 
569  LeafNodeType* touchLeaf(const Coord& xyz);
570 
573  template<typename AccessorT>
574  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT&);
575 
578  void resetBackground(const ValueType& oldBackground, const ValueType& newBackground);
579 
582  template<typename OtherChildNodeType, Index OtherLog2Dim>
583  bool hasSameTopology(const InternalNode<OtherChildNodeType, OtherLog2Dim>* other) const;
584 
586  template<typename NodeT>
587  static bool hasNodeType();
588 
589 protected:
597 
600  template<typename, Index> friend class InternalNode;
601 
602  // Mask accessors
603 public:
604  bool isValueMaskOn(Index n) const { return mValueMask.isOn(n); }
605  bool isValueMaskOn() const { return mValueMask.isOn(); }
606  bool isValueMaskOff(Index n) const { return mValueMask.isOff(n); }
607  bool isValueMaskOff() const { return mValueMask.isOff(); }
608  bool isChildMaskOn(Index n) const { return mChildMask.isOn(n); }
609  bool isChildMaskOff(Index n) const { return mChildMask.isOff(n); }
610  bool isChildMaskOff() const { return mChildMask.isOff(); }
611 protected:
613  void setValueMask(Index n, bool on) { mValueMask.set(n, mChildMask.isOn(n) ? false : on); }
617 
618  void makeChildNodeEmpty(Index n, const ValueType& value);
619  void setChildNode(Index i, ChildNodeType* child);
620  ChildNodeType* unsetChildNode(Index i, const ValueType& value);
621 
622  template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
623  static inline void doVisit(NodeT&, VisitorOp&);
624 
625  template<typename NodeT, typename OtherNodeT, typename VisitorOp,
626  typename ChildAllIterT, typename OtherChildAllIterT>
627  static inline void doVisit2Node(NodeT&, OtherNodeT&, VisitorOp&);
628 
629  template<typename NodeT, typename VisitorOp,
630  typename ChildAllIterT, typename OtherChildAllIterT>
631  static inline void doVisit2(NodeT&, OtherChildAllIterT&, VisitorOp&, bool otherIsLHS);
632 
633  ChildNodeType* getChildNode(Index n);
634  const ChildNodeType* getChildNode(Index n) const;
635 
636 
637  UnionType mNodes[NUM_VALUES];
641 }; // class InternalNode
642 
643 
645 
646 
647 template<typename ChildT, Index Log2Dim>
648 inline
650 {
651  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
652 }
653 
654 
655 template<typename ChildT, Index Log2Dim>
656 inline
657 InternalNode<ChildT, Log2Dim>::InternalNode(const Coord& origin, const ValueType& val, bool active):
658  mOrigin(origin[0] & ~(DIM - 1), // zero out the low-order bits
659  origin[1] & ~(DIM - 1),
660  origin[2] & ~(DIM - 1))
661 {
662  if (active) mValueMask.setOn();
663  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
664 }
665 
666 
667 template<typename ChildT, Index Log2Dim>
668 inline
670  mChildMask(other.mChildMask),
671  mValueMask(other.mValueMask),
672  mOrigin(other.mOrigin)
673 {
674  for (Index i = 0; i < NUM_VALUES; ++i) {
675  if (isChildMaskOn(i)) {
676  mNodes[i].setChild(new ChildNodeType(*(other.mNodes[i].getChild())));
677  } else {
678  mNodes[i].setValue(other.mNodes[i].getValue());
679  }
680  }
681 }
682 
683 template<typename ChildT, Index Log2Dim>
684 template<typename OtherChildNodeType>
685 inline
687  const ValueType& offValue, const ValueType& onValue, TopologyCopy):
688  mChildMask(other.mChildMask),
689  mValueMask(other.mValueMask),
690  mOrigin(other.mOrigin)
691 {
692  for (Index i = 0; i < NUM_VALUES; ++i) {
693  if (isChildMaskOn(i)) {
694  mNodes[i].setChild(new ChildNodeType(*(other.mNodes[i].getChild()),
695  offValue, onValue, TopologyCopy()));
696  } else {
697  mNodes[i].setValue(isValueMaskOn(i) ? onValue : offValue);
698  }
699  }
700 }
701 
702 template<typename ChildT, Index Log2Dim>
703 template<typename OtherChildNodeType>
704 inline
706  const ValueType& background, TopologyCopy):
707  mChildMask(other.mChildMask),
708  mValueMask(other.mValueMask),
709  mOrigin(other.mOrigin)
710 {
711  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
712  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
713  mNodes[iter.pos()].setChild(new ChildNodeType(*(other.mNodes[iter.pos()].getChild()),
714  background, TopologyCopy()));
715  }
716 }
717 
718 
719 template<typename ChildT, Index Log2Dim>
720 inline
722 {
723  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
724  delete mNodes[iter.pos()].getChild();
725  }
726 }
727 
728 
730 
731 
732 template<typename ChildT, Index Log2Dim>
733 inline Index32
735 {
736  if (ChildNodeType::getLevel() == 0) return mChildMask.countOn();
737  Index32 sum = 0;
738  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
739  sum += iter->leafCount();
740  }
741  return sum;
742 }
743 
744 
745 template<typename ChildT, Index Log2Dim>
746 inline Index32
748 {
749  Index32 sum = 1;
750  if (ChildNodeType::getLevel() == 0) return sum;
751  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
752  sum += iter->nonLeafCount();
753  }
754  return sum;
755 }
756 
757 
758 template<typename ChildT, Index Log2Dim>
759 inline Index64
761 {
762  Index64 sum = 0;
763  for (Index i = 0; i < NUM_VALUES; ++i) {
764  if (isChildMaskOff(i)) {
765  if (isValueMaskOn(i)) sum += ChildT::NUM_VOXELS;
766  } else {
767  sum += mNodes[i].getChild()->onVoxelCount();
768  }
769  }
770  return sum;
771 }
772 
773 
774 template<typename ChildT, Index Log2Dim>
775 inline Index64
777 {
778  Index64 sum = 0;
779  for (Index i = 0; i < NUM_VALUES; ++i) {
780  if (isChildMaskOff(i)) {
781  if (isValueMaskOff(i)) sum += ChildT::NUM_VOXELS;
782  } else {
783  sum += mNodes[i].getChild()->offVoxelCount();
784  }
785  }
786  return sum;
787 }
788 
789 
790 template<typename ChildT, Index Log2Dim>
791 inline Index64
793 {
794  Index64 sum = 0;
795  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
796  sum += mNodes[iter.pos()].getChild()->onLeafVoxelCount();
797  }
798  return sum;
799 }
800 
801 
802 template<typename ChildT, Index Log2Dim>
803 inline Index64
805 {
806  Index64 sum = 0;
807  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
808  sum += mNodes[iter.pos()].getChild()->offLeafVoxelCount();
809  }
810  return sum;
811 }
812 
813 
814 template<typename ChildT, Index Log2Dim>
815 inline Index64
817 {
818  Index64 sum = NUM_VALUES * sizeof(UnionType) + mChildMask.memUsage()
819  + mValueMask.memUsage() + sizeof(mOrigin);
820  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
821  sum += iter->memUsage();
822  }
823  return sum;
824 }
825 
826 
827 template<typename ChildT, Index Log2Dim>
828 inline void
830 {
831  if (bbox.isInside(this->getNodeBoundingBox())) return;
832 
833  ValueType dummy;
834  for (ChildAllCIter iter = this->cbeginChildAll(); iter; ++iter) {
835  if (const ChildT* child = iter.probeChild(dummy)) {
836  child->evalActiveVoxelBoundingBox(bbox);
837  } else if (iter.isValueOn()) {
838  bbox.expand(iter.getCoord(), ChildT::DIM);
839  }
840  }
841 }
842 
843 
845 
846 
847 template<typename ChildT, Index Log2Dim>
848 template<typename PruneOp>
849 inline void
851 {
852  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
853  const Index i = iter.pos();
854  ChildT* child = mNodes[i].getChild();
855  if (!op(*child)) continue;
856  delete child;
857  mChildMask.setOff(i);
858  mValueMask.set(i, op.state);
859  mNodes[i].setValue(op.value);
860  }
861 
862 }
863 
864 
865 template<typename ChildT, Index Log2Dim>
866 inline void
868 {
869  TolerancePrune<ValueType> op(tolerance);
870  this->pruneOp(op);
871 }
872 
873 
874 template<typename ChildT, Index Log2Dim>
875 inline void
877 {
879  this->pruneOp(op);
880 }
881 
882 
883 template<typename ChildT, Index Log2Dim>
884 inline void
886 {
887  this->pruneInactive(this->getBackground());
888 }
889 
890 
892 
893 template<typename ChildT, Index Log2Dim>
894 template<typename NodeT>
895 inline NodeT*
896 InternalNode<ChildT, Log2Dim>::stealNode(const Coord& xyz, const ValueType& value, bool state)
897 {
898  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
899  NodeT::LEVEL > ChildT::LEVEL) return NULL;
901  const Index n = this->coord2offset(xyz);
902  if (mChildMask.isOff(n)) return NULL;
903  ChildT* child = mNodes[n].getChild();
904  if (boost::is_same<NodeT, ChildT>::value) {
905  mChildMask.setOff(n);
906  mValueMask.set(n, state);
907  mNodes[n].setValue(value);
908  }
909  return (boost::is_same<NodeT, ChildT>::value)
910  ? reinterpret_cast<NodeT*>(child)
911  : child->template stealNode<NodeT>(xyz, value, state);
913 }
914 
916 
917 template<typename ChildT, Index Log2Dim>
918 template<typename NodeT>
919 inline NodeT*
921 {
922  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
923  NodeT::LEVEL > ChildT::LEVEL) return NULL;
925  const Index n = this->coord2offset(xyz);
926  if (mChildMask.isOff(n)) return NULL;
927  ChildT* child = mNodes[n].getChild();
928  return (boost::is_same<NodeT, ChildT>::value)
929  ? reinterpret_cast<NodeT*>(child)
930  : child->template probeNode<NodeT>(xyz);
932 }
933 
934 template<typename ChildT, Index Log2Dim>
935 template<typename NodeT, typename AccessorT>
936 inline NodeT*
938 {
939  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
940  NodeT::LEVEL > ChildT::LEVEL) return NULL;
942  const Index n = this->coord2offset(xyz);
943  if (mChildMask.isOff(n)) return NULL;
944  ChildT* child = mNodes[n].getChild();
945  acc.insert(xyz, child);
946  return (boost::is_same<NodeT, ChildT>::value)
947  ? reinterpret_cast<NodeT*>(child)
948  : child->template probeNodeAndCache<NodeT>(xyz, acc);
950 }
951 
952 template<typename ChildT, Index Log2Dim>
953 template<typename NodeT>
954 inline const NodeT*
956 {
957  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
958  NodeT::LEVEL > ChildT::LEVEL) return NULL;
960  const Index n = this->coord2offset(xyz);
961  if (mChildMask.isOff(n)) return NULL;
962  const ChildT* child = mNodes[n].getChild();
963  return (boost::is_same<NodeT, ChildT>::value)
964  ? reinterpret_cast<const NodeT*>(child)
965  : child->template probeConstNode<NodeT>(xyz);
967 }
968 
969 template<typename ChildT, Index Log2Dim>
970 template<typename NodeT, typename AccessorT>
971 inline const NodeT*
973 {
974  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
975  NodeT::LEVEL > ChildT::LEVEL) return NULL;
977  const Index n = this->coord2offset(xyz);
978  if (mChildMask.isOff(n)) return NULL;
979  const ChildT* child = mNodes[n].getChild();
980  acc.insert(xyz, child);
981  return (boost::is_same<NodeT, ChildT>::value)
982  ? reinterpret_cast<const NodeT*>(child)
983  : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
985 }
986 
988 
989 
990 template<typename ChildT, Index Log2Dim>
991 template<typename NodeT>
992 inline bool
994 {
995  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
996  NodeT::LEVEL > ChildT::LEVEL) return false;
998  return ChildT::template hasNodeType<NodeT>();
1000 }
1001 
1003 
1004 template<typename ChildT, Index Log2Dim>
1005 inline void
1007 {
1008  assert(leaf != NULL);
1009  const Coord& xyz = leaf->origin();
1010  const Index n = this->coord2offset(xyz);
1011  ChildT* child = NULL;
1012  if (mChildMask.isOff(n)) {
1013  if (ChildT::LEVEL>0) {
1014  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1015  } else {
1016  child = reinterpret_cast<ChildT*>(leaf);
1017  }
1018  mNodes[n].setChild(child);
1019  mChildMask.setOn(n);
1020  mValueMask.setOff(n);
1021  } else {
1022  if (ChildT::LEVEL>0) {
1023  child = mNodes[n].getChild();
1024  } else {
1025  delete mNodes[n].getChild();
1026  child = reinterpret_cast<ChildT*>(leaf);
1027  mNodes[n].setChild(child);
1028  }
1029  }
1030  child->addLeaf(leaf);
1031 }
1032 
1033 
1034 template<typename ChildT, Index Log2Dim>
1035 template<typename AccessorT>
1036 inline void
1038 {
1039  assert(leaf != NULL);
1040  const Coord& xyz = leaf->origin();
1041  const Index n = this->coord2offset(xyz);
1042  ChildT* child = NULL;
1043  if (mChildMask.isOff(n)) {
1044  if (ChildT::LEVEL>0) {
1045  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1046  acc.insert(xyz, child);//we only cache internal nodes
1047  } else {
1048  child = reinterpret_cast<ChildT*>(leaf);
1049  }
1050  mNodes[n].setChild(child);
1051  mChildMask.setOn(n);
1052  mValueMask.setOff(n);
1053  } else {
1054  if (ChildT::LEVEL>0) {
1055  child = mNodes[n].getChild();
1056  acc.insert(xyz, child);//we only cache internal nodes
1057  } else {
1058  delete mNodes[n].getChild();
1059  child = reinterpret_cast<ChildT*>(leaf);
1060  mNodes[n].setChild(child);
1061  }
1062  }
1063  child->addLeafAndCache(leaf, acc);
1064 }
1065 
1066 
1068 
1069 
1070 template<typename ChildT, Index Log2Dim>
1071 inline void
1073  const ValueType& value, bool state)
1074 {
1075  assert(level > 0);
1076  if (LEVEL >= level) {
1077  const Index n = this->coord2offset(xyz);
1078  if (mChildMask.isOff(n)) {// tile case
1079  if (LEVEL > level) {
1080  ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1081  mNodes[n].setChild(child);
1082  mChildMask.setOn(n);
1083  mValueMask.setOff(n);
1084  child->addTile(level, xyz, value, state);
1085  } else {
1086  mValueMask.set(n, state);
1087  mNodes[n].setValue(value);
1088  }
1089  } else {// child branch case
1090  ChildT* child = mNodes[n].getChild();
1091  if (LEVEL > level) {
1092  child->addTile(level, xyz, value, state);
1093  } else {
1094  delete child;
1095  mChildMask.setOff(n);
1096  mValueMask.set(n, state);
1097  mNodes[n].setValue(value);
1098  }
1099  }
1100  }
1101 }
1102 
1103 
1104 template<typename ChildT, Index Log2Dim>
1105 template<typename AccessorT>
1106 inline void
1108  const ValueType& value, bool state, AccessorT& acc)
1109 {
1110  assert(level > 0);
1111  if (LEVEL >= level) {
1112  const Index n = this->coord2offset(xyz);
1113  if (mChildMask.isOff(n)) {// tile case
1114  if (LEVEL > level) {
1115  ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1116  mNodes[n].setChild(child);
1117  mChildMask.setOn(n);
1118  mValueMask.setOff(n);
1119  acc.insert(xyz, child);
1120  child->addTileAndCache(level, xyz, value, state, acc);
1121  } else {
1122  mValueMask.set(n, state);
1123  mNodes[n].setValue(value);
1124  }
1125  } else {// child branch case
1126  ChildT* child = mNodes[n].getChild();
1127  if (LEVEL > level) {
1128  acc.insert(xyz, child);
1129  child->addTileAndCache(level, xyz, value, state, acc);
1130  } else {
1131  delete child;
1132  mChildMask.setOff(n);
1133  mValueMask.set(n, state);
1134  mNodes[n].setValue(value);
1135  }
1136  }
1137  }
1138 }
1139 
1140 
1142 
1143 
1144 template<typename ChildT, Index Log2Dim>
1145 inline typename ChildT::LeafNodeType*
1147 {
1148  const Index n = this->coord2offset(xyz);
1149  ChildT* child = NULL;
1150  if (mChildMask.isOff(n)) {
1151  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1152  mNodes[n].setChild(child);
1153  mChildMask.setOn(n);
1154  mValueMask.setOff(n);
1155  } else {
1156  child = mNodes[n].getChild();
1157  }
1158  return child->touchLeaf(xyz);
1159 }
1160 
1161 
1162 template<typename ChildT, Index Log2Dim>
1163 template<typename AccessorT>
1164 inline typename ChildT::LeafNodeType*
1166 {
1167  const Index n = this->coord2offset(xyz);
1168  if (mChildMask.isOff(n)) {
1169  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), mValueMask.isOn(n)));
1170  mChildMask.setOn(n);
1171  mValueMask.setOff(n);
1172  }
1173  acc.insert(xyz, mNodes[n].getChild());
1174  return mNodes[n].getChild()->touchLeafAndCache(xyz, acc);
1175 }
1176 
1177 
1179 
1180 
1181 template<typename ChildT, Index Log2Dim>
1182 inline bool
1184  const ValueType& tolerance) const
1185 {
1186  bool allEqual = true, firstValue = true, valueState = true;
1187  ValueType value = zeroVal<ValueType>();
1188  for (Index i = 0; allEqual && i < NUM_VALUES; ++i) {
1189  if (this->isChildMaskOff(i)) {
1190  // If entry i is a value, check if it is within tolerance
1191  // and whether its active state matches the other entries.
1192  if (firstValue) {
1193  firstValue = false;
1194  valueState = isValueMaskOn(i);
1195  value = mNodes[i].getValue();
1196  } else {
1197  allEqual = (isValueMaskOn(i) == valueState)
1198  && math::isApproxEqual(mNodes[i].getValue(), value, tolerance);
1199  }
1200  } else {
1201  // If entry i is a child, check if the child is constant and within tolerance
1202  // and whether its active state matches the other entries.
1203  ValueType childValue = zeroVal<ValueType>();
1204  bool isChildOn = false;
1205  if (mNodes[i].getChild()->isConstant(childValue, isChildOn, tolerance)) {
1206  if (firstValue) {
1207  firstValue = false;
1208  valueState = isChildOn;
1209  value = childValue;
1210  } else {
1211  allEqual = (isChildOn == valueState)
1212  && math::isApproxEqual(childValue, value, tolerance);
1213  }
1214  } else { // child is not constant
1215  allEqual = false;
1216  }
1217  }
1218  }
1219  if (allEqual) {
1220  constValue = value;
1221  state = valueState;
1222  }
1223  return allEqual;
1224 }
1225 
1226 
1228 
1229 
1230 template<typename ChildT, Index Log2Dim>
1231 inline bool
1233 {
1234  const bool anyActiveTiles = !mValueMask.isOff();
1235  if (LEVEL==1 || anyActiveTiles) return anyActiveTiles;
1236  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1237  if (iter->hasActiveTiles()) return true;
1238  }
1239  return false;
1240 }
1241 
1242 
1243 template<typename ChildT, Index Log2Dim>
1244 inline bool
1246 {
1247  const Index n = this->coord2offset(xyz);
1248  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1249  return mNodes[n].getChild()->isValueOn(xyz);
1250 }
1251 
1252 template<typename ChildT, Index Log2Dim>
1253 template<typename AccessorT>
1254 inline bool
1256 {
1257  const Index n = this->coord2offset(xyz);
1258  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1259  acc.insert(xyz, mNodes[n].getChild());
1260  return mNodes[n].getChild()->isValueOnAndCache(xyz, acc);
1261 }
1262 
1263 
1264 template<typename ChildT, Index Log2Dim>
1265 inline const typename ChildT::ValueType&
1267 {
1268  const Index n = this->coord2offset(xyz);
1269  return this->isChildMaskOff(n) ? mNodes[n].getValue()
1270  : mNodes[n].getChild()->getValue(xyz);
1271 }
1272 
1273 template<typename ChildT, Index Log2Dim>
1274 template<typename AccessorT>
1275 inline const typename ChildT::ValueType&
1277 {
1278  const Index n = this->coord2offset(xyz);
1279  if (this->isChildMaskOn(n)) {
1280  acc.insert(xyz, mNodes[n].getChild());
1281  return mNodes[n].getChild()->getValueAndCache(xyz, acc);
1282  }
1283  return mNodes[n].getValue();
1284 }
1285 
1286 
1287 template<typename ChildT, Index Log2Dim>
1288 inline Index
1290 {
1291  const Index n = this->coord2offset(xyz);
1292  return this->isChildMaskOff(n) ? LEVEL : mNodes[n].getChild()->getValueLevel(xyz);
1293 }
1294 
1295 template<typename ChildT, Index Log2Dim>
1296 template<typename AccessorT>
1297 inline Index
1299 {
1300  const Index n = this->coord2offset(xyz);
1301  if (this->isChildMaskOn(n)) {
1302  acc.insert(xyz, mNodes[n].getChild());
1303  return mNodes[n].getChild()->getValueLevelAndCache(xyz, acc);
1304  }
1305  return LEVEL;
1306 }
1307 
1308 
1309 template<typename ChildT, Index Log2Dim>
1310 inline bool
1312 {
1313  const Index n = this->coord2offset(xyz);
1314  if (this->isChildMaskOff(n)) {
1315  value = mNodes[n].getValue();
1316  return this->isValueMaskOn(n);
1317  }
1318  return mNodes[n].getChild()->probeValue(xyz, value);
1319 }
1320 
1321 template<typename ChildT, Index Log2Dim>
1322 template<typename AccessorT>
1323 inline bool
1325  ValueType& value, AccessorT& acc) const
1326 {
1327  const Index n = this->coord2offset(xyz);
1328  if (this->isChildMaskOn(n)) {
1329  acc.insert(xyz, mNodes[n].getChild());
1330  return mNodes[n].getChild()->probeValueAndCache(xyz, value, acc);
1331  }
1332  value = mNodes[n].getValue();
1333  return this->isValueMaskOn(n);
1334 }
1335 
1336 
1337 template<typename ChildT, Index Log2Dim>
1338 inline void
1340 {
1341  const Index n = this->coord2offset(xyz);
1342  bool hasChild = this->isChildMaskOn(n);
1343  if (!hasChild && this->isValueMaskOn(n)) {
1344  // If the voxel belongs to a constant tile that is active,
1345  // a child subtree must be constructed.
1346  mChildMask.setOn(n); // we're adding a child node so set the mask on
1347  mValueMask.setOff(n); // value mask is always off if child mask is on
1348  hasChild = true;
1349  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/true));
1350  }
1351  if (hasChild) mNodes[n].getChild()->setValueOff(xyz);
1352 }
1353 
1354 
1355 template<typename ChildT, Index Log2Dim>
1356 inline void
1358 {
1359  const Index n = this->coord2offset(xyz);
1360  bool hasChild = this->isChildMaskOn(n);
1361  if (!hasChild && !this->isValueMaskOn(n)) {
1362  // If the voxel belongs to a constant tile that is inactive,
1363  // a child subtree must be constructed.
1364  mChildMask.setOn(n); // we're adding a child node so set the mask on
1365  mValueMask.setOff(n); // value mask is always off if child mask is on
1366  hasChild = true;
1367  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/false));
1368  }
1369  if (hasChild) mNodes[n].getChild()->setValueOn(xyz);
1370 }
1371 
1372 
1373 template<typename ChildT, Index Log2Dim>
1374 inline void
1376 {
1377  const Index n = InternalNode::coord2offset(xyz);
1378  bool hasChild = this->isChildMaskOn(n);
1379  if (!hasChild) {
1380  const bool active = this->isValueMaskOn(n);
1381  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1382  // If the voxel belongs to a tile that is either active or that
1383  // has a constant value that is different from the one provided,
1384  // a child subtree must be constructed.
1385  mChildMask.setOn(n); // we're adding a child node so set the mask on
1386  mValueMask.setOff(n); // value mask is always off if child mask is on
1387  hasChild = true;
1388  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1389  }
1390  }
1391  if (hasChild) mNodes[n].getChild()->setValueOff(xyz, value);
1392 }
1393 
1394 template<typename ChildT, Index Log2Dim>
1395 template<typename AccessorT>
1396 inline void
1398  const ValueType& value, AccessorT& acc)
1399 {
1400  const Index n = InternalNode::coord2offset(xyz);
1401  bool hasChild = this->isChildMaskOn(n);
1402  if (!hasChild) {
1403  const bool active = this->isValueMaskOn(n);
1404  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1405  // If the voxel belongs to a tile that is either active or that
1406  // has a constant value that is different from the one provided,
1407  // a child subtree must be constructed.
1408  mChildMask.setOn(n); // we're adding a child node so set the mask on
1409  mValueMask.setOff(n); // value mask is always off if child mask is on
1410  hasChild = true;
1411  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1412  }
1413  }
1414  if (hasChild) {
1415  ChildT* child = mNodes[n].getChild();
1416  acc.insert(xyz, child);
1417  child->setValueOffAndCache(xyz, value, acc);
1418  }
1419 }
1420 
1421 
1422 template<typename ChildT, Index Log2Dim>
1423 inline void
1425 {
1426  const Index n = this->coord2offset(xyz);
1427  bool hasChild = this->isChildMaskOn(n);
1428  if (!hasChild) {
1429  const bool active = this->isValueMaskOn(n); // tile's active state
1430  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1431  // If the voxel belongs to a tile that is either inactive or that
1432  // has a constant value that is different from the one provided,
1433  // a child subtree must be constructed.
1434  mChildMask.setOn(n); // we're adding a child node so set the mask on
1435  mValueMask.setOff(n); // value mask is always off if child mask is on
1436  hasChild = true;
1437  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1438  }
1439  }
1440  if (hasChild) mNodes[n].getChild()->setValueOn(xyz, value);
1441 }
1442 
1443 template<typename ChildT, Index Log2Dim>
1444 template<typename AccessorT>
1445 inline void
1447  const ValueType& value, AccessorT& acc)
1448 {
1449  const Index n = this->coord2offset(xyz);
1450  bool hasChild = this->isChildMaskOn(n);
1451  if (!hasChild) {
1452  const bool active = this->isValueMaskOn(n);
1453  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1454  // If the voxel belongs to a tile that is either inactive or that
1455  // has a constant value that is different from the one provided,
1456  // a child subtree must be constructed.
1457  mChildMask.setOn(n); // we're adding a child node so set the mask on
1458  mValueMask.setOff(n); // value mask is always off if child mask is on
1459  hasChild = true;
1460  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1461  }
1462  }
1463  if (hasChild) {
1464  acc.insert(xyz, mNodes[n].getChild());
1465  mNodes[n].getChild()->setValueAndCache(xyz, value, acc);
1466  }
1467 }
1468 
1469 
1470 template<typename ChildT, Index Log2Dim>
1471 inline void
1473 {
1474  const Index n = this->coord2offset(xyz);
1475  bool hasChild = this->isChildMaskOn(n);
1476  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1477  // If the voxel has a tile value that is different from the one provided,
1478  // a child subtree must be constructed.
1479  const bool active = this->isValueMaskOn(n);
1480  mChildMask.setOn(n); // we're adding a child node so set the mask on
1481  mValueMask.setOff(n); // value mask is always off if child mask is on
1482  hasChild = true;
1483  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1484  }
1485  if (hasChild) mNodes[n].getChild()->setValueOnly(xyz, value);
1486 }
1487 
1488 template<typename ChildT, Index Log2Dim>
1489 template<typename AccessorT>
1490 inline void
1492  const ValueType& value, AccessorT& acc)
1493 {
1494  const Index n = this->coord2offset(xyz);
1495  bool hasChild = this->isChildMaskOn(n);
1496  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1497  // If the voxel has a tile value that is different from the one provided,
1498  // a child subtree must be constructed.
1499  const bool active = this->isValueMaskOn(n);
1500  mChildMask.setOn(n); // we're adding a child node so set the mask on
1501  mValueMask.setOff(n); // value mask is always off if child mask is on
1502  hasChild = true;
1503  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1504  }
1505  if (hasChild) {
1506  acc.insert(xyz, mNodes[n].getChild());
1507  mNodes[n].getChild()->setValueOnlyAndCache(xyz, value, acc);
1508  }
1509 }
1510 
1511 
1512 template<typename ChildT, Index Log2Dim>
1513 inline void
1515 {
1516  const Index n = this->coord2offset(xyz);
1517  bool hasChild = this->isChildMaskOn(n);
1518  if (!hasChild) {
1519  if (on != this->isValueMaskOn(n)) {
1520  // If the voxel belongs to a tile with the wrong active state,
1521  // then a child subtree must be constructed.
1522  mChildMask.setOn(n); // we're adding a child node so set the mask on
1523  mValueMask.setOff(n); // value mask is always off if child mask is on
1524  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1525  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1526  hasChild = true;
1527  }
1528  }
1529  if (hasChild) mNodes[n].getChild()->setActiveState(xyz, on);
1530 }
1531 
1532 template<typename ChildT, Index Log2Dim>
1533 template<typename AccessorT>
1534 inline void
1536 {
1537  const Index n = this->coord2offset(xyz);
1538  bool hasChild = this->isChildMaskOn(n);
1539  if (!hasChild) {
1540  if (on != this->isValueMaskOn(n)) {
1541  // If the voxel belongs to a tile with the wrong active state,
1542  // then a child subtree must be constructed.
1543  mChildMask.setOn(n); // we're adding a child node so set the mask on
1544  mValueMask.setOff(n); // value mask is always off if child mask is on
1545  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1546  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1547  hasChild = true;
1548  }
1549  }
1550  if (hasChild) {
1551  ChildT* child = mNodes[n].getChild();
1552  acc.insert(xyz, child);
1553  child->setActiveStateAndCache(xyz, on, acc);
1554  }
1555 }
1556 
1557 
1558 template<typename ChildT, Index Log2Dim>
1559 inline void
1561 {
1562  mValueMask = !mChildMask;
1563  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1564  mNodes[iter.pos()].getChild()->setValuesOn();
1565  }
1566 }
1567 
1568 
1569 template<typename ChildT, Index Log2Dim>
1570 inline void
1572 {
1573  const Index n = InternalNode::coord2offset(xyz);
1574  bool hasChild = this->isChildMaskOn(n);
1575  if (!hasChild) {
1576  const bool active = this->isValueMaskOn(n);
1577  if (!active || (mNodes[n].getValue() > value)) {
1578  // If the voxel belongs to a tile that is either inactive or that
1579  // has a constant value that is greater than the one provided,
1580  // a child subtree must be constructed.
1581  mChildMask.setOn(n); // we're adding a child node so set the mask on
1582  mValueMask.setOff(n); // value mask is always off if child mask is on
1583  hasChild = true;
1584  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1585  }
1586  }
1587  if (hasChild) mNodes[n].getChild()->setValueOnMin(xyz, value);
1588 }
1589 
1590 
1591 template<typename ChildT, Index Log2Dim>
1592 inline void
1594 {
1595  const Index n = InternalNode::coord2offset(xyz);
1596  bool hasChild = this->isChildMaskOn(n);
1597  if (!hasChild) {
1598  const bool active = this->isValueMaskOn(n);
1599  if (!active || (value > mNodes[n].getValue())) {
1600  // If the voxel belongs to a tile that is either inactive or that
1601  // has a constant value that is less than the one provided,
1602  // a child subtree must be constructed.
1603  mChildMask.setOn(n); // we're adding a child node so set the mask on
1604  mValueMask.setOff(n); // value mask is always off if child mask is on
1605  hasChild = true;
1606  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1607  }
1608  }
1609  if (hasChild) mNodes[n].getChild()->setValueOnMax(xyz, value);
1610 }
1611 
1612 
1613 template<typename ChildT, Index Log2Dim>
1614 inline void
1616 {
1617  const Index n = InternalNode::coord2offset(xyz);
1618  bool hasChild = this->isChildMaskOn(n);
1619  if (!hasChild) {
1620  const bool active = this->isValueMaskOn(n);
1621  if (!active || !math::isExactlyEqual(addend, zeroVal<ValueType>())) {
1622  // If the voxel belongs to a tile that is inactive or if
1623  // the addend is nonzero, a child subtree must be constructed.
1624  mChildMask.setOn(n);// we're adding a child node so set the mask on
1625  mValueMask.setOff(n);// value mask is always off if child mask is on
1626  hasChild = true;
1627  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1628  }
1629  }
1630  if (hasChild) mNodes[n].getChild()->setValueOnSum(xyz, addend);
1631 }
1632 
1633 template<typename ChildT, Index Log2Dim>
1634 template<typename AccessorT>
1635 inline void
1637  const ValueType& addend, AccessorT& acc)
1638 {
1639  const Index n = this->coord2offset(xyz);
1640  bool hasChild = this->isChildMaskOn(n);
1641  if (!hasChild) {
1642  const bool active = this->isValueMaskOn(n);
1643  if (!active || !math::isExactlyEqual(addend, zeroVal<ValueType>())) {
1644  // If the voxel belongs to a tile that is inactive or if
1645  // the addend is nonzero, a child subtree must be constructed.
1646  mChildMask.setOn(n); // we're adding a child node so set the mask on
1647  mValueMask.setOff(n); // value mask is always off if child mask is on
1648  hasChild = true;
1649  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1650  }
1651  }
1652  if (hasChild) {
1653  acc.insert(xyz, mNodes[n].getChild());
1654  mNodes[n].getChild()->setValueOnSumAndCache(xyz, addend, acc);
1655  }
1656 }
1657 
1658 
1660 
1661 
1662 template<typename ChildT, Index Log2Dim>
1663 inline void
1664 InternalNode<ChildT, Log2Dim>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1665 {
1666  Coord xyz, tileMin, tileMax;
1667  for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
1668  xyz.setX(x);
1669  for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
1670  xyz.setY(y);
1671  for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
1672  xyz.setZ(z);
1673 
1674  // Get the bounds of the tile that contains voxel (x, y, z).
1675  const Index n = this->coord2offset(xyz);
1676  tileMin = this->offset2globalCoord(n);
1677  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
1678 
1679  if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
1680  // If the box defined by (xyz, bbox.max()) doesn't completely enclose
1681  // the tile to which xyz belongs, create a child node (or retrieve
1682  // the existing one).
1683  ChildT* child = NULL;
1684  if (this->isChildMaskOff(n)) {
1685  // Replace the tile with a newly-created child that is initialized
1686  // with the tile's value and active state.
1687  child = new ChildT(xyz, mNodes[n].getValue(), this->isValueMaskOn(n));
1688  mChildMask.setOn(n);
1689  mValueMask.setOff(n);
1690  mNodes[n].setChild(child);
1691  } else {
1692  child = mNodes[n].getChild();
1693  }
1694 
1695  // Forward the fill request to the child.
1696  if (child) {
1697  child->fill(CoordBBox(xyz, Coord::minComponent(bbox.max(), tileMax)),
1698  value, active);
1699  }
1700 
1701  } else {
1702  // If the box given by (xyz, bbox.max()) completely encloses
1703  // the tile to which xyz belongs, create the tile (if it
1704  // doesn't already exist) and give it the fill value.
1705  this->makeChildNodeEmpty(n, value);
1706  mValueMask.set(n, active);
1707  }
1708  }
1709  }
1710  }
1711 }
1712 
1713 
1715 
1716 
1717 template<typename ChildT, Index Log2Dim>
1718 template<typename DenseT>
1719 inline void
1721 {
1722  const size_t xStride = dense.xStride(), yStride = dense.yStride();// zStride=1
1723  const Coord& min = dense.bbox().min();
1724  for (Coord xyz = bbox.min(), max; xyz[0] <= bbox.max()[0]; xyz[0] = max[0] + 1) {
1725  for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = max[1] + 1) {
1726  for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = max[2] + 1) {
1727  const Index n = this->coord2offset(xyz);
1728  // Get max coordinates of the child node that contains voxel xyz.
1729  max = this->offset2globalCoord(n).offsetBy(ChildT::DIM-1);
1730 
1731  // Get the bbox of the interection of bbox and the child node
1732  CoordBBox sub(xyz, Coord::minComponent(bbox.max(), max));
1733 
1734  if (this->isChildMaskOn(n)) {//is a child
1735  mNodes[n].getChild()->copyToDense(sub, dense);
1736  } else {//a tile value
1737  const ValueType value = mNodes[n].getValue();
1738  sub.translate(-min);
1739  ValueType* a0 = dense.data() + sub.min()[2];
1740  for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
1741  ValueType* a1 = a0 + x*xStride;
1742  for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
1743  ValueType* a2 = a1 + y*yStride;
1744  for (Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z) *a2++ = value;
1745  }
1746  }
1747  }
1748  }
1749  }
1750  }
1751 }
1752 
1753 
1755 
1756 
1757 template<typename ChildT, Index Log2Dim>
1758 inline void
1759 InternalNode<ChildT, Log2Dim>::writeTopology(std::ostream& os, bool toHalf) const
1760 {
1761  mChildMask.save(os);
1762  mValueMask.save(os);
1763 
1764  {
1765  // Copy all of this node's values into an array.
1766  boost::shared_array<ValueType> values(new ValueType[NUM_VALUES]);
1767  const ValueType zero = zeroVal<ValueType>();
1768  for (Index i = 0; i < NUM_VALUES; ++i) {
1769  values[i] = (mChildMask.isOff(i) ? mNodes[i].getValue() : zero);
1770  }
1771  // Compress (optionally) and write out the contents of the array.
1772  io::writeCompressedValues(os, values.get(), NUM_VALUES, mValueMask, mChildMask, toHalf);
1773  }
1774  // Write out the child nodes in order.
1775  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1776  iter->writeTopology(os, toHalf);
1777  }
1778 }
1779 
1780 
1781 template<typename ChildT, Index Log2Dim>
1782 inline void
1783 InternalNode<ChildT, Log2Dim>::readTopology(std::istream& is, bool fromHalf)
1784 {
1785  mChildMask.load(is);
1786  mValueMask.load(is);
1787 
1789  for (Index i = 0; i < NUM_VALUES; ++i) {
1790  if (this->isChildMaskOn(i)) {
1791  ChildNodeType* child =
1792  new ChildNodeType(offset2globalCoord(i), zeroVal<ValueType>());
1793  mNodes[i].setChild(child);
1794  child->readTopology(is);
1795  } else {
1796  ValueType value;
1797  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
1798  mNodes[i].setValue(value);
1799  }
1800  }
1801  } else {
1802  const bool oldVersion =
1804  const Index numValues = (oldVersion ? mChildMask.countOff() : NUM_VALUES);
1805  {
1806  // Read in (and uncompress, if necessary) all of this node's values
1807  // into a contiguous array.
1808  boost::shared_array<ValueType> values(new ValueType[numValues]);
1809  io::readCompressedValues(is, values.get(), numValues, mValueMask, fromHalf);
1810 
1811  // Copy values from the array into this node's table.
1812  if (oldVersion) {
1813  Index n = 0;
1814  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
1815  mNodes[iter.pos()].setValue(values[n++]);
1816  }
1817  assert(n == numValues);
1818  } else {
1819  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
1820  mNodes[iter.pos()].setValue(values[iter.pos()]);
1821  }
1822  }
1823  }
1824  // Read in all child nodes and insert them into the table at their proper locations.
1825  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1826  ChildNodeType* child = new ChildNodeType(iter.getCoord(), zeroVal<ValueType>());
1827  mNodes[iter.pos()].setChild(child);
1828  child->readTopology(is, fromHalf);
1829  }
1830  }
1831 }
1832 
1833 
1835 
1836 
1837 template<typename ChildT, Index Log2Dim>
1838 inline const typename ChildT::ValueType&
1840 {
1841  return (this->isChildMaskOn(0) ? mNodes[0].getChild()->getFirstValue() : mNodes[0].getValue());
1842 }
1843 
1844 
1845 template<typename ChildT, Index Log2Dim>
1846 inline const typename ChildT::ValueType&
1848 {
1849  const Index n = NUM_VALUES - 1;
1850  return (this->isChildMaskOn(n) ? mNodes[n].getChild()->getLastValue() : mNodes[n].getValue());
1851 }
1852 
1853 
1855 
1856 
1857 template<typename ChildT, Index Log2Dim>
1858 inline void
1860 {
1861  this->signedFloodFill(background, negative(background));
1862 }
1863 
1864 
1865 template<typename ChildT, Index Log2Dim>
1866 inline void
1868  const ValueType& insideValue)
1869 {
1870  // First, flood fill all child nodes.
1871  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1872  iter->signedFloodFill(outsideValue, insideValue);
1873  }
1874  const Index first = mChildMask.findFirstOn();
1875  if (first < NUM_VALUES) {
1876  bool xInside = math::isNegative(mNodes[first].getChild()->getFirstValue()),
1877  yInside = xInside, zInside = xInside;
1878  for (Index x = 0; x != (1 << Log2Dim); ++x) {
1879  const int x00 = x << (2 * Log2Dim); // offset for block(x, 0, 0)
1880  if (isChildMaskOn(x00)) {
1881  xInside = math::isNegative(mNodes[x00].getChild()->getLastValue());
1882  }
1883  yInside = xInside;
1884  for (Index y = 0; y != (1 << Log2Dim); ++y) {
1885  const Index xy0 = x00 + (y << Log2Dim); // offset for block(x, y, 0)
1886  if (isChildMaskOn(xy0)) {
1887  yInside = math::isNegative(mNodes[xy0].getChild()->getLastValue());
1888  }
1889  zInside = yInside;
1890  for (Index z = 0; z != (1 << Log2Dim); ++z) {
1891  const Index xyz = xy0 + z; // offset for block(x, y, z)
1892  if (isChildMaskOn(xyz)) {
1893  zInside = math::isNegative(mNodes[xyz].getChild()->getLastValue());
1894  } else {
1895  mNodes[xyz].setValue(zInside ? insideValue : outsideValue);
1896  }
1897  }
1898  }
1899  }
1900  } else {//no child nodes exist simply use the sign of the first tile value.
1901  const ValueType v = math::isNegative(mNodes[0].getValue()) ? insideValue : outsideValue;
1902  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(v);
1903  }
1904 }
1905 
1906 
1907 template<typename ChildT, Index Log2Dim>
1908 inline void
1910 {
1911  for (Index i = 0; i < NUM_VALUES; ++i) {
1912  if (this->isChildMaskOn(i)) {
1913  mNodes[i].getChild()->negate();
1914  } else {
1915  mNodes[i].setValue(negative(mNodes[i].getValue()));
1916  }
1917  }
1918 
1919 }
1920 
1921 
1922 template<typename ChildT, Index Log2Dim>
1923 inline void
1925 {
1926  for (ValueOnIter iter = this->beginValueOn(); iter; ++iter) {
1927  const Index n = iter.pos();
1928  ChildNodeType* child = new ChildNodeType(iter.getCoord(), iter.getValue(), true);
1929  mValueMask.setOff(n);
1930  mChildMask.setOn(n);
1931  mNodes[n].setChild(child);
1932  }
1933  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) iter->voxelizeActiveTiles();
1934 }
1935 
1936 
1937 template<typename ChildT, Index Log2Dim>
1938 inline void
1940  const ValueType& background, const ValueType& otherBackground)
1941 {
1942  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
1943  const Index n = iter.pos();
1944  if (mChildMask.isOff(n)) { // transfer node
1945  ChildNodeType* child = other.mNodes[n].getChild();
1946  other.mChildMask.setOff(n);
1947  // Note other's new tile value is undefined which is okay since
1948  // other is assumed to be cannibalized in the process of merging!
1949  child->resetBackground(otherBackground, background);
1950  mChildMask.setOn(n);
1951  mValueMask.setOff(n);
1952  mNodes[n].setChild(child);
1953  } else {
1954  mNodes[n].getChild()->merge(*iter, background, otherBackground);
1955  }
1956  }
1957 
1958  // Copy active tile values.
1959  for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
1960  const Index n = iter.pos();
1961  if (mChildMask.isOff(n) && mValueMask.isOff(n)) {
1962  mNodes[n].setValue(iter.getValue());
1963  mValueMask.setOn(n);
1964  }
1965  }
1966 }
1967 
1968 
1969 template<typename ChildT, Index Log2Dim>
1970 template<typename OtherChildT>
1971 inline void
1973 {
1974  typedef typename InternalNode<OtherChildT, Log2Dim>::ChildOnCIter OtherChildIter;
1975  typedef typename InternalNode<OtherChildT, Log2Dim>::ValueOnCIter OtherValueIter;
1976 
1977  for (OtherChildIter iter = other.cbeginChildOn(); iter; ++iter) {
1978  const Index i = iter.pos();
1979  if (mChildMask.isOn(i)) {//this has a child node
1980  mNodes[i].getChild()->topologyUnion(*iter);
1981  } else {// this is a tile so replace it with a child branch with identical topology
1982  ChildNodeType* child = new ChildNodeType(*iter, mNodes[i].getValue(), TopologyCopy());
1983  if (mValueMask.isOn(i)) {
1984  mValueMask.isOff(i);//we're replacing the active tile with a child branch
1985  child->setValuesOn();//activate all values since it was an active tile
1986  }
1987  mChildMask.setOn(i);
1988  mNodes[i].setChild(child);
1989  }
1990  }
1991  for (OtherValueIter iter = other.cbeginValueOn(); iter; ++iter) {
1992  const Index i = iter.pos();
1993  if (mChildMask.isOn(i)) {
1994  mNodes[i].getChild()->setValuesOn();
1995  } else if (mValueMask.isOff(i)) { //inactive tile
1996  mValueMask.setOn(i);
1997  }
1998  }
1999 }
2000 
2001 
2003 
2004 
2005 template<typename ChildT, Index Log2Dim>
2006 template<typename CombineOp>
2007 inline void
2009 {
2010  const ValueType zero = zeroVal<ValueType>();
2011 
2013 
2014  for (Index i = 0; i < NUM_VALUES; ++i) {
2015  if (this->isChildMaskOff(i) && other.isChildMaskOff(i)) {
2016  // Both this node and the other node have constant values (tiles).
2017  // Combine the two values and store the result as this node's new tile value.
2018  op(args.setARef(mNodes[i].getValue())
2019  .setAIsActive(isValueMaskOn(i))
2020  .setBRef(other.mNodes[i].getValue())
2021  .setBIsActive(other.isValueMaskOn(i)));
2022  mNodes[i].setValue(args.result());
2023  mValueMask.set(i, args.resultIsActive());
2024  } else if (this->isChildMaskOn(i) && other.isChildMaskOff(i)) {
2025  // Combine this node's child with the other node's constant value.
2026  ChildNodeType* child = mNodes[i].getChild();
2027  assert(child);
2028  if (child) {
2029  child->combine(other.mNodes[i].getValue(), other.isValueMaskOn(i), op);
2030  }
2031  } else if (this->isChildMaskOff(i) && other.isChildMaskOn(i)) {
2032  // Combine this node's constant value with the other node's child.
2033  ChildNodeType* child = other.mNodes[i].getChild();
2034  assert(child);
2035  if (child) {
2036  // Combine this node's constant value with the other node's child,
2037  // but use a new functor in which the A and B values are swapped,
2038  // since the constant value is the A value, not the B value.
2040  child->combine(mNodes[i].getValue(), isValueMaskOn(i), swappedOp);
2041 
2042  // Steal the other node's child.
2043  other.mChildMask.setOff(i);
2044  other.mNodes[i].setValue(zero);
2045  mChildMask.setOn(i);
2046  mValueMask.setOff(i);
2047  mNodes[i].setChild(child);
2048  }
2049 
2050  } else /*if (isChildMaskOn(i) && other.isChildMaskOn(i))*/ {
2051  // Combine this node's child with the other node's child.
2053  *child = mNodes[i].getChild(),
2054  *otherChild = other.mNodes[i].getChild();
2055  assert(child);
2056  assert(otherChild);
2057  if (child && otherChild) {
2058  child->combine(*otherChild, op);
2059  }
2060  }
2061  }
2062 }
2063 
2064 
2065 template<typename ChildT, Index Log2Dim>
2066 template<typename CombineOp>
2067 inline void
2068 InternalNode<ChildT, Log2Dim>::combine(const ValueType& value, bool valueIsActive, CombineOp& op)
2069 {
2071 
2072  for (Index i = 0; i < NUM_VALUES; ++i) {
2073  if (this->isChildMaskOff(i)) {
2074  // Combine this node's constant value with the given constant value.
2075  op(args.setARef(mNodes[i].getValue())
2076  .setAIsActive(isValueMaskOn(i))
2077  .setBRef(value)
2078  .setBIsActive(valueIsActive));
2079  mNodes[i].setValue(args.result());
2080  mValueMask.set(i, args.resultIsActive());
2081  } else /*if (isChildMaskOn(i))*/ {
2082  // Combine this node's child with the given constant value.
2083  ChildNodeType* child = mNodes[i].getChild();
2084  assert(child);
2085  if (child) child->combine(value, valueIsActive, op);
2086  }
2087  }
2088 }
2089 
2090 
2092 
2093 
2094 template<typename ChildT, Index Log2Dim>
2095 template<typename CombineOp>
2096 inline void
2098  CombineOp& op)
2099 {
2101 
2102  for (Index i = 0; i < NUM_VALUES; ++i) {
2103  if (other0.isChildMaskOff(i) && other1.isChildMaskOff(i)) {
2104  op(args.setARef(other0.mNodes[i].getValue())
2105  .setAIsActive(other0.isValueMaskOn(i))
2106  .setBRef(other1.mNodes[i].getValue())
2107  .setBIsActive(other1.isValueMaskOn(i)));
2108  // Replace child i with a constant value.
2109  this->makeChildNodeEmpty(i, args.result());
2110  mValueMask.set(i, args.resultIsActive());
2111  } else {
2112  ChildNodeType* otherChild = other0.isChildMaskOn(i)
2113  ? other0.mNodes[i].getChild() : other1.mNodes[i].getChild();
2114  assert(otherChild);
2115  if (this->isChildMaskOff(i)) {
2116  // Add a new child with the same coordinates, etc.
2117  // as the other node's child.
2118  mChildMask.setOn(i);
2119  mValueMask.setOff(i);
2120  mNodes[i].setChild(new ChildNodeType(otherChild->getOrigin(),
2121  mNodes[i].getValue()));
2122  }
2123 
2124  if (other0.isChildMaskOff(i)) {
2125  // Combine node1's child with node0's constant value
2126  // and write the result into child i.
2127  mNodes[i].getChild()->combine2(other0.mNodes[i].getValue(),
2128  *other1.mNodes[i].getChild(), other0.isValueMaskOn(i), op);
2129  } else if (other1.isChildMaskOff(i)) {
2130  // Combine node0's child with node1's constant value
2131  // and write the result into child i.
2132  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2133  other1.mNodes[i].getValue(), other1.isValueMaskOn(i), op);
2134  } else {
2135  // Combine node0's child with node1's child
2136  // and write the result into child i.
2137  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2138  *other1.mNodes[i].getChild(), op);
2139  }
2140  }
2141  }
2142 }
2143 
2144 
2145 template<typename ChildT, Index Log2Dim>
2146 template<typename CombineOp>
2147 inline void
2149  bool valueIsActive, CombineOp& op)
2150 {
2152 
2153  for (Index i = 0; i < NUM_VALUES; ++i) {
2154  if (other.isChildMaskOff(i)) {
2155  op(args.setARef(value)
2156  .setAIsActive(valueIsActive)
2157  .setBRef(other.mNodes[i].getValue())
2158  .setBIsActive(other.isValueMaskOn(i)));
2159  // Replace child i with a constant value.
2160  this->makeChildNodeEmpty(i, args.result());
2161  mValueMask.set(i, args.resultIsActive());
2162  } else {
2163  ChildNodeType* otherChild = other.mNodes[i].getChild();
2164  assert(otherChild);
2165  if (this->isChildMaskOff(i)) {
2166  // Add a new child with the same coordinates, etc.
2167  // as the other node's child.
2169  mChildMask.setOn(i);
2170  mValueMask.setOff(i);
2171  mNodes[i].setChild(new ChildNodeType(*otherChild));
2172  }
2173  // Combine the other node's child with a constant value
2174  // and write the result into child i.
2175  mNodes[i].getChild()->combine2(value, *otherChild, valueIsActive, op);
2176  }
2177  }
2178 }
2179 
2180 
2181 template<typename ChildT, Index Log2Dim>
2182 template<typename CombineOp>
2183 inline void
2185  bool valueIsActive, CombineOp& op)
2186 {
2188 
2189  for (Index i = 0; i < NUM_VALUES; ++i) {
2190  if (other.isChildMaskOff(i)) {
2191  op(args.setARef(other.mNodes[i].getValue())
2192  .setAIsActive(other.isValueMaskOn(i))
2193  .setBRef(value)
2194  .setBIsActive(valueIsActive));
2195  // Replace child i with a constant value.
2196  this->makeChildNodeEmpty(i, args.result());
2197  mValueMask.set(i, args.resultIsActive());
2198  } else {
2199  ChildNodeType* otherChild = other.mNodes[i].getChild();
2200  assert(otherChild);
2201  if (this->isChildMaskOff(i)) {
2202  // Add a new child with the same coordinates, etc.
2203  // as the other node's child.
2204  mChildMask.setOn(i);
2205  mValueMask.setOff(i);
2206  mNodes[i].setChild(new ChildNodeType(otherChild->getOrigin(),
2207  mNodes[i].getValue()));
2208  }
2209  // Combine the other node's child with a constant value
2210  // and write the result into child i.
2211  mNodes[i].getChild()->combine2(*otherChild, value, valueIsActive, op);
2212  }
2213  }
2214 }
2215 
2216 
2218 
2219 
2220 template<typename ChildT, Index Log2Dim>
2221 template<typename BBoxOp>
2222 inline void
2224 {
2225  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) {
2226 #ifdef _MSC_VER
2227  op.operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
2228 #else
2229  op.template operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
2230 #endif
2231  }
2232  if (op.template descent<LEVEL>()) {
2233  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) i->visitActiveBBox(op);
2234  } else {
2235  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) {
2236 #ifdef _MSC_VER
2237  op.operator()<LEVEL>(i->getNodeBoundingBox());
2238 #else
2239  op.template operator()<LEVEL>(i->getNodeBoundingBox());
2240 #endif
2241  }
2242  }
2243 }
2244 
2245 
2246 template<typename ChildT, Index Log2Dim>
2247 template<typename VisitorOp>
2248 inline void
2250 {
2251  doVisit<InternalNode, VisitorOp, ChildAllIter>(*this, op);
2252 }
2253 
2254 
2255 template<typename ChildT, Index Log2Dim>
2256 template<typename VisitorOp>
2257 inline void
2259 {
2260  doVisit<const InternalNode, VisitorOp, ChildAllCIter>(*this, op);
2261 }
2262 
2263 
2264 template<typename ChildT, Index Log2Dim>
2265 template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
2266 inline void
2267 InternalNode<ChildT, Log2Dim>::doVisit(NodeT& self, VisitorOp& op)
2268 {
2269  typename NodeT::ValueType val;
2270  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2271  if (op(iter)) continue;
2272  if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
2273  child->visit(op);
2274  }
2275  }
2276 }
2277 
2278 
2280 
2281 
2282 template<typename ChildT, Index Log2Dim>
2283 template<typename OtherNodeType, typename VisitorOp>
2284 inline void
2285 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op)
2286 {
2287  doVisit2Node<InternalNode, OtherNodeType, VisitorOp, ChildAllIter,
2288  typename OtherNodeType::ChildAllIter>(*this, other, op);
2289 }
2290 
2291 
2292 template<typename ChildT, Index Log2Dim>
2293 template<typename OtherNodeType, typename VisitorOp>
2294 inline void
2295 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op) const
2296 {
2297  doVisit2Node<const InternalNode, OtherNodeType, VisitorOp, ChildAllCIter,
2298  typename OtherNodeType::ChildAllCIter>(*this, other, op);
2299 }
2300 
2301 
2302 template<typename ChildT, Index Log2Dim>
2303 template<
2304  typename NodeT,
2305  typename OtherNodeT,
2306  typename VisitorOp,
2307  typename ChildAllIterT,
2308  typename OtherChildAllIterT>
2309 inline void
2310 InternalNode<ChildT, Log2Dim>::doVisit2Node(NodeT& self, OtherNodeT& other, VisitorOp& op)
2311 {
2312  // Allow the two nodes to have different ValueTypes, but not different dimensions.
2313  BOOST_STATIC_ASSERT(OtherNodeT::NUM_VALUES == NodeT::NUM_VALUES);
2314  BOOST_STATIC_ASSERT(OtherNodeT::LEVEL == NodeT::LEVEL);
2315 
2316  typename NodeT::ValueType val;
2317  typename OtherNodeT::ValueType otherVal;
2318 
2319  ChildAllIterT iter = self.beginChildAll();
2320  OtherChildAllIterT otherIter = other.beginChildAll();
2321 
2322  for ( ; iter && otherIter; ++iter, ++otherIter)
2323  {
2324  const size_t skipBranch = static_cast<size_t>(op(iter, otherIter));
2325 
2326  typename ChildAllIterT::ChildNodeType* child =
2327  (skipBranch & 1U) ? NULL : iter.probeChild(val);
2328  typename OtherChildAllIterT::ChildNodeType* otherChild =
2329  (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
2330 
2331  if (child != NULL && otherChild != NULL) {
2332  child->visit2Node(*otherChild, op);
2333  } else if (child != NULL) {
2334  child->visit2(otherIter, op);
2335  } else if (otherChild != NULL) {
2336  otherChild->visit2(iter, op, /*otherIsLHS=*/true);
2337  }
2338  }
2339 }
2340 
2341 
2343 
2344 
2345 template<typename ChildT, Index Log2Dim>
2346 template<typename OtherChildAllIterType, typename VisitorOp>
2347 inline void
2348 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
2349  VisitorOp& op, bool otherIsLHS)
2350 {
2351  doVisit2<InternalNode, VisitorOp, ChildAllIter, OtherChildAllIterType>(
2352  *this, otherIter, op, otherIsLHS);
2353 }
2354 
2355 
2356 template<typename ChildT, Index Log2Dim>
2357 template<typename OtherChildAllIterType, typename VisitorOp>
2358 inline void
2359 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
2360  VisitorOp& op, bool otherIsLHS) const
2361 {
2362  doVisit2<const InternalNode, VisitorOp, ChildAllCIter, OtherChildAllIterType>(
2363  *this, otherIter, op, otherIsLHS);
2364 }
2365 
2366 
2367 template<typename ChildT, Index Log2Dim>
2368 template<typename NodeT, typename VisitorOp, typename ChildAllIterT, typename OtherChildAllIterT>
2369 inline void
2370 InternalNode<ChildT, Log2Dim>::doVisit2(NodeT& self, OtherChildAllIterT& otherIter,
2371  VisitorOp& op, bool otherIsLHS)
2372 {
2373  if (!otherIter) return;
2374 
2375  const size_t skipBitMask = (otherIsLHS ? 2U : 1U);
2376 
2377  typename NodeT::ValueType val;
2378  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2379  const size_t skipBranch = static_cast<size_t>(
2380  otherIsLHS ? op(otherIter, iter) : op(iter, otherIter));
2381 
2382  typename ChildAllIterT::ChildNodeType* child =
2383  (skipBranch & skipBitMask) ? NULL : iter.probeChild(val);
2384 
2385  if (child != NULL) child->visit2(otherIter, op, otherIsLHS);
2386  }
2387 }
2388 
2389 
2391 
2392 
2393 template<typename ChildT, Index Log2Dim>
2394 inline void
2395 InternalNode<ChildT, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
2396 {
2397  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2398  iter->writeBuffers(os, toHalf);
2399  }
2400 }
2401 
2402 
2403 template<typename ChildT, Index Log2Dim>
2404 inline void
2405 InternalNode<ChildT, Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
2406 {
2407  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2408  iter->readBuffers(is, fromHalf);
2409  }
2410 }
2411 
2412 
2414 
2415 
2416 template<typename ChildT, Index Log2Dim>
2417 void
2419 {
2420  dims.push_back(Log2Dim);
2421  ChildNodeType::getNodeLog2Dims(dims);
2422 }
2423 
2424 
2425 template<typename ChildT, Index Log2Dim>
2426 inline void
2428 {
2429  assert(n<(1<<3*Log2Dim));
2430  xyz.setX(n >> 2*Log2Dim);
2431  n &= ((1<<2*Log2Dim)-1);
2432  xyz.setY(n >> Log2Dim);
2433  xyz.setZ(n & ((1<<Log2Dim)-1));
2434 }
2435 
2436 
2437 template<typename ChildT, Index Log2Dim>
2438 inline Index
2440 {
2441  return (((xyz[0]&DIM-1u)>>ChildNodeType::TOTAL)<<2*Log2Dim)
2442  + (((xyz[1]&DIM-1u)>>ChildNodeType::TOTAL)<< Log2Dim)
2443  + ((xyz[2]&DIM-1u)>>ChildNodeType::TOTAL);
2444 }
2445 
2446 
2447 template<typename ChildT, Index Log2Dim>
2448 inline Coord
2450 {
2451  Coord local;
2452  this->offset2coord(n, local);
2453  local <<= ChildT::TOTAL;
2454  return local + this->getOrigin();
2455 }
2456 
2457 
2459 
2460 
2461 template<typename ChildT, Index Log2Dim>
2462 inline void
2464  const ValueType& newBackground)
2465 {
2466  if (math::isExactlyEqual(oldBackground, newBackground)) return;
2467  for (Index i = 0; i < NUM_VALUES; ++i) {
2468  if (this->isChildMaskOn(i)) {
2469  mNodes[i].getChild()->resetBackground(oldBackground, newBackground);
2470  } else if (this->isValueMaskOff(i)) {
2471  if (math::isApproxEqual(mNodes[i].getValue(), oldBackground)) {
2472  mNodes[i].setValue(newBackground);
2473  } else if (math::isApproxEqual(mNodes[i].getValue(), negative(oldBackground))) {
2474  mNodes[i].setValue(negative(newBackground));
2475  }
2476  }
2477  }
2478 }
2479 
2480 
2481 template<typename ChildT, Index Log2Dim>
2482 template<typename OtherChildNodeType, Index OtherLog2Dim>
2483 inline bool
2486 {
2487  if (Log2Dim != OtherLog2Dim || mChildMask != other->mChildMask ||
2488  mValueMask != other->mValueMask) return false;
2489  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2490  if (!iter->hasSameTopology(other->mNodes[iter.pos()].getChild())) return false;
2491  }
2492  return true;
2493 }
2494 
2495 
2496 template<typename ChildT, Index Log2Dim>
2497 inline void
2499 {
2500  assert(child);
2501  if (this->isChildMaskOn(i)) {
2502  delete mNodes[i].getChild();
2503  } else {
2504  mChildMask.setOn(i);
2505  mValueMask.setOff(i);
2506  }
2507  mNodes[i].setChild(child);
2508 }
2509 
2510 
2511 template<typename ChildT, Index Log2Dim>
2512 inline ChildT*
2514 {
2515  if (this->isChildMaskOff(i)) {
2516  mNodes[i].setValue(value);
2517  return NULL;
2518  }
2519  ChildNodeType* child = mNodes[i].getChild();
2520  mChildMask.setOff(i);
2521  mNodes[i].setValue(value);
2522  return child;
2523 }
2524 
2525 
2526 template<typename ChildT, Index Log2Dim>
2527 inline void
2529 {
2530  delete this->unsetChildNode(n, value);
2531 }
2532 
2533 template<typename ChildT, Index Log2Dim>
2534 inline ChildT*
2536 {
2537  return (this->isChildMaskOn(n) ? mNodes[n].getChild() : NULL);
2538 }
2539 
2540 
2541 template<typename ChildT, Index Log2Dim>
2542 inline const ChildT*
2544 {
2545  return (this->isChildMaskOn(n) ? mNodes[n].getChild() : NULL);
2546 }
2547 
2548 } // namespace tree
2549 } // namespace OPENVDB_VERSION_NAME
2550 } // namespace openvdb
2551 
2552 #endif // OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
2553 
2554 // Copyright (c) 2012-2013 DreamWorks Animation LLC
2555 // All rights reserved. This software is distributed under the
2556 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )