1 // Copyright Contributors to the OpenVDB Project 2 // SPDX-License-Identifier: MPL-2.0 3 // 4 /// @file NodeVisitor.h 5 /// 6 /// @author Dan Bailey 7 /// 8 /// @brief Implementation of a depth-first node visitor. 9 /// 10 /// @note This algorithm is single-threaded by design and intended for rare 11 /// use cases where this is desirable. It is highly recommended to use 12 /// the NodeManager or DynamicNodeManager for much greater threaded 13 /// performance. 14 15 #ifndef OPENVDB_TOOLS_NODE_VISITOR_HAS_BEEN_INCLUDED 16 #define OPENVDB_TOOLS_NODE_VISITOR_HAS_BEEN_INCLUDED 17 18 #include <openvdb/version.h> 19 #include <openvdb/Types.h> 20 21 namespace openvdb { 22 OPENVDB_USE_VERSION_NAMESPACE 23 namespace OPENVDB_VERSION_NAME { 24 namespace tools { 25 26 /// @brief Visit all nodes in the tree depth-first and apply a user-supplied 27 /// functor to each node. 28 /// 29 /// @param tree tree to be visited. 30 /// @param op user-supplied functor, see examples for interface details. 31 /// @param idx optional offset to start sequential node indexing from a 32 /// non-zero index. 33 /// 34 /// @warning This method is single-threaded. Use the NodeManager or 35 /// DynamicNodeManager for much greater threaded performance. 36 /// 37 /// @par Example: 38 /// @code 39 /// Functor to offset all the active values of a tree. 40 /// struct OffsetOp 41 /// { 42 /// OffsetOp(float v): mOffset(v) { } 43 /// 44 /// template<typename NodeT> 45 /// void operator()(NodeT& node, size_t) const 46 /// { 47 /// for (auto iter = node.beginValueOn(); iter; ++iter) { 48 /// iter.setValue(iter.getValue() + mOffset); 49 /// } 50 /// } 51 /// private: 52 /// const float mOffset; 53 /// }; 54 /// 55 /// // usage: 56 /// OffsetOp op(3.0f); 57 /// visitNodesDepthFirst(tree, op); 58 /// 59 /// // Functor to offset all the active values of a tree. Note 60 /// // this implementation also illustrates how different 61 /// // computation can be applied to the different node types. 62 /// template<typename TreeT> 63 /// struct OffsetByLevelOp 64 /// { 65 /// using ValueT = typename TreeT::ValueType; 66 /// using RootT = typename TreeT::RootNodeType; 67 /// using LeafT = typename TreeT::LeafNodeType; 68 /// OffsetByLevelOp(const ValueT& v) : mOffset(v) {} 69 /// // Processes the root node. 70 /// void operator()(RootT& root, size_t) const 71 /// { 72 /// for (auto iter = root.beginValueOn(); iter; ++iter) { 73 /// iter.setValue(iter.getValue() + mOffset); 74 /// } 75 /// } 76 /// // Processes the leaf nodes. 77 /// void operator()(LeafT& leaf, size_t) const 78 /// { 79 /// for (auto iter = leaf.beginValueOn(); iter; ++iter) { 80 /// iter.setValue(iter.getValue() + mOffset); 81 /// } 82 /// } 83 /// // Processes the internal nodes. 84 /// template<typename NodeT> 85 /// void operator()(NodeT& node, size_t) const 86 /// { 87 /// for (auto iter = node.beginValueOn(); iter; ++iter) { 88 /// iter.setValue(iter.getValue() + mOffset); 89 /// } 90 /// } 91 /// private: 92 /// const ValueT mOffset; 93 /// }; 94 /// 95 /// // usage: 96 /// OffsetByLevelOp<FloatTree> op(3.0f); 97 /// visitNodesDepthFirst(tree, op); 98 /// 99 /// @endcode 100 /// 101 /// @par Here is an example when migrating from using the deprecated Tree::visit() 102 /// method. The main difference between the Tree::visit() method and this new 103 /// method is that the Tree::visit() method expected an object that can visit 104 /// tiles, values and nodes. In contrast, the visitNodesDepthFirst() method 105 /// visits only nodes and expects you to provide iteration over tiles and 106 /// voxels. 107 /// 108 /// @par Tree::visit() operator methods: 109 /// 110 /// @code 111 /// template <typename IterT> 112 /// bool operator()(IterT &iter) 113 /// { 114 /// typename IterT::NonConstValueType value; 115 /// typename IterT::ChildNodeType *child = iter.probeChild(value); 116 /// 117 /// if (child) 118 /// { 119 /// // If it is a leaf, process it now 120 /// if (child->getLevel() == 0) 121 /// { 122 /// processNode(*child); 123 /// return true; 124 /// } 125 /// // Otherwise, we want to keep digging down 126 /// return false; 127 /// } 128 /// 129 /// // No child, this is a constant node! 130 /// if (iter.isValueOn()) 131 /// { 132 /// openvdb::CoordBBox b; 133 /// b.min() = iter.getCoord(); 134 /// b.max() = b.min().offsetBy(IterT::ChildNodeType::DIM); 135 /// 136 /// processNodeBlock(b); 137 /// } 138 /// 139 /// // No need to dig further as there is no child. 140 /// return true; 141 /// } 142 /// 143 /// bool operator()(typename GridType::TreeType::LeafNodeType::ChildAllIter &) 144 /// { return true; } 145 /// bool operator()(typename GridType::TreeType::LeafNodeType::ChildAllCIter &) 146 /// { return true; } 147 /// 148 /// @endcode 149 /// 150 /// @par tools::visitNodesDepthFirst() operator methods: 151 /// 152 /// @code 153 /// using LeafT = typename GridType::TreeType::LeafNodeType; 154 /// 155 /// template <typename NodeT> 156 /// void operator()(const NodeT &node, size_t) 157 /// { 158 /// // iterate over active tiles 159 /// for (auto iter = node.beginValueOn(); iter; ++iter) 160 /// { 161 /// openvdb::CoordBBox b; 162 /// b.min() = iter.getCoord(); 163 /// b.max() = b.min().offsetBy(NodeT::ChildNodeType::DIM); 164 /// 165 /// processNodeBlock(b); 166 /// } 167 /// } 168 /// 169 /// void operator()(const LeafT &leaf, size_t) 170 /// { 171 /// processNode(leaf); 172 /// } 173 /// 174 /// @endcode 175 template <typename TreeT, typename OpT> 176 size_t visitNodesDepthFirst(TreeT& tree, OpT& op, size_t idx = 0); 177 178 179 /// @brief Visit all nodes that are downstream of a specific node in 180 /// depth-first order and apply a user-supplied functor to each node. 181 /// 182 /// @note This uses the same operator interface as documented in 183 /// visitNodesDepthFirst(). 184 /// 185 /// @note The LEVEL template argument can be used to reduce the traversal 186 /// depth. For example, calling visit() with a RootNode and using 187 /// NodeT::LEVEL-1 would not visit leaf nodes. 188 template <typename NodeT, Index LEVEL = NodeT::LEVEL> 189 struct DepthFirstNodeVisitor; 190 191 192 //////////////////////////////////////// 193 194 195 template <typename NodeT, Index LEVEL> 196 struct DepthFirstNodeVisitor 197 { 198 using NonConstChildType = typename NodeT::ChildNodeType; 199 using ChildNodeType = typename CopyConstness<NodeT, NonConstChildType>::Type; 200 201 template <typename OpT> 202 static size_t visit(NodeT& node, OpT& op, size_t idx = 0) 203 { 204 size_t offset = 0; 205 op(node, idx + offset++); 206 for (auto iter = node.beginChildOn(); iter; ++iter) { 207 offset += DepthFirstNodeVisitor<ChildNodeType>::visit( 208 *iter, op, idx + offset); 209 } 210 return offset; 211 } 212 }; 213 214 215 // terminate recursion 216 template <typename NodeT> 217 struct DepthFirstNodeVisitor<NodeT, 0> 218 { 219 template <typename OpT> 220 static size_t visit(NodeT& node, OpT& op, size_t idx = 0) 221 { 222 op(node, idx); 223 return size_t(1); 224 } 225 }; 226 227 228 template <typename TreeT, typename OpT> 229 size_t visitNodesDepthFirst(TreeT& tree, OpT& op, size_t idx) 230 { 231 using NonConstRootNodeType = typename TreeT::RootNodeType; 232 using RootNodeType = typename CopyConstness<TreeT, NonConstRootNodeType>::Type; 233 234 return DepthFirstNodeVisitor<RootNodeType>::visit(tree.root(), op, idx); 235 } 236 237 238 } // namespace tools 239 } // namespace OPENVDB_VERSION_NAME 240 } // namespace openvdb 241 242 #endif // OPENVDB_TOOLS_NODE_VISITOR_HAS_BEEN_INCLUDED 243