Blender V5.3
bmesh_decimate_unsubdivide.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 <algorithm>
12#include <optional>
13
14#include "MEM_guardedalloc.h"
15
16#include "BLI_array.hh"
17
18#include "bmesh.hh"
19#include "bmesh_decimate.hh" /* own include */
20
21namespace blender {
22
27constexpr int VERT_DISSOLVE_MAX = 4;
28
56
58 BMEdge **v_edges,
59 const int v_edges_num,
60 BMLoop *v_loops[VERT_DISSOLVE_MAX])
61{
62 int v_loops_num = 0;
63 for (int i = 0; i < v_edges_num; i++) {
64 const BMEdge *e = v_edges[i];
65 if (e->l != nullptr) {
66 BMLoop *l_radial_iter = e->l;
67 do {
68 if (l_radial_iter->v == v) {
69 /* Shouldn't be exceeded, more of a guard against corrupt topology. */
70 if (v_loops_num == VERT_DISSOLVE_MAX) [[unlikely]] {
72 return v_loops_num;
73 }
74 v_loops[v_loops_num++] = l_radial_iter;
75 }
76 } while ((l_radial_iter = l_radial_iter->radial_next) != e->l);
77 }
78 }
79 return v_loops_num;
80}
81
83 const int v_loops_all_num)
84{
85 BMEdge *edges_from_loop_ear[VERT_DISSOLVE_MAX];
86 uint edges_from_loop_ear_num = 0;
87
88 for (int i = 0; i < v_loops_all_num; i++) {
89 BMLoop *l = v_loops_all[i];
90 BMEdge *e_opposite;
91 if (l->f->len > 3) {
92 e_opposite = BM_edge_exists(l->prev->v, l->next->v);
93 if (e_opposite == nullptr) {
94 return false;
95 }
96 if (edges_from_loop_ear_num == VERT_DISSOLVE_MAX) {
97 return false;
98 }
99 }
100 else {
101 e_opposite = l->next->e;
102 }
103 edges_from_loop_ear[edges_from_loop_ear_num++] = e_opposite;
104 }
105
106 if (edges_from_loop_ear_num >= 3) {
107 if (BM_face_exists_multi_edge(edges_from_loop_ear, edges_from_loop_ear_num)) {
108 return true;
109 }
110 }
111
112 return false;
113}
114
125 const int v_loops_all_num)
126{
127 for (int i = 0; i < v_loops_all_num; i++) {
128 BMLoop *l = v_loops_all[i];
129 if (l->f->len > 3) {
131 return true;
132 }
133 }
134 }
135 return false;
136}
137
154 const int v_loops_all_num)
155{
156 BLI_assert(v_loops_all_num <= VERT_DISSOLVE_MAX);
157 if (v_loops_all_num < 2) {
158 return false;
159 }
160
161 BMLoop *v_loops[VERT_DISSOLVE_MAX];
162 int v_loops_num = 0;
163 for (int i = 0; i < v_loops_all_num; i++) {
164 BLI_assert(v_loops_all[i]->v == v_loops_all[0]->v);
165 BMLoop *l = v_loops_all[i];
166 if (l->f->len > 3) {
167 v_loops[v_loops_num++] = l;
168 }
169 }
170 if (v_loops_num < 2) {
171 return false;
172 }
173
174 std::ranges::sort(v_loops, v_loops + v_loops_num, {}, [](const BMLoop *l) { return l->f->len; });
175
177
178 /* Return the vertices left forming a face when the central vertex is collapsed out,
179 * canonicalized so two faces that collapse to the same loop compare equal. */
180 auto verts_canonical_collapsed_fn = [](const BMLoop *l_vert) -> VertArray {
181 const int verts_num = l_vert->f->len - 1;
182 VertArray verts(verts_num, NoInitialization());
183 int verts_index = 0;
184 for (const BMLoop *l = l_vert->next; l != l_vert; l = l->next) {
185 verts[verts_index++] = l->v;
186 }
187 BLI_assert(verts_index == verts_num);
188
189 /* Canonicalize using the minimum pointer, with the order
190 * defined by the next adjacent minimum. */
191 int i_min = 0;
192 for (int i = 1; i < verts_num; i++) {
193 if (verts[i] < verts[i_min]) {
194 i_min = i;
195 }
196 }
197 const int i_next = (i_min + 1 == verts_num) ? 0 : i_min + 1;
198 const int i_prev = (i_min == 0) ? verts_num - 1 : i_min - 1;
199 /* A step of `verts_num - 1` moves one place backward & wraps. */
200 const int step = (verts[i_next] < verts[i_prev]) ? 1 : (verts_num - 1);
201
202 VertArray verts_ordered(verts_num, NoInitialization());
203 for (int i = 0, j = i_min; i < verts_num; i++) {
204 verts_ordered[i] = verts[j];
205 j += step;
206 if (j >= verts_num) {
207 j -= verts_num;
208 }
209 }
210 return verts_ordered;
211 };
212
213 /* Only perform the relatively expensive unique face checks for
214 * groups of faces with matching numbers of sides. */
215 for (int group_beg = 0; group_beg < v_loops_num;) {
216 const int group_f_len = v_loops[group_beg]->f->len;
217 int group_end = group_beg + 1;
218 while (group_end < v_loops_num && v_loops[group_end]->f->len == group_f_len) {
219 group_end++;
220 }
221
222 const int group_len = group_end - group_beg;
223 if (group_len >= 2) {
224 VertArray collapsed[VERT_DISSOLVE_MAX];
225 for (int i = 0; i < group_len; i++) {
226 collapsed[i] = verts_canonical_collapsed_fn(v_loops[group_beg + i]);
227 }
228 for (int i = 0; i + 1 < group_len; i++) {
229 for (int j = i + 1; j < group_len; j++) {
230 if (std::ranges::equal(collapsed[i], collapsed[j])) {
231 return true;
232 }
233 }
234 }
235 }
236 group_beg = group_end;
237 }
238 return false;
239}
240
256static std::optional<VertDissolveMethod> bm_vert_dissolve_fan_or_chain_test(
257 BMVert *v,
258 const bool check_for_duplicates,
259 BMLoop *v_loops[VERT_DISSOLVE_MAX],
260 int *v_loops_num_p)
261{
262 BMIter iter;
263 BMEdge *e;
264
265 /* All edges connected to `v`. */
266 BMEdge *v_edges[VERT_DISSOLVE_MAX];
267
268 /* Boundary edges, only check for 2 because cases with more than 2 are ignored. */
269 BMEdge *e_boundary[2];
270 uint e_boundary_num = 0;
271
272 uint tot_edge = 0;
273 uint tot_edge_boundary = 0;
274 uint tot_edge_manifold = 0;
275 uint tot_edge_wire = 0;
276
277 /* In this loop we try to bail out early and gather data to be used later.
278 * Avoid expensive queries up front. */
279 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
280 if (BM_edge_is_boundary(e)) {
281 if (e_boundary_num < ARRAY_SIZE(e_boundary)) {
282 e_boundary[e_boundary_num] = e;
283 }
284 e_boundary_num++;
285 tot_edge_boundary++;
286 }
287 else if (BM_edge_is_manifold(e)) {
288 tot_edge_manifold++;
289 }
290 else if (BM_edge_is_wire(e)) {
291 tot_edge_wire++;
292 }
293 else {
294 return std::nullopt;
295 }
296
297 if (tot_edge == VERT_DISSOLVE_MAX) {
298 return std::nullopt;
299 }
300
301 v_edges[tot_edge] = e;
302 tot_edge++;
303 }
304
305 if (((tot_edge == 4) && (tot_edge_boundary == 0) && (tot_edge_manifold == 4)) ||
306 ((tot_edge == 3) && (tot_edge_boundary == 0) && (tot_edge_manifold == 3)))
307 {
308 if (check_for_duplicates) {
309 const int v_loops_num = bm_vert_loops_from_vert_edges(v, v_edges, tot_edge, v_loops);
310
311 /* Check the corners around `v` don't already form a face. */
312 if (bm_vert_dissolve_fan_makes_double_whole_face(v_loops, v_loops_num)) {
313 return std::nullopt;
314 }
315
316 /* Check if splits would create a duplicate (with existing or between each other). */
317 if (bm_vert_dissolve_fan_makes_double_with_existing(v_loops, v_loops_num) ||
319 {
320 return std::nullopt;
321 }
322
323 *v_loops_num_p = v_loops_num;
324 }
326 }
327 if ((tot_edge == 3) && (tot_edge_boundary == 2) && (tot_edge_manifold == 1)) {
328 if (check_for_duplicates) {
329 BLI_assert(e_boundary_num == 2);
330
331 if (const BMEdge *e_span = BM_edge_exists(BM_edge_other_vert(e_boundary[0], v),
332 BM_edge_other_vert(e_boundary[1], v)))
333 {
334 if (e_span->l) {
335 /* Boundary dissolving connects the two boundary edges into `e_span`.
336 * When `e_span` exists with a face, the dissolve may join across it.
337 * In isolation that is "ok" - however it means the dissolve may remove vertices
338 * other than `v`, causing the main un-subdivide loop to operate on freed geometry.
339 *
340 * NOTE(@ideasman42): If this was an important use case it's possible to inspect the
341 * topology and only reject dissolving when it would cause problems.
342 * However the situations where this occurs are not so important to support
343 * as they tend to be caused by overlapping/bow-tie faces.
344 * So it's simpler to reject them. */
345 return std::nullopt;
346 }
347 }
348
349 const int v_loops_num = bm_vert_loops_from_vert_edges(v, v_edges, tot_edge, v_loops);
350
351 /* Check if splits would create a duplicate (with existing or between each other). */
352 if (bm_vert_dissolve_fan_makes_double_with_existing(v_loops, v_loops_num) ||
354 {
355 return std::nullopt;
356 }
357
358 *v_loops_num_p = v_loops_num;
359 }
361 }
362 if ((tot_edge == 2) && (tot_edge_wire == 2)) {
364 }
365 if ((tot_edge == 2) && (tot_edge_manifold == 2)) {
367 }
368 return std::nullopt;
369}
370
375{
376 /* Re-test if dissolve is possible.
377 * The surrounding geometry may have changed since the first check,
378 * the first call also skips expensive degeneracy checks for this very reason. */
379 BMLoop *v_loops[VERT_DISSOLVE_MAX];
380 int v_loops_num = 0;
381 const std::optional<VertDissolveMethod> dissolve = bm_vert_dissolve_fan_or_chain_test(
382 v, true, v_loops, &v_loops_num);
383 if (!dissolve) {
384 return false;
385 }
386
387 switch (*dissolve) {
390 return (BM_vert_collapse_edge(bm, v->e, v, true, true, true) != nullptr);
391 }
394 for (int i = 0; i < v_loops_num; i++) {
395 BMLoop *l = v_loops[i];
396 if (l->f->len > 3) {
397 BMLoop *l_new;
398 BLI_assert(l->prev->v != l->next->v);
399 /* Must have been rejected by #bm_vert_dissolve_fan_or_chain_test.
400 * NOTE(@ideasman42): Assert because it's theoretically possible an edit
401 * in this loop creates a duplicate (although incredibly unlikely). */
403 BM_face_split(bm, l->f, l->prev, l->next, &l_new, nullptr, true);
404 BM_elem_flag_merge_into(l_new->e, l->e, l->prev->e);
405 }
406 }
407 return BM_vert_dissolve(bm, v);
408 }
409 }
410
411 return false;
412}
413
418enum {
422};
423
438static void bm_tag_untagged_neighbors(BMVert *verts_start[],
439 const uint verts_start_num,
440 const int desired_tag,
441 BMVert *r_verts_tagged[],
442 uint &r_verts_tagged_num)
443{
444
445 BMEdge *e;
446 BMIter iter;
447 r_verts_tagged_num = 0;
448
449 for (int i = 0; i < verts_start_num; i++) {
450 BMVert *v = verts_start[i];
451
452 /* Since DO_COLLAPSE and IGNORE are -1 and +1, inverting the sign finds the other. */
453 BLI_assert(BM_elem_index_get(v) == -desired_tag);
454
455 BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
456 BMVert *v_other = BM_edge_other_vert(e, v);
457 if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) {
458 BM_elem_index_set(v_other, desired_tag); /* set_dirty! */
459 r_verts_tagged[r_verts_tagged_num++] = v_other;
460 }
461 }
462 }
463}
464
465/* - BMVert.flag & BM_ELEM_TAG: shows we touched this vert
466 * - BMVert.index == -1: shows we will remove this vert
467 */
468
469void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, const int iterations, const bool tag_only)
470{
471 /* NOTE: while #BMWalker seems like a logical choice, it results in uneven geometry. */
472
473 BMVert **verts_collapse = MEM_new_array_uninitialized<BMVert *>(bm->totvert, __func__);
474 BMVert **verts_ignore = MEM_new_array_uninitialized<BMVert *>(bm->totvert, __func__);
475 uint verts_collapse_num = 0;
476 uint verts_ignore_num = 0;
477
478 BMIter iter;
479
480 int iter_step;
481
482 /* if tag_only is set, we assume the caller knows what verts to tag
483 * needed for the operator */
484 if (tag_only == false) {
485 BMVert *v;
486 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
488 }
489 }
490
491 /* Perform the number of iteration steps which the user requested. */
492 for (iter_step = 0; iter_step < iterations; iter_step++) {
493 BMVert *v, *v_next;
494 bool verts_were_marked_for_dissolve = false;
495
496 /* Tag all verts which are eligible to be dissolved on this iteration. */
497 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
499 bm_vert_dissolve_fan_or_chain_test(v, false, nullptr, nullptr))
500 {
501 BM_elem_index_set(v, VERT_INDEX_INIT); /* set_dirty! */
502 }
503 else {
504 BM_elem_index_set(v, VERT_INDEX_IGNORE); /* set_dirty! */
505 }
506 }
507
508 /* main loop, keep tagging until we can't tag any more islands */
509 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
510
511 /* Only process verts which are eligible for dissolve and which have not yet been tagged. */
513 continue;
514 }
515
516 /* Set the first #VERT_INDEX_INIT vert as the first starting vert. */
517 BM_elem_index_set(v, VERT_INDEX_IGNORE); /* set_dirty! */
518 verts_ignore[0] = v;
519 verts_ignore_num = 1;
520
521 /* Starting at v, expand outwards, tagging any currently untagged neighbors.
522 * verts will be alternately tagged for collapse or ignore.
523 * Stop when there are no neighbors left to expand to. */
524 while (true) {
525
526 bm_tag_untagged_neighbors(verts_ignore,
527 verts_ignore_num,
528 VERT_INDEX_DO_COLLAPSE, /* set_dirty! */
529 verts_collapse,
530 verts_collapse_num);
531 if (verts_collapse_num == 0) {
532 break;
533 }
534 verts_were_marked_for_dissolve = true;
535
536 bm_tag_untagged_neighbors(verts_collapse,
537 verts_collapse_num,
538 VERT_INDEX_IGNORE, /* set_dirty! */
539 verts_ignore,
540 verts_ignore_num);
541 if (verts_ignore_num == 0) {
542 break;
543 }
544 }
545 }
546
547 /* At high iteration levels, later steps can run out of verts that are eligible for dissolve.
548 * If this occurs, stop. Future iterations won't find any verts that this iteration didn't. */
549 if (!verts_were_marked_for_dissolve) {
550 break;
551 }
552
553 /* Remove all verts tagged for removal. */
554 BM_ITER_MESH_MUTABLE (v, v_next, &iter, bm, BM_VERTS_OF_MESH) {
557 }
558 }
559 }
560
561 /* Ensure the vert index values will be recomputed. */
563
564 MEM_delete(verts_collapse);
565 MEM_delete(verts_ignore);
566}
567
568void BM_mesh_decimate_unsubdivide(BMesh *bm, const int iterations)
569{
570 BM_mesh_decimate_unsubdivide_ex(bm, iterations, false);
571}
572
573} // namespace blender
Read Blender memory allocation and freeing.
#define BLI_assert_unreachable()
#define BM_elem_index_get(ele)
#define BM_elem_flag_merge_into(ele, ele_a, ele_b)
#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_MUTABLE(ele, ele_next, iter, bm, itype)
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
BMesh Iterators.
void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, int iterations, bool tag_only)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static std::optional< VertDissolveMethod > bm_vert_dissolve_fan_or_chain_test(BMVert *v, const bool check_for_duplicates, BMLoop *v_loops[VERT_DISSOLVE_MAX], int *v_loops_num_p)
unsigned int uint
Definition BKE_text.h:55
static bool bm_vert_dissolve_fan_makes_double_whole_face(BMLoop **v_loops_all, const int v_loops_all_num)
static int bm_vert_loops_from_vert_edges(const BMVert *v, BMEdge **v_edges, const int v_edges_num, BMLoop *v_loops[VERT_DISSOLVE_MAX])
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
constexpr int VERT_DISSOLVE_MAX
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void BM_mesh_decimate_unsubdivide(BMesh *bm, int iterations)
static void bm_tag_untagged_neighbors(BMVert *verts_start[], const uint verts_start_num, const int desired_tag, BMVert *r_verts_tagged[], uint &r_verts_tagged_num)
ATTR_WARN_UNUSED_RESULT const BMVert * v
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static bool bm_vert_dissolve_fan_makes_double_with_self(BMLoop **v_loops_all, const int v_loops_all_num)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
bool BM_face_split_check_double_face(BMLoop *l_a, BMLoop *l_b, const int f_len)
static bool bm_vert_dissolve_fan_or_chain(BMesh *bm, BMVert *v)
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
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.
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
bool BM_vert_dissolve(BMesh *bm, BMVert *v)
Dissolve Vert.
Definition bmesh_mods.cc:22
static bool bm_vert_dissolve_fan_makes_double_with_existing(BMLoop **v_loops_all, const int v_loops_all_num)
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.
bool BM_face_exists_multi_edge(BMEdge **earr, int len)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f