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