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