diff options
Diffstat (limited to 'source/blender/bmesh/operators/bmo_removedoubles.c')
| -rw-r--r-- | source/blender/bmesh/operators/bmo_removedoubles.c | 114 |
1 files changed, 44 insertions, 70 deletions
diff --git a/source/blender/bmesh/operators/bmo_removedoubles.c b/source/blender/bmesh/operators/bmo_removedoubles.c index 18704a6679f..d8e6f250adf 100644 --- a/source/blender/bmesh/operators/bmo_removedoubles.c +++ b/source/blender/bmesh/operators/bmo_removedoubles.c @@ -30,6 +30,7 @@ #include "BLI_math.h" #include "BLI_alloca.h" +#include "BLI_kdtree.h" #include "BLI_stackdefines.h" #include "BLI_stack.h" @@ -277,22 +278,7 @@ void bmo_weld_verts_exec(BMesh *bm, BMOperator *op) BMO_mesh_delete_oflag_context(bm, ELE_DEL, DEL_ONLYTAGGED); } -static int vergaverco(const void *e1, const void *e2) -{ - const BMVert *v1 = *(const void **)e1, *v2 = *(const void **)e2; - float x1 = v1->co[0] + v1->co[1] + v1->co[2]; - float x2 = v2->co[0] + v2->co[1] + v2->co[2]; - - if (x1 > x2) return 1; - else if (x1 < x2) return -1; - else return 0; -} - -// #define VERT_TESTED 1 // UNUSED -#define VERT_DOUBLE 2 -#define VERT_TARGET 4 #define VERT_KEEP 8 -// #define VERT_MARK 16 // UNUSED #define VERT_IN 32 #define EDGE_MARK 1 @@ -440,20 +426,24 @@ void bmo_collapse_exec(BMesh *bm, BMOperator *op) edge_stack = BLI_stack_new(sizeof(BMEdge *), __func__); BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { - float min[3], max[3], center[3]; + float center[3]; + int count = 0; BMVert *v_tar; + zero_v3(center); + if (!BMO_edge_flag_test(bm, e, EDGE_MARK)) continue; BLI_assert(BLI_stack_is_empty(edge_stack)); - INIT_MINMAX(min, max); for (e = BMW_begin(&walker, e->v1); e; e = BMW_step(&walker)) { BLI_stack_push(edge_stack, &e); - minmax_v3v3_v3(min, max, e->v1->co); - minmax_v3v3_v3(min, max, e->v2->co); + add_v3_v3(center, e->v1->co); + add_v3_v3(center, e->v2->co); + + count += 2; /* prevent adding to slot_targetmap multiple times */ BM_elem_flag_disable(e->v1, BM_ELEM_TAG); @@ -461,8 +451,7 @@ void bmo_collapse_exec(BMesh *bm, BMOperator *op) } if (!BLI_stack_is_empty(edge_stack)) { - - mid_v3_v3v3(center, min, max); + mul_v3_fl(center, 1.0f / count); /* snap edges to a point. for initial testing purposes anyway */ e = *(BMEdge **)BLI_stack_peek(edge_stack); @@ -581,77 +570,62 @@ static void bmesh_find_doubles_common( BMesh *bm, BMOperator *op, BMOperator *optarget, BMOpSlot *optarget_slot) { - BMVert **verts; - int verts_len; + const BMOpSlot *slot_verts = BMO_slot_get(op->slots_in, "verts"); + BMVert * const *verts = (BMVert **)slot_verts->data.buf; + const int verts_len = slot_verts->len; - int i, j, keepvert = 0; + bool has_keep_vert = false; + bool found_duplicates = false; const float dist = BMO_slot_float_get(op->slots_in, "dist"); - const float dist_sq = dist * dist; - const float dist3 = ((float)M_SQRT3 + 0.00005f) * dist; /* Just above sqrt(3) */ /* Test whether keep_verts arg exists and is non-empty */ if (BMO_slot_exists(op->slots_in, "keep_verts")) { BMOIter oiter; - keepvert = BMO_iter_new(&oiter, op->slots_in, "keep_verts", BM_VERT) != NULL; + has_keep_vert = BMO_iter_new(&oiter, op->slots_in, "keep_verts", BM_VERT) != NULL; } - /* get the verts as an array we can sort */ - verts = BMO_slot_as_arrayN(op->slots_in, "verts", &verts_len); - - /* sort by vertex coordinates added together */ - qsort(verts, verts_len, sizeof(BMVert *), vergaverco); - /* Flag keep_verts */ - if (keepvert) { + if (has_keep_vert) { BMO_slot_buffer_flag_enable(bm, op->slots_in, "keep_verts", BM_VERT, VERT_KEEP); } - for (i = 0; i < verts_len; i++) { - BMVert *v_check = verts[i]; - - if (BMO_vert_flag_test(bm, v_check, VERT_DOUBLE | VERT_TARGET)) { - continue; + int *duplicates = MEM_mallocN(sizeof(int) * verts_len, __func__); + { + KDTree *tree = BLI_kdtree_new(verts_len); + for (int i = 0; i < verts_len; i++) { + BLI_kdtree_insert(tree, i, verts[i]->co); + if (has_keep_vert && BMO_vert_flag_test(bm, verts[i], VERT_KEEP)) { + duplicates[i] = i; + } + else { + duplicates[i] = -1; + } } - for (j = i + 1; j < verts_len; j++) { - BMVert *v_other = verts[j]; - - /* a match has already been found, (we could check which is best, for now don't) */ - if (BMO_vert_flag_test(bm, v_other, VERT_DOUBLE | VERT_TARGET)) { - continue; - } + BLI_kdtree_balance(tree); + found_duplicates = BLI_kdtree_calc_duplicates_fast(tree, dist, false, duplicates) != 0; + BLI_kdtree_free(tree); + } - /* Compare sort values of the verts using 3x tolerance (allowing for the tolerance - * on each of the three axes). This avoids the more expensive length comparison - * for most vertex pairs. */ - if ((v_other->co[0] + v_other->co[1] + v_other->co[2]) - - (v_check->co[0] + v_check->co[1] + v_check->co[2]) > dist3) - { - break; + if (found_duplicates) { + for (int i = 0; i < verts_len; i++) { + BMVert *v_check = verts[i]; + if (duplicates[i] == -1) { + /* nop (others can use as target) */ } - - if (keepvert) { - if (BMO_vert_flag_test(bm, v_other, VERT_KEEP) == BMO_vert_flag_test(bm, v_check, VERT_KEEP)) - continue; + else if (duplicates[i] == i) { + /* keep (others can use as target) */ } - - if (compare_len_squared_v3v3(v_check->co, v_other->co, dist_sq)) { - - /* If one vert is marked as keep, make sure it will be the target */ - if (BMO_vert_flag_test(bm, v_other, VERT_KEEP)) { - SWAP(BMVert *, v_check, v_other); - } - - BMO_vert_flag_enable(bm, v_other, VERT_DOUBLE); - BMO_vert_flag_enable(bm, v_check, VERT_TARGET); - - BMO_slot_map_elem_insert(optarget, optarget_slot, v_other, v_check); + else { + BMVert *v_other = verts[duplicates[i]]; + BLI_assert(ELEM(duplicates[duplicates[i]], -1, duplicates[i])); + BMO_slot_map_elem_insert(optarget, optarget_slot, v_check, v_other); } } } - MEM_freeN(verts); + MEM_freeN(duplicates); } void bmo_remove_doubles_exec(BMesh *bm, BMOperator *op) |