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