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

[Antony Riakiotakis]

Revision: 49549
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=49549
Author:   psy-fi
Date:     2012-08-04 01:49:33 +0000 (Sat, 04 Aug 2012)
Log Message:
-----------
Isomap Unwrapper
=================
* First part of optimizations found in paper:

"Texture Mapping using Surface Flattening via Multi-Dimensional Scaling"
by Gil Zigelman, Ron Kimmel and Nahum Kiryati

(Multi-Dimensional Scaling is actually isomap with another name).

Implemented Dijkstra graph search algorithm that drops distance build
times from n^4 to n*(n*logn). The paper also describes a better distance
calulation algorithm so it seems like we shall soon see ISOMAP in its
full glory after all ;)

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-04 00:08:20 UTC (rev 49548)
+++ branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer.c	2012-08-04 01:49:33 UTC (rev 49549)
@@ -3082,9 +3082,13 @@
 
 		/* create matrix with squared edge distances */
 		float *dist_map = MEM_mallocN(sizeof(*dist_map)*nverts*nverts, "isomap_distance_map");
+		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;
 
 		param_isomap_new_solver(nverts);
 
+		#ifdef OLD_DIST_CONSTRUCTION
 		/* initialize every point to "infinity" according to the paper.
 		 * since this will make every inner product give infinity as well, initialize to some
 		 * large number instead */
@@ -3123,7 +3127,80 @@
 				dist_map[i*nverts + j] *=  dist_map[i*nverts + j];
 			}
 		}
+		#else
 
+		/* initialize graph distances */
+		for (i = 0; i < nverts; i++) {
+			for (j = 0; j < i + 1; j++) {
+				dist_map[i*nverts + j] = dist_map[j*nverts + i] = (i == j)? 0 : MAXFLOAT;
+			}
+		}
+
+		/* for each vert calculate graph distance */
+		for (v = chart->verts; v; v = v->nextlink) {
+			PVert *p_cent;
+			int i0 = v->u.id;
+
+			/* reset the visited flags */
+			memset(visited, 0, nverts);
+
+			visited[i0] = TRUE;
+			p_cent = v;
+
+			while (p_cent) {
+				/* iterate through the edge ring vertices of p0 and calculate geodesic
+				 * distances */
+				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;
+
+					e_iter = e_init = p_cent->edge;
+					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]) {
+							graph_stack[graph_stack_depth++] = 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);
+
+						/* 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);
+
+				if (graph_stack_depth > 0)
+					p_cent = graph_stack[--graph_stack_depth];
+				else
+					p_cent = NULL;
+			}
+		}
+
+		MEM_freeN(visited);
+		MEM_freeN(graph_stack);
+
+		#endif
+
 		if(!param_isomap_solve(dist_map)) {
 			param_warning("ISOMAP failure, matrix solution did not converge.\n");
 

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-04 00:08:20 UTC (rev 49548)
+++ branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer_isomap.cpp	2012-08-04 01:49:33 UTC (rev 49549)
@@ -29,6 +29,8 @@
 using namespace std;
 using namespace Eigen;
 
+#define UNWRAP_DEBUG
+
 /**
   containt the Eigen solver and does the actual solving
 */