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