diff options
author | Bastien Montagne <montagne29@wanadoo.fr> | 2012-04-19 16:31:39 +0400 |
---|---|---|
committer | Bastien Montagne <montagne29@wanadoo.fr> | 2012-04-19 16:31:39 +0400 |
commit | 7cadd242d3eb7a29f19efe1d1462dbe12998c196 (patch) | |
tree | 2d45c922527aa34bd78001f826baf976008afe54 /source | |
parent | 75b869e428cdb324ec338538efd4ab9dabd7d53a (diff) |
BMESH_TODO: xsort of vertices working again.
This commits adds a new function which can remap vertices/edges/faces of a BMesh in a new given order:
void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx)
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh.c | 170 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh.h | 1 | ||||
-rw-r--r-- | source/blender/editors/mesh/editmesh_tools.c | 86 |
3 files changed, 220 insertions, 37 deletions
diff --git a/source/blender/bmesh/intern/bmesh_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c index 826d4db4556..c70e694f9ea 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.c +++ b/source/blender/bmesh/intern/bmesh_mesh.c @@ -584,6 +584,176 @@ void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *fu } +/** + * Remaps the vertices, edges and/or faces of the bmesh as indicated by vert/edge/face_idx arrays + * (xxx_idx[org_index] = new_index). + * + * A NULL array means no changes. + * + * Note: - Does not mess with indices, just sets elem_index_dirty flag. + * - For verts/edges/faces only (as loops must remain "ordered" and "aligned" + * on a per-face basis...). + * + * WARNING: Be careful if you keep pointers to affected BM elements, or arrays, when using this func! + */ +void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx) +{ + /* Mapping old to new pointers. */ + GHash *vptr_map = NULL, *eptr_map = NULL, *fptr_map = NULL; + BMIter iter, iterl; + BMVert *ve; + BMEdge *ed; + BMFace *fa; + BMLoop *lo; + + if (!(vert_idx || edge_idx || face_idx)) + return; + + /* Remap vertices */ + if (vert_idx) { + BMVert **verts_pool, *verts_copy, **vep; + int i, totvert = bm->totvert; + int *new_idx = NULL; + + /* Init the old-to-new vert pointers mapping */ + vptr_map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "BM_mesh_remap vert pointers mapping"); + + /* Make a copy of all vertices. */ + verts_pool = MEM_callocN(sizeof(BMVert*) * totvert, "BM_mesh_remap verts pool"); + BM_iter_as_array(bm, BM_VERTS_OF_MESH, NULL, (void**)verts_pool, totvert); + verts_copy = MEM_mallocN(sizeof(BMVert) * totvert, "BM_mesh_remap verts copy"); + for (i = totvert, ve = verts_copy + totvert - 1, vep = verts_pool + totvert - 1; i--; ve--, vep--) { + *ve = **vep; +/* printf("*vep: %p, verts_pool[%d]: %p\n", *vep, i, verts_pool[i]);*/ + } + + /* Copy back verts to their new place, and update old2new pointers mapping. */ + new_idx = vert_idx + totvert - 1; + ve = verts_copy + totvert - 1; + vep = verts_pool + totvert - 1; /* old, org pointer */ + for (i = totvert; i--; new_idx--, ve--, vep--) { + BMVert *new_vep = verts_pool[*new_idx]; + *new_vep = *ve; +/* printf("mapping vert from %d to %d (%p/%p to %p)\n", i, *new_idx, *vep, verts_pool[i], new_vep);*/ + BLI_ghash_insert(vptr_map, (void*)*vep, (void*)new_vep); + } + bm->elem_index_dirty |= BM_VERT; + + MEM_freeN(verts_pool); + MEM_freeN(verts_copy); + } + + /* XXX Code not tested yet (though I don't why it would fail)! */ + if (edge_idx) { + BMEdge **edges_pool, *edges_copy, **edp; + int i, totedge = bm->totedge; + int *new_idx = NULL; + + /* Init the old-to-new vert pointers mapping */ + eptr_map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "BM_mesh_remap edge pointers mapping"); + + /* Make a copy of all vertices. */ + edges_pool = MEM_callocN(sizeof(BMEdge*) * totedge, "BM_mesh_remap edges pool"); + BM_iter_as_array(bm, BM_EDGES_OF_MESH, NULL, (void**)edges_pool, totedge); + edges_copy = MEM_mallocN(sizeof(BMEdge) * totedge, "BM_mesh_remap edges copy"); + for (i = totedge, ed = edges_copy + totedge - 1, edp = edges_pool + totedge - 1; i--; ed--, edp--) { + *ed = **edp; + } + + /* Copy back verts to their new place, and update old2new pointers mapping. */ + new_idx = edge_idx + totedge - 1; + ed = edges_copy + totedge - 1; + edp = edges_pool + totedge - 1; /* old, org pointer */ + for (i = totedge; i--; new_idx--, ed--, edp--) { + BMEdge *new_edp = edges_pool[*new_idx]; + *new_edp = *ed; + BLI_ghash_insert(eptr_map, (void*)*edp, (void*)new_edp); + } + + bm->elem_index_dirty |= BM_EDGE; + + MEM_freeN(edges_pool); + MEM_freeN(edges_copy); + } + + /* XXX Code not tested yet (though I don't why it would fail)! */ + if (face_idx) { + BMFace **faces_pool, *faces_copy, **fap; + int i, totface = bm->totface; + int *new_idx = NULL; + + /* Init the old-to-new vert pointers mapping */ + fptr_map = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "BM_mesh_remap face pointers mapping"); + + /* Make a copy of all vertices. */ + faces_pool = MEM_callocN(sizeof(BMFace*) * totface, "BM_mesh_remap faces pool"); + BM_iter_as_array(bm, BM_FACES_OF_MESH, NULL, (void**)faces_pool, totface); + faces_copy = MEM_mallocN(sizeof(BMFace) * totface, "BM_mesh_remap faces copy"); + for (i = totface, fa = faces_copy + totface - 1, fap = faces_pool + totface - 1; i--; fa--, fap--) { + *fa = **fap; + } + + /* Copy back verts to their new place, and update old2new pointers mapping. */ + new_idx = face_idx + totface - 1; + fa = faces_copy + totface - 1; + fap = faces_pool + totface - 1; /* old, org pointer */ + for (i = totface; i--; new_idx--, fa--, fap--) { + BMFace *new_fap = faces_pool[*new_idx]; + *new_fap = *fa; + BLI_ghash_insert(fptr_map, (void*)*fap, (void*)new_fap); + } + + bm->elem_index_dirty |= BM_FACE; + + MEM_freeN(faces_pool); + MEM_freeN(faces_copy); + } + + /* And now, fix all vertices/edges/faces/loops pointers! */ + /* Verts' pointers, only edge pointers... */ + if (eptr_map) { + BM_ITER(ve, &iter, bm, BM_VERTS_OF_MESH, NULL) { +/* printf("Vert e: %p -> %p\n", ve->e, BLI_ghash_lookup(eptr_map, (const void*)ve->e));*/ + ve->e = BLI_ghash_lookup(eptr_map, (const void*)ve->e); + } + } + + /* Edges' pointers, only vert pointers (as we don’t mess with loops!)... */ + if (vptr_map) { + BM_ITER(ed, &iter, bm, BM_EDGES_OF_MESH, NULL) { +/* printf("Edge v1: %p -> %p\n", ed->v1, BLI_ghash_lookup(vptr_map, (const void*)ed->v1));*/ +/* printf("Edge v2: %p -> %p\n", ed->v2, BLI_ghash_lookup(vptr_map, (const void*)ed->v2));*/ + ed->v1 = BLI_ghash_lookup(vptr_map, (const void*)ed->v1); + ed->v2 = BLI_ghash_lookup(vptr_map, (const void*)ed->v2); + } + } + + /* Faces' pointers (loops, in fact), always needed... */ + BM_ITER(fa, &iter, bm, BM_FACES_OF_MESH, NULL) { + BM_ITER(lo, &iterl, bm, BM_LOOPS_OF_FACE, fa) { + if (vptr_map) { +/* printf("Loop v: %p -> %p\n", lo->v, BLI_ghash_lookup(vptr_map, (const void*)lo->v));*/ + lo->v = BLI_ghash_lookup(vptr_map, (const void*)lo->v); + } + if (eptr_map) { +/* printf("Loop e: %p -> %p\n", lo->e, BLI_ghash_lookup(eptr_map, (const void*)lo->e));*/ + lo->e = BLI_ghash_lookup(eptr_map, (const void*)lo->e); + } + if (fptr_map) { +/* printf("Loop f: %p -> %p\n", lo->f, BLI_ghash_lookup(fptr_map, (const void*)lo->f));*/ + lo->f = BLI_ghash_lookup(fptr_map, (const void*)lo->f); + } + } + } + + if (vptr_map) + BLI_ghash_free(vptr_map, NULL, NULL); + if (eptr_map) + BLI_ghash_free(eptr_map, NULL, NULL); + if (fptr_map) + BLI_ghash_free(fptr_map, NULL, NULL); +} + BMVert *BM_vert_at_index(BMesh *bm, const int index) { return BLI_mempool_findelem(bm->vpool, index); diff --git a/source/blender/bmesh/intern/bmesh_mesh.h b/source/blender/bmesh/intern/bmesh_mesh.h index f48cc09af3b..970db6339c3 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.h +++ b/source/blender/bmesh/intern/bmesh_mesh.h @@ -43,6 +43,7 @@ void bmesh_edit_end(BMesh *bm, int flag); void BM_mesh_elem_index_ensure(BMesh *bm, const char hflag); void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *func, const char *msg_a, const char *msg_b); +void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx); BMVert *BM_vert_at_index(BMesh *bm, const int index); BMEdge *BM_edge_at_index(BMesh *bm, const int index); diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c index e5eb7ad11fd..fe9571b1978 100644 --- a/source/blender/editors/mesh/editmesh_tools.c +++ b/source/blender/editors/mesh/editmesh_tools.c @@ -3599,15 +3599,14 @@ void MESH_OT_select_mirror(wmOperatorType *ot) RNA_def_boolean(ot->srna, "extend", 0, "Extend", "Extend the existing selection"); } -#if 0 /* UNUSED */ /* qsort routines. not sure how to make these * work, since we aren't using linked lists for * geometry anymore. might need a sortof "swap" * function for bmesh elements. */ typedef struct xvertsort { - float x; - BMVert *v1; + int x; /* X screen-coordinate */ + int org_idx; /* Original index of this vertex _in the mempool_ */ } xvertsort; @@ -3615,11 +3614,13 @@ static int vergxco(const void *v1, const void *v2) { const xvertsort *x1 = v1, *x2 = v2; - if (x1->x > x2->x) return 1; - else if (x1->x < x2->x) return -1; - return 0; + /* We move unchanged vertices (org_idx < 0) at the begining of the sorted list. */ + if (x1->org_idx >= 0 && x2->org_idx >= 0) + return (x1->x > x2->x) - (x1->x < x2->x); + return (x2->org_idx < 0) - (x1->org_idx < 0); } +#if 0 /* Unused */ struct facesort { uintptr_t x; struct EditFace *efa; @@ -3635,66 +3636,77 @@ static int vergface(const void *v1, const void *v2) } #endif -// XXX is this needed? -/* called from buttons */ -#if 0 /* UNUSED */ -static void xsortvert_flag__doSetX(void *userData, EditVert *UNUSED(eve), int x, int UNUSED(y), int index) +static void xsortvert_flag__doSetX(void *userData, BMVert *UNUSED(eve), int x, int UNUSED(y), int index) { xvertsort *sortblock = userData; sortblock[index].x = x; } -#endif /* all verts with (flag & 'flag') are sorted */ -static void xsortvert_flag(bContext *UNUSED(C), int UNUSED(flag)) +static void xsortvert_flag(bContext *C, int flag) { - /* BMESH_TODO */ -#if 0 //hrm, geometry isn't in linked lists anymore. . . ViewContext vc; BMEditMesh *em; - BMVert *eve; + BMVert *ve; BMIter iter; xvertsort *sortblock; - ListBase tbase; - int i, amount; + int *unchangedblock, *vmap; + int totvert, sorted = 0, unchanged = 0, i; em_setup_viewcontext(C, &vc); em = vc.em; - amount = em->bm->totvert; - sortblock = MEM_callocN(sizeof(xvertsort) * amount, "xsort"); - BM_ITER (eve, &iter, em->bm, BM_VERTS_OF_MESH, NULL) { - if (BM_elem_flag_test(eve, BM_ELEM_SELECT)) - sortblock[i].v1 = eve; + totvert = em->bm->totvert; + + sortblock = MEM_callocN(sizeof(xvertsort) * totvert, "xsort sorted"); + /* Stores unchanged verts, will be reused as final old2new vert mapping... */ + unchangedblock = MEM_callocN(sizeof(int) * totvert, "xsort unchanged"); + BM_ITER_INDEX(ve, &iter, em->bm, BM_VERTS_OF_MESH, NULL, i) { + if (BM_elem_flag_test(ve, flag)) { + sortblock[i].org_idx = i; + sorted++; + } + else { + unchangedblock[unchanged++] = i; + sortblock[i].org_idx = -1; + } } - +/* printf("%d verts: %d to be sorted, %d unchanged…\n", totvert, sorted, unchanged);*/ + if (sorted == 0) + return; + ED_view3d_init_mats_rv3d(vc.obedit, vc.rv3d); mesh_foreachScreenVert(&vc, xsortvert_flag__doSetX, sortblock, V3D_CLIP_TEST_OFF); - qsort(sortblock, amount, sizeof(xvertsort), vergxco); - - /* make temporal listbase */ - tbase.first = tbase.last = 0; - for (i = 0; i < amount; i++) { - eve = sortblock[i].v1; + qsort(sortblock, totvert, sizeof(xvertsort), vergxco); - if (eve) { - BLI_remlink(&vc.em->verts, eve); - BLI_addtail(&tbase, eve); - } + /* Convert sortblock into an array mapping old idx to new. */ + vmap = unchangedblock; + unchangedblock = NULL; + if (unchanged) { + unchangedblock = MEM_mallocN(sizeof(int) * unchanged, "xsort unchanged"); + memcpy(unchangedblock, vmap, unchanged * sizeof(int)); + } + for (i = totvert; i--; ) { + if (i < unchanged) + vmap[unchangedblock[i]] = i; + else + vmap[sortblock[i].org_idx] = i; } - - BLI_movelisttolist(&vc.em->verts, &tbase); MEM_freeN(sortblock); -#endif + if (unchangedblock) + MEM_freeN(unchangedblock); + + BM_mesh_remap(em->bm, vmap, NULL, NULL); + MEM_freeN(vmap); } static int edbm_vertices_sort_exec(bContext *C, wmOperator *UNUSED(op)) { - xsortvert_flag(C, SELECT); + xsortvert_flag(C, BM_ELEM_SELECT); return OPERATOR_FINISHED; } |