Cycles: add voronoi features and distance settings from Blender.

Features to get the 2nd, 3rd, 4th closest point instead of the closest, and
various distance metrics. No viewport/Eevee support yet.

Patch by Michel Anders, Charlie Jolly and Brecht Van Lommel.

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

7 files changed, 281 insertions, 62 deletions

diff --git a/intern/cycles/blender/blender_shader.cpp b/intern/cycles/blender/blender_shader.cpp
index 8afcb0ce885..956f8f767a6 100644
--- a/intern/cycles/blender/blender_shader.cpp
+++ b/intern/cycles/blender/blender_shader.cpp
@@ -748,6 +748,8 @@ static ShaderNode *add_node(Scene *scene,
 		BL::ShaderNodeTexVoronoi b_voronoi_node(b_node);
 		VoronoiTextureNode *voronoi = new VoronoiTextureNode();
 		voronoi->coloring = (NodeVoronoiColoring)b_voronoi_node.coloring();
+		voronoi->metric = (NodeVoronoiDistanceMetric)b_voronoi_node.distance();
+		voronoi->feature = (NodeVoronoiFeature)b_voronoi_node.feature();
 		BL::TexMapping b_texture_mapping(b_voronoi_node.texture_mapping());
 		get_tex_mapping(&voronoi->tex_mapping, b_texture_mapping);
 		node = voronoi;
diff --git a/intern/cycles/kernel/shaders/node_voronoi_texture.osl b/intern/cycles/kernel/shaders/node_voronoi_texture.osl
index 0c3b95ae4d0..2e47d74a414 100644
--- a/intern/cycles/kernel/shaders/node_voronoi_texture.osl
+++ b/intern/cycles/kernel/shaders/node_voronoi_texture.osl
@@ -17,12 +17,93 @@
 #include "stdosl.h"
 #include "node_texture.h"
 
+void voronoi_m(point p, string metric, float e, float da[4], point pa[4])
+{
+	/* Compute the distance to and the position of the four closest neighbors to p.
+	 *
+	 * The neighbors are randomly placed, 1 each in a 3x3x3 grid (Worley pattern).
+	 * The distances and points are returned in ascending order, i.e. da[0] and pa[0] will
+	 * contain the distance to the closest point and its coordinates respectively.
+	 */
+	int xx, yy, zz, xi, yi, zi;
+
+	xi = (int)floor(p[0]);
+	yi = (int)floor(p[1]);
+	zi = (int)floor(p[2]);
+
+	da[0] = 1e10;
+	da[1] = 1e10;
+	da[2] = 1e10;
+	da[3] = 1e10;
+
+	for (xx = xi - 1; xx <= xi + 1; xx++) {
+		for (yy = yi - 1; yy <= yi + 1; yy++) {
+			for (zz = zi - 1; zz <= zi + 1; zz++) {
+				point ip = point(xx, yy, zz);
+				point vp = (point)cellnoise_color(ip);
+				point pd = p - (vp + ip);
+
+				float d = 0.0;
+				if (metric == "distance") {
+					d = dot(pd, pd);
+				}
+				else if (metric == "manhattan") {
+					d = fabs(pd[0]) + fabs(pd[1]) + fabs(pd[2]);
+				}
+				else if (metric == "chebychev") {
+					d = max(fabs(pd[0]), max(fabs(pd[1]), fabs(pd[2])));
+				}
+				else if (metric == "minkowski") {
+					d = pow(pow(fabs(pd[0]), e) + pow(fabs(pd[1]), e) + pow(fabs(pd[2]), e), 1.0/e);
+				}
+
+				vp += point(xx, yy, zz);
+
+				if (d < da[0]) {
+					da[3] = da[2];
+					da[2] = da[1];
+					da[1] = da[0];
+					da[0] = d;
+
+					pa[3] = pa[2];
+					pa[2] = pa[1];
+					pa[1] = pa[0];
+					pa[0] = vp;
+				}
+				else if (d < da[1]) {
+					da[3] = da[2];
+					da[2] = da[1];
+					da[1] = d;
+
+					pa[3] = pa[2];
+					pa[2] = pa[1];
+					pa[1] = vp;
+				}
+				else if (d < da[2]) {
+					da[3] = da[2];
+					da[2] = d;
+
+					pa[3] = pa[2];
+					pa[2] = vp;
+				}
+				else if (d < da[3]) {
+					da[3] = d;
+					pa[3] = vp;
+				}
+			}
+		}
+	}
+}
+
 /* Voronoi */
 
 shader node_voronoi_texture(
 	int use_mapping = 0,
 	matrix mapping = matrix(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 	string coloring = "intensity",
+	string metric = "distance",
+	string feature = "F1",
+	float Exponent = 1.0,
 	float Scale = 5.0,
 	point Vector = P,
 	output float Fac = 0.0,
@@ -37,17 +118,48 @@ shader node_voronoi_texture(
 	float da[4];
 	point pa[4];
 
-	voronoi(p * Scale, 1.0, da, pa);
+	/* compute distance and point coordinate of 4 nearest neighbours */
+	voronoi_m(p * Scale, metric, Exponent, da, pa);
 
-	/* Colored output */
 	if (coloring == "intensity") {
-		Fac = fabs(da[0]);
+		/* Intensity output */
+		if (feature == "F1") {
+			Fac = fabs(da[0]);
+		}
+		else if (feature == "F2") {
+			Fac = fabs(da[1]);
+		}
+		else if (feature == "F3") {
+			Fac = fabs(da[2]);
+		}
+		else if (feature == "F4") {
+			Fac = fabs(da[3]);
+		}
+		else if (feature == "F2F1") {
+			Fac = fabs(da[1] - da[0]);
+		}
 		Color = color(Fac);
 	}
 	else {
-		Color = cellnoise_color(pa[0]);
-		Fac = (Color[0] + Color[1] + Color[2]) * (1.0 / 3.0);
+		/* Color output */
+		if (feature == "F1") {
+			Color = pa[0];
+		}
+		else if (feature == "F2") {
+			Color = pa[1];
+		}
+		else if (feature == "F3") {
+			Color = pa[2];
+		}
+		else if (feature == "F4") {
+			Color = pa[3];
+		}
+		else if (feature == "F2F1") {
+			Color = fabs(pa[1] - pa[0]);
+		}
 
+		Color = cellnoise_color(Color);
+		Fac = (Color[0] + Color[1] + Color[2]) * (1.0 / 3.0);
 	}
 }
 
diff --git a/intern/cycles/kernel/svm/svm_types.h b/intern/cycles/kernel/svm/svm_types.h
index 0fde5126434..e03ad3a0cfe 100644
--- a/intern/cycles/kernel/svm/svm_types.h
+++ b/intern/cycles/kernel/svm/svm_types.h
@@ -338,6 +338,21 @@ typedef enum NodeVoronoiColoring {
 	NODE_VORONOI_CELLS
 } NodeVoronoiColoring;
 
+typedef enum NodeVoronoiDistanceMetric {
+	NODE_VORONOI_DISTANCE,
+	NODE_VORONOI_MANHATTAN,
+	NODE_VORONOI_CHEBYCHEV,
+	NODE_VORONOI_MINKOWSKI
+} NodeVoronoiDistanceMetric;
+
+typedef enum NodeVoronoiFeature {
+	NODE_VORONOI_F1,
+	NODE_VORONOI_F2,
+	NODE_VORONOI_F3,
+	NODE_VORONOI_F4,
+	NODE_VORONOI_F2F1
+} NodeVoronoiFeature;
+
 typedef enum NodeBlendWeightType {
 	NODE_LAYER_WEIGHT_FRESNEL,
 	NODE_LAYER_WEIGHT_FACING
diff --git a/intern/cycles/kernel/svm/svm_voronoi.h b/intern/cycles/kernel/svm/svm_voronoi.h
index 5d0b8a2a406..e5e350bf76a 100644
--- a/intern/cycles/kernel/svm/svm_voronoi.h
+++ b/intern/cycles/kernel/svm/svm_voronoi.h
@@ -18,10 +18,19 @@ CCL_NAMESPACE_BEGIN
 
 /* Voronoi */
 
-ccl_device float voronoi_F1_distance(float3 p)
+ccl_device void voronoi_neighbors(float3 p, NodeVoronoiDistanceMetric distance, float e, float da[4], float3 pa[4])
 {
-	/* returns squared distance in da */
-	float da = 1e10f;
+	/* Compute the distance to and the position of the closest neighbors to p.
+	 *
+	 * The neighbors are randomly placed, 1 each in a 3x3x3 grid (Worley pattern).
+	 * The distances and points are returned in ascending order, i.e. da[0] and pa[0] will
+	 * contain the distance to the closest point and its coordinates respectively.
+	 */
+
+	da[0] = 1e10f;
+	da[1] = 1e10f;
+	da[2] = 1e10f;
+	da[3] = 1e10f;
 
 	int3 xyzi = quick_floor_to_int3(p);
 
@@ -31,71 +40,114 @@ ccl_device float voronoi_F1_distance(float3 p)
 				int3 ip = xyzi + make_int3(xx, yy, zz);
 				float3 fp = make_float3(ip.x, ip.y, ip.z);
 				float3 vp = fp + cellnoise3(fp);
-				float d = len_squared(p - vp);
-				da = min(d, da);
-			}
-		}
-	}
-
-	return da;
-}
 
-ccl_device float3 voronoi_F1_color(float3 p)
-{
-	/* returns color of the nearest point */
-	float da = 1e10f;
-	float3 pa;
-
-	int3 xyzi = quick_floor_to_int3(p);
+				float d;
+				switch(distance) {
+					case NODE_VORONOI_DISTANCE:
+						d = len_squared(p - vp);
+						break;
+					case NODE_VORONOI_MANHATTAN:
+						d = reduce_add(fabs(vp - p));
+						break;
+					case NODE_VORONOI_CHEBYCHEV:
+						d = max3(fabs(vp - p));
+						break;
+					case NODE_VORONOI_MINKOWSKI:
+						float3 n = fabs(vp - p);
+						if(e == 0.5f) {
+							d = sqr(reduce_add(sqrt(n)));
+						}
+						else {
+							d = powf(reduce_add(pow3(n, e)), 1.0f/e);
+						}
+						break;
+				}
 
-	for(int xx = -1; xx <= 1; xx++) {
-		for(int yy = -1; yy <= 1; yy++) {
-			for(int zz = -1; zz <= 1; zz++) {
-				int3 ip = xyzi + make_int3(xx, yy, zz);
-				float3 fp = make_float3(ip.x, ip.y, ip.z);
-				float3 vp = fp + cellnoise3(fp);
-				float d = len_squared(p - vp);
+				/* To keep the shortest four distances and associated points we have to keep them in sorted order. */
+				if (d < da[0]) {
+					da[3] = da[2];
+					da[2] = da[1];
+					da[1] = da[0];
+					da[0] = d;
+
+					pa[3] = pa[2];
+					pa[2] = pa[1];
+					pa[1] = pa[0];
+					pa[0] = vp;
+				}
+				else if (d < da[1]) {
+					da[3] = da[2];
+					da[2] = da[1];
+					da[1] = d;
+
+					pa[3] = pa[2];
+					pa[2] = pa[1];
+					pa[1] = vp;
+				}
+				else if (d < da[2]) {
+					da[3] = da[2];
+					da[2] = d;
 
-				if(d < da) {
-					da = d;
-					pa = vp;
+					pa[3] = pa[2];
+					pa[2] = vp;
+				}
+				else if (d < da[3]) {
+					da[3] = d;
+					pa[3] = vp;
 				}
 			}
 		}
 	}
-
-	return cellnoise3(pa);
-}
-
-ccl_device_noinline float4 svm_voronoi(NodeVoronoiColoring coloring, float3 p)
-{
-	if(coloring == NODE_VORONOI_INTENSITY) {
-		/* compute squared distance to the nearest neighbour */
-		float fac = voronoi_F1_distance(p);
-		return make_float4(fac, fac, fac, fac);
-	}
-	else {
-		/* compute color of the nearest neighbour */
-		float3 color = voronoi_F1_color(p);
-		return make_float4(color.x, color.y, color.z, average(color));
-	}
 }
 
 ccl_device void svm_node_tex_voronoi(KernelGlobals *kg, ShaderData *sd, float *stack, uint4 node, int *offset)
 {
-	uint coloring = node.y;
-	uint scale_offset, co_offset, fac_offset, color_offset;
+	uint4 node2 = read_node(kg, offset);
+
+	uint co_offset, coloring, distance, feature;
+	uint scale_offset, e_offset, fac_offset, color_offset;
 
-	decode_node_uchar4(node.z, &scale_offset, &co_offset, &fac_offset, &color_offset);
+	decode_node_uchar4(node.y, &co_offset, &coloring, &distance, &feature);
+	decode_node_uchar4(node.z, &scale_offset, &e_offset, &fac_offset, &color_offset);
 
 	float3 co = stack_load_float3(stack, co_offset);
-	float scale = stack_load_float_default(stack, scale_offset, node.w);
+	float scale = stack_load_float_default(stack, scale_offset, node2.x);
+	float exponent = stack_load_float_default(stack, e_offset, node2.y);
 
-	float4 result = svm_voronoi((NodeVoronoiColoring)coloring, co*scale);
-	float3 color = make_float3(result.x, result.y, result.z);
-	float f = result.w;
+	float dist[4];
+	float3 neighbor[4];
+	voronoi_neighbors(co*scale, (NodeVoronoiDistanceMetric)distance, exponent, dist, neighbor);
+
+	float3 color;
+	float fac;
+	if(coloring == NODE_VORONOI_INTENSITY) {
+		switch(feature) {
+			case NODE_VORONOI_F1: fac = dist[0]; break;
+			case NODE_VORONOI_F2: fac = dist[1]; break;
+			case NODE_VORONOI_F3: fac = dist[2]; break;
+			case NODE_VORONOI_F4: fac = dist[3]; break;
+			case NODE_VORONOI_F2F1: fac = dist[1] - dist[0]; break;
+		}
+
+		color = make_float3(fac, fac, fac);
+	}
+	else {
+		 /* NODE_VORONOI_CELLS */
+		switch(feature) {
+			case NODE_VORONOI_F1: color = neighbor[0]; break;
+			case NODE_VORONOI_F2: color = neighbor[1]; break;
+			case NODE_VORONOI_F3: color = neighbor[2]; break;
+			case NODE_VORONOI_F4: color = neighbor[3]; break;
+			/* Usefulness of this vector is questionable. Note F2 >= F1 but the
+			 * individual vector components might not be. */
+			case NODE_VORONOI_F2F1: color = fabs(neighbor[1] - neighbor[0]); break;
+		}
+
+		color = cellnoise3(color);
+		fac = average(color);
+	}
 
-	if(stack_valid(fac_offset)) stack_store_float(stack, fac_offset, f);
+	if(stack_valid(fac_offset)) stack_store_float(stack, fac_offset, fac);
 	if(stack_valid(color_offset)) stack_store_float3(stack, color_offset, color);
 }
 
diff --git a/intern/cycles/render/nodes.cpp b/intern/cycles/render/nodes.cpp
index fe2916d21d4..986004433e4 100644
--- a/intern/cycles/render/nodes.cpp
+++ b/intern/cycles/render/nodes.cpp
@@ -913,7 +913,23 @@ NODE_DEFINE(VoronoiTextureNode)
 	coloring_enum.insert("cells", NODE_VORONOI_CELLS);
 	SOCKET_ENUM(coloring, "Coloring", coloring_enum, NODE_VORONOI_INTENSITY);
 
+	static NodeEnum metric;
+	metric.insert("distance", NODE_VORONOI_DISTANCE);
+	metric.insert("manhattan", NODE_VORONOI_MANHATTAN);
+	metric.insert("chebychev", NODE_VORONOI_CHEBYCHEV);
+	metric.insert("minkowski", NODE_VORONOI_MINKOWSKI);
+	SOCKET_ENUM(metric, "Distance Metric", metric, NODE_VORONOI_INTENSITY);
+
+	static NodeEnum feature_enum;
+	feature_enum.insert("F1", NODE_VORONOI_F1);
+	feature_enum.insert("F2", NODE_VORONOI_F2);
+	feature_enum.insert("F3", NODE_VORONOI_F3);
+	feature_enum.insert("F4", NODE_VORONOI_F4);
+	feature_enum.insert("F2F1", NODE_VORONOI_F2F1);
+	SOCKET_ENUM(feature, "Feature", feature_enum, NODE_VORONOI_INTENSITY);
+
 	SOCKET_IN_FLOAT(scale, "Scale", 1.0f);
+	SOCKET_IN_FLOAT(exponent, "Exponent", 0.5f);
 	SOCKET_IN_POINT(vector, "Vector", make_float3(0.0f, 0.0f, 0.0f), SocketType::LINK_TEXTURE_GENERATED);
 
 	SOCKET_OUT_COLOR(color, "Color");
@@ -931,19 +947,32 @@ void VoronoiTextureNode::compile(SVMCompiler& compiler)
 {
 	ShaderInput *scale_in = input("Scale");
 	ShaderInput *vector_in = input("Vector");
+	ShaderInput *exponent_in = input("Exponent");
 	ShaderOutput *color_out = output("Color");
 	ShaderOutput *fac_out = output("Fac");
 
+	if (vector_in->link) compiler.stack_assign(vector_in);
+	if (scale_in->link) compiler.stack_assign(scale_in);
+	if (exponent_in->link) compiler.stack_assign(exponent_in);
+
 	int vector_offset = tex_mapping.compile_begin(compiler, vector_in);
 
 	compiler.add_node(NODE_TEX_VORONOI,
-		coloring,
 		compiler.encode_uchar4(
-			compiler.stack_assign_if_linked(scale_in),
 			vector_offset,
+			coloring,
+			metric,
+			feature
+		),
+		compiler.encode_uchar4(
+			compiler.stack_assign_if_linked(scale_in),
+			compiler.stack_assign_if_linked(exponent_in),
 			compiler.stack_assign(fac_out),
-			compiler.stack_assign(color_out)),
-		__float_as_int(scale));
+			compiler.stack_assign(color_out)
+		));
+	compiler.add_node(
+		__float_as_int(scale),
+		__float_as_int(exponent));
 
 	tex_mapping.compile_end(compiler, vector_in, vector_offset);
 }
@@ -953,6 +982,8 @@ void VoronoiTextureNode::compile(OSLCompiler& compiler)
 	tex_mapping.compile(compiler);
 
 	compiler.parameter(this, "coloring");
+	compiler.parameter(this, "metric");
+	compiler.parameter(this, "feature");
 	compiler.add(this, "node_voronoi_texture");
 }
 
diff --git a/intern/cycles/render/nodes.h b/intern/cycles/render/nodes.h
index f24445ea2e9..ebe6db6e362 100644
--- a/intern/cycles/render/nodes.h
+++ b/intern/cycles/render/nodes.h
@@ -189,7 +189,9 @@ public:
 	virtual int get_group() { return NODE_GROUP_LEVEL_2; }
 
 	NodeVoronoiColoring coloring;
-	float scale;
+	NodeVoronoiDistanceMetric metric;
+	NodeVoronoiFeature feature;
+	float scale, exponent;
 	float3 vector;
 };
 
diff --git a/intern/cycles/util/util_math_float3.h b/intern/cycles/util/util_math_float3.h
index e42ded76c75..3a5a2ab2244 100644
--- a/intern/cycles/util/util_math_float3.h
+++ b/intern/cycles/util/util_math_float3.h
@@ -280,6 +280,11 @@ ccl_device_inline float3 sqrt(const float3& a)
 #endif
 }
 
+ccl_device_inline float3 pow3(const float3& a, float e)
+{
+	return make_float3(powf(a.x, e), powf(a.y, e), powf(a.z, e));
+}
+
 ccl_device_inline float3 mix(const float3& a, const float3& b, float t)
 {
 	return a + t*(b - a);