Improvements to bmesh edge rotate
authorCampbell Barton <ideasman42@gmail.com>
Mon, 5 Mar 2012 00:50:18 +0000 (00:50 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Mon, 5 Mar 2012 00:50:18 +0000 (00:50 +0000)
On a user level, edge rotate now works better with multiple edges selected, it wont make zero area faces or rotate edges into existing ones.

With a single edge selected - rotate is less strict and will allow ugly resulting faces but still checks on duplicate edges.

API:
* BM_edge_rotate now takes a flag, to optionally...
** check for existing edge
** splice edge (rotate and merge)
** check for degenerate resulting faces (overlapping geometry, zero area)
** beauty - only rotate to a better fit.
... this allows it to still be used as a low level API function since all checks can be skipped.

* BM_edge_rotate() now works a bit different, it find the new edge rotation before joining the faces - exposed by BM_edge_rotate_calc().

* Added api call bmesh_radial_faceloop_find_vert() - Radial Find a Vertex Loop in Face

source/blender/bmesh/intern/bmesh_core.c
source/blender/bmesh/intern/bmesh_core.h
source/blender/bmesh/intern/bmesh_mods.c
source/blender/bmesh/intern/bmesh_mods.h
source/blender/bmesh/intern/bmesh_structure.c
source/blender/bmesh/intern/bmesh_structure.h
source/blender/bmesh/operators/bmo_triangulate.c
source/blender/bmesh/operators/bmo_utils.c
source/blender/python/bmesh/bmesh_py_utils.c

index dd5edca..97a7cb4 100644 (file)
@@ -41,7 +41,7 @@
  * TESTING ONLY! */
 // #define USE_DEBUG_INDEX_MEMCHECK
 
-static int bm_edge_splice(BMesh *bm, BMEdge *e, BMEdge *etarget);
+int BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *etarget);
 
 #ifdef USE_DEBUG_INDEX_MEMCHECK
 #define DEBUG_MEMCHECK_INDEX_INVALIDATE(ele)               \
@@ -1523,7 +1523,7 @@ BMEdge *bmesh_jekv(BMesh *bm, BMEdge *ke, BMVert *kv, const short check_edge_dou
                        if (check_edge_double) {
                                if (e_splice) {
                                        /* removes e_splice */
-                                       bm_edge_splice(bm, e_splice, oe);
+                                       BM_edge_splice(bm, e_splice, oe);
                                }
                        }
 
@@ -1845,7 +1845,7 @@ static int bm_vert_cut(BMesh *bm, BMVert *v, BMVert ***vout, int *len)
  *
  * \note Edges must already have the same vertices.
  */
-static int bm_edge_splice(BMesh *bm, BMEdge *e, BMEdge *etarget)
+int BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *etarget)
 {
        BMLoop *l;
 
index bfdb17e..82731c1 100644 (file)
@@ -40,6 +40,8 @@ void BM_face_kill(BMesh *bm, BMFace *f);
 void BM_edge_kill(BMesh *bm, BMEdge *e);
 void BM_vert_kill(BMesh *bm, BMVert *v);
 
+int  BM_edge_splice(BMesh *bm, BMEdge *e, BMEdge *etarget);
+
 int  bmesh_loop_reverse(BMesh *bm, BMFace *f);
 
 BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface);
index 3a42645..462b0cc 100644 (file)
@@ -708,6 +708,50 @@ int BM_face_validate(BMesh *bm, BMFace *face, FILE *err)
        return ret;
 }
 
+
+/**
+ * Calculate the 2 loops which _would_ make up the newly rotated Edge
+ * but don't actually change anything.
+ *
+ * Use this to further inspect if the loops to be connected have issues:
+ *
+ * Examples:
+ * - the newly formed edge already exists
+ * - the new face would be degenerate (zero area / concav /  bow-tie)
+ * - may want to measure if the new edge gives improved results topology.
+ *   over the old one, as with beauty fill.
+ *
+ * \note #BM_edge_rotate_check must have already run.
+ */
+void BM_edge_rotate_calc(BMesh *bm, BMEdge *e, int ccw,
+                         BMLoop **r_l1, BMLoop **r_l2)
+{
+       BMVert *v1, *v2;
+       BMFace *fa, *fb;
+
+       /* this should have already run */
+       BLI_assert(BM_edge_rotate_check(bm, e) == TRUE);
+
+       /* we know this will work */
+       BM_edge_face_pair(e, &fa, &fb);
+
+       /* so we can use ccw variable correctly,
+        * otherwise we could use the egdes verts direct */
+       BM_edge_ordered_verts(e, &v1, &v2);
+
+       /* we could swap the verts _or_ the faces, swapping faces
+        * gives more pradictable resuts since that way the next vert
+        * just sitches from face fa / fb */
+       if (ccw) {
+               SWAP(BMFace *, fa, fb);
+       }
+
+
+
+       *r_l1 = BM_face_other_vert_loop(fb, v2, v1);
+       *r_l2 = BM_face_other_vert_loop(fa, v1, v2);
+}
+
 /**
  * \brief Check if Rotate Edge is OK
  *
@@ -745,6 +789,115 @@ int BM_edge_rotate_check(BMesh *UNUSED(bm), BMEdge *e)
        }
 }
 
+/**
+ * \brief Check if Edge Rotate Gives Degenerate Faces
+ *
+ * Check 2 cases
+ * 1) does the newly forms edge form a flipped face (compare with previous cross product)
+ * 2) does the newly formed edge caise a zero area corner (or close enough to be almost zero)
+ *
+ * \param l1,l2 are the loops of the proposed verts to rotate too and should
+ * be the result of calling #BM_edge_rotate_calc
+ */
+int BM_edge_rotate_check_degenerate(BMesh *bm, BMEdge *e,
+                                    BMLoop *l1, BMLoop *l2)
+{
+       /* note: for these vars 'old' just means initial edge state. */
+
+       float ed_dir_old[3]; /* edge vector */
+       float ed_dir_new[3]; /* edge vector */
+       float ed_dir_new_flip[3]; /* edge vector */
+
+       float ed_dir_v1_old[3];
+       float ed_dir_v2_old[3];
+
+       float ed_dir_v1_new[3];
+       float ed_dir_v2_new[3];
+
+       float cross_old[3];
+       float cross_new[3];
+
+       /* original verts - these will be in the edge 'e' */
+       BMVert *v1_old, *v2_old;
+
+       /* verts from the loops passed */
+
+       BMVert *v1, *v2;
+       /* these are the opposite verts - the verts that _would_ be used if 'ccw' was inverted*/
+       BMVert *v1_alt, *v2_alt;
+
+       /* this should have already run */
+       BLI_assert(BM_edge_rotate_check(bm, e) == TRUE);
+
+       BM_edge_ordered_verts(e, &v1_old, &v2_old);
+
+       v1 = l1->v;
+       v2 = l2->v;
+
+       /* get the next vert along */
+       v1_alt = BM_face_other_vert_loop(l1->f, v1_old, v1)->v;
+       v2_alt = BM_face_other_vert_loop(l2->f, v2_old, v2)->v;
+
+       /* normalize all so comparisons are scale independent */
+
+       BLI_assert(BM_edge_exists(v1_old, v1));
+       BLI_assert(BM_edge_exists(v1, v1_alt));
+
+       BLI_assert(BM_edge_exists(v2_old, v2));
+       BLI_assert(BM_edge_exists(v2, v2_alt));
+
+       /* old and new edge vecs */
+       sub_v3_v3v3(ed_dir_old, v1_old->co, v2_old->co);
+       sub_v3_v3v3(ed_dir_new, v1->co, v2->co);
+       normalize_v3(ed_dir_old);
+       normalize_v3(ed_dir_new);
+
+       /* old edge corner vecs */
+       sub_v3_v3v3(ed_dir_v1_old, v1_old->co, v1->co);
+       sub_v3_v3v3(ed_dir_v2_old, v2_old->co, v2->co);
+       normalize_v3(ed_dir_v1_old);
+       normalize_v3(ed_dir_v2_old);
+
+       /* old edge corner vecs */
+       sub_v3_v3v3(ed_dir_v1_new, v1->co, v1_alt->co);
+       sub_v3_v3v3(ed_dir_v2_new, v2->co, v2_alt->co);
+       normalize_v3(ed_dir_v1_new);
+       normalize_v3(ed_dir_v2_new);
+
+       /* compare */
+       cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v1_old);
+       cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v1_new);
+       if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
+               return FALSE;
+       }
+       cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v2_old);
+       cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v2_new);
+       if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
+               return FALSE;
+       }
+
+       negate_v3_v3(ed_dir_new_flip, ed_dir_new);
+
+       /* result is zero area corner */
+       if ((dot_v3v3(ed_dir_new,      ed_dir_v1_new) > 0.999f) ||
+           (dot_v3v3(ed_dir_new_flip, ed_dir_v2_new) > 0.999f))
+       {
+               return FALSE;
+       }
+
+       return TRUE;
+}
+
+int BM_edge_rotate_check_beauty(BMesh *UNUSED(bm), BMEdge *e,
+                                BMLoop *l1, BMLoop *l2)
+{
+       /* Stupid check for now:
+        * Could compare angles of surrounding edges
+        * before & after, but this is OK.*/
+       return (len_squared_v3v3(e->v1->co, e->v2->co) >
+               len_squared_v3v3(l1->v->co, l2->v->co));
+}
+
 /**
  * \brief Rotate Edge
  *
@@ -756,45 +909,77 @@ int BM_edge_rotate_check(BMesh *UNUSED(bm), BMEdge *e)
  *
  * \note This works by dissolving the edge then re-creating it,
  * so the returned edge won't have the same pointer address as the original one.
+ *
+ * \see header definition for \a check_flag enum.
  */
-BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, int ccw)
+BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const short ccw, const short check_flag)
 {
        BMVert *v1, *v2;
-       BMLoop *l, *l1, *l2, *nl;
+       BMLoop *l1, *l2, *nl;
        BMFace *f;
-       BMIter liter;
+       BMEdge *e_splice = NULL;
 
        if (!BM_edge_rotate_check(bm, e)) {
                return NULL;
        }
 
-       v1 = e->v1;
-       v2 = e->v2;
+       BM_edge_rotate_calc(bm, e, ccw, &l1, &l2);
 
-       f = BM_faces_join_pair(bm, e->l->f, e->l->radial_next->f, e);
+       /* the loops will be freed so assign verts */
+       v1 = l1->v;
+       v2 = l2->v;
 
-       if (f == NULL)
-               return NULL;
 
-       BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
-               if (l->v == v1)
-                       l1 = l;
-               else if (l->v == v2)
-                       l2 = l;
+
+       /* --------------------------------------- */
+       /* Checking Code - make sure we can rotate */
+
+       if (check_flag & BM_EDGEROT_CHECK_BEAUTY) {
+               if (!BM_edge_rotate_check_beauty(bm, e, l1, l2)) {
+                       return NULL;
+               }
        }
-       
-       if (ccw) {
-               l1 = l1->prev;
-               l2 = l2->prev;
+
+       /* check before applying */
+       if (check_flag & BM_EDGEROT_CHECK_SPLICE) {
+               e_splice = BM_edge_exists(v1, v2);
        }
-       else {
-               l1 = l1->next;
-               l2 = l2->next;
+       else if (check_flag & BM_EDGEROT_CHECK_EXISTS) {
+               if (BM_edge_exists(v1, v2)) {
+                       return NULL;
+               }
+       }
+
+       /* slowest, check last */
+       if (check_flag & BM_EDGEROT_CHECK_DEGENERATE) {
+               if (!BM_edge_rotate_check_degenerate(bm, e, l1, l2)) {
+                       return NULL;
+               }
+       }
+       /* Done Checking */
+       /* ------------- */
+
+
+
+       /* rotate the edge */
+       f = BM_faces_join_pair(bm, l1->f, l2->f, e);
+
+       if (f == NULL) {
+               return NULL;
        }
 
-       if (!BM_face_split(bm, f, l1->v, l2->v, &nl, NULL))
+       /* note, this assumes joining the faces _didnt_ also remove the verts.
+        * the #BM_edge_rotate_check will ensure this, but its possibly corrupt state or future edits
+        * break this */
+
+       if (!BM_face_split(bm, f, v1, v2, &nl, NULL))
                return NULL;
 
+       /* replace existing edge (kill e_splice) */
+       if (e_splice) {
+               BM_edge_splice(bm, e_splice, nl->e);
+       }
+
        return nl->e;
 }
 
index d530e9d..f3344f2 100644 (file)
@@ -53,8 +53,23 @@ BMVert *BM_edge_split_n(BMesh *bm, BMEdge *e, int numcuts);
 
 int     BM_face_validate(BMesh *bm, BMFace *face, FILE *err);
 
+void    BM_edge_rotate_calc(BMesh *bm, BMEdge *e, int ccw,
+                                   BMLoop **r_l1, BMLoop **r_l2);
 int     BM_edge_rotate_check(BMesh *UNUSED(bm), BMEdge *e);
-BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, int ccw);
+int     BM_edge_rotate_check_degenerate(BMesh *bm, BMEdge *e,
+                                        BMLoop *l1, BMLoop *l2);
+int     BM_edge_rotate_check_beauty(BMesh *bm, BMEdge *e,
+                                    BMLoop *l1, BMLoop *l2);
+BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const short ccw, const short check_flag);
+
+/* flags for BM_edge_rotate */
+enum {
+       BM_EDGEROT_CHECK_EXISTS     = (1 << 0), /* disallow to rotate when the new edge matches an existing one */
+       BM_EDGEROT_CHECK_SPLICE     = (1 << 1), /* overrides existing check, if the edge already, rotate and merge them */
+       BM_EDGEROT_CHECK_DEGENERATE = (1 << 2), /* disallow creating bow-tie, concave or zero area faces */
+       BM_EDGEROT_CHECK_BEAUTY     = (1 << 3)  /* disallow to rotate into ugly topology */
+};
+
 
 BMVert *BM_vert_rip(BMesh *bm, BMFace *sf, BMVert *sv);
 
index ad6a8a6..abce778 100644 (file)
@@ -201,15 +201,13 @@ void bmesh_disk_edge_remove(BMEdge *e, BMVert *v)
        dl1->next = dl1->prev = NULL;
 }
 
-/*
- *                     bmesh_disk_edge_next
+/**
+ * \brief Next Disk Edge
  *
  *     Find the next edge in a disk cycle
  *
- *  Returns -
- *     Pointer to the next edge in the disk cycle for the vertex v.
+ *     \return Pointer to the next edge in the disk cycle for the vertex v.
  */
-
 BMEdge *bmesh_disk_edge_next(BMEdge *e, BMVert *v)
 {
        if (v == e->v1)
@@ -453,6 +451,27 @@ BMLoop *bmesh_radial_faceloop_find_next(BMLoop *l, BMVert *v)
        return l;
 }
 
+/* NOTE: this function has not been used or tested - so take care but it should work ok,
+ * I wrote it for some tool that ended up not using it, however this seems like a reasonable
+ * thing to be able to find the loop between a vertex and a face so keeping - campbell */
+/**
+ * \brief Radial Find a Vertex Loop in Face
+ *
+ * Finds the loop used which uses \a v in face loop \a l
+ */
+BMLoop *bmesh_radial_faceloop_find_vert(BMFace *f, BMVert *v) /* name is a bit awkward */
+{
+       BMLoop *l_iter, *l_first;
+       if (v->e && (l_iter = l_first = v->e->l)) {
+               do {
+                       if (l_iter->v == v && l_iter->f == f) {
+                               return l_iter;
+                       }
+               } while ((l_iter = l_iter->radial_next) != l_first);
+       }
+       return NULL;
+}
+
 int bmesh_radial_length(BMLoop *l)
 {
        BMLoop *l_iter = l;
index c3780a5..8b43f72 100644 (file)
@@ -64,6 +64,7 @@ int     bmesh_radial_face_find(BMEdge *e, BMFace *f);
 int     bmesh_radial_facevert_count(BMLoop *l, BMVert *v);
 BMLoop *bmesh_radial_faceloop_find_first(BMLoop *l, BMVert *v);
 BMLoop *bmesh_radial_faceloop_find_next(BMLoop *l, BMVert *v);
+BMLoop *bmesh_radial_faceloop_find_vert(BMFace *f, BMVert *v);
 int     bmesh_radial_validate(int radlen, BMLoop *l);
 
 /* EDGE UTILITIES */
index 2029d59..63837b7 100644 (file)
@@ -139,7 +139,7 @@ void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op)
                                fac2 = opp1 / (len2 + len3 + len6) + opp2 / (len4 + len1 + len6);
                                
                                if (fac1 > fac2) {
-                                       e = BM_edge_rotate(bm, e, FALSE);
+                                       e = BM_edge_rotate(bm, e, FALSE, BM_EDGEROT_CHECK_EXISTS);
                                        if (e) {
                                                BMO_elem_flag_enable(bm, e, ELE_NEW);
 
index 8e75d78..9aed578 100644 (file)
@@ -124,6 +124,10 @@ void bmo_edgerotate_exec(BMesh *bm, BMOperator *op)
        BMOIter siter;
        BMEdge *e, *e2;
        int ccw = BMO_slot_bool_get(op, "ccw");
+       int is_single = BMO_slot_buffer_count(bm, op, "edges") == 1;
+       short check_flag = is_single ?
+                   BM_EDGEROT_CHECK_EXISTS :
+                   BM_EDGEROT_CHECK_EXISTS | BM_EDGEROT_CHECK_DEGENERATE;
 
 #define EDGE_OUT   1
 #define FACE_TAINT 1
@@ -141,9 +145,12 @@ void bmo_edgerotate_exec(BMesh *bm, BMOperator *op)
                                    BMO_elem_flag_test(bm, fb, FACE_TAINT) == FALSE)
                                {
 
-                                       if (!(e2 = BM_edge_rotate(bm, e, ccw))) {
+                                       if (!(e2 = BM_edge_rotate(bm, e, ccw, check_flag))) {
+#if 0
                                                BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, "Could not rotate edge");
                                                return;
+#endif
+                                               continue;
                                        }
 
                                        BMO_elem_flag_enable(bm, e2, EDGE_OUT);
index a8d9052..83c75d7 100644 (file)
@@ -291,7 +291,7 @@ static PyObject *bpy_bm_utils_edge_rotate(PyObject *UNUSED(self), PyObject *args
 
        bm = py_edge->bm;
 
-       e_new = BM_edge_rotate(bm, py_edge->e, do_ccw);
+       e_new = BM_edge_rotate(bm, py_edge->e, do_ccw, 0); /* BMESH_TODO - expose to API */
 
        if (e_new) {
                return BPy_BMEdge_CreatePyObject(bm, e_new);