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