Fix T70864: Separate loose parts runs indefinitely

Large objects with many separate pieces became unstably slow
(run for hours and not finish).

The entire original mesh was being duplicated twice per loose part.

In own tests, millions of vertices and thousands of loose parts
now run in around 5-15 seconds.

6 files changed, 267 insertions, 0 deletions

diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index 599871a505a..00954eb400c 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -99,6 +99,8 @@ set(SRC
   intern/bmesh_mesh.h
   intern/bmesh_mesh_conv.c
   intern/bmesh_mesh_conv.h
+  intern/bmesh_mesh_duplicate.c
+  intern/bmesh_mesh_duplicate.h
   intern/bmesh_mesh_validate.c
   intern/bmesh_mesh_validate.h
   intern/bmesh_mods.c
diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h
index b7356a89314..bdb719e0d7a 100644
--- a/source/blender/bmesh/bmesh.h
+++ b/source/blender/bmesh/bmesh.h
@@ -216,6 +216,7 @@ extern "C" {
 #include "intern/bmesh_marking.h"
 #include "intern/bmesh_mesh.h"
 #include "intern/bmesh_mesh_conv.h"
+#include "intern/bmesh_mesh_duplicate.h"
 #include "intern/bmesh_mesh_validate.h"
 #include "intern/bmesh_mods.h"
 #include "intern/bmesh_operators.h"
diff --git a/source/blender/bmesh/intern/bmesh_mesh_duplicate.c b/source/blender/bmesh/intern/bmesh_mesh_duplicate.c
new file mode 100644
index 00000000000..51f9d2eab1d
--- /dev/null
+++ b/source/blender/bmesh/intern/bmesh_mesh_duplicate.c
@@ -0,0 +1,139 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bmesh
+ *
+ * Duplicate geometry from one mesh from another.
+ */
+
+#include "DNA_object_types.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_alloca.h"
+#include "BLI_math_vector.h"
+
+#include "bmesh.h"
+#include "intern/bmesh_private.h" /* for element checking */
+
+static BMVert *bm_vert_copy(BMesh *bm_src, BMesh *bm_dst, BMVert *v_src)
+{
+  BMVert *v_dst = BM_vert_create(bm_dst, v_src->co, NULL, BM_CREATE_SKIP_CD);
+  BM_elem_attrs_copy(bm_src, bm_dst, v_src, v_dst);
+  return v_dst;
+}
+
+static BMEdge *bm_edge_copy_with_arrays(BMesh *bm_src,
+                                        BMesh *bm_dst,
+                                        BMEdge *e_src,
+                                        BMVert **verts_dst)
+{
+  BMVert *e_dst_v1 = verts_dst[BM_elem_index_get(e_src->v1)];
+  BMVert *e_dst_v2 = verts_dst[BM_elem_index_get(e_src->v2)];
+  BMEdge *e_dst = BM_edge_create(bm_dst, e_dst_v1, e_dst_v2, NULL, BM_CREATE_SKIP_CD);
+  BM_elem_attrs_copy(bm_src, bm_dst, e_src, e_dst);
+  return e_dst;
+}
+
+static BMFace *bm_face_copy_with_arrays(
+    BMesh *bm_src, BMesh *bm_dst, BMFace *f_src, BMVert **verts_dst, BMEdge **edges_dst
+
+)
+{
+  BMFace *f_dst;
+  BMVert **vtar = BLI_array_alloca(vtar, f_src->len);
+  BMEdge **edar = BLI_array_alloca(edar, f_src->len);
+  BMLoop *l_iter_src, *l_iter_dst, *l_first_src;
+  int i;
+
+  l_first_src = BM_FACE_FIRST_LOOP(f_src);
+
+  /* Lookup verts & edges. */
+  l_iter_src = l_first_src;
+  i = 0;
+  do {
+    vtar[i] = verts_dst[BM_elem_index_get(l_iter_src->v)];
+    edar[i] = edges_dst[BM_elem_index_get(l_iter_src->e)];
+    i++;
+  } while ((l_iter_src = l_iter_src->next) != l_first_src);
+
+  /* Create new face. */
+  f_dst = BM_face_create(bm_dst, vtar, edar, f_src->len, NULL, BM_CREATE_SKIP_CD);
+
+  /* Copy attributes. */
+  BM_elem_attrs_copy(bm_src, bm_dst, f_src, f_dst);
+
+  /* Copy per-loop custom data. */
+  l_iter_src = l_first_src;
+  l_iter_dst = BM_FACE_FIRST_LOOP(f_dst);
+  do {
+    BM_elem_attrs_copy(bm_src, bm_dst, l_iter_src, l_iter_dst);
+  } while ((void)(l_iter_dst = l_iter_dst->next), (l_iter_src = l_iter_src->next) != l_first_src);
+
+  return f_dst;
+}
+
+/**
+ * Geometry must be completely isolated.
+ */
+void BM_mesh_copy_arrays(BMesh *bm_src,
+                         BMesh *bm_dst,
+                         BMVert **verts_src,
+                         uint verts_src_len,
+                         BMEdge **edges_src,
+                         uint edges_src_len,
+                         BMFace **faces_src,
+                         uint faces_src_len)
+{
+  /* Vertices. */
+  BMVert **verts_dst = MEM_mallocN(sizeof(*verts_dst) * verts_src_len, __func__);
+  for (uint i = 0; i < verts_src_len; i++) {
+    BMVert *v_src = verts_src[i];
+    BM_elem_index_set(v_src, i); /* set_dirty! */
+
+    BMVert *v_dst = bm_vert_copy(bm_src, bm_dst, v_src);
+    BM_elem_index_set(v_dst, i); /* set_ok */
+    verts_dst[i] = v_dst;
+  }
+  bm_src->elem_index_dirty |= BM_VERT;
+  bm_dst->elem_index_dirty &= ~BM_VERT;
+
+  /* Edges. */
+  BMEdge **edges_dst = MEM_mallocN(sizeof(*edges_dst) * edges_src_len, __func__);
+  for (uint i = 0; i < edges_src_len; i++) {
+    BMEdge *e_src = edges_src[i];
+    BM_elem_index_set(e_src, i); /* set_dirty! */
+
+    BMEdge *e_dst = bm_edge_copy_with_arrays(bm_src, bm_dst, e_src, verts_dst);
+    BM_elem_index_set(e_dst, i);
+    edges_dst[i] = e_dst;
+  }
+  bm_src->elem_index_dirty |= BM_EDGE;
+  bm_dst->elem_index_dirty &= ~BM_EDGE;
+
+  /* Faces. */
+  for (uint i = 0; i < faces_src_len; i++) {
+    BMFace *f_src = faces_src[i];
+    BMFace *f_dst = bm_face_copy_with_arrays(bm_src, bm_dst, f_src, verts_dst, edges_dst);
+    BM_elem_index_set(f_dst, i);
+  }
+  bm_dst->elem_index_dirty &= ~BM_FACE;
+
+  /* Cleanup. */
+  MEM_freeN(verts_dst);
+  MEM_freeN(edges_dst);
+}
diff --git a/source/blender/bmesh/intern/bmesh_mesh_duplicate.h b/source/blender/bmesh/intern/bmesh_mesh_duplicate.h
new file mode 100644
index 00000000000..17d4071b69f
--- /dev/null
+++ b/source/blender/bmesh/intern/bmesh_mesh_duplicate.h
@@ -0,0 +1,33 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __BMESH_MESH_DUPLICATE_H__
+#define __BMESH_MESH_DUPLICATE_H__
+
+/** \file
+ * \ingroup bmesh
+ */
+
+void BM_mesh_copy_arrays(BMesh *bm_src,
+                         BMesh *bm_dst,
+                         BMVert **verts_src,
+                         uint verts_src_len,
+                         BMEdge **edges_src,
+                         uint edges_src_len,
+                         BMFace **faces_src,
+                         uint faces_src_len);
+
+#endif /* __BMESH_MESH_DUPLICATE_H__ */
diff --git a/source/blender/bmesh/intern/bmesh_query.c b/source/blender/bmesh/intern/bmesh_query.c
index 219bec15e5b..cebfd4df75b 100644
--- a/source/blender/bmesh/intern/bmesh_query.c
+++ b/source/blender/bmesh/intern/bmesh_query.c
@@ -2808,6 +2808,91 @@ int BM_mesh_calc_edge_groups(BMesh *bm,
   return group_curr;
 }
 
+int BM_mesh_calc_edge_groups_as_arrays(
+    BMesh *bm, BMVert **verts, BMEdge **edges, BMFace **faces, int (**r_groups)[3])
+{
+  int(*groups)[3] = MEM_mallocN(sizeof(*groups) * bm->totvert, __func__);
+  STACK_DECLARE(groups);
+  STACK_INIT(groups, bm->totvert);
+
+  /* Clear all selected vertices */
+  BM_mesh_elem_hflag_disable_all(bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_TAG, false);
+
+  BMVert **stack = MEM_mallocN(sizeof(*stack) * bm->totvert, __func__);
+  STACK_DECLARE(stack);
+  STACK_INIT(stack, bm->totvert);
+
+  STACK_DECLARE(verts);
+  STACK_INIT(verts, bm->totvert);
+
+  STACK_DECLARE(edges);
+  STACK_INIT(edges, bm->totedge);
+
+  STACK_DECLARE(faces);
+  STACK_INIT(faces, bm->totface);
+
+  BMIter iter;
+  BMVert *v_stack_init;
+  BM_ITER_MESH (v_stack_init, &iter, bm, BM_VERTS_OF_MESH) {
+    if (BM_elem_flag_test(v_stack_init, BM_ELEM_TAG)) {
+      continue;
+    }
+
+    const uint verts_init = STACK_SIZE(verts);
+    const uint edges_init = STACK_SIZE(edges);
+    const uint faces_init = STACK_SIZE(faces);
+
+    /* Initialize stack. */
+    BM_elem_flag_enable(v_stack_init, BM_ELEM_TAG);
+    STACK_PUSH(verts, v_stack_init);
+
+    if (v_stack_init->e != NULL) {
+      BMVert *v_iter = v_stack_init;
+      do {
+        BMEdge *e_iter, *e_first;
+        e_iter = e_first = v_iter->e;
+        do {
+          if (!BM_elem_flag_test(e_iter, BM_ELEM_TAG)) {
+            BM_elem_flag_enable(e_iter, BM_ELEM_TAG);
+            STACK_PUSH(edges, e_iter);
+
+            if (e_iter->l != NULL) {
+              BMLoop *l_iter, *l_first;
+              l_iter = l_first = e_iter->l;
+              do {
+                if (!BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
+                  BM_elem_flag_enable(l_iter->f, BM_ELEM_TAG);
+                  STACK_PUSH(faces, l_iter->f);
+                }
+              } while ((l_iter = l_iter->radial_next) != l_first);
+            }
+
+            BMVert *v_other = BM_edge_other_vert(e_iter, v_iter);
+            if (!BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
+              BM_elem_flag_enable(v_other, BM_ELEM_TAG);
+              STACK_PUSH(verts, v_other);
+
+              STACK_PUSH(stack, v_other);
+            }
+          }
+        } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_iter)) != e_first);
+      } while ((v_iter = STACK_POP(stack)));
+    }
+
+    int *g = STACK_PUSH_RET(groups);
+    g[0] = STACK_SIZE(verts) - verts_init;
+    g[1] = STACK_SIZE(edges) - edges_init;
+    g[2] = STACK_SIZE(faces) - faces_init;
+  }
+
+  MEM_freeN(stack);
+
+  /* Reduce alloc to required size. */
+  groups = MEM_reallocN(groups, sizeof(*groups) * STACK_SIZE(groups));
+  *r_groups = groups;
+  return STACK_SIZE(groups);
+}
+
 float bmesh_subd_falloff_calc(const int falloff, float val)
 {
   switch (falloff) {
diff --git a/source/blender/bmesh/intern/bmesh_query.h b/source/blender/bmesh/intern/bmesh_query.h
index 3a864fbb5dd..134e0b99691 100644
--- a/source/blender/bmesh/intern/bmesh_query.h
+++ b/source/blender/bmesh/intern/bmesh_query.h
@@ -249,6 +249,13 @@ int BM_mesh_calc_edge_groups(BMesh *bm,
                              void *user_data,
                              const char hflag_test) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3);
 
+int BM_mesh_calc_edge_groups_as_arrays(BMesh *bm,
+                                       BMVert **verts,
+                                       BMEdge **edges,
+                                       BMFace **faces,
+                                       int (**r_groups)[3]) ATTR_WARN_UNUSED_RESULT
+    ATTR_NONNULL(1, 2, 3, 4, 5);
+
 /* not really any good place  to put this */
 float bmesh_subd_falloff_calc(const int falloff, float val) ATTR_WARN_UNUSED_RESULT;