Transform: AutoMerge & Split: Create and merge vertices at edge intersections

Differential Revision: D5635

1 files changed, 41 insertions, 430 deletions

diff --git a/source/blender/editors/mesh/editmesh_automerge.c b/source/blender/editors/mesh/editmesh_automerge.c
index 1d342c7e9a2..fb8ee85f9db 100644
--- a/source/blender/editors/mesh/editmesh_automerge.c
+++ b/source/blender/editors/mesh/editmesh_automerge.c
@@ -28,22 +28,19 @@
 
 #include "MEM_guardedalloc.h"
 
-#include "BLI_bitmap.h"
-#include "BLI_math.h"
-#include "BLI_sort.h"
-
-#include "BKE_bvhutils.h"
 #include "BKE_editmesh.h"
 
-#include "WM_api.h"
+#include "DNA_object_types.h"
+#include "DNA_scene_types.h"
 
 #include "ED_mesh.h"
-#include "ED_screen.h"
-#include "ED_transform.h"
 
-#include "DNA_object_types.h"
+#include "tools/bmesh_intersect_edges.h"
 
-#include "DEG_depsgraph.h"
+//#define DEBUG_TIME
+#ifdef DEBUG_TIME
+#  include "PIL_time.h"
+#endif
 
 /* use bmesh operator flags for a few operators */
 #define BMO_ELE_TAG 1
@@ -94,231 +91,8 @@ void EDBM_automerge(Object *obedit, bool update, const char hflag, const float d
  * Used after transform operations.
  * \{ */
 
-struct EDBMSplitEdge {
-  BMVert *v;
-  BMEdge *e;
-  float lambda;
-};
-
-struct EDBMSplitBestFaceData {
-  BMEdge **edgenet;
-  int edgenet_len;
-
-  /**
-   * Track the range of vertices in edgenet along the faces normal,
-   * find the lowest since it's most likely to be most co-planar with the face.
-   */
-  float best_face_range_on_normal_axis;
-  BMFace *r_best_face;
-};
-
-struct EDBMSplitEdgeData {
-  BMesh *bm;
-
-  BMEdge *r_edge;
-  float r_lambda;
-};
-
-static bool edbm_vert_pair_share_best_splittable_face_cb(BMFace *f,
-                                                         BMLoop *l_a,
-                                                         BMLoop *l_b,
-                                                         void *userdata)
-{
-  struct EDBMSplitBestFaceData *data = userdata;
-  float no[3];
-  copy_v3_v3(no, f->no);
-
-  float min = dot_v3v3(l_a->v->co, no);
-  float max = dot_v3v3(l_b->v->co, no);
-  if (min > max) {
-    SWAP(float, min, max);
-  }
-
-  BMVert *v_test = l_b->v;
-  BMEdge **e_iter = &data->edgenet[0];
-  int verts_len = data->edgenet_len - 1;
-  for (int i = verts_len; i--; e_iter++) {
-    v_test = BM_edge_other_vert(*e_iter, v_test);
-    if (!BM_face_point_inside_test(f, v_test->co)) {
-      return false;
-    }
-    float dot = dot_v3v3(v_test->co, no);
-    if (dot < min) {
-      min = dot;
-    }
-    if (dot > max) {
-      max = dot;
-    }
-  }
-
-  const float test_face_range_on_normal_axis = max - min;
-  if (test_face_range_on_normal_axis < data->best_face_range_on_normal_axis) {
-    data->best_face_range_on_normal_axis = test_face_range_on_normal_axis;
-    data->r_best_face = f;
-  }
-
-  return false;
-}
-
-/* find the best splittable face between the two vertices. */
-static bool edbm_vert_pair_share_splittable_face_cb(BMFace *UNUSED(f),
-                                                    BMLoop *l_a,
-                                                    BMLoop *l_b,
-                                                    void *userdata)
-{
-  float(*data)[3] = userdata;
-  float *v_a_co = data[0];
-  float *v_a_b_dir = data[1];
-
-  float lambda;
-  if (isect_ray_seg_v3(v_a_co, v_a_b_dir, l_a->prev->v->co, l_a->next->v->co, &lambda)) {
-    if (IN_RANGE(lambda, 0.0f, 1.0f)) {
-      return true;
-    }
-    else if (isect_ray_seg_v3(v_a_co, v_a_b_dir, l_b->prev->v->co, l_b->next->v->co, &lambda)) {
-      return IN_RANGE(lambda, 0.0f, 1.0f);
-    }
-  }
-  return false;
-}
-
-static void edbm_automerge_weld_linked_wire_edges_into_linked_faces(
-    BMesh *bm, BMVert *v, const float epsilon, BMEdge **r_edgenet[], int *r_edgenet_alloc_len)
-{
-  BMEdge **edgenet = *r_edgenet;
-  int edgenet_alloc_len = *r_edgenet_alloc_len;
-
-  BMIter iter;
-  BMEdge *e;
-  BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
-    int edgenet_len = 0;
-    BMVert *v_other = v;
-    while (BM_edge_is_wire(e)) {
-      if (edgenet_alloc_len == edgenet_len) {
-        edgenet_alloc_len = (edgenet_alloc_len + 1) * 2;
-        edgenet = MEM_reallocN(edgenet, (edgenet_alloc_len) * sizeof(*edgenet));
-      }
-      edgenet[edgenet_len++] = e;
-      v_other = BM_edge_other_vert(e, v_other);
-      if (v_other == v) {
-        /* Endless loop. */
-        break;
-      }
-
-      BMEdge *e_next = BM_DISK_EDGE_NEXT(e, v_other);
-      if (e_next == e) {
-        /* Vert is wire_endpoint. */
-        edgenet_len = 0;
-        break;
-      }
-
-      BMEdge *e_test = e_next;
-      while ((e_test = BM_DISK_EDGE_NEXT(e_test, v_other)) != e) {
-        if (e_test->l) {
-          /* Vert is linked to a face. */
-          goto l_break;
-        }
-      }
-
-      e = e_next;
-    }
-
-    BMLoop *dummy;
-    BMFace *best_face;
-
-  l_break:
-    if (edgenet_len == 0) {
-      /* Nothing to do. */
-      continue;
-    }
-    if (edgenet_len == 1) {
-      float data[2][3];
-      copy_v3_v3(data[0], v_other->co);
-      sub_v3_v3v3(data[1], v->co, data[0]);
-      best_face = BM_vert_pair_shared_face_cb(
-          v_other, v, true, edbm_vert_pair_share_splittable_face_cb, &data, &dummy, &dummy);
-    }
-    else {
-      struct EDBMSplitBestFaceData data = {
-          .edgenet = edgenet,
-          .edgenet_len = edgenet_len,
-          .best_face_range_on_normal_axis = FLT_MAX,
-          .r_best_face = NULL,
-      };
-      BM_vert_pair_shared_face_cb(
-          v_other, v, true, edbm_vert_pair_share_best_splittable_face_cb, &data, &dummy, &dummy);
-
-      if (data.r_best_face) {
-        float no[3], min = FLT_MAX, max = -FLT_MAX;
-        copy_v3_v3(no, data.r_best_face->no);
-        BMVert *v_test;
-        BMIter f_iter;
-        BM_ITER_ELEM (v_test, &f_iter, data.r_best_face, BM_VERTS_OF_FACE) {
-          float dot = dot_v3v3(v_test->co, no);
-          if (dot < min) {
-            min = dot;
-          }
-          if (dot > max) {
-            max = dot;
-          }
-        }
-        float range = max - min + 2 * epsilon;
-        if (range < data.best_face_range_on_normal_axis) {
-          data.r_best_face = NULL;
-        }
-      }
-      best_face = data.r_best_face;
-    }
-
-    if (best_face) {
-      BM_face_split_edgenet(bm, best_face, edgenet, edgenet_len, NULL, NULL);
-    }
-  }
-
-  *r_edgenet = edgenet;
-  *r_edgenet_alloc_len = edgenet_alloc_len;
-}
-
-static void ebbm_automerge_and_split_find_duplicate_cb(void *userdata,
-                                                       int index,
-                                                       const float co[3],
-                                                       BVHTreeNearest *nearest)
-{
-  struct EDBMSplitEdgeData *data = userdata;
-  BMEdge *e = BM_edge_at_index(data->bm, index);
-  float lambda = line_point_factor_v3_ex(co, e->v1->co, e->v2->co, 0.0f, -1.0f);
-  if (IN_RANGE(lambda, 0.0f, 1.0f)) {
-    float near_co[3];
-    interp_v3_v3v3(near_co, e->v1->co, e->v2->co, lambda);
-    float dist_sq = len_squared_v3v3(near_co, co);
-    if (dist_sq < nearest->dist_sq) {
-      nearest->dist_sq = dist_sq;
-      nearest->index = index;
-
-      data->r_edge = e;
-      data->r_lambda = lambda;
-    }
-  }
-}
-
-static int edbm_automerge_and_split_sort_cmp_by_keys_cb(const void *index1_v,
-                                                        const void *index2_v,
-                                                        void *keys_v)
-{
-  const struct EDBMSplitEdge *cuts = keys_v;
-  const int *index1 = (int *)index1_v;
-  const int *index2 = (int *)index2_v;
-
-  if (cuts[*index1].lambda > cuts[*index2].lambda) {
-    return 1;
-  }
-  else {
-    return -1;
-  }
-}
-
 void EDBM_automerge_and_split(Object *obedit,
-                              bool split_edges,
+                              bool UNUSED(split_edges),
                               bool split_faces,
                               bool update,
                               const char hflag,
@@ -328,219 +102,56 @@ void EDBM_automerge_and_split(Object *obedit,
 
   BMEditMesh *em = BKE_editmesh_from_object(obedit);
   BMesh *bm = em->bm;
-  BMOperator findop, weldop;
-  BMOpSlot *slot_targetmap;
-  BMIter iter;
-  BMVert *v;
-
-  /* tag and count the verts to be tested. */
-  BM_mesh_elem_toolflags_ensure(bm);
-  int verts_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);
-      BMO_vert_flag_enable(bm, v, BMO_ELE_TAG);
-      verts_len++;
-    }
-    else {
-      BM_elem_flag_disable(v, BM_ELEM_TAG);
-    }
-  }
 
-  /* Search for doubles among all vertices, but only merge non-BMO_ELE_TAG
-   * vertices into BMO_ELE_TAG vertices. */
-  BMO_op_initf(bm, &findop, 0, "find_doubles verts=%av keep_verts=%Fv dist=%f", BMO_ELE_TAG, dist);
-  BMO_op_exec(bm, &findop);
-
-  /* Init weld_verts operator to later fill the targetmap. */
-  BMO_op_init(bm, &weldop, 0, "weld_verts");
-  BMO_slot_copy(&findop, slots_out, "targetmap.out", &weldop, slots_in, "targetmap");
-
-  slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
+#ifdef DEBUG_TIME
+  em->bm = BM_mesh_copy(bm);
 
-  /* Remove duplicate vertices from the split edge test and check and split faces. */
-  GHashIterator gh_iter;
-  GHash *ghash_targetmap = BMO_SLOT_AS_GHASH(slot_targetmap);
-  GHASH_ITER (gh_iter, ghash_targetmap) {
-    v = BLI_ghashIterator_getKey(&gh_iter);
-    BMVert *v_dst = BLI_ghashIterator_getValue(&gh_iter);
-    if (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
-      /* Should this happen? */
-      SWAP(BMVert *, v, v_dst);
-    }
-    BLI_assert(BM_elem_flag_test(v, BM_ELEM_TAG));
-    BM_elem_flag_disable(v, BM_ELEM_TAG);
+  double t1 = PIL_check_seconds_timer();
+  EDBM_automerge(obedit, false, hflag, dist);
+  t1 = PIL_check_seconds_timer() - t1;
 
-    ok = true;
-    verts_len--;
-  }
+  BM_mesh_free(em->bm);
+  em->bm = bm;
+  double t2 = PIL_check_seconds_timer();
+#endif
 
-  int totedge = bm->totedge;
-  if (totedge == 0 || verts_len == 0) {
-    split_edges = false;
-  }
+  BMOperator weldop;
+  BMOpSlot *slot_targetmap;
 
-  if (split_edges) {
-    /* Count and tag edges. */
-    BMEdge *e;
-    int edges_len = 0;
-    BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
-      if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN) && !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_len++;
-      }
-      else {
-        BM_elem_flag_disable(e, BM_ELEM_TAG);
-      }
-    }
+  BMO_op_init(bm, &weldop, BMO_FLAG_DEFAULTS, "weld_verts");
+  slot_targetmap = BMO_slot_get(weldop.slots_in, "targetmap");
 
-    if (edges_len) {
-      /* Use `e->head.index` to count intersections. */
-      bm->elem_index_dirty &= ~BM_EDGE;
+  GHash *ghash_targetmap = BMO_SLOT_AS_GHASH(slot_targetmap);
 
-      /* Create a BVHTree of edges with `dist` as epsilon. */
-      BVHTree *tree_edges = BLI_bvhtree_new(edges_len, dist, 2, 6);
-      int i;
-      BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
-        if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
-          float co[2][3];
-          copy_v3_v3(co[0], e->v1->co);
-          copy_v3_v3(co[1], e->v2->co);
+  ok = BM_mesh_intersect_edges(bm, hflag, dist, ghash_targetmap);
 
-          BLI_bvhtree_insert(tree_edges, i, co[0], 2);
+  if (ok) {
+    BMO_op_exec(bm, &weldop);
 
-          e->head.index = 0;
-        }
+    BMEdge **edgenet = NULL;
+    int edgenet_alloc_len = 0;
+    if (split_faces) {
+      GHashIterator gh_iter;
+      GHASH_ITER (gh_iter, ghash_targetmap) {
+        BMVert *v = BLI_ghashIterator_getValue(&gh_iter);
+        // BLI_assert(BM_elem_flag_test(v, hflag) || hflag == BM_ELEM_TAG);
+        BM_vert_weld_linked_wire_edges_into_linked_faces(
+            bm, v, dist, &edgenet, &edgenet_alloc_len);
       }
-      BLI_bvhtree_balance(tree_edges);
-
-      struct EDBMSplitEdge *cuts_iter, *cuts;
-
-      /* Store all intersections in this array. */
-      cuts = MEM_mallocN(verts_len * sizeof(*cuts), __func__);
-      cuts_iter = &cuts[0];
-
-      int cuts_len = 0;
-      int cut_edges_len = 0;
-      float dist_sq = SQUARE(dist);
-      struct EDBMSplitEdgeData data = {bm};
-
-      /* Start the search for intersections. */
-      BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
-        if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
-          float co[3];
-          copy_v3_v3(co, v->co);
-          int e_index = BLI_bvhtree_find_nearest_first(
-              tree_edges, co, dist_sq, ebbm_automerge_and_split_find_duplicate_cb, &data);
-
-          if (e_index != -1) {
-            e = data.r_edge;
-            e->head.index++;
-
-            cuts_iter->v = v;
-            cuts_iter->e = e;
-            cuts_iter->lambda = data.r_lambda;
-            cuts_iter++;
-            cuts_len++;
-
-            if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
-              BM_elem_flag_disable(e, BM_ELEM_TAG);
-              cut_edges_len++;
-            }
-          }
-        }
-      }
-      BLI_bvhtree_free(tree_edges);
-
-      if (cuts_len) {
-        /* 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((cut_edges_len * sizeof(*e_map)) +
-                                (cuts_len * sizeof(*(e_map->cuts_index))),
-                            __func__);
-
-        int map_len = 0;
-        cuts_iter = &cuts[0];
-        for (i = 0; i < cuts_len; i++, cuts_iter++) {
-          e = cuts_iter->e;
-          if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
-            BM_elem_flag_enable(e, BM_ELEM_TAG);
-            int e_cuts_len = e->head.index;
-
-            e_map_iter = (void *)&e_map->as_int[map_len];
-            e_map_iter->cuts_len = e_cuts_len;
-            e_map_iter->cuts_index[0] = i;
-
-            /* Use `e->head.index` to indicate which slot to fill with the `cuts` index. */
-            e->head.index = map_len + 1;
-            map_len += 1 + e_cuts_len;
-          }
-          else {
-            e_map->as_int[++e->head.index] = i;
-          }
-        }
-
-        /* Split Edges and Faces. */
-        for (i = 0; i < map_len;
-             e_map_iter = (void *)&e_map->as_int[i], i += 1 + e_map_iter->cuts_len) {
-
-          /* sort by lambda. */
-          BLI_qsort_r(e_map_iter->cuts_index,
-                      e_map_iter->cuts_len,
-                      sizeof(*(e_map->cuts_index)),
-                      edbm_automerge_and_split_sort_cmp_by_keys_cb,
-                      cuts);
-
-          float lambda, lambda_prev = 0.0f;
-          for (int j = 0; j < e_map_iter->cuts_len; j++) {
-            cuts_iter = &cuts[e_map_iter->cuts_index[j]];
-            lambda = (cuts_iter->lambda - lambda_prev) / (1.0f - lambda_prev);
-            lambda_prev = cuts_iter->lambda;
-            v = cuts_iter->v;
-            e = cuts_iter->e;
-
-            BMVert *v_new = BM_edge_split(bm, e, e->v1, NULL, lambda);
-
-            BMO_slot_map_elem_insert(&weldop, slot_targetmap, v_new, v);
-          }
-        }
-
-        ok = true;
-        MEM_freeN(e_map);
-      }
-
-      MEM_freeN(cuts);
     }
-  }
-
-  BMO_op_exec(bm, &weldop);
 
-  BMEdge **edgenet = NULL;
-  int edgenet_alloc_len = 0;
-  if (split_faces) {
-    GHASH_ITER (gh_iter, ghash_targetmap) {
-      v = BLI_ghashIterator_getValue(&gh_iter);
-      BLI_assert(BM_elem_flag_test(v, hflag) || hflag == BM_ELEM_TAG);
-      edbm_automerge_weld_linked_wire_edges_into_linked_faces(
-          bm, v, dist, &edgenet, &edgenet_alloc_len);
+    if (edgenet) {
+      MEM_freeN(edgenet);
     }
   }
 
-  if (edgenet) {
-    MEM_freeN(edgenet);
-  }
-
-  BMO_op_finish(bm, &findop);
   BMO_op_finish(bm, &weldop);
 
+#ifdef DEBUG_TIME
+  t2 = PIL_check_seconds_timer() - t2;
+  printf("t1: %lf; t2: %lf; fac: %lf\n", t1, t2, t1 / t2);
+#endif
+
   if (LIKELY(ok) && update) {
     EDBM_update_generic(em, true, true);
   }