From 98db4cc6391df8c8b21516bbdbc0af8f493a15b3 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Fri, 12 Feb 2021 17:41:28 +0100 Subject: 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 --- source/blender/blenkernel/BKE_geometry_set.h | 2 +- source/blender/blenkernel/BKE_geometry_set.hh | 9 ++++ source/blender/blenkernel/intern/geometry_set.cc | 69 ++++++++++++++++++++++-- source/blender/blenkernel/intern/object_dupli.c | 10 ++-- 4 files changed, 82 insertions(+), 8 deletions(-) diff --git a/source/blender/blenkernel/BKE_geometry_set.h b/source/blender/blenkernel/BKE_geometry_set.h index 27ac6d98688..ac42674654f 100644 --- a/source/blender/blenkernel/BKE_geometry_set.h +++ b/source/blender/blenkernel/BKE_geometry_set.h @@ -47,7 +47,7 @@ typedef struct InstancedData { int BKE_geometry_set_instances(const struct GeometrySet *geometry_set, float (**r_transforms)[4][4], - int **r_ids, + const int **r_almost_unique_ids, struct InstancedData **r_instanced_data); #ifdef __cplusplus 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 ids_; blender::Vector 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 almost_unique_ids_; + public: InstancesComponent(); ~InstancesComponent() = default; @@ -445,6 +452,8 @@ class InstancesComponent : public GeometryComponent { blender::MutableSpan transforms(); int instances_amount() const; + blender::Span almost_unique_ids() const; + bool is_empty() const final; static constexpr inline GeometryComponentType static_type = GeometryComponentType::Instances; diff --git a/source/blender/blenkernel/intern/geometry_set.cc b/source/blender/blenkernel/intern/geometry_set.cc index a47a3dbc872..6db15c9393d 100644 --- a/source/blender/blenkernel/intern/geometry_set.cc +++ b/source/blender/blenkernel/intern/geometry_set.cc @@ -22,6 +22,8 @@ #include "DNA_object_types.h" +#include "BLI_rand.hh" + #include "MEM_guardedalloc.h" using blender::float3; @@ -542,6 +544,68 @@ bool InstancesComponent::is_empty() const return transforms_.size() == 0; } +static blender::Array generate_unique_instance_ids(Span original_ids) +{ + using namespace blender; + Array unique_ids(original_ids.size()); + + Set used_unique_ids; + used_unique_ids.reserve(original_ids.size()); + Vector instances_with_id_collision; + for (const int instance_index : original_ids.index_range()) { + const int original_id = original_ids[instance_index]; + if (used_unique_ids.add(original_id)) { + /* The original id has not been used by another instance yet. */ + unique_ids[instance_index] = original_id; + } + else { + /* The original id of this instance collided with a previous instance, it needs to be looked + * at again in a second pass. Don't generate a new random id here, because this might collide + * with other existing ids. */ + instances_with_id_collision.append(instance_index); + } + } + + Map generator_by_original_id; + for (const int instance_index : instances_with_id_collision) { + const int original_id = original_ids[instance_index]; + RandomNumberGenerator &rng = generator_by_original_id.lookup_or_add_cb(original_id, [&]() { + RandomNumberGenerator rng; + rng.seed_random(original_id); + return rng; + }); + + const int max_iteration = 100; + for (int iteration = 0;; iteration++) { + /* Try generating random numbers until an unused one has been found. */ + const int random_id = rng.get_int32(); + if (used_unique_ids.add(random_id)) { + /* This random id is not used by another instance. */ + unique_ids[instance_index] = random_id; + break; + } + if (iteration == max_iteration) { + /* It seems to be very unlikely that we ever run into this case (assuming there are less + * than 2^30 instances). However, if that happens, it's better to use an id that is not + * unique than to be stuck in an infinite loop. */ + unique_ids[instance_index] = original_id; + break; + } + } + } + + return unique_ids; +} + +blender::Span InstancesComponent::almost_unique_ids() const +{ + std::lock_guard lock(almost_unique_ids_mutex_); + if (almost_unique_ids_.size() != ids_.size()) { + almost_unique_ids_ = generate_unique_instance_ids(ids_); + } + return almost_unique_ids_; +} + /** \} */ /* -------------------------------------------------------------------- */ @@ -560,7 +624,7 @@ bool BKE_geometry_set_has_instances(const GeometrySet *geometry_set) int BKE_geometry_set_instances(const GeometrySet *geometry_set, float (**r_transforms)[4][4], - int **r_ids, + const int **r_almost_unique_ids, InstancedData **r_instanced_data) { const InstancesComponent *component = geometry_set->get_component_for_read(); @@ -568,9 +632,8 @@ int BKE_geometry_set_instances(const GeometrySet *geometry_set, return 0; } *r_transforms = (float(*)[4][4])component->transforms().data(); - *r_ids = (int *)component->ids().data(); - *r_instanced_data = (InstancedData *)component->instanced_data().data(); *r_instanced_data = (InstancedData *)component->instanced_data().data(); + *r_almost_unique_ids = (const int *)component->almost_unique_ids().data(); return component->instances_amount(); } diff --git a/source/blender/blenkernel/intern/object_dupli.c b/source/blender/blenkernel/intern/object_dupli.c index 6c8a57f8599..632e7519f05 100644 --- a/source/blender/blenkernel/intern/object_dupli.c +++ b/source/blender/blenkernel/intern/object_dupli.c @@ -814,15 +814,17 @@ static const DupliGenerator gen_dupli_verts_pointcloud = { static void make_duplis_instances_component(const DupliContext *ctx) { float(*instance_offset_matrices)[4][4]; - int *ids; InstancedData *instanced_data; - const int amount = BKE_geometry_set_instances( - ctx->object->runtime.geometry_set_eval, &instance_offset_matrices, &ids, &instanced_data); + const int *almost_unique_ids; + const int amount = BKE_geometry_set_instances(ctx->object->runtime.geometry_set_eval, + &instance_offset_matrices, + &almost_unique_ids, + &instanced_data); for (int i = 0; i < amount; i++) { InstancedData *data = &instanced_data[i]; - const int id = ids[i] != -1 ? ids[i] : i; + const int id = almost_unique_ids[i]; if (data->type == INSTANCE_DATA_TYPE_OBJECT) { Object *object = data->data.object; -- cgit v1.2.3