Blender V5.3
bmesh_intersect.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
21
22#include <algorithm>
23
24#include "MEM_guardedalloc.h"
25
26#include "BLI_linklist.hh"
27#include "BLI_math_geom_c.hh"
28#include "BLI_math_vector_c.hh"
29#include "BLI_memarena.hh"
30#include "BLI_set.hh"
31#include "BLI_utildefines.hh"
32#include "BLI_vector.hh"
33
35
36#include "BLI_kdopbvh.hh"
37
38#include "bmesh.hh"
40
41#include "bmesh_intersect.hh" /* own include */
42
44
45#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
46
47namespace blender {
48
49/*
50 * Some of these depend on each other:
51 */
52
53/* splice verts into existing edges */
54#define USE_SPLICE
55/* split faces by intersecting edges */
56#define USE_NET
57/* split resulting edges */
58#define USE_SEPARATE
59/* remove verts created by intersecting triangles */
60#define USE_DISSOLVE
61/* detect isolated holes and fill them */
62#define USE_NET_ISLAND_CONNECT
63
64/* strict asserts that may fail in practice (handy for debugging cases which should succeed) */
65// #define USE_PARANOID
66/* use accelerated overlap check */
67#define USE_BVH
68
69// #define USE_DUMP
70
71static void tri_v3_scale(float v1[3], float v2[3], float v3[3], const float t)
72{
73 float p[3];
74
75 mid_v3_v3v3v3(p, v1, v2, v3);
76
77 interp_v3_v3v3(v1, p, v1, t);
78 interp_v3_v3v3(v2, p, v2, t);
79 interp_v3_v3v3(v3, p, v3, t);
80}
81
82#ifdef USE_DISSOLVE
83/* other edge when a vert only has 2 edges */
85{
88
89 if (v->e != e) {
90 return v->e;
91 }
92 return BM_DISK_EDGE_NEXT(v->e, v);
93}
94#endif
95
104
110
113 GHash *edgetri_cache; /* int[4]: BMVert */
114 GHash *edge_verts; /* BMEdge: LinkList(of verts), new and original edges */
115 GHash *face_edges; /* BMFace-index: LinkList(of edges), only original faces */
117 LinkNode *vert_dissolve; /* BMVert's */
118
120
122};
123
132
133static bool ghash_insert_link(GHash *gh, void *key, void *val, bool use_test, MemArena *mem_arena)
134{
135 void **ls_base_p;
136 LinkBase *ls_base;
137 LinkNode *ls;
138
139 if (!BLI_ghash_ensure_p(gh, key, &ls_base_p)) {
140 ls_base = static_cast<LinkBase *>(*ls_base_p = BLI_memarena_alloc(mem_arena,
141 sizeof(*ls_base)));
142 ls_base->list = nullptr;
143 ls_base->list_len = 0;
144 }
145 else {
146 ls_base = static_cast<LinkBase *>(*ls_base_p);
147 if (use_test && (BLI_linklist_index(ls_base->list, val) != -1)) {
148 return false;
149 }
150 }
151
152 ls = static_cast<LinkNode *>(BLI_memarena_alloc(mem_arena, sizeof(*ls)));
153 ls->next = ls_base->list;
154 ls->link = val;
155 ls_base->list = ls;
156 ls_base->list_len += 1;
157
158 return true;
159}
160
161struct VertSort {
162 float val;
164};
165
166#ifdef USE_SPLICE
167static void edge_verts_sort(const float co[3], LinkBase *v_ls_base)
168{
169 /* not optimal but list will be typically < 5 */
170 uint i;
172 LinkNode *node;
173
174 BLI_assert(v_ls_base->list_len > 1);
175
176 for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) {
177 BMVert *v = static_cast<BMVert *>(node->link);
179 vert_sort[i].val = len_squared_v3v3(co, v->co);
180 vert_sort[i].v = v;
181 }
182
183 std::ranges::sort(vert_sort, [](const VertSort &a, const VertSort &b) { return a.val < b.val; });
184
185 for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) {
186 node->link = vert_sort[i].v;
187 }
188}
189#endif
190
191static void edge_verts_add(ISectState *s, BMEdge *e, BMVert *v, const bool use_test)
192{
195 ghash_insert_link(s->edge_verts, static_cast<void *>(e), v, use_test, s->mem_arena);
196}
197
198static void face_edges_add(ISectState *s, const int f_index, BMEdge *e, const bool use_test)
199{
200 void *f_index_key = POINTER_FROM_INT(f_index);
202 BLI_assert(BM_edge_in_face(e, s->bm->ftable[f_index]) == false);
203 BLI_assert(BM_elem_index_get(s->bm->ftable[f_index]) == f_index);
204
205 ghash_insert_link(s->face_edges, f_index_key, e, use_test, s->mem_arena);
206}
207
208#ifdef USE_NET
210 BMFace *f,
211 LinkBase *e_ls_base,
212 bool use_island_connect,
213 bool use_partial_connect,
214 MemArena *mem_arena_edgenet)
215{
216 uint i;
217 uint edge_arr_len = e_ls_base->list_len;
218 /* NOTE: `edge_arr` pointer may be reassigned to arena memory below. */
219 Array<BMEdge *, BM_DEFAULT_TOPOLOGY_STACK_SIZE> edge_arr_buf(edge_arr_len);
220 BMEdge **edge_arr = edge_arr_buf.data();
221 LinkNode *node;
223
224 for (i = 0, node = e_ls_base->list; i < e_ls_base->list_len; i++, node = node->next) {
225 edge_arr[i] = static_cast<BMEdge *>(node->link);
226 }
227 BLI_assert(node == nullptr);
228
229# ifdef USE_DUMP
230 printf("# %s: %d %u\n", __func__, BM_elem_index_get(f), e_ls_base->list_len);
231# endif
232
233# ifdef USE_NET_ISLAND_CONNECT
234 if (use_island_connect) {
235 uint edge_arr_holes_len;
236 BMEdge **edge_arr_holes;
238 f,
239 edge_arr,
240 edge_arr_len,
241 use_partial_connect,
242 mem_arena_edgenet,
243 &edge_arr_holes,
244 &edge_arr_holes_len))
245 {
246 edge_arr_len = edge_arr_holes_len;
247 edge_arr = edge_arr_holes; /* owned by the arena */
248 }
249 }
250# else
251 UNUSED_VARS(use_island_connect, mem_arena_edgenet);
252# endif
253
254 BM_face_split_edgenet(bm, f, edge_arr, int(edge_arr_len), nullptr);
255}
256#endif
257
258#ifdef USE_DISSOLVE
268#endif
269
270static enum ISectType intersect_line_tri(const float p0[3],
271 const float p1[3],
272 const float *t_cos[3],
273 const float t_nor[3],
274 float r_ix[3],
275 const ISectEpsilon *e)
276{
277 float p_dir[3];
278 uint i_t0;
279 float fac;
280
281 sub_v3_v3v3(p_dir, p0, p1);
282 normalize_v3(p_dir);
283
284 for (i_t0 = 0; i_t0 < 3; i_t0++) {
285 const uint i_t1 = (i_t0 + 1) % 3;
286 float te_dir[3];
287
288 sub_v3_v3v3(te_dir, t_cos[i_t0], t_cos[i_t1]);
289 normalize_v3(te_dir);
290 if (fabsf(dot_v3v3(p_dir, te_dir)) >= 1.0f - e->eps) {
291 /* co-linear */
292 }
293 else {
294 float ix_pair[2][3];
295 int ix_pair_type;
296
297 ix_pair_type = isect_line_line_epsilon_v3(
298 p0, p1, t_cos[i_t0], t_cos[i_t1], ix_pair[0], ix_pair[1], 0.0f);
299
300 if (ix_pair_type != 0) {
301 if (ix_pair_type == 1) {
302 copy_v3_v3(ix_pair[1], ix_pair[0]);
303 }
304
305 if ((ix_pair_type == 1) || (len_squared_v3v3(ix_pair[0], ix_pair[1]) <= e->eps_margin_sq))
306 {
307 fac = line_point_factor_v3(ix_pair[1], t_cos[i_t0], t_cos[i_t1]);
308 if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
309 fac = line_point_factor_v3(ix_pair[0], p0, p1);
310 if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
311 copy_v3_v3(r_ix, ix_pair[0]);
312 return ISectType(IX_EDGE_TRI_EDGE0 + static_cast<enum ISectType>(i_t0));
313 }
314 }
315 }
316 }
317 }
318 }
319
320 /* check ray isn't planar with tri */
321 if (fabsf(dot_v3v3(p_dir, t_nor)) >= e->eps) {
323 p0, p1, t_cos[0], t_cos[1], t_cos[2], &fac, nullptr, 0.0f))
324 {
325 if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
326 interp_v3_v3v3(r_ix, p0, p1, fac);
327 if (std::min({len_squared_v3v3(t_cos[0], r_ix),
328 len_squared_v3v3(t_cos[1], r_ix),
329 len_squared_v3v3(t_cos[2], r_ix)}) >= e->eps_margin_sq)
330 {
331 return IX_EDGE_TRI;
332 }
333 }
334 }
335 }
336
337 /* r_ix may be unset */
338 return IX_NONE;
339}
340
342 BMVert *e_v0,
343 BMVert *e_v1,
344 BMVert *t[3],
345 const int t_index,
346 const float *t_cos[3],
347 const float t_nor[3],
348 enum ISectType *r_side)
349{
350 BMesh *bm = s->bm;
351 int k_arr[IX_TOT][4];
352 uint i;
353 const int ti[3] = {UNPACK3_EX(BM_elem_index_get, t, )};
354 float ix[3];
355
356 if (BM_elem_index_get(e_v0) > BM_elem_index_get(e_v1)) {
357 std::swap(e_v0, e_v1);
358 }
359
360#ifdef USE_PARANOID
361 BLI_assert(len_squared_v3v3(e_v0->co, t[0]->co) >= s->epsilon.eps_sq);
362 BLI_assert(len_squared_v3v3(e_v0->co, t[1]->co) >= s->epsilon.eps_sq);
363 BLI_assert(len_squared_v3v3(e_v0->co, t[2]->co) >= s->epsilon.eps_sq);
364 BLI_assert(len_squared_v3v3(e_v1->co, t[0]->co) >= s->epsilon.eps_sq);
365 BLI_assert(len_squared_v3v3(e_v1->co, t[1]->co) >= s->epsilon.eps_sq);
366 BLI_assert(len_squared_v3v3(e_v1->co, t[2]->co) >= s->epsilon.eps_sq);
367#endif
368
369#define KEY_SET(k, i0, i1, i2, i3) \
370 { \
371 (k)[0] = i0; \
372 (k)[1] = i1; \
373 (k)[2] = i2; \
374 (k)[3] = i3; \
375 } \
376 (void)0
377
378/* Order tri, then order (1-2, 2-3). */
379#define KEY_EDGE_TRI_ORDER(k) \
380 { \
381 if (k[2] > k[3]) { \
382 std::swap(k[2], k[3]); \
383 } \
384 if (k[0] > k[2]) { \
385 std::swap(k[0], k[2]); \
386 std::swap(k[1], k[3]); \
387 } \
388 } \
389 (void)0
390
391 KEY_SET(k_arr[IX_EDGE_TRI], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), t_index, -1);
392 /* need to order here */
393 KEY_SET(
394 k_arr[IX_EDGE_TRI_EDGE0], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[0], ti[1]);
395 KEY_SET(
396 k_arr[IX_EDGE_TRI_EDGE1], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[1], ti[2]);
397 KEY_SET(
398 k_arr[IX_EDGE_TRI_EDGE2], BM_elem_index_get(e_v0), BM_elem_index_get(e_v1), ti[2], ti[0]);
399
403
404#undef KEY_SET
405#undef KEY_EDGE_TRI_ORDER
406
407 for (i = 0; i < ARRAY_SIZE(k_arr); i++) {
408 BMVert *iv;
409
410 iv = static_cast<BMVert *>(BLI_ghash_lookup(s->edgetri_cache, k_arr[i]));
411
412 if (iv) {
413#ifdef USE_DUMP
414 printf("# cache hit (%d, %d, %d, %d)\n", UNPACK4(k_arr[i]));
415#endif
416 *r_side = static_cast<enum ISectType>(i);
417 return iv;
418 }
419 }
420
421 *r_side = intersect_line_tri(e_v0->co, e_v1->co, t_cos, t_nor, ix, &s->epsilon);
422 if (*r_side != IX_NONE) {
423 BMVert *iv;
424 BMEdge *e;
425#ifdef USE_DUMP
426 printf("# new vertex (%.6f, %.6f, %.6f) %d\n", UNPACK3(ix), *r_side);
427#endif
428
429#ifdef USE_PARANOID
432 BLI_assert(len_squared_v3v3(ix, t[0]->co) > s->epsilon.eps_sq);
433 BLI_assert(len_squared_v3v3(ix, t[1]->co) > s->epsilon.eps_sq);
434 BLI_assert(len_squared_v3v3(ix, t[2]->co) > s->epsilon.eps_sq);
435#endif
436 iv = BM_vert_create(bm, ix, nullptr, eBMCreateFlag(0));
437
438 e = BM_edge_exists(e_v0, e_v1);
439 if (e) {
440#ifdef USE_DUMP
441 printf("# adding to edge %d\n", BM_elem_index_get(e));
442#endif
443 edge_verts_add(s, e, iv, false);
444 }
445 else {
446#ifdef USE_DISSOLVE
447 vert_dissolve_add(s, iv);
448#endif
449 }
450
451 if ((*r_side >= IX_EDGE_TRI_EDGE0) && (*r_side <= IX_EDGE_TRI_EDGE2)) {
452 i = uint(*r_side - IX_EDGE_TRI_EDGE0);
453 e = BM_edge_exists(t[i], t[(i + 1) % 3]);
454 if (e) {
455 edge_verts_add(s, e, iv, false);
456 }
457 }
458
459 {
460 int *k = static_cast<int *>(BLI_memarena_alloc(s->mem_arena, sizeof(int[4])));
461 memcpy(k, k_arr[*r_side], sizeof(int[4]));
463 }
464
465 return iv;
466 }
467
468 *r_side = IX_NONE;
469
470 return nullptr;
471}
472
474 int (*test_fn)(BMFace *f, void *user_data);
476};
477
478static bool bm_loop_filter_fn(const BMLoop *l, void *user_data)
479{
481 return false;
482 }
483
484 if (l->radial_next != l) {
485 LoopFilterWrap *data = static_cast<LoopFilterWrap *>(user_data);
486 BMLoop *l_iter = l->radial_next;
487 const int face_side = data->test_fn(l->f, data->user_data);
488 do {
489 const int face_side_other = data->test_fn(l_iter->f, data->user_data);
490 if (face_side_other == -1) [[unlikely]] {
491 /* pass */
492 }
493 else if (face_side_other != face_side) {
494 return false;
495 }
496 } while ((l_iter = l_iter->radial_next) != l);
497 return true;
498 }
499 return false;
500}
501
506 int a_index,
507 int b_index,
508 const std::array<BMLoop *, 3> &a,
509 const std::array<BMLoop *, 3> &b,
510 bool no_shared)
511{
512 BMFace *f_a = a[0]->f;
513 BMFace *f_b = b[0]->f;
514 BMVert *fv_a[3] = {UNPACK3_EX(, a, ->v)};
515 BMVert *fv_b[3] = {UNPACK3_EX(, b, ->v)};
516 const float *f_a_cos[3] = {UNPACK3_EX(, fv_a, ->co)};
517 const float *f_b_cos[3] = {UNPACK3_EX(, fv_b, ->co)};
518 float f_a_nor[3];
519 float f_b_nor[3];
520 uint i;
521
522 /* should be enough but may need to bump */
523 BMVert *iv_ls_a[8];
524 BMVert *iv_ls_b[8];
525 STACK_DECLARE(iv_ls_a);
526 STACK_DECLARE(iv_ls_b);
527
528 if (no_shared) {
529 if (ELEM(fv_a[0], UNPACK3(fv_b)) || ELEM(fv_a[1], UNPACK3(fv_b)) ||
530 ELEM(fv_a[2], UNPACK3(fv_b))) [[unlikely]]
531 {
532 return;
533 }
534 }
535 else {
536 if (BM_face_share_edge_check(f_a, f_b)) [[unlikely]] {
537 return;
538 }
539 }
540
541 STACK_INIT(iv_ls_a, ARRAY_SIZE(iv_ls_a));
542 STACK_INIT(iv_ls_b, ARRAY_SIZE(iv_ls_b));
543
544#define VERT_VISIT_A _FLAG_WALK
545#define VERT_VISIT_B _FLAG_WALK_ALT
546
547#define STACK_PUSH_TEST_A(ele) \
548 if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_A) == 0) { \
549 BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_A); \
550 STACK_PUSH(iv_ls_a, ele); \
551 } \
552 ((void)0)
553
554#define STACK_PUSH_TEST_B(ele) \
555 if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_B) == 0) { \
556 BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_B); \
557 STACK_PUSH(iv_ls_b, ele); \
558 } \
559 ((void)0)
560
561 /* vert-vert
562 * --------- */
563 {
564 /* first check if any verts are touching
565 * (any case where we won't create new verts)
566 */
567 uint i_a;
568 for (i_a = 0; i_a < 3; i_a++) {
569 uint i_b;
570 for (i_b = 0; i_b < 3; i_b++) {
571 if (len_squared_v3v3(fv_a[i_a]->co, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
572#ifdef USE_DUMP
573 if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A) == 0) {
574 printf(" ('VERT-VERT-A') %u, %d),\n", i_a, BM_elem_index_get(fv_a[i_a]));
575 }
576 if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B) == 0) {
577 printf(" ('VERT-VERT-B') %u, %d),\n", i_b, BM_elem_index_get(fv_b[i_b]));
578 }
579#endif
580 STACK_PUSH_TEST_A(fv_a[i_a]);
581 STACK_PUSH_TEST_B(fv_b[i_b]);
582 }
583 }
584 }
585 }
586
587 /* vert-edge
588 * --------- */
589 {
590 uint i_a;
591 for (i_a = 0; i_a < 3; i_a++) {
592 if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A) == 0) {
593 uint i_b_e0;
594 for (i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
595 uint i_b_e1 = (i_b_e0 + 1) % 3;
596
597 if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) ||
598 BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B))
599 {
600 continue;
601 }
602
603 const float fac = line_point_factor_v3(
604 fv_a[i_a]->co, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co);
605 if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {
606 float ix[3];
607 interp_v3_v3v3(ix, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co, fac);
608 if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
609 BMEdge *e;
610 STACK_PUSH_TEST_B(fv_a[i_a]);
611 // STACK_PUSH_TEST_A(fv_a[i_a]);
612 e = BM_edge_exists(fv_b[i_b_e0], fv_b[i_b_e1]);
613#ifdef USE_DUMP
614 printf(" ('VERT-EDGE-A', %d, %d),\n",
615 BM_elem_index_get(fv_b[i_b_e0]),
616 BM_elem_index_get(fv_b[i_b_e1]));
617#endif
618 if (e) {
619#ifdef USE_DUMP
620 printf("# adding to edge %d\n", BM_elem_index_get(e));
621#endif
622 edge_verts_add(s, e, fv_a[i_a], true);
623 }
624 break;
625 }
626 }
627 }
628 }
629 }
630 }
631
632 {
633 uint i_b;
634 for (i_b = 0; i_b < 3; i_b++) {
635 if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B) == 0) {
636 uint i_a_e0;
637 for (i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
638 uint i_a_e1 = (i_a_e0 + 1) % 3;
639
640 if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) ||
641 BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A))
642 {
643 continue;
644 }
645
646 const float fac = line_point_factor_v3(
647 fv_b[i_b]->co, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co);
648 if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {
649 float ix[3];
650 interp_v3_v3v3(ix, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co, fac);
651 if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
652 BMEdge *e;
653 STACK_PUSH_TEST_A(fv_b[i_b]);
654 // STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
655 e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]);
656#ifdef USE_DUMP
657 printf(" ('VERT-EDGE-B', %d, %d),\n",
658 BM_elem_index_get(fv_a[i_a_e0]),
659 BM_elem_index_get(fv_a[i_a_e1]));
660#endif
661 if (e) {
662#ifdef USE_DUMP
663 printf("# adding to edge %d\n", BM_elem_index_get(e));
664#endif
665 edge_verts_add(s, e, fv_b[i_b], true);
666 }
667 break;
668 }
669 }
670 }
671 }
672 }
673 }
674
675 /* vert-tri
676 * -------- */
677 {
678
679 float t_scale[3][3];
680 uint i_a;
681
682 copy_v3_v3(t_scale[0], fv_b[0]->co);
683 copy_v3_v3(t_scale[1], fv_b[1]->co);
684 copy_v3_v3(t_scale[2], fv_b[2]->co);
685 tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x);
686
687 /* second check for verts intersecting the triangle */
688 for (i_a = 0; i_a < 3; i_a++) {
689 if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A)) {
690 continue;
691 }
692
693 float ix[3];
694 if (isect_point_tri_v3(fv_a[i_a]->co, UNPACK3(t_scale), ix)) {
695 if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
696 STACK_PUSH_TEST_A(fv_a[i_a]);
697 STACK_PUSH_TEST_B(fv_a[i_a]);
698#ifdef USE_DUMP
699 printf(" 'VERT TRI-A',\n");
700#endif
701 }
702 }
703 }
704 }
705
706 {
707 float t_scale[3][3];
708 uint i_b;
709
710 copy_v3_v3(t_scale[0], fv_a[0]->co);
711 copy_v3_v3(t_scale[1], fv_a[1]->co);
712 copy_v3_v3(t_scale[2], fv_a[2]->co);
713 tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x);
714
715 for (i_b = 0; i_b < 3; i_b++) {
716 if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B)) {
717 continue;
718 }
719
720 float ix[3];
721 if (isect_point_tri_v3(fv_b[i_b]->co, UNPACK3(t_scale), ix)) {
722 if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
723 STACK_PUSH_TEST_A(fv_b[i_b]);
724 STACK_PUSH_TEST_B(fv_b[i_b]);
725#ifdef USE_DUMP
726 printf(" 'VERT TRI-B',\n");
727#endif
728 }
729 }
730 }
731 }
732
733 if ((STACK_SIZE(iv_ls_a) >= 3) && (STACK_SIZE(iv_ls_b) >= 3)) {
734#ifdef USE_DUMP
735 printf("# OVERLAP\n");
736#endif
737 goto finally;
738 }
739
740 normal_tri_v3(f_a_nor, UNPACK3(f_a_cos));
741 normal_tri_v3(f_b_nor, UNPACK3(f_b_cos));
742
743 /* edge-tri & edge-edge
744 * -------------------- */
745 {
746 for (uint i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
747 uint i_a_e1 = (i_a_e0 + 1) % 3;
748 enum ISectType side;
749 BMVert *iv;
750
751 if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) ||
752 BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A))
753 {
754 continue;
755 }
756
758 s, fv_a[i_a_e0], fv_a[i_a_e1], fv_b, b_index, f_b_cos, f_b_nor, &side);
759 if (iv) {
762#ifdef USE_DUMP
763 printf(" ('EDGE-TRI-A', %d),\n", side);
764#endif
765 }
766 }
767
768 for (uint i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
769 uint i_b_e1 = (i_b_e0 + 1) % 3;
770 enum ISectType side;
771 BMVert *iv;
772
773 if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) ||
774 BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B))
775 {
776 continue;
777 }
778
780 s, fv_b[i_b_e0], fv_b[i_b_e1], fv_a, a_index, f_a_cos, f_a_nor, &side);
781 if (iv) {
784#ifdef USE_DUMP
785 printf(" ('EDGE-TRI-B', %d),\n", side);
786#endif
787 }
788 }
789 }
790
791 {
792 for (i = 0; i < 2; i++) {
793 BMVert **ie_vs;
794 BMFace *f;
795 bool ie_exists;
796 BMEdge *ie;
797
798 if (i == 0) {
799 if (STACK_SIZE(iv_ls_a) != 2) {
800 continue;
801 }
802 ie_vs = iv_ls_a;
803 f = f_a;
804 }
805 else {
806 if (STACK_SIZE(iv_ls_b) != 2) {
807 continue;
808 }
809 ie_vs = iv_ls_b;
810 f = f_b;
811 }
812
813 /* possible but unlikely we get this - for edge-edge intersection */
814 ie = BM_edge_exists(UNPACK2(ie_vs));
815 if (ie == nullptr) {
816 ie_exists = false;
817 /* one of the verts must be new if we are making an edge
818 * ...no, we need this in case 2x quads intersect at either ends.
819 * if not (ie_vs[0].index == -1 or ie_vs[1].index == -1):
820 * continue */
821 ie = BM_edge_create(s->bm, UNPACK2(ie_vs), nullptr, eBMCreateFlag(0));
822 s->wire_edges->add(ie);
823 }
824 else {
825 ie_exists = true;
826 /* may already exist */
827 s->wire_edges->add(ie);
828
829 if (BM_edge_in_face(ie, f)) {
830 continue;
831 }
832 }
833
834 face_edges_add(s, BM_elem_index_get(f), ie, ie_exists);
835 // BLI_assert(len(ie_vs) <= 2)
836 }
837 }
838
839finally:
840 for (i = 0; i < STACK_SIZE(iv_ls_a); i++) {
842 }
843 for (i = 0; i < STACK_SIZE(iv_ls_b); i++) {
845 }
846}
847
848#ifdef USE_BVH
849
854
855# ifdef USE_KDOPBVH_WATERTIGHT
856static const IsectRayPrecalc isect_precalc_x = {1, 2, 0, 0, 0, 1};
857# endif
858
859static void raycast_callback(void *userdata,
860 int index,
861 const BVHTreeRay *ray,
862 BVHTreeRayHit * /*hit*/)
863{
864 RaycastData *raycast_data = static_cast<RaycastData *>(userdata);
865 const float **looptris = raycast_data->looptris;
866 const float *v0 = looptris[index * 3 + 0];
867 const float *v1 = looptris[index * 3 + 1];
868 const float *v2 = looptris[index * 3 + 2];
869 float dist;
870
871 if (
873 isect_ray_tri_watertight_v3(ray->origin, &isect_precalc_x, v0, v1, v2, &dist, nullptr)
874# else
876 ray->origin, ray->direction, v0, v1, v2, &dist, nullptr, FLT_EPSILON)
877# endif
878 )
879 {
880 if (dist >= 0.0f) {
881# ifdef USE_DUMP
882 printf("%s:\n", __func__);
883 print_v3(" origin", ray->origin);
884 print_v3(" direction", ray->direction);
885 printf(" dist %f\n", dist);
886 print_v3(" v0", v0);
887 print_v3(" v1", v1);
888 print_v3(" v2", v2);
889# endif
890
891# ifdef USE_DUMP
892 printf("%s: Adding depth %f\n", __func__, dist);
893# endif
894 raycast_data->z_buffer->append(dist);
895 }
896 }
897}
898
899static int isect_bvhtree_point_v3(BVHTree *tree, const float **looptris, const float co[3])
900{
901 Vector<float, 64> z_buffer;
902
903 RaycastData raycast_data = {
904 looptris,
905 &z_buffer,
906 };
907 BVHTreeRayHit hit = {0};
908 const float dir[3] = {1.0f, 0.0f, 0.0f};
909
910 /* Need to initialize hit even tho it's not used.
911 * This is to make it so KD-tree believes we didn't intersect anything and
912 * keeps calling the intersect callback.
913 */
914 hit.index = -1;
916
917 BLI_bvhtree_ray_cast(tree, co, dir, 0.0f, &hit, raycast_callback, &raycast_data);
918
919# ifdef USE_DUMP
920 printf("%s: Total intersections: %zu\n", __func__, z_buffer.count);
921# endif
922
923 int num_isect;
924
925 if (z_buffer.is_empty()) {
926 num_isect = 0;
927 }
928 else if (z_buffer.size() == 1) {
929 num_isect = 1;
930 }
931 else {
932 /* 2 or more */
933 const float eps = FLT_EPSILON * 10;
934 num_isect = 1; /* always count first */
935
936 std::ranges::sort(z_buffer);
937
938 const float *depth_arr = z_buffer.data();
939 float depth_last = depth_arr[0];
940
941 for (uint i = 1; i < z_buffer.size(); i++) {
942 if (depth_arr[i] - depth_last > eps) {
943 depth_last = depth_arr[i];
944 num_isect++;
945 }
946 }
947 }
948
949 // return (num_isect & 1) == 1;
950 return num_isect;
951}
952
953#endif /* USE_BVH */
954
956 const Span<std::array<BMLoop *, 3>> looptris,
957 int (*test_fn)(BMFace *f, void *user_data),
958 void *user_data,
959 const bool use_self,
960 const bool use_separate,
961 const bool use_dissolve,
962 const bool use_island_connect,
963 const bool use_partial_connect,
964 const bool use_edge_tag,
965 const int boolean_mode,
966 const float eps)
967{
968 ISectState s;
969 const int totface_orig = bm->totface;
970
971 /* use to check if we made any changes */
972 bool has_edit_isect = false, has_edit_boolean = false;
973
974 /* needed for boolean, since cutting up faces moves the loops within the face */
975 const float **looptri_coords = nullptr;
976
977#ifdef USE_BVH
978 BVHTree *tree_a, *tree_b;
979 uint tree_overlap_tot;
980 BVHTreeOverlap *overlap;
981#else
982 int i_a, i_b;
983#endif
984
985 s.bm = bm;
986
989
990 s.edge_verts = BLI_ghash_ptr_new(__func__);
991 s.face_edges = BLI_ghash_int_new(__func__);
992 s.wire_edges = MEM_new<Set<BMEdge *>>(__func__);
993 s.vert_dissolve = nullptr;
994
996
997 /* setup epsilon from base */
998 s.epsilon.eps = eps;
999 s.epsilon.eps2x = eps * 2.0f;
1000 s.epsilon.eps_margin = s.epsilon.eps2x * 10.0f;
1001
1002 s.epsilon.eps_sq = s.epsilon.eps * s.epsilon.eps;
1005
1007 BM_VERT | BM_EDGE |
1008#ifdef USE_NET
1009 BM_FACE |
1010#endif
1011 0);
1012
1014#ifdef USE_SPLICE
1015 BM_EDGE |
1016#endif
1017#ifdef USE_NET
1018 BM_FACE |
1019#endif
1020 0);
1021
1022#ifdef USE_DISSOLVE
1023 if (use_dissolve) {
1025 }
1026#else
1027 UNUSED_VARS(use_dissolve);
1028#endif
1029
1030#ifdef USE_DUMP
1031 printf("data = [\n");
1032#endif
1033
1034 if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) {
1035 /* Keep original geometry for ray-cast callbacks. */
1036 float **cos;
1037 int i, j;
1038
1039 cos = MEM_new_array_uninitialized<float *>(size_t(looptris.size()) * 3, __func__);
1040 for (i = 0, j = 0; i < int(looptris.size()); i++) {
1041 cos[j++] = looptris[i][0]->v->co;
1042 cos[j++] = looptris[i][1]->v->co;
1043 cos[j++] = looptris[i][2]->v->co;
1044 }
1045 looptri_coords = (const float **)cos;
1046 }
1047
1048#ifdef USE_BVH
1049 {
1050 int i;
1051 tree_a = BLI_bvhtree_new(int(looptris.size()), s.epsilon.eps_margin, 8, 8);
1052 for (i = 0; i < int(looptris.size()); i++) {
1053 if (test_fn(looptris[i][0]->f, user_data) == 0) {
1054 const float t_cos[3][3] = {
1055 {UNPACK3(looptris[i][0]->v->co)},
1056 {UNPACK3(looptris[i][1]->v->co)},
1057 {UNPACK3(looptris[i][2]->v->co)},
1058 };
1059
1060 BLI_bvhtree_insert(tree_a, i, reinterpret_cast<const float *>(t_cos), 3);
1061 }
1062 }
1063 BLI_bvhtree_balance(tree_a);
1064 }
1065
1066 if (use_self == false) {
1067 int i;
1068 tree_b = BLI_bvhtree_new(int(looptris.size()), s.epsilon.eps_margin, 8, 8);
1069 for (i = 0; i < int(looptris.size()); i++) {
1070 if (test_fn(looptris[i][0]->f, user_data) == 1) {
1071 const float t_cos[3][3] = {
1072 {UNPACK3(looptris[i][0]->v->co)},
1073 {UNPACK3(looptris[i][1]->v->co)},
1074 {UNPACK3(looptris[i][2]->v->co)},
1075 };
1076
1077 BLI_bvhtree_insert(tree_b, i, reinterpret_cast<const float *>(t_cos), 3);
1078 }
1079 }
1080 BLI_bvhtree_balance(tree_b);
1081 }
1082 else {
1083 tree_b = tree_a;
1084 }
1085
1086 /* For self intersection this can be useful, sometimes users generate geometry
1087 * where surfaces that seem disconnected happen to share an edge.
1088 * So when performing intersection calculation allow shared vertices,
1089 * just not shared edges. See #75946. */
1090 const bool isect_tri_tri_no_shared = (boolean_mode != BMESH_ISECT_BOOLEAN_NONE);
1091
1093# ifndef NDEBUG
1094 /* The overlap result must match that obtained in Release to succeed
1095 * in the `bmesh_boolean` test. */
1096 if (looptris.size() < 1024) {
1098 }
1099# endif
1100 overlap = BLI_bvhtree_overlap_ex(tree_b, tree_a, &tree_overlap_tot, nullptr, nullptr, 0, flag);
1101
1102 if (overlap) {
1103 uint i;
1104
1105 for (i = 0; i < tree_overlap_tot; i++) {
1106# ifdef USE_DUMP
1107 printf(" ((%d, %d), (\n", overlap[i].indexA, overlap[i].indexB);
1108# endif
1110 overlap[i].indexA,
1111 overlap[i].indexB,
1112 looptris[overlap[i].indexA],
1113 looptris[overlap[i].indexB],
1114 isect_tri_tri_no_shared);
1115# ifdef USE_DUMP
1116 printf(")),\n");
1117# endif
1118 }
1119 MEM_delete(overlap);
1120 }
1121
1122 if (boolean_mode == BMESH_ISECT_BOOLEAN_NONE) {
1123 /* no booleans, just free immediate */
1124 BLI_bvhtree_free(tree_a);
1125 if (tree_a != tree_b) {
1126 BLI_bvhtree_free(tree_b);
1127 }
1128 }
1129
1130#else
1131 {
1132 for (i_a = 0; i_a < looptris.size(); i_a++) {
1133 const int t_a = test_fn(looptris[i_a][0]->f, user_data);
1134 for (i_b = i_a + 1; i_b < looptris.size(); i_b++) {
1135 const int t_b = test_fn(looptris[i_b][0]->f, user_data);
1136
1137 if (use_self) {
1138 if ((t_a != 0) || (t_b != 0)) {
1139 continue;
1140 }
1141 }
1142 else {
1143 if ((t_a != t_b) && !ELEM(-1, t_a, t_b)) {
1144 continue;
1145 }
1146 }
1147
1148# ifdef USE_DUMP
1149 printf(" ((%d, %d), (", i_a, i_b);
1150# endif
1151 bm_isect_tri_tri(&s, i_a, i_b, looptris[i_a], looptris[i_b], isect_tri_tri_no_shared);
1152# ifdef USE_DUMP
1153 printf(")),\n");
1154# endif
1155 }
1156 }
1157 }
1158#endif /* USE_BVH */
1159
1160#ifdef USE_DUMP
1161 printf("]\n");
1162#endif
1163
1164 /* --------- */
1165
1166#ifdef USE_SPLICE
1167 {
1168 GHashIterator gh_iter;
1169
1170 GHASH_ITER (gh_iter, s.edge_verts) {
1171 BMEdge *e = static_cast<BMEdge *>(BLI_ghashIterator_getKey(&gh_iter));
1172 LinkBase *v_ls_base = static_cast<LinkBase *>(BLI_ghashIterator_getValue(&gh_iter));
1173
1174 BMVert *v_start;
1175 BMVert *v_end;
1176 BMVert *v_prev;
1177 bool is_wire;
1178
1179 LinkNode *node;
1180
1181 /* direction is arbitrary, could be swapped */
1182 v_start = e->v1;
1183 v_end = e->v2;
1184
1185 if (v_ls_base->list_len > 1) {
1186 edge_verts_sort(v_start->co, v_ls_base);
1187 }
1188
1189# ifdef USE_DUMP
1190 printf("# SPLITTING EDGE: %d, %u\n", BM_elem_index_get(e), v_ls_base->list_len);
1191# endif
1192 /* intersect */
1193 is_wire = s.wire_edges->contains(e);
1194
1195# ifdef USE_PARANOID
1196 for (node = v_ls_base->list; node; node = node->next) {
1197 BMVert *_v = node->link;
1200 }
1201# endif
1202
1203 v_prev = v_start;
1204
1205 for (node = v_ls_base->list; node; node = node->next) {
1206 BMVert *vi = static_cast<BMVert *>(node->link);
1207 const float fac = line_point_factor_v3(vi->co, e->v1->co, e->v2->co);
1208
1209 if (BM_vert_in_edge(e, v_prev)) {
1210 BMEdge *e_split;
1211 v_prev = BM_edge_split(bm, e, v_prev, &e_split, clamp_f(fac, 0.0f, 1.0f));
1212 BLI_assert(BM_vert_in_edge(e, v_end));
1213
1214 if (!BM_edge_exists(v_prev, vi) && !BM_vert_pair_share_face_check(v_prev, vi) &&
1215 !BM_vert_splice_check_double_edge(v_prev, vi) &&
1217 {
1218 BM_vert_splice(bm, vi, v_prev);
1219 }
1220 else {
1221 copy_v3_v3(v_prev->co, vi->co);
1222 }
1223 v_prev = vi;
1224 if (is_wire) {
1225 s.wire_edges->add(e_split);
1226 }
1227 }
1228 }
1229 UNUSED_VARS_NDEBUG(v_end);
1230 }
1231 }
1232#endif
1233
1234/* important to handle before edgenet */
1235#ifdef USE_DISSOLVE
1236 if (use_dissolve && (boolean_mode == BMESH_ISECT_BOOLEAN_NONE)) {
1237 /* first pass */
1238 BMVert *(*splice_ls)[2];
1239 STACK_DECLARE(splice_ls);
1240 LinkNode *node;
1241
1242 for (node = s.vert_dissolve; node; node = node->next) {
1243 BMVert *v = static_cast<BMVert *>(node->link);
1245 if (!BM_vert_is_edge_pair(v)) {
1247 }
1248 }
1249 }
1250
1251 splice_ls = MEM_new_array_uninitialized<BMVert *[2]>(size_t(s.wire_edges->size()), __func__);
1252 STACK_INIT(splice_ls, s.wire_edges->size());
1253
1254 for (node = s.vert_dissolve; node; node = node->next) {
1255 BMEdge *e_pair[2];
1256 BMVert *v = static_cast<BMVert *>(node->link);
1257 BMVert *v_a, *v_b;
1258
1260 continue;
1261 }
1262
1263 /* get chain */
1264 e_pair[0] = v->e;
1265 e_pair[1] = BM_DISK_EDGE_NEXT(v->e, v);
1266
1267 if (BM_elem_flag_test(e_pair[0], BM_ELEM_TAG) || BM_elem_flag_test(e_pair[1], BM_ELEM_TAG)) {
1268 continue;
1269 }
1270
1271 /* It's possible the vertex to dissolve is an edge on an existing face
1272 * that doesn't divide the face, therefore the edges are not wire
1273 * and shouldn't be handled here, see: #63787. */
1274 if (!s.wire_edges->contains(e_pair[0]) || !s.wire_edges->contains(e_pair[1])) {
1275 continue;
1276 }
1277
1278 v_a = BM_edge_other_vert(e_pair[0], v);
1279 v_b = BM_edge_other_vert(e_pair[1], v);
1280
1281 /* simple case */
1283 /* only start on an edge-case */
1284 /* pass */
1285 }
1286 else if (!BM_elem_flag_test(v_a, BM_ELEM_TAG) && !BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
1287 /* simple case, single edge spans face */
1288 BMVert **splice_pair;
1289 BM_elem_flag_enable(e_pair[1], BM_ELEM_TAG);
1290 splice_pair = STACK_PUSH_RET(splice_ls);
1291 splice_pair[0] = v;
1292 splice_pair[1] = v_b;
1293# ifdef USE_DUMP
1294 printf("# Simple Case!\n");
1295# endif
1296 }
1297 else {
1298# ifdef USE_PARANOID
1299 BMEdge *e_keep;
1300# endif
1301 BMEdge *e;
1302 BMEdge *e_step;
1303 BMVert *v_step;
1304
1305 /* walk the chain! */
1306 if (BM_elem_flag_test(v_a, BM_ELEM_TAG)) {
1307 e = e_pair[0];
1308# ifdef USE_PARANOID
1309 e_keep = e_pair[1];
1310# endif
1311 }
1312 else {
1313 std::swap(v_a, v_b);
1314 e = e_pair[1];
1315# ifdef USE_PARANOID
1316 e_keep = e_pair[0];
1317# endif
1318 }
1319
1320 /* WALK */
1321 v_step = v;
1322 e_step = e;
1323
1324 while (true) {
1325 BMEdge *e_next;
1326 BMVert *v_next;
1327
1328 v_next = BM_edge_other_vert(e_step, v_step);
1330 if (!BM_elem_flag_test(v_next, BM_ELEM_TAG)) {
1331 BMVert **splice_pair;
1332# ifdef USE_PARANOID
1333 BLI_assert(e_step != e_keep);
1334# endif
1335 splice_pair = STACK_PUSH_RET(splice_ls);
1336 splice_pair[0] = v;
1337 splice_pair[1] = v_next;
1338 break;
1339 }
1340
1341 e_next = bm_vert_other_edge(v_next, e_step);
1342 e_step = e_next;
1343 v_step = v_next;
1345# ifdef USE_PARANOID
1346 BLI_assert(e_step != e_keep);
1347# endif
1348# ifdef USE_DUMP
1349 printf("# walk step %p %p\n", e_next, v_next);
1350# endif
1351 }
1352# ifdef USE_PARANOID
1354# endif
1355 }
1356 }
1357
1358 /* Remove edges! */
1359 {
1360 GHashIterator gh_iter;
1361
1362 GHASH_ITER (gh_iter, s.face_edges) {
1363 LinkBase *e_ls_base = static_cast<LinkBase *>(BLI_ghashIterator_getValue(&gh_iter));
1364 LinkNode **node_prev_p;
1365
1366 node_prev_p = &e_ls_base->list;
1367 for (node = e_ls_base->list; node; node = node->next) {
1368 BMEdge *e = static_cast<BMEdge *>(node->link);
1370 /* allocated by arena, don't free */
1371 *node_prev_p = node->next;
1372 e_ls_base->list_len--;
1373 }
1374 else {
1375 node_prev_p = &node->next;
1376 }
1377 }
1378 }
1379 }
1380
1381 {
1382 BMIter eiter;
1383 BMEdge *e, *e_next;
1384
1385 BM_ITER_MESH_MUTABLE (e, e_next, &eiter, bm, BM_EDGES_OF_MESH) {
1387
1388 /* in rare and annoying cases,
1389 * there can be faces from 's.face_edges' removed by the edges.
1390 * These are degenerate cases, so just make sure we don't reference the faces again. */
1391 if (e->l) {
1392 BMLoop *l_iter = e->l;
1393 BMFace **faces;
1394
1395 faces = bm->ftable;
1396
1397 do {
1398 const int f_index = BM_elem_index_get(l_iter->f);
1399 if (f_index >= 0) {
1400 BLI_assert(f_index < totface_orig);
1401 /* we could check if these are in: 's.face_edges', but easier just to remove */
1402 faces[f_index] = nullptr;
1403 }
1404 } while ((l_iter = l_iter->radial_next) != e->l);
1405 }
1406
1407 s.wire_edges->remove(e);
1408 BM_edge_kill(bm, e);
1409 }
1410 }
1411 }
1412
1413 /* Remove verts! */
1414 {
1415 Set<BMVert *> verts_invalid;
1416
1417 for (node = s.vert_dissolve; node; node = node->next) {
1418 /* arena allocated, don't free */
1419 BMVert *v = static_cast<BMVert *>(node->link);
1421 if (!v->e) {
1422 verts_invalid.add(v);
1423 BM_vert_kill(bm, v);
1424 }
1425 }
1426 }
1427
1428 {
1429 uint i;
1430 for (i = 0; i < STACK_SIZE(splice_ls); i++) {
1431 if (!verts_invalid.contains(splice_ls[i][0]) && !verts_invalid.contains(splice_ls[i][1]))
1432 {
1433 if (!BM_edge_exists(UNPACK2(splice_ls[i])) &&
1434 !BM_vert_splice_check_double_edge(UNPACK2(splice_ls[i])) &&
1436 {
1437 BM_vert_splice(bm, splice_ls[i][1], splice_ls[i][0]);
1438 }
1439 }
1440 }
1441 }
1442 }
1443
1444 MEM_delete(splice_ls);
1445 }
1446#endif /* USE_DISSOLVE */
1447
1448/* now split faces */
1449#ifdef USE_NET
1450 {
1451 GHashIterator gh_iter;
1452 BMFace **faces;
1453
1454 MemArena *mem_arena_edgenet = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1455
1456 faces = bm->ftable;
1457
1458 GHASH_ITER (gh_iter, s.face_edges) {
1459 const int f_index = POINTER_AS_INT(BLI_ghashIterator_getKey(&gh_iter));
1460 BMFace *f;
1461 LinkBase *e_ls_base = static_cast<LinkBase *>(BLI_ghashIterator_getValue(&gh_iter));
1462
1463 BLI_assert(f_index >= 0 && f_index < totface_orig);
1464
1465 f = faces[f_index];
1466 if (f == nullptr) [[unlikely]] {
1467 continue;
1468 }
1469
1470 BLI_assert(BM_elem_index_get(f) == f_index);
1471
1473 bm, f, e_ls_base, use_island_connect, use_partial_connect, mem_arena_edgenet);
1474
1475 BLI_memarena_clear(mem_arena_edgenet);
1476 }
1477
1478 BLI_memarena_free(mem_arena_edgenet);
1479 }
1480#else
1481 UNUSED_VARS(use_island_connect);
1482#endif /* USE_NET */
1483 (void)totface_orig;
1484
1485#ifdef USE_SEPARATE
1486 if (use_separate) {
1488
1489 for (BMEdge *e : *s.wire_edges) {
1491 }
1492
1493 BM_mesh_edgesplit(bm, false, true, false);
1494 }
1495 else if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE || use_edge_tag) {
1496 /* no need to clear for boolean */
1497 for (BMEdge *e : *s.wire_edges) {
1499 }
1500 }
1501#else
1502 (void)use_separate;
1503#endif /* USE_SEPARATE */
1504
1505 if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) {
1506 BVHTree *tree_pair[2] = {tree_a, tree_b};
1507
1508 /* group vars */
1509 int *groups_array;
1510 int (*group_index)[2];
1511 int group_tot;
1512 int i;
1513 BMFace **ftable;
1514
1516 ftable = bm->ftable;
1517
1518 /* wrap the face-test callback to make it into an edge-loop delimiter */
1519 LoopFilterWrap user_data_wrap{};
1520 user_data_wrap.test_fn = test_fn;
1521 user_data_wrap.user_data = user_data;
1522
1523 groups_array = MEM_new_array_uninitialized<int>(size_t(bm->totface), __func__);
1524 group_tot = BM_mesh_calc_face_groups(
1525 bm, groups_array, &group_index, bm_loop_filter_fn, nullptr, &user_data_wrap, 0, BM_EDGE);
1526
1527#ifdef USE_DUMP
1528 printf("%s: Total face-groups: %d\n", __func__, group_tot);
1529#endif
1530
1531 /* Check if island is inside/outside */
1532 for (i = 0; i < group_tot; i++) {
1533 int fg = group_index[i][0];
1534 int fg_end = group_index[i][1] + fg;
1535 bool do_remove, do_flip;
1536
1537 {
1538 /* For now assume this is an OK face to test with (not degenerate!) */
1539 BMFace *f = ftable[groups_array[fg]];
1540 float co[3];
1541 int hits;
1542 int side = test_fn(f, user_data);
1543
1544 if (side == -1) {
1545 continue;
1546 }
1547 BLI_assert(ELEM(side, 0, 1));
1548 side = !side;
1549
1550 // BM_face_calc_center_median(f, co);
1552
1553 hits = isect_bvhtree_point_v3(tree_pair[side], looptri_coords, co);
1554
1555 switch (boolean_mode) {
1557 do_remove = ((hits & 1) != 1);
1558 do_flip = false;
1559 break;
1561 do_remove = ((hits & 1) == 1);
1562 do_flip = false;
1563 break;
1565 do_remove = ((hits & 1) == 1) == side;
1566 do_flip = (side == 0);
1567 break;
1568 }
1569 }
1570
1571 if (do_remove) {
1572 for (; fg != fg_end; fg++) {
1573 /* postpone killing the face since we access below, mark instead */
1574 // BM_face_kill_loose(bm, ftable[groups_array[fg]]);
1575 ftable[groups_array[fg]]->mat_nr = -1;
1576 }
1577 }
1578 else if (do_flip) {
1579 for (; fg != fg_end; fg++) {
1580 BM_face_normal_flip(bm, ftable[groups_array[fg]]);
1581 }
1582 }
1583
1584 has_edit_boolean |= (do_flip || do_remove);
1585 }
1586
1587 MEM_delete(groups_array);
1588 MEM_delete(group_index);
1589
1590#ifdef USE_DISSOLVE
1591 /* We have dissolve code above, this is alternative logic,
1592 * we need to do it after the boolean is executed. */
1593 if (use_dissolve) {
1594 LinkNode *node;
1595 for (node = s.vert_dissolve; node; node = node->next) {
1596 BMVert *v = static_cast<BMVert *>(node->link);
1597 if (BM_vert_is_edge_pair(v)) {
1598 /* we won't create degenerate faces from this */
1599 bool ok = true;
1600
1601 /* If dissolving would we create a 2-sided-face:
1602 * don't dissolve this since we may want to access the geometry. */
1603 if (v->e->l) {
1604 BMLoop *l_iter = v->e->l;
1605 do {
1606 if (l_iter->f->len == 3) {
1607 ok = false;
1608 break;
1609 }
1610 } while ((l_iter = l_iter->radial_next) != v->e->l);
1611 }
1612
1613 /* If dissolving would we create a duplicate face:
1614 * don't dissolve this otherwise it would be necessary to delete existing geometry.
1615 * NOTE(@ideasman42) this should only happen with degenerate geometry
1616 * (exactly overlapping geometry for e.g.).
1617 * See the complex test file in #150360. */
1618 if (ok) {
1620 ok = false;
1621 }
1622 }
1623
1624 if (ok) {
1625 BM_vert_collapse_edge(bm, v->e, v, true, false, false);
1626 }
1627 }
1628 }
1629 }
1630#endif
1631
1632 {
1633 int tot = bm->totface;
1634 for (i = 0; i < tot; i++) {
1635 if (ftable[i]->mat_nr == -1) {
1636 BM_face_kill_loose(bm, ftable[i]);
1637 }
1638 }
1639 }
1640 }
1641
1642 if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) {
1643 MEM_delete(looptri_coords);
1644
1645 /* no booleans, just free immediate */
1646 BLI_bvhtree_free(tree_a);
1647 if (tree_a != tree_b) {
1648 BLI_bvhtree_free(tree_b);
1649 }
1650 }
1651
1652 has_edit_isect = (BLI_ghash_len(s.face_edges) != 0);
1653
1654 /* cleanup */
1655 BLI_ghash_free(s.edgetri_cache, nullptr, nullptr);
1656
1657 BLI_ghash_free(s.edge_verts, nullptr, nullptr);
1658 BLI_ghash_free(s.face_edges, nullptr, nullptr);
1659 MEM_delete(s.wire_edges);
1660
1662
1663 /* It's unlikely the selection history is useful at this point,
1664 * if this is not called this array would need to be validated, see: #86799. */
1666
1667 return (has_edit_isect || has_edit_boolean);
1668}
1669
1670} // namespace blender
#define BLI_ghashutil_inthash_v4_cmp
Definition BLI_ghash.hh:601
#define GHASH_ITER(gh_iter_, ghash_)
Definition BLI_ghash.hh:320
#define BLI_ghashutil_inthash_v4_p
Definition BLI_ghash.hh:592
#define BVH_RAYCAST_DIST_MAX
#define USE_KDOPBVH_WATERTIGHT
#define BLI_MEMARENA_STD_BUFSIZE
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
#define STACK_PUSH_RET(stack)
Read Blender memory allocation and freeing.
#define UNPACK2(a)
#define UNPACK3_EX(pre, a, post)
#define UNPACK4(a)
#define UNUSED_VARS(...)
#define POINTER_FROM_INT(i)
#define UNUSED_VARS_NDEBUG(...)
#define POINTER_AS_INT(i)
#define UNPACK3(a)
#define ELEM(...)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define KEY_EDGE_TRI_ORDER(k)
#define KEY_SET(k, i0, i1, i2, i3)
#define STACK_PUSH_TEST_B(ele)
#define VERT_VISIT_B
#define USE_SPLICE
#define STACK_PUSH_TEST_A(ele)
#define USE_NET
#define VERT_VISIT_A
#define BM_ITER_MESH_MUTABLE(ele, ele_next, iter, bm, itype)
#define BM_ELEM_API_FLAG_DISABLE(element, f)
#define BM_ELEM_API_FLAG_TEST(element, f)
const T * data() const
Definition BLI_array.hh:323
bool contains(const Key &key) const
Definition BLI_set.hh:310
bool add(const Key &key)
Definition BLI_set.hh:248
int64_t size() const
bool is_empty() const
void append(const T &value)
#define FLT_EPSILON
#define cos
BMesh Iterators.
static enum ISectType intersect_line_tri(const float p0[3], const float p1[3], const float *t_cos[3], const float t_nor[3], float r_ix[3], const ISectEpsilon *e)
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
bool isect_point_tri_v3(const float p[3], const float v1[3], const float v2[3], const float v3[3], float r_isect_co[3])
BVHTreeOverlap * BLI_bvhtree_overlap_ex(const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata, uint max_interactions, int flag)
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
BLI_INLINE void * BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.hh:297
int isect_line_line_epsilon_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float r_i1[3], float r_i2[3], float epsilon)
bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
GHash * BLI_ghash_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
static void bm_isect_tri_tri(ISectState *s, int a_index, int b_index, const std::array< BMLoop *, 3 > &a, const std::array< BMLoop *, 3 > &b, bool no_shared)
void BM_face_normal_flip(BMesh *bm, BMFace *f)
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
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
bool isect_ray_tri_watertight_v3(const float ray_origin[3], const struct IsectRayPrecalc *isect_precalc, const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
void BM_vert_kill(BMesh *bm, BMVert *v)
void mid_v3_v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3])
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:735
void BLI_bvhtree_free(BVHTree *tree)
void BLI_bvhtree_balance(BVHTree *tree)
void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, struct MemArena *ma) ATTR_NONNULL(1
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
ATTR_WARN_UNUSED_RESULT const BMVert * v
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.
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
int BLI_bvhtree_ray_cast(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
void print_v3(const char *str, const float v[3])
static void raycast_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *)
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 BLI_ghash_insert(GHash *gh, void *key, void *val)
Definition BLI_ghash.cc:711
BLI_INLINE void * BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.hh:301
bool BM_face_share_edge_check(BMFace *f_a, BMFace *f_b)
int BLI_linklist_index(const LinkNode *list, const void *ptr) ATTR_WARN_UNUSED_RESULT
static void edge_verts_add(ISectState *s, BMEdge *e, BMVert *v, const bool use_test)
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:866
void BM_edge_kill(BMesh *bm, BMEdge *e)
BMesh const char void * data
bool BM_mesh_intersect(BMesh *bm, const Span< std::array< BMLoop *, 3 > > looptris, int(*test_fn)(BMFace *f, void *user_data), void *user_data, const bool use_self, const bool use_separate, const bool use_dissolve, const bool use_island_connect, const bool use_partial_connect, const bool use_edge_tag, const int boolean_mode, const float eps)
bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:756
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
static void edge_verts_sort(const float co[3], LinkBase *v_ls_base)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
@ BMESH_ISECT_BOOLEAN_NONE
@ BMESH_ISECT_BOOLEAN_DIFFERENCE
@ BMESH_ISECT_BOOLEAN_UNION
@ BMESH_ISECT_BOOLEAN_ISECT
bool BM_vert_pair_share_face_check(BMVert *v_a, BMVert *v_b)
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
static BMVert * bm_isect_edge_tri(ISectState *s, BMVert *e_v0, BMVert *e_v1, BMVert *t[3], const int t_index, const float *t_cos[3], const float t_nor[3], enum ISectType *r_side)
GHash * BLI_ghash_ptr_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
void BM_face_kill_loose(BMesh *bm, BMFace *f)
bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
Splice Vert.
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
static void tri_v3_scale(float v1[3], float v2[3], float v3[3], const float t)
unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:706
@ BVH_OVERLAP_USE_THREADING
@ BVH_OVERLAP_RETURN_PAIRS
static bool ghash_insert_link(GHash *gh, void *key, void *val, bool use_test, MemArena *mem_arena)
void BM_face_calc_point_in_face(const BMFace *f, float r_co[3])
BMEdge * BM_vert_collapse_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool kill_degenerate_faces, const bool kill_duplicate_faces)
Vert Collapse Faces.
bool BM_vert_splice_check_double_edge(BMVert *v_a, BMVert *v_b)
static bool bm_loop_filter_fn(const BMLoop *l, void *user_data)
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)
MINLINE float normalize_v3(float n[3])
static int isect_bvhtree_point_v3(BVHTree *tree, const float **looptris, const float co[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
BMVert * BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float fac)
Edge Split.
bool isect_line_segment_tri_epsilon_v3(const float p1[3], const float p2[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], float epsilon)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
static void vert_dissolve_add(ISectState *s, BMVert *v)
int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int(**r_group_index)[2], BMLoopFilterFunc filter_fn, BMLoopPairFilterFunc filter_pair_fn, void *user_data, const char hflag_test, const char htype_step)
void BM_mesh_edgesplit(BMesh *bm, const bool use_verts, const bool tag_only, const bool copy_select)
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)
bool BM_vert_is_edge_pair(const BMVert *v)
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
bool BM_face_split_edgenet(BMesh *bm, BMFace *f, BMEdge **edge_net, const int edge_net_len, Vector< BMFace * > *r_face_arr)
static BMEdge * bm_vert_other_edge(BMVert *v, BMEdge *e)
void BM_select_history_clear(BMesh *bm)
bool BM_vert_splice_check_double_face(BMVert *v_a, BMVert *v_b)
bool isect_ray_tri_epsilon_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], float epsilon)
bool BM_vert_collapse_check_double_face(BMVert *v_collapse)
GHash * BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:690
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
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.
static void face_edges_split(BMesh *bm, BMFace *f, LinkBase *e_ls_base, bool use_island_connect, bool use_partial_connect, MemArena *mem_arena_edgenet)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
static void face_edges_add(ISectState *s, const int f_index, BMEdge *e, const bool use_test)
MINLINE float clamp_f(float value, float min, float max)
const btScalar eps
Definition poly34.cpp:11
#define fabsf
struct BMLoop * radial_next
struct BMFace * f
Set< BMEdge * > * wire_edges
struct LinkNode * next
int(*) test_fn(BMFace *f, void *user_data)
Vector< float, 64 > * z_buffer
struct BMLoop * radial_next