1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 */
16
17 /** \file
18 * \ingroup bmesh
19 *
20 * This file contains functions for answering common
21 * Topological and geometric queries about a mesh, such
22 * as, "What is the angle between these two faces?" or,
23 * "How many faces are incident upon this vertex?" Tool
24 * authors should use the functions in this file instead
25 * of inspecting the mesh structure directly.
26 */
27
28 #include "MEM_guardedalloc.h"
29
30 #include "BLI_alloca.h"
31 #include "BLI_linklist.h"
32 #include "BLI_math.h"
33 #include "BLI_utildefines_stack.h"
34
35 #include "BKE_customdata.h"
36
37 #include "bmesh.h"
38 #include "intern/bmesh_private.h"
39
40 /**
41 * \brief Other Loop in Face Sharing an Edge
42 *
43 * Finds the other loop that shares \a v with \a e loop in \a f.
44 * <pre>
45 * +----------+
46 * | |
47 * | f |
48 * | |
49 * +----------+ <-- return the face loop of this vertex.
50 * v --> e
51 * ^ ^ <------- These vert args define direction
52 * in the face to check.
53 * The faces loop direction is ignored.
54 * </pre>
55 *
56 * \note caller must ensure \a e is used in \a f
57 */
BM_face_other_edge_loop(BMFace * f,BMEdge * e,BMVert * v)58 BMLoop *BM_face_other_edge_loop(BMFace *f, BMEdge *e, BMVert *v)
59 {
60 BMLoop *l = BM_face_edge_share_loop(f, e);
61 BLI_assert(l != NULL);
62 return BM_loop_other_edge_loop(l, v);
63 }
64
65 /**
66 * See #BM_face_other_edge_loop This is the same functionality
67 * to be used when the edges loop is already known.
68 */
BM_loop_other_edge_loop(BMLoop * l,BMVert * v)69 BMLoop *BM_loop_other_edge_loop(BMLoop *l, BMVert *v)
70 {
71 BLI_assert(BM_vert_in_edge(l->e, v));
72 return l->v == v ? l->prev : l->next;
73 }
74
75 /**
76 * \brief Other Loop in Face Sharing a Vertex
77 *
78 * Finds the other loop in a face.
79 *
80 * This function returns a loop in \a f that shares an edge with \a v
81 * The direction is defined by \a v_prev, where the return value is
82 * the loop of what would be 'v_next'
83 * <pre>
84 * +----------+ <-- return the face loop of this vertex.
85 * | |
86 * | f |
87 * | |
88 * +----------+
89 * v_prev --> v
90 * ^^^^^^ ^ <-- These vert args define direction
91 * in the face to check.
92 * The faces loop direction is ignored.
93 * </pre>
94 *
95 * \note \a v_prev and \a v _implicitly_ define an edge.
96 */
BM_face_other_vert_loop(BMFace * f,BMVert * v_prev,BMVert * v)97 BMLoop *BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v)
98 {
99 BMLoop *l_iter = BM_face_vert_share_loop(f, v);
100
101 BLI_assert(BM_edge_exists(v_prev, v) != NULL);
102
103 if (l_iter) {
104 if (l_iter->prev->v == v_prev) {
105 return l_iter->next;
106 }
107 if (l_iter->next->v == v_prev) {
108 return l_iter->prev;
109 }
110 /* invalid args */
111 BLI_assert(0);
112 return NULL;
113 }
114 /* invalid args */
115 BLI_assert(0);
116 return NULL;
117 }
118
119 /**
120 * \brief Other Loop in Face Sharing a Vert
121 *
122 * Finds the other loop that shares \a v with \a e loop in \a f.
123 * <pre>
124 * +----------+ <-- return the face loop of this vertex.
125 * | |
126 * | |
127 * | |
128 * +----------+ <-- This vertex defines the direction.
129 * l v
130 * ^ <------- This loop defines both the face to search
131 * and the edge, in combination with 'v'
132 * The faces loop direction is ignored.
133 * </pre>
134 */
BM_loop_other_vert_loop(BMLoop * l,BMVert * v)135 BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v)
136 {
137 #if 0 /* works but slow */
138 return BM_face_other_vert_loop(l->f, BM_edge_other_vert(l->e, v), v);
139 #else
140 BMEdge *e = l->e;
141 BMVert *v_prev = BM_edge_other_vert(e, v);
142 if (l->v == v) {
143 if (l->prev->v == v_prev) {
144 return l->next;
145 }
146 BLI_assert(l->next->v == v_prev);
147
148 return l->prev;
149 }
150 BLI_assert(l->v == v_prev);
151
152 if (l->prev->v == v) {
153 return l->prev->prev;
154 }
155 BLI_assert(l->next->v == v);
156 return l->next->next;
157 #endif
158 }
159
160 /**
161 * Return the other loop that uses this edge.
162 *
163 * In this case the loop defines the vertex,
164 * the edge passed in defines the direction to step.
165 *
166 * <pre>
167 * +----------+ <-- Return the face-loop of this vertex.
168 * | |
169 * | e | <-- This edge defines the direction.
170 * | |
171 * +----------+ <-- This loop defines the face and vertex..
172 * l
173 * </pre>
174 *
175 */
BM_loop_other_vert_loop_by_edge(BMLoop * l,BMEdge * e)176 BMLoop *BM_loop_other_vert_loop_by_edge(BMLoop *l, BMEdge *e)
177 {
178 BLI_assert(BM_vert_in_edge(e, l->v));
179 if (l->e == e) {
180 return l->next;
181 }
182 if (l->prev->e == e) {
183 return l->prev;
184 }
185
186 BLI_assert(0);
187 return NULL;
188 }
189
190 /**
191 * Check if verts share a face.
192 */
BM_vert_pair_share_face_check(BMVert * v_a,BMVert * v_b)193 bool BM_vert_pair_share_face_check(BMVert *v_a, BMVert *v_b)
194 {
195 if (v_a->e && v_b->e) {
196 BMIter iter;
197 BMFace *f;
198
199 BM_ITER_ELEM (f, &iter, v_a, BM_FACES_OF_VERT) {
200 if (BM_vert_in_face(v_b, f)) {
201 return true;
202 }
203 }
204 }
205
206 return false;
207 }
208
BM_vert_pair_share_face_check_cb(BMVert * v_a,BMVert * v_b,bool (* test_fn)(BMFace *,void * user_data),void * user_data)209 bool BM_vert_pair_share_face_check_cb(BMVert *v_a,
210 BMVert *v_b,
211 bool (*test_fn)(BMFace *, void *user_data),
212 void *user_data)
213 {
214 if (v_a->e && v_b->e) {
215 BMIter iter;
216 BMFace *f;
217
218 BM_ITER_ELEM (f, &iter, v_a, BM_FACES_OF_VERT) {
219 if (test_fn(f, user_data)) {
220 if (BM_vert_in_face(v_b, f)) {
221 return true;
222 }
223 }
224 }
225 }
226
227 return false;
228 }
229
BM_vert_pair_shared_face_cb(BMVert * v_a,BMVert * v_b,const bool allow_adjacent,bool (* callback)(BMFace *,BMLoop *,BMLoop *,void * userdata),void * user_data,BMLoop ** r_l_a,BMLoop ** r_l_b)230 BMFace *BM_vert_pair_shared_face_cb(BMVert *v_a,
231 BMVert *v_b,
232 const bool allow_adjacent,
233 bool (*callback)(BMFace *, BMLoop *, BMLoop *, void *userdata),
234 void *user_data,
235 BMLoop **r_l_a,
236 BMLoop **r_l_b)
237 {
238 if (v_a->e && v_b->e) {
239 BMIter iter;
240 BMLoop *l_a, *l_b;
241
242 BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
243 BMFace *f = l_a->f;
244 l_b = BM_face_vert_share_loop(f, v_b);
245 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b)) &&
246 callback(f, l_a, l_b, user_data)) {
247 *r_l_a = l_a;
248 *r_l_b = l_b;
249
250 return f;
251 }
252 }
253 }
254
255 return NULL;
256 }
257
258 /**
259 * Given 2 verts, find the smallest face they share and give back both loops.
260 */
BM_vert_pair_share_face_by_len(BMVert * v_a,BMVert * v_b,BMLoop ** r_l_a,BMLoop ** r_l_b,const bool allow_adjacent)261 BMFace *BM_vert_pair_share_face_by_len(
262 BMVert *v_a, BMVert *v_b, BMLoop **r_l_a, BMLoop **r_l_b, const bool allow_adjacent)
263 {
264 BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
265 BMFace *f_cur = NULL;
266
267 if (v_a->e && v_b->e) {
268 BMIter iter;
269 BMLoop *l_a, *l_b;
270
271 BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
272 if ((f_cur == NULL) || (l_a->f->len < f_cur->len)) {
273 l_b = BM_face_vert_share_loop(l_a->f, v_b);
274 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
275 f_cur = l_a->f;
276 l_cur_a = l_a;
277 l_cur_b = l_b;
278 }
279 }
280 }
281 }
282
283 *r_l_a = l_cur_a;
284 *r_l_b = l_cur_b;
285
286 return f_cur;
287 }
288
BM_edge_pair_share_face_by_len(BMEdge * e_a,BMEdge * e_b,BMLoop ** r_l_a,BMLoop ** r_l_b,const bool allow_adjacent)289 BMFace *BM_edge_pair_share_face_by_len(
290 BMEdge *e_a, BMEdge *e_b, BMLoop **r_l_a, BMLoop **r_l_b, const bool allow_adjacent)
291 {
292 BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
293 BMFace *f_cur = NULL;
294
295 if (e_a->l && e_b->l) {
296 BMIter iter;
297 BMLoop *l_a, *l_b;
298
299 BM_ITER_ELEM (l_a, &iter, e_a, BM_LOOPS_OF_EDGE) {
300 if ((f_cur == NULL) || (l_a->f->len < f_cur->len)) {
301 l_b = BM_face_edge_share_loop(l_a->f, e_b);
302 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
303 f_cur = l_a->f;
304 l_cur_a = l_a;
305 l_cur_b = l_b;
306 }
307 }
308 }
309 }
310
311 *r_l_a = l_cur_a;
312 *r_l_b = l_cur_b;
313
314 return f_cur;
315 }
316
bm_face_calc_split_dot(BMLoop * l_a,BMLoop * l_b)317 static float bm_face_calc_split_dot(BMLoop *l_a, BMLoop *l_b)
318 {
319 float no[2][3];
320
321 if ((BM_face_calc_normal_subset(l_a, l_b, no[0]) != 0.0f) &&
322 (BM_face_calc_normal_subset(l_b, l_a, no[1]) != 0.0f)) {
323 return dot_v3v3(no[0], no[1]);
324 }
325 return -1.0f;
326 }
327
328 /**
329 * Check if a point is inside the corner defined by a loop
330 * (within the 2 planes defined by the loops corner & face normal).
331 *
332 * \return signed, squared distance to the loops planes, less than 0.0 when outside.
333 */
BM_loop_point_side_of_loop_test(const BMLoop * l,const float co[3])334 float BM_loop_point_side_of_loop_test(const BMLoop *l, const float co[3])
335 {
336 const float *axis = l->f->no;
337 return dist_signed_squared_to_corner_v3v3v3(co, l->prev->v->co, l->v->co, l->next->v->co, axis);
338 }
339
340 /**
341 * Check if a point is inside the edge defined by a loop
342 * (within the plane defined by the loops edge & face normal).
343 *
344 * \return signed, squared distance to the edge plane, less than 0.0 when outside.
345 */
BM_loop_point_side_of_edge_test(const BMLoop * l,const float co[3])346 float BM_loop_point_side_of_edge_test(const BMLoop *l, const float co[3])
347 {
348 const float *axis = l->f->no;
349 float dir[3];
350 float plane[4];
351
352 sub_v3_v3v3(dir, l->next->v->co, l->v->co);
353 cross_v3_v3v3(plane, axis, dir);
354
355 plane[3] = -dot_v3v3(plane, l->v->co);
356 return dist_signed_squared_to_plane_v3(co, plane);
357 }
358
359 /**
360 * Given 2 verts,
361 * find a face they share that has the lowest angle across these verts and give back both loops.
362 *
363 * This can be better than #BM_vert_pair_share_face_by_len
364 * because concave splits are ranked lowest.
365 */
BM_vert_pair_share_face_by_angle(BMVert * v_a,BMVert * v_b,BMLoop ** r_l_a,BMLoop ** r_l_b,const bool allow_adjacent)366 BMFace *BM_vert_pair_share_face_by_angle(
367 BMVert *v_a, BMVert *v_b, BMLoop **r_l_a, BMLoop **r_l_b, const bool allow_adjacent)
368 {
369 BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
370 BMFace *f_cur = NULL;
371
372 if (v_a->e && v_b->e) {
373 BMIter iter;
374 BMLoop *l_a, *l_b;
375 float dot_best = -1.0f;
376
377 BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
378 l_b = BM_face_vert_share_loop(l_a->f, v_b);
379 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
380
381 if (f_cur == NULL) {
382 f_cur = l_a->f;
383 l_cur_a = l_a;
384 l_cur_b = l_b;
385 }
386 else {
387 /* avoid expensive calculations if we only ever find one face */
388 float dot;
389 if (dot_best == -1.0f) {
390 dot_best = bm_face_calc_split_dot(l_cur_a, l_cur_b);
391 }
392
393 dot = bm_face_calc_split_dot(l_a, l_b);
394 if (dot > dot_best) {
395 dot_best = dot;
396
397 f_cur = l_a->f;
398 l_cur_a = l_a;
399 l_cur_b = l_b;
400 }
401 }
402 }
403 }
404 }
405
406 *r_l_a = l_cur_a;
407 *r_l_b = l_cur_b;
408
409 return f_cur;
410 }
411
412 /**
413 * Get the first loop of a vert. Uses the same initialization code for the first loop of the
414 * iterator API
415 */
BM_vert_find_first_loop(BMVert * v)416 BMLoop *BM_vert_find_first_loop(BMVert *v)
417 {
418 return v->e ? bmesh_disk_faceloop_find_first(v->e, v) : NULL;
419 }
420 /**
421 * A version of #BM_vert_find_first_loop that ignores hidden loops.
422 */
BM_vert_find_first_loop_visible(BMVert * v)423 BMLoop *BM_vert_find_first_loop_visible(BMVert *v)
424 {
425 return v->e ? bmesh_disk_faceloop_find_first_visible(v->e, v) : NULL;
426 }
427
428 /**
429 * Returns true if the vertex is used in a given face.
430 */
BM_vert_in_face(BMVert * v,BMFace * f)431 bool BM_vert_in_face(BMVert *v, BMFace *f)
432 {
433 BMLoop *l_iter, *l_first;
434
435 #ifdef USE_BMESH_HOLES
436 BMLoopList *lst;
437 for (lst = f->loops.first; lst; lst = lst->next)
438 #endif
439 {
440 #ifdef USE_BMESH_HOLES
441 l_iter = l_first = lst->first;
442 #else
443 l_iter = l_first = f->l_first;
444 #endif
445 do {
446 if (l_iter->v == v) {
447 return true;
448 }
449 } while ((l_iter = l_iter->next) != l_first);
450 }
451
452 return false;
453 }
454
455 /**
456 * Compares the number of vertices in an array
457 * that appear in a given face
458 */
BM_verts_in_face_count(BMVert ** varr,int len,BMFace * f)459 int BM_verts_in_face_count(BMVert **varr, int len, BMFace *f)
460 {
461 BMLoop *l_iter, *l_first;
462
463 #ifdef USE_BMESH_HOLES
464 BMLoopList *lst;
465 #endif
466
467 int i, count = 0;
468
469 for (i = 0; i < len; i++) {
470 BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
471 }
472
473 #ifdef USE_BMESH_HOLES
474 for (lst = f->loops.first; lst; lst = lst->next)
475 #endif
476 {
477
478 #ifdef USE_BMESH_HOLES
479 l_iter = l_first = lst->first;
480 #else
481 l_iter = l_first = f->l_first;
482 #endif
483
484 do {
485 if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
486 count++;
487 }
488
489 } while ((l_iter = l_iter->next) != l_first);
490 }
491
492 for (i = 0; i < len; i++) {
493 BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
494 }
495
496 return count;
497 }
498
499 /**
500 * Return true if all verts are in the face.
501 */
BM_verts_in_face(BMVert ** varr,int len,BMFace * f)502 bool BM_verts_in_face(BMVert **varr, int len, BMFace *f)
503 {
504 BMLoop *l_iter, *l_first;
505
506 #ifdef USE_BMESH_HOLES
507 BMLoopList *lst;
508 #endif
509
510 int i;
511 bool ok = true;
512
513 /* simple check, we know can't succeed */
514 if (f->len < len) {
515 return false;
516 }
517
518 for (i = 0; i < len; i++) {
519 BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
520 }
521
522 #ifdef USE_BMESH_HOLES
523 for (lst = f->loops.first; lst; lst = lst->next)
524 #endif
525 {
526
527 #ifdef USE_BMESH_HOLES
528 l_iter = l_first = lst->first;
529 #else
530 l_iter = l_first = f->l_first;
531 #endif
532
533 do {
534 if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
535 /* pass */
536 }
537 else {
538 ok = false;
539 break;
540 }
541
542 } while ((l_iter = l_iter->next) != l_first);
543 }
544
545 for (i = 0; i < len; i++) {
546 BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
547 }
548
549 return ok;
550 }
551
552 /**
553 * Returns whether or not a given edge is part of a given face.
554 */
BM_edge_in_face(const BMEdge * e,const BMFace * f)555 bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
556 {
557 if (e->l) {
558 const BMLoop *l_iter, *l_first;
559
560 l_iter = l_first = e->l;
561 do {
562 if (l_iter->f == f) {
563 return true;
564 }
565 } while ((l_iter = l_iter->radial_next) != l_first);
566 }
567
568 return false;
569 }
570
571 /**
572 * Given a edge and a loop (assumes the edge is manifold). returns
573 * the other faces loop, sharing the same vertex.
574 *
575 * <pre>
576 * +-------------------+
577 * | |
578 * | |
579 * |l_other <-- return |
580 * +-------------------+ <-- A manifold edge between 2 faces
581 * |l e <-- edge |
582 * |^ <-------- loop |
583 * | |
584 * +-------------------+
585 * </pre>
586 */
BM_edge_other_loop(BMEdge * e,BMLoop * l)587 BMLoop *BM_edge_other_loop(BMEdge *e, BMLoop *l)
588 {
589 BMLoop *l_other;
590
591 // BLI_assert(BM_edge_is_manifold(e)); // TOO strict, just check if we have another radial face
592 BLI_assert(e->l && e->l->radial_next != e->l);
593 BLI_assert(BM_vert_in_edge(e, l->v));
594
595 l_other = (l->e == e) ? l : l->prev;
596 l_other = l_other->radial_next;
597 BLI_assert(l_other->e == e);
598
599 if (l_other->v == l->v) {
600 /* pass */
601 }
602 else if (l_other->next->v == l->v) {
603 l_other = l_other->next;
604 }
605 else {
606 BLI_assert(0);
607 }
608
609 return l_other;
610 }
611
612 /**
613 * Utility function to step around a fan of loops,
614 * using an edge to mark the previous side.
615 *
616 * \note all edges must be manifold,
617 * once a non manifold edge is hit, return NULL.
618 *
619 * <pre>
620 * ,.,-->|
621 * _,-' |
622 * ,' | (notice how 'e_step'
623 * / | and 'l' define the
624 * / | direction the arrow
625 * | return | points).
626 * | loop --> |
627 * ---------------------+---------------------
628 * ^ l --> |
629 * | |
630 * assign e_step |
631 * |
632 * begin e_step ----> |
633 * |
634 * </pre>
635 */
636
BM_vert_step_fan_loop(BMLoop * l,BMEdge ** e_step)637 BMLoop *BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
638 {
639 BMEdge *e_prev = *e_step;
640 BMEdge *e_next;
641 if (l->e == e_prev) {
642 e_next = l->prev->e;
643 }
644 else if (l->prev->e == e_prev) {
645 e_next = l->e;
646 }
647 else {
648 BLI_assert(0);
649 return NULL;
650 }
651
652 if (BM_edge_is_manifold(e_next)) {
653 return BM_edge_other_loop((*e_step = e_next), l);
654 }
655 return NULL;
656 }
657
658 /**
659 * The function takes a vertex at the center of a fan and returns the opposite edge in the fan.
660 * All edges in the fan must be manifold, otherwise return NULL.
661 *
662 * \note This could (probably) be done more efficiently.
663 */
BM_vert_other_disk_edge(BMVert * v,BMEdge * e_first)664 BMEdge *BM_vert_other_disk_edge(BMVert *v, BMEdge *e_first)
665 {
666 BMLoop *l_a;
667 int tot = 0;
668 int i;
669
670 BLI_assert(BM_vert_in_edge(e_first, v));
671
672 l_a = e_first->l;
673 do {
674 l_a = BM_loop_other_vert_loop(l_a, v);
675 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
676 if (BM_edge_is_manifold(l_a->e)) {
677 l_a = l_a->radial_next;
678 }
679 else {
680 return NULL;
681 }
682
683 tot++;
684 } while (l_a != e_first->l);
685
686 /* we know the total, now loop half way */
687 tot /= 2;
688 i = 0;
689
690 l_a = e_first->l;
691 do {
692 if (i == tot) {
693 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
694 return l_a->e;
695 }
696
697 l_a = BM_loop_other_vert_loop(l_a, v);
698 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
699 if (BM_edge_is_manifold(l_a->e)) {
700 l_a = l_a->radial_next;
701 }
702 /* this wont have changed from the previous loop */
703
704 i++;
705 } while (l_a != e_first->l);
706
707 return NULL;
708 }
709
710 /**
711 * Returns edge length
712 */
BM_edge_calc_length(const BMEdge * e)713 float BM_edge_calc_length(const BMEdge *e)
714 {
715 return len_v3v3(e->v1->co, e->v2->co);
716 }
717
718 /**
719 * Returns edge length squared (for comparisons)
720 */
BM_edge_calc_length_squared(const BMEdge * e)721 float BM_edge_calc_length_squared(const BMEdge *e)
722 {
723 return len_squared_v3v3(e->v1->co, e->v2->co);
724 }
725
726 /**
727 * Utility function, since enough times we have an edge
728 * and want to access 2 connected faces.
729 *
730 * \return true when only 2 faces are found.
731 */
BM_edge_face_pair(BMEdge * e,BMFace ** r_fa,BMFace ** r_fb)732 bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
733 {
734 BMLoop *la, *lb;
735
736 if ((la = e->l) && (lb = la->radial_next) && (la != lb) && (lb->radial_next == la)) {
737 *r_fa = la->f;
738 *r_fb = lb->f;
739 return true;
740 }
741
742 *r_fa = NULL;
743 *r_fb = NULL;
744 return false;
745 }
746
747 /**
748 * Utility function, since enough times we have an edge
749 * and want to access 2 connected loops.
750 *
751 * \return true when only 2 faces are found.
752 */
BM_edge_loop_pair(BMEdge * e,BMLoop ** r_la,BMLoop ** r_lb)753 bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
754 {
755 BMLoop *la, *lb;
756
757 if ((la = e->l) && (lb = la->radial_next) && (la != lb) && (lb->radial_next == la)) {
758 *r_la = la;
759 *r_lb = lb;
760 return true;
761 }
762
763 *r_la = NULL;
764 *r_lb = NULL;
765 return false;
766 }
767
768 /**
769 * Fast alternative to ``(BM_vert_edge_count(v) == 2)``
770 */
BM_vert_is_edge_pair(const BMVert * v)771 bool BM_vert_is_edge_pair(const BMVert *v)
772 {
773 const BMEdge *e = v->e;
774 if (e) {
775 BMEdge *e_other = BM_DISK_EDGE_NEXT(e, v);
776 return ((e_other != e) && (BM_DISK_EDGE_NEXT(e_other, v) == e));
777 }
778 return false;
779 }
780
781 /**
782 * Fast alternative to ``(BM_vert_edge_count(v) == 2)``
783 * that checks both edges connect to the same faces.
784 */
BM_vert_is_edge_pair_manifold(const BMVert * v)785 bool BM_vert_is_edge_pair_manifold(const BMVert *v)
786 {
787 const BMEdge *e = v->e;
788 if (e) {
789 BMEdge *e_other = BM_DISK_EDGE_NEXT(e, v);
790 if (((e_other != e) && (BM_DISK_EDGE_NEXT(e_other, v) == e))) {
791 return BM_edge_is_manifold(e) && BM_edge_is_manifold(e_other);
792 }
793 }
794 return false;
795 }
796
797 /**
798 * Access a verts 2 connected edges.
799 *
800 * \return true when only 2 verts are found.
801 */
BM_vert_edge_pair(BMVert * v,BMEdge ** r_e_a,BMEdge ** r_e_b)802 bool BM_vert_edge_pair(BMVert *v, BMEdge **r_e_a, BMEdge **r_e_b)
803 {
804 BMEdge *e_a = v->e;
805 if (e_a) {
806 BMEdge *e_b = BM_DISK_EDGE_NEXT(e_a, v);
807 if ((e_b != e_a) && (BM_DISK_EDGE_NEXT(e_b, v) == e_a)) {
808 *r_e_a = e_a;
809 *r_e_b = e_b;
810 return true;
811 }
812 }
813
814 *r_e_a = NULL;
815 *r_e_b = NULL;
816 return false;
817 }
818
819 /**
820 * Returns the number of edges around this vertex.
821 */
BM_vert_edge_count(const BMVert * v)822 int BM_vert_edge_count(const BMVert *v)
823 {
824 return bmesh_disk_count(v);
825 }
826
BM_vert_edge_count_at_most(const BMVert * v,const int count_max)827 int BM_vert_edge_count_at_most(const BMVert *v, const int count_max)
828 {
829 return bmesh_disk_count_at_most(v, count_max);
830 }
831
BM_vert_edge_count_nonwire(const BMVert * v)832 int BM_vert_edge_count_nonwire(const BMVert *v)
833 {
834 int count = 0;
835 BMIter eiter;
836 BMEdge *edge;
837 BM_ITER_ELEM (edge, &eiter, (BMVert *)v, BM_EDGES_OF_VERT) {
838 if (edge->l) {
839 count++;
840 }
841 }
842 return count;
843 }
844 /**
845 * Returns the number of faces around this edge
846 */
BM_edge_face_count(const BMEdge * e)847 int BM_edge_face_count(const BMEdge *e)
848 {
849 int count = 0;
850
851 if (e->l) {
852 BMLoop *l_iter, *l_first;
853
854 l_iter = l_first = e->l;
855 do {
856 count++;
857 } while ((l_iter = l_iter->radial_next) != l_first);
858 }
859
860 return count;
861 }
862
BM_edge_face_count_at_most(const BMEdge * e,const int count_max)863 int BM_edge_face_count_at_most(const BMEdge *e, const int count_max)
864 {
865 int count = 0;
866
867 if (e->l) {
868 BMLoop *l_iter, *l_first;
869
870 l_iter = l_first = e->l;
871 do {
872 count++;
873 if (count == count_max) {
874 break;
875 }
876 } while ((l_iter = l_iter->radial_next) != l_first);
877 }
878
879 return count;
880 }
881
882 /**
883 * Returns the number of faces around this vert
884 * length matches #BM_LOOPS_OF_VERT iterator
885 */
BM_vert_face_count(const BMVert * v)886 int BM_vert_face_count(const BMVert *v)
887 {
888 return bmesh_disk_facevert_count(v);
889 }
890
BM_vert_face_count_at_most(const BMVert * v,int count_max)891 int BM_vert_face_count_at_most(const BMVert *v, int count_max)
892 {
893 return bmesh_disk_facevert_count_at_most(v, count_max);
894 }
895
896 /**
897 * Return true if the vertex is connected to _any_ faces.
898 *
899 * same as ``BM_vert_face_count(v) != 0`` or ``BM_vert_find_first_loop(v) == NULL``
900 */
BM_vert_face_check(const BMVert * v)901 bool BM_vert_face_check(const BMVert *v)
902 {
903 if (v->e != NULL) {
904 const BMEdge *e_iter, *e_first;
905 e_first = e_iter = v->e;
906 do {
907 if (e_iter->l != NULL) {
908 return true;
909 }
910 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
911 }
912 return false;
913 }
914
915 /**
916 * Tests whether or not the vertex is part of a wire edge.
917 * (ie: has no faces attached to it)
918 */
BM_vert_is_wire(const BMVert * v)919 bool BM_vert_is_wire(const BMVert *v)
920 {
921 if (v->e) {
922 BMEdge *e_first, *e_iter;
923
924 e_first = e_iter = v->e;
925 do {
926 if (e_iter->l) {
927 return false;
928 }
929 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
930
931 return true;
932 }
933 return false;
934 }
935
936 /**
937 * A vertex is non-manifold if it meets the following conditions:
938 * 1: Loose - (has no edges/faces incident upon it).
939 * 2: Joins two distinct regions - (two pyramids joined at the tip).
940 * 3: Is part of an edge with more than 2 faces.
941 * 4: Is part of a wire edge.
942 */
BM_vert_is_manifold(const BMVert * v)943 bool BM_vert_is_manifold(const BMVert *v)
944 {
945 BMEdge *e_iter, *e_first, *e_prev;
946 BMLoop *l_iter, *l_first;
947 int loop_num = 0, loop_num_region = 0, boundary_num = 0;
948
949 if (v->e == NULL) {
950 /* loose vert */
951 return false;
952 }
953
954 /* count edges while looking for non-manifold edges */
955 e_first = e_iter = v->e;
956 /* may be null */
957 l_first = e_iter->l;
958 do {
959 /* loose edge or edge shared by more than two faces,
960 * edges with 1 face user are OK, otherwise we could
961 * use BM_edge_is_manifold() here */
962 if (e_iter->l == NULL || (e_iter->l != e_iter->l->radial_next->radial_next)) {
963 return false;
964 }
965
966 /* count radial loops */
967 if (e_iter->l->v == v) {
968 loop_num += 1;
969 }
970
971 if (!BM_edge_is_boundary(e_iter)) {
972 /* non boundary check opposite loop */
973 if (e_iter->l->radial_next->v == v) {
974 loop_num += 1;
975 }
976 }
977 else {
978 /* start at the boundary */
979 l_first = e_iter->l;
980 boundary_num += 1;
981 /* >2 boundaries cant be manifold */
982 if (boundary_num == 3) {
983 return false;
984 }
985 }
986 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
987
988 e_first = l_first->e;
989 l_first = (l_first->v == v) ? l_first : l_first->next;
990 BLI_assert(l_first->v == v);
991
992 l_iter = l_first;
993 e_prev = e_first;
994
995 do {
996 loop_num_region += 1;
997 } while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first) && (l_iter != NULL));
998
999 return (loop_num == loop_num_region);
1000 }
1001
1002 #define LOOP_VISIT _FLAG_WALK
1003 #define EDGE_VISIT _FLAG_WALK
1004
bm_loop_region_count__recursive(BMEdge * e,BMVert * v)1005 static int bm_loop_region_count__recursive(BMEdge *e, BMVert *v)
1006 {
1007 BMLoop *l_iter, *l_first;
1008 int count = 0;
1009
1010 BLI_assert(!BM_ELEM_API_FLAG_TEST(e, EDGE_VISIT));
1011 BM_ELEM_API_FLAG_ENABLE(e, EDGE_VISIT);
1012
1013 l_iter = l_first = e->l;
1014 do {
1015 if (l_iter->v == v) {
1016 BMEdge *e_other = l_iter->prev->e;
1017 if (!BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) {
1018 BM_ELEM_API_FLAG_ENABLE(l_iter, LOOP_VISIT);
1019 count += 1;
1020 }
1021 if (!BM_ELEM_API_FLAG_TEST(e_other, EDGE_VISIT)) {
1022 count += bm_loop_region_count__recursive(e_other, v);
1023 }
1024 }
1025 else if (l_iter->next->v == v) {
1026 BMEdge *e_other = l_iter->next->e;
1027 if (!BM_ELEM_API_FLAG_TEST(l_iter->next, LOOP_VISIT)) {
1028 BM_ELEM_API_FLAG_ENABLE(l_iter->next, LOOP_VISIT);
1029 count += 1;
1030 }
1031 if (!BM_ELEM_API_FLAG_TEST(e_other, EDGE_VISIT)) {
1032 count += bm_loop_region_count__recursive(e_other, v);
1033 }
1034 }
1035 else {
1036 BLI_assert(0);
1037 }
1038 } while ((l_iter = l_iter->radial_next) != l_first);
1039
1040 return count;
1041 }
1042
bm_loop_region_count__clear(BMLoop * l)1043 static int bm_loop_region_count__clear(BMLoop *l)
1044 {
1045 int count = 0;
1046 BMEdge *e_iter, *e_first;
1047
1048 /* clear flags */
1049 e_iter = e_first = l->e;
1050 do {
1051 BM_ELEM_API_FLAG_DISABLE(e_iter, EDGE_VISIT);
1052 if (e_iter->l) {
1053 BMLoop *l_iter, *l_first;
1054 l_iter = l_first = e_iter->l;
1055 do {
1056 if (l_iter->v == l->v) {
1057 BM_ELEM_API_FLAG_DISABLE(l_iter, LOOP_VISIT);
1058 count += 1;
1059 }
1060 } while ((l_iter = l_iter->radial_next) != l_first);
1061 }
1062 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, l->v)) != e_first);
1063
1064 return count;
1065 }
1066
1067 /**
1068 * The number of loops connected to this loop (not including disconnected regions).
1069 */
BM_loop_region_loops_count_at_most(BMLoop * l,int * r_loop_total)1070 int BM_loop_region_loops_count_at_most(BMLoop *l, int *r_loop_total)
1071 {
1072 const int count = bm_loop_region_count__recursive(l->e, l->v);
1073 const int count_total = bm_loop_region_count__clear(l);
1074 if (r_loop_total) {
1075 *r_loop_total = count_total;
1076 }
1077 return count;
1078 }
1079
1080 #undef LOOP_VISIT
1081 #undef EDGE_VISIT
1082
BM_loop_region_loops_count(BMLoop * l)1083 int BM_loop_region_loops_count(BMLoop *l)
1084 {
1085 return BM_loop_region_loops_count_at_most(l, NULL);
1086 }
1087
1088 /**
1089 * A version of #BM_vert_is_manifold
1090 * which only checks if we're connected to multiple isolated regions.
1091 */
BM_vert_is_manifold_region(const BMVert * v)1092 bool BM_vert_is_manifold_region(const BMVert *v)
1093 {
1094 BMLoop *l_first = BM_vert_find_first_loop((BMVert *)v);
1095 if (l_first) {
1096 int count, count_total;
1097 count = BM_loop_region_loops_count_at_most(l_first, &count_total);
1098 return (count == count_total);
1099 }
1100 return true;
1101 }
1102
1103 /**
1104 * Check if the edge is convex or concave
1105 * (depends on face winding)
1106 */
BM_edge_is_convex(const BMEdge * e)1107 bool BM_edge_is_convex(const BMEdge *e)
1108 {
1109 if (BM_edge_is_manifold(e)) {
1110 BMLoop *l1 = e->l;
1111 BMLoop *l2 = e->l->radial_next;
1112 if (!equals_v3v3(l1->f->no, l2->f->no)) {
1113 float cross[3];
1114 float l_dir[3];
1115 cross_v3_v3v3(cross, l1->f->no, l2->f->no);
1116 /* we assume contiguous normals, otherwise the result isn't meaningful */
1117 sub_v3_v3v3(l_dir, l1->next->v->co, l1->v->co);
1118 return (dot_v3v3(l_dir, cross) > 0.0f);
1119 }
1120 }
1121 return true;
1122 }
1123
1124 /**
1125 * \return true when loop customdata is contiguous.
1126 */
BM_edge_is_contiguous_loop_cd(const BMEdge * e,const int cd_loop_type,const int cd_loop_offset)1127 bool BM_edge_is_contiguous_loop_cd(const BMEdge *e,
1128 const int cd_loop_type,
1129 const int cd_loop_offset)
1130 {
1131 BLI_assert(cd_loop_offset != -1);
1132
1133 if (e->l && e->l->radial_next != e->l) {
1134 const BMLoop *l_base_v1 = e->l;
1135 const BMLoop *l_base_v2 = e->l->next;
1136 const void *l_base_cd_v1 = BM_ELEM_CD_GET_VOID_P(l_base_v1, cd_loop_offset);
1137 const void *l_base_cd_v2 = BM_ELEM_CD_GET_VOID_P(l_base_v2, cd_loop_offset);
1138 const BMLoop *l_iter = e->l->radial_next;
1139 do {
1140 const BMLoop *l_iter_v1;
1141 const BMLoop *l_iter_v2;
1142 const void *l_iter_cd_v1;
1143 const void *l_iter_cd_v2;
1144
1145 if (l_iter->v == l_base_v1->v) {
1146 l_iter_v1 = l_iter;
1147 l_iter_v2 = l_iter->next;
1148 }
1149 else {
1150 l_iter_v1 = l_iter->next;
1151 l_iter_v2 = l_iter;
1152 }
1153 BLI_assert((l_iter_v1->v == l_base_v1->v) && (l_iter_v2->v == l_base_v2->v));
1154
1155 l_iter_cd_v1 = BM_ELEM_CD_GET_VOID_P(l_iter_v1, cd_loop_offset);
1156 l_iter_cd_v2 = BM_ELEM_CD_GET_VOID_P(l_iter_v2, cd_loop_offset);
1157
1158 if ((CustomData_data_equals(cd_loop_type, l_base_cd_v1, l_iter_cd_v1) == 0) ||
1159 (CustomData_data_equals(cd_loop_type, l_base_cd_v2, l_iter_cd_v2) == 0)) {
1160 return false;
1161 }
1162
1163 } while ((l_iter = l_iter->radial_next) != e->l);
1164 }
1165 return true;
1166 }
1167
BM_vert_is_boundary(const BMVert * v)1168 bool BM_vert_is_boundary(const BMVert *v)
1169 {
1170 if (v->e) {
1171 BMEdge *e_first, *e_iter;
1172
1173 e_first = e_iter = v->e;
1174 do {
1175 if (BM_edge_is_boundary(e_iter)) {
1176 return true;
1177 }
1178 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
1179
1180 return false;
1181 }
1182 return false;
1183 }
1184
1185 /**
1186 * Returns the number of faces that are adjacent to both f1 and f2,
1187 * \note Could be sped up a bit by not using iterators and by tagging
1188 * faces on either side, then count the tags rather then searching.
1189 */
BM_face_share_face_count(BMFace * f_a,BMFace * f_b)1190 int BM_face_share_face_count(BMFace *f_a, BMFace *f_b)
1191 {
1192 BMIter iter1, iter2;
1193 BMEdge *e;
1194 BMFace *f;
1195 int count = 0;
1196
1197 BM_ITER_ELEM (e, &iter1, f_a, BM_EDGES_OF_FACE) {
1198 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
1199 if (f != f_a && f != f_b && BM_face_share_edge_check(f, f_b)) {
1200 count++;
1201 }
1202 }
1203 }
1204
1205 return count;
1206 }
1207
1208 /**
1209 * same as #BM_face_share_face_count but returns a bool
1210 */
BM_face_share_face_check(BMFace * f_a,BMFace * f_b)1211 bool BM_face_share_face_check(BMFace *f_a, BMFace *f_b)
1212 {
1213 BMIter iter1, iter2;
1214 BMEdge *e;
1215 BMFace *f;
1216
1217 BM_ITER_ELEM (e, &iter1, f_a, BM_EDGES_OF_FACE) {
1218 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
1219 if (f != f_a && f != f_b && BM_face_share_edge_check(f, f_b)) {
1220 return true;
1221 }
1222 }
1223 }
1224
1225 return false;
1226 }
1227
1228 /**
1229 * Counts the number of edges two faces share (if any)
1230 */
BM_face_share_edge_count(BMFace * f_a,BMFace * f_b)1231 int BM_face_share_edge_count(BMFace *f_a, BMFace *f_b)
1232 {
1233 BMLoop *l_iter;
1234 BMLoop *l_first;
1235 int count = 0;
1236
1237 l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
1238 do {
1239 if (BM_edge_in_face(l_iter->e, f_b)) {
1240 count++;
1241 }
1242 } while ((l_iter = l_iter->next) != l_first);
1243
1244 return count;
1245 }
1246
1247 /**
1248 * Returns true if the faces share an edge
1249 */
BM_face_share_edge_check(BMFace * f1,BMFace * f2)1250 bool BM_face_share_edge_check(BMFace *f1, BMFace *f2)
1251 {
1252 BMLoop *l_iter;
1253 BMLoop *l_first;
1254
1255 l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
1256 do {
1257 if (BM_edge_in_face(l_iter->e, f2)) {
1258 return true;
1259 }
1260 } while ((l_iter = l_iter->next) != l_first);
1261
1262 return false;
1263 }
1264
1265 /**
1266 * Counts the number of verts two faces share (if any).
1267 */
BM_face_share_vert_count(BMFace * f_a,BMFace * f_b)1268 int BM_face_share_vert_count(BMFace *f_a, BMFace *f_b)
1269 {
1270 BMLoop *l_iter;
1271 BMLoop *l_first;
1272 int count = 0;
1273
1274 l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
1275 do {
1276 if (BM_vert_in_face(l_iter->v, f_b)) {
1277 count++;
1278 }
1279 } while ((l_iter = l_iter->next) != l_first);
1280
1281 return count;
1282 }
1283
1284 /**
1285 * Returns true if the faces share a vert.
1286 */
BM_face_share_vert_check(BMFace * f_a,BMFace * f_b)1287 bool BM_face_share_vert_check(BMFace *f_a, BMFace *f_b)
1288 {
1289 BMLoop *l_iter;
1290 BMLoop *l_first;
1291
1292 l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
1293 do {
1294 if (BM_vert_in_face(l_iter->v, f_b)) {
1295 return true;
1296 }
1297 } while ((l_iter = l_iter->next) != l_first);
1298
1299 return false;
1300 }
1301
1302 /**
1303 * Returns true when 2 loops share an edge (are adjacent in the face-fan)
1304 */
BM_loop_share_edge_check(BMLoop * l_a,BMLoop * l_b)1305 bool BM_loop_share_edge_check(BMLoop *l_a, BMLoop *l_b)
1306 {
1307 BLI_assert(l_a->v == l_b->v);
1308 return (ELEM(l_a->e, l_b->e, l_b->prev->e) || ELEM(l_b->e, l_a->e, l_a->prev->e));
1309 }
1310
1311 /**
1312 * Test if e1 shares any faces with e2
1313 */
BM_edge_share_face_check(BMEdge * e1,BMEdge * e2)1314 bool BM_edge_share_face_check(BMEdge *e1, BMEdge *e2)
1315 {
1316 BMLoop *l;
1317 BMFace *f;
1318
1319 if (e1->l && e2->l) {
1320 l = e1->l;
1321 do {
1322 f = l->f;
1323 if (BM_edge_in_face(e2, f)) {
1324 return true;
1325 }
1326 l = l->radial_next;
1327 } while (l != e1->l);
1328 }
1329 return false;
1330 }
1331
1332 /**
1333 * Test if e1 shares any quad faces with e2
1334 */
BM_edge_share_quad_check(BMEdge * e1,BMEdge * e2)1335 bool BM_edge_share_quad_check(BMEdge *e1, BMEdge *e2)
1336 {
1337 BMLoop *l;
1338 BMFace *f;
1339
1340 if (e1->l && e2->l) {
1341 l = e1->l;
1342 do {
1343 f = l->f;
1344 if (f->len == 4) {
1345 if (BM_edge_in_face(e2, f)) {
1346 return true;
1347 }
1348 }
1349 l = l->radial_next;
1350 } while (l != e1->l);
1351 }
1352 return false;
1353 }
1354
1355 /**
1356 * Tests to see if e1 shares a vertex with e2
1357 */
BM_edge_share_vert_check(BMEdge * e1,BMEdge * e2)1358 bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
1359 {
1360 return (e1->v1 == e2->v1 || e1->v1 == e2->v2 || e1->v2 == e2->v1 || e1->v2 == e2->v2);
1361 }
1362
1363 /**
1364 * Return the shared vertex between the two edges or NULL
1365 */
BM_edge_share_vert(BMEdge * e1,BMEdge * e2)1366 BMVert *BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
1367 {
1368 BLI_assert(e1 != e2);
1369 if (BM_vert_in_edge(e2, e1->v1)) {
1370 return e1->v1;
1371 }
1372 if (BM_vert_in_edge(e2, e1->v2)) {
1373 return e1->v2;
1374 }
1375 return NULL;
1376 }
1377
1378 /**
1379 * \brief Return the Loop Shared by Edge and Vert
1380 *
1381 * Finds the loop used which uses \a in face loop \a l
1382 *
1383 * \note this function takes a loop rather than an edge
1384 * so we can select the face that the loop should be from.
1385 */
BM_edge_vert_share_loop(BMLoop * l,BMVert * v)1386 BMLoop *BM_edge_vert_share_loop(BMLoop *l, BMVert *v)
1387 {
1388 BLI_assert(BM_vert_in_edge(l->e, v));
1389 if (l->v == v) {
1390 return l;
1391 }
1392 return l->next;
1393 }
1394
1395 /**
1396 * \brief Return the Loop Shared by Face and Vertex
1397 *
1398 * Finds the loop used which uses \a v in face loop \a l
1399 *
1400 * \note currently this just uses simple loop in future may be sped up
1401 * using radial vars
1402 */
BM_face_vert_share_loop(BMFace * f,BMVert * v)1403 BMLoop *BM_face_vert_share_loop(BMFace *f, BMVert *v)
1404 {
1405 BMLoop *l_first;
1406 BMLoop *l_iter;
1407
1408 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1409 do {
1410 if (l_iter->v == v) {
1411 return l_iter;
1412 }
1413 } while ((l_iter = l_iter->next) != l_first);
1414
1415 return NULL;
1416 }
1417
1418 /**
1419 * \brief Return the Loop Shared by Face and Edge
1420 *
1421 * Finds the loop used which uses \a e in face loop \a l
1422 *
1423 * \note currently this just uses simple loop in future may be sped up
1424 * using radial vars
1425 */
BM_face_edge_share_loop(BMFace * f,BMEdge * e)1426 BMLoop *BM_face_edge_share_loop(BMFace *f, BMEdge *e)
1427 {
1428 BMLoop *l_first;
1429 BMLoop *l_iter;
1430
1431 l_iter = l_first = e->l;
1432 do {
1433 if (l_iter->f == f) {
1434 return l_iter;
1435 }
1436 } while ((l_iter = l_iter->radial_next) != l_first);
1437
1438 return NULL;
1439 }
1440
1441 /**
1442 * Returns the verts of an edge as used in a face
1443 * if used in a face at all, otherwise just assign as used in the edge.
1444 *
1445 * Useful to get a deterministic winding order when calling
1446 * BM_face_create_ngon() on an arbitrary array of verts,
1447 * though be sure to pick an edge which has a face.
1448 *
1449 * \note This is in fact quite a simple check,
1450 * mainly include this function so the intent is more obvious.
1451 * We know these 2 verts will _always_ make up the loops edge
1452 */
BM_edge_ordered_verts_ex(const BMEdge * edge,BMVert ** r_v1,BMVert ** r_v2,const BMLoop * edge_loop)1453 void BM_edge_ordered_verts_ex(const BMEdge *edge,
1454 BMVert **r_v1,
1455 BMVert **r_v2,
1456 const BMLoop *edge_loop)
1457 {
1458 BLI_assert(edge_loop->e == edge);
1459 (void)edge; /* quiet warning in release build */
1460 *r_v1 = edge_loop->v;
1461 *r_v2 = edge_loop->next->v;
1462 }
1463
BM_edge_ordered_verts(const BMEdge * edge,BMVert ** r_v1,BMVert ** r_v2)1464 void BM_edge_ordered_verts(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
1465 {
1466 BM_edge_ordered_verts_ex(edge, r_v1, r_v2, edge->l);
1467 }
1468
1469 /**
1470 * \return The previous loop, over \a eps_sq distance from \a l (or \a NULL if l_stop is reached).
1471 */
BM_loop_find_prev_nodouble(BMLoop * l,BMLoop * l_stop,const float eps_sq)1472 BMLoop *BM_loop_find_prev_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq)
1473 {
1474 BMLoop *l_step = l->prev;
1475
1476 BLI_assert(!ELEM(l_stop, NULL, l));
1477
1478 while (UNLIKELY(len_squared_v3v3(l->v->co, l_step->v->co) < eps_sq)) {
1479 l_step = l_step->prev;
1480 BLI_assert(l_step != l);
1481 if (UNLIKELY(l_step == l_stop)) {
1482 return NULL;
1483 }
1484 }
1485
1486 return l_step;
1487 }
1488
1489 /**
1490 * \return The next loop, over \a eps_sq distance from \a l (or \a NULL if l_stop is reached).
1491 */
BM_loop_find_next_nodouble(BMLoop * l,BMLoop * l_stop,const float eps_sq)1492 BMLoop *BM_loop_find_next_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq)
1493 {
1494 BMLoop *l_step = l->next;
1495
1496 BLI_assert(!ELEM(l_stop, NULL, l));
1497
1498 while (UNLIKELY(len_squared_v3v3(l->v->co, l_step->v->co) < eps_sq)) {
1499 l_step = l_step->next;
1500 BLI_assert(l_step != l);
1501 if (UNLIKELY(l_step == l_stop)) {
1502 return NULL;
1503 }
1504 }
1505
1506 return l_step;
1507 }
1508
1509 /**
1510 * Check if the loop is convex or concave
1511 * (depends on face normal)
1512 */
BM_loop_is_convex(const BMLoop * l)1513 bool BM_loop_is_convex(const BMLoop *l)
1514 {
1515 float e_dir_prev[3];
1516 float e_dir_next[3];
1517 float l_no[3];
1518
1519 sub_v3_v3v3(e_dir_prev, l->prev->v->co, l->v->co);
1520 sub_v3_v3v3(e_dir_next, l->next->v->co, l->v->co);
1521 cross_v3_v3v3(l_no, e_dir_next, e_dir_prev);
1522 return dot_v3v3(l_no, l->f->no) > 0.0f;
1523 }
1524
1525 /**
1526 * Calculates the angle between the previous and next loops
1527 * (angle at this loops face corner).
1528 *
1529 * \return angle in radians
1530 */
BM_loop_calc_face_angle(const BMLoop * l)1531 float BM_loop_calc_face_angle(const BMLoop *l)
1532 {
1533 return angle_v3v3v3(l->prev->v->co, l->v->co, l->next->v->co);
1534 }
1535
1536 /**
1537 * \brief BM_loop_calc_face_normal
1538 *
1539 * Calculate the normal at this loop corner or fallback to the face normal on straight lines.
1540 *
1541 * \param l: The loop to calculate the normal at.
1542 * \param epsilon_sq: Value to avoid numeric errors (1e-5f works well).
1543 * \param r_normal: Resulting normal.
1544 */
BM_loop_calc_face_normal_safe_ex(const BMLoop * l,const float epsilon_sq,float r_normal[3])1545 float BM_loop_calc_face_normal_safe_ex(const BMLoop *l, const float epsilon_sq, float r_normal[3])
1546 {
1547 /* Note: we cannot use result of normal_tri_v3 here to detect colinear vectors
1548 * (vertex on a straight line) from zero value,
1549 * because it does not normalize both vectors before making cross-product.
1550 * Instead of adding two costly normalize computations,
1551 * just check ourselves for colinear case. */
1552 /* Note: FEPSILON might need some finer tweaking at some point?
1553 * Seems to be working OK for now though. */
1554 float v1[3], v2[3], v_tmp[3];
1555 sub_v3_v3v3(v1, l->prev->v->co, l->v->co);
1556 sub_v3_v3v3(v2, l->next->v->co, l->v->co);
1557
1558 const float fac = ((v2[0] == 0.0f) ?
1559 ((v2[1] == 0.0f) ? ((v2[2] == 0.0f) ? 0.0f : v1[2] / v2[2]) :
1560 v1[1] / v2[1]) :
1561 v1[0] / v2[0]);
1562
1563 mul_v3_v3fl(v_tmp, v2, fac);
1564 sub_v3_v3(v_tmp, v1);
1565 if (fac != 0.0f && !is_zero_v3(v1) && len_squared_v3(v_tmp) > epsilon_sq) {
1566 /* Not co-linear, we can compute cross-product and normalize it into normal. */
1567 cross_v3_v3v3(r_normal, v1, v2);
1568 return normalize_v3(r_normal);
1569 }
1570 copy_v3_v3(r_normal, l->f->no);
1571 return 0.0f;
1572 }
1573
1574 /**
1575 * A version of BM_loop_calc_face_normal_safe_ex which takes vertex coordinates.
1576 */
BM_loop_calc_face_normal_safe_vcos_ex(const BMLoop * l,const float normal_fallback[3],float const (* vertexCos)[3],const float epsilon_sq,float r_normal[3])1577 float BM_loop_calc_face_normal_safe_vcos_ex(const BMLoop *l,
1578 const float normal_fallback[3],
1579 float const (*vertexCos)[3],
1580 const float epsilon_sq,
1581 float r_normal[3])
1582 {
1583 const int i_prev = BM_elem_index_get(l->prev->v);
1584 const int i_next = BM_elem_index_get(l->next->v);
1585 const int i = BM_elem_index_get(l->v);
1586
1587 float v1[3], v2[3], v_tmp[3];
1588 sub_v3_v3v3(v1, vertexCos[i_prev], vertexCos[i]);
1589 sub_v3_v3v3(v2, vertexCos[i_next], vertexCos[i]);
1590
1591 const float fac = ((v2[0] == 0.0f) ?
1592 ((v2[1] == 0.0f) ? ((v2[2] == 0.0f) ? 0.0f : v1[2] / v2[2]) :
1593 v1[1] / v2[1]) :
1594 v1[0] / v2[0]);
1595
1596 mul_v3_v3fl(v_tmp, v2, fac);
1597 sub_v3_v3(v_tmp, v1);
1598 if (fac != 0.0f && !is_zero_v3(v1) && len_squared_v3(v_tmp) > epsilon_sq) {
1599 /* Not co-linear, we can compute cross-product and normalize it into normal. */
1600 cross_v3_v3v3(r_normal, v1, v2);
1601 return normalize_v3(r_normal);
1602 }
1603 copy_v3_v3(r_normal, normal_fallback);
1604 return 0.0f;
1605 }
1606
1607 /**
1608 * #BM_loop_calc_face_normal_safe_ex with pre-defined sane epsilon.
1609 *
1610 * Since this doesn't scale based on triangle size, fixed value works well.
1611 */
BM_loop_calc_face_normal_safe(const BMLoop * l,float r_normal[3])1612 float BM_loop_calc_face_normal_safe(const BMLoop *l, float r_normal[3])
1613 {
1614 return BM_loop_calc_face_normal_safe_ex(l, 1e-5f, r_normal);
1615 }
1616
BM_loop_calc_face_normal_safe_vcos(const BMLoop * l,const float normal_fallback[3],float const (* vertexCos)[3],float r_normal[3])1617 float BM_loop_calc_face_normal_safe_vcos(const BMLoop *l,
1618 const float normal_fallback[3],
1619 float const (*vertexCos)[3],
1620 float r_normal[3])
1621
1622 {
1623 return BM_loop_calc_face_normal_safe_vcos_ex(l, normal_fallback, vertexCos, 1e-5f, r_normal);
1624 }
1625
1626 /**
1627 * \brief BM_loop_calc_face_normal
1628 *
1629 * Calculate the normal at this loop corner or fallback to the face normal on straight lines.
1630 *
1631 * \param l: The loop to calculate the normal at
1632 * \param r_normal: Resulting normal
1633 * \return The length of the cross product (double the area).
1634 */
BM_loop_calc_face_normal(const BMLoop * l,float r_normal[3])1635 float BM_loop_calc_face_normal(const BMLoop *l, float r_normal[3])
1636 {
1637 float v1[3], v2[3];
1638 sub_v3_v3v3(v1, l->prev->v->co, l->v->co);
1639 sub_v3_v3v3(v2, l->next->v->co, l->v->co);
1640
1641 cross_v3_v3v3(r_normal, v1, v2);
1642 const float len = normalize_v3(r_normal);
1643 if (UNLIKELY(len == 0.0f)) {
1644 copy_v3_v3(r_normal, l->f->no);
1645 }
1646 return len;
1647 }
1648
1649 /**
1650 * \brief BM_loop_calc_face_direction
1651 *
1652 * Calculate the direction a loop is pointing.
1653 *
1654 * \param l: The loop to calculate the direction at
1655 * \param r_dir: Resulting direction
1656 */
BM_loop_calc_face_direction(const BMLoop * l,float r_dir[3])1657 void BM_loop_calc_face_direction(const BMLoop *l, float r_dir[3])
1658 {
1659 float v_prev[3];
1660 float v_next[3];
1661
1662 sub_v3_v3v3(v_prev, l->v->co, l->prev->v->co);
1663 sub_v3_v3v3(v_next, l->next->v->co, l->v->co);
1664
1665 normalize_v3(v_prev);
1666 normalize_v3(v_next);
1667
1668 add_v3_v3v3(r_dir, v_prev, v_next);
1669 normalize_v3(r_dir);
1670 }
1671
1672 /**
1673 * \brief BM_loop_calc_face_tangent
1674 *
1675 * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1676 * This vector always points inward into the face.
1677 *
1678 * \param l: The loop to calculate the tangent at
1679 * \param r_tangent: Resulting tangent
1680 */
BM_loop_calc_face_tangent(const BMLoop * l,float r_tangent[3])1681 void BM_loop_calc_face_tangent(const BMLoop *l, float r_tangent[3])
1682 {
1683 float v_prev[3];
1684 float v_next[3];
1685 float dir[3];
1686
1687 sub_v3_v3v3(v_prev, l->prev->v->co, l->v->co);
1688 sub_v3_v3v3(v_next, l->v->co, l->next->v->co);
1689
1690 normalize_v3(v_prev);
1691 normalize_v3(v_next);
1692 add_v3_v3v3(dir, v_prev, v_next);
1693
1694 if (compare_v3v3(v_prev, v_next, FLT_EPSILON * 10.0f) == false) {
1695 float nor[3]; /* for this purpose doesn't need to be normalized */
1696 cross_v3_v3v3(nor, v_prev, v_next);
1697 /* concave face check */
1698 if (UNLIKELY(dot_v3v3(nor, l->f->no) < 0.0f)) {
1699 negate_v3(nor);
1700 }
1701 cross_v3_v3v3(r_tangent, dir, nor);
1702 }
1703 else {
1704 /* prev/next are the same - compare with face normal since we don't have one */
1705 cross_v3_v3v3(r_tangent, dir, l->f->no);
1706 }
1707
1708 normalize_v3(r_tangent);
1709 }
1710
1711 /**
1712 * \brief BMESH EDGE/FACE ANGLE
1713 *
1714 * Calculates the angle between two faces.
1715 * Assumes the face normals are correct.
1716 *
1717 * \return angle in radians
1718 */
BM_edge_calc_face_angle_ex(const BMEdge * e,const float fallback)1719 float BM_edge_calc_face_angle_ex(const BMEdge *e, const float fallback)
1720 {
1721 if (BM_edge_is_manifold(e)) {
1722 const BMLoop *l1 = e->l;
1723 const BMLoop *l2 = e->l->radial_next;
1724 return angle_normalized_v3v3(l1->f->no, l2->f->no);
1725 }
1726 return fallback;
1727 }
BM_edge_calc_face_angle(const BMEdge * e)1728 float BM_edge_calc_face_angle(const BMEdge *e)
1729 {
1730 return BM_edge_calc_face_angle_ex(e, DEG2RADF(90.0f));
1731 }
1732
1733 /**
1734 * \brief BMESH EDGE/FACE ANGLE
1735 *
1736 * Calculates the angle between two faces in world space.
1737 * Assumes the face normals are correct.
1738 *
1739 * \return angle in radians
1740 */
BM_edge_calc_face_angle_with_imat3_ex(const BMEdge * e,const float imat3[3][3],const float fallback)1741 float BM_edge_calc_face_angle_with_imat3_ex(const BMEdge *e,
1742 const float imat3[3][3],
1743 const float fallback)
1744 {
1745 if (BM_edge_is_manifold(e)) {
1746 const BMLoop *l1 = e->l;
1747 const BMLoop *l2 = e->l->radial_next;
1748 float no1[3], no2[3];
1749 copy_v3_v3(no1, l1->f->no);
1750 copy_v3_v3(no2, l2->f->no);
1751
1752 mul_transposed_m3_v3(imat3, no1);
1753 mul_transposed_m3_v3(imat3, no2);
1754
1755 normalize_v3(no1);
1756 normalize_v3(no2);
1757
1758 return angle_normalized_v3v3(no1, no2);
1759 }
1760 return fallback;
1761 }
BM_edge_calc_face_angle_with_imat3(const BMEdge * e,const float imat3[3][3])1762 float BM_edge_calc_face_angle_with_imat3(const BMEdge *e, const float imat3[3][3])
1763 {
1764 return BM_edge_calc_face_angle_with_imat3_ex(e, imat3, DEG2RADF(90.0f));
1765 }
1766
1767 /**
1768 * \brief BMESH EDGE/FACE ANGLE
1769 *
1770 * Calculates the angle between two faces.
1771 * Assumes the face normals are correct.
1772 *
1773 * \return angle in radians
1774 */
BM_edge_calc_face_angle_signed_ex(const BMEdge * e,const float fallback)1775 float BM_edge_calc_face_angle_signed_ex(const BMEdge *e, const float fallback)
1776 {
1777 if (BM_edge_is_manifold(e)) {
1778 BMLoop *l1 = e->l;
1779 BMLoop *l2 = e->l->radial_next;
1780 const float angle = angle_normalized_v3v3(l1->f->no, l2->f->no);
1781 return BM_edge_is_convex(e) ? angle : -angle;
1782 }
1783 return fallback;
1784 }
BM_edge_calc_face_angle_signed(const BMEdge * e)1785 float BM_edge_calc_face_angle_signed(const BMEdge *e)
1786 {
1787 return BM_edge_calc_face_angle_signed_ex(e, DEG2RADF(90.0f));
1788 }
1789
1790 /**
1791 * \brief BMESH EDGE/FACE TANGENT
1792 *
1793 * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1794 * This vector always points inward into the face.
1795 *
1796 * \brief BM_edge_calc_face_tangent
1797 * \param e:
1798 * \param e_loop: The loop to calculate the tangent at,
1799 * used to get the face and winding direction.
1800 * \param r_tangent: The loop corner tangent to set
1801 */
1802
BM_edge_calc_face_tangent(const BMEdge * e,const BMLoop * e_loop,float r_tangent[3])1803 void BM_edge_calc_face_tangent(const BMEdge *e, const BMLoop *e_loop, float r_tangent[3])
1804 {
1805 float tvec[3];
1806 BMVert *v1, *v2;
1807 BM_edge_ordered_verts_ex(e, &v1, &v2, e_loop);
1808
1809 sub_v3_v3v3(tvec, v1->co, v2->co); /* use for temp storage */
1810 /* note, we could average the tangents of both loops,
1811 * for non flat ngons it will give a better direction */
1812 cross_v3_v3v3(r_tangent, tvec, e_loop->f->no);
1813 normalize_v3(r_tangent);
1814 }
1815
1816 /**
1817 * \brief BMESH VERT/EDGE ANGLE
1818 *
1819 * Calculates the angle a verts 2 edges.
1820 *
1821 * \returns the angle in radians
1822 */
BM_vert_calc_edge_angle_ex(const BMVert * v,const float fallback)1823 float BM_vert_calc_edge_angle_ex(const BMVert *v, const float fallback)
1824 {
1825 BMEdge *e1, *e2;
1826
1827 /* saves BM_vert_edge_count(v) and and edge iterator,
1828 * get the edges and count them both at once */
1829
1830 if ((e1 = v->e) && (e2 = bmesh_disk_edge_next(e1, v)) && (e1 != e2) &&
1831 /* make sure we come full circle and only have 2 connected edges */
1832 (e1 == bmesh_disk_edge_next(e2, v))) {
1833 BMVert *v1 = BM_edge_other_vert(e1, v);
1834 BMVert *v2 = BM_edge_other_vert(e2, v);
1835
1836 return (float)M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
1837 }
1838 return fallback;
1839 }
1840
BM_vert_calc_edge_angle(const BMVert * v)1841 float BM_vert_calc_edge_angle(const BMVert *v)
1842 {
1843 return BM_vert_calc_edge_angle_ex(v, DEG2RADF(90.0f));
1844 }
1845
1846 /**
1847 * \note this isn't optimal to run on an array of verts,
1848 * see 'solidify_add_thickness' for a function which runs on an array.
1849 */
BM_vert_calc_shell_factor(const BMVert * v)1850 float BM_vert_calc_shell_factor(const BMVert *v)
1851 {
1852 BMIter iter;
1853 BMLoop *l;
1854 float accum_shell = 0.0f;
1855 float accum_angle = 0.0f;
1856
1857 BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) {
1858 const float face_angle = BM_loop_calc_face_angle(l);
1859 accum_shell += shell_v3v3_normalized_to_dist(v->no, l->f->no) * face_angle;
1860 accum_angle += face_angle;
1861 }
1862
1863 if (accum_angle != 0.0f) {
1864 return accum_shell / accum_angle;
1865 }
1866 return 1.0f;
1867 }
1868 /* alternate version of #BM_vert_calc_shell_factor which only
1869 * uses 'hflag' faces, but falls back to all if none found. */
BM_vert_calc_shell_factor_ex(const BMVert * v,const float no[3],const char hflag)1870 float BM_vert_calc_shell_factor_ex(const BMVert *v, const float no[3], const char hflag)
1871 {
1872 BMIter iter;
1873 const BMLoop *l;
1874 float accum_shell = 0.0f;
1875 float accum_angle = 0.0f;
1876 int tot_sel = 0, tot = 0;
1877
1878 BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) {
1879 if (BM_elem_flag_test(l->f, hflag)) { /* <-- main difference to BM_vert_calc_shell_factor! */
1880 const float face_angle = BM_loop_calc_face_angle(l);
1881 accum_shell += shell_v3v3_normalized_to_dist(no, l->f->no) * face_angle;
1882 accum_angle += face_angle;
1883 tot_sel++;
1884 }
1885 tot++;
1886 }
1887
1888 if (accum_angle != 0.0f) {
1889 return accum_shell / accum_angle;
1890 }
1891 /* other main difference from BM_vert_calc_shell_factor! */
1892 if (tot != 0 && tot_sel == 0) {
1893 /* none selected, so use all */
1894 return BM_vert_calc_shell_factor(v);
1895 }
1896 return 1.0f;
1897 }
1898
1899 /**
1900 * \note quite an obscure function.
1901 * used in bmesh operators that have a relative scale options,
1902 */
BM_vert_calc_median_tagged_edge_length(const BMVert * v)1903 float BM_vert_calc_median_tagged_edge_length(const BMVert *v)
1904 {
1905 BMIter iter;
1906 BMEdge *e;
1907 int tot;
1908 float length = 0.0f;
1909
1910 BM_ITER_ELEM_INDEX (e, &iter, (BMVert *)v, BM_EDGES_OF_VERT, tot) {
1911 const BMVert *v_other = BM_edge_other_vert(e, v);
1912 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1913 length += BM_edge_calc_length(e);
1914 }
1915 }
1916
1917 if (tot) {
1918 return length / (float)tot;
1919 }
1920 return 0.0f;
1921 }
1922
1923 /**
1924 * Returns the loop of the shortest edge in f.
1925 */
BM_face_find_shortest_loop(BMFace * f)1926 BMLoop *BM_face_find_shortest_loop(BMFace *f)
1927 {
1928 BMLoop *shortest_loop = NULL;
1929 float shortest_len = FLT_MAX;
1930
1931 BMLoop *l_iter;
1932 BMLoop *l_first;
1933
1934 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1935
1936 do {
1937 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1938 if (len_sq <= shortest_len) {
1939 shortest_loop = l_iter;
1940 shortest_len = len_sq;
1941 }
1942 } while ((l_iter = l_iter->next) != l_first);
1943
1944 return shortest_loop;
1945 }
1946
1947 /**
1948 * Returns the loop of the longest edge in f.
1949 */
BM_face_find_longest_loop(BMFace * f)1950 BMLoop *BM_face_find_longest_loop(BMFace *f)
1951 {
1952 BMLoop *longest_loop = NULL;
1953 float len_max_sq = 0.0f;
1954
1955 BMLoop *l_iter;
1956 BMLoop *l_first;
1957
1958 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1959
1960 do {
1961 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1962 if (len_sq >= len_max_sq) {
1963 longest_loop = l_iter;
1964 len_max_sq = len_sq;
1965 }
1966 } while ((l_iter = l_iter->next) != l_first);
1967
1968 return longest_loop;
1969 }
1970
1971 /**
1972 * Returns the edge existing between \a v_a and \a v_b, or NULL if there isn't one.
1973 *
1974 * \note multiple edges may exist between any two vertices, and therefore
1975 * this function only returns the first one found.
1976 */
1977 #if 0
1978 BMEdge *BM_edge_exists(BMVert *v_a, BMVert *v_b)
1979 {
1980 BMIter iter;
1981 BMEdge *e;
1982
1983 BLI_assert(v_a != v_b);
1984 BLI_assert(v_a->head.htype == BM_VERT && v_b->head.htype == BM_VERT);
1985
1986 BM_ITER_ELEM (e, &iter, v_a, BM_EDGES_OF_VERT) {
1987 if (e->v1 == v_b || e->v2 == v_b) {
1988 return e;
1989 }
1990 }
1991
1992 return NULL;
1993 }
1994 #else
BM_edge_exists(BMVert * v_a,BMVert * v_b)1995 BMEdge *BM_edge_exists(BMVert *v_a, BMVert *v_b)
1996 {
1997 /* speedup by looping over both edges verts
1998 * where one vert may connect to many edges but not the other. */
1999
2000 BMEdge *e_a, *e_b;
2001
2002 BLI_assert(v_a != v_b);
2003 BLI_assert(v_a->head.htype == BM_VERT && v_b->head.htype == BM_VERT);
2004
2005 if ((e_a = v_a->e) && (e_b = v_b->e)) {
2006 BMEdge *e_a_iter = e_a, *e_b_iter = e_b;
2007
2008 do {
2009 if (BM_vert_in_edge(e_a_iter, v_b)) {
2010 return e_a_iter;
2011 }
2012 if (BM_vert_in_edge(e_b_iter, v_a)) {
2013 return e_b_iter;
2014 }
2015 } while (((e_a_iter = bmesh_disk_edge_next(e_a_iter, v_a)) != e_a) &&
2016 ((e_b_iter = bmesh_disk_edge_next(e_b_iter, v_b)) != e_b));
2017 }
2018
2019 return NULL;
2020 }
2021 #endif
2022
2023 /**
2024 * Returns an edge sharing the same vertices as this one.
2025 * This isn't an invalid state but tools should clean up these cases before
2026 * returning the mesh to the user.
2027 */
BM_edge_find_double(BMEdge * e)2028 BMEdge *BM_edge_find_double(BMEdge *e)
2029 {
2030 BMVert *v = e->v1;
2031 BMVert *v_other = e->v2;
2032
2033 BMEdge *e_iter;
2034
2035 e_iter = e;
2036 while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e) {
2037 if (UNLIKELY(BM_vert_in_edge(e_iter, v_other))) {
2038 return e_iter;
2039 }
2040 }
2041
2042 return NULL;
2043 }
2044
2045 /**
2046 * Only #BMEdge.l access us needed, however when we want the first visible loop,
2047 * a utility function is needed.
2048 */
BM_edge_find_first_loop_visible(BMEdge * e)2049 BMLoop *BM_edge_find_first_loop_visible(BMEdge *e)
2050 {
2051 if (e->l != NULL) {
2052 BMLoop *l_iter, *l_first;
2053 l_iter = l_first = e->l;
2054 do {
2055 if (!BM_elem_flag_test(l_iter->f, BM_ELEM_HIDDEN)) {
2056 return l_iter;
2057 }
2058 } while ((l_iter = l_iter->radial_next) != l_first);
2059 }
2060 return NULL;
2061 }
2062
2063 /**
2064 * Given a set of vertices (varr), find out if
2065 * there is a face with exactly those vertices
2066 * (and only those vertices).
2067 *
2068 * \note there used to be a BM_face_exists_overlap function that checks for partial overlap.
2069 */
BM_face_exists(BMVert ** varr,int len)2070 BMFace *BM_face_exists(BMVert **varr, int len)
2071 {
2072 if (varr[0]->e) {
2073 BMEdge *e_iter, *e_first;
2074 e_iter = e_first = varr[0]->e;
2075
2076 /* would normally use BM_LOOPS_OF_VERT, but this runs so often,
2077 * its faster to iterate on the data directly */
2078 do {
2079 if (e_iter->l) {
2080 BMLoop *l_iter_radial, *l_first_radial;
2081 l_iter_radial = l_first_radial = e_iter->l;
2082
2083 do {
2084 if ((l_iter_radial->v == varr[0]) && (l_iter_radial->f->len == len)) {
2085 /* the fist 2 verts match, now check the remaining (len - 2) faces do too
2086 * winding isn't known, so check in both directions */
2087 int i_walk = 2;
2088
2089 if (l_iter_radial->next->v == varr[1]) {
2090 BMLoop *l_walk = l_iter_radial->next->next;
2091 do {
2092 if (l_walk->v != varr[i_walk]) {
2093 break;
2094 }
2095 } while ((void)(l_walk = l_walk->next), ++i_walk != len);
2096 }
2097 else if (l_iter_radial->prev->v == varr[1]) {
2098 BMLoop *l_walk = l_iter_radial->prev->prev;
2099 do {
2100 if (l_walk->v != varr[i_walk]) {
2101 break;
2102 }
2103 } while ((void)(l_walk = l_walk->prev), ++i_walk != len);
2104 }
2105
2106 if (i_walk == len) {
2107 return l_iter_radial->f;
2108 }
2109 }
2110 } while ((l_iter_radial = l_iter_radial->radial_next) != l_first_radial);
2111 }
2112 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, varr[0])) != e_first);
2113 }
2114
2115 return NULL;
2116 }
2117
2118 /**
2119 * Check if the face has an exact duplicate (both winding directions).
2120 */
BM_face_find_double(BMFace * f)2121 BMFace *BM_face_find_double(BMFace *f)
2122 {
2123 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
2124 for (BMLoop *l_iter = l_first->radial_next; l_first != l_iter; l_iter = l_iter->radial_next) {
2125 if (l_iter->f->len == l_first->f->len) {
2126 if (l_iter->v == l_first->v) {
2127 BMLoop *l_a = l_first, *l_b = l_iter, *l_b_init = l_iter;
2128 do {
2129 if (l_a->e != l_b->e) {
2130 break;
2131 }
2132 } while (((void)(l_a = l_a->next), (l_b = l_b->next)) != l_b_init);
2133 if (l_b == l_b_init) {
2134 return l_iter->f;
2135 }
2136 }
2137 else {
2138 BMLoop *l_a = l_first, *l_b = l_iter, *l_b_init = l_iter;
2139 do {
2140 if (l_a->e != l_b->e) {
2141 break;
2142 }
2143 } while (((void)(l_a = l_a->prev), (l_b = l_b->next)) != l_b_init);
2144 if (l_b == l_b_init) {
2145 return l_iter->f;
2146 }
2147 }
2148 }
2149 }
2150 return NULL;
2151 }
2152
2153 /**
2154 * Given a set of vertices and edges (\a varr, \a earr), find out if
2155 * all those vertices are filled in by existing faces that _only_ use those vertices.
2156 *
2157 * This is for use in cases where creating a face is possible but would result in
2158 * many overlapping faces.
2159 *
2160 * An example of how this is used: when 2 tri's are selected that share an edge,
2161 * pressing Fkey would make a new overlapping quad (without a check like this)
2162 *
2163 * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
2164 */
BM_face_exists_multi(BMVert ** varr,BMEdge ** earr,int len)2165 bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
2166 {
2167 BMFace *f;
2168 BMEdge *e;
2169 BMVert *v;
2170 bool ok;
2171 int tot_tag;
2172
2173 BMIter fiter;
2174 BMIter viter;
2175
2176 int i;
2177
2178 for (i = 0; i < len; i++) {
2179 /* save some time by looping over edge faces rather than vert faces
2180 * will still loop over some faces twice but not as many */
2181 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
2182 BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
2183 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
2184 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
2185 }
2186 }
2187
2188 /* clear all edge tags */
2189 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
2190 BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
2191 }
2192 }
2193
2194 /* now tag all verts and edges in the boundary array as true so
2195 * we can know if a face-vert is from our array */
2196 for (i = 0; i < len; i++) {
2197 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
2198 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
2199 }
2200
2201 /* so! boundary is tagged, everything else cleared */
2202
2203 /* 1) tag all faces connected to edges - if all their verts are boundary */
2204 tot_tag = 0;
2205 for (i = 0; i < len; i++) {
2206 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
2207 if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
2208 ok = true;
2209 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
2210 if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
2211 ok = false;
2212 break;
2213 }
2214 }
2215
2216 if (ok) {
2217 /* we only use boundary verts */
2218 BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
2219 tot_tag++;
2220 }
2221 }
2222 else {
2223 /* we already found! */
2224 }
2225 }
2226 }
2227
2228 if (tot_tag == 0) {
2229 /* no faces use only boundary verts, quit early */
2230 ok = false;
2231 goto finally;
2232 }
2233
2234 /* 2) loop over non-boundary edges that use boundary verts,
2235 * check each have 2 tagged faces connected (faces that only use 'varr' verts) */
2236 ok = true;
2237 for (i = 0; i < len; i++) {
2238 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
2239
2240 if (/* non-boundary edge */
2241 BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == false &&
2242 /* ...using boundary verts */
2243 BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) &&
2244 BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG)) {
2245 int tot_face_tag = 0;
2246 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
2247 if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
2248 tot_face_tag++;
2249 }
2250 }
2251
2252 if (tot_face_tag != 2) {
2253 ok = false;
2254 break;
2255 }
2256 }
2257 }
2258
2259 if (ok == false) {
2260 break;
2261 }
2262 }
2263
2264 finally:
2265 /* Cleanup */
2266 for (i = 0; i < len; i++) {
2267 BM_elem_flag_disable(varr[i], BM_ELEM_INTERNAL_TAG);
2268 BM_elem_flag_disable(earr[i], BM_ELEM_INTERNAL_TAG);
2269 }
2270 return ok;
2271 }
2272
2273 /* same as 'BM_face_exists_multi' but built vert array from edges */
BM_face_exists_multi_edge(BMEdge ** earr,int len)2274 bool BM_face_exists_multi_edge(BMEdge **earr, int len)
2275 {
2276 BMVert **varr = BLI_array_alloca(varr, len);
2277
2278 /* first check if verts have edges, if not we can bail out early */
2279 if (!BM_verts_from_edges(varr, earr, len)) {
2280 BMESH_ASSERT(0);
2281 return false;
2282 }
2283
2284 return BM_face_exists_multi(varr, earr, len);
2285 }
2286
2287 /**
2288 * Given a set of vertices (varr), find out if
2289 * all those vertices overlap an existing face.
2290 *
2291 * \note The face may contain other verts \b not in \a varr.
2292 *
2293 * \note Its possible there are more than one overlapping faces,
2294 * in this case the first one found will be returned.
2295 *
2296 * \param varr: Array of unordered verts.
2297 * \param len: \a varr array length.
2298 * \return The face or NULL.
2299 */
2300
BM_face_exists_overlap(BMVert ** varr,const int len)2301 BMFace *BM_face_exists_overlap(BMVert **varr, const int len)
2302 {
2303 BMIter viter;
2304 BMFace *f;
2305 int i;
2306 BMFace *f_overlap = NULL;
2307 LinkNode *f_lnk = NULL;
2308
2309 #ifdef DEBUG
2310 /* check flag isn't already set */
2311 for (i = 0; i < len; i++) {
2312 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2313 BLI_assert(BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0);
2314 }
2315 }
2316 #endif
2317
2318 for (i = 0; i < len; i++) {
2319 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2320 if (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0) {
2321 if (len <= BM_verts_in_face_count(varr, len, f)) {
2322 f_overlap = f;
2323 break;
2324 }
2325
2326 BM_ELEM_API_FLAG_ENABLE(f, _FLAG_OVERLAP);
2327 BLI_linklist_prepend_alloca(&f_lnk, f);
2328 }
2329 }
2330 }
2331
2332 for (; f_lnk; f_lnk = f_lnk->next) {
2333 BM_ELEM_API_FLAG_DISABLE((BMFace *)f_lnk->link, _FLAG_OVERLAP);
2334 }
2335
2336 return f_overlap;
2337 }
2338
2339 /**
2340 * Given a set of vertices (varr), find out if
2341 * there is a face that uses vertices only from this list
2342 * (that the face is a subset or made from the vertices given).
2343 *
2344 * \param varr: Array of unordered verts.
2345 * \param len: varr array length.
2346 */
BM_face_exists_overlap_subset(BMVert ** varr,const int len)2347 bool BM_face_exists_overlap_subset(BMVert **varr, const int len)
2348 {
2349 BMIter viter;
2350 BMFace *f;
2351 bool is_init = false;
2352 bool is_overlap = false;
2353 LinkNode *f_lnk = NULL;
2354
2355 #ifdef DEBUG
2356 /* check flag isn't already set */
2357 for (int i = 0; i < len; i++) {
2358 BLI_assert(BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP) == 0);
2359 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2360 BLI_assert(BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0);
2361 }
2362 }
2363 #endif
2364
2365 for (int i = 0; i < len; i++) {
2366 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
2367 if ((f->len <= len) && (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0)) {
2368 /* check if all vers in this face are flagged*/
2369 BMLoop *l_iter, *l_first;
2370
2371 if (is_init == false) {
2372 is_init = true;
2373 for (int j = 0; j < len; j++) {
2374 BM_ELEM_API_FLAG_ENABLE(varr[j], _FLAG_OVERLAP);
2375 }
2376 }
2377
2378 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2379 is_overlap = true;
2380 do {
2381 if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP) == 0) {
2382 is_overlap = false;
2383 break;
2384 }
2385 } while ((l_iter = l_iter->next) != l_first);
2386
2387 if (is_overlap) {
2388 break;
2389 }
2390
2391 BM_ELEM_API_FLAG_ENABLE(f, _FLAG_OVERLAP);
2392 BLI_linklist_prepend_alloca(&f_lnk, f);
2393 }
2394 }
2395 }
2396
2397 if (is_init == true) {
2398 for (int i = 0; i < len; i++) {
2399 BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
2400 }
2401 }
2402
2403 for (; f_lnk; f_lnk = f_lnk->next) {
2404 BM_ELEM_API_FLAG_DISABLE((BMFace *)f_lnk->link, _FLAG_OVERLAP);
2405 }
2406
2407 return is_overlap;
2408 }
2409
BM_vert_is_all_edge_flag_test(const BMVert * v,const char hflag,const bool respect_hide)2410 bool BM_vert_is_all_edge_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
2411 {
2412 if (v->e) {
2413 BMEdge *e_other;
2414 BMIter eiter;
2415
2416 BM_ITER_ELEM (e_other, &eiter, (BMVert *)v, BM_EDGES_OF_VERT) {
2417 if (!respect_hide || !BM_elem_flag_test(e_other, BM_ELEM_HIDDEN)) {
2418 if (!BM_elem_flag_test(e_other, hflag)) {
2419 return false;
2420 }
2421 }
2422 }
2423 }
2424
2425 return true;
2426 }
2427
BM_vert_is_all_face_flag_test(const BMVert * v,const char hflag,const bool respect_hide)2428 bool BM_vert_is_all_face_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
2429 {
2430 if (v->e) {
2431 BMEdge *f_other;
2432 BMIter fiter;
2433
2434 BM_ITER_ELEM (f_other, &fiter, (BMVert *)v, BM_FACES_OF_VERT) {
2435 if (!respect_hide || !BM_elem_flag_test(f_other, BM_ELEM_HIDDEN)) {
2436 if (!BM_elem_flag_test(f_other, hflag)) {
2437 return false;
2438 }
2439 }
2440 }
2441 }
2442
2443 return true;
2444 }
2445
BM_edge_is_all_face_flag_test(const BMEdge * e,const char hflag,const bool respect_hide)2446 bool BM_edge_is_all_face_flag_test(const BMEdge *e, const char hflag, const bool respect_hide)
2447 {
2448 if (e->l) {
2449 BMLoop *l_iter, *l_first;
2450
2451 l_iter = l_first = e->l;
2452 do {
2453 if (!respect_hide || !BM_elem_flag_test(l_iter->f, BM_ELEM_HIDDEN)) {
2454 if (!BM_elem_flag_test(l_iter->f, hflag)) {
2455 return false;
2456 }
2457 }
2458 } while ((l_iter = l_iter->radial_next) != l_first);
2459 }
2460
2461 return true;
2462 }
2463
BM_edge_is_any_face_flag_test(const BMEdge * e,const char hflag)2464 bool BM_edge_is_any_face_flag_test(const BMEdge *e, const char hflag)
2465 {
2466 if (e->l) {
2467 BMLoop *l_iter, *l_first;
2468
2469 l_iter = l_first = e->l;
2470 do {
2471 if (BM_elem_flag_test(l_iter->f, hflag)) {
2472 return true;
2473 }
2474 } while ((l_iter = l_iter->radial_next) != l_first);
2475 }
2476
2477 return false;
2478 }
2479
2480 /* convenience functions for checking flags */
BM_edge_is_any_vert_flag_test(const BMEdge * e,const char hflag)2481 bool BM_edge_is_any_vert_flag_test(const BMEdge *e, const char hflag)
2482 {
2483 return (BM_elem_flag_test(e->v1, hflag) || BM_elem_flag_test(e->v2, hflag));
2484 }
2485
BM_face_is_any_vert_flag_test(const BMFace * f,const char hflag)2486 bool BM_face_is_any_vert_flag_test(const BMFace *f, const char hflag)
2487 {
2488 BMLoop *l_iter;
2489 BMLoop *l_first;
2490
2491 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2492 do {
2493 if (BM_elem_flag_test(l_iter->v, hflag)) {
2494 return true;
2495 }
2496 } while ((l_iter = l_iter->next) != l_first);
2497 return false;
2498 }
2499
BM_face_is_any_edge_flag_test(const BMFace * f,const char hflag)2500 bool BM_face_is_any_edge_flag_test(const BMFace *f, const char hflag)
2501 {
2502 BMLoop *l_iter;
2503 BMLoop *l_first;
2504
2505 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2506 do {
2507 if (BM_elem_flag_test(l_iter->e, hflag)) {
2508 return true;
2509 }
2510 } while ((l_iter = l_iter->next) != l_first);
2511 return false;
2512 }
2513
BM_edge_is_any_face_len_test(const BMEdge * e,const int len)2514 bool BM_edge_is_any_face_len_test(const BMEdge *e, const int len)
2515 {
2516 if (e->l) {
2517 BMLoop *l_iter, *l_first;
2518
2519 l_iter = l_first = e->l;
2520 do {
2521 if (l_iter->f->len == len) {
2522 return true;
2523 }
2524 } while ((l_iter = l_iter->radial_next) != l_first);
2525 }
2526
2527 return false;
2528 }
2529
2530 /**
2531 * Use within assert's to check normals are valid.
2532 */
BM_face_is_normal_valid(const BMFace * f)2533 bool BM_face_is_normal_valid(const BMFace *f)
2534 {
2535 const float eps = 0.0001f;
2536 float no[3];
2537
2538 BM_face_calc_normal(f, no);
2539 return len_squared_v3v3(no, f->no) < (eps * eps);
2540 }
2541
2542 /**
2543 * Use to accumulate volume calculation for faces with consistent winding.
2544 *
2545 * Use double precision since this is prone to float precision error, see T73295.
2546 */
bm_mesh_calc_volume_face(const BMFace * f)2547 static double bm_mesh_calc_volume_face(const BMFace *f)
2548 {
2549 const int tottri = f->len - 2;
2550 BMLoop **loops = BLI_array_alloca(loops, f->len);
2551 uint(*index)[3] = BLI_array_alloca(index, tottri);
2552 double vol = 0.0;
2553
2554 BM_face_calc_tessellation(f, false, loops, index);
2555
2556 for (int j = 0; j < tottri; j++) {
2557 const float *p1 = loops[index[j][0]]->v->co;
2558 const float *p2 = loops[index[j][1]]->v->co;
2559 const float *p3 = loops[index[j][2]]->v->co;
2560
2561 double p1_db[3];
2562 double p2_db[3];
2563 double p3_db[3];
2564
2565 copy_v3db_v3fl(p1_db, p1);
2566 copy_v3db_v3fl(p2_db, p2);
2567 copy_v3db_v3fl(p3_db, p3);
2568
2569 /* co1.dot(co2.cross(co3)) / 6.0 */
2570 double cross[3];
2571 cross_v3_v3v3_db(cross, p2_db, p3_db);
2572 vol += dot_v3v3_db(p1_db, cross);
2573 }
2574 return (1.0 / 6.0) * vol;
2575 }
BM_mesh_calc_volume(BMesh * bm,bool is_signed)2576 double BM_mesh_calc_volume(BMesh *bm, bool is_signed)
2577 {
2578 /* warning, calls own tessellation function, may be slow */
2579 double vol = 0.0;
2580 BMFace *f;
2581 BMIter fiter;
2582
2583 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
2584 vol += bm_mesh_calc_volume_face(f);
2585 }
2586
2587 if (is_signed == false) {
2588 vol = fabs(vol);
2589 }
2590
2591 return vol;
2592 }
2593
2594 /* note, almost duplicate of BM_mesh_calc_edge_groups, keep in sync */
2595 /**
2596 * Calculate isolated groups of faces with optional filtering.
2597 *
2598 * \param bm: the BMesh.
2599 * \param r_groups_array: Array of ints to fill in, length of bm->totface
2600 * (or when hflag_test is set, the number of flagged faces).
2601 * \param r_group_index: index, length pairs into \a r_groups_array, size of return value
2602 * int pairs: (array_start, array_length).
2603 * \param filter_fn: Filter the edge-loops or vert-loops we step over (depends on \a htype_step).
2604 * \param user_data: Optional user data for \a filter_fn, can be NULL.
2605 * \param hflag_test: Optional flag to test faces,
2606 * use to exclude faces from the calculation, 0 for all faces.
2607 * \param htype_step: BM_VERT to walk over face-verts, BM_EDGE to walk over faces edges
2608 * (having both set is supported too).
2609 * \return The number of groups found.
2610 */
BM_mesh_calc_face_groups(BMesh * bm,int * r_groups_array,int (** r_group_index)[2],BMLoopFilterFunc filter_fn,BMLoopPairFilterFunc filter_pair_fn,void * user_data,const char hflag_test,const char htype_step)2611 int BM_mesh_calc_face_groups(BMesh *bm,
2612 int *r_groups_array,
2613 int (**r_group_index)[2],
2614 BMLoopFilterFunc filter_fn,
2615 BMLoopPairFilterFunc filter_pair_fn,
2616 void *user_data,
2617 const char hflag_test,
2618 const char htype_step)
2619 {
2620 #ifdef DEBUG
2621 int group_index_len = 1;
2622 #else
2623 int group_index_len = 32;
2624 #endif
2625
2626 int(*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
2627
2628 int *group_array = r_groups_array;
2629 STACK_DECLARE(group_array);
2630
2631 int group_curr = 0;
2632
2633 uint tot_faces = 0;
2634 uint tot_touch = 0;
2635
2636 BMFace **stack;
2637 STACK_DECLARE(stack);
2638
2639 BMIter iter;
2640 BMFace *f;
2641 int i;
2642
2643 STACK_INIT(group_array, bm->totface);
2644
2645 BLI_assert(((htype_step & ~(BM_VERT | BM_EDGE)) == 0) && (htype_step != 0));
2646
2647 /* init the array */
2648 BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
2649 if ((hflag_test == 0) || BM_elem_flag_test(f, hflag_test)) {
2650 tot_faces++;
2651 BM_elem_flag_disable(f, BM_ELEM_TAG);
2652 }
2653 else {
2654 /* never walk over tagged */
2655 BM_elem_flag_enable(f, BM_ELEM_TAG);
2656 }
2657
2658 BM_elem_index_set(f, i); /* set_inline */
2659 }
2660 bm->elem_index_dirty &= ~BM_FACE;
2661
2662 /* detect groups */
2663 stack = MEM_mallocN(sizeof(*stack) * tot_faces, __func__);
2664
2665 while (tot_touch != tot_faces) {
2666 int *group_item;
2667 bool ok = false;
2668
2669 BLI_assert(tot_touch < tot_faces);
2670
2671 STACK_INIT(stack, tot_faces);
2672
2673 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
2674 if (BM_elem_flag_test(f, BM_ELEM_TAG) == false) {
2675 BM_elem_flag_enable(f, BM_ELEM_TAG);
2676 STACK_PUSH(stack, f);
2677 ok = true;
2678 break;
2679 }
2680 }
2681
2682 BLI_assert(ok == true);
2683 UNUSED_VARS_NDEBUG(ok);
2684
2685 /* manage arrays */
2686 if (group_index_len == group_curr) {
2687 group_index_len *= 2;
2688 group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
2689 }
2690
2691 group_item = group_index[group_curr];
2692 group_item[0] = STACK_SIZE(group_array);
2693 group_item[1] = 0;
2694
2695 while ((f = STACK_POP(stack))) {
2696 BMLoop *l_iter, *l_first;
2697
2698 /* add face */
2699 STACK_PUSH(group_array, BM_elem_index_get(f));
2700 tot_touch++;
2701 group_item[1]++;
2702 /* done */
2703
2704 if (htype_step & BM_EDGE) {
2705 /* search for other faces */
2706 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2707 do {
2708 BMLoop *l_radial_iter = l_iter->radial_next;
2709 if ((l_radial_iter != l_iter) && ((filter_fn == NULL) || filter_fn(l_iter, user_data))) {
2710 do {
2711 if ((filter_pair_fn == NULL) || filter_pair_fn(l_iter, l_radial_iter, user_data)) {
2712 BMFace *f_other = l_radial_iter->f;
2713 if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
2714 BM_elem_flag_enable(f_other, BM_ELEM_TAG);
2715 STACK_PUSH(stack, f_other);
2716 }
2717 }
2718 } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
2719 }
2720 } while ((l_iter = l_iter->next) != l_first);
2721 }
2722
2723 if (htype_step & BM_VERT) {
2724 BMIter liter;
2725 /* search for other faces */
2726 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2727 do {
2728 if ((filter_fn == NULL) || filter_fn(l_iter, user_data)) {
2729 BMLoop *l_other;
2730 BM_ITER_ELEM (l_other, &liter, l_iter, BM_LOOPS_OF_LOOP) {
2731 if ((filter_pair_fn == NULL) || filter_pair_fn(l_iter, l_other, user_data)) {
2732 BMFace *f_other = l_other->f;
2733 if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
2734 BM_elem_flag_enable(f_other, BM_ELEM_TAG);
2735 STACK_PUSH(stack, f_other);
2736 }
2737 }
2738 }
2739 }
2740 } while ((l_iter = l_iter->next) != l_first);
2741 }
2742 }
2743
2744 group_curr++;
2745 }
2746
2747 MEM_freeN(stack);
2748
2749 /* reduce alloc to required size */
2750 group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
2751 *r_group_index = group_index;
2752
2753 return group_curr;
2754 }
2755
2756 /* note, almost duplicate of BM_mesh_calc_face_groups, keep in sync */
2757 /**
2758 * Calculate isolated groups of edges with optional filtering.
2759 *
2760 * \param bm: the BMesh.
2761 * \param r_groups_array: Array of ints to fill in, length of bm->totedge
2762 * (or when hflag_test is set, the number of flagged edges).
2763 * \param r_group_index: index, length pairs into \a r_groups_array, size of return value
2764 * int pairs: (array_start, array_length).
2765 * \param filter_fn: Filter the edges or verts we step over (depends on \a htype_step)
2766 * as to which types we deal with.
2767 * \param user_data: Optional user data for \a filter_fn, can be NULL.
2768 * \param hflag_test: Optional flag to test edges,
2769 * use to exclude edges from the calculation, 0 for all edges.
2770 * \return The number of groups found.
2771 *
2772 * \note Unlike #BM_mesh_calc_face_groups there is no 'htype_step' argument,
2773 * since we always walk over verts.
2774 */
BM_mesh_calc_edge_groups(BMesh * bm,int * r_groups_array,int (** r_group_index)[2],BMVertFilterFunc filter_fn,void * user_data,const char hflag_test)2775 int BM_mesh_calc_edge_groups(BMesh *bm,
2776 int *r_groups_array,
2777 int (**r_group_index)[2],
2778 BMVertFilterFunc filter_fn,
2779 void *user_data,
2780 const char hflag_test)
2781 {
2782 #ifdef DEBUG
2783 int group_index_len = 1;
2784 #else
2785 int group_index_len = 32;
2786 #endif
2787
2788 int(*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
2789
2790 int *group_array = r_groups_array;
2791 STACK_DECLARE(group_array);
2792
2793 int group_curr = 0;
2794
2795 uint tot_edges = 0;
2796 uint tot_touch = 0;
2797
2798 BMEdge **stack;
2799 STACK_DECLARE(stack);
2800
2801 BMIter iter;
2802 BMEdge *e;
2803 int i;
2804
2805 STACK_INIT(group_array, bm->totedge);
2806
2807 /* init the array */
2808 BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
2809 if ((hflag_test == 0) || BM_elem_flag_test(e, hflag_test)) {
2810 tot_edges++;
2811 BM_elem_flag_disable(e, BM_ELEM_TAG);
2812 }
2813 else {
2814 /* never walk over tagged */
2815 BM_elem_flag_enable(e, BM_ELEM_TAG);
2816 }
2817
2818 BM_elem_index_set(e, i); /* set_inline */
2819 }
2820 bm->elem_index_dirty &= ~BM_EDGE;
2821
2822 /* detect groups */
2823 stack = MEM_mallocN(sizeof(*stack) * tot_edges, __func__);
2824
2825 while (tot_touch != tot_edges) {
2826 int *group_item;
2827 bool ok = false;
2828
2829 BLI_assert(tot_touch < tot_edges);
2830
2831 STACK_INIT(stack, tot_edges);
2832
2833 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
2834 if (BM_elem_flag_test(e, BM_ELEM_TAG) == false) {
2835 BM_elem_flag_enable(e, BM_ELEM_TAG);
2836 STACK_PUSH(stack, e);
2837 ok = true;
2838 break;
2839 }
2840 }
2841
2842 BLI_assert(ok == true);
2843 UNUSED_VARS_NDEBUG(ok);
2844
2845 /* manage arrays */
2846 if (group_index_len == group_curr) {
2847 group_index_len *= 2;
2848 group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
2849 }
2850
2851 group_item = group_index[group_curr];
2852 group_item[0] = STACK_SIZE(group_array);
2853 group_item[1] = 0;
2854
2855 while ((e = STACK_POP(stack))) {
2856 BMIter viter;
2857 BMIter eiter;
2858 BMVert *v;
2859
2860 /* add edge */
2861 STACK_PUSH(group_array, BM_elem_index_get(e));
2862 tot_touch++;
2863 group_item[1]++;
2864 /* done */
2865
2866 /* search for other edges */
2867 BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
2868 if ((filter_fn == NULL) || filter_fn(v, user_data)) {
2869 BMEdge *e_other;
2870 BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
2871 if (BM_elem_flag_test(e_other, BM_ELEM_TAG) == false) {
2872 BM_elem_flag_enable(e_other, BM_ELEM_TAG);
2873 STACK_PUSH(stack, e_other);
2874 }
2875 }
2876 }
2877 }
2878 }
2879
2880 group_curr++;
2881 }
2882
2883 MEM_freeN(stack);
2884
2885 /* reduce alloc to required size */
2886 group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
2887 *r_group_index = group_index;
2888
2889 return group_curr;
2890 }
2891
2892 /**
2893 * This is an alternative to #BM_mesh_calc_edge_groups.
2894 *
2895 * While we could call this, then create vertex & face arrays,
2896 * it requires looping over geometry connectivity twice,
2897 * this slows down edit-mesh separate by loose parts, see: T70864.
2898 */
BM_mesh_calc_edge_groups_as_arrays(BMesh * bm,BMVert ** verts,BMEdge ** edges,BMFace ** faces,int (** r_groups)[3])2899 int BM_mesh_calc_edge_groups_as_arrays(
2900 BMesh *bm, BMVert **verts, BMEdge **edges, BMFace **faces, int (**r_groups)[3])
2901 {
2902 int(*groups)[3] = MEM_mallocN(sizeof(*groups) * bm->totvert, __func__);
2903 STACK_DECLARE(groups);
2904 STACK_INIT(groups, bm->totvert);
2905
2906 /* Clear all selected vertices */
2907 BM_mesh_elem_hflag_disable_all(bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_TAG, false);
2908
2909 BMVert **stack = MEM_mallocN(sizeof(*stack) * bm->totvert, __func__);
2910 STACK_DECLARE(stack);
2911 STACK_INIT(stack, bm->totvert);
2912
2913 STACK_DECLARE(verts);
2914 STACK_INIT(verts, bm->totvert);
2915
2916 STACK_DECLARE(edges);
2917 STACK_INIT(edges, bm->totedge);
2918
2919 STACK_DECLARE(faces);
2920 STACK_INIT(faces, bm->totface);
2921
2922 BMIter iter;
2923 BMVert *v_stack_init;
2924 BM_ITER_MESH (v_stack_init, &iter, bm, BM_VERTS_OF_MESH) {
2925 if (BM_elem_flag_test(v_stack_init, BM_ELEM_TAG)) {
2926 continue;
2927 }
2928
2929 const uint verts_init = STACK_SIZE(verts);
2930 const uint edges_init = STACK_SIZE(edges);
2931 const uint faces_init = STACK_SIZE(faces);
2932
2933 /* Initialize stack. */
2934 BM_elem_flag_enable(v_stack_init, BM_ELEM_TAG);
2935 STACK_PUSH(verts, v_stack_init);
2936
2937 if (v_stack_init->e != NULL) {
2938 BMVert *v_iter = v_stack_init;
2939 do {
2940 BMEdge *e_iter, *e_first;
2941 e_iter = e_first = v_iter->e;
2942 do {
2943 if (!BM_elem_flag_test(e_iter, BM_ELEM_TAG)) {
2944 BM_elem_flag_enable(e_iter, BM_ELEM_TAG);
2945 STACK_PUSH(edges, e_iter);
2946
2947 if (e_iter->l != NULL) {
2948 BMLoop *l_iter, *l_first;
2949 l_iter = l_first = e_iter->l;
2950 do {
2951 if (!BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
2952 BM_elem_flag_enable(l_iter->f, BM_ELEM_TAG);
2953 STACK_PUSH(faces, l_iter->f);
2954 }
2955 } while ((l_iter = l_iter->radial_next) != l_first);
2956 }
2957
2958 BMVert *v_other = BM_edge_other_vert(e_iter, v_iter);
2959 if (!BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
2960 BM_elem_flag_enable(v_other, BM_ELEM_TAG);
2961 STACK_PUSH(verts, v_other);
2962
2963 STACK_PUSH(stack, v_other);
2964 }
2965 }
2966 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_iter)) != e_first);
2967 } while ((v_iter = STACK_POP(stack)));
2968 }
2969
2970 int *g = STACK_PUSH_RET(groups);
2971 g[0] = STACK_SIZE(verts) - verts_init;
2972 g[1] = STACK_SIZE(edges) - edges_init;
2973 g[2] = STACK_SIZE(faces) - faces_init;
2974 }
2975
2976 MEM_freeN(stack);
2977
2978 /* Reduce alloc to required size. */
2979 groups = MEM_reallocN(groups, sizeof(*groups) * STACK_SIZE(groups));
2980 *r_groups = groups;
2981 return STACK_SIZE(groups);
2982 }
2983
bmesh_subd_falloff_calc(const int falloff,float val)2984 float bmesh_subd_falloff_calc(const int falloff, float val)
2985 {
2986 switch (falloff) {
2987 case SUBD_FALLOFF_SMOOTH:
2988 val = 3.0f * val * val - 2.0f * val * val * val;
2989 break;
2990 case SUBD_FALLOFF_SPHERE:
2991 val = sqrtf(2.0f * val - val * val);
2992 break;
2993 case SUBD_FALLOFF_ROOT:
2994 val = sqrtf(val);
2995 break;
2996 case SUBD_FALLOFF_SHARP:
2997 val = val * val;
2998 break;
2999 case SUBD_FALLOFF_LIN:
3000 break;
3001 case SUBD_FALLOFF_INVSQUARE:
3002 val = val * (2.0f - val);
3003 break;
3004 default:
3005 BLI_assert(0);
3006 break;
3007 }
3008
3009 return val;
3010 }
3011