11 #ifndef OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
12 #define OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
19 #include <tbb/blocked_range.h>
20 #include <tbb/parallel_for.h>
21 #include <tbb/parallel_reduce.h>
22 #include <tbb/parallel_sort.h>
42 template<
typename Gr
idType>
43 inline typename GridType::ValueType lsutilGridMax()
48 template<
typename Gr
idType>
49 inline typename GridType::ValueType lsutilGridZero()
51 return zeroVal<typename GridType::ValueType>();
74 template<
class Gr
idType>
78 typename GridType::ValueType cutoffDistance = lsutilGridMax<GridType>());
91 template<
class Gr
idOrTreeType>
92 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
94 const GridOrTreeType& volume,
95 typename GridOrTreeType::ValueType isovalue = lsutilGridZero<GridOrTreeType>());
118 template<
typename Gr
idOrTreeType>
119 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
121 const GridOrTreeType& volume,
122 typename GridOrTreeType::ValueType isovalue = lsutilGridZero<GridOrTreeType>(),
123 const typename TreeAdapter<GridOrTreeType>::TreeType::template ValueConverter<bool>::Type*
132 template<
typename Gr
idOrTreeType>
133 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
142 template<
typename Gr
idOrTreeType>
145 std::vector<
typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr>& masks);
155 template<
typename Gr
idOrTreeType>
158 std::vector<typename GridOrTreeType::Ptr>& segments);
169 template<
typename Gr
idOrTreeType>
171 segmentSDF(
const GridOrTreeType& volume, std::vector<typename GridOrTreeType::Ptr>& segments);
180 namespace level_set_util_internal {
183 template<
typename LeafNodeType>
191 : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
195 void operator()(
const tbb::blocked_range<size_t>& range)
const {
199 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
201 mMaskNodes[n] =
nullptr;
202 const LeafNodeType& node = *mNodes[n];
210 const ValueType* values = &node.getValue(0);
211 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
212 if (values[i] < mIsovalue) maskNodePt->
setValueOn(i,
true);
216 mMaskNodes[n] = maskNodePt;
217 maskNodePt =
nullptr;
221 if (maskNodePt)
delete maskNodePt;
224 LeafNodeType
const *
const *
const mNodes;
230 template<
typename TreeType,
typename InternalNodeType>
236 : mTree(&tree), mMaskNodes(maskNodes), mIsovalue(isovalue) { }
238 void operator()(
const tbb::blocked_range<size_t>& range)
const {
240 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
241 typename InternalNodeType::ValueAllIter it = mMaskNodes[n]->beginValueAll();
243 if (acc.
getValue(it.getCoord()) < mIsovalue) {
257 template<
typename TreeType>
264 const size_t * nodexIndexMap,
ValueType background)
265 : mNewTree(background)
268 , mNodeIndexMap(nodexIndexMap)
273 : mNewTree(rhs.mNewTree.background())
276 , mNodeIndexMap(rhs.mNodeIndexMap)
285 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
286 for (
size_t i = mNodeIndexMap[n], I = mNodeIndexMap[n + 1]; i < I; ++i) {
287 if (mNodes[i] !=
nullptr) acc.
addLeaf(mNodes[i]);
291 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
301 TreeType *
const mTreePt;
302 LeafNodeType **
const mNodes;
303 size_t const *
const mNodeIndexMap;
308 template<
typename LeafNodeType>
316 : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
320 void operator()(
const tbb::blocked_range<size_t>& range)
const {
324 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
326 mMaskNodes[n] =
nullptr;
327 const LeafNodeType& node = *mNodes[n];
335 typename LeafNodeType::ValueOnCIter it;
336 for (it = node.cbeginValueOn(); it; ++it) {
337 maskNodePt->
setValueOn(it.pos(), ((*it - mIsovalue) < 0.0) ? 0 : 1);
341 mMaskNodes[n] = maskNodePt;
342 maskNodePt =
nullptr;
346 if (maskNodePt)
delete maskNodePt;
349 LeafNodeType
const *
const *
const mNodes;
355 template<
typename LeafNodeType>
361 void operator()(
const tbb::blocked_range<size_t>& range)
const {
362 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
364 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
365 values[i] = values[i] < 0 ? 1 : -1;
374 template<
typename LeafNodeType>
392 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
393 const ValueType* data = mNodes[n]->buffer().data();
394 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
395 minValue =
std::min(minValue, data[i]);
404 LeafNodeType
const *
const *
const mNodes;
408 template<
typename InternalNodeType>
426 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
427 typename InternalNodeType::ValueAllCIter it = mNodes[n]->beginValueAll();
438 InternalNodeType
const *
const *
const mNodes;
442 template<
typename LeafNodeType>
448 : mNodes(nodes), mWeight(
ValueType(1.0) / cutoffDistance)
452 void operator()(
const tbb::blocked_range<size_t>& range)
const {
454 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
456 LeafNodeType& node = *mNodes[n];
459 ValueType* values = node.buffer().data();
460 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
462 if (values[i] >
ValueType(0.0)) node.setValueOn(i);
465 if (node.onVoxelCount() == 0) {
477 template<
typename TreeType,
typename InternalNodeType>
481 : mTree(&tree), mNodes(nodes) { }
483 void operator()(
const tbb::blocked_range<size_t>& range)
const {
485 using ValueType =
typename TreeType::ValueType;
488 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
489 typename InternalNodeType::ValueAllIter it = mNodes[n]->beginValueAll();
491 if (acc.
getValue(it.getCoord()) < ValueType(0.0)) {
492 it.setValue(ValueType(1.0));
504 template<
typename TreeType>
509 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
515 , mFillMask(&fillMask)
516 , mFillNodes(fillNodes)
517 , mNewNodes(newNodes)
518 , mIsovalue(isovalue)
522 void operator()(
const tbb::blocked_range<size_t>& range)
const {
527 std::unique_ptr<char[]> valueMask(
new char[BoolLeafNodeType::SIZE]);
529 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
531 mNewNodes[n] =
nullptr;
533 const Coord& origin = node.origin();
535 const bool denseNode = node.isDense();
540 int denseNeighbors = 0;
544 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
547 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
550 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
553 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
556 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
559 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
561 if (denseNeighbors == 6)
continue;
565 memset(valueMask.get(), 0,
sizeof(
char) * BoolLeafNodeType::SIZE);
567 const typename TreeType::LeafNodeType* distNode = distAcc.
probeConstLeaf(origin);
571 bool earlyTermination =
false;
575 evalInternalNeighborsP(valueMask.get(), node, *distNode);
576 evalInternalNeighborsN(valueMask.get(), node, *distNode);
577 }
else if (distAcc.
getValue(origin) > mIsovalue) {
578 earlyTermination = evalInternalNeighborsP(valueMask.get(), node);
579 if (!earlyTermination) {
580 earlyTermination = evalInternalNeighborsN(valueMask.get(), node);
587 if (!earlyTermination) {
588 evalExternalNeighborsX<true>(valueMask.get(), node, maskAcc, distAcc);
589 evalExternalNeighborsX<false>(valueMask.get(), node, maskAcc, distAcc);
590 evalExternalNeighborsY<true>(valueMask.get(), node, maskAcc, distAcc);
591 evalExternalNeighborsY<false>(valueMask.get(), node, maskAcc, distAcc);
592 evalExternalNeighborsZ<true>(valueMask.get(), node, maskAcc, distAcc);
593 evalExternalNeighborsZ<false>(valueMask.get(), node, maskAcc, distAcc);
598 int numBoundaryValues = 0;
599 for (
Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
600 numBoundaryValues += valueMask[i] == 1;
603 if (numBoundaryValues > 0) {
605 for (
Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
606 if (valueMask[i] == 1) mNewNodes[n]->setValueOn(i);
614 void evalInternalNeighborsP(
char* valueMask,
const BoolLeafNodeType& node,
615 const LeafNodeType& distNode)
const
617 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
618 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
619 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
620 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
621 for (
Index z = 0; z < BoolLeafNodeType::DIM - 1; ++z) {
622 const Index pos = yPos + z;
624 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
626 if (!node.isValueOn(pos + 1) && distNode.getValue(pos + 1) > mIsovalue) {
633 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
634 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
635 for (
Index y = 0; y < BoolLeafNodeType::DIM - 1; ++y) {
636 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
637 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
638 const Index pos = yPos + z;
640 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
642 if (!node.isValueOn(pos + BoolLeafNodeType::DIM) &&
643 distNode.getValue(pos + BoolLeafNodeType::DIM) > mIsovalue) {
650 for (
Index x = 0; x < BoolLeafNodeType::DIM - 1; ++x) {
651 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
652 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
653 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
654 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
655 const Index pos = yPos + z;
657 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
659 if (!node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
660 (distNode.getValue(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)
670 bool evalInternalNeighborsP(
char* valueMask,
const BoolLeafNodeType& node)
const {
672 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
673 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
674 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
675 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
676 for (
Index z = 0; z < BoolLeafNodeType::DIM - 1; ++z) {
677 const Index pos = yPos + z;
679 if (node.isValueOn(pos) && !node.isValueOn(pos + 1)) {
687 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
688 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
689 for (
Index y = 0; y < BoolLeafNodeType::DIM - 1; ++y) {
690 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
691 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
692 const Index pos = yPos + z;
694 if (node.isValueOn(pos) && !node.isValueOn(pos + BoolLeafNodeType::DIM)) {
702 for (
Index x = 0; x < BoolLeafNodeType::DIM - 1; ++x) {
703 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
704 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
705 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
706 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
707 const Index pos = yPos + z;
709 if (node.isValueOn(pos) &&
710 !node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
723 void evalInternalNeighborsN(
char* valueMask,
const BoolLeafNodeType& node,
724 const LeafNodeType& distNode)
const
726 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
727 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
728 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
729 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
730 for (
Index z = 1; z < BoolLeafNodeType::DIM; ++z) {
731 const Index pos = yPos + z;
733 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
735 if (!node.isValueOn(pos - 1) && distNode.getValue(pos - 1) > mIsovalue) {
742 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
743 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
744 for (
Index y = 1; y < BoolLeafNodeType::DIM; ++y) {
745 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
746 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
747 const Index pos = yPos + z;
749 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
751 if (!node.isValueOn(pos - BoolLeafNodeType::DIM) &&
752 distNode.getValue(pos - BoolLeafNodeType::DIM) > mIsovalue) {
759 for (
Index x = 1; x < BoolLeafNodeType::DIM; ++x) {
760 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
761 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
762 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
763 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
764 const Index pos = yPos + z;
766 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
768 if (!node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
769 (distNode.getValue(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)
780 bool evalInternalNeighborsN(
char* valueMask,
const BoolLeafNodeType& node)
const {
782 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
783 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
784 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
785 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
786 for (
Index z = 1; z < BoolLeafNodeType::DIM; ++z) {
787 const Index pos = yPos + z;
789 if (node.isValueOn(pos) && !node.isValueOn(pos - 1)) {
797 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
798 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
799 for (
Index y = 1; y < BoolLeafNodeType::DIM; ++y) {
800 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
801 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
802 const Index pos = yPos + z;
804 if (node.isValueOn(pos) && !node.isValueOn(pos - BoolLeafNodeType::DIM)) {
812 for (
Index x = 1; x < BoolLeafNodeType::DIM; ++x) {
813 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
814 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
815 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
816 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
817 const Index pos = yPos + z;
819 if (node.isValueOn(pos) &&
820 !node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
835 template<
bool UpWind>
836 void evalExternalNeighborsX(
char* valueMask,
const BoolLeafNodeType& node,
837 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
838 const tree::ValueAccessor<const TreeType>& distAcc)
const {
840 const Coord& origin = node.origin();
841 Coord ijk(0, 0, 0), nijk;
846 ijk[0] = int(BoolLeafNodeType::DIM) - 1;
849 const Index xPos = ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM));
851 for (ijk[1] = 0; ijk[1] < int(BoolLeafNodeType::DIM); ++ijk[1]) {
852 const Index yPos = xPos + (ijk[1] << int(BoolLeafNodeType::LOG2DIM));
854 for (ijk[2] = 0; ijk[2] < int(BoolLeafNodeType::DIM); ++ijk[2]) {
855 const Index pos = yPos + ijk[2];
857 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
859 nijk = origin + ijk.offsetBy(step, 0, 0);
861 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
870 template<
bool UpWind>
871 void evalExternalNeighborsY(
char* valueMask,
const BoolLeafNodeType& node,
872 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
873 const tree::ValueAccessor<const TreeType>& distAcc)
const {
875 const Coord& origin = node.origin();
876 Coord ijk(0, 0, 0), nijk;
881 ijk[1] = int(BoolLeafNodeType::DIM) - 1;
884 const Index yPos = ijk[1] << int(BoolLeafNodeType::LOG2DIM);
886 for (ijk[0] = 0; ijk[0] < int(BoolLeafNodeType::DIM); ++ijk[0]) {
887 const Index xPos = yPos + (ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM)));
889 for (ijk[2] = 0; ijk[2] < int(BoolLeafNodeType::DIM); ++ijk[2]) {
890 const Index pos = xPos + ijk[2];
892 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
894 nijk = origin + ijk.offsetBy(0, step, 0);
895 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
904 template<
bool UpWind>
905 void evalExternalNeighborsZ(
char* valueMask,
const BoolLeafNodeType& node,
906 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
907 const tree::ValueAccessor<const TreeType>& distAcc)
const {
909 const Coord& origin = node.origin();
910 Coord ijk(0, 0, 0), nijk;
915 ijk[2] = int(BoolLeafNodeType::DIM) - 1;
918 for (ijk[0] = 0; ijk[0] < int(BoolLeafNodeType::DIM); ++ijk[0]) {
919 const Index xPos = ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM));
921 for (ijk[1] = 0; ijk[1] < int(BoolLeafNodeType::DIM); ++ijk[1]) {
922 const Index pos = ijk[2] + xPos + (ijk[1] << int(BoolLeafNodeType::LOG2DIM));
924 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
926 nijk = origin + ijk.offsetBy(0, 0, step);
927 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
937 TreeType
const *
const mTree;
938 BoolTreeType
const *
const mFillMask;
939 BoolLeafNodeType
const *
const *
const mFillNodes;
940 BoolLeafNodeType **
const mNewNodes;
941 ValueType
const mIsovalue;
947 template <
class TreeType>
948 inline typename TreeType::template ValueConverter<char>::Type::Ptr
950 const typename TreeType::template ValueConverter<bool>::Type* fillMask)
952 using LeafNodeType =
typename TreeType::LeafNodeType;
953 using RootNodeType =
typename TreeType::RootNodeType;
954 using NodeChainType =
typename RootNodeType::NodeChainType;
955 using InternalNodeType =
typename NodeChainType::template Get<1>;
957 using CharTreeType =
typename TreeType::template ValueConverter<char>::Type;
958 using CharLeafNodeType =
typename CharTreeType::LeafNodeType;
960 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
961 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
963 const TreeType* treePt = &tree;
965 size_t numLeafNodes = 0, numInternalNodes = 0;
967 std::vector<const LeafNodeType*> nodes;
968 std::vector<size_t> leafnodeCount;
972 std::vector<const InternalNodeType*> internalNodes;
973 treePt->getNodes(internalNodes);
975 numInternalNodes = internalNodes.size();
977 leafnodeCount.push_back(0);
978 for (
size_t n = 0; n < numInternalNodes; ++n) {
979 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
982 numLeafNodes = leafnodeCount.back();
985 nodes.reserve(numLeafNodes);
987 for (
size_t n = 0; n < numInternalNodes; ++n) {
988 internalNodes[n]->getNodes(nodes);
993 std::unique_ptr<CharLeafNodeType*[]> maskNodes(
new CharLeafNodeType*[numLeafNodes]);
995 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
999 typename CharTreeType::Ptr maskTree(
new CharTreeType(1));
1002 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1006 std::vector<CharLeafNodeType*> extraMaskNodes;
1010 std::vector<const BoolLeafNodeType*> fillMaskNodes;
1011 fillMask->getNodes(fillMaskNodes);
1013 std::unique_ptr<BoolLeafNodeType*[]> boundaryMaskNodes(
1014 new BoolLeafNodeType*[fillMaskNodes.size()]);
1016 tbb::parallel_for(tbb::blocked_range<size_t>(0, fillMaskNodes.size()),
1018 boundaryMaskNodes.get()));
1022 for (
size_t n = 0, N = fillMaskNodes.size(); n < N; ++n) {
1024 if (boundaryMaskNodes[n] ==
nullptr)
continue;
1026 const BoolLeafNodeType& boundaryNode = *boundaryMaskNodes[n];
1027 const Coord& origin = boundaryNode.origin();
1029 CharLeafNodeType* maskNodePt = maskAcc.
probeLeaf(origin);
1033 extraMaskNodes.push_back(maskNodePt);
1036 char* data = maskNodePt->buffer().data();
1038 typename BoolLeafNodeType::ValueOnCIter it = boundaryNode.cbeginValueOn();
1040 if (data[it.pos()] != 0) data[it.pos()] = -1;
1043 delete boundaryMaskNodes[n];
1051 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1054 if (!extraMaskNodes.empty()) {
1055 tbb::parallel_for(tbb::blocked_range<size_t>(0, extraMaskNodes.size()),
1066 template <
class TreeType>
1067 inline typename TreeType::template ValueConverter<bool>::Type::Ptr
1070 using ValueType =
typename TreeType::ValueType;
1071 using LeafNodeType =
typename TreeType::LeafNodeType;
1072 using RootNodeType =
typename TreeType::RootNodeType;
1073 using NodeChainType =
typename RootNodeType::NodeChainType;
1074 using InternalNodeType =
typename NodeChainType::template Get<1>;
1076 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1077 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1078 using BoolRootNodeType =
typename BoolTreeType::RootNodeType;
1079 using BoolNodeChainType =
typename BoolRootNodeType::NodeChainType;
1080 using BoolInternalNodeType =
typename BoolNodeChainType::template Get<1>;
1092 size_t numLeafNodes = 0, numInternalNodes = 0;
1094 std::vector<const LeafNodeType*> nodes;
1095 std::vector<size_t> leafnodeCount;
1099 std::vector<const InternalNodeType*> internalNodes;
1100 tree.getNodes(internalNodes);
1102 numInternalNodes = internalNodes.size();
1104 leafnodeCount.push_back(0);
1105 for (
size_t n = 0; n < numInternalNodes; ++n) {
1106 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
1109 numLeafNodes = leafnodeCount.back();
1112 nodes.reserve(numLeafNodes);
1114 for (
size_t n = 0; n < numInternalNodes; ++n) {
1115 internalNodes[n]->getNodes(nodes);
1120 std::unique_ptr<BoolLeafNodeType*[]> maskNodes(
new BoolLeafNodeType*[numLeafNodes]);
1122 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1127 typename BoolTreeType::Ptr maskTree(
new BoolTreeType(
false));
1130 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1134 std::vector<BoolInternalNodeType*> internalMaskNodes;
1135 maskTree->getNodes(internalMaskNodes);
1137 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalMaskNodes.size()),
1142 typename BoolTreeType::ValueAllIter it(*maskTree);
1143 it.setMaxDepth(BoolTreeType::ValueAllIter::LEAF_DEPTH - 2);
1146 if (acc.
getValue(it.getCoord()) < iso) {
1148 it.setActiveState(
true);
1156 template<
typename InputTreeType>
1161 using BoolTreeType =
typename InputTreeType::template ValueConverter<bool>::Type;
1165 const InputTreeType& inputTree,
1166 const std::vector<const InputLeafNodeType*>& inputLeafNodes,
1169 : mInputAccessor(inputTree)
1170 , mInputNodes(!inputLeafNodes.empty() ? &inputLeafNodes.front() : nullptr)
1172 , mMaskAccessor(maskTree)
1178 : mInputAccessor(rhs.mInputAccessor.tree())
1179 , mInputNodes(rhs.mInputNodes)
1181 , mMaskAccessor(mMaskTree)
1182 , mIsovalue(rhs.mIsovalue)
1193 for (
size_t n = range.begin(); mInputNodes && (n != range.end()); ++n) {
1198 else maskNodePt->setOrigin(node.origin());
1200 bool collectedData =
false;
1202 for (
typename InputLeafNodeType::ValueOnCIter it = node.cbeginValueOn(); it; ++it) {
1204 bool isUnder = *it < iso;
1206 ijk = it.getCoord();
1209 bool signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1214 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1220 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1226 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1232 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1238 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1243 collectedData =
true;
1244 maskNodePt->setValueOn(it.pos(),
true);
1248 if (collectedData) {
1249 mMaskAccessor.addLeaf(maskNodePt);
1250 maskNodePt =
nullptr;
1254 if (maskNodePt)
delete maskNodePt;
1258 mMaskAccessor.tree().merge(rhs.mMaskAccessor.
tree());
1263 InputLeafNodeType
const *
const *
const mInputNodes;
1265 BoolTreeType mMaskTree;
1268 InputValueType mIsovalue;
1275 template<
typename NodeType>
1290 template<
typename NodeType>
1295 using NodeMaskType =
typename NodeType::NodeMaskType;
1297 using NodeMaskSegmentTypePtr =
typename NodeMaskSegmentType::Ptr;
1299 NodeMaskType nodeMask(node.getValueMask());
1300 std::deque<Index> indexList;
1302 while (!nodeMask.isOff()) {
1304 NodeMaskSegmentTypePtr segment(
new NodeMaskSegmentType());
1305 segment->origin = node.origin();
1307 NodeMaskType& mask = segment->mask;
1309 indexList.push_back(nodeMask.findFirstOn());
1310 nodeMask.setOff(indexList.back());
1313 while (!indexList.empty()) {
1315 const Index pos = indexList.back();
1316 indexList.pop_back();
1318 if (mask.isOn(pos))
continue;
1321 ijk = NodeType::offsetToLocalCoord(pos);
1323 Index npos = pos - 1;
1324 if (ijk[2] != 0 && nodeMask.isOn(npos)) {
1325 nodeMask.setOff(npos);
1326 indexList.push_back(npos);
1330 if (ijk[2] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1331 nodeMask.setOff(npos);
1332 indexList.push_back(npos);
1335 npos = pos - NodeType::DIM;
1336 if (ijk[1] != 0 && nodeMask.isOn(npos)) {
1337 nodeMask.setOff(npos);
1338 indexList.push_back(npos);
1341 npos = pos + NodeType::DIM;
1342 if (ijk[1] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1343 nodeMask.setOff(npos);
1344 indexList.push_back(npos);
1347 npos = pos - NodeType::DIM * NodeType::DIM;
1348 if (ijk[0] != 0 && nodeMask.isOn(npos)) {
1349 nodeMask.setOff(npos);
1350 indexList.push_back(npos);
1353 npos = pos + NodeType::DIM * NodeType::DIM;
1354 if (ijk[0] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1355 nodeMask.setOff(npos);
1356 indexList.push_back(npos);
1361 segments.push_back(segment);
1366 template<
typename NodeType>
1374 : mNodes(!nodes.empty() ? &nodes.front() : nullptr)
1375 , mNodeMaskArray(nodeMaskArray)
1380 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1381 NodeType& node = *mNodes[n];
1385 Coord& origin =
const_cast<Coord&
>(node.origin());
1386 origin[0] =
static_cast<int>(n);
1395 template<
typename TreeType,
typename NodeType>
1405 , mNodeMaskArray(nodeMaskArray)
1413 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1416 if (segments.empty())
continue;
1418 std::vector<std::set<NodeMaskSegmentType*> > connections(segments.size());
1420 Coord ijk = segments[0]->origin;
1422 const NodeType* node = acc.template probeConstNode<NodeType>(ijk);
1423 if (!node)
continue;
1427 ijk[2] += NodeType::DIM;
1428 const NodeType* nodeZUp = acc.template probeConstNode<NodeType>(ijk);
1429 ijk[2] -= (NodeType::DIM + NodeType::DIM);
1430 const NodeType* nodeZDown = acc.template probeConstNode<NodeType>(ijk);
1431 ijk[2] += NodeType::DIM;
1433 ijk[1] += NodeType::DIM;
1434 const NodeType* nodeYUp = acc.template probeConstNode<NodeType>(ijk);
1435 ijk[1] -= (NodeType::DIM + NodeType::DIM);
1436 const NodeType* nodeYDown = acc.template probeConstNode<NodeType>(ijk);
1437 ijk[1] += NodeType::DIM;
1439 ijk[0] += NodeType::DIM;
1440 const NodeType* nodeXUp = acc.template probeConstNode<NodeType>(ijk);
1441 ijk[0] -= (NodeType::DIM + NodeType::DIM);
1442 const NodeType* nodeXDown = acc.template probeConstNode<NodeType>(ijk);
1443 ijk[0] += NodeType::DIM;
1445 const Index startPos = node->getValueMask().findFirstOn();
1446 for (
Index pos = startPos; pos < NodeMaskType::SIZE; ++pos) {
1448 if (!node->isValueOn(pos))
continue;
1450 ijk = NodeType::offsetToLocalCoord(pos);
1452 #ifdef _MSC_FULL_VER
1453 #if _MSC_FULL_VER >= 190000000 && _MSC_FULL_VER < 190024210
1455 volatile Index npos = 0;
1464 npos = pos + (NodeType::DIM - 1);
1465 if (nodeZDown && nodeZDown->isValueOn(npos)) {
1467 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeZDown)], npos);
1468 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1469 connections[idx].insert(nsegment);
1471 }
else if (ijk[2] == (NodeType::DIM - 1)) {
1472 npos = pos - (NodeType::DIM - 1);
1473 if (nodeZUp && nodeZUp->isValueOn(npos)) {
1475 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeZUp)], npos);
1476 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1477 connections[idx].insert(nsegment);
1482 npos = pos + (NodeType::DIM - 1) * NodeType::DIM;
1483 if (nodeYDown && nodeYDown->isValueOn(npos)) {
1485 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeYDown)], npos);
1486 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1487 connections[idx].insert(nsegment);
1489 }
else if (ijk[1] == (NodeType::DIM - 1)) {
1490 npos = pos - (NodeType::DIM - 1) * NodeType::DIM;
1491 if (nodeYUp && nodeYUp->isValueOn(npos)) {
1493 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeYUp)], npos);
1494 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1495 connections[idx].insert(nsegment);
1500 npos = pos + (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1501 if (nodeXDown && nodeXDown->isValueOn(npos)) {
1503 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeXDown)], npos);
1504 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1505 connections[idx].insert(nsegment);
1507 }
else if (ijk[0] == (NodeType::DIM - 1)) {
1508 npos = pos - (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1509 if (nodeXUp && nodeXUp->isValueOn(npos)) {
1511 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeXUp)], npos);
1512 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1513 connections[idx].insert(nsegment);
1518 for (
size_t i = 0, I = connections.size(); i < I; ++i) {
1520 typename std::set<NodeMaskSegmentType*>::iterator
1521 it = connections[i].begin(), end = connections[i].end();
1523 std::vector<NodeMaskSegmentType*>& segmentConnections = segments[i]->connections;
1524 segmentConnections.reserve(connections.size());
1525 for (; it != end; ++it) {
1526 segmentConnections.push_back(*it);
1534 static inline size_t getNodeOffset(
const NodeType& node) {
1535 return static_cast<size_t>(node.origin()[0]);
1538 static inline NodeMaskSegmentType*
1539 findNodeMaskSegment(NodeMaskSegmentVector& segments,
Index pos)
1541 NodeMaskSegmentType* segment =
nullptr;
1543 for (
size_t n = 0, N = segments.size(); n < N; ++n) {
1544 if (segments[n]->mask.isOn(pos)) {
1545 segment = segments[n].get();
1554 findNodeMaskSegmentIndex(NodeMaskSegmentVector& segments,
Index pos)
1556 for (
Index n = 0, N =
Index(segments.size()); n < N; ++n) {
1557 if (segments[n]->mask.isOn(pos))
return n;
1562 TreeType
const *
const mTree;
1563 NodeMaskSegmentVector *
const mNodeMaskArray;
1567 template<
typename TreeType>
1575 : mSegments(!segments.empty() ? &segments.front() : nullptr)
1576 , mTree(new TreeType(false))
1581 : mSegments(rhs.mSegments)
1582 , mTree(new TreeType(false))
1594 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1597 node->getValueMask() |= segment.
mask;
1602 NodeMaskSegmentType *
const *
const mSegments;
1610 template<
typename TreeType>
1617 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1623 std::vector<BoolLeafNodeType*>& maskNodes)
1624 : mDistTree(&distTree)
1625 , mMaskTree(&maskTree)
1626 , mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
1627 , mNewMaskTree(false)
1632 : mDistTree(rhs.mDistTree)
1633 , mMaskTree(rhs.mMaskTree)
1634 , mMaskNodes(rhs.mMaskNodes)
1635 , mNewMaskTree(false)
1651 NodeMaskType maskZUp, maskZDown, maskYUp, maskYDown, maskXUp, maskXDown;
1653 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1656 if (maskNode.isEmpty())
continue;
1658 Coord ijk = maskNode.origin(), nijk;
1661 if (!distNode)
continue;
1663 const ValueType *dataZUp =
nullptr, *dataZDown =
nullptr,
1664 *dataYUp =
nullptr, *dataYDown =
nullptr,
1665 *dataXUp =
nullptr, *dataXDown =
nullptr;
1667 ijk[2] += NodeType::DIM;
1668 getData(ijk, distAcc, maskAcc, maskZUp, dataZUp);
1669 ijk[2] -= (NodeType::DIM + NodeType::DIM);
1670 getData(ijk, distAcc, maskAcc, maskZDown, dataZDown);
1671 ijk[2] += NodeType::DIM;
1673 ijk[1] += NodeType::DIM;
1674 getData(ijk, distAcc, maskAcc, maskYUp, dataYUp);
1675 ijk[1] -= (NodeType::DIM + NodeType::DIM);
1676 getData(ijk, distAcc, maskAcc, maskYDown, dataYDown);
1677 ijk[1] += NodeType::DIM;
1679 ijk[0] += NodeType::DIM;
1680 getData(ijk, distAcc, maskAcc, maskXUp, dataXUp);
1681 ijk[0] -= (NodeType::DIM + NodeType::DIM);
1682 getData(ijk, distAcc, maskAcc, maskXDown, dataXDown);
1683 ijk[0] += NodeType::DIM;
1685 for (
typename BoolLeafNodeType::ValueOnIter it = maskNode.beginValueOn(); it; ++it) {
1687 const Index pos = it.pos();
1688 const ValueType val = std::abs(distNode->getValue(pos));
1690 ijk = BoolLeafNodeType::offsetToLocalCoord(pos);
1691 nijk = ijk + maskNode.origin();
1693 if (dataZUp && ijk[2] == (BoolLeafNodeType::DIM - 1)) {
1694 const Index npos = pos - (NodeType::DIM - 1);
1695 if (maskZUp.isOn(npos) && std::abs(dataZUp[npos]) > val) {
1696 newMaskAcc.
setValueOn(nijk.offsetBy(0, 0, 1));
1698 }
else if (dataZDown && ijk[2] == 0) {
1699 const Index npos = pos + (NodeType::DIM - 1);
1700 if (maskZDown.isOn(npos) && std::abs(dataZDown[npos]) > val) {
1701 newMaskAcc.
setValueOn(nijk.offsetBy(0, 0, -1));
1705 if (dataYUp && ijk[1] == (BoolLeafNodeType::DIM - 1)) {
1706 const Index npos = pos - (NodeType::DIM - 1) * NodeType::DIM;
1707 if (maskYUp.isOn(npos) && std::abs(dataYUp[npos]) > val) {
1708 newMaskAcc.
setValueOn(nijk.offsetBy(0, 1, 0));
1710 }
else if (dataYDown && ijk[1] == 0) {
1711 const Index npos = pos + (NodeType::DIM - 1) * NodeType::DIM;
1712 if (maskYDown.isOn(npos) && std::abs(dataYDown[npos]) > val) {
1713 newMaskAcc.
setValueOn(nijk.offsetBy(0, -1, 0));
1717 if (dataXUp && ijk[0] == (BoolLeafNodeType::DIM - 1)) {
1718 const Index npos = pos - (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1719 if (maskXUp.isOn(npos) && std::abs(dataXUp[npos]) > val) {
1720 newMaskAcc.
setValueOn(nijk.offsetBy(1, 0, 0));
1722 }
else if (dataXDown && ijk[0] == 0) {
1723 const Index npos = pos + (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1724 if (maskXDown.isOn(npos) && std::abs(dataXDown[npos]) > val) {
1725 newMaskAcc.
setValueOn(nijk.offsetBy(-1, 0, 0));
1738 const ValueType*& data)
1742 data = node->buffer().data();
1743 mask = node->getValueMask();
1744 const BoolLeafNodeType* maskNodePt = maskAcc.
probeConstLeaf(ijk);
1745 if (maskNodePt) mask -= maskNodePt->getValueMask();
1749 TreeType
const *
const mDistTree;
1750 BoolTreeType *
const mMaskTree;
1751 BoolLeafNodeType **
const mMaskNodes;
1753 BoolTreeType mNewMaskTree;
1757 template<
typename TreeType>
1766 : mTree(&tree), mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
1774 std::vector<Index> indexList;
1775 indexList.reserve(NodeMaskType::SIZE);
1777 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1782 if (!distNode)
continue;
1787 for (
Index pos = narrowbandMask.findFirstOn(); pos < NodeMaskType::SIZE; ++pos) {
1788 if (narrowbandMask.isOn(pos)) indexList.push_back(pos);
1791 mask -= narrowbandMask;
1794 const ValueType* data = distNode->buffer().data();
1797 while (!indexList.empty()) {
1799 const Index pos = indexList.back();
1800 indexList.pop_back();
1802 if (narrowbandMask.isOn(pos))
continue;
1803 narrowbandMask.setOn(pos);
1805 const ValueType dist = std::abs(data[pos]);
1807 ijk = LeafNodeType::offsetToLocalCoord(pos);
1809 Index npos = pos - 1;
1810 if (ijk[2] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1812 indexList.push_back(npos);
1816 if ((ijk[2] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1817 && std::abs(data[npos]) > dist)
1820 indexList.push_back(npos);
1823 npos = pos - LeafNodeType::DIM;
1824 if (ijk[1] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1826 indexList.push_back(npos);
1829 npos = pos + LeafNodeType::DIM;
1830 if ((ijk[1] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1831 && std::abs(data[npos]) > dist)
1834 indexList.push_back(npos);
1837 npos = pos - LeafNodeType::DIM * LeafNodeType::DIM;
1838 if (ijk[0] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1840 indexList.push_back(npos);
1843 npos = pos + LeafNodeType::DIM * LeafNodeType::DIM;
1844 if ((ijk[0] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1845 && std::abs(data[npos]) > dist)
1848 indexList.push_back(npos);
1859 template<
typename TreeType>
1862 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1867 : mTree(&tree), mSegments(!segments.empty() ? &segments.front() : nullptr)
1873 const TreeType& distTree = *mTree;
1874 std::vector<BoolLeafNodeType*> nodes;
1876 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1885 candidateMask.getNodes(nodes);
1886 if (nodes.empty())
break;
1888 const tbb::blocked_range<size_t> nodeRange(0, nodes.size());
1892 narrowBandMask.topologyUnion(candidateMask);
1895 tbb::parallel_reduce(nodeRange, op);
1899 candidateMask.clear();
1910 template<
typename TreeType>
1922 , mSegments(!segments.empty() ? &segments.front() : nullptr)
1928 std::vector<const InternalNodeType*> nodes;
1929 tree.getNodes(nodes);
1931 if (!nodes.empty()) {
1933 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1939 std::vector<const LeafNodeType*> nodes;
1940 tree.getNodes(nodes);
1941 if (!nodes.empty()) {
1943 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1948 mMinValue = minSDFValue;
1952 const ValueType interiorValue = -std::abs(mMinValue);
1953 const ValueType exteriorValue = std::abs(mTree->background());
1954 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1961 TreeType
const *
const mTree;
1962 TreeTypePtr *
const mSegments;
1963 ValueType mMinValue;
1967 template<
typename TreeType>
1974 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1978 MaskedCopy(
const TreeType& tree, std::vector<TreeTypePtr>& segments,
1979 std::vector<BoolTreeTypePtr>& masks)
1981 , mSegments(!segments.empty() ? &segments.front() : nullptr)
1982 , mMasks(!masks.empty() ? &masks.front() : nullptr)
1988 std::vector<const BoolLeafNodeType*> nodes;
1990 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1995 mask.getNodes(nodes);
1997 Copy op(*mTree, nodes);
1998 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
1999 mSegments[n] = op.outputTree();
2006 Copy(
const TreeType& inputTree, std::vector<const BoolLeafNodeType*>& maskNodes)
2007 : mInputTree(&inputTree)
2008 , mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
2009 , mOutputTreePtr(new TreeType(inputTree.background()))
2013 Copy(
const Copy& rhs, tbb::split)
2014 : mInputTree(rhs.mInputTree)
2015 , mMaskNodes(rhs.mMaskNodes)
2016 , mOutputTreePtr(new TreeType(mInputTree->background()))
2020 TreeTypePtr& outputTree() {
return mOutputTreePtr; }
2022 void join(Copy& rhs) { mOutputTreePtr->merge(*rhs.mOutputTreePtr); }
2024 void operator()(
const tbb::blocked_range<size_t>& range) {
2026 tree::ValueAccessor<const TreeType> inputAcc(*mInputTree);
2027 tree::ValueAccessor<TreeType> outputAcc(*mOutputTreePtr);
2029 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
2031 const BoolLeafNodeType& maskNode = *mMaskNodes[n];
2032 if (maskNode.isEmpty())
continue;
2034 const Coord& ijk = maskNode.origin();
2036 const LeafNodeType* inputNode = inputAcc.probeConstLeaf(ijk);
2039 LeafNodeType* outputNode = outputAcc.touchLeaf(ijk);
2041 for (
typename BoolLeafNodeType::ValueOnCIter it = maskNode.cbeginValueOn();
2044 const Index idx = it.pos();
2045 outputNode->setValueOn(idx, inputNode->getValue(idx));
2048 const int valueDepth = inputAcc.getValueDepth(ijk);
2049 if (valueDepth >= 0) {
2050 outputAcc.addTile(TreeType::RootNodeType::LEVEL - valueDepth,
2051 ijk, inputAcc.getValue(ijk),
true);
2058 TreeType
const *
const mInputTree;
2059 BoolLeafNodeType
const *
const *
const mMaskNodes;
2060 TreeTypePtr mOutputTreePtr;
2063 TreeType
const *
const mTree;
2064 TreeTypePtr *
const mSegments;
2065 BoolTreeTypePtr *
const mMasks;
2072 template<
typename VolumePtrType>
2076 : mSegments(!segments.empty() ? &segments.front() : nullptr)
2077 , mCountArray(countArray)
2082 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
2083 mCountArray[n] = mSegments[n]->activeVoxelCount();
2096 inline bool operator() (
const size_t& lhs,
const size_t& rhs)
const
2098 return (mCountArray[lhs] > mCountArray[rhs]);
2107 template<
typename TreeType>
2114 {
return maskTree; }
2119 template<
typename TreeType>
2126 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2133 maskGrid->setTransform(grid.transform().
copy());
2139 maskGrid->setTransform(grid.transform().
copy());
2140 maskGrid->insertMeta(grid);
2152 template <
class Gr
idType>
2156 using ValueType =
typename GridType::ValueType;
2157 using TreeType =
typename GridType::TreeType;
2158 using LeafNodeType =
typename TreeType::LeafNodeType;
2159 using RootNodeType =
typename TreeType::RootNodeType;
2160 using NodeChainType =
typename RootNodeType::NodeChainType;
2161 using InternalNodeType =
typename NodeChainType::template Get<1>;
2165 TreeType& tree = grid.tree();
2167 size_t numLeafNodes = 0, numInternalNodes = 0;
2169 std::vector<LeafNodeType*> nodes;
2170 std::vector<size_t> leafnodeCount;
2174 std::vector<InternalNodeType*> internalNodes;
2175 tree.getNodes(internalNodes);
2177 numInternalNodes = internalNodes.size();
2179 leafnodeCount.push_back(0);
2180 for (
size_t n = 0; n < numInternalNodes; ++n) {
2181 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
2184 numLeafNodes = leafnodeCount.back();
2187 nodes.reserve(numLeafNodes);
2189 for (
size_t n = 0; n < numInternalNodes; ++n) {
2190 internalNodes[n]->stealNodes(nodes, tree.background(),
false);
2198 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), minOp);
2202 if (minSDFValue > ValueType(0.0)) {
2204 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
2208 cutoffDistance = -std::abs(cutoffDistance);
2209 cutoffDistance = minSDFValue > cutoffDistance ? minSDFValue : cutoffDistance;
2215 tbb::parallel_for(tbb::blocked_range<size_t>(0, nodes.size()),
2219 typename TreeType::Ptr newTree(
new TreeType(ValueType(0.0)));
2222 *newTree, &nodes[0], &leafnodeCount[0], 0);
2223 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
2226 std::vector<InternalNodeType*> internalNodes;
2227 newTree->getNodes(internalNodes);
2229 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalNodes.size()),
2231 tree, &internalNodes[0]));
2236 typename TreeType::ValueAllIter it(*newTree);
2237 it.setMaxDepth(TreeType::ValueAllIter::LEAF_DEPTH - 2);
2240 if (acc.
getValue(it.getCoord()) < ValueType(0.0)) {
2241 it.setValue(ValueType(1.0));
2242 it.setActiveState(
true);
2250 typename TreeType::ValueAllIter it(tree);
2251 it.setMaxDepth(TreeType::ValueAllIter::ROOT_DEPTH);
2253 if (it.getValue() < ValueType(0.0)) {
2254 newTree->addTile(TreeType::ValueAllIter::ROOT_LEVEL, it.getCoord(),
2255 ValueType(1.0),
true);
2260 grid.setTree(newTree);
2268 template <
class Gr
idOrTreeType>
2269 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2270 sdfInteriorMask(
const GridOrTreeType& volume,
typename GridOrTreeType::ValueType isovalue)
2275 using BoolTreePtrType =
typename TreeType::template ValueConverter<bool>::Type::Ptr;
2283 template<
typename Gr
idOrTreeType>
2284 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2286 typename GridOrTreeType::ValueType isovalue,
2293 using CharTreePtrType =
typename TreeType::template ValueConverter<char>::Type::Ptr;
2295 tree, isovalue, fillMask);
2297 using BoolTreePtrType =
typename TreeType::template ValueConverter<bool>::Type::Ptr;
2308 template<
typename Gr
idOrTreeType>
2309 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2315 std::vector<const typename TreeType::LeafNodeType*> nodes;
2316 tree.getNodes(nodes);
2318 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2319 typename BoolTreeType::Ptr mask(
new BoolTreeType(
false));
2322 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
2332 template<
typename Gr
idOrTreeType>
2335 std::vector<
typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr>& masks)
2338 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2339 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2340 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
2343 using NodeMaskSegmentPtrType =
typename NodeMaskSegmentType::Ptr;
2344 using NodeMaskSegmentPtrVector =
typename std::vector<NodeMaskSegmentPtrType>;
2345 using NodeMaskSegmentRawPtrVector =
typename std::vector<NodeMaskSegmentType*>;
2351 BoolTreeType topologyMask(tree,
false,
TopologyCopy());
2356 if (topologyMask.hasActiveTiles()) {
2357 topologyMask.voxelizeActiveTiles();
2360 std::vector<BoolLeafNodeType*> leafnodes;
2361 topologyMask.getNodes(leafnodes);
2363 if (leafnodes.empty())
return;
2368 std::unique_ptr<NodeMaskSegmentPtrVector[]> nodeSegmentArray(
2369 new NodeMaskSegmentPtrVector[leafnodes.size()]);
2371 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
2373 leafnodes, nodeSegmentArray.get()));
2378 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
2380 topologyMask, nodeSegmentArray.get()));
2382 topologyMask.clear();
2384 size_t nodeSegmentCount = 0;
2385 for (
size_t n = 0, N = leafnodes.size(); n < N; ++n) {
2386 nodeSegmentCount += nodeSegmentArray[n].size();
2391 std::deque<NodeMaskSegmentRawPtrVector> nodeSegmentGroups;
2393 NodeMaskSegmentType* nextSegment = nodeSegmentArray[0][0].get();
2394 while (nextSegment) {
2396 nodeSegmentGroups.push_back(NodeMaskSegmentRawPtrVector());
2398 std::vector<NodeMaskSegmentType*>& segmentGroup = nodeSegmentGroups.back();
2399 segmentGroup.reserve(nodeSegmentCount);
2401 std::deque<NodeMaskSegmentType*> segmentQueue;
2402 segmentQueue.push_back(nextSegment);
2403 nextSegment =
nullptr;
2405 while (!segmentQueue.empty()) {
2407 NodeMaskSegmentType* segment = segmentQueue.back();
2408 segmentQueue.pop_back();
2410 if (segment->visited)
continue;
2411 segment->visited =
true;
2413 segmentGroup.push_back(segment);
2416 std::vector<NodeMaskSegmentType*>& connections = segment->connections;
2417 for (
size_t n = 0, N = connections.size(); n < N; ++n) {
2418 if (!connections[n]->visited) segmentQueue.push_back(connections[n]);
2423 for (
size_t n = 0, N = leafnodes.size(); n < N; ++n) {
2424 NodeMaskSegmentPtrVector& nodeSegments = nodeSegmentArray[n];
2425 for (
size_t i = 0, I = nodeSegments.size(); i < I; ++i) {
2426 if (!nodeSegments[i]->visited) nextSegment = nodeSegments[i].get();
2433 if (nodeSegmentGroups.size() == 1) {
2435 BoolTreePtrType mask(
new BoolTreeType(tree,
false,
TopologyCopy()));
2439 if (mask->hasActiveTiles()) {
2440 mask->voxelizeActiveTiles();
2447 }
else if (nodeSegmentGroups.size() > 1) {
2449 for (
size_t n = 0, N = nodeSegmentGroups.size(); n < N; ++n) {
2451 NodeMaskSegmentRawPtrVector& segmentGroup = nodeSegmentGroups[n];
2454 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, segmentGroup.size()), op);
2458 volume, op.
mask()));
2464 if (masks.size() > 1) {
2465 const size_t segmentCount = masks.size();
2467 std::unique_ptr<size_t[]> segmentOrderArray(
new size_t[segmentCount]);
2468 std::unique_ptr<size_t[]> voxelCountArray(
new size_t[segmentCount]);
2470 for (
size_t n = 0; n < segmentCount; ++n) {
2471 segmentOrderArray[n] = n;
2474 tbb::parallel_for(tbb::blocked_range<size_t>(0, segmentCount),
2476 masks, voxelCountArray.get()));
2478 size_t *begin = segmentOrderArray.get();
2480 voxelCountArray.get()));
2482 std::vector<BoolTreePtrType> orderedMasks;
2483 orderedMasks.reserve(masks.size());
2485 for (
size_t n = 0; n < segmentCount; ++n) {
2486 orderedMasks.push_back(masks[segmentOrderArray[n]]);
2489 masks.swap(orderedMasks);
2495 template<
typename Gr
idOrTreeType>
2498 std::vector<typename GridOrTreeType::Ptr>& segments)
2501 using TreePtrType =
typename TreeType::Ptr;
2502 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2503 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2508 std::vector<BoolTreePtrType> maskSegmentArray;
2513 const size_t numSegments =
std::max(
size_t(1), maskSegmentArray.size());
2514 std::vector<TreePtrType> outputSegmentArray(numSegments);
2516 if (maskSegmentArray.empty()) {
2519 outputSegmentArray[0] = TreePtrType(
new TreeType(inputTree.background()));
2520 }
else if (numSegments == 1) {
2522 TreePtrType segment(
new TreeType(inputTree));
2525 if (segment->leafCount() != inputTree.leafCount()) {
2526 segment->topologyIntersection(*maskSegmentArray[0]);
2528 outputSegmentArray[0] = segment;
2530 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
2531 tbb::parallel_for(segmentRange,
2536 for (
auto& segment : outputSegmentArray) {
2544 template<
typename Gr
idOrTreeType>
2546 segmentSDF(
const GridOrTreeType& volume, std::vector<typename GridOrTreeType::Ptr>& segments)
2549 using TreePtrType =
typename TreeType::Ptr;
2550 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2551 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2559 std::vector<BoolTreePtrType> maskSegmentArray;
2562 const size_t numSegments =
std::max(
size_t(1), maskSegmentArray.size());
2563 std::vector<TreePtrType> outputSegmentArray(numSegments);
2565 if (maskSegmentArray.empty()) {
2568 outputSegmentArray[0] = TreePtrType(
new TreeType(inputTree.background()));
2570 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
2573 tbb::parallel_for(segmentRange,
2579 inputTree, outputSegmentArray, maskSegmentArray));
2581 tbb::parallel_for(segmentRange,
2585 for (
auto& segment : outputSegmentArray) {
2596 #endif // OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED