[Bf-blender-cvs] [4202a208c2d] functions: compute dependency depths in network implementation
Jacques Lucke
noreply at git.blender.org
Mon Jan 27 22:10:05 CET 2020
Commit: 4202a208c2d68d22ddfe23cfcbe5ff63578eadcb
Author: Jacques Lucke
Date: Sun Jan 26 20:39:41 2020 +0100
Branches: functions
https://developer.blender.org/rB4202a208c2d68d22ddfe23cfcbe5ff63578eadcb
compute dependency depths in network implementation
===================================================================
M source/blender/functions/FN_multi_function_network.h
M source/blender/functions/intern/multi_function_network.cc
M source/blender/functions/intern/multi_functions/network.cc
===================================================================
diff --git a/source/blender/functions/FN_multi_function_network.h b/source/blender/functions/FN_multi_function_network.h
index ea4fe4c545b..c7ef567ed31 100644
--- a/source/blender/functions/FN_multi_function_network.h
+++ b/source/blender/functions/FN_multi_function_network.h
@@ -286,6 +286,8 @@ class MFNode : BLI::NonCopyable, BLI::NonMovable {
const MFFunctionNode &as_function() const;
const MFDummyNode &as_dummy() const;
+
+ template<typename FuncT> void foreach_origin_node(const FuncT &func) const;
};
class MFFunctionNode final : public MFNode {
@@ -376,6 +378,8 @@ class MFNetwork : BLI::NonCopyable, BLI::NonMovable {
Vector<MFInputSocket *> m_input_sockets;
Vector<MFOutputSocket *> m_output_sockets;
+ Array<uint> m_max_dependency_depth_per_node;
+
public:
MFNetwork(MFNetworkBuilder &builder);
~MFNetwork();
@@ -385,15 +389,8 @@ class MFNetwork : BLI::NonCopyable, BLI::NonMovable {
IndexRange socket_ids() const;
IndexRange node_ids() const;
- ArrayRef<const MFDummyNode *> dummy_nodes() const
- {
- return m_dummy_nodes.as_ref();
- }
-
- ArrayRef<const MFFunctionNode *> function_nodes() const
- {
- return m_function_nodes.as_ref();
- }
+ ArrayRef<const MFDummyNode *> dummy_nodes() const;
+ ArrayRef<const MFFunctionNode *> function_nodes() const;
Vector<const MFOutputSocket *> find_dummy_dependencies(
ArrayRef<const MFInputSocket *> sockets) const;
@@ -401,6 +398,8 @@ class MFNetwork : BLI::NonCopyable, BLI::NonMovable {
Vector<const MFFunctionNode *> find_function_dependencies(
ArrayRef<const MFInputSocket *> sockets) const;
+ ArrayRef<uint> max_dependency_depth_per_node() const;
+
private:
void create_links_to_node(MFNetworkBuilder &builder,
MFNode *to_node,
@@ -409,6 +408,8 @@ class MFNetwork : BLI::NonCopyable, BLI::NonMovable {
void create_link_to_socket(MFNetworkBuilder &builder,
MFInputSocket *to_socket,
MFBuilderInputSocket *to_builder_socket);
+
+ void compute_max_dependency_depths();
};
/* Builder Implementations
@@ -660,6 +661,15 @@ inline const MFDummyNode &MFNode::as_dummy() const
return *(const MFDummyNode *)this;
}
+template<typename FuncT> void MFNode::foreach_origin_node(const FuncT &func) const
+{
+ for (const MFInputSocket *socket : m_inputs) {
+ const MFOutputSocket &origin_socket = socket->origin();
+ const MFNode &origin_node = origin_socket.node();
+ func(origin_node);
+ }
+}
+
inline const MultiFunction &MFFunctionNode::function() const
{
return *m_function;
@@ -786,6 +796,21 @@ inline IndexRange MFNetwork::node_ids() const
return IndexRange(m_node_by_id.size());
}
+inline ArrayRef<const MFDummyNode *> MFNetwork::dummy_nodes() const
+{
+ return m_dummy_nodes.as_ref();
+}
+
+inline ArrayRef<const MFFunctionNode *> MFNetwork::function_nodes() const
+{
+ return m_function_nodes.as_ref();
+}
+
+inline ArrayRef<uint> MFNetwork::max_dependency_depth_per_node() const
+{
+ return m_max_dependency_depth_per_node;
+}
+
} // namespace FN
#endif /* __FN_MULTI_FUNCTION_NETWORK_H__ */
diff --git a/source/blender/functions/intern/multi_function_network.cc b/source/blender/functions/intern/multi_function_network.cc
index b1086681265..ef089f451f4 100644
--- a/source/blender/functions/intern/multi_function_network.cc
+++ b/source/blender/functions/intern/multi_function_network.cc
@@ -468,6 +468,8 @@ MFNetwork::MFNetwork(MFNetworkBuilder &builder)
MFBuilderDummyNode *to_builder_node = builder_dummy_nodes[node_index];
this->create_links_to_node(builder, to_node, to_builder_node);
}
+
+ this->compute_max_dependency_depths();
}
void MFNetwork::create_links_to_node(MFNetworkBuilder &builder,
@@ -509,6 +511,47 @@ void MFNetwork::create_link_to_socket(MFNetworkBuilder &builder,
to_socket->m_origin = from_socket;
}
+BLI_NOINLINE void MFNetwork::compute_max_dependency_depths()
+{
+ m_max_dependency_depth_per_node = Array<uint>(m_node_by_id.size(), UINT32_MAX);
+ Array<uint> &max_depths = m_max_dependency_depth_per_node;
+
+ for (const MFDummyNode *node : this->dummy_nodes()) {
+ max_depths[node->id()] = 0;
+ }
+
+ Stack<const MFNode *> nodes_to_check;
+ nodes_to_check.push_multiple(this->function_nodes());
+
+ while (!nodes_to_check.is_empty()) {
+ const MFNode ¤t = *nodes_to_check.peek();
+ if (max_depths[current.id()] != UINT32_MAX) {
+ nodes_to_check.pop();
+ continue;
+ }
+
+ bool all_inputs_computed = true;
+ uint max_incoming_depth = 0;
+ current.foreach_origin_node([&](const MFNode &origin_node) {
+ uint origin_depth = max_depths[origin_node.id()];
+ if (origin_depth == UINT32_MAX) {
+ nodes_to_check.push(&origin_node);
+ all_inputs_computed = false;
+ }
+ else {
+ max_incoming_depth = std::max(max_incoming_depth, origin_depth);
+ }
+ });
+
+ if (!all_inputs_computed) {
+ continue;
+ }
+
+ nodes_to_check.pop();
+ max_depths[current.id()] = max_incoming_depth + 1;
+ }
+}
+
MFNetwork::~MFNetwork()
{
for (auto node : m_function_nodes) {
diff --git a/source/blender/functions/intern/multi_functions/network.cc b/source/blender/functions/intern/multi_functions/network.cc
index 5689fa8db7b..3bde778cdda 100644
--- a/source/blender/functions/intern/multi_functions/network.cc
+++ b/source/blender/functions/intern/multi_functions/network.cc
@@ -395,55 +395,11 @@ BLI_NOINLINE void MF_EvaluateNetwork::copy_inputs_to_storage(MFParams params,
}
}
-static BLI_NOINLINE void compute_max_depth_per_node(const MFNetwork &network,
- MutableArrayRef<int> r_max_depths)
-{
- BLI_assert(r_max_depths.size() == network.node_ids().size());
- r_max_depths.fill(-1);
-
- for (const MFDummyNode *node : network.dummy_nodes()) {
- r_max_depths[node->id()] = 0;
- }
-
- Stack<const MFNode *> nodes_to_check;
- nodes_to_check.push_multiple(network.function_nodes());
-
- while (!nodes_to_check.is_empty()) {
- const MFNode ¤t = *nodes_to_check.peek();
- if (r_max_depths[current.id()] >= 0) {
- nodes_to_check.pop();
- continue;
- }
-
- bool all_inputs_computed = true;
- int max_incoming_depth = 0;
- for (const MFInputSocket *socket : current.inputs()) {
- const MFNode &origin_node = socket->origin().node();
- int origin_depth = r_max_depths[origin_node.id()];
- if (origin_depth == -1) {
- nodes_to_check.push(&origin_node);
- all_inputs_computed = false;
- }
- else {
- max_incoming_depth = std::max(max_incoming_depth, origin_depth);
- }
- }
-
- if (!all_inputs_computed) {
- continue;
- }
-
- nodes_to_check.pop();
- r_max_depths[current.id()] = max_incoming_depth + 1;
- }
-}
-
BLI_NOINLINE void MF_EvaluateNetwork::evaluate_network_to_compute_outputs(
MFContext &global_context, Storage &storage) const
{
const MFNetwork &network = m_outputs[0]->node().network();
- Array<int> max_depths(network.node_ids().size());
- compute_max_depth_per_node(network, max_depths);
+ ArrayRef<uint> max_dependency_depths = network.max_dependency_depth_per_node();
Stack<const MFSocket *> sockets_to_compute;
sockets_to_compute.push_multiple(m_outputs.as_ref());
@@ -476,7 +432,8 @@ BLI_NOINLINE void MF_EvaluateNetwork::evaluate_network_to_compute_outputs(
std::sort(missing_inputs.begin(),
missing_inputs.end(),
[&](const MFInputSocket *a, const MFInputSocket *b) {
- return max_depths[a->origin().node().id()] < max_depths[b->origin().node().id()];
+ return max_dependency_depths[a->origin().node().id()] <
+ max_dependency_depths[b->origin().node().id()];
});
sockets_to_compute.push_multiple(missing_inputs.as_ref());
More information about the Bf-blender-cvs
mailing list