OpenVDB  9.0.1
NodeVisitor.h
Go to the documentation of this file.
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 {
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>
190 
191 
192 ////////////////////////////////////////
193 
194 
195 template <typename NodeT, Index LEVEL>
197 {
198  using NonConstChildType = typename NodeT::ChildNodeType;
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) {
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
static size_t visit(NodeT &node, OpT &op, size_t idx=0)
Definition: NodeVisitor.h:220
Visit all nodes that are downstream of a specific node in depth-first order and apply a user-supplied...
Definition: NodeVisitor.h:189
size_t visitNodesDepthFirst(TreeT &tree, OpT &op, size_t idx=0)
Visit all nodes in the tree depth-first and apply a user-supplied functor to each node...
Definition: NodeVisitor.h:229
typename NodeT::ChildNodeType NonConstChildType
Definition: NodeVisitor.h:198
typename CopyConstness< NodeT, NonConstChildType >::Type ChildNodeType
Definition: NodeVisitor.h:199
Definition: Exceptions.h:13
static size_t visit(NodeT &node, OpT &op, size_t idx=0)
Definition: NodeVisitor.h:202
typename std::remove_const< ToType >::type Type
Definition: Types.h:400
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:202