OpenVDB  0.104.0
InternalNode.h
Go to the documentation of this file.
1 
2 //
3 // Copyright (c) 2012 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  };
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  };
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  };
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 
298  template<typename AccessorT>
299  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
300 
305  template<typename AccessorT>
306  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
307 
312  template<typename AccessorT>
313  void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
314 
319  template<typename AccessorT>
320  void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
321 
327  template<typename AccessorT>
328  void setValueOnSumAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
329 
334  template<typename AccessorT>
335  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
336 
341  template<typename AccessorT>
342  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
343 
348  template<typename AccessorT>
349  bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
350 
356  template<typename AccessorT>
357  OPENVDB_DEPRECATED const ValueType& getValue(const Coord& xyz, bool& on, int& level, AccessorT&) const;
358 
359  template<typename ProbeType, typename AccessorT>
360  OPENVDB_DEPRECATED const ValueType& probe(const Coord& xyz, ProbeType& p, AccessorT&) const;
361 
362  template<bool State, bool Level, typename AccessorT>
363  OPENVDB_DEPRECATED const ValueType& probe(const Coord& xyz, bool& state, int& level, AccessorT&) const;
364 
371  template<typename AccessorT>
372  Index getValueLevelAndCache(const Coord& xyz, AccessorT&) const;
373 
375  void setValuesOn();
376 
380  template<typename AccessorT>
381  OPENVDB_DEPRECATED void updateCache(const Coord& xyz, AccessorT&) const;
382 
383  //
384  // I/O
385  //
386  void writeTopology(std::ostream&, bool toHalf = false) const;
387  void readTopology(std::istream&, bool fromHalf = false);
388  void writeBuffers(std::ostream&, bool toHalf = false) const;
389  void readBuffers(std::istream&, bool fromHalf = false);
390 
391 
392  // @brief Flood fill inactive values based on the signs of the active values,
393  // setting outside values to +background and inside values to -background.
394  void signedFloodFill(const ValueType& background);
395 
396  void negate();
397 
399  void voxelizeActiveTiles();
400 
405  void merge(InternalNode& other, const ValueType& background, const ValueType& otherBackground);
406 
415  template<typename OtherChildNodeType>
416  void topologyUnion(const InternalNode<OtherChildNodeType, Log2Dim>& other);
417 
418  template<typename CombineOp>
419  void combine(InternalNode& other, CombineOp&);
420  template<typename CombineOp>
421  void combine(const ValueType& value, bool valueIsActive, CombineOp&);
422 
423  template<typename CombineOp>
424  void combine2(const InternalNode& other0, const InternalNode& other1, CombineOp&);
425  template<typename CombineOp>
426  void combine2(const ValueType& value, const InternalNode& other,
427  bool valueIsActive, CombineOp&);
428  template<typename CombineOp>
429  void combine2(const InternalNode& other, const ValueType& value,
430  bool valueIsActive, CombineOp&);
431 
437  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
438 
439  template<typename VisitorOp> void visit(VisitorOp&);
440  template<typename VisitorOp> void visit(VisitorOp&) const;
441 
442  template<typename OtherNodeType, typename VisitorOp>
443  void visit2Node(OtherNodeType& other, VisitorOp&);
444  template<typename OtherNodeType, typename VisitorOp>
445  void visit2Node(OtherNodeType& other, VisitorOp&) const;
446  template<typename IterT, typename VisitorOp>
447  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false);
448  template<typename IterT, typename VisitorOp>
449  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false) const;
450 
457  template<typename PruneOp> void pruneOp(PruneOp&);
458 
462  void prune(const ValueType& tolerance = zeroVal<ValueType>());
463 
466  void pruneInactive(const ValueType&);
467 
470  void pruneInactive();
471 
478  LeafNodeType* touchLeaf(const Coord& xyz);
479 
482  LeafNodeType* probeLeaf(const Coord& xyz);
485  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
486 
489  template<typename AccessorT>
490  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT&);
491 
494  template<typename AccessorT>
495  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT&);
498  template<typename AccessorT>
499  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT&) const;
500 
501  void resetBackground(const ValueType& oldBackground, const ValueType& newBackground);
502 
505  template<typename OtherChildNodeType, Index OtherLog2Dim>
506  bool hasSameTopology(const InternalNode<OtherChildNodeType, OtherLog2Dim>* other) const;
507 
508 protected:
510 
511 
516 
519  template<typename, Index> friend class InternalNode;
520 
521  // Mask accessors
522 public:
523  bool isValueMaskOn(Index n) const { return mValueMask.isOn(n); }
524  bool isValueMaskOn() const { return mValueMask.isOn(); }
525  bool isValueMaskOff(Index n) const { return mValueMask.isOff(n); }
526  bool isValueMaskOff() const { return mValueMask.isOff(); }
527  bool isChildMaskOn(Index n) const { return mChildMask.isOn(n); }
528  bool isChildMaskOff(Index n) const { return mChildMask.isOff(n); }
529  bool isChildMaskOff() const { return mChildMask.isOff(); }
530 protected:
532 
533 
534  void setValueMask(Index n, bool on) { mValueMask.set(n, mChildMask.isOn(n) ? false : on); }
536 
537  void makeChildNodeEmpty(Index n, const ValueType& value);
538  void setChildNode(Index i, ChildNodeType* child);
539  ChildNodeType* unsetChildNode(Index i, const ValueType& value);
540 
541  template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
542  static inline void doVisit(NodeT&, VisitorOp&);
543 
544  template<typename NodeT, typename OtherNodeT, typename VisitorOp,
545  typename ChildAllIterT, typename OtherChildAllIterT>
546  static inline void doVisit2Node(NodeT&, OtherNodeT&, VisitorOp&);
547 
548  template<typename NodeT, typename VisitorOp,
549  typename ChildAllIterT, typename OtherChildAllIterT>
550  static inline void doVisit2(NodeT&, OtherChildAllIterT&, VisitorOp&, bool otherIsLHS);
551 
552  ChildNodeType* getChildNode(Index n);
553  const ChildNodeType* getChildNode(Index n) const;
554 
555 
556  UnionType mNodes[NUM_VALUES];
560 }; // class InternalNode
561 
562 
564 
565 
566 template<typename ChildT, Index Log2Dim>
567 inline
569 {
570  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
571 }
572 
573 
574 template<typename ChildT, Index Log2Dim>
575 inline
576 InternalNode<ChildT, Log2Dim>::InternalNode(const Coord& origin, const ValueType& val, bool active):
577  mOrigin(origin[0] & ~(DIM - 1), // zero out the low-order bits
578  origin[1] & ~(DIM - 1),
579  origin[2] & ~(DIM - 1))
580 {
581  if (active) mValueMask.setOn();
582  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
583 }
584 
585 
586 template<typename ChildT, Index Log2Dim>
587 inline
589  mChildMask(other.mChildMask),
590  mValueMask(other.mValueMask),
591  mOrigin(other.mOrigin)
592 {
593  for (Index i = 0; i < NUM_VALUES; ++i) {
594  if (isChildMaskOn(i)) {
595  mNodes[i].setChild(new ChildNodeType(*(other.mNodes[i].getChild())));
596  } else {
597  mNodes[i].setValue(other.mNodes[i].getValue());
598  }
599  }
600 }
601 
602 template<typename ChildT, Index Log2Dim>
603 template<typename OtherChildNodeType>
604 inline
606  const ValueType& offValue, const ValueType& onValue, TopologyCopy):
607  mChildMask(other.mChildMask),
608  mValueMask(other.mValueMask),
609  mOrigin(other.mOrigin)
610 {
611  for (Index i = 0; i < NUM_VALUES; ++i) {
612  if (isChildMaskOn(i)) {
613  mNodes[i].setChild(new ChildNodeType(*(other.mNodes[i].getChild()),
614  offValue, onValue, TopologyCopy()));
615  } else {
616  mNodes[i].setValue(isValueMaskOn(i) ? onValue : offValue);
617  }
618  }
619 }
620 
621 template<typename ChildT, Index Log2Dim>
622 template<typename OtherChildNodeType>
623 inline
625  const ValueType& background, TopologyCopy):
626  mChildMask(other.mChildMask),
627  mValueMask(other.mValueMask),
628  mOrigin(other.mOrigin)
629 {
630  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
631  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
632  mNodes[iter.pos()].setChild(new ChildNodeType(*(other.mNodes[iter.pos()].getChild()),
633  background, TopologyCopy()));
634  }
635 }
636 
637 
638 template<typename ChildT, Index Log2Dim>
639 inline
641 {
642  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
643  delete mNodes[iter.pos()].getChild();
644  }
645 }
646 
647 
649 
650 
651 template<typename ChildT, Index Log2Dim>
652 inline Index32
654 {
655  if (ChildNodeType::getLevel() == 0) return mChildMask.countOn();
656  Index32 sum = 0;
657  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
658  sum += iter->leafCount();
659  }
660  return sum;
661 }
662 
663 
664 template<typename ChildT, Index Log2Dim>
665 inline Index32
667 {
668  Index32 sum = 1;
669  if (ChildNodeType::getLevel() == 0) return sum;
670  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
671  sum += iter->nonLeafCount();
672  }
673  return sum;
674 }
675 
676 
677 template<typename ChildT, Index Log2Dim>
678 inline Index64
680 {
681  Index64 sum = 0;
682  for (Index i = 0; i < NUM_VALUES; ++i) {
683  if (isChildMaskOff(i)) {
684  if (isValueMaskOn(i)) sum += ChildT::NUM_VOXELS;
685  } else {
686  sum += mNodes[i].getChild()->onVoxelCount();
687  }
688  }
689  return sum;
690 }
691 
692 
693 template<typename ChildT, Index Log2Dim>
694 inline Index64
696 {
697  Index64 sum = 0;
698  for (Index i = 0; i < NUM_VALUES; ++i) {
699  if (isChildMaskOff(i)) {
700  if (isValueMaskOff(i)) sum += ChildT::NUM_VOXELS;
701  } else {
702  sum += mNodes[i].getChild()->offVoxelCount();
703  }
704  }
705  return sum;
706 }
707 
708 
709 template<typename ChildT, Index Log2Dim>
710 inline Index64
712 {
713  Index64 sum = 0;
714  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
715  sum += mNodes[iter.pos()].getChild()->onLeafVoxelCount();
716  }
717  return sum;
718 }
719 
720 
721 template<typename ChildT, Index Log2Dim>
722 inline Index64
724 {
725  Index64 sum = 0;
726  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
727  sum += mNodes[iter.pos()].getChild()->offLeafVoxelCount();
728  }
729  return sum;
730 }
731 
732 
733 template<typename ChildT, Index Log2Dim>
734 inline Index64
736 {
737  Index64 sum = NUM_VALUES * sizeof(UnionType) + mChildMask.memUsage()
738  + mValueMask.memUsage() + sizeof(mOrigin);
739  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
740  sum += iter->memUsage();
741  }
742  return sum;
743 }
744 
745 
746 template<typename ChildT, Index Log2Dim>
747 inline void
749 {
750  if (bbox.isInside(this->getNodeBoundingBox())) return;
751 
752  ValueType dummy;
753  for (ChildAllCIter iter = this->cbeginChildAll(); iter; ++iter) {
754  if (const ChildT* child = iter.probeChild(dummy)) {
755  child->evalActiveVoxelBoundingBox(bbox);
756  } else if (iter.isValueOn()) {
757  bbox.expand(iter.getCoord(), ChildT::DIM);
758  }
759  }
760 }
761 
762 
764 
765 
766 template<typename ChildT, Index Log2Dim>
767 template<typename PruneOp>
768 inline void
770 {
771  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
772  const Index i = iter.pos();
773  ChildT* child = mNodes[i].getChild();
774  if (!op(*child)) continue;
775  delete child;
776  mChildMask.setOff(i);
777  mValueMask.set(i, op.state);
778  mNodes[i].setValue(op.value);
779  }
780 
781 }
782 
783 
784 template<typename ChildT, Index Log2Dim>
785 inline void
787 {
788  TolerancePrune<ValueType> op(tolerance);
789  this->pruneOp(op);
790 }
791 
792 
793 template<typename ChildT, Index Log2Dim>
794 inline void
796 {
798  this->pruneOp(op);
799 }
800 
801 
802 template<typename ChildT, Index Log2Dim>
803 inline void
805 {
806  this->pruneInactive(this->getBackground());
807 }
808 
809 template<typename ChildT, Index Log2Dim>
810 inline typename ChildT::LeafNodeType*
812 {
813  const Index n = this->coord2offset(xyz);
814  if (mChildMask.isOff(n)) {
815  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), mValueMask.isOn(n)));
816  mChildMask.setOn(n);
817  mValueMask.setOff(n);
818  }
819  return mNodes[n].getChild()->touchLeaf(xyz);
820 }
821 
822 template<typename ChildT, Index Log2Dim>
823 template<typename AccessorT>
824 inline typename ChildT::LeafNodeType*
826 {
827  const Index n = this->coord2offset(xyz);
828  if (mChildMask.isOff(n)) {
829  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), mValueMask.isOn(n)));
830  mChildMask.setOn(n);
831  mValueMask.setOff(n);
832  }
833  acc.insert(xyz, mNodes[n].getChild());
834  return mNodes[n].getChild()->touchLeafAndCache(xyz,acc);
835 }
836 
837 template<typename ChildT, Index Log2Dim>
838 inline typename ChildT::LeafNodeType*
840 {
841  const Index n = this->coord2offset(xyz);
842  return mChildMask.isOn(n) ? mNodes[n].getChild()->probeLeaf(xyz) : NULL;
843 }
844 
845 template<typename ChildT, Index Log2Dim>
846 inline const typename ChildT::LeafNodeType*
848 {
849  const Index n = this->coord2offset(xyz);
850  return mChildMask.isOn(n) ? mNodes[n].getChild()->probeConstLeaf(xyz) : NULL;
851 }
852 
853 template<typename ChildT, Index Log2Dim>
854 template<typename AccessorT>
855 inline typename ChildT::LeafNodeType*
857 {
858  const Index n = this->coord2offset(xyz);
859  if (mChildMask.isOff(n)) return NULL;
860  acc.insert(xyz, mNodes[n].getChild());
861  return mNodes[n].getChild()->probeLeafAndCache(xyz,acc);
862 }
863 
864 template<typename ChildT, Index Log2Dim>
865 template<typename AccessorT>
866 inline const typename ChildT::LeafNodeType*
868 {
869  const Index n = this->coord2offset(xyz);
870  if (mChildMask.isOff(n)) return NULL;
871  acc.insert(xyz, mNodes[n].getChild());
872  return mNodes[n].getChild()->probeConstLeafAndCache(xyz,acc);
873 }
874 
875 
877 
878 
879 template<typename ChildT, Index Log2Dim>
880 inline bool
882  const ValueType& tolerance) const
883 {
884  bool allEqual = true, firstValue = true, valueState = true;
885  ValueType value = zeroVal<ValueType>();
886  for (Index i = 0; allEqual && i < NUM_VALUES; ++i) {
887  if (this->isChildMaskOff(i)) {
888  // If entry i is a value, check if it is within tolerance
889  // and whether its active state matches the other entries.
890  if (firstValue) {
891  firstValue = false;
892  valueState = isValueMaskOn(i);
893  value = mNodes[i].getValue();
894  } else {
895  allEqual = (isValueMaskOn(i) == valueState)
896  && math::isApproxEqual(mNodes[i].getValue(), value, tolerance);
897  }
898  } else {
899  // If entry i is a child, check if the child is constant and within tolerance
900  // and whether its active state matches the other entries.
901  ValueType childValue = zeroVal<ValueType>();
902  bool isChildOn = false;
903  if (mNodes[i].getChild()->isConstant(childValue, isChildOn, tolerance)) {
904  if (firstValue) {
905  firstValue = false;
906  valueState = isChildOn;
907  value = childValue;
908  } else {
909  allEqual = (isChildOn == valueState)
910  && math::isApproxEqual(childValue, value, tolerance);
911  }
912  } else { // child is not constant
913  allEqual = false;
914  }
915  }
916  }
917  if (allEqual) {
918  constValue = value;
919  state = valueState;
920  }
921  return allEqual;
922 }
923 
924 
926 
927 
928 template<typename ChildT, Index Log2Dim>
929 inline bool
931 {
932  const Index n = this->coord2offset(xyz);
933  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
934  return mNodes[n].getChild()->isValueOn(xyz);
935 }
936 
937 template<typename ChildT, Index Log2Dim>
938 inline bool
940 {
941  const bool anyActiveTiles = !mValueMask.isOff();
942  if (LEVEL==1 || anyActiveTiles) return anyActiveTiles;
943  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
944  if (iter->hasActiveTiles()) return true;
945  }
946  return false;
947 }
948 
949 template<typename ChildT, Index Log2Dim>
950 template<typename AccessorT>
951 inline bool
953 {
954  const Index n = this->coord2offset(xyz);
955  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
956  acc.insert(xyz, mNodes[n].getChild());
957  return mNodes[n].getChild()->isValueOnAndCache(xyz, acc);
958 }
959 
960 
961 template<typename ChildT, Index Log2Dim>
962 inline const typename ChildT::ValueType&
964 {
965  const Index n = this->coord2offset(xyz);
966  return this->isChildMaskOff(n) ? mNodes[n].getValue()
967  : mNodes[n].getChild()->getValue(xyz);
968 }
969 
970 template<typename ChildT, Index Log2Dim>
971 template<typename AccessorT>
972 inline const typename ChildT::ValueType&
974 {
975  const Index n = this->coord2offset(xyz);
976  if (this->isChildMaskOn(n)) {
977  acc.insert(xyz, mNodes[n].getChild());
978  return mNodes[n].getChild()->getValueAndCache(xyz, acc);
979  }
980  return mNodes[n].getValue();
981 }
982 
983 
984 template<typename ChildT, Index Log2Dim>
985 inline Index
987 {
988  const Index n = this->coord2offset(xyz);
989  return this->isChildMaskOff(n) ? LEVEL : mNodes[n].getChild()->getValueLevel(xyz);
990 }
991 
992 template<typename ChildT, Index Log2Dim>
993 template<typename AccessorT>
994 inline Index
996 {
997  const Index n = this->coord2offset(xyz);
998  if (this->isChildMaskOn(n)) {
999  acc.insert(xyz, mNodes[n].getChild());
1000  return mNodes[n].getChild()->getValueLevelAndCache(xyz, acc);
1001  }
1002  return LEVEL;
1003 }
1004 
1005 
1006 template<typename ChildT, Index Log2Dim>
1007 inline bool
1009 {
1010  const Index n = this->coord2offset(xyz);
1011  if (this->isChildMaskOff(n)) {
1012  value = mNodes[n].getValue();
1013  return this->isValueMaskOn(n);
1014  }
1015  return mNodes[n].getChild()->probeValue(xyz, value);
1016 }
1017 
1018 template<typename ChildT, Index Log2Dim>
1019 template<typename AccessorT>
1020 inline bool
1022  ValueType& value, AccessorT& acc) const
1023 {
1024  const Index n = this->coord2offset(xyz);
1025  if (this->isChildMaskOn(n)) {
1026  acc.insert(xyz, mNodes[n].getChild());
1027  return mNodes[n].getChild()->probeValueAndCache(xyz, value, acc);
1028  }
1029  value = mNodes[n].getValue();
1030  return this->isValueMaskOn(n);
1031 }
1032 
1033 
1034 template<typename ChildT, Index Log2Dim>
1035 template<typename AccessorT>
1036 inline const typename ChildT::ValueType&
1037 InternalNode<ChildT, Log2Dim>::getValue(const Coord& xyz, bool& state, int& level,
1038  AccessorT& acc) const
1039 {
1040  const Index n = this->coord2offset(xyz);
1041  if (this->isChildMaskOn(n)) {
1042  acc.insert(xyz, mNodes[n].getChild());
1043  return mNodes[n].getChild()->getValue(xyz, state, level, acc);
1044  }
1045  state = this->isValueMaskOn(n);
1046  level = LEVEL;
1047  return mNodes[n].getValue();
1048 }
1049 
1050 
1051 template<typename ChildT, Index Log2Dim>
1052 template<typename ProbeT, typename AccessorT>
1053 inline const typename ChildT::ValueType&
1054 InternalNode<ChildT, Log2Dim>::probe(const Coord& xyz, ProbeT& p, AccessorT& acc) const
1055 {
1056  const Index n = this->coord2offset(xyz);
1057  if (this->isChildMaskOn(n)) {
1058  acc.insert(xyz, mNodes[n].getChild());
1059  return mNodes[n].getChild()->probe(xyz, p, acc);
1060  }
1061  p.setState(this->isValueMaskOn(n));
1062  p.setLevel(LEVEL);
1063  return mNodes[n].getValue();
1064 }
1065 
1066 template<typename ChildT, Index Log2Dim>
1067 template<bool State, bool Level, typename AccessorT>
1068 inline const typename ChildT::ValueType&
1069 InternalNode<ChildT, Log2Dim>::probe(const Coord& xyz, bool& state, int& level, AccessorT& acc) const
1070 {
1071  const Index n = this->coord2offset(xyz);
1072  if (this->isChildMaskOn(n)) {
1073  acc.insert(xyz, mNodes[n].getChild());
1074  return mNodes[n].getChild()->template probe<State,Level,AccessorT>(xyz, state, level, acc);
1075  }
1076  if (State) state = this->isValueMaskOn(n);
1077  if (Level) level = LEVEL;
1078  return mNodes[n].getValue();
1079 }
1080 
1081 
1082 template<typename ChildT, Index Log2Dim>
1083 inline void
1085 {
1086  const Index n = this->coord2offset(xyz);
1087  bool hasChild = this->isChildMaskOn(n);
1088  if (!hasChild && this->isValueMaskOn(n)) {
1089  // If the voxel belongs to a constant tile that is active,
1090  // a child subtree must be constructed.
1091  mChildMask.setOn(n); // we're adding a child node so set the mask on
1092  mValueMask.setOff(n); // value mask is always off if child mask is on
1093  hasChild = true;
1094  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/true));
1095  }
1096  if (hasChild) mNodes[n].getChild()->setValueOff(xyz);
1097 }
1098 
1099 
1100 template<typename ChildT, Index Log2Dim>
1101 inline void
1103 {
1104  const Index n = this->coord2offset(xyz);
1105  bool hasChild = this->isChildMaskOn(n);
1106  if (!hasChild && !this->isValueMaskOn(n)) {
1107  // If the voxel belongs to a constant tile that is inactive,
1108  // a child subtree must be constructed.
1109  mChildMask.setOn(n); // we're adding a child node so set the mask on
1110  mValueMask.setOff(n); // value mask is always off if child mask is on
1111  hasChild = true;
1112  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/false));
1113  }
1114  if (hasChild) mNodes[n].getChild()->setValueOn(xyz);
1115 }
1116 
1117 
1118 template<typename ChildT, Index Log2Dim>
1119 inline void
1121 {
1122  const Index n = InternalNode::coord2offset(xyz);
1123  bool hasChild = this->isChildMaskOn(n);
1124  if (!hasChild) {
1125  const bool active = this->isValueMaskOn(n);
1126  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1127  // If the voxel belongs to a tile that is either active or that
1128  // has a constant value that is different from the one provided,
1129  // a child subtree must be constructed.
1130  mChildMask.setOn(n); // we're adding a child node so set the mask on
1131  mValueMask.setOff(n); // value mask is always off if child mask is on
1132  hasChild = true;
1133  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1134  }
1135  }
1136  if (hasChild) mNodes[n].getChild()->setValueOff(xyz, value);
1137 }
1138 
1139 template<typename ChildT, Index Log2Dim>
1140 template<typename AccessorT>
1141 inline void
1143  const ValueType& value, AccessorT& acc)
1144 {
1145  const Index n = InternalNode::coord2offset(xyz);
1146  bool hasChild = this->isChildMaskOn(n);
1147  if (!hasChild) {
1148  const bool active = this->isValueMaskOn(n);
1149  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1150  // If the voxel belongs to a tile that is either active or that
1151  // has a constant value that is different from the one provided,
1152  // a child subtree must be constructed.
1153  mChildMask.setOn(n); // we're adding a child node so set the mask on
1154  mValueMask.setOff(n); // value mask is always off if child mask is on
1155  hasChild = true;
1156  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1157  }
1158  }
1159  if (hasChild) {
1160  ChildT* child = mNodes[n].getChild();
1161  acc.insert(xyz, child);
1162  child->setValueOffAndCache(xyz, value, acc);
1163  }
1164 }
1165 
1166 
1167 template<typename ChildT, Index Log2Dim>
1168 inline void
1170 {
1171  const Index n = this->coord2offset(xyz);
1172  bool hasChild = this->isChildMaskOn(n);
1173  if (!hasChild) {
1174  const bool active = this->isValueMaskOn(n); // tile's active state
1175  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1176  // If the voxel belongs to a tile that is either inactive or that
1177  // has a constant value that is different from the one provided,
1178  // a child subtree must be constructed.
1179  mChildMask.setOn(n); // we're adding a child node so set the mask on
1180  mValueMask.setOff(n); // value mask is always off if child mask is on
1181  hasChild = true;
1182  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1183  }
1184  }
1185  if (hasChild) mNodes[n].getChild()->setValueOn(xyz, value);
1186 }
1187 
1188 template<typename ChildT, Index Log2Dim>
1189 template<typename AccessorT>
1190 inline void
1192  const ValueType& value, AccessorT& acc)
1193 {
1194  const Index n = this->coord2offset(xyz);
1195  bool hasChild = this->isChildMaskOn(n);
1196  if (!hasChild) {
1197  const bool active = this->isValueMaskOn(n);
1198  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1199  // If the voxel belongs to a tile that is either inactive or that
1200  // has a constant value that is different from the one provided,
1201  // a child subtree must be constructed.
1202  mChildMask.setOn(n); // we're adding a child node so set the mask on
1203  mValueMask.setOff(n); // value mask is always off if child mask is on
1204  hasChild = true;
1205  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1206  }
1207  }
1208  if (hasChild) {
1209  acc.insert(xyz, mNodes[n].getChild());
1210  mNodes[n].getChild()->setValueAndCache(xyz, value, acc);
1211  }
1212 }
1213 
1214 
1215 template<typename ChildT, Index Log2Dim>
1216 inline void
1218 {
1219  const Index n = this->coord2offset(xyz);
1220  bool hasChild = this->isChildMaskOn(n);
1221  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1222  // If the voxel has a tile value that is different from the one provided,
1223  // a child subtree must be constructed.
1224  const bool active = this->isValueMaskOn(n);
1225  mChildMask.setOn(n); // we're adding a child node so set the mask on
1226  mValueMask.setOff(n); // value mask is always off if child mask is on
1227  hasChild = true;
1228  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1229  }
1230  if (hasChild) mNodes[n].getChild()->setValueOnly(xyz, value);
1231 }
1232 
1233 template<typename ChildT, Index Log2Dim>
1234 template<typename AccessorT>
1235 inline void
1237  const ValueType& value, AccessorT& acc)
1238 {
1239  const Index n = this->coord2offset(xyz);
1240  bool hasChild = this->isChildMaskOn(n);
1241  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1242  // If the voxel has a tile value that is different from the one provided,
1243  // a child subtree must be constructed.
1244  const bool active = this->isValueMaskOn(n);
1245  mChildMask.setOn(n); // we're adding a child node so set the mask on
1246  mValueMask.setOff(n); // value mask is always off if child mask is on
1247  hasChild = true;
1248  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1249  }
1250  if (hasChild) {
1251  acc.insert(xyz, mNodes[n].getChild());
1252  mNodes[n].getChild()->setValueOnlyAndCache(xyz, value, acc);
1253  }
1254 }
1255 
1256 
1257 template<typename ChildT, Index Log2Dim>
1258 inline void
1260 {
1261  const Index n = this->coord2offset(xyz);
1262  bool hasChild = this->isChildMaskOn(n);
1263  if (!hasChild) {
1264  if (on != this->isValueMaskOn(n)) {
1265  // If the voxel belongs to a tile with the wrong active state,
1266  // then a child subtree must be constructed.
1267  mChildMask.setOn(n); // we're adding a child node so set the mask on
1268  mValueMask.setOff(n); // value mask is always off if child mask is on
1269  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1270  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1271  hasChild = true;
1272  }
1273  }
1274  if (hasChild) mNodes[n].getChild()->setActiveState(xyz, on);
1275 }
1276 
1277 template<typename ChildT, Index Log2Dim>
1278 template<typename AccessorT>
1279 inline void
1281 {
1282  const Index n = this->coord2offset(xyz);
1283  bool hasChild = this->isChildMaskOn(n);
1284  if (!hasChild) {
1285  if (on != this->isValueMaskOn(n)) {
1286  // If the voxel belongs to a tile with the wrong active state,
1287  // then a child subtree must be constructed.
1288  mChildMask.setOn(n); // we're adding a child node so set the mask on
1289  mValueMask.setOff(n); // value mask is always off if child mask is on
1290  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1291  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1292  hasChild = true;
1293  }
1294  }
1295  if (hasChild) {
1296  ChildT* child = mNodes[n].getChild();
1297  acc.insert(xyz, child);
1298  child->setActiveStateAndCache(xyz, on, acc);
1299  }
1300 }
1301 
1302 
1303 template<typename ChildT, Index Log2Dim>
1304 inline void
1306 {
1307  mValueMask = !mChildMask;
1308  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1309  mNodes[iter.pos()].getChild()->setValuesOn();
1310  }
1311 }
1312 
1313 
1314 template<typename ChildT, Index Log2Dim>
1315 inline void
1317 {
1318  const Index n = InternalNode::coord2offset(xyz);
1319  bool hasChild = this->isChildMaskOn(n);
1320  if (!hasChild) {
1321  const bool active = this->isValueMaskOn(n);
1322  if (!active || (mNodes[n].getValue() > value)) {
1323  // If the voxel belongs to a tile that is either inactive or that
1324  // has a constant value that is greater than the one provided,
1325  // a child subtree must be constructed.
1326  mChildMask.setOn(n); // we're adding a child node so set the mask on
1327  mValueMask.setOff(n); // value mask is always off if child mask is on
1328  hasChild = true;
1329  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1330  }
1331  }
1332  if (hasChild) mNodes[n].getChild()->setValueOnMin(xyz, value);
1333 }
1334 
1335 
1336 template<typename ChildT, Index Log2Dim>
1337 inline void
1339 {
1340  const Index n = InternalNode::coord2offset(xyz);
1341  bool hasChild = this->isChildMaskOn(n);
1342  if (!hasChild) {
1343  const bool active = this->isValueMaskOn(n);
1344  if (!active || (value > mNodes[n].getValue())) {
1345  // If the voxel belongs to a tile that is either inactive or that
1346  // has a constant value that is less than the one provided,
1347  // a child subtree must be constructed.
1348  mChildMask.setOn(n); // we're adding a child node so set the mask on
1349  mValueMask.setOff(n); // value mask is always off if child mask is on
1350  hasChild = true;
1351  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1352  }
1353  }
1354  if (hasChild) mNodes[n].getChild()->setValueOnMax(xyz, value);
1355 }
1356 
1357 
1358 template<typename ChildT, Index Log2Dim>
1359 inline void
1361 {
1362  const Index n = InternalNode::coord2offset(xyz);
1363  bool hasChild = this->isChildMaskOn(n);
1364  if (!hasChild) {
1365  const bool active = this->isValueMaskOn(n);
1366  if (!active || !math::isExactlyEqual(addend, zeroVal<ValueType>())) {
1367  // If the voxel belongs to a tile that is inactive or if
1368  // the addend is nonzero, a child subtree must be constructed.
1369  mChildMask.setOn(n);// we're adding a child node so set the mask on
1370  mValueMask.setOff(n);// value mask is always off if child mask is on
1371  hasChild = true;
1372  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1373  }
1374  }
1375  if (hasChild) mNodes[n].getChild()->setValueOnSum(xyz, addend);
1376 }
1377 
1378 template<typename ChildT, Index Log2Dim>
1379 template<typename AccessorT>
1380 inline void
1382  const ValueType& addend, AccessorT& acc)
1383 {
1384  const Index n = this->coord2offset(xyz);
1385  bool hasChild = this->isChildMaskOn(n);
1386  if (!hasChild) {
1387  const bool active = this->isValueMaskOn(n);
1388  if (!active || !math::isExactlyEqual(addend, zeroVal<ValueType>())) {
1389  // If the voxel belongs to a tile that is inactive or if
1390  // the addend is nonzero, a child subtree must be constructed.
1391  mChildMask.setOn(n); // we're adding a child node so set the mask on
1392  mValueMask.setOff(n); // value mask is always off if child mask is on
1393  hasChild = true;
1394  mNodes[n].setChild(new ChildNodeType(xyz, mNodes[n].getValue(), active));
1395  }
1396  }
1397  if (hasChild) {
1398  acc.insert(xyz, mNodes[n].getChild());
1399  mNodes[n].getChild()->setValueOnSumAndCache(xyz, addend, acc);
1400  }
1401 }
1402 
1403 
1404 template<typename ChildT, Index Log2Dim>
1405 template<typename AccessorT>
1406 inline void
1407 InternalNode<ChildT, Log2Dim>::updateCache(const Coord& xyz, AccessorT& acc) const
1408 {
1409  const Index n = this->coord2offset(xyz);
1410  if (this->isChildMaskOn(n)) {
1411  acc.insert(xyz, mNodes[n].getChild());
1412  mNodes[n].getChild()->updateCache(xyz, acc);
1413  }
1414 }
1415 
1416 
1418 
1419 
1420 template<typename ChildT, Index Log2Dim>
1421 inline void
1422 InternalNode<ChildT, Log2Dim>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1423 {
1424  Coord xyz, tileMin, tileMax;
1425  for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
1426  xyz.setX(x);
1427  for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
1428  xyz.setY(y);
1429  for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
1430  xyz.setZ(z);
1431 
1432  // Get the bounds of the tile that contains voxel (x, y, z).
1433  const Index n = this->coord2offset(xyz);
1434  tileMin = this->offset2globalCoord(n);
1435  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
1436 
1437  if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
1438  // If the box defined by (xyz, bbox.max()) doesn't completely enclose
1439  // the tile to which xyz belongs, create a child node (or retrieve
1440  // the existing one).
1441  ChildT* child = NULL;
1442  if (this->isChildMaskOff(n)) {
1443  // Replace the tile with a newly-created child that is initialized
1444  // with the tile's value and active state.
1445  child = new ChildT(xyz, mNodes[n].getValue(), this->isValueMaskOn(n));
1446  mChildMask.setOn(n);
1447  mValueMask.setOff(n);
1448  mNodes[n].setChild(child);
1449  } else {
1450  child = mNodes[n].getChild();
1451  }
1452 
1453  // Forward the fill request to the child.
1454  if (child) {
1455  child->fill(CoordBBox(xyz, Coord::minComponent(bbox.max(), tileMax)),
1456  value, active);
1457  }
1458 
1459  } else {
1460  // If the box given by (xyz, bbox.max()) completely encloses
1461  // the tile to which xyz belongs, create the tile (if it
1462  // doesn't already exist) and give it the fill value.
1463  this->makeChildNodeEmpty(n, value);
1464  mValueMask.set(n, active);
1465  }
1466  }
1467  }
1468  }
1469 }
1470 
1471 
1473 
1474 
1475 template<typename ChildT, Index Log2Dim>
1476 inline void
1477 InternalNode<ChildT, Log2Dim>::writeTopology(std::ostream& os, bool toHalf) const
1478 {
1479  mChildMask.save(os);
1480  mValueMask.save(os);
1481 
1482  {
1483  // Copy all of this node's values into an array.
1484  boost::shared_array<ValueType> values(new ValueType[NUM_VALUES]);
1485  const ValueType zero = zeroVal<ValueType>();
1486  for (Index i = 0; i < NUM_VALUES; ++i) {
1487  values[i] = (mChildMask.isOff(i) ? mNodes[i].getValue() : zero);
1488  }
1489  // Compress (optionally) and write out the contents of the array.
1490  io::writeCompressedValues(os, values.get(), NUM_VALUES, mValueMask, mChildMask, toHalf);
1491  }
1492  // Write out the child nodes in order.
1493  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1494  iter->writeTopology(os, toHalf);
1495  }
1496 }
1497 
1498 
1499 template<typename ChildT, Index Log2Dim>
1500 inline void
1501 InternalNode<ChildT, Log2Dim>::readTopology(std::istream& is, bool fromHalf)
1502 {
1503  mChildMask.load(is);
1504  mValueMask.load(is);
1505 
1507  for (Index i = 0; i < NUM_VALUES; ++i) {
1508  if (this->isChildMaskOn(i)) {
1509  ChildNodeType* child =
1510  new ChildNodeType(offset2globalCoord(i), zeroVal<ValueType>());
1511  mNodes[i].setChild(child);
1512  child->readTopology(is);
1513  } else {
1514  ValueType value;
1515  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
1516  mNodes[i].setValue(value);
1517  }
1518  }
1519  } else {
1520  const bool oldVersion =
1522  const Index numValues = (oldVersion ? mChildMask.countOff() : NUM_VALUES);
1523  {
1524  // Read in (and uncompress, if necessary) all of this node's values
1525  // into a contiguous array.
1526  boost::shared_array<ValueType> values(new ValueType[numValues]);
1527  io::readCompressedValues(is, values.get(), numValues, mValueMask, fromHalf);
1528 
1529  // Copy values from the array into this node's table.
1530  if (oldVersion) {
1531  Index n = 0;
1532  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
1533  mNodes[iter.pos()].setValue(values[n++]);
1534  }
1535  assert(n == numValues);
1536  } else {
1537  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
1538  mNodes[iter.pos()].setValue(values[iter.pos()]);
1539  }
1540  }
1541  }
1542  // Read in all child nodes and insert them into the table at their proper locations.
1543  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1544  ChildNodeType* child = new ChildNodeType(iter.getCoord(), zeroVal<ValueType>());
1545  mNodes[iter.pos()].setChild(child);
1546  child->readTopology(is, fromHalf);
1547  }
1548  }
1549 }
1550 
1551 
1553 
1554 
1555 template<typename ChildT, Index Log2Dim>
1556 inline const typename ChildT::ValueType&
1558 {
1559  return (this->isChildMaskOn(0) ? mNodes[0].getChild()->getFirstValue() : mNodes[0].getValue());
1560 }
1561 
1562 
1563 template<typename ChildT, Index Log2Dim>
1564 inline const typename ChildT::ValueType&
1566 {
1567  const Index n = NUM_VALUES - 1;
1568  return (this->isChildMaskOn(n) ? mNodes[n].getChild()->getLastValue() : mNodes[n].getValue());
1569 }
1570 
1571 
1573 
1577 template<typename ChildT, Index Log2Dim>
1578 inline void
1580 {
1581  const ValueType zero = zeroVal<ValueType>();
1582  assert(!math::isExactlyEqual(background, zero)); // background must differ from -background
1583 
1584  // First, flood fill all child nodes.
1585  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1586  iter->signedFloodFill(background);
1587  }
1588  const Index first = mChildMask.findFirstOn();
1589  assert(first < NUM_VALUES);
1590  bool inside = (mNodes[first].getChild()->getFirstValue() < zero),
1591  xInside = inside,
1592  yInside = inside;
1593  for (Index i = 0; i != (1 << Log2Dim); ++i) {
1594  const int i00 = i << (2 * Log2Dim); // offset for block(i, 0, 0)
1595  if (isChildMaskOn(i00)) {
1596  xInside = (mNodes[i00].getChild()->getLastValue() < zero);
1597  }
1598  yInside = xInside;
1599  for (Index j = 0; j != (1 << Log2Dim); ++j) {
1600  const Index ij0 = i00 + (j << Log2Dim); // offset for block(i, j, 0)
1601  if (isChildMaskOn(ij0)) {
1602  yInside = (mNodes[ij0].getChild()->getLastValue() < zero);
1603  }
1604  inside = yInside;
1605  for (Index k = 0; k != (1 << Log2Dim); ++k) {
1606  const Index ijk = ij0 + k; // offset for block(i, j, k)
1607  if (isChildMaskOn(ijk)) {
1608  inside = (mNodes[ijk].getChild()->getLastValue() < zero);
1609  } else {
1610  mNodes[ijk].setValue(inside ? negative(background) : background);
1611  }
1612  }
1613  }
1614  }
1615 }
1616 
1617 
1618 template<typename ChildT, Index Log2Dim>
1619 inline void
1621 {
1622  for (Index i = 0; i < NUM_VALUES; ++i) {
1623  if (this->isChildMaskOn(i)) {
1624  mNodes[i].getChild()->negate();
1625  } else {
1626  mNodes[i].setValue(negative(mNodes[i].getValue()));
1627  }
1628  }
1629 
1630 }
1631 
1632 template<typename ChildT, Index Log2Dim>
1633 inline void
1635 {
1636  for (ValueOnIter iter = this->beginValueOn(); iter; ++iter) {
1637  const Index n = iter.pos();
1638  ChildNodeType* child = new ChildNodeType(iter.getCoord(), iter.getValue(), true);
1639  mValueMask.setOff(n);
1640  mChildMask.setOn(n);
1641  mNodes[n].setChild(child);
1642  }
1643  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) iter->voxelizeActiveTiles();
1644 }
1645 
1646 template<typename ChildT, Index Log2Dim>
1647 inline void
1649  const ValueType& background, const ValueType& otherBackground)
1650 {
1651  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
1652  const Index n = iter.pos();
1653  if (mChildMask.isOff(n)) { // transfer node
1654  ChildNodeType* child = other.mNodes[n].getChild();
1655  other.mChildMask.setOff(n);
1656  // Note other's new tile value is undefined which is okay since
1657  // other is assumed to be cannibalized in the process of merging!
1658  child->resetBackground(otherBackground, background);
1659  mChildMask.setOn(n);
1660  mValueMask.setOff(n);
1661  mNodes[n].setChild(child);
1662  } else {
1663  mNodes[n].getChild()->merge(*iter, background, otherBackground);
1664  }
1665  }
1666 
1667  // Copy active tile values.
1668  for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
1669  const Index n = iter.pos();
1670  if (mChildMask.isOff(n) && mValueMask.isOff(n)) {
1671  mNodes[n].setValue(iter.getValue());
1672  mValueMask.setOn(n);
1673  }
1674  }
1675 }
1676 
1677 
1678 template<typename ChildT, Index Log2Dim>
1679 template<typename OtherChildT>
1680 inline void
1682 {
1683  typedef typename InternalNode<OtherChildT, Log2Dim>::ChildOnCIter OtherChildIter;
1684  typedef typename InternalNode<OtherChildT, Log2Dim>::ValueOnCIter OtherValueIter;
1685 
1686  for (OtherChildIter iter = other.cbeginChildOn(); iter; ++iter) {
1687  const Index i = iter.pos();
1688  if (mChildMask.isOn(i)) {
1689  mNodes[i].getChild()->topologyUnion(*iter);
1690  } else if (mValueMask.isOff(i)) { //inactive tile
1691  mChildMask.setOn(i);
1692  mNodes[i].setChild(new ChildNodeType(*iter, mNodes[i].getValue(), TopologyCopy()));
1693  }
1694  }
1695  for (OtherValueIter iter = other.cbeginValueOn(); iter; ++iter) {
1696  const Index i = iter.pos();
1697  if (mChildMask.isOn(i)) {
1698  mNodes[i].getChild()->setValuesOn();
1699  } else if (mValueMask.isOff(i)) { //inactive tile
1700  mValueMask.setOn(i);
1701  }
1702  }
1703 }
1704 
1706 
1707 
1708 template<typename ChildT, Index Log2Dim>
1709 template<typename CombineOp>
1710 inline void
1712 {
1713  const ValueType zero = zeroVal<ValueType>();
1714 
1716 
1717  for (Index i = 0; i < NUM_VALUES; ++i) {
1718  if (this->isChildMaskOff(i) && other.isChildMaskOff(i)) {
1719  // Both this node and the other node have constant values (tiles).
1720  // Combine the two values and store the result as this node's new tile value.
1721  op(args.setARef(mNodes[i].getValue())
1722  .setAIsActive(isValueMaskOn(i))
1723  .setBRef(other.mNodes[i].getValue())
1724  .setBIsActive(other.isValueMaskOn(i)));
1725  mNodes[i].setValue(args.result());
1726  mValueMask.set(i, args.resultIsActive());
1727  } else if (this->isChildMaskOn(i) && other.isChildMaskOff(i)) {
1728  // Combine this node's child with the other node's constant value.
1729  ChildNodeType* child = mNodes[i].getChild();
1730  assert(child);
1731  if (child) {
1732  child->combine(other.mNodes[i].getValue(), other.isValueMaskOn(i), op);
1733  }
1734  } else if (this->isChildMaskOff(i) && other.isChildMaskOn(i)) {
1735  // Combine this node's constant value with the other node's child.
1736  ChildNodeType* child = other.mNodes[i].getChild();
1737  assert(child);
1738  if (child) {
1739  // Combine this node's constant value with the other node's child,
1740  // but use a new functor in which the A and B values are swapped,
1741  // since the constant value is the A value, not the B value.
1743  child->combine(mNodes[i].getValue(), isValueMaskOn(i), swappedOp);
1744 
1745  // Steal the other node's child.
1746  other.mChildMask.setOff(i);
1747  other.mNodes[i].setValue(zero);
1748  mChildMask.setOn(i);
1749  mValueMask.setOff(i);
1750  mNodes[i].setChild(child);
1751  }
1752 
1753  } else /*if (isChildMaskOn(i) && other.isChildMaskOn(i))*/ {
1754  // Combine this node's child with the other node's child.
1756  *child = mNodes[i].getChild(),
1757  *otherChild = other.mNodes[i].getChild();
1758  assert(child);
1759  assert(otherChild);
1760  if (child && otherChild) {
1761  child->combine(*otherChild, op);
1762  }
1763  }
1764  }
1765 }
1766 
1767 
1768 template<typename ChildT, Index Log2Dim>
1769 template<typename CombineOp>
1770 inline void
1771 InternalNode<ChildT, Log2Dim>::combine(const ValueType& value, bool valueIsActive, CombineOp& op)
1772 {
1774 
1775  for (Index i = 0; i < NUM_VALUES; ++i) {
1776  if (this->isChildMaskOff(i)) {
1777  // Combine this node's constant value with the given constant value.
1778  op(args.setARef(mNodes[i].getValue())
1779  .setAIsActive(isValueMaskOn(i))
1780  .setBRef(value)
1781  .setBIsActive(valueIsActive));
1782  mNodes[i].setValue(args.result());
1783  mValueMask.set(i, args.resultIsActive());
1784  } else /*if (isChildMaskOn(i))*/ {
1785  // Combine this node's child with the given constant value.
1786  ChildNodeType* child = mNodes[i].getChild();
1787  assert(child);
1788  if (child) child->combine(value, valueIsActive, op);
1789  }
1790  }
1791 }
1792 
1793 
1795 
1796 
1797 template<typename ChildT, Index Log2Dim>
1798 template<typename CombineOp>
1799 inline void
1801  CombineOp& op)
1802 {
1804 
1805  for (Index i = 0; i < NUM_VALUES; ++i) {
1806  if (other0.isChildMaskOff(i) && other1.isChildMaskOff(i)) {
1807  op(args.setARef(other0.mNodes[i].getValue())
1808  .setAIsActive(other0.isValueMaskOn(i))
1809  .setBRef(other1.mNodes[i].getValue())
1810  .setBIsActive(other1.isValueMaskOn(i)));
1811  // Replace child i with a constant value.
1812  this->makeChildNodeEmpty(i, args.result());
1813  mValueMask.set(i, args.resultIsActive());
1814  } else {
1815  ChildNodeType* otherChild = other0.isChildMaskOn(i)
1816  ? other0.mNodes[i].getChild() : other1.mNodes[i].getChild();
1817  assert(otherChild);
1818  if (this->isChildMaskOff(i)) {
1819  // Add a new child with the same coordinates, etc.
1820  // as the other node's child.
1821  mChildMask.setOn(i);
1822  mValueMask.setOff(i);
1823  mNodes[i].setChild(new ChildNodeType(otherChild->getOrigin(),
1824  mNodes[i].getValue()));
1825  }
1826 
1827  if (other0.isChildMaskOff(i)) {
1828  // Combine node1's child with node0's constant value
1829  // and write the result into child i.
1830  mNodes[i].getChild()->combine2(other0.mNodes[i].getValue(),
1831  *other1.mNodes[i].getChild(), other0.isValueMaskOn(i), op);
1832  } else if (other1.isChildMaskOff(i)) {
1833  // Combine node0's child with node1's constant value
1834  // and write the result into child i.
1835  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
1836  other1.mNodes[i].getValue(), other1.isValueMaskOn(i), op);
1837  } else {
1838  // Combine node0's child with node1's child
1839  // and write the result into child i.
1840  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
1841  *other1.mNodes[i].getChild(), op);
1842  }
1843  }
1844  }
1845 }
1846 
1847 
1848 template<typename ChildT, Index Log2Dim>
1849 template<typename CombineOp>
1850 inline void
1852  bool valueIsActive, CombineOp& op)
1853 {
1855 
1856  for (Index i = 0; i < NUM_VALUES; ++i) {
1857  if (other.isChildMaskOff(i)) {
1858  op(args.setARef(value)
1859  .setAIsActive(valueIsActive)
1860  .setBRef(other.mNodes[i].getValue())
1861  .setBIsActive(other.isValueMaskOn(i)));
1862  // Replace child i with a constant value.
1863  this->makeChildNodeEmpty(i, args.result());
1864  mValueMask.set(i, args.resultIsActive());
1865  } else {
1866  ChildNodeType* otherChild = other.mNodes[i].getChild();
1867  assert(otherChild);
1868  if (this->isChildMaskOff(i)) {
1869  // Add a new child with the same coordinates, etc.
1870  // as the other node's child.
1872  mChildMask.setOn(i);
1873  mValueMask.setOff(i);
1874  mNodes[i].setChild(new ChildNodeType(*otherChild));
1875  }
1876  // Combine the other node's child with a constant value
1877  // and write the result into child i.
1878  mNodes[i].getChild()->combine2(value, *otherChild, valueIsActive, op);
1879  }
1880  }
1881 }
1882 
1883 
1884 template<typename ChildT, Index Log2Dim>
1885 template<typename CombineOp>
1886 inline void
1888  bool valueIsActive, CombineOp& op)
1889 {
1891 
1892  for (Index i = 0; i < NUM_VALUES; ++i) {
1893  if (other.isChildMaskOff(i)) {
1894  op(args.setARef(other.mNodes[i].getValue())
1895  .setAIsActive(other.isValueMaskOn(i))
1896  .setBRef(value)
1897  .setBIsActive(valueIsActive));
1898  // Replace child i with a constant value.
1899  this->makeChildNodeEmpty(i, args.result());
1900  mValueMask.set(i, args.resultIsActive());
1901  } else {
1902  ChildNodeType* otherChild = other.mNodes[i].getChild();
1903  assert(otherChild);
1904  if (this->isChildMaskOff(i)) {
1905  // Add a new child with the same coordinates, etc.
1906  // as the other node's child.
1907  mChildMask.setOn(i);
1908  mValueMask.setOff(i);
1909  mNodes[i].setChild(new ChildNodeType(otherChild->getOrigin(),
1910  mNodes[i].getValue()));
1911  }
1912  // Combine the other node's child with a constant value
1913  // and write the result into child i.
1914  mNodes[i].getChild()->combine2(*otherChild, value, valueIsActive, op);
1915  }
1916  }
1917 }
1918 
1919 
1921 
1922 
1923 template<typename ChildT, Index Log2Dim>
1924 template<typename BBoxOp>
1925 inline void
1927 {
1928  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) {
1929 #ifdef _MSC_VER
1930  op.operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
1931 #else
1932  op.template operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
1933 #endif
1934  }
1935  if (op.template descent<LEVEL>()) {
1936  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) i->visitActiveBBox(op);
1937  } else {
1938  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) {
1939 #ifdef _MSC_VER
1940  op.operator()<LEVEL>(i->getNodeBoundingBox());
1941 #else
1942  op.template operator()<LEVEL>(i->getNodeBoundingBox());
1943 #endif
1944  }
1945  }
1946 }
1947 
1948 
1949 template<typename ChildT, Index Log2Dim>
1950 template<typename VisitorOp>
1951 inline void
1953 {
1954  doVisit<InternalNode, VisitorOp, ChildAllIter>(*this, op);
1955 }
1956 
1957 
1958 template<typename ChildT, Index Log2Dim>
1959 template<typename VisitorOp>
1960 inline void
1962 {
1963  doVisit<const InternalNode, VisitorOp, ChildAllCIter>(*this, op);
1964 }
1965 
1966 
1967 template<typename ChildT, Index Log2Dim>
1968 template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
1969 inline void
1970 InternalNode<ChildT, Log2Dim>::doVisit(NodeT& self, VisitorOp& op)
1971 {
1972  typename NodeT::ValueType val;
1973  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
1974  if (op(iter)) continue;
1975  if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
1976  child->visit(op);
1977  }
1978  }
1979 }
1980 
1981 
1983 
1984 
1985 template<typename ChildT, Index Log2Dim>
1986 template<typename OtherNodeType, typename VisitorOp>
1987 inline void
1988 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op)
1989 {
1990  doVisit2Node<InternalNode, OtherNodeType, VisitorOp, ChildAllIter,
1991  typename OtherNodeType::ChildAllIter>(*this, other, op);
1992 }
1993 
1994 
1995 template<typename ChildT, Index Log2Dim>
1996 template<typename OtherNodeType, typename VisitorOp>
1997 inline void
1998 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op) const
1999 {
2000  doVisit2Node<const InternalNode, OtherNodeType, VisitorOp, ChildAllCIter,
2001  typename OtherNodeType::ChildAllCIter>(*this, other, op);
2002 }
2003 
2004 
2005 template<typename ChildT, Index Log2Dim>
2006 template<
2007  typename NodeT,
2008  typename OtherNodeT,
2009  typename VisitorOp,
2010  typename ChildAllIterT,
2011  typename OtherChildAllIterT>
2012 inline void
2013 InternalNode<ChildT, Log2Dim>::doVisit2Node(NodeT& self, OtherNodeT& other, VisitorOp& op)
2014 {
2015  // Allow the two nodes to have different ValueTypes, but not different dimensions.
2016  BOOST_STATIC_ASSERT(OtherNodeT::NUM_VALUES == NodeT::NUM_VALUES);
2017  BOOST_STATIC_ASSERT(OtherNodeT::LEVEL == NodeT::LEVEL);
2018 
2019  typename NodeT::ValueType val;
2020  typename OtherNodeT::ValueType otherVal;
2021 
2022  ChildAllIterT iter = self.beginChildAll();
2023  OtherChildAllIterT otherIter = other.beginChildAll();
2024 
2025  for ( ; iter && otherIter; ++iter, ++otherIter)
2026  {
2027  const size_t skipBranch = static_cast<size_t>(op(iter, otherIter));
2028 
2029  typename ChildAllIterT::ChildNodeType* child =
2030  (skipBranch & 1U) ? NULL : iter.probeChild(val);
2031  typename OtherChildAllIterT::ChildNodeType* otherChild =
2032  (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
2033 
2034  if (child != NULL && otherChild != NULL) {
2035  child->visit2Node(*otherChild, op);
2036  } else if (child != NULL) {
2037  child->visit2(otherIter, op);
2038  } else if (otherChild != NULL) {
2039  otherChild->visit2(iter, op, /*otherIsLHS=*/true);
2040  }
2041  }
2042 }
2043 
2044 
2046 
2047 
2048 template<typename ChildT, Index Log2Dim>
2049 template<typename OtherChildAllIterType, typename VisitorOp>
2050 inline void
2051 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
2052  VisitorOp& op, bool otherIsLHS)
2053 {
2054  doVisit2<InternalNode, VisitorOp, ChildAllIter, OtherChildAllIterType>(
2055  *this, otherIter, op, otherIsLHS);
2056 }
2057 
2058 
2059 template<typename ChildT, Index Log2Dim>
2060 template<typename OtherChildAllIterType, typename VisitorOp>
2061 inline void
2062 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
2063  VisitorOp& op, bool otherIsLHS) const
2064 {
2065  doVisit2<const InternalNode, VisitorOp, ChildAllCIter, OtherChildAllIterType>(
2066  *this, otherIter, op, otherIsLHS);
2067 }
2068 
2069 
2070 template<typename ChildT, Index Log2Dim>
2071 template<typename NodeT, typename VisitorOp, typename ChildAllIterT, typename OtherChildAllIterT>
2072 inline void
2073 InternalNode<ChildT, Log2Dim>::doVisit2(NodeT& self, OtherChildAllIterT& otherIter,
2074  VisitorOp& op, bool otherIsLHS)
2075 {
2076  if (!otherIter) return;
2077 
2078  const size_t skipBitMask = (otherIsLHS ? 2U : 1U);
2079 
2080  typename NodeT::ValueType val;
2081  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2082  const size_t skipBranch = static_cast<size_t>(
2083  otherIsLHS ? op(otherIter, iter) : op(iter, otherIter));
2084 
2085  typename ChildAllIterT::ChildNodeType* child =
2086  (skipBranch & skipBitMask) ? NULL : iter.probeChild(val);
2087 
2088  if (child != NULL) child->visit2(otherIter, op, otherIsLHS);
2089  }
2090 }
2091 
2092 
2094 
2095 
2096 template<typename ChildT, Index Log2Dim>
2097 inline void
2098 InternalNode<ChildT, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
2099 {
2100  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2101  iter->writeBuffers(os, toHalf);
2102  }
2103 }
2104 
2105 
2106 template<typename ChildT, Index Log2Dim>
2107 inline void
2108 InternalNode<ChildT, Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
2109 {
2110  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2111  iter->readBuffers(is, fromHalf);
2112  }
2113 }
2114 
2115 
2117 
2118 
2119 template<typename ChildT, Index Log2Dim>
2120 void
2122 {
2123  dims.push_back(Log2Dim);
2124  ChildNodeType::getNodeLog2Dims(dims);
2125 }
2126 
2127 
2128 template<typename ChildT, Index Log2Dim>
2129 inline void
2131 {
2132  assert(n<(1<<3*Log2Dim));
2133  xyz.setX(n >> 2*Log2Dim);
2134  n &= ((1<<2*Log2Dim)-1);
2135  xyz.setY(n >> Log2Dim);
2136  xyz.setZ(n & ((1<<Log2Dim)-1));
2137 }
2138 
2139 
2140 template<typename ChildT, Index Log2Dim>
2141 inline Index
2143 {
2144  return (((xyz[0]&DIM-1u)>>ChildNodeType::TOTAL)<<2*Log2Dim)
2145  + (((xyz[1]&DIM-1u)>>ChildNodeType::TOTAL)<< Log2Dim)
2146  + ((xyz[2]&DIM-1u)>>ChildNodeType::TOTAL);
2147 }
2148 
2149 
2150 template<typename ChildT, Index Log2Dim>
2151 inline Coord
2153 {
2154  Coord local;
2155  this->offset2coord(n, local);
2156  local <<= ChildT::TOTAL;
2157  return local + this->getOrigin();
2158 }
2159 
2160 
2162 
2163 
2164 template<typename ChildT, Index Log2Dim>
2165 inline void
2167  const ValueType& newBackground)
2168 {
2169  for (Index i = 0; i < NUM_VALUES; ++i) {
2170  if (this->isChildMaskOn(i)) {
2171  mNodes[i].getChild()->resetBackground(oldBackground, newBackground);
2172  } else {
2173  if (math::isApproxEqual(mNodes[i].getValue(), oldBackground)) {
2174  mNodes[i].setValue(newBackground);
2175  } else if (math::isApproxEqual(mNodes[i].getValue(), negative(oldBackground))) {
2176  mNodes[i].setValue(negative(newBackground));
2177  }
2178  }
2179  }
2180 }
2181 
2182 
2183 template<typename ChildT, Index Log2Dim>
2184 template<typename OtherChildNodeType, Index OtherLog2Dim>
2185 inline bool
2188 {
2189  if (Log2Dim != OtherLog2Dim || mChildMask != other->mChildMask ||
2190  mValueMask != other->mValueMask) return false;
2191  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2192  if (!iter->hasSameTopology(other->mNodes[iter.pos()].getChild())) return false;
2193  }
2194  return true;
2195 }
2196 
2197 
2198 template<typename ChildT, Index Log2Dim>
2199 inline void
2201 {
2202  assert(child);
2203  if (this->isChildMaskOn(i)) {
2204  delete mNodes[i].getChild();
2205  } else {
2206  mChildMask.setOn(i);
2207  mValueMask.setOff(i);
2208  }
2209  mNodes[i].setChild(child);
2210 }
2211 
2212 
2213 template<typename ChildT, Index Log2Dim>
2214 inline ChildT*
2216 {
2217  if (this->isChildMaskOff(i)) {
2218  mNodes[i].setValue(value);
2219  return NULL;
2220  }
2221  ChildNodeType* child = mNodes[i].getChild();
2222  mChildMask.setOff(i);
2223  mNodes[i].setValue(value);
2224  return child;
2225 }
2226 
2227 
2228 template<typename ChildT, Index Log2Dim>
2229 inline void
2231 {
2232  delete this->unsetChildNode(n, value);
2233 }
2234 
2235 template<typename ChildT, Index Log2Dim>
2236 inline ChildT*
2238 {
2239  return (this->isChildMaskOn(n) ? mNodes[n].getChild() : NULL);
2240 }
2241 
2242 
2243 template<typename ChildT, Index Log2Dim>
2244 inline const ChildT*
2246 {
2247  return (this->isChildMaskOn(n) ? mNodes[n].getChild() : NULL);
2248 }
2249 
2250 } // namespace tree
2251 } // namespace OPENVDB_VERSION_NAME
2252 } // namespace openvdb
2253 
2254 #endif // OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
2255 
2256 // Copyright (c) 2012 DreamWorks Animation LLC
2257 // All rights reserved. This software is distributed under the
2258 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )