Cycles: Implement node deduplication routines

The idea of this commit is to merge nodes which has identical settings
and matching inputs into a single node in order to minimize number of
SVM instructions.

This is quite simple bottom-top graph traversal and the trickiest part
is how to compare node settings without too much trouble which seems to
be solved is quite clean way.

Still possibilities for further improvements:

- Support comparison of BSDF nodes
- Support comparison of volume nodes
- Support comparison of curve mapping/ramp nodes

Reviewers: brecht, juicyfruit, dingto

Differential Revision: https://developer.blender.org/D1673

3 files changed, 381 insertions, 10 deletions

diff --git a/intern/cycles/render/graph.cpp b/intern/cycles/render/graph.cpp
index 7bffb29c77c..f0fb0a2c4f7 100644
--- a/intern/cycles/render/graph.cpp
+++ b/intern/cycles/render/graph.cpp
@@ -51,6 +51,42 @@ bool check_node_inputs_traversed(const ShaderNode *node,
 	return true;
 }
 
+bool check_node_inputs_equals(const ShaderNode *node_a,
+                              const ShaderNode *node_b)
+{
+	if(node_a->inputs.size() != node_b->inputs.size()) {
+		/* Happens with BSDF closure nodes which are currently sharing the same
+		 * name for all the BSDF types, making it impossible to filter out
+		 * incompatible nodes.
+		 */
+		return false;
+	}
+	for(int i = 0; i < node_a->inputs.size(); ++i) {
+		ShaderInput *input_a = node_a->inputs[i],
+		            *input_b = node_b->inputs[i];
+		assert(strcmp(input_a->name, input_b->name) == 0);
+		if(input_a->link == NULL && input_b->link == NULL) {
+			/* Unconnected inputs are expected to have the same value. */
+			if(input_a->value != input_b->value) {
+				return false;
+			}
+		}
+		else if(input_a->link != NULL && input_b->link != NULL) {
+			/* Expect links are to come from the same exact socket. */
+			if(input_a->link != input_b->link) {
+				return false;
+			}
+		}
+		else {
+			/* One socket has a link and another has not, inputs can't be
+			 * considered equal.
+			 */
+			return false;
+		}
+	}
+	return true;
+}
+
 }  /* namespace */
 
 /* Input and Output */
@@ -365,6 +401,7 @@ void ShaderGraph::copy_nodes(ShaderNodeSet& nodes, ShaderNodeMap& nnodemap)
 		}
 	}
 }
+
 /* Graph simplification */
 /* ******************** */
 
@@ -620,7 +657,7 @@ void ShaderGraph::constant_fold()
 	}
 }
 
-/* Step 3: Simplification.*/
+/* Step 3: Simplification. */
 void ShaderGraph::simplify_settings(Scene *scene)
 {
 	foreach(ShaderNode *node, nodes) {
@@ -628,6 +665,77 @@ void ShaderGraph::simplify_settings(Scene *scene)
 	}
 }
 
+/* Step 4: Deduplicate nodes with same settings. */
+void ShaderGraph::deduplicate_nodes()
+{
+	/* NOTES:
+	 * - Deduplication happens for nodes which has same exact settings and same
+	 *   exact input links configuration (either connected to same output or has
+	 *   the same exact default value).
+	 * - Deduplication happens in the bottom-top manner, so we know for fact that
+	 *   all traversed nodes are either can not be deduplicated at all or were
+	 *   already deduplicated.
+	 */
+
+	ShaderNodeSet done, scheduled;
+	queue<ShaderNode*> traverse_queue;
+
+	/* Schedule nodes which doesn't have any dependencies. */
+	foreach(ShaderNode *node, nodes) {
+		if(!check_node_inputs_has_links(node)) {
+			traverse_queue.push(node);
+			scheduled.insert(node);
+		}
+	}
+
+	while(!traverse_queue.empty()) {
+		ShaderNode *node = traverse_queue.front();
+		traverse_queue.pop();
+		done.insert(node);
+		/* Schedule the nodes which were depending on the current node. */
+		foreach(ShaderOutput *output, node->outputs) {
+			foreach(ShaderInput *input, output->links) {
+				if(scheduled.find(input->parent) != scheduled.end()) {
+					/* Node might not be optimized yet but scheduled already
+					 * by other dependencies. No need to re-schedule it.
+					 */
+					continue;
+				}
+				/* Schedule node if its inputs are fully done. */
+				if(check_node_inputs_traversed(input->parent, done)) {
+					traverse_queue.push(input->parent);
+					scheduled.insert(input->parent);
+				}
+			}
+		}
+		/* Try to merge this node with another one. */
+		foreach(ShaderNode *other_node, done) {
+			if(node == other_node) {
+				/* Don't merge with self. */
+				continue;
+			}
+			if(node->name != other_node->name) {
+				/* Can only de-duplicate nodes of the same type. */
+				continue;
+			}
+			if(!check_node_inputs_equals(node, other_node)) {
+				/* Node inputs are different, can't merge them, */
+				continue;
+			}
+			if(!node->equals(other_node)) {
+				/* Node settings are different. */
+				continue;
+			}
+			/* TODO(sergey): Consider making it an utility function. */
+			for(int i = 0; i < node->outputs.size(); ++i) {
+				vector<ShaderInput*> inputs = node->outputs[i]->links;
+				relink(node->inputs, inputs, other_node->outputs[i]);
+			}
+			break;
+		}
+	}
+}
+
 void ShaderGraph::break_cycles(ShaderNode *node, vector<bool>& visited, vector<bool>& on_stack)
 {
 	visited[node->id] = true;
@@ -671,7 +779,7 @@ void ShaderGraph::clean(Scene *scene)
 	simplify_settings(scene);
 
 	/* 4: De-duplication. */
-	/* TODO(dingto): Implement */
+	deduplicate_nodes();
 
 	/* we do two things here: find cycles and break them, and remove unused
 	 * nodes that don't feed into the output. how cycles are broken is
diff --git a/intern/cycles/render/graph.h b/intern/cycles/render/graph.h
index 2f852d6b889..0382cbcfa18 100644
--- a/intern/cycles/render/graph.h
+++ b/intern/cycles/render/graph.h
@@ -238,6 +238,21 @@ public:
 	 * nodes group.
 	 */
 	virtual int get_feature() { return bump == SHADER_BUMP_NONE ? 0 : NODE_FEATURE_BUMP; }
+
+	/* Check whether settings of the node equals to another one.
+	 *
+	 * This is mainly used to check whether two nodes can be merged
+	 * together. Meaning, runtime stuff like node id and unbound slots
+	 * will be ignored for comparison.
+	 *
+	 * NOTE: If some node can't be de-duplicated for whatever reason it
+	 * is to be handled in the subclass.
+	 */
+	virtual bool equals(const ShaderNode *other)
+	{
+		return name == other->name &&
+		       bump == other->bump;
+	}
 };
 
 
@@ -311,13 +326,16 @@ protected:
 	void copy_nodes(ShaderNodeSet& nodes, ShaderNodeMap& nnodemap);
 
 	void break_cycles(ShaderNode *node, vector<bool>& visited, vector<bool>& on_stack);
-	void clean(Scene *scene);
-	void simplify_settings(Scene *scene);
-	void constant_fold();
 	void bump_from_displacement();
 	void refine_bump_nodes();
 	void default_inputs(bool do_osl);
 	void transform_multi_closure(ShaderNode *node, ShaderOutput *weight_out, bool volume);
+
+	/* Graph simplification routines. */
+	void clean(Scene *scene);
+	void constant_fold();
+	void simplify_settings(Scene *scene);
+	void deduplicate_nodes();
 };
 
 CCL_NAMESPACE_END
diff --git a/intern/cycles/render/nodes.h b/intern/cycles/render/nodes.h
index b88227a8dfd..4eddc90be3f 100644
--- a/intern/cycles/render/nodes.h
+++ b/intern/cycles/render/nodes.h
@@ -52,6 +52,20 @@ public:
 
 	enum Projection { FLAT, CUBE, TUBE, SPHERE };
 	Projection projection;
+
+	bool equals(const TextureMapping& other) {
+		return translation == other.translation &&
+		       rotation == other.rotation &&
+		       scale == other.scale &&
+		       use_minmax == other.use_minmax &&
+		       min == other.min &&
+		       max == other.max &&
+		       type == other.type &&
+		       x_mapping == other.x_mapping &&
+		       y_mapping == other.y_mapping &&
+		       z_mapping == other.z_mapping &&
+		       projection == other.projection;
+	}
 };
 
 /* Nodes */
@@ -69,12 +83,22 @@ class TextureNode : public ShaderNode {
 public:
 	TextureNode(const char *name_) : ShaderNode(name_) {}
 	TextureMapping tex_mapping;
+
+	virtual bool equals(const ShaderNode *other) {
+		return ShaderNode::equals(other) &&
+		       tex_mapping.equals(((const TextureNode*)other)->tex_mapping);
+	}
 };
 
 class ImageSlotTextureNode : public ImageSlotNode {
 public:
 	ImageSlotTextureNode(const char *name_) : ImageSlotNode(name_) {}
 	TextureMapping tex_mapping;
+
+	virtual bool equals(const ShaderNode *other) {
+		return ShaderNode::equals(other) &&
+		       tex_mapping.equals(((const ImageSlotTextureNode*)other)->tex_mapping);
+	}
 };
 
 class ImageTextureNode : public ImageSlotTextureNode {
@@ -99,6 +123,20 @@ public:
 
 	static ShaderEnum color_space_enum;
 	static ShaderEnum projection_enum;
+
+	virtual bool equals(const ShaderNode *other) {
+		const ImageTextureNode *image_node = (const ImageTextureNode*)other;
+		return ImageSlotTextureNode::equals(other) &&
+		       use_alpha == image_node->use_alpha &&
+		       filename == image_node->filename &&
+		       builtin_data == image_node->builtin_data &&
+		       color_space == image_node->color_space &&
+		       projection == image_node->projection &&
+		       interpolation == image_node->interpolation &&
+		       extension == image_node->extension &&
+		       projection_blend == image_node->projection_blend &&
+		       animated == image_node->animated;
+	}
 };
 
 class EnvironmentTextureNode : public ImageSlotTextureNode {
@@ -122,6 +160,18 @@ public:
 
 	static ShaderEnum color_space_enum;
 	static ShaderEnum projection_enum;
+
+	virtual bool equals(const ShaderNode *other) {
+		const EnvironmentTextureNode *env_node = (const EnvironmentTextureNode*)other;
+		return ImageSlotTextureNode::equals(other) &&
+		       use_alpha == env_node->use_alpha &&
+		       filename == env_node->filename &&
+		       builtin_data == env_node->builtin_data &&
+		       color_space == env_node->color_space &&
+		       projection == env_node->projection &&
+		       interpolation == env_node->interpolation &&
+		       animated == env_node->animated;
+	}
 };
 
 class SkyTextureNode : public TextureNode {
@@ -133,14 +183,26 @@ public:
 	float3 sun_direction;
 	float turbidity;
 	float ground_albedo;
-	
+
 	ustring type;
 	static ShaderEnum type_enum;
+
+	virtual bool equals(const ShaderNode *other) {
+		const SkyTextureNode *sky_node = (const SkyTextureNode*)other;
+		return TextureNode::equals(other) &&
+		       sun_direction == sky_node->sun_direction &&
+		       turbidity == sky_node->turbidity &&
+		       ground_albedo == sky_node->ground_albedo &&
+		       type == sky_node->type;
+	}
 };
 
 class OutputNode : public ShaderNode {
 public:
 	SHADER_NODE_CLASS(OutputNode)
+
+	/* Don't allow output node de-duplication. */
+	virtual bool equals(const ShaderNode * /*other*/) { return false; }
 };
 
 class GradientTextureNode : public TextureNode {
@@ -151,6 +213,12 @@ public:
 
 	ustring type;
 	static ShaderEnum type_enum;
+
+	virtual bool equals(const ShaderNode *other) {
+		const GradientTextureNode *gradient_node = (const GradientTextureNode*)other;
+		return TextureNode::equals(other) &&
+		       type == gradient_node->type;
+	}
 };
 
 class NoiseTextureNode : public TextureNode {
@@ -167,6 +235,12 @@ public:
 	ustring coloring;
 
 	static ShaderEnum coloring_enum;
+
+	virtual bool equals(const ShaderNode *other) {
+		const VoronoiTextureNode *voronoi_node = (const VoronoiTextureNode*)other;
+		return TextureNode::equals(other) &&
+		       coloring == voronoi_node->coloring;
+	}
 };
 
 class MusgraveTextureNode : public TextureNode {
@@ -178,6 +252,12 @@ public:
 	ustring type;
 
 	static ShaderEnum type_enum;
+
+	virtual bool equals(const ShaderNode *other) {
+		const MusgraveTextureNode *musgrave_node = (const MusgraveTextureNode*)other;
+		return TextureNode::equals(other) &&
+		       type == musgrave_node->type;
+	}
 };
 
 class WaveTextureNode : public TextureNode {
@@ -188,6 +268,12 @@ public:
 
 	ustring type;
 	static ShaderEnum type_enum;
+
+	virtual bool equals(const ShaderNode *other) {
+		const WaveTextureNode *wave_node = (const WaveTextureNode*)other;
+		return TextureNode::equals(other) &&
+		       type == wave_node->type;
+	}
 };
 
 class MagicTextureNode : public TextureNode {
@@ -197,6 +283,12 @@ public:
 	virtual int get_group() { return NODE_GROUP_LEVEL_2; }
 
 	int depth;
+
+	virtual bool equals(const ShaderNode *other) {
+		const MagicTextureNode *magic_node = (const MagicTextureNode*)other;
+		return TextureNode::equals(other) &&
+		       depth == magic_node->depth;
+	}
 };
 
 class CheckerTextureNode : public TextureNode {
@@ -209,11 +301,20 @@ public:
 class BrickTextureNode : public TextureNode {
 public:
 	SHADER_NODE_CLASS(BrickTextureNode)
-	
+
 	float offset, squash;
 	int offset_frequency, squash_frequency;
 
 	virtual int get_group() { return NODE_GROUP_LEVEL_2; }
+
+	virtual bool equals(const ShaderNode *other) {
+		const BrickTextureNode *brick_node = (const BrickTextureNode*)other;
+		return TextureNode::equals(other) &&
+		       offset == brick_node->offset &&
+		       squash == brick_node->squash &&
+		       offset_frequency == brick_node->offset_frequency &&
+		       squash_frequency == brick_node->squash_frequency;
+	}
 };
 
 class PointDensityTextureNode : public ShaderNode {
@@ -237,6 +338,16 @@ public:
 	Transform tfm;
 
 	static ShaderEnum space_enum;
+
+	virtual bool equals(const ShaderNode *other) {
+		const PointDensityTextureNode *point_dendity_node = (const PointDensityTextureNode*)other;
+		return ShaderNode::equals(other) &&
+		       filename == point_dendity_node->filename &&
+		       space == point_dendity_node->space &&
+		       builtin_data == point_dendity_node->builtin_data &&
+		       interpolation == point_dendity_node->interpolation &&
+		       tfm == point_dendity_node->tfm;
+	}
 };
 
 class MappingNode : public ShaderNode {
@@ -245,6 +356,12 @@ public:
 	virtual int get_group() { return NODE_GROUP_LEVEL_2; }
 
 	TextureMapping tex_mapping;
+
+	virtual bool equals(const ShaderNode *other) {
+		const MappingNode *mapping_node = (const MappingNode*)other;
+		return ShaderNode::equals(other) &&
+		       tex_mapping.equals(mapping_node->tex_mapping);
+	}
 };
 
 class ConvertNode : public ShaderNode {
@@ -255,6 +372,14 @@ public:
 	bool constant_fold(ShaderOutput *socket, float3 *optimized_value);
 
 	ShaderSocketType from, to;
+
+	virtual bool equals(const ShaderNode *other)
+	{
+		const ConvertNode *convert_node = (const ConvertNode*)other;
+		return ShaderNode::equals(other) &&
+		       from == convert_node->from &&
+		       to == convert_node->to;
+	}
 };
 
 class ProxyNode : public ShaderNode {
@@ -263,6 +388,15 @@ public:
 	SHADER_NODE_BASE_CLASS(ProxyNode)
 
 	ShaderSocketType type;
+
+	virtual bool equals(const ShaderNode * /*other*/)
+	{
+		/* Proxy nodes are created for node groups and can't be duplicated
+		 * actually. So in order to make code a bit more robust in obscure cases
+		 * lets explicitly forbid de-duplication of proxy nodes for now.
+		 */
+		return false;
+	}
 };
 
 class BsdfNode : public ShaderNode {
@@ -275,6 +409,12 @@ public:
 
 	ClosureType closure;
 	bool scattering;
+
+	virtual bool equals(const ShaderNode * /*other*/)
+	{
+		/* TODO(sergey): With some care BSDF nodes can be de-duplicated. */
+		return false;
+	}
 };
 
 class AnisotropicBsdfNode : public BsdfNode {
@@ -394,6 +534,12 @@ public:
 	virtual int get_group() { return NODE_GROUP_LEVEL_1; }
 
 	ClosureType closure;
+
+	virtual bool equals(const ShaderNode * /*other*/)
+	{
+		/* TODO(sergey): With some care Volume nodes can be de-duplicated. */
+		return false;
+	}
 };
 
 class AbsorptionVolumeNode : public VolumeNode {
@@ -432,6 +578,14 @@ public:
 	bool from_dupli;
 	bool use_transform;
 	Transform ob_tfm;
+
+	virtual bool equals(const ShaderNode *other) {
+		const TextureCoordinateNode *texco_node = (const TextureCoordinateNode*)other;
+		return ShaderNode::equals(other) &&
+		       from_dupli == texco_node->from_dupli &&
+		       use_transform == texco_node->use_transform &&
+		       ob_tfm == texco_node->ob_tfm;
+	}
 };
 
 class UVMapNode : public ShaderNode {
@@ -443,6 +597,13 @@ public:
 
 	ustring attribute;
 	bool from_dupli;
+
+	virtual bool equals(const ShaderNode *other) {
+		const UVMapNode *uv_map_node = (const UVMapNode*)other;
+		return ShaderNode::equals(other) &&
+		       attribute == uv_map_node->attribute &&
+		       from_dupli == uv_map_node->from_dupli;
+	}
 };
 
 class LightPathNode : public ShaderNode {
@@ -489,6 +650,12 @@ public:
 	bool constant_fold(ShaderOutput *socket, float3 *optimized_value);
 
 	float value;
+
+	virtual bool equals(const ShaderNode *other) {
+		const ValueNode *value_node = (const ValueNode*)other;
+		return ShaderNode::equals(other) &&
+		       value == value_node->value;
+	}
 };
 
 class ColorNode : public ShaderNode {
@@ -498,6 +665,12 @@ public:
 	bool constant_fold(ShaderOutput *socket, float3 *optimized_value);
 
 	float3 value;
+
+	virtual bool equals(const ShaderNode *other) {
+		const ColorNode *color_node = (const ColorNode*)other;
+		return ShaderNode::equals(other) &&
+		       value == color_node->value;
+	}
 };
 
 class AddClosureNode : public ShaderNode {
@@ -532,6 +705,14 @@ public:
 
 	ustring type;
 	static ShaderEnum type_enum;
+
+	virtual bool equals(const ShaderNode *other)
+	{
+		const MixNode *mix_node = (const MixNode*)other;
+		return ShaderNode::equals(other) &&
+		       use_clamp == mix_node->use_clamp &&
+		       type == mix_node->type;
+	}
 };
 
 class CombineRGBNode : public ShaderNode {
@@ -603,6 +784,12 @@ public:
 	bool has_spatial_varying() { return true; }
 
 	ustring attribute;
+
+	virtual bool equals(const ShaderNode *other) {
+		const AttributeNode *color_node = (const AttributeNode*)other;
+		return ShaderNode::equals(other) &&
+		       attribute == color_node->attribute;
+	}
 };
 
 class CameraNode : public ShaderNode {
@@ -630,7 +817,7 @@ public:
 	SHADER_NODE_CLASS(WireframeNode)
 	bool has_spatial_varying() { return true; }
 	virtual int get_group() { return NODE_GROUP_LEVEL_3; }
-	
+
 	bool use_pixel_size;
 };
 
@@ -659,6 +846,14 @@ public:
 
 	ustring type;
 	static ShaderEnum type_enum;
+
+	virtual bool equals(const ShaderNode *other)
+	{
+		const MathNode *math_node = (const MathNode*)other;
+		return ShaderNode::equals(other) &&
+		       use_clamp == math_node->use_clamp &&
+		       type == math_node->type;
+	}
 };
 
 class NormalNode : public ShaderNode {
@@ -667,6 +862,13 @@ public:
 	virtual int get_group() { return NODE_GROUP_LEVEL_2; }
 
 	float3 direction;
+
+	virtual bool equals(const ShaderNode *other)
+	{
+		const NormalNode *normal_node = (const NormalNode*)other;
+		return ShaderNode::equals(other) &&
+		       direction == normal_node->direction;
+	}
 };
 
 class VectorMathNode : public ShaderNode {
@@ -677,6 +879,13 @@ public:
 
 	ustring type;
 	static ShaderEnum type_enum;
+
+	virtual bool equals(const ShaderNode *other)
+	{
+		const MathNode *math_node = (const MathNode*)other;
+		return ShaderNode::equals(other) &&
+		       type == math_node->type;
+	}
 };
 
 class VectorTransformNode : public ShaderNode {
@@ -688,9 +897,17 @@ public:
 	ustring type;
 	ustring convert_from;
 	ustring convert_to;
-	
+
 	static ShaderEnum type_enum;
 	static ShaderEnum convert_space_enum;
+
+	virtual bool equals(const ShaderNode *other) {
+		const VectorTransformNode *vector_transform_node = (const VectorTransformNode*)other;
+		return ShaderNode::equals(other) &&
+		       type == vector_transform_node->type &&
+		       convert_from == vector_transform_node->convert_from &&
+		       convert_to == vector_transform_node->convert_to;
+	}
 };
 
 class BumpNode : public ShaderNode {
@@ -702,6 +919,12 @@ public:
 	}
 
 	bool invert;
+
+	virtual bool equals(const ShaderNode *other) {
+		const BumpNode *bump_node = (const BumpNode*)other;
+		return ShaderNode::equals(other) &&
+		       invert == bump_node->invert;
+	}
 };
 
 class RGBCurvesNode : public ShaderNode {
@@ -709,6 +932,7 @@ public:
 	SHADER_NODE_CLASS(RGBCurvesNode)
 
 	virtual int get_group() { return NODE_GROUP_LEVEL_3; }
+	virtual bool equals(const ShaderNode * /*other*/) { return false; }
 
 	float4 curves[RAMP_TABLE_SIZE];
 	float min_x, max_x;
@@ -719,6 +943,7 @@ public:
 	SHADER_NODE_CLASS(VectorCurvesNode)
 
 	virtual int get_group() { return NODE_GROUP_LEVEL_3; }
+	virtual bool equals(const ShaderNode * /*other*/) { return false; }
 
 	float4 curves[RAMP_TABLE_SIZE];
 };
@@ -729,6 +954,7 @@ public:
 	float4 ramp[RAMP_TABLE_SIZE];
 	bool interpolate;
 	virtual int get_group() { return NODE_GROUP_LEVEL_1; }
+	virtual bool equals(const ShaderNode * /*other*/) { return false; }
 };
 
 class SetNormalNode : public ShaderNode {
@@ -745,11 +971,13 @@ public:
 
 	string filepath;
 	string bytecode_hash;
-	
+
 	/* ShaderInput/ShaderOutput only stores a shallow string copy (const char *)!
 	 * The actual socket names have to be stored externally to avoid memory errors. */
 	vector<ustring> input_names;
 	vector<ustring> output_names;
+
+	virtual bool equals(const ShaderNode * /*other*/) { return false; }
 };
 
 class NormalMapNode : public ShaderNode {
@@ -763,6 +991,14 @@ public:
 	static ShaderEnum space_enum;
 
 	ustring attribute;
+
+	virtual bool equals(const ShaderNode *other)
+	{
+		const NormalMapNode *normal_map_node = (const NormalMapNode*)other;
+		return ShaderNode::equals(other) &&
+		       space == normal_map_node->space &&
+		       attribute == normal_map_node->attribute;
+	}
 };
 
 class TangentNode : public ShaderNode {
@@ -779,6 +1015,15 @@ public:
 	static ShaderEnum axis_enum;
 
 	ustring attribute;
+
+	virtual bool equals(const ShaderNode *other)
+	{
+		const TangentNode *tangent_node = (const TangentNode*)other;
+		return ShaderNode::equals(other) &&
+		       direction_type == tangent_node->direction_type &&
+		       axis == tangent_node->axis &&
+		       attribute == tangent_node->attribute;
+	}
 };
 
 CCL_NAMESPACE_END