| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // Copyright Contributors to the OpenVDB Project | ||
| 2 | // SPDX-License-Identifier: MPL-2.0 | ||
| 3 | // | ||
| 4 | /// @file Prune.h | ||
| 5 | /// | ||
| 6 | /// @brief Defined various multi-threaded utility functions for trees | ||
| 7 | /// | ||
| 8 | /// @author Ken Museth | ||
| 9 | |||
| 10 | #ifndef OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED | ||
| 11 | #define OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED | ||
| 12 | |||
| 13 | #include <openvdb/math/Math.h> // for isNegative and negative | ||
| 14 | #include <openvdb/Types.h> | ||
| 15 | #include <openvdb/tree/NodeManager.h> | ||
| 16 | #include <openvdb/openvdb.h> | ||
| 17 | #include <algorithm> // for std::nth_element() | ||
| 18 | #include <type_traits> | ||
| 19 | |||
| 20 | namespace openvdb { | ||
| 21 | OPENVDB_USE_VERSION_NAMESPACE | ||
| 22 | namespace OPENVDB_VERSION_NAME { | ||
| 23 | namespace tools { | ||
| 24 | |||
| 25 | /// @brief Reduce the memory footprint of a @a tree by replacing with tiles | ||
| 26 | /// any nodes whose values are all the same (optionally to within a tolerance) | ||
| 27 | /// and have the same active state. | ||
| 28 | /// | ||
| 29 | /// @note For trees with non-boolean values a child node with (approximately) | ||
| 30 | /// constant values are replaced with a tile value corresponding to the median | ||
| 31 | /// of the values in said child node. | ||
| 32 | /// | ||
| 33 | /// @param tree the tree to be pruned | ||
| 34 | /// @param tolerance tolerance within which values are considered to be equal | ||
| 35 | /// @param threaded enable or disable threading (threading is enabled by default) | ||
| 36 | /// @param grainSize used to control the threading granularity (default is 1) | ||
| 37 | template<typename TreeT> | ||
| 38 | void | ||
| 39 | prune(TreeT& tree, | ||
| 40 | typename TreeT::ValueType tolerance = zeroVal<typename TreeT::ValueType>(), | ||
| 41 | bool threaded = true, | ||
| 42 | size_t grainSize = 1); | ||
| 43 | |||
| 44 | |||
| 45 | /// @brief Reduce the memory footprint of a @a tree by replacing with tiles | ||
| 46 | /// any non-leaf nodes whose values are all the same (optionally to within a tolerance) | ||
| 47 | /// and have the same active state. | ||
| 48 | /// | ||
| 49 | /// @param tree the tree to be pruned | ||
| 50 | /// @param tolerance tolerance within which values are considered to be equal | ||
| 51 | /// @param threaded enable or disable threading (threading is enabled by default) | ||
| 52 | /// @param grainSize used to control the threading granularity (default is 1) | ||
| 53 | template<typename TreeT> | ||
| 54 | void | ||
| 55 | pruneTiles(TreeT& tree, | ||
| 56 | typename TreeT::ValueType tolerance = zeroVal<typename TreeT::ValueType>(), | ||
| 57 | bool threaded = true, | ||
| 58 | size_t grainSize = 1); | ||
| 59 | |||
| 60 | |||
| 61 | /// @brief Reduce the memory footprint of a @a tree by replacing with | ||
| 62 | /// background tiles any nodes whose values are all inactive. | ||
| 63 | /// | ||
| 64 | /// @param tree the tree to be pruned | ||
| 65 | /// @param threaded enable or disable threading (threading is enabled by default) | ||
| 66 | /// @param grainSize used to control the threading granularity (default is 1) | ||
| 67 | template<typename TreeT> | ||
| 68 | void | ||
| 69 | pruneInactive(TreeT& tree, bool threaded = true, size_t grainSize = 1); | ||
| 70 | |||
| 71 | |||
| 72 | /// @brief Reduce the memory footprint of a @a tree by replacing any nodes | ||
| 73 | /// whose values are all inactive with tiles of the given @a value. | ||
| 74 | /// | ||
| 75 | /// @param tree the tree to be pruned | ||
| 76 | /// @param value value assigned to inactive tiles created during pruning | ||
| 77 | /// @param threaded enable or disable threading (threading is enabled by default) | ||
| 78 | /// @param grainSize used to control the threading granularity (default is 1) | ||
| 79 | template<typename TreeT> | ||
| 80 | void | ||
| 81 | pruneInactiveWithValue( | ||
| 82 | TreeT& tree, | ||
| 83 | const typename TreeT::ValueType& value, | ||
| 84 | bool threaded = true, | ||
| 85 | size_t grainSize = 1); | ||
| 86 | |||
| 87 | |||
| 88 | /// @brief Reduce the memory footprint of a @a tree by replacing nodes | ||
| 89 | /// whose values are all inactive with inactive tiles having a value equal to | ||
| 90 | /// the first value encountered in the (inactive) child. | ||
| 91 | /// @details This method is faster than tolerance-based prune and | ||
| 92 | /// useful for narrow-band level set applications where inactive | ||
| 93 | /// values are limited to either an inside or an outside value. | ||
| 94 | /// | ||
| 95 | /// @param tree the tree to be pruned | ||
| 96 | /// @param threaded enable or disable threading (threading is enabled by default) | ||
| 97 | /// @param grainSize used to control the threading granularity (default is 1) | ||
| 98 | /// | ||
| 99 | /// @throw ValueError if the background of the @a tree is negative (as defined by math::isNegative) | ||
| 100 | template<typename TreeT> | ||
| 101 | void | ||
| 102 | pruneLevelSet(TreeT& tree, | ||
| 103 | bool threaded = true, | ||
| 104 | size_t grainSize = 1); | ||
| 105 | |||
| 106 | |||
| 107 | /// @brief Reduce the memory footprint of a @a tree by replacing nodes whose voxel values | ||
| 108 | /// are all inactive with inactive tiles having the value -| @a insideWidth | | ||
| 109 | /// if the voxel values are negative and | @a outsideWidth | otherwise. | ||
| 110 | /// | ||
| 111 | /// @details This method is faster than tolerance-based prune and | ||
| 112 | /// useful for narrow-band level set applications where inactive | ||
| 113 | /// values are limited to either an inside or an outside value. | ||
| 114 | /// | ||
| 115 | /// @param tree the tree to be pruned | ||
| 116 | /// @param outsideWidth the width of the outside of the narrow band | ||
| 117 | /// @param insideWidth the width of the inside of the narrow band | ||
| 118 | /// @param threaded enable or disable threading (threading is enabled by default) | ||
| 119 | /// @param grainSize used to control the threading granularity (default is 1) | ||
| 120 | /// | ||
| 121 | /// @throw ValueError if @a outsideWidth is negative or @a insideWidth is | ||
| 122 | /// not negative (as defined by math::isNegative). | ||
| 123 | template<typename TreeT> | ||
| 124 | void | ||
| 125 | pruneLevelSet(TreeT& tree, | ||
| 126 | const typename TreeT::ValueType& outsideWidth, | ||
| 127 | const typename TreeT::ValueType& insideWidth, | ||
| 128 | bool threaded = true, | ||
| 129 | size_t grainSize = 1); | ||
| 130 | |||
| 131 | |||
| 132 | //////////////////////////////////////////////// | ||
| 133 | |||
| 134 | |||
| 135 | template<typename TreeT, Index TerminationLevel = 0> | ||
| 136 | class InactivePruneOp | ||
| 137 | { | ||
| 138 | public: | ||
| 139 | using ValueT = typename TreeT::ValueType; | ||
| 140 | using RootT = typename TreeT::RootNodeType; | ||
| 141 | using LeafT = typename TreeT::LeafNodeType; | ||
| 142 | static_assert(RootT::LEVEL > TerminationLevel, "TerminationLevel out of range"); | ||
| 143 | |||
| 144 | 4514 | InactivePruneOp(TreeT& tree) : mValue(tree.background()) | |
| 145 | { | ||
| 146 |
7/16✓ Branch 1 taken 3354 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 13 taken 1088 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 12 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 35 times.
✗ Branch 20 not taken.
✓ Branch 22 taken 18 times.
✗ Branch 23 not taken.
|
4514 | tree.clearAllAccessors();//clear cache of nodes that could be pruned |
| 147 | 4514 | } | |
| 148 | |||
| 149 | ✗ | InactivePruneOp(TreeT& tree, const ValueT& v) : mValue(v) | |
| 150 | { | ||
| 151 | ✗ | tree.clearAllAccessors();//clear cache of nodes that could be pruned | |
| 152 | } | ||
| 153 | |||
| 154 | // Nothing to do at the leaf node level | ||
| 155 | void operator()(LeafT&) const {} | ||
| 156 | |||
| 157 | // Prune the child nodes of the internal nodes | ||
| 158 | template<typename NodeT> | ||
| 159 | 28198 | void operator()(NodeT& node) const | |
| 160 | { | ||
| 161 | if (NodeT::LEVEL > TerminationLevel) { | ||
| 162 |
2/2✓ Branch 0 taken 78564 times.
✓ Branch 1 taken 14099 times.
|
185326 | for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) { |
| 163 |
2/2✓ Branch 0 taken 11052 times.
✓ Branch 1 taken 67480 times.
|
157082 | if (it->isInactive()) node.addTile(it.pos(), mValue, false); |
| 164 | } | ||
| 165 | } | ||
| 166 | 28198 | } | |
| 167 | |||
| 168 | // Prune the child nodes of the root node | ||
| 169 | 5674 | void operator()(RootT& root) const | |
| 170 | { | ||
| 171 |
2/2✓ Branch 1 taken 7026 times.
✓ Branch 2 taken 4514 times.
|
21470 | for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) { |
| 172 |
2/2✓ Branch 0 taken 1455 times.
✓ Branch 1 taken 5571 times.
|
10122 | if (it->isInactive()) root.addTile(it.getCoord(), mValue, false); |
| 173 | } | ||
| 174 | 5674 | root.eraseBackgroundTiles(); | |
| 175 | 5674 | } | |
| 176 | |||
| 177 | private: | ||
| 178 | const ValueT mValue; | ||
| 179 | };// InactivePruneOp | ||
| 180 | |||
| 181 | |||
| 182 | template<typename TreeT, Index TerminationLevel = 0> | ||
| 183 | class TolerancePruneOp | ||
| 184 | { | ||
| 185 | public: | ||
| 186 | using ValueT = typename TreeT::ValueType; | ||
| 187 | using RootT = typename TreeT::RootNodeType; | ||
| 188 | using LeafT = typename TreeT::LeafNodeType; | ||
| 189 | static_assert(RootT::LEVEL > TerminationLevel, "TerminationLevel out of range"); | ||
| 190 | |||
| 191 | 193 | TolerancePruneOp(TreeT& tree, const ValueT& tol) : mTolerance(tol) | |
| 192 | { | ||
| 193 |
11/32✓ Branch 1 taken 67 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 13 taken 22 times.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✓ Branch 22 taken 2 times.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✓ Branch 28 taken 10 times.
✗ Branch 29 not taken.
✓ Branch 31 taken 8 times.
✗ Branch 32 not taken.
✓ Branch 34 taken 8 times.
✗ Branch 35 not taken.
✓ Branch 37 taken 49 times.
✗ Branch 38 not taken.
✓ Branch 40 taken 8 times.
✗ Branch 41 not taken.
✓ Branch 43 taken 8 times.
✗ Branch 44 not taken.
✓ Branch 46 taken 10 times.
✗ Branch 47 not taken.
|
193 | tree.clearAllAccessors();//clear cache of nodes that could be pruned |
| 194 | 193 | } | |
| 195 | |||
| 196 | // Prune the child nodes of the root node | ||
| 197 | 320 | inline void operator()(RootT& root) const | |
| 198 | { | ||
| 199 | ValueT value; | ||
| 200 | bool state; | ||
| 201 |
2/2✓ Branch 1 taken 949 times.
✓ Branch 2 taken 193 times.
|
2179 | for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) { |
| 202 |
3/3✓ Branch 0 taken 64 times.
✓ Branch 1 taken 362 times.
✓ Branch 2 taken 523 times.
|
1539 | if (this->isConstant(*it, value, state)) root.addTile(it.getCoord(), value, state); |
| 203 | } | ||
| 204 | 320 | root.eraseBackgroundTiles(); | |
| 205 | 320 | } | |
| 206 | |||
| 207 | // Prune the child nodes of the internal nodes | ||
| 208 | template<typename NodeT> | ||
| 209 | 4706 | inline void operator()(NodeT& node) const | |
| 210 | { | ||
| 211 | if (NodeT::LEVEL > TerminationLevel) { | ||
| 212 | ValueT value; | ||
| 213 | bool state; | ||
| 214 |
2/2✓ Branch 0 taken 41656 times.
✓ Branch 1 taken 2353 times.
|
88018 | for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) { |
| 215 |
5/5✓ Branch 0 taken 692 times.
✓ Branch 1 taken 37021 times.
✓ Branch 2 taken 735 times.
✓ Branch 3 taken 15441 times.
✓ Branch 4 taken 19550 times.
|
78316 | if (this->isConstant(*it, value, state)) node.addTile(it.pos(), value, state); |
| 216 | } | ||
| 217 | } | ||
| 218 | 4706 | } | |
| 219 | |||
| 220 | // Nothing to do at the leaf node level | ||
| 221 | inline void operator()(LeafT&) const {} | ||
| 222 | |||
| 223 | private: | ||
| 224 | // Private method specialized for leaf nodes | ||
| 225 | 15441 | inline ValueT median(LeafT& leaf) const {return leaf.medianAll(leaf.buffer().data());} | |
| 226 | |||
| 227 | // Private method for internal nodes | ||
| 228 | template<typename NodeT> | ||
| 229 | inline typename NodeT::ValueType median(NodeT& node) const | ||
| 230 | { | ||
| 231 | using UnionT = typename NodeT::UnionType; | ||
| 232 | UnionT* data = const_cast<UnionT*>(node.getTable());//never do this at home kids :) | ||
| 233 | static const size_t midpoint = (NodeT::NUM_VALUES - 1) >> 1; | ||
| 234 |
24/184✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 296 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 18352 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 18352 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 1480 times.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 1480 times.
✗ Branch 16 not taken.
✓ Branch 17 taken 296 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✓ Branch 25 taken 1 times.
✗ Branch 26 not taken.
✓ Branch 27 taken 510 times.
✗ Branch 28 not taken.
✓ Branch 29 taken 510 times.
✗ Branch 30 not taken.
✓ Branch 31 taken 8 times.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✓ Branch 35 taken 8 times.
✗ Branch 36 not taken.
✓ Branch 37 taken 1 times.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✓ Branch 59 taken 9 times.
✗ Branch 60 not taken.
✓ Branch 61 taken 36846 times.
✗ Branch 62 not taken.
✓ Branch 63 taken 36846 times.
✗ Branch 64 not taken.
✓ Branch 65 taken 99 times.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✓ Branch 69 taken 99 times.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 81 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 102 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✓ Branch 105 taken 9 times.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 108 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✗ Branch 111 not taken.
✗ Branch 112 not taken.
✗ Branch 113 not taken.
✗ Branch 114 not taken.
✗ Branch 115 not taken.
✗ Branch 119 not taken.
✗ Branch 120 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 123 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 126 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 132 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 135 not taken.
✗ Branch 136 not taken.
✗ Branch 137 not taken.
✗ Branch 162 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✗ Branch 165 not taken.
✗ Branch 166 not taken.
✗ Branch 167 not taken.
✗ Branch 168 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
✗ Branch 172 not taken.
✗ Branch 173 not taken.
✗ Branch 174 not taken.
✓ Branch 175 taken 9 times.
✗ Branch 176 not taken.
✓ Branch 177 taken 294894 times.
✗ Branch 178 not taken.
✓ Branch 179 taken 294894 times.
✗ Branch 180 not taken.
✓ Branch 181 taken 126 times.
✗ Branch 182 not taken.
✗ Branch 183 not taken.
✗ Branch 184 not taken.
✓ Branch 185 taken 126 times.
✗ Branch 186 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 189 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 192 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 195 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 198 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 201 not taken.
✗ Branch 202 not taken.
✗ Branch 203 not taken.
✗ Branch 204 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 207 not taken.
✗ Branch 208 not taken.
✗ Branch 209 not taken.
✗ Branch 216 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✗ Branch 219 not taken.
✗ Branch 220 not taken.
✓ Branch 221 taken 9 times.
✗ Branch 222 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 225 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 228 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 231 not taken.
|
703547 | auto op = [](const UnionT& a, const UnionT& b){return a.getValue() < b.getValue();}; |
| 235 | 315 | std::nth_element(data, data + midpoint, data + NodeT::NUM_VALUES, op); | |
| 236 | 315 | return data[midpoint].getValue(); | |
| 237 | } | ||
| 238 | |||
| 239 | // Specialization to nodes templated on booleans values | ||
| 240 | template<typename NodeT> | ||
| 241 | inline | ||
| 242 | typename std::enable_if<std::is_same<bool, typename NodeT::ValueType>::value, bool>::type | ||
| 243 | isConstant(NodeT& node, bool& value, bool& state) const | ||
| 244 | { | ||
| 245 | 2833 | return node.isConstant(value, state, mTolerance); | |
| 246 | } | ||
| 247 | |||
| 248 | // Nodes templated on non-boolean values | ||
| 249 | template<typename NodeT> | ||
| 250 | inline | ||
| 251 | typename std::enable_if<!std::is_same<bool, typename NodeT::ValueType>::value, bool>::type | ||
| 252 | 73128 | isConstant(NodeT& node, ValueT& value, bool& state) const | |
| 253 | { | ||
| 254 | ValueT tmp; | ||
| 255 | 73128 | const bool test = node.isConstant(value, tmp, state, mTolerance); | |
| 256 |
2/2✓ Branch 0 taken 15756 times.
✓ Branch 1 taken 20808 times.
|
104640 | if (test) value = this->median(node); |
| 257 | 73128 | return test; | |
| 258 | } | ||
| 259 | |||
| 260 | const ValueT mTolerance; | ||
| 261 | };// TolerancePruneOp | ||
| 262 | |||
| 263 | |||
| 264 | template<typename TreeT, Index TerminationLevel = 0> | ||
| 265 | class LevelSetPruneOp | ||
| 266 | { | ||
| 267 | public: | ||
| 268 | using ValueT = typename TreeT::ValueType; | ||
| 269 | using RootT = typename TreeT::RootNodeType; | ||
| 270 | using LeafT = typename TreeT::LeafNodeType; | ||
| 271 | static_assert(RootT::LEVEL > TerminationLevel, "TerminationLevel out of range"); | ||
| 272 | |||
| 273 | 233 | LevelSetPruneOp(TreeT& tree) | |
| 274 | : mOutside(tree.background()) | ||
| 275 |
1/3✗ Branch 0 not taken.
✓ Branch 1 taken 119 times.
✗ Branch 2 not taken.
|
233 | , mInside(math::negative(mOutside)) |
| 276 | { | ||
| 277 |
1/3✗ Branch 0 not taken.
✓ Branch 1 taken 119 times.
✗ Branch 2 not taken.
|
233 | if (math::isNegative(mOutside)) { |
| 278 | ✗ | OPENVDB_THROW(ValueError, | |
| 279 | "LevelSetPruneOp: the background value cannot be negative!"); | ||
| 280 | } | ||
| 281 |
0/2✗ Branch 1 not taken.
✗ Branch 2 not taken.
|
233 | tree.clearAllAccessors();//clear cache of nodes that could be pruned |
| 282 | 233 | } | |
| 283 | |||
| 284 | 64 | LevelSetPruneOp(TreeT& tree, const ValueT& outside, const ValueT& inside) | |
| 285 | : mOutside(outside) | ||
| 286 | 64 | , mInside(inside) | |
| 287 | { | ||
| 288 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
|
64 | if (math::isNegative(mOutside)) { |
| 289 | ✗ | OPENVDB_THROW(ValueError, | |
| 290 | "LevelSetPruneOp: the outside value cannot be negative!"); | ||
| 291 | } | ||
| 292 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
|
64 | if (!math::isNegative(mInside)) { |
| 293 | ✗ | OPENVDB_THROW(ValueError, | |
| 294 | "LevelSetPruneOp: the inside value must be negative!"); | ||
| 295 | } | ||
| 296 | 64 | tree.clearAllAccessors();//clear cache of nodes that could be pruned | |
| 297 | } | ||
| 298 | |||
| 299 | // Nothing to do at the leaf node level | ||
| 300 | void operator()(LeafT&) const {} | ||
| 301 | |||
| 302 | // Prune the child nodes of the internal nodes | ||
| 303 | template<typename NodeT> | ||
| 304 | 2686 | void operator()(NodeT& node) const | |
| 305 | { | ||
| 306 | if (NodeT::LEVEL > TerminationLevel) { | ||
| 307 |
2/2✓ Branch 0 taken 89135 times.
✓ Branch 1 taken 1343 times.
|
180956 | for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) { |
| 308 |
2/2✓ Branch 0 taken 898 times.
✓ Branch 1 taken 88237 times.
|
178270 | if (it->isInactive()) node.addTile(it.pos(), this->getTileValue(it), false); |
| 309 | } | ||
| 310 | } | ||
| 311 | 2686 | } | |
| 312 | |||
| 313 | // Prune the child nodes of the root node | ||
| 314 | 297 | void operator()(RootT& root) const | |
| 315 | { | ||
| 316 |
2/2✓ Branch 1 taken 578 times.
✓ Branch 2 taken 151 times.
|
1730 | for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) { |
| 317 |
2/2✓ Branch 0 taken 18 times.
✓ Branch 1 taken 560 times.
|
1172 | if (it->isInactive()) root.addTile(it.getCoord(), this->getTileValue(it), false); |
| 318 | } | ||
| 319 | 297 | root.eraseBackgroundTiles(); | |
| 320 | 297 | } | |
| 321 | |||
| 322 | private: | ||
| 323 | template <typename IterT> | ||
| 324 | 1796 | inline ValueT getTileValue(const IterT& iter) const | |
| 325 | { | ||
| 326 |
4/7✓ Branch 1 taken 176 times.
✓ Branch 2 taken 704 times.
✓ Branch 3 taken 18 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 18 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
3574 | return math::isNegative(iter->getFirstValue()) ? mInside : mOutside; |
| 327 | } | ||
| 328 | |||
| 329 | const ValueT mOutside, mInside; | ||
| 330 | };// LevelSetPruneOp | ||
| 331 | |||
| 332 | |||
| 333 | template<typename TreeT> | ||
| 334 | void | ||
| 335 | 272 | prune(TreeT& tree, typename TreeT::ValueType tol, bool threaded, size_t grainSize) | |
| 336 | { | ||
| 337 | 544 | tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree); | |
| 338 | TolerancePruneOp<TreeT> op(tree, tol); | ||
| 339 |
1/2✓ Branch 1 taken 169 times.
✗ Branch 2 not taken.
|
272 | nodes.foreachBottomUp(op, threaded, grainSize); |
| 340 | 272 | } | |
| 341 | |||
| 342 | |||
| 343 | template<typename TreeT> | ||
| 344 | void | ||
| 345 | 48 | pruneTiles(TreeT& tree, typename TreeT::ValueType tol, bool threaded, size_t grainSize) | |
| 346 | { | ||
| 347 | 48 | tree::NodeManager<TreeT, TreeT::DEPTH-3> nodes(tree); | |
| 348 | TolerancePruneOp<TreeT> op(tree, tol); | ||
| 349 |
1/2✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
|
48 | nodes.foreachBottomUp(op, threaded, grainSize); |
| 350 | } | ||
| 351 | |||
| 352 | |||
| 353 | template<typename TreeT> | ||
| 354 | void | ||
| 355 | 5674 | pruneInactive(TreeT& tree, bool threaded, size_t grainSize) | |
| 356 | { | ||
| 357 | 11348 | tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree); | |
| 358 | InactivePruneOp<TreeT> op(tree); | ||
| 359 |
1/2✓ Branch 1 taken 4514 times.
✗ Branch 2 not taken.
|
5674 | nodes.foreachBottomUp(op, threaded, grainSize); |
| 360 | 5674 | } | |
| 361 | |||
| 362 | |||
| 363 | template<typename TreeT> | ||
| 364 | void | ||
| 365 | ✗ | pruneInactiveWithValue(TreeT& tree, const typename TreeT::ValueType& v, | |
| 366 | bool threaded, size_t grainSize) | ||
| 367 | { | ||
| 368 | ✗ | tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree); | |
| 369 | InactivePruneOp<TreeT> op(tree, v); | ||
| 370 | ✗ | nodes.foreachBottomUp(op, threaded, grainSize); | |
| 371 | } | ||
| 372 | |||
| 373 | |||
| 374 | template<typename TreeT> | ||
| 375 | void | ||
| 376 | 64 | pruneLevelSet(TreeT& tree, | |
| 377 | const typename TreeT::ValueType& outside, | ||
| 378 | const typename TreeT::ValueType& inside, | ||
| 379 | bool threaded, | ||
| 380 | size_t grainSize) | ||
| 381 | { | ||
| 382 | 128 | tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree); | |
| 383 |
1/2✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
|
64 | LevelSetPruneOp<TreeT> op(tree, outside, inside); |
| 384 |
1/2✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
|
64 | nodes.foreachBottomUp(op, threaded, grainSize); |
| 385 | } | ||
| 386 | |||
| 387 | |||
| 388 | template<typename TreeT> | ||
| 389 | void | ||
| 390 | 233 | pruneLevelSet(TreeT& tree, bool threaded, size_t grainSize) | |
| 391 | { | ||
| 392 | 466 | tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree); | |
| 393 |
1/2✓ Branch 1 taken 119 times.
✗ Branch 2 not taken.
|
233 | LevelSetPruneOp<TreeT> op(tree); |
| 394 |
1/2✓ Branch 1 taken 119 times.
✗ Branch 2 not taken.
|
233 | nodes.foreachBottomUp(op, threaded, grainSize); |
| 395 | 233 | } | |
| 396 | |||
| 397 | |||
| 398 | //////////////////////////////////////// | ||
| 399 | |||
| 400 | |||
| 401 | // Explicit Template Instantiation | ||
| 402 | |||
| 403 | #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION | ||
| 404 | |||
| 405 | #ifdef OPENVDB_INSTANTIATE_PRUNE | ||
| 406 | #include <openvdb/util/ExplicitInstantiation.h> | ||
| 407 | #endif | ||
| 408 | |||
| 409 | #define _FUNCTION(TreeT) \ | ||
| 410 | void prune(TreeT&, TreeT::ValueType, bool, size_t) | ||
| 411 | OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION) | ||
| 412 | #undef _FUNCTION | ||
| 413 | |||
| 414 | #define _FUNCTION(TreeT) \ | ||
| 415 | void pruneTiles(TreeT&, TreeT::ValueType, bool, size_t) | ||
| 416 | OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION) | ||
| 417 | #undef _FUNCTION | ||
| 418 | |||
| 419 | #define _FUNCTION(TreeT) \ | ||
| 420 | void pruneInactive(TreeT&, bool, size_t) | ||
| 421 | OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION) | ||
| 422 | #undef _FUNCTION | ||
| 423 | |||
| 424 | #define _FUNCTION(TreeT) \ | ||
| 425 | void pruneInactiveWithValue(TreeT&, const TreeT::ValueType&, bool, size_t) | ||
| 426 | OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION) | ||
| 427 | #undef _FUNCTION | ||
| 428 | |||
| 429 | #define _FUNCTION(TreeT) \ | ||
| 430 | void pruneLevelSet(TreeT&, bool, size_t) | ||
| 431 | OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION) | ||
| 432 | #undef _FUNCTION | ||
| 433 | |||
| 434 | #define _FUNCTION(TreeT) \ | ||
| 435 | void pruneLevelSet(TreeT&, const TreeT::ValueType&, const TreeT::ValueType&, bool, size_t) | ||
| 436 | OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION) | ||
| 437 | #undef _FUNCTION | ||
| 438 | |||
| 439 | #endif // OPENVDB_USE_EXPLICIT_INSTANTIATION | ||
| 440 | |||
| 441 | |||
| 442 | } // namespace tools | ||
| 443 | } // namespace OPENVDB_VERSION_NAME | ||
| 444 | } // namespace openvdb | ||
| 445 | |||
| 446 | #endif // OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED | ||
| 447 |