HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
TopologyToLevelSet.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 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 //
29 ///////////////////////////////////////////////////////////////////////////
30 //
31 /// @file TopologyToLevelSet.h
32 ///
33 /// @brief This tool generates a narrow-band signed distance field / level set
34 /// from the interface between active and inactive voxels in a vdb grid.
35 ///
36 /// @par Example:
37 /// Combine with @c tools::PointsToVolume for fast point cloud to level set conversion.
38 
39 #ifndef OPENVDB_TOOLS_TOPOLOGY_TO_LEVELSET_HAS_BEEN_INCLUDED
40 #define OPENVDB_TOOLS_TOPOLOGY_TO_LEVELSET_HAS_BEEN_INCLUDED
41 
42 #include "LevelSetFilter.h"
43 #include "Morphology.h" // for erodeVoxels and dilateActiveValues
44 #include "SignedFloodFill.h"
45 
46 #include <openvdb/Grid.h>
47 #include <openvdb/Types.h>
48 #include <openvdb/math/FiniteDifference.h> // for math::BiasedGradientScheme
50 #include <tbb/task_group.h>
51 #include <algorithm> // for std::min(), std::max()
52 #include <vector>
53 
54 
55 namespace openvdb {
57 namespace OPENVDB_VERSION_NAME {
58 namespace tools {
59 
60 
61 /// @brief Compute the narrow-band signed distance to the interface between
62 /// active and inactive voxels in the input grid.
63 ///
64 /// @return A shared pointer to a new sdf / level set grid of type @c float
65 ///
66 /// @param grid Input grid of arbitrary type whose active voxels are used
67 /// in constructing the level set.
68 /// @param halfWidth Half the width of the narrow band in voxel units.
69 /// @param closingSteps Number of morphological closing steps used to fill gaps
70 /// in the active voxel region.
71 /// @param dilation Number of voxels to expand the active voxel region.
72 /// @param smoothingSteps Number of smoothing interations.
73 template<typename GridT>
74 inline typename GridT::template ValueConverter<float>::Type::Ptr
75 topologyToLevelSet(const GridT& grid, int halfWidth = 3, int closingSteps = 1, int dilation = 0,
76  int smoothingSteps = 0);
77 
78 
79 /// @brief Compute the narrow-band signed distance to the interface between
80 /// active and inactive voxels in the input grid.
81 ///
82 /// @return A shared pointer to a new sdf / level set grid of type @c float
83 ///
84 /// @param grid Input grid of arbitrary type whose active voxels are used
85 /// in constructing the level set.
86 /// @param halfWidth Half the width of the narrow band in voxel units.
87 /// @param closingSteps Number of morphological closing steps used to fill gaps
88 /// in the active voxel region.
89 /// @param dilation Number of voxels to expand the active voxel region.
90 /// @param smoothingSteps Number of smoothing interations.
91 /// @param interrupt Optional object adhering to the util::NullInterrupter interface.
92 template<typename GridT, typename InterrupterT>
93 inline typename GridT::template ValueConverter<float>::Type::Ptr
94 topologyToLevelSet(const GridT& grid, int halfWidth = 3, int closingSteps = 1, int dilation = 0,
95  int smoothingSteps = 0, InterrupterT* interrupt = nullptr);
96 
97 
98 ////////////////////////////////////////
99 
100 
101 namespace ttls_internal {
102 
103 
104 template<typename TreeT>
105 struct DilateOp
106 {
107  DilateOp(TreeT& t, int n) : tree(&t), size(n) {}
108  void operator()() const {
110  }
111  TreeT* tree;
112  const int size;
113 };
114 
115 
116 template<typename TreeT>
117 struct ErodeOp
118 {
119  ErodeOp(TreeT& t, int n) : tree(&t), size(n) {}
120  void operator()() const { erodeVoxels( *tree, size); }
121  TreeT* tree;
122  const int size;
123 };
124 
125 
126 template<typename TreeType>
128 {
129  using LeafNodeType = typename TreeType::LeafNodeType;
130  using ValueType = typename TreeType::ValueType;
131 
132  OffsetAndMinComp(std::vector<LeafNodeType*>& lhsNodes,
133  const TreeType& rhsTree, ValueType offset)
134  : mLhsNodes(lhsNodes.empty() ? nullptr : &lhsNodes[0]), mRhsTree(&rhsTree), mOffset(offset)
135  {
136  }
137 
138  void operator()(const tbb::blocked_range<size_t>& range) const
139  {
140  using Iterator = typename LeafNodeType::ValueOnIter;
141 
142  tree::ValueAccessor<const TreeType> rhsAcc(*mRhsTree);
143  const ValueType offset = mOffset;
144 
145  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
146 
147  LeafNodeType& lhsNode = *mLhsNodes[n];
148  const LeafNodeType * rhsNodePt = rhsAcc.probeConstLeaf(lhsNode.origin());
149  if (!rhsNodePt) continue;
150 
151  for (Iterator it = lhsNode.beginValueOn(); it; ++it) {
152  ValueType& val = const_cast<ValueType&>(it.getValue());
153  val = std::min(val, offset + rhsNodePt->getValue(it.pos()));
154  }
155  }
156  }
157 
158 private:
159  LeafNodeType * * const mLhsNodes;
160  TreeType const * const mRhsTree;
161  ValueType const mOffset;
162 }; // struct OffsetAndMinComp
163 
164 
165 template<typename GridType, typename InterrupterType>
166 inline void
167 normalizeLevelSet(GridType& grid, const int halfWidthInVoxels, InterrupterType* interrupt = nullptr)
168 {
171  filter.setNormCount(halfWidthInVoxels);
172  filter.normalize();
173  filter.prune();
174 }
175 
176 
177 template<typename GridType, typename InterrupterType>
178 inline void
179 smoothLevelSet(GridType& grid, int iterations, int halfBandWidthInVoxels,
180  InterrupterType* interrupt = nullptr)
181 {
182  using ValueType = typename GridType::ValueType;
183  using TreeType = typename GridType::TreeType;
184  using LeafNodeType = typename TreeType::LeafNodeType;
185 
186  GridType filterGrid(grid);
187 
190 
191  for (int n = 0; n < iterations; ++n) {
192  if (interrupt && interrupt->wasInterrupted()) break;
193  filter.mean(1);
194  }
195 
196  std::vector<LeafNodeType*> nodes;
197  grid.tree().getNodes(nodes);
198 
199  const ValueType offset = ValueType(double(0.5) * grid.transform().voxelSize()[0]);
200 
201  tbb::parallel_for(tbb::blocked_range<size_t>(0, nodes.size()),
202  OffsetAndMinComp<TreeType>(nodes, filterGrid.tree(), -offset));
203 
204  // Clean up any damanage that was done by the min operation
205  normalizeLevelSet(grid, halfBandWidthInVoxels, interrupt);
206 }
207 
208 
209 } // namespace ttls_internal
210 
211 
212 
213 template<typename GridT, typename InterrupterT>
214 inline typename GridT::template ValueConverter<float>::Type::Ptr
215 topologyToLevelSet(const GridT& grid, int halfWidth, int closingSteps, int dilation,
216  int smoothingSteps, InterrupterT* interrupt)
217 {
218  using MaskTreeT = typename GridT::TreeType::template ValueConverter<ValueMask>::Type;
219  using FloatTreeT = typename GridT::TreeType::template ValueConverter<float>::Type;
220  using FloatGridT = Grid<FloatTreeT>;
221 
222  // Check inputs
223 
224  halfWidth = std::max(halfWidth, 1);
225  closingSteps = std::max(closingSteps, 0);
226  dilation = std::max(dilation, 0);
227 
228  if (!grid.hasUniformVoxels()) {
229  OPENVDB_THROW(ValueError, "Non-uniform voxels are not supported!");
230  }
231 
232  // Copy the topology into a MaskGrid.
233  MaskTreeT maskTree( grid.tree(), false/*background*/, openvdb::TopologyCopy() );
234 
235  // Morphological closing operation.
236  dilateActiveValues( maskTree, closingSteps + dilation, tools::NN_FACE, tools::IGNORE_TILES );
237  erodeVoxels( maskTree, closingSteps );
238 
239  // Generate a volume with an implicit zero crossing at the boundary
240  // between active and inactive values in the input grid.
241  const float background = float(grid.voxelSize()[0]) * float(halfWidth);
242  typename FloatTreeT::Ptr lsTree(
243  new FloatTreeT( maskTree, /*out=*/background, /*in=*/-background, openvdb::TopologyCopy() ) );
244 
245  tbb::task_group pool;
246  pool.run( ttls_internal::ErodeOp< MaskTreeT >( maskTree, halfWidth ) );
247  pool.run( ttls_internal::DilateOp<FloatTreeT>( *lsTree , halfWidth ) );
248  pool.wait();// wait for both tasks to complete
249 
250  lsTree->topologyDifference( maskTree );
251  tools::pruneLevelSet( *lsTree, /*threading=*/true);
252 
253  // Create a level set grid from the tree
254  typename FloatGridT::Ptr lsGrid = FloatGridT::create( lsTree );
255  lsGrid->setTransform( grid.transform().copy() );
256  lsGrid->setGridClass( openvdb::GRID_LEVEL_SET );
257 
258  // Use a PDE based scheme to propagate distance values from the
259  // implicit zero crossing.
260  ttls_internal::normalizeLevelSet(*lsGrid, 3*halfWidth, interrupt);
261 
262  // Additional filtering
263  if (smoothingSteps > 0) {
264  ttls_internal::smoothLevelSet(*lsGrid, smoothingSteps, halfWidth, interrupt);
265  }
266 
267  return lsGrid;
268 }
269 
270 
271 template<typename GridT>
272 inline typename GridT::template ValueConverter<float>::Type::Ptr
273 topologyToLevelSet(const GridT& grid, int halfWidth, int closingSteps, int dilation, int smoothingSteps)
274 {
275  util::NullInterrupter interrupt;
276  return topologyToLevelSet(grid, halfWidth, closingSteps, dilation, smoothingSteps, &interrupt);
277 }
278 
279 
280 } // namespace tools
281 } // namespace OPENVDB_VERSION_NAME
282 } // namespace openvdb
283 
284 #endif // OPENVDB_TOOLS_TOPOLOGY_TO_LEVELSET_HAS_BEEN_INCLUDED
285 
286 
287 // Copyright (c) DreamWorks Animation LLC
288 // All rights reserved. This software is distributed under the
289 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
vint4 max(const vint4 &a, const vint4 &b)
Definition: simd.h:4703
void parallel_for(int64_t start, int64_t end, std::function< void(int64_t index)> &&task, parallel_options opt=parallel_options(0, Split_Y, 1))
Definition: parallel.h:153
GLenum GLint * range
Definition: glew.h:3500
GLsizeiptr size
Definition: glew.h:1681
Filtering (e.g. diffusion) of narrow-band level sets. An optional scalar field can be used to produce...
void prune()
Set voxels that are outside the narrow band to the background value (if trimming is enabled) and prun...
*Note that the tasks the is the thread number *for the pool
Definition: thread.h:655
void mean(int width=1, const MaskType *mask=nullptr)
One iteration of mean-value flow of the level set.
GLuint const GLfloat * val
Definition: glew.h:2794
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:200
Dummy NOOP interrupter class defining interface.
void setNormCount(int n)
Set the number of normalizations performed per track or normalize call.
SYS_FORCE_INLINE const_iterator end() const
GLint GLint GLint GLint GLint GLint GLint GLbitfield GLenum filter
Definition: glew.h:2981
const LeafNodeT * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z), or nullptr if no such node exists...
OffsetAndMinComp(std::vector< LeafNodeType * > &lhsNodes, const TreeType &rhsTree, ValueType offset)
GLsizei n
Definition: glew.h:4040
void normalizeLevelSet(GridType &grid, const int halfWidthInVoxels, InterrupterType *interrupt=nullptr)
void setSpatialScheme(math::BiasedGradientScheme s)
Set the spatial finite difference scheme.
Container class that associates a tree with a transform and metadata.
Definition: Grid.h:55
Propagate the signs of distance values from the active voxels in the narrow band to the inactive valu...
OPENVDB_STATIC_SPECIALIZATION void erodeVoxels(TreeType &tree, int iterations=1, NearestNeighbors nn=NN_FACE)
Topologically erode all leaf-level active voxels in the given tree.
Definition: Morphology.h:880
GridT::template ValueConverter< float >::Type::Ptr topologyToLevelSet(const GridT &grid, int halfWidth=3, int closingSteps=1, int dilation=0, int smoothingSteps=0)
Compute the narrow-band signed distance to the interface between active and inactive voxels in the in...
GA_API const UT_StringHolder N
void smoothLevelSet(GridType &grid, int iterations, int halfBandWidthInVoxels, InterrupterType *interrupt=nullptr)
Implementation of morphological dilation and erosion.
Performs various types of level set deformations with interface tracking. These unrestricted deformat...
vint4 min(const vint4 &a, const vint4 &b)
Definition: simd.h:4694
void pruneLevelSet(TreeT &tree, bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing nodes whose values are all inactive with inactive ...
Definition: Prune.h:416
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:146
void normalize(const MaskType *mask)
Iterative normalization, i.e. solving the Eikonal equation.
GLdouble GLdouble t
Definition: glew.h:1398
OPENVDB_STATIC_SPECIALIZATION void dilateActiveValues(TreeType &tree, int iterations=1, NearestNeighbors nn=NN_FACE, TilePolicy mode=PRESERVE_TILES)
Topologically dilate all active values (i.e. both voxels and tiles) in a tree using one of three near...
Definition: Morphology.h:1081
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:109
GLintptr offset
Definition: glew.h:1682
void operator()(const tbb::blocked_range< size_t > &range) const