diff options
3 files changed, 121 insertions, 42 deletions
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_relations.cc b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc index 64fb15a465b..3e7fb702d6a 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_relations.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc @@ -28,6 +28,8 @@ #include <stdio.h> #include <stdlib.h> #include <cstring> /* required for STREQ later on. */ +#include <deque> +#include <unordered_set> #include "MEM_guardedalloc.h" @@ -119,6 +121,9 @@ extern "C" { namespace DEG { +using std::deque; +using std::unordered_set; + /* ***************** */ /* Relations Builder */ @@ -1330,48 +1335,6 @@ void DepsgraphRelationBuilder::build_animdata_drivers(ID *id) /* create the driver's relations to targets */ build_driver(id, fcu); - /* Special case for array drivers: we can not multithread them because - * of the way how they work internally: animation system will write the - * whole array back to RNA even when changing individual array value. - * - * Some tricky things here: - * - array_index is -1 for single channel drivers, meaning we only have - * to do some magic when array_index is not -1. - * - We do relation from next array index to a previous one, so we don't - * have to deal with array index 0. - * - * TODO(sergey): Avoid liner lookup somehow. */ - if (fcu->array_index > 0) { - FCurve *fcu_prev = nullptr; - LISTBASE_FOREACH (FCurve *, fcu_candidate, &adt->drivers) { - /* Writing to different RNA paths is */ - const char *rna_path = fcu->rna_path ? fcu->rna_path : ""; - if (!STREQ(fcu_candidate->rna_path, rna_path)) { - continue; - } - /* We only do relation from previous fcurve to previous one. */ - if (fcu_candidate->array_index >= fcu->array_index) { - continue; - } - /* Choose fcurve with highest possible array index. */ - if (fcu_prev == nullptr || fcu_candidate->array_index > fcu_prev->array_index) { - fcu_prev = fcu_candidate; - } - } - if (fcu_prev != nullptr) { - OperationKey prev_driver_key(id, - NodeType::PARAMETERS, - OperationCode::DRIVER, - fcu_prev->rna_path ? fcu_prev->rna_path : "", - fcu_prev->array_index); - OperationKey driver_key(id, - NodeType::PARAMETERS, - OperationCode::DRIVER, - fcu->rna_path ? fcu->rna_path : "", - fcu->array_index); - add_relation(prev_driver_key, driver_key, "Driver Order"); - } - } /* prevent driver from occurring before own animation... */ if (adt->action || adt->nla_tracks.first) { @@ -2710,6 +2673,116 @@ void DepsgraphRelationBuilder::build_copy_on_write_relations(IDNode *id_node) #endif } +static bool is_reachable(const Node *const from, const Node *const to) +{ + if (from == to) { + return true; + } + + // Perform a graph walk from 'to' towards its incoming connections. + // Walking from 'from' towards its outgoing connections is 10x slower on the Spring rig. + deque<const Node *> queue; + unordered_set<const Node *> seen; + queue.push_back(to); + while (!queue.empty()) { + // Visit the next node to inspect. + const Node *visit = queue.back(); + queue.pop_back(); + + if (visit == from) { + return true; + } + + // Queue all incoming relations that we haven't seen before. + for (Relation *relation : visit->inlinks) { + const Node *prev_node = relation->from; + if (seen.insert(prev_node).second) { + queue.push_back(prev_node); + } + } + } + return false; +} + +void DepsgraphRelationBuilder::build_driver_relations() +{ + for (IDNode *id_node : graph_->id_nodes) { + build_driver_relations(id_node); + } +} + +void DepsgraphRelationBuilder::build_driver_relations(IDNode *id_node) +{ + /* Add relations between drivers that write to the same datablock. + * + * This prevents threading issues when two separate RNA properties write to + * the same memory address. For example: + * - Drivers on individual array elements, as the animation system will write + * the whole array back to RNA even when changing individual array value. + * - Drivers on RNA properties that map to a single bit flag. Changing the RNA + * value will write the entire int containing the bit, in a non-thread-safe + * way. + */ + ID *id_orig = id_node->id_orig; + AnimData *adt = BKE_animdata_from_id(id_orig); + if (adt == nullptr) { + return; + } + + // Mapping from RNA prefix -> set of driver evaluation nodes: + typedef vector<Node *> DriverGroup; + typedef map<string, DriverGroup> DriverGroupMap; + DriverGroupMap driver_groups; + + LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) { + // Get the RNA path except the part after the last dot. + char *last_dot = strrchr(fcu->rna_path, '.'); + string rna_prefix; + if (last_dot != nullptr) { + rna_prefix = string(fcu->rna_path, last_dot); + } + + // Insert this driver node into the group belonging to the RNA prefix. + OperationKey driver_key( + id_orig, NodeType::PARAMETERS, OperationCode::DRIVER, fcu->rna_path, fcu->array_index); + Node *node_driver = get_node(driver_key); + driver_groups[rna_prefix].push_back(node_driver); + } + + for (pair<string, DriverGroup> prefix_group : driver_groups) { + // For each node in the driver group, try to connect it to another node + // in the same group without creating any cycles. + int num_drivers = prefix_group.second.size(); + for (int from_index = 0; from_index < num_drivers; ++from_index) { + Node *op_from = prefix_group.second[from_index]; + + // Start by trying the next node in the group. + for (int to_offset = 1; to_offset < num_drivers - 1; ++to_offset) { + int to_index = (from_index + to_offset) % num_drivers; + Node *op_to = prefix_group.second[to_index]; + + // Investigate whether this relation would create a dependency cycle. + // Example graph: + // A -> B -> C + // and investigating a potential connection C->A. Because A->C is an + // existing transitive connection, adding C->A would create a cycle. + if (is_reachable(op_to, op_from)) { + continue; + } + + // No need to directly connect this node if there is already a transitive connection. + if (is_reachable(op_from, op_to)) { + break; + } + + add_operation_relation( + op_from->get_exit_operation(), op_to->get_entry_operation(), "Driver Serialisation"); + break; + } + } + } +} + /* **** ID traversal callbacks functions **** */ void DepsgraphRelationBuilder::modifier_walk(void *user_data, diff --git a/source/blender/depsgraph/intern/builder/deg_builder_relations.h b/source/blender/depsgraph/intern/builder/deg_builder_relations.h index 11eb31c68f6..7da3577a7b5 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_relations.h +++ b/source/blender/depsgraph/intern/builder/deg_builder_relations.h @@ -302,6 +302,8 @@ class DepsgraphRelationBuilder : public DepsgraphBuilder { virtual void build_copy_on_write_relations(); virtual void build_copy_on_write_relations(IDNode *id_node); + virtual void build_driver_relations(); + virtual void build_driver_relations(IDNode *id_node); template<typename KeyType> OperationNode *find_operation_node(const KeyType &key); diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc index a570e042c26..3fe585ff73c 100644 --- a/source/blender/depsgraph/intern/depsgraph_build.cc +++ b/source/blender/depsgraph/intern/depsgraph_build.cc @@ -251,6 +251,7 @@ void DEG_graph_build_from_view_layer(Depsgraph *graph, relation_builder.begin_build(); relation_builder.build_view_layer(scene, view_layer, DEG::DEG_ID_LINKED_DIRECTLY); relation_builder.build_copy_on_write_relations(); + relation_builder.build_driver_relations(); /* Finalize building. */ graph_build_finalize_common(deg_graph, bmain); /* Finish statistics. */ @@ -284,6 +285,7 @@ void DEG_graph_build_for_render_pipeline(Depsgraph *graph, relation_builder.begin_build(); relation_builder.build_scene_render(scene, view_layer); relation_builder.build_copy_on_write_relations(); + relation_builder.build_driver_relations(); /* Finalize building. */ graph_build_finalize_common(deg_graph, bmain); /* Finish statistics. */ @@ -317,6 +319,7 @@ void DEG_graph_build_for_compositor_preview( relation_builder.build_scene_render(scene, view_layer); relation_builder.build_nodetree(nodetree); relation_builder.build_copy_on_write_relations(); + relation_builder.build_driver_relations(); /* Finalize building. */ graph_build_finalize_common(deg_graph, bmain); /* Finish statistics. */ @@ -458,6 +461,7 @@ void DEG_graph_build_from_ids(Depsgraph *graph, relation_builder.build_id(ids[i]); } relation_builder.build_copy_on_write_relations(); + relation_builder.build_driver_relations(); /* Finalize building. */ graph_build_finalize_common(deg_graph, bmain); /* Finish statistics. */ |