Geometry Nodes: support instance attributes when realizing instances

This patch refactors the instance-realization code and adds new functionality.
* Named and anonymous attributes are propagated from instances to the
  realized geometry. If the same attribute exists on the geometry and on an
  instance, the attribute on the geometry has precedence.
* The id attribute has special handling to avoid creating the same id on many
  output points. This is necessary to make e.g. the Random Value node work
  as expected afterwards.

Realizing instance attributes has an effect on existing files, especially due to the
id attribute. To avoid breaking existing files, the Realize Instances node now has
a legacy option that is enabled for all already existing Realize Instances nodes.
Removing this legacy behavior does affect some existing files (although not many).
We can decide whether it's worth to remove the old behavior as a separate step.

This refactor also improves performance when realizing instances. That is mainly
due to multi-threading. See D13446 to get the file used for benchmarking. The
curve code is not as optimized as it could be yet. That's mainly because the storage
for these attributes might change soonish and it wasn't worth optimizing for the
current storage format right now.

```
1,000,000 x mesh vertex:       530 ms -> 130 ms
1,000,000 x simple cube:      1290 ms -> 190 ms
1,000,000 x point:            1000 ms -> 150 ms
1,000,000 x curve spiral:     1740 ms -> 330 ms
1,000,000 x curve line:       1110 ms -> 210 ms
10,000 x subdivided cylinder:  170 ms ->  40 ms
10 x subdivided spiral:        180 ms -> 180 ms
```

Differential Revision: https://developer.blender.org/D13446

8 files changed, 35 insertions, 374 deletions

diff --git a/source/blender/blenkernel/BKE_blender_version.h b/source/blender/blenkernel/BKE_blender_version.h
index 83429b58faf..d0ab8be9a29 100644
--- a/source/blender/blenkernel/BKE_blender_version.h
+++ b/source/blender/blenkernel/BKE_blender_version.h
@@ -39,7 +39,7 @@ extern "C" {
 
 /* Blender file format version. */
 #define BLENDER_FILE_VERSION BLENDER_VERSION
-#define BLENDER_FILE_SUBVERSION 4
+#define BLENDER_FILE_SUBVERSION 5
 
 /* Minimum Blender version that supports reading file written with the current
  * version. Older Blender versions will test this and show a warning if the file
diff --git a/source/blender/blenkernel/BKE_geometry_set_instances.hh b/source/blender/blenkernel/BKE_geometry_set_instances.hh
index 414cb750937..98120b07f2d 100644
--- a/source/blender/blenkernel/BKE_geometry_set_instances.hh
+++ b/source/blender/blenkernel/BKE_geometry_set_instances.hh
@@ -57,8 +57,6 @@ struct GeometryInstanceGroup {
 void geometry_set_gather_instances(const GeometrySet &geometry_set,
                                    Vector<GeometryInstanceGroup> &r_instance_groups);
 
-GeometrySet geometry_set_realize_instances(const GeometrySet &geometry_set);
-
 /**
  * Add information about all the attributes on every component of the type. The resulting info
  * will contain the highest complexity data type and the highest priority domain among every
diff --git a/source/blender/blenkernel/BKE_spline.hh b/source/blender/blenkernel/BKE_spline.hh
index 2073ec065fa..ebdc4a0ca0b 100644
--- a/source/blender/blenkernel/BKE_spline.hh
+++ b/source/blender/blenkernel/BKE_spline.hh
@@ -705,6 +705,7 @@ struct CurveEval {
    * \warning Call #reallocate on the spline's attributes after adding all splines.
    */
   void add_spline(SplinePtr spline);
+  void add_splines(blender::MutableSpan<SplinePtr> splines);
   void remove_splines(blender::IndexMask mask);
 
   void translate(const blender::float3 &translation);
diff --git a/source/blender/blenkernel/BKE_type_conversions.hh b/source/blender/blenkernel/BKE_type_conversions.hh
index 27419b32de6..ebfb13cd08f 100644
--- a/source/blender/blenkernel/BKE_type_conversions.hh
+++ b/source/blender/blenkernel/BKE_type_conversions.hh
@@ -72,6 +72,8 @@ class DataTypeConversions {
                                 const void *from_value,
                                 void *to_value) const;
 
+  void convert_to_initialized_n(fn::GSpan from_span, fn::GMutableSpan to_span) const;
+
   fn::GVArray try_convert(fn::GVArray varray, const CPPType &to_type) const;
 
   fn::GVMutableArray try_convert(fn::GVMutableArray varray, const CPPType &to_type) const;
diff --git a/source/blender/blenkernel/intern/curve_eval.cc b/source/blender/blenkernel/intern/curve_eval.cc
index 02abb097175..38f736e6907 100644
--- a/source/blender/blenkernel/intern/curve_eval.cc
+++ b/source/blender/blenkernel/intern/curve_eval.cc
@@ -71,6 +71,13 @@ void CurveEval::add_spline(SplinePtr spline)
   splines_.append(std::move(spline));
 }
 
+void CurveEval::add_splines(MutableSpan<SplinePtr> splines)
+{
+  for (SplinePtr &spline : splines) {
+    this->add_spline(std::move(spline));
+  }
+}
+
 void CurveEval::remove_splines(blender::IndexMask mask)
 {
   for (int i = mask.size() - 1; i >= 0; i--) {
diff --git a/source/blender/blenkernel/intern/geometry_set.cc b/source/blender/blenkernel/intern/geometry_set.cc
index 7830e897109..ef5609ec9a8 100644
--- a/source/blender/blenkernel/intern/geometry_set.cc
+++ b/source/blender/blenkernel/intern/geometry_set.cc
@@ -481,13 +481,18 @@ void GeometrySet::gather_attributes_for_propagation(
           return;
         }
 
+        AttributeDomain domain = meta_data.domain;
+        if (dst_component_type != GEO_COMPONENT_TYPE_INSTANCES && domain == ATTR_DOMAIN_INSTANCE) {
+          domain = ATTR_DOMAIN_POINT;
+        }
+
         auto add_info = [&](AttributeKind *attribute_kind) {
-          attribute_kind->domain = meta_data.domain;
+          attribute_kind->domain = domain;
           attribute_kind->data_type = meta_data.data_type;
         };
         auto modify_info = [&](AttributeKind *attribute_kind) {
           attribute_kind->domain = bke::attribute_domain_highest_priority(
-              {attribute_kind->domain, meta_data.domain});
+              {attribute_kind->domain, domain});
           attribute_kind->data_type = bke::attribute_data_type_highest_complexity(
               {attribute_kind->data_type, meta_data.data_type});
         };
diff --git a/source/blender/blenkernel/intern/geometry_set_instances.cc b/source/blender/blenkernel/intern/geometry_set_instances.cc
index 6d50dcd3c8c..4d84d5d899d 100644
--- a/source/blender/blenkernel/intern/geometry_set_instances.cc
+++ b/source/blender/blenkernel/intern/geometry_set_instances.cc
@@ -207,375 +207,6 @@ void geometry_set_gather_instances_attribute_info(Span<GeometryInstanceGroup> se
   }
 }
 
-static Mesh *join_mesh_topology_and_builtin_attributes(Span<GeometryInstanceGroup> set_groups)
-{
-  int totverts = 0;
-  int totloops = 0;
-  int totedges = 0;
-  int totpolys = 0;
-  int64_t cd_dirty_vert = 0;
-  int64_t cd_dirty_poly = 0;
-  int64_t cd_dirty_edge = 0;
-  int64_t cd_dirty_loop = 0;
-  VectorSet<Material *> materials;
-
-  for (const GeometryInstanceGroup &set_group : set_groups) {
-    const GeometrySet &set = set_group.geometry_set;
-    const int tot_transforms = set_group.transforms.size();
-    if (set.has_mesh()) {
-      const Mesh &mesh = *set.get_mesh_for_read();
-      totverts += mesh.totvert * tot_transforms;
-      totloops += mesh.totloop * tot_transforms;
-      totedges += mesh.totedge * tot_transforms;
-      totpolys += mesh.totpoly * tot_transforms;
-      cd_dirty_vert |= mesh.runtime.cd_dirty_vert;
-      cd_dirty_poly |= mesh.runtime.cd_dirty_poly;
-      cd_dirty_edge |= mesh.runtime.cd_dirty_edge;
-      cd_dirty_loop |= mesh.runtime.cd_dirty_loop;
-      for (const int slot_index : IndexRange(mesh.totcol)) {
-        Material *material = mesh.mat[slot_index];
-        materials.add(material);
-      }
-    }
-  }
-
-  /* Don't create an empty mesh. */
-  if ((totverts + totloops + totedges + totpolys) == 0) {
-    return nullptr;
-  }
-
-  Mesh *new_mesh = BKE_mesh_new_nomain(totverts, totedges, 0, totloops, totpolys);
-  /* Copy settings from the first input geometry set with a mesh. */
-  for (const GeometryInstanceGroup &set_group : set_groups) {
-    const GeometrySet &set = set_group.geometry_set;
-    if (set.has_mesh()) {
-      const Mesh &mesh = *set.get_mesh_for_read();
-      BKE_mesh_copy_parameters_for_eval(new_mesh, &mesh);
-      break;
-    }
-  }
-  for (const int i : IndexRange(materials.size())) {
-    Material *material = materials[i];
-    BKE_id_material_eval_assign(&new_mesh->id, i + 1, material);
-  }
-  new_mesh->runtime.cd_dirty_vert = cd_dirty_vert;
-  new_mesh->runtime.cd_dirty_poly = cd_dirty_poly;
-  new_mesh->runtime.cd_dirty_edge = cd_dirty_edge;
-  new_mesh->runtime.cd_dirty_loop = cd_dirty_loop;
-
-  int vert_offset = 0;
-  int loop_offset = 0;
-  int edge_offset = 0;
-  int poly_offset = 0;
-  for (const GeometryInstanceGroup &set_group : set_groups) {
-    const GeometrySet &set = set_group.geometry_set;
-    if (set.has_mesh()) {
-      const Mesh &mesh = *set.get_mesh_for_read();
-
-      Array<int> material_index_map(mesh.totcol);
-      for (const int i : IndexRange(mesh.totcol)) {
-        Material *material = mesh.mat[i];
-        const int new_material_index = materials.index_of(material);
-        material_index_map[i] = new_material_index;
-      }
-
-      for (const float4x4 &transform : set_group.transforms) {
-        for (const int i : IndexRange(mesh.totvert)) {
-          const MVert &old_vert = mesh.mvert[i];
-          MVert &new_vert = new_mesh->mvert[vert_offset + i];
-
-          new_vert = old_vert;
-
-          const float3 new_position = transform * float3(old_vert.co);
-          copy_v3_v3(new_vert.co, new_position);
-        }
-        for (const int i : IndexRange(mesh.totedge)) {
-          const MEdge &old_edge = mesh.medge[i];
-          MEdge &new_edge = new_mesh->medge[edge_offset + i];
-          new_edge = old_edge;
-          new_edge.v1 += vert_offset;
-          new_edge.v2 += vert_offset;
-        }
-        for (const int i : IndexRange(mesh.totloop)) {
-          const MLoop &old_loop = mesh.mloop[i];
-          MLoop &new_loop = new_mesh->mloop[loop_offset + i];
-          new_loop = old_loop;
-          new_loop.v += vert_offset;
-          new_loop.e += edge_offset;
-        }
-        for (const int i : IndexRange(mesh.totpoly)) {
-          const MPoly &old_poly = mesh.mpoly[i];
-          MPoly &new_poly = new_mesh->mpoly[poly_offset + i];
-          new_poly = old_poly;
-          new_poly.loopstart += loop_offset;
-          if (old_poly.mat_nr >= 0 && old_poly.mat_nr < mesh.totcol) {
-            new_poly.mat_nr = material_index_map[new_poly.mat_nr];
-          }
-          else {
-            /* The material index was invalid before. */
-            new_poly.mat_nr = 0;
-          }
-        }
-
-        vert_offset += mesh.totvert;
-        loop_offset += mesh.totloop;
-        edge_offset += mesh.totedge;
-        poly_offset += mesh.totpoly;
-      }
-    }
-  }
-
-  /* A possible optimization is to only tag the normals dirty when there are transforms that change
-   * normals. */
-  BKE_mesh_normals_tag_dirty(new_mesh);
-
-  return new_mesh;
-}
-
-static void join_attributes(Span<GeometryInstanceGroup> set_groups,
-                            Span<GeometryComponentType> component_types,
-                            const Map<AttributeIDRef, AttributeKind> &attribute_info,
-                            GeometryComponent &result)
-{
-  for (Map<AttributeIDRef, AttributeKind>::Item entry : attribute_info.items()) {
-    const AttributeIDRef attribute_id = entry.key;
-    const AttributeDomain domain_output = entry.value.domain;
-    const CustomDataType data_type_output = entry.value.data_type;
-    const CPPType *cpp_type = bke::custom_data_type_to_cpp_type(data_type_output);
-    BLI_assert(cpp_type != nullptr);
-
-    result.attribute_try_create(
-        entry.key, domain_output, data_type_output, AttributeInitDefault());
-    WriteAttributeLookup write_attribute = result.attribute_try_get_for_write(attribute_id);
-    if (!write_attribute || &write_attribute.varray.type() != cpp_type ||
-        write_attribute.domain != domain_output) {
-      continue;
-    }
-
-    fn::GVMutableArray_GSpan dst_span{write_attribute.varray};
-
-    int offset = 0;
-    for (const GeometryInstanceGroup &set_group : set_groups) {
-      const GeometrySet &set = set_group.geometry_set;
-      for (const GeometryComponentType component_type : component_types) {
-        if (set.has(component_type)) {
-          const GeometryComponent &component = *set.get_component_for_read(component_type);
-          const int domain_size = component.attribute_domain_size(domain_output);
-          if (domain_size == 0) {
-            continue; /* Domain size is 0, so no need to increment the offset. */
-          }
-          GVArray source_attribute = component.attribute_try_get_for_read(
-              attribute_id, domain_output, data_type_output);
-
-          if (source_attribute) {
-            fn::GVArray_GSpan src_span{source_attribute};
-            const void *src_buffer = src_span.data();
-            for (const int UNUSED(i) : set_group.transforms.index_range()) {
-              void *dst_buffer = dst_span[offset];
-              cpp_type->copy_assign_n(src_buffer, dst_buffer, domain_size);
-              offset += domain_size;
-            }
-          }
-          else {
-            offset += domain_size * set_group.transforms.size();
-          }
-        }
-      }
-    }
-
-    dst_span.save();
-  }
-}
-
-static PointCloud *join_pointcloud_position_attribute(Span<GeometryInstanceGroup> set_groups)
-{
-  /* Count the total number of points. */
-  int totpoint = 0;
-  for (const GeometryInstanceGroup &set_group : set_groups) {
-    const GeometrySet &set = set_group.geometry_set;
-    if (set.has<PointCloudComponent>()) {
-      const PointCloudComponent &component = *set.get_component_for_read<PointCloudComponent>();
-      totpoint += component.attribute_domain_size(ATTR_DOMAIN_POINT);
-    }
-  }
-  if (totpoint == 0) {
-    return nullptr;
-  }
-
-  PointCloud *new_pointcloud = BKE_pointcloud_new_nomain(totpoint);
-  MutableSpan new_positions{(float3 *)new_pointcloud->co, new_pointcloud->totpoint};
-
-  /* Transform each instance's point locations into the new point cloud. */
-  int offset = 0;
-  for (const GeometryInstanceGroup &set_group : set_groups) {
-    const GeometrySet &set = set_group.geometry_set;
-    const PointCloud *pointcloud = set.get_pointcloud_for_read();
-    if (pointcloud == nullptr) {
-      continue;
-    }
-    for (const float4x4 &transform : set_group.transforms) {
-      for (const int i : IndexRange(pointcloud->totpoint)) {
-        new_positions[offset + i] = transform * float3(pointcloud->co[i]);
-      }
-      offset += pointcloud->totpoint;
-    }
-  }
-
-  return new_pointcloud;
-}
-
-static CurveEval *join_curve_splines_and_builtin_attributes(Span<GeometryInstanceGroup> set_groups)
-{
-  Vector<SplinePtr> new_splines;
-  for (const GeometryInstanceGroup &set_group : set_groups) {
-    const GeometrySet &set = set_group.geometry_set;
-    if (!set.has_curve()) {
-      continue;
-    }
-
-    const CurveEval &source_curve = *set.get_curve_for_read();
-    for (const SplinePtr &source_spline : source_curve.splines()) {
-      for (const float4x4 &transform : set_group.transforms) {
-        SplinePtr new_spline = source_spline->copy_without_attributes();
-        new_spline->transform(transform);
-        new_splines.append(std::move(new_spline));
-      }
-    }
-  }
-  if (new_splines.is_empty()) {
-    return nullptr;
-  }
-
-  CurveEval *new_curve = new CurveEval();
-  for (SplinePtr &new_spline : new_splines) {
-    new_curve->add_spline(std::move(new_spline));
-  }
-
-  new_curve->attributes.reallocate(new_curve->splines().size());
-  return new_curve;
-}
-
-static void join_instance_groups_mesh(Span<GeometryInstanceGroup> set_groups, GeometrySet &result)
-{
-  Mesh *new_mesh = join_mesh_topology_and_builtin_attributes(set_groups);
-  if (new_mesh == nullptr) {
-    return;
-  }
-
-  MeshComponent &dst_component = result.get_component_for_write<MeshComponent>();
-  dst_component.replace(new_mesh);
-
-  /* Don't copy attributes that are stored directly in the mesh data structs. */
-  Map<AttributeIDRef, AttributeKind> attributes;
-  geometry_set_gather_instances_attribute_info(
-      set_groups,
-      {GEO_COMPONENT_TYPE_MESH},
-      {"position", "material_index", "normal", "shade_smooth", "crease"},
-      attributes);
-  join_attributes(set_groups,
-                  {GEO_COMPONENT_TYPE_MESH},
-                  attributes,
-                  static_cast<GeometryComponent &>(dst_component));
-}
-
-static void join_instance_groups_pointcloud(Span<GeometryInstanceGroup> set_groups,
-                                            GeometrySet &result)
-{
-  PointCloud *new_pointcloud = join_pointcloud_position_attribute(set_groups);
-  if (new_pointcloud == nullptr) {
-    return;
-  }
-
-  PointCloudComponent &dst_component = result.get_component_for_write<PointCloudComponent>();
-  dst_component.replace(new_pointcloud);
-
-  Map<AttributeIDRef, AttributeKind> attributes;
-  geometry_set_gather_instances_attribute_info(
-      set_groups, {GEO_COMPONENT_TYPE_POINT_CLOUD}, {"position"}, attributes);
-  join_attributes(set_groups,
-                  {GEO_COMPONENT_TYPE_POINT_CLOUD},
-                  attributes,
-                  static_cast<GeometryComponent &>(dst_component));
-}
-
-static void join_instance_groups_volume(Span<GeometryInstanceGroup> set_groups,
-                                        GeometrySet &result)
-{
-  /* Not yet supported; for now only return the first volume. Joining volume grids with the same
-   * name requires resampling of at least one of the grids. The cell size of the resulting volume
-   * has to be determined somehow. */
-  for (const GeometryInstanceGroup &set_group : set_groups) {
-    const GeometrySet &set = set_group.geometry_set;
-    if (set.has<VolumeComponent>()) {
-      result.add(*set.get_component_for_read<VolumeComponent>());
-      return;
-    }
-  }
-}
-
-/**
- * Curve point domain attributes must be in the same order on every spline. The order might have
- * been different on separate instances, so ensure that all splines have the same order. Note that
- * because #Map is used, the order is not necessarily consistent every time, but it is the same for
- * every spline, and that's what matters.
- */
-static void sort_curve_point_attributes(const Map<AttributeIDRef, AttributeKind> &info,
-                                        MutableSpan<SplinePtr> splines)
-{
-  Vector<AttributeIDRef> new_order;
-  for (Map<AttributeIDRef, AttributeKind>::Item item : info.items()) {
-    if (item.value.domain == ATTR_DOMAIN_POINT) {
-      /* Only sort attributes stored on splines. */
-      new_order.append(item.key);
-    }
-  }
-  for (SplinePtr &spline : splines) {
-    spline->attributes.reorder(new_order);
-  }
-}
-
-static void join_instance_groups_curve(Span<GeometryInstanceGroup> set_groups, GeometrySet &result)
-{
-  CurveEval *curve = join_curve_splines_and_builtin_attributes(set_groups);
-  if (curve == nullptr) {
-    return;
-  }
-
-  CurveComponent &dst_component = result.get_component_for_write<CurveComponent>();
-  dst_component.replace(curve);
-
-  Map<AttributeIDRef, AttributeKind> attributes;
-  geometry_set_gather_instances_attribute_info(
-      set_groups,
-      {GEO_COMPONENT_TYPE_CURVE},
-      {"position", "radius", "tilt", "handle_left", "handle_right", "cyclic", "resolution"},
-      attributes);
-  join_attributes(set_groups,
-                  {GEO_COMPONENT_TYPE_CURVE},
-                  attributes,
-                  static_cast<GeometryComponent &>(dst_component));
-  sort_curve_point_attributes(attributes, curve->splines());
-  curve->assert_valid_point_attributes();
-}
-
-GeometrySet geometry_set_realize_instances(const GeometrySet &geometry_set)
-{
-  if (!geometry_set.has_instances()) {
-    return geometry_set;
-  }
-
-  GeometrySet new_geometry_set;
-
-  Vector<GeometryInstanceGroup> set_groups;
-  geometry_set_gather_instances(geometry_set, set_groups);
-  join_instance_groups_mesh(set_groups, new_geometry_set);
-  join_instance_groups_pointcloud(set_groups, new_geometry_set);
-  join_instance_groups_volume(set_groups, new_geometry_set);
-  join_instance_groups_curve(set_groups, new_geometry_set);
-
-  return new_geometry_set;
-}
-
 }  // namespace blender::bke
 
 void InstancesComponent::foreach_referenced_geometry(
diff --git a/source/blender/blenkernel/intern/type_conversions.cc b/source/blender/blenkernel/intern/type_conversions.cc
index ab42d508538..b23220286e6 100644
--- a/source/blender/blenkernel/intern/type_conversions.cc
+++ b/source/blender/blenkernel/intern/type_conversions.cc
@@ -239,6 +239,23 @@ void DataTypeConversions::convert_to_uninitialized(const CPPType &from_type,
   functions->convert_single_to_uninitialized(from_value, to_value);
 }
 
+void DataTypeConversions::convert_to_initialized_n(fn::GSpan from_span,
+                                                   fn::GMutableSpan to_span) const
+{
+  const CPPType &from_type = from_span.type();
+  const CPPType &to_type = to_span.type();
+  BLI_assert(from_span.size() == to_span.size());
+  BLI_assert(this->is_convertible(from_type, to_type));
+  const fn::MultiFunction *fn = this->get_conversion_multi_function(
+      MFDataType::ForSingle(from_type), MFDataType::ForSingle(to_type));
+  fn::MFParamsBuilder params{*fn, from_span.size()};
+  params.add_readonly_single_input(from_span);
+  to_type.destruct_n(to_span.data(), to_span.size());
+  params.add_uninitialized_single_output(to_span);
+  fn::MFContextBuilder context;
+  fn->call_auto(IndexRange(from_span.size()), params, context);
+}
+
 class GVArray_For_ConvertedGVArray : public fn::GVArrayImpl {
  private:
   fn::GVArray varray_;