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>
44template<
typename Gr
idType>
45inline typename GridType::ValueType lsutilGridMax()
47 return std::numeric_limits<typename GridType::ValueType>::max();
50template<
typename Gr
idType>
51inline typename GridType::ValueType lsutilGridZero()
53 return zeroVal<typename GridType::ValueType>();
76template<
class Gr
idType>
80 typename GridType::ValueType cutoffDistance = lsutilGridMax<GridType>());
93template<
class Gr
idOrTreeType>
94typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
96 const GridOrTreeType& volume,
97 typename GridOrTreeType::ValueType isovalue = lsutilGridZero<GridOrTreeType>());
120template<
typename Gr
idOrTreeType>
121typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
123 const GridOrTreeType& volume,
124 typename GridOrTreeType::ValueType isovalue = lsutilGridZero<GridOrTreeType>(),
125 const typename TreeAdapter<GridOrTreeType>::TreeType::template ValueConverter<bool>::Type*
134template<
typename Gr
idOrTreeType>
135typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
144template<
typename Gr
idOrTreeType>
147 std::vector<
typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr>& masks);
157template<
typename Gr
idOrTreeType>
160 std::vector<typename GridOrTreeType::Ptr>& segments);
171template<
typename Gr
idOrTreeType>
173segmentSDF(
const GridOrTreeType& volume, std::vector<typename GridOrTreeType::Ptr>& segments);
183namespace level_set_util_internal {
186template<
typename LeafNodeType>
187struct MaskInteriorVoxels {
189 using ValueType =
typename LeafNodeType::ValueType;
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());
213 const ValueType* values = &node.getValue(0);
214 for (Index i = 0; i < LeafNodeType::SIZE; ++i) {
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;
229 ValueType
const mIsovalue;
233template<
typename TreeType,
typename InternalNodeType>
234struct MaskInteriorTiles {
236 using ValueType =
typename TreeType::ValueType;
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;
256 ValueType
const mIsovalue;
260template<
typename TreeType>
263 using ValueType =
typename TreeType::ValueType;
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)
275 PopulateTree(PopulateTree& rhs, tbb::split)
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;
311template<
typename LeafNodeType>
312struct LabelBoundaryVoxels {
314 using ValueType =
typename LeafNodeType::ValueType;
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;
354 ValueType
const mIsovalue;
358template<
typename LeafNodeType>
359struct FlipRegionSign {
360 using ValueType =
typename LeafNodeType::ValueType;
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) {
366 ValueType* values =
const_cast<ValueType*
>(&mNodes[n]->getValue(0));
367 for (Index i = 0; i < LeafNodeType::SIZE; ++i) {
368 values[i] = values[i] < 0 ? 1 : -1;
373 LeafNodeType **
const mNodes;
377template<
typename LeafNodeType>
378struct FindMinVoxelValue {
380 using ValueType =
typename LeafNodeType::ValueType;
382 FindMinVoxelValue(LeafNodeType
const *
const *
const leafnodes)
383 : minValue(
std::numeric_limits<ValueType>::
max())
388 FindMinVoxelValue(FindMinVoxelValue& rhs, tbb::split)
389 : minValue(
std::numeric_limits<ValueType>::
max())
394 void operator()(
const tbb::blocked_range<size_t>& range) {
395 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
396 const ValueType* data = mNodes[n]->buffer().data();
397 for (Index i = 0; i < LeafNodeType::SIZE; ++i) {
398 minValue = std::min(minValue, data[i]);
403 void join(FindMinVoxelValue& rhs) { minValue = std::min(minValue, rhs.minValue); }
407 LeafNodeType
const *
const *
const mNodes;
411template<
typename InternalNodeType>
412struct FindMinTileValue {
414 using ValueType =
typename InternalNodeType::ValueType;
416 FindMinTileValue(InternalNodeType
const *
const *
const nodes)
417 : minValue(
std::numeric_limits<ValueType>::
max())
422 FindMinTileValue(FindMinTileValue& rhs, tbb::split)
423 : minValue(
std::numeric_limits<ValueType>::
max())
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();
432 minValue = std::min(minValue, *it);
437 void join(FindMinTileValue& rhs) { minValue = std::min(minValue, rhs.minValue); }
441 InternalNodeType
const *
const *
const mNodes;
445template<
typename LeafNodeType>
446struct SDFVoxelsToFogVolume {
448 using ValueType =
typename LeafNodeType::ValueType;
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();
463 for (Index i = 0; i < LeafNodeType::SIZE; ++i) {
464 values[i] = values[i] > ValueType(0.0) ? ValueType(0.0) : values[i] * mWeight;
465 if (values[i] > ValueType(0.0)) node.setValueOn(i);
468 if (node.onVoxelCount() == 0) {
475 LeafNodeType **
const mNodes;
476 ValueType
const mWeight;
480template<
typename TreeType,
typename InternalNodeType>
481struct SDFTilesToFogVolume {
483 SDFTilesToFogVolume(
const TreeType& tree, InternalNodeType ** nodes)
484 : mTree(&tree), mNodes(nodes) { }
486 void operator()(
const tbb::blocked_range<size_t>& range)
const {
488 using ValueType =
typename TreeType::ValueType;
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)) {
495 it.setValue(ValueType(1.0));
502 TreeType
const *
const mTree;
503 InternalNodeType **
const mNodes;
507template<
typename TreeType>
508struct FillMaskBoundary {
510 using ValueType =
typename TreeType::ValueType;
511 using LeafNodeType =
typename TreeType::LeafNodeType;
512 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
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);
530 std::unique_ptr<char[]> valueMask(
new char[BoolLeafNodeType::SIZE]);
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;
568 memset(valueMask.get(), 0,
sizeof(
char) * BoolLeafNodeType::SIZE);
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;
602 for (Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
603 numBoundaryValues += valueMask[i] == 1;
606 if (numBoundaryValues > 0) {
607 mNewNodes[n] =
new BoolLeafNodeType(origin,
false);
608 for (Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
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;
950template <
class TreeType>
951typename TreeType::template ValueConverter<char>::Type::Ptr
952computeEnclosedRegionMask(
const TreeType& tree,
typename TreeType::ValueType isovalue,
953 const typename TreeType::template ValueConverter<bool>::Type* fillMask)
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>;
960 using CharTreeType =
typename TreeType::template ValueConverter<char>::Type;
961 using CharLeafNodeType =
typename CharTreeType::LeafNodeType;
963 using BoolTreeType =
typename TreeType::template ValueConverter<bool>::Type;
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]);
998 tbb::parallel_for(tbb::blocked_range<size_t>(0, 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()]);
1019 tbb::parallel_for(tbb::blocked_range<size_t>(0, 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];
1051 tools::traceExteriorBoundaries(*maskTree);
1054 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1055 FlipRegionSign<CharLeafNodeType>(maskNodes.get()));
1057 if (!extraMaskNodes.empty()) {
1058 tbb::parallel_for(tbb::blocked_range<size_t>(0, extraMaskNodes.size()),
1059 FlipRegionSign<CharLeafNodeType>(extraMaskNodes.data()));
1063 tools::signedFloodFill(*maskTree);
1069template <
class TreeType>
1070typename TreeType::template ValueConverter<bool>::Type::Ptr
1071computeInteriorMask(
const TreeType& tree,
typename TreeType::ValueType iso)
1073 using ValueType =
typename TreeType::ValueType;
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>;
1093 static_cast<ValueType
>(tree.background() - math::Tolerance<ValueType>::value()));
1095 size_t numLeafNodes = 0, numInternalNodes = 0;
1097 std::vector<const LeafNodeType*> nodes;
1098 std::vector<size_t> leafnodeCount;
1102 std::vector<const InternalNodeType*> internalNodes;
1103 tree.getNodes(internalNodes);
1105 numInternalNodes = internalNodes.size();
1107 leafnodeCount.push_back(0);
1108 for (
size_t n = 0; n < numInternalNodes; ++n) {
1109 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
1112 numLeafNodes = leafnodeCount.back();
1115 nodes.reserve(numLeafNodes);
1117 for (
size_t n = 0; n < numInternalNodes; ++n) {
1118 internalNodes[n]->getNodes(nodes);
1123 std::unique_ptr<BoolLeafNodeType*[]> maskNodes(
new BoolLeafNodeType*[numLeafNodes]);
1125 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
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);
1140 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalMaskNodes.size()),
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);
1159template<
typename InputTreeType>
1160struct MaskIsovalueCrossingVoxels
1162 using InputValueType =
typename InputTreeType::ValueType;
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;
1278template<
typename NodeType>
1279struct 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;
1293template<
typename NodeType>
1295nodeMaskSegmentation(
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);
1369template<
typename NodeType>
1370struct 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;
1398template<
typename TreeType,
typename NodeType>
1399struct 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();
1449 for (Index pos = startPos; pos < NodeMaskType::SIZE; ++pos) {
1451 if (!node->isValueOn(pos))
continue;
1453 ijk = NodeType::offsetToLocalCoord(pos);
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;
1570template<
typename TreeType>
1571struct 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;
1613template<
typename TreeType>
1614struct ExpandLeafNodeRegion
1616 using ValueType =
typename TreeType::ValueType;
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;
1760template<
typename TreeType>
1761struct FillLeafNodeVoxels
1763 using ValueType =
typename TreeType::ValueType;
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();
1790 for (Index pos = narrowbandMask.findFirstOn(); pos < NodeMaskType::SIZE; ++pos) {
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);
1808 const ValueType dist = std::abs(data[pos]);
1810 ijk = LeafNodeType::offsetToLocalCoord(pos);
1812 Index npos = pos - 1;
1813 if (ijk[2] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1815 indexList.push_back(npos);
1819 if ((ijk[2] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1820 && std::abs(data[npos]) > dist)
1823 indexList.push_back(npos);
1826 npos = pos - LeafNodeType::DIM;
1827 if (ijk[1] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1829 indexList.push_back(npos);
1832 npos = pos + LeafNodeType::DIM;
1833 if ((ijk[1] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1834 && std::abs(data[npos]) > dist)
1837 indexList.push_back(npos);
1840 npos = pos - LeafNodeType::DIM * LeafNodeType::DIM;
1841 if (ijk[0] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1843 indexList.push_back(npos);
1846 npos = pos + LeafNodeType::DIM * LeafNodeType::DIM;
1847 if ((ijk[0] != (LeafNodeType::DIM - 1)) && mask.isOn(npos)
1848 && std::abs(data[npos]) > dist)
1851 indexList.push_back(npos);
1857 TreeType
const *
const mTree;
1858 BoolLeafNodeType **
const mMaskNodes;
1862template<
typename TreeType>
1863struct 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());
1893 tbb::parallel_for(nodeRange, FillLeafNodeVoxels<TreeType>(distTree, nodes));
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;
1913template<
typename TreeType>
1916 using TreeTypePtr =
typename TreeType::Ptr;
1917 using ValueType =
typename TreeType::ValueType;
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))
1928 ValueType minSDFValue = std::numeric_limits<ValueType>::max();
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);
1941 if (minSDFValue > ValueType(0.0)) {
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) {
1958 tools::signedFloodFillWithValues(*mSegments[n], exteriorValue, interiorValue);
1964 TreeType
const *
const mTree;
1965 TreeTypePtr *
const mSegments;
1966 ValueType mMinValue;
1970template<
typename TreeType>
1973 using TreeTypePtr =
typename TreeType::Ptr;
1974 using ValueType =
typename TreeType::ValueType;
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()))
2016 Copy(
const Copy& rhs, tbb::split)
2017 : mInputTree(rhs.mInputTree)
2018 , mMaskNodes(rhs.mMaskNodes)
2019 , mOutputTreePtr(new TreeType(mInputTree->background()))
2023 TreeTypePtr& outputTree() {
return mOutputTreePtr; }
2025 void join(Copy& rhs) { mOutputTreePtr->merge(*rhs.mOutputTreePtr); }
2027 void operator()(
const tbb::blocked_range<size_t>& range) {
2029 tree::ValueAccessor<const TreeType> inputAcc(*mInputTree);
2030 tree::ValueAccessor<TreeType> outputAcc(*mOutputTreePtr);
2032 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
2034 const BoolLeafNodeType& maskNode = *mMaskNodes[n];
2035 if (maskNode.isEmpty())
continue;
2037 const Coord& ijk = maskNode.origin();
2039 const LeafNodeType* inputNode = inputAcc.probeConstLeaf(ijk);
2042 LeafNodeType* outputNode = outputAcc.touchLeaf(ijk);
2044 for (
typename BoolLeafNodeType::ValueOnCIter it = maskNode.cbeginValueOn();
2047 const Index idx = it.pos();
2048 outputNode->setValueOn(idx, inputNode->getValue(idx));
2051 const int valueDepth = inputAcc.getValueDepth(ijk);
2052 if (valueDepth >= 0) {
2053 outputAcc.addTile(TreeType::RootNodeType::LEVEL - valueDepth,
2054 ijk, inputAcc.getValue(ijk),
true);
2061 TreeType
const *
const mInputTree;
2062 BoolLeafNodeType
const *
const *
const mMaskNodes;
2063 TreeTypePtr mOutputTreePtr;
2066 TreeType
const *
const mTree;
2067 TreeTypePtr *
const mSegments;
2068 BoolTreeTypePtr *
const mMasks;
2075template<
typename VolumePtrType>
2076struct 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;
2110template<
typename TreeType>
2111struct 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; }
2122template<
typename TreeType>
2123struct 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);
2157template <
class Gr
idType>
2161 using ValueType =
typename GridType::ValueType;
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);
2199 ValueType minSDFValue = std::numeric_limits<ValueType>::max();
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);
2207 if (minSDFValue > ValueType(0.0)) {
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;
2220 tbb::parallel_for(tbb::blocked_range<size_t>(0, nodes.size()),
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);
2234 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalNodes.size()),
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);
2245 if (acc.
getValue(it.getCoord()) < ValueType(0.0)) {
2246 it.setValue(ValueType(1.0));
2247 it.setActiveState(
true);
2255 typename TreeType::ValueAllIter it(tree);
2256 it.setMaxDepth(TreeType::ValueAllIter::ROOT_DEPTH);
2258 if (it.getValue() < ValueType(0.0)) {
2259 newTree->addTile(TreeType::ValueAllIter::ROOT_LEVEL, it.getCoord(),
2260 ValueType(1.0),
true);
2265 grid.setTree(newTree);
2273template <
class Gr
idOrTreeType>
2274typename 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(
2288template<
typename Gr
idOrTreeType>
2289typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2291 typename GridOrTreeType::ValueType isovalue,
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(
2313template<
typename Gr
idOrTreeType>
2314typename 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(
2337template<
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());
2360 tools::pruneInactive(topologyMask);
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()]);
2377 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
2378 level_set_util_internal::SegmentNodeMask<BoolLeafNodeType>(
2379 leafnodes, nodeSegmentArray.get()));
2384 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
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) {
2441 BoolTreePtrType mask(
new BoolTreeType(tree,
false,
TopologyCopy()));
2443 tools::pruneInactive(*mask);
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;
2480 tbb::parallel_for(tbb::blocked_range<size_t>(0, segmentCount),
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);
2501template<
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);
2537 tbb::parallel_for(segmentRange,
2538 level_set_util_internal::MaskedCopy<TreeType>(inputTree, outputSegmentArray,
2542 for (
auto& segment : outputSegmentArray) {
2544 level_set_util_internal::GridOrTreeConstructor<GridOrTreeType>::construct(
2550template<
typename Gr
idOrTreeType>
2552segmentSDF(
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);
2579 tbb::parallel_for(segmentRange,
2580 level_set_util_internal::ExpandNarrowbandMask<TreeType>(inputTree, maskSegmentArray));
2584 tbb::parallel_for(segmentRange, level_set_util_internal::MaskedCopy<TreeType>(
2585 inputTree, outputSegmentArray, maskSegmentArray));
2587 tbb::parallel_for(segmentRange,
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>&)
Convert polygonal meshes that consist of quads and/or triangles into signed or unsigned distance fiel...
Attribute-owned data structure for points. Point attributes are stored in leaf nodes and ordered by v...
Propagate the signs of distance values from the active voxels in the narrow band to the inactive valu...
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition Types.h:644
Definition ValueAccessor.h:191
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition ValueAccessor.h:235
GridType
List of types that are currently supported by NanoVDB.
Definition NanoVDB.h:243
Index32 Index
Definition Types.h:54
@ GRID_FOG_VOLUME
Definition Types.h:417
openvdb::GridBase Grid
Definition Utils.h:34
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:1060
_TreeType TreeType
Definition Grid.h:1061
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition version.h.in:121
#define OPENVDB_USE_VERSION_NAMESPACE
Definition version.h.in:212
#define OPENVDB_REAL_TREE_INSTANTIATE(Function)
Definition version.h.in:157
#define OPENVDB_ALL_TREE_INSTANTIATE(Function)
Definition version.h.in:161