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

3 files changed, 236 insertions, 57 deletions

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);
 }