11 #ifndef OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
12 #define OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
19 #include <boost/mpl/at.hpp>
20 #include <boost/mpl/int.hpp>
21 #include <tbb/blocked_range.h>
22 #include <tbb/parallel_for.h>
23 #include <tbb/parallel_reduce.h>
24 #include <tbb/parallel_sort.h>
44 template<
typename Gr
idType>
45 inline typename GridType::ValueType lsutilGridMax()
50 template<
typename Gr
idType>
51 inline typename GridType::ValueType lsutilGridZero()
53 return zeroVal<typename GridType::ValueType>();
76 template<
class Gr
idType>
80 typename GridType::ValueType cutoffDistance = lsutilGridMax<GridType>());
93 template<
class Gr
idOrTreeType>
94 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
96 const GridOrTreeType& volume,
97 typename GridOrTreeType::ValueType isovalue = lsutilGridZero<GridOrTreeType>());
120 template<
typename Gr
idOrTreeType>
121 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
123 const GridOrTreeType& volume,
124 typename GridOrTreeType::ValueType isovalue = lsutilGridZero<GridOrTreeType>(),
125 const typename TreeAdapter<GridOrTreeType>::TreeType::template ValueConverter<bool>::Type*
134 template<
typename Gr
idOrTreeType>
135 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
144 template<
typename Gr
idOrTreeType>
147 std::vector<
typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr>& masks);
157 template<
typename Gr
idOrTreeType>
160 std::vector<typename GridOrTreeType::Ptr>& segments);
171 template<
typename Gr
idOrTreeType>
173 segmentSDF(
const GridOrTreeType& volume, std::vector<typename GridOrTreeType::Ptr>& segments);
182 namespace level_set_util_internal {
185 template<
typename LeafNodeType>
193 : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
197 void operator()(
const tbb::blocked_range<size_t>& range)
const {
201 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
203 mMaskNodes[n] =
nullptr;
204 const LeafNodeType& node = *mNodes[n];
212 const ValueType* values = &node.getValue(0);
213 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
214 if (values[i] < mIsovalue) maskNodePt->
setValueOn(i,
true);
218 mMaskNodes[n] = maskNodePt;
219 maskNodePt =
nullptr;
223 if (maskNodePt)
delete maskNodePt;
226 LeafNodeType
const *
const *
const mNodes;
232 template<
typename TreeType,
typename InternalNodeType>
238 : mTree(&tree), mMaskNodes(maskNodes), mIsovalue(isovalue) { }
240 void operator()(
const tbb::blocked_range<size_t>& range)
const {
242 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
243 typename InternalNodeType::ValueAllIter it = mMaskNodes[n]->beginValueAll();
245 if (acc.
getValue(it.getCoord()) < mIsovalue) {
259 template<
typename TreeType>
266 const size_t * nodexIndexMap,
ValueType background)
267 : mNewTree(background)
270 , mNodeIndexMap(nodexIndexMap)
275 : mNewTree(rhs.mNewTree.background())
278 , mNodeIndexMap(rhs.mNodeIndexMap)
287 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
288 for (
size_t i = mNodeIndexMap[n], I = mNodeIndexMap[n + 1]; i < I; ++i) {
289 if (mNodes[i] !=
nullptr) acc.
addLeaf(mNodes[i]);
293 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
303 TreeType *
const mTreePt;
304 LeafNodeType **
const mNodes;
305 size_t const *
const mNodeIndexMap;
310 template<
typename LeafNodeType>
318 : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
322 void operator()(
const tbb::blocked_range<size_t>& range)
const {
326 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
328 mMaskNodes[n] =
nullptr;
329 const LeafNodeType& node = *mNodes[n];
337 typename LeafNodeType::ValueOnCIter it;
338 for (it = node.cbeginValueOn(); it; ++it) {
339 maskNodePt->
setValueOn(it.pos(), ((*it - mIsovalue) < 0.0) ? 0 : 1);
343 mMaskNodes[n] = maskNodePt;
344 maskNodePt =
nullptr;
348 if (maskNodePt)
delete maskNodePt;
351 LeafNodeType
const *
const *
const mNodes;
357 template<
typename LeafNodeType>
363 void operator()(
const tbb::blocked_range<size_t>& range)
const {
364 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
366 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
367 values[i] = values[i] < 0 ? 1 : -1;
376 template<
typename LeafNodeType>
394 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
395 const ValueType* data = mNodes[n]->buffer().data();
396 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
397 minValue =
std::min(minValue, data[i]);
406 LeafNodeType
const *
const *
const mNodes;
410 template<
typename InternalNodeType>
428 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
429 typename InternalNodeType::ValueAllCIter it = mNodes[n]->beginValueAll();
440 InternalNodeType
const *
const *
const mNodes;
444 template<
typename LeafNodeType>
450 : mNodes(nodes), mWeight(
ValueType(1.0) / cutoffDistance)
454 void operator()(
const tbb::blocked_range<size_t>& range)
const {
456 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
458 LeafNodeType& node = *mNodes[n];
461 ValueType* values = node.buffer().data();
462 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
464 if (values[i] >
ValueType(0.0)) node.setValueOn(i);
467 if (node.onVoxelCount() == 0) {
479 template<
typename TreeType,
typename InternalNodeType>
483 : mTree(&tree), mNodes(nodes) { }
485 void operator()(
const tbb::blocked_range<size_t>& range)
const {
487 using ValueType =
typename TreeType::ValueType;
490 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
491 typename InternalNodeType::ValueAllIter it = mNodes[n]->beginValueAll();
493 if (acc.
getValue(it.getCoord()) < ValueType(0.0)) {
494 it.setValue(ValueType(1.0));
506 template<
typename TreeType>
511 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
517 , mFillMask(&fillMask)
518 , mFillNodes(fillNodes)
519 , mNewNodes(newNodes)
520 , mIsovalue(isovalue)
524 void operator()(
const tbb::blocked_range<size_t>& range)
const {
529 std::unique_ptr<char[]> valueMask(
new char[BoolLeafNodeType::SIZE]);
531 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
533 mNewNodes[n] =
nullptr;
535 const Coord& origin = node.origin();
537 const bool denseNode = node.isDense();
542 int denseNeighbors = 0;
546 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
549 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
552 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
555 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
558 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
561 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
563 if (denseNeighbors == 6)
continue;
567 memset(valueMask.get(), 0,
sizeof(
char) * BoolLeafNodeType::SIZE);
569 const typename TreeType::LeafNodeType* distNode = distAcc.
probeConstLeaf(origin);
573 bool earlyTermination =
false;
577 evalInternalNeighborsP(valueMask.get(), node, *distNode);
578 evalInternalNeighborsN(valueMask.get(), node, *distNode);
579 }
else if (distAcc.
getValue(origin) > mIsovalue) {
580 earlyTermination = evalInternalNeighborsP(valueMask.get(), node);
581 if (!earlyTermination) {
582 earlyTermination = evalInternalNeighborsN(valueMask.get(), node);
589 if (!earlyTermination) {
590 evalExternalNeighborsX<true>(valueMask.get(), node, maskAcc, distAcc);
591 evalExternalNeighborsX<false>(valueMask.get(), node, maskAcc, distAcc);
592 evalExternalNeighborsY<true>(valueMask.get(), node, maskAcc, distAcc);
593 evalExternalNeighborsY<false>(valueMask.get(), node, maskAcc, distAcc);
594 evalExternalNeighborsZ<true>(valueMask.get(), node, maskAcc, distAcc);
595 evalExternalNeighborsZ<false>(valueMask.get(), node, maskAcc, distAcc);
600 int numBoundaryValues = 0;
601 for (
Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
602 numBoundaryValues += valueMask[i] == 1;
605 if (numBoundaryValues > 0) {
607 for (
Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
608 if (valueMask[i] == 1) mNewNodes[n]->setValueOn(i);
616 void evalInternalNeighborsP(
char* valueMask,
const BoolLeafNodeType& node,
617 const LeafNodeType& distNode)
const
619 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
620 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
621 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
622 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
623 for (
Index z = 0; z < BoolLeafNodeType::DIM - 1; ++z) {
624 const Index pos = yPos + z;
626 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
628 if (!node.isValueOn(pos + 1) && distNode.getValue(pos + 1) > mIsovalue) {
635 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
636 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
637 for (
Index y = 0; y < BoolLeafNodeType::DIM - 1; ++y) {
638 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
639 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
640 const Index pos = yPos + z;
642 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
644 if (!node.isValueOn(pos + BoolLeafNodeType::DIM) &&
645 distNode.getValue(pos + BoolLeafNodeType::DIM) > mIsovalue) {
652 for (
Index x = 0; x < BoolLeafNodeType::DIM - 1; ++x) {
653 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
654 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
655 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
656 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
657 const Index pos = yPos + z;
659 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
661 if (!node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
662 (distNode.getValue(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)
672 bool evalInternalNeighborsP(
char* valueMask,
const BoolLeafNodeType& node)
const {
674 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
675 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
676 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
677 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
678 for (
Index z = 0; z < BoolLeafNodeType::DIM - 1; ++z) {
679 const Index pos = yPos + z;
681 if (node.isValueOn(pos) && !node.isValueOn(pos + 1)) {
689 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
690 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
691 for (
Index y = 0; y < BoolLeafNodeType::DIM - 1; ++y) {
692 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
693 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
694 const Index pos = yPos + z;
696 if (node.isValueOn(pos) && !node.isValueOn(pos + BoolLeafNodeType::DIM)) {
704 for (
Index x = 0; x < BoolLeafNodeType::DIM - 1; ++x) {
705 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
706 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
707 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
708 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
709 const Index pos = yPos + z;
711 if (node.isValueOn(pos) &&
712 !node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
725 void evalInternalNeighborsN(
char* valueMask,
const BoolLeafNodeType& node,
726 const LeafNodeType& distNode)
const
728 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
729 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
730 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
731 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
732 for (
Index z = 1; z < BoolLeafNodeType::DIM; ++z) {
733 const Index pos = yPos + z;
735 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
737 if (!node.isValueOn(pos - 1) && distNode.getValue(pos - 1) > mIsovalue) {
744 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
745 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
746 for (
Index y = 1; y < BoolLeafNodeType::DIM; ++y) {
747 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
748 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
749 const Index pos = yPos + z;
751 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
753 if (!node.isValueOn(pos - BoolLeafNodeType::DIM) &&
754 distNode.getValue(pos - BoolLeafNodeType::DIM) > mIsovalue) {
761 for (
Index x = 1; x < BoolLeafNodeType::DIM; ++x) {
762 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
763 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
764 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
765 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
766 const Index pos = yPos + z;
768 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
770 if (!node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
771 (distNode.getValue(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)
782 bool evalInternalNeighborsN(
char* valueMask,
const BoolLeafNodeType& node)
const {
784 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
785 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
786 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
787 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
788 for (
Index z = 1; z < BoolLeafNodeType::DIM; ++z) {
789 const Index pos = yPos + z;
791 if (node.isValueOn(pos) && !node.isValueOn(pos - 1)) {
799 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
800 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
801 for (
Index y = 1; y < BoolLeafNodeType::DIM; ++y) {
802 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
803 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
804 const Index pos = yPos + z;
806 if (node.isValueOn(pos) && !node.isValueOn(pos - BoolLeafNodeType::DIM)) {
814 for (
Index x = 1; x < BoolLeafNodeType::DIM; ++x) {
815 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
816 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
817 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
818 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
819 const Index pos = yPos + z;
821 if (node.isValueOn(pos) &&
822 !node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
837 template<
bool UpWind>
838 void evalExternalNeighborsX(
char* valueMask,
const BoolLeafNodeType& node,
839 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
840 const tree::ValueAccessor<const TreeType>& distAcc)
const {
842 const Coord& origin = node.origin();
843 Coord ijk(0, 0, 0), nijk;
848 ijk[0] = int(BoolLeafNodeType::DIM) - 1;
851 const Index xPos = ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM));
853 for (ijk[1] = 0; ijk[1] < int(BoolLeafNodeType::DIM); ++ijk[1]) {
854 const Index yPos = xPos + (ijk[1] << int(BoolLeafNodeType::LOG2DIM));
856 for (ijk[2] = 0; ijk[2] < int(BoolLeafNodeType::DIM); ++ijk[2]) {
857 const Index pos = yPos + ijk[2];
859 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
861 nijk = origin + ijk.offsetBy(step, 0, 0);
863 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
872 template<
bool UpWind>
873 void evalExternalNeighborsY(
char* valueMask,
const BoolLeafNodeType& node,
874 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
875 const tree::ValueAccessor<const TreeType>& distAcc)
const {
877 const Coord& origin = node.origin();
878 Coord ijk(0, 0, 0), nijk;
883 ijk[1] = int(BoolLeafNodeType::DIM) - 1;
886 const Index yPos = ijk[1] << int(BoolLeafNodeType::LOG2DIM);
888 for (ijk[0] = 0; ijk[0] < int(BoolLeafNodeType::DIM); ++ijk[0]) {
889 const Index xPos = yPos + (ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM)));
891 for (ijk[2] = 0; ijk[2] < int(BoolLeafNodeType::DIM); ++ijk[2]) {
892 const Index pos = xPos + ijk[2];
894 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
896 nijk = origin + ijk.offsetBy(0, step, 0);
897 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
906 template<
bool UpWind>
907 void evalExternalNeighborsZ(
char* valueMask,
const BoolLeafNodeType& node,
908 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
909 const tree::ValueAccessor<const TreeType>& distAcc)
const {
911 const Coord& origin = node.origin();
912 Coord ijk(0, 0, 0), nijk;
917 ijk[2] = int(BoolLeafNodeType::DIM) - 1;
920 for (ijk[0] = 0; ijk[0] < int(BoolLeafNodeType::DIM); ++ijk[0]) {
921 const Index xPos = ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM));
923 for (ijk[1] = 0; ijk[1] < int(BoolLeafNodeType::DIM); ++ijk[1]) {
924 const Index pos = ijk[2] + xPos + (ijk[1] << int(BoolLeafNodeType::LOG2DIM));
926 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
928 nijk = origin + ijk.offsetBy(0, 0, step);
929 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
939 TreeType
const *
const mTree;
940 BoolTreeType
const *
const mFillMask;
941 BoolLeafNodeType
const *
const *
const mFillNodes;
942 BoolLeafNodeType **
const mNewNodes;
943 ValueType
const mIsovalue;
949 template <
class TreeType>
950 inline typename TreeType::template ValueConverter<char>::Type::Ptr
952 const typename TreeType::template ValueConverter<bool>::Type* fillMask)
954 using LeafNodeType =
typename TreeType::LeafNodeType;
955 using RootNodeType =
typename TreeType::RootNodeType;
956 using NodeChainType =
typename RootNodeType::NodeChainType;
957 using InternalNodeType =
typename boost::mpl::at<NodeChainType, boost::mpl::int_<1>>::type;
959 using CharTreeType =
typename TreeType::template ValueConverter<char>::Type;
960 using CharLeafNodeType =
typename CharTreeType::LeafNodeType;
962 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
963 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
965 const TreeType* treePt = &tree;
967 size_t numLeafNodes = 0, numInternalNodes = 0;
969 std::vector<const LeafNodeType*> nodes;
970 std::vector<size_t> leafnodeCount;
974 std::vector<const InternalNodeType*> internalNodes;
975 treePt->getNodes(internalNodes);
977 numInternalNodes = internalNodes.size();
979 leafnodeCount.push_back(0);
980 for (
size_t n = 0; n < numInternalNodes; ++n) {
981 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
984 numLeafNodes = leafnodeCount.back();
987 nodes.reserve(numLeafNodes);
989 for (
size_t n = 0; n < numInternalNodes; ++n) {
990 internalNodes[n]->getNodes(nodes);
995 std::unique_ptr<CharLeafNodeType*[]> maskNodes(
new CharLeafNodeType*[numLeafNodes]);
997 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1001 typename CharTreeType::Ptr maskTree(
new CharTreeType(1));
1004 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1008 std::vector<CharLeafNodeType*> extraMaskNodes;
1012 std::vector<const BoolLeafNodeType*> fillMaskNodes;
1013 fillMask->getNodes(fillMaskNodes);
1015 std::unique_ptr<BoolLeafNodeType*[]> boundaryMaskNodes(
1016 new BoolLeafNodeType*[fillMaskNodes.size()]);
1018 tbb::parallel_for(tbb::blocked_range<size_t>(0, fillMaskNodes.size()),
1020 boundaryMaskNodes.get()));
1024 for (
size_t n = 0, N = fillMaskNodes.size(); n < N; ++n) {
1026 if (boundaryMaskNodes[n] ==
nullptr)
continue;
1028 const BoolLeafNodeType& boundaryNode = *boundaryMaskNodes[n];
1029 const Coord& origin = boundaryNode.origin();
1031 CharLeafNodeType* maskNodePt = maskAcc.
probeLeaf(origin);
1035 extraMaskNodes.push_back(maskNodePt);
1038 char* data = maskNodePt->buffer().data();
1040 typename BoolLeafNodeType::ValueOnCIter it = boundaryNode.cbeginValueOn();
1042 if (data[it.pos()] != 0) data[it.pos()] = -1;
1045 delete boundaryMaskNodes[n];
1053 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1056 if (!extraMaskNodes.empty()) {
1057 tbb::parallel_for(tbb::blocked_range<size_t>(0, extraMaskNodes.size()),
1068 template <
class TreeType>
1069 inline typename TreeType::template ValueConverter<bool>::Type::Ptr
1072 using ValueType =
typename TreeType::ValueType;
1073 using LeafNodeType =
typename TreeType::LeafNodeType;
1074 using RootNodeType =
typename TreeType::RootNodeType;
1075 using NodeChainType =
typename RootNodeType::NodeChainType;
1076 using InternalNodeType =
typename boost::mpl::at<NodeChainType, boost::mpl::int_<1> >::type;
1078 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1079 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1080 using BoolRootNodeType =
typename BoolTreeType::RootNodeType;
1081 using BoolNodeChainType =
typename BoolRootNodeType::NodeChainType;
1082 using BoolInternalNodeType =
1083 typename boost::mpl::at<BoolNodeChainType, boost::mpl::int_<1>>::type;
1095 size_t numLeafNodes = 0, numInternalNodes = 0;
1097 std::vector<const LeafNodeType*> nodes;
1098 std::vector<size_t> leafnodeCount;
1102 std::vector<const InternalNodeType*> internalNodes;
1103 tree.getNodes(internalNodes);
1105 numInternalNodes = internalNodes.size();
1107 leafnodeCount.push_back(0);
1108 for (
size_t n = 0; n < numInternalNodes; ++n) {
1109 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
1112 numLeafNodes = leafnodeCount.back();
1115 nodes.reserve(numLeafNodes);
1117 for (
size_t n = 0; n < numInternalNodes; ++n) {
1118 internalNodes[n]->getNodes(nodes);
1123 std::unique_ptr<BoolLeafNodeType*[]> maskNodes(
new BoolLeafNodeType*[numLeafNodes]);
1125 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1130 typename BoolTreeType::Ptr maskTree(
new BoolTreeType(
false));
1133 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1137 std::vector<BoolInternalNodeType*> internalMaskNodes;
1138 maskTree->getNodes(internalMaskNodes);
1140 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalMaskNodes.size()),
1145 typename BoolTreeType::ValueAllIter it(*maskTree);
1146 it.setMaxDepth(BoolTreeType::ValueAllIter::LEAF_DEPTH - 2);
1149 if (acc.
getValue(it.getCoord()) < iso) {
1151 it.setActiveState(
true);
1159 template<
typename InputTreeType>
1164 using BoolTreeType =
typename InputTreeType::template ValueConverter<bool>::Type;
1168 const InputTreeType& inputTree,
1169 const std::vector<const InputLeafNodeType*>& inputLeafNodes,
1172 : mInputAccessor(inputTree)
1173 , mInputNodes(!inputLeafNodes.empty() ? &inputLeafNodes.front() : nullptr)
1175 , mMaskAccessor(maskTree)
1181 : mInputAccessor(rhs.mInputAccessor.tree())
1182 , mInputNodes(rhs.mInputNodes)
1184 , mMaskAccessor(mMaskTree)
1185 , mIsovalue(rhs.mIsovalue)
1196 for (
size_t n = range.begin(); mInputNodes && (n != range.end()); ++n) {
1201 else maskNodePt->setOrigin(node.origin());
1203 bool collectedData =
false;
1205 for (
typename InputLeafNodeType::ValueOnCIter it = node.cbeginValueOn(); it; ++it) {
1207 bool isUnder = *it < iso;
1209 ijk = it.getCoord();
1212 bool signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1217 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1223 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1229 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1235 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1241 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1246 collectedData =
true;
1247 maskNodePt->setValueOn(it.pos(),
true);
1251 if (collectedData) {
1252 mMaskAccessor.addLeaf(maskNodePt);
1253 maskNodePt =
nullptr;
1257 if (maskNodePt)
delete maskNodePt;
1261 mMaskAccessor.tree().merge(rhs.mMaskAccessor.
tree());
1266 InputLeafNodeType
const *
const *
const mInputNodes;
1268 BoolTreeType mMaskTree;
1271 InputValueType mIsovalue;
1278 template<
typename NodeType>
1293 template<
typename NodeType>
1298 using NodeMaskType =
typename NodeType::NodeMaskType;
1300 using NodeMaskSegmentTypePtr =
typename NodeMaskSegmentType::Ptr;
1302 NodeMaskType nodeMask(node.getValueMask());
1303 std::deque<Index> indexList;
1305 while (!nodeMask.isOff()) {
1307 NodeMaskSegmentTypePtr segment(
new NodeMaskSegmentType());
1308 segment->origin = node.origin();
1310 NodeMaskType& mask = segment->mask;
1312 indexList.push_back(nodeMask.findFirstOn());
1313 nodeMask.setOff(indexList.back());
1316 while (!indexList.empty()) {
1318 const Index pos = indexList.back();
1319 indexList.pop_back();
1321 if (mask.isOn(pos))
continue;
1324 ijk = NodeType::offsetToLocalCoord(pos);
1326 Index npos = pos - 1;
1327 if (ijk[2] != 0 && nodeMask.isOn(npos)) {
1328 nodeMask.setOff(npos);
1329 indexList.push_back(npos);
1333 if (ijk[2] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1334 nodeMask.setOff(npos);
1335 indexList.push_back(npos);
1338 npos = pos - NodeType::DIM;
1339 if (ijk[1] != 0 && nodeMask.isOn(npos)) {
1340 nodeMask.setOff(npos);
1341 indexList.push_back(npos);
1344 npos = pos + NodeType::DIM;
1345 if (ijk[1] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1346 nodeMask.setOff(npos);
1347 indexList.push_back(npos);
1350 npos = pos - NodeType::DIM * NodeType::DIM;
1351 if (ijk[0] != 0 && nodeMask.isOn(npos)) {
1352 nodeMask.setOff(npos);
1353 indexList.push_back(npos);
1356 npos = pos + NodeType::DIM * NodeType::DIM;
1357 if (ijk[0] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1358 nodeMask.setOff(npos);
1359 indexList.push_back(npos);
1364 segments.push_back(segment);
1369 template<
typename NodeType>
1377 : mNodes(!nodes.empty() ? &nodes.front() : nullptr)
1378 , mNodeMaskArray(nodeMaskArray)
1383 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1384 NodeType& node = *mNodes[n];
1388 Coord& origin =
const_cast<Coord&
>(node.origin());
1389 origin[0] =
static_cast<int>(n);
1398 template<
typename TreeType,
typename NodeType>
1408 , mNodeMaskArray(nodeMaskArray)
1416 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1419 if (segments.empty())
continue;
1421 std::vector<std::set<NodeMaskSegmentType*> > connections(segments.size());
1423 Coord ijk = segments[0]->origin;
1425 const NodeType* node = acc.template probeConstNode<NodeType>(ijk);
1426 if (!node)
continue;
1430 ijk[2] += NodeType::DIM;
1431 const NodeType* nodeZUp = acc.template probeConstNode<NodeType>(ijk);
1432 ijk[2] -= (NodeType::DIM + NodeType::DIM);
1433 const NodeType* nodeZDown = acc.template probeConstNode<NodeType>(ijk);
1434 ijk[2] += NodeType::DIM;
1436 ijk[1] += NodeType::DIM;
1437 const NodeType* nodeYUp = acc.template probeConstNode<NodeType>(ijk);
1438 ijk[1] -= (NodeType::DIM + NodeType::DIM);
1439 const NodeType* nodeYDown = acc.template probeConstNode<NodeType>(ijk);
1440 ijk[1] += NodeType::DIM;
1442 ijk[0] += NodeType::DIM;
1443 const NodeType* nodeXUp = acc.template probeConstNode<NodeType>(ijk);
1444 ijk[0] -= (NodeType::DIM + NodeType::DIM);
1445 const NodeType* nodeXDown = acc.template probeConstNode<NodeType>(ijk);
1446 ijk[0] += NodeType::DIM;
1448 const Index startPos = node->getValueMask().findFirstOn();
1449 for (
Index pos = startPos; pos < NodeMaskType::SIZE; ++pos) {
1451 if (!node->isValueOn(pos))
continue;
1453 ijk = NodeType::offsetToLocalCoord(pos);
1455 #ifdef _MSC_FULL_VER
1456 #if _MSC_FULL_VER >= 190000000 && _MSC_FULL_VER < 190024210
1458 volatile Index npos = 0;
1467 npos = pos + (NodeType::DIM - 1);
1468 if (nodeZDown && nodeZDown->isValueOn(npos)) {
1470 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeZDown)], npos);
1471 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1472 connections[idx].insert(nsegment);
1474 }
else if (ijk[2] == (NodeType::DIM - 1)) {
1475 npos = pos - (NodeType::DIM - 1);
1476 if (nodeZUp && nodeZUp->isValueOn(npos)) {
1478 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeZUp)], npos);
1479 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1480 connections[idx].insert(nsegment);
1485 npos = pos + (NodeType::DIM - 1) * NodeType::DIM;
1486 if (nodeYDown && nodeYDown->isValueOn(npos)) {
1488 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeYDown)], npos);
1489 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1490 connections[idx].insert(nsegment);
1492 }
else if (ijk[1] == (NodeType::DIM - 1)) {
1493 npos = pos - (NodeType::DIM - 1) * NodeType::DIM;
1494 if (nodeYUp && nodeYUp->isValueOn(npos)) {
1496 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeYUp)], npos);
1497 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1498 connections[idx].insert(nsegment);
1503 npos = pos + (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1504 if (nodeXDown && nodeXDown->isValueOn(npos)) {
1506 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeXDown)], npos);
1507 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1508 connections[idx].insert(nsegment);
1510 }
else if (ijk[0] == (NodeType::DIM - 1)) {
1511 npos = pos - (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1512 if (nodeXUp && nodeXUp->isValueOn(npos)) {
1514 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeXUp)], npos);
1515 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1516 connections[idx].insert(nsegment);
1521 for (
size_t i = 0, I = connections.size(); i < I; ++i) {
1523 typename std::set<NodeMaskSegmentType*>::iterator
1524 it = connections[i].begin(), end = connections[i].end();
1526 std::vector<NodeMaskSegmentType*>& segmentConnections = segments[i]->connections;
1527 segmentConnections.reserve(connections.size());
1528 for (; it != end; ++it) {
1529 segmentConnections.push_back(*it);
1537 static inline size_t getNodeOffset(
const NodeType& node) {
1538 return static_cast<size_t>(node.origin()[0]);
1541 static inline NodeMaskSegmentType*
1542 findNodeMaskSegment(NodeMaskSegmentVector& segments,
Index pos)
1544 NodeMaskSegmentType* segment =
nullptr;
1546 for (
size_t n = 0, N = segments.size(); n < N; ++n) {
1547 if (segments[n]->mask.isOn(pos)) {
1548 segment = segments[n].get();
1557 findNodeMaskSegmentIndex(NodeMaskSegmentVector& segments,
Index pos)
1559 for (
Index n = 0, N =
Index(segments.size()); n < N; ++n) {
1560 if (segments[n]->mask.isOn(pos))
return n;
1565 TreeType
const *
const mTree;
1566 NodeMaskSegmentVector *
const mNodeMaskArray;
1570 template<
typename TreeType>
1578 : mSegments(!segments.empty() ? &segments.front() : nullptr)
1579 , mTree(new TreeType(false))
1584 : mSegments(rhs.mSegments)
1585 , mTree(new TreeType(false))
1597 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1600 node->getValueMask() |= segment.
mask;
1605 NodeMaskSegmentType *
const *
const mSegments;
1613 template<
typename TreeType>
1620 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1626 std::vector<BoolLeafNodeType*>& maskNodes)
1627 : mDistTree(&distTree)
1628 , mMaskTree(&maskTree)
1629 , mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
1630 , mNewMaskTree(false)
1635 : mDistTree(rhs.mDistTree)
1636 , mMaskTree(rhs.mMaskTree)
1637 , mMaskNodes(rhs.mMaskNodes)
1638 , mNewMaskTree(false)
1654 NodeMaskType maskZUp, maskZDown, maskYUp, maskYDown, maskXUp, maskXDown;
1656 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1659 if (maskNode.isEmpty())
continue;
1661 Coord ijk = maskNode.origin(), nijk;
1664 if (!distNode)
continue;
1666 const ValueType *dataZUp =
nullptr, *dataZDown =
nullptr,
1667 *dataYUp =
nullptr, *dataYDown =
nullptr,
1668 *dataXUp =
nullptr, *dataXDown =
nullptr;
1670 ijk[2] += NodeType::DIM;
1671 getData(ijk, distAcc, maskAcc, maskZUp, dataZUp);
1672 ijk[2] -= (NodeType::DIM + NodeType::DIM);
1673 getData(ijk, distAcc, maskAcc, maskZDown, dataZDown);
1674 ijk[2] += NodeType::DIM;
1676 ijk[1] += NodeType::DIM;
1677 getData(ijk, distAcc, maskAcc, maskYUp, dataYUp);
1678 ijk[1] -= (NodeType::DIM + NodeType::DIM);
1679 getData(ijk, distAcc, maskAcc, maskYDown, dataYDown);
1680 ijk[1] += NodeType::DIM;
1682 ijk[0] += NodeType::DIM;
1683 getData(ijk, distAcc, maskAcc, maskXUp, dataXUp);
1684 ijk[0] -= (NodeType::DIM + NodeType::DIM);
1685 getData(ijk, distAcc, maskAcc, maskXDown, dataXDown);
1686 ijk[0] += NodeType::DIM;
1688 for (
typename BoolLeafNodeType::ValueOnIter it = maskNode.beginValueOn(); it; ++it) {
1690 const Index pos = it.pos();
1691 const ValueType val = std::abs(distNode->getValue(pos));
1693 ijk = BoolLeafNodeType::offsetToLocalCoord(pos);
1694 nijk = ijk + maskNode.origin();
1696 if (dataZUp && ijk[2] == (BoolLeafNodeType::DIM - 1)) {
1697 const Index npos = pos - (NodeType::DIM - 1);
1698 if (maskZUp.isOn(npos) && std::abs(dataZUp[npos]) > val) {
1699 newMaskAcc.
setValueOn(nijk.offsetBy(0, 0, 1));
1701 }
else if (dataZDown && ijk[2] == 0) {
1702 const Index npos = pos + (NodeType::DIM - 1);
1703 if (maskZDown.isOn(npos) && std::abs(dataZDown[npos]) > val) {
1704 newMaskAcc.
setValueOn(nijk.offsetBy(0, 0, -1));
1708 if (dataYUp && ijk[1] == (BoolLeafNodeType::DIM - 1)) {
1709 const Index npos = pos - (NodeType::DIM - 1) * NodeType::DIM;
1710 if (maskYUp.isOn(npos) && std::abs(dataYUp[npos]) > val) {
1711 newMaskAcc.
setValueOn(nijk.offsetBy(0, 1, 0));
1713 }
else if (dataYDown && ijk[1] == 0) {
1714 const Index npos = pos + (NodeType::DIM - 1) * NodeType::DIM;
1715 if (maskYDown.isOn(npos) && std::abs(dataYDown[npos]) > val) {
1716 newMaskAcc.
setValueOn(nijk.offsetBy(0, -1, 0));
1720 if (dataXUp && ijk[0] == (BoolLeafNodeType::DIM - 1)) {
1721 const Index npos = pos - (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1722 if (maskXUp.isOn(npos) && std::abs(dataXUp[npos]) > val) {
1723 newMaskAcc.
setValueOn(nijk.offsetBy(1, 0, 0));
1725 }
else if (dataXDown && ijk[0] == 0) {
1726 const Index npos = pos + (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1727 if (maskXDown.isOn(npos) && std::abs(dataXDown[npos]) > val) {
1728 newMaskAcc.
setValueOn(nijk.offsetBy(-1, 0, 0));
1741 const ValueType*& data)
1745 data = node->buffer().data();
1746 mask = node->getValueMask();
1747 const BoolLeafNodeType* maskNodePt = maskAcc.
probeConstLeaf(ijk);
1748 if (maskNodePt) mask -= maskNodePt->getValueMask();
1752 TreeType
const *
const mDistTree;
1753 BoolTreeType *
const mMaskTree;
1754 BoolLeafNodeType **
const mMaskNodes;
1756 BoolTreeType mNewMaskTree;
1760 template<
typename TreeType>
1769 : mTree(&tree), mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
1777 std::vector<Index> indexList;
1778 indexList.reserve(NodeMaskType::SIZE);
1780 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1785 if (!distNode)
continue;
1790 for (
Index pos = narrowbandMask.findFirstOn(); pos < NodeMaskType::SIZE; ++pos) {
1791 if (narrowbandMask.isOn(pos)) indexList.push_back(pos);
1794 mask -= narrowbandMask;
1797 const ValueType* data = distNode->buffer().data();
1800 while (!indexList.empty()) {
1802 const Index pos = indexList.back();
1803 indexList.pop_back();
1805 if (narrowbandMask.isOn(pos))
continue;
1806 narrowbandMask.setOn(pos);
1808 const ValueType dist = std::abs(data[pos]);
1810 ijk = LeafNodeType::offsetToLocalCoord(pos);
1812 Index npos = pos - 1;
1813 if (ijk[2] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1815 indexList.push_back(npos);
1819 if ((ijk[2] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1820 && std::abs(data[npos]) > dist)
1823 indexList.push_back(npos);
1826 npos = pos - LeafNodeType::DIM;
1827 if (ijk[1] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1829 indexList.push_back(npos);
1832 npos = pos + LeafNodeType::DIM;
1833 if ((ijk[1] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1834 && std::abs(data[npos]) > dist)
1837 indexList.push_back(npos);
1840 npos = pos - LeafNodeType::DIM * LeafNodeType::DIM;
1841 if (ijk[0] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1843 indexList.push_back(npos);
1846 npos = pos + LeafNodeType::DIM * LeafNodeType::DIM;
1847 if ((ijk[0] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1848 && std::abs(data[npos]) > dist)
1851 indexList.push_back(npos);
1862 template<
typename TreeType>
1865 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1870 : mTree(&tree), mSegments(!segments.empty() ? &segments.front() : nullptr)
1876 const TreeType& distTree = *mTree;
1877 std::vector<BoolLeafNodeType*> nodes;
1879 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1888 candidateMask.getNodes(nodes);
1889 if (nodes.empty())
break;
1891 const tbb::blocked_range<size_t> nodeRange(0, nodes.size());
1895 narrowBandMask.topologyUnion(candidateMask);
1898 tbb::parallel_reduce(nodeRange, op);
1902 candidateMask.clear();
1913 template<
typename TreeType>
1925 , mSegments(!segments.empty() ? &segments.front() : nullptr)
1931 std::vector<const InternalNodeType*> nodes;
1932 tree.getNodes(nodes);
1934 if (!nodes.empty()) {
1936 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1942 std::vector<const LeafNodeType*> nodes;
1943 tree.getNodes(nodes);
1944 if (!nodes.empty()) {
1946 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1951 mMinValue = minSDFValue;
1955 const ValueType interiorValue = -std::abs(mMinValue);
1956 const ValueType exteriorValue = std::abs(mTree->background());
1957 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1964 TreeType
const *
const mTree;
1965 TreeTypePtr *
const mSegments;
1966 ValueType mMinValue;
1970 template<
typename TreeType>
1977 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1981 MaskedCopy(
const TreeType& tree, std::vector<TreeTypePtr>& segments,
1982 std::vector<BoolTreeTypePtr>& masks)
1984 , mSegments(!segments.empty() ? &segments.front() : nullptr)
1985 , mMasks(!masks.empty() ? &masks.front() : nullptr)
1991 std::vector<const BoolLeafNodeType*> nodes;
1993 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1998 mask.getNodes(nodes);
2000 Copy op(*mTree, nodes);
2001 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
2002 mSegments[n] = op.outputTree();
2009 Copy(
const TreeType& inputTree, std::vector<const BoolLeafNodeType*>& maskNodes)
2010 : mInputTree(&inputTree)
2011 , mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
2012 , mOutputTreePtr(new TreeType(inputTree.background()))
2016 Copy(
const Copy& rhs, tbb::split)
2017 : mInputTree(rhs.mInputTree)
2018 , mMaskNodes(rhs.mMaskNodes)
2019 , mOutputTreePtr(new TreeType(mInputTree->background()))
2023 TreeTypePtr& outputTree() {
return mOutputTreePtr; }
2025 void join(Copy& rhs) { mOutputTreePtr->merge(*rhs.mOutputTreePtr); }
2027 void operator()(
const tbb::blocked_range<size_t>& range) {
2029 tree::ValueAccessor<const TreeType> inputAcc(*mInputTree);
2030 tree::ValueAccessor<TreeType> outputAcc(*mOutputTreePtr);
2032 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
2034 const BoolLeafNodeType& maskNode = *mMaskNodes[n];
2035 if (maskNode.isEmpty())
continue;
2037 const Coord& ijk = maskNode.origin();
2039 const LeafNodeType* inputNode = inputAcc.probeConstLeaf(ijk);
2042 LeafNodeType* outputNode = outputAcc.touchLeaf(ijk);
2044 for (
typename BoolLeafNodeType::ValueOnCIter it = maskNode.cbeginValueOn();
2047 const Index idx = it.pos();
2048 outputNode->setValueOn(idx, inputNode->getValue(idx));
2051 const int valueDepth = inputAcc.getValueDepth(ijk);
2052 if (valueDepth >= 0) {
2053 outputAcc.addTile(TreeType::RootNodeType::LEVEL - valueDepth,
2054 ijk, inputAcc.getValue(ijk),
true);
2061 TreeType
const *
const mInputTree;
2062 BoolLeafNodeType
const *
const *
const mMaskNodes;
2063 TreeTypePtr mOutputTreePtr;
2066 TreeType
const *
const mTree;
2067 TreeTypePtr *
const mSegments;
2068 BoolTreeTypePtr *
const mMasks;
2075 template<
typename VolumePtrType>
2079 : mSegments(!segments.empty() ? &segments.front() : nullptr)
2080 , mCountArray(countArray)
2085 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
2086 mCountArray[n] = mSegments[n]->activeVoxelCount();
2099 inline bool operator() (
const size_t& lhs,
const size_t& rhs)
const
2101 return (mCountArray[lhs] > mCountArray[rhs]);
2110 template<
typename TreeType>
2117 {
return maskTree; }
2122 template<
typename TreeType>
2129 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2136 maskGrid->setTransform(grid.transform().
copy());
2142 maskGrid->setTransform(grid.transform().
copy());
2143 maskGrid->insertMeta(grid);
2155 template <
class Gr
idType>
2159 using ValueType =
typename GridType::ValueType;
2160 using TreeType =
typename GridType::TreeType;
2161 using LeafNodeType =
typename TreeType::LeafNodeType;
2162 using RootNodeType =
typename TreeType::RootNodeType;
2163 using NodeChainType =
typename RootNodeType::NodeChainType;
2164 using InternalNodeType =
typename boost::mpl::at<NodeChainType, boost::mpl::int_<1>>::type;
2168 TreeType& tree = grid.tree();
2170 size_t numLeafNodes = 0, numInternalNodes = 0;
2172 std::vector<LeafNodeType*> nodes;
2173 std::vector<size_t> leafnodeCount;
2177 std::vector<InternalNodeType*> internalNodes;
2178 tree.getNodes(internalNodes);
2180 numInternalNodes = internalNodes.size();
2182 leafnodeCount.push_back(0);
2183 for (
size_t n = 0; n < numInternalNodes; ++n) {
2184 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
2187 numLeafNodes = leafnodeCount.back();
2190 nodes.reserve(numLeafNodes);
2192 for (
size_t n = 0; n < numInternalNodes; ++n) {
2193 internalNodes[n]->stealNodes(nodes, tree.background(),
false);
2201 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), minOp);
2205 if (minSDFValue > ValueType(0.0)) {
2207 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
2211 cutoffDistance = -std::abs(cutoffDistance);
2212 cutoffDistance = minSDFValue > cutoffDistance ? minSDFValue : cutoffDistance;
2218 tbb::parallel_for(tbb::blocked_range<size_t>(0, nodes.size()),
2222 typename TreeType::Ptr newTree(
new TreeType(ValueType(0.0)));
2225 *newTree, &nodes[0], &leafnodeCount[0], 0);
2226 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
2229 std::vector<InternalNodeType*> internalNodes;
2230 newTree->getNodes(internalNodes);
2232 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalNodes.size()),
2234 tree, &internalNodes[0]));
2239 typename TreeType::ValueAllIter it(*newTree);
2240 it.setMaxDepth(TreeType::ValueAllIter::LEAF_DEPTH - 2);
2243 if (acc.
getValue(it.getCoord()) < ValueType(0.0)) {
2244 it.setValue(ValueType(1.0));
2245 it.setActiveState(
true);
2253 typename TreeType::ValueAllIter it(tree);
2254 it.setMaxDepth(TreeType::ValueAllIter::ROOT_DEPTH);
2256 if (it.getValue() < ValueType(0.0)) {
2257 newTree->addTile(TreeType::ValueAllIter::ROOT_LEVEL, it.getCoord(),
2258 ValueType(1.0),
true);
2263 grid.setTree(newTree);
2271 template <
class Gr
idOrTreeType>
2272 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2273 sdfInteriorMask(
const GridOrTreeType& volume,
typename GridOrTreeType::ValueType isovalue)
2278 using BoolTreePtrType =
typename TreeType::template ValueConverter<bool>::Type::Ptr;
2286 template<
typename Gr
idOrTreeType>
2287 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2289 typename GridOrTreeType::ValueType isovalue,
2296 using CharTreePtrType =
typename TreeType::template ValueConverter<char>::Type::Ptr;
2298 tree, isovalue, fillMask);
2300 using BoolTreePtrType =
typename TreeType::template ValueConverter<bool>::Type::Ptr;
2311 template<
typename Gr
idOrTreeType>
2312 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2318 std::vector<const typename TreeType::LeafNodeType*> nodes;
2319 tree.getNodes(nodes);
2321 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2322 typename BoolTreeType::Ptr mask(
new BoolTreeType(
false));
2325 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
2335 template<
typename Gr
idOrTreeType>
2338 std::vector<
typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr>& masks)
2341 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2342 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2343 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
2346 using NodeMaskSegmentPtrType =
typename NodeMaskSegmentType::Ptr;
2347 using NodeMaskSegmentPtrVector =
typename std::vector<NodeMaskSegmentPtrType>;
2348 using NodeMaskSegmentRawPtrVector =
typename std::vector<NodeMaskSegmentType*>;
2354 BoolTreeType topologyMask(tree,
false,
TopologyCopy());
2359 if (topologyMask.hasActiveTiles()) {
2360 topologyMask.voxelizeActiveTiles();
2363 std::vector<BoolLeafNodeType*> leafnodes;
2364 topologyMask.getNodes(leafnodes);
2366 if (leafnodes.empty())
return;
2371 std::unique_ptr<NodeMaskSegmentPtrVector[]> nodeSegmentArray(
2372 new NodeMaskSegmentPtrVector[leafnodes.size()]);
2374 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
2376 leafnodes, nodeSegmentArray.get()));
2381 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
2383 topologyMask, nodeSegmentArray.get()));
2385 topologyMask.clear();
2387 size_t nodeSegmentCount = 0;
2388 for (
size_t n = 0, N = leafnodes.size(); n < N; ++n) {
2389 nodeSegmentCount += nodeSegmentArray[n].size();
2394 std::deque<NodeMaskSegmentRawPtrVector> nodeSegmentGroups;
2396 NodeMaskSegmentType* nextSegment = nodeSegmentArray[0][0].get();
2397 while (nextSegment) {
2399 nodeSegmentGroups.push_back(NodeMaskSegmentRawPtrVector());
2401 std::vector<NodeMaskSegmentType*>& segmentGroup = nodeSegmentGroups.back();
2402 segmentGroup.reserve(nodeSegmentCount);
2404 std::deque<NodeMaskSegmentType*> segmentQueue;
2405 segmentQueue.push_back(nextSegment);
2406 nextSegment =
nullptr;
2408 while (!segmentQueue.empty()) {
2410 NodeMaskSegmentType* segment = segmentQueue.back();
2411 segmentQueue.pop_back();
2413 if (segment->visited)
continue;
2414 segment->visited =
true;
2416 segmentGroup.push_back(segment);
2419 std::vector<NodeMaskSegmentType*>& connections = segment->connections;
2420 for (
size_t n = 0, N = connections.size(); n < N; ++n) {
2421 if (!connections[n]->visited) segmentQueue.push_back(connections[n]);
2426 for (
size_t n = 0, N = leafnodes.size(); n < N; ++n) {
2427 NodeMaskSegmentPtrVector& nodeSegments = nodeSegmentArray[n];
2428 for (
size_t i = 0, I = nodeSegments.size(); i < I; ++i) {
2429 if (!nodeSegments[i]->visited) nextSegment = nodeSegments[i].get();
2436 if (nodeSegmentGroups.size() == 1) {
2438 BoolTreePtrType mask(
new BoolTreeType(tree,
false,
TopologyCopy()));
2442 if (mask->hasActiveTiles()) {
2443 mask->voxelizeActiveTiles();
2450 }
else if (nodeSegmentGroups.size() > 1) {
2452 for (
size_t n = 0, N = nodeSegmentGroups.size(); n < N; ++n) {
2454 NodeMaskSegmentRawPtrVector& segmentGroup = nodeSegmentGroups[n];
2457 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, segmentGroup.size()), op);
2461 volume, op.
mask()));
2467 if (masks.size() > 1) {
2468 const size_t segmentCount = masks.size();
2470 std::unique_ptr<size_t[]> segmentOrderArray(
new size_t[segmentCount]);
2471 std::unique_ptr<size_t[]> voxelCountArray(
new size_t[segmentCount]);
2473 for (
size_t n = 0; n < segmentCount; ++n) {
2474 segmentOrderArray[n] = n;
2477 tbb::parallel_for(tbb::blocked_range<size_t>(0, segmentCount),
2479 masks, voxelCountArray.get()));
2481 size_t *begin = segmentOrderArray.get();
2483 voxelCountArray.get()));
2485 std::vector<BoolTreePtrType> orderedMasks;
2486 orderedMasks.reserve(masks.size());
2488 for (
size_t n = 0; n < segmentCount; ++n) {
2489 orderedMasks.push_back(masks[segmentOrderArray[n]]);
2492 masks.swap(orderedMasks);
2498 template<
typename Gr
idOrTreeType>
2501 std::vector<typename GridOrTreeType::Ptr>& segments)
2504 using TreePtrType =
typename TreeType::Ptr;
2505 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2506 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2511 std::vector<BoolTreePtrType> maskSegmentArray;
2516 const size_t numSegments =
std::max(
size_t(1), maskSegmentArray.size());
2517 std::vector<TreePtrType> outputSegmentArray(numSegments);
2519 if (maskSegmentArray.empty()) {
2522 outputSegmentArray[0] = TreePtrType(
new TreeType(inputTree.background()));
2523 }
else if (numSegments == 1) {
2525 TreePtrType segment(
new TreeType(inputTree));
2528 if (segment->leafCount() != inputTree.leafCount()) {
2529 segment->topologyIntersection(*maskSegmentArray[0]);
2531 outputSegmentArray[0] = segment;
2533 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
2534 tbb::parallel_for(segmentRange,
2539 for (
auto& segment : outputSegmentArray) {
2547 template<
typename Gr
idOrTreeType>
2549 segmentSDF(
const GridOrTreeType& volume, std::vector<typename GridOrTreeType::Ptr>& segments)
2552 using TreePtrType =
typename TreeType::Ptr;
2553 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2554 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2562 std::vector<BoolTreePtrType> maskSegmentArray;
2565 const size_t numSegments =
std::max(
size_t(1), maskSegmentArray.size());
2566 std::vector<TreePtrType> outputSegmentArray(numSegments);
2568 if (maskSegmentArray.empty()) {
2571 outputSegmentArray[0] = TreePtrType(
new TreeType(inputTree.background()));
2573 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
2576 tbb::parallel_for(segmentRange,
2582 inputTree, outputSegmentArray, maskSegmentArray));
2584 tbb::parallel_for(segmentRange,
2588 for (
auto& segment : outputSegmentArray) {
2599 #endif // OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED