Revision: 49577
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=49577
Author: psy-fi
Date: 2012-08-05 14:22:44 +0000 (Sun, 05 Aug 2012)
Log Message:
-----------
Isomap Unwrapper
================
* Update graph distance as well if needed.
Modified Paths:
--------------
branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer.c
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 14:11:51 UTC (rev 49576)
+++
branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer.c
2012-08-05 14:22:44 UTC (rev 49577)
@@ -3070,6 +3070,11 @@
}
}
+typedef struct GraphVertInfo {
+ int removed;
+ HeapNode * node;
+} GraphVertInfo;
+
static PBool p_chart_lscm_solve(PHandle *handle, PChart *chart)
{
@@ -3085,7 +3090,7 @@
/* 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");
+ GraphVertInfo *visited = MEM_mallocN(nverts*sizeof(*visited),
"isomap_visited_flags");
Heap *graph_heap = BLI_heap_new();
#endif
@@ -3144,16 +3149,15 @@
PVert *p_cent;
int i0 = v->u.id;
- /* reset the visited flags */
- memset(visited, 0, nverts);
-
- visited[i0] = TRUE;
+ /* reset the visited nodes */
+ memset(visited, 0, nverts*sizeof(*visited));
p_cent = v;
while (p_cent) {
/* iterate through the edge ring vertices of p0
and calculate geodesic
* distances */
int ic = p_cent->u.id;
+ char update = FALSE;
/* iterate through all edges and update
distances to distance matrix */
PEdge *e_iter, *e_init, *e_ipair;
@@ -3161,35 +3165,56 @@
int ij;
float sum_dist;
+ /* iterating through this vert means we no
longer need to update the graph for
+ * it (distances may need to be updated though)
*/
+ visited[ic].removed = TRUE;
+ visited[ic].node = NULL;
+
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);
+ update = (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;
+ /* add pverts in the heap */
+ if(update) {
+ dist_map[i0*nverts + ij] =
dist_map[ij*nverts + i0] = sum_dist;
+ if(!visited[ij].removed) {
+ if (visited[ij].node) {
+
BLI_heap_remove(graph_heap, visited[ij].node);
+ }
+
+ visited[ij].node =
BLI_heap_insert(graph_heap, sum_dist , p_viter);
+ }
}
+ if(!visited[ij].removed && !visited[ij].node) {
+ visited[ij].node =
BLI_heap_insert(graph_heap, sum_dist , p_viter);
+ }
+ do {
+ update = FALSE;
- 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);
+ update = (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;
+ /* add pverts in the hash */
+ if(update) {
+ dist_map[i0*nverts + ij] =
dist_map[ij*nverts + i0] = sum_dist;
+ if(!visited[ij].removed) {
+ if (visited[ij].node) {
+
BLI_heap_remove(graph_heap, visited[ij].node);
+ }
+
+ visited[ij].node =
BLI_heap_insert(graph_heap, sum_dist , p_viter);
+ }
}
-
+ if(!visited[ij].removed &&
!visited[ij].node) {
+ visited[ij].node =
BLI_heap_insert(graph_heap, sum_dist , p_viter);
+ }
/* 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 */
@@ -3200,8 +3225,10 @@
BLI_assert(e_iter || !e_ipair);
- if(BLI_heap_size(graph_heap) > 0)
+ if(BLI_heap_size(graph_heap) > 0) {
p_cent = BLI_heap_popmin(graph_heap);
+
+ }
else
p_cent = NULL;
}
@@ -3215,15 +3242,12 @@
}
}
-
+ BLI_heap_free(graph_heap, NULL);
MEM_freeN(visited);
- BLI_heap_free(graph_heap, NULL);
#endif
if(!param_isomap_solve(dist_map)) {
- param_warning("ISOMAP failure, matrix solution did not
converge.\n");
-
param_isomap_delete_solver();
MEM_freeN(dist_map);
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
