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