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