Blender V5.3
bmo_dissolve.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
10
11#include <cmath>
12
13#include "MEM_guardedalloc.h"
14
15#include "BLI_math_vector_c.hh"
16#include "BLI_stack_c.hh"
17#include "BLI_vector.hh"
18
19#include "bmesh.hh"
20#include "bmesh_tools.hh"
21
23
24namespace blender {
25
26/* ***_ISGC: mark for garbage-collection */
27
28#define FACE_MARK 1
29#define FACE_ORIG 2
30#define FACE_NEW 4
31#define FACE_TAG 8
32
33#define EDGE_MARK 1
34#define EDGE_TAG 2
35#define EDGE_ISGC 8
40#define EDGE_CHAIN 16
41
42#define VERT_MARK 1
43#define VERT_MARK_PAIR 4
44#define VERT_TAG 2
45#define VERT_ISGC 8
46#define VERT_MARK_TEAR 16
47
48/* -------------------------------------------------------------------- */
51
53{
54 BMWalker regwalker;
55 BMIter liter2;
56 BMLoop *l2, *l3;
57 BMFace *f2;
58
59 /* Checks if there are any unmarked boundary edges in the face region. */
60
61 BMW_init(&regwalker,
62 bm,
70
71 for (f2 = static_cast<BMFace *>(BMW_begin(&regwalker, f)); f2;
72 f2 = static_cast<BMFace *>(BMW_step(&regwalker)))
73 {
74 BM_ITER_ELEM (l2, &liter2, f2, BM_LOOPS_OF_FACE) {
75 l3 = l2->radial_next;
77 if (!BMO_edge_flag_test(bm, l2->e, EDGE_MARK)) {
78 return false;
79 }
80 }
81 }
82 }
83 BMW_end(&regwalker);
84
85 return true;
86}
87
92{
93 BMEdge *e_pair[2];
94 const bool is_edge_pair = BM_vert_edge_pair(v, &e_pair[0], &e_pair[1]);
95
96 BLI_assert(is_edge_pair);
97 UNUSED_VARS_NDEBUG(is_edge_pair);
98
99 /* Compute the angle between the edges. Start with the raw angle. */
100 BMVert *v_a = BM_edge_other_vert(e_pair[0], v);
101 BMVert *v_b = BM_edge_other_vert(e_pair[1], v);
102 float angle = M_PI - angle_v3v3v3(v_a->co, v->co, v_b->co);
103
104 /* There are two ways to measure the angle around a vert with two edges. The first is to
105 * measure the raw angle between the two neighboring edges, the second is to measure the
106 * angle of the edges around the vertex normal vector. When the vert is an edge pair
107 * between two faces, The normal measurement is better in general. In the specific case of
108 * a vert between two faces, but the faces have a *very* sharp angle between them, then the
109 * raw angle is better, because the normal is perpendicular to average of the two faces,
110 * and if the faces are folded almost 180 degrees, the vertex normal becomes more an more
111 * edge-on to the faces, meaning the angle *around the normal* becomes more and more flat,
112 * even if it makes a sharp angle when viewed from the side.
113 *
114 * When the faces become very folded, the `raw_factor` adds some of the "as seen from the side"
115 * angle back into the computation, making the algorithm behave more intuitively.
116 *
117 * The `raw_factor` is computed as follows:
118 * - When not a face pair, part this is skipped, and the raw angle is used.
119 * - When a face pair is co-planar, or has an angle up to 90 degrees, `raw_factor` is 0.0.
120 * - As angle increases from 90 to 180 degrees, `raw_factor` increases from 0.0 to 1.0.
121 */
122 BMFace *f_pair[2];
123 if (BM_edge_face_pair(v->e, &f_pair[0], &f_pair[1])) {
124 /* Due to merges, the normals are not currently trustworthy. Compute them. */
125 float no_a[3], no_b[3];
126 BM_face_calc_normal(f_pair[0], no_a);
127 BM_face_calc_normal(f_pair[1], no_b);
128
129 /* Now determine the raw factor based on how folded the faces are. */
130 const float raw_factor = std::clamp(-dot_v3v3(no_a, no_b), 0.0f, 1.0f);
131
132 /* Blend the two ways of computing the angle. */
133 float normal_angle = M_PI - angle_on_axis_v3v3v3_v3(v_a->co, v->co, v_b->co, v->no);
134 angle = interpf(angle, normal_angle, raw_factor);
135 }
136
137 return angle;
138}
139
144
145{
146 /* Merge the header flags on the two edges that will be merged. */
147 BMEdge *e_pair[2];
148 const bool is_edge_pair = BM_vert_edge_pair(v, &e_pair[0], &e_pair[1]);
149
150 BLI_assert(is_edge_pair);
151 UNUSED_VARS_NDEBUG(is_edge_pair);
152
153 BM_elem_flag_merge_ex(e_pair[0], e_pair[1], BM_ELEM_HIDDEN);
154
155 /* Dissolve the vertex. */
156 BMEdge *e_new = BM_vert_collapse_edge(bm, v->e, v, do_del, true, true);
157
158 if (e_new) {
159 /* Ensure the result of dissolving never leaves visible edges connected to hidden vertices.
160 * From a user perspective this is an invalid state which tools should not allow. */
161 if (!BM_elem_flag_test(e_new, BM_ELEM_HIDDEN)) {
162 if (BM_elem_flag_test(e_new->v1, BM_ELEM_HIDDEN) ||
164 {
165 if (BM_elem_flag_test(e_new, BM_ELEM_SELECT)) {
166 BM_edge_select_set_noflush(bm, e_new, false);
167 }
169 }
170 }
171 }
172 return e_new;
173}
174
175static void bm_face_split(BMesh *bm, const short oflag, bool use_edge_delete)
176{
177 BLI_Stack *edge_delete_verts;
178 BMIter iter;
179 BMVert *v;
180
181 if (use_edge_delete) {
182 edge_delete_verts = BLI_stack_new(sizeof(BMVert *), __func__);
183 }
184
185 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
186 if (BMO_vert_flag_test(bm, v, oflag)) {
187 if (BM_vert_is_edge_pair(v) == false) {
188 BMIter liter;
189 BMLoop *l;
190 BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
191 if (l->f->len > 3) {
192 if (BMO_vert_flag_test(bm, l->next->v, oflag) == 0 &&
193 BMO_vert_flag_test(bm, l->prev->v, oflag) == 0)
194 {
195 BM_face_split(bm, l->f, l->next, l->prev, nullptr, nullptr, true);
196 }
197 }
198 }
199
200 if (use_edge_delete) {
201 BLI_stack_push(edge_delete_verts, &v);
202 }
203 }
204 }
205 }
206
207 if (use_edge_delete) {
208 while (!BLI_stack_is_empty(edge_delete_verts)) {
209 /* remove surrounding edges & faces */
210 BLI_stack_pop(edge_delete_verts, &v);
211 while (v->e) {
212 BM_edge_kill(bm, v->e);
213 }
214 }
215 BLI_stack_free(edge_delete_verts);
216 }
217}
218
220
221/* -------------------------------------------------------------------- */
224
226{
227 BMOIter oiter;
228 BMFace *f;
229 BMWalker regwalker;
230
231 const bool use_verts = BMO_slot_bool_get(op->slots_in, "use_verts");
232
233 if (use_verts) {
234 /* tag verts that start out with only 2 edges,
235 * don't remove these later */
236 BMIter viter;
237 BMVert *v;
238
239 BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
241 }
242 }
243
245
246 /* List of regions which are themselves a list of faces. */
248
249 /* collect region */
250 BMO_ITER (f, &oiter, op->slots_in, "faces", BM_FACE) {
251 if (!BMO_face_flag_test(bm, f, FACE_TAG)) {
252 continue;
253 }
254
255 BMW_init(&regwalker,
256 bm,
260 FACE_MARK,
261 /* no need to check BMW_FLAG_TEST_HIDDEN, faces are already marked by the bmo. */
265
266 /* Check there are at least two faces before creating the array. */
267 BMFace *faces_init[2];
268 if ((faces_init[0] = static_cast<BMFace *>(BMW_begin(&regwalker, f))) &&
269 (faces_init[1] = static_cast<BMFace *>(BMW_step(&regwalker))))
270 {
271 Vector<BMFace *> faces;
272 faces.append(faces_init[0]);
273 faces.append(faces_init[1]);
274
275 BMFace *f_iter;
276 while ((f_iter = static_cast<BMFace *>(BMW_step(&regwalker)))) {
277 faces.append(f_iter);
278 }
279
280 for (BMFace *face : faces) {
283 }
284
285 regions.append_as(std::move(faces));
286 }
287
288 BMW_end(&regwalker);
289 }
290
291 /* track how many faces we should end up with */
292 int totface_target = bm->totface;
293
294 for (Vector<BMFace *> &faces : regions) {
295 const int64_t faces_len = faces.size();
296
297 BMFace *f_double;
298
299 BMFace *f_new = BM_faces_join(bm, faces.data(), faces_len, true, &f_double);
300
301 if (f_new) [[likely]] {
302
303 /* All the joined faces are gone and the fresh f_new represents their union. */
304 totface_target -= faces_len - 1;
305
306 if (f_double) [[unlikely]] {
307 /* `BM_faces_join()` succeeded, but there is a double. Keep the pre-existing face
308 * and retain its custom-data. Remove the newly made merge result. */
309 BM_face_kill(bm, f_new);
310 totface_target -= 1;
311 f_new = f_double;
312 }
313
314 /* Un-mark the joined face to ensure it is not garbage collected later. */
316
317 /* Mark the joined face so it can be added to the selection later. */
319 }
320 else {
321 /* `BM_faces_join()` failed. */
322
323 /* NOTE: prior to 3.0 this raised an error: "Could not create merged face".
324 * Change behavior since it's not useful to fail entirely when a single face-group
325 * can't be merged into one face. Continue with other face groups instead.
326 *
327 * This could optionally do a partial merge, where some faces are joined. */
328
329 /* Prevent these faces from being removed. */
330 for (BMFace *face : faces) {
332 }
333 }
334 }
335
336 /* Typically no faces need to be deleted */
337 if (totface_target != bm->totface) {
338 BMO_op_callf(bm, op->flag, "delete geom=%ff context=%i", FACE_ORIG, DEL_FACES);
339 }
340
341 if (use_verts) {
342 BMIter viter;
343 BMVert *v, *v_next;
344
345 BM_ITER_MESH_MUTABLE (v, v_next, &viter, bm, BM_VERTS_OF_MESH) {
347 continue;
348 }
349 if (BM_vert_is_edge_pair(v)) {
351 }
352 }
353 }
354
356
358}
359
369static BMVert *bmo_find_end_of_chain(BMesh *bm, BMEdge *e, BMVert *v, const short edge_oflag = 0)
370{
371 BMVert *v_init = v;
372
373 while (BM_vert_is_edge_pair(v)) {
374
375 /* Move one step down the chain. */
378
379 /* If we walk to an edge that has already been processed, there's no need to keep working.
380 * If `edge_oflag` is 0, this test never returns true,
381 * so iteration will truly go to the end. */
382 if (BMO_edge_flag_test(bm, e, edge_oflag)) {
383 return nullptr;
384 }
385
386 /* Optionally mark along the chain.
387 * If `edge_oflag` is 0, `hflag |= 0` is still faster than if + test + jump. */
388 BMO_edge_flag_enable(bm, e, edge_oflag);
389
390 /* While this should never happen in the context this function is called.
391 * Avoid an eternal loop even in the case of degenerate geometry. */
392 BLI_assert(v != v_init);
393 if (v == v_init) [[unlikely]] {
394 return nullptr;
395 }
396 }
397 return v;
398}
399
405{
406 /* If the vert was already tested and marked, don't test again. */
408 return false;
409 }
410
411 /* Check each face at this vert by checking each loop. */
412 BMIter iter;
413 BMLoop *l_a;
414 BM_ITER_ELEM (l_a, &iter, v, BM_LOOPS_OF_VERT) {
416
417 /* `l_a` and `l_b` are now the two edges of the face that share this vert.
418 * if both are untagged, return true. */
420 return true;
421 }
422 }
423
424 return false;
425}
426
431 BMVert *v,
432 const short edge_oflag,
433 const int max)
434{
435 int retval = 0;
436 BMIter iter;
437 BMEdge *e;
438 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
439 if (BMO_edge_flag_test(bm, e, edge_oflag)) {
440 retval++;
441 }
442 if (retval == max) {
443 return retval;
444 }
445 }
446 return retval;
447}
448
450{
451 /* Set the default not to limit dissolving at all. */
452 BMO_slot_float_set(op->slots_in, "angle_threshold", M_PI);
453}
454
456{
457 // BMOperator fop;
458 BMOIter eiter;
459 BMIter iter;
460 BMEdge *e, *e_next;
461 BMVert *v, *v_next;
462
463 /* Even when geometry has exact angles like 0 or 90 or 180 deg, `angle_on_axis_v3v3v3_v3`
464 * can return slightly incorrect values due to cos/sin functions, floating point error, etc.
465 * This lets the test ignore that tiny bit of math error so users won't notice. */
466 const float angle_epsilon = RAD2DEGF(0.0001f);
467
468 const float angle_threshold = BMO_slot_float_get(op->slots_in, "angle_threshold");
469
470 /* Use verts when told to... except, do *not* use verts when angle_threshold is 0.0. */
471 const bool use_verts = BMO_slot_bool_get(op->slots_in, "use_verts") &&
472 (angle_threshold > angle_epsilon);
473
474 /* If angle threshold is 180, don't bother with angle math, just dissolve everything. */
475 const bool dissolve_all = (angle_threshold > M_PI - angle_epsilon);
476
477 const bool use_face_split = BMO_slot_bool_get(op->slots_in, "use_face_split");
478
479 const bool use_preserve_quads = BMO_slot_bool_get(op->slots_in, "use_preserve_quads");
480
481 if (use_face_split || use_verts) {
483 }
484
485 /* Tag certain geometry around the selected edges, for later processing. */
486 BMO_ITER (e, &eiter, op->slots_in, "edges", BM_EDGE) {
487
488 /* Connected edge chains have endpoints with edge pairs. The existing behavior was to dissolve
489 * the verts, both in the middle, and at the ends, of any selected edges in chains. Mark these
490 * kind of edges, so we know to skip the angle threshold test later. */
491 if (BM_vert_is_edge_pair(e->v1) || BM_vert_is_edge_pair(e->v2)) {
493 }
494
495 BMFace *f_pair[2];
496 if (BM_edge_face_pair(e, &f_pair[0], &f_pair[1])) {
497 /* Tag all the edges and verts of the two faces on either side of this edge.
498 * This edge is going to be dissolved, and after that happens, some of those elements of the
499 * surrounding faces might end up as loose geometry, depending on how the dissolve affected
500 * geometry near them. Tag them `*_ISGC`, to be checked later, and cleaned up if loose. */
501 uint j;
502 for (j = 0; j < 2; j++) {
503 BMLoop *l_first, *l_iter;
504 l_iter = l_first = BM_FACE_FIRST_LOOP(f_pair[j]);
505 do {
508 } while ((l_iter = l_iter->next) != l_first);
509 }
510
511 /* If using verts, and this edge is part of a chain that will be dissolved, then extend
512 * `EDGE_TAG` to both ends of the chain. This marks any edges that, even though they might
513 * not be selected, will also be dissolved when the face merge happens. This allows counting
514 * how many edges will remain after the dissolves are done later. */
515 if (use_verts && BMO_edge_flag_test(bm, e, EDGE_CHAIN)) {
518 }
519 }
520 }
521
522 if (use_verts) {
523
524 /* Mark all verts that are candidates to be dissolved. */
525 BMO_ITER (e, &eiter, op->slots_in, "edges", BM_EDGE) {
526
527 /* Edges only dissolve if they are manifold, so if the edge won't be dissolved, then there's
528 * no reason to mark either of its ends for dissolve. */
529 BMFace *f_pair[2];
530 if (!BM_edge_face_pair(e, &f_pair[0], &f_pair[1])) {
531 continue;
532 }
533
534 /* if `BM_faces_join_pair` will be done, mark the correct two verts at the ends for
535 * dissolve. */
536 for (int i = 0; i < 2; i++) {
537 BMVert *v_edge = *((&e->v1) + i);
538
539 /* An edge between two triangles should dissolve to a quad, akin to un-triangulate.
540 * Prevent dissolving either corner, if doing so would collapse the corner, converting
541 * the quad to a triangle or wire. This happens when two triangles join, and the vert
542 * has two untagged edges, and the _only_ other tagged edge is this edge that's about
543 * to be dissolved. When that case is found, skip it, do not tag it.
544 * The edge count test ensures that if we're dissolving a chain, the crossing loop cuts
545 * will still be dissolved, even if they happen to make an "un-triangulate" case.
546 * This is not done when face split is active, because face split often creates triangle
547 * pairs on edges that touch boundaries, resulting in the boundary vert not dissolving. */
548 if (use_preserve_quads && f_pair[0]->len == 3 && f_pair[1]->len == 3 &&
550 {
551 continue;
552 }
553
554 /* If a chain, follow the chain until the end is found. The whole chain will dissolve, so
555 * the test needs to happen there, at the end of the chain, where it meets other geometry,
556 * not here, at the end of a selected edge that only touches other parts of the chain. */
557 if (BM_vert_is_edge_pair(v_edge)) {
558 v_edge = bmo_find_end_of_chain(bm, e, v_edge, EDGE_CHAIN);
559 }
560
561 /* If the end of the chain was searched for and was not located, take no action. */
562 if (v_edge == nullptr) {
563 continue;
564 }
565
566 /* When the user selected multiple edges that meet at one vert, and there are existing
567 * faces at that vert that are *not* selected, then remove that vert from consideration for
568 * dissolve.
569 *
570 * This logic implements the following:
571 * - When several dissolved edges cross a loop cut, the loop cut vert should be dissolved.
572 * (`bmo_vert_touches_unselected_face()` will be false).
573 * - When dissolve edges *end* at a T on a loop cut, the loop cut vert should be dissolved.
574 * (`bmo_vert_tagged_edges_count_at_most()` will be 1).
575 * - When multiple dissolve edges touch the corner of a quad or triangle, but leave in a
576 * different direction, regard that contact is 'incidental' and the face should stay.
577 * (both tests will be true).
578 */
581 {
582 continue;
583 }
584
585 /* Mark for dissolve. */
587 }
588 }
589 }
590
591 if (use_face_split) {
592 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
593 BMIter itersub;
594 int untag_count = 0;
595 BM_ITER_ELEM (e, &itersub, v, BM_EDGES_OF_VERT) {
597 untag_count++;
598 }
599 }
600
601 /* check that we have 2 edges remaining after dissolve */
602 if (untag_count <= 2) {
604 }
605 }
606
607 bm_face_split(bm, VERT_TAG, false);
608 }
609
610 /* Merge any face pairs that straddle a selected edge. */
611 BMO_ITER (e, &eiter, op->slots_in, "edges", BM_EDGE) {
612 BMLoop *l_a, *l_b;
613 if (BM_edge_loop_pair(e, &l_a, &l_b)) {
614 BM_faces_join_pair(bm, l_a, l_b, false, nullptr);
615 }
616 }
617
618 /* Cleanup geometry. Remove any edges that are garbage collectible and that have became
619 * irrelevant (no loops) because of face merges. */
620 BM_ITER_MESH_MUTABLE (e, e_next, &iter, bm, BM_EDGES_OF_MESH) {
621 if ((e->l == nullptr) && BMO_edge_flag_test(bm, e, EDGE_ISGC)) {
622 BM_edge_kill(bm, e);
623 }
624 }
625
626 /* Cleanup geometry. Remove any verts that are garbage collectible and that have became
627 * isolated verts (no edges) because of edge dissolves. */
628 BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
629 if ((v->e == nullptr) && BMO_vert_flag_test(bm, v, VERT_ISGC)) {
630 BM_vert_kill(bm, v);
631 }
632 }
633
634 /* If dissolving verts, then evaluate each VERT_MARK vert. */
635 if (use_verts) {
636 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
638 continue;
639 }
640
641 /* If it is not an edge pair, it cannot be merged. */
642 BMEdge *e_pair[2];
643 if (BM_vert_edge_pair(v, &e_pair[0], &e_pair[1]) == false) {
645 continue;
646 }
647
648 /* At an angle threshold of 180, dissolve everything, skip the math of the angle test. */
649 if (dissolve_all) {
650 /* VERT_MARK remains enabled. */
651 continue;
652 }
653
654 /* Verts in edge chains ignore the angle test. This maintains the previous behavior,
655 * where such verts were not subject to the angle threshold.
656 *
657 * When edge chains are selected for dissolve, all edge-pair verts at *both* ends of each
658 * selected edge will be dissolved, combining the selected edges into their neighbors.
659 *
660 * Note that when only *part* of a chain is selected, this *will* alter unselected edges,
661 * because selected edges will merge *into their unselected neighbors*. This too, has been
662 * maintained, for consistency with the previous (but possibly unintentional) behavior. */
663 if (BMO_edge_flag_test(bm, e_pair[0], EDGE_CHAIN) ||
664 BMO_edge_flag_test(bm, e_pair[1], EDGE_CHAIN))
665 {
666 /* VERT_MARK remains enabled. */
667 continue;
668 }
669
670 /* If the angle at the vert is larger than the threshold, it cannot be merged. */
671 if (bmo_vert_calc_edge_angle_blended(v) > angle_threshold - angle_epsilon) {
673 continue;
674 }
675 }
676
677 /* Dissolve all verts that remain tagged. This is done in a separate iteration pass. Otherwise
678 * the early dissolves would alter the angles measured at neighboring verts tested later. */
679 BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
681 continue;
682 }
683
684 /* Even though pairs were checked before, the process of performing edge merges
685 * might change a neighboring vert such that it is no longer an edge pair. */
686 if (!BM_vert_is_edge_pair(v)) {
687 continue;
688 }
689
691 }
692 }
693}
694
696{
697 BMOIter oiter;
698 BMIter iter;
699 BMVert *v, *v_next;
700 BMEdge *e, *e_next;
701
702 const bool use_face_split = BMO_slot_bool_get(op->slots_in, "use_face_split");
703 const bool use_boundary_tear = BMO_slot_bool_get(op->slots_in, "use_boundary_tear");
704
705 BMO_ITER (v, &oiter, op->slots_in, "verts", BM_VERT) {
707 }
708
709 if (use_face_split) {
710 bm_face_split(bm, VERT_MARK, false);
711 }
712
713 if (use_boundary_tear) {
714 BMO_ITER (v, &oiter, op->slots_in, "verts", BM_VERT) {
715 if (!BM_vert_is_edge_pair(v)) {
716 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
717 if (BM_edge_is_boundary(e)) {
719 break;
720 }
721 }
722 }
723 }
724
726 }
727
728 BMO_ITER (v, &oiter, op->slots_in, "verts", BM_VERT) {
729 BMIter itersub;
730 BMLoop *l_first;
731 BMEdge *e_first = nullptr;
732 BM_ITER_ELEM (l_first, &itersub, v, BM_LOOPS_OF_VERT) {
733 BMLoop *l_iter;
734 l_iter = l_first;
735 do {
738 } while ((l_iter = l_iter->next) != l_first);
739
740 e_first = l_first->e;
741 }
742
743 /* important e_first won't be deleted */
744 if (e_first) {
745 e = e_first;
746 do {
747 e_next = BM_DISK_EDGE_NEXT(e, v);
748 if (BM_edge_is_wire(e)) {
749 BM_edge_kill(bm, e);
750 }
751 } while ((e = e_next) != e_first);
752 }
753 }
754
755 BMO_ITER (v, &oiter, op->slots_in, "verts", BM_VERT) {
756 /* tag here so we avoid feedback loop (checking topology as we edit) */
757 if (BM_vert_is_edge_pair(v)) {
759 }
760 }
761
762 BMO_ITER (v, &oiter, op->slots_in, "verts", BM_VERT) {
763 BMIter itersub;
764
765 /* Merge across every edge that touches `v`. This does a `BM_faces_join_pair()` for each edge.
766 * There may be a possible performance improvement available here, for high valence verts.
767 * Collecting a list of 20 faces and performing a single `BM_faces_join` would almost certainly
768 * more performant than doing 19 separate `BM_faces_join_pair()` of 2 faces each in sequence.
769 * Low valence verts would need benchmarking, to check that such a change isn't harmful. */
771 BM_ITER_ELEM (e, &itersub, v, BM_EDGES_OF_VERT) {
772 BMLoop *l_a, *l_b;
773 if (BM_edge_loop_pair(e, &l_a, &l_b)) {
774 BM_faces_join_pair(bm, l_a, l_b, false, nullptr);
775 }
776 }
777 }
778 }
779
780 /* Cleanup geometry (#BM_faces_join_pair, but it removes geometry we're looping on)
781 * so do this in a separate pass instead. */
782 BM_ITER_MESH_MUTABLE (e, e_next, &iter, bm, BM_EDGES_OF_MESH) {
783 if ((e->l == nullptr) && BMO_edge_flag_test(bm, e, EDGE_ISGC)) {
784 BM_edge_kill(bm, e);
785 }
786 }
787
788 /* final cleanup */
789 BMO_ITER (v, &oiter, op->slots_in, "verts", BM_VERT) {
790 if (BM_vert_is_edge_pair(v)) {
792 }
793 }
794
795 BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
796 if ((v->e == nullptr) && BMO_vert_flag_test(bm, v, VERT_ISGC)) {
797 BM_vert_kill(bm, v);
798 }
799 }
800 /* done with cleanup */
801}
802
804{
805 BMOpSlot *einput = BMO_slot_get(op->slots_in, "edges");
806 BMOpSlot *vinput = BMO_slot_get(op->slots_in, "verts");
807 const float angle_max = M_PI_2;
808 const float angle_limit = min_ff(angle_max, BMO_slot_float_get(op->slots_in, "angle_limit"));
809 const bool do_dissolve_boundaries = BMO_slot_bool_get(op->slots_in, "use_dissolve_boundaries");
810 const BMO_Delimit delimit = BMO_Delimit(BMO_slot_int_get(op->slots_in, "delimit"));
811
813 angle_limit,
814 do_dissolve_boundaries,
815 delimit,
816 reinterpret_cast<BMVert **> BMO_SLOT_AS_BUFFER(vinput),
817 vinput->len,
818 reinterpret_cast<BMEdge **> BMO_SLOT_AS_BUFFER(einput),
819 einput->len,
820 FACE_NEW);
821
823}
824
825#define EDGE_MARK 1
826#define EDGE_COLLAPSE 2
827
828static void bm_mesh_edge_collapse_flagged(BMesh *bm, const int flag, const short oflag)
829{
830 BMO_op_callf(bm, flag, "collapse edges=%fe uvs=%b", oflag, true);
831}
832
834{
835 const float dist = BMO_slot_float_get(op->slots_in, "dist");
836 const float dist_sq = dist * dist;
837
838 bool found;
839 BMIter eiter;
840 BMEdge *e;
841
843
844 /* collapse zero length edges, this accounts for zero area faces too */
845 found = false;
846 BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
848 if (BM_edge_calc_length_squared(e) < dist_sq) {
850 found = true;
851 }
852 }
853
854 /* clear all loop tags (checked later) */
855 if (e->l) {
856 BMLoop *l_iter, *l_first;
857 l_iter = l_first = e->l;
858 do {
860 } while ((l_iter = l_iter->radial_next) != l_first);
861 }
862 }
863
864 if (found) {
866 }
867
868 /* clip degenerate ears from the face */
869 found = false;
870 BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
871 if (e->l && BMO_edge_flag_test(bm, e, EDGE_MARK)) {
872 BMLoop *l_iter, *l_first;
873 l_iter = l_first = e->l;
874 do {
875 if (
876 /* check the loop hasn't already been tested (and flag not to test again) */
877 !BM_elem_flag_test(l_iter, BM_ELEM_TAG) &&
878 ((void)BM_elem_flag_enable(l_iter, BM_ELEM_TAG),
879
880 /* check we're marked to tested (radial edge already tested) */
881 BMO_edge_flag_test(bm, l_iter->prev->e, EDGE_MARK) &&
882
883 /* check edges are not already going to be collapsed */
884 !BMO_edge_flag_test(bm, l_iter->e, EDGE_COLLAPSE) &&
886 {
887 /* test if the faces loop (ear) is degenerate */
888 float dir_prev[3], len_prev;
889 float dir_next[3], len_next;
890
891 sub_v3_v3v3(dir_prev, l_iter->prev->v->co, l_iter->v->co);
892 sub_v3_v3v3(dir_next, l_iter->next->v->co, l_iter->v->co);
893
894 len_prev = normalize_v3(dir_prev);
895 len_next = normalize_v3(dir_next);
896
897 if ((len_v3v3(dir_prev, dir_next) * min_ff(len_prev, len_next)) <= dist) {
898 bool reset = false;
899
900 if (fabsf(len_prev - len_next) <= dist) {
901 /* both edges the same length */
902 if (l_iter->f->len == 3) {
903 /* ideally this would have been discovered with short edge test above */
905 found = true;
906 }
907 else {
908 /* add a joining edge and tag for removal */
909 BMLoop *l_split;
910 if (BM_face_split(
911 bm, l_iter->f, l_iter->prev, l_iter->next, &l_split, nullptr, true))
912 {
914 found = true;
915 reset = true;
916 }
917 }
918 }
919 else if (len_prev < len_next) {
920 /* split 'l_iter->e', then join the vert with next */
921 BMVert *v_new;
922 BMEdge *e_new;
923 BMLoop *l_split;
924 v_new = BM_edge_split(bm, l_iter->e, l_iter->v, &e_new, len_prev / len_next);
925 BLI_assert(v_new == l_iter->next->v);
926 (void)v_new;
927 if (BM_face_split(
928 bm, l_iter->f, l_iter->prev, l_iter->next, &l_split, nullptr, true))
929 {
931 found = true;
932 }
933 reset = true;
934 }
935 else if (len_next < len_prev) {
936 /* split 'l_iter->prev->e', then join the vert with next */
937 BMVert *v_new;
938 BMEdge *e_new;
939 BMLoop *l_split;
940 v_new = BM_edge_split(bm, l_iter->prev->e, l_iter->v, &e_new, len_next / len_prev);
941 BLI_assert(v_new == l_iter->prev->v);
942 (void)v_new;
943 if (BM_face_split(
944 bm, l_iter->f, l_iter->prev, l_iter->next, &l_split, nullptr, true))
945 {
947 found = true;
948 }
949 reset = true;
950 }
951
952 if (reset) {
953 /* we can't easily track where we are on the radial edge, reset! */
954 l_first = l_iter;
955 }
956 }
957 }
958 } while ((l_iter = l_iter->radial_next) != l_first);
959 }
960 }
961
962 if (found) {
964 }
965}
966
968
969} // namespace blender
#define M_PI_2
#define RAD2DEGF(_rad)
#define M_PI
Read Blender memory allocation and freeing.
#define UNUSED_FUNCTION(x)
#define UNUSED_VARS_NDEBUG(...)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_flag_merge_ex(ele_a, ele_b, hflag_and)
#define BM_elem_flag_disable(ele, hflag)
#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_MUTABLE(ele, ele_next, iter, bm, itype)
#define BMO_vert_flag_disable(bm, e, oflag)
#define BMO_edge_flag_test(bm, e, oflag)
#define BMO_edge_flag_enable(bm, e, oflag)
#define BMO_vert_flag_enable(bm, e, oflag)
#define BMO_vert_flag_set(bm, e, oflag, val)
#define BMO_SLOT_AS_BUFFER(slot)
#define BMO_face_flag_enable(bm, e, oflag)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
#define BMO_vert_flag_test(bm, e, oflag)
#define BMO_face_flag_disable(bm, e, oflag)
#define BMO_face_flag_test(bm, e, oflag)
#define BMW_NIL_LAY
#define BMW_MASK_NOP
#define FACE_MARK
#define EDGE_MARK
Definition bmo_bridge.cc:28
#define FACE_TAG
#define VERT_MARK
#define VERT_MARK_TEAR
#define FACE_ORIG
#define FACE_NEW
#define VERT_TAG
#define EDGE_TAG
#define EDGE_ISGC
#define EDGE_CHAIN
#define VERT_ISGC
#define EDGE_COLLAPSE
#define VERT_MARK_PAIR
btScalar max
void reset()
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
void append(const T &value)
void append_as(ForwardValue &&...value)
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
BMesh Iterators.
MINLINE float min_ff(float a, float b)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
bool BMO_error_occurred_at_level(BMesh *bm, eBMOpErrorLevel level)
int BMO_slot_int_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
__int64 int64_t
Definition BKE_text.h:90
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
bool BLI_stack_is_empty(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:253
unsigned int uint
Definition BKE_text.h:55
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition stack.cc:99
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void BM_vert_kill(BMesh *bm, BMVert *v)
void * BMW_begin(BMWalker *walker, void *start)
@ BMW_ISLAND_MANIFOLD
float BMO_slot_float_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void BMO_slot_buffer_flag_enable(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
BMO_FLAG_BUFFER.
float angle_v3v3v3(const float a[3], const float b[3], const float c[3]) ATTR_WARN_UNUSED_RESULT
static int bmo_vert_tagged_edges_count_at_most(BMesh *bm, BMVert *v, const short edge_oflag, const int max)
void BMW_init(BMWalker *walker, BMesh *bm, int type, short mask_vert, short mask_edge, short mask_face, BMWFlag flag, int layer, BMWDelimitFlag delimit)
Initialize Walker.
void BLI_stack_pop(BLI_Stack *stack, void *dst) ATTR_NONNULL()
Definition stack.cc:141
void BMO_slot_float_set(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, float f)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static BMVert * bmo_find_end_of_chain(BMesh *bm, BMEdge *e, BMVert *v, const short edge_oflag=0)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BMFace * BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del, BMFace **r_double)
Join Connected Faces.
static void bm_mesh_edge_collapse_flagged(BMesh *bm, const int flag, const short oflag)
void bmo_dissolve_degenerate_exec(BMesh *bm, BMOperator *op)
float angle_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT
void BM_mesh_decimate_dissolve_ex(BMesh *bm, float angle_limit, bool do_dissolve_boundaries, BMO_Delimit delimit, BMVert **vinput_arr, int vinput_len, BMEdge **einput_arr, int einput_len, short oflag_out)
static void bm_face_split(BMesh *bm, const short oflag, bool use_edge_delete)
static bool UNUSED_FUNCTION check_hole_in_region(BMesh *bm, BMFace *f)
void BMW_end(BMWalker *walker)
End Walker.
void BM_edge_kill(BMesh *bm, BMEdge *e)
void bmo_dissolve_faces_exec(BMesh *bm, BMOperator *op)
void BMO_slot_buffer_from_enabled_flag(BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
void bmo_dissolve_limit_exec(BMesh *bm, BMOperator *op)
void bmo_dissolve_edges_init(BMOperator *op)
void bmo_dissolve_verts_exec(BMesh *bm, BMOperator *op)
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
bool BMO_op_callf(BMesh *bm, int flag, const char *fmt,...)
static float bmo_vert_calc_edge_angle_blended(const BMVert *v)
bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
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.
BMOpSlot * BMO_slot_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identifier)
BMESH OPSTACK GET SLOT.
MINLINE float normalize_v3(float n[3])
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void bmo_dissolve_edges_exec(BMesh *bm, BMOperator *op)
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
MINLINE void sub_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.
void BM_face_kill(BMesh *bm, BMFace *f)
BMFace * BM_face_split(BMesh *bm, BMFace *f, BMLoop *l_a, BMLoop *l_b, BMLoop **r_l, BMEdge *example, const bool no_double)
Face Split.
float BM_face_calc_normal(const BMFace *f, float r_no[3])
BMESH UPDATE FACE NORMAL.
bool BM_vert_is_edge_pair(const BMVert *v)
void * BMW_step(BMWalker *walker)
Step Walker.
static bool bmo_vert_touches_unselected_face(BMesh *bm, BMVert *v)
bool BM_vert_edge_pair(const BMVert *v, BMEdge **r_e_a, BMEdge **r_e_b)
MINLINE float interpf(float target, float origin, float t)
void BLI_stack_push(BLI_Stack *stack, const void *src) ATTR_NONNULL()
Definition stack.cc:135
BMFace * BM_faces_join_pair(BMesh *bm, BMLoop *l_a, BMLoop *l_b, const bool do_del, BMFace **r_double)
Faces Join Pair.
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
ATTR_WARN_UNUSED_RESULT const BMFlagLayer const short oflag
@ BMO_ERROR_FATAL
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
void BM_edge_select_set_noflush(BMesh *bm, BMEdge *e, const bool select)
static BMEdge * bm_vert_collapse_edge_and_merge(BMesh *bm, BMVert *v, const bool do_del)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
BMLoop * BM_loop_other_edge_loop(BMLoop *l, BMVert *v)
#define fabsf
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]