[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
gEDA-user: spring-mass autoplacer
I would like to share a very early version of my autoplacer based on
spring - mass interaction.
It is very limited but maybe it will evelve in something useful.
I didn't waste my time learning gtk so it is currently under ctrl-p key
combination (as the other autoplacer was).
Here is how it works:
Elements are represented as boxes, connected with springs created from
netlist. There is a spring between any two objects in each netlist.
Currenlty only translations are handled, that is there is no rotation
and no side flipping. Elements from different sides interact with each
other which should be changed in next version and by splitting algorithm
in two. Each element interacts with others because of the springs and
colisions. Only selected elements' position is actually updated so you
can manually place your connectors, select all other components and
apply spring-mass to it.
In the beginning (today, 1pm) I wanted to optimize each step of earlier
autoplacer by running several sessions of spring-mass on each mutation
to get better results. I think spring mass could be used as an
interactive tool i.e. - click enable springs, drag elements and watch
them get placed.
Simply put:
Select what you want to move, hit ctrl-p and watch it change.
The diff files are probably hard to use but I didn't know how to make
better ones :)
Peter
2843,2845c2843,2844
< //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")))
2849,2867c2848
< // 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 ())
38,39d37
< //#define DEBUG_SPRINGS
<
217d214
< printf("Showing %d boxes\n", blist->BoxN);
329d325
<
614,905d609
< //====================================================================================== CUT SPRINGS ====
<
< double spr_k = 0.01;
<
< typedef struct spr_elem {
< LocationType x,y;
< LocationType w,h;
< LocationType vx,vy;
< LocationType mx,my;
< LocationType 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;
< 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;
< }
<
< int spr_update_collision_forces( spr_elem *elm ) {
< 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 = ComputeIntersectionArea( blptr );
< if( mass_involved > 0.0 ) {
< 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;
< #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_b->fx -= spr_k * (x2-x1);
< spr->elem_a->fy += spr_k * (y2-y1);
< spr->elem_b->fy -= spr_k * (y2-y1);
< spr = spr->next;
< }
< }
<
< void SpringAlg( NetListTypePtr Nets ) {
< //selected = PtrN, (ElementType *)Ptr
< spr_elem *eroot = NULL;
< spr_spring *sroot = NULL;
< Cardinal i,j,k;
<
< ELEMENT_LOOP(PCB->Data);
< {
< //twórz obiekty
< spr_elem *e = new_elem(&eroot);
<
< e->element = element;
< e->can_move = TEST_FLAG( SELECTEDFLAG, element );
< //TODO: better bounding box calculations PAD/PIN/THICKNESS/CLEARENCE
< e->w = fabs(element->BoundingBox.X2 - element->BoundingBox.X1);
< e->h = fabs(element->BoundingBox.Y2 - element->BoundingBox.Y1);
< e->x = fabs(element->BoundingBox.X2 + element->BoundingBox.X1)/2;
< e->y = fabs(element->BoundingBox.Y2 + element->BoundingBox.Y1)/2;
< e->mass = e->w*e->h;
< if( !e->mass ) e->mass = 1;
< /*
< 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 );
< */
< //twórz obiekty
< #if 1
< PIN_LOOP( element ) ;
< {
< //twórz sprężynki
< // printf("PIN @ %d %d\n", pin->X, pin->Y );
< }
< END_LOOP;
< PAD_LOOP( element ) ;
< {
< // printf("PAD @ %d %d\n", pad->Point1.X, pad->Point1.Y );
< }
< END_LOOP;
< #endif
< }
< 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;
< }
< }
< //twórz sprężynki
< for( i=0; i<Nets->NetN; i++ )
< {
< 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[k];
< spr_elem *e;
< spr_elem *a = NULL;
< spr_elem *b = NULL;
< spr_spring *s = NULL;
< e = eroot;
< while( e )
< {
< if( (ElementType *)e->element == (ElementType *)c1->ptr1 )
< a = e;
< if( (ElementType *)e->element == (ElementType *)c2->ptr1 )
< b = e;
< e = e->next;
< }
<
< if( a != NULL && b != NULL && a != b )
< {
< s = new_spring( &sroot );
<
< 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
< }
< }
< }
< }
<
< //pętla, póki cośtam
< // while(1)
< {
< //zeruj siły
< spr_elem *e;
< e = eroot;
< while( e ) {
< e->fx = e->fy = 0;
< e = e->next;
< }
< //siły od kolizji
< spr_update_collision_forces(eroot);
< //siły od sprężyn
< spr_update_spring_forces(eroot,sroot);
< //aktualizuj prędkości
< e = eroot;
< while( e ) {
< e->vx += e->fx/e->mass;
< e->vy += e->fy/e->mass;
< e = e->next;
< }
< //aktualizuj położenie
< e = eroot;
< while( e ) {
< if( e->can_move ) {
< MoveElementLowLevel (PCB->Data, e->element, e->vx, e->vy);
< e->x += e->vx;
< e->y += e->vy;
< }
< e = e->next;
< }
< }
< }
<
< 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 ====
<
973d676
<
1096c799
< double T = T0;
---
> double T = T0;
1101c804
< printf ("Starting cost is %.0f\n",ComputeCost (Nets, T0, 5));
---
> printf ("Starting cost is %.0f\n",ComputeCost (Nets, T0, 5));
685,690d684
< spring_mass_selected_cb(GtkAction *action, OutputType *out)
< {
< ActionSpringMassSelected();
< }
<
< static void
1225,1227d1218
< { "SpringMassSelected", NULL, N_("Apply Spring-Mass algorithm to selected elements"),
< "<control>s", NULL,
< G_CALLBACK(spring_mass_selected_cb) },
135d134
< {"Spring-Mass selected elements" SpringMassSelected() a={"Ctrl-S" "Ctrl<Key>s"}}