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

1 files changed, 83 insertions, 0 deletions

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();