2 * ***** BEGIN GPL LICENSE BLOCK *****
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 * Contributor(s): Joseph Eagar, Geoffrey Bantle, Campbell Barton
20 * ***** END GPL LICENSE BLOCK *****
23 /** \file blender/bmesh/intern/bmesh_queries.c
26 * This file contains functions for answering common
27 * Topological and geometric queries about a mesh, such
28 * as, "What is the angle between these two faces?" or,
29 * "How many faces are incident upon this vertex?" Tool
30 * authors should use the functions in this file instead
31 * of inspecting the mesh structure directly.
34 #include "MEM_guardedalloc.h"
36 #include "BLI_array.h"
40 #include "intern/bmesh_private.h"
42 #define BM_OVERLAP (1 << 13)
45 * Returns whether or not a given vertex is
46 * is part of a given edge.
48 int BM_vert_in_edge(BMEdge *e, BMVert *v)
50 return bmesh_vert_in_edge(e, v);
54 * \brief Other Loop in Face Sharing an Edge
56 * Finds the other loop that shares \a v with \a e loop in \a f.
62 * +----------+ <-- return the face loop of this vertex.
64 * ^ ^ <------- These vert args define direction
65 * in the face to check.
66 * The faces loop direction is ignored.
69 BMLoop *BM_face_other_edge_loop(BMFace *f, BMEdge *e, BMVert *v)
74 /* we could loop around the face too, but turns out this uses a lot
75 * more iterations (approx double with quads, many more with 5+ ngons) */
76 l_iter = l_first = e->l;
79 if (l_iter->e == e && l_iter->f == f) {
82 } while ((l_iter = l_iter->radial_next) != l_first);
84 return l_iter->v == v ? l_iter->prev : l_iter->next;
88 * \brief Other Loop in Face Sharing a Vertex
90 * Finds the other loop in a face.
92 * This function returns a loop in \a f that shares an edge with \a v
93 * The direction is defined by \a v_prev, where the return value is
94 * the loop of what would be 'v_next'
96 * +----------+ <-- return the face loop of this vertex.
102 * ^^^^^^ ^ <-- These vert args define direction
103 * in the face to check.
104 * The faces loop direction is ignored.
107 * \note \a v_prev and \a v _implicitly_ define an edge.
109 BMLoop *BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v)
114 BLI_assert(BM_edge_exists(v_prev, v) != NULL);
116 BM_ITER_ELEM (l_iter, &liter, v, BM_LOOPS_OF_VERT) {
117 if (l_iter->f == f) {
123 if (l_iter->prev->v == v_prev) {
126 else if (l_iter->next->v == v_prev) {
143 * \brief Other Loop in Face Sharing a Vert
145 * Finds the other loop that shares \a v with \a e loop in \a f.
147 * +----------+ <-- return the face loop of this vertex.
151 * +----------+ <-- This vertex defines the direction.
153 * ^ <------- This loop defines both the face to search
154 * and the edge, in combination with 'v'
155 * The faces loop direction is ignored.
159 BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v)
161 #if 0 /* works but slow */
162 return BM_face_other_vert_loop(l->f, BM_edge_other_vert(l->e, v), v);
165 BMVert *v_prev = BM_edge_other_vert(e, v);
167 if (l->prev->v == v_prev) {
171 BLI_assert(l->next->v == v_prev);
177 BLI_assert(l->v == v_prev);
179 if (l->prev->v == v) {
180 return l->prev->prev;
183 BLI_assert(l->next->v == v);
184 return l->next->next;
194 * Get the first loop of a vert. Uses the same initialization code for the first loop of the
197 BMLoop *BM_vert_find_first_loop(BMVert *v)
204 e = bmesh_disk_faceedge_find_first(v->e, v);
209 return bmesh_radial_faceloop_find_first(e->l, v);
213 * Returns TRUE if the vertex is used in a given face.
215 int BM_vert_in_face(BMFace *f, BMVert *v)
217 BMLoop *l_iter, *l_first;
219 #ifdef USE_BMESH_HOLES
221 for (lst = f->loops.first; lst; lst = lst->next)
224 #ifdef USE_BMESH_HOLES
225 l_iter = l_first = lst->first;
227 l_iter = l_first = f->l_first;
230 if (l_iter->v == v) {
233 } while ((l_iter = l_iter->next) != l_first);
240 * Compares the number of vertices in an array
241 * that appear in a given face
243 int BM_verts_in_face(BMesh *bm, BMFace *f, BMVert **varr, int len)
245 BMLoop *l_iter, *l_first;
247 #ifdef USE_BMESH_HOLES
253 for (i = 0; i < len; i++) {
254 BMO_elem_flag_enable(bm, varr[i], BM_OVERLAP);
257 #ifdef USE_BMESH_HOLES
258 for (lst = f->loops.first; lst; lst = lst->next)
262 #ifdef USE_BMESH_HOLES
263 l_iter = l_first = lst->first;
265 l_iter = l_first = f->l_first;
269 if (BMO_elem_flag_test(bm, l_iter->v, BM_OVERLAP)) {
273 } while ((l_iter = l_iter->next) != l_first);
276 for (i = 0; i < len; i++) BMO_elem_flag_disable(bm, varr[i], BM_OVERLAP);
282 * Returns whether or not a given edge is is part of a given face.
284 int BM_edge_in_face(BMFace *f, BMEdge *e)
289 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
292 if (l_iter->e == e) {
295 } while ((l_iter = l_iter->next) != l_first);
301 * Returns whether or not a given edge is is part of a given loop.
303 int BM_edge_in_loop(BMEdge *e, BMLoop *l)
305 return (l->e == e || l->prev->e == e);
309 * Returns whether or not two vertices are in
312 int BM_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
314 return bmesh_verts_in_edge(v1, v2, e);
318 * Given a edge and one of its vertices, returns
321 BMVert *BM_edge_other_vert(BMEdge *e, BMVert *v)
323 return bmesh_edge_other_vert_get(e, v);
327 * Given a edge and a loop (assumes the edge is manifold). returns
328 * the other faces loop, sharing the same vertex.
331 * +-------------------+
334 * |l_other <-- return |
335 * +-------------------+ <-- A manifold edge between 2 faces
337 * |^ <-------- loop |
339 * +-------------------+
342 BMLoop *BM_edge_other_loop(BMEdge *e, BMLoop *l)
346 // BLI_assert(BM_edge_is_manifold(e)); // TOO strict, just check if we have another radial face
347 BLI_assert(e->l && e->l->radial_next != e->l);
348 BLI_assert(BM_vert_in_edge(e, l->v));
350 l_other = (l->e == e) ? l : l->prev;
351 l_other = l_other->radial_next;
352 BLI_assert(l_other->e == e);
354 if (l_other->v == l->v) {
357 else if (l_other->next->v == l->v) {
358 l_other = l_other->next;
368 * Utility function to step around a fan of loops,
369 * using an edge to mark the previous side.
371 * \note all edges must be manifold,
372 * once a non manifold edge is hit, return NULL.
377 * ,' | (notice how 'e_step'
378 * / | and 'l' define the
379 * / | direction the arrow
380 * | return | points).
382 * ---------------------+---------------------
387 * begin e_step ----> |
392 BMLoop *BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
394 BMEdge *e_prev = *e_step;
396 if (l->e == e_prev) {
399 else if (l->prev->e == e_prev) {
407 if (BM_edge_is_manifold(e_next)) {
408 return BM_edge_other_loop((*e_step = e_next), l);
418 * The function takes a vertex at the center of a fan and returns the opposite edge in the fan.
419 * All edges in the fan must be manifold, otherwise return NULL.
421 * \note This could (probably) be done more effieiently.
423 BMEdge *BM_vert_other_disk_edge(BMVert *v, BMEdge *e_first)
429 BLI_assert(BM_vert_in_edge(e_first, v));
433 l_a = BM_loop_other_vert_loop(l_a, v);
434 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
435 if (BM_edge_is_manifold(l_a->e)) {
436 l_a = l_a->radial_next;
443 } while (l_a != e_first->l);
445 /* we know the total, now loop half way */
452 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
456 l_a = BM_loop_other_vert_loop(l_a, v);
457 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
458 if (BM_edge_is_manifold(l_a->e)) {
459 l_a = l_a->radial_next;
461 /* this wont have changed from the previous loop */
465 } while (l_a != e_first->l);
471 * Returms edge length
473 float BM_edge_calc_length(BMEdge *e)
475 return len_v3v3(e->v1->co, e->v2->co);
479 * Utility function, since enough times we have an edge
480 * and want to access 2 connected faces.
482 * \return TRUE when only 2 faces are found.
484 int BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
489 (lb = la->radial_next) &&
491 (lb->radial_next == la))
505 * Utility function, since enough times we have an edge
506 * and want to access 2 connected loops.
508 * \return TRUE when only 2 faces are found.
510 int BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
515 (lb = la->radial_next) &&
517 (lb->radial_next == la))
531 * Returns the number of edges around this vertex.
533 int BM_vert_edge_count(BMVert *v)
535 return bmesh_disk_count(v);
538 int BM_vert_edge_count_nonwire(BMVert *v)
543 BM_ITER_ELEM (edge, &eiter, v, BM_EDGES_OF_VERT) {
551 * Returns the number of faces around this edge
553 int BM_edge_face_count(BMEdge *e)
561 l_iter = l_first = e->l;
565 } while ((l_iter = l_iter->radial_next) != l_first);
572 * Returns the number of faces around this vert
573 * length matches #BM_LOOPS_OF_VERT iterator
575 int BM_vert_face_count(BMVert *v)
577 return bmesh_disk_facevert_count(v);
581 * Tests whether or not the vertex is part of a wire edge.
582 * (ie: has no faces attached to it)
584 int BM_vert_is_wire(BMVert *v)
587 BMEdge *e_first, *e_iter;
589 e_first = e_iter = v->e;
594 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
604 * Tests whether or not the edge is part of a wire.
605 * (ie: has no faces attached to it)
607 int BM_edge_is_wire(BMEdge *e)
609 return (e->l) ? FALSE : TRUE;
613 * A vertex is non-manifold if it meets the following conditions:
614 * 1: Loose - (has no edges/faces incident upon it).
615 * 2: Joins two distinct regions - (two pyramids joined at the tip).
616 * 3: Is part of a an edge with more than 2 faces.
617 * 4: Is part of a wire edge.
619 int BM_vert_is_manifold(BMVert *v)
623 int len, count, flag;
630 /* count edges while looking for non-manifold edges */
634 /* loose edge or edge shared by more than two faces,
635 * edges with 1 face user are OK, otherwise we could
636 * use BM_edge_is_manifold() here */
637 if (e->l == NULL || bmesh_radial_length(e->l) > 2) {
641 } while ((e = bmesh_disk_edge_next(e, v)) != oe);
649 l = (l->v == v) ? l->prev : l->next;
651 count++; /* count the edges */
653 if (flag && l->radial_next == l) {
654 /* we've hit the edge of an open mesh, reset once */
661 else if (l->radial_next == l) {
671 /* vert shared by multiple regions */
679 * Tests whether or not this edge is manifold.
680 * A manifold edge has exactly 2 faces attached to it.
683 #if 1 /* fast path for checking manifold */
684 int BM_edge_is_manifold(BMEdge *e)
686 const BMLoop *l = e->l;
687 return (l && (l->radial_next != l) && /* not 0 or 1 face users */
688 (l->radial_next->radial_next == l)); /* 2 face users */
691 int BM_edge_is_manifold(BMEdge *e)
693 int count = BM_edge_face_count(e);
704 * Tests whether or not an edge is on the boundary
705 * of a shell (has one face associated with it)
708 #if 1 /* fast path for checking boundary */
709 int BM_edge_is_boundary(BMEdge *e)
711 const BMLoop *l = e->l;
712 return (l && (l->radial_next == l));
715 int BM_edge_is_boundary(BMEdge *e)
717 int count = BM_edge_face_count(e);
728 * Returns the number of faces that are adjacent to both f1 and f2,
729 * \note Could be sped up a bit by not using iterators and by tagging
730 * faces on either side, then count the tags rather then searching.
732 int BM_face_share_face_count(BMFace *f1, BMFace *f2)
739 BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
740 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
741 if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2))
750 * same as #BM_face_share_face_count but returns a bool
752 int BM_face_share_face_check(BMFace *f1, BMFace *f2)
758 BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
759 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
760 if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2))
769 * Counts the number of edges two faces share (if any)
771 int BM_face_share_edge_count(BMFace *f1, BMFace *f2)
777 l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
779 if (bmesh_radial_face_find(l_iter->e, f2)) {
782 } while ((l_iter = l_iter->next) != l_first);
788 * Returns TRUE if the faces share an edge
790 int BM_face_share_edge_check(BMFace *f1, BMFace *f2)
795 l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
797 if (bmesh_radial_face_find(l_iter->e, f2)) {
800 } while ((l_iter = l_iter->next) != l_first);
806 * Test if e1 shares any faces with e2
808 int BM_edge_share_face_check(BMEdge *e1, BMEdge *e2)
813 if (e1->l && e2->l) {
817 if (bmesh_radial_face_find(e2, f)) {
821 } while (l != e1->l);
827 * Tests to see if e1 shares a vertex with e2
829 int BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
831 return (e1->v1 == e2->v1 ||
838 * Return the shared vertex between the two edges or NULL
840 BMVert *BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
842 if (BM_vert_in_edge(e2, e1->v1)) {
845 else if (BM_vert_in_edge(e2, e1->v2)) {
854 * \brief Return the Loop Shared by Face and Vertex
856 * Finds the loop used which uses \a v in face loop \a l
858 * \note currently this just uses simple loop in future may be sped up
861 BMLoop *BM_face_vert_share_loop(BMFace *f, BMVert *v)
866 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
868 if (l_iter->v == v) {
871 } while ((l_iter = l_iter->next) != l_first);
877 * \brief Return the Loop Shared by Face and Edge
879 * Finds the loop used which uses \a e in face loop \a l
881 * \note currently this just uses simple loop in future may be sped up
884 BMLoop *BM_face_edge_share_loop(BMFace *f, BMEdge *e)
889 l_iter = l_first = e->l;
891 if (l_iter->f == f) {
894 } while ((l_iter = l_iter->radial_next) != l_first);
900 * Returns the verts of an edge as used in a face
901 * if used in a face at all, otherwise just assign as used in the edge.
903 * Useful to get a deterministic winding order when calling
904 * BM_face_create_ngon() on an arbitrary array of verts,
905 * though be sure to pick an edge which has a face.
907 * \note This is in fact quite a simple check, mainly include this function so the intent is more obvious.
908 * We know these 2 verts will _always_ make up the loops edge
910 void BM_edge_ordered_verts_ex(BMEdge *edge, BMVert **r_v1, BMVert **r_v2,
913 BLI_assert(edge_loop->e == edge);
914 (void)edge; /* quiet warning in release build */
915 *r_v1 = edge_loop->v;
916 *r_v2 = edge_loop->next->v;
919 void BM_edge_ordered_verts(BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
921 BM_edge_ordered_verts_ex(edge, r_v1, r_v2, edge->l);
925 * Calculates the angle between the previous and next loops
926 * (angle at this loops face corner).
928 * \return angle in radians
930 float BM_loop_calc_face_angle(BMLoop *l)
932 return angle_v3v3v3(l->prev->v->co,
938 * \brief BM_loop_calc_face_normal
940 * Calculate the normal at this loop corner or fallback to the face normal on straight lines.
942 * \param l The loop to calculate the normal at
943 * \param r_normal Resulting normal
945 void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3])
947 if (normal_tri_v3(r_normal,
950 l->next->v->co) != 0.0f)
955 copy_v3_v3(r_normal, l->f->no);
960 * \brief BM_loop_calc_face_tangent
962 * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
963 * This vector always points inward into the face.
965 * \param l The loop to calculate the tangent at
966 * \param r_tangent Resulting tangent
968 void BM_loop_calc_face_tangent(BMLoop *l, float r_tangent[3])
973 sub_v3_v3v3(v_prev, l->prev->v->co, l->v->co);
974 sub_v3_v3v3(v_next, l->v->co, l->next->v->co);
976 normalize_v3(v_prev);
977 normalize_v3(v_next);
979 if (compare_v3v3(v_prev, v_next, FLT_EPSILON) == FALSE) {
981 float nor[3]; /* for this purpose doesn't need to be normalized */
982 add_v3_v3v3(dir, v_prev, v_next);
983 cross_v3_v3v3(nor, v_prev, v_next);
984 cross_v3_v3v3(r_tangent, dir, nor);
987 /* prev/next are the same - compare with face normal since we don't have one */
988 cross_v3_v3v3(r_tangent, v_next, l->f->no);
991 normalize_v3(r_tangent);
995 * \brief BMESH EDGE/FACE ANGLE
997 * Calculates the angle between two faces.
998 * Assumes the face normals are correct.
1000 * \return angle in radians
1002 float BM_edge_calc_face_angle(BMEdge *e)
1004 if (BM_edge_is_manifold(e)) {
1006 BMLoop *l2 = e->l->radial_next;
1007 return angle_normalized_v3v3(l1->f->no, l2->f->no);
1010 return DEG2RADF(90.0f);
1015 * \brief BMESH EDGE/FACE TANGENT
1017 * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1018 * This vector always points inward into the face.
1020 * \brief BM_edge_calc_face_tangent
1022 * \param e_loop The loop to calculate the tangent at,
1023 * used to get the face and winding direction.
1024 * \param r_tangent The loop corner tangent to set
1027 void BM_edge_calc_face_tangent(BMEdge *e, BMLoop *e_loop, float r_tangent[3])
1031 BM_edge_ordered_verts_ex(e, &v1, &v2, e_loop);
1033 sub_v3_v3v3(tvec, v1->co, v2->co); /* use for temp storage */
1034 /* note, we could average the tangents of both loops,
1035 * for non flat ngons it will give a better direction */
1036 cross_v3_v3v3(r_tangent, tvec, e_loop->f->no);
1037 normalize_v3(r_tangent);
1041 * \brief BMESH VERT/EDGE ANGLE
1043 * Calculates the angle a verts 2 edges.
1045 * \returns the angle in radians
1047 float BM_vert_calc_edge_angle(BMVert *v)
1051 /* saves BM_vert_edge_count(v) and and edge iterator,
1052 * get the edges and count them both at once */
1055 (e2 = bmesh_disk_edge_next(e1, v)) &&
1056 /* make sure we come full circle and only have 2 connected edges */
1057 (e1 == bmesh_disk_edge_next(e2, v)))
1059 BMVert *v1 = BM_edge_other_vert(e1, v);
1060 BMVert *v2 = BM_edge_other_vert(e2, v);
1062 return (float)M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
1065 return DEG2RADF(90.0f);
1070 * \note this isn't optimal to run on an array of verts,
1071 * see 'solidify_add_thickness' for a function which runs on an array.
1073 float BM_vert_calc_shell_factor(BMVert *v)
1077 float accum_shell = 0.0f;
1078 float accum_angle = 0.0f;
1080 BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
1081 const float face_angle = BM_loop_calc_face_angle(l);
1082 accum_shell += shell_angle_to_dist(angle_normalized_v3v3(v->no, l->f->no)) * face_angle;
1083 accum_angle += face_angle;
1086 if (accum_angle != 0.0f) {
1087 return accum_shell / accum_angle;
1095 * \note quite an obscure function.
1096 * used in bmesh operators that have a relative scale options,
1098 float BM_vert_calc_mean_tagged_edge_length(BMVert *v)
1103 float length = 0.0f;
1105 BM_ITER_ELEM_INDEX (e, &iter, v, BM_EDGES_OF_VERT, tot) {
1106 BMVert *v_other = BM_edge_other_vert(e, v);
1107 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1108 length += BM_edge_calc_length(e);
1113 return length / (float)tot;
1122 * Returns the loop of the shortest edge in f.
1124 BMLoop *BM_face_find_shortest_loop(BMFace *f)
1126 BMLoop *shortest_loop = NULL;
1127 float shortest_len = FLT_MAX;
1132 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1135 const float len = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1136 if (len <= shortest_len) {
1137 shortest_loop = l_iter;
1140 } while ((l_iter = l_iter->next) != l_first);
1142 return shortest_loop;
1146 * Returns the loop of the longest edge in f.
1148 BMLoop *BM_face_find_longest_loop(BMFace *f)
1150 BMLoop *longest_loop = NULL;
1151 float longest_len = 0.0f;
1156 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1159 const float len = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1160 if (len >= longest_len) {
1161 longest_loop = l_iter;
1164 } while ((l_iter = l_iter->next) != l_first);
1166 return longest_loop;
1170 * Returns the edge existing between v1 and v2, or NULL if there isn't one.
1172 * \note multiple edges may exist between any two vertices, and therefore
1173 * this function only returns the first one found.
1175 BMEdge *BM_edge_exists(BMVert *v1, BMVert *v2)
1180 BM_ITER_ELEM (e, &iter, v1, BM_EDGES_OF_VERT) {
1181 if (e->v1 == v2 || e->v2 == v2)
1189 * Returns an edge sharing the same vertices as this one.
1190 * This isn't an invalid state but tools should clean up these cases before
1191 * returning the mesh to the user.
1193 BMEdge *BM_edge_find_double(BMEdge *e)
1196 BMVert *v_other = e->v2;
1201 while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e) {
1202 if (UNLIKELY(BM_vert_in_edge(e_iter, v_other))) {
1211 * Given a set of vertices \a varr, find out if
1212 * all those vertices overlap an existing face.
1214 * \note Making a face here is valid but in some cases you wont want to
1215 * make a face thats part of another.
1217 * \returns TRUE for overlap
1220 int BM_face_exists_overlap(BMesh *bm, BMVert **varr, int len, BMFace **r_overlapface)
1226 for (i = 0; i < len; i++) {
1227 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1228 amount = BM_verts_in_face(bm, f, varr, len);
1229 if (amount >= len) {
1230 if (r_overlapface) {
1238 if (r_overlapface) {
1239 *r_overlapface = NULL;
1246 * Given a set of vertices (varr), find out if
1247 * there is a face with exactly those vertices
1248 * (and only those vertices).
1250 int BM_face_exists(BMesh *bm, BMVert **varr, int len, BMFace **r_existface)
1256 for (i = 0; i < len; i++) {
1257 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1258 amount = BM_verts_in_face(bm, f, varr, len);
1259 if (amount == len && amount == f->len) {
1269 *r_existface = NULL;
1276 * Given a set of vertices and edges (\a varr, \a earr), find out if
1277 * all those vertices are filled in by existing faces that _only_ use those vertices.
1279 * This is for use in cases where creating a face is possible but would result in
1280 * many overlapping faces.
1282 * An example of how this is used: when 2 tri's are selected that share an edge,
1283 * pressing Fkey would make a new overlapping quad (without a check like this)
1285 * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
1287 int BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
1300 for (i = 0; i < len; i++) {
1301 /* save some time by looping over edge faces rather then vert faces
1302 * will still loop over some faces twice but not as many */
1303 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1304 BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
1305 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1306 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
1310 /* clear all edge tags */
1311 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1312 BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
1316 /* now tag all verts and edges in the boundary array as true so
1317 * we can know if a face-vert is from our array */
1318 for (i = 0; i < len; i++) {
1319 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
1320 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
1324 /* so! boundary is tagged, everything else cleared */
1327 /* 1) tag all faces connected to edges - if all their verts are boundary */
1329 for (i = 0; i < len; i++) {
1330 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1331 if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
1333 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1334 if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
1341 /* we only use boundary verts */
1342 BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
1347 /* we already found! */
1353 /* no faces use only boundary verts, quit early */
1357 /* 2) loop over non-boundary edges that use boundary verts,
1358 * check each have 2 tagges faces connected (faces that only use 'varr' verts) */
1360 for (i = 0; i < len; i++) {
1361 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1363 if (/* non-boundary edge */
1364 BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == FALSE &&
1365 /* ...using boundary verts */
1366 BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == TRUE &&
1367 BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == TRUE)
1369 int tot_face_tag = 0;
1370 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
1371 if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
1376 if (tot_face_tag != 2) {
1392 /* same as 'BM_face_exists_multi' but built vert array from edges */
1393 int BM_face_exists_multi_edge(BMEdge **earr, int len)
1396 BLI_array_fixedstack_declare(varr, BM_NGON_STACK_SIZE, len, __func__);
1401 /* first check if verts have edges, if not we can bail out early */
1403 for (i = len - 1, i_next = 0; i_next < len; (i = i_next++)) {
1404 if (!(varr[i] = BM_edge_share_vert(earr[i], earr[i_next]))) {
1412 BLI_array_fixedstack_free(varr);
1416 ok = BM_face_exists_multi(varr, earr, len);
1418 BLI_array_fixedstack_free(varr);
1423 /* convenience functiosn for checking flags */
1424 int BM_edge_is_any_vert_flag_test(BMEdge *e, const char hflag)
1426 return (BM_elem_flag_test(e->v1, hflag) ||
1427 BM_elem_flag_test(e->v2, hflag));
1430 int BM_face_is_any_vert_flag_test(BMFace *f, const char hflag)
1435 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1437 if (BM_elem_flag_test(l_iter->v, hflag)) {
1440 } while ((l_iter = l_iter->next) != l_first);
1444 int BM_face_is_any_edge_flag_test(BMFace *f, const char hflag)
1449 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1451 if (BM_elem_flag_test(l_iter->e, hflag)) {
1454 } while ((l_iter = l_iter->next) != l_first);