[Bf-blender-cvs] [c4c68a8] depsgraph_refactor: Depsgraph: Implement russian roulette cycles solver

[Sergey Sharybin]

Commit: c4c68a823b482ac6a67d68e707dd8be12e5d6cf0
Author: Sergey Sharybin
Date:   Wed Feb 4 19:34:04 2015 +0500
Branches: depsgraph_refactor
https://developer.blender.org/rBc4c68a823b482ac6a67d68e707dd8be12e5d6cf0

Depsgraph: Implement russian roulette cycles solver

The intention is to mark some relations from cycles as cyclic so
graph evaluation will ignore them when calculating number of pending
relations which are not satisfied yet.

This should unlock some rigs which are currently not possible to
evaluate at all because for cycle dependencies are never met.

In fact, with transitive relations reduction koro rig now is kinda
working. It's flickering but bones are not locked. What's weird is
that disabling transitive reduction makes some bones to not being
evaluated.

This is weird because it means either:

- Dependency cycle detector doesn't work 100% correct.
- Transitive reduction kills some extra relations which it shouldn't.
- We've got issue in graph traversal somewhere.

===================================================================

M	source/blender/depsgraph/intern/depsgraph.cpp
M	source/blender/depsgraph/intern/depsgraph_build.cpp
M	source/blender/depsgraph/intern/depsgraph_eval.cpp

===================================================================

diff --git a/source/blender/depsgraph/intern/depsgraph.cpp b/source/blender/depsgraph/intern/depsgraph.cpp
index 41f0dfb..8d15f32 100644
--- a/source/blender/depsgraph/intern/depsgraph.cpp
+++ b/source/blender/depsgraph/intern/depsgraph.cpp
@@ -371,6 +371,7 @@ DepsRelation::DepsRelation(DepsNode *from,
 	this->to = to;
 	this->type = type;
 	this->name = description;
+	this->flag = 0;
 
 	/* Hook it up to the nodes which use it. */
 	from->outlinks.insert(this);
diff --git a/source/blender/depsgraph/intern/depsgraph_build.cpp b/source/blender/depsgraph/intern/depsgraph_build.cpp
index 3542955..a5fc590 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.cpp
+++ b/source/blender/depsgraph/intern/depsgraph_build.cpp
@@ -607,6 +607,8 @@ static void deg_graph_detect_cycles(Depsgraph *graph)
 						       current->via_relation->name.c_str());
 						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;
diff --git a/source/blender/depsgraph/intern/depsgraph_eval.cpp b/source/blender/depsgraph/intern/depsgraph_eval.cpp
index 59b77f3..baa3a43 100644
--- a/source/blender/depsgraph/intern/depsgraph_eval.cpp
+++ b/source/blender/depsgraph/intern/depsgraph_eval.cpp
@@ -170,7 +170,9 @@ static void calculate_pending_parents(Depsgraph *graph, int layers)
 			     ++it_rel)
 			{
 				DepsRelation *rel = *it_rel;
-				if (rel->from->type == DEPSNODE_TYPE_OPERATION) {
+				if (rel->from->type == DEPSNODE_TYPE_OPERATION &&
+				    (rel->flag & DEPSREL_FLAG_CYCLIC) == 0)
+				{
 					OperationDepsNode *from = (OperationDepsNode *)rel->from;
 					if (from->flag & DEPSOP_FLAG_NEEDS_UPDATE) {
 						++node->num_links_pending;
@@ -256,8 +258,10 @@ static void schedule_children(TaskPool *pool,
 		if ((id_child->layers & layers) != 0 &&
 		    (child->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0)
 		{
-			BLI_assert(child->num_links_pending > 0);
-			atomic_sub_uint32(&child->num_links_pending, 1);
+			if ((rel->flag & DEPSREL_FLAG_CYCLIC) == 0) {
+				BLI_assert(child->num_links_pending > 0);
+				atomic_sub_uint32(&child->num_links_pending, 1);
+			}
 
 			if (child->num_links_pending == 0) {
 				BLI_spin_lock(&graph->lock);