[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
gEDA-user: spring-mass update
Here are diffs for my spring algorithm.
The hot key is now ctrl-q and there are less springs.
Some attempts were made to avoid oscilations.
It would be nice to know what do you think about it and if somebody
bothered to run it.
--- pcb-gtk-springs/src/action.c 2005-03-28 22:14:22.000000000 +0200
+++ pcb-gtk/src/action.c 2005-02-27 20:16:00.000000000 +0100
@@ -2840,31 +2840,12 @@
void
ActionAutoPlaceSelected (void)
{
-//FIXME remove comments
-// if (gui_dialog_confirm(_("Auto-placement can NOT be undone.\n"
-// "Do you want to continue anyway?\n")))
+ if (gui_dialog_confirm(_("Auto-placement can NOT be undone.\n"
+ "Do you want to continue anyway?\n")))
{
HideCrosshair (True);
gui_watch_cursor ();
-// if (AutoPlaceSelected ())
- if (SpringMassSelected ())
- SetChangedFlag (True);
- gui_restore_cursor ();
- RestoreCrosshair (True);
- }
-}
-
-/* ---------------------------------------------------------------------------
- * action routine to apply spring-mass algorithm
- * syntax: SpringMassSelected()
- */
-void
-ActionSpringMassSelected (void)
-{
- {
- HideCrosshair (True);
- gui_watch_cursor ();
- if (SpringMassSelected ())
+ if (AutoPlaceSelected ())
SetChangedFlag (True);
gui_restore_cursor ();
RestoreCrosshair (True);
--- pcb-gtk-springs/src/autoplace.c 2005-03-30 09:25:59.000000000 +0200
+++ pcb-gtk/src/autoplace.c 2005-03-28 22:42:27.000000000 +0200
@@ -35,8 +35,6 @@
/* functions used to autoplace elements.
*/
-//#define DEBUG_SPRINGS 1
-
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
@@ -69,8 +67,8 @@
RCSID("$Id: autoplace.c,v 1.12 2005/01/03 12:56:58 danmc Exp $");
#define EXPANDRECTXY(r1, x1, y1, x2, y2) { \
- (r1)->X1=MIN((r1)->X1, (x1)); (r1)->Y1=MIN((r1)->Y1, (y1)); \
- (r1)->X2=MAX((r1)->X2, (x2)); (r1)->Y2=MAX((r1)->Y2, (y2)); \
+ r1->X1=MIN(r1->X1, x1); r1->Y1=MIN(r1->Y1, y1); \
+ r1->X2=MAX(r1->X2, x2); r1->Y2=MAX(r1->Y2, y2); \
}
#define EXPANDRECT(r1, r2) EXPANDRECTXY(r1, r2->X1, r2->Y1, r2->X2, r2->Y2)
@@ -214,7 +212,6 @@
{
Cardinal i;
LayerTypePtr SLayer = &(PCB->Data->Layer[MAX_LAYER + SOLDER_LAYER]);
- printf("Showing %d boxes\n", blist->BoxN);
for (i = 0; i < blist->BoxN; i++)
{
CreateNewLineOnLayer (SLayer, blist->Box[i].X1, blist->Box[i].Y1,
@@ -326,7 +323,6 @@
* "Placement and Routing of Electronic Modules" edited by Michael Pecht
* Marcel Dekker, Inc. 1993. ISBN: 0-8247-8916-4 TK7868.P7.P57 1993
*/
-
static double
ComputeCost (NetListTypePtr Nets, double T0, double T)
{
@@ -439,7 +435,7 @@
{
thickness = pad->Thickness / 2;
clearance = pad->Clearance * 2;
- EXPANDRECTXY (box,
+ EXPANDRECTXY (box,
MIN (pad->Point1.X,
pad->Point2.X) - (thickness +
clearance),
@@ -611,387 +607,6 @@
return W + (delta1 + delta2 + delta3 - delta4 + delta5);
}
-//====================================================================================== CUT SPRINGS ====
-
-double spr_k = 0.001;
-double spr_k_multiplier = 0.99;
-
-typedef struct spr_elem {
- LocationType x,y;
- LocationType w,h;
- double vx,vy;
- double mx,my;
- double fx,fy;
- double mass;
- Boolean can_move;
- ElementTypePtr element;
- struct spr_elem *next;
-} spr_elem;
-
-typedef struct spr_spring {
- spr_elem *elem_a;
- spr_elem *elem_b;
- LocationType ax,ay;
- LocationType bx,by;
- double k;
- struct spr_spring *next;
-} spr_spring;
-
-spr_elem *new_elem( spr_elem **list ) {
- spr_elem *n;
- n = malloc(sizeof(spr_elem));
- memset(n,0,sizeof(spr_elem));
- n->next = *list;
- *list = n;
- return n;
-}
-
-spr_spring *new_spring( spr_spring **list ) {
- spr_spring *n;
- n = malloc(sizeof(spr_spring));
- memset(n,0,sizeof(spr_spring));
- n->next = *list;
- *list = n;
- return n;
-}
-
-void spr_free_elements( spr_elem **list ) {
- while( *list ) {
- spr_elem *s = (*list)->next;
- free(*list);
- *list = s;
- }
-}
-
-void spr_free_springs( spr_spring **list ) {
- while( *list ) {
- spr_spring *s = (*list)->next;
- free(*list);
- *list = s;
- }
-}
-
-int spr_update_collision_forces( spr_elem *elm, spr_spring *spr ) {
- int found = 0;
- if( !elm ) return 0;
- while( elm->next ) {
- spr_elem *e = elm->next;
- while( e ) {
- double mass_involved;
- BoxListType bl;
- BoxListTypePtr blptr = &bl;
- bl.BoxN = 2;
- bl.Box = malloc(sizeof(BoxType)*2);
- bl.Box[0] = elm->element->BoundingBox;
- bl.Box[1] = e->element->BoundingBox;
- mass_involved = fabs( ComputeIntersectionArea( blptr ) );
- if( mass_involved > 0.0 ) {
- spr_spring *s;
- double fx = e->x - elm->x;
- double fy = e->y - elm->y;
- double len = sqrt( fx*fx + fy*fy );
- fx *= mass_involved;
- fy *= mass_involved;
- fx /= len;
- fy /= len;
- elm->fx -= fx;
- elm->fy -= fy;
- e->fx += fx;
- e->fy += fy;
- found = 1;
-
- s = spr;
- while( s ) {
- if( (s->elem_a == elm && s->elem_b == e) ||
- (s->elem_b == elm && s->elem_a == e) )
- {
- //weaken springs that connect intersecting elements
- s->k *= spr_k_multiplier;
-// spr_k *= spr_k_multiplier;
- }
-
- s = s->next;
- }
-
-#if DEBUG_SPRINGS
- printf("Intersection found [%s / %s], force %f %f\n", e->element->Name[1].TextString, elm->element->Name[1].TextString, fx,fy);
-#endif
- }
- free(bl.Box);
- e = e->next;
- }
- elm = elm->next;
- }
- return found;
-}
-
-int spr_update_spring_forces( spr_elem *elm, spr_spring *spr ) {
- while( spr ) {
- //FIXME for now i ignore momentum, maybe later
- LocationType x1 = spr->ax + spr->elem_a->x;
- LocationType y1 = spr->ay + spr->elem_a->y;
- LocationType x2 = spr->bx + spr->elem_b->x;
- LocationType y2 = spr->by + spr->elem_b->y;
- spr->elem_a->fx += spr->k * (x2-x1);
- spr->elem_a->fy += spr->k * (y2-y1);
- spr->elem_b->fx -= spr->k * (x2-x1);
- spr->elem_b->fy -= spr->k * (y2-y1);
-// printf("Spring [%d,%d] to [%d,%d] k=%f\n",x1,y1,x2,y2,spr->k);
-// printf("element a force %f,%f; element b force %f,%f\n",
-// spr->elem_a->fx,spr->elem_a->fy,
-// spr->elem_b->fx,spr->elem_b->fy);
- spr = spr->next;
- }
- return 0;
-}
-
-void spr_create_spring( spr_elem **eroot, spr_spring **sroot, ConnectionTypePtr c1, ConnectionTypePtr c2 ) {
-
- spr_elem *e;
- spr_elem *a = NULL;
- spr_elem *b = NULL;
- spr_spring *s = NULL;
-
- e = *eroot;
- while( e )
- {
- if( e->element == (ElementTypePtr)c1->ptr1 )
- a = e;
- if( e->element == (ElementTypePtr)c2->ptr1 )
- b = e;
- e = e->next;
- }
-
- if( a != NULL && b != NULL && a != b && (a->can_move || b->can_move) )
- {
- s = new_spring( sroot );
- s->k = spr_k;
-
- switch( c1->type )
- {
- case PAD_TYPE: s->ax = (((PadTypePtr)c1->ptr2)->Point1.X +
- ((PadTypePtr)c1->ptr2)->Point2.X) / 2;
- s->ay = (((PadTypePtr)c1->ptr2)->Point1.Y +
- ((PadTypePtr)c1->ptr2)->Point2.Y) / 2;
- break;
- case PIN_TYPE: s->ax = ((PinTypePtr)c1->ptr2)->X;
- s->ay = ((PinTypePtr)c1->ptr2)->Y;
- break;
- }
-
- switch( c2->type )
- {
- case PAD_TYPE: s->bx = (((PadTypePtr)c2->ptr2)->Point1.X +
- ((PadTypePtr)c2->ptr2)->Point2.X) / 2;
- s->by = (((PadTypePtr)c2->ptr2)->Point1.Y +
- ((PadTypePtr)c2->ptr2)->Point2.Y) / 2;
- break;
- case PIN_TYPE: s->bx = ((PinTypePtr)c2->ptr2)->X;
- s->by = ((PinTypePtr)c2->ptr2)->Y;
- break;
- }
-
- s->ax -= a->x;
- s->ay -= a->y;
- s->bx -= b->x;
- s->by -= b->y;
-
- s->elem_a = a;
- s->elem_b = b;
-#if DEBUG_SPRINGS
- printf("Net %d, connection %d,%d [%d,%d] [%d,%d]\n", i,j,k, s->ax,s->ay, s->bx,s->by);
-#endif
- }
-}
-
-void SpringAlg( NetListTypePtr Nets ) {
- //selected = PtrN, (ElementType *)Ptr
- spr_elem *eroot = NULL;
- spr_spring *sroot = NULL;
- Cardinal i,j,k;
-
- ELEMENT_LOOP(PCB->Data);
- {
- BoxType b;
- //twórz obiekty
- spr_elem *e = new_elem(&eroot);
-
- b = element->BoundingBox;
- e->element = element;
- e->can_move = TEST_FLAG( SELECTEDFLAG, element );
-
- //TODO: better bounding box calculations PAD/PIN/THICKNESS/CLEARENCE
-// printf("Box [%d,%d]x[%d,%d]\n",element->BoundingBox.X1,element->BoundingBox.Y1,element->BoundingBox.X2,element->BoundingBox.Y2);
-/*
- printf("New element %s (%s) [%d,%d,%d,%d]\n",
- e->element->Name[1].TextString, e->can_move ? "movable" : "static",
- e->x, e->y, e->w, e->h );
-*/
- //grow bounding boxes to allow tracks in between
- PIN_LOOP( element ) ;
- {
- LocationType thickness = pin->Thickness / 2;
- LocationType clearance = pin->Clearance * 2;
- EXPANDRECTXY (&b,
- pin->X - (thickness + clearance),
- pin->Y - (thickness + clearance),
- pin->X + (thickness + clearance),
- pin->Y + (thickness + clearance))
-// printf("PIN @ %d %d\n", pin->X, pin->Y );
- }
- END_LOOP;
- PAD_LOOP( element ) ;
- {
- LocationType thickness = pad->Thickness / 2;
- LocationType clearance = pad->Clearance * 2;
- EXPANDRECTXY (&b,
- MIN (pad->Point1.X,
- pad->Point2.X) - (thickness +
- clearance),
- MIN (pad->Point1.Y,
- pad->Point2.Y) - (thickness +
- clearance),
- MAX (pad->Point1.X,
- pad->Point2.X) + (thickness +
- clearance),
- MAX (pad->Point1.Y,
- pad->Point2.Y) + (thickness +
- clearance));
-// printf("PAD @ %d %d\n", pad->Point1.X, pad->Point1.Y );
- }
- END_LOOP;
- e->w = fabs(b.X2 - b.X1);
- e->h = fabs(b.Y2 - b.Y1);
- e->x = fabs(b.X2 + b.X1)/2;
- e->y = fabs(b.Y2 + b.Y1)/2;
- e->mass = ((double)e->w/10)*((double)e->h/10);
- if( !e->mass ) e->mass = 1;
- }
- END_LOOP;
-
- {
- spr_elem *e;
- double max = 0;
- double min;
- //find max mass
- e = eroot;
- while(e) {
- if( e->mass > max )
- max = e->mass;
- e = e->next;
- }
- //find min mass
- e = eroot;
- min = max;
- while(e) {
- if( e->mass < min )
- min = e->mass;
- e = e->next;
- }
- //normalize
- e = eroot;
- while(e) {
- e->mass /= min;
- e = e->next;
- }
- }
-
- for( i=0; i<Nets->NetN; i++ )
- {
- long double min_distance = -1;
- Cardinal closest = -1;
- for( j=0; j<Nets->Net[i].ConnectionN-1; j++ )
- {
- for( k=j+1; k<Nets->Net[i].ConnectionN; k++ )
- {
- ConnectionTypePtr c1 = (ConnectionTypePtr)&Nets->Net[i].Connection[j];
- ConnectionTypePtr c2 = (ConnectionTypePtr)&Nets->Net[i].Connection[closest];
- long double distance;
-
- distance = sqrt((c1->X - c2->X)*(c1->X - c2->X) + (c1->Y - c2->Y)*(c1->Y - c2->Y));
-
- if( distance < min_distance || min_distance == -1 ) {
- min_distance = distance;
- closest = k;
- }
- }
-
- ConnectionTypePtr c1 = (ConnectionTypePtr)&Nets->Net[i].Connection[j];
- ConnectionTypePtr c2 = (ConnectionTypePtr)&Nets->Net[i].Connection[closest];
-
- spr_create_spring( &eroot, &sroot, c1, c2 );
- }
- }
-
- for(i=0;i<50;i++)
- {
- //initialize forces
- //speeds too for now
- spr_elem *e;
- e = eroot;
- while( e ) {
- e->vx = e->vy = e->fx = e->fy = 0;
- e = e->next;
- }
- spr_update_collision_forces(eroot,sroot);
- spr_update_spring_forces(eroot,sroot);
- //update speeds
- e = eroot;
- while( e ) {
- if( e->can_move ) {
-// printf("Element mass is %f\n",e->mass);
-// printf("Velocity before: %d %d\n",(int)e->vx,(int)e->vy);
- e->vx += e->fx/e->mass;
- e->vy += e->fy/e->mass;
-// printf("Velocity after: %d %d\n",(int)e->vx,(int)e->vy);
- }
- e = e->next;
- }
- //update locations
- e = eroot;
- while( e ) {
- if( e->can_move ) {
-// printf("Location before: %d %d\n",(int)e->x,(int)e->y);
- MoveElementLowLevel (PCB->Data, e->element, e->vx, e->vy);
- e->x += e->vx;
- e->y += e->vy;
-// printf("Loaction after: %d %d\n",(int)e->x,(int)e->y);
- }
- e = e->next;
- }
- }
-
- spr_free_elements(&eroot);
- spr_free_springs(&sroot);
-}
-
-Boolean SpringMassSelected (void) {
- NetListTypePtr Nets;
- Boolean changed = False;
-
- Nets = ProcNetlist (&PCB->NetlistLib);
- if (!Nets)
- {
- Message (_("Can't add rat lines because no netlist is loaded.\n"));
- goto done;
- }
-
- changed = True;
- SpringAlg(Nets);
-// changed = True;
-// goto done;
-done:
-
- if (changed)
- {
- DeleteRats (False);
- AddAllRats (False, NULL);
- ClearAndRedrawOutput ();
- }
- return (changed);
-}
-//====================================================================================== CUT SPRINGS ====
-
/* ---------------------------------------------------------------------------
* Perturb:
* 1) flip SMD from solder side to component side or vice-versa.
@@ -1059,7 +674,6 @@
default:
assert (0);
}
-
return pt;
}
@@ -1182,12 +796,12 @@
}
/* now anneal in earnest */
{
- double T = T0;
+ double T = T0;
long steps = 0;
int good_moves = 0, moves = 0;
const int good_move_cutoff = CostParameter.m * Selected.PtrN;
const int move_cutoff = 2 * good_move_cutoff;
- printf ("Starting cost is %.0f\n",ComputeCost (Nets, T0, 5));
+ printf ("Starting cost is %.0f\n",ComputeCost (Nets, T0, 5));
C0 = ComputeCost (Nets, T0, T);
while (1)
{
--- pcb-gtk-springs/src/gui-top-window.c 2005-03-29 00:03:07.000000000 +0200
+++ pcb-gtk/src/gui-top-window.c 2005-02-27 18:24:21.000000000 +0100
@@ -682,12 +682,6 @@
}
static void
-spring_mass_selected_cb(GtkAction *action, OutputType *out)
- {
- ActionSpringMassSelected();
- }
-
-static void
disperse_all_elements_cb(GtkAction *action, OutputType *out)
{
ActionDisperseElements("All");
@@ -1222,9 +1216,6 @@
G_CALLBACK(select_text_by_name_cb) },
{ "SelectViasByName", NULL, N_("Vias"), NULL, NULL,
G_CALLBACK(select_vias_by_name_cb) },
- { "SpringMassSelected", NULL, N_("Apply Spring-Mass algorithm to selected elements"),
- "<control>q", NULL,
- G_CALLBACK(spring_mass_selected_cb) },
{ "AutoPlaceSelected", NULL, N_("Auto place selected elements"),
"<control>p", NULL,
G_CALLBACK(auto_place_selected_cb) },
@@ -1682,7 +1673,6 @@
" <menuitem action='SelectViasByName'/>"
" </menu>"
" <separator/>"
-" <menuitem action='SpringMassSelected'/>"
" <menuitem action='AutoPlaceSelected'/>"
" <menuitem action='DisperseAllElements'/>"
" <menuitem action='DisperseSelectedElements'/>"
--- pcb-gtk-springs/src/pcb-menu.res 2005-03-28 22:01:54.000000000 +0200
+++ pcb-gtk/src/pcb-menu.res 2005-01-13 23:15:44.000000000 +0100
@@ -132,7 +132,6 @@
{"Text Objects" Select(TextByName) ActiveWhen(have_regex)}
{"Vias" Select(ViaByName) ActiveWhen(have_regex)}
-
- {"Spring-Mass selected elements" SpringMassSelected() a={"Ctrl-S" "Ctrl<Key>s"}}
{"Auto-place selected elements" AutoPlaceSelected() a={"Ctrl-P" "Ctrl<Key>p"}}
{"Disperse all elements" DisperseElements()}
{"Move selected elements to other side" Flip(SelectedElements) a={"Shift-B" "Shift<Key>b"}}