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

[Antony Riakiotakis]

Revision: 49542
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=49542
Author:   psy-fi
Date:     2012-08-03 22:52:55 +0000 (Fri, 03 Aug 2012)
Log Message:
-----------
Isomap Unwrapper
==================
* First working version, however:

1) It's extremely slow (finding geodesic distances between all vertices
on mesh is O^4 expensive!) It can be optimized away, however there is
problem number...
2) The result is not that good when only using mesh connectivity from
edges. I may have to look at an alternative to calculate distances.

However, reading some more papers it looks like this is quite an
expensive algorithm. Coupled with the fact that it can't support pinned
UVs this will probably as far as this will go since there is no time to
investigate other methods. I will try to see if result can be improved a
bit though.

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-03 22:33:45 UTC (rev 49541)
+++ branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer.c	2012-08-03 22:52:55 UTC (rev 49542)
@@ -3078,11 +3078,11 @@
 		PEdge *e;
 		PVert *v;
 		int nverts = chart->nverts;
-		int i, j, k;
+		int i, j, k, l;
 
 		/* create matrix with squared edge distances */
 		float *dist_map = MEM_mallocN(sizeof(*dist_map)*nverts*nverts, "isomap_distance_map");
-		float *init_map = MEM_mallocN(sizeof(*dist_map)*nverts*nverts, "isomap_distance_map");
+		//float *init_map = MEM_mallocN(sizeof(*dist_map)*nverts*nverts, "isomap_distance_map");
 
 		param_isomap_new_solver(nverts);
 
@@ -3091,38 +3091,44 @@
 		 * large number instead */
 		for (i = 0; i < nverts; i++)
 			for (j = 0; j < nverts; j++) {
-				*(dist_map + i*nverts + j) = (i == j)? 0 : 500;
-				*(init_map + i*nverts + j) = 500000;
+				*(dist_map + i*nverts + j) = (i == j)? 0 : MAXFLOAT;
+				//*(init_map + i*nverts + j) = MAXFLOAT;
 			}
 
 		/* for each edge, put the squared distance to the appropriate matrix positions */
 		for (e = chart->edges; e; e = e->nextlink) {
 			/* fill the upper right part of the matrix */
-			*(dist_map + e->vert->u.id*nverts + e->next->vert->u.id) =
-			*(dist_map + e->next->vert->u.id*nverts + e->vert->u.id) =
+			dist_map[e->vert->u.id*nverts + e->next->vert->u.id] =
+			dist_map[e->next->vert->u.id*nverts + e->vert->u.id] =
 			        p_edge_length(e);
 		}
 
 		/* now edge length has been computed. Now construct shortest paths
 		 * and put them to lower left of matrix. */
-		for (i = 0; i < nverts; i++) {
-			for (j = 0; j < nverts; j++) {
-				for (k = 0; k < nverts; k++) {
-					float sum_dist;
-					sum_dist = *(dist_map + i*nverts + k) + *(dist_map + k*nverts + j);
+		for (l = 0; l < nverts; l++) {
+			for (i = 0; i < nverts; i++) {
+				for (j = 0; j < nverts; j++) {
+					for (k = 0; k < nverts; k++) {
+						float sum_dist = dist_map[i*nverts + k] + dist_map[k*nverts + j];
 
-					*(init_map + i*nverts + j) = minf(*(init_map + i*nverts + j), sum_dist);
+						dist_map[i*nverts + j] = dist_map[j*nverts + i] = minf(dist_map[i*nverts + j], sum_dist);
+					}
 				}
 			}
 		}
 
+		for (i = 0; i < nverts; i++) {
+			for (j = 0; j < nverts; j++) {
+				dist_map[i*nverts + j] *=  dist_map[i*nverts + j];
+			}
+		}
 
-		if(!param_isomap_solve(init_map)) {
+		if(!param_isomap_solve(dist_map)) {
 			param_warning("ISOMAP failure, matrix solution did not converge.\n");
 
 			param_isomap_delete_solver();
 			MEM_freeN(dist_map);
-			MEM_freeN(init_map);
+			//MEM_freeN(init_map);
 
 			return P_FALSE;
 		}
@@ -3134,7 +3140,7 @@
 		/* cleanup */
 		param_isomap_delete_solver();
 		MEM_freeN(dist_map);
-		MEM_freeN(init_map);
+		//MEM_freeN(init_map);
 
 		return P_TRUE;
 	} else {

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-03 22:33:45 UTC (rev 49541)
+++ branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer_isomap.cpp	2012-08-03 22:52:55 UTC (rev 49542)
@@ -64,10 +64,11 @@
 	centering_transform.setConstant(size, size, 1.0/size);
 	centering_transform = MatrixXf::Identity(size, size) - centering_transform;
 
-	final = -0.5 * centering_transform * map_matrix * map_matrix * centering_transform;
+	final = -0.5 * centering_transform * map_matrix * centering_transform;
 
 	eigensolver.compute(final);
 
+	cout << centering_transform << endl << endl;
 	cout << map_matrix << endl << endl;
 	cout << final << endl << endl;
 
@@ -90,11 +91,10 @@
 	float eigenvalue1 = eigensolver.eigenvalues()(size - 1);
 	float eigenvalue2 = eigensolver.eigenvalues()(size - 2);
 
-	uv[0] = eigensolver.eigenvectors()(index, size - 1)*signf(eigenvalue1)*sqrtf(fabs(eigenvalue1));
-	uv[1] = eigensolver.eigenvectors()(index, size - 2)*signf(eigenvalue2)*sqrtf(fabs(eigenvalue2));
+	uv[0] = eigensolver.eigenvectors()(index, size - 1)*sqrtf(eigenvalue1);
+	uv[1] = eigensolver.eigenvectors()(index, size - 2)*sqrtf(eigenvalue2);
 
 	cout << index << ' ' << uv[0] << ' ' << uv[1] << endl;
-	cout << index << ' ' << eigenvalue1 << ' ' << eigenvalue2 << endl;
 	cout << index << ' ' << eigensolver.eigenvectors()(index, size - 1)
 	     << ' ' << eigensolver.eigenvectors()(index, size - 2) << endl;
 }