Blender  V3.3
geometry_component_instances.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #include <mutex>
4 
5 #include "BLI_float4x4.hh"
6 #include "BLI_index_mask.hh"
7 #include "BLI_map.hh"
8 #include "BLI_rand.hh"
9 #include "BLI_set.hh"
10 #include "BLI_span.hh"
11 #include "BLI_task.hh"
12 #include "BLI_vector.hh"
13 
14 #include "DNA_collection_types.h"
15 
16 #include "BKE_attribute_math.hh"
17 #include "BKE_geometry_set.hh"
19 
21 
22 #include "BLI_cpp_type_make.hh"
23 
24 using blender::float4x4;
25 using blender::GSpan;
26 using blender::IndexMask;
27 using blender::Map;
29 using blender::Set;
30 using blender::Span;
31 using blender::VectorSet;
32 
34 
35 /* -------------------------------------------------------------------- */
40 {
41 }
42 
44 {
45  InstancesComponent *new_component = new InstancesComponent();
46  new_component->instance_reference_handles_ = instance_reference_handles_;
47  new_component->instance_transforms_ = instance_transforms_;
48  new_component->references_ = references_;
49  new_component->attributes_ = attributes_;
50  return new_component;
51 }
52 
53 void InstancesComponent::reserve(int min_capacity)
54 {
55  instance_reference_handles_.reserve(min_capacity);
56  instance_transforms_.reserve(min_capacity);
57  attributes_.reallocate(min_capacity);
58 }
59 
60 void InstancesComponent::resize(int capacity)
61 {
62  instance_reference_handles_.resize(capacity);
63  instance_transforms_.resize(capacity);
64  attributes_.reallocate(capacity);
65 }
66 
68 {
69  instance_reference_handles_.clear();
70  instance_transforms_.clear();
71  attributes_.clear();
72  references_.clear();
73 }
74 
75 void InstancesComponent::add_instance(const int instance_handle, const float4x4 &transform)
76 {
77  BLI_assert(instance_handle >= 0);
78  BLI_assert(instance_handle < references_.size());
79  instance_reference_handles_.append(instance_handle);
80  instance_transforms_.append(transform);
81  attributes_.reallocate(this->instances_num());
82 }
83 
85 {
86  return instance_reference_handles_;
87 }
88 
90 {
91  return instance_reference_handles_;
92 }
93 
95 {
96  return instance_transforms_;
97 }
99 {
100  return instance_transforms_;
101 }
102 
104 {
105  /* If this assert fails, it means #ensure_geometry_instances must be called first or that the
106  * reference can't be converted to a geometry set. */
107  BLI_assert(references_[reference_index].type() == InstanceReference::Type::GeometrySet);
108 
109  /* The const cast is okay because the instance's hash in the set
110  * is not changed by adjusting the data inside the geometry set. */
111  return const_cast<GeometrySet &>(references_[reference_index].geometry_set());
112 }
113 
115 {
116  return references_.index_of_or_add_as(reference);
117 }
118 
120 {
121  return references_;
122 }
123 
124 template<typename T>
126 {
127  BLI_assert(src.data() != dst.data());
128  using namespace blender;
129  threading::parallel_for(mask.index_range(), 1024, [&](IndexRange range) {
130  for (const int i : range) {
131  dst[i] = src[mask[i]];
132  }
133  });
134 }
135 
137 {
138  using namespace blender;
139  if (mask.is_range() && mask.as_range().start() == 0) {
140  /* Deleting from the end of the array can be much faster since no data has to be shifted. */
141  this->resize(mask.size());
142  this->remove_unused_references();
143  return;
144  }
145 
146  Vector<int> new_handles(mask.size());
147  copy_data_based_on_mask<int>(this->instance_reference_handles(), new_handles, mask);
148  instance_reference_handles_ = std::move(new_handles);
149  Vector<float4x4> new_transforms(mask.size());
150  copy_data_based_on_mask<float4x4>(this->instance_transforms(), new_transforms, mask);
151  instance_transforms_ = std::move(new_transforms);
152 
153  const bke::CustomDataAttributes &src_attributes = attributes_;
154 
155  bke::CustomDataAttributes dst_attributes;
156  dst_attributes.reallocate(mask.size());
157 
158  src_attributes.foreach_attribute(
159  [&](const bke::AttributeIDRef &id, const bke::AttributeMetaData &meta_data) {
160  if (!id.should_be_kept()) {
161  return true;
162  }
163 
164  GSpan src = *src_attributes.get_for_read(id);
165  dst_attributes.create(id, meta_data.data_type);
166  GMutableSpan dst = *dst_attributes.get_for_write(id);
167 
168  attribute_math::convert_to_static_type(src.type(), [&](auto dummy) {
169  using T = decltype(dummy);
170  copy_data_based_on_mask<T>(src.typed<T>(), dst.typed<T>(), mask);
171  });
172  return true;
173  },
175 
176  attributes_ = std::move(dst_attributes);
177  this->remove_unused_references();
178 }
179 
181 {
182  using namespace blender;
183  using namespace blender::bke;
184 
185  const int tot_instances = this->instances_num();
186  const int tot_references_before = references_.size();
187 
188  if (tot_instances == 0) {
189  /* If there are no instances, no reference is needed. */
190  references_.clear();
191  return;
192  }
193  if (tot_references_before == 1) {
194  /* There is only one reference and at least one instance. So the only existing reference is
195  * used. Nothing to do here. */
196  return;
197  }
198 
199  Array<bool> usage_by_handle(tot_references_before, false);
201 
202  /* Loop over all instances to see which references are used. */
203  threading::parallel_for(IndexRange(tot_instances), 1000, [&](IndexRange range) {
204  /* Use local counter to avoid lock contention. */
205  Array<bool> local_usage_by_handle(tot_references_before, false);
206 
207  for (const int i : range) {
208  const int handle = instance_reference_handles_[i];
209  BLI_assert(handle >= 0 && handle < tot_references_before);
210  local_usage_by_handle[handle] = true;
211  }
212 
213  std::lock_guard lock{mutex};
214  for (const int i : IndexRange(tot_references_before)) {
215  usage_by_handle[i] |= local_usage_by_handle[i];
216  }
217  });
218 
219  if (!usage_by_handle.as_span().contains(false)) {
220  /* All references are used. */
221  return;
222  }
223 
224  /* Create new references and a mapping for the handles. */
225  Vector<int> handle_mapping;
226  VectorSet<InstanceReference> new_references;
227  int next_new_handle = 0;
228  bool handles_have_to_be_updated = false;
229  for (const int old_handle : IndexRange(tot_references_before)) {
230  if (!usage_by_handle[old_handle]) {
231  /* Add some dummy value. It won't be read again. */
232  handle_mapping.append(-1);
233  }
234  else {
235  const InstanceReference &reference = references_[old_handle];
236  handle_mapping.append(next_new_handle);
237  new_references.add_new(reference);
238  if (old_handle != next_new_handle) {
239  handles_have_to_be_updated = true;
240  }
241  next_new_handle++;
242  }
243  }
244  references_ = new_references;
245 
246  if (!handles_have_to_be_updated) {
247  /* All remaining handles are the same as before, so they don't have to be updated. This happens
248  * when unused handles are only at the end. */
249  return;
250  }
251 
252  /* Update handles of instances. */
253  threading::parallel_for(IndexRange(tot_instances), 1000, [&](IndexRange range) {
254  for (const int i : range) {
255  instance_reference_handles_[i] = handle_mapping[instance_reference_handles_[i]];
256  }
257  });
258 }
259 
261 {
262  return instance_transforms_.size();
263 }
264 
266 {
267  return references_.size();
268 }
269 
271 {
272  return this->instance_reference_handles_.size() == 0;
273 }
274 
276 {
277  for (const InstanceReference &reference : references_) {
278  if (!reference.owns_direct_data()) {
279  return false;
280  }
281  }
282  return true;
283 }
284 
286 {
287  BLI_assert(this->is_mutable());
288  for (const InstanceReference &const_reference : references_) {
289  /* Const cast is fine because we are not changing anything that would change the hash of the
290  * reference. */
291  InstanceReference &reference = const_cast<InstanceReference &>(const_reference);
292  reference.ensure_owns_direct_data();
293  }
294 }
295 
297 {
298  using namespace blender;
299  Array<int> unique_ids(original_ids.size());
300 
301  Set<int> used_unique_ids;
302  used_unique_ids.reserve(original_ids.size());
303  Vector<int> instances_with_id_collision;
304  for (const int instance_index : original_ids.index_range()) {
305  const int original_id = original_ids[instance_index];
306  if (used_unique_ids.add(original_id)) {
307  /* The original id has not been used by another instance yet. */
308  unique_ids[instance_index] = original_id;
309  }
310  else {
311  /* The original id of this instance collided with a previous instance, it needs to be looked
312  * at again in a second pass. Don't generate a new random id here, because this might collide
313  * with other existing ids. */
314  instances_with_id_collision.append(instance_index);
315  }
316  }
317 
318  Map<int, RandomNumberGenerator> generator_by_original_id;
319  for (const int instance_index : instances_with_id_collision) {
320  const int original_id = original_ids[instance_index];
321  RandomNumberGenerator &rng = generator_by_original_id.lookup_or_add_cb(original_id, [&]() {
323  rng.seed_random(original_id);
324  return rng;
325  });
326 
327  const int max_iteration = 100;
328  for (int iteration = 0;; iteration++) {
329  /* Try generating random numbers until an unused one has been found. */
330  const int random_id = rng.get_int32();
331  if (used_unique_ids.add(random_id)) {
332  /* This random id is not used by another instance. */
333  unique_ids[instance_index] = random_id;
334  break;
335  }
336  if (iteration == max_iteration) {
337  /* It seems to be very unlikely that we ever run into this case (assuming there are less
338  * than 2^30 instances). However, if that happens, it's better to use an id that is not
339  * unique than to be stuck in an infinite loop. */
340  unique_ids[instance_index] = original_id;
341  break;
342  }
343  }
344  }
345 
346  return unique_ids;
347 }
348 
350 {
351  std::lock_guard lock(almost_unique_ids_mutex_);
352  std::optional<GSpan> instance_ids_gspan = attributes_.get_for_read("id");
353  if (instance_ids_gspan) {
354  Span<int> instance_ids = instance_ids_gspan->typed<int>();
355  if (almost_unique_ids_.size() != instance_ids.size()) {
356  almost_unique_ids_ = generate_unique_instance_ids(instance_ids);
357  }
358  }
359  else {
360  almost_unique_ids_.reinitialize(this->instances_num());
361  for (const int i : almost_unique_ids_.index_range()) {
362  almost_unique_ids_[i] = i;
363  }
364  }
365  return almost_unique_ids_;
366 }
367 
369 {
370  return this->attributes_;
371 }
372 
374 {
375  return this->attributes_;
376 }
377 
378 namespace blender::bke {
379 
381 {
382  return transform.translation();
383 }
384 
385 static void set_transform_position(float4x4 &transform, const float3 position)
386 {
387  copy_v3_v3(transform.values[3], position);
388 }
389 
391  public:
394  "position", ATTR_DOMAIN_INSTANCE, CD_PROP_FLOAT3, NonCreatable, Writable, NonDeletable)
395  {
396  }
397 
398  GVArray try_get_for_read(const void *owner) const final
399  {
400  const InstancesComponent &instances_component = *static_cast<const InstancesComponent *>(
401  owner);
402  Span<float4x4> transforms = instances_component.instance_transforms();
404  }
405 
406  GAttributeWriter try_get_for_write(void *owner) const final
407  {
408  InstancesComponent &instances_component = *static_cast<InstancesComponent *>(owner);
409  MutableSpan<float4x4> transforms = instances_component.instance_transforms();
412  set_transform_position>(transforms),
413  domain_};
414  }
415 
416  bool try_delete(void *UNUSED(owner)) const final
417  {
418  return false;
419  }
420 
421  bool try_create(void *UNUSED(owner), const AttributeInit &UNUSED(initializer)) const final
422  {
423  return false;
424  }
425 
426  bool exists(const void *UNUSED(owner)) const final
427  {
428  return true;
429  }
430 };
431 
433 {
434  static InstancePositionAttributeProvider position;
435  static CustomDataAccessInfo instance_custom_data_access = {
436  [](void *owner) -> CustomData * {
437  InstancesComponent &inst = *static_cast<InstancesComponent *>(owner);
438  return &inst.instance_attributes().data;
439  },
440  [](const void *owner) -> const CustomData * {
441  const InstancesComponent &inst = *static_cast<const InstancesComponent *>(owner);
442  return &inst.instance_attributes().data;
443  },
444  [](const void *owner) -> int {
445  const InstancesComponent &inst = *static_cast<const InstancesComponent *>(owner);
446  return inst.instances_num();
447  },
448  nullptr};
449 
460  BuiltinAttributeProvider::Creatable,
461  BuiltinAttributeProvider::Writable,
462  BuiltinAttributeProvider::Deletable,
463  instance_custom_data_access,
464  make_array_read_attribute<int>,
465  make_array_write_attribute<int>,
466  nullptr);
467 
468  static CustomDataAttributeProvider instance_custom_data(ATTR_DOMAIN_INSTANCE,
469  instance_custom_data_access);
470 
471  return ComponentAttributeProviders({&position, &id}, {&instance_custom_data});
472 }
473 
475 {
478  attribute_accessor_functions::accessor_functions_for_providers<providers>();
479  fn.domain_size = [](const void *owner, const eAttrDomain domain) {
480  if (owner == nullptr) {
481  return 0;
482  }
483  const InstancesComponent &instances = *static_cast<const InstancesComponent *>(owner);
484  switch (domain) {
486  return instances.instances_num();
487  default:
488  return 0;
489  }
490  };
491  fn.domain_supported = [](const void *UNUSED(owner), const eAttrDomain domain) {
492  return domain == ATTR_DOMAIN_INSTANCE;
493  };
494  fn.adapt_domain = [](const void *UNUSED(owner),
495  const blender::GVArray &varray,
496  const eAttrDomain from_domain,
497  const eAttrDomain to_domain) {
498  if (from_domain == to_domain && from_domain == ATTR_DOMAIN_INSTANCE) {
499  return varray;
500  }
501  return blender::GVArray{};
502  };
503  return fn;
504 }
505 
507 {
509  return fn;
510 }
511 
512 } // namespace blender::bke
513 
514 std::optional<blender::bke::AttributeAccessor> InstancesComponent::attributes() const
515 {
518 }
519 
520 std::optional<blender::bke::MutableAttributeAccessor> InstancesComponent::attributes_for_write()
521 {
524 }
525 
eAttrDomain
Definition: BKE_attribute.h:25
@ ATTR_DOMAIN_INSTANCE
Definition: BKE_attribute.h:32
@ GEO_COMPONENT_TYPE_INSTANCES
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define final(a, b, c)
Definition: BLI_hash.h:21
MINLINE void copy_v3_v3(float r[3], const float a[3])
#define UNUSED(x)
ThreadMutex mutex
Object groups, one object can be in many groups at once.
@ CD_PROP_FLOAT3
@ CD_PROP_INT32
float float4x4[4][4]
in reality light always falls off quadratically Particle Retrieve the data of the particle that spawned the object for example to give variation to multiple instances of an object Point Retrieve information about points in a point cloud Retrieve the edges of an object as it appears to Cycles topology will always appear triangulated Convert a blackbody temperature to an RGB value Normal Map
volatile int lock
SIMD_FORCE_INLINE btVector3 transform(const btVector3 &point) const
GeometryComponentType type() const
bool is_mutable() const
Definition: geometry_set.cc:97
blender::Span< int > instance_reference_handles() const
blender::bke::CustomDataAttributes & instance_attributes()
std::optional< blender::bke::AttributeAccessor > attributes() const final
std::optional< blender::bke::MutableAttributeAccessor > attributes_for_write() final
blender::Span< int > almost_unique_ids() const
int add_reference(const InstanceReference &reference)
GeometrySet & geometry_set_from_reference(int reference_index)
blender::Span< InstanceReference > references() const
GeometryComponent * copy() const override
bool owns_direct_data() const override
void add_instance(int instance_handle, const blender::float4x4 &transform)
blender::MutableSpan< blender::float4x4 > instance_transforms()
void remove_instances(const blender::IndexMask mask)
void reserve(int min_capacity)
Span< T > as_span() const
Definition: BLI_array.hh:231
int64_t size() const
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Definition: BLI_map.hh:561
constexpr T * data() const
Definition: BLI_span.hh:548
void seed_random(uint32_t seed)
Definition: rand.cc:368
void reserve(const int64_t n)
Definition: BLI_set.hh:589
bool add(const Key &key)
Definition: BLI_set.hh:253
constexpr int64_t size() const
Definition: BLI_span.hh:240
constexpr IndexRange index_range() const
Definition: BLI_span.hh:401
int64_t index_of_or_add_as(ForwardKey &&key)
void add_new(const Key &key)
int64_t size() const
void append(const T &value)
Definition: BLI_vector.hh:433
void resize(const int64_t new_size)
Definition: BLI_vector.hh:353
void reserve(const int64_t min_capacity)
Definition: BLI_vector.hh:340
std::optional< blender::GSpan > get_for_read(const AttributeIDRef &attribute_id) const
bool create(const AttributeIDRef &attribute_id, eCustomDataType data_type)
std::optional< blender::GMutableSpan > get_for_write(const AttributeIDRef &attribute_id)
bool foreach_attribute(const AttributeForeachCallback callback, eAttrDomain domain) const
GVArray try_get_for_read(const void *owner) const final
bool exists(const void *UNUSED(owner)) const final
GAttributeWriter try_get_for_write(void *owner) const final
bool try_create(void *UNUSED(owner), const AttributeInit &UNUSED(initializer)) const final
SyclQueue void void * src
BLI_CPP_TYPE_MAKE(GeometrySet, GeometrySet, CPPTypeFlags::Printable)
static void copy_data_based_on_mask(Span< T > src, MutableSpan< T > dst, IndexMask mask)
static blender::Array< int > generate_unique_instance_ids(Span< int > original_ids)
ccl_device_inline float4 mask(const int4 &mask, const float4 &a)
Definition: math_float4.h:513
void convert_to_static_type(const CPPType &cpp_type, const Func &func)
static float3 get_transform_position(const float4x4 &transform)
static ComponentAttributeProviders create_attribute_providers_for_instances()
static const AttributeAccessorFunctions & get_instances_accessor_functions_ref()
static AttributeAccessorFunctions get_instances_accessor_functions()
static void set_transform_position(float4x4 &transform, const float3 position)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
bool(* domain_supported)(const void *owner, eAttrDomain domain)
GVArray(* adapt_domain)(const void *owner, const GVArray &varray, eAttrDomain from_domain, eAttrDomain to_domain)
int(* domain_size)(const void *owner, eAttrDomain domain)