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