[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [49749] branches/soc-2012-bratwurst/source /blender/editors/uvedit/uvedit_parametrizer.c: Isomap Unwrapper
Antony Riakiotakis
kalast at gmail.com
Fri Aug 10 01:59:41 CEST 2012
Revision: 49749
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=49749
Author: psy-fi
Date: 2012-08-09 23:59:41 +0000 (Thu, 09 Aug 2012)
Log Message:
-----------
Isomap Unwrapper
================
* Add code that determines the distance based on nearby vertices, if any
of them have had their distance calculated. That has been achallenge as
can be seen from the loads of debug code that went into it.
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-09 23:59:36 UTC (rev 49748)
+++ branches/soc-2012-bratwurst/source/blender/editors/uvedit/uvedit_parametrizer.c 2012-08-09 23:59:41 UTC (rev 49749)
@@ -3073,13 +3073,14 @@
typedef struct GraphVertInfo {
int removed;
+ int added;
HeapNode * node;
} GraphVertInfo;
-void p_chart_isomap_iterate_graph_edge(int i0, PEdge *p_edge, PBool inverted, PBool do_double, float *dist_map, int nverts, GraphVertInfo *visited, Heap *graph_heap)
+PBool p_chart_isomap_iterate_graph_edge(int i0, PEdge *p_edge, PBool inverted, PBool do_double, float *dist_map, int nverts, GraphVertInfo *visited, Heap *graph_heap)
{
PBool update = P_FALSE;
- int ij, io;
+ int ij, iother;
int ic;
float sum_dist;
float d[3];
@@ -3088,20 +3089,6 @@
PVert *p_viter;
PVert *p_other;
- /* determine if we can calculate distance from two neighbors. p_cent is guaranteed to
- * have valid distance data so simply check for other vert */
- if (do_double) {
- p_other = p_edge->next->next->vert;
- io = p_other->u.id;
-
- if (!visited[io].node) {
- /* add a node to the heap so that the node will be traversed later.
- * make sure to put a max value so the node gets to the bottom of the heap. */
- visited[io].node = BLI_heap_insert(graph_heap, MAXFLOAT , p_other);
- return;
- }
- }
-
if(inverted) {
p_cent = p_edge->next->vert;
p_viter = p_edge->vert;
@@ -3113,6 +3100,48 @@
ic = p_cent->u.id;
ij = p_viter->u.id;
+ /* determine if we can calculate distance from two neighbors. p_cent is guaranteed to
+ * have valid distance data so simply check for other vert */
+ if (do_double) {
+ p_other = p_edge->next->next->vert;
+ iother = p_other->u.id;
+
+ if (!visited[iother].added) {
+ PBool fail = P_FALSE;
+ /* first attempt calculating the vert using the other triangle */
+ p_edge = p_edge->pair;
+ /* possible that we are at a chart's edge */
+ if (p_edge) {
+ if(inverted) {
+ p_viter = p_edge->next->vert;
+ } else {
+ p_viter = p_edge->vert;
+ }
+
+ ij = p_viter->u.id;
+
+ p_other = p_edge->next->next->vert;
+ iother = p_other->u.id;
+ } else {
+ fail = P_TRUE;
+ }
+
+ if (!visited[iother].added)
+ fail = P_TRUE;
+
+ /* attempt failed, return 0 */
+ if(fail) {
+ /* add a node to the heap so that the node will be traversed later.
+ * make sure to put a max value so the node gets to the bottom of the heap. */
+ if (!visited[ij].node)
+ visited[ij].node = BLI_heap_insert(graph_heap, MAXFLOAT , p_viter);
+
+ printf("vertex %d failed due to vertex %d missing. inverted: %d\n", ij, iother, inverted);
+ return P_FALSE;
+ }
+ }
+ }
+
d[0] = p_viter->co[0] - p_cent->co[0];
d[1] = p_viter->co[1] - p_cent->co[1];
d[2] = p_viter->co[2] - p_cent->co[2];
@@ -3120,6 +3149,11 @@
sum_dist = dist_map[ic*nverts + i0] + sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2]);
update = (dist_map[i0*nverts + ij] > sum_dist);
+ if (!visited[ij].added && visited[ij].node) {
+ BLI_heap_remove(graph_heap, visited[ij].node);
+ visited[ij].node = NULL;
+ }
+
/* add pverts in the hash */
if(update) {
dist_map[i0*nverts + ij] = dist_map[ij*nverts + i0] = sum_dist;
@@ -3134,13 +3168,20 @@
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 */
- //BLI_assert (e_iter->vert == p_viter || e_iter->next->vert == p_viter);
+ visited[ij].added = TRUE;
+ if (do_double) {
+ printf("vertex %d calculated, other vertex %d, inverted %d \n", ij, iother, inverted);
+ } else {
+ printf("vertex %d calculated\n", ij);
+ }
+ return P_TRUE;
}
+typedef struct GraphEdgeInfo {
+ PEdge *e;
+ PBool inverted;
+} GraphEdgeInfo;
+
static PBool p_chart_lscm_solve(PHandle *handle, PChart *chart)
{
enum UnwrapMethods method = handle->method;
@@ -3148,12 +3189,13 @@
if (method == UNWRAP_ISOMAP) {
PVert *v;
int nverts = chart->nverts;
- int i, j;
+ int i, j, stack_depth = 0;
/* create matrix with squared edge distances */
float *dist_map = MEM_mallocN(sizeof(*dist_map)*nverts*nverts, "isomap_distance_map");
GraphVertInfo *visited = MEM_mallocN(nverts*sizeof(*visited), "isomap_visited_flags");
Heap *graph_heap = BLI_heap_new();
+ GraphEdgeInfo *prox_stack = MEM_mallocN(nverts*sizeof(*prox_stack), "isomap_proximity_stack");
param_isomap_new_solver(nverts);
@@ -3170,8 +3212,13 @@
PVert *p_cent;
int i0 = v->u.id;
+ printf("changing initial vertex: %d\n", i0);
+
/* reset the visited nodes */
memset(visited, 0, nverts*sizeof(*visited));
+
+ visited[i0].added = P_TRUE;
+
p_cent = v;
/* calculate distance on a first circle of verts around the first vertex.
@@ -3179,6 +3226,8 @@
while (p_cent) {
int ic = p_cent->u.id;
+ int stack_iter = 0;
+ int old_stack_depth;
PEdge *e_iter, *e_init;
@@ -3188,11 +3237,10 @@
e_iter = e_init = p_cent->edge;
- /* iterate through the edge ring vertices of p0 and calculate geodesic
- * distances */
+ /* iterate through the edge ring vertices of p_cent */
do {
- p_chart_isomap_iterate_graph_edge(i0, e_iter, P_FALSE, not_first,
- dist_map, nverts, visited, graph_heap);
+ prox_stack[stack_depth].e = e_iter;
+ prox_stack[stack_depth++].inverted = P_FALSE;
e_iter = e_iter->next->next;
@@ -3200,14 +3248,69 @@
if(e_iter->pair)
e_iter = e_iter->pair;
else {
- p_chart_isomap_iterate_graph_edge(i0, e_iter, P_TRUE, not_first,
- dist_map, nverts, visited, graph_heap);
+ prox_stack[stack_depth].e = e_iter;
+ prox_stack[stack_depth++].inverted = P_TRUE;
break;
}
} while (e_iter != e_init);
+ old_stack_depth = stack_depth;
+ printf("processing vertex %d \n", ic);
+ while (stack_depth) {
+ int old_stack_iter = stack_iter;
+
+ stack_iter %= stack_depth;
+
+ if(stack_iter < old_stack_iter) {
+ if(old_stack_depth == stack_depth) {
+ printf("deadlock vertex index: %d\n", ic);
+ for(i = 0; i < nverts; i++) {
+ printf("%d vertex info added: %d\n",i, visited[i].added);
+ printf("%d vertex info removed: %d\n",i, visited[i].added);
+ }
+ e_iter = e_init = p_cent->edge;
+
+ /* iterate through the edge ring vertices of p_cent */
+ do {
+ printf("neighbor index: %d\n",e_iter->next->vert->u.id);
+ e_iter = e_iter->next->next;
+ if(e_iter->pair)
+ e_iter = e_iter->pair;
+ else {
+ printf("neighbor index: %d\n",e_iter->vert->u.id);
+ break;
+ }
+ } while (e_iter != e_init);
+
+ BLI_heap_free(graph_heap, NULL);
+ MEM_freeN(visited);
+ MEM_freeN(prox_stack);
+ MEM_freeN(dist_map);
+
+ return P_FALSE;
+ }
+ old_stack_depth = stack_depth;
+ }
+
+ if(p_chart_isomap_iterate_graph_edge(i0, prox_stack[stack_iter].e,
+ prox_stack[stack_iter].inverted,
+ not_first, dist_map, nverts,
+ visited, graph_heap))
+ {
+ prox_stack[stack_iter].e = prox_stack[stack_depth - 1].e;
+ prox_stack[stack_iter].inverted = prox_stack[stack_depth - 1].inverted;
+ stack_depth--;
+ continue;
+ }
+ stack_iter++;
+ }
+
if(BLI_heap_size(graph_heap) > 0) {
p_cent = BLI_heap_popmin(graph_heap);
+
+ if(!visited[p_cent->u.id].added) {
+ printf("BLI_heap_size(graph_heap) %d\n", BLI_heap_size(graph_heap));
+ }
}
else {
p_cent = NULL;
@@ -3217,6 +3320,9 @@
}
}
+ BLI_heap_free(graph_heap, NULL);
+ MEM_freeN(visited);
+ MEM_freeN(prox_stack);
for (i = 0; i < nverts; i++) {
for (j = 0; j < i + 1; j++) {
@@ -3225,9 +3331,6 @@
}
}
- BLI_heap_free(graph_heap, NULL);
- MEM_freeN(visited);
-
if(!param_isomap_solve(dist_map)) {
param_isomap_delete_solver();
MEM_freeN(dist_map);
More information about the Bf-blender-cvs
mailing list