BMesh: add check to BM_vert_pair_share_face to allow adjacent loops
authorCampbell Barton <ideasman42@gmail.com>
Tue, 13 May 2014 06:19:07 +0000 (16:19 +1000)
committerCampbell Barton <ideasman42@gmail.com>
Tue, 13 May 2014 06:49:57 +0000 (16:49 +1000)
Add BM_vert_pair_share_face_by_angle to avoid selecting concave splits.

source/blender/bmesh/intern/bmesh_queries.c
source/blender/bmesh/intern/bmesh_queries.h
source/blender/bmesh/operators/bmo_subdivide.c

index 67f333215d9a0696a23f26baa69cbd3be87dab62..61e1a15c60566a53c62b17528e1b0b6f3f80d098 100644 (file)
@@ -184,8 +184,10 @@ BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v)
 /**
  * Given 2 verts, find the smallest face they share and give back both loops.
  */
-BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b,
-                                BMLoop **r_l_a, BMLoop **r_l_b)
+BMFace *BM_vert_pair_share_face_by_len(
+        BMVert *v_a, BMVert *v_b,
+        BMLoop **r_l_a, BMLoop **r_l_b,
+        const bool allow_adjacent)
 {
        BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
        BMFace *f_cur = NULL;
@@ -197,7 +199,7 @@ BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b,
                BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
                        if ((f_cur == NULL) || (l_a->f->len < f_cur->len)) {
                                l_b = BM_face_vert_share_loop(l_a->f, v_b);
-                               if (l_b) {
+                               if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
                                        f_cur = l_a->f;
                                        l_cur_a = l_a;
                                        l_cur_b = l_b;
@@ -206,12 +208,80 @@ BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b,
                }
        }
 
-       if (r_l_a) *r_l_a = l_cur_a;
-       if (r_l_b) *r_l_b = l_cur_b;
+       *r_l_a = l_cur_a;
+       *r_l_b = l_cur_b;
 
        return f_cur;
 }
 
+static float bm_face_calc_split_dot(BMLoop *l_a, BMLoop *l_b)
+{
+       float no[2][3];
+
+       if ((BM_face_calc_normal_subset(l_a, l_b, no[0]) != 0.0f) &&
+           (BM_face_calc_normal_subset(l_b, l_a, no[1]) != 0.0f))
+       {
+               return dot_v3v3(no[0], no[1]);
+       }
+       else {
+               return -1.0f;
+       }
+}
+
+/**
+ * Given 2 verts, find a face they share that has the lowest angle across these verts and give back both loops.
+ *
+ * This can be better then #BM_vert_pair_share_face_by_len because concave splits are ranked lowest.
+ */
+BMFace *BM_vert_pair_share_face_by_angle(
+        BMVert *v_a, BMVert *v_b,
+        BMLoop **r_l_a, BMLoop **r_l_b,
+        const bool allow_adjacent)
+{
+       BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
+       BMFace *f_cur = NULL;
+
+       if (v_a->e && v_b->e) {
+               BMIter iter;
+               BMLoop *l_a, *l_b;
+               float dot_best = -1.0f;
+
+               BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
+                       l_b = BM_face_vert_share_loop(l_a->f, v_b);
+                       if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
+
+                               if (f_cur == NULL) {
+                                       f_cur = l_a->f;
+                                       l_cur_a = l_a;
+                                       l_cur_b = l_b;
+                               }
+                               else {
+                                       /* avoid expensive calculations if we only ever find one face */
+                                       float dot;
+                                       if (dot_best == -1.0f) {
+                                               dot_best = bm_face_calc_split_dot(l_cur_a, l_cur_b);
+                                       }
+
+                                       dot = bm_face_calc_split_dot(l_a, l_b);
+                                       if (dot > dot_best) {
+                                               dot_best = dot;
+
+                                               f_cur = l_a->f;
+                                               l_cur_a = l_a;
+                                               l_cur_b = l_b;
+                                       }
+                               }
+                       }
+               }
+       }
+
+       *r_l_a = l_cur_a;
+       *r_l_b = l_cur_b;
+
+       return f_cur;
+}
+
+
 /**
  * Get the first loop of a vert. Uses the same initialization code for the first loop of the
  * iterator API
index 36e67a73f1fc1089a6bb13a9e59419bc6e976adc..7db04a529eb683a183eb38d420f616446664f06c 100644 (file)
@@ -49,8 +49,15 @@ BMLoop *BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v);
 BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v);
 BMLoop *BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step);
 BMLoop *BM_vert_find_first_loop(BMVert *v);
-BMFace *BM_vert_pair_share_face(BMVert *v_a, BMVert *v_b,
-                                BMLoop **r_l_a, BMLoop **r_l_b);
+
+BMFace *BM_vert_pair_share_face_by_len(
+        BMVert *v_a, BMVert *v_b,
+        BMLoop **r_l_a, BMLoop **r_l_b,
+        const bool allow_adjacent) ATTR_NONNULL();
+BMFace *BM_vert_pair_share_face_by_angle(
+        BMVert *v_a, BMVert *v_b,
+        BMLoop **r_l_a, BMLoop **r_l_b,
+        const bool allow_adjacent) ATTR_NONNULL();
 
 int     BM_vert_edge_count_nonwire(BMVert *v);
 int     BM_vert_edge_count(BMVert *v);
index e0c86564db4f0965c645bf1d120a1591e4bdf03f..8d948fbcc698ee1a578093831ae733406c2acb07 100644 (file)
@@ -140,13 +140,19 @@ static BMEdge *connect_smallest_face(BMesh *bm, BMVert *v_a, BMVert *v_b, BMFace
 
        /* this isn't the best thing in the world.  it doesn't handle cases where there's
         * multiple faces yet.  that might require a convexity test to figure out which
-        * face is "best" and who knows what for non-manifold conditions. */
-       f = BM_vert_pair_share_face(v_a, v_b, &l_a, &l_b);
+        * face is "best" and who knows what for non-manifold conditions.
+        *
+        * note: we allow adjacent here, since theres no chance this happens.
+        */
+       f = BM_vert_pair_share_face_by_len(v_a, v_b, &l_a, &l_b, true);
+
 
        if (f) {
                BMFace *f_new;
                BMLoop *l_new;
 
+               BLI_assert(!BM_loop_is_adjacent(l_a, l_b));
+
                f_new = BM_face_split(bm, f, l_a, l_b, &l_new, NULL, false);
                
                if (r_f_new) *r_f_new = f_new;