11 #ifndef OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
12 #define OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
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>
50 template<
typename Gr
idType>
53 return zeroVal<typename GridType::ValueType>();
76 template<
class Gr
idType>
93 template<
class Gr
idOrTreeType>
94 typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
96 const GridOrTreeType& volume,
120 template<
typename Gr
idOrTreeType>
121 typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
123 const GridOrTreeType& volume,
134 template<
typename Gr
idOrTreeType>
135 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);
183 namespace level_set_util_internal {
186 template<
typename LeafNodeType>
187 struct MaskInteriorVoxels {
190 using BoolLeafNodeType = tree::LeafNode<bool, LeafNodeType::LOG2DIM>;
193 ValueType isovalue,
const LeafNodeType ** nodes, BoolLeafNodeType ** maskNodes)
194 : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
198 void operator()(
const tbb::blocked_range<size_t>&
range)
const {
200 BoolLeafNodeType * maskNodePt =
nullptr;
202 for (
size_t n = range.begin(),
N = range.
end();
n <
N; ++
n) {
204 mMaskNodes[
n] =
nullptr;
205 const LeafNodeType& node = *mNodes[
n];
208 maskNodePt =
new BoolLeafNodeType(node.origin(),
false);
210 maskNodePt->setOrigin(node.origin());
215 if (values[i] < mIsovalue) maskNodePt->setValueOn(i,
true);
218 if (maskNodePt->onVoxelCount() > 0) {
219 mMaskNodes[
n] = maskNodePt;
220 maskNodePt =
nullptr;
227 LeafNodeType
const *
const *
const mNodes;
228 BoolLeafNodeType **
const mMaskNodes;
233 template<
typename TreeType,
typename InternalNodeType>
234 struct MaskInteriorTiles {
238 MaskInteriorTiles(
ValueType isovalue,
const TreeType& tree, InternalNodeType ** maskNodes)
239 : mTree(&tree), mMaskNodes(maskNodes), mIsovalue(isovalue) { }
241 void operator()(
const tbb::blocked_range<size_t>& range)
const {
242 tree::ValueAccessor<const TreeType> acc(*mTree);
243 for (
size_t n = range.begin(), N = range.end();
n <
N; ++
n) {
244 typename InternalNodeType::ValueAllIter it = mMaskNodes[
n]->beginValueAll();
246 if (acc.getValue(it.getCoord()) < mIsovalue) {
254 TreeType
const *
const mTree;
255 InternalNodeType **
const mMaskNodes;
260 template<
typename TreeType>
261 struct PopulateTree {
264 using LeafNodeType =
typename TreeType::LeafNodeType;
266 PopulateTree(TreeType& tree, LeafNodeType** leafnodes,
267 const size_t * nodexIndexMap,
ValueType background)
268 : mNewTree(background)
271 , mNodeIndexMap(nodexIndexMap)
276 : mNewTree(rhs.mNewTree.background())
279 , mNodeIndexMap(rhs.mNodeIndexMap)
283 void operator()(
const tbb::blocked_range<size_t>& range) {
285 tree::ValueAccessor<TreeType> acc(*mTreePt);
288 for (
size_t n = range.begin(), N = range.end();
n <
N; ++
n) {
289 for (
size_t i = mNodeIndexMap[
n], I = mNodeIndexMap[n + 1]; i < I; ++i) {
290 if (mNodes[i] !=
nullptr) acc.addLeaf(mNodes[i]);
294 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
295 acc.addLeaf(mNodes[n]);
300 void join(PopulateTree& rhs) { mTreePt->merge(*rhs.mTreePt); }
304 TreeType *
const mTreePt;
305 LeafNodeType **
const mNodes;
306 size_t const *
const mNodeIndexMap;
311 template<
typename LeafNodeType>
312 struct LabelBoundaryVoxels {
315 using CharLeafNodeType = tree::LeafNode<char, LeafNodeType::LOG2DIM>;
318 ValueType isovalue,
const LeafNodeType ** nodes, CharLeafNodeType ** maskNodes)
319 : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
323 void operator()(
const tbb::blocked_range<size_t>& range)
const {
325 CharLeafNodeType * maskNodePt =
nullptr;
327 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
329 mMaskNodes[
n] =
nullptr;
330 const LeafNodeType& node = *mNodes[
n];
333 maskNodePt =
new CharLeafNodeType(node.origin(), 1);
335 maskNodePt->setOrigin(node.origin());
338 typename LeafNodeType::ValueOnCIter it;
339 for (it = node.cbeginValueOn(); it; ++it) {
340 maskNodePt->setValueOn(it.pos(), ((*it - mIsovalue) < 0.0) ? 0 : 1);
343 if (maskNodePt->onVoxelCount() > 0) {
344 mMaskNodes[
n] = maskNodePt;
345 maskNodePt =
nullptr;
352 LeafNodeType
const *
const *
const mNodes;
353 CharLeafNodeType **
const mMaskNodes;
358 template<
typename LeafNodeType>
359 struct FlipRegionSign {
362 FlipRegionSign(LeafNodeType ** nodes) : mNodes(nodes) { }
364 void operator()(
const tbb::blocked_range<size_t>& range)
const {
365 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
368 values[i] = values[i] < 0 ? 1 : -1;
373 LeafNodeType **
const mNodes;
377 template<
typename LeafNodeType>
378 struct FindMinVoxelValue {
382 FindMinVoxelValue(LeafNodeType
const *
const *
const leafnodes)
388 FindMinVoxelValue(FindMinVoxelValue& rhs,
tbb::split)
394 void operator()(
const tbb::blocked_range<size_t>& range) {
395 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
398 minValue =
std::min(minValue, data[i]);
403 void join(FindMinVoxelValue& rhs) { minValue =
std::min(minValue, rhs.minValue); }
407 LeafNodeType
const *
const *
const mNodes;
411 template<
typename InternalNodeType>
412 struct FindMinTileValue {
416 FindMinTileValue(InternalNodeType
const *
const *
const nodes)
422 FindMinTileValue(FindMinTileValue& rhs,
tbb::split)
428 void operator()(
const tbb::blocked_range<size_t>& range) {
429 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
430 typename InternalNodeType::ValueAllCIter it = mNodes[
n]->beginValueAll();
437 void join(FindMinTileValue& rhs) { minValue =
std::min(minValue, rhs.minValue); }
441 InternalNodeType
const *
const *
const mNodes;
445 template<
typename LeafNodeType>
446 struct SDFVoxelsToFogVolume {
450 SDFVoxelsToFogVolume(LeafNodeType ** nodes,
ValueType cutoffDistance)
451 : mNodes(nodes), mWeight(
ValueType(1.0) / cutoffDistance)
455 void operator()(
const tbb::blocked_range<size_t>& range)
const {
457 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
459 LeafNodeType& node = *mNodes[
n];
462 ValueType* values = node.buffer().data();
465 if (values[i] >
ValueType(0.0)) node.setValueOn(i);
468 if (node.onVoxelCount() == 0) {
475 LeafNodeType **
const mNodes;
476 ValueType
const mWeight;
480 template<
typename TreeType,
typename InternalNodeType>
481 struct SDFTilesToFogVolume {
483 SDFTilesToFogVolume(
const TreeType& tree, InternalNodeType ** nodes)
484 : mTree(&tree), mNodes(nodes) { }
486 void operator()(
const tbb::blocked_range<size_t>& range)
const {
489 tree::ValueAccessor<const TreeType> acc(*mTree);
491 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
492 typename InternalNodeType::ValueAllIter it = mNodes[
n]->beginValueAll();
494 if (acc.getValue(it.getCoord()) <
ValueType(0.0)) {
502 TreeType
const *
const mTree;
503 InternalNodeType **
const mNodes;
507 template<
typename TreeType>
508 struct FillMaskBoundary {
511 using LeafNodeType =
typename TreeType::LeafNodeType;
513 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
515 FillMaskBoundary(
const TreeType& tree, ValueType isovalue,
const BoolTreeType& fillMask,
516 const BoolLeafNodeType ** fillNodes, BoolLeafNodeType ** newNodes)
518 , mFillMask(&fillMask)
519 , mFillNodes(fillNodes)
520 , mNewNodes(newNodes)
521 , mIsovalue(isovalue)
525 void operator()(
const tbb::blocked_range<size_t>& range)
const {
527 tree::ValueAccessor<const BoolTreeType> maskAcc(*mFillMask);
528 tree::ValueAccessor<const TreeType> distAcc(*mTree);
532 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
534 mNewNodes[
n] =
nullptr;
535 const BoolLeafNodeType& node = *mFillNodes[
n];
536 const Coord& origin = node.origin();
538 const bool denseNode = node.isDense();
543 int denseNeighbors = 0;
545 const BoolLeafNodeType* neighborNode =
546 maskAcc.probeConstLeaf(origin.offsetBy(-1, 0, 0));
547 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
549 neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(BoolLeafNodeType::DIM, 0, 0));
550 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
552 neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, -1, 0));
553 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
555 neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, BoolLeafNodeType::DIM, 0));
556 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
558 neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, 0, -1));
559 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
561 neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, 0, BoolLeafNodeType::DIM));
562 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
564 if (denseNeighbors == 6)
continue;
570 const typename TreeType::LeafNodeType* distNode = distAcc.probeConstLeaf(origin);
574 bool earlyTermination =
false;
578 evalInternalNeighborsP(valueMask.get(), node, *distNode);
579 evalInternalNeighborsN(valueMask.get(), node, *distNode);
580 }
else if (distAcc.getValue(origin) > mIsovalue) {
581 earlyTermination = evalInternalNeighborsP(valueMask.get(), node);
582 if (!earlyTermination) {
583 earlyTermination = evalInternalNeighborsN(valueMask.get(), node);
590 if (!earlyTermination) {
591 evalExternalNeighborsX<true>(valueMask.get(), node, maskAcc, distAcc);
592 evalExternalNeighborsX<false>(valueMask.get(), node, maskAcc, distAcc);
593 evalExternalNeighborsY<true>(valueMask.get(), node, maskAcc, distAcc);
594 evalExternalNeighborsY<false>(valueMask.get(), node, maskAcc, distAcc);
595 evalExternalNeighborsZ<true>(valueMask.get(), node, maskAcc, distAcc);
596 evalExternalNeighborsZ<false>(valueMask.get(), node, maskAcc, distAcc);
601 int numBoundaryValues = 0;
603 numBoundaryValues += valueMask[i] == 1;
606 if (numBoundaryValues > 0) {
607 mNewNodes[
n] =
new BoolLeafNodeType(origin,
false);
609 if (valueMask[i] == 1) mNewNodes[
n]->setValueOn(i);
617 void evalInternalNeighborsP(
char* valueMask,
const BoolLeafNodeType& node,
618 const LeafNodeType& distNode)
const
620 for (Index
x = 0;
x < BoolLeafNodeType::DIM; ++
x) {
621 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
622 for (Index
y = 0;
y < BoolLeafNodeType::DIM; ++
y) {
623 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
624 for (Index
z = 0;
z < BoolLeafNodeType::DIM - 1; ++
z) {
625 const Index pos = yPos +
z;
627 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
629 if (!node.isValueOn(pos + 1) && distNode.getValue(pos + 1) > mIsovalue) {
636 for (Index
x = 0;
x < BoolLeafNodeType::DIM; ++
x) {
637 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
638 for (Index
y = 0;
y < BoolLeafNodeType::DIM - 1; ++
y) {
639 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
640 for (Index z = 0; z < BoolLeafNodeType::DIM; ++
z) {
641 const Index pos = yPos +
z;
643 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
645 if (!node.isValueOn(pos + BoolLeafNodeType::DIM) &&
646 distNode.getValue(pos + BoolLeafNodeType::DIM) > mIsovalue) {
653 for (Index
x = 0;
x < BoolLeafNodeType::DIM - 1; ++
x) {
654 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
655 for (Index
y = 0;
y < BoolLeafNodeType::DIM; ++
y) {
656 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
657 for (Index z = 0; z < BoolLeafNodeType::DIM; ++
z) {
658 const Index pos = yPos +
z;
660 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
662 if (!node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
663 (distNode.getValue(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)
673 bool evalInternalNeighborsP(
char* valueMask,
const BoolLeafNodeType& node)
const {
675 for (Index
x = 0;
x < BoolLeafNodeType::DIM; ++
x) {
676 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
677 for (Index
y = 0;
y < BoolLeafNodeType::DIM; ++
y) {
678 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
679 for (Index z = 0; z < BoolLeafNodeType::DIM - 1; ++
z) {
680 const Index pos = yPos +
z;
682 if (node.isValueOn(pos) && !node.isValueOn(pos + 1)) {
690 for (Index
x = 0;
x < BoolLeafNodeType::DIM; ++
x) {
691 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
692 for (Index
y = 0;
y < BoolLeafNodeType::DIM - 1; ++
y) {
693 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
694 for (Index z = 0; z < BoolLeafNodeType::DIM; ++
z) {
695 const Index pos = yPos +
z;
697 if (node.isValueOn(pos) && !node.isValueOn(pos + BoolLeafNodeType::DIM)) {
705 for (Index
x = 0;
x < BoolLeafNodeType::DIM - 1; ++
x) {
706 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
707 for (Index
y = 0;
y < BoolLeafNodeType::DIM; ++
y) {
708 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
709 for (Index z = 0; z < BoolLeafNodeType::DIM; ++
z) {
710 const Index pos = yPos +
z;
712 if (node.isValueOn(pos) &&
713 !node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
726 void evalInternalNeighborsN(
char* valueMask,
const BoolLeafNodeType& node,
727 const LeafNodeType& distNode)
const
729 for (Index
x = 0;
x < BoolLeafNodeType::DIM; ++
x) {
730 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
731 for (Index
y = 0;
y < BoolLeafNodeType::DIM; ++
y) {
732 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
733 for (Index z = 1; z < BoolLeafNodeType::DIM; ++
z) {
734 const Index pos = yPos +
z;
736 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
738 if (!node.isValueOn(pos - 1) && distNode.getValue(pos - 1) > mIsovalue) {
745 for (Index
x = 0;
x < BoolLeafNodeType::DIM; ++
x) {
746 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
747 for (Index
y = 1;
y < BoolLeafNodeType::DIM; ++
y) {
748 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
749 for (Index z = 0; z < BoolLeafNodeType::DIM; ++
z) {
750 const Index pos = yPos +
z;
752 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
754 if (!node.isValueOn(pos - BoolLeafNodeType::DIM) &&
755 distNode.getValue(pos - BoolLeafNodeType::DIM) > mIsovalue) {
762 for (Index
x = 1;
x < BoolLeafNodeType::DIM; ++
x) {
763 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
764 for (Index
y = 0;
y < BoolLeafNodeType::DIM; ++
y) {
765 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
766 for (Index z = 0; z < BoolLeafNodeType::DIM; ++
z) {
767 const Index pos = yPos +
z;
769 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
771 if (!node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
772 (distNode.getValue(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)
783 bool evalInternalNeighborsN(
char* valueMask,
const BoolLeafNodeType& node)
const {
785 for (Index
x = 0;
x < BoolLeafNodeType::DIM; ++
x) {
786 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
787 for (Index
y = 0;
y < BoolLeafNodeType::DIM; ++
y) {
788 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
789 for (Index z = 1; z < BoolLeafNodeType::DIM; ++
z) {
790 const Index pos = yPos +
z;
792 if (node.isValueOn(pos) && !node.isValueOn(pos - 1)) {
800 for (Index
x = 0;
x < BoolLeafNodeType::DIM; ++
x) {
801 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
802 for (Index
y = 1;
y < BoolLeafNodeType::DIM; ++
y) {
803 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
804 for (Index z = 0; z < BoolLeafNodeType::DIM; ++
z) {
805 const Index pos = yPos +
z;
807 if (node.isValueOn(pos) && !node.isValueOn(pos - BoolLeafNodeType::DIM)) {
815 for (Index
x = 1;
x < BoolLeafNodeType::DIM; ++
x) {
816 const Index xPos =
x << (2 * BoolLeafNodeType::LOG2DIM);
817 for (Index
y = 0;
y < BoolLeafNodeType::DIM; ++
y) {
818 const Index yPos = xPos + (
y << BoolLeafNodeType::LOG2DIM);
819 for (Index z = 0; z < BoolLeafNodeType::DIM; ++
z) {
820 const Index pos = yPos +
z;
822 if (node.isValueOn(pos) &&
823 !node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
838 template<
bool UpWind>
839 void evalExternalNeighborsX(
char* valueMask,
const BoolLeafNodeType& node,
840 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
841 const tree::ValueAccessor<const TreeType>& distAcc)
const {
843 const Coord& origin = node.origin();
844 Coord ijk(0, 0, 0), nijk;
849 ijk[0] =
int(BoolLeafNodeType::DIM) - 1;
852 const Index xPos = ijk[0] << (2 *
int(BoolLeafNodeType::LOG2DIM));
854 for (ijk[1] = 0; ijk[1] <
int(BoolLeafNodeType::DIM); ++ijk[1]) {
855 const Index yPos = xPos + (ijk[1] <<
int(BoolLeafNodeType::LOG2DIM));
857 for (ijk[2] = 0; ijk[2] <
int(BoolLeafNodeType::DIM); ++ijk[2]) {
858 const Index pos = yPos + ijk[2];
860 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
862 nijk = origin + ijk.offsetBy(step, 0, 0);
864 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
873 template<
bool UpWind>
874 void evalExternalNeighborsY(
char* valueMask,
const BoolLeafNodeType& node,
875 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
876 const tree::ValueAccessor<const TreeType>& distAcc)
const {
878 const Coord& origin = node.origin();
879 Coord ijk(0, 0, 0), nijk;
884 ijk[1] =
int(BoolLeafNodeType::DIM) - 1;
887 const Index yPos = ijk[1] <<
int(BoolLeafNodeType::LOG2DIM);
889 for (ijk[0] = 0; ijk[0] <
int(BoolLeafNodeType::DIM); ++ijk[0]) {
890 const Index xPos = yPos + (ijk[0] << (2 *
int(BoolLeafNodeType::LOG2DIM)));
892 for (ijk[2] = 0; ijk[2] <
int(BoolLeafNodeType::DIM); ++ijk[2]) {
893 const Index pos = xPos + ijk[2];
895 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
897 nijk = origin + ijk.offsetBy(0, step, 0);
898 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
907 template<
bool UpWind>
908 void evalExternalNeighborsZ(
char* valueMask,
const BoolLeafNodeType& node,
909 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
910 const tree::ValueAccessor<const TreeType>& distAcc)
const {
912 const Coord& origin = node.origin();
913 Coord ijk(0, 0, 0), nijk;
918 ijk[2] =
int(BoolLeafNodeType::DIM) - 1;
921 for (ijk[0] = 0; ijk[0] <
int(BoolLeafNodeType::DIM); ++ijk[0]) {
922 const Index xPos = ijk[0] << (2 *
int(BoolLeafNodeType::LOG2DIM));
924 for (ijk[1] = 0; ijk[1] <
int(BoolLeafNodeType::DIM); ++ijk[1]) {
925 const Index pos = ijk[2] + xPos + (ijk[1] <<
int(BoolLeafNodeType::LOG2DIM));
927 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
929 nijk = origin + ijk.offsetBy(0, 0, step);
930 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
940 TreeType
const *
const mTree;
941 BoolTreeType
const *
const mFillMask;
942 BoolLeafNodeType
const *
const *
const mFillNodes;
943 BoolLeafNodeType **
const mNewNodes;
944 ValueType
const mIsovalue;
950 template <
class TreeType>
951 typename TreeType::template ValueConverter<char>::Type::Ptr
955 using LeafNodeType =
typename TreeType::LeafNodeType;
956 using RootNodeType =
typename TreeType::RootNodeType;
957 using NodeChainType =
typename RootNodeType::NodeChainType;
958 using InternalNodeType =
typename NodeChainType::template Get<1>;
961 using CharLeafNodeType =
typename CharTreeType::LeafNodeType;
964 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
966 const TreeType* treePt = &tree;
968 size_t numLeafNodes = 0, numInternalNodes = 0;
970 std::vector<const LeafNodeType*> nodes;
971 std::vector<size_t> leafnodeCount;
975 std::vector<const InternalNodeType*> internalNodes;
976 treePt->getNodes(internalNodes);
978 numInternalNodes = internalNodes.size();
980 leafnodeCount.push_back(0);
981 for (
size_t n = 0; n < numInternalNodes; ++
n) {
982 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[
n]->leafCount());
985 numLeafNodes = leafnodeCount.back();
988 nodes.reserve(numLeafNodes);
990 for (
size_t n = 0; n < numInternalNodes; ++
n) {
991 internalNodes[
n]->getNodes(nodes);
996 std::unique_ptr<CharLeafNodeType*[]> maskNodes(
new CharLeafNodeType*[numLeafNodes]);
999 LabelBoundaryVoxels<LeafNodeType>(isovalue, nodes.data(), maskNodes.get()));
1002 typename CharTreeType::Ptr maskTree(
new CharTreeType(1));
1004 PopulateTree<CharTreeType> populate(*maskTree, maskNodes.get(), leafnodeCount.data(), 1);
1005 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1009 std::vector<CharLeafNodeType*> extraMaskNodes;
1013 std::vector<const BoolLeafNodeType*> fillMaskNodes;
1014 fillMask->getNodes(fillMaskNodes);
1016 std::unique_ptr<BoolLeafNodeType*[]> boundaryMaskNodes(
1017 new BoolLeafNodeType*[fillMaskNodes.size()]);
1020 FillMaskBoundary<TreeType>(tree, isovalue, *fillMask, fillMaskNodes.data(),
1021 boundaryMaskNodes.get()));
1023 tree::ValueAccessor<CharTreeType> maskAcc(*maskTree);
1025 for (
size_t n = 0, N = fillMaskNodes.size(); n <
N; ++
n) {
1027 if (boundaryMaskNodes[n] ==
nullptr)
continue;
1029 const BoolLeafNodeType& boundaryNode = *boundaryMaskNodes[
n];
1030 const Coord& origin = boundaryNode.origin();
1032 CharLeafNodeType* maskNodePt = maskAcc.probeLeaf(origin);
1035 maskNodePt = maskAcc.touchLeaf(origin);
1036 extraMaskNodes.push_back(maskNodePt);
1039 char* data = maskNodePt->buffer().data();
1041 typename BoolLeafNodeType::ValueOnCIter it = boundaryNode.cbeginValueOn();
1043 if (data[it.pos()] != 0) data[it.pos()] = -1;
1046 delete boundaryMaskNodes[
n];
1055 FlipRegionSign<CharLeafNodeType>(maskNodes.get()));
1057 if (!extraMaskNodes.empty()) {
1059 FlipRegionSign<CharLeafNodeType>(extraMaskNodes.data()));
1069 template <
class TreeType>
1070 typename TreeType::template ValueConverter<bool>::Type::Ptr
1074 using LeafNodeType =
typename TreeType::LeafNodeType;
1075 using RootNodeType =
typename TreeType::RootNodeType;
1076 using NodeChainType =
typename RootNodeType::NodeChainType;
1077 using InternalNodeType =
typename NodeChainType::template Get<1>;
1079 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1080 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1081 using BoolRootNodeType =
typename BoolTreeType::RootNodeType;
1082 using BoolNodeChainType =
typename BoolRootNodeType::NodeChainType;
1083 using BoolInternalNodeType =
typename BoolNodeChainType::template Get<1>;
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]);
1126 MaskInteriorVoxels<LeafNodeType>(iso, nodes.data(), maskNodes.get()));
1130 typename BoolTreeType::Ptr maskTree(
new BoolTreeType(
false));
1132 PopulateTree<BoolTreeType> populate(*maskTree, maskNodes.get(), leafnodeCount.data(),
false);
1133 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1137 std::vector<BoolInternalNodeType*> internalMaskNodes;
1138 maskTree->getNodes(internalMaskNodes);
1141 MaskInteriorTiles<TreeType, BoolInternalNodeType>(iso, tree, internalMaskNodes.data()));
1143 tree::ValueAccessor<const TreeType> acc(tree);
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>
1160 struct MaskIsovalueCrossingVoxels
1163 using InputLeafNodeType =
typename InputTreeType::LeafNodeType;
1164 using BoolTreeType =
typename InputTreeType::template ValueConverter<bool>::Type;
1165 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1167 MaskIsovalueCrossingVoxels(
1168 const InputTreeType& inputTree,
1169 const std::vector<const InputLeafNodeType*>& inputLeafNodes,
1170 BoolTreeType& maskTree,
1172 : mInputAccessor(inputTree)
1173 , mInputNodes(!inputLeafNodes.empty() ? &inputLeafNodes.front() : nullptr)
1175 , mMaskAccessor(maskTree)
1180 MaskIsovalueCrossingVoxels(MaskIsovalueCrossingVoxels& rhs,
tbb::split)
1181 : mInputAccessor(rhs.mInputAccessor.tree())
1182 , mInputNodes(rhs.mInputNodes)
1184 , mMaskAccessor(mMaskTree)
1185 , mIsovalue(rhs.mIsovalue)
1189 void operator()(
const tbb::blocked_range<size_t>& range) {
1191 const InputValueType iso = mIsovalue;
1194 BoolLeafNodeType* maskNodePt =
nullptr;
1196 for (
size_t n = range.begin(); mInputNodes && (n != range.end()); ++
n) {
1198 const InputLeafNodeType& node = *mInputNodes[
n];
1200 if (!maskNodePt) maskNodePt =
new BoolLeafNodeType(node.origin(),
false);
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;
1260 void join(MaskIsovalueCrossingVoxels& rhs) {
1261 mMaskAccessor.tree().merge(rhs.mMaskAccessor.tree());
1265 tree::ValueAccessor<const InputTreeType> mInputAccessor;
1266 InputLeafNodeType
const *
const *
const mInputNodes;
1268 BoolTreeType mMaskTree;
1269 tree::ValueAccessor<BoolTreeType> mMaskAccessor;
1271 InputValueType mIsovalue;
1278 template<
typename NodeType>
1279 struct NodeMaskSegment
1281 using Ptr = SharedPtr<NodeMaskSegment>;
1282 using NodeMaskType =
typename NodeType::NodeMaskType;
1284 NodeMaskSegment() : connections(),
mask(false), origin(0,0,0), visited(false) {}
1286 std::vector<NodeMaskSegment*> connections;
1293 template<
typename NodeType>
1295 nodeMaskSegmentation(
const NodeType& node,
1296 std::vector<
typename NodeMaskSegment<NodeType>::Ptr>& segments)
1298 using NodeMaskType =
typename NodeType::NodeMaskType;
1299 using NodeMaskSegmentType = NodeMaskSegment<NodeType>;
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>
1370 struct SegmentNodeMask
1372 using NodeMaskSegmentType = NodeMaskSegment<NodeType>;
1373 using NodeMaskSegmentTypePtr =
typename NodeMaskSegmentType::Ptr;
1374 using NodeMaskSegmentVector =
typename std::vector<NodeMaskSegmentTypePtr>;
1376 SegmentNodeMask(std::vector<NodeType*>& nodes, NodeMaskSegmentVector* nodeMaskArray)
1377 : mNodes(!nodes.empty() ? &nodes.front() : nullptr)
1378 , mNodeMaskArray(nodeMaskArray)
1382 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1383 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
1384 NodeType& node = *mNodes[
n];
1385 nodeMaskSegmentation(node, mNodeMaskArray[n]);
1388 Coord& origin =
const_cast<Coord&
>(node.origin());
1389 origin[0] =
static_cast<int>(
n);
1393 NodeType *
const *
const mNodes;
1394 NodeMaskSegmentVector *
const mNodeMaskArray;
1398 template<
typename TreeType,
typename NodeType>
1399 struct ConnectNodeMaskSegments
1401 using NodeMaskType =
typename NodeType::NodeMaskType;
1402 using NodeMaskSegmentType = NodeMaskSegment<NodeType>;
1403 using NodeMaskSegmentTypePtr =
typename NodeMaskSegmentType::Ptr;
1404 using NodeMaskSegmentVector =
typename std::vector<NodeMaskSegmentTypePtr>;
1406 ConnectNodeMaskSegments(
const TreeType& tree, NodeMaskSegmentVector* nodeMaskArray)
1408 , mNodeMaskArray(nodeMaskArray)
1412 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1414 tree::ValueAccessor<const TreeType> acc(*mTree);
1416 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
1418 NodeMaskSegmentVector& segments = mNodeMaskArray[
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();
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)) {
1469 NodeMaskSegmentType* nsegment =
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)) {
1477 NodeMaskSegmentType* nsegment =
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)) {
1487 NodeMaskSegmentType* nsegment =
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)) {
1495 NodeMaskSegmentType* nsegment =
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)) {
1505 NodeMaskSegmentType* nsegment =
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)) {
1513 NodeMaskSegmentType* nsegment =
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>
1571 struct MaskSegmentGroup
1573 using LeafNodeType =
typename TreeType::LeafNodeType;
1574 using TreeTypePtr =
typename TreeType::Ptr;
1575 using NodeMaskSegmentType = NodeMaskSegment<LeafNodeType>;
1577 MaskSegmentGroup(
const std::vector<NodeMaskSegmentType*>& segments)
1578 : mSegments(!segments.empty() ? &segments.front() : nullptr)
1579 , mTree(new TreeType(false))
1583 MaskSegmentGroup(
const MaskSegmentGroup& rhs,
tbb::split)
1584 : mSegments(rhs.mSegments)
1585 , mTree(new TreeType(false))
1589 TreeTypePtr&
mask() {
return mTree; }
1591 void join(MaskSegmentGroup& rhs) { mTree->merge(*rhs.mTree); }
1593 void operator()(
const tbb::blocked_range<size_t>& range) {
1595 tree::ValueAccessor<TreeType> acc(*mTree);
1597 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
1598 NodeMaskSegmentType& segment = *mSegments[
n];
1599 LeafNodeType* node = acc.touchLeaf(segment.origin);
1600 node->getValueMask() |= segment.mask;
1605 NodeMaskSegmentType *
const *
const mSegments;
1613 template<
typename TreeType>
1614 struct ExpandLeafNodeRegion
1617 using LeafNodeType =
typename TreeType::LeafNodeType;
1618 using NodeMaskType =
typename LeafNodeType::NodeMaskType;
1620 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1621 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1625 ExpandLeafNodeRegion(
const TreeType& distTree, BoolTreeType& maskTree,
1626 std::vector<BoolLeafNodeType*>& maskNodes)
1627 : mDistTree(&distTree)
1628 , mMaskTree(&maskTree)
1629 , mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
1630 , mNewMaskTree(false)
1634 ExpandLeafNodeRegion(
const ExpandLeafNodeRegion& rhs,
tbb::split)
1635 : mDistTree(rhs.mDistTree)
1636 , mMaskTree(rhs.mMaskTree)
1637 , mMaskNodes(rhs.mMaskNodes)
1638 , mNewMaskTree(false)
1642 BoolTreeType& newMaskTree() {
return mNewMaskTree; }
1644 void join(ExpandLeafNodeRegion& rhs) { mNewMaskTree.merge(rhs.mNewMaskTree); }
1646 void operator()(
const tbb::blocked_range<size_t>& range) {
1648 using NodeType = LeafNodeType;
1650 tree::ValueAccessor<const TreeType> distAcc(*mDistTree);
1651 tree::ValueAccessor<const BoolTreeType> maskAcc(*mMaskTree);
1652 tree::ValueAccessor<BoolTreeType> newMaskAcc(mNewMaskTree);
1654 NodeMaskType maskZUp, maskZDown, maskYUp, maskYDown, maskXUp, maskXDown;
1656 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
1658 BoolLeafNodeType& maskNode = *mMaskNodes[
n];
1659 if (maskNode.isEmpty())
continue;
1661 Coord ijk = maskNode.origin(), nijk;
1663 const LeafNodeType* distNode = distAcc.probeConstLeaf(ijk);
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));
1739 getData(
const Coord& ijk, tree::ValueAccessor<const TreeType>& distAcc,
1740 tree::ValueAccessor<const BoolTreeType>& maskAcc, NodeMaskType& mask,
1741 const ValueType*& data)
1743 const LeafNodeType* node = distAcc.probeConstLeaf(ijk);
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>
1761 struct FillLeafNodeVoxels
1764 using LeafNodeType =
typename TreeType::LeafNodeType;
1765 using NodeMaskType =
typename LeafNodeType::NodeMaskType;
1766 using BoolLeafNodeType = tree::LeafNode<bool, LeafNodeType::LOG2DIM>;
1768 FillLeafNodeVoxels(
const TreeType& tree, std::vector<BoolLeafNodeType*>& maskNodes)
1769 : mTree(&tree), mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
1773 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1775 tree::ValueAccessor<const TreeType> distAcc(*mTree);
1777 std::vector<Index> indexList;
1778 indexList.reserve(NodeMaskType::SIZE);
1780 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
1782 BoolLeafNodeType& maskNode = *mMaskNodes[
n];
1784 const LeafNodeType * distNode = distAcc.probeConstLeaf(maskNode.origin());
1785 if (!distNode)
continue;
1787 NodeMaskType
mask(distNode->getValueMask());
1788 NodeMaskType& narrowbandMask = maskNode.getValueMask();
1791 if (narrowbandMask.isOn(pos)) indexList.push_back(pos);
1794 mask -= narrowbandMask;
1795 narrowbandMask.setOff();
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);
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)
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)
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)
1851 indexList.push_back(npos);
1857 TreeType
const *
const mTree;
1858 BoolLeafNodeType **
const mMaskNodes;
1862 template<
typename TreeType>
1863 struct ExpandNarrowbandMask
1865 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1866 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1867 using BoolTreeTypePtr =
typename BoolTreeType::Ptr;
1869 ExpandNarrowbandMask(
const TreeType& tree, std::vector<BoolTreeTypePtr>& segments)
1870 : mTree(&tree), mSegments(!segments.empty() ? &segments.front() : nullptr)
1874 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1876 const TreeType& distTree = *mTree;
1877 std::vector<BoolLeafNodeType*> nodes;
1879 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
1881 BoolTreeType& narrowBandMask = *mSegments[
n];
1883 BoolTreeType candidateMask(narrowBandMask,
false, TopologyCopy());
1888 candidateMask.getNodes(nodes);
1889 if (nodes.empty())
break;
1891 const tbb::blocked_range<size_t> nodeRange(0, nodes.size());
1895 narrowBandMask.topologyUnion(candidateMask);
1897 ExpandLeafNodeRegion<TreeType> op(distTree, narrowBandMask, nodes);
1898 tbb::parallel_reduce(nodeRange, op);
1900 if (op.newMaskTree().empty())
break;
1902 candidateMask.clear();
1903 candidateMask.merge(op.newMaskTree());
1908 TreeType
const *
const mTree;
1909 BoolTreeTypePtr *
const mSegments;
1913 template<
typename TreeType>
1914 struct FloodFillSign
1916 using TreeTypePtr =
typename TreeType::Ptr;
1918 using LeafNodeType =
typename TreeType::LeafNodeType;
1919 using RootNodeType =
typename TreeType::RootNodeType;
1920 using NodeChainType =
typename RootNodeType::NodeChainType;
1921 using InternalNodeType =
typename NodeChainType::template Get<1>;
1923 FloodFillSign(
const TreeType& tree, std::vector<TreeTypePtr>& segments)
1925 , mSegments(!segments.empty() ? &segments.front() : nullptr)
1926 , mMinValue(ValueType(0.0))
1931 std::vector<const InternalNodeType*> nodes;
1932 tree.getNodes(nodes);
1934 if (!nodes.empty()) {
1935 FindMinTileValue<InternalNodeType> minOp(nodes.data());
1936 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1937 minSDFValue =
std::min(minSDFValue, minOp.minValue);
1942 std::vector<const LeafNodeType*> nodes;
1943 tree.getNodes(nodes);
1944 if (!nodes.empty()) {
1945 FindMinVoxelValue<LeafNodeType> minOp(nodes.data());
1946 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1947 minSDFValue =
std::min(minSDFValue, minOp.minValue);
1951 mMinValue = minSDFValue;
1954 void operator()(
const tbb::blocked_range<size_t>& range)
const {
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>
1973 using TreeTypePtr =
typename TreeType::Ptr;
1975 using LeafNodeType =
typename TreeType::LeafNodeType;
1977 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1978 using BoolTreeTypePtr =
typename BoolTreeType::Ptr;
1979 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
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)
1989 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1991 std::vector<const BoolLeafNodeType*> nodes;
1993 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
1995 const BoolTreeType& mask = *
mMasks[
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()))
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>
2076 struct ComputeActiveVoxelCount
2078 ComputeActiveVoxelCount(std::vector<VolumePtrType>& segments,
size_t *countArray)
2079 : mSegments(!segments.empty() ? &segments.front() : nullptr)
2080 , mCountArray(countArray)
2084 void operator()(
const tbb::blocked_range<size_t>& range)
const {
2085 for (
size_t n = range.begin(), N = range.end(); n <
N; ++
n) {
2086 mCountArray[
n] = mSegments[
n]->activeVoxelCount();
2090 VolumePtrType *
const mSegments;
2091 size_t *
const mCountArray;
2097 GreaterCount(
const size_t *countArray) : mCountArray(countArray) {}
2099 inline bool operator() (
const size_t& lhs,
const size_t& rhs)
const
2101 return (mCountArray[lhs] > mCountArray[rhs]);
2104 size_t const *
const mCountArray;
2110 template<
typename TreeType>
2111 struct GridOrTreeConstructor
2113 using TreeTypePtr =
typename TreeType::Ptr;
2114 using BoolTreePtrType =
typename TreeType::template ValueConverter<bool>::Type::Ptr;
2116 static BoolTreePtrType constructMask(
const TreeType&, BoolTreePtrType& maskTree)
2117 {
return maskTree; }
2118 static TreeTypePtr construct(
const TreeType&, TreeTypePtr& tree) {
return tree; }
2122 template<
typename TreeType>
2123 struct GridOrTreeConstructor<Grid<TreeType> >
2126 using GridTypePtr =
typename Grid<TreeType>::Ptr;
2127 using TreeTypePtr =
typename TreeType::Ptr;
2129 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2130 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2131 using BoolGridType = Grid<BoolTreeType>;
2132 using BoolGridPtrType =
typename BoolGridType::Ptr;
2134 static BoolGridPtrType constructMask(
const GridType& grid, BoolTreePtrType& maskTree) {
2135 BoolGridPtrType maskGrid(BoolGridType::create(maskTree));
2136 maskGrid->setTransform(grid.transform().copy());
2140 static GridTypePtr construct(
const GridType& grid, TreeTypePtr& maskTree) {
2141 GridTypePtr maskGrid(GridType::create(maskTree));
2142 maskGrid->setTransform(grid.transform().copy());
2143 maskGrid->insertMeta(grid);
2157 template <
class Gr
idType>
2162 using TreeType =
typename GridType::TreeType;
2163 using LeafNodeType =
typename TreeType::LeafNodeType;
2164 using RootNodeType =
typename TreeType::RootNodeType;
2165 using NodeChainType =
typename RootNodeType::NodeChainType;
2166 using InternalNodeType =
typename NodeChainType::template Get<1>;
2170 TreeType& tree = grid.tree();
2172 size_t numLeafNodes = 0, numInternalNodes = 0;
2174 std::vector<LeafNodeType*> nodes;
2175 std::vector<size_t> leafnodeCount;
2179 std::vector<InternalNodeType*> internalNodes;
2180 tree.getNodes(internalNodes);
2182 numInternalNodes = internalNodes.size();
2184 leafnodeCount.push_back(0);
2185 for (
size_t n = 0; n < numInternalNodes; ++
n) {
2186 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[
n]->leafCount());
2189 numLeafNodes = leafnodeCount.back();
2192 nodes.reserve(numLeafNodes);
2194 for (
size_t n = 0; n < numInternalNodes; ++
n) {
2195 internalNodes[
n]->stealNodes(nodes, tree.background(),
false);
2202 level_set_util_internal::FindMinTileValue<InternalNodeType> minOp(internalNodes.data());
2203 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), minOp);
2204 minSDFValue =
std::min(minSDFValue, minOp.minValue);
2208 level_set_util_internal::FindMinVoxelValue<LeafNodeType> minOp(nodes.data());
2209 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
2210 minSDFValue =
std::min(minSDFValue, minOp.minValue);
2213 cutoffDistance = -
std::abs(cutoffDistance);
2214 cutoffDistance = minSDFValue > cutoffDistance ? minSDFValue : cutoffDistance;
2221 level_set_util_internal::SDFVoxelsToFogVolume<LeafNodeType>(nodes.data(), cutoffDistance));
2224 typename TreeType::Ptr newTree(
new TreeType(
ValueType(0.0)));
2226 level_set_util_internal::PopulateTree<TreeType> populate(
2227 *newTree, nodes.data(), leafnodeCount.data(), 0);
2228 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
2231 std::vector<InternalNodeType*> internalNodes;
2232 newTree->getNodes(internalNodes);
2235 level_set_util_internal::SDFTilesToFogVolume<TreeType, InternalNodeType>(
2236 tree, internalNodes.data()));
2241 typename TreeType::ValueAllIter it(*newTree);
2242 it.setMaxDepth(TreeType::ValueAllIter::LEAF_DEPTH - 2);
2247 it.setActiveState(
true);
2255 typename TreeType::ValueAllIter it(tree);
2256 it.setMaxDepth(TreeType::ValueAllIter::ROOT_DEPTH);
2265 grid.setTree(newTree);
2273 template <
class Gr
idOrTreeType>
2274 typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2280 using BoolTreePtrType =
typename TreeType::template ValueConverter<bool>::Type::Ptr;
2281 BoolTreePtrType mask = level_set_util_internal::computeInteriorMask(tree, isovalue);
2283 return level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::constructMask(
2288 template<
typename Gr
idOrTreeType>
2289 typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2298 using CharTreePtrType =
typename TreeType::template ValueConverter<char>::Type::Ptr;
2299 CharTreePtrType regionMask = level_set_util_internal::computeEnclosedRegionMask(
2300 tree, isovalue, fillMask);
2302 using BoolTreePtrType =
typename TreeType::template ValueConverter<bool>::Type::Ptr;
2303 BoolTreePtrType mask = level_set_util_internal::computeInteriorMask(*regionMask, 0);
2305 return level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::constructMask(
2313 template<
typename Gr
idOrTreeType>
2314 typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2320 std::vector<const typename TreeType::LeafNodeType*> nodes;
2321 tree.getNodes(nodes);
2323 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2324 typename BoolTreeType::Ptr
mask(
new BoolTreeType(
false));
2326 level_set_util_internal::MaskIsovalueCrossingVoxels<TreeType> op(tree, nodes, *mask, isovalue);
2327 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
2329 return level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::constructMask(
2337 template<
typename Gr
idOrTreeType>
2340 std::vector<
typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr>& masks)
2343 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2344 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2345 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
2346 using BoolGridOrTreePtrType =
typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr;
2348 using NodeMaskSegmentType = level_set_util_internal::NodeMaskSegment<BoolLeafNodeType>;
2349 using NodeMaskSegmentPtrType =
typename NodeMaskSegmentType::Ptr;
2350 using NodeMaskSegmentPtrVector =
typename std::vector<NodeMaskSegmentPtrType>;
2351 using NodeMaskSegmentRawPtrVector =
typename std::vector<NodeMaskSegmentType*>;
2357 BoolTreeType topologyMask(tree,
false,
TopologyCopy());
2362 if (topologyMask.hasActiveTiles()) {
2363 topologyMask.voxelizeActiveTiles();
2366 std::vector<BoolLeafNodeType*> leafnodes;
2367 topologyMask.getNodes(leafnodes);
2369 if (leafnodes.empty())
return;
2374 std::unique_ptr<NodeMaskSegmentPtrVector[]> nodeSegmentArray(
2375 new NodeMaskSegmentPtrVector[leafnodes.size()]);
2378 level_set_util_internal::SegmentNodeMask<BoolLeafNodeType>(
2379 leafnodes, nodeSegmentArray.get()));
2385 level_set_util_internal::ConnectNodeMaskSegments<BoolTreeType, BoolLeafNodeType>(
2386 topologyMask, nodeSegmentArray.get()));
2388 topologyMask.clear();
2390 size_t nodeSegmentCount = 0;
2391 for (
size_t n = 0, N = leafnodes.size(); n <
N; ++
n) {
2392 nodeSegmentCount += nodeSegmentArray[
n].size();
2397 std::deque<NodeMaskSegmentRawPtrVector> nodeSegmentGroups;
2399 NodeMaskSegmentType* nextSegment = nodeSegmentArray[0][0].get();
2400 while (nextSegment) {
2402 nodeSegmentGroups.push_back(NodeMaskSegmentRawPtrVector());
2404 std::vector<NodeMaskSegmentType*>& segmentGroup = nodeSegmentGroups.back();
2405 segmentGroup.reserve(nodeSegmentCount);
2407 std::deque<NodeMaskSegmentType*> segmentQueue;
2408 segmentQueue.push_back(nextSegment);
2409 nextSegment =
nullptr;
2411 while (!segmentQueue.empty()) {
2413 NodeMaskSegmentType* segment = segmentQueue.back();
2414 segmentQueue.pop_back();
2416 if (segment->visited)
continue;
2417 segment->visited =
true;
2419 segmentGroup.push_back(segment);
2422 std::vector<NodeMaskSegmentType*>& connections = segment->connections;
2423 for (
size_t n = 0, N = connections.size(); n <
N; ++
n) {
2424 if (!connections[n]->visited) segmentQueue.push_back(connections[n]);
2429 for (
size_t n = 0, N = leafnodes.size(); n <
N; ++
n) {
2430 NodeMaskSegmentPtrVector& nodeSegments = nodeSegmentArray[
n];
2431 for (
size_t i = 0, I = nodeSegments.size(); i < I; ++i) {
2432 if (!nodeSegments[i]->visited) nextSegment = nodeSegments[i].get();
2439 if (nodeSegmentGroups.size() == 1) {
2445 if (mask->hasActiveTiles()) {
2446 mask->voxelizeActiveTiles();
2450 level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::constructMask(
2453 }
else if (nodeSegmentGroups.size() > 1) {
2455 for (
size_t n = 0, N = nodeSegmentGroups.size(); n <
N; ++
n) {
2457 NodeMaskSegmentRawPtrVector& segmentGroup = nodeSegmentGroups[
n];
2459 level_set_util_internal::MaskSegmentGroup<BoolTreeType> op(segmentGroup);
2460 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, segmentGroup.size()), op);
2463 level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::constructMask(
2464 volume, op.mask()));
2470 if (masks.size() > 1) {
2471 const size_t segmentCount = masks.size();
2473 std::unique_ptr<size_t[]> segmentOrderArray(
new size_t[segmentCount]);
2474 std::unique_ptr<size_t[]> voxelCountArray(
new size_t[segmentCount]);
2476 for (
size_t n = 0; n < segmentCount; ++
n) {
2477 segmentOrderArray[
n] =
n;
2481 level_set_util_internal::ComputeActiveVoxelCount<BoolGridOrTreePtrType>(
2482 masks, voxelCountArray.get()));
2484 size_t *
begin = segmentOrderArray.get();
2485 tbb::parallel_sort(begin, begin + masks.size(), level_set_util_internal::GreaterCount(
2486 voxelCountArray.get()));
2488 std::vector<BoolGridOrTreePtrType> orderedMasks;
2489 orderedMasks.reserve(masks.size());
2491 for (
size_t n = 0; n < segmentCount; ++
n) {
2492 orderedMasks.push_back(masks[segmentOrderArray[n]]);
2495 masks.swap(orderedMasks);
2501 template<
typename Gr
idOrTreeType>
2504 std::vector<typename GridOrTreeType::Ptr>& segments)
2507 using TreePtrType =
typename TreeType::Ptr;
2508 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2509 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2514 std::vector<BoolTreePtrType> maskSegmentArray;
2519 const size_t numSegments =
std::max(
size_t(1), maskSegmentArray.size());
2520 std::vector<TreePtrType> outputSegmentArray(numSegments);
2522 if (maskSegmentArray.empty()) {
2525 outputSegmentArray[0] = TreePtrType(
new TreeType(inputTree.background()));
2526 }
else if (numSegments == 1) {
2528 TreePtrType segment(
new TreeType(inputTree));
2531 if (segment->leafCount() != inputTree.leafCount()) {
2532 segment->topologyIntersection(*maskSegmentArray[0]);
2534 outputSegmentArray[0] = segment;
2536 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
2538 level_set_util_internal::MaskedCopy<TreeType>(inputTree, outputSegmentArray,
2542 for (
auto& segment : outputSegmentArray) {
2544 level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::construct(
2550 template<
typename Gr
idOrTreeType>
2552 segmentSDF(
const GridOrTreeType& volume, std::vector<typename GridOrTreeType::Ptr>& segments)
2555 using TreePtrType =
typename TreeType::Ptr;
2556 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2557 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2565 std::vector<BoolTreePtrType> maskSegmentArray;
2568 const size_t numSegments =
std::max(
size_t(1), maskSegmentArray.size());
2569 std::vector<TreePtrType> outputSegmentArray(numSegments);
2571 if (maskSegmentArray.empty()) {
2574 outputSegmentArray[0] = TreePtrType(
new TreeType(inputTree.background()));
2576 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
2580 level_set_util_internal::ExpandNarrowbandMask<TreeType>(inputTree, maskSegmentArray));
2585 inputTree, outputSegmentArray, maskSegmentArray));
2588 level_set_util_internal::FloodFillSign<TreeType>(inputTree, outputSegmentArray));
2591 for (
auto& segment : outputSegmentArray) {
2593 level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::construct(
2604 #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION
2606 #ifdef OPENVDB_INSTANTIATE_LEVELSETUTIL
2610 #define _FUNCTION(TreeT) \
2611 void sdfToFogVolume(Grid<TreeT>&, TreeT::ValueType)
2615 #define _FUNCTION(TreeT) \
2616 TreeT::ValueConverter<bool>::Type::Ptr sdfInteriorMask(const TreeT&, TreeT::ValueType)
2620 #define _FUNCTION(TreeT) \
2621 Grid<TreeT>::ValueConverter<bool>::Type::Ptr sdfInteriorMask(const Grid<TreeT>&, TreeT::ValueType)
2625 #define _FUNCTION(TreeT) \
2626 TreeT::ValueConverter<bool>::Type::Ptr extractEnclosedRegion(\
2627 const TreeT&, TreeT::ValueType, \
2628 const TreeAdapter<TreeT>::TreeType::ValueConverter<bool>::Type*)
2632 #define _FUNCTION(TreeT) \
2633 Grid<TreeT>::ValueConverter<bool>::Type::Ptr extractEnclosedRegion(\
2634 const Grid<TreeT>&, TreeT::ValueType, \
2635 const TreeAdapter<Grid<TreeT>>::TreeType::ValueConverter<bool>::Type*)
2639 #define _FUNCTION(TreeT) \
2640 TreeT::ValueConverter<bool>::Type::Ptr extractIsosurfaceMask(const TreeT&, TreeT::ValueType)
2644 #define _FUNCTION(TreeT) \
2645 Grid<TreeT>::ValueConverter<bool>::Type::Ptr extractIsosurfaceMask(const Grid<TreeT>&, TreeT::ValueType)
2649 #define _FUNCTION(TreeT) \
2650 void extractActiveVoxelSegmentMasks(\
2651 const TreeT&, std::vector<TreeT::ValueConverter<bool>::Type::Ptr>&)
2655 #define _FUNCTION(TreeT) \
2656 void extractActiveVoxelSegmentMasks(\
2657 const Grid<TreeT>&, std::vector<Grid<TreeT>::ValueConverter<bool>::Type::Ptr>&)
2661 #define _FUNCTION(TreeT) \
2662 void segmentActiveVoxels(const TreeT&, std::vector<TreeT::Ptr>&)
2666 #define _FUNCTION(TreeT) \
2667 void segmentActiveVoxels(const Grid<TreeT>&, std::vector<Grid<TreeT>::Ptr>&)
2671 #define _FUNCTION(TreeT) \
2672 void segmentSDF(const TreeT&, std::vector<TreeT::Ptr>&)
2676 #define _FUNCTION(TreeT) \
2677 void segmentSDF(const Grid<TreeT>&, std::vector<Grid<TreeT>::Ptr>&)
2681 #endif // OPENVDB_USE_EXPLICIT_INSTANTIATION
2688 #endif // OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
void parallel_for(int64_t start, int64_t end, std::function< void(int64_t index)> &&task, parallel_options opt=parallel_options(0, Split_Y, 1))
typedef int(APIENTRYP RE_PFNGLXSWAPINTERVALSGIPROC)(int)
GA_API const UT_StringHolder dist
GridType
List of types that are currently supported by NanoVDB.
GLdouble GLdouble GLdouble z
#define OPENVDB_REAL_TREE_INSTANTIATE(Function)
#define OPENVDB_USE_VERSION_NAMESPACE
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
The Value Accessor Implementation and API methods. The majoirty of the API matches the API of a compa...
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
#define OPENVDB_ALL_TREE_INSTANTIATE(Function)
SYS_FORCE_INLINE const_iterator end() const
static TreeType & tree(TreeType &t)
Propagate the signs of distance values from the active voxels in the narrow band to the inactive valu...
GLenum GLsizei GLsizei GLint * values
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GA_API const UT_StringHolder N
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER IMATH_HOSTDEVICE constexpr T abs(T a) IMATH_NOEXCEPT
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
void OIIO_UTIL_API split(string_view str, std::vector< string_view > &result, string_view sep=string_view(), int maxsplit=-1)
Convert polygonal meshes that consist of quads and/or triangles into signed or unsigned distance fiel...
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Attribute-owned data structure for points. Point attributes are stored in leaf nodes and ordered by v...
PcpNodeRef_ChildrenIterator begin(const PcpNodeRef::child_const_range &r)
Support for range-based for loops for PcpNodeRef children ranges.