diff options
Diffstat (limited to 'source/blender/blenkernel/intern')
| -rw-r--r-- | source/blender/blenkernel/intern/geometry_component_instances.cc | 385 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/geometry_fields.cc | 16 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/geometry_set.cc | 58 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/geometry_set_instances.cc | 45 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/instances.cc | 348 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/object_dupli.cc | 17 |
6 files changed, 503 insertions, 366 deletions
diff --git a/source/blender/blenkernel/intern/geometry_component_instances.cc b/source/blender/blenkernel/intern/geometry_component_instances.cc index 0b5f7cbf902..be1d9524509 100644 --- a/source/blender/blenkernel/intern/geometry_component_instances.cc +++ b/source/blender/blenkernel/intern/geometry_component_instances.cc @@ -16,6 +16,7 @@ #include "BKE_attribute_math.hh" #include "BKE_geometry_set.hh" #include "BKE_geometry_set_instances.hh" +#include "BKE_instances.hh" #include "attribute_access_intern.hh" @@ -29,8 +30,8 @@ using blender::MutableSpan; using blender::Set; using blender::Span; using blender::VectorSet; - -BLI_CPP_TYPE_MAKE(InstanceReference, InstanceReference, CPPTypeFlags::None) +using blender::bke::InstanceReference; +using blender::bke::Instances; /* -------------------------------------------------------------------- */ /** \name Geometry Component Implementation @@ -40,339 +41,76 @@ InstancesComponent::InstancesComponent() : GeometryComponent(GEO_COMPONENT_TYPE_ { } -GeometryComponent *InstancesComponent::copy() const -{ - InstancesComponent *new_component = new InstancesComponent(); - new_component->instance_reference_handles_ = instance_reference_handles_; - new_component->instance_transforms_ = instance_transforms_; - new_component->references_ = references_; - new_component->attributes_ = attributes_; - return new_component; -} - -void InstancesComponent::reserve(int min_capacity) +InstancesComponent::~InstancesComponent() { - instance_reference_handles_.reserve(min_capacity); - instance_transforms_.reserve(min_capacity); - attributes_.reallocate(min_capacity); + this->clear(); } -void InstancesComponent::resize(int capacity) +GeometryComponent *InstancesComponent::copy() const { - instance_reference_handles_.resize(capacity); - instance_transforms_.resize(capacity); - attributes_.reallocate(capacity); + InstancesComponent *new_component = new InstancesComponent(); + if (instances_ != nullptr) { + new_component->instances_ = new Instances(*instances_); + new_component->ownership_ = GeometryOwnershipType::Owned; + } + return new_component; } void InstancesComponent::clear() { - instance_reference_handles_.clear(); - instance_transforms_.clear(); - attributes_.clear(); - references_.clear(); -} - -void InstancesComponent::add_instance(const int instance_handle, const float4x4 &transform) -{ - BLI_assert(instance_handle >= 0); - BLI_assert(instance_handle < references_.size()); - instance_reference_handles_.append(instance_handle); - instance_transforms_.append(transform); - attributes_.reallocate(this->instances_num()); -} - -blender::Span<int> InstancesComponent::instance_reference_handles() const -{ - return instance_reference_handles_; -} - -blender::MutableSpan<int> InstancesComponent::instance_reference_handles() -{ - return instance_reference_handles_; -} - -blender::MutableSpan<blender::float4x4> InstancesComponent::instance_transforms() -{ - return instance_transforms_; -} -blender::Span<blender::float4x4> InstancesComponent::instance_transforms() const -{ - return instance_transforms_; -} - -GeometrySet &InstancesComponent::geometry_set_from_reference(const int reference_index) -{ - /* If this assert fails, it means #ensure_geometry_instances must be called first or that the - * reference can't be converted to a geometry set. */ - BLI_assert(references_[reference_index].type() == InstanceReference::Type::GeometrySet); - - /* The const cast is okay because the instance's hash in the set - * is not changed by adjusting the data inside the geometry set. */ - return const_cast<GeometrySet &>(references_[reference_index].geometry_set()); -} - -int InstancesComponent::add_reference(const InstanceReference &reference) -{ - return references_.index_of_or_add_as(reference); -} - -blender::Span<InstanceReference> InstancesComponent::references() const -{ - return references_; -} - -template<typename T> -static void copy_data_based_on_mask(Span<T> src, MutableSpan<T> dst, IndexMask mask) -{ - BLI_assert(src.data() != dst.data()); - using namespace blender; - threading::parallel_for(mask.index_range(), 1024, [&](IndexRange range) { - for (const int i : range) { - dst[i] = src[mask[i]]; - } - }); -} - -void InstancesComponent::remove_instances(const IndexMask mask) -{ - using namespace blender; - if (mask.is_range() && mask.as_range().start() == 0) { - /* Deleting from the end of the array can be much faster since no data has to be shifted. */ - this->resize(mask.size()); - this->remove_unused_references(); - return; + BLI_assert(this->is_mutable()); + if (ownership_ == GeometryOwnershipType::Owned) { + delete instances_; } - - Vector<int> new_handles(mask.size()); - copy_data_based_on_mask<int>(this->instance_reference_handles(), new_handles, mask); - instance_reference_handles_ = std::move(new_handles); - Vector<float4x4> new_transforms(mask.size()); - copy_data_based_on_mask<float4x4>(this->instance_transforms(), new_transforms, mask); - instance_transforms_ = std::move(new_transforms); - - const bke::CustomDataAttributes &src_attributes = attributes_; - - bke::CustomDataAttributes dst_attributes; - dst_attributes.reallocate(mask.size()); - - src_attributes.foreach_attribute( - [&](const bke::AttributeIDRef &id, const bke::AttributeMetaData &meta_data) { - if (!id.should_be_kept()) { - return true; - } - - GSpan src = *src_attributes.get_for_read(id); - dst_attributes.create(id, meta_data.data_type); - GMutableSpan dst = *dst_attributes.get_for_write(id); - - attribute_math::convert_to_static_type(src.type(), [&](auto dummy) { - using T = decltype(dummy); - copy_data_based_on_mask<T>(src.typed<T>(), dst.typed<T>(), mask); - }); - return true; - }, - ATTR_DOMAIN_INSTANCE); - - attributes_ = std::move(dst_attributes); - this->remove_unused_references(); + instances_ = nullptr; } -void InstancesComponent::remove_unused_references() +bool InstancesComponent::is_empty() const { - using namespace blender; - using namespace blender::bke; - - const int tot_instances = this->instances_num(); - const int tot_references_before = references_.size(); - - if (tot_instances == 0) { - /* If there are no instances, no reference is needed. */ - references_.clear(); - return; - } - if (tot_references_before == 1) { - /* There is only one reference and at least one instance. So the only existing reference is - * used. Nothing to do here. */ - return; - } - - Array<bool> usage_by_handle(tot_references_before, false); - std::mutex mutex; - - /* Loop over all instances to see which references are used. */ - threading::parallel_for(IndexRange(tot_instances), 1000, [&](IndexRange range) { - /* Use local counter to avoid lock contention. */ - Array<bool> local_usage_by_handle(tot_references_before, false); - - for (const int i : range) { - const int handle = instance_reference_handles_[i]; - BLI_assert(handle >= 0 && handle < tot_references_before); - local_usage_by_handle[handle] = true; - } - - std::lock_guard lock{mutex}; - for (const int i : IndexRange(tot_references_before)) { - usage_by_handle[i] |= local_usage_by_handle[i]; - } - }); - - if (!usage_by_handle.as_span().contains(false)) { - /* All references are used. */ - return; - } - - /* Create new references and a mapping for the handles. */ - Vector<int> handle_mapping; - VectorSet<InstanceReference> new_references; - int next_new_handle = 0; - bool handles_have_to_be_updated = false; - for (const int old_handle : IndexRange(tot_references_before)) { - if (!usage_by_handle[old_handle]) { - /* Add some dummy value. It won't be read again. */ - handle_mapping.append(-1); - } - else { - const InstanceReference &reference = references_[old_handle]; - handle_mapping.append(next_new_handle); - new_references.add_new(reference); - if (old_handle != next_new_handle) { - handles_have_to_be_updated = true; - } - next_new_handle++; + if (instances_ != nullptr) { + if (instances_->instances_num() > 0) { + return false; } } - references_ = new_references; - - if (!handles_have_to_be_updated) { - /* All remaining handles are the same as before, so they don't have to be updated. This happens - * when unused handles are only at the end. */ - return; - } - - /* Update handles of instances. */ - threading::parallel_for(IndexRange(tot_instances), 1000, [&](IndexRange range) { - for (const int i : range) { - instance_reference_handles_[i] = handle_mapping[instance_reference_handles_[i]]; - } - }); -} - -int InstancesComponent::instances_num() const -{ - return instance_transforms_.size(); -} - -int InstancesComponent::references_num() const -{ - return references_.size(); -} - -bool InstancesComponent::is_empty() const -{ - return this->instance_reference_handles_.size() == 0; + return true; } bool InstancesComponent::owns_direct_data() const { - for (const InstanceReference &reference : references_) { - if (!reference.owns_direct_data()) { - return false; - } + if (instances_ != nullptr) { + return instances_->owns_direct_data(); } return true; } void InstancesComponent::ensure_owns_direct_data() { - BLI_assert(this->is_mutable()); - for (const InstanceReference &const_reference : references_) { - /* Const cast is fine because we are not changing anything that would change the hash of the - * reference. */ - InstanceReference &reference = const_cast<InstanceReference &>(const_reference); - reference.ensure_owns_direct_data(); + if (instances_ != nullptr) { + instances_->ensure_owns_direct_data(); } } -static blender::Array<int> generate_unique_instance_ids(Span<int> original_ids) +const blender::bke::Instances *InstancesComponent::get_for_read() const { - 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; + return instances_; } -blender::Span<int> InstancesComponent::almost_unique_ids() const +blender::bke::Instances *InstancesComponent::get_for_write() { - std::lock_guard lock(almost_unique_ids_mutex_); - std::optional<GSpan> instance_ids_gspan = attributes_.get_for_read("id"); - if (instance_ids_gspan) { - Span<int> instance_ids = instance_ids_gspan->typed<int>(); - if (almost_unique_ids_.size() != instance_ids.size()) { - almost_unique_ids_ = generate_unique_instance_ids(instance_ids); - } - } - else { - almost_unique_ids_.reinitialize(this->instances_num()); - for (const int i : almost_unique_ids_.index_range()) { - almost_unique_ids_[i] = i; - } + BLI_assert(this->is_mutable()); + if (ownership_ == GeometryOwnershipType::ReadOnly) { + instances_ = new Instances(*instances_); + ownership_ = GeometryOwnershipType::Owned; } - return almost_unique_ids_; + return instances_; } -blender::bke::CustomDataAttributes &InstancesComponent::instance_attributes() +void InstancesComponent::replace(Instances *instances, GeometryOwnershipType ownership) { - return this->attributes_; -} - -const blender::bke::CustomDataAttributes &InstancesComponent::instance_attributes() const -{ - return this->attributes_; + BLI_assert(this->is_mutable()); + this->clear(); + instances_ = instances; + ownership_ = ownership; } namespace blender::bke { @@ -397,16 +135,21 @@ class InstancePositionAttributeProvider final : public BuiltinAttributeProvider GVArray try_get_for_read(const void *owner) const final { - const InstancesComponent &instances_component = *static_cast<const InstancesComponent *>( - owner); - Span<float4x4> transforms = instances_component.instance_transforms(); + const Instances *instances = static_cast<const Instances *>(owner); + if (instances == nullptr) { + return {}; + } + Span<float4x4> transforms = instances->transforms(); return VArray<float3>::ForDerivedSpan<float4x4, get_transform_position>(transforms); } GAttributeWriter try_get_for_write(void *owner) const final { - InstancesComponent &instances_component = *static_cast<InstancesComponent *>(owner); - MutableSpan<float4x4> transforms = instances_component.instance_transforms(); + Instances *instances = static_cast<Instances *>(owner); + if (instances == nullptr) { + return {}; + } + MutableSpan<float4x4> transforms = instances->transforms(); return {VMutableArray<float3>::ForDerivedSpan<float4x4, get_transform_position, set_transform_position>(transforms), @@ -434,16 +177,16 @@ static ComponentAttributeProviders create_attribute_providers_for_instances() static InstancePositionAttributeProvider position; static CustomDataAccessInfo instance_custom_data_access = { [](void *owner) -> CustomData * { - InstancesComponent &inst = *static_cast<InstancesComponent *>(owner); - return &inst.instance_attributes().data; + Instances *instances = static_cast<Instances *>(owner); + return &instances->custom_data_attributes().data; }, [](const void *owner) -> const CustomData * { - const InstancesComponent &inst = *static_cast<const InstancesComponent *>(owner); - return &inst.instance_attributes().data; + const Instances *instances = static_cast<const Instances *>(owner); + return &instances->custom_data_attributes().data; }, [](const void *owner) -> int { - const InstancesComponent &inst = *static_cast<const InstancesComponent *>(owner); - return inst.instances_num(); + const Instances *instances = static_cast<const Instances *>(owner); + return instances->instances_num(); }}; /** @@ -479,10 +222,10 @@ static AttributeAccessorFunctions get_instances_accessor_functions() if (owner == nullptr) { return 0; } - const InstancesComponent &instances = *static_cast<const InstancesComponent *>(owner); + const Instances *instances = static_cast<const Instances *>(owner); switch (domain) { case ATTR_DOMAIN_INSTANCE: - return instances.instances_num(); + return instances->instances_num(); default: return 0; } @@ -508,18 +251,30 @@ static const AttributeAccessorFunctions &get_instances_accessor_functions_ref() return fn; } +blender::bke::AttributeAccessor Instances::attributes() const +{ + return blender::bke::AttributeAccessor(this, + blender::bke::get_instances_accessor_functions_ref()); +} + +blender::bke::MutableAttributeAccessor Instances::attributes_for_write() +{ + return blender::bke::MutableAttributeAccessor( + this, blender::bke::get_instances_accessor_functions_ref()); +} + } // namespace blender::bke std::optional<blender::bke::AttributeAccessor> InstancesComponent::attributes() const { - return blender::bke::AttributeAccessor(this, + return blender::bke::AttributeAccessor(instances_, blender::bke::get_instances_accessor_functions_ref()); } std::optional<blender::bke::MutableAttributeAccessor> InstancesComponent::attributes_for_write() { return blender::bke::MutableAttributeAccessor( - this, blender::bke::get_instances_accessor_functions_ref()); + instances_, blender::bke::get_instances_accessor_functions_ref()); } /** \} */ diff --git a/source/blender/blenkernel/intern/geometry_fields.cc b/source/blender/blenkernel/intern/geometry_fields.cc index b492af4af77..82ffda57398 100644 --- a/source/blender/blenkernel/intern/geometry_fields.cc +++ b/source/blender/blenkernel/intern/geometry_fields.cc @@ -4,6 +4,7 @@ #include "BKE_curves.hh" #include "BKE_geometry_fields.hh" #include "BKE_geometry_set.hh" +#include "BKE_instances.hh" #include "BKE_mesh.h" #include "BKE_pointcloud.h" #include "BKE_type_conversions.hh" @@ -64,7 +65,7 @@ GeometryFieldContext::GeometryFieldContext(const GeometryComponent &component, case GEO_COMPONENT_TYPE_INSTANCES: { const InstancesComponent &instances_component = static_cast<const InstancesComponent &>( component); - geometry_ = &instances_component; + geometry_ = instances_component.get_for_read(); break; } case GEO_COMPONENT_TYPE_VOLUME: @@ -86,7 +87,7 @@ GeometryFieldContext::GeometryFieldContext(const PointCloud &points) : geometry_(&points), type_(GEO_COMPONENT_TYPE_POINT_CLOUD), domain_(ATTR_DOMAIN_POINT) { } -GeometryFieldContext::GeometryFieldContext(const InstancesComponent &instances) +GeometryFieldContext::GeometryFieldContext(const Instances &instances) : geometry_(&instances), type_(GEO_COMPONENT_TYPE_INSTANCES), domain_(ATTR_DOMAIN_INSTANCE) { } @@ -102,7 +103,7 @@ std::optional<AttributeAccessor> GeometryFieldContext::attributes() const if (const PointCloud *pointcloud = this->pointcloud()) { return pointcloud->attributes(); } - if (const InstancesComponent *instances = this->instances()) { + if (const Instances *instances = this->instances()) { return instances->attributes(); } return {}; @@ -124,11 +125,10 @@ const PointCloud *GeometryFieldContext::pointcloud() const static_cast<const PointCloud *>(geometry_) : nullptr; } -const InstancesComponent *GeometryFieldContext::instances() const +const Instances *GeometryFieldContext::instances() const { - return this->type() == GEO_COMPONENT_TYPE_INSTANCES ? - static_cast<const InstancesComponent *>(geometry_) : - nullptr; + return this->type() == GEO_COMPONENT_TYPE_INSTANCES ? static_cast<const Instances *>(geometry_) : + nullptr; } GVArray GeometryFieldInput::get_varray_for_context(const fn::FieldContext &context, @@ -230,7 +230,7 @@ GVArray InstancesFieldInput::get_varray_for_context(const fn::FieldContext &cont { if (const GeometryFieldContext *geometry_context = dynamic_cast<const GeometryFieldContext *>( &context)) { - if (const InstancesComponent *instances = geometry_context->instances()) { + if (const Instances *instances = geometry_context->instances()) { return this->get_varray_for_context(*instances, mask); } } diff --git a/source/blender/blenkernel/intern/geometry_set.cc b/source/blender/blenkernel/intern/geometry_set.cc index 46ff8141504..90568a8a080 100644 --- a/source/blender/blenkernel/intern/geometry_set.cc +++ b/source/blender/blenkernel/intern/geometry_set.cc @@ -9,6 +9,7 @@ #include "BKE_attribute.h" #include "BKE_curves.hh" #include "BKE_geometry_set.hh" +#include "BKE_instances.hh" #include "BKE_lib_id.h" #include "BKE_mesh.h" #include "BKE_mesh_wrapper.h" @@ -31,6 +32,8 @@ using blender::MutableSpan; using blender::Span; using blender::StringRef; using blender::Vector; +using blender::bke::InstanceReference; +using blender::bke::Instances; /* -------------------------------------------------------------------- */ /** \name Geometry Component @@ -256,8 +259,7 @@ std::ostream &operator<<(std::ostream &stream, const GeometrySet &geometry_set) parts.append(std::to_string(BKE_volume_num_grids(volume)) + " volume grids"); } if (geometry_set.has_instances()) { - parts.append(std::to_string( - geometry_set.get_component_for_read<InstancesComponent>()->instances_num()) + + parts.append(std::to_string(geometry_set.get_instances_for_read()->instances_num()) + " instances"); } if (geometry_set.get_curve_edit_hints_for_read()) { @@ -338,6 +340,12 @@ const Curves *GeometrySet::get_curves_for_read() const return (component == nullptr) ? nullptr : component->get_for_read(); } +const Instances *GeometrySet::get_instances_for_read() const +{ + const InstancesComponent *component = this->get_component_for_read<InstancesComponent>(); + return (component == nullptr) ? nullptr : component->get_for_read(); +} + const blender::bke::CurvesEditHints *GeometrySet::get_curve_edit_hints_for_read() const { const GeometryComponentEditData *component = @@ -354,7 +362,8 @@ bool GeometrySet::has_pointcloud() const bool GeometrySet::has_instances() const { const InstancesComponent *component = this->get_component_for_read<InstancesComponent>(); - return component != nullptr && component->instances_num() >= 1; + return component != nullptr && component->get_for_read() != nullptr && + component->get_for_read()->instances_num() >= 1; } bool GeometrySet::has_volume() const @@ -428,6 +437,14 @@ GeometrySet GeometrySet::create_with_curves(Curves *curves, GeometryOwnershipTyp return geometry_set; } +GeometrySet GeometrySet::create_with_instances(Instances *instances, + GeometryOwnershipType ownership) +{ + GeometrySet geometry_set; + geometry_set.replace_instances(instances, ownership); + return geometry_set; +} + void GeometrySet::replace_mesh(Mesh *mesh, GeometryOwnershipType ownership) { if (mesh == nullptr) { @@ -456,6 +473,20 @@ void GeometrySet::replace_curves(Curves *curves, GeometryOwnershipType ownership component.replace(curves, ownership); } +void GeometrySet::replace_instances(Instances *instances, GeometryOwnershipType ownership) +{ + if (instances == nullptr) { + this->remove<InstancesComponent>(); + return; + } + if (instances == this->get_instances_for_read()) { + return; + } + this->remove<InstancesComponent>(); + InstancesComponent &component = this->get_component_for_write<InstancesComponent>(); + component.replace(instances, ownership); +} + void GeometrySet::replace_pointcloud(PointCloud *pointcloud, GeometryOwnershipType ownership) { if (pointcloud == nullptr) { @@ -508,6 +539,12 @@ Curves *GeometrySet::get_curves_for_write() return component == nullptr ? nullptr : component->get_for_write(); } +Instances *GeometrySet::get_instances_for_write() +{ + InstancesComponent *component = this->get_component_ptr<InstancesComponent>(); + return component == nullptr ? nullptr : component->get_for_write(); +} + blender::bke::CurvesEditHints *GeometrySet::get_curve_edit_hints_for_write() { if (!this->has<GeometryComponentEditData>()) { @@ -539,7 +576,7 @@ void GeometrySet::attribute_foreach(const Span<GeometryComponentType> component_ } } if (include_instances && this->has_instances()) { - const InstancesComponent &instances = *this->get_component_for_read<InstancesComponent>(); + const Instances &instances = *this->get_instances_for_read(); instances.foreach_referenced_geometry([&](const GeometrySet &instance_geometry_set) { instance_geometry_set.attribute_foreach(component_types, include_instances, callback); }); @@ -611,7 +648,7 @@ static void gather_component_types_recursive(const GeometrySet &geometry_set, if (!include_instances) { return; } - const InstancesComponent *instances = geometry_set.get_component_for_read<InstancesComponent>(); + const blender::bke::Instances *instances = geometry_set.get_instances_for_read(); if (instances == nullptr) { return; } @@ -638,12 +675,11 @@ static void gather_mutable_geometry_sets(GeometrySet &geometry_set, } /* In the future this can be improved by deduplicating instance references across different * instances. */ - InstancesComponent &instances_component = - geometry_set.get_component_for_write<InstancesComponent>(); - instances_component.ensure_geometry_instances(); - for (const int handle : instances_component.references().index_range()) { - if (instances_component.references()[handle].type() == InstanceReference::Type::GeometrySet) { - GeometrySet &instance_geometry = instances_component.geometry_set_from_reference(handle); + Instances &instances = *geometry_set.get_instances_for_write(); + instances.ensure_geometry_instances(); + for (const int handle : instances.references().index_range()) { + if (instances.references()[handle].type() == InstanceReference::Type::GeometrySet) { + GeometrySet &instance_geometry = instances.geometry_set_from_reference(handle); gather_mutable_geometry_sets(instance_geometry, r_geometry_sets); } } diff --git a/source/blender/blenkernel/intern/geometry_set_instances.cc b/source/blender/blenkernel/intern/geometry_set_instances.cc index 0ae49a586f1..e078991187d 100644 --- a/source/blender/blenkernel/intern/geometry_set_instances.cc +++ b/source/blender/blenkernel/intern/geometry_set_instances.cc @@ -2,6 +2,7 @@ #include "BKE_collection.h" #include "BKE_geometry_set_instances.hh" +#include "BKE_instances.hh" #include "BKE_material.h" #include "BKE_mesh.h" #include "BKE_mesh_wrapper.h" @@ -62,12 +63,11 @@ GeometrySet object_get_evaluated_geometry_set(const Object &object) return geometry_set; } if (object.type == OB_EMPTY && object.instance_collection != nullptr) { - GeometrySet geometry_set; Collection &collection = *object.instance_collection; - InstancesComponent &instances = geometry_set.get_component_for_write<InstancesComponent>(); - const int handle = instances.add_reference(collection); - instances.add_instance(handle, float4x4::identity()); - return geometry_set; + std::unique_ptr<Instances> instances = std::make_unique<Instances>(); + const int handle = instances->add_reference(collection); + instances->add_instance(handle, float4x4::identity()); + return GeometrySet::create_with_instances(instances.release()); } /* Return by value since there is not always an existing geometry set owned elsewhere to use. */ @@ -115,12 +115,11 @@ static void geometry_set_collect_recursive(const GeometrySet &geometry_set, r_sets.append({geometry_set, {transform}}); if (geometry_set.has_instances()) { - const InstancesComponent &instances_component = - *geometry_set.get_component_for_read<InstancesComponent>(); + const Instances &instances = *geometry_set.get_instances_for_read(); - Span<float4x4> transforms = instances_component.instance_transforms(); - Span<int> handles = instances_component.instance_reference_handles(); - Span<InstanceReference> references = instances_component.references(); + Span<float4x4> transforms = instances.transforms(); + Span<int> handles = instances.reference_handles(); + Span<InstanceReference> references = instances.references(); for (const int i : transforms.index_range()) { const InstanceReference &reference = references[handles[i]]; const float4x4 instance_transform = transform * transforms[i]; @@ -156,9 +155,7 @@ void geometry_set_gather_instances(const GeometrySet &geometry_set, geometry_set_collect_recursive(geometry_set, float4x4::identity(), r_instance_groups); } -} // namespace blender::bke - -void InstancesComponent::foreach_referenced_geometry( +void Instances::foreach_referenced_geometry( blender::FunctionRef<void(const GeometrySet &geometry_set)> callback) const { using namespace blender::bke; @@ -191,7 +188,7 @@ void InstancesComponent::foreach_referenced_geometry( } } -void InstancesComponent::ensure_geometry_instances() +void Instances::ensure_geometry_instances() { using namespace blender; using namespace blender::bke; @@ -211,9 +208,7 @@ void InstancesComponent::ensure_geometry_instances() const Object &object = reference.object(); GeometrySet object_geometry_set = object_get_evaluated_geometry_set(object); if (object_geometry_set.has_instances()) { - InstancesComponent &component = - object_geometry_set.get_component_for_write<InstancesComponent>(); - component.ensure_geometry_instances(); + object_geometry_set.get_instances_for_write()->ensure_geometry_instances(); } new_references.add_new(std::move(object_geometry_set)); break; @@ -221,22 +216,22 @@ void InstancesComponent::ensure_geometry_instances() case InstanceReference::Type::Collection: { /* Create a new reference that contains a geometry set that contains all objects from the * collection as instances. */ - GeometrySet collection_geometry_set; - InstancesComponent &component = - collection_geometry_set.get_component_for_write<InstancesComponent>(); + std::unique_ptr<Instances> instances = std::make_unique<Instances>(); Collection &collection = reference.collection(); FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN (&collection, object) { - const int handle = component.add_reference(*object); - component.add_instance(handle, object->obmat); - float4x4 &transform = component.instance_transforms().last(); + const int handle = instances->add_reference(*object); + instances->add_instance(handle, object->obmat); + float4x4 &transform = instances->transforms().last(); sub_v3_v3(transform.values[3], collection.instance_offset); } FOREACH_COLLECTION_OBJECT_RECURSIVE_END; - component.ensure_geometry_instances(); - new_references.add_new(std::move(collection_geometry_set)); + instances->ensure_geometry_instances(); + new_references.add_new(GeometrySet::create_with_instances(instances.release())); break; } } } references_ = std::move(new_references); } + +} // namespace blender::bke diff --git a/source/blender/blenkernel/intern/instances.cc b/source/blender/blenkernel/intern/instances.cc new file mode 100644 index 00000000000..dd759453630 --- /dev/null +++ b/source/blender/blenkernel/intern/instances.cc @@ -0,0 +1,348 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#include "BLI_cpp_type_make.hh" +#include "BLI_rand.hh" +#include "BLI_task.hh" + +#include "BKE_attribute_math.hh" +#include "BKE_geometry_set.hh" +#include "BKE_instances.hh" + +BLI_CPP_TYPE_MAKE(InstanceReference, blender::bke::InstanceReference, CPPTypeFlags::None) + +namespace blender::bke { + +InstanceReference::InstanceReference(GeometrySet geometry_set) + : type_(Type::GeometrySet), + geometry_set_(std::make_unique<GeometrySet>(std::move(geometry_set))) +{ +} + +void InstanceReference::ensure_owns_direct_data() +{ + if (type_ != Type::GeometrySet) { + return; + } + geometry_set_->ensure_owns_direct_data(); +} + +bool InstanceReference::owns_direct_data() const +{ + if (type_ != Type::GeometrySet) { + /* The object and collection instances are not direct data. */ + return true; + } + return geometry_set_->owns_direct_data(); +} + +Instances::Instances(const Instances &other) + : references_(other.references_), + reference_handles_(other.reference_handles_), + transforms_(other.transforms_), + almost_unique_ids_(other.almost_unique_ids_), + attributes_(other.attributes_) +{ +} + +void Instances::reserve(int min_capacity) +{ + reference_handles_.reserve(min_capacity); + transforms_.reserve(min_capacity); + attributes_.reallocate(min_capacity); +} + +void Instances::resize(int capacity) +{ + reference_handles_.resize(capacity); + transforms_.resize(capacity); + attributes_.reallocate(capacity); +} + +void Instances::add_instance(const int instance_handle, const float4x4 &transform) +{ + BLI_assert(instance_handle >= 0); + BLI_assert(instance_handle < references_.size()); + reference_handles_.append(instance_handle); + transforms_.append(transform); + attributes_.reallocate(this->instances_num()); +} + +blender::Span<int> Instances::reference_handles() const +{ + return reference_handles_; +} + +blender::MutableSpan<int> Instances::reference_handles() +{ + return reference_handles_; +} + +blender::MutableSpan<blender::float4x4> Instances::transforms() +{ + return transforms_; +} +blender::Span<blender::float4x4> Instances::transforms() const +{ + return transforms_; +} + +GeometrySet &Instances::geometry_set_from_reference(const int reference_index) +{ + /* If this assert fails, it means #ensure_geometry_instances must be called first or that the + * reference can't be converted to a geometry set. */ + BLI_assert(references_[reference_index].type() == InstanceReference::Type::GeometrySet); + + /* The const cast is okay because the instance's hash in the set + * is not changed by adjusting the data inside the geometry set. */ + return const_cast<GeometrySet &>(references_[reference_index].geometry_set()); +} + +int Instances::add_reference(const InstanceReference &reference) +{ + return references_.index_of_or_add_as(reference); +} + +blender::Span<InstanceReference> Instances::references() const +{ + return references_; +} + +template<typename T> +static void copy_data_based_on_mask(Span<T> src, MutableSpan<T> dst, IndexMask mask) +{ + BLI_assert(src.data() != dst.data()); + using namespace blender; + threading::parallel_for(mask.index_range(), 1024, [&](IndexRange range) { + for (const int i : range) { + dst[i] = src[mask[i]]; + } + }); +} + +void Instances::remove(const IndexMask mask) +{ + using namespace blender; + if (mask.is_range() && mask.as_range().start() == 0) { + /* Deleting from the end of the array can be much faster since no data has to be shifted. */ + this->resize(mask.size()); + this->remove_unused_references(); + return; + } + + Vector<int> new_handles(mask.size()); + copy_data_based_on_mask<int>(this->reference_handles(), new_handles, mask); + reference_handles_ = std::move(new_handles); + Vector<float4x4> new_transforms(mask.size()); + copy_data_based_on_mask<float4x4>(this->transforms(), new_transforms, mask); + transforms_ = std::move(new_transforms); + + const bke::CustomDataAttributes &src_attributes = attributes_; + + bke::CustomDataAttributes dst_attributes; + dst_attributes.reallocate(mask.size()); + + src_attributes.foreach_attribute( + [&](const bke::AttributeIDRef &id, const bke::AttributeMetaData &meta_data) { + if (!id.should_be_kept()) { + return true; + } + + GSpan src = *src_attributes.get_for_read(id); + dst_attributes.create(id, meta_data.data_type); + GMutableSpan dst = *dst_attributes.get_for_write(id); + + attribute_math::convert_to_static_type(src.type(), [&](auto dummy) { + using T = decltype(dummy); + copy_data_based_on_mask<T>(src.typed<T>(), dst.typed<T>(), mask); + }); + return true; + }, + ATTR_DOMAIN_INSTANCE); + + attributes_ = std::move(dst_attributes); + this->remove_unused_references(); +} + +void Instances::remove_unused_references() +{ + using namespace blender; + using namespace blender::bke; + + const int tot_instances = this->instances_num(); + const int tot_references_before = references_.size(); + + if (tot_instances == 0) { + /* If there are no instances, no reference is needed. */ + references_.clear(); + return; + } + if (tot_references_before == 1) { + /* There is only one reference and at least one instance. So the only existing reference is + * used. Nothing to do here. */ + return; + } + + Array<bool> usage_by_handle(tot_references_before, false); + std::mutex mutex; + + /* Loop over all instances to see which references are used. */ + threading::parallel_for(IndexRange(tot_instances), 1000, [&](IndexRange range) { + /* Use local counter to avoid lock contention. */ + Array<bool> local_usage_by_handle(tot_references_before, false); + + for (const int i : range) { + const int handle = reference_handles_[i]; + BLI_assert(handle >= 0 && handle < tot_references_before); + local_usage_by_handle[handle] = true; + } + + std::lock_guard lock{mutex}; + for (const int i : IndexRange(tot_references_before)) { + usage_by_handle[i] |= local_usage_by_handle[i]; + } + }); + + if (!usage_by_handle.as_span().contains(false)) { + /* All references are used. */ + return; + } + + /* Create new references and a mapping for the handles. */ + Vector<int> handle_mapping; + VectorSet<InstanceReference> new_references; + int next_new_handle = 0; + bool handles_have_to_be_updated = false; + for (const int old_handle : IndexRange(tot_references_before)) { + if (!usage_by_handle[old_handle]) { + /* Add some dummy value. It won't be read again. */ + handle_mapping.append(-1); + } + else { + const InstanceReference &reference = references_[old_handle]; + handle_mapping.append(next_new_handle); + new_references.add_new(reference); + if (old_handle != next_new_handle) { + handles_have_to_be_updated = true; + } + next_new_handle++; + } + } + references_ = new_references; + + if (!handles_have_to_be_updated) { + /* All remaining handles are the same as before, so they don't have to be updated. This happens + * when unused handles are only at the end. */ + return; + } + + /* Update handles of instances. */ + threading::parallel_for(IndexRange(tot_instances), 1000, [&](IndexRange range) { + for (const int i : range) { + reference_handles_[i] = handle_mapping[reference_handles_[i]]; + } + }); +} + +int Instances::instances_num() const +{ + return transforms_.size(); +} + +int Instances::references_num() const +{ + return references_.size(); +} + +bool Instances::owns_direct_data() const +{ + for (const InstanceReference &reference : references_) { + if (!reference.owns_direct_data()) { + return false; + } + } + return true; +} + +void Instances::ensure_owns_direct_data() +{ + for (const InstanceReference &const_reference : references_) { + /* Const cast is fine because we are not changing anything that would change the hash of the + * reference. */ + InstanceReference &reference = const_cast<InstanceReference &>(const_reference); + reference.ensure_owns_direct_data(); + } +} + +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> Instances::almost_unique_ids() const +{ + std::lock_guard lock(almost_unique_ids_mutex_); + std::optional<GSpan> instance_ids_gspan = attributes_.get_for_read("id"); + if (instance_ids_gspan) { + Span<int> instance_ids = instance_ids_gspan->typed<int>(); + if (almost_unique_ids_.size() != instance_ids.size()) { + almost_unique_ids_ = generate_unique_instance_ids(instance_ids); + } + } + else { + almost_unique_ids_.reinitialize(this->instances_num()); + for (const int i : almost_unique_ids_.index_range()) { + almost_unique_ids_[i] = i; + } + } + return almost_unique_ids_; +} + +} // namespace blender::bke diff --git a/source/blender/blenkernel/intern/object_dupli.cc b/source/blender/blenkernel/intern/object_dupli.cc index 96da99af97e..d43eff6f9b4 100644 --- a/source/blender/blenkernel/intern/object_dupli.cc +++ b/source/blender/blenkernel/intern/object_dupli.cc @@ -41,6 +41,7 @@ #include "BKE_geometry_set.hh" #include "BKE_global.h" #include "BKE_idprop.h" +#include "BKE_instances.hh" #include "BKE_lattice.h" #include "BKE_main.h" #include "BKE_mesh.h" @@ -70,6 +71,8 @@ using blender::float3; using blender::float4x4; using blender::Span; using blender::Vector; +using blender::bke::InstanceReference; +using blender::bke::Instances; namespace geo_log = blender::nodes::geo_eval_log; /* -------------------------------------------------------------------- */ @@ -874,8 +877,8 @@ static void make_duplis_geometry_set_impl(const DupliContext *ctx, } const bool creates_duplis_for_components = component_index >= 1; - const InstancesComponent *component = geometry_set.get_component_for_read<InstancesComponent>(); - if (component == nullptr) { + const Instances *instances = geometry_set.get_instances_for_read(); + if (instances == nullptr) { return; } @@ -890,13 +893,13 @@ static void make_duplis_geometry_set_impl(const DupliContext *ctx, instances_ctx = &new_instances_ctx; } - Span<float4x4> instance_offset_matrices = component->instance_transforms(); - Span<int> instance_reference_handles = component->instance_reference_handles(); - Span<int> almost_unique_ids = component->almost_unique_ids(); - Span<InstanceReference> references = component->references(); + Span<float4x4> instance_offset_matrices = instances->transforms(); + Span<int> reference_handles = instances->reference_handles(); + Span<int> almost_unique_ids = instances->almost_unique_ids(); + Span<InstanceReference> references = instances->references(); for (int64_t i : instance_offset_matrices.index_range()) { - const InstanceReference &reference = references[instance_reference_handles[i]]; + const InstanceReference &reference = references[reference_handles[i]]; const int id = almost_unique_ids[i]; const DupliContext *ctx_for_instance = instances_ctx; |