bmesh-decimator update
authorCampbell Barton <ideasman42@gmail.com>
Sun, 21 Oct 2012 15:20:53 +0000 (15:20 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Sun, 21 Oct 2012 15:20:53 +0000 (15:20 +0000)
- update face normals when triangulating.
- avoid divide by zero when interpolating customdata on a zero length edge.
- replace zero float comparisons with fabsf() < FLT_EPSILON to avoid numeric error.

also renamed BLI_heap_empty() --> BLI_heap_is_empty() so its obviously readonly function.

source/blender/blenlib/BLI_heap.h
source/blender/blenlib/intern/BLI_heap.c
source/blender/blenlib/intern/quadric.c
source/blender/bmesh/intern/bmesh_decimate.c
source/blender/bmesh/operators/bmo_utils.c
source/blender/editors/include/ED_object.h
source/blender/editors/mesh/editmesh_select.c
source/blender/modifiers/intern/MOD_skin.c

index 9d7e6107f199469872656cd6b6f384b3e4c675ca..adbbf266b4e6f1941944ee459b1b67b2270e1c02 100644 (file)
@@ -54,7 +54,7 @@ HeapNode       *BLI_heap_insert(Heap *heap, float value, void *ptr);
 void            BLI_heap_remove(Heap *heap, HeapNode *node);
 
 /* Return 0 if the heap is empty, 1 otherwise. */
-int             BLI_heap_empty(Heap *heap);
+int             BLI_heap_is_empty(Heap *heap);
 
 /* Return the size of the heap. */
 int             BLI_heap_size(Heap *heap);
@@ -69,5 +69,4 @@ void           *BLI_heap_popmin(Heap *heap);
 float           BLI_heap_node_value(HeapNode *heap);
 void           *BLI_heap_node_ptr(HeapNode *heap);
 
-#endif
-
+#endif  /* __BLI_HEAP_H__ */
index 5e0762a5d6864f17dbe2f2eab7b72eaa8c725b34..5a33e998561d632410035be1a21d67cc44724889 100644 (file)
@@ -165,7 +165,7 @@ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
        return node;
 }
 
-int BLI_heap_empty(Heap *heap)
+int BLI_heap_is_empty(Heap *heap)
 {
        return (heap->size == 0);
 }
index 1c04beacbfb81248486c712532addda6f71771f2..bb39cb61e78193f09f2b9b88c637f264d7345d7a 100644 (file)
@@ -117,7 +117,7 @@ int BLI_quadric_optimize(const Quadric *q, float v[3])
                             m[1][0], m[1][1], m[1][2],
                             m[2][0], m[2][1], m[2][2]);
 
-       if (det != 0.0f) {
+       if (fabsf(det) > FLT_EPSILON) {
                invert_m3(m);
                BLI_quadric_to_vector_v3(q, v);
                mul_m3_v3(m, v);
index b5783c4b9f06c8b6b6554ca6a06414046037646c..18c6df8696c1e79a4eb2fbc8bc5ab406187252db 100644 (file)
 /* defines for testing */
 #define USE_CUSTOMDATA
 #define USE_TRIANGULATE
-#define USE_PRESERVE_BOUNDARY  /* could disable but its nicer not to mix boundary/non-boundry verts */
+// #define USE_PRESERVE_BOUNDARY  /* could disable but its nicer not to mix boundary/non-boundry verts */
 
 /* these checks are for rare cases that we can't avoid since they are valid meshes still */
 #define USE_SAFETY_CHECKS
 
-#define BOUNDARY_PRESERVE_WEIGHT 1.0f
+#define BOUNDARY_PRESERVE_WEIGHT 100.0f
+
 
 #ifdef USE_PRESERVE_BOUNDARY
 /* re-use smooth for tagging boundary edges, not totally great */
@@ -102,7 +103,7 @@ static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
                        f = e->l->f;
                        cross_v3_v3v3(edge_cross, edge_vector, f->no);
 
-                       if (normalize_v3(edge_cross) != 0.0f) {
+                       if (fabsf(normalize_v3(edge_cross)) > FLT_EPSILON) {
                                Quadric q;
                                BLI_quadric_from_v3_dist(&q, edge_vector, -dot_v3v3(edge_cross, e->v1->co));
                                BLI_quadric_mul(&q, BOUNDARY_PRESERVE_WEIGHT);
@@ -188,6 +189,7 @@ static void bm_decim_build_edge_cost_single(BMEdge *e,
        q2 = &vquadrics[BM_elem_index_get(e->v2)];
 
        cost = (BLI_quadric_evaluate(q1, optimize_co) + BLI_quadric_evaluate(q2, optimize_co));
+       // print("COST %.12f\n");
 
        eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, cost, e);
 }
@@ -305,6 +307,9 @@ static int bm_decim_triangulate_begin(BMesh *bm)
                                        BM_elem_index_set(l_new, f_index);
                                        BM_elem_index_set(l_new->radial_next, f_index);
 
+                                       BM_face_normal_update(f);
+                                       BM_face_normal_update(f_new);
+
                                        has_cut = TRUE;
                                }
                        }
@@ -406,6 +411,8 @@ static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_cle
                        w[1] = customdata_fac;
                }
 
+               // print_v2("weights", w);
+
                /* WATCH IT! - should NOT reference (_clear or _other) vars for this while loop */
 
                /* walk around the fan using 'e_prev' */
@@ -496,16 +503,29 @@ static int bm_edge_collapse_is_degenerate(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) */
 
-       const int is_boundary = BM_edge_is_boundary(e_first);
-
        BMEdge *e_iter;
 
 #ifdef USE_PRESERVE_BOUNDARY
+       const int is_boundary = BM_edge_is_boundary(e_first);
+
        if (BM_elem_flag_test(e_first->v1, BM_ELEM_IS_BOUNDARY) !=
            BM_elem_flag_test(e_first->v2, BM_ELEM_IS_BOUNDARY))
        {
                return TRUE;
        }
+       if ((is_boundary == FALSE) &&
+           (BM_elem_flag_test(e_first->v1, BM_ELEM_IS_BOUNDARY) ||
+            BM_elem_flag_test(e_first->v2, BM_ELEM_IS_BOUNDARY)))
+       {
+               return TRUE;
+       }
+
+       /* sanity */
+       if (is_boundary == TRUE) {
+               BLI_assert(BM_elem_flag_test(e_first->v1, BM_ELEM_IS_BOUNDARY) != FALSE);
+               BLI_assert(BM_elem_flag_test(e_first->v2, BM_ELEM_IS_BOUNDARY) != FALSE);
+       }
+
 #endif  /* USE_PRESERVE_BOUNDARY */
 
        /* clear flags on both disks */
@@ -514,15 +534,6 @@ static int bm_edge_collapse_is_degenerate(BMEdge *e_first)
                if (!(BM_edge_is_manifold(e_iter) || BM_edge_is_boundary(e_iter))) {
                        return TRUE;
                }
-#ifdef USE_PRESERVE_BOUNDARY
-               /* not exactly a degenerate case, but dont collapse edges into boundries */
-               if ((is_boundary == FALSE) &&
-                   (BM_elem_flag_test(e_iter->v1, BM_ELEM_IS_BOUNDARY) ||
-                    BM_elem_flag_test(e_iter->v2, BM_ELEM_IS_BOUNDARY)))
-               {
-                       return TRUE;
-               }
-#endif  /* USE_PRESERVE_BOUNDARY */
                bm_edge_tag_disable(e_iter);
        } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v1)) != e_first);
 
@@ -531,15 +542,6 @@ static int bm_edge_collapse_is_degenerate(BMEdge *e_first)
                if (!(BM_edge_is_manifold(e_iter) || BM_edge_is_boundary(e_iter))) {
                        return TRUE;
                }
-#ifdef USE_PRESERVE_BOUNDARY
-               /* not exactly a degenerate case, but dont collapse edges into boundries */
-               if ((is_boundary == FALSE) &&
-                   (BM_elem_flag_test(e_iter->v1, BM_ELEM_IS_BOUNDARY) ||
-                    BM_elem_flag_test(e_iter->v2, BM_ELEM_IS_BOUNDARY)))
-               {
-                       return TRUE;
-               }
-#endif  /* USE_PRESERVE_BOUNDARY */
                bm_edge_tag_disable(e_iter);
        } while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
 
@@ -765,7 +767,7 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
                                    const CD_UseFlag customdata_flag)
 {
        int e_clear_other[2];
-       BMVert *v = e->v1;
+       BMVert *v_other = e->v1;
        int v_clear_index = BM_elem_index_get(e->v2);  /* the vert is removed so only store the index */
        float optimize_co[3];
        float customdata_fac;
@@ -773,7 +775,18 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
        bm_decim_calc_target_co(e, optimize_co, vquadrics);
 
        /* use for customdata merging */
-       customdata_fac = line_point_factor_v3(optimize_co, e->v1->co, e->v2->co);
+       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);
+
+               /* simple test for stupid collapse */
+//             if (customdata_fac < 0.0 - FLT_EPSILON || customdata_fac > 1.0f + FLT_EPSILON) {
+//                     return;
+//             }
+       }
+       else {
+               /* avoid divide by zero */
+               customdata_fac = 0.5f;
+       }
 
        if (bm_edge_collapse(bm, e, e->v2, e_clear_other, customdata_flag, customdata_fac)) {
                /* update collapse info */
@@ -781,7 +794,7 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
 
                e = NULL;  /* paranoid safety check */
 
-               copy_v3_v3(v->co, optimize_co);
+               copy_v3_v3(v_other->co, optimize_co);
 
                /* remove eheap */
                for (i = 0; i < 2; i++) {
@@ -793,23 +806,23 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
                }
 
                /* update vertex quadric, add kept vertex from killed vertex */
-               BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(v)], &vquadrics[v_clear_index]);
+               BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(v_other)], &vquadrics[v_clear_index]);
 
                /* update connected normals */
 
                /* in fact face normals are not used for progressive updates, no need to update them */
                // BM_vert_normal_update_all(v);
-               BM_vert_normal_update(v);
+               BM_vert_normal_update(v_other);
 
                /* update error costs and the eheap */
-               if (LIKELY(v->e)) {
+               if (LIKELY(v_other->e)) {
                        BMEdge *e_iter;
                        BMEdge *e_first;
-                       e_iter = e_first = v->e;
+                       e_iter = e_first = v_other->e;
                        do {
                                BLI_assert(BM_edge_find_double(e_iter) == NULL);
                                bm_decim_build_edge_cost_single(e_iter, vquadrics, eheap, eheap_table);
-                       } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
+                       } while ((e_iter = bmesh_disk_edge_next(e_iter, v_other)) != e_first);
                }
        }
 }
@@ -859,10 +872,13 @@ void BM_mesh_decimate(BMesh *bm, const float factor)
 #endif
 
        /* iterative edge collapse and maintain the eheap */
-       while ((bm->totface > face_tot_target) && (BLI_heap_empty(eheap) == FALSE)) {
+       while ((bm->totface > face_tot_target) && (BLI_heap_is_empty(eheap) == FALSE)) {
+               // const float value = BLI_heap_node_value(BLI_heap_top(eheap));
                BMEdge *e = BLI_heap_popmin(eheap);
                BLI_assert(BM_elem_index_get(e) < tot_edge_orig);  /* handy to detect corruptions elsewhere */
 
+               // printf("COST %.10f\n", value);
+
                /* under normal conditions wont be accessed again,
                 * but NULL just incase so we don't use freed node */
                eheap_table[BM_elem_index_get(e)] = NULL;
index 7562d7e1da24be29bc0aadb8890c038f1f87c5db..42c5557327b5e3c22c525fca4f9fdf9ab9e93c3a 100644 (file)
@@ -1281,7 +1281,7 @@ void bmo_shortest_path_exec(BMesh *bm, BMOperator *op)
                vert_list[i].hn = BLI_heap_insert(h, vert_list[i].weight, vert_list[i].v);
        }
 
-       while (!BLI_heap_empty(h)) {
+       while (!BLI_heap_is_empty(h)) {
                BMEdge *e;
                BMIter e_i;
                float v_weight;
index d6ac9eb750d7810ad29a43e365284a60b500929f..0d0b8d8e797f655c6f362f54e7ccd52f5e1cb4cc 100644 (file)
@@ -203,4 +203,3 @@ void ED_object_select_linked_by_id(struct bContext *C, struct ID *id);
 #endif
 
 #endif /* __ED_OBJECT_H__ */
-
index 65cd9c7d709ce017290758df696fe0945c2ebca6..c0c4be3ec776774944d5e0cc47492cc604545a0f 100644 (file)
@@ -1326,7 +1326,7 @@ static int edgetag_shortest_path(Scene *scene, BMEditMesh *em, BMEdge *source, B
        EDBM_index_arrays_init(em, 1, 1, 0);
        targetnum = BM_elem_index_get(target);
 
-       while (!BLI_heap_empty(heap)) {
+       while (!BLI_heap_is_empty(heap)) {
                mednum = GET_INT_FROM_POINTER(BLI_heap_popmin(heap));
                e = EDBM_edge_at_index(em, mednum);
 
index 222f13185ea06cb8c1f72afa5b2854c48563d24d..7dd988ac3211c55ef623c9ef19ff0245e6d185b3 100644 (file)
@@ -1422,7 +1422,7 @@ static void hull_merge_triangles(SkinOutput *so, const SkinModifierData *smd)
                }
        }
 
-       while (!BLI_heap_empty(heap)) {
+       while (!BLI_heap_is_empty(heap)) {
                BMFace *adj[2];
 
                e = BLI_heap_popmin(heap);