source/blender/blenkernel/intern/node.c

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