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