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 | |
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')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 9 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.h | 3 | ||||
-rw-r--r-- | source/blender/bmesh/operators/bmo_connect_concave.c | 11 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_decimate_collapse.c | 12 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_triangulate.c | 15 |
5 files changed, 14 insertions, 36 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(); diff --git a/source/blender/bmesh/operators/bmo_connect_concave.c b/source/blender/bmesh/operators/bmo_connect_concave.c index 9bb67ed9341..80774323d31 100644 --- a/source/blender/bmesh/operators/bmo_connect_concave.c +++ b/source/blender/bmesh/operators/bmo_connect_concave.c @@ -41,7 +41,6 @@ #include "BLI_heap.h" #include "BLI_polyfill2d.h" #include "BLI_polyfill2d_beautify.h" -#include "BLI_edgehash.h" #include "BLI_linklist.h" #include "bmesh.h" @@ -77,7 +76,7 @@ static bool bm_face_split_by_concave( BMesh *bm, BMFace *f_base, const float eps, MemArena *pf_arena, - struct Heap *pf_heap, struct EdgeHash *pf_ehash) + struct Heap *pf_heap) { const int f_base_len = f_base->len; int faces_array_tot = f_base_len - 3; @@ -99,7 +98,7 @@ static bool bm_face_split_by_concave( &faces_double, quad_method, ngon_method, false, pf_arena, - pf_heap, pf_ehash); + pf_heap); BLI_assert(edges_array_tot <= f_base_len - 3); @@ -161,7 +160,6 @@ static bool bm_face_split_by_concave( } BLI_heap_clear(pf_heap, NULL); - BLI_edgehash_clear_ex(pf_ehash, NULL, BLI_POLYFILL_ALLOC_NGON_RESERVE); while (faces_double) { LinkNode *next = faces_double->next; @@ -201,17 +199,15 @@ void bmo_connect_verts_concave_exec(BMesh *bm, BMOperator *op) MemArena *pf_arena; Heap *pf_heap; - EdgeHash *pf_ehash; pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__); pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE); - pf_ehash = BLI_edgehash_new_ex(__func__, BLI_POLYFILL_ALLOC_NGON_RESERVE); BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) { if (f->len > 3 && bm_face_convex_tag_verts(f)) { if (bm_face_split_by_concave( bm, f, FLT_EPSILON, - pf_arena, pf_heap, pf_ehash)) + pf_arena, pf_heap)) { changed = true; } @@ -225,5 +221,4 @@ void bmo_connect_verts_concave_exec(BMesh *bm, BMOperator *op) BLI_memarena_free(pf_arena); BLI_heap_free(pf_heap, NULL); - BLI_edgehash_free(pf_ehash, NULL); } diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c b/source/blender/bmesh/tools/bmesh_decimate_collapse.c index 36ae7231f94..d734d9b6ae1 100644 --- a/source/blender/bmesh/tools/bmesh_decimate_collapse.c +++ b/source/blender/bmesh/tools/bmesh_decimate_collapse.c @@ -497,7 +497,7 @@ static bool 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 f_base_len = f_base->len; int faces_array_tot = f_base_len - 3; @@ -516,8 +516,7 @@ static bool bm_face_triangulate( edges_array, &edges_array_tot, r_faces_double, quad_method, ngon_method, false, - pf_arena, - pf_heap, pf_ehash); + pf_arena, pf_heap); for (int i = 0; i < edges_array_tot; i++) { BMLoop *l_iter, *l_first; @@ -567,19 +566,16 @@ static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot) { MemArena *pf_arena; Heap *pf_heap; - EdgeHash *pf_ehash; LinkNode *faces_double = NULL; if (has_ngon) { pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__); pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE); - pf_ehash = BLI_edgehash_new_ex(__func__, BLI_POLYFILL_ALLOC_NGON_RESERVE); } else { pf_arena = NULL; pf_heap = NULL; - pf_ehash = NULL; } /* adding new faces as we loop over faces @@ -591,8 +587,7 @@ static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot) bm, f, &faces_double, r_edges_tri_tot, - pf_arena, - pf_heap, pf_ehash); + pf_arena, pf_heap); } } @@ -606,7 +601,6 @@ static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot) if (has_ngon) { BLI_memarena_free(pf_arena); BLI_heap_free(pf_heap, NULL); - BLI_edgehash_free(pf_ehash, NULL); } BLI_assert((bm->elem_index_dirty & BM_VERT) == 0); diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c index ce1bc46d5e8..bd201fa89bf 100644 --- a/source/blender/bmesh/tools/bmesh_triangulate.c +++ b/source/blender/bmesh/tools/bmesh_triangulate.c @@ -35,7 +35,6 @@ #include "BLI_alloca.h" #include "BLI_memarena.h" #include "BLI_heap.h" -#include "BLI_edgehash.h" #include "BLI_linklist.h" /* only for defines */ @@ -57,7 +56,7 @@ static void bm_face_triangulate_mapping( MemArena *pf_arena, /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */ - struct Heap *pf_heap, struct EdgeHash *pf_ehash) + struct Heap *pf_heap) { int faces_array_tot = face->len - 3; BMFace **faces_array = BLI_array_alloca(faces_array, faces_array_tot); @@ -71,7 +70,7 @@ static void bm_face_triangulate_mapping( &faces_double, quad_method, ngon_method, use_tag, pf_arena, - pf_heap, pf_ehash); + pf_heap); if (faces_array_tot) { int i; @@ -98,17 +97,14 @@ void BM_mesh_triangulate( BMFace *face; MemArena *pf_arena; Heap *pf_heap; - EdgeHash *pf_ehash; pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__); if (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY) { pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE); - pf_ehash = BLI_edgehash_new_ex(__func__, BLI_POLYFILL_ALLOC_NGON_RESERVE); } else { pf_heap = NULL; - pf_ehash = NULL; } if (slot_facemap_out) { @@ -120,8 +116,7 @@ void BM_mesh_triangulate( bm, face, quad_method, ngon_method, tag_only, op, slot_facemap_out, slot_facemap_double_out, - pf_arena, - pf_heap, pf_ehash); + pf_arena, pf_heap); } } } @@ -138,8 +133,7 @@ void BM_mesh_triangulate( NULL, NULL, &faces_double, quad_method, ngon_method, tag_only, - pf_arena, - pf_heap, pf_ehash); + pf_arena, pf_heap); } } } @@ -156,6 +150,5 @@ void BM_mesh_triangulate( if (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY) { BLI_heap_free(pf_heap, NULL); - BLI_edgehash_free(pf_ehash, NULL); } } |