Geometry Nodes: new Instance on Points node

This adds a new Instance on Points node that is a replacement
for the old Point Instance node. Contrary to the old node,
it does not have a mode to instance objects or collections
directly. Instead, the node has to be used with an Object/
Collection Info to achieve the same effect.

Rotation and scale of the instances can be adjusted in the node
directly or can be controlled with a field to get some variation
between instances.

The node supports placing different instances on different points.
The user has control over which instance is placed on which point
using an Instance Index input. If that functionality is used, the
Instance Geometry has to contain multiple instances that can are
instanced separately.

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

5 files changed, 102 insertions, 9 deletions

diff --git a/source/blender/blenkernel/BKE_geometry_set.hh b/source/blender/blenkernel/BKE_geometry_set.hh
index 5fcdbc83e25..571c6c6a0a0 100644
--- a/source/blender/blenkernel/BKE_geometry_set.hh
+++ b/source/blender/blenkernel/BKE_geometry_set.hh
@@ -323,6 +323,7 @@ struct GeometrySet {
   bool has_instances() const;
   bool has_volume() const;
   bool has_curve() const;
+  bool has_realized_data() const;
 
   const Mesh *get_mesh_for_read() const;
   const PointCloud *get_pointcloud_for_read() const;
@@ -478,7 +479,7 @@ class InstanceReference {
   Type type_ = Type::None;
   /** Depending on the type this is either null, an Object or Collection pointer. */
   void *data_ = nullptr;
-  std::unique_ptr<GeometrySet> geometry_set_;
+  std::shared_ptr<GeometrySet> geometry_set_;
 
  public:
   InstanceReference() = default;
@@ -493,17 +494,10 @@ class InstanceReference {
 
   InstanceReference(GeometrySet geometry_set)
       : type_(Type::GeometrySet),
-        geometry_set_(std::make_unique<GeometrySet>(std::move(geometry_set)))
+        geometry_set_(std::make_shared<GeometrySet>(std::move(geometry_set)))
   {
   }
 
-  InstanceReference(const InstanceReference &src) : type_(src.type_), data_(src.data_)
-  {
-    if (src.type_ == Type::GeometrySet) {
-      geometry_set_ = std::make_unique<GeometrySet>(*src.geometry_set_);
-    }
-  }
-
   Type type() const
   {
     return type_;
@@ -595,6 +589,7 @@ class InstancesComponent : public GeometryComponent {
   void add_instance(int instance_handle, const blender::float4x4 &transform, const int id = -1);
 
   blender::Span<InstanceReference> references() const;
+  void remove_unused_references();
 
   void ensure_geometry_instances();
   GeometrySet &geometry_set_from_reference(const int reference_index);
diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h
index 52f8a3d8136..5491f2a3de9 100644
--- a/source/blender/blenkernel/BKE_node.h
+++ b/source/blender/blenkernel/BKE_node.h
@@ -1502,6 +1502,7 @@ int ntreeTexExecTree(struct bNodeTree *ntree,
 #define GEO_NODE_CURVE_FILLET 1089
 #define GEO_NODE_DISTRIBUTE_POINTS_ON_FACES 1090
 #define GEO_NODE_STRING_TO_CURVES 1091
+#define GEO_NODE_INSTANCE_ON_POINTS 1092
 
 /** \} */
 
diff --git a/source/blender/blenkernel/intern/geometry_component_instances.cc b/source/blender/blenkernel/intern/geometry_component_instances.cc
index 9479d012cb8..f1f60266545 100644
--- a/source/blender/blenkernel/intern/geometry_component_instances.cc
+++ b/source/blender/blenkernel/intern/geometry_component_instances.cc
@@ -14,11 +14,14 @@
  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  */
 
+#include <mutex>
+
 #include "BLI_float4x4.hh"
 #include "BLI_map.hh"
 #include "BLI_rand.hh"
 #include "BLI_set.hh"
 #include "BLI_span.hh"
+#include "BLI_task.hh"
 #include "BLI_vector.hh"
 
 #include "DNA_collection_types.h"
@@ -182,6 +185,86 @@ blender::Span<InstanceReference> InstancesComponent::references() const
   return references_;
 }
 
+void InstancesComponent::remove_unused_references()
+{
+  using namespace blender;
+  using namespace blender::bke;
+
+  const int tot_instances = this->instances_amount();
+  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++;
+    }
+  }
+  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_amount() const
 {
   return instance_transforms_.size();
diff --git a/source/blender/blenkernel/intern/geometry_set.cc b/source/blender/blenkernel/intern/geometry_set.cc
index 54e9fadf8ed..1ebdde75f46 100644
--- a/source/blender/blenkernel/intern/geometry_set.cc
+++ b/source/blender/blenkernel/intern/geometry_set.cc
@@ -291,6 +291,19 @@ bool GeometrySet::has_curve() const
   return component != nullptr && component->has_curve();
 }
 
+/* Returns true when the geometry set has any data that is not an instance. */
+bool GeometrySet::has_realized_data() const
+{
+  if (components_.is_empty()) {
+    return false;
+  }
+  if (components_.size() > 1) {
+    return true;
+  }
+  /* Check if the only component is an #InstancesComponent. */
+  return this->get_component_for_read<InstancesComponent>() == nullptr;
+}
+
 /* Create a new geometry set that only contains the given mesh. */
 GeometrySet GeometrySet::create_with_mesh(Mesh *mesh, GeometryOwnershipType ownership)
 {
diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc
index c10aa3bbc5a..f1f643ffed7 100644
--- a/source/blender/blenkernel/intern/node.cc
+++ b/source/blender/blenkernel/intern/node.cc
@@ -5764,6 +5764,7 @@ static void registerGeometryNodes()
   register_node_type_geo_delete_geometry();
   register_node_type_geo_distribute_points_on_faces();
   register_node_type_geo_edge_split();
+  register_node_type_geo_instance_on_points();
   register_node_type_geo_input_index();
   register_node_type_geo_input_material();
   register_node_type_geo_input_normal();