Fix error in recent vert/edge-slide commits
[blender.git] / source / blender / bmesh / tools / bmesh_decimate_collapse.c
index c38b9f54a335c793c6d25cf6367b7eaa5861b096..230cb302d283aef5499d2e32ce27c23b70316693 100644 (file)
@@ -20,7 +20,7 @@
  * ***** END GPL LICENSE BLOCK *****
  */
 
-/** \file blender/bmesh/intern/bmesh_decimate_collapse.c
+/** \file blender/bmesh/tools/bmesh_decimate_collapse.c
  *  \ingroup bmesh
  *
  * BMesh decimator that uses an edge collapse method.
@@ -30,7 +30,6 @@
 
 #include "MEM_guardedalloc.h"
 
-#include "DNA_scene_types.h"
 
 #include "BLI_math.h"
 #include "BLI_quadric.h"
@@ -116,7 +115,7 @@ static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
 static void bm_decim_calc_target_co(BMEdge *e, float optimize_co[3],
                                     const Quadric *vquadrics)
 {
-       /* compute an edge contration target for edge 'e'
+       /* compute an edge contraction target for edge 'e'
         * this is computed by summing it's vertices quadrics and
         * optimizing the result. */
        Quadric q;
@@ -134,7 +133,7 @@ static void bm_decim_calc_target_co(BMEdge *e, float optimize_co[3],
        }
 }
 
-static int bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_co[3])
+static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_co[3])
 {
        BMIter liter;
        BMLoop *l;
@@ -146,8 +145,8 @@ static int bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_c
 
                BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
                        if (l->e != e && l->prev->e != e) {
-                               float *co_prev = l->prev->v->co;
-                               float *co_next = l->next->v->co;
+                               const float *co_prev = l->prev->v->co;
+                               const float *co_next = l->next->v->co;
                                float cross_exist[3];
                                float cross_optim[3];
 
@@ -172,16 +171,16 @@ static int bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_c
 #endif
 
                                /* use a small value rather then zero so we don't flip a face in multiple steps
-                                * (first making it zero area, then flipping again)*/
+                                * (first making it zero area, then flipping again) */
                                if (dot_v3v3(cross_exist, cross_optim) <= FLT_EPSILON) {
                                        //printf("no flip\n");
-                                       return TRUE;
+                                       return true;
                                }
                        }
                }
        }
 
-       return FALSE;
+       return false;
 }
 
 static void bm_decim_build_edge_cost_single(BMEdge *e,
@@ -223,8 +222,8 @@ static void bm_decim_build_edge_cost_single(BMEdge *e,
        }
 
        if (vweights) {
-               if ((vweights[BM_elem_index_get(e->v1)] < FLT_EPSILON) &&
-                   (vweights[BM_elem_index_get(e->v2)] < FLT_EPSILON))
+               if ((vweights[BM_elem_index_get(e->v1)] >= BM_MESH_DECIM_WEIGHT_MAX) &&
+                   (vweights[BM_elem_index_get(e->v2)] >= BM_MESH_DECIM_WEIGHT_MAX))
                {
                        /* skip collapsing this edge */
                        eheap_table[BM_elem_index_get(e)] = NULL;
@@ -244,11 +243,15 @@ static void bm_decim_build_edge_cost_single(BMEdge *e,
                        BLI_quadric_evaluate(q2, optimize_co));
        }
        else {
-               cost = ((BLI_quadric_evaluate(q1, optimize_co) * vweights[BM_elem_index_get(e->v1)]) +
-                       (BLI_quadric_evaluate(q2, optimize_co) * vweights[BM_elem_index_get(e->v2)]));
+               /* add 1.0 so planar edges are still weighted against */
+               cost = (((BLI_quadric_evaluate(q1, optimize_co) + 1.0f) * vweights[BM_elem_index_get(e->v1)]) +
+                       ((BLI_quadric_evaluate(q2, optimize_co) + 1.0f) * vweights[BM_elem_index_get(e->v2)]));
        }
        // print("COST %.12f\n");
 
+       /* note, 'cost' shouldn't be negative but happens sometimes with small values.
+        * this can cause faces that make up a flat surface to over-collapse, see [#37121] */
+       cost = fabsf(cost);
        eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, cost, e);
 }
 
@@ -290,15 +293,15 @@ static void bm_decim_build_edge_cost(BMesh *bm,
  * collapsing edges so even has some advantage over decimating quads
  * directly.
  *
- * \return TRUE if any faces were triangulated.
+ * \return true if any faces were triangulated.
  */
 
-static int bm_decim_triangulate_begin(BMesh *bm)
+static bool bm_decim_triangulate_begin(BMesh *bm)
 {
        BMIter iter;
        BMFace *f;
-       // int has_quad;  // could optimize this a little
-       int has_cut = FALSE;
+       // bool has_quad;  // could optimize this a little
+       bool has_cut = false;
 
        BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
 
@@ -309,12 +312,14 @@ static int bm_decim_triangulate_begin(BMesh *bm)
 
                l_iter = l_first = BM_FACE_FIRST_LOOP(f);
                do {
-                       BM_elem_index_set(l_iter, -1);
+                       BM_elem_index_set(l_iter, -1);  /* set_dirty */
                } while ((l_iter = l_iter->next) != l_first);
 
                // has_quad |= (f->len == 4)
        }
 
+       bm->elem_index_dirty |= BM_LOOP;
+
        /* adding new faces as we loop over faces
         * is normally best avoided, however in this case its not so bad because any face touched twice
         * will already be triangulated*/
@@ -344,7 +349,7 @@ static int bm_decim_triangulate_begin(BMesh *bm)
                        }
 
 #ifdef USE_SAFETY_CHECKS
-                       if (BM_edge_exists(l_a->v, l_b->v) == FALSE)
+                       if (BM_edge_exists(l_a->v, l_b->v) == NULL)
 #endif
                        {
                                BMFace *f_new;
@@ -354,7 +359,7 @@ static int bm_decim_triangulate_begin(BMesh *bm)
                                 * - if there is a quad that has a free standing edge joining it along
                                 * where we want to split the face, there isnt a good way we can handle this.
                                 * currently that edge will get removed when joining the tris back into a quad. */
-                               f_new = BM_face_split(bm, f, l_a->v, l_b->v, &l_new, NULL, FALSE);
+                               f_new = BM_face_split(bm, f, l_a, l_b, &l_new, NULL, false);
 
                                if (f_new) {
                                        /* the value of this doesn't matter, only that the 2 loops match and have unique values */
@@ -363,13 +368,13 @@ static int bm_decim_triangulate_begin(BMesh *bm)
                                        /* since we just split theres only ever 2 loops */
                                        BLI_assert(BM_edge_is_manifold(l_new->e));
 
-                                       BM_elem_index_set(l_new, f_index);
-                                       BM_elem_index_set(l_new->radial_next, f_index);
+                                       BM_elem_index_set(l_new, f_index);  /* set_dirty */
+                                       BM_elem_index_set(l_new->radial_next, f_index);  /* set_dirty */
 
                                        BM_face_normal_update(f);
                                        BM_face_normal_update(f_new);
 
-                                       has_cut = TRUE;
+                                       has_cut = true;
                                }
                        }
                }
@@ -389,10 +394,10 @@ static void bm_decim_triangulate_end(BMesh *bm)
 {
        /* decimation finished, now re-join */
        BMIter iter;
-       BMEdge *e;
+       BMEdge *e, *e_next;
 
        /* boundary edges */
-       BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+       BM_ITER_MESH_MUTABLE (e, e_next, &iter, bm, BM_EDGES_OF_MESH) {
                BMLoop *l_a, *l_b;
                if (BM_edge_loop_pair(e, &l_a, &l_b)) {
                        const int l_a_index = BM_elem_index_get(l_a);
@@ -409,15 +414,15 @@ static void bm_decim_triangulate_end(BMesh *bm)
                                                                BM_vert_in_edge(e, l_b->next->v) ? l_b->prev->v : l_b->next->v,
                                                        };
 
-                                                       BLI_assert(ELEM3(vquad[0], vquad[1], vquad[2], vquad[3]) == FALSE);
-                                                       BLI_assert(ELEM3(vquad[1], vquad[0], vquad[2], vquad[3]) == FALSE);
-                                                       BLI_assert(ELEM3(vquad[2], vquad[1], vquad[0], vquad[3]) == FALSE);
-                                                       BLI_assert(ELEM3(vquad[3], vquad[1], vquad[2], vquad[0]) == FALSE);
+                                                       BLI_assert(ELEM(vquad[0], vquad[1], vquad[2], vquad[3]) == false);
+                                                       BLI_assert(ELEM(vquad[1], vquad[0], vquad[2], vquad[3]) == false);
+                                                       BLI_assert(ELEM(vquad[2], vquad[1], vquad[0], vquad[3]) == false);
+                                                       BLI_assert(ELEM(vquad[3], vquad[1], vquad[2], vquad[0]) == false);
 
                                                        if (is_quad_convex_v3(vquad[0]->co, vquad[1]->co, vquad[2]->co, vquad[3]->co)) {
                                                                /* highly unlikely to fail, but prevents possible double-ups */
                                                                BMFace *f[2] = {l_a->f, l_b->f};
-                                                               BM_faces_join(bm, f, 2, TRUE);
+                                                               BM_faces_join(bm, f, 2, true);
                                                        }
                                                }
                                        }
@@ -440,9 +445,11 @@ static void bm_decim_triangulate_end(BMesh *bm)
 static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other,
                                              const float customdata_fac)
 {
+       /* disable seam check - the seam check would have to be done per layer, its not really that important */
+//#define USE_SEAM
        /* these don't need to be updated, since they will get removed when the edge collapses */
        BMLoop *l_clear, *l_other;
-       const int is_manifold = BM_edge_is_manifold(l->e);
+       const bool is_manifold = BM_edge_is_manifold(l->e);
        int side;
 
        /* l defines the vert to collapse into  */
@@ -463,7 +470,9 @@ static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_cle
 
        /* now we have both corners of the face 'l->f' */
        for (side = 0; side < 2; side++) {
-               int is_seam = FALSE;
+#ifdef USE_SEAM
+               bool is_seam = false;
+#endif
                void *src[2];
                BMFace *f_exit = is_manifold ? l->radial_next->f : NULL;
                BMEdge *e_prev = l->e;
@@ -500,34 +509,44 @@ static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_cle
                                break;
                        }
 
+#ifdef USE_SEAM
                        /* break out unless we find a match */
-                       is_seam = TRUE;
+                       is_seam = true;
+#endif
 
                        /* ok. we have a loop. now be smart with it! */
                        for (i = 0; i < bm->ldata.totlayer; i++) {
                                if (CustomData_layer_has_math(&bm->ldata, i)) {
                                        const int offset = bm->ldata.layers[i].offset;
                                        const int type = bm->ldata.layers[i].type;
-                                       void *cd_src, *cd_iter;
-
-                                       /* todo, make nicer macros for this */
-                                       cd_src = (char *)src[0] + offset;
-                                       // cd_dst = (char *)src[1] + offset;  // UNUSED
-                                       cd_iter  = (char *)l_iter->head.data  + offset;
+                                       const void *cd_src[2] = {
+                                           POINTER_OFFSET(src[0], offset),
+                                           POINTER_OFFSET(src[1], offset),
+                                       };
+                                       void *cd_iter = POINTER_OFFSET(l_iter->head.data, offset);
 
                                        /* detect seams */
-                                       if (CustomData_data_equals(type, cd_src, cd_iter)) {
-                                               CustomData_bmesh_interp(&bm->ldata, src, w, NULL, 2, l_iter->head.data);
-                                               is_seam = FALSE;
+                                       if (CustomData_data_equals(type, cd_src[0], cd_iter)) {
+                                               CustomData_bmesh_interp_n(
+                                                       &bm->ldata, cd_src, w, NULL, ARRAY_SIZE(cd_src),
+                                                       POINTER_OFFSET(l_iter->head.data, offset), i);
+#ifdef USE_SEAM
+                                               is_seam = false;
+#endif
                                        }
                                }
                        }
 
+#ifdef USE_SEAM
                        if (is_seam) {
                                break;
                        }
+#endif
                }
        }
+
+//#undef USE_SEAM
+
 }
 #endif  /* USE_CUSTOMDATA */
 
@@ -564,7 +583,7 @@ static void bm_edge_tag_disable(BMEdge *e)
        }
 }
 
-static int bm_edge_tag_test(BMEdge *e)
+static bool bm_edge_tag_test(BMEdge *e)
 {
        /* is the edge or one of its faces tagged? */
        return (BM_elem_flag_test(e->v1, BM_ELEM_TAG) ||
@@ -587,7 +606,7 @@ BLI_INLINE int bm_edge_is_manifold_or_boundary(BMLoop *l)
 #endif
 }
 
-static int bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
+static bool bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
 {
        /* simply check that there is no overlap between faces and edges of each vert,
         * (excluding the 2 faces attached to 'e' and 'e' its self) */
@@ -598,7 +617,7 @@ static int bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
        e_iter = e_first;
        do {
                if (!bm_edge_is_manifold_or_boundary(e_iter->l)) {
-                       return TRUE;
+                       return true;
                }
                bm_edge_tag_disable(e_iter);
        } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v1)) != e_first);
@@ -606,7 +625,7 @@ static int bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
        e_iter = e_first;
        do {
                if (!bm_edge_is_manifold_or_boundary(e_iter->l)) {
-                       return TRUE;
+                       return true;
                }
                bm_edge_tag_disable(e_iter);
        } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
@@ -662,16 +681,16 @@ static int bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
        e_iter = e_first;
        do {
                if (bm_edge_tag_test(e_iter)) {
-                       return TRUE;
+                       return true;
                }
        } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
 
-       return FALSE;
+       return false;
 }
 
 /**
  * special, highly limited edge collapse function
- * intended for speed over flexibiliy.
+ * intended for speed over flexibility.
  * can only collapse edges connected to (1, 2) tris.
  *
  * Important - dont add vert/edge/face data on collapsing!
@@ -679,13 +698,13 @@ static int bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
  * \param e_clear_other let caller know what edges we remove besides \a e_clear
  * \param customdata_flag merge factor, scales from 0 - 1 ('v_clear' -> 'v_other')
  */
-static int bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2],
+static bool bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2],
 #ifdef USE_CUSTOMDATA
-                            const CD_UseFlag customdata_flag,
-                            const float customdata_fac
+                             const CD_UseFlag customdata_flag,
+                             const float customdata_fac
 #else
-                            const CD_UseFlag UNUSED(customdata_flag),
-                            const float UNUSED(customdata_fac)
+                             const CD_UseFlag UNUSED(customdata_flag),
+                             const float UNUSED(customdata_fac)
 #endif
                             )
 {
@@ -697,11 +716,11 @@ static int bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e
        if (BM_edge_is_manifold(e_clear)) {
                BMLoop *l_a, *l_b;
                BMEdge *e_a_other[2], *e_b_other[2];
-               int ok;
+               bool ok;
 
                ok = BM_edge_loop_pair(e_clear, &l_a, &l_b);
 
-               BLI_assert(ok == TRUE);
+               BLI_assert(ok == true);
                BLI_assert(l_a->f->len == 3);
                BLI_assert(l_b->f->len == 3);
 
@@ -724,9 +743,6 @@ static int bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e
                        e_b_other[0] = l_b->next->e;
                }
 
-               BLI_assert(BM_edge_share_vert(e_a_other[0], e_b_other[0]));
-               BLI_assert(BM_edge_share_vert(e_a_other[1], e_b_other[1]));
-
                /* we could assert this case, but better just bail out */
 #if 0
                BLI_assert(e_a_other[0] != e_b_other[0]);
@@ -738,9 +754,12 @@ static int bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e
                if (ELEM(e_a_other[0], e_b_other[0], e_b_other[1]) ||
                    ELEM(e_a_other[1], e_b_other[0], e_b_other[1]))
                {
-                       return FALSE;
+                       return false;
                }
 
+               BLI_assert(BM_edge_share_vert(e_a_other[0], e_b_other[0]));
+               BLI_assert(BM_edge_share_vert(e_a_other[1], e_b_other[1]));
+
                r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
                r_e_clear_other[1] = BM_elem_index_get(e_b_other[0]);
 
@@ -771,7 +790,7 @@ static int bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e
 
                // BM_mesh_validate(bm);
 
-               return TRUE;
+               return true;
        }
        else if (BM_edge_is_boundary(e_clear)) {
                /* same as above but only one triangle */
@@ -818,10 +837,10 @@ static int bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e
 
                // BM_mesh_validate(bm);
 
-               return TRUE;
+               return true;
        }
        else {
-               return FALSE;
+               return false;
        }
 }
 
@@ -858,7 +877,7 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
        }
 
        /* use for customdata merging */
-       if (LIKELY(compare_v3v3(e->v1->co, e->v2->co, FLT_EPSILON) == FALSE)) {
+       if (LIKELY(compare_v3v3(e->v1->co, e->v2->co, FLT_EPSILON) == false)) {
                customdata_fac = line_point_factor_v3(optimize_co, e->v1->co, e->v2->co);
 #if 0
                /* simple test for stupid collapse */
@@ -877,9 +896,7 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
                int i;
 
                if (vweights) {
-                       const int fac = CLAMPIS(customdata_fac, 0.0f, 1.0f);
-                       vweights[BM_elem_index_get(v_other)] = (vweights[v_clear_index]              * (1.0f - fac)) +
-                                                              (vweights[BM_elem_index_get(v_other)] * fac);
+                       vweights[BM_elem_index_get(v_other)] += vweights[v_clear_index];
                }
 
                e = NULL;  /* paranoid safety check */
@@ -937,7 +954,7 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
                                        else
                                                e_outer = l->prev->e;
 
-                                       BLI_assert(BM_vert_in_edge(e_outer, l->v) == FALSE);
+                                       BLI_assert(BM_vert_in_edge(e_outer, l->v) == false);
 
                                        bm_decim_build_edge_cost_single(e_outer, vquadrics, vweights, eheap, eheap_table);
                                }
@@ -960,17 +977,17 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
  * \brief BM_mesh_decimate
  * \param bm The mesh
  * \param factor face count multiplier [0 - 1]
- * \param vertex_weights Optional array of vertex  aligned weights [0 - 1],
+ * \param vweights Optional array of vertex  aligned weights [0 - 1],
  *        a vertex group is the usual source for this.
  */
-void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, const int do_triangulate)
+void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, const bool do_triangulate)
 {
        Heap *eheap;             /* edge heap */
        HeapNode **eheap_table;  /* edge index aligned table pointing to the eheap */
        Quadric *vquadrics;      /* vert index aligned quadrics */
        int tot_edge_orig;
        int face_tot_target;
-       int use_triangulate;
+       bool use_triangulate;
 
        CD_UseFlag customdata_flag = 0;
 
@@ -984,7 +1001,7 @@ void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, c
        vquadrics = MEM_callocN(sizeof(Quadric) * bm->totvert, __func__);
        /* since some edges may be degenerate, we might be over allocing a little here */
        eheap = BLI_heap_new_ex(bm->totedge);
-       eheap_table = MEM_callocN(sizeof(HeapNode *) * bm->totedge, __func__);
+       eheap_table = MEM_mallocN(sizeof(HeapNode *) * bm->totedge, __func__);
        tot_edge_orig = bm->totedge;
 
 
@@ -994,7 +1011,7 @@ void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, c
        bm_decim_build_edge_cost(bm, vquadrics, vweights, eheap, eheap_table);
 
        face_tot_target = bm->totface * factor;
-       bm->elem_index_dirty |= BM_FACE | BM_EDGE | BM_VERT;
+       bm->elem_index_dirty |= BM_ALL;
 
 
 #ifdef USE_CUSTOMDATA
@@ -1006,7 +1023,7 @@ void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, c
 
        /* iterative edge collapse and maintain the eheap */
        while ((bm->totface > face_tot_target) &&
-              (BLI_heap_is_empty(eheap) == FALSE) &&
+              (BLI_heap_is_empty(eheap) == false) &&
               (BLI_heap_node_value(BLI_heap_top(eheap)) != COST_INVALID))
        {
                // const float value = BLI_heap_node_value(BLI_heap_top(eheap));
@@ -1024,7 +1041,7 @@ void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, c
 
 
 #ifdef USE_TRIANGULATE
-       if (do_triangulate == FALSE) {
+       if (do_triangulate == false) {
                /* its possible we only had triangles, skip this step in that case */
                if (LIKELY(use_triangulate)) {
                        /* temp convert quads to triangles */