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