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