edit-mesh improvements to select shortest path

- Ctrl+RMB only worked for edges & faces
- Menu item 'Select Shortest Path' only worked for vertices.

Now Ctrl+RMB works for vertices and the menu item works for verts/edges/faces (depending on the current selection).

13 files changed, 1089 insertions, 816 deletions

diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index 0d01e078e83..1e704e04b43 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -122,6 +122,8 @@ set(SRC
 	tools/bmesh_decimate.h
 	tools/bmesh_edgesplit.c
 	tools/bmesh_edgesplit.h
+	tools/bmesh_path.c
+	tools/bmesh_path.h
 	tools/bmesh_triangulate.c
 	tools/bmesh_triangulate.h
 
diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h
index de78e192ebb..022dfe452e7 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_path.h"
 #include "tools/bmesh_triangulate.h"
 
 #ifdef __cplusplus
diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c
index b42e6c537a9..497c99f3f8a 100644
--- a/source/blender/bmesh/intern/bmesh_opdefines.c
+++ b/source/blender/bmesh/intern/bmesh_opdefines.c
@@ -1276,27 +1276,6 @@ static BMOpDefine bmo_reverse_colors_def = {
 };
 
 /*
- * Shortest Path.
- *
- * Select the shortest path between 2 verts.
- */
-static BMOpDefine bmo_shortest_path_def = {
-	"shortest_path",
-	/* slots_in */
-	{{"vert_start", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT | BMO_OP_SLOT_SUBTYPE_ELEM_IS_SINGLE}},   /* start vertex */
-	 {"vert_end", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT | BMO_OP_SLOT_SUBTYPE_ELEM_IS_SINGLE}},     /* end vertex */
-	 {"type", BMO_OP_SLOT_INT},             /* type of selection */
-	 {{'\0'}},
-	},
-	/* slots_out */
-	{{"verts.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT}}, /* output vertices */
-	 {{'\0'}},
-	},
-	bmo_shortest_path_exec,
-	BMO_OPTYPE_FLAG_SELECT_FLUSH,
-};
-
-/*
  * Edge Split.
  *
  * Disconnects faces along input edges.
@@ -1769,7 +1748,6 @@ const BMOpDefine *bmo_opdefines[] = {
 	&bmo_rotate_edges_def,
 	&bmo_rotate_uvs_def,
 	&bmo_scale_def,
-	&bmo_shortest_path_def,
 	&bmo_similar_edges_def,
 	&bmo_similar_faces_def,
 	&bmo_similar_verts_def,
diff --git a/source/blender/bmesh/intern/bmesh_operators.h b/source/blender/bmesh/intern/bmesh_operators.h
index efb0c65408b..7f62d4cd21a 100644
--- a/source/blender/bmesh/intern/bmesh_operators.h
+++ b/source/blender/bmesh/intern/bmesh_operators.h
@@ -110,12 +110,6 @@ enum {
 	SIMVERT_EDGE
 };
 
-/* vertex path selection values */
-enum {
-	VPATH_SELECT_EDGE_LENGTH = 0,
-	VPATH_SELECT_TOPOLOGICAL
-};
-
 /* Poke face center calculation */
 enum {
 	BMOP_POKE_MEAN_WEIGHTED = 0,
diff --git a/source/blender/bmesh/operators/bmo_utils.c b/source/blender/bmesh/operators/bmo_utils.c
index 14870dc918a..5e61b8ea7ea 100644
--- a/source/blender/bmesh/operators/bmo_utils.c
+++ b/source/blender/bmesh/operators/bmo_utils.c
@@ -673,111 +673,3 @@ void bmo_reverse_colors_exec(BMesh *bm, BMOperator *op)
 		}
 	}
 }
-
-
-/*************************************************************************** *
- * shortest vertex path select
- *************************************************************************** */
-
-typedef struct ElemNode {
-	BMVert *v;	/* vertex */
-	BMVert *parent;	/* node parent id */
-	float weight;	/* node weight */
-	HeapNode *hn;	/* heap node */
-} ElemNode;
-
-#define VERT_MARK	1
-
-void bmo_shortest_path_exec(BMesh *bm, BMOperator *op)
-{
-	BMIter v_iter;		/* mesh verts iterator */
-	BMVert *sv, *ev;	/* starting vertex, ending vertex */
-	BMVert *v;		/* mesh vertex */
-	Heap *h = NULL;
-
-	ElemNode *vert_list = NULL;
-
-	int num_total = 0 /*, num_sels = 0 */, i = 0;
-	const int type = BMO_slot_int_get(op->slots_in, "type");
-
-	sv = BMO_slot_buffer_get_single(BMO_slot_get(op->slots_in, "vert_start"));
-	ev = BMO_slot_buffer_get_single(BMO_slot_get(op->slots_in, "vert_end"));
-
-	num_total = BM_mesh_elem_count(bm, BM_VERT);
-
-	/* allocate memory for the nodes */
-	vert_list = (ElemNode *)MEM_mallocN(sizeof(ElemNode) * num_total, "vertex nodes");
-
-	/* iterate through all the mesh vertices */
-	/* loop through all the vertices and fill the vertices/indices structure */
-	i = 0;
-	BM_ITER_MESH (v, &v_iter, bm, BM_VERTS_OF_MESH) {
-		vert_list[i].v = v;
-		vert_list[i].parent = NULL;
-		vert_list[i].weight = FLT_MAX;
-		BM_elem_index_set(v, i); /* set_inline */
-		i++;
-	}
-	bm->elem_index_dirty &= ~BM_VERT;
-
-	/*
-	 * we now have everything we need, start Dijkstra path finding algorithm
-	 */
-
-	/* set the distance/weight of the start vertex to 0 */
-	vert_list[BM_elem_index_get(sv)].weight = 0.0f;
-
-	h = BLI_heap_new();
-
-	for (i = 0; i < num_total; i++) {
-		vert_list[i].hn = BLI_heap_insert(h, vert_list[i].weight, vert_list[i].v);
-	}
-
-	while (!BLI_heap_is_empty(h)) {
-		BMEdge *e;
-		BMIter e_i;
-		float v_weight;
-
-		/* take the vertex with the lowest weight out of the heap */
-		BMVert *v = (BMVert *)BLI_heap_popmin(h);
-
-		if (vert_list[BM_elem_index_get(v)].weight == FLT_MAX) /* this means that there is no path */
-			break;
-
-		v_weight = vert_list[BM_elem_index_get(v)].weight;
-
-		BM_ITER_ELEM (e, &e_i, v, BM_EDGES_OF_VERT) {
-			BMVert *u;
-			float e_weight = v_weight;
-
-			if (type == VPATH_SELECT_EDGE_LENGTH)
-				e_weight += len_v3v3(e->v1->co, e->v2->co);
-			else e_weight += 1.0f;
-
-			u = (e->v1 == v) ? e->v2 : e->v1;
-
-			if (e_weight < vert_list[BM_elem_index_get(u)].weight) { /* is this path shorter ? */
-				/* add it if so */
-				vert_list[BM_elem_index_get(u)].parent = v;
-				vert_list[BM_elem_index_get(u)].weight = e_weight;
-
-				/* we should do a heap update node function!!! :-/ */
-				BLI_heap_remove(h, vert_list[BM_elem_index_get(u)].hn);
-				BLI_heap_insert(h, e_weight, u);
-			}
-		}
-	}
-
-	/* now we trace the path (if it exists) */
-	v = ev;
-
-	while (vert_list[BM_elem_index_get(v)].parent != NULL) {
-		BMO_elem_flag_enable(bm, v, VERT_MARK);
-		v = vert_list[BM_elem_index_get(v)].parent;
-	}
-
-	BLI_heap_free(h, NULL);
-	MEM_freeN(vert_list);
-
-	BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "verts.out", BM_VERT, VERT_MARK);
-}
diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c
new file mode 100644
index 00000000000..eda252f18f5
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_path.c
@@ -0,0 +1,411 @@
+/*
+ * ***** 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.
+ *
+ * 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 *****
+ */
+
+/** \file blender/bmesh/tools/bmesh_path.c
+ *  \ingroup bmesh
+ *
+ * Find a path between 2 elements.
+ *
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+#include "BLI_linklist.h"
+#include "BLI_heap.h"
+
+#include "bmesh.h"
+#include "bmesh_path.h"  /* own include */
+
+/* -------------------------------------------------------------------- */
+/* Generic Helpers */
+
+static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3[3])
+{
+	float cost, d1[3], d2[3];
+
+
+	/* The cost is based on the simple sum of the length of the two edgees... */
+	sub_v3_v3v3(d1, v2, v1);
+	sub_v3_v3v3(d2, v3, v2);
+	cost = normalize_v3(d1) + normalize_v3(d2);
+
+	/* but is biased to give higher values to sharp turns, so that it will take
+	 * paths with fewer "turns" when selecting between equal-weighted paths between
+	 * the two edges */
+	cost = cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v3v3(d1, d2)))));
+
+	return cost;
+}
+
+
+
+/* -------------------------------------------------------------------- */
+/* BM_mesh_calc_path_vert */
+
+static void verttag_add_adjacent(Heap *heap, BMVert *v_a, BMVert **verts_prev, float *cost, const bool use_length)
+{
+	BMIter eiter;
+	BMEdge *e;
+	BMVert *v_b;
+
+	const int v_a_index = BM_elem_index_get(v_a);
+
+	/* loop over faces of face, but do so by first looping over loops */
+	BM_ITER_ELEM (e, &eiter, v_a, BM_EDGES_OF_VERT) {
+		v_b = BM_edge_other_vert(e, v_a);
+		if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
+			/* we know 'f_b' is not visited, check it out! */
+			const int v_b_index = BM_elem_index_get(v_b);
+			const float cost_cut = use_length ? len_v3v3(v_a->co, v_b->co) : 1.0f;
+			const float cost_new = cost[v_a_index] + cost_cut;
+
+			if (cost[v_b_index] > cost_new) {
+				cost[v_b_index] = cost_new;
+				verts_prev[v_b_index] = v_a;
+				BLI_heap_insert(heap, cost_new, v_b);
+			}
+		}
+	}
+}
+
+LinkNode *BM_mesh_calc_path_vert(
+        BMesh *bm, BMVert *v_src, BMVert *v_dst, const bool use_length,
+        void *user_data, bool (*test_fn)(BMVert *, void *user_data))
+{
+	LinkNode *path = NULL;
+	/* BM_ELEM_TAG flag is used to store visited edges */
+	BMVert *v;
+	BMIter viter;
+	Heap *heap;
+	float *cost;
+	BMVert **verts_prev;
+	int i, totvert;
+
+	/* note, would pass BM_EDGE except we are looping over all faces anyway */
+	// 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_index_set(v, i); /* set_inline */
+	}
+	bm->elem_index_dirty &= ~BM_VERT;
+
+	/* alloc */
+	totvert = bm->totvert;
+	verts_prev = MEM_callocN(sizeof(*verts_prev) * totvert, __func__);
+	cost = MEM_mallocN(sizeof(*cost) * totvert, __func__);
+
+	fill_vn_fl(cost, totvert, 1e20f);
+
+	/*
+	 * Arrays are now filled as follows:
+	 *
+	 * As the search continues, verts_prev[n] will be the previous verts on the shortest
+	 * path found so far to face n. BM_ELEM_TAG is used to tag elements we have visited,
+	 * cost[n] will contain the length of the shortest
+	 * path to face n found so far, Finally, heap is a priority heap which is built on the
+	 * the same data as the cost array, but inverted: it is a worklist of faces prioritized
+	 * by the shortest path found so far to the face.
+	 */
+
+	/* regular dijkstra shortest path, but over faces instead of vertices */
+	heap = BLI_heap_new();
+	BLI_heap_insert(heap, 0.0f, v_src);
+	cost[BM_elem_index_get(v_src)] = 0.0f;
+
+	while ((v = BLI_heap_popmin(heap))) {
+
+		if (v == v_dst)
+			break;
+
+		if (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
+			BM_elem_flag_enable(v, BM_ELEM_TAG);
+			verttag_add_adjacent(heap, v, verts_prev, cost, use_length);
+		}
+	}
+
+	if (v == v_dst) {
+		do {
+			BLI_linklist_prepend(&path, v);
+		} while ((v = verts_prev[BM_elem_index_get(v)]));
+	}
+
+	MEM_freeN(verts_prev);
+	MEM_freeN(cost);
+	BLI_heap_free(heap, NULL);
+
+	return path;
+}
+
+
+
+/* -------------------------------------------------------------------- */
+/* BM_mesh_calc_path_edge */
+
+
+static float edgetag_cut_cost(BMEdge *e1, BMEdge *e2, BMVert *v)
+{
+	BMVert *v1 = BM_edge_other_vert(e1, v);
+	BMVert *v2 = BM_edge_other_vert(e2, v);
+	return step_cost_3_v3(v1->co, v->co, v2->co);
+}
+
+static void edgetag_add_adjacent(Heap *heap, BMEdge *e1, BMEdge **edges_prev, float *cost, const bool use_length)
+{
+	BMIter viter;
+	BMVert *v;
+
+	BMIter eiter;
+	BMEdge *e2;
+
+	const int e1_index = BM_elem_index_get(e1);
+
+	BM_ITER_ELEM (v, &viter, e1, BM_VERTS_OF_EDGE) {
+		BM_ITER_ELEM (e2, &eiter, v, BM_EDGES_OF_VERT) {
+			if (!BM_elem_flag_test(e2, BM_ELEM_TAG)) {
+				/* we know 'e2' is not visited, check it out! */
+				const int e2_index = BM_elem_index_get(e2);
+				const float cost_cut = use_length ? edgetag_cut_cost(e1, e2, v) : 1.0f;
+				const float cost_new = cost[e1_index] + cost_cut;
+
+				if (cost[e2_index] > cost_new) {
+					cost[e2_index] = cost_new;
+					edges_prev[e2_index] = e1;
+					BLI_heap_insert(heap, cost_new, e2);
+				}
+			}
+		}
+	}
+}
+
+
+LinkNode *BM_mesh_calc_path_edge(
+        BMesh *bm, BMEdge *e_src, BMEdge *e_dst, const bool use_length,
+        void *user_data, bool (*filter_fn)(BMEdge *, void *user_data))
+{
+	LinkNode *path = NULL;
+	/* BM_ELEM_TAG flag is used to store visited edges */
+	BMEdge *e;
+	BMIter eiter;
+	Heap *heap;
+	float *cost;
+	BMEdge **edges_prev;
+	int i, totedge;
+
+	/* note, would pass BM_EDGE except we are looping over all edges anyway */
+	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_index_set(e, i); /* set_inline */
+	}
+	bm->elem_index_dirty &= ~BM_EDGE;
+
+	/* alloc */
+	totedge = bm->totedge;
+	edges_prev = MEM_callocN(sizeof(*edges_prev) * totedge, "SeamPathPrevious");
+	cost = MEM_mallocN(sizeof(*cost) * totedge, "SeamPathCost");
+
+	fill_vn_fl(cost, totedge, 1e20f);
+
+	/*
+	 * Arrays are now filled as follows:
+	 *
+	 * As the search continues, prevedge[n] will be the previous edge on the shortest
+	 * path found so far to edge n. BM_ELEM_TAG is used to tag elements we have visited,
+	 * cost[n] will contain the length of the shortest
+	 * path to edge n found so far, Finally, heap is a priority heap which is built on the
+	 * the same data as the cost array, but inverted: it is a worklist of edges prioritized
+	 * by the shortest path found so far to the edge.
+	 */
+
+	/* regular dijkstra shortest path, but over edges instead of vertices */
+	heap = BLI_heap_new();
+	BLI_heap_insert(heap, 0.0f, e_src);
+	cost[BM_elem_index_get(e_src)] = 0.0f;
+
+	while ((e = BLI_heap_popmin(heap))) {
+
+		if (e == e_dst)
+			break;
+
+		if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
+			BM_elem_flag_enable(e, BM_ELEM_TAG);
+			edgetag_add_adjacent(heap, e, edges_prev, cost, use_length);
+		}
+	}
+
+	if (e == e_dst) {
+		do {
+			BLI_linklist_prepend(&path, e);
+		} while ((e = edges_prev[BM_elem_index_get(e)]));
+	}
+
+	MEM_freeN(edges_prev);
+	MEM_freeN(cost);
+	BLI_heap_free(heap, NULL);
+
+	return path;
+}
+
+
+
+/* -------------------------------------------------------------------- */
+/* BM_mesh_calc_path_face */
+
+static float facetag_cut_cost(BMFace *f_a, BMFace *f_b, BMEdge *e)
+{
+	float f_a_cent[3];
+	float f_b_cent[3];
+	float e_cent[3];
+
+	BM_face_calc_center_mean(f_a, f_a_cent);
+	BM_face_calc_center_mean(f_b, f_b_cent);
+	mid_v3_v3v3(e_cent, e->v1->co, e->v2->co);
+
+	return step_cost_3_v3(f_a_cent, e_cent, f_b_cent);
+}
+
+static void facetag_add_adjacent(Heap *heap, BMFace *f_a, BMFace **faces_prev, float *cost, const bool use_length)
+{
+	BMIter liter;
+	BMLoop *l_a;
+	BMFace *f_b;
+
+	const int f_a_index = BM_elem_index_get(f_a);
+
+	/* loop over faces of face, but do so by first looping over loops */
+	BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
+		BMLoop *l_first;
+		BMLoop *l_iter;
+
+		l_iter = l_first = l_a;
+		do {
+			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 float cost_cut = use_length ? facetag_cut_cost(f_a, f_b, l_iter->e) : 1.0f;
+				const float cost_new = cost[f_a_index] + cost_cut;
+
+				if (cost[f_b_index] > cost_new) {
+					cost[f_b_index] = cost_new;
+					faces_prev[f_b_index] = f_a;
+					BLI_heap_insert(heap, cost_new, f_b);
+				}
+			}
+		} while ((l_iter = l_iter->radial_next) != l_first);
+	}
+}
+
+LinkNode *BM_mesh_calc_path_face(
+        BMesh *bm, BMFace *f_src, BMFace *f_dst, const bool use_length,
+        void *user_data, bool (*test_fn)(BMFace *, void *user_data))
+{
+	LinkNode *path = NULL;
+	/* BM_ELEM_TAG flag is used to store visited edges */
+	BMFace *f;
+	BMIter fiter;
+	Heap *heap;
+	float *cost;
+	BMFace **faces_prev;
+	int i, totface;
+
+	/* note, would pass BM_EDGE except we are looping over all faces anyway */
+	// 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_index_set(f, i); /* set_inline */
+	}
+	bm->elem_index_dirty &= ~BM_FACE;
+
+	/* alloc */
+	totface = bm->totface;
+	faces_prev = MEM_callocN(sizeof(*faces_prev) * totface, __func__);
+	cost = MEM_mallocN(sizeof(*cost) * totface, __func__);
+
+	fill_vn_fl(cost, totface, 1e20f);
+
+	/*
+	 * Arrays are now filled as follows:
+	 *
+	 * As the search continues, faces_prev[n] will be the previous face on the shortest
+	 * path found so far to face n. BM_ELEM_TAG is used to tag elements we have visited,
+	 * cost[n] will contain the length of the shortest
+	 * path to face n found so far, Finally, heap is a priority heap which is built on the
+	 * the same data as the cost array, but inverted: it is a worklist of faces prioritized
+	 * by the shortest path found so far to the face.
+	 */
+
+	/* regular dijkstra shortest path, but over faces instead of vertices */
+	heap = BLI_heap_new();
+	BLI_heap_insert(heap, 0.0f, f_src);
+	cost[BM_elem_index_get(f_src)] = 0.0f;
+
+	while ((f = BLI_heap_popmin(heap))) {
+
+		if (f == f_dst)
+			break;
+
+		if (!BM_elem_flag_test(f, BM_ELEM_TAG)) {
+			BM_elem_flag_enable(f, BM_ELEM_TAG);
+			facetag_add_adjacent(heap, f, faces_prev, cost, use_length);
+		}
+	}
+
+	if (f == f_dst) {
+		do {
+			BLI_linklist_prepend(&path, f);
+		} while ((f = faces_prev[BM_elem_index_get(f)]));
+	}
+
+	MEM_freeN(faces_prev);
+	MEM_freeN(cost);
+	BLI_heap_free(heap, NULL);
+
+	return path;
+}
diff --git a/source/blender/bmesh/tools/bmesh_path.h b/source/blender/bmesh/tools/bmesh_path.h
new file mode 100644
index 00000000000..a13290b875e
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_path.h
@@ -0,0 +1,42 @@
+/*
+ * ***** 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):
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_PATH_H__
+#define __BMESH_PATH_H__
+
+/** \file blender/bmesh/tools/bmesh_path.h
+ *  \ingroup bmesh
+ */
+
+struct LinkNode *BM_mesh_calc_path_vert(
+        BMesh *bm, BMVert *v_src, BMVert *v_dst, const bool  use_length,
+        void *user_data, bool (*filter_fn)(BMVert *, void *));
+
+struct LinkNode *BM_mesh_calc_path_edge(
+        BMesh *bm, BMEdge *e_src, BMEdge *e_dst, const bool  use_length,
+        void *user_data, bool (*filter_fn)(BMEdge *, void *));
+
+struct LinkNode *BM_mesh_calc_path_face(
+        BMesh *bm, BMFace *f_src, BMFace *f_dst, const bool  use_length,
+        void *user_data, bool (*test_fn)(BMFace *, void *));
+
+#endif /* __BMESH_PATH_H__ */
diff --git a/source/blender/editors/mesh/CMakeLists.txt b/source/blender/editors/mesh/CMakeLists.txt
index 1fdf97bbbd3..69ef4715df6 100644
--- a/source/blender/editors/mesh/CMakeLists.txt
+++ b/source/blender/editors/mesh/CMakeLists.txt
@@ -47,6 +47,7 @@ set(SRC
 	editmesh_knife.c
 	editmesh_knife_project.c
 	editmesh_loopcut.c
+	editmesh_path.c
 	editmesh_rip.c
 	editmesh_select.c
 	editmesh_tools.c
diff --git a/source/blender/editors/mesh/editmesh_path.c b/source/blender/editors/mesh/editmesh_path.c
new file mode 100644
index 00000000000..6f591c5c8d4
--- /dev/null
+++ b/source/blender/editors/mesh/editmesh_path.c
@@ -0,0 +1,623 @@
+/*
+ * ***** 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.
+ *
+ * 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 *****
+ */
+
+/** \file blender/editors/mesh/editmesh_path.c
+ *  \ingroup edmesh
+ */
+
+#include "DNA_scene_types.h"
+#include "DNA_object_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_windowmanager_types.h"
+
+#include "BLI_math.h"
+#include "BLI_linklist.h"
+
+#include "BKE_context.h"
+#include "BKE_editmesh.h"
+#include "BKE_report.h"
+
+#include "ED_mesh.h"
+#include "ED_screen.h"
+#include "ED_uvedit.h"
+#include "ED_view3d.h"
+
+#include "RNA_access.h"
+#include "RNA_define.h"
+
+#include "WM_types.h"
+
+#include "mesh_intern.h"  /* own include */
+
+struct UserData {
+	BMesh *bm;
+	Mesh  *me;
+	Scene *scene;
+};
+
+/* -------------------------------------------------------------------- */
+/* Vert Path */
+
+/* callbacks */
+static bool verttag_filter_cb(BMVert *v, void *UNUSED(user_data_v))
+{
+	return !BM_elem_flag_test(v, BM_ELEM_HIDDEN);
+}
+static bool verttag_test_cb(BMVert *v, void *UNUSED(user_data_v))
+{
+	return BM_elem_flag_test_bool(v, BM_ELEM_SELECT);
+}
+static void verttag_set_cb(BMVert *v, bool val, void *user_data_v)
+{
+	struct UserData *user_data = user_data_v;
+	BM_vert_select_set(user_data->bm, v, val);
+}
+
+static bool mouse_mesh_shortest_path_vert(ViewContext *vc)
+{
+	/* unlike edge/face versions, this uses a bmesh operator */
+
+	BMEditMesh *em = vc->em;
+	BMVert *v_dst;
+	float dist = 75.0f;
+	const bool use_length = true;
+
+	v_dst = EDBM_vert_find_nearest(vc, &dist, false, false);
+	if (v_dst) {
+		struct UserData user_data = {vc->em->bm, vc->obedit->data, vc->scene};
+		LinkNode *path = NULL;
+
+		if (em->bm->selected.last) {
+			BMEditSelection *ese = em->bm->selected.last;
+
+			if (ese && ese->htype == BM_VERT) {
+				BMVert *v_act;
+				v_act = (BMVert *)ese->ele;
+				if (v_act != v_dst) {
+					if ((path = BM_mesh_calc_path_vert(em->bm, v_act, v_dst, use_length,
+					                                   &user_data, verttag_filter_cb)))
+					{
+						BM_select_history_remove(em->bm, v_act);
+					}
+				}
+			}
+		}
+
+		if (path) {
+			/* toggle the flag */
+			bool all_set = true;
+			LinkNode *node;
+
+			node = path;
+			do {
+				if (!verttag_test_cb((BMVert *)node->link, &user_data)) {
+					all_set = false;
+					break;
+				}
+			} while ((node = node->next));
+
+			node = path;
+			do {
+				verttag_set_cb((BMVert *)node->link, !all_set, &user_data);
+			} while ((node = node->next));
+
+			BLI_linklist_free(path, NULL);
+		}
+		else {
+			const bool is_act = !verttag_test_cb(v_dst, &user_data);
+			verttag_set_cb(v_dst, is_act, &user_data); /* switch the face option */
+		}
+
+		EDBM_selectmode_flush(em);
+
+		/* even if this is selected it may not be in the selection list */
+		if (BM_elem_flag_test(v_dst, BM_ELEM_SELECT) == 0)
+			BM_select_history_remove(em->bm, v_dst);
+		else
+			BM_select_history_store(em->bm, v_dst);
+
+		EDBM_update_generic(em, false, false);
+
+		return true;
+	}
+	else {
+		return false;
+	}
+}
+
+
+
+/* -------------------------------------------------------------------- */
+/* Edge Path */
+
+/* callbacks */
+static bool edgetag_filter_cb(BMEdge *e, void *UNUSED(user_data_v))
+{
+	return !BM_elem_flag_test(e, BM_ELEM_HIDDEN);
+}
+static bool edgetag_test_cb(BMEdge *e, void *user_data_v)
+{
+	struct UserData *user_data = user_data_v;
+	Scene *scene = user_data->scene;
+	BMesh *bm = user_data->bm;
+
+	switch (scene->toolsettings->edge_mode) {
+		case EDGE_MODE_SELECT:
+			return BM_elem_flag_test(e, BM_ELEM_SELECT) ? true : false;
+		case EDGE_MODE_TAG_SEAM:
+			return BM_elem_flag_test(e, BM_ELEM_SEAM) ? false : true;
+		case EDGE_MODE_TAG_SHARP:
+			return BM_elem_flag_test(e, BM_ELEM_SMOOTH) ? false : true;
+		case EDGE_MODE_TAG_CREASE:
+			return BM_elem_float_data_get(&bm->edata, e, CD_CREASE) ? true : false;
+		case EDGE_MODE_TAG_BEVEL:
+			return BM_elem_float_data_get(&bm->edata, e, CD_BWEIGHT) ? true : false;
+#ifdef WITH_FREESTYLE
+		case EDGE_MODE_TAG_FREESTYLE:
+			{
+				FreestyleEdge *fed = CustomData_bmesh_get(&bm->edata, e->head.data, CD_FREESTYLE_EDGE);
+				return (!fed) ? FALSE : (fed->flag & FREESTYLE_EDGE_MARK) ? true : false;
+			}
+			break;
+#endif
+	}
+	return 0;
+}
+static void edgetag_set_cb(BMEdge *e, bool val, void *user_data_v)
+{
+	struct UserData *user_data = user_data_v;
+	Scene *scene = user_data->scene;
+	BMesh *bm = user_data->bm;
+
+	switch (scene->toolsettings->edge_mode) {
+		case EDGE_MODE_SELECT:
+			BM_edge_select_set(bm, e, val);
+			break;
+		case EDGE_MODE_TAG_SEAM:
+			BM_elem_flag_set(e, BM_ELEM_SEAM, val);
+			break;
+		case EDGE_MODE_TAG_SHARP:
+			BM_elem_flag_set(e, BM_ELEM_SMOOTH, !val);
+			break;
+		case EDGE_MODE_TAG_CREASE:
+			BM_elem_float_data_set(&bm->edata, e, CD_CREASE, (val) ? 1.0f : 0.0f);
+			break;
+		case EDGE_MODE_TAG_BEVEL:
+			BM_elem_float_data_set(&bm->edata, e, CD_BWEIGHT, (val) ? 1.0f : 0.0f);
+			break;
+#ifdef WITH_FREESTYLE
+		case EDGE_MODE_TAG_FREESTYLE:
+		{
+			FreestyleEdge *fed;
+			fed = CustomData_bmesh_get(&bm->edata, e->head.data, CD_FREESTYLE_EDGE);
+			if (!val)
+				fed->flag &= ~FREESTYLE_EDGE_MARK;
+			else
+				fed->flag |= FREESTYLE_EDGE_MARK;
+			break;
+		}
+#endif
+	}
+}
+
+static void edgetag_ensure_cd_flag(Scene *scene, Mesh *me)
+{
+	BMesh *bm = me->edit_btmesh->bm;
+
+	switch (scene->toolsettings->edge_mode) {
+		case EDGE_MODE_TAG_CREASE:
+			BM_mesh_cd_flag_ensure(bm, me, ME_CDFLAG_EDGE_CREASE);
+			break;
+		case EDGE_MODE_TAG_BEVEL:
+			BM_mesh_cd_flag_ensure(bm, me, ME_CDFLAG_EDGE_BWEIGHT);
+			break;
+#ifdef WITH_FREESTYLE
+		case EDGE_MODE_TAG_FREESTYLE:
+			if (!CustomData_has_layer(&bm->edata, CD_FREESTYLE_EDGE)) {
+				BM_data_layer_add(bm, &bm->edata, CD_FREESTYLE_EDGE);
+			}
+			break;
+#endif
+		default:
+			break;
+	}
+}
+
+/* mesh shortest path select, uses prev-selected edge */
+
+/* since you want to create paths with multiple selects, it doesn't have extend option */
+static bool mouse_mesh_shortest_path_edge(ViewContext *vc)
+{
+	BMEditMesh *em = vc->em;
+	BMEdge *e_dst;
+	float dist = 75.0f;
+	const bool use_length = true;
+
+	e_dst = EDBM_edge_find_nearest(vc, &dist);
+	if (e_dst) {
+		struct UserData user_data = {vc->em->bm, vc->obedit->data, vc->scene};
+		LinkNode *path = NULL;
+		Mesh *me = vc->obedit->data;
+
+		edgetag_ensure_cd_flag(vc->scene, em->ob->data);
+
+		if (em->bm->selected.last) {
+			BMEditSelection *ese = em->bm->selected.last;
+
+			if (ese && ese->htype == BM_EDGE) {
+				BMEdge *e_act;
+				e_act = (BMEdge *)ese->ele;
+				if (e_act != e_dst) {
+					if ((path = BM_mesh_calc_path_edge(em->bm, e_act, e_dst, use_length,
+					                                   &user_data, edgetag_filter_cb)))
+					{
+						BM_select_history_remove(em->bm, e_act);
+					}
+				}
+			}
+		}
+
+		if (path) {
+			/* toggle the flag */
+			bool all_set = true;
+			LinkNode *node;
+
+			node = path;
+			do {
+				if (!edgetag_test_cb((BMEdge *)node->link, &user_data)) {
+					all_set = false;
+					break;
+				}
+			} while ((node = node->next));
+
+			node = path;
+			do {
+				edgetag_set_cb((BMEdge *)node->link, !all_set, &user_data);
+			} while ((node = node->next));
+
+			BLI_linklist_free(path, NULL);
+		}
+		else {
+			const bool is_act = !edgetag_test_cb(e_dst, &user_data);
+			edgetag_ensure_cd_flag(vc->scene, vc->obedit->data);
+			edgetag_set_cb(e_dst, is_act, &user_data); /* switch the edge option */
+		}
+
+		EDBM_selectmode_flush(em);
+
+		/* even if this is selected it may not be in the selection list */
+		if (edgetag_test_cb(e_dst, &user_data) == 0)
+			BM_select_history_remove(em->bm, e_dst);
+		else
+			BM_select_history_store(em->bm, e_dst);
+
+		/* force drawmode for mesh */
+		switch (vc->scene->toolsettings->edge_mode) {
+
+			case EDGE_MODE_TAG_SEAM:
+				me->drawflag |= ME_DRAWSEAMS;
+				ED_uvedit_live_unwrap(vc->scene, vc->obedit);
+				break;
+			case EDGE_MODE_TAG_SHARP:
+				me->drawflag |= ME_DRAWSHARP;
+				break;
+			case EDGE_MODE_TAG_CREASE:
+				me->drawflag |= ME_DRAWCREASES;
+				break;
+			case EDGE_MODE_TAG_BEVEL:
+				me->drawflag |= ME_DRAWBWEIGHTS;
+				break;
+#ifdef WITH_FREESTYLE
+			case EDGE_MODE_TAG_FREESTYLE:
+				me->drawflag |= ME_DRAW_FREESTYLE_EDGE;
+				break;
+#endif
+		}
+
+		EDBM_update_generic(em, false, false);
+
+		return true;
+	}
+	else {
+		return false;
+	}
+}
+
+
+
+/* -------------------------------------------------------------------- */
+/* Face Path */
+
+/* callbacks */
+static bool facetag_filter_cb(BMFace *f, void *UNUSED(user_data_v))
+{
+	return !BM_elem_flag_test(f, BM_ELEM_HIDDEN);
+}
+//static bool facetag_test_cb(Scene *UNUSED(scene), BMesh *UNUSED(bm), BMFace *f)
+static bool facetag_test_cb(BMFace *f, void *UNUSED(user_data_v))
+{
+	return BM_elem_flag_test_bool(f, BM_ELEM_SELECT);
+}
+//static void facetag_set_cb(BMesh *bm, Scene *UNUSED(scene), BMFace *f, const bool val)
+static void facetag_set_cb(BMFace *f, bool val, void *user_data_v)
+{
+	struct UserData *user_data = user_data_v;
+	BM_face_select_set(user_data->bm, f, val);
+}
+
+static bool mouse_mesh_shortest_path_face(ViewContext *vc)
+{
+	BMEditMesh *em = vc->em;
+	BMFace *f_dst;
+	float dist = 75.0f;
+	const bool use_length = true;
+
+	f_dst = EDBM_face_find_nearest(vc, &dist);
+	if (f_dst) {
+		struct UserData user_data = {vc->em->bm, vc->obedit->data, vc->scene};
+		LinkNode *path = NULL;
+		BMFace *f_act = BM_active_face_get(em->bm, false, true);
+
+		if (f_act) {
+			if (f_act != f_dst) {
+				if ((path = BM_mesh_calc_path_face(em->bm, f_act, f_dst, use_length,
+				                                   &user_data, facetag_filter_cb)))
+				{
+					BM_select_history_remove(em->bm, f_act);
+				}
+			}
+		}
+
+		if (path) {
+			/* toggle the flag */
+			bool all_set = true;
+			LinkNode *node;
+
+			node = path;
+			do {
+				if (!facetag_test_cb((BMFace *)node->link, &user_data)) {
+					all_set = false;
+					break;
+				}
+			} while ((node = node->next));
+
+			node = path;
+			do {
+				facetag_set_cb((BMFace *)node->link, !all_set, &user_data);
+			} while ((node = node->next));
+
+			BLI_linklist_free(path, NULL);
+		}
+		else {
+			const bool is_act = !facetag_test_cb(f_dst, &user_data);
+			facetag_set_cb(f_dst, is_act, &user_data); /* switch the face option */
+		}
+
+		EDBM_selectmode_flush(em);
+
+		/* even if this is selected it may not be in the selection list */
+		if (facetag_test_cb(f_dst, &user_data) == 0)
+			BM_select_history_remove(em->bm, f_dst);
+		else
+			BM_select_history_store(em->bm, f_dst);
+
+		BM_active_face_set(em->bm, f_dst);
+
+		EDBM_update_generic(em, false, false);
+
+		return true;
+	}
+	else {
+		return false;
+	}
+}
+
+
+
+/* -------------------------------------------------------------------- */
+/* Main Operator for vert/edge/face tag */
+
+static int edbm_shortest_path_pick_invoke(bContext *C, wmOperator *UNUSED(op), const wmEvent *event)
+{
+	ViewContext vc;
+	BMEditMesh *em;
+
+	view3d_operator_needs_opengl(C);
+
+	em_setup_viewcontext(C, &vc);
+	copy_v2_v2_int(vc.mval, event->mval);
+	em = vc.em;
+
+	if (em->selectmode & SCE_SELECT_VERTEX) {
+		if (mouse_mesh_shortest_path_vert(&vc)) {
+			return OPERATOR_FINISHED;
+		}
+		else {
+			return OPERATOR_PASS_THROUGH;
+		}
+	}
+	else if (em->selectmode & SCE_SELECT_EDGE) {
+		if (mouse_mesh_shortest_path_edge(&vc)) {
+			return OPERATOR_FINISHED;
+		}
+		else {
+			return OPERATOR_PASS_THROUGH;
+		}
+	}
+	else if (em->selectmode & SCE_SELECT_FACE) {
+		if (mouse_mesh_shortest_path_face(&vc)) {
+			return OPERATOR_FINISHED;
+		}
+		else {
+			return OPERATOR_PASS_THROUGH;
+		}
+	}
+
+	return OPERATOR_PASS_THROUGH;
+}
+
+void MESH_OT_shortest_path_pick(wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name = "Pick Shortest Path";
+	ot->idname = "MESH_OT_shortest_path_pick";
+	ot->description = "Select shortest path between two selections";
+
+	/* api callbacks */
+	ot->invoke = edbm_shortest_path_pick_invoke;
+	ot->poll = ED_operator_editmesh_region_view3d;
+
+	/* flags */
+	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
+
+	/* properties */
+	RNA_def_boolean(ot->srna, "extend", false, "Extend", "Extend the selection");
+}
+
+
+
+/* -------------------------------------------------------------------- */
+/* Select path between existing selection */
+
+static bool ele_filter_visible_cb(BMElem *ele, void *UNUSED(user_data))
+{
+	return !BM_elem_flag_test(ele, BM_ELEM_HIDDEN);
+}
+
+static int edbm_shortest_path_select_exec(bContext *C, wmOperator *op)
+{
+	Object *ob = CTX_data_edit_object(C);
+	BMEditMesh *em = BKE_editmesh_from_object(ob);
+	BMIter iter;
+	BMEditSelection *ese_src, *ese_dst;
+	BMElem *ele_src = NULL, *ele_dst = NULL, *ele;
+
+	const bool use_length = RNA_boolean_get(op->ptr, "use_length");
+
+	/* first try to find vertices in edit selection */
+	ese_src = em->bm->selected.last;
+	if (ese_src && (ese_dst = ese_src->prev) && (ese_src->htype  == ese_dst->htype)) {
+		ele_src = ese_src->ele;
+		ele_dst = ese_dst->ele;
+	}
+	else {
+		/* if selection history isn't available, find two selected elements */
+
+		if ((em->selectmode & SCE_SELECT_VERTEX) && (em->bm->totvertsel >= 2)) {
+			BM_ITER_MESH (ele, &iter, em->bm, BM_VERTS_OF_MESH) {
+				if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
+					if      (ele_src == NULL) ele_src = ele;
+					else if (ele_dst == NULL) ele_dst = ele;
+					else                      break;
+				}
+			}
+		}
+
+		if ((ele_src == NULL) && (em->selectmode & SCE_SELECT_EDGE) && (em->bm->totedgesel >= 2)) {
+			BM_ITER_MESH (ele, &iter, em->bm, BM_EDGES_OF_MESH) {
+				if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
+					if      (ele_src == NULL) ele_src = ele;
+					else if (ele_dst == NULL) ele_dst = ele;
+					else                      break;
+				}
+			}
+		}
+
+		if ((ele_src == NULL) && (em->selectmode & SCE_SELECT_FACE) && (em->bm->totfacesel >= 2)) {
+			BM_ITER_MESH (ele, &iter, em->bm, BM_FACES_OF_MESH) {
+				if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
+					if      (ele_src == NULL) ele_src = ele;
+					else if (ele_dst == NULL) ele_dst = ele;
+					else                      break;
+				}
+			}
+		}
+	}
+
+	if (ele_src && ele_dst) {
+		LinkNode *path = NULL;
+		switch (ele_src->head.htype) {
+			case BM_VERT:
+				path = BM_mesh_calc_path_vert(
+				           em->bm, (BMVert *)ele_src, (BMVert *)ele_dst, use_length,
+				           NULL, (bool (*)(BMVert *, void *))ele_filter_visible_cb);
+				break;
+			case BM_EDGE:
+				path = BM_mesh_calc_path_edge(
+				           em->bm, (BMEdge *)ele_src, (BMEdge *)ele_dst, use_length,
+				           NULL, (bool (*)(BMEdge *, void *))ele_filter_visible_cb);
+				break;
+			case BM_FACE:
+				path = BM_mesh_calc_path_face(
+				           em->bm, (BMFace *)ele_src, (BMFace *)ele_dst, use_length,
+				           NULL, (bool (*)(BMFace *, void *))ele_filter_visible_cb);
+				break;
+		}
+
+		if (path) {
+			LinkNode *node = path;
+
+			do {
+				BM_elem_select_set(em->bm, node->link, true);
+			} while ((node = node->next));
+
+			BLI_linklist_free(path, NULL);
+		}
+		else {
+			BKE_report(op->reports, RPT_WARNING, "Path can't be found");
+			return OPERATOR_CANCELLED;
+		}
+
+		EDBM_selectmode_flush(em);
+		EDBM_update_generic(em, false, false);
+
+		return OPERATOR_FINISHED;
+	}
+	else {
+		BKE_report(op->reports, RPT_WARNING, "Path selection requires two matching elements to be selected");
+		return OPERATOR_CANCELLED;
+	}
+}
+
+void MESH_OT_shortest_path_select(wmOperatorType *ot)
+{
+	/* identifiers */
+	ot->name = "Select Shortest Path";
+	ot->idname = "MESH_OT_shortest_path_select";
+	ot->description = "Selected vertex path between two vertices";
+
+	/* api callbacks */
+	ot->exec = edbm_shortest_path_select_exec;
+	ot->poll = ED_operator_editmesh;
+
+	/* flags */
+	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
+
+	/* properties */
+	RNA_def_boolean(ot->srna, "use_length", true, "Length", "Use length when measuring distance");
+}
diff --git a/source/blender/editors/mesh/editmesh_select.c b/source/blender/editors/mesh/editmesh_select.c
index c2869f80341..996331d2f8c 100644
--- a/source/blender/editors/mesh/editmesh_select.c
+++ b/source/blender/editors/mesh/editmesh_select.c
@@ -32,11 +32,11 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_listbase.h"
+#include "BLI_linklist.h"
 #include "BLI_math.h"
 #include "BLI_rand.h"
 #include "BLI_array.h"
 #include "BLI_smallhash.h"
-#include "BLI_heap.h"
 
 #include "BKE_context.h"
 #include "BKE_displist.h"
@@ -55,13 +55,11 @@
 
 #include "ED_mesh.h"
 #include "ED_screen.h"
-#include "ED_uvedit.h"
 #include "ED_view3d.h"
 
 #include "BIF_gl.h"
 
 #include "DNA_object_types.h"
-#include "DNA_mesh_types.h"
 #include "DNA_meshdata_types.h"
 
 #include "GPU_extensions.h"
@@ -1343,563 +1341,6 @@ void MESH_OT_select_interior_faces(wmOperatorType *ot)
 	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
 }
 
-/* ******************* generic tag_shortest_path and helpers ****************** */
-
-static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3[3])
-{
-	float cost, d1[3], d2[3];
-
-
-	/* The cost is based on the simple sum of the length of the two edgees... */
-	sub_v3_v3v3(d1, v2, v1);
-	sub_v3_v3v3(d2, v3, v2);
-	cost = normalize_v3(d1) + normalize_v3(d2);
-
-	/* but is biased to give higher values to sharp turns, so that it will take
-	 * paths with fewer "turns" when selecting between equal-weighted paths between
-	 * the two edges */
-	cost = cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v3v3(d1, d2)))));
-
-	return cost;
-}
-
-/* ******************* edgetag_shortest_path and helpers ****************** */
-
-static float edgetag_cut_cost(BMEdge *e1, BMEdge *e2, BMVert *v)
-{
-	BMVert *v1 = BM_edge_other_vert(e1, v);
-	BMVert *v2 = BM_edge_other_vert(e2, v);
-	return step_cost_3_v3(v1->co, v->co, v2->co);
-}
-
-static void edgetag_add_adjacent(Heap *heap, BMEdge *e1, BMEdge **edges_prev, float *cost)
-{
-	BMIter viter;
-	BMVert *v;
-
-	BMIter eiter;
-	BMEdge *e2;
-
-	const int e1_index = BM_elem_index_get(e1);
-
-	BM_ITER_ELEM (v, &viter, e1, BM_VERTS_OF_EDGE) {
-		BM_ITER_ELEM (e2, &eiter, v, BM_EDGES_OF_VERT) {
-			if (!BM_elem_flag_test(e2, BM_ELEM_TAG)) {
-				/* we know 'e2' is not visited, check it out! */
-				const int e2_index = BM_elem_index_get(e2);
-				const float cost_cut = edgetag_cut_cost(e1, e2, v);
-				const float cost_new = cost[e1_index] + cost_cut;
-
-				if (cost[e2_index] > cost_new) {
-					cost[e2_index] = cost_new;
-					edges_prev[e2_index] = e1;
-					BLI_heap_insert(heap, cost_new, e2);
-				}
-			}
-		}
-	}
-}
-
-static void edgetag_context_set(BMesh *bm, Scene *scene, BMEdge *e, int val)
-{
-	
-	switch (scene->toolsettings->edge_mode) {
-		case EDGE_MODE_SELECT:
-			BM_edge_select_set(bm, e, val);
-			break;
-		case EDGE_MODE_TAG_SEAM:
-			BM_elem_flag_set(e, BM_ELEM_SEAM, val);
-			break;
-		case EDGE_MODE_TAG_SHARP:
-			BM_elem_flag_set(e, BM_ELEM_SMOOTH, !val);
-			break;
-		case EDGE_MODE_TAG_CREASE:
-			BM_elem_float_data_set(&bm->edata, e, CD_CREASE, (val) ? 1.0f : 0.0f);
-			break;
-		case EDGE_MODE_TAG_BEVEL:
-			BM_elem_float_data_set(&bm->edata, e, CD_BWEIGHT, (val) ? 1.0f : 0.0f);
-			break;
-#ifdef WITH_FREESTYLE
-		case EDGE_MODE_TAG_FREESTYLE:
-		{
-			FreestyleEdge *fed;
-			fed = CustomData_bmesh_get(&bm->edata, e->head.data, CD_FREESTYLE_EDGE);
-			if (!val)
-				fed->flag &= ~FREESTYLE_EDGE_MARK;
-			else
-				fed->flag |= FREESTYLE_EDGE_MARK;
-			break;
-		}
-#endif
-	}
-}
-
-static int edgetag_context_check(Scene *scene, BMesh *bm, BMEdge *e)
-{
-	switch (scene->toolsettings->edge_mode) {
-		case EDGE_MODE_SELECT:
-			return BM_elem_flag_test(e, BM_ELEM_SELECT) ? true : false;
-		case EDGE_MODE_TAG_SEAM:
-			return BM_elem_flag_test(e, BM_ELEM_SEAM);
-		case EDGE_MODE_TAG_SHARP:
-			return !BM_elem_flag_test(e, BM_ELEM_SMOOTH);
-		case EDGE_MODE_TAG_CREASE:
-			return BM_elem_float_data_get(&bm->edata, e, CD_CREASE) ? true : false;
-		case EDGE_MODE_TAG_BEVEL:
-			return BM_elem_float_data_get(&bm->edata, e, CD_BWEIGHT) ? true : false;
-#ifdef WITH_FREESTYLE
-		case EDGE_MODE_TAG_FREESTYLE:
-			{
-				FreestyleEdge *fed = CustomData_bmesh_get(&bm->edata, e->head.data, CD_FREESTYLE_EDGE);
-				return (!fed) ? FALSE : (fed->flag & FREESTYLE_EDGE_MARK) ? TRUE : FALSE;
-			}
-			break;
-#endif
-	}
-	return 0;
-}
-
-static void edgetag_ensure_cd_flag(Scene *scene, Mesh *me)
-{
-	BMesh *bm = me->edit_btmesh->bm;
-
-	switch (scene->toolsettings->edge_mode) {
-		case EDGE_MODE_TAG_CREASE:
-			BM_mesh_cd_flag_ensure(bm, me, ME_CDFLAG_EDGE_CREASE);
-			break;
-		case EDGE_MODE_TAG_BEVEL:
-			BM_mesh_cd_flag_ensure(bm, me, ME_CDFLAG_EDGE_BWEIGHT);
-			break;
-#ifdef WITH_FREESTYLE
-		case EDGE_MODE_TAG_FREESTYLE:
-			if (!CustomData_has_layer(&bm->edata, CD_FREESTYLE_EDGE)) {
-				BM_data_layer_add(bm, &bm->edata, CD_FREESTYLE_EDGE);
-			}
-			break;
-#endif
-		default:
-			break;
-	}
-}
-
-static int edgetag_shortest_path(Scene *scene, BMesh *bm, BMEdge *e_src, BMEdge *e_dst)
-{
-	/* BM_ELEM_TAG flag is used to store visited edges */
-	BMEdge *e;
-	BMIter eiter;
-	Heap *heap;
-	float *cost;
-	BMEdge **edges_prev;
-	int i, totedge;
-
-	/* note, would pass BM_EDGE except we are looping over all edges anyway */
-	BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */);
-
-	edgetag_ensure_cd_flag(scene, OBACT->data);
-
-	BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
-		if (BM_elem_flag_test(e, BM_ELEM_HIDDEN) == false) {
-			BM_elem_flag_disable(e, BM_ELEM_TAG);
-		}
-		else {
-			BM_elem_flag_enable(e, BM_ELEM_TAG);
-		}
-
-		BM_elem_index_set(e, i); /* set_inline */
-	}
-	bm->elem_index_dirty &= ~BM_EDGE;
-
-	/* alloc */
-	totedge = bm->totedge;
-	edges_prev = MEM_callocN(sizeof(*edges_prev) * totedge, "SeamPathPrevious");
-	cost = MEM_mallocN(sizeof(*cost) * totedge, "SeamPathCost");
-
-	fill_vn_fl(cost, totedge, 1e20f);
-
-	/*
-	 * Arrays are now filled as follows:
-	 *
-	 * As the search continues, prevedge[n] will be the previous edge on the shortest
-	 * path found so far to edge n. The visitedhash will of course contain entries
-	 * for edges that have been visited, cost[n] will contain the length of the shortest
-	 * path to edge n found so far, Finally, heap is a priority heap which is built on the
-	 * the same data as the cost array, but inverted: it is a worklist of edges prioritized
-	 * by the shortest path found so far to the edge.
-	 */
-
-	/* regular dijkstra shortest path, but over edges instead of vertices */
-	heap = BLI_heap_new();
-	BLI_heap_insert(heap, 0.0f, e_src);
-	cost[BM_elem_index_get(e_src)] = 0.0f;
-
-	e = NULL;
-
-	while (!BLI_heap_is_empty(heap)) {
-		e = BLI_heap_popmin(heap);
-
-		if (e == e_dst)
-			break;
-
-		if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
-			BM_elem_flag_enable(e, BM_ELEM_TAG);
-			edgetag_add_adjacent(heap, e, edges_prev, cost);
-		}
-	}
-	
-	if (e == e_dst) {
-		bool all_set = true;
-
-		/* Check whether the path is already completely tagged.
-		 * if it is, the tags will be cleared instead of set. */
-		e = e_dst;
-		do {
-			if (!edgetag_context_check(scene, bm, e)) {
-				all_set = false;
-				break;
-			}
-		} while ((e = edges_prev[BM_elem_index_get(e)]));
-
-		/* Follow path back and source and add or remove tags */
-		e = e_dst;
-		do {
-			edgetag_context_set(bm, scene, e, !all_set);
-		} while ((e = edges_prev[BM_elem_index_get(e)]));
-	}
-
-	MEM_freeN(edges_prev);
-	MEM_freeN(cost);
-	BLI_heap_free(heap, NULL);
-
-	return 1;
-}
-
-/* ******************* mesh shortest path select, uses prev-selected edge ****************** */
-
-/* since you want to create paths with multiple selects, it doesn't have extend option */
-static int mouse_mesh_shortest_path_edge(ViewContext *vc)
-{
-	BMEditMesh *em = vc->em;
-	BMEdge *e_dst;
-	float dist = 75.0f;
-	
-	e_dst = EDBM_edge_find_nearest(vc, &dist);
-	if (e_dst) {
-		Mesh *me = vc->obedit->data;
-		bool is_path = false;
-		
-		if (em->bm->selected.last) {
-			BMEditSelection *ese = em->bm->selected.last;
-			
-			if (ese && ese->htype == BM_EDGE) {
-				BMEdge *e_act;
-				e_act = (BMEdge *)ese->ele;
-				if (e_act != e_dst) {
-					if (edgetag_shortest_path(vc->scene, em->bm, e_act, e_dst)) {
-						BM_select_history_remove(em->bm, e_act);
-						is_path = true;
-					}
-				}
-			}
-		}
-		if (is_path == false) {
-			int act = (edgetag_context_check(vc->scene, em->bm, e_dst) == 0);
-			edgetag_ensure_cd_flag(vc->scene, vc->obedit->data);
-			edgetag_context_set(em->bm, vc->scene, e_dst, act); /* switch the edge option */
-		}
-		
-		EDBM_selectmode_flush(em);
-
-		/* even if this is selected it may not be in the selection list */
-		if (edgetag_context_check(vc->scene, em->bm, e_dst) == 0)
-			BM_select_history_remove(em->bm, e_dst);
-		else
-			BM_select_history_store(em->bm, e_dst);
-	
-		/* force drawmode for mesh */
-		switch (vc->scene->toolsettings->edge_mode) {
-			
-			case EDGE_MODE_TAG_SEAM:
-				me->drawflag |= ME_DRAWSEAMS;
-				ED_uvedit_live_unwrap(vc->scene, vc->obedit);
-				break;
-			case EDGE_MODE_TAG_SHARP:
-				me->drawflag |= ME_DRAWSHARP;
-				break;
-			case EDGE_MODE_TAG_CREASE:
-				me->drawflag |= ME_DRAWCREASES;
-				break;
-			case EDGE_MODE_TAG_BEVEL:
-				me->drawflag |= ME_DRAWBWEIGHTS;
-				break;
-#ifdef WITH_FREESTYLE
-			case EDGE_MODE_TAG_FREESTYLE:
-				me->drawflag |= ME_DRAW_FREESTYLE_EDGE;
-				break;
-#endif
-		}
-		
-		EDBM_update_generic(em, false, false);
-
-		return true;
-	}
-	else {
-		return false;
-	}
-}
-
-
-/* ******************* facetag_shortest_path and helpers ****************** */
-
-
-static float facetag_cut_cost(BMFace *f1, BMFace *f2, BMEdge *e)
-{
-	float f1_cent[3];
-	float f2_cent[3];
-	float e_cent[3];
-
-	BM_face_calc_center_mean(f1, f1_cent);
-	BM_face_calc_center_mean(f2, f2_cent);
-	mid_v3_v3v3(e_cent, e->v1->co, e->v2->co);
-
-	return step_cost_3_v3(f1_cent, e_cent, f2_cent);
-}
-
-static void facetag_add_adjacent(Heap *heap, BMFace *f1, BMFace **faces_prev, float *cost)
-{
-	BMIter liter;
-	BMLoop *l2;
-	BMFace *f2;
-
-	const int f1_index = BM_elem_index_get(f1);
-
-	/* loop over faces of face, but do so by first looping over loops */
-	BM_ITER_ELEM (l2, &liter, f1, BM_LOOPS_OF_FACE) {
-		BMLoop *l_first;
-		BMLoop *l_iter;
-
-		l_iter = l_first = l2;
-		do {
-			f2 = l_iter->f;
-			if (!BM_elem_flag_test(f2, BM_ELEM_TAG)) {
-				/* we know 'f2' is not visited, check it out! */
-				const int f2_index = BM_elem_index_get(f2);
-				const float cost_cut = facetag_cut_cost(f1, f2, l_iter->e);
-				const float cost_new = cost[f1_index] + cost_cut;
-
-				if (cost[f2_index] > cost_new) {
-					cost[f2_index] = cost_new;
-					faces_prev[f2_index] = f1;
-					BLI_heap_insert(heap, cost_new, f2);
-				}
-			}
-		} while ((l_iter = l_iter->radial_next) != l_first);
-	}
-}
-
-static void facetag_context_set(BMesh *bm, Scene *UNUSED(scene), BMFace *f, int val)
-{
-	BM_face_select_set(bm, f, val);
-}
-
-static int facetag_context_check(Scene *UNUSED(scene), BMesh *UNUSED(bm), BMFace *f)
-{
-	return BM_elem_flag_test(f, BM_ELEM_SELECT) ? 1 : 0;
-}
-
-static int facetag_shortest_path(Scene *scene, BMesh *bm, BMFace *f_src, BMFace *f_dst)
-{
-	/* BM_ELEM_TAG flag is used to store visited edges */
-	BMFace *f;
-	BMIter fiter;
-	Heap *heap;
-	float *cost;
-	BMFace **faces_prev;
-	int i, totface;
-
-	/* note, would pass BM_EDGE except we are looping over all faces anyway */
-	// 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 (BM_elem_flag_test(f, BM_ELEM_HIDDEN) == false) {
-			BM_elem_flag_disable(f, BM_ELEM_TAG);
-		}
-		else {
-			BM_elem_flag_enable(f, BM_ELEM_TAG);
-		}
-
-		BM_elem_index_set(f, i); /* set_inline */
-	}
-	bm->elem_index_dirty &= ~BM_FACE;
-
-	/* alloc */
-	totface = bm->totface;
-	faces_prev = MEM_callocN(sizeof(*faces_prev) * totface, "SeamPathPrevious");
-	cost = MEM_mallocN(sizeof(*cost) * totface, "SeamPathCost");
-
-	fill_vn_fl(cost, totface, 1e20f);
-
-	/*
-	 * Arrays are now filled as follows:
-	 *
-	 * As the search continues, faces_prev[n] will be the previous face on the shortest
-	 * path found so far to face n. The visitedhash will of course contain entries
-	 * for faces that have been visited, cost[n] will contain the length of the shortest
-	 * path to face n found so far, Finally, heap is a priority heap which is built on the
-	 * the same data as the cost array, but inverted: it is a worklist of faces prioritized
-	 * by the shortest path found so far to the face.
-	 */
-
-	/* regular dijkstra shortest path, but over faces instead of vertices */
-	heap = BLI_heap_new();
-	BLI_heap_insert(heap, 0.0f, f_src);
-	cost[BM_elem_index_get(f_src)] = 0.0f;
-
-	f = NULL;
-
-	while (!BLI_heap_is_empty(heap)) {
-		f = BLI_heap_popmin(heap);
-
-		if (f == f_dst)
-			break;
-
-		if (!BM_elem_flag_test(f, BM_ELEM_TAG)) {
-			BM_elem_flag_enable(f, BM_ELEM_TAG);
-			facetag_add_adjacent(heap, f, faces_prev, cost);
-		}
-	}
-
-	if (f == f_dst) {
-		bool all_set = true;
-
-		/* Check whether the path is already completely tagged.
-		 * if it is, the tags will be cleared instead of set. */
-		f = f_dst;
-		do {
-			if (!facetag_context_check(scene, bm, f)) {
-				all_set = false;
-				break;
-			}
-		} while ((f = faces_prev[BM_elem_index_get(f)]));
-
-		/* Follow path back and source and add or remove tags */
-		f = f_dst;
-		do {
-			facetag_context_set(bm, scene, f, !all_set);
-		} while ((f = faces_prev[BM_elem_index_get(f)]));
-	}
-
-	MEM_freeN(faces_prev);
-	MEM_freeN(cost);
-	BLI_heap_free(heap, NULL);
-
-	return 1;
-}
-
-static int mouse_mesh_shortest_path_face(ViewContext *vc)
-{
-	BMEditMesh *em = vc->em;
-	BMFace *f_dst;
-	float dist = 75.0f;
-
-	f_dst = EDBM_face_find_nearest(vc, &dist);
-	if (f_dst) {
-		int path = 0;
-		BMFace *f_act = BM_active_face_get(em->bm, false, true);
-
-		if (f_act) {
-			if (f_act != f_dst) {
-				if (facetag_shortest_path(vc->scene, em->bm, f_act, f_dst)) {
-					BM_select_history_remove(em->bm, f_act);
-					path = 1;
-				}
-			}
-		}
-		if (path == 0) {
-			int act = (facetag_context_check(vc->scene, em->bm, f_dst) == 0);
-			facetag_context_set(em->bm, vc->scene, f_dst, act); /* switch the face option */
-		}
-
-		EDBM_selectmode_flush(em);
-
-		/* even if this is selected it may not be in the selection list */
-		if (facetag_context_check(vc->scene, em->bm, f_dst) == 0)
-			BM_select_history_remove(em->bm, f_dst);
-		else
-			BM_select_history_store(em->bm, f_dst);
-
-		BM_active_face_set(em->bm, f_dst);
-
-		EDBM_update_generic(em, false, false);
-
-		return true;
-	}
-	else {
-		return false;
-	}
-}
-
-
-/* ******************* operator for edge and face tag ****************** */
-
-static int edbm_shortest_path_select_invoke(bContext *C, wmOperator *UNUSED(op), const wmEvent *event)
-{
-	ViewContext vc;
-	BMEditMesh *em;
-
-	view3d_operator_needs_opengl(C);
-
-	em_setup_viewcontext(C, &vc);
-	vc.mval[0] = event->mval[0];
-	vc.mval[1] = event->mval[1];
-	em = vc.em;
-
-	if (em->selectmode & SCE_SELECT_EDGE) {
-		if (mouse_mesh_shortest_path_edge(&vc)) {
-			return OPERATOR_FINISHED;
-		}
-		else {
-			return OPERATOR_PASS_THROUGH;
-		}
-	}
-	else if (em->selectmode & SCE_SELECT_FACE) {
-		if (mouse_mesh_shortest_path_face(&vc)) {
-			return OPERATOR_FINISHED;
-		}
-		else {
-			return OPERATOR_PASS_THROUGH;
-		}
-	}
-
-	return OPERATOR_PASS_THROUGH;
-}
-
-static int edbm_shortest_path_select_poll(bContext *C)
-{
-	if (ED_operator_editmesh_region_view3d(C)) {
-		Object *obedit = CTX_data_edit_object(C);
-		BMEditMesh *em = BKE_editmesh_from_object(obedit);
-		return (em->selectmode & (SCE_SELECT_EDGE | SCE_SELECT_FACE)) != 0;
-	}
-	return 0;
-}
-
-void MESH_OT_select_shortest_path(wmOperatorType *ot)
-{
-	/* identifiers */
-	ot->name = "Shortest Path Select";
-	ot->idname = "MESH_OT_select_shortest_path";
-	ot->description = "Select shortest path between two selections";
-	
-	/* api callbacks */
-	ot->invoke = edbm_shortest_path_select_invoke;
-	ot->poll = edbm_shortest_path_select_poll;
-	
-	/* flags */
-	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
-	
-	/* properties */
-	RNA_def_boolean(ot->srna, "extend", false, "Extend", "Extend the selection");
-}
 
 /* ************************************************** */
 /* here actual select happens */
@@ -3758,116 +3199,4 @@ void MESH_OT_loop_to_region(wmOperatorType *ot)
 }
 
 
-/************************ Vertex Path Operator *************************/
-
-typedef struct PathNode {
-	/* int u; */       /* UNUSED */
-	/* int visited; */ /* UNUSED */
-	ListBase edges;
-} PathNode;
-
-typedef struct PathEdge {
-	struct PathEdge *next, *prev;
-	int v;
-	float w;
-} PathEdge;
-
-static int edbm_select_vertex_path_exec(bContext *C, wmOperator *op)
-{
-	Object *ob = CTX_data_edit_object(C);
-	BMEditMesh *em = BKE_editmesh_from_object(ob);
-	BMOperator bmop;
-	BMIter iter;
-	BMVert *eve = NULL, *svert = NULL, *evert = NULL;
-	BMEditSelection *sv, *ev;
-
-	/* get the type from RNA */
-	const int type = RNA_enum_get(op->ptr, "type");
-
-	/* first try to find vertices in edit selection */
-	sv = em->bm->selected.last;
-	if (sv != NULL) {
-		ev = sv->prev;
-
-		if (ev && (sv->htype == BM_VERT) && (ev->htype == BM_VERT)) {
-			svert = (BMVert *)sv->ele;
-			evert = (BMVert *)ev->ele;
-		}
-	}
-
-	/* if those are not found, because vertices where selected by e.g.
-	 * border or circle select, find two selected vertices */
-	if (svert == NULL) {
-		BM_ITER_MESH (eve, &iter, em->bm, BM_VERTS_OF_MESH) {
-			if (!BM_elem_flag_test(eve, BM_ELEM_SELECT) || BM_elem_flag_test(eve, BM_ELEM_HIDDEN))
-				continue;
-
-			if (svert == NULL) {
-				svert = eve;
-			}
-			else if (evert == NULL) {
-				evert = eve;
-			}
-			else {
-				/* more than two vertices are selected,
-				 * show warning message and cancel operator */
-				svert = evert = NULL;
-				break;
-			}
-		}
-	}
-
-	if (svert == NULL || evert == NULL) {
-		BKE_report(op->reports, RPT_WARNING, "Path selection requires two vertices to be selected");
-		return OPERATOR_CANCELLED;
-	}
-
-	/* initialize the bmop using EDBM api, which does various ui error reporting and other stuff */
-	EDBM_op_init(em, &bmop, op,
-	             "shortest_path vert_start=%e vert_end=%e type=%i",
-	             svert, evert, type);
-
-	/* execute the operator */
-	BMO_op_exec(em->bm, &bmop);
-
-	/* DO NOT clear the existing selection */
-	/* EDBM_flag_disable_all(em, BM_ELEM_SELECT); */
-
-	/* select the output */
-	BMO_slot_buffer_hflag_enable(em->bm, bmop.slots_out, "verts.out", BM_VERT, BM_ELEM_SELECT, true);
-
-	/* finish the operator */
-	if (!EDBM_op_finish(em, &bmop, op, true)) {
-		return OPERATOR_CANCELLED;
-	}
-
-	EDBM_selectmode_flush(em);
-
-	EDBM_update_generic(em, false, false);
-
-	return OPERATOR_FINISHED;
-}
-
-void MESH_OT_select_vertex_path(wmOperatorType *ot)
-{
-	static const EnumPropertyItem type_items[] = {
-		{VPATH_SELECT_EDGE_LENGTH, "EDGE_LENGTH", 0, "Edge Length", NULL},
-		{VPATH_SELECT_TOPOLOGICAL, "TOPOLOGICAL", 0, "Topological", NULL},
-		{0, NULL, 0, NULL, NULL}
-	};
-
-	/* identifiers */
-	ot->name = "Select Vertex Path";
-	ot->idname = "MESH_OT_select_vertex_path";
-	ot->description = "Selected vertex path between two vertices";
-
-	/* api callbacks */
-	ot->exec = edbm_select_vertex_path_exec;
-	ot->poll = ED_operator_editmesh;
-
-	/* flags */
-	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
-
-	/* properties */
-	RNA_def_enum(ot->srna, "type", type_items, VPATH_SELECT_EDGE_LENGTH, "Type", "Method to compute distance");
-}
+/************************ Select Path Operator *************************/
diff --git a/source/blender/editors/mesh/mesh_intern.h b/source/blender/editors/mesh/mesh_intern.h
index 59238ff0baa..2102ede2672 100644
--- a/source/blender/editors/mesh/mesh_intern.h
+++ b/source/blender/editors/mesh/mesh_intern.h
@@ -112,7 +112,7 @@ void MESH_OT_inset(struct wmOperatorType *ot);
 
 /* *** editmesh_knife.c *** */
 void MESH_OT_knife_tool(struct wmOperatorType *ot);
-void MESH_OT_knife_project(wmOperatorType *ot);
+void MESH_OT_knife_project(struct wmOperatorType *ot);
 void EDBM_mesh_knife(struct bContext *C, struct LinkNode *polys, bool use_tag);
 
 struct wmKeyMap *knifetool_modal_keymap(struct wmKeyConfig *keyconf);
@@ -134,7 +134,7 @@ void MESH_OT_loop_select(struct wmOperatorType *ot);
 void MESH_OT_edgering_select(struct wmOperatorType *ot);
 void MESH_OT_select_all(struct wmOperatorType *ot);
 void MESH_OT_select_interior_faces(struct wmOperatorType *ot);
-void MESH_OT_select_shortest_path(struct wmOperatorType *ot);
+void MESH_OT_shortest_path_pick(struct wmOperatorType *ot);
 void MESH_OT_select_linked(struct wmOperatorType *ot);
 void MESH_OT_select_linked_pick(struct wmOperatorType *ot);
 void MESH_OT_select_face_by_sides(struct wmOperatorType *ot);
@@ -152,7 +152,7 @@ void MESH_OT_select_axis(struct wmOperatorType *ot);
 void MESH_OT_select_next_loop(struct wmOperatorType *ot);
 void MESH_OT_region_to_loop(struct wmOperatorType *ot);
 void MESH_OT_loop_to_region(struct wmOperatorType *ot);
-void MESH_OT_select_vertex_path(struct wmOperatorType *ot);
+void MESH_OT_shortest_path_select(struct wmOperatorType *ot);
 
 extern struct EnumPropertyItem *corner_type_items;
 
diff --git a/source/blender/editors/mesh/mesh_ops.c b/source/blender/editors/mesh/mesh_ops.c
index cca9b9b9f2d..307377a8aa6 100644
--- a/source/blender/editors/mesh/mesh_ops.c
+++ b/source/blender/editors/mesh/mesh_ops.c
@@ -88,7 +88,7 @@ void ED_operatortypes_mesh(void)
 	WM_operatortype_append(MESH_OT_split);
 	WM_operatortype_append(MESH_OT_extrude_repeat);
 	WM_operatortype_append(MESH_OT_edge_rotate);
-	WM_operatortype_append(MESH_OT_select_vertex_path);
+	WM_operatortype_append(MESH_OT_shortest_path_select);
 	WM_operatortype_append(MESH_OT_loop_to_region);
 	WM_operatortype_append(MESH_OT_region_to_loop);
 	WM_operatortype_append(MESH_OT_select_axis);
@@ -122,7 +122,7 @@ void ED_operatortypes_mesh(void)
 	WM_operatortype_append(MESH_OT_dupli_extrude_cursor);
 	WM_operatortype_append(MESH_OT_loop_select);
 	WM_operatortype_append(MESH_OT_edge_face_add);
-	WM_operatortype_append(MESH_OT_select_shortest_path);
+	WM_operatortype_append(MESH_OT_shortest_path_pick);
 	WM_operatortype_append(MESH_OT_select_similar);
 	WM_operatortype_append(MESH_OT_select_mode);
 	WM_operatortype_append(MESH_OT_loop_multi_select);
@@ -297,7 +297,7 @@ void ED_keymap_mesh(wmKeyConfig *keyconf)
 	RNA_boolean_set(kmi->ptr, "deselect", false);
 	RNA_boolean_set(kmi->ptr, "toggle", true);
 
-	WM_keymap_add_item(keymap, "MESH_OT_select_shortest_path", SELECTMOUSE, KM_PRESS, KM_CTRL, 0);
+	WM_keymap_add_item(keymap, "MESH_OT_shortest_path_pick", SELECTMOUSE, KM_PRESS, KM_CTRL, 0);
 
 	kmi = WM_keymap_add_item(keymap, "MESH_OT_select_all", AKEY, KM_PRESS, 0, 0);
 	RNA_enum_set(kmi->ptr, "action", SEL_TOGGLE);
diff --git a/source/blender/makesrna/intern/rna_scene.c b/source/blender/makesrna/intern/rna_scene.c
index 68a5e9ebb12..ec672522a76 100644
--- a/source/blender/makesrna/intern/rna_scene.c
+++ b/source/blender/makesrna/intern/rna_scene.c
@@ -1869,7 +1869,7 @@ static void rna_def_tool_settings(BlenderRNA  *brna)
 	RNA_def_property_float_sdna(prop, NULL, "vgroup_weight");
 	RNA_def_property_ui_text(prop, "Vertex Group Weight", "Weight to assign in vertex groups");
 
-	/* use with MESH_OT_select_shortest_path */
+	/* use with MESH_OT_shortest_path_pick */
 	prop = RNA_def_property(srna, "edge_path_mode", PROP_ENUM, PROP_NONE);
 	RNA_def_property_enum_sdna(prop, NULL, "edge_mode");
 	RNA_def_property_enum_items(prop, edge_tag_items);