Camera tracking integration
[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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 /** \file blender/blenkernel/intern/node.c
31  *  \ingroup bke
32  */
33
34
35 #if 0 /* pynodes commented for now */
36 #  ifdef WITH_PYTHON
37 #    include <Python.h>
38 #  endif
39 #endif
40
41 #include "MEM_guardedalloc.h"
42
43 #include <stdlib.h>
44 #include <stddef.h>
45 #include <string.h>
46 #include <limits.h>
47
48 #include "DNA_anim_types.h"
49 #include "DNA_node_types.h"
50 #include "DNA_scene_types.h"
51 #include "DNA_action_types.h"
52
53 #include "BLI_string.h"
54 #include "BLI_math.h"
55 #include "BLI_listbase.h"
56 #include "BLI_path_util.h"
57 #include "BLI_utildefines.h"
58
59 #include "BKE_animsys.h"
60 #include "BKE_action.h"
61 #include "BKE_fcurve.h"
62 #include "BKE_global.h"
63 #include "BKE_image.h"
64 #include "BKE_library.h"
65 #include "BKE_main.h"
66 #include "BKE_node.h"
67 #include "BKE_utildefines.h"
68 #include "BKE_utildefines.h"
69
70 #include "BLI_listbase.h"
71
72 #include "RNA_access.h"
73
74 #include "NOD_socket.h"
75 #include "NOD_composite.h"
76 #include "NOD_shader.h"
77 #include "NOD_texture.h"
78
79
80 bNodeTreeType *ntreeGetType(int type)
81 {
82         static bNodeTreeType *types[NUM_NTREE_TYPES];
83         static int types_init = 1;
84         if (types_init) {
85                 types[NTREE_SHADER] = &ntreeType_Shader;
86                 types[NTREE_COMPOSIT] = &ntreeType_Composite;
87                 types[NTREE_TEXTURE] = &ntreeType_Texture;
88                 types_init = 0;
89         }
90         
91         if(type >= 0 && type < NUM_NTREE_TYPES) {
92                 return types[type];
93         }
94         else {
95                 return NULL;
96         }
97 }
98
99 static bNodeType *node_get_type(bNodeTree *ntree, int type)
100 {
101         bNodeType *ntype = ntreeGetType(ntree->type)->node_types.first;
102         for(; ntype; ntype= ntype->next)
103                 if(ntype->type==type)
104                         return ntype;
105         
106         return NULL;
107 }
108
109 bNodeType *ntreeGetNodeType(bNodeTree *ntree)
110 {
111         return node_get_type(ntree, ntree->nodetype);
112 }
113
114 bNodeSocketType *ntreeGetSocketType(int type)
115 {
116         static bNodeSocketType *types[NUM_SOCKET_TYPES]= {NULL};
117         static int types_init = 1;
118
119         if (types_init) {
120                 node_socket_type_init(types);
121                 types_init= 0;
122         }
123
124         if(type < NUM_SOCKET_TYPES) {
125                 return types[type];
126         }
127         else {
128                 return NULL;
129         }
130 }
131
132 void ntreeInitTypes(bNodeTree *ntree)
133 {
134         bNode *node, *next;
135         
136         for(node= ntree->nodes.first; node; node= next) {
137                 next= node->next;
138                 
139                 node->typeinfo= node_get_type(ntree, node->type);
140                 
141                 if(node->type==NODE_DYNAMIC) {
142                         /* needed info if the pynode script fails now: */
143                         node->storage= ntree;
144                         if(node->id!=NULL) { /* not an empty script node */
145                                 node->custom1= 0;
146                                 node->custom1= BSET(node->custom1,NODE_DYNAMIC_ADDEXIST);
147                         }
148 //                      if(node->typeinfo)
149 //                              node->typeinfo->initfunc(node);
150                 }
151
152                 if(node->typeinfo==NULL) {
153                         printf("Error: Node type %s doesn't exist anymore, removed\n", node->name);
154                         nodeFreeNode(ntree, node);
155                 }
156         }
157                         
158         ntree->init |= NTREE_TYPE_INIT;
159 }
160
161 static bNodeSocket *make_socket(bNodeTree *UNUSED(ntree), int in_out, const char *name, int type)
162 {
163         bNodeSocketType *stype= ntreeGetSocketType(type);
164         bNodeSocket *sock;
165         
166         sock= MEM_callocN(sizeof(bNodeSocket), "sock");
167         
168         BLI_strncpy(sock->name, name, NODE_MAXSTR);
169         sock->limit = (in_out==SOCK_IN ? 1 : 0xFFF);
170         sock->type= type;
171         sock->storage = NULL;
172         
173         if (stype->value_structsize > 0)
174                 sock->default_value = MEM_callocN(stype->value_structsize, "default socket value");
175         
176         return sock;
177 }
178
179 bNodeSocket *nodeAddSocket(bNodeTree *ntree, bNode *node, int in_out, const char *name, int type)
180 {
181         bNodeSocket *sock = make_socket(ntree, in_out, name, type);
182         if (in_out==SOCK_IN)
183                 BLI_addtail(&node->inputs, sock);
184         else if (in_out==SOCK_OUT)
185                 BLI_addtail(&node->outputs, sock);
186         
187         ntree->update |= NTREE_UPDATE_NODES;
188         
189         return sock;
190 }
191
192 bNodeSocket *nodeInsertSocket(bNodeTree *ntree, bNode *node, int in_out, bNodeSocket *next_sock, const char *name, int type)
193 {
194         bNodeSocket *sock = make_socket(ntree, in_out, name, type);
195         if (in_out==SOCK_IN)
196                 BLI_insertlinkbefore(&node->inputs, next_sock, sock);
197         else if (in_out==SOCK_OUT)
198                 BLI_insertlinkbefore(&node->outputs, next_sock, sock);
199         
200         ntree->update |= NTREE_UPDATE_NODES;
201         
202         return sock;
203 }
204
205 void nodeRemoveSocket(bNodeTree *ntree, bNode *node, bNodeSocket *sock)
206 {
207         bNodeLink *link, *next;
208         
209         for(link= ntree->links.first; link; link= next) {
210                 next= link->next;
211                 if(link->fromsock==sock || link->tosock==sock) {
212                         nodeRemLink(ntree, link);
213                 }
214         }
215         
216         /* this is fast, this way we don't need an in_out argument */
217         BLI_remlink(&node->inputs, sock);
218         BLI_remlink(&node->outputs, sock);
219         
220         if (sock->default_value)
221                 MEM_freeN(sock->default_value);
222         MEM_freeN(sock);
223         
224         ntree->update |= NTREE_UPDATE_NODES;
225 }
226
227 void nodeRemoveAllSockets(bNodeTree *ntree, bNode *node)
228 {
229         bNodeSocket *sock;
230         bNodeLink *link, *next;
231         
232         for(link= ntree->links.first; link; link= next) {
233                 next= link->next;
234                 if(link->fromnode==node || link->tonode==node) {
235                         nodeRemLink(ntree, link);
236                 }
237         }
238         
239         for (sock=node->inputs.first; sock; sock=sock->next)
240                 if (sock->default_value)
241                         MEM_freeN(sock->default_value);
242         BLI_freelistN(&node->inputs);
243         for (sock=node->outputs.first; sock; sock=sock->next)
244                 if (sock->default_value)
245                         MEM_freeN(sock->default_value);
246         
247         BLI_freelistN(&node->outputs);
248         
249         ntree->update |= NTREE_UPDATE_NODES;
250 }
251
252 /* finds a node based on its name */
253 bNode *nodeFindNodebyName(bNodeTree *ntree, const char *name)
254 {
255         return BLI_findstring(&ntree->nodes, name, offsetof(bNode, name));
256 }
257
258 /* finds a node based on given socket */
259 int nodeFindNode(bNodeTree *ntree, bNodeSocket *sock, bNode **nodep, int *sockindex, int *in_out)
260 {
261         bNode *node;
262         bNodeSocket *tsock;
263         int index= 0;
264         
265         for(node= ntree->nodes.first; node; node= node->next) {
266                 for(index=0, tsock= node->inputs.first; tsock; tsock= tsock->next, index++) {
267                         if(tsock==sock) {
268                                 if (in_out) *in_out= SOCK_IN;
269                                 break;
270                         }
271                 }
272                 if(tsock)
273                         break;
274                 for(index=0, tsock= node->outputs.first; tsock; tsock= tsock->next, index++) {
275                         if(tsock==sock) {
276                                 if (in_out) *in_out= SOCK_OUT;
277                                 break;
278                         }
279                 }
280                 if(tsock)
281                         break;
282         }
283
284         if(node) {
285                 *nodep= node;
286                 if(sockindex) *sockindex= index;
287                 return 1;
288         }
289         
290         *nodep= NULL;
291         return 0;
292 }
293
294 /* ************** Add stuff ********** */
295 static void node_add_sockets_from_type(bNodeTree *ntree, bNode *node, bNodeType *ntype)
296 {
297         bNodeSocketTemplate *sockdef;
298         bNodeSocket *sock;
299
300         if(ntype->inputs) {
301                 sockdef= ntype->inputs;
302                 while(sockdef->type != -1) {
303                         sock = node_add_input_from_template(ntree, node, sockdef);
304                         
305                         sockdef++;
306                 }
307         }
308         if(ntype->outputs) {
309                 sockdef= ntype->outputs;
310                 while(sockdef->type != -1) {
311                         sock = node_add_output_from_template(ntree, node, sockdef);
312                         
313                         sockdef++;
314                 }
315         }
316 }
317
318 /* Find the first available, non-duplicate name for a given node */
319 void nodeUniqueName(bNodeTree *ntree, bNode *node)
320 {
321         BLI_uniquename(&ntree->nodes, node, "Node", '.', offsetof(bNode, name), sizeof(node->name));
322 }
323
324 bNode *nodeAddNode(bNodeTree *ntree, struct bNodeTemplate *ntemp)
325 {
326         bNode *node;
327         bNodeType *ntype;
328         
329         ntype= node_get_type(ntree, ntemp->type);
330         if(ntype == NULL) {
331                 printf("nodeAddNodeType() error: '%d' type invalid\n", ntemp->type);
332                 return NULL;
333         }
334         /* validity check */
335         if (!nodeValid(ntree, ntemp))
336                 return NULL;
337         
338         node= MEM_callocN(sizeof(bNode), "new node");
339         node->type= ntype->type;
340         node->typeinfo= ntype;
341         node->flag= NODE_SELECT|ntype->flag;
342         node->width= ntype->width;
343         node->miniwidth= 42.0f;
344         node->height= ntype->height;
345         
346         node_add_sockets_from_type(ntree, node, ntype);
347         
348         if(ntype->initfunc!=NULL)
349                 ntype->initfunc(ntree, node, ntemp);
350         
351         /* initialize the node name with the node label */
352         BLI_strncpy(node->name, nodeLabel(node), NODE_MAXSTR);
353         nodeUniqueName(ntree, node);
354         
355         BLI_addtail(&ntree->nodes, node);
356         
357         ntree->update |= NTREE_UPDATE_NODES;
358         
359         return node;
360 }
361
362 void nodeMakeDynamicType(bNode *node)
363 {
364         /* find SH_DYNAMIC_NODE ntype */
365         bNodeType *ntype= ntreeGetType(NTREE_SHADER)->node_types.first;
366         while(ntype) {
367                 if(ntype->type==NODE_DYNAMIC)
368                         break;
369                 ntype= ntype->next;
370         }
371
372         /* make own type struct to fill */
373         if(ntype) {
374                 /*node->typeinfo= MEM_dupallocN(ntype);*/
375                 bNodeType *newtype= MEM_callocN(sizeof(bNodeType), "dynamic bNodeType");
376                 *newtype= *ntype;
377                 strcpy(newtype->name, ntype->name);
378                 node->typeinfo= newtype;
379         }
380 }
381
382 /* keep socket listorder identical, for copying links */
383 /* ntree is the target tree */
384 bNode *nodeCopyNode(struct bNodeTree *ntree, struct bNode *node)
385 {
386         bNode *nnode= MEM_callocN(sizeof(bNode), "dupli node");
387         bNodeSocket *sock, *oldsock;
388
389         *nnode= *node;
390         nodeUniqueName(ntree, nnode);
391         
392         BLI_addtail(&ntree->nodes, nnode);
393
394         BLI_duplicatelist(&nnode->inputs, &node->inputs);
395         oldsock= node->inputs.first;
396         for(sock= nnode->inputs.first; sock; sock= sock->next, oldsock= oldsock->next) {
397                 oldsock->new_sock= sock;
398                 sock->stack_index= 0;
399                 
400                 sock->default_value = (oldsock->default_value ? MEM_dupallocN(oldsock->default_value) : NULL);
401                 
402                 /* XXX some compositor node (e.g. image, render layers) still store
403                  * some persistent buffer data here, need to clear this to avoid dangling pointers.
404                  */
405                 sock->cache = NULL;
406         }
407         
408         BLI_duplicatelist(&nnode->outputs, &node->outputs);
409         oldsock= node->outputs.first;
410         for(sock= nnode->outputs.first; sock; sock= sock->next, oldsock= oldsock->next) {
411                 oldsock->new_sock= sock;
412                 sock->stack_index= 0;
413                 
414                 sock->default_value = (oldsock->default_value ? MEM_dupallocN(oldsock->default_value) : NULL);
415                 
416                 /* XXX some compositor node (e.g. image, render layers) still store
417                  * some persistent buffer data here, need to clear this to avoid dangling pointers.
418                  */
419                 sock->cache = NULL;
420         }
421         
422         /* don't increase node->id users, freenode doesn't decrement either */
423         
424         if(node->typeinfo->copystoragefunc)
425                 node->typeinfo->copystoragefunc(node, nnode);
426         
427         node->new_node= nnode;
428         nnode->new_node= NULL;
429         nnode->preview= NULL;
430         
431         ntree->update |= NTREE_UPDATE_NODES;
432         
433         return nnode;
434 }
435
436 /* also used via rna api, so we check for proper input output direction */
437 bNodeLink *nodeAddLink(bNodeTree *ntree, bNode *fromnode, bNodeSocket *fromsock, bNode *tonode, bNodeSocket *tosock)
438 {
439         bNodeSocket *sock;
440         bNodeLink *link= NULL; 
441         int from= 0, to= 0;
442         
443         if(fromnode) {
444                 /* test valid input */
445                 for(sock= fromnode->outputs.first; sock; sock= sock->next)
446                         if(sock==fromsock)
447                                 break;
448                 if(sock)
449                         from= 1; /* OK */
450                 else {
451                         for(sock= fromnode->inputs.first; sock; sock= sock->next)
452                                 if(sock==fromsock)
453                                         break;
454                         if(sock)
455                                 from= -1; /* OK but flip */
456                 }
457         }
458         else {
459                 /* check tree sockets */
460                 for(sock= ntree->inputs.first; sock; sock= sock->next)
461                         if(sock==fromsock)
462                                 break;
463                 if(sock)
464                         from= 1; /* OK */
465                 else {
466                         for(sock= ntree->outputs.first; sock; sock= sock->next)
467                                 if(sock==fromsock)
468                                         break;
469                         if(sock)
470                                 from= -1; /* OK but flip */
471                 }
472         }
473         if(tonode) {
474                 for(sock= tonode->inputs.first; sock; sock= sock->next)
475                         if(sock==tosock)
476                                 break;
477                 if(sock)
478                         to= 1; /* OK */
479                 else {
480                         for(sock= tonode->outputs.first; sock; sock= sock->next)
481                                 if(sock==tosock)
482                                         break;
483                         if(sock)
484                                 to= -1; /* OK but flip */
485                 }
486         }
487         else {
488                 /* check tree sockets */
489                 for(sock= ntree->outputs.first; sock; sock= sock->next)
490                         if(sock==tosock)
491                                 break;
492                 if(sock)
493                         to= 1; /* OK */
494                 else {
495                         for(sock= ntree->inputs.first; sock; sock= sock->next)
496                                 if(sock==tosock)
497                                         break;
498                         if(sock)
499                                 to= -1; /* OK but flip */
500                 }
501         }
502         
503         if(from >= 0 && to >= 0) {
504                 link= MEM_callocN(sizeof(bNodeLink), "link");
505                 BLI_addtail(&ntree->links, link);
506                 link->fromnode= fromnode;
507                 link->fromsock= fromsock;
508                 link->tonode= tonode;
509                 link->tosock= tosock;
510         }
511         else if(from <= 0 && to <= 0) {
512                 link= MEM_callocN(sizeof(bNodeLink), "link");
513                 BLI_addtail(&ntree->links, link);
514                 link->fromnode= tonode;
515                 link->fromsock= tosock;
516                 link->tonode= fromnode;
517                 link->tosock= fromsock;
518         }
519         
520         ntree->update |= NTREE_UPDATE_LINKS;
521         
522         return link;
523 }
524
525 void nodeRemLink(bNodeTree *ntree, bNodeLink *link)
526 {
527         BLI_remlink(&ntree->links, link);
528         if(link->tosock)
529                 link->tosock->link= NULL;
530         MEM_freeN(link);
531         
532         ntree->update |= NTREE_UPDATE_LINKS;
533 }
534
535 void nodeRemSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
536 {
537         bNodeLink *link, *next;
538         
539         for(link= ntree->links.first; link; link= next) {
540                 next= link->next;
541                 if(link->fromsock==sock || link->tosock==sock) {
542                         nodeRemLink(ntree, link);
543                 }
544         }
545         
546         ntree->update |= NTREE_UPDATE_LINKS;
547 }
548
549 /* transforms node location to area coords */
550 void nodeSpaceCoords(bNode *node, float *locx, float *locy)
551 {
552         if (node->parent) {
553                 nodeSpaceCoords(node->parent, locx, locy);
554                 *locx += node->locx;
555                 *locy += node->locy;
556         }
557         else {
558                 *locx = node->locx;
559                 *locy = node->locy;
560         }
561 }
562
563 void nodeAttachNode(bNode *node, bNode *parent)
564 {
565         float parentx, parenty;
566         
567         node->parent = parent;
568         /* transform to parent space */
569         nodeSpaceCoords(parent, &parentx, &parenty);
570         node->locx -= parentx;
571         node->locy -= parenty;
572 }
573
574 void nodeDetachNode(struct bNode *node)
575 {
576         float parentx, parenty;
577         
578         if (node->parent) {
579                 /* transform to "global" (area) space */
580                 nodeSpaceCoords(node->parent, &parentx, &parenty);
581                 node->locx += parentx;
582                 node->locy += parenty;
583                 node->parent = NULL;
584         }
585 }
586
587 bNodeTree *ntreeAddTree(const char *name, int type, int nodetype)
588 {
589         bNodeTree *ntree;
590         bNodeType *ntype;
591         
592         /* trees are created as local trees if they of compositor, material or texture type,
593          * node groups and other tree types are created as library data.
594          */
595         if (ELEM3(type, NTREE_COMPOSIT, NTREE_SHADER, NTREE_TEXTURE) && nodetype==0) {
596                 ntree= MEM_callocN(sizeof(bNodeTree), "new node tree");
597                 *( (short *)ntree->id.name )= ID_NT; /* not "type", as that is ntree->type */
598                 BLI_strncpy(ntree->id.name+2, name, sizeof(ntree->id.name));
599         }
600         else
601                 ntree= alloc_libblock(&G.main->nodetree, ID_NT, name);
602         
603         ntree->type= type;
604         ntree->nodetype = nodetype;
605         
606         ntreeInitTypes(ntree);
607         
608         ntype = node_get_type(ntree, ntree->nodetype);
609         if (ntype && ntype->inittreefunc)
610                 ntype->inittreefunc(ntree);
611         
612         return ntree;
613 }
614
615 /* Warning: this function gets called during some rather unexpected times
616  *      - this gets called when executing compositing updates (for threaded previews)
617  *      - when the nodetree datablock needs to be copied (i.e. when users get copied)
618  *      - for scene duplication use ntreeSwapID() after so we dont have stale pointers.
619  */
620 bNodeTree *ntreeCopyTree(bNodeTree *ntree)
621 {
622         bNodeTree *newtree;
623         bNode *node, *nnode, *last;
624         bNodeLink *link;
625         bNodeSocket *gsock, *oldgsock;
626         
627         if(ntree==NULL) return NULL;
628         
629         /* is ntree part of library? */
630         for(newtree=G.main->nodetree.first; newtree; newtree= newtree->id.next)
631                 if(newtree==ntree) break;
632         if(newtree) {
633                 newtree= copy_libblock(ntree);
634         } else {
635                 newtree= MEM_dupallocN(ntree);
636                 copy_libblock_data(&newtree->id, &ntree->id, TRUE); /* copy animdata and ID props */
637         }
638
639         id_us_plus((ID *)newtree->gpd);
640
641         /* in case a running nodetree is copied */
642         newtree->execdata= NULL;
643         
644         newtree->nodes.first= newtree->nodes.last= NULL;
645         newtree->links.first= newtree->links.last= NULL;
646         
647         last = ntree->nodes.last;
648         for(node= ntree->nodes.first; node; node= node->next) {
649                 node->new_node= NULL;
650                 nnode= nodeCopyNode(newtree, node);     /* sets node->new */
651                 
652                 /* make sure we don't copy new nodes again! */
653                 if (node==last)
654                         break;
655         }
656         
657         /* socket definition for group usage */
658         BLI_duplicatelist(&newtree->inputs, &ntree->inputs);
659         for(gsock= newtree->inputs.first, oldgsock= ntree->inputs.first; gsock; gsock=gsock->next, oldgsock=oldgsock->next) {
660                 oldgsock->new_sock= gsock;
661                 gsock->groupsock = (oldgsock->groupsock ? oldgsock->groupsock->new_sock : NULL);
662                 gsock->default_value = (oldgsock->default_value ? MEM_dupallocN(oldgsock->default_value) : NULL);
663         }
664         BLI_duplicatelist(&newtree->outputs, &ntree->outputs);
665         for(gsock= newtree->outputs.first, oldgsock= ntree->outputs.first; gsock; gsock=gsock->next, oldgsock=oldgsock->next) {
666                 oldgsock->new_sock= gsock;
667                 gsock->groupsock = (oldgsock->groupsock ? oldgsock->groupsock->new_sock : NULL);
668                 gsock->default_value = (oldgsock->default_value ? MEM_dupallocN(oldgsock->default_value) : NULL);
669         }
670         
671         /* copy links */
672         BLI_duplicatelist(&newtree->links, &ntree->links);
673         for(link= newtree->links.first; link; link= link->next) {
674                 link->fromnode = (link->fromnode ? link->fromnode->new_node : NULL);
675                 link->fromsock = (link->fromsock ? link->fromsock->new_sock : NULL);
676                 link->tonode = (link->tonode ? link->tonode->new_node : NULL);
677                 link->tosock = (link->tosock ? link->tosock->new_sock : NULL);
678                 /* update the link socket's pointer */
679                 if (link->tosock)
680                         link->tosock->link = link;
681         }
682         
683         /* update node->parent pointers */
684         for (node=newtree->nodes.first; node; node=node->next) {
685                 if (node->parent)
686                         node->parent = node->parent->new_node;
687         }
688         
689         return newtree;
690 }
691
692 /* use when duplicating scenes */
693 void ntreeSwitchID(bNodeTree *ntree, ID *id_from, ID *id_to)
694 {
695         bNode *node;
696         /* for scene duplication only */
697         for(node= ntree->nodes.first; node; node= node->next) {
698                 if(node->id==id_from) {
699                         node->id= id_to;
700                 }
701         }
702 }
703
704 /* *************** preview *********** */
705 /* if node->preview, then we assume the rect to exist */
706
707 void nodeFreePreview(bNode *node)
708 {
709         if(node->preview) {
710                 if(node->preview->rect)
711                         MEM_freeN(node->preview->rect);
712                 MEM_freeN(node->preview);
713                 node->preview= NULL;
714         }       
715 }
716
717 static void node_init_preview(bNode *node, int xsize, int ysize)
718 {
719         
720         if(node->preview==NULL) {
721                 node->preview= MEM_callocN(sizeof(bNodePreview), "node preview");
722                 //              printf("added preview %s\n", node->name);
723         }
724         
725         /* node previews can get added with variable size this way */
726         if(xsize==0 || ysize==0)
727                 return;
728         
729         /* sanity checks & initialize */
730         if(node->preview->rect) {
731                 if(node->preview->xsize!=xsize && node->preview->ysize!=ysize) {
732                         MEM_freeN(node->preview->rect);
733                         node->preview->rect= NULL;
734                 }
735         }
736         
737         if(node->preview->rect==NULL) {
738                 node->preview->rect= MEM_callocN(4*xsize + xsize*ysize*sizeof(char)*4, "node preview rect");
739                 node->preview->xsize= xsize;
740                 node->preview->ysize= ysize;
741         }
742         /* no clear, makes nicer previews */
743 }
744
745 void ntreeInitPreview(bNodeTree *ntree, int xsize, int ysize)
746 {
747         bNode *node;
748         
749         if(ntree==NULL)
750                 return;
751         
752         for(node= ntree->nodes.first; node; node= node->next) {
753                 if(node->typeinfo->flag & NODE_PREVIEW) /* hrms, check for closed nodes? */
754                         node_init_preview(node, xsize, ysize);
755                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
756                         ntreeInitPreview((bNodeTree *)node->id, xsize, ysize);
757         }               
758 }
759
760 static void nodeClearPreview(bNode *node)
761 {
762         if(node->preview && node->preview->rect)
763                 memset(node->preview->rect, 0, MEM_allocN_len(node->preview->rect));
764 }
765
766 /* use it to enforce clear */
767 void ntreeClearPreview(bNodeTree *ntree)
768 {
769         bNode *node;
770         
771         if(ntree==NULL)
772                 return;
773         
774         for(node= ntree->nodes.first; node; node= node->next) {
775                 if(node->typeinfo->flag & NODE_PREVIEW)
776                         nodeClearPreview(node);
777                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
778                         ntreeClearPreview((bNodeTree *)node->id);
779         }               
780 }
781
782 /* hack warning! this function is only used for shader previews, and 
783 since it gets called multiple times per pixel for Ztransp we only
784 add the color once. Preview gets cleared before it starts render though */
785 void nodeAddToPreview(bNode *node, float *col, int x, int y, int do_manage)
786 {
787         bNodePreview *preview= node->preview;
788         if(preview) {
789                 if(x>=0 && y>=0) {
790                         if(x<preview->xsize && y<preview->ysize) {
791                                 unsigned char *tar= preview->rect+ 4*((preview->xsize*y) + x);
792                                 
793                                 if(do_manage) {
794                                         tar[0]= FTOCHAR(linearrgb_to_srgb(col[0]));
795                                         tar[1]= FTOCHAR(linearrgb_to_srgb(col[1]));
796                                         tar[2]= FTOCHAR(linearrgb_to_srgb(col[2]));
797                                 }
798                                 else {
799                                         tar[0]= FTOCHAR(col[0]);
800                                         tar[1]= FTOCHAR(col[1]);
801                                         tar[2]= FTOCHAR(col[2]);
802                                 }
803                                 tar[3]= FTOCHAR(col[3]);
804                         }
805                         //else printf("prv out bound x y %d %d\n", x, y);
806                 }
807                 //else printf("prv out bound x y %d %d\n", x, y);
808         }
809 }
810
811 /* ************** Free stuff ********** */
812
813 /* goes over entire tree */
814 void nodeUnlinkNode(bNodeTree *ntree, bNode *node)
815 {
816         bNodeLink *link, *next;
817         bNodeSocket *sock;
818         ListBase *lb;
819         
820         for(link= ntree->links.first; link; link= next) {
821                 next= link->next;
822                 
823                 if(link->fromnode==node) {
824                         lb= &node->outputs;
825                         if (link->tonode)
826                                 NodeTagChanged(ntree, link->tonode);
827                 }
828                 else if(link->tonode==node)
829                         lb= &node->inputs;
830                 else
831                         lb= NULL;
832
833                 if(lb) {
834                         for(sock= lb->first; sock; sock= sock->next) {
835                                 if(link->fromsock==sock || link->tosock==sock)
836                                         break;
837                         }
838                         if(sock) {
839                                 nodeRemLink(ntree, link);
840                         }
841                 }
842         }
843 }
844
845 static void node_unlink_attached(bNodeTree *ntree, bNode *parent)
846 {
847         bNode *node;
848         for (node=ntree->nodes.first; node; node=node->next) {
849                 if (node->parent == parent)
850                         nodeDetachNode(node);
851         }
852 }
853
854 void nodeFreeNode(bNodeTree *ntree, bNode *node)
855 {
856         bNodeTreeType *treetype= ntreeGetType(ntree->type);
857         bNodeSocket *sock, *nextsock;
858         
859         /* remove all references to this node */
860         nodeUnlinkNode(ntree, node);
861         node_unlink_attached(ntree, node);
862         
863         BLI_remlink(&ntree->nodes, node);
864
865         /* since it is called while free database, node->id is undefined */
866         
867         if (treetype->free_node_cache)
868                 treetype->free_node_cache(ntree, node);
869         
870         for (sock=node->inputs.first; sock; sock = nextsock) {
871                 nextsock = sock->next;
872                 if (sock->default_value)
873                         MEM_freeN(sock->default_value);
874                 MEM_freeN(sock);
875         }
876         for (sock=node->outputs.first; sock; sock = nextsock) {
877                 nextsock = sock->next;
878                 if (sock->default_value)
879                         MEM_freeN(sock->default_value);
880                 MEM_freeN(sock);
881         }
882
883         nodeFreePreview(node);
884
885         if(node->typeinfo && node->typeinfo->freestoragefunc) {
886                 node->typeinfo->freestoragefunc(node);
887         }
888
889         MEM_freeN(node);
890         
891         ntree->update |= NTREE_UPDATE_NODES;
892 }
893
894 /* do not free ntree itself here, free_libblock calls this function too */
895 void ntreeFreeTree(bNodeTree *ntree)
896 {
897         bNode *node, *next;
898         bNodeSocket *sock;
899         
900         if(ntree==NULL) return;
901         
902         /* XXX hack! node trees should not store execution graphs at all.
903          * This should be removed when old tree types no longer require it.
904          * Currently the execution data for texture nodes remains in the tree
905          * after execution, until the node tree is updated or freed.
906          */
907         if (ntree->execdata) {
908                 switch (ntree->type) {
909                 case NTREE_COMPOSIT:
910                         ntreeCompositEndExecTree(ntree->execdata, 1);
911                         break;
912                 case NTREE_SHADER:
913                         ntreeShaderEndExecTree(ntree->execdata, 1);
914                         break;
915                 case NTREE_TEXTURE:
916                         ntreeTexEndExecTree(ntree->execdata, 1);
917                         break;
918                 }
919         }
920         
921         BKE_free_animdata((ID *)ntree);
922         
923         id_us_min((ID *)ntree->gpd);
924
925         BLI_freelistN(&ntree->links);   /* do first, then unlink_node goes fast */
926         
927         for(node= ntree->nodes.first; node; node= next) {
928                 next= node->next;
929                 nodeFreeNode(ntree, node);
930         }
931         
932         for (sock=ntree->inputs.first; sock; sock=sock->next)
933                 if (sock->default_value)
934                         MEM_freeN(sock->default_value);
935         BLI_freelistN(&ntree->inputs);
936         for (sock=ntree->outputs.first; sock; sock=sock->next)
937                 if (sock->default_value)
938                         MEM_freeN(sock->default_value);
939         BLI_freelistN(&ntree->outputs);
940 }
941
942 void ntreeFreeCache(bNodeTree *ntree)
943 {
944         bNodeTreeType *treetype;
945         
946         if(ntree==NULL) return;
947         
948         treetype= ntreeGetType(ntree->type);
949         if (treetype->free_cache)
950                 treetype->free_cache(ntree);
951 }
952
953 void ntreeSetOutput(bNodeTree *ntree)
954 {
955         bNode *node;
956
957         /* find the active outputs, might become tree type dependant handler */
958         for(node= ntree->nodes.first; node; node= node->next) {
959                 if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
960                         bNode *tnode;
961                         int output= 0;
962                         
963                         /* we need a check for which output node should be tagged like this, below an exception */
964                         if(node->type==CMP_NODE_OUTPUT_FILE)
965                            continue;
966                            
967                         /* there is more types having output class, each one is checked */
968                         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
969                                 if(tnode->typeinfo->nclass==NODE_CLASS_OUTPUT) {
970                                         
971                                         if(ntree->type==NTREE_COMPOSIT) {
972                                                         
973                                                 /* same type, exception for viewer */
974                                                 if(tnode->type==node->type ||
975                                                    (ELEM(tnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) &&
976                                                         ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))) {
977                                                         if(tnode->flag & NODE_DO_OUTPUT) {
978                                                                 output++;
979                                                                 if(output>1)
980                                                                         tnode->flag &= ~NODE_DO_OUTPUT;
981                                                         }
982                                                 }
983                                         }
984                                         else {
985                                                 /* same type */
986                                                 if(tnode->type==node->type) {
987                                                         if(tnode->flag & NODE_DO_OUTPUT) {
988                                                                 output++;
989                                                                 if(output>1)
990                                                                         tnode->flag &= ~NODE_DO_OUTPUT;
991                                                         }
992                                                 }
993                                         }
994                                 }
995                         }
996                         if(output==0)
997                                 node->flag |= NODE_DO_OUTPUT;
998                 }
999         }
1000         
1001         /* here we could recursively set which nodes have to be done,
1002                 might be different for editor or for "real" use... */
1003 }
1004
1005 typedef struct MakeLocalCallData {
1006         ID *group_id;
1007         ID *new_id;
1008         int lib, local;
1009 } MakeLocalCallData;
1010
1011 static void ntreeMakeLocal_CheckLocal(void *calldata, ID *owner_id, bNodeTree *ntree)
1012 {
1013         MakeLocalCallData *cd= (MakeLocalCallData*)calldata;
1014         bNode *node;
1015         
1016         /* find if group is in tree */
1017         for(node= ntree->nodes.first; node; node= node->next) {
1018                 if(node->id == cd->group_id) {
1019                         if(owner_id->lib) cd->lib= 1;
1020                         else cd->local= 1;
1021                 }
1022         }
1023 }
1024
1025 static void ntreeMakeLocal_LinkNew(void *calldata, ID *owner_id, bNodeTree *ntree)
1026 {
1027         MakeLocalCallData *cd= (MakeLocalCallData*)calldata;
1028         bNode *node;
1029         
1030         /* find if group is in tree */
1031         for(node= ntree->nodes.first; node; node= node->next) {
1032                 if(node->id == cd->group_id) {
1033                         if(owner_id->lib==NULL) {
1034                                 node->id= cd->new_id;
1035                                 cd->new_id->us++;
1036                                 cd->group_id->us--;
1037                         }
1038                 }
1039         }
1040 }
1041
1042 void ntreeMakeLocal(bNodeTree *ntree)
1043 {
1044         bNodeTreeType *treetype= ntreeGetType(ntree->type);
1045         MakeLocalCallData cd;
1046         
1047         /* - only lib users: do nothing
1048                 * - only local users: set flag
1049                 * - mixed: make copy
1050                 */
1051         
1052         if(ntree->id.lib==NULL) return;
1053         if(ntree->id.us==1) {
1054                 ntree->id.lib= NULL;
1055                 ntree->id.flag= LIB_LOCAL;
1056                 new_id(NULL, (ID *)ntree, NULL);
1057                 return;
1058         }
1059         
1060         /* now check users of groups... again typedepending, callback... */
1061         cd.group_id = &ntree->id;
1062         cd.new_id = NULL;
1063         cd.local = 0;
1064         cd.lib = 0;
1065         
1066         treetype->foreach_nodetree(G.main, &cd, &ntreeMakeLocal_CheckLocal);
1067         
1068         /* if all users are local, we simply make tree local */
1069         if(cd.local && cd.lib==0) {
1070                 ntree->id.lib= NULL;
1071                 ntree->id.flag= LIB_LOCAL;
1072                 new_id(NULL, (ID *)ntree, NULL);
1073         }
1074         else if(cd.local && cd.lib) {
1075                 /* this is the mixed case, we copy the tree and assign it to local users */
1076                 bNodeTree *newtree= ntreeCopyTree(ntree);
1077                 
1078                 newtree->id.us= 0;
1079                 
1080
1081                 cd.new_id = &newtree->id;
1082                 treetype->foreach_nodetree(G.main, &cd, &ntreeMakeLocal_LinkNew);
1083         }
1084 }
1085
1086 int ntreeNodeExists(bNodeTree *ntree, bNode *testnode)
1087 {
1088         bNode *node= ntree->nodes.first;
1089         for(; node; node= node->next)
1090                 if(node==testnode)
1091                         return 1;
1092         return 0;
1093 }
1094
1095 int ntreeOutputExists(bNode *node, bNodeSocket *testsock)
1096 {
1097         bNodeSocket *sock= node->outputs.first;
1098         for(; sock; sock= sock->next)
1099                 if(sock==testsock)
1100                         return 1;
1101         return 0;
1102 }
1103
1104 /* returns localized tree for execution in threads */
1105 bNodeTree *ntreeLocalize(bNodeTree *ntree)
1106 {
1107         bNodeTreeType *ntreetype= ntreeGetType(ntree->type);
1108
1109         bNodeTree *ltree;
1110         bNode *node;
1111         
1112         bAction *action_backup= NULL, *tmpact_backup= NULL;
1113         
1114         /* Workaround for copying an action on each render!
1115          * set action to NULL so animdata actions dont get copied */
1116         AnimData *adt= BKE_animdata_from_id(&ntree->id);
1117
1118         if(adt) {
1119                 action_backup= adt->action;
1120                 tmpact_backup= adt->tmpact;
1121
1122                 adt->action= NULL;
1123                 adt->tmpact= NULL;
1124         }
1125
1126         /* node copy func */
1127         ltree= ntreeCopyTree(ntree);
1128
1129         if(adt) {
1130                 AnimData *ladt= BKE_animdata_from_id(&ltree->id);
1131
1132                 adt->action= ladt->action= action_backup;
1133                 adt->tmpact= ladt->tmpact= tmpact_backup;
1134
1135                 if(action_backup) action_backup->id.us++;
1136                 if(tmpact_backup) tmpact_backup->id.us++;
1137                 
1138         }
1139         /* end animdata uglyness */
1140
1141         /* ensures only a single output node is enabled */
1142         ntreeSetOutput(ntree);
1143
1144         for(node= ntree->nodes.first; node; node= node->next) {
1145                 /* store new_node pointer to original */
1146                 node->new_node->new_node= node;
1147         }
1148
1149         if (ntreetype->localize)
1150                 ntreetype->localize(ltree, ntree);
1151
1152         return ltree;
1153 }
1154
1155 /* sync local composite with real tree */
1156 /* local tree is supposed to be running, be careful moving previews! */
1157 /* is called by jobs manager, outside threads, so it doesnt happen during draw */
1158 void ntreeLocalSync(bNodeTree *localtree, bNodeTree *ntree)
1159 {
1160         bNodeTreeType *ntreetype= ntreeGetType(ntree->type);
1161
1162         if (ntreetype->local_sync)
1163                 ntreetype->local_sync(localtree, ntree);
1164 }
1165
1166 /* merge local tree results back, and free local tree */
1167 /* we have to assume the editor already changed completely */
1168 void ntreeLocalMerge(bNodeTree *localtree, bNodeTree *ntree)
1169 {
1170         bNodeTreeType *ntreetype= ntreeGetType(ntree->type);
1171         bNode *lnode;
1172         
1173         /* move over the compbufs and previews */
1174         for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
1175                 if(ntreeNodeExists(ntree, lnode->new_node)) {
1176                         if(lnode->preview && lnode->preview->rect) {
1177                                 nodeFreePreview(lnode->new_node);
1178                                 lnode->new_node->preview= lnode->preview;
1179                                 lnode->preview= NULL;
1180                         }
1181                 }
1182         }
1183
1184         if (ntreetype->local_merge)
1185                 ntreetype->local_merge(localtree, ntree);
1186
1187         ntreeFreeTree(localtree);
1188         MEM_freeN(localtree);
1189 }
1190
1191 /* ************ find stuff *************** */
1192
1193 int ntreeHasType(bNodeTree *ntree, int type)
1194 {
1195         bNode *node;
1196         
1197         if(ntree)
1198                 for(node= ntree->nodes.first; node; node= node->next)
1199                         if(node->type == type)
1200                                 return 1;
1201         return 0;
1202 }
1203
1204 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
1205 {
1206         bNodeLink *link;
1207         
1208         for(link= ntree->links.first; link; link= link->next) {
1209                 if(link->fromsock==from && link->tosock==to)
1210                         return link;
1211                 if(link->fromsock==to && link->tosock==from)    /* hrms? */
1212                         return link;
1213         }
1214         return NULL;
1215 }
1216
1217 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1218 {
1219         bNodeLink *link;
1220         int tot= 0;
1221         
1222         for(link= ntree->links.first; link; link= link->next) {
1223                 if(link->fromsock==sock || link->tosock==sock)
1224                         tot++;
1225         }
1226         return tot;
1227 }
1228
1229 bNode *nodeGetActive(bNodeTree *ntree)
1230 {
1231         bNode *node;
1232         
1233         if(ntree==NULL) return NULL;
1234         
1235         for(node= ntree->nodes.first; node; node= node->next)
1236                 if(node->flag & NODE_ACTIVE)
1237                         break;
1238         return node;
1239 }
1240
1241 /* two active flags, ID nodes have special flag for buttons display */
1242 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
1243 {
1244         bNode *node;
1245         
1246         if(ntree==NULL) return NULL;
1247
1248         /* check for group edit */
1249         for(node= ntree->nodes.first; node; node= node->next)
1250                 if(node->flag & NODE_GROUP_EDIT)
1251                         break;
1252
1253         if(node)
1254                 ntree= (bNodeTree*)node->id;
1255         
1256         /* now find active node with this id */
1257         for(node= ntree->nodes.first; node; node= node->next)
1258                 if(node->id && GS(node->id->name)==idtype)
1259                         if(node->flag & NODE_ACTIVE_ID)
1260                                 break;
1261
1262         return node;
1263 }
1264
1265 int nodeSetActiveID(bNodeTree *ntree, short idtype, ID *id)
1266 {
1267         bNode *node;
1268         int ok= FALSE;
1269
1270         if(ntree==NULL) return ok;
1271
1272         /* check for group edit */
1273         for(node= ntree->nodes.first; node; node= node->next)
1274                 if(node->flag & NODE_GROUP_EDIT)
1275                         break;
1276
1277         if(node)
1278                 ntree= (bNodeTree*)node->id;
1279
1280         /* now find active node with this id */
1281         for(node= ntree->nodes.first; node; node= node->next) {
1282                 if(node->id && GS(node->id->name)==idtype) {
1283                         if(id && ok==FALSE && node->id==id) {
1284                                 node->flag |= NODE_ACTIVE_ID;
1285                                 ok= TRUE;
1286                         } else {
1287                                 node->flag &= ~NODE_ACTIVE_ID;
1288                         }
1289                 }
1290         }
1291
1292         return ok;
1293 }
1294
1295
1296 /* two active flags, ID nodes have special flag for buttons display */
1297 void nodeClearActiveID(bNodeTree *ntree, short idtype)
1298 {
1299         bNode *node;
1300         
1301         if(ntree==NULL) return;
1302         
1303         for(node= ntree->nodes.first; node; node= node->next)
1304                 if(node->id && GS(node->id->name)==idtype)
1305                         node->flag &= ~NODE_ACTIVE_ID;
1306 }
1307
1308 /* two active flags, ID nodes have special flag for buttons display */
1309 void nodeSetActive(bNodeTree *ntree, bNode *node)
1310 {
1311         bNode *tnode;
1312         
1313         /* make sure only one node is active, and only one per ID type */
1314         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1315                 tnode->flag &= ~NODE_ACTIVE;
1316                 
1317                 if(node->id && tnode->id) {
1318                         if(GS(node->id->name) == GS(tnode->id->name))
1319                                 tnode->flag &= ~NODE_ACTIVE_ID;
1320                 }
1321         }
1322         
1323         node->flag |= NODE_ACTIVE;
1324         if(node->id)
1325                 node->flag |= NODE_ACTIVE_ID;
1326 }
1327
1328 /* use flags are not persistant yet, groups might need different tagging, so we do it each time
1329    when we need to get this info */
1330 void ntreeSocketUseFlags(bNodeTree *ntree)
1331 {
1332         bNode *node;
1333         bNodeSocket *sock;
1334         bNodeLink *link;
1335         
1336         /* clear flags */
1337         for(node= ntree->nodes.first; node; node= node->next) {
1338                 for(sock= node->inputs.first; sock; sock= sock->next)
1339                         sock->flag &= ~SOCK_IN_USE;
1340                 for(sock= node->outputs.first; sock; sock= sock->next)
1341                         sock->flag &= ~SOCK_IN_USE;
1342         }
1343         
1344         /* tag all thats in use */
1345         for(link= ntree->links.first; link; link= link->next) {
1346         
1347                 if(link->fromsock) // FIXME, see below
1348                         link->fromsock->flag |= SOCK_IN_USE;
1349                 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
1350                         link->tosock->flag |= SOCK_IN_USE;
1351         }
1352 }
1353
1354 /* ************** dependency stuff *********** */
1355
1356 /* node is guaranteed to be not checked before */
1357 static int node_get_deplist_recurs(bNode *node, bNode ***nsort)
1358 {
1359         bNode *fromnode;
1360         bNodeSocket *sock;
1361         int level = 0xFFF;
1362         
1363         node->done= 1;
1364         
1365         /* check linked nodes */
1366         for(sock= node->inputs.first; sock; sock= sock->next) {
1367                 if(sock->link) {
1368                         fromnode= sock->link->fromnode;
1369                         if(fromnode) {
1370                                 if (fromnode->done==0)
1371                                         fromnode->level= node_get_deplist_recurs(fromnode, nsort);
1372                                 if (fromnode->level <= level)
1373                                         level = fromnode->level - 1;
1374                         }
1375                 }
1376         }
1377         
1378         /* check parent node */
1379         if (node->parent) {
1380                 if (node->parent->done==0)
1381                         node->parent->level= node_get_deplist_recurs(node->parent, nsort);
1382                 if (node->parent->level <= level)
1383                         level = node->parent->level - 1;
1384         }
1385         
1386         if (nsort) {
1387                 **nsort= node;
1388                 (*nsort)++;
1389         }
1390         
1391         return level;
1392 }
1393
1394 void ntreeGetDependencyList(struct bNodeTree *ntree, struct bNode ***deplist, int *totnodes)
1395 {
1396         bNode *node, **nsort;
1397         
1398         *totnodes=0;
1399         
1400         /* first clear data */
1401         for(node= ntree->nodes.first; node; node= node->next) {
1402                 node->done= 0;
1403                 (*totnodes)++;
1404         }
1405         if(*totnodes==0) {
1406                 *deplist = NULL;
1407                 return;
1408         }
1409         
1410         nsort= *deplist= MEM_callocN((*totnodes)*sizeof(bNode*), "sorted node array");
1411         
1412         /* recursive check */
1413         for(node= ntree->nodes.first; node; node= node->next) {
1414                 if(node->done==0) {
1415                         node->level= node_get_deplist_recurs(node, &nsort);
1416                 }
1417         }
1418 }
1419
1420 static void ntree_update_link_pointers(bNodeTree *ntree)
1421 {
1422         bNode *node;
1423         bNodeSocket *sock;
1424         bNodeLink *link;
1425         
1426         /* first clear data */
1427         for(node= ntree->nodes.first; node; node= node->next) {
1428                 for(sock= node->inputs.first; sock; sock= sock->next)
1429                         sock->link= NULL;
1430         }
1431         /* clear socket links */
1432         for(sock= ntree->outputs.first; sock; sock= sock->next)
1433                 sock->link= NULL;
1434
1435         for(link= ntree->links.first; link; link= link->next) {
1436                 if (link->tosock)
1437                         link->tosock->link= link;
1438         }
1439 }
1440
1441 static void ntree_validate_links(bNodeTree *ntree)
1442 {
1443         bNodeTreeType *ntreetype = ntreeGetType(ntree->type);
1444         bNodeLink *link;
1445         
1446         for (link = ntree->links.first; link; link = link->next) {
1447                 link->flag |= NODE_LINK_VALID;
1448                 if (link->fromnode && link->tonode && link->fromnode->level <= link->tonode->level)
1449                         link->flag &= ~NODE_LINK_VALID;
1450                 else if (ntreetype->validate_link) {
1451                         if (!ntreetype->validate_link(ntree, link))
1452                                 link->flag &= ~NODE_LINK_VALID;
1453                 }
1454         }
1455 }
1456
1457 static void ntree_verify_nodes_cb(void *calldata, struct ID *UNUSED(owner_id), struct bNodeTree *ntree)
1458 {
1459         ID *id= (ID*)calldata;
1460         bNode *node;
1461         
1462         for (node=ntree->nodes.first; node; node=node->next)
1463                 if (node->typeinfo->verifyfunc)
1464                         node->typeinfo->verifyfunc(ntree, node, id);
1465 }
1466
1467 void ntreeVerifyNodes(struct Main *main, struct ID *id)
1468 {
1469         bNodeTreeType *ntreetype;
1470         bNodeTree *ntree;
1471         int n;
1472         
1473         for (n=0; n < NUM_NTREE_TYPES; ++n) {
1474                 ntreetype= ntreeGetType(n);
1475                 if (ntreetype && ntreetype->foreach_nodetree)
1476                         ntreetype->foreach_nodetree(main, id, ntree_verify_nodes_cb);
1477         }
1478         for (ntree=main->nodetree.first; ntree; ntree=ntree->id.next)
1479                 ntree_verify_nodes_cb(id, NULL, ntree);
1480 }
1481
1482 void ntreeUpdateTree(bNodeTree *ntree)
1483 {
1484         bNodeTreeType *ntreetype= ntreeGetType(ntree->type);
1485         bNode *node;
1486         bNode **deplist;
1487         int totnodes, n;
1488         
1489         ntree_update_link_pointers(ntree);
1490         
1491         /* also updates the node level! */
1492         ntreeGetDependencyList(ntree, &deplist, &totnodes);
1493         
1494         if (deplist) {
1495                 /* update individual nodes */
1496                 for (n=0; n < totnodes; ++n) {
1497                         node = deplist[n];
1498                         if (ntreetype->update_node)
1499                                 ntreetype->update_node(ntree, node);
1500                         else if (node->typeinfo->updatefunc)
1501                                 node->typeinfo->updatefunc(ntree, node);
1502                 }
1503                 
1504                 MEM_freeN(deplist);
1505                 
1506                 /* ensures only a single output node is enabled, texnode allows multiple though */
1507                 if(ntree->type!=NTREE_TEXTURE)
1508                         ntreeSetOutput(ntree);
1509                 
1510         }
1511         
1512         /* general tree updates */
1513         if (ntree->update & (NTREE_UPDATE_LINKS|NTREE_UPDATE_NODES)) {
1514                 ntree_validate_links(ntree);
1515         }
1516         
1517         /* update tree */
1518         if (ntreetype->update)
1519                 ntreetype->update(ntree);
1520         else {
1521                 bNodeType *ntype= node_get_type(ntree, ntree->nodetype);
1522                 if (ntype && ntype->updatetreefunc)
1523                         ntype->updatetreefunc(ntree);
1524         }
1525         
1526         /* XXX hack, should be done by depsgraph!! */
1527         ntreeVerifyNodes(G.main, &ntree->id);
1528         
1529         /* clear the update flag */
1530         ntree->update = 0;
1531 }
1532
1533 void NodeTagChanged(bNodeTree *ntree, bNode *node)
1534 {
1535         bNodeTreeType *ntreetype = ntreeGetType(ntree->type);
1536         
1537         /* extra null pointer checks here because this is called when unlinking
1538            unknown nodes on file load, so typeinfo pointers may not be set */
1539         if (ntreetype && ntreetype->update_node)
1540                 ntreetype->update_node(ntree, node);
1541         else if (node->typeinfo && node->typeinfo->updatefunc)
1542                 node->typeinfo->updatefunc(ntree, node);
1543 }
1544
1545 int NodeTagIDChanged(bNodeTree *ntree, ID *id)
1546 {
1547         bNodeTreeType *ntreetype;
1548         bNode *node;
1549         int change = FALSE;
1550
1551         if(ELEM(NULL, id, ntree))
1552                 return change;
1553         
1554         ntreetype = ntreeGetType(ntree->type);
1555         
1556         if (ntreetype->update_node) {
1557                 for(node= ntree->nodes.first; node; node= node->next) {
1558                         if(node->id==id) {
1559                                 change = TRUE;
1560                                 ntreetype->update_node(ntree, node);
1561                         }
1562                 }
1563         }
1564         else {
1565                 for(node= ntree->nodes.first; node; node= node->next) {
1566                         if(node->id==id) {
1567                                 change = TRUE;
1568                                 if (node->typeinfo->updatefunc)
1569                                         node->typeinfo->updatefunc(ntree, node);
1570                         }
1571                 }
1572         }
1573         
1574         return change;
1575 }
1576
1577
1578 /* ************* node type access ********** */
1579
1580 int nodeValid(bNodeTree *ntree, bNodeTemplate *ntemp)
1581 {
1582         bNodeType *ntype= node_get_type(ntree, ntemp->type);
1583         if (ntype) {
1584                 if (ntype->validfunc)
1585                         return ntype->validfunc(ntree, ntemp);
1586                 else
1587                         return 1;
1588         }
1589         else
1590                 return 0;
1591 }
1592
1593 const char* nodeLabel(bNode *node)
1594 {
1595         if (node->label[0]!='\0')
1596                 return node->label;
1597         else if (node->typeinfo->labelfunc)
1598                 return node->typeinfo->labelfunc(node);
1599         else
1600                 return node->typeinfo->name;
1601 }
1602
1603 struct bNodeTree *nodeGroupEditGet(struct bNode *node)
1604 {
1605         if (node->typeinfo->group_edit_get)
1606                 return node->typeinfo->group_edit_get(node);
1607         else
1608                 return NULL;
1609 }
1610
1611 struct bNodeTree *nodeGroupEditSet(struct bNode *node, int edit)
1612 {
1613         if (node->typeinfo->group_edit_set)
1614                 return node->typeinfo->group_edit_set(node, edit);
1615         else if (node->typeinfo->group_edit_get)
1616                 return node->typeinfo->group_edit_get(node);
1617         else
1618                 return NULL;
1619 }
1620
1621 void nodeGroupEditClear(struct bNode *node)
1622 {
1623         if (node->typeinfo->group_edit_clear)
1624                 node->typeinfo->group_edit_clear(node);
1625 }
1626
1627 struct bNodeTemplate nodeMakeTemplate(struct bNode *node)
1628 {
1629         bNodeTemplate ntemp;
1630         if (node->typeinfo->templatefunc)
1631                 return node->typeinfo->templatefunc(node);
1632         else {
1633                 ntemp.type = node->type;
1634                 return ntemp;
1635         }
1636 }
1637
1638 void node_type_base(bNodeType *ntype, int type, const char *name, short nclass, short flag)
1639 {
1640         memset(ntype, 0, sizeof(bNodeType));
1641         
1642         ntype->type = type;
1643         BLI_strncpy(ntype->name, name, sizeof(ntype->name));
1644         ntype->nclass = nclass;
1645         ntype->flag = flag;
1646         
1647         /* default size values */
1648         ntype->width = 140;
1649         ntype->minwidth = 100;
1650         ntype->maxwidth = 320;
1651         ntype->height = 100;
1652         ntype->minheight = 30;
1653         ntype->maxheight = FLT_MAX;
1654 }
1655
1656 void node_type_socket_templates(struct bNodeType *ntype, struct bNodeSocketTemplate *inputs, struct bNodeSocketTemplate *outputs)
1657 {
1658         ntype->inputs = inputs;
1659         ntype->outputs = outputs;
1660 }
1661
1662 void node_type_init(struct bNodeType *ntype, void (*initfunc)(struct bNodeTree *ntree, struct bNode *node, struct bNodeTemplate *ntemp))
1663 {
1664         ntype->initfunc = initfunc;
1665 }
1666
1667 void node_type_valid(struct bNodeType *ntype, int (*validfunc)(struct bNodeTree *ntree, struct bNodeTemplate *ntemp))
1668 {
1669         ntype->validfunc = validfunc;
1670 }
1671
1672 void node_type_size(struct bNodeType *ntype, int width, int minwidth, int maxwidth)
1673 {
1674         ntype->width = width;
1675         ntype->minwidth = minwidth;
1676         if (maxwidth <= minwidth)
1677                 ntype->maxwidth = FLT_MAX;
1678         else
1679                 ntype->maxwidth = maxwidth;
1680 }
1681
1682 void node_type_storage(bNodeType *ntype, const char *storagename, void (*freestoragefunc)(struct bNode *), void (*copystoragefunc)(struct bNode *, struct bNode *))
1683 {
1684         if (storagename)
1685                 strncpy(ntype->storagename, storagename, sizeof(ntype->storagename));
1686         else
1687                 ntype->storagename[0] = '\0';
1688         ntype->copystoragefunc = copystoragefunc;
1689         ntype->freestoragefunc = freestoragefunc;
1690 }
1691
1692 void node_type_label(struct bNodeType *ntype, const char *(*labelfunc)(struct bNode *))
1693 {
1694         ntype->labelfunc = labelfunc;
1695 }
1696
1697 void node_type_template(struct bNodeType *ntype, struct bNodeTemplate (*templatefunc)(struct bNode *))
1698 {
1699         ntype->templatefunc = templatefunc;
1700 }
1701
1702 void node_type_update(struct bNodeType *ntype,
1703                                           void (*updatefunc)(struct bNodeTree *ntree, struct bNode *node),
1704                                           void (*verifyfunc)(struct bNodeTree *ntree, struct bNode *node, struct ID *id))
1705 {
1706         ntype->updatefunc = updatefunc;
1707         ntype->verifyfunc = verifyfunc;
1708 }
1709
1710 void node_type_tree(struct bNodeType *ntype, void (*inittreefunc)(struct bNodeTree *), void (*updatetreefunc)(struct bNodeTree *))
1711 {
1712         ntype->inittreefunc = inittreefunc;
1713         ntype->updatetreefunc = updatetreefunc;
1714 }
1715
1716 void node_type_group_edit(struct bNodeType *ntype,
1717                                                   struct bNodeTree *(*group_edit_get)(struct bNode *node),
1718                                                   struct bNodeTree *(*group_edit_set)(struct bNode *node, int edit),
1719                                                   void (*group_edit_clear)(struct bNode *node))
1720 {
1721         ntype->group_edit_get = group_edit_get;
1722         ntype->group_edit_set = group_edit_set;
1723         ntype->group_edit_clear = group_edit_clear;
1724 }
1725
1726 void node_type_exec(struct bNodeType *ntype, void (*execfunc)(void *data, struct bNode *, struct bNodeStack **, struct bNodeStack **))
1727 {
1728         ntype->execfunc = execfunc;
1729 }
1730
1731 void node_type_exec_new(struct bNodeType *ntype,
1732                                                 void *(*initexecfunc)(struct bNode *node),
1733                                                 void (*freeexecfunc)(struct bNode *node, void *nodedata),
1734                                                 void (*newexecfunc)(void *data, int thread, struct bNode *, void *nodedata, struct bNodeStack **, struct bNodeStack **))
1735 {
1736         ntype->initexecfunc = initexecfunc;
1737         ntype->freeexecfunc = freeexecfunc;
1738         ntype->newexecfunc = newexecfunc;
1739 }
1740
1741 void node_type_gpu(struct bNodeType *ntype, int (*gpufunc)(struct GPUMaterial *mat, struct bNode *node, struct GPUNodeStack *in, struct GPUNodeStack *out))
1742 {
1743         ntype->gpufunc = gpufunc;
1744 }
1745
1746 void node_type_gpu_ext(struct bNodeType *ntype, int (*gpuextfunc)(struct GPUMaterial *mat, struct bNode *node, void *nodedata, struct GPUNodeStack *in, struct GPUNodeStack *out))
1747 {
1748         ntype->gpuextfunc = gpuextfunc;
1749 }
1750
1751
1752 static bNodeType *is_nodetype_registered(ListBase *typelist, int type) 
1753 {
1754         bNodeType *ntype= typelist->first;
1755         
1756         for(;ntype; ntype= ntype->next )
1757                 if(ntype->type==type)
1758                         return ntype;
1759         
1760         return NULL;
1761 }
1762
1763 void nodeRegisterType(ListBase *typelist, bNodeType *ntype) 
1764 {
1765         bNodeType *found= is_nodetype_registered(typelist, ntype->type);
1766         
1767         if(found==NULL)
1768                 BLI_addtail(typelist, ntype);
1769 }
1770
1771 static void registerCompositNodes(ListBase *ntypelist)
1772 {
1773         register_node_type_frame(ntypelist);
1774         
1775         register_node_type_cmp_group(ntypelist);
1776 //      register_node_type_cmp_forloop(ntypelist);
1777 //      register_node_type_cmp_whileloop(ntypelist);
1778         
1779         register_node_type_cmp_rlayers(ntypelist);
1780         register_node_type_cmp_image(ntypelist);
1781         register_node_type_cmp_texture(ntypelist);
1782         register_node_type_cmp_value(ntypelist);
1783         register_node_type_cmp_rgb(ntypelist);
1784         register_node_type_cmp_curve_time(ntypelist);
1785         register_node_type_cmp_movieclip(ntypelist);
1786         
1787         register_node_type_cmp_composite(ntypelist);
1788         register_node_type_cmp_viewer(ntypelist);
1789         register_node_type_cmp_splitviewer(ntypelist);
1790         register_node_type_cmp_output_file(ntypelist);
1791         register_node_type_cmp_view_levels(ntypelist);
1792         
1793         register_node_type_cmp_curve_rgb(ntypelist);
1794         register_node_type_cmp_mix_rgb(ntypelist);
1795         register_node_type_cmp_hue_sat(ntypelist);
1796         register_node_type_cmp_brightcontrast(ntypelist);
1797         register_node_type_cmp_gamma(ntypelist);
1798         register_node_type_cmp_invert(ntypelist);
1799         register_node_type_cmp_alphaover(ntypelist);
1800         register_node_type_cmp_zcombine(ntypelist);
1801         register_node_type_cmp_colorbalance(ntypelist);
1802         register_node_type_cmp_huecorrect(ntypelist);
1803         
1804         register_node_type_cmp_normal(ntypelist);
1805         register_node_type_cmp_curve_vec(ntypelist);
1806         register_node_type_cmp_map_value(ntypelist);
1807         register_node_type_cmp_normalize(ntypelist);
1808         
1809         register_node_type_cmp_filter(ntypelist);
1810         register_node_type_cmp_blur(ntypelist);
1811         register_node_type_cmp_dblur(ntypelist);
1812         register_node_type_cmp_bilateralblur(ntypelist);
1813         register_node_type_cmp_vecblur(ntypelist);
1814         register_node_type_cmp_dilateerode(ntypelist);
1815         register_node_type_cmp_defocus(ntypelist);
1816         
1817         register_node_type_cmp_valtorgb(ntypelist);
1818         register_node_type_cmp_rgbtobw(ntypelist);
1819         register_node_type_cmp_setalpha(ntypelist);
1820         register_node_type_cmp_idmask(ntypelist);
1821         register_node_type_cmp_math(ntypelist);
1822         register_node_type_cmp_seprgba(ntypelist);
1823         register_node_type_cmp_combrgba(ntypelist);
1824         register_node_type_cmp_sephsva(ntypelist);
1825         register_node_type_cmp_combhsva(ntypelist);
1826         register_node_type_cmp_sepyuva(ntypelist);
1827         register_node_type_cmp_combyuva(ntypelist);
1828         register_node_type_cmp_sepycca(ntypelist);
1829         register_node_type_cmp_combycca(ntypelist);
1830         register_node_type_cmp_premulkey(ntypelist);
1831         
1832         register_node_type_cmp_diff_matte(ntypelist);
1833         register_node_type_cmp_distance_matte(ntypelist);
1834         register_node_type_cmp_chroma_matte(ntypelist);
1835         register_node_type_cmp_color_matte(ntypelist);
1836         register_node_type_cmp_channel_matte(ntypelist);
1837         register_node_type_cmp_color_spill(ntypelist);
1838         register_node_type_cmp_luma_matte(ntypelist);
1839         
1840         register_node_type_cmp_translate(ntypelist);
1841         register_node_type_cmp_rotate(ntypelist);
1842         register_node_type_cmp_scale(ntypelist);
1843         register_node_type_cmp_flip(ntypelist);
1844         register_node_type_cmp_crop(ntypelist);
1845         register_node_type_cmp_displace(ntypelist);
1846         register_node_type_cmp_mapuv(ntypelist);
1847         register_node_type_cmp_glare(ntypelist);
1848         register_node_type_cmp_tonemap(ntypelist);
1849         register_node_type_cmp_lensdist(ntypelist);
1850         register_node_type_cmp_transform(ntypelist);
1851         register_node_type_cmp_stabilize2d(ntypelist);
1852         register_node_type_cmp_moviedistort(ntypelist);
1853         register_node_type_cmp_movieundistort(ntypelist);
1854 }
1855
1856 static void registerShaderNodes(ListBase *ntypelist) 
1857 {
1858         register_node_type_frame(ntypelist);
1859         
1860         register_node_type_sh_group(ntypelist);
1861 //      register_node_type_sh_forloop(ntypelist);
1862 //      register_node_type_sh_whileloop(ntypelist);
1863         
1864         register_node_type_sh_output(ntypelist);
1865         register_node_type_sh_mix_rgb(ntypelist);
1866         register_node_type_sh_valtorgb(ntypelist);
1867         register_node_type_sh_rgbtobw(ntypelist);
1868         register_node_type_sh_normal(ntypelist);
1869         register_node_type_sh_geom(ntypelist);
1870         register_node_type_sh_mapping(ntypelist);
1871         register_node_type_sh_curve_vec(ntypelist);
1872         register_node_type_sh_curve_rgb(ntypelist);
1873         register_node_type_sh_math(ntypelist);
1874         register_node_type_sh_vect_math(ntypelist);
1875         register_node_type_sh_squeeze(ntypelist);
1876         register_node_type_sh_camera(ntypelist);
1877         register_node_type_sh_material(ntypelist);
1878         register_node_type_sh_material_ext(ntypelist);
1879         register_node_type_sh_value(ntypelist);
1880         register_node_type_sh_rgb(ntypelist);
1881         register_node_type_sh_texture(ntypelist);
1882 //      register_node_type_sh_dynamic(ntypelist);
1883         register_node_type_sh_invert(ntypelist);
1884         register_node_type_sh_seprgb(ntypelist);
1885         register_node_type_sh_combrgb(ntypelist);
1886         register_node_type_sh_hue_sat(ntypelist);
1887 }
1888
1889 static void registerTextureNodes(ListBase *ntypelist)
1890 {
1891         register_node_type_frame(ntypelist);
1892         
1893         register_node_type_tex_group(ntypelist);
1894 //      register_node_type_tex_forloop(ntypelist);
1895 //      register_node_type_tex_whileloop(ntypelist);
1896         
1897         register_node_type_tex_math(ntypelist);
1898         register_node_type_tex_mix_rgb(ntypelist);
1899         register_node_type_tex_valtorgb(ntypelist);
1900         register_node_type_tex_rgbtobw(ntypelist);
1901         register_node_type_tex_valtonor(ntypelist);
1902         register_node_type_tex_curve_rgb(ntypelist);
1903         register_node_type_tex_curve_time(ntypelist);
1904         register_node_type_tex_invert(ntypelist);
1905         register_node_type_tex_hue_sat(ntypelist);
1906         register_node_type_tex_coord(ntypelist);
1907         register_node_type_tex_distance(ntypelist);
1908         register_node_type_tex_compose(ntypelist);
1909         register_node_type_tex_decompose(ntypelist);
1910         
1911         register_node_type_tex_output(ntypelist);
1912         register_node_type_tex_viewer(ntypelist);
1913         
1914         register_node_type_tex_checker(ntypelist);
1915         register_node_type_tex_texture(ntypelist);
1916         register_node_type_tex_bricks(ntypelist);
1917         register_node_type_tex_image(ntypelist);
1918         
1919         register_node_type_tex_rotate(ntypelist);
1920         register_node_type_tex_translate(ntypelist);
1921         register_node_type_tex_scale(ntypelist);
1922         register_node_type_tex_at(ntypelist);
1923         
1924         register_node_type_tex_proc_voronoi(ntypelist);
1925         register_node_type_tex_proc_blend(ntypelist);
1926         register_node_type_tex_proc_magic(ntypelist);
1927         register_node_type_tex_proc_marble(ntypelist);
1928         register_node_type_tex_proc_clouds(ntypelist);
1929         register_node_type_tex_proc_wood(ntypelist);
1930         register_node_type_tex_proc_musgrave(ntypelist);
1931         register_node_type_tex_proc_noise(ntypelist);
1932         register_node_type_tex_proc_stucci(ntypelist);
1933         register_node_type_tex_proc_distnoise(ntypelist);
1934 }
1935
1936 static void free_dynamic_typeinfo(bNodeType *ntype)
1937 {
1938         if(ntype->type==NODE_DYNAMIC) {
1939                 if(ntype->inputs) {
1940                         MEM_freeN(ntype->inputs);
1941                 }
1942                 if(ntype->outputs) {
1943                         MEM_freeN(ntype->outputs);
1944                 }
1945                 if(ntype->name) {
1946                         MEM_freeN((void *)ntype->name);
1947                 }
1948         }
1949 }
1950
1951 static void free_typeinfos(ListBase *list)
1952 {
1953         bNodeType *ntype, *next;
1954         for(ntype=list->first; ntype; ntype=next) {
1955                 next = ntype->next;
1956                 
1957                 if(ntype->type==NODE_DYNAMIC)
1958                         free_dynamic_typeinfo(ntype);
1959                 
1960                 if(ntype->needs_free)
1961                         MEM_freeN(ntype);
1962         }
1963 }
1964
1965 void init_nodesystem(void) 
1966 {
1967         registerCompositNodes(&ntreeGetType(NTREE_COMPOSIT)->node_types);
1968         registerShaderNodes(&ntreeGetType(NTREE_SHADER)->node_types);
1969         registerTextureNodes(&ntreeGetType(NTREE_TEXTURE)->node_types);
1970 }
1971
1972 void free_nodesystem(void) 
1973 {
1974         free_typeinfos(&ntreeGetType(NTREE_COMPOSIT)->node_types);
1975         free_typeinfos(&ntreeGetType(NTREE_SHADER)->node_types);
1976         free_typeinfos(&ntreeGetType(NTREE_TEXTURE)->node_types);
1977 }
1978
1979 /* called from unlink_scene, when deleting a scene goes over all scenes
1980  * other than the input, checks if they have render layer nodes referencing
1981  * the to-be-deleted scene, and resets them to NULL. */
1982
1983 /* XXX needs to get current scene then! */
1984 void clear_scene_in_nodes(Main *bmain, Scene *sce)
1985 {
1986         Scene *sce1;
1987         bNode *node;
1988
1989         for(sce1= bmain->scene.first; sce1; sce1=sce1->id.next) {
1990                 if(sce1!=sce) {
1991                         if(sce1->nodetree) {
1992                                 for(node= sce1->nodetree->nodes.first; node; node= node->next) {
1993                                         if(node->type==CMP_NODE_R_LAYERS) {
1994                                                 Scene *nodesce= (Scene *)node->id;
1995                                                 
1996                                                 if (nodesce==sce) node->id = NULL;
1997                                         }
1998                                 }
1999                         }
2000                 }
2001         }
2002 }
2003