2.5
[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         if(type==TEX_NODE_OUTPUT)
954                 ntreeTexAssignIndex(ntree, node);
955
956         nodeAddSockets(node, ntype);
957         
958         return node;
959 }
960
961 void nodeMakeDynamicType(bNode *node)
962 {
963         /* find SH_DYNAMIC_NODE ntype */
964         bNodeType *ntype= node_all_shaders.first;
965         while(ntype) {
966                 if(ntype->type==NODE_DYNAMIC && ntype->id==NULL)
967                         break;
968                 ntype= ntype->next;
969         }
970
971         /* make own type struct to fill */
972         if(ntype) {
973                 /*node->typeinfo= MEM_dupallocN(ntype);*/
974                 bNodeType *newtype= MEM_callocN(sizeof(bNodeType), "dynamic bNodeType");
975                 *newtype= *ntype;
976                 newtype->name= BLI_strdup(ntype->name);
977                 node->typeinfo= newtype;
978         }
979 }
980
981 void nodeUpdateType(bNodeTree *ntree, bNode* node, bNodeType *ntype)
982 {
983         verify_socket_list(ntree, &node->inputs, ntype->inputs);
984         verify_socket_list(ntree, &node->outputs, ntype->outputs);
985 }
986
987 /* keep socket listorder identical, for copying links */
988 /* ntree is the target tree */
989 bNode *nodeCopyNode(struct bNodeTree *ntree, struct bNode *node, int internal)
990 {
991         bNode *nnode= MEM_callocN(sizeof(bNode), "dupli node");
992         bNodeSocket *sock, *oldsock;
993
994         *nnode= *node;
995         BLI_addtail(&ntree->nodes, nnode);
996         
997         BLI_duplicatelist(&nnode->inputs, &node->inputs);
998         oldsock= node->inputs.first;
999         for(sock= nnode->inputs.first; sock; sock= sock->next, oldsock= oldsock->next) {
1000                 oldsock->new_sock= sock;
1001                 if(internal)
1002                         sock->own_index= 0;
1003         }
1004         
1005         BLI_duplicatelist(&nnode->outputs, &node->outputs);
1006         oldsock= node->outputs.first;
1007         for(sock= nnode->outputs.first; sock; sock= sock->next, oldsock= oldsock->next) {
1008                 if(internal)
1009                         sock->own_index= 0;
1010                 sock->stack_index= 0;
1011                 sock->ns.data= NULL;
1012                 oldsock->new_sock= sock;
1013         }
1014         
1015         if(nnode->id)
1016                 nnode->id->us++;
1017         
1018         if(node->typeinfo->copystoragefunc)
1019                 node->typeinfo->copystoragefunc(node, nnode);
1020         
1021         node->new_node= nnode;
1022         nnode->new_node= NULL;
1023         nnode->preview= NULL;
1024         
1025         if(node->type==TEX_NODE_OUTPUT)
1026                 ntreeTexAssignIndex(ntree, node);
1027
1028         return nnode;
1029 }
1030
1031 bNodeLink *nodeAddLink(bNodeTree *ntree, bNode *fromnode, bNodeSocket *fromsock, bNode *tonode, bNodeSocket *tosock)
1032 {
1033         bNodeLink *link= MEM_callocN(sizeof(bNodeLink), "link");
1034         
1035         BLI_addtail(&ntree->links, link);
1036         link->fromnode= fromnode;
1037         link->fromsock= fromsock;
1038         link->tonode= tonode;
1039         link->tosock= tosock;
1040         
1041         return link;
1042 }
1043
1044 void nodeRemLink(bNodeTree *ntree, bNodeLink *link)
1045 {
1046         BLI_remlink(&ntree->links, link);
1047         if(link->tosock)
1048                 link->tosock->link= NULL;
1049         MEM_freeN(link);
1050 }
1051
1052
1053 bNodeTree *ntreeAddTree(int type)
1054 {
1055         bNodeTree *ntree= MEM_callocN(sizeof(bNodeTree), "new node tree");
1056         ntree->type= type;
1057         ntree->alltypes.first = NULL;
1058         ntree->alltypes.last = NULL;
1059         
1060         ntreeInitTypes(ntree);
1061         return ntree;
1062 }
1063
1064 bNodeTree *ntreeCopyTree(bNodeTree *ntree, int internal_select)
1065 {
1066         bNodeTree *newtree;
1067         bNode *node, *nnode, *last;
1068         bNodeLink *link, *nlink;
1069         bNodeSocket *sock;
1070         int a;
1071         
1072         if(ntree==NULL) return NULL;
1073         
1074         if(internal_select==0) {
1075                 /* is ntree part of library? */
1076                 for(newtree=G.main->nodetree.first; newtree; newtree= newtree->id.next)
1077                         if(newtree==ntree) break;
1078                 if(newtree)
1079                         newtree= copy_libblock(ntree);
1080                 else
1081                         newtree= MEM_dupallocN(ntree);
1082                 newtree->nodes.first= newtree->nodes.last= NULL;
1083                 newtree->links.first= newtree->links.last= NULL;
1084         }
1085         else
1086                 newtree= ntree;
1087         
1088         last= ntree->nodes.last;
1089         for(node= ntree->nodes.first; node; node= node->next) {
1090                 
1091                 node->new_node= NULL;
1092                 if(internal_select==0 || (node->flag & NODE_SELECT)) {
1093                         nnode= nodeCopyNode(newtree, node, internal_select);    /* sets node->new */
1094                         if(internal_select) {
1095                                 node->flag &= ~NODE_SELECT;
1096                                 nnode->flag |= NODE_SELECT;
1097                         }
1098                         node->flag &= ~NODE_ACTIVE;
1099
1100                         /* deselect original sockets */
1101                         for(sock= node->inputs.first; sock; sock= sock->next) {
1102                                 if(sock->flag & SOCK_SEL) sock->flag&= ~SOCK_SEL;
1103                         }
1104                         for(sock= node->outputs.first; sock; sock= sock->next) {
1105                                 if(sock->flag & SOCK_SEL) sock->flag&= ~SOCK_SEL;
1106                         }
1107                         
1108                         /* set tree selin and selout to new sockets */
1109                         for(sock= nnode->inputs.first; sock; sock= sock->next) {
1110                                 if(sock->flag & SOCK_SEL) {
1111                                         ntree->selin= sock;
1112                                         break;
1113                                 }
1114                         }
1115                         for(sock= nnode->outputs.first; sock; sock= sock->next) {
1116                                 if(sock->flag & SOCK_SEL) {
1117                                         ntree->selout= sock;
1118                                         break;
1119                                 }
1120                         }
1121                 }
1122                 if(node==last) break;
1123         }
1124         
1125         /* check for copying links */
1126         for(link= ntree->links.first; link; link= link->next) {
1127                 if(link->fromnode==NULL || link->tonode==NULL);
1128                 else if(link->fromnode->new_node && link->tonode->new_node) {
1129                         nlink= nodeAddLink(newtree, link->fromnode->new_node, NULL, link->tonode->new_node, NULL);
1130                         /* sockets were copied in order */
1131                         for(a=0, sock= link->fromnode->outputs.first; sock; sock= sock->next, a++) {
1132                                 if(sock==link->fromsock)
1133                                         break;
1134                         }
1135                         nlink->fromsock= BLI_findlink(&link->fromnode->new_node->outputs, a);
1136                         
1137                         for(a=0, sock= link->tonode->inputs.first; sock; sock= sock->next, a++) {
1138                                 if(sock==link->tosock)
1139                                         break;
1140                         }
1141                         nlink->tosock= BLI_findlink(&link->tonode->new_node->inputs, a);
1142                 }
1143         }
1144         
1145         /* own type definition for group usage */
1146         if(internal_select==0) {
1147                 if(ntree->owntype) {
1148                         newtree->owntype= MEM_dupallocN(ntree->owntype);
1149                         if(ntree->owntype->inputs)
1150                                 newtree->owntype->inputs= MEM_dupallocN(ntree->owntype->inputs);
1151                         if(ntree->owntype->outputs)
1152                                 newtree->owntype->outputs= MEM_dupallocN(ntree->owntype->outputs);
1153                 }
1154         }
1155         /* weird this is required... there seem to be link pointers wrong still? */
1156         /* anyhoo, doing this solves crashes on copying entire tree (copy scene) and delete nodes */
1157         ntreeSolveOrder(newtree);
1158
1159         return newtree;
1160 }
1161
1162 /* *************** preview *********** */
1163 /* if node->preview, then we assume the rect to exist */
1164
1165 static void node_free_preview(bNode *node)
1166 {
1167         if(node->preview) {
1168                 if(node->preview->rect)
1169                         MEM_freeN(node->preview->rect);
1170                 MEM_freeN(node->preview);
1171                 node->preview= NULL;
1172         }       
1173 }
1174
1175 static void node_init_preview(bNode *node, int xsize, int ysize)
1176 {
1177         
1178         if(node->preview==NULL) {
1179                 node->preview= MEM_callocN(sizeof(bNodePreview), "node preview");
1180                 //              printf("added preview %s\n", node->name);
1181         }
1182         
1183         /* node previews can get added with variable size this way */
1184         if(xsize==0 || ysize==0)
1185                 return;
1186         
1187         /* sanity checks & initialize */
1188         if(node->preview->rect) {
1189                 if(node->preview->xsize!=xsize && node->preview->ysize!=ysize) {
1190                         MEM_freeN(node->preview->rect);
1191                         node->preview->rect= NULL;
1192                 }
1193         }
1194         
1195         if(node->preview->rect==NULL) {
1196                 node->preview->rect= MEM_callocN(4*xsize + xsize*ysize*sizeof(float)*4, "node preview rect");
1197                 node->preview->xsize= xsize;
1198                 node->preview->ysize= ysize;
1199         }
1200 }
1201
1202 void ntreeInitPreview(bNodeTree *ntree, int xsize, int ysize)
1203 {
1204         bNode *node;
1205         
1206         if(ntree==NULL)
1207                 return;
1208         
1209         for(node= ntree->nodes.first; node; node= node->next) {
1210                 if(node->typeinfo->flag & NODE_PREVIEW) /* hrms, check for closed nodes? */
1211                         node_init_preview(node, xsize, ysize);
1212                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1213                         ntreeInitPreview((bNodeTree *)node->id, xsize, ysize);
1214         }               
1215 }
1216
1217 static void nodeClearPreview(bNode *node)
1218 {
1219         if(node->preview && node->preview->rect)
1220                 memset(node->preview->rect, 0, MEM_allocN_len(node->preview->rect));
1221 }
1222
1223 /* use it to enforce clear */
1224 void ntreeClearPreview(bNodeTree *ntree)
1225 {
1226         bNode *node;
1227         
1228         if(ntree==NULL)
1229                 return;
1230         
1231         for(node= ntree->nodes.first; node; node= node->next) {
1232                 if(node->typeinfo->flag & NODE_PREVIEW)
1233                         nodeClearPreview(node);
1234                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1235                         ntreeClearPreview((bNodeTree *)node->id);
1236         }               
1237 }
1238
1239 /* hack warning! this function is only used for shader previews, and 
1240 since it gets called multiple times per pixel for Ztransp we only
1241 add the color once. Preview gets cleared before it starts render though */
1242 void nodeAddToPreview(bNode *node, float *col, int x, int y)
1243 {
1244         bNodePreview *preview= node->preview;
1245         if(preview) {
1246                 if(x>=0 && y>=0) {
1247                         if(x<preview->xsize && y<preview->ysize) {
1248                                 float *tar= preview->rect+ 4*((preview->xsize*y) + x);
1249                                 //if(tar[0]==0.0f) {
1250                                 QUATCOPY(tar, col);
1251                                 //}
1252                         }
1253                         //else printf("prv out bound x y %d %d\n", x, y);
1254                 }
1255                 //else printf("prv out bound x y %d %d\n", x, y);
1256         }
1257 }
1258
1259
1260 /* ************** Free stuff ********** */
1261
1262 /* goes over entire tree */
1263 void nodeUnlinkNode(bNodeTree *ntree, bNode *node)
1264 {
1265         bNodeLink *link, *next;
1266         bNodeSocket *sock;
1267         ListBase *lb;
1268         
1269         for(link= ntree->links.first; link; link= next) {
1270                 next= link->next;
1271                 
1272                 if(link->fromnode==node) {
1273                         lb= &node->outputs;
1274                         NodeTagChanged(ntree, link->tonode);
1275                 }
1276                 else if(link->tonode==node)
1277                         lb= &node->inputs;
1278                 else
1279                         lb= NULL;
1280
1281                 if(lb) {
1282                         for(sock= lb->first; sock; sock= sock->next) {
1283                                 if(link->fromsock==sock || link->tosock==sock)
1284                                         break;
1285                         }
1286                         if(sock) {
1287                                 nodeRemLink(ntree, link);
1288                         }
1289                 }
1290         }
1291 }
1292
1293 static void composit_free_node_cache(bNode *node)
1294 {
1295         bNodeSocket *sock;
1296         
1297         for(sock= node->outputs.first; sock; sock= sock->next) {
1298                 if(sock->ns.data) {
1299                         free_compbuf(sock->ns.data);
1300                         sock->ns.data= NULL;
1301                 }
1302         }
1303 }
1304
1305 void nodeFreeNode(bNodeTree *ntree, bNode *node)
1306 {
1307         nodeUnlinkNode(ntree, node);
1308         BLI_remlink(&ntree->nodes, node);
1309
1310         /* since it is called while free database, node->id is undefined */
1311         
1312         if(ntree->type==NTREE_COMPOSIT)
1313                 composit_free_node_cache(node);
1314         BLI_freelistN(&node->inputs);
1315         BLI_freelistN(&node->outputs);
1316         
1317         node_free_preview(node);
1318
1319         if(node->typeinfo && node->typeinfo->freestoragefunc) {
1320                 node->typeinfo->freestoragefunc(node);
1321         }
1322
1323         MEM_freeN(node);
1324 }
1325
1326 /* do not free ntree itself here, free_libblock calls this function too */
1327 void ntreeFreeTree(bNodeTree *ntree)
1328 {
1329         bNode *node, *next;
1330         
1331         if(ntree==NULL) return;
1332         
1333         ntreeEndExecTree(ntree);        /* checks for if it is still initialized */
1334         
1335         BLI_freelistN(&ntree->links);   /* do first, then unlink_node goes fast */
1336         
1337         for(node= ntree->nodes.first; node; node= next) {
1338                 next= node->next;
1339                 nodeFreeNode(ntree, node);
1340         }
1341         
1342         if(ntree->owntype) {
1343                 if(ntree->owntype->inputs)
1344                         MEM_freeN(ntree->owntype->inputs);
1345                 if(ntree->owntype->outputs)
1346                         MEM_freeN(ntree->owntype->outputs);
1347                 MEM_freeN(ntree->owntype);
1348         }
1349 }
1350
1351 void ntreeFreeCache(bNodeTree *ntree)
1352 {
1353         bNode *node;
1354         
1355         if(ntree==NULL) return;
1356
1357         if(ntree->type==NTREE_COMPOSIT)
1358                 for(node= ntree->nodes.first; node; node= node->next)
1359                         composit_free_node_cache(node);
1360
1361 }
1362
1363 void ntreeMakeLocal(bNodeTree *ntree)
1364 {
1365         int local=0, lib=0;
1366         
1367         /* - only lib users: do nothing
1368             * - only local users: set flag
1369             * - mixed: make copy
1370             */
1371         
1372         if(ntree->id.lib==NULL) return;
1373         if(ntree->id.us==1) {
1374                 ntree->id.lib= 0;
1375                 ntree->id.flag= LIB_LOCAL;
1376                 new_id(0, (ID *)ntree, 0);
1377                 return;
1378         }
1379         
1380         /* now check users of groups... again typedepending, callback... */
1381         if(ntree->type==NTREE_SHADER) {
1382                 Material *ma;
1383                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1384                         if(ma->nodetree) {
1385                                 bNode *node;
1386                                 
1387                                 /* find if group is in tree */
1388                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
1389                                         if(node->id == (ID *)ntree) {
1390                                                 if(ma->id.lib) lib= 1;
1391                                                 else local= 1;
1392                                         }
1393                                 }
1394                         }
1395                 }
1396         }
1397         else if(ntree->type==NTREE_COMPOSIT) {
1398                 Scene *sce;
1399                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
1400                         if(sce->nodetree) {
1401                                 bNode *node;
1402                                 
1403                                 /* find if group is in tree */
1404                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
1405                                         if(node->id == (ID *)ntree) {
1406                                                 if(sce->id.lib) lib= 1;
1407                                                 else local= 1;
1408                                         }
1409                                 }
1410                         }
1411                 }
1412         }
1413         else if(ntree->type==NTREE_TEXTURE) {
1414                 Tex *tx;
1415                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
1416                         if(tx->nodetree) {
1417                                 bNode *node;
1418                                 
1419                                 /* find if group is in tree */
1420                                 for(node= tx->nodetree->nodes.first; node; node= node->next) {
1421                                         if(node->id == (ID *)ntree) {
1422                                                 if(tx->id.lib) lib= 1;
1423                                                 else local= 1;
1424                                         }
1425                                 }
1426                         }
1427                 }
1428         }
1429         
1430         /* if all users are local, we simply make tree local */
1431         if(local && lib==0) {
1432                 ntree->id.lib= NULL;
1433                 ntree->id.flag= LIB_LOCAL;
1434                 new_id(0, (ID *)ntree, 0);
1435         }
1436         else if(local && lib) {
1437                 /* this is the mixed case, we copy the tree and assign it to local users */
1438                 bNodeTree *newtree= ntreeCopyTree(ntree, 0);
1439                 
1440                 newtree->id.us= 0;
1441                 
1442                 if(ntree->type==NTREE_SHADER) {
1443                         Material *ma;
1444                         for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1445                                 if(ma->nodetree) {
1446                                         bNode *node;
1447                                         
1448                                         /* find if group is in tree */
1449                                         for(node= ma->nodetree->nodes.first; node; node= node->next) {
1450                                                 if(node->id == (ID *)ntree) {
1451                                                         if(ma->id.lib==NULL) {
1452                                                                 node->id= &newtree->id;
1453                                                                 newtree->id.us++;
1454                                                                 ntree->id.us--;
1455                                                         }
1456                                                 }
1457                                         }
1458                                 }
1459                         }
1460                 }
1461                 else if(ntree->type==NTREE_COMPOSIT) {
1462                         Scene *sce;
1463                         for(sce= G.main->scene.first; sce; sce= sce->id.next) {
1464                                 if(sce->nodetree) {
1465                                         bNode *node;
1466                                         
1467                                         /* find if group is in tree */
1468                                         for(node= sce->nodetree->nodes.first; node; node= node->next) {
1469                                                 if(node->id == (ID *)ntree) {
1470                                                         if(sce->id.lib==NULL) {
1471                                                                 node->id= &newtree->id;
1472                                                                 newtree->id.us++;
1473                                                                 ntree->id.us--;
1474                                                         }
1475                                                 }
1476                                         }
1477                                 }
1478                         }
1479                 }
1480                 else if(ntree->type==NTREE_TEXTURE) {
1481                         Tex *tx;
1482                         for(tx= G.main->tex.first; tx; tx= tx->id.next) {
1483                                 if(tx->nodetree) {
1484                                         bNode *node;
1485                                         
1486                                         /* find if group is in tree */
1487                                         for(node= tx->nodetree->nodes.first; node; node= node->next) {
1488                                                 if(node->id == (ID *)ntree) {
1489                                                         if(tx->id.lib==NULL) {
1490                                                                 node->id= &newtree->id;
1491                                                                 newtree->id.us++;
1492                                                                 ntree->id.us--;
1493                                                         }
1494                                                 }
1495                                         }
1496                                 }
1497                         }
1498                 }
1499         }
1500 }
1501
1502
1503 /* ************ find stuff *************** */
1504
1505 static int ntreeHasType(bNodeTree *ntree, int type)
1506 {
1507         bNode *node;
1508         
1509         if(ntree)
1510                 for(node= ntree->nodes.first; node; node= node->next)
1511                         if(node->type == type)
1512                                 return 1;
1513         return 0;
1514 }
1515
1516 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
1517 {
1518         bNodeLink *link;
1519         
1520         for(link= ntree->links.first; link; link= link->next) {
1521                 if(link->fromsock==from && link->tosock==to)
1522                         return link;
1523                 if(link->fromsock==to && link->tosock==from)    /* hrms? */
1524                         return link;
1525         }
1526         return NULL;
1527 }
1528
1529 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1530 {
1531         bNodeLink *link;
1532         int tot= 0;
1533         
1534         for(link= ntree->links.first; link; link= link->next) {
1535                 if(link->fromsock==sock || link->tosock==sock)
1536                         tot++;
1537         }
1538         return tot;
1539 }
1540
1541 bNode *nodeGetActive(bNodeTree *ntree)
1542 {
1543         bNode *node;
1544         
1545         if(ntree==NULL) return NULL;
1546         
1547         for(node= ntree->nodes.first; node; node= node->next)
1548                 if(node->flag & NODE_ACTIVE)
1549                         break;
1550         return node;
1551 }
1552
1553 /* two active flags, ID nodes have special flag for buttons display */
1554 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
1555 {
1556         bNode *node;
1557         
1558         if(ntree==NULL) return NULL;
1559
1560         /* check for group edit */
1561     for(node= ntree->nodes.first; node; node= node->next)
1562                 if(node->flag & NODE_GROUP_EDIT)
1563                         break;
1564
1565         if(node)
1566                 ntree= (bNodeTree*)node->id;
1567         
1568         /* now find active node with this id */
1569         for(node= ntree->nodes.first; node; node= node->next)
1570                 if(node->id && GS(node->id->name)==idtype)
1571                         if(node->flag & NODE_ACTIVE_ID)
1572                                 break;
1573
1574         return node;
1575 }
1576
1577 /* two active flags, ID nodes have special flag for buttons display */
1578 void nodeClearActiveID(bNodeTree *ntree, short idtype)
1579 {
1580         bNode *node;
1581         
1582         if(ntree==NULL) return;
1583         
1584         for(node= ntree->nodes.first; node; node= node->next)
1585                 if(node->id && GS(node->id->name)==idtype)
1586                         node->flag &= ~NODE_ACTIVE_ID;
1587 }
1588
1589 /* two active flags, ID nodes have special flag for buttons display */
1590 void nodeSetActive(bNodeTree *ntree, bNode *node)
1591 {
1592         bNode *tnode;
1593         
1594         /* make sure only one node is active, and only one per ID type */
1595         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1596                 tnode->flag &= ~NODE_ACTIVE;
1597                 
1598                 if(node->id && tnode->id) {
1599                         if(GS(node->id->name) == GS(tnode->id->name))
1600                                 tnode->flag &= ~NODE_ACTIVE_ID;
1601                 }
1602         }
1603         
1604         node->flag |= NODE_ACTIVE;
1605         if(node->id)
1606                 node->flag |= NODE_ACTIVE_ID;
1607 }
1608
1609 /* use flags are not persistant yet, groups might need different tagging, so we do it each time
1610    when we need to get this info */
1611 void ntreeSocketUseFlags(bNodeTree *ntree)
1612 {
1613         bNode *node;
1614         bNodeSocket *sock;
1615         bNodeLink *link;
1616         
1617         /* clear flags */
1618         for(node= ntree->nodes.first; node; node= node->next) {
1619                 for(sock= node->inputs.first; sock; sock= sock->next)
1620                         sock->flag &= ~SOCK_IN_USE;
1621                 for(sock= node->outputs.first; sock; sock= sock->next)
1622                         sock->flag &= ~SOCK_IN_USE;
1623         }
1624         
1625         /* tag all thats in use */
1626         for(link= ntree->links.first; link; link= link->next) {
1627                 link->fromsock->flag |= SOCK_IN_USE;
1628                 link->tosock->flag |= SOCK_IN_USE;
1629         }
1630 }
1631
1632 /* ************** dependency stuff *********** */
1633
1634 /* node is guaranteed to be not checked before */
1635 static int node_recurs_check(bNode *node, bNode ***nsort, int level)
1636 {
1637         bNode *fromnode;
1638         bNodeSocket *sock;
1639         int has_inputlinks= 0;
1640         
1641         node->done= 1;
1642         level++;
1643         
1644         for(sock= node->inputs.first; sock; sock= sock->next) {
1645                 if(sock->link) {
1646                         has_inputlinks= 1;
1647                         fromnode= sock->link->fromnode;
1648                         if(fromnode->done==0) {
1649                                 fromnode->level= node_recurs_check(fromnode, nsort, level);
1650                         }
1651                 }
1652         }
1653 //      printf("node sort %s level %d\n", node->name, level);
1654         **nsort= node;
1655         (*nsort)++;
1656         
1657         if(has_inputlinks)
1658                 return level;
1659         else 
1660                 return 0xFFF;
1661 }
1662
1663 void ntreeSolveOrder(bNodeTree *ntree)
1664 {
1665         bNode *node, **nodesort, **nsort;
1666         bNodeSocket *sock;
1667         bNodeLink *link;
1668         int a, totnode=0;
1669         
1670         /* the solve-order is called on each tree change, so we should be sure no exec can be running */
1671         ntreeEndExecTree(ntree);
1672
1673         /* set links pointers the input sockets, to find dependencies */
1674         /* first clear data */
1675         for(node= ntree->nodes.first; node; node= node->next) {
1676                 node->done= 0;
1677                 totnode++;
1678                 for(sock= node->inputs.first; sock; sock= sock->next)
1679                         sock->link= NULL;
1680         }
1681         if(totnode==0)
1682                 return;
1683         
1684         for(link= ntree->links.first; link; link= link->next) {
1685                 link->tosock->link= link;
1686         }
1687         
1688         nsort= nodesort= MEM_callocN(totnode*sizeof(void *), "sorted node array");
1689         
1690         /* recursive check */
1691         for(node= ntree->nodes.first; node; node= node->next) {
1692                 if(node->done==0) {
1693                         node->level= node_recurs_check(node, &nsort, 0);
1694                 }
1695         }
1696         
1697         /* re-insert nodes in order, first a paranoia check */
1698         for(a=0; a<totnode; a++) {
1699                 if(nodesort[a]==NULL)
1700                         break;
1701         }
1702         if(a<totnode)
1703                 printf("sort error in node tree");
1704         else {
1705                 ntree->nodes.first= ntree->nodes.last= NULL;
1706                 for(a=0; a<totnode; a++)
1707                         BLI_addtail(&ntree->nodes, nodesort[a]);
1708         }
1709         
1710         MEM_freeN(nodesort);
1711         
1712         /* find the active outputs, might become tree type dependant handler */
1713         for(node= ntree->nodes.first; node; node= node->next) {
1714                 if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1715                         bNode *tnode;
1716                         int output= 0;
1717                         
1718                         /* we need a check for which output node should be tagged like this, below an exception */
1719                         if(node->type==CMP_NODE_OUTPUT_FILE)
1720                            continue;
1721                            
1722                         /* there is more types having output class, each one is checked */
1723                         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1724                                 if(tnode->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1725                                         if(tnode->type==node->type) {
1726                                                 if(tnode->flag & NODE_DO_OUTPUT) {
1727                                                         output++;
1728                                                         if(output>1)
1729                                                                 tnode->flag &= ~NODE_DO_OUTPUT;
1730                                                 }
1731                                         }
1732                                 }
1733                         }
1734                         if(output==0)
1735                                 node->flag |= NODE_DO_OUTPUT;
1736                 }
1737         }
1738         
1739         /* here we could recursively set which nodes have to be done,
1740                 might be different for editor or for "real" use... */
1741 }
1742
1743 /* should be callback! */
1744 void NodeTagChanged(bNodeTree *ntree, bNode *node)
1745 {
1746         if(ntree->type==NTREE_COMPOSIT) {
1747                 bNodeSocket *sock;
1748
1749                 for(sock= node->outputs.first; sock; sock= sock->next) {
1750                         if(sock->ns.data) {
1751                                 //free_compbuf(sock->ns.data);
1752                                 //sock->ns.data= NULL;
1753                         }
1754                 }
1755                 node->need_exec= 1;
1756         }
1757         else if(ntree->type == NTREE_TEXTURE)
1758                 ntreeTexUpdatePreviews(ntree);
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 /* stack indices make sure all nodes only write in allocated data, for making it thread safe */
1988 /* only root tree gets the stack, to enable instances to have own stack entries */
1989 /* only two threads now! */
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         
2011         nts= MEM_callocN(sizeof(bNodeThreadStack), "bNodeThreadStack");
2012         nts->stack= MEM_dupallocN(ntree->stack);
2013         nts->used= 1;
2014         BLI_addtail(lb, nts);
2015
2016         return nts;
2017 }
2018
2019 static void ntreeReleaseThreadStack(bNodeThreadStack *nts)
2020 {
2021         nts->used= 0;
2022 }
2023
2024 /* free texture delegates */
2025 static void tex_end_exec(bNodeTree *ntree)
2026 {
2027         bNodeThreadStack *nts;
2028         bNodeStack *ns;
2029         int th, a;
2030         
2031         if(ntree->threadstack)
2032                 for(th=0; th<BLENDER_MAX_THREADS; th++)
2033                         for(nts=ntree->threadstack[th].first; nts; nts=nts->next)
2034                                 for(ns= nts->stack, a=0; a<ntree->stacksize; a++, ns++)
2035                                         if(ns->data)
2036                                                 MEM_freeN(ns->data);
2037                                                 
2038 }
2039
2040 void ntreeBeginExecTree(bNodeTree *ntree)
2041 {
2042         /* let's make it sure */
2043         if(ntree->init & NTREE_EXEC_INIT)
2044                 return;
2045         
2046         /* allocate the thread stack listbase array */
2047         if(ntree->type!=NTREE_COMPOSIT)
2048                 ntree->threadstack= MEM_callocN(BLENDER_MAX_THREADS*sizeof(ListBase), "thread stack array");
2049
2050         /* goes recursive over all groups */
2051         ntree->stacksize= ntree_begin_exec_tree(ntree);
2052
2053         if(ntree->stacksize) {
2054                 bNode *node;
2055                 bNodeStack *ns;
2056                 int a;
2057                 
2058                 /* allocate the base stack */
2059                 ns=ntree->stack= MEM_callocN(ntree->stacksize*sizeof(bNodeStack), "node stack");
2060                 
2061                 /* tag inputs, the get_stack() gives own socket stackdata if not in use */
2062                 for(a=0; a<ntree->stacksize; a++, ns++) ns->hasinput= 1;
2063                 
2064                 /* tag used outputs, so we know when we can skip operations */
2065                 for(node= ntree->nodes.first; node; node= node->next) {
2066                         bNodeSocket *sock;
2067                         for(sock= node->inputs.first; sock; sock= sock->next) {
2068                                 if(sock->link) {
2069                                         ns= ntree->stack + sock->link->fromsock->stack_index;
2070                                         ns->hasoutput= 1;
2071                                         ns->sockettype= sock->link->fromsock->type;
2072                                 }
2073                                 else
2074                                         sock->ns.sockettype= sock->type;
2075                         }
2076                         if(node->type==NODE_GROUP && node->id)
2077                                 group_tag_used_outputs(node, ntree->stack);
2078                 }
2079                 
2080                 if(ntree->type==NTREE_COMPOSIT)
2081                         composit_begin_exec(ntree, 0);
2082         }
2083         
2084         ntree->init |= NTREE_EXEC_INIT;
2085 }
2086
2087 void ntreeEndExecTree(bNodeTree *ntree)
2088 {
2089         
2090         if(ntree->init & NTREE_EXEC_INIT) {
2091                 bNodeThreadStack *nts;
2092                 int a;
2093                 
2094                 /* another callback candidate! */
2095                 if(ntree->type==NTREE_COMPOSIT)
2096                         composit_end_exec(ntree, 0);
2097                 else if(ntree->type==NTREE_TEXTURE)
2098                         tex_end_exec(ntree);
2099                 
2100                 if(ntree->stack) {
2101                         MEM_freeN(ntree->stack);
2102                         ntree->stack= NULL;
2103                 }
2104
2105                 if(ntree->threadstack) {
2106                         for(a=0; a<BLENDER_MAX_THREADS; a++) {
2107                                 for(nts=ntree->threadstack[a].first; nts; nts=nts->next)
2108                                         if (nts->stack) MEM_freeN(nts->stack);
2109                                 BLI_freelistN(&ntree->threadstack[a]);
2110                         }
2111
2112                         MEM_freeN(ntree->threadstack);
2113                         ntree->threadstack= NULL;
2114                 }
2115
2116                 ntree->init &= ~NTREE_EXEC_INIT;
2117         }
2118 }
2119
2120 static void node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out)
2121 {
2122         bNodeSocket *sock;
2123         
2124         /* build pointer stack */
2125         for(sock= node->inputs.first; sock; sock= sock->next) {
2126                 if(sock->link)
2127                         *(in++)= stack + sock->link->fromsock->stack_index;
2128                 else
2129                         *(in++)= &sock->ns;
2130         }
2131         
2132         for(sock= node->outputs.first; sock; sock= sock->next) {
2133                 *(out++)= stack + sock->stack_index;
2134         }
2135 }
2136
2137 /* nodes are presorted, so exec is in order of list */
2138 void ntreeExecTree(bNodeTree *ntree, void *callerdata, int thread)
2139 {
2140         bNode *node;
2141         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2142         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2143         bNodeStack *stack;
2144         bNodeThreadStack *nts = NULL;
2145         
2146         /* only when initialized */
2147         if((ntree->init & NTREE_EXEC_INIT)==0)
2148                 ntreeBeginExecTree(ntree);
2149                 
2150         /* composite does 1 node per thread, so no multiple stacks needed */
2151         if(ntree->type==NTREE_COMPOSIT) {
2152                 stack= ntree->stack;
2153         }
2154         else {
2155                 nts= ntreeGetThreadStack(ntree, thread);
2156                 stack= nts->stack;
2157         }
2158         
2159         for(node= ntree->nodes.first; node; node= node->next) {
2160                 if(node->typeinfo->execfunc) {
2161                         node_get_stack(node, stack, nsin, nsout);
2162                         node->typeinfo->execfunc(callerdata, node, nsin, nsout);
2163                 }
2164                 else if(node->type==NODE_GROUP && node->id) {
2165                         node_get_stack(node, stack, nsin, nsout);
2166                         node_group_execute(stack, callerdata, node, nsin, nsout); 
2167                 }
2168         }
2169
2170         if(nts)
2171                 ntreeReleaseThreadStack(nts);
2172 }
2173
2174
2175 /* ***************************** threaded version for execute composite nodes ************* */
2176 /* these are nodes without input, only giving values */
2177 /* or nodes with only value inputs */
2178 static int node_only_value(bNode *node)
2179 {
2180         bNodeSocket *sock;
2181         
2182         if(ELEM3(node->type, CMP_NODE_TIME, CMP_NODE_VALUE, CMP_NODE_RGB))
2183                 return 1;
2184         
2185         /* doing this for all node types goes wrong. memory free errors */
2186         if(node->inputs.first && node->type==CMP_NODE_MAP_VALUE) {
2187                 int retval= 1;
2188                 for(sock= node->inputs.first; sock; sock= sock->next) {
2189                         if(sock->link)
2190                                 retval &= node_only_value(sock->link->fromnode);
2191                 }
2192                 return retval;
2193         }
2194         return 0;
2195 }
2196
2197
2198 /* not changing info, for thread callback */
2199 typedef struct ThreadData {
2200         bNodeStack *stack;
2201         RenderData *rd;
2202 } ThreadData;
2203
2204 static void *exec_composite_node(void *node_v)
2205 {
2206         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2207         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2208         bNode *node= node_v;
2209         ThreadData *thd= (ThreadData *)node->threaddata;
2210         
2211         node_get_stack(node, thd->stack, nsin, nsout);
2212         
2213         if((node->flag & NODE_MUTED) && (!node_only_value(node))) {
2214                 /* viewers we execute, for feedback to user */
2215                 if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) 
2216                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2217                 else
2218                         node_compo_pass_on(node, nsin, nsout);
2219         }
2220         else if(node->typeinfo->execfunc) {
2221                 node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2222         }
2223         else if(node->type==NODE_GROUP && node->id) {
2224                 node_group_execute(thd->stack, thd->rd, node, nsin, nsout); 
2225         }
2226         
2227         node->exec |= NODE_READY;
2228         return 0;
2229 }
2230
2231 /* return total of executable nodes, for timecursor */
2232 /* only compositor uses it */
2233 static int setExecutableNodes(bNodeTree *ntree, ThreadData *thd)
2234 {
2235         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2236         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2237         bNode *node;
2238         bNodeSocket *sock;
2239         int totnode= 0, group_edit= 0;
2240         
2241         /* note; do not add a dependency sort here, the stack was created already */
2242         
2243         /* if we are in group edit, viewer nodes get skipped when group has viewer */
2244         for(node= ntree->nodes.first; node; node= node->next)
2245                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
2246                         if(ntreeHasType((bNodeTree *)node->id, CMP_NODE_VIEWER))
2247                                 group_edit= 1;
2248         
2249         for(node= ntree->nodes.first; node; node= node->next) {
2250                 int a;
2251                 
2252                 node_get_stack(node, thd->stack, nsin, nsout);
2253                 
2254                 /* test the outputs */
2255                 /* skip value-only nodes (should be in type!) */
2256                 if(!node_only_value(node)) {
2257                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
2258                                 if(nsout[a]->data==NULL && nsout[a]->hasoutput) {
2259                                         node->need_exec= 1;
2260                                         break;
2261                                 }
2262                         }
2263                 }
2264                 
2265                 /* test the inputs */
2266                 for(a=0, sock= node->inputs.first; sock; sock= sock->next, a++) {
2267                         /* skip viewer nodes in bg render or group edit */
2268                         if( ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) && (G.background || group_edit))
2269                                 node->need_exec= 0;
2270                         /* is sock in use? */
2271                         else if(sock->link) {
2272                                 bNodeLink *link= sock->link;
2273                                 
2274                                 /* this is the test for a cyclic case */
2275                                 if(link->fromnode==NULL || link->tonode==NULL);
2276                                 else if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF) {
2277                                         if(link->fromnode->need_exec) {
2278                                                 node->need_exec= 1;
2279                                                 break;
2280                                         }
2281                                 }
2282                                 else {
2283                                         node->need_exec= 0;
2284                                         printf("Node %s skipped, cyclic dependency\n", node->name);
2285                                 }
2286                         }
2287                 }
2288                 
2289                 if(node->need_exec) {
2290                         
2291                         /* free output buffers */
2292                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
2293                                 if(nsout[a]->data) {
2294                                         free_compbuf(nsout[a]->data);
2295                                         nsout[a]->data= NULL;
2296                                 }
2297                         }
2298                         totnode++;
2299                         /* printf("node needs exec %s\n", node->name); */
2300                         
2301                         /* tag for getExecutableNode() */
2302                         node->exec= 0;
2303                 }
2304                 else {
2305                         /* tag for getExecutableNode() */
2306                         node->exec= NODE_READY|NODE_FINISHED|NODE_SKIPPED;
2307                         
2308                 }
2309         }
2310         
2311         /* last step: set the stack values for only-value nodes */
2312         /* just does all now, compared to a full buffer exec this is nothing */
2313         if(totnode) {
2314                 for(node= ntree->nodes.first; node; node= node->next) {
2315                         if(node->need_exec==0 && node_only_value(node)) {
2316                                 if(node->typeinfo->execfunc) {
2317                                         node_get_stack(node, thd->stack, nsin, nsout);
2318                                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2319                                 }
2320                         }
2321                 }
2322         }
2323         
2324         return totnode;
2325 }
2326
2327 /* while executing tree, free buffers from nodes that are not needed anymore */
2328 static void freeExecutableNode(bNodeTree *ntree)
2329 {
2330         /* node outputs can be freed when:
2331         - not a render result or image node
2332         - when node outputs go to nodes all being set NODE_FINISHED
2333         */
2334         bNode *node;
2335         bNodeSocket *sock;
2336         
2337         /* set exec flag for finished nodes that might need freed */
2338         for(node= ntree->nodes.first; node; node= node->next) {
2339                 if(node->type!=CMP_NODE_R_LAYERS)
2340                         if(node->exec & NODE_FINISHED)
2341                                 node->exec |= NODE_FREEBUFS;
2342         }
2343         /* clear this flag for input links that are not done yet */
2344         for(node= ntree->nodes.first; node; node= node->next) {
2345                 if((node->exec & NODE_FINISHED)==0) {
2346                         for(sock= node->inputs.first; sock; sock= sock->next)
2347                                 if(sock->link)
2348                                         sock->link->fromnode->exec &= ~NODE_FREEBUFS;
2349                 }
2350         }
2351         /* now we can free buffers */
2352         for(node= ntree->nodes.first; node; node= node->next) {
2353                 if(node->exec & NODE_FREEBUFS) {
2354                         for(sock= node->outputs.first; sock; sock= sock->next) {
2355                                 bNodeStack *ns= ntree->stack + sock->stack_index;
2356                                 if(ns->data) {
2357                                         free_compbuf(ns->data);
2358                                         ns->data= NULL;
2359                                         // printf("freed buf node %s \n", node->name);
2360                                 }
2361                         }
2362                 }
2363         }
2364 }
2365
2366 static bNode *getExecutableNode(bNodeTree *ntree)
2367 {
2368         bNode *node;
2369         bNodeSocket *sock;
2370         
2371         for(node= ntree->nodes.first; node; node= node->next) {
2372                 if(node->exec==0) {
2373                         
2374                         /* input sockets should be ready */
2375                         for(sock= node->inputs.first; sock; sock= sock->next) {
2376                                 if(sock->link)
2377                                         if((sock->link->fromnode->exec & NODE_READY)==0)
2378                                                 break;
2379                         }
2380                         if(sock==NULL)
2381                                 return node;
2382                 }
2383         }
2384         return NULL;
2385 }
2386
2387
2388 /* optimized tree execute test for compositing */
2389 void ntreeCompositExecTree(bNodeTree *ntree, RenderData *rd, int do_preview)
2390 {
2391         bNode *node;
2392         ListBase threads;
2393         ThreadData thdata;
2394         int totnode, rendering= 1;
2395         
2396         if(ntree==NULL) return;
2397         
2398         if(do_preview)
2399                 ntreeInitPreview(ntree, 0, 0);
2400         
2401         ntreeBeginExecTree(ntree);
2402         
2403         /* prevent unlucky accidents */
2404         if(G.background)
2405                 rd->scemode &= ~R_COMP_CROP;
2406         
2407         /* setup callerdata for thread callback */
2408         thdata.rd= rd;
2409         thdata.stack= ntree->stack;
2410         
2411         /* fixed seed, for example noise texture */
2412         BLI_srandom(rd->cfra);
2413
2414         /* sets need_exec tags in nodes */
2415         totnode= setExecutableNodes(ntree, &thdata);
2416
2417         BLI_init_threads(&threads, exec_composite_node, rd->threads);
2418         
2419         while(rendering) {
2420                 
2421                 if(BLI_available_threads(&threads)) {
2422                         node= getExecutableNode(ntree);
2423                         if(node) {
2424                                 
2425                                 if(ntree->timecursor)
2426                                         ntree->timecursor(ntree->tch, totnode);
2427                                 if(ntree->stats_draw) {
2428                                         char str[64];
2429                                         sprintf(str, "Compositing %d %s", totnode, node->name);
2430                                         ntree->stats_draw(ntree->sdh, str);
2431                                 }
2432                                 totnode--;
2433                                 
2434                                 node->threaddata = &thdata;
2435                                 node->exec= NODE_PROCESSING;
2436                                 BLI_insert_thread(&threads, node);
2437                         }
2438                         else
2439                                 PIL_sleep_ms(50);
2440                 }
2441                 else
2442                         PIL_sleep_ms(50);
2443                 
2444                 rendering= 0;
2445                 /* test for ESC */
2446                 if(ntree->test_break && ntree->test_break(ntree->tbh)) {
2447                         for(node= ntree->nodes.first; node; node= node->next)
2448                                 node->exec |= NODE_READY;
2449                 }
2450                 
2451                 /* check for ready ones, and if we need to continue */
2452                 for(node= ntree->nodes.first; node; node= node->next) {
2453                         if(node->exec & NODE_READY) {
2454                                 if((node->exec & NODE_FINISHED)==0) {
2455                                         BLI_remove_thread(&threads, node); /* this waits for running thread to finish btw */
2456                                         node->exec |= NODE_FINISHED;
2457                                         
2458                                         /* freeing unused buffers */
2459                                         if(rd->scemode & R_COMP_FREE)
2460                                                 freeExecutableNode(ntree);
2461                                 }
2462                         }
2463                         else rendering= 1;
2464                 }
2465         }
2466         
2467         BLI_end_threads(&threads);
2468         
2469         ntreeEndExecTree(ntree);
2470 }
2471
2472
2473 /* ********** copy composite tree entirely, to allow threaded exec ******************* */
2474 /* ***************** do NOT execute this in a thread!               ****************** */
2475
2476 /* returns localized composite tree for execution in threads */
2477 /* local tree then owns all compbufs */
2478 bNodeTree *ntreeLocalize(bNodeTree *ntree)
2479 {
2480         bNodeTree *ltree= ntreeCopyTree(ntree, 0);
2481         bNode *node;
2482         bNodeSocket *sock;
2483         
2484         /* move over the compbufs */
2485         /* right after ntreeCopyTree() oldsock pointers are valid */
2486         for(node= ntree->nodes.first; node; node= node->next) {
2487                 
2488                 /* store new_node pointer to original */
2489                 node->new_node->new_node= node;
2490                 /* ensure new user input gets handled ok */
2491                 node->need_exec= 0;
2492                 
2493                 if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2494                         if(node->id && (node->flag & NODE_DO_OUTPUT)) {
2495                                 node->new_node->id= (ID *)BKE_image_copy((Image *)node->id);
2496                         }
2497                 }
2498                 
2499                 for(sock= node->outputs.first; sock; sock= sock->next) {
2500                         
2501                         sock->new_sock->ns.data= sock->ns.data;
2502                         sock->ns.data= NULL;
2503                         sock->new_sock->new_sock= sock;
2504                 }
2505         }
2506         
2507         return ltree;
2508 }
2509
2510 static int node_exists(bNodeTree *ntree, bNode *testnode)
2511 {
2512         bNode *node= ntree->nodes.first;
2513         for(; node; node= node->next)
2514                 if(node==testnode)
2515                         return 1;
2516         return 0;
2517 }
2518
2519 static int outsocket_exists(bNode *node, bNodeSocket *testsock)
2520 {
2521         bNodeSocket *sock= node->outputs.first;
2522         for(; sock; sock= sock->next)
2523                 if(sock==testsock)
2524                         return 1;
2525         return 0;
2526 }
2527
2528
2529 /* sync local composite with real tree */
2530 /* local composite is supposed to be running, be careful moving previews! */
2531 void ntreeLocalSync(bNodeTree *localtree, bNodeTree *ntree)
2532 {
2533         bNode *lnode;
2534         
2535         /* move over the compbufs and previews */
2536         for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2537                 if( (lnode->exec & NODE_READY) && !(lnode->exec & NODE_SKIPPED) ) {
2538                         if(node_exists(ntree, lnode->new_node)) {
2539                                 
2540                                 if(lnode->preview && lnode->preview->rect) {
2541                                         node_free_preview(lnode->new_node);
2542                                         lnode->new_node->preview= lnode->preview;
2543                                         lnode->preview= NULL;
2544                                 }
2545                         }
2546                 }
2547         }
2548 }
2549
2550 /* merge local tree results back, and free local tree */
2551 /* we have to assume the editor already changed completely */
2552 void ntreeLocalMerge(bNodeTree *localtree, bNodeTree *ntree)
2553 {
2554         bNode *lnode;
2555         bNodeSocket *lsock;
2556         
2557         /* move over the compbufs and previews */
2558         for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2559                 if(node_exists(ntree, lnode->new_node)) {
2560                         
2561                         if(lnode->preview && lnode->preview->rect) {
2562                                 node_free_preview(lnode->new_node);
2563                                 lnode->new_node->preview= lnode->preview;
2564                                 lnode->preview= NULL;
2565                         }
2566                         
2567                         if(ELEM(lnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2568                                 if(lnode->id && (lnode->flag & NODE_DO_OUTPUT)) {
2569                                         BKE_image_merge((Image *)lnode->new_node->id, (Image *)lnode->id);
2570                                 }
2571                         }
2572                         
2573                         for(lsock= lnode->outputs.first; lsock; lsock= lsock->next) {
2574                                 if(outsocket_exists(lnode->new_node, lsock->new_sock)) {
2575                                         lsock->new_sock->ns.data= lsock->ns.data;
2576                                         lsock->ns.data= NULL;
2577                                         lsock->new_sock= NULL;
2578                                 }
2579                         }
2580                 }
2581         }
2582         ntreeFreeTree(localtree);
2583         MEM_freeN(localtree);
2584 }
2585
2586 /* *********************************************** */
2587
2588 /* GPU material from shader nodes */
2589
2590 static void gpu_from_node_stack(ListBase *sockets, bNodeStack **ns, GPUNodeStack *gs)
2591 {
2592         bNodeSocket *sock;
2593         int i;
2594
2595         for (sock=sockets->first, i=0; sock; sock=sock->next, i++) {
2596                 memset(&gs[i], 0, sizeof(gs[i]));
2597
2598         QUATCOPY(gs[i].vec, ns[i]->vec);
2599                 gs[i].link= ns[i]->data;
2600
2601                 if (sock->type == SOCK_VALUE)
2602                         gs[i].type= GPU_FLOAT;
2603                 else if (sock->type == SOCK_VECTOR)
2604                         gs[i].type= GPU_VEC3;
2605                 else if (sock->type == SOCK_RGBA)
2606                         gs[i].type= GPU_VEC4;
2607                 else
2608                         gs[i].type= GPU_NONE;
2609
2610                 gs[i].name = "";
2611                 gs[i].hasinput= ns[i]->hasinput && ns[i]->data;
2612                 gs[i].hasoutput= ns[i]->hasinput && ns[i]->data;
2613                 gs[i].sockettype= ns[i]->sockettype;
2614         }
2615
2616         gs[i].type= GPU_NONE;
2617 }
2618
2619 static void data_from_gpu_stack(ListBase *sockets, bNodeStack **ns, GPUNodeStack *gs)
2620 {
2621         bNodeSocket *sock;
2622         int i;
2623
2624         for (sock=sockets->first, i=0; sock; sock=sock->next, i++) {
2625                 ns[i]->data= gs[i].link;
2626                 ns[i]->hasinput= gs[i].hasinput && gs[i].link;
2627                 ns[i]->hasoutput= gs[i].hasoutput;
2628                 ns[i]->sockettype= gs[i].sockettype;
2629         }
2630 }
2631
2632 static void gpu_node_group_execute(bNodeStack *stack, GPUMaterial *mat, bNode *gnode, bNodeStack **in, bNodeStack **out)
2633 {
2634         bNode *node;
2635         bNodeTree *ntree= (bNodeTree *)gnode->id;
2636         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2637         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2638         GPUNodeStack gpuin[MAX_SOCKET+1], gpuout[MAX_SOCKET+1];
2639         int doit = 0;
2640         
2641         if(ntree==NULL) return;
2642         
2643         stack+= gnode->stack_index;
2644                 
2645         for(node= ntree->nodes.first; node; node= node->next) {
2646                 if(node->typeinfo->gpufunc) {
2647                         group_node_get_stack(node, stack, nsin, nsout, in, out);
2648
2649                         doit = 0;
2650                         
2651                         /* for groups, only execute outputs for edited group */
2652                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
2653                                 if(gnode->flag & NODE_GROUP_EDIT)
2654                                         if(node->flag & NODE_DO_OUTPUT)
2655                                                 doit = 1;
2656                         }
2657                         else
2658                                 doit = 1;
2659
2660                         if(doit)  {
2661                                 gpu_from_node_stack(&node->inputs, nsin, gpuin);
2662                                 gpu_from_node_stack(&node->outputs, nsout, gpuout);
2663                                 if(node->typeinfo->gpufunc(mat, node, gpuin, gpuout))
2664                                         data_from_gpu_stack(&node->outputs, nsout, gpuout);
2665                         }
2666                 }
2667         }
2668 }
2669
2670 void ntreeGPUMaterialNodes(bNodeTree *ntree, GPUMaterial *mat)
2671 {
2672         bNode *node;
2673         bNodeStack *stack;
2674         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2675         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2676         GPUNodeStack gpuin[MAX_SOCKET+1], gpuout[MAX_SOCKET+1];
2677
2678         if((ntree->init & NTREE_EXEC_INIT)==0)
2679                 ntreeBeginExecTree(ntree);
2680
2681         stack= ntree->stack;
2682
2683         for(node= ntree->nodes.first; node; node= node->next) {
2684                 if(node->typeinfo->gpufunc) {
2685                         node_get_stack(node, stack, nsin, nsout);
2686                         gpu_from_node_stack(&node->inputs, nsin, gpuin);
2687                         gpu_from_node_stack(&node->outputs, nsout, gpuout);
2688                         if(node->typeinfo->gpufunc(mat, node, gpuin, gpuout))
2689                                 data_from_gpu_stack(&node->outputs, nsout, gpuout);
2690                 }
2691         else if(node->type==NODE_GROUP && node->id) {
2692                         node_get_stack(node, stack, nsin, nsout);
2693                         gpu_node_group_execute(stack, mat, node, nsin, nsout);
2694                 }
2695         }
2696
2697         ntreeEndExecTree(ntree);
2698 }
2699
2700 /* **************** call to switch lamploop for material node ************ */
2701
2702 void (*node_shader_lamp_loop)(struct ShadeInput *, struct ShadeResult *);
2703
2704 void set_node_shader_lamp_loop(void (*lamp_loop_func)(ShadeInput *, ShadeResult *))
2705 {
2706         node_shader_lamp_loop= lamp_loop_func;
2707 }
2708
2709 /* clumsy checking... should do dynamic outputs once */
2710 static void force_hidden_passes(bNode *node, int passflag)
2711 {
2712         bNodeSocket *sock;
2713         
2714         for(sock= node->outputs.first; sock; sock= sock->next)
2715                 sock->flag &= ~SOCK_UNAVAIL;
2716         
2717         sock= BLI_findlink(&node->outputs, RRES_OUT_Z);
2718         if(!(passflag & SCE_PASS_Z)) sock->flag |= SOCK_UNAVAIL;
2719         sock= BLI_findlink(&node->outputs, RRES_OUT_NORMAL);
2720         if(!(passflag & SCE_PASS_NORMAL)) sock->flag |= SOCK_UNAVAIL;
2721         sock= BLI_findlink(&node->outputs, RRES_OUT_VEC);
2722         if(!(passflag & SCE_PASS_VECTOR)) sock->flag |= SOCK_UNAVAIL;
2723         sock= BLI_findlink(&node->outputs, RRES_OUT_UV);
2724         if(!(passflag & SCE_PASS_UV)) sock->flag |= SOCK_UNAVAIL;
2725         sock= BLI_findlink(&node->outputs, RRES_OUT_RGBA);
2726         if(!(passflag & SCE_PASS_RGBA)) sock->flag |= SOCK_UNAVAIL;
2727         sock= BLI_findlink(&node->outputs, RRES_OUT_DIFF);
2728         if(!(passflag & SCE_PASS_DIFFUSE)) sock->flag |= SOCK_UNAVAIL;
2729         sock= BLI_findlink(&node->outputs, RRES_OUT_SPEC);
2730         if(!(passflag & SCE_PASS_SPEC)) sock->flag |= SOCK_UNAVAIL;
2731         sock= BLI_findlink(&node->outputs, RRES_OUT_SHADOW);
2732         if(!(passflag & SCE_PASS_SHADOW)) sock->flag |= SOCK_UNAVAIL;
2733         sock= BLI_findlink(&node->outputs, RRES_OUT_AO);
2734         if(!(passflag & SCE_PASS_AO)) sock->flag |= SOCK_UNAVAIL;
2735         sock= BLI_findlink(&node->outputs, RRES_OUT_REFLECT);
2736         if(!(passflag & SCE_PASS_REFLECT)) sock->flag |= SOCK_UNAVAIL;
2737         sock= BLI_findlink(&node->outputs, RRES_OUT_REFRACT);
2738         if(!(passflag & SCE_PASS_REFRACT)) sock->flag |= SOCK_UNAVAIL;
2739         sock= BLI_findlink(&node->outputs, RRES_OUT_RADIO);
2740         if(!(passflag & SCE_PASS_RADIO)) sock->flag |= SOCK_UNAVAIL;
2741         sock= BLI_findlink(&node->outputs, RRES_OUT_INDEXOB);
2742         if(!(passflag & SCE_PASS_INDEXOB)) sock->flag |= SOCK_UNAVAIL;
2743         sock= BLI_findlink(&node->outputs, RRES_OUT_MIST);
2744         if(!(passflag & SCE_PASS_MIST)) sock->flag |= SOCK_UNAVAIL;
2745         
2746 }
2747
2748 /* based on rules, force sockets hidden always */
2749 void ntreeCompositForceHidden(bNodeTree *ntree, Scene *curscene)
2750 {
2751         bNode *node;
2752         
2753         if(ntree==NULL) return;
2754         
2755         for(node= ntree->nodes.first; node; node= node->next) {
2756                 if( node->type==CMP_NODE_R_LAYERS) {
2757                         Scene *sce= node->id?(Scene *)node->id:curscene;
2758                         SceneRenderLayer *srl= BLI_findlink(&sce->r.layers, node->custom1);
2759                         if(srl)
2760                                 force_hidden_passes(node, srl->passflag);
2761                 }
2762                 else if( node->type==CMP_NODE_IMAGE) {
2763                         Image *ima= (Image *)node->id;
2764                         if(ima) {
2765                                 if(ima->rr) {
2766                                         ImageUser *iuser= node->storage;
2767                                         RenderLayer *rl= BLI_findlink(&ima->rr->layers, iuser->layer);
2768                                         if(rl)
2769                                                 force_hidden_passes(node, rl->passflag);
2770                                         else
2771                                                 force_hidden_passes(node, 0);
2772                                 }
2773                                 else if(ima->type!=IMA_TYPE_MULTILAYER) {       /* if ->rr not yet read we keep inputs */
2774                                         force_hidden_passes(node, RRES_OUT_Z);
2775                                 }
2776                                 else
2777                                         force_hidden_passes(node, 0);
2778                         }
2779                         else
2780                                 force_hidden_passes(node, 0);
2781                 }
2782         }
2783
2784 }
2785
2786 /* called from render pipeline, to tag render input and output */
2787 /* need to do all scenes, to prevent errors when you re-render 1 scene */
2788 void ntreeCompositTagRender(Scene *curscene)
2789 {
2790         Scene *sce;
2791         
2792         for(sce= G.main->scene.first; sce; sce= sce->id.next) {
2793                 if(sce->nodetree) {
2794                         bNode *node;
2795                         
2796                         for(node= sce->nodetree->nodes.first; node; node= node->next) {
2797                                 if(node->id==(ID *)curscene || node->type==CMP_NODE_COMPOSITE)
2798                                         NodeTagChanged(sce->nodetree, node);
2799                         }
2800                 }
2801         }
2802 }
2803
2804 /* tags nodes that have animation capabilities */
2805 int ntreeCompositTagAnimated(bNodeTree *ntree)
2806 {
2807         bNode *node;
2808         int tagged= 0;
2809         
2810         if(ntree==NULL) return 0;
2811         
2812         for(node= ntree->nodes.first; node; node= node->next) {
2813                 if(node->type==CMP_NODE_IMAGE) {
2814                         Image *ima= (Image *)node->id;
2815                         if(ima && ELEM(ima->source, IMA_SRC_MOVIE, IMA_SRC_SEQUENCE)) {
2816                                 NodeTagChanged(ntree, node);
2817                                 tagged= 1;
2818                         }
2819                 }
2820                 else if(node->type==CMP_NODE_TIME) {
2821                         NodeTagChanged(ntree, node);
2822                         tagged= 1;
2823                 }
2824                 else if(node->type==CMP_NODE_R_LAYERS) {
2825                         NodeTagChanged(ntree, node);
2826                         tagged= 1;
2827                 }
2828                 else if(node->type==NODE_GROUP) {
2829                         if( ntreeCompositTagAnimated((bNodeTree *)node->id) ) {
2830                                 NodeTagChanged(ntree, node);
2831                         }
2832                 }
2833         }
2834         
2835         return tagged;
2836 }
2837
2838
2839 /* called from image window preview */
2840 void ntreeCompositTagGenerators(bNodeTree *ntree)
2841 {
2842         bNode *node;
2843         
2844         if(ntree==NULL) return;
2845         
2846         for(node= ntree->nodes.first; node; node= node->next) {
2847                 if( ELEM(node->type, CMP_NODE_R_LAYERS, CMP_NODE_IMAGE))
2848                         NodeTagChanged(ntree, node);
2849         }
2850 }
2851
2852 int ntreeTexTagAnimated(bNodeTree *ntree)
2853 {
2854         bNode *node;
2855         
2856         if(ntree==NULL) return 0;
2857         
2858         for(node= ntree->nodes.first; node; node= node->next) {
2859                 if(node->type==TEX_NODE_CURVE_TIME) {
2860                         NodeTagChanged(ntree, node);
2861                         return 1;
2862                 }
2863                 else if(node->type==NODE_GROUP) {
2864                         if( ntreeTexTagAnimated((bNodeTree *)node->id) ) {
2865                                 return 1;
2866                         }
2867                 }
2868         }
2869         
2870         return 0;
2871 }
2872
2873 /* ************* node definition init ********** */
2874
2875 static bNodeType *is_nodetype_registered(ListBase *typelist, int type, ID *id) 
2876 {
2877         bNodeType *ntype= typelist->first;
2878         
2879         for(;ntype; ntype= ntype->next )
2880                 if(ntype->type==type && ntype->id==id)
2881                         return ntype;
2882         
2883         return NULL;
2884 }
2885
2886 /* type can be from a static array, we make copy for duplicate types (like group) */
2887 void nodeRegisterType(ListBase *typelist, const bNodeType *ntype) 
2888 {
2889         bNodeType *found= is_nodetype_registered(typelist, ntype->type, ntype->id);
2890         
2891         if(found==NULL) {
2892                 bNodeType *ntypen= MEM_callocN(sizeof(bNodeType), "node type");
2893                 *ntypen= *ntype;
2894                 BLI_addtail(typelist, ntypen);
2895         }
2896 }
2897
2898 static void registerCompositNodes(ListBase *ntypelist)
2899 {
2900         nodeRegisterType(ntypelist, &node_group_typeinfo);
2901         nodeRegisterType(ntypelist, &cmp_node_rlayers);
2902         nodeRegisterType(ntypelist, &cmp_node_image);
2903         nodeRegisterType(ntypelist, &cmp_node_texture);
2904         nodeRegisterType(ntypelist, &cmp_node_value);
2905         nodeRegisterType(ntypelist, &cmp_node_rgb);
2906         nodeRegisterType(ntypelist, &cmp_node_curve_time);
2907         
2908         nodeRegisterType(ntypelist, &cmp_node_composite);
2909         nodeRegisterType(ntypelist, &cmp_node_viewer);
2910         nodeRegisterType(ntypelist, &cmp_node_splitviewer);
2911         nodeRegisterType(ntypelist, &cmp_node_output_file);
2912         
2913         nodeRegisterType(ntypelist, &cmp_node_curve_rgb);
2914         nodeRegisterType(ntypelist, &cmp_node_mix_rgb);
2915         nodeRegisterType(ntypelist, &cmp_node_hue_sat);
2916         nodeRegisterType(ntypelist, &cmp_node_brightcontrast);
2917         nodeRegisterType(ntypelist, &cmp_node_gamma);
2918         nodeRegisterType(ntypelist, &cmp_node_invert);
2919         nodeRegisterType(ntypelist, &cmp_node_alphaover);
2920         nodeRegisterType(ntypelist, &cmp_node_zcombine);
2921         
2922         nodeRegisterType(ntypelist, &cmp_node_normal);
2923         nodeRegisterType(ntypelist, &cmp_node_curve_vec);
2924         nodeRegisterType(ntypelist, &cmp_node_map_value);
2925         nodeRegisterType(ntypelist, &cmp_node_normalize);
2926         
2927         nodeRegisterType(ntypelist, &cmp_node_filter);
2928         nodeRegisterType(ntypelist, &cmp_node_blur);
2929         nodeRegisterType(ntypelist, &cmp_node_dblur);
2930         nodeRegisterType(ntypelist, &cmp_node_bilateralblur);
2931         nodeRegisterType(ntypelist, &cmp_node_vecblur);
2932         nodeRegisterType(ntypelist, &cmp_node_dilateerode);
2933         nodeRegisterType(ntypelist, &cmp_node_defocus);
2934         
2935         nodeRegisterType(ntypelist, &cmp_node_valtorgb);
2936         nodeRegisterType(ntypelist, &cmp_node_rgbtobw);
2937         nodeRegisterType(ntypelist, &cmp_node_setalpha);
2938         nodeRegisterType(ntypelist, &cmp_node_idmask);
2939         nodeRegisterType(ntypelist, &cmp_node_math);
2940         nodeRegisterType(ntypelist, &cmp_node_seprgba);
2941         nodeRegisterType(ntypelist, &cmp_node_combrgba);
2942         nodeRegisterType(ntypelist, &cmp_node_sephsva);
2943         nodeRegisterType(ntypelist, &cmp_node_combhsva);
2944         nodeRegisterType(ntypelist, &cmp_node_sepyuva);
2945         nodeRegisterType(ntypelist, &cmp_node_combyuva);
2946         nodeRegisterType(ntypelist, &cmp_node_sepycca);
2947         nodeRegisterType(ntypelist, &cmp_node_combycca);
2948         nodeRegisterType(ntypelist, &cmp_node_premulkey);
2949         
2950         nodeRegisterType(ntypelist, &cmp_node_diff_matte);
2951         nodeRegisterType(ntypelist, &cmp_node_chroma);
2952         nodeRegisterType(ntypelist, &cmp_node_channel_matte);
2953         nodeRegisterType(ntypelist, &cmp_node_color_spill);
2954         nodeRegisterType(ntypelist, &cmp_node_luma_matte);
2955         
2956         nodeRegisterType(ntypelist, &cmp_node_translate);
2957         nodeRegisterType(ntypelist, &cmp_node_rotate);
2958         nodeRegisterType(ntypelist, &cmp_node_scale);
2959         nodeRegisterType(ntypelist, &cmp_node_flip);
2960         nodeRegisterType(ntypelist, &cmp_node_crop);
2961         nodeRegisterType(ntypelist, &cmp_node_displace);
2962         nodeRegisterType(ntypelist, &cmp_node_mapuv);
2963         nodeRegisterType(ntypelist, &cmp_node_glare);
2964         nodeRegisterType(ntypelist, &cmp_node_tonemap);
2965         nodeRegisterType(ntypelist, &cmp_node_lensdist);
2966 }
2967
2968 static void registerShaderNodes(ListBase *ntypelist) 
2969 {
2970         nodeRegisterType(ntypelist, &node_group_typeinfo);
2971         nodeRegisterType(ntypelist, &sh_node_output);
2972         nodeRegisterType(ntypelist, &sh_node_mix_rgb);
2973         nodeRegisterType(ntypelist, &sh_node_valtorgb);
2974         nodeRegisterType(ntypelist, &sh_node_rgbtobw);
2975         nodeRegisterType(ntypelist, &sh_node_normal);
2976         nodeRegisterType(ntypelist, &sh_node_geom);
2977         nodeRegisterType(ntypelist, &sh_node_mapping);
2978         nodeRegisterType(ntypelist, &sh_node_curve_vec);
2979         nodeRegisterType(ntypelist, &sh_node_curve_rgb);
2980         nodeRegisterType(ntypelist, &sh_node_math);
2981         nodeRegisterType(ntypelist, &sh_node_vect_math);
2982         nodeRegisterType(ntypelist, &sh_node_squeeze);
2983         nodeRegisterType(ntypelist, &sh_node_camera);
2984         nodeRegisterType(ntypelist, &sh_node_material);
2985         nodeRegisterType(ntypelist, &sh_node_material_ext);
2986         nodeRegisterType(ntypelist, &sh_node_value);
2987         nodeRegisterType(ntypelist, &sh_node_rgb);
2988         nodeRegisterType(ntypelist, &sh_node_texture);
2989         nodeRegisterType(ntypelist, &node_dynamic_typeinfo);
2990         nodeRegisterType(ntypelist, &sh_node_invert);
2991         nodeRegisterType(ntypelist, &sh_node_seprgb);
2992         nodeRegisterType(ntypelist, &sh_node_combrgb);
2993         nodeRegisterType(ntypelist, &sh_node_hue_sat);
2994 }
2995
2996 static void registerTextureNodes(ListBase *ntypelist)
2997 {
2998         nodeRegisterType(ntypelist, &node_group_typeinfo);
2999         nodeRegisterType(ntypelist, &tex_node_math);
3000         nodeRegisterType(ntypelist, &tex_node_mix_rgb);
3001         nodeRegisterType(ntypelist, &tex_node_valtorgb);
3002         nodeRegisterType(ntypelist, &tex_node_rgbtobw);
3003         nodeRegisterType(ntypelist, &tex_node_curve_rgb);
3004         nodeRegisterType(ntypelist, &tex_node_curve_time);
3005         nodeRegisterType(ntypelist, &tex_node_invert);
3006         nodeRegisterType(ntypelist, &tex_node_hue_sat);
3007         nodeRegisterType(ntypelist, &tex_node_coord);
3008         nodeRegisterType(ntypelist, &tex_node_distance);
3009         
3010         nodeRegisterType(ntypelist, &tex_node_output);
3011         nodeRegisterType(ntypelist, &tex_node_viewer);
3012         
3013         nodeRegisterType(ntypelist, &tex_node_checker);
3014         nodeRegisterType(ntypelist, &tex_node_texture);
3015         nodeRegisterType(ntypelist, &tex_node_bricks);
3016         nodeRegisterType(ntypelist, &tex_node_image);
3017         
3018         nodeRegisterType(ntypelist, &tex_node_rotate);
3019         nodeRegisterType(ntypelist, &tex_node_translate);
3020         
3021         nodeRegisterType(ntypelist, &tex_node_proc_voronoi);
3022         nodeRegisterType(ntypelist, &tex_node_proc_blend);
3023         nodeRegisterType(ntypelist, &tex_node_proc_magic);
3024         nodeRegisterType(ntypelist, &tex_node_proc_marble);
3025         nodeRegisterType(ntypelist, &tex_node_proc_clouds);
3026         nodeRegisterType(ntypelist, &tex_node_proc_wood);
3027         nodeRegisterType(ntypelist, &tex_node_proc_musgrave);
3028         nodeRegisterType(ntypelist, &tex_node_proc_noise);
3029         nodeRegisterType(ntypelist, &tex_node_proc_stucci);
3030         nodeRegisterType(ntypelist, &tex_node_proc_distnoise);
3031 }
3032
3033 static void remove_dynamic_typeinfos(ListBase *list)
3034 {
3035         bNodeType *ntype= list->first;
3036         bNodeType *next= NULL;
3037         while(ntype) {
3038                 next= ntype->next;
3039                 if(ntype->type==NODE_DYNAMIC && ntype->id!=NULL) {
3040                         BLI_remlink(list, ntype);
3041                         if(ntype->inputs) {
3042                                 bNodeSocketType *sock= ntype->inputs;
3043                                 while(sock->type!=-1) {
3044                                         MEM_freeN(sock->name);
3045                                         sock++;
3046                                 }
3047                                 MEM_freeN(ntype->inputs);
3048                         }
3049                         if(ntype->outputs) {
3050                                 bNodeSocketType *sock= ntype->outputs;
3051                                 while(sock->type!=-1) {
3052                                         MEM_freeN(sock->name);
3053                                         sock++;
3054                                 }
3055                                 MEM_freeN(ntype->outputs);
3056                         }
3057                         if(ntype->name) {
3058                                 MEM_freeN(ntype->name);
3059                         }
3060                         MEM_freeN(ntype);
3061                 }
3062                 ntype= next;
3063         }
3064 }
3065
3066 void init_nodesystem(void) 
3067 {
3068         registerCompositNodes(&node_all_composit);
3069         registerShaderNodes(&node_all_shaders);
3070         registerTextureNodes(&node_all_textures);
3071 }
3072
3073 void free_nodesystem(void) 
3074 {
3075         /*remove_dynamic_typeinfos(&node_all_composit);*/ /* unused for now */
3076         BLI_freelistN(&node_all_composit);
3077         remove_dynamic_typeinfos(&node_all_shaders);
3078         BLI_freelistN(&node_all_shaders);
3079         BLI_freelistN(&node_all_textures);
3080 }