GCC Code Coverage Report

Directory: ./
File: openvdb/openvdb/tools/NodeVisitor.h
Date: 2022-07-25 17:40:05
Exec Total Coverage
Lines: 8 8 100.0%
Functions: 26 40 65.0%
Branches: 5 11 45.5%
Line Branch Exec Source
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
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 8 times.
 256 static size_t visit(NodeT& node, OpT& op, size_t idx = 0)
203 {
204 size_t offset = 0;
205 118 op(node, idx + offset++);
206
3/3
✓ Branch 0 taken 10178 times.
✓ Branch 1 taken 170 times.
✓ Branch 2 taken 6 times.
 20722 for (auto iter = node.beginChildOn(); iter; ++iter) {
207 26114 offset += DepthFirstNodeVisitor<ChildNodeType>::visit(
208 *iter, op, idx + offset);
209 }
210 256 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
0/6
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
 2831 op(node, idx);
223 return size_t(1);
224 }
225 };
226
227
228 template <typename TreeT, typename OpT>
229 7 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 7 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