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.

2 files changed, 7 insertions, 20 deletions

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