diff options
author | Campbell Barton <ideasman42@gmail.com> | 2012-03-05 04:50:18 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2012-03-05 04:50:18 +0400 |
commit | 4d84e869a0fd540247a99edbfeca24ffb75644cd (patch) | |
tree | 09c2b88dce2b66316f5e17d969170fdfd0cffbbc | |
parent | 5f509134ec22102cb00fdc9a623798c149fa43a9 (diff) |
Improvements to bmesh edge rotate
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
-rw-r--r-- | source/blender/bmesh/intern/bmesh_core.c | 6 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_core.h | 2 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_mods.c | 227 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_mods.h | 17 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_structure.c | 29 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_structure.h | 1 | ||||
-rw-r--r-- | source/blender/bmesh/operators/bmo_triangulate.c | 2 | ||||
-rw-r--r-- | source/blender/bmesh/operators/bmo_utils.c | 9 | ||||
-rw-r--r-- | source/blender/python/bmesh/bmesh_py_utils.c | 2 |
9 files changed, 262 insertions, 33 deletions
diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c index dd5edcae583..97a7cb41eaa 100644 --- a/source/blender/bmesh/intern/bmesh_core.c +++ b/source/blender/bmesh/intern/bmesh_core.c @@ -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; diff --git a/source/blender/bmesh/intern/bmesh_core.h b/source/blender/bmesh/intern/bmesh_core.h index bfdb17e2a1e..82731c11cf4 100644 --- a/source/blender/bmesh/intern/bmesh_core.h +++ b/source/blender/bmesh/intern/bmesh_core.h @@ -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); diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c index 3a4264575f0..462b0cc2369 100644 --- a/source/blender/bmesh/intern/bmesh_mods.c +++ b/source/blender/bmesh/intern/bmesh_mods.c @@ -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 * @@ -746,6 +790,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 * * Spins an edge topologically, @@ -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; } diff --git a/source/blender/bmesh/intern/bmesh_mods.h b/source/blender/bmesh/intern/bmesh_mods.h index d530e9d8666..f3344f2d687 100644 --- a/source/blender/bmesh/intern/bmesh_mods.h +++ b/source/blender/bmesh/intern/bmesh_mods.h @@ -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); diff --git a/source/blender/bmesh/intern/bmesh_structure.c b/source/blender/bmesh/intern/bmesh_structure.c index ad6a8a615e3..abce7780e79 100644 --- a/source/blender/bmesh/intern/bmesh_structure.c +++ b/source/blender/bmesh/intern/bmesh_structure.c @@ -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; diff --git a/source/blender/bmesh/intern/bmesh_structure.h b/source/blender/bmesh/intern/bmesh_structure.h index c3780a5dede..8b43f72c725 100644 --- a/source/blender/bmesh/intern/bmesh_structure.h +++ b/source/blender/bmesh/intern/bmesh_structure.h @@ -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 */ diff --git a/source/blender/bmesh/operators/bmo_triangulate.c b/source/blender/bmesh/operators/bmo_triangulate.c index 2029d595af7..63837b7e087 100644 --- a/source/blender/bmesh/operators/bmo_triangulate.c +++ b/source/blender/bmesh/operators/bmo_triangulate.c @@ -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); diff --git a/source/blender/bmesh/operators/bmo_utils.c b/source/blender/bmesh/operators/bmo_utils.c index 8e75d7880ee..9aed578dccc 100644 --- a/source/blender/bmesh/operators/bmo_utils.c +++ b/source/blender/bmesh/operators/bmo_utils.c @@ -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); diff --git a/source/blender/python/bmesh/bmesh_py_utils.c b/source/blender/python/bmesh/bmesh_py_utils.c index a8d90522c15..83c75d775c1 100644 --- a/source/blender/python/bmesh/bmesh_py_utils.c +++ b/source/blender/python/bmesh/bmesh_py_utils.c @@ -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); |