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