[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [49569] branches/soc-2012-bratwurst/source /blender/editors/uvedit: Isomap Unwrapper

[Antony Riakiotakis]

Revision: 49569
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=49569
Author:   psy-fi
Date:     2012-08-05 02:34:31 +0000 (Sun, 05 Aug 2012)
Log Message:
-----------
Isomap Unwrapper
=================
* Fix, pass squares of distances to eigen solver
* Use a heap instead of a stack to get the next vertex to iterate
through in Dijkstra graph search algorithm. This is needed because we
may follow a non-optimal path and not get the nearest path between
vertices. This introduces the O(n*log(n)) performance (was more like
simply O(n) till now, but unfortunately, it was incorrect).

Modified Paths:
--------------
    branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer.c
    branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer_isomap.cpp

Modified: branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer.c
===================================================================
--- branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer.c	2012-08-05 01:50:08 UTC (rev 49568)
+++ branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer.c	2012-08-05 02:34:31 UTC (rev 49569)
@@ -3072,6 +3072,8 @@
 
 static PBool p_chart_lscm_solve(PHandle *handle, PChart *chart)
 {
+
+	//#define OLD_DIST_CONSTRUCTION
 	enum UnwrapMethods method = handle->method;
 
 	if (method == UNWRAP_ISOMAP) {
@@ -3082,9 +3084,10 @@
 
 		/* create matrix with squared edge distances */
 		float *dist_map = MEM_mallocN(sizeof(*dist_map)*nverts*nverts, "isomap_distance_map");
+		#ifndef OLD_DIST_CONSTRUCTION
 		char *visited = MEM_mallocN(nverts, "isomap_visited_flags");
-		PVert **graph_stack = MEM_mallocN(sizeof(*graph_stack)*nverts, "isomap_distance_stack");
-		int graph_stack_depth = 0;
+		Heap *graph_heap = BLI_heap_new();
+		#endif
 
 		param_isomap_new_solver(nverts);
 
@@ -3153,51 +3156,68 @@
 				int ic = p_cent->u.id;
 
 				/* iterate through all edges and update distances to distance matrix */
-					PEdge *e_iter, *e_init;
-					PVert *p_viter;
-					int ij;
-					float sum_dist;
+				PEdge *e_iter, *e_init, *e_ipair;
+				PVert *p_viter;
+				int ij;
+				float sum_dist;
 
-					e_iter = e_init = p_cent->edge;
-					p_viter = e_iter->next->vert;
+				e_iter = e_init = p_cent->edge;
+				e_ipair = e_init->pair;
+				p_viter = e_iter->next->vert;
 
+				ij = p_viter->u.id;
+				sum_dist = dist_map[ic*nverts + i0] + p_edge_length(e_iter);
+				dist_map[i0*nverts + ij] = dist_map[ij*nverts + i0] =
+				        minf(dist_map[i0*nverts + ij], sum_dist);
+
+				/* add pverts in the hash and tag as visited */
+				if (!visited[ij]) {
+					BLI_heap_insert(graph_heap, dist_map[i0*nverts + ij] , p_viter);
+					visited[ij] = TRUE;
+				}
+
+				do {
+					e_iter = e_iter->next->next;
+					p_viter = e_iter->vert;
 					ij = p_viter->u.id;
-						sum_dist = dist_map[ic*nverts + i0] + p_edge_length(e_iter);
-						dist_map[i0*nverts + ij] = dist_map[ij*nverts + i0] =
-						       minf(dist_map[i0*nverts + ij], sum_dist);
+					sum_dist = dist_map[ic*nverts + i0] + p_edge_length(e_iter);
+					dist_map[i0*nverts + ij] = dist_map[ij*nverts + i0] =
+					        minf(dist_map[i0*nverts + ij], sum_dist);
 
-						/* add pverts in the hash and tag as visited */
-						if (!visited[ij]) {
-							graph_stack[graph_stack_depth++] = p_viter;
-							visited[ij] = TRUE;
-						}
+					/* add pverts in the hash and tag as visited */
+					if (!visited[ij]) {
+						BLI_heap_insert(graph_heap, dist_map[i0*nverts + ij] , p_viter);
+						visited[ij] = TRUE;
+					}
 
-					do {
-						e_iter = e_iter->next->next;
-						p_viter = e_iter->vert;
-						ij = p_viter->u.id;
-						sum_dist = dist_map[ic*nverts + i0] + p_edge_length(e_iter);
-						dist_map[i0*nverts + ij] = dist_map[ij*nverts + i0] =
-						       minf(dist_map[i0*nverts + ij], sum_dist);
+					/* assert that one of the two edge vertices is actually the p_cent vertex */
+					BLI_assert (e_iter->vert == p_cent || e_iter->next->vert == p_cent);
+					/* also assert that one of the two edge vertices is actually the p_viter vertex */
+					BLI_assert (e_iter->vert == p_viter || e_iter->next->vert == p_viter);
 
-						/* add pverts in the hash and tag as visited */
-						if (!visited[ij]) {
-							graph_stack[graph_stack_depth++] = p_viter;
-							visited[ij] = TRUE;
-						}
+					e_iter = e_iter->pair;
+				} while (e_iter && e_iter != e_init);
 
-						e_iter = e_iter->pair;
-					} while (e_iter && e_iter != e_init);
+				BLI_assert(e_iter || !e_ipair);
 
-				if (graph_stack_depth > 0)
-					p_cent = graph_stack[--graph_stack_depth];
+				if(BLI_heap_size(graph_heap) > 0)
+					p_cent = BLI_heap_popmin(graph_heap);
 				else
 					p_cent = NULL;
 			}
 		}
 
+
+		for (i = 0; i < nverts; i++) {
+			for (j = 0; j < i + 1; j++) {
+				dist_map[i*nverts + j] *= dist_map[i*nverts + j];
+				dist_map[j*nverts + i] *= dist_map[j*nverts + i];
+			}
+		}
+
+
 		MEM_freeN(visited);
-		MEM_freeN(graph_stack);
+		BLI_heap_free(graph_heap, NULL);
 
 		#endif
 

Modified: branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer_isomap.cpp
===================================================================
--- branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer_isomap.cpp	2012-08-05 01:50:08 UTC (rev 49568)
+++ branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer_isomap.cpp	2012-08-05 02:34:31 UTC (rev 49569)
@@ -29,7 +29,7 @@
 using namespace std;
 using namespace Eigen;
 
-#define UNWRAP_DEBUG
+//#define UNWRAP_DEBUG
 
 /**
   containt the Eigen solver and does the actual solving
@@ -71,8 +71,8 @@
 	eigensolver.compute(final);
 
 	#ifdef UNWRAP_DEBUG
-	cout << map_matrix << endl << endl;
-	cout << final << endl << endl;
+	cout << "distance map" << endl << map_matrix << endl << endl;
+	cout << "final matrix" << endl << final << endl << endl;
 	#endif
 
 	if (eigensolver.info() != Success) {