EditMesh: Improve AutoMerge with Split Edges & Faces

Previously, compared to `Auto Merge` without `Split Edges & Faces`,
`Auto Merge` with this option ignored duplicates between selected
vertices. It only considered duplicates between selected vertices and
unselected vertices.

This is a regress and not a progress.

This commit implements this behavior, so this option matches the other
`Auto Merge`.

1 files changed, 203 insertions, 321 deletions

diff --git a/source/blender/bmesh/tools/bmesh_intersect_edges.c b/source/blender/bmesh/tools/bmesh_intersect_edges.c
index 82e2151dc01..27102694e88 100644
--- a/source/blender/bmesh/tools/bmesh_intersect_edges.c
+++ b/source/blender/bmesh/tools/bmesh_intersect_edges.c
@@ -240,20 +240,15 @@ struct EDBMSplitElem {
 struct EDBMSplitData {
   BMesh *bm;
   BLI_Stack *pair_stack;
-  int cut_edges_a_len;
-  int cut_edges_b_len;
+  int cut_edges_len;
   float dist_sq;
   float dist_sq_sq;
 };
 
 /* Utils */
 
-static void bm_vert_pair_elem_setup_ex(BMVert *v,
-                                       float edge_index,
-                                       struct EDBMSplitElem *r_pair_elem)
+static void bm_vert_pair_elem_setup_ex(BMVert *v, struct EDBMSplitElem *r_pair_elem)
 {
-  BLI_assert(v->head.index == -1);
-  v->head.index = edge_index;
   r_pair_elem->vert = v;
 }
 
@@ -274,21 +269,23 @@ static void bm_edge_pair_elem_setup(BMEdge *e,
 }
 
 /* Util for Vert x Edge and Edge x Edge callbacks */
-static bool bm_vertxedge_isect_impl_ex(BMVert *v,
-                                       BMEdge *e,
-                                       int edge_index,
-                                       const float co[3],
-                                       const float dir[3],
-                                       float lambda,
-                                       float data_dist_sq,
-                                       int *data_cut_edges_len,
-                                       struct EDBMSplitElem r_pair[2])
+static bool bm_edgexvert_isect_impl(BMVert *v,
+                                    BMEdge *e,
+                                    const float co[3],
+                                    const float dir[3],
+                                    float lambda,
+                                    float data_dist_sq,
+                                    int *data_cut_edges_len,
+                                    struct EDBMSplitElem r_pair[2])
 {
-  BLI_assert(v->head.index == -1);
-
   BMVert *e_v;
   float dist_sq_vert_factor;
 
+  if (!IN_RANGE_INCL(lambda, 0.0f, 1.0f)) {
+    /* Vert x Vert is already handled elsewhere. */
+    return false;
+  }
+
   if (lambda < 0.5f) {
     e_v = e->v1;
     dist_sq_vert_factor = lambda;
@@ -299,27 +296,19 @@ static bool bm_vertxedge_isect_impl_ex(BMVert *v,
   }
 
   if (v != e_v) {
-    CLAMP(lambda, 0.0f, 1.0f);
+    float dist_sq_vert = SQUARE(dist_sq_vert_factor) * len_squared_v3(dir);
+    if (dist_sq_vert < data_dist_sq) {
+      /* Vert x Vert is already handled elsewhere. */
+      return false;
+    }
 
     float near[3];
     madd_v3_v3v3fl(near, co, dir, lambda);
 
     float dist_sq = len_squared_v3v3(v->co, near);
     if (dist_sq < data_dist_sq) {
-      float dist_sq_vert = SQUARE(dist_sq_vert_factor) * len_squared_v3(dir);
-      if (dist_sq_vert < data_dist_sq) {
-        if (e_v->head.index != -1) {
-          /* Vertex already has an intersection. */
-          return false;
-        }
-
-        bm_vert_pair_elem_setup_ex(e_v, -2, &r_pair[1]);
-      }
-      else {
-        bm_edge_pair_elem_setup(e, lambda, data_cut_edges_len, &r_pair[1]);
-      }
-
-      bm_vert_pair_elem_setup_ex(v, edge_index, &r_pair[0]);
+      bm_edge_pair_elem_setup(e, lambda, data_cut_edges_len, &r_pair[0]);
+      bm_vert_pair_elem_setup_ex(v, &r_pair[1]);
       return true;
     }
   }
@@ -340,75 +329,48 @@ static bool bm_vertxvert_isect_cb(void *userdata, int index_a, int index_b, int
   BLI_assert(v_a->head.index == -1);
 
   /* Set index -2 for sure that it will not repeat keys in `targetmap`. */
-  bm_vert_pair_elem_setup_ex(v_a, -2, &pair[0]);
-  bm_vert_pair_elem_setup_ex(v_b, -1, &pair[1]);
+  bm_vert_pair_elem_setup_ex(v_a, &pair[0]);
+  bm_vert_pair_elem_setup_ex(v_b, &pair[1]);
 
   return true;
 }
 
+static bool bm_vertxvert_self_isect_cb(void *userdata, int index_a, int index_b, int thread)
+{
+  if (index_a < index_b) {
+    return bm_vertxvert_isect_cb(userdata, index_a, index_b, thread);
+  }
+  return false;
+}
+
 /* Vertex x Edge and Edge x Vertex Callbacks */
 
-static int bm_vertxedge_isect_impl(BMesh *bm,
-                                   int vert_index,
-                                   int edge_index,
-                                   float data_dist_sq,
-                                   int *data_cut_edges_len,
-                                   struct EDBMSplitElem r_pair[2])
+static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
 {
-  BMVert *v = BM_vert_at_index(bm, vert_index);
-  BMEdge *e = BM_edge_at_index(bm, edge_index);
-
-  if (v->head.index != -1) {
-    /* Only one vertex per edge. */
-    return false;
-  }
+  struct EDBMSplitData *data = userdata;
+  BMEdge *e = BM_edge_at_index(data->bm, index_a);
+  BMVert *v = BM_vert_at_index(data->bm, index_b);
 
   float co[3], dir[3], lambda;
   copy_v3_v3(co, e->v1->co);
   sub_v3_v3v3(dir, e->v2->co, co);
   lambda = ray_point_factor_v3_ex(v->co, co, dir, 0.0f, -1.0f);
 
-  return bm_vertxedge_isect_impl_ex(
-      v, e, edge_index, co, dir, lambda, data_dist_sq, data_cut_edges_len, r_pair);
-}
-
-static bool bm_vertxedge_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
-{
-  struct EDBMSplitData *data = userdata;
   struct EDBMSplitElem pair_tmp[2];
-  if (bm_vertxedge_isect_impl(
-          data->bm, index_a, index_b, data->dist_sq, &data->cut_edges_b_len, pair_tmp)) {
+  if (bm_edgexvert_isect_impl(
+          v, e, co, dir, lambda, data->dist_sq, &data->cut_edges_len, pair_tmp)) {
     struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
     pair[0] = pair_tmp[0];
     pair[1] = pair_tmp[1];
-
-    return true;
-  }
-
-  return false;
-}
-
-static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
-{
-  struct EDBMSplitData *data = userdata;
-  struct EDBMSplitElem pair_tmp[2];
-  if (bm_vertxedge_isect_impl(
-          data->bm, index_b, index_a, data->dist_sq, &data->cut_edges_a_len, pair_tmp)) {
-    struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
-    pair[0] = pair_tmp[1];
-    pair[1] = pair_tmp[0];
-
-    return true;
   }
 
+  /* Always return false with edges. */
   return false;
 }
 
 /* Edge x Edge Callbacks */
 
 static void bm_edgexedge_isect_impl(struct EDBMSplitData *data,
-                                    int index_a,
-                                    int index_b,
                                     BMEdge *e_a,
                                     BMEdge *e_b,
                                     const float co_a[3],
@@ -439,8 +401,18 @@ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data,
   }
 
   if (e_a_v != e_b_v) {
-    CLAMP(lambda_a, 0.0f, 1.0f);
-    CLAMP(lambda_b, 0.0f, 1.0f);
+    if (!IN_RANGE_INCL(lambda_a, 0.0f, 1.0f) || !IN_RANGE_INCL(lambda_b, 0.0f, 1.0f)) {
+      /* Vert x Edge is already handled elsewhere. */
+      return;
+    }
+
+    float dist_sq_va = SQUARE(dist_sq_va_factor) * len_squared_v3(dir_a);
+    float dist_sq_vb = SQUARE(dist_sq_vb_factor) * len_squared_v3(dir_b);
+
+    if (dist_sq_va < data->dist_sq || dist_sq_vb < data->dist_sq) {
+      /* Vert x Edge is already handled elsewhere. */
+      return;
+    }
 
     float near_a[3], near_b[3];
     madd_v3_v3v3fl(near_a, co_a, dir_a, lambda_a);
@@ -450,32 +422,8 @@ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data,
     if (dist_sq < data->dist_sq) {
       struct EDBMSplitElem pair_tmp[2];
 
-      float dist_sq_va = SQUARE(dist_sq_va_factor) * len_squared_v3(dir_a);
-      float dist_sq_vb = SQUARE(dist_sq_vb_factor) * len_squared_v3(dir_b);
-
-      if (dist_sq_va < data->dist_sq) {
-        if (e_a_v->head.index != -1) {
-          /* Only one vertex per edge. */
-          return;
-        }
-        bm_vert_pair_elem_setup_ex(e_a_v, index_b, &pair_tmp[0]);
-      }
-
-      if (dist_sq_vb < data->dist_sq) {
-        if (e_b_v->head.index != -1) {
-          /* Only one vertex per edge. */
-          return;
-        }
-        bm_vert_pair_elem_setup_ex(e_b_v, index_a, &pair_tmp[1]);
-      }
-      else {
-        bm_edge_pair_elem_setup(e_b, lambda_b, &data->cut_edges_b_len, &pair_tmp[1]);
-      }
-
-      /* Don't setup edges before a return. */
-      if (dist_sq_va >= data->dist_sq) {
-        bm_edge_pair_elem_setup(e_a, lambda_a, &data->cut_edges_a_len, &pair_tmp[0]);
-      }
+      bm_edge_pair_elem_setup(e_a, lambda_a, &data->cut_edges_len, &pair_tmp[0]);
+      bm_edge_pair_elem_setup(e_b, lambda_b, &data->cut_edges_len, &pair_tmp[1]);
 
       struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
       pair[0] = pair_tmp[0];
@@ -486,11 +434,15 @@ static void bm_edgexedge_isect_impl(struct EDBMSplitData *data,
 
 static bool bm_edgexedge_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
 {
-  bool ret = false;
   struct EDBMSplitData *data = userdata;
   BMEdge *e_a = BM_edge_at_index(data->bm, index_a);
   BMEdge *e_b = BM_edge_at_index(data->bm, index_b);
 
+  if (BM_edge_share_vert_check(e_a, e_b)) {
+    /* The other vertices may intersect but Vert x Edge is already handled elsewhere. */
+    return false;
+  }
+
   float co_a[3], dir_a[3], co_b[3], dir_b[3];
   copy_v3_v3(co_a, e_a->v1->co);
   sub_v3_v3v3(dir_a, e_a->v2->co, co_a);
@@ -501,99 +453,19 @@ static bool bm_edgexedge_isect_cb(void *userdata, int index_a, int index_b, int
   float lambda_a, lambda_b;
   /* Using with dist^4 as `epsilon` is not the best solution, but it fits in most cases. */
   if (isect_ray_ray_epsilon_v3(co_a, dir_a, co_b, dir_b, data->dist_sq_sq, &lambda_a, &lambda_b)) {
-    if (ELEM(index_b, e_a->v1->head.index, e_a->v2->head.index) ||
-        ELEM(index_a, e_b->v1->head.index, e_b->v2->head.index)) {
-      return ret;
-    }
-
-    /* Edge x Edge returns always false. */
-    bm_edgexedge_isect_impl(
-        data, index_a, index_b, e_a, e_b, co_a, dir_a, co_b, dir_b, lambda_a, lambda_b);
+    bm_edgexedge_isect_impl(data, e_a, e_b, co_a, dir_a, co_b, dir_b, lambda_a, lambda_b);
   }
-  else {
-    /* Parallel */
-    struct EDBMSplitElem pair_tmp[2];
-    float vec[3], len_sq_a, len_sq_b, lambda;
-    sub_v3_v3v3(vec, co_b, co_a);
-    len_sq_a = len_squared_v3(dir_a);
-    len_sq_b = len_squared_v3(dir_b);
-
-    if (!ELEM(e_b->v1, e_a->v1, e_a->v2) && e_b->v1->head.index == -1) {
-      lambda = dot_v3v3(vec, dir_a) / len_sq_a;
-      if (bm_vertxedge_isect_impl_ex(e_b->v1,
-                                     e_a,
-                                     index_a,
-                                     co_a,
-                                     dir_a,
-                                     lambda,
-                                     data->dist_sq,
-                                     &data->cut_edges_a_len,
-                                     pair_tmp)) {
-        struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
-        pair[0] = pair_tmp[1];
-        pair[1] = pair_tmp[0];
-        ret |= true;
-      }
-    }
 
-    if (!ELEM(e_a->v1, e_b->v1, e_b->v2) && e_a->v1->head.index == -1) {
-      lambda = -dot_v3v3(vec, dir_b) / len_sq_b;
-      if (bm_vertxedge_isect_impl_ex(e_a->v1,
-                                     e_b,
-                                     index_b,
-                                     co_b,
-                                     dir_b,
-                                     lambda,
-                                     data->dist_sq,
-                                     &data->cut_edges_b_len,
-                                     pair_tmp)) {
-        struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
-        pair[0] = pair_tmp[0];
-        pair[1] = pair_tmp[1];
-        ret |= true;
-      }
-    }
-
-    add_v3_v3(vec, dir_b);
-    if (!ELEM(e_b->v2, e_a->v1, e_a->v2) && e_b->v2->head.index == -1) {
-      lambda = dot_v3v3(vec, dir_a) / len_sq_a;
-      if (bm_vertxedge_isect_impl_ex(e_b->v2,
-                                     e_a,
-                                     index_a,
-                                     co_a,
-                                     dir_a,
-                                     lambda,
-                                     data->dist_sq,
-                                     &data->cut_edges_a_len,
-                                     pair_tmp)) {
-        struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
-        pair[0] = pair_tmp[1];
-        pair[1] = pair_tmp[0];
-        ret |= true;
-      }
-    }
+  /* Edge x Edge returns always false. */
+  return false;
+}
 
-    sub_v3_v3(vec, dir_a);
-    if (!ELEM(e_a->v2, e_b->v1, e_b->v2) && e_a->v2->head.index == -1) {
-      lambda = 1.0f - dot_v3v3(vec, dir_b) / len_sq_b;
-      if (bm_vertxedge_isect_impl_ex(e_a->v2,
-                                     e_b,
-                                     index_b,
-                                     co_b,
-                                     dir_b,
-                                     lambda,
-                                     data->dist_sq,
-                                     &data->cut_edges_b_len,
-                                     pair_tmp)) {
-        struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
-        pair[0] = pair_tmp[0];
-        pair[1] = pair_tmp[1];
-        ret |= true;
-      }
-    }
+static bool bm_edgexedge_self_isect_cb(void *userdata, int index_a, int index_b, int thread)
+{
+  if (index_a < index_b) {
+    return bm_edgexedge_isect_cb(userdata, index_a, index_b, thread);
   }
-
-  return ret;
+  return false;
 }
 
 /* -------------------------------------------------------------------- */
@@ -610,27 +482,13 @@ static void bvhtree_overlap_thread_safe(const BVHTree *tree1,
 /* -------------------------------------------------------------------- */
 /* Callbacks for `BLI_qsort_r` */
 
-static int sort_cmp_by_lambda_a_cb(const void *index1_v, const void *index2_v, void *keys_v)
+static int sort_cmp_by_lambda_cb(const void *index1_v, const void *index2_v, void *keys_v)
 {
-  const struct EDBMSplitElem(*pair_array)[2] = keys_v;
+  const struct EDBMSplitElem *pair_flat = keys_v;
   const int index1 = *(int *)index1_v;
   const int index2 = *(int *)index2_v;
 
-  if (pair_array[index1][0].lambda > pair_array[index2][0].lambda) {
-    return 1;
-  }
-  else {
-    return -1;
-  }
-}
-
-static int sort_cmp_by_lambda_b_cb(const void *index1_v, const void *index2_v, void *keys_v)
-{
-  const struct EDBMSplitElem(*pair_array)[2] = keys_v;
-  const int index1 = *(int *)index1_v;
-  const int index2 = *(int *)index2_v;
-
-  if (pair_array[index1][1].lambda > pair_array[index2][1].lambda) {
+  if (pair_flat[index1].lambda > pair_flat[index2].lambda) {
     return 1;
   }
   else {
@@ -657,176 +515,199 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas
   BLI_Stack *pair_stack = BLI_stack_new(sizeof(*pair_array), __func__);
   int pair_len = 0;
 
-  float dist_sq = SQUARE(dist);
+  const float dist_sq = SQUARE(dist);
+  const float dist_half = dist / 2;
+
   struct EDBMSplitData data = {
       .bm = bm,
       .pair_stack = pair_stack,
-      .cut_edges_a_len = 0,
-      .cut_edges_b_len = 0,
+      .cut_edges_len = 0,
       .dist_sq = dist_sq,
       .dist_sq_sq = SQUARE(dist_sq),
   };
 
   /* tag and count the verts to be tested. */
   int verts_act_len = 0, verts_remain_len = 0;
-  int loose_verts_act_len = 0, loose_verts_remain_len = 0;
   BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
     if (BM_elem_flag_test(v, hflag)) {
       BM_elem_flag_enable(v, BM_ELEM_TAG);
       v->head.index = -1;
       verts_act_len++;
-      if (!v->e) {
-        loose_verts_act_len++;
-      }
     }
     else {
       BM_elem_flag_disable(v, BM_ELEM_TAG);
       if (!BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
         v->head.index = -1;
         verts_remain_len++;
-        if (!v->e) {
-          loose_verts_remain_len++;
-        }
       }
     }
   }
   bm->elem_index_dirty |= BM_VERT;
 
   /* Start the creation of BVHTrees. */
-  BVHTree *tree_loose_verts_act = NULL, *tree_loose_verts_remain = NULL;
-  if (loose_verts_act_len) {
-    tree_loose_verts_act = BLI_bvhtree_new(loose_verts_act_len, dist, 2, KDOP_AXIS_LEN);
+  BVHTree *tree_verts_act = NULL, *tree_verts_remain = NULL;
+  if (verts_act_len) {
+    tree_verts_act = BLI_bvhtree_new(verts_act_len, dist_half, 2, KDOP_AXIS_LEN);
   }
-  if (loose_verts_remain_len) {
-    tree_loose_verts_remain = BLI_bvhtree_new(loose_verts_remain_len, 0.0f, 2, KDOP_AXIS_LEN);
+  if (verts_remain_len) {
+    tree_verts_remain = BLI_bvhtree_new(verts_remain_len, dist_half, 2, KDOP_AXIS_LEN);
   }
 
-  if (tree_loose_verts_act || tree_loose_verts_remain) {
+  if (tree_verts_act || tree_verts_remain) {
     BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
       if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
-        if (tree_loose_verts_act && !v->e) {
-          BLI_bvhtree_insert(tree_loose_verts_act, i, v->co, 1);
+        if (tree_verts_act) {
+          BLI_bvhtree_insert(tree_verts_act, i, v->co, 1);
         }
       }
-      else if (tree_loose_verts_remain && !v->e && !BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
-        BLI_bvhtree_insert(tree_loose_verts_remain, i, v->co, 1);
+      else if (tree_verts_remain && !BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
+        BLI_bvhtree_insert(tree_verts_remain, i, v->co, 1);
       }
     }
-    if (tree_loose_verts_act) {
-      BLI_bvhtree_balance(tree_loose_verts_act);
+
+    if (tree_verts_act) {
+      BLI_bvhtree_balance(tree_verts_act);
+      /* First pair search. */
+      bvhtree_overlap_thread_safe(
+          tree_verts_act, tree_verts_act, bm_vertxvert_self_isect_cb, &data);
     }
 
-    if (tree_loose_verts_remain) {
-      BLI_bvhtree_balance(tree_loose_verts_remain);
+    if (tree_verts_remain) {
+      BLI_bvhtree_balance(tree_verts_remain);
     }
 
-    if (tree_loose_verts_act && tree_loose_verts_remain) {
-      /* First pair search. */
-      bvhtree_overlap_thread_safe(
-          tree_loose_verts_act, tree_loose_verts_remain, bm_vertxvert_isect_cb, &data);
+    if (tree_verts_act && tree_verts_remain) {
+      bvhtree_overlap_thread_safe(tree_verts_remain, tree_verts_act, bm_vertxvert_isect_cb, &data);
     }
   }
 
-  /* Tag and count the edges. */
-  int edges_act_len = 0, edges_remain_len = 0;
-  BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
-    if (BM_elem_flag_test(e->v1, BM_ELEM_TAG) || BM_elem_flag_test(e->v2, BM_ELEM_TAG)) {
-      BM_elem_flag_enable(e, BM_ELEM_TAG);
-      edges_act_len++;
-    }
-    else {
-      BM_elem_flag_disable(e, BM_ELEM_TAG);
-      if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
-        edges_remain_len++;
+  if (true) {
+    uint vert_x_vert_pair_len = BLI_stack_count(pair_stack);
+
+    /* Tag and count the edges. */
+    int edges_act_len = 0, edges_remain_len = 0;
+    BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+      if (BM_elem_flag_test(e->v1, BM_ELEM_TAG) || BM_elem_flag_test(e->v2, BM_ELEM_TAG)) {
+        BM_elem_flag_enable(e, BM_ELEM_TAG);
+        edges_act_len++;
+      }
+      else {
+        BM_elem_flag_disable(e, BM_ELEM_TAG);
+        if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
+          edges_remain_len++;
+        }
       }
     }
-  }
 
-  if (edges_remain_len) {
     BVHTree *tree_edges_act = NULL, *tree_edges_remain = NULL;
-    tree_edges_remain = BLI_bvhtree_new(edges_remain_len, 0.0f, 2, KDOP_AXIS_LEN);
     if (edges_act_len) {
-      tree_edges_act = BLI_bvhtree_new(edges_act_len, dist, 2, KDOP_AXIS_LEN);
+      tree_edges_act = BLI_bvhtree_new(edges_act_len, dist_half, 2, KDOP_AXIS_LEN);
+    }
+
+    if (edges_remain_len && (tree_edges_act || tree_verts_act)) {
+      tree_edges_remain = BLI_bvhtree_new(edges_remain_len, dist_half, 2, KDOP_AXIS_LEN);
     }
 
-    BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
-      float co[2][3];
-      if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
-        if (tree_edges_act) {
+    if (tree_edges_act || tree_edges_remain) {
+      BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
+        float co[2][3];
+        if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
+          if (tree_edges_act) {
+            e->head.index = 0;
+            copy_v3_v3(co[0], e->v1->co);
+            copy_v3_v3(co[1], e->v2->co);
+            BLI_bvhtree_insert(tree_edges_act, i, co[0], 2);
+          }
+        }
+        else if (tree_edges_remain && !BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
+          /* Tag used in the overlap callbacks. */
+          BM_elem_flag_enable(e, BM_ELEM_TAG);
           e->head.index = 0;
           copy_v3_v3(co[0], e->v1->co);
           copy_v3_v3(co[1], e->v2->co);
-          BLI_bvhtree_insert(tree_edges_act, i, co[0], 2);
+          BLI_bvhtree_insert(tree_edges_remain, i, co[0], 2);
         }
       }
-      else if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
-        /* Tag used in the overlap callbacks. */
-        BM_elem_flag_enable(e, BM_ELEM_TAG);
-        e->head.index = 0;
-        copy_v3_v3(co[0], e->v1->co);
-        copy_v3_v3(co[1], e->v2->co);
-        BLI_bvhtree_insert(tree_edges_remain, i, co[0], 2);
-      }
-    }
-    /* Use `e->head.index` to count intersections. */
-    bm->elem_index_dirty |= BM_EDGE;
+      /* Use `e->head.index` to count intersections. */
+      bm->elem_index_dirty |= BM_EDGE;
 
-    BLI_bvhtree_balance(tree_edges_remain);
-    if (tree_edges_act) {
-      BLI_bvhtree_balance(tree_edges_act);
-    }
+      if (tree_edges_act) {
+        BLI_bvhtree_balance(tree_edges_act);
+      }
 
-    if (tree_edges_act) {
-      /* Edge x Edge */
-      bvhtree_overlap_thread_safe(tree_edges_act, tree_edges_remain, bm_edgexedge_isect_cb, &data);
+      if (tree_edges_remain) {
+        BLI_bvhtree_balance(tree_edges_remain);
+      }
 
-      if (tree_loose_verts_remain) {
-        /* Edge x Vert */
+      if (tree_edges_act) {
+        /* Edge x Edge */
         bvhtree_overlap_thread_safe(
-            tree_edges_act, tree_loose_verts_remain, bm_edgexvert_isect_cb, &data);
-      }
+            tree_edges_act, tree_edges_act, bm_edgexedge_self_isect_cb, &data);
 
-      BLI_bvhtree_free(tree_edges_act);
-    }
+        if (tree_edges_remain) {
+          bvhtree_overlap_thread_safe(
+              tree_edges_remain, tree_edges_act, bm_edgexedge_isect_cb, &data);
+        }
 
-    if (tree_loose_verts_act) {
-      /* Vert x Edge */
-      bvhtree_overlap_thread_safe(
-          tree_loose_verts_act, tree_edges_remain, bm_vertxedge_isect_cb, &data);
-    }
+        if (tree_verts_act) {
+          /* Vert x Edge */
+          bvhtree_overlap_thread_safe(
+              tree_edges_act, tree_verts_act, bm_edgexvert_isect_cb, &data);
+        }
+
+        if (tree_verts_remain) {
+          /* Vert x Edge */
+          bvhtree_overlap_thread_safe(
+              tree_edges_act, tree_verts_remain, bm_edgexvert_isect_cb, &data);
+        }
 
-    BLI_bvhtree_free(tree_edges_remain);
+        BLI_bvhtree_free(tree_edges_act);
+      }
+
+      if (tree_verts_act && tree_edges_remain) {
+        /* Vert x Edge */
+        bvhtree_overlap_thread_safe(
+            tree_edges_remain, tree_verts_act, bm_edgexvert_isect_cb, &data);
+      }
 
-    pair_len = BLI_stack_count(pair_stack);
-    if (pair_len) {
-      pair_array = MEM_mallocN(sizeof(*pair_array) * pair_len, __func__);
-      BLI_stack_pop_n_reverse(pair_stack, pair_array, pair_len);
+      BLI_bvhtree_free(tree_edges_remain);
 
-      /* Map intersections per edge. */
-      union {
-        struct {
-          int cuts_len;
-          int cuts_index[];
-        };
-        int as_int[0];
-      } * e_map_iter, *e_map;
+      pair_len = BLI_stack_count(pair_stack);
+      int elem_x_edge_pair_len = pair_len - vert_x_vert_pair_len;
+      if (elem_x_edge_pair_len) {
+        pair_array = MEM_mallocN(sizeof(*pair_array) * pair_len, __func__);
+        BLI_stack_pop_n_reverse(pair_stack, pair_array, pair_len);
 
-      size_t e_map_size = (max_ii(data.cut_edges_a_len, data.cut_edges_b_len) * sizeof(*e_map)) +
-                          (pair_len * sizeof(*(e_map->cuts_index)));
+        /* Map intersections per edge. */
+        union {
+          struct {
+            int cuts_len;
+            int cuts_index[];
+          };
+          int as_int[0];
+        } * e_map_iter, *e_map;
 
-      e_map = MEM_mallocN(e_map_size, __func__);
+        size_t e_map_size = (data.cut_edges_len * sizeof(*e_map)) +
+                            (2 * (size_t)elem_x_edge_pair_len * sizeof(*(e_map->cuts_index)));
 
-      /* Convert every pair to Vert x Vert. */
-      for (int pair = 0; pair < 2; pair++) {
+        e_map = MEM_mallocN(e_map_size, __func__);
         int map_len = 0;
-        pair_iter = &pair_array[0];
-        for (i = 0; i < pair_len; i++, pair_iter++) {
-          if ((*pair_iter)[pair].elem->head.htype != BM_EDGE) {
-            /* Take the opportunity to set all vert indices to -1 again. */
-            (*pair_iter)[pair].elem->head.index = -1;
+
+        /* Convert every pair to Vert x Vert. */
+
+        /* The list of pairs starts with [vert x vert] followed by [edge x edge]
+         * and finally [vert x edge].
+         * Ignore the [vert x vert] pairs */
+        struct EDBMSplitElem *pair_flat, *pair_flat_iter;
+        pair_flat = (struct EDBMSplitElem *)&pair_array[vert_x_vert_pair_len];
+        pair_flat_iter = &pair_flat[0];
+        uint pair_flat_len = 2 * elem_x_edge_pair_len;
+        for (i = 0; i < pair_flat_len; i++, pair_flat_iter++) {
+          if (pair_flat_iter->elem->head.htype != BM_EDGE) {
             continue;
           }
-          e = (*pair_iter)[pair].edge;
+
+          e = pair_flat_iter->edge;
           if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
             BM_elem_flag_enable(e, BM_ELEM_TAG);
             int e_cuts_len = e->head.index;
@@ -852,12 +733,14 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas
           BLI_qsort_r(e_map_iter->cuts_index,
                       e_map_iter->cuts_len,
                       sizeof(*(e_map->cuts_index)),
-                      pair == 0 ? sort_cmp_by_lambda_a_cb : sort_cmp_by_lambda_b_cb,
-                      pair_array);
+                      sort_cmp_by_lambda_cb,
+                      pair_flat);
 
           float lambda, lambda_prev = 0.0f;
           for (int j = 0; j < e_map_iter->cuts_len; j++) {
-            struct EDBMSplitElem *pair_elem = &pair_array[e_map_iter->cuts_index[j]][pair];
+            uint index = e_map_iter->cuts_index[j];
+
+            struct EDBMSplitElem *pair_elem = &pair_flat[index];
             lambda = (pair_elem->lambda - lambda_prev) / (1.0f - lambda_prev);
             lambda_prev = pair_elem->lambda;
             e = pair_elem->edge;
@@ -867,14 +750,14 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas
             pair_elem->vert = v_new;
           }
         }
-      }
 
-      MEM_freeN(e_map);
+        MEM_freeN(e_map);
+      }
     }
   }
 
-  BLI_bvhtree_free(tree_loose_verts_act);
-  BLI_bvhtree_free(tree_loose_verts_remain);
+  BLI_bvhtree_free(tree_verts_act);
+  BLI_bvhtree_free(tree_verts_remain);
 
   if (r_targetmap) {
     if (pair_array == NULL) {
@@ -886,7 +769,6 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas
     }
 
     if (pair_array) {
-      /* Organize the vertices in the order they will be merged. */
       pair_iter = &pair_array[0];
       for (i = 0; i < pair_len; i++, pair_iter++) {
         BLI_assert((*pair_iter)[0].elem->head.htype == BM_VERT);