diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-10-22 17:15:26 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2017-10-22 17:40:03 +0300 |
commit | 6dfe4cbc6b8717223c631e80af6c7552576966e1 (patch) | |
tree | 5fb0e2103cc6e8926370a5b1cee9a95fff4726a0 /source/blender/bmesh/intern | |
parent | 57a0cb797d60024357a3e3a64c1873844b0178bd (diff) |
Polyfill Beautify: half-edge optimization
Was using an edge hash for triangle -> edge lookups,
updating triangle indices for each edge-rotation.
Replace this with half-edge which can rotate edges much more simply,
writing triangles back once the solution has been calculated.
Gives ~33% speedup in own tests.
Diffstat (limited to 'source/blender/bmesh/intern')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 9 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.h | 3 |
2 files changed, 4 insertions, 8 deletions
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 977ae192c79..bf5fc18935d 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -925,7 +925,7 @@ void BM_face_triangulate( MemArena *pf_arena, /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */ - struct Heap *pf_heap, struct EdgeHash *pf_ehash) + struct Heap *pf_heap) { const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS); const bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY); @@ -1041,7 +1041,7 @@ void BM_face_triangulate( if (use_beauty) { BLI_polyfill_beautify( projverts, f->len, tris, - pf_arena, pf_heap, pf_ehash); + pf_arena, pf_heap); } BLI_memarena_clear(pf_arena); @@ -1497,7 +1497,6 @@ void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_ /* use_beauty */ Heap *pf_heap = NULL; - EdgeHash *pf_ehash = NULL; BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { /* don't consider two-edged faces */ @@ -1574,7 +1573,6 @@ void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_ if (UNLIKELY(pf_arena == NULL)) { pf_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE); - pf_ehash = BLI_edgehash_new_ex(__func__, BLI_POLYFILL_ALLOC_NGON_RESERVE); } tris = BLI_memarena_alloc(pf_arena, sizeof(*tris) * totfilltri); @@ -1593,7 +1591,7 @@ void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_ BLI_polyfill_calc_arena(projverts, efa->len, 1, tris, pf_arena); - BLI_polyfill_beautify(projverts, efa->len, tris, pf_arena, pf_heap, pf_ehash); + BLI_polyfill_beautify(projverts, efa->len, tris, pf_arena, pf_heap); for (j = 0; j < totfilltri; j++) { BMLoop **l_ptr = looptris[i++]; @@ -1612,7 +1610,6 @@ void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_ BLI_memarena_free(pf_arena); BLI_heap_free(pf_heap, NULL); - BLI_edgehash_free(pf_ehash, NULL); } *r_looptris_tot = i; diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index 313caac1243..4ec8ea59018 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -27,7 +27,6 @@ * \ingroup bmesh */ -struct EdgeHash; struct Heap; #include "BLI_compiler_attrs.h" @@ -83,7 +82,7 @@ void BM_face_triangulate( const int quad_method, const int ngon_method, const bool use_tag, struct MemArena *pf_arena, - struct Heap *pf_heap, struct EdgeHash *pf_ehash + struct Heap *pf_heap ) ATTR_NONNULL(1, 2); void BM_face_splits_check_legal(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len) ATTR_NONNULL(); |