diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-04-16 18:57:02 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-04-16 18:57:02 +0400 |
commit | ea0ad013d35984cba06cd8318fd42cc39c74c37f (patch) | |
tree | 2ef30bc202ead8349911731d6b1328da218ad7fe | |
parent | e39ea5f0a36b88da21fe6ddb09ebdf38399fe6a3 (diff) |
bmesh speedup for bvh building, replace SmallHash with BLI_bitmap, using a hash doesn't make much sense since in most cases all vertices are accessed and the hash isn't guaranteed to be small.
gives ~9x speedup to filling 'cagecos' in my own tests on a high poly mesh.
-rw-r--r-- | source/blender/blenkernel/intern/editmesh_bvh.c | 52 |
1 files changed, 28 insertions, 24 deletions
diff --git a/source/blender/blenkernel/intern/editmesh_bvh.c b/source/blender/blenkernel/intern/editmesh_bvh.c index 98750b412f0..a94d1d1e5aa 100644 --- a/source/blender/blenkernel/intern/editmesh_bvh.c +++ b/source/blender/blenkernel/intern/editmesh_bvh.c @@ -34,7 +34,7 @@ #include "DNA_object_types.h" #include "BLI_math.h" -#include "BLI_smallhash.h" +#include "BLI_bitmap.h" #include "BKE_DerivedMesh.h" #include "BKE_editmesh.h" @@ -56,21 +56,22 @@ struct BMBVHTree { float curw, curd; float co[3], (*cagecos)[3], (*cos)[3]; int curtag, flag; - - Object *ob; +}; + +struct CageUserData { + int totvert; + float (*cagecos)[3]; + BLI_bitmap vert_bitmap; }; static void cage_mapped_verts_callback(void *userData, int index, const float co[3], const float UNUSED(no_f[3]), const short UNUSED(no_s[3])) { - void **data = userData; - BMEditMesh *em = data[0]; - float (*cagecos)[3] = data[1]; - SmallHash *hash = data[2]; - - if (index >= 0 && index < em->bm->totvert && !BLI_smallhash_haskey(hash, index)) { - BLI_smallhash_insert(hash, index, NULL); - copy_v3_v3(cagecos[index], co); + struct CageUserData *data = userData; + + if ((index >= 0 && index < data->totvert) && (!BLI_BITMAP_GET(data->vert_bitmap, index))) { + BLI_BITMAP_SET(data->vert_bitmap, index); + copy_v3_v3(data->cagecos[index], co); } } @@ -79,7 +80,6 @@ BMBVHTree *BKE_bmbvh_new(BMEditMesh *em, int flag, struct Scene *scene) struct BMLoop *(*looptris)[3] = em->looptris; BMBVHTree *tree = MEM_callocN(sizeof(*tree), "BMBVHTree"); DerivedMesh *cage, *final; - SmallHash shash; float cos[3][3], (*cagecos)[3] = NULL; int i; int tottri; @@ -87,11 +87,9 @@ BMBVHTree *BKE_bmbvh_new(BMEditMesh *em, int flag, struct Scene *scene) /* BKE_editmesh_tessface_calc() must be called already */ BLI_assert(em->tottri != 0 || em->bm->totface == 0); - /* when initializing cage verts, we only want the first cage coordinate for each vertex, - * so that e.g. mirror or array use original vertex coordinates and not mirrored or duplicate */ - BLI_smallhash_init(&shash); + /* cage-flag needs scene */ + BLI_assert(scene || !(flag & BMBVH_USE_CAGE)); - tree->ob = em->ob; tree->em = em; tree->bm = em->bm; tree->epsilon = FLT_EPSILON * 2.0f; @@ -120,11 +118,12 @@ BMBVHTree *BKE_bmbvh_new(BMEditMesh *em, int flag, struct Scene *scene) tree->tree = BLI_bvhtree_new(tottri, tree->epsilon, 8, 8); if (flag & BMBVH_USE_CAGE) { + BLI_bitmap vert_bitmap; BMIter iter; BMVert *v; - void *data[3]; - - tree->cos = MEM_callocN(sizeof(float) * 3 * em->bm->totvert, "bmbvh cos"); + struct CageUserData data; + + tree->cos = MEM_callocN(sizeof(*tree->cos) * em->bm->totvert, "bmbvh cos"); BM_ITER_MESH_INDEX (v, &iter, em->bm, BM_VERTS_OF_MESH, i) { BM_elem_index_set(v, i); /* set_inline */ copy_v3_v3(tree->cos[i], v->co); @@ -135,11 +134,17 @@ BMBVHTree *BKE_bmbvh_new(BMEditMesh *em, int flag, struct Scene *scene) cage = editbmesh_get_derived_cage_and_final(scene, em->ob, em, &final, CD_MASK_DERIVEDMESH); cagecos = MEM_callocN(sizeof(float) * 3 * em->bm->totvert, "bmbvh cagecos"); - data[0] = em; - data[1] = cagecos; - data[2] = &shash; + /* when initializing cage verts, we only want the first cage coordinate for each vertex, + * so that e.g. mirror or array use original vertex coordinates and not mirrored or duplicate */ + vert_bitmap = BLI_BITMAP_NEW(em->bm->totvert, __func__); + + data.totvert = em->bm->totvert; + data.cagecos = cagecos; + data.vert_bitmap = vert_bitmap; - cage->foreachMappedVert(cage, cage_mapped_verts_callback, data); + cage->foreachMappedVert(cage, cage_mapped_verts_callback, &data); + + MEM_freeN(vert_bitmap); } tree->cagecos = cagecos; @@ -175,7 +180,6 @@ BMBVHTree *BKE_bmbvh_new(BMEditMesh *em, int flag, struct Scene *scene) } BLI_bvhtree_balance(tree->tree); - BLI_smallhash_release(&shash); return tree; } |