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;
356 template<
typename AccessorT>
359 template<
typename ProbeType,
typename AccessorT>
362 template<
bool State,
bool Level,
typename AccessorT>
371 template<
typename AccessorT>
372 Index getValueLevelAndCache(
const Coord& xyz, AccessorT&)
const;
380 template<
typename AccessorT>
386 void writeTopology(std::ostream&,
bool toHalf =
false)
const;
387 void readTopology(std::istream&,
bool fromHalf =
false);
388 void writeBuffers(std::ostream&,
bool toHalf =
false)
const;
389 void readBuffers(std::istream&,
bool fromHalf =
false);
394 void signedFloodFill(
const ValueType& background);
399 void voxelizeActiveTiles();
405 void merge(
InternalNode& other,
const ValueType& background,
const ValueType& otherBackground);
415 template<
typename OtherChildNodeType>
418 template<
typename CombineOp>
420 template<
typename CombineOp>
421 void combine(
const ValueType& value,
bool valueIsActive, CombineOp&);
423 template<
typename CombineOp>
425 template<
typename CombineOp>
426 void combine2(
const ValueType& value,
const InternalNode& other,
427 bool valueIsActive, CombineOp&);
428 template<
typename CombineOp>
429 void combine2(
const InternalNode& other,
const ValueType& value,
430 bool valueIsActive, CombineOp&);
437 template<
typename BBoxOp>
void visitActiveBBox(BBoxOp&)
const;
439 template<
typename VisitorOp>
void visit(VisitorOp&);
440 template<
typename VisitorOp>
void visit(VisitorOp&)
const;
442 template<
typename OtherNodeType,
typename VisitorOp>
443 void visit2Node(OtherNodeType& other, VisitorOp&);
444 template<
typename OtherNodeType,
typename VisitorOp>
445 void visit2Node(OtherNodeType& other, VisitorOp&)
const;
446 template<
typename IterT,
typename VisitorOp>
447 void visit2(IterT& otherIter, VisitorOp&,
bool otherIsLHS =
false);
448 template<
typename IterT,
typename VisitorOp>
449 void visit2(IterT& otherIter, VisitorOp&,
bool otherIsLHS =
false)
const;
457 template<
typename PruneOp>
void pruneOp(PruneOp&);
462 void prune(
const ValueType& tolerance = zeroVal<ValueType>());
466 void pruneInactive(
const ValueType&);
470 void pruneInactive();
478 LeafNodeType* touchLeaf(
const Coord& xyz);
482 LeafNodeType* probeLeaf(
const Coord& xyz);
485 const LeafNodeType* probeConstLeaf(
const Coord& xyz)
const;
489 template<
typename AccessorT>
490 LeafNodeType* touchLeafAndCache(
const Coord& xyz, AccessorT&);
494 template<
typename AccessorT>
495 LeafNodeType* probeLeafAndCache(
const Coord& xyz, AccessorT&);
498 template<
typename AccessorT>
499 const LeafNodeType* probeConstLeafAndCache(
const Coord& xyz, AccessorT&)
const;
501 void resetBackground(
const ValueType& oldBackground,
const ValueType& newBackground);
505 template<
typename OtherChildNodeType, Index OtherLog2Dim>
537 void makeChildNodeEmpty(
Index n,
const ValueType& value);
538 void setChildNode(
Index i, ChildNodeType* child);
539 ChildNodeType* unsetChildNode(
Index i,
const ValueType& value);
541 template<
typename NodeT,
typename VisitorOp,
typename ChildAllIterT>
542 static inline void doVisit(NodeT&, VisitorOp&);
544 template<
typename NodeT,
typename OtherNodeT,
typename VisitorOp,
545 typename ChildAllIterT,
typename OtherChildAllIterT>
546 static inline void doVisit2Node(NodeT&, OtherNodeT&, VisitorOp&);
548 template<
typename NodeT,
typename VisitorOp,
549 typename ChildAllIterT,
typename OtherChildAllIterT>
550 static inline void doVisit2(NodeT&, OtherChildAllIterT&, VisitorOp&,
bool otherIsLHS);
552 ChildNodeType* getChildNode(
Index n);
553 const ChildNodeType* getChildNode(
Index n)
const;
566 template<
typename ChildT, Index Log2Dim>
570 for (
Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
574 template<
typename ChildT, Index Log2Dim>
577 mOrigin(origin[0] & ~(DIM - 1),
578 origin[1] & ~(DIM - 1),
579 origin[2] & ~(DIM - 1))
586 template<
typename ChildT, Index Log2Dim>
589 mChildMask(other.mChildMask),
590 mValueMask(other.mValueMask),
591 mOrigin(other.mOrigin)
602 template<
typename ChildT, Index Log2Dim>
603 template<
typename OtherChildNodeType>
607 mChildMask(other.mChildMask),
608 mValueMask(other.mValueMask),
609 mOrigin(other.mOrigin)
621 template<
typename ChildT, Index Log2Dim>
622 template<
typename OtherChildNodeType>
626 mChildMask(other.mChildMask),
627 mValueMask(other.mValueMask),
628 mOrigin(other.mOrigin)
638 template<
typename ChildT, Index Log2Dim>
642 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
643 delete mNodes[iter.pos()].getChild();
651 template<
typename ChildT, Index Log2Dim>
655 if (ChildNodeType::getLevel() == 0)
return mChildMask.countOn();
657 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
658 sum += iter->leafCount();
664 template<
typename ChildT, Index Log2Dim>
669 if (ChildNodeType::getLevel() == 0)
return sum;
670 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
671 sum += iter->nonLeafCount();
677 template<
typename ChildT, Index Log2Dim>
682 for (
Index i = 0; i < NUM_VALUES; ++i) {
683 if (isChildMaskOff(i)) {
684 if (isValueMaskOn(i)) sum += ChildT::NUM_VOXELS;
686 sum += mNodes[i].getChild()->onVoxelCount();
693 template<
typename ChildT, Index Log2Dim>
698 for (
Index i = 0; i < NUM_VALUES; ++i) {
699 if (isChildMaskOff(i)) {
700 if (isValueMaskOff(i)) sum += ChildT::NUM_VOXELS;
702 sum += mNodes[i].getChild()->offVoxelCount();
709 template<
typename ChildT, Index Log2Dim>
714 for (
ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
715 sum += mNodes[iter.pos()].getChild()->onLeafVoxelCount();
721 template<
typename ChildT, Index Log2Dim>
726 for (
ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
727 sum += mNodes[iter.pos()].getChild()->offLeafVoxelCount();
733 template<
typename ChildT, Index Log2Dim>
738 + mValueMask.memUsage() +
sizeof(mOrigin);
739 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
740 sum += iter->memUsage();
746 template<
typename ChildT, Index Log2Dim>
750 if (bbox.
isInside(this->getNodeBoundingBox()))
return;
753 for (
ChildAllCIter iter = this->cbeginChildAll(); iter; ++iter) {
754 if (
const ChildT* child = iter.probeChild(dummy)) {
755 child->evalActiveVoxelBoundingBox(bbox);
756 }
else if (iter.isValueOn()) {
757 bbox.
expand(iter.getCoord(), ChildT::DIM);
766 template<
typename ChildT, Index Log2Dim>
767 template<
typename PruneOp>
771 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
772 const Index i = iter.pos();
773 ChildT* child = mNodes[i].getChild();
774 if (!op(*child))
continue;
776 mChildMask.setOff(i);
777 mValueMask.set(i, op.state);
778 mNodes[i].setValue(op.value);
784 template<
typename ChildT, Index Log2Dim>
793 template<
typename ChildT, Index Log2Dim>
802 template<
typename ChildT, Index Log2Dim>
806 this->pruneInactive(this->getBackground());
809 template<
typename ChildT, Index Log2Dim>
810 inline typename ChildT::LeafNodeType*
813 const Index n = this->coord2offset(xyz);
814 if (mChildMask.isOff(n)) {
815 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), mValueMask.isOn(n)));
817 mValueMask.setOff(n);
819 return mNodes[n].getChild()->touchLeaf(xyz);
822 template<
typename ChildT, Index Log2Dim>
823 template<
typename AccessorT>
824 inline typename ChildT::LeafNodeType*
827 const Index n = this->coord2offset(xyz);
828 if (mChildMask.isOff(n)) {
829 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), mValueMask.isOn(n)));
831 mValueMask.setOff(n);
833 acc.insert(xyz, mNodes[n].getChild());
834 return mNodes[n].getChild()->touchLeafAndCache(xyz,acc);
837 template<
typename ChildT, Index Log2Dim>
838 inline typename ChildT::LeafNodeType*
841 const Index n = this->coord2offset(xyz);
842 return mChildMask.isOn(n) ? mNodes[n].getChild()->probeLeaf(xyz) : NULL;
845 template<
typename ChildT, Index Log2Dim>
846 inline const typename ChildT::LeafNodeType*
849 const Index n = this->coord2offset(xyz);
850 return mChildMask.isOn(n) ? mNodes[n].getChild()->probeConstLeaf(xyz) : NULL;
853 template<
typename ChildT, Index Log2Dim>
854 template<
typename AccessorT>
855 inline typename ChildT::LeafNodeType*
858 const Index n = this->coord2offset(xyz);
859 if (mChildMask.isOff(n))
return NULL;
860 acc.insert(xyz, mNodes[n].getChild());
861 return mNodes[n].getChild()->probeLeafAndCache(xyz,acc);
864 template<
typename ChildT, Index Log2Dim>
865 template<
typename AccessorT>
866 inline const typename ChildT::LeafNodeType*
869 const Index n = this->coord2offset(xyz);
870 if (mChildMask.isOff(n))
return NULL;
871 acc.insert(xyz, mNodes[n].getChild());
872 return mNodes[n].getChild()->probeConstLeafAndCache(xyz,acc);
879 template<
typename ChildT, Index Log2Dim>
884 bool allEqual =
true, firstValue =
true, valueState =
true;
886 for (
Index i = 0; allEqual && i < NUM_VALUES; ++i) {
887 if (this->isChildMaskOff(i)) {
892 valueState = isValueMaskOn(i);
893 value = mNodes[i].getValue();
895 allEqual = (isValueMaskOn(i) == valueState)
901 ValueType childValue = zeroVal<ValueType>();
902 bool isChildOn =
false;
903 if (mNodes[i].getChild()->isConstant(childValue, isChildOn, tolerance)) {
906 valueState = isChildOn;
909 allEqual = (isChildOn == valueState)
928 template<
typename ChildT, Index Log2Dim>
932 const Index n = this->coord2offset(xyz);
933 if (this->isChildMaskOff(n))
return this->isValueMaskOn(n);
934 return mNodes[n].getChild()->isValueOn(xyz);
937 template<
typename ChildT, Index Log2Dim>
941 const bool anyActiveTiles = !mValueMask.isOff();
942 if (LEVEL==1 || anyActiveTiles)
return anyActiveTiles;
943 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
944 if (iter->hasActiveTiles())
return true;
949 template<
typename ChildT, Index Log2Dim>
950 template<
typename AccessorT>
954 const Index n = this->coord2offset(xyz);
955 if (this->isChildMaskOff(n))
return this->isValueMaskOn(n);
956 acc.insert(xyz, mNodes[n].getChild());
957 return mNodes[n].getChild()->isValueOnAndCache(xyz, acc);
961 template<
typename ChildT, Index Log2Dim>
962 inline const typename ChildT::ValueType&
965 const Index n = this->coord2offset(xyz);
966 return this->isChildMaskOff(n) ? mNodes[n].getValue()
967 : mNodes[n].getChild()->getValue(xyz);
970 template<
typename ChildT, Index Log2Dim>
971 template<
typename AccessorT>
972 inline const typename ChildT::ValueType&
975 const Index n = this->coord2offset(xyz);
976 if (this->isChildMaskOn(n)) {
977 acc.insert(xyz, mNodes[n].getChild());
978 return mNodes[n].getChild()->getValueAndCache(xyz, acc);
980 return mNodes[n].getValue();
984 template<
typename ChildT, Index Log2Dim>
988 const Index n = this->coord2offset(xyz);
989 return this->isChildMaskOff(n) ? LEVEL : mNodes[n].getChild()->getValueLevel(xyz);
992 template<
typename ChildT, Index Log2Dim>
993 template<
typename AccessorT>
997 const Index n = this->coord2offset(xyz);
998 if (this->isChildMaskOn(n)) {
999 acc.insert(xyz, mNodes[n].getChild());
1000 return mNodes[n].getChild()->getValueLevelAndCache(xyz, acc);
1006 template<
typename ChildT, Index Log2Dim>
1010 const Index n = this->coord2offset(xyz);
1011 if (this->isChildMaskOff(n)) {
1012 value = mNodes[n].getValue();
1013 return this->isValueMaskOn(n);
1015 return mNodes[n].getChild()->probeValue(xyz, value);
1018 template<
typename ChildT, Index Log2Dim>
1019 template<
typename AccessorT>
1024 const Index n = this->coord2offset(xyz);
1025 if (this->isChildMaskOn(n)) {
1026 acc.insert(xyz, mNodes[n].getChild());
1027 return mNodes[n].getChild()->probeValueAndCache(xyz, value, acc);
1029 value = mNodes[n].getValue();
1030 return this->isValueMaskOn(n);
1034 template<
typename ChildT, Index Log2Dim>
1035 template<
typename AccessorT>
1036 inline const typename ChildT::ValueType&
1038 AccessorT& acc)
const
1040 const Index n = this->coord2offset(xyz);
1041 if (this->isChildMaskOn(n)) {
1042 acc.insert(xyz, mNodes[n].getChild());
1043 return mNodes[n].getChild()->getValue(xyz, state, level, acc);
1045 state = this->isValueMaskOn(n);
1047 return mNodes[n].getValue();
1051 template<
typename ChildT, Index Log2Dim>
1052 template<
typename ProbeT,
typename AccessorT>
1053 inline const typename ChildT::ValueType&
1056 const Index n = this->coord2offset(xyz);
1057 if (this->isChildMaskOn(n)) {
1058 acc.insert(xyz, mNodes[n].getChild());
1059 return mNodes[n].getChild()->probe(xyz, p, acc);
1061 p.setState(this->isValueMaskOn(n));
1063 return mNodes[n].getValue();
1066 template<
typename ChildT, Index Log2Dim>
1067 template<
bool State,
bool Level,
typename AccessorT>
1068 inline const typename ChildT::ValueType&
1071 const Index n = this->coord2offset(xyz);
1072 if (this->isChildMaskOn(n)) {
1073 acc.insert(xyz, mNodes[n].getChild());
1074 return mNodes[n].getChild()->template probe<State,Level,AccessorT>(xyz, state, level, acc);
1076 if (State) state = this->isValueMaskOn(n);
1077 if (Level) level = LEVEL;
1078 return mNodes[n].getValue();
1082 template<
typename ChildT, Index Log2Dim>
1086 const Index n = this->coord2offset(xyz);
1087 bool hasChild = this->isChildMaskOn(n);
1088 if (!hasChild && this->isValueMaskOn(n)) {
1091 mChildMask.setOn(n);
1092 mValueMask.setOff(n);
1094 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(),
true));
1096 if (hasChild) mNodes[n].getChild()->setValueOff(xyz);
1100 template<
typename ChildT, Index Log2Dim>
1104 const Index n = this->coord2offset(xyz);
1105 bool hasChild = this->isChildMaskOn(n);
1106 if (!hasChild && !this->isValueMaskOn(n)) {
1109 mChildMask.setOn(n);
1110 mValueMask.setOff(n);
1112 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(),
false));
1114 if (hasChild) mNodes[n].getChild()->setValueOn(xyz);
1118 template<
typename ChildT, Index Log2Dim>
1123 bool hasChild = this->isChildMaskOn(n);
1125 const bool active = this->isValueMaskOn(n);
1130 mChildMask.setOn(n);
1131 mValueMask.setOff(n);
1133 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1136 if (hasChild) mNodes[n].getChild()->setValueOff(xyz, value);
1139 template<
typename ChildT, Index Log2Dim>
1140 template<
typename AccessorT>
1146 bool hasChild = this->isChildMaskOn(n);
1148 const bool active = this->isValueMaskOn(n);
1153 mChildMask.setOn(n);
1154 mValueMask.setOff(n);
1156 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1160 ChildT* child = mNodes[n].getChild();
1161 acc.insert(xyz, child);
1162 child->setValueOffAndCache(xyz, value, acc);
1167 template<
typename ChildT, Index Log2Dim>
1171 const Index n = this->coord2offset(xyz);
1172 bool hasChild = this->isChildMaskOn(n);
1174 const bool active = this->isValueMaskOn(n);
1179 mChildMask.setOn(n);
1180 mValueMask.setOff(n);
1182 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1185 if (hasChild) mNodes[n].getChild()->setValueOn(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);
1197 const bool active = this->isValueMaskOn(n);
1202 mChildMask.setOn(n);
1203 mValueMask.setOff(n);
1205 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1209 acc.insert(xyz, mNodes[n].getChild());
1210 mNodes[n].getChild()->setValueAndCache(xyz, value, acc);
1215 template<
typename ChildT, Index Log2Dim>
1219 const Index n = this->coord2offset(xyz);
1220 bool hasChild = this->isChildMaskOn(n);
1224 const bool active = this->isValueMaskOn(n);
1225 mChildMask.setOn(n);
1226 mValueMask.setOff(n);
1228 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1230 if (hasChild) mNodes[n].getChild()->setValueOnly(xyz, value);
1233 template<
typename ChildT, Index Log2Dim>
1234 template<
typename AccessorT>
1239 const Index n = this->coord2offset(xyz);
1240 bool hasChild = this->isChildMaskOn(n);
1244 const bool active = this->isValueMaskOn(n);
1245 mChildMask.setOn(n);
1246 mValueMask.setOff(n);
1248 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1251 acc.insert(xyz, mNodes[n].getChild());
1252 mNodes[n].getChild()->setValueOnlyAndCache(xyz, value, acc);
1257 template<
typename ChildT, Index Log2Dim>
1261 const Index n = this->coord2offset(xyz);
1262 bool hasChild = this->isChildMaskOn(n);
1264 if (on != this->isValueMaskOn(n)) {
1267 mChildMask.setOn(n);
1268 mValueMask.setOff(n);
1269 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1274 if (hasChild) mNodes[n].getChild()->setActiveState(xyz, on);
1277 template<
typename ChildT, Index Log2Dim>
1278 template<
typename AccessorT>
1282 const Index n = this->coord2offset(xyz);
1283 bool hasChild = this->isChildMaskOn(n);
1285 if (on != this->isValueMaskOn(n)) {
1288 mChildMask.setOn(n);
1289 mValueMask.setOff(n);
1290 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1296 ChildT* child = mNodes[n].getChild();
1297 acc.insert(xyz, child);
1298 child->setActiveStateAndCache(xyz, on, acc);
1303 template<
typename ChildT, Index Log2Dim>
1307 mValueMask = !mChildMask;
1308 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1309 mNodes[iter.pos()].getChild()->setValuesOn();
1314 template<
typename ChildT, Index Log2Dim>
1319 bool hasChild = this->isChildMaskOn(n);
1321 const bool active = this->isValueMaskOn(n);
1322 if (!active || (mNodes[n].getValue() > value)) {
1326 mChildMask.setOn(n);
1327 mValueMask.setOff(n);
1329 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1332 if (hasChild) mNodes[n].getChild()->setValueOnMin(xyz, value);
1336 template<
typename ChildT, Index Log2Dim>
1341 bool hasChild = this->isChildMaskOn(n);
1343 const bool active = this->isValueMaskOn(n);
1344 if (!active || (value > mNodes[n].getValue())) {
1348 mChildMask.setOn(n);
1349 mValueMask.setOff(n);
1351 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1354 if (hasChild) mNodes[n].getChild()->setValueOnMax(xyz, value);
1358 template<
typename ChildT, Index Log2Dim>
1363 bool hasChild = this->isChildMaskOn(n);
1365 const bool active = this->isValueMaskOn(n);
1369 mChildMask.setOn(n);
1370 mValueMask.setOff(n);
1372 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1375 if (hasChild) mNodes[n].getChild()->setValueOnSum(xyz, addend);
1378 template<
typename ChildT, Index Log2Dim>
1379 template<
typename AccessorT>
1382 const ValueType& addend, AccessorT& acc)
1384 const Index n = this->coord2offset(xyz);
1385 bool hasChild = this->isChildMaskOn(n);
1387 const bool active = this->isValueMaskOn(n);
1391 mChildMask.setOn(n);
1392 mValueMask.setOff(n);
1394 mNodes[n].setChild(
new ChildNodeType(xyz, mNodes[n].getValue(), active));
1398 acc.insert(xyz, mNodes[n].getChild());
1399 mNodes[n].getChild()->setValueOnSumAndCache(xyz, addend, acc);
1404 template<
typename ChildT, Index Log2Dim>
1405 template<
typename AccessorT>
1409 const Index n = this->coord2offset(xyz);
1410 if (this->isChildMaskOn(n)) {
1411 acc.insert(xyz, mNodes[n].getChild());
1412 mNodes[n].getChild()->updateCache(xyz, acc);
1420 template<
typename ChildT, Index Log2Dim>
1424 Coord xyz, tileMin, tileMax;
1425 for (
int x = bbox.
min().
x(); x <= bbox.
max().
x(); x = tileMax.
x() + 1) {
1427 for (
int y = bbox.
min().
y(); y <= bbox.
max().
y(); y = tileMax.
y() + 1) {
1429 for (
int z = bbox.
min().
z(); z <= bbox.
max().
z(); z = tileMax.
z() + 1) {
1433 const Index n = this->coord2offset(xyz);
1434 tileMin = this->offset2globalCoord(n);
1435 tileMax = tileMin.
offsetBy(ChildT::DIM - 1);
1441 ChildT* child = NULL;
1442 if (this->isChildMaskOff(n)) {
1445 child =
new ChildT(xyz, mNodes[n].getValue(), this->isValueMaskOn(n));
1446 mChildMask.setOn(n);
1447 mValueMask.setOff(n);
1448 mNodes[n].setChild(child);
1450 child = mNodes[n].getChild();
1463 this->makeChildNodeEmpty(n, value);
1464 mValueMask.set(n, active);
1475 template<
typename ChildT, Index Log2Dim>
1479 mChildMask.save(os);
1480 mValueMask.save(os);
1484 boost::shared_array<ValueType> values(
new ValueType[NUM_VALUES]);
1485 const ValueType zero = zeroVal<ValueType>();
1486 for (
Index i = 0; i < NUM_VALUES; ++i) {
1487 values[i] = (mChildMask.isOff(i) ? mNodes[i].getValue() : zero);
1493 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1494 iter->writeTopology(os, toHalf);
1499 template<
typename ChildT, Index Log2Dim>
1503 mChildMask.load(is);
1504 mValueMask.load(is);
1507 for (
Index i = 0; i < NUM_VALUES; ++i) {
1508 if (this->isChildMaskOn(i)) {
1510 new ChildNodeType(offset2globalCoord(i), zeroVal<ValueType>());
1511 mNodes[i].setChild(child);
1512 child->readTopology(is);
1515 is.read(reinterpret_cast<char*>(&value),
sizeof(
ValueType));
1516 mNodes[i].setValue(value);
1520 const bool oldVersion =
1522 const Index numValues = (oldVersion ? mChildMask.countOff() : NUM_VALUES);
1526 boost::shared_array<ValueType> values(
new ValueType[numValues]);
1532 for (
ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
1533 mNodes[iter.pos()].setValue(values[n++]);
1535 assert(n == numValues);
1537 for (
ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
1538 mNodes[iter.pos()].setValue(values[iter.pos()]);
1543 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1545 mNodes[iter.pos()].setChild(child);
1546 child->readTopology(is, fromHalf);
1555 template<
typename ChildT, Index Log2Dim>
1556 inline const typename ChildT::ValueType&
1559 return (this->isChildMaskOn(0) ? mNodes[0].getChild()->getFirstValue() : mNodes[0].getValue());
1563 template<
typename ChildT, Index Log2Dim>
1564 inline const typename ChildT::ValueType&
1567 const Index n = NUM_VALUES - 1;
1568 return (this->isChildMaskOn(n) ? mNodes[n].getChild()->getLastValue() : mNodes[n].getValue());
1577 template<
typename ChildT, Index Log2Dim>
1581 const ValueType zero = zeroVal<ValueType>();
1585 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1586 iter->signedFloodFill(background);
1588 const Index first = mChildMask.findFirstOn();
1589 assert(first < NUM_VALUES);
1590 bool inside = (mNodes[first].getChild()->getFirstValue() < zero),
1593 for (
Index i = 0; i != (1 << Log2Dim); ++i) {
1594 const int i00 = i << (2 * Log2Dim);
1595 if (isChildMaskOn(i00)) {
1596 xInside = (mNodes[i00].getChild()->getLastValue() < zero);
1599 for (
Index j = 0; j != (1 << Log2Dim); ++j) {
1600 const Index ij0 = i00 + (j << Log2Dim);
1601 if (isChildMaskOn(ij0)) {
1602 yInside = (mNodes[ij0].getChild()->getLastValue() < zero);
1605 for (
Index k = 0; k != (1 << Log2Dim); ++k) {
1606 const Index ijk = ij0 + k;
1607 if (isChildMaskOn(ijk)) {
1608 inside = (mNodes[ijk].getChild()->getLastValue() < zero);
1610 mNodes[ijk].setValue(inside ?
negative(background) : background);
1618 template<
typename ChildT, Index Log2Dim>
1622 for (
Index i = 0; i < NUM_VALUES; ++i) {
1623 if (this->isChildMaskOn(i)) {
1624 mNodes[i].getChild()->negate();
1626 mNodes[i].setValue(
negative(mNodes[i].getValue()));
1632 template<
typename ChildT, Index Log2Dim>
1636 for (
ValueOnIter iter = this->beginValueOn(); iter; ++iter) {
1637 const Index n = iter.pos();
1639 mValueMask.setOff(n);
1640 mChildMask.setOn(n);
1641 mNodes[n].setChild(child);
1643 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) iter->voxelizeActiveTiles();
1646 template<
typename ChildT, Index Log2Dim>
1652 const Index n = iter.pos();
1653 if (mChildMask.isOff(n)) {
1658 child->resetBackground(otherBackground, background);
1659 mChildMask.setOn(n);
1660 mValueMask.setOff(n);
1661 mNodes[n].setChild(child);
1663 mNodes[n].getChild()->merge(*iter, background, otherBackground);
1669 const Index n = iter.pos();
1670 if (mChildMask.isOff(n) && mValueMask.isOff(n)) {
1671 mNodes[n].setValue(iter.getValue());
1672 mValueMask.setOn(n);
1678 template<
typename ChildT, Index Log2Dim>
1679 template<
typename OtherChildT>
1686 for (OtherChildIter iter = other.
cbeginChildOn(); iter; ++iter) {
1688 if (mChildMask.isOn(i)) {
1689 mNodes[i].getChild()->topologyUnion(*iter);
1690 }
else if (mValueMask.isOff(i)) {
1691 mChildMask.setOn(i);
1695 for (OtherValueIter iter = other.
cbeginValueOn(); iter; ++iter) {
1696 const Index i = iter.pos();
1697 if (mChildMask.isOn(i)) {
1698 mNodes[i].getChild()->setValuesOn();
1699 }
else if (mValueMask.isOff(i)) {
1700 mValueMask.setOn(i);
1708 template<
typename ChildT, Index Log2Dim>
1709 template<
typename CombineOp>
1713 const ValueType zero = zeroVal<ValueType>();
1717 for (
Index i = 0; i < NUM_VALUES; ++i) {
1721 op(args.setARef(mNodes[i].getValue())
1722 .setAIsActive(isValueMaskOn(i))
1723 .setBRef(other.
mNodes[i].getValue())
1725 mNodes[i].setValue(args.result());
1726 mValueMask.set(i, args.resultIsActive());
1734 }
else if (this->isChildMaskOff(i) && other.
isChildMaskOn(i)) {
1743 child->combine(mNodes[i].getValue(), isValueMaskOn(i), swappedOp);
1747 other.
mNodes[i].setValue(zero);
1748 mChildMask.setOn(i);
1749 mValueMask.setOff(i);
1750 mNodes[i].setChild(child);
1756 *child = mNodes[i].getChild(),
1757 *otherChild = other.
mNodes[i].getChild();
1760 if (child && otherChild) {
1761 child->combine(*otherChild, op);
1768 template<
typename ChildT, Index Log2Dim>
1769 template<
typename CombineOp>
1775 for (
Index i = 0; i < NUM_VALUES; ++i) {
1776 if (this->isChildMaskOff(i)) {
1778 op(args.
setARef(mNodes[i].getValue())
1779 .setAIsActive(isValueMaskOn(i))
1781 .setBIsActive(valueIsActive));
1782 mNodes[i].setValue(args.
result());
1788 if (child) child->combine(value, valueIsActive, op);
1797 template<
typename ChildT, Index Log2Dim>
1798 template<
typename CombineOp>
1805 for (
Index i = 0; i < NUM_VALUES; ++i) {
1809 .setBRef(other1.
mNodes[i].getValue())
1812 this->makeChildNodeEmpty(i, args.
result());
1816 ? other0.
mNodes[i].getChild() : other1.
mNodes[i].getChild();
1818 if (this->isChildMaskOff(i)) {
1821 mChildMask.setOn(i);
1822 mValueMask.setOff(i);
1823 mNodes[i].setChild(
new ChildNodeType(otherChild->getOrigin(),
1824 mNodes[i].getValue()));
1830 mNodes[i].getChild()->combine2(other0.
mNodes[i].getValue(),
1835 mNodes[i].getChild()->combine2(*other0.
mNodes[i].getChild(),
1840 mNodes[i].getChild()->combine2(*other0.
mNodes[i].getChild(),
1841 *other1.
mNodes[i].getChild(), op);
1848 template<
typename ChildT, Index Log2Dim>
1849 template<
typename CombineOp>
1852 bool valueIsActive, CombineOp& op)
1856 for (
Index i = 0; i < NUM_VALUES; ++i) {
1859 .setAIsActive(valueIsActive)
1860 .setBRef(other.
mNodes[i].getValue())
1863 this->makeChildNodeEmpty(i, args.
result());
1868 if (this->isChildMaskOff(i)) {
1872 mChildMask.setOn(i);
1873 mValueMask.setOff(i);
1878 mNodes[i].getChild()->combine2(value, *otherChild, valueIsActive, op);
1884 template<
typename ChildT, Index Log2Dim>
1885 template<
typename CombineOp>
1888 bool valueIsActive, CombineOp& op)
1892 for (
Index i = 0; i < NUM_VALUES; ++i) {
1897 .setBIsActive(valueIsActive));
1899 this->makeChildNodeEmpty(i, args.
result());
1904 if (this->isChildMaskOff(i)) {
1907 mChildMask.setOn(i);
1908 mValueMask.setOff(i);
1909 mNodes[i].setChild(
new ChildNodeType(otherChild->getOrigin(),
1910 mNodes[i].getValue()));
1914 mNodes[i].getChild()->combine2(*otherChild, value, valueIsActive, op);
1923 template<
typename ChildT, Index Log2Dim>
1924 template<
typename BBoxOp>
1935 if (op.template descent<LEVEL>()) {
1936 for (
ChildOnCIter i = this->cbeginChildOn(); i; ++i) i->visitActiveBBox(op);
1940 op.operator()<LEVEL>(i->getNodeBoundingBox());
1942 op.template operator()<LEVEL>(i->getNodeBoundingBox());
1949 template<
typename ChildT, Index Log2Dim>
1950 template<
typename VisitorOp>
1954 doVisit<InternalNode, VisitorOp, ChildAllIter>(*
this, op);
1958 template<
typename ChildT, Index Log2Dim>
1959 template<
typename VisitorOp>
1963 doVisit<const InternalNode, VisitorOp, ChildAllCIter>(*
this, op);
1967 template<
typename ChildT, Index Log2Dim>
1968 template<
typename NodeT,
typename VisitorOp,
typename ChildAllIterT>
1972 typename NodeT::ValueType val;
1973 for (ChildAllIterT iter =
self.beginChildAll(); iter; ++iter) {
1974 if (op(iter))
continue;
1975 if (
typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
1985 template<
typename ChildT, Index Log2Dim>
1986 template<
typename OtherNodeType,
typename VisitorOp>
1991 typename OtherNodeType::ChildAllIter>(*
this, other, op);
1995 template<
typename ChildT, Index Log2Dim>
1996 template<
typename OtherNodeType,
typename VisitorOp>
2001 typename OtherNodeType::ChildAllCIter>(*
this, other, op);
2005 template<
typename ChildT, Index Log2Dim>
2008 typename OtherNodeT,
2010 typename ChildAllIterT,
2011 typename OtherChildAllIterT>
2016 BOOST_STATIC_ASSERT(OtherNodeT::NUM_VALUES == NodeT::NUM_VALUES);
2017 BOOST_STATIC_ASSERT(OtherNodeT::LEVEL == NodeT::LEVEL);
2019 typename NodeT::ValueType val;
2020 typename OtherNodeT::ValueType otherVal;
2022 ChildAllIterT iter =
self.beginChildAll();
2023 OtherChildAllIterT otherIter = other.beginChildAll();
2025 for ( ; iter && otherIter; ++iter, ++otherIter)
2027 const size_t skipBranch =
static_cast<size_t>(op(iter, otherIter));
2029 typename ChildAllIterT::ChildNodeType* child =
2030 (skipBranch & 1U) ? NULL : iter.probeChild(val);
2031 typename OtherChildAllIterT::ChildNodeType* otherChild =
2032 (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
2034 if (child != NULL && otherChild != NULL) {
2035 child->visit2Node(*otherChild, op);
2036 }
else if (child != NULL) {
2037 child->visit2(otherIter, op);
2038 }
else if (otherChild != NULL) {
2039 otherChild->visit2(iter, op,
true);
2048 template<
typename ChildT, Index Log2Dim>
2049 template<
typename OtherChildAllIterType,
typename VisitorOp>
2052 VisitorOp& op,
bool otherIsLHS)
2054 doVisit2<InternalNode, VisitorOp, ChildAllIter, OtherChildAllIterType>(
2055 *
this, otherIter, op, otherIsLHS);
2059 template<
typename ChildT, Index Log2Dim>
2060 template<
typename OtherChildAllIterType,
typename VisitorOp>
2063 VisitorOp& op,
bool otherIsLHS)
const
2065 doVisit2<const InternalNode, VisitorOp, ChildAllCIter, OtherChildAllIterType>(
2066 *
this, otherIter, op, otherIsLHS);
2070 template<
typename ChildT, Index Log2Dim>
2071 template<
typename NodeT,
typename VisitorOp,
typename ChildAllIterT,
typename OtherChildAllIterT>
2074 VisitorOp& op,
bool otherIsLHS)
2076 if (!otherIter)
return;
2078 const size_t skipBitMask = (otherIsLHS ? 2U : 1U);
2080 typename NodeT::ValueType val;
2081 for (ChildAllIterT iter =
self.beginChildAll(); iter; ++iter) {
2082 const size_t skipBranch =
static_cast<size_t>(
2083 otherIsLHS ? op(otherIter, iter) : op(iter, otherIter));
2085 typename ChildAllIterT::ChildNodeType* child =
2086 (skipBranch & skipBitMask) ? NULL : iter.probeChild(val);
2088 if (child != NULL) child->visit2(otherIter, op, otherIsLHS);
2096 template<
typename ChildT, Index Log2Dim>
2100 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2101 iter->writeBuffers(os, toHalf);
2106 template<
typename ChildT, Index Log2Dim>
2110 for (
ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2111 iter->readBuffers(is, fromHalf);
2119 template<
typename ChildT, Index Log2Dim>
2123 dims.push_back(Log2Dim);
2124 ChildNodeType::getNodeLog2Dims(dims);
2128 template<
typename ChildT, Index Log2Dim>
2132 assert(n<(1<<3*Log2Dim));
2133 xyz.
setX(n >> 2*Log2Dim);
2134 n &= ((1<<2*Log2Dim)-1);
2135 xyz.
setY(n >> Log2Dim);
2136 xyz.
setZ(n & ((1<<Log2Dim)-1));
2140 template<
typename ChildT, Index Log2Dim>
2144 return (((xyz[0]&DIM-1u)>>ChildNodeType::TOTAL)<<2*Log2Dim)
2145 + (((xyz[1]&DIM-1u)>>ChildNodeType::TOTAL)<< Log2Dim)
2146 + ((xyz[2]&DIM-1u)>>ChildNodeType::TOTAL);
2150 template<
typename ChildT, Index Log2Dim>
2155 this->offset2coord(n, local);
2156 local <<= ChildT::TOTAL;
2157 return local + this->getOrigin();
2164 template<
typename ChildT, Index Log2Dim>
2169 for (
Index i = 0; i < NUM_VALUES; ++i) {
2170 if (this->isChildMaskOn(i)) {
2171 mNodes[i].getChild()->resetBackground(oldBackground, newBackground);
2174 mNodes[i].setValue(newBackground);
2176 mNodes[i].setValue(
negative(newBackground));
2183 template<
typename ChildT, Index Log2Dim>
2184 template<
typename OtherChildNodeType, Index OtherLog2Dim>
2189 if (Log2Dim != OtherLog2Dim || mChildMask != other->
mChildMask ||
2190 mValueMask != other->
mValueMask)
return false;
2191 for (
ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2192 if (!iter->hasSameTopology(other->
mNodes[iter.pos()].getChild()))
return false;
2198 template<
typename ChildT, Index Log2Dim>
2203 if (this->isChildMaskOn(i)) {
2204 delete mNodes[i].getChild();
2206 mChildMask.setOn(i);
2207 mValueMask.setOff(i);
2209 mNodes[i].setChild(child);
2213 template<
typename ChildT, Index Log2Dim>
2217 if (this->isChildMaskOff(i)) {
2218 mNodes[i].setValue(value);
2222 mChildMask.setOff(i);
2223 mNodes[i].setValue(value);
2228 template<
typename ChildT, Index Log2Dim>
2232 delete this->unsetChildNode(n, value);
2235 template<
typename ChildT, Index Log2Dim>
2239 return (this->isChildMaskOn(n) ? mNodes[n].getChild() : NULL);
2243 template<
typename ChildT, Index Log2Dim>
2244 inline const ChildT*
2247 return (this->isChildMaskOn(n) ? mNodes[n].getChild() : NULL);
2254 #endif // OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED