Blender V5.3
bmesh_polygon_edgenet.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
11// #define DEBUG_PRINT
12
13#include <algorithm>
14
15#include "MEM_guardedalloc.h"
16
17#include "BLI_kdopbvh.hh"
18#include "BLI_linklist_stack.hh"
19#include "BLI_math_geom_c.hh"
20#include "BLI_math_matrix_c.hh"
21#include "BLI_math_vector_c.hh"
23#include "BLI_memarena.hh"
24#include "BLI_sort_utils.hh"
26#include "BLI_vector.hh"
27
28#include "BKE_customdata.hh"
29
30#include "bmesh.hh"
32
33namespace blender {
34
35/* -------------------------------------------------------------------- */
45
46/* NOTE: All these flags _must_ be cleared on exit. */
47
48/* face is a part of the edge-net (including the original face we're splitting) */
49#define FACE_NET _FLAG_WALK
50/* edge is a part of the edge-net we're filling */
51#define EDGE_NET _FLAG_WALK
52/* tag verts we've visit */
53#define VERT_VISIT _FLAG_WALK
54#define VERT_IN_QUEUE _FLAG_WALK_ALT
55
56struct VertOrder {
57 float angle;
59};
60
62{
63 uint count = 0;
64 BMLoop *l;
65
66 if ((l = e->l)) {
67 do {
69 count++;
70 }
71 } while ((l = l->radial_next) != e->l);
72 }
73 return count;
74}
75
77{
78 BMLoop *l;
79
80 if ((l = e->l)) {
81 do {
83 return l;
84 }
85 } while ((l = l->radial_next) != e->l);
86 }
87 return nullptr;
88}
89
90static void normalize_v2_m3_v3v3(float out[2],
91 const float axis_mat[3][3],
92 const float v1[3],
93 const float v2[3])
94{
95 float dir[3];
96 sub_v3_v3v3(dir, v1, v2);
97 mul_v2_m3v3(out, axis_mat, dir);
99}
100
106 const float face_normal[3],
107 const float face_normal_matrix[3][3],
108 BMEdge *e_pair[2])
109{
110 /* Always find one boundary edge (to determine winding)
111 * and one wire (if available), otherwise another boundary.
112 */
113
114 /* detect winding */
115 BMLoop *l_walk;
116 bool swap;
117
118 BLI_SMALLSTACK_DECLARE(edges_boundary, BMEdge *);
119 BLI_SMALLSTACK_DECLARE(edges_wire, BMEdge *);
120 int edges_boundary_len = 0;
121 int edges_wire_len = 0;
122
123 {
124 BMEdge *e, *e_first;
125 e = e_first = v_init->e;
126 do {
128 const uint count = bm_edge_flagged_radial_count(e);
129 if (count == 1) {
130 BLI_SMALLSTACK_PUSH(edges_boundary, e);
131 edges_boundary_len++;
132 }
133 else if (count == 0) {
134 BLI_SMALLSTACK_PUSH(edges_wire, e);
135 edges_wire_len++;
136 }
137 }
138 } while ((e = BM_DISK_EDGE_NEXT(e, v_init)) != e_first);
139 }
140
141 /* first edge should always be boundary */
142 if (edges_boundary_len == 0) {
143 return false;
144 }
145 e_pair[0] = static_cast<BMEdge *>(BLI_SMALLSTACK_POP(edges_boundary));
146
147 /* use to hold boundary OR wire edges */
148 BLI_SMALLSTACK_DECLARE(edges_search, BMEdge *);
149
150 /* attempt one boundary and one wire, or 2 boundary */
151 if (edges_wire_len == 0) {
152 if (edges_boundary_len > 1) {
153 e_pair[1] = static_cast<BMEdge *>(BLI_SMALLSTACK_POP(edges_boundary));
154
155 if (edges_boundary_len > 2) {
156 BLI_SMALLSTACK_SWAP(edges_search, edges_boundary);
157 }
158 }
159 else {
160 /* one boundary and no wire */
161 return false;
162 }
163 }
164 else {
165 e_pair[1] = static_cast<BMEdge *>(BLI_SMALLSTACK_POP(edges_wire));
166 if (edges_wire_len > 1) {
167 BLI_SMALLSTACK_SWAP(edges_search, edges_wire);
168 }
169 }
170
171 /* if we swapped above, search this list for the best edge */
172 if (!BLI_SMALLSTACK_IS_EMPTY(edges_search)) {
173 /* find the best edge in 'edge_list' to use for 'e_pair[1]' */
174 const BMVert *v_prev = BM_edge_other_vert(e_pair[0], v_init);
175 const BMVert *v_next = BM_edge_other_vert(e_pair[1], v_init);
176
177 float dir_prev[2], dir_next[2];
178
179 normalize_v2_m3_v3v3(dir_prev, face_normal_matrix, v_prev->co, v_init->co);
180 normalize_v2_m3_v3v3(dir_next, face_normal_matrix, v_next->co, v_init->co);
181 float angle_best_cos = dot_v2v2(dir_next, dir_prev);
182
183 BMEdge *e;
184 while ((e = static_cast<BMEdge *>(BLI_SMALLSTACK_POP(edges_search)))) {
185 v_next = BM_edge_other_vert(e, v_init);
186 float dir_test[2];
187
188 normalize_v2_m3_v3v3(dir_test, face_normal_matrix, v_next->co, v_init->co);
189 const float angle_test_cos = dot_v2v2(dir_prev, dir_test);
190
191 if (angle_test_cos > angle_best_cos) {
192 angle_best_cos = angle_test_cos;
193 e_pair[1] = e;
194 }
195 }
196 }
197
198 /* flip based on winding */
199 l_walk = bm_edge_flagged_radial_first(e_pair[0]);
200 swap = false;
201 if (face_normal == l_walk->f->no) {
202 swap = !swap;
203 }
204 if (l_walk->v != v_init) {
205 swap = !swap;
206 }
207 if (swap) {
208 std::swap(e_pair[0], e_pair[1]);
209 }
210
211 return true;
212}
213
223{
224 int edges_boundary_len = 0;
225 int edges_wire_len = 0;
226
227 {
228 BMEdge *e, *e_first;
229 e = e_first = v_init->e;
230 do {
232 const uint count = bm_edge_flagged_radial_count(e);
233 if (count == 1) {
234 edges_boundary_len++;
235 }
236 else if (count == 0) {
237 edges_wire_len++;
238 }
239 }
240 } while ((e = BM_DISK_EDGE_NEXT(e, v_init)) != e_first);
241 }
242
243 /* first edge should always be boundary */
244 if (edges_boundary_len == 0) {
245 return false;
246 }
247
248 /* attempt one boundary and one wire, or 2 boundary */
249 if (edges_wire_len == 0) {
250 if (edges_boundary_len >= 2) {
251 /* pass */
252 }
253 else {
254 /* one boundary and no wire */
255 return false;
256 }
257 }
258 else {
259 /* pass */
260 }
261
262 return true;
263}
264
266 const float face_normal[3],
267 /* cache to avoid realloc every time */
268 VertOrder *edge_order,
269 const uint edge_order_len,
270 BMEdge *e_pair[2])
271{
272 UNUSED_VARS_NDEBUG(edge_order_len);
273
274/* fast-path for the common case (avoid push-pop).
275 * Also avoids tagging as visited since we know we
276 * can't reach these verts some other way */
277#define USE_FASTPATH_NOFORK
278
279 BMVert *v;
280 BMVert *v_dst;
281 bool found = false;
282
283 VertOrder *eo;
284 STACK_DECLARE(edge_order);
285
286 /* store visited verts so we can clear the visit flag after execution */
287 BLI_SMALLSTACK_DECLARE(vert_visit, BMVert *);
288
289 /* likely this will stay very small
290 * all verts pushed into this stack _must_ have their previous edges set! */
291 BLI_SMALLSTACK_DECLARE(vert_stack, BMVert *);
292 BLI_SMALLSTACK_DECLARE(vert_stack_next, BMVert *);
293
294 STACK_INIT(edge_order, edge_order_len);
295
296 /* start stepping */
297 v = BM_edge_other_vert(e_pair[0], v_init);
298 v->e = e_pair[0];
299 BLI_SMALLSTACK_PUSH(vert_stack, v);
300
301 v_dst = BM_edge_other_vert(e_pair[1], v_init);
302
303#ifdef DEBUG_PRINT
304 printf("%s: vert (search) %d\n", __func__, BM_elem_index_get(v_init));
305#endif
306
307 /* This loop will keep stepping over the best possible edge,
308 * in most cases it finds the direct route to close the face.
309 *
310 * In cases where paths can't be closed,
311 * alternatives are stored in the 'vert_stack'.
312 */
313 while ((v = static_cast<BMVert *>(BLI_SMALLSTACK_POP_EX(vert_stack, vert_stack_next)))) {
314#ifdef USE_FASTPATH_NOFORK
315 walk_nofork:
316#else
317 BLI_SMALLSTACK_PUSH(vert_visit, v);
319#endif
320
321 BLI_assert(STACK_SIZE(edge_order) == 0);
322
323 /* check if we're done! */
324 if (v == v_dst) {
325 found = true;
326 goto finally;
327 }
328
329 BMEdge *e_next, *e_first;
330 e_first = v->e;
331 e_next = BM_DISK_EDGE_NEXT(e_first, v); /* always skip this verts edge */
332
333 /* in rare cases there may be edges with a single connecting vertex */
334 if (e_next != e_first) {
335 do {
336 if (BM_ELEM_API_FLAG_TEST(e_next, EDGE_NET) && (bm_edge_flagged_radial_count(e_next) < 2))
337 {
338 BMVert *v_next;
339
340 v_next = BM_edge_other_vert(e_next, v);
341 BLI_assert(v->e != e_next);
342
343#ifdef DEBUG_PRINT
344 /* indent and print */
345 {
346 BMVert *_v = v;
347 do {
348 printf(" ");
349 } while ((_v = BM_edge_other_vert(_v->e, _v)) != v_init);
350 printf("vert %d -> %d (add=%d)\n",
352 BM_elem_index_get(v_next),
353 BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT) == 0);
354 }
355#endif
356
357 if (!BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT)) {
358 eo = STACK_PUSH_RET_PTR(edge_order);
359 eo->v = v_next;
360
361 v_next->e = e_next;
362 }
363 }
364 } while ((e_next = BM_DISK_EDGE_NEXT(e_next, v)) != e_first);
365 }
366
367#ifdef USE_FASTPATH_NOFORK
368 if (STACK_SIZE(edge_order) == 1) {
369 eo = STACK_POP_PTR(edge_order);
370 v = eo->v;
371
372 goto walk_nofork;
373 }
374#endif
375
376 /* sort by angle if needed */
377 if (STACK_SIZE(edge_order) > 1) {
378 uint j;
379 BMVert *v_prev = BM_edge_other_vert(v->e, v);
380
381 for (j = 0; j < STACK_SIZE(edge_order); j++) {
383 v_prev->co, v->co, edge_order[j].v->co, face_normal);
384 }
385 qsort(edge_order, STACK_SIZE(edge_order), sizeof(VertOrder), BLI_sortutil_cmp_float_reverse);
386
387#ifdef USE_FASTPATH_NOFORK
388 /* only tag forks */
389 BLI_SMALLSTACK_PUSH(vert_visit, v);
391#endif
392 }
393
394 while ((eo = STACK_POP_PTR(edge_order))) {
395 BLI_SMALLSTACK_PUSH(vert_stack_next, eo->v);
396 }
397
398 if (!BLI_SMALLSTACK_IS_EMPTY(vert_stack_next)) {
399 BLI_SMALLSTACK_SWAP(vert_stack, vert_stack_next);
400 }
401 }
402
403finally:
404 /* clear flag for next execution */
405 while ((v = static_cast<BMVert *>(BLI_SMALLSTACK_POP(vert_visit)))) {
407 }
408
409 return found;
410
411#undef USE_FASTPATH_NOFORK
412}
413
415 const float face_normal[3],
416 const float face_normal_matrix[3][3],
417 /* cache to avoid realloc every time */
418 VertOrder *edge_order,
419 const uint edge_order_len,
420 BMVert **face_verts,
421 BMEdge **face_edges,
422 int *r_face_verts_len,
423 bool *r_check_face_exists)
424{
425 BMEdge *e_pair[2];
426
427 if (!bm_face_split_edgenet_find_loop_pair(v_init, face_normal, face_normal_matrix, e_pair)) {
428 return false;
429 }
430
431 BLI_assert((bm_edge_flagged_radial_count(e_pair[0]) == 1) ||
432 (bm_edge_flagged_radial_count(e_pair[1]) == 1));
433
435 v_init, face_normal, edge_order, edge_order_len, e_pair))
436 {
437 return false;
438 }
439
440 /* Skip redundant checks for existing faces if *any* edges are wire. */
441 bool check_face_exists = true;
442
443 BMVert *v = BM_edge_other_vert(e_pair[1], v_init);
444 int i = 0;
445 face_verts[i] = v_init;
446 face_edges[i] = e_pair[1];
447 if (check_face_exists && BM_edge_is_wire(face_edges[i])) {
448 check_face_exists = false;
449 }
450 i++;
451
452 do {
453 face_verts[i] = v;
454 face_edges[i] = v->e;
455 if (check_face_exists && BM_edge_is_wire(face_edges[i])) {
456 check_face_exists = false;
457 }
458 i++;
459 } while ((v = BM_edge_other_vert(v->e, v)) != v_init);
460
461 if (i < 3) {
462 return false;
463 }
464
465#ifndef NDEBUG
466 for (int j = 0, j_prev = i - 1; j < i; j_prev = j++) {
467 BLI_assert(face_edges[j_prev] == BM_edge_exists(face_verts[j], face_verts[j_prev]));
468 }
469#endif
470
471 *r_face_verts_len = i;
472
473 *r_check_face_exists = check_face_exists;
474 return true;
475}
476
478 BMesh *bm, BMFace *f, BMEdge **edge_net, const int edge_net_len, Vector<BMFace *> *r_face_arr)
479{
480 /* re-use for new face verts */
481 BMVert **face_verts;
482 BMEdge **face_edges;
483 int face_verts_len;
484
485 BMVert **vert_queue;
486 STACK_DECLARE(vert_queue);
487 int i;
488
489 VertOrder *edge_order;
490 const uint edge_order_len = edge_net_len + 2;
491
492 BMVert *v;
493
494 BMLoop *l_iter, *l_first;
495
496 if (!edge_net_len) {
497 if (r_face_arr) {
498 r_face_arr->clear_and_shrink();
499 }
500 return false;
501 }
502
503 /* These arrays used to be stack memory, however they can be
504 * large for single faces with complex edge-nets, see: #65980. */
505
506 /* over-alloc (probably 2-4 is only used in most cases), for the biggest-fan */
507 edge_order = MEM_new_array_uninitialized<VertOrder>(edge_order_len, __func__);
508
509 /* use later */
510 face_verts = MEM_new_array_uninitialized<BMVert *>(edge_net_len + f->len, __func__);
511 face_edges = MEM_new_array_uninitialized<BMEdge *>(edge_net_len + f->len, __func__);
512
513 vert_queue = MEM_new_array_uninitialized<BMVert *>(edge_net_len + f->len, __func__);
514 STACK_INIT(vert_queue, f->len + edge_net_len);
515
518
519#ifndef NDEBUG
520 for (i = 0; i < edge_net_len; i++) {
521 BLI_assert(BM_ELEM_API_FLAG_TEST(edge_net[i], EDGE_NET) == 0);
522 BLI_assert(BM_edge_in_face(edge_net[i], f) == false);
523 }
524 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
525 do {
527 } while ((l_iter = l_iter->next) != l_first);
528#endif
529
530 /* NOTE: 'VERT_IN_QUEUE' is often not needed at all,
531 * however in rare cases verts are added multiple times to the queue,
532 * that on its own is harmless but in _very_ rare cases,
533 * the queue will overflow its maximum size,
534 * so we better be strict about this! see: #51539 */
535
536 for (i = 0; i < edge_net_len; i++) {
537 BM_ELEM_API_FLAG_ENABLE(edge_net[i], EDGE_NET);
538 BM_ELEM_API_FLAG_DISABLE(edge_net[i]->v1, VERT_IN_QUEUE);
540 }
541 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
542 do {
545 } while ((l_iter = l_iter->next) != l_first);
546
547 float face_normal_matrix[3][3];
548 axis_dominant_v3_to_m3(face_normal_matrix, f->no);
549
550 /* any vert can be used to begin with */
551 STACK_PUSH(vert_queue, l_first->v);
553
554 Vector<BMFace *> face_arr;
555 while ((v = STACK_POP(vert_queue))) {
556 bool check_face_exists = false;
559 f->no,
560 face_normal_matrix,
561 edge_order,
562 edge_order_len,
563 face_verts,
564 face_edges,
565 &face_verts_len,
566 &check_face_exists))
567 {
568 BMFace *f_new = nullptr;
569
570 if (check_face_exists && BM_face_exists(face_verts, face_verts_len)) [[unlikely]] {
571 /* Should only happen in unexpected/degenerate cases, see: #150360. */
572 }
573 else {
574 BLI_assert(!BM_face_exists(face_verts, face_verts_len));
575 f_new = BM_face_create(bm, face_verts, face_edges, face_verts_len, f, BM_CREATE_NOP);
576 }
577 for (i = 0; i < edge_net_len; i++) {
579 }
580
581 if (f_new) {
582 BLI_assert(f != f_new);
583 face_arr.append(f_new);
584 copy_v3_v3(f_new->no, f->no);
585
586 /* warning, normally don't do this,
587 * its needed for mesh intersection - which tracks face-sides based on selection */
588 f_new->head.hflag = f->head.hflag;
589 if (f->head.hflag & BM_ELEM_SELECT) {
590 bm->totfacesel++;
591 }
592
594
595 /* add new verts to keep finding loops for
596 * (verts between boundary and manifold edges) */
597 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
598 do {
599 /* Avoid adding to queue multiple times (not common but happens). */
600 if (!BM_ELEM_API_FLAG_TEST(l_iter->v, VERT_IN_QUEUE) &&
602 {
603 STACK_PUSH(vert_queue, l_iter->v);
605 }
606 } while ((l_iter = l_iter->next) != l_first);
607 }
608 }
609 }
610
612 /* reuse VERT_VISIT here to tag vert's already interpolated */
613 BMIter iter;
614 BMLoop *l_other;
615
616 /* See: #BM_loop_interp_from_face for similar logic. */
620 void **blocks = blocks_buf.data();
621 float (*cos_2d)[2] = reinterpret_cast<float (*)[2]>(cos_2d_buf.data());
622 float axis_mat[3][3];
623 float co[2];
624
625 /* interior loops */
626 axis_dominant_v3_to_m3(axis_mat, f->no);
627
628 /* first simply copy from existing face */
629 i = 0;
630 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
631 do {
632 BM_ITER_ELEM (l_other, &iter, l_iter->v, BM_LOOPS_OF_VERT) {
633 if ((l_other->f != f) && BM_ELEM_API_FLAG_TEST(l_other->f, FACE_NET)) {
634 CustomData_bmesh_copy_block(bm->ldata, l_iter->head.data, &l_other->head.data);
635 }
636 }
637 /* tag not to interpolate */
639
640 mul_v2_m3v3(cos_2d[i], axis_mat, l_iter->v->co);
641 blocks[i] = l_iter->head.data;
642
643 } while ((void)i++, (l_iter = l_iter->next) != l_first);
644
645 for (i = 0; i < edge_net_len; i++) {
646 BM_ITER_ELEM (v, &iter, edge_net[i], BM_VERTS_OF_EDGE) {
648 BMIter liter;
649
651
652 /* interpolate this loop, then copy to the rest */
653 l_first = nullptr;
654
655 BM_ITER_ELEM (l_iter, &liter, v, BM_LOOPS_OF_VERT) {
656 if (BM_ELEM_API_FLAG_TEST(l_iter->f, FACE_NET)) {
657 if (l_first == nullptr) {
658 mul_v2_m3v3(co, axis_mat, v->co);
659 interp_weights_poly_v2(w.data(), cos_2d, f->len, co);
661 &bm->ldata, (const void **)blocks, w.data(), f->len, l_iter->head.data);
662 l_first = l_iter;
663 }
664 else {
665 CustomData_bmesh_copy_block(bm->ldata, l_first->head.data, &l_iter->head.data);
666 }
667 }
668 }
669 }
670 }
671 }
672 }
673
674 /* cleanup */
675 for (i = 0; i < edge_net_len; i++) {
677 /* from interp only */
678 BM_ELEM_API_FLAG_DISABLE(edge_net[i]->v1, VERT_VISIT);
680 }
681 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
682 do {
684 /* from interp only */
686 } while ((l_iter = l_iter->next) != l_first);
687
688 if (!face_arr.is_empty()) {
689 bmesh_face_swap_data(f, face_arr[0]);
690 BM_face_kill(bm, face_arr[0]);
691 face_arr[0] = f;
692 }
693 else {
695 }
696
697 for (BMFace *face : face_arr) {
699 }
700
701 if (r_face_arr) {
702 *r_face_arr = std::move(face_arr);
703 }
704
705 MEM_delete(edge_order);
706 MEM_delete(face_verts);
707 MEM_delete(face_edges);
708 MEM_delete(vert_queue);
709
710 return true;
711}
712
713#undef FACE_NET
714#undef VERT_VISIT
715#undef EDGE_NET
716
718
719/* -------------------------------------------------------------------- */
732
733#define USE_PARTIAL_CONNECT
734
735#define VERT_IS_VALID BM_ELEM_INTERNAL_TAG
736
737/* can be X or Y */
738#define SORT_AXIS 0
739
741 const BMVert *v_a,
742 const BMVert *v_b,
743 float r_isect[2])
744{
745 /* This bias seems like it could be too large,
746 * mostly its not needed, see #52329 for example where it is. */
747 const float endpoint_bias = 1e-4f;
749 v_a->co, v_b->co, e->v1->co, e->v2->co, endpoint_bias, r_isect) == 1) &&
750 ((e->v1 != v_a) && (e->v2 != v_a) && (e->v1 != v_b) && (e->v2 != v_b)));
751}
752
753BLI_INLINE int axis_pt_cmp(const float pt_a[2], const float pt_b[2])
754{
755 if (pt_a[0] < pt_b[0]) {
756 return -1;
757 }
758 if (pt_a[0] > pt_b[0]) {
759 return 1;
760 }
761 if (pt_a[1] < pt_b[1]) {
762 return -1;
763 }
764 if (pt_a[1] > pt_b[1]) {
765 return 1;
766 }
767 return 0;
768}
769
776 LinkNode edge_links; /* keep first */
778
779 /* Set the following vars once we have >1 groups */
780
781 /* when an edge in a previous group connects to this one,
782 * so there's no need to create one pointing back. */
784
785 /* verts in the group which has the lowest & highest values,
786 * the lower vertex is connected to the first edge */
787 struct {
788 BMVert *min, *max;
789 /* used for sorting only */
790 float min_axis[2];
791 float max_axis[2];
793};
794
795static int group_min_cmp_fn(const void *p1, const void *p2)
796{
797 const EdgeGroupIsland *g1 = *static_cast<EdgeGroupIsland **>(const_cast<void *>(p1));
798 const EdgeGroupIsland *g2 = *static_cast<EdgeGroupIsland **>(const_cast<void *>(p2));
799 /* min->co[SORT_AXIS] hasn't been applied yet */
800 int test = axis_pt_cmp(g1->vert_span.min_axis, g2->vert_span.min_axis);
801 if (test == 0) [[unlikely]] {
802 test = axis_pt_cmp(g1->vert_span.max_axis, g2->vert_span.max_axis);
803 }
804 return test;
805}
806
816
824
825static void bvhtree_test_edges_isect_2d_vert_cb(void *user_data,
826 int index,
827 const BVHTreeRay * /*ray*/,
828 BVHTreeRayHit *hit)
829{
831 const BMEdge *e = data->edge_arr[index];
832 const int v1_index = BM_elem_index_get(e->v1);
833 float co_isect[2];
834
835 if (edge_isect_verts_point_2d(e, data->v_origin, data->v_other, co_isect)) {
836 const float t = line_point_factor_v2(co_isect, data->v_origin->co, data->v_other->co);
837 const float dist_new = data->dist_orig * t;
838 /* avoid float precision issues, possible this is greater,
839 * check above zero to allow some overlap
840 * (and needed for partial-connect which will overlap vertices) */
841 if ((dist_new < hit->dist) && (dist_new > 0.0f)) [[likely]] {
842 /* v1/v2 will both be in the same group */
843 if (v1_index < int(data->vert_range[0]) || v1_index >= int(data->vert_range[1])) {
844 hit->dist = dist_new;
845 hit->index = index;
846 }
847 }
848 }
849}
850
851static void bvhtree_test_edges_isect_2d_ray_cb(void *user_data,
852 int index,
853 const BVHTreeRay *ray,
854 BVHTreeRayHit *hit)
855{
856 Edges_VertRay_BVHTreeTest *data = static_cast<Edges_VertRay_BVHTreeTest *>(user_data);
857 const BMEdge *e = data->edge_arr[index];
858
859 /* direction is normalized, so this will be the distance */
860 float dist_new;
862 data->v_origin->co, ray->direction, e->v1->co, e->v2->co, &dist_new, nullptr))
863 {
864 /* avoid float precision issues, possible this is greater,
865 * check above zero to allow some overlap
866 * (and needed for partial-connect which will overlap vertices) */
867 if (dist_new < hit->dist && (dist_new > 0.0f)) [[likely]] {
868 if (e->v1 != data->v_origin && e->v2 != data->v_origin) {
869 const int v1_index = BM_elem_index_get(e->v1);
870 /* v1/v2 will both be in the same group */
871 if (v1_index < int(data->vert_range[0]) || v1_index >= int(data->vert_range[1])) {
872 hit->dist = dist_new;
873 hit->index = index;
874 }
875 }
876 }
877 }
878}
879
896
898 BMVert *v_origin,
899 BMVert *v_other)
900{
901 int index;
902
903 BVHTreeRayHit hit = {0};
904 float dir[3];
905
906 sub_v2_v2v2(dir, v_other->co, v_origin->co);
907 dir[2] = 0.0f;
908 hit.index = -1;
909 hit.dist = normalize_v2(dir);
910
911 Edges_VertVert_BVHTreeTest user_data = {0};
912 user_data.dist_orig = hit.dist;
913 user_data.edge_arr = args->edge_arr;
914 user_data.v_origin = v_origin;
915 user_data.v_other = v_other;
916 user_data.vert_range = args->vert_range;
917
919 v_origin->co,
920 dir,
921 0.0f,
922 &hit,
924 &user_data,
925 0);
926
927 BMEdge *e_hit = (index != -1) ? args->edge_arr[index] : nullptr;
928
929 /* check existing connections (no spatial optimization here since we're continually adding). */
930 if (index == -1) [[likely]] {
931 float t_best = 1.0f;
932 for (uint i = 0; i < args->edge_arr_new_len; i++) {
933 float co_isect[2];
934 if (edge_isect_verts_point_2d(args->edge_arr_new[i], v_origin, v_other, co_isect))
935 [[unlikely]]
936 {
937 const float t_test = line_point_factor_v2(co_isect, v_origin->co, v_other->co);
938 if (t_test < t_best) {
939 t_best = t_test;
940
941 e_hit = args->edge_arr_new[i];
942 }
943 }
944 }
945 }
946
947 return e_hit;
948}
949
955 BMVert *v_origin,
956 const float dir[3])
957{
958 int index;
959 BVHTreeRayHit hit = {0};
960
962
963 hit.index = -1;
965
966 Edges_VertRay_BVHTreeTest user_data = {nullptr};
967 user_data.edge_arr = args->edge_arr;
968 user_data.v_origin = v_origin;
969 user_data.vert_range = args->vert_range;
970
972 v_origin->co,
973 dir,
974 0.0f,
975 &hit,
977 &user_data,
978 0);
979
980 BMEdge *e_hit = (index != -1) ? args->edge_arr[index] : nullptr;
981
982 /* check existing connections (no spatial optimization here since we're continually adding). */
983 if (index != -1) [[likely]] {
984 for (uint i = 0; i < args->edge_arr_new_len; i++) {
985 BMEdge *e = args->edge_arr_new[i];
986 float dist_new;
987 if (isect_ray_seg_v2(v_origin->co, dir, e->v1->co, e->v2->co, &dist_new, nullptr)) {
988 if (e->v1 != v_origin && e->v2 != v_origin) {
989 /* avoid float precision issues, possible this is greater */
990 if (dist_new < hit.dist) [[likely]] {
991 hit.dist = dist_new;
992
993 e_hit = args->edge_arr_new[i];
994 }
995 }
996 }
997 }
998 }
999
1000 return e_hit;
1001}
1002
1004 BMVert *v_origin,
1005 /* false = negative, true = positive */
1006 bool direction_sign)
1007{
1021
1022 float dir[3] = {0, 0, 0};
1023 dir[SORT_AXIS] = direction_sign ? 1.0f : -1.0f;
1024 BMEdge *e_hit = test_edges_isect_2d_ray(args, v_origin, dir);
1025 BMVert *v_other = nullptr;
1026
1027 if (e_hit) {
1028 BMVert *v_other_fallback = nullptr;
1029
1030 BLI_SMALLSTACK_DECLARE(vert_search, BMVert *);
1031
1032 /* ensure we never add verts multiple times (not all that likely - but possible) */
1033 BLI_SMALLSTACK_DECLARE(vert_blacklist, BMVert *);
1034
1035 do {
1036 BMVert *v_pair[2];
1037 /* ensure the closest vertex is popped back off the stack first */
1038 if (len_squared_v2v2(v_origin->co, e_hit->v1->co) >
1039 len_squared_v2v2(v_origin->co, e_hit->v2->co))
1040 {
1041 ARRAY_SET_ITEMS(v_pair, e_hit->v1, e_hit->v2);
1042 }
1043 else {
1044 ARRAY_SET_ITEMS(v_pair, e_hit->v2, e_hit->v1);
1045 }
1046
1047 for (int j = 0; j < 2; j++) {
1048 BMVert *v_iter = v_pair[j];
1049 if (BM_elem_flag_test(v_iter, VERT_IS_VALID)) {
1050 if (direction_sign ? (v_iter->co[SORT_AXIS] > v_origin->co[SORT_AXIS]) :
1051 (v_iter->co[SORT_AXIS] < v_origin->co[SORT_AXIS]))
1052 {
1053 BLI_SMALLSTACK_PUSH(vert_search, v_iter);
1054 BLI_SMALLSTACK_PUSH(vert_blacklist, v_iter);
1056 }
1057 }
1058 }
1059 v_other_fallback = v_other;
1060
1061 } while ((v_other = static_cast<BMVert *>(BLI_SMALLSTACK_POP(vert_search))) &&
1062 (e_hit = test_edges_isect_2d_vert(args, v_origin, v_other)));
1063
1064 if (v_other == nullptr) {
1065#ifdef DEBUG_PRINT
1066 printf("Using fallback\n");
1067#endif
1068 v_other = v_other_fallback;
1069 }
1070
1071 /* reset the blacklist flag, for future use */
1072 BMVert *v;
1073 while ((v = static_cast<BMVert *>(BLI_SMALLSTACK_POP(vert_blacklist)))) {
1075 }
1076 }
1077
1078 /* if we reach this line, v_other is either the best vertex or its nullptr */
1079 return v_other ? BM_elem_index_get(v_other) : -1;
1080}
1081
1086#ifdef USE_PARTIAL_CONNECT
1087
1092static bool test_tagged_and_notface(BMEdge *e, void *fptr)
1093{
1094 BMFace *f = static_cast<BMFace *>(fptr);
1096}
1097
1106{
1107 /* -------------------------------------------------------------------- */
1108 /* Initial check that we may be a delimiting vert (keep this fast) */
1109
1110 /* initial check - see if we have 3+ flagged edges attached to 'v_delimit'
1111 * if not, we can early exit */
1112 LinkNode *e_delimit_list = nullptr;
1113 uint e_delimit_list_len = 0;
1114
1115# define EDGE_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
1116# define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
1117
1118# define FOREACH_VERT_EDGE(v_, e_, body_) \
1119 { \
1120 BMEdge *e_ = v_->e; \
1121 do { \
1122 body_ \
1123 } while ((e_ = BM_DISK_EDGE_NEXT(e_, v_)) != v_->e); \
1124 } \
1125 ((void)0)
1126
1127 /* start with face edges, since we need to split away wire-only edges */
1128 BMEdge *e_face_init = nullptr;
1129
1130 FOREACH_VERT_EDGE(v_delimit, e_iter, {
1131 if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) {
1133 BLI_linklist_prepend_alloca(&e_delimit_list, e_iter);
1134 e_delimit_list_len++;
1135 if (e_iter->l != nullptr && BM_edge_in_face(e_iter, f)) {
1136 e_face_init = e_iter;
1137 }
1138 }
1139 });
1140
1141 /* skip typical edge-chain verts */
1142 if (e_delimit_list_len <= 2) [[likely]] {
1143 return nullptr;
1144 }
1145
1146 /* -------------------------------------------------------------------- */
1147 /* Complicated stuff starts now! */
1148
1149 /* Store connected vertices for restoring the flag */
1150 LinkNode *vert_stack = nullptr;
1151 BLI_linklist_prepend_alloca(&vert_stack, v_delimit);
1153
1154 /* Walk the net... */
1155 {
1156 BLI_SMALLSTACK_DECLARE(search, BMVert *);
1157 BMVert *v_other = BM_edge_other_vert(e_face_init ? e_face_init : v_delimit->e, v_delimit);
1158
1159 BLI_SMALLSTACK_PUSH(search, v_other);
1160 if (BM_elem_flag_test(v_other, VERT_NOT_IN_STACK)) {
1162 BLI_linklist_prepend_alloca(&vert_stack, v_other);
1163 }
1164
1165 while ((v_other = static_cast<BMVert *>(BLI_SMALLSTACK_POP(search)))) {
1167 BMEdge *e_iter = v_other->e;
1168 do {
1169 BMVert *v_step = BM_edge_other_vert(e_iter, v_other);
1170 if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) {
1171 if (BM_elem_flag_test(v_step, VERT_NOT_IN_STACK)) {
1173 BLI_SMALLSTACK_PUSH(search, v_step);
1174 BLI_linklist_prepend_alloca(&vert_stack, v_step);
1175 }
1176 }
1177 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_other)) != v_other->e);
1178 }
1179 }
1180
1181 /* Detect if this is a delimiter
1182 * by checking if we didn't walk any of edges connected to 'v_delimit'. */
1183 bool is_delimit = false;
1184 FOREACH_VERT_EDGE(v_delimit, e_iter, {
1185 BMVert *v_step = BM_edge_other_vert(e_iter, v_delimit);
1186 if (BM_elem_flag_test(v_step, VERT_NOT_IN_STACK) && !BM_edge_in_face(e_iter, f)) {
1187 is_delimit = true; /* if one vertex is valid - we have a mix */
1188 }
1189 else {
1190 /* match the vertex flag (only for edges around 'v_delimit') */
1192 }
1193 });
1194
1195# undef FOREACH_VERT_EDGE
1196
1197 /* Execute the split */
1198 BMVert *v_split = nullptr;
1199 if (is_delimit) {
1200 v_split = BM_vert_create(bm, v_delimit->co, nullptr, eBMCreateFlag(0));
1203
1204 BLI_assert(v_delimit->e != nullptr);
1205
1206/* Degenerate, avoid eternal loop, see: #59074. */
1207# if 0
1208 BLI_assert(v_split->e != nullptr);
1209# else
1210 if (v_split->e == nullptr) [[unlikely]] {
1211 BM_vert_kill(bm, v_split);
1212 v_split = nullptr;
1213 }
1214# endif
1215 }
1216
1217 /* Restore flags */
1218 do {
1220 } while ((vert_stack = vert_stack->next));
1221
1222 do {
1223 BM_elem_flag_enable((BMEdge *)e_delimit_list->link, EDGE_NOT_IN_STACK);
1224 } while ((e_delimit_list = e_delimit_list->next));
1225
1226# undef EDGE_NOT_IN_STACK
1227# undef VERT_NOT_IN_STACK
1228
1229 return v_split;
1230}
1231
1235static bool bm_vert_partial_connect_check_overlap(const int *remap,
1236 const int v_a_index,
1237 const int v_b_index)
1238{
1239 /* Connected to each other. */
1240 if ((remap[v_a_index] == v_b_index) || (remap[v_b_index] == v_a_index)) [[unlikely]] {
1241 return true;
1242 }
1243 return false;
1244}
1245
1246#endif /* USE_PARTIAL_CONNECT */
1247
1249 BMFace *f,
1250 BMEdge **edge_net_init,
1251 const uint edge_net_init_len,
1252 bool use_partial_connect,
1253 MemArena *mem_arena,
1254 BMEdge ***r_edge_net_new,
1255 uint *r_edge_net_new_len)
1256{
1257 /* -------------------------------------------------------------------- */
1269
1270 const uint edge_arr_len = uint(edge_net_init_len) + uint(f->len);
1271 BMEdge **edge_arr = static_cast<BMEdge **>(
1272 BLI_memarena_alloc(mem_arena, sizeof(*edge_arr) * edge_arr_len));
1273 bool ok = false;
1274 uint edge_net_new_len = uint(edge_net_init_len);
1275
1276 memcpy(edge_arr, edge_net_init, sizeof(*edge_arr) * size_t(edge_net_init_len));
1277
1278/* _must_ clear on exit */
1279#define EDGE_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
1280#define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
1281
1282 {
1283 uint i = edge_net_init_len;
1284 BMLoop *l_iter, *l_first;
1285 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1286 do {
1289 edge_arr[i++] = l_iter->e;
1290 } while ((l_iter = l_iter->next) != l_first);
1291 BLI_assert(i == edge_arr_len);
1292 }
1293
1294 for (uint i = 0; i < edge_arr_len; i++) {
1296 BM_elem_flag_enable(edge_arr[i]->v1, VERT_NOT_IN_STACK);
1298 }
1299
1300#ifdef USE_PARTIAL_CONNECT
1301 /* Split-out delimiting vertices */
1302 struct TempVertPair {
1303 TempVertPair *next;
1304 BMVert *v_temp;
1305 BMVert *v_orig;
1306 };
1307
1308 struct {
1309 TempVertPair *list;
1310 uint len;
1311 int *remap; /* temp -> orig mapping */
1312 } temp_vert_pairs = {nullptr};
1313
1314 if (use_partial_connect) {
1315 for (uint i = 0; i < edge_net_init_len; i++) {
1316 for (uint j = 0; j < 2; j++) {
1317 BMVert *v_delimit = (&edge_arr[i]->v1)[j];
1318 BMVert *v_other;
1319
1320 /* NOTE: remapping will _never_ map a vertex to an already mapped vertex. */
1321 while ((v_other = bm_face_split_edgenet_partial_connect(bm, v_delimit, f))) [[unlikely]] {
1322 TempVertPair *tvp = static_cast<TempVertPair *>(
1323 BLI_memarena_alloc(mem_arena, sizeof(*tvp)));
1324 tvp->next = temp_vert_pairs.list;
1325 tvp->v_orig = v_delimit;
1326 tvp->v_temp = v_other;
1327 temp_vert_pairs.list = tvp;
1328 temp_vert_pairs.len++;
1329 }
1330 }
1331 }
1332
1333 if (temp_vert_pairs.len == 0) {
1334 use_partial_connect = false;
1335 }
1336 }
1337#endif /* USE_PARTIAL_CONNECT */
1338
1339 uint group_arr_len = 0;
1340 LinkNode *group_head = nullptr;
1341 {
1342 /* scan 'edge_arr' backwards so the outer face boundary is handled first
1343 * (since its likely to be the largest) */
1344 uint edge_index = (edge_arr_len - 1);
1345 uint edge_in_group_tot = 0;
1346
1347 BLI_SMALLSTACK_DECLARE(vstack, BMVert *);
1348
1349 while (true) {
1350 LinkNode *edge_links = nullptr;
1351 uint unique_verts_in_group = 0, unique_edges_in_group = 0;
1352
1353 /* list of groups */
1354 BLI_assert(BM_elem_flag_test(edge_arr[edge_index]->v1, VERT_NOT_IN_STACK));
1355 BLI_SMALLSTACK_PUSH(vstack, edge_arr[edge_index]->v1);
1356 BM_elem_flag_disable(edge_arr[edge_index]->v1, VERT_NOT_IN_STACK);
1357
1358 BMVert *v_iter;
1359 while ((v_iter = static_cast<BMVert *>(BLI_SMALLSTACK_POP(vstack)))) {
1360 unique_verts_in_group++;
1361
1362 BMEdge *e_iter = v_iter->e;
1363 do {
1364 if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) {
1366 unique_edges_in_group++;
1367
1368 BLI_linklist_prepend_arena(&edge_links, e_iter, mem_arena);
1369
1370 BMVert *v_other = BM_edge_other_vert(e_iter, v_iter);
1371 if (BM_elem_flag_test(v_other, VERT_NOT_IN_STACK)) {
1372 BLI_SMALLSTACK_PUSH(vstack, v_other);
1374 }
1375 }
1376 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_iter)) != v_iter->e);
1377 }
1378
1379 EdgeGroupIsland *g = static_cast<EdgeGroupIsland *>(
1380 BLI_memarena_alloc(mem_arena, sizeof(*g)));
1381 g->vert_len = unique_verts_in_group;
1382 g->edge_len = unique_edges_in_group;
1383 edge_in_group_tot += unique_edges_in_group;
1384
1385 BLI_linklist_prepend_nlink(&group_head, edge_links, reinterpret_cast<LinkNode *>(g));
1386
1387 group_arr_len++;
1388
1389 if (edge_in_group_tot == edge_arr_len) {
1390 break;
1391 }
1392
1393 /* skip edges in the stack */
1394 while (BM_elem_flag_test(edge_arr[edge_index], EDGE_NOT_IN_STACK) == false) {
1395 BLI_assert(edge_index != 0);
1396 edge_index--;
1397 }
1398 }
1399 }
1400
1401 /* Declare here because of `goto` below. */
1402 BMEdge **edge_net_new = nullptr;
1403 BVHTree *bvhtree = nullptr;
1404 float (*vert_coords_backup)[3] = nullptr;
1405 uint *verts_group_table = nullptr;
1406 BMVert **vert_arr = nullptr;
1407 uint vert_arr_len = 0;
1408 EdgeGroupIsland **group_arr = nullptr;
1409
1410 /* single group - no holes */
1411 if (group_arr_len == 1) {
1412 goto finally;
1413 }
1414
1415 /* -------------------------------------------------------------------- */
1416 /* Previous checks need to be kept fast, since they will run very often,
1417 * now we know there are holes, so calculate a spatial lookup info and
1418 * other per-group data.
1419 */
1420
1421 float axis_mat[3][3];
1422 axis_dominant_v3_to_m3(axis_mat, f->no);
1423
1424#define VERT_IN_ARRAY BM_ELEM_INTERNAL_TAG
1425 /* Any destructive edits are going to render the UV selection dirty,
1426 * the flags use here is acceptable. */
1427#define EDGE_IS_NEW BM_ELEM_SELECT_UV
1428
1429 group_arr = static_cast<EdgeGroupIsland **>(
1430 BLI_memarena_alloc(mem_arena, sizeof(*group_arr) * group_arr_len));
1431 /* sort groups by lowest value vertex */
1432 {
1433 /* fill 'groups_arr' in reverse order so the boundary face is first */
1434 EdgeGroupIsland **group_arr_p = &group_arr[group_arr_len];
1435
1436 for (EdgeGroupIsland *g = static_cast<EdgeGroupIsland *>(static_cast<void *>(group_head)); g;
1437 g = reinterpret_cast<EdgeGroupIsland *>(g->edge_links.next))
1438 {
1439 LinkNode *edge_links = static_cast<LinkNode *>(g->edge_links.link);
1440
1441 /* init with *any* different verts */
1442 g->vert_span.min = (static_cast<BMEdge *>(edge_links->link))->v1;
1443 g->vert_span.max = (static_cast<BMEdge *>(edge_links->link))->v2;
1444 float min_axis[2] = {FLT_MAX, FLT_MAX};
1445 float max_axis[2] = {-FLT_MAX, -FLT_MAX};
1446
1447 do {
1448 BMEdge *e = static_cast<BMEdge *>(edge_links->link);
1450
1451 for (int j = 0; j < 2; j++) {
1452 BMVert *v_iter = (&e->v1)[j];
1453 BLI_assert(v_iter->head.htype == BM_VERT);
1454 /* ideally we could use 'v_iter->co[SORT_AXIS]' here,
1455 * but we need to sort the groups before setting the vertex array order */
1456 const float axis_value[2] = {
1457#if SORT_AXIS == 0
1458 dot_m3_v3_row_x(axis_mat, v_iter->co),
1459 dot_m3_v3_row_y(axis_mat, v_iter->co),
1460#else
1461 dot_m3_v3_row_y(axis_mat, v_iter->co),
1462 dot_m3_v3_row_x(axis_mat, v_iter->co),
1463#endif
1464 };
1465
1466 if (axis_pt_cmp(axis_value, min_axis) == -1) {
1467 g->vert_span.min = v_iter;
1468 copy_v2_v2(min_axis, axis_value);
1469 }
1470 if (axis_pt_cmp(axis_value, max_axis) == 1) {
1471 g->vert_span.max = v_iter;
1472 copy_v2_v2(max_axis, axis_value);
1473 }
1474 }
1475 } while ((edge_links = edge_links->next));
1476
1477 copy_v2_v2(g->vert_span.min_axis, min_axis);
1478 copy_v2_v2(g->vert_span.max_axis, max_axis);
1479
1480 g->has_prev_edge = false;
1481
1482 vert_arr_len += g->vert_len;
1483
1484 *(--group_arr_p) = g;
1485 }
1486 }
1487
1488 qsort(group_arr, group_arr_len, sizeof(*group_arr), group_min_cmp_fn);
1489
1490 /* we don't know how many unique verts there are connecting the edges, so over-alloc */
1491 vert_arr = static_cast<BMVert **>(
1492 BLI_memarena_alloc(mem_arena, sizeof(*vert_arr) * vert_arr_len));
1493 /* map vertex -> group index */
1494 verts_group_table = static_cast<uint *>(
1495 BLI_memarena_alloc(mem_arena, sizeof(*verts_group_table) * vert_arr_len));
1496
1497 vert_coords_backup = static_cast<float (*)[3]>(
1498 BLI_memarena_alloc(mem_arena, sizeof(*vert_coords_backup) * vert_arr_len));
1499
1500 {
1501 /* relative location, for higher precision calculations */
1502 const float f_co_ref[3] = {UNPACK3(BM_FACE_FIRST_LOOP(f)->v->co)};
1503
1504 int v_index = 0; /* global vert index */
1505 for (uint g_index = 0; g_index < group_arr_len; g_index++) {
1506 LinkNode *edge_links = static_cast<LinkNode *>(group_arr[g_index]->edge_links.link);
1507 do {
1508 BMEdge *e = static_cast<BMEdge *>(edge_links->link);
1509 for (int j = 0; j < 2; j++) {
1510 BMVert *v_iter = (&e->v1)[j];
1511 if (!BM_elem_flag_test(v_iter, VERT_IN_ARRAY)) {
1513
1514 /* not nice, but alternatives aren't much better :S */
1515 {
1516 copy_v3_v3(vert_coords_backup[v_index], v_iter->co);
1517
1518 /* for higher precision */
1519 sub_v3_v3(v_iter->co, f_co_ref);
1520
1521 float co_2d[2];
1522 mul_v2_m3v3(co_2d, axis_mat, v_iter->co);
1523 v_iter->co[0] = co_2d[0];
1524 v_iter->co[1] = co_2d[1];
1525 v_iter->co[2] = 0.0f;
1526 }
1527
1528 BM_elem_index_set(v_iter, v_index); /* set_dirty */
1529
1530 vert_arr[v_index] = v_iter;
1531 verts_group_table[v_index] = g_index;
1532 v_index++;
1533 }
1534 }
1535 } while ((edge_links = edge_links->next));
1536 }
1537 }
1538
1540
1541 /* Now create BVH tree.
1542 *
1543 * Note that a large epsilon is used because meshes with dimensions of around 100+ need it.
1544 * see #52329. */
1545 bvhtree = BLI_bvhtree_new(edge_arr_len, 1e-4f, 8, 8);
1546 for (uint i = 0; i < edge_arr_len; i++) {
1547 const float e_cos[2][3] = {
1548 {UNPACK2(edge_arr[i]->v1->co), 0.0f},
1549 {UNPACK2(edge_arr[i]->v2->co), 0.0f},
1550 };
1551 BLI_bvhtree_insert(bvhtree, i, reinterpret_cast<const float *>(e_cos), 2);
1552 }
1553 BLI_bvhtree_balance(bvhtree);
1554
1555#ifdef USE_PARTIAL_CONNECT
1556 if (use_partial_connect) {
1557 /* needs to be done once the vertex indices have been written into */
1558 temp_vert_pairs.remap = static_cast<int *>(
1559 BLI_memarena_alloc(mem_arena, sizeof(*temp_vert_pairs.remap) * vert_arr_len));
1560 std::fill_n(temp_vert_pairs.remap, vert_arr_len, -1);
1561
1562 TempVertPair *tvp = temp_vert_pairs.list;
1563 do {
1564 temp_vert_pairs.remap[BM_elem_index_get(tvp->v_temp)] = BM_elem_index_get(tvp->v_orig);
1565 } while ((tvp = tvp->next));
1566 }
1567#endif /* USE_PARTIAL_CONNECT */
1568
1569 /* Create connections between groups */
1570
1571 /* may be an over-alloc, but not by much */
1572 edge_net_new_len = uint(edge_net_init_len) + ((group_arr_len - 1) * 2);
1573 edge_net_new = static_cast<BMEdge **>(
1574 BLI_memarena_alloc(mem_arena, sizeof(*edge_net_new) * edge_net_new_len));
1575 memcpy(edge_net_new, edge_net_init, sizeof(*edge_net_new) * size_t(edge_net_init_len));
1576
1577 {
1578 uint edge_net_new_index = edge_net_init_len;
1579 /* start-end of the verts in the current group */
1580
1581 uint vert_range[2];
1582
1583 vert_range[0] = 0;
1584 vert_range[1] = group_arr[0]->vert_len;
1585
1587 args.bvhtree = bvhtree;
1588
1589 /* use the new edge array so we can scan edges which have been added */
1590 args.edge_arr = edge_arr;
1591 args.edge_arr_len = edge_arr_len;
1592
1593 /* we only want to check newly created edges */
1594 args.edge_arr_new = edge_net_new + edge_net_init_len;
1595 args.edge_arr_new_len = 0;
1596
1597 args.vert_range = vert_range;
1598
1599 for (uint g_index = 1; g_index < group_arr_len; g_index++) {
1600 EdgeGroupIsland *g = group_arr[g_index];
1601
1602 /* The range of verts this group uses in 'verts_arr' (not including the last index). */
1603 vert_range[0] = vert_range[1];
1604 vert_range[1] += g->vert_len;
1605
1606 if (g->has_prev_edge == false) {
1607 BMVert *v_origin = g->vert_span.min;
1608 /* Index of BMVert for the edge group connection with `v_origin`. */
1609 const int index_other = bm_face_split_edgenet_find_connection(&args, v_origin, false);
1610 // BLI_assert(index_other >= 0 && index_other < int(vert_arr_len));
1611
1612 /* only for degenerate geometry */
1613 if (index_other != -1) {
1614#ifdef USE_PARTIAL_CONNECT
1615 if ((use_partial_connect == false) ||
1617 temp_vert_pairs.remap, BM_elem_index_get(v_origin), index_other) == false))
1618#endif
1619 {
1620 BMVert *v_end = vert_arr[index_other];
1621 const int totedge_prev = bm->totedge;
1622 /* Doubles should not be present in the common case,
1623 * see the complex test file from: #150360. */
1624 BMEdge *e_new = edge_net_new[edge_net_new_index] = BM_edge_create(
1625 bm, v_origin, v_end, nullptr, BM_CREATE_NO_DOUBLE);
1626 if ((edge_net_new[edge_net_new_index] = e_new)) {
1627#ifdef USE_PARTIAL_CONNECT
1628 BM_elem_index_set(e_new, edge_net_new_index);
1629#endif
1630 BM_elem_flag_set(e_new, EDGE_IS_NEW, bm->totedge != totedge_prev);
1631 edge_net_new_index++;
1632 args.edge_arr_new_len++;
1633 }
1634 }
1635 }
1636 }
1637
1638 {
1639 BMVert *v_origin = g->vert_span.max;
1640 /* Index of BMVert for the edge group connection with `v_origin`. */
1641 const int index_other = bm_face_split_edgenet_find_connection(&args, v_origin, true);
1642 // BLI_assert(index_other >= 0 && index_other < int(vert_arr_len));
1643
1644 /* only for degenerate geometry */
1645 if (index_other != -1) {
1646#ifdef USE_PARTIAL_CONNECT
1647 if ((use_partial_connect == false) ||
1649 temp_vert_pairs.remap, BM_elem_index_get(v_origin), index_other) == false))
1650#endif
1651 {
1652 BMVert *v_end = vert_arr[index_other];
1653 const int totedge_prev = bm->totedge;
1654 /* Doubles should not be present in the common case,
1655 * see the complex test file from: #150360. */
1656 BMEdge *e_new = edge_net_new[edge_net_new_index] = BM_edge_create(
1657 bm, v_origin, v_end, nullptr, BM_CREATE_NO_DOUBLE);
1658 if ((edge_net_new[edge_net_new_index] = e_new)) {
1659#ifdef USE_PARTIAL_CONNECT
1660 BM_elem_index_set(e_new, edge_net_new_index);
1661#endif
1662 BM_elem_flag_set(e_new, EDGE_IS_NEW, bm->totedge != totedge_prev);
1663 edge_net_new_index++;
1664 args.edge_arr_new_len++;
1665 }
1666 }
1667
1668 /* tell the 'next' group it doesn't need to create its own back-link */
1669 uint g_index_other = verts_group_table[index_other];
1670 group_arr[g_index_other]->has_prev_edge = true;
1671 }
1672 }
1673 }
1674 BLI_assert(edge_net_new_len >= edge_net_new_index);
1675 edge_net_new_len = edge_net_new_index;
1676 }
1677
1678 BLI_bvhtree_free(bvhtree);
1679
1680 *r_edge_net_new = edge_net_new;
1681 *r_edge_net_new_len = edge_net_new_len;
1682 ok = true;
1683
1684 for (uint i = 0; i < vert_arr_len; i++) {
1685 copy_v3_v3(vert_arr[i]->co, vert_coords_backup[i]);
1686 }
1687
1688finally:
1689
1690#ifdef USE_PARTIAL_CONNECT
1691 /* don't free 'vert_temp_pair_list', its part of the arena */
1692 if (use_partial_connect) {
1693
1694/* Sanity check: ensure we don't have connecting edges before splicing begins. */
1695# ifndef NDEBUG
1696 {
1697 TempVertPair *tvp = temp_vert_pairs.list;
1698 do {
1699 /* We must _never_ create connections here
1700 * (in case the islands can't have a connection at all). */
1701 BLI_assert(BM_edge_exists(tvp->v_orig, tvp->v_temp) == nullptr);
1702 } while ((tvp = tvp->next));
1703 }
1704# endif
1705
1706 TempVertPair *tvp = temp_vert_pairs.list;
1707 do {
1708 /* its _very_ unlikely the edge exists,
1709 * however splicing may cause this. see: #48012 */
1710 if (!BM_edge_exists(tvp->v_orig, tvp->v_temp) &&
1711 !BM_vert_splice_check_double_face(tvp->v_orig, tvp->v_temp))
1712 {
1713 BM_vert_splice(bm, tvp->v_orig, tvp->v_temp);
1714 }
1715 } while ((tvp = tvp->next));
1716
1717 /* Remove edges which have become doubles since splicing vertices together,
1718 * its less trouble than detecting future-doubles on edge-creation.
1719 *
1720 * Only kill it when it was created here because an pre-existing edge may be
1721 * part of a face which should not be removed as part of this isolated cleanup.
1722 * Any other doubles which may exist are left as-is,
1723 * the caller is responsible for them, see #160601. */
1724 for (uint i = edge_net_init_len; i < edge_net_new_len; i++) {
1725 while (BM_edge_find_double(edge_net_new[i])) {
1726 if (BM_elem_flag_test(edge_net_new[i], EDGE_IS_NEW)) {
1727 BM_edge_kill(bm, edge_net_new[i]);
1728 }
1729 edge_net_new_len--;
1730 if (i == edge_net_new_len) {
1731 break;
1732 }
1733 edge_net_new[i] = edge_net_new[edge_net_new_len];
1734 }
1735 }
1736
1737 *r_edge_net_new_len = edge_net_new_len;
1738 }
1739#endif
1740
1741 for (uint i = 0; i < edge_arr_len; i++) {
1743 BM_elem_flag_disable(edge_arr[i]->v1, VERT_NOT_IN_STACK);
1745 }
1746
1747#undef VERT_IN_ARRAY
1748#undef EDGE_IS_NEW
1749#undef VERT_NOT_IN_STACK
1750#undef EDGE_NOT_IN_STACK
1751
1752 return ok;
1753}
1754
1755#undef SORT_AXIS
1756
1758
1759} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
#define BVH_RAYCAST_DIST_MAX
#define BLI_ASSERT_UNIT_V2(v)
#define STACK_POP(stack)
#define STACK_POP_PTR(stack)
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_PUSH_RET_PTR(stack)
#define STACK_INIT(stack, stack_num)
Read Blender memory allocation and freeing.
#define UNPACK2(a)
#define ARRAY_SET_ITEMS(...)
#define UNUSED_VARS_NDEBUG(...)
#define BLI_INLINE
#define UNPACK3(a)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_FACE_FIRST_LOOP(p)
#define VERT_VISIT
#define BM_elem_index_get(ele)
#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_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define EDGE_NET
#define EDGE_IS_NEW
#define VERT_NOT_IN_STACK
#define VERT_IS_VALID
#define SORT_AXIS
#define EDGE_NOT_IN_STACK
#define VERT_IN_QUEUE
#define FOREACH_VERT_EDGE(v_, e_, body_)
#define FACE_NET
#define VERT_IN_ARRAY
#define BM_ELEM_API_FLAG_DISABLE(element, f)
#define BM_ELEM_API_FLAG_TEST(element, f)
#define BM_ELEM_API_FLAG_ENABLE(element, f)
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
const T * data() const
Definition BLI_array.hh:323
void append(const T &value)
bool is_empty() const
void clear_and_shrink()
#define FLT_MAX
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static BMVert * bm_face_split_edgenet_partial_connect(BMesh *bm, BMVert *v_delimit, BMFace *f)
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
bool isect_ray_seg_v2(const float ray_origin[2], const float ray_direction[2], const float v0[2], const float v1[2], float *r_lambda, float *r_u)
MINLINE float dot_m3_v3_row_y(const float M[3][3], const float a[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static bool bm_face_split_edgenet_find_loop_walk(BMVert *v_init, const float face_normal[3], VertOrder *edge_order, const uint edge_order_len, BMEdge *e_pair[2])
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void BM_vert_kill(BMesh *bm, BMVert *v)
static BMLoop * bm_edge_flagged_radial_first(BMEdge *e)
MINLINE void copy_v2_v2(float r[2], const float a[2])
void BLI_bvhtree_free(BVHTree *tree)
void CustomData_bmesh_interp(CustomData *data, const void **src_blocks, const float *weights, int count, void *dst_block)
int BLI_bvhtree_ray_cast_ex(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata, int flag)
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
static bool bm_vert_partial_connect_check_overlap(const int *remap, const int v_a_index, const int v_b_index)
int isect_seg_seg_v2_point_ex(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float endpoint_bias, float r_vi[2])
void BLI_bvhtree_balance(BVHTree *tree)
void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, struct MemArena *ma) ATTR_NONNULL(1
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
static void bvhtree_test_edges_isect_2d_vert_cb(void *user_data, int index, const BVHTreeRay *, BVHTreeRayHit *hit)
MINLINE float normalize_v2(float n[2])
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.
BMFace * BM_face_create(BMesh *bm, BMVert *const *verts, BMEdge *const *edges, const int len, const BMFace *f_example, const eBMCreateFlag create_flag)
void BM_vert_separate_tested_edges(BMesh *, BMVert *v_dst, BMVert *v_src, bool(*testfn)(BMEdge *, void *arg), void *arg)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static bool test_tagged_and_notface(BMEdge *e, void *fptr)
MINLINE void sub_v3_v3(float r[3], const float a[3])
@ BM_CREATE_NO_DOUBLE
Definition bmesh_core.hh:36
@ BM_CREATE_NOP
Definition bmesh_core.hh:34
float angle_signed_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT
void BM_edge_kill(BMesh *bm, BMEdge *e)
BMesh const char void * data
float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2])
void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) ATTR_NONNULL(1
static uint bm_edge_flagged_radial_count(BMEdge *e)
static BMEdge * test_edges_isect_2d_vert(const EdgeGroup_FindConnection_Args *args, BMVert *v_origin, BMVert *v_other)
static bool bm_face_split_edgenet_find_loop_pair_exists(BMVert *v_init)
MINLINE axis_t min_axis(axis_t a, axis_t b)
int BLI_sortutil_cmp_float_reverse(const void *a_, const void *b_)
Definition sort_utils.cc:41
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
MINLINE float dot_m3_v3_row_x(const float M[3][3], const float a[3]) ATTR_WARN_UNUSED_RESULT
bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
Splice Vert.
static int group_min_cmp_fn(const void *p1, const void *p2)
MINLINE float dot_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
void interp_weights_poly_v2(float w[], float v[][2], int n, const float co[2])
BMFace * BM_face_exists(BMVert *const *varr, int len)
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
static BMEdge * test_edges_isect_2d_ray(const EdgeGroup_FindConnection_Args *args, BMVert *v_origin, const float dir[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
BLI_INLINE bool edge_isect_verts_point_2d(const BMEdge *e, const BMVert *v_a, const BMVert *v_b, float r_isect[2])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
void BM_face_kill(BMesh *bm, BMFace *f)
bool BM_face_split_edgenet_connect_islands(BMesh *bm, BMFace *f, BMEdge **edge_net_init, const uint edge_net_init_len, bool use_partial_connect, MemArena *mem_arena, BMEdge ***r_edge_net_new, uint *r_edge_net_new_len)
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
static bool bm_face_split_edgenet_find_loop_pair(BMVert *v_init, const float face_normal[3], const float face_normal_matrix[3][3], BMEdge *e_pair[2])
bool BM_face_split_edgenet(BMesh *bm, BMFace *f, BMEdge **edge_net, const int edge_net_len, Vector< BMFace * > *r_face_arr)
BMEdge * BM_edge_find_double(BMEdge *e)
bool BM_vert_splice_check_double_face(BMVert *v_a, BMVert *v_b)
static void normalize_v2_m3_v3v3(float out[2], const float axis_mat[3][3], const float v1[3], const float v2[3])
bool CustomData_has_math(const CustomData *data)
MINLINE float len_squared_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
static int bm_face_split_edgenet_find_connection(const EdgeGroup_FindConnection_Args *args, BMVert *v_origin, bool direction_sign)
static void bvhtree_test_edges_isect_2d_ray_cb(void *user_data, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
@ BM_ELEM_INTERNAL_TAG
BLI_INLINE int axis_pt_cmp(const float pt_a[2], const float pt_b[2])
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.
void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
static bool bm_face_split_edgenet_find_loop(BMVert *v_init, const float face_normal[3], const float face_normal_matrix[3][3], VertOrder *edge_order, const uint edge_order_len, BMVert **face_verts, BMEdge **face_edges, int *r_face_verts_len, bool *r_check_face_exists)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define swap(a, b)
Definition sort.cc:61
struct BMLoop * next
struct BMEdge * e
struct BMVert * v
struct BMFace * f
struct BMEdge * e
struct blender::EdgeGroupIsland::@263354005325326233205312234055326163323057041077 vert_span
struct LinkNode * next
struct BMLoop * radial_next