Geometry Nodes: Make random attribute node stable

Currently, the random attribute node doesn't work well for most
workflows because for any change in the input data it outputs
completely different results.

This patch adds an implicit seed attribute input to the node, referred
to by "id". The attribute is hashed for each element using the CPPType
system's hash method, meaning the attribute can have any data type.
Supporting any data type is also important so any attribute can be
copied into the "id" attribute and used as a seed.

The "id" attribute is an example of a "reserved name" attribute,
meaning attributes with this name can be used implicitly by nodes like
the random attribute node. Although it makes it a bit more difficult
to dig deeper, using the name implicitly rather than exposing it as an
input should make the system more accessible and predictable.

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

7 files changed, 162 insertions, 45 deletions

diff --git a/source/blender/blenkernel/BKE_attribute_access.hh b/source/blender/blenkernel/BKE_attribute_access.hh
index eafd86d176b..22e14e44bec 100644
--- a/source/blender/blenkernel/BKE_attribute_access.hh
+++ b/source/blender/blenkernel/BKE_attribute_access.hh
@@ -267,10 +267,12 @@ template<typename T> class TypedWriteAttribute {
 using BooleanReadAttribute = TypedReadAttribute<bool>;
 using FloatReadAttribute = TypedReadAttribute<float>;
 using Float3ReadAttribute = TypedReadAttribute<float3>;
+using Int32ReadAttribute = TypedReadAttribute<int>;
 using Color4fReadAttribute = TypedReadAttribute<Color4f>;
 using BooleanWriteAttribute = TypedWriteAttribute<bool>;
 using FloatWriteAttribute = TypedWriteAttribute<float>;
 using Float3WriteAttribute = TypedWriteAttribute<float3>;
+using Int32WriteAttribute = TypedWriteAttribute<int>;
 using Color4fWriteAttribute = TypedWriteAttribute<Color4f>;
 
 }  // namespace blender::bke
diff --git a/source/blender/blenkernel/BKE_geometry_set.hh b/source/blender/blenkernel/BKE_geometry_set.hh
index 90d444aa270..e4232a84a00 100644
--- a/source/blender/blenkernel/BKE_geometry_set.hh
+++ b/source/blender/blenkernel/BKE_geometry_set.hh
@@ -136,6 +136,11 @@ class GeometryComponent {
       const AttributeDomain domain,
       const CustomDataType data_type) const;
 
+  /* Get a read-only attribute interpolated to the input domain, leaving the data type unchanged.
+   * Returns null when the attribute does not exist. */
+  blender::bke::ReadAttributePtr attribute_try_get_for_read(
+      const blender::StringRef attribute_name, const AttributeDomain domain) const;
+
   /* Get a read-only attribute for the given domain and data type.
    * Returns a constant attribute based on the default value if the attribute does not exist.
    * Never returns null. */
diff --git a/source/blender/blenkernel/intern/attribute_access.cc b/source/blender/blenkernel/intern/attribute_access.cc
index 623335f65a1..934beb8a848 100644
--- a/source/blender/blenkernel/intern/attribute_access.cc
+++ b/source/blender/blenkernel/intern/attribute_access.cc
@@ -660,6 +660,28 @@ ReadAttributePtr GeometryComponent::attribute_try_get_for_read(
   return attribute;
 }
 
+ReadAttributePtr GeometryComponent::attribute_try_get_for_read(const StringRef attribute_name,
+                                                               const AttributeDomain domain) const
+{
+  if (!this->attribute_domain_supported(domain)) {
+    return {};
+  }
+
+  ReadAttributePtr attribute = this->attribute_try_get_for_read(attribute_name);
+  if (!attribute) {
+    return {};
+  }
+
+  if (attribute->domain() != domain) {
+    attribute = this->attribute_try_adapt_domain(std::move(attribute), domain);
+    if (!attribute) {
+      return {};
+    }
+  }
+
+  return attribute;
+}
+
 ReadAttributePtr GeometryComponent::attribute_get_for_read(const StringRef attribute_name,
                                                            const AttributeDomain domain,
                                                            const CustomDataType data_type,
diff --git a/source/blender/blenlib/BLI_hash.h b/source/blender/blenlib/BLI_hash.h
index c2be416ef5f..d687e805323 100644
--- a/source/blender/blenlib/BLI_hash.h
+++ b/source/blender/blenlib/BLI_hash.h
@@ -26,35 +26,59 @@
 extern "C" {
 #endif
 
-BLI_INLINE unsigned int BLI_hash_int_2d(unsigned int kx, unsigned int ky)
-{
+/**
+ * Jenkins Lookup3 Hash Functions.
+ * Source: http://burtleburtle.net/bob/c/lookup3.c
+ */
+
 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
+#define final(a, b, c) \
+  { \
+    c ^= b; \
+    c -= rot(b, 14); \
+    a ^= c; \
+    a -= rot(c, 11); \
+    b ^= a; \
+    b -= rot(a, 25); \
+    c ^= b; \
+    c -= rot(b, 16); \
+    a ^= c; \
+    a -= rot(c, 4); \
+    b ^= a; \
+    b -= rot(a, 14); \
+    c ^= b; \
+    c -= rot(b, 24); \
+  } \
+  ((void)0)
+
+BLI_INLINE unsigned int BLI_hash_int_3d(unsigned int kx, unsigned int ky, unsigned int kz)
+{
+  unsigned int a, b, c;
+  a = b = c = 0xdeadbeef + (3 << 2) + 13;
+
+  c += kz;
+  b += ky;
+  a += kx;
+  final(a, b, c);
+
+  return c;
+}
 
+BLI_INLINE unsigned int BLI_hash_int_2d(unsigned int kx, unsigned int ky)
+{
   unsigned int a, b, c;
 
   a = b = c = 0xdeadbeef + (2 << 2) + 13;
   a += kx;
   b += ky;
 
-  c ^= b;
-  c -= rot(b, 14);
-  a ^= c;
-  a -= rot(c, 11);
-  b ^= a;
-  b -= rot(a, 25);
-  c ^= b;
-  c -= rot(b, 16);
-  a ^= c;
-  a -= rot(c, 4);
-  b ^= a;
-  b -= rot(a, 14);
-  c ^= b;
-  c -= rot(b, 24);
+  final(a, b, c);
 
   return c;
+}
 
+#undef final
 #undef rot
-}
 
 BLI_INLINE unsigned int BLI_hash_string(const char *str)
 {
diff --git a/source/blender/nodes/NOD_geometry_exec.hh b/source/blender/nodes/NOD_geometry_exec.hh
index 445e1ed6af2..cac04e18fc7 100644
--- a/source/blender/nodes/NOD_geometry_exec.hh
+++ b/source/blender/nodes/NOD_geometry_exec.hh
@@ -34,6 +34,8 @@ using bke::Float3ReadAttribute;
 using bke::Float3WriteAttribute;
 using bke::FloatReadAttribute;
 using bke::FloatWriteAttribute;
+using bke::Int32ReadAttribute;
+using bke::Int32WriteAttribute;
 using bke::PersistentDataHandleMap;
 using bke::PersistentObjectHandle;
 using bke::ReadAttribute;
diff --git a/source/blender/nodes/geometry/nodes/node_geo_attribute_randomize.cc b/source/blender/nodes/geometry/nodes/node_geo_attribute_randomize.cc
index 53df2e8c087..2c3acfc9735 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_attribute_randomize.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_attribute_randomize.cc
@@ -16,6 +16,7 @@
 
 #include "node_geometry_util.hh"
 
+#include "BLI_hash.h"
 #include "BLI_rand.hh"
 
 #include "DNA_mesh_types.h"
@@ -59,48 +60,85 @@ static void geo_node_attribute_randomize_update(bNodeTree *UNUSED(ntree), bNode
 
 namespace blender::nodes {
 
-static void randomize_attribute(BooleanWriteAttribute &attribute, RandomNumberGenerator &rng)
+/** Rehash to combine the seed with the "id" hash and a mutator for each dimension. */
+static float noise_from_index_and_mutator(const int seed, const int hash, const int mutator)
+{
+  const int combined_hash = BLI_hash_int_3d(seed, hash, mutator);
+  return BLI_hash_int_01(combined_hash);
+}
+
+/** Rehash to combine the seed with the "id" hash. */
+static float noise_from_index(const int seed, const int hash)
+{
+  const int combined_hash = BLI_hash_int_2d(seed, hash);
+  return BLI_hash_int_01(combined_hash);
+}
+
+static void randomize_attribute(BooleanWriteAttribute &attribute, Span<int> hashes, const int seed)
 {
   MutableSpan<bool> attribute_span = attribute.get_span();
   for (const int i : IndexRange(attribute.size())) {
-    const bool value = rng.get_float() > 0.5f;
+    const bool value = noise_from_index(seed, hashes[i]) > 0.5f;
     attribute_span[i] = value;
   }
   attribute.apply_span();
 }
 
-static void randomize_attribute(FloatWriteAttribute &attribute,
-                                float min,
-                                float max,
-                                RandomNumberGenerator &rng)
+static void randomize_attribute(
+    FloatWriteAttribute &attribute, float min, float max, Span<int> hashes, const int seed)
 {
   MutableSpan<float> attribute_span = attribute.get_span();
   for (const int i : IndexRange(attribute.size())) {
-    const float value = rng.get_float() * (max - min) + min;
+    const float value = noise_from_index(seed, hashes[i]) * (max - min) + min;
     attribute_span[i] = value;
   }
   attribute.apply_span();
 }
 
-static void randomize_attribute(Float3WriteAttribute &attribute,
-                                float3 min,
-                                float3 max,
-                                RandomNumberGenerator &rng)
+static void randomize_attribute(
+    Float3WriteAttribute &attribute, float3 min, float3 max, Span<int> hashes, const int seed)
 {
   MutableSpan<float3> attribute_span = attribute.get_span();
   for (const int i : IndexRange(attribute.size())) {
-    const float x = rng.get_float();
-    const float y = rng.get_float();
-    const float z = rng.get_float();
+    const float x = noise_from_index_and_mutator(seed, hashes[i], 47);
+    const float y = noise_from_index_and_mutator(seed, hashes[i], 8);
+    const float z = noise_from_index_and_mutator(seed, hashes[i], 64);
     const float3 value = float3(x, y, z) * (max - min) + min;
     attribute_span[i] = value;
   }
   attribute.apply_span();
 }
 
+static Array<int> get_element_hashes(GeometryComponent &component,
+                                     const AttributeDomain domain,
+                                     const int attribute_size)
+{
+  /* Hash the reserved name attribute "id" as a (hopefully) stable seed for each point. */
+  ReadAttributePtr hash_attribute = component.attribute_try_get_for_read("id", domain);
+  Array<int> hashes(attribute_size);
+  if (hash_attribute) {
+    BLI_assert(hashes.size() == hash_attribute->size());
+    const CPPType &cpp_type = hash_attribute->cpp_type();
+    fn::GSpan items = hash_attribute->get_span();
+    for (const int i : hashes.index_range()) {
+      hashes[i] = (int)cpp_type.hash(items[i]);
+    }
+  }
+  else {
+    /* If there is no "id" attribute for per-point variation, just create it here. */
+    RandomNumberGenerator rng;
+    rng.seed(0);
+    for (const int i : hashes.index_range()) {
+      hashes[i] = rng.get_int32();
+    }
+  }
+
+  return hashes;
+}
+
 static void randomize_attribute(GeometryComponent &component,
                                 const GeoNodeExecParams &params,
-                                RandomNumberGenerator &rng)
+                                const int seed)
 {
   const bNode &node = params.node();
   const CustomDataType data_type = static_cast<CustomDataType>(node.custom1);
@@ -116,24 +154,26 @@ static void randomize_attribute(GeometryComponent &component,
     return;
   }
 
+  Array<int> hashes = get_element_hashes(component, domain, attribute->size());
+
   switch (data_type) {
     case CD_PROP_FLOAT: {
       FloatWriteAttribute float_attribute = std::move(attribute);
       const float min_value = params.get_input<float>("Min_001");
       const float max_value = params.get_input<float>("Max_001");
-      randomize_attribute(float_attribute, min_value, max_value, rng);
+      randomize_attribute(float_attribute, min_value, max_value, hashes, seed);
       break;
     }
     case CD_PROP_FLOAT3: {
       Float3WriteAttribute float3_attribute = std::move(attribute);
       const float3 min_value = params.get_input<float3>("Min");
       const float3 max_value = params.get_input<float3>("Max");
-      randomize_attribute(float3_attribute, min_value, max_value, rng);
+      randomize_attribute(float3_attribute, min_value, max_value, hashes, seed);
       break;
     }
     case CD_PROP_BOOL: {
       BooleanWriteAttribute boolean_attribute = std::move(attribute);
-      randomize_attribute(boolean_attribute, rng);
+      randomize_attribute(boolean_attribute, hashes, seed);
       break;
     }
     default:
@@ -147,14 +187,10 @@ static void geo_node_random_attribute_exec(GeoNodeExecParams params)
   const int seed = params.get_input<int>("Seed");
 
   if (geometry_set.has<MeshComponent>()) {
-    RandomNumberGenerator rng;
-    rng.seed_random(seed);
-    randomize_attribute(geometry_set.get_component_for_write<MeshComponent>(), params, rng);
+    randomize_attribute(geometry_set.get_component_for_write<MeshComponent>(), params, seed);
   }
   if (geometry_set.has<PointCloudComponent>()) {
-    RandomNumberGenerator rng;
-    rng.seed_random(seed + 3245231);
-    randomize_attribute(geometry_set.get_component_for_write<PointCloudComponent>(), params, rng);
+    randomize_attribute(geometry_set.get_component_for_write<PointCloudComponent>(), params, seed);
   }
 
   params.set_output("Geometry", geometry_set);
diff --git a/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc b/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc
index 50c9246fc9b..1d3fbae5b2e 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc
@@ -58,6 +58,7 @@ namespace blender::nodes {
 static Vector<float3> random_scatter_points_from_mesh(const Mesh *mesh,
                                                       const float density,
                                                       const FloatReadAttribute &density_factors,
+                                                      Vector<int> &r_ids,
                                                       const int seed)
 {
   /* This only updates a cache and can be considered to be logically const. */
@@ -95,6 +96,9 @@ static Vector<float3> random_scatter_points_from_mesh(const Mesh *mesh,
       float3 point_pos;
       interp_v3_v3v3v3(point_pos, v0_pos, v1_pos, v2_pos, bary_coords);
       points.append(point_pos);
+
+      /* Build a hash stable even when the mesh is deformed. */
+      r_ids.append(((int)(bary_coords.hash()) + looptri_index));
     }
   }
 
@@ -106,10 +110,14 @@ struct RayCastAll_Data {
 
   BVHTree_RayCastCallback raycast_callback;
 
+  /** The original coordinate the result point was projected from. */
+  float2 raystart;
+
   const Mesh *mesh;
   float base_weight;
   FloatReadAttribute *density_factors;
   Vector<float3> *projected_points;
+  Vector<int> *stable_ids;
   float cur_point_weight;
 };
 
@@ -148,6 +156,9 @@ static void project_2d_bvh_callback(void *userdata,
 
     if (point_weight >= FLT_EPSILON && data->cur_point_weight <= point_weight) {
       data->projected_points->append(hit->co);
+
+      /* Build a hash stable even when the mesh is deformed. */
+      data->stable_ids->append((int)data->raystart.hash());
     }
   }
 }
@@ -156,6 +167,7 @@ static Vector<float3> poisson_scatter_points_from_mesh(const Mesh *mesh,
                                                        const float density,
                                                        const float minimum_distance,
                                                        const FloatReadAttribute &density_factors,
+                                                       Vector<int> &r_ids,
                                                        const int seed)
 {
   Vector<float3> points;
@@ -191,6 +203,7 @@ static Vector<float3> poisson_scatter_points_from_mesh(const Mesh *mesh,
   const float3 bounds_max = float3(point_scale_multiplier, point_scale_multiplier, 0);
   poisson_disk_point_elimination(&points, &output_points, 2.0f * minimum_distance, bounds_max);
   Vector<float3> final_points;
+  r_ids.reserve(output_points_target);
   final_points.reserve(output_points_target);
 
   /* Check if we have any points we should remove from the final possion distribition. */
@@ -205,6 +218,7 @@ static Vector<float3> poisson_scatter_points_from_mesh(const Mesh *mesh,
   data.raycast_callback = treedata.raycast_callback;
   data.mesh = mesh;
   data.projected_points = &final_points;
+  data.stable_ids = &r_ids;
   data.density_factors = const_cast<FloatReadAttribute *>(&density_factors);
   data.base_weight = std::min(
       1.0f, density / (output_points.size() / (point_scale_multiplier * point_scale_multiplier)));
@@ -229,6 +243,7 @@ static Vector<float3> poisson_scatter_points_from_mesh(const Mesh *mesh,
         raystart.y = output_points[idx].y + tile_curr_y_coord;
 
         data.cur_point_weight = (float)idx / (float)output_points.size();
+        data.raystart = raystart;
 
         BLI_bvhtree_ray_cast_all(
             treedata.tree, raystart, dir, 0.0f, max_dist, project_2d_bvh_callback, &data);
@@ -267,15 +282,17 @@ static void geo_node_point_distribute_exec(GeoNodeExecParams params)
       density_attribute, ATTR_DOMAIN_POINT, 1.0f);
   const int seed = params.get_input<int>("Seed");
 
+  Vector<int> stable_ids;
   Vector<float3> points;
-
   switch (distribute_method) {
     case GEO_NODE_POINT_DISTRIBUTE_RANDOM:
-      points = random_scatter_points_from_mesh(mesh_in, density, density_factors, seed);
+      points = random_scatter_points_from_mesh(
+          mesh_in, density, density_factors, stable_ids, seed);
       break;
     case GEO_NODE_POINT_DISTRIBUTE_POISSON:
       const float min_dist = params.extract_input<float>("Distance Min");
-      points = poisson_scatter_points_from_mesh(mesh_in, density, min_dist, density_factors, seed);
+      points = poisson_scatter_points_from_mesh(
+          mesh_in, density, min_dist, density_factors, stable_ids, seed);
       break;
   }
 
@@ -286,7 +303,16 @@ static void geo_node_point_distribute_exec(GeoNodeExecParams params)
     pointcloud->radius[i] = 0.05f;
   }
 
-  geometry_set_out.replace_pointcloud(pointcloud);
+  PointCloudComponent &point_component =
+      geometry_set_out.get_component_for_write<PointCloudComponent>();
+  point_component.replace(pointcloud);
+
+  Int32WriteAttribute stable_id_attribute = point_component.attribute_try_ensure_for_write(
+      "id", ATTR_DOMAIN_POINT, CD_PROP_INT32);
+  MutableSpan<int> stable_ids_span = stable_id_attribute.get_span();
+  stable_ids_span.copy_from(stable_ids);
+  stable_id_attribute.apply_span();
+
   params.set_output("Geometry", std::move(geometry_set_out));
 }
 }  // namespace blender::nodes