diff options
Diffstat (limited to 'source/blender/depsgraph/intern/builder')
4 files changed, 164 insertions, 43 deletions
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc index c9fa35bd551..026aa309b02 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc @@ -46,6 +46,8 @@ namespace DEG { +namespace { + typedef enum eCyclicCheckVisitedState { /* Not is not visited at all during traversal. */ NODE_NOT_VISITED = 0, @@ -55,6 +57,30 @@ typedef enum eCyclicCheckVisitedState { NODE_IN_STACK = 2, } eCyclicCheckVisitedState; +struct StackEntry { + OperationDepsNode *node; + StackEntry *from; + DepsRelation *via_relation; +}; + +struct CyclesSolverState { + CyclesSolverState(Depsgraph *graph) + : graph(graph), + traversal_stack(BLI_stack_new(sizeof(StackEntry), + "DEG detect cycles stack")), + num_cycles(0) { + } + ~CyclesSolverState() { + BLI_stack_free(traversal_stack); + if (num_cycles != 0) { + printf("Detected %d dependency cycles\n", num_cycles); + } + } + Depsgraph *graph; + BLI_Stack *traversal_stack; + int num_cycles; +}; + BLI_INLINE void set_node_visited_state(DepsNode *node, eCyclicCheckVisitedState state) { @@ -76,19 +102,20 @@ BLI_INLINE int get_node_num_visited_children(DepsNode *node) return node->done >> 2; } -void deg_graph_detect_cycles(Depsgraph *graph) +void schedule_node_to_stack(CyclesSolverState *state, OperationDepsNode *node) { - struct StackEntry { - OperationDepsNode *node; - StackEntry *from; - DepsRelation *via_relation; - }; - - BLI_Stack *traversal_stack = BLI_stack_new(sizeof(StackEntry), - "DEG detect cycles stack"); + StackEntry entry; + entry.node = node; + entry.from = NULL; + entry.via_relation = NULL; + BLI_stack_push(state->traversal_stack, &entry); + set_node_visited_state(node, NODE_IN_STACK); +} - int num_cycles = 0; - foreach (OperationDepsNode *node, graph->operations) { +/* Schedule leaf nodes (node without input links) for traversal. */ +void schedule_leaf_nodes(CyclesSolverState *state) +{ + foreach (OperationDepsNode *node, state->graph->operations) { bool has_inlinks = false; foreach (DepsRelation *rel, node->inlinks) { if (rel->from->type == DEG_NODE_TYPE_OPERATION) { @@ -97,18 +124,32 @@ void deg_graph_detect_cycles(Depsgraph *graph) } node->done = 0; if (has_inlinks == false) { - StackEntry entry; - entry.node = node; - entry.from = NULL; - entry.via_relation = NULL; - BLI_stack_push(traversal_stack, &entry); - set_node_visited_state(node, NODE_IN_STACK); + schedule_node_to_stack(state, node); } else { set_node_visited_state(node, NODE_NOT_VISITED); } } +} + +/* Schedule node which was not checked yet for being belong to + * any of dependency cycle. + */ +bool schedule_non_checked_node(CyclesSolverState *state) +{ + foreach (OperationDepsNode *node, state->graph->operations) { + if (get_node_visited_state(node) == NODE_NOT_VISITED) { + schedule_node_to_stack(state, node); + return true; + } + } + return false; +} +/* Solve cycles with all nodes which are scheduled for traversal. */ +void solve_cycles(CyclesSolverState *state) +{ + BLI_Stack *traversal_stack = state->traversal_stack; while (!BLI_stack_is_empty(traversal_stack)) { StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack); OperationDepsNode *node = entry->node; @@ -137,7 +178,7 @@ void deg_graph_detect_cycles(Depsgraph *graph) } /* TODO(sergey): So called russian roulette cycle solver. */ rel->flag |= DEPSREL_FLAG_CYCLIC; - ++num_cycles; + ++state->num_cycles; } else if (to_state == NODE_NOT_VISITED) { StackEntry new_entry; @@ -157,11 +198,23 @@ void deg_graph_detect_cycles(Depsgraph *graph) BLI_stack_discard(traversal_stack); } } +} - BLI_stack_free(traversal_stack); +} // namespace - if (num_cycles != 0) { - printf("Detected %d dependency cycles\n", num_cycles); +void deg_graph_detect_cycles(Depsgraph *graph) +{ + CyclesSolverState state(graph); + /* First we solve cycles which are reachable from leaf nodes. */ + schedule_leaf_nodes(&state); + solve_cycles(&state); + /* We are not done yet. It is possible to have closed loop cycle, + * for example A -> B -> C -> A. These nodes were not scheduled + * yet (since they all have inlinks), and were not traversed since + * nobody else points to them. + */ + while (schedule_non_checked_node(&state)) { + solve_cycles(&state); } } diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc index 7572ee90c0b..0f21c152192 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc @@ -239,6 +239,22 @@ OperationDepsNode *DepsgraphNodeBuilder::add_operation_node( name_tag); } +OperationDepsNode *DepsgraphNodeBuilder::ensure_operation_node( + ID *id, + eDepsNode_Type comp_type, + const DepsEvalOperationCb& op, + eDepsOperation_Code opcode, + const char *name, + int name_tag) +{ + OperationDepsNode *operation = + find_operation_node(id, comp_type, opcode, name, name_tag); + if (operation != NULL) { + return operation; + } + return add_operation_node(id, comp_type, op, opcode, name, name_tag); +} + bool DepsgraphNodeBuilder::has_operation_node(ID *id, eDepsNode_Type comp_type, const char *comp_name, @@ -516,30 +532,54 @@ void DepsgraphNodeBuilder::build_animdata(ID *id) * \param id: ID-Block that driver is attached to * \param fcu: Driver-FCurve */ -OperationDepsNode *DepsgraphNodeBuilder::build_driver(ID *id, FCurve *fcu) +void DepsgraphNodeBuilder::build_driver(ID *id, FCurve *fcurve) { /* Create data node for this driver */ - /* TODO(sergey): Avoid creating same operation multiple times, - * in the future we need to avoid lookup of the operation as well - * and use some tagging magic instead. - */ - OperationDepsNode *driver_op = find_operation_node(id, - DEG_NODE_TYPE_PARAMETERS, - DEG_OPCODE_DRIVER, - fcu->rna_path ? fcu->rna_path : "", - fcu->array_index); - - if (driver_op == NULL) { - driver_op = add_operation_node(id, - DEG_NODE_TYPE_PARAMETERS, - function_bind(BKE_animsys_eval_driver, _1, id, fcu), - DEG_OPCODE_DRIVER, - fcu->rna_path ? fcu->rna_path : "", - fcu->array_index); + ensure_operation_node(id, + DEG_NODE_TYPE_PARAMETERS, + function_bind(BKE_animsys_eval_driver, _1, id, fcurve), + DEG_OPCODE_DRIVER, + fcurve->rna_path ? fcurve->rna_path : "", + fcurve->array_index); + build_driver_variables(id, fcurve); +} + +void DepsgraphNodeBuilder::build_driver_variables(ID * id, FCurve *fcurve) +{ + build_driver_id_property(id, fcurve->rna_path); + LISTBASE_FOREACH (DriverVar *, dvar, &fcurve->driver->variables) { + DRIVER_TARGETS_USED_LOOPER(dvar) + { + build_driver_id_property(dtar->id, dtar->rna_path); + } + DRIVER_TARGETS_LOOPER_END } +} - /* return driver node created */ - return driver_op; +void DepsgraphNodeBuilder::build_driver_id_property(ID *id, + const char *rna_path) +{ + if (id == NULL || rna_path == NULL) { + return; + } + PointerRNA id_ptr, ptr; + PropertyRNA *prop; + RNA_id_pointer_create(id, &id_ptr); + if (!RNA_path_resolve_full(&id_ptr, rna_path, &ptr, &prop, NULL)) { + return; + } + if (prop == NULL) { + return; + } + if (!RNA_property_is_idprop(prop)) { + return; + } + const char *prop_identifier = RNA_property_identifier((PropertyRNA *)prop); + ensure_operation_node(id, + DEG_NODE_TYPE_PARAMETERS, + NULL, + DEG_OPCODE_ID_PROPERTY, + prop_identifier); } /* Recursively build graph for world */ diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes.h b/source/blender/depsgraph/intern/builder/deg_builder_nodes.h index 825015194e2..9d47dc6bced 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_nodes.h +++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes.h @@ -99,6 +99,13 @@ struct DepsgraphNodeBuilder { const char *name = "", int name_tag = -1); + OperationDepsNode *ensure_operation_node(ID *id, + eDepsNode_Type comp_type, + const DepsEvalOperationCb& op, + eDepsOperation_Code opcode, + const char *name = "", + int name_tag = -1); + bool has_operation_node(ID *id, eDepsNode_Type comp_type, const char *comp_name, @@ -130,7 +137,9 @@ struct DepsgraphNodeBuilder { void build_particles(Object *object); void build_cloth(Object *object); void build_animdata(ID *id); - OperationDepsNode *build_driver(ID *id, FCurve *fcurve); + void build_driver(ID *id, FCurve *fcurve); + void build_driver_variables(ID *id, FCurve *fcurve); + void build_driver_id_property(ID *id, const char *rna_path); void build_ik_pose(Object *object, bPoseChannel *pchan, bConstraint *con); diff --git a/source/blender/depsgraph/intern/builder/deg_builder_relations.cc b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc index 0d85b1dfc93..40db9d1b5f1 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_relations.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc @@ -1126,7 +1126,26 @@ void DepsgraphRelationBuilder::build_driver_data(ID *id, FCurve *fcu) } else { RNAPathKey target_key(id, rna_path); - add_relation(driver_key, target_key, "Driver -> Target"); + if (RNA_pointer_is_null(&target_key.ptr)) { + /* TODO(sergey): This would only mean that driver is broken. + * so we can't create relation anyway. However, we need to avoid + * adding drivers which are known to be buggy to a dependency + * graph, in order to save computational power. + */ + } + else { + if (target_key.prop != NULL && + RNA_property_is_idprop(target_key.prop)) + { + OperationKey parameters_key(id, + DEG_NODE_TYPE_PARAMETERS, + DEG_OPCODE_PARAMETERS_EVAL); + add_relation(target_key, + parameters_key, + "Driver Target -> Properties"); + } + add_relation(driver_key, target_key, "Driver -> Target"); + } } } |