merge with trunk at r31523
[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 void NodeTagIDChanged(bNodeTree *ntree, ID *id)
1791 {
1792         if(id==NULL)
1793                 return;
1794         
1795         if(ntree->type==NTREE_COMPOSIT) {
1796                 bNode *node;
1797                 
1798                 for(node= ntree->nodes.first; node; node= node->next)
1799                         if(node->id==id)
1800                                 NodeTagChanged(ntree, node);
1801         }
1802 }
1803
1804
1805
1806 /* ******************* executing ************* */
1807
1808 /* see notes at ntreeBeginExecTree */
1809 static void group_node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out, bNodeStack **gin, bNodeStack **gout)
1810 {
1811         bNodeSocket *sock;
1812         
1813         /* build pointer stack */
1814         for(sock= node->inputs.first; sock; sock= sock->next) {
1815                 if(sock->intern) {
1816                         /* yep, intern can have link or is hidden socket */
1817                         if(sock->link)
1818                                 *(in++)= stack + sock->link->fromsock->stack_index;
1819                         else
1820                                 *(in++)= &sock->ns;
1821                 }
1822                 else
1823                         *(in++)= gin[sock->stack_index_ext];
1824         }
1825         
1826         for(sock= node->outputs.first; sock; sock= sock->next) {
1827                 if(sock->intern)
1828                         *(out++)= stack + sock->stack_index;
1829                 else
1830                         *(out++)= gout[sock->stack_index_ext];
1831         }
1832 }
1833
1834 static void node_group_execute(bNodeStack *stack, void *data, bNode *gnode, bNodeStack **in, bNodeStack **out)
1835 {
1836         bNode *node;
1837         bNodeTree *ntree= (bNodeTree *)gnode->id;
1838         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1839         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1840         
1841         if(ntree==NULL) return;
1842         
1843         stack+= gnode->stack_index;
1844                 
1845         for(node= ntree->nodes.first; node; node= node->next) {
1846                 if(node->typeinfo->execfunc) {
1847                         group_node_get_stack(node, stack, nsin, nsout, in, out);
1848                         
1849                         /* for groups, only execute outputs for edited group */
1850                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1851                                 if(node->type==CMP_NODE_OUTPUT_FILE || (gnode->flag & NODE_GROUP_EDIT))
1852                                         node->typeinfo->execfunc(data, node, nsin, nsout);
1853                         }
1854                         else
1855                                 node->typeinfo->execfunc(data, node, nsin, nsout);
1856                 }
1857         }
1858         
1859         /* free internal group output nodes */
1860         if(ntree->type==NTREE_COMPOSIT) {
1861                 for(node= ntree->nodes.first; node; node= node->next) {
1862                         if(node->typeinfo->execfunc) {
1863                                 bNodeSocket *sock;
1864                                 
1865                                 for(sock= node->outputs.first; sock; sock= sock->next) {
1866                                         if(sock->intern) {
1867                                                 bNodeStack *ns= stack + sock->stack_index;
1868                                                 if(ns->data) {
1869                                                         free_compbuf(ns->data);
1870                                                         ns->data= NULL;
1871                                                 }
1872                                         }
1873                                 }
1874                         }
1875                 }
1876         }
1877 }
1878
1879 /* recursively called for groups */
1880 /* we set all trees on own local indices, but put a total counter
1881    in the groups, so each instance of a group has own stack */
1882 static int ntree_begin_exec_tree(bNodeTree *ntree)
1883 {
1884         bNode *node;
1885         bNodeSocket *sock;
1886         int index= 0, index_in= 0, index_out= 0;
1887         
1888         if((ntree->init & NTREE_TYPE_INIT)==0)
1889                 ntreeInitTypes(ntree);
1890         
1891         /* create indices for stack, check preview */
1892         for(node= ntree->nodes.first; node; node= node->next) {
1893                 
1894                 for(sock= node->inputs.first; sock; sock= sock->next) {
1895                         if(sock->intern==0)
1896                                 sock->stack_index_ext= index_in++;
1897                 }
1898                 
1899                 for(sock= node->outputs.first; sock; sock= sock->next) {
1900                         sock->stack_index= index++;
1901                         if(sock->intern==0)
1902                                 sock->stack_index_ext= index_out++;
1903                 }
1904                 
1905                 if(node->type==NODE_GROUP) {
1906                         if(node->id) {
1907                                 node->stack_index= index;
1908                                 index+= ntree_begin_exec_tree((bNodeTree *)node->id);
1909                         }
1910                 }
1911         }
1912         
1913         return index;
1914 }
1915
1916 /* copy socket compbufs to stack, initialize usage of curve nodes */
1917 static void composit_begin_exec(bNodeTree *ntree, int is_group)
1918 {
1919         bNode *node;
1920         bNodeSocket *sock;
1921         
1922         for(node= ntree->nodes.first; node; node= node->next) {
1923                 
1924                 /* initialize needed for groups */
1925                 node->exec= 0;  
1926                 
1927                 if(is_group==0) {
1928                         for(sock= node->outputs.first; sock; sock= sock->next) {
1929                                 bNodeStack *ns= ntree->stack + sock->stack_index;
1930                                 
1931                                 if(sock->ns.data) {
1932                                         ns->data= sock->ns.data;
1933                                         sock->ns.data= NULL;
1934                                 }
1935                         }
1936                 }
1937                 /* cannot initialize them while using in threads */
1938                 if(ELEM4(node->type, CMP_NODE_TIME, CMP_NODE_CURVE_VEC, CMP_NODE_CURVE_RGB, CMP_NODE_HUECORRECT)) {
1939                         curvemapping_initialize(node->storage);
1940                         if(node->type==CMP_NODE_CURVE_RGB)
1941                                 curvemapping_premultiply(node->storage, 0);
1942                 }
1943                 if(node->type==NODE_GROUP)
1944                         composit_begin_exec((bNodeTree *)node->id, 1);
1945
1946         }
1947 }
1948
1949 /* copy stack compbufs to sockets */
1950 static void composit_end_exec(bNodeTree *ntree, int is_group)
1951 {
1952         extern void print_compbuf(char *str, struct CompBuf *cbuf);
1953         bNode *node;
1954         bNodeStack *ns;
1955         int a;
1956
1957         for(node= ntree->nodes.first; node; node= node->next) {
1958                 if(is_group==0) {
1959                         bNodeSocket *sock;
1960                 
1961                         for(sock= node->outputs.first; sock; sock= sock->next) {
1962                                 ns= ntree->stack + sock->stack_index;
1963                                 if(ns->data) {
1964                                         sock->ns.data= ns->data;
1965                                         ns->data= NULL;
1966                                 }
1967                         }
1968                 }
1969                 if(node->type==CMP_NODE_CURVE_RGB)
1970                         curvemapping_premultiply(node->storage, 1);
1971                 
1972                 if(node->type==NODE_GROUP)
1973                         composit_end_exec((bNodeTree *)node->id, 1);
1974
1975                 node->need_exec= 0;
1976         }
1977         
1978         if(is_group==0) {
1979                 /* internally, group buffers are not stored */
1980                 for(ns= ntree->stack, a=0; a<ntree->stacksize; a++, ns++) {
1981                         if(ns->data) {
1982                                 printf("freed leftover buffer from stack\n");
1983                                 free_compbuf(ns->data);
1984                                 ns->data= NULL;
1985                         }
1986                 }
1987         }
1988 }
1989
1990 static void group_tag_used_outputs(bNode *gnode, bNodeStack *stack)
1991 {
1992         bNodeTree *ntree= (bNodeTree *)gnode->id;
1993         bNode *node;
1994         
1995         stack+= gnode->stack_index;
1996         
1997         for(node= ntree->nodes.first; node; node= node->next) {
1998                 if(node->typeinfo->execfunc) {
1999                         bNodeSocket *sock;
2000                         
2001                         for(sock= node->inputs.first; sock; sock= sock->next) {
2002                                 if(sock->intern) {
2003                                         if(sock->link) {
2004                                                 bNodeStack *ns= stack + sock->link->fromsock->stack_index;
2005                                                 ns->hasoutput= 1;
2006                                                 ns->sockettype= sock->link->fromsock->type;
2007                                         }
2008                                         else
2009                                                 sock->ns.sockettype= sock->type;
2010                                 }
2011                         }
2012                 }
2013         }
2014 }
2015
2016 /* notes below are ancient! (ton) */
2017 /* stack indices make sure all nodes only write in allocated data, for making it thread safe */
2018 /* only root tree gets the stack, to enable instances to have own stack entries */
2019 /* per tree (and per group) unique indices are created */
2020 /* the index_ext we need to be able to map from groups to the group-node own stack */
2021
2022 typedef struct bNodeThreadStack {
2023         struct bNodeThreadStack *next, *prev;
2024         bNodeStack *stack;
2025         int used;
2026 } bNodeThreadStack;
2027
2028 static bNodeThreadStack *ntreeGetThreadStack(bNodeTree *ntree, int thread)
2029 {
2030         ListBase *lb= &ntree->threadstack[thread];
2031         bNodeThreadStack *nts;
2032         
2033         for(nts=lb->first; nts; nts=nts->next) {
2034                 if(!nts->used) {
2035                         nts->used= 1;
2036                         return nts;
2037                 }
2038         }
2039         nts= MEM_callocN(sizeof(bNodeThreadStack), "bNodeThreadStack");
2040         nts->stack= MEM_dupallocN(ntree->stack);
2041         nts->used= 1;
2042         BLI_addtail(lb, nts);
2043
2044         return nts;
2045 }
2046
2047 static void ntreeReleaseThreadStack(bNodeThreadStack *nts)
2048 {
2049         nts->used= 0;
2050 }
2051
2052 /* free texture delegates */
2053 static void tex_end_exec(bNodeTree *ntree)
2054 {
2055         bNodeThreadStack *nts;
2056         bNodeStack *ns;
2057         int th, a;
2058         
2059         if(ntree->threadstack)
2060                 for(th=0; th<BLENDER_MAX_THREADS; th++)
2061                         for(nts=ntree->threadstack[th].first; nts; nts=nts->next)
2062                                 for(ns= nts->stack, a=0; a<ntree->stacksize; a++, ns++)
2063                                         if(ns->data)
2064                                                 MEM_freeN(ns->data);
2065                                                 
2066 }
2067
2068 void ntreeBeginExecTree(bNodeTree *ntree)
2069 {
2070         /* let's make it sure */
2071         if(ntree->init & NTREE_EXEC_INIT)
2072                 return;
2073         
2074         /* allocate the thread stack listbase array */
2075         if(ntree->type!=NTREE_COMPOSIT)
2076                 ntree->threadstack= MEM_callocN(BLENDER_MAX_THREADS*sizeof(ListBase), "thread stack array");
2077
2078         /* goes recursive over all groups */
2079         ntree->stacksize= ntree_begin_exec_tree(ntree);
2080
2081         if(ntree->stacksize) {
2082                 bNode *node;
2083                 bNodeStack *ns;
2084                 int a;
2085                 
2086                 /* allocate the base stack */
2087                 ns=ntree->stack= MEM_callocN(ntree->stacksize*sizeof(bNodeStack), "node stack");
2088                 
2089                 /* tag inputs, the get_stack() gives own socket stackdata if not in use */
2090                 for(a=0; a<ntree->stacksize; a++, ns++) ns->hasinput= 1;
2091                 
2092                 /* tag used outputs, so we know when we can skip operations */
2093                 for(node= ntree->nodes.first; node; node= node->next) {
2094                         bNodeSocket *sock;
2095                         
2096                         /* composite has own need_exec tag handling */
2097                         if(ntree->type!=NTREE_COMPOSIT)
2098                                 node->need_exec= 1;
2099
2100                         for(sock= node->inputs.first; sock; sock= sock->next) {
2101                                 if(sock->link) {
2102                                         ns= ntree->stack + sock->link->fromsock->stack_index;
2103                                         ns->hasoutput= 1;
2104                                         ns->sockettype= sock->link->fromsock->type;
2105                                 }
2106                                 else
2107                                         sock->ns.sockettype= sock->type;
2108                                 
2109                                 if(sock->link) {
2110                                         bNodeLink *link= sock->link;
2111                                         /* this is the test for a cyclic case */
2112                                         if(link->fromnode && link->tonode) {
2113                                                 if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF);
2114                                                 else {
2115                                                         node->need_exec= 0;
2116                                                 }
2117                                         }
2118                                 }
2119                         }
2120                         
2121                         if(node->type==NODE_GROUP && node->id)
2122                                 group_tag_used_outputs(node, ntree->stack);
2123                         
2124                 }
2125                 
2126                 if(ntree->type==NTREE_COMPOSIT)
2127                         composit_begin_exec(ntree, 0);
2128         }
2129         
2130         ntree->init |= NTREE_EXEC_INIT;
2131 }
2132
2133 void ntreeEndExecTree(bNodeTree *ntree)
2134 {
2135         
2136         if(ntree->init & NTREE_EXEC_INIT) {
2137                 bNodeThreadStack *nts;
2138                 int a;
2139                 
2140                 /* another callback candidate! */
2141                 if(ntree->type==NTREE_COMPOSIT)
2142                         composit_end_exec(ntree, 0);
2143                 else if(ntree->type==NTREE_TEXTURE)
2144                         tex_end_exec(ntree);
2145                 
2146                 if(ntree->stack) {
2147                         MEM_freeN(ntree->stack);
2148                         ntree->stack= NULL;
2149                 }
2150
2151                 if(ntree->threadstack) {
2152                         for(a=0; a<BLENDER_MAX_THREADS; a++) {
2153                                 for(nts=ntree->threadstack[a].first; nts; nts=nts->next)
2154                                         if (nts->stack) MEM_freeN(nts->stack);
2155                                 BLI_freelistN(&ntree->threadstack[a]);
2156                         }
2157
2158                         MEM_freeN(ntree->threadstack);
2159                         ntree->threadstack= NULL;
2160                 }
2161
2162                 ntree->init &= ~NTREE_EXEC_INIT;
2163         }
2164 }
2165
2166 static void node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out)
2167 {
2168         bNodeSocket *sock;
2169         
2170         /* build pointer stack */
2171         for(sock= node->inputs.first; sock; sock= sock->next) {
2172                 if(sock->link)
2173                         *(in++)= stack + sock->link->fromsock->stack_index;
2174                 else
2175                         *(in++)= &sock->ns;
2176         }
2177         
2178         for(sock= node->outputs.first; sock; sock= sock->next) {
2179                 *(out++)= stack + sock->stack_index;
2180         }
2181 }
2182
2183 /* nodes are presorted, so exec is in order of list */
2184 void ntreeExecTree(bNodeTree *ntree, void *callerdata, int thread)
2185 {
2186         bNode *node;
2187         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2188         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2189         bNodeStack *stack;
2190         bNodeThreadStack *nts = NULL;
2191         
2192         /* only when initialized */
2193         if((ntree->init & NTREE_EXEC_INIT)==0)
2194                 ntreeBeginExecTree(ntree);
2195                 
2196         /* composite does 1 node per thread, so no multiple stacks needed */
2197         if(ntree->type==NTREE_COMPOSIT) {
2198                 stack= ntree->stack;
2199         }
2200         else {
2201                 nts= ntreeGetThreadStack(ntree, thread);
2202                 stack= nts->stack;
2203         }
2204         
2205         for(node= ntree->nodes.first; node; node= node->next) {
2206                 if(node->need_exec) {
2207                         if(node->typeinfo->execfunc) {
2208                                 node_get_stack(node, stack, nsin, nsout);
2209                                 node->typeinfo->execfunc(callerdata, node, nsin, nsout);
2210                         }
2211                         else if(node->type==NODE_GROUP && node->id) {
2212                                 node_get_stack(node, stack, nsin, nsout);
2213                                 node_group_execute(stack, callerdata, node, nsin, nsout); 
2214                         }
2215                 }
2216         }
2217
2218         if(nts)
2219                 ntreeReleaseThreadStack(nts);
2220 }
2221
2222
2223 /* ***************************** threaded version for execute composite nodes ************* */
2224 /* these are nodes without input, only giving values */
2225 /* or nodes with only value inputs */
2226 static int node_only_value(bNode *node)
2227 {
2228         bNodeSocket *sock;
2229         
2230         if(ELEM3(node->type, CMP_NODE_TIME, CMP_NODE_VALUE, CMP_NODE_RGB))
2231                 return 1;
2232         
2233         /* doing this for all node types goes wrong. memory free errors */
2234         if(node->inputs.first && node->type==CMP_NODE_MAP_VALUE) {
2235                 int retval= 1;
2236                 for(sock= node->inputs.first; sock; sock= sock->next) {
2237                         if(sock->link)
2238                                 retval &= node_only_value(sock->link->fromnode);
2239                 }
2240                 return retval;
2241         }
2242         return 0;
2243 }
2244
2245
2246 /* not changing info, for thread callback */
2247 typedef struct ThreadData {
2248         bNodeStack *stack;
2249         RenderData *rd;
2250 } ThreadData;
2251
2252 static void *exec_composite_node(void *node_v)
2253 {
2254         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2255         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2256         bNode *node= node_v;
2257         ThreadData *thd= (ThreadData *)node->threaddata;
2258         
2259         node_get_stack(node, thd->stack, nsin, nsout);
2260         
2261         if((node->flag & NODE_MUTED) && (!node_only_value(node))) {
2262                 /* viewers we execute, for feedback to user */
2263                 if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) 
2264                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2265                 else
2266                         node_compo_pass_on(node, nsin, nsout);
2267         }
2268         else if(node->typeinfo->execfunc) {
2269                 node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2270         }
2271         else if(node->type==NODE_GROUP && node->id) {
2272                 node_group_execute(thd->stack, thd->rd, node, nsin, nsout); 
2273         }
2274         
2275         node->exec |= NODE_READY;
2276         return 0;
2277 }
2278
2279 /* return total of executable nodes, for timecursor */
2280 /* only compositor uses it */
2281 static int setExecutableNodes(bNodeTree *ntree, ThreadData *thd)
2282 {
2283         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2284         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2285         bNode *node;
2286         bNodeSocket *sock;
2287         int totnode= 0, group_edit= 0;
2288         
2289         /* note; do not add a dependency sort here, the stack was created already */
2290         
2291         /* if we are in group edit, viewer nodes get skipped when group has viewer */
2292         for(node= ntree->nodes.first; node; node= node->next)
2293                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
2294                         if(ntreeHasType((bNodeTree *)node->id, CMP_NODE_VIEWER))
2295                                 group_edit= 1;
2296         
2297         for(node= ntree->nodes.first; node; node= node->next) {
2298                 int a;
2299                 
2300                 node_get_stack(node, thd->stack, nsin, nsout);
2301                 
2302                 /* test the outputs */
2303                 /* skip value-only nodes (should be in type!) */
2304                 if(!node_only_value(node)) {
2305                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
2306                                 if(nsout[a]->data==NULL && nsout[a]->hasoutput) {
2307                                         node->need_exec= 1;
2308                                         break;
2309                                 }
2310                         }
2311                 }
2312                 
2313                 /* test the inputs */
2314                 for(a=0, sock= node->inputs.first; sock; sock= sock->next, a++) {
2315                         /* skip viewer nodes in bg render or group edit */
2316                         if( ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) && (G.background || group_edit))
2317                                 node->need_exec= 0;
2318                         /* is sock in use? */
2319                         else if(sock->link) {
2320                                 bNodeLink *link= sock->link;
2321                                 
2322                                 /* this is the test for a cyclic case */
2323                                 if(link->fromnode==NULL || link->tonode==NULL);
2324                                 else if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF) {
2325                                         if(link->fromnode->need_exec) {
2326                                                 node->need_exec= 1;
2327                                                 break;
2328                                         }
2329                                 }
2330                                 else {
2331                                         node->need_exec= 0;
2332                                         printf("Node %s skipped, cyclic dependency\n", node->name);
2333                                 }
2334                         }
2335                 }
2336                 
2337                 if(node->need_exec) {
2338                         
2339                         /* free output buffers */
2340                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
2341                                 if(nsout[a]->data) {
2342                                         free_compbuf(nsout[a]->data);
2343                                         nsout[a]->data= NULL;
2344                                 }
2345                         }
2346                         totnode++;
2347                         /* printf("node needs exec %s\n", node->name); */
2348                         
2349                         /* tag for getExecutableNode() */
2350                         node->exec= 0;
2351                 }
2352                 else {
2353                         /* tag for getExecutableNode() */
2354                         node->exec= NODE_READY|NODE_FINISHED|NODE_SKIPPED;
2355                         
2356                 }
2357         }
2358         
2359         /* last step: set the stack values for only-value nodes */
2360         /* just does all now, compared to a full buffer exec this is nothing */
2361         if(totnode) {
2362                 for(node= ntree->nodes.first; node; node= node->next) {
2363                         if(node->need_exec==0 && node_only_value(node)) {
2364                                 if(node->typeinfo->execfunc) {
2365                                         node_get_stack(node, thd->stack, nsin, nsout);
2366                                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2367                                 }
2368                         }
2369                 }
2370         }
2371         
2372         return totnode;
2373 }
2374
2375 /* while executing tree, free buffers from nodes that are not needed anymore */
2376 static void freeExecutableNode(bNodeTree *ntree)
2377 {
2378         /* node outputs can be freed when:
2379         - not a render result or image node
2380         - when node outputs go to nodes all being set NODE_FINISHED
2381         */
2382         bNode *node;
2383         bNodeSocket *sock;
2384         
2385         /* set exec flag for finished nodes that might need freed */
2386         for(node= ntree->nodes.first; node; node= node->next) {
2387                 if(node->type!=CMP_NODE_R_LAYERS)
2388                         if(node->exec & NODE_FINISHED)
2389                                 node->exec |= NODE_FREEBUFS;
2390         }
2391         /* clear this flag for input links that are not done yet */
2392         for(node= ntree->nodes.first; node; node= node->next) {
2393                 if((node->exec & NODE_FINISHED)==0) {
2394                         for(sock= node->inputs.first; sock; sock= sock->next)
2395                                 if(sock->link)
2396                                         sock->link->fromnode->exec &= ~NODE_FREEBUFS;
2397                 }
2398         }
2399         /* now we can free buffers */
2400         for(node= ntree->nodes.first; node; node= node->next) {
2401                 if(node->exec & NODE_FREEBUFS) {
2402                         for(sock= node->outputs.first; sock; sock= sock->next) {
2403                                 bNodeStack *ns= ntree->stack + sock->stack_index;
2404                                 if(ns->data) {
2405                                         free_compbuf(ns->data);
2406                                         ns->data= NULL;
2407                                         // printf("freed buf node %s \n", node->name);
2408                                 }
2409                         }
2410                 }
2411         }
2412 }
2413
2414 static bNode *getExecutableNode(bNodeTree *ntree)
2415 {
2416         bNode *node;
2417         bNodeSocket *sock;
2418         
2419         for(node= ntree->nodes.first; node; node= node->next) {
2420                 if(node->exec==0) {
2421                         
2422                         /* input sockets should be ready */
2423                         for(sock= node->inputs.first; sock; sock= sock->next) {
2424                                 if(sock->link)
2425                                         if((sock->link->fromnode->exec & NODE_READY)==0)
2426                                                 break;
2427                         }
2428                         if(sock==NULL)
2429                                 return node;
2430                 }
2431         }
2432         return NULL;
2433 }
2434
2435
2436 /* optimized tree execute test for compositing */
2437 void ntreeCompositExecTree(bNodeTree *ntree, RenderData *rd, int do_preview)
2438 {
2439         bNode *node;
2440         ListBase threads;
2441         ThreadData thdata;
2442         int totnode, curnode, rendering= 1;
2443         
2444         if(ntree==NULL) return;
2445         
2446         if(do_preview)
2447                 ntreeInitPreview(ntree, 0, 0);
2448         
2449         ntreeBeginExecTree(ntree);
2450         
2451         /* prevent unlucky accidents */
2452         if(G.background)
2453                 rd->scemode &= ~R_COMP_CROP;
2454         
2455         /* setup callerdata for thread callback */
2456         thdata.rd= rd;
2457         thdata.stack= ntree->stack;
2458         
2459         /* fixed seed, for example noise texture */
2460         BLI_srandom(rd->cfra);
2461
2462         /* sets need_exec tags in nodes */
2463         curnode = totnode= setExecutableNodes(ntree, &thdata);
2464
2465         BLI_init_threads(&threads, exec_composite_node, rd->threads);
2466         
2467         while(rendering) {
2468                 
2469                 if(BLI_available_threads(&threads)) {
2470                         node= getExecutableNode(ntree);
2471                         if(node) {
2472                                 
2473                                 if(ntree->progress && totnode)
2474                                         ntree->progress(ntree->prh, (1.0 - curnode/(float)totnode));
2475                                 if(ntree->stats_draw) {
2476                                         char str[64];
2477                                         sprintf(str, "Compositing %d %s", curnode, node->name);
2478                                         ntree->stats_draw(ntree->sdh, str);
2479                                 }
2480                                 curnode--;
2481                                 
2482                                 node->threaddata = &thdata;
2483                                 node->exec= NODE_PROCESSING;
2484                                 BLI_insert_thread(&threads, node);
2485                         }
2486                         else
2487                                 PIL_sleep_ms(50);
2488                 }
2489                 else
2490                         PIL_sleep_ms(50);
2491                 
2492                 rendering= 0;
2493                 /* test for ESC */
2494                 if(ntree->test_break && ntree->test_break(ntree->tbh)) {
2495                         for(node= ntree->nodes.first; node; node= node->next)
2496                                 node->exec |= NODE_READY;
2497                 }
2498                 
2499                 /* check for ready ones, and if we need to continue */
2500                 for(node= ntree->nodes.first; node; node= node->next) {
2501                         if(node->exec & NODE_READY) {
2502                                 if((node->exec & NODE_FINISHED)==0) {
2503                                         BLI_remove_thread(&threads, node); /* this waits for running thread to finish btw */
2504                                         node->exec |= NODE_FINISHED;
2505                                         
2506                                         /* freeing unused buffers */
2507                                         if(rd->scemode & R_COMP_FREE)
2508                                                 freeExecutableNode(ntree);
2509                                 }
2510                         }
2511                         else rendering= 1;
2512                 }
2513         }
2514         
2515         BLI_end_threads(&threads);
2516         
2517         ntreeEndExecTree(ntree);
2518 }
2519
2520
2521 /* ********** copy composite tree entirely, to allow threaded exec ******************* */
2522 /* ***************** do NOT execute this in a thread!               ****************** */
2523
2524 /* returns localized composite tree for execution in threads */
2525 /* local tree then owns all compbufs */
2526 bNodeTree *ntreeLocalize(bNodeTree *ntree)
2527 {
2528         bNodeTree *ltree;
2529         bNode *node;
2530         bNodeSocket *sock;
2531         
2532         bAction *action_backup= NULL, *tmpact_backup= NULL;
2533         
2534         /* Workaround for copying an action on each render!
2535          * set action to NULL so animdata actions dont get copied */
2536         AnimData *adt= BKE_animdata_from_id(&ntree->id);
2537
2538         if(adt) {
2539                 action_backup= adt->action;
2540                 tmpact_backup= adt->tmpact;
2541
2542                 adt->action= NULL;
2543                 adt->tmpact= NULL;
2544         }
2545
2546         /* node copy func */
2547         ltree= ntreeCopyTree(ntree, 0);
2548
2549         if(adt) {
2550                 AnimData *ladt= BKE_animdata_from_id(&ltree->id);
2551
2552                 adt->action= ladt->action= action_backup;
2553                 adt->tmpact= ladt->tmpact= tmpact_backup;
2554
2555                 if(action_backup) action_backup->id.us++;
2556                 if(tmpact_backup) tmpact_backup->id.us++;
2557                 
2558         }
2559         /* end animdata uglyness */
2560         
2561         /* move over the compbufs */
2562         /* right after ntreeCopyTree() oldsock pointers are valid */
2563         for(node= ntree->nodes.first; node; node= node->next) {
2564                 
2565                 /* store new_node pointer to original */
2566                 node->new_node->new_node= node;
2567                 /* ensure new user input gets handled ok */
2568                 node->need_exec= 0;
2569                 
2570                 if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2571                         if(node->id) {
2572                                 if(node->flag & NODE_DO_OUTPUT)
2573                                         node->new_node->id= (ID *)copy_image((Image *)node->id);
2574                                 else
2575                                         node->new_node->id= NULL;
2576                         }
2577                 }
2578                 
2579                 for(sock= node->outputs.first; sock; sock= sock->next) {
2580                         
2581                         sock->new_sock->ns.data= sock->ns.data;
2582                         compbuf_set_node(sock->new_sock->ns.data, node->new_node);
2583                         
2584                         sock->ns.data= NULL;
2585                         sock->new_sock->new_sock= sock;
2586                 }
2587         }
2588         
2589         return ltree;
2590 }
2591
2592 static int node_exists(bNodeTree *ntree, bNode *testnode)
2593 {
2594         bNode *node= ntree->nodes.first;
2595         for(; node; node= node->next)
2596                 if(node==testnode)
2597                         return 1;
2598         return 0;
2599 }
2600
2601 static int outsocket_exists(bNode *node, bNodeSocket *testsock)
2602 {
2603         bNodeSocket *sock= node->outputs.first;
2604         for(; sock; sock= sock->next)
2605                 if(sock==testsock)
2606                         return 1;
2607         return 0;
2608 }
2609
2610
2611 /* sync local composite with real tree */
2612 /* local composite is supposed to be running, be careful moving previews! */
2613 void ntreeLocalSync(bNodeTree *localtree, bNodeTree *ntree)
2614 {
2615         bNode *lnode;
2616         
2617         /* move over the compbufs and previews */
2618         for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2619                 if( (lnode->exec & NODE_READY) && !(lnode->exec & NODE_SKIPPED) ) {
2620                         if(node_exists(ntree, lnode->new_node)) {
2621                                 
2622                                 if(lnode->preview && lnode->preview->rect) {
2623                                         node_free_preview(lnode->new_node);
2624                                         lnode->new_node->preview= lnode->preview;
2625                                         lnode->preview= NULL;
2626                                 }
2627                         }
2628                 }
2629         }
2630 }
2631
2632 /* merge local tree results back, and free local tree */
2633 /* we have to assume the editor already changed completely */
2634 void ntreeLocalMerge(bNodeTree *localtree, bNodeTree *ntree)
2635 {
2636         bNode *lnode;
2637         bNodeSocket *lsock;
2638         
2639         /* move over the compbufs and previews */
2640         for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2641                 if(node_exists(ntree, lnode->new_node)) {
2642                         
2643                         if(lnode->preview && lnode->preview->rect) {
2644                                 node_free_preview(lnode->new_node);
2645                                 lnode->new_node->preview= lnode->preview;
2646                                 lnode->preview= NULL;
2647                         }
2648                         
2649                         if(ELEM(lnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2650                                 if(lnode->id && (lnode->flag & NODE_DO_OUTPUT)) {
2651                                         /* image_merge does sanity check for pointers */
2652                                         BKE_image_merge((Image *)lnode->new_node->id, (Image *)lnode->id);
2653                                 }
2654                         }
2655                         
2656                         for(lsock= lnode->outputs.first; lsock; lsock= lsock->next) {
2657                                 if(outsocket_exists(lnode->new_node, lsock->new_sock)) {
2658                                         lsock->new_sock->ns.data= lsock->ns.data;
2659                                         compbuf_set_node(lsock->new_sock->ns.data, lnode->new_node);
2660                                         lsock->ns.data= NULL;
2661                                         lsock->new_sock= NULL;
2662                                 }
2663                         }
2664                 }
2665         }
2666         ntreeFreeTree(localtree);
2667         MEM_freeN(localtree);
2668 }
2669
2670 /* *********************************************** */
2671
2672 /* GPU material from shader nodes */
2673
2674 static void gpu_from_node_stack(ListBase *sockets, bNodeStack **ns, GPUNodeStack *gs)
2675 {
2676         bNodeSocket *sock;
2677         int i;
2678
2679         for (sock=sockets->first, i=0; sock; sock=sock->next, i++) {
2680                 memset(&gs[i], 0, sizeof(gs[i]));
2681
2682                 QUATCOPY(gs[i].vec, ns[i]->vec);
2683                 gs[i].link= ns[i]->data;
2684
2685                 if (sock->type == SOCK_VALUE)
2686                         gs[i].type= GPU_FLOAT;
2687                 else if (sock->type == SOCK_VECTOR)
2688                         gs[i].type= GPU_VEC3;
2689                 else if (sock->type == SOCK_RGBA)
2690                         gs[i].type= GPU_VEC4;
2691                 else
2692                         gs[i].type= GPU_NONE;
2693
2694                 gs[i].name = "";
2695                 gs[i].hasinput= ns[i]->hasinput && ns[i]->data;
2696                 gs[i].hasoutput= ns[i]->hasinput && ns[i]->data;
2697                 gs[i].sockettype= ns[i]->sockettype;
2698         }
2699
2700         gs[i].type= GPU_NONE;
2701 }
2702
2703 static void data_from_gpu_stack(ListBase *sockets, bNodeStack **ns, GPUNodeStack *gs)
2704 {
2705         bNodeSocket *sock;
2706         int i;
2707
2708         for (sock=sockets->first, i=0; sock; sock=sock->next, i++) {
2709                 ns[i]->data= gs[i].link;
2710                 ns[i]->hasinput= gs[i].hasinput && gs[i].link;
2711                 ns[i]->hasoutput= gs[i].hasoutput;
2712                 ns[i]->sockettype= gs[i].sockettype;
2713         }
2714 }
2715
2716 static void gpu_node_group_execute(bNodeStack *stack, GPUMaterial *mat, bNode *gnode, bNodeStack **in, bNodeStack **out)
2717 {
2718         bNode *node;
2719         bNodeTree *ntree= (bNodeTree *)gnode->id;
2720         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2721         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2722         GPUNodeStack gpuin[MAX_SOCKET+1], gpuout[MAX_SOCKET+1];
2723         int doit = 0;
2724         
2725         if(ntree==NULL) return;
2726         
2727         stack+= gnode->stack_index;
2728                 
2729         for(node= ntree->nodes.first; node; node= node->next) {
2730                 if(node->typeinfo->gpufunc) {
2731                         group_node_get_stack(node, stack, nsin, nsout, in, out);
2732
2733                         doit = 0;
2734                         
2735                         /* for groups, only execute outputs for edited group */
2736                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
2737                                 if(gnode->flag & NODE_GROUP_EDIT)
2738                                         if(node->flag & NODE_DO_OUTPUT)
2739                                                 doit = 1;
2740                         }
2741                         else
2742                                 doit = 1;
2743
2744                         if(doit)  {
2745                                 gpu_from_node_stack(&node->inputs, nsin, gpuin);
2746                                 gpu_from_node_stack(&node->outputs, nsout, gpuout);
2747                                 if(node->typeinfo->gpufunc(mat, node, gpuin, gpuout))
2748                                         data_from_gpu_stack(&node->outputs, nsout, gpuout);
2749                         }
2750                 }
2751         }
2752 }
2753
2754 void ntreeGPUMaterialNodes(bNodeTree *ntree, GPUMaterial *mat)
2755 {
2756         bNode *node;
2757         bNodeStack *stack;
2758         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2759         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2760         GPUNodeStack gpuin[MAX_SOCKET+1], gpuout[MAX_SOCKET+1];
2761
2762         if((ntree->init & NTREE_EXEC_INIT)==0)
2763                 ntreeBeginExecTree(ntree);
2764
2765         stack= ntree->stack;
2766
2767         for(node= ntree->nodes.first; node; node= node->next) {
2768                 if(node->typeinfo->gpufunc) {
2769                         node_get_stack(node, stack, nsin, nsout);
2770                         gpu_from_node_stack(&node->inputs, nsin, gpuin);
2771                         gpu_from_node_stack(&node->outputs, nsout, gpuout);
2772                         if(node->typeinfo->gpufunc(mat, node, gpuin, gpuout))
2773                                 data_from_gpu_stack(&node->outputs, nsout, gpuout);
2774                 }
2775                 else if(node->type==NODE_GROUP && node->id) {
2776                         node_get_stack(node, stack, nsin, nsout);
2777                         gpu_node_group_execute(stack, mat, node, nsin, nsout);
2778                 }
2779         }
2780
2781         ntreeEndExecTree(ntree);
2782 }
2783
2784 /* **************** call to switch lamploop for material node ************ */
2785
2786 void (*node_shader_lamp_loop)(struct ShadeInput *, struct ShadeResult *);
2787
2788 void set_node_shader_lamp_loop(void (*lamp_loop_func)(ShadeInput *, ShadeResult *))
2789 {
2790         node_shader_lamp_loop= lamp_loop_func;
2791 }
2792
2793 /* clumsy checking... should do dynamic outputs once */
2794 static void force_hidden_passes(bNode *node, int passflag)
2795 {
2796         bNodeSocket *sock;
2797         
2798         for(sock= node->outputs.first; sock; sock= sock->next)
2799                 sock->flag &= ~SOCK_UNAVAIL;
2800         
2801         sock= BLI_findlink(&node->outputs, RRES_OUT_Z);
2802         if(!(passflag & SCE_PASS_Z)) sock->flag |= SOCK_UNAVAIL;
2803         sock= BLI_findlink(&node->outputs, RRES_OUT_NORMAL);
2804         if(!(passflag & SCE_PASS_NORMAL)) sock->flag |= SOCK_UNAVAIL;
2805         sock= BLI_findlink(&node->outputs, RRES_OUT_VEC);
2806         if(!(passflag & SCE_PASS_VECTOR)) sock->flag |= SOCK_UNAVAIL;
2807         sock= BLI_findlink(&node->outputs, RRES_OUT_UV);
2808         if(!(passflag & SCE_PASS_UV)) sock->flag |= SOCK_UNAVAIL;
2809         sock= BLI_findlink(&node->outputs, RRES_OUT_RGBA);
2810         if(!(passflag & SCE_PASS_RGBA)) sock->flag |= SOCK_UNAVAIL;
2811         sock= BLI_findlink(&node->outputs, RRES_OUT_DIFF);
2812         if(!(passflag & SCE_PASS_DIFFUSE)) sock->flag |= SOCK_UNAVAIL;
2813         sock= BLI_findlink(&node->outputs, RRES_OUT_SPEC);
2814         if(!(passflag & SCE_PASS_SPEC)) sock->flag |= SOCK_UNAVAIL;
2815         sock= BLI_findlink(&node->outputs, RRES_OUT_SHADOW);
2816         if(!(passflag & SCE_PASS_SHADOW)) sock->flag |= SOCK_UNAVAIL;
2817         sock= BLI_findlink(&node->outputs, RRES_OUT_AO);
2818         if(!(passflag & SCE_PASS_AO)) sock->flag |= SOCK_UNAVAIL;
2819         sock= BLI_findlink(&node->outputs, RRES_OUT_REFLECT);
2820         if(!(passflag & SCE_PASS_REFLECT)) sock->flag |= SOCK_UNAVAIL;
2821         sock= BLI_findlink(&node->outputs, RRES_OUT_REFRACT);
2822         if(!(passflag & SCE_PASS_REFRACT)) sock->flag |= SOCK_UNAVAIL;
2823         sock= BLI_findlink(&node->outputs, RRES_OUT_INDIRECT);
2824         if(!(passflag & SCE_PASS_INDIRECT)) sock->flag |= SOCK_UNAVAIL;
2825         sock= BLI_findlink(&node->outputs, RRES_OUT_INDEXOB);
2826         if(!(passflag & SCE_PASS_INDEXOB)) sock->flag |= SOCK_UNAVAIL;
2827         sock= BLI_findlink(&node->outputs, RRES_OUT_MIST);
2828         if(!(passflag & SCE_PASS_MIST)) sock->flag |= SOCK_UNAVAIL;
2829         sock= BLI_findlink(&node->outputs, RRES_OUT_EMIT);
2830         if(!(passflag & SCE_PASS_EMIT)) sock->flag |= SOCK_UNAVAIL;
2831         sock= BLI_findlink(&node->outputs, RRES_OUT_ENV);
2832         if(!(passflag & SCE_PASS_ENVIRONMENT)) sock->flag |= SOCK_UNAVAIL;
2833         
2834 }
2835
2836 /* based on rules, force sockets hidden always */
2837 void ntreeCompositForceHidden(bNodeTree *ntree, Scene *curscene)
2838 {
2839         bNode *node;
2840         
2841         if(ntree==NULL) return;
2842         
2843         for(node= ntree->nodes.first; node; node= node->next) {
2844                 if( node->type==CMP_NODE_R_LAYERS) {
2845                         Scene *sce= node->id?(Scene *)node->id:curscene;
2846                         SceneRenderLayer *srl= BLI_findlink(&sce->r.layers, node->custom1);
2847                         if(srl)
2848                                 force_hidden_passes(node, srl->passflag);
2849                 }
2850                 else if( node->type==CMP_NODE_IMAGE) {
2851                         Image *ima= (Image *)node->id;
2852                         if(ima) {
2853                                 if(ima->rr) {
2854                                         ImageUser *iuser= node->storage;
2855                                         RenderLayer *rl= BLI_findlink(&ima->rr->layers, iuser->layer);
2856                                         if(rl)
2857                                                 force_hidden_passes(node, rl->passflag);
2858                                         else
2859                                                 force_hidden_passes(node, 0);
2860                                 }
2861                                 else if(ima->type!=IMA_TYPE_MULTILAYER) {       /* if ->rr not yet read we keep inputs */
2862                                         force_hidden_passes(node, RRES_OUT_Z);
2863                                 }
2864                                 else
2865                                         force_hidden_passes(node, 0);
2866                         }
2867                         else
2868                                 force_hidden_passes(node, 0);
2869                 }
2870         }
2871
2872 }
2873
2874 /* called from render pipeline, to tag render input and output */
2875 /* need to do all scenes, to prevent errors when you re-render 1 scene */
2876 void ntreeCompositTagRender(Scene *curscene)
2877 {
2878         Scene *sce;
2879         
2880         for(sce= G.main->scene.first; sce; sce= sce->id.next) {
2881                 if(sce->nodetree) {
2882                         bNode *node;
2883                         
2884                         for(node= sce->nodetree->nodes.first; node; node= node->next) {
2885                                 if(node->id==(ID *)curscene || node->type==CMP_NODE_COMPOSITE)
2886                                         NodeTagChanged(sce->nodetree, node);
2887                         }
2888                 }
2889         }
2890 }
2891
2892 static int node_animation_properties(bNodeTree *ntree, bNode *node)
2893 {
2894         bNodeSocket *sock;
2895         const ListBase *lb;
2896         Link *link;
2897         PointerRNA ptr;
2898         PropertyRNA *prop;
2899         
2900         /* check to see if any of the node's properties have fcurves */
2901         RNA_pointer_create((ID *)ntree, &RNA_Node, node, &ptr);
2902         lb = RNA_struct_defined_properties(ptr.type);
2903         
2904         for (link=lb->first; link; link=link->next) {
2905                 int driven, len=1, index;
2906                 prop = (PropertyRNA *)link;
2907                 
2908                 if (RNA_property_array_check(&ptr, prop))
2909                         len = RNA_property_array_length(&ptr, prop);
2910                 
2911                 for (index=0; index<len; index++) {
2912                         if (rna_get_fcurve(&ptr, prop, index, NULL, &driven)) {
2913                                 NodeTagChanged(ntree, node);
2914                                 return 1;
2915                         }
2916                 }
2917         }
2918         
2919         /* now check node sockets */
2920         for (sock = node->inputs.first; sock; sock=sock->next) {
2921                 int driven, len=1, index;
2922                 
2923                 RNA_pointer_create((ID *)ntree, &RNA_NodeSocket, sock, &ptr);
2924                 prop = RNA_struct_find_property(&ptr, "default_value");
2925                 
2926                 if (RNA_property_array_check(&ptr, prop))
2927                         len = RNA_property_array_length(&ptr, prop);
2928                 
2929                 for (index=0; index<len; index++) {
2930                         if (rna_get_fcurve(&ptr, prop, index, NULL, &driven)) {
2931                                 NodeTagChanged(ntree, node);
2932                                 return 1;
2933                         }
2934                 }
2935         }
2936
2937         return 0;
2938 }
2939
2940 /* tags nodes that have animation capabilities */
2941 int ntreeCompositTagAnimated(bNodeTree *ntree)
2942 {
2943         bNode *node;
2944         int tagged= 0;
2945         
2946         if(ntree==NULL) return 0;
2947         
2948         for(node= ntree->nodes.first; node; node= node->next) {
2949                 
2950                 tagged = node_animation_properties(ntree, node);
2951                 
2952                 /* otherwise always tag these node types */
2953                 if(node->type==CMP_NODE_IMAGE) {
2954                         Image *ima= (Image *)node->id;
2955                         if(ima && ELEM(ima->source, IMA_SRC_MOVIE, IMA_SRC_SEQUENCE)) {
2956                                 NodeTagChanged(ntree, node);
2957                                 tagged= 1;
2958                         }
2959                 }
2960                 else if(node->type==CMP_NODE_TIME) {
2961                         NodeTagChanged(ntree, node);
2962                         tagged= 1;
2963                 }
2964                 else if(node->type==CMP_NODE_R_LAYERS) {
2965                         NodeTagChanged(ntree, node);
2966                         tagged= 1;
2967                 }
2968                 else if(node->type==NODE_GROUP) {
2969                         if( ntreeCompositTagAnimated((bNodeTree *)node->id) ) {
2970                                 NodeTagChanged(ntree, node);
2971                         }
2972                 }
2973         }
2974         
2975         return tagged;
2976 }
2977
2978
2979 /* called from image window preview */
2980 void ntreeCompositTagGenerators(bNodeTree *ntree)
2981 {
2982         bNode *node;
2983         
2984         if(ntree==NULL) return;
2985         
2986         for(node= ntree->nodes.first; node; node= node->next) {
2987                 if( ELEM(node->type, CMP_NODE_R_LAYERS, CMP_NODE_IMAGE))
2988                         NodeTagChanged(ntree, node);
2989         }
2990 }
2991
2992 int ntreeTexTagAnimated(bNodeTree *ntree)
2993 {
2994         bNode *node;
2995         
2996         if(ntree==NULL) return 0;
2997         
2998         for(node= ntree->nodes.first; node; node= node->next) {
2999                 if(node->type==TEX_NODE_CURVE_TIME) {
3000                         NodeTagChanged(ntree, node);
3001                         return 1;
3002                 }
3003                 else if(node->type==NODE_GROUP) {
3004                         if( ntreeTexTagAnimated((bNodeTree *)node->id) ) {
3005                                 return 1;
3006                         }
3007                 }
3008         }
3009         
3010         return 0;
3011 }
3012
3013 /* ************* node definition init ********** */
3014
3015 static bNodeType *is_nodetype_registered(ListBase *typelist, int type, ID *id) 
3016 {
3017         bNodeType *ntype= typelist->first;
3018         
3019         for(;ntype; ntype= ntype->next )
3020                 if(ntype->type==type && ntype->id==id)
3021                         return ntype;
3022         
3023         return NULL;
3024 }
3025
3026 /* type can be from a static array, we make copy for duplicate types (like group) */
3027 void nodeRegisterType(ListBase *typelist, const bNodeType *ntype) 
3028 {
3029         bNodeType *found= is_nodetype_registered(typelist, ntype->type, ntype->id);
3030         
3031         if(found==NULL) {
3032                 bNodeType *ntypen= MEM_callocN(sizeof(bNodeType), "node type");
3033                 *ntypen= *ntype;
3034                 BLI_addtail(typelist, ntypen);
3035          }
3036 }
3037
3038 static void registerCompositNodes(ListBase *ntypelist)
3039 {
3040         nodeRegisterType(ntypelist, &node_group_typeinfo);
3041         nodeRegisterType(ntypelist, &cmp_node_rlayers);
3042         nodeRegisterType(ntypelist, &cmp_node_image);
3043         nodeRegisterType(ntypelist, &cmp_node_texture);
3044         nodeRegisterType(ntypelist, &cmp_node_value);
3045         nodeRegisterType(ntypelist, &cmp_node_rgb);
3046         nodeRegisterType(ntypelist, &cmp_node_curve_time);
3047         
3048         nodeRegisterType(ntypelist, &cmp_node_composite);
3049         nodeRegisterType(ntypelist, &cmp_node_viewer);
3050         nodeRegisterType(ntypelist, &cmp_node_splitviewer);
3051         nodeRegisterType(ntypelist, &cmp_node_output_file);
3052         nodeRegisterType(ntypelist, &cmp_node_view_levels);
3053         
3054         nodeRegisterType(ntypelist, &cmp_node_curve_rgb);
3055         nodeRegisterType(ntypelist, &cmp_node_mix_rgb);
3056         nodeRegisterType(ntypelist, &cmp_node_hue_sat);
3057         nodeRegisterType(ntypelist, &cmp_node_brightcontrast);
3058         nodeRegisterType(ntypelist, &cmp_node_gamma);
3059         nodeRegisterType(ntypelist, &cmp_node_invert);
3060         nodeRegisterType(ntypelist, &cmp_node_alphaover);
3061         nodeRegisterType(ntypelist, &cmp_node_zcombine);
3062         nodeRegisterType(ntypelist, &cmp_node_colorbalance);
3063         nodeRegisterType(ntypelist, &cmp_node_huecorrect);
3064         
3065         nodeRegisterType(ntypelist, &cmp_node_normal);
3066         nodeRegisterType(ntypelist, &cmp_node_curve_vec);
3067         nodeRegisterType(ntypelist, &cmp_node_map_value);
3068         nodeRegisterType(ntypelist, &cmp_node_normalize);
3069         
3070         nodeRegisterType(ntypelist, &cmp_node_filter);
3071         nodeRegisterType(ntypelist, &cmp_node_blur);
3072         nodeRegisterType(ntypelist, &cmp_node_dblur);
3073         nodeRegisterType(ntypelist, &cmp_node_bilateralblur);
3074         nodeRegisterType(ntypelist, &cmp_node_vecblur);
3075         nodeRegisterType(ntypelist, &cmp_node_dilateerode);
3076         nodeRegisterType(ntypelist, &cmp_node_defocus);
3077         
3078         nodeRegisterType(ntypelist, &cmp_node_valtorgb);
3079         nodeRegisterType(ntypelist, &cmp_node_rgbtobw);
3080         nodeRegisterType(ntypelist, &cmp_node_setalpha);
3081         nodeRegisterType(ntypelist, &cmp_node_idmask);
3082         nodeRegisterType(ntypelist, &cmp_node_math);
3083         nodeRegisterType(ntypelist, &cmp_node_seprgba);
3084         nodeRegisterType(ntypelist, &cmp_node_combrgba);
3085         nodeRegisterType(ntypelist, &cmp_node_sephsva);
3086         nodeRegisterType(ntypelist, &cmp_node_combhsva);
3087         nodeRegisterType(ntypelist, &cmp_node_sepyuva);
3088         nodeRegisterType(ntypelist, &cmp_node_combyuva);
3089         nodeRegisterType(ntypelist, &cmp_node_sepycca);
3090         nodeRegisterType(ntypelist, &cmp_node_combycca);
3091         nodeRegisterType(ntypelist, &cmp_node_premulkey);
3092         
3093         nodeRegisterType(ntypelist, &cmp_node_diff_matte);
3094         nodeRegisterType(ntypelist, &cmp_node_distance_matte);
3095         nodeRegisterType(ntypelist, &cmp_node_chroma_matte);
3096         nodeRegisterType(ntypelist, &cmp_node_color_matte);
3097         nodeRegisterType(ntypelist, &cmp_node_channel_matte);
3098         nodeRegisterType(ntypelist, &cmp_node_color_spill);
3099         nodeRegisterType(ntypelist, &cmp_node_luma_matte);
3100         
3101         nodeRegisterType(ntypelist, &cmp_node_translate);
3102         nodeRegisterType(ntypelist, &cmp_node_rotate);
3103         nodeRegisterType(ntypelist, &cmp_node_scale);
3104    &n