rewrite edgenet fill bmesh operator.

previous code created faces with mixed face-flipping and could get very slow,
test with ~60,000 edges here hung my system for over 2min (didnt wait for it to finish), new code executes in about 1 second.

new code doesn't attempt to flip faces correctly, its quite involved to do so, especially when the new faces are not created adjacent to eachother.
so simpler to calculate normals afterwards.

7 files changed, 563 insertions, 994 deletions

diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index 228ebcb96c4..533593d6f77 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -123,6 +123,8 @@ set(SRC
 	tools/bmesh_decimate_dissolve.c
 	tools/bmesh_decimate_unsubdivide.c
 	tools/bmesh_decimate.h
+	tools/bmesh_edgenet.c
+	tools/bmesh_edgenet.h
 	tools/bmesh_edgesplit.c
 	tools/bmesh_edgesplit.h
 	tools/bmesh_path.c
diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h
index d1d93bbfd1d..1f7c9ee97f6 100644
--- a/source/blender/bmesh/bmesh.h
+++ b/source/blender/bmesh/bmesh.h
@@ -271,6 +271,7 @@ extern "C" {
 
 #include "tools/bmesh_bevel.h"
 #include "tools/bmesh_decimate.h"
+#include "tools/bmesh_edgenet.h"
 #include "tools/bmesh_edgesplit.h"
 #include "tools/bmesh_path.h"
 #include "tools/bmesh_triangulate.h"
diff --git a/source/blender/bmesh/operators/bmo_create.c b/source/blender/bmesh/operators/bmo_create.c
index 64d0ec6ac27..11144d1186c 100644
--- a/source/blender/bmesh/operators/bmo_create.c
+++ b/source/blender/bmesh/operators/bmo_create.c
@@ -145,6 +145,7 @@ void bmo_contextual_create_exec(BMesh *bm, BMOperator *op)
 	/* EdgeNet Create */
 	if (tote != 0) {
 		/* call edgenet prepare op so additional face creation cases work */
+
 		BMOperator op_sub;
 		BMO_op_initf(bm, &op_sub, op->flag, "edgenet_prepare edges=%fe", ELE_NEW);
 		BMO_op_exec(bm, &op_sub);
diff --git a/source/blender/bmesh/operators/bmo_edgenet.c b/source/blender/bmesh/operators/bmo_edgenet.c
index 923b877b822..6c88161ca35 100644
--- a/source/blender/bmesh/operators/bmo_edgenet.c
+++ b/source/blender/bmesh/operators/bmo_edgenet.c
@@ -48,1017 +48,38 @@
 #define ELE_NEW		1
 #define ELE_ORIG	4
 
-#define FACE_IGNORE	16
-
-typedef struct EPathNode {
-	struct EPathNode *next, *prev;
-	BMVert *v;
-	BMEdge *e;
-	BMEdge *cure;
-} EPathNode;
-
-typedef struct EPath {
-	ListBase nodes;
-	float weight;
-	int group;
-} EPath;
-
-typedef struct PathBase {
-	BLI_mempool *nodepool, *pathpool;
-} PathBase;
-
-typedef struct EdgeData {
-	int tag;
-	int ftag;
-	BMDiskLink v1_disk_link, v2_disk_link;
-} EdgeData;
-
-typedef struct VertData {
-	BMEdge *e;
-	float no[3], offco[3], sco[3]; /* offco is vertex coordinate slightly offset randomly */
-	int tag;
-} VertData;
-
-static int count_edge_faces(BMesh *bm, BMEdge *e);
-
-/****  rotation system code * */
-
-BLI_INLINE BMDiskLink *rs_edge_link_get(BMEdge *e, BMVert *v, EdgeData *e_data)
-{
-	return v == ((BMEdge *)e)->v1 ? &(((EdgeData *)e_data)->v1_disk_link) :
-	                                &(((EdgeData *)e_data)->v2_disk_link);
-}
-
-static bool rotsys_append_edge(BMEdge *e, BMVert *v,
-                               EdgeData *edata, VertData *vdata)
-{
-	EdgeData *ed = &edata[BM_elem_index_get(e)];
-	VertData *vd = &vdata[BM_elem_index_get(v)];
-
-	if (!vd->e) {
-		Link *e1 = (Link *)rs_edge_link_get(e, v, ed);
-
-		vd->e = e;
-		e1->next = e1->prev = (Link *)e;
-	}
-	else {
-		BMDiskLink *dl1, *dl2, *dl3;
-		EdgeData *ved = &edata[BM_elem_index_get(vd->e)];
-
-		dl1 = rs_edge_link_get(e, v, ed);
-		dl2 = rs_edge_link_get(vd->e, v, ved);
-		dl3 = dl2->prev ? rs_edge_link_get(dl2->prev, v, &edata[BM_elem_index_get(dl2->prev)]) : NULL;
-
-		dl1->next = vd->e;
-		dl1->prev = dl2->prev;
-
-		dl2->prev = e;
-		if (dl3) {
-			dl3->next = e;
-		}
-	}
-
-	return true;
-}
-
-static void UNUSED_FUNCTION(rotsys_remove_edge)(BMEdge *e, BMVert *v,
-                                                EdgeData *edata, VertData *vdata)
-{
-	EdgeData *ed = edata + BM_elem_index_get(e);
-	VertData *vd = vdata + BM_elem_index_get(v);
-	BMDiskLink *e1, *e2;
-
-	e1 = rs_edge_link_get(e, v, ed);
-	if (e1->prev) {
-		e2 = rs_edge_link_get(e1->prev, v, ed);
-		e2->next = e1->next;
-	}
-
-	if (e1->next) {
-		e2 = rs_edge_link_get(e1->next, v, ed);
-		e2->prev = e1->prev;
-	}
-
-	if (vd->e == e)
-		vd->e = (e != e1->next) ? e1->next : NULL;
-
-	e1->next = e1->prev = NULL;
-}
-
-static BMEdge *rotsys_nextedge(BMEdge *e, BMVert *v,
-                               EdgeData *edata, VertData *UNUSED(vdata))
-{
-	if (v == e->v1)
-		return edata[BM_elem_index_get(e)].v1_disk_link.next;
-	if (v == e->v2)
-		return edata[BM_elem_index_get(e)].v2_disk_link.next;
-	return NULL;
-}
-
-static BMEdge *rotsys_prevedge(BMEdge *e, BMVert *v,
-                               EdgeData *edata, VertData *UNUSED(vdata))
-{
-	if (v == e->v1)
-		return edata[BM_elem_index_get(e)].v1_disk_link.prev;
-	if (v == e->v2)
-		return edata[BM_elem_index_get(e)].v2_disk_link.prev;
-	return NULL;
-}
-
-static void rotsys_reverse(BMEdge *UNUSED(e), BMVert *v, EdgeData *edata, VertData *vdata)
-{
-	BMEdge **edges = NULL;
-	BMEdge *e_first;
-	BMEdge *e;
-	BLI_array_staticdeclare(edges, BM_DEFAULT_NGON_STACK_SIZE);
-	int i, totedge;
-
-	e = e_first = vdata[BM_elem_index_get(v)].e;
-	do {
-		BLI_array_append(edges, e);
-		e = rotsys_nextedge(e, v, edata, vdata);
-	} while (e != e_first);
-
-	totedge = BLI_array_count(edges);
-	for (i = 0; i < totedge / 2; i++) {
-		SWAP(BMEdge *, edges[i], edges[totedge - 1 - i]);
-	}
-
-	vdata[BM_elem_index_get(v)].e = NULL;
-	for (i = 0; i < totedge; i++) {
-		rotsys_append_edge(edges[i], v, edata, vdata);
-	}
-
-	BLI_array_free(edges);
-}
-
-static int UNUSED_FUNCTION(rotsys_count)(BMVert *v, EdgeData *edata, VertData *vdata)
-{
-	BMEdge *e = vdata[BM_elem_index_get(v)].e;
-	int i = 0;
-
-	if (!e)
-		return 0;
-
-	do {
-		if (!e)
-			return 0;
-		e =  rotsys_nextedge(e, v, edata, vdata);
-
-		if (i >= (1 << 20)) {
-			printf("bmesh error: infinite loop in disk cycle!\n");
-			return 0;
-		}
-
-		i += 1;
-	} while (e != vdata[BM_elem_index_get(v)].e);
-
-	return i;
-}
-
-static int UNUSED_FUNCTION(rotsys_fill_faces)(BMesh *bm, EdgeData *edata, VertData *vdata)
-{
-	BMIter iter;
-	BMEdge *e, **edges = NULL;
-	BLI_array_declare(edges);
-	BMVert *v, **verts = NULL;
-	BMFace *f;
-	BLI_array_declare(verts);
-	SmallHash visithash, *hash = &visithash;
-	int i;
-
-	BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
-		BMEdge *e2, *starte;
-		BMVert *startv;
-		int rad, ok;
-
-		rad = count_edge_faces(bm, e);
-
-		if (rad < 2) {
-			starte = e;
-		}
-		else {
-			continue;
-		}
-
-		/* do two passes, going forward then backward */
-		for (i = 0; i < 2; i++) {
-			BLI_smallhash_init(hash);
-
-			BLI_array_empty(verts);
-			BLI_array_empty(edges);
-
-			startv = v = starte->v1;
-			e2 = starte;
-			ok = 1;
-			if (!v || !e2)
-				continue;
-
-			do {
-				if (BLI_smallhash_haskey(hash, (uintptr_t)e2) ||
-				    BLI_smallhash_haskey(hash, (uintptr_t)v))
-				{
-					ok = 0;
-					break;
-				}
-
-				BLI_array_append(verts, v);
-				BLI_array_append(edges, e2);
-
-				BLI_smallhash_insert(hash, (uintptr_t)e2, NULL);
-
-				v = BM_edge_other_vert(e2, v);
-				e2 = i ? rotsys_prevedge(e2, v, edata, vdata) : rotsys_nextedge(e2, v, edata, vdata);
-			} while (e2 != starte && v != startv);
-
-			BLI_smallhash_release(hash);
-
-			if (!ok || BLI_array_count(edges) < 3)
-				continue;
-
-			f = BM_face_create_ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), BM_CREATE_NO_DOUBLE);
-			if (UNLIKELY(f == NULL)) {
-				continue;
-			}
-		}
-	}
-
-	return 0;
-}
-
-static void rotsys_make_consistent(BMesh *bm, EdgeData *edata, VertData *vdata)
-{
-	BMIter iter;
-	BMEdge *e;
-	BMVert *v, **stack = NULL;
-	BLI_array_declare(stack);
-	int i;
-
-	for (i = 0; i < bm->totvert; i++) {
-		vdata[i].tag = 0;
-	}
-
-	while (1) {
-		VertData *vd;
-		BMVert *startv = NULL;
-		float dis;
-
-		BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
-			vd = vdata + BM_elem_index_get(v);
-
-			if (vd->tag)
-				continue;
-
-			if (!startv || dot_v3v3(vd->offco, vd->offco) > dis) {
-				dis = dot_v3v3(vd->offco, vd->offco);
-				startv = v;
-			}
-		}
-
-		if (!startv)
-			break;
-
-		vd = vdata + BM_elem_index_get(startv);
-
-		BLI_array_empty(stack);
-		BLI_array_append(stack, startv);
-
-		vd->tag = 1;
-
-		while (BLI_array_count(stack)) {
-			v = BLI_array_pop(stack);
-			vd = vdata + BM_elem_index_get(v);
-
-			if (!vd->e)
-				continue;
-
-			e = vd->e;
-			do {
-				BMVert *v2 = BM_edge_other_vert(e, v);
-				VertData *vd2 = vdata + BM_elem_index_get(v2);
-
-				if (dot_v3v3(vd->no, vd2->no) < 0.0f + FLT_EPSILON * 2) {
-					rotsys_reverse(e, v2, edata, vdata);
-					mul_v3_fl(vd2->no, -1.0f);
-				}
-
-				if (!vd2->tag) {
-					BLI_array_append(stack, v2);
-					vd2->tag = 1;
-				}
-
-				e = rotsys_nextedge(e, v, edata, vdata);
-			} while (e != vd->e);
-		}
-	}
-
-	BLI_array_free(stack);
-}
-
-static void init_rotsys(BMesh *bm, EdgeData *edata, VertData *vdata)
-{
-	BMIter iter;
-	BMEdge *e;
-	BMEdge **edges = NULL;
-	BLI_array_staticdeclare(edges, BM_DEFAULT_NGON_STACK_SIZE);
-	BMVert *v;
-	RNG *rng;
-	/* BMVert **verts = NULL; */
-	/* BLI_array_staticdeclare(verts, BM_DEFAULT_NGON_STACK_SIZE); */ /* UNUSE */
-	int i;
-
-	BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
-		BMIter eiter;
-		float no[3], cent[3];
-		int j, k = 0, totedge = 0;
-
-		if (BM_elem_index_get(v) == -1)
-			continue;
-
-		BLI_array_empty(edges);
-
-		BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
-			if (BMO_elem_flag_test(bm, e, EDGE_MARK)) {
-				BLI_array_append(edges, e);
-				totedge++;
-			}
-		}
-
-		copy_v3_v3(cent, v->co);
-
-		zero_v3(no);
-		for (i = 0; i < totedge; i++) {
-			BMEdge *e1, *e2;
-			float cno[3], vec1[3], vec2[3];
-
-			e1 = edges[i];
-			e2 = edges[(i + 1) % totedge];
-
-			sub_v3_v3v3(vec1, (BM_edge_other_vert(e1, v))->co, v->co);
-			sub_v3_v3v3(vec2, (BM_edge_other_vert(e2, v))->co, v->co);
-
-			cross_v3_v3v3(cno, vec1, vec2);
-			normalize_v3(cno);
-
-			if (i && dot_v3v3(cno, no) < 0.0f + FLT_EPSILON * 10)
-				mul_v3_fl(cno, -1.0f);
-
-			add_v3_v3(no, cno);
-			normalize_v3(no);
-		}
-
-		/* generate plane-flattened coordinates */
-		for (i = 0; i < totedge; i++) {
-			BMEdge *e1;
-			BMVert *v2;
-			float cvec[3], vec1[3];
-
-			e1 = edges[i];
-			v2 = BM_edge_other_vert(e1, v);
-
-			sub_v3_v3v3(vec1, v2->co, v->co);
-
-			cross_v3_v3v3(cvec, vec1, no);
-			cross_v3_v3v3(vec1, cvec, no);
-			normalize_v3(vec1);
-
-			mul_v3_fl(vec1, len_v3v3(v2->co, v->co));
-			add_v3_v3(vec1, v->co);
-
-			copy_v3_v3(vdata[BM_elem_index_get(v2)].sco, vec1);
-		}
-
-		rng = BLI_rng_new_srandom(0);
-
-		/* first, ensure no 0 or 180 angles between adjacent
-		 * (and that adjacent's adjacent) edges */
-		for (i = 0, k = 0; i < totedge; i++) {
-			BMEdge *e1, *e2, *e3 = NULL;
-			BMVert *v1, *v2, *v3;
-			VertData *vd1, *vd2, *vd3;
-			float vec1[3], vec2[3], vec3[3], size;
-			int s1, s2, s3;
-
-			if (totedge < 3)
-				continue;
-
-			e1 = edges[(i + totedge - 1) % totedge];
-			e2 = edges[i];
-			e3 = edges[(i + 1) % totedge];
-
-			v1 = BM_edge_other_vert(e1, v);
-			v2 = BM_edge_other_vert(e2, v);
-			v3 = BM_edge_other_vert(e3, v);
-
-			vd1 = vdata + BM_elem_index_get(v1);
-			vd2 = vdata + BM_elem_index_get(v2);
-			vd3 = vdata + BM_elem_index_get(v3);
-
-			sub_v3_v3v3(vec1, vd1->sco, cent);
-			sub_v3_v3v3(vec2, vd2->sco, cent);
-			sub_v3_v3v3(vec3, vd3->sco, cent);
-
-			size = (len_v3(vec1) + len_v3(vec3)) * 0.01f;
-			normalize_v3(vec1); normalize_v3(vec2); normalize_v3(vec3);
-
-#ifdef STRAIGHT
-#undef STRAIGHT
-#endif
-#define STRAIGHT(vec11, vec22) (fabsf(dot_v3v3((vec11), (vec22))) > 1.0f - ((float)FLT_EPSILON * 1000.0f))
-
-			s1 = STRAIGHT(vec1, vec2); s2 = STRAIGHT(vec2, vec3); s3 = STRAIGHT(vec1, vec3);
-
-			if (s1 || s2 || s3) {
-				copy_v3_v3(cent, v->co);
-
-				for (j = 0; j < 3; j++) {
-					float fac = (BLI_rng_get_float(rng) - 0.5f) * size;
-					cent[j] += fac;
-				}
-
-				if (k < 2000) {
-					i = 0;
-					k++;
-					continue;
-				}
-				else {
-					k++;
-					continue;
-				}
-
-			}
-		}
-
-		BLI_rng_free(rng);
-
-		copy_v3_v3(vdata[BM_elem_index_get(v)].offco, cent);
-		//copy_v3_v3(v->co, cent);
-
-		/* now, sort edges so the triangle fan of all edges
-		 * has a consistent normal.  this is the same as
-		 * sorting by polar coordinates along a group normal */
-		for (j = 0; j < totedge; j++) {
-			for (i = 0; i < totedge; i++) {
-				BMEdge *e1, *e2, *e3 = NULL;
-				BMVert *v1, *v2, *v3;
-				VertData *vd1, *vd2, *vd3;
-				float vec1[3], vec2[3], vec3[3], n1[3], n2[3], n3[3];
-
-				e1 = edges[(i + totedge - 1) % totedge];
-				e2 = edges[i];
-				e3 = edges[(i + 1) % totedge];
-
-				v1 = BM_edge_other_vert(e1, v);
-				v2 = BM_edge_other_vert(e2, v);
-				v3 = BM_edge_other_vert(e3, v);
-
-				vd1 = vdata + BM_elem_index_get(v1);
-				vd2 = vdata + BM_elem_index_get(v2);
-				vd3 = vdata + BM_elem_index_get(v3);
-
-				sub_v3_v3v3(vec1, vd1->sco, cent);
-				sub_v3_v3v3(vec2, vd2->sco, cent);
-				sub_v3_v3v3(vec3, vd3->sco, cent);
-
-				cross_v3_v3v3(n1, vec1, vec2);
-				cross_v3_v3v3(n2, vec2, vec3);
-				cross_v3_v3v3(n3, vec1, vec3);
-
-				/* this case happens often enough and probably not worth bothering users with,
-				 * maybe enable for debugging code but not for everyday use - campbell */
-#if 0
-				/* Other way to determine if two vectors approach are (nearly) parallel: the
-				 * cross product of the two vectors will approach zero */
-				{
-					int s1, s2, s3;
-					s1 = (dot_v3v3(n1, n1) < (0.0f + FLT_EPSILON * 10));
-					s2 = (dot_v3v3(n2, n2) < (0.0f + FLT_EPSILON * 10));
-					s3 = (totedge < 3) ? 0 : (dot_v3v3(n3, n3) < (0.0f + FLT_EPSILON * 10));
-
-					if (s1 || s2 || s3) {
-						fprintf(stderr, "%s: s1: %d, s2: %d, s3: %dx (bmesh internal error)\n", __func__, s1, s2, s3);
-					}
-				}
-#endif
-
-				normalize_v3(n1); normalize_v3(n2); normalize_v3(n3);
-
-
-				if (dot_v3v3(n1, n2) < 0.0f) {
-					if (dot_v3v3(n1, n3) >= 0.0f + FLT_EPSILON * 10) {
-						SWAP(BMEdge *, edges[i], edges[(i + 1) % totedge]);
-					}
-					else {
-						SWAP(BMEdge *, edges[(i + totedge - 1) % totedge], edges[(i + 1) % totedge]);
-						SWAP(BMEdge *, edges[i], edges[(i + 1) % totedge]);
-					}
-				}
-			}
-		}
-
-#undef STRAIGHT
-
-		zero_v3(no);
-
-		/* yay, edges are sorted */
-		for (i = 0; i < totedge; i++) {
-			BMEdge *e1 = edges[i], *e2 = edges[(i + 1) % totedge];
-			float eno[3];
-
-			normal_tri_v3(eno, BM_edge_other_vert(e1, v)->co, v->co, BM_edge_other_vert(e2, v)->co);
-			add_v3_v3(no, eno);
-
-			rotsys_append_edge(edges[i], v, edata, vdata);
-		}
-
-		normalize_v3(no);
-		copy_v3_v3(vdata[BM_elem_index_get(v)].no, no);
-	}
-
-	/* now, make sure rotation system is topologically consistent
-	 * (e.g. vert normals consistently point either inside or outside) */
-	rotsys_make_consistent(bm, edata, vdata);
-
-	//rotsys_fill_faces(bm, edata, vdata);
-
-#if 0
-	/* create visualizing geometry */
-	BMVert *lastv;
-	BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
-		BMVert *v2;
-		BMFace *f;
-		int totedge = BM_vert_edge_count(v);
-
-		if (BM_elem_index_get(v) == -1)
-			continue;
-
-		//cv = BM_vert_create(bm, cent, v);
-		//BM_elem_index_set(cv, -1);  /* set_dirty! */
-		i = 0;
-		e = vdata[BM_elem_index_get(v)].e;
-		lastv = NULL;
-		do {
-			BMEdge *e2;
-			BMVert *v2;
-			float f = ((float)i / (float)totedge) * 0.35 + 0.05;
-			float co[3];
-
-			if (!e)
-				break;
-
-			if (!BM_edge_other_vert(e, v))
-				continue;
-
-			sub_v3_v3v3(co, (BM_edge_other_vert(e, v))->co, vdata[BM_elem_index_get(v)].offco);
-			mul_v3_fl(co, f);
-			add_v3_v3(co, vdata[BM_elem_index_get(v)].offco);
-
-			v2 = BM_vert_create(bm, co, NULL);
-			BM_elem_index_set(v2, -1); /* set_dirty! */
-			//BM_edge_create(bm, cv, v2, NULL, 0);
-
-			BM_vert_select_set(bm, v2, true);
-			if (lastv) {
-				e2 = BM_edge_create(bm, lastv, v2, NULL, 0);
-				BM_edge_select_set(bm, e2, true);
-			}
-
-			lastv = v2;
-
-			e = rotsys_nextedge(e, v, edata, vdata);
-			i++;
-		} while (e != vdata[BM_elem_index_get(v)].e);
-	}
-#endif
-
-	BLI_array_free(edges);
-}
-
-static PathBase *edge_pathbase_new(void)
-{
-	PathBase *pb = MEM_callocN(sizeof(PathBase), "PathBase");
-
-	pb->nodepool = BLI_mempool_create(sizeof(EPathNode), 1, 512, BLI_MEMPOOL_SYSMALLOC);
-	pb->pathpool = BLI_mempool_create(sizeof(EPath), 1, 512, BLI_MEMPOOL_SYSMALLOC);
-
-	return pb;
-}
-
-static void edge_pathbase_free(PathBase *pathbase)
-{
-	BLI_mempool_destroy(pathbase->nodepool);
-	BLI_mempool_destroy(pathbase->pathpool);
-	MEM_freeN(pathbase);
-}
-
-static EPath *edge_copy_add_path(PathBase *pb, EPath *path, BMVert *appendv, BMEdge *e)
-{
-	EPath *path2;
-	EPathNode *node, *node2;
-
-	path2 = BLI_mempool_alloc(pb->pathpool);
-	path2->nodes.first = path2->nodes.last = NULL;
-	path2->weight = 0.0f;
-	path2->group = path->group;
-
-	for (node = path->nodes.first; node; node = node->next) {
-		node2 = BLI_mempool_alloc(pb->nodepool);
-		*node2 = *node;
-		BLI_addtail(&path2->nodes, node2);
-	}
-
-	node2 = BLI_mempool_alloc(pb->nodepool);
-	node2->v = appendv;
-	node2->e = e;
-	node2->cure = NULL;
-
-	BLI_addtail(&path2->nodes, node2);
-
-	return path2;
-}
-
-static EPath *edge_path_new(PathBase *pb, BMVert *start, BMEdge *starte)
-{
-	EPath *path;
-	EPathNode *node;
-
-	path = BLI_mempool_alloc(pb->pathpool);
-	node = BLI_mempool_alloc(pb->nodepool);
-
-	path->nodes.first = path->nodes.last = NULL;
-
-	node->v = start;
-	node->e = starte;
-	node->cure = NULL;
-
-	BLI_addtail(&path->nodes, node);
-	path->weight = 0.0f;
-
-	return path;
-}
-
-static float edge_weight_path(EPath *path, EdgeData *edata, VertData *UNUSED(vdata))
-{
-	EPathNode *node, *first = path->nodes.first;
-	float w = 0.0;
-
-	for (node = path->nodes.first; node; node = node->next) {
-		if (node->e && node != path->nodes.first) {
-			w += edata[BM_elem_index_get(node->e)].ftag;
-			if (node->prev) {
-				/* BMESH_TOD */
-				(void)first;
-				//w += len_v3v3(node->v->co, first->e->v1->co) * 0.0001f;
-				//w += len_v3v3(node->v->co, first->e->v2->co) * 0.0001f;
-			}
-		}
-
-		w += 1.0f;
-	}
-
-	return w;
-}
-
-
-static void edge_free_path(PathBase *pathbase, EPath *path)
-{
-	EPathNode *node, *next;
-
-	for (node = path->nodes.first; node; node = next) {
-		next = node->next;
-		BLI_mempool_free(pathbase->nodepool, node);
-	}
-
-	BLI_mempool_free(pathbase->pathpool, path);
-}
-
-static EPath *edge_find_shortest_path(BMesh *bm, BMOperator *op, BMEdge *edge, EdgeData *edata,
-                                      VertData *vdata, PathBase *pathbase, int group)
-{
-	BMEdge *e;
-	GHash *gh = BLI_ghash_ptr_new("createops find shortest path");
-	BMVert *v1, *v2;
-	BMVert **verts = NULL;
-	BLI_array_staticdeclare(verts, 1024);
-	Heap *heap = BLI_heap_new();
-	EPath *path = NULL, *path2;
-	BMVert *startv;
-	BMVert *endv;
-	EPathNode *node;
-	int i;
-	const bool use_restrict = BMO_slot_bool_get(op->slots_in, "use_restrict");
-	BMOpSlot *slot_restrict = BMO_slot_get(op->slots_in, "restrict");
-
-
-	startv = edata[BM_elem_index_get(edge)].ftag ? edge->v2 : edge->v1;
-	endv = edata[BM_elem_index_get(edge)].ftag ? edge->v1 : edge->v2;
-
-	path = edge_path_new(pathbase, startv, edge);
-	BLI_ghash_insert(gh, startv, NULL);
-	BLI_heap_insert(heap, path->weight, path);
-	path->group = group;
-
-	while (BLI_heap_size(heap)) {
-		VertData *vd;
-		EPathNode *last;
-		BMFace *f = NULL;
-
-		path = BLI_heap_popmin(heap);
-		last = path->nodes.last;
-		v1 = last->v;
-
-		if (v1 == endv) {
-			/* make sure this path loop doesn't already exists */
-			i = 0;
-			BLI_array_empty(verts);
-			for (i = 0, node = path->nodes.first; node; node = node->next, i++) {
-				BLI_array_grow_one(verts);
-				verts[i] = node->v;
-			}
-
-			if (BM_face_exists(verts, i, &f)) {
-				if (!BMO_elem_flag_test(bm, f, FACE_IGNORE)) {
-					BLI_ghash_remove(gh, endv, NULL, NULL);
-					continue;
-				}
-			}
-			break;
-		}
-
-		vd = vdata + BM_elem_index_get(v1);
-		if (!vd->e)
-			continue;
-
-		v2 = NULL;
-		while (1) {
-			if (!last->cure) {
-				last->cure = e = vdata[BM_elem_index_get(last->v)].e;
-			}
-			else {
-				last->cure = e = rotsys_nextedge(last->cure, last->v, edata, vdata);
-				if (last->cure == vdata[BM_elem_index_get(last->v)].e) {
-					v2 = NULL;
-					break;
-				}
-			}
-
-			if (e == edge || !BMO_elem_flag_test(bm, e, EDGE_MARK)) {
-				continue;
-			}
-
-			v2 = BM_edge_other_vert(e, last->v);
-
-			if (BLI_ghash_haskey(gh, v2)) {
-				v2 = NULL;
-				continue;
-			}
-
-			if (use_restrict) {
-				int *group_flag = (int *)BMO_slot_map_data_get(slot_restrict, e);
-				if (group_flag) {
-					if (!(*group_flag & path->group)) {
-						v2 = NULL;
-						continue;
-					}
-				}
-			}
-
-			break;
-		}
-
-		if (!v2) {
-			edge_free_path(pathbase, path);
-			path = NULL;
-			continue;
-		}
-
-		/* add path back into heap */
-		BLI_heap_insert(heap, path->weight, path);
-
-		/* put v2 in gh ma */
-		BLI_ghash_insert(gh, v2, NULL);
-
-		path2 = edge_copy_add_path(pathbase, path, v2, e);
-		path2->weight = edge_weight_path(path2, edata, vdata);
-
-		BLI_heap_insert(heap, path2->weight, path2);
-	}
-
-	if (path && ((EPathNode *)path->nodes.last)->v != endv) {
-		edge_free_path(pathbase, path);
-		path = NULL;
-	}
-
-	BLI_array_free(verts);
-	BLI_heap_free(heap, NULL);
-	BLI_ghash_free(gh, NULL, NULL);
-
-	return path;
-}
-
-static int count_edge_faces(BMesh *bm, BMEdge *e)
-{
-	int i = 0;
-	BMLoop *l = e->l;
-
-	if (!l) {
-		return 0;
-	}
-
-	do {
-		if (!BMO_elem_flag_test(bm, l->f, FACE_IGNORE)) {
-			i++;
-		}
-
-		l = l->radial_next;
-	} while (l != e->l);
-
-	return i;
-}
-
-BLI_INLINE void vote_on_winding(BMEdge *edge, EPathNode *node, unsigned int winding[2])
-{
-	BMVert *test_v1, *test_v2;
-	/* we want to use the reverse winding to the existing order */
-	BM_edge_ordered_verts(edge, &test_v2, &test_v1);
-
-	/* edges vote on which winding wins out */
-	winding[(test_v1 == node->v)]++;
-}
-
-static BMFace *bm_face_from_path(BMesh *bm, EPath *path,
-                                 EdgeData *edata,
-                                 const bool use_fill_check)
-{
-	/* accumulte winding directions for each edge which has a face */
-	const unsigned int path_len = BLI_countlist(&path->nodes);
-	unsigned int winding[2] = {0, 0};
-	unsigned int i;
-
-	EPathNode *node;
-
-	BMVert **verts = BLI_array_alloca(verts, path_len);
-	BMEdge **edges = BLI_array_alloca(edges, path_len);
-	BMEdge *e;
-	BMVert *v;
-
-	for (node = path->nodes.first, i = 0; node; node = node->next, i++) {
-
-		v = node->v;
-		e = BM_edge_exists(v, node->next ?
-		                      node->next->v :
-		                      ((EPathNode *)path->nodes.first)->v);
-
-		/* check on the winding */
-		if (e->l) {
-			if (UNLIKELY(count_edge_faces(bm, e) >= 2)) {
-				return NULL;
-			}
-
-			vote_on_winding(e, node, winding);
-		}
-
-		verts[i] = v;
-		edges[i] = e;
-	}
-
-	/* do after incase we bail early, above */
-	for (i = 0; i < path_len; i++) {
-		edata[BM_elem_index_get(edges[i])].ftag++;
-	}
-
-
-	/* if these are even it doesn't really matter what to do,
-	 * with consistent geometry one will be zero, the choice is clear */
-	if (winding[0] > winding[1]) {
-		BLI_array_wrap(verts, path_len, -1);
-		BLI_array_reverse(verts, path_len);
-		BLI_array_reverse(edges, path_len);
-	}
-
-	if ((use_fill_check == false) ||
-	    /* fairly expensive check - see if there are already faces filling this area */
-	    (BM_face_exists_multi(verts, edges, path_len) == false))
-	{
-		return BM_face_create(bm, verts, edges, path_len, BM_CREATE_NO_DOUBLE);
-	}
-	else {
-		return NULL;
-	}
-}
-
 void bmo_edgenet_fill_exec(BMesh *bm, BMOperator *op)
 {
-	BMIter iter;
 	BMOIter siter;
 	BMFace *f;
-	BMEdge *e;
-	EPath *path;
-	EdgeData *edata;
-	VertData *vdata;
-	PathBase *pathbase;
-	const bool use_restrict   = BMO_slot_bool_get(op->slots_in, "use_restrict");
-	const bool use_fill_check = BMO_slot_bool_get(op->slots_in, "use_fill_check");
 	const short mat_nr        = BMO_slot_int_get(op->slots_in,  "mat_nr");
 	const bool use_smooth     = BMO_slot_bool_get(op->slots_in, "use_smooth");
-	int i;
-	BMOpSlot *slot_restrict          = BMO_slot_get(op->slots_in, "restrict");
-	BMOpSlot *slot_face_groupmap_out = BMO_slot_get(op->slots_out, "face_groupmap.out");
 
 	if (!bm->totvert || !bm->totedge)
 		return;
 
-	pathbase = edge_pathbase_new();
-
-	edata = MEM_callocN(sizeof(EdgeData) * bm->totedge, "EdgeData");
-	vdata = MEM_callocN(sizeof(VertData) * bm->totvert, "VertData");
+	BMO_slot_buffer_hflag_enable(bm, op->slots_in, "edges", BM_EDGE, BM_ELEM_TAG, false);
 
-	BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
-	BMO_slot_buffer_flag_enable(bm, op->slots_in, "exclude_faces", BM_FACE, FACE_IGNORE);
-
-	BM_mesh_elem_index_ensure(bm, BM_VERT);
-
-	BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
-		BMO_elem_flag_enable(bm, f, ELE_ORIG);
-	}
+	BM_mesh_edgenet(bm, true, FACE_NEW);
 
-	BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
-		BM_elem_index_set(e, i); /* set_inline */
+	BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_NEW);
 
-		if (!BMO_elem_flag_test(bm, e, EDGE_MARK)) {
-			edata[i].tag = 2;
+	BMO_ITER (f, &siter, op->slots_out, "faces.out", BM_FACE) {
+		f->mat_nr = mat_nr;
+		if (use_smooth) {
+			BM_elem_flag_enable(f, BM_ELEM_SMOOTH);
 		}
+		/* normals are zero'd */
+		BM_face_normal_update(f);
 	}
-	bm->elem_index_dirty &= ~BM_EDGE;
-
-	init_rotsys(bm, edata, vdata);
-
-	while (1) {
-		BMEdge *edge = NULL;
-		int group = 0;
-
-		BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
-			/* if restrict is on, only start on faces in the restrict map */
-			if (use_restrict && !BMO_slot_map_contains(slot_restrict, e))
-				continue;
-
-			if (edata[BM_elem_index_get(e)].tag < 2) {
-				edge = e;
-
-				if (use_restrict) {
-					int gi_iter = 0, gi_count = 0, gi = 0;
 
-					group = BMO_slot_map_int_get(slot_restrict, e);
-
-					for (gi_iter = 0; gi_iter < 30; gi_iter++) {
-						if (group & (1 << gi_iter)) {
-							gi_count++;
-							gi = gi_iter;
-
-							if (gi_count - 1 == edata[BM_elem_index_get(e)].tag) {
-								break;
-							}
-						}
-					}
-
-					group = (1 << gi);
-				}
-
-				break;
-			}
-		}
-
-		if (!edge)
-			break;
-
-		edata[BM_elem_index_get(edge)].tag += 1;
-
-		path = edge_find_shortest_path(bm, op, edge, edata, vdata, pathbase, group);
-		if (path && path->nodes.first) {
-			BMFace *f = bm_face_from_path(bm, path, edata,
-			                              use_fill_check);
-
-			if (f && !BMO_elem_flag_test(bm, f, ELE_ORIG)) {
-				BMO_elem_flag_enable(bm, f, FACE_NEW);
-				f->mat_nr = mat_nr;
-				if (use_smooth) {
-					BM_elem_flag_enable(f, BM_ELEM_SMOOTH);
-				}
-			}
-
-			if (use_restrict) {
-				BMO_slot_map_int_insert(op, slot_face_groupmap_out, f, path->group);
-			}
-
-			edge_free_path(pathbase, path);
-		}
+	/* recalc normals,
+	 * TODO, could do checks to make normals consistent */
+	{
+		BMO_op_callf(bm, op->flag,
+		             "recalc_face_normals faces=%S",
+		             op, "faces.out");
 	}
-
-	BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_NEW);
-
-	edge_pathbase_free(pathbase);
-	MEM_freeN(edata);
-	MEM_freeN(vdata);
 }
 
 static BMEdge *edge_next(BMesh *bm, BMEdge *e)
diff --git a/source/blender/bmesh/operators/bmo_normals.c b/source/blender/bmesh/operators/bmo_normals.c
index 025b8557331..b645766178d 100644
--- a/source/blender/bmesh/operators/bmo_normals.c
+++ b/source/blender/bmesh/operators/bmo_normals.c
@@ -77,6 +77,7 @@ static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int f
 		madd_v3_v3fl(cent, f_cent, cent_fac);
 
 		BLI_assert(BMO_elem_flag_test(bm, faces[i], FACE_TEMP) == 0);
+		BLI_assert(BM_face_is_normal_valid(faces[i]));
 	}
 
 	f_len_best = -FLT_MAX;
diff --git a/source/blender/bmesh/tools/bmesh_edgenet.c b/source/blender/bmesh/tools/bmesh_edgenet.c
new file mode 100644
index 00000000000..ed5d47e9391
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_edgenet.c
@@ -0,0 +1,511 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Campbell Barton
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/tools/bmesh_edgenet.c
+ *  \ingroup bmesh
+ *
+ * Edgenet Fill.
+ *
+ */
+
+#include <limits.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_alloca.h"
+#include "BLI_mempool.h"
+#include "BLI_linklist.h"
+
+#include "bmesh.h"
+
+#ifdef __GNUC__
+#  pragma GCC diagnostic error "-Wsign-conversion"
+#  if (__GNUC__ * 100 + __GNUC_MINOR__) >= 406  /* gcc4.6+ only */
+#    pragma GCC diagnostic error "-Wsign-compare"
+#    pragma GCC diagnostic error "-Wconversion"
+#  endif
+#endif
+
+/* Data for one end of an edge involved in a bevel */
+typedef struct VertNetInfo {
+	BMVert *prev;               /* previous vertex */
+	int pass;                   /* path scanning pass value, for internal calculation */
+	int face;                   /* face index connected to the edge between this and the previous vert */
+	int flag;                   /* flag */
+} VertNetInfo;
+
+enum {
+	VNINFO_FLAG_IS_MIXFACE = (1 << 0),
+};
+
+/**
+ * Check if this edge can be used in a path.
+ */
+static bool bm_edge_step_ok(BMEdge *e)
+{
+	return BM_elem_flag_test(e, BM_ELEM_TAG) && ((e->l == NULL) || (e->l->radial_next == e->l));
+}
+
+static int bm_edge_face(BMEdge *e)
+{
+	return e->l ? BM_elem_index_get(e->l->f) : -1;
+}
+
+/**
+ * Get the next available edge we can use to attempt tp calculate a path from.
+ */
+static BMEdge *bm_edgenet_edge_get_next(
+        BMesh *bm,
+        LinkNode **edge_queue, BLI_mempool *edge_queue_pool)
+{
+	BMEdge *e;
+	BMIter iter;
+
+	while (*edge_queue) {
+		e = BLI_linklist_pop_pool(edge_queue, edge_queue_pool);
+		if (bm_edge_step_ok(e)) {
+			return e;
+		}
+	}
+
+	BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+		if (bm_edge_step_ok(e)) {
+			return e;
+		}
+	}
+
+	return NULL;
+}
+
+
+/**
+ * Edge loops are built up using links to the 'prev' member.
+ * with each side of the loop having its own pass (negated from the other).
+ *
+ * This function returns half a loop, the caller needs to run twice to get both sides.
+ */
+static unsigned int bm_edgenet_path_from_pass(
+        BMVert *v, LinkNode **v_ls,
+        VertNetInfo *vnet_info, BLI_mempool *path_pool)
+{
+	VertNetInfo *vn = &vnet_info[BM_elem_index_get(v)];
+	const int pass = vn->pass;
+	unsigned int v_ls_tot = 0;
+
+	do {
+		BLI_linklist_prepend_pool(v_ls, v, path_pool);
+		v_ls_tot += 1;
+		v = vn->prev;
+		vn = &vnet_info[BM_elem_index_get(v)];
+	} while ((vn->pass == pass));
+
+	return v_ls_tot;
+}
+
+/**
+ * Specialized wrapper for #BM_face_exists_overlap_subset
+ * that gets the verts from a path before we allocate it in the correct order.
+ */
+static bool bm_edgenet_path_check_overlap(
+        BMVert *v1, BMVert *v2,
+        VertNetInfo *vnet_info)
+{
+	/* vert order doesn't matter */
+	unsigned int v_ls_tot = 0;
+	LinkNode *v_ls;
+	BMVert *v_pair[2] = {v1, v2};
+	unsigned int i;
+
+	for (i = 0; i < 2; i++) {
+		BMVert *v = v_pair[i];
+		VertNetInfo *vn = &vnet_info[BM_elem_index_get(v)];
+		const int pass = vn->pass;
+		do {
+			BLI_linklist_prepend_alloca(&v_ls, v);
+			v_ls_tot += 1;
+			v = vn->prev;
+			vn = &vnet_info[BM_elem_index_get(v)];
+		} while ((vn->pass == pass));
+	}
+
+	if (v_ls_tot) {
+		BMVert **vert_arr = BLI_array_alloca(vert_arr, v_ls_tot);
+		LinkNode *v_lnk;
+		for (i = 0, v_lnk = v_ls; i < v_ls_tot; v_lnk = v_lnk->next, i++) {
+			vert_arr[i] = v_lnk->link;
+		}
+
+		return BM_face_exists_overlap_subset(vert_arr, (int)v_ls_tot);
+	}
+	else {
+		return false;
+	}
+}
+
+/**
+ * Create a face from the path.
+ */
+static BMFace *bm_edgenet_face_from_path(
+        BMesh *bm, LinkNode *path, const unsigned int path_len)
+{
+	BMFace *f;
+	LinkNode *v_lnk;
+	unsigned int i;
+	unsigned int i_prev;
+
+	BMVert **vert_arr = BLI_array_alloca(vert_arr, path_len);
+	BMEdge **edge_arr = BLI_array_alloca(edge_arr, path_len);
+
+	for (v_lnk = path, i = 0; v_lnk; v_lnk = v_lnk->next, i++) {
+		vert_arr[i] = v_lnk->link;
+	}
+
+	i_prev = path_len - 1;
+	for (i = 0; i < path_len; i++) {
+		edge_arr[i_prev] = BM_edge_exists(vert_arr[i], vert_arr[i_prev]);
+		i_prev = i;
+	}
+
+	/* no need for this, we do overlap checks before allowing the path to be used */
+#if 0
+	if (BM_face_exists_multi(vert_arr, edge_arr, path_len)) {
+		return NULL;
+	}
+#endif
+
+	f = BM_face_create(bm, vert_arr, edge_arr, (int)path_len, 0);
+
+	return f;
+}
+
+/**
+ * Step along the path from \a v_curr to any vert not already in the path.
+ *
+ * \return The connecting edge if the path is found, otherwise NULL.
+ */
+static BMEdge *bm_edgenet_path_step(
+        BMVert *v_curr, LinkNode **v_ls,
+        VertNetInfo *vnet_info, BLI_mempool *path_pool)
+{
+	const VertNetInfo *vn_curr = &vnet_info[BM_elem_index_get(v_curr)];
+
+	BMEdge *e;
+	BMIter iter;
+	unsigned int tot = 0;
+	unsigned int v_ls_tot = 0;
+
+	BM_ITER_ELEM (e, &iter, v_curr, BM_EDGES_OF_VERT) {
+		BMVert *v_next = BM_edge_other_vert(e, v_curr);
+		if (v_next != vn_curr->prev) {
+			if (bm_edge_step_ok(e)) {
+				VertNetInfo *vn_next = &vnet_info[BM_elem_index_get(v_next)];
+
+				/* check we're not looping back on ourselves */
+				if (vn_curr->pass != vn_next->pass) {
+
+					if (vn_curr->pass == -vn_next->pass) {
+						if ((vn_curr->flag & VNINFO_FLAG_IS_MIXFACE) ||
+							(vn_next->flag & VNINFO_FLAG_IS_MIXFACE))
+						{
+							/* found connecting edge */
+							if (bm_edgenet_path_check_overlap(v_curr, v_next, vnet_info) == false) {
+								return e;
+							}
+						}
+					}
+					else {
+						vn_next->face = bm_edge_face(e);
+						vn_next->pass = vn_curr->pass;
+						vn_next->prev = v_curr;
+
+						/* flush flag down the path */
+						vn_next->flag &= ~VNINFO_FLAG_IS_MIXFACE;
+						if ((vn_curr->flag & VNINFO_FLAG_IS_MIXFACE) ||
+							(vn_next->face == -1) ||
+							(vn_next->face != vn_curr->face))
+						{
+							vn_next->flag |= VNINFO_FLAG_IS_MIXFACE;
+						}
+
+						/* add to the list! */
+						BLI_linklist_prepend_pool(v_ls, v_next, path_pool);
+						v_ls_tot += 1;
+					}
+				}
+			}
+			tot += 1;
+		}
+	}
+
+	/* trick to walk along wire-edge paths */
+	if (v_ls_tot == 1 && tot == 1) {
+		v_curr = BLI_linklist_pop_pool(v_ls, path_pool);
+		bm_edgenet_path_step(v_curr, v_ls, vnet_info, path_pool);
+	}
+
+	return NULL;
+}
+
+/**
+ * Given an edge, find the first path that can form a face.
+ *
+ * \return A linked list of verts.
+ */
+static LinkNode *bm_edgenet_path_calc(
+        BMEdge *e, const int pass_nr, const unsigned int path_cost_max,
+        unsigned int *r_path_len, unsigned int *r_path_cost,
+        VertNetInfo *vnet_info, BLI_mempool *path_pool)
+{
+	VertNetInfo *vn_1, *vn_2;
+	const int f_index = bm_edge_face(e);
+	bool found;
+
+	LinkNode *v_ls_prev = NULL;
+	LinkNode *v_ls_next = NULL;
+
+	unsigned int path_cost_accum = 0;
+
+	BLI_assert(bm_edge_step_ok(e));
+
+	*r_path_len = 0;
+	*r_path_cost = 0;
+
+	vn_1 = &vnet_info[BM_elem_index_get(e->v1)];
+	vn_2 = &vnet_info[BM_elem_index_get(e->v2)];
+
+	vn_1->pass =  pass_nr;
+	vn_2->pass = -pass_nr;
+
+	vn_1->prev = e->v2;
+	vn_2->prev = e->v1;
+
+	vn_1->face =
+	vn_2->face = f_index;
+
+	vn_1->flag =
+	vn_2->flag = (f_index == -1) ? VNINFO_FLAG_IS_MIXFACE : 0;
+
+	/* prime the searchlist */
+	BLI_linklist_prepend_pool(&v_ls_prev, e->v1, path_pool);
+	BLI_linklist_prepend_pool(&v_ls_prev, e->v2, path_pool);
+
+	do {
+		found = false;
+
+		/* no point to continue, we're over budget */
+		if (path_cost_accum >= path_cost_max) {
+			BLI_linklist_free_pool(v_ls_next, NULL, path_pool);
+			BLI_linklist_free_pool(v_ls_prev, NULL, path_pool);
+			return NULL;
+		}
+
+		while (v_ls_prev) {
+			const LinkNode *v_ls_next_old = v_ls_next;
+			BMVert *v = BLI_linklist_pop_pool(&v_ls_prev, path_pool);
+			BMEdge *e_found = bm_edgenet_path_step(v, &v_ls_next, vnet_info, path_pool);
+
+			if (e_found) {
+				LinkNode *path = NULL;
+				unsigned int path_len;
+				BLI_linklist_free_pool(v_ls_next, NULL, path_pool);
+				BLI_linklist_free_pool(v_ls_prev, NULL, path_pool);
+
+				// BLI_assert(BLI_mempool_count(path_pool) == 0);
+
+				path_len = bm_edgenet_path_from_pass(e_found->v1, &path, vnet_info, path_pool);
+				BLI_linklist_reverse(&path);
+				path_len += bm_edgenet_path_from_pass(e_found->v2, &path, vnet_info, path_pool);
+				*r_path_len = path_len;
+				*r_path_cost = path_cost_accum;
+				return path;
+			}
+			else {
+				/* check if a change was made */
+				if (v_ls_next_old != v_ls_next) {
+					found = true;
+				}
+			}
+
+		}
+		BLI_assert(v_ls_prev == NULL);
+
+		path_cost_accum++;
+
+		/* swap */
+		v_ls_prev = v_ls_next;
+		v_ls_next = NULL;
+
+	} while (found);
+
+	BLI_assert(v_ls_prev == NULL);
+	BLI_assert(v_ls_next == NULL);
+
+	/* tag not to search again */
+	BM_elem_flag_disable(e, BM_ELEM_TAG);
+
+	return NULL;
+}
+
+/**
+ * Wrapper for #bm_edgenet_path_calc which ensures all included edges
+ * _don't_ have a better option.
+ */
+static LinkNode *bm_edgenet_path_calc_best(
+        BMEdge *e, int *pass_nr, unsigned int path_cost_max,
+        unsigned int *r_path_len, unsigned int *r_path_cost,
+        VertNetInfo *vnet_info, BLI_mempool *path_pool)
+{
+	LinkNode *path;
+	unsigned int path_cost;
+
+	path = bm_edgenet_path_calc(e, *pass_nr, path_cost_max,
+	                            r_path_len, &path_cost,
+	                            vnet_info, path_pool);
+	(*pass_nr)++;
+
+	if (path == NULL) {
+		return NULL;
+	}
+	else if (path_cost <= 1) {
+		/* any face that takes 1-2 iterations to find we consider valid */
+		return path;
+	}
+	else {
+		/* Check every edge to see if any can give a better path.
+		 * This avoids very strange/long paths from being created. */
+
+		const unsigned int path_len = *r_path_len;
+		unsigned int i, i_prev;
+		BMVert **vert_arr = BLI_array_alloca(vert_arr, path_len);
+		LinkNode *v_lnk;
+
+		for (v_lnk = path, i = 0; v_lnk; v_lnk = v_lnk->next, i++) {
+			vert_arr[i] = v_lnk->link;
+		}
+
+		i_prev = path_len - 1;
+		for (i = 0; i < path_len; i++) {
+			BMEdge *e_other = BM_edge_exists(vert_arr[i], vert_arr[i_prev]);
+			if (e_other != e) {
+				LinkNode *path_test;
+				unsigned int path_len_test;
+				unsigned int path_cost_test;
+
+				path_test = bm_edgenet_path_calc(e_other, *pass_nr, path_cost,
+				                                 &path_len_test, &path_cost_test,
+				                                 vnet_info, path_pool);
+				(*pass_nr)++;
+
+				if (path_test) {
+					BLI_assert(path_cost_test < path_cost);
+
+					BLI_linklist_free_pool(path, NULL, path_pool);
+					path = path_test;
+					*r_path_len = path_len_test;
+					*r_path_cost = path_cost_test;
+					path_cost = path_cost_test;
+				}
+			}
+
+			i_prev = i;
+		}
+	}
+	return path;
+}
+
+/**
+ * Fill in faces from an edgenet made up of boundary and wire edges.
+ *
+ * \note New faces currently don't have their normals calculated and are flipped randomly.
+ *       The caller needs to flip faces correctly.
+ *
+ * \param bm  The mesh to operate on.
+ * \param use_edge_tag  Only fill tagged edges.
+ * \param face_oflag  if nonzero, apply all new faces with this bmo flag.
+ */
+void BM_mesh_edgenet(BMesh *bm, const bool use_edge_tag, const short face_oflag)
+{
+	VertNetInfo *vnet_info = MEM_callocN(sizeof(*vnet_info) * (size_t)bm->totvert, __func__);
+	BLI_mempool *edge_queue_pool = BLI_mempool_create(sizeof(LinkNode), 1, 512, 0);
+	BLI_mempool *path_pool = BLI_mempool_create(sizeof(LinkNode), 1, 512, 0);
+	LinkNode *edge_queue = NULL;
+
+	BMEdge *e;
+	BMIter iter;
+
+	int pass_nr = 1;
+
+	if (use_edge_tag == false) {
+		BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+			BM_elem_flag_enable(e, BM_ELEM_TAG);
+			BM_elem_flag_set(e, BM_ELEM_TAG, bm_edge_step_ok(e));
+		}
+	}
+
+	BM_mesh_elem_index_ensure(bm, BM_VERT | BM_FACE);
+
+	while (true) {
+		LinkNode *path = NULL;
+		unsigned int path_len;
+		unsigned int path_cost;
+
+		e = bm_edgenet_edge_get_next(bm, &edge_queue, edge_queue_pool);
+		if (e == NULL) {
+			break;
+		}
+
+		BLI_assert(bm_edge_step_ok(e) == true);
+
+		path = bm_edgenet_path_calc_best(e, &pass_nr, UINT_MAX,
+		                                 &path_len, &path_cost,
+		                                 vnet_info, path_pool);
+
+		if (path) {
+			BMFace *f = bm_edgenet_face_from_path(bm, path, path_len);
+			/* queue edges to operate on */
+			BMLoop *l_first, *l_iter;
+			l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+			do {
+				if (bm_edge_step_ok(l_iter->e)) {
+					BLI_linklist_prepend_pool(&edge_queue, l_iter->e, edge_queue_pool);
+				}
+			} while ((l_iter = l_iter->next) != l_first);
+
+			if (face_oflag) {
+				BMO_elem_flag_enable(bm, f, face_oflag);
+			}
+
+			/* the face index only needs to be unique, not kept valid */
+			BM_elem_index_set(f, bm->totface - 1);  /* set_dirty */
+		}
+
+		BLI_linklist_free_pool(path, NULL, path_pool);
+		BLI_assert(BLI_mempool_count(path_pool) == 0);
+	}
+
+	bm->elem_index_dirty |= BM_FACE;
+
+	BLI_mempool_destroy(edge_queue_pool);
+	BLI_mempool_destroy(path_pool);
+	MEM_freeN(vnet_info);
+}
diff --git a/source/blender/bmesh/tools/bmesh_edgenet.h b/source/blender/bmesh/tools/bmesh_edgenet.h
new file mode 100644
index 00000000000..ffb3fa133da
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_edgenet.h
@@ -0,0 +1,32 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Campbell Barton
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_EDGENET_H__
+#define __BMESH_EDGENET_H__
+
+/** \file blender/bmesh/tools/bmesh_edgenet.h
+ *  \ingroup bmesh
+ */
+
+void BM_mesh_edgenet(BMesh *bm, const bool use_edge_tag, const short face_oflag);
+
+#endif /* __BMESH_EDGENET_H__ */