| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // Copyright Contributors to the OpenVDB Project | ||
| 2 | // SPDX-License-Identifier: MPL-2.0 | ||
| 3 | |||
| 4 | /// @file Clip.h | ||
| 5 | /// | ||
| 6 | /// @brief Functions to clip a grid against a bounding box, a camera frustum, | ||
| 7 | /// or another grid's active voxel topology | ||
| 8 | |||
| 9 | #ifndef OPENVDB_TOOLS_CLIP_HAS_BEEN_INCLUDED | ||
| 10 | #define OPENVDB_TOOLS_CLIP_HAS_BEEN_INCLUDED | ||
| 11 | |||
| 12 | #include <openvdb/Grid.h> | ||
| 13 | #include <openvdb/math/Math.h> // for math::isNegative() | ||
| 14 | #include <openvdb/math/Maps.h> // for math::NonlinearFrustumMap | ||
| 15 | #include <openvdb/tree/LeafManager.h> | ||
| 16 | #include <openvdb/points/PointDataGrid.h> | ||
| 17 | #include "GridTransformer.h" // for tools::resampleToMatch() | ||
| 18 | #include "Prune.h" | ||
| 19 | #include <tbb/blocked_range.h> | ||
| 20 | #include <tbb/parallel_reduce.h> | ||
| 21 | #include <type_traits> // for std::enable_if, std::is_same | ||
| 22 | #include <vector> | ||
| 23 | |||
| 24 | |||
| 25 | namespace openvdb { | ||
| 26 | OPENVDB_USE_VERSION_NAMESPACE | ||
| 27 | namespace OPENVDB_VERSION_NAME { | ||
| 28 | namespace tools { | ||
| 29 | |||
| 30 | /// @brief Clip the given grid against a world-space bounding box | ||
| 31 | /// and return a new grid containing the result. | ||
| 32 | /// @param grid the grid to be clipped | ||
| 33 | /// @param bbox a world-space bounding box | ||
| 34 | /// @param keepInterior if true, discard voxels that lie outside the bounding box; | ||
| 35 | /// if false, discard voxels that lie inside the bounding box | ||
| 36 | /// @warning Clipping a level set will likely produce a grid that is | ||
| 37 | /// no longer a valid level set. | ||
| 38 | template<typename GridType> | ||
| 39 | typename GridType::Ptr | ||
| 40 | clip(const GridType& grid, const BBoxd& bbox, bool keepInterior = true); | ||
| 41 | |||
| 42 | /// @brief Clip the given grid against a frustum and return a new grid containing the result. | ||
| 43 | /// @param grid the grid to be clipped | ||
| 44 | /// @param frustum a frustum map | ||
| 45 | /// @param keepInterior if true, discard voxels that lie outside the frustum; | ||
| 46 | /// if false, discard voxels that lie inside the frustum | ||
| 47 | /// @warning Clipping a level set will likely produce a grid that is | ||
| 48 | /// no longer a valid level set. | ||
| 49 | template<typename GridType> | ||
| 50 | typename GridType::Ptr | ||
| 51 | clip(const GridType& grid, const math::NonlinearFrustumMap& frustum, bool keepInterior = true); | ||
| 52 | |||
| 53 | /// @brief Clip a grid against the active voxels of another grid | ||
| 54 | /// and return a new grid containing the result. | ||
| 55 | /// @param grid the grid to be clipped | ||
| 56 | /// @param mask a grid whose active voxels form a boolean clipping mask | ||
| 57 | /// @param keepInterior if true, discard voxels that do not intersect the mask; | ||
| 58 | /// if false, discard voxels that intersect the mask | ||
| 59 | /// @details The mask grid need not have the same transform as the source grid. | ||
| 60 | /// Also, if the mask grid is a level set, consider using tools::sdfInteriorMask | ||
| 61 | /// to construct a new mask comprising the interior (rather than the narrow band) | ||
| 62 | /// of the level set. | ||
| 63 | /// @warning Clipping a level set will likely produce a grid that is | ||
| 64 | /// no longer a valid level set. | ||
| 65 | template<typename GridType, typename MaskTreeType> | ||
| 66 | typename GridType::Ptr | ||
| 67 | clip(const GridType& grid, const Grid<MaskTreeType>& mask, bool keepInterior = true); | ||
| 68 | |||
| 69 | |||
| 70 | //////////////////////////////////////// | ||
| 71 | |||
| 72 | /// @cond OPENVDB_DOCS_INTERNAL | ||
| 73 | |||
| 74 | namespace clip_internal { | ||
| 75 | |||
| 76 | // Use either MaskGrids or BoolGrids internally. | ||
| 77 | // (MaskGrids have a somewhat lower memory footprint.) | ||
| 78 | using MaskValueType = ValueMask; | ||
| 79 | //using MaskValueType = bool; | ||
| 80 | |||
| 81 | |||
| 82 | template<typename TreeT> | ||
| 83 | class MaskInteriorVoxels | ||
| 84 | { | ||
| 85 | public: | ||
| 86 | using ValueT = typename TreeT::ValueType; | ||
| 87 | using LeafNodeT = typename TreeT::LeafNodeType; | ||
| 88 | |||
| 89 | MaskInteriorVoxels(const TreeT& tree): mAcc(tree) {} | ||
| 90 | |||
| 91 | template<typename LeafNodeType> | ||
| 92 | ✗ | void operator()(LeafNodeType& leaf, size_t /*leafIndex*/) const | |
| 93 | { | ||
| 94 | ✗ | const auto* refLeaf = mAcc.probeConstLeaf(leaf.origin()); | |
| 95 | ✗ | if (refLeaf) { | |
| 96 | ✗ | for (auto iter = leaf.beginValueOff(); iter; ++iter) { | |
| 97 | const auto pos = iter.pos(); | ||
| 98 | ✗ | leaf.setActiveState(pos, math::isNegative(refLeaf->getValue(pos))); | |
| 99 | } | ||
| 100 | } | ||
| 101 | } | ||
| 102 | |||
| 103 | private: | ||
| 104 | tree::ValueAccessor<const TreeT> mAcc; | ||
| 105 | }; | ||
| 106 | |||
| 107 | |||
| 108 | //////////////////////////////////////// | ||
| 109 | |||
| 110 | |||
| 111 | template<typename TreeT> | ||
| 112 | 12 | class CopyLeafNodes | |
| 113 | { | ||
| 114 | public: | ||
| 115 | using MaskTreeT = typename TreeT::template ValueConverter<MaskValueType>::Type; | ||
| 116 | using MaskLeafManagerT = tree::LeafManager<const MaskTreeT>; | ||
| 117 | |||
| 118 | CopyLeafNodes(const TreeT&, const MaskLeafManagerT&); | ||
| 119 | |||
| 120 | void run(bool threaded = true); | ||
| 121 | |||
| 122 | typename TreeT::Ptr tree() const { return mNewTree; } | ||
| 123 | |||
| 124 | CopyLeafNodes(CopyLeafNodes&, tbb::split); | ||
| 125 | void operator()(const tbb::blocked_range<size_t>&); | ||
| 126 | 12 | void join(const CopyLeafNodes& rhs) { mNewTree->merge(*rhs.mNewTree); } | |
| 127 | |||
| 128 | private: | ||
| 129 | const MaskTreeT* mClipMask; | ||
| 130 | const TreeT* mTree; | ||
| 131 | const MaskLeafManagerT* mLeafNodes; | ||
| 132 | typename TreeT::Ptr mNewTree; | ||
| 133 | }; | ||
| 134 | |||
| 135 | |||
| 136 | template<typename TreeT> | ||
| 137 | 12 | CopyLeafNodes<TreeT>::CopyLeafNodes(const TreeT& tree, const MaskLeafManagerT& leafNodes) | |
| 138 | : mTree(&tree) | ||
| 139 | , mLeafNodes(&leafNodes) | ||
| 140 | 12 | , mNewTree(new TreeT(mTree->background())) | |
| 141 | { | ||
| 142 | } | ||
| 143 | |||
| 144 | |||
| 145 | template<typename TreeT> | ||
| 146 | 24 | CopyLeafNodes<TreeT>::CopyLeafNodes(CopyLeafNodes& rhs, tbb::split) | |
| 147 | 24 | : mTree(rhs.mTree) | |
| 148 | 24 | , mLeafNodes(rhs.mLeafNodes) | |
| 149 | 24 | , mNewTree(new TreeT(mTree->background())) | |
| 150 | { | ||
| 151 | } | ||
| 152 | |||
| 153 | |||
| 154 | template<typename TreeT> | ||
| 155 | void | ||
| 156 | 12 | CopyLeafNodes<TreeT>::run(bool threaded) | |
| 157 | { | ||
| 158 |
1/2✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
|
12 | if (threaded) tbb::parallel_reduce(mLeafNodes->getRange(), *this); |
| 159 | ✗ | else (*this)(mLeafNodes->getRange()); | |
| 160 | } | ||
| 161 | |||
| 162 | |||
| 163 | template<typename TreeT> | ||
| 164 | void | ||
| 165 | 248 | CopyLeafNodes<TreeT>::operator()(const tbb::blocked_range<size_t>& range) | |
| 166 | { | ||
| 167 | tree::ValueAccessor<TreeT> acc(*mNewTree); | ||
| 168 |
1/2✓ Branch 1 taken 124 times.
✗ Branch 2 not taken.
|
248 | tree::ValueAccessor<const TreeT> refAcc(*mTree); |
| 169 | |||
| 170 |
2/2✓ Branch 0 taken 124 times.
✓ Branch 1 taken 124 times.
|
496 | for (auto n = range.begin(); n != range.end(); ++n) { |
| 171 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 124 times.
|
248 | const auto& maskLeaf = mLeafNodes->leaf(n); |
| 172 | const auto& ijk = maskLeaf.origin(); | ||
| 173 | const auto* refLeaf = refAcc.probeConstLeaf(ijk); | ||
| 174 | |||
| 175 |
1/2✓ Branch 1 taken 124 times.
✗ Branch 2 not taken.
|
248 | auto* newLeaf = acc.touchLeaf(ijk); |
| 176 | |||
| 177 |
2/2✓ Branch 0 taken 112 times.
✓ Branch 1 taken 12 times.
|
248 | if (refLeaf) { |
| 178 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 112 times.
|
224 | for (auto it = maskLeaf.cbeginValueOn(); it; ++it) { |
| 179 | const auto pos = it.pos(); | ||
| 180 | ✗ | newLeaf->setValueOnly(pos, refLeaf->getValue(pos)); | |
| 181 | ✗ | newLeaf->setActiveState(pos, refLeaf->isValueOn(pos)); | |
| 182 | } | ||
| 183 | } else { | ||
| 184 | typename TreeT::ValueType value; | ||
| 185 |
1/2✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
|
24 | bool isActive = refAcc.probeValue(ijk, value); |
| 186 | |||
| 187 |
2/2✓ Branch 0 taken 78 times.
✓ Branch 1 taken 12 times.
|
180 | for (auto it = maskLeaf.cbeginValueOn(); it; ++it) { |
| 188 | const auto pos = it.pos(); | ||
| 189 |
1/2✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
|
156 | newLeaf->setValueOnly(pos, value); |
| 190 | 156 | newLeaf->setActiveState(pos, isActive); | |
| 191 | } | ||
| 192 | } | ||
| 193 | } | ||
| 194 | } | ||
| 195 | |||
| 196 | |||
| 197 | //////////////////////////////////////// | ||
| 198 | |||
| 199 | |||
| 200 | struct BoolSampler | ||
| 201 | { | ||
| 202 | static const char* name() { return "bin"; } | ||
| 203 | static int radius() { return 2; } | ||
| 204 | static bool mipmap() { return false; } | ||
| 205 | static bool consistent() { return true; } | ||
| 206 | |||
| 207 | template<class TreeT> | ||
| 208 | static bool sample(const TreeT& inTree, | ||
| 209 | const Vec3R& inCoord, typename TreeT::ValueType& result) | ||
| 210 | { | ||
| 211 | ✗ | return inTree.probeValue(Coord::floor(inCoord), result); | |
| 212 | } | ||
| 213 | }; | ||
| 214 | |||
| 215 | |||
| 216 | //////////////////////////////////////// | ||
| 217 | |||
| 218 | |||
| 219 | // Convert a grid of one type to a grid of another type | ||
| 220 | template<typename FromGridT, typename ToGridT> | ||
| 221 | struct ConvertGrid | ||
| 222 | { | ||
| 223 | using FromGridCPtrT = typename FromGridT::ConstPtr; | ||
| 224 | using ToGridPtrT = typename ToGridT::Ptr; | ||
| 225 | ToGridPtrT operator()(const FromGridCPtrT& grid) { return ToGridPtrT(new ToGridT(*grid)); } | ||
| 226 | }; | ||
| 227 | |||
| 228 | // Partial specialization that avoids copying when | ||
| 229 | // the input and output grid types are the same | ||
| 230 | template<typename GridT> | ||
| 231 | struct ConvertGrid<GridT, GridT> | ||
| 232 | { | ||
| 233 | using GridCPtrT = typename GridT::ConstPtr; | ||
| 234 | GridCPtrT operator()(const GridCPtrT& grid) { return grid; } | ||
| 235 | }; | ||
| 236 | |||
| 237 | |||
| 238 | //////////////////////////////////////// | ||
| 239 | |||
| 240 | |||
| 241 | // Convert a grid of arbitrary type to a mask grid with the same tree configuration | ||
| 242 | // and return a pointer to the new grid. | ||
| 243 | /// @private | ||
| 244 | template<typename GridT> | ||
| 245 | typename std::enable_if<!std::is_same<MaskValueType, typename GridT::BuildType>::value, | ||
| 246 | typename GridT::template ValueConverter<MaskValueType>::Type::Ptr>::type | ||
| 247 | 8 | convertToMaskGrid(const GridT& grid) | |
| 248 | { | ||
| 249 | using MaskGridT = typename GridT::template ValueConverter<MaskValueType>::Type; | ||
| 250 |
1/2✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
|
8 | auto mask = MaskGridT::create(/*background=*/false); |
| 251 | mask->topologyUnion(grid); | ||
| 252 |
2/6✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
|
8 | mask->setTransform(grid.constTransform().copy()); |
| 253 | 8 | return mask; | |
| 254 | } | ||
| 255 | |||
| 256 | // Overload that avoids any processing if the input grid is already a mask grid | ||
| 257 | /// @private | ||
| 258 | template<typename GridT> | ||
| 259 | typename std::enable_if<std::is_same<MaskValueType, typename GridT::BuildType>::value, | ||
| 260 | typename GridT::ConstPtr>::type | ||
| 261 | 1 | convertToMaskGrid(const GridT& grid) | |
| 262 | { | ||
| 263 | 1 | return grid.copy(); // shallow copy | |
| 264 | } | ||
| 265 | |||
| 266 | |||
| 267 | //////////////////////////////////////// | ||
| 268 | |||
| 269 | |||
| 270 | /// @private | ||
| 271 | template<typename GridType> | ||
| 272 | typename GridType::Ptr | ||
| 273 | 12 | doClip( | |
| 274 | const GridType& grid, | ||
| 275 | const typename GridType::template ValueConverter<MaskValueType>::Type& clipMask, | ||
| 276 | bool keepInterior) | ||
| 277 | { | ||
| 278 | using TreeT = typename GridType::TreeType; | ||
| 279 | using MaskTreeT = typename GridType::TreeType::template ValueConverter<MaskValueType>::Type; | ||
| 280 | |||
| 281 | 12 | const auto gridClass = grid.getGridClass(); | |
| 282 | const auto& tree = grid.tree(); | ||
| 283 | |||
| 284 |
1/2✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
|
24 | MaskTreeT gridMask(false); |
| 285 | gridMask.topologyUnion(tree); | ||
| 286 | |||
| 287 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
|
12 | if (gridClass == GRID_LEVEL_SET) { |
| 288 | ✗ | tree::LeafManager<MaskTreeT> leafNodes(gridMask); | |
| 289 | ✗ | leafNodes.foreach(MaskInteriorVoxels<TreeT>(tree)); | |
| 290 | |||
| 291 | tree::ValueAccessor<const TreeT> acc(tree); | ||
| 292 | |||
| 293 | ✗ | typename MaskTreeT::ValueAllIter iter(gridMask); | |
| 294 | ✗ | iter.setMaxDepth(MaskTreeT::ValueAllIter::LEAF_DEPTH - 1); | |
| 295 | |||
| 296 | ✗ | for ( ; iter; ++iter) { | |
| 297 | ✗ | iter.setActiveState(math::isNegative(acc.getValue(iter.getCoord()))); | |
| 298 | } | ||
| 299 | } | ||
| 300 | |||
| 301 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
|
12 | if (keepInterior) { |
| 302 | gridMask.topologyIntersection(clipMask.constTree()); | ||
| 303 | } else { | ||
| 304 | gridMask.topologyDifference(clipMask.constTree()); | ||
| 305 | } | ||
| 306 | |||
| 307 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
12 | auto outGrid = grid.copyWithNewTree(); |
| 308 | { | ||
| 309 | // Copy voxel values and states. | ||
| 310 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
24 | tree::LeafManager<const MaskTreeT> leafNodes(gridMask); |
| 311 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
12 | CopyLeafNodes<TreeT> maskOp(tree, leafNodes); |
| 312 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
12 | maskOp.run(); |
| 313 |
3/10✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 6 times.
✓ Branch 6 taken 6 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
|
24 | outGrid->setTree(maskOp.tree()); |
| 314 | } | ||
| 315 | { | ||
| 316 | // Copy tile values and states. | ||
| 317 | tree::ValueAccessor<const TreeT> refAcc(tree); | ||
| 318 | tree::ValueAccessor<const MaskTreeT> maskAcc(gridMask); | ||
| 319 | |||
| 320 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
12 | typename TreeT::ValueAllIter it(outGrid->tree()); |
| 321 | 12 | it.setMaxDepth(TreeT::ValueAllIter::LEAF_DEPTH - 1); | |
| 322 |
2/2✓ Branch 0 taken 884588 times.
✓ Branch 1 taken 6 times.
|
1769188 | for ( ; it; ++it) { |
| 323 | 1769176 | Coord ijk = it.getCoord(); | |
| 324 | |||
| 325 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 884588 times.
|
1769176 | if (maskAcc.isValueOn(ijk)) { |
| 326 | typename TreeT::ValueType value; | ||
| 327 | ✗ | bool isActive = refAcc.probeValue(ijk, value); | |
| 328 | |||
| 329 | it.setValue(value); | ||
| 330 | ✗ | if (!isActive) it.setValueOff(); | |
| 331 | } | ||
| 332 | } | ||
| 333 | } | ||
| 334 | |||
| 335 |
2/6✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
|
12 | outGrid->setTransform(grid.transform().copy()); |
| 336 |
2/4✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
|
12 | if (gridClass != GRID_LEVEL_SET) outGrid->setGridClass(gridClass); |
| 337 | |||
| 338 | 12 | return outGrid; | |
| 339 | } | ||
| 340 | |||
| 341 | } // namespace clip_internal | ||
| 342 | |||
| 343 | /// @endcond | ||
| 344 | |||
| 345 | |||
| 346 | //////////////////////////////////////// | ||
| 347 | |||
| 348 | |||
| 349 | /// @private | ||
| 350 | template<typename GridType> | ||
| 351 | typename GridType::Ptr | ||
| 352 | 2 | clip(const GridType& grid, const BBoxd& bbox, bool keepInterior) | |
| 353 | { | ||
| 354 | using MaskValueT = clip_internal::MaskValueType; | ||
| 355 | using MaskGridT = typename GridType::template ValueConverter<MaskValueT>::Type; | ||
| 356 | |||
| 357 | // Transform the world-space bounding box into the source grid's index space. | ||
| 358 | Vec3d idxMin, idxMax; | ||
| 359 | 2 | math::calculateBounds(grid.constTransform(), bbox.min(), bbox.max(), idxMin, idxMax); | |
| 360 | 2 | CoordBBox region(Coord::floor(idxMin), Coord::floor(idxMax)); | |
| 361 | // Construct a boolean mask grid that is true inside the index-space bounding box | ||
| 362 | // and false everywhere else. | ||
| 363 | 4 | MaskGridT clipMask(/*background=*/false); | |
| 364 |
1/2✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
|
2 | clipMask.fill(region, /*value=*/true, /*active=*/true); |
| 365 | |||
| 366 |
1/2✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
|
4 | return clip_internal::doClip(grid, clipMask, keepInterior); |
| 367 | } | ||
| 368 | |||
| 369 | |||
| 370 | /// @private | ||
| 371 | template<typename SrcGridType, typename ClipTreeType> | ||
| 372 | typename SrcGridType::Ptr | ||
| 373 | 5 | clip(const SrcGridType& srcGrid, const Grid<ClipTreeType>& clipGrid, bool keepInterior) | |
| 374 | { | ||
| 375 | using MaskValueT = clip_internal::MaskValueType; | ||
| 376 | using ClipGridType = Grid<ClipTreeType>; | ||
| 377 | using SrcMaskGridType = typename SrcGridType::template ValueConverter<MaskValueT>::Type; | ||
| 378 | using ClipMaskGridType = typename ClipGridType::template ValueConverter<MaskValueT>::Type; | ||
| 379 | |||
| 380 | // Convert the clipping grid to a boolean-valued mask grid with the same tree configuration. | ||
| 381 | 5 | auto maskGrid = clip_internal::convertToMaskGrid(clipGrid); | |
| 382 | |||
| 383 | // Resample the mask grid into the source grid's index space. | ||
| 384 | 5 | if (srcGrid.constTransform() != maskGrid->constTransform()) { | |
| 385 | ✗ | auto resampledMask = ClipMaskGridType::create(/*background=*/false); | |
| 386 | ✗ | resampledMask->setTransform(srcGrid.constTransform().copy()); | |
| 387 | ✗ | tools::resampleToMatch<clip_internal::BoolSampler>(*maskGrid, *resampledMask); | |
| 388 | ✗ | tools::prune(resampledMask->tree()); | |
| 389 | maskGrid = resampledMask; | ||
| 390 | } | ||
| 391 | |||
| 392 | // Convert the mask grid to a mask grid with the same tree configuration as the source grid. | ||
| 393 | 4 | auto clipMask = clip_internal::ConvertGrid< | |
| 394 | /*from=*/ClipMaskGridType, /*to=*/SrcMaskGridType>()(maskGrid); | ||
| 395 | |||
| 396 | // Clip the source grid against the mask grid. | ||
| 397 | 10 | return clip_internal::doClip(srcGrid, *clipMask, keepInterior); | |
| 398 | } | ||
| 399 | |||
| 400 | |||
| 401 | /// @private | ||
| 402 | template<typename GridType> | ||
| 403 | typename GridType::Ptr | ||
| 404 | 3 | clip(const GridType& inGrid, const math::NonlinearFrustumMap& frustumMap, bool keepInterior) | |
| 405 | { | ||
| 406 | using ValueT = typename GridType::ValueType; | ||
| 407 | using TreeT = typename GridType::TreeType; | ||
| 408 | using LeafT = typename TreeT::LeafNodeType; | ||
| 409 | |||
| 410 | const auto& gridXform = inGrid.transform(); | ||
| 411 | 3 | const auto frustumIndexBBox = frustumMap.getBBox(); | |
| 412 | |||
| 413 | // Return true if index-space point (i,j,k) lies inside the frustum. | ||
| 414 | 2114691 | auto frustumContainsCoord = [&](const Coord& ijk) -> bool { | |
| 415 | auto xyz = gridXform.indexToWorld(ijk); | ||
| 416 | 2114688 | xyz = frustumMap.applyInverseMap(xyz); | |
| 417 | 2114688 | return frustumIndexBBox.isInside(xyz); | |
| 418 | }; | ||
| 419 | |||
| 420 | // Return the frustum index-space bounding box of the corners of | ||
| 421 | // the given grid index-space bounding box. | ||
| 422 | 1116325 | auto toFrustumIndexSpace = [&](const CoordBBox& inBBox) -> BBoxd { | |
| 423 | 65666 | const Coord bounds[2] = { inBBox.min(), inBBox.max() }; | |
| 424 | Coord ijk; | ||
| 425 | BBoxd outBBox; | ||
| 426 |
2/20✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 525328 times.
✓ Branch 9 taken 65666 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
|
590994 | for (int i = 0; i < 8; ++i) { |
| 427 | 525328 | ijk[0] = bounds[(i & 1) >> 0][0]; | |
| 428 | 525328 | ijk[1] = bounds[(i & 2) >> 1][1]; | |
| 429 | 525328 | ijk[2] = bounds[(i & 4) >> 2][2]; | |
| 430 | auto xyz = gridXform.indexToWorld(ijk); | ||
| 431 | 525328 | xyz = frustumMap.applyInverseMap(xyz); | |
| 432 | 525328 | outBBox.expand(xyz); | |
| 433 | } | ||
| 434 | 65666 | return outBBox; | |
| 435 | }; | ||
| 436 | |||
| 437 | // Construct an output grid with the same transform and metadata as the input grid. | ||
| 438 | 3 | auto outGrid = inGrid.copyWithNewTree(); | |
| 439 | 3 | if (outGrid->getGridClass() == GRID_LEVEL_SET) { | |
| 440 | // After clipping, a level set grid might no longer be a valid SDF. | ||
| 441 | ✗ | outGrid->setGridClass(GRID_UNKNOWN); | |
| 442 | } | ||
| 443 | |||
| 444 | const auto& bg = outGrid->background(); | ||
| 445 | |||
| 446 | auto outAcc = outGrid->getAccessor(); | ||
| 447 | |||
| 448 | // Copy active and inactive tiles that intersect the clipping region | ||
| 449 | // from the input grid to the output grid. | ||
| 450 | // ("Clipping region" refers to either the interior or the exterior | ||
| 451 | // of the frustum, depending on the value of keepInterior.) | ||
| 452 | auto tileIter = inGrid.beginValueAll(); | ||
| 453 | 3 | tileIter.setMaxDepth(GridType::ValueAllIter::LEAF_DEPTH - 1); | |
| 454 | 3 | CoordBBox tileBBox; | |
| 455 | 360387 | for ( ; tileIter; ++tileIter) { | |
| 456 | const bool tileActive = tileIter.isValueOn(); | ||
| 457 | const auto& tileValue = tileIter.getValue(); | ||
| 458 | |||
| 459 | // Skip background tiles. | ||
| 460 | 360384 | if (!tileActive && math::isApproxEqual(tileValue, bg)) continue; | |
| 461 | |||
| 462 | // Transform the tile's bounding box into frustum index space. | ||
| 463 | 10 | tileIter.getBoundingBox(tileBBox); | |
| 464 | 10 | const auto tileFrustumBBox = toFrustumIndexSpace(tileBBox); | |
| 465 | |||
| 466 | // Determine whether any or all of the tile intersects the clipping region. | ||
| 467 | enum class CopyTile { kNone, kPartial, kFull }; | ||
| 468 | auto copyTile = CopyTile::kNone; | ||
| 469 | 10 | if (keepInterior) { | |
| 470 | 9 | if (frustumIndexBBox.isInside(tileFrustumBBox)) { | |
| 471 | copyTile = CopyTile::kFull; | ||
| 472 | 9 | } else if (frustumIndexBBox.hasOverlap(tileFrustumBBox)) { | |
| 473 | copyTile = CopyTile::kPartial; | ||
| 474 | } | ||
| 475 | } else { | ||
| 476 | 1 | if (!frustumIndexBBox.hasOverlap(tileFrustumBBox)) { | |
| 477 | copyTile = CopyTile::kFull; | ||
| 478 | 1 | } else if (!frustumIndexBBox.isInside(tileFrustumBBox)) { | |
| 479 | copyTile = CopyTile::kPartial; | ||
| 480 | } | ||
| 481 | } | ||
| 482 | switch (copyTile) { | ||
| 483 | case CopyTile::kNone: | ||
| 484 | break; | ||
| 485 | ✗ | case CopyTile::kFull: | |
| 486 | // Copy the entire tile. | ||
| 487 | ✗ | outAcc.addTile(tileIter.getLevel(), tileBBox.min(), tileValue, tileActive); | |
| 488 | break; | ||
| 489 | 10 | case CopyTile::kPartial: | |
| 490 | // Copy only voxels inside the clipping region. | ||
| 491 | 131200 | for (std::vector<CoordBBox> bboxVec = { tileBBox }; !bboxVec.empty(); ) { | |
| 492 | // For efficiency, subdivide sufficiently large tiles and discard | ||
| 493 | // subregions based on additional bounding box intersection tests. | ||
| 494 | // The mimimum subregion size is chosen so that cost of the | ||
| 495 | // bounding box test is comparable to testing every voxel. | ||
| 496 | 131190 | if (bboxVec.back().volume() > 64 && bboxVec.back().is_divisible()) { | |
| 497 | // Subdivide this region in-place and append the other half to the list. | ||
| 498 | 65590 | bboxVec.emplace_back(bboxVec.back(), tbb::split{}); | |
| 499 | 98348 | continue; | |
| 500 | } | ||
| 501 | 65600 | auto subBBox = bboxVec.back(); | |
| 502 | bboxVec.pop_back(); | ||
| 503 | |||
| 504 | // Discard the subregion if it lies completely outside the clipping region. | ||
| 505 | 65600 | if (keepInterior) { | |
| 506 | 32832 | if (!frustumIndexBBox.hasOverlap(toFrustumIndexSpace(subBBox))) continue; | |
| 507 | } else { | ||
| 508 | 32768 | if (frustumIndexBBox.isInside(toFrustumIndexSpace(subBBox))) continue; | |
| 509 | } | ||
| 510 | |||
| 511 | // Test every voxel within the subregion. | ||
| 512 | 2134730 | for (const auto& ijk: subBBox) { | |
| 513 | 2101888 | if (frustumContainsCoord(ijk) == keepInterior) { | |
| 514 | 2099576 | if (tileActive) { | |
| 515 | outAcc.setValueOn(ijk, tileValue); | ||
| 516 | } else { | ||
| 517 | ✗ | outAcc.setValueOff(ijk, tileValue); | |
| 518 | } | ||
| 519 | } | ||
| 520 | } | ||
| 521 | } | ||
| 522 | 10 | break; | |
| 523 | } | ||
| 524 | } | ||
| 525 | 3 | tools::prune(outGrid->tree()); | |
| 526 | |||
| 527 | // Ensure that the output grid has the same leaf node topology as the input grid, | ||
| 528 | // with the exception of leaf nodes that lie completely outside the clipping region. | ||
| 529 | // (This operation is serial.) | ||
| 530 | 59 | for (auto leafIter = inGrid.constTree().beginLeaf(); leafIter; ++leafIter) { | |
| 531 | 56 | const auto leafBBox = leafIter->getNodeBoundingBox(); | |
| 532 | 56 | const auto leafFrustumBBox = toFrustumIndexSpace(leafBBox); | |
| 533 | 56 | if (keepInterior) { | |
| 534 | 56 | if (frustumIndexBBox.hasOverlap(leafFrustumBBox)) { | |
| 535 | 13 | outAcc.touchLeaf(leafBBox.min()); | |
| 536 | } | ||
| 537 | } else { | ||
| 538 | ✗ | if (!frustumIndexBBox.hasOverlap(leafFrustumBBox) | |
| 539 | ✗ | || !frustumIndexBBox.isInside(leafFrustumBBox)) | |
| 540 | { | ||
| 541 | ✗ | outAcc.touchLeaf(leafBBox.min()); | |
| 542 | } | ||
| 543 | } | ||
| 544 | } | ||
| 545 | |||
| 546 | // In parallel across output leaf nodes, copy leaf voxels | ||
| 547 | // from the input grid to the output grid. | ||
| 548 | 3 | tree::LeafManager<TreeT> outLeafNodes{outGrid->tree()}; | |
| 549 | 3 | outLeafNodes.foreach( | |
| 550 | 50 | [&](LeafT& leaf, size_t /*idx*/) { | |
| 551 | auto inAcc = inGrid.getConstAccessor(); | ||
| 552 | ValueT val; | ||
| 553 |
2/20✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 13 taken 12800 times.
✓ Branch 14 taken 25 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
|
12850 | for (auto voxelIter = leaf.beginValueAll(); voxelIter; ++voxelIter) { |
| 554 |
1/20✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 13 taken 12800 times.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
|
12800 | const auto ijk = voxelIter.getCoord(); |
| 555 |
3/40✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✓ Branch 21 taken 12800 times.
✗ Branch 22 not taken.
✓ Branch 23 taken 3894 times.
✓ Branch 24 taken 8906 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
|
12800 | if (frustumContainsCoord(ijk) == keepInterior) { |
| 556 |
1/16✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 13 taken 3894 times.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
|
3894 | const bool active = inAcc.probeValue(ijk, val); |
| 557 |
1/18✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 13 taken 3894 times.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
|
3894 | voxelIter.setValue(val); |
| 558 |
1/18✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 13 taken 3894 times.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
|
3894 | voxelIter.setValueOn(active); |
| 559 | } | ||
| 560 | } | ||
| 561 | } | ||
| 562 | ); | ||
| 563 | |||
| 564 | 3 | return outGrid; | |
| 565 | } | ||
| 566 | |||
| 567 | |||
| 568 | //////////////////////////////////////// | ||
| 569 | |||
| 570 | |||
| 571 | // Explicit Template Instantiation | ||
| 572 | |||
| 573 | #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION | ||
| 574 | |||
| 575 | #ifdef OPENVDB_INSTANTIATE_CLIP | ||
| 576 | #include <openvdb/util/ExplicitInstantiation.h> | ||
| 577 | #endif | ||
| 578 | |||
| 579 | #define _FUNCTION(TreeT) \ | ||
| 580 | Grid<TreeT>::Ptr clip(const Grid<TreeT>&, const BBoxd&, bool) | ||
| 581 | OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION) | ||
| 582 | #undef _FUNCTION | ||
| 583 | |||
| 584 | #define _FUNCTION(TreeT) \ | ||
| 585 | Grid<TreeT>::Ptr clip(const Grid<TreeT>&, const math::NonlinearFrustumMap&, bool) | ||
| 586 | OPENVDB_ALL_TREE_INSTANTIATE(_FUNCTION) | ||
| 587 | #undef _FUNCTION | ||
| 588 | |||
| 589 | #define _FUNCTION(TreeT) \ | ||
| 590 | Grid<TreeT>::Ptr clip_internal::doClip(const Grid<TreeT>&, const MaskGrid&, bool) | ||
| 591 | OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION) | ||
| 592 | #undef _FUNCTION | ||
| 593 | |||
| 594 | #endif // OPENVDB_USE_EXPLICIT_INSTANTIATION | ||
| 595 | |||
| 596 | |||
| 597 | } // namespace tools | ||
| 598 | } // namespace OPENVDB_VERSION_NAME | ||
| 599 | } // namespace openvdb | ||
| 600 | |||
| 601 | #endif // OPENVDB_TOOLS_CLIP_HAS_BEEN_INCLUDED | ||
| 602 |