diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-01-14 22:37:58 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-01-14 22:37:58 +0400 |
commit | 2b7db66edf76a79c7abcf75f4bccafd17ecfeb37 (patch) | |
tree | 8da2aafd9bf15fd5cfd0e55b3961c15bbf7858a1 /source/blender/bmesh | |
parent | 8869c135e3ec917d6dfc69fac1cbb086b14f90e4 (diff) |
optimize BM_face_exists(), was doing a lot of redundant checks.
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.c | 155 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.h | 3 |
2 files changed, 119 insertions, 39 deletions
diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index 23d7af5277c..7ed23aaf1f8 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -278,6 +278,60 @@ int BM_verts_in_face_count(BMFace *f, BMVert **varr, int len) return count; } + +/** + * Return true if all verts are in the face. + */ +bool BM_verts_in_face(BMFace *f, BMVert **varr, int len) +{ + BMLoop *l_iter, *l_first; + +#ifdef USE_BMESH_HOLES + BMLoopList *lst; +#endif + + int i; + bool ok = true; + + /* simple check, we know can't succeed */ + if (f->len < len) { + return false; + } + + for (i = 0; i < len; i++) { + BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP); + } + +#ifdef USE_BMESH_HOLES + for (lst = f->loops.first; lst; lst = lst->next) +#endif + { + +#ifdef USE_BMESH_HOLES + l_iter = l_first = lst->first; +#else + l_iter = l_first = f->l_first; +#endif + + do { + if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) { + /* pass */ + } + else { + ok = false; + break; + } + + } while ((l_iter = l_iter->next) != l_first); + } + + for (i = 0; i < len; i++) { + BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP); + } + + return ok; +} + /** * Returns whether or not a given edge is is part of a given face. */ @@ -1273,67 +1327,94 @@ BMEdge *BM_edge_find_double(BMEdge *e) } /** - * Given a set of vertices \a varr, find out if - * all those vertices overlap an existing face. - * - * \note Making a face here is valid but in some cases you wont want to - * make a face thats part of another. - * - * \returns true for overlap + * Given a set of vertices (varr), find out if + * there is a face with exactly those vertices + * (and only those vertices). * + * \note there used to be a BM_face_exists_overlap function that checked for partial overlap, + * however this is no longer used, simple to add back. */ -bool BM_face_exists_overlap(BMVert **varr, int len, BMFace **r_overlapface) +bool BM_face_exists(BMVert **varr, int len, BMFace **r_existface) { + BMVert *v_search = varr[0]; /* we can search any of the verts in the array */ BMIter viter; BMFace *f; - int i, amount; - for (i = 0; i < len; i++) { - BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) { - amount = BM_verts_in_face_count(f, varr, len); - if (amount >= len) { - if (r_overlapface) { - *r_overlapface = f; + +#if 0 + BM_ITER_ELEM (f, &viter, v_search, BM_FACES_OF_VERT) { + if (f->len == len) { + if (BM_verts_in_face(f, varr, len)) { + if (r_existface) { + *r_existface = f; } return true; } } } - if (r_overlapface) { - *r_overlapface = NULL; + if (r_existface) { + *r_existface = NULL; } - return false; -} -/** - * Given a set of vertices (varr), find out if - * there is a face with exactly those vertices - * (and only those vertices). - */ -bool BM_face_exists(BMVert **varr, int len, BMFace **r_existface) -{ - BMIter viter; - BMFace *f; - int i, amount; +#else - for (i = 0; i < len; i++) { - BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) { - amount = BM_verts_in_face_count(f, varr, len); - if (amount == len && amount == f->len) { + /* faster to do the flagging once, and inline */ + bool is_init = false; + bool is_found = false; + int i; + + + BM_ITER_ELEM (f, &viter, v_search, BM_FACES_OF_VERT) { + if (f->len == len) { + if (is_init == false) { + is_init = true; + for (i = 0; i < len; i++) { + BLI_assert(!BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP)); + BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP); + } + } + + is_found = true; + + { + BMLoop *l_iter; + BMLoop *l_first; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + + do { + if (!BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) { + is_found = false; + break; + } + } while ((l_iter = l_iter->next) != l_first); + } + + if (is_found) { if (r_existface) { *r_existface = f; } - return true; + break; } } } - if (r_existface) { - *r_existface = NULL; + if (is_found == false) { + if (r_existface) { + *r_existface = NULL; + } } - return false; + + if (is_init == true) { + for (i = 0; i < len; i++) { + BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP); + } + } + + return is_found; +#endif } diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h index 4641fa86fb0..9892700162e 100644 --- a/source/blender/bmesh/intern/bmesh_queries.h +++ b/source/blender/bmesh/intern/bmesh_queries.h @@ -29,6 +29,7 @@ bool BM_vert_in_face(BMFace *f, BMVert *v); int BM_verts_in_face_count(BMFace *f, BMVert **varr, int len); +bool BM_verts_in_face(BMFace *f, BMVert **varr, int len); bool BM_edge_in_face(BMFace *f, BMEdge *e); bool BM_edge_in_loop(BMEdge *e, BMLoop *l); @@ -79,8 +80,6 @@ BMLoop *BM_face_find_longest_loop(BMFace *f); BMEdge *BM_edge_exists(BMVert *v1, BMVert *v2); BMEdge *BM_edge_find_double(BMEdge *e); -bool BM_face_exists_overlap(BMVert **varr, int len, BMFace **r_existface); - bool BM_face_exists(BMVert **varr, int len, BMFace **r_existface); bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len); |