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

7 files changed, 156 insertions, 1 deletions

diff --git a/intern/cycles/blender/blender_mesh.cpp b/intern/cycles/blender/blender_mesh.cpp
index 30417e85441..5c28404e745 100644
--- a/intern/cycles/blender/blender_mesh.cpp
+++ b/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);
diff --git a/intern/cycles/kernel/kernel_types.h b/intern/cycles/kernel/kernel_types.h
index 1e5534b0c17..7306c32d7c8 100644
--- a/intern/cycles/kernel/kernel_types.h
+++ b/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
diff --git a/intern/cycles/kernel/shaders/node_geometry.osl b/intern/cycles/kernel/shaders/node_geometry.osl
index b5c1c6611c1..3cf2e974022 100644
--- a/intern/cycles/kernel/shaders/node_geometry.osl
+++ b/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);
 }
diff --git a/intern/cycles/render/attribute.cpp b/intern/cycles/render/attribute.cpp
index 0fa1142f354..b65c2faa788 100644
--- a/intern/cycles/render/attribute.cpp
+++ b/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;
diff --git a/intern/cycles/render/nodes.cpp b/intern/cycles/render/nodes.cpp
index b58e10a7b52..f637fbf3b37 100644
--- a/intern/cycles/render/nodes.cpp
+++ b/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)
diff --git a/intern/cycles/util/CMakeLists.txt b/intern/cycles/util/CMakeLists.txt
index 0063422aaef..ef100c12453 100644
--- a/intern/cycles/util/CMakeLists.txt
+++ b/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
diff --git a/intern/cycles/util/util_disjoint_set.h b/intern/cycles/util/util_disjoint_set.h
new file mode 100644
index 00000000000..80f3c714a29
--- /dev/null
+++ b/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__ */