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