BMesh: improve path-select fill region w/ ngons

Rewrote to work with ngons and and more complex topology, now uses separate function.
Fixes T48009.

7 files changed, 587 insertions, 371 deletions

diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index 1afa98fd6f8..30fefe37f0e 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -148,6 +148,8 @@ set(SRC
 	tools/bmesh_intersect.h
 	tools/bmesh_path.c
 	tools/bmesh_path.h
+	tools/bmesh_path_region.c
+	tools/bmesh_path_region.h
 	tools/bmesh_region_match.c
 	tools/bmesh_region_match.h
 	tools/bmesh_triangulate.c
diff --git a/source/blender/bmesh/bmesh_tools.h b/source/blender/bmesh/bmesh_tools.h
index f7f767f91bf..23212dd085e 100644
--- a/source/blender/bmesh/bmesh_tools.h
+++ b/source/blender/bmesh/bmesh_tools.h
@@ -41,6 +41,7 @@ extern "C" {
 #include "tools/bmesh_edgenet.h"
 #include "tools/bmesh_edgesplit.h"
 #include "tools/bmesh_path.h"
+#include "tools/bmesh_path_region.h"
 #include "tools/bmesh_region_match.h"
 #include "tools/bmesh_triangulate.h"
 
diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c
index 79a002f9f41..30b083cacda 100644
--- a/source/blender/bmesh/tools/bmesh_path.c
+++ b/source/blender/bmesh/tools/bmesh_path.c
@@ -15,13 +15,6 @@
  * along with this program; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  *
- * The Original Code is Copyright (C) 2004 Blender Foundation.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
  * ***** END GPL LICENSE BLOCK *****
  */
 
@@ -36,14 +29,11 @@
 
 #include "BLI_math.h"
 #include "BLI_linklist.h"
-#include "BLI_stackdefines.h"
 #include "BLI_heap.h"
 
 #include "bmesh.h"
 #include "bmesh_path.h"  /* own include */
 
-/* optionally expand all paths (result is no longer ordered) */
-#define USE_PATH_FILL
 
 /* -------------------------------------------------------------------- */
 /* Generic Helpers */
@@ -71,72 +61,6 @@ static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3
 /* -------------------------------------------------------------------- */
 /* BM_mesh_calc_path_vert */
 
-#ifdef USE_PATH_FILL
-static void verttag_calc_fill_steps(
-        BMesh *bm, BMVert *v_start, int *steps, int steps_max, BMVert **stack_array,
-        const struct BMCalcPathParams *params)
-{
-	copy_vn_i(steps, bm->totvert, steps_max);
-
-	BMVert **stack = stack_array;
-	STACK_DECLARE(stack);
-	STACK_INIT(stack, bm->totvert);
-
-	STACK_PUSH(stack, v_start);
-	steps[BM_elem_index_get(v_start)] = 0;
-
-	while (STACK_SIZE(stack) != 0) {
-		BMVert *v_a = STACK_POP(stack);
-		const int v_a_index = BM_elem_index_get(v_a);
-		int step_a = steps[v_a_index];
-
-		if (step_a < steps_max) {
-			{
-				BMIter eiter;
-				BMEdge *e;
-				/* loop over faces of face, but do so by first looping over loops */
-				BM_ITER_ELEM (e, &eiter, v_a, BM_EDGES_OF_VERT) {
-					BMVert *v_b = BM_edge_other_vert(e, v_a);
-					if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
-						/* we know 'v_b' is not visited, check it out! */
-						const int v_b_index = BM_elem_index_get(v_b);
-						const int step_b = step_a + 1;
-						if (steps[v_b_index] > step_b) {
-							steps[v_b_index] = step_b;
-							STACK_PUSH(stack, v_b);
-						}
-					}
-				}
-			}
-
-			if (params->use_step_face) {
-				BMIter liter;
-				BMLoop *l;
-				/* loop over faces of face, but do so by first looping over loops */
-				BM_ITER_ELEM (l, &liter, v_a, BM_LOOPS_OF_VERT) {
-					if (l->f->len > 3) {
-						/* skip loops on adjacent edges */
-						BMLoop *l_iter = l->next->next;
-						do {
-							BMVert *v_b = l_iter->v;
-							if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
-								/* we know 'v_b' is not visited, check it out! */
-								const int v_b_index = BM_elem_index_get(v_b);
-								const int step_b = step_a + 1;
-								if (steps[v_b_index] > step_b) {
-									steps[v_b_index] = step_b;
-									STACK_PUSH(stack, v_b);
-								}
-							}
-						} while ((l_iter = l_iter->next) != l->prev);
-					}
-				}
-			}
-		}
-	}
-}
-#endif /* USE_PATH_FILL */
-
 static void verttag_add_adjacent(
         Heap *heap, BMVert *v_a, BMVert **verts_prev, float *cost,
         const struct BMCalcPathParams *params)
@@ -196,7 +120,7 @@ static void verttag_add_adjacent(
 
 LinkNode *BM_mesh_calc_path_vert(
         BMesh *bm, BMVert *v_src, BMVert *v_dst, const struct BMCalcPathParams *params,
-        bool (*test_fn)(BMVert *, void *user_data), void *user_data)
+        bool (*filter_fn)(BMVert *, void *user_data), void *user_data)
 {
 	LinkNode *path = NULL;
 	/* BM_ELEM_TAG flag is used to store visited edges */
@@ -211,13 +135,7 @@ LinkNode *BM_mesh_calc_path_vert(
 	// BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG
 
 	BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
-		if (test_fn(v, user_data)) {
-			BM_elem_flag_disable(v, BM_ELEM_TAG);
-		}
-		else {
-			BM_elem_flag_enable(v, BM_ELEM_TAG);
-		}
-
+		BM_elem_flag_set(v, BM_ELEM_TAG, !filter_fn(v, user_data));
 		BM_elem_index_set(v, i); /* set_inline */
 	}
 	bm->elem_index_dirty &= ~BM_VERT;
@@ -258,36 +176,9 @@ LinkNode *BM_mesh_calc_path_vert(
 	}
 
 	if (v == v_dst) {
-		int path_len = 0;
 		do {
 			BLI_linklist_prepend(&path, v);
-			path_len++;
 		} while ((v = verts_prev[BM_elem_index_get(v)]));
-
-#ifdef USE_PATH_FILL
-		if (params->use_fill) {
-			BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
-				BM_elem_flag_set(v, BM_ELEM_TAG, !test_fn(v, user_data));
-			}
-
-			int *steps_src = MEM_mallocN(sizeof(*steps_src) * totvert, __func__);
-			int *steps_dst = MEM_mallocN(sizeof(*steps_dst) * totvert, __func__);
-
-			/* reuse memory */
-			BMVert **stack_array = verts_prev;
-			verttag_calc_fill_steps(bm, v_src, steps_src, path_len, stack_array, params);
-			verttag_calc_fill_steps(bm, v_dst, steps_dst, path_len, stack_array, params);
-
-			BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
-				if (steps_src[i] + steps_dst[i] < path_len) {
-					BLI_linklist_prepend(&path, v);
-				}
-			}
-
-			MEM_freeN(steps_src);
-			MEM_freeN(steps_dst);
-		}
-#endif
 	}
 
 	MEM_freeN(verts_prev);
@@ -300,86 +191,6 @@ LinkNode *BM_mesh_calc_path_vert(
 /* -------------------------------------------------------------------- */
 /* BM_mesh_calc_path_edge */
 
-#ifdef USE_PATH_FILL
-static void edgetag_calc_fill_steps(
-        BMesh *bm, BMEdge *e_start, int *steps, int steps_max, BMEdge **stack_array,
-        const struct BMCalcPathParams *params)
-{
-	copy_vn_i(steps, bm->totedge, steps_max);
-
-	BMEdge **stack = stack_array;
-	STACK_DECLARE(stack);
-	STACK_INIT(stack, bm->totedge);
-
-	STACK_PUSH(stack, e_start);
-	steps[BM_elem_index_get(e_start)] = 0;
-
-	while (STACK_SIZE(stack) != 0) {
-		BMEdge *e_a = STACK_POP(stack);
-		const int e_a_index = BM_elem_index_get(e_a);
-		int step_a = steps[e_a_index];
-
-		if (step_a < steps_max) {
-			/* unlike vert/face, stepping faces disables scanning connected edges
-			 * and only steps over faces (selecting a ring of edges instead of a loop) */
-			if (params->use_step_face == false) {
-				BMIter viter;
-				BMVert *v;
-
-				BMIter eiter;
-				BMEdge *e_b;
-
-				BM_ITER_ELEM (v, &viter, e_a, BM_VERTS_OF_EDGE) {
-					BM_ITER_ELEM (e_b, &eiter, v, BM_EDGES_OF_VERT) {
-						if (!BM_elem_flag_test(e_b, BM_ELEM_TAG)) {
-							/* we know 'e_b' is not visited, check it out! */
-							const int e_b_index = BM_elem_index_get(e_b);
-							const int step_b = step_a + 1;
-							if (steps[e_b_index] > step_b) {
-								steps[e_b_index] = step_b;
-								STACK_PUSH(stack, e_b);
-							}
-						}
-					}
-				}
-			}
-			else {
-				BMLoop *l_first, *l_iter;
-
-				l_iter = l_first = e_a->l;
-				do {
-					BMLoop *l_cycle_iter, *l_cycle_end;
-
-					l_cycle_iter = l_iter->next;
-					l_cycle_end = l_iter;
-
-					/* good, but we need to allow this otherwise paths may fail to connect at all */
-		#if 0
-					if (l_iter->f->len > 3) {
-						l_cycle_iter = l_cycle_iter->next;
-						l_cycle_end = l_cycle_end->prev;
-					}
-		#endif
-
-					do {
-						BMEdge *e_b = l_cycle_iter->e;
-						if (!BM_elem_flag_test(e_b, BM_ELEM_TAG)) {
-							/* we know 'e_b' is not visited, check it out! */
-							const int e_b_index = BM_elem_index_get(e_b);
-							const int step_b = step_a + 1;
-							if (steps[e_b_index] > step_b) {
-								steps[e_b_index] = step_b;
-								STACK_PUSH(stack, e_b);
-							}
-						}
-					} while ((l_cycle_iter = l_cycle_iter->next) != l_cycle_end);
-				} while ((l_iter = l_iter->radial_next) != l_first);
-			}
-		}
-	}
-}
-#endif /* USE_PATH_FILL */
-
 static float edgetag_cut_cost_vert(BMEdge *e_a, BMEdge *e_b, BMVert *v)
 {
 	BMVert *v1 = BM_edge_other_vert(e_a, v);
@@ -496,13 +307,7 @@ LinkNode *BM_mesh_calc_path_edge(
 	BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */);
 
 	BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
-		if (filter_fn(e, user_data)) {
-			BM_elem_flag_disable(e, BM_ELEM_TAG);
-		}
-		else {
-			BM_elem_flag_enable(e, BM_ELEM_TAG);
-		}
-
+		BM_elem_flag_set(e, BM_ELEM_TAG, !filter_fn(e, user_data));
 		BM_elem_index_set(e, i); /* set_inline */
 	}
 	bm->elem_index_dirty &= ~BM_EDGE;
@@ -543,36 +348,9 @@ LinkNode *BM_mesh_calc_path_edge(
 	}
 
 	if (e == e_dst) {
-		int path_len = 0;
 		do {
 			BLI_linklist_prepend(&path, e);
-			path_len++;
 		} while ((e = edges_prev[BM_elem_index_get(e)]));
-
-#ifdef USE_PATH_FILL
-		if (params->use_fill) {
-			BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
-				BM_elem_flag_set(e, BM_ELEM_TAG, !filter_fn(e, user_data));
-			}
-
-			int *steps_src = MEM_mallocN(sizeof(*steps_src) * totedge, __func__);
-			int *steps_dst = MEM_mallocN(sizeof(*steps_dst) * totedge, __func__);
-
-			/* reuse memory */
-			BMEdge **stack_array = edges_prev;
-			edgetag_calc_fill_steps(bm, e_src, steps_src, path_len, stack_array, params);
-			edgetag_calc_fill_steps(bm, e_dst, steps_dst, path_len, stack_array, params);
-
-			BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
-				if (steps_src[i] + steps_dst[i] < path_len) {
-					BLI_linklist_prepend(&path, e);
-				}
-			}
-
-			MEM_freeN(steps_src);
-			MEM_freeN(steps_dst);
-		}
-#endif
 	}
 
 	MEM_freeN(edges_prev);
@@ -583,84 +361,9 @@ LinkNode *BM_mesh_calc_path_edge(
 }
 
 
-
 /* -------------------------------------------------------------------- */
 /* BM_mesh_calc_path_face */
 
-#ifdef USE_PATH_FILL
-static void facetag_calc_fill_steps(
-        BMesh *bm, BMFace *f_start, int *steps, int steps_max, BMFace **stack_array,
-        const struct BMCalcPathParams *params)
-{
-	copy_vn_i(steps, bm->totface, steps_max);
-
-	BMFace **stack = stack_array;
-	STACK_DECLARE(stack);
-	STACK_INIT(stack, bm->totface);
-
-	STACK_PUSH(stack, f_start);
-	steps[BM_elem_index_get(f_start)] = 0;
-
-	while (STACK_SIZE(stack) != 0) {
-		BMFace *f_a = STACK_POP(stack);
-		const int f_a_index = BM_elem_index_get(f_a);
-		int step_a = steps[f_a_index];
-
-		if (step_a < steps_max) {
-
-			{
-				BMIter liter;
-				BMLoop *l_a;
-
-				BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
-					BMLoop *l_first, *l_iter;
-
-					l_iter = l_first = l_a;
-					do {
-						BMFace *f_b = l_iter->f;
-						if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
-							/* we know 'f_b' is not visited, check it out! */
-							const int f_b_index = BM_elem_index_get(f_b);
-							const int step_b = step_a + 1;
-							if (steps[f_b_index] > step_b) {
-								steps[f_b_index] = step_b;
-								STACK_PUSH(stack, f_b);
-							}
-						}
-					} while ((l_iter = l_iter->radial_next) != l_first);
-				}
-			}
-
-
-			if (params->use_step_face) {
-				BMIter liter;
-				BMLoop *l_a;
-
-				BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
-					BMIter litersub;
-					BMLoop *l_b;
-					BM_ITER_ELEM (l_b, &litersub, l_a->v, BM_LOOPS_OF_VERT) {
-						if ((l_a != l_b) && !BM_loop_share_edge_check(l_a, l_b)) {
-							BMFace *f_b = l_b->f;
-							if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
-								/* we know 'f_b' is not visited, check it out! */
-								const int f_b_index = BM_elem_index_get(f_b);
-								const int step_b = step_a + 1;
-								if (steps[f_b_index] > step_b) {
-									steps[f_b_index] = step_b;
-									STACK_PUSH(stack, f_b);
-								}
-							}
-						}
-					}
-				}
-			}
-
-		}
-	}
-}
-#endif /* USE_PATH_FILL */
-
 static float facetag_cut_cost_edge(BMFace *f_a, BMFace *f_b, BMEdge *e)
 {
 	float f_a_cent[3];
@@ -768,7 +471,7 @@ static void facetag_add_adjacent(
 
 LinkNode *BM_mesh_calc_path_face(
         BMesh *bm, BMFace *f_src, BMFace *f_dst, const struct BMCalcPathParams *params,
-        bool (*test_fn)(BMFace *, void *user_data), void *user_data)
+        bool (*filter_fn)(BMFace *, void *user_data), void *user_data)
 {
 	LinkNode *path = NULL;
 	/* BM_ELEM_TAG flag is used to store visited edges */
@@ -783,13 +486,7 @@ LinkNode *BM_mesh_calc_path_face(
 	// BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG
 
 	BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
-		if (test_fn(f, user_data)) {
-			BM_elem_flag_disable(f, BM_ELEM_TAG);
-		}
-		else {
-			BM_elem_flag_enable(f, BM_ELEM_TAG);
-		}
-
+		BM_elem_flag_set(f, BM_ELEM_TAG, !filter_fn(f, user_data));
 		BM_elem_index_set(f, i); /* set_inline */
 	}
 	bm->elem_index_dirty &= ~BM_FACE;
@@ -830,36 +527,9 @@ LinkNode *BM_mesh_calc_path_face(
 	}
 
 	if (f == f_dst) {
-		int path_len = 0;
 		do {
 			BLI_linklist_prepend(&path, f);
-			path_len++;
 		} while ((f = faces_prev[BM_elem_index_get(f)]));
-
-#ifdef USE_PATH_FILL
-		if (params->use_fill) {
-			BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
-				BM_elem_flag_set(f, BM_ELEM_TAG, !test_fn(f, user_data));
-			}
-
-			int *steps_src = MEM_mallocN(sizeof(*steps_src) * totface, __func__);
-			int *steps_dst = MEM_mallocN(sizeof(*steps_dst) * totface, __func__);
-
-			/* reuse memory */
-			BMFace **stack_array = faces_prev;
-			facetag_calc_fill_steps(bm, f_src, steps_src, path_len, stack_array, params);
-			facetag_calc_fill_steps(bm, f_dst, steps_dst, path_len, stack_array, params);
-
-			BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
-				if (steps_src[i] + steps_dst[i] < path_len) {
-					BLI_linklist_prepend(&path, f);
-				}
-			}
-
-			MEM_freeN(steps_src);
-			MEM_freeN(steps_dst);
-		}
-#endif
 	}
 
 	MEM_freeN(faces_prev);
diff --git a/source/blender/bmesh/tools/bmesh_path.h b/source/blender/bmesh/tools/bmesh_path.h
index 9df1568f750..b6de5e0e4e0 100644
--- a/source/blender/bmesh/tools/bmesh_path.h
+++ b/source/blender/bmesh/tools/bmesh_path.h
@@ -30,8 +30,6 @@
 struct BMCalcPathParams {
 	unsigned int use_topology_distance : 1;
 	unsigned int use_step_face : 1;
-	/* return all paths (no longer ordered) */
-	unsigned int use_fill : 1;
 };
 
 struct LinkNode *BM_mesh_calc_path_vert(
@@ -46,7 +44,7 @@ ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 5);
 
 struct LinkNode *BM_mesh_calc_path_face(
         BMesh *bm, BMFace *f_src, BMFace *f_dst, const struct BMCalcPathParams *params,
-        bool (*test_fn)(BMFace *, void *), void *user_data)
+        bool (*filter_fn)(BMFace *, void *), void *user_data)
 ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 5);
 
 #endif /* __BMESH_PATH_H__ */
diff --git a/source/blender/bmesh/tools/bmesh_path_region.c b/source/blender/bmesh/tools/bmesh_path_region.c
new file mode 100644
index 00000000000..e68dc867269
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_path_region.c
@@ -0,0 +1,462 @@
+/*
+ * ***** 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.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/tools/bmesh_path_region.c
+ *  \ingroup bmesh
+ *
+ * Find the region defined by the path(s) between 2 elements.
+ * (path isn't ordered).
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+#include "BLI_linklist.h"
+#include "BLI_stackdefines.h"
+#include "BLI_alloca.h"
+
+#include "bmesh.h"
+#include "bmesh_path_region.h"  /* own include */
+
+
+/* Special handling of vertices with 2 edges
+ * (act as if the edge-chain is a single edge). */
+#define USE_EDGE_CHAIN
+
+
+#ifdef USE_EDGE_CHAIN
+/**
+ * Takes a vertex with 2 edge users and fills in the vertices at each end-point,
+ * or nothing if if the edges loop back to its self.
+ */
+static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2])
+{
+	BMEdge *e = v_pivot->e;
+	int j = 0;
+	do {
+		BMEdge *e_chain = e;
+		BMVert *v_other = BM_edge_other_vert(e_chain, v_pivot);
+		while (BM_vert_is_edge_pair(v_other)) {
+			BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_other);
+			BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_other) == e_chain);
+			v_other = BM_edge_other_vert(e_chain_next, v_other);
+			if (v_other == v_pivot) {
+				return false;
+			}
+			e_chain = e_chain_next;
+		}
+		v_end_pair[j++] = v_other;
+	} while ((e = BM_DISK_EDGE_NEXT(e, v_pivot)) != v_pivot->e);
+
+	BLI_assert(j == 2);
+	return true;
+}
+#endif  /* USE_EDGE_CHAIN */
+
+
+/** \name Vertex in Region Checks
+ * \{ */
+
+static bool bm_vert_region_test(BMVert *v, int * const depths[2], const int pass)
+{
+	const int index = BM_elem_index_get(v);
+	return (((depths[0][index] != -1) && (depths[1][index] != -1)) && \
+	        ((depths[0][index]        +   depths[1][index]) < pass));
+}
+
+#ifdef USE_EDGE_CHAIN
+static bool bm_vert_region_test_chain(BMVert *v, int * const depths[2], const int pass)
+{
+	BMVert *v_end_pair[2];
+	if (bm_vert_region_test(v, depths, pass)) {
+		return true;
+	}
+	else if (BM_vert_is_edge_pair(v) &&
+	         bm_vert_pair_ends(v, v_end_pair) &&
+	         bm_vert_region_test(v_end_pair[0], depths, pass) &&
+	         bm_vert_region_test(v_end_pair[1], depths, pass))
+	{
+		return true;
+	}
+
+	return false;
+}
+#else
+static bool bm_vert_region_test_chain(BMVert *v, int * const depths[2], const int pass)
+{
+	return bm_vert_region_test(v, depths, pass);
+}
+#endif
+
+/** \} */
+
+
+/**
+ * Main logic for calculating region between 2 elements.
+ *
+ * This method works walking (breadth first) over all vertices,
+ * keeping track of topological distance from the source.
+ *
+ * This is done in both directions, after that each vertices 'depth' is added to check
+ * if its less than the number of passes needed to complete the search.
+ * When it is, we know the path is one of possible paths that have the minimum topological distance.
+ *
+ * \note Only verts without BM_ELEM_TAG will be walked over.
+ */
+static LinkNode *mesh_calc_path_region_elem(
+        BMesh *bm,
+        BMElem *ele_src, BMElem *ele_dst,
+        const char path_htype)
+{
+	int      ele_verts_len[2];
+	BMVert **ele_verts[2];
+
+	/* Get vertices from any `ele_src/ele_dst` elements. */
+	for (int side = 0; side < 2; side++) {
+		BMElem *ele = side ? ele_dst : ele_src;
+		int j = 0;
+
+		if (ele->head.htype == BM_FACE) {
+			BMFace *f = (BMFace *)ele;
+			ele_verts[side] = BLI_array_alloca(ele_verts[side], f->len);
+
+			BMLoop *l_first, *l_iter;
+			l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+			do {
+				ele_verts[side][j++] = l_iter->v;
+			} while ((l_iter = l_iter->next) != l_first);
+		}
+		else if (ele->head.htype == BM_EDGE) {
+			BMEdge *e = (BMEdge *)ele;
+			ele_verts[side] = BLI_array_alloca(ele_verts[side], 2);
+
+			ele_verts[side][j++] = e->v1;
+			ele_verts[side][j++] = e->v2;
+		}
+		else if (ele->head.htype == BM_VERT) {
+			BMVert *v = (BMVert *)ele;
+			ele_verts[side] = BLI_array_alloca(ele_verts[side], 1);
+
+			ele_verts[side][j++] = v;
+		}
+		else {
+			BLI_assert(0);
+		}
+		ele_verts_len[side] = j;
+	}
+
+	int *depths[2] = {NULL};
+	int pass = 0;
+
+	BMVert **stack       = MEM_mallocN(sizeof(*stack)       * bm->totvert, __func__);
+	BMVert **stack_other = MEM_mallocN(sizeof(*stack_other) * bm->totvert, __func__);
+
+	STACK_DECLARE(stack);
+	STACK_INIT(stack, bm->totvert);
+
+	STACK_DECLARE(stack_other);
+	STACK_INIT(stack_other, bm->totvert);
+
+	BM_mesh_elem_index_ensure(bm, BM_VERT);
+
+	/* After exhausting all possible elements, we should have found all elements on the 'side_other'.
+	 * otherwise, exit early. */
+	bool found_all = false;
+
+	for (int side = 0; side < 2; side++) {
+		const int side_other = !side;
+
+		/* initialize depths to -1 (un-touched), fill in with the depth as we walk over the edges. */
+		depths[side] = MEM_mallocN(sizeof(*depths[side]) * bm->totvert, __func__);
+		copy_vn_i(depths[side], bm->totvert, -1);
+
+		/* needed for second side */
+		STACK_CLEAR(stack);
+		STACK_CLEAR(stack_other);
+
+		for (int i = 0; i < ele_verts_len[side]; i++) {
+			BMVert *v = ele_verts[side][i];
+			depths[side][BM_elem_index_get(v)] = 0;
+			if (v->e && !BM_elem_flag_test(v, BM_ELEM_TAG)) {
+				STACK_PUSH(stack, v);
+			}
+		}
+
+#ifdef USE_EDGE_CHAIN
+		/* Expand initial state to end-point vertices when they only have 2x edges,
+		 * this prevents odd behavior when source or destination are in the middle of a long chain of edges. */
+		if (ELEM(path_htype, BM_VERT, BM_EDGE)) {
+			for (int i = 0; i < ele_verts_len[side]; i++) {
+				BMVert *v = ele_verts[side][i];
+				BMVert *v_end_pair[2];
+				if (BM_vert_is_edge_pair(v) && bm_vert_pair_ends(v, v_end_pair)) {
+					for (int j = 0; j < 2; j++) {
+						const int v_end_index = BM_elem_index_get(v_end_pair[j]);
+						if (depths[side][v_end_index] == -1) {
+							depths[side][v_end_index] = 0;
+							if (!BM_elem_flag_test(v_end_pair[j], BM_ELEM_TAG)) {
+								STACK_PUSH(stack, v_end_pair[j]);
+							}
+						}
+					}
+				}
+			}
+		}
+#endif  /* USE_EDGE_CHAIN */
+
+		/* Keep walking over connected geometry until we find all the vertices in `ele_verts[side_other]`,
+		 * or exit the loop when theres no connection. */
+		found_all = false;
+		for (pass = 1; (STACK_SIZE(stack) != 0); pass++) {
+			while (STACK_SIZE(stack) != 0) {
+				BMVert *v_a = STACK_POP(stack);
+				const int v_a_index = BM_elem_index_get(v_a);
+				BMEdge *e = v_a->e;
+
+				do {
+					BMVert *v_b = BM_edge_other_vert(e, v_a);
+					int v_b_index = BM_elem_index_get(v_b);
+					if (depths[side][v_b_index] == -1) {
+
+#ifdef USE_EDGE_CHAIN
+						/* Walk along the chain, fill in values until we reach a vertex with 3+ edges. */
+						{
+							BMEdge *e_chain = e;
+							while (BM_vert_is_edge_pair(v_b) &&
+							       ((depths[side][v_b_index] == -1)))
+							{
+								depths[side][v_b_index] = pass;
+
+								BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_b);
+								BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_b) == e_chain);
+								v_b = BM_edge_other_vert(e_chain_next, v_b);
+								v_b_index = BM_elem_index_get(v_b);
+								e_chain = e_chain_next;
+							}
+						}
+#endif  /* USE_EDGE_CHAIN */
+
+						/* Add the other vertex to the stack, to be traversed in the next pass. */
+						if (depths[side][v_b_index] == -1) {
+#ifdef USE_EDGE_CHAIN
+							BLI_assert(!BM_vert_is_edge_pair(v_b));
+#endif
+							BLI_assert(pass == depths[side][v_a_index] + 1);
+							depths[side][v_b_index] = pass;
+							if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
+								STACK_PUSH(stack_other, v_b);
+							}
+						}
+					}
+				} while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != v_a->e);
+			}
+
+			/* Stop searching once theres none left.
+			 * Note that this looks in-efficient, however until the target elements reached,
+			 * it will exit immediately.
+			 * After that, it takes as many passes as the element has edges to finish off. */
+			found_all = true;
+			for (int i = 0; i < ele_verts_len[side_other]; i++) {
+				if (depths[side][BM_elem_index_get(ele_verts[side_other][i])] == -1) {
+					found_all = false;
+					break;
+				}
+			}
+			if (found_all == true) {
+				pass++;
+				break;
+			}
+
+			STACK_SWAP(stack, stack_other);
+		}
+
+		/* if we have nothing left, and didn't find all elements on the other side,
+		 * exit early and don't continue */
+		if (found_all == false) {
+			break;
+		}
+	}
+
+	MEM_freeN(stack);
+	MEM_freeN(stack_other);
+
+
+	/* Now we have depths recorded from both sides,
+	 * select elements that use tagged verts. */
+	LinkNode *path = NULL;
+
+	if (found_all == false) {
+		/* fail! (do nothing) */
+	}
+	else if (path_htype == BM_FACE) {
+		BMIter fiter;
+		BMFace *f;
+
+		BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
+			if (!BM_elem_flag_test(f, BM_ELEM_TAG)) {
+				/* check all verts in face are tagged */
+				BMLoop *l_first, *l_iter;
+				l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+				bool ok = true;
+				do {
+					if (!bm_vert_region_test_chain(l_iter->v, depths, pass)) {
+						ok = false;
+						break;
+					}
+				} while ((l_iter = l_iter->next) != l_first);
+
+				if (ok) {
+					BLI_linklist_prepend(&path, f);
+				}
+			}
+		}
+	}
+	else if (path_htype == BM_EDGE) {
+		BMIter eiter;
+		BMEdge *e;
+
+		BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
+			if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
+				/* check all verts in edge are tagged */
+				bool ok = true;
+				for (int j = 0; j < 2; j++) {
+					if (!bm_vert_region_test_chain(*((&e->v1) + j), depths, pass)) {
+						ok = false;
+						break;
+					}
+				}
+
+				if (ok) {
+					BLI_linklist_prepend(&path, e);
+				}
+			}
+		}
+	}
+	else if (path_htype == BM_VERT) {
+		BMIter viter;
+		BMVert *v;
+
+		BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
+			if (bm_vert_region_test_chain(v, depths, pass)) {
+				BLI_linklist_prepend(&path, v);
+			}
+		}
+	}
+
+
+	for (int side = 0; side < 2; side++) {
+		if (depths[side]) {
+			MEM_freeN(depths[side]);
+		}
+	}
+
+	return path;
+}
+
+#undef USE_EDGE_CHAIN
+
+
+/** \name Main Functions (exposed externally).
+ * \{ */
+
+LinkNode *BM_mesh_calc_path_region_vert(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*filter_fn)(BMVert *, void *user_data), void *user_data)
+{
+	LinkNode *path = NULL;
+	/* BM_ELEM_TAG flag is used to store visited verts */
+	BMVert *v;
+	BMIter viter;
+	int i;
+
+	BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
+		BM_elem_flag_set(v, BM_ELEM_TAG, !filter_fn(v, user_data));
+		BM_elem_index_set(v, i); /* set_inline */
+	}
+	bm->elem_index_dirty &= ~BM_VERT;
+
+	path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_VERT);
+
+	return path;
+}
+
+LinkNode *BM_mesh_calc_path_region_edge(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*filter_fn)(BMEdge *, void *user_data), void *user_data)
+{
+	LinkNode *path = NULL;
+	/* BM_ELEM_TAG flag is used to store visited verts */
+	BMEdge *e;
+	BMIter eiter;
+	int i;
+
+	/* flush flag to verts */
+	BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, false);
+
+	BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
+		bool test;
+		BM_elem_flag_set(e, BM_ELEM_TAG, test = !filter_fn(e, user_data));
+
+		/* flush tag to verts */
+		if (test == false) {
+			for (int j = 0; j < 2; j++) {
+				BM_elem_flag_disable(*((&e->v1) + j), BM_ELEM_TAG);
+			}
+		}
+	}
+
+	path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_EDGE);
+
+	return path;
+}
+
+LinkNode *BM_mesh_calc_path_region_face(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*filter_fn)(BMFace *, void *user_data), void *user_data)
+{
+	LinkNode *path = NULL;
+	/* BM_ELEM_TAG flag is used to store visited verts */
+	BMFace *f;
+	BMIter fiter;
+	int i;
+
+	/* flush flag to verts */
+	BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, false);
+
+	BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
+		bool test;
+		BM_elem_flag_set(f, BM_ELEM_TAG, test = !filter_fn(f, user_data));
+
+		/* flush tag to verts */
+		if (test == false) {
+			BMLoop *l_first, *l_iter;
+			l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+			do {
+				BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG);
+			} while ((l_iter = l_iter->next) != l_first);
+		}
+	}
+
+	path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_FACE);
+
+	return path;
+}
+
+/** \} */
diff --git a/source/blender/bmesh/tools/bmesh_path_region.h b/source/blender/bmesh/tools/bmesh_path_region.h
new file mode 100644
index 00000000000..06e56a59fb2
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_path_region.h
@@ -0,0 +1,43 @@
+/*
+ * ***** 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.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_PATH_REGION_H__
+#define __BMESH_PATH_REGION_H__
+
+/** \file blender/bmesh/tools/bmesh_path_region.h
+ *  \ingroup bmesh
+ */
+
+struct LinkNode *BM_mesh_calc_path_region_vert(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*test_fn)(BMVert *, void *user_data), void *user_data)
+ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3);
+
+struct LinkNode *BM_mesh_calc_path_region_edge(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*test_fn)(BMEdge *, void *user_data), void *user_data)
+ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3);
+
+struct LinkNode *BM_mesh_calc_path_region_face(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*test_fn)(BMFace *, void *user_data), void *user_data)
+ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3);
+
+#endif /* __BMESH_PATH_REGION_H__ */
diff --git a/source/blender/editors/mesh/editmesh_path.c b/source/blender/editors/mesh/editmesh_path.c
index 1a8eae784aa..55ed0e521ea 100644
--- a/source/blender/editors/mesh/editmesh_path.c
+++ b/source/blender/editors/mesh/editmesh_path.c
@@ -128,17 +128,26 @@ static void mouse_mesh_shortest_path_vert(
 
 	struct UserData user_data = {bm, obedit->data, op_params};
 	LinkNode *path = NULL;
+	bool is_path_ordered = false;
 
 	if (v_act && (v_act != v_dst)) {
-		if ((path = BM_mesh_calc_path_vert(
-		         bm, v_act, v_dst,
-		         &(const struct BMCalcPathParams) {
-		             .use_topology_distance = op_params->use_topology_distance,
-		             .use_step_face = op_params->use_face_step,
-		             .use_fill = op_params->use_fill,
-		         },
-		         verttag_filter_cb, &user_data)))
-		{
+		if (op_params->use_fill) {
+			path = BM_mesh_calc_path_region_vert(
+			        bm, (BMElem *)v_act, (BMElem *)v_dst,
+			        verttag_filter_cb, &user_data);
+		}
+		else {
+			is_path_ordered = true;
+			path = BM_mesh_calc_path_vert(
+			        bm, v_act, v_dst,
+			        &(const struct BMCalcPathParams) {
+			            .use_topology_distance = op_params->use_topology_distance,
+			            .use_step_face = op_params->use_face_step,
+			        },
+			        verttag_filter_cb, &user_data);
+		}
+
+		if (path) {
 			if (op_params->track_active) {
 				BM_select_history_remove(bm, v_act);
 			}
@@ -163,9 +172,13 @@ static void mouse_mesh_shortest_path_vert(
 		int depth = 1;
 		node = path;
 		do {
-			if (WM_operator_properties_checker_interval_test(&op_params->interval_params, depth)) {
+			if ((is_path_ordered == false) ||
+			    WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
+			{
 				verttag_set_cb((BMVert *)node->link, !all_set, &user_data);
-				v_dst_last = node->link;
+				if (is_path_ordered) {
+					v_dst_last = node->link;
+				}
 			}
 		} while ((void)depth++, (node = node->next));
 
@@ -302,19 +315,28 @@ static void mouse_mesh_shortest_path_edge(
 	struct UserData user_data = {bm, obedit->data, op_params};
 	LinkNode *path = NULL;
 	Mesh *me = obedit->data;
+	bool is_path_ordered = false;
 
 	edgetag_ensure_cd_flag(scene, obedit->data);
 
 	if (e_act && (e_act != e_dst)) {
-		if ((path = BM_mesh_calc_path_edge(
-		         bm, e_act, e_dst,
-		         &(const struct BMCalcPathParams) {
-		             .use_topology_distance = op_params->use_topology_distance,
-		             .use_step_face = op_params->use_face_step,
-		             .use_fill = op_params->use_fill,
-		         },
-		         edgetag_filter_cb, &user_data)))
-		{
+		if (op_params->use_fill) {
+			path = BM_mesh_calc_path_region_edge(
+			        bm, (BMElem *)e_act, (BMElem *)e_dst,
+			        edgetag_filter_cb, &user_data);
+		}
+		else {
+			is_path_ordered = true;
+			path = BM_mesh_calc_path_edge(
+			        bm, e_act, e_dst,
+			        &(const struct BMCalcPathParams) {
+			            .use_topology_distance = op_params->use_topology_distance,
+			            .use_step_face = op_params->use_face_step,
+			        },
+			        edgetag_filter_cb, &user_data);
+		}
+
+		if (path) {
 			if (op_params->track_active) {
 				BM_select_history_remove(bm, e_act);
 			}
@@ -339,9 +361,13 @@ static void mouse_mesh_shortest_path_edge(
 		int depth = 1;
 		node = path;
 		do {
-			if (WM_operator_properties_checker_interval_test(&op_params->interval_params, depth)) {
+			if ((is_path_ordered == false) ||
+			    WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
+			{
 				edgetag_set_cb((BMEdge *)node->link, !all_set, &user_data);
-				e_dst_last = node->link;
+				if (is_path_ordered) {
+					e_dst_last = node->link;
+				}
 			}
 		} while ((void)depth++, (node = node->next));
 
@@ -433,18 +459,28 @@ static void mouse_mesh_shortest_path_face(
 
 	struct UserData user_data = {bm, obedit->data, op_params};
 	LinkNode *path = NULL;
+	bool is_path_ordered = false;
 
 	if (f_act) {
+		if (op_params->use_fill) {
+			path = BM_mesh_calc_path_region_face(
+			        bm, (BMElem *)f_act, (BMElem *)f_dst,
+			        facetag_filter_cb, &user_data);
+		}
+		else {
+			is_path_ordered = true;
+			path = BM_mesh_calc_path_face(
+			        bm, f_act, f_dst,
+			        &(const struct BMCalcPathParams) {
+			            .use_topology_distance = op_params->use_topology_distance,
+			            .use_step_face = op_params->use_face_step,
+			        },
+			        facetag_filter_cb, &user_data);
+		}
+
+
 		if (f_act != f_dst) {
-			if ((path = BM_mesh_calc_path_face(
-			         bm, f_act, f_dst,
-			         &(const struct BMCalcPathParams) {
-			             .use_topology_distance = op_params->use_topology_distance,
-			             .use_step_face = op_params->use_face_step,
-			             .use_fill = op_params->use_fill,
-			         },
-			         facetag_filter_cb, &user_data)))
-			{
+			if (path) {
 				if (op_params->track_active) {
 					BM_select_history_remove(bm, f_act);
 				}
@@ -470,9 +506,13 @@ static void mouse_mesh_shortest_path_face(
 		int depth = 1;
 		node = path;
 		do {
-			if (WM_operator_properties_checker_interval_test(&op_params->interval_params, depth)) {
+			if ((is_path_ordered == false) ||
+			    WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
+			{
 				facetag_set_cb((BMFace *)node->link, !all_set, &user_data);
-				f_dst_last = node->link;
+				if (is_path_ordered) {
+					f_dst_last = node->link;
+				}
 			}
 		} while ((void)depth++, (node = node->next));