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
*/
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
