diff options
Diffstat (limited to 'source/blender/bmesh/intern/bmesh_queries.c')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.c | 309 |
1 files changed, 195 insertions, 114 deletions
diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index b5b6c69bd7e..7ed23aaf1f8 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -43,7 +43,7 @@ * Returns whether or not a given vertex is * is part of a given edge. */ -int BM_vert_in_edge(BMEdge *e, BMVert *v) +bool BM_vert_in_edge(BMEdge *e, BMVert *v) { return bmesh_vert_in_edge(e, v); } @@ -208,9 +208,9 @@ BMLoop *BM_vert_find_first_loop(BMVert *v) } /** - * Returns TRUE if the vertex is used in a given face. + * Returns true if the vertex is used in a given face. */ -int BM_vert_in_face(BMFace *f, BMVert *v) +bool BM_vert_in_face(BMFace *f, BMVert *v) { BMLoop *l_iter, *l_first; @@ -226,19 +226,19 @@ int BM_vert_in_face(BMFace *f, BMVert *v) #endif do { if (l_iter->v == v) { - return TRUE; + return true; } } while ((l_iter = l_iter->next) != l_first); } - return FALSE; + return false; } /** * Compares the number of vertices in an array * that appear in a given face */ -int BM_verts_in_face(BMFace *f, BMVert **varr, int len) +int BM_verts_in_face_count(BMFace *f, BMVert **varr, int len) { BMLoop *l_iter, *l_first; @@ -278,10 +278,64 @@ int BM_verts_in_face(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. */ -int BM_edge_in_face(BMFace *f, BMEdge *e) +bool BM_edge_in_face(BMFace *f, BMEdge *e) { BMLoop *l_iter; BMLoop *l_first; @@ -290,17 +344,17 @@ int BM_edge_in_face(BMFace *f, BMEdge *e) do { if (l_iter->e == e) { - return TRUE; + return true; } } while ((l_iter = l_iter->next) != l_first); - return FALSE; + return false; } /** * Returns whether or not a given edge is is part of a given loop. */ -int BM_edge_in_loop(BMEdge *e, BMLoop *l) +bool BM_edge_in_loop(BMEdge *e, BMLoop *l) { return (l->e == e || l->prev->e == e); } @@ -309,7 +363,7 @@ int BM_edge_in_loop(BMEdge *e, BMLoop *l) * Returns whether or not two vertices are in * a given edge */ -int BM_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e) +bool BM_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e) { return bmesh_verts_in_edge(v1, v2, e); } @@ -487,9 +541,9 @@ float BM_edge_calc_length_squared(BMEdge *e) * Utility function, since enough times we have an edge * and want to access 2 connected faces. * - * \return TRUE when only 2 faces are found. + * \return true when only 2 faces are found. */ -int BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb) +bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb) { BMLoop *la, *lb; @@ -500,12 +554,12 @@ int BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb) { *r_fa = la->f; *r_fb = lb->f; - return TRUE; + return true; } else { *r_fa = NULL; *r_fb = NULL; - return FALSE; + return false; } } @@ -513,9 +567,9 @@ int BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb) * Utility function, since enough times we have an edge * and want to access 2 connected loops. * - * \return TRUE when only 2 faces are found. + * \return true when only 2 faces are found. */ -int BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb) +bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb) { BMLoop *la, *lb; @@ -526,12 +580,12 @@ int BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb) { *r_la = la; *r_lb = lb; - return TRUE; + return true; } else { *r_la = NULL; *r_lb = NULL; - return FALSE; + return false; } } @@ -589,7 +643,7 @@ int BM_vert_face_count(BMVert *v) * Tests whether or not the vertex is part of a wire edge. * (ie: has no faces attached to it) */ -int BM_vert_is_wire(BMVert *v) +bool BM_vert_is_wire(BMVert *v) { if (v->e) { BMEdge *e_first, *e_iter; @@ -597,14 +651,14 @@ int BM_vert_is_wire(BMVert *v) e_first = e_iter = v->e; do { if (e_iter->l) { - return FALSE; + return false; } } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first); - return TRUE; + return true; } else { - return FALSE; + return false; } } @@ -612,9 +666,9 @@ int BM_vert_is_wire(BMVert *v) * Tests whether or not the edge is part of a wire. * (ie: has no faces attached to it) */ -int BM_edge_is_wire(BMEdge *e) +bool BM_edge_is_wire(BMEdge *e) { - return (e->l) ? FALSE : TRUE; + return (e->l == NULL); } /** @@ -624,7 +678,7 @@ int BM_edge_is_wire(BMEdge *e) * 3: Is part of a an edge with more than 2 faces. * 4: Is part of a wire edge. */ -int BM_vert_is_manifold(BMVert *v) +bool BM_vert_is_manifold(BMVert *v) { BMEdge *e, *oe; BMLoop *l; @@ -632,7 +686,7 @@ int BM_vert_is_manifold(BMVert *v) if (v->e == NULL) { /* loose vert */ - return FALSE; + return false; } /* count edges while looking for non-manifold edges */ @@ -643,7 +697,7 @@ int BM_vert_is_manifold(BMVert *v) * edges with 1 face user are OK, otherwise we could * use BM_edge_is_manifold() here */ if (e->l == NULL || bmesh_radial_length(e->l) > 2) { - return FALSE; + return false; } len++; } while ((e = bmesh_disk_edge_next(e, v)) != oe); @@ -677,10 +731,10 @@ int BM_vert_is_manifold(BMVert *v) if (count < len) { /* vert shared by multiple regions */ - return FALSE; + return false; } - return TRUE; + return true; } /** @@ -689,7 +743,7 @@ int BM_vert_is_manifold(BMVert *v) */ #if 1 /* fast path for checking manifold */ -int BM_edge_is_manifold(BMEdge *e) +bool BM_edge_is_manifold(BMEdge *e) { const BMLoop *l = e->l; return (l && (l->radial_next != l) && /* not 0 or 1 face users */ @@ -700,10 +754,10 @@ int BM_edge_is_manifold(BMEdge *e) { int count = BM_edge_face_count(e); if (count == 2) { - return TRUE; + return true; } else { - return FALSE; + return false; } } #endif @@ -714,7 +768,7 @@ int BM_edge_is_manifold(BMEdge *e) */ #if 1 /* fast path for checking boundary */ -int BM_edge_is_boundary(BMEdge *e) +bool BM_edge_is_boundary(BMEdge *e) { const BMLoop *l = e->l; return (l && (l->radial_next == l)); @@ -724,10 +778,10 @@ int BM_edge_is_boundary(BMEdge *e) { int count = BM_edge_face_count(e); if (count == 1) { - return TRUE; + return true; } else { - return FALSE; + return false; } } #endif @@ -757,7 +811,7 @@ int BM_face_share_face_count(BMFace *f1, BMFace *f2) /** * same as #BM_face_share_face_count but returns a bool */ -int BM_face_share_face_check(BMFace *f1, BMFace *f2) +bool BM_face_share_face_check(BMFace *f1, BMFace *f2) { BMIter iter1, iter2; BMEdge *e; @@ -766,11 +820,11 @@ int BM_face_share_face_check(BMFace *f1, BMFace *f2) BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) { BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) { if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2)) - return TRUE; + return true; } } - return FALSE; + return false; } /** @@ -793,9 +847,9 @@ int BM_face_share_edge_count(BMFace *f1, BMFace *f2) } /** - * Returns TRUE if the faces share an edge + * Returns true if the faces share an edge */ -int BM_face_share_edge_check(BMFace *f1, BMFace *f2) +bool BM_face_share_edge_check(BMFace *f1, BMFace *f2) { BMLoop *l_iter; BMLoop *l_first; @@ -803,17 +857,17 @@ int BM_face_share_edge_check(BMFace *f1, BMFace *f2) l_iter = l_first = BM_FACE_FIRST_LOOP(f1); do { if (bmesh_radial_face_find(l_iter->e, f2)) { - return TRUE; + return true; } } while ((l_iter = l_iter->next) != l_first); - return FALSE; + return false; } /** - * Test if e1 shares any faces with e2 + * Test if e1 shares any faces with e2 */ -int BM_edge_share_face_check(BMEdge *e1, BMEdge *e2) +bool BM_edge_share_face_check(BMEdge *e1, BMEdge *e2) { BMLoop *l; BMFace *f; @@ -823,18 +877,18 @@ int BM_edge_share_face_check(BMEdge *e1, BMEdge *e2) do { f = l->f; if (bmesh_radial_face_find(e2, f)) { - return TRUE; + return true; } l = l->radial_next; } while (l != e1->l); } - return FALSE; + return false; } /** * Test if e1 shares any quad faces with e2 */ -int BM_edge_share_quad_check(BMEdge *e1, BMEdge *e2) +bool BM_edge_share_quad_check(BMEdge *e1, BMEdge *e2) { BMLoop *l; BMFace *f; @@ -845,19 +899,19 @@ int BM_edge_share_quad_check(BMEdge *e1, BMEdge *e2) f = l->f; if (f->len == 4) { if (bmesh_radial_face_find(e2, f)) { - return TRUE; + return true; } } l = l->radial_next; } while (l != e1->l); } - return FALSE; + return false; } /** * Tests to see if e1 shares a vertex with e2 */ -int BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2) +bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2) { return (e1->v1 == e2->v1 || e1->v1 == e2->v2 || @@ -1007,7 +1061,7 @@ void BM_loop_calc_face_tangent(BMLoop *l, float r_tangent[3]) normalize_v3(v_prev); normalize_v3(v_next); - if (compare_v3v3(v_prev, v_next, FLT_EPSILON) == FALSE) { + if (compare_v3v3(v_prev, v_next, FLT_EPSILON) == false) { float dir[3]; float nor[3]; /* for this purpose doesn't need to be normalized */ add_v3_v3v3(dir, v_prev, v_next); @@ -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. */ -int 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(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; + return true; } } } - if (r_overlapface) { - *r_overlapface = NULL; + if (r_existface) { + *r_existface = NULL; } + return false; - return FALSE; -} +#else -/** - * Given a set of vertices (varr), find out if - * there is a face with exactly those vertices - * (and only those vertices). - */ -int BM_face_exists(BMVert **varr, int len, BMFace **r_existface) -{ - BMIter viter; - BMFace *f; - int i, amount; + /* faster to do the flagging once, and inline */ + bool is_init = false; + bool is_found = false; + int i; - for (i = 0; i < len; i++) { - BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) { - amount = BM_verts_in_face(f, varr, len); - if (amount == len && amount == f->len) { + + 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 } @@ -1349,12 +1430,12 @@ int BM_face_exists(BMVert **varr, int len, BMFace **r_existface) * * \a earr and \a varr can be in any order, however they _must_ form a closed loop. */ -int BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len) +bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len) { BMFace *f; BMEdge *e; BMVert *v; - int ok; + bool ok; int tot_tag; BMIter fiter; @@ -1394,10 +1475,10 @@ int BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len) for (i = 0; i < len; i++) { BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) { if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) { - ok = TRUE; + ok = true; BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) { if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) { - ok = FALSE; + ok = false; break; } } @@ -1416,20 +1497,20 @@ int BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len) if (tot_tag == 0) { /* no faces use only boundary verts, quit early */ - return FALSE; + return false; } /* 2) loop over non-boundary edges that use boundary verts, * check each have 2 tagges faces connected (faces that only use 'varr' verts) */ - ok = TRUE; + ok = true; for (i = 0; i < len; i++) { BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) { if (/* non-boundary edge */ - BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == FALSE && + BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == false && /* ...using boundary verts */ - BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == TRUE && - BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == TRUE) + BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == true && + BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == true) { int tot_face_tag = 0; BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) { @@ -1439,14 +1520,14 @@ int BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len) } if (tot_face_tag != 2) { - ok = FALSE; + ok = false; break; } } } - if (ok == FALSE) { + if (ok == false) { break; } } @@ -1455,25 +1536,25 @@ int BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len) } /* same as 'BM_face_exists_multi' but built vert array from edges */ -int BM_face_exists_multi_edge(BMEdge **earr, int len) +bool BM_face_exists_multi_edge(BMEdge **earr, int len) { BMVert **varr = BLI_array_alloca(varr, len); - int ok; + bool ok; int i, i_next; /* first check if verts have edges, if not we can bail out early */ - ok = TRUE; + ok = true; for (i = len - 1, i_next = 0; i_next < len; (i = i_next++)) { if (!(varr[i] = BM_edge_share_vert(earr[i], earr[i_next]))) { - ok = FALSE; + ok = false; break; } } - if (ok == FALSE) { + if (ok == false) { BMESH_ASSERT(0); - return FALSE; + return false; } ok = BM_face_exists_multi(varr, earr, len); @@ -1482,13 +1563,13 @@ int BM_face_exists_multi_edge(BMEdge **earr, int len) } /* convenience functions for checking flags */ -int BM_edge_is_any_vert_flag_test(BMEdge *e, const char hflag) +bool BM_edge_is_any_vert_flag_test(BMEdge *e, const char hflag) { return (BM_elem_flag_test(e->v1, hflag) || BM_elem_flag_test(e->v2, hflag)); } -int BM_face_is_any_vert_flag_test(BMFace *f, const char hflag) +bool BM_face_is_any_vert_flag_test(BMFace *f, const char hflag) { BMLoop *l_iter; BMLoop *l_first; @@ -1496,13 +1577,13 @@ int BM_face_is_any_vert_flag_test(BMFace *f, const char hflag) l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { if (BM_elem_flag_test(l_iter->v, hflag)) { - return TRUE; + return true; } } while ((l_iter = l_iter->next) != l_first); - return FALSE; + return false; } -int BM_face_is_any_edge_flag_test(BMFace *f, const char hflag) +bool BM_face_is_any_edge_flag_test(BMFace *f, const char hflag) { BMLoop *l_iter; BMLoop *l_first; @@ -1510,8 +1591,8 @@ int BM_face_is_any_edge_flag_test(BMFace *f, const char hflag) l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { if (BM_elem_flag_test(l_iter->e, hflag)) { - return TRUE; + return true; } } while ((l_iter = l_iter->next) != l_first); - return FALSE; + return false; } |