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