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