35 #ifndef OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
36 #define OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
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>
43 #include <openvdb/math/Math.h>
44 #include <openvdb/version.h>
45 #include <openvdb/Types.h>
56 template<
typename _ChildNodeType, Index Log2Dim>
62 typedef typename ChildNodeType::ValueType
ValueType;
68 TOTAL = Log2Dim + ChildNodeType::TOTAL,
70 NUM_VALUES = 1 << (3 * Log2Dim),
71 LEVEL = 1 + ChildNodeType::LEVEL;
73 NUM_VOXELS = uint64_t(1) << (3 * TOTAL);
77 template<
typename OtherValueType>
94 template<
typename OtherChildNodeType>
99 template<
typename OtherChildNodeType>
101 const ValueType& offValue,
const ValueType& onValue,
118 template<
typename NodeT,
typename ChildT,
typename MaskIterT,
typename TagT>
120 MaskIterT, ChildIter<NodeT, ChildT, MaskIterT, TagT>, NodeT, ChildT>
124 MaskIterT,
ChildIter<NodeT, ChildT, MaskIterT, TagT>, NodeT, ChildT>(iter, parent) {}
126 ChildT&
getItem(
Index pos)
const {
return *(this->parent().getChildNode(pos)); }
129 void setItem(
Index pos,
const ChildT& c)
const { this->parent().setChildNode(pos, &c); }
132 template<
typename NodeT,
typename ValueT,
typename MaskIterT,
typename TagT>
134 MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>
138 MaskIterT,
ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>(iter, parent) {}
140 const ValueT&
getItem(
Index pos)
const {
return this->parent().mNodes[pos].getValue(); }
143 void setItem(
Index pos,
const ValueT& v)
const { this->parent().mNodes[pos].setValue(v); }
146 template<
typename NodeT,
typename ChildT,
typename ValueT,
typename TagT>
148 MaskDenseIterator, DenseIter<NodeT, ChildT, ValueT, TagT>, NodeT, ChildT, ValueT>
159 child = this->parent().getChildNode(pos);
160 if (!child) value = this->parent().mNodes[pos].getValue();
161 return (child != NULL);
165 void setItem(
Index pos, ChildT* child)
const
167 this->parent().setChildNode(pos, child);
171 void unsetItem(
Index pos,
const ValueT& value)
const
173 this->parent().unsetChildNode(pos, value);
216 static void getNodeLog2Dims(std::vector<Index>& dims);
220 static void offset2coord(
Index n,
Coord& xyz);
229 Index64 onLeafVoxelCount()
const;
230 Index64 offLeafVoxelCount()
const;
237 void evalActiveVoxelBoundingBox(
CoordBBox& bbox)
const;
243 bool isEmpty()
const {
return mChildMask.isOff(); }
248 bool isConstant(ValueType& constValue,
bool& state,
249 const ValueType& tolerance = zeroVal<ValueType>())
const;
251 bool isInactive()
const {
return this->isChildMaskOff() && this->isValueMaskOff(); }
254 bool isValueOn(
const Coord& xyz)
const;
259 bool hasActiveTiles()
const;
261 const ValueType& getValue(
const Coord& xyz)
const;
262 bool probeValue(
const Coord& xyz, ValueType& value)
const;
270 const ValueType& getFirstValue()
const;
273 const ValueType& getLastValue()
const;
276 void setActiveState(
const Coord& xyz,
bool on);
279 void setValueOff(
const Coord& xyz);
281 void setValueOff(
const Coord& xyz,
const ValueType& value);
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);
292 void fill(
const CoordBBox& bbox,
const ValueType&,
bool active =
true);
298 template<
typename AccessorT>
299 const ValueType& getValueAndCache(
const Coord& xyz, AccessorT&)
const;
305 template<
typename AccessorT>
306 bool isValueOnAndCache(
const Coord& xyz, AccessorT&)
const;
312 template<
typename AccessorT>
313 void setValueAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
319 template<
typename AccessorT>
320 void setValueOnlyAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
327 template<
typename AccessorT>
328 void setValueOnSumAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
334 template<
typename AccessorT>
335 void setValueOffAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
341 template<
typename AccessorT>
342 void setActiveStateAndCache(
const Coord& xyz,
bool on, AccessorT&);
348 template<
typename AccessorT>
349 bool probeValueAndCache(
const Coord& xyz, ValueType& value, AccessorT&)
const;
357 template<
typename AccessorT>
358 Index getValueLevelAndCache(
const Coord& xyz, AccessorT&)
const;
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);
381 void signedFloodFill(
const ValueType& background);
389 void signedFloodFill(
const ValueType& outside,
const ValueType& inside);
396 void voxelizeActiveTiles();
402 void merge(
InternalNode& other,
const ValueType& background,
const ValueType& otherBackground);
416 template<
typename OtherChildNodeType>
419 template<
typename CombineOp>
421 template<
typename CombineOp>
422 void combine(
const ValueType& value,
bool valueIsActive, CombineOp&);
424 template<
typename 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&);
438 template<
typename BBoxOp>
void visitActiveBBox(BBoxOp&)
const;
440 template<
typename VisitorOp>
void visit(VisitorOp&);
441 template<
typename VisitorOp>
void visit(VisitorOp&)
const;
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;
458 template<
typename PruneOp>
void pruneOp(PruneOp&);
463 void prune(
const ValueType& tolerance = zeroVal<ValueType>());
467 void pruneInactive(
const ValueType&);
471 void pruneInactive();
479 LeafNodeType* touchLeaf(
const Coord& xyz);
483 LeafNodeType* probeLeaf(
const Coord& xyz);
486 const LeafNodeType* probeConstLeaf(
const Coord& xyz)
const;
490 template<
typename AccessorT>
491 LeafNodeType* touchLeafAndCache(
const Coord& xyz, AccessorT&);
495 template<
typename AccessorT>
496 LeafNodeType* probeLeafAndCache(
const Coord& xyz, AccessorT&);
499 template<
typename AccessorT>
500 const LeafNodeType* probeConstLeafAndCache(
const Coord& xyz, AccessorT&)
const;
504 void resetBackground(
const ValueType& oldBackground,
const ValueType& newBackground);
508 template<
typename OtherChildNodeType, Index OtherLog2Dim>
540 void makeChildNodeEmpty(
Index n,
const ValueType& value);
541 void setChildNode(
Index i, ChildNodeType* child);
542 ChildNodeType* unsetChildNode(
Index i,
const ValueType& value);
544 template<
typename NodeT,
typename VisitorOp,
typename ChildAllIterT>
545 static inline void doVisit(NodeT&, VisitorOp&);
547 template<
typename NodeT,
typename OtherNodeT,
typename VisitorOp,
548 typename ChildAllIterT,
typename OtherChildAllIterT>
549 static inline void doVisit2Node(NodeT&, OtherNodeT&, VisitorOp&);
551 template<
typename NodeT,
typename VisitorOp,
552 typename ChildAllIterT,
typename OtherChildAllIterT>
553 static inline void doVisit2(NodeT&, OtherChildAllIterT&, VisitorOp&,
bool otherIsLHS);
555 ChildNodeType* getChildNode(
Index n);
556 const ChildNodeType* getChildNode(
Index n)
const;
569 template<
typename ChildT, Index Log2Dim>
573 for (
Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
577 template<
typename ChildT, Index Log2Dim>
580 mOrigin(origin[0] & ~(DIM - 1),
581 origin[1] & ~(DIM - 1),
582 origin[2] & ~(DIM - 1))
589 template<
typename ChildT, Index Log2Dim>
592 mChildMask(other.mChildMask),
593 mValueMask(other.mValueMask),
594 mOrigin(other.mOrigin)
605 template<
typename ChildT, Index Log2Dim>
606 template<
typename OtherChildNodeType>
610 mChildMask(other.mChildMask),
611 mValueMask(other.mValueMask),
612 mOrigin(other.mOrigin)
624 template<
typename ChildT, Index Log2Dim>
625 template<
typename OtherChildNodeType>
629 mChildMask(other.mChildMask),
630 mValueMask(other.mValueMask),
631 mOrigin(other.mOrigin)
641 template<
typename ChildT, Index Log2Dim>
645 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
646 delete mNodes[iter.pos()].getChild();
654 template<
typename ChildT, Index Log2Dim>
658 if (ChildNodeType::getLevel() == 0)
return mChildMask.countOn();
660 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
661 sum += iter->leafCount();
667 template<
typename ChildT, Index Log2Dim>
672 if (ChildNodeType::getLevel() == 0)
return sum;
673 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
674 sum += iter->nonLeafCount();
680 template<
typename ChildT, Index Log2Dim>
685 for (
Index i = 0; i < NUM_VALUES; ++i) {
686 if (isChildMaskOff(i)) {
687 if (isValueMaskOn(i)) sum += ChildT::NUM_VOXELS;
689 sum += mNodes[i].getChild()->onVoxelCount();
696 template<
typename ChildT, Index Log2Dim>
701 for (
Index i = 0; i < NUM_VALUES; ++i) {
702 if (isChildMaskOff(i)) {
703 if (isValueMaskOff(i)) sum += ChildT::NUM_VOXELS;
705 sum += mNodes[i].getChild()->offVoxelCount();
712 template<
typename ChildT, Index Log2Dim>
717 for (
ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
718 sum += mNodes[iter.pos()].getChild()->onLeafVoxelCount();
724 template<
typename ChildT, Index Log2Dim>
729 for (
ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
730 sum += mNodes[iter.pos()].getChild()->offLeafVoxelCount();
736 template<
typename ChildT, Index Log2Dim>
741 + mValueMask.memUsage() +
sizeof(mOrigin);
742 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
743 sum += iter->memUsage();
749 template<
typename ChildT, Index Log2Dim>
753 if (bbox.
isInside(this->getNodeBoundingBox()))
return;
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);
769 template<
typename ChildT, Index Log2Dim>
770 template<
typename PruneOp>
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;
779 mChildMask.setOff(i);
780 mValueMask.set(i, op.state);
781 mNodes[i].setValue(op.value);
787 template<
typename ChildT, Index Log2Dim>
796 template<
typename ChildT, Index Log2Dim>
805 template<
typename ChildT, Index Log2Dim>
809 this->pruneInactive(this->getBackground());
812 template<
typename ChildT, Index Log2Dim>
813 inline typename ChildT::LeafNodeType*
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)));
820 mValueMask.setOff(n);
822 return mNodes[n].getChild()->touchLeaf(xyz);
825 template<
typename ChildT, Index Log2Dim>
826 template<
typename AccessorT>
827 inline typename ChildT::LeafNodeType*
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)));
834 mValueMask.setOff(n);
836 acc.insert(xyz, mNodes[n].getChild());
837 return mNodes[n].getChild()->touchLeafAndCache(xyz,acc);
840 template<
typename ChildT, Index Log2Dim>
841 inline typename ChildT::LeafNodeType*
844 const Index n = this->coord2offset(xyz);
845 return mChildMask.isOn(n) ? mNodes[n].getChild()->probeLeaf(xyz) : NULL;
848 template<
typename ChildT, Index Log2Dim>
849 inline const typename ChildT::LeafNodeType*
852 const Index n = this->coord2offset(xyz);
853 return mChildMask.isOn(n) ? mNodes[n].getChild()->probeConstLeaf(xyz) : NULL;
856 template<
typename ChildT, Index Log2Dim>
857 template<
typename AccessorT>
858 inline typename ChildT::LeafNodeType*
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);
867 template<
typename ChildT, Index Log2Dim>
868 template<
typename AccessorT>
869 inline const typename ChildT::LeafNodeType*
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);
882 template<
typename ChildT, Index Log2Dim>
887 bool allEqual =
true, firstValue =
true, valueState =
true;
889 for (
Index i = 0; allEqual && i < NUM_VALUES; ++i) {
890 if (this->isChildMaskOff(i)) {
895 valueState = isValueMaskOn(i);
896 value = mNodes[i].getValue();
898 allEqual = (isValueMaskOn(i) == valueState)
904 ValueType childValue = zeroVal<ValueType>();
905 bool isChildOn =
false;
906 if (mNodes[i].getChild()->isConstant(childValue, isChildOn, tolerance)) {
909 valueState = isChildOn;
912 allEqual = (isChildOn == valueState)
931 template<
typename ChildT, Index Log2Dim>
935 const Index n = this->coord2offset(xyz);
936 if (this->isChildMaskOff(n))
return this->isValueMaskOn(n);
937 return mNodes[n].getChild()->isValueOn(xyz);
940 template<
typename ChildT, Index Log2Dim>
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;
952 template<
typename ChildT, Index Log2Dim>
953 template<
typename AccessorT>
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);
964 template<
typename ChildT, Index Log2Dim>
965 inline const typename ChildT::ValueType&
968 const Index n = this->coord2offset(xyz);
969 return this->isChildMaskOff(n) ? mNodes[n].getValue()
970 : mNodes[n].getChild()->getValue(xyz);
973 template<
typename ChildT, Index Log2Dim>
974 template<
typename AccessorT>
975 inline const typename ChildT::ValueType&
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);
983 return mNodes[n].getValue();
987 template<
typename ChildT, Index Log2Dim>
991 const Index n = this->coord2offset(xyz);
992 return this->isChildMaskOff(n) ? LEVEL : mNodes[n].getChild()->getValueLevel(xyz);
995 template<
typename ChildT, Index Log2Dim>
996 template<
typename AccessorT>
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);
1009 template<
typename ChildT, Index Log2Dim>
1013 const Index n = this->coord2offset(xyz);
1014 if (this->isChildMaskOff(n)) {
1015 value = mNodes[n].getValue();
1016 return this->isValueMaskOn(n);
1018 return mNodes[n].getChild()->probeValue(xyz, value);
1021 template<
typename ChildT, Index Log2Dim>
1022 template<
typename AccessorT>
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);
1032 value = mNodes[n].getValue();
1033 return this->isValueMaskOn(n);
1037 template<
typename ChildT, Index Log2Dim>
1041 const Index n = this->coord2offset(xyz);
1042 bool hasChild = this->isChildMaskOn(n);
1043 if (!hasChild && this->isValueMaskOn(n)) {
1046 mChildMask.setOn(n);
1047 mValueMask.setOff(n);
1049 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(),
true));
1051 if (hasChild) mNodes[n].getChild()->setValueOff(xyz);
1055 template<
typename ChildT, Index Log2Dim>
1059 const Index n = this->coord2offset(xyz);
1060 bool hasChild = this->isChildMaskOn(n);
1061 if (!hasChild && !this->isValueMaskOn(n)) {
1064 mChildMask.setOn(n);
1065 mValueMask.setOff(n);
1067 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(),
false));
1069 if (hasChild) mNodes[n].getChild()->setValueOn(xyz);
1073 template<
typename ChildT, Index Log2Dim>
1078 bool hasChild = this->isChildMaskOn(n);
1080 const bool active = this->isValueMaskOn(n);
1085 mChildMask.setOn(n);
1086 mValueMask.setOff(n);
1088 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1091 if (hasChild) mNodes[n].getChild()->setValueOff(xyz, value);
1094 template<
typename ChildT, Index Log2Dim>
1095 template<
typename AccessorT>
1101 bool hasChild = this->isChildMaskOn(n);
1103 const bool active = this->isValueMaskOn(n);
1108 mChildMask.setOn(n);
1109 mValueMask.setOff(n);
1111 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1115 ChildT* child = mNodes[n].getChild();
1116 acc.insert(xyz, child);
1117 child->setValueOffAndCache(xyz, value, acc);
1122 template<
typename ChildT, Index Log2Dim>
1126 const Index n = this->coord2offset(xyz);
1127 bool hasChild = this->isChildMaskOn(n);
1129 const bool active = this->isValueMaskOn(n);
1134 mChildMask.setOn(n);
1135 mValueMask.setOff(n);
1137 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1140 if (hasChild) mNodes[n].getChild()->setValueOn(xyz, value);
1143 template<
typename ChildT, Index Log2Dim>
1144 template<
typename AccessorT>
1149 const Index n = this->coord2offset(xyz);
1150 bool hasChild = this->isChildMaskOn(n);
1152 const bool active = this->isValueMaskOn(n);
1157 mChildMask.setOn(n);
1158 mValueMask.setOff(n);
1160 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1164 acc.insert(xyz, mNodes[n].getChild());
1165 mNodes[n].getChild()->setValueAndCache(xyz, value, acc);
1170 template<
typename ChildT, Index Log2Dim>
1174 const Index n = this->coord2offset(xyz);
1175 bool hasChild = this->isChildMaskOn(n);
1179 const bool active = this->isValueMaskOn(n);
1180 mChildMask.setOn(n);
1181 mValueMask.setOff(n);
1183 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1185 if (hasChild) mNodes[n].getChild()->setValueOnly(xyz, value);
1188 template<
typename ChildT, Index Log2Dim>
1189 template<
typename AccessorT>
1194 const Index n = this->coord2offset(xyz);
1195 bool hasChild = this->isChildMaskOn(n);
1199 const bool active = this->isValueMaskOn(n);
1200 mChildMask.setOn(n);
1201 mValueMask.setOff(n);
1203 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1206 acc.insert(xyz, mNodes[n].getChild());
1207 mNodes[n].getChild()->setValueOnlyAndCache(xyz, value, acc);
1212 template<
typename ChildT, Index Log2Dim>
1216 const Index n = this->coord2offset(xyz);
1217 bool hasChild = this->isChildMaskOn(n);
1219 if (on != this->isValueMaskOn(n)) {
1222 mChildMask.setOn(n);
1223 mValueMask.setOff(n);
1224 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1229 if (hasChild) mNodes[n].getChild()->setActiveState(xyz, on);
1232 template<
typename ChildT, Index Log2Dim>
1233 template<
typename AccessorT>
1237 const Index n = this->coord2offset(xyz);
1238 bool hasChild = this->isChildMaskOn(n);
1240 if (on != this->isValueMaskOn(n)) {
1243 mChildMask.setOn(n);
1244 mValueMask.setOff(n);
1245 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1251 ChildT* child = mNodes[n].getChild();
1252 acc.insert(xyz, child);
1253 child->setActiveStateAndCache(xyz, on, acc);
1258 template<
typename ChildT, Index Log2Dim>
1262 mValueMask = !mChildMask;
1263 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1264 mNodes[iter.pos()].getChild()->setValuesOn();
1269 template<
typename ChildT, Index Log2Dim>
1274 bool hasChild = this->isChildMaskOn(n);
1276 const bool active = this->isValueMaskOn(n);
1277 if (!active || (mNodes[n].getValue() > value)) {
1281 mChildMask.setOn(n);
1282 mValueMask.setOff(n);
1284 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1287 if (hasChild) mNodes[n].getChild()->setValueOnMin(xyz, value);
1291 template<
typename ChildT, Index Log2Dim>
1296 bool hasChild = this->isChildMaskOn(n);
1298 const bool active = this->isValueMaskOn(n);
1299 if (!active || (value > mNodes[n].getValue())) {
1303 mChildMask.setOn(n);
1304 mValueMask.setOff(n);
1306 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1309 if (hasChild) mNodes[n].getChild()->setValueOnMax(xyz, value);
1313 template<
typename ChildT, Index Log2Dim>
1318 bool hasChild = this->isChildMaskOn(n);
1320 const bool active = this->isValueMaskOn(n);
1324 mChildMask.setOn(n);
1325 mValueMask.setOff(n);
1327 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1330 if (hasChild) mNodes[n].getChild()->setValueOnSum(xyz, addend);
1333 template<
typename ChildT, Index Log2Dim>
1334 template<
typename AccessorT>
1337 const ValueType& addend, AccessorT& acc)
1339 const Index n = this->coord2offset(xyz);
1340 bool hasChild = this->isChildMaskOn(n);
1342 const bool active = this->isValueMaskOn(n);
1346 mChildMask.setOn(n);
1347 mValueMask.setOff(n);
1349 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1353 acc.insert(xyz, mNodes[n].getChild());
1354 mNodes[n].getChild()->setValueOnSumAndCache(xyz, addend, acc);
1362 template<
typename ChildT, Index Log2Dim>
1366 Coord xyz, tileMin, tileMax;
1367 for (
int x = bbox.
min().
x(); x <= bbox.
max().
x(); x = tileMax.
x() + 1) {
1369 for (
int y = bbox.
min().
y(); y <= bbox.
max().
y(); y = tileMax.
y() + 1) {
1371 for (
int z = bbox.
min().
z(); z <= bbox.
max().
z(); z = tileMax.
z() + 1) {
1375 const Index n = this->coord2offset(xyz);
1376 tileMin = this->offset2globalCoord(n);
1377 tileMax = tileMin.
offsetBy(ChildT::DIM - 1);
1383 ChildT* child = NULL;
1384 if (this->isChildMaskOff(n)) {
1387 child =
new ChildT(xyz, mNodes[n].getValue(), this->isValueMaskOn(n));
1388 mChildMask.setOn(n);
1389 mValueMask.setOff(n);
1390 mNodes[n].setChild(child);
1392 child = mNodes[n].getChild();
1405 this->makeChildNodeEmpty(n, value);
1406 mValueMask.set(n, active);
1417 template<
typename ChildT, Index Log2Dim>
1421 mChildMask.save(os);
1422 mValueMask.save(os);
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);
1435 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1436 iter->writeTopology(os, toHalf);
1441 template<
typename ChildT, Index Log2Dim>
1445 mChildMask.load(is);
1446 mValueMask.load(is);
1449 for (
Index i = 0; i < NUM_VALUES; ++i) {
1450 if (this->isChildMaskOn(i)) {
1452 new ChildNodeType(offset2globalCoord(i), zeroVal<ValueType>());
1453 mNodes[i].setChild(child);
1454 child->readTopology(is);
1457 is.read(reinterpret_cast<char*>(&value),
sizeof(
ValueType));
1458 mNodes[i].setValue(value);
1462 const bool oldVersion =
1464 const Index numValues = (oldVersion ? mChildMask.countOff() : NUM_VALUES);
1468 boost::shared_array<ValueType> values(
new ValueType[numValues]);
1474 for (
ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
1475 mNodes[iter.pos()].setValue(values[n++]);
1477 assert(n == numValues);
1479 for (
ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
1480 mNodes[iter.pos()].setValue(values[iter.pos()]);
1485 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1487 mNodes[iter.pos()].setChild(child);
1488 child->readTopology(is, fromHalf);
1497 template<
typename ChildT, Index Log2Dim>
1498 inline const typename ChildT::ValueType&
1501 return (this->isChildMaskOn(0) ? mNodes[0].getChild()->getFirstValue() : mNodes[0].getValue());
1505 template<
typename ChildT, Index Log2Dim>
1506 inline const typename ChildT::ValueType&
1509 const Index n = NUM_VALUES - 1;
1510 return (this->isChildMaskOn(n) ? mNodes[n].getChild()->getLastValue() : mNodes[n].getValue());
1515 template<
typename ChildT, Index Log2Dim>
1519 this->signedFloodFill(background,
negative(background));
1522 template<
typename ChildT, Index Log2Dim>
1528 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1529 iter->signedFloodFill(outsideValue, insideValue);
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);
1537 if (isChildMaskOn(x00)) {
1541 for (
Index y = 0; y != (1 << Log2Dim); ++y) {
1542 const Index xy0 = x00 + (y << Log2Dim);
1543 if (isChildMaskOn(xy0)) {
1547 for (
Index z = 0; z != (1 << Log2Dim); ++z) {
1548 const Index xyz = xy0 + z;
1549 if (isChildMaskOn(xyz)) {
1552 mNodes[xyz].setValue(zInside ? insideValue : outsideValue);
1559 for (
Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(v);
1564 template<
typename ChildT, Index Log2Dim>
1568 for (
Index i = 0; i < NUM_VALUES; ++i) {
1569 if (this->isChildMaskOn(i)) {
1570 mNodes[i].getChild()->negate();
1572 mNodes[i].setValue(
negative(mNodes[i].getValue()));
1578 template<
typename ChildT, Index Log2Dim>
1582 for (
ValueOnIter iter = this->beginValueOn(); iter; ++iter) {
1583 const Index n = iter.pos();
1585 mValueMask.setOff(n);
1586 mChildMask.setOn(n);
1587 mNodes[n].setChild(child);
1589 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) iter->voxelizeActiveTiles();
1592 template<
typename ChildT, Index Log2Dim>
1598 const Index n = iter.pos();
1599 if (mChildMask.isOff(n)) {
1604 child->resetBackground(otherBackground, background);
1605 mChildMask.setOn(n);
1606 mValueMask.setOff(n);
1607 mNodes[n].setChild(child);
1609 mNodes[n].getChild()->merge(*iter, background, otherBackground);
1615 const Index n = iter.pos();
1616 if (mChildMask.isOff(n) && mValueMask.isOff(n)) {
1617 mNodes[n].setValue(iter.getValue());
1618 mValueMask.setOn(n);
1624 template<
typename ChildT, Index Log2Dim>
1625 template<
typename OtherChildT>
1632 for (OtherChildIter iter = other.
cbeginChildOn(); iter; ++iter) {
1634 if (mChildMask.isOn(i)) {
1635 mNodes[i].getChild()->topologyUnion(*iter);
1638 if (mValueMask.isOn(i)) {
1639 mValueMask.isOff(i);
1640 child->setValuesOn();
1642 mChildMask.setOn(i);
1643 mNodes[i].setChild(child);
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)) {
1651 mValueMask.setOn(i);
1659 template<
typename ChildT, Index Log2Dim>
1660 template<
typename CombineOp>
1664 const ValueType zero = zeroVal<ValueType>();
1668 for (
Index i = 0; i < NUM_VALUES; ++i) {
1672 op(args.setARef(mNodes[i].getValue())
1673 .setAIsActive(isValueMaskOn(i))
1674 .setBRef(other.
mNodes[i].getValue())
1676 mNodes[i].setValue(args.result());
1677 mValueMask.set(i, args.resultIsActive());
1685 }
else if (this->isChildMaskOff(i) && other.
isChildMaskOn(i)) {
1694 child->combine(mNodes[i].getValue(), isValueMaskOn(i), swappedOp);
1698 other.
mNodes[i].setValue(zero);
1699 mChildMask.setOn(i);
1700 mValueMask.setOff(i);
1701 mNodes[i].setChild(child);
1707 *child = mNodes[i].getChild(),
1708 *otherChild = other.
mNodes[i].getChild();
1711 if (child && otherChild) {
1712 child->combine(*otherChild, op);
1719 template<
typename ChildT, Index Log2Dim>
1720 template<
typename CombineOp>
1726 for (
Index i = 0; i < NUM_VALUES; ++i) {
1727 if (this->isChildMaskOff(i)) {
1729 op(args.
setARef(mNodes[i].getValue())
1730 .setAIsActive(isValueMaskOn(i))
1732 .setBIsActive(valueIsActive));
1733 mNodes[i].setValue(args.
result());
1739 if (child) child->combine(value, valueIsActive, op);
1748 template<
typename ChildT, Index Log2Dim>
1749 template<
typename CombineOp>
1756 for (
Index i = 0; i < NUM_VALUES; ++i) {
1760 .setBRef(other1.
mNodes[i].getValue())
1763 this->makeChildNodeEmpty(i, args.
result());
1767 ? other0.
mNodes[i].getChild() : other1.
mNodes[i].getChild();
1769 if (this->isChildMaskOff(i)) {
1772 mChildMask.setOn(i);
1773 mValueMask.setOff(i);
1774 mNodes[i].setChild(
new ChildNodeType(otherChild->getOrigin(),
1775 mNodes[i].getValue()));
1781 mNodes[i].getChild()->combine2(other0.
mNodes[i].getValue(),
1786 mNodes[i].getChild()->combine2(*other0.
mNodes[i].getChild(),
1791 mNodes[i].getChild()->combine2(*other0.
mNodes[i].getChild(),
1792 *other1.
mNodes[i].getChild(), op);
1799 template<
typename ChildT, Index Log2Dim>
1800 template<
typename CombineOp>
1803 bool valueIsActive, CombineOp& op)
1807 for (
Index i = 0; i < NUM_VALUES; ++i) {
1810 .setAIsActive(valueIsActive)
1811 .setBRef(other.
mNodes[i].getValue())
1814 this->makeChildNodeEmpty(i, args.
result());
1819 if (this->isChildMaskOff(i)) {
1823 mChildMask.setOn(i);
1824 mValueMask.setOff(i);
1829 mNodes[i].getChild()->combine2(value, *otherChild, valueIsActive, op);
1835 template<
typename ChildT, Index Log2Dim>
1836 template<
typename CombineOp>
1839 bool valueIsActive, CombineOp& op)
1843 for (
Index i = 0; i < NUM_VALUES; ++i) {
1848 .setBIsActive(valueIsActive));
1850 this->makeChildNodeEmpty(i, args.
result());
1855 if (this->isChildMaskOff(i)) {
1858 mChildMask.setOn(i);
1859 mValueMask.setOff(i);
1860 mNodes[i].setChild(
new ChildNodeType(otherChild->getOrigin(),
1861 mNodes[i].getValue()));
1865 mNodes[i].getChild()->combine2(*otherChild, value, valueIsActive, op);
1874 template<
typename ChildT, Index Log2Dim>
1875 template<
typename BBoxOp>
1886 if (op.template descent<LEVEL>()) {
1887 for (
ChildOnCIter i = this->cbeginChildOn(); i; ++i) i->visitActiveBBox(op);
1891 op.operator()<LEVEL>(i->getNodeBoundingBox());
1893 op.template operator()<LEVEL>(i->getNodeBoundingBox());
1900 template<
typename ChildT, Index Log2Dim>
1901 template<
typename VisitorOp>
1905 doVisit<InternalNode, VisitorOp, ChildAllIter>(*
this, op);
1909 template<
typename ChildT, Index Log2Dim>
1910 template<
typename VisitorOp>
1914 doVisit<const InternalNode, VisitorOp, ChildAllCIter>(*
this, op);
1918 template<
typename ChildT, Index Log2Dim>
1919 template<
typename NodeT,
typename VisitorOp,
typename ChildAllIterT>
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)) {
1936 template<
typename ChildT, Index Log2Dim>
1937 template<
typename OtherNodeType,
typename VisitorOp>
1942 typename OtherNodeType::ChildAllIter>(*
this, other, op);
1946 template<
typename ChildT, Index Log2Dim>
1947 template<
typename OtherNodeType,
typename VisitorOp>
1952 typename OtherNodeType::ChildAllCIter>(*
this, other, op);
1956 template<
typename ChildT, Index Log2Dim>
1959 typename OtherNodeT,
1961 typename ChildAllIterT,
1962 typename OtherChildAllIterT>
1967 BOOST_STATIC_ASSERT(OtherNodeT::NUM_VALUES == NodeT::NUM_VALUES);
1968 BOOST_STATIC_ASSERT(OtherNodeT::LEVEL == NodeT::LEVEL);
1970 typename NodeT::ValueType val;
1971 typename OtherNodeT::ValueType otherVal;
1973 ChildAllIterT iter =
self.beginChildAll();
1974 OtherChildAllIterT otherIter = other.beginChildAll();
1976 for ( ; iter && otherIter; ++iter, ++otherIter)
1978 const size_t skipBranch =
static_cast<size_t>(op(iter, otherIter));
1980 typename ChildAllIterT::ChildNodeType* child =
1981 (skipBranch & 1U) ? NULL : iter.probeChild(val);
1982 typename OtherChildAllIterT::ChildNodeType* otherChild =
1983 (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
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,
true);
1999 template<
typename ChildT, Index Log2Dim>
2000 template<
typename OtherChildAllIterType,
typename VisitorOp>
2003 VisitorOp& op,
bool otherIsLHS)
2005 doVisit2<InternalNode, VisitorOp, ChildAllIter, OtherChildAllIterType>(
2006 *
this, otherIter, op, otherIsLHS);
2010 template<
typename ChildT, Index Log2Dim>
2011 template<
typename OtherChildAllIterType,
typename VisitorOp>
2014 VisitorOp& op,
bool otherIsLHS)
const
2016 doVisit2<const InternalNode, VisitorOp, ChildAllCIter, OtherChildAllIterType>(
2017 *
this, otherIter, op, otherIsLHS);
2021 template<
typename ChildT, Index Log2Dim>
2022 template<
typename NodeT,
typename VisitorOp,
typename ChildAllIterT,
typename OtherChildAllIterT>
2025 VisitorOp& op,
bool otherIsLHS)
2027 if (!otherIter)
return;
2029 const size_t skipBitMask = (otherIsLHS ? 2U : 1U);
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));
2036 typename ChildAllIterT::ChildNodeType* child =
2037 (skipBranch & skipBitMask) ? NULL : iter.probeChild(val);
2039 if (child != NULL) child->visit2(otherIter, op, otherIsLHS);
2047 template<
typename ChildT, Index Log2Dim>
2051 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2052 iter->writeBuffers(os, toHalf);
2057 template<
typename ChildT, Index Log2Dim>
2061 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2062 iter->readBuffers(is, fromHalf);
2070 template<
typename ChildT, Index Log2Dim>
2074 dims.push_back(Log2Dim);
2075 ChildNodeType::getNodeLog2Dims(dims);
2079 template<
typename ChildT, Index Log2Dim>
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));
2091 template<
typename ChildT, Index Log2Dim>
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);
2101 template<
typename ChildT, Index Log2Dim>
2106 this->offset2coord(n, local);
2107 local <<= ChildT::TOTAL;
2108 return local + this->getOrigin();
2115 template<
typename ChildT, Index Log2Dim>
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)) {
2126 mNodes[i].setValue(newBackground);
2128 mNodes[i].setValue(
negative(newBackground));
2135 template<
typename ChildT, Index Log2Dim>
2136 template<
typename OtherChildNodeType, Index OtherLog2Dim>
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;
2150 template<
typename ChildT, Index Log2Dim>
2155 if (this->isChildMaskOn(i)) {
2156 delete mNodes[i].getChild();
2158 mChildMask.setOn(i);
2159 mValueMask.setOff(i);
2161 mNodes[i].setChild(child);
2165 template<
typename ChildT, Index Log2Dim>
2169 if (this->isChildMaskOff(i)) {
2170 mNodes[i].setValue(value);
2174 mChildMask.setOff(i);
2175 mNodes[i].setValue(value);
2180 template<
typename ChildT, Index Log2Dim>
2184 delete this->unsetChildNode(n, value);
2187 template<
typename ChildT, Index Log2Dim>
2191 return (this->isChildMaskOn(n) ? mNodes[n].getChild() : NULL);
2195 template<
typename ChildT, Index Log2Dim>
2196 inline const ChildT*
2199 return (this->isChildMaskOn(n) ? mNodes[n].getChild() : NULL);
2206 #endif // OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED