Blender V5.3
bmesh_core.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
10
11#include "MEM_guardedalloc.h"
12
13#include "BLI_enum_flags.hh"
14#include "BLI_linklist_stack.hh"
15#include "BLI_math_vector_c.hh"
17#include "BLI_vector.hh"
18
19#include "BKE_customdata.hh"
20#include "BKE_mesh.hh"
21
22#include "bmesh.hh"
24
25namespace blender {
26
27/* use so valgrinds memcheck alerts us when undefined index is used.
28 * TESTING ONLY! */
29// #define USE_DEBUG_INDEX_MEMCHECK
30
31#ifdef USE_DEBUG_INDEX_MEMCHECK
32# define DEBUG_MEMCHECK_INDEX_INVALIDATE(ele) \
33 { \
34 int undef_idx; \
35 BM_elem_index_set(ele, undef_idx); /* set_ok_invalid */ \
36 } \
37 (void)0
38
39#endif
40
41/* -------------------------------------------------------------------- */
44
46 const BMLoop *l_a_end,
47 const BMLoop *l_b,
48 const BMLoop *l_b_end)
49{
50 BLI_assert(l_a->f == l_a_end->f);
51 BLI_assert(l_b->f == l_b_end->f);
52 BLI_assert(l_a->f != l_b->f);
53 UNUSED_VARS_NDEBUG(l_b_end);
54#ifndef NDEBUG
55 /* Ensure the loops have the same topological distance. */
56 {
57 const BMLoop *l_a_iter = l_a;
58 const BMLoop *l_b_iter = l_b;
59 while (true) {
60 if (l_a_iter == l_a_end || l_b_iter == l_b_end) {
61 break;
62 }
63 l_a_iter = l_a_iter->next;
64 l_b_iter = l_b_iter->next;
65 }
66 BLI_assert(l_a_iter == l_a_end);
67 BLI_assert(l_b_iter == l_b_end);
68 }
69#endif
70 const BMLoop *l_a_iter = l_a;
71 const BMLoop *l_b_iter = l_b;
72 BLI_assert(l_a->f != l_b->f);
73 while (true) {
74 if (l_b_iter->v != l_a_iter->v) {
75 return false;
76 }
77 if (l_a_iter == l_a_end) {
78 BLI_assert(l_b_iter == l_b_end);
79 break;
80 }
81 l_a_iter = l_a_iter->next;
82 l_b_iter = l_b_iter->next;
83 }
84 return true;
85}
86
88 const BMLoop *l_a_end,
89 const BMLoop *l_b,
90 const BMLoop *l_b_end)
91{
92 BLI_assert(l_a->f == l_a_end->f);
93 BLI_assert(l_b->f == l_b_end->f);
94 BLI_assert(l_a->f != l_b->f);
95 UNUSED_VARS_NDEBUG(l_b_end);
96#ifndef NDEBUG
97 /* Ensure the loops have the same topological distance. */
98 {
99 const BMLoop *l_a_iter = l_a;
100 const BMLoop *l_b_iter = l_b;
101 while (true) {
102 if (l_a_iter == l_a_end || l_b_iter == l_b_end) {
103 break;
104 }
105 l_a_iter = l_a_iter->next;
106 l_b_iter = l_b_iter->prev;
107 }
108 BLI_assert(l_a_iter == l_a_end);
109 BLI_assert(l_b_iter == l_b_end);
110 }
111#endif
112 const BMLoop *l_a_iter = l_a;
113 const BMLoop *l_b_iter = l_b;
114 while (true) {
115 if (l_b_iter->v != l_a_iter->v) {
116 return false;
117 }
118 if (l_a_iter == l_a_end) {
119 BLI_assert(l_b_iter == l_b_end);
120 break;
121 }
122 l_a_iter = l_a_iter->next;
123 l_b_iter = l_b_iter->prev;
124 }
125 return true;
126}
127
129
131 const float co[3],
132 const BMVert *v_example,
133 const eBMCreateFlag create_flag)
134{
135 BMVert *v = static_cast<BMVert *>(BLI_mempool_alloc(bm->vpool));
136
137 BLI_assert((v_example == nullptr) || (v_example->head.htype == BM_VERT));
138 BLI_assert(!(create_flag & 1));
139
140 /* --- assign all members --- */
141 v->head.data = nullptr;
142
143#ifdef USE_DEBUG_INDEX_MEMCHECK
144 DEBUG_MEMCHECK_INDEX_INVALIDATE(v);
145#else
146 BM_elem_index_set(v, -1); /* set_ok_invalid */
147#endif
148
149 v->head.htype = BM_VERT;
150 v->head.hflag = 0;
151 v->head.api_flag = 0;
152
153 /* allocate flags */
154 if (bm->use_toolflags) {
155 (reinterpret_cast<BMVert_OFlag *>(v))->oflags = static_cast<BMFlagLayer *>(
157 }
158
159 /* 'v->no' is handled by BM_elem_attrs_copy */
160 if (co) {
161 copy_v3_v3(v->co, co);
162 }
163 else {
164 zero_v3(v->co);
165 }
166 /* 'v->no' set below */
167
168 v->e = nullptr;
169 /* --- done --- */
170
171 /* disallow this flag for verts - its meaningless */
172 BLI_assert((create_flag & BM_CREATE_NO_DOUBLE) == 0);
173
174 /* may add to middle of the pool */
178
179 bm->totvert++;
180
181 if (!(create_flag & BM_CREATE_SKIP_CD)) {
182 if (v_example) {
183 int *keyi;
184
185 /* handles 'v->no' too */
186 BM_elem_attrs_copy(bm, v_example, v);
187
188 /* Exception: don't copy the original shape-key index. */
189 keyi = static_cast<int *>(CustomData_bmesh_get(&bm->vdata, v->head.data, CD_SHAPE_KEYINDEX));
190 if (keyi) {
191 *keyi = ORIGINDEX_NONE;
192 }
193 }
194 else {
196 zero_v3(v->no);
197 }
198 }
199 else {
200 if (v_example) {
201 copy_v3_v3(v->no, v_example->no);
202 }
203 else {
204 zero_v3(v->no);
205 }
206 }
207
209
210 return v;
211}
212
214 BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *e_example, const eBMCreateFlag create_flag)
215{
216 BMEdge *e;
217
218 BLI_assert(v1 != v2);
220 BLI_assert((e_example == nullptr) || (e_example->head.htype == BM_EDGE));
221 BLI_assert(!(create_flag & 1));
222
223 if ((create_flag & BM_CREATE_NO_DOUBLE) && (e = BM_edge_exists(v1, v2))) {
224 return e;
225 }
226
227 e = static_cast<BMEdge *>(BLI_mempool_alloc(bm->epool));
228
229 /* --- assign all members --- */
230 e->head.data = nullptr;
231
232#ifdef USE_DEBUG_INDEX_MEMCHECK
233 DEBUG_MEMCHECK_INDEX_INVALIDATE(e);
234#else
235 BM_elem_index_set(e, -1); /* set_ok_invalid */
236#endif
237
238 e->head.htype = BM_EDGE;
240 e->head.api_flag = 0;
241
242 /* allocate flags */
243 if (bm->use_toolflags) {
244 (reinterpret_cast<BMEdge_OFlag *>(e))->oflags = static_cast<BMFlagLayer *>(
246 }
247
248 e->v1 = v1;
249 e->v2 = v2;
250 e->l = nullptr;
251
252 memset(&e->v1_disk_link, 0, sizeof(BMDiskLink));
253 memset(&e->v2_disk_link, 0, sizeof(BMDiskLink));
254
255 /* --- done --- */
256
259
260 /* may add to middle of the pool */
264
265 bm->totedge++;
266
267 if (!(create_flag & BM_CREATE_SKIP_CD)) {
268 if (e_example) {
269 BM_elem_attrs_copy(bm, e_example, e);
270 }
271 else {
273 }
274 }
275
277
278 return e;
279}
280
287 BMVert *v,
288 BMEdge *e,
289 BMFace *f,
290 const BMLoop *l_example,
291 const eBMCreateFlag create_flag)
292{
293 BMLoop *l = nullptr;
294
295 l = static_cast<BMLoop *>(BLI_mempool_alloc(bm->lpool));
296
297 BLI_assert((l_example == nullptr) || (l_example->head.htype == BM_LOOP));
298 BLI_assert(!(create_flag & 1));
299
300#ifndef NDEBUG
301 if (l_example) {
302 /* ensure passing a loop is either sharing the same vertex, or entirely disconnected
303 * use to catch mistake passing in loop offset-by-one. */
304 BLI_assert((v == l_example->v) || !ELEM(v, l_example->prev->v, l_example->next->v));
305 }
306#endif
307
308 /* --- assign all members --- */
309 l->head.data = nullptr;
310
311#ifdef USE_DEBUG_INDEX_MEMCHECK
312 DEBUG_MEMCHECK_INDEX_INVALIDATE(l);
313#else
314 BM_elem_index_set(l, -1); /* set_ok_invalid */
315#endif
316
317 l->head.htype = BM_LOOP;
318 l->head.hflag = 0;
319 l->head.api_flag = 0;
320
321 l->v = v;
322 l->e = e;
323 l->f = f;
324
325 l->radial_next = nullptr;
326 l->radial_prev = nullptr;
327 l->next = nullptr;
328 l->prev = nullptr;
329 /* --- done --- */
330
331 /* may add to middle of the pool */
334
335 bm->totloop++;
336
337 if (!(create_flag & BM_CREATE_SKIP_CD)) {
338 if (l_example) {
339 /* no need to copy attrs, just handle customdata */
341 }
342 else {
344 }
345 }
346
347 return l;
348}
349
351 BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte, const eBMCreateFlag create_flag)
352{
353#ifdef USE_BMESH_HOLES
354 BMLoopList *lst = BLI_mempool_calloc(bm->looplistpool);
355#endif
356 BMLoop *l = bm_loop_create(bm, startv, starte, f, nullptr /* starte->l */, create_flag);
357
359
360#ifdef USE_BMESH_HOLES
361 lst->first = lst->last = l;
362 BLI_addtail(&f->loops, lst);
363#else
364 f->l_first = l;
365#endif
366
367 return l;
368}
369
371 BMFace *f,
372 const bool copy_verts,
373 const bool copy_edges)
374{
377 BMLoop *l_iter;
378 BMLoop *l_first;
379 BMFace *f_copy;
380 int i;
381
382 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
383 i = 0;
384 do {
385 if (copy_verts) {
386 verts[i] = BM_vert_create(bm_dst, l_iter->v->co, l_iter->v, BM_CREATE_NOP);
387 }
388 else {
389 verts[i] = l_iter->v;
390 }
391 i++;
392 } while ((l_iter = l_iter->next) != l_first);
393
394 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
395 i = 0;
396 do {
397 if (copy_edges) {
398 BMVert *v1, *v2;
399
400 if (l_iter->e->v1 == verts[i]) {
401 v1 = verts[i];
402 v2 = verts[(i + 1) % f->len];
403 }
404 else {
405 v2 = verts[i];
406 v1 = verts[(i + 1) % f->len];
407 }
408
409 edges[i] = BM_edge_create(bm_dst, v1, v2, l_iter->e, BM_CREATE_NOP);
410 }
411 else {
412 edges[i] = l_iter->e;
413 }
414 i++;
415 } while ((l_iter = l_iter->next) != l_first);
416
417 f_copy = BM_face_create(bm_dst, verts.data(), edges.data(), f->len, nullptr, BM_CREATE_SKIP_CD);
418
419 return f_copy;
420}
421
423 const BMCustomDataCopyMap &cd_face_map,
424 const BMCustomDataCopyMap &cd_loop_map,
425 BMFace *f,
426 const bool copy_verts,
427 const bool copy_edges)
428{
429 BMFace *f_copy = bm_face_copy_impl(bm_dst, f, copy_verts, copy_edges);
430
431 /* Copy custom-data. */
432 BM_elem_attrs_copy(bm_dst, cd_face_map, f, f_copy);
433
434 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
435 BMLoop *l_copy = BM_FACE_FIRST_LOOP(f_copy);
436 BMLoop *l_iter = l_first;
437 do {
438 BM_elem_attrs_copy(bm_dst, cd_loop_map, l_iter, l_copy);
439 l_copy = l_copy->next;
440 } while ((l_iter = l_iter->next) != l_first);
441 return f_copy;
442}
443
444BMFace *BM_face_copy(BMesh *bm_dst, BMFace *f, const bool copy_verts, const bool copy_edges)
445{
446 BMFace *f_copy = bm_face_copy_impl(bm_dst, f, copy_verts, copy_edges);
447
448 /* Copy custom-data. */
449 BM_elem_attrs_copy(bm_dst, f, f_copy);
450
451 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
452 BMLoop *l_copy = BM_FACE_FIRST_LOOP(f_copy);
453 BMLoop *l_iter = l_first;
454 do {
455 BM_elem_attrs_copy(bm_dst, l_iter, l_copy);
456 l_copy = l_copy->next;
457 } while ((l_iter = l_iter->next) != l_first);
458 return f_copy;
459}
460
468{
469 BMFace *f;
470
471 f = static_cast<BMFace *>(BLI_mempool_alloc(bm->fpool));
472
473 /* --- assign all members --- */
474 f->head.data = nullptr;
475#ifdef USE_DEBUG_INDEX_MEMCHECK
476 DEBUG_MEMCHECK_INDEX_INVALIDATE(f);
477#else
478 BM_elem_index_set(f, -1); /* set_ok_invalid */
479#endif
480
481 f->head.htype = BM_FACE;
482 f->head.hflag = 0;
483 f->head.api_flag = 0;
484
485 /* allocate flags */
486 if (bm->use_toolflags) {
487 (reinterpret_cast<BMFace_OFlag *>(f))->oflags = static_cast<BMFlagLayer *>(
489 }
490
491#ifdef USE_BMESH_HOLES
492 f->loops.clear_no_delete();
493#else
494 f->l_first = nullptr;
495#endif
496 f->len = 0;
497 /* caller must initialize */
498 // zero_v3(f->no);
499 f->mat_nr = 0;
500 /* --- done --- */
501
502 /* may add to middle of the pool */
506
507 bm->totface++;
508
509#ifdef USE_BMESH_HOLES
510 f->totbounds = 0;
511#endif
512
513 return f;
514}
515
517 BMVert *const *verts,
518 BMEdge *const *edges,
519 const int len,
520 const BMFace *f_example,
521 const eBMCreateFlag create_flag)
522{
523 BMFace *f = nullptr;
524 BMLoop *l, *startl, *lastl;
525 int i;
526
527 BLI_assert((f_example == nullptr) || (f_example->head.htype == BM_FACE));
528 BLI_assert(!(create_flag & 1));
529
530 if (len == 0) {
531 /* just return nullptr for now */
532 return nullptr;
533 }
534
535 if (create_flag & BM_CREATE_NO_DOUBLE) {
536 /* Check if face already exists */
537 f = BM_face_exists(verts, len);
538 if (f != nullptr) {
539 return f;
540 }
541 }
542
544
545 startl = lastl = bm_face_boundary_add(bm, f, verts[0], edges[0], create_flag);
546
547 for (i = 1; i < len; i++) {
548 l = bm_loop_create(bm, verts[i], edges[i], f, nullptr /* edges[i]->l */, create_flag);
549
550 bmesh_radial_loop_append(edges[i], l);
551
552 l->prev = lastl;
553 lastl->next = l;
554 lastl = l;
555 }
556
557 startl->prev = lastl;
558 lastl->next = startl;
559
560 f->len = len;
561
562 if (!(create_flag & BM_CREATE_SKIP_CD)) {
563 if (f_example) {
564 BM_elem_attrs_copy(bm, f_example, f);
565 }
566 else {
568 zero_v3(f->no);
569 }
570 }
571 else {
572 if (f_example) {
573 copy_v3_v3(f->no, f_example->no);
574 }
575 else {
576 zero_v3(f->no);
577 }
578 }
579
581
582 return f;
583}
584
586 BMVert **vert_arr,
587 const int len,
588 const BMFace *f_example,
589 const eBMCreateFlag create_flag,
590 const bool create_edges)
591{
593
594 if (create_edges) {
595 BM_edges_from_verts_ensure(bm, edge_arr.data(), vert_arr, len);
596 }
597 else {
598 if (BM_edges_from_verts(edge_arr.data(), vert_arr, len) == false) {
599 return nullptr;
600 }
601 }
602
603 return BM_face_create(bm, vert_arr, edge_arr.data(), len, f_example, create_flag);
604}
605
606#ifndef NDEBUG
607
642
643int bmesh_elem_check(void *element, const char htype)
644{
645 BMHeader *head = static_cast<BMHeader *>(element);
647
648 if (!element) {
649 return IS_NULL;
650 }
651
652 if (head->htype != htype) {
653 return IS_WRONG_TYPE;
654 }
655
656 switch (htype) {
657 case BM_VERT: {
658 BMVert *v = static_cast<BMVert *>(element);
659 if (v->e && v->e->head.htype != BM_EDGE) {
661 }
662 break;
663 }
664 case BM_EDGE: {
665 BMEdge *e = static_cast<BMEdge *>(element);
666 if (e->v1_disk_link.prev == nullptr || e->v2_disk_link.prev == nullptr ||
667 e->v1_disk_link.next == nullptr || e->v2_disk_link.next == nullptr)
668 {
670 }
671
672 if (e->l && e->l->head.htype != BM_LOOP) {
674 }
675 if (e->l && e->l->f->head.htype != BM_FACE) {
677 }
678 if (e->l && (e->l->radial_next == nullptr || e->l->radial_prev == nullptr)) {
680 }
681 if (e->l && e->l->f->len <= 0) {
683 }
684 break;
685 }
686 case BM_LOOP: {
687 BMLoop *l = static_cast<BMLoop *>(element);
688 BMLoop *l2;
689 int i;
690
691 if (l->f->head.htype != BM_FACE) {
693 }
694 if (l->e->head.htype != BM_EDGE) {
696 }
697 if (l->v->head.htype != BM_VERT) {
699 }
700 if (!BM_vert_in_edge(l->e, l->v)) {
701 fprintf(stderr,
702 "%s: fatal bmesh error (vert not in edge)! (bmesh internal error)\n",
703 __func__);
705 }
706
707 if (l->radial_next == nullptr || l->radial_prev == nullptr) {
709 }
710 if (l->f->len <= 0) {
712 }
713
714 /* validate boundary loop -- invalid for hole loops, of course,
715 * but we won't be allowing those for a while yet */
716 l2 = l;
717 i = 0;
718 do {
719 if (i >= BM_NGON_MAX) {
720 break;
721 }
722
723 i++;
724 } while ((l2 = l2->next) != l);
725
726 if (i != l->f->len || l2 != l) {
728 }
729
732 }
733
734 break;
735 }
736 case BM_FACE: {
737 BMFace *f = static_cast<BMFace *>(element);
738 BMLoop *l_iter;
739 BMLoop *l_first;
740 int len = 0;
741
742# ifdef USE_BMESH_HOLES
743 if (!f->loops.first)
744# else
745 if (!f->l_first)
746# endif
747 {
748 err |= IS_FACE_NULL_LOOP;
749 }
750 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
751 do {
752 if (l_iter->f != f) {
753 fprintf(stderr,
754 "%s: loop inside one face points to another! (bmesh internal error)\n",
755 __func__);
757 }
758
759 if (!l_iter->e) {
760 err |= IS_FACE_NULL_EDGE;
761 }
762 if (!l_iter->v) {
763 err |= IS_FACE_NULL_VERT;
764 }
765 if (l_iter->e && l_iter->v) {
766 if (!BM_vert_in_edge(l_iter->e, l_iter->v) ||
767 !BM_vert_in_edge(l_iter->e, l_iter->next->v))
768 {
770 }
771
772 if (!bmesh_radial_validate(bmesh_radial_length(l_iter), l_iter)) {
774 }
775
776 if (bmesh_disk_count_at_most(l_iter->v, 2) < 2) {
778 }
779 }
780
781 /* check for duplicates */
784 }
786 if (l_iter->v) {
789 }
791 }
792 if (l_iter->e) {
795 }
797 }
798
799 len++;
800 } while ((l_iter = l_iter->next) != l_first);
801
802 /* cleanup duplicates flag */
803 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
804 do {
806 if (l_iter->v) {
808 }
809 if (l_iter->e) {
811 }
812 } while ((l_iter = l_iter->next) != l_first);
813
814 if (len != f->len) {
816 }
817 break;
818 }
819 default:
820 BLI_assert(0);
821 break;
822 }
823
824 BMESH_ASSERT(err == 0);
825
826 return err;
827}
828
829#endif /* !NDEBUG */
830
836{
837 bm->totvert--;
841
843
844 if (v->head.data) {
846 }
847
848 if (bm->vtoolflagpool) {
849 BLI_mempool_free(bm->vtoolflagpool, (reinterpret_cast<BMVert_OFlag *>(v))->oflags);
850 }
852}
853
859{
860 bm->totedge--;
864
866
867 if (e->head.data) {
869 }
870
871 if (bm->etoolflagpool) {
872 BLI_mempool_free(bm->etoolflagpool, (reinterpret_cast<BMEdge_OFlag *>(e))->oflags);
873 }
875}
876
882{
883 if (bm->act_face == f) {
884 bm->act_face = nullptr;
885 }
886
887 bm->totface--;
891
893
894 if (f->head.data) {
896 }
897
898 if (bm->ftoolflagpool) {
899 BLI_mempool_free(bm->ftoolflagpool, (reinterpret_cast<BMFace_OFlag *>(f))->oflags);
900 }
902}
903
909{
910 bm->totloop--;
913
914 if (l->head.data) {
916 }
917
919}
920
922{
924 BMLoop *l_iter;
925 BMLoop *l_first;
926 int i = 0;
927
928 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
929 do {
930 edges[i++] = l_iter->e;
931 } while ((l_iter = l_iter->next) != l_first);
932
933 /* Take care, the first iteration kills `f`. */
934 for (BMEdge *e : edges) {
935 BM_edge_kill(bm, e);
936 }
937}
938
940{
942 BMLoop *l_iter;
943 BMLoop *l_first;
944 int i = 0;
945
946 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
947 do {
948 verts[i++] = l_iter->v;
949 } while ((l_iter = l_iter->next) != l_first);
950
951 /* Take care, the first iteration kills `f`. */
952 for (BMVert *v : verts) {
953 BM_vert_kill(bm, v);
954 }
955}
956
958{
959#ifdef USE_BMESH_HOLES
960 BMLoopList *ls, *ls_next;
961#endif
962
963#ifdef NDEBUG
964 /* check length since we may be removing degenerate faces */
965 if (f->len >= 3) {
967 }
968#endif
969
970#ifdef USE_BMESH_HOLES
971 for (ls = f->loops.first; ls; ls = ls_next)
972#else
973 if (f->l_first)
974#endif
975 {
976 BMLoop *l_iter, *l_next, *l_first;
977
978#ifdef USE_BMESH_HOLES
979 ls_next = ls->next;
980 l_iter = l_first = ls->first;
981#else
982 l_iter = l_first = f->l_first;
983#endif
984
985 do {
986 l_next = l_iter->next;
987
988 bmesh_radial_loop_remove(l_iter->e, l_iter);
989 bm_kill_only_loop(bm, l_iter);
990
991 } while ((l_iter = l_next) != l_first);
992
993#ifdef USE_BMESH_HOLES
994 BLI_mempool_free(bm->looplistpool, ls);
995#endif
996 }
997
999}
1000
1002{
1003#ifdef USE_BMESH_HOLES
1004 BMLoopList *ls, *ls_next;
1005#endif
1006
1008
1009#ifdef USE_BMESH_HOLES
1010 for (ls = f->loops.first; ls; ls = ls_next)
1011#else
1012 if (f->l_first)
1013#endif
1014 {
1015 BMLoop *l_iter, *l_next, *l_first;
1016
1017#ifdef USE_BMESH_HOLES
1018 ls_next = ls->next;
1019 l_iter = l_first = ls->first;
1020#else
1021 l_iter = l_first = f->l_first;
1022#endif
1023
1024 do {
1025 BMEdge *e;
1026 l_next = l_iter->next;
1027
1028 e = l_iter->e;
1029 bmesh_radial_loop_remove(e, l_iter);
1030 bm_kill_only_loop(bm, l_iter);
1031
1032 if (e->l == nullptr) {
1033 BMVert *v1 = e->v1, *v2 = e->v2;
1034
1038
1039 if (v1->e == nullptr) {
1040 bm_kill_only_vert(bm, v1);
1041 }
1042 if (v2->e == nullptr) {
1044 }
1045 }
1046 } while ((l_iter = l_next) != l_first);
1047
1048#ifdef USE_BMESH_HOLES
1049 BLI_mempool_free(bm->looplistpool, ls);
1050#endif
1051 }
1052
1054}
1055
1057{
1058 while (e->l) {
1059 BM_face_kill(bm, e->l->f);
1060 }
1061
1064
1066}
1067
1069{
1070 while (v->e) {
1071 BM_edge_kill(bm, v->e);
1072 }
1073
1075}
1076
1077/********** private disk and radial cycle functions ********** */
1078
1083{
1084 BMLoop *l_first = l;
1085 int i = 0;
1086
1087 do {
1088 i++;
1089 } while ((l = l->next) != l_first);
1090
1091 return i;
1092}
1093
1095 BMFace *f,
1096 const int cd_loop_mdisp_offset,
1097 const bool use_loop_mdisp_flip)
1098{
1099 BMLoop *l_first = f->l_first;
1100
1101 /* track previous cycles radial state */
1102 BMEdge *e_prev = l_first->prev->e;
1103 BMLoop *l_prev_radial_next = l_first->prev->radial_next;
1104 BMLoop *l_prev_radial_prev = l_first->prev->radial_prev;
1105 bool is_prev_boundary = l_prev_radial_next == l_prev_radial_next->radial_next;
1106
1107 BMLoop *l_iter = l_first;
1108 do {
1109 BMEdge *e_iter = l_iter->e;
1110 BMLoop *l_iter_radial_next = l_iter->radial_next;
1111 BMLoop *l_iter_radial_prev = l_iter->radial_prev;
1112 bool is_iter_boundary = l_iter_radial_next == l_iter_radial_next->radial_next;
1113
1114#if 0
1115 bmesh_radial_loop_remove(e_iter, l_iter);
1116 bmesh_radial_loop_append(e_prev, l_iter);
1117#else
1118 /* inline loop reversal */
1119 if (is_prev_boundary) {
1120 /* boundary */
1121 l_iter->radial_next = l_iter;
1122 l_iter->radial_prev = l_iter;
1123 }
1124 else {
1125 /* non-boundary, replace radial links */
1126 l_iter->radial_next = l_prev_radial_next;
1127 l_iter->radial_prev = l_prev_radial_prev;
1128 l_prev_radial_next->radial_prev = l_iter;
1129 l_prev_radial_prev->radial_next = l_iter;
1130 }
1131
1132 if (e_iter->l == l_iter) {
1133 e_iter->l = l_iter->next;
1134 }
1135 l_iter->e = e_prev;
1136#endif
1137
1138 std::swap(l_iter->next, l_iter->prev);
1139
1140 if (cd_loop_mdisp_offset != -1) {
1141 MDisps *md = static_cast<MDisps *>(BM_ELEM_CD_GET_VOID_P(l_iter, cd_loop_mdisp_offset));
1142 BKE_mesh_mdisp_flip(md, use_loop_mdisp_flip);
1143 }
1144
1145 e_prev = e_iter;
1146 l_prev_radial_next = l_iter_radial_next;
1147 l_prev_radial_prev = l_iter_radial_prev;
1148 is_prev_boundary = is_iter_boundary;
1149
1150 /* step to next (now swapped) */
1151 } while ((l_iter = l_iter->prev) != l_first);
1152
1153#ifndef NDEBUG
1154 /* validate radial */
1155 int i;
1156 for (i = 0, l_iter = l_first; i < f->len; i++, l_iter = l_iter->next) {
1157 BM_CHECK_ELEMENT(l_iter);
1158 BM_CHECK_ELEMENT(l_iter->e);
1159 BM_CHECK_ELEMENT(l_iter->v);
1160 BM_CHECK_ELEMENT(l_iter->f);
1161 }
1162
1164#endif
1165
1166 /* Loop indices are no more valid! */
1168}
1169
1170static void bm_elements_systag_enable(void *veles, int tot, const char api_flag)
1171{
1172 BMHeader **eles = static_cast<BMHeader **>(veles);
1173 int i;
1174
1175 for (i = 0; i < tot; i++) {
1176 BM_ELEM_API_FLAG_ENABLE((BMElemF *)eles[i], api_flag);
1177 }
1178}
1179
1180static void bm_elements_systag_disable(void *veles, int tot, const char api_flag)
1181{
1182 BMHeader **eles = static_cast<BMHeader **>(veles);
1183 int i;
1184
1185 for (i = 0; i < tot; i++) {
1186 BM_ELEM_API_FLAG_DISABLE((BMElemF *)eles[i], api_flag);
1187 }
1188}
1189
1190static int bm_loop_systag_count_radial(BMLoop *l, const char api_flag)
1191{
1192 BMLoop *l_iter = l;
1193 int i = 0;
1194 do {
1195 i += BM_ELEM_API_FLAG_TEST(l_iter->f, api_flag) ? 1 : 0;
1196 } while ((l_iter = l_iter->radial_next) != l);
1197
1198 return i;
1199}
1200
1201static int UNUSED_FUNCTION(bm_vert_systag_count_disk)(BMVert *v, const char api_flag)
1202{
1203 BMEdge *e = v->e;
1204 int i = 0;
1205
1206 if (!e) {
1207 return 0;
1208 }
1209
1210 do {
1211 i += BM_ELEM_API_FLAG_TEST(e, api_flag) ? 1 : 0;
1212 } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
1213
1214 return i;
1215}
1216
1221static bool bm_vert_is_manifold_flagged(BMVert *v, const char api_flag)
1222{
1223 BMEdge *e = v->e;
1224
1225 if (!e) {
1226 return false;
1227 }
1228
1229 do {
1230 BMLoop *l = e->l;
1231
1232 if (!l) {
1233 return false;
1234 }
1235
1236 if (BM_edge_is_boundary(l->e)) {
1237 return false;
1238 }
1239
1240 do {
1241 if (!BM_ELEM_API_FLAG_TEST(l->f, api_flag)) {
1242 return false;
1243 }
1244 } while ((l = l->radial_next) != e->l);
1245 } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
1246
1247 return true;
1248}
1249
1250/* Mid-level Topology Manipulation Functions */
1251
1252BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del, BMFace **r_double)
1253{
1254 BMFace *f, *f_new;
1255#ifdef USE_BMESH_HOLES
1256 BMLoopList *lst;
1257 ListBaseT<BMLoopList> holes = {nullptr, nullptr};
1258#endif
1259 BMLoop *l_iter;
1260 BMLoop *l_first;
1261 BMVert *v1 = nullptr, *v2 = nullptr;
1262 int i;
1263 const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
1264 BMFace *f_existing;
1265 const bool had_active_face = (bm->act_face != nullptr);
1266
1267 /* Initialize the return value if provided. This ensures it will be nullptr if the join fails. */
1268 if (r_double) {
1269 *r_double = nullptr;
1270 }
1271
1272 if (!totface) [[unlikely]] {
1273 BMESH_ASSERT(0);
1274 return nullptr;
1275 }
1276
1277 if (totface == 1) {
1278 return faces[0];
1279 }
1280
1281 bm_elements_systag_enable(faces, totface, _FLAG_JF);
1282
1286
1287 for (i = 0; i < totface; i++) {
1288 f = faces[i];
1289 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1290 do {
1291 int rlen = bm_loop_systag_count_radial(l_iter, _FLAG_JF);
1292
1293 if (rlen > 2) {
1294 /* Input faces do not form a contiguous manifold region.
1295 * Clean up flags and fail. */
1296 bm_elements_systag_disable(faces, totface, _FLAG_JF);
1297 return nullptr;
1298 }
1299 if (rlen == 1) {
1300 edges.append(l_iter->e);
1301
1302 if (!v1) {
1303 v1 = l_iter->v;
1304 v2 = BM_edge_other_vert(l_iter->e, l_iter->v);
1305 }
1306 }
1307 else if (rlen == 2) {
1308 const bool d1 = bm_vert_is_manifold_flagged(l_iter->e->v1, _FLAG_JF);
1309 const bool d2 = bm_vert_is_manifold_flagged(l_iter->e->v2, _FLAG_JF);
1310
1311 if (!d1 && !d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e, _FLAG_JF)) {
1312 /* don't remove an edge it makes up the side of another face
1313 * else this will remove the face as well - campbell */
1314 if (!BM_edge_face_count_is_over(l_iter->e, 2)) {
1315 if (do_del) {
1316 deledges.append(l_iter->e);
1317 }
1319 }
1320 }
1321 else {
1322 if (d1 && !BM_ELEM_API_FLAG_TEST(l_iter->e->v1, _FLAG_JF)) {
1323 if (do_del) {
1324 delverts.append(l_iter->e->v1);
1325 }
1327 }
1328
1329 if (d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e->v2, _FLAG_JF)) {
1330 if (do_del) {
1331 delverts.append(l_iter->e->v2);
1332 }
1334 }
1335 }
1336 }
1337 } while ((l_iter = l_iter->next) != l_first);
1338
1339#ifdef USE_BMESH_HOLES
1340 for (lst = f->loops.first; lst; lst = lst->next) {
1341 if (lst == f->loops.first) {
1342 continue;
1343 }
1344
1345 BLI_remlink(&f->loops, lst);
1346 BLI_addtail(&holes, lst);
1347 }
1348#endif
1349 }
1350
1351 /* create region face */
1352 f_new = !edges.is_empty() ?
1354 bm, v1, v2, edges.data(), edges.size(), faces[0], BM_CREATE_NOP) :
1355 nullptr;
1356 if (f_new == nullptr) [[unlikely]] {
1357 /* Invalid boundary region to join faces
1358 * Clean up flags and fail */
1359 bm_elements_systag_disable(faces, totface, _FLAG_JF);
1360 return nullptr;
1361 }
1362
1363 /* If a new face was created, check whether it is a double of an existing face. */
1364 f_existing = BM_face_find_double(f_new);
1365 if (f_existing) {
1366
1367 /* Return the double to the calling function if that was requested. */
1368 if (r_double) {
1369 *r_double = f_existing;
1370 }
1371
1372 /* Otherwise, automatically reuse the existing face. */
1373 else {
1374 BM_face_kill(bm, f_new);
1375 f_new = f_existing;
1376 }
1377 }
1378
1379 bool reusing_face = (f_existing && r_double == nullptr);
1380
1381 /* If we are *not* reusing an existing face, we need to transfer data from the faces being joined
1382 * to the newly created joined face. */
1383 if (reusing_face == false) [[likely]] {
1384
1385 /* copy over loop data */
1386 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1387 do {
1388 BMLoop *l2 = l_iter->radial_next;
1389
1390 do {
1391 if (BM_ELEM_API_FLAG_TEST(l2->f, _FLAG_JF)) {
1392 break;
1393 }
1394 l2 = l2->radial_next;
1395 } while (l2 != l_iter);
1396
1397 if (l2 != l_iter) {
1398 /* loops share an edge, shared vert depends on winding */
1399 if (l2->v != l_iter->v) {
1400 l2 = l2->next;
1401 }
1402 BLI_assert(l_iter->v == l2->v);
1403
1404 BM_elem_attrs_copy(bm, l2, l_iter);
1405 }
1406 } while ((l_iter = l_iter->next) != l_first);
1407
1408#ifdef USE_BMESH_HOLES
1409 /* add holes */
1410 BLI_movelisttolist(&f_new->loops, &holes);
1411
1412 /* update loop face pointer */
1413 for (lst = f_new->loops.first; lst; lst = lst->next) {
1414 l_iter = l_first = lst->first;
1415 do {
1416 l_iter->f = f_new;
1417 } while ((l_iter = l_iter->next) != l_first);
1418 }
1419#endif
1420
1421 /* handle multi-res data */
1422 if (cd_loop_mdisp_offset != -1) {
1423 float f_center[3];
1425
1426 BM_face_calc_center_median(f_new, f_center);
1427 for (i = 0; i < totface; i++) {
1428 BM_face_calc_center_median(faces[i], faces_center[i]);
1429 }
1430
1431 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1432 do {
1433 for (i = 0; i < totface; i++) {
1435 bm, l_iter, faces[i], f_center, faces_center[i], cd_loop_mdisp_offset);
1436 }
1437 } while ((l_iter = l_iter->next) != l_first);
1438 }
1439 }
1440
1441 /* Clean up the internal flags. */
1442 bm_elements_systag_disable(faces, totface, _FLAG_JF);
1444
1445 if (do_del) {
1446 /* If `do_del`, delete all the edges and verts that were identified while walking the mesh. */
1447 for (BMEdge *edge : deledges) {
1448 BM_edge_kill(bm, edge);
1449 }
1450
1451 for (BMVert *vert : delverts) {
1452 BM_vert_kill(bm, vert);
1453 }
1454 }
1455 else {
1456 /* Otherwise, delete only the faces that were merged
1457 * (do not leave the mesh with both the old and new faces). */
1458 for (i = 0; i < totface; i++) {
1459 BM_face_kill(bm, faces[i]);
1460 }
1461 }
1462
1463 /* If the mesh started with an active face, but no longer has one, then the active face was one
1464 * of the faces that was joined then deleted. Set the active face to preserve it. */
1465 if (had_active_face && bm->act_face == nullptr) {
1466 bm->act_face = f_new;
1467 }
1468
1469 BM_CHECK_ELEMENT(f_new);
1470 return f_new;
1471}
1472
1474{
1475 BMFace *f;
1476#ifdef USE_BMESH_HOLES
1477 BMLoopList *lst;
1478#endif
1479
1481
1482#ifdef USE_BMESH_HOLES
1483 lst = BLI_mempool_calloc(bm->looplistpool);
1484 BLI_addtail(&f->loops, lst);
1485#endif
1486
1487#ifdef USE_BMESH_HOLES
1488 f->totbounds = 1;
1489#endif
1490
1491 BM_elem_attrs_copy(bm, f_example, f);
1492
1493 return f;
1494}
1495
1497 BMFace *f,
1498 BMLoop *l_v1,
1499 BMLoop *l_v2,
1500 BMLoop **r_l,
1501#ifdef USE_BMESH_HOLES
1502 ListBaseT<BMLoopList> *holes,
1503#endif
1504 BMEdge *e_example,
1505 const bool no_double)
1506{
1507#ifdef USE_BMESH_HOLES
1508 BMLoopList *lst, *lst2;
1509#else
1510 int first_loop_f1;
1511#endif
1512
1513 BMFace *f2;
1514 BMLoop *l_iter, *l_first;
1515 BMLoop *l_f1 = nullptr, *l_f2 = nullptr;
1516 BMEdge *e;
1517 BMVert *v1 = l_v1->v, *v2 = l_v2->v;
1518 int f1len, f2len;
1519
1520 BLI_assert(f == l_v1->f && f == l_v2->f);
1521
1522 /* allocate new edge between v1 and v2 */
1523 e = BM_edge_create(bm, v1, v2, e_example, no_double ? BM_CREATE_NO_DOUBLE : BM_CREATE_NOP);
1524
1525 f2 = bm_face_create__sfme(bm, f);
1526 l_f1 = bm_loop_create(bm, v2, e, f, l_v2, eBMCreateFlag(0));
1527 l_f2 = bm_loop_create(bm, v1, e, f2, l_v1, eBMCreateFlag(0));
1528
1529 l_f1->prev = l_v2->prev;
1530 l_f2->prev = l_v1->prev;
1531 l_v2->prev->next = l_f1;
1532 l_v1->prev->next = l_f2;
1533
1534 l_f1->next = l_v1;
1535 l_f2->next = l_v2;
1536 l_v1->prev = l_f1;
1537 l_v2->prev = l_f2;
1538
1539#ifdef USE_BMESH_HOLES
1540 lst = f->loops.first;
1541 lst2 = f2->loops.first;
1542
1543 lst2->first = lst2->last = l_f2;
1544 lst->first = lst->last = l_f1;
1545#else
1546 /* find which of the faces the original first loop is in */
1547 l_iter = l_first = l_f1;
1548 first_loop_f1 = 0;
1549 do {
1550 if (l_iter == f->l_first) {
1551 first_loop_f1 = 1;
1552 }
1553 } while ((l_iter = l_iter->next) != l_first);
1554
1555 if (first_loop_f1) {
1556 /* Original first loop was in f1, find a suitable first loop for f2
1557 * which is as similar as possible to f1. the order matters for tools
1558 * such as dupli-faces. */
1559 if (f->l_first->prev == l_f1) {
1560 f2->l_first = l_f2->prev;
1561 }
1562 else if (f->l_first->next == l_f1) {
1563 f2->l_first = l_f2->next;
1564 }
1565 else {
1566 f2->l_first = l_f2;
1567 }
1568 }
1569 else {
1570 /* original first loop was in f2, further do same as above */
1571 f2->l_first = f->l_first;
1572
1573 if (f->l_first->prev == l_f2) {
1574 f->l_first = l_f1->prev;
1575 }
1576 else if (f->l_first->next == l_f2) {
1577 f->l_first = l_f1->next;
1578 }
1579 else {
1580 f->l_first = l_f1;
1581 }
1582 }
1583#endif
1584
1585 /* validate both loop */
1586 /* I don't know how many loops are supposed to be in each face at this point! FIXME */
1587
1588 /* go through all of f2's loops and make sure they point to it properly */
1589 l_iter = l_first = BM_FACE_FIRST_LOOP(f2);
1590 f2len = 0;
1591 do {
1592 l_iter->f = f2;
1593 f2len++;
1594 } while ((l_iter = l_iter->next) != l_first);
1595
1596 /* link up the new loops into the new edges radial */
1599
1600 f2->len = f2len;
1601
1602 f1len = 0;
1603 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1604 do {
1605 f1len++;
1606 } while ((l_iter = l_iter->next) != l_first);
1607
1608 f->len = f1len;
1609
1610 if (r_l) {
1611 *r_l = l_f2;
1612 }
1613
1614#ifdef USE_BMESH_HOLES
1615 if (holes) {
1616 BLI_movelisttolist(&f2->loops, holes);
1617 }
1618 else {
1619 /* this code is not significant until holes actually work */
1620 // printf("WARNING: call to split face euler without holes argument; holes will be tossed.\n");
1621 for (lst = f->loops.last; lst != f->loops.first; lst = lst2) {
1622 lst2 = lst->prev;
1623 BLI_mempool_free(bm->looplistpool, lst);
1624 }
1625 }
1626#endif
1627
1630 BM_CHECK_ELEMENT(f2);
1631
1632 return f2;
1633}
1634
1636{
1637 BMLoop *l_next;
1638 BMEdge *e_new;
1639 BMVert *v_new, *v_old;
1640#ifndef NDEBUG
1641 int valence1, valence2;
1642 bool edok;
1643 int i;
1644#endif
1645
1646 BLI_assert(BM_vert_in_edge(e, tv) != false);
1647
1648 v_old = BM_edge_other_vert(e, tv);
1649
1650#ifndef NDEBUG
1651 valence1 = bmesh_disk_count(v_old);
1652 valence2 = bmesh_disk_count(tv);
1653#endif
1654
1655 /* order of 'e_new' verts should match 'e'
1656 * (so extruded faces don't flip) */
1657 v_new = BM_vert_create(bm, tv->co, tv, BM_CREATE_NOP);
1658 e_new = BM_edge_create(bm, tv, v_new, e, BM_CREATE_NOP);
1659
1660 bmesh_disk_edge_remove(e_new, tv);
1661 bmesh_disk_edge_remove(e_new, v_new);
1662
1663 bmesh_disk_vert_replace(e, v_new, tv);
1664
1665 /* add e_new to v_new's disk cycle */
1666 bmesh_disk_edge_append(e_new, v_new);
1667
1668 /* add e_new to tv's disk cycle */
1669 bmesh_disk_edge_append(e_new, tv);
1670
1671#ifndef NDEBUG
1672 /* verify disk cycles */
1673 edok = bmesh_disk_validate(valence1, v_old->e, v_old);
1674 BMESH_ASSERT(edok != false);
1675 edok = bmesh_disk_validate(valence2, tv->e, tv);
1676 BMESH_ASSERT(edok != false);
1677 edok = bmesh_disk_validate(2, v_new->e, v_new);
1678 BMESH_ASSERT(edok != false);
1679#endif
1680
1681 /* Split the radial cycle if present */
1682 l_next = e->l;
1683 e->l = nullptr;
1684 if (l_next) {
1685 BMLoop *l_new, *l;
1686#ifndef NDEBUG
1687 int radlen = bmesh_radial_length(l_next);
1688#endif
1689 bool is_first = true;
1690
1691 /* Take the next loop. Remove it from radial. Split it. Append to appropriate radials */
1692 while (l_next) {
1693 l = l_next;
1694 l->f->len++;
1695 l_next = l_next != l_next->radial_next ? l_next->radial_next : nullptr;
1697
1698 l_new = bm_loop_create(bm, nullptr, nullptr, l->f, l, eBMCreateFlag(0));
1699 l_new->prev = l;
1700 l_new->next = l->next;
1701 l_new->prev->next = l_new;
1702 l_new->next->prev = l_new;
1703 l_new->v = v_new;
1704
1705 /* assign the correct edge to the correct loop */
1706 if (BM_verts_in_edge(l_new->v, l_new->next->v, e)) {
1707 l_new->e = e;
1708 l->e = e_new;
1709
1710 /* append l into e_new's rad cycle */
1711 if (is_first) {
1712 is_first = false;
1713 l->radial_next = l->radial_prev = nullptr;
1714 }
1715
1716 bmesh_radial_loop_append(l_new->e, l_new);
1718 }
1719 else if (BM_verts_in_edge(l_new->v, l_new->next->v, e_new)) {
1720 l_new->e = e_new;
1721 l->e = e;
1722
1723 /* append l into e_new's rad cycle */
1724 if (is_first) {
1725 is_first = false;
1726 l->radial_next = l->radial_prev = nullptr;
1727 }
1728
1729 bmesh_radial_loop_append(l_new->e, l_new);
1731 }
1732 }
1733
1734#ifndef NDEBUG
1735 /* verify length of radial cycle */
1736 edok = bmesh_radial_validate(radlen, e->l);
1737 BMESH_ASSERT(edok != false);
1738 edok = bmesh_radial_validate(radlen, e_new->l);
1739 BMESH_ASSERT(edok != false);
1740
1741 /* verify loop->v and loop->next->v pointers for e */
1742 for (i = 0, l = e->l; i < radlen; i++, l = l->radial_next) {
1743 BMESH_ASSERT(l->e == e);
1744 // BMESH_ASSERT(l->radial_next == l);
1745 BMESH_ASSERT(!(l->prev->e != e_new && l->next->e != e_new));
1746
1747 edok = BM_verts_in_edge(l->v, l->next->v, e);
1748 BMESH_ASSERT(edok != false);
1749 BMESH_ASSERT(l->v != l->next->v);
1750 BMESH_ASSERT(l->e != l->next->e);
1751
1752 /* verify loop cycle for kloop->f */
1757 }
1758 /* verify loop->v and loop->next->v pointers for e_new */
1759 for (i = 0, l = e_new->l; i < radlen; i++, l = l->radial_next) {
1760 BMESH_ASSERT(l->e == e_new);
1761 // BMESH_ASSERT(l->radial_next == l);
1762 BMESH_ASSERT(!(l->prev->e != e && l->next->e != e));
1763 edok = BM_verts_in_edge(l->v, l->next->v, e_new);
1764 BMESH_ASSERT(edok != false);
1765 BMESH_ASSERT(l->v != l->next->v);
1766 BMESH_ASSERT(l->e != l->next->e);
1767
1772 }
1773#endif
1774 }
1775
1776 BM_CHECK_ELEMENT(e_new);
1777 BM_CHECK_ELEMENT(v_new);
1778 BM_CHECK_ELEMENT(v_old);
1780 BM_CHECK_ELEMENT(tv);
1781
1782 if (r_e) {
1783 *r_e = e_new;
1784 }
1785 return v_new;
1786}
1787
1789 BMEdge *e_kill,
1790 BMVert *v_kill,
1791 const bool do_del,
1792 const bool check_edge_exists,
1793 const bool kill_degenerate_faces,
1794 const bool kill_duplicate_faces)
1795{
1796 BMEdge *e_old;
1797 BMVert *v_old, *v_target;
1798 BMLoop *l_kill;
1799#ifndef NDEBUG
1800 int radlen, i;
1801 bool edok;
1802#endif
1803
1804 BLI_assert(BM_vert_in_edge(e_kill, v_kill));
1805
1806 if (BM_vert_in_edge(e_kill, v_kill) == 0) {
1807 return nullptr;
1808 }
1809
1810 if (bmesh_disk_count_at_most(v_kill, 3) == 2) {
1811#ifndef NDEBUG
1812 int valence1, valence2;
1813 BMLoop *l;
1814#endif
1815
1816 e_old = bmesh_disk_edge_next(e_kill, v_kill);
1817 v_target = BM_edge_other_vert(e_kill, v_kill);
1818 v_old = BM_edge_other_vert(e_old, v_kill);
1819
1820 /* check for double edges */
1821 if (BM_verts_in_edge(v_kill, v_target, e_old)) {
1822 return nullptr;
1823 }
1824
1825 BMEdge *e_splice;
1826 BLI_SMALLSTACK_DECLARE(faces_degenerate, BMFace *);
1827 BMLoop *l_kill_next;
1828
1829 /* Candidates for being duplicate. */
1830 BLI_SMALLSTACK_DECLARE(faces_duplicate_candidate, BMFace *);
1831
1832#ifndef NDEBUG
1833 /* For verification later, count valence of 'v_old' and 'v_target' */
1834 valence1 = bmesh_disk_count(v_old);
1835 valence2 = bmesh_disk_count(v_target);
1836#endif
1837
1838 if (check_edge_exists) {
1839 e_splice = BM_edge_exists(v_target, v_old);
1840 }
1841
1842 bmesh_disk_vert_replace(e_old, v_target, v_kill);
1843
1844 /* remove e_kill from 'v_target's disk cycle */
1845 bmesh_disk_edge_remove(e_kill, v_target);
1846
1847#ifndef NDEBUG
1848 /* deal with radial cycle of e_kill */
1849 radlen = bmesh_radial_length(e_kill->l);
1850#endif
1851 if (e_kill->l) {
1852
1853 /* fix the neighboring loops of all loops in e_kill's radial cycle */
1854 l_kill = e_kill->l;
1855 do {
1856 /* relink loops and fix vertex pointer */
1857 if (l_kill->next->v == v_kill) {
1858 l_kill->next->v = v_target;
1859 }
1860
1861 l_kill->next->prev = l_kill->prev;
1862 l_kill->prev->next = l_kill->next;
1863 if (BM_FACE_FIRST_LOOP(l_kill->f) == l_kill) {
1864 BM_FACE_FIRST_LOOP(l_kill->f) = l_kill->next;
1865 }
1866
1867 /* fix len attribute of face */
1868 l_kill->f->len--;
1869 if (kill_degenerate_faces && (l_kill->f->len < 3)) {
1870 BLI_SMALLSTACK_PUSH(faces_degenerate, l_kill->f);
1871 }
1872 else {
1873 /* The duplicate test isn't reliable at this point as `e_splice` might be set,
1874 * so the duplicate test needs to run once the edge has been spliced. */
1875 if (kill_duplicate_faces) {
1876 BLI_SMALLSTACK_PUSH(faces_duplicate_candidate, l_kill->f);
1877 }
1878 }
1879 l_kill_next = l_kill->radial_next;
1880
1881 bm_kill_only_loop(bm, l_kill);
1882
1883 } while ((l_kill = l_kill_next) != e_kill->l);
1884/* `e_kill->l` is invalid but the edge is freed next. */
1885#ifndef NDEBUG
1886 /* Validate radial cycle of e_old */
1887 edok = bmesh_radial_validate(radlen, e_old->l);
1888 BMESH_ASSERT(edok != false);
1889#endif
1890 }
1891 /* deallocate edge */
1892 bm_kill_only_edge(bm, e_kill);
1893
1894 /* deallocate vertex */
1895 if (do_del) {
1896 bm_kill_only_vert(bm, v_kill);
1897 }
1898 else {
1899 v_kill->e = nullptr;
1900 }
1901
1902#ifndef NDEBUG
1903 /* Validate disk cycle lengths of 'v_old', 'v_target' are unchanged */
1904 edok = bmesh_disk_validate(valence1, v_old->e, v_old);
1905 BMESH_ASSERT(edok != false);
1906 edok = bmesh_disk_validate(valence2, v_target->e, v_target);
1907 BMESH_ASSERT(edok != false);
1908
1909 /* Validate loop cycle of all faces attached to 'e_old' */
1910 for (i = 0, l = e_old->l; i < radlen; i++, l = l->radial_next) {
1911 BMESH_ASSERT(l->e == e_old);
1912 edok = BM_verts_in_edge(l->v, l->next->v, e_old);
1913 BMESH_ASSERT(edok != false);
1914 edok = bmesh_loop_validate(l->f);
1915 BMESH_ASSERT(edok != false);
1916
1921 }
1922#endif
1923 if (check_edge_exists) {
1924 if (e_splice) {
1925 /* removes e_splice */
1926 BM_edge_splice(bm, e_old, e_splice);
1927 }
1928 }
1929
1930 if (kill_degenerate_faces) {
1931 BMFace *f_kill;
1932 while ((f_kill = static_cast<BMFace *>(BLI_SMALLSTACK_POP(faces_degenerate)))) {
1933 BM_face_kill(bm, f_kill);
1934 }
1935 }
1936
1937 if (kill_duplicate_faces) {
1938 BMFace *f_kill;
1939 while ((f_kill = static_cast<BMFace *>(BLI_SMALLSTACK_POP(faces_duplicate_candidate)))) {
1940 if (BM_face_find_double(f_kill)) {
1941 BM_face_kill(bm, f_kill);
1942 }
1943 }
1944 }
1945
1946 BM_CHECK_ELEMENT(v_old);
1947 BM_CHECK_ELEMENT(v_target);
1948 BM_CHECK_ELEMENT(e_old);
1949
1950 return e_old;
1951 }
1952 return nullptr;
1953}
1954
1956 BMEdge *e_kill,
1957 BMVert *v_kill,
1958 const bool do_del,
1959 const bool check_edge_exists,
1960 const bool kill_degenerate_faces)
1961{
1962 BLI_SMALLSTACK_DECLARE(faces_degenerate, BMFace *);
1963 BMVert *v_target = BM_edge_other_vert(e_kill, v_kill);
1964
1965 BLI_assert(BM_vert_in_edge(e_kill, v_kill));
1966
1967 if (e_kill->l) {
1968 BMLoop *l_kill, *l_first, *l_kill_next;
1969 l_kill = l_first = e_kill->l;
1970 do {
1971 /* relink loops and fix vertex pointer */
1972 if (l_kill->next->v == v_kill) {
1973 l_kill->next->v = v_target;
1974 }
1975
1976 l_kill->next->prev = l_kill->prev;
1977 l_kill->prev->next = l_kill->next;
1978 if (BM_FACE_FIRST_LOOP(l_kill->f) == l_kill) {
1979 BM_FACE_FIRST_LOOP(l_kill->f) = l_kill->next;
1980 }
1981
1982 /* fix len attribute of face */
1983 l_kill->f->len--;
1984 if (kill_degenerate_faces) {
1985 if (l_kill->f->len < 3) {
1986 BLI_SMALLSTACK_PUSH(faces_degenerate, l_kill->f);
1987 }
1988 }
1989 l_kill_next = l_kill->radial_next;
1990
1991 bm_kill_only_loop(bm, l_kill);
1992
1993 } while ((l_kill = l_kill_next) != l_first);
1994
1995 e_kill->l = nullptr;
1996 }
1997
1998 BM_edge_kill(bm, e_kill);
1999 BM_CHECK_ELEMENT(v_kill);
2000 BM_CHECK_ELEMENT(v_target);
2001
2002 if (v_target->e && v_kill->e) {
2003 /* Inline `BM_vert_splice(bm, v_target, v_kill)`. */
2004 BMEdge *e;
2005 while ((e = v_kill->e)) {
2006 BMEdge *e_target;
2007
2008 if (check_edge_exists) {
2009 e_target = BM_edge_exists(v_target, BM_edge_other_vert(e, v_kill));
2010 }
2011
2012 bmesh_edge_vert_swap(e, v_target, v_kill);
2013 BLI_assert(e->v1 != e->v2);
2014
2015 if (check_edge_exists) {
2016 if (e_target) {
2017 BM_edge_splice(bm, e_target, e);
2018 }
2019 }
2020 }
2021 }
2022
2023 if (kill_degenerate_faces) {
2024 BMFace *f_kill;
2025 while ((f_kill = static_cast<BMFace *>(BLI_SMALLSTACK_POP(faces_degenerate)))) {
2026 BM_face_kill(bm, f_kill);
2027 }
2028 }
2029
2030 if (do_del) {
2031 BLI_assert(v_kill->e == nullptr);
2032 bm_kill_only_vert(bm, v_kill);
2033 }
2034
2035 return v_target;
2036}
2037
2039{
2040 BMLoop *l_iter, *l_f1 = nullptr, *l_f2 = nullptr;
2041 int newlen = 0, i, f1len = 0, f2len = 0;
2042 bool edok;
2043 /* can't join a face to itself */
2044 if (f1 == f2) {
2045 return nullptr;
2046 }
2047
2048 /* validate that edge is 2-manifold edge */
2049 if (!BM_edge_is_manifold(e)) {
2050 return nullptr;
2051 }
2052
2053 /* verify that e is in both f1 and f2 */
2054 f1len = f1->len;
2055 f2len = f2->len;
2056
2057 if (!((l_f1 = BM_face_edge_share_loop(f1, e)) && (l_f2 = BM_face_edge_share_loop(f2, e)))) {
2058 return nullptr;
2059 }
2060
2061 /* validate direction of f2's loop cycle is compatible */
2062 if (l_f1->v == l_f2->v) {
2063 return nullptr;
2064 }
2065
2066 /* validate that for each face, each vertex has another edge in its disk cycle that is
2067 * not e, and not shared. */
2068 if (BM_edge_in_face(l_f1->next->e, f2) || BM_edge_in_face(l_f1->prev->e, f2) ||
2069 BM_edge_in_face(l_f2->next->e, f1) || BM_edge_in_face(l_f2->prev->e, f1))
2070 {
2071 return nullptr;
2072 }
2073
2074 /* validate only one shared edge */
2075 if (BM_face_share_edge_count(f1, f2) > 1) {
2076 return nullptr;
2077 }
2078
2079 /* validate no internal join */
2080 {
2081 bool is_dupe = false;
2082
2083 /* TODO: skip clearing once this is ensured. */
2084 for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f2); i < f2len; i++, l_iter = l_iter->next) {
2086 }
2087
2088 for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < f1len; i++, l_iter = l_iter->next) {
2089 BM_elem_flag_set(l_iter->v, BM_ELEM_INTERNAL_TAG, l_iter != l_f1);
2090 }
2091 for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f2); i < f2len; i++, l_iter = l_iter->next) {
2092 if (l_iter != l_f2) {
2093 /* as soon as a duplicate is found, bail out */
2094 if (BM_elem_flag_test(l_iter->v, BM_ELEM_INTERNAL_TAG)) {
2095 is_dupe = true;
2096 break;
2097 }
2098 }
2099 }
2100 /* Cleanup tags. */
2101 for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < f1len; i++, l_iter = l_iter->next) {
2103 }
2104 if (is_dupe) {
2105 return nullptr;
2106 }
2107 }
2108
2109 /* join the two loop */
2110 l_f1->prev->next = l_f2->next;
2111 l_f2->next->prev = l_f1->prev;
2112
2113 l_f1->next->prev = l_f2->prev;
2114 l_f2->prev->next = l_f1->next;
2115
2116 /* If `l_f1` was base-loop, make `l_f1->next` the base. */
2117 if (BM_FACE_FIRST_LOOP(f1) == l_f1) {
2118 BM_FACE_FIRST_LOOP(f1) = l_f1->next;
2119 }
2120
2121 /* increase length of f1 */
2122 f1->len += (f2->len - 2);
2123
2124 /* make sure each loop points to the proper face */
2125 newlen = f1->len;
2126 for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < newlen; i++, l_iter = l_iter->next) {
2127 l_iter->f = f1;
2128 }
2129
2130 /* remove edge from the disk cycle of its two vertices */
2131 bmesh_disk_edge_remove(l_f1->e, l_f1->e->v1);
2132 bmesh_disk_edge_remove(l_f1->e, l_f1->e->v2);
2133
2134 /* deallocate edge and its two loops as well as f2 */
2135 if (bm->etoolflagpool) {
2136 BLI_mempool_free(bm->etoolflagpool, (reinterpret_cast<BMEdge_OFlag *>(l_f1->e))->oflags);
2137 }
2138 BLI_mempool_free(bm->epool, l_f1->e);
2139 bm->totedge--;
2140 BLI_mempool_free(bm->lpool, l_f1);
2141 bm->totloop--;
2142 BLI_mempool_free(bm->lpool, l_f2);
2143 bm->totloop--;
2144 if (bm->ftoolflagpool) {
2145 BLI_mempool_free(bm->ftoolflagpool, (reinterpret_cast<BMFace_OFlag *>(f2))->oflags);
2146 }
2148 bm->totface--;
2149 /* account for both above */
2151
2152 BM_CHECK_ELEMENT(f1);
2153
2154 /* validate the new loop cycle */
2155 edok = bmesh_loop_validate(f1);
2156 BMESH_ASSERT(edok != false);
2157
2158 return f1;
2159}
2160
2162{
2163 bool is_double = false;
2164
2165 BLI_assert(BM_edge_exists(v_a, v_b) == nullptr);
2166
2167 if (v_a->e && v_b->e) {
2168 BMEdge *e, *e_first;
2169
2170#define VERT_VISIT _FLAG_WALK
2171
2172 /* tag 'v_a' */
2173 e = e_first = v_a->e;
2174 do {
2175 BMVert *v_other = BM_edge_other_vert(e, v_a);
2178 } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != e_first);
2179
2180 /* check 'v_b' connects to 'v_a' edges */
2181 e = e_first = v_b->e;
2182 do {
2183 BMVert *v_other = BM_edge_other_vert(e, v_b);
2184 if (BM_ELEM_API_FLAG_TEST(v_other, VERT_VISIT)) {
2185 is_double = true;
2186 break;
2187 }
2188 } while ((e = BM_DISK_EDGE_NEXT(e, v_b)) != e_first);
2189
2190 /* cleanup */
2191 e = e_first = v_a->e;
2192 do {
2193 BMVert *v_other = BM_edge_other_vert(e, v_a);
2196 } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != e_first);
2197
2198#undef VERT_VISIT
2199 }
2200
2201 return is_double;
2202}
2203
2205{
2206 if (ELEM(nullptr, v_a->e, v_b->e)) {
2207 return false;
2208 }
2209
2210 BMVert *v_pair[2] = {v_a, v_b};
2212
2213 for (const int side : IndexRange(2)) {
2214 BMEdge *e_iter = v_pair[side]->e;
2215 do {
2216 if (BMLoop *l = e_iter->l) {
2217 do {
2218 if (l->v == v_pair[side]) {
2219 loops_pair[side].append(l);
2220 }
2221 } while ((l = l->radial_next) != e_iter->l);
2222 }
2223 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_pair[side])) != v_pair[side]->e);
2224 if (loops_pair[side].is_empty()) {
2225 return false;
2226 }
2227 }
2228
2229 for (const int side : IndexRange(2)) {
2230 if (loops_pair[side].size() > 1) {
2231 std::ranges::sort(loops_pair[side],
2232 [](BMLoop *a, BMLoop *b) { return a->f->len < b->f->len; });
2233 }
2234 }
2235
2236 int a_beg = 0;
2237 int b_beg = 0;
2238 while (a_beg < loops_pair[0].size() && b_beg < loops_pair[1].size()) {
2239 const int a_len = loops_pair[0][a_beg]->f->len;
2240 const int b_len = loops_pair[1][b_beg]->f->len;
2241
2242 if (a_len < b_len) {
2243 a_beg++;
2244 continue;
2245 }
2246 if (a_len > b_len) {
2247 b_beg++;
2248 continue;
2249 }
2250
2251 /* `a_len == b_len`: find the range of elements with this length in both lists. */
2252 const int f_len = a_len;
2253 int a_end = a_beg + 1;
2254 int b_end = b_beg + 1;
2255 while (a_end < loops_pair[0].size() && loops_pair[0][a_end]->f->len == f_len) {
2256 a_end++;
2257 }
2258 while (b_end < loops_pair[1].size() && loops_pair[1][b_end]->f->len == f_len) {
2259 b_end++;
2260 }
2261
2262 /* Compare all pairs within this matching length range. */
2263 for (int a_index = a_beg; a_index < a_end; a_index++) {
2264 BMLoop *l_a = loops_pair[0][a_index];
2265 for (int b_index = b_beg; b_index < b_end; b_index++) {
2266 BMLoop *l_b = loops_pair[1][b_index];
2267 if ((l_a->next->v == l_b->next->v) && (l_a->prev->v == l_b->prev->v)) {
2269 l_a->next->next, l_a->prev->prev, l_b->next->next, l_b->prev->prev))
2270 {
2271 return true;
2272 }
2273 }
2274 else if ((l_a->next->v == l_b->prev->v) && (l_a->prev->v == l_b->next->v)) {
2276 l_a->next->next, l_a->prev->prev, l_b->prev->prev, l_b->next->next))
2277 {
2278 return true;
2279 }
2280 }
2281 }
2282 }
2283
2284 a_beg = a_end;
2285 b_beg = b_end;
2286 }
2287 return false;
2288}
2289
2291{
2292 /* Caller must ensure. */
2293 BLI_assert(BM_vert_is_edge_pair(v_collapse));
2294
2295 BMLoop *l_collapse_a_first = v_collapse->e->l;
2296 if (l_collapse_a_first == nullptr) {
2297 return false;
2298 }
2299
2300 BMEdge *e_a = v_collapse->e;
2301 BMEdge *e_b = (l_collapse_a_first->v == v_collapse) ? l_collapse_a_first->prev->e :
2302 l_collapse_a_first->next->e;
2303 BLI_assert(e_a != e_b && BM_vert_in_edge(e_b, v_collapse));
2304 UNUSED_VARS_NDEBUG(e_a);
2305 BMVert *v_a = BM_edge_other_vert(v_collapse->e, v_collapse);
2306 BMVert *v_b = BM_edge_other_vert(e_b, v_collapse);
2307
2308 BMEdge *e_exists = BM_edge_exists(v_a, v_b);
2309 if (e_exists == nullptr || e_exists->l == nullptr) {
2310 return false;
2311 }
2312
2313 BMLoop *l_collapse_a_iter = l_collapse_a_first;
2314 do {
2315 if (l_collapse_a_iter->f->len <= 3) {
2316 continue;
2317 }
2318 BMLoop *l_collapse = nullptr;
2319 if (l_collapse_a_iter->v == v_collapse) {
2320 l_collapse = l_collapse_a_iter;
2321 }
2322 else if (l_collapse_a_iter->next->v == v_collapse) {
2323 l_collapse = l_collapse_a_iter->next;
2324 }
2325 else if (l_collapse_a_iter->prev->v == v_collapse) {
2326 l_collapse = l_collapse_a_iter->prev;
2327 }
2328 BLI_assert(l_collapse && l_collapse->v == v_collapse);
2329
2330 /* Check if `l_collapse_a_iter->f` could collapse into an existing face
2331 * attached to `e_exists`. */
2332 BMLoop *l_exists_iter = e_exists->l;
2333 do {
2334 if (l_collapse_a_iter->f->len - 1 != l_exists_iter->f->len) {
2335 continue;
2336 }
2337 /* Detect if these could be duplicates. */
2338 BMLoop *l_collapse_beg = l_collapse->next;
2339 BMLoop *l_collapse_end = l_collapse->prev;
2340
2341 const bool swap_winding = l_collapse_beg->v == l_exists_iter->v;
2342 BMLoop *l_exists_beg;
2343 BMLoop *l_exists_end;
2344 if (swap_winding) {
2345 l_exists_beg = l_exists_iter;
2346 l_exists_end = l_exists_iter->next;
2347 }
2348 else {
2349 l_exists_beg = l_exists_iter->next;
2350 l_exists_end = l_exists_iter;
2351 }
2352
2353 /* Walk around loops of both faces checking the vertices match. */
2354 BLI_assert(l_collapse_beg->v == l_exists_beg->v);
2355 BLI_assert(l_collapse_end->v == l_exists_end->v);
2356 if (swap_winding) {
2357 BLI_assert(l_collapse_beg->v == l_exists_end->prev->v);
2358 BLI_assert(l_collapse_end->v == l_exists_beg->next->v);
2360 l_collapse_end->prev,
2361 l_exists_beg->prev,
2362 l_exists_end->next))
2363 {
2364 return true;
2365 }
2366 }
2367 else {
2368 BLI_assert(l_collapse_beg->v == l_exists_end->next->v);
2369 BLI_assert(l_collapse_end->v == l_exists_beg->prev->v);
2371 l_collapse_end->prev,
2372 l_exists_beg->next,
2373 l_exists_end->prev))
2374 {
2375 return true;
2376 }
2377 }
2378 } while ((l_exists_iter = l_exists_iter->radial_next) != e_exists->l);
2379 } while ((l_collapse_a_iter = l_collapse_a_iter->radial_next) != l_collapse_a_first);
2380
2381 return false;
2382}
2383
2385{
2386 BLI_assert(l_a->f == l_b->f);
2387 BLI_assert(l_a != l_b);
2388
2389 /* Check if a face exists on either side. */
2390 const int side_b_len = (l_a->f->len - f_len) + 2;
2391
2392 return (BM_face_exists_subset_from_face(l_a, l_b, f_len) != nullptr) ||
2393 (BM_face_exists_subset_from_face(l_b, l_a, side_b_len) != nullptr);
2394}
2395
2396bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
2397{
2398 BMEdge *e;
2399
2400 /* verts already spliced */
2401 if (v_src == v_dst) {
2402 return false;
2403 }
2404
2405 BLI_assert(BM_vert_pair_share_face_check(v_src, v_dst) == false);
2406
2407 /* move all the edges from 'v_src' disk to 'v_dst' */
2408 while ((e = v_src->e)) {
2409 bmesh_edge_vert_swap(e, v_dst, v_src);
2410 BLI_assert(e->v1 != e->v2);
2411 }
2412
2413 BM_CHECK_ELEMENT(v_src);
2414 BM_CHECK_ELEMENT(v_dst);
2415
2416 /* 'v_src' is unused now, and can be killed */
2417 BM_vert_kill(bm, v_src);
2418
2419 return true;
2420}
2421
2422/* -------------------------------------------------------------------- */
2425
2426/* BM_edge_face_count(e) >= 1 */
2428{
2429 return (e->l && e->l->radial_next != e->l);
2430}
2431
2433 BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len, const bool copy_select)
2434{
2435 int v_edges_num = 0;
2436
2437 /* Detailed notes on array use since this is stack memory, we have to be careful */
2438
2439 /* newly created vertices, only use when 'r_vout' is set
2440 * (total size will be number of fans) */
2441 BLI_SMALLSTACK_DECLARE(verts_new, BMVert *);
2442 /* fill with edges from the face-fan, clearing on completion
2443 * (total size will be max fan edge count) */
2445 /* temp store edges to walk over when filling 'edges',
2446 * (total size will be max radial edges of any edge) */
2447 BLI_SMALLSTACK_DECLARE(edges_search, BMEdge *);
2448
2449 /* number of resulting verts, include self */
2450 int verts_num = 1;
2451 /* track the total number of edges handled, so we know when we've found the last fan */
2452 int edges_found = 0;
2453
2454#define EDGE_VISIT _FLAG_WALK
2455
2456 /* count and flag at once */
2457 if (v->e) {
2458 BMEdge *e_first, *e_iter;
2459 e_iter = e_first = v->e;
2460 do {
2461 v_edges_num += 1;
2462
2465 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
2466
2467 while (true) {
2468 /* Considering only edges and faces incident on vertex v, walk
2469 * the edges & collect in the 'edges' list for splitting */
2470
2471 BMEdge *e = v->e;
2473
2474 do {
2476 BLI_SMALLSTACK_PUSH(edges, e);
2477 edges_found += 1;
2478
2479 if (e->l) {
2480 BMLoop *l_iter, *l_first;
2481 l_iter = l_first = e->l;
2482 do {
2483 BMLoop *l_adjacent = (l_iter->v == v) ? l_iter->prev : l_iter->next;
2484 BLI_assert(BM_vert_in_edge(l_adjacent->e, v));
2485 if (BM_ELEM_API_FLAG_TEST(l_adjacent->e, EDGE_VISIT)) {
2487 BLI_SMALLSTACK_PUSH(edges_search, l_adjacent->e);
2488 }
2489 } while ((l_iter = l_iter->radial_next) != l_first);
2490 }
2491 } while ((e = static_cast<BMEdge *>(BLI_SMALLSTACK_POP(edges_search))));
2492
2493 /* now we have all edges connected to 'v->e' */
2494
2495 BLI_assert(edges_found <= v_edges_num);
2496
2497 if (edges_found == v_edges_num) {
2498 /* We're done! The remaining edges in 'edges' form the last fan,
2499 * which can be left as is.
2500 * if 'edges' were allocated it'd be freed here. */
2501 break;
2502 }
2503
2504 BMVert *v_new;
2505
2506 v_new = BM_vert_create(bm, v->co, v, BM_CREATE_NOP);
2507 if (copy_select) {
2508 BM_elem_select_copy(bm, v_new, v);
2509 }
2510
2511 while ((e = static_cast<BMEdge *>(BLI_SMALLSTACK_POP(edges)))) {
2512 bmesh_edge_vert_swap(e, v_new, v);
2513 }
2514
2515 if (r_vout) {
2516 BLI_SMALLSTACK_PUSH(verts_new, v_new);
2517 }
2518 verts_num += 1;
2519 }
2520 }
2521
2522#undef EDGE_VISIT
2523
2524 /* flags are clean now, handle return values */
2525
2526 if (r_vout_len != nullptr) {
2527 *r_vout_len = verts_num;
2528 }
2529
2530 if (r_vout != nullptr) {
2531 BMVert **verts;
2532
2533 verts = MEM_new_array_uninitialized<BMVert *>(verts_num, __func__);
2534 *r_vout = verts;
2535
2536 verts[0] = v;
2537 BLI_SMALLSTACK_AS_TABLE(verts_new, &verts[1]);
2538 }
2539}
2540
2561{
2562 do {
2563 LinkNode *n_orig = static_cast<LinkNode *>(edges_separate->link);
2564 do {
2565 LinkNode *n_prev = n_orig;
2566 LinkNode *n_step = n_orig->next;
2567 BMEdge *e_orig = static_cast<BMEdge *>(n_orig->link);
2568 do {
2569 BMEdge *e = static_cast<BMEdge *>(n_step->link);
2570 BLI_assert(e != e_orig);
2571 if ((e->v1 == e_orig->v1) && (e->v2 == e_orig->v2) && BM_edge_splice(bm, e_orig, e)) {
2572 /* don't visit again */
2573 n_prev->next = n_step->next;
2574 }
2575 else {
2576 n_prev = n_step;
2577 }
2578 } while ((n_step = n_step->next));
2579
2580 } while ((n_orig = n_orig->next) && n_orig->next);
2581 } while ((edges_separate = edges_separate->next));
2582}
2583
2585 BMVert *v,
2586 BMEdge **e_in,
2587 int e_in_len,
2588 const bool copy_select,
2589 BMVert ***r_vout,
2590 int *r_vout_len)
2591{
2592 LinkNode *edges_separate = nullptr;
2593 int i;
2594
2595 for (i = 0; i < e_in_len; i++) {
2596 BMEdge *e = e_in[i];
2598 LinkNode *edges_orig = nullptr;
2599 do {
2600 BMLoop *l_sep = e->l;
2601 bmesh_kernel_edge_separate(bm, e, l_sep, copy_select);
2602 BLI_linklist_prepend_alloca(&edges_orig, l_sep->e);
2603 BLI_assert(e != l_sep->e);
2604 } while (bm_edge_supports_separate(e));
2605 BLI_linklist_prepend_alloca(&edges_orig, e);
2606 BLI_linklist_prepend_alloca(&edges_separate, edges_orig);
2607 }
2608 }
2609
2610 bmesh_kernel_vert_separate(bm, v, r_vout, r_vout_len, copy_select);
2611
2612 if (edges_separate) {
2613 bmesh_kernel_vert_separate__cleanup(bm, edges_separate);
2614 }
2615}
2616
2618 BMVert *v,
2619 const char hflag,
2620 const bool copy_select,
2621 BMVert ***r_vout,
2622 int *r_vout_len)
2623{
2624 LinkNode *edges_separate = nullptr;
2625 BMEdge *e_iter, *e_first;
2626
2627 e_iter = e_first = v->e;
2628 do {
2629 if (BM_elem_flag_test(e_iter, hflag)) {
2630 BMEdge *e = e_iter;
2632 LinkNode *edges_orig = nullptr;
2633 do {
2634 BMLoop *l_sep = e->l;
2635 bmesh_kernel_edge_separate(bm, e, l_sep, copy_select);
2636 /* trick to avoid looping over separated edges */
2637 if (edges_separate == nullptr && edges_orig == nullptr) {
2638 e_first = l_sep->e;
2639 }
2640 BLI_linklist_prepend_alloca(&edges_orig, l_sep->e);
2641 BLI_assert(e != l_sep->e);
2642 } while (bm_edge_supports_separate(e));
2643 BLI_linklist_prepend_alloca(&edges_orig, e);
2644 BLI_linklist_prepend_alloca(&edges_separate, edges_orig);
2645 }
2646 }
2647 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first);
2648
2649 bmesh_kernel_vert_separate(bm, v, r_vout, r_vout_len, copy_select);
2650
2651 if (edges_separate) {
2652 bmesh_kernel_vert_separate__cleanup(bm, edges_separate);
2653 }
2654}
2655
2657 BMesh * /*bm*/, BMVert *v_dst, BMVert *v_src, bool (*testfn)(BMEdge *, void *arg), void *arg)
2658{
2659 LinkNode *edges_hflag = nullptr;
2660 BMEdge *e_iter, *e_first;
2661
2662 e_iter = e_first = v_src->e;
2663 do {
2664 if (testfn(e_iter, arg)) {
2665 BLI_linklist_prepend_alloca(&edges_hflag, e_iter);
2666 }
2667 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_src)) != e_first);
2668
2669 if (edges_hflag) {
2670 do {
2671 e_iter = static_cast<BMEdge *>(edges_hflag->link);
2672 bmesh_disk_vert_replace(e_iter, v_dst, v_src);
2673 } while ((edges_hflag = edges_hflag->next));
2674 }
2675}
2676
2678
2679bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src)
2680{
2681 BMLoop *l;
2682
2683 if (!BM_vert_in_edge(e_src, e_dst->v1) || !BM_vert_in_edge(e_src, e_dst->v2)) {
2684 /* not the same vertices can't splice */
2685
2686 /* the caller should really make sure this doesn't happen ever
2687 * so assert on release builds */
2688 BLI_assert(0);
2689
2690 return false;
2691 }
2692
2693 while (e_src->l) {
2694 l = e_src->l;
2695 BLI_assert(BM_vert_in_edge(e_dst, l->v));
2696 BLI_assert(BM_vert_in_edge(e_dst, l->next->v));
2699 }
2700
2701 BLI_assert(bmesh_radial_length(e_src->l) == 0);
2702
2703 BM_CHECK_ELEMENT(e_src);
2704 BM_CHECK_ELEMENT(e_dst);
2705
2706 /* removes from disks too */
2707 BM_edge_kill(bm, e_src);
2708
2709 return true;
2710}
2711
2712void bmesh_kernel_edge_separate(BMesh *bm, BMEdge *e, BMLoop *l_sep, const bool copy_select)
2713{
2714 BMEdge *e_new;
2715#ifndef NDEBUG
2716 const int radlen = bmesh_radial_length(e->l);
2717#endif
2718
2719 BLI_assert(l_sep->e == e);
2720 BLI_assert(e->l);
2721
2722 if (BM_edge_is_boundary(e)) {
2723 BLI_assert(0); /* no cut required */
2724 return;
2725 }
2726
2727 if (l_sep == e->l) {
2728 e->l = l_sep->radial_next;
2729 }
2730
2731 e_new = BM_edge_create(bm, e->v1, e->v2, e, BM_CREATE_NOP);
2733 bmesh_radial_loop_append(e_new, l_sep);
2734 l_sep->e = e_new;
2735
2736 if (copy_select) {
2737 BM_elem_select_copy(bm, e_new, e);
2738 }
2739
2740 BLI_assert(bmesh_radial_length(e->l) == radlen - 1);
2741 BLI_assert(bmesh_radial_length(e_new->l) == 1);
2742
2743 BM_CHECK_ELEMENT(e_new);
2745}
2746
2748{
2749 BMVert *v_new = nullptr;
2750 BMVert *v_sep = l_sep->v;
2751 BMEdge *e_iter;
2752 BMEdge *edges[2];
2753 int i;
2754
2755 /* peel the face from the edge radials on both sides of the
2756 * loop vert, disconnecting the face from its fan */
2757 if (!BM_edge_is_boundary(l_sep->e)) {
2758 bmesh_kernel_edge_separate(bm, l_sep->e, l_sep, false);
2759 }
2760 if (!BM_edge_is_boundary(l_sep->prev->e)) {
2761 bmesh_kernel_edge_separate(bm, l_sep->prev->e, l_sep->prev, false);
2762 }
2763
2764/* do inline, below */
2765#if 0
2766 if (BM_vert_edge_count_is_equal(v_sep, 2)) {
2767 return v_sep;
2768 }
2769#endif
2770
2771 /* Search for an edge unattached to this loop */
2772 e_iter = v_sep->e;
2773 while (!ELEM(e_iter, l_sep->e, l_sep->prev->e)) {
2774 e_iter = bmesh_disk_edge_next(e_iter, v_sep);
2775
2776 /* We've come back around to the initial edge, all touch this loop.
2777 * If there are still only two edges out of v_sep,
2778 * then this whole URMV was just a no-op, so exit now. */
2779 if (e_iter == v_sep->e) {
2781 return v_sep;
2782 }
2783 }
2784
2785 v_sep->e = l_sep->e;
2786
2787 v_new = BM_vert_create(bm, v_sep->co, v_sep, BM_CREATE_NOP);
2788
2789 edges[0] = l_sep->e;
2790 edges[1] = l_sep->prev->e;
2791
2792 for (i = 0; i < ARRAY_SIZE(edges); i++) {
2793 BMEdge *e = edges[i];
2794 bmesh_edge_vert_swap(e, v_new, v_sep);
2795 }
2796
2797 BLI_assert(v_sep != l_sep->v);
2798 BLI_assert(v_sep->e != l_sep->v->e);
2799
2800 BM_CHECK_ELEMENT(l_sep);
2801 BM_CHECK_ELEMENT(v_sep);
2802 BM_CHECK_ELEMENT(edges[0]);
2803 BM_CHECK_ELEMENT(edges[1]);
2804 BM_CHECK_ELEMENT(v_new);
2805
2806 return v_new;
2807}
2808
2810{
2811 BMVert *v_sep = larr[0]->v;
2812 BMVert *v_new;
2813 int edges_len = 0;
2814 int i;
2815 /* any edges not owned by 'larr' loops connected to 'v_sep'? */
2816 bool is_mixed_edge_any = false;
2817 /* any loops not owned by 'larr' radially connected to 'larr' loop edges? */
2818 bool is_mixed_loop_any = false;
2819
2820#define LOOP_VISIT _FLAG_WALK
2821#define EDGE_VISIT _FLAG_WALK
2822
2823 for (i = 0; i < larr_len; i++) {
2824 BMLoop *l_sep = larr[i];
2825
2826 /* all must be from the same vert! */
2827 BLI_assert(v_sep == l_sep->v);
2828
2831
2832 /* weak! but it makes it simpler to check for edges to split
2833 * while doing a radial loop (where loops may be adjacent) */
2836
2837 BMLoop *loop_pair[2] = {l_sep, l_sep->prev};
2838 for (int j = 0; j < ARRAY_SIZE(loop_pair); j++) {
2839 BMEdge *e = loop_pair[j]->e;
2842 edges_len += 1;
2843 }
2844 }
2845 }
2846
2848 BMEdge **edges = edges_buf.data();
2849 STACK_DECLARE(edges);
2850
2851 STACK_INIT(edges, edges_len);
2852
2853 {
2854 BMEdge *e_first, *e_iter;
2855 e_iter = e_first = v_sep->e;
2856 do {
2857 if (BM_ELEM_API_FLAG_TEST(e_iter, EDGE_VISIT)) {
2858 BMLoop *l_iter, *l_first;
2859 bool is_mixed_loop = false;
2860
2861 l_iter = l_first = e_iter->l;
2862 do {
2863 if (!BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) {
2864 is_mixed_loop = true;
2865 break;
2866 }
2867 } while ((l_iter = l_iter->radial_next) != l_first);
2868
2869 if (is_mixed_loop) {
2870 /* ensure the first loop is one we don't own so we can do a quick check below
2871 * on the edge's loop-flag to see if the edge is mixed or not. */
2872 e_iter->l = l_iter;
2873
2874 is_mixed_loop_any = true;
2875 }
2876
2877 STACK_PUSH(edges, e_iter);
2878 }
2879 else {
2880 /* at least one edge attached isn't connected to our loops */
2881 is_mixed_edge_any = true;
2882 }
2883 } while ((e_iter = bmesh_disk_edge_next(e_iter, v_sep)) != e_first);
2884 }
2885
2886 BLI_assert(edges_len == STACK_SIZE(edges));
2887
2888 if (is_mixed_loop_any == false && is_mixed_edge_any == false) {
2889 /* all loops in 'larr' are the sole owners of their edges.
2890 * nothing to split away from, this is a no-op */
2891 v_new = v_sep;
2892 }
2893 else {
2894 v_new = BM_vert_create(bm, v_sep->co, v_sep, BM_CREATE_NOP);
2895
2896 for (i = 0; i < STACK_SIZE(edges); i++) {
2897 BMEdge *e = edges[i];
2898 BMLoop *l_iter, *l_first, *l_next;
2899 BMEdge *e_new;
2900
2901 /* disable so copied edge isn't left dirty (loop edges are cleared last too) */
2903
2904 /* will always be false when (is_mixed_loop_any == false) */
2906 /* edge has some loops owned by us, some owned by other loops */
2907 BMVert *e_new_v_pair[2];
2908
2909 if (e->v1 == v_sep) {
2910 e_new_v_pair[0] = v_new;
2911 e_new_v_pair[1] = e->v2;
2912 }
2913 else {
2914 BLI_assert(v_sep == e->v2);
2915 e_new_v_pair[0] = e->v1;
2916 e_new_v_pair[1] = v_new;
2917 }
2918
2919 e_new = BM_edge_create(bm, UNPACK2(e_new_v_pair), e, BM_CREATE_NOP);
2920
2921 /* now moved all loops from 'larr' to this newly created edge */
2922 l_iter = l_first = e->l;
2923 do {
2924 l_next = l_iter->radial_next;
2925 if (BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) {
2926 bmesh_radial_loop_remove(e, l_iter);
2927 bmesh_radial_loop_append(e_new, l_iter);
2928 l_iter->e = e_new;
2929 }
2930 } while ((l_iter = l_next) != l_first);
2931 }
2932 else {
2933 /* we own the edge entirely, replace the vert */
2934 bmesh_disk_vert_replace(e, v_new, v_sep);
2935 }
2936
2937 /* loop vert is handled last! */
2938 }
2939 }
2940
2941 for (i = 0; i < larr_len; i++) {
2942 BMLoop *l_sep = larr[i];
2943
2944 l_sep->v = v_new;
2945
2952
2955 }
2956
2957#undef LOOP_VISIT
2958#undef EDGE_VISIT
2959
2960 return v_new;
2961}
2962
2964{
2965 BMLoop *l_iter, *l_first;
2966
2967 BLI_assert(ELEM(v_src, e->v1, e->v2));
2968 bmesh_disk_vert_replace(e, v_dst, v_src);
2969
2970 l_iter = l_first = e->l;
2971 do {
2972 if (l_iter->v == v_src) {
2973 l_iter->v = v_dst;
2974 if (BM_vert_in_edge(l_iter->prev->e, v_src)) {
2975 bmesh_edge_vert_swap__recursive(l_iter->prev->e, v_dst, v_src);
2976 }
2977 }
2978 else if (l_iter->next->v == v_src) {
2979 l_iter->next->v = v_dst;
2980 if (BM_vert_in_edge(l_iter->next->e, v_src)) {
2981 bmesh_edge_vert_swap__recursive(l_iter->next->e, v_dst, v_src);
2982 }
2983 }
2984 else {
2985 BLI_assert(l_iter->prev->v != v_src);
2986 }
2987 } while ((l_iter = l_iter->radial_next) != l_first);
2988}
2989
2991{
2992 BMVert *v_new = BM_vert_create(bm, l_sep->v->co, l_sep->v, BM_CREATE_NOP);
2993 /* passing either 'l_sep->e', 'l_sep->prev->e' will work */
2994 bmesh_edge_vert_swap__recursive(l_sep->e, v_new, l_sep->v);
2995 BLI_assert(l_sep->v == v_new);
2996 return v_new;
2997}
2998
3000{
3001 BMLoop *l_iter, *l_first;
3002
3003 BLI_assert(f_a != f_b);
3004
3005 l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
3006 do {
3007 l_iter->f = f_b;
3008 } while ((l_iter = l_iter->next) != l_first);
3009
3010 l_iter = l_first = BM_FACE_FIRST_LOOP(f_b);
3011 do {
3012 l_iter->f = f_a;
3013 } while ((l_iter = l_iter->next) != l_first);
3014
3015 std::swap((*f_a), (*f_b));
3016
3017 /* swap back */
3018 std::swap(f_a->head.data, f_b->head.data);
3019 std::swap(f_a->head.index, f_b->head.index);
3020}
3021
3022} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
#define ORIGINDEX_NONE
#define ENUM_OPERATORS(_enum_type)
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
Read Blender memory allocation and freeing.
#define UNPACK2(a)
#define UNUSED_FUNCTION(x)
#define UNUSED_VARS_NDEBUG(...)
#define BLI_INLINE
#define ELEM(...)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_NGON_MAX
#define BM_FACE_FIRST_LOOP(p)
#define BM_ELEM_CD_GET_VOID_P(ele, offset)
#define LOOP_VISIT
#define EDGE_VISIT
#define VERT_VISIT
#define BMESH_ASSERT(a)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_set(ele, hflag, val)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_select_history_remove(bm, ele)
#define BM_ELEM_API_FLAG_DISABLE(element, f)
#define BM_ELEM_API_FLAG_TEST(element, f)
#define BM_CHECK_ELEMENT(el)
#define BM_ELEM_API_FLAG_ENABLE(element, f)
#define BM_edge_face_count_is_over(e, n)
#define BM_vert_edge_count_is_equal(v, n)
const T * data() const
Definition BLI_array.hh:323
constexpr IndexRange()=default
int64_t size() const
void append(const T &value)
bool is_empty() const
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
BMesh Iterators.
void bmesh_disk_edge_remove(BMEdge *e, BMVert *v)
@ IS_FACE_NULL_EDGE
@ IS_LOOP_WRONG_VERT_TYPE
@ IS_FACE_NULL_VERT
@ IS_WRONG_TYPE
@ IS_EDGE_ZERO_FACE_LENGTH
@ IS_FACE_LOOP_VERT_NOT_IN_EDGE
@ IS_LOOP_WRONG_RADIAL_LENGTH
@ IS_FACE_LOOP_WRONG_RADIAL_LENGTH
@ IS_FACE_WRONG_LOOP_FACE
@ IS_FACE_LOOP_DUPE_EDGE
@ IS_LOOP_NULL_CYCLE_LINK
@ IS_EDGE_NULL_DISK_LINK
@ IS_LOOP_WRONG_FACE_TYPE
@ IS_LOOP_WRONG_EDGE_TYPE
@ IS_FACE_WRONG_LENGTH
@ IS_FACE_LOOP_DUPE_LOOP
@ IS_LOOP_ZERO_FACE_LENGTH
@ IS_LOOP_WRONG_FACE_LENGTH
@ IS_VERT_WRONG_EDGE_TYPE
@ IS_FACE_NULL_LOOP
@ IS_EDGE_WRONG_FACE_TYPE
@ IS_LOOP_VERT_NOT_IN_EDGE
@ IS_EDGE_NULL_RADIAL_LINK
@ IS_FACE_LOOP_DUPE_VERT
@ IS_EDGE_WRONG_LOOP_TYPE
@ IS_FACE_LOOP_WRONG_DISK_LENGTH
void BM_face_calc_center_median(const BMFace *f, float r_cent[3])
int CustomData_get_offset(const CustomData *data, eCustomDataType type)
BMFace * BM_face_copy(BMesh *bm_dst, const BMCustomDataCopyMap &cd_face_map, const BMCustomDataCopyMap &cd_loop_map, BMFace *f, const bool copy_verts, const bool copy_edges)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void bmesh_radial_loop_append(BMEdge *e, BMLoop *l)
BMFace * BM_face_create_verts(BMesh *bm, BMVert **vert_arr, const int len, const BMFace *f_example, const eBMCreateFlag create_flag, const bool create_edges)
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
bool bmesh_disk_validate(int len, BMEdge *e, BMVert *v)
static void bm_elements_systag_disable(void *veles, int tot, const char api_flag)
void * CustomData_bmesh_get(const CustomData *data, void *block, eCustomDataType type)
bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
@ BM_SPACEARR_DIRTY_ALL
void bmesh_kernel_loop_reverse(BMesh *bm, BMFace *f, const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
Loop Reverse.
MINLINE void copy_v3_v3(float r[3], const float a[3])
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
BMFace * bmesh_kernel_split_face_make_edge(BMesh *bm, BMFace *f, BMLoop *l_v1, BMLoop *l_v2, BMLoop **r_l, BMEdge *e_example, const bool no_double)
Split Face Make Edge (SFME).
static void bm_kill_only_edge(BMesh *bm, BMEdge *e)
ATTR_WARN_UNUSED_RESULT const BMLoop * l
BMVert * bmesh_kernel_join_vert_kill_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool check_edge_exists, const bool kill_degenerate_faces)
Join Vert Kill Edge (JVKE).
void BM_vert_separate_hflag(BMesh *bm, BMVert *v, const char hflag, const bool copy_select, BMVert ***r_vout, int *r_vout_len)
bool bmesh_radial_validate(int radlen, BMLoop *l)
void bmesh_edge_vert_swap(BMEdge *e, BMVert *v_dst, BMVert *v_src)
void BM_vert_kill(BMesh *bm, BMVert *v)
void BM_face_edges_kill(BMesh *bm, BMFace *f)
static BMFace * bm_face_create__sfme(BMesh *bm, BMFace *f_example)
BMLoop * BM_face_edge_share_loop(BMFace *f, BMEdge *e)
Return the Loop Shared by Face and Edge.
static void bmesh_kernel_vert_separate__cleanup(BMesh *bm, LinkNode *edges_separate)
void void void BLI_movelisttolist(ListBase *dst, ListBase *src) ATTR_NONNULL(1
Definition listbase.cc:32
BMVert * bmesh_kernel_unglue_region_make_vert_multi(BMesh *bm, BMLoop **larr, int larr_len)
static void bm_kill_only_loop(BMesh *bm, BMLoop *l)
bool bmesh_loop_validate(BMFace *f)
BMVert * bmesh_kernel_split_edge_make_vert(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e)
Split Edge Make Vert (SEMV).
BMVert * bmesh_kernel_unglue_region_make_vert_multi_isolated(BMesh *bm, BMLoop *l_sep)
ATTR_WARN_UNUSED_RESULT const BMVert * v
void CustomData_bmesh_copy_block(CustomData &data, void *src_block, void **dst_block)
BMVert * BM_vert_create(BMesh *bm, const float co[3], const BMVert *v_example, const eBMCreateFlag create_flag)
Main function for creating a new vertex.
static void bm_elements_systag_enable(void *veles, int tot, const char api_flag)
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BMFace * BM_face_create(BMesh *bm, BMVert *const *verts, BMEdge *const *edges, const int len, const BMFace *f_example, const eBMCreateFlag create_flag)
static int UNUSED_FUNCTION bm_loop_length(BMLoop *l)
BMEdge * bmesh_kernel_join_edge_kill_vert(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool check_edge_exists, const bool kill_degenerate_faces, const bool kill_duplicate_faces)
Join Edge Kill Vert (JEKV).
int bmesh_elem_check(void *element, const char htype)
void BM_vert_separate_tested_edges(BMesh *, BMVert *v_dst, BMVert *v_src, bool(*testfn)(BMEdge *, void *arg), void *arg)
void bmesh_kernel_edge_separate(BMesh *bm, BMEdge *e, BMLoop *l_sep, const bool copy_select)
Separate Edge.
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 bmesh_radial_loop_remove(BMEdge *e, BMLoop *l)
BMESH RADIAL REMOVE LOOP.
void BM_face_verts_kill(BMesh *bm, BMFace *f)
int BM_face_share_edge_count(BMFace *f_a, BMFace *f_b)
int bmesh_radial_length(const BMLoop *l)
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
BMFace * BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del, BMFace **r_double)
Join Connected Faces.
void BM_vert_separate(BMesh *bm, BMVert *v, BMEdge **e_in, int e_in_len, const bool copy_select, BMVert ***r_vout, int *r_vout_len)
void CustomData_bmesh_free_block(CustomData *data, void **block)
void CustomData_bmesh_set_default(CustomData *data, void **block)
int bmesh_disk_count_at_most(const BMVert *v, int count_max)
void bmesh_disk_vert_replace(BMEdge *e, BMVert *v_dst, BMVert *v_src)
static void bm_kill_only_vert(BMesh *bm, BMVert *v)
ATTR_WARN_UNUSED_RESULT const BMFlagLayer * oflags
@ BM_CREATE_NO_DOUBLE
Definition bmesh_core.hh:36
@ BM_CREATE_NOP
Definition bmesh_core.hh:34
@ BM_CREATE_SKIP_CD
Definition bmesh_core.hh:42
static void bm_kill_only_face(BMesh *bm, BMFace *f)
bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src)
Splice Edge.
void BLI_remlink(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:138
void BM_edge_kill(BMesh *bm, BMEdge *e)
BMFace * bmesh_kernel_join_face_kill_edge(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e)
Join Face Kill Edge (JFKE).
bool BM_edges_from_verts(BMEdge **edge_arr, BMVert **vert_arr, const int len)
void BM_elem_select_copy(BMesh *bm_dst, void *ele_dst_v, const void *ele_src_v)
void bmesh_kernel_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len, const bool copy_select)
Separate Vert.
bool BM_face_split_check_double_face(BMLoop *l_a, BMLoop *l_b, const int f_len)
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
int bmesh_disk_count(const BMVert *v)
static BMFace * bm_face_copy_impl(BMesh *bm_dst, BMFace *f, const bool copy_verts, const bool copy_edges)
bool BM_vert_pair_share_face_check(BMVert *v_a, BMVert *v_b)
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
BMVert * bmesh_kernel_unglue_region_make_vert(BMesh *bm, BMLoop *l_sep)
Un-glue Region Make Vert (URMV).
void BM_face_kill_loose(BMesh *bm, BMFace *f)
bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
Splice Vert.
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void bmesh_disk_edge_append(BMEdge *e, BMVert *v)
BLI_INLINE bool BM_verts_in_edge(const BMVert *v1, const BMVert *v2, const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BKE_mesh_mdisp_flip(MDisps *md, bool use_loop_mdisp_flip)
MINLINE void zero_v3(float r[3])
static BMLoop * bm_face_boundary_add(BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte, const eBMCreateFlag create_flag)
bool BM_vert_splice_check_double_edge(BMVert *v_a, BMVert *v_b)
static int UNUSED_FUNCTION bm_vert_systag_count_disk(BMVert *v, const char api_flag)
BMFace * BM_face_exists(BMVert *const *varr, int len)
void BM_edges_from_verts_ensure(BMesh *bm, BMEdge **edge_arr, BMVert **vert_arr, const int len)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:118
ATTR_WARN_UNUSED_RESULT const BMVert * v2
void BM_face_kill(BMesh *bm, BMFace *f)
BMFace * BM_face_create_ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, const int len, const BMFace *f_example, const eBMCreateFlag create_flag)
Make NGon.
void * BLI_mempool_calloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
BMFace * BM_face_exists_subset_from_face(BMLoop *l_a, BMLoop *l_b, const int f_len)
static BMLoop * bm_loop_create(BMesh *bm, BMVert *v, BMEdge *e, BMFace *f, const BMLoop *l_example, const eBMCreateFlag create_flag)
bool BM_vert_is_edge_pair(const BMVert *v)
static void bmesh_edge_vert_swap__recursive(BMEdge *e, BMVert *v_dst, BMVert *v_src)
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BMFace * BM_face_find_double(BMFace *f)
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
bool BM_vert_splice_check_double_face(BMVert *v_a, BMVert *v_b)
bool BM_vert_collapse_check_double_face(BMVert *v_collapse)
void BM_loop_interp_multires_ex(BMesh *, BMLoop *l_dst, const BMFace *f_src, const float f_dst_center[3], const float f_src_center[3], const int cd_loop_mdisp_offset)
void BM_elem_attrs_copy(BMesh *bm, const BMCustomDataCopyMap &map, const BMVert *src, BMVert *dst)
ATTR_WARN_UNUSED_RESULT const void * element
@ BM_ELEM_INTERNAL_TAG
void bmesh_radial_loop_unlink(BMLoop *l)
BMEdge * BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *e_example, const eBMCreateFlag create_flag)
Main function for creating a new edge.
BLI_INLINE BMFace * bm_face_create__internal(BMesh *bm)
static bool bm_vert_is_manifold_flagged(BMVert *v, const char api_flag)
void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b)
BLI_INLINE bool bm_edge_supports_separate(const BMEdge *e)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
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
static int bm_loop_systag_count_radial(BMLoop *l, const char api_flag)
struct BMLoop * l
struct BMLoop * next
struct BMLoop * prev
struct BMLoop * radial_prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct BMEdge * e
struct LinkNode * next
struct BMLoop * radial_next
struct BMLoop * radial_prev