Edit Mesh: New option "Split Edges & Faces" to "AutoMerge"

Ref T66423

Differential revision: https://developer.blender.org/D5562

9 files changed, 464 insertions, 3 deletions

diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index a348694c4da..abfd561200c 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -177,6 +177,12 @@ int BLI_bvhtree_find_nearest(BVHTree *tree,
                              BVHTree_NearestPointCallback callback,
                              void *userdata);
 
+int BLI_bvhtree_find_nearest_first(BVHTree *tree,
+                                   const float co[3],
+                                   const float dist_sq,
+                                   BVHTree_NearestPointCallback callback,
+                                   void *userdata);
+
 int BLI_bvhtree_ray_cast_ex(BVHTree *tree,
                             const float co[3],
                             const float dir[3],
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 0e93fd8e13b..ed3c7096865 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -1467,6 +1467,95 @@ int BLI_bvhtree_find_nearest(BVHTree *tree,
 /** \} */
 
 /* -------------------------------------------------------------------- */
+/** \name BLI_bvhtree_find_nearest_first
+ * \{ */
+
+static bool isect_aabb_v3(BVHNode *node, const float co[3])
+{
+  const BVHTreeAxisRange *bv = (const BVHTreeAxisRange *)node->bv;
+
+  if (co[0] > bv[0].min && co[0] < bv[0].max && co[1] > bv[1].min && co[1] < bv[1].max &&
+      co[2] > bv[2].min && co[2] < bv[2].max) {
+    return true;
+  }
+
+  return false;
+}
+
+static bool dfs_find_duplicate_fast_dfs(BVHNearestData *data, BVHNode *node)
+{
+  if (node->totnode == 0) {
+    if (isect_aabb_v3(node, data->co)) {
+      if (data->callback) {
+        const float dist_sq = data->nearest.dist_sq;
+        data->callback(data->userdata, node->index, data->co, &data->nearest);
+        return (data->nearest.dist_sq < dist_sq);
+      }
+      else {
+        data->nearest.index = node->index;
+        return true;
+      }
+    }
+  }
+  else {
+    /* Better heuristic to pick the closest node to dive on */
+    int i;
+
+    if (data->proj[node->main_axis] <= node->children[0]->bv[node->main_axis * 2 + 1]) {
+      for (i = 0; i != node->totnode; i++) {
+        if (isect_aabb_v3(node->children[i], data->co)) {
+          if (dfs_find_duplicate_fast_dfs(data, node->children[i])) {
+            return true;
+          }
+        }
+      }
+    }
+    else {
+      for (i = node->totnode; i--;) {
+        if (isect_aabb_v3(node->children[i], data->co)) {
+          if (dfs_find_duplicate_fast_dfs(data, node->children[i])) {
+            return true;
+          }
+        }
+      }
+    }
+  }
+  return false;
+}
+
+/**
+ * Find the first node nearby.
+ * Favors speed over quality since it doesn't find the best target node.
+ */
+int BLI_bvhtree_find_nearest_first(BVHTree *tree,
+                                   const float co[3],
+                                   const float dist_sq,
+                                   BVHTree_NearestPointCallback callback,
+                                   void *userdata)
+{
+  BVHNearestData data;
+  BVHNode *root = tree->nodes[tree->totleaf];
+
+  /* init data to search */
+  data.tree = tree;
+  data.co = co;
+
+  data.callback = callback;
+  data.userdata = userdata;
+  data.nearest.index = -1;
+  data.nearest.dist_sq = dist_sq;
+
+  /* dfs search */
+  if (root) {
+    dfs_find_duplicate_fast_dfs(&data, root);
+  }
+
+  return data.nearest.index;
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
 /** \name BLI_bvhtree_ray_cast
  *
  * raycast is done by performing a DFS on the BVHTree and saving the closest hit.
diff --git a/source/blender/bmesh/intern/bmesh_query.c b/source/blender/bmesh/intern/bmesh_query.c
index 51bc86e40eb..219bec15e5b 100644
--- a/source/blender/bmesh/intern/bmesh_query.c
+++ b/source/blender/bmesh/intern/bmesh_query.c
@@ -207,6 +207,34 @@ bool BM_vert_pair_share_face_check_cb(BMVert *v_a,
   return false;
 }
 
+BMFace *BM_vert_pair_shared_face_cb(BMVert *v_a,
+                                    BMVert *v_b,
+                                    const bool allow_adjacent,
+                                    bool (*callback)(BMFace *, BMLoop *, BMLoop *, void *userdata),
+                                    void *user_data,
+                                    BMLoop **r_l_a,
+                                    BMLoop **r_l_b)
+{
+  if (v_a->e && v_b->e) {
+    BMIter iter;
+    BMLoop *l_a, *l_b;
+
+    BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
+      BMFace *f = l_a->f;
+      l_b = BM_face_vert_share_loop(f, v_b);
+      if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b)) &&
+          callback(f, l_a, l_b, user_data)) {
+        *r_l_a = l_a;
+        *r_l_b = l_b;
+
+        return f;
+      }
+    }
+  }
+
+  return NULL;
+}
+
 /**
  * Given 2 verts, find the smallest face they share and give back both loops.
  */
diff --git a/source/blender/bmesh/intern/bmesh_query.h b/source/blender/bmesh/intern/bmesh_query.h
index e96984490c0..3a864fbb5dd 100644
--- a/source/blender/bmesh/intern/bmesh_query.h
+++ b/source/blender/bmesh/intern/bmesh_query.h
@@ -62,6 +62,13 @@ bool BM_vert_pair_share_face_check_cb(BMVert *v_a,
                                       bool (*test_fn)(BMFace *f, void *user_data),
                                       void *user_data) ATTR_WARN_UNUSED_RESULT
     ATTR_NONNULL(1, 2, 3);
+BMFace *BM_vert_pair_shared_face_cb(BMVert *v_a,
+                                    BMVert *v_b,
+                                    const bool allow_adjacent,
+                                    bool (*callback)(BMFace *, BMLoop *, BMLoop *, void *userdata),
+                                    void *user_data,
+                                    BMLoop **r_l_a,
+                                    BMLoop **r_l_b) ATTR_NONNULL(1, 2, 4, 6, 7);
 BMFace *BM_vert_pair_share_face_by_len(BMVert *v_a,
                                        BMVert *v_b,
                                        BMLoop **r_l_a,
diff --git a/source/blender/editors/include/ED_mesh.h b/source/blender/editors/include/ED_mesh.h
index 0b2adfed531..30d4aa10c1b 100644
--- a/source/blender/editors/include/ED_mesh.h
+++ b/source/blender/editors/include/ED_mesh.h
@@ -145,6 +145,8 @@ void ED_mesh_undosys_type(struct UndoType *ut);
 void EDBM_select_mirrored(
     struct BMEditMesh *em, const int axis, const bool extend, int *r_totmirr, int *r_totfail);
 void EDBM_automerge(struct Scene *scene, struct Object *ob, bool update, const char hflag);
+void EDBM_automerge_and_split(
+    struct Scene *scene, struct Object *ob, bool split_edges, bool update, const char hflag);
 
 struct BMVert *EDBM_vert_find_nearest_ex(struct ViewContext *vc,
                                          float *r_dist,
diff --git a/source/blender/editors/mesh/editmesh_select.c b/source/blender/editors/mesh/editmesh_select.c
index 94ffd9a34d6..e60934734bc 100644
--- a/source/blender/editors/mesh/editmesh_select.c
+++ b/source/blender/editors/mesh/editmesh_select.c
@@ -31,8 +31,10 @@
 #include "BLI_math.h"
 #include "BLI_math_bits.h"
 #include "BLI_rand.h"
+#include "BLI_sort.h"
 #include "BLI_array.h"
 
+#include "BKE_bvhutils.h"
 #include "BKE_context.h"
 #include "BKE_report.h"
 #include "BKE_paint.h"
@@ -193,6 +195,314 @@ void EDBM_automerge(Scene *scene, Object *obedit, bool update, const char hflag)
   }
 }
 
+struct EDBMSplitEdge {
+  BMVert *v;
+  BMEdge *e;
+  float lambda;
+};
+
+struct EDBMSplitEdgeData {
+  BMesh *bm;
+
+  BMEdge *r_edge;
+  float r_lambda;
+};
+
+static bool edbm_automerge_and_split_check_best_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)) {
+      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 bool edbm_automerge_check_and_split_faces(BMesh *bm, BMVert *v_src, BMVert *v_dst)
+{
+  BMIter iter;
+  BMEdge *e_iter;
+  BM_ITER_ELEM (e_iter, &iter, v_src, BM_EDGES_OF_VERT) {
+    BMVert *vert_other = BM_edge_other_vert(e_iter, v_src);
+    if (vert_other != v_dst) {
+      float data[2][3];
+      copy_v3_v3(data[0], vert_other->co);
+      sub_v3_v3v3(data[1], v_dst->co, data[0]);
+
+      BMLoop *l_a, *l_b;
+      BMFace *f = BM_vert_pair_shared_face_cb(
+          vert_other, v_dst, false, edbm_automerge_and_split_check_best_face_cb, data, &l_a, &l_b);
+
+      if (f) {
+        BM_face_split(bm, f, l_a, l_b, NULL, NULL, true);
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+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(
+    Scene *scene, Object *obedit, bool split_edges, bool update, const char hflag)
+{
+  bool ok = false;
+
+  BMEditMesh *em = BKE_editmesh_from_object(obedit);
+  BMesh *bm = em->bm;
+  float dist = scene->toolsettings->doublimit;
+  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");
+
+  /* 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);
+
+    edbm_automerge_check_and_split_faces(bm, v, v_dst);
+
+    ok = true;
+    verts_len--;
+  }
+
+  int totedge = bm->totedge;
+  if (totedge == 0 || verts_len == 0) {
+    split_edges = false;
+  }
+
+  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);
+      }
+    }
+
+    if (edges_len) {
+      /* 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);
+
+          BLI_bvhtree_insert(tree_edges, i, co[0], 2);
+
+          /* Use `e->head.index` to count intersections. */
+          e->head.index = 0;
+        }
+      }
+      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);
+
+            edbm_automerge_check_and_split_faces(bm, v, v_new);
+            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);
+
+  BMO_op_finish(bm, &findop);
+  BMO_op_finish(bm, &weldop);
+
+  if (LIKELY(ok) && update) {
+    EDBM_update_generic(em, true, true);
+  }
+}
+
 /** \} */
 
 /* -------------------------------------------------------------------- */
diff --git a/source/blender/editors/transform/transform_conversions.c b/source/blender/editors/transform/transform_conversions.c
index a6514526166..94a19514a86 100644
--- a/source/blender/editors/transform/transform_conversions.c
+++ b/source/blender/editors/transform/transform_conversions.c
@@ -7126,7 +7126,14 @@ static void special_aftertrans_update__mesh(bContext *UNUSED(C), TransInfo *t)
         hflag = BM_ELEM_SELECT;
       }
 
-      EDBM_automerge(t->scene, tc->obedit, true, hflag);
+      if (t->scene->toolsettings->automerge & AUTO_MERGE) {
+        if (t->scene->toolsettings->automerge & AUTO_MERGE_AND_SPLIT) {
+          EDBM_automerge_and_split(t->scene, tc->obedit, true, true, hflag);
+        }
+        else {
+          EDBM_automerge(t->scene, tc->obedit, true, hflag);
+        }
+      }
 
       /* Special case, this is needed or faces won't re-select.
        * Flush selected edges to faces. */
diff --git a/source/blender/makesdna/DNA_scene_types.h b/source/blender/makesdna/DNA_scene_types.h
index 412bf358a44..617656d1b2c 100644
--- a/source/blender/makesdna/DNA_scene_types.h
+++ b/source/blender/makesdna/DNA_scene_types.h
@@ -1366,6 +1366,12 @@ typedef struct MeshStatVis {
 /* *************************************************************** */
 /* Tool Settings */
 
+/* CurvePaintSettings.surface_plane */
+enum {
+  AUTO_MERGE = 1 << 0,
+  AUTO_MERGE_AND_SPLIT = 1 << 1,
+};
+
 typedef struct ToolSettings {
   /** Vertex paint. */
   VPaint *vpaint;
diff --git a/source/blender/makesrna/intern/rna_scene.c b/source/blender/makesrna/intern/rna_scene.c
index 939572923ac..67c82484864 100644
--- a/source/blender/makesrna/intern/rna_scene.c
+++ b/source/blender/makesrna/intern/rna_scene.c
@@ -2944,9 +2944,15 @@ static void rna_def_tool_settings(BlenderRNA *brna)
   RNA_def_property_update(prop, NC_SPACE | ND_SPACE_VIEW3D, NULL);
 
   prop = RNA_def_property(srna, "use_mesh_automerge", PROP_BOOLEAN, PROP_NONE);
-  RNA_def_property_boolean_sdna(prop, NULL, "automerge", 0);
+  RNA_def_property_boolean_sdna(prop, NULL, "automerge", AUTO_MERGE);
   RNA_def_property_ui_text(
-      prop, "Auto Merge", "Automatically merge vertices moved to the same location");
+      prop, "Auto Merge Vertices", "Automatically merge vertices moved to the same location");
+  RNA_def_property_ui_icon(prop, ICON_AUTOMERGE_OFF, 1);
+  RNA_def_property_update(prop, NC_SCENE | ND_TOOLSETTINGS, NULL); /* header redraw */
+
+  prop = RNA_def_property(srna, "use_mesh_automerge_and_split", PROP_BOOLEAN, PROP_NONE);
+  RNA_def_property_boolean_sdna(prop, NULL, "automerge", AUTO_MERGE_AND_SPLIT);
+  RNA_def_property_ui_text(prop, "Split Edges & Faces", "Automatically split edges and faces");
   RNA_def_property_ui_icon(prop, ICON_AUTOMERGE_OFF, 1);
   RNA_def_property_update(prop, NC_SCENE | ND_TOOLSETTINGS, NULL); /* header redraw */