Edit Mesh: Auto Merge - Split Edges & Faces - Better logic for splitting faces

Differential Revision: https://developer.blender.org/D6626

2 files changed, 214 insertions, 105 deletions

diff --git a/source/blender/bmesh/tools/bmesh_intersect_edges.c b/source/blender/bmesh/tools/bmesh_intersect_edges.c
index c3687c5d477..b25dc82aac9 100644
--- a/source/blender/bmesh/tools/bmesh_intersect_edges.c
+++ b/source/blender/bmesh/tools/bmesh_intersect_edges.c
@@ -57,7 +57,7 @@ struct EDBMSplitBestFaceData {
    * 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;
+  float best_edgenet_range_on_face_normal;
   BMFace *r_best_face;
 };
 
@@ -76,11 +76,14 @@ static bool bm_vert_pair_share_best_splittable_face_cb(BMFace *f,
     SWAP(float, min, max);
   }
 
-  BMVert *v_test = l_b->v;
   BMEdge **e_iter = &data->edgenet[0];
+  BMEdge *e_next = data->edgenet[1];
+  BMVert *v_test = ELEM((*e_iter)->v1, e_next->v1, e_next->v2) ? (*e_iter)->v2 : (*e_iter)->v1;
+
   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);
+    BLI_assert(v_test != NULL);
     if (!BM_face_point_inside_test(f, v_test->co)) {
       return false;
     }
@@ -93,9 +96,9 @@ static bool bm_vert_pair_share_best_splittable_face_cb(BMFace *f,
     }
   }
 
-  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;
+  const float test_edgenet_range_on_face_normal = max - min;
+  if (test_edgenet_range_on_face_normal < data->best_edgenet_range_on_face_normal) {
+    data->best_edgenet_range_on_face_normal = test_edgenet_range_on_face_normal;
     data->r_best_face = f;
   }
 
@@ -111,114 +114,79 @@ static bool bm_vert_pair_share_splittable_face_cb(BMFace *UNUSED(f),
   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)) {
+  const float range_min = -FLT_EPSILON;
+  const float range_max = 1.0f + FLT_EPSILON;
+
+  float co[3];
+  float dir[3];
+  float lambda_a;
+  float lambda_b;
+
+  copy_v3_v3(co, l_a->prev->v->co);
+  sub_v3_v3v3(dir, l_a->next->v->co, co);
+  if (isect_ray_ray_v3(v_a_co, v_a_b_dir, co, dir, &lambda_a, &lambda_b)) {
+    if (IN_RANGE(lambda_a, range_min, range_max) && IN_RANGE(lambda_b, range_min, range_max)) {
       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);
+    else {
+      copy_v3_v3(co, l_b->prev->v->co);
+      sub_v3_v3v3(dir, l_b->next->v->co, co);
+      if (isect_ray_ray_v3(v_a_co, v_a_b_dir, co, dir, &lambda_a, &lambda_b)) {
+        return IN_RANGE(lambda_a, range_min, range_max) &&
+               IN_RANGE(lambda_b, range_min, range_max);
+      }
     }
   }
   return false;
 }
 
-void BM_vert_weld_linked_wire_edges_into_linked_faces(
-    BMesh *bm, BMVert *v, const float epsilon, BMEdge **r_edgenet[], int *r_edgenet_alloc_len)
+static BMFace *bm_vert_pair_best_face_get(
+    BMVert *v_a, BMVert *v_b, BMEdge **edgenet, const int edgenet_len, const float epsilon)
 {
-  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;
+  BMFace *r_best_face = NULL;
 
-  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, bm_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, bm_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;
-          }
+  BMLoop *dummy;
+  if (edgenet_len == 1) {
+    float data[2][3];
+    copy_v3_v3(data[0], v_b->co);
+    sub_v3_v3v3(data[1], v_a->co, data[0]);
+    r_best_face = BM_vert_pair_shared_face_cb(
+        v_a, v_b, false, bm_vert_pair_share_splittable_face_cb, &data, &dummy, &dummy);
+  }
+  else {
+    struct EDBMSplitBestFaceData data = {
+        .edgenet = edgenet,
+        .edgenet_len = edgenet_len,
+        .best_edgenet_range_on_face_normal = FLT_MAX,
+        .r_best_face = NULL,
+    };
+    BM_vert_pair_shared_face_cb(
+        v_a, v_b, true, bm_vert_pair_share_best_splittable_face_cb, &data, &dummy, &dummy);
+
+    if (data.r_best_face) {
+      /* Check if the edgenet's range is smaller than the face's range. */
+      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;
         }
-        float range = max - min + 2 * epsilon;
-        if (range < data.best_face_range_on_normal_axis) {
-          data.r_best_face = NULL;
+        if (dot > max) {
+          max = dot;
         }
       }
-      best_face = data.r_best_face;
-    }
-
-    if (best_face) {
-      BM_face_split_edgenet(bm, best_face, edgenet, edgenet_len, NULL, NULL);
+      float face_range_on_normal = max - min + 2 * epsilon;
+      if (face_range_on_normal < data.best_edgenet_range_on_face_normal) {
+        data.r_best_face = NULL;
+      }
     }
+    r_best_face = data.r_best_face;
   }
 
-  *r_edgenet = edgenet;
-  *r_edgenet_alloc_len = edgenet_alloc_len;
+  return r_best_face;
 }
 
 /** \} */
@@ -517,7 +485,8 @@ static int sort_cmp_by_lambda_cb(const void *index1_v, const void *index2_v, voi
 
 #define INTERSECT_EDGES
 
-bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHash *r_targetmap)
+bool BM_mesh_intersect_edges(
+    BMesh *bm, const char hflag, const float dist, const bool split_faces, GHash *r_targetmap)
 {
   bool ok = false;
 
@@ -560,6 +529,9 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas
         verts_remain_len++;
       }
     }
+
+    /* The index will indicate which cut in pair_array this vertex belongs to. */
+    BM_elem_index_set(v, -1);
   }
   bm->elem_index_dirty |= BM_VERT;
 
@@ -621,6 +593,10 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas
       /* Don't test hidden edges or smaller than the minimum distance.
        * These have already been handled in the vertices overlap. */
       BM_elem_index_set(e, 0);
+      if (split_faces) {
+        /* Tag to be ignored. */
+        BM_elem_flag_enable(e, BM_ELEM_TAG);
+      }
       continue;
     }
 
@@ -631,6 +607,10 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas
     else {
       BM_elem_index_set(e, EDGE_REMAIN_TO_TEST);
       edges_remain_len++;
+      if (split_faces) {
+        /* Tag to be ignored. */
+        BM_elem_flag_enable(e, BM_ELEM_TAG);
+      }
     }
   }
 
@@ -823,6 +803,11 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas
           lambda = (pair_elem->lambda - lambda_prev) / (1.0f - lambda_prev);
           lambda_prev = pair_elem->lambda;
           e = pair_elem->edge;
+          if (split_faces) {
+            /* Tagged edges are ignored when split faces.
+            /* Untag these. */
+            BM_elem_flag_disable(e, BM_ELEM_TAG);
+          }
 
           BMVert *v_new = BM_edge_split(bm, e, e->v1, NULL, lambda);
           pair_elem->vert = v_new;
@@ -856,10 +841,136 @@ bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHas
         BLI_assert((*pair_iter)[0].elem->head.htype == BM_VERT);
         BLI_assert((*pair_iter)[1].elem->head.htype == BM_VERT);
         BLI_assert((*pair_iter)[0].elem != (*pair_iter)[1].elem);
-
-        BLI_ghash_insert(r_targetmap, (*pair_iter)[0].vert, (*pair_iter)[1].vert);
+        BMVert *v_key, *v_val;
+        v_key = (*pair_iter)[0].vert;
+        v_val = (*pair_iter)[1].vert;
+        BLI_ghash_insert(r_targetmap, v_key, v_val);
+        if (split_faces) {
+          BM_elem_index_set(v_key, i * 2);
+          BM_elem_index_set(v_val, i * 2 + 1);
+        }
       }
 
+      if (split_faces) {
+        BMEdge **edgenet = NULL;
+        int edgenet_alloc_len = 0;
+
+        struct EDBMSplitElem *pair_flat = (struct EDBMSplitElem *)&pair_array[0];
+        BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+          if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
+            continue;
+          }
+          BM_elem_flag_enable(e, BM_ELEM_TAG);
+
+          BMVert *va, *vb, *va_dest = NULL;
+          va = e->v1;
+          vb = e->v2;
+
+          int v_cut = BM_elem_index_get(va);
+          int v_cut_other = BM_elem_index_get(vb);
+          if (v_cut == -1 && v_cut_other == -1) {
+            continue;
+          }
+
+          if (v_cut == -1) {
+            SWAP(BMVert *, va, vb);
+            v_cut = v_cut_other;
+            v_cut_other = -1;
+          }
+
+          v_cut += v_cut % 2 ? -1 : 1;
+          va_dest = pair_flat[v_cut].vert;
+
+          BMFace *best_face = NULL;
+          int edgenet_len = 0;
+          BMVert *v_other_dest, *v_other = vb;
+          BMEdge *e_net = e;
+          while (true) {
+            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_net;
+
+            if (v_cut_other != -1) {
+              v_cut_other += v_cut_other % 2 ? -1 : 1;
+              v_other_dest = pair_flat[v_cut_other].vert;
+            }
+            else {
+              v_other_dest = v_other;
+            }
+
+            best_face = bm_vert_pair_best_face_get(
+                va_dest, v_other_dest, edgenet, edgenet_len, dist);
+
+            if (best_face) {
+              if (va_dest != va) {
+                e_net = edgenet[0];
+                if (edgenet_len > 1) {
+                  vb = BM_edge_other_vert(e_net, va);
+                }
+                else {
+                  vb = v_other_dest;
+                }
+                edgenet[0] = BM_edge_create(bm, va_dest, vb, e_net, BM_CREATE_NOP);
+              }
+              if ((edgenet_len > 1) && (v_other_dest != v_other)) {
+                e_net = edgenet[edgenet_len - 1];
+                edgenet[edgenet_len - 1] = BM_edge_create(
+                    bm, v_other_dest, BM_edge_other_vert(e_net, v_other), e_net, BM_CREATE_NOP);
+              }
+              break;
+            }
+
+            BMEdge *e_test = e_net, *e_next = NULL;
+            while ((e_test = BM_DISK_EDGE_NEXT(e_test, v_other)) != (e_net)) {
+              if (!BM_edge_is_wire(e_test)) {
+                if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
+                  continue;
+                }
+                if (BM_elem_index_get(e_test->v1) == -1 && BM_elem_index_get(e_test->v2) == -1) {
+                  continue;
+                }
+              }
+              else if (!BM_edge_is_wire(e_net)) {
+                continue;
+              }
+              e_next = e_test;
+              break;
+            }
+
+            if (e_next == NULL) {
+              break;
+            }
+
+            e_net = e_next;
+            v_other = BM_edge_other_vert(e_net, v_other);
+            if (v_other == va) {
+              /* Endless loop. */
+              break;
+            }
+            v_cut_other = BM_elem_index_get(v_other);
+          }
+
+          if (best_face) {
+            BMFace **face_arr = NULL;
+            int face_arr_len = 0;
+            BM_face_split_edgenet(bm, best_face, edgenet, edgenet_len, &face_arr, &face_arr_len);
+            if (face_arr) {
+              /* Update the new faces normal.
+               * Normal is necessary to obtain the best face for edgenet */
+              while (face_arr_len--) {
+                BM_face_normal_update(face_arr[face_arr_len]);
+              }
+              MEM_freeN(face_arr);
+            }
+          }
+        }
+
+        if (edgenet) {
+          MEM_freeN(edgenet);
+        }
+      }
       ok = true;
     }
   }
diff --git a/source/blender/bmesh/tools/bmesh_intersect_edges.h b/source/blender/bmesh/tools/bmesh_intersect_edges.h
index a22a1ca1e1d..7e2252250d6 100644
--- a/source/blender/bmesh/tools/bmesh_intersect_edges.h
+++ b/source/blender/bmesh/tools/bmesh_intersect_edges.h
@@ -21,9 +21,7 @@
 #ifndef __BMESH_INTERSECT_EDGES_H__
 #define __BMESH_INTERSECT_EDGES_H__
 
-void BM_vert_weld_linked_wire_edges_into_linked_faces(
-    BMesh *bm, BMVert *v, const float epsilon, BMEdge **r_edgenet[], int *r_edgenet_alloc_len);
-
-bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHash *r_targetmap);
+bool BM_mesh_intersect_edges(
+    BMesh *bm, const char hflag, const float dist, const bool split_faces, GHash *r_targetmap);
 
 #endif /* __BMESH_INTERSECT_EDGES_H__ */