/* $Id: autoroute.c,v 1.3 2006/03/08 13:58:25 mcmahill Exp $ */ /* * COPYRIGHT * * PCB, interactive printed circuit board design * Copyright (C) 1994,1995,1996 Thomas Nau * Copyright (C) 1998,1999,2000,2001 harry eaton * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. * * Contact addresses for paper mail and Email: * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA * haceaton@aplcomm.jhuapl.edu * */ /* this file, autoroute.c, was written and is * Copyright (c) 2001 C. Scott Ananian */ /* functions used to autoroute nets. */ /* *------------------------------------------------------------------- * This file implements a rectangle-expansion router, based on * "A Method for Gridless Routing of Printed Circuit Boards" by * A. C. Finch, K. J. Mackenzie, G. J. Balsdon, and G. Symonds in the * 1985 Proceedings of the 22nd ACM/IEEE Design Automation Conference. * This reference is available from the ACM Digital Library at * http://www.acm.org/dl for those with institutional or personal * access to it. It's also available from your local engineering * library. *-------------------------------------------------------------------- */ #define NET_HEAP #define REGION 75000 #ifdef HAVE_CONFIG_H #include "config.h" #endif #include "global.h" #include #include #include "data.h" #include "macro.h" #include "autoroute.h" #include "box.h" /*#include "clip.h"*/ #include "create.h" #include "draw.h" #include "error.h" #include "heap.h" #include "rtree.h" #include "misc.h" #include "mtspace.h" #include "mymem.h" #include "polygon.h" /* for UpdatePIPFlags */ #include "rats.h" #include "remove.h" #include "undo.h" #include "vector.h" RCSID("$Id: autoroute.c,v 1.3 2006/03/08 13:58:25 mcmahill Exp $"); /* #defines to enable some debugging output */ /*#define ROUTE_VERBOSE*/ /* #define ROUTE_DEBUG #define DEBUG_SHOW_ROUTE_BOXES #define DEBUG_SHOW_VIA_BOXES #define DEBUG_SHOW_EXPANSION_BOXES */ /* round up "half" thicknesses */ #define HALF_THICK(x) (((x)+1)/2) /* a styles maximum bloat is its keepaway plus the larger of its via radius * or line half-thickness. */ #define BLOAT(style)\ ((style)->Keepaway + HALF_THICK((style)->Thick)) /* conflict penalty is less for traces laid down during previous pass than * it is for traces already laid down in this pass. */ #define CONFLICT_LEVEL(rb)\ (((rb)->flags.is_odd==AutoRouteParameters.is_odd) ?\ HI_CONFLICT : LO_CONFLICT ) #define CONFLICT_PENALTY(rb)\ (CONFLICT_LEVEL(rb)==HI_CONFLICT ? \ AutoRouteParameters.ConflictPenalty : \ CONFLICT_LEVEL(rb)==LO_CONFLICT ? \ AutoRouteParameters.LastConflictPenalty : 1) #if !defined(ABS) #define ABS(x) (((x)<0)?-(x):(x)) #endif #define LIST_LOOP(init, which, x) do {\ routebox_t *__next_one__ = (init);\ x = NULL;\ while (!x || __next_one__ != (init)) {\ x = __next_one__;\ /* save next one first in case the command modifies or frees it */\ __next_one__ = x->which.next #define FOREACH_SUBNET(net, p) do {\ routebox_t *_pp_;\ /* fail-fast: check subnet_processed flags */\ LIST_LOOP(net, same_net, p); \ assert(!p->flags.subnet_processed);\ END_LOOP;\ /* iterate through *distinct* subnets */\ LIST_LOOP(net, same_net, p); \ if (!p->flags.subnet_processed) {\ LIST_LOOP(p, same_subnet, _pp_);\ _pp_->flags.subnet_processed=1;\ END_LOOP #define END_FOREACH(net, p) \ }; \ END_LOOP;\ /* reset subnet_processed flags */\ LIST_LOOP(net, same_net, p); \ p->flags.subnet_processed=0;\ END_LOOP;\ } while (0) /* notes: * all rectangles are assumed to be closed on the top and left and * open on the bottom and right. That is, they include their top-left * corner but don't include their bottom-right corner. * * Obstacles, however, are thought of to be closed on all sides, * and exclusion zone *open* on all sides. We will ignore the infintesimal * difference w.r.t. obstacles, but exclusion zones will be consistently * bumped in one unit on the top and left in order to exclose the same * integer coordinates as their open-rectangle equivalents. * * expansion regions are always half-closed. This means that when * tracing paths, you must steer clear of the bottom and right edges. */ /* --------------------------------------------------------------------------- * some local types */ /* augmented RouteStyleType */ typedef struct { /* a routing style */ const RouteStyleType *style; /* flag indicating whether this augmented style is ever used. * We only update mtspace if the style is used somewhere in the netlist */ Boolean Used; } AugmentedRouteStyleType; /* enumerated type for conflict levels */ typedef enum { NO_CONFLICT = 0, LO_CONFLICT = 1, HI_CONFLICT = 2 } conflict_t; typedef struct routebox { const BoxType box; union { PadTypePtr pad; PinTypePtr pin; PinTypePtr via; struct routebox *via_shadow; /* points to the via in r-tree which * points to the PinType in the PCB. */ LineTypePtr line; void *generic; /* 'other' is polygon, arc, text */ struct routebox *expansion_area; /* previous expansion area in search */ } parent; unsigned char group; unsigned char layer; enum { PAD, PIN, VIA, VIA_SHADOW, LINE, OTHER, EXPANSION_AREA, PLANE } type; cost_t cost; struct { unsigned nonstraight:1; unsigned fixed:1; /* for searches */ unsigned source:1; unsigned target:1; /* rects on same net as source and target don't need clearance areas */ unsigned nobloat:1; /* mark circular pins, so that we be sure to connect them up properly */ unsigned circular:1; /* we sometimes create routeboxen that don't actually belong to a * r-tree yet -- make sure refcount of orphans is set properly */ unsigned orphan:1; /* was this nonfixed obstacle generated on an odd or even pass? */ unsigned is_odd:1; /* fixed route boxes that have already been "routed through" in this * search have their "touched" flag set. */ unsigned touched:1; /* this is a status bit for iterating through *different* subnets */ unsigned subnet_processed:1; /* some expansion_areas represent via candidates */ unsigned is_via:1; /* mark non-straight lines which go from bottom-left to upper-right, * instead of from upper-left to bottom-right. */ unsigned bl_to_ur:1; /* mark polygons which are "transparent" for via-placement; that is, * vias through the polygon will automatically be given a keepaway * and will not electrically connect to the polygon. */ unsigned clear_poly:1; /* this markes "conflicting" routes that must be torn up to obtain * a correct routing. This flag allows us to return a correct routing * even if the user cancels auto-route after a non-final pass. */ unsigned is_bad:1; /* for assertion that 'box' is never changed after creation */ unsigned inited:1; } flags; /* reference count for orphan routeboxes; free when refcount==0 */ int refcount; /* when routing with conflicts, we keep a record of what we're * conflicting *with*. */ struct routebox *underlying; /* route style of the net associated with this routebox */ AugmentedRouteStyleType *augStyle; /* circular lists with connectivity information. */ struct routebox_list { struct routebox *next, *prev; } same_net, same_subnet, original_subnet, different_net; } routebox_t; typedef struct routedata { /* one rtree per layer *group */ rtree_t *layergrouptree[MAX_LAYER]; /* no silkscreen layers here =) */ /* root pointer into connectivity information */ routebox_t *first_net; /* default routing style */ RouteStyleType defaultStyle; /* augmented style structures */ AugmentedRouteStyleType augStyles[NUM_STYLES + 1]; /* what is the maximum bloat (keepaway+line half-width or * keepaway+via_radius) for any style we've seen? */ BDimension max_bloat; mtspace_t *mtspace; } routedata_t; typedef struct edge_struct { routebox_t *rb; /* path expansion edges are real routeboxen. */ CheapPointType cost_point; cost_t cost_to_point; /* from source */ cost_t cost; /* cached edge cost */ routebox_t *mincost_target; /* minimum cost from cost_point to any target */ direction_t expand_dir; /* ignored if expand_all_sides is set */ struct { /* ignore expand_dir and expand all sides if this is set. */ /* used for vias and the initial source objects */ unsigned expand_all_sides:1; /* XXX: this is redundant with is_via? */ /* this indicates that this 'edge' is a via candidate. */ unsigned is_via:1; /* record "conflict level" of via candidates, in case we need to split * them later. */ conflict_t via_conflict_level:2; /* when "routing with conflicts", sometimes edge is interior. */ unsigned is_interior:1; } flags; } edge_t; static struct { /* net style parameters */ AugmentedRouteStyleType *augStyle; /* cost parameters */ cost_t ViaCost, /* additional "length" cost for using a via */ SurfacePenalty, /* scale for congestion on SMD layers */ LastConflictPenalty, /* length mult. for routing over last pass' trace */ ConflictPenalty, /* length multiplier for routing over another trace */ JogPenalty, /* additional "length" cost for changing direction */ DirectionPenalty; /* (rational) length multiplier for routing in */ /* are vias allowed? */ Boolean use_vias; /* is this an odd or even pass? */ Boolean is_odd; /* permit conflicts? */ Boolean with_conflicts; /* is this a final "smoothing" pass? */ Boolean is_smoothing; } AutoRouteParameters; static int ro = 0; /* --------------------------------------------------------------------------- * some local prototypes */ static routebox_t *CreateExpansionArea (const BoxType * area, Cardinal group, routebox_t * parent, Boolean relax_edge_requirements, edge_t * edge); static cost_t edge_cost (const edge_t * e); static BoxType edge_to_box (const BoxType * box, direction_t expand_dir); static void ResetSubnet (routebox_t * net); /* --------------------------------------------------------------------------- * some local identifiers */ /* group number of groups that hold surface mount pads */ static Cardinal front, back; static Boolean bad_x[MAX_LAYER], bad_y[MAX_LAYER]; /* assertion helper for routeboxen */ #ifndef NDEBUG static int __routebox_is_good (routebox_t * rb) { assert (rb && (0 <= rb->group) && (rb->group < MAX_LAYER) && (rb->box.X1 <= rb->box.X2) && (rb->box.Y1 <= rb->box.Y2) && (rb->flags.orphan ? (rb->box.X1 != rb->box.X2) || (rb->box.Y1 != rb->box.Y2) : (rb->box.X1 != rb->box.X2) && (rb->box.Y1 != rb->box.Y2))); assert ((rb->flags.source ? rb->flags.nobloat : 1) && (rb->flags.target ? rb->flags.nobloat : 1) && (rb->flags.orphan ? !rb->flags.touched : rb->refcount == 0) && (rb->flags.touched ? rb->type != EXPANSION_AREA : 1)); assert ((rb->flags.is_odd ? (!rb->flags.fixed) && (rb->type == VIA || rb->type == VIA_SHADOW || rb->type == LINE || rb->type == PLANE) : 1)); assert ((rb->flags.bl_to_ur ? rb->flags.nonstraight : 1) && (rb->flags.clear_poly ? ((rb->type == OTHER || rb->type == PLANE) && rb->flags.fixed && !rb->flags.orphan) : 1)); assert ((rb->underlying == NULL || !rb->underlying->flags.orphan) && rb->flags.inited); assert (rb->augStyle != NULL && rb->augStyle->style != NULL); assert (rb->same_net.next && rb->same_net.prev && rb->same_subnet.next && rb->same_subnet.prev && rb->original_subnet.next && rb->original_subnet.prev && rb->different_net.next && rb->different_net.prev); return 1; } static int __edge_is_good (edge_t * e) { assert (e && e->rb && __routebox_is_good (e->rb)); assert ((e->rb->flags.orphan ? e->rb->refcount > 0 : 1)); assert ((0 <= e->expand_dir) && (e->expand_dir < 4) && (e->flags. is_interior ? (e->flags.expand_all_sides && e->rb->underlying) : 1)); assert ((e->flags.is_via ? e->rb->flags.is_via : 1) && (e->flags.via_conflict_level >= 0 && e->flags.via_conflict_level <= 2) && (e->flags.via_conflict_level != 0 ? e->flags.is_via : 1)); assert ((e->cost_to_point >= 0) && e->cost >= 0); return 1; } #endif /* !NDEBUG */ /*--------------------------------------------------------------------- * route utility functions. */ enum boxlist { NET, SUBNET, ORIGINAL, DIFFERENT_NET }; static struct routebox_list * __select_list (routebox_t * r, enum boxlist which) { assert (r); switch (which) { default: assert (0); case NET: return &(r->same_net); case SUBNET: return &(r->same_subnet); case ORIGINAL: return &(r->original_subnet); case DIFFERENT_NET: return &(r->different_net); } } static void InitLists (routebox_t * r) { static enum boxlist all[] = { NET, SUBNET, ORIGINAL, DIFFERENT_NET } , *p; for (p = all; p < all + (sizeof (all) / sizeof (*p)); p++) { struct routebox_list *rl = __select_list (r, *p); rl->prev = rl->next = r; } } static void MergeNets (routebox_t * a, routebox_t * b, enum boxlist which) { struct routebox_list *al, *bl, *anl, *bnl; routebox_t *an, *bn; assert (a && b); assert (a != b); al = __select_list (a, which); bl = __select_list (b, which); assert (al && bl); an = al->next; bn = bl->next; assert (an && bn); anl = __select_list (an, which); bnl = __select_list (bn, which); assert (anl && bnl); bl->next = an; anl->prev = b; al->next = bn; bnl->prev = a; } static void RemoveFromNet (routebox_t * a, enum boxlist which) { struct routebox_list *al, *anl, *apl; routebox_t *an, *ap; assert (a); al = __select_list (a, which); assert (al); an = al->next; ap = al->prev; if (an == a || ap == a) return; /* not on any list */ assert (an && ap); anl = __select_list (an, which); apl = __select_list (ap, which); assert (anl && apl); anl->prev = ap; apl->next = an; al->next = al->prev = a; return; } static void init_const_box (routebox_t * rb, LocationType X1, LocationType Y1, LocationType X2, LocationType Y2) { BoxType *bp = (BoxType *) & rb->box; /* note discarding const! */ assert (!rb->flags.inited); assert (X1 <= X2 && Y1 <= Y2); bp->X1 = X1; bp->Y1 = Y1; bp->X2 = X2; bp->Y2 = Y2; rb->flags.inited = 1; } /*--------------------------------------------------------------------- * routedata initialization functions. */ static Boolean is_layer_group_active (Cardinal group) { int i; assert (0 <= group && group < MAX_LAYER); for (i = 0; i < PCB->LayerGroups.Number[group]; i++) /* layer must be 1) not silk (ie, < MAX_LAYER) and 2) on */ if ((PCB->LayerGroups.Entries[group][i] < MAX_LAYER) && PCB->Data->Layer[PCB->LayerGroups.Entries[group][i]].On) return True; /* this layer group is active. */ return False; } static void AddPin (PointerListType layergroupboxes[], PinTypePtr pin, Boolean is_via) { routebox_t **rbpp, *lastrb = NULL; int i; /* a pin cuts through every layer group */ for (i = 0; i < MAX_LAYER; i++) { rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[i]); *rbpp = malloc (sizeof (**rbpp)); (*rbpp)->group = i; init_const_box (*rbpp, /*X1 */ pin->X - HALF_THICK (pin->Thickness), /*Y1 */ pin->Y - HALF_THICK (pin->Thickness), /*X2 */ pin->X + HALF_THICK (pin->Thickness), /*Y2 */ pin->Y + HALF_THICK (pin->Thickness)); /* set aux. properties */ if (is_via) { (*rbpp)->type = VIA; (*rbpp)->parent.via = pin; } else { (*rbpp)->type = PIN; (*rbpp)->parent.pin = pin; } (*rbpp)->flags.fixed = 1; (*rbpp)->flags.circular = !TEST_FLAG (SQUAREFLAG, pin); /* circular lists */ InitLists (*rbpp); /* link together */ if (lastrb) { MergeNets (*rbpp, lastrb, NET); MergeNets (*rbpp, lastrb, SUBNET); MergeNets (*rbpp, lastrb, ORIGINAL); } lastrb = *rbpp; } return; } static void AddPad (PointerListType layergroupboxes[], ElementTypePtr element, PadTypePtr pad) { BDimension halfthick; routebox_t **rbpp; int layergroup = TEST_FLAG (ONSOLDERFLAG, pad) ? back : front; assert (0 <= layergroup && layergroup < MAX_LAYER); assert (PCB->LayerGroups.Number[layergroup] > 0); rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]); assert (rbpp); *rbpp = malloc (sizeof (**rbpp)); assert (*rbpp); (*rbpp)->group = layergroup; halfthick = HALF_THICK (pad->Thickness); init_const_box (*rbpp, /*X1 */ MIN (pad->Point1.X, pad->Point2.X) - halfthick, /*Y1 */ MIN (pad->Point1.Y, pad->Point2.Y) - halfthick, /*X2 */ MAX (pad->Point1.X, pad->Point2.X) + halfthick, /*Y2 */ MAX (pad->Point1.Y, pad->Point2.Y) + halfthick); /* kludge for non-manhattan pads */ if (pad->Point1.X != pad->Point2.X && pad->Point1.Y != pad->Point2.Y) (*rbpp)->flags.nonstraight = 1; /* set aux. properties */ (*rbpp)->type = PAD; (*rbpp)->parent.pad = pad; (*rbpp)->flags.fixed = 1; /* circular lists */ InitLists (*rbpp); return; } static void AddLine (PointerListType layergroupboxes[], int layer, LineTypePtr line) { routebox_t **rbpp; int layergroup; assert (layergroupboxes && line); assert (0 <= layer && layer < MAX_LAYER); layergroup = GetLayerGroupNumberByNumber (layer); assert (0 <= layergroup && layergroup < MAX_LAYER); assert (PCB->LayerGroups.Number[layergroup] > 0); rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]); *rbpp = malloc (sizeof (**rbpp)); (*rbpp)->group = layergroup; init_const_box (*rbpp, /*X1 */ MIN (line->Point1.X, line->Point2.X) - HALF_THICK (line->Thickness), /*Y1 */ MIN (line->Point1.Y, line->Point2.Y) - HALF_THICK (line->Thickness), /*X2 */ MAX (line->Point1.X, line->Point2.X) + HALF_THICK (line->Thickness), /*Y2 */ MAX (line->Point1.Y, line->Point2.Y) + HALF_THICK (line->Thickness)); /* kludge for non-manhattan lines */ if (line->Point1.X != line->Point2.X && line->Point1.Y != line->Point2.Y) { (*rbpp)->flags.nonstraight = 1; (*rbpp)->flags.bl_to_ur = (MIN (line->Point1.X, line->Point2.X) == line->Point1.X) != (MIN (line->Point1.Y, line->Point2.Y) == line->Point1.Y); } /* set aux. properties */ (*rbpp)->type = LINE; (*rbpp)->parent.line = line; (*rbpp)->flags.fixed = 1; /* circular lists */ InitLists (*rbpp); return; } static routebox_t * AddIrregularObstacle (PointerListType layergroupboxes[], LocationType X1, LocationType Y1, LocationType X2, LocationType Y2, Cardinal layer, void *parent) { routebox_t **rbpp; int layergroup; assert (layergroupboxes && parent); assert (0 <= layer && layer < MAX_LAYER); assert (X1 <= X2 && Y1 <= Y2); layergroup = GetLayerGroupNumberByNumber (layer); assert (0 <= layergroup && layergroup < MAX_LAYER); assert (PCB->LayerGroups.Number[layergroup] > 0); rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]); *rbpp = malloc (sizeof (**rbpp)); (*rbpp)->group = layergroup; init_const_box (*rbpp, X1, Y1, X2, Y2); (*rbpp)->flags.nonstraight = 1; (*rbpp)->type = OTHER; (*rbpp)->parent.generic = parent; (*rbpp)->flags.fixed = 1; /* circular lists */ InitLists (*rbpp); return *rbpp; } static void AddPolygon (PointerListType layergroupboxes[], Cardinal layer, PolygonTypePtr polygon) { int is_not_rectangle = 1; routebox_t *rb = AddIrregularObstacle (layergroupboxes, polygon->BoundingBox.X1, polygon->BoundingBox.Y1, polygon->BoundingBox.X2, polygon->BoundingBox.Y2, layer, polygon); if (polygon->PointN == 4 && (polygon->Points[0].X == polygon->Points[1].X || polygon->Points[0].Y == polygon->Points[1].Y) && (polygon->Points[1].X == polygon->Points[2].X || polygon->Points[1].Y == polygon->Points[2].Y) && (polygon->Points[2].X == polygon->Points[3].X || polygon->Points[2].Y == polygon->Points[3].Y) && (polygon->Points[3].X == polygon->Points[0].X || polygon->Points[3].Y == polygon->Points[0].Y)) is_not_rectangle = 0; rb->flags.nonstraight = is_not_rectangle; rb->layer = layer; if (TEST_FLAG (CLEARPOLYFLAG, polygon)) { rb->flags.clear_poly = 1; if (!is_not_rectangle) rb->type = PLANE; } } static void AddText (PointerListType layergroupboxes[], Cardinal layer, TextTypePtr text) { AddIrregularObstacle (layergroupboxes, text->BoundingBox.X1, text->BoundingBox.Y1, text->BoundingBox.X2, text->BoundingBox.Y2, layer, text); } static void AddArc (PointerListType layergroupboxes[], Cardinal layer, ArcTypePtr arc) { AddIrregularObstacle (layergroupboxes, arc->BoundingBox.X1, arc->BoundingBox.Y1, arc->BoundingBox.X2, arc->BoundingBox.Y2, layer, arc); } struct find_closure { routebox_t *match; void *key; }; static int __found_one (const BoxType * box, void *cl) { struct find_closure *fc = (struct find_closure *) cl; routebox_t *rb = (routebox_t *) box; if (fc->key == rb->parent.generic) { fc->match = rb; return 1; } else return 0; } static routebox_t * FindRouteBox (routedata_t * rd, LocationType X, LocationType Y, void *matches) { struct find_closure fc; BoxType region; int group; fc.match = NULL; fc.key = matches; region.X1 = region.X2 = X; region.Y1 = region.Y2 = Y; for (group = 0; group < MAX_LAYER; group++) if (r_search (rd->layergrouptree[group], ®ion, NULL, __found_one, &fc)) return fc.match; return NULL; /* no match found */ } static int __found_one_on_lg (const BoxType * box, void *cl) { routebox_t **rb = (routebox_t **) cl; *rb = (routebox_t *) box; return 1; } static routebox_t * FindRouteBoxOnLayerGroup (routedata_t * rd, LocationType X, LocationType Y, Cardinal layergroup) { routebox_t *rb; BoxType region; region.X1 = region.X2 = X; region.Y1 = region.Y2 = Y; if (r_search (rd->layergrouptree[layergroup], ®ion, NULL, __found_one_on_lg, &rb)) return rb; return NULL; /* no match found */ } #ifdef ROUTE_DEBUG static void DumpRouteBox (routebox_t * rb) { printf ("RB: (%d,%d)-(%d,%d) l%d; ", rb->box.X1, rb->box.Y1, rb->box.X2, rb->box.Y2, (int) rb->group); switch (rb->type) { case PAD: printf ("PAD[%s %s] ", rb->parent.pad->Name, rb->parent.pad->Number); break; case PIN: printf ("PIN[%s %s] ", rb->parent.pin->Name, rb->parent.pin->Number); break; case VIA: if (!rb->parent.via) break; printf ("VIA[%s %s] ", rb->parent.via->Name, rb->parent.via->Number); break; case LINE: printf ("LINE "); break; case OTHER: printf ("OTHER "); break; case EXPANSION_AREA: printf ("EXPAREA "); break; default: printf ("UNKNOWN "); break; } if (rb->flags.nonstraight) printf ("(nonstraight) "); if (rb->flags.fixed) printf ("(fixed) "); if (rb->flags.source) printf ("(source) "); if (rb->flags.target) printf ("(target) "); if (rb->flags.orphan) printf ("(orphan) "); printf ("\n"); } #endif static routedata_t * CreateRouteData () { BDimension nearest = Settings.Keepaway; NetListListType Nets; PointerListType layergroupboxes[MAX_LAYER]; BoxType bbox; routedata_t *rd; Boolean other = True; int i; front = GetLayerGroupNumberByNumber (MAX_LAYER + COMPONENT_LAYER); back = GetLayerGroupNumberByNumber (MAX_LAYER + SOLDER_LAYER); /* determine prefered routing direction on each group */ for (i = 0; i < MAX_LAYER; i++) { if (i != back && i != front) { bad_x[i] = other; other = !other; bad_y[i] = other; } else { bad_x[i] = False; bad_y[i] = False; } } /* create routedata */ rd = malloc (sizeof (*rd)); /* create default style */ rd->defaultStyle.Thick = Settings.LineThickness; rd->defaultStyle.Diameter = Settings.ViaThickness; rd->defaultStyle.Hole = Settings.ViaDrillingHole; rd->defaultStyle.Keepaway = Settings.Keepaway; rd->max_bloat = BLOAT (&rd->defaultStyle); /* create augStyles structures */ bbox.X1 = bbox.Y1 = 0; bbox.X2 = PCB->MaxWidth; bbox.Y2 = PCB->MaxHeight; for (i = 0; i < NUM_STYLES + 1; i++) { RouteStyleType *style = (i < NUM_STYLES) ? &PCB->RouteStyle[i] : &rd->defaultStyle; rd->augStyles[i].style = style; rd->augStyles[i].Used = False; } /* initialize pointerlisttype */ for (i = 0; i < MAX_LAYER; i++) { layergroupboxes[i].Ptr = NULL; layergroupboxes[i].PtrN = 0; layergroupboxes[i].PtrMax = 0; } /* add pins and pads of elements */ ALLPIN_LOOP (PCB->Data); { AddPin (layergroupboxes, pin, False); } ENDALL_LOOP; ALLPAD_LOOP (PCB->Data); { AddPad (layergroupboxes, element, pad); } ENDALL_LOOP; /* add all vias */ VIA_LOOP (PCB->Data); { AddPin (layergroupboxes, via, True); } END_LOOP; for (i = 0; i < MAX_LAYER; i++) { /* add all (non-rat) lines */ LINE_LOOP (LAYER_PTR (i)); { AddLine (layergroupboxes, i, line); } END_LOOP; /* add all "should-avoid" polygons */ POLYGON_LOOP (LAYER_PTR (i)); { AddPolygon (layergroupboxes, i, polygon); } END_LOOP; /* add all copper text */ TEXT_LOOP (LAYER_PTR (i)); { AddText (layergroupboxes, i, text); } END_LOOP; /* add all arcs */ ARC_LOOP (LAYER_PTR (i)); { AddArc (layergroupboxes, i, arc); } END_LOOP; } /* create r-trees from pointer lists */ for (i = 0; i < MAX_LAYER; i++) { /* initialize style (we'll fill in a "real" style later, when we add * the connectivity information) */ POINTER_LOOP (&layergroupboxes[i]); { /* we're initializing this to the "default" style */ ((routebox_t *) * ptr)->augStyle = &rd->augStyles[NUM_STYLES]; } END_LOOP; /* create the r-tree */ rd->layergrouptree[i] = r_create_tree ((const BoxType **) layergroupboxes[i].Ptr, layergroupboxes[i].PtrN, 1); } /* now add connectivity/style information */ Nets = CollectSubnets (False); { routebox_t *last_net = NULL; NETLIST_LOOP (&Nets); { routebox_t *last_in_net = NULL; NET_LOOP (netlist); { routebox_t *last_in_subnet = NULL; CONNECTION_LOOP (net); { routebox_t *rb, *tmp; int j; for (j = 0; j < NUM_STYLES; j++) if (net->Style == rd->augStyles[j].style) break; rb = FindRouteBox (rd, connection->X, connection->Y, connection->ptr2); if (!rb) continue; /* XXX: set rb->augStyle! */ rb->augStyle = &rd->augStyles[j]; rb->augStyle->Used = True; /* traces are listed twice, at start point and at end point */ if (rb != last_in_subnet) { /* update circular connectivity lists */ if (last_in_subnet) MergeNets (last_in_subnet, rb, ORIGINAL); if (last_in_net) MergeNets (last_in_net, rb, NET); last_in_subnet = last_in_net = rb; rd->max_bloat = MAX (rd->max_bloat, BLOAT (rb->augStyle->style)); } LIST_LOOP (rb, same_net, tmp); { tmp->augStyle = &rd->augStyles[j]; } END_LOOP; } END_LOOP; } END_LOOP; if (last_net && last_in_net) MergeNets (last_net, last_in_net, DIFFERENT_NET); last_net = last_in_net; } END_LOOP; rd->first_net = last_net; } FreeNetListListMemory (&Nets); /* reset all nets to "original" connectivity (which we just set) */ { routebox_t *net; LIST_LOOP (rd->first_net, different_net, net); ResetSubnet (net); END_LOOP; } /* find smallest keepaway for mtspace */ for (i = 0; i < NUM_STYLES + 1; i++) { RouteStyleType *style = (i < NUM_STYLES) ? &PCB->RouteStyle[i] : &rd->defaultStyle; MAKEMIN (nearest, style->Keepaway); } rd->mtspace = mtspace_create (&bbox, nearest); /* create "empty-space" structures for via placement (now that we know * appropriate keepaways for all the fixed elements) */ for (i = 0; i < MAX_LAYER; i++) { POINTER_LOOP (&layergroupboxes[i]); { routebox_t *rb = (routebox_t *) * ptr; if (!rb->flags.clear_poly) mtspace_add (rd->mtspace, &rb->box, FIXED, rb->augStyle->style->Keepaway); } END_LOOP; } /* free pointer lists */ for (i = 0; i < MAX_LAYER; i++) FreePointerListMemory (&layergroupboxes[i]); /* done! */ return rd; } void DestroyRouteData (routedata_t ** rd) { int i; for (i = 0; i < MAX_LAYER; i++) r_destroy_tree (&(*rd)->layergrouptree[i]); mtspace_destroy (&(*rd)->mtspace); free (*rd); *rd = NULL; } /*----------------------------------------------------------------- * routebox reference counting. */ /* increment the reference count on a routebox. */ static void RB_up_count (routebox_t * rb) { assert (rb->flags.orphan); rb->refcount++; } /* decrement the reference count on a routebox, freeing if this box becomes * unused. */ static void RB_down_count (routebox_t * rb) { assert (rb->flags.orphan); assert (rb->refcount > 0); if (--rb->refcount == 0) { /* rb->underlying is guaranteed to not be an orphan, so we only need * to downcount the parent, if type==EXPANSION_AREA */ if (rb->type == EXPANSION_AREA && rb->parent.expansion_area->flags.orphan) RB_down_count (rb->parent.expansion_area); free (rb); } } /*----------------------------------------------------------------- * Rectangle-expansion routing code. */ static void ResetSubnet (routebox_t * net) { routebox_t *rb; /* reset connectivity of everything on this net */ LIST_LOOP (net, same_net, rb); rb->same_subnet = rb->original_subnet; END_LOOP; } static cost_t cost_to_point_on_layer (const CheapPointType * p1, const CheapPointType * p2, Cardinal point_layer) { cost_t x_dist = ABS (p1->X - p2->X), y_dist = ABS (p1->Y - p2->Y), r = 0; if (bad_x[point_layer]) x_dist *= AutoRouteParameters.DirectionPenalty; else if (bad_y[point_layer]) y_dist *= AutoRouteParameters.DirectionPenalty; /* cost is proportional to orthogonal distance. */ r = x_dist + y_dist; /* penalize the surface layers in order to minimize SMD pad congestion */ if (point_layer == front || point_layer == back) r *= AutoRouteParameters.SurfacePenalty; return r; } static cost_t cost_to_point (const CheapPointType * p1, Cardinal point_layer1, const CheapPointType * p2, Cardinal point_layer2) { cost_t r = cost_to_point_on_layer (p1, p2, point_layer1); /* apply via cost penalty if layers differ */ if (point_layer1 != point_layer2) r += AutoRouteParameters.ViaCost; return r; } /* return the minimum *cost* from a point to a box on any layer. * It's safe to return a smaller than minimum cost */ static cost_t cost_to_layerless_box (const CheapPointType * p, Cardinal point_layer, const BoxType * b) { CheapPointType p2 = closest_point_in_box (p, b); /* front layer has no prefered direction so it's cheapest */ return ABS (p2.X - p->X) + ABS (p2.Y - p->Y); } /* return the minimum *cost* from a point to a route box, including possible * via costs if the route box is on a different layer. */ static cost_t cost_to_routebox (const CheapPointType * p, Cardinal point_layer, const routebox_t * rb) { cost_t trial; CheapPointType p2 = closest_point_in_box (p, &rb->box); if (point_layer == rb->group) return cost_to_point_on_layer (p, &p2, rb->group); trial = AutoRouteParameters.ViaCost; trial += MIN (cost_to_point_on_layer (p, &p2, point_layer), cost_to_point_on_layer (p, &p2, rb->group)); return trial; } static BoxType bloat_routebox (routebox_t * rb) { BoxType r; BDimension keepaway; assert (__routebox_is_good (rb)); if (rb->type == EXPANSION_AREA || rb->flags.nobloat) return rb->box; /* no bloat */ /* obstacle exclusion zones get bloated, and then shrunk on their * top and left sides so that they approximate their "open" * brethern. */ keepaway = MAX (AutoRouteParameters.augStyle->style->Keepaway, rb->augStyle->style->Keepaway); r = bloat_box (&rb->box, keepaway + HALF_THICK (AutoRouteParameters.augStyle->style->Thick)); r.X1++; r.Y1++; return r; } #ifdef ROUTE_DEBUG /* only for debugging expansion areas */ /* makes a line on the solder layer silk surrounding the box */ static void showbox (BoxType b, Dimension thickness, int group) { LineTypePtr line; LayerTypePtr SLayer = LAYER_PTR (group); gdk_gc_set_line_attributes (Output.fgGC, thickness, GDK_LINE_SOLID, GDK_CAP_ROUND, GDK_JOIN_ROUND); gdk_gc_set_foreground (Output.fgGC, SLayer->Color); XDrawLine (Output.top_window->window, Output.fgGC, b.X1, b.Y1, b.X2, b.Y1); XDrawLine (Output.top_window->window, Output.fgGC, b.X1, b.Y2, b.X2, b.Y2); XDrawLine (Output.top_window->window, Output.fgGC, b.X1, b.Y1, b.X1, b.Y2); XDrawLine (Output.top_window->window, Output.fgGC, b.X2, b.Y1, b.X2, b.Y2); #if XXX if (XtAppPending (Context)) XtAppProcessEvent (Context, XtIMAll); XSync (Dpy, False); #endif if (b.Y1 == b.Y2 || b.X1 == b.X2) thickness = 5; line = CreateNewLineOnLayer (LAYER_PTR (MAX_LAYER + COMPONENT_LAYER), b.X1, b.Y1, b.X2, b.Y1, thickness, 0, 0); AddObjectToCreateUndoList (LINE_TYPE, LAYER_PTR (MAX_LAYER + COMPONENT_LAYER), line, line); if (b.Y1 != b.Y2) { line = CreateNewLineOnLayer (LAYER_PTR (MAX_LAYER + COMPONENT_LAYER), b.X1, b.Y2, b.X2, b.Y2, thickness, 0, 0); AddObjectToCreateUndoList (LINE_TYPE, LAYER_PTR (MAX_LAYER + COMPONENT_LAYER), line, line); } line = CreateNewLineOnLayer (LAYER_PTR (MAX_LAYER + COMPONENT_LAYER), b.X1, b.Y1, b.X1, b.Y2, thickness, 0, 0); AddObjectToCreateUndoList (LINE_TYPE, LAYER_PTR (MAX_LAYER + COMPONENT_LAYER), line, line); if (b.X1 != b.X2) { line = CreateNewLineOnLayer (LAYER_PTR (MAX_LAYER + COMPONENT_LAYER), b.X2, b.Y1, b.X2, b.Y2, thickness, 0, 0); AddObjectToCreateUndoList (LINE_TYPE, LAYER_PTR (MAX_LAYER + COMPONENT_LAYER), line, line); } } #endif #if defined(ROUTE_DEBUG) static void showedge (edge_t * e) { BoxType *b = (BoxType *) e->rb; gdk_gc_set_line_attributes (Output.fgGC, 1, GDK_LINE_SOLID, GDK_CAP_ROUND, GDK_JOIN_ROUND); gdk_gc_set_foreground (Output.fgGC, &Settings.MaskColor); switch (e->expand_dir) { case NORTH: XDrawCLine (Output.top_window->window, Output.fgGC, b->X1, b->Y1, b->X2, b->Y1); break; case SOUTH: XDrawCLine (Output.top_window->window, Output.fgGC, b->X1, b->Y2, b->X2, b->Y2); break; case WEST: XDrawCLine (Output.top_window->window, Output.fgGC, b->X1, b->Y1, b->X1, b->Y2); break; case EAST: XDrawCLine (Output.top_window->window, Output.fgGC, b->X2, b->Y1, b->X2, b->Y2); break; } } #endif #if defined(ROUTE_DEBUG) static void showroutebox (routebox_t * rb) { showbox (rb->box, rb->flags.source ? 5 : 3, rb->flags.is_via ? MAX_LAYER + COMPONENT_LAYER : rb->group); } #endif static void EraseRouteBox (routebox_t * rb) { LocationType X1, Y1, X2, Y2; BDimension thick; if (rb->box.X2 - rb->box.X1 < rb->box.Y2 - rb->box.Y1) { thick = rb->box.X2 - rb->box.X1; X1 = X2 = (rb->box.X2 + rb->box.X1) / 2; Y1 = rb->box.Y1 + thick / 2; Y2 = rb->box.Y2 - thick / 2; } else { thick = rb->box.Y2 - rb->box.Y1; Y1 = Y2 = (rb->box.Y2 + rb->box.Y1) / 2; X1 = rb->box.X1 + thick / 2; X2 = rb->box.X2 - thick / 2; } #ifdef FIXME gdk_gc_set_line_attributes (Output.fgGC, TO_SCREEN (thick), GDK_LINE_SOLID, GDK_CAP_ROUND, GDK_JOIN_ROUND); gdk_gc_set_foreground (Output.fgGC, &Settings.BackgroundColor); XDrawCLine (Output.top_window->window, Output.fgGC, X1, Y1, X2, Y2); #endif } /* return a "parent" of this edge which immediately precedes it in the route.*/ static routebox_t * route_parent (routebox_t * rb) { while (rb->flags.orphan && rb->underlying == NULL && !rb->flags.is_via) { assert (rb->type == EXPANSION_AREA); rb = rb->parent.expansion_area; assert (rb); } return rb; } /* return a "parent" of this edge which resides in a r-tree somewhere */ /* -- actually, this "parent" *may* be a via box, which doesn't live in * a r-tree. -- */ static routebox_t * nonorphan_parent (routebox_t * rb) { rb = route_parent (rb); return rb->underlying ? rb->underlying : rb; } /* some routines to find the minimum *cost* from a cost point to * a target (any target) */ struct mincost_target_closure { const CheapPointType *CostPoint; Cardinal CostPointLayer; routebox_t *nearest; cost_t nearest_cost; }; static int __region_within_guess (const BoxType * region, void *cl) { struct mincost_target_closure *mtc = (struct mincost_target_closure *) cl; cost_t cost_to_region; if (mtc->nearest == NULL) return 1; cost_to_region = cost_to_layerless_box (mtc->CostPoint, mtc->CostPointLayer, region); assert (cost_to_region >= 0); /* if no guess yet, all regions are "close enough" */ /* note that cost is *strictly more* than minimum distance, so we'll * always search a region large enough. */ return (cost_to_region < mtc->nearest_cost); } static int __found_new_guess (const BoxType * box, void *cl) { struct mincost_target_closure *mtc = (struct mincost_target_closure *) cl; routebox_t *guess = (routebox_t *) box; cost_t cost_to_guess = cost_to_routebox (mtc->CostPoint, mtc->CostPointLayer, guess); assert (cost_to_guess >= 0); /* if we don't have a guess yet, or this is cheaper than previous guess... */ if (mtc->nearest == NULL || cost_to_guess < mtc->nearest_cost) { mtc->nearest = guess; mtc->nearest_cost = cost_to_guess; /* this is our new guess! */ return 1; } else return 0; /* not less expensive than our last guess */ } /* target_guess is our guess at what the nearest target is, or NULL if we * just plum don't have a clue. */ static routebox_t * mincost_target_to_point (const CheapPointType * CostPoint, Cardinal CostPointLayer, rtree_t * targets, routebox_t * target_guess) { struct mincost_target_closure mtc; assert (target_guess == NULL || target_guess->flags.target); /* this is a target, right? */ mtc.CostPoint = CostPoint; mtc.CostPointLayer = CostPointLayer; mtc.nearest = target_guess; if (mtc.nearest) mtc.nearest_cost = cost_to_routebox (mtc.CostPoint, mtc.CostPointLayer, mtc.nearest); r_search (targets, NULL, __region_within_guess, __found_new_guess, &mtc); assert (mtc.nearest != NULL && mtc.nearest_cost >= 0); assert (mtc.nearest->flags.target); /* this is a target, right? */ return mtc.nearest; } /* create edge from field values */ /* mincost_target_guess can be NULL */ static edge_t * CreateEdge (routebox_t * rb, LocationType CostPointX, LocationType CostPointY, cost_t cost_to_point, routebox_t * mincost_target_guess, direction_t expand_dir, rtree_t * targets) { edge_t *e; assert (__routebox_is_good (rb)); e = malloc (sizeof (*e)); assert (e); e->rb = rb; if (rb->flags.orphan) RB_up_count (rb); e->cost_point.X = CostPointX; e->cost_point.Y = CostPointY; e->cost_to_point = cost_to_point; /* if this is edge is created in response to a target, use it */ if (targets) e->mincost_target = mincost_target_to_point (&e->cost_point, rb->group, targets, mincost_target_guess); else e->mincost_target = mincost_target_guess; e->expand_dir = expand_dir; assert (e->rb && e->mincost_target); /* valid edge? */ assert (!e->flags.is_via || e->flags.expand_all_sides); /* cost point should be on edge (unless this is a plane/via/conflict edge) */ assert (rb->type == PLANE || rb->underlying != NULL || rb->flags.is_via || ((expand_dir == NORTH || expand_dir == SOUTH) ? rb->box.X1 <= CostPointX && CostPointX <= rb->box.X2 && CostPointY == (expand_dir == NORTH ? rb->box.Y1 : rb->box.Y2) : /* expand_dir==EAST || expand_dir==WEST */ rb->box.Y1 <= CostPointY && CostPointY <= rb->box.Y2 && CostPointX == (expand_dir == EAST ? rb->box.X2 : rb->box.X1))); assert (__edge_is_good (e)); /* done */ return e; } /* create edge, using previous edge to fill in defaults. */ /* most of the work here is in determining a new cost point */ static edge_t * CreateEdge2 (routebox_t * rb, direction_t expand_dir, edge_t * previous_edge, rtree_t * targets, routebox_t * guess) { BoxType thisbox; CheapPointType thiscost, prevcost; cost_t d; assert (rb && previous_edge); /* okay, find closest costpoint to costpoint of previous edge */ thisbox = edge_to_box (&rb->box, expand_dir); prevcost = previous_edge->cost_point; thiscost = closest_point_in_box (&prevcost, &thisbox); /* compute cost-to-point */ d = cost_to_point_on_layer (&prevcost, &thiscost, rb->group); /* add in jog penalty */ if (previous_edge->expand_dir != expand_dir) d += AutoRouteParameters.JogPenalty; /* okay, new edge! */ return CreateEdge (rb, thiscost.X, thiscost.Y, previous_edge->cost_to_point + d, guess ? guess : previous_edge->mincost_target, expand_dir, targets); } /* create via edge, using previous edge to fill in defaults. */ static edge_t * CreateViaEdge (const BoxType * area, Cardinal group, routebox_t * parent, edge_t * previous_edge, conflict_t to_site_conflict, conflict_t through_site_conflict, rtree_t * targets) { routebox_t *rb; CheapPointType costpoint; cost_t d; edge_t *ne; cost_t scale[3]; scale[0] = 1; scale[1] = AutoRouteParameters.LastConflictPenalty; scale[2] = AutoRouteParameters.ConflictPenalty; assert (__box_is_good (area)); assert (AutoRouteParameters.with_conflicts || (to_site_conflict == NO_CONFLICT && through_site_conflict == NO_CONFLICT)); rb = CreateExpansionArea (area, group, parent, True, previous_edge); rb->flags.is_via = 1; #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_VIA_BOXES) showroutebox (rb); #endif /* ROUTE_DEBUG && DEBUG_SHOW_VIA_BOXES */ /* for planes, choose a point near the target */ if (parent->type == PLANE) { routebox_t *target; CheapPointType pnt; /* find a target near this via box */ pnt.X = (area->X2 + area->X1) / 2; pnt.Y = (area->Y2 + area->Y1) / 2; target = mincost_target_to_point (&pnt, rb->group, targets, previous_edge->mincost_target); /* now find point near the target */ pnt.X = (target->box.X1 + target->box.X2) / 2; pnt.Y = (target->box.Y1 + target->box.Y2) / 2; costpoint = closest_point_in_box (&pnt, &rb->box); d = (scale[through_site_conflict] * cost_to_point (&costpoint, group, &costpoint, previous_edge->rb->group)); ne = CreateEdge (rb, costpoint.X, costpoint.Y, previous_edge->cost_to_point + d, target, NORTH /*arbitrary */ , NULL); } else { costpoint = closest_point_in_box (&previous_edge->cost_point, &rb->box); d = (scale[to_site_conflict] * cost_to_point_on_layer (&costpoint, &previous_edge->cost_point, previous_edge->rb->group)) + (scale[through_site_conflict] * cost_to_point (&costpoint, group, &costpoint, previous_edge->rb->group)); ne = CreateEdge (rb, costpoint.X, costpoint.Y, previous_edge->cost_to_point + d, previous_edge->mincost_target, NORTH /*arbitrary */ , targets); } ne->flags.expand_all_sides = ne->flags.is_via = 1; ne->flags.via_conflict_level = to_site_conflict; assert (__edge_is_good (ne)); return ne; } /* create "interior" edge for routing with conflicts */ static edge_t * CreateEdgeWithConflicts (const BoxType * interior_edge, routebox_t * container, edge_t * previous_edge, cost_t cost_penalty_to_box, rtree_t * targets) { routebox_t *rb; BoxType b; CheapPointType costpoint; cost_t d; edge_t *ne; assert (interior_edge && container && previous_edge && targets); assert (!container->flags.orphan); assert (AutoRouteParameters.with_conflicts); /* create expansion area equal to the bloated container. Put costpoint * in this box. compute cost, but add jog penalty. */ b = bloat_routebox (container); assert (previous_edge->rb->group == container->group); rb = CreateExpansionArea (&b, previous_edge->rb->group, previous_edge->rb, True, previous_edge); rb->underlying = container; /* crucial! */ costpoint = closest_point_in_box (&previous_edge->cost_point, &b); d = cost_to_point_on_layer (&costpoint, &previous_edge->cost_point, previous_edge->rb->group); d *= cost_penalty_to_box; ne = CreateEdge (rb, costpoint.X, costpoint.Y, previous_edge->cost_to_point + d, previous_edge->mincost_target, NORTH /*arbitrary */ , targets); ne->flags.expand_all_sides = ne->flags.is_interior = 1; assert (__edge_is_good (ne)); return ne; } static void DestroyEdge (edge_t ** e) { assert (e && *e); if ((*e)->rb->flags.orphan) RB_down_count ((*e)->rb); /* possibly free rb */ free (*e); *e = NULL; } /* cost function for an edge. */ static cost_t edge_cost (const edge_t * e) { if (e->rb->type == PLANE) return 1; /* thermals are cheap */ /* we should penalize an edge that will expand to choke-off a bunch * of pads i.e. it's on a pad layer, and there is a pad with +/- a few vias * rectangle from the edge but I don't know how to do that easily */ /* cost_to_routebox adds in our via correction, too. */ return e->cost_to_point + cost_to_routebox (&e->cost_point, e->rb->group, e->mincost_target); } static LocationType edge_length (const BoxType * cb, direction_t expand_dir) { BoxType b = *cb; ROTATEBOX_TO_NORTH (b, expand_dir); assert (b.X1 <= b.X2); return b.X2 - b.X1; } /* return a bounding box for the PCB board. */ static BoxType pcb_bounds (void) { BoxType b; b.X1 = 0; b.X2 = PCB->MaxWidth; b.Y1 = 0; b.Y2 = PCB->MaxHeight; /* adjust from closed to half-closed box */ b.X2++; b.Y2++; /* done */ return b; } static BoxType shrunk_pcb_bounds () { BoxType b = pcb_bounds (); return shrink_box (&b, AutoRouteParameters.augStyle->style->Keepaway + HALF_THICK (AutoRouteParameters.augStyle->style->Thick)); } /* create a maximal expansion region from the specified edge to the edge * of the PCB (minus the required keepaway). */ static BoxType edge_to_infinity_region (edge_t * e) { BoxType max, ebox; ebox = e->rb->box; max = shrunk_pcb_bounds (); /* normalize to north */ ROTATEBOX_TO_NORTH (max, e->expand_dir); ROTATEBOX_TO_NORTH (ebox, e->expand_dir); /* north case: */ max.X1 = ebox.X1; max.X2 = ebox.X2; max.Y2 = ebox.Y1; /* unnormalize */ ROTATEBOX_FROM_NORTH (max, e->expand_dir); /* done */ return max; } /* given an edge of a box, return a box containing exactly the points on that * edge. Note that the box is treated as closed; that is, the bottom and * right "edges" consist of points (just barely) not in the (half-open) box. */ static BoxType edge_to_box (const BoxType * box, direction_t expand_dir) { BoxType b = *box; /* narrow box down to just the appropriate edge */ switch (expand_dir) { case NORTH: b.Y2 = b.Y1; break; case EAST: b.X1 = b.X2; break; case SOUTH: b.Y1 = b.Y2; break; case WEST: b.X2 = b.X1; break; default: assert (0); } /* treat b as *closed* instead of half-closed, by adding one to * the (normally-open) bottom and right edges. */ b.X2++; b.Y2++; /* done! */ return b; } /* limit the specified expansion region so that it just touches the * given limit. Returns 1 if the limited region has any area. */ static BoxType limit_region (BoxType region, edge_t * e, BoxType lbox) { ROTATEBOX_TO_NORTH (region, e->expand_dir); ROTATEBOX_TO_NORTH (lbox, e->expand_dir); /* north case: */ assert (lbox.Y2 >= region.Y1); /* validity of limiter */ assert (lbox.X1 <= region.X2); assert (lbox.X2 >= region.X1); region.Y1 = lbox.Y2; /* this can fail if starting copper violates spacing rule */ /* assert (region.Y1 <= region.Y2); */ /* now rotate back */ ROTATEBOX_FROM_NORTH (region, e->expand_dir); return region; } struct broken_boxes { BoxType left, center, right; Boolean is_valid_left, is_valid_center, is_valid_right; }; static struct broken_boxes break_box_edge (const BoxType * original, direction_t which_edge, routebox_t * breaker) { BoxType origbox, breakbox; struct broken_boxes result; assert (original && breaker); origbox = *original; breakbox = bloat_routebox (breaker); ROTATEBOX_TO_NORTH (origbox, which_edge); ROTATEBOX_TO_NORTH (breakbox, which_edge); result.right.Y1 = result.right.Y2 = result.center.Y1 = result.center.Y2 = result.left.Y1 = result.left.Y2 = origbox.Y1; /* validity of breaker */ assert (breakbox.X1 < origbox.X2 && breakbox.X2 > origbox.X1); /* left edge piece */ result.left.X1 = origbox.X1; result.left.X2 = breakbox.X1; /* center (ie blocked) edge piece */ result.center.X1 = MAX (breakbox.X1, origbox.X1); result.center.X2 = MIN (breakbox.X2, origbox.X2); /* right edge piece */ result.right.X1 = breakbox.X2; result.right.X2 = origbox.X2; /* validity: */ result.is_valid_left = (result.left.X1 < result.left.X2); result.is_valid_center = (result.center.X1 < result.center.X2); result.is_valid_right = (result.right.X1 < result.right.X2); /* rotate back */ ROTATEBOX_FROM_NORTH (result.left, which_edge); ROTATEBOX_FROM_NORTH (result.center, which_edge); ROTATEBOX_FROM_NORTH (result.right, which_edge); /* done */ return result; } #ifndef NDEBUG static int share_edge (const BoxType * child, const BoxType * parent) { return (child->X1 == parent->X2 || child->X2 == parent->X1 || child->Y1 == parent->Y2 || child->Y2 == parent->Y1) && ((parent->X1 <= child->X1 && child->X2 <= parent->X2) || (parent->Y1 <= child->Y1 && child->Y2 <= parent->Y2)); } static int edge_intersect (const BoxType * child, const BoxType * parent) { return (child->X1 <= parent->X2) && (child->X2 >= parent->X1) && (child->Y1 <= parent->Y2) && (child->Y2 >= parent->Y1); } #endif /* area is the expansion area, on layer group 'group'. 'parent' is the * immediately preceding expansion area, for backtracing. 'lastarea' is * the last expansion area created, we string these together in a loop * so we can remove them all easily at the end. */ static routebox_t * CreateExpansionArea (const BoxType * area, Cardinal group, routebox_t * parent, Boolean relax_edge_requirements, edge_t * src_edge) { CheapPointType center; routebox_t *rb = (routebox_t *) malloc (sizeof (*rb)); assert (area && parent); init_const_box (rb, area->X1, area->Y1, area->X2, area->Y2); rb->group = group; rb->type = EXPANSION_AREA; /* should always share edge with parent */ assert (relax_edge_requirements ? edge_intersect (&rb->box, &parent->box) : share_edge (&rb->box, &parent->box)); rb->parent.expansion_area = route_parent (parent); assert (relax_edge_requirements ? edge_intersect (&rb->box, &parent->box) : share_edge (&rb->box, &parent->box)); if (rb->parent.expansion_area->flags.orphan) RB_up_count (rb->parent.expansion_area); rb->flags.orphan = 1; rb->augStyle = AutoRouteParameters.augStyle; center.X = (area->X1 + area->X2) / 2; center.Y = (area->Y1 + area->Y2) / 2; rb->cost = src_edge->cost_to_point + cost_to_point_on_layer (&src_edge->cost_point, ¢er, group); InitLists (rb); #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES) showroutebox (rb); #endif /* ROUTE_DEBUG && DEBUG_SHOW_EXPANSION_BOXES */ return rb; } /*------ FindBlocker ------*/ struct FindBlocker_info { edge_t *expansion_edge; BDimension maxbloat; routebox_t *blocker; LocationType min_dist; BoxType north_box; }; /* helper methods for __FindBlocker */ static int __FindBlocker_rect_in_reg (const BoxType * box, void *cl) { struct FindBlocker_info *fbi = (struct FindBlocker_info *) cl; BoxType rbox; rbox = bloat_routebox ((routebox_t *) box); ROTATEBOX_TO_NORTH (rbox, fbi->expansion_edge->expand_dir); if (rbox.X2 <= fbi->north_box.X1 || rbox.X1 >= fbi->north_box.X2 || rbox.Y1 > fbi->north_box.Y1) return 0; if (fbi->blocker != NULL && rbox.Y2 < fbi->north_box.Y1 - fbi->min_dist) return 0; /* this is a box; it has to jump through a few more hoops */ if ((routebox_t *) box == nonorphan_parent (fbi->expansion_edge->rb)) return 0; /* this is the parent */ #if 0 if (rbox.Y2 > fbi->north_box.Y1) { /* extends below edge */ /* this assert can fail if minimum keepaway is > pin spacing */ assert (fbi->expansion_edge->flags.is_interior); /* XXX: what to do here? */ } #endif /* okay, this is the closest we've found. */ assert (fbi->blocker == NULL || (fbi->north_box.Y1 - rbox.Y2) <= fbi->min_dist); fbi->blocker = (routebox_t *) box; fbi->min_dist = fbi->north_box.Y1 - rbox.Y2; /* this assert can fail if the minimum keepaway is failed by an element pin spacing. assert (fbi->min_dist >= 0); */ return 1; } static int __FindBlocker_reg_in_sea (const BoxType * region, void *cl) { struct FindBlocker_info *fbi = (struct FindBlocker_info *) cl; BoxType rbox; rbox = bloat_box (region, fbi->maxbloat); #if 0 ROTATEBOX_TO_NORTH (rbox, fbi->expansion_edge->expand_dir); if (rbox.X2 < fbi->north_box.X1 || rbox.X1 > fbi->north_box.X2 || rbox.Y1 > fbi->north_box.Y1) return 0; if (fbi->blocker != NULL && rbox.Y2 < fbi->north_box.Y1 - fbi->min_dist) return 0; #else switch (fbi->expansion_edge->expand_dir) { case WEST: if (-rbox.Y2 > fbi->north_box.X2 || -rbox.Y1 < fbi->north_box.X1 || rbox.X1 > fbi->north_box.Y1 || (fbi->blocker != NULL && rbox.X2 < fbi->north_box.Y1 - fbi->min_dist)) return 0; return 1; case SOUTH: if (-rbox.X2 > fbi->north_box.X2 || -rbox.X1 < fbi->north_box.X1 || -rbox.Y2 > fbi->north_box.Y1 || (fbi->blocker != NULL && -rbox.Y1 < fbi->north_box.Y1 - fbi->min_dist)) return 0; return 1; case EAST: if (rbox.Y1 > fbi->north_box.X2 || rbox.Y2 < fbi->north_box.X1 || -rbox.X2 > fbi->north_box.Y1 || (fbi->blocker != NULL && -rbox.X1 < fbi->north_box.Y1 - fbi->min_dist)) return 0; return 1; case NORTH: if (rbox.X1 > fbi->north_box.X2 || rbox.X2 < fbi->north_box.X1 || rbox.Y1 > fbi->north_box.Y1 || (fbi->blocker != NULL && rbox.Y2 < fbi->north_box.Y1 - fbi->min_dist)) return 0; return 1; default: assert (0); } #endif return 1; } /* main FindBlocker routine. Returns NULL if no neighbor in the * requested direction. * - region is closed on all edges - */ routebox_t * FindBlocker (rtree_t * rtree, edge_t * e, BDimension maxbloat) { struct FindBlocker_info fbi; BoxType sbox; fbi.expansion_edge = e; fbi.maxbloat = maxbloat; fbi.blocker = NULL; fbi.min_dist = 0; fbi.north_box = e->rb->box; sbox = bloat_box (&e->rb->box, maxbloat); switch (e->expand_dir) { case NORTH: sbox.Y1 = -MAX_COORD; break; case EAST: sbox.X2 = MAX_COORD; break; case SOUTH: sbox.Y2 = MAX_COORD; break; case WEST: sbox.X1 = -MAX_COORD; break; default: assert (0); } ROTATEBOX_TO_NORTH (fbi.north_box, e->expand_dir); r_search (rtree, &sbox, __FindBlocker_reg_in_sea, __FindBlocker_rect_in_reg, &fbi); return fbi.blocker; } /* ------------ */ struct fio_info { edge_t *edge; routebox_t *intersect; jmp_buf env; BoxType north_box; }; static int fio_rect_in_reg (const BoxType * box, void *cl) { struct fio_info *fio = (struct fio_info *) cl; routebox_t *rb; BoxType rbox; rbox = bloat_routebox ((routebox_t *) box); ROTATEBOX_TO_NORTH (rbox, fio->edge->expand_dir); if (rbox.X2 <= fio->north_box.X1 || rbox.X1 >= fio->north_box.X2 || rbox.Y1 > fio->north_box.Y1 || rbox.Y2 < fio->north_box.Y1) return 0; /* this is a box; it has to jump through a few more hoops */ /* everything on same net is ignored */ rb = (routebox_t *) box; assert (rb == nonorphan_parent (rb)); if (rb == nonorphan_parent (fio->edge->rb)) return 0; /* okay, this is an intersector! */ fio->intersect = rb; longjmp (fio->env, 1); /* skip to the end! */ return 1; /* never reached */ } static routebox_t * FindIntersectingObstacle (rtree_t * rtree, edge_t * e, BDimension maxbloat) { struct fio_info fio; BoxType sbox; fio.edge = e; fio.intersect = NULL; fio.north_box = e->rb->box; sbox = bloat_box (&e->rb->box, maxbloat); /* exclude equality point from search depending on expansion direction */ switch (e->expand_dir) { case NORTH: case SOUTH: sbox.X1 += 1; sbox.X2 -= 1; break; case EAST: case WEST: sbox.Y1 += 1; sbox.Y2 -= 1; break; default: assert (0); } ROTATEBOX_TO_NORTH (fio.north_box, e->expand_dir); if (setjmp (fio.env) == 0) r_search (rtree, &sbox, NULL, fio_rect_in_reg, &fio); return fio.intersect; } /* ------------ */ struct foib_info { const BoxType *box; BDimension maxbloat; routebox_t *intersect; jmp_buf env; }; static int foib_check (const BoxType * region_or_box, struct foib_info *foib, Boolean is_region) { BoxType rbox; rbox = is_region ? bloat_box (region_or_box, foib->maxbloat) : bloat_routebox ((routebox_t *) region_or_box); if (!box_intersect (&rbox, foib->box)) return 0; if (!is_region) { /* this is an intersector! */ foib->intersect = (routebox_t *) region_or_box; longjmp (foib->env, 1); /* skip to the end! */ } return 1; } static int foib_reg_in_sea (const BoxType * region, void *cl) { return foib_check (region, (struct foib_info *) cl, True); } static int foib_rect_in_reg (const BoxType * box, void *cl) { return foib_check (box, (struct foib_info *) cl, False); } static routebox_t * FindOneInBox (rtree_t * rtree, const BoxType * box, BDimension maxbloat) { struct foib_info foib; foib.box = box; foib.maxbloat = maxbloat; foib.intersect = NULL; if (setjmp (foib.env) == 0) r_search (rtree, NULL, foib_reg_in_sea, foib_rect_in_reg, &foib); return foib.intersect; } struct therm_info { routebox_t *winner; jmp_buf env; }; static int ftherm_rect_in_reg (const BoxType * box, void *cl) { routebox_t *rbox = (routebox_t *) box; struct therm_info *ti = (struct therm_info *) cl; if (rbox->type == PIN || rbox->type == VIA || rbox->type == VIA_SHADOW) { ti->winner = rbox; longjmp (ti->env, 1); } return 0; } /* check for a pin or via target that a polygon can just use a thermal to connect to */ static routebox_t * FindThermable (rtree_t * rtree, const BoxType * box) { struct therm_info info; info.winner = NULL; if (setjmp (info.env) == 0) r_search (rtree, box, NULL, ftherm_rect_in_reg, &info); return info.winner; } /* create a new edge for every edge of the given routebox (e->rb) and * put the result edges in result_vec. */ void ExpandAllEdges (edge_t * e, vector_t * result_vec, cost_t cost_penalty_in_box, rtree_t * targets) { CheapPointType costpoint; cost_t cost; int i; assert (__edge_is_good (e)); assert (e->flags.expand_all_sides); for (i = 0; i < 4; i++) { /* for all directions */ switch (i) { /* assign appropriate cost point */ case NORTH: costpoint.X = e->cost_point.X; costpoint.Y = e->rb->box.Y1; break; case EAST: costpoint.X = e->rb->box.X2; costpoint.Y = e->cost_point.Y; break; case SOUTH: costpoint.X = e->cost_point.X; costpoint.Y = e->rb->box.Y2; break; case WEST: costpoint.X = e->rb->box.X1; costpoint.Y = e->cost_point.Y; break; default: assert (0); } cost = cost_penalty_in_box * cost_to_point_on_layer (&e->cost_point, &costpoint, e->rb->group); vector_append (result_vec, CreateEdge (e->rb, costpoint.X, costpoint.Y, e->cost_to_point + cost, e->mincost_target, i, targets)); } /* done */ return; } /* find edges that intersect obstacles, and break them into * intersecting and non-intersecting edges. */ void BreakEdges (routedata_t * rd, vector_t * edge_vec, rtree_t * targets) { BoxType edgebox, bbox = shrunk_pcb_bounds (); vector_t *broken_vec = vector_create (); while (!vector_is_empty (edge_vec)) { edge_t *e, *ne; routebox_t *rb; /* pop off the top edge */ e = vector_remove_last (edge_vec); if (e->rb->type == PLANE) { vector_append (broken_vec, e); continue; } assert (!e->flags.expand_all_sides); /* check for edges that poke off the edge of the routeable area */ edgebox = edge_to_box (&e->rb->box, e->expand_dir); if (!box_intersect (&bbox, &edgebox)) { /* edge completely off the PCB, skip it. */ DestroyEdge (&e); continue; } if (!box_in_box (&bbox, &edgebox)) { /* edge partially off the PCB, clip it. */ routebox_t *nrb; BoxType newbox = clip_box (&edgebox, &bbox); /* 'close' box (newbox is currently half-open) */ newbox.X2--; newbox.Y2--; /* okay, create new, clipped, edge */ nrb = CreateExpansionArea (&newbox, e->rb->group, route_parent (e->rb), True, e); ne = CreateEdge2 (nrb, e->expand_dir, e, targets, NULL); if (!e->rb->flags.circular) nrb->flags.source = e->rb->flags.source; nrb->flags.nobloat = e->rb->flags.nobloat; /* adjust cost */ ne->cost_to_point = e->rb->flags.source ? e->cost_to_point : e->cost_to_point + (CONFLICT_PENALTY (nonorphan_parent (e->rb)) * (ne->cost_to_point - e->cost_to_point)); assert (__edge_is_good (ne)); /* replace e with ne and continue. */ DestroyEdge (&e); e = ne; edgebox = edge_to_box (&e->rb->box, e->expand_dir); } assert (box_intersect (&bbox, &edgebox)); assert (box_in_box (&bbox, &edgebox)); /* find an intersecting obstacle, and then break edge on it. */ rb = FindIntersectingObstacle (rd->layergrouptree[e->rb->group], e, rd->max_bloat); assert (__edge_is_good (e)); if (rb == NULL) { /* no intersecting obstacle, this baby's good! */ #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EDGE_BOXES) showroutebox (e->rb); printf ("GOOD EDGE FOUND!\n"); #endif assert (__edge_is_good (e)); vector_append (broken_vec, e); } else { /* rb has an intersecting obstacle. break this in three pieces */ struct broken_boxes r = break_box_edge (&e->rb->box, e->expand_dir, rb); routebox_t *parent; int i; /* "canonical parent" is the original source */ parent = route_parent (e->rb); assert (parent->underlying || parent->flags.is_via || parent->type != EXPANSION_AREA); for (i = 0; i < 2; i++) if (i ? r.is_valid_left : r.is_valid_right) { routebox_t *nrb = CreateExpansionArea (i ? &r.left : &r.right, e->rb->group, parent, False, e); ne = CreateEdge2 (nrb, e->expand_dir, e, targets, NULL); if (!e->rb->flags.circular) nrb->flags.source = e->rb->flags.source; nrb->flags.nobloat = e->rb->flags.nobloat; /* adjust cost */ ne->cost_to_point = e->rb->flags.source ? e->cost_to_point : e->cost_to_point + (CONFLICT_PENALTY (nonorphan_parent (e->rb)) * (ne->cost_to_point - e->cost_to_point)); assert (__edge_is_good (ne)); vector_append (edge_vec, ne); } /* center edge is "interior" to obstacle */ /* don't bother adding if this is a source-interior edge */ /* or an expansion edge or the conflict is fixed */ if (r.is_valid_center && (!rb->flags.source) && rb->type != EXPANSION_AREA && (rb->flags.target || !rb->flags.fixed) && AutoRouteParameters.with_conflicts) { ne = CreateEdgeWithConflicts (&r.center, rb, e, CONFLICT_PENALTY (nonorphan_parent (e->rb)), targets); assert (__edge_is_good (ne)); vector_append (broken_vec, ne); } DestroyEdge (&e); } /* done with this edge */ } /* all good edges are now on broken_vec list. */ /* Transfer them back to edge_vec */ assert (vector_size (edge_vec) == 0); vector_append_vector (edge_vec, broken_vec); vector_destroy (&broken_vec); /* done! */ return; } /*-------------------------------------------------------------------- * Route-tracing code: once we've got a path of expansion boxes, trace * a line through them to actually create the connection. */ static void RD_DrawThermal (routedata_t * rd, LocationType X, LocationType Y, Cardinal group, Cardinal layer, routebox_t * subnet, Boolean is_bad) { routebox_t *rb; rb = (routebox_t *) malloc (sizeof (*rb)); init_const_box (rb, X, Y, X + 1, Y + 1); rb->group = group; rb->layer = layer; rb->flags.fixed = 0; rb->flags.is_bad = is_bad; rb->flags.is_odd = AutoRouteParameters.is_odd; rb->flags.circular = 0; rb->augStyle = AutoRouteParameters.augStyle; rb->type = PLANE; InitLists (rb); MergeNets (rb, subnet, NET); MergeNets (rb, subnet, SUBNET); r_insert_entry (rd->layergrouptree[group], &rb->box, 1); if (AutoRouteParameters.use_vias) mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN, rb->augStyle->style->Keepaway); } static void RD_DrawVia (routedata_t * rd, LocationType X, LocationType Y, BDimension radius, routebox_t * subnet, Boolean is_bad) { routebox_t *rb, *first_via = NULL; int i; /* a via cuts through every layer group */ for (i = 0; i < MAX_LAYER; i++) { if (!is_layer_group_active (i)) continue; rb = (routebox_t *) malloc(sizeof (*rb)); init_const_box (rb, /*X1 */ X - radius, /*Y1 */ Y - radius, /*X2 */ X + radius, /*Y2 */ Y + radius); rb->group = i; if (first_via == NULL) { rb->type = VIA; rb->parent.via = NULL; /* indicates that not on PCB yet */ first_via = rb; } else { rb->type = VIA_SHADOW; rb->parent.via_shadow = first_via; } rb->flags.fixed = 0; /* indicates that not on PCB yet */ rb->flags.is_odd = AutoRouteParameters.is_odd; rb->flags.is_bad = is_bad; rb->flags.circular = True; rb->augStyle = AutoRouteParameters.augStyle; InitLists (rb); /* add these to proper subnet. */ MergeNets (rb, subnet, NET); MergeNets (rb, subnet, SUBNET); assert (__routebox_is_good (rb)); /* and add it to the r-tree! */ r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1); #ifdef FIXME if (TEST_FLAG (LIVEROUTEFLAG, PCB)) { gdk_gc_set_line_attributes (Output.fgGC, TO_SCREEN (2 * radius), GDK_LINE_SOLID, GDK_CAP_ROUND, GDK_JOIN_ROUND); gdk_gc_set_foreground (Output.fgGC, PCB->ViaColor); XDrawCLine (Output.top_window->window, Output.fgGC, X, Y, X, Y); } #endif /* and to the via space structures */ if (AutoRouteParameters.use_vias) mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN, rb->augStyle->style->Keepaway); } } static void RD_DrawLine (routedata_t * rd, LocationType X1, LocationType Y1, LocationType X2, LocationType Y2, BDimension halfthick, Cardinal group, routebox_t * subnet, Boolean is_bad, Boolean is_45) { routebox_t *rb; /* don't draw zero-length segments. */ if (X1 == X2 && Y1 == Y2) return; rb = (routebox_t *) malloc (sizeof (*rb)); assert (is_45 ? (ABS (X2 - X1) == ABS (Y2 - Y1)) /* line must be 45-degrees */ : (X1 == X2 || Y1 == Y2) /* line must be ortho */ ); init_const_box (rb, /*X1 */ MIN (X1, X2) - halfthick, /*Y1 */ MIN (Y1, Y2) - halfthick, /*X2 */ MAX (X1, X2) + halfthick, /*Y2 */ MAX (Y1, Y2) + halfthick); rb->group = group; rb->type = LINE; rb->parent.line = NULL; /* indicates that not on PCB yet */ rb->flags.fixed = 0; /* indicates that not on PCB yet */ rb->flags.is_odd = AutoRouteParameters.is_odd; rb->flags.is_bad = is_bad; rb->flags.nonstraight = is_45; rb->flags.bl_to_ur = is_45 && (MIN (X1, X2) == X1) != (MIN (Y1, Y2) == Y1); rb->augStyle = AutoRouteParameters.augStyle; InitLists (rb); /* add these to proper subnet. */ MergeNets (rb, subnet, NET); MergeNets (rb, subnet, SUBNET); assert (__routebox_is_good (rb)); /* and add it to the r-tree! */ r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1); #ifdef FIXME if (TEST_FLAG (LIVEROUTEFLAG, PCB)) { LayerTypePtr layp = LAYER_PTR (PCB->LayerGroups.Entries[rb->group][0]); gdk_gc_set_line_attributes (Output.fgGC, TO_SCREEN (2 * halfthick), GDK_LINE_SOLID, GDK_CAP_ROUND, GDK_JOIN_ROUND); gdk_gc_set_foreground (Output.fgGC, layp->Color); XDrawCLine (Output.top_window->window, Output.fgGC, X1, Y1, X2, Y2); } #endif /* and to the via space structures */ if (AutoRouteParameters.use_vias) mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN, rb->augStyle->style->Keepaway); } static Boolean RD_DrawManhattanLine (routedata_t * rd, const BoxType * bbox, CheapPointType start, CheapPointType end, BDimension halfthick, Cardinal group, routebox_t * subnet, Boolean is_bad, Boolean last_was_x) { CheapPointType knee = start; /* don't draw zero-length segments; start and knee should box be in bbox */ if (point_in_box (bbox, end.X, start.Y)) knee.X = end.X; else knee.Y = end.Y; if (knee.X == end.X && last_was_x && point_in_box (bbox, start.X, end.Y)) { knee.X = start.X; knee.Y = end.Y; } assert (point_in_box (bbox, knee.X, knee.Y)); if (1 || !AutoRouteParameters.is_smoothing) { /* draw standard manhattan paths */ RD_DrawLine (rd, start.X, start.Y, knee.X, knee.Y, halfthick, group, subnet, is_bad, False); RD_DrawLine (rd, knee.X, knee.Y, end.X, end.Y, halfthick, group, subnet, is_bad, False); } else { /* draw 45-degree path across knee */ BDimension len45 = MIN (ABS (start.X - end.X), ABS (start.Y - end.Y)); CheapPointType kneestart = knee, kneeend = knee; if (kneestart.X == start.X) kneestart.Y += (kneestart.Y > start.Y) ? -len45 : len45; else kneestart.X += (kneestart.X > start.X) ? -len45 : len45; if (kneeend.X == end.X) kneeend.Y += (kneeend.Y > end.Y) ? -len45 : len45; else kneeend.X += (kneeend.X > end.X) ? -len45 : len45; RD_DrawLine (rd, start.X, start.Y, kneestart.X, kneestart.Y, halfthick, group, subnet, is_bad, False); RD_DrawLine (rd, kneestart.X, kneestart.Y, kneeend.X, kneeend.Y, halfthick, group, subnet, is_bad, True); RD_DrawLine (rd, kneeend.X, kneeend.Y, end.X, end.Y, halfthick, group, subnet, is_bad, False); } return (knee.X == end.X); } static void TracePath (routedata_t * rd, routebox_t * path, routebox_t * target, routebox_t * subnet, Boolean is_bad) { Boolean last_x = False; BDimension halfwidth = HALF_THICK (AutoRouteParameters.augStyle->style->Thick); BDimension radius = HALF_THICK (AutoRouteParameters.augStyle->style->Diameter); CheapPointType lastpoint, nextpoint; routebox_t *lastpath; BoxType b; assert (subnet->augStyle == AutoRouteParameters.augStyle); /* start from *edge* of target box */ /*XXX: because we round up odd thicknesses, there's the possibility that * a connecting line end-point might be 0.005 mil off the "real" edge. * don't worry about this because line *thicknesses* are always >= 0.01 mil. */ nextpoint.X = (path->box.X1 + path->box.X2) / 2; nextpoint.Y = (path->box.Y1 + path->box.Y2) / 2; nextpoint = closest_point_in_box (&nextpoint, &path->parent.expansion_area->box); /* for circular targets, use *inscribed* rectangle so we're sure to * connect. */ b = path->box; if (target->flags.circular) b = shrink_box (&b, MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 5); nextpoint = closest_point_in_box (&nextpoint, &b); /* hace route to actual pins/pads */ if (target->type == PIN) { nextpoint.X = target->parent.pin->X; nextpoint.Y = target->parent.pin->Y; } else if (target->type == PAD) { if (abs (target->parent.pad->Point1.X - nextpoint.X) < abs (target->parent.pad->Point2.X - nextpoint.X)) nextpoint.X = target->parent.pad->Point1.X; else nextpoint.X = target->parent.pad->Point2.X; if (abs (target->parent.pad->Point1.Y - nextpoint.Y) < abs (target->parent.pad->Point2.Y - nextpoint.Y)) nextpoint.Y = target->parent.pad->Point1.Y; else nextpoint.Y = target->parent.pad->Point2.Y; } #ifdef TO_LINE else if (target->type == LINE) { BDimension half_thick = MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 2; if (abs (b.X1 + half_thick - nextpoint.X) < abs (b.X2 - half_thick - nextpoint.X)) nextpoint.X = b.X1 + half_thick; else nextpoint.X = b.X2 - half_thick; if (abs (b.Y1 + half_thick - nextpoint.Y) < abs (b.Y2 - half_thick - nextpoint.Y)) nextpoint.Y = b.Y1 + half_thick; else nextpoint.Y = b.Y2 - half_thick; } #endif #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES) showroutebox (path); printf ("TRACEPOINT start (%d, %d)\n", nextpoint.X, nextpoint.Y); #endif /* ROUTE_DEBUG && DEBUG_SHOW_ROUTE_BOXES */ do { lastpoint = nextpoint; lastpath = path; assert (path->type == EXPANSION_AREA); path = path->parent.expansion_area; b = path->box; assert (b.X1 != b.X2 && b.Y1 != b.Y2); /* need someplace to put line! */ /* find point on path perimeter closest to last point */ /* if source terminal, try to hit a good place */ if (path->flags.source && AutoRouteParameters.is_smoothing) { switch (path->type) { case PAD: if (abs (path->parent.pad->Point1.X - lastpoint.X) < abs (path->parent.pad->Point2.X - lastpoint.X)) nextpoint.X = path->parent.pad->Point1.X; else nextpoint.X = path->parent.pad->Point2.X; if (abs (path->parent.pad->Point1.Y - lastpoint.Y) < abs (path->parent.pad->Point2.Y - lastpoint.Y)) nextpoint.Y = path->parent.pad->Point1.Y; else nextpoint.Y = path->parent.pad->Point2.Y; nextpoint = closest_point_in_box (&nextpoint, &lastpath->box); break; case PLANE: nextpoint = closest_point_in_box (&lastpoint, &b); break; case PIN: nextpoint.X = (b.X1 + b.X2) / 2; nextpoint.Y = (b.Y1 + b.Y2) / 2; nextpoint = closest_point_in_box (&nextpoint, &lastpath->box); break; #ifdef TO_LINE case LINE: { BDimension half_thick = MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 2; if (abs (b.X1 + half_thick - lastpoint.X) < abs (b.X2 - half_thick - lastpoint.X)) nextpoint.X = b.X1 + half_thick; else nextpoint.X = b.X2 - half_thick; if (abs (b.Y1 + half_thick - lastpoint.Y) < abs (b.Y2 - half_thick - lastpoint.Y)) nextpoint.Y = b.Y1 + half_thick; else nextpoint.Y = b.Y2 - half_thick; nextpoint = closest_point_in_box (&nextpoint, &lastpath->box); } break; #endif default: if (abs (b.X1 - lastpoint.X) < abs (b.X2 - lastpoint.X)) nextpoint.X = b.X1; else nextpoint.X = b.X2 - 1; if (abs (b.Y1 - lastpoint.Y) < abs (b.Y2 - lastpoint.Y)) nextpoint.Y = b.Y1; else nextpoint.Y = b.Y2 - 1; nextpoint = closest_point_in_box (&nextpoint, &lastpath->box); break; } nextpoint = closest_point_in_box (&nextpoint, &b); } else nextpoint = closest_point_in_box (&lastpoint, &b); assert (point_in_box (&lastpath->box, lastpoint.X, lastpoint.Y)); assert (point_in_box (&path->box, nextpoint.X, nextpoint.Y)); #if defined(ROUTE_DEBUG) printf ("TRACEPATH: "); DumpRouteBox (path); printf ("TRACEPATH: point (%d, %d) to point (%d, %d) layer %d\n", lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y, path->group); #endif /* draw orthogonal lines from lastpoint to nextpoint */ /* knee is placed in lastpath box */ /* should never cause line to leave union of lastpath/path boxes */ last_x = RD_DrawManhattanLine (rd, &lastpath->box, lastpoint, nextpoint, halfwidth, path->group, subnet, is_bad, last_x); if (path->flags.is_via) { /* if via, then add via */ #ifdef ROUTE_VERBOSE printf (" (vias)"); #endif assert (point_in_box (&path->box, nextpoint.X, nextpoint.Y)); RD_DrawVia (rd, nextpoint.X, nextpoint.Y, radius, subnet, is_bad); } assert (lastpath->flags.is_via || path->group == lastpath->group); #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES) showroutebox (path); #endif /* ROUTE_DEBUG && DEBUG_SHOW_ROUTE_BOXES */ } while (!path->flags.source); /* if this is connected to a plane, draw the thermal */ if (path->type == PLANE) RD_DrawThermal (rd, nextpoint.X, nextpoint.Y, path->group, path->layer, subnet, is_bad); /* this is source box; draw line to edge */ lastpath = path; lastpoint = nextpoint; /* for circular targets, use *inscribed* rectangle so we're sure to * connect. */ b = path->box; if (path->flags.circular) b = shrink_box (&b, MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 5); nextpoint = closest_point_in_box (&lastpoint, &b); /* hace route to actual pins/pads */ if (path->type == PIN) { nextpoint.X = path->parent.pin->X; nextpoint.Y = path->parent.pin->Y; } else if (path->type == PAD) { if (abs (path->parent.pad->Point1.X - nextpoint.X) < abs (path->parent.pad->Point2.X - nextpoint.X)) nextpoint.X = path->parent.pad->Point1.X; else nextpoint.X = path->parent.pad->Point2.X; if (abs (path->parent.pad->Point1.Y - nextpoint.Y) < abs (path->parent.pad->Point2.Y - nextpoint.Y)) nextpoint.Y = path->parent.pad->Point1.Y; else nextpoint.Y = path->parent.pad->Point2.Y; } #ifdef TO_LINE else if (path->type == LINE) { BDimension half_thick = MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 2; if (abs (b.X1 + half_thick - lastpoint.X) < abs (b.X2 - half_thick - lastpoint.X)) nextpoint.X = b.X1 + half_thick; else nextpoint.X = b.X2 - half_thick; if (abs (b.Y1 + half_thick - lastpoint.Y) < abs (b.Y2 - half_thick - lastpoint.Y)) nextpoint.Y = b.Y1 + half_thick; else nextpoint.Y = b.Y2 - half_thick; } #endif #if defined(ROUTE_DEBUG) printf ("TRACEPATH: "); DumpRouteBox (path); printf ("TRACEPATH: point (%d, %d) to last point (%d, %d) layer %d\n", lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y, path->group); #endif RD_DrawManhattanLine (rd, &lastpath->box, lastpoint, nextpoint, halfwidth, lastpath->group, subnet, is_bad, last_x); /* XXX: nonstraight terminals may not be connected properly! */ /* done! */ } struct routeone_state { /* heap of all candidate expansion edges */ heap_t *workheap; /* information about the best path found so far. */ routebox_t *best_path, *best_target; cost_t best_cost; }; static void add_or_destroy_edge (struct routeone_state *s, edge_t * e) { #if 0 routebox_t *fixed = route_parent (e->rb); /* discard edges that are too far outside the route box */ { if ((e->cost_point.X + REGION < MIN (fixed->box.X1, e->mincost_target->box.X1)) || (e->cost_point.Y + REGION < MIN (fixed->box.Y1, e->mincost_target->box.Y1)) || (e->cost_point.X - REGION > MAX (fixed->box.X2, e->mincost_target->box.X2)) || (e->cost_point.Y - REGION > MAX (fixed->box.Y2, e->mincost_target->box.Y2))) { DestroyEdge (&e); return; } } #endif e->cost = edge_cost (e); assert (__edge_is_good (e)); assert (is_layer_group_active (e->rb->group)); if (s->best_path == NULL || e->cost < s->best_cost) heap_insert (s->workheap, e->cost, e); else DestroyEdge (&e); } static void best_path_candidate (struct routeone_state *s, edge_t * e, routebox_t * best_target) { e->cost = edge_cost (e); if (s->best_path == NULL || e->cost < s->best_cost) { #if defined(ROUTE_DEBUG) printf ("New best path seen! cost = %f\n", e->cost); #endif /* new best path! */ if (s->best_path && s->best_path->flags.orphan) RB_down_count (s->best_path); s->best_path = e->rb; s->best_target = best_target; s->best_cost = e->cost; assert (s->best_cost >= 0); /* don't free this when we destroy edge! */ if (s->best_path->flags.orphan) RB_up_count (s->best_path); } } /* vectors for via site candidates (see mtspace.h) */ struct routeone_via_site_state { vector_t *free_space_vec; vector_t *lo_conflict_space_vec; vector_t *hi_conflict_space_vec; }; void add_via_sites (struct routeone_state *s, struct routeone_via_site_state *vss, mtspace_t * mtspace, routebox_t * within, conflict_t within_conflict_level, edge_t * parent_edge, rtree_t * targets, BDimension shrink) { int i, j, count = 0; BoxType region = shrink_box (&within->box, shrink); assert (AutoRouteParameters.use_vias); /* XXX: need to clip 'within' to shrunk_pcb_bounds, because when XXX: routing with conflicts may poke over edge. */ if (region.X2 <= region.X1 || region.Y2 <= region.Y1) return; mtspace_query_rect (mtspace, ®ion, HALF_THICK (AutoRouteParameters.augStyle->style-> Diameter), AutoRouteParameters.augStyle->style->Keepaway, vss->free_space_vec, vss->lo_conflict_space_vec, vss->hi_conflict_space_vec, AutoRouteParameters.is_odd); for (i = 0; i < 3; i++) { vector_t *v = (i == NO_CONFLICT ? vss->free_space_vec : i == LO_CONFLICT ? vss->lo_conflict_space_vec : i == HI_CONFLICT ? vss->hi_conflict_space_vec : NULL); assert (v); while (!vector_is_empty (v)) { BoxType cliparea; BoxType *area = vector_remove_last (v); if (!box_intersect (area, ®ion) || !(i == NO_CONFLICT || AutoRouteParameters.with_conflicts)) { free (area); continue; } cliparea = clip_box (area, ®ion); free (area); assert (__box_is_good (&cliparea)); count++; for (j = 0; j < MAX_LAYER; j++) { edge_t *ne; if (j == within->group) continue; if (!is_layer_group_active (j)) continue; ne = CreateViaEdge (&cliparea, j, within, parent_edge, within_conflict_level, i, targets); add_or_destroy_edge (s, ne); } } } assert (vector_is_empty (vss->free_space_vec)); assert (vector_is_empty (vss->lo_conflict_space_vec)); assert (vector_is_empty (vss->hi_conflict_space_vec)); } struct routeone_status { Boolean found_route; Boolean route_had_conflicts; cost_t best_route_cost; Boolean net_completely_routed; }; static struct routeone_status RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges) { struct routeone_status result; routebox_t *p; int seen, i; const BoxType **target_list; int num_targets; rtree_t *targets; /* vector of source edges for filtering */ vector_t *source_vec; /* vector of expansion areas to be eventually removed from r-tree */ vector_t *area_vec; /* vector of "touched" fixed regions to be reset upon completion */ vector_t *touched_vec; /* working vector */ vector_t *edge_vec; struct routeone_state s; struct routeone_via_site_state vss; assert (rd && from); /* no targets on to/from net need keepaway areas */ LIST_LOOP (from, same_net, p); p->flags.nobloat = 1; END_LOOP; /* set 'source' flags */ LIST_LOOP (from, same_subnet, p); p->flags.source = 1; END_LOOP; assert (from->flags.source); seen = 0; if (to) { /* if we're routing to a specific target */ if (!to->flags.source) { /* not already connected */ /* check that 'to' and 'from' are on the same net */ seen = 0; #ifndef NDEBUG LIST_LOOP (from, same_net, p); if (p == to) seen = 1; END_LOOP; #endif assert (seen); /* otherwise from and to are on different nets! */ /* set target flags only on 'to's subnet */ LIST_LOOP (to, same_subnet, p); p->flags.target = 1; END_LOOP; assert (to->flags.target); } } else { /* all nodes on the net but not connected to from are targets */ LIST_LOOP (from, same_net, p); if (!p->flags.source) p->flags.target = 1; END_LOOP; } /* remove source/target flags from non-straight obstacles, because they * don't fill their bounding boxes and so connecting to them * after we've routed is problematic. Better solution? */ LIST_LOOP (from, same_net, p); if (p->flags.nonstraight) p->flags.source = p->flags.target = 0; END_LOOP; /* count up the targets */ num_targets = 0; LIST_LOOP (from, same_net, p); if (p->flags.target) num_targets++; END_LOOP; /* if no targets, then net is done! reset flags and return. */ if (num_targets == 0) { LIST_LOOP (from, same_net, p); p->flags.source = p->flags.target = p->flags.nobloat = 0; END_LOOP; result.found_route = False; result.net_completely_routed = True; result.best_route_cost = 0; return result; } result.net_completely_routed = False; /* okay, there's stuff to route */ assert (!from->flags.target); assert (num_targets > 0); /* create list of target pointers and from that a r-tree of targets */ target_list = malloc (num_targets * sizeof (*target_list)); i = 0; LIST_LOOP (from, same_net, p); if (p->flags.target) { target_list[i++] = &p->box; } END_LOOP; targets = r_create_tree (target_list, i, 0); assert (i <= num_targets); free (target_list); /* add all sources to a vector (since we need to BreakEdges) */ source_vec = vector_create (); LIST_LOOP (from, same_subnet, p); { /* we need the test for 'source' because this box may be nonstraight */ if (p->flags.source && is_layer_group_active (p->group)) { edge_t *e; cost_t ns_penalty = 0, ew_penalty = 0; /* penalize long-side expansion of pads */ if (p->type == PAD) { if (p->box.X2 - p->box.X1 > p->box.Y2 - p->box.Y1) ns_penalty = p->box.X2 - p->box.X1; if (p->box.Y2 - p->box.Y1 > p->box.X2 - p->box.X1) ew_penalty = p->box.Y2 - p->box.Y1; } /* may expand in all directions from source; center edge cost point. */ /* note that planes shouldn't really expand, but we need an edge */ if (p->type != PLANE) { e = CreateEdge (p, (p->box.X1 + p->box.X2) / 2, p->box.Y1, ns_penalty, NULL, p->type == PLANE ? SOUTH : NORTH, targets); e->cost = edge_cost (e); vector_append (source_vec, e); e = CreateEdge (p, (p->box.X1 + p->box.X2) / 2, p->box.Y2, ns_penalty, NULL, p->type == PLANE ? NORTH : SOUTH, targets); vector_append (source_vec, e); e = CreateEdge (p, p->box.X2, (p->box.Y1 + p->box.Y2) / 2, ew_penalty, NULL, p->type == PLANE ? WEST : EAST, targets); e->cost = edge_cost (e); vector_append (source_vec, e); } e = CreateEdge (p, p->box.X1, (p->box.Y1 + p->box.Y2) / 2, ew_penalty, NULL, p->type == PLANE ? EAST : WEST, targets); e->cost = edge_cost (e); vector_append (source_vec, e); } } END_LOOP; /* break source edges; some edges may be too near obstacles to be able * to exit from. */ BreakEdges (rd, source_vec, targets); /* okay, main expansion-search routing loop. */ /* set up the initial activity heap */ s.workheap = heap_create (); assert (s.workheap); while (!vector_is_empty (source_vec)) { edge_t *e = vector_remove_last (source_vec); assert (is_layer_group_active (e->rb->group)); e->cost = edge_cost (e); heap_insert (s.workheap, e->cost, e); } vector_destroy (&source_vec); /* okay, process items from heap until it is empty! */ s.best_path = NULL; area_vec = vector_create (); edge_vec = vector_create (); touched_vec = vector_create (); vss.free_space_vec = vector_create (); vss.lo_conflict_space_vec = vector_create (); vss.hi_conflict_space_vec = vector_create (); while (!heap_is_empty (s.workheap)) { edge_t *e = heap_remove_smallest (s.workheap); assert (__edge_is_good (e)); /* we should never add edges on inactive layer groups to the heap. */ assert (is_layer_group_active (e->rb->group)); /* don't bother expanding this edge if the minimum possible edge cost * is already larger than the best edge cost we've found. */ if (s.best_path && e->cost > s.best_cost) goto dontexpand; /* skip this edge */ /* cost the route so far when failed */ if (seen <= max_edges && !s.best_path) s.best_cost = e->cost; /* surprisingly it helps to give up and not try too hard to find * a route! This is not only faster, but results in better routing. * who would have guessed? */ if (seen++ > max_edges) goto dontexpand; #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES) showedge (e); #endif /* for a plane, look for quick connections with thermals or vias */ if (e->rb->type == PLANE) { routebox_t *pin = FindThermable (targets, &e->rb->box); if (pin) { edge_t *ne; routebox_t *nrb = CreateExpansionArea (&pin->box, e->rb->group, e->rb, True, e); nrb->type = PLANE; ne = CreateEdge2 (nrb, e->expand_dir, e, NULL, pin); best_path_candidate (&s, ne, pin); DestroyEdge (&ne); } else { /* add in possible via sites in nrb */ if (AutoRouteParameters.use_vias) add_via_sites (&s, &vss, rd->mtspace, e->rb, NO_CONFLICT, e, targets, e->rb->augStyle->style->Diameter); } goto dontexpand; /* planes only connect via thermals */ } if (e->flags.is_interior) { assert (AutoRouteParameters.with_conflicts); /* no interior edges unless routing with conflicts! */ assert (e->rb->underlying); if (e->rb->underlying->flags.touched) goto dontexpand; /* already done this one */ /* touch this interior box */ e->rb->underlying->flags.touched = 1; vector_append (touched_vec, e->rb->underlying); /* is this a target? */ if (e->rb->underlying->flags.target) best_path_candidate (&s, e, e->rb->underlying); /* new best path? */ /* don't allow conflicts with fixed edges */ if (e->rb->underlying->flags.fixed) goto dontexpand; /* break all edges and come up with a new vector of edges */ assert (__edge_is_good (e)); assert (e->flags.expand_all_sides); assert (vector_is_empty (edge_vec)); ExpandAllEdges (e, edge_vec, CONFLICT_PENALTY (e->rb->underlying), targets); BreakEdges (rd, edge_vec, targets); /* add broken edges to s.workheap */ while (!vector_is_empty (edge_vec)) add_or_destroy_edge (&s, (edge_t *) vector_remove_last (edge_vec)); /* add in possible via sites on conflict rect. */ /* note that e->rb should be bloated version of conflict rect */ if (AutoRouteParameters.use_vias) add_via_sites (&s, &vss, rd->mtspace, e->rb, CONFLICT_LEVEL (e->rb->underlying), e, targets, 0); } else if (e->flags.is_via) { /* special case via */ routebox_t *intersecting; assert (AutoRouteParameters.use_vias); assert (e->flags.expand_all_sides); assert (vector_is_empty (edge_vec)); intersecting = FindOneInBox (rd->layergrouptree[e->rb->group], &e->rb->box, rd->max_bloat); if (intersecting == NULL) { /* this via candidate is in an open area; add it to r-tree as * an expansion area */ assert (e->rb->type == EXPANSION_AREA && e->rb->flags.is_via); assert (r_region_is_empty (rd->layergrouptree[e->rb->group], &e->rb->box)); r_insert_entry (rd->layergrouptree[e->rb->group], &e->rb->box, 1); e->rb->flags.orphan = 0; /* not an orphan any more */ /* add to vector of all expansion areas in r-tree */ vector_append (area_vec, e->rb); /* mark reset refcount to 0, since this is not an orphan any more. */ e->rb->refcount = 0; /* expand from all four edges! */ for (i = 0; i < 4; i++) { edge_t *ne = CreateEdge2 (e->rb, i, e, targets, NULL); add_or_destroy_edge (&s, ne); } } else { /* XXX: disabling this causes no via collisions. */ BoxType a = bloat_routebox (intersecting), b; edge_t *ne; int i, j; /* something intersects this via candidate. split via candidate * into pieces and add these pieces to the workheap. */ for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { b = e->rb->box; switch (i) { case 0: b.X2 = MIN (b.X2, a.X1); break; /* left */ case 1: b.X1 = MAX (b.X1, a.X1); b.X2 = MIN (b.X2, a.X2); break; /*c */ case 2: b.X1 = MAX (b.X1, a.X2); break; /* right */ default: assert (0); } switch (j) { case 0: b.Y2 = MIN (b.Y2, a.Y1); break; /* top */ case 1: b.Y1 = MAX (b.Y1, a.Y1); b.Y2 = MIN (b.Y2, a.Y2); break; /*c */ case 2: b.Y1 = MAX (b.Y1, a.Y2); break; /* bottom */ default: assert (0); } /* skip if this box is not valid */ if (!(b.X1 < b.X2 && b.Y1 < b.Y2)) continue; if (i == 1 && j == 1) { /* this bit of the via space is obstructed. */ if (intersecting->type == EXPANSION_AREA) continue; /* skip this bit, it's already been done. */ /* create an edge with conflicts, if enabled */ if (!AutoRouteParameters.with_conflicts) continue; ne = CreateEdgeWithConflicts (&b, intersecting, e, 1 /*cost penalty to box */ , targets); add_or_destroy_edge (&s, ne); } else { /* if this is not the intersecting piece, create a new * (hopefully unobstructed) via edge and add it back to the * workheap. */ ne = CreateViaEdge (&b, e->rb->group, e->rb->parent.expansion_area, e, e->flags.via_conflict_level, NO_CONFLICT /* value here doesn't matter */ , targets); add_or_destroy_edge (&s, ne); } } } } /* between the time these edges are inserted and the * time they are processed, new expansion boxes (which * conflict with these edges) may be added to the graph! * w.o vias this isn't a problem because the broken box * is not an orphan. */ } else { /* create expansion area from edge */ BoxType expand_region; /* next expansion area */ routebox_t *next; /* this is the obstacle limiting the expansion area */ struct broken_boxes bb; /* edges split by the obstacle */ routebox_t *nrb = NULL; /* new route box */ edge_t *ne; /* new edge */ /* the 'expand_dir' edges of the expansion area have to be split. * this is the parent of those edges */ routebox_t *top_parent = e->rb; /* expand this edge */ #if defined(ROUTE_DEBUG) printf ("EXPANDING EDGE %p: cost %f point (%d, %d) direction ", e, e->cost_to_point, e->cost_point.X, e->cost_point.Y); switch (e->expand_dir) { case NORTH: printf ("NORTH\n"); break; case SOUTH: printf ("SOUTH\n"); break; case WEST: printf ("WEST\n"); break; case EAST: printf ("EAST\n"); break; } DumpRouteBox (e->rb); #endif next = FindBlocker (rd->layergrouptree[e->rb->group], e, rd->max_bloat); /* limit region to next box. */ expand_region = edge_to_infinity_region (e); if (expand_region.X1 >= expand_region.X2 || expand_region.Y1 >= expand_region.Y2) goto dontexpand; /* expansion edge is past PCB edge */ if (next) expand_region = limit_region (expand_region, e, bloat_routebox (next)); if (expand_region.X1 > expand_region.X2 || expand_region.Y1 > expand_region.Y2) goto dontexpand; /* existing copper violates spacing rule */ if (edge_length (&expand_region, (e->expand_dir + 1) % 4) > 0) { assert (edge_length (&expand_region, e->expand_dir) > 0); /* ooh, a non-zero area expansion region! add it to the r-tree! */ /* create new route box nrb and add it to the tree */ nrb = CreateExpansionArea (&expand_region, e->rb->group, e->rb, False, e); assert (r_region_is_empty (rd->layergrouptree[nrb->group], &nrb->box)); r_insert_entry (rd->layergrouptree[nrb->group], &nrb->box, 1); nrb->flags.orphan = 0; /* not an orphan any more */ /* add to vector of all expansion areas in r-tree */ vector_append (area_vec, nrb); /* parent of orphan expansion edges on top should be this */ top_parent = nrb; /* add side edges to the expansion activity heap */ for (i = 1; i < 4; i += 2) { /* directions +/- 1 */ ne = CreateEdge2 (nrb, (e->expand_dir + i) % 4, e, targets, NULL); add_or_destroy_edge (&s, ne); } /* add in possible via sites in nrb */ if (AutoRouteParameters.use_vias) add_via_sites (&s, &vss, rd->mtspace, nrb, NO_CONFLICT, e, targets, 0); } /* if we didn't hit *anything* (i.e. we hit the edge of the board), * then don't expand any more in this direction. */ if (next == NULL) goto dontexpand; if (next->flags.source) goto dontexpand; /* split the blocked edge at the obstacle. Add the two * free edges; the edge that abuts the obstacle is also a * (high-cost) expansion edge as long as the thing we hit isn't * an expansion area. If the thing we hit is a target, then * celebrate! */ bb = break_box_edge (&expand_region, e->expand_dir, next); /* now deal with blocker... */ /* maybe we've found a target? */ if (next->flags.target) { /* we've won! */ assert (bb.is_valid_center); nrb = CreateExpansionArea (&next->box, e->rb->group, top_parent, True, e); /* the expansion area we just created is the target box * we hit it coming from the e->expand_dir direction, but * the edge we hit is the opposite one on *this* box * so be sure to create ne as the new struck edge in order * to compute the cost right. */ /* sometime the minimum cost target is a *different* target, * because of where the cost point was. But *this* cost is to * *this* target, so manually set mincost_target before we * call edge_cost() inside best_path_candidate. */ ne = CreateEdge2 (nrb, (e->expand_dir + 2) % 4, e, NULL, next); assert (ne->rb == nrb); best_path_candidate (&s, ne, next); /* new best path? */ DestroyEdge (&ne); } /* "left" is in rotate_north coordinates */ if (bb.is_valid_left) { /* left edge valid? */ nrb = CreateExpansionArea (&bb.left, e->rb->group, top_parent, False, e); ne = CreateEdge2 (nrb, e->expand_dir, e, targets, NULL); add_or_destroy_edge (&s, ne); } /* "right" is in rotate_north coordinates */ if (bb.is_valid_right) { /* right edge valid? */ nrb = CreateExpansionArea (&bb.right, e->rb->group, top_parent, False, e); ne = CreateEdge2 (nrb, e->expand_dir, e, targets, NULL); add_or_destroy_edge (&s, ne); } if (next->type == EXPANSION_AREA) { CheapPointType center; cost_t cost; center.X = (next->box.X1 + next->box.X2) / 2; center.Y = (next->box.Y1 + next->box.Y2) / 2; cost = cost_to_point_on_layer (&e->cost_point, ¢er, next->group); /* don't expand this edge, but check if we found a cheaper way here */ /*XXX prevent loops */ if (next->cost >= e->cost_to_point + cost); { routebox_t *rb; for (rb = top_parent; !rb->flags.source; rb = rb->parent.expansion_area) if (rb == next) break; /* if this route is cheaper, replace the blocker's parent */ if (rb != next) { for (rb = next; !rb->flags.source; rb = rb->parent.expansion_area) if (rb == top_parent) break; if (rb != top_parent) { next->parent.expansion_area = top_parent; next->cost = e->cost_to_point + cost; if (top_parent->flags.orphan) RB_up_count (top_parent); } } } } else if (!next->flags.target && !next->flags.fixed && AutoRouteParameters.with_conflicts) { edge_t *ne2; /* is center valid for expansion? (with conflicts) */ assert (bb.is_valid_center); /* how could it not be? */ nrb = CreateExpansionArea (&bb.center, e->rb->group, top_parent, False, e); ne = CreateEdge2 (nrb, e->expand_dir, e, targets, NULL); /* no penalty to reach conflict box, since we're still outside here */ ne2 = CreateEdgeWithConflicts (&bb.center, next, ne, 1, targets); add_or_destroy_edge (&s, ne2); DestroyEdge (&ne); } } dontexpand: DestroyEdge (&e); } heap_destroy (&s.workheap); r_destroy_tree (&targets); assert (vector_is_empty (edge_vec)); vector_destroy (&edge_vec); /* we should have a path in best_path now */ if (s.best_path) { routebox_t *rb; #ifdef ROUTE_VERBOSE printf ("%d:%d RC %.0f", ro++, seen, s.best_cost); #endif result.found_route = True; result.best_route_cost = s.best_cost; /* determine if the best path had conflicts */ result.route_had_conflicts = False; for (rb = s.best_path; !rb->flags.source; rb = rb->parent.expansion_area) if (rb->underlying && rb->underlying->flags.is_odd == AutoRouteParameters.is_odd) { result.route_had_conflicts = True; #ifdef ROUTE_VERBOSE printf (" (conflicts)"); #endif break; } /* back-trace the path and add lines/vias to r-tree */ TracePath (rd, s.best_path, s.best_target, from, result.route_had_conflicts); MergeNets (from, s.best_target, SUBNET); RB_down_count (s.best_path); /* free routeboxen along path */ #ifdef ROUTE_VERBOSE printf ("\n"); #endif } else { #ifdef ROUTE_VERBOSE printf ("%d:%d NO PATH FOUND.\n", ro++, seen); #endif result.best_route_cost = s.best_cost; result.found_route = False; } /* clean up; remove all 'source', 'target', and 'nobloat' flags */ LIST_LOOP (from, same_net, p); p->flags.source = p->flags.target = p->flags.nobloat = 0; END_LOOP; /* now remove all expansion areas from the r-tree. */ while (!vector_is_empty (area_vec)) { routebox_t *rb = vector_remove_last (area_vec); assert (!rb->flags.orphan); r_delete_entry (rd->layergrouptree[rb->group], &rb->box); } vector_destroy (&area_vec); /* reset flags on touched fixed rects */ while (!vector_is_empty (touched_vec)) { routebox_t *rb = vector_remove_last (touched_vec); assert (rb->flags.touched); rb->flags.touched = 0; } vector_destroy (&touched_vec); vector_destroy (&vss.free_space_vec); vector_destroy (&vss.lo_conflict_space_vec); vector_destroy (&vss.hi_conflict_space_vec); return result; } static void InitAutoRouteParameters (int pass, AugmentedRouteStyleType * augStyle, Boolean with_conflicts, Boolean is_smoothing) { /* routing style */ AutoRouteParameters.augStyle = augStyle; /* costs */ AutoRouteParameters.ViaCost = 15000; AutoRouteParameters.LastConflictPenalty = 30. * (exp (LN_2_OVER_2 * MIN (30, pass * 4)) - 0.9); AutoRouteParameters.ConflictPenalty = 10 * AutoRouteParameters.LastConflictPenalty; AutoRouteParameters.JogPenalty = 2000; AutoRouteParameters.DirectionPenalty = 2; AutoRouteParameters.SurfacePenalty = 1.5; /* other */ AutoRouteParameters.use_vias = True; AutoRouteParameters.is_odd = (pass & 1); AutoRouteParameters.with_conflicts = with_conflicts; AutoRouteParameters.is_smoothing = is_smoothing; } struct routeall_status { /* --- for completion rate statistics ---- */ int total_subnets; /* total subnets routed without conflicts */ int routed_subnets; /* total subnets routed with conflicts */ int conflict_subnets; }; struct routeall_status RouteAll (routedata_t * rd) { struct routeall_status ras; struct routeone_status ros; #ifdef NET_HEAP heap_t *net_heap; #endif heap_t *this_pass, *next_pass, *tmp; routebox_t *net, *p, *pp; cost_t total_net_cost; int i, limit = 9; /* initialize heap for first pass; * do smallest area first; that makes * the subsequent costs more representative */ this_pass = heap_create (); next_pass = heap_create (); #ifdef NET_HEAP net_heap = heap_create (); #endif LIST_LOOP (rd->first_net, different_net, net); { float area; BoxType bb = net->box; LIST_LOOP (net, same_net, p); { MAKEMIN (bb.X1, p->box.X1); MAKEMIN (bb.Y1, p->box.Y1); MAKEMAX (bb.X2, p->box.X2); MAKEMAX (bb.Y2, p->box.Y2); } END_LOOP; area = (float) (bb.X2 - bb.X1) * (bb.Y2 - bb.Y1); heap_insert (this_pass, area, net); } END_LOOP; /* refinement/finishing passes */ for (i = 0; i <= limit; i++) { #ifdef ROUTE_VERBOSE if (i > 0) printf ("--------- STARTING REFINEMENT PASS %d ------------\n", i); #endif ras.total_subnets = ras.routed_subnets = ras.conflict_subnets = 0; assert (heap_is_empty (next_pass)); while (!heap_is_empty (this_pass)) { net = (routebox_t *) heap_remove_smallest (this_pass); InitAutoRouteParameters (i, net->augStyle, i < limit, i == limit); if (i > 0) { /* rip up all unfixed traces in this net */ LIST_LOOP (net, same_net, p); if (!p->flags.fixed) { assert (!p->flags.orphan); RemoveFromNet (p, NET); RemoveFromNet (p, SUBNET); if (AutoRouteParameters.use_vias) mtspace_remove (rd->mtspace, &p->box, p->flags.is_odd ? ODD : EVEN, p->augStyle->style->Keepaway); if (TEST_FLAG (LIVEROUTEFLAG, PCB) && (p->type == LINE || p->type == VIA)) EraseRouteBox (p); r_delete_entry (rd->layergrouptree[p->group], &p->box); } END_LOOP; /* reset to original connectivity */ ResetSubnet (net); } /* count number of subnets */ FOREACH_SUBNET (net, p); ras.total_subnets++; END_FOREACH (net, p); /* the first subnet doesn't require routing. */ ras.total_subnets--; /* and re-route! */ total_net_cost = 0; /* only route that which isn't fully routed */ if (ras.total_subnets) { /* the loop here ensures that we get to all subnets even if * some of them are unreachable from the first subnet. */ LIST_LOOP (net, same_net, p); { #ifdef NET_HEAP /* using a heap allows us to start from smaller objects and * end at bigger ones. also prefer to start at planes, then pads */ if (p->flags.fixed) heap_insert (net_heap, (float) (p->box.X2 - p->box.X1) * (p->box.Y2 - p->box.Y1) * (p->type == PLANE ? -1 : (p->type == PAD ? 1 : 10)), p); } END_LOOP; while (!heap_is_empty (net_heap)) { p = (routebox_t *) heap_remove_smallest (net_heap); #endif if (p->flags.fixed && !p->flags.subnet_processed && p->type != OTHER) { do { ros = RouteOne (rd, p, NULL, 3000); if (ros.found_route) { total_net_cost += ros.best_route_cost; if (ros.route_had_conflicts) ras.conflict_subnets++; else ras.routed_subnets++; } else { total_net_cost += ros.best_route_cost; /* don't bother trying any other source in this subnet */ LIST_LOOP (p, same_subnet, pp); pp->flags.subnet_processed = 1; END_LOOP; } /* note that we can infer nothing about ras.total_subnets based * on the number of calls to RouteOne, because we may be unable * to route a net from a particular starting point, but perfectly * able to route it from some other. */ } while (ros.found_route && !ros.net_completely_routed); } } #ifndef NET_HEAP END_LOOP; #endif } /* Route easiest nets from this pass first on next pass. * This works best because it's likely that the hardest * is the last one routed (since it has the most obstacles) * but it will do no good to rip it up and try it again * without first changing any of the other routes */ heap_insert (next_pass, total_net_cost, net); /* reset subnet_processed flags */ LIST_LOOP (net, same_net, p); { p->flags.subnet_processed = 0; } END_LOOP; } /* swap this_pass and next_pass and do it all over again! */ ro = 0; assert (heap_is_empty (this_pass)); tmp = this_pass; this_pass = next_pass; next_pass = tmp; /* XXX: here we should update a status bar */ #ifdef ROUTE_VERBOSE printf ("END OF PASS %d: %d/%d subnets routed without conflicts\n", i, ras.routed_subnets, ras.total_subnets); #endif /* if no conflicts found, skip directly to smoothing pass! */ if (ras.conflict_subnets == 0 && i < limit) i = limit - 1; } Message ("%d of %d nets successfully routed.\n", ras.routed_subnets, ras.total_subnets); heap_destroy (&this_pass); heap_destroy (&next_pass); #ifdef NET_HEAP heap_destroy (&net_heap); #endif /* no conflicts should be left at the end of the process. */ assert (ras.conflict_subnets == 0); return ras; } struct fpin_info { PinTypePtr pin; LocationType X, Y; jmp_buf env; }; static int fpin_rect (const BoxType * b, void *cl) { PinTypePtr pin = (PinTypePtr) b; struct fpin_info *info = (struct fpin_info *) cl; if (pin->X == info->X && pin->Y == info->Y) { info->pin = (PinTypePtr) b; longjmp (info->env, 1); } return 0; } static int FindPin (const BoxType * box, PinTypePtr * pin) { struct fpin_info info; info.pin = NULL; info.X = box->X1; info.Y = box->Y1; if (setjmp (info.env) == 0) r_search (PCB->Data->pin_tree, box, NULL, fpin_rect, &info); else { *pin = info.pin; return PIN_TYPE; } if (setjmp (info.env) == 0) r_search (PCB->Data->via_tree, box, NULL, fpin_rect, &info); else { *pin = info.pin; return VIA_TYPE; } *pin = NULL; return NO_TYPE; } /* paths go on first 'on' layer in group */ /* returns 'True' if any paths were added. */ Boolean IronDownAllUnfixedPaths (routedata_t * rd) { Boolean changed = False; LayerTypePtr layer; routebox_t *net, *p; int i; LIST_LOOP (rd->first_net, different_net, net); { LIST_LOOP (net, same_net, p); { if (!p->flags.fixed) { /* find first on layer in this group */ assert (PCB->LayerGroups.Number[p->group] > 0); assert (is_layer_group_active (p->group)); for (i = 0, layer = NULL; i < PCB->LayerGroups.Number[p->group]; i++) { layer = LAYER_PTR (PCB->LayerGroups.Entries[p->group][i]); if (layer->On) break; } assert (layer && layer->On); /*at least one layer must be on in this group! */ assert (p->type != EXPANSION_AREA); if (p->type == LINE) { BDimension halfwidth = HALF_THICK (p->augStyle->style->Thick); BoxType b; assert (p->parent.line == NULL); /* orthogonal; thickness is 2*halfwidth */ /* hace assert (p->flags.nonstraight || p->box.X1 + halfwidth == p->box.X2 - halfwidth || p->box.Y1 + halfwidth == p->box.Y2 - halfwidth); */ /* flip coordinates, if bl_to_ur */ b = shrink_box (&p->box, halfwidth); if (p->flags.bl_to_ur) { BDimension t; t = b.X1; b.X1 = b.X2; b.X2 = t; } /* using CreateDrawn instead of CreateNew concatenates sequential lines */ p->parent.line = CreateDrawnLineOnLayer (layer, b.X1, b.Y1, b.X2, b.Y2, p->augStyle->style->Thick, p->augStyle->style->Keepaway, MakeFlags (AUTOFLAG)); if (p->parent.line) { AddObjectToCreateUndoList (LINE_TYPE, layer, p->parent.line, p->parent.line); changed = True; } } else if (p->type == VIA || p->type == VIA_SHADOW) { routebox_t *pp = (p->type == VIA_SHADOW) ? p->parent.via_shadow : p; BDimension radius = HALF_THICK (pp->augStyle->style->Diameter); assert (pp->type == VIA); if (pp->parent.via == NULL) { assert (pp->box.X1 + radius == pp->box.X2 - radius); assert (pp->box.Y1 + radius == pp->box.Y2 - radius); pp->parent.via = CreateNewVia (PCB->Data, pp->box.X1 + radius, pp->box.Y1 + radius, pp->augStyle->style->Diameter, 2 * pp->augStyle->style->Keepaway, 0, pp->augStyle->style->Hole, NULL, MakeFlags (AUTOFLAG)); assert (pp->parent.via); if (pp->parent.via) { UpdatePIPFlags (pp->parent.via, (ElementTypePtr) pp->parent.via, NULL, False); AddObjectToCreateUndoList (VIA_TYPE, pp->parent.via, pp->parent.via, pp->parent.via); changed = True; } } assert (pp->parent.via); if (p->type == VIA_SHADOW) { p->type = VIA; p->parent.via = pp->parent.via; } } else if (p->type == PLANE) ; else assert (0); } } END_LOOP; /* loop again to place all the thermals now that the vias are down */ LIST_LOOP (net, same_net, p); { if (!p->flags.fixed && p->type == PLANE) { PinTypePtr pin = NULL; int type = FindPin (&p->box, &pin); if (pin) { AddObjectToFlagUndoList (type, pin->Element ? pin->Element : pin, pin, pin); SET_THERM (p->layer, pin); } } } END_LOOP; } END_LOOP; return changed; } Boolean AutoRoute (Boolean selected) { Boolean changed = False; routedata_t *rd; int i; for (i = 0; i < NUM_STYLES; i++) { if (PCB->RouteStyle[i].Thick == 0 || PCB->RouteStyle[1].Diameter == 0 || PCB->RouteStyle[1].Hole == 0 || PCB->RouteStyle[i].Keepaway == 0) { Message ("You must define proper routing styles\n" "before auto-routing.\n"); return (False); } } if (PCB->Data->RatN == 0) return (False); rd = CreateRouteData (); if (1) { routebox_t *net, *rb, *last; int i = 0; /* count numberof rats selected */ RAT_LOOP (PCB->Data); { if (!selected || TEST_FLAG (SELECTEDFLAG, line)) i++; } END_LOOP; #ifdef ROUTE_VERBOSE printf ("%d nets!\n", i); #endif if (i == 0) goto donerouting; /* nothing to do here */ /* if only one rat selected, do things the quick way. =) */ if (i == 1) { RAT_LOOP (PCB->Data); if (!selected || TEST_FLAG (SELECTEDFLAG, line)) { /* look up the end points of this rat line */ routebox_t *a; routebox_t *b; a = FindRouteBoxOnLayerGroup (rd, line->Point1.X, line->Point1.Y, line->group1); b = FindRouteBoxOnLayerGroup (rd, line->Point2.X, line->Point2.Y, line->group2); assert (a != NULL && b != NULL); assert (a->augStyle == b->augStyle); /* route exactly one net, without allowing conflicts */ InitAutoRouteParameters (0, a->augStyle, False, True); changed = RouteOne (rd, a, b, 150000).found_route || changed; goto donerouting; } END_LOOP; } /* otherwise, munge the netlists so that only the selected rats * get connected. */ /* first, separate all sub nets into separate nets */ /* note that this code works because LIST_LOOP is clever enough not to * be fooled when the list is changing out from under it. */ last = NULL; LIST_LOOP (rd->first_net, different_net, net); { FOREACH_SUBNET (net, rb); { if (last) { last->different_net.next = rb; rb->different_net.prev = last; } last = rb; } END_FOREACH (net, rb); LIST_LOOP (net, same_net, rb); { rb->same_net = rb->same_subnet; } END_LOOP; /* at this point all nets are equal to their subnets */ } END_LOOP; if (last) { last->different_net.next = rd->first_net; rd->first_net->different_net.prev = last; } /* now merge only those subnets connected by a rat line */ RAT_LOOP (PCB->Data); if (!selected || TEST_FLAG (SELECTEDFLAG, line)) { /* look up the end points of this rat line */ routebox_t *a; routebox_t *b; a = FindRouteBoxOnLayerGroup (rd, line->Point1.X, line->Point1.Y, line->group1); b = FindRouteBoxOnLayerGroup (rd, line->Point2.X, line->Point2.Y, line->group2); if (!a || !b) { Message ("The rats nest is stale! Aborting autoroute...\n"); goto donerouting; } /* merge subnets into a net! */ MergeNets (a, b, NET); } END_LOOP; /* now 'different_net' may point to too many different nets. Reset. */ LIST_LOOP (rd->first_net, different_net, net); { if (!net->flags.touched) { LIST_LOOP (net, same_net, rb); rb->flags.touched = 1; END_LOOP; } else /* this is not a "different net"! */ RemoveFromNet (net, DIFFERENT_NET); } END_LOOP; /* reset "touched" flag */ LIST_LOOP (rd->first_net, different_net, net); { LIST_LOOP (net, same_net, rb); { assert (rb->flags.touched); rb->flags.touched = 0; } END_LOOP; } END_LOOP; } /* okay, rd's idea of netlist now corresponds to what we want routed */ /* auto-route all nets */ changed = (RouteAll (rd).routed_subnets > 0) || changed; donerouting: if (changed) changed = IronDownAllUnfixedPaths (rd); DestroyRouteData (&rd); if (changed) { SaveUndoSerialNumber (); /* optimize rats, we've changed connectivity a lot. */ DeleteRats (False /*all rats */ ); RestoreUndoSerialNumber (); AddAllRats (False /*all rats */ , NULL); RestoreUndoSerialNumber (); IncrementUndoSerialNumber (); ClearAndRedrawOutput (); } return (changed); }