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