Blender V5.3
instances.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "BLI_array_utils.hh"
10#include "BLI_listbase.hh"
11#include "BLI_rand.hh"
12#include "BLI_task.hh"
13
15#include "DNA_object_types.h"
16
17#include "BKE_geometry_set.hh"
19#include "BKE_instances.hh"
20
22
23namespace blender::bke {
24
26 : type_(Type::GeometrySet),
27 geometry_set_(std::make_unique<GeometrySet>(std::move(geometry_set)))
28{
29}
30
32 : type_(other.type_), data_(other.data_)
33{
34 if (other.geometry_set_) {
35 geometry_set_ = std::make_unique<GeometrySet>(*other.geometry_set_);
36 }
37}
38
40{
41 if (type_ != Type::GeometrySet) {
42 return;
43 }
44 geometry_set_->ensure_owns_direct_data();
45}
46
48{
49 if (type_ != Type::GeometrySet) {
50 /* The object and collection instances are not direct data. */
51 return true;
52 }
53 return geometry_set_->owns_direct_data();
54}
55
57{
58 switch (type_) {
59 case Type::GeometrySet: {
60 geometry_set_->count_memory(memory);
61 }
62 default: {
63 break;
64 }
65 }
66}
67
72
77
78static std::unique_ptr<bke::Instances> convert_collection_to_instances(
79 const Collection &collection)
80{
81 const int instances_num = collection.children.count() + collection.gobject.count();
82
83 auto instances = std::make_unique<bke::Instances>(instances_num);
84
85 MutableSpan<int> handles = instances->reference_handles_for_write();
86 MutableSpan<float4x4> transforms = instances->transforms_for_write();
87
88 int i = 0;
89
90 for (CollectionChild &collection_child : collection.children) {
92 transform.location() += float3(collection_child.collection->instance_offset);
93 transform.location() -= float3(collection.instance_offset);
94 transforms[i] = transform;
95
96 handles[i] = instances->add_reference(*collection_child.collection);
97
98 i++;
99 }
100
101 for (CollectionObject &collection_object : collection.gobject) {
103 transform.location() -= float3(collection.instance_offset);
104 transform *= (collection_object.ob)->object_to_world();
105 transforms[i] = transform;
106
107 handles[i] = instances->add_reference(*collection_object.ob);
108
109 i++;
110 }
111
112 return instances;
113}
114
116{
117 r_geometry_set.clear();
118 switch (type_) {
119 case Type::Object: {
120 const Object &object = this->object();
121 r_geometry_set = bke::object_get_evaluated_geometry_set(object);
122 break;
123 }
124 case Type::Collection: {
125 const Collection &collection = this->collection();
126 std::unique_ptr<bke::Instances> instances_ptr = convert_collection_to_instances(collection);
127 r_geometry_set.replace_instances(instances_ptr.release());
128 break;
129 }
130 case Type::GeometrySet: {
131 r_geometry_set = this->geometry_set();
132 break;
133 }
134 case Type::None: {
135 break;
136 }
137 }
138}
139
141{
142 switch (type_) {
143 case Type::Object:
144 return this->object().id.name + 2;
145 case Type::Collection:
146 return this->collection().id.name + 2;
148 return this->geometry_set().name();
149 case Type::None:
150 break;
151 }
152 return "";
153}
154
156{
157 if (a.geometry_set_ && b.geometry_set_) {
158 return *a.geometry_set_ == *b.geometry_set_;
159 }
160 return a.type_ == b.type_ && a.data_ == b.data_;
161}
162
164{
165 const uint64_t geometry_hash = geometry_set_ ? geometry_set_->hash() : 0;
166 return get_default_hash(geometry_hash, type_, data_);
167}
168
169Instances::Instances() = default;
170
171Instances::Instances(const int size) : instances_num_(size)
172{
173 attributes_.resize(AttrDomain::Instance, size);
174}
175
177 : references_(std::move(other.references_)),
178 instances_num_(other.instances_num_),
179 attributes_(std::move(other.attributes_)),
180 reference_user_counts_(std::move(other.reference_user_counts_)),
181 unique_ids_cache_(std::move(other.unique_ids_cache_))
182{
183}
184
186 : references_(other.references_),
187 instances_num_(other.instances_num_),
188 attributes_(other.attributes_),
189 reference_user_counts_(other.reference_user_counts_),
190 unique_ids_cache_(other.unique_ids_cache_)
191{
192}
193
194Instances::~Instances() = default;
195
197{
198 if (this == &other) {
199 return *this;
200 }
201 std::destroy_at(this);
202 new (this) Instances(other);
203 return *this;
204}
205
207{
208 if (this == &other) {
209 return *this;
210 }
211 std::destroy_at(this);
212 new (this) Instances(std::move(other));
213 return *this;
214}
215
216void Instances::resize(int size)
217{
218 attributes_.resize(AttrDomain::Instance, size);
219 instances_num_ = size;
220}
221
223{
225 attributes_, AttrDomain::Instance, ".reference_index", instances_num_)
226 .value_or(Span<int>());
227}
228
230{
232 attributes_, AttrDomain::Instance, ".reference_index", instances_num_);
233}
234
236{
238 attributes_, AttrDomain::Instance, "instance_transform", instances_num_)
239 .value_or(Span<float4x4>());
240}
241
243{
245 attributes_, AttrDomain::Instance, "instance_transform", instances_num_);
246}
247
249{
250 /* If this assert fails, it means #ensure_geometry_instances must be called first or that the
251 * reference can't be converted to a geometry set. */
252 BLI_assert(references_[reference_index].type() == InstanceReference::Type::GeometrySet);
253
254 return references_[reference_index].geometry_set();
255}
256
258{
259 for (const int i : references_.index_range()) {
260 const InstanceReference &reference = references_[i];
261 if (reference == query) {
262 return i;
263 }
264 }
265 return std::nullopt;
266}
267
269{
270 if (std::optional<int> handle = this->find_reference_handle(reference)) {
271 return *handle;
272 }
273 return this->add_new_reference(reference);
274}
275
277{
278 if (std::optional<int> handle = this->find_reference_handle(reference)) {
279 return *handle;
280 }
281 return this->add_new_reference(std::move(reference));
282}
283
285{
287 return references_.append_and_get_index(std::move(reference));
288}
289
291{
292 return references_;
293}
294
299
300void Instances::remove(const IndexMask &mask, const AttributeFilter &attribute_filter)
301{
302 const std::optional<IndexRange> masked_range = mask.to_range();
303 if (masked_range.has_value() && masked_range->start() == 0) {
304 /* Deleting from the end of the array can be much faster since no data has to be shifted. */
305 this->resize(mask.size());
307 return;
308 }
309
310 Instances new_instances;
311 new_instances.references_ = std::move(references_);
312 new_instances.instances_num_ = mask.size();
313
317 attribute_filter,
318 mask,
319 new_instances.attributes_for_write());
320
321 *this = std::move(new_instances);
322
324}
325
327{
328 const int tot_instances = instances_num_;
329 const int tot_references_before = references_.size();
330
331 if (tot_instances == 0) {
332 /* If there are no instances, no reference is needed. */
333 references_.clear();
334 return;
335 }
336 if (tot_references_before == 1) {
337 /* There is only one reference and at least one instance. So the only existing reference is
338 * used. Nothing to do here. */
339 return;
340 }
341
342 const Span<int> reference_handles = this->reference_handles();
343
344 Array<bool> usage_by_handle(tot_references_before, false);
345 Mutex mutex;
346
347 /* Loop over all instances to see which references are used. */
348 threading::parallel_for(IndexRange(tot_instances), 1000, [&](IndexRange range) {
349 /* Use local counter to avoid lock contention. */
350 Array<bool> local_usage_by_handle(tot_references_before, false);
351
352 for (const int i : range) {
353 const int handle = reference_handles[i];
354 BLI_assert(handle >= 0 && handle < tot_references_before);
355 local_usage_by_handle[handle] = true;
356 }
357
358 std::lock_guard lock{mutex};
359 for (const int i : IndexRange(tot_references_before)) {
360 usage_by_handle[i] |= local_usage_by_handle[i];
361 }
362 });
363
364 if (!usage_by_handle.as_span().contains(false)) {
365 /* All references are used. */
366 return;
367 }
368
369 /* Create new references and a mapping for the handles. */
370 Vector<int> handle_mapping;
371 Vector<InstanceReference> new_references;
372 int next_new_handle = 0;
373 bool handles_have_to_be_updated = false;
374 for (const int old_handle : IndexRange(tot_references_before)) {
375 if (!usage_by_handle[old_handle]) {
376 /* Add some dummy value. It won't be read again. */
377 handle_mapping.append(-1);
378 }
379 else {
380 const InstanceReference &reference = references_[old_handle];
381 handle_mapping.append(next_new_handle);
382 new_references.append(reference);
383 if (old_handle != next_new_handle) {
384 handles_have_to_be_updated = true;
385 }
386 next_new_handle++;
387 }
388 }
389 references_ = new_references;
390
391 if (!handles_have_to_be_updated) {
392 /* All remaining handles are the same as before, so they don't have to be updated. This happens
393 * when unused handles are only at the end. */
394 return;
395 }
396
397 /* Update handles of instances. */
398 {
400 threading::parallel_for(IndexRange(tot_instances), 1000, [&](IndexRange range) {
401 for (const int i : range) {
402 reference_handles[i] = handle_mapping[reference_handles[i]];
403 }
404 });
405 }
406}
407
409{
410 return this->instances_num_;
411}
412
414{
415 return references_.size();
416}
417
419{
420 for (const InstanceReference &reference : references_) {
421 if (!reference.owns_direct_data()) {
422 return false;
423 }
424 }
425 return true;
426}
427
429{
430 for (const InstanceReference &const_reference : references_) {
431 /* `const` cast is fine because we are not changing anything that would change the hash of the
432 * reference. */
433 InstanceReference &reference = const_cast<InstanceReference &>(const_reference);
434 reference.ensure_owns_direct_data();
435 }
436}
437
439{
440 attributes_.count_memory(memory);
441 for (const InstanceReference &reference : references_) {
442 reference.count_memory(memory);
443 }
444}
445
447{
448 Array<int> unique_ids(original_ids.size());
449
450 Set<int> used_unique_ids;
451 used_unique_ids.reserve(original_ids.size());
452 Vector<int> instances_with_id_collision;
453 for (const int instance_index : original_ids.index_range()) {
454 const int original_id = original_ids[instance_index];
455 if (used_unique_ids.add(original_id)) {
456 /* The original id has not been used by another instance yet. */
457 unique_ids[instance_index] = original_id;
458 }
459 else {
460 /* The original id of this instance collided with a previous instance, it needs to be looked
461 * at again in a second pass. Don't generate a new random id here, because this might collide
462 * with other existing ids. */
463 instances_with_id_collision.append(instance_index);
464 }
465 }
466
467 Map<int, RandomNumberGenerator> generator_by_original_id;
468 for (const int instance_index : instances_with_id_collision) {
469 const int original_id = original_ids[instance_index];
470 RandomNumberGenerator &rng = generator_by_original_id.lookup_or_add_cb(original_id, [&]() {
472 rng.seed_random(original_id);
473 return rng;
474 });
475
476 const int max_iteration = 100;
477 for (int iteration = 0;; iteration++) {
478 /* Try generating random numbers until an unused one has been found. */
479 const int random_id = rng.get_int32();
480 if (used_unique_ids.add(random_id)) {
481 /* This random id is not used by another instance. */
482 unique_ids[instance_index] = random_id;
483 break;
484 }
485 if (iteration == max_iteration) {
486 /* The likelihood of running into this case is very low even if there is a huge number of
487 * instances. For correctness, it's still good to systematically find an unused id instead
488 * of purely relying on randomness. */
489 for (const int generated_id : IndexRange(INT32_MAX)) {
490 if (used_unique_ids.add(generated_id)) {
491 unique_ids[instance_index] = generated_id;
492 break;
493 }
494 }
495 break;
496 }
497 }
498 }
499
500 return unique_ids;
501}
502
504{
505 reference_user_counts_.ensure([&](Array<int> &r_data) {
506 const int references_num = references_.size();
508 r_data.fill(0);
509
510 const Span<int> handles = this->reference_handles();
511 for (const int handle : handles) {
512 if (handle >= 0 && handle < references_num) {
513 r_data[handle]++;
514 }
515 }
516 });
517 return reference_user_counts_.data();
518}
519
521{
522 unique_ids_cache_.ensure([&](Array<int> &r_data) {
523 const VArraySpan<int> instance_ids = *this->attributes().lookup<int>("id");
524 if (instance_ids.is_empty()) {
525 r_data.reinitialize(instances_num_);
527 return;
528 }
529 r_data = generate_unique_instance_ids(instance_ids);
530 });
531 return unique_ids_cache_.data();
532}
533
535{
536 return transform.location();
537}
538
540{
541 transform.location() = position;
542}
543
549
556
557} // namespace blender::bke
#define INT32_MAX
Object groups, one object can be in many groups at once.
Object is a sort of wrapper for general info.
volatile int lock
Span< T > as_span() const
Definition BLI_array.hh:254
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
void fill(const T &value) const
Definition BLI_array.hh:283
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
constexpr IndexRange()=default
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Definition BLI_map.hh:620
void seed_random(uint32_t seed)
Definition rand.cc:297
void reserve(const int64_t n)
Definition BLI_set.hh:656
bool add(const Key &key)
Definition BLI_set.hh:248
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
static VArray from_derived_span(Span< StructT > values)
static VMutableArray from_derived_span(MutableSpan< StructT > values)
int64_t size() const
void append(const T &value)
GAttributeReader lookup(const StringRef name) const
AttributeAccessor(const void *owner, const AttributeAccessorFunctions &fn)
void count_memory(MemoryCounter &memory) const
Definition instances.cc:56
void to_geometry_set(GeometrySet &r_geometry_set) const
Definition instances.cc:115
StringRefNull name() const
Definition instances.cc:140
friend bool operator==(const InstanceReference &a, const InstanceReference &b)
Definition instances.cc:155
Collection & collection() const
Span< int > reference_handles() const
Definition instances.cc:222
MutableSpan< int > reference_handles_for_write()
Definition instances.cc:229
int add_reference(const InstanceReference &reference)
Definition instances.cc:268
void remove(const IndexMask &mask, const AttributeFilter &attribute_filter)
Definition instances.cc:300
GeometrySet & geometry_set_from_reference(int reference_index)
Definition instances.cc:248
Span< float4x4 > transforms() const
Definition instances.cc:235
Span< InstanceReference > references() const
Definition instances.cc:290
Span< int > reference_user_counts() const
Definition instances.cc:503
int add_new_reference(InstanceReference reference)
Definition instances.cc:284
Instances & operator=(const Instances &other)
Definition instances.cc:196
int references_num() const
Definition instances.cc:413
bke::MutableAttributeAccessor attributes_for_write()
Definition instances.cc:73
bke::AttributeAccessor attributes() const
Definition instances.cc:68
MutableSpan< InstanceReference > references_for_write()
Definition instances.cc:295
int instances_num() const
Definition instances.cc:408
void count_memory(MemoryCounter &memory) const
Definition instances.cc:438
bool owns_direct_data() const
Definition instances.cc:418
void resize(int size)
Definition instances.cc:216
std::optional< int > find_reference_handle(const InstanceReference &query)
Definition instances.cc:257
MutableSpan< float4x4 > transforms_for_write()
Definition instances.cc:242
Span< int > unique_ids() const
Definition instances.cc:520
MutableAttributeAccessor(void *owner, const AttributeAccessorFunctions &fn)
constexpr bool is_empty() const
#define instance_index
#define position
void fill_index_range(MutableSpan< T > span, const T start=0)
GMutableSpan get_mutable_attribute(AttributeStorage &storage, const AttrDomain domain, const CPPType &cpp_type, const StringRef name, const int64_t domain_size, const void *custom_default_value)
std::optional< GSpan > get_span_attribute(const AttributeStorage &storage, const AttrDomain domain, const CPPType &cpp_type, const StringRef name, const int64_t domain_size)
static std::unique_ptr< bke::Instances > convert_collection_to_instances(const Collection &collection)
Definition instances.cc:78
void gather_attributes(AttributeAccessor src_attributes, AttrDomain src_domain, AttrDomain dst_domain, const AttributeFilter &attribute_filter, const IndexMask &selection, MutableAttributeAccessor dst_attributes)
static float3 get_transform_position(const float4x4 &transform)
Definition instances.cc:534
GeometrySet object_get_evaluated_geometry_set(const Object &object, bool apply_subdiv=true)
VArray< float3 > instance_position_varray(const Instances &instances)
Definition instances.cc:544
static Array< int > generate_unique_instance_ids(Span< int > original_ids)
Definition instances.cc:446
VMutableArray< float3 > instance_position_varray_for_write(Instances &instances)
Definition instances.cc:550
static void set_transform_position(float4x4 &transform, const float3 position)
Definition instances.cc:539
const AttributeAccessorFunctions & instance_attribute_accessor_functions()
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
unsigned __int64 uint64_t
Definition BKE_text.h:91
MatBase< float, 4, 4 > float4x4
std::mutex Mutex
Definition BLI_mutex.hh:51
VecBase< float, 3 > float3
constexpr uint64_t get_default_hash(const T &v, const Args &...args)
Definition BLI_hash.hh:252
ListBaseT< CollectionChild > children
ListBaseT< CollectionObject > gobject
char name[258]
Definition DNA_ID.h:433
StringRefNull name() const
void replace_instances(Instances *instances, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)