Cycles: Add Random Per Island attribute.

The Random Per Island attribute is a random float associated with each
connected component (island) of the mesh. It is particularly useful
when artists want to add variations to meshes composed of separate
units. Like tree leaves created using particle systems, wood planks
created using array modifiers, or abstract splines created using AN.

Reviewed By: Sergey Sharybin, Jacques Lucke

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

intern/cycles/blender/blender_mesh.cpp

@@ -29,8 +29,10 @@
 
 #include "util/util_algorithm.h"
 #include "util/util_foreach.h"
+#include "util/util_hash.h"
 #include "util/util_logging.h"
 #include "util/util_math.h"
+#include "util/util_disjoint_set.h"
 
 #include "mikktspace.h"
 
@@ -679,6 +681,55 @@ static void attr_create_pointiness(Scene *scene, Mesh *mesh, BL::Mesh &b_mesh, b
   }
 }
 
+/* The Random Per Island attribute is a random float associated with each
+ * connected component (island) of the mesh. The attribute is computed by
+ * first classifying the vertices into different sets using a Disjoint Set
+ * data structure. Then the index of the root of each vertex (Which is the
+ * representative of the set the vertex belongs to) is hashed and stored.
+ *
+ * We are using a face attribute to avoid interpolation during rendering,
+ * allowing the user to safely hash the output further. Had we used vertex
+ * attribute, the interpolation will introduce very slight variations,
+ * making the output unsafe to hash. */
+static void attr_create_random_per_island(Scene *scene,
+                                          Mesh *mesh,
+                                          BL::Mesh &b_mesh,
+                                          bool subdivision)
+{
+  if (!mesh->need_attribute(scene, ATTR_STD_RANDOM_PER_ISLAND)) {
+    return;
+  }
+
+  int number_of_vertices = b_mesh.vertices.length();
+  if (number_of_vertices == 0) {
+    return;
+  }
+
+  DisjointSet vertices_sets(number_of_vertices);
+
+  BL::Mesh::edges_iterator e;
+  for (b_mesh.edges.begin(e); e != b_mesh.edges.end(); ++e) {
+    vertices_sets.join(e->vertices()[0], e->vertices()[1]);
+  }
+
+  AttributeSet &attributes = (subdivision) ? mesh->subd_attributes : mesh->attributes;
+  Attribute *attribute = attributes.add(ATTR_STD_RANDOM_PER_ISLAND);
+  float *data = attribute->data_float();
+
+  if (!subdivision) {
+    BL::Mesh::loop_triangles_iterator t;
+    for (b_mesh.loop_triangles.begin(t); t != b_mesh.loop_triangles.end(); ++t) {
+      data[t->index()] = hash_uint_to_float(vertices_sets.find(t->vertices()[0]));
+    }
+  }
+  else {
+    BL::Mesh::polygons_iterator p;
+    for (b_mesh.polygons.begin(p); p != b_mesh.polygons.end(); ++p) {
+      data[p->index()] = hash_uint_to_float(vertices_sets.find(p->vertices()[0]));
+    }
+  }
+}
+
 /* Create Mesh */
 
 static void create_mesh(Scene *scene,
@@ -799,6 +850,7 @@ static void create_mesh(Scene *scene,
    */
   attr_create_pointiness(scene, mesh, b_mesh, subdivision);
   attr_create_vertex_color(scene, mesh, b_mesh, subdivision);
+  attr_create_random_per_island(scene, mesh, b_mesh, subdivision);
 
   if (subdivision) {
     attr_create_subd_uv_map(scene, mesh, b_mesh, subdivide_uvs);

intern/cycles/kernel/kernel_types.h

@@ -768,6 +768,7 @@ typedef enum AttributeStandard {
   ATTR_STD_VOLUME_TEMPERATURE,
   ATTR_STD_VOLUME_VELOCITY,
   ATTR_STD_POINTINESS,
+  ATTR_STD_RANDOM_PER_ISLAND,
   ATTR_STD_NUM,
 
   ATTR_STD_NOT_FOUND = ~0

intern/cycles/kernel/shaders/node_geometry.osl

@@ -26,7 +26,8 @@ shader node_geometry(normal NormalIn = N,
                      output vector Incoming = vector(0.0, 0.0, 0.0),
                      output point Parametric = point(0.0, 0.0, 0.0),
                      output float Backfacing = 0.0,
-                     output float Pointiness = 0.0)
+                     output float Pointiness = 0.0,
+                     output float RandomPerIsland = 0.0)
 {
   Position = P;
   Normal = NormalIn;
@@ -65,4 +66,6 @@ shader node_geometry(normal NormalIn = N,
   else if (bump_offset == "dy") {
     Pointiness += Dy(Pointiness);
   }
+
+  getattribute("geom:random_per_island", RandomPerIsland);
 }

intern/cycles/render/attribute.cpp

@@ -312,6 +312,8 @@ const char *Attribute::standard_name(AttributeStandard std)
       return "velocity";
     case ATTR_STD_POINTINESS:
       return "pointiness";
+    case ATTR_STD_RANDOM_PER_ISLAND:
+      return "random_per_island";
     case ATTR_STD_NOT_FOUND:
     case ATTR_STD_NONE:
     case ATTR_STD_NUM:
@@ -468,6 +470,9 @@ Attribute *AttributeSet::add(AttributeStandard std, ustring name)
       case ATTR_STD_POINTINESS:
         attr = add(name, TypeDesc::TypeFloat, ATTR_ELEMENT_VERTEX);
         break;
+      case ATTR_STD_RANDOM_PER_ISLAND:
+        attr = add(name, TypeDesc::TypeFloat, ATTR_ELEMENT_FACE);
+        break;
       default:
         assert(0);
         break;
@@ -496,6 +501,9 @@ Attribute *AttributeSet::add(AttributeStandard std, ustring name)
       case ATTR_STD_POINTINESS:
         attr = add(name, TypeDesc::TypeFloat, ATTR_ELEMENT_VERTEX);
         break;
+      case ATTR_STD_RANDOM_PER_ISLAND:
+        attr = add(name, TypeDesc::TypeFloat, ATTR_ELEMENT_FACE);
+        break;
       default:
         assert(0);
         break;

intern/cycles/render/nodes.cpp

@@ -3502,6 +3502,7 @@ NODE_DEFINE(GeometryNode)
   SOCKET_OUT_POINT(parametric, "Parametric");
   SOCKET_OUT_FLOAT(backfacing, "Backfacing");
   SOCKET_OUT_FLOAT(pointiness, "Pointiness");
+  SOCKET_OUT_FLOAT(random_per_island, "Random Per Island");
 
   return type;
 }
@@ -3520,6 +3521,9 @@ void GeometryNode::attributes(Shader *shader, AttributeRequestSet *attributes)
     if (!output("Pointiness")->links.empty()) {
       attributes->add(ATTR_STD_POINTINESS);
     }
+    if (!output("Random Per Island")->links.empty()) {
+      attributes->add(ATTR_STD_RANDOM_PER_ISLAND);
+    }
   }
 
   ShaderNode::attributes(shader, attributes);
@@ -3585,6 +3589,17 @@ void GeometryNode::compile(SVMCompiler &compiler)
       compiler.add_node(NODE_VALUE_F, __float_as_int(0.0f), compiler.stack_assign(out));
     }
   }
+
+  out = output("Random Per Island");
+  if (!out->links.empty()) {
+    if (compiler.output_type() != SHADER_TYPE_VOLUME) {
+      compiler.add_node(
+          attr_node, ATTR_STD_RANDOM_PER_ISLAND, compiler.stack_assign(out), NODE_ATTR_FLOAT);
+    }
+    else {
+      compiler.add_node(NODE_VALUE_F, __float_as_int(0.0f), compiler.stack_assign(out));
+    }
+  }
 }
 
 void GeometryNode::compile(OSLCompiler &compiler)

intern/cycles/util/CMakeLists.txt

@@ -60,6 +60,7 @@ set(SRC_HEADERS
   util_debug.h
   util_defines.h
   util_deque.h
+  util_disjoint_set.h
   util_guarded_allocator.cpp
   util_foreach.h
   util_function.h

intern/cycles/util/util_disjoint_set.h

@@ -0,0 +1,75 @@
+/*
+ * Copyright 2011-2013 Blender Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __UTIL_DISJOINT_SET_H__
+#define __UTIL_DISJOINT_SET_H__
+
+#include <utility>
+#include "util_array.h"
+
+CCL_NAMESPACE_BEGIN
+
+class DisjointSet {
+ private:
+  array<size_t> parents;
+  array<size_t> ranks;
+
+ public:
+  DisjointSet(size_t size) : parents(size), ranks(size)
+  {
+    for (size_t i = 0; i < size; i++) {
+      parents[i] = i;
+      ranks[i] = 0;
+    }
+  }
+
+  size_t find(size_t x)
+  {
+    size_t root = x;
+    while (parents[root] != root) {
+      root = parents[root];
+    }
+    while (parents[x] != root) {
+      size_t parent = parents[x];
+      parents[x] = root;
+      x = parent;
+    }
+    return root;
+  }
+
+  void join(size_t x, size_t y)
+  {
+    size_t x_root = find(x);
+    size_t y_root = find(y);
+
+    if (x_root == y_root) {
+      return;
+    }
+
+    if (ranks[x_root] < ranks[y_root]) {
+      std::swap(x_root, y_root);
+    }
+    parents[y_root] = x_root;
+
+    if (ranks[x_root] == ranks[y_root]) {
+      ranks[x_root]++;
+    }
+  }
+};
+
+CCL_NAMESPACE_END
+
+#endif /* __UTIL_DISJOINT_SET_H__ */

source/blender/gpu/shaders/material/gpu_shader_material_geometry.glsl

@@ -11,7 +11,8 @@ void node_geometry(vec3 I,
                    out vec3 incoming,
                    out vec3 parametric,
                    out float backfacing,
-                   out float pointiness)
+                   out float pointiness,
+                   out float random_per_island)
 {
   /* handle perspective/orthographic */
   vec3 I_view = (ProjectionMatrix[3][3] == 0.0) ? normalize(I) : vec3(0.0, 0.0, -1.0);
@@ -42,5 +43,6 @@ void node_geometry(vec3 I,
   parametric = vec3(barycentric, 0.0);
   backfacing = (gl_FrontFacing) ? 0.0 : 1.0;
   pointiness = 0.5;
+  random_per_island = 0.0;
 #endif
 }

source/blender/nodes/shader/nodes/node_shader_geometry.c

@@ -30,6 +30,7 @@ static bNodeSocketTemplate sh_node_geometry_out[] = {
     {SOCK_VECTOR, 0, N_("Parametric"), 0.0f, 0.0f, 0.0f, 0.0f, 0.0f, 1.0f},
     {SOCK_FLOAT, 0, N_("Backfacing"), 0.0f, 0.0f, 0.0f, 0.0f, 0.0f, 1.0f},
     {SOCK_FLOAT, 0, N_("Pointiness"), 0.0f, 0.0f, 0.0f, 0.0f, 0.0f, 1.0f},
+    {SOCK_FLOAT, 0, N_("Random Per Island"), 0.0f, 0.0f, 0.0f, 0.0f, 0.0f, 1.0f},
     {-1, 0, ""},
 };