Blender V5.3
bmesh_query.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
15
16#include <array>
17
18#include "MEM_guardedalloc.h"
19
20#include "BLI_array.hh"
21#include "BLI_linklist.hh"
22#include "BLI_math_base_c.hh"
23#include "BLI_math_geom_c.hh"
24#include "BLI_math_matrix_c.hh"
26#include "BLI_math_vector_c.hh"
28
29#include "BKE_customdata.hh"
30
31#include "bmesh.hh"
33
34namespace blender {
35
42
44{
46 return l->v == v ? l->prev : l->next;
47}
48
50{
51 BMLoop *l_iter = BM_face_vert_share_loop(f, v);
52
53 BLI_assert(BM_edge_exists(v_prev, v) != nullptr);
54
55 if (l_iter) {
56 if (l_iter->prev->v == v_prev) {
57 return l_iter->next;
58 }
59 if (l_iter->next->v == v_prev) {
60 return l_iter->prev;
61 }
62 /* invalid args */
63 BLI_assert(0);
64 return nullptr;
65 }
66 /* invalid args */
67 BLI_assert(0);
68 return nullptr;
69}
70
72{
73#if 0 /* works but slow */
75#else
76 BMEdge *e = l->e;
77 BMVert *v_prev = BM_edge_other_vert(e, v);
78 if (l->v == v) {
79 if (l->prev->v == v_prev) {
80 return l->next;
81 }
82 BLI_assert(l->next->v == v_prev);
83
84 return l->prev;
85 }
86 BLI_assert(l->v == v_prev);
87
88 if (l->prev->v == v) {
89 return l->prev->prev;
90 }
91 BLI_assert(l->next->v == v);
92 return l->next->next;
93#endif
94}
95
97{
99 if (l->e == e) {
100 return l->next;
101 }
102 if (l->prev->e == e) {
103 return l->prev;
104 }
105
106 BLI_assert(0);
107 return nullptr;
108}
109
111{
112 if (v_a->e && v_b->e) {
113 BMIter iter;
114 BMFace *f;
115
116 BM_ITER_ELEM (f, &iter, v_a, BM_FACES_OF_VERT) {
117 if (BM_vert_in_face(v_b, f)) {
118 return true;
119 }
120 }
121 }
122
123 return false;
124}
125
127 BMVert *v_b,
128 bool (*test_fn)(BMFace *, void *user_data),
129 void *user_data)
130{
131 if (v_a->e && v_b->e) {
132 BMIter iter;
133 BMFace *f;
134
135 BM_ITER_ELEM (f, &iter, v_a, BM_FACES_OF_VERT) {
136 if (test_fn(f, user_data)) {
137 if (BM_vert_in_face(v_b, f)) {
138 return true;
139 }
140 }
141 }
142 }
143
144 return false;
145}
146
148 BMVert *v_b,
149 const bool allow_adjacent,
150 bool (*callback)(BMFace *, BMLoop *, BMLoop *, void *userdata),
151 void *user_data,
152 BMLoop **r_l_a,
153 BMLoop **r_l_b)
154{
155 if (v_a->e && v_b->e) {
156 BMIter iter;
157 BMLoop *l_a, *l_b;
158
159 BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
160 BMFace *f = l_a->f;
162 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b)) &&
163 callback(f, l_a, l_b, user_data))
164 {
165 *r_l_a = l_a;
166 *r_l_b = l_b;
167
168 return f;
169 }
170 }
171 }
172
173 return nullptr;
174}
175
177 BMVert *v_a, BMVert *v_b, BMLoop **r_l_a, BMLoop **r_l_b, const bool allow_adjacent)
178{
179 BMLoop *l_cur_a = nullptr, *l_cur_b = nullptr;
180 BMFace *f_cur = nullptr;
181
182 if (v_a->e && v_b->e) {
183 BMIter iter;
184 BMLoop *l_a, *l_b;
185
186 BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
187 if ((f_cur == nullptr) || (l_a->f->len < f_cur->len)) {
188 l_b = BM_face_vert_share_loop(l_a->f, v_b);
189 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
190 f_cur = l_a->f;
191 l_cur_a = l_a;
192 l_cur_b = l_b;
193 }
194 }
195 }
196 }
197
198 *r_l_a = l_cur_a;
199 *r_l_b = l_cur_b;
200
201 return f_cur;
202}
203
205 BMEdge *e_a, BMEdge *e_b, BMLoop **r_l_a, BMLoop **r_l_b, const bool allow_adjacent)
206{
207 BMLoop *l_cur_a = nullptr, *l_cur_b = nullptr;
208 BMFace *f_cur = nullptr;
209
210 if (e_a->l && e_b->l) {
211 BMIter iter;
212 BMLoop *l_a, *l_b;
213
214 BM_ITER_ELEM (l_a, &iter, e_a, BM_LOOPS_OF_EDGE) {
215 if ((f_cur == nullptr) || (l_a->f->len < f_cur->len)) {
216 l_b = BM_face_edge_share_loop(l_a->f, e_b);
217 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
218 f_cur = l_a->f;
219 l_cur_a = l_a;
220 l_cur_b = l_b;
221 }
222 }
223 }
224 }
225
226 *r_l_a = l_cur_a;
227 *r_l_b = l_cur_b;
228
229 return f_cur;
230}
231
233{
234 float no[2][3];
235
236 if ((BM_face_calc_normal_subset(l_a, l_b, no[0]) != 0.0f) &&
237 (BM_face_calc_normal_subset(l_b, l_a, no[1]) != 0.0f))
238 {
239 return dot_v3v3(no[0], no[1]);
240 }
241 return -1.0f;
242}
243
244float BM_loop_point_side_of_loop_test(const BMLoop *l, const float co[3])
245{
246 const float *axis = l->f->no;
247 return dist_signed_squared_to_corner_v3v3v3(co, l->prev->v->co, l->v->co, l->next->v->co, axis);
248}
249
250float BM_loop_point_side_of_edge_test(const BMLoop *l, const float co[3])
251{
252 const float *axis = l->f->no;
253 float dir[3];
254 float plane[4];
255
256 sub_v3_v3v3(dir, l->next->v->co, l->v->co);
257 cross_v3_v3v3(plane, axis, dir);
258
259 plane[3] = -dot_v3v3(plane, l->v->co);
260 return dist_signed_squared_to_plane_v3(co, plane);
261}
262
264 BMVert *v_a, BMVert *v_b, BMLoop **r_l_a, BMLoop **r_l_b, const bool allow_adjacent)
265{
266 BMLoop *l_cur_a = nullptr, *l_cur_b = nullptr;
267 BMFace *f_cur = nullptr;
268
269 if (v_a->e && v_b->e) {
270 BMIter iter;
271 BMLoop *l_a, *l_b;
272 float dot_best = -1.0f;
273
274 BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
275 l_b = BM_face_vert_share_loop(l_a->f, v_b);
276 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
277
278 if (f_cur == nullptr) {
279 f_cur = l_a->f;
280 l_cur_a = l_a;
281 l_cur_b = l_b;
282 }
283 else {
284 /* avoid expensive calculations if we only ever find one face */
285 float dot;
286 if (dot_best == -1.0f) {
287 dot_best = bm_face_calc_split_dot(l_cur_a, l_cur_b);
288 }
289
291 if (dot > dot_best) {
292 dot_best = dot;
293
294 f_cur = l_a->f;
295 l_cur_a = l_a;
296 l_cur_b = l_b;
297 }
298 }
299 }
300 }
301 }
302
303 *r_l_a = l_cur_a;
304 *r_l_b = l_cur_b;
305
306 return f_cur;
307}
308
310{
311 return v->e ? bmesh_disk_faceloop_find_first(v->e, v) : nullptr;
312}
317
319{
320 BMLoop *l_iter, *l_first;
321
322#ifdef USE_BMESH_HOLES
323 BMLoopList *lst;
324 for (lst = f->loops.first; lst; lst = lst->next)
325#endif
326 {
327#ifdef USE_BMESH_HOLES
328 l_iter = l_first = lst->first;
329#else
330 l_iter = l_first = f->l_first;
331#endif
332 do {
333 if (l_iter->v == v) {
334 return true;
335 }
336 } while ((l_iter = l_iter->next) != l_first);
337 }
338
339 return false;
340}
341
343{
344 BMLoop *l_iter, *l_first;
345
346#ifdef USE_BMESH_HOLES
347 BMLoopList *lst;
348#endif
349
350 int i, count = 0;
351
352 for (i = 0; i < len; i++) {
354 }
355
356#ifdef USE_BMESH_HOLES
357 for (lst = f->loops.first; lst; lst = lst->next)
358#endif
359 {
360
361#ifdef USE_BMESH_HOLES
362 l_iter = l_first = lst->first;
363#else
364 l_iter = l_first = f->l_first;
365#endif
366
367 do {
368 if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
369 count++;
370 }
371
372 } while ((l_iter = l_iter->next) != l_first);
373 }
374
375 for (i = 0; i < len; i++) {
377 }
378
379 return count;
380}
381
382bool BM_verts_in_face(BMVert **varr, int len, BMFace *f)
383{
384 BMLoop *l_iter, *l_first;
385
386#ifdef USE_BMESH_HOLES
387 BMLoopList *lst;
388#endif
389
390 int i;
391 bool ok = true;
392
393 /* simple check, we know can't succeed */
394 if (f->len < len) {
395 return false;
396 }
397
398 for (i = 0; i < len; i++) {
400 }
401
402#ifdef USE_BMESH_HOLES
403 for (lst = f->loops.first; lst; lst = lst->next)
404#endif
405 {
406
407#ifdef USE_BMESH_HOLES
408 l_iter = l_first = lst->first;
409#else
410 l_iter = l_first = f->l_first;
411#endif
412
413 do {
414 if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
415 /* pass */
416 }
417 else {
418 ok = false;
419 break;
420 }
421
422 } while ((l_iter = l_iter->next) != l_first);
423 }
424
425 for (i = 0; i < len; i++) {
427 }
428
429 return ok;
430}
431
432bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
433{
434 if (e->l) {
435 const BMLoop *l_iter, *l_first;
436
437 l_iter = l_first = e->l;
438 do {
439 if (l_iter->f == f) {
440 return true;
441 }
442 } while ((l_iter = l_iter->radial_next) != l_first);
443 }
444
445 return false;
446}
447
449{
450 BMLoop *l_other;
451
452 // BLI_assert(BM_edge_is_manifold(e)); /* Too strict, just check there is another radial face. */
453 BLI_assert(e->l && e->l->radial_next != e->l);
455
456 l_other = (l->e == e) ? l : l->prev;
457 l_other = l_other->radial_next;
458 BLI_assert(l_other->e == e);
459
460 if (l_other->v == l->v) {
461 /* pass */
462 }
463 else if (l_other->next->v == l->v) {
464 l_other = l_other->next;
465 }
466 else {
467 BLI_assert(0);
468 }
469
470 return l_other;
471}
472
474{
475 BMEdge *e_prev = *e_step;
476 BMEdge *e_next;
477 if (l->e == e_prev) {
478 e_next = l->prev->e;
479 }
480 else if (l->prev->e == e_prev) {
481 e_next = l->e;
482 }
483 else {
484 BLI_assert(0);
485 return nullptr;
486 }
487
488 if (BM_edge_is_manifold(e_next)) {
489 return BM_edge_other_loop((*e_step = e_next), l);
490 }
491 return nullptr;
492}
493
495{
496 BMLoop *l_a;
497 int tot = 0;
498 int i;
499
500 BLI_assert(BM_vert_in_edge(e_first, v));
501
502 l_a = e_first->l;
503 do {
504 l_a = BM_loop_other_vert_loop(l_a, v);
505 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
506 if (BM_edge_is_manifold(l_a->e)) {
507 l_a = l_a->radial_next;
508 }
509 else {
510 return nullptr;
511 }
512
513 tot++;
514 } while (l_a != e_first->l);
515
516 /* we know the total, now loop half way */
517 tot /= 2;
518 i = 0;
519
520 l_a = e_first->l;
521 do {
522 if (i == tot) {
523 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
524 return l_a->e;
525 }
526
527 l_a = BM_loop_other_vert_loop(l_a, v);
528 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
529 if (BM_edge_is_manifold(l_a->e)) {
530 l_a = l_a->radial_next;
531 }
532 /* this won't have changed from the previous loop */
533
534 i++;
535 } while (l_a != e_first->l);
536
537 return nullptr;
538}
539
541{
542 return len_v3v3(e->v1->co, e->v2->co);
543}
544
546{
547 return len_squared_v3v3(e->v1->co, e->v2->co);
548}
549
550bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
551{
552 BMLoop *la, *lb;
553
554 if ((la = e->l) && (lb = la->radial_next) && (la != lb) && (lb->radial_next == la)) {
555 *r_fa = la->f;
556 *r_fb = lb->f;
557 return true;
558 }
559
560 *r_fa = nullptr;
561 *r_fb = nullptr;
562 return false;
563}
564
565bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
566{
567 BMLoop *la, *lb;
568
569 if ((la = e->l) && (lb = la->radial_next) && (la != lb) && (lb->radial_next == la)) {
570 *r_la = la;
571 *r_lb = lb;
572 return true;
573 }
574
575 *r_la = nullptr;
576 *r_lb = nullptr;
577 return false;
578}
579
581{
582 const BMEdge *e = v->e;
583 if (e) {
584 BMEdge *e_other = BM_DISK_EDGE_NEXT(e, v);
585 return ((e_other != e) && (BM_DISK_EDGE_NEXT(e_other, v) == e));
586 }
587 return false;
588}
589
591{
592 const BMEdge *e = v->e;
593 if (e) {
594 BMEdge *e_other = BM_DISK_EDGE_NEXT(e, v);
595 if ((e_other != e) && (BM_DISK_EDGE_NEXT(e_other, v) == e)) {
596 return BM_edge_is_manifold(e) && BM_edge_is_manifold(e_other);
597 }
598 }
599 return false;
600}
601
602bool BM_vert_edge_pair(const BMVert *v, BMEdge **r_e_a, BMEdge **r_e_b)
603{
604 BMEdge *e_a = v->e;
605 if (e_a) {
606 BMEdge *e_b = BM_DISK_EDGE_NEXT(e_a, v);
607 if ((e_b != e_a) && (BM_DISK_EDGE_NEXT(e_b, v) == e_a)) {
608 *r_e_a = e_a;
609 *r_e_b = e_b;
610 return true;
611 }
612 }
613
614 *r_e_a = nullptr;
615 *r_e_b = nullptr;
616 return false;
617}
618
620{
621 return bmesh_disk_count(v);
622}
623
624int BM_vert_edge_count_at_most(const BMVert *v, const int count_max)
625{
626 return bmesh_disk_count_at_most(v, count_max);
627}
628
630{
631 int count = 0;
632 BMIter eiter;
633 BMEdge *edge;
634 BM_ITER_ELEM (edge, &eiter, (BMVert *)v, BM_EDGES_OF_VERT) {
635 if (edge->l) {
636 count++;
637 }
638 }
639 return count;
640}
642{
643 int count = 0;
644
645 if (e->l) {
646 BMLoop *l_iter, *l_first;
647
648 l_iter = l_first = e->l;
649 do {
650 count++;
651 } while ((l_iter = l_iter->radial_next) != l_first);
652 }
653
654 return count;
655}
656
657int BM_edge_face_count_at_most(const BMEdge *e, const int count_max)
658{
659 int count = 0;
660
661 if (e->l) {
662 BMLoop *l_iter, *l_first;
663
664 l_iter = l_first = e->l;
665 do {
666 count++;
667 if (count == count_max) {
668 break;
669 }
670 } while ((l_iter = l_iter->radial_next) != l_first);
671 }
672
673 return count;
674}
675
677{
679}
680
681int BM_vert_face_count_at_most(const BMVert *v, int count_max)
682{
683 return bmesh_disk_facevert_count_at_most(v, count_max);
684}
685
687{
688 if (v->e != nullptr) {
689 const BMEdge *e_iter, *e_first;
690 e_first = e_iter = v->e;
691 do {
692 if (e_iter->l != nullptr) {
693 return true;
694 }
695 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
696 }
697 return false;
698}
699
701{
702 if (v->e) {
703 BMEdge *e_first, *e_iter;
704
705 e_first = e_iter = v->e;
706 do {
707 if (e_iter->l) {
708 return false;
709 }
710 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
711
712 return true;
713 }
714 return false;
715}
716
718{
719 BMEdge *e_iter, *e_first, *e_prev;
720 BMLoop *l_iter, *l_first;
721 int loop_num = 0, loop_num_region = 0, boundary_num = 0;
722
723 if (v->e == nullptr) {
724 /* loose vert */
725 return false;
726 }
727
728 /* count edges while looking for non-manifold edges */
729 e_first = e_iter = v->e;
730 /* may be null */
731 l_first = e_iter->l;
732 do {
733 /* loose edge or edge shared by more than two faces,
734 * edges with 1 face user are OK, otherwise we could
735 * use BM_edge_is_manifold() here */
736 if (e_iter->l == nullptr || (e_iter->l != e_iter->l->radial_next->radial_next)) {
737 return false;
738 }
739
740 /* count radial loops */
741 if (e_iter->l->v == v) {
742 loop_num += 1;
743 }
744
745 if (!BM_edge_is_boundary(e_iter)) {
746 /* non boundary check opposite loop */
747 if (e_iter->l->radial_next->v == v) {
748 loop_num += 1;
749 }
750 }
751 else {
752 /* start at the boundary */
753 l_first = e_iter->l;
754 boundary_num += 1;
755 /* >2 boundaries can't be manifold */
756 if (boundary_num == 3) {
757 return false;
758 }
759 }
760 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
761
762 e_first = l_first->e;
763 l_first = (l_first->v == v) ? l_first : l_first->next;
764 BLI_assert(l_first->v == v);
765
766 l_iter = l_first;
767 e_prev = e_first;
768
769 do {
770 loop_num_region += 1;
771 } while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first) && (l_iter != nullptr));
772
773 return (loop_num == loop_num_region);
774}
775
776#define LOOP_VISIT _FLAG_WALK
777#define EDGE_VISIT _FLAG_WALK
778
780{
781 BMLoop *l_iter, *l_first;
782 int count = 0;
783
786
787 l_iter = l_first = e->l;
788 do {
789 if (l_iter->v == v) {
790 BMEdge *e_other = l_iter->prev->e;
791 if (!BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) {
793 count += 1;
794 }
795 if (!BM_ELEM_API_FLAG_TEST(e_other, EDGE_VISIT)) {
796 count += bm_loop_region_count__recursive(e_other, v);
797 }
798 }
799 else if (l_iter->next->v == v) {
800 BMEdge *e_other = l_iter->next->e;
801 if (!BM_ELEM_API_FLAG_TEST(l_iter->next, LOOP_VISIT)) {
803 count += 1;
804 }
805 if (!BM_ELEM_API_FLAG_TEST(e_other, EDGE_VISIT)) {
806 count += bm_loop_region_count__recursive(e_other, v);
807 }
808 }
809 else {
810 BLI_assert(0);
811 }
812 } while ((l_iter = l_iter->radial_next) != l_first);
813
814 return count;
815}
816
818{
819 int count = 0;
820 BMEdge *e_iter, *e_first;
821
822 /* clear flags */
823 e_iter = e_first = l->e;
824 do {
826 if (e_iter->l) {
827 BMLoop *l_iter, *l_first;
828 l_iter = l_first = e_iter->l;
829 do {
830 if (l_iter->v == l->v) {
832 count += 1;
833 }
834 } while ((l_iter = l_iter->radial_next) != l_first);
835 }
836 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, l->v)) != e_first);
837
838 return count;
839}
840
842{
843 const int count = bm_loop_region_count__recursive(l->e, l->v);
844 const int count_total = bm_loop_region_count__clear(l);
845 if (r_loop_total) {
846 *r_loop_total = count_total;
847 }
848 return count;
849}
850
851#undef LOOP_VISIT
852#undef EDGE_VISIT
853
858
860{
861 BMLoop *l_first = BM_vert_find_first_loop(const_cast<BMVert *>(v));
862 if (l_first) {
863 int count, count_total;
864 count = BM_loop_region_loops_count_at_most(l_first, &count_total);
865 return (count == count_total);
866 }
867 return true;
868}
869
871{
872 if (BM_edge_is_manifold(e)) {
873 BMLoop *l1 = e->l;
874 BMLoop *l2 = e->l->radial_next;
875 if (!equals_v3v3(l1->f->no, l2->f->no)) {
876 float cross[3];
877 float l_dir[3];
878 cross_v3_v3v3(cross, l1->f->no, l2->f->no);
879 /* we assume contiguous normals, otherwise the result isn't meaningful */
880 sub_v3_v3v3(l_dir, l1->next->v->co, l1->v->co);
881 return (dot_v3v3(l_dir, cross) > 0.0f);
882 }
883 }
884 return true;
885}
886
888 const int cd_loop_type,
889 const int cd_loop_offset)
890{
891 BLI_assert(cd_loop_offset != -1);
892
893 if (e->l && e->l->radial_next != e->l) {
894 const BMLoop *l_base_v1 = e->l;
895 const BMLoop *l_base_v2 = e->l->next;
896 const void *l_base_cd_v1 = BM_ELEM_CD_GET_VOID_P(l_base_v1, cd_loop_offset);
897 const void *l_base_cd_v2 = BM_ELEM_CD_GET_VOID_P(l_base_v2, cd_loop_offset);
898 const BMLoop *l_iter = e->l->radial_next;
899 do {
900 const BMLoop *l_iter_v1;
901 const BMLoop *l_iter_v2;
902 const void *l_iter_cd_v1;
903 const void *l_iter_cd_v2;
904
905 if (l_iter->v == l_base_v1->v) {
906 l_iter_v1 = l_iter;
907 l_iter_v2 = l_iter->next;
908 }
909 else {
910 l_iter_v1 = l_iter->next;
911 l_iter_v2 = l_iter;
912 }
913 BLI_assert((l_iter_v1->v == l_base_v1->v) && (l_iter_v2->v == l_base_v2->v));
914
915 l_iter_cd_v1 = BM_ELEM_CD_GET_VOID_P(l_iter_v1, cd_loop_offset);
916 l_iter_cd_v2 = BM_ELEM_CD_GET_VOID_P(l_iter_v2, cd_loop_offset);
917
918 if ((CustomData_data_equals(eCustomDataType(cd_loop_type), l_base_cd_v1, l_iter_cd_v1) ==
919 0) ||
920 (CustomData_data_equals(eCustomDataType(cd_loop_type), l_base_cd_v2, l_iter_cd_v2) == 0))
921 {
922 return false;
923 }
924
925 } while ((l_iter = l_iter->radial_next) != e->l);
926 }
927 return true;
928}
929
931{
932 if (v->e) {
933 BMEdge *e_first, *e_iter;
934
935 e_first = e_iter = v->e;
936 do {
937 if (BM_edge_is_boundary(e_iter)) {
938 return true;
939 }
940 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
941
942 return false;
943 }
944 return false;
945}
946
948{
949 BMIter iter1, iter2;
950 BMEdge *e;
951 BMFace *f;
952 int count = 0;
953
954 BM_ITER_ELEM (e, &iter1, f_a, BM_EDGES_OF_FACE) {
955 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
956 if (f != f_a && f != f_b && BM_face_share_edge_check(f, f_b)) {
957 count++;
958 }
959 }
960 }
961
962 return count;
963}
964
966{
967 BMIter iter1, iter2;
968 BMEdge *e;
969 BMFace *f;
970
971 BM_ITER_ELEM (e, &iter1, f_a, BM_EDGES_OF_FACE) {
972 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
973 if (f != f_a && f != f_b && BM_face_share_edge_check(f, f_b)) {
974 return true;
975 }
976 }
977 }
978
979 return false;
980}
981
983{
984 BMLoop *l_iter;
985 BMLoop *l_first;
986 int count = 0;
987
988 l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
989 do {
990 if (BM_edge_in_face(l_iter->e, f_b)) {
991 count++;
992 }
993 } while ((l_iter = l_iter->next) != l_first);
994
995 return count;
996}
997
999{
1000 BMLoop *l_iter;
1001 BMLoop *l_first;
1002
1003 l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
1004 do {
1005 if (BM_edge_in_face(l_iter->e, f_b)) {
1006 return true;
1007 }
1008 } while ((l_iter = l_iter->next) != l_first);
1009
1010 return false;
1011}
1012
1014{
1015 BMLoop *l_iter;
1016 BMLoop *l_first;
1017 int count = 0;
1018
1019 l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
1020 do {
1021 if (BM_vert_in_face(l_iter->v, f_b)) {
1022 count++;
1023 }
1024 } while ((l_iter = l_iter->next) != l_first);
1025
1026 return count;
1027}
1028
1030{
1031 BMLoop *l_iter;
1032 BMLoop *l_first;
1033
1034 l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
1035 do {
1036 if (BM_vert_in_face(l_iter->v, f_b)) {
1037 return true;
1038 }
1039 } while ((l_iter = l_iter->next) != l_first);
1040
1041 return false;
1042}
1043
1045{
1046 BLI_assert(l_a->v == l_b->v);
1047 return (ELEM(l_a->e, l_b->e, l_b->prev->e) || ELEM(l_b->e, l_a->e, l_a->prev->e));
1048}
1049
1051{
1052 BMLoop *l;
1053 BMFace *f;
1054
1055 if (e1->l && e2->l) {
1056 l = e1->l;
1057 do {
1058 f = l->f;
1059 if (BM_edge_in_face(e2, f)) {
1060 return true;
1061 }
1062 l = l->radial_next;
1063 } while (l != e1->l);
1064 }
1065 return false;
1066}
1067
1069{
1070 BMLoop *l;
1071 BMFace *f;
1072
1073 if (e1->l && e2->l) {
1074 l = e1->l;
1075 do {
1076 f = l->f;
1077 if (f->len == 4) {
1078 if (BM_edge_in_face(e2, f)) {
1079 return true;
1080 }
1081 }
1082 l = l->radial_next;
1083 } while (l != e1->l);
1084 }
1085 return false;
1086}
1087
1089{
1090 return (e1->v1 == e2->v1 || e1->v1 == e2->v2 || e1->v2 == e2->v1 || e1->v2 == e2->v2);
1091}
1092
1094{
1095 BLI_assert(e1 != e2);
1096 if (BM_vert_in_edge(e2, e1->v1)) {
1097 return e1->v1;
1098 }
1099 if (BM_vert_in_edge(e2, e1->v2)) {
1100 return e1->v2;
1101 }
1102 return nullptr;
1103}
1104
1106{
1108 if (l->v == v) {
1109 return l;
1110 }
1111 return l->next;
1112}
1113
1115{
1116 BMLoop *l_first;
1117 BMLoop *l_iter;
1118
1119 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1120 do {
1121 if (l_iter->v == v) {
1122 return l_iter;
1123 }
1124 } while ((l_iter = l_iter->next) != l_first);
1125
1126 return nullptr;
1127}
1128
1130{
1131 BMLoop *l_first;
1132 BMLoop *l_iter;
1133
1134 l_iter = l_first = e->l;
1135 do {
1136 if (l_iter->f == f) {
1137 return l_iter;
1138 }
1139 } while ((l_iter = l_iter->radial_next) != l_first);
1140
1141 return nullptr;
1142}
1143
1145 BMVert **r_v1,
1146 BMVert **r_v2,
1147 const BMLoop *edge_loop)
1148{
1149 BLI_assert(edge_loop->e == edge);
1150 (void)edge; /* quiet warning in release build */
1151 *r_v1 = edge_loop->v;
1152 *r_v2 = edge_loop->next->v;
1153}
1154
1155void BM_edge_ordered_verts(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
1156{
1157 BM_edge_ordered_verts_ex(edge, r_v1, r_v2, edge->l);
1158}
1159
1160BMLoop *BM_loop_find_prev_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq)
1161{
1162 BMLoop *l_step = l->prev;
1163
1164 BLI_assert(!ELEM(l_stop, nullptr, l));
1165
1166 while (len_squared_v3v3(l->v->co, l_step->v->co) < eps_sq) [[unlikely]] {
1167 l_step = l_step->prev;
1168 BLI_assert(l_step != l);
1169 if (l_step == l_stop) [[unlikely]] {
1170 return nullptr;
1171 }
1172 }
1173
1174 return l_step;
1175}
1176
1177BMLoop *BM_loop_find_next_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq)
1178{
1179 BMLoop *l_step = l->next;
1180
1181 BLI_assert(!ELEM(l_stop, nullptr, l));
1182
1183 while (len_squared_v3v3(l->v->co, l_step->v->co) < eps_sq) [[unlikely]] {
1184 l_step = l_step->next;
1185 BLI_assert(l_step != l);
1186 if (l_step == l_stop) [[unlikely]] {
1187 return nullptr;
1188 }
1189 }
1190
1191 return l_step;
1192}
1193
1195{
1196 float e_dir_prev[3];
1197 float e_dir_next[3];
1198 float l_no[3];
1199
1200 sub_v3_v3v3(e_dir_prev, l->prev->v->co, l->v->co);
1201 sub_v3_v3v3(e_dir_next, l->next->v->co, l->v->co);
1202 cross_v3_v3v3(l_no, e_dir_next, e_dir_prev);
1203 return dot_v3v3(l_no, l->f->no) > 0.0f;
1204}
1205
1207{
1208 return angle_v3v3v3(l->prev->v->co, l->v->co, l->next->v->co);
1209}
1210
1211float BM_loop_calc_face_normal_safe_ex(const BMLoop *l, const float epsilon_sq, float r_normal[3])
1212{
1213 /* NOTE: we cannot use result of normal_tri_v3 here to detect colinear vectors
1214 * (vertex on a straight line) from zero value,
1215 * because it does not normalize both vectors before making cross-product.
1216 * Instead of adding two costly normalize computations,
1217 * just check ourselves for colinear case. */
1218 /* NOTE: FEPSILON might need some finer tweaking at some point?
1219 * Seems to be working OK for now though. */
1220 float v1[3], v2[3], v_tmp[3];
1221 sub_v3_v3v3(v1, l->prev->v->co, l->v->co);
1222 sub_v3_v3v3(v2, l->next->v->co, l->v->co);
1223
1224 const float fac = ((v2[0] == 0.0f) ?
1225 ((v2[1] == 0.0f) ? ((v2[2] == 0.0f) ? 0.0f : v1[2] / v2[2]) :
1226 v1[1] / v2[1]) :
1227 v1[0] / v2[0]);
1228
1229 mul_v3_v3fl(v_tmp, v2, fac);
1230 sub_v3_v3(v_tmp, v1);
1231 if (fac != 0.0f && !is_zero_v3(v1) && len_squared_v3(v_tmp) > epsilon_sq) {
1232 /* Not co-linear, we can compute cross-product and normalize it into normal. */
1233 cross_v3_v3v3(r_normal, v1, v2);
1234 return normalize_v3(r_normal);
1235 }
1236 copy_v3_v3(r_normal, l->f->no);
1237 return 0.0f;
1238}
1239
1241 const float normal_fallback[3],
1242 float const (*vertexCos)[3],
1243 const float epsilon_sq,
1244 float r_normal[3])
1245{
1246 const int i_prev = BM_elem_index_get(l->prev->v);
1247 const int i_next = BM_elem_index_get(l->next->v);
1248 const int i = BM_elem_index_get(l->v);
1249
1250 float v1[3], v2[3], v_tmp[3];
1251 sub_v3_v3v3(v1, vertexCos[i_prev], vertexCos[i]);
1252 sub_v3_v3v3(v2, vertexCos[i_next], vertexCos[i]);
1253
1254 const float fac = ((v2[0] == 0.0f) ?
1255 ((v2[1] == 0.0f) ? ((v2[2] == 0.0f) ? 0.0f : v1[2] / v2[2]) :
1256 v1[1] / v2[1]) :
1257 v1[0] / v2[0]);
1258
1259 mul_v3_v3fl(v_tmp, v2, fac);
1260 sub_v3_v3(v_tmp, v1);
1261 if (fac != 0.0f && !is_zero_v3(v1) && len_squared_v3(v_tmp) > epsilon_sq) {
1262 /* Not co-linear, we can compute cross-product and normalize it into normal. */
1263 cross_v3_v3v3(r_normal, v1, v2);
1264 return normalize_v3(r_normal);
1265 }
1266 copy_v3_v3(r_normal, normal_fallback);
1267 return 0.0f;
1268}
1269
1270float BM_loop_calc_face_normal_safe(const BMLoop *l, float r_normal[3])
1271{
1272 return BM_loop_calc_face_normal_safe_ex(l, 1e-5f, r_normal);
1273}
1274
1276 const float normal_fallback[3],
1277 float const (*vertexCos)[3],
1278 float r_normal[3])
1279
1280{
1281 return BM_loop_calc_face_normal_safe_vcos_ex(l, normal_fallback, vertexCos, 1e-5f, r_normal);
1282}
1283
1284float BM_loop_calc_face_normal(const BMLoop *l, float r_normal[3])
1285{
1286 float v1[3], v2[3];
1287 sub_v3_v3v3(v1, l->prev->v->co, l->v->co);
1288 sub_v3_v3v3(v2, l->next->v->co, l->v->co);
1289
1290 cross_v3_v3v3(r_normal, v1, v2);
1291 const float len = normalize_v3(r_normal);
1292 if (len == 0.0f) [[unlikely]] {
1293 copy_v3_v3(r_normal, l->f->no);
1294 }
1295 return len;
1296}
1297
1298void BM_loop_calc_face_direction(const BMLoop *l, float r_dir[3])
1299{
1300 float v_prev[3];
1301 float v_next[3];
1302
1303 sub_v3_v3v3(v_prev, l->v->co, l->prev->v->co);
1304 sub_v3_v3v3(v_next, l->next->v->co, l->v->co);
1305
1306 normalize_v3(v_prev);
1307 normalize_v3(v_next);
1308
1309 add_v3_v3v3(r_dir, v_prev, v_next);
1310 normalize_v3(r_dir);
1311}
1312
1313void BM_loop_calc_face_tangent(const BMLoop *l, float r_tangent[3])
1314{
1315 float v_prev[3];
1316 float v_next[3];
1317 float dir[3];
1318
1319 sub_v3_v3v3(v_prev, l->prev->v->co, l->v->co);
1320 sub_v3_v3v3(v_next, l->v->co, l->next->v->co);
1321
1322 normalize_v3(v_prev);
1323 normalize_v3(v_next);
1324 add_v3_v3v3(dir, v_prev, v_next);
1325
1326 if (compare_v3v3(v_prev, v_next, FLT_EPSILON * 10.0f) == false) {
1327 float nor[3]; /* for this purpose doesn't need to be normalized */
1328 cross_v3_v3v3(nor, v_prev, v_next);
1329 /* concave face check */
1330 if (dot_v3v3(nor, l->f->no) < 0.0f) [[unlikely]] {
1331 negate_v3(nor);
1332 }
1333 cross_v3_v3v3(r_tangent, dir, nor);
1334 }
1335 else {
1336 /* prev/next are the same - compare with face normal since we don't have one */
1337 cross_v3_v3v3(r_tangent, dir, l->f->no);
1338 }
1339
1340 normalize_v3(r_tangent);
1341}
1342
1343float BM_edge_calc_face_angle_ex(const BMEdge *e, const float fallback)
1344{
1345 if (BM_edge_is_manifold(e)) {
1346 const BMLoop *l1 = e->l;
1347 const BMLoop *l2 = e->l->radial_next;
1348 return angle_normalized_v3v3(l1->f->no, l2->f->no);
1349 }
1350 return fallback;
1351}
1353{
1354 return BM_edge_calc_face_angle_ex(e, DEG2RADF(90.0f));
1355}
1356
1358 const float imat3[3][3],
1359 const float fallback)
1360{
1361 if (BM_edge_is_manifold(e)) {
1362 const BMLoop *l1 = e->l;
1363 const BMLoop *l2 = e->l->radial_next;
1364 float no1[3], no2[3];
1365 copy_v3_v3(no1, l1->f->no);
1366 copy_v3_v3(no2, l2->f->no);
1367
1368 mul_transposed_m3_v3(imat3, no1);
1369 mul_transposed_m3_v3(imat3, no2);
1370
1371 normalize_v3(no1);
1372 normalize_v3(no2);
1373
1374 return angle_normalized_v3v3(no1, no2);
1375 }
1376 return fallback;
1377}
1378float BM_edge_calc_face_angle_with_imat3(const BMEdge *e, const float imat3[3][3])
1379{
1380 return BM_edge_calc_face_angle_with_imat3_ex(e, imat3, DEG2RADF(90.0f));
1381}
1382
1383float BM_edge_calc_face_angle_signed_ex(const BMEdge *e, const float fallback)
1384{
1385 if (BM_edge_is_manifold(e)) {
1386 BMLoop *l1 = e->l;
1387 BMLoop *l2 = e->l->radial_next;
1388 const float angle = angle_normalized_v3v3(l1->f->no, l2->f->no);
1389 return BM_edge_is_convex(e) ? angle : -angle;
1390 }
1391 return fallback;
1392}
1397
1398void BM_edge_calc_face_tangent(const BMEdge *e, const BMLoop *e_loop, float r_tangent[3])
1399{
1400 float tvec[3];
1401 BMVert *v1, *v2;
1402 BM_edge_ordered_verts_ex(e, &v1, &v2, e_loop);
1403
1404 sub_v3_v3v3(tvec, v1->co, v2->co); /* use for temp storage */
1405 /* NOTE: we could average the tangents of both loops,
1406 * for non flat ngons it will give a better direction */
1407 cross_v3_v3v3(r_tangent, tvec, e_loop->f->no);
1408 normalize_v3(r_tangent);
1409}
1410
1411float BM_vert_calc_edge_angle_ex(const BMVert *v, const float fallback)
1412{
1413 BMEdge *e1, *e2;
1414
1415 /* Saves `BM_vert_edge_count(v)` and edge iterator,
1416 * get the edges and count them both at once. */
1417
1418 if ((e1 = v->e) && (e2 = bmesh_disk_edge_next(e1, v)) && (e1 != e2) &&
1419 /* make sure we come full circle and only have 2 connected edges */
1420 (e1 == bmesh_disk_edge_next(e2, v)))
1421 {
1422 BMVert *v1 = BM_edge_other_vert(e1, v);
1423 BMVert *v2 = BM_edge_other_vert(e2, v);
1424
1425 return float(M_PI) - angle_v3v3v3(v1->co, v->co, v2->co);
1426 }
1427 return fallback;
1428}
1429
1431{
1432 return BM_vert_calc_edge_angle_ex(v, DEG2RADF(90.0f));
1433}
1434
1436{
1437 BMIter iter;
1438 BMLoop *l;
1439 float accum_shell = 0.0f;
1440 float accum_angle = 0.0f;
1441
1442 BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) {
1443 const float face_angle = BM_loop_calc_face_angle(l);
1444 accum_shell += shell_v3v3_normalized_to_dist(v->no, l->f->no) * face_angle;
1445 accum_angle += face_angle;
1446 }
1447
1448 if (accum_angle != 0.0f) {
1449 return accum_shell / accum_angle;
1450 }
1451 return 1.0f;
1452}
1453float BM_vert_calc_shell_factor_ex(const BMVert *v, const float no[3], const char hflag)
1454{
1455 BMIter iter;
1456 const BMLoop *l;
1457 float accum_shell = 0.0f;
1458 float accum_angle = 0.0f;
1459 int tot_sel = 0, tot = 0;
1460
1461 BM_ITER_ELEM (l, &iter, (BMVert *)v, BM_LOOPS_OF_VERT) {
1462 if (BM_elem_flag_test(l->f, hflag)) { /* <-- main difference to BM_vert_calc_shell_factor! */
1463 const float face_angle = BM_loop_calc_face_angle(l);
1464 accum_shell += shell_v3v3_normalized_to_dist(no, l->f->no) * face_angle;
1465 accum_angle += face_angle;
1466 tot_sel++;
1467 }
1468 tot++;
1469 }
1470
1471 if (accum_angle != 0.0f) {
1472 return accum_shell / accum_angle;
1473 }
1474 /* other main difference from BM_vert_calc_shell_factor! */
1475 if (tot != 0 && tot_sel == 0) {
1476 /* none selected, so use all */
1478 }
1479 return 1.0f;
1480}
1481
1483{
1484 BMIter iter;
1485 BMEdge *e;
1486 int tot;
1487 float length = 0.0f;
1488
1489 BM_ITER_ELEM_INDEX (e, &iter, (BMVert *)v, BM_EDGES_OF_VERT, tot) {
1490 const BMVert *v_other = BM_edge_other_vert(e, v);
1491 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1493 }
1494 }
1495
1496 if (tot) {
1497 return length / float(tot);
1498 }
1499 return 0.0f;
1500}
1501
1503{
1504 float shortest_len = FLT_MAX;
1505
1506 BMLoop *l_iter;
1507 BMLoop *l_first;
1508
1509 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1510 BMLoop *shortest_loop = l_first; /* Fallback for non-finite coordinates, see #108658. */
1511
1512 do {
1513 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1514 if (len_sq <= shortest_len) {
1515 shortest_loop = l_iter;
1516 shortest_len = len_sq;
1517 }
1518 } while ((l_iter = l_iter->next) != l_first);
1519
1520 return shortest_loop;
1521}
1522
1524{
1525 float len_max_sq = 0.0f;
1526
1527 BMLoop *l_iter;
1528 BMLoop *l_first;
1529
1530 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1531 BMLoop *longest_loop = l_first; /* Fallback for non-finite coordinates, see #108658. */
1532
1533 do {
1534 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1535 if (len_sq >= len_max_sq) {
1536 longest_loop = l_iter;
1537 len_max_sq = len_sq;
1538 }
1539 } while ((l_iter = l_iter->next) != l_first);
1540
1541 return longest_loop;
1542}
1543
1550#if 0
1551BMEdge *BM_edge_exists(BMVert *v_a, BMVert *v_b)
1552{
1553 BMIter iter;
1554 BMEdge *e;
1555
1556 BLI_assert(v_a != v_b);
1557 BLI_assert(v_a->head.htype == BM_VERT && v_b->head.htype == BM_VERT);
1558
1559 BM_ITER_ELEM (e, &iter, v_a, BM_EDGES_OF_VERT) {
1560 if (e->v1 == v_b || e->v2 == v_b) {
1561 return e;
1562 }
1563 }
1564
1565 return nullptr;
1566}
1567#else
1569{
1570 /* speedup by looping over both edges verts
1571 * where one vert may connect to many edges but not the other. */
1572
1573 BMEdge *e_a, *e_b;
1574
1575 BLI_assert(v_a != v_b);
1576 BLI_assert(v_a->head.htype == BM_VERT && v_b->head.htype == BM_VERT);
1577
1578 if ((e_a = v_a->e) && (e_b = v_b->e)) {
1579 BMEdge *e_a_iter = e_a, *e_b_iter = e_b;
1580
1581 do {
1582 if (BM_vert_in_edge(e_a_iter, v_b)) {
1583 return e_a_iter;
1584 }
1585 if (BM_vert_in_edge(e_b_iter, v_a)) {
1586 return e_b_iter;
1587 }
1588 } while (((e_a_iter = bmesh_disk_edge_next(e_a_iter, v_a)) != e_a) &&
1589 ((e_b_iter = bmesh_disk_edge_next(e_b_iter, v_b)) != e_b));
1590 }
1591
1592 return nullptr;
1593}
1594#endif
1595
1597{
1598 BMVert *v = e->v1;
1599 BMVert *v_other = e->v2;
1600
1601 BMEdge *e_iter;
1602
1603 e_iter = e;
1604 while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e) {
1605 if (BM_vert_in_edge(e_iter, v_other)) [[unlikely]] {
1606 return e_iter;
1607 }
1608 }
1609
1610 return nullptr;
1611}
1612
1614{
1615 if (e->l != nullptr) {
1616 BMLoop *l_iter, *l_first;
1617 l_iter = l_first = e->l;
1618 do {
1619 if (!BM_elem_flag_test(l_iter->f, BM_ELEM_HIDDEN)) {
1620 return l_iter;
1621 }
1622 } while ((l_iter = l_iter->radial_next) != l_first);
1623 }
1624 return nullptr;
1625}
1626
1627BMFace *BM_face_exists(BMVert *const *varr, int len)
1628{
1629 if (varr[0]->e) {
1630 BMEdge *e_iter, *e_first;
1631 e_iter = e_first = varr[0]->e;
1632
1633 /* would normally use BM_LOOPS_OF_VERT, but this runs so often,
1634 * its faster to iterate on the data directly */
1635 do {
1636 if (e_iter->l) {
1637 BMLoop *l_iter_radial, *l_first_radial;
1638 l_iter_radial = l_first_radial = e_iter->l;
1639
1640 do {
1641 if ((l_iter_radial->v == varr[0]) && (l_iter_radial->f->len == len)) {
1642 /* the fist 2 verts match, now check the remaining (len - 2) faces do too
1643 * winding isn't known, so check in both directions */
1644 int i_walk = 2;
1645
1646 if (l_iter_radial->next->v == varr[1]) {
1647 BMLoop *l_walk = l_iter_radial->next->next;
1648 do {
1649 if (l_walk->v != varr[i_walk]) {
1650 break;
1651 }
1652 } while ((void)(l_walk = l_walk->next), ++i_walk != len);
1653 }
1654 else if (l_iter_radial->prev->v == varr[1]) {
1655 BMLoop *l_walk = l_iter_radial->prev->prev;
1656 do {
1657 if (l_walk->v != varr[i_walk]) {
1658 break;
1659 }
1660 } while ((void)(l_walk = l_walk->prev), ++i_walk != len);
1661 }
1662
1663 if (i_walk == len) {
1664 return l_iter_radial->f;
1665 }
1666 }
1667 } while ((l_iter_radial = l_iter_radial->radial_next) != l_first_radial);
1668 }
1669 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, varr[0])) != e_first);
1670 }
1671
1672 return nullptr;
1673}
1674
1676{
1677 BLI_assert(l_a->f == l_b->f);
1678 BLI_assert(l_a != l_b);
1679#ifndef NDEBUG
1680 {
1681 BMLoop *l_test = l_a;
1682 for (int i = 1; i < f_len; i++) {
1683 l_test = l_test->next;
1684 }
1685 BLI_assert(l_test == l_b);
1686 }
1687#endif
1688
1689 BMEdge *e_exists = BM_edge_exists(l_a->v, l_b->v);
1690 if (e_exists == nullptr || e_exists->l == nullptr) {
1691 return nullptr;
1692 }
1693
1694 BMLoop *l_radial_iter = e_exists->l;
1695 do {
1696 if (l_radial_iter->f->len != f_len) {
1697 continue;
1698 }
1699
1700 const bool swap_winding = (l_radial_iter->v == l_a->v);
1701 BMLoop *l_other_beg, *l_other_end;
1702 if (swap_winding) {
1703 l_other_beg = l_radial_iter;
1704 l_other_end = l_radial_iter->next;
1705 }
1706 else {
1707 l_other_beg = l_radial_iter->next;
1708 l_other_end = l_radial_iter;
1709 }
1710 BLI_assert(l_a->v == l_other_beg->v);
1711 BLI_assert(l_b->v == l_other_end->v);
1712
1713 if (swap_winding) {
1715 l_a->next, l_b->prev, l_other_beg->prev, l_other_end->next))
1716 {
1717 return l_radial_iter->f;
1718 }
1719 }
1720 else {
1722 l_a->next, l_b->prev, l_other_beg->next, l_other_end->prev))
1723 {
1724 return l_radial_iter->f;
1725 }
1726 }
1727 } while ((l_radial_iter = l_radial_iter->radial_next) != e_exists->l);
1728
1729 return nullptr;
1730}
1731
1733{
1734 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
1735 for (BMLoop *l_iter = l_first->radial_next; l_first != l_iter; l_iter = l_iter->radial_next) {
1736 if (l_iter->f->len == l_first->f->len) {
1737 if (l_iter->v == l_first->v) {
1738 BMLoop *l_a = l_first, *l_b = l_iter, *l_b_init = l_iter;
1739 do {
1740 if (l_a->e != l_b->e) {
1741 break;
1742 }
1743 } while (((void)(l_a = l_a->next), (l_b = l_b->next)) != l_b_init);
1744 if (l_b == l_b_init) {
1745 return l_iter->f;
1746 }
1747 }
1748 else {
1749 BMLoop *l_a = l_first, *l_b = l_iter, *l_b_init = l_iter;
1750 do {
1751 if (l_a->e != l_b->e) {
1752 break;
1753 }
1754 } while (((void)(l_a = l_a->prev), (l_b = l_b->next)) != l_b_init);
1755 if (l_b == l_b_init) {
1756 return l_iter->f;
1757 }
1758 }
1759 }
1760 }
1761 return nullptr;
1762}
1763
1764bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
1765{
1766 BMFace *f;
1767 BMEdge *e;
1768 BMVert *v;
1769 bool ok;
1770 int tot_tag;
1771
1772 BMIter fiter;
1773 BMIter viter;
1774
1775 int i;
1776
1777 for (i = 0; i < len; i++) {
1778 /* save some time by looping over edge faces rather than vert faces
1779 * will still loop over some faces twice but not as many */
1780 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1782 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1784 }
1785 }
1786
1787 /* clear all edge tags */
1788 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1790 }
1791 }
1792
1793 /* now tag all verts and edges in the boundary array as true so
1794 * we can know if a face-vert is from our array */
1795 for (i = 0; i < len; i++) {
1798 }
1799
1800 /* so! boundary is tagged, everything else cleared */
1801
1802 /* 1) tag all faces connected to edges - if all their verts are boundary */
1803 tot_tag = 0;
1804 for (i = 0; i < len; i++) {
1805 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1807 ok = true;
1808 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1810 ok = false;
1811 break;
1812 }
1813 }
1814
1815 if (ok) {
1816 /* we only use boundary verts */
1818 tot_tag++;
1819 }
1820 }
1821 else {
1822 /* we already found! */
1823 }
1824 }
1825 }
1826
1827 if (tot_tag == 0) {
1828 /* no faces use only boundary verts, quit early */
1829 ok = false;
1830 goto finally;
1831 }
1832
1833 /* 2) loop over non-boundary edges that use boundary verts,
1834 * check each have 2 tagged faces connected (faces that only use 'varr' verts) */
1835 ok = true;
1836 for (i = 0; i < len; i++) {
1837 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1838
1839 if (/* non-boundary edge */
1841 /* ...using boundary verts */
1844 {
1845 int tot_face_tag = 0;
1846 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
1848 tot_face_tag++;
1849 }
1850 }
1851
1852 if (tot_face_tag != 2) {
1853 ok = false;
1854 break;
1855 }
1856 }
1857 }
1858
1859 if (ok == false) {
1860 break;
1861 }
1862 }
1863
1864finally:
1865 /* Cleanup */
1866 for (i = 0; i < len; i++) {
1869 }
1870 return ok;
1871}
1872
1874{
1875 /* Build a unique vertex array from `earr`, to pass to #BM_face_exists_multi. */
1877
1878 for (int i = 0; i < len; i++) {
1881 }
1882
1883 int varr_len = 0;
1884 for (int i = 0; i < len; i++) {
1885 BMEdge *e = earr[i];
1886 for (int j = 0; j < 2; j++) {
1887 BMVert *v = *((&e->v1) + j);
1890 /* Invalid input, likely a bug in the caller (assert below).
1891 * Keep going so all flags are cleared. */
1892 if (varr_len < len) {
1893 varr[varr_len] = v;
1894 }
1895 varr_len++;
1896 }
1897 }
1898 }
1899
1900 /* A closed loop has exactly one vert per edge, anything else is invalid input. */
1901 if (varr_len != len) {
1902 BMESH_ASSERT(0);
1903 return false;
1904 }
1905
1906 return BM_face_exists_multi(varr.data(), earr, len);
1907}
1908
1910{
1911 BMIter viter;
1912 BMFace *f;
1913 int i;
1914 BMFace *f_overlap = nullptr;
1915 LinkNode *f_lnk = nullptr;
1916
1917#ifndef NDEBUG
1918 /* check flag isn't already set */
1919 for (i = 0; i < len; i++) {
1920 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1922 }
1923 }
1924#endif
1925
1926 for (i = 0; i < len; i++) {
1927 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1928 if (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0) {
1929 if (len <= BM_verts_in_face_count(varr, len, f)) {
1930 f_overlap = f;
1931 break;
1932 }
1933
1935 BLI_linklist_prepend_alloca(&f_lnk, f);
1936 }
1937 }
1938 }
1939
1940 for (; f_lnk; f_lnk = f_lnk->next) {
1942 }
1943
1944 return f_overlap;
1945}
1946
1948{
1949 BMIter viter;
1950 BMFace *f;
1951 bool is_init = false;
1952 bool is_overlap = false;
1953 LinkNode *f_lnk = nullptr;
1954
1955#ifndef NDEBUG
1956 /* check flag isn't already set */
1957 for (int i = 0; i < len; i++) {
1959 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1961 }
1962 }
1963#endif
1964
1965 for (int i = 0; i < len; i++) {
1966 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1967 if ((f->len <= len) && (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0)) {
1968 /* Check if all verts in this face are flagged. */
1969 BMLoop *l_iter, *l_first;
1970
1971 if (is_init == false) {
1972 is_init = true;
1973 for (int j = 0; j < len; j++) {
1975 }
1976 }
1977
1978 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1979 is_overlap = true;
1980 do {
1981 if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP) == 0) {
1982 is_overlap = false;
1983 break;
1984 }
1985 } while ((l_iter = l_iter->next) != l_first);
1986
1987 if (is_overlap) {
1988 break;
1989 }
1990
1992 BLI_linklist_prepend_alloca(&f_lnk, f);
1993 }
1994 }
1995 }
1996
1997 if (is_init == true) {
1998 for (int i = 0; i < len; i++) {
2000 }
2001 }
2002
2003 for (; f_lnk; f_lnk = f_lnk->next) {
2005 }
2006
2007 return is_overlap;
2008}
2009
2010bool BM_vert_is_all_edge_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
2011{
2012 if (v->e) {
2013 BMEdge *e_other;
2014 BMIter eiter;
2015
2016 BM_ITER_ELEM (e_other, &eiter, (BMVert *)v, BM_EDGES_OF_VERT) {
2017 if (!respect_hide || !BM_elem_flag_test(e_other, BM_ELEM_HIDDEN)) {
2018 if (!BM_elem_flag_test(e_other, hflag)) {
2019 return false;
2020 }
2021 }
2022 }
2023 }
2024
2025 return true;
2026}
2027
2028bool BM_vert_is_all_face_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
2029{
2030 if (v->e) {
2031 BMEdge *f_other;
2032 BMIter fiter;
2033
2034 BM_ITER_ELEM (f_other, &fiter, (BMVert *)v, BM_FACES_OF_VERT) {
2035 if (!respect_hide || !BM_elem_flag_test(f_other, BM_ELEM_HIDDEN)) {
2036 if (!BM_elem_flag_test(f_other, hflag)) {
2037 return false;
2038 }
2039 }
2040 }
2041 }
2042
2043 return true;
2044}
2045
2046bool BM_edge_is_all_face_flag_test(const BMEdge *e, const char hflag, const bool respect_hide)
2047{
2048 if (e->l) {
2049 BMLoop *l_iter, *l_first;
2050
2051 l_iter = l_first = e->l;
2052 do {
2053 if (!respect_hide || !BM_elem_flag_test(l_iter->f, BM_ELEM_HIDDEN)) {
2054 if (!BM_elem_flag_test(l_iter->f, hflag)) {
2055 return false;
2056 }
2057 }
2058 } while ((l_iter = l_iter->radial_next) != l_first);
2059 }
2060
2061 return true;
2062}
2063
2064bool BM_edge_is_any_face_flag_test(const BMEdge *e, const char hflag)
2065{
2066 if (e->l) {
2067 BMLoop *l_iter, *l_first;
2068
2069 l_iter = l_first = e->l;
2070 do {
2071 if (BM_elem_flag_test(l_iter->f, hflag)) {
2072 return true;
2073 }
2074 } while ((l_iter = l_iter->radial_next) != l_first);
2075 }
2076
2077 return false;
2078}
2079
2080bool BM_edge_is_any_vert_flag_test(const BMEdge *e, const char hflag)
2081{
2082 return (BM_elem_flag_test(e->v1, hflag) || BM_elem_flag_test(e->v2, hflag));
2083}
2084
2085bool BM_face_is_any_vert_flag_test(const BMFace *f, const char hflag)
2086{
2087 BMLoop *l_iter;
2088 BMLoop *l_first;
2089
2090 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2091 do {
2092 if (BM_elem_flag_test(l_iter->v, hflag)) {
2093 return true;
2094 }
2095 } while ((l_iter = l_iter->next) != l_first);
2096 return false;
2097}
2098
2099bool BM_face_is_any_edge_flag_test(const BMFace *f, const char hflag)
2100{
2101 BMLoop *l_iter;
2102 BMLoop *l_first;
2103
2104 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2105 do {
2106 if (BM_elem_flag_test(l_iter->e, hflag)) {
2107 return true;
2108 }
2109 } while ((l_iter = l_iter->next) != l_first);
2110 return false;
2111}
2112
2114{
2115 if (e->l) {
2116 BMLoop *l_iter, *l_first;
2117
2118 l_iter = l_first = e->l;
2119 do {
2120 if (l_iter->f->len == len) {
2121 return true;
2122 }
2123 } while ((l_iter = l_iter->radial_next) != l_first);
2124 }
2125
2126 return false;
2127}
2128
2130{
2131 const float eps = 0.0001f;
2132 float no[3];
2133
2134 BM_face_calc_normal(f, no);
2135 /* Invert comparison so NAN normals don't assert. */
2136 return !(len_squared_v3v3(no, f->no) >= (eps * eps));
2137}
2138
2144static double bm_mesh_calc_volume_face(const BMFace *f)
2145{
2146 const int tottri = f->len - 2;
2149 double vol = 0.0;
2150
2151 BM_face_calc_tessellation(f, false, loops.data(), reinterpret_cast<uint(*)[3]>(index.data()));
2152
2153 for (int j = 0; j < tottri; j++) {
2154 const float *p1 = loops[index[j][0]]->v->co;
2155 const float *p2 = loops[index[j][1]]->v->co;
2156 const float *p3 = loops[index[j][2]]->v->co;
2157
2158 double p1_db[3];
2159 double p2_db[3];
2160 double p3_db[3];
2161
2162 copy_v3db_v3fl(p1_db, p1);
2163 copy_v3db_v3fl(p2_db, p2);
2164 copy_v3db_v3fl(p3_db, p3);
2165
2166 /* co1.dot(co2.cross(co3)) / 6.0 */
2167 double cross[3];
2168 cross_v3_v3v3_db(cross, p2_db, p3_db);
2169 vol += dot_v3v3_db(p1_db, cross);
2170 }
2171 return (1.0 / 6.0) * vol;
2172}
2173double BM_mesh_calc_volume(BMesh *bm, bool is_signed)
2174{
2175 /* warning, calls its own tessellation function, may be slow */
2176 double vol = 0.0;
2177 BMFace *f;
2178 BMIter fiter;
2179
2180 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
2181 vol += bm_mesh_calc_volume_face(f);
2182 }
2183
2184 if (is_signed == false) {
2185 vol = fabs(vol);
2186 }
2187
2188 return vol;
2189}
2190
2192 int *r_groups_array,
2193 int (**r_group_index)[2],
2194 BMLoopFilterFunc filter_fn,
2195 BMLoopPairFilterFunc filter_pair_fn,
2196 void *user_data,
2197 const char hflag_test,
2198 const char htype_step)
2199{
2200 /* NOTE: almost duplicate of #BM_mesh_calc_edge_groups, keep in sync. */
2201
2202#ifndef NDEBUG
2203 int group_index_len = 1;
2204#else
2205 int group_index_len = 32;
2206#endif
2207
2208 int (*group_index)[2] = MEM_new_array_uninitialized<int[2]>(group_index_len, __func__);
2209
2210 int *group_array = r_groups_array;
2211 STACK_DECLARE(group_array);
2212
2213 int group_curr = 0;
2214
2215 uint tot_faces = 0;
2216 uint tot_touch = 0;
2217
2218 BMFace **stack;
2219 STACK_DECLARE(stack);
2220
2221 BMIter iter;
2222 BMFace *f, *f_next;
2223 int i;
2224
2225 STACK_INIT(group_array, bm->totface);
2226
2227 BLI_assert(((htype_step & ~(BM_VERT | BM_EDGE)) == 0) && (htype_step != 0));
2228
2229 /* init the array */
2230 BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
2231 if ((hflag_test == 0) || BM_elem_flag_test(f, hflag_test)) {
2232 tot_faces++;
2234 }
2235 else {
2236 /* never walk over tagged */
2238 }
2239
2240 BM_elem_index_set(f, i); /* set_inline */
2241 }
2243
2244 /* detect groups */
2245 stack = MEM_new_array_uninitialized<BMFace *>(tot_faces, __func__);
2246
2247 f_next = static_cast<BMFace *>(BM_iter_new(&iter, bm, BM_FACES_OF_MESH, nullptr));
2248
2249 while (tot_touch != tot_faces) {
2250 int *group_item;
2251 bool ok = false;
2252
2253 BLI_assert(tot_touch < tot_faces);
2254
2255 STACK_INIT(stack, tot_faces);
2256
2257 for (; f_next; f_next = static_cast<BMFace *>(BM_iter_step(&iter))) {
2258 if (BM_elem_flag_test(f_next, BM_ELEM_TAG) == false) {
2260 STACK_PUSH(stack, f_next);
2261 ok = true;
2262 break;
2263 }
2264 }
2265
2266 BLI_assert(ok == true);
2268
2269 /* manage arrays */
2270 if (group_index_len == group_curr) {
2271 group_index_len *= 2;
2272 group_index = static_cast<int (*)[2]>(
2273 MEM_realloc_uninitialized(group_index, sizeof(*group_index) * group_index_len));
2274 }
2275
2276 group_item = group_index[group_curr];
2277 group_item[0] = STACK_SIZE(group_array);
2278 group_item[1] = 0;
2279
2280 while ((f = STACK_POP(stack))) {
2281 BMLoop *l_iter, *l_first;
2282
2283 /* add face */
2284 STACK_PUSH(group_array, BM_elem_index_get(f));
2285 tot_touch++;
2286 group_item[1]++;
2287 /* done */
2288
2289 if (htype_step & BM_EDGE) {
2290 /* search for other faces */
2291 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2292 do {
2293 BMLoop *l_radial_iter = l_iter->radial_next;
2294 if ((l_radial_iter != l_iter) &&
2295 ((filter_fn == nullptr) || filter_fn(l_iter, user_data)))
2296 {
2297 do {
2298 if ((filter_pair_fn == nullptr) || filter_pair_fn(l_iter, l_radial_iter, user_data))
2299 {
2300 BMFace *f_other = l_radial_iter->f;
2301 if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
2303 STACK_PUSH(stack, f_other);
2304 }
2305 }
2306 } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
2307 }
2308 } while ((l_iter = l_iter->next) != l_first);
2309 }
2310
2311 if (htype_step & BM_VERT) {
2312 BMIter liter;
2313 /* search for other faces */
2314 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2315 do {
2316 if ((filter_fn == nullptr) || filter_fn(l_iter, user_data)) {
2317 BMLoop *l_other;
2318 BM_ITER_ELEM (l_other, &liter, l_iter, BM_LOOPS_OF_LOOP) {
2319 if ((filter_pair_fn == nullptr) || filter_pair_fn(l_iter, l_other, user_data)) {
2320 BMFace *f_other = l_other->f;
2321 if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
2323 STACK_PUSH(stack, f_other);
2324 }
2325 }
2326 }
2327 }
2328 } while ((l_iter = l_iter->next) != l_first);
2329 }
2330 }
2331
2332 group_curr++;
2333 }
2334
2335 MEM_delete(stack);
2336
2337 /* Reduce allocation to the required size. */
2338 if (group_index_len != group_curr) {
2339 group_index = static_cast<int (*)[2]>(
2340 MEM_realloc_uninitialized(group_index, sizeof(*group_index) * group_curr));
2341 }
2342 *r_group_index = group_index;
2343
2344 return group_curr;
2345}
2346
2348 int *r_groups_array,
2349 int (**r_group_index)[2],
2350 BMVertFilterFunc filter_fn,
2351 void *user_data,
2352 const char hflag_test)
2353{
2354 /* NOTE: almost duplicate of #BM_mesh_calc_face_groups, keep in sync. */
2355
2356#ifndef NDEBUG
2357 int group_index_len = 1;
2358#else
2359 int group_index_len = 32;
2360#endif
2361
2362 int (*group_index)[2] = MEM_new_array_uninitialized<int[2]>(group_index_len, __func__);
2363
2364 int *group_array = r_groups_array;
2365 STACK_DECLARE(group_array);
2366
2367 int group_curr = 0;
2368
2369 uint tot_edges = 0;
2370 uint tot_touch = 0;
2371
2372 BMEdge **stack;
2373 STACK_DECLARE(stack);
2374
2375 BMIter iter;
2376 BMEdge *e, *e_next;
2377 int i;
2378 STACK_INIT(group_array, bm->totedge);
2379
2380 /* init the array */
2381 BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
2382 if ((hflag_test == 0) || BM_elem_flag_test(e, hflag_test)) {
2383 tot_edges++;
2385 }
2386 else {
2387 /* never walk over tagged */
2389 }
2390
2391 BM_elem_index_set(e, i); /* set_inline */
2392 }
2394
2395 /* detect groups */
2396 stack = MEM_new_array_uninitialized<BMEdge *>(tot_edges, __func__);
2397
2398 e_next = static_cast<BMEdge *>(BM_iter_new(&iter, bm, BM_EDGES_OF_MESH, nullptr));
2399
2400 while (tot_touch != tot_edges) {
2401 int *group_item;
2402 bool ok = false;
2403
2404 BLI_assert(tot_touch < tot_edges);
2405
2406 STACK_INIT(stack, tot_edges);
2407
2408 for (; e_next; e_next = static_cast<BMEdge *>(BM_iter_step(&iter))) {
2409 if (BM_elem_flag_test(e_next, BM_ELEM_TAG) == false) {
2411 STACK_PUSH(stack, e_next);
2412 ok = true;
2413 break;
2414 }
2415 }
2416
2417 BLI_assert(ok == true);
2419
2420 /* manage arrays */
2421 if (group_index_len == group_curr) {
2422 group_index_len *= 2;
2423 group_index = static_cast<int (*)[2]>(
2424 MEM_realloc_uninitialized(group_index, sizeof(*group_index) * group_index_len));
2425 }
2426
2427 group_item = group_index[group_curr];
2428 group_item[0] = STACK_SIZE(group_array);
2429 group_item[1] = 0;
2430
2431 while ((e = STACK_POP(stack))) {
2432 BMIter viter;
2433 BMIter eiter;
2434 BMVert *v;
2435
2436 /* add edge */
2437 STACK_PUSH(group_array, BM_elem_index_get(e));
2438 tot_touch++;
2439 group_item[1]++;
2440 /* done */
2441
2442 /* search for other edges */
2443 BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
2444 if ((filter_fn == nullptr) || filter_fn(v, user_data)) {
2445 BMEdge *e_other;
2446 BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
2447 if (BM_elem_flag_test(e_other, BM_ELEM_TAG) == false) {
2449 STACK_PUSH(stack, e_other);
2450 }
2451 }
2452 }
2453 }
2454 }
2455
2456 group_curr++;
2457 }
2458
2459 MEM_delete(stack);
2460
2461 /* Reduce allocation to the required size. */
2462 if (group_index_len != group_curr) {
2463 group_index = static_cast<int (*)[2]>(
2464 MEM_realloc_uninitialized(group_index, sizeof(*group_index) * group_curr));
2465 }
2466 *r_group_index = group_index;
2467
2468 return group_curr;
2469}
2470
2472 BMesh *bm, BMVert **verts, BMEdge **edges, BMFace **faces, int (**r_groups)[3])
2473{
2474 int (*groups)[3] = MEM_new_array_uninitialized<int[3]>(bm->totvert, __func__);
2475 STACK_DECLARE(groups);
2476 STACK_INIT(groups, bm->totvert);
2477
2478 /* Clear all selected vertices */
2480
2482 STACK_DECLARE(stack);
2483 STACK_INIT(stack, bm->totvert);
2484
2485 STACK_DECLARE(verts);
2486 STACK_INIT(verts, bm->totvert);
2487
2488 STACK_DECLARE(edges);
2489 STACK_INIT(edges, bm->totedge);
2490
2491 STACK_DECLARE(faces);
2492 STACK_INIT(faces, bm->totface);
2493
2494 BMIter iter;
2495 BMVert *v_stack_init;
2496 BM_ITER_MESH (v_stack_init, &iter, bm, BM_VERTS_OF_MESH) {
2497 if (BM_elem_flag_test(v_stack_init, BM_ELEM_TAG)) {
2498 continue;
2499 }
2500
2501 const uint verts_init = STACK_SIZE(verts);
2502 const uint edges_init = STACK_SIZE(edges);
2503 const uint faces_init = STACK_SIZE(faces);
2504
2505 /* Initialize stack. */
2506 BM_elem_flag_enable(v_stack_init, BM_ELEM_TAG);
2507 STACK_PUSH(verts, v_stack_init);
2508
2509 if (v_stack_init->e != nullptr) {
2510 BMVert *v_iter = v_stack_init;
2511 do {
2512 BMEdge *e_iter, *e_first;
2513 e_iter = e_first = v_iter->e;
2514 do {
2515 if (!BM_elem_flag_test(e_iter, BM_ELEM_TAG)) {
2517 STACK_PUSH(edges, e_iter);
2518
2519 if (e_iter->l != nullptr) {
2520 BMLoop *l_iter, *l_first;
2521 l_iter = l_first = e_iter->l;
2522 do {
2523 if (!BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
2525 STACK_PUSH(faces, l_iter->f);
2526 }
2527 } while ((l_iter = l_iter->radial_next) != l_first);
2528 }
2529
2530 BMVert *v_other = BM_edge_other_vert(e_iter, v_iter);
2531 if (!BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
2533 STACK_PUSH(verts, v_other);
2534
2535 STACK_PUSH(stack, v_other);
2536 }
2537 }
2538 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_iter)) != e_first);
2539 } while ((v_iter = STACK_POP(stack)));
2540 }
2541
2542 int *g = STACK_PUSH_RET(groups);
2543 g[0] = STACK_SIZE(verts) - verts_init;
2544 g[1] = STACK_SIZE(edges) - edges_init;
2545 g[2] = STACK_SIZE(faces) - faces_init;
2546 }
2547
2548 MEM_delete(stack);
2549
2550 /* Reduce allocation to the required size. */
2551 groups = static_cast<int (*)[3]>(
2552 MEM_realloc_uninitialized(groups, sizeof(*groups) * STACK_SIZE(groups)));
2553 *r_groups = groups;
2554 return STACK_SIZE(groups);
2555}
2556
2557float bmesh_subd_falloff_calc(const int falloff, float val)
2558{
2559 switch (falloff) {
2561 val = 3.0f * val * val - 2.0f * val * val * val;
2562 break;
2564 val = sqrtf(2.0f * val - val * val);
2565 break;
2566 case SUBD_FALLOFF_ROOT:
2567 val = sqrtf(val);
2568 break;
2569 case SUBD_FALLOFF_SHARP:
2570 val = val * val;
2571 break;
2572 case SUBD_FALLOFF_LIN:
2573 break;
2575 val = val * (2.0f - val);
2576 break;
2577 default:
2578 BLI_assert(0);
2579 break;
2580 }
2581
2582 return val;
2583}
2584
2585} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
#define DEG2RADF(_deg)
#define M_PI
#define STACK_POP(stack)
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
#define STACK_PUSH_RET(stack)
Read Blender memory allocation and freeing.
#define UNUSED_VARS_NDEBUG(...)
#define BLI_assert(a)
#define ELEM(...)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_DEFAULT_NGON_STACK_SIZE
#define BM_FACE_FIRST_LOOP(p)
#define BM_ELEM_CD_GET_VOID_P(ele, offset)
#define LOOP_VISIT
#define EDGE_VISIT
#define BMESH_ASSERT(a)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
#define BM_ITER_ELEM_INDEX(ele, iter, data, itype, indexvar)
#define BM_iter_new(iter, bm, itype, data)
#define BM_VERT
#define MEM_realloc_uninitialized(vmemh, len)
#define BM_ELEM_API_FLAG_DISABLE(element, f)
#define BM_ELEM_API_FLAG_TEST(element, f)
#define BM_ELEM_API_FLAG_ENABLE(element, f)
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
const T * data() const
Definition BLI_array.hh:323
#define FLT_MAX
#define FLT_EPSILON
float dot(VecOp< float, D >, VecOp< float, D >) RET
VecBase< float, 3 > cross(VecOp< float, 3 >, VecOp< float, 3 >) RET
float length(VecOp< float, D >) RET
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
ccl_device_inline dual3 fabs(const ccl_private dual3 &a)
Definition math_dual.h:241
BMesh Iterators.
bool BM_loop_share_edge_check(BMLoop *l_a, BMLoop *l_b)
float BM_loop_calc_face_normal_safe_vcos(const BMLoop *l, const float normal_fallback[3], float const (*vertexCos)[3], float r_normal[3])
void BM_face_calc_tessellation(const BMFace *f, const bool use_fixed_quad, BMLoop **r_loops, uint(*r_index)[3])
void BM_loop_calc_face_direction(const BMLoop *l, float r_dir[3])
BM_loop_calc_face_direction.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BM_edge_calc_face_tangent(const BMEdge *e, const BMLoop *e_loop, float r_tangent[3])
BMESH EDGE/FACE TANGENT.
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float shell_v3v3_normalized_to_dist(const float a[3], const float b[3])
float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
bool BM_face_pair_overlap_check_subset_same_winding(const BMLoop *l_a, const BMLoop *l_a_end, const BMLoop *l_b, const BMLoop *l_b_end)
Definition bmesh_core.cc:45
int BM_loop_region_loops_count(BMLoop *l)
int BM_edge_face_count(const BMEdge *e)
bool BM_verts_in_face(BMVert **varr, int len, BMFace *f)
bool BM_face_is_any_vert_flag_test(const BMFace *f, const char hflag)
BMFace * 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)
float BM_face_calc_normal_subset(const BMLoop *l_first, const BMLoop *l_last, float r_no[3])
bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
bool BM_edge_is_any_face_len_test(const BMEdge *e, const int len)
bool BM_face_exists_overlap_subset(BMVert **varr, const int len)
MINLINE double dot_v3v3_db(const double a[3], const double b[3]) ATTR_WARN_UNUSED_RESULT
BMFace * BM_face_exists_overlap(BMVert **varr, const int len)
float BM_edge_calc_face_angle(const BMEdge *e)
BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
float BM_vert_calc_median_tagged_edge_length(const BMVert *v)
bool BM_edge_share_face_check(BMEdge *e1, BMEdge *e2)
ATTR_WARN_UNUSED_RESULT const BMLoop * l
MINLINE void copy_v3db_v3fl(double r[3], const float a[3])
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
float BM_edge_calc_face_angle_signed_ex(const BMEdge *e, const float fallback)
BMESH EDGE/FACE ANGLE.
float dist_signed_squared_to_plane_v3(const float p[3], const float plane[4])
Definition math_geom.cc:479
bool BM_vert_is_wire(const BMVert *v)
float angle_v3v3v3(const float a[3], const float b[3], const float c[3]) ATTR_WARN_UNUSED_RESULT
BMVert * BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
bool BM_edge_is_convex(const BMEdge *e)
float BM_edge_calc_face_angle_with_imat3_ex(const BMEdge *e, const float imat3[3][3], const float fallback)
BMESH EDGE/FACE ANGLE.
bool BM_edge_is_any_face_flag_test(const BMEdge *e, const char hflag)
BMLoop * BM_edge_vert_share_loop(BMLoop *l, BMVert *v)
Return the Loop Shared by Edge and Vert.
BMLoop * BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
BMLoop * BM_face_edge_share_loop(BMFace *f, BMEdge *e)
Return the Loop Shared by Face and Edge.
bool CustomData_data_equals(eCustomDataType type, const void *data1, const void *data2)
int bmesh_disk_facevert_count(const BMVert *v)
DISK COUNT FACE VERT.
bool BM_face_is_any_edge_flag_test(const BMFace *f, const char hflag)
int BM_face_share_face_count(BMFace *f_a, BMFace *f_b)
int BM_edge_face_count_at_most(const BMEdge *e, const int count_max)
BMFace * 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)
float BM_loop_calc_face_normal_safe_ex(const BMLoop *l, const float epsilon_sq, float r_normal[3])
BM_loop_calc_face_normal.
BMLoop * BM_face_find_shortest_loop(BMFace *f)
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
float BM_vert_calc_shell_factor(const BMVert *v)
bool BM_vert_is_all_face_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
BMLoop * BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v)
Other Loop in Face Sharing a Vertex.
ATTR_WARN_UNUSED_RESULT const BMVert * v
static int bm_loop_region_count__recursive(BMEdge *e, BMVert *v)
float BM_vert_calc_edge_angle(const BMVert *v)
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
float BM_edge_calc_length(const BMEdge *e)
int 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)
int BM_vert_edge_count_at_most(const BMVert *v, const int count_max)
bool BM_vert_is_boundary(const BMVert *v)
BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BM_edge_ordered_verts_ex(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2, const BMLoop *edge_loop)
BMLoop * BM_face_find_longest_loop(BMFace *f)
void BM_loop_calc_face_tangent(const BMLoop *l, float r_tangent[3])
BM_loop_calc_face_tangent.
BMLoop * bmesh_disk_faceloop_find_first(const BMEdge *e, const BMVert *v)
int BM_face_share_edge_count(BMFace *f_a, BMFace *f_b)
BMFace * 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)
MINLINE void sub_v3_v3(float r[3], const float a[3])
bool BM_face_share_edge_check(BMFace *f_a, BMFace *f_b)
bool BM_vert_is_edge_pair_manifold(const BMVert *v)
void mul_transposed_m3_v3(const float M[3][3], float r[3])
bool BM_face_share_face_check(BMFace *f_a, BMFace *f_b)
MINLINE bool equals_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
float BM_loop_calc_face_normal(const BMLoop *l, float r_normal[3])
BM_loop_calc_face_normal.
double BM_mesh_calc_volume(BMesh *bm, bool is_signed)
int bmesh_disk_count_at_most(const BMVert *v, int count_max)
int BM_vert_face_count(const BMVert *v)
int BM_loop_region_loops_count_at_most(BMLoop *l, int *r_loop_total)
static float bm_face_calc_split_dot(BMLoop *l_a, BMLoop *l_b)
bool BM_face_share_vert_check(BMFace *f_a, BMFace *f_b)
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
float BM_vert_calc_shell_factor_ex(const BMVert *v, const float no[3], const char hflag)
@ SUBD_FALLOFF_INVSQUARE
float BM_edge_calc_face_angle_ex(const BMEdge *e, const float fallback)
BMESH EDGE/FACE ANGLE.
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
bool BM_vert_is_all_edge_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
BMLoop * BM_loop_other_vert_loop_by_edge(BMLoop *l, BMEdge *e)
int bmesh_disk_count(const BMVert *v)
BMLoop * BM_vert_find_first_loop(BMVert *v)
static int bm_loop_region_count__clear(BMLoop *l)
int BM_vert_edge_count_nonwire(const BMVert *v)
MINLINE void cross_v3_v3v3_db(double r[3], const double a[3], const double b[3])
bool BM_vert_in_face(BMVert *v, BMFace *f)
bool BM_vert_pair_share_face_check(BMVert *v_a, BMVert *v_b)
MINLINE void negate_v3(float r[3])
BMLoop * BM_edge_find_first_loop_visible(BMEdge *e)
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BM_edge_ordered_verts(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
BMLoop * BM_loop_find_next_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq)
BMLoop * BM_edge_other_loop(BMEdge *e, BMLoop *l)
BMLoop * BM_loop_other_vert_loop(BMLoop *l, BMVert *v)
Other Loop in Face Sharing a Vert.
bool(*)(const BMVert *, void *user_data) BMVertFilterFunc
float BM_vert_calc_edge_angle_ex(const BMVert *v, const float fallback)
BMESH VERT/EDGE ANGLE.
int BM_vert_face_count_at_most(const BMVert *v, int count_max)
float BM_loop_calc_face_normal_safe(const BMLoop *l, float r_normal[3])
float bmesh_subd_falloff_calc(const int falloff, float val)
BMFace * 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)
float BM_loop_calc_face_angle(const BMLoop *l)
BMFace * BM_face_exists(BMVert *const *varr, int len)
MINLINE void mul_v3_v3fl(float r[3], const float a[3], float f)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
MINLINE float normalize_v3(float n[3])
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
float BM_edge_calc_length_squared(const BMEdge *e)
bool BM_edge_share_quad_check(BMEdge *e1, BMEdge *e2)
MINLINE bool compare_v3v3(const float v1[3], const float v2[3], float limit) ATTR_WARN_UNUSED_RESULT
bool BM_edge_is_all_face_flag_test(const BMEdge *e, const char hflag, const bool respect_hide)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
bool BM_vert_is_manifold_region(const BMVert *v)
int 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)
BMEdge * BM_vert_other_disk_edge(BMVert *v, BMEdge *e_first)
BMLoop * BM_vert_find_first_loop_visible(BMVert *v)
float BM_face_calc_normal(const BMFace *f, float r_no[3])
BMESH UPDATE FACE NORMAL.
BMFace * BM_face_exists_subset_from_face(BMLoop *l_a, BMLoop *l_b, const int f_len)
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
bool BM_vert_is_edge_pair(const BMVert *v)
BMLoop * BM_loop_find_prev_nodouble(BMLoop *l, BMLoop *l_stop, const float eps_sq)
bool BM_face_exists_multi_edge(BMEdge **earr, int len)
int BM_face_share_vert_count(BMFace *f_a, BMFace *f_b)
bool BM_vert_edge_pair(const BMVert *v, BMEdge **r_e_a, BMEdge **r_e_b)
BMEdge * BM_edge_find_double(BMEdge *e)
float BM_edge_calc_face_angle_with_imat3(const BMEdge *e, const float imat3[3][3])
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
int BM_verts_in_face_count(BMVert **varr, int len, BMFace *f)
int bmesh_disk_facevert_count_at_most(const BMVert *v, const int count_max)
BMLoop * BM_face_vert_share_loop(BMFace *f, BMVert *v)
Return the Loop Shared by Face and Vertex.
BMFace * BM_face_find_double(BMFace *f)
float BM_loop_point_side_of_edge_test(const BMLoop *l, const float co[3])
bool BM_vert_is_manifold(const BMVert *v)
bool(*)(const BMLoop *, void *user_data) BMLoopFilterFunc
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
bool BM_face_is_normal_valid(const BMFace *f)
BMLoop * BM_face_other_edge_loop(BMFace *f, BMEdge *e, BMVert *v)
Other Loop in Face Sharing an Edge.
bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
static double bm_mesh_calc_volume_face(const BMFace *f)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
@ BM_ELEM_INTERNAL_TAG
BMLoop * bmesh_disk_faceloop_find_first_visible(const BMEdge *e, const BMVert *v)
float dist_signed_squared_to_corner_v3v3v3(const float p[3], const float v1[3], const float v2[3], const float v3[3], const float axis_ref[3])
Definition math_geom.cc:562
MINLINE bool is_zero_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
bool BM_vert_pair_share_face_check_cb(BMVert *v_a, BMVert *v_b, bool(*test_fn)(BMFace *, void *user_data), void *user_data)
bool BM_edge_is_any_vert_flag_test(const BMEdge *e, const char hflag)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
float BM_edge_calc_face_angle_signed(const BMEdge *e)
bool BM_vert_face_check(const BMVert *v)
int BM_mesh_calc_edge_groups_as_arrays(BMesh *bm, BMVert **verts, BMEdge **edges, BMFace **faces, int(**r_groups)[3])
bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
bool BM_edge_is_contiguous_loop_cd(const BMEdge *e, const int cd_loop_type, const int cd_loop_offset)
int BM_vert_edge_count(const BMVert *v)
BMLoop * BM_loop_other_edge_loop(BMLoop *l, BMVert *v)
bool BM_face_pair_overlap_check_subset_swap_winding(const BMLoop *l_a, const BMLoop *l_a_end, const BMLoop *l_b, const BMLoop *l_b_end)
Definition bmesh_core.cc:87
bool(*)(const BMLoop *, const BMLoop *, void *user_data) BMLoopPairFilterFunc
float BM_loop_point_side_of_loop_test(const BMLoop *l, const float co[3])
bool BM_loop_is_convex(const BMLoop *l)
float 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])
const btScalar eps
Definition poly34.cpp:11
#define sqrtf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
struct BMLoop * l
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct BMEdge * e
struct LinkNode * next
struct BMLoop * radial_next