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