Blender V5.3
bmesh_decimate_collapse.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 <cstddef>
12
13#include "MEM_guardedalloc.h"
14
15#include "BLI_array.hh"
16#include "BLI_enum_flags.hh"
17#include "BLI_heap.hh"
18#include "BLI_linklist.hh"
19#include "BLI_math_geom_c.hh"
20#include "BLI_math_vector_c.hh"
21#include "BLI_memarena.hh"
22#include "BLI_polyfill_2d.hh"
24#include "BLI_quadric.hh"
26
27#include "BKE_customdata.hh"
28
29#include "bmesh.hh"
30#include "bmesh_decimate.hh" /* own include */
31
33
34#define USE_SYMMETRY
35#ifdef USE_SYMMETRY
36# include "BLI_kdtree.hh"
37#endif
38
39namespace blender {
40
41/* defines for testing */
42#define USE_CUSTOMDATA
43#define USE_TRIANGULATE
45#define USE_VERT_NORMAL_INTERP
46
48#define USE_TOPOLOGY_FALLBACK
49#ifdef USE_TOPOLOGY_FALLBACK
51# define TOPOLOGY_FALLBACK_EPS 1e-12f
52#endif
53
54#define BOUNDARY_PRESERVE_WEIGHT 100.0f
59#define OPTIMIZE_EPS 1e-8
60#define COST_INVALID FLT_MAX
61
63 CD_DO_VERT = (1 << 0),
64 CD_DO_EDGE = (1 << 1),
65 CD_DO_LOOP = (1 << 2),
66};
68
69/* BMesh Helper Functions
70 * ********************** */
71
72
75static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
76{
77 BMIter iter;
78 BMFace *f;
79 BMEdge *e;
80
81 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
82 BMLoop *l_first;
83 BMLoop *l_iter;
84
85 float center[3];
86 double plane_db[4];
87 Quadric q;
88
90 copy_v3db_v3fl(plane_db, f->no);
91 plane_db[3] = -dot_v3db_v3fl(plane_db, center);
92
93 BLI_quadric_from_plane(&q, plane_db);
94
95 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
96 do {
97 BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(l_iter->v)], &q);
98 } while ((l_iter = l_iter->next) != l_first);
99 }
100
101 /* boundary edges */
102 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
103 if (BM_edge_is_boundary(e)) [[unlikely]] {
104 float edge_vector[3];
105 float edge_plane[3];
106 double edge_plane_db[4];
107 sub_v3_v3v3(edge_vector, e->v2->co, e->v1->co);
108 f = e->l->f;
109
110 cross_v3_v3v3(edge_plane, edge_vector, f->no);
111 copy_v3db_v3fl(edge_plane_db, edge_plane);
112
113 if (normalize_v3_db(edge_plane_db) > double(FLT_EPSILON)) {
114 Quadric q;
115 float center[3];
116
117 mid_v3_v3v3(center, e->v1->co, e->v2->co);
118
119 edge_plane_db[3] = -dot_v3db_v3fl(edge_plane_db, center);
120 BLI_quadric_from_plane(&q, edge_plane_db);
122
123 BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v1)], &q);
124 BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v2)], &q);
125 }
126 }
127 }
128}
129
130static void bm_decim_calc_target_co_db(BMEdge *e, double optimize_co[3], const Quadric *vquadrics)
131{
132 /* compute an edge contraction target for edge 'e'
133 * this is computed by summing its vertices quadrics and
134 * optimizing the result. */
135 Quadric q;
136
138 &q, &vquadrics[BM_elem_index_get(e->v1)], &vquadrics[BM_elem_index_get(e->v2)]);
139
140 if (BLI_quadric_optimize(&q, optimize_co, OPTIMIZE_EPS)) {
141 /* all is good */
142 return;
143 }
144
145 optimize_co[0] = 0.5 * (double(e->v1->co[0]) + double(e->v2->co[0]));
146 optimize_co[1] = 0.5 * (double(e->v1->co[1]) + double(e->v2->co[1]));
147 optimize_co[2] = 0.5 * (double(e->v1->co[2]) + double(e->v2->co[2]));
148}
149
150static void bm_decim_calc_target_co_fl(BMEdge *e, float optimize_co[3], const Quadric *vquadrics)
151{
152 double optimize_co_db[3];
153 bm_decim_calc_target_co_db(e, optimize_co_db, vquadrics);
154 copy_v3fl_v3db(optimize_co, optimize_co_db);
155}
156
157static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_co[3])
158{
159 BMIter liter;
160 BMLoop *l;
161 uint i;
162
163 for (i = 0; i < 2; i++) {
164 /* loop over both verts */
165 BMVert *v = *((&e->v1) + i);
166
167 BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
168 if (l->e != e && l->prev->e != e) {
169 const float *co_prev = l->prev->v->co;
170 const float *co_next = l->next->v->co;
171 float cross_exist[3];
172 float cross_optim[3];
173
174#if 1
175 /* line between the two outer verts, re-use for both cross products */
176 float vec_other[3];
177 /* before collapse */
178 float vec_exist[3];
179 /* after collapse */
180 float vec_optim[3];
181
182 sub_v3_v3v3(vec_other, co_prev, co_next);
183 sub_v3_v3v3(vec_exist, co_prev, v->co);
184 sub_v3_v3v3(vec_optim, co_prev, optimize_co);
185
186 cross_v3_v3v3(cross_exist, vec_other, vec_exist);
187 cross_v3_v3v3(cross_optim, vec_other, vec_optim);
188
189 /* avoid normalize */
190 if (dot_v3v3(cross_exist, cross_optim) <=
191 (len_squared_v3(cross_exist) + len_squared_v3(cross_optim)) * 0.01f)
192 {
193 return true;
194 }
195#else
196 normal_tri_v3(cross_exist, v->co, co_prev, co_next);
197 normal_tri_v3(cross_optim, optimize_co, co_prev, co_next);
198
199 /* use a small value rather than zero so we don't flip a face in multiple steps
200 * (first making it zero area, then flipping again) */
201 if (dot_v3v3(cross_exist, cross_optim) <= FLT_EPSILON) {
202 // printf("no flip\n");
203 return true;
204 }
205#endif
206 }
207 }
208 }
209
210 return false;
211}
212
213#ifdef USE_TOPOLOGY_FALLBACK
221{
222 return fabsf(dot_v3v3(e->v1->no, e->v2->no)) /
223 min_ff(-len_squared_v3v3(e->v1->co, e->v2->co), -FLT_EPSILON);
224}
226{
227 return fabsf(dot_v3v3(e->v1->no, e->v2->no)) /
228 min_ff(-len_v3v3(e->v1->co, e->v2->co), -FLT_EPSILON);
229}
230
231#endif /* USE_TOPOLOGY_FALLBACK */
232
234 const Quadric *vquadrics,
235 const float *vweights,
236 const float vweight_factor,
237 Heap *eheap,
238 HeapNode **eheap_table)
239{
240 float cost;
241
242 if (vweights && ((vweights[BM_elem_index_get(e->v1)] == 0.0f) ||
243 (vweights[BM_elem_index_get(e->v2)] == 0.0f))) [[unlikely]]
244 {
245 goto clear;
246 }
247
248 /* Check we can collapse, some edges we better not touch. */
249 if (BM_edge_is_boundary(e)) {
250 if (e->l->f->len == 3) {
251 /* Pass. */
252 }
253 else {
254 /* Only collapse triangles. */
255 goto clear;
256 }
257 }
258 else if (BM_edge_is_manifold(e)) {
259 if ((e->l->f->len == 3) && (e->l->radial_next->f->len == 3)) {
260 /* Pass. */
261 }
262 else {
263 /* Only collapse triangles. */
264 goto clear;
265 }
266 }
267 else {
268 goto clear;
269 }
270 /* End sanity check. */
271
272 {
273 double optimize_co[3];
274 bm_decim_calc_target_co_db(e, optimize_co, vquadrics);
275
276 const Quadric *q1, *q2;
277 q1 = &vquadrics[BM_elem_index_get(e->v1)];
278 q2 = &vquadrics[BM_elem_index_get(e->v2)];
279
280 cost = (BLI_quadric_evaluate(q1, optimize_co) + BLI_quadric_evaluate(q2, optimize_co));
281 }
282
283 /* NOTE: 'cost' shouldn't be negative but happens sometimes with small values.
284 * this can cause faces that make up a flat surface to over-collapse, see #37121. */
285 cost = fabsf(cost);
286
287#ifdef USE_TOPOLOGY_FALLBACK
288 if (cost < TOPOLOGY_FALLBACK_EPS) [[unlikely]] {
289 /* subtract existing cost to further differentiate edges from one another
290 *
291 * keep topology cost below 0.0 so their values don't interfere with quadric cost,
292 * (and they get handled first). */
293 if (vweights == nullptr) {
295 }
296 else {
297 /* with weights we need to use the real length so we can scale them properly */
298 const float e_weight = (vweights[BM_elem_index_get(e->v1)] +
299 vweights[BM_elem_index_get(e->v2)]);
301 /* NOTE: this is rather arbitrary max weight is 2 here,
302 * allow for skipping edges 4x the length, based on weights */
303 if (e_weight) {
304 cost *= 1.0f + (e_weight * vweight_factor);
305 }
306
307 BLI_assert(cost <= 0.0f);
308 }
309 }
310 else
311#endif
312 if (vweights)
313 {
314 const float e_weight = 2.0f - (vweights[BM_elem_index_get(e->v1)] +
315 vweights[BM_elem_index_get(e->v2)]);
316 if (e_weight) {
317 cost += (BM_edge_calc_length(e) * (e_weight * vweight_factor));
318 }
319 }
320
321 BLI_heap_insert_or_update(eheap, &eheap_table[BM_elem_index_get(e)], cost, e);
322 return;
323
324clear:
325 if (eheap_table[BM_elem_index_get(e)]) {
326 BLI_heap_remove(eheap, eheap_table[BM_elem_index_get(e)]);
327 }
328 eheap_table[BM_elem_index_get(e)] = nullptr;
329}
330
331/* use this for degenerate cases - add back to the heap with an invalid cost,
332 * this way it may be calculated again if surrounding geometry changes */
333static void bm_decim_invalid_edge_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table)
334{
335 BLI_assert(eheap_table[BM_elem_index_get(e)] == nullptr);
336 eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, COST_INVALID, e);
337}
338
340 const Quadric *vquadrics,
341 const float *vweights,
342 const float vweight_factor,
343 Heap *eheap,
344 HeapNode **eheap_table)
345{
346 BMIter iter;
347 BMEdge *e;
348 uint i;
349
351 BM_elem_index_set(e, i); /* set_inline */
352 /* keep sanity check happy */
353 eheap_table[i] = nullptr;
354 bm_decim_build_edge_cost_single(e, vquadrics, vweights, vweight_factor, eheap, eheap_table);
355 }
357}
358
359#ifdef USE_SYMMETRY
360
362 /* pre-flipped coords */
363 float e_v1_co[3], e_v2_co[3];
364 /* Use to compare the correct endpoints in case v1/v2 are swapped. */
365 float e_dir[3];
366
368
369 /* same for all */
371 float limit_sq;
372};
373
374static bool bm_edge_symmetry_check_cb(void *user_data,
375 int index,
376 const float3 & /*co*/,
377 float /*dist_sq*/)
378{
379 KD_Symmetry_Data *sym_data = static_cast<KD_Symmetry_Data *>(user_data);
380 BMEdge *e_other = sym_data->etable[index];
381 float e_other_dir[3];
382
383 sub_v3_v3v3(e_other_dir, e_other->v2->co, e_other->v1->co);
384
385 if (dot_v3v3(e_other_dir, sym_data->e_dir) > 0.0f) {
386 if ((len_squared_v3v3(sym_data->e_v1_co, e_other->v1->co) > sym_data->limit_sq) ||
387 (len_squared_v3v3(sym_data->e_v2_co, e_other->v2->co) > sym_data->limit_sq))
388 {
389 return true;
390 }
391 }
392 else {
393 if ((len_squared_v3v3(sym_data->e_v1_co, e_other->v2->co) > sym_data->limit_sq) ||
394 (len_squared_v3v3(sym_data->e_v2_co, e_other->v1->co) > sym_data->limit_sq))
395 {
396 return true;
397 }
398 }
399
400 /* exit on first-hit, this is OK since the search range is very small */
401 sym_data->e_found_index = index;
402 return false;
403}
404
405static int *bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit)
406{
407 KD_Symmetry_Data sym_data;
408 BMIter iter;
409 BMEdge *e, **etable;
410 uint i;
411 int *edge_symmetry_map;
412 const float limit_sq = square_f(limit);
413 KDTree<float3> *tree;
414
416
418 edge_symmetry_map = MEM_new_array_uninitialized<int>(bm->totedge, __func__);
419
421 float co[3];
422 mid_v3_v3v3(co, e->v1->co, e->v2->co);
423 kdtree_insert<float3>(tree, i, co);
424 etable[i] = e;
425 edge_symmetry_map[i] = -1;
426 }
427
429
430 sym_data.etable = etable;
431 sym_data.limit_sq = limit_sq;
432
434 if (edge_symmetry_map[i] == -1) {
435 float co[3];
436 mid_v3_v3v3(co, e->v1->co, e->v2->co);
437 co[symmetry_axis] *= -1.0f;
438
439 copy_v3_v3(sym_data.e_v1_co, e->v1->co);
440 copy_v3_v3(sym_data.e_v2_co, e->v2->co);
441 sym_data.e_v1_co[symmetry_axis] *= -1.0f;
442 sym_data.e_v2_co[symmetry_axis] *= -1.0f;
443 sub_v3_v3v3(sym_data.e_dir, sym_data.e_v2_co, sym_data.e_v1_co);
444 sym_data.e_found_index = -1;
445
447 tree, co, limit, [&](int index, const float3 &co, float dist_sq) {
448 return bm_edge_symmetry_check_cb(&sym_data, index, co, dist_sq);
449 });
450
451 if (sym_data.e_found_index != -1) {
452 const int i_other = sym_data.e_found_index;
453 edge_symmetry_map[i] = i_other;
454 edge_symmetry_map[i_other] = i;
455 }
456 }
457 }
458
459 MEM_delete(etable);
461
462 return edge_symmetry_map;
463}
464#endif /* USE_SYMMETRY */
465
466#ifdef USE_TRIANGULATE
467/* Temp Triangulation
468 * ****************** */
469
483 BMFace *f_base,
484 LinkNode **r_faces_double,
485 int *r_edges_tri_tot,
486
487 MemArena *pf_arena,
488 /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
489 Heap *pf_heap)
490{
491 const int f_base_len = f_base->len;
492 int faces_array_tot = f_base_len - 3;
493 int edges_array_tot = f_base_len - 3;
494 Array<BMFace *, BM_DEFAULT_NGON_STACK_SIZE> faces_array(faces_array_tot);
495 Array<BMEdge *, BM_DEFAULT_NGON_STACK_SIZE> edges_array(edges_array_tot);
496 const int quad_method = 0, ngon_method = 0; /* beauty */
497
498 bool has_cut = false;
499
500 const int f_index = BM_elem_index_get(f_base);
501
503 f_base,
504 faces_array.data(),
505 &faces_array_tot,
506 edges_array.data(),
507 &edges_array_tot,
508 r_faces_double,
509 quad_method,
510 ngon_method,
511 false,
512 pf_arena,
513 pf_heap);
514
515 for (int i = 0; i < edges_array_tot; i++) {
516 BMLoop *l_iter, *l_first;
517 l_iter = l_first = edges_array[i]->l;
518 do {
519 BM_elem_index_set(l_iter, f_index); /* set_dirty */
520 has_cut = true;
521 } while ((l_iter = l_iter->radial_next) != l_first);
522 }
523
524 for (int i = 0; i < faces_array_tot; i++) {
525 BM_face_normal_update(faces_array[i]);
526 }
527
528 *r_edges_tri_tot += edges_array_tot;
529
530 return has_cut;
531}
532
533static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot)
534{
535 BMIter iter;
536 BMFace *f;
537 bool has_ngon = false;
538 bool has_cut = false;
539
541
542 /* first clear loop index values */
543 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
544 BMLoop *l_iter;
545 BMLoop *l_first;
546
547 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
548 do {
549 BM_elem_index_set(l_iter, -1); /* set_dirty */
550 } while ((l_iter = l_iter->next) != l_first);
551
552 has_ngon |= (f->len > 4);
553 }
554
556
557 {
558 MemArena *pf_arena;
559 Heap *pf_heap;
560
561 LinkNode *faces_double = nullptr;
562
563 if (has_ngon) {
564 pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
566 }
567 else {
568 pf_arena = nullptr;
569 pf_heap = nullptr;
570 }
571
572 /* Adding new faces as we loop over faces
573 * is normally best avoided, however in this case its not so bad because any face touched twice
574 * will already be triangulated. */
575 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
576 if (f->len > 3) {
577 has_cut |= bm_face_triangulate(bm,
578 f,
579 &faces_double,
580 r_edges_tri_tot,
581
582 pf_arena,
583 pf_heap);
584 }
585 }
586
587 while (faces_double) {
588 LinkNode *next = faces_double->next;
589 BM_face_kill(bm, static_cast<BMFace *>(faces_double->link));
590 MEM_delete(faces_double);
591 faces_double = next;
592 }
593
594 if (has_ngon) {
595 BLI_memarena_free(pf_arena);
596 BLI_heap_free(pf_heap, nullptr);
597 }
598
600
601 if (has_cut) {
602 /* now triangulation is done we need to correct index values */
604 }
605 }
606
607 return has_cut;
608}
609
610static void bm_decim_triangulate_end(BMesh *bm, const int edges_tri_tot)
611{
612 /* decimation finished, now re-join */
613 BMIter iter;
614 BMEdge *e;
615
616 /* we need to collect before merging for ngons since the loops indices will be lost */
617 BMEdge **edges_tri = MEM_new_array_uninitialized<BMEdge *>(std::min(edges_tri_tot, bm->totedge),
618 __func__);
619 STACK_DECLARE(edges_tri);
620
621 STACK_INIT(edges_tri, std::min(edges_tri_tot, bm->totedge));
622
623 /* boundary edges */
624 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
625 BMLoop *l_a, *l_b;
626 if (BM_edge_loop_pair(e, &l_a, &l_b)) {
627 const int l_a_index = BM_elem_index_get(l_a);
628 if (l_a_index != -1) {
629 const int l_b_index = BM_elem_index_get(l_b);
630 if (l_a_index == l_b_index) {
631 if (l_a->v != l_b->v) { /* if this is the case, faces have become flipped */
632 /* check we are not making a degenerate quad */
633
634# define CAN_LOOP_MERGE(l) \
635 (BM_loop_is_manifold(l) && ((l)->v != (l)->radial_next->v) && \
636 (l_a_index == BM_elem_index_get(l)) && (l_a_index == BM_elem_index_get((l)->radial_next)))
637
638 if ((l_a->f->len == 3 && l_b->f->len == 3) && !CAN_LOOP_MERGE(l_a->next) &&
641 {
642 BMVert *vquad[4] = {
643 e->v1,
644 BM_vert_in_edge(e, l_a->next->v) ? l_a->prev->v : l_a->next->v,
645 e->v2,
646 BM_vert_in_edge(e, l_b->next->v) ? l_b->prev->v : l_b->next->v,
647 };
648
649 BLI_assert(ELEM(vquad[0], vquad[1], vquad[2], vquad[3]) == false);
650 BLI_assert(ELEM(vquad[1], vquad[0], vquad[2], vquad[3]) == false);
651 BLI_assert(ELEM(vquad[2], vquad[1], vquad[0], vquad[3]) == false);
652 BLI_assert(ELEM(vquad[3], vquad[1], vquad[2], vquad[0]) == false);
653
654 if (!is_quad_convex_v3(vquad[0]->co, vquad[1]->co, vquad[2]->co, vquad[3]->co)) {
655 continue;
656 }
657 }
658# undef CAN_LOOP_MERGE
659
660 /* highly unlikely to fail, but prevents possible double-ups */
661 STACK_PUSH(edges_tri, e);
662 }
663 }
664 }
665 }
666 }
667
668 for (int i = 0; i < STACK_SIZE(edges_tri); i++) {
669 BMLoop *l_a, *l_b;
670 e = edges_tri[i];
671 if (BM_edge_loop_pair(e, &l_a, &l_b)) {
672 BMFace *f_double;
673
674 BMFace *f_array[2] = {l_a->f, l_b->f};
675 BMFace *f_join = BM_faces_join(bm, f_array, 2, false, &f_double);
676 /* In practice - duplicates should be quite rare - but we can't guarantee
677 * that merging faces does *not* create a duplicate.
678 * Since duplicates are not allowed in the resulting mesh (see #BM_mesh_validate),
679 * they must be removed here, see: #159549. */
680 if (f_double != nullptr) [[unlikely]] {
681 BM_face_kill(bm, f_join);
682 }
683
684 if (e->l == nullptr) {
685 BM_edge_kill(bm, e);
686 }
687 }
688 }
689 MEM_delete(edges_tri);
690}
691
692#endif /* USE_TRIANGULATE */
693
694/* Edge Collapse Functions
695 * *********************** */
696
697#ifdef USE_CUSTOMDATA
698
703 BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other, const float customdata_fac)
704{
705 /* Disable seam check - the seam check would have to be done per layer,
706 * its not really that important. */
707 // #define USE_SEAM
708 /* these don't need to be updated, since they will get removed when the edge collapses */
709 BMLoop *l_clear, *l_other;
710 const bool is_manifold = BM_edge_is_manifold(l->e);
711 int side;
712
713 /* first find the loop of 'v_other' that's attached to the face of 'l' */
714 if (l->v == v_clear) {
715 l_clear = l;
716 l_other = l->next;
717 }
718 else {
719 l_clear = l->next;
720 l_other = l;
721 }
722
723 BLI_assert(l_clear->v == v_clear);
724 BLI_assert(l_other->v == v_other);
725 /* quiet warnings for release */
726 (void)v_other;
727
728 /* now we have both corners of the face 'l->f' */
729 for (side = 0; side < 2; side++) {
730# ifdef USE_SEAM
731 bool is_seam = false;
732# endif
733 void *src[2];
734 BMFace *f_exit = is_manifold ? l->radial_next->f : nullptr;
735 BMEdge *e_prev = l->e;
736 BMLoop *l_first;
737 BMLoop *l_iter;
738 float w[2];
739
740 if (side == 0) {
741 l_iter = l_first = l_clear;
742 src[0] = l_clear->head.data;
743 src[1] = l_other->head.data;
744
745 w[0] = customdata_fac;
746 w[1] = 1.0f - customdata_fac;
747 }
748 else {
749 l_iter = l_first = l_other;
750 src[0] = l_other->head.data;
751 src[1] = l_clear->head.data;
752
753 w[0] = 1.0f - customdata_fac;
754 w[1] = customdata_fac;
755 }
756
757 // print_v2("weights", w);
758
759 /* WATCH IT! - should NOT reference (_clear or _other) vars for this while loop */
760
761 /* walk around the fan using 'e_prev' */
762 while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first) && (l_iter != nullptr)) {
763 int i;
764 /* quit once we hit the opposite face, if we have one */
765 if (f_exit && UNLIKELY(f_exit == l_iter->f)) {
766 break;
767 }
768
769# ifdef USE_SEAM
770 /* break out unless we find a match */
771 is_seam = true;
772# endif
773
774 /* ok. we have a loop. now be smart with it! */
775 for (i = 0; i < bm->ldata.totlayer; i++) {
777 const int offset = bm->ldata.layers[i].offset;
778 const int type = bm->ldata.layers[i].type;
779 const void *cd_src[2] = {
780 POINTER_OFFSET(src[0], offset),
781 POINTER_OFFSET(src[1], offset),
782 };
783 void *cd_iter = POINTER_OFFSET(l_iter->head.data, offset);
784
785 /* detect seams */
786 if (CustomData_data_equals(eCustomDataType(type), cd_src[0], cd_iter)) {
788 cd_src,
789 w,
790 ARRAY_SIZE(cd_src),
791 POINTER_OFFSET(l_iter->head.data, offset),
792 i);
793# ifdef USE_SEAM
794 is_seam = false;
795# endif
796 }
797 }
798 }
799
800# ifdef USE_SEAM
801 if (is_seam) {
802 break;
803 }
804# endif
805 }
806 }
807
808 // #undef USE_SEAM
809}
810#endif /* USE_CUSTOMDATA */
811
820
822{
825 if (e->l) {
827 if (e->l != e->l->radial_next) {
828 BM_elem_flag_enable(e->l->radial_next->f, BM_ELEM_TAG);
829 }
830 }
831}
832
834{
837 if (e->l) {
839 if (e->l != e->l->radial_next) {
840 BM_elem_flag_disable(e->l->radial_next->f, BM_ELEM_TAG);
841 }
842 }
843}
844
846{
847 /* is the edge or one of its faces tagged? */
849 (e->l &&
851 (e->l != e->l->radial_next && BM_elem_flag_test(e->l->radial_next->f, BM_ELEM_TAG)))));
852}
853
854/* takes the edges loop */
856{
857#if 0
858 /* less optimized version of check below */
860#else
861 /* if the edge is a boundary it points to itself, else this must be a manifold */
862 return LIKELY(l) && LIKELY(l->radial_next->radial_next == l);
863#endif
864}
865
867{
868 /* simply check that there is no overlap between faces and edges of each vert,
869 * (excluding the 2 faces attached to 'e' and 'e' itself) */
870
871 BMEdge *e_iter;
872
873 /* clear flags on both disks */
874 e_iter = e_first;
875 do {
876 if (!bm_edge_is_manifold_or_boundary(e_iter->l)) {
877 return true;
878 }
879 bm_edge_tag_disable(e_iter);
880 } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v1)) != e_first);
881
882 e_iter = e_first;
883 do {
884 if (!bm_edge_is_manifold_or_boundary(e_iter->l)) {
885 return true;
886 }
887 bm_edge_tag_disable(e_iter);
888 } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
889
890 /* now enable one side... */
891 e_iter = e_first;
892 do {
893 bm_edge_tag_enable(e_iter);
894 } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v1)) != e_first);
895
896 /* ... except for the edge we will collapse, we know that's shared,
897 * disable this to avoid false positive. We could be smart and never enable these
898 * face/edge tags in the first place but easier to do this */
899 // bm_edge_tag_disable(e_first);
900 /* do inline... */
901 {
902#if 0
903 BMIter iter;
904 BMIter liter;
905 BMLoop *l;
906 BMVert *v;
907 BM_ITER_ELEM (l, &liter, e_first, BM_LOOPS_OF_EDGE) {
909 BM_ITER_ELEM (v, &iter, l->f, BM_VERTS_OF_FACE) {
911 }
912 }
913#else
914 /* we know each face is a triangle, no looping/iterators needed here */
915
916 BMLoop *l_radial;
917 BMLoop *l_face;
918
919 l_radial = e_first->l;
920 l_face = l_radial;
921 BLI_assert(l_face->f->len == 3);
923 BM_elem_flag_disable((l_face = l_radial)->v, BM_ELEM_TAG);
924 BM_elem_flag_disable((l_face = l_face->next)->v, BM_ELEM_TAG);
926 l_face = l_radial->radial_next;
927 if (l_radial != l_face) {
928 BLI_assert(l_face->f->len == 3);
930 BM_elem_flag_disable((l_face = l_radial->radial_next)->v, BM_ELEM_TAG);
931 BM_elem_flag_disable((l_face = l_face->next)->v, BM_ELEM_TAG);
933 }
934#endif
935 }
936
937 /* and check for overlap */
938 e_iter = e_first;
939 do {
940 if (bm_edge_tag_test(e_iter)) {
941 return true;
942 }
943 } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
944
945 return false;
946}
947
959 BMEdge *e_clear,
960 BMVert *v_clear,
961 int r_e_clear_other[2],
962#ifdef USE_SYMMETRY
963 int *edge_symmetry_map,
964#endif
965#ifdef USE_CUSTOMDATA
966 const CD_UseFlag customdata_flag,
967 const float customdata_fac
968#else
969 const CD_UseFlag /*customdata_flag*/,
970 const float /*customdata_fac*/
971#endif
972)
973{
974 BMVert *v_other;
975
976 v_other = BM_edge_other_vert(e_clear, v_clear);
977 BLI_assert(v_other != nullptr);
978
979 if (BM_edge_is_manifold(e_clear)) {
980 BMLoop *l_a, *l_b;
981 BMEdge *e_a_other[2], *e_b_other[2];
982 bool ok;
983
984 ok = BM_edge_loop_pair(e_clear, &l_a, &l_b);
985
986 BLI_assert(ok == true);
987 BLI_assert(l_a->f->len == 3);
988 BLI_assert(l_b->f->len == 3);
990
991 /* keep 'v_clear' 0th */
992 if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
993 e_a_other[0] = l_a->prev->e;
994 e_a_other[1] = l_a->next->e;
995 }
996 else {
997 e_a_other[1] = l_a->prev->e;
998 e_a_other[0] = l_a->next->e;
999 }
1000
1001 if (BM_vert_in_edge(l_b->prev->e, v_clear)) {
1002 e_b_other[0] = l_b->prev->e;
1003 e_b_other[1] = l_b->next->e;
1004 }
1005 else {
1006 e_b_other[1] = l_b->prev->e;
1007 e_b_other[0] = l_b->next->e;
1008 }
1009
1010/* we could assert this case, but better just bail out */
1011#if 0
1012 BLI_assert(e_a_other[0] != e_b_other[0]);
1013 BLI_assert(e_a_other[0] != e_b_other[1]);
1014 BLI_assert(e_b_other[0] != e_a_other[0]);
1015 BLI_assert(e_b_other[0] != e_a_other[1]);
1016#endif
1017 /* not totally common but we want to avoid */
1018 if (ELEM(e_a_other[0], e_b_other[0], e_b_other[1]) ||
1019 ELEM(e_a_other[1], e_b_other[0], e_b_other[1]))
1020 {
1021 return false;
1022 }
1023
1024 BLI_assert(BM_edge_share_vert(e_a_other[0], e_b_other[0]));
1025 BLI_assert(BM_edge_share_vert(e_a_other[1], e_b_other[1]));
1026
1027 r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
1028 r_e_clear_other[1] = BM_elem_index_get(e_b_other[0]);
1029
1030#ifdef USE_CUSTOMDATA
1031 /* before killing, do customdata */
1032 if (customdata_flag & CD_DO_VERT) {
1033 BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
1034 }
1035 if (customdata_flag & CD_DO_EDGE) {
1036 BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
1037 BM_data_interp_from_edges(bm, e_b_other[1], e_b_other[0], e_b_other[1], customdata_fac);
1038 }
1039 if (customdata_flag & CD_DO_LOOP) {
1040 bm_edge_collapse_loop_customdata(bm, e_clear->l, v_clear, v_other, customdata_fac);
1042 bm, e_clear->l->radial_next, v_clear, v_other, customdata_fac);
1043 }
1044#endif
1045
1046 BM_edge_kill(bm, e_clear);
1047
1048 v_other->head.hflag |= v_clear->head.hflag;
1049 BM_vert_splice(bm, v_other, v_clear);
1050
1051 e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag;
1052 e_b_other[1]->head.hflag |= e_b_other[0]->head.hflag;
1053 BM_edge_splice(bm, e_a_other[1], e_a_other[0]);
1054 BM_edge_splice(bm, e_b_other[1], e_b_other[0]);
1055
1056#ifdef USE_SYMMETRY
1057 /* update mirror map */
1058 if (edge_symmetry_map) {
1059 if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
1060 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] = BM_elem_index_get(e_a_other[1]);
1061 }
1062 if (edge_symmetry_map[r_e_clear_other[1]] != -1) {
1063 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[1]]] = BM_elem_index_get(e_b_other[1]);
1064 }
1065 }
1066#endif
1067
1068 // BM_mesh_is_valid(bm);
1069
1070 return true;
1071 }
1072 if (BM_edge_is_boundary(e_clear)) {
1073 /* same as above but only one triangle */
1074 BMLoop *l_a;
1075 BMEdge *e_a_other[2];
1076
1077 l_a = e_clear->l;
1078
1079 BLI_assert(l_a->f->len == 3);
1080
1081 /* keep 'v_clear' 0th */
1082 if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
1083 e_a_other[0] = l_a->prev->e;
1084 e_a_other[1] = l_a->next->e;
1085 }
1086 else {
1087 e_a_other[1] = l_a->prev->e;
1088 e_a_other[0] = l_a->next->e;
1089 }
1090
1091 r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
1092 r_e_clear_other[1] = -1;
1093
1094#ifdef USE_CUSTOMDATA
1095 /* before killing, do customdata */
1096 if (customdata_flag & CD_DO_VERT) {
1097 BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
1098 }
1099 if (customdata_flag & CD_DO_EDGE) {
1100 BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
1101 }
1102 if (customdata_flag & CD_DO_LOOP) {
1103 bm_edge_collapse_loop_customdata(bm, e_clear->l, v_clear, v_other, customdata_fac);
1104 }
1105#endif
1106
1107 BM_edge_kill(bm, e_clear);
1108
1109 v_other->head.hflag |= v_clear->head.hflag;
1110 BM_vert_splice(bm, v_other, v_clear);
1111
1112 e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag;
1113 BM_edge_splice(bm, e_a_other[1], e_a_other[0]);
1114
1115#ifdef USE_SYMMETRY
1116 /* update mirror map */
1117 if (edge_symmetry_map) {
1118 if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
1119 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] = BM_elem_index_get(e_a_other[1]);
1120 }
1121 }
1122#endif
1123
1124 // BM_mesh_is_valid(bm);
1125
1126 return true;
1127 }
1128 return false;
1129}
1130
1137 BMEdge *e,
1138 Quadric *vquadrics,
1139 float *vweights,
1140 const float vweight_factor,
1141 Heap *eheap,
1142 HeapNode **eheap_table,
1143#ifdef USE_SYMMETRY
1144 int *edge_symmetry_map,
1145#endif
1146 const CD_UseFlag customdata_flag,
1147 float optimize_co[3],
1148 bool optimize_co_calc)
1149{
1150 int e_clear_other[2];
1151 BMVert *v_other = e->v1;
1152 const int v_other_index = BM_elem_index_get(e->v1);
1153 /* the vert is removed so only store the index */
1154 const int v_clear_index = BM_elem_index_get(e->v2);
1155 float customdata_fac;
1156
1157#ifdef USE_VERT_NORMAL_INTERP
1158 float v_clear_no[3];
1159 copy_v3_v3(v_clear_no, e->v2->no);
1160#endif
1161
1162 /* when false, use without degenerate checks */
1163 if (optimize_co_calc) {
1164 /* disallow collapsing which results in degenerate cases */
1165 if (bm_edge_collapse_is_degenerate_topology(e)) [[unlikely]] {
1166 /* add back with a high cost */
1167 bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
1168 return false;
1169 }
1170
1171 bm_decim_calc_target_co_fl(e, optimize_co, vquadrics);
1172
1173 /* check if this would result in an overlapping face */
1174 if (bm_edge_collapse_is_degenerate_flip(e, optimize_co)) [[unlikely]] {
1175 /* add back with a high cost */
1176 bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
1177 return false;
1178 }
1179 }
1180
1181 /* use for customdata merging */
1182 if (compare_v3v3(e->v1->co, e->v2->co, FLT_EPSILON) == false) [[likely]] {
1183 customdata_fac = line_point_factor_v3(optimize_co, e->v1->co, e->v2->co);
1184#if 0
1185 /* simple test for stupid collapse */
1186 if (customdata_fac < 0.0 - FLT_EPSILON || customdata_fac > 1.0f + FLT_EPSILON) {
1187 return false;
1188 }
1189#endif
1190 }
1191 else {
1192 /* avoid divide by zero */
1193 customdata_fac = 0.5f;
1194 }
1195
1196 if (bm_edge_collapse(bm,
1197 e,
1198 e->v2,
1199 e_clear_other,
1200#ifdef USE_SYMMETRY
1201 edge_symmetry_map,
1202#endif
1203 customdata_flag,
1204 customdata_fac))
1205 {
1206 /* update collapse info */
1207 int i;
1208
1209 if (vweights) {
1210 float v_other_weight = interpf(
1211 vweights[v_other_index], vweights[v_clear_index], customdata_fac);
1212 CLAMP(v_other_weight, 0.0f, 1.0f);
1213 vweights[v_other_index] = v_other_weight;
1214 }
1215
1216 /* paranoid safety check */
1217 e = nullptr;
1218
1219 copy_v3_v3(v_other->co, optimize_co);
1220
1221 /* remove eheap */
1222 for (i = 0; i < 2; i++) {
1223 /* highly unlikely 'eheap_table[ke_other[i]]' would be nullptr, but do for sanity sake */
1224 if ((e_clear_other[i] != -1) && (eheap_table[e_clear_other[i]] != nullptr)) {
1225 BLI_heap_remove(eheap, eheap_table[e_clear_other[i]]);
1226 eheap_table[e_clear_other[i]] = nullptr;
1227 }
1228 }
1229
1230 /* update vertex quadric, add kept vertex from killed vertex */
1231 BLI_quadric_add_qu_qu(&vquadrics[v_other_index], &vquadrics[v_clear_index]);
1232
1233/* update connected normals */
1234
1235/* in fact face normals are not used for progressive updates, no need to update them */
1236// BM_vert_normal_update_all(v);
1237#ifdef USE_VERT_NORMAL_INTERP
1238 interp_v3_v3v3(v_other->no, v_other->no, v_clear_no, customdata_fac);
1239 normalize_v3(v_other->no);
1240#else
1241 BM_vert_normal_update(v_other);
1242#endif
1243
1244 /* update error costs and the eheap */
1245 if (v_other->e) [[likely]] {
1246 BMEdge *e_iter;
1247 BMEdge *e_first;
1248 e_iter = e_first = v_other->e;
1249 do {
1250 BLI_assert(BM_edge_find_double(e_iter) == nullptr);
1252 e_iter, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1253 } while ((e_iter = bmesh_disk_edge_next(e_iter, v_other)) != e_first);
1254 }
1255
1256/* this block used to be disabled,
1257 * but enable now since surrounding faces may have been
1258 * set to COST_INVALID because of a face overlap that no longer occurs */
1259#if 1
1260 /* optional, update edges around the vertex face fan */
1261 {
1262 BMIter liter;
1263 BMLoop *l;
1264 BM_ITER_ELEM (l, &liter, v_other, BM_LOOPS_OF_VERT) {
1265 if (l->f->len == 3) {
1266 BMEdge *e_outer;
1267 if (BM_vert_in_edge(l->prev->e, l->v)) {
1268 e_outer = l->next->e;
1269 }
1270 else {
1271 e_outer = l->prev->e;
1272 }
1273
1274 BLI_assert(BM_vert_in_edge(e_outer, l->v) == false);
1275
1277 e_outer, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1278 }
1279 }
1280 }
1281 /* end optional update */
1282 return true;
1283#endif
1284 }
1285 /* add back with a high cost */
1286 bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
1287 return false;
1288}
1289
1290/* Main Decimate Function
1291 * ********************** */
1292
1294 const float factor,
1295 float *vweights,
1296 float vweight_factor,
1297 const bool do_triangulate,
1298 const int symmetry_axis,
1299 const float symmetry_eps)
1300{
1301 /* edge heap */
1302 Heap *eheap;
1303 /* edge index aligned table pointing to the eheap */
1304 HeapNode **eheap_table;
1305 /* vert index aligned quadrics */
1306 Quadric *vquadrics;
1307 int tot_edge_orig;
1308 int face_tot_target;
1309
1310 CD_UseFlag customdata_flag = CD_UseFlag(0);
1311
1312#ifdef USE_SYMMETRY
1313 bool use_symmetry = (symmetry_axis != -1);
1314 int *edge_symmetry_map;
1315#endif
1316
1317#ifdef USE_TRIANGULATE
1318 int edges_tri_tot = 0;
1319 /* temp convert quads to triangles */
1320 bool use_triangulate = bm_decim_triangulate_begin(bm, &edges_tri_tot);
1321#else
1322 UNUSED_VARS(do_triangulate);
1323#endif
1324
1325 /* Edge indices are used to index into `eheap_table`, ensure they're valid.
1326 * Needed since callers may pass a mesh with dirty edge indices,
1327 * for example running the decimate operator twice in edit-mode. */
1329
1330 /* Allocate variables. */
1331 vquadrics = MEM_new_array_zeroed<Quadric>(bm->totvert, __func__);
1332 /* Since some edges may be degenerate, we might be over allocating a little here. */
1333 eheap = BLI_heap_new_ex(bm->totedge);
1334 eheap_table = MEM_new_array_uninitialized<HeapNode *>(bm->totedge, __func__);
1335 tot_edge_orig = bm->totedge;
1336
1337 /* build initial edge collapse cost data */
1338 bm_decim_build_quadrics(bm, vquadrics);
1339
1340 bm_decim_build_edge_cost(bm, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1341
1342 face_tot_target = bm->totface * factor;
1344
1345#ifdef USE_SYMMETRY
1346 edge_symmetry_map = (use_symmetry) ? bm_edge_symmetry_map(bm, symmetry_axis, symmetry_eps) :
1347 nullptr;
1348#else
1349 UNUSED_VARS(symmetry_axis, symmetry_eps);
1350#endif
1351
1352#ifdef USE_CUSTOMDATA
1353 /* initialize customdata flag, we only need math for loops */
1355 customdata_flag |= CD_DO_VERT;
1356 }
1358 customdata_flag |= CD_DO_EDGE;
1359 }
1360 if (CustomData_has_math(&bm->ldata)) {
1361 customdata_flag |= CD_DO_LOOP;
1362 }
1363#endif
1364
1365/* iterative edge collapse and maintain the eheap */
1366#ifdef USE_SYMMETRY
1367 if (use_symmetry == false)
1368#endif
1369 {
1370 /* simple non-mirror case */
1371 while ((bm->totface > face_tot_target) && (BLI_heap_is_empty(eheap) == false) &&
1372 (BLI_heap_top_value(eheap) != COST_INVALID))
1373 {
1374 // const float value = BLI_heap_node_value(BLI_heap_top(eheap));
1375 BMEdge *e = static_cast<BMEdge *>(BLI_heap_pop_min(eheap));
1376 float optimize_co[3];
1377 /* handy to detect corruptions elsewhere */
1378 BLI_assert(BM_elem_index_get(e) < tot_edge_orig);
1379
1380 /* Under normal conditions won't be accessed again,
1381 * but nullptr just in case so we don't use freed node. */
1382 eheap_table[BM_elem_index_get(e)] = nullptr;
1383
1385 e,
1386 vquadrics,
1387 vweights,
1388 vweight_factor,
1389 eheap,
1390 eheap_table,
1391#ifdef USE_SYMMETRY
1392 edge_symmetry_map,
1393#endif
1394 customdata_flag,
1395 optimize_co,
1396 true);
1397 }
1398 }
1399#ifdef USE_SYMMETRY
1400 else {
1401 while ((bm->totface > face_tot_target) && (BLI_heap_is_empty(eheap) == false) &&
1402 (BLI_heap_top_value(eheap) != COST_INVALID))
1403 {
1404 /* NOTE:
1405 * - `eheap_table[e_index_mirr]` is only removed from the heap at the last moment
1406 * since its possible (in theory) for collapsing `e` to remove `e_mirr`.
1407 * - edges sharing a vertex are ignored, so the pivot vertex isn't moved to one side.
1408 */
1409
1410 BMEdge *e = static_cast<BMEdge *>(BLI_heap_pop_min(eheap));
1411 const int e_index = BM_elem_index_get(e);
1412 const int e_index_mirr = edge_symmetry_map[e_index];
1413 BMEdge *e_mirr = nullptr;
1414 float optimize_co[3];
1415 char e_invalidate = 0;
1416
1417 BLI_assert(e_index < tot_edge_orig);
1418
1419 eheap_table[e_index] = nullptr;
1420
1421 if (e_index_mirr != -1) {
1422 if (e_index_mirr == e_index) {
1423 /* pass */
1424 }
1425 else if (eheap_table[e_index_mirr]) {
1426 e_mirr = static_cast<BMEdge *>(BLI_heap_node_ptr(eheap_table[e_index_mirr]));
1427 /* for now ignore edges with a shared vertex */
1428 if (BM_edge_share_vert_check(e, e_mirr)) {
1429 /* ignore permanently!
1430 * Otherwise we would keep re-evaluating and attempting to collapse. */
1431 // e_invalidate |= (1 | 2);
1432 goto invalidate;
1433 }
1434 }
1435 else {
1436 /* mirror edge can't be operated on (happens with asymmetrical meshes) */
1437 e_invalidate |= 1;
1438 goto invalidate;
1439 }
1440 }
1441
1442 /* when false, use without degenerate checks */
1443 {
1444 /* run both before checking (since they invalidate surrounding geometry) */
1445 bool ok_a, ok_b;
1446
1448 ok_b = e_mirr ? !bm_edge_collapse_is_degenerate_topology(e_mirr) : true;
1449
1450 /* disallow collapsing which results in degenerate cases */
1451
1452 if (!ok_a || !ok_b) [[unlikely]] {
1453 e_invalidate |= (1 | (e_mirr ? 2 : 0));
1454 goto invalidate;
1455 }
1456
1457 bm_decim_calc_target_co_fl(e, optimize_co, vquadrics);
1458
1459 if (e_index_mirr == e_index) {
1460 optimize_co[symmetry_axis] = 0.0f;
1461 }
1462
1463 /* check if this would result in an overlapping face */
1464 if (bm_edge_collapse_is_degenerate_flip(e, optimize_co)) [[unlikely]] {
1465 e_invalidate |= (1 | (e_mirr ? 2 : 0));
1466 goto invalidate;
1467 }
1468 }
1469
1471 e,
1472 vquadrics,
1473 vweights,
1474 vweight_factor,
1475 eheap,
1476 eheap_table,
1477 edge_symmetry_map,
1478 customdata_flag,
1479 optimize_co,
1480 false))
1481 {
1482 if (e_mirr && (eheap_table[e_index_mirr])) {
1483 BLI_assert(e_index_mirr != e_index);
1484 BLI_heap_remove(eheap, eheap_table[e_index_mirr]);
1485 eheap_table[e_index_mirr] = nullptr;
1486 optimize_co[symmetry_axis] *= -1.0f;
1488 e_mirr,
1489 vquadrics,
1490 vweights,
1491 vweight_factor,
1492 eheap,
1493 eheap_table,
1494 edge_symmetry_map,
1495 customdata_flag,
1496 optimize_co,
1497 false);
1498 }
1499 }
1500 else {
1501 if (e_mirr && (eheap_table[e_index_mirr])) {
1502 e_invalidate |= 2;
1503 goto invalidate;
1504 }
1505 }
1506
1507 BLI_assert(e_invalidate == 0);
1508 continue;
1509
1510 invalidate:
1511 if (e_invalidate & 1) {
1512 bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
1513 }
1514
1515 if (e_invalidate & 2) {
1516 BLI_assert(eheap_table[e_index_mirr] != nullptr);
1517 BLI_heap_remove(eheap, eheap_table[e_index_mirr]);
1518 eheap_table[e_index_mirr] = nullptr;
1519 bm_decim_invalid_edge_cost_single(e_mirr, eheap, eheap_table);
1520 }
1521 }
1522
1523 MEM_delete(edge_symmetry_map);
1524 }
1525#endif /* USE_SYMMETRY */
1526
1527#ifdef USE_TRIANGULATE
1528 if (do_triangulate == false) {
1529 /* its possible we only had triangles, skip this step in that case */
1530 if (use_triangulate) [[likely]] {
1531 /* temp convert quads to triangles */
1532 bm_decim_triangulate_end(bm, edges_tri_tot);
1533 }
1534 }
1535#endif
1536
1537 /* free vars */
1538 MEM_delete(vquadrics);
1539 MEM_delete(eheap_table);
1540 BLI_heap_free(eheap, nullptr);
1541
1542 /* testing only */
1543 // BM_mesh_is_valid(bm);
1544
1545 /* quiet release build warning */
1546 (void)tot_edge_orig;
1547}
1548
1549} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
#define ENUM_OPERATORS(_enum_type)
A min-heap / priority queue ADT.
A KD-tree for nearest neighbor search.
#define BLI_POLYFILL_ARENA_SIZE
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
Read Blender memory allocation and freeing.
#define CLAMP(a, b, c)
#define UNUSED_VARS(...)
#define UNUSED_VARS_NDEBUG(...)
#define BLI_INLINE
#define UNLIKELY(x)
#define ELEM(...)
#define POINTER_OFFSET(v, ofs)
#define LIKELY(x)
#define BM_ALL
#define BM_FACE_FIRST_LOOP(p)
#define TOPOLOGY_FALLBACK_EPS
#define USE_CUSTOMDATA
#define BOUNDARY_PRESERVE_WEIGHT
#define COST_INVALID
#define CAN_LOOP_MERGE(l)
#define USE_SYMMETRY
#define OPTIMIZE_EPS
#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)
SIMD_FORCE_INLINE void invalidate()
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
const T * data() const
Definition BLI_array.hh:323
#define FLT_EPSILON
BMesh Iterators.
MINLINE float min_ff(float a, float b)
static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot)
void BM_face_calc_center_median(const BMFace *f, float r_cent[3])
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
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:271
void kdtree_balance(KDTree< CoordT > *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])
static bool bm_face_triangulate(BMesh *bm, BMFace *f_base, LinkNode **r_faces_double, int *r_edges_tri_tot, MemArena *pf_arena, Heap *pf_heap)
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:173
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
ATTR_WARN_UNUSED_RESULT const BMLoop * l
static void bm_decim_build_edge_cost_single(BMEdge *e, const Quadric *vquadrics, const float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table)
MINLINE void copy_v3db_v3fl(double r[3], const float a[3])
static void bm_decim_build_edge_cost(BMesh *bm, const Quadric *vquadrics, const float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table)
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
Definition BLI_heap.cc:309
static void bm_decim_calc_target_co_fl(BMEdge *e, float optimize_co[3], const Quadric *vquadrics)
static bool bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2], int *edge_symmetry_map, const CD_UseFlag customdata_flag, const float customdata_fac)
bool CustomData_has_interp(const CustomData *data)
BMVert * BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_co[3])
void BLI_quadric_from_plane(Quadric *q, const double v[4])
Definition quadric.cc:33
void kdtree_range_search_cb(const KDTree< CoordT > *tree, const CoordT &co, typename KDTree< CoordT >::ValueType range, Fn &&search_cb)
static bool bm_decim_edge_collapse(BMesh *bm, BMEdge *e, Quadric *vquadrics, float *vweights, const float vweight_factor, Heap *eheap, HeapNode **eheap_table, int *edge_symmetry_map, const CD_UseFlag customdata_flag, float optimize_co[3], bool optimize_co_calc)
void BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **r_faces_new, int *r_faces_new_tot, BMEdge **r_edges_new, int *r_edges_new_tot, LinkNode **r_faces_double, const int quad_method, const int ngon_method, const bool use_tag, MemArena *pf_arena, Heap *pf_heap)
BMESH TRIANGULATE FACE.
BMLoop * BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
bool CustomData_data_equals(eCustomDataType type, const void *data1, const void *data2)
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
static bool bm_edge_tag_test(BMEdge *e)
ATTR_WARN_UNUSED_RESULT const BMVert * v
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
void BM_data_interp_from_edges(BMesh *bm, const BMEdge *e_src_1, const BMEdge *e_src_2, BMEdge *e_dst, const float fac)
Data, Interpolate From Edges.
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BLI_quadric_add_qu_ququ(Quadric *r, const Quadric *a, const Quadric *b)
Definition quadric.cc:124
static bool bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
float BM_edge_calc_length(const BMEdge *e)
bool BLI_quadric_optimize(const Quadric *q, double v[3], double epsilon)
Definition quadric.cc:149
BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:293
static void bm_edge_tag_disable(BMEdge *e)
static float bm_decim_build_edge_cost_single_squared__topology(BMEdge *e)
void BM_vert_normal_update(BMVert *v)
BMFace * BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del, BMFace **r_double)
Join Connected Faces.
KDTree< CoordT > * kdtree_new(uint nodes_len_capacity)
Definition BLI_kdtree.hh:65
static int * bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit)
bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src)
Splice Edge.
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void BM_face_normal_update(BMFace *f)
void CustomData_bmesh_interp_n(CustomData *data, const void **src_blocks, const float *weights, int count, void *dst_block_ofs, int n)
void BM_edge_kill(BMesh *bm, BMEdge *e)
float BLI_heap_top_value(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:286
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition BLI_heap.cc:236
void kdtree_insert(KDTree< CoordT > *tree, int index, const CoordT &co)
Definition BLI_kdtree.hh:96
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
Splice Vert.
void BLI_quadric_add_qu_qu(Quadric *a, const Quadric *b)
Definition quadric.cc:117
BLI_INLINE bool BM_edge_is_boundary(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
static void bm_decim_calc_target_co_db(BMEdge *e, double optimize_co[3], const Quadric *vquadrics)
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
Definition BLI_heap.cc:261
static bool bm_edge_symmetry_check_cb(void *user_data, int index, const float3 &, float)
MINLINE void copy_v3fl_v3db(float r[3], const double a[3])
MINLINE float normalize_v3(float n[3])
void kdtree_free(KDTree< CoordT > *tree)
Definition BLI_kdtree.hh:84
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])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE bool compare_v3v3(const float v1[3], const float v2[3], float limit) ATTR_WARN_UNUSED_RESULT
void BM_mesh_decimate_collapse(BMesh *bm, float factor, float *vweights, float vweight_factor, bool do_triangulate, int symmetry_axis, float symmetry_eps)
BM_mesh_decimate.
void BM_face_kill(BMesh *bm, BMFace *f)
bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
double BLI_quadric_evaluate(const Quadric *q, const double v[3])
Definition quadric.cc:137
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float square_f(float a)
MINLINE float interpf(float target, float origin, float t)
BMEdge * BM_edge_find_double(BMEdge *e)
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE int bm_edge_is_manifold_or_boundary(BMLoop *l)
static void bm_decim_triangulate_end(BMesh *bm, const int edges_tri_tot)
void BM_data_interp_from_verts(BMesh *bm, const BMVert *v_src_1, const BMVert *v_src_2, BMVert *v_dst, const float fac)
Data, Interpolate From Verts.
bool CustomData_has_math(const CustomData *data)
VecBase< float, 3 > float3
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
static void bm_decim_invalid_edge_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table)
MINLINE double normalize_v3_db(double n[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE double dot_v3db_v3fl(const double a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
static float bm_decim_build_edge_cost_single__topology(BMEdge *e)
static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
bool CustomData_layer_has_math(const CustomData *data, int layer_n)
static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other, const float customdata_fac)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void BLI_quadric_mul(Quadric *a, double scalar)
Definition quadric.cc:132
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void * BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:354
static void bm_edge_tag_enable(BMEdge *e)
#define fabsf
struct BMLoop * l
struct BMLoop * next
struct BMLoop * prev
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct BMEdge * e
struct LinkNode * next
struct BMLoop * radial_next