Fix T84899: instance ids are not unique in common cases

Ids stored in the `id` attribute cannot be assumed to be unique. While they
might be unique in some cases, this is not something that can be guaranteed
in general. For some use cases (e.g. generating "stable randomness" on points)
uniqueness is not important. To support features like motion blur, unique ids
are important though.

This patch implements a simple algorithm that turns non-unique ids into
unique ones. It might fail to do so under very unlikely circumstances, in
which it returns non-unique ids instead of possibly going into an endless
loop.

Here are some requirements I set for the algorithm:
* Ids that are unique already, must not be changed.
* The same input should generate the same output.
* Handle cases when all ids are different and when all ids are the same
  equally well (in expected linear time).
* Small changes in the input id array should ideally only have a small
  impact on the output id array.

The reported bug happened because cycles found multiple objects with
the same id and thought that it was a single object that moved on every
check.

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

1 files changed, 9 insertions, 0 deletions

diff --git a/source/blender/blenkernel/BKE_geometry_set.hh b/source/blender/blenkernel/BKE_geometry_set.hh
index 31739465afd..6f6269be208 100644
--- a/source/blender/blenkernel/BKE_geometry_set.hh
+++ b/source/blender/blenkernel/BKE_geometry_set.hh
@@ -429,6 +429,13 @@ class InstancesComponent : public GeometryComponent {
   blender::Vector<int> ids_;
   blender::Vector<InstancedData> instanced_data_;
 
+  /* These almost unique ids are generated based on `ids_`, which might not contain unique ids at
+   * all. They are *almost* unique, because under certain very unlikely circumstances, they are not
+   * unique. Code using these ids should not crash when they are not unique but can generally
+   * expect them to be unique. */
+  mutable std::mutex almost_unique_ids_mutex_;
+  mutable blender::Array<int> almost_unique_ids_;
+
  public:
   InstancesComponent();
   ~InstancesComponent() = default;
@@ -445,6 +452,8 @@ class InstancesComponent : public GeometryComponent {
   blender::MutableSpan<blender::float4x4> transforms();
   int instances_amount() const;
 
+  blender::Span<int> almost_unique_ids() const;
+
   bool is_empty() const final;
 
   static constexpr inline GeometryComponentType static_type = GeometryComponentType::Instances;