OpenVDB  3.1.0
LevelSetUtil.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2015 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 //
37 
38 
39 #ifndef OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
40 #define OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
41 
42 #include "MeshToVolume.h" // for traceExteriorBoundaries
43 #include "SignedFloodFill.h" // for signedFloodFill
44 
45 #include <openvdb/Types.h>
46 #include <openvdb/Grid.h>
47 
48 #include <tbb/blocked_range.h>
49 #include <tbb/parallel_for.h>
50 #include <tbb/parallel_reduce.h>
51 
52 #include <limits>
53 
54 namespace openvdb {
56 namespace OPENVDB_VERSION_NAME {
57 namespace tools {
58 
59 // MS Visual C++ requires this extra level of indirection in order to compile
60 // THIS MUST EXIST IN AN UNNAMED NAMESPACE IN ORDER TO COMPILE ON WINDOWS
61 namespace {
62 
63 template<typename GridType>
64 inline typename GridType::ValueType lsutilGridMax()
65 {
67 }
68 
69 template<typename GridType>
70 inline typename GridType::ValueType lsutilGridZero()
71 {
72  return zeroVal<typename GridType::ValueType>();
73 }
74 
75 } // unnamed namespace
76 
77 
79 
80 
95 template<class GridType>
96 inline void
98  GridType& grid,
99  typename GridType::ValueType cutoffDistance = lsutilGridMax<GridType>());
100 
101 
112 template<class GridOrTreeType>
113 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
115  const GridOrTreeType& volume,
116  typename GridOrTreeType::ValueType isovalue = lsutilGridZero<GridOrTreeType>());
117 
118 
139 template<typename GridOrTreeType>
140 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
141 extractEnclosedRegion(const GridOrTreeType& volume,
142  typename GridOrTreeType::ValueType isovalue = lsutilGridZero<GridOrTreeType>(),
143  const typename TreeAdapter<GridOrTreeType>::TreeType::template ValueConverter<bool>::Type* fillMask = NULL);
144 
145 
146 
147 
150 
151 // Internal utility objects and implementation details
152 
153 
154 namespace level_set_util_internal {
155 
156 
157 template<typename LeafNodeType>
159 
160  typedef typename LeafNodeType::ValueType ValueType;
162 
164  ValueType isovalue, const LeafNodeType ** nodes, BoolLeafNodeType ** maskNodes)
165  : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
166  {
167  }
168 
169  void operator()(const tbb::blocked_range<size_t>& range) const {
170 
171  BoolLeafNodeType * maskNodePt = NULL;
172 
173  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
174 
175  mMaskNodes[n] = NULL;
176  const LeafNodeType& node = *mNodes[n];
177 
178  if (!maskNodePt) {
179  maskNodePt = new BoolLeafNodeType(node.origin(), false);
180  } else {
181  maskNodePt->setOrigin(node.origin());
182  }
183 
184  const ValueType* values = &node.getValue(0);
185  for (Index i = 0; i < LeafNodeType::SIZE; ++i) {
186  if (values[i] < mIsovalue) maskNodePt->setValueOn(i, true);
187  }
188 
189  if (maskNodePt->onVoxelCount() > 0) {
190  mMaskNodes[n] = maskNodePt;
191  maskNodePt = NULL;
192  }
193  }
194 
195  if (maskNodePt) delete maskNodePt;
196  }
197 
198  LeafNodeType const * const * const mNodes;
199  BoolLeafNodeType ** const mMaskNodes;
200  ValueType const mIsovalue;
201 }; // MaskInteriorVoxels
202 
203 
204 template<typename TreeType, typename InternalNodeType>
206 
207  typedef typename TreeType::ValueType ValueType;
208 
209  MaskInteriorTiles(ValueType isovalue, const TreeType& tree, InternalNodeType ** maskNodes)
210  : mTree(&tree), mMaskNodes(maskNodes), mIsovalue(isovalue) { }
211 
212  void operator()(const tbb::blocked_range<size_t>& range) const {
214  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
215  typename InternalNodeType::ValueAllIter it = mMaskNodes[n]->beginValueAll();
216  for (; it; ++it) {
217  if (acc.getValue(it.getCoord()) < mIsovalue) {
218  it.setValue(true);
219  it.setValueOn(true);
220  }
221  }
222  }
223  }
224 
225  TreeType const * const mTree;
226  InternalNodeType ** const mMaskNodes;
227  ValueType const mIsovalue;
228 }; // MaskInteriorTiles
229 
230 
231 template<typename TreeType>
232 struct PopulateTree {
233 
234  typedef typename TreeType::ValueType ValueType;
235  typedef typename TreeType::LeafNodeType LeafNodeType;
236 
237  PopulateTree(TreeType& tree, LeafNodeType** leafnodes,
238  const size_t * nodexIndexMap, ValueType background)
239  : mNewTree(background)
240  , mTreePt(&tree)
241  , mNodes(leafnodes)
242  , mNodeIndexMap(nodexIndexMap)
243  {
244  }
245 
246  PopulateTree(PopulateTree& rhs, tbb::split)
247  : mNewTree(rhs.mNewTree.background())
248  , mTreePt(&mNewTree)
249  , mNodes(rhs.mNodes)
250  , mNodeIndexMap(rhs.mNodeIndexMap)
251  {
252  }
253 
254  void operator()(const tbb::blocked_range<size_t>& range) {
255 
256  tree::ValueAccessor<TreeType> acc(*mTreePt);
257 
258  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
259  for (size_t i = mNodeIndexMap[n], I = mNodeIndexMap[n + 1]; i < I; ++i) {
260  if (mNodes[i] != NULL) acc.addLeaf(mNodes[i]);
261  }
262  }
263  }
264 
265  void join(PopulateTree& rhs) { mTreePt->merge(*rhs.mTreePt); }
266 
267 private:
268  TreeType mNewTree;
269  TreeType * const mTreePt;
270  LeafNodeType ** const mNodes;
271  size_t const * const mNodeIndexMap;
272 }; // PopulateTree
273 
274 
276 template<typename LeafNodeType>
278 
279  typedef typename LeafNodeType::ValueType ValueType;
281 
283  ValueType isovalue, const LeafNodeType ** nodes, CharLeafNodeType ** maskNodes)
284  : mNodes(nodes), mMaskNodes(maskNodes), mIsovalue(isovalue)
285  {
286  }
287 
288  void operator()(const tbb::blocked_range<size_t>& range) const {
289 
290  CharLeafNodeType * maskNodePt = NULL;
291 
292  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
293 
294  mMaskNodes[n] = NULL;
295  const LeafNodeType& node = *mNodes[n];
296 
297  if (!maskNodePt) {
298  maskNodePt = new CharLeafNodeType(node.origin(), 1);
299  } else {
300  maskNodePt->setOrigin(node.origin());
301  }
302 
303  typename LeafNodeType::ValueOnCIter it;
304  for (it = node.cbeginValueOn(); it; ++it) {
305  maskNodePt->setValueOn(it.pos(), ((*it - mIsovalue) < 0.0) ? 0 : 1);
306  }
307 
308  if (maskNodePt->onVoxelCount() > 0) {
309  mMaskNodes[n] = maskNodePt;
310  maskNodePt = NULL;
311  }
312  }
313 
314  if (maskNodePt) delete maskNodePt;
315  }
316 
317  LeafNodeType const * const * const mNodes;
318  CharLeafNodeType ** const mMaskNodes;
319  ValueType const mIsovalue;
320 }; // LabelBoundaryVoxels
321 
322 
323 template<typename LeafNodeType>
325  typedef typename LeafNodeType::ValueType ValueType;
326 
327  FlipRegionSign(LeafNodeType ** nodes) : mNodes(nodes) { }
328 
329  void operator()(const tbb::blocked_range<size_t>& range) const {
330  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
331  ValueType* values = const_cast<ValueType*>(&mNodes[n]->getValue(0));
332  for (Index i = 0; i < LeafNodeType::SIZE; ++i) {
333  values[i] = values[i] < 0 ? 1 : -1;
334  }
335  }
336  }
337 
338  LeafNodeType ** const mNodes;
339 }; // FlipRegionSign
340 
341 
342 template<typename LeafNodeType>
344 
345  typedef typename LeafNodeType::ValueType ValueType;
346 
347  FindMinVoxelValue(LeafNodeType const * const * const leafnodes)
348  : minValue(std::numeric_limits<ValueType>::max())
349  , mNodes(leafnodes)
350  {
351  }
352 
354  : minValue(std::numeric_limits<ValueType>::max())
355  , mNodes(rhs.mNodes)
356  {
357  }
358 
359  void operator()(const tbb::blocked_range<size_t>& range) {
360  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
361  const ValueType* data = mNodes[n]->buffer().data();
362  for (Index i = 0; i < LeafNodeType::SIZE; ++i) {
363  minValue = std::min(minValue, data[i]);
364  }
365  }
366  }
367 
368  void join(FindMinVoxelValue& rhs) { minValue = std::min(minValue, rhs.minValue); }
369 
370  ValueType minValue;
371 
372  LeafNodeType const * const * const mNodes;
373 }; // FindMinVoxelValue
374 
375 
376 template<typename InternalNodeType>
378 
379  typedef typename InternalNodeType::ValueType ValueType;
380 
381  FindMinTileValue(InternalNodeType const * const * const nodes)
382  : minValue(std::numeric_limits<ValueType>::max())
383  , mNodes(nodes)
384  {
385  }
386 
388  : minValue(std::numeric_limits<ValueType>::max())
389  , mNodes(rhs.mNodes)
390  {
391  }
392 
393  void operator()(const tbb::blocked_range<size_t>& range) {
394  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
395  typename InternalNodeType::ValueAllCIter it = mNodes[n]->beginValueAll();
396  for (; it; ++it) {
397  minValue = std::min(minValue, *it);
398  }
399  }
400  }
401 
402  void join(FindMinTileValue& rhs) { minValue = std::min(minValue, rhs.minValue); }
403 
404  ValueType minValue;
405 
406  InternalNodeType const * const * const mNodes;
407 }; // FindMinTileValue
408 
409 
410 template<typename LeafNodeType>
412 
413  typedef typename LeafNodeType::ValueType ValueType;
414 
415  SDFVoxelsToFogVolume(LeafNodeType ** nodes, ValueType cutoffDistance)
416  : mNodes(nodes), mWeight(ValueType(1.0) / cutoffDistance)
417  {
418  }
419 
420  void operator()(const tbb::blocked_range<size_t>& range) const {
421 
422  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
423 
424  LeafNodeType& node = *mNodes[n];
425  node.setValuesOff();
426 
427  ValueType* values = node.buffer().data();
428  for (Index i = 0; i < LeafNodeType::SIZE; ++i) {
429  values[i] = values[i] > ValueType(0.0) ? ValueType(0.0) : values[i] * mWeight;
430  if (values[i] > ValueType(0.0)) node.setValueOn(i);
431  }
432 
433  if (node.onVoxelCount() == 0) {
434  delete mNodes[n];
435  mNodes[n] = NULL;
436  }
437  }
438  }
439 
440  LeafNodeType ** const mNodes;
441  ValueType const mWeight;
442 }; // SDFVoxelsToFogVolume
443 
444 
445 template<typename TreeType, typename InternalNodeType>
447 
448  SDFTilesToFogVolume(const TreeType& tree, InternalNodeType ** nodes)
449  : mTree(&tree), mNodes(nodes) { }
450 
451  void operator()(const tbb::blocked_range<size_t>& range) const {
452 
453  typedef typename TreeType::ValueType ValueType;
455 
456  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
457  typename InternalNodeType::ValueAllIter it = mNodes[n]->beginValueAll();
458  for (; it; ++it) {
459  if (acc.getValue(it.getCoord()) < ValueType(0.0)) {
460  it.setValue(ValueType(1.0));
461  it.setValueOn(true);
462  }
463  }
464  }
465  }
466 
467  TreeType const * const mTree;
468  InternalNodeType ** const mNodes;
469 }; // SDFTilesToFogVolume
470 
471 
472 template<typename TreeType>
474 
475  typedef typename TreeType::ValueType ValueType;
476  typedef typename TreeType::LeafNodeType LeafNodeType;
477  typedef typename TreeType::template ValueConverter<bool>::Type BoolTreeType;
478  typedef typename BoolTreeType::LeafNodeType BoolLeafNodeType;
479 
480  FillMaskBoundary(const TreeType& tree, ValueType isovalue, const BoolTreeType& fillMask,
481  const BoolLeafNodeType ** fillNodes, BoolLeafNodeType ** newNodes)
482  : mTree(&tree), mFillMask(&fillMask), mFillNodes(fillNodes), mNewNodes(newNodes), mIsovalue(isovalue)
483  {
484  }
485 
486  void operator()(const tbb::blocked_range<size_t>& range) const {
487 
488  tree::ValueAccessor<const BoolTreeType> maskAcc(*mFillMask);
489  tree::ValueAccessor<const TreeType> distAcc(*mTree);
490 
491  boost::scoped_array<char> valueMask(new char[BoolLeafNodeType::SIZE]);
492 
493  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
494 
495  mNewNodes[n] = NULL;
496  const BoolLeafNodeType& node = *mFillNodes[n];
497  const Coord& origin = node.origin();
498 
499  const bool denseNode = node.isDense();
500 
501  // possible early out if the fill mask is dense
502  if (denseNode) {
503 
504  int denseNeighbors = 0;
505 
506  const BoolLeafNodeType* neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(-1, 0, 0));
507  if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
508 
509  neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(BoolLeafNodeType::DIM, 0, 0));
510  if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
511 
512  neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, -1, 0));
513  if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
514 
515  neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, BoolLeafNodeType::DIM, 0));
516  if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
517 
518  neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, 0, -1));
519  if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
520 
521  neighborNode = maskAcc.probeConstLeaf(origin.offsetBy(0, 0, BoolLeafNodeType::DIM));
522  if (neighborNode && neighborNode->isDense()) ++denseNeighbors;
523 
524  if (denseNeighbors == 6) continue;
525  }
526 
527  // rest value mask
528  memset(valueMask.get(), 0, sizeof(char) * BoolLeafNodeType::SIZE);
529 
530  const typename TreeType::LeafNodeType* distNode = distAcc.probeConstLeaf(origin);
531 
532  // check internal voxel neighbors
533 
534  bool earlyTermination = false;
535 
536  if (!denseNode) {
537  if (distNode) {
538  evalInternalNeighborsP(valueMask.get(), node, *distNode);
539  evalInternalNeighborsN(valueMask.get(), node, *distNode);
540  } else if (distAcc.getValue(origin) > mIsovalue) {
541  earlyTermination = evalInternalNeighborsP(valueMask.get(), node);
542  if (!earlyTermination) earlyTermination = evalInternalNeighborsN(valueMask.get(), node);
543  }
544  }
545 
546  // check external voxel neighbors
547 
548  if (!earlyTermination) {
549  evalExternalNeighborsX<true>(valueMask.get(), node, maskAcc, distAcc);
550  evalExternalNeighborsX<false>(valueMask.get(), node, maskAcc, distAcc);
551  evalExternalNeighborsY<true>(valueMask.get(), node, maskAcc, distAcc);
552  evalExternalNeighborsY<false>(valueMask.get(), node, maskAcc, distAcc);
553  evalExternalNeighborsZ<true>(valueMask.get(), node, maskAcc, distAcc);
554  evalExternalNeighborsZ<false>(valueMask.get(), node, maskAcc, distAcc);
555  }
556 
557  // Export marked boundary voxels.
558 
559  int numBoundaryValues = 0;
560  for (Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
561  numBoundaryValues += valueMask[i] == 1;
562  }
563 
564  if (numBoundaryValues > 0) {
565  mNewNodes[n] = new BoolLeafNodeType(origin, false);
566  for (Index i = 0, I = BoolLeafNodeType::SIZE; i < I; ++i) {
567  if (valueMask[i] == 1) mNewNodes[n]->setValueOn(i);
568  }
569  }
570  }
571  }
572 
573 private:
574 
575  // Check internal voxel neighbors in positive {x, y, z} directions.
576 
577  void evalInternalNeighborsP(char* valueMask, const BoolLeafNodeType& node, const LeafNodeType& distNode) const {
578 
579  for (Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
580  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
581  for (Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
582  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
583  for (Index z = 0; z < BoolLeafNodeType::DIM - 1; ++z) {
584  const Index pos = yPos + z;
585 
586  if (valueMask[pos] != 0 || !node.isValueOn(pos)) continue;
587 
588  if (!node.isValueOn(pos + 1) && distNode.getValue(pos + 1) > mIsovalue) {
589  valueMask[pos] = 1;
590  }
591  }
592  }
593  }
594 
595  for (Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
596  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
597  for (Index y = 0; y < BoolLeafNodeType::DIM - 1; ++y) {
598  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
599  for (Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
600  const Index pos = yPos + z;
601 
602  if (valueMask[pos] != 0 || !node.isValueOn(pos)) continue;
603 
604  if (!node.isValueOn(pos + BoolLeafNodeType::DIM) &&
605  distNode.getValue(pos + BoolLeafNodeType::DIM) > mIsovalue) {
606  valueMask[pos] = 1;
607  }
608  }
609  }
610  }
611 
612  for (Index x = 0; x < BoolLeafNodeType::DIM - 1; ++x) {
613  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
614  for (Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
615  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
616  for (Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
617  const Index pos = yPos + z;
618 
619  if (valueMask[pos] != 0 || !node.isValueOn(pos)) continue;
620 
621  if (!node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
622  distNode.getValue(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) > mIsovalue) {
623  valueMask[pos] = 1;
624  }
625  }
626  }
627  }
628  }
629 
630  bool evalInternalNeighborsP(char* valueMask, const BoolLeafNodeType& node) const {
631 
632  for (Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
633  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
634  for (Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
635  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
636  for (Index z = 0; z < BoolLeafNodeType::DIM - 1; ++z) {
637  const Index pos = yPos + z;
638 
639  if (node.isValueOn(pos) && !node.isValueOn(pos + 1)) {
640  valueMask[pos] = 1;
641  return true;
642  }
643  }
644  }
645  }
646 
647  for (Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
648  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
649  for (Index y = 0; y < BoolLeafNodeType::DIM - 1; ++y) {
650  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
651  for (Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
652  const Index pos = yPos + z;
653 
654  if (node.isValueOn(pos) && !node.isValueOn(pos + BoolLeafNodeType::DIM)) {
655  valueMask[pos] = 1;
656  return true;
657  }
658  }
659  }
660  }
661 
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;
668 
669  if (node.isValueOn(pos) &&
670  !node.isValueOn(pos + BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
671  valueMask[pos] = 1;
672  return true;
673  }
674  }
675  }
676  }
677 
678  return false;
679  }
680 
681  // Check internal voxel neighbors in negative {x, y, z} directions.
682 
683  void evalInternalNeighborsN(char* valueMask, const BoolLeafNodeType& node, const LeafNodeType& distNode) const {
684 
685  for (Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
686  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
687  for (Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
688  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
689  for (Index z = 1; z < BoolLeafNodeType::DIM; ++z) {
690  const Index pos = yPos + z;
691 
692  if (valueMask[pos] != 0 || !node.isValueOn(pos)) continue;
693 
694  if (!node.isValueOn(pos - 1) && distNode.getValue(pos - 1) > mIsovalue) {
695  valueMask[pos] = 1;
696  }
697  }
698  }
699  }
700 
701  for (Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
702  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
703  for (Index y = 1; y < BoolLeafNodeType::DIM; ++y) {
704  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
705  for (Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
706  const Index pos = yPos + z;
707 
708  if (valueMask[pos] != 0 || !node.isValueOn(pos)) continue;
709 
710  if (!node.isValueOn(pos - BoolLeafNodeType::DIM) &&
711  distNode.getValue(pos - BoolLeafNodeType::DIM) > mIsovalue) {
712  valueMask[pos] = 1;
713  }
714  }
715  }
716  }
717 
718  for (Index x = 1; x < BoolLeafNodeType::DIM; ++x) {
719  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
720  for (Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
721  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
722  for (Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
723  const Index pos = yPos + z;
724 
725  if (valueMask[pos] != 0 || !node.isValueOn(pos)) continue;
726 
727  if (!node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) &&
728  distNode.getValue(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM) > mIsovalue) {
729  valueMask[pos] = 1;
730  }
731  }
732  }
733  }
734  }
735 
736 
737  bool evalInternalNeighborsN(char* valueMask, const BoolLeafNodeType& node) const {
738 
739  for (Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
740  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
741  for (Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
742  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
743  for (Index z = 1; z < BoolLeafNodeType::DIM; ++z) {
744  const Index pos = yPos + z;
745 
746  if (node.isValueOn(pos) && !node.isValueOn(pos - 1)) {
747  valueMask[pos] = 1;
748  return true;
749  }
750  }
751  }
752  }
753 
754  for (Index x = 0; x < BoolLeafNodeType::DIM; ++x) {
755  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
756  for (Index y = 1; y < BoolLeafNodeType::DIM; ++y) {
757  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
758  for (Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
759  const Index pos = yPos + z;
760 
761  if (node.isValueOn(pos) && !node.isValueOn(pos - BoolLeafNodeType::DIM)) {
762  valueMask[pos] = 1;
763  return true;
764  }
765  }
766  }
767  }
768 
769  for (Index x = 1; x < BoolLeafNodeType::DIM; ++x) {
770  const Index xPos = x << (2 * BoolLeafNodeType::LOG2DIM);
771  for (Index y = 0; y < BoolLeafNodeType::DIM; ++y) {
772  const Index yPos = xPos + (y << BoolLeafNodeType::LOG2DIM);
773  for (Index z = 0; z < BoolLeafNodeType::DIM; ++z) {
774  const Index pos = yPos + z;
775 
776  if (node.isValueOn(pos) &&
777  !node.isValueOn(pos - BoolLeafNodeType::DIM * BoolLeafNodeType::DIM)) {
778  valueMask[pos] = 1;
779  return true;
780  }
781  }
782  }
783  }
784 
785  return false;
786  }
787 
788 
789  // Check external voxel neighbors
790 
791  // If UpWind is true check the X+ oriented node face, else the X- oriented face.
792  template<bool UpWind>
793  void evalExternalNeighborsX(char* valueMask, const BoolLeafNodeType& node,
795  const tree::ValueAccessor<const TreeType>& distAcc) const {
796 
797  const Coord& origin = node.origin();
798  Coord ijk(0, 0, 0), nijk;
799  int step = -1;
800 
801  if (UpWind) {
802  step = 1;
803  ijk[0] = int(BoolLeafNodeType::DIM) - 1;
804  }
805 
806  const Index xPos = ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM));
807 
808  for (ijk[1] = 0; ijk[1] < int(BoolLeafNodeType::DIM); ++ijk[1]) {
809  const Index yPos = xPos + (ijk[1] << int(BoolLeafNodeType::LOG2DIM));
810 
811  for (ijk[2] = 0; ijk[2] < int(BoolLeafNodeType::DIM); ++ijk[2]) {
812  const Index pos = yPos + ijk[2];
813 
814  if (valueMask[pos] == 0 && node.isValueOn(pos)) {
815 
816  nijk = origin + ijk.offsetBy(step, 0, 0);
817 
818  if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
819  valueMask[pos] = 1;
820  }
821  }
822  }
823  }
824  }
825 
826  // If UpWind is true check the Y+ oriented node face, else the Y- oriented face.
827  template<bool UpWind>
828  void evalExternalNeighborsY(char* valueMask, const BoolLeafNodeType& node,
830  const tree::ValueAccessor<const TreeType>& distAcc) const {
831 
832  const Coord& origin = node.origin();
833  Coord ijk(0, 0, 0), nijk;
834  int step = -1;
835 
836  if (UpWind) {
837  step = 1;
838  ijk[1] = int(BoolLeafNodeType::DIM) - 1;
839  }
840 
841  const Index yPos = ijk[1] << int(BoolLeafNodeType::LOG2DIM);
842 
843  for (ijk[0] = 0; ijk[0] < int(BoolLeafNodeType::DIM); ++ijk[0]) {
844  const Index xPos = yPos + (ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM)));
845 
846  for (ijk[2] = 0; ijk[2] < int(BoolLeafNodeType::DIM); ++ijk[2]) {
847  const Index pos = xPos + ijk[2];
848 
849  if (valueMask[pos] == 0 && node.isValueOn(pos)) {
850 
851  nijk = origin + ijk.offsetBy(0, step, 0);
852  if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
853  valueMask[pos] = 1;
854  }
855  }
856  }
857  }
858  }
859 
860  // If UpWind is true check the Z+ oriented node face, else the Z- oriented face.
861  template<bool UpWind>
862  void evalExternalNeighborsZ(char* valueMask, const BoolLeafNodeType& node,
864  const tree::ValueAccessor<const TreeType>& distAcc) const {
865 
866  const Coord& origin = node.origin();
867  Coord ijk(0, 0, 0), nijk;
868  int step = -1;
869 
870  if (UpWind) {
871  step = 1;
872  ijk[2] = int(BoolLeafNodeType::DIM) - 1;
873  }
874 
875  for (ijk[0] = 0; ijk[0] < int(BoolLeafNodeType::DIM); ++ijk[0]) {
876  const Index xPos = ijk[0] << (2 * int(BoolLeafNodeType::LOG2DIM));
877 
878  for (ijk[1] = 0; ijk[1] < int(BoolLeafNodeType::DIM); ++ijk[1]) {
879  const Index pos = ijk[2] + xPos + (ijk[1] << int(BoolLeafNodeType::LOG2DIM));
880 
881  if (valueMask[pos] == 0 && node.isValueOn(pos)) {
882 
883  nijk = origin + ijk.offsetBy(0, 0, step);
884  if (!maskAcc.isValueOn(nijk) && distAcc.getValue(nijk) > mIsovalue) {
885  valueMask[pos] = 1;
886  }
887  }
888  }
889  }
890  }
891 
893 
894  TreeType const * const mTree;
895  BoolTreeType const * const mFillMask;
896  BoolLeafNodeType const * const * const mFillNodes;
897  BoolLeafNodeType ** const mNewNodes;
898  ValueType const mIsovalue;
899 }; // FillMaskBoundary
900 
901 
904 template <class TreeType>
905 inline typename TreeType::template ValueConverter<char>::Type::Ptr
906 computeEnclosedRegionMask(const TreeType& tree, typename TreeType::ValueType isovalue,
907  const typename TreeType::template ValueConverter<bool>::Type* fillMask)
908 {
909  typedef typename TreeType::LeafNodeType LeafNodeType;
910  typedef typename TreeType::RootNodeType RootNodeType;
911  typedef typename RootNodeType::NodeChainType NodeChainType;
912  typedef typename boost::mpl::at<NodeChainType, boost::mpl::int_<1> >::type InternalNodeType;
913 
914  typedef typename TreeType::template ValueConverter<char>::Type CharTreeType;
915  typedef typename CharTreeType::LeafNodeType CharLeafNodeType;
916  typedef typename CharTreeType::RootNodeType CharRootNodeType;
917  typedef typename CharRootNodeType::NodeChainType CharNodeChainType;
918 
919  typedef typename TreeType::template ValueConverter<bool>::Type BoolTreeType;
920  typedef typename BoolTreeType::LeafNodeType BoolLeafNodeType;
921 
923 
924  const TreeType* treePt = &tree;
925 
926  size_t numLeafNodes = 0, numInternalNodes = 0;
927 
928  std::vector<const LeafNodeType*> nodes;
929  std::vector<size_t> leafnodeCount;
930 
931  {
932  // compute the prefix sum of the leafnode count in each internal node.
933  std::vector<const InternalNodeType*> internalNodes;
934  treePt->getNodes(internalNodes);
935 
936  numInternalNodes = internalNodes.size();
937 
938  leafnodeCount.push_back(0);
939  for (size_t n = 0; n < numInternalNodes; ++n) {
940  leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
941  }
942 
943  numLeafNodes = leafnodeCount.back();
944 
945  // extract all leafnodes
946  nodes.reserve(numLeafNodes);
947 
948  for (size_t n = 0; n < numInternalNodes; ++n) {
949  internalNodes[n]->getNodes(nodes);
950  }
951  }
952 
953  // create mask leafnodes
954  boost::scoped_array<CharLeafNodeType*> maskNodes(new CharLeafNodeType*[numLeafNodes]);
955 
956  tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
957  LabelBoundaryVoxels<LeafNodeType>(isovalue, &nodes[0], maskNodes.get()));
958 
959  // create mask grid
960  typename CharTreeType::Ptr maskTree(new CharTreeType(1));
961 
962  PopulateTree<CharTreeType> populate(*maskTree, maskNodes.get(), &leafnodeCount[0], 1);
963  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
964 
965  // optionally evaluate the fill mask
966 
967  std::vector<CharLeafNodeType*> extraMaskNodes;
968 
969  if (fillMask) {
970 
971  std::vector<const BoolLeafNodeType*> fillMaskNodes;
972  fillMask->getNodes(fillMaskNodes);
973 
974  boost::scoped_array<BoolLeafNodeType*> boundaryMaskNodes(new BoolLeafNodeType*[fillMaskNodes.size()]);
975 
976  tbb::parallel_for(tbb::blocked_range<size_t>(0, fillMaskNodes.size()),
977  FillMaskBoundary<TreeType>(tree, isovalue, *fillMask, &fillMaskNodes[0], boundaryMaskNodes.get()));
978 
979  tree::ValueAccessor<CharTreeType> maskAcc(*maskTree);
980 
981  for (size_t n = 0, N = fillMaskNodes.size(); n < N; ++n) {
982 
983  if (boundaryMaskNodes[n] == NULL) continue;
984 
985  const BoolLeafNodeType& boundaryNode = *boundaryMaskNodes[n];
986  const Coord& origin = boundaryNode.origin();
987 
988  CharLeafNodeType* maskNodePt = maskAcc.probeLeaf(origin);
989 
990  if (!maskNodePt) {
991  maskNodePt = maskAcc.touchLeaf(origin);
992  extraMaskNodes.push_back(maskNodePt);
993  }
994 
995  char* data = maskNodePt->buffer().data();
996 
997  typename BoolLeafNodeType::ValueOnCIter it = boundaryNode.cbeginValueOn();
998  for (; it; ++it) {
999  if (data[it.pos()] != 0) data[it.pos()] = -1;
1000  }
1001 
1002  delete boundaryMaskNodes[n];
1003  }
1004  }
1005 
1006  // eliminate enclosed regions
1007  tools::traceExteriorBoundaries(*maskTree);
1008 
1009  // flip voxel sign to negative inside and positive outside.
1010  tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1011  FlipRegionSign<CharLeafNodeType>(maskNodes.get()));
1012 
1013  if (!extraMaskNodes.empty()) {
1014  tbb::parallel_for(tbb::blocked_range<size_t>(0, extraMaskNodes.size()),
1015  FlipRegionSign<CharLeafNodeType>(&extraMaskNodes[0]));
1016  }
1017 
1018  // propagate sign information into tile region
1019  tools::signedFloodFill(*maskTree);
1020 
1021  return maskTree;
1022 } // computeEnclosedRegionMask()
1023 
1024 
1025 template <class TreeType>
1026 inline typename TreeType::template ValueConverter<bool>::Type::Ptr
1027 computeInteriorMask(const TreeType& tree, typename TreeType::ValueType iso)
1028 {
1029  typedef typename TreeType::LeafNodeType LeafNodeType;
1030  typedef typename TreeType::RootNodeType RootNodeType;
1031  typedef typename RootNodeType::NodeChainType NodeChainType;
1032  typedef typename boost::mpl::at<NodeChainType, boost::mpl::int_<1> >::type InternalNodeType;
1033 
1034  typedef typename TreeType::template ValueConverter<bool>::Type BoolTreeType;
1035  typedef typename BoolTreeType::LeafNodeType BoolLeafNodeType;
1036  typedef typename BoolTreeType::RootNodeType BoolRootNodeType;
1037  typedef typename BoolRootNodeType::NodeChainType BoolNodeChainType;
1038  typedef typename boost::mpl::at<BoolNodeChainType, boost::mpl::int_<1> >::type BoolInternalNodeType;
1039 
1041  size_t numLeafNodes = 0, numInternalNodes = 0;
1042 
1043  std::vector<const LeafNodeType*> nodes;
1044  std::vector<size_t> leafnodeCount;
1045 
1046  {
1047  // compute the prefix sum of the leafnode count in each internal node.
1048  std::vector<const InternalNodeType*> internalNodes;
1049  tree.getNodes(internalNodes);
1050 
1051  numInternalNodes = internalNodes.size();
1052 
1053  leafnodeCount.push_back(0);
1054  for (size_t n = 0; n < numInternalNodes; ++n) {
1055  leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
1056  }
1057 
1058  numLeafNodes = leafnodeCount.back();
1059 
1060  // extract all leafnodes
1061  nodes.reserve(numLeafNodes);
1062 
1063  for (size_t n = 0; n < numInternalNodes; ++n) {
1064  internalNodes[n]->getNodes(nodes);
1065  }
1066  }
1067 
1068  // create mask leafnodes
1069  boost::scoped_array<BoolLeafNodeType*> maskNodes(new BoolLeafNodeType*[numLeafNodes]);
1070 
1071  tbb::parallel_for(tbb::blocked_range<size_t>(0, numLeafNodes),
1072  MaskInteriorVoxels<LeafNodeType>(iso, &nodes[0], maskNodes.get()));
1073 
1074 
1075  // create mask grid
1076  typename BoolTreeType::Ptr maskTree(new BoolTreeType(false));
1077 
1078  PopulateTree<BoolTreeType> populate(*maskTree, maskNodes.get(), &leafnodeCount[0], false);
1079  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1080 
1081 
1082  // evaluate tile values
1083  std::vector<BoolInternalNodeType*> internalMaskNodes;
1084  maskTree->getNodes(internalMaskNodes);
1085 
1086  tbb::parallel_for(tbb::blocked_range<size_t>(0, internalMaskNodes.size()),
1087  MaskInteriorTiles<TreeType, BoolInternalNodeType>(iso, tree, &internalMaskNodes[0]));
1088 
1090 
1091  typename BoolTreeType::ValueAllIter it(*maskTree);
1092  it.setMaxDepth(BoolTreeType::ValueAllIter::LEAF_DEPTH - 2);
1093 
1094  for ( ; it; ++it) {
1095  if (acc.getValue(it.getCoord()) < iso) {
1096  it.setValue(true);
1097  it.setActiveState(true);
1098  }
1099  }
1100 
1101  return maskTree;
1102 } // computeInteriorMask()
1103 
1104 
1105 template<typename TreeType>
1107 {
1108  typedef typename TreeType::template ValueConverter<bool>::Type::Ptr BoolTreePtrType;
1109  static BoolTreePtrType construct(const TreeType&, BoolTreePtrType& maskTree) { return maskTree; }
1110 };
1111 
1112 
1113 template<typename TreeType>
1114 struct GridOrTreeConstructor<Grid<TreeType> >
1115 {
1117 
1118  typedef typename TreeType::template ValueConverter<bool>::Type BoolTreeType;
1119  typedef typename BoolTreeType::Ptr BoolTreePtrType;
1122 
1123  static BoolGridPtrType construct(const GridType& grid, BoolTreePtrType& maskTree) {
1124  BoolGridPtrType maskGrid(BoolGridType::create(maskTree));
1125  maskGrid->setTransform(grid.transform().copy());
1126  return maskGrid;
1127  }
1128 };
1129 
1130 
1131 } // namespace level_set_util_internal
1132 
1133 
1135 
1136 
1137 template <class GridType>
1138 inline void
1139 sdfToFogVolume(GridType& grid, typename GridType::ValueType cutoffDistance)
1140 {
1141  typedef typename GridType::ValueType ValueType;
1142  typedef typename GridType::TreeType TreeType;
1143  typedef typename TreeType::LeafNodeType LeafNodeType;
1144  typedef typename TreeType::RootNodeType RootNodeType;
1145  typedef typename RootNodeType::NodeChainType NodeChainType;
1146  typedef typename boost::mpl::at<NodeChainType, boost::mpl::int_<1> >::type InternalNodeType;
1147 
1149 
1150  TreeType& tree = grid.tree();
1151 
1152  size_t numLeafNodes = 0, numInternalNodes = 0;
1153 
1154  std::vector<LeafNodeType*> nodes;
1155  std::vector<size_t> leafnodeCount;
1156 
1157  {
1158  // Compute the prefix sum of the leafnode count in each internal node.
1159  std::vector<InternalNodeType*> internalNodes;
1160  tree.getNodes(internalNodes);
1161 
1162  numInternalNodes = internalNodes.size();
1163 
1164  leafnodeCount.push_back(0);
1165  for (size_t n = 0; n < numInternalNodes; ++n) {
1166  leafnodeCount.push_back(leafnodeCount.back() + internalNodes[n]->leafCount());
1167  }
1168 
1169  numLeafNodes = leafnodeCount.back();
1170 
1171  // Steal all leafnodes (Removes them from the tree and transfers ownership.)
1172  nodes.reserve(numLeafNodes);
1173 
1174  for (size_t n = 0; n < numInternalNodes; ++n) {
1175  internalNodes[n]->stealNodes(nodes, tree.background(), false);
1176  }
1177 
1178  // Clamp cutoffDistance to min sdf value
1179  ValueType minSDFValue = std::numeric_limits<ValueType>::max();
1180 
1181  {
1183  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), minOp);
1184  minSDFValue = std::min(minSDFValue, minOp.minValue);
1185  }
1186 
1187  if (minSDFValue > ValueType(0.0)) {
1189  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), minOp);
1190  minSDFValue = std::min(minSDFValue, minOp.minValue);
1191  }
1192 
1193  cutoffDistance = -std::abs(cutoffDistance);
1194  cutoffDistance = minSDFValue > cutoffDistance ? minSDFValue : cutoffDistance;
1195  }
1196 
1197  // Transform voxel values and delete leafnodes that are uniformly zero after the transformation.
1198  // (Positive values are set to zero with inactive state and negative values are remapped
1199  // from zero to one with active state.)
1200  tbb::parallel_for(tbb::blocked_range<size_t>(0, nodes.size()),
1202 
1203  // Populate a new tree with the remaining leafnodes
1204  typename TreeType::Ptr newTree(new TreeType(ValueType(0.0)));
1205 
1206  level_set_util_internal::PopulateTree<TreeType> populate(*newTree, &nodes[0], &leafnodeCount[0], 0);
1207  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, numInternalNodes), populate);
1208 
1209  // Transform tile values (Negative valued tiles are set to 1.0 with active state.)
1210  std::vector<InternalNodeType*> internalNodes;
1211  newTree->getNodes(internalNodes);
1212 
1213  tbb::parallel_for(tbb::blocked_range<size_t>(0, internalNodes.size()),
1215 
1216  {
1218 
1219  typename TreeType::ValueAllIter it(*newTree);
1220  it.setMaxDepth(TreeType::ValueAllIter::LEAF_DEPTH - 2);
1221 
1222  for ( ; it; ++it) {
1223  if (acc.getValue(it.getCoord()) < ValueType(0.0)) {
1224  it.setValue(ValueType(1.0));
1225  it.setActiveState(true);
1226  }
1227  }
1228  }
1229 
1230  // Insert missing root level tiles. (The new tree is constructed from the remaining leafnodes
1231  // and will therefore not contain any root level tiles that may exist in the original tree.)
1232  {
1233  typename TreeType::ValueAllIter it(tree);
1234  it.setMaxDepth(TreeType::ValueAllIter::ROOT_DEPTH);
1235  for ( ; it; ++it) {
1236  if (it.getValue() < ValueType(0.0)) {
1237  newTree->addTile(TreeType::ValueAllIter::ROOT_LEVEL, it.getCoord(), ValueType(1.0), true);
1238  }
1239  }
1240  }
1241 
1242  grid.setTree(newTree);
1243  grid.setGridClass(GRID_FOG_VOLUME);
1244 }
1245 
1246 
1248 
1249 
1250 template <class GridOrTreeType>
1251 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
1252 sdfInteriorMask(const GridOrTreeType& volume, typename GridOrTreeType::ValueType isovalue)
1253 {
1254  typedef typename TreeAdapter<GridOrTreeType>::TreeType TreeType;
1255  const TreeType& tree = TreeAdapter<GridOrTreeType>::tree(volume);
1256 
1257  typedef typename TreeType::template ValueConverter<bool>::Type::Ptr BoolTreePtrType;
1258  BoolTreePtrType mask = level_set_util_internal::computeInteriorMask(tree, isovalue);
1259 
1261 }
1262 
1263 
1264 template<typename GridOrTreeType>
1265 inline typename GridOrTreeType::template ValueConverter<bool>::Type::Ptr
1266 extractEnclosedRegion(const GridOrTreeType& volume,
1267  typename GridOrTreeType::ValueType isovalue,
1268  const typename TreeAdapter<GridOrTreeType>::TreeType::template ValueConverter<bool>::Type* fillMask)
1269 {
1270  typedef typename TreeAdapter<GridOrTreeType>::TreeType TreeType;
1271  const TreeType& tree = TreeAdapter<GridOrTreeType>::tree(volume);
1272 
1273  typedef typename TreeType::template ValueConverter<char>::Type::Ptr CharTreePtrType;
1274  CharTreePtrType regionMask = level_set_util_internal::computeEnclosedRegionMask(tree, isovalue, fillMask);
1275 
1276  typedef typename TreeType::template ValueConverter<bool>::Type::Ptr BoolTreePtrType;
1277  BoolTreePtrType mask = level_set_util_internal::computeInteriorMask(*regionMask, 0);
1278 
1280 }
1281 
1282 
1283 } // namespace tools
1284 } // namespace OPENVDB_VERSION_NAME
1285 } // namespace openvdb
1286 
1287 #endif // OPENVDB_TOOLS_LEVEL_SET_UTIL_HAS_BEEN_INCLUDED
1288 
1289 // Copyright (c) 2012-2015 DreamWorks Animation LLC
1290 // All rights reserved. This software is distributed under the
1291 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
1292 
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
CharLeafNodeType **const mMaskNodes
Definition: LevelSetUtil.h:318
InternalNodeType **const mNodes
Definition: LevelSetUtil.h:468
Index32 Index
Definition: Types.h:58
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
LeafNodeType const *const *const mNodes
Definition: LevelSetUtil.h:198
tree::LeafNode< bool, LeafNodeType::LOG2DIM > BoolLeafNodeType
Definition: LevelSetUtil.h:161
void operator()(const tbb::blocked_range< size_t > &range)
Definition: LevelSetUtil.h:393
LeafNodeType::ValueType ValueType
Definition: LevelSetUtil.h:413
BoolTreeType::LeafNodeType BoolLeafNodeType
Definition: LevelSetUtil.h:478
SDFVoxelsToFogVolume(LeafNodeType **nodes, ValueType cutoffDistance)
Definition: LevelSetUtil.h:415
TreeType::ValueType ValueType
Definition: LevelSetUtil.h:234
Negative active values are set 0, everything else is set to 1.
Definition: LevelSetUtil.h:277
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: LevelSetUtil.h:451
LeafNodeType const *const *const mNodes
Definition: LevelSetUtil.h:317
LeafNodeType::ValueType ValueType
Definition: LevelSetUtil.h:345
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don&#39;t change its value.
Definition: LeafNode.h:712
TreeType::template ValueConverter< bool >::Type BoolTreeType
Definition: LevelSetUtil.h:477
FindMinTileValue(InternalNodeType const *const *const nodes)
Definition: LevelSetUtil.h:381
tree::LeafNode< char, LeafNodeType::LOG2DIM > CharLeafNodeType
Definition: LevelSetUtil.h:280
PopulateTree(PopulateTree &rhs, tbb::split)
Definition: LevelSetUtil.h:246
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: LevelSetUtil.h:420
static BoolTreePtrType construct(const TreeType &, BoolTreePtrType &maskTree)
Definition: LevelSetUtil.h:1109
Definition: Types.h:207
TreeType::template ValueConverter< bool >::Type::Ptr computeInteriorMask(const TreeType &tree, typename TreeType::ValueType iso)
Definition: LevelSetUtil.h:1027
ValueType const mIsovalue
Definition: LevelSetUtil.h:319
const boost::disable_if_c< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:105
void sdfToFogVolume(GridType &grid, typename GridType::ValueType cutoffDistance=lsutilGridMax< GridType >())
Threaded method to convert a sparse level set/SDF into a sparse fog volume.
Definition: LevelSetUtil.h:1139
InternalNodeType::ValueType ValueType
Definition: LevelSetUtil.h:379
ValueType const mIsovalue
Definition: LevelSetUtil.h:227
TreeType::template ValueConverter< char >::Type::Ptr computeEnclosedRegionMask(const TreeType &tree, typename TreeType::ValueType isovalue, const typename TreeType::template ValueConverter< bool >::Type *fillMask)
Constructs a memory light char tree that represents the exterior region with +1 and the interior regi...
Definition: LevelSetUtil.h:906
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: LevelSetUtil.h:288
boost::shared_ptr< Grid > Ptr
Definition: Grid.h:485
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:256
GridOrTreeType::template ValueConverter< bool >::Type::Ptr sdfInteriorMask(const GridOrTreeType &volume, typename GridOrTreeType::ValueType isovalue=lsutilGridZero< GridOrTreeType >())
Threaded method to construct a boolean mask that represents interior regions in a signed distance fie...
Definition: LevelSetUtil.h:1252
Container class that associates a tree with a transform and metadata.
Definition: Grid.h:54
TreeType const *const mTree
Definition: LevelSetUtil.h:225
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: LevelSetUtil.h:486
SDFTilesToFogVolume(const TreeType &tree, InternalNodeType **nodes)
Definition: LevelSetUtil.h:448
_TreeType TreeType
Definition: Grid.h:882
#define OPENVDB_VERSION_NAME
Definition: version.h:43
GridOrTreeType::template ValueConverter< bool >::Type::Ptr extractEnclosedRegion(const GridOrTreeType &volume, typename GridOrTreeType::ValueType isovalue=lsutilGridZero< GridOrTreeType >(), const typename TreeAdapter< GridOrTreeType >::TreeType::template ValueConverter< bool >::Type *fillMask=NULL)
Extracts the interior regions of a signed distance field and topologically enclosed (watertight) regi...
Definition: LevelSetUtil.h:1266
FindMinTileValue(FindMinTileValue &rhs, tbb::split)
Definition: LevelSetUtil.h:387
void join(PopulateTree &rhs)
Definition: LevelSetUtil.h:265
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:263
PopulateTree(TreeType &tree, LeafNodeType **leafnodes, const size_t *nodexIndexMap, ValueType background)
Definition: LevelSetUtil.h:237
Propagates the sign of distance values from the active voxels in the narrow band to the inactive valu...
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
Convert polygonal meshes that consist of quads and/or triangles into signed or unsigned distance fiel...
ValueType const mWeight
Definition: LevelSetUtil.h:441
void join(FindMinVoxelValue &rhs)
Definition: LevelSetUtil.h:368
LeafNodeType::ValueType ValueType
Definition: LevelSetUtil.h:325
Definition: Exceptions.h:39
Ptr copy() const
Definition: Transform.h:77
ValueType const mIsovalue
Definition: LevelSetUtil.h:200
InternalNodeType const *const *const mNodes
Definition: LevelSetUtil.h:406
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:880
FindMinVoxelValue(FindMinVoxelValue &rhs, tbb::split)
Definition: LevelSetUtil.h:353
TreeType::template ValueConverter< bool >::Type::Ptr BoolTreePtrType
Definition: LevelSetUtil.h:1108
LeafNodeType **const mNodes
Definition: LevelSetUtil.h:338
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
Index64 onVoxelCount() const
Return the number of voxels marked On.
Definition: LeafNode.h:438
FillMaskBoundary(const TreeType &tree, ValueType isovalue, const BoolTreeType &fillMask, const BoolLeafNodeType **fillNodes, BoolLeafNodeType **newNodes)
Definition: LevelSetUtil.h:480
TreeType::LeafNodeType LeafNodeType
Definition: LevelSetUtil.h:235
FlipRegionSign(LeafNodeType **nodes)
Definition: LevelSetUtil.h:327
TreeType::ValueType ValueType
Definition: LevelSetUtil.h:475
void traceExteriorBoundaries(FloatTreeT &tree)
Traces the exterior voxel boundary of closed objects in the input volume tree. Exterior voxels are ma...
Definition: MeshToVolume.h:2826
void signedFloodFill(TreeOrLeafManagerT &tree, bool threaded=true, size_t grainSize=1)
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
Definition: SignedFloodFill.h:280
FindMinVoxelValue(LeafNodeType const *const *const leafnodes)
Definition: LevelSetUtil.h:347
const boost::disable_if_c< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:109
LeafNodeType const *const *const mNodes
Definition: LevelSetUtil.h:372
LeafNodeType **const mNodes
Definition: LevelSetUtil.h:440
void operator()(const tbb::blocked_range< size_t > &range)
Definition: LevelSetUtil.h:254
static TreeType & tree(TreeType &t)
Definition: Grid.h:897
InternalNodeType **const mMaskNodes
Definition: LevelSetUtil.h:226
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: LevelSetUtil.h:329
MaskInteriorVoxels(ValueType isovalue, const LeafNodeType **nodes, BoolLeafNodeType **maskNodes)
Definition: LevelSetUtil.h:163
TreeType::template ValueConverter< bool >::Type BoolTreeType
Definition: LevelSetUtil.h:1118
MaskInteriorTiles(ValueType isovalue, const TreeType &tree, InternalNodeType **maskNodes)
Definition: LevelSetUtil.h:209
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: LevelSetUtil.h:169
TreeType::ValueType ValueType
Definition: LevelSetUtil.h:207
Templated block class to hold specific data types and a fixed number of values determined by Log2Dim...
Definition: LeafNode.h:65
static BoolGridPtrType construct(const GridType &grid, BoolTreePtrType &maskTree)
Definition: LevelSetUtil.h:1123
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
math::Transform & transform()
Return a reference to this grid&#39;s transform, which might be shared with other grids.
Definition: Grid.h:335
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: LevelSetUtil.h:212
LabelBoundaryVoxels(ValueType isovalue, const LeafNodeType **nodes, CharLeafNodeType **maskNodes)
Definition: LevelSetUtil.h:282
void join(FindMinTileValue &rhs)
Definition: LevelSetUtil.h:402
BoolLeafNodeType **const mMaskNodes
Definition: LevelSetUtil.h:199
TreeType const *const mTree
Definition: LevelSetUtil.h:467
void operator()(const tbb::blocked_range< size_t > &range)
Definition: LevelSetUtil.h:359
LeafNodeType::ValueType ValueType
Definition: LevelSetUtil.h:160
LeafNodeType::ValueType ValueType
Definition: LevelSetUtil.h:279
void setOrigin(const Coord &origin)
Set the grid index coordinates of this node&#39;s local origin.
Definition: LeafNode.h:470
TreeType::LeafNodeType LeafNodeType
Definition: LevelSetUtil.h:476