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

2 files changed, 76 insertions, 0 deletions

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__ */