Blender V5.3
bmesh_edgeloop.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2013 by Campbell Barton. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include "MEM_guardedalloc.h"
12
13#include "BLI_listbase.hh"
14#include "BLI_math_vector_c.hh"
15#include "BLI_mempool.hh"
16#include "BLI_set.hh"
17#include "BLI_stack_c.hh"
19
20#include "bmesh.hh"
21
22#include "bmesh_edgeloop.hh" /* own include */
23
24namespace blender {
25
28 ListBaseT<LinkData> verts;
29 int flag;
30 int len;
31 /* Optional values to calculate. */
32 float co[3], no[3];
33};
34
35#define BM_EDGELOOP_IS_CLOSED (1 << 0)
40#define BM_EDGELOOP_IS_CLOSED_JUNCTION (1 << 1)
41
42/* Use a small value since we need normals even for very small loops. */
43#define EDGELOOP_EPS 1e-10f
44
45/* -------------------------------------------------------------------- */
46/* BM_mesh_edgeloops_find & Utility Functions. */
47
48static int bm_vert_other_tag(BMVert *v, BMVert *v_prev, BMEdge **r_e)
49{
50 BMIter iter;
51 BMEdge *e, *e_next = nullptr;
52 uint count = 0;
53
54 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
56 BMVert *v_other = BM_edge_other_vert(e, v);
57 if (v_other != v_prev) {
58 e_next = e;
59 count++;
60 }
61 }
62 }
63
64 *r_e = e_next;
65 return count;
66}
67
73{
74 BMIter iter;
75 BMEdge *e;
76 int count = 0;
77 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
79 count++;
80 if (count > 2) {
81 return true;
82 }
83 }
84 }
85 return false;
86}
87
94static bool bm_loop_build(BMEdgeLoopStore *el_store,
95 BMVert *v_prev,
96 BMVert *v,
97 int dir,
98 const Set<BMVert *> *vert_junctions)
99{
100 void (*add_fn)(ListBase *, void *) = dir == 1 ? BLI_addhead : BLI_addtail;
101 BMEdge *e_next;
102 BMVert *v_next;
103 BMVert *v_first = v;
104
105 BLI_assert(abs(dir) == 1);
106
108 return true;
109 }
110
111 while (v) {
113 int count;
114 node->data = v;
115 add_fn(&el_store->verts, node);
116 el_store->len++;
117
118 if (vert_junctions) {
119 /* A junction terminates the loop: it may be shared as an end-point by other loops
120 * (so its tag is left set), but is never traversed. */
121 if (vert_junctions->contains(v)) {
122 break;
123 }
124 }
126
127 count = bm_vert_other_tag(v, v_prev, &e_next);
128 if (count == 1) {
129 v_next = BM_edge_other_vert(e_next, v);
131 if (v_next == v_first) [[unlikely]] {
132 el_store->flag |= BM_EDGELOOP_IS_CLOSED;
133 v_next = nullptr;
134 }
135 }
136 else if (count == 0) {
137 /* pass */
138 v_next = nullptr;
139 }
140 else {
141 v_next = nullptr;
142 return false;
143 }
144
145 v_prev = v;
146 v = v_next;
147 }
148
149 return true;
150}
151
153 ListBaseT<BMEdgeLoopStore> *r_eloops,
154 FunctionRef<bool(BMEdge *)> test_fn,
155 const BMEdgeLoopFind_Params *params)
156{
157 BMIter iter;
158 BMEdge *e;
159 BMVert *v;
160 int count = 0;
161 bool use_vert_junction = params ? params->use_vert_junction : false;
162
163 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
165 }
166
167 /* first flush edges to tags, and tag verts */
168 BLI_Stack *edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__);
169 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
171 if (test_fn(e)) {
175 BLI_stack_push(edge_stack, static_cast<void *>(&e));
176 }
177 else {
179 }
180 }
181
182 const uint edges_len = BLI_stack_count(edge_stack);
183 BMEdge **edges = MEM_new_array_uninitialized<BMEdge *>(edges_len, __func__);
184 BLI_stack_pop_n_reverse(edge_stack, edges, BLI_stack_count(edge_stack));
185 BLI_stack_free(edge_stack);
186
187 /* Collect junctions in a single pass while the edge tags are still complete, so membership can
188 * be tested cheaply as the walk clears the tags. */
189 Set<BMVert *> vert_junction_set;
190 if (use_vert_junction) {
191 for (BMEdge *e : Span{edges, edges_len}) {
192 for (BMVert *v_end : {e->v1, e->v2}) {
193 if (!vert_junction_set.contains(v_end) && bm_vert_is_junction(v_end)) {
194 vert_junction_set.add(v_end);
195 }
196 }
197 }
198 }
199 if (vert_junction_set.is_empty()) {
200 use_vert_junction = false;
201 }
202 const Set<BMVert *> *vert_junctions = use_vert_junction ? &vert_junction_set : nullptr;
203
204 for (BMEdge *e : Span{edges, edges_len}) {
207
208 /* add both directions */
209 const bool built = bm_loop_build(el_store, e->v1, e->v2, 1, vert_junctions) &&
210 bm_loop_build(el_store, e->v2, e->v1, -1, vert_junctions);
211
212 if (use_vert_junction) {
213 /* Both directions ending on the same vertex means they met at a shared junction:
214 * the loop is cyclic, anchored at that junction. Drop the duplicated end and flag it
215 * (kept distinct from a fully closed loop, which has no anchor). */
216 if (built && el_store->len >= 2) {
217 LinkData *node_first = el_store->verts.first();
218 LinkData *node_last = el_store->verts.last();
219 if (node_first->data == node_last->data) {
220 BLI_remlink(&el_store->verts, node_last);
221 MEM_delete(node_last);
222 el_store->len--;
224 }
225 }
226 }
227
228 if (built && el_store->len > 1) {
229 BLI_addtail(r_eloops, el_store);
230 count++;
231 }
232 else {
233 BM_edgeloop_free(el_store);
234 }
235 }
236 }
237
238 for (BMEdge *e : Span{edges, edges_len}) {
242 }
243
244 MEM_delete(edges);
245 return count;
246}
247
248/* -------------------------------------------------------------------- */
249/* BM_mesh_edgeloops_find_path & Util Functions. */
250
259
260static void vs_add(
261 BLI_mempool *vs_pool, ListBaseT<VertStep> *lb, BMVert *v, BMEdge *e_prev, const int iter_tot)
262{
263 VertStep *vs_new = static_cast<VertStep *>(BLI_mempool_alloc(vs_pool));
264 vs_new->v = v;
265
266 BM_elem_index_set(v, iter_tot); /* set_dirty */
267
268 /* This edge stores a direct path back to the original vertex so we can
269 * backtrack without having to store an array of previous verts. */
270
271 /* WARNING: Setting the edge is not common practice but currently harmless, take care. */
272 BLI_assert(BM_vert_in_edge(e_prev, v));
273 v->e = e_prev;
274
275 BLI_addtail(lb, vs_new);
276}
277
279 ListBaseT<VertStep> *lb,
280 const int dir,
281 BMVert *v_match[2])
282{
283 ListBaseT<VertStep> lb_tmp = {nullptr, nullptr};
284 VertStep *vs, *vs_next;
285 BLI_assert(abs(dir) == 1);
286
287 for (vs = lb->first(); vs; vs = vs_next) {
288 BMIter iter;
289 BMEdge *e;
290 /* these values will be the same every iteration */
291 const int vs_iter_tot = BM_elem_index_get(vs->v);
292 const int vs_iter_next = vs_iter_tot + dir;
293
294 vs_next = vs->next;
295
296 BM_ITER_ELEM (e, &iter, vs->v, BM_EDGES_OF_VERT) {
298 BMVert *v_next = BM_edge_other_vert(e, vs->v);
299 const int v_next_index = BM_elem_index_get(v_next);
300 /* not essential to clear flag but prevents more checking next time round */
302 if (v_next_index == 0) {
303 vs_add(vs_pool, &lb_tmp, v_next, e, vs_iter_next);
304 }
305 else if ((dir < 0) == (v_next_index < 0)) {
306 /* on the same side - do nothing */
307 }
308 else {
309 /* we have met out match! (vertices from different sides meet) */
310 if (dir == 1) {
311 v_match[0] = vs->v;
312 v_match[1] = v_next;
313 }
314 else {
315 v_match[0] = v_next;
316 v_match[1] = vs->v;
317 }
318 /* normally we would manage memory of remaining items in (lb, lb_tmp),
319 * but search is done, vs_pool will get destroyed immediately */
320 return true;
321 }
322 }
323 }
324
325 BLI_mempool_free(vs_pool, vs);
326 }
327
328 /* Commented because used in a loop, and this flag has already been set. */
329 // bm->elem_index_dirty |= BM_VERT;
330
331 /* `lb` is now full of freed items, overwrite. */
332 *lb = lb_tmp;
333
334 return (lb->is_empty() == false);
335}
336
338 ListBaseT<BMEdgeLoopStore> *r_eloops,
339 FunctionRef<bool(BMEdge *)> test_fn,
340 BMVert *v_src,
341 BMVert *v_dst)
342{
343 BMIter iter;
344 BMEdge *e;
345 bool found = false;
346
347 BLI_assert(v_src != v_dst);
348
349 {
350 BMVert *v;
351 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
354 }
355 }
357
358 /* first flush edges to tags, and tag verts */
359 int edges_len;
360 BMEdge **edges;
361
362 if (test_fn) {
363 BLI_Stack *edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__);
364 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
365 if (test_fn(e)) {
369 BLI_stack_push(edge_stack, static_cast<void *>(&e));
370 }
371 else {
373 }
374 }
375 edges_len = BLI_stack_count(edge_stack);
376 edges = MEM_new_array_uninitialized<BMEdge *>(edges_len, __func__);
377 BLI_stack_pop_n_reverse(edge_stack, edges, BLI_stack_count(edge_stack));
378 BLI_stack_free(edge_stack);
379 }
380 else {
381 int i = 0;
382 edges_len = bm->totedge;
383 edges = MEM_new_array_uninitialized<BMEdge *>(edges_len, __func__);
384
389 edges[i] = e;
390 }
391 }
392
393 /* prime the lists and begin search */
394 {
395 BMVert *v_match[2] = {nullptr, nullptr};
396 ListBaseT<VertStep> lb_src = {nullptr, nullptr};
397 ListBaseT<VertStep> lb_dst = {nullptr, nullptr};
398 BLI_mempool *vs_pool = BLI_mempool_create(sizeof(VertStep), 0, 512, BLI_MEMPOOL_NOP);
399
400 /* edge args are dummy */
401 vs_add(vs_pool, &lb_src, v_src, v_src->e, 1);
402 vs_add(vs_pool, &lb_dst, v_dst, v_dst->e, -1);
404
405 do {
406 if ((bm_loop_path_build_step(vs_pool, &lb_src, 1, v_match) == false) || v_match[0]) {
407 break;
408 }
409 if ((bm_loop_path_build_step(vs_pool, &lb_dst, -1, v_match) == false) || v_match[0]) {
410 break;
411 }
412 } while (true);
413
414 BLI_mempool_destroy(vs_pool);
415
416 if (v_match[0]) {
418 BMVert *v;
419
420 /* build loop from edge pointers */
421 v = v_match[0];
422 while (true) {
424 node->data = v;
425 BLI_addhead(&el_store->verts, node);
426 el_store->len++;
427 if (v == v_src) {
428 break;
429 }
430 v = BM_edge_other_vert(v->e, v);
431 }
432
433 v = v_match[1];
434 while (true) {
436 node->data = v;
437 BLI_addtail(&el_store->verts, node);
438 el_store->len++;
439 if (v == v_dst) {
440 break;
441 }
442 v = BM_edge_other_vert(v->e, v);
443 }
444
445 BLI_addtail(r_eloops, el_store);
446
447 found = true;
448 }
449 }
450
451 for (BMEdge *e : Span{edges, edges_len}) {
455 }
456 MEM_delete(edges);
457
458 return found;
459}
460
461/* -------------------------------------------------------------------- */
462/* BM_mesh_edgeloops_xxx utility function */
463
464void BM_mesh_edgeloops_free(ListBaseT<BMEdgeLoopStore> *eloops)
465{
466 while (BMEdgeLoopStore *el_store = static_cast<BMEdgeLoopStore *>(BLI_pophead(eloops))) {
467 BM_edgeloop_free(el_store);
468 }
469}
470
471void BM_mesh_edgeloops_calc_center(BMesh *bm, ListBaseT<BMEdgeLoopStore> *eloops)
472{
473 for (BMEdgeLoopStore &el_store : *eloops) {
474 BM_edgeloop_calc_center(bm, &el_store);
475 }
476}
477
478void BM_mesh_edgeloops_calc_normal(BMesh *bm, ListBaseT<BMEdgeLoopStore> *eloops)
479{
480 for (BMEdgeLoopStore &el_store : *eloops) {
481 BM_edgeloop_calc_normal(bm, &el_store);
482 }
483}
484
486 ListBaseT<BMEdgeLoopStore> *eloops,
487 const float no_align[3])
488{
489 for (BMEdgeLoopStore &el_store : *eloops) {
490 BM_edgeloop_calc_normal_aligned(bm, &el_store, no_align);
491 }
492}
493
495 ListBaseT<BMEdgeLoopStore> *eloops,
496 const bool use_normals)
497{
498 ListBaseT<BMEdgeLoopStore> eloops_ordered = {nullptr};
499 float cent[3];
500 int tot = 0;
501 zero_v3(cent);
502 /* assumes we calculated centers already */
503 for (BMEdgeLoopStore &el_store : *eloops) {
504 if (!is_finite_v3(el_store.co)) [[unlikely]] {
505 continue;
506 }
507 add_v3_v3(cent, el_store.co);
508 tot += 1;
509 }
510 if (tot > 0) {
511 mul_v3_fl(cent, 1.0f / float(tot));
512 if (!is_finite_v3(cent)) {
513 zero_v3(cent);
514 }
515 }
516
517 /* Find the furthest out loop. */
518 {
519 BMEdgeLoopStore *el_store_best = nullptr;
520 float len_best_sq = -1.0f;
521 for (BMEdgeLoopStore &el_store : *eloops) {
522 const float len_sq = len_squared_v3v3(cent, el_store.co);
523 /* Null check to account for non-finite distances. */
524 if ((len_sq > len_best_sq) || (el_store_best == nullptr)) {
525 len_best_sq = len_sq;
526 el_store_best = &el_store;
527 }
528 }
529
530 BLI_remlink(eloops, el_store_best);
531 BLI_addtail(&eloops_ordered, el_store_best);
532 }
533
534 /* not so efficient re-ordering */
535 while (eloops->first()) {
536 BMEdgeLoopStore *el_store_best = nullptr;
537 const float *co = (eloops_ordered.last())->co;
538 const float *no = (eloops_ordered.last())->no;
539 float len_best_sq = FLT_MAX;
540
541 if (use_normals) {
543 }
544
545 for (BMEdgeLoopStore &el_store : *eloops) {
546 float len_sq;
547 if (use_normals) {
548 /* Scale the length by how close the loops are to pointing at each other. */
549 float dir[3];
550 sub_v3_v3v3(dir, co, el_store.co);
551 len_sq = normalize_v3(dir);
552 len_sq = len_sq *
553 ((1.0f - fabsf(dot_v3v3(dir, no))) + (1.0f - fabsf(dot_v3v3(dir, el_store.no))));
554 }
555 else {
556 len_sq = len_squared_v3v3(co, el_store.co);
557 }
558
559 /* Null check to account for non-finite distances. */
560 if ((len_sq < len_best_sq) || (el_store_best == nullptr)) {
561 len_best_sq = len_sq;
562 el_store_best = &el_store;
563 }
564 }
565
566 BLI_remlink(eloops, el_store_best);
567 BLI_addtail(&eloops_ordered, el_store_best);
568 }
569
570 *eloops = eloops_ordered;
571}
572
573/* -------------------------------------------------------------------- */
574/* BM_edgeloop_*** functions */
575
577{
579 *el_store_copy = *el_store;
580 BLI_duplicatelist(&el_store_copy->verts, &el_store->verts);
581 return el_store_copy;
582}
583
584BMEdgeLoopStore *BM_edgeloop_from_verts(BMVert **v_arr, const int v_arr_tot, bool is_closed)
585{
587 int i;
588 for (i = 0; i < v_arr_tot; i++) {
590 node->data = v_arr[i];
591 BLI_addtail(&el_store->verts, node);
592 }
593 el_store->len = v_arr_tot;
594 if (is_closed) {
595 el_store->flag |= BM_EDGELOOP_IS_CLOSED;
596 }
597 return el_store;
598}
599
601{
602 el_store->verts.free_no_destruct();
603 MEM_delete(el_store);
604}
605
607{
608 return (el_store->flag & BM_EDGELOOP_IS_CLOSED) != 0;
609}
610
612{
613 return (el_store->flag & BM_EDGELOOP_IS_CLOSED_JUNCTION) != 0;
614}
615
616ListBaseT<LinkData> *BM_edgeloop_verts_get(BMEdgeLoopStore *el_store)
617{
618 return &el_store->verts;
619}
620
622{
623 return el_store->len;
624}
625
627{
628 return el_store->no;
629}
630
632{
633 return el_store->co;
634}
635
636#define NODE_AS_V(n) ((BMVert *)((LinkData *)n)->data)
637#define NODE_AS_CO(n) ((BMVert *)((LinkData *)n)->data)->co
638
640{
641 LinkData *node;
642 int i = 0;
643 for (node = el_store->verts.first(); node && node->next; node = node->next) {
644 e_arr[i++] = BM_edge_exists(NODE_AS_V(node), NODE_AS_V(node->next));
645 BLI_assert(e_arr[i - 1] != nullptr);
646 }
647
648 if (el_store->flag & BM_EDGELOOP_IS_CLOSED) {
649 e_arr[i] = BM_edge_exists(NODE_AS_V(el_store->verts.first()),
650 NODE_AS_V(el_store->verts.last()));
651 BLI_assert(e_arr[i] != nullptr);
652 }
653 BLI_assert(el_store->len == i + 1);
654}
655
657{
658 LinkData *node_curr = el_store->verts.last();
659 LinkData *node_prev = (el_store->verts.last())->prev;
660 LinkData *node_first = el_store->verts.first();
661 LinkData *node_next = node_first;
662
663 const float *v_prev = NODE_AS_CO(node_prev);
664 const float *v_curr = NODE_AS_CO(node_curr);
665 const float *v_next = NODE_AS_CO(node_next);
666
667 float totw = 0.0f;
668 float w_prev;
669
670 zero_v3(el_store->co);
671
672 w_prev = len_v3v3(v_prev, v_curr);
673 do {
674 const float w_curr = len_v3v3(v_curr, v_next);
675 const float w = (w_curr + w_prev);
676 madd_v3_v3fl(el_store->co, v_curr, w);
677 totw += w;
678 w_prev = w_curr;
679
680 node_prev = node_curr;
681 node_curr = node_next;
682 node_next = node_next->next;
683
684 if (node_next == nullptr) {
685 break;
686 }
687 v_prev = v_curr;
688 v_curr = v_next;
689 v_next = NODE_AS_CO(node_next);
690 } while (true);
691
692 if (totw != 0.0f) {
693 mul_v3_fl(el_store->co, 1.0f / totw);
694 }
695}
696
698{
699 LinkData *node_curr = el_store->verts.first();
700 const float *v_prev = NODE_AS_CO(el_store->verts.last());
701 const float *v_curr = NODE_AS_CO(node_curr);
702
703 zero_v3(el_store->no);
704
705 /* Newell's Method */
706 do {
707 add_newell_cross_v3_v3v3(el_store->no, v_prev, v_curr);
708
709 if ((node_curr = node_curr->next)) {
710 v_prev = v_curr;
711 v_curr = NODE_AS_CO(node_curr);
712 }
713 else {
714 break;
715 }
716 } while (true);
717
718 if (normalize_v3(el_store->no) < EDGELOOP_EPS) [[unlikely]] {
719 el_store->no[2] = 1.0f; /* other axis set to 0.0 */
720 return false;
721 }
722 return true;
723}
724
726 BMEdgeLoopStore *el_store,
727 const float no_align[3])
728{
729 LinkData *node_curr = el_store->verts.first();
730 const float *v_prev = NODE_AS_CO(el_store->verts.last());
731 const float *v_curr = NODE_AS_CO(node_curr);
732
733 zero_v3(el_store->no);
734
735 /* Own Method */
736 do {
737 float cross[3], no[3], dir[3];
738 sub_v3_v3v3(dir, v_curr, v_prev);
739 cross_v3_v3v3(cross, no_align, dir);
740 cross_v3_v3v3(no, dir, cross);
741 add_v3_v3(el_store->no, no);
742
743 if ((node_curr = node_curr->next)) {
744 v_prev = v_curr;
745 v_curr = NODE_AS_CO(node_curr);
746 }
747 else {
748 break;
749 }
750 } while (true);
751
752 if (normalize_v3(el_store->no) < EDGELOOP_EPS) [[unlikely]] {
753 el_store->no[2] = 1.0f; /* other axis set to 0.0 */
754 return false;
755 }
756 return true;
757}
758
759void BM_edgeloop_flip(BMesh * /*bm*/, BMEdgeLoopStore *el_store)
760{
761 negate_v3(el_store->no);
762 BLI_listbase_reverse(&el_store->verts);
763}
764
766 BMesh *bm, BMEdgeLoopStore *el_store, int el_store_len, bool split, Set<BMEdge *> *split_edges)
767{
768 bool split_swap = true;
769
770#define EDGE_SPLIT(node_copy, node_other) \
771 { \
772 BMVert *v_split, *v_other = static_cast<BMVert *>((node_other)->data); \
773 BMEdge *e_split, \
774 *e_other = BM_edge_exists(static_cast<BMVert *>((node_copy)->data), v_other); \
775 v_split = BM_edge_split(bm, \
776 e_other, \
777 static_cast<BMVert *>(split_swap ? (node_copy)->data : v_other), \
778 &e_split, \
779 0.0f); \
780 v_split->e = e_split; \
781 BLI_assert(v_split == e_split->v2); \
782 split_edges->add(e_split); \
783 (node_copy)->data = v_split; \
784 } \
785 ((void)0)
786
787 /* first double until we are more than half as big */
788 while ((el_store->len * 2) < el_store_len) {
789 LinkData *node_curr = el_store->verts.first();
790 while (node_curr) {
791 LinkData *node_curr_copy = MEM_dupalloc(node_curr);
792 if (split == false) {
793 BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
794 node_curr = node_curr_copy->next;
795 }
796 else {
797 if (node_curr->next || (el_store->flag & BM_EDGELOOP_IS_CLOSED)) {
798 EDGE_SPLIT(node_curr_copy,
799 node_curr->next ? node_curr->next : (LinkData *)el_store->verts.first());
800 BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
801 node_curr = node_curr_copy->next;
802 }
803 else {
804 EDGE_SPLIT(node_curr_copy, node_curr->prev);
805 BLI_insertlinkbefore(&el_store->verts, node_curr, node_curr_copy);
806 node_curr = node_curr->next;
807 }
808 split_swap = !split_swap;
809 }
810 el_store->len++;
811 }
812 split_swap = !split_swap;
813 }
814
815 if (el_store->len < el_store_len) {
816 LinkData *node_curr = el_store->verts.first();
817
818 int iter_prev = 0;
819 BLI_FOREACH_SPARSE_RANGE (el_store->len, (el_store_len - el_store->len), iter) {
820 while (iter_prev < iter) {
821 node_curr = node_curr->next;
822 iter_prev += 1;
823 }
824
825 LinkData *node_curr_copy;
826 node_curr_copy = MEM_dupalloc(node_curr);
827 if (split == false) {
828 BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
829 node_curr = node_curr_copy->next;
830 }
831 else {
832 if (node_curr->next || (el_store->flag & BM_EDGELOOP_IS_CLOSED)) {
833 EDGE_SPLIT(node_curr_copy,
834 node_curr->next ? node_curr->next : (LinkData *)el_store->verts.first());
835 BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
836 node_curr = node_curr_copy->next;
837 }
838 else {
839 EDGE_SPLIT(node_curr_copy, node_curr->prev);
840 BLI_insertlinkbefore(&el_store->verts, node_curr, node_curr_copy);
841 node_curr = node_curr->next;
842 }
843 split_swap = !split_swap;
844 }
845 el_store->len++;
846 iter_prev += 1;
847 }
848 }
849
850#undef BKE_FOREACH_SUBSET_OF_RANGE
851#undef EDGE_SPLIT
852
853 BLI_assert(el_store->len == el_store_len);
854}
855
857{
858 /* A little more efficient if 'a' as smaller. */
859 if (el_store_a->len > el_store_b->len) {
860 std::swap(el_store_a, el_store_b);
861 }
862
863 /* init */
864 for (LinkData &node : el_store_a->verts) {
866 }
867 for (LinkData &node : el_store_b->verts) {
869 }
870
871 /* Check 'a' (clear as we go). */
872 for (LinkData &node : el_store_a->verts) {
874 /* Finish clearing 'a', leave tag clean. */
875 LinkData *remaining_node = &node;
876 while ((remaining_node = remaining_node->next)) {
878 }
879 return true;
880 }
882 }
883 return false;
884}
885
886} // namespace blender
#define BLI_ASSERT_UNIT_V3(v)
#define BLI_FOREACH_SPARSE_RANGE(src, dst, i)
Read Blender memory allocation and freeing.
#define BM_EDGELOOP_IS_CLOSED
#define NODE_AS_CO(n)
#define NODE_AS_V(n)
#define EDGELOOP_EPS
#define BM_EDGELOOP_IS_CLOSED_JUNCTION
#define EDGE_SPLIT(node_copy, node_other)
#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)
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
bool contains(const Key &key) const
Definition BLI_set.hh:310
bool add(const Key &key)
Definition BLI_set.hh:248
bool is_empty() const
Definition BLI_set.hh:614
#define FLT_MAX
#define abs
VecBase< float, 3 > cross(VecOp< float, 3 >, VecOp< float, 3 >) RET
void split(const std::string &s, const char delim, std::vector< std::string > &tokens)
Definition abc_util.cc:68
BMesh Iterators.
bool BM_edgeloop_calc_normal_aligned(BMesh *, BMEdgeLoopStore *el_store, const float no_align[3])
BMEdgeLoopStore * BM_edgeloop_from_verts(BMVert **v_arr, const int v_arr_tot, bool is_closed)
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
ListBaseT< LinkData > * BM_edgeloop_verts_get(BMEdgeLoopStore *el_store)
int BM_mesh_edgeloops_find(BMesh *bm, ListBaseT< BMEdgeLoopStore > *r_eloops, FunctionRef< bool(BMEdge *)> test_fn, const BMEdgeLoopFind_Params *params)
bool BM_edgeloop_is_closed_junction(BMEdgeLoopStore *el_store)
MINLINE bool is_finite_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
void BM_mesh_edgeloops_calc_center(BMesh *bm, ListBaseT< BMEdgeLoopStore > *eloops)
void BM_edgeloop_flip(BMesh *, BMEdgeLoopStore *el_store)
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
void BM_edgeloop_expand(BMesh *bm, BMEdgeLoopStore *el_store, int el_store_len, bool split, Set< BMEdge * > *split_edges)
void BLI_addhead(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:98
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition stack.cc:99
void BM_mesh_edgeloops_free(ListBaseT< BMEdgeLoopStore > *eloops)
void BM_edgeloop_free(BMEdgeLoopStore *el_store)
void void void void void void BLI_duplicatelist(ListBase *dst, const ListBase *src) ATTR_NONNULL(1
Definition listbase.cc:834
void BM_mesh_edgeloops_calc_normal(BMesh *bm, ListBaseT< BMEdgeLoopStore > *eloops)
static int bm_vert_other_tag(BMVert *v, BMVert *v_prev, BMEdge **r_e)
const float * BM_edgeloop_normal_get(BMEdgeLoopStore *el_store)
bool BM_mesh_edgeloops_find_path(BMesh *bm, ListBaseT< BMEdgeLoopStore > *r_eloops, FunctionRef< bool(BMEdge *)> test_fn, BMVert *v_src, BMVert *v_dst)
ATTR_WARN_UNUSED_RESULT 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()
MINLINE void mul_v3_fl(float r[3], float f)
bool BM_edgeloop_is_closed(BMEdgeLoopStore *el_store)
static bool bm_loop_path_build_step(BLI_mempool *vs_pool, ListBaseT< VertStep > *lb, const int dir, BMVert *v_match[2])
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
void * BLI_pophead(ListBase *listbase) ATTR_NONNULL(1)
Definition listbase.cc:259
void BM_mesh_edgeloops_calc_normal_aligned(BMesh *bm, ListBaseT< BMEdgeLoopStore > *eloops, const float no_align[3])
int BM_edgeloop_length_get(BMEdgeLoopStore *el_store)
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
const float * BM_edgeloop_center_get(BMEdgeLoopStore *el_store)
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
void BM_edgeloop_edges_get(BMEdgeLoopStore *el_store, BMEdge **e_arr)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void BLI_remlink(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:138
size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:231
void BLI_insertlinkafter(ListBase *listbase, void *vprevlink, void *vnewlink) ATTR_NONNULL(1)
Definition listbase.cc:339
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
void BM_edgeloop_calc_center(BMesh *, BMEdgeLoopStore *el_store)
MINLINE void negate_v3(float r[3])
void void void void void void void BLI_listbase_reverse(ListBase *lb) ATTR_NONNULL(1)
Definition listbase.cc:850
static void vs_add(BLI_mempool *vs_pool, ListBaseT< VertStep > *lb, BMVert *v, BMEdge *e_prev, const int iter_tot)
BMEdgeLoopStore * BM_edgeloop_copy(BMEdgeLoopStore *el_store)
MINLINE void zero_v3(float r[3])
void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink) ATTR_NONNULL(1)
Definition listbase.cc:378
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
MINLINE float normalize_v3(float n[3])
MINLINE void add_v3_v3(float r[3], const float a[3])
static bool bm_vert_is_junction(BMVert *v)
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
bool BM_edgeloop_overlap_check(BMEdgeLoopStore *el_store_a, BMEdgeLoopStore *el_store_b)
void BLI_stack_pop_n_reverse(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL()
Definition stack.cc:160
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:118
@ BLI_MEMPOOL_NOP
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL()
Definition stack.cc:135
static bool bm_loop_build(BMEdgeLoopStore *el_store, BMVert *v_prev, BMVert *v, int dir, const Set< BMVert * > *vert_junctions)
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
BLI_Stack * BLI_stack_new(size_t elem_size, const char *description) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:85
bool BM_edgeloop_calc_normal(BMesh *, BMEdgeLoopStore *el_store)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
@ BM_ELEM_INTERNAL_TAG
void BM_mesh_edgeloops_calc_order(BMesh *, ListBaseT< BMEdgeLoopStore > *eloops, const bool use_normals)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
#define fabsf
ListBaseT< LinkData > verts
struct BMEdge * e
struct LinkData * prev
struct LinkData * next