[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15845] branches/harmonic-skeleton/source/ blender/src/reeb.c: Add automatic weight probagation between islands without any selected vertex .
Martin Poirier
theeth at yahoo.com
Mon Jul 28 17:04:34 CEST 2008
Revision: 15845
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15845
Author: theeth
Date: 2008-07-28 17:03:58 +0200 (Mon, 28 Jul 2008)
Log Message:
-----------
Add automatic weight probagation between islands without any selected vertex. Makes it easier to do multi part meshes.
Modified Paths:
--------------
branches/harmonic-skeleton/source/blender/src/reeb.c
Modified: branches/harmonic-skeleton/source/blender/src/reeb.c
===================================================================
--- branches/harmonic-skeleton/source/blender/src/reeb.c 2008-07-28 14:35:56 UTC (rev 15844)
+++ branches/harmonic-skeleton/source/blender/src/reeb.c 2008-07-28 15:03:58 UTC (rev 15845)
@@ -2681,6 +2681,98 @@
return e;
}
+void shortestPathsFromVert(EditMesh *em, EditVert *starting_vert, EditEdge **edges)
+{
+ EditVert *current_eve = NULL;
+ EditEdge *eed = NULL;
+ EditEdge *select_eed = NULL;
+ float current_weight = 0;
+ int next_edge_index = 0;
+ int selected_edge_index = 0;
+
+ current_eve = starting_vert;
+
+ /* Initialize edge flag */
+ for(eed= em->edges.first; eed; eed= eed->next)
+ {
+ eed->f1 = 0;
+ }
+
+ do {
+ int i;
+
+ current_eve->f1 = 1; /* mark vertex as selected */
+
+ /* Add all new edges connected to current_eve to the list */
+ NextEdgeForVert(NULL, NULL); // Reset next edge
+ for(eed = NextEdgeForVert(em, current_eve); eed; eed = NextEdgeForVert(em, current_eve))
+ {
+ if (eed->f1 == 0)
+ {
+ edges[next_edge_index] = eed;
+ eed->f1 = 1;
+ next_edge_index++;
+ }
+ }
+
+ /* Find next shortest edge */
+ select_eed = NULL;
+ for(i = 0; i < next_edge_index; i++)
+ {
+ eed = edges[i];
+
+ if (eed->f1 != 2 && (eed->v1->f1 == 0 || eed->v2->f1 == 0)) /* eed is not selected yet and leads to a new node */
+ {
+ float new_weight = 0;
+ if (eed->v1->f1 == 1)
+ {
+ new_weight = eed->v1->tmp.fp + eed->tmp.fp;
+ }
+ else
+ {
+ new_weight = eed->v2->tmp.fp + eed->tmp.fp;
+ }
+
+ if (select_eed == NULL || new_weight < current_weight) /* no selected edge or current smaller than selected */
+ {
+ current_weight = new_weight;
+ select_eed = eed;
+ selected_edge_index = i;
+ }
+ }
+ else
+ {
+ /* edge shouldn't be in list. Decrement next index and insert last edge in this place and reset iteration*/
+ next_edge_index--;
+ edges[i] = edges[next_edge_index];
+ i--;
+ }
+ }
+
+ if (select_eed != NULL)
+ {
+ select_eed->f1 = 2;
+
+ /* decrement next index and swap selected with last edge in list */
+ next_edge_index--;
+ edges[selected_edge_index] = edges[next_edge_index];
+
+ if (select_eed->v1->f1 == 0) /* v1 is the new vertex */
+ {
+ current_eve = select_eed->v1;
+ }
+ else /* otherwise, it's v2 */
+ {
+ current_eve = select_eed->v2;
+ }
+ current_eve->tmp.fp = current_weight;
+ }
+
+ } while (select_eed != NULL);
+
+ printf("\n");
+}
+
int weightFromDistance(EditMesh *em)
{
EditVert *eve;
@@ -2716,99 +2808,71 @@
}
else
{
- EditVert *eve, *current_eve = NULL;
+ EditVert *eve;
+ EditEdge *eed;
+ EditEdge **edges;
+ int allDone = 0;
+
+ /* Allocate scratch array for edges */
+ edges = MEM_callocN(totedge * sizeof(EditEdge*), "Edges");
+
+ /* Calculate edge weight */
+ for(eed = em->edges.first; eed; eed= eed->next)
+ {
+ eed->tmp.fp = VecLenf(eed->v1->co, eed->v2->co);
+ }
+
/* Apply dijkstra spf for each selected vert */
for(eve = em->verts.first; eve; eve = eve->next)
{
if (eve->f & SELECT)
{
- current_eve = eve;
- eve->f1 = 1;
-
+ shortestPathsFromVert(em, eve, edges);
+ }
+ }
+
+ /* connect unselected islands */
+ while (allDone == 0)
+ {
+ EditVert *selected_eve = NULL;
+ float selected_weight = 0;
+ float min_distance = FLT_MAX;
+
+ allDone = 1;
+
+ for (eve = em->verts.first; eve; eve = eve->next)
+ {
+ if (eve->f1 != 1)
{
- EditEdge *eed = NULL;
- EditEdge *select_eed = NULL;
- EditEdge **edges = NULL;
- float currentWeight = 0;
- int eIndex = 0;
+ EditVert *closest_eve;
- edges = MEM_callocN(totedge * sizeof(EditEdge*), "Edges");
-
- /* Calculate edge weight and initialize edge flag */
- for(eed= em->edges.first; eed; eed= eed->next)
+ for (closest_eve = em->verts.first; closest_eve; closest_eve = closest_eve->next)
{
- eed->tmp.fp = VecLenf(eed->v1->co, eed->v2->co);
- eed->f1 = 0;
- }
-
- do {
- int i;
-
- current_eve->f1 = 1; /* mark vertex as selected */
-
- /* Add all new edges connected to current_eve to the list */
- NextEdgeForVert(NULL, NULL); // Reset next edge
- for(eed = NextEdgeForVert(em, current_eve); eed; eed = NextEdgeForVert(em, current_eve))
- {
- if (eed->f1 == 0)
- {
- edges[eIndex] = eed;
- eed->f1 = 1;
- eIndex++;
- }
- }
-
- /* Find next shortest edge */
- select_eed = NULL;
- for(i = 0; i < eIndex; i++)
+ /* vertex is already processed and distance is smaller than current minimum */
+ if (closest_eve->f1 == 1)
{
- eed = edges[i];
-
- if (eed->f1 != 2 && (eed->v1->f1 == 0 || eed->v2->f1 == 0)) /* eed is not selected yet and leads to a new node */
+ float distance = VecLenf(closest_eve->co, eve->co);
+ if (distance < min_distance)
{
- float newWeight = 0;
- if (eed->v1->f1 == 1)
- {
- newWeight = eed->v1->tmp.fp + eed->tmp.fp;
- }
- else
- {
- newWeight = eed->v2->tmp.fp + eed->tmp.fp;
- }
-
- if (select_eed == NULL || newWeight < currentWeight) /* no selected edge or current smaller than selected */
- {
- currentWeight = newWeight;
- select_eed = eed;
- }
+ min_distance = distance;
+ selected_eve = eve;
+ selected_weight = closest_eve->tmp.fp;
}
}
-
- if (select_eed != NULL)
- {
- select_eed->f1 = 2;
-
- if (select_eed->v1->f1 == 0) /* v1 is the new vertex */
- {
- current_eve = select_eed->v1;
- }
- else /* otherwise, it's v2 */
- {
- current_eve = select_eed->v2;
- }
- current_eve->tmp.fp = currentWeight;
- }
-
- printf("\redge %i / %i", eIndex, totedge);
-
- } while (select_eed != NULL);
-
- MEM_freeN(edges);
-
- printf("\n");
+ }
}
}
+
+ if (selected_eve)
+ {
+ allDone = 0;
+
+ selected_eve->tmp.fp = selected_weight + min_distance;
+ shortestPathsFromVert(em, selected_eve, edges);
+ }
}
+
+ MEM_freeN(edges);
}
for(eve = em->verts.first; eve && vCount == 0; eve = eve->next)
More information about the Bf-blender-cvs
mailing list