[Bf-blender-cvs] [8294452] master: Fix T46782: Updating Shaders very slow with complex nodegraph

[Sergey Sharybin]

Commit: 8294452b14fac54443f31fe11950d19370e27b43
Author: Sergey Sharybin
Date:   Wed Nov 25 13:46:51 2015 +0500
Branches: master
https://developer.blender.org/rB8294452b14fac54443f31fe11950d19370e27b43

Fix T46782: Updating Shaders very slow with complex nodegraph

The issue was caused by not really optimal graph traversal for gathering nodes
dependencies which could have exponential complexity with a long tree branches
connected with multiple connections between them.

Now we optimize the depth traversal and perform early output if the node was
already traversed.

Please note that this adds some limitations to the use of SVM compiler's
find_dependencies() in the cases when skip_node is not NULL and one wants to
perform dependencies find sequentially with the same set. This doesn't happen
in the code, but one should be aware of this.

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

M	intern/cycles/render/graph.cpp
M	intern/cycles/render/osl.cpp
M	intern/cycles/render/svm.cpp

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

diff --git a/intern/cycles/render/graph.cpp b/intern/cycles/render/graph.cpp
index 3e417d1..e888cb3 100644
--- a/intern/cycles/render/graph.cpp
+++ b/intern/cycles/render/graph.cpp
@@ -306,7 +306,7 @@ void ShaderGraph::find_dependencies(ShaderNodeSet& dependencies, ShaderInput *in
 	/* find all nodes that this input depends on directly and indirectly */
 	ShaderNode *node = (input->link)? input->link->parent: NULL;
 
-	if(node) {
+	if(node != NULL && dependencies.find(node) == dependencies.end()) {
 		foreach(ShaderInput *in, node->inputs)
 			find_dependencies(dependencies, in);
 
diff --git a/intern/cycles/render/osl.cpp b/intern/cycles/render/osl.cpp
index 4306931..4933ed6 100644
--- a/intern/cycles/render/osl.cpp
+++ b/intern/cycles/render/osl.cpp
@@ -702,7 +702,7 @@ void OSLCompiler::find_dependencies(ShaderNodeSet& dependencies, ShaderInput *in
 {
 	ShaderNode *node = (input->link)? input->link->parent: NULL;
 
-	if(node) {
+	if(node != NULL && dependencies.find(node) == dependencies.end()) {
 		foreach(ShaderInput *in, node->inputs)
 			if(!node_skip_input(node, in))
 				find_dependencies(dependencies, in);
diff --git a/intern/cycles/render/svm.cpp b/intern/cycles/render/svm.cpp
index fa22287..a4c7e7e 100644
--- a/intern/cycles/render/svm.cpp
+++ b/intern/cycles/render/svm.cpp
@@ -373,7 +373,11 @@ void SVMCompiler::find_dependencies(ShaderNodeSet& dependencies,
 {
 	ShaderNode *node = (input->link)? input->link->parent: NULL;
 
-	if(node && done.find(node) == done.end() && node != skip_node) {
+	if(node != NULL &&
+	   done.find(node) == done.end() &&
+	   node != skip_node &&
+	   dependencies.find(node) == dependencies.end())
+	{
 		foreach(ShaderInput *in, node->inputs)
 			if(!node_skip_input(node, in))
 				find_dependencies(dependencies, done, in, skip_node);