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.

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);
 	}
 }