320bead1c6145b4cd99684044cba6fb4e1cddd4c
[blender.git] / source / blender / blenkernel / intern / node.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. 
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2005 Blender Foundation.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): Bob Holcomb.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 #ifdef WITH_PYTHON
31 #include <Python.h>
32 #endif
33
34 #include "MEM_guardedalloc.h"
35
36 #include <stdlib.h>
37 #include <stddef.h>
38 #include <string.h>
39 #include <limits.h>
40
41 #include "DNA_anim_types.h"
42 #include "DNA_action_types.h"
43 #include "DNA_node_types.h"
44
45 #include "BLI_listbase.h"
46
47 #include "RNA_access.h"
48
49 #include "BKE_animsys.h"
50 #include "BKE_action.h"
51 #include "BKE_fcurve.h"
52 #include "BKE_node.h"
53 #include "BKE_utildefines.h"
54 #include "BKE_node.h"
55
56 #include "PIL_time.h"
57
58 #include "CMP_node.h"
59 #include "intern/CMP_util.h"    /* stupid include path... */
60
61 #include "SHD_node.h"
62 #include "TEX_node.h"
63 #include "intern/TEX_util.h"
64
65 #include "GPU_material.h"
66
67 static ListBase empty_list = {NULL, NULL};
68 ListBase node_all_composit = {NULL, NULL};
69 ListBase node_all_shaders = {NULL, NULL};
70 ListBase node_all_textures = {NULL, NULL};
71
72 /* ************** Type stuff **********  */
73
74 static bNodeType *node_get_type(bNodeTree *ntree, int type, ID *id)
75 {
76         bNodeType *ntype = ntree->alltypes.first;
77         for(; ntype; ntype= ntype->next)
78                 if(ntype->type==type && id==ntype->id )
79                         return ntype;
80         
81         return NULL;
82 }
83
84 void ntreeInitTypes(bNodeTree *ntree)
85 {
86         bNode *node, *next;
87         
88         if(ntree->type==NTREE_SHADER)
89                 ntree->alltypes= node_all_shaders;
90         else if(ntree->type==NTREE_COMPOSIT)
91                 ntree->alltypes= node_all_composit;
92         else if(ntree->type==NTREE_TEXTURE)
93                 ntree->alltypes= node_all_textures;
94         else {
95                 ntree->alltypes= empty_list;
96                 printf("Error: no type definitions for nodes\n");
97         }
98         
99         for(node= ntree->nodes.first; node; node= next) {
100                 next= node->next;
101                 if(node->type==NODE_DYNAMIC) {
102                         bNodeType *stype= NULL;
103                         if(node->id==NULL) { /* empty script node */
104                                 stype= node_get_type(ntree, node->type, NULL);
105                         } else { /* not an empty script node */
106                                 stype= node_get_type(ntree, node->type, node->id);
107                                 if(!stype) {
108                                         stype= node_get_type(ntree, node->type, NULL);
109                                         /* needed info if the pynode script fails now: */
110                                         if (node->id) node->storage= ntree;
111                                 } else {
112                                         node->custom1= 0;
113                                         node->custom1= BSET(node->custom1,NODE_DYNAMIC_ADDEXIST);
114                                 }
115                         }
116                         node->typeinfo= stype;
117                         if(node->typeinfo)
118                                 node->typeinfo->initfunc(node);
119                 } else {
120                         node->typeinfo= node_get_type(ntree, node->type, NULL);
121                 }
122
123                 if(node->typeinfo==NULL) {
124                         printf("Error: Node type %s doesn't exist anymore, removed\n", node->name);
125                         nodeFreeNode(ntree, node);
126                 }
127         }
128                         
129         ntree->init |= NTREE_TYPE_INIT;
130 }
131
132 /* updates node with (modified) bNodeType.. this should be done for all trees */
133 void ntreeUpdateType(bNodeTree *ntree, bNodeType *ntype)
134 {
135         bNode *node;
136
137         for(node= ntree->nodes.first; node; node= node->next) {
138                 if(node->typeinfo== ntype) {
139                         nodeUpdateType(ntree, node, ntype);
140                 }
141         }
142 }
143
144 /* only used internal... we depend on type definitions! */
145 static bNodeSocket *node_add_socket_type(ListBase *lb, bNodeSocketType *stype)
146 {
147         bNodeSocket *sock= MEM_callocN(sizeof(bNodeSocket), "sock");
148         
149         BLI_strncpy(sock->name, stype->name, NODE_MAXSTR);
150         if(stype->limit==0) sock->limit= 0xFFF;
151         else sock->limit= stype->limit;
152         sock->type= stype->type;
153         
154         sock->ns.vec[0]= stype->val1;
155         sock->ns.vec[1]= stype->val2;
156         sock->ns.vec[2]= stype->val3;
157         sock->ns.vec[3]= stype->val4;
158         sock->ns.min= stype->min;
159         sock->ns.max= stype->max;
160         
161         if(lb)
162                 BLI_addtail(lb, sock);
163
164         return sock;
165 }
166
167 static bNodeSocket *node_add_group_socket(ListBase *lb, bNodeSocket *gsock)
168 {
169         bNodeSocket *sock= MEM_callocN(sizeof(bNodeSocket), "sock");
170         
171         /* make a copy of the group socket */
172         *sock = *gsock;
173         sock->link = NULL;
174         sock->next = sock->prev = NULL;
175         sock->new_sock = NULL;
176         sock->ns.data = NULL;
177         
178         sock->own_index = gsock->own_index;
179         sock->groupsock = gsock;
180         /* XXX hack: group socket input/output roles are inverted internally,
181          * need to change the limit value when making actual node sockets from them.
182          */
183         sock->limit = (gsock->limit==1 ? 0xFFF : 1);
184         
185         if(lb)
186                 BLI_addtail(lb, sock);
187
188         return sock;
189 }
190
191 static void node_rem_socket(bNodeTree *ntree, ListBase *lb, bNodeSocket *sock)
192 {
193         bNodeLink *link, *next;
194         
195         for(link= ntree->links.first; link; link= next) {
196                 next= link->next;
197                 if(link->fromsock==sock || link->tosock==sock) {
198                         nodeRemLink(ntree, link);
199                 }
200         }
201         
202         BLI_remlink(lb, sock);
203         MEM_freeN(sock);
204 }
205
206 static bNodeSocket *verify_socket(ListBase *lb, bNodeSocketType *stype)
207 {
208         bNodeSocket *sock;
209         
210         for(sock= lb->first; sock; sock= sock->next) {
211                 if(strncmp(sock->name, stype->name, NODE_MAXSTR)==0)
212                         break;
213         }
214         if(sock) {
215                 sock->type= stype->type;                /* in future, read this from tydefs! */
216                 if(stype->limit==0) sock->limit= 0xFFF;
217                 else sock->limit= stype->limit;
218                 
219                 sock->ns.min= stype->min;
220                 sock->ns.max= stype->max;
221                 
222                 BLI_remlink(lb, sock);
223                 
224                 return sock;
225         }
226         else {
227                 return node_add_socket_type(NULL, stype);
228         }
229 }
230
231 static bNodeSocket *verify_group_socket(ListBase *lb, bNodeSocket *gsock)
232 {
233         bNodeSocket *sock;
234         
235         for(sock= lb->first; sock; sock= sock->next) {
236                 if(sock->own_index==gsock->own_index)
237                                 break;
238         }
239         if(sock) {
240                 sock->groupsock = gsock;
241                 
242                 strcpy(sock->name, gsock->name);
243                 sock->type= gsock->type;
244                 
245                 /* XXX hack: group socket input/output roles are inverted internally,
246                  * need to change the limit value when making actual node sockets from them.
247                  */
248                 sock->limit = (gsock->limit==1 ? 0xFFF : 1);
249                 
250                 sock->ns.min= gsock->ns.min;
251                 sock->ns.max= gsock->ns.max;
252                 
253                 BLI_remlink(lb, sock);
254                 
255                 return sock;
256         }
257         else {
258                 return node_add_group_socket(NULL, gsock);
259         }
260 }
261
262 static void verify_socket_list(bNodeTree *ntree, ListBase *lb, bNodeSocketType *stype_first)
263 {
264         bNodeSocketType *stype;
265         
266         /* no inputs anymore? */
267         if(stype_first==NULL) {
268                 while(lb->first)
269                         node_rem_socket(ntree, lb, lb->first);
270         }
271         else {
272                 /* step by step compare */
273                 stype= stype_first;
274                 while(stype->type != -1) {
275                         stype->sock= verify_socket(lb, stype);
276                         stype++;
277                 }
278                 /* leftovers are removed */
279                 while(lb->first)
280                         node_rem_socket(ntree, lb, lb->first);
281                 /* and we put back the verified sockets */
282                 stype= stype_first;
283                 while(stype->type != -1) {
284                         BLI_addtail(lb, stype->sock);
285                         stype++;
286                 }
287         }
288 }
289
290 static void verify_group_socket_list(bNodeTree *ntree, ListBase *lb, ListBase *glb)
291 {
292         bNodeSocket *gsock;
293         
294         /* step by step compare */
295         for (gsock= glb->first; gsock; gsock=gsock->next) {
296                 /* abusing new_sock pointer for verification here! only used inside this function */
297                 gsock->new_sock= verify_group_socket(lb, gsock);
298         }
299         /* leftovers are removed */
300         while(lb->first)
301                 node_rem_socket(ntree, lb, lb->first);
302         /* and we put back the verified sockets */
303         for (gsock= glb->first; gsock; gsock=gsock->next) {
304                 BLI_addtail(lb, gsock->new_sock);
305                 gsock->new_sock = NULL;
306         }
307 }
308
309 void nodeVerifyType(bNodeTree *ntree, bNode *node)
310 {
311         /* node groups don't have static sock lists, but use external sockets from the tree instead */
312         if (node->type==NODE_GROUP) {
313                 bNodeTree *ngroup= (bNodeTree*)node->id;
314                 if (ngroup) {
315                         verify_group_socket_list(ntree, &node->inputs, &ngroup->inputs);
316                         verify_group_socket_list(ntree, &node->outputs, &ngroup->outputs);
317                 }
318         }
319         else {
320                 bNodeType *ntype= node->typeinfo;
321                 if(ntype) {
322                         verify_socket_list(ntree, &node->inputs, ntype->inputs);
323                         verify_socket_list(ntree, &node->outputs, ntype->outputs);
324                 }
325         }
326 }
327
328 void ntreeVerifyTypes(bNodeTree *ntree)
329 {
330         bNode *node;
331         
332         /* if((ntree->init & NTREE_TYPE_INIT)==0) */
333         ntreeInitTypes(ntree);
334
335         /* check inputs and outputs, and remove or insert them */
336         for(node= ntree->nodes.first; node; node= node->next)
337                 nodeVerifyType(ntree, node);
338         
339 }
340
341 /* ************** Group stuff ********** */
342
343 /* XXX group typeinfo struct is used directly in ntreeMakeOwnType, needs cleanup */
344 static bNodeType ntype_group;
345
346 /* groups display their internal tree name as label */
347 static const char *group_label(bNode *node)
348 {
349         return node->id->name+2;
350 }
351
352 void register_node_type_group(ListBase *lb)
353 {
354         node_type_base(&ntype_group, NODE_GROUP, "Group", NODE_CLASS_GROUP, NODE_OPTIONS, NULL, NULL);
355         node_type_size(&ntype_group, 120, 60, 200);
356         node_type_label(&ntype_group, group_label);
357         
358         nodeRegisterType(lb, &ntype_group);
359 }
360
361 static bNodeSocket *find_group_node_input(bNode *gnode, bNodeSocket *gsock)
362 {
363         bNodeSocket *sock;
364         for (sock=gnode->inputs.first; sock; sock=sock->next)
365                 if (sock->groupsock == gsock)
366                         return sock;
367         return NULL;
368 }
369
370 static bNodeSocket *find_group_node_output(bNode *gnode, bNodeSocket *gsock)
371 {
372         bNodeSocket *sock;
373         for (sock=gnode->outputs.first; sock; sock=sock->next)
374                 if (sock->groupsock == gsock)
375                         return sock;
376         return NULL;
377 }
378
379 bNode *nodeMakeGroupFromSelected(bNodeTree *ntree)
380 {
381         bNodeLink *link, *linkn;
382         bNode *node, *gnode, *nextn;
383         bNodeTree *ngroup;
384         bNodeSocket *gsock;
385         ListBase anim_basepaths = {NULL, NULL};
386         float min[2], max[2];
387         int totnode=0;
388         
389         INIT_MINMAX2(min, max);
390         
391         /* is there something to group? also do some clearing */
392         for(node= ntree->nodes.first; node; node= node->next) {
393                 if(node->flag & NODE_SELECT) {
394                         /* no groups in groups */
395                         if(node->type==NODE_GROUP)
396                                 return NULL;
397                         DO_MINMAX2( (&node->locx), min, max);
398                         totnode++;
399                 }
400                 node->done= 0;
401         }
402         if(totnode==0) return NULL;
403         
404         /* check if all connections are OK, no unselected node has both
405                 inputs and outputs to a selection */
406         for(link= ntree->links.first; link; link= link->next) {
407                 if(link->fromnode && link->tonode && link->fromnode->flag & NODE_SELECT)
408                         link->tonode->done |= 1;
409                 if(link->fromnode && link->tonode && link->tonode->flag & NODE_SELECT)
410                         link->fromnode->done |= 2;
411         }       
412         
413         for(node= ntree->nodes.first; node; node= node->next) {
414                 if((node->flag & NODE_SELECT)==0)
415                         if(node->done==3)
416                                 break;
417         }
418         if(node) 
419                 return NULL;
420         
421         /* OK! new nodetree */
422         ngroup= ntreeAddTree("NodeGroup", ntree->type, TRUE);
423         
424         /* move nodes over */
425         for(node= ntree->nodes.first; node; node= nextn) {
426                 nextn= node->next;
427                 if(node->flag & NODE_SELECT) {
428                         /* keep track of this node's RNA "base" path (the part of the pat identifying the node) 
429                          * if the old nodetree has animation data which potentially covers this node
430                          */
431                         if (ntree->adt) {
432                                 PointerRNA ptr;
433                                 char *path;
434                                 
435                                 RNA_pointer_create(&ntree->id, &RNA_Node, node, &ptr);
436                                 path = RNA_path_from_ID_to_struct(&ptr);
437                                 
438                                 if (path)
439                                         BLI_addtail(&anim_basepaths, BLI_genericNodeN(path));
440                         }
441                         
442                         /* change node-collection membership */
443                         BLI_remlink(&ntree->nodes, node);
444                         BLI_addtail(&ngroup->nodes, node);
445                         
446                         node->locx-= 0.5f*(min[0]+max[0]);
447                         node->locy-= 0.5f*(min[1]+max[1]);
448                 }
449         }
450
451         /* move animation data over */
452         if (ntree->adt) {
453                 LinkData *ld, *ldn=NULL;
454                 
455                 BKE_animdata_separate_by_basepath(&ntree->id, &ngroup->id, &anim_basepaths);
456                 
457                 /* paths + their wrappers need to be freed */
458                 for (ld = anim_basepaths.first; ld; ld = ldn) {
459                         ldn = ld->next;
460                         
461                         MEM_freeN(ld->data);
462                         BLI_freelinkN(&anim_basepaths, ld);
463                 }
464         }
465         
466         /* make group node */
467         gnode= nodeAddNodeType(ntree, NODE_GROUP, ngroup, NULL);
468         gnode->locx= 0.5f*(min[0]+max[0]);
469         gnode->locy= 0.5f*(min[1]+max[1]);
470         
471         /* relink external sockets */
472         for(link= ntree->links.first; link; link= linkn) {
473                 linkn= link->next;
474                 
475                 if(link->fromnode && link->tonode && (link->fromnode->flag & link->tonode->flag & NODE_SELECT)) {
476                         BLI_remlink(&ntree->links, link);
477                         BLI_addtail(&ngroup->links, link);
478                 }
479                 else if(link->tonode && (link->tonode->flag & NODE_SELECT)) {
480                         gsock = nodeGroupExposeSocket(ngroup, link->tosock, SOCK_IN);
481                         link->tosock->link = nodeAddLink(ngroup, NULL, gsock, link->tonode, link->tosock);
482                         link->tosock = node_add_group_socket(&gnode->inputs, gsock);
483                         link->tonode = gnode;
484                 }
485                 else if(link->fromnode && (link->fromnode->flag & NODE_SELECT)) {
486                         /* search for existing group node socket */
487                         for (gsock=ngroup->outputs.first; gsock; gsock=gsock->next)
488                                 if (gsock->link && gsock->link->fromsock==link->fromsock)
489                                         break;
490                         if (!gsock) {
491                                 gsock = nodeGroupExposeSocket(ngroup, link->fromsock, SOCK_OUT);
492                                 gsock->link = nodeAddLink(ngroup, link->fromnode, link->fromsock, NULL, gsock);
493                                 link->fromsock = node_add_group_socket(&gnode->outputs, gsock);
494                         }
495                         else
496                                 link->fromsock = find_group_node_output(gnode, gsock);
497                         link->fromnode = gnode;
498                 }
499         }
500
501         /* update node levels */
502         ntreeSolveOrder(ntree);
503
504         return gnode;
505 }
506
507 /* here's a nasty little one, need to check users... */
508 /* should become callbackable... */
509 void nodeGroupVerify(bNodeTree *ngroup)
510 {
511         /* group changed, so we rebuild the type definition */
512 //      ntreeMakeGroupSockets(ngroup);
513         
514         if(ngroup->type==NTREE_SHADER) {
515                 Material *ma;
516                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
517                         if(ma->nodetree) {
518                                 bNode *node;
519                                 for(node= ma->nodetree->nodes.first; node; node= node->next)
520                                         if(node->id == (ID *)ngroup)
521                                                 nodeVerifyType(ma->nodetree, node);
522                         }
523                 }
524         }
525         else if(ngroup->type==NTREE_COMPOSIT) {
526                 Scene *sce;
527                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
528                         if(sce->nodetree) {
529                                 bNode *node;
530                                 for(node= sce->nodetree->nodes.first; node; node= node->next)
531                                         if(node->id == (ID *)ngroup)
532                                                 nodeVerifyType(sce->nodetree, node);
533                         }
534                 }
535         }
536         else if(ngroup->type==NTREE_TEXTURE) {
537                 Tex *tx;
538                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
539                         if(tx->nodetree) {
540                                 bNode *node;
541                                 for(node= tx->nodetree->nodes.first; node; node= node->next)
542                                         if(node->id == (ID *)ngroup)
543                                                 nodeVerifyType(tx->nodetree, node);
544                         }
545                 }
546         }
547 }
548
549 /* also to check all users of groups. Now only used in editor for hide/unhide */
550 /* should become callbackable? */
551 void nodeGroupSocketUseFlags(bNodeTree *ngroup)
552 {
553         bNode *node;
554         bNodeSocket *sock;
555
556         /* clear flags */
557         for(node= ngroup->nodes.first; node; node= node->next) {
558                 for(sock= node->inputs.first; sock; sock= sock->next)
559                         sock->flag &= ~SOCK_IN_USE;
560                 for(sock= node->outputs.first; sock; sock= sock->next)
561                         sock->flag &= ~SOCK_IN_USE;
562         }
563         
564         /* tag all thats in use */
565         if(ngroup->type==NTREE_SHADER) {
566                 Material *ma;
567                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
568                         if(ma->nodetree) {
569                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
570                                         if(node->id==&ngroup->id) {
571                                                 for(sock= node->inputs.first; sock; sock= sock->next)
572                                                         if(sock->link)
573                                                                 if(sock->groupsock) 
574                                                                         sock->groupsock->flag |= SOCK_IN_USE;
575                                                 for(sock= node->outputs.first; sock; sock= sock->next)
576                                                         if(nodeCountSocketLinks(ma->nodetree, sock))
577                                                                 if(sock->groupsock) 
578                                                                         sock->groupsock->flag |= SOCK_IN_USE;
579                                         }
580                                 }
581                         }
582                 }
583         }
584         else if(ngroup->type==NTREE_COMPOSIT) {
585                 Scene *sce;
586                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
587                         if(sce->nodetree) {
588                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
589                                         if(node->id==(ID *)ngroup) {
590                                                 for(sock= node->inputs.first; sock; sock= sock->next)
591                                                         if(sock->link)
592                                                                 if(sock->groupsock) 
593                                                                         sock->groupsock->flag |= SOCK_IN_USE;
594                                                 for(sock= node->outputs.first; sock; sock= sock->next)
595                                                         if(nodeCountSocketLinks(sce->nodetree, sock))
596                                                                 if(sock->groupsock) 
597                                                                         sock->groupsock->flag |= SOCK_IN_USE;
598                                         }
599                                 }
600                         }
601                 }
602         }
603         else if(ngroup->type==NTREE_TEXTURE) {
604                 Tex *tx;
605                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
606                         if(tx->nodetree) {
607                                 for(node= tx->nodetree->nodes.first; node; node= node->next) {
608                                         if(node->id==(ID *)ngroup) {
609                                                 for(sock= node->inputs.first; sock; sock= sock->next)
610                                                         if(sock->link)
611                                                                 if(sock->groupsock) 
612                                                                         sock->groupsock->flag |= SOCK_IN_USE;
613                                                 for(sock= node->outputs.first; sock; sock= sock->next)
614                                                         if(nodeCountSocketLinks(tx->nodetree, sock))
615                                                                 if(sock->groupsock) 
616                                                                         sock->groupsock->flag |= SOCK_IN_USE;
617                                         }
618                                 }
619                         }
620                 }
621         }
622         
623 }
624 /* finds a node based on its name */
625 bNode *nodeFindNodebyName(bNodeTree *ntree, const char *name)
626 {
627         return BLI_findstring(&ntree->nodes, name, offsetof(bNode, name));
628 }
629
630 /* finds a node based on given socket */
631 int nodeFindNode(bNodeTree *ntree, bNodeSocket *sock, bNode **nodep, int *sockindex, int *in_out)
632 {
633         bNode *node;
634         bNodeSocket *tsock;
635         int index= 0;
636         
637         for(node= ntree->nodes.first; node; node= node->next) {
638                 for(index=0, tsock= node->inputs.first; tsock; tsock= tsock->next, index++) {
639                         if(tsock==sock) {
640                                 if (in_out) *in_out= SOCK_IN;
641                                 break;
642                         }
643                 }
644                 if(tsock)
645                         break;
646                 for(index=0, tsock= node->outputs.first; tsock; tsock= tsock->next, index++) {
647                         if(tsock==sock) {
648                                 if (in_out) *in_out= SOCK_OUT;
649                                 break;
650                         }
651                 }
652                 if(tsock)
653                         break;
654         }
655
656         if(node) {
657                 *nodep= node;
658                 if(sockindex) *sockindex= index;
659                 return 1;
660         }
661         
662         *nodep= NULL;
663         return 0;
664 }
665
666 /* returns 1 if its OK */
667 int nodeGroupUnGroup(bNodeTree *ntree, bNode *gnode)
668 {
669         bNodeLink *link, *linkn;
670         bNode *node, *nextn;
671         bNodeTree *ngroup, *wgroup;
672         ListBase anim_basepaths = {NULL, NULL};
673         
674         ngroup= (bNodeTree *)gnode->id;
675         if(ngroup==NULL) return 0;
676         
677         /* clear new pointers, set in copytree */
678         for(node= ntree->nodes.first; node; node= node->next)
679                 node->new_node= NULL;
680         
681         /* wgroup is a temporary copy of the NodeTree we're merging in
682          *      - all of wgroup's nodes are transferred across to their new home
683          *      - ngroup (i.e. the source NodeTree) is left unscathed
684          */
685         wgroup= ntreeCopyTree(ngroup);
686         
687         /* add the nodes into the ntree */
688         for(node= wgroup->nodes.first; node; node= nextn) {
689                 nextn= node->next;
690                 
691                 /* keep track of this node's RNA "base" path (the part of the pat identifying the node) 
692                  * if the old nodetree has animation data which potentially covers this node
693                  */
694                 if (wgroup->adt) {
695                         PointerRNA ptr;
696                         char *path;
697                         
698                         RNA_pointer_create(&wgroup->id, &RNA_Node, node, &ptr);
699                         path = RNA_path_from_ID_to_struct(&ptr);
700                         
701                         if (path)
702                                 BLI_addtail(&anim_basepaths, BLI_genericNodeN(path));
703                 }
704                 
705                 /* migrate node */
706                 BLI_remlink(&wgroup->nodes, node);
707                 BLI_addtail(&ntree->nodes, node);
708                 
709                 node->locx+= gnode->locx;
710                 node->locy+= gnode->locy;
711                 
712                 node->flag |= NODE_SELECT;
713         }
714         
715         /* restore external links to and from the gnode */
716         for(link= ntree->links.first; link; link= link->next) {
717                 if (link->fromnode==gnode) {
718                         if (link->fromsock->groupsock) {
719                                 bNodeSocket *gsock= link->fromsock->groupsock;
720                                 if (gsock->link) {
721                                         if (gsock->link->fromnode) {
722                                                 /* NB: using the new internal copies here! the groupsock pointer still maps to the old tree */
723                                                 link->fromnode = (gsock->link->fromnode ? gsock->link->fromnode->new_node : NULL);
724                                                 link->fromsock = gsock->link->fromsock->new_sock;
725                                         }
726                                         else {
727                                                 /* group output directly maps to group input */
728                                                 bNodeSocket *insock= find_group_node_input(gnode, gsock->link->fromsock);
729                                                 if (insock->link) {
730                                                         link->fromnode = insock->link->fromnode;
731                                                         link->fromsock = insock->link->fromsock;
732                                                 }
733                                         }
734                                 }
735                                 else {
736                                         /* constant group output: copy the stack value to the external socket.
737                                          * the link is kept here until all possible external users have been fixed.
738                                          */
739                                         QUATCOPY(link->tosock->ns.vec, gsock->ns.vec);
740                                 }
741                         }
742                 }
743         }
744         /* remove internal output links, these are not used anymore */
745         for(link=wgroup->links.first; link; link= linkn) {
746                 linkn = link->next;
747                 if (!link->tonode)
748                         nodeRemLink(wgroup, link);
749         }
750         /* restore links from internal nodes */
751         for(link= wgroup->links.first; link; link= link->next) {
752                 /* indicates link to group input */
753                 if (!link->fromnode) {
754                         /* NB: can't use find_group_node_input here,
755                          * because gnode sockets still point to the old tree!
756                          */
757                         bNodeSocket *insock;
758                         for (insock= gnode->inputs.first; insock; insock= insock->next)
759                                 if (insock->groupsock->new_sock == link->fromsock)
760                                         break;
761                         if (insock->link) {
762                                 link->fromnode = insock->link->fromnode;
763                                 link->fromsock = insock->link->fromsock;
764                         }
765                         else {
766                                 /* uses group constant input. copy the input value and remove the dead link. */
767                                 QUATCOPY(link->tosock->ns.vec, insock->ns.vec);
768                                 nodeRemLink(wgroup, link);
769                         }
770                 }
771         }
772         
773         /* add internal links to the ntree */
774         for(link= wgroup->links.first; link; link= linkn) {
775                 linkn= link->next;
776                 BLI_remlink(&wgroup->links, link);
777                 BLI_addtail(&ntree->links, link);
778         }
779         
780         /* and copy across the animation */
781         if (wgroup->adt) {
782                 LinkData *ld, *ldn=NULL;
783                 bAction *waction;
784                 
785                 /* firstly, wgroup needs to temporary dummy action that can be destroyed, as it shares copies */
786                 waction = wgroup->adt->action = copy_action(wgroup->adt->action);
787                 
788                 /* now perform the moving */
789                 BKE_animdata_separate_by_basepath(&wgroup->id, &ntree->id, &anim_basepaths);
790                 
791                 /* paths + their wrappers need to be freed */
792                 for (ld = anim_basepaths.first; ld; ld = ldn) {
793                         ldn = ld->next;
794                         
795                         MEM_freeN(ld->data);
796                         BLI_freelinkN(&anim_basepaths, ld);
797                 }
798                 
799                 /* free temp action too */
800                 free_libblock(&G.main->action, waction);
801         }
802         
803         /* delete the group instance. this also removes old input links! */
804         nodeFreeNode(ntree, gnode);
805         
806         /* free the group tree (takes care of user count) */
807         free_libblock(&G.main->nodetree, wgroup);
808         
809         /* solve order goes fine, but the level tags not... doing it twice works for now. solve this once */
810         /* XXX is this still necessary with new groups? it may have been caused by non-updated sock->link pointers. lukas */
811         ntreeSolveOrder(ntree);
812         ntreeSolveOrder(ntree);
813
814         return 1;
815 }
816
817 void nodeGroupCopy(bNode *gnode)
818 {
819         bNodeSocket *sock;
820
821         gnode->id->us--;
822         gnode->id= (ID *)ntreeCopyTree((bNodeTree *)gnode->id);
823
824         /* new_sock was set in nodeCopyNode */
825         for(sock=gnode->inputs.first; sock; sock=sock->next)
826                 if(sock->groupsock)
827                         sock->groupsock= sock->groupsock->new_sock;
828
829         for(sock=gnode->outputs.first; sock; sock=sock->next)
830                 if(sock->groupsock)
831                         sock->groupsock= sock->groupsock->new_sock;
832 }
833
834 bNodeSocket *nodeGroupAddSocket(bNodeTree *ngroup, const char *name, int type, int in_out)
835 {
836         bNodeSocket *gsock = MEM_callocN(sizeof(bNodeSocket), "bNodeSocket");
837         
838         strncpy(gsock->name, name, sizeof(gsock->name));
839         gsock->type = type;
840         gsock->ns.sockettype = type;
841         gsock->ns.min = INT_MIN;
842         gsock->ns.max = INT_MAX;
843         zero_v4(gsock->ns.vec);
844         gsock->ns.data = NULL;
845         gsock->flag = 0;
846
847         gsock->next = gsock->prev = NULL;
848         gsock->new_sock = NULL;
849         gsock->link = NULL;
850         gsock->ns.data = NULL;
851         /* assign new unique index */
852         gsock->own_index = ngroup->cur_index++;
853         gsock->limit = (in_out==SOCK_IN ? 0xFFF : 1);
854         
855         BLI_addtail(in_out==SOCK_IN ? &ngroup->inputs : &ngroup->outputs, gsock);
856         
857         return gsock;
858 }
859
860 bNodeSocket *nodeGroupExposeSocket(bNodeTree *ngroup, bNodeSocket *sock, int in_out)
861 {
862         bNodeSocket *gsock= nodeGroupAddSocket(ngroup, sock->name, sock->type, in_out);
863         /* initialize the default socket value */
864         QUATCOPY(gsock->ns.vec, sock->ns.vec);
865         return gsock;
866 }
867
868 void nodeGroupExposeAllSockets(bNodeTree *ngroup)
869 {
870         bNode *node;
871         bNodeSocket *sock, *gsock;
872         
873         for (node=ngroup->nodes.first; node; node=node->next) {
874                 for (sock=node->inputs.first; sock; sock=sock->next) {
875                         if (!sock->link && !(sock->flag & SOCK_HIDDEN)) {
876                                 gsock = nodeGroupAddSocket(ngroup, sock->name, sock->type, SOCK_IN);
877                                 /* initialize the default socket value */
878                                 QUATCOPY(gsock->ns.vec, sock->ns.vec);
879                                 sock->link = nodeAddLink(ngroup, NULL, gsock, node, sock);
880                         }
881                 }
882                 for (sock=node->outputs.first; sock; sock=sock->next) {
883                         if (nodeCountSocketLinks(ngroup, sock)==0 && !(sock->flag & SOCK_HIDDEN)) {
884                                 gsock = nodeGroupAddSocket(ngroup, sock->name, sock->type, SOCK_OUT);
885                                 /* initialize the default socket value */
886                                 QUATCOPY(gsock->ns.vec, sock->ns.vec);
887                                 gsock->link = nodeAddLink(ngroup, node, sock, NULL, gsock);
888                         }
889                 }
890         }
891 }
892
893 void nodeGroupRemoveSocket(bNodeTree *ngroup, bNodeSocket *gsock, int in_out)
894 {
895         nodeRemSocketLinks(ngroup, gsock);
896         switch (in_out) {
897         case SOCK_IN:   BLI_remlink(&ngroup->inputs, gsock);    break;
898         case SOCK_OUT:  BLI_remlink(&ngroup->outputs, gsock);   break;
899         }
900 }
901
902 /* ************** Add stuff ********** */
903 void nodeAddSockets(bNode *node, bNodeType *ntype)
904 {
905         if (node->type==NODE_GROUP) {
906                 bNodeTree *ntree= (bNodeTree*)node->id;
907                 if (ntree) {
908                         bNodeSocket *gsock;
909                         for (gsock=ntree->inputs.first; gsock; gsock=gsock->next)
910                                 node_add_group_socket(&node->inputs, gsock);
911                         for (gsock=ntree->outputs.first; gsock; gsock=gsock->next)
912                                 node_add_group_socket(&node->outputs, gsock);
913                 }
914         }
915         else {
916                 bNodeSocketType *stype;
917                 
918                 if(ntype->inputs) {
919                         stype= ntype->inputs;
920                         while(stype->type != -1) {
921                                 node_add_socket_type(&node->inputs, stype);
922                                 stype++;
923                         }
924                 }
925                 if(ntype->outputs) {
926                         stype= ntype->outputs;
927                         while(stype->type != -1) {
928                                 node_add_socket_type(&node->outputs, stype);
929                                 stype++;
930                         }
931                 }
932         }
933 }
934
935 /* Find the first available, non-duplicate name for a given node */
936 void nodeUniqueName(bNodeTree *ntree, bNode *node)
937 {
938         BLI_uniquename(&ntree->nodes, node, "Node", '.', offsetof(bNode, name), sizeof(node->name));
939 }
940
941 bNode *nodeAddNodeType(bNodeTree *ntree, int type, bNodeTree *ngroup, ID *id)
942 {
943         bNode *node= NULL;
944         bNodeType *ntype= NULL;
945
946         if (ngroup && BLI_findindex(&G.main->nodetree, ngroup)==-1) {
947                 printf("nodeAddNodeType() error: '%s' not in main->nodetree\n", ngroup->id.name);
948                 return NULL;
949         }
950
951         if(type>=NODE_DYNAMIC_MENU) {
952                 int a=0, idx= type-NODE_DYNAMIC_MENU;
953                 ntype= ntree->alltypes.first;
954                 while(ntype) {
955                         if(ntype->type==NODE_DYNAMIC) {
956                                 if(a==idx)
957                                         break;
958                                 a++;
959                         }
960                         ntype= ntype->next;
961                 }
962         } else
963                 ntype= node_get_type(ntree, type, id);
964
965         node= MEM_callocN(sizeof(bNode), "new node");
966         BLI_addtail(&ntree->nodes, node);
967         node->typeinfo= ntype;
968         if(type>=NODE_DYNAMIC_MENU)
969                 node->custom2= type; /* for node_dynamic_init */
970
971         if(ngroup)
972                 BLI_strncpy(node->name, ngroup->id.name+2, NODE_MAXSTR);
973         else if(type>NODE_DYNAMIC_MENU) {
974                 BLI_strncpy(node->name, ntype->id->name+2, NODE_MAXSTR);
975         }
976         else
977                 BLI_strncpy(node->name, ntype->name, NODE_MAXSTR);
978
979         nodeUniqueName(ntree, node);
980         
981         node->type= ntype->type;
982         node->flag= NODE_SELECT|ntype->flag;
983         node->width= ntype->width;
984         node->miniwidth= 42.0f;         /* small value only, allows print of first chars */
985
986         if(type==NODE_GROUP)
987                 node->id= (ID *)ngroup;
988
989         /* need init handler later? */
990         /* got it-bob*/
991         if(ntype->initfunc!=NULL)
992                 ntype->initfunc(node);
993         
994         nodeAddSockets(node, ntype);
995         
996         return node;
997 }
998
999 void nodeMakeDynamicType(bNode *node)
1000 {
1001         /* find SH_DYNAMIC_NODE ntype */
1002         bNodeType *ntype= node_all_shaders.first;
1003         while(ntype) {
1004                 if(ntype->type==NODE_DYNAMIC && ntype->id==NULL)
1005                         break;
1006                 ntype= ntype->next;
1007         }
1008
1009         /* make own type struct to fill */
1010         if(ntype) {
1011                 /*node->typeinfo= MEM_dupallocN(ntype);*/
1012                 bNodeType *newtype= MEM_callocN(sizeof(bNodeType), "dynamic bNodeType");
1013                 *newtype= *ntype;
1014                 newtype->name= BLI_strdup(ntype->name);
1015                 node->typeinfo= newtype;
1016         }
1017 }
1018
1019 void nodeUpdateType(bNodeTree *ntree, bNode* node, bNodeType *ntype)
1020 {
1021         verify_socket_list(ntree, &node->inputs, ntype->inputs);
1022         verify_socket_list(ntree, &node->outputs, ntype->outputs);
1023 }
1024
1025 /* keep socket listorder identical, for copying links */
1026 /* ntree is the target tree */
1027 bNode *nodeCopyNode(struct bNodeTree *ntree, struct bNode *node)
1028 {
1029         bNode *nnode= MEM_callocN(sizeof(bNode), "dupli node");
1030         bNodeSocket *sock, *oldsock;
1031
1032         *nnode= *node;
1033         nodeUniqueName(ntree, nnode);
1034         
1035         BLI_addtail(&ntree->nodes, nnode);
1036         
1037         BLI_duplicatelist(&nnode->inputs, &node->inputs);
1038         oldsock= node->inputs.first;
1039         for(sock= nnode->inputs.first; sock; sock= sock->next, oldsock= oldsock->next) {
1040                 oldsock->new_sock= sock;
1041         }
1042         
1043         BLI_duplicatelist(&nnode->outputs, &node->outputs);
1044         oldsock= node->outputs.first;
1045         for(sock= nnode->outputs.first; sock; sock= sock->next, oldsock= oldsock->next) {
1046                 sock->stack_index= 0;
1047                 sock->ns.data= NULL;
1048                 oldsock->new_sock= sock;
1049         }
1050         
1051         /* don't increase node->id users, freenode doesn't decrement either */
1052         
1053         if(node->typeinfo->copystoragefunc)
1054                 node->typeinfo->copystoragefunc(node, nnode);
1055         
1056         node->new_node= nnode;
1057         nnode->new_node= NULL;
1058         nnode->preview= NULL;
1059         
1060         return nnode;
1061 }
1062
1063 /* fromsock and tosock can be NULL */
1064 /* also used via rna api, so we check for proper input output direction */
1065 bNodeLink *nodeAddLink(bNodeTree *ntree, bNode *fromnode, bNodeSocket *fromsock, bNode *tonode, bNodeSocket *tosock)
1066 {
1067         bNodeSocket *sock;
1068         bNodeLink *link= NULL; 
1069         int from= 0, to= 0;
1070         
1071         if(fromnode) {
1072                 /* test valid input */
1073                 for(sock= fromnode->outputs.first; sock; sock= sock->next)
1074                         if(sock==fromsock)
1075                                 break;
1076                 if(sock)
1077                         from= 1; /* OK */
1078                 else {
1079                         for(sock= fromnode->inputs.first; sock; sock= sock->next)
1080                                 if(sock==fromsock)
1081                                         break;
1082                         if(sock)
1083                                 from= -1; /* OK but flip */
1084                 }
1085         }
1086         if(tonode) {
1087                 for(sock= tonode->inputs.first; sock; sock= sock->next)
1088                         if(sock==tosock)
1089                                 break;
1090                 if(sock)
1091                         to= 1; /* OK */
1092                 else {
1093                         for(sock= tonode->outputs.first; sock; sock= sock->next)
1094                                 if(sock==tosock)
1095                                         break;
1096                         if(sock)
1097                                 to= -1; /* OK but flip */
1098                 }
1099         }
1100         
1101         /* this allows NULL sockets to work */
1102         if(from >= 0 && to >= 0) {
1103                 link= MEM_callocN(sizeof(bNodeLink), "link");
1104                 BLI_addtail(&ntree->links, link);
1105                 link->fromnode= fromnode;
1106                 link->fromsock= fromsock;
1107                 link->tonode= tonode;
1108                 link->tosock= tosock;
1109         }
1110         else if(from <= 0 && to <= 0) {
1111                 link= MEM_callocN(sizeof(bNodeLink), "link");
1112                 BLI_addtail(&ntree->links, link);
1113                 link->fromnode= tonode;
1114                 link->fromsock= tosock;
1115                 link->tonode= fromnode;
1116                 link->tosock= fromsock;
1117         }
1118         
1119         return link;
1120 }
1121
1122 void nodeRemLink(bNodeTree *ntree, bNodeLink *link)
1123 {
1124         BLI_remlink(&ntree->links, link);
1125         if(link->tosock)
1126                 link->tosock->link= NULL;
1127         MEM_freeN(link);
1128 }
1129
1130 void nodeRemSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1131 {
1132         bNodeLink *link, *next;
1133         
1134         for(link= ntree->links.first; link; link= next) {
1135                 next= link->next;
1136                 if(link->fromsock==sock || link->tosock==sock) {
1137                         nodeRemLink(ntree, link);
1138                 }
1139         }
1140 }
1141
1142
1143 bNodeTree *ntreeAddTree(const char *name, int type, const short is_group)
1144 {
1145         bNodeTree *ntree;
1146
1147         if (is_group)
1148                 ntree= alloc_libblock(&G.main->nodetree, ID_NT, name);
1149         else {
1150                 ntree= MEM_callocN(sizeof(bNodeTree), "new node tree");
1151                 *( (short *)ntree->id.name )= ID_NT; /* not "type", as that is ntree->type */
1152                 BLI_strncpy(ntree->id.name+2, name, sizeof(ntree->id.name));
1153         }
1154
1155         ntree->type= type;
1156         ntree->alltypes.first = NULL;
1157         ntree->alltypes.last = NULL;
1158
1159         ntreeInitTypes(ntree);
1160         return ntree;
1161 }
1162
1163 /* Warning: this function gets called during some rather unexpected times
1164  *      - this gets called when executing compositing updates (for threaded previews)
1165  *      - when the nodetree datablock needs to be copied (i.e. when users get copied)
1166  *      - for scene duplication use ntreeSwapID() after so we dont have stale pointers.
1167  */
1168 bNodeTree *ntreeCopyTree(bNodeTree *ntree)
1169 {
1170         bNodeTree *newtree;
1171         bNode *node, *nnode, *last;
1172         bNodeLink *link;
1173         bNodeSocket *gsock, *oldgsock;
1174         
1175         if(ntree==NULL) return NULL;
1176         
1177         /* is ntree part of library? */
1178         for(newtree=G.main->nodetree.first; newtree; newtree= newtree->id.next)
1179                 if(newtree==ntree) break;
1180         if(newtree) {
1181                 newtree= copy_libblock(ntree);
1182         } else {
1183                 newtree= MEM_dupallocN(ntree);
1184                 copy_libblock_data(&newtree->id, &ntree->id, TRUE); /* copy animdata and ID props */
1185         }
1186         newtree->nodes.first= newtree->nodes.last= NULL;
1187         newtree->links.first= newtree->links.last= NULL;
1188         
1189         last = ntree->nodes.last;
1190         for(node= ntree->nodes.first; node; node= node->next) {
1191                 node->new_node= NULL;
1192                 nnode= nodeCopyNode(newtree, node);     /* sets node->new */
1193                 if(node==last) break;
1194         }
1195         
1196         /* socket definition for group usage */
1197         BLI_duplicatelist(&newtree->inputs, &ntree->inputs);
1198         for(gsock= newtree->inputs.first, oldgsock= ntree->inputs.first; gsock; gsock=gsock->next, oldgsock=oldgsock->next) {
1199                 oldgsock->new_sock= gsock;
1200                 gsock->groupsock = (oldgsock->groupsock ? oldgsock->groupsock->new_sock : NULL);
1201         }
1202         
1203         BLI_duplicatelist(&newtree->outputs, &ntree->outputs);
1204         for(gsock= newtree->outputs.first, oldgsock= ntree->outputs.first; gsock; gsock=gsock->next, oldgsock=oldgsock->next) {
1205                 oldgsock->new_sock= gsock;
1206                 gsock->groupsock = (oldgsock->groupsock ? oldgsock->groupsock->new_sock : NULL);
1207         }
1208
1209         /* copy links */
1210         BLI_duplicatelist(&newtree->links, &ntree->links);
1211         for(link= newtree->links.first; link; link= link->next) {
1212                 link->fromnode = (link->fromnode ? link->fromnode->new_node : NULL);
1213                 link->fromsock = (link->fromsock ? link->fromsock->new_sock : NULL);
1214                 link->tonode = (link->tonode ? link->tonode->new_node : NULL);
1215                 link->tosock = (link->tosock ? link->tosock->new_sock : NULL);
1216                 /* update the link socket's pointer */
1217                 if (link->tosock)
1218                         link->tosock->link = link;
1219         }
1220
1221         return newtree;
1222 }
1223
1224 /* use when duplicating scenes */
1225 void ntreeSwitchID(bNodeTree *ntree, ID *id_from, ID *id_to)
1226 {
1227         bNode *node;
1228         /* for scene duplication only */
1229         for(node= ntree->nodes.first; node; node= node->next) {
1230                 if(node->id==id_from) {
1231                         node->id= id_to;
1232                 }
1233         }
1234 }
1235
1236 /* *************** preview *********** */
1237 /* if node->preview, then we assume the rect to exist */
1238
1239 static void node_free_preview(bNode *node)
1240 {
1241         if(node->preview) {
1242                 if(node->preview->rect)
1243                         MEM_freeN(node->preview->rect);
1244                 MEM_freeN(node->preview);
1245                 node->preview= NULL;
1246         }       
1247 }
1248
1249 static void node_init_preview(bNode *node, int xsize, int ysize)
1250 {
1251         
1252         if(node->preview==NULL) {
1253                 node->preview= MEM_callocN(sizeof(bNodePreview), "node preview");
1254                 //              printf("added preview %s\n", node->name);
1255         }
1256         
1257         /* node previews can get added with variable size this way */
1258         if(xsize==0 || ysize==0)
1259                 return;
1260         
1261         /* sanity checks & initialize */
1262         if(node->preview->rect) {
1263                 if(node->preview->xsize!=xsize && node->preview->ysize!=ysize) {
1264                         MEM_freeN(node->preview->rect);
1265                         node->preview->rect= NULL;
1266                 }
1267         }
1268         
1269         if(node->preview->rect==NULL) {
1270                 node->preview->rect= MEM_callocN(4*xsize + xsize*ysize*sizeof(char)*4, "node preview rect");
1271                 node->preview->xsize= xsize;
1272                 node->preview->ysize= ysize;
1273         }
1274         /* no clear, makes nicer previews */
1275 }
1276
1277 void ntreeInitPreview(bNodeTree *ntree, int xsize, int ysize)
1278 {
1279         bNode *node;
1280         
1281         if(ntree==NULL)
1282                 return;
1283         
1284         for(node= ntree->nodes.first; node; node= node->next) {
1285                 if(node->typeinfo->flag & NODE_PREVIEW) /* hrms, check for closed nodes? */
1286                         node_init_preview(node, xsize, ysize);
1287                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1288                         ntreeInitPreview((bNodeTree *)node->id, xsize, ysize);
1289         }               
1290 }
1291
1292 static void nodeClearPreview(bNode *node)
1293 {
1294         if(node->preview && node->preview->rect)
1295                 memset(node->preview->rect, 0, MEM_allocN_len(node->preview->rect));
1296 }
1297
1298 /* use it to enforce clear */
1299 void ntreeClearPreview(bNodeTree *ntree)
1300 {
1301         bNode *node;
1302         
1303         if(ntree==NULL)
1304                 return;
1305         
1306         for(node= ntree->nodes.first; node; node= node->next) {
1307                 if(node->typeinfo->flag & NODE_PREVIEW)
1308                         nodeClearPreview(node);
1309                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1310                         ntreeClearPreview((bNodeTree *)node->id);
1311         }               
1312 }
1313
1314 /* hack warning! this function is only used for shader previews, and 
1315 since it gets called multiple times per pixel for Ztransp we only
1316 add the color once. Preview gets cleared before it starts render though */
1317 void nodeAddToPreview(bNode *node, float *col, int x, int y)
1318 {
1319         bNodePreview *preview= node->preview;
1320         if(preview) {
1321                 if(x>=0 && y>=0) {
1322                         if(x<preview->xsize && y<preview->ysize) {
1323                                 unsigned char *tar= preview->rect+ 4*((preview->xsize*y) + x);
1324                                 
1325                                 if(TRUE) {
1326                                         tar[0]= FTOCHAR(linearrgb_to_srgb(col[0]));
1327                                         tar[1]= FTOCHAR(linearrgb_to_srgb(col[1]));
1328                                         tar[2]= FTOCHAR(linearrgb_to_srgb(col[2]));
1329                                 }
1330                                 else {
1331                                         tar[0]= FTOCHAR(col[0]);
1332                                         tar[1]= FTOCHAR(col[1]);
1333                                         tar[2]= FTOCHAR(col[2]);
1334                                 }
1335                                 tar[3]= FTOCHAR(col[3]);
1336                         }
1337                         //else printf("prv out bound x y %d %d\n", x, y);
1338                 }
1339                 //else printf("prv out bound x y %d %d\n", x, y);
1340         }
1341 }
1342
1343
1344 /* ************** Free stuff ********** */
1345
1346 /* goes over entire tree */
1347 void nodeUnlinkNode(bNodeTree *ntree, bNode *node)
1348 {
1349         bNodeLink *link, *next;
1350         bNodeSocket *sock;
1351         ListBase *lb;
1352         
1353         for(link= ntree->links.first; link; link= next) {
1354                 next= link->next;
1355                 
1356                 if(link->fromnode==node) {
1357                         lb= &node->outputs;
1358                         if (link->tonode)
1359                                 NodeTagChanged(ntree, link->tonode);
1360                 }
1361                 else if(link->tonode==node)
1362                         lb= &node->inputs;
1363                 else
1364                         lb= NULL;
1365
1366                 if(lb) {
1367                         for(sock= lb->first; sock; sock= sock->next) {
1368                                 if(link->fromsock==sock || link->tosock==sock)
1369                                         break;
1370                         }
1371                         if(sock) {
1372                                 nodeRemLink(ntree, link);
1373                         }
1374                 }
1375         }
1376 }
1377
1378 static void composit_free_node_cache(bNode *node)
1379 {
1380         bNodeSocket *sock;
1381         
1382         for(sock= node->outputs.first; sock; sock= sock->next) {
1383                 if(sock->ns.data) {
1384                         free_compbuf(sock->ns.data);
1385                         sock->ns.data= NULL;
1386                 }
1387         }
1388 }
1389
1390 void nodeFreeNode(bNodeTree *ntree, bNode *node)
1391 {
1392         nodeUnlinkNode(ntree, node);
1393         BLI_remlink(&ntree->nodes, node);
1394
1395         /* since it is called while free database, node->id is undefined */
1396         
1397         if(ntree->type==NTREE_COMPOSIT)
1398                 composit_free_node_cache(node);
1399         BLI_freelistN(&node->inputs);
1400         BLI_freelistN(&node->outputs);
1401         
1402         node_free_preview(node);
1403
1404         if(node->typeinfo && node->typeinfo->freestoragefunc) {
1405                 node->typeinfo->freestoragefunc(node);
1406         }
1407
1408         MEM_freeN(node);
1409 }
1410
1411 /* do not free ntree itself here, free_libblock calls this function too */
1412 void ntreeFreeTree(bNodeTree *ntree)
1413 {
1414         bNode *node, *next;
1415         
1416         if(ntree==NULL) return;
1417         
1418         ntreeEndExecTree(ntree);        /* checks for if it is still initialized */
1419         
1420         BKE_free_animdata((ID *)ntree);
1421
1422         BLI_freelistN(&ntree->links);   /* do first, then unlink_node goes fast */
1423         
1424         for(node= ntree->nodes.first; node; node= next) {
1425                 next= node->next;
1426                 nodeFreeNode(ntree, node);
1427         }
1428         
1429         BLI_freelistN(&ntree->inputs);
1430         BLI_freelistN(&ntree->outputs);
1431 }
1432
1433 void ntreeFreeCache(bNodeTree *ntree)
1434 {
1435         bNode *node;
1436         
1437         if(ntree==NULL) return;
1438
1439         if(ntree->type==NTREE_COMPOSIT)
1440                 for(node= ntree->nodes.first; node; node= node->next)
1441                         composit_free_node_cache(node);
1442
1443 }
1444
1445 void ntreeMakeLocal(bNodeTree *ntree)
1446 {
1447         int local=0, lib=0;
1448         
1449         /* - only lib users: do nothing
1450                 * - only local users: set flag
1451                 * - mixed: make copy
1452                 */
1453         
1454         if(ntree->id.lib==NULL) return;
1455         if(ntree->id.us==1) {
1456                 ntree->id.lib= NULL;
1457                 ntree->id.flag= LIB_LOCAL;
1458                 new_id(NULL, (ID *)ntree, NULL);
1459                 return;
1460         }
1461         
1462         /* now check users of groups... again typedepending, callback... */
1463         if(ntree->type==NTREE_SHADER) {
1464                 Material *ma;
1465                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1466                         if(ma->nodetree) {
1467                                 bNode *node;
1468                                 
1469                                 /* find if group is in tree */
1470                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
1471                                         if(node->id == (ID *)ntree) {
1472                                                 if(ma->id.lib) lib= 1;
1473                                                 else local= 1;
1474                                         }
1475                                 }
1476                         }
1477                 }
1478         }
1479         else if(ntree->type==NTREE_COMPOSIT) {
1480                 Scene *sce;
1481                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
1482                         if(sce->nodetree) {
1483                                 bNode *node;
1484                                 
1485                                 /* find if group is in tree */
1486                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
1487                                         if(node->id == (ID *)ntree) {
1488                                                 if(sce->id.lib) lib= 1;
1489                                                 else local= 1;
1490                                         }
1491                                 }
1492                         }
1493                 }
1494         }
1495         else if(ntree->type==NTREE_TEXTURE) {
1496                 Tex *tx;
1497                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
1498                         if(tx->nodetree) {
1499                                 bNode *node;
1500                                 
1501                                 /* find if group is in tree */
1502                                 for(node= tx->nodetree->nodes.first; node; node= node->next) {
1503                                         if(node->id == (ID *)ntree) {
1504                                                 if(tx->id.lib) lib= 1;
1505                                                 else local= 1;
1506                                         }
1507                                 }
1508                         }
1509                 }
1510         }
1511         
1512         /* if all users are local, we simply make tree local */
1513         if(local && lib==0) {
1514                 ntree->id.lib= NULL;
1515                 ntree->id.flag= LIB_LOCAL;
1516                 new_id(NULL, (ID *)ntree, NULL);
1517         }
1518         else if(local && lib) {
1519                 /* this is the mixed case, we copy the tree and assign it to local users */
1520                 bNodeTree *newtree= ntreeCopyTree(ntree);
1521                 
1522                 newtree->id.us= 0;
1523                 
1524                 if(ntree->type==NTREE_SHADER) {
1525                         Material *ma;
1526                         for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1527                                 if(ma->nodetree) {
1528                                         bNode *node;
1529                                         
1530                                         /* find if group is in tree */
1531                                         for(node= ma->nodetree->nodes.first; node; node= node->next) {
1532                                                 if(node->id == (ID *)ntree) {
1533                                                         if(ma->id.lib==NULL) {
1534                                                                 node->id= &newtree->id;
1535                                                                 newtree->id.us++;
1536                                                                 ntree->id.us--;
1537                                                         }
1538                                                 }
1539                                         }
1540                                 }
1541                         }
1542                 }
1543                 else if(ntree->type==NTREE_COMPOSIT) {
1544                         Scene *sce;
1545                         for(sce= G.main->scene.first; sce; sce= sce->id.next) {
1546                                 if(sce->nodetree) {
1547                                         bNode *node;
1548                                         
1549                                         /* find if group is in tree */
1550                                         for(node= sce->nodetree->nodes.first; node; node= node->next) {
1551                                                 if(node->id == (ID *)ntree) {
1552                                                         if(sce->id.lib==NULL) {
1553                                                                 node->id= &newtree->id;
1554                                                                 newtree->id.us++;
1555                                                                 ntree->id.us--;
1556                                                         }
1557                                                 }
1558                                         }
1559                                 }
1560                         }
1561                 }
1562                 else if(ntree->type==NTREE_TEXTURE) {
1563                         Tex *tx;
1564                         for(tx= G.main->tex.first; tx; tx= tx->id.next) {
1565                                 if(tx->nodetree) {
1566                                         bNode *node;
1567                                         
1568                                         /* find if group is in tree */
1569                                         for(node= tx->nodetree->nodes.first; node; node= node->next) {
1570                                                 if(node->id == (ID *)ntree) {
1571                                                         if(tx->id.lib==NULL) {
1572                                                                 node->id= &newtree->id;
1573                                                                 newtree->id.us++;
1574                                                                 ntree->id.us--;
1575                                                         }
1576                                                 }
1577                                         }
1578                                 }
1579                         }
1580                 }
1581         }
1582 }
1583
1584
1585 /* ************ find stuff *************** */
1586
1587 static int ntreeHasType(bNodeTree *ntree, int type)
1588 {
1589         bNode *node;
1590         
1591         if(ntree)
1592                 for(node= ntree->nodes.first; node; node= node->next)
1593                         if(node->type == type)
1594                                 return 1;
1595         return 0;
1596 }
1597
1598 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
1599 {
1600         bNodeLink *link;
1601         
1602         for(link= ntree->links.first; link; link= link->next) {
1603                 if(link->fromsock==from && link->tosock==to)
1604                         return link;
1605                 if(link->fromsock==to && link->tosock==from)    /* hrms? */
1606                         return link;
1607         }
1608         return NULL;
1609 }
1610
1611 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1612 {
1613         bNodeLink *link;
1614         int tot= 0;
1615         
1616         for(link= ntree->links.first; link; link= link->next) {
1617                 if(link->fromsock==sock || link->tosock==sock)
1618                         tot++;
1619         }
1620         return tot;
1621 }
1622
1623 bNode *nodeGetActive(bNodeTree *ntree)
1624 {
1625         bNode *node;
1626         
1627         if(ntree==NULL) return NULL;
1628         
1629         for(node= ntree->nodes.first; node; node= node->next)
1630                 if(node->flag & NODE_ACTIVE)
1631                         break;
1632         return node;
1633 }
1634
1635 /* two active flags, ID nodes have special flag for buttons display */
1636 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
1637 {
1638         bNode *node;
1639         
1640         if(ntree==NULL) return NULL;
1641
1642         /* check for group edit */
1643         for(node= ntree->nodes.first; node; node= node->next)
1644                 if(node->flag & NODE_GROUP_EDIT)
1645                         break;
1646
1647         if(node)
1648                 ntree= (bNodeTree*)node->id;
1649         
1650         /* now find active node with this id */
1651         for(node= ntree->nodes.first; node; node= node->next)
1652                 if(node->id && GS(node->id->name)==idtype)
1653                         if(node->flag & NODE_ACTIVE_ID)
1654                                 break;
1655
1656         return node;
1657 }
1658
1659 int nodeSetActiveID(bNodeTree *ntree, short idtype, ID *id)
1660 {
1661         bNode *node;
1662         int ok= FALSE;
1663
1664         if(ntree==NULL) return ok;
1665
1666         /* check for group edit */
1667         for(node= ntree->nodes.first; node; node= node->next)
1668                 if(node->flag & NODE_GROUP_EDIT)
1669                         break;
1670
1671         if(node)
1672                 ntree= (bNodeTree*)node->id;
1673
1674         /* now find active node with this id */
1675         for(node= ntree->nodes.first; node; node= node->next) {
1676                 if(node->id && GS(node->id->name)==idtype) {
1677                         if(id && ok==FALSE && node->id==id) {
1678                                 node->flag |= NODE_ACTIVE_ID;
1679                                 ok= TRUE;
1680                         } else {
1681                                 node->flag &= ~NODE_ACTIVE_ID;
1682                         }
1683                 }
1684         }
1685
1686         return ok;
1687 }
1688
1689
1690 /* two active flags, ID nodes have special flag for buttons display */
1691 void nodeClearActiveID(bNodeTree *ntree, short idtype)
1692 {
1693         bNode *node;
1694         
1695         if(ntree==NULL) return;
1696         
1697         for(node= ntree->nodes.first; node; node= node->next)
1698                 if(node->id && GS(node->id->name)==idtype)
1699                         node->flag &= ~NODE_ACTIVE_ID;
1700 }
1701
1702 /* two active flags, ID nodes have special flag for buttons display */
1703 void nodeSetActive(bNodeTree *ntree, bNode *node)
1704 {
1705         bNode *tnode;
1706         
1707         /* make sure only one node is active, and only one per ID type */
1708         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1709                 tnode->flag &= ~NODE_ACTIVE;
1710                 
1711                 if(node->id && tnode->id) {
1712                         if(GS(node->id->name) == GS(tnode->id->name))
1713                                 tnode->flag &= ~NODE_ACTIVE_ID;
1714                 }
1715         }
1716         
1717         node->flag |= NODE_ACTIVE;
1718         if(node->id)
1719                 node->flag |= NODE_ACTIVE_ID;
1720 }
1721
1722 /* use flags are not persistant yet, groups might need different tagging, so we do it each time
1723    when we need to get this info */
1724 void ntreeSocketUseFlags(bNodeTree *ntree)
1725 {
1726         bNode *node;
1727         bNodeSocket *sock;
1728         bNodeLink *link;
1729         
1730         /* clear flags */
1731         for(node= ntree->nodes.first; node; node= node->next) {
1732                 for(sock= node->inputs.first; sock; sock= sock->next)
1733                         sock->flag &= ~SOCK_IN_USE;
1734                 for(sock= node->outputs.first; sock; sock= sock->next)
1735                         sock->flag &= ~SOCK_IN_USE;
1736         }
1737         
1738         /* tag all thats in use */
1739         for(link= ntree->links.first; link; link= link->next) {
1740         
1741                 if(link->fromsock) // FIXME, see below
1742                         link->fromsock->flag |= SOCK_IN_USE;
1743                 if(link->tosock) // FIXME This can be NULL, when dragging a new link in the UI, should probably copy the node tree for preview render - campbell
1744                         link->tosock->flag |= SOCK_IN_USE;
1745         }
1746 }
1747
1748 /* ************** dependency stuff *********** */
1749
1750 /* node is guaranteed to be not checked before */
1751 static int node_recurs_check(bNode *node, bNode ***nsort, int level)
1752 {
1753         bNode *fromnode;
1754         bNodeSocket *sock;
1755         int has_inputlinks= 0;
1756         
1757         node->done= 1;
1758         level++;
1759         
1760         for(sock= node->inputs.first; sock; sock= sock->next) {
1761                 if(sock->link) {
1762                         has_inputlinks= 1;
1763                         fromnode= sock->link->fromnode;
1764                         if(fromnode && fromnode->done==0) {
1765                                 fromnode->level= node_recurs_check(fromnode, nsort, level);
1766                         }
1767                 }
1768         }
1769 //      printf("node sort %s level %d\n", node->name, level);
1770         **nsort= node;
1771         (*nsort)++;
1772         
1773         if(has_inputlinks)
1774                 return level;
1775         else 
1776                 return 0xFFF;
1777 }
1778
1779
1780 static void ntreeSetOutput(bNodeTree *ntree)
1781 {
1782         bNode *node;
1783
1784         /* find the active outputs, might become tree type dependant handler */
1785         for(node= ntree->nodes.first; node; node= node->next) {
1786                 if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1787                         bNode *tnode;
1788                         int output= 0;
1789                         
1790                         /* we need a check for which output node should be tagged like this, below an exception */
1791                         if(node->type==CMP_NODE_OUTPUT_FILE)
1792                            continue;
1793                            
1794                         /* there is more types having output class, each one is checked */
1795                         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1796                                 if(tnode->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1797                                         
1798                                         if(ntree->type==NTREE_COMPOSIT) {
1799                                                         
1800                                                 /* same type, exception for viewer */
1801                                                 if(tnode->type==node->type ||
1802                                                    (ELEM(tnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) &&
1803                                                         ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))) {
1804                                                         if(tnode->flag & NODE_DO_OUTPUT) {
1805                                                                 output++;
1806                                                                 if(output>1)
1807                                                                         tnode->flag &= ~NODE_DO_OUTPUT;
1808                                                         }
1809                                                 }
1810                                         }
1811                                         else {
1812                                                 /* same type */
1813                                                 if(tnode->type==node->type) {
1814                                                         if(tnode->flag & NODE_DO_OUTPUT) {
1815                                                                 output++;
1816                                                                 if(output>1)
1817                                                                         tnode->flag &= ~NODE_DO_OUTPUT;
1818                                                         }
1819                                                 }
1820                                         }
1821                                 }
1822                         }
1823                         if(output==0)
1824                                 node->flag |= NODE_DO_OUTPUT;
1825                 }
1826         }
1827         
1828         /* here we could recursively set which nodes have to be done,
1829                 might be different for editor or for "real" use... */
1830 }
1831
1832 void ntreeSolveOrder(bNodeTree *ntree)
1833 {
1834         bNode *node, **nodesort, **nsort;
1835         bNodeSocket *sock;
1836         bNodeLink *link;
1837         int a, totnode=0;
1838         
1839         /* the solve-order is called on each tree change, so we should be sure no exec can be running */
1840         ntreeEndExecTree(ntree);
1841
1842         /* set links pointers the input sockets, to find dependencies */
1843         /* first clear data */
1844         for(node= ntree->nodes.first; node; node= node->next) {
1845                 node->done= 0;
1846                 totnode++;
1847                 for(sock= node->inputs.first; sock; sock= sock->next)
1848                         sock->link= NULL;
1849         }
1850         /* clear group socket links */
1851         for(sock= ntree->outputs.first; sock; sock= sock->next)
1852                 sock->link= NULL;
1853         if(totnode==0)
1854                 return;
1855         
1856         for(link= ntree->links.first; link; link= link->next) {
1857                 link->tosock->link= link;
1858         }
1859         
1860         nsort= nodesort= MEM_callocN(totnode*sizeof(void *), "sorted node array");
1861         
1862         /* recursive check */
1863         for(node= ntree->nodes.first; node; node= node->next) {
1864                 if(node->done==0) {
1865                         node->level= node_recurs_check(node, &nsort, 0);
1866                 }
1867         }
1868         
1869         /* re-insert nodes in order, first a paranoia check */
1870         for(a=0; a<totnode; a++) {
1871                 if(nodesort[a]==NULL)
1872                         break;
1873         }
1874         if(a<totnode)
1875                 printf("sort error in node tree");
1876         else {
1877                 ntree->nodes.first= ntree->nodes.last= NULL;
1878                 for(a=0; a<totnode; a++)
1879                         BLI_addtail(&ntree->nodes, nodesort[a]);
1880         }
1881         
1882         MEM_freeN(nodesort);
1883
1884         ntreeSetOutput(ntree);
1885 }
1886
1887
1888 /* Should be callback! */
1889 /* Do not call execs here */
1890 void NodeTagChanged(bNodeTree *ntree, bNode *node)
1891 {
1892         if(ntree->type==NTREE_COMPOSIT) {
1893                 bNodeSocket *sock;
1894
1895                 for(sock= node->outputs.first; sock; sock= sock->next) {
1896                         if(sock->ns.data) {
1897                                 //free_compbuf(sock->ns.data);
1898                                 //sock->ns.data= NULL;
1899                         }
1900                 }
1901                 node->need_exec= 1;
1902         }
1903 }
1904
1905 int NodeTagIDChanged(bNodeTree *ntree, ID *id)
1906 {
1907         int change = FALSE;
1908
1909         if(ELEM(NULL, id, ntree))
1910                 return change;
1911         
1912         if(ntree->type==NTREE_COMPOSIT) {
1913                 bNode *node;
1914                 
1915                 for(node= ntree->nodes.first; node; node= node->next) {
1916                         if(node->id==id) {
1917                                 change= TRUE;
1918                                 NodeTagChanged(ntree, node);
1919                         }
1920                 }
1921         }
1922         
1923         return change;
1924 }
1925
1926
1927
1928 /* ******************* executing ************* */
1929
1930 /* for a given socket, find the actual stack entry */
1931 static bNodeStack *get_socket_stack(bNodeStack *stack, bNodeSocket *sock, bNodeStack **gin)
1932 {
1933         switch (sock->stack_type) {
1934         case SOCK_STACK_LOCAL:
1935                 return stack + sock->stack_index;
1936         case SOCK_STACK_EXTERN:
1937                 return (gin ? gin[sock->stack_index] : NULL);
1938         case SOCK_STACK_CONST:
1939                 return sock->stack_ptr;
1940         }
1941         return NULL;
1942 }
1943
1944 /* see notes at ntreeBeginExecTree */
1945 static void node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out, bNodeStack **gin)
1946 {
1947         bNodeSocket *sock;
1948         
1949         /* build pointer stack */
1950         if (in) {
1951                 for(sock= node->inputs.first; sock; sock= sock->next) {
1952                         *(in++) = get_socket_stack(stack, sock, gin);
1953                 }
1954         }
1955         
1956         if (out) {
1957                 for(sock= node->outputs.first; sock; sock= sock->next) {
1958                         *(out++) = get_socket_stack(stack, sock, gin);
1959                 }
1960         }
1961 }
1962
1963 static void node_group_execute(bNodeStack *stack, void *data, bNode *gnode, bNodeStack **in)
1964 {
1965         bNode *node;
1966         bNodeTree *ntree= (bNodeTree *)gnode->id;
1967         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1968         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1969         
1970         if(ntree==NULL) return;
1971         
1972         stack+= gnode->stack_index;
1973                 
1974         for(node= ntree->nodes.first; node; node= node->next) {
1975                 if(node->typeinfo->execfunc) {
1976                         node_get_stack(node, stack, nsin, nsout, in);
1977                         
1978                         /* for groups, only execute outputs for edited group */
1979                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1980                                 if(node->type==CMP_NODE_OUTPUT_FILE || (gnode->flag & NODE_GROUP_EDIT))
1981                                         node->typeinfo->execfunc(data, node, nsin, nsout);
1982                         }
1983                         else
1984                                 node->typeinfo->execfunc(data, node, nsin, nsout);
1985                 }
1986         }
1987         
1988         /* free internal buffers */
1989         if (ntree->type==NTREE_COMPOSIT) {
1990                 bNodeSocket *sock;
1991                 bNodeStack *ns;
1992                 for (sock=ntree->outputs.first; sock; sock=sock->next) {
1993                         /* use the hasoutput flag to tag external sockets */
1994                         if (sock->stack_type==SOCK_STACK_LOCAL) {
1995                                 ns= get_socket_stack(stack, sock, in);
1996                                 ns->hasoutput = 0;
1997                         }
1998                 }
1999                 /* now free all stacks that are not used from outside */
2000                 for (node=ntree->nodes.first; node; node=node->next) {
2001                         for (sock=node->outputs.first; sock; sock=sock->next) {
2002                                 if (sock->stack_type==SOCK_STACK_LOCAL ) {
2003                                         ns= get_socket_stack(stack, sock, in);
2004                                         if (ns->hasoutput!=0 && ns->data) {
2005                                                 free_compbuf(ns->data);
2006                                                 ns->data = NULL;
2007                                                 /* reset the flag */
2008                                                 ns->hasoutput = 1;
2009                                         }
2010                                 }
2011                         }
2012                 }
2013         }
2014 }
2015
2016 static int set_stack_indexes_default(bNode *node, int index)
2017 {
2018         bNodeSocket *sock;
2019         
2020         for (sock=node->inputs.first; sock; sock=sock->next) {
2021                 if (sock->link && sock->link->fromsock) {
2022                         sock->stack_type = sock->link->fromsock->stack_type;
2023                         sock->stack_index = sock->link->fromsock->stack_index;
2024                         sock->stack_ptr = sock->link->fromsock->stack_ptr;
2025                 }
2026                 else {
2027                         sock->stack_type = SOCK_STACK_CONST;
2028                         sock->stack_index = -1;
2029                         sock->stack_ptr = &sock->ns;
2030                 }
2031         }
2032         
2033         for (sock=node->outputs.first; sock; sock=sock->next) {
2034                 sock->stack_type = SOCK_STACK_LOCAL;
2035                 sock->stack_index = index++;
2036                 sock->stack_ptr = NULL;
2037         }
2038         
2039         return index;
2040 }
2041
2042 static int ntree_begin_exec_tree(bNodeTree *ntree);
2043 static int set_stack_indexes_group(bNode *node, int index)
2044 {
2045         bNodeTree *ngroup= (bNodeTree*)node->id;
2046         bNodeSocket *sock;
2047         
2048         if((ngroup->init & NTREE_TYPE_INIT)==0)
2049                 ntreeInitTypes(ngroup);
2050         
2051         node->stack_index = index;
2052         index += ntree_begin_exec_tree(ngroup);
2053         
2054         for (sock=node->inputs.first; sock; sock=sock->next) {
2055                 if (sock->link && sock->link->fromsock) {
2056                         sock->stack_type = sock->link->fromsock->stack_type;
2057                         sock->stack_index = sock->link->fromsock->stack_index;
2058                         sock->stack_ptr = sock->link->fromsock->stack_ptr;
2059                 }
2060                 else {
2061                         sock->stack_type = SOCK_STACK_CONST;
2062                         sock->stack_index = -1;
2063                         sock->stack_ptr = &sock->ns;
2064                 }
2065         }
2066         
2067         /* identify group node outputs from internal group sockets */
2068         for(sock= node->outputs.first; sock; sock= sock->next) {
2069                 if (sock->groupsock) {
2070                         bNodeSocket *insock, *gsock = sock->groupsock;
2071                         switch (gsock->stack_type) {
2072                         case SOCK_STACK_EXTERN:
2073                                 /* extern stack is resolved for this group node instance */
2074                                 insock= find_group_node_input(node, gsock->link->fromsock);
2075                                 sock->stack_type = insock->stack_type;
2076                                 sock->stack_index = insock->stack_index;
2077                                 sock->stack_ptr = insock->stack_ptr;
2078                                 break;
2079                         case SOCK_STACK_LOCAL:
2080                                 sock->stack_type = SOCK_STACK_LOCAL;
2081                                 /* local stack index must be offset by group node instance */
2082                                 sock->stack_index = gsock->stack_index + node->stack_index;
2083                                 sock->stack_ptr = NULL;
2084                                 break;
2085                         case SOCK_STACK_CONST:
2086                                 sock->stack_type = SOCK_STACK_CONST;
2087                                 sock->stack_index = -1;
2088                                 sock->stack_ptr = gsock->stack_ptr;
2089                                 break;
2090                         }
2091                 }
2092                 else {
2093                         sock->stack_type = SOCK_STACK_LOCAL;
2094                         sock->stack_index = index++;
2095                         sock->stack_ptr = NULL;
2096                 }
2097         }
2098         
2099         return index;
2100 }
2101
2102 /* recursively called for groups */
2103 /* we set all trees on own local indices, but put a total counter
2104    in the groups, so each instance of a group has own stack */
2105 static int ntree_begin_exec_tree(bNodeTree *ntree)
2106 {
2107         bNode *node;
2108         bNodeSocket *gsock;
2109         int index= 0, i;
2110         
2111         if((ntree->init & NTREE_TYPE_INIT)==0)
2112                 ntreeInitTypes(ntree);
2113         
2114         /* group inputs are numbered 0..totinputs, so external stack can easily be addressed */
2115         i = 0;
2116         for(gsock=ntree->inputs.first; gsock; gsock = gsock->next) {
2117                 gsock->stack_type = SOCK_STACK_EXTERN;
2118                 gsock->stack_index = i++;
2119                 gsock->stack_ptr = NULL;
2120         }
2121         
2122         /* create indices for stack, check preview */
2123         for(node= ntree->nodes.first; node; node= node->next) {
2124                 /* XXX can this be done by a generic one-for-all function?
2125                  * otherwise should use node-type callback.
2126                  */
2127                 if(node->type==NODE_GROUP)
2128                         index = set_stack_indexes_group(node, index);
2129                 else
2130                         index = set_stack_indexes_default(node, index);
2131         }
2132         
2133         /* group outputs */
2134         for(gsock=ntree->outputs.first; gsock; gsock = gsock->next) {
2135                 if (gsock->link && gsock->link->fromsock) {
2136                         gsock->stack_type = gsock->link->fromsock->stack_type;
2137                         gsock->stack_index = gsock->link->fromsock->stack_index;
2138                         gsock->stack_ptr = gsock->link->fromsock->stack_ptr;
2139                 }
2140                 else {
2141                         gsock->stack_type = SOCK_STACK_CONST;
2142                         gsock->stack_index = -1;
2143                         gsock->stack_ptr = &gsock->ns;
2144                 }
2145         }
2146         
2147         return index;
2148 }
2149
2150 /* copy socket compbufs to stack, initialize usage of curve nodes */
2151 static void composit_begin_exec(bNodeTree *ntree, bNodeStack *stack)
2152 {
2153         bNode *node;
2154         bNodeSocket *sock;
2155         
2156         for(node= ntree->nodes.first; node; node= node->next) {
2157                 
2158                 /* initialize needed for groups */
2159                 node->exec= 0;  
2160                 
2161                 for(sock= node->outputs.first; sock; sock= sock->next) {
2162                         bNodeStack *ns= get_socket_stack(stack, sock, NULL);
2163                         if(ns && sock->ns.data) {
2164                                 ns->data= sock->ns.data;
2165                                 sock->ns.data= NULL;
2166                         }
2167                 }
2168                 
2169                 /* cannot initialize them while using in threads */
2170                 if(ELEM4(node->type, CMP_NODE_TIME, CMP_NODE_CURVE_VEC, CMP_NODE_CURVE_RGB, CMP_NODE_HUECORRECT)) {
2171                         curvemapping_initialize(node->storage);
2172                         if(node->type==CMP_NODE_CURVE_RGB)
2173                                 curvemapping_premultiply(node->storage, 0);
2174                 }
2175                 if(node->type==NODE_GROUP)
2176                         composit_begin_exec((bNodeTree *)node->id, stack + node->stack_index);
2177
2178         }
2179 }
2180
2181 /* copy stack compbufs to sockets */
2182 static void composit_end_exec(bNodeTree *ntree, bNodeStack *stack)
2183 {
2184         bNode *node;
2185         bNodeStack *ns;
2186
2187         for(node= ntree->nodes.first; node; node= node->next) {
2188                 bNodeSocket *sock;
2189                 
2190                 for(sock= node->outputs.first; sock; sock= sock->next) {
2191                         ns = get_socket_stack(stack, sock, NULL);
2192                         if(ns && ns->data) {
2193                                 sock->ns.data= ns->data;
2194                                 ns->data= NULL;
2195                         }
2196                 }
2197                 
2198                 if(node->type==CMP_NODE_CURVE_RGB)
2199                         curvemapping_premultiply(node->storage, 1);
2200                 
2201                 if(node->type==NODE_GROUP)
2202                         composit_end_exec((bNodeTree *)node->id, stack + node->stack_index);
2203
2204                 node->need_exec= 0;
2205         }
2206 }
2207
2208 static void group_tag_used_outputs(bNode *gnode, bNodeStack *stack, bNodeStack **gin)
2209 {
2210         bNodeTree *ntree= (bNodeTree *)gnode->id;
2211         bNode *node;
2212         bNodeSocket *sock;
2213         
2214         stack+= gnode->stack_index;
2215         
2216         for(node= ntree->nodes.first; node; node= node->next) {
2217                 if(node->typeinfo->execfunc) {
2218                         for(sock= node->inputs.first; sock; sock= sock->next) {
2219                                 bNodeStack *ns = get_socket_stack(stack, sock, gin);
2220                                 ns->hasoutput= 1;
2221                         }
2222                 }
2223                 
2224                 /* set stack types (for local stack entries) */
2225                 for(sock= node->outputs.first; sock; sock= sock->next) {
2226                         bNodeStack *ns = get_socket_stack(stack, sock, NULL);
2227                         if (ns)
2228                                 ns->sockettype = sock->type;
2229                 }
2230         }
2231 }
2232
2233 /* notes below are ancient! (ton) */
2234 /* stack indices make sure all nodes only write in allocated data, for making it thread safe */
2235 /* only root tree gets the stack, to enable instances to have own stack entries */
2236 /* per tree (and per group) unique indices are created */
2237 /* the index_ext we need to be able to map from groups to the group-node own stack */
2238
2239 typedef struct bNodeThreadStack {
2240         struct bNodeThreadStack *next, *prev;
2241         bNodeStack *stack;
2242         int used;
2243 } bNodeThreadStack;
2244
2245 static bNodeThreadStack *ntreeGetThreadStack(bNodeTree *ntree, int thread)
2246 {
2247         ListBase *lb= &ntree->threadstack[thread];
2248         bNodeThreadStack *nts;
2249         
2250         for(nts=lb->first; nts; nts=nts->next) {
2251                 if(!nts->used) {
2252                         nts->used= 1;
2253                         return nts;
2254                 }
2255         }
2256         nts= MEM_callocN(sizeof(bNodeThreadStack), "bNodeThreadStack");
2257         nts->stack= MEM_dupallocN(ntree->stack);
2258         nts->used= 1;
2259         BLI_addtail(lb, nts);
2260
2261         return nts;
2262 }
2263
2264 static void ntreeReleaseThreadStack(bNodeThreadStack *nts)
2265 {
2266         nts->used= 0;
2267 }
2268
2269 /* free texture delegates */
2270 static void tex_end_exec(bNodeTree *ntree)
2271 {
2272         bNodeThreadStack *nts;
2273         bNodeStack *ns;
2274         int th, a;
2275         
2276         if(ntree->threadstack)
2277                 for(th=0; th<BLENDER_MAX_THREADS; th++)
2278                         for(nts=ntree->threadstack[th].first; nts; nts=nts->next)
2279                                 for(ns= nts->stack, a=0; a<ntree->stacksize; a++, ns++)
2280                                         if(ns->data)
2281                                                 MEM_freeN(ns->data);
2282                                                 
2283 }
2284
2285 void ntreeBeginExecTree(bNodeTree *ntree)
2286 {
2287         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2288         
2289         /* let's make it sure */
2290         if(ntree->init & NTREE_EXEC_INIT)
2291                 return;
2292         
2293         /* allocate the thread stack listbase array */
2294         if(ntree->type!=NTREE_COMPOSIT)
2295                 ntree->threadstack= MEM_callocN(BLENDER_MAX_THREADS*sizeof(ListBase), "thread stack array");
2296
2297         /* goes recursive over all groups */
2298         ntree->stacksize= ntree_begin_exec_tree(ntree);
2299
2300         if(ntree->stacksize) {
2301                 bNode *node;
2302                 bNodeStack *ns;
2303                 int a;
2304                 
2305                 /* allocate the base stack */
2306                 ns=ntree->stack= MEM_callocN(ntree->stacksize*sizeof(bNodeStack), "node stack");
2307                 
2308                 /* tag inputs, the get_stack() gives own socket stackdata if not in use */
2309                 for(a=0; a<ntree->stacksize; a++, ns++) ns->hasinput= 1;
2310                 
2311                 /* tag used outputs, so we know when we can skip operations */
2312                 for(node= ntree->nodes.first; node; node= node->next) {
2313                         bNodeSocket *sock;
2314                         
2315                         /* composite has own need_exec tag handling */
2316                         if(ntree->type!=NTREE_COMPOSIT)
2317                                 node->need_exec= 1;
2318
2319                         for(sock= node->inputs.first; sock; sock= sock->next) {
2320                                 ns = get_socket_stack(ntree->stack, sock, NULL);
2321                                 if (ns) {
2322                                         ns->hasoutput = 1;
2323                                         
2324                                         /* sock type is needed to detect rgba or value or vector types */
2325                                         if(sock->link)
2326                                                 ns->sockettype= sock->link->fromsock->type;
2327                                         else
2328                                                 sock->ns.sockettype= sock->type;
2329                                 }
2330                                 
2331                                 if(sock->link) {
2332                                         bNodeLink *link= sock->link;
2333                                         /* this is the test for a cyclic case */
2334                                         if(link->fromnode && link->tonode) {
2335                                                 if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF);
2336                                                 else {
2337                                                         node->need_exec= 0;
2338                                                 }
2339                                         }
2340                                 }
2341                         }
2342                         
2343                         /* set stack types (for local stack entries) */
2344                         for(sock= node->outputs.first; sock; sock= sock->next) {
2345                                 ns = get_socket_stack(ntree->stack, sock, NULL);
2346                                 if (ns)
2347                                         ns->sockettype = sock->type;
2348                         }
2349                         
2350                         if(node->type==NODE_GROUP && node->id) {
2351                                 node_get_stack(node, ntree->stack, nsin, NULL, NULL);
2352                                 group_tag_used_outputs(node, ntree->stack, nsin);
2353                         }
2354                 }
2355                 
2356                 if(ntree->type==NTREE_COMPOSIT)
2357                         composit_begin_exec(ntree, ntree->stack);
2358         }
2359         
2360         ntree->init |= NTREE_EXEC_INIT;
2361 }
2362
2363 void ntreeEndExecTree(bNodeTree *ntree)
2364 {
2365         bNodeStack *ns;
2366         
2367         if(ntree->init & NTREE_EXEC_INIT) {
2368                 bNodeThreadStack *nts;
2369                 int a;
2370                 
2371                 /* another callback candidate! */
2372                 if(ntree->type==NTREE_COMPOSIT) {
2373                         composit_end_exec(ntree, ntree->stack);
2374                         
2375                         for(ns= ntree->stack, a=0; a<ntree->stacksize; a++, ns++) {
2376                                 if(ns->data) {
2377                                         printf("freed leftover buffer from stack\n");
2378                                         free_compbuf(ns->data);
2379                                         ns->data= NULL;
2380                                 }
2381                         }
2382                 }
2383                 else if(ntree->type==NTREE_TEXTURE)
2384                         tex_end_exec(ntree);
2385                 
2386                 if(ntree->stack) {
2387                         MEM_freeN(ntree->stack);
2388                         ntree->stack= NULL;
2389                 }
2390
2391                 if(ntree->threadstack) {
2392                         for(a=0; a<BLENDER_MAX_THREADS; a++) {
2393                                 for(nts=ntree->threadstack[a].first; nts; nts=nts->next)
2394                                         if (nts->stack) MEM_freeN(nts->stack);
2395                                 BLI_freelistN(&ntree->threadstack[a]);
2396                         }
2397
2398                         MEM_freeN(ntree->threadstack);
2399                         ntree->threadstack= NULL;
2400                 }
2401
2402                 ntree->init &= ~NTREE_EXEC_INIT;
2403         }
2404 }
2405
2406 /* nodes are presorted, so exec is in order of list */
2407 void ntreeExecTree(bNodeTree *ntree, void *callerdata, int thread)
2408 {
2409         bNode *node;
2410         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2411         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2412         bNodeStack *stack;
2413         bNodeThreadStack *nts = NULL;
2414         
2415         /* only when initialized */
2416         if((ntree->init & NTREE_EXEC_INIT)==0)
2417                 ntreeBeginExecTree(ntree);
2418         
2419         /* composite does 1 node per thread, so no multiple stacks needed */
2420         if(ntree->type==NTREE_COMPOSIT) {
2421                 stack= ntree->stack;
2422         }
2423         else {
2424                 nts= ntreeGetThreadStack(ntree, thread);
2425                 stack= nts->stack;
2426         }
2427         
2428         for(node= ntree->nodes.first; node; node= node->next) {
2429                 if(node->need_exec) {
2430                         if(node->typeinfo->execfunc) {
2431                                 node_get_stack(node, stack, nsin, nsout, NULL);
2432                                 node->typeinfo->execfunc(callerdata, node, nsin, nsout);
2433                         }
2434                         else if(node->type==NODE_GROUP && node->id) {
2435                                 node_get_stack(node, stack, nsin, NULL, NULL);
2436                                 node_group_execute(stack, callerdata, node, nsin);
2437                         }
2438                 }
2439         }
2440
2441         if(nts)
2442                 ntreeReleaseThreadStack(nts);
2443 }
2444
2445
2446 /* ***************************** threaded version for execute composite nodes ************* */
2447 /* these are nodes without input, only giving values */
2448 /* or nodes with only value inputs */
2449 static int node_only_value(bNode *node)
2450 {
2451         bNodeSocket *sock;
2452         
2453         if(ELEM3(node->type, CMP_NODE_TIME, CMP_NODE_VALUE, CMP_NODE_RGB))
2454                 return 1;
2455         
2456         /* doing this for all node types goes wrong. memory free errors */
2457         if(node->inputs.first && node->type==CMP_NODE_MAP_VALUE) {
2458                 int retval= 1;
2459                 for(sock= node->inputs.first; sock; sock= sock->next) {
2460                         if(sock->link)
2461                                 retval &= node_only_value(sock->link->fromnode);
2462                 }
2463                 return retval;
2464         }
2465         return 0;
2466 }
2467
2468
2469 /* not changing info, for thread callback */
2470 typedef struct ThreadData {
2471         bNodeStack *stack;
2472         RenderData *rd;
2473 } ThreadData;
2474
2475 static void *exec_composite_node(void *node_v)
2476 {
2477         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2478         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2479         bNode *node= node_v;
2480         ThreadData *thd= (ThreadData *)node->threaddata;
2481         
2482         node_get_stack(node, thd->stack, nsin, nsout, NULL);
2483         
2484         if((node->flag & NODE_MUTED) && (!node_only_value(node))) {
2485                 /* viewers we execute, for feedback to user */
2486                 if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) 
2487                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2488                 else
2489                         node_compo_pass_on(node, nsin, nsout);
2490         }
2491         else if(node->typeinfo->execfunc) {
2492                 node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2493         }
2494         else if(node->type==NODE_GROUP && node->id) {
2495                 node_group_execute(thd->stack, thd->rd, node, nsin); 
2496         }
2497         
2498         node->exec |= NODE_READY;
2499         return NULL;
2500 }
2501
2502 /* return total of executable nodes, for timecursor */
2503 /* only compositor uses it */
2504 static int setExecutableNodes(bNodeTree *ntree, ThreadData *thd)
2505 {
2506         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2507         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2508         bNode *node;
2509         bNodeSocket *sock;
2510         int totnode= 0, group_edit= 0;
2511         
2512         /* note; do not add a dependency sort here, the stack was created already */
2513         
2514         /* if we are in group edit, viewer nodes get skipped when group has viewer */
2515         for(node= ntree->nodes.first; node; node= node->next)
2516                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
2517                         if(ntreeHasType((bNodeTree *)node->id, CMP_NODE_VIEWER))
2518                                 group_edit= 1;
2519         
2520         for(node= ntree->nodes.first; node; node= node->next) {
2521                 int a;
2522                 
2523                 node_get_stack(node, thd->stack, nsin, nsout, NULL);
2524                 
2525                 /* test the outputs */
2526                 /* skip value-only nodes (should be in type!) */
2527                 if(!node_only_value(node)) {
2528                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
2529                                 if(nsout[a]->data==NULL && nsout[a]->hasoutput) {
2530                                         node->need_exec= 1;
2531                                         break;
2532                                 }
2533                         }
2534                 }
2535                 
2536                 /* test the inputs */
2537                 for(a=0, sock= node->inputs.first; sock; sock= sock->next, a++) {
2538                         /* skip viewer nodes in bg render or group edit */
2539                         if( ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) && (G.background || group_edit))
2540                                 node->need_exec= 0;
2541                         /* is sock in use? */
2542                         else if(sock->link) {
2543                                 bNodeLink *link= sock->link;
2544                                 
2545                                 /* this is the test for a cyclic case */
2546                                 if(link->fromnode==NULL || link->tonode==NULL);
2547                                 else if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF) {
2548                                         if(link->fromnode->need_exec) {
2549                                                 node->need_exec= 1;
2550                                                 break;
2551                                         }
2552                                 }
2553                                 else {
2554                                         node->need_exec= 0;
2555                                         printf("Node %s skipped, cyclic dependency\n", node->name);
2556                                 }
2557                         }
2558                 }
2559                 
2560                 if(node->need_exec) {
2561                         
2562                         /* free output buffers */
2563                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
2564                                 if(nsout[a]->data) {
2565                                         free_compbuf(nsout[a]->data);
2566                                         nsout[a]->data= NULL;
2567                                 }
2568                         }
2569                         totnode++;
2570                         /* printf("node needs exec %s\n", node->name); */
2571                         
2572                         /* tag for getExecutableNode() */
2573                         node->exec= 0;
2574                 }
2575                 else {
2576                         /* tag for getExecutableNode() */
2577                         node->exec= NODE_READY|NODE_FINISHED|NODE_SKIPPED;
2578                         
2579                 }
2580         }
2581         
2582         /* last step: set the stack values for only-value nodes */
2583         /* just does all now, compared to a full buffer exec this is nothing */
2584         if(totnode) {
2585                 for(node= ntree->nodes.first; node; node= node->next) {
2586                         if(node->need_exec==0 && node_only_value(node)) {
2587                                 if(node->typeinfo->execfunc) {
2588                                         node_get_stack(node, thd->stack, nsin, nsout, NULL);
2589                                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2590                                 }
2591                         }
2592                 }
2593         }
2594         
2595         return totnode;
2596 }
2597
2598 /* while executing tree, free buffers from nodes that are not needed anymore */
2599 static void freeExecutableNode(bNodeTree *ntree)
2600 {
2601         /* node outputs can be freed when:
2602         - not a render result or image node
2603         - when node outputs go to nodes all being set NODE_FINISHED
2604         */
2605         bNode *node;
2606         bNodeSocket *sock;
2607         
2608         /* set exec flag for finished nodes that might need freed */
2609         for(node= ntree->nodes.first; node; node= node->next) {
2610                 if(node->type!=CMP_NODE_R_LAYERS)
2611                         if(node->exec & NODE_FINISHED)
2612                                 node->exec |= NODE_FREEBUFS;
2613         }
2614         /* clear this flag for input links that are not done yet */
2615         for(node= ntree->nodes.first; node; node= node->next) {
2616                 if((node->exec & NODE_FINISHED)==0) {
2617                         for(sock= node->inputs.first; sock; sock= sock->next)
2618                                 if(sock->link)
2619                                         sock->link->fromnode->exec &= ~NODE_FREEBUFS;
2620                 }
2621         }
2622         /* now we can free buffers */
2623         for(node= ntree->nodes.first; node; node= node->next) {
2624                 if(node->exec & NODE_FREEBUFS) {
2625                         for(sock= node->outputs.first; sock; sock= sock->next) {
2626                                 bNodeStack *ns= get_socket_stack(ntree->stack, sock, NULL);
2627                                 if(ns && ns->data) {
2628                                         free_compbuf(ns->data);
2629                                         ns->data= NULL;
2630                                         // printf("freed buf node %s \n", node->name);
2631                                 }
2632                         }
2633                 }
2634         }
2635 }
2636
2637 static bNode *getExecutableNode(bNodeTree *ntree)
2638 {
2639         bNode *node;
2640         bNodeSocket *sock;
2641         
2642         for(node= ntree->nodes.first; node; node= node->next) {
2643                 if(node->exec==0) {
2644                         
2645                         /* input sockets should be ready */
2646                         for(sock= node->inputs.first; sock; sock= sock->next) {
2647                                 if(sock->link && sock->link->fromnode)
2648                                         if((sock->link->fromnode->exec & NODE_READY)==0)
2649                                                 break;
2650                         }
2651                         if(sock==NULL)
2652                                 return node;
2653                 }
2654         }
2655         return NULL;
2656 }
2657
2658 /* check if texture nodes need exec or end */
2659 static  void ntree_composite_texnode(bNodeTree *ntree, int init)
2660 {
2661         bNode *node;
2662         
2663         for(node= ntree->nodes.first; node; node= node->next) {
2664                 if(node->type==CMP_NODE_TEXTURE && node->id) {
2665                         Tex *tex= (Tex *)node->id;
2666                         if(tex->nodetree && tex->use_nodes) {
2667                                 /* has internal flag to detect it only does it once */
2668                                 if(init)
2669                                         ntreeBeginExecTree(tex->nodetree); 
2670                                 else
2671                                         ntreeEndExecTree(tex->nodetree);
2672                         }
2673                 }
2674         }
2675
2676 }
2677
2678 /* optimized tree execute test for compositing */
2679 void ntreeCompositExecTree(bNodeTree *ntree, RenderData *rd, int do_preview)
2680 {
2681         bNode *node;
2682         ListBase threads;
2683         ThreadData thdata;
2684         int totnode, curnode, rendering= 1;
2685         
2686         if(ntree==NULL) return;
2687         
2688         if(do_preview)
2689                 ntreeInitPreview(ntree, 0, 0);
2690         
2691         ntreeBeginExecTree(ntree);
2692         ntree_composite_texnode(ntree, 1);
2693         
2694         /* prevent unlucky accidents */
2695         if(G.background)
2696                 rd->scemode &= ~R_COMP_CROP;
2697         
2698         /* setup callerdata for thread callback */
2699         thdata.rd= rd;
2700         thdata.stack= ntree->stack;
2701         
2702         /* fixed seed, for example noise texture */
2703         BLI_srandom(rd->cfra);
2704
2705         /* ensures only a single output node is enabled */
2706         ntreeSetOutput(ntree);
2707
2708         /* sets need_exec tags in nodes */
2709         curnode = totnode= setExecutableNodes(ntree, &thdata);
2710
2711         BLI_init_threads(&threads, exec_composite_node, rd->threads);
2712         
2713         while(rendering) {
2714                 
2715                 if(BLI_available_threads(&threads)) {
2716                         node= getExecutableNode(ntree);
2717                         if(node) {
2718                                 if(ntree->progress && totnode)
2719                                         ntree->progress(ntree->prh, (1.0 - curnode/(float)totnode));
2720                                 if(ntree->stats_draw) {
2721                                         char str[64];
2722                                         sprintf(str, "Compositing %d %s", curnode, node->name);
2723                                         ntree->stats_draw(ntree->sdh, str);
2724                                 }
2725                                 curnode--;
2726                                 
2727                                 node->threaddata = &thdata;
2728                                 node->exec= NODE_PROCESSING;
2729                                 BLI_insert_thread(&threads, node);
2730                         }
2731                         else
2732                                 PIL_sleep_ms(50);
2733                 }
2734                 else
2735                         PIL_sleep_ms(50);
2736                 
2737                 rendering= 0;
2738                 /* test for ESC */
2739                 if(ntree->test_break && ntree->test_break(ntree->tbh)) {
2740                         for(node= ntree->nodes.first; node; node= node->next)
2741                                 node->exec |= NODE_READY;
2742                 }
2743                 
2744                 /* check for ready ones, and if we need to continue */
2745                 for(node= ntree->nodes.first; node; node= node->next) {
2746                         if(node->exec & NODE_READY) {
2747                                 if((node->exec & NODE_FINISHED)==0) {
2748                                         BLI_remove_thread(&threads, node); /* this waits for running thread to finish btw */
2749                                         node->exec |= NODE_FINISHED;
2750                                         
2751                                         /* freeing unused buffers */
2752                                         if(rd->scemode & R_COMP_FREE)
2753                                                 freeExecutableNode(ntree);
2754                                 }
2755                         }
2756                         else rendering= 1;
2757                 }
2758         }
2759         
2760         BLI_end_threads(&threads);
2761         
2762         ntreeEndExecTree(ntree);
2763 }
2764
2765
2766 /* ********** copy composite tree entirely, to allow threaded exec ******************* */
2767 /* ***************** do NOT execute this in a thread!               ****************** */
2768
2769 /* returns localized composite tree for execution in threads */
2770 /* local tree then owns all compbufs */
2771 bNodeTree *ntreeLocalize(bNodeTree *ntree)
2772 {
2773         bNodeTree *ltree;
2774         bNode *node;
2775         bNodeSocket *sock;
2776         
2777         bAction *action_backup= NULL, *tmpact_backup= NULL;
2778         
2779         /* Workaround for copying an action on each render!
2780          * set action to NULL so animdata actions dont get copied */
2781         AnimData *adt= BKE_animdata_from_id(&ntree->id);
2782
2783         if(adt) {
2784                 action_backup= adt->action;
2785                 tmpact_backup= adt->tmpact;
2786
2787                 adt->action= NULL;
2788                 adt->tmpact= NULL;
2789         }
2790
2791         /* node copy func */
2792         ltree= ntreeCopyTree(ntree);
2793
2794         if(adt) {
2795                 AnimData *ladt= BKE_animdata_from_id(&ltree->id);
2796
2797                 adt->action= ladt->action= action_backup;
2798                 adt->tmpact= ladt->tmpact= tmpact_backup;
2799
2800                 if(action_backup) action_backup->id.us++;
2801                 if(tmpact_backup) tmpact_backup->id.us++;
2802                 
2803         }
2804         /* end animdata uglyness */
2805
2806         /* ensures only a single output node is enabled */
2807         ntreeSetOutput(ntree);
2808
2809         for(node= ntree->nodes.first; node; node= node->next) {
2810                 
2811                 /* store new_node pointer to original */
2812                 node->new_node->new_node= node;
2813                 /* ensure new user input gets handled ok */
2814                 node->need_exec= 0;
2815                 
2816                 if(ntree->type==NTREE_COMPOSIT) {
2817                         /* move over the compbufs */
2818                         /* right after ntreeCopyTree() oldsock pointers are valid */
2819                         
2820                         if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2821                                 if(node->id) {
2822                                         if(node->flag & NODE_DO_OUTPUT)
2823                                                 node->new_node->id= (ID *)copy_image((Image *)node->id);
2824                                         else
2825                                                 node->new_node->id= NULL;
2826                                 }
2827                         }
2828                         
2829                         for(sock= node->outputs.first; sock; sock= sock->next) {
2830                                 
2831                                 sock->new_sock->ns.data= sock->ns.data;
2832                                 compbuf_set_node(sock->new_sock->ns.data, node->new_node);
2833                                 
2834                                 sock->ns.data= NULL;
2835                                 sock->new_sock->new_sock= sock;
2836                         }
2837                 }
2838         }
2839         
2840         return ltree;
2841 }
2842
2843 static int node_exists(bNodeTree *ntree, bNode *testnode)
2844 {
2845         bNode *node= ntree->nodes.first;
2846         for(; node; node= node->next)
2847                 if(node==testnode)
2848                         return 1;
2849         return 0;
2850 }
2851
2852 static int outsocket_exists(bNode *node, bNodeSocket *testsock)
2853 {
2854         bNodeSocket *sock= node->outputs.first;
2855         for(; sock; sock= sock->next)
2856                 if(sock==testsock)
2857                         return 1;
2858         return 0;
2859 }
2860
2861
2862 /* sync local composite with real tree */
2863 /* local composite is supposed to be running, be careful moving previews! */
2864 /* is called by jobs manager, outside threads, so it doesnt happen during draw */
2865 void ntreeLocalSync(bNodeTree *localtree, bNodeTree *ntree)
2866 {
2867         bNode *lnode;
2868         
2869         if(ntree->type==NTREE_COMPOSIT) {
2870                 /* move over the compbufs and previews */
2871                 for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2872                         if( (lnode->exec & NODE_READY) && !(lnode->exec & NODE_SKIPPED) ) {
2873                                 if(node_exists(ntree, lnode->new_node)) {
2874                                         
2875                                         if(lnode->preview && lnode->preview->rect) {
2876                                                 node_free_preview(lnode->new_node);
2877                                                 lnode->new_node->preview= lnode->preview;
2878                                                 lnode->preview= NULL;
2879                                         }
2880                                 }
2881                         }
2882                 }
2883         }
2884         else if(ntree->type==NTREE_SHADER) {
2885                 /* copy over contents of previews */
2886                 for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2887                         if(node_exists(ntree, lnode->new_node)) {
2888                                 bNode *node= lnode->new_node;
2889                                 
2890                                 if(node->preview && node->preview->rect) {
2891                                         if(lnode->preview && lnode->preview->rect) {
2892                                                 int xsize= node->preview->xsize;
2893                                                 int ysize= node->preview->ysize;
2894                                                 memcpy(node->preview->rect, lnode->preview->rect, 4*xsize + xsize*ysize*sizeof(char)*4);
2895                                         }
2896                                 }
2897                         }
2898                 }
2899         }
2900 }
2901
2902 /* merge local tree results back, and free local tree */
2903 /* we have to assume the editor already changed completely */
2904 void ntreeLocalMerge(bNodeTree *localtree, bNodeTree *ntree)
2905 {
2906         bNode *lnode;
2907         bNodeSocket *lsock;
2908         
2909         /* move over the compbufs and previews */
2910         for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2911                 if(node_exists(ntree, lnode->new_node)) {
2912                         
2913                         if(lnode->preview && lnode->preview->rect) {
2914                                 node_free_preview(lnode->new_node);
2915                                 lnode->new_node->preview= lnode->preview;
2916                                 lnode->preview= NULL;
2917                         }
2918                         
2919                         if(ELEM(lnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2920                                 if(lnode->id && (lnode->flag & NODE_DO_OUTPUT)) {
2921                                         /* image_merge does sanity check for pointers */
2922                                         BKE_image_merge((Image *)lnode->new_node->id, (Image *)lnode->id);
2923                                 }
2924                         }
2925                         
2926                         for(lsock= lnode->outputs.first; lsock; lsock= lsock->next) {
2927                                 if(outsocket_exists(lnode->new_node, lsock->new_sock)) {
2928                                         lsock->new_sock->ns.data= lsock->ns.data;
2929                                         compbuf_set_node(lsock->new_sock->ns.data, lnode->new_node);
2930                                         lsock->ns.data= NULL;
2931                                         lsock->new_sock= NULL;
2932                                 }
2933                         }
2934                 }
2935         }
2936         ntreeFreeTree(localtree);
2937         MEM_freeN(localtree);
2938 }
2939
2940 /* *********************************************** */
2941
2942 /* GPU material from shader nodes */
2943
2944 static void gpu_from_node_stack(ListBase *sockets, bNodeStack **ns, GPUNodeStack *gs)
2945 {
2946         bNodeSocket *sock;
2947         int i;
2948
2949         for (sock=sockets->first, i=0; sock; sock=sock->next, i++) {
2950                 memset(&gs[i], 0, sizeof(gs[i]));
2951
2952                 QUATCOPY(gs[i].vec, ns[i]->vec);
2953                 gs[i].link= ns[i]->data;
2954
2955                 if (sock->type == SOCK_VALUE)
2956                         gs[i].type= GPU_FLOAT;
2957                 else if (sock->type == SOCK_VECTOR)
2958                         gs[i].type= GPU_VEC3;
2959                 else if (sock->type == SOCK_RGBA)
2960                         gs[i].type= GPU_VEC4;
2961                 else
2962                         gs[i].type= GPU_NONE;
2963
2964                 gs[i].name = "";
2965                 gs[i].hasinput= ns[i]->hasinput && ns[i]->data;
2966                 gs[i].hasoutput= ns[i]->hasoutput && ns[i]->data;
2967                 gs[i].sockettype= ns[i]->sockettype;
2968         }
2969
2970         gs[i].type= GPU_NONE;
2971 }
2972
2973 static void data_from_gpu_stack(ListBase *sockets, bNodeStack **ns, GPUNodeStack *gs)
2974 {
2975         bNodeSocket *sock;
2976         int i;
2977
2978         for (sock=sockets->first, i=0; sock; sock=sock->next, i++) {
2979                 ns[i]->data= gs[i].link;
2980                 ns[i]->sockettype= gs[i].sockettype;
2981         }
2982 }
2983
2984 static void gpu_node_group_execute(bNodeStack *stack, GPUMaterial *mat, bNode *gnode, bNodeStack **in)
2985 {
2986         bNode *node;
2987         bNodeTree *ntree= (bNodeTree *)gnode->id;
2988         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2989         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2990         GPUNodeStack gpuin[MAX_SOCKET+1], gpuout[MAX_SOCKET+1];
2991         int doit = 0;
2992         
2993         if(ntree==NULL) return;
2994         
2995         stack+= gnode->stack_index;
2996                 
2997         for(node= ntree->nodes.first; node; node= node->next) {
2998                 if(node->typeinfo->gpufunc) {
2999                         node_get_stack(node, stack, nsin, nsout, in);
3000
3001                         doit = 0;
3002                         
3003                         /* for groups, only execute outputs for edited group */
3004                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
3005                                 if(gnode->flag & NODE_GROUP_EDIT)
3006                                         if(node->flag & NODE_DO_OUTPUT)
3007                                                 doit = 1;
3008                         }
3009                         else
3010                                 doit = 1;
3011
3012                         if(doit)  {
3013                                 gpu_from_node_stack(&node->inputs, nsin, gpuin);
3014                                 gpu_from_node_stack(&node->outputs, nsout, gpuout);
3015                                 if(node->typeinfo->gpufunc(mat, node, gpuin, gpuout))
3016                                         data_from_gpu_stack(&node->outputs, nsout, gpuout);
3017                         }
3018                 }
3019         }
3020 }
3021
3022 void ntreeGPUMaterialNodes(bNodeTree *ntree, GPUMaterial *mat)
3023 {
3024         bNode *node;
3025         bNodeStack *stack;
3026         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
3027         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
3028         GPUNodeStack gpuin[MAX_SOCKET+1], gpuout[MAX_SOCKET+1];
3029
3030         if((ntree->init & NTREE_EXEC_INIT)==0)
3031                 ntreeBeginExecTree(ntree);
3032
3033         stack= ntree->stack;
3034
3035         for(node= ntree->nodes.first; node; node= node->next) {
3036                 if(node->typeinfo->gpufunc) {
3037                         node_get_stack(node, stack, nsin, nsout, NULL);
3038                         gpu_from_node_stack(&node->inputs, nsin, gpuin);
3039                         gpu_from_node_stack(&node->outputs, nsout, gpuout);
3040                         if(node->typeinfo->gpufunc(mat, node, gpuin, gpuout))
3041                                 data_from_gpu_stack(&node->outputs, nsout, gpuout);
3042                 }
3043                 else if(node->type==NODE_GROUP && node->id) {
3044                         node_get_stack(node, stack, nsin, nsout, NULL);
3045                         gpu_node_group_execute(stack, mat, node, nsin);
3046                 }
3047         }
3048
3049         ntreeEndExecTree(ntree);
3050 }
3051
3052 /* **************** call to switch lamploop for material node ************ */
3053
3054 void (*node_shader_lamp_loop)(struct ShadeInput *, struct ShadeResult *);
3055
3056 void set_node_shader_lamp_loop(void (*lamp_loop_func)(ShadeInput *, ShadeResult *))
3057 {
3058         node_shader_lamp_loop= lamp_loop_func;
3059 }
3060
3061 /* clumsy checking... should do dynamic outputs once */
3062 static void force_hidden_passes(bNode *node, int passflag)
3063 {
3064         bNodeSocket *sock;
3065         
3066         for(sock= node->outputs.first; sock; sock= sock->next)
3067                 sock->flag &= ~SOCK_UNAVAIL;
3068         
3069         sock= BLI_findlink(&node->outputs, RRES_OUT_Z);
3070         if(!(passflag & SCE_PASS_Z)) sock->flag |= SOCK_UNAVAIL;
3071         sock= BLI_findlink(&node->outputs, RRES_OUT_NORMAL);
3072         if(!(passflag & SCE_PASS_NORMAL)) sock->flag |= SOCK_UNAVAIL;
3073         sock= BLI_findlink(&node->outputs, RRES_OUT_VEC);
3074         if(!(passflag & SCE_PASS_VECTOR)) sock->flag |= SOCK_UNAVAIL;
3075         sock= BLI_findlink(&node->outputs, RRES_OUT_UV);
3076         if(!(passflag & SCE_PASS_UV)) sock->flag |= SOCK_UNAVAIL;
3077         sock= BLI_findlink(&node->outputs, RRES_OUT_RGBA);
3078         if(!(passflag & SCE_PASS_RGBA)) sock->flag |= SOCK_UNAVAIL;
3079         sock= BLI_findlink(&node->outputs, RRES_OUT_DIFF);