=== Node editor ===
[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;
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         duplicatelist(&nnode->inputs, &node->inputs);
810         for(sock= nnode->inputs.first; sock; sock= sock->next)
811                 sock->own_index= 0;
812         
813         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                 if(is_group==0) {
1627                         for(sock= node->outputs.first; sock; sock= sock->next) {
1628                                 bNodeStack *ns= ntree->stack[0] + sock->stack_index;
1629                                 
1630                                 if(sock->ns.data) {
1631                                         ns->data= sock->ns.data;
1632                                         sock->ns.data= NULL;
1633                                 }
1634                         }
1635                 }               
1636                 /* cannot initialize them while using in threads */
1637                 if(ELEM3(node->type, CMP_NODE_TIME, CMP_NODE_CURVE_VEC, CMP_NODE_CURVE_RGB)) {
1638                         curvemapping_initialize(node->storage);
1639                         if(node->type==CMP_NODE_CURVE_RGB)
1640                                 curvemapping_premultiply(node->storage, 0);
1641                 }
1642                 if(node->type==NODE_GROUP)
1643                         composit_begin_exec((bNodeTree *)node->id, 1);
1644
1645         }
1646 }
1647
1648 /* copy stack compbufs to sockets */
1649 static void composit_end_exec(bNodeTree *ntree, int is_group)
1650 {
1651         extern void print_compbuf(char *str, struct CompBuf *cbuf);
1652         bNode *node;
1653         bNodeStack *ns;
1654         int a;
1655
1656         for(node= ntree->nodes.first; node; node= node->next) {
1657                 if(is_group==0) {
1658                         bNodeSocket *sock;
1659                 
1660                         for(sock= node->outputs.first; sock; sock= sock->next) {
1661                                 ns= ntree->stack[0] + sock->stack_index;
1662                                 if(ns->data) {
1663                                         sock->ns.data= ns->data;
1664                                         ns->data= NULL;
1665                                 }
1666                         }
1667                 }
1668                 if(node->type==CMP_NODE_CURVE_RGB)
1669                         curvemapping_premultiply(node->storage, 1);
1670                 
1671                 if(node->type==NODE_GROUP)
1672                         composit_end_exec((bNodeTree *)node->id, 1);
1673
1674                 node->need_exec= 0;
1675         }
1676         
1677         if(is_group==0) {
1678                 /* internally, group buffers are not stored */
1679                 for(ns= ntree->stack[0], a=0; a<ntree->stacksize; a++, ns++) {
1680                         if(ns->data) {
1681                                 printf("freed leftover buffer from stack\n");
1682                                 free_compbuf(ns->data);
1683                         }
1684                 }
1685         }
1686 }
1687
1688 static void group_tag_used_outputs(bNode *gnode, bNodeStack *stack)
1689 {
1690         bNodeTree *ntree= (bNodeTree *)gnode->id;
1691         bNode *node;
1692         
1693         stack+= gnode->stack_index;
1694         
1695         for(node= ntree->nodes.first; node; node= node->next) {
1696                 if(node->typeinfo->execfunc) {
1697                         bNodeSocket *sock;
1698                         
1699                         for(sock= node->inputs.first; sock; sock= sock->next) {
1700                                 if(sock->intern) {
1701                                         if(sock->link) {
1702                                                 bNodeStack *ns= stack + sock->link->fromsock->stack_index;
1703                                                 ns->hasoutput= 1;
1704                                                 ns->sockettype= sock->link->fromsock->type;
1705                                         }
1706                                         else
1707                                                 sock->ns.sockettype= sock->type;
1708                                 }
1709                         }
1710                 }
1711         }
1712 }
1713
1714 /* stack indices make sure all nodes only write in allocated data, for making it thread safe */
1715 /* only root tree gets the stack, to enable instances to have own stack entries */
1716 /* only two threads now! */
1717 /* per tree (and per group) unique indices are created */
1718 /* the index_ext we need to be able to map from groups to the group-node own stack */
1719
1720 void ntreeBeginExecTree(bNodeTree *ntree)
1721 {
1722         /* let's make it sure */
1723         if(ntree->init & NTREE_EXEC_INIT)
1724                 return;
1725         
1726         /* allocate the stack pointer array */
1727         ntree->stack= MEM_callocN(BLENDER_MAX_THREADS*sizeof(void *), "stack array");
1728         
1729         /* goes recursive over all groups */
1730         ntree->stacksize= ntree_begin_exec_tree(ntree);
1731
1732         if(ntree->stacksize) {
1733                 bNode *node;
1734                 bNodeStack *ns;
1735                 int a;
1736                 
1737                 /* allocate the base stack */
1738                 ns=ntree->stack[0]= MEM_callocN(ntree->stacksize*sizeof(bNodeStack), "node stack");
1739                 
1740                 /* tag inputs, the get_stack() gives own socket stackdata if not in use */
1741                 for(a=0; a<ntree->stacksize; a++, ns++) ns->hasinput= 1;
1742                 
1743                 /* tag used outputs, so we know when we can skip operations */
1744                 for(node= ntree->nodes.first; node; node= node->next) {
1745                         bNodeSocket *sock;
1746                         for(sock= node->inputs.first; sock; sock= sock->next) {
1747                                 if(sock->link) {
1748                                         ns= ntree->stack[0] + sock->link->fromsock->stack_index;
1749                                         ns->hasoutput= 1;
1750                                         ns->sockettype= sock->link->fromsock->type;
1751                                 }
1752                                 else
1753                                         sock->ns.sockettype= sock->type;
1754                         }
1755                         if(node->type==NODE_GROUP && node->id)
1756                                 group_tag_used_outputs(node, ntree->stack[0]);
1757                 }
1758                 
1759                 /* composite does 1 node per thread, so no multiple stacks needed */
1760                 if(ntree->type==NTREE_COMPOSIT)
1761                         composit_begin_exec(ntree, 0);
1762                 else {
1763                         for(a=1; a<BLENDER_MAX_THREADS; a++)
1764                                 ntree->stack[a]= MEM_dupallocN(ntree->stack[0]);
1765                 }
1766         }
1767         
1768         ntree->init |= NTREE_EXEC_INIT;
1769 }
1770
1771 void ntreeEndExecTree(bNodeTree *ntree)
1772 {
1773         
1774         if(ntree->init & NTREE_EXEC_INIT) {
1775                 int a;
1776                 
1777                 /* another callback candidate! */
1778                 if(ntree->type==NTREE_COMPOSIT)
1779                         composit_end_exec(ntree, 0);
1780                 
1781                 if(ntree->stack) {
1782                         for(a=0; a<BLENDER_MAX_THREADS; a++)
1783                                 if(ntree->stack[a])
1784                                         MEM_freeN(ntree->stack[a]);
1785                 
1786                         MEM_freeN(ntree->stack);
1787                         ntree->stack= NULL;
1788                 }
1789
1790                 ntree->init &= ~NTREE_EXEC_INIT;
1791         }
1792 }
1793
1794 static void node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out)
1795 {
1796         bNodeSocket *sock;
1797         
1798         /* build pointer stack */
1799         for(sock= node->inputs.first; sock; sock= sock->next) {
1800                 if(sock->link)
1801                         *(in++)= stack + sock->link->fromsock->stack_index;
1802                 else
1803                         *(in++)= &sock->ns;
1804         }
1805         
1806         for(sock= node->outputs.first; sock; sock= sock->next) {
1807                 *(out++)= stack + sock->stack_index;
1808         }
1809 }
1810
1811 /* nodes are presorted, so exec is in order of list */
1812 void ntreeExecTree(bNodeTree *ntree, void *callerdata, int thread)
1813 {
1814         bNode *node;
1815         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1816         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1817         bNodeStack *stack;
1818         
1819         /* only when initialized */
1820         if((ntree->init & NTREE_EXEC_INIT)==0)
1821                 ntreeBeginExecTree(ntree);
1822                 
1823         stack= ntree->stack[thread];
1824         
1825         for(node= ntree->nodes.first; node; node= node->next) {
1826                 if(node->typeinfo->execfunc) {
1827                         node_get_stack(node, stack, nsin, nsout);
1828                         node->typeinfo->execfunc(callerdata, node, nsin, nsout);
1829                 }
1830                 else if(node->type==NODE_GROUP && node->id) {
1831                         node_get_stack(node, stack, nsin, nsout);
1832                         node_group_execute(stack, callerdata, node, nsin, nsout); 
1833                 }
1834         }
1835 }
1836
1837
1838 /* ***************************** threaded version for execute composite nodes ************* */
1839
1840 /* not changing info, for thread callback */
1841 typedef struct ThreadData {
1842         bNodeStack *stack;
1843         RenderData *rd;
1844 } ThreadData;
1845
1846 static void *exec_composite_node(void *node_v)
1847 {
1848         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1849         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1850         bNode *node= node_v;
1851         ThreadData *thd= (ThreadData *)node->new_node; /* abuse */
1852         
1853         node_get_stack(node, thd->stack, nsin, nsout);
1854         
1855         if(node->typeinfo->execfunc) {
1856                 node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
1857         }
1858         else if(node->type==NODE_GROUP && node->id) {
1859                 node_group_execute(thd->stack, thd->rd, node, nsin, nsout); 
1860         }
1861         
1862         node->exec |= NODE_READY;
1863         return 0;
1864 }
1865
1866 /* these are nodes without input, only giving values */
1867 /* or nodes with only value inputs */
1868 static int node_only_value(bNode *node)
1869 {
1870         bNodeSocket *sock;
1871         
1872         if(ELEM3(node->type, CMP_NODE_TIME, CMP_NODE_VALUE, CMP_NODE_RGB))
1873                 return 1;
1874         
1875         /* doing this for all node types goes wrong. memory free errors */
1876         if(node->inputs.first && node->type==CMP_NODE_MAP_VALUE) {
1877                 int retval= 1;
1878                 for(sock= node->inputs.first; sock; sock= sock->next) {
1879                         if(sock->link)
1880                                 retval &= node_only_value(sock->link->fromnode);
1881                 }
1882                 return retval;
1883         }
1884         return 0;
1885 }
1886
1887 /* return total of executable nodes, for timecursor */
1888 /* only compositor uses it */
1889 static int setExecutableNodes(bNodeTree *ntree, ThreadData *thd)
1890 {
1891         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1892         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1893         bNode *node;
1894         bNodeSocket *sock;
1895         int totnode= 0, group_edit= 0;
1896         
1897         /* note; do not add a dependency sort here, the stack was created already */
1898         
1899         /* if we are in group edit, viewer nodes get skipped when group has viewer */
1900         for(node= ntree->nodes.first; node; node= node->next)
1901                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1902                         if(ntreeHasType((bNodeTree *)node->id, CMP_NODE_VIEWER))
1903                                 group_edit= 1;
1904         
1905         for(node= ntree->nodes.first; node; node= node->next) {
1906                 int a;
1907                 
1908                 node_get_stack(node, thd->stack, nsin, nsout);
1909                 
1910                 /* test the outputs */
1911                 /* skip value-only nodes (should be in type!) */
1912                 if(!node_only_value(node)) {
1913                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
1914                                 if(nsout[a]->data==NULL && nsout[a]->hasoutput) {
1915                                         node->need_exec= 1;
1916                                         break;
1917                                 }
1918                         }
1919                 }
1920                 
1921                 /* test the inputs */
1922                 for(a=0, sock= node->inputs.first; sock; sock= sock->next, a++) {
1923                         /* skip viewer nodes in bg render or group edit */
1924                         if( ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) && (G.background || group_edit))
1925                                 node->need_exec= 0;
1926                         /* is sock in use? */
1927                         else if(sock->link) {
1928                                 bNodeLink *link= sock->link;
1929                                 /* this is the test for a cyclic case */
1930                                 if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF) {
1931                                         if(link->fromnode->need_exec) {
1932                                                 node->need_exec= 1;
1933                                                 break;
1934                                         }
1935                                 }
1936                                 else {
1937                                         node->need_exec= 0;
1938                                         printf("Node %s skipped, cyclic dependency\n", node->name);
1939                                 }
1940                         }
1941                 }
1942                 
1943                 if(node->need_exec) {
1944                         
1945                         /* free output buffers */
1946                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
1947                                 if(nsout[a]->data) {
1948                                         free_compbuf(nsout[a]->data);
1949                                         nsout[a]->data= NULL;
1950                                 }
1951                         }
1952                         totnode++;
1953                         /* printf("node needs exec %s\n", node->name); */
1954                         
1955                         /* tag for getExecutableNode() */
1956                         node->exec= 0;
1957                 }
1958                 else {
1959                         /* tag for getExecutableNode() */
1960                         node->exec= NODE_READY|NODE_FINISHED;
1961                         
1962                 }
1963         }
1964         
1965         /* last step: set the stack values for only-value nodes */
1966         /* just does all now, compared to a full buffer exec this is nothing */
1967         if(totnode) {
1968                 for(node= ntree->nodes.first; node; node= node->next) {
1969                         if(node->need_exec==0 && node_only_value(node)) {
1970                                 if(node->typeinfo->execfunc) {
1971                                         node_get_stack(node, thd->stack, nsin, nsout);
1972                                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
1973                                 }
1974                         }
1975                 }
1976         }
1977         
1978         return totnode;
1979 }
1980
1981 /* while executing tree, free buffers from nodes that are not needed anymore */
1982 static void freeExecutableNode(bNodeTree *ntree)
1983 {
1984         /* node outputs can be freed when:
1985         - not a render result or image node
1986         - when node outputs go to nodes all being set NODE_FINISHED
1987         */
1988         bNode *node;
1989         bNodeSocket *sock;
1990         
1991         /* set exec flag for finished nodes that might need freed */
1992         for(node= ntree->nodes.first; node; node= node->next) {
1993                 if(node->type!=CMP_NODE_R_LAYERS)
1994                         if(node->exec & NODE_FINISHED)
1995                                 node->exec |= NODE_FREEBUFS;
1996         }
1997         /* clear this flag for input links that are not done yet */
1998         for(node= ntree->nodes.first; node; node= node->next) {
1999                 if((node->exec & NODE_FINISHED)==0) {
2000                         for(sock= node->inputs.first; sock; sock= sock->next)
2001                                 if(sock->link)
2002                                         sock->link->fromnode->exec &= ~NODE_FREEBUFS;
2003                 }
2004         }
2005         /* now we can free buffers */
2006         for(node= ntree->nodes.first; node; node= node->next) {
2007                 if(node->exec & NODE_FREEBUFS) {
2008                         for(sock= node->outputs.first; sock; sock= sock->next) {
2009                                 bNodeStack *ns= ntree->stack[0] + sock->stack_index;
2010                                 if(ns->data) {
2011                                         free_compbuf(ns->data);
2012                                         ns->data= NULL;
2013                                         // printf("freed buf node %s \n", node->name);
2014                                 }
2015                         }
2016                 }
2017         }
2018 }
2019
2020 static bNode *getExecutableNode(bNodeTree *ntree)
2021 {
2022         bNode *node;
2023         bNodeSocket *sock;
2024         
2025         for(node= ntree->nodes.first; node; node= node->next) {
2026                 if(node->exec==0) {
2027                         
2028                         /* input sockets should be ready */
2029                         for(sock= node->inputs.first; sock; sock= sock->next) {
2030                                 if(sock->link)
2031                                         if((sock->link->fromnode->exec & NODE_READY)==0)
2032                                                 break;
2033                         }
2034                         if(sock==NULL)
2035                                 return node;
2036                 }
2037         }
2038         return NULL;
2039 }
2040
2041
2042 /* optimized tree execute test for compositing */
2043 void ntreeCompositExecTree(bNodeTree *ntree, RenderData *rd, int do_preview)
2044 {
2045         bNode *node;
2046         ListBase threads;
2047         ThreadData thdata;
2048         int totnode, rendering= 1;
2049         
2050         if(ntree==NULL) return;
2051         
2052         if(do_preview)
2053                 ntreeInitPreview(ntree, 0, 0);
2054         
2055         ntreeBeginExecTree(ntree);
2056         
2057         /* prevent unlucky accidents */
2058         if(G.background)
2059                 rd->scemode &= ~R_COMP_CROP;
2060         
2061         /* setup callerdata for thread callback */
2062         thdata.rd= rd;
2063         thdata.stack= ntree->stack[0];
2064         
2065         /* fixed seed, for example noise texture */
2066         BLI_srandom(rd->cfra);
2067
2068         /* sets need_exec tags in nodes */
2069         totnode= setExecutableNodes(ntree, &thdata);
2070         
2071         BLI_init_threads(&threads, exec_composite_node, rd->threads);
2072         
2073         while(rendering) {
2074                 
2075                 if(BLI_available_threads(&threads)) {
2076                         node= getExecutableNode(ntree);
2077                         if(node) {
2078
2079                                 if(ntree->timecursor)
2080                                         ntree->timecursor(totnode);
2081                                 if(ntree->stats_draw) {
2082                                         char str[64];
2083                                         sprintf(str, "Compositing %d %s", totnode, node->name);
2084                                         ntree->stats_draw(str);
2085                                 }
2086                                 totnode--;
2087                                 
2088                                 node->new_node = (bNode *)&thdata;
2089                                 node->exec= NODE_PROCESSING;
2090                                 BLI_insert_thread(&threads, node);
2091                         }
2092                         else
2093                                 PIL_sleep_ms(50);
2094                 }
2095                 else
2096                         PIL_sleep_ms(50);
2097                 
2098                 rendering= 0;
2099                 /* test for ESC */
2100                 if(ntree->test_break && ntree->test_break()) {
2101                         for(node= ntree->nodes.first; node; node= node->next)
2102                                 node->exec |= NODE_READY;
2103                 }
2104                 
2105                 /* check for ready ones, and if we need to continue */
2106                 for(node= ntree->nodes.first; node; node= node->next) {
2107                         if(node->exec & NODE_READY) {
2108                                 if((node->exec & NODE_FINISHED)==0) {
2109                                         BLI_remove_thread(&threads, node); /* this waits for running thread to finish btw */
2110                                         node->exec |= NODE_FINISHED;
2111                                         
2112                                         /* freeing unused buffers */
2113                                         if(rd->scemode & R_COMP_FREE)
2114                                                 freeExecutableNode(ntree);
2115                                 }
2116                         }
2117                         else rendering= 1;
2118                 }
2119         }
2120         
2121         
2122         BLI_end_threads(&threads);
2123         
2124         ntreeEndExecTree(ntree);
2125 }
2126
2127
2128 /* **************** call to switch lamploop for material node ************ */
2129
2130 void (*node_shader_lamp_loop)(struct ShadeInput *, struct ShadeResult *);
2131
2132 void set_node_shader_lamp_loop(void (*lamp_loop_func)(ShadeInput *, ShadeResult *))
2133 {
2134    node_shader_lamp_loop= lamp_loop_func;
2135 }
2136
2137 /* clumsy checking... should do dynamic outputs once */
2138 static void force_hidden_passes(bNode *node, int passflag)
2139 {
2140    bNodeSocket *sock;
2141
2142    for(sock= node->outputs.first; sock; sock= sock->next)
2143       sock->flag &= ~SOCK_UNAVAIL;
2144
2145    sock= BLI_findlink(&node->outputs, RRES_OUT_Z);
2146    if(!(passflag & SCE_PASS_Z)) sock->flag |= SOCK_UNAVAIL;
2147    sock= BLI_findlink(&node->outputs, RRES_OUT_NORMAL);
2148    if(!(passflag & SCE_PASS_NORMAL)) sock->flag |= SOCK_UNAVAIL;
2149    sock= BLI_findlink(&node->outputs, RRES_OUT_VEC);
2150    if(!(passflag & SCE_PASS_VECTOR)) sock->flag |= SOCK_UNAVAIL;
2151    sock= BLI_findlink(&node->outputs, RRES_OUT_UV);
2152    if(!(passflag & SCE_PASS_UV)) sock->flag |= SOCK_UNAVAIL;
2153    sock= BLI_findlink(&node->outputs, RRES_OUT_RGBA);
2154    if(!(passflag & SCE_PASS_RGBA)) sock->flag |= SOCK_UNAVAIL;
2155    sock= BLI_findlink(&node->outputs, RRES_OUT_DIFF);
2156    if(!(passflag & SCE_PASS_DIFFUSE)) sock->flag |= SOCK_UNAVAIL;
2157    sock= BLI_findlink(&node->outputs, RRES_OUT_SPEC);
2158    if(!(passflag & SCE_PASS_SPEC)) sock->flag |= SOCK_UNAVAIL;
2159    sock= BLI_findlink(&node->outputs, RRES_OUT_SHADOW);
2160    if(!(passflag & SCE_PASS_SHADOW)) sock->flag |= SOCK_UNAVAIL;
2161    sock= BLI_findlink(&node->outputs, RRES_OUT_AO);
2162    if(!(passflag & SCE_PASS_AO)) sock->flag |= SOCK_UNAVAIL;
2163    sock= BLI_findlink(&node->outputs, RRES_OUT_REFLECT);
2164    if(!(passflag & SCE_PASS_REFLECT)) sock->flag |= SOCK_UNAVAIL;
2165    sock= BLI_findlink(&node->outputs, RRES_OUT_REFRACT);
2166    if(!(passflag & SCE_PASS_REFRACT)) sock->flag |= SOCK_UNAVAIL;
2167    sock= BLI_findlink(&node->outputs, RRES_OUT_RADIO);
2168    if(!(passflag & SCE_PASS_RADIO)) sock->flag |= SOCK_UNAVAIL;
2169    sock= BLI_findlink(&node->outputs, RRES_OUT_INDEXOB);
2170    if(!(passflag & SCE_PASS_INDEXOB)) sock->flag |= SOCK_UNAVAIL;
2171
2172 }
2173
2174 /* based on rules, force sockets hidden always */
2175 void ntreeCompositForceHidden(bNodeTree *ntree)
2176 {
2177    bNode *node;
2178
2179    if(ntree==NULL) return;
2180
2181    for(node= ntree->nodes.first; node; node= node->next) {
2182       if( node->type==CMP_NODE_R_LAYERS) {
2183          Scene *sce= node->id?(Scene *)node->id:G.scene; /* G.scene is WEAK! */
2184          SceneRenderLayer *srl= BLI_findlink(&sce->r.layers, node->custom1);
2185          if(srl)
2186             force_hidden_passes(node, srl->passflag);
2187       }
2188       else if( node->type==CMP_NODE_IMAGE) {
2189          Image *ima= (Image *)node->id;
2190          if(ima) {
2191             if(ima->rr) {
2192                ImageUser *iuser= node->storage;
2193                RenderLayer *rl= BLI_findlink(&ima->rr->layers, iuser->layer);
2194                if(rl)
2195                   force_hidden_passes(node, rl->passflag);
2196                else
2197                   force_hidden_passes(node, 0);
2198             }
2199             else if(ima->type!=IMA_TYPE_MULTILAYER) {   /* if ->rr not yet read we keep inputs */
2200                force_hidden_passes(node, RRES_OUT_Z);
2201             }
2202          }
2203          else
2204             force_hidden_passes(node, 0);
2205       }
2206    }
2207
2208 }
2209
2210 /* called from render pipeline, to tag render input and output */
2211 /* need to do all scenes, to prevent errors when you re-render 1 scene */
2212 void ntreeCompositTagRender(Scene *curscene)
2213 {
2214    Scene *sce;
2215
2216    for(sce= G.main->scene.first; sce; sce= sce->id.next) {
2217       if(sce->nodetree) {
2218          bNode *node;
2219
2220          for(node= sce->nodetree->nodes.first; node; node= node->next) {
2221             if(node->id==(ID *)curscene || node->type==CMP_NODE_COMPOSITE)
2222                NodeTagChanged(sce->nodetree, node);
2223          }
2224       }
2225    }
2226 }
2227
2228 /* tags nodes that have animation capabilities */
2229 int ntreeCompositTagAnimated(bNodeTree *ntree)
2230 {
2231    bNode *node;
2232    int tagged= 0;
2233
2234    if(ntree==NULL) return 0;
2235
2236    for(node= ntree->nodes.first; node; node= node->next) {
2237       if(node->type==CMP_NODE_IMAGE) {
2238          Image *ima= (Image *)node->id;
2239          if(ima && ELEM(ima->source, IMA_SRC_MOVIE, IMA_SRC_SEQUENCE)) {
2240             NodeTagChanged(ntree, node);
2241             tagged= 1;
2242          }
2243       }
2244       else if(node->type==CMP_NODE_TIME) {
2245          NodeTagChanged(ntree, node);
2246          tagged= 1;
2247       }
2248       else if(node->type==CMP_NODE_R_LAYERS) {
2249          NodeTagChanged(ntree, node);
2250          tagged= 1;
2251       }
2252       else if(node->type==NODE_GROUP) {
2253          if( ntreeCompositTagAnimated((bNodeTree *)node->id) ) {
2254             NodeTagChanged(ntree, node);
2255          }
2256       }
2257    }
2258
2259    return tagged;
2260 }
2261
2262
2263 /* called from image window preview */
2264 void ntreeCompositTagGenerators(bNodeTree *ntree)
2265 {
2266    bNode *node;
2267
2268    if(ntree==NULL) return;
2269
2270    for(node= ntree->nodes.first; node; node= node->next) {
2271       if( ELEM(node->type, CMP_NODE_R_LAYERS, CMP_NODE_IMAGE))
2272          NodeTagChanged(ntree, node);
2273    }
2274 }
2275
2276 /* ************* node definition init ********** */
2277
2278 static bNodeType *is_nodetype_registered(ListBase *typelist, int type) 
2279 {
2280         bNodeType *ntype= typelist->first;
2281         
2282         for(;ntype; ntype= ntype->next )
2283                 if(ntype->type==type)
2284                         return ntype;
2285         
2286         return NULL;
2287 }
2288
2289 /* type can be from a static array, we make copy for duplicate types (like group) */
2290 void nodeRegisterType(ListBase *typelist, const bNodeType *ntype) 
2291 {
2292         bNodeType *found= is_nodetype_registered(typelist, ntype->type);
2293         
2294         if(found==NULL) {
2295                 bNodeType *ntypen= MEM_mallocN(sizeof(bNodeType), "node type");
2296                 *ntypen= *ntype;
2297                 BLI_addtail(typelist, ntypen);
2298         }
2299 }
2300
2301 static void registerCompositNodes(ListBase *ntypelist)
2302 {
2303         nodeRegisterType(ntypelist, &node_group_typeinfo);
2304         nodeRegisterType(ntypelist, &cmp_node_rlayers);
2305         nodeRegisterType(ntypelist, &cmp_node_image);
2306         nodeRegisterType(ntypelist, &cmp_node_texture);
2307         nodeRegisterType(ntypelist, &cmp_node_value);
2308         nodeRegisterType(ntypelist, &cmp_node_rgb);
2309         nodeRegisterType(ntypelist, &cmp_node_curve_time);
2310         
2311         nodeRegisterType(ntypelist, &cmp_node_composite);
2312         nodeRegisterType(ntypelist, &cmp_node_viewer);
2313         nodeRegisterType(ntypelist, &cmp_node_splitviewer);
2314         nodeRegisterType(ntypelist, &cmp_node_output_file);
2315         
2316         nodeRegisterType(ntypelist, &cmp_node_curve_rgb);
2317         nodeRegisterType(ntypelist, &cmp_node_mix_rgb);
2318         nodeRegisterType(ntypelist, &cmp_node_hue_sat);
2319         nodeRegisterType(ntypelist, &cmp_node_alphaover);
2320         nodeRegisterType(ntypelist, &cmp_node_zcombine);
2321         
2322         nodeRegisterType(ntypelist, &cmp_node_normal);
2323         nodeRegisterType(ntypelist, &cmp_node_curve_vec);
2324         nodeRegisterType(ntypelist, &cmp_node_map_value);
2325
2326         nodeRegisterType(ntypelist, &cmp_node_filter);
2327         nodeRegisterType(ntypelist, &cmp_node_blur);
2328         nodeRegisterType(ntypelist, &cmp_node_vecblur);
2329         nodeRegisterType(ntypelist, &cmp_node_dilateerode);
2330         nodeRegisterType(ntypelist, &cmp_node_defocus);
2331
2332         nodeRegisterType(ntypelist, &cmp_node_valtorgb);
2333         nodeRegisterType(ntypelist, &cmp_node_rgbtobw);
2334         nodeRegisterType(ntypelist, &cmp_node_setalpha);
2335         nodeRegisterType(ntypelist, &cmp_node_idmask);
2336         nodeRegisterType(ntypelist, &cmp_node_math);
2337         nodeRegisterType(ntypelist, &cmp_node_seprgba);
2338         nodeRegisterType(ntypelist, &cmp_node_combrgba);
2339         nodeRegisterType(ntypelist, &cmp_node_sephsva);
2340         nodeRegisterType(ntypelist, &cmp_node_combhsva);
2341         nodeRegisterType(ntypelist, &cmp_node_sepyuva);
2342         nodeRegisterType(ntypelist, &cmp_node_combyuva);
2343         nodeRegisterType(ntypelist, &cmp_node_sepycca);
2344         nodeRegisterType(ntypelist, &cmp_node_combycca);
2345                 
2346         nodeRegisterType(ntypelist, &cmp_node_diff_matte);
2347         nodeRegisterType(ntypelist, &cmp_node_chroma);
2348         nodeRegisterType(ntypelist, &cmp_node_channel_matte);
2349         nodeRegisterType(ntypelist, &cmp_node_color_spill);
2350         nodeRegisterType(ntypelist, &cmp_node_luma_matte);
2351         
2352         nodeRegisterType(ntypelist, &cmp_node_translate);
2353         nodeRegisterType(ntypelist, &cmp_node_rotate);
2354         nodeRegisterType(ntypelist, &cmp_node_scale);
2355         nodeRegisterType(ntypelist, &cmp_node_flip);
2356         nodeRegisterType(ntypelist, &cmp_node_displace);
2357         nodeRegisterType(ntypelist, &cmp_node_mapuv);
2358 }
2359
2360 static void registerShaderNodes(ListBase *ntypelist) 
2361 {
2362         nodeRegisterType(ntypelist, &node_group_typeinfo);
2363         nodeRegisterType(ntypelist, &sh_node_output);
2364         nodeRegisterType(ntypelist, &sh_node_mix_rgb);
2365         nodeRegisterType(ntypelist, &sh_node_valtorgb);
2366         nodeRegisterType(ntypelist, &sh_node_rgbtobw);
2367         nodeRegisterType(ntypelist, &sh_node_normal);
2368         nodeRegisterType(ntypelist, &sh_node_geom);
2369         nodeRegisterType(ntypelist, &sh_node_mapping);
2370         nodeRegisterType(ntypelist, &sh_node_curve_vec);
2371         nodeRegisterType(ntypelist, &sh_node_curve_rgb);
2372         nodeRegisterType(ntypelist, &sh_node_math);
2373         nodeRegisterType(ntypelist, &sh_node_vect_math);
2374         nodeRegisterType(ntypelist, &sh_node_squeeze);
2375         nodeRegisterType(ntypelist, &sh_node_camera);
2376         nodeRegisterType(ntypelist, &sh_node_material);
2377         nodeRegisterType(ntypelist, &sh_node_value);
2378         nodeRegisterType(ntypelist, &sh_node_rgb);
2379         nodeRegisterType(ntypelist, &sh_node_texture);
2380 }
2381
2382 void init_nodesystem(void) 
2383 {
2384         registerCompositNodes(&node_all_composit);
2385         registerShaderNodes(&node_all_shaders);
2386 }
2387
2388 void free_nodesystem(void) 
2389 {
2390         BLI_freelistN(&node_all_composit);
2391         BLI_freelistN(&node_all_shaders);
2392 }
2393
2394