Merging r46096 through r46110 from trunk into soc-2011-tomato
[blender-staging.git] / intern / cycles / render / graph.cpp
1 /*
2  * Copyright 2011, Blender Foundation.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  */
18
19 #include "attribute.h"
20 #include "graph.h"
21 #include "nodes.h"
22
23 #include "util_algorithm.h"
24 #include "util_debug.h"
25 #include "util_foreach.h"
26
27 CCL_NAMESPACE_BEGIN
28
29 /* Input and Output */
30
31 ShaderInput::ShaderInput(ShaderNode *parent_, const char *name_, ShaderSocketType type_)
32 {
33         parent = parent_;
34         name = name_;
35         type = type_;
36         link = NULL;
37         value = make_float3(0, 0, 0);
38         stack_offset = SVM_STACK_INVALID;
39         default_value = NONE;
40         osl_only = false;
41 }
42
43 ShaderOutput::ShaderOutput(ShaderNode *parent_, const char *name_, ShaderSocketType type_)
44 {
45         parent = parent_;
46         name = name_;
47         type = type_;
48         stack_offset = SVM_STACK_INVALID;
49 }
50
51 /* Node */
52
53 ShaderNode::ShaderNode(const char *name_)
54 {
55         name = name_;
56         id = -1;
57         bump = SHADER_BUMP_NONE;
58 }
59
60 ShaderNode::~ShaderNode()
61 {
62         foreach(ShaderInput *socket, inputs)
63                 delete socket;
64
65         foreach(ShaderOutput *socket, outputs)
66                 delete socket;
67 }
68
69 ShaderInput *ShaderNode::input(const char *name)
70 {
71         foreach(ShaderInput *socket, inputs)
72                 if(strcmp(socket->name, name) == 0)
73                         return socket;
74
75         return NULL;
76 }
77
78 ShaderOutput *ShaderNode::output(const char *name)
79 {
80         foreach(ShaderOutput *socket, outputs)
81                 if(strcmp(socket->name, name) == 0)
82                         return socket;
83
84         return NULL;
85 }
86
87 ShaderInput *ShaderNode::add_input(const char *name, ShaderSocketType type, float value)
88 {
89         ShaderInput *input = new ShaderInput(this, name, type);
90         input->value.x = value;
91         inputs.push_back(input);
92         return input;
93 }
94
95 ShaderInput *ShaderNode::add_input(const char *name, ShaderSocketType type, float3 value)
96 {
97         ShaderInput *input = new ShaderInput(this, name, type);
98         input->value = value;
99         inputs.push_back(input);
100         return input;
101 }
102
103 ShaderInput *ShaderNode::add_input(const char *name, ShaderSocketType type, ShaderInput::DefaultValue value, bool osl_only)
104 {
105         ShaderInput *input = add_input(name, type);
106         input->default_value = value;
107         input->osl_only = osl_only;
108         return input;
109 }
110
111 ShaderOutput *ShaderNode::add_output(const char *name, ShaderSocketType type)
112 {
113         ShaderOutput *output = new ShaderOutput(this, name, type);
114         outputs.push_back(output);
115         return output;
116 }
117
118 void ShaderNode::attributes(AttributeRequestSet *attributes)
119 {
120         foreach(ShaderInput *input, inputs) {
121                 if(!input->link) {
122                         if(input->default_value == ShaderInput::TEXTURE_GENERATED)
123                                 attributes->add(Attribute::STD_GENERATED);
124                         else if(input->default_value == ShaderInput::TEXTURE_UV)
125                                 attributes->add(Attribute::STD_UV);
126                 }
127         }
128 }
129
130 /* Graph */
131
132 ShaderGraph::ShaderGraph()
133 {
134         finalized = false;
135         add(new OutputNode());
136 }
137
138 ShaderGraph::~ShaderGraph()
139 {
140         foreach(ShaderNode *node, nodes)
141                 delete node;
142 }
143
144 ShaderNode *ShaderGraph::add(ShaderNode *node)
145 {
146         assert(!finalized);
147         node->id = nodes.size();
148         nodes.push_back(node);
149         return node;
150 }
151
152 ShaderNode *ShaderGraph::output()
153 {
154         return nodes.front();
155 }
156
157 ShaderGraph *ShaderGraph::copy()
158 {
159         ShaderGraph *newgraph = new ShaderGraph();
160
161         /* copy nodes */
162         set<ShaderNode*> nodes_all;
163         foreach(ShaderNode *node, nodes)
164                 nodes_all.insert(node);
165
166         map<ShaderNode*, ShaderNode*> nodes_copy;
167         copy_nodes(nodes_all, nodes_copy);
168
169         /* add nodes (in same order, so output is still first) */
170         newgraph->nodes.clear();
171         foreach(ShaderNode *node, nodes)
172                 newgraph->add(nodes_copy[node]);
173
174         return newgraph;
175 }
176
177 void ShaderGraph::connect(ShaderOutput *from, ShaderInput *to)
178 {
179         assert(!finalized);
180         assert(from && to);
181
182         if(to->link) {
183                 fprintf(stderr, "ShaderGraph connect: input already connected.\n");
184                 return;
185         }
186
187         if(from->type != to->type) {
188                 /* for closures we can't do automatic conversion */
189                 if(from->type == SHADER_SOCKET_CLOSURE || to->type == SHADER_SOCKET_CLOSURE) {
190                         fprintf(stderr, "ShaderGraph connect: can only connect closure to closure.\n");
191                         return;
192                 }
193
194                 /* add automatic conversion node in case of type mismatch */
195                 ShaderNode *convert = add(new ConvertNode(from->type, to->type));
196
197                 connect(from, convert->inputs[0]);
198                 connect(convert->outputs[0], to);
199         }
200         else {
201                 /* types match, just connect */
202                 to->link = from;
203                 from->links.push_back(to);
204         }
205 }
206
207 void ShaderGraph::disconnect(ShaderInput *to)
208 {
209         assert(!finalized);
210         assert(to->link);
211
212         ShaderOutput *from = to->link;
213
214         to->link = NULL;
215         from->links.erase(remove(from->links.begin(), from->links.end(), to), from->links.end());
216 }
217
218 void ShaderGraph::finalize(bool do_bump, bool do_osl)
219 {
220         /* before compiling, the shader graph may undergo a number of modifications.
221          * currently we set default geometry shader inputs, and create automatic bump
222          * from displacement. a graph can be finalized only once, and should not be
223          * modified afterwards. */
224
225         if(!finalized) {
226                 clean();
227                 default_inputs(do_osl);
228                 if(do_bump)
229                         bump_from_displacement();
230
231                 finalized = true;
232         }
233 }
234
235 void ShaderGraph::find_dependencies(set<ShaderNode*>& dependencies, ShaderInput *input)
236 {
237         /* find all nodes that this input dependes on directly and indirectly */
238         ShaderNode *node = (input->link)? input->link->parent: NULL;
239
240         if(node) {
241                 foreach(ShaderInput *in, node->inputs)
242                         find_dependencies(dependencies, in);
243
244                 dependencies.insert(node);
245         }
246 }
247
248 void ShaderGraph::copy_nodes(set<ShaderNode*>& nodes, map<ShaderNode*, ShaderNode*>& nnodemap)
249 {
250         /* copy a set of nodes, and the links between them. the assumption is
251          * made that all nodes that inputs are linked to are in the set too. */
252
253         /* copy nodes */
254         foreach(ShaderNode *node, nodes) {
255                 ShaderNode *nnode = node->clone();
256                 nnodemap[node] = nnode;
257
258                 nnode->inputs.clear();
259                 nnode->outputs.clear();
260
261                 foreach(ShaderInput *input, node->inputs) {
262                         ShaderInput *ninput = new ShaderInput(*input);
263                         nnode->inputs.push_back(ninput);
264
265                         ninput->parent = nnode;
266                         ninput->link = NULL;
267                 }
268
269                 foreach(ShaderOutput *output, node->outputs) {
270                         ShaderOutput *noutput = new ShaderOutput(*output);
271                         nnode->outputs.push_back(noutput);
272
273                         noutput->parent = nnode;
274                         noutput->links.clear();
275                 }
276         }
277
278         /* recreate links */
279         foreach(ShaderNode *node, nodes) {
280                 foreach(ShaderInput *input, node->inputs) {
281                         if(input->link) {
282                                 /* find new input and output */
283                                 ShaderNode *nfrom = nnodemap[input->link->parent];
284                                 ShaderNode *nto = nnodemap[input->parent];
285                                 ShaderOutput *noutput = nfrom->output(input->link->name);
286                                 ShaderInput *ninput = nto->input(input->name);
287
288                                 /* connect */
289                                 connect(noutput, ninput);
290                         }
291                 }
292         }
293 }
294
295 void ShaderGraph::remove_proxy_nodes(vector<bool>& removed)
296 {
297         foreach(ShaderNode *node, nodes) {
298                 ProxyNode *proxy = dynamic_cast<ProxyNode*>(node);
299                 if (proxy) {
300                         ShaderInput *input = proxy->inputs[0];
301                         ShaderOutput *output = proxy->outputs[0];
302                         
303                         /* temp. copy of the output links list.
304                          * output->links is modified when we disconnect!
305                          */
306                         vector<ShaderInput*> links(output->links);
307                         ShaderOutput *from = input->link;
308                         
309                         /* bypass the proxy node */
310                         if (from) {
311                                 disconnect(input);
312                                 foreach(ShaderInput *to, links) {
313                                         disconnect(to);
314                                         connect(from, to);
315                                 }
316                         }
317                         else {
318                                 foreach(ShaderInput *to, links) {
319                                         disconnect(to);
320                                         
321                                         /* transfer the default input value to the target socket */
322                                         to->set(input->value);
323                                 }
324                         }
325                         
326                         removed[proxy->id] = true;
327                 }
328         }
329 }
330
331 void ShaderGraph::break_cycles(ShaderNode *node, vector<bool>& visited, vector<bool>& on_stack)
332 {
333         visited[node->id] = true;
334         on_stack[node->id] = true;
335
336         foreach(ShaderInput *input, node->inputs) {
337                 if(input->link) {
338                         ShaderNode *depnode = input->link->parent;
339
340                         if(on_stack[depnode->id]) {
341                                 /* break cycle */
342                                 disconnect(input);
343                                 fprintf(stderr, "ShaderGraph: detected cycle in graph, connection removed.\n");
344                         }
345                         else if(!visited[depnode->id]) {
346                                 /* visit dependencies */
347                                 break_cycles(depnode, visited, on_stack);
348                         }
349                 }
350         }
351
352         on_stack[node->id] = false;
353 }
354
355 void ShaderGraph::clean()
356 {
357         /* we do two things here: find cycles and break them, and remove unused
358            nodes that don't feed into the output. how cycles are broken is
359            undefined, they are invalid input, the important thing is to not crash */
360
361         vector<bool> removed(nodes.size(), false);
362         vector<bool> visited(nodes.size(), false);
363         vector<bool> on_stack(nodes.size(), false);
364         
365         list<ShaderNode*> newnodes;
366         
367         /* remove proxy nodes */
368         remove_proxy_nodes(removed);
369         
370         foreach(ShaderNode *node, nodes) {
371                 if(!removed[node->id])
372                         newnodes.push_back(node);
373                 else
374                         delete node;
375         }
376         nodes = newnodes;
377         newnodes.clear();
378
379         /* break cycles */
380         break_cycles(output(), visited, on_stack);
381
382         /* remove unused nodes */
383         foreach(ShaderNode *node, nodes) {
384                 if(visited[node->id])
385                         newnodes.push_back(node);
386                 else
387                         delete node;
388         }
389         
390         nodes = newnodes;
391 }
392
393 void ShaderGraph::default_inputs(bool do_osl)
394 {
395         /* nodes can specify default texture coordinates, for now we give
396          * everything the position by default, except for the sky texture */
397
398         ShaderNode *geom = NULL;
399         ShaderNode *texco = NULL;
400
401         foreach(ShaderNode *node, nodes) {
402                 foreach(ShaderInput *input, node->inputs) {
403                         if(!input->link && !(input->osl_only && !do_osl)) {
404                                 if(input->default_value == ShaderInput::TEXTURE_GENERATED) {
405                                         if(!texco)
406                                                 texco = new TextureCoordinateNode();
407
408                                         connect(texco->output("Generated"), input);
409                                 }
410                                 else if(input->default_value == ShaderInput::TEXTURE_UV) {
411                                         if(!texco)
412                                                 texco = new TextureCoordinateNode();
413
414                                         connect(texco->output("UV"), input);
415                                 }
416                                 else if(input->default_value == ShaderInput::INCOMING) {
417                                         if(!geom)
418                                                 geom = new GeometryNode();
419
420                                         connect(geom->output("Incoming"), input);
421                                 }
422                                 else if(input->default_value == ShaderInput::NORMAL) {
423                                         if(!geom)
424                                                 geom = new GeometryNode();
425
426                                         connect(geom->output("Normal"), input);
427                                 }
428                                 else if(input->default_value == ShaderInput::POSITION) {
429                                         if(!geom)
430                                                 geom = new GeometryNode();
431
432                                         connect(geom->output("Position"), input);
433                                 }
434                         }
435                 }
436         }
437
438         if(geom)
439                 add(geom);
440         if(texco)
441                 add(texco);
442 }
443
444 void ShaderGraph::bump_from_displacement()
445 {
446         /* generate bump mapping automatically from displacement. bump mapping is
447          * done using a 3-tap filter, computing the displacement at the center,
448          * and two other positions shifted by ray differentials.
449          *
450          * since the input to displacement is a node graph, we need to ensure that
451          * all texture coordinates use are shift by the ray differentials. for this
452          * reason we make 3 copies of the node subgraph defining the displacement,
453          * with each different geometry and texture coordinate nodes that generate
454          * different shifted coordinates.
455          *
456          * these 3 displacement values are then fed into the bump node, which will
457          * modify the normal. */
458
459         ShaderInput *displacement_in = output()->input("Displacement");
460
461         if(!displacement_in->link)
462                 return;
463         
464         /* find dependencies for the given input */
465         set<ShaderNode*> nodes_displace;
466         find_dependencies(nodes_displace, displacement_in);
467
468         /* copy nodes for 3 bump samples */
469         map<ShaderNode*, ShaderNode*> nodes_center;
470         map<ShaderNode*, ShaderNode*> nodes_dx;
471         map<ShaderNode*, ShaderNode*> nodes_dy;
472
473         copy_nodes(nodes_displace, nodes_center);
474         copy_nodes(nodes_displace, nodes_dx);
475         copy_nodes(nodes_displace, nodes_dy);
476
477         /* mark nodes to indicate they are use for bump computation, so
478            that any texture coordinates are shifted by dx/dy when sampling */
479         foreach(NodePair& pair, nodes_center)
480                 pair.second->bump = SHADER_BUMP_CENTER;
481         foreach(NodePair& pair, nodes_dx)
482                 pair.second->bump = SHADER_BUMP_DX;
483         foreach(NodePair& pair, nodes_dy)
484                 pair.second->bump = SHADER_BUMP_DY;
485
486         /* add bump node and connect copied graphs to it */
487         ShaderNode *bump = add(new BumpNode());
488
489         ShaderOutput *out = displacement_in->link;
490         ShaderOutput *out_center = nodes_center[out->parent]->output(out->name);
491         ShaderOutput *out_dx = nodes_dx[out->parent]->output(out->name);
492         ShaderOutput *out_dy = nodes_dy[out->parent]->output(out->name);
493
494         connect(out_center, bump->input("SampleCenter"));
495         connect(out_dx, bump->input("SampleX"));
496         connect(out_dy, bump->input("SampleY"));
497
498         /* connect bump output to normal input nodes that aren't set yet. actually
499            this will only set the normal input to the geometry node that we created
500            and connected to all other normal inputs already. */
501         foreach(ShaderNode *node, nodes)
502                 foreach(ShaderInput *input, node->inputs)
503                         if(!input->link && input->default_value == ShaderInput::NORMAL)
504                                 connect(bump->output("Normal"), input);
505         
506         /* finally, add the copied nodes to the graph. we can't do this earlier
507            because we would create dependency cycles in the above loop */
508         foreach(NodePair& pair, nodes_center)
509                 add(pair.second);
510         foreach(NodePair& pair, nodes_dx)
511                 add(pair.second);
512         foreach(NodePair& pair, nodes_dy)
513                 add(pair.second);
514 }
515
516 CCL_NAMESPACE_END
517