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);
181 namespace level_set_util_internal {
184 template<
typename LeafNodeType>
185 struct MaskInteriorVoxels {
187 using ValueType =
typename LeafNodeType::ValueType;
188 using BoolLeafNodeType = tree::LeafNode<bool, LeafNodeType::LOG2DIM>;
191 ValueType isovalue,
const LeafNodeType ** nodes, BoolLeafNodeType ** maskNodes)
192 : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
196 void operator()(
const tbb::blocked_range<size_t>& range)
const {
198 BoolLeafNodeType * maskNodePt =
nullptr;
200 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
202 mMaskNodes[n] =
nullptr;
203 const LeafNodeType& node = *mNodes[n];
206 maskNodePt =
new BoolLeafNodeType(node.origin(),
false);
208 maskNodePt->setOrigin(node.origin());
211 const ValueType* values = &node.getValue(0);
212 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
213 if (values[i] < mIsovalue) maskNodePt->setValueOn(i,
true);
216 if (maskNodePt->onVoxelCount() > 0) {
217 mMaskNodes[n] = maskNodePt;
218 maskNodePt =
nullptr;
222 if (maskNodePt)
delete maskNodePt;
225 LeafNodeType
const *
const *
const mNodes;
226 BoolLeafNodeType **
const mMaskNodes;
227 ValueType
const mIsovalue;
231 template<
typename TreeType,
typename InternalNodeType>
232 struct MaskInteriorTiles {
234 using ValueType =
typename TreeType::ValueType;
236 MaskInteriorTiles(ValueType isovalue,
const TreeType& tree, InternalNodeType ** maskNodes)
237 : mTree(&tree), mMaskNodes(maskNodes), mIsovalue(isovalue) { }
239 void operator()(
const tbb::blocked_range<size_t>& range)
const {
240 tree::ValueAccessor<const TreeType> acc(*mTree);
241 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
242 typename InternalNodeType::ValueAllIter it = mMaskNodes[n]->beginValueAll();
244 if (acc.getValue(it.getCoord()) < mIsovalue) {
252 TreeType
const *
const mTree;
253 InternalNodeType **
const mMaskNodes;
254 ValueType
const mIsovalue;
258 template<
typename TreeType>
259 struct PopulateTree {
261 using ValueType =
typename TreeType::ValueType;
262 using LeafNodeType =
typename TreeType::LeafNodeType;
264 PopulateTree(TreeType& tree, LeafNodeType** leafnodes,
265 const size_t * nodexIndexMap, ValueType background)
266 : mNewTree(background)
269 , mNodeIndexMap(nodexIndexMap)
273 PopulateTree(PopulateTree& rhs, tbb::split)
274 : mNewTree(rhs.mNewTree.background())
277 , mNodeIndexMap(rhs.mNodeIndexMap)
281 void operator()(
const tbb::blocked_range<size_t>& range) {
283 tree::ValueAccessor<TreeType> acc(*mTreePt);
286 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
287 for (
size_t i = mNodeIndexMap[n], I = mNodeIndexMap[n + 1]; i < I; ++i) {
288 if (mNodes[i] !=
nullptr) acc.addLeaf(mNodes[i]);
292 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
293 acc.addLeaf(mNodes[n]);
298 void join(PopulateTree& rhs) { mTreePt->merge(*rhs.mTreePt); }
302 TreeType *
const mTreePt;
303 LeafNodeType **
const mNodes;
304 size_t const *
const mNodeIndexMap;
309 template<
typename LeafNodeType>
310 struct LabelBoundaryVoxels {
312 using ValueType =
typename LeafNodeType::ValueType;
313 using CharLeafNodeType = tree::LeafNode<char, LeafNodeType::LOG2DIM>;
316 ValueType isovalue,
const LeafNodeType ** nodes, CharLeafNodeType ** maskNodes)
317 : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
321 void operator()(
const tbb::blocked_range<size_t>& range)
const {
323 CharLeafNodeType * maskNodePt =
nullptr;
325 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
327 mMaskNodes[n] =
nullptr;
328 const LeafNodeType& node = *mNodes[n];
331 maskNodePt =
new CharLeafNodeType(node.origin(), 1);
333 maskNodePt->setOrigin(node.origin());
336 typename LeafNodeType::ValueOnCIter it;
337 for (it = node.cbeginValueOn(); it; ++it) {
338 maskNodePt->setValueOn(it.pos(), ((*it - mIsovalue) < 0.0) ? 0 : 1);
341 if (maskNodePt->onVoxelCount() > 0) {
342 mMaskNodes[n] = maskNodePt;
343 maskNodePt =
nullptr;
347 if (maskNodePt)
delete maskNodePt;
350 LeafNodeType
const *
const *
const mNodes;
351 CharLeafNodeType **
const mMaskNodes;
352 ValueType
const mIsovalue;
356 template<
typename LeafNodeType>
357 struct FlipRegionSign {
358 using ValueType =
typename LeafNodeType::ValueType;
360 FlipRegionSign(LeafNodeType ** nodes) : mNodes(nodes) { }
362 void operator()(
const tbb::blocked_range<size_t>& range)
const {
363 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
364 ValueType* values =
const_cast<ValueType*
>(&mNodes[n]->getValue(0));
365 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
366 values[i] = values[i] < 0 ? 1 : -1;
371 LeafNodeType **
const mNodes;
375 template<
typename LeafNodeType>
376 struct FindMinVoxelValue {
378 using ValueType =
typename LeafNodeType::ValueType;
380 FindMinVoxelValue(LeafNodeType
const *
const *
const leafnodes)
381 : minValue(
std::numeric_limits<ValueType>::
max())
386 FindMinVoxelValue(FindMinVoxelValue& rhs, tbb::split)
387 : minValue(
std::numeric_limits<ValueType>::
max())
392 void operator()(
const tbb::blocked_range<size_t>& range) {
393 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
394 const ValueType* data = mNodes[n]->buffer().data();
395 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
396 minValue =
std::min(minValue, data[i]);
401 void join(FindMinVoxelValue& rhs) { minValue =
std::min(minValue, rhs.minValue); }
405 LeafNodeType
const *
const *
const mNodes;
409 template<
typename InternalNodeType>
410 struct FindMinTileValue {
412 using ValueType =
typename InternalNodeType::ValueType;
414 FindMinTileValue(InternalNodeType
const *
const *
const nodes)
415 : minValue(
std::numeric_limits<ValueType>::
max())
420 FindMinTileValue(FindMinTileValue& rhs, tbb::split)
421 : minValue(
std::numeric_limits<ValueType>::
max())
426 void operator()(
const tbb::blocked_range<size_t>& range) {
427 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
428 typename InternalNodeType::ValueAllCIter it = mNodes[n]->beginValueAll();
435 void join(FindMinTileValue& rhs) { minValue =
std::min(minValue, rhs.minValue); }
439 InternalNodeType
const *
const *
const mNodes;
443 template<
typename LeafNodeType>
444 struct SDFVoxelsToFogVolume {
446 using ValueType =
typename LeafNodeType::ValueType;
448 SDFVoxelsToFogVolume(LeafNodeType ** nodes, ValueType cutoffDistance)
449 : mNodes(nodes), mWeight(ValueType(1.0) / cutoffDistance)
453 void operator()(
const tbb::blocked_range<size_t>& range)
const {
455 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
457 LeafNodeType& node = *mNodes[n];
460 ValueType* values = node.buffer().data();
461 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
462 values[i] = values[i] > ValueType(0.0) ? ValueType(0.0) : values[i] * mWeight;
463 if (values[i] > ValueType(0.0)) node.setValueOn(i);
466 if (node.onVoxelCount() == 0) {
473 LeafNodeType **
const mNodes;
474 ValueType
const mWeight;
478 template<
typename TreeType,
typename InternalNodeType>
479 struct SDFTilesToFogVolume {
481 SDFTilesToFogVolume(
const TreeType& tree, InternalNodeType ** nodes)
482 : mTree(&tree), mNodes(nodes) { }
484 void operator()(
const tbb::blocked_range<size_t>& range)
const {
486 using ValueType =
typename TreeType::ValueType;
487 tree::ValueAccessor<const TreeType> acc(*mTree);
489 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
490 typename InternalNodeType::ValueAllIter it = mNodes[n]->beginValueAll();
492 if (acc.getValue(it.getCoord()) < ValueType(0.0)) {
493 it.setValue(ValueType(1.0));
500 TreeType
const *
const mTree;
501 InternalNodeType **
const mNodes;
505 template<
typename TreeType>
506 struct FillMaskBoundary {
508 using ValueType =
typename TreeType::ValueType;
509 using LeafNodeType =
typename TreeType::LeafNodeType;
510 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
511 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
513 FillMaskBoundary(
const TreeType& tree, ValueType isovalue,
const BoolTreeType& fillMask,
514 const BoolLeafNodeType ** fillNodes, BoolLeafNodeType ** newNodes)
516 , mFillMask(&fillMask)
517 , mFillNodes(fillNodes)
518 , mNewNodes(newNodes)
519 , mIsovalue(isovalue)
523 void operator()(
const tbb::blocked_range<size_t>& range)
const {
525 tree::ValueAccessor<const BoolTreeType> maskAcc(*mFillMask);
526 tree::ValueAccessor<const TreeType> distAcc(*mTree);
528 std::unique_ptr<char[]> valueMask(
new char[BoolLeafNodeType::SIZE]);
530 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
532 mNewNodes[n] =
nullptr;
533 const BoolLeafNodeType& node = *mFillNodes[n];
534 const Coord& origin = node.origin();
536 const bool denseNode = node.isDense();
541 int denseNeighbors = 0;
543 const BoolLeafNodeType* neighborNode =
544 maskAcc.probeConstLeaf(origin.offsetBy(-1, 0, 0));
545 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
547 neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(BoolLeafNodeType::DIM, 0, 0));
548 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
550 neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, -1, 0));
551 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
553 neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, BoolLeafNodeType::DIM, 0));
554 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
556 neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, 0, -1));
557 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
559 neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, 0, BoolLeafNodeType::DIM));
560 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
562 if (denseNeighbors == 6)
continue;
566 memset(valueMask.get(), 0,
sizeof(
char) * BoolLeafNodeType::SIZE);
568 const typename TreeType::LeafNodeType* distNode = distAcc.probeConstLeaf(origin);
572 bool earlyTermination =
false;
576 evalInternalNeighborsP(valueMask.get(), node, *distNode);
577 evalInternalNeighborsN(valueMask.get(), node, *distNode);
578 }
else if (distAcc.getValue(origin) > mIsovalue) {
579 earlyTermination = evalInternalNeighborsP(valueMask.get(), node);
580 if (!earlyTermination) {
581 earlyTermination = evalInternalNeighborsN(valueMask.get(), node);
588 if (!earlyTermination) {
589 evalExternalNeighborsX<true>(valueMask.get(), node, maskAcc, distAcc);
590 evalExternalNeighborsX<false>(valueMask.get(), node, maskAcc, distAcc);
591 evalExternalNeighborsY<true>(valueMask.get(), node, maskAcc, distAcc);
592 evalExternalNeighborsY<false>(valueMask.get(), node, maskAcc, distAcc);
593 evalExternalNeighborsZ<true>(valueMask.get(), node, maskAcc, distAcc);
594 evalExternalNeighborsZ<false>(valueMask.get(), node, maskAcc, distAcc);
599 int numBoundaryValues = 0;
600 for (
Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
601 numBoundaryValues += valueMask[i] == 1;
604 if (numBoundaryValues > 0) {
605 mNewNodes[n] =
new BoolLeafNodeType(origin,
false);
606 for (
Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
607 if (valueMask[i] == 1) mNewNodes[n]->setValueOn(i);
615 void evalInternalNeighborsP(
char* valueMask,
const BoolLeafNodeType& node,
616 const LeafNodeType& distNode)
const
618 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
619 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
620 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
621 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
622 for (
Index z = 0; z < BoolLeafNodeType::DIM - 1; ++z) {
623 const Index pos = yPos + z;
625 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
627 if (!node.isValueOn(pos + 1) && distNode.getValue(pos + 1) > mIsovalue) {
634 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
635 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
636 for (
Index y = 0; y < BoolLeafNodeType::DIM - 1; ++y) {
637 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
638 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
639 const Index pos = yPos + z;
641 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
643 if (!node.isValueOn(pos + BoolLeafNodeType::DIM) &&
644 distNode.getValue(pos + BoolLeafNodeType::DIM) > mIsovalue) {
651 for (
Index x = 0; x < BoolLeafNodeType::DIM - 1; ++x) {
652 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
653 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
654 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
655 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
656 const Index pos = yPos + z;
658 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
660 if (!node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
661 (distNode.getValue(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)
671 bool evalInternalNeighborsP(
char* valueMask,
const BoolLeafNodeType& node)
const {
673 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
674 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
675 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
676 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
677 for (
Index z = 0; z < BoolLeafNodeType::DIM - 1; ++z) {
678 const Index pos = yPos + z;
680 if (node.isValueOn(pos) && !node.isValueOn(pos + 1)) {
688 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
689 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
690 for (
Index y = 0; y < BoolLeafNodeType::DIM - 1; ++y) {
691 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
692 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
693 const Index pos = yPos + z;
695 if (node.isValueOn(pos) && !node.isValueOn(pos + BoolLeafNodeType::DIM)) {
703 for (
Index x = 0; x < BoolLeafNodeType::DIM - 1; ++x) {
704 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
705 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
706 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
707 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
708 const Index pos = yPos + z;
710 if (node.isValueOn(pos) &&
711 !node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
724 void evalInternalNeighborsN(
char* valueMask,
const BoolLeafNodeType& node,
725 const LeafNodeType& distNode)
const
727 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
728 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
729 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
730 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
731 for (
Index z = 1; z < BoolLeafNodeType::DIM; ++z) {
732 const Index pos = yPos + z;
734 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
736 if (!node.isValueOn(pos - 1) && distNode.getValue(pos - 1) > mIsovalue) {
743 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
744 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
745 for (
Index y = 1; y < BoolLeafNodeType::DIM; ++y) {
746 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
747 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
748 const Index pos = yPos + z;
750 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
752 if (!node.isValueOn(pos - BoolLeafNodeType::DIM) &&
753 distNode.getValue(pos - BoolLeafNodeType::DIM) > mIsovalue) {
760 for (
Index x = 1; x < BoolLeafNodeType::DIM; ++x) {
761 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
762 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
763 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
764 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
765 const Index pos = yPos + z;
767 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
769 if (!node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
770 (distNode.getValue(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)
781 bool evalInternalNeighborsN(
char* valueMask,
const BoolLeafNodeType& node)
const {
783 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
784 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
785 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
786 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
787 for (
Index z = 1; z < BoolLeafNodeType::DIM; ++z) {
788 const Index pos = yPos + z;
790 if (node.isValueOn(pos) && !node.isValueOn(pos - 1)) {
798 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
799 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
800 for (
Index y = 1; y < BoolLeafNodeType::DIM; ++y) {
801 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
802 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
803 const Index pos = yPos + z;
805 if (node.isValueOn(pos) && !node.isValueOn(pos - BoolLeafNodeType::DIM)) {
813 for (
Index x = 1; x < BoolLeafNodeType::DIM; ++x) {
814 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
815 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
816 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
817 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
818 const Index pos = yPos + z;
820 if (node.isValueOn(pos) &&
821 !node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
836 template<
bool UpWind>
837 void evalExternalNeighborsX(
char* valueMask,
const BoolLeafNodeType& node,
838 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
839 const tree::ValueAccessor<const TreeType>& distAcc)
const {
841 const Coord& origin = node.origin();
842 Coord ijk(0, 0, 0), nijk;
847 ijk[0] = int(BoolLeafNodeType::DIM) - 1;
850 const Index xPos = ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM));
852 for (ijk[1] = 0; ijk[1] < int(BoolLeafNodeType::DIM); ++ijk[1]) {
853 const Index yPos = xPos + (ijk[1] << int(BoolLeafNodeType::LOG2DIM));
855 for (ijk[2] = 0; ijk[2] < int(BoolLeafNodeType::DIM); ++ijk[2]) {
856 const Index pos = yPos + ijk[2];
858 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
860 nijk = origin + ijk.offsetBy(step, 0, 0);
862 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
871 template<
bool UpWind>
872 void evalExternalNeighborsY(
char* valueMask,
const BoolLeafNodeType& node,
873 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
874 const tree::ValueAccessor<const TreeType>& distAcc)
const {
876 const Coord& origin = node.origin();
877 Coord ijk(0, 0, 0), nijk;
882 ijk[1] = int(BoolLeafNodeType::DIM) - 1;
885 const Index yPos = ijk[1] << int(BoolLeafNodeType::LOG2DIM);
887 for (ijk[0] = 0; ijk[0] < int(BoolLeafNodeType::DIM); ++ijk[0]) {
888 const Index xPos = yPos + (ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM)));
890 for (ijk[2] = 0; ijk[2] < int(BoolLeafNodeType::DIM); ++ijk[2]) {
891 const Index pos = xPos + ijk[2];
893 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
895 nijk = origin + ijk.offsetBy(0, step, 0);
896 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
905 template<
bool UpWind>
906 void evalExternalNeighborsZ(
char* valueMask,
const BoolLeafNodeType& node,
907 const tree::ValueAccessor<const BoolTreeType>& maskAcc,
908 const tree::ValueAccessor<const TreeType>& distAcc)
const {
910 const Coord& origin = node.origin();
911 Coord ijk(0, 0, 0), nijk;
916 ijk[2] = int(BoolLeafNodeType::DIM) - 1;
919 for (ijk[0] = 0; ijk[0] < int(BoolLeafNodeType::DIM); ++ijk[0]) {
920 const Index xPos = ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM));
922 for (ijk[1] = 0; ijk[1] < int(BoolLeafNodeType::DIM); ++ijk[1]) {
923 const Index pos = ijk[2] + xPos + (ijk[1] << int(BoolLeafNodeType::LOG2DIM));
925 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
927 nijk = origin + ijk.offsetBy(0, 0, step);
928 if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
938 TreeType
const *
const mTree;
939 BoolTreeType
const *
const mFillMask;
940 BoolLeafNodeType
const *
const *
const mFillNodes;
941 BoolLeafNodeType **
const mNewNodes;
942 ValueType
const mIsovalue;
948 template <
class TreeType>
949 inline typename TreeType::template ValueConverter<char>::Type::Ptr
950 computeEnclosedRegionMask(
const TreeType& tree,
typename TreeType::ValueType isovalue,
951 const typename TreeType::template ValueConverter<bool>::Type* fillMask)
953 using LeafNodeType =
typename TreeType::LeafNodeType;
954 using RootNodeType =
typename TreeType::RootNodeType;
955 using NodeChainType =
typename RootNodeType::NodeChainType;
956 using InternalNodeType =
typename NodeChainType::template Get<1>;
958 using CharTreeType =
typename TreeType::template ValueConverter<char>::Type;
959 using CharLeafNodeType =
typename CharTreeType::LeafNodeType;
961 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
962 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
964 const TreeType* treePt = &tree;
966 size_t numLeafNodes = 0, numInternalNodes = 0;
968 std::vector<const LeafNodeType*> nodes;
969 std::vector<size_t> leafnodeCount;
973 std::vector<const InternalNodeType*> internalNodes;
974 treePt->getNodes(internalNodes);
976 numInternalNodes = internalNodes.size();
978 leafnodeCount.push_back(0);
979 for (
size_t n = 0; n < numInternalNodes; ++n) {
980 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
983 numLeafNodes = leafnodeCount.back();
986 nodes.reserve(numLeafNodes);
988 for (
size_t n = 0; n < numInternalNodes; ++n) {
989 internalNodes[n]->getNodes(nodes);
994 std::unique_ptr<CharLeafNodeType*[]> maskNodes(
new CharLeafNodeType*[numLeafNodes]);
996 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
997 LabelBoundaryVoxels<LeafNodeType>(isovalue, nodes.data(), maskNodes.get()));
1000 typename CharTreeType::Ptr maskTree(
new CharTreeType(1));
1002 PopulateTree<CharTreeType> populate(*maskTree, maskNodes.get(), leafnodeCount.data(), 1);
1003 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1007 std::vector<CharLeafNodeType*> extraMaskNodes;
1011 std::vector<const BoolLeafNodeType*> fillMaskNodes;
1012 fillMask->getNodes(fillMaskNodes);
1014 std::unique_ptr<BoolLeafNodeType*[]> boundaryMaskNodes(
1015 new BoolLeafNodeType*[fillMaskNodes.size()]);
1017 tbb::parallel_for(tbb::blocked_range<size_t>(0, fillMaskNodes.size()),
1018 FillMaskBoundary<TreeType>(tree, isovalue, *fillMask, fillMaskNodes.data(),
1019 boundaryMaskNodes.get()));
1021 tree::ValueAccessor<CharTreeType> maskAcc(*maskTree);
1023 for (
size_t n = 0, N = fillMaskNodes.size(); n < N; ++n) {
1025 if (boundaryMaskNodes[n] ==
nullptr)
continue;
1027 const BoolLeafNodeType& boundaryNode = *boundaryMaskNodes[n];
1028 const Coord& origin = boundaryNode.origin();
1030 CharLeafNodeType* maskNodePt = maskAcc.probeLeaf(origin);
1033 maskNodePt = maskAcc.touchLeaf(origin);
1034 extraMaskNodes.push_back(maskNodePt);
1037 char* data = maskNodePt->buffer().data();
1039 typename BoolLeafNodeType::ValueOnCIter it = boundaryNode.cbeginValueOn();
1041 if (data[it.pos()] != 0) data[it.pos()] = -1;
1044 delete boundaryMaskNodes[n];
1052 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1053 FlipRegionSign<CharLeafNodeType>(maskNodes.get()));
1055 if (!extraMaskNodes.empty()) {
1056 tbb::parallel_for(tbb::blocked_range<size_t>(0, extraMaskNodes.size()),
1057 FlipRegionSign<CharLeafNodeType>(extraMaskNodes.data()));
1067 template <
class TreeType>
1068 inline typename TreeType::template ValueConverter<bool>::Type::Ptr
1069 computeInteriorMask(
const TreeType& tree,
typename TreeType::ValueType iso)
1071 using ValueType =
typename TreeType::ValueType;
1072 using LeafNodeType =
typename TreeType::LeafNodeType;
1073 using RootNodeType =
typename TreeType::RootNodeType;
1074 using NodeChainType =
typename RootNodeType::NodeChainType;
1075 using InternalNodeType =
typename NodeChainType::template Get<1>;
1077 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1078 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1079 using BoolRootNodeType =
typename BoolTreeType::RootNodeType;
1080 using BoolNodeChainType =
typename BoolRootNodeType::NodeChainType;
1081 using BoolInternalNodeType =
typename BoolNodeChainType::template Get<1>;
1091 static_cast<ValueType
>(tree.background() - math::Tolerance<ValueType>::value()));
1093 size_t numLeafNodes = 0, numInternalNodes = 0;
1095 std::vector<const LeafNodeType*> nodes;
1096 std::vector<size_t> leafnodeCount;
1100 std::vector<const InternalNodeType*> internalNodes;
1101 tree.getNodes(internalNodes);
1103 numInternalNodes = internalNodes.size();
1105 leafnodeCount.push_back(0);
1106 for (
size_t n = 0; n < numInternalNodes; ++n) {
1107 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
1110 numLeafNodes = leafnodeCount.back();
1113 nodes.reserve(numLeafNodes);
1115 for (
size_t n = 0; n < numInternalNodes; ++n) {
1116 internalNodes[n]->getNodes(nodes);
1121 std::unique_ptr<BoolLeafNodeType*[]> maskNodes(
new BoolLeafNodeType*[numLeafNodes]);
1123 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1124 MaskInteriorVoxels<LeafNodeType>(iso, nodes.data(), maskNodes.get()));
1128 typename BoolTreeType::Ptr maskTree(
new BoolTreeType(
false));
1130 PopulateTree<BoolTreeType> populate(*maskTree, maskNodes.get(), leafnodeCount.data(),
false);
1131 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1135 std::vector<BoolInternalNodeType*> internalMaskNodes;
1136 maskTree->getNodes(internalMaskNodes);
1138 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalMaskNodes.size()),
1139 MaskInteriorTiles<TreeType, BoolInternalNodeType>(iso, tree, internalMaskNodes.data()));
1141 tree::ValueAccessor<const TreeType> acc(tree);
1143 typename BoolTreeType::ValueAllIter it(*maskTree);
1144 it.setMaxDepth(BoolTreeType::ValueAllIter::LEAF_DEPTH - 2);
1147 if (acc.getValue(it.getCoord()) < iso) {
1149 it.setActiveState(
true);
1157 template<
typename InputTreeType>
1158 struct MaskIsovalueCrossingVoxels
1160 using InputValueType =
typename InputTreeType::ValueType;
1161 using InputLeafNodeType =
typename InputTreeType::LeafNodeType;
1162 using BoolTreeType =
typename InputTreeType::template ValueConverter<bool>::Type;
1163 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1165 MaskIsovalueCrossingVoxels(
1166 const InputTreeType& inputTree,
1167 const std::vector<const InputLeafNodeType*>& inputLeafNodes,
1168 BoolTreeType& maskTree,
1170 : mInputAccessor(inputTree)
1171 , mInputNodes(!inputLeafNodes.empty() ? &inputLeafNodes.front() : nullptr)
1173 , mMaskAccessor(maskTree)
1178 MaskIsovalueCrossingVoxels(MaskIsovalueCrossingVoxels& rhs, tbb::split)
1179 : mInputAccessor(rhs.mInputAccessor.tree())
1180 , mInputNodes(rhs.mInputNodes)
1182 , mMaskAccessor(mMaskTree)
1183 , mIsovalue(rhs.mIsovalue)
1187 void operator()(
const tbb::blocked_range<size_t>& range) {
1189 const InputValueType iso = mIsovalue;
1192 BoolLeafNodeType* maskNodePt =
nullptr;
1194 for (
size_t n = range.begin(); mInputNodes && (n != range.end()); ++n) {
1196 const InputLeafNodeType& node = *mInputNodes[n];
1198 if (!maskNodePt) maskNodePt =
new BoolLeafNodeType(node.origin(),
false);
1199 else maskNodePt->setOrigin(node.origin());
1201 bool collectedData =
false;
1203 for (
typename InputLeafNodeType::ValueOnCIter it = node.cbeginValueOn(); it; ++it) {
1205 bool isUnder = *it < iso;
1207 ijk = it.getCoord();
1210 bool signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1215 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1221 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1227 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1233 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1239 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1244 collectedData =
true;
1245 maskNodePt->setValueOn(it.pos(),
true);
1249 if (collectedData) {
1250 mMaskAccessor.addLeaf(maskNodePt);
1251 maskNodePt =
nullptr;
1255 if (maskNodePt)
delete maskNodePt;
1258 void join(MaskIsovalueCrossingVoxels& rhs) {
1259 mMaskAccessor.tree().merge(rhs.mMaskAccessor.tree());
1263 tree::ValueAccessor<const InputTreeType> mInputAccessor;
1264 InputLeafNodeType
const *
const *
const mInputNodes;
1266 BoolTreeType mMaskTree;
1267 tree::ValueAccessor<BoolTreeType> mMaskAccessor;
1269 InputValueType mIsovalue;
1276 template<
typename NodeType>
1277 struct NodeMaskSegment
1279 using Ptr = SharedPtr<NodeMaskSegment>;
1280 using NodeMaskType =
typename NodeType::NodeMaskType;
1282 NodeMaskSegment() : connections(), mask(false), origin(0,0,0), visited(false) {}
1284 std::vector<NodeMaskSegment*> connections;
1291 template<
typename NodeType>
1293 nodeMaskSegmentation(
const NodeType& node,
1294 std::vector<
typename NodeMaskSegment<NodeType>::Ptr>& segments)
1296 using NodeMaskType =
typename NodeType::NodeMaskType;
1297 using NodeMaskSegmentType = NodeMaskSegment<NodeType>;
1298 using NodeMaskSegmentTypePtr =
typename NodeMaskSegmentType::Ptr;
1300 NodeMaskType nodeMask(node.getValueMask());
1301 std::deque<Index> indexList;
1303 while (!nodeMask.isOff()) {
1305 NodeMaskSegmentTypePtr segment(
new NodeMaskSegmentType());
1306 segment->origin = node.origin();
1308 NodeMaskType& mask = segment->mask;
1310 indexList.push_back(nodeMask.findFirstOn());
1311 nodeMask.setOff(indexList.back());
1314 while (!indexList.empty()) {
1316 const Index pos = indexList.back();
1317 indexList.pop_back();
1319 if (mask.isOn(pos))
continue;
1322 ijk = NodeType::offsetToLocalCoord(pos);
1324 Index npos = pos - 1;
1325 if (ijk[2] != 0 && nodeMask.isOn(npos)) {
1326 nodeMask.setOff(npos);
1327 indexList.push_back(npos);
1331 if (ijk[2] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1332 nodeMask.setOff(npos);
1333 indexList.push_back(npos);
1336 npos = pos - NodeType::DIM;
1337 if (ijk[1] != 0 && nodeMask.isOn(npos)) {
1338 nodeMask.setOff(npos);
1339 indexList.push_back(npos);
1342 npos = pos + NodeType::DIM;
1343 if (ijk[1] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1344 nodeMask.setOff(npos);
1345 indexList.push_back(npos);
1348 npos = pos - NodeType::DIM * NodeType::DIM;
1349 if (ijk[0] != 0 && nodeMask.isOn(npos)) {
1350 nodeMask.setOff(npos);
1351 indexList.push_back(npos);
1354 npos = pos + NodeType::DIM * NodeType::DIM;
1355 if (ijk[0] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1356 nodeMask.setOff(npos);
1357 indexList.push_back(npos);
1362 segments.push_back(segment);
1367 template<
typename NodeType>
1368 struct SegmentNodeMask
1370 using NodeMaskSegmentType = NodeMaskSegment<NodeType>;
1371 using NodeMaskSegmentTypePtr =
typename NodeMaskSegmentType::Ptr;
1372 using NodeMaskSegmentVector =
typename std::vector<NodeMaskSegmentTypePtr>;
1374 SegmentNodeMask(std::vector<NodeType*>& nodes, NodeMaskSegmentVector* nodeMaskArray)
1375 : mNodes(!nodes.empty() ? &nodes.front() : nullptr)
1376 , mNodeMaskArray(nodeMaskArray)
1380 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1381 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1382 NodeType& node = *mNodes[n];
1383 nodeMaskSegmentation(node, mNodeMaskArray[n]);
1386 Coord& origin =
const_cast<Coord&
>(node.origin());
1387 origin[0] =
static_cast<int>(n);
1391 NodeType *
const *
const mNodes;
1392 NodeMaskSegmentVector *
const mNodeMaskArray;
1396 template<
typename TreeType,
typename NodeType>
1397 struct ConnectNodeMaskSegments
1399 using NodeMaskType =
typename NodeType::NodeMaskType;
1400 using NodeMaskSegmentType = NodeMaskSegment<NodeType>;
1401 using NodeMaskSegmentTypePtr =
typename NodeMaskSegmentType::Ptr;
1402 using NodeMaskSegmentVector =
typename std::vector<NodeMaskSegmentTypePtr>;
1404 ConnectNodeMaskSegments(
const TreeType& tree, NodeMaskSegmentVector* nodeMaskArray)
1406 , mNodeMaskArray(nodeMaskArray)
1410 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1412 tree::ValueAccessor<const TreeType> acc(*mTree);
1414 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1416 NodeMaskSegmentVector& segments = mNodeMaskArray[n];
1417 if (segments.empty())
continue;
1419 std::vector<std::set<NodeMaskSegmentType*> > connections(segments.size());
1421 Coord ijk = segments[0]->origin;
1423 const NodeType* node = acc.template probeConstNode<NodeType>(ijk);
1424 if (!node)
continue;
1428 ijk[2] += NodeType::DIM;
1429 const NodeType* nodeZUp = acc.template probeConstNode<NodeType>(ijk);
1430 ijk[2] -= (NodeType::DIM + NodeType::DIM);
1431 const NodeType* nodeZDown = acc.template probeConstNode<NodeType>(ijk);
1432 ijk[2] += NodeType::DIM;
1434 ijk[1] += NodeType::DIM;
1435 const NodeType* nodeYUp = acc.template probeConstNode<NodeType>(ijk);
1436 ijk[1] -= (NodeType::DIM + NodeType::DIM);
1437 const NodeType* nodeYDown = acc.template probeConstNode<NodeType>(ijk);
1438 ijk[1] += NodeType::DIM;
1440 ijk[0] += NodeType::DIM;
1441 const NodeType* nodeXUp = acc.template probeConstNode<NodeType>(ijk);
1442 ijk[0] -= (NodeType::DIM + NodeType::DIM);
1443 const NodeType* nodeXDown = acc.template probeConstNode<NodeType>(ijk);
1444 ijk[0] += NodeType::DIM;
1446 const Index startPos = node->getValueMask().findFirstOn();
1447 for (
Index pos = startPos; pos < NodeMaskType::SIZE; ++pos) {
1449 if (!node->isValueOn(pos))
continue;
1451 ijk = NodeType::offsetToLocalCoord(pos);
1453 #ifdef _MSC_FULL_VER
1454 #if _MSC_FULL_VER >= 190000000 && _MSC_FULL_VER < 190024210
1456 volatile Index npos = 0;
1465 npos = pos + (NodeType::DIM - 1);
1466 if (nodeZDown && nodeZDown->isValueOn(npos)) {
1467 NodeMaskSegmentType* nsegment =
1468 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeZDown)], npos);
1469 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1470 connections[idx].insert(nsegment);
1472 }
else if (ijk[2] == (NodeType::DIM - 1)) {
1473 npos = pos - (NodeType::DIM - 1);
1474 if (nodeZUp && nodeZUp->isValueOn(npos)) {
1475 NodeMaskSegmentType* nsegment =
1476 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeZUp)], npos);
1477 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1478 connections[idx].insert(nsegment);
1483 npos = pos + (NodeType::DIM - 1) * NodeType::DIM;
1484 if (nodeYDown && nodeYDown->isValueOn(npos)) {
1485 NodeMaskSegmentType* nsegment =
1486 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeYDown)], npos);
1487 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1488 connections[idx].insert(nsegment);
1490 }
else if (ijk[1] == (NodeType::DIM - 1)) {
1491 npos = pos - (NodeType::DIM - 1) * NodeType::DIM;
1492 if (nodeYUp && nodeYUp->isValueOn(npos)) {
1493 NodeMaskSegmentType* nsegment =
1494 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeYUp)], npos);
1495 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1496 connections[idx].insert(nsegment);
1501 npos = pos + (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1502 if (nodeXDown && nodeXDown->isValueOn(npos)) {
1503 NodeMaskSegmentType* nsegment =
1504 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeXDown)], npos);
1505 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1506 connections[idx].insert(nsegment);
1508 }
else if (ijk[0] == (NodeType::DIM - 1)) {
1509 npos = pos - (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1510 if (nodeXUp && nodeXUp->isValueOn(npos)) {
1511 NodeMaskSegmentType* nsegment =
1512 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeXUp)], npos);
1513 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1514 connections[idx].insert(nsegment);
1519 for (
size_t i = 0, I = connections.size(); i < I; ++i) {
1521 typename std::set<NodeMaskSegmentType*>::iterator
1522 it = connections[i].begin(), end = connections[i].end();
1524 std::vector<NodeMaskSegmentType*>& segmentConnections = segments[i]->connections;
1525 segmentConnections.reserve(connections.size());
1526 for (; it != end; ++it) {
1527 segmentConnections.push_back(*it);
1535 static inline size_t getNodeOffset(
const NodeType& node) {
1536 return static_cast<size_t>(node.origin()[0]);
1539 static inline NodeMaskSegmentType*
1540 findNodeMaskSegment(NodeMaskSegmentVector& segments,
Index pos)
1542 NodeMaskSegmentType* segment =
nullptr;
1544 for (
size_t n = 0, N = segments.size(); n < N; ++n) {
1545 if (segments[n]->mask.isOn(pos)) {
1546 segment = segments[n].get();
1555 findNodeMaskSegmentIndex(NodeMaskSegmentVector& segments,
Index pos)
1557 for (
Index n = 0, N =
Index(segments.size()); n < N; ++n) {
1558 if (segments[n]->mask.isOn(pos))
return n;
1563 TreeType
const *
const mTree;
1564 NodeMaskSegmentVector *
const mNodeMaskArray;
1568 template<
typename TreeType>
1569 struct MaskSegmentGroup
1571 using LeafNodeType =
typename TreeType::LeafNodeType;
1572 using TreeTypePtr =
typename TreeType::Ptr;
1573 using NodeMaskSegmentType = NodeMaskSegment<LeafNodeType>;
1575 MaskSegmentGroup(
const std::vector<NodeMaskSegmentType*>& segments)
1576 : mSegments(!segments.empty() ? &segments.front() : nullptr)
1577 , mTree(new TreeType(false))
1581 MaskSegmentGroup(
const MaskSegmentGroup& rhs, tbb::split)
1582 : mSegments(rhs.mSegments)
1583 , mTree(new TreeType(false))
1587 TreeTypePtr& mask() {
return mTree; }
1589 void join(MaskSegmentGroup& rhs) { mTree->merge(*rhs.mTree); }
1591 void operator()(
const tbb::blocked_range<size_t>& range) {
1593 tree::ValueAccessor<TreeType> acc(*mTree);
1595 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1596 NodeMaskSegmentType& segment = *mSegments[n];
1597 LeafNodeType* node = acc.touchLeaf(segment.origin);
1598 node->getValueMask() |= segment.mask;
1603 NodeMaskSegmentType *
const *
const mSegments;
1611 template<
typename TreeType>
1612 struct ExpandLeafNodeRegion
1614 using ValueType =
typename TreeType::ValueType;
1615 using LeafNodeType =
typename TreeType::LeafNodeType;
1616 using NodeMaskType =
typename LeafNodeType::NodeMaskType;
1618 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1619 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1623 ExpandLeafNodeRegion(
const TreeType& distTree, BoolTreeType& maskTree,
1624 std::vector<BoolLeafNodeType*>& maskNodes)
1625 : mDistTree(&distTree)
1626 , mMaskTree(&maskTree)
1627 , mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
1628 , mNewMaskTree(false)
1632 ExpandLeafNodeRegion(
const ExpandLeafNodeRegion& rhs, tbb::split)
1633 : mDistTree(rhs.mDistTree)
1634 , mMaskTree(rhs.mMaskTree)
1635 , mMaskNodes(rhs.mMaskNodes)
1636 , mNewMaskTree(false)
1640 BoolTreeType& newMaskTree() {
return mNewMaskTree; }
1642 void join(ExpandLeafNodeRegion& rhs) { mNewMaskTree.merge(rhs.mNewMaskTree); }
1644 void operator()(
const tbb::blocked_range<size_t>& range) {
1646 using NodeType = LeafNodeType;
1648 tree::ValueAccessor<const TreeType> distAcc(*mDistTree);
1649 tree::ValueAccessor<const BoolTreeType> maskAcc(*mMaskTree);
1650 tree::ValueAccessor<BoolTreeType> newMaskAcc(mNewMaskTree);
1652 NodeMaskType maskZUp, maskZDown, maskYUp, maskYDown, maskXUp, maskXDown;
1654 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1656 BoolLeafNodeType& maskNode = *mMaskNodes[n];
1657 if (maskNode.isEmpty())
continue;
1659 Coord ijk = maskNode.origin(), nijk;
1661 const LeafNodeType* distNode = distAcc.probeConstLeaf(ijk);
1662 if (!distNode)
continue;
1664 const ValueType *dataZUp =
nullptr, *dataZDown =
nullptr,
1665 *dataYUp =
nullptr, *dataYDown =
nullptr,
1666 *dataXUp =
nullptr, *dataXDown =
nullptr;
1668 ijk[2] += NodeType::DIM;
1669 getData(ijk, distAcc, maskAcc, maskZUp, dataZUp);
1670 ijk[2] -= (NodeType::DIM + NodeType::DIM);
1671 getData(ijk, distAcc, maskAcc, maskZDown, dataZDown);
1672 ijk[2] += NodeType::DIM;
1674 ijk[1] += NodeType::DIM;
1675 getData(ijk, distAcc, maskAcc, maskYUp, dataYUp);
1676 ijk[1] -= (NodeType::DIM + NodeType::DIM);
1677 getData(ijk, distAcc, maskAcc, maskYDown, dataYDown);
1678 ijk[1] += NodeType::DIM;
1680 ijk[0] += NodeType::DIM;
1681 getData(ijk, distAcc, maskAcc, maskXUp, dataXUp);
1682 ijk[0] -= (NodeType::DIM + NodeType::DIM);
1683 getData(ijk, distAcc, maskAcc, maskXDown, dataXDown);
1684 ijk[0] += NodeType::DIM;
1686 for (
typename BoolLeafNodeType::ValueOnIter it = maskNode.beginValueOn(); it; ++it) {
1688 const Index pos = it.pos();
1689 const ValueType val = std::abs(distNode->getValue(pos));
1691 ijk = BoolLeafNodeType::offsetToLocalCoord(pos);
1692 nijk = ijk + maskNode.origin();
1694 if (dataZUp && ijk[2] == (BoolLeafNodeType::DIM - 1)) {
1695 const Index npos = pos - (NodeType::DIM - 1);
1696 if (maskZUp.isOn(npos) && std::abs(dataZUp[npos]) > val) {
1697 newMaskAcc.setValueOn(nijk.offsetBy(0, 0, 1));
1699 }
else if (dataZDown && ijk[2] == 0) {
1700 const Index npos = pos + (NodeType::DIM - 1);
1701 if (maskZDown.isOn(npos) && std::abs(dataZDown[npos]) > val) {
1702 newMaskAcc.setValueOn(nijk.offsetBy(0, 0, -1));
1706 if (dataYUp && ijk[1] == (BoolLeafNodeType::DIM - 1)) {
1707 const Index npos = pos - (NodeType::DIM - 1) * NodeType::DIM;
1708 if (maskYUp.isOn(npos) && std::abs(dataYUp[npos]) > val) {
1709 newMaskAcc.setValueOn(nijk.offsetBy(0, 1, 0));
1711 }
else if (dataYDown && ijk[1] == 0) {
1712 const Index npos = pos + (NodeType::DIM - 1) * NodeType::DIM;
1713 if (maskYDown.isOn(npos) && std::abs(dataYDown[npos]) > val) {
1714 newMaskAcc.setValueOn(nijk.offsetBy(0, -1, 0));
1718 if (dataXUp && ijk[0] == (BoolLeafNodeType::DIM - 1)) {
1719 const Index npos = pos - (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1720 if (maskXUp.isOn(npos) && std::abs(dataXUp[npos]) > val) {
1721 newMaskAcc.setValueOn(nijk.offsetBy(1, 0, 0));
1723 }
else if (dataXDown && ijk[0] == 0) {
1724 const Index npos = pos + (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1725 if (maskXDown.isOn(npos) && std::abs(dataXDown[npos]) > val) {
1726 newMaskAcc.setValueOn(nijk.offsetBy(-1, 0, 0));
1737 getData(
const Coord& ijk, tree::ValueAccessor<const TreeType>& distAcc,
1738 tree::ValueAccessor<const BoolTreeType>& maskAcc, NodeMaskType& mask,
1739 const ValueType*& data)
1741 const LeafNodeType* node = distAcc.probeConstLeaf(ijk);
1743 data = node->buffer().data();
1744 mask = node->getValueMask();
1745 const BoolLeafNodeType* maskNodePt = maskAcc.probeConstLeaf(ijk);
1746 if (maskNodePt) mask -= maskNodePt->getValueMask();
1750 TreeType
const *
const mDistTree;
1751 BoolTreeType *
const mMaskTree;
1752 BoolLeafNodeType **
const mMaskNodes;
1754 BoolTreeType mNewMaskTree;
1758 template<
typename TreeType>
1759 struct FillLeafNodeVoxels
1761 using ValueType =
typename TreeType::ValueType;
1762 using LeafNodeType =
typename TreeType::LeafNodeType;
1763 using NodeMaskType =
typename LeafNodeType::NodeMaskType;
1764 using BoolLeafNodeType = tree::LeafNode<bool, LeafNodeType::LOG2DIM>;
1766 FillLeafNodeVoxels(
const TreeType& tree, std::vector<BoolLeafNodeType*>& maskNodes)
1767 : mTree(&tree), mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
1771 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1773 tree::ValueAccessor<const TreeType> distAcc(*mTree);
1775 std::vector<Index> indexList;
1776 indexList.reserve(NodeMaskType::SIZE);
1778 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1780 BoolLeafNodeType& maskNode = *mMaskNodes[n];
1782 const LeafNodeType * distNode = distAcc.probeConstLeaf(maskNode.origin());
1783 if (!distNode)
continue;
1785 NodeMaskType mask(distNode->getValueMask());
1786 NodeMaskType& narrowbandMask = maskNode.getValueMask();
1788 for (
Index pos = narrowbandMask.findFirstOn(); pos < NodeMaskType::SIZE; ++pos) {
1789 if (narrowbandMask.isOn(pos)) indexList.push_back(pos);
1792 mask -= narrowbandMask;
1793 narrowbandMask.setOff();
1795 const ValueType* data = distNode->buffer().data();
1798 while (!indexList.empty()) {
1800 const Index pos = indexList.back();
1801 indexList.pop_back();
1803 if (narrowbandMask.isOn(pos))
continue;
1804 narrowbandMask.setOn(pos);
1806 const ValueType dist = std::abs(data[pos]);
1808 ijk = LeafNodeType::offsetToLocalCoord(pos);
1810 Index npos = pos - 1;
1811 if (ijk[2] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1813 indexList.push_back(npos);
1817 if ((ijk[2] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1818 && std::abs(data[npos]) > dist)
1821 indexList.push_back(npos);
1824 npos = pos - LeafNodeType::DIM;
1825 if (ijk[1] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1827 indexList.push_back(npos);
1830 npos = pos + LeafNodeType::DIM;
1831 if ((ijk[1] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1832 && std::abs(data[npos]) > dist)
1835 indexList.push_back(npos);
1838 npos = pos - LeafNodeType::DIM * LeafNodeType::DIM;
1839 if (ijk[0] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1841 indexList.push_back(npos);
1844 npos = pos + LeafNodeType::DIM * LeafNodeType::DIM;
1845 if ((ijk[0] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1846 && std::abs(data[npos]) > dist)
1849 indexList.push_back(npos);
1855 TreeType
const *
const mTree;
1856 BoolLeafNodeType **
const mMaskNodes;
1860 template<
typename TreeType>
1861 struct ExpandNarrowbandMask
1863 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1864 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1865 using BoolTreeTypePtr =
typename BoolTreeType::Ptr;
1867 ExpandNarrowbandMask(
const TreeType& tree, std::vector<BoolTreeTypePtr>& segments)
1868 : mTree(&tree), mSegments(!segments.empty() ? &segments.front() : nullptr)
1872 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1874 const TreeType& distTree = *mTree;
1875 std::vector<BoolLeafNodeType*> nodes;
1877 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1879 BoolTreeType& narrowBandMask = *mSegments[n];
1881 BoolTreeType candidateMask(narrowBandMask,
false, TopologyCopy());
1886 candidateMask.getNodes(nodes);
1887 if (nodes.empty())
break;
1889 const tbb::blocked_range<size_t> nodeRange(0, nodes.size());
1891 tbb::parallel_for(nodeRange, FillLeafNodeVoxels<TreeType>(distTree, nodes));
1893 narrowBandMask.topologyUnion(candidateMask);
1895 ExpandLeafNodeRegion<TreeType> op(distTree, narrowBandMask, nodes);
1896 tbb::parallel_reduce(nodeRange, op);
1898 if (op.newMaskTree().empty())
break;
1900 candidateMask.clear();
1901 candidateMask.merge(op.newMaskTree());
1906 TreeType
const *
const mTree;
1907 BoolTreeTypePtr *
const mSegments;
1911 template<
typename TreeType>
1912 struct FloodFillSign
1914 using TreeTypePtr =
typename TreeType::Ptr;
1915 using ValueType =
typename TreeType::ValueType;
1916 using LeafNodeType =
typename TreeType::LeafNodeType;
1917 using RootNodeType =
typename TreeType::RootNodeType;
1918 using NodeChainType =
typename RootNodeType::NodeChainType;
1919 using InternalNodeType =
typename NodeChainType::template Get<1>;
1921 FloodFillSign(
const TreeType& tree, std::vector<TreeTypePtr>& segments)
1923 , mSegments(!segments.empty() ? &segments.front() : nullptr)
1924 , mMinValue(ValueType(0.0))
1929 std::vector<const InternalNodeType*> nodes;
1930 tree.getNodes(nodes);
1932 if (!nodes.empty()) {
1933 FindMinTileValue<InternalNodeType> minOp(nodes.data());
1934 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1935 minSDFValue =
std::min(minSDFValue, minOp.minValue);
1939 if (minSDFValue > ValueType(0.0)) {
1940 std::vector<const LeafNodeType*> nodes;
1941 tree.getNodes(nodes);
1942 if (!nodes.empty()) {
1943 FindMinVoxelValue<LeafNodeType> minOp(nodes.data());
1944 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1945 minSDFValue =
std::min(minSDFValue, minOp.minValue);
1949 mMinValue = minSDFValue;
1952 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1953 const ValueType interiorValue = -std::abs(mMinValue);
1954 const ValueType exteriorValue = std::abs(mTree->background());
1955 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1962 TreeType
const *
const mTree;
1963 TreeTypePtr *
const mSegments;
1964 ValueType mMinValue;
1968 template<
typename TreeType>
1971 using TreeTypePtr =
typename TreeType::Ptr;
1972 using ValueType =
typename TreeType::ValueType;
1973 using LeafNodeType =
typename TreeType::LeafNodeType;
1975 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
1976 using BoolTreeTypePtr =
typename BoolTreeType::Ptr;
1977 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
1979 MaskedCopy(
const TreeType& tree, std::vector<TreeTypePtr>& segments,
1980 std::vector<BoolTreeTypePtr>& masks)
1982 , mSegments(!segments.empty() ? &segments.front() : nullptr)
1983 , mMasks(!masks.empty() ? &masks.front() : nullptr)
1987 void operator()(
const tbb::blocked_range<size_t>& range)
const {
1989 std::vector<const BoolLeafNodeType*> nodes;
1991 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1993 const BoolTreeType& mask = *mMasks[n];
1996 mask.getNodes(nodes);
1998 Copy op(*mTree, nodes);
1999 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
2000 mSegments[n] = op.outputTree();
2007 Copy(
const TreeType& inputTree, std::vector<const BoolLeafNodeType*>& maskNodes)
2008 : mInputTree(&inputTree)
2009 , mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : nullptr)
2010 , mOutputTreePtr(new TreeType(inputTree.background()))
2014 Copy(
const Copy& rhs, tbb::split)
2015 : mInputTree(rhs.mInputTree)
2016 , mMaskNodes(rhs.mMaskNodes)
2017 , mOutputTreePtr(new TreeType(mInputTree->background()))
2021 TreeTypePtr& outputTree() {
return mOutputTreePtr; }
2023 void join(Copy& rhs) { mOutputTreePtr->merge(*rhs.mOutputTreePtr); }
2025 void operator()(
const tbb::blocked_range<size_t>& range) {
2027 tree::ValueAccessor<const TreeType> inputAcc(*mInputTree);
2028 tree::ValueAccessor<TreeType> outputAcc(*mOutputTreePtr);
2030 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
2032 const BoolLeafNodeType& maskNode = *mMaskNodes[n];
2033 if (maskNode.isEmpty())
continue;
2035 const Coord& ijk = maskNode.origin();
2037 const LeafNodeType* inputNode = inputAcc.probeConstLeaf(ijk);
2040 LeafNodeType* outputNode = outputAcc.touchLeaf(ijk);
2042 for (
typename BoolLeafNodeType::ValueOnCIter it = maskNode.cbeginValueOn();
2045 const Index idx = it.pos();
2046 outputNode->setValueOn(idx, inputNode->getValue(idx));
2049 const int valueDepth = inputAcc.getValueDepth(ijk);
2050 if (valueDepth >= 0) {
2051 outputAcc.addTile(TreeType::RootNodeType::LEVEL - valueDepth,
2052 ijk, inputAcc.getValue(ijk),
true);
2059 TreeType
const *
const mInputTree;
2060 BoolLeafNodeType
const *
const *
const mMaskNodes;
2061 TreeTypePtr mOutputTreePtr;
2064 TreeType
const *
const mTree;
2065 TreeTypePtr *
const mSegments;
2066 BoolTreeTypePtr *
const mMasks;
2073 template<
typename VolumePtrType>
2074 struct ComputeActiveVoxelCount
2076 ComputeActiveVoxelCount(std::vector<VolumePtrType>& segments,
size_t *countArray)
2077 : mSegments(!segments.empty() ? &segments.front() : nullptr)
2078 , mCountArray(countArray)
2082 void operator()(
const tbb::blocked_range<size_t>& range)
const {
2083 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
2084 mCountArray[n] = mSegments[n]->activeVoxelCount();
2088 VolumePtrType *
const mSegments;
2089 size_t *
const mCountArray;
2095 GreaterCount(
const size_t *countArray) : mCountArray(countArray) {}
2097 inline bool operator() (
const size_t& lhs,
const size_t& rhs)
const
2099 return (mCountArray[lhs] > mCountArray[rhs]);
2102 size_t const *
const mCountArray;
2108 template<
typename TreeType>
2109 struct GridOrTreeConstructor
2111 using TreeTypePtr =
typename TreeType::Ptr;
2112 using BoolTreePtrType =
typename TreeType::template ValueConverter<bool>::Type::Ptr;
2114 static BoolTreePtrType constructMask(
const TreeType&, BoolTreePtrType& maskTree)
2115 {
return maskTree; }
2116 static TreeTypePtr construct(
const TreeType&, TreeTypePtr& tree) {
return tree; }
2120 template<
typename TreeType>
2121 struct GridOrTreeConstructor<
Grid<TreeType> >
2123 using GridType = Grid<TreeType>;
2125 using TreeTypePtr =
typename TreeType::Ptr;
2127 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2128 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2129 using BoolGridType = Grid<BoolTreeType>;
2130 using BoolGridPtrType =
typename BoolGridType::Ptr;
2132 static BoolGridPtrType constructMask(
const GridType& grid, BoolTreePtrType& maskTree) {
2133 BoolGridPtrType maskGrid(BoolGridType::create(maskTree));
2134 maskGrid->setTransform(grid.transform().copy());
2138 static GridTypePtr construct(
const GridType& grid, TreeTypePtr& maskTree) {
2139 GridTypePtr maskGrid(GridType::create(maskTree));
2140 maskGrid->setTransform(grid.transform().copy());
2141 maskGrid->insertMeta(grid);
2155 template <
class Gr
idType>
2159 using ValueType =
typename GridType::ValueType;
2160 using TreeType =
typename GridType::TreeType;
2161 using LeafNodeType =
typename TreeType::LeafNodeType;
2162 using RootNodeType =
typename TreeType::RootNodeType;
2163 using NodeChainType =
typename RootNodeType::NodeChainType;
2164 using InternalNodeType =
typename NodeChainType::template Get<1>;
2168 TreeType& tree = grid.tree();
2170 size_t numLeafNodes = 0, numInternalNodes = 0;
2172 std::vector<LeafNodeType*> nodes;
2173 std::vector<size_t> leafnodeCount;
2177 std::vector<InternalNodeType*> internalNodes;
2178 tree.getNodes(internalNodes);
2180 numInternalNodes = internalNodes.size();
2182 leafnodeCount.push_back(0);
2183 for (
size_t n = 0; n < numInternalNodes; ++n) {
2184 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
2187 numLeafNodes = leafnodeCount.back();
2190 nodes.reserve(numLeafNodes);
2192 for (
size_t n = 0; n < numInternalNodes; ++n) {
2193 internalNodes[n]->stealNodes(nodes, tree.background(),
false);
2200 level_set_util_internal::FindMinTileValue<InternalNodeType> minOp(internalNodes.data());
2201 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), minOp);
2202 minSDFValue =
std::min(minSDFValue, minOp.minValue);
2205 if (minSDFValue > ValueType(0.0)) {
2206 level_set_util_internal::FindMinVoxelValue<LeafNodeType> minOp(nodes.data());
2207 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
2208 minSDFValue =
std::min(minSDFValue, minOp.minValue);
2211 cutoffDistance = -std::abs(cutoffDistance);
2212 cutoffDistance = minSDFValue > cutoffDistance ? minSDFValue : cutoffDistance;
2218 tbb::parallel_for(tbb::blocked_range<size_t>(0, nodes.size()),
2219 level_set_util_internal::SDFVoxelsToFogVolume<LeafNodeType>(nodes.data(), cutoffDistance));
2222 typename TreeType::Ptr newTree(
new TreeType(ValueType(0.0)));
2224 level_set_util_internal::PopulateTree<TreeType> populate(
2225 *newTree, nodes.data(), leafnodeCount.data(), 0);
2226 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
2229 std::vector<InternalNodeType*> internalNodes;
2230 newTree->getNodes(internalNodes);
2232 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalNodes.size()),
2233 level_set_util_internal::SDFTilesToFogVolume<TreeType, InternalNodeType>(
2234 tree, internalNodes.data()));
2239 typename TreeType::ValueAllIter it(*newTree);
2240 it.setMaxDepth(TreeType::ValueAllIter::LEAF_DEPTH - 2);
2243 if (acc.
getValue(it.getCoord()) < ValueType(0.0)) {
2244 it.setValue(ValueType(1.0));
2245 it.setActiveState(
true);
2253 typename TreeType::ValueAllIter it(tree);
2254 it.setMaxDepth(TreeType::ValueAllIter::ROOT_DEPTH);
2256 if (it.getValue() < ValueType(0.0)) {
2257 newTree->addTile(TreeType::ValueAllIter::ROOT_LEVEL, it.getCoord(),
2258 ValueType(1.0),
true);
2263 grid.setTree(newTree);
2271 template <
class Gr
idOrTreeType>
2272 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2273 sdfInteriorMask(
const GridOrTreeType& volume,
typename GridOrTreeType::ValueType isovalue)
2278 using BoolTreePtrType =
typename TreeType::template ValueConverter<bool>::Type::Ptr;
2279 BoolTreePtrType mask = level_set_util_internal::computeInteriorMask(tree, isovalue);
2281 return level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::constructMask(
2286 template<
typename Gr
idOrTreeType>
2287 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2289 typename GridOrTreeType::ValueType isovalue,
2296 using CharTreePtrType =
typename TreeType::template ValueConverter<char>::Type::Ptr;
2297 CharTreePtrType regionMask = level_set_util_internal::computeEnclosedRegionMask(
2298 tree, isovalue, fillMask);
2300 using BoolTreePtrType =
typename TreeType::template ValueConverter<bool>::Type::Ptr;
2301 BoolTreePtrType mask = level_set_util_internal::computeInteriorMask(*regionMask, 0);
2303 return level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::constructMask(
2311 template<
typename Gr
idOrTreeType>
2312 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2318 std::vector<const typename TreeType::LeafNodeType*> nodes;
2319 tree.getNodes(nodes);
2321 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2322 typename BoolTreeType::Ptr mask(
new BoolTreeType(
false));
2324 level_set_util_internal::MaskIsovalueCrossingVoxels<TreeType> op(tree, nodes, *mask, isovalue);
2325 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
2327 return level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::constructMask(
2335 template<
typename Gr
idOrTreeType>
2338 std::vector<
typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr>& masks)
2341 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2342 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2343 using BoolLeafNodeType =
typename BoolTreeType::LeafNodeType;
2345 using NodeMaskSegmentType = level_set_util_internal::NodeMaskSegment<BoolLeafNodeType>;
2346 using NodeMaskSegmentPtrType =
typename NodeMaskSegmentType::Ptr;
2347 using NodeMaskSegmentPtrVector =
typename std::vector<NodeMaskSegmentPtrType>;
2348 using NodeMaskSegmentRawPtrVector =
typename std::vector<NodeMaskSegmentType*>;
2354 BoolTreeType topologyMask(tree,
false,
TopologyCopy());
2359 if (topologyMask.hasActiveTiles()) {
2360 topologyMask.voxelizeActiveTiles();
2363 std::vector<BoolLeafNodeType*> leafnodes;
2364 topologyMask.getNodes(leafnodes);
2366 if (leafnodes.empty())
return;
2371 std::unique_ptr<NodeMaskSegmentPtrVector[]> nodeSegmentArray(
2372 new NodeMaskSegmentPtrVector[leafnodes.size()]);
2374 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
2375 level_set_util_internal::SegmentNodeMask<BoolLeafNodeType>(
2376 leafnodes, nodeSegmentArray.get()));
2381 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
2382 level_set_util_internal::ConnectNodeMaskSegments<BoolTreeType, BoolLeafNodeType>(
2383 topologyMask, nodeSegmentArray.get()));
2385 topologyMask.clear();
2387 size_t nodeSegmentCount = 0;
2388 for (
size_t n = 0, N = leafnodes.size(); n < N; ++n) {
2389 nodeSegmentCount += nodeSegmentArray[n].size();
2394 std::deque<NodeMaskSegmentRawPtrVector> nodeSegmentGroups;
2396 NodeMaskSegmentType* nextSegment = nodeSegmentArray[0][0].get();
2397 while (nextSegment) {
2399 nodeSegmentGroups.push_back(NodeMaskSegmentRawPtrVector());
2401 std::vector<NodeMaskSegmentType*>& segmentGroup = nodeSegmentGroups.back();
2402 segmentGroup.reserve(nodeSegmentCount);
2404 std::deque<NodeMaskSegmentType*> segmentQueue;
2405 segmentQueue.push_back(nextSegment);
2406 nextSegment =
nullptr;
2408 while (!segmentQueue.empty()) {
2410 NodeMaskSegmentType* segment = segmentQueue.back();
2411 segmentQueue.pop_back();
2413 if (segment->visited)
continue;
2414 segment->visited =
true;
2416 segmentGroup.push_back(segment);
2419 std::vector<NodeMaskSegmentType*>& connections = segment->connections;
2420 for (
size_t n = 0, N = connections.size(); n < N; ++n) {
2421 if (!connections[n]->visited) segmentQueue.push_back(connections[n]);
2426 for (
size_t n = 0, N = leafnodes.size(); n < N; ++n) {
2427 NodeMaskSegmentPtrVector& nodeSegments = nodeSegmentArray[n];
2428 for (
size_t i = 0, I = nodeSegments.size(); i < I; ++i) {
2429 if (!nodeSegments[i]->visited) nextSegment = nodeSegments[i].get();
2436 if (nodeSegmentGroups.size() == 1) {
2438 BoolTreePtrType mask(
new BoolTreeType(tree,
false,
TopologyCopy()));
2442 if (mask->hasActiveTiles()) {
2443 mask->voxelizeActiveTiles();
2447 level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::constructMask(
2450 }
else if (nodeSegmentGroups.size() > 1) {
2452 for (
size_t n = 0, N = nodeSegmentGroups.size(); n < N; ++n) {
2454 NodeMaskSegmentRawPtrVector& segmentGroup = nodeSegmentGroups[n];
2456 level_set_util_internal::MaskSegmentGroup<BoolTreeType> op(segmentGroup);
2457 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, segmentGroup.size()), op);
2460 level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::constructMask(
2461 volume, op.mask()));
2467 if (masks.size() > 1) {
2468 const size_t segmentCount = masks.size();
2470 std::unique_ptr<size_t[]> segmentOrderArray(
new size_t[segmentCount]);
2471 std::unique_ptr<size_t[]> voxelCountArray(
new size_t[segmentCount]);
2473 for (
size_t n = 0; n < segmentCount; ++n) {
2474 segmentOrderArray[n] = n;
2477 tbb::parallel_for(tbb::blocked_range<size_t>(0, segmentCount),
2478 level_set_util_internal::ComputeActiveVoxelCount<BoolTreePtrType>(
2479 masks, voxelCountArray.get()));
2481 size_t *begin = segmentOrderArray.get();
2482 tbb::parallel_sort(begin, begin + masks.size(), level_set_util_internal::GreaterCount(
2483 voxelCountArray.get()));
2485 std::vector<BoolTreePtrType> orderedMasks;
2486 orderedMasks.reserve(masks.size());
2488 for (
size_t n = 0; n < segmentCount; ++n) {
2489 orderedMasks.push_back(masks[segmentOrderArray[n]]);
2492 masks.swap(orderedMasks);
2498 template<
typename Gr
idOrTreeType>
2501 std::vector<typename GridOrTreeType::Ptr>& segments)
2504 using TreePtrType =
typename TreeType::Ptr;
2505 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2506 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2511 std::vector<BoolTreePtrType> maskSegmentArray;
2516 const size_t numSegments =
std::max(
size_t(1), maskSegmentArray.size());
2517 std::vector<TreePtrType> outputSegmentArray(numSegments);
2519 if (maskSegmentArray.empty()) {
2522 outputSegmentArray[0] = TreePtrType(
new TreeType(inputTree.background()));
2523 }
else if (numSegments == 1) {
2525 TreePtrType segment(
new TreeType(inputTree));
2528 if (segment->leafCount() != inputTree.leafCount()) {
2529 segment->topologyIntersection(*maskSegmentArray[0]);
2531 outputSegmentArray[0] = segment;
2533 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
2534 tbb::parallel_for(segmentRange,
2535 level_set_util_internal::MaskedCopy<TreeType>(inputTree, outputSegmentArray,
2539 for (
auto& segment : outputSegmentArray) {
2541 level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::construct(
2547 template<
typename Gr
idOrTreeType>
2549 segmentSDF(
const GridOrTreeType& volume, std::vector<typename GridOrTreeType::Ptr>& segments)
2552 using TreePtrType =
typename TreeType::Ptr;
2553 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
2554 using BoolTreePtrType =
typename BoolTreeType::Ptr;
2562 std::vector<BoolTreePtrType> maskSegmentArray;
2565 const size_t numSegments =
std::max(
size_t(1), maskSegmentArray.size());
2566 std::vector<TreePtrType> outputSegmentArray(numSegments);
2568 if (maskSegmentArray.empty()) {
2571 outputSegmentArray[0] = TreePtrType(
new TreeType(inputTree.background()));
2573 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
2576 tbb::parallel_for(segmentRange,
2577 level_set_util_internal::ExpandNarrowbandMask<TreeType>(inputTree, maskSegmentArray));
2581 tbb::parallel_for(segmentRange, level_set_util_internal::MaskedCopy<TreeType>(
2582 inputTree, outputSegmentArray, maskSegmentArray));
2584 tbb::parallel_for(segmentRange,
2585 level_set_util_internal::FloodFillSign<TreeType>(inputTree, outputSegmentArray));
2588 for (
auto& segment : outputSegmentArray) {
2590 level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::construct(
Convert polygonal meshes that consist of quads and/or triangles into signed or unsigned distance fiel...
Propagate the signs of distance values from the active voxels in the narrow band to the inactive valu...
SharedPtr< Grid > Ptr
Definition: Grid.h:579
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:564
Definition: ValueAccessor.h:183
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:219
Index32 Index
Definition: Types.h:54
@ GRID_FOG_VOLUME
Definition: Types.h:338
openvdb::GridBase Grid
Definition: Utils.h:33
Definition: Exceptions.h:13
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:1071
static TreeType & tree(TreeType &t)
Definition: Grid.h:1087
_TreeType TreeType
Definition: Grid.h:1072
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:180