[Bf-blender-cvs] [ecc37c7] soc-2016-uv_tools: WIP: Select shortest path - Computing the shortest path using regular Dijkstra algorithm

[Phil Gosch]

Commit: ecc37c77f8274ea37523f20a41f5958c5c5bd94a
Author: Phil Gosch
Date:   Thu Jun 2 11:44:55 2016 +0200
Branches: soc-2016-uv_tools
https://developer.blender.org/rBecc37c77f8274ea37523f20a41f5958c5c5bd94a

WIP: Select shortest path - Computing the shortest path using regular Dijkstra algorithm

===================================================================

M	source/blender/editors/uvedit/uvedit_parametrizer.c
M	source/blender/editors/uvedit/uvedit_parametrizer.h
M	source/blender/editors/uvedit/uvedit_unwrap_ops.c

===================================================================

diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.c b/source/blender/editors/uvedit/uvedit_parametrizer.c
index 81cbe56..eb8f595 100644
--- a/source/blender/editors/uvedit/uvedit_parametrizer.c
+++ b/source/blender/editors/uvedit/uvedit_parametrizer.c
@@ -34,6 +34,7 @@
 #include "BLI_heap.h"
 #include "BLI_boxpack2d.h"
 #include "BLI_convexhull2d.h"
+#include "BLI_linklist.h"
 
 #include "uvedit_parametrizer.h"
 
@@ -4705,9 +4706,134 @@ void param_scale_bounds(ParamHandle *handle)
 	}
 }
 
-void param_shortest_path(ParamHandle *handle)
+void p_verttag_add_adjacent(Heap *heap, PChart *chart, PVert *v_a, PVert **v_prev, float *cost)
 {
-	/* TODO (SaphireS): Shortest Path computation here */
+	const int v_a_index = v_a->u.id;
+	PEdge *e;
+	e = v_a->edge->next;
+
+	do {
+		PVert *v_b = e->vert; 
+
+		if (!(v_b->flag & PVERT_MARKED)) {
+			/* v_b not visited yet, check it out! */
+			const int v_b_index = v_b->u.id;
+			const float cost_cut = len_v2v2(v_a->uv, v_b->uv); /* params->use_topology_distance ? 1.0f : len_v2v2(v_a->uv, v_b->uv); */
+			const float cost_new = cost[v_a_index] + cost_cut;
+
+			if (cost[v_b_index] > cost_new) {
+				cost[v_b_index] = cost_new;
+				v_prev[v_b_index] = v_a;
+				BLI_heap_insert(heap, cost_new, v_b);
+			}
+		}
+
+		e = p_wheel_edge_next(e);
+	} while (e && (e != v_a->edge));
+}
+
+LinkNode* p_calc_path_vert(PChart *chart, PVert *src, PVert *dst)
+{
+	LinkNode *path = NULL;
+	Heap *heap;
+	PVert *vert;
+	PVert **verts_prev;
+	float *cost;
+	int totvert, index;
+
+	/* Clear flags */
+	for (vert = chart->verts, index = 0; vert; vert = vert->nextlink, index++) {
+		vert->flag &= ~PVERT_MARKED;
+		vert->u.id = index; /* Abuse lscm id field */
+	}
+
+	//src->flag &= ~PVERT_MARKED;
+	//printf(" src unmarked, index: %i \n", src->u.id);
+	//dst->flag &= ~PVERT_MARKED;
+	//printf(" src unmarked, index: %i \n", dst->u.id);
+
+	/* alloc */
+	totvert = chart->nverts;
+	verts_prev = MEM_callocN(sizeof(*verts_prev) * totvert, __func__);
+	cost = MEM_mallocN(sizeof(*cost) * totvert, __func__);
+
+	copy_vn_fl(cost, totvert, 1e20f);
+
+	/* regular dijkstra shortest path */
+	heap = BLI_heap_new();
+	BLI_heap_insert(heap, 0.0f, src);
+	cost[src->u.id] = 0.0f;
+
+	while (!BLI_heap_is_empty(heap)) {
+		vert = BLI_heap_popmin(heap);
+
+		if (vert == dst) {
+			break;
+		}		
+
+		if (!(vert->flag & PVERT_MARKED)) {
+			vert->flag |= PVERT_MARKED;
+			p_verttag_add_adjacent(heap, chart, vert, verts_prev, cost);
+		}
+	}
+
+	if (vert == dst) {
+		do {
+			BLI_linklist_prepend(&path, vert);
+		} while (vert = verts_prev[vert->u.id]);
+	}
+
+	MEM_freeN(verts_prev);
+	MEM_freeN(cost);
+	BLI_heap_free(heap, NULL);
+
+	return path;
+}
+
+void param_shortest_path(ParamHandle *handle, bool *p_found)
+{
+	PHandle *phandle = (PHandle *)handle;
+	PChart *chart, *current_chart;
+	PVert *v, *vert_src = NULL, *vert_dst = NULL;
+	int i, j;
+	bool success = false;
+
+	if (phandle->ncharts == 0)
+		return;
+
+	/* Get src and dst */
+	for (i = 0; i < phandle->ncharts; i++) {
+		chart = phandle->charts[i];
+
+		for (v = chart->verts; v; v = v->nextlink) {
+
+			if (v->flag & PVERT_SELECT) {
+
+				if (vert_src == NULL) {
+					vert_src = v;
+					current_chart = chart;
+				}
+				else if (vert_dst == NULL) {
+					if (current_chart == chart) {
+						vert_dst = v;
+					}
+				}
+			}
+		}
+	}
+
+	/* Connect src and dst */
+
+	LinkNode* path = NULL;
+	if (vert_src && vert_dst){
+		path = p_calc_path_vert(current_chart, vert_src, vert_dst);
+		if (path) {
+			/* TODO (SaphireS): Set *_SELECT tag for verts/edges */
+			success = true;
+		}
+	}
+
+	*p_found = success;
 }
 
 void param_flush(ParamHandle *handle)
diff --git a/source/blender/editors/uvedit/uvedit_parametrizer.h b/source/blender/editors/uvedit/uvedit_parametrizer.h
index 7f0a77e..2ce7fe1 100644
--- a/source/blender/editors/uvedit/uvedit_parametrizer.h
+++ b/source/blender/editors/uvedit/uvedit_parametrizer.h
@@ -115,7 +115,7 @@ void param_scale_bounds(ParamHandle *handle);
 
 /* Select shortest Path */
 
-void param_shortest_path(ParamHandle *handle);
+void param_shortest_path(ParamHandle *handle, bool *p_found);
 
 /* Flushing */
 
diff --git a/source/blender/editors/uvedit/uvedit_unwrap_ops.c b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
index aff3136..3aefb61 100644
--- a/source/blender/editors/uvedit/uvedit_unwrap_ops.c
+++ b/source/blender/editors/uvedit/uvedit_unwrap_ops.c
@@ -716,11 +716,12 @@ void UV_OT_minimize_stretch(wmOperatorType *ot)
 bool ED_uvedit_shortest_path_select(Scene *scene, Object *ob, BMesh *bm) 
 {
 	ParamHandle *handle;
+	bool path_found = false;
 	handle = construct_param_handle(scene, ob, bm, false, false, false, true);
-	param_shortest_path(handle);
+	param_shortest_path(handle, &path_found);
 	param_flush(handle);
 	param_delete(handle);
-	return true; /* TODO (SaphireS): WIP Code, return true only if a valid path was found*/
+	return path_found; /* TODO (SaphireS): WIP Code, return true only if a valid path was found*/
 }
 
 /* ******************** Pack Islands operator **************** */