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