2 * ***** BEGIN GPL LICENSE BLOCK *****
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 * Contributor(s): Campbell Barton
20 * ***** END GPL LICENSE BLOCK *****
23 /** \file blender/bmesh/tools/bmesh_decimate_collapse.c
26 * BMesh decimator that uses an edge collapse method.
31 #include "MEM_guardedalloc.h"
35 #include "BLI_quadric.h"
37 #include "BLI_linklist.h"
38 #include "BLI_alloca.h"
39 #include "BLI_memarena.h"
40 #include "BLI_edgehash.h"
41 #include "BLI_polyfill2d.h"
42 #include "BLI_polyfill2d_beautify.h"
43 #include "BLI_utildefines_stack.h"
46 #include "BKE_customdata.h"
49 #include "bmesh_decimate.h" /* own include */
51 #include "../intern/bmesh_structure.h"
55 #include "BLI_kdtree.h"
58 /* defines for testing */
59 #define USE_CUSTOMDATA
60 #define USE_TRIANGULATE
61 #define USE_VERT_NORMAL_INTERP /* has the advantage that flipped faces don't mess up vertex normals */
63 /* if the cost from #BLI_quadric_evaluate is 'noise', fallback to topology */
64 #define USE_TOPOLOGY_FALLBACK
65 #ifdef USE_TOPOLOGY_FALLBACK
66 /* cost is calculated with double precision, it's ok to use a very small epsilon, see T48154. */
67 # define TOPOLOGY_FALLBACK_EPS 1e-12f
70 #define BOUNDARY_PRESERVE_WEIGHT 100.0f
71 /* Uses double precision, impacts behavior on near-flat surfaces,
72 * cane give issues with very small faces. 1e-2 is too big, see: T48154. */
73 #define OPTIMIZE_EPS 1e-8
74 #define COST_INVALID FLT_MAX
76 typedef enum CD_UseFlag {
77 CD_DO_VERT = (1 << 0),
78 CD_DO_EDGE = (1 << 1),
83 /* BMesh Helper Functions
84 * ********************** */
87 * \param vquadrics must be calloc'd
89 static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
95 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
103 BM_face_calc_center_mean(f, center);
104 copy_v3db_v3fl(plane_db, f->no);
105 plane_db[3] = -dot_v3db_v3fl(plane_db, center);
107 BLI_quadric_from_plane(&q, plane_db);
109 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
111 BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(l_iter->v)], &q);
112 } while ((l_iter = l_iter->next) != l_first);
116 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
117 if (UNLIKELY(BM_edge_is_boundary(e))) {
118 float edge_vector[3];
120 double edge_plane_db[4];
121 sub_v3_v3v3(edge_vector, e->v2->co, e->v1->co);
124 cross_v3_v3v3(edge_plane, edge_vector, f->no);
125 copy_v3db_v3fl(edge_plane_db, edge_plane);
127 if (normalize_v3_d(edge_plane_db) > (double)FLT_EPSILON) {
131 mid_v3_v3v3(center, e->v1->co, e->v2->co);
133 edge_plane_db[3] = -dot_v3db_v3fl(edge_plane_db, center);
134 BLI_quadric_from_plane(&q, edge_plane_db);
135 BLI_quadric_mul(&q, BOUNDARY_PRESERVE_WEIGHT);
137 BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v1)], &q);
138 BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v2)], &q);
145 static void bm_decim_calc_target_co_db(
146 BMEdge *e, double optimize_co[3],
147 const Quadric *vquadrics)
149 /* compute an edge contraction target for edge 'e'
150 * this is computed by summing it's vertices quadrics and
151 * optimizing the result. */
154 BLI_quadric_add_qu_ququ(
156 &vquadrics[BM_elem_index_get(e->v1)],
157 &vquadrics[BM_elem_index_get(e->v2)]);
159 if (BLI_quadric_optimize(&q, optimize_co, OPTIMIZE_EPS)) {
160 return; /* all is good */
163 optimize_co[0] = 0.5 * ((double)e->v1->co[0] + (double)e->v2->co[0]);
164 optimize_co[1] = 0.5 * ((double)e->v1->co[1] + (double)e->v2->co[1]);
165 optimize_co[2] = 0.5 * ((double)e->v1->co[2] + (double)e->v2->co[2]);
169 static void bm_decim_calc_target_co_fl(
170 BMEdge *e, float optimize_co[3],
171 const Quadric *vquadrics)
173 double optimize_co_db[3];
174 bm_decim_calc_target_co_db(e, optimize_co_db, vquadrics);
175 copy_v3fl_v3db(optimize_co, optimize_co_db);
179 static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_co[3])
185 for (i = 0; i < 2; i++) {
186 /* loop over both verts */
187 BMVert *v = *((&e->v1) + i);
189 BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
190 if (l->e != e && l->prev->e != e) {
191 const float *co_prev = l->prev->v->co;
192 const float *co_next = l->next->v->co;
193 float cross_exist[3];
194 float cross_optim[3];
197 float vec_other[3]; /* line between the two outer verts, re-use for both cross products */
198 float vec_exist[3]; /* before collapse */
199 float vec_optim[3]; /* after collapse */
201 sub_v3_v3v3(vec_other, co_prev, co_next);
202 sub_v3_v3v3(vec_exist, co_prev, v->co);
203 sub_v3_v3v3(vec_optim, co_prev, optimize_co);
205 cross_v3_v3v3(cross_exist, vec_other, vec_exist);
206 cross_v3_v3v3(cross_optim, vec_other, vec_optim);
208 /* avoid normalize */
209 if (dot_v3v3(cross_exist, cross_optim) <=
210 (len_squared_v3(cross_exist) + len_squared_v3(cross_optim)) * 0.01f)
215 normal_tri_v3(cross_exist, v->co, co_prev, co_next);
216 normal_tri_v3(cross_optim, optimize_co, co_prev, co_next);
218 /* use a small value rather then zero so we don't flip a face in multiple steps
219 * (first making it zero area, then flipping again) */
220 if (dot_v3v3(cross_exist, cross_optim) <= FLT_EPSILON) {
221 //printf("no flip\n");
233 #ifdef USE_TOPOLOGY_FALLBACK
235 * when the cost is so small that its not useful (flat surfaces),
236 * fallback to using a 'topology' cost.
238 * This avoids cases where a flat (or near flat) areas get very un-even geometry.
240 static float bm_decim_build_edge_cost_single_squared__topology(BMEdge *e)
242 return fabsf(dot_v3v3(e->v1->no, e->v2->no)) / min_ff(-len_squared_v3v3(e->v1->co, e->v2->co), -FLT_EPSILON);
244 static float bm_decim_build_edge_cost_single__topology(BMEdge *e)
246 return fabsf(dot_v3v3(e->v1->no, e->v2->no)) / min_ff(-len_v3v3(e->v1->co, e->v2->co), -FLT_EPSILON);
249 #endif /* USE_TOPOLOGY_FALLBACK */
251 static void bm_decim_build_edge_cost_single(
253 const Quadric *vquadrics,
254 const float *vweights, const float vweight_factor,
255 Heap *eheap, HeapNode **eheap_table)
259 if (UNLIKELY(vweights &&
260 ((vweights[BM_elem_index_get(e->v1)] == 0.0f) ||
261 (vweights[BM_elem_index_get(e->v2)] == 0.0f))))
266 /* check we can collapse, some edges we better not touch */
267 if (BM_edge_is_boundary(e)) {
268 if (e->l->f->len == 3) {
272 /* only collapse tri's */
276 else if (BM_edge_is_manifold(e)) {
277 if ((e->l->f->len == 3) && (e->l->radial_next->f->len == 3)) {
281 /* only collapse tri's */
288 /* end sanity check */
291 double optimize_co[3];
292 bm_decim_calc_target_co_db(e, optimize_co, vquadrics);
294 const Quadric *q1, *q2;
295 q1 = &vquadrics[BM_elem_index_get(e->v1)];
296 q2 = &vquadrics[BM_elem_index_get(e->v2)];
298 cost = (BLI_quadric_evaluate(q1, optimize_co) +
299 BLI_quadric_evaluate(q2, optimize_co));
302 /* note, 'cost' shouldn't be negative but happens sometimes with small values.
303 * this can cause faces that make up a flat surface to over-collapse, see [#37121] */
306 #ifdef USE_TOPOLOGY_FALLBACK
307 if (UNLIKELY(cost < TOPOLOGY_FALLBACK_EPS)) {
308 /* subtract existing cost to further differentiate edges from one another
310 * keep topology cost below 0.0 so their values don't interfere with quadric cost,
311 * (and they get handled first).
313 if (vweights == NULL) {
314 cost = bm_decim_build_edge_cost_single_squared__topology(e) - cost;
317 /* with weights we need to use the real length so we can scale them properly */
318 const float e_weight = (vweights[BM_elem_index_get(e->v1)] +
319 vweights[BM_elem_index_get(e->v2)]);
320 cost = bm_decim_build_edge_cost_single__topology(e) - cost;
321 /* note, this is rather arbitrary max weight is 2 here,
322 * allow for skipping edges 4x the length, based on weights */
324 cost *= 1.0f + (e_weight * vweight_factor);
327 BLI_assert(cost <= 0.0f);
333 const float e_weight = 2.0f - (vweights[BM_elem_index_get(e->v1)] +
334 vweights[BM_elem_index_get(e->v2)]);
336 cost += (BM_edge_calc_length(e) * ((e_weight * vweight_factor)));
340 BLI_heap_insert_or_update(eheap, &eheap_table[BM_elem_index_get(e)], cost, e);
344 if (eheap_table[BM_elem_index_get(e)]) {
345 BLI_heap_remove(eheap, eheap_table[BM_elem_index_get(e)]);
347 eheap_table[BM_elem_index_get(e)] = NULL;
351 /* use this for degenerate cases - add back to the heap with an invalid cost,
352 * this way it may be calculated again if surrounding geometry changes */
353 static void bm_decim_invalid_edge_cost_single(
355 Heap *eheap, HeapNode **eheap_table)
357 BLI_assert(eheap_table[BM_elem_index_get(e)] == NULL);
358 eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, COST_INVALID, e);
361 static void bm_decim_build_edge_cost(
363 const Quadric *vquadrics,
364 const float *vweights, const float vweight_factor,
365 Heap *eheap, HeapNode **eheap_table)
371 BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
372 eheap_table[i] = NULL; /* keep sanity check happy */
373 bm_decim_build_edge_cost_single(e, vquadrics, vweights, vweight_factor, eheap, eheap_table);
379 struct KD_Symmetry_Data {
380 /* pre-flipped coords */
381 float e_v1_co[3], e_v2_co[3];
382 /* Use to compare the correct endpoints incase v1/v2 are swapped */
392 static bool bm_edge_symmetry_check_cb(void *user_data, int index, const float UNUSED(co[3]), float UNUSED(dist_sq))
394 struct KD_Symmetry_Data *sym_data = user_data;
395 BMEdge *e_other = sym_data->etable[index];
396 float e_other_dir[3];
398 sub_v3_v3v3(e_other_dir, e_other->v2->co, e_other->v1->co);
400 if (dot_v3v3(e_other_dir, sym_data->e_dir) > 0.0f) {
401 if ((len_squared_v3v3(sym_data->e_v1_co, e_other->v1->co) > sym_data->limit_sq) ||
402 (len_squared_v3v3(sym_data->e_v2_co, e_other->v2->co) > sym_data->limit_sq))
408 if ((len_squared_v3v3(sym_data->e_v1_co, e_other->v2->co) > sym_data->limit_sq) ||
409 (len_squared_v3v3(sym_data->e_v2_co, e_other->v1->co) > sym_data->limit_sq))
415 /* exit on first-hit, this is OK since the search range is very small */
416 sym_data->e_found_index = index;
420 static int *bm_edge_symmetry_map(BMesh *bm, uint symmetry_axis, float limit)
422 struct KD_Symmetry_Data sym_data;
426 int *edge_symmetry_map;
427 const float limit_sq = SQUARE(limit);
430 tree = BLI_kdtree_new(bm->totedge);
432 etable = MEM_mallocN(sizeof(*etable) * bm->totedge, __func__);
433 edge_symmetry_map = MEM_mallocN(sizeof(*edge_symmetry_map) * bm->totedge, __func__);
435 BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
437 mid_v3_v3v3(co, e->v1->co, e->v2->co);
438 BLI_kdtree_insert(tree, i, co);
440 edge_symmetry_map[i] = -1;
443 BLI_kdtree_balance(tree);
445 sym_data.etable = etable;
446 sym_data.limit_sq = limit_sq;
448 BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
449 if (edge_symmetry_map[i] == -1) {
451 mid_v3_v3v3(co, e->v1->co, e->v2->co);
452 co[symmetry_axis] *= -1.0f;
454 copy_v3_v3(sym_data.e_v1_co, e->v1->co);
455 copy_v3_v3(sym_data.e_v2_co, e->v2->co);
456 sym_data.e_v1_co[symmetry_axis] *= -1.0f;
457 sym_data.e_v2_co[symmetry_axis] *= -1.0f;
458 sub_v3_v3v3(sym_data.e_dir, sym_data.e_v2_co, sym_data.e_v1_co);
459 sym_data.e_found_index = -1;
461 BLI_kdtree_range_search_cb(tree, co, limit, bm_edge_symmetry_check_cb, &sym_data);
463 if (sym_data.e_found_index != -1) {
464 const int i_other = sym_data.e_found_index;
465 edge_symmetry_map[i] = i_other;
466 edge_symmetry_map[i_other] = i;
472 BLI_kdtree_free(tree);
474 return edge_symmetry_map;
476 #endif /* USE_SYMMETRY */
478 #ifdef USE_TRIANGULATE
479 /* Temp Triangulation
480 * ****************** */
483 * To keep things simple we can only collapse edges on triangulated data
484 * (limitation with edge collapse and error calculation functions).
486 * But to avoid annoying users by only giving triangle results, we can
487 * triangulate, keeping a reference between the faces, then join after
488 * if the edges don't collapse, this will also allow more choices when
489 * collapsing edges so even has some advantage over decimating quads
492 * \return true if any faces were triangulated.
494 static bool bm_face_triangulate(
495 BMesh *bm, BMFace *f_base, LinkNode **r_faces_double, int *r_edges_tri_tot,
498 /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
499 struct Heap *pf_heap)
501 const int f_base_len = f_base->len;
502 int faces_array_tot = f_base_len - 3;
503 int edges_array_tot = f_base_len - 3;
504 BMFace **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
505 BMEdge **edges_array = BLI_array_alloca(edges_array, edges_array_tot);
506 const int quad_method = 0, ngon_method = 0; /* beauty */
508 bool has_cut = false;
510 const int f_index = BM_elem_index_get(f_base);
514 faces_array, &faces_array_tot,
515 edges_array, &edges_array_tot,
517 quad_method, ngon_method, false,
520 for (int i = 0; i < edges_array_tot; i++) {
521 BMLoop *l_iter, *l_first;
522 l_iter = l_first = edges_array[i]->l;
524 BM_elem_index_set(l_iter, f_index); /* set_dirty */
526 } while ((l_iter = l_iter->radial_next) != l_first);
529 for (int i = 0; i < faces_array_tot; i++) {
530 BM_face_normal_update(faces_array[i]);
533 *r_edges_tri_tot += edges_array_tot;
539 static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot)
543 bool has_quad = false;
544 bool has_ngon = false;
545 bool has_cut = false;
547 BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
549 /* first clear loop index values */
550 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
554 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
556 BM_elem_index_set(l_iter, -1); /* set_dirty */
557 } while ((l_iter = l_iter->next) != l_first);
559 has_quad |= (f->len > 3);
560 has_ngon |= (f->len > 4);
563 bm->elem_index_dirty |= BM_LOOP;
569 LinkNode *faces_double = NULL;
572 pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
573 pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
580 /* adding new faces as we loop over faces
581 * is normally best avoided, however in this case its not so bad because any face touched twice
582 * will already be triangulated*/
583 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
585 has_cut |= bm_face_triangulate(
586 bm, f, &faces_double,
593 while (faces_double) {
594 LinkNode *next = faces_double->next;
595 BM_face_kill(bm, faces_double->link);
596 MEM_freeN(faces_double);
601 BLI_memarena_free(pf_arena);
602 BLI_heap_free(pf_heap, NULL);
605 BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
608 /* now triangulation is done we need to correct index values */
609 BM_mesh_elem_index_ensure(bm, BM_EDGE | BM_FACE);
617 static void bm_decim_triangulate_end(BMesh *bm, const int edges_tri_tot)
619 /* decimation finished, now re-join */
623 /* we need to collect before merging for ngons since the loops indices will be lost */
624 BMEdge **edges_tri = MEM_mallocN(MIN2(edges_tri_tot, bm->totedge) * sizeof(*edges_tri), __func__);
625 STACK_DECLARE(edges_tri);
627 STACK_INIT(edges_tri, MIN2(edges_tri_tot, bm->totedge));
630 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
632 if (BM_edge_loop_pair(e, &l_a, &l_b)) {
633 const int l_a_index = BM_elem_index_get(l_a);
634 if (l_a_index != -1) {
635 const int l_b_index = BM_elem_index_get(l_b);
636 if (l_a_index == l_b_index) {
637 if (l_a->v != l_b->v) { /* if this is the case, faces have become flipped */
638 /* check we are not making a degenerate quad */
640 #define CAN_LOOP_MERGE(l) \
641 (BM_loop_is_manifold(l) && \
642 ((l)->v != (l)->radial_next->v) && \
643 (l_a_index == BM_elem_index_get(l)) && \
644 (l_a_index == BM_elem_index_get((l)->radial_next)))
646 if ((l_a->f->len == 3 && l_b->f->len == 3) &&
647 (!CAN_LOOP_MERGE(l_a->next)) &&
648 (!CAN_LOOP_MERGE(l_a->prev)) &&
649 (!CAN_LOOP_MERGE(l_b->next)) &&
650 (!CAN_LOOP_MERGE(l_b->prev)))
654 BM_vert_in_edge(e, l_a->next->v) ? l_a->prev->v : l_a->next->v,
656 BM_vert_in_edge(e, l_b->next->v) ? l_b->prev->v : l_b->next->v,
659 BLI_assert(ELEM(vquad[0], vquad[1], vquad[2], vquad[3]) == false);
660 BLI_assert(ELEM(vquad[1], vquad[0], vquad[2], vquad[3]) == false);
661 BLI_assert(ELEM(vquad[2], vquad[1], vquad[0], vquad[3]) == false);
662 BLI_assert(ELEM(vquad[3], vquad[1], vquad[2], vquad[0]) == false);
664 if (!is_quad_convex_v3(vquad[0]->co, vquad[1]->co, vquad[2]->co, vquad[3]->co)) {
668 #undef CAN_LOOP_MERGE
670 /* highly unlikely to fail, but prevents possible double-ups */
671 STACK_PUSH(edges_tri, e);
678 for (int i = 0; i < STACK_SIZE(edges_tri); i++) {
681 if (BM_edge_loop_pair(e, &l_a, &l_b)) {
682 BMFace *f_array[2] = {l_a->f, l_b->f};
683 BM_faces_join(bm, f_array, 2, false);
689 MEM_freeN(edges_tri);
692 #endif /* USE_TRIANGULATE */
694 /* Edge Collapse Functions
695 * *********************** */
697 #ifdef USE_CUSTOMDATA
700 * \param l: defines the vert to collapse into.
702 static void bm_edge_collapse_loop_customdata(
703 BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other,
704 const float customdata_fac)
706 /* disable seam check - the seam check would have to be done per layer, its not really that important */
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);
713 /* first find the loop of 'v_other' thats attached to the face of 'l' */
714 if (l->v == v_clear) {
723 BLI_assert(l_clear->v == v_clear);
724 BLI_assert(l_other->v == v_other);
725 (void)v_other; /* quiet warnings for release */
727 /* now we have both corners of the face 'l->f' */
728 for (side = 0; side < 2; side++) {
730 bool is_seam = false;
733 BMFace *f_exit = is_manifold ? l->radial_next->f : NULL;
734 BMEdge *e_prev = l->e;
740 l_iter = l_first = l_clear;
741 src[0] = l_clear->head.data;
742 src[1] = l_other->head.data;
744 w[0] = customdata_fac;
745 w[1] = 1.0f - customdata_fac;
748 l_iter = l_first = l_other;
749 src[0] = l_other->head.data;
750 src[1] = l_clear->head.data;
752 w[0] = 1.0f - customdata_fac;
753 w[1] = customdata_fac;
756 // print_v2("weights", w);
758 /* WATCH IT! - should NOT reference (_clear or _other) vars for this while loop */
760 /* walk around the fan using 'e_prev' */
761 while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first) && (l_iter != NULL)) {
763 /* quit once we hit the opposite face, if we have one */
764 if (f_exit && UNLIKELY(f_exit == l_iter->f)) {
769 /* break out unless we find a match */
773 /* ok. we have a loop. now be smart with it! */
774 for (i = 0; i < bm->ldata.totlayer; i++) {
775 if (CustomData_layer_has_math(&bm->ldata, i)) {
776 const int offset = bm->ldata.layers[i].offset;
777 const int type = bm->ldata.layers[i].type;
778 const void *cd_src[2] = {
779 POINTER_OFFSET(src[0], offset),
780 POINTER_OFFSET(src[1], offset),
782 void *cd_iter = POINTER_OFFSET(l_iter->head.data, offset);
785 if (CustomData_data_equals(type, cd_src[0], cd_iter)) {
786 CustomData_bmesh_interp_n(
787 &bm->ldata, cd_src, w, NULL, ARRAY_SIZE(cd_src),
788 POINTER_OFFSET(l_iter->head.data, offset), i);
807 #endif /* USE_CUSTOMDATA */
810 * Check if the collapse will result in a degenerate mesh,
811 * that is - duplicate edges or faces.
813 * This situation could be checked for when calculating collapse cost
814 * however its quite slow and a degenerate collapse could eventuate
815 * after the cost is calculated, so instead, check just before collapsing.
818 static void bm_edge_tag_enable(BMEdge *e)
820 BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
821 BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
823 BM_elem_flag_enable(e->l->f, BM_ELEM_TAG);
824 if (e->l != e->l->radial_next) {
825 BM_elem_flag_enable(e->l->radial_next->f, BM_ELEM_TAG);
830 static void bm_edge_tag_disable(BMEdge *e)
832 BM_elem_flag_disable(e->v1, BM_ELEM_TAG);
833 BM_elem_flag_disable(e->v2, BM_ELEM_TAG);
835 BM_elem_flag_disable(e->l->f, BM_ELEM_TAG);
836 if (e->l != e->l->radial_next) {
837 BM_elem_flag_disable(e->l->radial_next->f, BM_ELEM_TAG);
842 static bool bm_edge_tag_test(BMEdge *e)
844 /* is the edge or one of its faces tagged? */
845 return (BM_elem_flag_test(e->v1, BM_ELEM_TAG) ||
846 BM_elem_flag_test(e->v2, BM_ELEM_TAG) ||
847 (e->l && (BM_elem_flag_test(e->l->f, BM_ELEM_TAG) ||
848 (e->l != e->l->radial_next &&
849 BM_elem_flag_test(e->l->radial_next->f, BM_ELEM_TAG))))
853 /* takes the edges loop */
854 BLI_INLINE int bm_edge_is_manifold_or_boundary(BMLoop *l)
857 /* less optimized version of check below */
858 return (BM_edge_is_manifold(l->e) || BM_edge_is_boundary(l->e);
860 /* if the edge is a boundary it points to its self, else this must be a manifold */
861 return LIKELY(l) && LIKELY(l->radial_next->radial_next == l);
865 static bool bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
867 /* simply check that there is no overlap between faces and edges of each vert,
868 * (excluding the 2 faces attached to 'e' and 'e' its self) */
872 /* clear flags on both disks */
875 if (!bm_edge_is_manifold_or_boundary(e_iter->l)) {
878 bm_edge_tag_disable(e_iter);
879 } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v1)) != e_first);
883 if (!bm_edge_is_manifold_or_boundary(e_iter->l)) {
886 bm_edge_tag_disable(e_iter);
887 } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
889 /* now enable one side... */
892 bm_edge_tag_enable(e_iter);
893 } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v1)) != e_first);
895 /* ... except for the edge we will collapse, we know thats shared,
896 * disable this to avoid false positive. We could be smart and never enable these
897 * face/edge tags in the first place but easier to do this */
898 // bm_edge_tag_disable(e_first);
906 BM_ITER_ELEM (l, &liter, e_first, BM_LOOPS_OF_EDGE) {
907 BM_elem_flag_disable(l->f, BM_ELEM_TAG);
908 BM_ITER_ELEM (v, &iter, l->f, BM_VERTS_OF_FACE) {
909 BM_elem_flag_disable(v, BM_ELEM_TAG);
913 /* we know each face is a triangle, no looping/iterators needed here */
918 l_radial = e_first->l;
920 BLI_assert(l_face->f->len == 3);
921 BM_elem_flag_disable(l_face->f, BM_ELEM_TAG);
922 BM_elem_flag_disable((l_face = l_radial)->v, BM_ELEM_TAG);
923 BM_elem_flag_disable((l_face = l_face->next)->v, BM_ELEM_TAG);
924 BM_elem_flag_disable(( l_face->next)->v, BM_ELEM_TAG);
925 l_face = l_radial->radial_next;
926 if (l_radial != l_face) {
927 BLI_assert(l_face->f->len == 3);
928 BM_elem_flag_disable(l_face->f, BM_ELEM_TAG);
929 BM_elem_flag_disable((l_face = l_radial->radial_next)->v, BM_ELEM_TAG);
930 BM_elem_flag_disable((l_face = l_face->next)->v, BM_ELEM_TAG);
931 BM_elem_flag_disable(( l_face->next)->v, BM_ELEM_TAG);
936 /* and check for overlap */
939 if (bm_edge_tag_test(e_iter)) {
942 } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
948 * special, highly limited edge collapse function
949 * intended for speed over flexibility.
950 * can only collapse edges connected to (1, 2) tris.
952 * Important - dont add vert/edge/face data on collapsing!
954 * \param r_e_clear_other: Let caller know what edges we remove besides \a e_clear
955 * \param customdata_flag: Merge factor, scales from 0 - 1 ('v_clear' -> 'v_other')
957 static bool bm_edge_collapse(
958 BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2],
960 int *edge_symmetry_map,
962 #ifdef USE_CUSTOMDATA
963 const CD_UseFlag customdata_flag,
964 const float customdata_fac
966 const CD_UseFlag UNUSED(customdata_flag),
967 const float UNUSED(customdata_fac)
973 v_other = BM_edge_other_vert(e_clear, v_clear);
974 BLI_assert(v_other != NULL);
976 if (BM_edge_is_manifold(e_clear)) {
978 BMEdge *e_a_other[2], *e_b_other[2];
981 ok = BM_edge_loop_pair(e_clear, &l_a, &l_b);
983 BLI_assert(ok == true);
984 BLI_assert(l_a->f->len == 3);
985 BLI_assert(l_b->f->len == 3);
986 UNUSED_VARS_NDEBUG(ok);
988 /* keep 'v_clear' 0th */
989 if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
990 e_a_other[0] = l_a->prev->e;
991 e_a_other[1] = l_a->next->e;
994 e_a_other[1] = l_a->prev->e;
995 e_a_other[0] = l_a->next->e;
998 if (BM_vert_in_edge(l_b->prev->e, v_clear)) {
999 e_b_other[0] = l_b->prev->e;
1000 e_b_other[1] = l_b->next->e;
1003 e_b_other[1] = l_b->prev->e;
1004 e_b_other[0] = l_b->next->e;
1007 /* we could assert this case, but better just bail out */
1009 BLI_assert(e_a_other[0] != e_b_other[0]);
1010 BLI_assert(e_a_other[0] != e_b_other[1]);
1011 BLI_assert(e_b_other[0] != e_a_other[0]);
1012 BLI_assert(e_b_other[0] != e_a_other[1]);
1014 /* not totally common but we want to avoid */
1015 if (ELEM(e_a_other[0], e_b_other[0], e_b_other[1]) ||
1016 ELEM(e_a_other[1], e_b_other[0], e_b_other[1]))
1021 BLI_assert(BM_edge_share_vert(e_a_other[0], e_b_other[0]));
1022 BLI_assert(BM_edge_share_vert(e_a_other[1], e_b_other[1]));
1024 r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
1025 r_e_clear_other[1] = BM_elem_index_get(e_b_other[0]);
1027 #ifdef USE_CUSTOMDATA
1028 /* before killing, do customdata */
1029 if (customdata_flag & CD_DO_VERT) {
1030 BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
1032 if (customdata_flag & CD_DO_EDGE) {
1033 BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
1034 BM_data_interp_from_edges(bm, e_b_other[1], e_b_other[0], e_b_other[1], customdata_fac);
1036 if (customdata_flag & CD_DO_LOOP) {
1037 bm_edge_collapse_loop_customdata(bm, e_clear->l, v_clear, v_other, customdata_fac);
1038 bm_edge_collapse_loop_customdata(bm, e_clear->l->radial_next, v_clear, v_other, customdata_fac);
1042 BM_edge_kill(bm, e_clear);
1044 v_other->head.hflag |= v_clear->head.hflag;
1045 BM_vert_splice(bm, v_other, v_clear);
1047 e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag;
1048 e_b_other[1]->head.hflag |= e_b_other[0]->head.hflag;
1049 BM_edge_splice(bm, e_a_other[1], e_a_other[0]);
1050 BM_edge_splice(bm, e_b_other[1], e_b_other[0]);
1053 /* update mirror map */
1054 if (edge_symmetry_map) {
1055 if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
1056 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] = BM_elem_index_get(e_a_other[1]);
1058 if (edge_symmetry_map[r_e_clear_other[1]] != -1) {
1059 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[1]]] = BM_elem_index_get(e_b_other[1]);
1064 // BM_mesh_validate(bm);
1068 else if (BM_edge_is_boundary(e_clear)) {
1069 /* same as above but only one triangle */
1071 BMEdge *e_a_other[2];
1075 BLI_assert(l_a->f->len == 3);
1077 /* keep 'v_clear' 0th */
1078 if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
1079 e_a_other[0] = l_a->prev->e;
1080 e_a_other[1] = l_a->next->e;
1083 e_a_other[1] = l_a->prev->e;
1084 e_a_other[0] = l_a->next->e;
1087 r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
1088 r_e_clear_other[1] = -1;
1090 #ifdef USE_CUSTOMDATA
1091 /* before killing, do customdata */
1092 if (customdata_flag & CD_DO_VERT) {
1093 BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
1095 if (customdata_flag & CD_DO_EDGE) {
1096 BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
1098 if (customdata_flag & CD_DO_LOOP) {
1099 bm_edge_collapse_loop_customdata(bm, e_clear->l, v_clear, v_other, customdata_fac);
1103 BM_edge_kill(bm, e_clear);
1105 v_other->head.hflag |= v_clear->head.hflag;
1106 BM_vert_splice(bm, v_other, v_clear);
1108 e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag;
1109 BM_edge_splice(bm, e_a_other[1], e_a_other[0]);
1112 /* update mirror map */
1113 if (edge_symmetry_map) {
1114 if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
1115 edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] = BM_elem_index_get(e_a_other[1]);
1120 // BM_mesh_validate(bm);
1131 * Collapse e the edge, removing e->v2
1133 * \return true when the edge was collapsed.
1135 static bool bm_decim_edge_collapse(
1136 BMesh *bm, BMEdge *e,
1138 float *vweights, const float vweight_factor,
1139 Heap *eheap, HeapNode **eheap_table,
1141 int *edge_symmetry_map,
1143 const CD_UseFlag customdata_flag,
1144 float optimize_co[3], bool optimize_co_calc
1147 int e_clear_other[2];
1148 BMVert *v_other = e->v1;
1149 const int v_other_index = BM_elem_index_get(e->v1);
1150 const int v_clear_index = BM_elem_index_get(e->v2); /* the vert is removed so only store the index */
1151 float customdata_fac;
1153 #ifdef USE_VERT_NORMAL_INTERP
1154 float v_clear_no[3];
1155 copy_v3_v3(v_clear_no, e->v2->no);
1158 /* when false, use without degenerate checks */
1159 if (optimize_co_calc) {
1160 /* disallow collapsing which results in degenerate cases */
1161 if (UNLIKELY(bm_edge_collapse_is_degenerate_topology(e))) {
1162 bm_decim_invalid_edge_cost_single(e, eheap, eheap_table); /* add back with a high cost */
1166 bm_decim_calc_target_co_fl(e, optimize_co, vquadrics);
1168 /* check if this would result in an overlapping face */
1169 if (UNLIKELY(bm_edge_collapse_is_degenerate_flip(e, optimize_co))) {
1170 bm_decim_invalid_edge_cost_single(e, eheap, eheap_table); /* add back with a high cost */
1175 /* use for customdata merging */
1176 if (LIKELY(compare_v3v3(e->v1->co, e->v2->co, FLT_EPSILON) == false)) {
1177 customdata_fac = line_point_factor_v3(optimize_co, e->v1->co, e->v2->co);
1179 /* simple test for stupid collapse */
1180 if (customdata_fac < 0.0 - FLT_EPSILON || customdata_fac > 1.0f + FLT_EPSILON) {
1186 /* avoid divide by zero */
1187 customdata_fac = 0.5f;
1190 if (bm_edge_collapse(
1191 bm, e, e->v2, e_clear_other,
1195 customdata_flag, customdata_fac))
1197 /* update collapse info */
1201 float v_other_weight = interpf(vweights[v_other_index], vweights[v_clear_index], customdata_fac);
1202 CLAMP(v_other_weight, 0.0f, 1.0f);
1203 vweights[v_other_index] = v_other_weight;
1206 e = NULL; /* paranoid safety check */
1208 copy_v3_v3(v_other->co, optimize_co);
1211 for (i = 0; i < 2; i++) {
1212 /* highly unlikely 'eheap_table[ke_other[i]]' would be NULL, but do for sanity sake */
1213 if ((e_clear_other[i] != -1) && (eheap_table[e_clear_other[i]] != NULL)) {
1214 BLI_heap_remove(eheap, eheap_table[e_clear_other[i]]);
1215 eheap_table[e_clear_other[i]] = NULL;
1219 /* update vertex quadric, add kept vertex from killed vertex */
1220 BLI_quadric_add_qu_qu(&vquadrics[v_other_index], &vquadrics[v_clear_index]);
1222 /* update connected normals */
1224 /* in fact face normals are not used for progressive updates, no need to update them */
1225 // BM_vert_normal_update_all(v);
1226 #ifdef USE_VERT_NORMAL_INTERP
1227 interp_v3_v3v3(v_other->no, v_other->no, v_clear_no, customdata_fac);
1228 normalize_v3(v_other->no);
1230 BM_vert_normal_update(v_other);
1234 /* update error costs and the eheap */
1235 if (LIKELY(v_other->e)) {
1238 e_iter = e_first = v_other->e;
1240 BLI_assert(BM_edge_find_double(e_iter) == NULL);
1241 bm_decim_build_edge_cost_single(e_iter, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1242 } while ((e_iter = bmesh_disk_edge_next(e_iter, v_other)) != e_first);
1245 /* this block used to be disabled,
1246 * but enable now since surrounding faces may have been
1247 * set to COST_INVALID because of a face overlap that no longer occurs */
1249 /* optional, update edges around the vertex face fan */
1253 BM_ITER_ELEM (l, &liter, v_other, BM_LOOPS_OF_VERT) {
1254 if (l->f->len == 3) {
1256 if (BM_vert_in_edge(l->prev->e, l->v))
1257 e_outer = l->next->e;
1259 e_outer = l->prev->e;
1261 BLI_assert(BM_vert_in_edge(e_outer, l->v) == false);
1263 bm_decim_build_edge_cost_single(e_outer, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1267 /* end optional update */
1272 /* add back with a high cost */
1273 bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
1279 /* Main Decimate Function
1280 * ********************** */
1283 * \brief BM_mesh_decimate
1284 * \param bm The mesh
1285 * \param factor face count multiplier [0 - 1]
1286 * \param vweights Optional array of vertex aligned weights [0 - 1],
1287 * a vertex group is the usual source for this.
1288 * \param symmetry_axis: Axis of symmetry, -1 to disable mirror decimate.
1289 * \param symmetry_eps: Threshold when matching mirror verts.
1291 void BM_mesh_decimate_collapse(
1294 float *vweights, float vweight_factor,
1295 const bool do_triangulate,
1296 const int symmetry_axis, const float symmetry_eps)
1298 Heap *eheap; /* edge heap */
1299 HeapNode **eheap_table; /* edge index aligned table pointing to the eheap */
1300 Quadric *vquadrics; /* vert index aligned quadrics */
1302 int face_tot_target;
1304 CD_UseFlag customdata_flag = 0;
1307 bool use_symmetry = (symmetry_axis != -1);
1308 int *edge_symmetry_map;
1311 #ifdef USE_TRIANGULATE
1312 int edges_tri_tot = 0;
1313 /* temp convert quads to triangles */
1314 bool use_triangulate = bm_decim_triangulate_begin(bm, &edges_tri_tot);
1316 UNUSED_VARS(do_triangulate);
1321 vquadrics = MEM_callocN(sizeof(Quadric) * bm->totvert, __func__);
1322 /* since some edges may be degenerate, we might be over allocing a little here */
1323 eheap = BLI_heap_new_ex(bm->totedge);
1324 eheap_table = MEM_mallocN(sizeof(HeapNode *) * bm->totedge, __func__);
1325 tot_edge_orig = bm->totedge;
1328 /* build initial edge collapse cost data */
1329 bm_decim_build_quadrics(bm, vquadrics);
1331 bm_decim_build_edge_cost(bm, vquadrics, vweights, vweight_factor, eheap, eheap_table);
1333 face_tot_target = bm->totface * factor;
1334 bm->elem_index_dirty |= BM_ALL;
1337 edge_symmetry_map = (use_symmetry) ? bm_edge_symmetry_map(bm, symmetry_axis, symmetry_eps) : NULL;
1339 UNUSED_VARS(symmetry_axis, symmetry_eps);
1342 #ifdef USE_CUSTOMDATA
1343 /* initialize customdata flag, we only need math for loops */
1344 if (CustomData_has_interp(&bm->vdata)) customdata_flag |= CD_DO_VERT;
1345 if (CustomData_has_interp(&bm->edata)) customdata_flag |= CD_DO_EDGE;
1346 if (CustomData_has_math(&bm->ldata)) customdata_flag |= CD_DO_LOOP;
1349 /* iterative edge collapse and maintain the eheap */
1351 if (use_symmetry == false)
1354 /* simple non-mirror case */
1355 while ((bm->totface > face_tot_target) &&
1356 (BLI_heap_is_empty(eheap) == false) &&
1357 (BLI_heap_node_value(BLI_heap_top(eheap)) != COST_INVALID))
1359 // const float value = BLI_heap_node_value(BLI_heap_top(eheap));
1360 BMEdge *e = BLI_heap_pop_min(eheap);
1361 float optimize_co[3];
1362 BLI_assert(BM_elem_index_get(e) < tot_edge_orig); /* handy to detect corruptions elsewhere */
1364 /* under normal conditions wont be accessed again,
1365 * but NULL just incase so we don't use freed node */
1366 eheap_table[BM_elem_index_get(e)] = NULL;
1368 bm_decim_edge_collapse(
1369 bm, e, vquadrics, vweights, vweight_factor, eheap, eheap_table,
1380 while ((bm->totface > face_tot_target) &&
1381 (BLI_heap_is_empty(eheap) == false) &&
1382 (BLI_heap_node_value(BLI_heap_top(eheap)) != COST_INVALID))
1386 * - `eheap_table[e_index_mirr]` is only removed from the heap at the last moment
1387 * since its possible (in theory) for collapsing `e` to remove `e_mirr`.
1388 * - edges sharing a vertex are ignored, so the pivot vertex isnt moved to one side.
1391 BMEdge *e = BLI_heap_pop_min(eheap);
1392 const int e_index = BM_elem_index_get(e);
1393 const int e_index_mirr = edge_symmetry_map[e_index];
1394 BMEdge *e_mirr = NULL;
1395 float optimize_co[3];
1396 char e_invalidate = 0;
1398 BLI_assert(e_index < tot_edge_orig);
1400 eheap_table[e_index] = NULL;
1402 if (e_index_mirr != -1) {
1403 if (e_index_mirr == e_index) {
1406 else if (eheap_table[e_index_mirr]) {
1407 e_mirr = BLI_heap_node_ptr(eheap_table[e_index_mirr]);
1408 /* for now ignore edges with a shared vertex */
1409 if (BM_edge_share_vert_check(e, e_mirr)) {
1410 /* ignore permanently!
1411 * Otherwise we would keep re-evaluating and attempting to collapse. */
1412 // e_invalidate |= (1 | 2);
1417 /* mirror edge can't be operated on (happens with asymmetrical meshes) */
1423 /* when false, use without degenerate checks */
1425 /* run both before checking (since they invalidate surrounding geometry) */
1428 ok_a = !bm_edge_collapse_is_degenerate_topology(e);
1429 ok_b = e_mirr ? !bm_edge_collapse_is_degenerate_topology(e_mirr) : true;
1431 /* disallow collapsing which results in degenerate cases */
1433 if (UNLIKELY(!ok_a || !ok_b)) {
1434 e_invalidate |= (1 | (e_mirr ? 2 : 0));
1438 bm_decim_calc_target_co_fl(e, optimize_co, vquadrics);
1440 if (e_index_mirr == e_index) {
1441 optimize_co[symmetry_axis] = 0.0f;
1444 /* check if this would result in an overlapping face */
1445 if (UNLIKELY(bm_edge_collapse_is_degenerate_flip(e, optimize_co))) {
1446 e_invalidate |= (1 | (e_mirr ? 2 : 0));
1451 if (bm_decim_edge_collapse(
1452 bm, e, vquadrics, vweights, vweight_factor, eheap, eheap_table,
1455 optimize_co, false))
1457 if (e_mirr && (eheap_table[e_index_mirr])) {
1458 BLI_assert(e_index_mirr != e_index);
1459 BLI_heap_remove(eheap, eheap_table[e_index_mirr]);
1460 eheap_table[e_index_mirr] = NULL;
1461 optimize_co[symmetry_axis] *= -1.0f;
1462 bm_decim_edge_collapse(
1463 bm, e_mirr, vquadrics, vweights, vweight_factor, eheap, eheap_table,
1466 optimize_co, false);
1470 if (e_mirr && (eheap_table[e_index_mirr])) {
1476 BLI_assert(e_invalidate == 0);
1480 if (e_invalidate & 1) {
1481 bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
1484 if (e_invalidate & 2) {
1485 BLI_assert(eheap_table[e_index_mirr] != NULL);
1486 BLI_heap_remove(eheap, eheap_table[e_index_mirr]);
1487 eheap_table[e_index_mirr] = NULL;
1488 bm_decim_invalid_edge_cost_single(e_mirr, eheap, eheap_table);
1492 MEM_freeN((void *)edge_symmetry_map);
1494 #endif /* USE_SYMMETRY */
1496 #ifdef USE_TRIANGULATE
1497 if (do_triangulate == false) {
1498 /* its possible we only had triangles, skip this step in that case */
1499 if (LIKELY(use_triangulate)) {
1500 /* temp convert quads to triangles */
1501 bm_decim_triangulate_end(bm, edges_tri_tot);
1507 MEM_freeN(vquadrics);
1508 MEM_freeN(eheap_table);
1509 BLI_heap_free(eheap, NULL);
1512 // BM_mesh_validate(bm);
1514 (void)tot_edge_orig; /* quiet release build warning */