Blender V5.3
editmesh_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
8
9#include "DNA_mesh_types.h"
10#include "DNA_object_types.h"
11
12#include "BLI_linklist_stack.hh"
13#include "BLI_math_geom_c.hh"
14#include "BLI_math_vector_c.hh"
15#include "BLI_memarena.hh"
16#include "BLI_stack_c.hh"
17#include "BLI_vector.hh"
18
19#include "BKE_context.hh"
20#include "BKE_editmesh.hh"
21#include "BKE_editmesh_bvh.hh"
22#include "BKE_layer.hh"
23#include "BKE_mesh_types.hh"
24#include "BKE_report.hh"
25
26#include "RNA_access.hh"
27#include "RNA_define.hh"
28
29#include "WM_types.hh"
30
32#include "UI_resources.hh"
33
34#include "ED_mesh.hh"
35#include "ED_screen.hh"
36
37#include "mesh_intern.hh" /* own include */
38
42
43namespace blender {
44
45/* detect isolated holes and fill them */
46#define USE_NET_ISLAND_CONNECT
47
51static int bm_face_isect_self(BMFace *f, void * /*user_data*/)
52{
54 return 0;
55 }
56 return -1;
57}
58
62static int bm_face_isect_pair(BMFace *f, void * /*user_data*/)
63{
65 return -1;
66 }
68 return 1;
69 }
70 return 0;
71}
72
77static int bm_face_isect_pair_swap(BMFace *f, void * /*user_data*/)
78{
80 return -1;
81 }
83 return 0;
84 }
85 return 1;
86}
87
91static void edbm_intersect_select(Mesh *mesh, bool do_select)
92{
93 BMEditMesh *em = mesh->runtime->edit_mesh.get();
95 if (do_select) {
97
99 BMIter iter;
100 BMEdge *e;
101
102 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
104 BM_edge_select_set(bm, e, true);
105 }
106 }
107
110 }
111 }
112
113 EDBMUpdate_Params params{};
114 params.calc_looptris = true;
115 params.calc_normals = true;
116 params.is_destructive = true;
117 EDBM_update(mesh, &params);
118}
119
120/* -------------------------------------------------------------------- */
125
126enum {
129};
130
131enum {
135};
136
137enum {
140};
141
143{
144 const int mode = RNA_enum_get(op->ptr, "mode");
145 int (*test_fn)(BMFace *, void *);
146 bool use_separate_all = false;
147 bool use_separate_cut = false;
148 const int separate_mode = RNA_enum_get(op->ptr, "separate_mode");
149 const float eps = RNA_float_get(op->ptr, "threshold");
150#ifdef WITH_GMP
151 const bool exact = RNA_enum_get(op->ptr, "solver") == ISECT_SOLVER_EXACT;
152#else
153 if (RNA_enum_get(op->ptr, "solver") == ISECT_SOLVER_EXACT) {
154 BKE_report(op->reports, RPT_WARNING, "Compiled without GMP, using \"float\" solver");
155 }
156 const bool exact = false;
157#endif
158 bool use_self;
159 bool has_isect;
160
161 switch (mode) {
162 case ISECT_SEL:
163 test_fn = bm_face_isect_self;
164 use_self = true;
165 break;
166 default: /* ISECT_SEL_UNSEL */
167 test_fn = bm_face_isect_pair;
168 use_self = false;
169 break;
170 }
171
172 switch (separate_mode) {
174 use_separate_all = true;
175 break;
177 if (use_self == false) {
178 use_separate_cut = true;
179 }
180 else {
181 /* we could support this but would require more advanced logic inside 'BM_mesh_intersect'
182 * for now just separate all */
183 use_separate_all = true;
184 }
185 break;
186 default: /* ISECT_SEPARATE_NONE */
187 break;
188 }
189 const Main *bmain = CTX_data_main(C);
190 const Scene *scene = CTX_data_scene(C);
191 ViewLayer *view_layer = CTX_data_view_layer(C);
192 uint isect_len = 0;
194 *bmain, scene, view_layer, CTX_wm_view3d(C));
195 for (Object *obedit : objects) {
198 if (bm->totfacesel == 0) {
199 continue;
200 }
201
202 if (exact) {
203 int nshapes = use_self ? 1 : 2;
204 has_isect = BM_mesh_boolean_knife(
205 bm, em->looptris, test_fn, nullptr, nshapes, use_self, use_separate_all, false, true);
206 }
207 else {
208 has_isect = BM_mesh_intersect(bm,
209 em->looptris,
210 test_fn,
211 nullptr,
212 use_self,
213 use_separate_all,
214 true,
215 true,
216 true,
217 true,
218 -1,
219 eps);
220 }
221
222 if (use_separate_cut) {
223 /* detach selected/un-selected faces */
226 }
227
228 edbm_intersect_select(id_cast<Mesh *>(obedit->data), has_isect);
229
230 if (!has_isect) {
231 isect_len++;
232 }
233 }
234
235 if (isect_len == objects.size()) {
236 BKE_report(op->reports, RPT_WARNING, "No intersections found");
237 }
238 return OPERATOR_FINISHED;
239}
240
241static void edbm_intersect_ui(bContext * /*C*/, wmOperator *op)
242{
243 ui::Layout &layout = *op->layout;
244
245 bool use_exact = RNA_enum_get(op->ptr, "solver") == ISECT_SOLVER_EXACT;
246
247 layout.use_property_split_set(true);
248 layout.use_property_decorate_set(false);
249 ui::Layout *row = &layout.row(false);
250 row->prop(op->ptr, "mode", ui::ITEM_R_EXPAND, std::nullopt, ICON_NONE);
251 layout.separator();
252 row = &layout.row(false);
253 row->prop(op->ptr, "separate_mode", ui::ITEM_R_EXPAND, std::nullopt, ICON_NONE);
254 layout.separator();
255
256 row = &layout.row(false);
257 row->prop(op->ptr, "solver", ui::ITEM_R_EXPAND, std::nullopt, ICON_NONE);
258 layout.separator();
259
260 if (!use_exact) {
261 layout.prop(op->ptr, "threshold", UI_ITEM_NONE, std::nullopt, ICON_NONE);
262 }
263}
264
266{
267 static const EnumPropertyItem isect_mode_items[] = {
268 {ISECT_SEL, "SELECT", 0, "Self Intersect", "Self intersect selected faces"},
270 "SELECT_UNSELECT",
271 0,
272 "Selected/Unselected",
273 "Intersect selected with unselected faces"},
274 {0, nullptr, 0, nullptr, nullptr},
275 };
276
277 static const EnumPropertyItem isect_separate_items[] = {
278 {ISECT_SEPARATE_ALL, "ALL", 0, "All", "Separate all geometry from intersections"},
280 "CUT",
281 0,
282 "Cut",
283 "Cut into geometry keeping each side separate (Selected/Unselected only)"},
284 {ISECT_SEPARATE_NONE, "NONE", 0, "Merge", "Merge all geometry from the intersection"},
285 {0, nullptr, 0, nullptr, nullptr},
286 };
287
288 static const EnumPropertyItem isect_intersect_solver_items[] = {
290 "FLOAT",
291 0,
292 "Float",
293 "Simple solver with good performance, without support for overlapping geometry"},
295 "EXACT",
296 0,
297 "Exact",
298 "Slower solver with the best results for coplanar faces"},
299 {0, nullptr, 0, nullptr, nullptr},
300 };
301
302 /* identifiers */
303 ot->name = "Intersect (Knife)";
304 ot->description = "Cut an intersection into faces";
305 ot->idname = "MESH_OT_intersect";
306
307 /* API callbacks. */
310 ot->ui = edbm_intersect_ui;
311
312 /* props */
313 RNA_def_enum(ot->srna, "mode", isect_mode_items, ISECT_SEL_UNSEL, "Source", "");
315 ot->srna, "separate_mode", isect_separate_items, ISECT_SEPARATE_CUT, "Separate Mode", "");
317 ot->srna, "threshold", 0.000001f, 0.0, 0.01, "Merge Threshold", "", 0.0, 0.001);
318 RNA_def_enum(ot->srna,
319 "solver",
320 isect_intersect_solver_items,
322 "Solver",
323 "Which Intersect solver to use");
324
325 /* flags */
327}
328
330
331/* -------------------------------------------------------------------- */
337
339{
340 const int boolean_operation = RNA_enum_get(op->ptr, "operation");
341 bool use_swap = RNA_boolean_get(op->ptr, "use_swap");
342 bool use_self = RNA_boolean_get(op->ptr, "use_self");
343#ifdef WITH_GMP
344 const bool use_exact = RNA_enum_get(op->ptr, "solver") == ISECT_SOLVER_EXACT;
345#else
346 if (RNA_enum_get(op->ptr, "solver") == ISECT_SOLVER_EXACT) {
347 BKE_report(op->reports, RPT_WARNING, "Compiled without GMP, using \"float\" solver");
348 }
349 const bool use_exact = false;
350#endif
351 const float eps = RNA_float_get(op->ptr, "threshold");
352 int (*test_fn)(BMFace *, void *);
353 bool has_isect;
354
355 test_fn = use_swap ? bm_face_isect_pair_swap : bm_face_isect_pair;
356 const Main *bmain = CTX_data_main(C);
357 const Scene *scene = CTX_data_scene(C);
358 ViewLayer *view_layer = CTX_data_view_layer(C);
359 uint isect_len = 0;
361 *bmain, scene, view_layer, CTX_wm_view3d(C));
362 for (Object *obedit : objects) {
365 if (bm->totfacesel == 0) {
366 continue;
367 }
368
369 if (use_exact) {
370 has_isect = BM_mesh_boolean(
371 bm, em->looptris, test_fn, nullptr, 2, use_self, true, false, boolean_operation);
372 }
373 else {
374 has_isect = BM_mesh_intersect(bm,
375 em->looptris,
376 test_fn,
377 nullptr,
378 false,
379 false,
380 true,
381 true,
382 false,
383 true,
384 boolean_operation,
385 eps);
386 }
387
388 edbm_intersect_select(id_cast<Mesh *>(obedit->data), has_isect);
389
390 if (!has_isect) {
391 isect_len++;
392 }
393 }
394
395 if (isect_len == objects.size()) {
396 BKE_report(op->reports, RPT_WARNING, "No intersections found");
397 }
398 return OPERATOR_FINISHED;
399}
400
402{
403 ui::Layout &layout = *op->layout;
404
405 bool use_exact = RNA_enum_get(op->ptr, "solver") == ISECT_SOLVER_EXACT;
406
407 layout.use_property_split_set(true);
408 layout.use_property_decorate_set(false);
409
410 ui::Layout &operation_row = layout.row(false);
411 operation_row.prop(op->ptr, "operation", ui::ITEM_R_EXPAND, std::nullopt, ICON_NONE);
412 layout.separator();
413
414 ui::Layout &solver_row = layout.row(false);
415 solver_row.prop(op->ptr, "solver", ui::ITEM_R_EXPAND, std::nullopt, ICON_NONE);
416 layout.separator();
417
418 layout.prop(op->ptr, "use_swap", UI_ITEM_NONE, std::nullopt, ICON_NONE);
419 layout.prop(op->ptr, "use_self", UI_ITEM_NONE, std::nullopt, ICON_NONE);
420 if (!use_exact) {
421 layout.prop(op->ptr, "threshold", UI_ITEM_NONE, std::nullopt, ICON_NONE);
422 }
423}
424
426{
427 static const EnumPropertyItem isect_boolean_operation_items[] = {
428 {BMESH_ISECT_BOOLEAN_ISECT, "INTERSECT", 0, "Intersect", ""},
429 {BMESH_ISECT_BOOLEAN_UNION, "UNION", 0, "Union", ""},
430 {BMESH_ISECT_BOOLEAN_DIFFERENCE, "DIFFERENCE", 0, "Difference", ""},
431 {0, nullptr, 0, nullptr, nullptr},
432 };
433
434 static const EnumPropertyItem isect_boolean_solver_items[] = {
435 {ISECT_SOLVER_FAST, "FLOAT", 0, "Float", "Faster solver, some limitations"},
436 {ISECT_SOLVER_EXACT, "EXACT", 0, "Exact", "Exact solver, slower, handles more cases"},
437 {0, nullptr, 0, nullptr, nullptr},
438 };
439
440 /* identifiers */
441 ot->name = "Intersect (Boolean)";
442 ot->description = "Cut solid geometry from selected to unselected";
443 ot->idname = "MESH_OT_intersect_boolean";
444
445 /* API callbacks. */
449
450 /* props */
451 RNA_def_enum(ot->srna,
452 "operation",
453 isect_boolean_operation_items,
455 "Boolean Operation",
456 "Which boolean operation to apply");
458 "use_swap",
459 false,
460 "Swap",
461 "Use with difference intersection to swap which side is kept");
463 ot->srna, "use_self", false, "Self Intersection", "Do self-union or self-intersection");
465 ot->srna, "threshold", 0.000001f, 0.0, 0.01, "Merge Threshold", "", 0.0, 0.001);
466 RNA_def_enum(ot->srna,
467 "solver",
468 isect_boolean_solver_items,
470 "Solver",
471 "Which Boolean solver to use");
472
473 /* flags */
475}
476
478
479/* -------------------------------------------------------------------- */
482
484 BMFace *f,
485 const char hflag, /* reusable memory buffer */
486 Vector<BMEdge *, 128> *edge_net_temp_buf)
487{
488 const int f_index = BM_elem_index_get(f);
489
490 BMLoop *l_iter;
491 BMLoop *l_first;
492 BMVert *v;
493
494 /* likely this will stay very small
495 * all verts pushed into this stack _must_ have their previous edges set! */
496 BLI_SMALLSTACK_DECLARE(vert_stack, BMVert *);
497 BLI_SMALLSTACK_DECLARE(vert_stack_next, BMVert *);
498
499 BLI_assert(edge_net_temp_buf->is_empty());
500
501 /* collect all edges */
502 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
503 do {
504 BMIter iter;
505 BMEdge *e;
506
507 BM_ITER_ELEM (e, &iter, l_iter->v, BM_EDGES_OF_VERT) {
508 if (BM_elem_flag_test(e, hflag) && (BM_elem_index_get(e) == f_index)) {
509 v = BM_edge_other_vert(e, l_iter->v);
510 v->e = e;
511
512 BLI_SMALLSTACK_PUSH(vert_stack, v);
513 edge_net_temp_buf->append(e);
514 }
515 }
516 } while ((l_iter = l_iter->next) != l_first);
517
518 /* now assign all */
519 /* pop free values into the next stack */
520 while ((v = static_cast<BMVert *>(BLI_SMALLSTACK_POP_EX(vert_stack, vert_stack_next)))) {
521 BMIter eiter;
522 BMEdge *e_next;
523
524 BM_ITER_ELEM (e_next, &eiter, v, BM_EDGES_OF_VERT) {
525 if (BM_elem_flag_test(e_next, hflag) && (BM_elem_index_get(e_next) == -1)) {
526 BMVert *v_next;
527 v_next = BM_edge_other_vert(e_next, v);
528 BM_elem_index_set(e_next, f_index);
529 BLI_SMALLSTACK_PUSH(vert_stack_next, v_next);
530 edge_net_temp_buf->append(e_next);
531 }
532 }
533
534 if (BLI_SMALLSTACK_IS_EMPTY(vert_stack)) {
535 BLI_SMALLSTACK_SWAP(vert_stack, vert_stack_next);
536 }
537 }
538
539 Vector<BMFace *> face_arr;
540 BM_face_split_edgenet(bm, f, edge_net_temp_buf->data(), edge_net_temp_buf->size(), &face_arr);
541
542 edge_net_temp_buf->clear();
543
544 for (BMFace *face : face_arr) {
545 BM_face_select_set(bm, face, true);
546 BM_elem_flag_disable(face, hflag);
547 }
548}
549
554static bool bm_vert_in_faces_radial(BMVert *v, BMEdge *e_radial, BMFace *f_ignore)
555{
556 BLI_assert(BM_vert_in_face(v, f_ignore) == false);
557 if (e_radial->l) {
558 BMLoop *l_iter = e_radial->l;
559 do {
560 if (l_iter->f != f_ignore) {
561 if (BM_vert_in_face(v, l_iter->f)) {
562 return true;
563 }
564 }
565 } while ((l_iter = l_iter->radial_next) != e_radial->l);
566 }
567 return false;
568}
569
570#ifdef USE_NET_ISLAND_CONNECT
571
572struct LinkBase {
573 LinkNode *list;
575};
576
578 BMFace *f_key,
579 BMEdge *e_val,
580 MemArena *mem_arena)
581{
582 LinkBase *ls_base = gh.lookup_or_add_cb(f_key, [&]() {
583 LinkBase *ls_base = static_cast<LinkBase *>(BLI_memarena_alloc(mem_arena, sizeof(*ls_base)));
584 ls_base->list = nullptr;
585 ls_base->list_len = 0;
586 return ls_base;
587 });
588
589 LinkNode *ls = static_cast<LinkNode *>(BLI_memarena_alloc(mem_arena, sizeof(*ls)));
590 ls->next = ls_base->list;
591 ls->link = e_val;
592 ls_base->list = ls;
593 ls_base->list_len += 1;
594}
595
596static int bm_edge_sort_length_cb(const void *e_a_v, const void *e_b_v)
597{
598 const float val_a = -BM_edge_calc_length_squared(
599 *(static_cast<BMEdge **>(const_cast<void *>(e_a_v))));
600 const float val_b = -BM_edge_calc_length_squared(
601 *(static_cast<BMEdge **>(const_cast<void *>(e_b_v))));
602
603 if (val_a > val_b) {
604 return 1;
605 }
606 if (val_a < val_b) {
607 return -1;
608 }
609 return 0;
610}
611
613 BMesh *bm, BMFace *f, LinkNode *e_link, const int e_link_len, MemArena *mem_arena_edgenet)
614{
615 BMEdge **edge_arr = static_cast<BMEdge **>(
616 BLI_memarena_alloc(mem_arena_edgenet, sizeof(*edge_arr) * e_link_len));
617 int edge_arr_len = 0;
618
619 while (e_link) {
620 edge_arr[edge_arr_len++] = static_cast<BMEdge *>(e_link->link);
621 e_link = e_link->next;
622 }
623
624 {
625 uint edge_arr_holes_len;
626 BMEdge **edge_arr_holes;
628 f,
629 edge_arr,
630 e_link_len,
631 true,
632 mem_arena_edgenet,
633 &edge_arr_holes,
634 &edge_arr_holes_len))
635 {
636 edge_arr_len = edge_arr_holes_len;
637 edge_arr = edge_arr_holes; /* owned by the arena */
638 }
639 }
640
641 BM_face_split_edgenet(bm, f, edge_arr, edge_arr_len, nullptr);
642
643 for (int i = e_link_len; i < edge_arr_len; i++) {
644 BM_edge_select_set(bm, edge_arr[i], true);
645 }
646
647 if (e_link_len != edge_arr_len) {
648 /* connecting partial islands can add redundant edges
649 * sort before removal to give deterministic outcome */
650 qsort(edge_arr, edge_arr_len - e_link_len, sizeof(*edge_arr), bm_edge_sort_length_cb);
651 for (int i = e_link_len; i < edge_arr_len; i++) {
652 BMFace *f_pair[2];
653 if (BM_edge_face_pair(edge_arr[i], &f_pair[0], &f_pair[1])) {
654 if (BM_face_share_vert_count(f_pair[0], f_pair[1]) == 2) {
655 BMFace *f_double;
656 BMFace *f_new = BM_faces_join(bm, f_pair, 2, true, &f_double);
657 /* See #BM_faces_join note on callers asserting when `r_double` is non-null. */
658 BLI_assert_msg(f_double == nullptr,
659 "Doubled face detected at " AT ". Resulting mesh may be corrupt.");
660
661 if (f_new) {
662 BM_face_select_set(bm, f_new, true);
663 }
664 }
665 }
666 }
667 }
668}
669
689 BMFace *f_a,
690 BMVert *v_pivot,
691 BMFace **ftable,
692 const int ftable_len,
693 float r_v_pivot_co[3],
694 float *r_v_pivot_fac)
695{
696 const int f_a_index = BM_elem_index_get(e_a);
697 bool found_other_self = false;
698 int found_other_face = 0;
699 BLI_SMALLSTACK_DECLARE(face_stack, BMFace *);
700
701 /* loop over surrounding edges to check if we're part of a chain or a delimiter vertex */
702 BMEdge *e_b = v_pivot->e;
703 do {
704 if (e_b != e_a) {
705 const int f_b_index = BM_elem_index_get(e_b);
706 if (f_b_index == f_a_index) {
707 /* not an endpoint */
708 found_other_self = true;
709 }
710 else if (f_b_index != -1) {
711 BLI_assert(f_b_index < ftable_len);
712 UNUSED_VARS_NDEBUG(ftable_len);
713
714 /* 'v_pivot' spans 2+ faces,
715 * tag to ensure we pick an edge that includes this face */
716 BMFace *f_b = ftable[f_b_index];
719 BLI_SMALLSTACK_PUSH(face_stack, f_b);
720 found_other_face++;
721 }
722 }
723 }
724 } while ((e_b = BM_DISK_EDGE_NEXT(e_b, v_pivot)) != v_pivot->e);
725
726 BMEdge *e_split = nullptr;
727
728 /* if we have no others or the other edge is outside this face,
729 * we're an endpoint to connect to a boundary */
730 if ((found_other_self == false) || found_other_face) {
731
732 BMLoop *l_iter, *l_first;
733 l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
734 float dist_best_sq = FLT_MAX;
735
736 do {
737 float v_pivot_co_test[3];
738 float v_pivot_fac = line_point_factor_v3(v_pivot->co, l_iter->e->v1->co, l_iter->e->v2->co);
739 CLAMP(v_pivot_fac, 0.0f, 1.0f);
740 interp_v3_v3v3(v_pivot_co_test, l_iter->e->v1->co, l_iter->e->v2->co, v_pivot_fac);
741
742 float dist_test_sq = len_squared_v3v3(v_pivot_co_test, v_pivot->co);
743 if ((dist_test_sq < dist_best_sq) || (e_split == nullptr)) {
744 bool ok = true;
745
746 if (BM_edge_exists(v_pivot, l_iter->e->v1) || BM_edge_exists(v_pivot, l_iter->e->v2))
747 [[unlikely]]
748 {
749 /* very unlikely but will cause complications splicing the verts together,
750 * so just skip this case */
751 ok = false;
752 }
753 else if (found_other_face) {
754 /* double check that _all_ the faces used by v_pivot's edges are attached
755 * to this edge otherwise don't attempt the split since it will give
756 * non-deterministic results */
757 BMLoop *l_radial_iter = l_iter->radial_next;
758 int other_face_shared = 0;
759 if (l_radial_iter != l_iter) {
760 do {
761 if (BM_elem_flag_test(l_radial_iter->f, BM_ELEM_INTERNAL_TAG)) {
762 other_face_shared++;
763 }
764 } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
765 }
766 if (other_face_shared != found_other_face) {
767 ok = false;
768 }
769 }
770
771 if (ok) {
772 e_split = l_iter->e;
773 dist_best_sq = dist_test_sq;
774 copy_v3_v3(r_v_pivot_co, v_pivot_co_test);
775 *r_v_pivot_fac = v_pivot_fac;
776 }
777 }
778 } while ((l_iter = l_iter->next) != l_first);
779 }
780
781 {
782 /* reset the flag, for future use */
783 BMFace *f;
784 while ((f = static_cast<BMFace *>(BLI_SMALLSTACK_POP(face_stack)))) {
786 }
787 }
788
789 return e_split;
790}
791
792#endif /* USE_NET_ISLAND_CONNECT */
793
795{
796 const char hflag = BM_ELEM_TAG;
797
798 BMEdge *e;
799 BMIter iter;
800
801 BLI_SMALLSTACK_DECLARE(loop_stack, BMLoop *);
802
803 const Main *bmain = CTX_data_main(C);
804 const Scene *scene = CTX_data_scene(C);
805 ViewLayer *view_layer = CTX_data_view_layer(C);
807 *bmain, scene, view_layer, CTX_wm_view3d(C));
808 for (Object *obedit : objects) {
811 if ((bm->totedgesel == 0) || (bm->totfacesel == 0)) {
812 continue;
813 }
814
815 {
816 BMVert *v;
817 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
818 BM_elem_flag_disable(v, hflag);
819 }
820 }
821
822 /* edge index is set to -1 then used to associate them with faces */
823 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
825 BM_elem_flag_enable(e, hflag);
826
827 BM_elem_flag_enable(e->v1, hflag);
828 BM_elem_flag_enable(e->v2, hflag);
829 }
830 else {
831 BM_elem_flag_disable(e, hflag);
832 }
833 BM_elem_index_set(e, -1); /* set_dirty */
834 }
836
837 {
838 BMFace *f;
839 int i;
840 BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
842 BM_elem_flag_enable(f, hflag);
843 }
844 else {
845 BM_elem_flag_disable(f, hflag);
846 }
848 BM_elem_index_set(f, i); /* set_ok */
849 }
850 }
852
853 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
854 if (BM_elem_flag_test(e, hflag)) {
855 BMIter viter;
856 BMVert *v;
857 BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
858 BMIter liter;
859 BMLoop *l;
860
861 uint loop_stack_len;
862 BMLoop *l_best = nullptr;
863
865 loop_stack_len = 0;
866
867 BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
868 if (BM_elem_flag_test(l->f, hflag)) {
869 BLI_SMALLSTACK_PUSH(loop_stack, l);
870 loop_stack_len++;
871 }
872 }
873
874 if (loop_stack_len == 0) {
875 /* pass */
876 }
877 else if (loop_stack_len == 1) {
878 l_best = static_cast<BMLoop *>(BLI_SMALLSTACK_POP(loop_stack));
879 }
880 else {
881 /* complicated case, match the edge with a face-loop */
882
883 BMVert *v_other = BM_edge_other_vert(e, v);
884 float e_dir[3];
885
886 /* we want closest to zero */
887 float dot_best = FLT_MAX;
888
889 sub_v3_v3v3(e_dir, v_other->co, v->co);
890 normalize_v3(e_dir);
891
892 while ((l = static_cast<BMLoop *>(BLI_SMALLSTACK_POP(loop_stack)))) {
893 float dot_test;
894
895 /* Check dot first to save on expensive angle-comparison.
896 * ideal case is 90d difference == 0.0 dot */
897 dot_test = fabsf(dot_v3v3(e_dir, l->f->no));
898 if (dot_test < dot_best) {
899
900 /* check we're in the correct corner
901 * (works with convex loops too) */
903 l->prev->v->co, l->v->co, v_other->co, l->f->no) <
905 l->prev->v->co, l->v->co, l->next->v->co, l->f->no))
906 {
907 dot_best = dot_test;
908 l_best = l;
909 }
910 }
911 }
912 }
913
914 if (l_best) {
915 BM_elem_index_set(e, BM_elem_index_get(l_best->f)); /* set_dirty */
916 }
917 }
918 }
919 }
920
921 {
922 BMFace *f;
923 Vector<BMEdge *, 128> edge_net_temp_buf;
924
925 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
926 if (BM_elem_flag_test(f, hflag)) {
927 bm_face_split_by_edges(bm, f, hflag, &edge_net_temp_buf);
928 }
929 }
930 }
931
932#ifdef USE_NET_ISLAND_CONNECT
933 /* before overwriting edge index values, collect edges left untouched */
934 BLI_Stack *edges_loose = BLI_stack_new(sizeof(BMEdge *), __func__);
935 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
937 BLI_stack_push(edges_loose, &e);
938 }
939 }
940#endif
941
942 EDBMUpdate_Params params{};
943 params.calc_looptris = true;
944 params.calc_normals = true;
945 params.is_destructive = true;
946 EDBM_update(id_cast<Mesh *>(obedit->data), &params);
947
948#ifdef USE_NET_ISLAND_CONNECT
949 /* we may have remaining isolated regions remaining,
950 * these will need to have connecting edges created */
951 if (!BLI_stack_is_empty(edges_loose)) {
952 Map<BMFace *, LinkBase *> face_edge_map;
953
954 MemArena *mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
955
957
958 {
959 BMBVHTree *bmbvh = BKE_bmbvh_new(bm, em->looptris, BMBVH_RESPECT_SELECT, nullptr, false);
960
961 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
962 BM_elem_index_set(e, -1); /* set_dirty */
963 }
964
965 while (!BLI_stack_is_empty(edges_loose)) {
966 BLI_stack_pop(edges_loose, &e);
967 float e_center[3];
968 mid_v3_v3v3(e_center, e->v1->co, e->v2->co);
969
970 BMFace *f = BKE_bmbvh_find_face_closest(bmbvh, e_center, FLT_MAX);
971 if (f) {
972 ghash_insert_face_edge_link(face_edge_map, f, e, mem_arena);
973 BM_elem_index_set(e, BM_elem_index_get(f)); /* set_dirty */
974 }
975 }
976
977 BKE_bmbvh_free(bmbvh);
978 }
979
981
983
984 /* detect edges chains that span faces
985 * and splice vertices into the closest edges */
986 {
987
988 for (const auto &item : face_edge_map.items()) {
989 BMFace *f = item.key;
990 LinkBase *e_ls_base = item.value;
991 LinkNode *e_link = e_ls_base->list;
992
993 do {
994 e = static_cast<BMEdge *>(e_link->link);
995
996 for (int j = 0; j < 2; j++) {
997 BMVert *v_pivot = (&e->v1)[j];
998 /* checking that \a v_pivot isn't in the face prevents attempting
999 * to splice the same vertex into an edge from multiple faces */
1000 if (!BM_vert_in_face(v_pivot, f)) {
1001 float v_pivot_co[3];
1002 float v_pivot_fac;
1004 e, f, v_pivot, bm->ftable, bm->totface, v_pivot_co, &v_pivot_fac);
1005
1006 if (e_split) {
1007 /* for degenerate cases this vertex may be in one
1008 * of this edges radial faces */
1009 if (!bm_vert_in_faces_radial(v_pivot, e_split, f)) {
1010 BMEdge *e_new;
1011 BMVert *v_new = BM_edge_split(bm, e_split, e_split->v1, &e_new, v_pivot_fac);
1012 if (v_new) {
1013 /* we _know_ these don't share an edge */
1014 BM_vert_splice(bm, v_pivot, v_new);
1015 BM_elem_index_set(e_new, BM_elem_index_get(e_split));
1016 }
1017 }
1018 }
1019 }
1020 }
1021
1022 } while ((e_link = e_link->next));
1023 }
1024 }
1025
1026 {
1027 MemArena *mem_arena_edgenet = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1028
1029 for (const auto &item : face_edge_map.items()) {
1030 BMFace *f = item.key;
1031 LinkBase *e_ls_base = item.value;
1032
1034 bm, f, e_ls_base->list, e_ls_base->list_len, mem_arena_edgenet);
1035
1036 BLI_memarena_clear(mem_arena_edgenet);
1037 }
1038
1039 BLI_memarena_free(mem_arena_edgenet);
1040 }
1041
1042 BLI_memarena_free(mem_arena);
1043
1044 EDBMUpdate_Params params{};
1045 params.calc_looptris = true;
1046 params.calc_normals = true;
1047 params.is_destructive = true;
1048 EDBM_update(id_cast<Mesh *>(obedit->data), &params);
1049 }
1050
1051 BLI_stack_free(edges_loose);
1052#endif /* USE_NET_ISLAND_CONNECT */
1053
1055 }
1056 return OPERATOR_FINISHED;
1057}
1058
1060{
1061 /* identifiers */
1062 ot->name = "Weld Edges into Faces";
1063 ot->description = "Weld loose edges into faces (splitting them into new faces)";
1064 ot->idname = "MESH_OT_face_split_by_edges";
1065
1066 /* API callbacks. */
1069
1070 /* flags */
1072}
1073
1075
1076} // namespace blender
#define BLI_MEMARENA_STD_BUFSIZE
Object is a sort of wrapper for general info.
#define C
Definition RandGen.cpp:29
#define UI_ITEM_NONE
#define CLAMP(a, b, c)
#define UNUSED_VARS_NDEBUG(...)
#define AT
#define BLI_assert_msg(a, msg)
#define BM_elem_cb_check_hflag_enabled_simple(type, hflag_p)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Definition BLI_map.hh:620
ItemIterator items() const &
Definition BLI_map.hh:902
int64_t size() const
void append(const T &value)
bool is_empty() const
#define FLT_MAX
BMesh Iterators.
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
static int bm_face_isect_pair(BMFace *f, void *)
void BKE_bmbvh_free(BMBVHTree *tree)
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 bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
int RNA_enum_get(PointerRNA *ptr, const char *name)
@ RPT_WARNING
Definition BKE_report.hh:40
void EDBM_selectmode_flush(BMesh *bm, short selectmode)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
BMesh * BKE_editmesh_bmesh_get_for_write(Mesh *mesh)
Definition editmesh.cc:79
static void edbm_intersect_boolean_ui(bContext *, wmOperator *op)
static bool bm_vert_in_faces_radial(BMVert *v, BMEdge *e_radial, BMFace *f_ignore)
bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:253
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
struct BMFace * BKE_bmbvh_find_face_closest(const BMBVHTree *tree, const float co[3], float dist_max)
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition stack.cc:99
ATTR_WARN_UNUSED_RESULT const BMLoop * l
static void bm_face_split_by_edges_island_connect(BMesh *bm, BMFace *f, LinkNode *e_link, const int e_link_len, MemArena *mem_arena_edgenet)
bool BM_mesh_boolean(BMesh *, Span< std::array< BMLoop *, 3 > > looptris, int(*test_fn)(BMFace *, void *), void *, const int, const bool, const bool, const bool, const int)
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
static void edbm_intersect_select(Mesh *mesh, bool do_select)
void MESH_OT_intersect(wmOperatorType *ot)
void EDBM_update(Mesh *mesh, const EDBMUpdate_Params *params)
void BLI_stack_pop(BLI_Stack *stack, void *dst) ATTR_NONNULL()
Definition stack.cc:141
PropertyRNA * RNA_def_enum(StructOrFunctionRNA *cont_, const char *identifier, const EnumPropertyItem *items, const int default_value, const char *ui_name, const char *ui_description)
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
void BM_mesh_select_mode_flush(BMesh *bm)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ViewLayer * CTX_data_view_layer(const bContext *C)
BMBVHTree * BKE_bmbvh_new(struct BMesh *bm, Span< std::array< BMLoop *, 3 > > looptris, int flag, const float3 *cos_cage, bool cos_cage_free)
BMFace * BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del, BMFace **r_double)
Join Connected Faces.
static void ghash_insert_face_edge_link(Map< BMFace *, LinkBase * > &gh, BMFace *f_key, BMEdge *e_val, MemArena *mem_arena)
bool ED_operator_editmesh(bContext *C)
float angle_signed_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT
static wmOperatorStatus edbm_intersect_boolean_exec(bContext *C, wmOperator *op)
void BKE_report(ReportList *reports, eReportType type, const char *message)
Definition report.cc:162
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 BM_mesh_boolean_knife(BMesh *, Span< std::array< BMLoop *, 3 > > looptris, int(*test_fn)(BMFace *, void *), void *, const int, const bool, const bool, const bool, const bool)
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
void BM_face_select_set(BMesh *bm, BMFace *f, const bool select)
Select Face.
bool BM_vert_in_face(BMVert *v, BMFace *f)
@ BMESH_ISECT_BOOLEAN_DIFFERENCE
@ BMESH_ISECT_BOOLEAN_UNION
@ BMESH_ISECT_BOOLEAN_ISECT
void BM_mesh_separate_faces(BMesh *bm, BMFaceFilterFunc filter_fn, void *user_data)
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)
bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
bool RNA_boolean_get(PointerRNA *ptr, const char *name)
static BMEdge * bm_face_split_edge_find(BMEdge *e_a, BMFace *f_a, BMVert *v_pivot, BMFace **ftable, const int ftable_len, float r_v_pivot_co[3], float *r_v_pivot_fac)
static void bm_face_split_by_edges(BMesh *bm, BMFace *f, const char hflag, Vector< BMEdge *, 128 > *edge_net_temp_buf)
BMEditMesh * BKE_editmesh_from_object(Object *ob)
Return the BMEditMesh for a given object.
Definition editmesh.cc:59
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])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
float BM_edge_calc_length_squared(const BMEdge *e)
BMVert * BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float fac)
Edge Split.
Main * CTX_data_main(const bContext *C)
void MESH_OT_face_split_by_edges(wmOperatorType *ot)
static int bm_face_isect_self(BMFace *f, void *)
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)
Vector< Object * > BKE_view_layer_array_from_objects_in_edit_mode_unique_data(const Main &bmain, const Scene *scene, ViewLayer *view_layer, const View3D *v3d)
PropertyRNA * RNA_def_float_distance(StructOrFunctionRNA *cont_, const char *identifier, const float default_value, const float hardmin, const float hardmax, const char *ui_name, const char *ui_description, const float softmin, const float softmax)
bool BM_face_split_edgenet(BMesh *bm, BMFace *f, BMEdge **edge_net, const int edge_net_len, Vector< BMFace * > *r_face_arr)
int BM_face_share_vert_count(BMFace *f_a, BMFace *f_b)
void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL()
Definition stack.cc:135
bool EDBM_uvselect_clear(BMesh *bm)
static int bm_face_isect_pair_swap(BMFace *f, void *)
Scene * CTX_data_scene(const bContext *C)
@ OPTYPE_REGISTER
Definition WM_types.hh:188
@ OPTYPE_UNDO
Definition WM_types.hh:190
PropertyRNA * RNA_def_boolean(StructOrFunctionRNA *cont_, const char *identifier, const bool default_value, const char *ui_name, const char *ui_description)
static wmOperatorStatus edbm_face_split_by_edges_exec(bContext *C, wmOperator *)
static wmOperatorStatus edbm_intersect_exec(bContext *C, wmOperator *op)
static int bm_edge_sort_length_cb(const void *e_a_v, const void *e_b_v)
BLI_Stack * BLI_stack_new(size_t elem_size, const char *description) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:85
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
@ BM_ELEM_INTERNAL_TAG
float RNA_float_get(PointerRNA *ptr, const char *name)
View3D * CTX_wm_view3d(const bContext *C)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
static void edbm_intersect_ui(bContext *, wmOperator *op)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void MESH_OT_intersect_boolean(wmOperatorType *ot)
void BM_edge_select_set(BMesh *bm, BMEdge *e, const bool select)
Select Edge.
const btScalar eps
Definition poly34.cpp:11
#define fabsf
struct BMLoop * l
Array< std::array< BMLoop *, 3 > > looptris
struct BMLoop * next
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct BMEdge * e
struct LinkNode * next
void use_property_decorate_set(bool is_decorate)
void use_property_split_set(bool is_sep)
void prop(PointerRNA *ptr, PropertyRNA *prop, int index, int value, eUI_Item_Flag flag, std::optional< StringRef > name_opt, int icon, std::optional< StringRef > placeholder=std::nullopt)
void separator(float factor=1.0f, LayoutSeparatorType type=LayoutSeparatorType::Auto)
Layout & row(bool align)
wmOperatorStatus(*) exec(bContext *C, wmOperator *op) ATTR_WARN_UNUSED_RESULT
Definition WM_types.hh:1125
const char * description
Definition WM_types.hh:1115
void(*) ui(bContext *C, wmOperator *op)
Definition WM_types.hh:1176
bool(*) poll(bContext *C) ATTR_WARN_UNUSED_RESULT
Definition WM_types.hh:1165
struct ReportList * reports