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