From bac735380189c63d2b8824cba8e0398bb35e9af2 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 12 May 2015 15:05:57 +0500 Subject: Depsgraph: New dependency graph integration commit This commit integrates the work done so far on the new dependency graph system, where goal was to replace legacy depsgraph with the new one, supporting loads of neat features like: - More granular dependency relation nature, which solves issues with fake cycles in the dependencies. - Move towards all-animatable, by better integration of drivers into the system. - Lay down some basis for upcoming copy-on-write, overrides and so on. The new system is living side-by-side with the previous one and disabled by default, so nothing will become suddenly broken. The way to enable new depsgraph is to pass `--new-depsgraph` command line argument. It's a bit early to consider the system production-ready, there are some TODOs and issues were discovered during the merge period, they'll be addressed ASAP. But it's important to merge, because it's the only way to attract artists to really start testing this system. There are number of assorted documents related on the design of the new system: * http://wiki.blender.org/index.php/User:Aligorith/GSoC2013_Depsgraph#Design_Documents * http://wiki.blender.org/index.php/User:Nazg-gul/DependencyGraph There are also some user-related information online: * http://code.blender.org/2015/02/blender-dependency-graph-branch-for-users/ * http://code.blender.org/2015/03/more-dependency-graph-tricks/ Kudos to everyone who was involved into the project: - Joshua "Aligorith" Leung -- design specification, initial code - Lukas "lukas_t" Toenne -- integrating code into blender, with further fixes - Sergey "Sergey" "Sharybin" -- some mocking around, trying to wrap up the project and so - Bassam "slikdigit" Kurdali -- stressing the new system, reporting all the issues and recording/writing documentation. - Everyone else who i forgot to mention here :) --- .../blender/depsgraph/util/depsgraph_util_cycle.cc | 134 +++++++++++++++++++++ 1 file changed, 134 insertions(+) create mode 100644 source/blender/depsgraph/util/depsgraph_util_cycle.cc (limited to 'source/blender/depsgraph/util/depsgraph_util_cycle.cc') diff --git a/source/blender/depsgraph/util/depsgraph_util_cycle.cc b/source/blender/depsgraph/util/depsgraph_util_cycle.cc new file mode 100644 index 00000000000..5a171d190cd --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_cycle.cc @@ -0,0 +1,134 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2015 Blender Foundation. + * All rights reserved. + * + * Contributor(s): Sergey Sharybin + */ + +#include +#include +#include + +extern "C" { +#include "BLI_utildefines.h" + +#include "DNA_ID.h" + +#include "RNA_access.h" +#include "RNA_types.h" +} + +#include "depsgraph_util_cycle.h" +#include "depsgraph.h" +#include "depsnode.h" +#include "depsnode_component.h" +#include "depsnode_operation.h" + +struct StackEntry { + OperationDepsNode *node; + StackEntry *from; + DepsRelation *via_relation; +}; + +void deg_graph_detect_cycles(Depsgraph *graph) +{ + /* Not is not visited at all during traversal. */ + const int NODE_NOT_VISITED = 0; + /* Node has been visited during traversal and not in current stack. */ + const int NODE_VISITED = 1; + /* Node has been visited during traversal and is in current stack. */ + const int NODE_IN_STACK = 2; + + std::stack traversal_stack; + for (Depsgraph::OperationNodes::const_iterator it_op = graph->operations.begin(); + it_op != graph->operations.end(); + ++it_op) + { + OperationDepsNode *node = *it_op; + bool has_inlinks = false; + for (OperationDepsNode::Relations::const_iterator it_rel = node->inlinks.begin(); + it_rel != node->inlinks.end(); + ++it_rel) + { + DepsRelation *rel = *it_rel; + if (rel->from->type == DEPSNODE_TYPE_OPERATION) { + has_inlinks = true; + } + } + if (has_inlinks == false) { + StackEntry entry; + entry.node = node; + entry.from = NULL; + entry.via_relation = NULL; + traversal_stack.push(entry); + node->done = NODE_IN_STACK; + } + else { + node->done = NODE_NOT_VISITED; + } + } + + while (!traversal_stack.empty()) { + StackEntry &entry = traversal_stack.top(); + OperationDepsNode *node = entry.node; + bool all_child_traversed = true; + for (OperationDepsNode::Relations::const_iterator it_rel = node->outlinks.begin(); + it_rel != node->outlinks.end(); + ++it_rel) + { + DepsRelation *rel = *it_rel; + if (rel->to->type == DEPSNODE_TYPE_OPERATION) { + OperationDepsNode *to = (OperationDepsNode *)rel->to; + if (to->done == NODE_IN_STACK) { + printf("Dependency cycle detected:\n"); + printf(" '%s' depends on '%s' through '%s'\n", + to->full_identifier().c_str(), + node->full_identifier().c_str(), + rel->name); + + StackEntry *current = &entry; + while (current->node != to) { + BLI_assert(current != NULL); + printf(" '%s' depends on '%s' through '%s'\n", + current->node->full_identifier().c_str(), + current->from->node->full_identifier().c_str(), + current->via_relation->name); + current = current->from; + } + /* TODO(sergey): So called roussian rlette cycle solver. */ + rel->flag |= DEPSREL_FLAG_CYCLIC; + } + else if (to->done == NODE_NOT_VISITED) { + StackEntry new_entry; + new_entry.node = to; + new_entry.from = &entry; + new_entry.via_relation = rel; + traversal_stack.push(new_entry); + to->done = NODE_IN_STACK; + all_child_traversed = false; + break; + } + } + } + if (all_child_traversed) { + node->done = NODE_VISITED; + traversal_stack.pop(); + } + } +} -- cgit v1.2.3 From 5d30c23c35aafba3a9bc772b4e66dd70b1ed84de Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Wed, 20 May 2015 12:54:45 +1000 Subject: doxygen: corrections/updates Also add depsgraph & physics --- source/blender/depsgraph/util/depsgraph_util_cycle.cc | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'source/blender/depsgraph/util/depsgraph_util_cycle.cc') diff --git a/source/blender/depsgraph/util/depsgraph_util_cycle.cc b/source/blender/depsgraph/util/depsgraph_util_cycle.cc index 5a171d190cd..5eae8c087ad 100644 --- a/source/blender/depsgraph/util/depsgraph_util_cycle.cc +++ b/source/blender/depsgraph/util/depsgraph_util_cycle.cc @@ -19,6 +19,12 @@ * All rights reserved. * * Contributor(s): Sergey Sharybin + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/util/depsgraph_util_cycle.cc + * \ingroup depsgraph */ #include -- cgit v1.2.3