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