Christmas coding work!
[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
36 #include "BKE_blender.h"
37 #include "BKE_node.h"
38 #include "BKE_utildefines.h"
39
40 #include "BLI_arithb.h"
41 #include "BLI_blenlib.h"
42
43 #include "MEM_guardedalloc.h"
44
45 /* ************** Type stuff ********** */
46
47 static bNodeType *nodeGetType(bNodeTree *ntree, int type)
48 {
49         bNodeType **typedefs= ntree->alltypes;
50         
51         while( *typedefs && (*typedefs)->type!=type)
52                 typedefs++;
53         
54         return *typedefs;
55 }
56
57 void ntreeInitTypes(bNodeTree *ntree)
58 {
59         bNode *node;
60         
61         if(ntree->type==NTREE_SHADER)
62                 ntree->alltypes= node_all_shaders;
63         else {
64                 ntree->alltypes= NULL;
65                 printf("Error: no type definitions for nodes\n");
66         }
67         
68         for(node= ntree->nodes.first; node; node= node->next) {
69                 node->typeinfo= nodeGetType(ntree, node->type);
70                 if(node->typeinfo==NULL)
71                         printf("Error: no typeinfo for node %s\n", node->name);
72         }
73                         
74         ntree->init |= NTREE_TYPE_INIT;
75 }
76
77 /* only used internal... we depend on type definitions! */
78 static bNodeSocket *node_add_socket_type(ListBase *lb, bNodeSocketType *stype)
79 {
80         bNodeSocket *sock= MEM_callocN(sizeof(bNodeSocket), "sock");
81         
82         BLI_strncpy(sock->name, stype->name, NODE_MAXSTR);
83         if(stype->limit==0) sock->limit= 0xFFF;
84         else sock->limit= stype->limit;
85         sock->type= stype->type;
86         
87         sock->ns.vec[0]= stype->val1;
88         sock->ns.vec[1]= stype->val2;
89         sock->ns.vec[2]= stype->val3;
90         sock->ns.vec[3]= stype->val4;
91                                 
92         if(lb)
93                 BLI_addtail(lb, sock);
94         
95         return sock;
96 }
97
98 static void node_rem_socket(bNodeTree *ntree, ListBase *lb, bNodeSocket *sock)
99 {
100         bNodeLink *link, *next;
101         
102         for(link= ntree->links.first; link; link= next) {
103                 next= link->next;
104                 if(link->fromsock==sock || link->tosock==sock) {
105                         nodeRemLink(ntree, link);
106                 }
107         }
108         
109         BLI_remlink(lb, sock);
110         MEM_freeN(sock);
111 }
112
113 static bNodeSocket *verify_socket(ListBase *lb, bNodeSocketType *stype)
114 {
115         bNodeSocket *sock;
116         
117         for(sock= lb->first; sock; sock= sock->next) {
118                 if(strncmp(sock->name, stype->name, NODE_MAXSTR)==0)
119                         break;
120         }
121         if(sock) {
122                 sock->type= stype->type;                /* in future, read this from tydefs! */
123                 if(stype->limit==0) sock->limit= 0xFFF;
124                 else sock->limit= stype->limit;
125                 BLI_remlink(lb, sock);
126                 return sock;
127         }
128         else {
129                 return node_add_socket_type(NULL, stype);
130         }
131 }
132
133 static void verify_socket_list(bNodeTree *ntree, ListBase *lb, bNodeSocketType *stype_first)
134 {
135         bNodeSocketType *stype;
136         
137         /* no inputs anymore? */
138         if(stype_first==NULL) {
139                 while(lb->first)
140                         node_rem_socket(ntree, lb, lb->first);
141         }
142         else {
143                 /* step by step compare */
144                 stype= stype_first;
145                 while(stype->type != -1) {
146                         stype->sock= verify_socket(lb, stype);
147                         stype++;
148                 }
149                 /* leftovers are removed */
150                 while(lb->first)
151                         node_rem_socket(ntree, lb, lb->first);
152                 /* and we put back the verified sockets */
153                 stype= stype_first;
154                 while(stype->type != -1) {
155                         BLI_addtail(lb, stype->sock);
156                         stype++;
157                 }
158         }
159 }
160
161 void ntreeVerifyTypes(bNodeTree *ntree)
162 {
163         bNode *node;
164         bNodeType *ntype;
165         
166         if((ntree->init & NTREE_TYPE_INIT)==0)
167                 ntreeInitTypes(ntree);
168         
169         /* check inputs and outputs, and remove or insert them */
170         for(node= ntree->nodes.first; node; node= node->next) {
171                 ntype= node->typeinfo;
172                 if(ntype) {
173                         /* might add some other verify stuff here */
174                         
175                         verify_socket_list(ntree, &node->inputs, ntype->inputs);
176                         verify_socket_list(ntree, &node->outputs, ntype->outputs);
177                 }
178         }
179 }
180
181
182
183 /* ************** Add stuff ********** */
184
185 /* not very important, but the stack solver likes to know a maximum */
186 #define MAX_SOCKET      64
187
188 bNode *nodeAddNodeType(bNodeTree *ntree, int type)
189 {
190         bNode *node;
191         bNodeType *ntype= nodeGetType(ntree, type);
192         bNodeSocketType *stype;
193         
194         node= MEM_callocN(sizeof(bNode), "new node");
195         BLI_addtail(&ntree->nodes, node);
196         node->typeinfo= ntype;
197         
198         BLI_strncpy(node->name, ntype->name, NODE_MAXSTR);
199         node->type= ntype->type;
200         node->flag= NODE_SELECT|ntype->flag;
201         node->width= ntype->width;
202
203         if(ntype->inputs) {
204                 stype= ntype->inputs;
205                 while(stype->type != -1) {
206                         node_add_socket_type(&node->inputs, stype);
207                         stype++;
208                 }
209         }
210         if(ntype->outputs) {
211                 stype= ntype->outputs;
212                 while(stype->type != -1) {
213                         node_add_socket_type(&node->outputs, stype);
214                         stype++;
215                 }
216         }
217         return node;
218 }
219
220 /* keep socket listorder identical, for copying links */
221 /* ntree is the target tree */
222 bNode *nodeCopyNode(struct bNodeTree *ntree, struct bNode *node)
223 {
224         bNode *nnode= MEM_callocN(sizeof(bNode), "dupli node");
225         
226         *nnode= *node;
227         BLI_addtail(&ntree->nodes, nnode);
228         
229         duplicatelist(&nnode->inputs, &node->inputs);
230         duplicatelist(&nnode->outputs, &node->outputs);
231         if(nnode->id)
232                 nnode->id->us++;
233         
234         if(nnode->storage)
235                 nnode->storage= MEM_dupallocN(nnode->storage);
236         
237         node->new= nnode;
238         nnode->new= NULL;
239         nnode->preview= NULL;
240         
241         return nnode;
242 }
243
244 bNodeLink *nodeAddLink(bNodeTree *ntree, bNode *fromnode, bNodeSocket *fromsock, bNode *tonode, bNodeSocket *tosock)
245 {
246         bNodeLink *link= MEM_callocN(sizeof(bNodeLink), "link");
247         
248         BLI_addtail(&ntree->links, link);
249         link->fromnode= fromnode;
250         link->fromsock= fromsock;
251         link->tonode= tonode;
252         link->tosock= tosock;
253         
254         return link;
255 }
256
257 void nodeRemLink(bNodeTree *ntree, bNodeLink *link)
258 {
259         BLI_remlink(&ntree->links, link);
260         if(link->tosock)
261                 link->tosock->link= NULL;
262         MEM_freeN(link);
263 }
264
265
266 bNodeTree *ntreeAddTree(int type)
267 {
268         bNodeTree *ntree= MEM_callocN(sizeof(bNodeTree), "new node tree");
269         ntree->type= type;
270         
271         ntreeInitTypes(ntree);
272         return ntree;
273 }
274
275 /* ************** Free stuff ********** */
276
277 /* goes over entire tree */
278 static void node_unlink_node(bNodeTree *ntree, bNode *node)
279 {
280         bNodeLink *link, *next;
281         bNodeSocket *sock;
282         ListBase *lb;
283         
284         for(link= ntree->links.first; link; link= next) {
285                 next= link->next;
286                 
287                 if(link->fromnode==node)
288                         lb= &node->outputs;
289                 else if(link->tonode==node)
290                         lb= &node->inputs;
291                 else
292                         lb= NULL;
293
294                 if(lb) {
295                         for(sock= lb->first; sock; sock= sock->next) {
296                                 if(link->fromsock==sock || link->tosock==sock)
297                                         break;
298                         }
299                         if(sock) {
300                                 nodeRemLink(ntree, link);
301                         }
302                 }
303         }
304 }
305
306 void nodeFreeNode(bNodeTree *ntree, bNode *node)
307 {
308         if(ntree) {
309                 node_unlink_node(ntree, node);
310                 BLI_remlink(&ntree->nodes, node);
311         }
312         if(node->id)
313                 node->id->us--;
314         
315         BLI_freelistN(&node->inputs);
316         BLI_freelistN(&node->outputs);
317         
318         if(node->preview) {
319                 if(node->preview->rect)
320                         MEM_freeN(node->preview->rect);
321                 MEM_freeN(node->preview);
322         }
323         if(node->storage)
324                 MEM_freeN(node->storage);
325         
326         MEM_freeN(node);
327 }
328
329 void ntreeFreeTree(bNodeTree *ntree)
330 {
331         bNode *node, *next;
332         
333         for(node= ntree->nodes.first; node; node= next) {
334                 next= node->next;
335                 nodeFreeNode(NULL, node);               /* NULL -> no unlinking needed */
336         }
337         BLI_freelistN(&ntree->links);
338         
339         MEM_freeN(ntree);
340 }
341
342 bNodeTree *ntreeCopyTree(bNodeTree *ntree, int internal_select)
343 {
344         bNodeTree *newtree;
345         bNode *node, *nnode, *last;
346         bNodeLink *link, *nlink;
347         bNodeSocket *sock;
348         int a;
349         
350         if(ntree==NULL) return NULL;
351         
352         if(internal_select==0) {
353                 newtree= MEM_dupallocN(ntree);
354                 newtree->nodes.first= newtree->nodes.last= NULL;
355                 newtree->links.first= newtree->links.last= NULL;
356         }
357         else
358                 newtree= ntree;
359         
360         last= ntree->nodes.last;
361         for(node= ntree->nodes.first; node; node= node->next) {
362                 
363                 node->new= NULL;
364                 if(internal_select==0 || (node->flag & NODE_SELECT)) {
365                         nnode= nodeCopyNode(newtree, node);     /* sets node->new */
366                         if(internal_select) {
367                                 node->flag &= ~NODE_SELECT;
368                                 nnode->flag |= NODE_SELECT;
369                         }
370                         node->flag &= ~NODE_ACTIVE;
371                 }
372                 if(node==last) break;
373         }
374         
375         /* check for copying links */
376         for(link= ntree->links.first; link; link= link->next) {
377                 if(link->fromnode->new && link->tonode->new) {
378                         nlink= nodeAddLink(newtree, link->fromnode->new, NULL, link->tonode->new, NULL);
379                         /* sockets were copied in order */
380                         for(a=0, sock= link->fromnode->outputs.first; sock; sock= sock->next, a++) {
381                                 if(sock==link->fromsock)
382                                         break;
383                         }
384                         nlink->fromsock= BLI_findlink(&link->fromnode->new->outputs, a);
385                         
386                         for(a=0, sock= link->tonode->inputs.first; sock; sock= sock->next, a++) {
387                                 if(sock==link->tosock)
388                                         break;
389                         }
390                         nlink->tosock= BLI_findlink(&link->tonode->new->inputs, a);
391                 }
392         }
393         return newtree;
394 }
395
396 /* ************ find stuff *************** */
397
398 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
399 {
400         bNodeLink *link;
401         
402         for(link= ntree->links.first; link; link= link->next) {
403                 if(link->fromsock==from && link->tosock==to)
404                         return link;
405                 if(link->fromsock==to && link->tosock==from)    /* hrms? */
406                         return link;
407         }
408         return NULL;
409 }
410
411 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
412 {
413         bNodeLink *link;
414         int tot= 0;
415         
416         for(link= ntree->links.first; link; link= link->next) {
417                 if(link->fromsock==sock || link->tosock==sock)
418                         tot++;
419         }
420         return tot;
421 }
422
423 bNode *nodeGetActive(bNodeTree *ntree)
424 {
425         bNode *node;
426         
427         if(ntree==NULL) return NULL;
428         
429         for(node= ntree->nodes.first; node; node= node->next)
430                 if(node->flag & NODE_ACTIVE)
431                         break;
432         return node;
433 }
434
435 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
436 {
437         bNode *node;
438         
439         if(ntree==NULL) return NULL;
440         
441         for(node= ntree->nodes.first; node; node= node->next)
442                 if(node->id && GS(node->id->name)==idtype)
443                         if(node->flag & NODE_ACTIVE_ID)
444                                 break;
445         return node;
446 }
447
448 /* ************** dependency stuff *********** */
449
450 /* node is guaranteed to be not checked before */
451 static int node_recurs_check(bNode *node, bNode ***nsort, int level)
452 {
453         bNode *fromnode;
454         bNodeSocket *sock;
455         int has_inputlinks= 0;
456         
457         node->done= 1;
458         level++;
459         
460         for(sock= node->inputs.first; sock; sock= sock->next) {
461                 if(sock->link) {
462                         has_inputlinks= 1;
463                         fromnode= sock->link->fromnode;
464                         if(fromnode->done==0) {
465                                 fromnode->level= node_recurs_check(fromnode, nsort, level);
466                         }
467                 }
468         }
469 //      printf("node sort %s level %d\n", node->name, level);
470         **nsort= node;
471         (*nsort)++;
472         
473         if(has_inputlinks)
474                 return level;
475         else 
476                 return 0xFFF;
477 }
478
479 void ntreeSolveOrder(bNodeTree *ntree)
480 {
481         bNode *node, **nodesort, **nsort;
482         bNodeSocket *sock;
483         bNodeLink *link;
484         int a, totnode=0;
485         
486         /* set links pointers the input sockets, to find dependencies */
487         /* first clear data */
488         for(node= ntree->nodes.first; node; node= node->next) {
489                 node->done= 0;
490                 totnode++;
491                 for(sock= node->inputs.first; sock; sock= sock->next)
492                         sock->link= NULL;
493         }
494         if(totnode==0)
495                 return;
496         
497         for(link= ntree->links.first; link; link= link->next) {
498                 link->tosock->link= link;
499         }
500         
501         nsort= nodesort= MEM_callocN(totnode*sizeof(void *), "sorted node array");
502         
503         /* recursive check */
504         for(node= ntree->nodes.first; node; node= node->next) {
505                 if(node->done==0) {
506                         node->level= node_recurs_check(node, &nsort, 0);
507                 }
508         }
509         
510         /* re-insert nodes in order, first a paranoia check */
511         for(a=0; a<totnode; a++) {
512                 if(nodesort[a]==NULL)
513                         break;
514         }
515         if(a<totnode)
516                 printf("sort error in node tree");
517         else {
518                 ntree->nodes.first= ntree->nodes.last= NULL;
519                 for(a=0; a<totnode; a++)
520                         BLI_addtail(&ntree->nodes, nodesort[a]);
521         }
522         
523         MEM_freeN(nodesort);
524         
525         /* find the active outputs, tree type dependant, might become handler */
526         if(ntree->type==NTREE_SHADER) {
527                 /* shader nodes only accepts one output */
528                 int output= 0;
529                 
530                 for(node= ntree->nodes.first; node; node= node->next) {
531                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
532                                 if(output==0)
533                                         node->flag |= NODE_DO_OUTPUT;
534                                 else
535                                         node->flag &= ~NODE_DO_OUTPUT;
536                                 output= 1;
537                         }
538                 }
539         }
540         
541         /* here we could recursively set which nodes have to be done,
542                 might be different for editor or for "real" use... */
543         
544         
545         
546 }
547
548 /* *************** preview *********** */
549
550 /* if node->preview, then we assume the rect to exist */
551
552 static void nodeInitPreview(bNode *node, int xsize, int ysize)
553 {
554         /* signal we don't do anything, preview writing is protected */
555         if(xsize==0 || ysize==0)
556                 return;
557         
558         /* sanity checks & initialize */
559         if(node->preview) {
560                 if(node->preview->xsize!=xsize && node->preview->ysize!=ysize) {
561                         MEM_freeN(node->preview->rect);
562                         node->preview->rect= NULL;
563                 }
564         }
565         
566         if(node->preview==NULL) {
567                 node->preview= MEM_callocN(sizeof(bNodePreview), "node preview");
568         }
569         if(node->preview->rect==NULL) {
570                 node->preview->rect= MEM_callocN(4*xsize + xsize*ysize*sizeof(float)*4, "node preview rect");
571                 node->preview->xsize= xsize;
572                 node->preview->ysize= ysize;
573         }
574 }
575
576 void nodeAddToPreview(bNode *node, float *col, int x, int y)
577 {
578         bNodePreview *preview= node->preview;
579         if(preview) {
580                 if(x>=0 && y>=0) {
581                         if(x<preview->xsize && y<preview->ysize) {
582                                 float *tar= preview->rect+ 4*((preview->xsize*y) + x);
583                                 QUATCOPY(tar, col);
584                         }
585                         else printf("prv out bound x y %d %d\n", x, y);
586                 }
587                 else printf("prv out bound x y %d %d\n", x, y);
588         }
589 }
590
591
592
593 /* ******************* executing ************* */
594
595
596 void ntreeBeginExecTree(bNodeTree *ntree, int xsize, int ysize)
597 {
598         bNode *node;
599         bNodeSocket *sock;
600         int index= 0;
601         
602         if((ntree->init & NTREE_TYPE_INIT)==0)
603                 ntreeInitTypes(ntree);
604         
605         /* create indices for stack, check preview */
606         for(node= ntree->nodes.first; node; node= node->next) {
607                 for(sock= node->outputs.first; sock; sock= sock->next) {
608                         sock->stack_index= index++;
609                 }
610                 
611                 if(node->typeinfo->flag & NODE_PREVIEW) /* hrms, check for closed nodes? */
612                         nodeInitPreview(node, xsize, ysize);
613                 
614         }
615         if(index) {
616                 bNodeStack *ns;
617                 int a;
618                 
619                 ns=ntree->stack= MEM_callocN(index*sizeof(bNodeStack), "node stack");
620                 for(a=0; a<index; a++, ns++) ns->hasinput= 1;
621         }
622         
623         ntree->init |= NTREE_EXEC_INIT;
624 }
625
626 void ntreeEndExecTree(bNodeTree *ntree)
627 {
628         if(ntree->stack) {
629                 MEM_freeN(ntree->stack);
630                 ntree->stack= NULL;
631         }
632
633         ntree->init &= ~NTREE_EXEC_INIT;
634 }
635
636 static void node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out)
637 {
638         bNodeSocket *sock;
639         
640         /* build pointer stack */
641         for(sock= node->inputs.first; sock; sock= sock->next) {
642                 if(sock->link)
643                         *(in++)= stack + sock->link->fromsock->stack_index;
644                 else
645                         *(in++)= &sock->ns;
646         }
647         
648         for(sock= node->outputs.first; sock; sock= sock->next) {
649                 *(out++)= stack + sock->stack_index;
650         }
651 }
652
653 /* nodes are presorted, so exec is in order of list */
654 void ntreeExecTree(bNodeTree *ntree)
655 {
656         bNode *node;
657         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
658         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
659         
660         /* only when initialized */
661         if(ntree->init & NTREE_EXEC_INIT) {
662         
663                 for(node= ntree->nodes.first; node; node= node->next) {
664                         if(node->typeinfo->execfunc) {
665                                 node_get_stack(node, ntree->stack, nsin, nsout);
666                                 node->typeinfo->execfunc(ntree->data, node, nsin, nsout);
667                         }
668                 }
669         }
670 }
671
672 /* clear one pixel in all the preview images */
673 void ntreeClearPixelTree(bNodeTree *ntree, int x, int y)
674 {
675         bNode *node;
676         float vec[4]= {0.0f, 0.0f, 0.0f, 0.0f};
677         
678         /* only when initialized */
679         if(ntree->init & NTREE_EXEC_INIT) {
680                 for(node= ntree->nodes.first; node; node= node->next) {
681                         if(node->preview)
682                                 nodeAddToPreview(node, vec, x, y);
683                 }
684         }
685 }