Final merge of HEAD (bf-blender) into the orange branch.
[blender.git] / source / blender / blenkernel / intern / node.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. 
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2005 Blender Foundation.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 #include <stdlib.h>
31 #include <string.h>
32
33 #include "DNA_ID.h"
34 #include "DNA_node_types.h"
35 #include "DNA_material_types.h"
36 #include "DNA_scene_types.h"
37
38 #include "BKE_blender.h"
39 #include "BKE_colortools.h"
40 #include "BKE_global.h"
41 #include "BKE_image.h"
42 #include "BKE_library.h"
43 #include "BKE_main.h"
44 #include "BKE_node.h"
45 #include "BKE_texture.h"
46 #include "BKE_utildefines.h"
47
48 #include "BLI_arithb.h"
49 #include "BLI_blenlib.h"
50
51 #include "MEM_guardedalloc.h"
52 #include "IMB_imbuf.h"
53
54 /* not very important, but the stack solver likes to know a maximum */
55 #define MAX_SOCKET      64
56
57 #pragma mark /* ************** Type stuff **********  */
58
59 static bNodeType *node_get_type(bNodeTree *ntree, int type, bNodeTree *ngroup)
60 {
61         if(type==NODE_GROUP) {
62                 if(ngroup && GS(ngroup->id.name)==ID_NT) {
63                         return ngroup->owntype;
64                 }
65                 return NULL;
66         }
67         else {
68                 bNodeType **typedefs= ntree->alltypes;
69                 
70                 while( *typedefs && (*typedefs)->type!=type)
71                         typedefs++;
72                 
73                 return *typedefs;
74         }
75 }
76
77 void ntreeInitTypes(bNodeTree *ntree)
78 {
79         bNode *node, *next;
80         
81         if(ntree->type==NTREE_SHADER)
82                 ntree->alltypes= node_all_shaders;
83         else if(ntree->type==NTREE_COMPOSIT)
84                 ntree->alltypes= node_all_composit;
85         else {
86                 ntree->alltypes= NULL;
87                 printf("Error: no type definitions for nodes\n");
88         }
89         
90         for(node= ntree->nodes.first; node; node= next) {
91                 next= node->next;
92                 node->typeinfo= node_get_type(ntree, node->type, (bNodeTree *)node->id);
93                 if(node->typeinfo==NULL) {
94                         printf("Error: Node type %s doesn't exist anymore, removed\n", node->name);
95                         nodeFreeNode(ntree, node);
96                 }
97         }
98                         
99         ntree->init |= NTREE_TYPE_INIT;
100 }
101
102 /* only used internal... we depend on type definitions! */
103 static bNodeSocket *node_add_socket_type(ListBase *lb, bNodeSocketType *stype)
104 {
105         bNodeSocket *sock= MEM_callocN(sizeof(bNodeSocket), "sock");
106         
107         BLI_strncpy(sock->name, stype->name, NODE_MAXSTR);
108         if(stype->limit==0) sock->limit= 0xFFF;
109         else sock->limit= stype->limit;
110         sock->type= stype->type;
111         
112         sock->to_index= stype->own_index;
113         sock->tosock= stype->internsock;
114         
115         sock->ns.vec[0]= stype->val1;
116         sock->ns.vec[1]= stype->val2;
117         sock->ns.vec[2]= stype->val3;
118         sock->ns.vec[3]= stype->val4;
119                                 
120         if(lb)
121                 BLI_addtail(lb, sock);
122         
123         return sock;
124 }
125
126 static void node_rem_socket(bNodeTree *ntree, ListBase *lb, bNodeSocket *sock)
127 {
128         bNodeLink *link, *next;
129         
130         for(link= ntree->links.first; link; link= next) {
131                 next= link->next;
132                 if(link->fromsock==sock || link->tosock==sock) {
133                         nodeRemLink(ntree, link);
134                 }
135         }
136         
137         BLI_remlink(lb, sock);
138         MEM_freeN(sock);
139 }
140
141 static bNodeSocket *verify_socket(ListBase *lb, bNodeSocketType *stype)
142 {
143         bNodeSocket *sock;
144         
145         for(sock= lb->first; sock; sock= sock->next) {
146                 /* both indices are zero for non-groups, otherwise it's a unique index */
147                 if(sock->to_index==stype->own_index)
148                         if(strncmp(sock->name, stype->name, NODE_MAXSTR)==0)
149                                 break;
150         }
151         if(sock) {
152                 sock->type= stype->type;                /* in future, read this from tydefs! */
153                 if(stype->limit==0) sock->limit= 0xFFF;
154                 else sock->limit= stype->limit;
155                 sock->tosock= stype->internsock;
156                 
157                 BLI_remlink(lb, sock);
158                 
159                 return sock;
160         }
161         else {
162                 return node_add_socket_type(NULL, stype);
163         }
164 }
165
166 static void verify_socket_list(bNodeTree *ntree, ListBase *lb, bNodeSocketType *stype_first)
167 {
168         bNodeSocketType *stype;
169         
170         /* no inputs anymore? */
171         if(stype_first==NULL) {
172                 while(lb->first)
173                         node_rem_socket(ntree, lb, lb->first);
174         }
175         else {
176                 /* step by step compare */
177                 stype= stype_first;
178                 while(stype->type != -1) {
179                         stype->sock= verify_socket(lb, stype);
180                         stype++;
181                 }
182                 /* leftovers are removed */
183                 while(lb->first)
184                         node_rem_socket(ntree, lb, lb->first);
185                 /* and we put back the verified sockets */
186                 stype= stype_first;
187                 while(stype->type != -1) {
188                         BLI_addtail(lb, stype->sock);
189                         stype++;
190                 }
191         }
192 }
193
194 void nodeVerifyType(bNodeTree *ntree, bNode *node)
195 {
196         bNodeType *ntype= node->typeinfo;
197         
198         if(ntype) {
199                 /* might add some other verify stuff here */
200                 
201                 verify_socket_list(ntree, &node->inputs, ntype->inputs);
202                 verify_socket_list(ntree, &node->outputs, ntype->outputs);
203         }
204 }
205
206 void ntreeVerifyTypes(bNodeTree *ntree)
207 {
208         bNode *node;
209         
210         if((ntree->init & NTREE_TYPE_INIT)==0)
211                 ntreeInitTypes(ntree);
212         
213         /* check inputs and outputs, and remove or insert them */
214         for(node= ntree->nodes.first; node; node= node->next)
215                 nodeVerifyType(ntree, node);
216         
217 }
218
219 #pragma mark /* ************** Group stuff ********** */
220
221 bNodeType node_group_typeinfo= {
222         /* type code   */       NODE_GROUP,
223         /* name        */       "Group",
224         /* width+range */       120, 60, 200,
225         /* class+opts  */       NODE_CLASS_GROUP, NODE_OPTIONS,
226         /* input sock  */       NULL,
227         /* output sock */       NULL,
228         /* storage     */       "",
229         /* execfunc    */       NULL,
230         
231 };
232
233 /* tag internal sockets */
234 static void group_tag_internal_sockets(bNodeTree *ngroup)
235 {
236         bNode *node;
237         bNodeSocket *sock;
238         bNodeLink *link;
239         
240         /* clear intern tag, but check already for hidden sockets */
241         for(node= ngroup->nodes.first; node; node= node->next) {
242                 for(sock= node->inputs.first; sock; sock= sock->next)
243                         sock->intern= sock->flag & SOCK_HIDDEN;
244                 for(sock= node->outputs.first; sock; sock= sock->next)
245                         sock->intern= sock->flag & SOCK_HIDDEN;
246         }
247         /* set tag */
248         for(link= ngroup->links.first; link; link= link->next) {
249                 link->fromsock->intern= 1;
250                 link->tosock->intern= 1;
251         }
252         
253         /* remove link pointer to external links (only happens on create group) */
254         for(node= ngroup->nodes.first; node; node= node->next) {
255                 for(sock= node->inputs.first; sock; sock= sock->next)
256                         if(sock->intern==0)
257                                 sock->link= NULL;
258         }
259
260         /* set all intern sockets to own_index zero, makes sure that later use won't mixup */
261         for(node= ngroup->nodes.first; node; node= node->next) {
262                 for(sock= node->inputs.first; sock; sock= sock->next)
263                         if(sock->intern)
264                                 sock->own_index= 0;
265                 for(sock= node->outputs.first; sock; sock= sock->next)
266                         if(sock->intern)
267                                 sock->own_index= 0;
268         }
269 }
270
271 /* after editing group, new sockets are zero */
272 /* this routine ensures unique identifiers for zero sockets that are exposed */
273 static void group_verify_own_indices(bNodeTree *ngroup)
274 {
275         bNode *node;
276         bNodeSocket *sock;
277         
278         for(node= ngroup->nodes.first; node; node= node->next) {
279                 for(sock= node->inputs.first; sock; sock= sock->next)
280                         if(sock->own_index==0 && sock->intern==0)
281                                 sock->own_index= ++(ngroup->cur_index);
282                 for(sock= node->outputs.first; sock; sock= sock->next)
283                         if(sock->own_index==0 && sock->intern==0)
284                                 sock->own_index= ++(ngroup->cur_index);
285         }
286 //      printf("internal index %d\n", ngroup->cur_index);
287 }
288
289
290 /* nodetrees can be used as groups, so we need typeinfo structs generated */
291 void ntreeMakeOwnType(bNodeTree *ngroup)
292 {
293         bNode *node;
294         bNodeSocket *sock;
295         int totin= 0, totout=0, a;
296
297         /* tags socket when internal linked */
298         group_tag_internal_sockets(ngroup);
299         
300         /* ensure all sockets have own unique id */
301         group_verify_own_indices(ngroup);
302         
303         /* counting stats */
304         for(node= ngroup->nodes.first; node; node= node->next) {
305                 if(node->type==NODE_GROUP)
306                         break;
307                 for(sock= node->inputs.first; sock; sock= sock->next)
308                         if(sock->intern==0) 
309                                 totin++;
310                 for(sock= node->outputs.first; sock; sock= sock->next)
311                         if(sock->intern==0) 
312                                 totout++;
313         }
314         /* debug: nodetrees in nodetrees not handled yet */
315         if(node) {
316                 printf("group in group, not supported yet\n");
317                 return;
318         }
319         
320         /* free own type struct */
321         if(ngroup->owntype) {
322                 if(ngroup->owntype->inputs)
323                         MEM_freeN(ngroup->owntype->inputs);
324                 if(ngroup->owntype->outputs)
325                         MEM_freeN(ngroup->owntype->outputs);
326                 MEM_freeN(ngroup->owntype);
327         }
328         
329         /* make own type struct */
330         ngroup->owntype= MEM_mallocN(sizeof(bNodeType), "group type");
331         *ngroup->owntype= node_group_typeinfo;
332         
333         /* input type arrays */
334         if(totin) {
335                 bNodeSocketType *stype;
336                 bNodeSocketType *inputs= MEM_mallocN(sizeof(bNodeSocketType)*(totin+1), "bNodeSocketType");
337                 a= 0;
338                 
339                 for(node= ngroup->nodes.first; node; node= node->next) {
340                         /* nodes are presumed fully verified, stype and socket list are in sync */
341                         stype= node->typeinfo->inputs;
342                         for(sock= node->inputs.first; sock; sock= sock->next, stype++) {
343                                 if(sock->intern==0) {
344                                         /* debug only print */
345                                         if(stype==NULL || stype->type==-1) printf("group verification error %s\n", ngroup->id.name);
346                                         
347                                         inputs[a]= *stype;
348                                         inputs[a].own_index= sock->own_index;
349                                         inputs[a].internsock= sock;     
350                                         a++;
351                                 }
352                         }
353                 }
354                 inputs[a].type= -1;     /* terminator code */
355                 ngroup->owntype->inputs= inputs;
356         }       
357         
358         /* output type arrays */
359         if(totout) {
360                 bNodeSocketType *stype;
361                 bNodeSocketType *outputs= MEM_mallocN(sizeof(bNodeSocketType)*(totout+1), "bNodeSocketType");
362                 a= 0;
363                 
364                 for(node= ngroup->nodes.first; node; node= node->next) {
365                         /* nodes are presumed fully verified, stype and socket list are in sync */
366                         stype= node->typeinfo->outputs;
367                         for(sock= node->outputs.first; sock; sock= sock->next, stype++) {
368                                 if(sock->intern==0) {
369                                         /* debug only print */
370                                         if(stype==NULL || stype->type==-1) printf("group verification error %s\n", ngroup->id.name);
371                                         
372                                         outputs[a]= *stype;
373                                         outputs[a].own_index= sock->own_index;
374                                         outputs[a].internsock= sock;    
375                                         a++;
376                                 }
377                         }
378                 }
379                 outputs[a].type= -1;    /* terminator code */
380                 ngroup->owntype->outputs= outputs;
381         }
382         
383         /* voila, the nodetree has the full definition for generating group-node instances! */
384 }
385
386
387 static bNodeSocket *groupnode_find_tosock(bNode *gnode, int index)
388 {
389         bNodeSocket *sock;
390         
391         for(sock= gnode->inputs.first; sock; sock= sock->next)
392                 if(sock->to_index==index)
393                         return sock;
394         return NULL;
395 }
396
397 static bNodeSocket *groupnode_find_fromsock(bNode *gnode, int index)
398 {
399         bNodeSocket *sock;
400         
401         for(sock= gnode->outputs.first; sock; sock= sock->next)
402                 if(sock->to_index==index)
403                         return sock;
404         return NULL;
405 }
406
407 bNode *nodeMakeGroupFromSelected(bNodeTree *ntree)
408 {
409         bNodeLink *link, *linkn;
410         bNode *node, *gnode, *nextn;
411         bNodeTree *ngroup;
412         float min[2], max[2];
413         int totnode=0;
414         
415         INIT_MINMAX2(min, max);
416         
417         /* is there something to group? also do some clearing */
418         for(node= ntree->nodes.first; node; node= node->next) {
419                 if(node->flag & NODE_SELECT) {
420                         /* no groups in groups */
421                         if(node->type==NODE_GROUP)
422                                 return NULL;
423                         DO_MINMAX2( (&node->locx), min, max);
424                         totnode++;
425                 }
426                 node->done= 0;
427         }
428         if(totnode==0) return NULL;
429         
430         /* check if all connections are OK, no unselected node has both
431                 inputs and outputs to a selection */
432         for(link= ntree->links.first; link; link= link->next) {
433                 if(link->fromnode->flag & NODE_SELECT)
434                         link->tonode->done |= 1;
435                 if(link->tonode->flag & NODE_SELECT)
436                         link->fromnode->done |= 2;
437         }       
438         
439         for(node= ntree->nodes.first; node; node= node->next) {
440                 if((node->flag & NODE_SELECT)==0)
441                         if(node->done==3)
442                                 break;
443         }
444         if(node) 
445                 return NULL;
446         
447         /* OK! new nodetree */
448         ngroup= alloc_libblock(&G.main->nodetree, ID_NT, "NodeGroup");
449         ngroup->type= ntree->type;
450         ngroup->alltypes= ntree->alltypes;
451         
452         /* move nodes over */
453         for(node= ntree->nodes.first; node; node= nextn) {
454                 nextn= node->next;
455                 if(node->flag & NODE_SELECT) {
456                         BLI_remlink(&ntree->nodes, node);
457                         BLI_addtail(&ngroup->nodes, node);
458                         node->locx-= 0.5f*(min[0]+max[0]);
459                         node->locy-= 0.5f*(min[1]+max[1]);
460                 }
461         }
462
463         /* move links over */
464         for(link= ntree->links.first; link; link= linkn) {
465                 linkn= link->next;
466                 if(link->fromnode->flag & link->tonode->flag & NODE_SELECT) {
467                         BLI_remlink(&ntree->links, link);
468                         BLI_addtail(&ngroup->links, link);
469                 }
470         }
471         
472         /* now we can make own group typeinfo */
473         ntreeMakeOwnType(ngroup);
474         
475         /* make group node */
476         gnode= nodeAddNodeType(ntree, NODE_GROUP, ngroup);
477         gnode->locx= 0.5f*(min[0]+max[0]);
478         gnode->locy= 0.5f*(min[1]+max[1]);
479         
480         /* relink external sockets */
481         for(link= ntree->links.first; link; link= link->next) {
482                 if(link->tonode->flag & NODE_SELECT) {
483                         link->tonode= gnode;
484                         link->tosock= groupnode_find_tosock(gnode, link->tosock->own_index);
485                         if(link->tosock==NULL) printf("Bad!\n");
486                 }
487                 else if(link->fromnode->flag & NODE_SELECT) {
488                         link->fromnode= gnode;
489                         link->fromsock= groupnode_find_fromsock(gnode, link->fromsock->own_index);
490                         if(link->fromsock==NULL) printf("Bad!\n");
491                 }
492         }
493         
494         return gnode;
495 }
496
497 /* note: ungroup: group_indices zero! */
498
499 /* here's a nasty little one, need to check users... */
500 /* should become callbackable... */
501 void nodeVerifyGroup(bNodeTree *ngroup)
502 {
503         
504         /* group changed, so we rebuild the type definition */
505         ntreeMakeOwnType(ngroup);
506         
507         if(ngroup->type==NTREE_SHADER) {
508                 Material *ma;
509                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
510                         if(ma->nodetree) {
511                                 bNode *node;
512                                 
513                                 /* find if group is in tree */
514                                 for(node= ma->nodetree->nodes.first; node; node= node->next)
515                                         if(node->id == (ID *)ngroup)
516                                                 break;
517                                 
518                                 if(node) {
519                                         /* set all type pointers OK */
520                                         ntreeInitTypes(ma->nodetree);
521                                         
522                                         for(node= ma->nodetree->nodes.first; node; node= node->next)
523                                                 if(node->id == (ID *)ngroup)
524                                                         nodeVerifyType(ma->nodetree, node);
525                                 }
526                         }
527                 }
528         }
529         else if(ngroup->type==NTREE_COMPOSIT) {
530                 Scene *sce;
531                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
532                         if(sce->nodetree) {
533                                 bNode *node;
534                                 
535                                 /* find if group is in tree */
536                                 for(node= sce->nodetree->nodes.first; node; node= node->next)
537                                         if(node->id == (ID *)ngroup)
538                                                 break;
539                                 
540                                 if(node) {
541                                         /* set all type pointers OK */
542                                         ntreeInitTypes(sce->nodetree);
543                                         
544                                         for(node= sce->nodetree->nodes.first; node; node= node->next)
545                                                 if(node->id == (ID *)ngroup)
546                                                         nodeVerifyType(sce->nodetree, node);
547                                 }
548                         }
549                 }
550         }
551 }
552
553 /* also to check all users of groups. Now only used in editor for hide/unhide */
554 /* should become callbackable? */
555 void nodeGroupSocketUseFlags(bNodeTree *ngroup)
556 {
557         bNode *node;
558         bNodeSocket *sock;
559
560         /* clear flags */
561         for(node= ngroup->nodes.first; node; node= node->next) {
562                 for(sock= node->inputs.first; sock; sock= sock->next)
563                         sock->flag &= ~SOCK_IN_USE;
564                 for(sock= node->outputs.first; sock; sock= sock->next)
565                         sock->flag &= ~SOCK_IN_USE;
566         }
567         
568         /* tag all thats in use */
569         if(ngroup->type==NTREE_SHADER) {
570                 Material *ma;
571                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
572                         if(ma->nodetree) {
573                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
574                                         if(node->id==(ID *)ngroup) {
575                                                 for(sock= node->inputs.first; sock; sock= sock->next)
576                                                         if(sock->link)
577                                                                 if(sock->tosock) 
578                                                                         sock->tosock->flag |= SOCK_IN_USE;
579                                                 for(sock= node->outputs.first; sock; sock= sock->next)
580                                                         if(nodeCountSocketLinks(ma->nodetree, sock))
581                                                                 if(sock->tosock) 
582                                                                         sock->tosock->flag |= SOCK_IN_USE;
583                                         }
584                                 }
585                         }
586                 }
587         }
588         else if(ngroup->type==NTREE_COMPOSIT) {
589                 Scene *sce;
590                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
591                         if(sce->nodetree) {
592                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
593                                         if(node->id==(ID *)ngroup) {
594                                                 for(sock= node->inputs.first; sock; sock= sock->next)
595                                                         if(sock->link)
596                                                                 if(sock->tosock) 
597                                                                         sock->tosock->flag |= SOCK_IN_USE;
598                                                 for(sock= node->outputs.first; sock; sock= sock->next)
599                                                         if(nodeCountSocketLinks(sce->nodetree, sock))
600                                                                 if(sock->tosock) 
601                                                                         sock->tosock->flag |= SOCK_IN_USE;
602                                         }
603                                 }
604                         }
605                 }
606         }
607 }
608
609 static void find_node_with_socket(bNodeTree *ntree, bNodeSocket *sock, bNode **nodep, int *sockindex)
610 {
611         bNode *node;
612         bNodeSocket *tsock;
613         int index;
614         
615         for(node= ntree->nodes.first; node; node= node->next) {
616                 for(index=0, tsock= node->inputs.first; tsock; tsock= tsock->next, index++)
617                         if(tsock==sock)
618                                 break;
619                 if(tsock)
620                         break;
621                 for(index=0, tsock= node->outputs.first; tsock; tsock= tsock->next, index++)
622                         if(tsock==sock)
623                                 break;
624                 if(tsock)
625                         break;
626         }
627         if(node) {
628                 *nodep= node;
629                 *sockindex= index;
630         }
631         else {
632                 *nodep= NULL;
633         }
634 }
635
636 /* returns 1 if its OK */
637 int nodeGroupUnGroup(bNodeTree *ntree, bNode *gnode)
638 {
639         bNodeLink *link, *linkn;
640         bNode *node, *nextn;
641         bNodeTree *ngroup, *wgroup;
642         int index;
643         
644         ngroup= (bNodeTree *)gnode->id;
645         if(ngroup==NULL) return 0;
646         
647         /* clear new pointers, set in copytree */
648         for(node= ntree->nodes.first; node; node= node->next)
649                 node->new= NULL;
650
651         wgroup= ntreeCopyTree(ngroup, 0);
652         
653         /* add the nodes into the ntree */
654         for(node= wgroup->nodes.first; node; node= nextn) {
655                 nextn= node->next;
656                 BLI_remlink(&wgroup->nodes, node);
657                 BLI_addtail(&ntree->nodes, node);
658                 node->locx+= gnode->locx;
659                 node->locy+= gnode->locy;
660                 node->flag |= NODE_SELECT;
661         }
662         /* and the internal links */
663         for(link= wgroup->links.first; link; link= linkn) {
664                 linkn= link->next;
665                 BLI_remlink(&wgroup->links, link);
666                 BLI_addtail(&ntree->links, link);
667         }
668
669         /* restore links to and from the gnode */
670         for(link= ntree->links.first; link; link= link->next) {
671                 if(link->tonode==gnode) {
672                         /* link->tosock->tosock is on the node we look for */
673                         find_node_with_socket(ngroup, link->tosock->tosock, &nextn, &index);
674                         if(nextn==NULL) printf("wrong stuff!\n");
675                         else if(nextn->new==NULL) printf("wrong stuff too!\n");
676                         else {
677                                 link->tonode= nextn->new;
678                                 link->tosock= BLI_findlink(&link->tonode->inputs, index);
679                         }
680                 }
681                 else if(link->fromnode==gnode) {
682                         /* link->fromsock->tosock is on the node we look for */
683                         find_node_with_socket(ngroup, link->fromsock->tosock, &nextn, &index);
684                         if(nextn==NULL) printf("1 wrong stuff!\n");
685                         else if(nextn->new==NULL) printf("1 wrong stuff too!\n");
686                         else {
687                                 link->fromnode= nextn->new;
688                                 link->fromsock= BLI_findlink(&link->fromnode->outputs, index);
689                         }
690                 }
691         }
692         
693         /* remove the gnode & work tree */
694         ntreeFreeTree(wgroup);
695         MEM_freeN(wgroup);
696         
697         nodeFreeNode(ntree, gnode);
698         
699         return 1;
700 }
701
702 #pragma mark /* ************** Add stuff ********** */
703
704 bNode *nodeAddNodeType(bNodeTree *ntree, int type, bNodeTree *ngroup)
705 {
706         bNode *node;
707         bNodeType *ntype= node_get_type(ntree, type, ngroup);
708         bNodeSocketType *stype;
709         
710         node= MEM_callocN(sizeof(bNode), "new node");
711         BLI_addtail(&ntree->nodes, node);
712         node->typeinfo= ntype;
713         
714         BLI_strncpy(node->name, ntype->name, NODE_MAXSTR);
715         node->type= ntype->type;
716         node->flag= NODE_SELECT|ntype->flag;
717         node->width= ntype->width;
718         node->miniwidth= 15.0f;         /* small value only, allows print of first chars */
719         
720         if(type==NODE_GROUP)
721                 node->id= (ID *)ngroup;
722         
723         if(ntype->inputs) {
724                 stype= ntype->inputs;
725                 while(stype->type != -1) {
726                         node_add_socket_type(&node->inputs, stype);
727                         stype++;
728                 }
729         }
730         if(ntype->outputs) {
731                 stype= ntype->outputs;
732                 while(stype->type != -1) {
733                         node_add_socket_type(&node->outputs, stype);
734                         stype++;
735                 }
736         }
737         
738         /* need init handler later? */
739         if(ntree->type==NTREE_SHADER) {
740                 if(type==SH_NODE_MATERIAL)
741                         node->custom1= SH_NODE_MAT_DIFF|SH_NODE_MAT_SPEC;
742                 else if(type==SH_NODE_VALTORGB)
743                         node->storage= add_colorband(1);
744                 else if(type==SH_NODE_MAPPING)
745                         node->storage= add_mapping();
746                 else if(type==SH_NODE_CURVE_VEC)
747                         node->storage= curvemapping_add(3, -1.0f, -1.0f, 1.0f, 1.0f);
748                 else if(type==SH_NODE_CURVE_RGB)
749                         node->storage= curvemapping_add(4, 0.0f, 0.0f, 1.0f, 1.0f);
750         }
751         else if(ntree->type==NTREE_COMPOSIT) {
752                 if(type==CMP_NODE_VALTORGB)
753                         node->storage= add_colorband(1);
754                 else if(type==CMP_NODE_CURVE_VEC)
755                         node->storage= curvemapping_add(3, -1.0f, -1.0f, 1.0f, 1.0f);
756                 else if(type==CMP_NODE_CURVE_RGB)
757                         node->storage= curvemapping_add(4, 0.0f, 0.0f, 1.0f, 1.0f);
758                 else if(type==CMP_NODE_MAP_VALUE)
759                         node->storage= add_mapping();
760         }
761         
762         return node;
763 }
764
765 /* keep socket listorder identical, for copying links */
766 /* ntree is the target tree */
767 bNode *nodeCopyNode(struct bNodeTree *ntree, struct bNode *node)
768 {
769         bNode *nnode= MEM_callocN(sizeof(bNode), "dupli node");
770         bNodeSocket *sock;
771
772         *nnode= *node;
773         BLI_addtail(&ntree->nodes, nnode);
774         
775         duplicatelist(&nnode->inputs, &node->inputs);
776         for(sock= nnode->inputs.first; sock; sock= sock->next)
777                 sock->own_index= 0;
778         
779         duplicatelist(&nnode->outputs, &node->outputs);
780         for(sock= nnode->outputs.first; sock; sock= sock->next) {
781                 sock->own_index= 0;
782                 sock->ns.data= NULL;
783         }
784         
785         if(nnode->id)
786                 nnode->id->us++;
787         
788         if(nnode->storage) {
789                 /* another candidate for handlerizing! */
790                 if(ntree->type==NTREE_SHADER) {
791                         if(node->type==SH_NODE_CURVE_VEC || node->type==SH_NODE_CURVE_RGB)
792                                 nnode->storage= curvemapping_copy(node->storage);
793                         else 
794                                 nnode->storage= MEM_dupallocN(nnode->storage);
795                 }
796                 else if(ntree->type==NTREE_COMPOSIT) {
797                         if(node->type==CMP_NODE_CURVE_VEC || node->type==CMP_NODE_CURVE_RGB)
798                                 nnode->storage= curvemapping_copy(node->storage);
799                         else 
800                                 nnode->storage= MEM_dupallocN(nnode->storage);
801                 }
802                 else 
803                         nnode->storage= MEM_dupallocN(nnode->storage);
804         }
805         
806         node->new= nnode;
807         nnode->new= NULL;
808         nnode->preview= NULL;
809         
810         return nnode;
811 }
812
813 bNodeLink *nodeAddLink(bNodeTree *ntree, bNode *fromnode, bNodeSocket *fromsock, bNode *tonode, bNodeSocket *tosock)
814 {
815         bNodeLink *link= MEM_callocN(sizeof(bNodeLink), "link");
816         
817         BLI_addtail(&ntree->links, link);
818         link->fromnode= fromnode;
819         link->fromsock= fromsock;
820         link->tonode= tonode;
821         link->tosock= tosock;
822         
823         return link;
824 }
825
826 void nodeRemLink(bNodeTree *ntree, bNodeLink *link)
827 {
828         BLI_remlink(&ntree->links, link);
829         if(link->tosock)
830                 link->tosock->link= NULL;
831         MEM_freeN(link);
832 }
833
834
835 bNodeTree *ntreeAddTree(int type)
836 {
837         bNodeTree *ntree= MEM_callocN(sizeof(bNodeTree), "new node tree");
838         ntree->type= type;
839         
840         ntreeInitTypes(ntree);
841         return ntree;
842 }
843
844 #pragma mark /* ************** Free stuff ********** */
845
846 /* goes over entire tree */
847 static void node_unlink_node(bNodeTree *ntree, bNode *node)
848 {
849         bNodeLink *link, *next;
850         bNodeSocket *sock;
851         ListBase *lb;
852         
853         for(link= ntree->links.first; link; link= next) {
854                 next= link->next;
855                 
856                 if(link->fromnode==node) {
857                         lb= &node->outputs;
858                         NodeTagChanged(ntree, link->tonode);
859                 }
860                 else if(link->tonode==node)
861                         lb= &node->inputs;
862                 else
863                         lb= NULL;
864
865                 if(lb) {
866                         for(sock= lb->first; sock; sock= sock->next) {
867                                 if(link->fromsock==sock || link->tosock==sock)
868                                         break;
869                         }
870                         if(sock) {
871                                 nodeRemLink(ntree, link);
872                         }
873                 }
874         }
875 }
876
877 static void composit_free_sockets(bNode *node)
878 {
879         bNodeSocket *sock;
880         
881         for(sock= node->outputs.first; sock; sock= sock->next) {
882                 if(sock->ns.data)
883                         free_compbuf(sock->ns.data);
884         }
885 }
886
887 void nodeFreeNode(bNodeTree *ntree, bNode *node)
888 {
889         node_unlink_node(ntree, node);
890         BLI_remlink(&ntree->nodes, node);
891
892         if(node->id)
893                 node->id->us--;
894         
895         if(ntree->type==NTREE_COMPOSIT)
896                 composit_free_sockets(node);
897         BLI_freelistN(&node->inputs);
898         BLI_freelistN(&node->outputs);
899         
900         if(node->preview) {
901                 if(node->preview->rect)
902                         MEM_freeN(node->preview->rect);
903                 MEM_freeN(node->preview);
904         }
905         if(node->storage) {
906                 /* could be handlerized at some point, now only 1 exception still */
907                 if(ntree->type==NTREE_SHADER) {
908                         if(node->type==SH_NODE_CURVE_VEC || node->type==SH_NODE_CURVE_RGB)
909                                 curvemapping_free(node->storage);
910                         else 
911                                 MEM_freeN(node->storage);
912                 }
913                 else if(ntree->type==NTREE_COMPOSIT) {
914                         if(node->type==CMP_NODE_CURVE_VEC || node->type==CMP_NODE_CURVE_RGB)
915                                 curvemapping_free(node->storage);
916                         else 
917                                 MEM_freeN(node->storage);
918                 }
919                 else 
920                         MEM_freeN(node->storage);
921         }
922         MEM_freeN(node);
923 }
924
925 /* do not free ntree itself here, free_libblock calls this function too */
926 void ntreeFreeTree(bNodeTree *ntree)
927 {
928         bNode *node, *next;
929         
930         if(ntree==NULL) return;
931         
932         BLI_freelistN(&ntree->links);   /* do first, then unlink_node goes fast */
933         
934         for(node= ntree->nodes.first; node; node= next) {
935                 next= node->next;
936                 nodeFreeNode(ntree, node);
937         }
938         
939         if(ntree->owntype) {
940                 if(ntree->owntype->inputs)
941                         MEM_freeN(ntree->owntype->inputs);
942                 if(ntree->owntype->outputs)
943                         MEM_freeN(ntree->owntype->outputs);
944                 MEM_freeN(ntree->owntype);
945         }
946 }
947
948 bNodeTree *ntreeCopyTree(bNodeTree *ntree, int internal_select)
949 {
950         bNodeTree *newtree;
951         bNode *node, *nnode, *last;
952         bNodeLink *link, *nlink;
953         bNodeSocket *sock;
954         int a;
955         
956         if(ntree==NULL) return NULL;
957         
958         if(internal_select==0) {
959                 newtree= MEM_dupallocN(ntree);
960                 newtree->nodes.first= newtree->nodes.last= NULL;
961                 newtree->links.first= newtree->links.last= NULL;
962         }
963         else
964                 newtree= ntree;
965         
966         last= ntree->nodes.last;
967         for(node= ntree->nodes.first; node; node= node->next) {
968                 
969                 node->new= NULL;
970                 if(internal_select==0 || (node->flag & NODE_SELECT)) {
971                         nnode= nodeCopyNode(newtree, node);     /* sets node->new */
972                         if(internal_select) {
973                                 node->flag &= ~NODE_SELECT;
974                                 nnode->flag |= NODE_SELECT;
975                         }
976                         node->flag &= ~NODE_ACTIVE;
977                 }
978                 if(node==last) break;
979         }
980         
981         /* check for copying links */
982         for(link= ntree->links.first; link; link= link->next) {
983                 if(link->fromnode->new && link->tonode->new) {
984                         nlink= nodeAddLink(newtree, link->fromnode->new, NULL, link->tonode->new, NULL);
985                         /* sockets were copied in order */
986                         for(a=0, sock= link->fromnode->outputs.first; sock; sock= sock->next, a++) {
987                                 if(sock==link->fromsock)
988                                         break;
989                         }
990                         nlink->fromsock= BLI_findlink(&link->fromnode->new->outputs, a);
991                         
992                         for(a=0, sock= link->tonode->inputs.first; sock; sock= sock->next, a++) {
993                                 if(sock==link->tosock)
994                                         break;
995                         }
996                         nlink->tosock= BLI_findlink(&link->tonode->new->inputs, a);
997                 }
998         }
999         
1000         /* own type definition for group usage */
1001         if(internal_select==0) {
1002                 if(ntree->owntype) {
1003                         newtree->owntype= MEM_dupallocN(ntree->owntype);
1004                         if(ntree->owntype->inputs)
1005                                 newtree->owntype->inputs= MEM_dupallocN(ntree->owntype->inputs);
1006                         if(ntree->owntype->outputs)
1007                                 newtree->owntype->outputs= MEM_dupallocN(ntree->owntype->outputs);
1008                 }
1009         }       
1010         return newtree;
1011 }
1012
1013 #pragma mark /* ************ find stuff *************** */
1014
1015 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
1016 {
1017         bNodeLink *link;
1018         
1019         for(link= ntree->links.first; link; link= link->next) {
1020                 if(link->fromsock==from && link->tosock==to)
1021                         return link;
1022                 if(link->fromsock==to && link->tosock==from)    /* hrms? */
1023                         return link;
1024         }
1025         return NULL;
1026 }
1027
1028 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1029 {
1030         bNodeLink *link;
1031         int tot= 0;
1032         
1033         for(link= ntree->links.first; link; link= link->next) {
1034                 if(link->fromsock==sock || link->tosock==sock)
1035                         tot++;
1036         }
1037         return tot;
1038 }
1039
1040 bNode *nodeGetActive(bNodeTree *ntree)
1041 {
1042         bNode *node;
1043         
1044         if(ntree==NULL) return NULL;
1045         
1046         for(node= ntree->nodes.first; node; node= node->next)
1047                 if(node->flag & NODE_ACTIVE)
1048                         break;
1049         return node;
1050 }
1051
1052 /* two active flags, ID nodes have special flag for buttons display */
1053 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
1054 {
1055         bNode *node;
1056         
1057         if(ntree==NULL) return NULL;
1058         
1059         for(node= ntree->nodes.first; node; node= node->next)
1060                 if(node->id && GS(node->id->name)==idtype)
1061                         if(node->flag & NODE_ACTIVE_ID)
1062                                 break;
1063         return node;
1064 }
1065
1066 /* two active flags, ID nodes have special flag for buttons display */
1067 void nodeClearActiveID(bNodeTree *ntree, short idtype)
1068 {
1069         bNode *node;
1070         
1071         if(ntree==NULL) return;
1072         
1073         for(node= ntree->nodes.first; node; node= node->next)
1074                 if(node->id && GS(node->id->name)==idtype)
1075                         node->flag &= ~NODE_ACTIVE_ID;
1076 }
1077
1078 /* two active flags, ID nodes have special flag for buttons display */
1079 void nodeSetActive(bNodeTree *ntree, bNode *node)
1080 {
1081         bNode *tnode;
1082         
1083         /* make sure only one node is active, and only one per ID type */
1084         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1085                 tnode->flag &= ~NODE_ACTIVE;
1086                 
1087                 if(node->id && tnode->id) {
1088                         if(GS(node->id->name) == GS(tnode->id->name))
1089                                 tnode->flag &= ~NODE_ACTIVE_ID;
1090                 }
1091         }
1092         
1093         node->flag |= NODE_ACTIVE;
1094         if(node->id)
1095                 node->flag |= NODE_ACTIVE_ID;
1096 }
1097
1098 /* use flags are not persistant yet, groups might need different tagging, so we do it each time
1099    when we need to get this info */
1100 void ntreeSocketUseFlags(bNodeTree *ntree)
1101 {
1102         bNode *node;
1103         bNodeSocket *sock;
1104         bNodeLink *link;
1105         
1106         /* clear flags */
1107         for(node= ntree->nodes.first; node; node= node->next) {
1108                 for(sock= node->inputs.first; sock; sock= sock->next)
1109                         sock->flag &= ~SOCK_IN_USE;
1110                 for(sock= node->outputs.first; sock; sock= sock->next)
1111                         sock->flag &= ~SOCK_IN_USE;
1112         }
1113         
1114         /* tag all thats in use */
1115         for(link= ntree->links.first; link; link= link->next) {
1116                 link->fromsock->flag |= SOCK_IN_USE;
1117                 link->tosock->flag |= SOCK_IN_USE;
1118         }
1119 }
1120
1121 #pragma mark /* ************** dependency stuff *********** */
1122
1123 /* node is guaranteed to be not checked before */
1124 static int node_recurs_check(bNode *node, bNode ***nsort, int level)
1125 {
1126         bNode *fromnode;
1127         bNodeSocket *sock;
1128         int has_inputlinks= 0;
1129         
1130         node->done= 1;
1131         level++;
1132         
1133         for(sock= node->inputs.first; sock; sock= sock->next) {
1134                 if(sock->link) {
1135                         has_inputlinks= 1;
1136                         fromnode= sock->link->fromnode;
1137                         if(fromnode->done==0) {
1138                                 fromnode->level= node_recurs_check(fromnode, nsort, level);
1139                         }
1140                 }
1141         }
1142 //      printf("node sort %s level %d\n", node->name, level);
1143         **nsort= node;
1144         (*nsort)++;
1145         
1146         if(has_inputlinks)
1147                 return level;
1148         else 
1149                 return 0xFFF;
1150 }
1151
1152 void ntreeSolveOrder(bNodeTree *ntree)
1153 {
1154         bNode *node, **nodesort, **nsort;
1155         bNodeSocket *sock;
1156         bNodeLink *link;
1157         int a, totnode=0;
1158         
1159         /* the solve-order is called on each tree change, so we should be sure no exec can be running */
1160         ntreeEndExecTree(ntree);
1161
1162         /* set links pointers the input sockets, to find dependencies */
1163         /* first clear data */
1164         for(node= ntree->nodes.first; node; node= node->next) {
1165                 node->done= 0;
1166                 totnode++;
1167                 for(sock= node->inputs.first; sock; sock= sock->next)
1168                         sock->link= NULL;
1169         }
1170         if(totnode==0)
1171                 return;
1172         
1173         for(link= ntree->links.first; link; link= link->next) {
1174                 link->tosock->link= link;
1175         }
1176         
1177         nsort= nodesort= MEM_callocN(totnode*sizeof(void *), "sorted node array");
1178         
1179         /* recursive check */
1180         for(node= ntree->nodes.first; node; node= node->next) {
1181                 if(node->done==0) {
1182                         node->level= node_recurs_check(node, &nsort, 0);
1183                 }
1184         }
1185         
1186         /* re-insert nodes in order, first a paranoia check */
1187         for(a=0; a<totnode; a++) {
1188                 if(nodesort[a]==NULL)
1189                         break;
1190         }
1191         if(a<totnode)
1192                 printf("sort error in node tree");
1193         else {
1194                 ntree->nodes.first= ntree->nodes.last= NULL;
1195                 for(a=0; a<totnode; a++)
1196                         BLI_addtail(&ntree->nodes, nodesort[a]);
1197         }
1198         
1199         MEM_freeN(nodesort);
1200         
1201         /* find the active outputs, might become tree type dependant handler */
1202         for(node= ntree->nodes.first; node; node= node->next) {
1203                 if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1204                         bNode *tnode;
1205                         int output= 0;
1206                         /* there is more types having output class, each one is checked */
1207                         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1208                                 if(tnode->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1209                                         if(tnode->type==node->type) {
1210                                                 if(tnode->flag & NODE_DO_OUTPUT) {
1211                                                         if(output>1)
1212                                                                 tnode->flag &= ~NODE_DO_OUTPUT;
1213                                                         output++;
1214                                                 }
1215                                         }
1216                                 }
1217                         }
1218                         if(output==0)
1219                                 node->flag |= NODE_DO_OUTPUT;
1220                 }
1221         }
1222         
1223         /* here we could recursively set which nodes have to be done,
1224                 might be different for editor or for "real" use... */
1225 }
1226
1227 /* should be callback! */
1228 void NodeTagChanged(bNodeTree *ntree, bNode *node)
1229 {
1230         if(ntree->type==NTREE_COMPOSIT) {
1231                 bNodeSocket *sock;
1232                 
1233                 for(sock= node->outputs.first; sock; sock= sock->next) {
1234                         if(sock->ns.data) {
1235                                 free_compbuf(sock->ns.data);
1236                                 sock->ns.data= NULL;
1237                         }
1238                 }
1239                 node->need_exec= 1;
1240         }
1241 }
1242
1243 #pragma mark /* *************** preview *********** */
1244
1245 /* if node->preview, then we assume the rect to exist */
1246
1247 static void nodeInitPreview(bNode *node, int xsize, int ysize)
1248 {
1249         
1250         if(node->preview==NULL) {
1251                 node->preview= MEM_callocN(sizeof(bNodePreview), "node preview");
1252                 printf("added preview %s\n", node->name);
1253         }
1254         
1255         /* node previews can get added with variable size this way */
1256         if(xsize==0 || ysize==0)
1257                 return;
1258         
1259         /* sanity checks & initialize */
1260         if(node->preview && node->preview->rect) {
1261                 if(node->preview->xsize!=xsize && node->preview->ysize!=ysize) {
1262                         MEM_freeN(node->preview->rect);
1263                         node->preview->rect= NULL;
1264                 }
1265         }
1266         
1267         if(node->preview->rect==NULL) {
1268                 node->preview->rect= MEM_callocN(4*xsize + xsize*ysize*sizeof(float)*4, "node preview rect");
1269                 node->preview->xsize= xsize;
1270                 node->preview->ysize= ysize;
1271         }
1272 }
1273
1274 void ntreeInitPreview(bNodeTree *ntree, int xsize, int ysize)
1275 {
1276         bNode *node;
1277         
1278         if(ntree==NULL)
1279                 return;
1280         
1281         for(node= ntree->nodes.first; node; node= node->next) {
1282                 if(node->typeinfo->flag & NODE_PREVIEW) /* hrms, check for closed nodes? */
1283                         nodeInitPreview(node, xsize, ysize);
1284                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1285                         ntreeInitPreview((bNodeTree *)node->id, xsize, ysize);
1286         }               
1287 }
1288
1289 void nodeAddToPreview(bNode *node, float *col, int x, int y)
1290 {
1291         bNodePreview *preview= node->preview;
1292         if(preview) {
1293                 if(x>=0 && y>=0) {
1294                         if(x<preview->xsize && y<preview->ysize) {
1295                                 float *tar= preview->rect+ 4*((preview->xsize*y) + x);
1296                                 QUATCOPY(tar, col);
1297                         }
1298                         else printf("prv out bound x y %d %d\n", x, y);
1299                 }
1300                 else printf("prv out bound x y %d %d\n", x, y);
1301         }
1302 }
1303
1304
1305
1306 #pragma mark /* ******************* executing ************* */
1307
1308 /* see notes at ntreeBeginExecTree */
1309 static void group_node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out, bNodeStack **gin, bNodeStack **gout)
1310 {
1311         bNodeSocket *sock;
1312         
1313         /* build pointer stack */
1314         for(sock= node->inputs.first; sock; sock= sock->next) {
1315                 if(sock->intern) {
1316                         /* yep, intern can have link or is hidden socket */
1317                         if(sock->link)
1318                                 *(in++)= stack + sock->link->fromsock->stack_index;
1319                         else
1320                                 *(in++)= &sock->ns;
1321                 }
1322                 else
1323                         *(in++)= gin[sock->stack_index_ext];
1324         }
1325         
1326         for(sock= node->outputs.first; sock; sock= sock->next) {
1327                 if(sock->intern)
1328                         *(out++)= stack + sock->stack_index;
1329                 else
1330                         *(out++)= gout[sock->stack_index_ext];
1331         }
1332 }
1333
1334 static void node_group_execute(bNodeStack *stack, void *data, bNode *gnode, bNodeStack **in, bNodeStack **out)
1335 {
1336         bNode *node;
1337         bNodeTree *ntree= (bNodeTree *)gnode->id;
1338         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1339         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1340         
1341         if(ntree==NULL) return;
1342         
1343         stack+= gnode->stack_index;
1344                 
1345         for(node= ntree->nodes.first; node; node= node->next) {
1346                 if(node->typeinfo->execfunc) {
1347                         group_node_get_stack(node, stack, nsin, nsout, in, out);
1348                         node->typeinfo->execfunc(data, node, nsin, nsout);
1349                 }
1350         }
1351 }
1352
1353 /* recursively called for groups */
1354 /* we set all trees on own local indices, but put a total counter
1355    in the groups, so each instance of a group has own stack */
1356 static int ntree_begin_exec_tree(bNodeTree *ntree)
1357 {
1358         bNode *node;
1359         bNodeSocket *sock;
1360         int index= 0, index_in= 0, index_out= 0;
1361         
1362         if((ntree->init & NTREE_TYPE_INIT)==0)
1363                 ntreeInitTypes(ntree);
1364         
1365         /* create indices for stack, check preview */
1366         for(node= ntree->nodes.first; node; node= node->next) {
1367                 
1368                 for(sock= node->inputs.first; sock; sock= sock->next) {
1369                         if(sock->intern==0)
1370                                 sock->stack_index_ext= index_in++;
1371                 }
1372                 
1373                 for(sock= node->outputs.first; sock; sock= sock->next) {
1374                         sock->stack_index= index++;
1375                         if(sock->intern==0)
1376                                 sock->stack_index_ext= index_out++;
1377                 }
1378                 
1379                 if(node->type==NODE_GROUP) {
1380                         if(node->id) {
1381                                 
1382                                 node->stack_index= index;
1383                                 index+= ntree_begin_exec_tree((bNodeTree *)node->id);
1384
1385                                 /* copy internal data from internal nodes to own input sockets */
1386                                 for(sock= node->inputs.first; sock; sock= sock->next) {
1387                                         if(sock->tosock) {
1388                                                 sock->ns= sock->tosock->ns;
1389                                         }
1390                                 }
1391                         }
1392                 }
1393         }
1394         
1395         return index;
1396 }
1397
1398 /* copy socket compbufs to stack */
1399 static void composit_begin_exec(bNodeTree *ntree)
1400 {
1401         bNode *node;
1402         
1403         for(node= ntree->nodes.first; node; node= node->next) {
1404                 bNodeSocket *sock;
1405                 for(sock= node->outputs.first; sock; sock= sock->next) {
1406                         if(sock->ns.data) {
1407                                 bNodeStack *ns= ntree->stack + sock->stack_index;
1408
1409                                 ns->data= sock->ns.data;
1410                                 sock->ns.data= NULL;
1411                         }
1412                 }
1413         }
1414 }
1415
1416 /* copy stack compbufs to sockets */
1417 static void composit_end_exec(bNodeTree *ntree)
1418 {
1419         extern void print_compbuf(char *str, struct CompBuf *cbuf);
1420         bNode *node;
1421         bNodeStack *ns;
1422         int a;
1423         
1424         for(node= ntree->nodes.first; node; node= node->next) {
1425                 bNodeSocket *sock;
1426                 
1427                 for(sock= node->outputs.first; sock; sock= sock->next) {
1428                         ns= ntree->stack + sock->stack_index;
1429                         if(ns->data) {
1430                                 sock->ns.data= ns->data;
1431                                 ns->data= NULL;
1432                         }
1433                 }
1434                 node->need_exec= 0;
1435         }
1436                                 
1437         for(ns= ntree->stack, a=0; a<ntree->stacksize; a++, ns++) {
1438                 if(ns->data) {
1439                         print_compbuf("error: buf hanging in stack", ns->data);
1440                         free_compbuf(ns->data);
1441                 }
1442         }
1443                                 
1444 }
1445
1446 /* stack indices make sure all nodes only write in allocated data, for making it thread safe */
1447 /* only root tree gets the stack, to enable instances to have own stack entries */
1448 /* only two threads now! */
1449 /* per tree (and per group) unique indices are created */
1450 /* the index_ext we need to be able to map from groups to the group-node own stack */
1451
1452 void ntreeBeginExecTree(bNodeTree *ntree)
1453 {
1454         
1455         /* goes recursive over all groups */
1456         ntree->stacksize= ntree_begin_exec_tree(ntree);
1457         
1458         if(ntree->stacksize) {
1459                 bNode *node;
1460                 bNodeStack *ns;
1461                 int a;
1462                 
1463                 /* allocate stack */
1464                 ns=ntree->stack= MEM_callocN(ntree->stacksize*sizeof(bNodeStack), "node stack");
1465                 
1466                 /* tag inputs, the get_stack() gives own socket stackdata if not in use */
1467                 for(a=0; a<ntree->stacksize; a++, ns++) ns->hasinput= 1;
1468                 
1469                 /* tag used outputs, so we know when we can skip operations */
1470                 /* hrms... groups... */
1471                 for(node= ntree->nodes.first; node; node= node->next) {
1472                         bNodeSocket *sock;
1473                         for(sock= node->inputs.first; sock; sock= sock->next) {
1474                                 if(sock->link) {
1475                                         ns= ntree->stack + sock->link->fromsock->stack_index;
1476                                         ns->hasoutput= 1;
1477                                 }
1478                         }
1479                 }
1480                 if(ntree->type==NTREE_COMPOSIT)
1481                         composit_begin_exec(ntree);
1482                 else
1483                         ntree->stack1= MEM_dupallocN(ntree->stack);
1484         }
1485         
1486         ntree->init |= NTREE_EXEC_INIT;
1487 }
1488
1489 void ntreeEndExecTree(bNodeTree *ntree)
1490 {
1491         
1492         if(ntree->init & NTREE_EXEC_INIT) {
1493                 
1494                 /* another callback candidate! */
1495                 if(ntree->type==NTREE_COMPOSIT)
1496                         composit_end_exec(ntree);
1497                 
1498                 if(ntree->stack)
1499                         MEM_freeN(ntree->stack);
1500                 ntree->stack= NULL;
1501                 
1502                 if(ntree->stack1)
1503                         MEM_freeN(ntree->stack1);
1504                 ntree->stack1= NULL;
1505
1506                 ntree->init &= ~NTREE_EXEC_INIT;
1507         }
1508 }
1509
1510 static void node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out)
1511 {
1512         bNodeSocket *sock;
1513         
1514         /* build pointer stack */
1515         for(sock= node->inputs.first; sock; sock= sock->next) {
1516                 if(sock->link)
1517                         *(in++)= stack + sock->link->fromsock->stack_index;
1518                 else
1519                         *(in++)= &sock->ns;
1520         }
1521         
1522         for(sock= node->outputs.first; sock; sock= sock->next) {
1523                 *(out++)= stack + sock->stack_index;
1524         }
1525 }
1526
1527 /* nodes are presorted, so exec is in order of list */
1528 void ntreeExecTree(bNodeTree *ntree, void *callerdata, int thread)
1529 {
1530         bNode *node;
1531         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1532         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1533         bNodeStack *stack;
1534         
1535         /* only when initialized */
1536         if((ntree->init & NTREE_EXEC_INIT)==0)
1537                 ntreeBeginExecTree(ntree);
1538                 
1539         if(thread)
1540                 stack= ntree->stack1;
1541         else
1542                 stack= ntree->stack;
1543         
1544         for(node= ntree->nodes.first; node; node= node->next) {
1545                 if(node->typeinfo->execfunc) {
1546                         node_get_stack(node, stack, nsin, nsout);
1547                         node->typeinfo->execfunc(callerdata, node, nsin, nsout);
1548                 }
1549                 else if(node->type==NODE_GROUP && node->id) {
1550                         node_get_stack(node, stack, nsin, nsout);
1551                         node_group_execute(stack, callerdata, node, nsin, nsout); 
1552                 }
1553         }
1554 }
1555
1556 /* optimized tree execute test for compositing */
1557 void ntreeCompositExecTree(bNodeTree *ntree, RenderData *rd, int do_preview)
1558 {
1559         bNode *node;
1560         bNodeSocket *sock;
1561         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1562         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1563         bNodeStack *stack;
1564         int totnode;
1565         
1566         if(ntree==NULL) return;
1567         
1568         totnode= BLI_countlist(&ntree->nodes);
1569         
1570         if(do_preview)
1571                 ntreeInitPreview(ntree, 0, 0);
1572         
1573         ntreeBeginExecTree(ntree);
1574         
1575         stack= ntree->stack;
1576         
1577         for(node= ntree->nodes.first; node; node= node->next) {
1578                 if(node->typeinfo->execfunc) {
1579                         int a;
1580                         
1581                         node_get_stack(node, stack, nsin, nsout);
1582                         
1583                         /* test the inputs */
1584                         for(a=0, sock= node->inputs.first; sock; sock= sock->next, a++) {
1585                                 /* is sock in use? */
1586                                 if(sock->link) {
1587                                         if(nsin[a]->data==NULL || sock->link->fromnode->need_exec) {
1588                                                 node->need_exec= 1;
1589                                                 break;
1590                                         }
1591                                 }
1592                         }
1593                         
1594                         /* test the outputs */
1595                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
1596                                 if(nsout[a]->data==NULL && nsout[a]->hasoutput) {
1597                                         node->need_exec= 1;
1598                                         break;
1599                                 }
1600                         }
1601                         if(node->need_exec) {
1602                                 
1603                                 /* free output buffers */
1604                                 for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
1605                                         if(nsout[a]->data) {
1606                                                 free_compbuf(nsout[a]->data);
1607                                                 nsout[a]->data= NULL;
1608                                         }
1609                                 }
1610                                 if(ntree->timecursor)
1611                                         ntree->timecursor(totnode);
1612                                 
1613                                 printf("exec node %s\n", node->name);
1614                                 node->typeinfo->execfunc(rd, node, nsin, nsout);
1615                         }
1616                 }
1617                 else if(node->type==NODE_GROUP && node->id) {
1618                         node_get_stack(node, stack, nsin, nsout);
1619                         node_group_execute(stack, rd, node, nsin, nsout); 
1620                 }
1621                 totnode--;
1622         }
1623         
1624         
1625         ntreeEndExecTree(ntree);
1626         
1627         free_unused_animimages();
1628         
1629 }
1630