diff options
-rw-r--r-- | source/blender/blenkernel/BKE_geometry_set.h | 2 | ||||
-rw-r--r-- | source/blender/blenkernel/BKE_geometry_set.hh | 9 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/geometry_set.cc | 69 | ||||
-rw-r--r-- | 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<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; 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<int> generate_unique_instance_ids(Span<int> original_ids) +{ + using namespace blender; + Array<int> unique_ids(original_ids.size()); + + Set<int> used_unique_ids; + used_unique_ids.reserve(original_ids.size()); + Vector<int> 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<int, RandomNumberGenerator> 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<int> 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<InstancesComponent>(); @@ -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; |