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