Cycles: svn merge -r41225:41232 ^/trunk/blender
[blender.git] / source / blender / editors / space_node / node_layout.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: none of this file.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/space_node/node_layout.c
29  *  \ingroup spnode
30  */
31
32 #include <stdlib.h>
33
34 #include "MEM_guardedalloc.h"
35
36 #include "BLI_utildefines.h"
37
38 #include "DNA_node_types.h"
39
40 #include "ED_node.h"
41
42 /* Inspired by the algorithm for graphviz dot, as described in the paper:
43    "A Technique for Drawing Directed Graphs", 1993
44    
45    We have it much easier though, as the graph is already acyclic, and we
46    are given a root node. */
47
48 typedef struct NodeAutoLayout {
49         int rank;
50         int visited;
51 } NodeAutoLayout;
52
53 static void node_layout_assign_rank(NodeAutoLayout *layout, bNode *from, int rank)
54 {
55         bNodeSocket *sock;
56
57         for(sock=from->inputs.first; sock; sock=sock->next) {
58                 if(sock->link) {
59                         bNode *node = sock->link->fromnode;
60
61                         if(layout[node->nr].visited)
62                                 continue;
63
64                         layout[node->nr].rank= rank;
65                         layout[node->nr].visited= 1;
66
67                         node_layout_assign_rank(layout, node, rank+1);
68                 }
69         }
70 }
71
72 void ED_node_tree_auto_layout(bNodeTree *ntree, bNode *root)
73 {
74         NodeAutoLayout *layout;
75         bNode *node;
76         float locx, locy, hspacing= 50.0f, vspacing= 30.0f;
77         int a, rank, tot= 0, maxrank= 0;
78
79         for(node=ntree->nodes.first; node; node=node->next)
80                 node->nr= tot++;
81         
82         layout= MEM_callocN(sizeof(NodeAutoLayout)*tot, "NodeAutoLayout");
83
84         layout[root->nr].rank= 0;
85         layout[root->nr].visited= 1;
86
87         node_layout_assign_rank(layout, root, layout[root->nr].rank+1);
88
89         for(a=0; a<tot; a++)
90                 maxrank = MAX2(maxrank, layout[a].rank);
91         
92         locx= root->locx;
93         locy= root->locy - (root->totr.ymax - root->totr.ymin)*0.5f;
94         
95         for(rank=1; rank<=maxrank; rank++) {
96                 float maxwidth= 0.0f;
97                 float totheight= 0.0f;
98                 float y;
99
100                 locx -= hspacing;
101
102                 for(node=ntree->nodes.first; node; node=node->next) {
103                         if(layout[node->nr].rank == rank) {
104                                 if(totheight > 0.0f)
105                                         totheight += vspacing;
106                                 totheight += (node->totr.ymax - node->totr.ymin);
107                         }
108                 }
109
110                 y = locy + totheight*0.5f;
111
112                 for(node=ntree->nodes.first; node; node=node->next) {
113                         if(layout[node->nr].rank == rank) {
114                                 maxwidth = MAX2(maxwidth, node->width);
115                                 node->locx = locx - node->width;
116                                 node->locy = y;
117
118                                 y -= (node->totr.ymax - node->totr.ymin);
119                                 y -= vspacing;
120                         }
121                 }
122
123                 locx -= maxwidth;
124         }
125
126         MEM_freeN(layout);
127 }
128