39 #ifndef OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED 40 #define OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED 45 #include <openvdb/Types.h> 46 #include <openvdb/Grid.h> 48 #include <tbb/blocked_range.h> 49 #include <tbb/parallel_for.h> 50 #include <tbb/parallel_reduce.h> 51 #include <tbb/parallel_sort.h> 64 template<
typename Gr
idType>
65 inline typename GridType::ValueType lsutilGridMax()
70 template<
typename Gr
idType>
71 inline typename GridType::ValueType lsutilGridZero()
73 return zeroVal<typename GridType::ValueType>();
96 template<
class Gr
idType>
100 typename GridType::ValueType cutoffDistance = lsutilGridMax<GridType>());
113 template<
class Gr
idOrTreeType>
114 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
116 const GridOrTreeType& volume,
117 typename GridOrTreeType::ValueType isovalue = lsutilGridZero<GridOrTreeType>());
140 template<
typename Gr
idOrTreeType>
141 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
143 typename GridOrTreeType::ValueType isovalue = lsutilGridZero<GridOrTreeType>(),
144 const typename TreeAdapter<GridOrTreeType>::TreeType::template ValueConverter<bool>::Type* fillMask = NULL);
151 template<
typename Gr
idOrTreeType>
152 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
161 template<
typename Gr
idOrTreeType>
164 std::vector<
typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr>& masks);
174 template<
typename Gr
idOrTreeType>
176 segmentActiveVoxels(
const GridOrTreeType& volume, std::vector<typename GridOrTreeType::Ptr>& segments);
187 template<
typename Gr
idOrTreeType>
189 segmentSDF(
const GridOrTreeType& volume, std::vector<typename GridOrTreeType::Ptr>& segments);
198 namespace level_set_util_internal {
201 template<
typename LeafNodeType>
208 ValueType isovalue,
const LeafNodeType ** nodes, BoolLeafNodeType ** maskNodes)
209 : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
213 void operator()(
const tbb::blocked_range<size_t>& range)
const {
215 BoolLeafNodeType * maskNodePt = NULL;
217 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
219 mMaskNodes[n] = NULL;
220 const LeafNodeType& node = *mNodes[n];
223 maskNodePt =
new BoolLeafNodeType(node.origin(),
false);
228 const ValueType* values = &node.getValue(0);
229 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
230 if (values[i] < mIsovalue) maskNodePt->
setValueOn(i,
true);
234 mMaskNodes[n] = maskNodePt;
239 if (maskNodePt)
delete maskNodePt;
242 LeafNodeType
const *
const *
const mNodes;
248 template<
typename TreeType,
typename InternalNodeType>
254 : mTree(&tree), mMaskNodes(maskNodes), mIsovalue(isovalue) { }
256 void operator()(
const tbb::blocked_range<size_t>& range)
const {
258 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
259 typename InternalNodeType::ValueAllIter it = mMaskNodes[n]->beginValueAll();
261 if (acc.
getValue(it.getCoord()) < mIsovalue) {
275 template<
typename TreeType>
282 const size_t * nodexIndexMap, ValueType background)
283 : mNewTree(background)
286 , mNodeIndexMap(nodexIndexMap)
291 : mNewTree(rhs.mNewTree.background())
294 , mNodeIndexMap(rhs.mNodeIndexMap)
303 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
304 for (
size_t i = mNodeIndexMap[n], I = mNodeIndexMap[n + 1]; i < I; ++i) {
305 if (mNodes[i] != NULL) acc.
addLeaf(mNodes[i]);
309 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
319 TreeType *
const mTreePt;
320 LeafNodeType **
const mNodes;
321 size_t const *
const mNodeIndexMap;
326 template<
typename LeafNodeType>
333 ValueType isovalue,
const LeafNodeType ** nodes, CharLeafNodeType ** maskNodes)
334 : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
338 void operator()(
const tbb::blocked_range<size_t>& range)
const {
340 CharLeafNodeType * maskNodePt = NULL;
342 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
344 mMaskNodes[n] = NULL;
345 const LeafNodeType& node = *mNodes[n];
348 maskNodePt =
new CharLeafNodeType(node.origin(), 1);
353 typename LeafNodeType::ValueOnCIter it;
354 for (it = node.cbeginValueOn(); it; ++it) {
355 maskNodePt->
setValueOn(it.pos(), ((*it - mIsovalue) < 0.0) ? 0 : 1);
359 mMaskNodes[n] = maskNodePt;
364 if (maskNodePt)
delete maskNodePt;
367 LeafNodeType
const *
const *
const mNodes;
373 template<
typename LeafNodeType>
379 void operator()(
const tbb::blocked_range<size_t>& range)
const {
380 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
381 ValueType* values =
const_cast<ValueType*
>(&mNodes[n]->getValue(0));
382 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
383 values[i] = values[i] < 0 ? 1 : -1;
392 template<
typename LeafNodeType>
398 : minValue(std::numeric_limits<ValueType>::
max())
404 : minValue(std::numeric_limits<ValueType>::
max())
410 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
411 const ValueType* data = mNodes[n]->buffer().data();
412 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
413 minValue =
std::min(minValue, data[i]);
422 LeafNodeType
const *
const *
const mNodes;
426 template<
typename InternalNodeType>
432 : minValue(std::numeric_limits<ValueType>::
max())
438 : minValue(std::numeric_limits<ValueType>::
max())
444 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
445 typename InternalNodeType::ValueAllCIter it = mNodes[n]->beginValueAll();
456 InternalNodeType
const *
const *
const mNodes;
460 template<
typename LeafNodeType>
466 : mNodes(nodes), mWeight(ValueType(1.0) / cutoffDistance)
470 void operator()(
const tbb::blocked_range<size_t>& range)
const {
472 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
474 LeafNodeType& node = *mNodes[n];
477 ValueType* values = node.buffer().data();
478 for (
Index i = 0; i < LeafNodeType::SIZE; ++i) {
479 values[i] = values[i] > ValueType(0.0) ? ValueType(0.0) : values[i] * mWeight;
480 if (values[i] > ValueType(0.0)) node.setValueOn(i);
483 if (node.onVoxelCount() == 0) {
495 template<
typename TreeType,
typename InternalNodeType>
499 : mTree(&tree), mNodes(nodes) { }
501 void operator()(
const tbb::blocked_range<size_t>& range)
const {
503 typedef typename TreeType::ValueType ValueType;
506 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
507 typename InternalNodeType::ValueAllIter it = mNodes[n]->beginValueAll();
509 if (acc.
getValue(it.getCoord()) < ValueType(0.0)) {
510 it.setValue(ValueType(1.0));
522 template<
typename TreeType>
527 typedef typename TreeType::template ValueConverter<bool>::Type
BoolTreeType;
531 const BoolLeafNodeType ** fillNodes, BoolLeafNodeType ** newNodes)
532 : mTree(&tree), mFillMask(&fillMask), mFillNodes(fillNodes), mNewNodes(newNodes), mIsovalue(isovalue)
536 void operator()(
const tbb::blocked_range<size_t>& range)
const {
541 boost::scoped_array<char> valueMask(
new char[BoolLeafNodeType::SIZE]);
543 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
546 const BoolLeafNodeType& node = *mFillNodes[n];
547 const Coord& origin = node.origin();
549 const bool denseNode = node.isDense();
554 int denseNeighbors = 0;
557 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
560 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
563 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
566 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
569 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
572 if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
574 if (denseNeighbors == 6)
continue;
578 memset(valueMask.get(), 0,
sizeof(char) * BoolLeafNodeType::SIZE);
580 const typename TreeType::LeafNodeType* distNode = distAcc.
probeConstLeaf(origin);
584 bool earlyTermination =
false;
588 evalInternalNeighborsP(valueMask.get(), node, *distNode);
589 evalInternalNeighborsN(valueMask.get(), node, *distNode);
590 }
else if (distAcc.
getValue(origin) > mIsovalue) {
591 earlyTermination = evalInternalNeighborsP(valueMask.get(), node);
592 if (!earlyTermination) earlyTermination = evalInternalNeighborsN(valueMask.get(), node);
598 if (!earlyTermination) {
599 evalExternalNeighborsX<true>(valueMask.get(), node, maskAcc, distAcc);
600 evalExternalNeighborsX<false>(valueMask.get(), node, maskAcc, distAcc);
601 evalExternalNeighborsY<true>(valueMask.get(), node, maskAcc, distAcc);
602 evalExternalNeighborsY<false>(valueMask.get(), node, maskAcc, distAcc);
603 evalExternalNeighborsZ<true>(valueMask.get(), node, maskAcc, distAcc);
604 evalExternalNeighborsZ<false>(valueMask.get(), node, maskAcc, distAcc);
609 int numBoundaryValues = 0;
610 for (
Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
611 numBoundaryValues += valueMask[i] == 1;
614 if (numBoundaryValues > 0) {
615 mNewNodes[n] =
new BoolLeafNodeType(origin,
false);
616 for (
Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
617 if (valueMask[i] == 1) mNewNodes[n]->setValueOn(i);
627 void evalInternalNeighborsP(
char* valueMask,
const BoolLeafNodeType& node,
const LeafNodeType& distNode)
const {
629 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
630 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
631 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
632 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
633 for (
Index z = 0; z < BoolLeafNodeType::DIM - 1; ++z) {
634 const Index pos = yPos + z;
636 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
638 if (!node.isValueOn(pos + 1) && distNode.getValue(pos + 1) > mIsovalue) {
645 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
646 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
647 for (
Index y = 0; y < BoolLeafNodeType::DIM - 1; ++y) {
648 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
649 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
650 const Index pos = yPos + z;
652 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
654 if (!node.isValueOn(pos + BoolLeafNodeType::DIM) &&
655 distNode.getValue(pos + BoolLeafNodeType::DIM) > mIsovalue) {
662 for (
Index x = 0; x < BoolLeafNodeType::DIM - 1; ++x) {
663 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
664 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
665 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
666 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
667 const Index pos = yPos + z;
669 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
671 if (!node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
672 distNode.getValue(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) > mIsovalue) {
680 bool evalInternalNeighborsP(
char* valueMask,
const BoolLeafNodeType& node)
const {
682 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
683 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
684 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
685 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
686 for (
Index z = 0; z < BoolLeafNodeType::DIM - 1; ++z) {
687 const Index pos = yPos + z;
689 if (node.isValueOn(pos) && !node.isValueOn(pos + 1)) {
697 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
698 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
699 for (
Index y = 0; y < BoolLeafNodeType::DIM - 1; ++y) {
700 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
701 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
702 const Index pos = yPos + z;
704 if (node.isValueOn(pos) && !node.isValueOn(pos + BoolLeafNodeType::DIM)) {
712 for (
Index x = 0; x < BoolLeafNodeType::DIM - 1; ++x) {
713 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
714 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
715 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
716 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
717 const Index pos = yPos + z;
719 if (node.isValueOn(pos) &&
720 !node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
733 void evalInternalNeighborsN(
char* valueMask,
const BoolLeafNodeType& node,
const LeafNodeType& distNode)
const {
735 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
736 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
737 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
738 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
739 for (
Index z = 1; z < BoolLeafNodeType::DIM; ++z) {
740 const Index pos = yPos + z;
742 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
744 if (!node.isValueOn(pos - 1) && distNode.getValue(pos - 1) > mIsovalue) {
751 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
752 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
753 for (
Index y = 1; y < BoolLeafNodeType::DIM; ++y) {
754 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
755 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
756 const Index pos = yPos + z;
758 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
760 if (!node.isValueOn(pos - BoolLeafNodeType::DIM) &&
761 distNode.getValue(pos - BoolLeafNodeType::DIM) > mIsovalue) {
768 for (
Index x = 1; x < BoolLeafNodeType::DIM; ++x) {
769 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
770 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
771 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
772 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
773 const Index pos = yPos + z;
775 if (valueMask[pos] != 0 || !node.isValueOn(pos))
continue;
777 if (!node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
778 distNode.getValue(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) > mIsovalue) {
787 bool evalInternalNeighborsN(
char* valueMask,
const BoolLeafNodeType& node)
const {
789 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
790 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
791 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
792 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
793 for (
Index z = 1; z < BoolLeafNodeType::DIM; ++z) {
794 const Index pos = yPos + z;
796 if (node.isValueOn(pos) && !node.isValueOn(pos - 1)) {
804 for (
Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
805 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
806 for (
Index y = 1; y < BoolLeafNodeType::DIM; ++y) {
807 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
808 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
809 const Index pos = yPos + z;
811 if (node.isValueOn(pos) && !node.isValueOn(pos - BoolLeafNodeType::DIM)) {
819 for (
Index x = 1; x < BoolLeafNodeType::DIM; ++x) {
820 const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
821 for (
Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
822 const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
823 for (
Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
824 const Index pos = yPos + z;
826 if (node.isValueOn(pos) &&
827 !node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
842 template<
bool UpWind>
843 void evalExternalNeighborsX(
char* valueMask,
const BoolLeafNodeType& node,
847 const Coord& origin = node.origin();
848 Coord ijk(0, 0, 0), nijk;
853 ijk[0] = int(BoolLeafNodeType::DIM) - 1;
856 const Index xPos = ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM));
858 for (ijk[1] = 0; ijk[1] < int(BoolLeafNodeType::DIM); ++ijk[1]) {
859 const Index yPos = xPos + (ijk[1] << int(BoolLeafNodeType::LOG2DIM));
861 for (ijk[2] = 0; ijk[2] < int(BoolLeafNodeType::DIM); ++ijk[2]) {
862 const Index pos = yPos + ijk[2];
864 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
866 nijk = origin + ijk.
offsetBy(step, 0, 0);
877 template<
bool UpWind>
878 void evalExternalNeighborsY(
char* valueMask,
const BoolLeafNodeType& node,
882 const Coord& origin = node.origin();
883 Coord ijk(0, 0, 0), nijk;
888 ijk[1] = int(BoolLeafNodeType::DIM) - 1;
891 const Index yPos = ijk[1] << int(BoolLeafNodeType::LOG2DIM);
893 for (ijk[0] = 0; ijk[0] < int(BoolLeafNodeType::DIM); ++ijk[0]) {
894 const Index xPos = yPos + (ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM)));
896 for (ijk[2] = 0; ijk[2] < int(BoolLeafNodeType::DIM); ++ijk[2]) {
897 const Index pos = xPos + ijk[2];
899 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
901 nijk = origin + ijk.
offsetBy(0, step, 0);
911 template<
bool UpWind>
912 void evalExternalNeighborsZ(
char* valueMask,
const BoolLeafNodeType& node,
916 const Coord& origin = node.origin();
917 Coord ijk(0, 0, 0), nijk;
922 ijk[2] = int(BoolLeafNodeType::DIM) - 1;
925 for (ijk[0] = 0; ijk[0] < int(BoolLeafNodeType::DIM); ++ijk[0]) {
926 const Index xPos = ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM));
928 for (ijk[1] = 0; ijk[1] < int(BoolLeafNodeType::DIM); ++ijk[1]) {
929 const Index pos = ijk[2] + xPos + (ijk[1] << int(BoolLeafNodeType::LOG2DIM));
931 if (valueMask[pos] == 0 && node.isValueOn(pos)) {
933 nijk = origin + ijk.
offsetBy(0, 0, step);
944 TreeType
const *
const mTree;
945 BoolTreeType
const *
const mFillMask;
946 BoolLeafNodeType
const *
const *
const mFillNodes;
947 BoolLeafNodeType **
const mNewNodes;
948 ValueType
const mIsovalue;
954 template <
class TreeType>
955 inline typename TreeType::template ValueConverter<char>::Type::Ptr
957 const typename TreeType::template ValueConverter<bool>::Type* fillMask)
959 typedef typename TreeType::LeafNodeType LeafNodeType;
960 typedef typename TreeType::RootNodeType RootNodeType;
961 typedef typename RootNodeType::NodeChainType NodeChainType;
962 typedef typename boost::mpl::at<NodeChainType, boost::mpl::int_<1> >::type InternalNodeType;
964 typedef typename TreeType::template ValueConverter<char>::Type CharTreeType;
965 typedef typename CharTreeType::LeafNodeType CharLeafNodeType;
966 typedef typename CharTreeType::RootNodeType CharRootNodeType;
967 typedef typename CharRootNodeType::NodeChainType CharNodeChainType;
969 typedef typename TreeType::template ValueConverter<bool>::Type BoolTreeType;
970 typedef typename BoolTreeType::LeafNodeType BoolLeafNodeType;
974 const TreeType* treePt = &tree;
976 size_t numLeafNodes = 0, numInternalNodes = 0;
978 std::vector<const LeafNodeType*> nodes;
979 std::vector<size_t> leafnodeCount;
983 std::vector<const InternalNodeType*> internalNodes;
984 treePt->getNodes(internalNodes);
986 numInternalNodes = internalNodes.size();
988 leafnodeCount.push_back(0);
989 for (
size_t n = 0; n < numInternalNodes; ++n) {
990 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
993 numLeafNodes = leafnodeCount.back();
996 nodes.reserve(numLeafNodes);
998 for (
size_t n = 0; n < numInternalNodes; ++n) {
999 internalNodes[n]->getNodes(nodes);
1004 boost::scoped_array<CharLeafNodeType*> maskNodes(
new CharLeafNodeType*[numLeafNodes]);
1006 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1010 typename CharTreeType::Ptr maskTree(
new CharTreeType(1));
1013 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1017 std::vector<CharLeafNodeType*> extraMaskNodes;
1021 std::vector<const BoolLeafNodeType*> fillMaskNodes;
1022 fillMask->getNodes(fillMaskNodes);
1024 boost::scoped_array<BoolLeafNodeType*> boundaryMaskNodes(
new BoolLeafNodeType*[fillMaskNodes.size()]);
1026 tbb::parallel_for(tbb::blocked_range<size_t>(0, fillMaskNodes.size()),
1031 for (
size_t n = 0, N = fillMaskNodes.size(); n < N; ++n) {
1033 if (boundaryMaskNodes[n] == NULL)
continue;
1035 const BoolLeafNodeType& boundaryNode = *boundaryMaskNodes[n];
1036 const Coord& origin = boundaryNode.origin();
1038 CharLeafNodeType* maskNodePt = maskAcc.
probeLeaf(origin);
1042 extraMaskNodes.push_back(maskNodePt);
1045 char* data = maskNodePt->buffer().data();
1047 typename BoolLeafNodeType::ValueOnCIter it = boundaryNode.cbeginValueOn();
1049 if (data[it.pos()] != 0) data[it.pos()] = -1;
1052 delete boundaryMaskNodes[n];
1060 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1063 if (!extraMaskNodes.empty()) {
1064 tbb::parallel_for(tbb::blocked_range<size_t>(0, extraMaskNodes.size()),
1075 template <
class TreeType>
1076 inline typename TreeType::template ValueConverter<bool>::Type::Ptr
1079 typedef typename TreeType::LeafNodeType LeafNodeType;
1080 typedef typename TreeType::RootNodeType RootNodeType;
1081 typedef typename RootNodeType::NodeChainType NodeChainType;
1082 typedef typename boost::mpl::at<NodeChainType, boost::mpl::int_<1> >::type InternalNodeType;
1084 typedef typename TreeType::template ValueConverter<bool>::Type BoolTreeType;
1085 typedef typename BoolTreeType::LeafNodeType BoolLeafNodeType;
1086 typedef typename BoolTreeType::RootNodeType BoolRootNodeType;
1087 typedef typename BoolRootNodeType::NodeChainType BoolNodeChainType;
1088 typedef typename boost::mpl::at<BoolNodeChainType, boost::mpl::int_<1> >::type BoolInternalNodeType;
1091 size_t numLeafNodes = 0, numInternalNodes = 0;
1093 std::vector<const LeafNodeType*> nodes;
1094 std::vector<size_t> leafnodeCount;
1098 std::vector<const InternalNodeType*> internalNodes;
1099 tree.getNodes(internalNodes);
1101 numInternalNodes = internalNodes.size();
1103 leafnodeCount.push_back(0);
1104 for (
size_t n = 0; n < numInternalNodes; ++n) {
1105 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
1108 numLeafNodes = leafnodeCount.back();
1111 nodes.reserve(numLeafNodes);
1113 for (
size_t n = 0; n < numInternalNodes; ++n) {
1114 internalNodes[n]->getNodes(nodes);
1119 boost::scoped_array<BoolLeafNodeType*> maskNodes(
new BoolLeafNodeType*[numLeafNodes]);
1121 tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1126 typename BoolTreeType::Ptr maskTree(
new BoolTreeType(
false));
1129 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1133 std::vector<BoolInternalNodeType*> internalMaskNodes;
1134 maskTree->getNodes(internalMaskNodes);
1136 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalMaskNodes.size()),
1141 typename BoolTreeType::ValueAllIter it(*maskTree);
1142 it.setMaxDepth(BoolTreeType::ValueAllIter::LEAF_DEPTH - 2);
1145 if (acc.getValue(it.getCoord()) < iso) {
1147 it.setActiveState(
true);
1155 template<
typename InputTreeType>
1160 typedef typename InputTreeType::template ValueConverter<bool>::Type
BoolTreeType;
1164 const InputTreeType& inputTree,
1165 const std::vector<const InputLeafNodeType*>& inputLeafNodes,
1166 BoolTreeType& maskTree,
1168 : mInputAccessor(inputTree)
1169 , mInputNodes(!inputLeafNodes.empty() ? &inputLeafNodes.front() : NULL)
1171 , mMaskAccessor(maskTree)
1177 : mInputAccessor(rhs.mInputAccessor.tree())
1178 , mInputNodes(rhs.mInputNodes)
1180 , mMaskAccessor(mMaskTree)
1181 , mIsovalue(rhs.mIsovalue)
1187 const InputValueType iso = mIsovalue;
1190 BoolLeafNodeType* maskNodePt = NULL;
1192 for (
size_t n = range.begin(); mInputNodes && (n != range.end()); ++n) {
1194 const InputLeafNodeType& node = *mInputNodes[n];
1196 if (!maskNodePt) maskNodePt =
new BoolLeafNodeType(node.origin(),
false);
1197 else maskNodePt->setOrigin(node.origin());
1199 bool collectedData =
false;
1201 for (
typename InputLeafNodeType::ValueOnCIter it = node.cbeginValueOn(); it; ++it) {
1203 bool isUnder = *it < iso;
1205 ijk = it.getCoord();
1208 bool signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1213 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1219 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1225 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1231 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1237 signChange = isUnder != (mInputAccessor.getValue(ijk) < iso);
1242 collectedData =
true;
1243 maskNodePt->setValueOn(it.pos(),
true);
1247 if (collectedData) {
1248 mMaskAccessor.addLeaf(maskNodePt);
1253 if (maskNodePt)
delete maskNodePt;
1257 mMaskAccessor.tree().merge(rhs.mMaskAccessor.
tree());
1262 InputLeafNodeType
const *
const *
const mInputNodes;
1264 BoolTreeType mMaskTree;
1267 InputValueType mIsovalue;
1274 template<
typename NodeType>
1277 typedef boost::shared_ptr<NodeMaskSegment>
Ptr;
1289 template<
typename NodeType>
1294 typedef typename NodeType::NodeMaskType NodeMaskType;
1296 typedef typename NodeMaskSegmentType::Ptr NodeMaskSegmentTypePtr;
1298 NodeMaskType nodeMask(node.getValueMask());
1299 std::deque<Index> indexList;
1301 while (!nodeMask.isOff()) {
1303 NodeMaskSegmentTypePtr segment(
new NodeMaskSegmentType());
1304 segment->origin = node.origin();
1306 NodeMaskType& mask = segment->mask;
1308 indexList.push_back(nodeMask.findFirstOn());
1309 nodeMask.setOff(indexList.back());
1312 while (!indexList.empty()) {
1314 const Index pos = indexList.back();
1315 indexList.pop_back();
1317 if (mask.isOn(pos))
continue;
1320 ijk = NodeType::offsetToLocalCoord(pos);
1322 Index npos = pos - 1;
1323 if (ijk[2] != 0 && nodeMask.isOn(npos)) {
1324 nodeMask.setOff(npos);
1325 indexList.push_back(npos);
1329 if (ijk[2] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1330 nodeMask.setOff(npos);
1331 indexList.push_back(npos);
1334 npos = pos - NodeType::DIM;
1335 if (ijk[1] != 0 && nodeMask.isOn(npos)) {
1336 nodeMask.setOff(npos);
1337 indexList.push_back(npos);
1340 npos = pos + NodeType::DIM;
1341 if (ijk[1] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1342 nodeMask.setOff(npos);
1343 indexList.push_back(npos);
1346 npos = pos - NodeType::DIM * NodeType::DIM;
1347 if (ijk[0] != 0 && nodeMask.isOn(npos)) {
1348 nodeMask.setOff(npos);
1349 indexList.push_back(npos);
1352 npos = pos + NodeType::DIM * NodeType::DIM;
1353 if (ijk[0] != (NodeType::DIM - 1) && nodeMask.isOn(npos)) {
1354 nodeMask.setOff(npos);
1355 indexList.push_back(npos);
1360 segments.push_back(segment);
1365 template<
typename NodeType>
1373 : mNodes(!nodes.empty() ? &nodes.front() : NULL)
1374 , mNodeMaskArray(nodeMaskArray)
1379 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1380 NodeType& node = *mNodes[n];
1384 Coord& origin =
const_cast<Coord&
>(node.origin());
1385 origin[0] =
static_cast<int>(n);
1394 template<
typename TreeType,
typename NodeType>
1404 , mNodeMaskArray(nodeMaskArray)
1412 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1414 NodeMaskSegmentVector& segments = mNodeMaskArray[n];
1415 if (segments.empty())
continue;
1417 std::vector<std::set<NodeMaskSegmentType*> > connections(segments.size());
1419 Coord ijk = segments[0]->origin;
1421 const NodeType* node = acc.template probeConstNode<NodeType>(ijk);
1422 if (!node)
continue;
1426 ijk[2] += NodeType::DIM;
1427 const NodeType* nodeZUp = acc.template probeConstNode<NodeType>(ijk);
1428 ijk[2] -= (NodeType::DIM + NodeType::DIM);
1429 const NodeType* nodeZDown = acc.template probeConstNode<NodeType>(ijk);
1430 ijk[2] += NodeType::DIM;
1432 ijk[1] += NodeType::DIM;
1433 const NodeType* nodeYUp = acc.template probeConstNode<NodeType>(ijk);
1434 ijk[1] -= (NodeType::DIM + NodeType::DIM);
1435 const NodeType* nodeYDown = acc.template probeConstNode<NodeType>(ijk);
1436 ijk[1] += NodeType::DIM;
1438 ijk[0] += NodeType::DIM;
1439 const NodeType* nodeXUp = acc.template probeConstNode<NodeType>(ijk);
1440 ijk[0] -= (NodeType::DIM + NodeType::DIM);
1441 const NodeType* nodeXDown = acc.template probeConstNode<NodeType>(ijk);
1442 ijk[0] += NodeType::DIM;
1444 const Index startPos = node->getValueMask().findFirstOn();
1445 for (
Index pos = startPos; pos < NodeMaskType::SIZE; ++pos) {
1447 if (!node->isValueOn(pos))
continue;
1449 ijk = NodeType::offsetToLocalCoord(pos);
1453 npos = pos + (NodeType::DIM - 1);
1454 if (nodeZDown && nodeZDown->isValueOn(npos)) {
1455 NodeMaskSegmentType* nsegment =
1456 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeZDown)], npos);
1457 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1458 connections[idx].insert(nsegment);
1460 }
else if (ijk[2] == (NodeType::DIM - 1)) {
1461 npos = pos - (NodeType::DIM - 1);
1462 if (nodeZUp && nodeZUp->isValueOn(npos)) {
1463 NodeMaskSegmentType* nsegment =
1464 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeZUp)], npos);
1465 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1466 connections[idx].insert(nsegment);
1471 npos = pos + (NodeType::DIM - 1) * NodeType::DIM;
1472 if (nodeYDown && nodeYDown->isValueOn(npos)) {
1473 NodeMaskSegmentType* nsegment =
1474 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeYDown)], npos);
1475 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1476 connections[idx].insert(nsegment);
1478 }
else if (ijk[1] == (NodeType::DIM - 1)) {
1479 npos = pos - (NodeType::DIM - 1) * NodeType::DIM;
1480 if (nodeYUp && nodeYUp->isValueOn(npos)) {
1481 NodeMaskSegmentType* nsegment =
1482 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeYUp)], npos);
1483 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1484 connections[idx].insert(nsegment);
1489 npos = pos + (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1490 if (nodeXDown && nodeXDown->isValueOn(npos)) {
1491 NodeMaskSegmentType* nsegment =
1492 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeXDown)], npos);
1493 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1494 connections[idx].insert(nsegment);
1496 }
else if (ijk[0] == (NodeType::DIM - 1)) {
1497 npos = pos - (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1498 if (nodeXUp && nodeXUp->isValueOn(npos)) {
1499 NodeMaskSegmentType* nsegment =
1500 findNodeMaskSegment(mNodeMaskArray[getNodeOffset(*nodeXUp)], npos);
1501 const Index idx = findNodeMaskSegmentIndex(segments, pos);
1502 connections[idx].insert(nsegment);
1507 for (
size_t i = 0, I = connections.size(); i < I; ++i) {
1509 typename std::set<NodeMaskSegmentType*>::iterator
1510 it = connections[i].begin(), end = connections[i].end();
1512 std::vector<NodeMaskSegmentType*>& segmentConnections = segments[i]->connections;
1513 segmentConnections.reserve(connections.size());
1514 for (; it != end; ++it) {
1515 segmentConnections.push_back(*it);
1523 static inline size_t getNodeOffset(
const NodeType& node) {
1524 return static_cast<size_t>(node.origin()[0]);
1527 static inline NodeMaskSegmentType*
1528 findNodeMaskSegment(NodeMaskSegmentVector& segments,
Index pos)
1530 NodeMaskSegmentType* segment = NULL;
1532 for (
size_t n = 0, N = segments.size(); n < N; ++n) {
1533 if (segments[n]->mask.isOn(pos)) {
1534 segment = segments[n].get();
1543 findNodeMaskSegmentIndex(NodeMaskSegmentVector& segments,
Index pos)
1545 for (
Index n = 0, N =
Index(segments.size()); n < N; ++n) {
1546 if (segments[n]->mask.isOn(pos))
return n;
1551 TreeType
const *
const mTree;
1552 NodeMaskSegmentVector *
const mNodeMaskArray;
1556 template<
typename TreeType>
1564 : mSegments(!segments.empty() ? &segments.front() : NULL)
1565 , mTree(new TreeType(false))
1570 : mSegments(rhs.mSegments)
1571 , mTree(new TreeType(false))
1575 TreeTypePtr&
mask() {
return mTree; }
1583 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1584 NodeMaskSegmentType& segment = *mSegments[n];
1586 node->getValueMask() |= segment.
mask;
1591 NodeMaskSegmentType *
const *
const mSegments;
1599 template<
typename TreeType>
1606 typedef typename TreeType::template ValueConverter<bool>::Type
BoolTreeType;
1612 : mDistTree(&distTree)
1613 , mMaskTree(&maskTree)
1614 , mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : NULL)
1615 , mNewMaskTree(false)
1620 : mDistTree(rhs.mDistTree)
1621 , mMaskTree(rhs.mMaskTree)
1622 , mMaskNodes(rhs.mMaskNodes)
1623 , mNewMaskTree(false)
1633 typedef LeafNodeType NodeType;
1639 NodeMaskType maskZUp, maskZDown, maskYUp, maskYDown, maskXUp, maskXDown;
1641 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1643 BoolLeafNodeType& maskNode = *mMaskNodes[n];
1644 if (maskNode.isEmpty())
continue;
1646 Coord ijk = maskNode.origin(), nijk;
1649 if (!distNode)
continue;
1651 const ValueType *dataZUp = NULL, *dataZDown = NULL,
1652 *dataYUp = NULL, *dataYDown = NULL,
1653 *dataXUp = NULL, *dataXDown = NULL;
1655 ijk[2] += NodeType::DIM;
1656 getData(ijk, distAcc, maskAcc, maskZUp, dataZUp);
1657 ijk[2] -= (NodeType::DIM + NodeType::DIM);
1658 getData(ijk, distAcc, maskAcc, maskZDown, dataZDown);
1659 ijk[2] += NodeType::DIM;
1661 ijk[1] += NodeType::DIM;
1662 getData(ijk, distAcc, maskAcc, maskYUp, dataYUp);
1663 ijk[1] -= (NodeType::DIM + NodeType::DIM);
1664 getData(ijk, distAcc, maskAcc, maskYDown, dataYDown);
1665 ijk[1] += NodeType::DIM;
1667 ijk[0] += NodeType::DIM;
1668 getData(ijk, distAcc, maskAcc, maskXUp, dataXUp);
1669 ijk[0] -= (NodeType::DIM + NodeType::DIM);
1670 getData(ijk, distAcc, maskAcc, maskXDown, dataXDown);
1671 ijk[0] += NodeType::DIM;
1673 for (
typename BoolLeafNodeType::ValueOnIter it = maskNode.beginValueOn(); it; ++it) {
1675 const Index pos = it.pos();
1676 const ValueType val = std::abs(distNode->getValue(pos));
1678 ijk = BoolLeafNodeType::offsetToLocalCoord(pos);
1679 nijk = ijk + maskNode.origin();
1681 if (dataZUp && ijk[2] == (BoolLeafNodeType::DIM - 1)) {
1682 const Index npos = pos - (NodeType::DIM - 1);
1683 if (maskZUp.isOn(npos) && std::abs(dataZUp[npos]) > val) {
1684 newMaskAcc.
setValueOn(nijk.offsetBy(0, 0, 1));
1686 }
else if (dataZDown && ijk[2] == 0) {
1687 const Index npos = pos + (NodeType::DIM - 1);
1688 if (maskZDown.isOn(npos) && std::abs(dataZDown[npos]) > val) {
1689 newMaskAcc.
setValueOn(nijk.offsetBy(0, 0, -1));
1693 if (dataYUp && ijk[1] == (BoolLeafNodeType::DIM - 1)) {
1694 const Index npos = pos - (NodeType::DIM - 1) * NodeType::DIM;
1695 if (maskYUp.isOn(npos) && std::abs(dataYUp[npos]) > val) {
1696 newMaskAcc.
setValueOn(nijk.offsetBy(0, 1, 0));
1698 }
else if (dataYDown && ijk[1] == 0) {
1699 const Index npos = pos + (NodeType::DIM - 1) * NodeType::DIM;
1700 if (maskYDown.isOn(npos) && std::abs(dataYDown[npos]) > val) {
1701 newMaskAcc.
setValueOn(nijk.offsetBy(0, -1, 0));
1705 if (dataXUp && ijk[0] == (BoolLeafNodeType::DIM - 1)) {
1706 const Index npos = pos - (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1707 if (maskXUp.isOn(npos) && std::abs(dataXUp[npos]) > val) {
1708 newMaskAcc.
setValueOn(nijk.offsetBy(1, 0, 0));
1710 }
else if (dataXDown && ijk[0] == 0) {
1711 const Index npos = pos + (NodeType::DIM - 1) * NodeType::DIM * NodeType::DIM;
1712 if (maskXDown.isOn(npos) && std::abs(dataXDown[npos]) > val) {
1713 newMaskAcc.
setValueOn(nijk.offsetBy(-1, 0, 0));
1729 data = node->buffer().data();
1730 mask = node->getValueMask();
1731 const BoolLeafNodeType* maskNodePt = maskAcc.
probeConstLeaf(ijk);
1732 if (maskNodePt) mask -= maskNodePt->getValueMask();
1736 TreeType
const *
const mDistTree;
1737 BoolTreeType *
const mMaskTree;
1738 BoolLeafNodeType **
const mMaskNodes;
1740 BoolTreeType mNewMaskTree;
1744 template<
typename TreeType>
1753 : mTree(&tree), mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : NULL)
1761 std::vector<Index> indexList;
1762 indexList.reserve(NodeMaskType::SIZE);
1764 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1766 BoolLeafNodeType& maskNode = *mMaskNodes[n];
1769 if (!distNode)
continue;
1771 NodeMaskType mask(distNode->getValueMask());
1772 NodeMaskType& narrowbandMask = maskNode.
getValueMask();
1774 for (
Index pos = narrowbandMask.findFirstOn(); pos < NodeMaskType::SIZE; ++pos) {
1775 if (narrowbandMask.isOn(pos)) indexList.push_back(pos);
1778 mask -= narrowbandMask;
1781 const ValueType* data = distNode->buffer().data();
1784 while (!indexList.empty()) {
1786 const Index pos = indexList.back();
1787 indexList.pop_back();
1789 if (narrowbandMask.isOn(pos))
continue;
1790 narrowbandMask.setOn(pos);
1792 const ValueType dist = std::abs(data[pos]);
1794 ijk = LeafNodeType::offsetToLocalCoord(pos);
1796 Index npos = pos - 1;
1797 if (ijk[2] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1799 indexList.push_back(npos);
1803 if (ijk[2] != (LeafNodeType::DIM - 1) && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1805 indexList.push_back(npos);
1808 npos = pos - LeafNodeType::DIM;
1809 if (ijk[1] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1811 indexList.push_back(npos);
1814 npos = pos + LeafNodeType::DIM;
1815 if (ijk[1] != (LeafNodeType::DIM - 1) && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1817 indexList.push_back(npos);
1820 npos = pos - LeafNodeType::DIM * LeafNodeType::DIM;
1821 if (ijk[0] != 0 && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1823 indexList.push_back(npos);
1826 npos = pos + LeafNodeType::DIM * LeafNodeType::DIM;
1827 if (ijk[0] != (LeafNodeType::DIM - 1) && mask.isOn(npos) && std::abs(data[npos]) > dist) {
1829 indexList.push_back(npos);
1840 template<
typename TreeType>
1843 typedef typename TreeType::template ValueConverter<bool>::Type
BoolTreeType;
1848 : mTree(&tree), mSegments(!segments.empty() ? &segments.front() : NULL)
1854 const TreeType& distTree = *mTree;
1855 std::vector<BoolLeafNodeType*> nodes;
1857 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1859 BoolTreeType& narrowBandMask = *mSegments[n];
1861 BoolTreeType candidateMask(narrowBandMask,
false,
TopologyCopy());
1866 candidateMask.getNodes(nodes);
1867 if (nodes.empty())
break;
1869 const tbb::blocked_range<size_t> nodeRange(0, nodes.size());
1873 narrowBandMask.topologyUnion(candidateMask);
1876 tbb::parallel_reduce(nodeRange, op);
1880 candidateMask.clear();
1891 template<
typename TreeType>
1903 , mSegments(!segments.empty() ? &segments.front() : NULL)
1904 , mMinValue(ValueType(0.0))
1909 std::vector<const InternalNodeType*> nodes;
1910 tree.getNodes(nodes);
1912 if (!nodes.empty()) {
1914 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1919 if (minSDFValue > ValueType(0.0)) {
1920 std::vector<const LeafNodeType*> nodes;
1921 tree.getNodes(nodes);
1922 if (!nodes.empty()) {
1924 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1929 mMinValue = minSDFValue;
1933 const ValueType interiorValue = -std::abs(mMinValue);
1934 const ValueType exteriorValue = std::abs(mTree->background());
1935 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1942 TreeType
const *
const mTree;
1943 TreeTypePtr *
const mSegments;
1944 ValueType mMinValue;
1948 template<
typename TreeType>
1955 typedef typename TreeType::template ValueConverter<bool>::Type
BoolTreeType;
1959 MaskedCopy(
const TreeType& tree, std::vector<TreeTypePtr>& segments, std::vector<BoolTreeTypePtr>& masks)
1961 , mSegments(!segments.empty() ? &segments.front() : NULL)
1962 , mMasks(!masks.empty() ? &masks.front() : NULL)
1968 std::vector<const BoolLeafNodeType*> nodes;
1970 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
1972 const BoolTreeType& mask = *mMasks[n];
1975 mask.getNodes(nodes);
1977 Copy op(*mTree, nodes);
1978 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
1979 mSegments[n] = op.outputTree();
1986 Copy(
const TreeType& inputTree, std::vector<const BoolLeafNodeType*>& maskNodes)
1987 : mInputTree(&inputTree)
1988 , mMaskNodes(!maskNodes.empty() ? &maskNodes.front() : NULL)
1989 , mOutputTreePtr(
new TreeType(inputTree.background()))
1993 Copy(
const Copy& rhs, tbb::split)
1994 : mInputTree(rhs.mInputTree)
1995 , mMaskNodes(rhs.mMaskNodes)
1996 , mOutputTreePtr(
new TreeType(mInputTree->background()))
2000 TreeTypePtr& outputTree() {
return mOutputTreePtr; }
2002 void join(Copy& rhs) { mOutputTreePtr->merge(*rhs.mOutputTreePtr); }
2004 void operator()(
const tbb::blocked_range<size_t>& range) {
2009 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
2011 const BoolLeafNodeType& maskNode = *mMaskNodes[n];
2012 if (maskNode.isEmpty())
continue;
2014 const Coord& ijk = maskNode.origin();
2019 LeafNodeType* outputNode = outputAcc.
touchLeaf(ijk);
2021 for (
typename BoolLeafNodeType::ValueOnCIter it = maskNode.cbeginValueOn(); it; ++it) {
2022 const Index idx = it.pos();
2023 outputNode->setValueOn(idx, inputNode->getValue(idx));
2027 if (valueDepth >= 0) {
2028 outputAcc.
addTile(TreeType::RootNodeType::LEVEL - valueDepth,
2029 ijk, inputAcc.
getValue(ijk),
true);
2036 TreeType
const *
const mInputTree;
2037 BoolLeafNodeType
const *
const *
const mMaskNodes;
2038 TreeTypePtr mOutputTreePtr;
2041 TreeType
const *
const mTree;
2042 TreeTypePtr *
const mSegments;
2043 BoolTreeTypePtr *
const mMasks;
2050 template<
typename VolumePtrType>
2054 : mSegments(!segments.empty() ? &segments.front() : NULL)
2055 , mCountArray(countArray)
2060 for (
size_t n = range.begin(), N = range.end(); n < N; ++n) {
2061 mCountArray[n] = mSegments[n]->activeVoxelCount();
2074 inline bool operator() (
const size_t& lhs,
const size_t& rhs)
const 2076 return (mCountArray[lhs] > mCountArray[rhs]);
2085 template<
typename TreeType>
2091 static BoolTreePtrType
constructMask(
const TreeType&, BoolTreePtrType& maskTree) {
return maskTree; }
2092 static TreeTypePtr
construct(
const TreeType&, TreeTypePtr& tree) {
return tree; }
2096 template<
typename TreeType>
2103 typedef typename TreeType::template ValueConverter<bool>::Type
BoolTreeType;
2108 static BoolGridPtrType
constructMask(
const GridType& grid, BoolTreePtrType& maskTree) {
2109 BoolGridPtrType maskGrid(BoolGridType::create(maskTree));
2114 static GridTypePtr
construct(
const GridType& grid, TreeTypePtr& maskTree) {
2115 GridTypePtr maskGrid(GridType::create(maskTree));
2117 maskGrid->insertMeta(grid);
2129 template <
class Gr
idType>
2133 typedef typename GridType::ValueType ValueType;
2134 typedef typename GridType::TreeType TreeType;
2135 typedef typename TreeType::LeafNodeType LeafNodeType;
2136 typedef typename TreeType::RootNodeType RootNodeType;
2137 typedef typename RootNodeType::NodeChainType NodeChainType;
2138 typedef typename boost::mpl::at<NodeChainType, boost::mpl::int_<1> >::type InternalNodeType;
2142 TreeType& tree = grid.tree();
2144 size_t numLeafNodes = 0, numInternalNodes = 0;
2146 std::vector<LeafNodeType*> nodes;
2147 std::vector<size_t> leafnodeCount;
2151 std::vector<InternalNodeType*> internalNodes;
2152 tree.getNodes(internalNodes);
2154 numInternalNodes = internalNodes.size();
2156 leafnodeCount.push_back(0);
2157 for (
size_t n = 0; n < numInternalNodes; ++n) {
2158 leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
2161 numLeafNodes = leafnodeCount.back();
2164 nodes.reserve(numLeafNodes);
2166 for (
size_t n = 0; n < numInternalNodes; ++n) {
2167 internalNodes[n]->stealNodes(nodes, tree.background(),
false);
2175 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), minOp);
2179 if (minSDFValue > ValueType(0.0)) {
2181 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
2185 cutoffDistance = -std::abs(cutoffDistance);
2186 cutoffDistance = minSDFValue > cutoffDistance ? minSDFValue : cutoffDistance;
2192 tbb::parallel_for(tbb::blocked_range<size_t>(0, nodes.size()),
2196 typename TreeType::Ptr newTree(
new TreeType(ValueType(0.0)));
2199 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
2202 std::vector<InternalNodeType*> internalNodes;
2203 newTree->getNodes(internalNodes);
2205 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalNodes.size()),
2211 typename TreeType::ValueAllIter it(*newTree);
2212 it.setMaxDepth(TreeType::ValueAllIter::LEAF_DEPTH - 2);
2215 if (acc.
getValue(it.getCoord()) < ValueType(0.0)) {
2216 it.setValue(ValueType(1.0));
2217 it.setActiveState(
true);
2225 typename TreeType::ValueAllIter it(tree);
2226 it.setMaxDepth(TreeType::ValueAllIter::ROOT_DEPTH);
2228 if (it.getValue() < ValueType(0.0)) {
2229 newTree->addTile(TreeType::ValueAllIter::ROOT_LEVEL, it.getCoord(), ValueType(1.0),
true);
2234 grid.setTree(newTree);
2242 template <
class Gr
idOrTreeType>
2243 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2244 sdfInteriorMask(
const GridOrTreeType& volume,
typename GridOrTreeType::ValueType isovalue)
2249 typedef typename TreeType::template ValueConverter<bool>::Type::Ptr BoolTreePtrType;
2256 template<
typename Gr
idOrTreeType>
2257 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2259 typename GridOrTreeType::ValueType isovalue,
2265 typedef typename TreeType::template ValueConverter<char>::Type::Ptr CharTreePtrType;
2268 typedef typename TreeType::template ValueConverter<bool>::Type::Ptr BoolTreePtrType;
2278 template<
typename Gr
idOrTreeType>
2279 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
2285 std::vector<const typename TreeType::LeafNodeType*> nodes;
2286 tree.getNodes(nodes);
2288 typedef typename TreeType::template ValueConverter<bool>::Type BoolTreeType;
2289 typename BoolTreeType::Ptr mask(
new BoolTreeType(
false));
2292 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
2301 template<
typename Gr
idOrTreeType>
2304 std::vector<
typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr>& masks)
2307 typedef typename TreeType::template ValueConverter<bool>::Type BoolTreeType;
2308 typedef typename BoolTreeType::Ptr BoolTreePtrType;
2309 typedef typename BoolTreeType::LeafNodeType BoolLeafNodeType;
2312 typedef typename NodeMaskSegmentType::Ptr NodeMaskSegmentPtrType;
2313 typedef typename std::vector<NodeMaskSegmentPtrType> NodeMaskSegmentPtrVector;
2314 typedef typename std::vector<NodeMaskSegmentType*> NodeMaskSegmentRawPtrVector;
2320 BoolTreeType topologyMask(tree,
false,
TopologyCopy());
2322 if (topologyMask.hasActiveTiles()) {
2323 topologyMask.voxelizeActiveTiles();
2326 std::vector<BoolLeafNodeType*> leafnodes;
2327 topologyMask.getNodes(leafnodes);
2329 if (leafnodes.empty())
return;
2334 boost::scoped_array<NodeMaskSegmentPtrVector> nodeSegmentArray(
new NodeMaskSegmentPtrVector[leafnodes.size()]);
2336 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
2342 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
2344 topologyMask, nodeSegmentArray.get()));
2346 topologyMask.clear();
2348 size_t nodeSegmentCount = 0;
2349 for (
size_t n = 0, N = leafnodes.size(); n < N; ++n) {
2350 nodeSegmentCount += nodeSegmentArray[n].size();
2355 std::deque<NodeMaskSegmentRawPtrVector> nodeSegmentGroups;
2357 NodeMaskSegmentType* nextSegment = nodeSegmentArray[0][0].get();
2358 while (nextSegment) {
2360 nodeSegmentGroups.push_back(NodeMaskSegmentRawPtrVector());
2362 std::vector<NodeMaskSegmentType*>& segmentGroup = nodeSegmentGroups.back();
2363 segmentGroup.reserve(nodeSegmentCount);
2365 std::deque<NodeMaskSegmentType*> segmentQueue;
2366 segmentQueue.push_back(nextSegment);
2369 while (!segmentQueue.empty()) {
2371 NodeMaskSegmentType* segment = segmentQueue.back();
2372 segmentQueue.pop_back();
2374 if (segment->visited)
continue;
2375 segment->visited =
true;
2377 segmentGroup.push_back(segment);
2380 std::vector<NodeMaskSegmentType*>& connections = segment->connections;
2381 for (
size_t n = 0, N = connections.size(); n < N; ++n) {
2382 if (!connections[n]->visited) segmentQueue.push_back(connections[n]);
2387 for (
size_t n = 0, N = leafnodes.size(); n < N; ++n) {
2388 NodeMaskSegmentPtrVector& nodeSegments = nodeSegmentArray[n];
2389 for (
size_t i = 0, I = nodeSegments.size(); i < I; ++i) {
2390 if (!nodeSegments[i]->visited) nextSegment = nodeSegments[i].get();
2397 if (nodeSegmentGroups.size() == 1) {
2399 BoolTreePtrType mask(
new BoolTreeType(tree,
false,
TopologyCopy()));
2401 if (mask->hasActiveTiles()) {
2402 mask->voxelizeActiveTiles();
2408 }
else if (nodeSegmentGroups.size() > 1) {
2410 for (
size_t n = 0, N = nodeSegmentGroups.size(); n < N; ++n) {
2412 NodeMaskSegmentRawPtrVector& segmentGroup = nodeSegmentGroups[n];
2415 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, segmentGroup.size()), op);
2424 if (masks.size() > 1) {
2425 const size_t segmentCount = masks.size();
2427 boost::scoped_array<size_t> segmentOrderArray(
new size_t[segmentCount]);
2428 boost::scoped_array<size_t> voxelCountArray(
new size_t[segmentCount]);
2430 for (
size_t n = 0; n < segmentCount; ++n) {
2431 segmentOrderArray[n] = n;
2434 tbb::parallel_for(tbb::blocked_range<size_t>(0, segmentCount),
2437 size_t *begin = segmentOrderArray.get();
2440 std::vector<BoolTreePtrType> orderedMasks;
2441 orderedMasks.reserve(masks.size());
2443 for (
size_t n = 0; n < segmentCount; ++n) {
2444 orderedMasks.push_back(masks[segmentOrderArray[n]]);
2447 masks.swap(orderedMasks);
2453 template<
typename Gr
idOrTreeType>
2458 typedef typename TreeType::Ptr TreePtrType;
2459 typedef typename TreeType::template ValueConverter<bool>::Type BoolTreeType;
2460 typedef typename BoolTreeType::Ptr BoolTreePtrType;
2465 std::vector<BoolTreePtrType> maskSegmentArray;
2468 const size_t numSegments = maskSegmentArray.size();
2470 if (numSegments < 2) {
2472 TreePtrType segment(
new TreeType(inputTree));
2478 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
2481 std::vector<TreePtrType> outputSegmentArray(numSegments);
2483 tbb::parallel_for(segmentRange,
2486 for (
size_t n = 0, N = numSegments; n < N; ++n) {
2493 template<
typename Gr
idOrTreeType>
2495 segmentSDF(
const GridOrTreeType& volume, std::vector<typename GridOrTreeType::Ptr>& segments)
2498 typedef typename TreeType::Ptr TreePtrType;
2499 typedef typename TreeType::template ValueConverter<bool>::Type BoolTreeType;
2500 typedef typename BoolTreeType::Ptr BoolTreePtrType;
2508 std::vector<BoolTreePtrType> maskSegmentArray;
2511 const size_t numSegments = maskSegmentArray.size();
2513 if (numSegments < 2) {
2515 TreePtrType segment(
new TreeType(inputTree));
2521 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
2525 tbb::parallel_for(segmentRange,
2529 std::vector<TreePtrType> outputSegmentArray(numSegments);
2531 tbb::parallel_for(segmentRange,
2534 tbb::parallel_for(segmentRange,
2538 for (
size_t n = 0, N = numSegments; n < N; ++n) {
2549 #endif // OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
void addLeaf(LeafNodeT *leaf)
Add the specified leaf to this tree, possibly creating a child branch in the process. If the leaf node already exists, replace it.
Definition: ValueAccessor.h:374
LeafNodeT * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z), or NULL if no such node exists...
Definition: ValueAccessor.h:424
int getValueDepth(const Coord &xyz) const
Definition: ValueAccessor.h:275
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don't change its value.
Definition: LeafNode.h:714
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:47
boost::shared_ptr< Grid > Ptr
Definition: Grid.h:485
void setValueOn(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:292
math::Transform & transform()
Return a reference to this grid's transform, which might be shared with other grids.
Definition: Grid.h:335
Index32 Index
Definition: Types.h:58
#define OPENVDB_VERSION_NAME
Definition: version.h:43
const Coord & origin() const
Return the grid index coordinates of this node's local origin.
Definition: LeafNode.h:475
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:256
Propagates the sign of distance values from the active voxels in the narrow band to the inactive valu...
Templated block class to hold specific data types and a fixed number of values determined by Log2Dim...
Definition: LeafNode.h:65
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:898
Convert polygonal meshes that consist of quads and/or triangles into signed or unsigned distance fiel...
Coord offsetBy(Int32 dx, Int32 dy, Int32 dz) const
Definition: Coord.h:111
Definition: Exceptions.h:39
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Add a tile at the specified tree level that contains voxel (x, y, z), possibly deleting existing node...
Definition: ValueAccessor.h:382
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:263
Index64 onVoxelCount() const
Return the number of voxels marked On.
Definition: LeafNode.h:440
LeafNodeT * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one, but preserve the values and active states of all voxels.
Definition: ValueAccessor.h:393
_TreeType TreeType
Definition: Grid.h:900
static TreeType & tree(TreeType &t)
Definition: Grid.h:915
const NodeMaskType & getValueMask() const
Definition: LeafNode.h:1109
void setOff(Index32 n)
Set the nth bit off.
Definition: NodeMasks.h:454
TreeType & tree() const
Return a reference to the tree associated with this accessor.
Definition: ValueAccessor.h:147
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
const LeafNodeT * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z), or NULL if no such node exists...
Definition: ValueAccessor.h:429
void setOrigin(const Coord &origin)
Set the grid index coordinates of this node's local origin.
Definition: LeafNode.h:472
Container class that associates a tree with a transform and metadata.
Definition: Grid.h:54