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