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 +++++++++++++++++++++ .../blender/depsgraph/util/depsgraph_util_cycle.h | 31 +++++ .../depsgraph/util/depsgraph_util_function.h | 106 ++++++++++++++++ .../blender/depsgraph/util/depsgraph_util_hash.h | 66 ++++++++++ source/blender/depsgraph/util/depsgraph_util_map.h | 61 ++++++++++ .../depsgraph/util/depsgraph_util_pchanmap.cc | 132 ++++++++++++++++++++ .../depsgraph/util/depsgraph_util_pchanmap.h | 55 +++++++++ source/blender/depsgraph/util/depsgraph_util_set.h | 60 +++++++++ .../depsgraph/util/depsgraph_util_transitive.cc | 133 ++++++++++++++++++++ .../depsgraph/util/depsgraph_util_transitive.h | 32 +++++ 10 files changed, 810 insertions(+) create mode 100644 source/blender/depsgraph/util/depsgraph_util_cycle.cc create mode 100644 source/blender/depsgraph/util/depsgraph_util_cycle.h create mode 100644 source/blender/depsgraph/util/depsgraph_util_function.h create mode 100644 source/blender/depsgraph/util/depsgraph_util_hash.h create mode 100644 source/blender/depsgraph/util/depsgraph_util_map.h create mode 100644 source/blender/depsgraph/util/depsgraph_util_pchanmap.cc create mode 100644 source/blender/depsgraph/util/depsgraph_util_pchanmap.h create mode 100644 source/blender/depsgraph/util/depsgraph_util_set.h create mode 100644 source/blender/depsgraph/util/depsgraph_util_transitive.cc create mode 100644 source/blender/depsgraph/util/depsgraph_util_transitive.h (limited to 'source/blender/depsgraph/util') 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(); + } + } +} diff --git a/source/blender/depsgraph/util/depsgraph_util_cycle.h b/source/blender/depsgraph/util/depsgraph_util_cycle.h new file mode 100644 index 00000000000..f827d85c16a --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_cycle.h @@ -0,0 +1,31 @@ +/* + * ***** 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 + */ + +#ifndef __DEPSGRAPH_UTIL_CYCLE_H__ +#define __DEPSGRAPH_UTIL_CYCLE_H__ + +struct Depsgraph; + +void deg_graph_detect_cycles(Depsgraph *graph); + +#endif /* __DEPSGRAPH_UTIL_CYCLE_H__ */ diff --git a/source/blender/depsgraph/util/depsgraph_util_function.h b/source/blender/depsgraph/util/depsgraph_util_function.h new file mode 100644 index 00000000000..f62efd76267 --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_function.h @@ -0,0 +1,106 @@ +/* + * ***** 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) 2014 Blender Foundation. + * All rights reserved. + * + * Original Author: Lukas Toenne + * Contributor(s): + */ + +#ifndef __DEPSGRAPH_UTIL_FUNCTION_H__ +#define __DEPSGRAPH_UTIL_FUNCTION_H__ + +#if (__cplusplus > 199711L) || (defined(_MSC_VER) && _MSC_VER >= 1800) + +#include + +using std::function; +using namespace std::placeholders; +#define function_bind std::bind + +#elif defined(HAVE_BOOST_FUNCTION_BINDINGS) + +#include +#include + +using boost::function; +#define function_bind boost::bind + +#else + +#pragma message("No available function binding implementation. Using stub instead, disabling new depsgraph") + +#ifndef WITH_LEGACY_DEPSGRAPH +# error "Unable to build new depsgraph and legacy one is disabled." +#endif + +#define DISABLE_NEW_DEPSGRAPH + +#include + +template +class function { +public: + function() {}; + function(void *) {} + operator bool() const { return false; } + bool operator== (void*) { return false; } + + template + void operator() (T1) { + BLI_assert(!"Should not be used"); + } +}; + +class Wrap { +public: + Wrap() {} + template + Wrap(T /*arg*/) {} +}; + +template +void *function_bind(T func, + Wrap arg1 = Wrap(), + Wrap arg2 = Wrap(), + Wrap arg3 = Wrap(), + Wrap arg4 = Wrap(), + Wrap arg5 = Wrap(), + Wrap arg6 = Wrap(), + Wrap arg7 = Wrap()) +{ + BLI_assert(!"Should not be used"); + (void)func; + (void)arg1; + (void)arg2; + (void)arg3; + (void)arg4; + (void)arg5; + (void)arg6; + (void)arg7; + return NULL; +} + +#define _1 Wrap() +#define _2 Wrap() +#define _3 Wrap() +#define _4 Wrap() + +#endif + +#endif /* __DEPSGRAPH_UTIL_SET_H__ */ diff --git a/source/blender/depsgraph/util/depsgraph_util_hash.h b/source/blender/depsgraph/util/depsgraph_util_hash.h new file mode 100644 index 00000000000..0f5a85b3526 --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_hash.h @@ -0,0 +1,66 @@ +/* + * ***** 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) 2014 Blender Foundation. + * All rights reserved. + * + * Original Author: Brecht van Lommel + * Contributor(s): Lukas Toenne + */ + +#ifndef __DEPSGRAPH_UTIL_HASH_H__ +#define __DEPSGRAPH_UTIL_HASH_H__ + +#if defined(DEG_NO_UNORDERED_MAP) +# define DEG_HASH_NAMESPACE_BEGIN +# define DEG_HASH_NAMESPACE_END +#endif + +#if defined(DEG_TR1_UNORDERED_MAP) +# include +# define DEG_HASH_NAMESPACE_BEGIN namespace std { namespace tr1 { +# define DEG_HASH_NAMESPACE_END } } +using std::tr1::hash; +#endif + +#if defined(DEG_STD_UNORDERED_MAP) +# include +# define DEG_HASH_NAMESPACE_BEGIN namespace std { +# define DEG_HASH_NAMESPACE_END } +using std::hash; +#endif + +#if defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) +# include +# define DEG_HASH_NAMESPACE_BEGIN namespace std { namespace tr1 { +# define DEG_HASH_NAMESPACE_END } } +using std::tr1::hash; +#endif + +#if !defined(DEG_NO_UNORDERED_MAP) && !defined(DEG_TR1_UNORDERED_MAP) && \ + !defined(DEG_STD_UNORDERED_MAP) && !defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) // NOLINT +# error One of: DEG_NO_UNORDERED_MAP, DEG_TR1_UNORDERED_MAP,\ + DEG_STD_UNORDERED_MAP, DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE must be defined! // NOLINT +#endif + +/* XXX this might require 2 different variants for sizeof(size_t) (32 vs 64 bit) */ +inline size_t hash_combine(size_t hash_a, size_t hash_b) +{ + return hash_a ^ (hash_b + 0x9e3779b9 + (hash_a << 6) + (hash_a >> 2)); +} + +#endif /* __DEPSGRAPH_UTIL_HASH_H__ */ diff --git a/source/blender/depsgraph/util/depsgraph_util_map.h b/source/blender/depsgraph/util/depsgraph_util_map.h new file mode 100644 index 00000000000..2951641431b --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_map.h @@ -0,0 +1,61 @@ +/* + * ***** 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) 2014 Blender Foundation. + * All rights reserved. + * + * Original Author: Brecht van Lommel + * Contributor(s): Lukas Toenne + */ + +#ifndef __DEPSGRAPH_UTIL_MAP_H__ +#define __DEPSGRAPH_UTIL_MAP_H__ + +#include + +#include "depsgraph_util_hash.h" + +using std::map; +using std::pair; + +#if defined(DEG_NO_UNORDERED_MAP) +# include +typedef std::map unordered_map; +#endif + +#if defined(DEG_TR1_UNORDERED_MAP) +# include +using std::tr1::unordered_map; +#endif + +#if defined(DEG_STD_UNORDERED_MAP) +# include +using std::unordered_map; +#endif + +#if defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) +# include +using std::tr1::unordered_map; +#endif + +#if !defined(DEG_NO_UNORDERED_MAP) && !defined(DEG_TR1_UNORDERED_MAP) && \ + !defined(DEG_STD_UNORDERED_MAP) && !defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) // NOLINT +# error One of: DEG_NO_UNORDERED_MAP, DEG_TR1_UNORDERED_MAP,\ + DEG_STD_UNORDERED_MAP, DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE must be defined! // NOLINT +#endif + +#endif /* __DEPSGRAPH_UTIL_MAP_H__ */ diff --git a/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc b/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc new file mode 100644 index 00000000000..36bd72108ed --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc @@ -0,0 +1,132 @@ +/* + * ***** 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. + * + * Original Author: Sergey Sharybin + * Contributor(s): Joshua Leung + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#include "depsgraph_util_pchanmap.h" + +#include +#include + +extern "C" { +#include "BLI_utildefines.h" +#include "BLI_ghash.h" +} + +static void free_rootpchanmap_valueset(void *val) +{ + /* Just need to free the set itself - the names stored are all references. */ + GSet *values = (GSet *)val; + BLI_gset_free(values, NULL); +} + +RootPChanMap::RootPChanMap() +{ + /* Just create empty map. */ + m_map = BLI_ghash_str_new("RootPChanMap"); +} + +RootPChanMap::~RootPChanMap() +{ + /* Free the map, and all the value sets. */ + BLI_ghash_free(m_map, NULL, free_rootpchanmap_valueset); +} + +/* Debug contents of map */ +void RootPChanMap::print_debug() +{ + GHashIterator it1; + GSetIterator it2; + + printf("Root PChan Map:\n"); + GHASH_ITER(it1, m_map) { + const char *item = (const char *)BLI_ghashIterator_getKey(&it1); + GSet *values = (GSet *)BLI_ghashIterator_getValue(&it1); + + printf(" %s : { ", item); + GSET_ITER(it2, values) { + const char *val = (const char *)BLI_gsetIterator_getKey(&it2); + printf("%s, ", val); + } + printf("}\n"); + } +} + +/* Add a mapping. */ +void RootPChanMap::add_bone(const char *bone, const char *root) +{ + if (BLI_ghash_haskey(m_map, bone)) { + /* Add new entry, but only add the root if it doesn't already + * exist in there. + */ + GSet *values = (GSet *)BLI_ghash_lookup(m_map, bone); + BLI_gset_add(values, (void *)root); + } + else { + /* Create new set and mapping. */ + GSet *values = BLI_gset_new(BLI_ghashutil_strhash_p, + BLI_ghashutil_strcmp, + "RootPChanMap Value Set"); + BLI_ghash_insert(m_map, (void *)bone, (void *)values); + + /* Add new entry now. */ + BLI_gset_insert(values, (void *)root); + } +} + +/* Check if there's a common root bone between two bones. */ +bool RootPChanMap::has_common_root(const char *bone1, const char *bone2) +{ + /* Ensure that both are in the map... */ + if (BLI_ghash_haskey(m_map, bone1) == false) { + //fprintf("RootPChanMap: bone1 '%s' not found (%s => %s)\n", bone1, bone1, bone2); + //print_debug(); + return false; + } + + if (BLI_ghash_haskey(m_map, bone2) == false) { + //fprintf("RootPChanMap: bone2 '%s' not found (%s => %s)\n", bone2, bone1, bone2); + //print_debug(); + return false; + } + + GSet *bone1_roots = (GSet *)BLI_ghash_lookup(m_map, (void *)bone1); + GSet *bone2_roots = (GSet *)BLI_ghash_lookup(m_map, (void *)bone2); + + GSetIterator it1, it2; + GSET_ITER(it1, bone1_roots) { + GSET_ITER(it2, bone2_roots) { + const char *v1 = (const char *)BLI_gsetIterator_getKey(&it1); + const char *v2 = (const char *)BLI_gsetIterator_getKey(&it2); + + if (strcmp(v1, v2) == 0) { + //fprintf("RootPchanMap: %s in common for %s => %s\n", v1, bone1, bone2); + return true; + } + } + } + + //fprintf("RootPChanMap: No common root found (%s => %s)\n", bone1, bone2); + return false; +} diff --git a/source/blender/depsgraph/util/depsgraph_util_pchanmap.h b/source/blender/depsgraph/util/depsgraph_util_pchanmap.h new file mode 100644 index 00000000000..5d27d84c0da --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_pchanmap.h @@ -0,0 +1,55 @@ +/* + * ***** 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. + * + * Original Author: Sergey Sharybin + * Contributor(s): Joshua Leung + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef ___DEPSGRAPH_UTIL_PCHANMAP_H__ +#define ___DEPSGRAPH_UTIL_PCHANMAP_H__ + +struct RootPChanMap { + /* ctor and dtor - Create and free the internal map respectively. */ + RootPChanMap(); + ~RootPChanMap(); + + /* Debug contents of map. */ + void print_debug(); + + /* Add a mapping. */ + void add_bone(const char *bone, const char *root); + + /* Check if there's a common root bone between two bones. */ + bool has_common_root(const char *bone1, const char *bone2); + +private: + /* The actual map: + * - Keys are "strings" (const char *) - not dynamically allocated. + * - Values are "sets" (const char *) - not dynamically allocated. + * + * We don't use the C++ maps here, as it's more convenient to use + * Blender's GHash and be able to compare by-value instead of by-ref. + */ + struct GHash *m_map; +}; + +#endif /* __DEPSGRAPH_UTIL_PCHANMAP_H__ */ diff --git a/source/blender/depsgraph/util/depsgraph_util_set.h b/source/blender/depsgraph/util/depsgraph_util_set.h new file mode 100644 index 00000000000..09fa5313920 --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_set.h @@ -0,0 +1,60 @@ +/* + * ***** 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) 2014 Blender Foundation. + * All rights reserved. + * + * Original Author: Brecht van Lommel + * Contributor(s): Lukas Toenne + */ + +#ifndef __DEPSGRAPH_UTIL_SET_H__ +#define __DEPSGRAPH_UTIL_SET_H__ + +#include + +#include "depsgraph_util_hash.h" + +using std::set; + +#if defined(DEG_NO_UNORDERED_MAP) +# include +typedef std::set unordered_set; +#endif + +#if defined(DEG_TR1_UNORDERED_MAP) +# include +using std::tr1::unordered_set; +#endif + +#if defined(DEG_STD_UNORDERED_MAP) +# include +using std::unordered_set; +#endif + +#if defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) +# include +using std::tr1::unordered_set; +#endif + +#if !defined(DEG_NO_UNORDERED_MAP) && !defined(DEG_TR1_UNORDERED_MAP) && \ + !defined(DEG_STD_UNORDERED_MAP) && !defined(DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE) // NOLINT +# error One of: DEG_NO_UNORDERED_MAP, DEG_TR1_UNORDERED_MAP,\ + DEG_STD_UNORDERED_MAP, DEG_STD_UNORDERED_MAP_IN_TR1_NAMESPACE must be defined! // NOLINT +#endif + +#endif /* __DEPSGRAPH_UTIL_SET_H__ */ diff --git a/source/blender/depsgraph/util/depsgraph_util_transitive.cc b/source/blender/depsgraph/util/depsgraph_util_transitive.cc new file mode 100644 index 00000000000..9411d013c44 --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_transitive.cc @@ -0,0 +1,133 @@ +/* + * ***** 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): Lukas Toenne + * Sergey Sharybin, + */ + +extern "C" { +#include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" + +#include "DNA_ID.h" + +#include "RNA_access.h" +#include "RNA_types.h" +} + +#include "depsgraph_util_transitive.h" +#include "depsgraph.h" +#include "depsnode.h" +#include "depsnode_component.h" +#include "depsnode_operation.h" + +/* -------------------------------------------------- */ + +/* Performs a transitive reduction to remove redundant relations. + * http://en.wikipedia.org/wiki/Transitive_reduction + * + * XXX The current implementation is somewhat naive and has O(V*E) worst case + * runtime. + * A more optimized algorithm can be implemented later, e.g. + * + * http://www.sciencedirect.com/science/article/pii/0304397588900321/pdf?md5=3391e309b708b6f9cdedcd08f84f4afc&pid=1-s2.0-0304397588900321-main.pdf + * + * Care has to be taken to make sure the algorithm can handle the cyclic case + * too! (unless we can to prevent this case early on). + */ + +enum { + OP_VISITED = 1, + OP_REACHABLE = 2, +}; + +static void deg_graph_tag_paths_recursive(DepsNode *node) +{ + if (node->done & OP_VISITED) + return; + node->done |= OP_VISITED; + + for (OperationDepsNode::Relations::const_iterator it = node->inlinks.begin(); + it != node->inlinks.end(); + ++it) + { + DepsRelation *rel = *it; + + deg_graph_tag_paths_recursive(rel->from); + /* Do this only in inlinks loop, so the target node does not get + * flagged. + */ + rel->from->done |= OP_REACHABLE; + } +} + +void deg_graph_transitive_reduction(Depsgraph *graph) +{ + for (Depsgraph::OperationNodes::const_iterator it_target = graph->operations.begin(); + it_target != graph->operations.end(); + ++it_target) + { + OperationDepsNode *target = *it_target; + + /* Clear tags. */ + for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); + it != graph->operations.end(); + ++it) + { + OperationDepsNode *node = *it; + node->done = 0; + } + + /* mark nodes from which we can reach the target + * start with children, so the target node and direct children are not + * flagged. + */ + target->done |= OP_VISITED; + for (OperationDepsNode::Relations::const_iterator it = target->inlinks.begin(); + it != target->inlinks.end(); + ++it) + { + DepsRelation *rel = *it; + + deg_graph_tag_paths_recursive(rel->from); + } + + /* Eemove redundant paths to the target. */ + for (DepsNode::Relations::const_iterator it_rel = target->inlinks.begin(); + it_rel != target->inlinks.end(); + ) + { + DepsRelation *rel = *it_rel; + /* Increment in advance, so we can safely remove the relation. */ + ++it_rel; + + if (rel->from->type == DEPSNODE_TYPE_TIMESOURCE) { + /* HACK: time source nodes don't get "done" flag set/cleared. */ + /* TODO: there will be other types in future, so iterators above + * need modifying. + */ + } + else if (rel->from->done & OP_REACHABLE) { + OBJECT_GUARDED_DELETE(rel, DepsRelation); + } + } + } +} diff --git a/source/blender/depsgraph/util/depsgraph_util_transitive.h b/source/blender/depsgraph/util/depsgraph_util_transitive.h new file mode 100644 index 00000000000..8995c18eca0 --- /dev/null +++ b/source/blender/depsgraph/util/depsgraph_util_transitive.h @@ -0,0 +1,32 @@ +/* + * ***** 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): Lukas Toenne + * Sergey Sharybin, + */ + +#ifndef __DEPSGRAPH_UTIL_TRANSITIVE_H__ +#define __DEPSGRAPH_UTIL_TRANSITIVE_H__ + +struct Depsgraph; + +void deg_graph_transitive_reduction(Depsgraph *graph); + +#endif /* __DEPSGRAPH_UTIL_TRANSITIVE_H__ */ -- cgit v1.2.3 From 8697c19e91d128d91026ac043f2570583a689724 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 12 May 2015 16:40:22 +0500 Subject: Depsgraph: Don't use C++11 function binding with MSVC It has some weird incompatibility with the way how Boost and GCC C++11 function bindings works, resulting in compilation errors. --- source/blender/depsgraph/util/depsgraph_util_function.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'source/blender/depsgraph/util') diff --git a/source/blender/depsgraph/util/depsgraph_util_function.h b/source/blender/depsgraph/util/depsgraph_util_function.h index f62efd76267..0f5582812f1 100644 --- a/source/blender/depsgraph/util/depsgraph_util_function.h +++ b/source/blender/depsgraph/util/depsgraph_util_function.h @@ -25,7 +25,7 @@ #ifndef __DEPSGRAPH_UTIL_FUNCTION_H__ #define __DEPSGRAPH_UTIL_FUNCTION_H__ -#if (__cplusplus > 199711L) || (defined(_MSC_VER) && _MSC_VER >= 1800) +#if (__cplusplus > 199711L) #include -- cgit v1.2.3 From e4cd4c383f13eb9705d9f5d3536c0b2b72e727bd Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Wed, 13 May 2015 06:10:49 +1000 Subject: Cleanup: style --- source/blender/depsgraph/util/depsgraph_util_function.h | 2 +- source/blender/depsgraph/util/depsgraph_util_pchanmap.h | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'source/blender/depsgraph/util') diff --git a/source/blender/depsgraph/util/depsgraph_util_function.h b/source/blender/depsgraph/util/depsgraph_util_function.h index 0f5582812f1..976a9d6cc2b 100644 --- a/source/blender/depsgraph/util/depsgraph_util_function.h +++ b/source/blender/depsgraph/util/depsgraph_util_function.h @@ -59,7 +59,7 @@ public: function() {}; function(void *) {} operator bool() const { return false; } - bool operator== (void*) { return false; } + bool operator== (void *) { return false; } template void operator() (T1) { diff --git a/source/blender/depsgraph/util/depsgraph_util_pchanmap.h b/source/blender/depsgraph/util/depsgraph_util_pchanmap.h index 5d27d84c0da..82ec8654bc5 100644 --- a/source/blender/depsgraph/util/depsgraph_util_pchanmap.h +++ b/source/blender/depsgraph/util/depsgraph_util_pchanmap.h @@ -24,8 +24,8 @@ * ***** END GPL LICENSE BLOCK ***** */ -#ifndef ___DEPSGRAPH_UTIL_PCHANMAP_H__ -#define ___DEPSGRAPH_UTIL_PCHANMAP_H__ +#ifndef __DEPSGRAPH_UTIL_PCHANMAP_H__ +#define __DEPSGRAPH_UTIL_PCHANMAP_H__ struct RootPChanMap { /* ctor and dtor - Create and free the internal map respectively. */ -- 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 ++++++ source/blender/depsgraph/util/depsgraph_util_cycle.h | 6 ++++++ source/blender/depsgraph/util/depsgraph_util_function.h | 6 ++++++ source/blender/depsgraph/util/depsgraph_util_hash.h | 6 ++++++ source/blender/depsgraph/util/depsgraph_util_map.h | 6 ++++++ source/blender/depsgraph/util/depsgraph_util_pchanmap.cc | 4 ++++ source/blender/depsgraph/util/depsgraph_util_pchanmap.h | 4 ++++ source/blender/depsgraph/util/depsgraph_util_set.h | 6 ++++++ source/blender/depsgraph/util/depsgraph_util_transitive.cc | 8 +++++++- source/blender/depsgraph/util/depsgraph_util_transitive.h | 6 ++++++ 10 files changed, 57 insertions(+), 1 deletion(-) (limited to 'source/blender/depsgraph/util') 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 diff --git a/source/blender/depsgraph/util/depsgraph_util_cycle.h b/source/blender/depsgraph/util/depsgraph_util_cycle.h index f827d85c16a..fac38b61057 100644 --- a/source/blender/depsgraph/util/depsgraph_util_cycle.h +++ b/source/blender/depsgraph/util/depsgraph_util_cycle.h @@ -19,6 +19,12 @@ * All rights reserved. * * Contributor(s): Sergey Sharybin + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/util/depsgraph_util_cycle.h + * \ingroup depsgraph */ #ifndef __DEPSGRAPH_UTIL_CYCLE_H__ diff --git a/source/blender/depsgraph/util/depsgraph_util_function.h b/source/blender/depsgraph/util/depsgraph_util_function.h index 976a9d6cc2b..74bf5de8ab6 100644 --- a/source/blender/depsgraph/util/depsgraph_util_function.h +++ b/source/blender/depsgraph/util/depsgraph_util_function.h @@ -20,6 +20,12 @@ * * Original Author: Lukas Toenne * Contributor(s): + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/util/depsgraph_util_function.h + * \ingroup depsgraph */ #ifndef __DEPSGRAPH_UTIL_FUNCTION_H__ diff --git a/source/blender/depsgraph/util/depsgraph_util_hash.h b/source/blender/depsgraph/util/depsgraph_util_hash.h index 0f5a85b3526..bc75627a026 100644 --- a/source/blender/depsgraph/util/depsgraph_util_hash.h +++ b/source/blender/depsgraph/util/depsgraph_util_hash.h @@ -20,6 +20,12 @@ * * Original Author: Brecht van Lommel * Contributor(s): Lukas Toenne + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/util/depsgraph_util_hash.h + * \ingroup depsgraph */ #ifndef __DEPSGRAPH_UTIL_HASH_H__ diff --git a/source/blender/depsgraph/util/depsgraph_util_map.h b/source/blender/depsgraph/util/depsgraph_util_map.h index 2951641431b..0eae1d79e34 100644 --- a/source/blender/depsgraph/util/depsgraph_util_map.h +++ b/source/blender/depsgraph/util/depsgraph_util_map.h @@ -20,6 +20,12 @@ * * Original Author: Brecht van Lommel * Contributor(s): Lukas Toenne + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/util/depsgraph_util_map.h + * \ingroup depsgraph */ #ifndef __DEPSGRAPH_UTIL_MAP_H__ diff --git a/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc b/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc index 36bd72108ed..80b37ec622d 100644 --- a/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc +++ b/source/blender/depsgraph/util/depsgraph_util_pchanmap.cc @@ -24,6 +24,10 @@ * ***** END GPL LICENSE BLOCK ***** */ +/** \file blender/depsgraph/util/depsgraph_util_pchanmap.cc + * \ingroup depsgraph + */ + #include "depsgraph_util_pchanmap.h" #include diff --git a/source/blender/depsgraph/util/depsgraph_util_pchanmap.h b/source/blender/depsgraph/util/depsgraph_util_pchanmap.h index 82ec8654bc5..b7f4c495933 100644 --- a/source/blender/depsgraph/util/depsgraph_util_pchanmap.h +++ b/source/blender/depsgraph/util/depsgraph_util_pchanmap.h @@ -24,6 +24,10 @@ * ***** END GPL LICENSE BLOCK ***** */ +/** \file blender/depsgraph/util/depsgraph_util_pchanmap.h + * \ingroup depsgraph + */ + #ifndef __DEPSGRAPH_UTIL_PCHANMAP_H__ #define __DEPSGRAPH_UTIL_PCHANMAP_H__ diff --git a/source/blender/depsgraph/util/depsgraph_util_set.h b/source/blender/depsgraph/util/depsgraph_util_set.h index 09fa5313920..008ec6b74ca 100644 --- a/source/blender/depsgraph/util/depsgraph_util_set.h +++ b/source/blender/depsgraph/util/depsgraph_util_set.h @@ -20,6 +20,12 @@ * * Original Author: Brecht van Lommel * Contributor(s): Lukas Toenne + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/util/depsgraph_util_set.h + * \ingroup depsgraph */ #ifndef __DEPSGRAPH_UTIL_SET_H__ diff --git a/source/blender/depsgraph/util/depsgraph_util_transitive.cc b/source/blender/depsgraph/util/depsgraph_util_transitive.cc index 9411d013c44..98192a9540f 100644 --- a/source/blender/depsgraph/util/depsgraph_util_transitive.cc +++ b/source/blender/depsgraph/util/depsgraph_util_transitive.cc @@ -18,8 +18,14 @@ * The Original Code is Copyright (C) 2015 Blender Foundation. * All rights reserved. * - * Contributor(s): Lukas Toenne + * Contributor(s): Lukas Toenne, * Sergey Sharybin, + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/util/depsgraph_util_transitive.cc + * \ingroup depsgraph */ extern "C" { diff --git a/source/blender/depsgraph/util/depsgraph_util_transitive.h b/source/blender/depsgraph/util/depsgraph_util_transitive.h index 8995c18eca0..a80a1d783d7 100644 --- a/source/blender/depsgraph/util/depsgraph_util_transitive.h +++ b/source/blender/depsgraph/util/depsgraph_util_transitive.h @@ -20,6 +20,12 @@ * * Contributor(s): Lukas Toenne * Sergey Sharybin, + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/util/depsgraph_util_transitive.h + * \ingroup depsgraph */ #ifndef __DEPSGRAPH_UTIL_TRANSITIVE_H__ -- cgit v1.2.3 From 907f804ad8a32b39018a51f9b4bfab359222068a Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Fri, 5 Jun 2015 03:37:14 +0500 Subject: Depsgraph: Fix typo in header guard comment --- source/blender/depsgraph/util/depsgraph_util_function.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'source/blender/depsgraph/util') diff --git a/source/blender/depsgraph/util/depsgraph_util_function.h b/source/blender/depsgraph/util/depsgraph_util_function.h index 74bf5de8ab6..a4301833408 100644 --- a/source/blender/depsgraph/util/depsgraph_util_function.h +++ b/source/blender/depsgraph/util/depsgraph_util_function.h @@ -109,4 +109,4 @@ void *function_bind(T func, #endif -#endif /* __DEPSGRAPH_UTIL_SET_H__ */ +#endif /* __DEPSGRAPH_UTIL_FUNCTION_H__ */ -- cgit v1.2.3