[Bf-blender-cvs] [8c45804a1cd] functions: initial deepest depth first heuristic
Jacques Lucke
noreply at git.blender.org
Mon Jan 27 22:10:02 CET 2020
Commit: 8c45804a1cd8e383a6f414a9a120597ca6e5ac3b
Author: Jacques Lucke
Date: Sun Jan 26 17:26:45 2020 +0100
Branches: functions
https://developer.blender.org/rB8c45804a1cd8e383a6f414a9a120597ca6e5ac3b
initial deepest depth first heuristic
===================================================================
M source/blender/functions/FN_multi_function_network.h
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 fd3e21b6a58..ea4fe4c545b 100644
--- a/source/blender/functions/FN_multi_function_network.h
+++ b/source/blender/functions/FN_multi_function_network.h
@@ -383,12 +383,18 @@ class MFNetwork : BLI::NonCopyable, BLI::NonMovable {
const MFNode &node_by_id(uint id) const;
const MFSocket &socket_by_id(uint id) const;
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();
+ }
+
Vector<const MFOutputSocket *> find_dummy_dependencies(
ArrayRef<const MFInputSocket *> sockets) const;
@@ -775,6 +781,11 @@ inline IndexRange MFNetwork::socket_ids() const
return IndexRange(m_socket_by_id.size());
}
+inline IndexRange MFNetwork::node_ids() const
+{
+ return IndexRange(m_node_by_id.size());
+}
+
} // namespace FN
#endif /* __FN_MULTI_FUNCTION_NETWORK_H__ */
diff --git a/source/blender/functions/intern/multi_functions/network.cc b/source/blender/functions/intern/multi_functions/network.cc
index 3d27a6eb5b5..5689fa8db7b 100644
--- a/source/blender/functions/intern/multi_functions/network.cc
+++ b/source/blender/functions/intern/multi_functions/network.cc
@@ -5,6 +5,7 @@
namespace FN {
using BLI::ArrayAllocator;
+using BLI::ScopedVector;
namespace OutputValueType {
enum Enum {
@@ -394,14 +395,58 @@ 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
{
- Stack<const MFSocket *> sockets_to_compute;
+ const MFNetwork &network = m_outputs[0]->node().network();
+ Array<int> max_depths(network.node_ids().size());
+ compute_max_depth_per_node(network, max_depths);
- for (const MFInputSocket *input_socket : m_outputs) {
- sockets_to_compute.push(input_socket);
- }
+ Stack<const MFSocket *> sockets_to_compute;
+ sockets_to_compute.push_multiple(m_outputs.as_ref());
while (!sockets_to_compute.is_empty()) {
const MFSocket &socket = *sockets_to_compute.peek();
@@ -420,15 +465,23 @@ BLI_NOINLINE void MF_EvaluateNetwork::evaluate_network_to_compute_outputs(
const MFOutputSocket &output_socket = socket.as_output();
const MFFunctionNode &function_node = output_socket.node().as_function();
- uint not_computed_inputs_amount = 0;
+ ScopedVector<const MFInputSocket *> missing_inputs;
for (const MFInputSocket *input_socket : function_node.inputs()) {
if (!storage.input_is_computed(*input_socket)) {
- not_computed_inputs_amount++;
+ missing_inputs.append(input_socket);
sockets_to_compute.push(input_socket);
}
}
- bool all_inputs_are_computed = not_computed_inputs_amount == 0;
+ 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()];
+ });
+
+ sockets_to_compute.push_multiple(missing_inputs.as_ref());
+
+ bool all_inputs_are_computed = missing_inputs.size() == 0;
if (all_inputs_are_computed) {
this->evaluate_function(global_context, function_node, storage);
sockets_to_compute.pop();
@@ -442,7 +495,7 @@ BLI_NOINLINE void MF_EvaluateNetwork::evaluate_function(MFContext &global_contex
Storage &storage) const
{
const MultiFunction &function = function_node.function();
- std::cout << function.name() << "\n";
+ // std::cout << "Function: " << function.name() << "\n";
MFParamsBuilder params_builder{function, storage.mask().min_array_size()};
More information about the Bf-blender-cvs
mailing list