Orange; daily noodler update commit.

- Adding execution code for Node trees. Was a bit a puzzle, since I want
  it to be multithreading by design. This now is solved by defining a
  stack per tree for all data that's being written into. This stack, which
  resides now in the NodeTree itself, then can be allocated per thread.

- For testing pleasure, I've added a 'mix node' and a 'show node', so
  you can already see it do something. :)

- reshuffled structure, to put things nice together, and have easier node
  adding. Current state is still WIP though, structure might change.
  For the record; new file node_shaders.c will contain all shader node
  definitions, apart from the drawing callbacks.

Next: I'm going to check on Andrea's work on icons now, since this is very
much needed for true shader/composit work.
Now back to release work...

4 files changed, 327 insertions, 17 deletions

diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h
index a36fd7d9f4c..4146ebc71a0 100644
--- a/source/blender/blenkernel/BKE_node.h
+++ b/source/blender/blenkernel/BKE_node.h
@@ -43,6 +43,8 @@ struct ListBase;
 #define SOCK_OUT	2
 
 
+/* ************** GENERIC API *************** */
+
 void			nodeFreeNode(struct bNodeTree *ntree, struct bNode *node);
 void			nodeFreeTree(struct bNodeTree *ntree);
 
@@ -55,8 +57,20 @@ struct bNodeSocket *nodeAddSocket(struct bNode *node, int type, int where, int l
 struct bNodeLink *nodeFindLink(struct bNodeTree *ntree, struct bNodeSocket *from, struct bNodeSocket *to);
 int				nodeCountSocketLinks(struct bNodeTree *ntree, struct bNodeSocket *sock);
 
-void nodeSolveOrder(struct bNodeTree *ntree);
+void			nodeSolveOrder(struct bNodeTree *ntree);
+void			nodeExecTree(struct bNodeTree *ntree);
+
+/* ************** SHADER NODES *************** */
+
+/* types are needed to restore callbacks */
+#define SH_NODE_TEST		0
+#define SH_NODE_RGB			1
+#define SH_NODE_VALUE		2
+#define SH_NODE_MIX_RGB		3
+#define SH_NODE_SHOW_RGB	4
 
+struct bNode	*node_shader_add(struct bNodeTree *ntree, int type);
+void			node_shader_set_execfunc(struct bNode *node);
 
 #endif
 
diff --git a/source/blender/blenkernel/SConscript b/source/blender/blenkernel/SConscript
index c388c1d9382..11baca6ffca 100644
--- a/source/blender/blenkernel/SConscript
+++ b/source/blender/blenkernel/SConscript
@@ -44,6 +44,7 @@ source_files = ['intern/constraint.c',
                 'intern/property.c',
                 'intern/softbody.c',
 		'intern/node.c',
+		'intern/node_shaders.c',
                 'intern/texture.c']
 
 blenkernel_env.Append (CPPPATH = ['.',
diff --git a/source/blender/blenkernel/intern/node.c b/source/blender/blenkernel/intern/node.c
index 73bfe4ac7e3..3d568e4e391 100644
--- a/source/blender/blenkernel/intern/node.c
+++ b/source/blender/blenkernel/intern/node.c
@@ -35,12 +35,16 @@
 #include "BKE_blender.h"
 #include "BKE_node.h"
 
+#include "BLI_arithb.h"
 #include "BLI_blenlib.h"
 
 #include "MEM_guardedalloc.h"
 
 /* ************** Add stuff ********** */
 
+/* not very important, but the stack solver likes to know a maximum */
+#define MAX_SOCKET	64
+
 bNode *nodeAddNode(struct bNodeTree *ntree, char *name)
 {
 	bNode *node= MEM_callocN(sizeof(bNode), "new node");
@@ -185,23 +189,24 @@ int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
 	return tot;
 }
 
-/* ************** solve stuff *********** */
+/* ************** dependency stuff *********** */
 
 /* node is guaranteed to be not checked before */
 static int node_recurs_check(bNode *node, bNode ***nsort, int level)
 {
+	bNode *fromnode;
 	bNodeSocket *sock;
-	bNodeLink *link;
 	int has_inputlinks= 0;
 	
 	node->done= 1;
 	level++;
 	
 	for(sock= node->inputs.first; sock; sock= sock->next) {
-		for(link= sock->links.first; link; link= link->next) {
+		if(sock->link) {
 			has_inputlinks= 1;
-			if(link->fromnode->done==0) {
-				link->fromnode->level= node_recurs_check(link->fromnode, nsort, level);
+			fromnode= sock->link->fromnode;
+			if(fromnode->done==0) {
+				fromnode->level= node_recurs_check(fromnode, nsort, level);
 			}
 		}
 	}
@@ -222,20 +227,19 @@ void nodeSolveOrder(bNodeTree *ntree)
 	bNodeLink *link;
 	int a, totnode=0;
 	
-	/* move all links into the input sockets, to find dependencies */
+	/* set links pointers the input sockets, to find dependencies */
 	/* first clear data */
 	for(node= ntree->nodes.first; node; node= node->next) {
 		node->done= 0;
 		totnode++;
 		for(sock= node->inputs.first; sock; sock= sock->next)
-			sock->links.first= sock->links.last= NULL;
+			sock->link= NULL;
 	}
 	if(totnode==0)
 		return;
 	
-	while((link= ntree->links.first)) {
-		BLI_remlink(&ntree->links, link);
-		BLI_addtail(&link->tosock->links, link);
+	for(link= ntree->links.first; link; link= link->next) {
+		link->tosock->link= link;
 	}
 	
 	nsort= nodesort= MEM_callocN(totnode*sizeof(void *), "sorted node array");
@@ -262,13 +266,78 @@ void nodeSolveOrder(bNodeTree *ntree)
 	
 	MEM_freeN(nodesort);
 	
-	/* move links back */
+}
+
+/* ******************* executing ************* */
+
+
+void nodeBeginExecTree(bNodeTree *ntree)
+{
+	bNode *node;
+	bNodeSocket *sock;
+	int index= 0;
+	
+	if((ntree->init & NTREE_EXEC_SET)==0) {
+		for(node= ntree->nodes.first; node; node= node->next) {
+			if(ntree->type==NTREE_SHADER)
+				node_shader_set_execfunc(node);
+		}
+		ntree->init |= NTREE_EXEC_SET;
+	}
+	
+	/* create indices for stack */
 	for(node= ntree->nodes.first; node; node= node->next) {
-		for(sock= node->inputs.first; sock; sock= sock->next) {
-			while((link= sock->links.first)) {
-				BLI_remlink(&sock->links, link);
-				BLI_addtail(&ntree->links, link);
-			}
+		
+		for(sock= node->outputs.first; sock; sock= sock->next) {
+			sock->stack_index= index++;
+		}
+	}
+	if(index) {
+		ntree->stack= MEM_callocN(index*sizeof(bNodeStack), "node stack");
+	}
+}
+
+void nodeEndExecTree(bNodeTree *ntree)
+{
+	if(ntree->stack) {
+		MEM_freeN(ntree->stack);
+		ntree->stack= NULL;
+	}
+}
+
+static void node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **spp)
+{
+	static bNodeStack empty= {{1.0f, 1.0f, 1.0f, 1.0f}, NULL};
+	bNodeSocket *sock;
+	
+	/* build pointer stack */
+	for(sock= node->inputs.first; sock; sock= sock->next) {
+		if(sock->link)
+			*(spp++)= stack + sock->link->fromsock->stack_index;
+		else
+			*(spp++)= ∅	/* input is not written into */
+	}
+	
+	for(sock= node->outputs.first; sock; sock= sock->next) {
+		*(spp++)= stack + sock->stack_index;
+	}
+}
+
+/* nodes are presorted, so exec is in order of list */
+void nodeExecTree(bNodeTree *ntree)
+{
+	bNode *node;
+	bNodeStack *ns[MAX_SOCKET];	/* arbitrary... watch this */
+	
+	nodeBeginExecTree(ntree);
+	
+	for(node= ntree->nodes.first; node; node= node->next) {
+		if(node->execfunc) {
+			node_get_stack(node, ntree->stack, ns);
+			node->execfunc(node, ns);
 		}
 	}
+
+	nodeEndExecTree(ntree);
 }
+
diff --git a/source/blender/blenkernel/intern/node_shaders.c b/source/blender/blenkernel/intern/node_shaders.c
new file mode 100644
index 00000000000..74728abac9c
--- /dev/null
+++ b/source/blender/blenkernel/intern/node_shaders.c
@@ -0,0 +1,226 @@
+/**
+ * $Id$
+ *
+ * ***** 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2005 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include <stdlib.h>
+
+#include "DNA_ID.h"
+#include "DNA_node_types.h"
+
+#include "BKE_blender.h"
+#include "BKE_node.h"
+#include "BKE_utildefines.h"
+
+#include "BLI_arithb.h"
+#include "BLI_blenlib.h"
+
+#include "MEM_guardedalloc.h"
+
+/* **************** testnode ************ */
+
+static void blendcolor(float *col1, float *col2, float *output, float fac)
+{
+	output[0]= (1.0f-fac)*col1[0] + (fac)*col2[0];
+	output[1]= (1.0f-fac)*col1[1] + (fac)*col2[1];
+	output[2]= (1.0f-fac)*col1[2] + (fac)*col2[2];
+}
+
+static void node_shader_exec_test(bNode *node, bNodeStack **ns)
+{
+	
+	blendcolor(ns[0]->vec, ns[1]->vec, ns[2]->vec, 0.5);
+
+//	printvecf(node->name, ns[2]->vec);
+}
+
+static bNode *node_shader_add_test(bNodeTree *ntree)
+{
+	bNode *node= nodeAddNode(ntree, "TestNode");
+	static int tot= 0;
+	
+	sprintf(node->name, "Testnode%d", tot++);
+	node->type= SH_NODE_TEST;
+	node->width= 80.0f;
+	
+	/* add sockets */
+	nodeAddSocket(node, SOCK_RGBA, SOCK_IN, 1, "Col");
+	nodeAddSocket(node, SOCK_RGBA, SOCK_IN, 1, "Spec");
+	nodeAddSocket(node, SOCK_RGBA, SOCK_OUT, 0xFFF, "Diffuse");
+	
+	return node;
+}
+
+/* **************** value node ************ */
+
+static void node_shader_exec_value(bNode *node, bNodeStack **ns)
+{
+	/* no input node! */
+	ns[0]->vec[0]= node->ns.vec[0];
+//	printf("%s %f\n", node->name, ns[0]->vec[0]);
+}
+
+static bNode *node_shader_add_value(bNodeTree *ntree)
+{
+	bNode *node= nodeAddNode(ntree, "Value");
+	
+	node->type= SH_NODE_VALUE;
+	node->width= 80.0f;
+	node->prv_h= 20.0f;
+	
+	/* add sockets */
+	nodeAddSocket(node, SOCK_VALUE, SOCK_OUT, 0xFFF, "");
+	
+	return node;
+}
+
+/* **************** rgba node ************ */
+
+static void node_shader_exec_rgb(bNode *node, bNodeStack **ns)
+{
+	/* no input node! */
+	QUATCOPY(ns[0]->vec, node->ns.vec);
+	
+//	printvecf(node->name, ns[0]->vec);
+}
+
+static bNode *node_shader_add_rgb(bNodeTree *ntree)
+{
+	bNode *node= nodeAddNode(ntree, "RGB");
+	
+	node->type= SH_NODE_RGB;
+	node->width= 100.0f;
+	node->prv_h= 100.0f;
+	node->ns.vec[3]= 1.0f;		/* alpha init */
+	
+	/* add sockets */
+	nodeAddSocket(node, SOCK_RGBA, SOCK_OUT, 0xFFF, "");
+	
+	return node;
+}
+
+/* **************** mix rgba node ************ */
+
+static void node_shader_exec_mix_rgb(bNode *node, bNodeStack **ns)
+{
+	/* stack order is fac, col1, col2, out */
+	blendcolor(ns[1]->vec, ns[2]->vec, ns[3]->vec, ns[0]->vec[0]);
+}
+
+static bNode *node_shader_add_mix_rgb(bNodeTree *ntree)
+{
+	bNode *node= nodeAddNode(ntree, "Mix RGB");
+	
+	node->type= SH_NODE_MIX_RGB;
+	node->width= 80.0f;
+	node->prv_h= 0.0f;
+	
+	/* add sockets */
+	nodeAddSocket(node, SOCK_VALUE, SOCK_IN, 1, "Fac");
+	nodeAddSocket(node, SOCK_RGBA, SOCK_IN, 1, "Color1");
+	nodeAddSocket(node, SOCK_RGBA, SOCK_IN, 1, "Color2");
+	nodeAddSocket(node, SOCK_RGBA, SOCK_OUT, 0xFFF, "Color");
+	
+	return node;
+}
+
+
+/* **************** show rgba node ************ */
+
+static void node_shader_exec_show_rgb(bNode *node, bNodeStack **ns)
+{
+	/* only input node! */
+	QUATCOPY(node->ns.vec, ns[0]->vec);
+	
+//	printvecf(node->name, ns[0]->vec);
+}
+
+static bNode *node_shader_add_show_rgb(bNodeTree *ntree)
+{
+	bNode *node= nodeAddNode(ntree, "Show RGB");
+	
+	node->type= SH_NODE_SHOW_RGB;
+	node->width= 80.0f;
+	node->prv_h= 0.0f;
+	node->ns.vec[3]= 1.0f;		/* alpha init */
+	
+	/* add sockets */
+	nodeAddSocket(node, SOCK_RGBA, SOCK_IN, 1, "");
+	
+	return node;
+}
+
+
+/* **************** API for add ************** */
+
+bNode *node_shader_add(bNodeTree *ntree, int type)
+{
+	bNode *node= NULL;
+	
+	switch(type) {
+	case SH_NODE_TEST:
+		node= node_shader_add_test(ntree);
+		break;
+	case SH_NODE_VALUE:
+		node= node_shader_add_value(ntree);
+		break;
+	case SH_NODE_RGB:
+		node= node_shader_add_rgb(ntree);
+		break;
+	case SH_NODE_SHOW_RGB:
+		node= node_shader_add_show_rgb(ntree);
+		break;
+	case SH_NODE_MIX_RGB:
+		node= node_shader_add_mix_rgb(ntree);
+		break;
+	}
+	return node;
+}
+
+/* ******************* set the callbacks, called from UI, loader ***** */
+
+void node_shader_set_execfunc(bNode *node)
+{
+	switch(node->type) {
+	case SH_NODE_TEST:
+		node->execfunc= node_shader_exec_test;
+		break;
+	case SH_NODE_VALUE:
+		node->execfunc= node_shader_exec_value;
+		break;
+	case SH_NODE_RGB:
+		node->execfunc= node_shader_exec_rgb;
+		break;
+	case SH_NODE_SHOW_RGB:
+		node->execfunc= node_shader_exec_show_rgb;
+		break;
+	case SH_NODE_MIX_RGB:
+		node->execfunc= node_shader_exec_mix_rgb;
+		break;
+	}
+}
+