[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
gEDA-cvs: pcb.git: branch: master updated (e6fc02c73c4884bb973abc98ccf511b711d43c5e)
The branch, master has been updated
via e6fc02c73c4884bb973abc98ccf511b711d43c5e (commit)
via dfc097708cf04983767be89b4e29a551cc0b3bc3 (commit)
via 9e849936702de867e84b82e55ffe9b1549b44c25 (commit)
from 1889ec316b0b4e3d4a41d132a3f4a80ced5d8812 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
=========
Summary
=========
src/autoroute.c | 5155 ++++++++++++++++++++++++++------------------
src/box.h | 61 +-
src/heap.c | 21 +
src/heap.h | 5 +-
src/hid.h | 6 +
src/hid/gtk/gtkhid-main.c | 18 +
src/hid/lesstif/main.c | 18 +
src/mtspace.c | 386 +++--
src/mtspace.h | 3 +-
src/rtree.c | 20 +-
src/vector.c | 14 +
src/vector.h | 2 +
12 files changed, 3449 insertions(+), 2260 deletions(-)
=================
Commit Messages
=================
commit dfc097708cf04983767be89b4e29a551cc0b3bc3
Author: harry <harry@harry-laptop.(none)>
Commit: harry <harry@harry-laptop.(none)>
Fix bugs in autorouter where homeless boxes were being freed prematurely
:100644 100644 0b09585... e7691cc... M src/autoroute.c
commit 9e849936702de867e84b82e55ffe9b1549b44c25
Author: harry <harry@harry-laptop.(none)>
Commit: harry <harry@harry-laptop.(none)>
Major updates to the autorouter. Fixes bug created from prior changes
elsewhere and changes significantly the way that expansion searching
is performed.
:100644 100644 5c689e4... 0b09585... M src/autoroute.c
:100644 100644 59f2f47... 291c6d7... M src/box.h
:100644 100644 4959b58... fee6412... M src/heap.c
:100644 100644 4eeb2b7... 6ee973d... M src/heap.h
:100644 100644 3efb9ed... d3faad6... M src/hid.h
:100644 100644 c27f857... 871a0d0... M src/hid/gtk/gtkhid-main.c
:100644 100644 99f9851... 37e3f5d... M src/hid/lesstif/main.c
:100644 100644 b94f9cd... f5ce554... M src/mtspace.c
:100644 100644 33157aa... 4e6eb8e... M src/mtspace.h
:100644 100644 19741e4... aa5b41a... M src/rtree.c
:100644 100644 1786607... 169afd3... M src/vector.c
:100644 100644 957f524... 3eabef5... M src/vector.h
=========
Changes
=========
commit dfc097708cf04983767be89b4e29a551cc0b3bc3
Author: harry <harry@harry-laptop.(none)>
Commit: harry <harry@harry-laptop.(none)>
Fix bugs in autorouter where homeless boxes were being freed prematurely
diff --git a/src/autoroute.c b/src/autoroute.c
index 0b09585..e7691cc 100644
--- a/src/autoroute.c
+++ b/src/autoroute.c
@@ -1551,7 +1551,7 @@ EraseRouteBox (routebox_t * rb)
static routebox_t *
route_parent (routebox_t * rb)
{
- while (rb->flags.homeless && !rb->flags.is_via)
+ while (rb->flags.homeless && !rb->flags.is_via && !rb->flags.is_thermal)
{
assert (rb->type == EXPANSION_AREA);
rb = rb->parent.expansion_area;
@@ -2041,6 +2041,8 @@ CreateExpansionArea (const BoxType * area, Cardinal group,
&rb->cost_point, rb->group);
assert (relax_edge_requirements ? edge_intersect (&rb->sbox, &parent->sbox)
: share_edge (&rb->sbox, &parent->sbox));
+ if (rb->parent.expansion_area->flags.homeless)
+ RB_up_count(rb->parent.expansion_area);
rb->flags.homeless = 1;
rb->flags.nobloat = 1;
rb->style = AutoRouteParameters.style;
@@ -2437,6 +2439,8 @@ CreateBridge (const BoxType * area, routebox_t * parent, direction_t dir)
&rb->cost_point,
rb->group);
rb->parent.expansion_area = route_parent (parent);
+ if (rb->parent.expansion_area->flags.homeless)
+ RB_up_count (rb->parent.expansion_area);
rb->flags.homeless = 1;
rb->flags.nobloat = 1;
rb->style = parent->style;
@@ -3497,6 +3501,8 @@ TracePath (routedata_t * rd, routebox_t * path, const routebox_t * target,
* is where we're utlimately headed on this path. However, it
* must reside in the plane as well as the via area too.
*/
+ nextpoint.X = CENTER_X (path->sbox);
+ nextpoint.Y = CENTER_Y (path->sbox);
if (path->parent.expansion_area->flags.is_via)
{
TargetPoint (&nextpoint, rb_source (path));
commit 9e849936702de867e84b82e55ffe9b1549b44c25
Author: harry <harry@harry-laptop.(none)>
Commit: harry <harry@harry-laptop.(none)>
Major updates to the autorouter. Fixes bug created from prior changes
elsewhere and changes significantly the way that expansion searching
is performed.
diff --git a/src/autoroute.c b/src/autoroute.c
index 5c689e4..0b09585 100644
--- a/src/autoroute.c
+++ b/src/autoroute.c
@@ -28,6 +28,8 @@
*/
/* this file, autoroute.c, was written and is
* Copyright (c) 2001 C. Scott Ananian
+ * Copyright (c) 2006 harry eaton
+ * Copyright (c) 2009 harry eaton
*/
/* functions used to autoroute nets.
*/
@@ -41,10 +43,15 @@
* http://www.acm.org/dl for those with institutional or personal
* access to it. It's also available from your local engineering
* library.
+ *
+ * The code is much closer to what is described in the paper now,
+ * in that expansion areas can grow from corners and in all directions
+ * at once. Previously, these were emulated with discrete boxes moving
+ * in the cardinal directions. With the new method, there are fewer but
+ * larger expansion boxes that one might do a better job of routing in.
*--------------------------------------------------------------------
*/
#define NET_HEAP 1
-#undef BREAK_ALL
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
@@ -58,7 +65,6 @@
#include "macro.h"
#include "autoroute.h"
#include "box.h"
-/*#include "clip.h"*/
#include "create.h"
#include "draw.h"
#include "error.h"
@@ -86,14 +92,15 @@ RCSID ("$Id$");
#define ROUTE_VERBOSE
*/
-
/*
#define ROUTE_DEBUG
-#define DEBUG_SHOW_ROUTE_BOXES
+//#define DEBUG_SHOW_ROUTE_BOXES
#define DEBUG_SHOW_EXPANSION_BOXES
-#define DEBUG_SHOW_VIA_BOXES
+//#define DEBUG_SHOW_EDGES
+//#define DEBUG_SHOW_VIA_BOXES
#define DEBUG_SHOW_TARGETS
-#define DEBUG_SHOW_ZIGZAG
+#define DEBUG_SHOW_SOURCES
+//#define DEBUG_SHOW_ZIGZAG
*/
static hidGC ar_gc = 0;
@@ -111,15 +118,20 @@ static hidGC ar_gc = 0;
(((rb)->flags.is_odd==AutoRouteParameters.is_odd) ?\
HI_CONFLICT : LO_CONFLICT )
#define CONFLICT_PENALTY(rb)\
- (CONFLICT_LEVEL(rb)==HI_CONFLICT ? \
+ ((CONFLICT_LEVEL(rb)==HI_CONFLICT ? \
AutoRouteParameters.ConflictPenalty : \
CONFLICT_LEVEL(rb)==LO_CONFLICT ? \
- AutoRouteParameters.LastConflictPenalty : 1)
+ AutoRouteParameters.LastConflictPenalty : 1) * (rb)->pass)
#if !defined(ABS)
#define ABS(x) (((x)<0)?-(x):(x))
#endif
+#define _NORTH 1
+#define _EAST 2
+#define _SOUTH 4
+#define _WEST 8
+
#define LIST_LOOP(init, which, x) do {\
routebox_t *__next_one__ = (init);\
x = NULL;\
@@ -150,33 +162,23 @@ static hidGC ar_gc = 0;
p->flags.subnet_processed=0;\
END_LOOP;\
} while (0)
+#define SWAP(t, f, s) do { t a=s; s=f; f=a; } 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 infinitesimal
- * 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.
+ * corner but don't include their bottom and right edges.
*
* expansion regions are always half-closed. This means that when
- * tracing paths, you must steer clear of the bottom and right edges.
+ * tracing paths, you must steer clear of the bottom and right edges.,
+ * because these are not actually in the allowed box.
+ *
+ * All routeboxes *except* EXPANSION_AREAS now have their "box" bloated by
+ * their particular required keepaway. This simplifies the tree searching.
+ * the "sbox" contains the unbloated box.
*/
/* ---------------------------------------------------------------------------
* 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
@@ -185,23 +187,23 @@ conflict_t;
typedef struct routebox
{
- const BoxType box;
+ const BoxType box, sbox;
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. */
+ 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 */
+ void *generic; /* 'other' is polygon, arc, text */
+ struct routebox *expansion_area; /* previous expansion area in search */
}
parent;
unsigned short group;
unsigned short layer;
enum
- { PAD, PIN, VIA, VIA_SHADOW, LINE, OTHER, EXPANSION_AREA, PLANE }
+ { PAD, PIN, VIA, VIA_SHADOW, LINE, OTHER, EXPANSION_AREA, PLANE, THERMAL }
type;
struct
{
@@ -215,8 +217,8 @@ typedef struct routebox
/* 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;
+ * r-tree yet -- make sure refcount of homelesss is set properly */
+ unsigned homeless: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
@@ -239,18 +241,27 @@ typedef struct routebox
unsigned is_bad:1;
/* for assertion that 'box' is never changed after creation */
unsigned inited:1;
+ /* indicate this expansion ares is a thermal between the pin and plane */
+ unsigned is_thermal;
}
flags;
/* indicate the direction an expansion box came from */
cost_t cost;
CheapPointType cost_point;
- /* reference count for orphan routeboxes; free when refcount==0 */
+ /* reference count for homeless routeboxes; free when refcount==0 */
int refcount;
/* when routing with conflicts, we keep a record of what we're
- * conflicting *with*. */
- struct routebox *underlying;
+ * conflicting with.
+ */
+ vector_t *conflicts_with;
/* route style of the net associated with this routebox */
- AugmentedRouteStyleType *augStyle;
+ RouteStyleType *style;
+ /* congestion values for the edges of an expansion box */
+ unsigned char n, e, s, w;
+ /* what pass this this track was laid down on */
+ unsigned char pass;
+ /* the direction this came from, if any */
+ direction_t came_from;
/* circular lists with connectivity information. */
struct routebox_list
{
@@ -263,34 +274,32 @@ routebox_t;
typedef struct routedata
{
/* one rtree per layer *group */
- rtree_t *layergrouptree[MAX_LAYER]; /* no silkscreen layers here =) */
+ 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];
+ RouteStyleType defaultstyle;
+ /* style structures */
+ RouteStyleType *styles[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;
+ BDimension max_keep;
mtspace_t *mtspace;
}
routedata_t;
typedef struct edge_struct
{
- routebox_t *rb; /* path expansion edges are real routeboxen. */
+ 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 */
- vetting_t *work; /* for via search edges */
- direction_t expand_dir; /* ignored if expand_all_sides is set */
+ 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 */
+ vetting_t *work; /* for via search edges */
+ direction_t expand_dir;
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
@@ -300,6 +309,8 @@ typedef struct edge_struct
unsigned is_interior:1;
/* this is a fake edge used to defer searching for via spaces */
unsigned via_search:1;
+ /* this is a via edge in a plane where the cost point moves for free */
+ unsigned in_plane:1;
}
flags;
}
@@ -308,17 +319,17 @@ edge_t;
static struct
{
/* net style parameters */
- AugmentedRouteStyleType *augStyle;
+ RouteStyleType *style;
+ /* the present bloat */
+ BDimension bloat;
/* cost parameters */
- cost_t ViaCost, /* additional "length" cost for using a via */
- WrongWayPenalty, /* cost for expanding an edge away from the target */
- 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 */
- AwayPenalty, /* length multiplier for getting further from the target */
- NewLayerPenalty, SearchPenalty, MinPenalty; /* smallest of Surface, Direction Penalty */
+ cost_t ViaCost, /* additional "length" cost for using a via */
+ LastConflictPenalty, /* length mult. for routing over last pass' trace */
+ ConflictPenalty, /* length multiplier for routing over another trace */
+ JogPenalty, /* additional "length" cost for changing direction */
+ CongestionPenalty, /* (rational) length multiplier for routing in */
+ NewLayerPenalty, /* penalty for routing on a previously unused layer */
+ MinPenalty; /* smallest Direction Penalty */
/* maximum conflict incidence before calling it "no path found" */
int hi_conflict;
/* are vias allowed? */
@@ -331,25 +342,45 @@ static struct
Boolean is_smoothing;
/* rip up nets regardless of conflicts? */
Boolean rip_always;
+ Boolean last_smooth;
+ unsigned char pass;
}
AutoRouteParameters;
+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;
+};
+
/* ---------------------------------------------------------------------------
* some local prototypes
*/
static routebox_t *CreateExpansionArea (const BoxType * area, Cardinal group,
- routebox_t * parent,
- Boolean relax_edge_requirements,
- edge_t * edge);
+ routebox_t * parent,
+ Boolean relax_edge_requirements,
+ edge_t * edge);
static cost_t edge_cost (const edge_t * e, const cost_t too_big);
+static void best_path_candidate (struct routeone_state *s,
+ edge_t * e, routebox_t * best_target);
-static BoxType edge_to_box (const BoxType * box, direction_t expand_dir);
+static BoxType edge_to_box (const routebox_t * rb, direction_t expand_dir);
+static void add_or_destroy_edge (struct routeone_state *s, edge_t * e);
+
+static void
+RD_DrawThermal (routedata_t * rd, LocationType X, LocationType Y,
+ Cardinal group, Cardinal layer, routebox_t * subnet,
+ Boolean is_bad);
static void ResetSubnet (routebox_t * net);
#ifdef ROUTE_DEBUG
-static int showboxen = 0;
+static int showboxen = -2;
+static int aabort = 0;
static void showroutebox (routebox_t * rb);
#endif
@@ -358,11 +389,12 @@ static void showroutebox (routebox_t * rb);
*/
/* group number of groups that hold surface mount pads */
static Cardinal front, back;
-static Boolean bad_x[MAX_LAYER], bad_y[MAX_LAYER], usedGroup[MAX_LAYER];
+static Boolean usedGroup[MAX_LAYER];
+static int x_cost[MAX_LAYER], y_cost[MAX_LAYER];
static Boolean is_layer_group_active[MAX_LAYER];
static int ro = 0;
-static int smoothes = 3;
-static int passes = 9;
+static int smoothes = 1;
+static int passes = 12;
static int routing_layers = 0;
/* assertion helper for routeboxen */
@@ -371,46 +403,65 @@ static int
__routebox_is_good (routebox_t * rb)
{
assert (rb && (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)));
+ (rb->box.X1 <= rb->box.X2) && (rb->box.Y1 <= rb->box.Y2) &&
+ (rb->flags.homeless ?
+ (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));
+ (rb->flags.target ? rb->flags.nobloat : 1) &&
+ (rb->flags.homeless ? !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);
+ (rb->type == VIA || rb->type == VIA_SHADOW || rb->type == LINE
+ || rb->type == PLANE) : 1));
+ assert (rb->flags.clear_poly ?
+ ((rb->type == OTHER || rb->type == PLANE) && rb->flags.fixed
+ && !rb->flags.homeless) : 1);
+ assert (rb->flags.inited);
+/* run through conflict list showing none are homeless, targets or sources */
+ if (rb->conflicts_with)
+ {
+ int i;
+ for (i = 0; i < vector_size (rb->conflicts_with); i++)
+ {
+ routebox_t *c = vector_element (rb->conflicts_with, i);
+ assert (!c->flags.homeless && !c->flags.source && !c->flags.target
+ && !c->flags.fixed);
+ }
+ }
+ assert (rb->style != NULL && rb->style != NULL);
+ assert (rb->type == EXPANSION_AREA
+ || (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->rb->flags.homeless ? e->rb->refcount > 0 : 1));
+ assert ((0 <= e->expand_dir) && (e->expand_dir < 9)
+ && (e->flags.
+ is_interior ? (e->expand_dir == ALL
+ && e->rb->conflicts_with) : 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));
+ && (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;
}
+
+int
+no_planes (const BoxType * b, void *cl)
+{
+ routebox_t *rb = (routebox_t *) b;
+ if (rb->type == PLANE)
+ return 0;
+ return 1;
+}
#endif /* !NDEBUG */
/*---------------------------------------------------------------------
@@ -457,6 +508,8 @@ MergeNets (routebox_t * a, routebox_t * b, enum boxlist which)
routebox_t *an, *bn;
assert (a && b);
assert (a != b);
+ assert (a->type != EXPANSION_AREA);
+ assert (b->type != EXPANSION_AREA);
al = __select_list (a, which);
bl = __select_list (b, which);
assert (al && bl);
@@ -483,7 +536,7 @@ RemoveFromNet (routebox_t * a, enum boxlist which)
an = al->next;
ap = al->prev;
if (an == a || ap == a)
- return; /* not on any list */
+ return; /* not on any list */
assert (an && ap);
anl = __select_list (an, which);
apl = __select_list (ap, which);
@@ -496,12 +549,17 @@ RemoveFromNet (routebox_t * a, enum boxlist which)
static void
init_const_box (routebox_t * rb,
- LocationType X1, LocationType Y1, LocationType X2,
- LocationType Y2)
+ LocationType X1, LocationType Y1, LocationType X2,
+ LocationType Y2, BDimension keepaway)
{
- BoxType *bp = (BoxType *) & rb->box; /* note discarding const! */
+ BoxType *bp = (BoxType *) & rb->box; /* note discarding const! */
assert (!rb->flags.inited);
assert (X1 <= X2 && Y1 <= Y2);
+ bp->X1 = X1 - keepaway;
+ bp->Y1 = Y1 - keepaway;
+ bp->X2 = X2 + keepaway;
+ bp->Y2 = Y2 + keepaway;
+ bp = (BoxType *) & rb->sbox;
bp->X1 = X1;
bp->Y1 = Y1;
bp->X2 = X2;
@@ -509,12 +567,39 @@ init_const_box (routebox_t * rb,
rb->flags.inited = 1;
}
+static inline BoxType
+shrink_routebox (const routebox_t * rb)
+{
+ return rb->sbox;
+}
+
+static inline cost_t
+box_area (const BoxType b)
+{
+ cost_t ans = b.X2 - b.X1;
+ return ans * (b.Y2 - b.Y1);
+}
+
+static inline CheapPointType
+closest_point_in_routebox (const CheapPointType * from, const routebox_t * rb)
+{
+ return closest_point_in_box (from, &rb->sbox);
+}
+
+static inline Boolean
+point_in_shrunk_box (const routebox_t * box, LocationType X, LocationType Y)
+{
+ BoxType b = shrink_routebox (box);
+ return point_in_box (&b, X, Y);
+}
+
/*---------------------------------------------------------------------
* routedata initialization functions.
*/
static routebox_t *
-AddPin (PointerListType layergroupboxes[], PinTypePtr pin, Boolean is_via)
+AddPin (PointerListType layergroupboxes[], PinTypePtr pin, Boolean is_via,
+ RouteStyleType * style)
{
routebox_t **rbpp, *lastrb = NULL;
int i, ht;
@@ -523,42 +608,45 @@ AddPin (PointerListType layergroupboxes[], PinTypePtr pin, Boolean is_via)
{
rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[i]);
*rbpp = malloc (sizeof (**rbpp));
+ memset ((void *) *rbpp, 0, sizeof (**rbpp));
(*rbpp)->group = i;
ht = HALF_THICK (MAX (pin->Thickness, pin->DrillingHole));
init_const_box (*rbpp,
- /*X1 */ pin->X - ht,
- /*Y1 */ pin->Y - ht,
- /*X2 */ pin->X + ht,
- /*Y2 */ pin->Y + ht);
+ /*X1 */ pin->X - ht,
+ /*Y1 */ pin->Y - ht,
+ /*X2 */ pin->X + ht,
+ /*Y2 */ pin->Y + ht, style->Keepaway);
/* set aux. properties */
if (is_via)
- {
- (*rbpp)->type = VIA;
- (*rbpp)->parent.via = pin;
- }
+ {
+ (*rbpp)->type = VIA;
+ (*rbpp)->parent.via = pin;
+ }
else
- {
- (*rbpp)->type = PIN;
- (*rbpp)->parent.pin = pin;
- }
+ {
+ (*rbpp)->type = PIN;
+ (*rbpp)->parent.pin = pin;
+ }
(*rbpp)->flags.fixed = 1;
+ (*rbpp)->came_from = ALL;
+ (*rbpp)->style = style;
(*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);
- }
+ {
+ MergeNets (*rbpp, lastrb, NET);
+ MergeNets (*rbpp, lastrb, SUBNET);
+ MergeNets (*rbpp, lastrb, ORIGINAL);
+ }
lastrb = *rbpp;
}
return lastrb;
}
static routebox_t *
AddPad (PointerListType layergroupboxes[],
- ElementTypePtr element, PadTypePtr pad)
+ ElementTypePtr element, PadTypePtr pad, RouteStyleType * style)
{
BDimension halfthick;
routebox_t **rbpp;
@@ -569,13 +657,15 @@ AddPad (PointerListType layergroupboxes[],
assert (rbpp);
*rbpp = malloc (sizeof (**rbpp));
assert (*rbpp);
+ memset (*rbpp, 0, sizeof (**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);
+ /*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,
+ style->Keepaway);
/* kludge for non-manhattan pads (which are not allowed at present) */
if (pad->Point1.X != pad->Point2.X && pad->Point1.Y != pad->Point2.Y)
(*rbpp)->flags.nonstraight = 1;
@@ -583,13 +673,15 @@ AddPad (PointerListType layergroupboxes[],
(*rbpp)->type = PAD;
(*rbpp)->parent.pad = pad;
(*rbpp)->flags.fixed = 1;
+ (*rbpp)->came_from = ALL;
+ (*rbpp)->style = style;
/* circular lists */
InitLists (*rbpp);
return *rbpp;
}
static routebox_t *
AddLine (PointerListType layergroupboxes[], int layergroup, LineTypePtr line,
- LineTypePtr ptr)
+ LineTypePtr ptr, RouteStyleType * style)
{
routebox_t **rbpp;
assert (layergroupboxes && line);
@@ -598,24 +690,25 @@ AddLine (PointerListType layergroupboxes[], int layergroup, LineTypePtr line,
rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
*rbpp = malloc (sizeof (**rbpp));
+ memset (*rbpp, 0, 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));
+ /*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), style->Keepaway);
/* 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);
+ (MIN (line->Point1.X, line->Point2.X) == line->Point1.X) !=
+ (MIN (line->Point1.Y, line->Point2.Y) == line->Point1.Y);
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ZIGZAG)
showroutebox (*rbpp);
#endif
@@ -624,17 +717,20 @@ AddLine (PointerListType layergroupboxes[], int layergroup, LineTypePtr line,
(*rbpp)->type = LINE;
(*rbpp)->parent.line = ptr;
(*rbpp)->flags.fixed = 1;
+ (*rbpp)->came_from = ALL;
+ (*rbpp)->style = style;
/* circular lists */
InitLists (*rbpp);
return *rbpp;
}
static routebox_t *
AddIrregularObstacle (PointerListType layergroupboxes[],
- LocationType X1, LocationType Y1,
- LocationType X2, LocationType Y2, Cardinal layergroup,
- void *parent)
+ LocationType X1, LocationType Y1,
+ LocationType X2, LocationType Y2, Cardinal layergroup,
+ void *parent, RouteStyleType * style)
{
routebox_t **rbpp;
+ LocationType keep = style->Keepaway;
assert (layergroupboxes && parent);
assert (X1 <= X2 && Y1 <= Y2);
assert (0 <= layergroup && layergroup < max_layer);
@@ -642,12 +738,14 @@ AddIrregularObstacle (PointerListType layergroupboxes[],
rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
*rbpp = malloc (sizeof (**rbpp));
+ memset (*rbpp, 0, sizeof (**rbpp));
(*rbpp)->group = layergroup;
- init_const_box (*rbpp, X1, Y1, X2, Y2);
+ init_const_box (*rbpp, X1, Y1, X2, Y2, keep);
(*rbpp)->flags.nonstraight = 1;
(*rbpp)->type = OTHER;
(*rbpp)->parent.generic = parent;
(*rbpp)->flags.fixed = 1;
+ (*rbpp)->style = style;
/* circular lists */
InitLists (*rbpp);
return *rbpp;
@@ -655,7 +753,7 @@ AddIrregularObstacle (PointerListType layergroupboxes[],
static routebox_t *
AddPolygon (PointerListType layergroupboxes[], Cardinal layer,
- PolygonTypePtr polygon)
+ PolygonTypePtr polygon, RouteStyleType * style)
{
int is_not_rectangle = 1;
int layergroup = GetLayerGroupNumberByNumber (layer);
@@ -666,7 +764,7 @@ AddPolygon (PointerListType layergroupboxes[], Cardinal layer,
polygon->BoundingBox.Y1,
polygon->BoundingBox.X2,
polygon->BoundingBox.Y2,
- layergroup, polygon);
+ layergroup, polygon, style);
if (polygon->PointN == 4 &&
(polygon->Points[0].X == polygon->Points[1].X ||
polygon->Points[0].Y == polygon->Points[1].Y) &&
@@ -679,35 +777,37 @@ AddPolygon (PointerListType layergroupboxes[], Cardinal layer,
is_not_rectangle = 0;
rb->flags.nonstraight = is_not_rectangle;
rb->layer = layer;
+ rb->came_from = ALL;
if (TEST_FLAG (CLEARPOLYFLAG, polygon))
{
rb->flags.clear_poly = 1;
if (!is_not_rectangle)
- rb->type = PLANE;
+ rb->type = PLANE;
}
return rb;
}
static void
AddText (PointerListType layergroupboxes[], Cardinal layergroup,
- TextTypePtr text)
+ TextTypePtr text, RouteStyleType * style)
{
AddIrregularObstacle (layergroupboxes,
- text->BoundingBox.X1, text->BoundingBox.Y1,
- text->BoundingBox.X2, text->BoundingBox.Y2,
- layergroup, text);
+ text->BoundingBox.X1, text->BoundingBox.Y1,
+ text->BoundingBox.X2, text->BoundingBox.Y2,
+ layergroup, text, style);
}
static routebox_t *
AddArc (PointerListType layergroupboxes[], Cardinal layergroup,
- ArcTypePtr arc)
+ ArcTypePtr arc, RouteStyleType * style)
{
return AddIrregularObstacle (layergroupboxes,
- arc->BoundingBox.X1, arc->BoundingBox.Y1,
- arc->BoundingBox.X2, arc->BoundingBox.Y2,
- layergroup, arc);
+ arc->BoundingBox.X1, arc->BoundingBox.Y1,
+ arc->BoundingBox.X2, arc->BoundingBox.Y2,
+ layergroup, arc, style);
}
struct rb_info
{
+ BoxType query;
routebox_t *winner;
jmp_buf env;
};
@@ -717,33 +817,39 @@ __found_one_on_lg (const BoxType * box, void *cl)
{
struct rb_info *inf = (struct rb_info *) cl;
routebox_t *rb = (routebox_t *) box;
+ BoxType sb;
+
if (rb->flags.nonstraight)
- return 1;
+ return 0;
+ sb = shrink_box (&rb->box, rb->style->Keepaway);
+ if (inf->query.X1 >= sb.X2 || inf->query.X2 <= sb.X1 ||
+ inf->query.Y1 >= sb.Y2 || inf->query.Y2 <= sb.Y1)
+ return 0;
inf->winner = rb;
+ if (rb->type == PLANE)
+ return 1; /* keep looking for something smaller if a plane was found */
longjmp (inf->env, 1);
return 0;
}
static routebox_t *
FindRouteBoxOnLayerGroup (routedata_t * rd,
- LocationType X, LocationType Y, Cardinal layergroup)
+ LocationType X, LocationType Y, Cardinal layergroup)
{
struct rb_info info;
- BoxType region;
info.winner = NULL;
- region.X1 = region.X2 = X;
- region.Y1 = region.Y2 = Y;
+ info.query = point_box (X, Y);
if (setjmp (info.env) == 0)
- r_search (rd->layergrouptree[layergroup], ®ion, NULL,
- __found_one_on_lg, &info);
+ r_search (rd->layergrouptree[layergroup], &info.query, NULL,
+ __found_one_on_lg, &info);
return info.winner;
}
-#ifdef ROUTE_DEBUG
+#ifdef ROUTE_DEBUG_VERBOSE
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);
+ rb->box.X1, rb->box.Y1, rb->box.X2, rb->box.Y2, (int) rb->group);
switch (rb->type)
{
case PAD:
@@ -754,7 +860,7 @@ DumpRouteBox (routebox_t * rb)
break;
case VIA:
if (!rb->parent.via)
- break;
+ break;
printf ("VIA[%s %s] ", rb->parent.via->Name, rb->parent.via->Number);
break;
case LINE:
@@ -778,8 +884,8 @@ DumpRouteBox (routebox_t * rb)
printf ("(source) ");
if (rb->flags.target)
printf ("(target) ");
- if (rb->flags.orphan)
- printf ("(orphan) ");
+ if (rb->flags.homeless)
+ printf ("(homeless) ");
printf ("\n");
}
#endif
@@ -791,7 +897,6 @@ CreateRouteData ()
PointerListType layergroupboxes[MAX_LAYER];
BoxType bbox;
routedata_t *rd;
- Boolean other = True;
int group, i;
/* check which layers are active first */
@@ -799,53 +904,59 @@ CreateRouteData ()
for (group = 0; group < max_layer; group++)
{
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)
- {
- routing_layers++;
- is_layer_group_active[group] = True;
- break;
- }
- else
- is_layer_group_active[group] = False;
+ /* 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)
+ {
+ routing_layers++;
+ is_layer_group_active[group] = True;
+ break;
+ }
+ else
+ is_layer_group_active[group] = False;
}
- AutoRouteParameters.use_vias = ((routing_layers > 1) ? True : False);
+ /* if via visibility is turned off, don't use them */
+ AutoRouteParameters.use_vias = routing_layers > 1 && PCB->ViaOn;
front = GetLayerGroupNumberByNumber (max_layer + COMPONENT_LAYER);
back = GetLayerGroupNumberByNumber (max_layer + SOLDER_LAYER);
/* determine preferred 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;
- }
+ {
+ x_cost[i] = (i & 1) ? 2 : 1;
+ y_cost[i] = (i & 1) ? 1 : 2;
+ }
+ else if (i == back)
+ {
+ x_cost[i] = 4;
+ y_cost[i] = 2;
+ }
else
- {
- bad_x[i] = False;
- bad_y[i] = False;
- }
+ {
+ x_cost[i] = 2;
+ y_cost[i] = 2;
+ }
}
/* create routedata */
rd = malloc (sizeof (*rd));
+ memset ((void *) rd, 0, 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 */
+ 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);
+ rd->max_keep = Settings.Keepaway;
+ /* create styles 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;
+ (i < NUM_STYLES) ? &PCB->RouteStyle[i] : &rd->defaultstyle;
+ rd->styles[i] = style;
}
/* initialize pointerlisttype */
@@ -856,10 +967,10 @@ CreateRouteData ()
layergroupboxes[i].PtrMax = 0;
GROUP_LOOP (PCB->Data, i);
{
- if (layer->LineN || layer->ArcN)
- usedGroup[i] = True;
- else
- usedGroup[i] = False;
+ if (layer->LineN || layer->ArcN)
+ usedGroup[i] = True;
+ else
+ usedGroup[i] = False;
}
END_LOOP;
}
@@ -870,7 +981,7 @@ CreateRouteData ()
*
* this saves on searching the trees to find the nets
*/
- /* use the DRCFLAG to mark objects as their entered */
+ /* use the DRCFLAG to mark objects as they are entered */
ResetFoundPinsViasAndPads (False);
ResetFoundLinesAndPolygons (False);
Nets = CollectSubnets (False);
@@ -881,106 +992,106 @@ CreateRouteData ()
routebox_t *last_in_net = NULL;
NET_LOOP (netlist);
{
- routebox_t *last_in_subnet = NULL;
- int j;
-
- for (j = 0; j < NUM_STYLES; j++)
- if (net->Style == rd->augStyles[j].style)
- break;
- CONNECTION_LOOP (net);
- {
- routebox_t *rb = NULL;
- SET_FLAG (DRCFLAG, (PinTypePtr) connection->ptr2);
- if (connection->type == LINE_TYPE)
- {
- LineType *line = (LineType *) connection->ptr2;
-
- /* lines are listed at each end, so skip one */
- /* this should probably by a macro named "BUMP_LOOP" */
- n--;
-
- /* dice up non-straight lines into many tiny obstacles */
- if (line->Point1.X != line->Point2.X
- && line->Point1.Y != line->Point2.Y)
- {
- LineType fake_line = *line;
- int dx = (line->Point2.X - line->Point1.X);
- int dy = (line->Point2.Y - line->Point1.Y);
- int segs = MAX (ABS (dx),
- ABS (dy)) / (4 *
- BLOAT (rd->augStyles[j].
- style) + 1);
- int qq;
- segs = MAX (1, MIN (segs, 32)); /* don't go too crazy */
- dx /= segs;
- dy /= segs;
- for (qq = 0; qq < segs - 1; qq++)
- {
- fake_line.Point2.X = fake_line.Point1.X + dx;
- fake_line.Point2.Y = fake_line.Point1.Y + dy;
- if (fake_line.Point2.X == line->Point2.X
- && fake_line.Point2.Y == line->Point2.Y)
- break;
- rb =
- AddLine (layergroupboxes, connection->group,
- &fake_line, line);
- rb->augStyle = &rd->augStyles[j];
- if (last_in_subnet && rb != last_in_subnet)
- MergeNets (last_in_subnet, rb, ORIGINAL);
- if (last_in_net && rb != last_in_net)
- MergeNets (last_in_net, rb, NET);
- last_in_subnet = last_in_net = rb;
- fake_line.Point1 = fake_line.Point2;
- }
- fake_line.Point2 = line->Point2;
- rb =
- AddLine (layergroupboxes, connection->group, &fake_line,
- line);
- }
- else
- {
- rb =
- AddLine (layergroupboxes, connection->group, line, line);
- }
- }
- else
- switch (connection->type)
- {
- case PAD_TYPE:
- rb =
- AddPad (layergroupboxes, connection->ptr1,
- connection->ptr2);
- break;
- case PIN_TYPE:
- rb = AddPin (layergroupboxes, connection->ptr2, False);
- break;
- case VIA_TYPE:
- rb = AddPin (layergroupboxes, connection->ptr2, True);
- break;
- case POLYGON_TYPE:
- rb =
- AddPolygon (layergroupboxes,
- GetLayerNumber (PCB->Data, connection->ptr1),
- connection->ptr2);
- break;
- }
- assert (rb);
- /* set rb->augStyle! */
- rb->augStyle = &rd->augStyles[j];
- rb->augStyle->Used = True;
- /* update circular connectivity lists */
- if (last_in_subnet && rb != last_in_subnet)
- MergeNets (last_in_subnet, rb, ORIGINAL);
- if (last_in_net && rb != 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));
- }
- END_LOOP;
+ routebox_t *last_in_subnet = NULL;
+ int j;
+
+ for (j = 0; j < NUM_STYLES; j++)
+ if (net->Style == rd->styles[j])
+ break;
+ CONNECTION_LOOP (net);
+ {
+ routebox_t *rb = NULL;
+ SET_FLAG (DRCFLAG, (PinTypePtr) connection->ptr2);
+ if (connection->type == LINE_TYPE)
+ {
+ LineType *line = (LineType *) connection->ptr2;
+
+ /* lines are listed at each end, so skip one */
+ /* this should probably by a macro named "BUMP_LOOP" */
+ n--;
+
+ /* dice up non-straight lines into many tiny obstacles */
+ if (line->Point1.X != line->Point2.X
+ && line->Point1.Y != line->Point2.Y)
+ {
+ LineType fake_line = *line;
+ int dx = (line->Point2.X - line->Point1.X);
+ int dy = (line->Point2.Y - line->Point1.Y);
+ int segs = MAX (ABS (dx),
+ ABS (dy)) / (4 * BLOAT (rd->styles[j]) + 1);
+ int qq;
+ segs = MAX (1, MIN (segs, 32)); /* don't go too crazy */
+ dx /= segs;
+ dy /= segs;
+ for (qq = 0; qq < segs - 1; qq++)
+ {
+ fake_line.Point2.X = fake_line.Point1.X + dx;
+ fake_line.Point2.Y = fake_line.Point1.Y + dy;
+ if (fake_line.Point2.X == line->Point2.X
+ && fake_line.Point2.Y == line->Point2.Y)
+ break;
+ rb =
+ AddLine (layergroupboxes, connection->group,
+ &fake_line, line, rd->styles[j]);
+ if (last_in_subnet && rb != last_in_subnet)
+ MergeNets (last_in_subnet, rb, ORIGINAL);
+ if (last_in_net && rb != last_in_net)
+ MergeNets (last_in_net, rb, NET);
+ last_in_subnet = last_in_net = rb;
+ fake_line.Point1 = fake_line.Point2;
+ }
+ fake_line.Point2 = line->Point2;
+ rb =
+ AddLine (layergroupboxes, connection->group, &fake_line,
+ line, rd->styles[j]);
+ }
+ else
+ {
+ rb =
+ AddLine (layergroupboxes, connection->group, line, line,
+ rd->styles[j]);
+ }
+ }
+ else
+ switch (connection->type)
+ {
+ case PAD_TYPE:
+ rb =
+ AddPad (layergroupboxes, connection->ptr1,
+ connection->ptr2, rd->styles[j]);
+ break;
+ case PIN_TYPE:
+ rb =
+ AddPin (layergroupboxes, connection->ptr2, False,
+ rd->styles[j]);
+ break;
+ case VIA_TYPE:
+ rb =
+ AddPin (layergroupboxes, connection->ptr2, True,
+ rd->styles[j]);
+ break;
+ case POLYGON_TYPE:
+ rb =
+ AddPolygon (layergroupboxes,
+ GetLayerNumber (PCB->Data, connection->ptr1),
+ connection->ptr2, rd->styles[j]);
+ break;
+ }
+ assert (rb);
+ /* update circular connectivity lists */
+ if (last_in_subnet && rb != last_in_subnet)
+ MergeNets (last_in_subnet, rb, ORIGINAL);
+ if (last_in_net && rb != 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->style));
+ rd->max_keep = MAX (rd->max_keep, rb->style->Keepaway);
+ }
+ END_LOOP;
}
END_LOOP;
if (last_net && last_in_net)
- MergeNets (last_net, last_in_net, DIFFERENT_NET);
+ MergeNets (last_net, last_in_net, DIFFERENT_NET);
last_net = last_in_net;
}
END_LOOP;
@@ -1002,7 +1113,7 @@ CreateRouteData ()
if (TEST_FLAG (DRCFLAG, pin))
CLEAR_FLAG (DRCFLAG, pin);
else
- AddPin (layergroupboxes, pin, False);
+ AddPin (layergroupboxes, pin, False, rd->styles[NUM_STYLES]);
}
ENDALL_LOOP;
ALLPAD_LOOP (PCB->Data);
@@ -1010,7 +1121,7 @@ CreateRouteData ()
if (TEST_FLAG (DRCFLAG, pad))
CLEAR_FLAG (DRCFLAG, pad);
else
- AddPad (layergroupboxes, element, pad);
+ AddPad (layergroupboxes, element, pad, rd->styles[NUM_STYLES]);
}
ENDALL_LOOP;
/* add all vias */
@@ -1019,7 +1130,7 @@ CreateRouteData ()
if (TEST_FLAG (DRCFLAG, via))
CLEAR_FLAG (DRCFLAG, via);
else
- AddPin (layergroupboxes, via, True);
+ AddPin (layergroupboxes, via, True, rd->styles[NUM_STYLES]);
}
END_LOOP;
@@ -1029,61 +1140,64 @@ CreateRouteData ()
/* add all (non-rat) lines */
LINE_LOOP (LAYER_PTR (i));
{
- if (TEST_FLAG (DRCFLAG, line))
- {
- CLEAR_FLAG (DRCFLAG, line);
- continue;
- }
- /* dice up non-straight lines into many tiny obstacles */
- if (line->Point1.X != line->Point2.X
- && line->Point1.Y != line->Point2.Y)
- {
- LineType fake_line = *line;
- int dx = (line->Point2.X - line->Point1.X);
- int dy = (line->Point2.Y - line->Point1.Y);
- int segs = MAX (ABS (dx), ABS (dy)) / (4 * rd->max_bloat + 1);
- int qq;
- segs = MAX (1, MIN (segs, 32)); /* don't go too crazy */
- dx /= segs;
- dy /= segs;
- for (qq = 0; qq < segs - 1; qq++)
- {
- fake_line.Point2.X = fake_line.Point1.X + dx;
- fake_line.Point2.Y = fake_line.Point1.Y + dy;
- if (fake_line.Point2.X == line->Point2.X
- && fake_line.Point2.Y == line->Point2.Y)
- break;
- AddLine (layergroupboxes, layergroup, &fake_line, line);
- fake_line.Point1 = fake_line.Point2;
- }
- fake_line.Point2 = line->Point2;
- AddLine (layergroupboxes, layergroup, &fake_line, line);
- }
- else
- {
- AddLine (layergroupboxes, layergroup, line, line);
- }
+ if (TEST_FLAG (DRCFLAG, line))
+ {
+ CLEAR_FLAG (DRCFLAG, line);
+ continue;
+ }
+ /* dice up non-straight lines into many tiny obstacles */
+ if (line->Point1.X != line->Point2.X
+ && line->Point1.Y != line->Point2.Y)
+ {
+ LineType fake_line = *line;
+ int dx = (line->Point2.X - line->Point1.X);
+ int dy = (line->Point2.Y - line->Point1.Y);
+ int segs = MAX (ABS (dx), ABS (dy)) / (4 * rd->max_bloat + 1);
+ int qq;
+ segs = MAX (1, MIN (segs, 32)); /* don't go too crazy */
+ dx /= segs;
+ dy /= segs;
+ for (qq = 0; qq < segs - 1; qq++)
+ {
+ fake_line.Point2.X = fake_line.Point1.X + dx;
+ fake_line.Point2.Y = fake_line.Point1.Y + dy;
+ if (fake_line.Point2.X == line->Point2.X
+ && fake_line.Point2.Y == line->Point2.Y)
+ break;
+ AddLine (layergroupboxes, layergroup, &fake_line, line,
+ rd->styles[NUM_STYLES]);
+ fake_line.Point1 = fake_line.Point2;
+ }
+ fake_line.Point2 = line->Point2;
+ AddLine (layergroupboxes, layergroup, &fake_line, line,
+ rd->styles[NUM_STYLES]);
+ }
+ else
+ {
+ AddLine (layergroupboxes, layergroup, line, line,
+ rd->styles[NUM_STYLES]);
+ }
}
END_LOOP;
/* add all polygons */
POLYGON_LOOP (LAYER_PTR (i));
{
- if (TEST_FLAG (DRCFLAG, polygon))
- CLEAR_FLAG (DRCFLAG, polygon);
- else
- AddPolygon (layergroupboxes, i, polygon);
+ if (TEST_FLAG (DRCFLAG, polygon))
+ CLEAR_FLAG (DRCFLAG, polygon);
+ else
+ AddPolygon (layergroupboxes, i, polygon, rd->styles[NUM_STYLES]);
}
END_LOOP;
/* add all copper text */
TEXT_LOOP (LAYER_PTR (i));
{
- AddText (layergroupboxes, layergroup, text);
+ AddText (layergroupboxes, layergroup, text, rd->styles[NUM_STYLES]);
}
END_LOOP;
/* add all arcs */
ARC_LOOP (LAYER_PTR (i));
{
- AddArc (layergroupboxes, layergroup, arc);
+ AddArc (layergroupboxes, layergroup, arc, rd->styles[NUM_STYLES]);
}
END_LOOP;
}
@@ -1091,18 +1205,10 @@ CreateRouteData ()
/* 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);
+ r_create_tree ((const BoxType **) layergroupboxes[i].Ptr,
+ layergroupboxes[i].PtrN, 1);
}
if (AutoRouteParameters.use_vias)
@@ -1112,16 +1218,15 @@ CreateRouteData ()
/* 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;
- }
+ {
+ POINTER_LOOP (&layergroupboxes[i]);
+ {
+ routebox_t *rb = (routebox_t *) * ptr;
+ if (!rb->flags.clear_poly)
+ mtspace_add (rd->mtspace, &rb->box, FIXED, rb->style->Keepaway);
+ }
+ END_LOOP;
+ }
}
/* free pointer lists */
for (i = 0; i < max_layer; i++)
@@ -1150,7 +1255,7 @@ DestroyRouteData (routedata_t ** rd)
static void
RB_up_count (routebox_t * rb)
{
- assert (rb->flags.orphan);
+ assert (rb->flags.homeless);
rb->refcount++;
}
@@ -1159,15 +1264,13 @@ RB_up_count (routebox_t * rb)
static void
RB_down_count (routebox_t * rb)
{
- assert (rb->flags.orphan);
+ assert (rb->type == EXPANSION_AREA);
+ assert (rb->flags.homeless);
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);
+ if (rb->parent.expansion_area->flags.homeless)
+ RB_down_count (rb->parent.expansion_area);
free (rb);
}
}
@@ -1188,24 +1291,21 @@ ResetSubnet (routebox_t * net)
static inline cost_t
cost_to_point_on_layer (const CheapPointType * p1,
- const CheapPointType * p2, Cardinal point_layer)
+ const CheapPointType * p2, Cardinal point_layer)
{
cost_t x_dist = p1->X - p2->X, y_dist = p1->Y - p2->Y, r;
- if (bad_x[point_layer])
- x_dist *= AutoRouteParameters.DirectionPenalty;
- else if (bad_y[point_layer])
- y_dist *= AutoRouteParameters.DirectionPenalty;
+ x_dist *= x_cost[point_layer];
+ y_dist *= y_cost[point_layer];
/* cost is proportional to orthogonal distance. */
r = ABS (x_dist) + ABS (y_dist);
- /* penalize the surface layers in order to minimize SMD pad congestion */
- if (point_layer == front || point_layer == back)
- r *= AutoRouteParameters.SurfacePenalty;
+ if (p1->X != p2->X && p1->Y != p2->Y)
+ r += AutoRouteParameters.JogPenalty;
return r;
}
static cost_t
cost_to_point (const CheapPointType * p1, Cardinal point_layer1,
- const CheapPointType * p2, Cardinal point_layer2)
+ 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 */
@@ -1219,7 +1319,7 @@ cost_to_point (const CheapPointType * p1, Cardinal point_layer1,
*/
static cost_t
cost_to_layerless_box (const CheapPointType * p, Cardinal point_layer,
- const BoxType * b)
+ const BoxType * b)
{
CheapPointType p2 = closest_point_in_box (p, b);
register cost_t c1, c2;
@@ -1248,83 +1348,93 @@ TargetPoint (CheapPointType * nextpoint, const routebox_t * target)
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;
+ abs (target->parent.pad->Point2.X - nextpoint->X))
+ nextpoint->X = target->parent.pad->Point1.X;
else
- nextpoint->X = target->parent.pad->Point2.X;
+ 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;
+ abs (target->parent.pad->Point2.Y - nextpoint->Y))
+ nextpoint->Y = target->parent.pad->Point1.Y;
else
- nextpoint->Y = target->parent.pad->Point2.Y;
+ nextpoint->Y = target->parent.pad->Point2.Y;
return True;
}
- else if (target->type == VIA)
+ else
{
- nextpoint->X = (target->box.X1 + target->box.X2) / 2;
- nextpoint->Y = (target->box.Y1 + target->box.Y2) / 2;
+ nextpoint->X = CENTER_X (target->sbox);
+ nextpoint->Y = CENTER_Y (target->sbox);
}
return False;
}
/* return the *minimum cost* from a point to a route box, including possible
- * via costs if the route box is on a different layer. */
+ * via costs if the route box is on a different layer.
+ * assume routbox is bloated unless it is an expansion area
+ */
static cost_t
cost_to_routebox (const CheapPointType * p, Cardinal point_layer,
- const routebox_t * rb)
+ const routebox_t * rb)
{
- register cost_t c1, c2, trial = 0;
- CheapPointType p2 = closest_point_in_box (p, &rb->box);
-// if (rb->flags.target)
- // TargetPoint (&p2, rb);
+ register cost_t trial = 0;
+ CheapPointType p2 = closest_point_in_routebox (p, rb);
if (!usedGroup[point_layer] || !usedGroup[rb->group])
trial = AutoRouteParameters.NewLayerPenalty;
- if ((p->X - p2.X) * (p->Y - p2.Y) != 0)
+ if ((p2.X - p->X) * (p2.Y - p->Y) != 0)
trial += AutoRouteParameters.JogPenalty;
/* special case for defered via searching */
- if (point_layer > max_layer)
- return trial + cost_to_point_on_layer (p, &p2, rb->group);
- if (point_layer == rb->group)
- return trial + cost_to_point_on_layer (p, &p2, point_layer);
+ if (point_layer > max_layer || point_layer == rb->group)
+ return trial + ABS (p2.X - p->X) + ABS (p2.Y - p->Y);
+ /* if this target is only a via away, then the via is cheaper than the congestion */
+ if (p->X == p2.X && p->Y == p2.Y)
+ return trial + 1;
trial += AutoRouteParameters.ViaCost;
- c1 = cost_to_point_on_layer (p, &p2, point_layer);
- c2 = cost_to_point_on_layer (p, &p2, rb->group);
- trial += MIN (c1, c2);
+ trial += ABS (p2.X - p->X) + ABS (p2.Y - p->Y);
return trial;
}
+
static BoxType
bloat_routebox (routebox_t * rb)
{
BoxType r;
- BDimension keepaway;
+ LocationType 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"
- * brethren. */
- 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++;
+
+ if (rb->flags.nobloat)
+ return rb->sbox;
+
+ /* Obstacle exclusion zones get bloated by the larger of
+ * the two required clearances plus half the track width.
+ */
+ keepaway = MAX (AutoRouteParameters.style->Keepaway, rb->style->Keepaway);
+ r = bloat_box (&rb->sbox, keepaway +
+ HALF_THICK (AutoRouteParameters.style->Thick));
return r;
}
-#ifdef ROUTE_DEBUG /* only for debugging expansion areas */
+#ifdef ROUTE_DEBUG /* only for debugging expansion areas */
+
+void
+fillbox (const BoxType * b)
+{
+ LayerTypePtr SLayer = LAYER_PTR (0);
+ gui->set_color (Output.fgGC, SLayer->Color);
+ gui->fill_rect (Output.fgGC, b->X1, b->Y1, b->X2, b->Y2);
+}
+
/* makes a line on the solder layer silk surrounding the box */
void
showbox (BoxType b, Dimension thickness, int group)
{
LineTypePtr line;
LayerTypePtr SLayer = LAYER_PTR (group);
- if (!showboxen)
+ if (showboxen < -1)
+ return;
+ if (showboxen != -1 && showboxen != group)
return;
+
gui->set_line_width (Output.fgGC, thickness);
gui->set_line_cap (Output.fgGC, Trace_Cap);
gui->set_color (Output.fgGC, SLayer->Color);
@@ -1333,45 +1443,42 @@ showbox (BoxType b, Dimension thickness, int group)
gui->draw_line (Output.fgGC, b.X1, b.Y2, b.X2, b.Y2);
gui->draw_line (Output.fgGC, b.X1, b.Y1, b.X1, b.Y2);
gui->draw_line (Output.fgGC, b.X2, b.Y1, b.X2, b.Y2);
+ gui->use_mask (HID_FLUSH_DRAW_Q);
-#if XXX
- if (XtAppPending (Context))
- XtAppProcessEvent (Context, XtIMAll);
- XSync (Dpy, False);
-#endif
-
+#if 1
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,
- MakeFlags (0));
+ b.X1, b.Y1, b.X2, b.Y1, thickness, 0,
+ MakeFlags (0));
AddObjectToCreateUndoList (LINE_TYPE,
- LAYER_PTR (max_layer + COMPONENT_LAYER), line,
- line);
+ 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,
- MakeFlags (0));
+ b.X1, b.Y2, b.X2, b.Y2, thickness, 0,
+ MakeFlags (0));
AddObjectToCreateUndoList (LINE_TYPE,
- LAYER_PTR (max_layer + COMPONENT_LAYER),
- line, line);
+ 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,
- MakeFlags (0));
+ b.X1, b.Y1, b.X1, b.Y2, thickness, 0,
+ MakeFlags (0));
AddObjectToCreateUndoList (LINE_TYPE,
- LAYER_PTR (max_layer + COMPONENT_LAYER), line,
- line);
+ 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,
- MakeFlags (0));
+ b.X2, b.Y1, b.X2, b.Y2, thickness, 0,
+ MakeFlags (0));
AddObjectToCreateUndoList (LINE_TYPE,
- LAYER_PTR (max_layer + COMPONENT_LAYER),
- line, line);
+ LAYER_PTR (max_layer + COMPONENT_LAYER),
+ line, line);
}
+#endif
}
#endif
@@ -1399,6 +1506,8 @@ showedge (edge_t * e)
case EAST:
gui->draw_line (Output.fgGC, b->X2, b->Y1, b->X2, b->Y2);
break;
+ default:
+ break;
}
}
#endif
@@ -1407,8 +1516,8 @@ showedge (edge_t * e)
static void
showroutebox (routebox_t * rb)
{
- showbox (rb->box, rb->flags.source ? 8 : (rb->flags.target ? 4 : 1),
- rb->flags.is_via ? max_layer + COMPONENT_LAYER : rb->group);
+ showbox (rb->sbox, rb->flags.source ? 20 : (rb->flags.target ? 10 : 1),
+ rb->flags.is_via ? max_layer + COMPONENT_LAYER : rb->group);
}
#endif
@@ -1442,7 +1551,7 @@ EraseRouteBox (routebox_t * rb)
static routebox_t *
route_parent (routebox_t * rb)
{
- while (rb->flags.orphan && rb->underlying == NULL && !rb->flags.is_via)
+ while (rb->flags.homeless && !rb->flags.is_via)
{
assert (rb->type == EXPANSION_AREA);
rb = rb->parent.expansion_area;
@@ -1451,14 +1560,71 @@ route_parent (routebox_t * rb)
return rb;
}
+static vector_t *
+path_conflicts (routebox_t * rb, routebox_t * conflictor, Boolean branch)
+{
+ if (branch)
+ rb->conflicts_with = vector_duplicate (rb->conflicts_with);
+ else if (!rb->conflicts_with)
+ rb->conflicts_with = vector_create ();
+ vector_append (rb->conflicts_with, conflictor);
+ return rb->conflicts_with;
+}
+
+/* Touch everything (except fixed) on each net found
+ * in the conflicts vector. If the vector is different
+ * from the last one touched, untouch the last batch
+ * and touch the new one. Always call with touch=1
+ * (except for recursive call). Call with NULL, 1 to
+ * clear the last batch touched.
+ *
+ * touched items become invisible to current path
+ * so we don't encounter the same conflictor more
+ * than once
+ */
+
+static void
+touch_conflicts (vector_t * conflicts, int touch)
+{
+ static vector_t *last = NULL;
+ static int last_size = 0;
+ int i, n;
+ i = 0;
+ if (touch)
+ {
+ if (last && conflicts != last)
+ touch_conflicts (last, 0);
+ if (!conflicts)
+ return;
+ last = conflicts;
+ i = last_size;
+ }
+ n = vector_size (conflicts);
+ for (; i < n; i++)
+ {
+ routebox_t *rb = (routebox_t *) vector_element (conflicts, i);
+ routebox_t *p;
+ LIST_LOOP (rb, same_net, p);
+ if (!p->flags.fixed)
+ p->flags.touched = touch;
+ END_LOOP;
+ }
+ if (!touch)
+ {
+ last = NULL;
+ last_size = 0;
+ }
+ else
+ last_size = n;
+}
+
/* 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)
+nonhomeless_parent (routebox_t * rb)
{
- rb = route_parent (rb);
- return rb->underlying ? rb->underlying : rb;
+ return route_parent (rb);
}
/* some routines to find the minimum *cost* from a cost point to
@@ -1497,22 +1663,22 @@ __found_new_guess (const BoxType * box, void *cl)
if (cost_to_guess < mtc->nearest_cost)
{
mtc->nearest = guess;
- mtc->nearest_cost = cost_to_guess; /* this is our new guess! */
+ mtc->nearest_cost = cost_to_guess; /* this is our new guess! */
return 1;
}
else
- return 0; /* not less expensive than our last guess */
+ 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)
+ 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? */
+ assert (target_guess == NULL || target_guess->flags.target); /* this is a target, right? */
mtc.CostPoint = CostPoint;
mtc.CostPointLayer = CostPointLayer;
mtc.nearest = target_guess;
@@ -1523,7 +1689,7 @@ mincost_target_to_point (const CheapPointType * CostPoint,
mtc.nearest_cost = EXPENSIVE;
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? */
+ assert (mtc.nearest->flags.target); /* this is a target, right? */
return mtc.nearest;
}
@@ -1531,17 +1697,18 @@ mincost_target_to_point (const CheapPointType * CostPoint,
/* 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)
+ 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));
+ memset ((void *) e, 0, sizeof (*e));
assert (e);
e->rb = rb;
- if (rb->flags.orphan)
+ if (rb->flags.homeless)
RB_up_count (rb);
e->cost_point.X = CostPointX;
e->cost_point.Y = CostPointY;
@@ -1551,40 +1718,35 @@ CreateEdge (routebox_t * rb,
if (targets)
e->mincost_target =
mincost_target_to_point (&e->cost_point, rb->group,
- targets, mincost_target_guess);
+ 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);
+ assert (e->rb && e->mincost_target); /* valid edge? */
+ assert (!e->flags.is_via || e->expand_dir == ALL);
/* 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)));
+#if 0
+ assert (rb->type == PLANE || rb->conflicts_with != NULL || rb->flags.is_via
+ || rb->flags.is_thermal
+ || ((expand_dir == NORTH || expand_dir == SOUTH) ? rb->sbox.X1 <=
+ CostPointX && CostPointX < rb->sbox.X2
+ && CostPointY == (expand_dir ==
+ NORTH ? rb->sbox.Y1 : rb->sbox.Y2 - 1) :
+ /* expand_dir==EAST || expand_dir==WEST */
+ rb->sbox.Y1 <= CostPointY && CostPointY < rb->sbox.Y2 &&
+ CostPointX == (expand_dir ==
+ EAST ? rb->sbox.X2 - 1 : rb->sbox.X1)));
+#endif
assert (__edge_is_good (e));
/* done */
return e;
}
-static cost_t
-going_away (CheapPointType first, CheapPointType second, routebox_t * target)
-{
- CheapPointType t = closest_point_in_box (&second, &target->box);
- if (SQUARE (t.X - second.X) + SQUARE (t.Y - second.Y) >
- SQUARE (t.X - first.X) + SQUARE (t.Y - first.Y))
- return AutoRouteParameters.AwayPenalty;
- return 1;
-}
-
/* 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)
+ edge_t * previous_edge, rtree_t * targets, routebox_t * guess)
{
BoxType thisbox;
CheapPointType thiscost, prevcost;
@@ -1592,31 +1754,28 @@ CreateEdge2 (routebox_t * rb, direction_t expand_dir,
assert (rb && previous_edge);
/* okay, find cheapest costpoint to costpoint of previous edge */
- thisbox = edge_to_box (&rb->box, expand_dir);
+ thisbox = edge_to_box (rb, expand_dir);
prevcost = previous_edge->cost_point;
/* find point closest to target */
thiscost = closest_point_in_box (&prevcost, &thisbox);
/* compute cost-to-point */
d = cost_to_point_on_layer (&prevcost, &thiscost, rb->group);
- /* penalize getting further from the target */
- d *= going_away (prevcost, thiscost, previous_edge->mincost_target);
/* add in jog penalty */
- if (previous_edge->expand_dir != expand_dir
- && (!guess || !guess->flags.target))
+ 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);
+ 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 * parent, edge_t * previous_edge,
+ conflict_t to_site_conflict,
+ conflict_t through_site_conflict, rtree_t * targets)
{
routebox_t *rb;
CheapPointType costpoint;
@@ -1628,98 +1787,123 @@ CreateViaEdge (const BoxType * area, Cardinal group,
scale[1] = AutoRouteParameters.LastConflictPenalty;
scale[2] = AutoRouteParameters.ConflictPenalty;
- assert (__box_is_good (area));
+ assert (box_is_good (area));
assert (AutoRouteParameters.with_conflicts ||
- (to_site_conflict == NO_CONFLICT &&
- through_site_conflict == NO_CONFLICT));
+ (to_site_conflict == NO_CONFLICT &&
+ through_site_conflict == NO_CONFLICT));
rb = CreateExpansionArea (area, group, parent, True, previous_edge);
rb->flags.is_via = 1;
+ rb->came_from = ALL;
#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)
+ if (previous_edge->flags.in_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;
+ pnt.X = CENTER_X (*area);
+ pnt.Y = CENTER_Y (*area);
target = mincost_target_to_point (&pnt, rb->group,
- targets,
- previous_edge->mincost_target);
+ 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);
+ pnt.X = CENTER_X (target->box);
+ pnt.Y = CENTER_Y (target->box);
+ costpoint = closest_point_in_routebox (&pnt, rb);
+ /* we moved from the previous cost point through the plane which is free travel */
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);
+ (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, ALL, NULL);
+ ne->mincost_target = target;
}
else
{
- costpoint = closest_point_in_box (&previous_edge->cost_point, &rb->box);
+ routebox_t *target;
+ target = previous_edge->mincost_target;
+ costpoint = closest_point_in_routebox (&previous_edge->cost_point, rb);
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);
+ (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));
+ /* if the target is just this via away, then this via is cheaper */
+ if (target->group == group &&
+ point_in_shrunk_box (target, costpoint.X, costpoint.Y))
+ d -= AutoRouteParameters.ViaCost / 2;
+ ne =
+ CreateEdge (rb, costpoint.X, costpoint.Y,
+ previous_edge->cost_to_point + d,
+ previous_edge->mincost_target, ALL, targets);
}
- ne->flags.expand_all_sides = ne->flags.is_via = 1;
+ 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 */
+/* Presently once we "jump inside" the conflicting object
+ * we consider it a routing highway to travel inside since
+ * it will become available if the conflict is elliminated.
+ * That is why we ignore the interior_edge argument.
+ */
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 * 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 (!container->flags.homeless);
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 (container->flags.touched == 0);
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);
+ /* use the caller's idea of what this box should be */
+ rb =
+ CreateExpansionArea (interior_edge, previous_edge->rb->group,
+ previous_edge->rb, True, previous_edge);
+ path_conflicts (rb, container, True); /* crucial! */
+ costpoint =
+ closest_point_in_box (&previous_edge->cost_point, interior_edge);
+ 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;
+ d += previous_edge->cost_to_point;
+ ne = CreateEdge (rb, costpoint.X, costpoint.Y, d, NULL, ALL, targets);
+ ne->flags.is_interior = 1;
assert (__edge_is_good (ne));
return ne;
}
static void
+KillEdge (void *edge)
+{
+ edge_t *e = (edge_t *) edge;
+ assert (e);
+ if (e->rb->flags.homeless)
+ RB_down_count (e->rb);
+ if (e->flags.via_search)
+ mtsFreeWork (&e->work);
+ free (e);
+}
+
+static void
DestroyEdge (edge_t ** e)
{
assert (e && *e);
- if ((*e)->rb->flags.orphan)
- RB_down_count ((*e)->rb); /* possibly free rb */
- if ((*e)->flags.via_search)
- mtsFreeWork (&(*e)->work);
- free (*e);
+ KillEdge (*e);
*e = NULL;
}
@@ -1727,31 +1911,9 @@ DestroyEdge (edge_t ** e)
static cost_t
edge_cost (const edge_t * e, const cost_t too_big)
{
- cost_t penalty = 0;
- if (e->rb->type == PLANE)
- return 1; /* thermals are cheap */
- if (!usedGroup[e->rb->group])
- penalty = AutoRouteParameters.NewLayerPenalty;
- switch (e->expand_dir)
- {
- case NORTH:
- if (e->mincost_target->box.Y1 >= e->rb->box.Y1)
- penalty += AutoRouteParameters.WrongWayPenalty;
- break;
- case SOUTH:
- if (e->mincost_target->box.Y2 <= e->rb->box.Y2)
- penalty += AutoRouteParameters.WrongWayPenalty;
- break;
- case WEST:
- if (e->mincost_target->box.X1 >= e->rb->box.X1)
- penalty += AutoRouteParameters.WrongWayPenalty;
- break;
- case EAST:
- if (e->mincost_target->box.X2 >= e->rb->box.X2)
- penalty += AutoRouteParameters.WrongWayPenalty;
- break;
- }
- penalty += e->cost_to_point;
+ cost_t penalty = e->cost_to_point;
+ if (e->rb->flags.is_thermal || e->rb->type == PLANE)
+ return penalty; /* thermals are cheap */
if (penalty > too_big)
return penalty;
@@ -1760,109 +1922,35 @@ edge_cost (const edge_t * e, const cost_t too_big)
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
+ * edge. Note that the return 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)
+edge_to_box (const routebox_t * rb, direction_t expand_dir)
{
- BoxType b = *box;
+ BoxType b = shrink_routebox (rb);
/* narrow box down to just the appropriate edge */
switch (expand_dir)
{
case NORTH:
- b.Y2 = b.Y1;
+ b.Y2 = b.Y1 + 1;
break;
case EAST:
- b.X1 = b.X2;
+ b.X1 = b.X2 - 1;
break;
case SOUTH:
- b.Y1 = b.Y2;
+ b.Y1 = b.Y2 - 1;
break;
case WEST:
- b.X2 = b.X1;
+ b.X2 = b.X1 + 1;
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 the limited region (which may be invalid). */
-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.X1 <= region.X2);
- assert (lbox.X2 >= region.X1);
- region.Y1 = lbox.Y2;
- /* now rotate back */
- ROTATEBOX_FROM_NORTH (region, e->expand_dir);
- return region;
-}
-
struct broken_boxes
{
BoxType left, center, right;
@@ -1871,7 +1959,7 @@ struct broken_boxes
static struct broken_boxes
break_box_edge (const BoxType * original, direction_t which_edge,
- routebox_t * breaker)
+ routebox_t * breaker)
{
BoxType origbox, breakbox;
struct broken_boxes result;
@@ -1882,10 +1970,10 @@ break_box_edge (const BoxType * original, direction_t which_edge,
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);
+ result.right.Y1 = result.center.Y1 = result.left.Y1 = origbox.Y1;
+ result.right.Y2 = result.center.Y2 = result.left.Y2 = origbox.Y1 + 1;
+ /* validity of breaker is not important because the boxes are marked invalid */
+ //assert (breakbox.X1 <= origbox.X2 && breakbox.X2 >= origbox.X1);
/* left edge piece */
result.left.X1 = origbox.X1;
result.left.X2 = breakbox.X1;
@@ -1932,241 +2020,1016 @@ edge_intersect (const BoxType * child, const BoxType * parent)
* 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)
+ routebox_t * parent,
+ Boolean relax_edge_requirements, edge_t * src_edge)
{
routebox_t *rb = (routebox_t *) malloc (sizeof (*rb));
+ memset ((void *) rb, 0, sizeof (*rb));
assert (area && parent);
- init_const_box (rb, area->X1, area->Y1, area->X2, area->Y2);
+ init_const_box (rb, area->X1, area->Y1, area->X2, area->Y2, 0);
rb->group = group;
rb->type = EXPANSION_AREA;
- rb->cost_point = src_edge->cost_point;
- rb->cost = src_edge->cost_to_point;
- /* should always share edge with parent */
- assert (relax_edge_requirements ? edge_intersect (&rb->box, &parent->box)
- : share_edge (&rb->box, &parent->box));
+ /* should always share edge or overlap with parent */
+ assert (relax_edge_requirements ? box_intersect (&rb->sbox, &parent->sbox)
+ : share_edge (&rb->sbox, &parent->sbox));
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;
- InitLists (rb);
+ rb->cost_point =
+ closest_point_in_box (&rb->parent.expansion_area->cost_point, area);
+ rb->cost =
+ rb->parent.expansion_area->cost +
+ cost_to_point_on_layer (&rb->parent.expansion_area->cost_point,
+ &rb->cost_point, rb->group);
+ assert (relax_edge_requirements ? edge_intersect (&rb->sbox, &parent->sbox)
+ : share_edge (&rb->sbox, &parent->sbox));
+ rb->flags.homeless = 1;
+ rb->flags.nobloat = 1;
+ rb->style = AutoRouteParameters.style;
+ rb->conflicts_with = parent->conflicts_with;
+/* we will never link an EXPANSION_AREA into the nets because they
+ * are *ONLY* used for path searching. No need to call InitLists ()
+ */
+ rb->came_from = src_edge->expand_dir;
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
showroutebox (rb);
#endif /* ROUTE_DEBUG && DEBUG_SHOW_EXPANSION_BOXES */
return rb;
}
-Boolean
-no_loops (routebox_t * chain, routebox_t * rb)
+/*------ Expand ------*/
+struct E_result
{
- while (!rb->flags.source)
- {
- rb = rb->parent.expansion_area;
- if (rb == chain)
- return False;
- }
- return True;
-}
-
-/*------ FindBlocker ------*/
-struct FindBlocker_info
-{
- edge_t *expansion_edge;
- BDimension maxbloat;
- routebox_t *blocker;
- LocationType min_dist;
- BoxType north_box;
- Boolean not_via;
+ routebox_t *parent;
+ routebox_t *n, *e, *s, *w;
+ BDimension keep, bloat;
+ BoxType inflated, orig;
+ int done;
};
-/* helper methods for __FindBlocker */
+/* test method for Expand()
+ * this routebox potentially is a blocker limiting expansion
+ * if this is so, we limit the inflate box so another exactly
+ * like it wouldn't be seen. We do this while keep the inflated
+ * box as large as possible.
+ */
static int
-__FindBlocker_rect_in_reg (const BoxType * box, void *cl)
+__Expand_this_rect (const BoxType * box, void *cl)
{
- struct FindBlocker_info *fbi = (struct FindBlocker_info *) cl;
+ struct E_result *res = (struct E_result *) cl;
routebox_t *rb = (routebox_t *) box;
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 (rbox.Y2 < fbi->north_box.Y1 - fbi->min_dist)
+ BDimension dn, de, ds, dw, bloat;
+
+ /* we don't see conflicts already encountered */
+ if (rb->flags.touched)
return 0;
- /* this is a box; it has to jump through a few more hoops */
- if (rb == nonorphan_parent (fbi->expansion_edge->rb))
- return 0; /* this is the parent */
- if (rb->type == EXPANSION_AREA && fbi->not_via
- && fbi->expansion_edge->cost_to_point +
- AutoRouteParameters.SearchPenalty < rb->cost)
+
+ /* The inflated box outer edges include its own
+ * track width plus its own keepaway.
+ *
+ * To check for intersection, we need to expand
+ * anything with greater keepaway by its excess
+ * keepaway.
+ *
+ * If something has nobloat then we need to shrink
+ * the inflated box back and see if it still touches.
+ */
+
+ if (rb->flags.nobloat)
{
- CheapPointType cp;
- cp = closest_point_in_box (&fbi->expansion_edge->cost_point, box);
- if (cost_to_point_on_layer
- (&fbi->expansion_edge->cost_point, &cp,
- rb->group) + fbi->expansion_edge->cost_to_point <
- 1.2 * (rb->cost +
- cost_to_point_on_layer (&rb->cost_point, &cp, rb->group))
- && no_loops (rb, fbi->expansion_edge->rb))
- return 0; /* this region may cost less from this direction */
+ rbox = rb->sbox;
+ bloat = res->bloat;
+ if (rbox.X2 <= res->inflated.X1 + bloat ||
+ rbox.X1 >= res->inflated.X2 - bloat ||
+ rbox.Y1 >= res->inflated.Y2 - bloat ||
+ rbox.Y2 <= res->inflated.Y1 + bloat)
+ return 0; /* doesn't touch */
}
- /* 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);
+ else
+ {
+ if (rb->style->Keepaway > res->keep)
+ rbox = bloat_box (&rb->sbox, rb->style->Keepaway - res->keep);
+ else
+ rbox = rb->sbox;
+
+ if (rbox.X2 <= res->inflated.X1 || rbox.X1 >= res->inflated.X2
+ || rbox.Y1 >= res->inflated.Y2 || rbox.Y2 <= res->inflated.Y1)
+ return 0; /* doesn't touch */
+ bloat = 0;
+ }
+
+ /* this is an intersecting box; it has to jump through a few more hoops */
+ if (rb == res->parent || rb->parent.expansion_area == res->parent)
+ return 0; /* don't see what we came from */
+
+ /* if we are expanding a source edge, don't let other sources
+ * or their expansions stop us.
+ */
+#if 1
+ if (res->parent->flags.source)
+ if (rb->flags.source
+ || (rb->type == EXPANSION_AREA
+ && rb->parent.expansion_area->flags.source))
+ return 0;
+#endif
+
+ /* we ignore via expansion boxes because maybe its
+ * cheaper to get there without the via through
+ * the path we're exploring now.
*/
+ if (rb->flags.is_via && rb->type == EXPANSION_AREA)
+ return 0;
+
+ if (rb->type == PLANE) /* expanding inside a plane is not good */
+ {
+ if (rbox.X1 < res->orig.X1 && rbox.X2 > res->orig.X2 &&
+ rbox.Y1 < res->orig.Y1 && rbox.Y2 > res->orig.Y2)
+ {
+ res->inflated = bloat_box (&res->orig, res->bloat);
+ return 1;
+ }
+ }
+ /* calculate the distances from original box to this blocker */
+ dn = de = ds = dw = 0;
+ if (!(res->done & _NORTH) && rbox.Y1 <= res->orig.Y1
+ && rbox.Y2 > res->inflated.Y1)
+ dn = res->orig.Y1 - rbox.Y2;
+ if (!(res->done & _EAST) && rbox.X2 >= res->orig.X2
+ && rbox.X1 < res->inflated.X2)
+ de = rbox.X1 - res->orig.X2;
+ if (!(res->done & _SOUTH) && rbox.Y2 >= res->orig.Y2
+ && rbox.Y1 < res->inflated.Y2)
+ ds = rbox.Y1 - res->orig.Y2;
+ if (!(res->done & _WEST) && rbox.X1 <= res->orig.X1
+ && rbox.X2 > res->inflated.X1)
+ dw = res->orig.X1 - rbox.X2;
+ if (dn <= 0 && de <= 0 && ds <= 0 && dw <= 0)
+ return 1;
+ /* now shrink the inflated box to the largest blocking direction */
+ if (dn >= de && dn >= ds && dn >= dw)
+ {
+ res->inflated.Y1 = rbox.Y2 - bloat;
+ res->n = rb;
+ }
+ else if (de >= ds && de >= dw)
+ {
+ res->inflated.X2 = rbox.X1 + bloat;
+ res->e = rb;
+ }
+ else if (ds >= dw)
+ {
+ res->inflated.Y2 = rbox.Y1 + bloat;
+ res->s = rb;
+ }
+ else
+ {
+ res->inflated.X1 = rbox.X2 - bloat;
+ res->w = rb;
+ }
return 1;
}
-static int
-__FindBlocker_reg_in_sea (const BoxType * region, void *cl)
+
+static Boolean
+boink_box (routebox_t * rb, struct E_result *res, direction_t dir)
{
- struct FindBlocker_info *fbi = (struct FindBlocker_info *) cl;
- BoxType rbox;
- rbox = bloat_box (region, fbi->maxbloat);
- switch (fbi->expansion_edge->expand_dir)
+ LocationType bloat;
+ if (rb->style->Keepaway > res->keep)
+ bloat = res->keep - rb->style->Keepaway;
+ else
+ bloat = 0;
+ if (rb->flags.nobloat)
+ bloat = res->bloat;
+ switch (dir)
{
- case WEST:
- if (rbox.X2 < fbi->north_box.Y1 - fbi->min_dist ||
- -rbox.Y2 > fbi->north_box.X2 ||
- -rbox.Y1 < fbi->north_box.X1 || rbox.X1 > fbi->north_box.Y1)
- return 0;
- return 1;
+ case NORTH:
case SOUTH:
- if (-rbox.Y1 < fbi->north_box.Y1 - fbi->min_dist ||
- -rbox.X2 > fbi->north_box.X2 ||
- -rbox.X1 < fbi->north_box.X1 || -rbox.Y2 > fbi->north_box.Y1)
- return 0;
- return 1;
+ if (rb->sbox.X2 <= res->inflated.X1 + bloat
+ || rb->sbox.X1 >= res->inflated.X2 - bloat)
+ return False;
+ return True;
case EAST:
- if (-rbox.X1 < fbi->north_box.Y1 - fbi->min_dist ||
- rbox.Y1 > fbi->north_box.X2 ||
- rbox.Y2 < fbi->north_box.X1 || -rbox.X2 > fbi->north_box.Y1)
- return 0;
- return 1;
- case NORTH:
- if (rbox.Y2 < fbi->north_box.Y1 - fbi->min_dist ||
- rbox.X1 > fbi->north_box.X2 ||
- rbox.X2 < fbi->north_box.X1 || rbox.Y1 > fbi->north_box.Y1)
- return 0;
- return 1;
+ case WEST:
+ if (rb->sbox.Y1 >= res->inflated.Y2 - bloat
+ || rb->sbox.Y2 <= res->inflated.Y1 + bloat)
+ return False;
+ return True;
+ break;
default:
assert (0);
}
- return 1;
+ return False;
}
-/* main FindBlocker routine. Returns NULL if no neighbor in the
- * requested direction.
- * - region is closed on all edges -
+/* main Expand routine.
+ *
+ * The expansion probe edge includes the keepaway and half thickness
+ * as the search is performed in order to see everything relevant.
+ * The result is backed off by this amount before being returned.
+ * Targets (and other no-bloat routeboxes) go all the way to touching.
+ * This is accomplished by backing off the probe edge when checking
+ * for touch against such an object. Usually the expanding edge
+ * bumps into neighboring pins on the same device that require a
+ * keepaway, preventing seeing a target immediately. Rather than await
+ * another expansion to actually touch the target, the edge breaker code
+ * looks past the keepaway to see these targets even though they
+ * weren't actually touched in the expansion.
*/
-routebox_t *
-FindBlocker (rtree_t * rtree, edge_t * e, BDimension maxbloat)
+struct E_result *
+Expand (rtree_t * rtree, edge_t * e, const BoxType * box)
{
- struct FindBlocker_info fbi;
- BoxType sbox;
+ static struct E_result ans;
+ int noshrink; /* bit field of which edges to not shrink */
- fbi.expansion_edge = e;
- fbi.maxbloat = maxbloat;
- fbi.blocker = NULL;
- fbi.min_dist = MAX_COORD;
- fbi.north_box = e->rb->box;
- fbi.not_via = !e->rb->flags.is_via;
+ ans.bloat = AutoRouteParameters.bloat;
+ ans.orig = *box;
+ ans.n = ans.e = ans.s = ans.w = NULL;
- sbox = bloat_box (&e->rb->box, maxbloat);
+ /* the inflated box must be bloated in all directions that it might
+ * hit something in order to guarantee that we see object in the
+ * tree it might hit. The tree holds objects bloated by their own
+ * keepaway so we are guaranteed to honor that.
+ */
switch (e->expand_dir)
{
+ case ALL:
+ ans.inflated.X1 = (e->rb->came_from == EAST ? ans.orig.X1 : 0);
+ ans.inflated.Y1 = (e->rb->came_from == SOUTH ? ans.orig.Y1 : 0);
+ ans.inflated.X2 =
+ (e->rb->came_from == WEST ? ans.orig.X2 : PCB->MaxWidth);
+ ans.inflated.Y2 =
+ (e->rb->came_from == NORTH ? ans.orig.Y2 : PCB->MaxHeight);
+ if (e->rb->came_from == NORTH)
+ ans.done = noshrink = _SOUTH;
+ else if (e->rb->came_from == EAST)
+ ans.done = noshrink = _WEST;
+ else if (e->rb->came_from == SOUTH)
+ ans.done = noshrink = _NORTH;
+ else if (e->rb->came_from == WEST)
+ ans.done = noshrink = _EAST;
+ else
+ ans.done = noshrink = 0;
+ break;
case NORTH:
- sbox.Y1 = -MAX_COORD;
+ ans.done = _SOUTH + _EAST + _WEST;
+ noshrink = _SOUTH;
+ ans.inflated.X1 = box->X1 - ans.bloat;
+ ans.inflated.X2 = box->X2 + ans.bloat;
+ ans.inflated.Y2 = box->Y2;
+ ans.inflated.Y1 = 0; /* far north */
+ break;
+ case NE:
+ ans.done = _SOUTH + _WEST;
+ noshrink = 0;
+ ans.inflated.X1 = box->X1 - ans.bloat;
+ ans.inflated.X2 = PCB->MaxWidth;
+ ans.inflated.Y2 = box->Y2 + ans.bloat;
+ ans.inflated.Y1 = 0;
break;
case EAST:
- sbox.X2 = MAX_COORD;
+ ans.done = _NORTH + _SOUTH + _WEST;
+ noshrink = _WEST;
+ ans.inflated.Y1 = box->Y1 - ans.bloat;
+ ans.inflated.Y2 = box->Y2 + ans.bloat;
+ ans.inflated.X1 = box->X1;
+ ans.inflated.X2 = PCB->MaxWidth;
+ break;
+ case SE:
+ ans.done = _NORTH + _WEST;
+ noshrink = 0;
+ ans.inflated.X1 = box->X1 - ans.bloat;
+ ans.inflated.X2 = PCB->MaxWidth;
+ ans.inflated.Y2 = PCB->MaxHeight;
+ ans.inflated.Y1 = box->Y1 - ans.bloat;
break;
case SOUTH:
- sbox.Y2 = MAX_COORD;
+ ans.done = _NORTH + _EAST + _WEST;
+ noshrink = _NORTH;
+ ans.inflated.X1 = box->X1 - ans.bloat;
+ ans.inflated.X2 = box->X2 + ans.bloat;
+ ans.inflated.Y1 = box->Y1;
+ ans.inflated.Y2 = PCB->MaxHeight;
+ break;
+ case SW:
+ ans.done = _NORTH + _EAST;
+ noshrink = 0;
+ ans.inflated.X1 = 0;
+ ans.inflated.X2 = box->X2 + ans.bloat;
+ ans.inflated.Y2 = PCB->MaxHeight;
+ ans.inflated.Y1 = box->Y1 - ans.bloat;
break;
case WEST:
- sbox.X1 = -MAX_COORD;
+ ans.done = _NORTH + _SOUTH + _EAST;
+ noshrink = _EAST;
+ ans.inflated.Y1 = box->Y1 - ans.bloat;
+ ans.inflated.Y2 = box->Y2 + ans.bloat;
+ ans.inflated.X1 = 0;
+ ans.inflated.X2 = box->X2;
+ break;
+ case NW:
+ ans.done = _SOUTH + _EAST;
+ noshrink = 0;
+ ans.inflated.X1 = 0;
+ ans.inflated.X2 = box->X2 + ans.bloat;
+ ans.inflated.Y2 = box->Y2 + ans.bloat;
+ ans.inflated.Y1 = 0;
break;
default:
+ noshrink = ans.done = 0;
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;
+ ans.keep = e->rb->style->Keepaway;
+ ans.parent = nonhomeless_parent (e->rb);
+ r_search (rtree, &ans.inflated, NULL, __Expand_this_rect, &ans);
+/* because the overlaping boxes are found in random order, some blockers
+ * may have limited edges prematurely, so we check if the blockers realy
+ * are blocking, and make another try if not
+ */
+ if (ans.n && !boink_box (ans.n, &ans, NORTH))
+ ans.inflated.Y1 = 0;
+ else
+ ans.done |= _NORTH;
+ if (ans.e && !boink_box (ans.e, &ans, EAST))
+ ans.inflated.X2 = PCB->MaxWidth;
+ else
+ ans.done |= _EAST;
+ if (ans.s && !boink_box (ans.s, &ans, SOUTH))
+ ans.inflated.Y2 = PCB->MaxHeight;
+ else
+ ans.done |= _SOUTH;
+ if (ans.w && !boink_box (ans.w, &ans, WEST))
+ ans.inflated.X1 = 0;
+ else
+ ans.done |= _WEST;
+ if (ans.done != _NORTH + _EAST + _SOUTH + _WEST)
+ {
+ r_search (rtree, &ans.inflated, NULL, __Expand_this_rect, &ans);
+ }
+ if ((noshrink & _NORTH) == 0)
+ ans.inflated.Y1 += ans.bloat;
+ if ((noshrink & _EAST) == 0)
+ ans.inflated.X2 -= ans.bloat;
+ if ((noshrink & _SOUTH) == 0)
+ ans.inflated.Y2 -= ans.bloat;
+ if ((noshrink & _WEST) == 0)
+ ans.inflated.X1 += ans.bloat;
+ return &ans;
}
-/* ------------ */
+/* blocker_to_heap puts the blockers into a heap so they
+ * can be retrieved in clockwise order. If a blocker
+ * is also a target, it gets put into the vector too.
+ * It returns 1 for any fixed blocker that is not part
+ * of this net and zero otherwise.
+ */
+static int
+blocker_to_heap (heap_t * heap, routebox_t * rb,
+ BoxType * box, direction_t dir)
+{
+ BoxType b = rb->sbox;
+ if (rb->style->Keepaway > AutoRouteParameters.style->Keepaway)
+ b =
+ bloat_box (&b,
+ rb->style->Keepaway - AutoRouteParameters.style->Keepaway);
+ b = clip_box (&b, box);
+ assert (box_is_good (&b));
+ /* we want to look at the blockers clockwise around the box */
+ switch (dir)
+ {
+ /* we need to use the other coordinate fraction to resolve
+ * ties since we want the shorter of the furthest
+ * first.
+ */
+ case NORTH:
+ heap_insert (heap, b.X1 - b.X1 / (b.X2 + 1.0), rb);
+ break;
+ case EAST:
+ heap_insert (heap, b.Y1 - b.Y1 / (b.Y2 + 1.0), rb);
+ break;
+ case SOUTH:
+ heap_insert (heap, -(b.X2 + b.X1 / (b.X2 + 1.0)), rb);
+ break;
+ case WEST:
+ heap_insert (heap, -(b.Y2 + b.Y1 / (b.Y2 + 1.0)), rb);
+ break;
+ default:
+ assert (0);
+ }
+ if (rb->flags.fixed && !rb->flags.target && !rb->flags.source)
+ return 1;
+ return 0;
+}
-struct fio_info
+/* this creates an EXPANSION_AREA to bridge small gaps or,
+ * (more commonly) create a supper-thin box to provide a
+ * home for an expansion edge.
+ */
+static routebox_t *
+CreateBridge (const BoxType * area, routebox_t * parent, direction_t dir)
{
- edge_t *edge;
- routebox_t *intersect;
- jmp_buf env;
- BoxType north_box;
+ routebox_t *rb = (routebox_t *) malloc (sizeof (*rb));
+ memset ((void *) rb, 0, sizeof (*rb));
+ assert (area && parent);
+ init_const_box (rb, area->X1, area->Y1, area->X2, area->Y2, 0);
+ rb->group = parent->group;
+ rb->type = EXPANSION_AREA;
+ rb->came_from = dir;
+ rb->cost_point = closest_point_in_box (&parent->cost_point, area);
+ rb->cost = parent->cost + cost_to_point_on_layer (&parent->cost_point,
+ &rb->cost_point,
+ rb->group);
+ rb->parent.expansion_area = route_parent (parent);
+ rb->flags.homeless = 1;
+ rb->flags.nobloat = 1;
+ rb->style = parent->style;
+ rb->conflicts_with = parent->conflicts_with;
+#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EDGES)
+ showroutebox (rb);
+#endif
+ return rb;
+}
+
+/* moveable_edge prepares the new search edges based on the
+ * starting box, direction and blocker if any.
+ */
+void
+moveable_edge (vector_t * result, const BoxType * box, direction_t dir,
+ routebox_t * rb,
+ routebox_t * blocker, edge_t * e, rtree_t * targets,
+ struct routeone_state *s, rtree_t * tree, vector_t * area_vec)
+{
+ BoxType b;
+ assert (box_is_good (box));
+ b = *box;
+ /* for the cardinal directions, move the box to overlap the
+ * the parent by 1 unit. Corner expansions overlap more
+ * and their starting boxes are pre-prepared.
+ * Check if anything is headed off the board edges
+ */
+ switch (dir)
+ {
+ default:
+ break;
+ case NORTH:
+ b.Y2 = b.Y1;
+ b.Y1--;
+ if (b.Y1 <= AutoRouteParameters.bloat)
+ return; /* off board edge */
+ break;
+ case EAST:
+ b.X1 = b.X2;
+ b.X2++;
+ if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat)
+ return; /* off board edge */
+ break;
+ case SOUTH:
+ b.Y1 = b.Y2;
+ b.Y2++;
+ if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat)
+ return; /* off board edge */
+ break;
+ case WEST:
+ b.X2 = b.X1;
+ b.X1--;
+ if (b.X1 <= AutoRouteParameters.bloat)
+ return; /* off board edge */
+ break;
+ case NE:
+ if (b.Y1 <= AutoRouteParameters.bloat + 1
+ && b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
+ return; /* off board edge */
+ if (b.Y1 <= AutoRouteParameters.bloat + 1)
+ dir = EAST; /* north off board edge */
+ if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
+ dir = NORTH; /* east off board edge */
+ break;
+ case SE:
+ if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1
+ && b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
+ return; /* off board edge */
+ if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1)
+ dir = EAST; /* south off board edge */
+ if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
+ dir = SOUTH; /* east off board edge */
+ break;
+ case SW:
+ if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1
+ && b.X1 <= AutoRouteParameters.bloat + 1)
+ return; /* off board edge */
+ if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1)
+ dir = WEST; /* south off board edge */
+ if (b.X1 <= AutoRouteParameters.bloat + 1)
+ dir = SOUTH; /* west off board edge */
+ break;
+ case NW:
+ if (b.Y1 <= AutoRouteParameters.bloat + 1
+ && b.X1 <= AutoRouteParameters.bloat + 1)
+ return; /* off board edge */
+ if (b.Y1 <= AutoRouteParameters.bloat + 1)
+ dir = WEST; /* north off board edge */
+ if (b.X1 <= AutoRouteParameters.bloat + 1)
+ dir = NORTH; /* west off board edge */
+ break;
+ }
+
+ if (!blocker)
+ {
+ edge_t *ne;
+ routebox_t *nrb = CreateBridge (&b, rb, dir);
+ /* move the cost point in corner expansions
+ * these boxes are bigger, so move close to the target
+ */
+ if (dir == NE || dir == SE || dir == SW || dir == NW)
+ {
+ CheapPointType p;
+ p =
+ closest_point_in_box (&nrb->cost_point, &e->mincost_target->sbox);
+ p = closest_point_in_box (&p, &b);
+ nrb->cost += cost_to_point_on_layer (&p, &nrb->cost_point,
+ nrb->group);
+ nrb->cost_point = p;
+ }
+ ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y,
+ nrb->cost, NULL, dir, targets);
+ vector_append (result, ne);
+ }
+ else if (AutoRouteParameters.with_conflicts && !blocker->flags.target
+ && !blocker->flags.fixed && !blocker->flags.touched &&
+ !blocker->flags.source && blocker->type != EXPANSION_AREA)
+ {
+ edge_t *ne;
+ routebox_t *nrb;
+ /* make a bridge to the edge of the blocker
+ * in all directions from there
+ */
+ switch (dir)
+ {
+ case NORTH:
+ b.Y1 = blocker->sbox.Y2 - 1;
+ break;
+ case EAST:
+ b.X2 = blocker->sbox.X1 + 1;
+ break;
+ case SOUTH:
+ b.Y2 = blocker->sbox.Y1 + 1;
+ break;
+ case WEST:
+ b.X1 = blocker->sbox.X2 - 1;
+ break;
+ default:
+ assert (0);
+ }
+ if (!box_is_good (&b))
+ return; /* how did this happen ? */
+ nrb = CreateBridge (&b, rb, dir);
+ r_insert_entry (tree, &nrb->box, 1);
+ vector_append (area_vec, nrb);
+ nrb->flags.homeless = 0; /* not homeless any more */
+ /* mark this one as conflicted */
+ path_conflicts (nrb, blocker, True);
+ /* and make an expansion edge */
+ nrb->cost_point =
+ closest_point_in_box (&nrb->cost_point, &blocker->sbox);
+ nrb->cost +=
+ cost_to_point_on_layer (&nrb->parent.expansion_area->cost_point,
+ &nrb->cost_point,
+ nrb->group) * CONFLICT_PENALTY (blocker);
+
+ ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y, nrb->cost,
+ NULL, ALL, targets);
+ ne->flags.is_interior = 1;
+ vector_append (result, ne);
+ }
+#if 1
+ else if (blocker->type == EXPANSION_AREA)
+ {
+ if (blocker->cost < rb->cost || blocker->cost <= rb->cost +
+ cost_to_point_on_layer (&blocker->cost_point, &rb->cost_point,
+ rb->group))
+ return;
+ if (blocker->conflicts_with || rb->conflicts_with)
+ return;
+ /* does the blocker overlap this routebox ?? */
+ /* does this re-parenting operation leave a memory leak? */
+ if (blocker->parent.expansion_area->flags.homeless)
+ RB_down_count (blocker->parent.expansion_area);
+ blocker->parent.expansion_area = rb;
+ return;
+ }
+#endif
+ else if (blocker->flags.target)
+ {
+ routebox_t *nrb;
+ edge_t *ne;
+ b = bloat_box (&b, 1);
+ if (!box_intersect (&b, &blocker->sbox))
+ {
+ /* if the expansion edge stopped before touching, expand the bridge */
+ switch (dir)
+ {
+ case NORTH:
+ b.Y1 -= AutoRouteParameters.bloat + 1;
+ break;
+ case EAST:
+ b.X2 += AutoRouteParameters.bloat + 1;
+ break;
+ case SOUTH:
+ b.Y2 += AutoRouteParameters.bloat + 1;
+ break;
+ case WEST:
+ b.X1 -= AutoRouteParameters.bloat + 1;
+ break;
+ default:
+ assert (0);
+ }
+ }
+ assert (box_intersect (&b, &blocker->sbox));
+ b = shrink_box (&b, 1);
+ nrb = CreateBridge (&b, rb, dir);
+ r_insert_entry (tree, &nrb->box, 1);
+ vector_append (area_vec, nrb);
+ nrb->flags.homeless = 0; /* not homeless any more */
+ ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y,
+ nrb->cost, blocker, dir, NULL);
+ best_path_candidate (s, ne, blocker);
+ DestroyEdge (&ne);
+ }
+}
+
+struct break_info
+{
+ heap_t *heap;
+ routebox_t *parent;
+ BoxType box;
+ direction_t dir;
+ Boolean ignore_source;
};
static int
-fio_rect_in_reg (const BoxType * box, void *cl)
+__GatherBlockers (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)
+ routebox_t *rb = (routebox_t *) box;
+ struct break_info *bi = (struct break_info *) cl;
+ BoxType b;
+
+ if (bi->parent == rb || rb->flags.touched ||
+ bi->parent->parent.expansion_area == rb)
+ return 0;
+ if (rb->flags.source && bi->ignore_source)
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))
+ b = rb->sbox;
+ if (rb->style->Keepaway > AutoRouteParameters.style->Keepaway)
+ b =
+ bloat_box (&b,
+ rb->style->Keepaway - AutoRouteParameters.style->Keepaway);
+ if (b.X2 <= bi->box.X1 || b.X1 >= bi->box.X2
+ || b.Y1 >= bi->box.Y2 || b.Y2 <= bi->box.Y1)
return 0;
- /* okay, this is an intersector! */
- fio->intersect = rb;
- longjmp (fio->env, 1); /* skip to the end! */
- return 1; /* never reached */
+ return blocker_to_heap (bi->heap, rb, &bi->box, bi->dir);
}
-static routebox_t *
-FindIntersectingObstacle (rtree_t * rtree, edge_t * e, BDimension maxbloat)
+/* shrink the box to the last limit for the previous direction,
+ * i.e. if dir is SOUTH, then this means fixing up an EAST leftover
+ * edge, which would be the southern most edge for that example.
+ */
+static inline BoxType
+previous_edge (LocationType last, direction_t i, const BoxType * b)
{
- 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)
+ BoxType db = *b;
+ switch (i)
{
- case NORTH:
+ case EAST:
+ db.X1 = last;
+ break;
case SOUTH:
- sbox.X1 += 1;
- sbox.X2 -= 1;
+ db.Y1 = last;
break;
- case EAST:
case WEST:
- sbox.Y1 += 1;
- sbox.Y2 -= 1;
+ db.X2 = last;
break;
default:
+ Message ("previous edge bogus direction!");
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;
+ return db;
+}
+
+/* Break all the edges of the box that need breaking, handling
+ * targets as they are found, and putting any moveable edges
+ * in the return vector.
+ */
+vector_t *
+BreakManyEdges (struct routeone_state * s, rtree_t * targets, rtree_t * tree,
+ vector_t * area_vec, struct E_result * ans, routebox_t * rb,
+ edge_t * e)
+{
+ struct break_info bi;
+ vector_t *edges;
+ heap_t *heap[4];
+ LocationType first, last;
+ BDimension bloat;
+ direction_t dir;
+ routebox_t fake;
+
+ edges = vector_create ();
+ bi.ignore_source = rb->parent.expansion_area->flags.source;
+ bi.parent = rb;
+ /* we add 2 to the bloat.
+ * 1 will get us to the actual blocker that Expand() hit
+ * but 1 more is needed because the new expansion edges
+ * move out by 1 so they don't overlap their parents
+ * this extra expansion could "trap" the edge if
+ * there is a blocker 2 units from the original rb,
+ * it is 1 unit from the new expansion edge which
+ * would prevent expansion. So we want to break the
+ * edge on it now to avoid the trap.
+ */
+
+ bloat = AutoRouteParameters.bloat + 2;
+ /* for corner expansion, we need to have a fake blocker
+ * to prevent expansion back where we came from since
+ * we still need to break portions of all 4 edges
+ */
+ if (e->expand_dir == NE || e->expand_dir == SE ||
+ e->expand_dir == SW || e->expand_dir == NW)
+ {
+ BoxType *fb = (BoxType *) & fake.sbox;
+ memset (&fake, 0, sizeof (fake));
+ *fb = e->rb->sbox;
+ fake.flags.fixed = 1; /* this stops expansion there */
+ fake.type = LINE;
+ fake.style = AutoRouteParameters.style;
+#ifndef NDEBUG
+ /* the routbox_is_good checker wants a lot more! */
+ fake.flags.inited = 1;
+ fb = (BoxType *) & fake.box;
+ *fb = e->rb->sbox;
+ fake.same_net.next = fake.same_net.prev = &fake;
+ fake.same_subnet.next = fake.same_subnet.prev = &fake;
+ fake.original_subnet.next = fake.original_subnet.prev = &fake;
+ fake.different_net.next = fake.different_net.prev = &fake;
+#endif
+ }
+ /* gather all of the blockers in heaps so they can be accessed
+ * in clockwise order, which allows finding corners that can
+ * be expanded.
+ */
+ for (dir = NORTH; dir <= WEST; dir++)
+ {
+ /* don't break the edge we came from */
+ if (e->expand_dir != ((dir + 2) % 4))
+ {
+ heap[dir] = heap_create ();
+ bi.box = bloat_box (&rb->sbox, bloat);
+ bi.heap = heap[dir];
+ bi.dir = dir;
+ /* convert to edge */
+ switch (dir)
+ {
+ case NORTH:
+ bi.box.Y2 = bi.box.Y1 + bloat + 1;
+ /* for corner expansion, block the start edges and
+ * limit the blocker search to only the new edge segment
+ */
+ if (e->expand_dir == SE || e->expand_dir == SW)
+ blocker_to_heap (heap[dir], &fake, &bi.box, dir);
+ if (e->expand_dir == SE)
+ bi.box.X1 = e->rb->sbox.X2;
+ if (e->expand_dir == SW)
+ bi.box.X2 = e->rb->sbox.X1;
+ rb->n = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
+ break;
+ case EAST:
+ bi.box.X1 = bi.box.X2 - bloat - 1;
+ /* corner, same as above */
+ if (e->expand_dir == SW || e->expand_dir == NW)
+ blocker_to_heap (heap[dir], &fake, &bi.box, dir);
+ if (e->expand_dir == SW)
+ bi.box.Y1 = e->rb->sbox.Y2;
+ if (e->expand_dir == NW)
+ bi.box.Y2 = e->rb->sbox.Y1;
+ rb->e = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
+ break;
+ case SOUTH:
+ bi.box.Y1 = bi.box.Y2 - bloat - 1;
+ /* corner, same as above */
+ if (e->expand_dir == NE || e->expand_dir == NW)
+ blocker_to_heap (heap[dir], &fake, &bi.box, dir);
+ if (e->expand_dir == NE)
+ bi.box.X1 = e->rb->sbox.X2;
+ if (e->expand_dir == NW)
+ bi.box.X2 = e->rb->sbox.X1;
+ rb->s = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
+ break;
+ case WEST:
+ bi.box.X2 = bi.box.X1 + bloat + 1;
+ /* corner, same as above */
+ if (e->expand_dir == NE || e->expand_dir == SE)
+ blocker_to_heap (heap[dir], &fake, &bi.box, dir);
+ if (e->expand_dir == SE)
+ bi.box.Y1 = e->rb->sbox.Y2;
+ if (e->expand_dir == NE)
+ bi.box.Y2 = e->rb->sbox.Y1;
+ rb->w = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
+ break;
+ default:
+ assert (0);
+ }
+ }
+ else
+ heap[dir] = NULL;
+ }
+#if 1
+ rb->cost +=
+ (rb->n + rb->e + rb->s +
+ rb->w) * AutoRouteParameters.CongestionPenalty / box_area (rb->sbox);
+#endif
+/* now handle the blockers:
+ * Go around the expansion area clockwise (North->East->South->West)
+ * pulling blockers from the heap (which makes them come out in the right
+ * order). Break the edges on the blocker and make the segments and corners
+ * moveable as possible.
+ */
+ first = last = -1;
+ for (dir = NORTH; dir <= WEST; dir++)
+ {
+ if (heap[dir] && !heap_is_empty (heap[dir]))
+ {
+ /* pull the very first one out of the heap outside of the
+ * heap loop because it is special; it can be part of a corner
+ */
+ routebox_t *blk = (routebox_t *) heap_remove_smallest (heap[dir]);
+ BoxType b = rb->sbox;
+ struct broken_boxes broke = break_box_edge (&b, dir, blk);
+ if (broke.is_valid_left)
+ {
+ /* if last > 0, then the previous edge had a segment
+ * joining this one, so it forms a valid corner expansion
+ */
+ if (last > 0)
+ {
+ /* make a corner expansion */
+ BoxType db = b;
+ switch (dir)
+ {
+ case EAST:
+ /* possible NE expansion */
+ db.X1 = last;
+ db.Y2 = MIN (db.Y2, broke.left.Y2);
+ break;
+ case SOUTH:
+ /* possible SE expansion */
+ db.Y1 = last;
+ db.X1 = MAX (db.X1, broke.left.X1);
+ break;
+ case WEST:
+ /* possible SW expansion */
+ db.X2 = last;
+ db.Y1 = MAX (db.Y1, broke.left.Y1);
+ break;
+ default:
+ assert (0);
+ break;
+ }
+ moveable_edge (edges, &db, dir + 3, rb, NULL, e, targets,
+ s, NULL, NULL);
+ }
+ else if (dir == NORTH) /* north is start, so nothing "before" it */
+ {
+ /* save for a possible corner once we've
+ * finished circling the box
+ */
+ first = MAX (b.X1, broke.left.X2);
+ }
+ else
+ {
+ /* this is just a boring straight expansion
+ * since the orthogonal segment was blocked
+ */
+ moveable_edge (edges, &broke.left, dir, rb, NULL, e,
+ targets, s, NULL, NULL);
+ }
+ } /* broke.is_valid_left */
+ else if (last > 0)
+ {
+ /* if the last one didn't become a corner,
+ * we still want to expand it straight out
+ * in the direction of the previous edge,
+ * which it belongs to.
+ */
+ BoxType db = previous_edge (last, dir, &rb->sbox);
+ moveable_edge (edges, &db, dir - 1, rb, NULL, e, targets, s,
+ NULL, NULL);
+ }
+ if (broke.is_valid_center && !blk->flags.source)
+ moveable_edge (edges, &broke.center, dir, rb, blk, e, targets, s,
+ tree, area_vec);
+ /* this is the heap extraction loop. We break out
+ * if there's nothing left in the heap, but if we * are blocked all the way to the far edge, we can
+ * just leave stuff in the heap when it is destroyed
+ */
+ while (broke.is_valid_right)
+ {
+ /* move the box edge to the next potential free point */
+ switch (dir)
+ {
+ case NORTH:
+ last = b.X1 = MAX (broke.right.X1, b.X1);
+ break;
+ case EAST:
+ last = b.Y1 = MAX (broke.right.Y1, b.Y1);
+ break;
+ case SOUTH:
+ last = b.X2 = MIN (broke.right.X2, b.X2);
+ break;
+ case WEST:
+ last = b.Y2 = MIN (broke.right.Y2, b.Y2);
+ break;
+ default:
+ assert (0);
+ }
+ if (heap_is_empty (heap[dir]))
+ break;
+ blk = heap_remove_smallest (heap[dir]);
+ broke = break_box_edge (&b, dir, blk);
+ if (broke.is_valid_left)
+ moveable_edge (edges, &broke.left, dir, rb, NULL, e, targets,
+ s, NULL, NULL);
+ if (broke.is_valid_center && !blk->flags.source)
+ moveable_edge (edges, &broke.center, dir, rb, blk, e, targets,
+ s, tree, area_vec);
+ }
+ if (!broke.is_valid_right)
+ last = -1;
+ }
+ else /* if (heap[dir]) */
+ {
+ /* nothing touched this edge! Expand the whole edge unless
+ * (1) it hit the board edge or (2) was the source of our expansion
+ *
+ * for this case (of hitting nothing) we give up trying for corner
+ * expansions because it is likely that they're not possible anyway
+ */
+ if ((e->expand_dir == ALL ? e->rb->came_from : e->expand_dir) !=
+ ((dir + 2) % 4))
+ {
+ /* ok, we are not going back on ourselves, and the whole edge seems free */
+ moveable_edge (edges, &rb->sbox, dir, rb, NULL, e, targets, s,
+ NULL, NULL);
+ }
+
+ if (last > 0)
+ {
+ /* expand the leftover from the prior direction */
+ BoxType db = previous_edge (last, dir, &rb->sbox);
+ moveable_edge (edges, &db, dir - 1, rb, NULL, e, targets, s,
+ NULL, NULL);
+ }
+ last = -1;
+ }
+ } /* for loop */
+ /* finally, check for the NW corner now that we've come full circle */
+ if (first > 0 && last > 0)
+ {
+ BoxType db = rb->sbox;
+ db.X2 = first;
+ db.Y2 = last;
+ moveable_edge (edges, &db, NW, rb, NULL, e, targets, s, NULL, NULL);
+ }
+ else
+ {
+ if (first > 0)
+ {
+ BoxType db = rb->sbox;
+ db.X2 = first;
+ moveable_edge (edges, &db, NORTH, rb, NULL, e, targets, s, NULL,
+ NULL);
+ }
+ else if (last > 0)
+ {
+ BoxType db = rb->sbox;
+ db.Y2 = last;
+ moveable_edge (edges, &db, WEST, rb, NULL, e, targets, s, NULL,
+ NULL);
+ }
+ }
+ /* done with all expansion edges of this box */
+ for (dir = NORTH; dir <= WEST; dir++)
+ {
+ if (heap[dir])
+ heap_destroy (&heap[dir]);
+ }
+ return edges;
+}
+
+static routebox_t *
+rb_source (routebox_t * rb)
+{
+ while (rb && !rb->flags.source)
+ {
+ assert (rb->type == EXPANSION_AREA);
+ rb = rb->parent.expansion_area;
+ }
+ assert (rb);
+ return rb;
}
/* ------------ */
@@ -2174,285 +3037,117 @@ FindIntersectingObstacle (rtree_t * rtree, edge_t * e, BDimension maxbloat)
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)
+foib_rect_in_reg (const BoxType * box, void *cl)
{
+ struct foib_info *foib = (struct foib_info *) cl;
BoxType rbox;
- rbox = is_region ? bloat_box (region_or_box, foib->maxbloat) :
- bloat_routebox ((routebox_t *) region_or_box);
+ routebox_t *rb = (routebox_t *) box;
+ if (rb->flags.touched)
+ return 0;
+// if (rb->type == EXPANSION_AREA && !rb->flags.is_via)
+ // return 0;
+ rbox = bloat_routebox (rb);
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! */
- }
+ /* this is an intersector! */
+ foib->intersect = (routebox_t *) 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)
+FindOneInBox (rtree_t * rtree, routebox_t * rb)
{
struct foib_info foib;
+ BoxType r;
- foib.box = box;
- foib.maxbloat = maxbloat;
+ r = rb->sbox;
+ foib.box = &r;
foib.intersect = NULL;
if (setjmp (foib.env) == 0)
- r_search (rtree, NULL, foib_reg_in_sea, foib_rect_in_reg, &foib);
+ r_search (rtree, &r, NULL, foib_rect_in_reg, &foib);
return foib.intersect;
}
+struct therm_info
+{
+ routebox_t *plane;
+ BoxType query;
+ jmp_buf env;
+};
static int
ftherm_rect_in_reg (const BoxType * box, void *cl)
{
routebox_t *rbox = (routebox_t *) box;
- struct rb_info *ti = (struct rb_info *) cl;
+ struct therm_info *ti = (struct therm_info *) cl;
+ BoxType sq, sb;
- if (rbox->type == PIN || rbox->type == VIA || rbox->type == VIA_SHADOW)
+ if (rbox->type != PIN && rbox->type != VIA && rbox->type != VIA_SHADOW)
+ return 0;
+ if (rbox->group != ti->plane->group)
+ return 0;
+
+ sb = shrink_routebox (rbox);
+ switch (rbox->type)
{
- ti->winner = rbox;
- longjmp (ti->env, 1);
+ case PIN:
+ sq = shrink_box (&ti->query, rbox->parent.pin->Thickness);
+ if (!box_intersect (&sb, &sq))
+ return 0;
+ sb.X1 = rbox->parent.pin->X;
+ sb.Y1 = rbox->parent.pin->Y;
+ break;
+ case VIA:
+ if (rbox->flags.fixed)
+ {
+ sq = shrink_box (&ti->query, rbox->parent.via->Thickness);
+ sb.X1 = rbox->parent.pin->X;
+ sb.Y1 = rbox->parent.pin->Y;
+ }
+ else
+ {
+ sq = shrink_box (&ti->query, rbox->style->Diameter);
+ sb.X1 = CENTER_X (sb);
+ sb.Y1 = CENTER_Y (sb);
+ }
+ if (!box_intersect (&sb, &sq))
+ return 0;
+ break;
+ case VIA_SHADOW:
+ sq = shrink_box (&ti->query, rbox->style->Diameter);
+ if (!box_intersect (&sb, &sq))
+ return 0;
+ sb.X1 = CENTER_X (sb);
+ sb.Y1 = CENTER_Y (sb);
+ break;
+ default:
+ assert (0);
}
- return 0;
+ ti->plane = rbox;
+ longjmp (ti->env, 1);
+ return 1;
}
/* 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)
+routebox_t *
+FindThermable (rtree_t * rtree, routebox_t * rb)
{
- struct rb_info info;
+ 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;
-}
+ info.plane = rb;
+ info.query = shrink_routebox (rb);
-/* 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:
- costpoint.X = 0;
- costpoint.Y = 0;
- 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))
+ if (setjmp (info.env) == 0)
{
- 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)
- {
- /* an expansion area is not really an obstacle */
- if (rb->type == EXPANSION_AREA)
- {
- routebox_t *nrb = CreateExpansionArea (&r.center,
- e->rb->group, parent,
- False, e);
- ne = CreateEdge2 (nrb, e->expand_dir, e, targets, NULL);
- nrb->flags.nobloat = e->rb->flags.nobloat;
- ne->cost_to_point =
- e->cost_to_point +
- (e->rb->flags.
- source ? 0 : (CONFLICT_PENALTY (nonorphan_parent (e->rb))
- * (ne->cost_to_point - e->cost_to_point)));
- assert (__edge_is_good (ne));
- vector_append (broken_vec, ne);
- }
- else if (!rb->flags.source && (!rb->flags.fixed
- || rb->flags.target)
- && 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);
- }
- /* we still want to hit targets if routing without conflicts
- * since a target is not really a conflict
- */
- else if (rb->flags.target) /* good news */
- {
- routebox_t *nrb = CreateExpansionArea (&r.center,
- e->rb->group, parent,
- False, e);
- ne = CreateEdge2 (nrb, e->expand_dir, e, NULL, rb);
- nrb->flags.nobloat = e->rb->flags.nobloat;
- ne->cost_to_point =
- e->cost_to_point +
- e->rb->flags.
- source ? 0 : (CONFLICT_PENALTY (nonorphan_parent (e->rb))
- * (ne->cost_to_point - e->cost_to_point));
- assert (__edge_is_good (ne));
- vector_append (broken_vec, ne);
- }
- }
- DestroyEdge (&e);
- }
- /* done with this edge */
+ r_search (rtree, &info.query, NULL, ftherm_rect_in_reg, &info);
+ return NULL;
}
- /* 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;
+ return info.plane;
}
/*--------------------------------------------------------------------
@@ -2461,60 +3156,69 @@ BreakEdges (routedata_t * rd, vector_t * edge_vec, rtree_t * targets)
*/
static void
RD_DrawThermal (routedata_t * rd, LocationType X, LocationType Y,
- Cardinal group, Cardinal layer, routebox_t * subnet,
- Boolean is_bad)
+ 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);
+ memset ((void *) rb, 0, sizeof (*rb));
+ init_const_box (rb, X, Y, X + 1, Y + 1, 0);
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;
+ rb->style = AutoRouteParameters.style;
+ rb->type = THERMAL;
InitLists (rb);
MergeNets (rb, subnet, NET);
MergeNets (rb, subnet, SUBNET);
+ /* add it to the r-tree, this may be the whole route! */
+ r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
+ rb->flags.homeless = 0;
}
static void
RD_DrawVia (routedata_t * rd, LocationType X, LocationType Y,
- BDimension radius, routebox_t * subnet, Boolean is_bad)
+ BDimension radius, routebox_t * subnet, Boolean is_bad)
{
routebox_t *rb, *first_via = NULL;
int i;
+ int ka = AutoRouteParameters.style->Keepaway;
+
/* a via cuts through every layer group */
for (i = 0; i < max_layer; i++)
{
if (!is_layer_group_active[i])
- continue;
+ continue;
rb = (routebox_t *) malloc (sizeof (*rb));
+ memset ((void *) rb, 0, sizeof (*rb));
init_const_box (rb,
- /*X1 */ X - radius, /*Y1 */ Y - radius,
- /*X2 */ X + radius, /*Y2 */ Y + radius);
+ /*X1 */ X - radius, /*Y1 */ Y - radius,
+ /*X2 */ X + radius + 1, /*Y2 */ Y + radius + 1, ka);
rb->group = i;
- rb->flags.fixed = 0; /* 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->came_from = ALL;
rb->flags.circular = True;
- rb->augStyle = AutoRouteParameters.augStyle;
+ rb->style = AutoRouteParameters.style;
+ rb->pass = AutoRouteParameters.pass;
if (first_via == NULL)
- {
- rb->type = VIA;
- rb->parent.via = NULL; /* indicates that not on PCB yet */
- first_via = rb;
- /* only add the first via to mtspace, not the shadows too */
- mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN,
- rb->augStyle->style->Keepaway);
- }
+ {
+ rb->type = VIA;
+ rb->parent.via = NULL; /* indicates that not on PCB yet */
+ first_via = rb;
+ /* only add the first via to mtspace, not the shadows too */
+ mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN,
+ rb->style->Keepaway);
+ }
else
- {
- rb->type = VIA_SHADOW;
- rb->parent.via_shadow = first_via;
- }
+ {
+ rb->type = VIA_SHADOW;
+ rb->parent.via_shadow = first_via;
+ }
InitLists (rb);
/* add these to proper subnet. */
MergeNets (rb, subnet, NET);
@@ -2522,45 +3226,96 @@ RD_DrawVia (routedata_t * rd, LocationType X, LocationType Y,
assert (__routebox_is_good (rb));
/* and add it to the r-tree! */
r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
+ rb->flags.homeless = 0; /* not homeless anymore */
if (TEST_FLAG (LIVEROUTEFLAG, PCB))
- {
+ {
gui->set_color (ar_gc, PCB->ViaColor);
gui->fill_circle (ar_gc, X, Y, radius);
- }
+ }
}
}
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)
+ LocationType X1, LocationType Y1, LocationType X2,
+ LocationType Y2, BDimension halfthick, Cardinal group,
+ routebox_t * subnet, Boolean is_bad, Boolean is_45)
{
+ /* we hold the line in a queue to concatenate segments that
+ * ajoin one another. That reduces the number of things in
+ * the trees and allows conflict boxes to be larger, both of
+ * which are really useful.
+ */
+ static LocationType qX1 = -1, qY1, qX2, qY2;
+ static BDimension qhthick;
+ static Cardinal qgroup;
+ static Boolean qis_45, qis_bad;
+ static routebox_t *qsn;
+
routebox_t *rb;
+ int ka = AutoRouteParameters.style->Keepaway;
+
/* don't draw zero-length segments. */
if (X1 == X2 && Y1 == Y2)
return;
+ if (qX1 == -1) /* first ever */
+ {
+ qX1 = X1;
+ qY1 = Y1;
+ qX2 = X2;
+ qY2 = Y2;
+ qhthick = halfthick;
+ qgroup = group;
+ qis_45 = is_45;
+ qis_bad = is_bad;
+ qsn = subnet;
+ return;
+ }
+ /* Check if the lines concatenat. We only check the
+ * normal expected nextpoint=lastpoint condition
+ */
+ if (X1 == qX2 && Y1 == qY2 && qhthick == halfthick && qgroup == group)
+ {
+ if (qX1 == qX2 && X1 == X2) /* everybody on the same X here */
+ {
+ qY2 = Y2;
+ return;
+ }
+ if (qY1 == qY2 && Y1 == Y2) /* same Y all around */
+ {
+ qX2 = X2;
+ return;
+ }
+ }
+ /* dump the queue, no match here */
+ if (qX1 == -1)
+ return; /* but not this! */
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 */ );
+ memset ((void *) rb, 0, sizeof (*rb));
+ assert (is_45 ? (ABS (qX2 - qX1) == ABS (qY2 - qY1)) /* line must be 45-degrees */
+ : (qX1 == qX2 || qY1 == qY2) /* 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;
+ /*X1 */ MIN (qX1, qX2) - qhthick,
+ /*Y1 */ MIN (qY1, qY2) - qhthick,
+ /*X2 */ MAX (qX1, qX2) + qhthick + 1,
+ /*Y2 */ MAX (qY1, qY2) + qhthick + 1, ka);
+ rb->group = qgroup;
rb->type = LINE;
- rb->parent.line = NULL; /* indicates that not on PCB yet */
- rb->flags.fixed = 0; /* indicates that not on PCB yet */
+ 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;
+ rb->flags.is_bad = qis_bad;
+ rb->came_from = ALL;
+ rb->flags.homeless = 0; /* we're putting this in the tree */
+ rb->flags.nonstraight = qis_45;
+ rb->flags.bl_to_ur = ((qX2 >= qX1 && qY2 <= qY1)
+ || (qX2 <= qX1 && qY2 >= qY1));
+ rb->style = AutoRouteParameters.style;
+ rb->pass = AutoRouteParameters.pass;
InitLists (rb);
/* add these to proper subnet. */
- MergeNets (rb, subnet, NET);
- MergeNets (rb, subnet, SUBNET);
+ MergeNets (rb, qsn, NET);
+ MergeNets (rb, qsn, SUBNET);
assert (__routebox_is_good (rb));
/* and add it to the r-tree! */
r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
@@ -2569,36 +3324,46 @@ RD_DrawLine (routedata_t * rd,
{
LayerTypePtr layp = LAYER_PTR (PCB->LayerGroups.Entries[rb->group][0]);
- gui->set_line_width (ar_gc, 2*halfthick);
+ gui->set_line_width (ar_gc, 2 * qhthick);
gui->set_color (ar_gc, layp->Color);
- gui->draw_line (ar_gc, X1, Y1, X2, Y2);
+ gui->draw_line (ar_gc, qX1, qY1, qX2, qY2);
}
/* 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);
+ rb->style->Keepaway);
usedGroup[rb->group] = True;
+ /* and queue this one */
+ qX1 = X1;
+ qY1 = Y1;
+ qX2 = X2;
+ qY2 = Y2;
+ qhthick = halfthick;
+ qgroup = group;
+ qis_45 = is_45;
+ qis_bad = is_bad;
+ qsn = subnet;
}
static Boolean
RD_DrawManhattanLine (routedata_t * rd,
- const BoxType * box1, const BoxType * box2,
- CheapPointType start, CheapPointType end,
- BDimension halfthick, Cardinal group,
- routebox_t * subnet, Boolean is_bad, Boolean last_was_x)
+ const BoxType * box1, const BoxType * box2,
+ CheapPointType start, CheapPointType end,
+ BDimension halfthick, Cardinal group,
+ routebox_t * subnet, Boolean is_bad, Boolean last_was_x)
{
CheapPointType knee = start;
if (end.X == start.X)
{
RD_DrawLine (rd, start.X, start.Y, end.X, end.Y, halfthick, group,
- subnet, is_bad, False);
+ subnet, is_bad, False);
return False;
}
else if (end.Y == start.Y)
{
RD_DrawLine (rd, start.X, start.Y, end.X, end.Y, halfthick, group,
- subnet, is_bad, False);
+ subnet, is_bad, False);
return True;
}
/* find where knee belongs */
@@ -2620,16 +3385,17 @@ RD_DrawManhattanLine (routedata_t * rd,
knee.X = start.X;
knee.Y = end.Y;
}
- assert (point_in_box (box1, knee.X, knee.Y)
- || point_in_box (box2, knee.X, knee.Y));
+ assert (AutoRouteParameters.is_smoothing
+ || point_in_closed_box (box1, knee.X, knee.Y)
+ || point_in_closed_box (box2, 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);
+ subnet, is_bad, False);
RD_DrawLine (rd, knee.X, knee.Y, end.X, end.Y, halfthick, group,
- subnet, is_bad, False);
+ subnet, is_bad, False);
}
else
{
@@ -2637,19 +3403,19 @@ RD_DrawManhattanLine (routedata_t * rd,
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;
+ kneestart.Y += (kneestart.Y > start.Y) ? -len45 : len45;
else
- kneestart.X += (kneestart.X > start.X) ? -len45 : len45;
+ kneestart.X += (kneestart.X > start.X) ? -len45 : len45;
if (kneeend.X == end.X)
- kneeend.Y += (kneeend.Y > end.Y) ? -len45 : len45;
+ kneeend.Y += (kneeend.Y > end.Y) ? -len45 : len45;
else
- kneeend.X += (kneeend.X > end.X) ? -len45 : len45;
+ 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);
+ group, subnet, is_bad, False);
RD_DrawLine (rd, kneestart.X, kneestart.Y, kneeend.X, kneeend.Y,
- halfthick, group, subnet, is_bad, True);
+ halfthick, group, subnet, is_bad, True);
RD_DrawLine (rd, kneeend.X, kneeend.Y, end.X, end.Y, halfthick, group,
- subnet, is_bad, False);
+ subnet, is_bad, False);
}
return (knee.X != end.X);
}
@@ -2661,70 +3427,120 @@ add_clearance (CheapPointType * nextpoint, const BoxType * b)
if (nextpoint->X == b->X1)
{
if (nextpoint->X +
- AutoRouteParameters.augStyle->style->Keepaway < (b->X1 + b->X2) / 2)
- nextpoint->X += AutoRouteParameters.augStyle->style->Keepaway;
+ AutoRouteParameters.style->Keepaway < (b->X1 + b->X2) / 2)
+ nextpoint->X += AutoRouteParameters.style->Keepaway;
else
- nextpoint->X = (b->X1 + b->X2) / 2;
+ nextpoint->X = (b->X1 + b->X2) / 2;
}
else if (nextpoint->X == b->X2)
{
if (nextpoint->X -
- AutoRouteParameters.augStyle->style->Keepaway > (b->X1 + b->X2) / 2)
- nextpoint->X -= AutoRouteParameters.augStyle->style->Keepaway;
+ AutoRouteParameters.style->Keepaway > (b->X1 + b->X2) / 2)
+ nextpoint->X -= AutoRouteParameters.style->Keepaway;
else
- nextpoint->X = (b->X1 + b->X2) / 2;
+ nextpoint->X = (b->X1 + b->X2) / 2;
}
else if (nextpoint->Y == b->Y1)
{
if (nextpoint->Y +
- AutoRouteParameters.augStyle->style->Keepaway < (b->Y1 + b->Y2) / 2)
- nextpoint->Y += AutoRouteParameters.augStyle->style->Keepaway;
+ AutoRouteParameters.style->Keepaway < (b->Y1 + b->Y2) / 2)
+ nextpoint->Y += AutoRouteParameters.style->Keepaway;
else
- nextpoint->Y = (b->Y1 + b->Y2) / 2;
+ nextpoint->Y = (b->Y1 + b->Y2) / 2;
}
else if (nextpoint->Y == b->Y2)
{
if (nextpoint->Y -
- AutoRouteParameters.augStyle->style->Keepaway > (b->Y1 + b->Y2) / 2)
- nextpoint->Y -= AutoRouteParameters.augStyle->style->Keepaway;
+ AutoRouteParameters.style->Keepaway > (b->Y1 + b->Y2) / 2)
+ nextpoint->Y -= AutoRouteParameters.style->Keepaway;
else
- nextpoint->Y = (b->Y1 + b->Y2) / 2;
+ nextpoint->Y = (b->Y1 + b->Y2) / 2;
}
}
+/* This back-traces the expansion boxes along the best path
+ * it draws the lines that will make the actual path.
+ * during refinement passes, it should try to maximize the area
+ * for other tracks so routing completion is easier.
+ *
+ * during smoothing passes, it should try to make a better path,
+ * possibly using diagonals, etc. The path boxes are larger on
+ * average now so there is more possiblity to decide on a nice
+ * path. Any combination of lines and arcs is possible, so long
+ * as they don't poke more than half thick outside the path box.
+ */
+
static void
TracePath (routedata_t * rd, routebox_t * path, const routebox_t * target,
- routebox_t * subnet, Boolean is_bad)
+ 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);
+ BDimension halfwidth = HALF_THICK (AutoRouteParameters.style->Thick);
+ BDimension radius = HALF_THICK (AutoRouteParameters.style->Diameter);
CheapPointType lastpoint, nextpoint;
routebox_t *lastpath;
BoxType b;
- assert (subnet->augStyle == AutoRouteParameters.augStyle);
- /* start from *edge* of target box */
+ assert (subnet->style == AutoRouteParameters.style);
/*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);
- TargetPoint (&nextpoint, target);
+
+ /* if we start with a thermal the target was a plane
+ * or the target was a pin and the source a plane
+ * in which case this thermal is the whole path
+ */
+ if (path->flags.is_thermal)
+ {
+ /* the target was a plane, so we need to find a good spot for the via
+ * now. It's logical to place it close to the source box which
+ * is where we're utlimately headed on this path. However, it
+ * must reside in the plane as well as the via area too.
+ */
+ if (path->parent.expansion_area->flags.is_via)
+ {
+ TargetPoint (&nextpoint, rb_source (path));
+ /* nextpoint is the middle of the source terminal now */
+ b = clip_box (&path->sbox, &path->parent.expansion_area->sbox);
+ nextpoint = closest_point_in_box (&nextpoint, &b);
+ /* now it's in the via and plane near the source */
+ }
+ else /* no via coming, target must have been a pin */
+ {
+ assert (target->type == PIN);
+ TargetPoint (&nextpoint, target);
+ }
+ assert (point_in_box (&path->sbox, nextpoint.X, nextpoint.Y));
+ RD_DrawThermal (rd, nextpoint.X, nextpoint.Y, path->group,
+ path->layer, subnet, is_bad);
+ }
+ else
+ {
+ /* start from best place of target box */
+ lastpoint.X = CENTER_X (target->sbox);
+ lastpoint.Y = CENTER_Y (target->sbox);
+ TargetPoint (&lastpoint, target);
+ if (AutoRouteParameters.last_smooth
+ && box_in_box (&path->sbox, &target->sbox))
+ path = path->parent.expansion_area;
+ b = path->sbox;
+ 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);
+ if (AutoRouteParameters.last_smooth)
+ RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
+ halfwidth, path->group, subnet, is_bad, TRUE);
+ else
+ last_x = RD_DrawManhattanLine (rd, &target->sbox, &path->sbox,
+ lastpoint, nextpoint, halfwidth,
+ path->group, subnet, is_bad, last_x);
+ }
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
showroutebox (path);
+#if defined(ROUTE_VERBOSE)
printf ("TRACEPOINT start (%d, %d)\n", nextpoint.X, nextpoint.Y);
-#endif /* ROUTE_DEBUG && DEBUG_SHOW_ROUTE_BOXES */
+#endif
+#endif
do
{
@@ -2732,43 +3548,49 @@ TracePath (routedata_t * rd, routebox_t * path, const routebox_t * target,
lastpath = path;
assert (path->type == EXPANSION_AREA);
path = path->parent.expansion_area;
-
- b = path->box;
+ b = path->sbox;
if (path->flags.circular)
- b = shrink_box (&b, MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 5);
- assert (b.X1 != b.X2 && b.Y1 != b.Y2); /* need someplace to put line! */
+ b = shrink_box (&b, MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 5);
+ 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 */
nextpoint = closest_point_in_box (&lastpoint, &b);
+#if 0
/* leave more clearance if this is a smoothing pass */
- if (AutoRouteParameters.is_smoothing)
- add_clearance (&nextpoint, &b);
- if (path->flags.source)
- TargetPoint (&nextpoint, path);
+ if (AutoRouteParameters.is_smoothing &&
+ (nextpoint.X != lastpoint.X || nextpoint.Y != lastpoint.Y))
+ add_clearance (&nextpoint, &b);
+#endif
+ if (path->flags.source && path->type != PLANE)
+ TargetPoint (&nextpoint, path);
assert (point_in_box (&lastpath->box, lastpoint.X, lastpoint.Y));
assert (point_in_box (&path->box, nextpoint.X, nextpoint.Y));
-#if defined(ROUTE_DEBUG)
+#if defined(ROUTE_DEBUG_VERBOSE)
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);
+ 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, &path->box,
- lastpoint, nextpoint, halfwidth,
- path->group, subnet, is_bad, last_x);
+ if (AutoRouteParameters.last_smooth)
+ RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
+ halfwidth, path->group, subnet, is_bad, TRUE);
+ else
+ last_x = RD_DrawManhattanLine (rd, &lastpath->sbox, &path->sbox,
+ lastpoint, nextpoint, halfwidth,
+ path->group, subnet, is_bad, last_x);
if (path->flags.is_via)
- { /* if via, then add via */
+ { /* if via, then add via */
#ifdef ROUTE_VERBOSE
- printf (" (vias)");
+ 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 (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);
@@ -2776,79 +3598,86 @@ TracePath (routedata_t * rd, routebox_t * path, const routebox_t * target,
showroutebox (path);
#endif /* ROUTE_DEBUG && DEBUG_SHOW_ROUTE_BOXES */
/* 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);
+ if (path->flags.is_thermal || path->type == PLANE)
+ RD_DrawThermal (rd, lastpoint.X, lastpoint.Y, path->group,
+ path->layer, subnet, is_bad);
/* when one hop from the source, make an extra path in *this* box */
- if (path->parent.expansion_area
- && path->parent.expansion_area->flags.source)
- {
- /* find special point on source (if it exists) */
- if (TargetPoint (&lastpoint, path->parent.expansion_area))
- {
- lastpoint = closest_point_in_box (&lastpoint, &path->box);
- if (AutoRouteParameters.is_smoothing)
- add_clearance (&lastpoint, &path->box);
- last_x = RD_DrawManhattanLine (rd, &path->box, &path->box,
- nextpoint, lastpoint, halfwidth,
- path->group, subnet, is_bad,
- last_x);
-#if defined(ROUTE_DEBUG)
- printf ("TRACEPATH: ");
- DumpRouteBox (path);
- printf
- ("TRACEPATH: (to source) point (%d, %d) to point (%d, %d) layer %d\n",
- nextpoint.X, nextpoint.Y, lastpoint.X, lastpoint.Y,
- path->group);
+ if (path->type == EXPANSION_AREA
+ && path->parent.expansion_area->flags.source
+ && path->parent.expansion_area->type != PLANE)
+ {
+ /* find special point on source (if it exists) */
+ if (TargetPoint (&lastpoint, path->parent.expansion_area))
+ {
+ lastpoint = closest_point_in_routebox (&lastpoint, path);
+ b = shrink_routebox (path);
+#if 0
+ if (AutoRouteParameters.is_smoothing)
+ add_clearance (&lastpoint, &b);
+#else
+ if (AutoRouteParameters.last_smooth)
+ RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X,
+ nextpoint.Y, halfwidth, path->group, subnet,
+ is_bad, TRUE);
+ else
+#endif
+ last_x = RD_DrawManhattanLine (rd, &b, &b,
+ nextpoint, lastpoint,
+ halfwidth, path->group, subnet,
+ is_bad, last_x);
+#if defined(ROUTE_DEBUG_VERBOSE)
+ printf ("TRACEPATH: ");
+ DumpRouteBox (path);
+ printf
+ ("TRACEPATH: (to source) point (%d, %d) to point (%d, %d) layer %d\n",
+ nextpoint.X, nextpoint.Y, lastpoint.X, lastpoint.Y,
+ path->group);
#endif
- nextpoint = lastpoint;
- }
- }
+ nextpoint = lastpoint;
+ }
+ }
}
while (!path->flags.source);
+ /* flush the line queue */
+ RD_DrawLine (rd, -1, 0, 0, 0, 0, 0, NULL, False, False);
+ if (TEST_FLAG (LIVEROUTEFLAG, PCB))
+ gui->use_mask (HID_FLUSH_DRAW_Q);
}
-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;
-};
-
/* create a fake "edge" used to defer via site searching. */
static void
CreateSearchEdge (struct routeone_state *s, vetting_t * work, edge_t * parent,
- routebox_t * rb, conflict_t conflict, rtree_t * targets)
+ routebox_t * rb, conflict_t conflict, rtree_t * targets,
+ Boolean in_plane)
{
- int boxes;
routebox_t *target;
+ BoxType b;
cost_t cost;
assert (__routebox_is_good (rb));
/* find the cheapest target */
- boxes = mtsBoxCount (work);
#if 0
target =
mincost_target_to_point (&parent->cost_point, max_layer + 1, targets,
- parent->mincost_target);
+ parent->mincost_target);
#else
target = parent->mincost_target;
#endif
+ b = shrink_routebox (target);
cost =
parent->cost_to_point + AutoRouteParameters.ViaCost +
- AutoRouteParameters.SearchPenalty * boxes +
- cost_to_layerless_box (&rb->cost_point, 0, &target->box);
+ cost_to_layerless_box (&rb->cost_point, 0, &b);
if (cost < s->best_cost)
{
edge_t *ne;
ne = malloc (sizeof (*ne));
+ memset ((void *) ne, 0, sizeof (*ne));
assert (ne);
ne->flags.via_search = 1;
+ ne->flags.in_plane = in_plane;
ne->rb = rb;
- if (rb->flags.orphan)
- RB_up_count (rb);
+ if (rb->flags.homeless)
+ RB_up_count (rb);
ne->work = work;
ne->mincost_target = target;
ne->flags.via_conflict_level = conflict;
@@ -2877,24 +3706,24 @@ add_or_destroy_edge (struct routeone_state *s, edge_t * e)
static void
best_path_candidate (struct routeone_state *s,
- edge_t * e, routebox_t * best_target)
+ edge_t * e, routebox_t * best_target)
{
e->cost = edge_cost (e, EXPENSIVE);
if (s->best_path == NULL || e->cost < s->best_cost)
{
-#if defined(ROUTE_DEBUG)
+#if defined(ROUTE_DEBUG) && defined (ROUTE_VERBOSE)
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);
+ if (s->best_path && s->best_path->flags.homeless)
+ 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);
+ if (s->best_path->flags.homeless)
+ RB_up_count (s->best_path);
}
}
@@ -2909,40 +3738,40 @@ struct routeone_via_site_state
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)
+ 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, Boolean in_plane)
{
int radius, keepaway;
vetting_t *work;
- BoxType region = shrink_box (&within->box, shrink);
+ BoxType region = shrink_routebox (within);
+ shrink_box (®ion, shrink);
- radius = HALF_THICK (AutoRouteParameters.augStyle->style->Diameter);
- keepaway = AutoRouteParameters.augStyle->style->Keepaway;
+ radius = HALF_THICK (AutoRouteParameters.style->Diameter);
+ keepaway = AutoRouteParameters.style->Keepaway;
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;
- //showbox (region, 1, max_layer + COMPONENT_LAYER);
+ /* ask for a via box near our cost_point first */
work = mtspace_query_rect (mtspace, ®ion, radius, keepaway,
- NULL, vss->free_space_vec,
- vss->lo_conflict_space_vec,
- vss->hi_conflict_space_vec,
- AutoRouteParameters.is_odd,
- AutoRouteParameters.with_conflicts);
+ NULL, vss->free_space_vec,
+ vss->lo_conflict_space_vec,
+ vss->hi_conflict_space_vec,
+ AutoRouteParameters.is_odd,
+ AutoRouteParameters.with_conflicts,
+ &parent_edge->cost_point);
if (!work)
return;
CreateSearchEdge (s, work, parent_edge, within, within_conflict_level,
- targets);
+ targets, in_plane);
}
void
do_via_search (edge_t * search, struct routeone_state *s,
- struct routeone_via_site_state *vss, mtspace_t * mtspace,
- rtree_t * targets)
+ struct routeone_via_site_state *vss, mtspace_t * mtspace,
+ rtree_t * targets)
{
int i, j, count = 0;
int radius, keepaway;
@@ -2950,62 +3779,198 @@ do_via_search (edge_t * search, struct routeone_state *s,
routebox_t *within;
conflict_t within_conflict_level;
- radius = HALF_THICK (AutoRouteParameters.augStyle->style->Diameter);
- keepaway = AutoRouteParameters.augStyle->style->Keepaway;
+ radius = HALF_THICK (AutoRouteParameters.style->Diameter);
+ keepaway = AutoRouteParameters.style->Keepaway;
work = mtspace_query_rect (mtspace, NULL, 0, 0,
- search->work, vss->free_space_vec,
- vss->lo_conflict_space_vec,
- vss->hi_conflict_space_vec,
- AutoRouteParameters.is_odd,
- AutoRouteParameters.with_conflicts);
+ search->work, vss->free_space_vec,
+ vss->lo_conflict_space_vec,
+ vss->hi_conflict_space_vec,
+ AutoRouteParameters.is_odd,
+ AutoRouteParameters.with_conflicts, NULL);
within = search->rb;
within_conflict_level = search->flags.via_conflict_level;
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);
+ (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 (!(i == NO_CONFLICT || AutoRouteParameters.with_conflicts))
- {
- free (area);
- continue;
- }
- /* answers are bloated by radius + keepaway */
- cliparea = shrink_box (area, radius + keepaway);
- cliparea.X2 += 1;
- cliparea.Y2 += 1;
- 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, search,
- within_conflict_level, i, targets);
- add_or_destroy_edge (s, ne);
- }
- }
+ {
+ BoxType cliparea;
+ BoxType *area = vector_remove_last (v);
+ if (!(i == NO_CONFLICT || AutoRouteParameters.with_conflicts))
+ {
+ free (area);
+ continue;
+ }
+ /* answers are bloated by radius + keepaway */
+ cliparea = shrink_box (area, radius + keepaway);
+ close_box (&cliparea);
+ free (area);
+ assert (box_is_good (&cliparea));
+ count++;
+ for (j = 0; j < max_layer; j++)
+ {
+ edge_t *ne;
+ if (j == within->group || !is_layer_group_active[j])
+ continue;
+ ne = CreateViaEdge (&cliparea, j, within, search,
+ within_conflict_level, i, targets);
+ add_or_destroy_edge (s, ne);
+ }
+ }
}
/* prevent freeing of work when this edge is destroyed */
search->flags.via_search = 0;
if (!work)
return;
- CreateSearchEdge (s, work, search, within, within_conflict_level, targets);
+ CreateSearchEdge (s, work, search, within, within_conflict_level, targets,
+ search->flags.in_plane);
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));
}
+/* vector of expansion areas to be eventually removed from r-tree
+ * this is a global for troubleshooting
+ */
+vector_t *area_vec;
+
+/* some routines for use in gdb while debugging */
+#if defined(ROUTE_DEBUG)
+static void
+list_conflicts (routebox_t * rb)
+{
+ int i, n;
+ if (!rb->conflicts_with)
+ return;
+ n = vector_size (rb->conflicts_with);
+ for (i = 0; i < n; i++)
+ printf ("%p, ", vector_element (rb->conflicts_with, i));
+}
+
+static void
+show_area_vec (int lay)
+{
+ int n, save;
+
+ if (!area_vec)
+ return;
+ save = showboxen;
+ showboxen = lay;
+ for (n = 0; n < vector_size (area_vec); n++)
+ {
+ routebox_t *rb = (routebox_t *) vector_element (area_vec, n);
+ showroutebox (rb);
+ }
+ showboxen = save;
+}
+
+static Boolean
+net_id (routebox_t * rb, long int id)
+{
+ routebox_t * p;
+ LIST_LOOP (rb, same_net, p);
+ if (p->flags.source && p->parent.pad->ID == id)
+ return True;
+ END_LOOP;
+ return False;
+}
+
+static void
+trace_parents (routebox_t * rb)
+{
+ while (rb && rb->type == EXPANSION_AREA)
+ {
+ printf (" %p ->", rb);
+ rb = rb->parent.expansion_area;
+ }
+ if (rb)
+ printf (" %p is source\n", rb);
+ else
+ printf ("NULL!\n");
+}
+
+static void
+show_one (routebox_t * rb)
+{
+ int save = showboxen;
+ showboxen = -1;
+ showroutebox (rb);
+ showboxen = save;
+}
+
+static void
+show_path (routebox_t * rb)
+{
+ while (rb && rb->type == EXPANSION_AREA)
+ {
+ show_one (rb);
+ rb = rb->parent.expansion_area;
+ }
+ show_one (rb);
+}
+
+static void
+show_sources (routebox_t * rb)
+{
+ routebox_t *p;
+ if (!rb->flags.source && !rb->flags.target)
+ {
+ printf ("start with a source or target please\n");
+ return;
+ }
+ LIST_LOOP (rb, same_net, p);
+ if (p->flags.source)
+ show_one (p);
+ END_LOOP;
+}
+
+int
+__show_tree (const BoxType * b, void *cl)
+{
+ int eo = (int) cl;
+ routebox_t *rb = (routebox_t *) b;
+ if (eo < 0 || eo == rb->flags.is_odd)
+ fillbox (b);
+ return 1;
+}
+
+static void
+show_tree (rtree_t * tree, int even_odd)
+{
+ r_search (tree, NULL, NULL, __show_tree, (void *) even_odd);
+ gui->use_mask (HID_FLUSH_DRAW_Q);
+}
+
+#endif
+
+static int
+__conflict_source (const BoxType * box, void *cl)
+{
+ routebox_t *rb = (routebox_t *) box;
+ if (rb->flags.touched || rb->flags.fixed)
+ return 0;
+ else
+ {
+ routebox_t *this = (routebox_t *) cl;
+ path_conflicts (this, rb, False);
+ touch_conflicts (this->conflicts_with, 1);
+ }
+ return 1;
+}
+
+static void
+source_conflicts (rtree_t * tree, routebox_t * rb)
+{
+ if (!AutoRouteParameters.with_conflicts)
+ return;
+ r_search (tree, &rb->sbox, NULL, __conflict_source, rb);
+ touch_conflicts (NULL, 1);
+}
+
struct routeone_status
{
Boolean found_route;
@@ -3014,6 +3979,7 @@ struct routeone_status
Boolean net_completely_routed;
};
+
static struct routeone_status
RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
{
@@ -3025,10 +3991,6 @@ RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
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;
@@ -3036,6 +3998,7 @@ RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
struct routeone_via_site_state vss;
assert (rd && from);
+ result.route_had_conflicts = 0;
/* no targets on to/from net need keepaway areas */
LIST_LOOP (from, same_net, p);
p->flags.nobloat = 1;
@@ -3053,38 +4016,38 @@ RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
* don't fill their bounding boxes and so connecting to them
* after we've routed is problematic. Better solution? */
if (to)
- { /* if we're routing to a specific target */
+ { /* 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;
+ { /* 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;
+ 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);
- if (!p->flags.nonstraight && is_layer_group_active[p->group])
- {
- p->flags.target = 1;
- num_targets++;
- }
- END_LOOP;
- }
+ assert (seen); /* otherwise from and to are on different nets! */
+ /* set target flags only on 'to's subnet */
+ LIST_LOOP (to, same_subnet, p);
+ if (!p->flags.nonstraight && is_layer_group_active[p->group])
+ {
+ p->flags.target = 1;
+ num_targets++;
+ }
+ END_LOOP;
+ }
}
else
{
/* all nodes on the net but not connected to from are targets */
LIST_LOOP (from, same_net, p);
if (!p->flags.source && is_layer_group_active[p->group]
- && !p->flags.nonstraight)
- {
- p->flags.target = 1;
- num_targets++;
- }
+ && !p->flags.nonstraight)
+ {
+ p->flags.target = 1;
+ num_targets++;
+ }
END_LOOP;
}
@@ -3122,52 +4085,43 @@ RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
assert (i <= num_targets);
free (target_list);
- /* add all sources to a vector (since we need to BreakEdges) */
source_vec = vector_create ();
+ /* touch the source subnet to prepare check for conflictors */
+ LIST_LOOP (from, same_subnet, p);
+ p->flags.touched = 1;
+ END_LOOP;
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, NORTH, targets);
- e->cost = edge_cost (e, EXPENSIVE);
- vector_append (source_vec, e);
- e = CreateEdge (p, (p->box.X1 + p->box.X2) / 2,
- p->box.Y2, ns_penalty, NULL, SOUTH, targets);
- e->cost = edge_cost (e, EXPENSIVE);
- vector_append (source_vec, e);
- e = CreateEdge (p, p->box.X2,
- (p->box.Y1 + p->box.Y2) / 2,
- ew_penalty, NULL, EAST, targets);
- e->cost = edge_cost (e, EXPENSIVE);
- 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, EXPENSIVE);
- vector_append (source_vec, e);
+ CheapPointType cp;
+ edge_t *e;
+ BoxType b = shrink_routebox (p);
+
+#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_SOURCES)
+ showroutebox (p);
+#endif
+ /* may expand in all directions from source; center edge cost point. */
+ /* note that planes shouldn't really expand, but we need an edge */
+
+ cp.X = CENTER_X (b);
+ cp.Y = CENTER_Y (b);
+ e = CreateEdge (p, cp.X, cp.Y, 0, NULL, ALL, targets);
+ cp = closest_point_in_box (&cp, &e->mincost_target->sbox);
+ cp = closest_point_in_box (&cp, &b);
+ e->cost_point = cp;
+ p->cost_point = cp;
+ source_conflicts (rd->layergrouptree[p->group], p);
+ vector_append (source_vec, e);
}
}
END_LOOP;
+ LIST_LOOP (from, same_subnet, p);
+ p->flags.touched = 0;
+ 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 */
@@ -3186,406 +4140,304 @@ RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
s.best_cost = EXPENSIVE;
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);
- if (e->flags.via_search)
- {
- if (seen++ <= max_edges)
- do_via_search (e, &s, &vss, rd->mtspace, targets);
- goto dontexpand;
- }
- 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]);
+#ifdef ROUTE_DEBUG
+ if (aabort)
+ goto dontexpand;
+#endif
/* 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 */
+ if (s.best_path && e->cost >= s.best_cost)
+ {
+ heap_free (s.workheap, KillEdge);
+ goto dontexpand; /* skip this edge */
+ }
/* 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;
+ goto dontexpand;
+ assert (__edge_is_good (e));
+ /* mark or unmark conflictors as needed */
+ touch_conflicts (e->rb->conflicts_with, 1);
+ if (e->flags.via_search)
+ {
+ do_via_search (e, &s, &vss, rd->mtspace, targets);
+ goto dontexpand;
+ }
+ /* we should never add edges on inactive layer groups to the heap. */
+ assert (is_layer_group_active[e->rb->group]);
#if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
//showedge (e);
#endif
+ if (e->rb->flags.is_thermal)
+ {
+ best_path_candidate (&s, e, e->mincost_target);
+ goto dontexpand;
+ }
/* 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 &&
- e->cost + AutoRouteParameters.ViaCost < s.best_cost)
- 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 &&
- e->cost + AutoRouteParameters.ViaCost < s.best_cost)
- 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
- || intersecting->flags.fixed)
- 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 ", e, e->cost_to_point);
- switch (e->expand_dir)
- {
- case NORTH:
- printf ("(X:%d to %d NORTH of %d)\n", e->rb->box.X1,
- e->rb->box.X2, e->rb->box.Y1);
- break;
- case SOUTH:
- printf ("(X:%d to %d SOUTH of %d)\n", e->rb->box.X1,
- e->rb->box.X2, e->rb->box.Y2);
- break;
- case WEST:
- printf ("(Y:%d to %d WEST of %d)\n", e->rb->box.Y1,
- e->rb->box.Y2, e->rb->box.X1);
- break;
- case EAST:
- printf ("(Y:%d to %d EAST of %d)\n", e->rb->box.Y1,
- e->rb->box.Y2, e->rb->box.X2);
- break;
- }
-#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)
- {
-#ifdef ROUTE_DEBUG
- printf ("past pcb edge\n");
-#endif
- 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)
- {
-#ifdef ROUTE_DEBUG
- printf ("copper violates spacing\n");
-#endif
- 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);
-#ifdef ROUTE_DEBUG
- DumpRouteBox (nrb);
-#endif
- 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;
- if (next && next->flags.source)
- goto dontexpand;
- /* no sense in expanding edges on targets */
- if (!next || !next->flags.target)
- {
- /* 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 &&
- e->cost + AutoRouteParameters.ViaCost < s.best_cost)
- 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)
- {
-#ifdef ROUTE_DEBUG
- printf ("hit source terminal\n");
-#endif
- goto dontexpand;
- }
- /* now deal with blocker... */
- /* maybe we've found a target? */
- if (next->flags.target)
- {
-#ifdef ROUTE_DEBUG
- printf ("hit target!\n");
-#endif
- /* we've won! */
- 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);
- 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);
- /* "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);
-#ifdef ROUTE_DEBUG
- printf ("left::");
- DumpRouteBox (nrb);
-#endif
- ne = CreateEdge2 (nrb, e->expand_dir, e, targets, NULL);
-#ifdef BREAK_ALL
- assert (vector_is_empty (edge_vec));
- vector_append (edge_vec, ne);
-#else
- add_or_destroy_edge (&s, ne);
-#endif
- }
- /* "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);
-#ifdef ROUTE_DEBUG
- printf ("right::");
- DumpRouteBox (nrb);
-#endif
- ne = CreateEdge2 (nrb, e->expand_dir, e, targets, NULL);
-#ifdef BREAK_ALL
- vector_append (edge_vec, ne);
-#else
- add_or_destroy_edge (&s, ne);
-#endif
- }
-#ifdef BREAK_ALL
- 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));
+ {
+ routebox_t *pin = FindThermable (targets, e->rb);
+ if (pin)
+ {
+ BoxType b = shrink_routebox (pin);
+ edge_t *ne;
+ routebox_t *nrb;
+ assert (pin->flags.target);
+ nrb = CreateExpansionArea (&b, e->rb->group, e->rb, True, e);
+ nrb->flags.is_thermal = 1;
+ /* moving through the plane is free */
+ e->cost_point.X = b.X1;
+ e->cost_point.Y = b.Y1;
+ ne = CreateEdge2 (nrb, e->expand_dir, e, NULL, pin);
+ best_path_candidate (&s, ne, pin);
+ DestroyEdge (&ne);
+ }
+ else
+ {
+ /* add in possible via sites in plane */
+ if (AutoRouteParameters.use_vias &&
+ e->cost + AutoRouteParameters.ViaCost < s.best_cost)
+ {
+ /* we need a giant thermal */
+ routebox_t *nrb =
+ CreateExpansionArea (&e->rb->sbox, e->rb->group, e->rb,
+ True, e);
+ edge_t *ne = CreateEdge2 (nrb, e->expand_dir, e, NULL,
+ e->mincost_target);
+ nrb->flags.is_thermal = 1;
+ add_via_sites (&s, &vss, rd->mtspace, nrb, NO_CONFLICT, ne,
+ targets, e->rb->style->Diameter, True);
+ }
+ }
+ goto dontexpand; /* planes only connect via thermals */
+ }
+ if (e->flags.is_via)
+ { /* special case via */
+ routebox_t *intersecting;
+ assert (AutoRouteParameters.use_vias);
+ assert (e->expand_dir == ALL);
+ assert (vector_is_empty (edge_vec));
+ /* if there is already something here on this layer (like an
+ * EXPANSION_AREA), then we don't want to expand from here
+ * at least not inside the expansion area. A PLANE on the
+ * other hand may be a target, or not.
+ */
+ intersecting =
+ FindOneInBox (rd->layergrouptree[e->rb->group], e->rb);
+
+ if (intersecting && intersecting->flags.target
+ && intersecting->type == PLANE)
+ {
+ /* we have hit a plane */
+ edge_t *ne;
+ routebox_t *nrb;
+ BoxType b = shrink_routebox (e->rb);
+ /* limit via region to that inside the plane */
+ clip_box (&b, &intersecting->sbox);
+ nrb = CreateExpansionArea (&b, e->rb->group, e->rb, True, e);
+ nrb->flags.is_thermal = 1;
+ ne = CreateEdge2 (nrb, e->expand_dir, e, NULL, intersecting);
+ best_path_candidate (&s, ne, intersecting);
+ DestroyEdge (&ne);
+ goto dontexpand;
+ }
+ else 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_search (rd->layergrouptree[e->rb->group],
+ &e->rb->box, NULL, no_planes,0));
+ */
+ r_insert_entry (rd->layergrouptree[e->rb->group], &e->rb->box,
+ 1);
+ e->rb->flags.homeless = 0; /* not homeless 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 homeless any more. */
+ e->rb->refcount = 0;
+ /* go ahead and expand this edge! */
+ }
+ else if (1)
+ goto dontexpand;
+ else if (0)
+ { /* 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 = shrink_routebox (e->rb);
+ 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
+ || intersecting->flags.fixed)
+ 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);
+ }
+ }
+ }
+ goto dontexpand;
+ }
+ /* 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 homeless. */
+ }
+ if (1)
+ {
+ routebox_t *nrb;
+ struct E_result *ans;
+ BoxType b;
+ vector_t *broken;
+ if (e->flags.is_interior)
+ {
+ assert (AutoRouteParameters.with_conflicts); /* no interior edges unless
+ routing with conflicts! */
+ assert (e->rb->conflicts_with);
+ b = e->rb->sbox;
+ switch (e->rb->came_from)
+ {
+ case NORTH:
+ b.Y2 = b.Y1 + 1;
+ b.X1 = CENTER_X (b);
+ b.X2 = b.X1 + 1;
+ break;
+ case EAST:
+ b.X1 = b.X2 - 1;
+ b.Y1 = CENTER_Y (b);
+ b.Y2 = b.Y1 + 1;
+ break;
+ case SOUTH:
+ b.Y1 = b.Y2 - 1;
+ b.X1 = CENTER_X (b);
+ b.X2 = b.X1 + 1;
+ break;
+ case WEST:
+ b.X2 = b.X1 + 1;
+ b.Y1 = CENTER_Y (b);
+ b.Y2 = b.Y1 + 1;
+ break;
+ default:
+ assert (0);
+ }
+ }
+ /* sources may not expand to their own edges because of
+ * adjacent blockers.
+ */
+ else if (e->rb->flags.source)
+ b = box_center (&e->rb->sbox);
+ else
+ b = e->rb->sbox;
+ ans = Expand (rd->layergrouptree[e->rb->group], e, &b);
+ if (!box_intersect (&ans->inflated, &ans->orig))
+ goto dontexpand;
+#if 0
+ /* skip if it didn't actually expand */
+ if (ans->inflated.X1 >= e->rb->sbox.X1 &&
+ ans->inflated.X2 <= e->rb->sbox.X2 &&
+ ans->inflated.Y1 >= e->rb->sbox.Y1 &&
+ ans->inflated.Y2 <= e->rb->sbox.Y2)
+ goto dontexpand;
#endif
- if (next->type != EXPANSION_AREA && !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);
- }
- }
+
+ if (!box_is_good (&ans->inflated))
+ goto dontexpand;
+ nrb = CreateExpansionArea (&ans->inflated, e->rb->group, e->rb,
+ True, e);
+ r_insert_entry (rd->layergrouptree[nrb->group], &nrb->box, 1);
+ vector_append (area_vec, nrb);
+ nrb->flags.homeless = 0; /* not homeless any more */
+ broken =
+ BreakManyEdges (&s, targets, rd->layergrouptree[nrb->group],
+ area_vec, ans, nrb, e);
+ while (!vector_is_empty (broken))
+ {
+ edge_t *ne = vector_remove_last (broken);
+ add_or_destroy_edge (&s, ne);
+ }
+ vector_destroy (&broken);
+
+ /* add in possible via sites in nrb */
+ if (AutoRouteParameters.use_vias && !e->rb->flags.is_via &&
+ e->cost + AutoRouteParameters.ViaCost < s.best_cost)
+ add_via_sites (&s, &vss,
+ rd->mtspace, nrb, NO_CONFLICT, e, targets, 0,
+ False);
+ goto dontexpand;
+ }
dontexpand:
DestroyEdge (&e);
}
+ touch_conflicts (NULL, 1);
heap_destroy (&s.workheap);
r_destroy_tree (&targets);
assert (vector_is_empty (edge_vec));
@@ -3602,33 +4454,33 @@ RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
result.best_route_cost = s.best_cost;
/* determine if the best path had conflicts */
result.route_had_conflicts = 0;
- if (AutoRouteParameters.with_conflicts)
- for (rb = s.best_path; !rb->flags.source;
- rb = rb->parent.expansion_area)
- if (rb->underlying)
- {
- rb->underlying->flags.is_bad = 1;
- result.route_had_conflicts++;
- }
+ if (AutoRouteParameters.with_conflicts && s.best_path->conflicts_with)
+ {
+ while (!vector_is_empty (s.best_path->conflicts_with))
+ {
+ rb = vector_remove_last (s.best_path->conflicts_with);
+ rb->flags.is_bad = 1;
+ result.route_had_conflicts++;
+ }
+ }
#ifdef ROUTE_VERBOSE
if (result.route_had_conflicts)
- printf (" (%d conflicts)", result.route_had_conflicts);
+ printf (" (%d conflicts)", result.route_had_conflicts);
#endif
if (result.route_had_conflicts < AutoRouteParameters.hi_conflict)
- {
- /* 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 */
- }
+ {
+ /* 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);
+ }
else
- {
+ {
#ifdef ROUTE_VERBOSE
- printf (" (too many in fact)");
+ printf (" (too many in fact)");
#endif
- result.found_route = False;
- }
+ result.found_route = False;
+ }
#ifdef ROUTE_VERBOSE
printf ("\n");
#endif
@@ -3641,26 +4493,23 @@ RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
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);
+ assert (!rb->flags.homeless);
+ if (rb->conflicts_with
+ && rb->parent.expansion_area->conflicts_with != rb->conflicts_with)
+ vector_destroy (&rb->conflicts_with);
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);
+ /* clean up; remove all 'source', 'target', and 'nobloat' flags */
+ LIST_LOOP (from, same_net, p);
+ if (p->flags.source && p->conflicts_with)
+ vector_destroy (&p->conflicts_with);
+ p->flags.touched = p->flags.source = p->flags.target = p->flags.nobloat = 0;
+ END_LOOP;
vector_destroy (&vss.free_space_vec);
vector_destroy (&vss.lo_conflict_space_vec);
@@ -3671,34 +4520,42 @@ RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
static void
InitAutoRouteParameters (int pass,
- AugmentedRouteStyleType * augStyle,
- Boolean with_conflicts, Boolean is_smoothing)
+ RouteStyleType * style,
+ Boolean with_conflicts, Boolean is_smoothing,
+ Boolean lastpass)
{
+ int i;
/* routing style */
- AutoRouteParameters.augStyle = augStyle;
+ AutoRouteParameters.style = style;
+ AutoRouteParameters.bloat = style->Keepaway + HALF_THICK (style->Thick);
/* costs */
AutoRouteParameters.ViaCost =
- 50000 + augStyle->style->Diameter * (is_smoothing ? 80 : 10);
- AutoRouteParameters.LastConflictPenalty = 500 * pass / passes + 2;
+ 350000 + style->Diameter * (is_smoothing ? 80 : 30);
+ AutoRouteParameters.LastConflictPenalty = (400 * pass / passes + 2)/(pass+1);
AutoRouteParameters.ConflictPenalty =
- 5 * AutoRouteParameters.LastConflictPenalty;
+ 4 * AutoRouteParameters.LastConflictPenalty;
AutoRouteParameters.JogPenalty = 1000 * (is_smoothing ? 20 : 4);
- AutoRouteParameters.WrongWayPenalty = 2000 * (is_smoothing ? 2 : 4);
- AutoRouteParameters.DirectionPenalty = 2;
- AutoRouteParameters.SurfacePenalty = 3;
- AutoRouteParameters.AwayPenalty = 4;
- AutoRouteParameters.MinPenalty = MIN (AutoRouteParameters.DirectionPenalty,
- AutoRouteParameters.SurfacePenalty);
- AutoRouteParameters.SearchPenalty = 200000;
+ AutoRouteParameters.CongestionPenalty = 1e6;
+ AutoRouteParameters.MinPenalty = EXPENSIVE;
+ for (i = 0; i < max_layer; i++)
+ {
+ if (is_layer_group_active[i]) {
+ AutoRouteParameters.MinPenalty = MIN (x_cost[i],
+ AutoRouteParameters.MinPenalty);
+ AutoRouteParameters.MinPenalty = MIN (y_cost[i],
+ AutoRouteParameters.MinPenalty);
+ }
+ }
AutoRouteParameters.NewLayerPenalty = is_smoothing ?
- 0.5 * EXPENSIVE : 6 * AutoRouteParameters.ViaCost +
- AutoRouteParameters.SearchPenalty;
+ 0.5 * EXPENSIVE : 10 * AutoRouteParameters.ViaCost;
/* other */
- AutoRouteParameters.hi_conflict = MAX (passes - pass + 3, 3);
+ AutoRouteParameters.hi_conflict = MAX (8 * (passes - pass + 1), 6);
AutoRouteParameters.is_odd = (pass & 1);
AutoRouteParameters.with_conflicts = with_conflicts;
AutoRouteParameters.is_smoothing = is_smoothing;
AutoRouteParameters.rip_always = is_smoothing;
+ AutoRouteParameters.last_smooth = 0; //lastpass;
+ AutoRouteParameters.pass = pass + 1;
}
#ifndef NDEBUG
@@ -3723,7 +4580,7 @@ no_expansion_boxes (routedata_t * rd)
for (i = 0; i < max_layer; i++)
{
if (r_search (rd->layergrouptree[i], &big, NULL, bad_boy, NULL))
- return False;
+ return False;
}
return True;
}
@@ -3737,6 +4594,11 @@ struct routeall_status
int routed_subnets;
/* total subnets routed with conflicts */
int conflict_subnets;
+ /* net failted entirely */
+ int failed;
+ /* net was ripped */
+ int ripped;
+ int total_nets_routed;
};
struct routeall_status
RouteAll (routedata_t * rd)
@@ -3763,13 +4625,13 @@ RouteAll (routedata_t * rd)
LIST_LOOP (rd->first_net, different_net, net);
{
float area;
- BoxType bb = net->box;
+ BoxType bb = shrink_routebox (net);
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);
+ MAKEMIN (bb.X1, p->sbox.X1);
+ MAKEMIN (bb.Y1, p->sbox.Y1);
+ MAKEMAX (bb.X2, p->sbox.X2);
+ MAKEMAX (bb.Y2, p->sbox.Y2);
}
END_LOOP;
area = (float) (bb.X2 - bb.X1) * (bb.Y2 - bb.Y1);
@@ -3777,170 +4639,202 @@ RouteAll (routedata_t * rd)
}
END_LOOP;
+ ras.total_nets_routed = 0;
/* refinement/finishing passes */
for (i = 0; i <= passes + smoothes; i++)
{
#ifdef ROUTE_VERBOSE
if (i > 0 && i <= passes)
- printf ("--------- STARTING REFINEMENT PASS %d ------------\n", i);
+ printf ("--------- STARTING REFINEMENT PASS %d ------------\n", i);
else if (i > passes)
- printf ("--------- STARTING SMOOTHING PASS %d -------------\n",
- i - passes);
+ printf ("--------- STARTING SMOOTHING PASS %d -------------\n",
+ i - passes);
#endif
- ras.total_subnets = ras.routed_subnets = ras.conflict_subnets = 0;
+ ras.total_subnets = ras.routed_subnets = ras.conflict_subnets =
+ ras.failed = ras.ripped = 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 < passes, i > passes);
- if (i > 0)
- {
- /* rip up all unfixed traces in this net ? */
- if (AutoRouteParameters.rip_always)
- rip = True;
- else
- {
- rip = False;
- LIST_LOOP (net, same_net, p);
- if (!p->flags.fixed && p->flags.is_bad)
- {
- rip = True;
- break;
- }
- END_LOOP;
- }
-
- LIST_LOOP (net, same_net, p);
- if (!p->flags.fixed)
- {
- Boolean del;
- assert (!p->flags.orphan);
- p->flags.is_bad = 0;
- if (rip)
- {
- RemoveFromNet (p, NET);
- RemoveFromNet (p, SUBNET);
- }
- if (AutoRouteParameters.use_vias && p->type != VIA_SHADOW)
- {
- mtspace_remove (rd->mtspace, &p->box,
- p->flags.is_odd ? ODD : EVEN,
- p->augStyle->style->Keepaway);
- if (!rip)
- mtspace_add (rd->mtspace, &p->box,
- p->flags.is_odd ? EVEN : ODD,
- p->augStyle->style->Keepaway);
- }
- if (rip)
- {
- if (TEST_FLAG (LIVEROUTEFLAG, PCB)
- && (p->type == LINE || p->type == VIA))
- EraseRouteBox (p);
- del =
- r_delete_entry (rd->layergrouptree[p->group],
- &p->box);
- assert (del);
- }
- else
- {
- p->flags.is_odd = AutoRouteParameters.is_odd;
- }
- }
- END_LOOP;
- /* reset to original connectivity */
- if (rip)
- ResetSubnet (net);
- else
- {
- heap_insert (next_pass, 0, net);
- continue;
- }
- }
- /* 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 ROUTE_DEBUG
+ if (aabort)
+ break;
+#endif
+ net = (routebox_t *) heap_remove_smallest (this_pass);
+ InitAutoRouteParameters (i, net->style, i < passes, i > passes,
+ i == passes + smoothes);
+ if (i > 0)
+ {
+ /* rip up all unfixed traces in this net ? */
+ if (AutoRouteParameters.rip_always)
+ rip = True;
+ else
+ {
+ rip = False;
+ LIST_LOOP (net, same_net, p);
+ if (p->flags.is_bad)
+ {
+ rip = True;
+ break;
+ }
+ END_LOOP;
+ }
+
+ LIST_LOOP (net, same_net, p);
+ p->flags.is_bad = 0;
+ if (!p->flags.fixed)
+ {
+ Boolean del;
+ assert (!p->flags.homeless);
+ if (rip)
+ {
+ RemoveFromNet (p, NET);
+ RemoveFromNet (p, SUBNET);
+ }
+ if (AutoRouteParameters.use_vias && p->type != VIA_SHADOW
+ && p->type != PLANE)
+ {
+ mtspace_remove (rd->mtspace, &p->box,
+ p->flags.is_odd ? ODD : EVEN,
+ p->style->Keepaway);
+ if (!rip)
+ mtspace_add (rd->mtspace, &p->box,
+ p->flags.is_odd ? EVEN : ODD,
+ p->style->Keepaway);
+ }
+ if (rip)
+ {
+ if (TEST_FLAG (LIVEROUTEFLAG, PCB)
+ && (p->type == LINE || p->type == VIA))
+ EraseRouteBox (p);
+ del =
+ r_delete_entry (rd->layergrouptree[p->group],
+ &p->box);
+ assert (del);
+ }
+ else
+ {
+ p->flags.is_odd = AutoRouteParameters.is_odd;
+ }
+ }
+ END_LOOP;
+ if (TEST_FLAG (LIVEROUTEFLAG, PCB))
+ gui->use_mask (HID_FLUSH_DRAW_Q);
+ /* reset to original connectivity */
+ if (rip)
+ {
+ ras.ripped++;
+ ResetSubnet (net);
+ }
+ else
+ {
+ heap_insert (next_pass, 0, net);
+ continue;
+ }
+ }
+ /* 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 */
+#ifdef ROUTE_DEBUG
+ if (ras.total_subnets && !aabort)
+#else
+ if (ras.total_subnets)
+#endif
+ {
+ /* 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 */
- 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);
+ BoxType b = shrink_routebox (p);
+ /* using a heap allows us to start from smaller objects and
+ * end at bigger ones. also prefer to start at planes, then pads */
+ heap_insert (net_heap, (float) (b.X2 - b.X1) *
+#if defined(ROUTE_RANDOMIZED)
+ (0.3 + rand () / (RAND_MAX + 1.0)) *
+#endif
+ (b.Y2 - b.Y1) * (p->type == PLANE ?
+ -1 : (p->type ==
+ PAD ? 1 : 10)), p);
+ }
+ END_LOOP;
+ ros.net_completely_routed = 0;
+ 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
- {
- assert (no_expansion_boxes (rd));
- ros =
- RouteOne (rd, p, NULL,
- ((AutoRouteParameters.
- is_smoothing ? 2000 : 800) * (i +
- 1)) *
- routing_layers);
- total_net_cost += ros.best_route_cost;
- if (ros.found_route)
- {
- if (ros.route_had_conflicts)
- ras.conflict_subnets++;
- else
- ras.routed_subnets++;
- }
- else
- {
- /* 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);
- }
- }
+ if (p->flags.fixed && !p->flags.subnet_processed
+ && p->type != OTHER)
+ {
+ while (!ros.net_completely_routed)
+ {
+ assert (no_expansion_boxes (rd));
+ /* FIX ME: the number of edges to examine should be in autoroute parameters
+ * i.e. the 2000 and 800 hard-coded below should be controllable by the user
+ */
+ ros =
+ RouteOne (rd, p, NULL,
+ ((AutoRouteParameters.
+ is_smoothing ? 2000 : 800) * (i +
+ 1)) *
+ routing_layers);
+ total_net_cost += ros.best_route_cost;
+ if (ros.found_route)
+ {
+ if (ros.route_had_conflicts)
+ ras.conflict_subnets++;
+ else
+ {
+ ras.routed_subnets++;
+ ras.total_nets_routed++;
+ }
+ }
+ else
+ {
+ if (!ros.net_completely_routed)
+ ras.failed++;
+ /* don't bother trying any other source in this subnet */
+ LIST_LOOP (p, same_subnet, pp);
+ pp->flags.subnet_processed = 1;
+ END_LOOP;
+ break;
+ }
+ /* 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. */
+ }
+ }
+ }
#ifndef NET_HEAP
- END_LOOP;
+ 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);
- if (total_net_cost < EXPENSIVE)
- this_cost += total_net_cost;
- /* reset subnet_processed flags */
- LIST_LOOP (net, same_net, p);
- {
- p->flags.subnet_processed = 0;
- }
- END_LOOP;
- }
+ if (!ros.net_completely_routed)
+ net->flags.is_bad = 1; /* don't skip this the next round */
+ }
+
+ /* 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);
+ if (total_net_cost < EXPENSIVE)
+ this_cost += total_net_cost;
+ /* 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));
@@ -3948,23 +4842,28 @@ RouteAll (routedata_t * rd)
this_pass = next_pass;
next_pass = tmp;
/* XXX: here we should update a status bar */
-#ifdef ROUTE_VERBOSE
+#if defined(ROUTE_DEBUG) || defined (ROUTE_VERBOSE)
printf
- ("END OF PASS %d: %d/%d subnets routed without conflicts at cost %.0f\n",
- i, ras.routed_subnets, ras.total_subnets, this_cost);
+ ("END OF PASS %d: %d/%d subnets routed without conflicts at cost %.0f, %d conflicts, %d failed %d ripped\n",
+ i, ras.routed_subnets, ras.total_subnets, this_cost,
+ ras.conflict_subnets, ras.failed, ras.ripped);
+#endif
+#ifdef ROUTE_DEBUG
+ if (aabort)
+ break;
#endif
/* if no conflicts found, skip directly to smoothing pass! */
if (ras.conflict_subnets == 0 && ras.routed_subnets == ras.total_subnets
- && i < passes)
- i = passes - (smoothes ? 0 : 1);
+ && i <= passes)
+ i = passes - (smoothes ? 0 : 1);
/* if no changes in a smoothing round, then we're done */
- if (this_cost == last_cost && i > passes)
- break;
+ if (this_cost == last_cost && i > passes && i < passes + smoothes)
+ i = passes + smoothes - 1;
last_cost = this_cost;
this_cost = 0;
}
Message ("%d of %d nets successfully routed.\n", ras.routed_subnets,
- ras.total_subnets);
+ ras.total_subnets);
heap_destroy (&this_pass);
heap_destroy (&next_pass);
@@ -4039,113 +4938,124 @@ IronDownAllUnfixedPaths (routedata_t * rd)
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 * 2,
- MakeFlags (AUTOFLAG |
- (TEST_FLAG (CLEARNEWFLAG, PCB) ? CLEARLINEFLAG :
- 0)));
-
- 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)
- {
- 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);
- }
+ {
+ /* 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->style->Thick);
+ BoxType b;
+ assert (p->parent.line == NULL);
+ /* orthogonal; thickness is 2*halfwidth */
+ /* flip coordinates, if bl_to_ur */
+ b = p->sbox;
+ b = shrink_box (&b, halfwidth);
+ if (b.X2 == b.X1 + 1)
+ b.X2 = b.X1;
+ if (b.Y2 == b.Y1 + 1)
+ b.Y2 = b.Y1;
+ 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->style->Thick,
+ p->style->Keepaway * 2,
+ MakeFlags (AUTOFLAG |
+ (TEST_FLAG (CLEARNEWFLAG, PCB) ? CLEARLINEFLAG :
+ 0)));
+
+ 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->style->Diameter);
+ BoxType b = shrink_routebox (p);
+ assert (pp->type == VIA);
+ if (pp->parent.via == NULL)
+ {
+ assert (b.X1 + radius == b.X2 - radius);
+ assert (b.Y1 + radius == b.Y2 - radius);
+ pp->parent.via =
+ CreateNewVia (PCB->Data, b.X1 + radius,
+ b.Y1 + radius,
+ pp->style->Diameter,
+ 2 * pp->style->Keepaway,
+ 0, pp->style->Hole, NULL,
+ MakeFlags (AUTOFLAG));
+ assert (pp->parent.via);
+ if (pp->parent.via)
+ {
+ 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 == THERMAL)
+ /* nothing to do because, the via might not be there yet */ ;
+ 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);
- ASSIGN_THERM (p->layer, PCB->ThermStyle, pin);
- }
- }
+ if (p->type == THERMAL)
+ {
+ PinTypePtr pin = NULL;
+ /* thermals are alread a single point search, no need to shrink */
+ int type = FindPin (&p->box, &pin);
+ if (pin)
+ {
+ AddObjectToClearPolyUndoList (type,
+ pin->Element ? pin->Element : pin,
+ pin, pin, False);
+ RestoreToPolygon (PCB->Data, VIA_TYPE, LAYER_PTR (p->layer),
+ pin);
+ AddObjectToFlagUndoList (type,
+ pin->Element ? pin->Element : pin, pin,
+ pin);
+ ASSIGN_THERM (p->layer, PCB->ThermStyle, pin);
+ AddObjectToClearPolyUndoList (type,
+ pin->Element ? pin->Element : pin,
+ pin, pin, True);
+ ClearFromPolygon (PCB->Data, VIA_TYPE, LAYER_PTR (p->layer),
+ pin);
+ changed = True;
+ }
+ }
}
END_LOOP;
}
@@ -4160,6 +5070,11 @@ AutoRoute (Boolean selected)
routedata_t *rd;
int i;
+ if (TEST_FLAG (LIVEROUTEFLAG, PCB))
+ {
+ gui->use_mask (HID_LIVE_DRAWING);
+ }
+
if (ar_gc == 0)
{
ar_gc = gui->make_gc ();
@@ -4169,13 +5084,13 @@ AutoRoute (Boolean selected)
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);
- }
+ 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);
@@ -4189,39 +5104,48 @@ AutoRoute (Boolean selected)
/* count number of rats selected */
RAT_LOOP (PCB->Data);
{
- if (!selected || TEST_FLAG (SELECTEDFLAG, line))
- i++;
+ 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 */
+ 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;
- }
+ {
+ 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->style == b->style);
+/*
+ if (a->type != PAD && b->type == PAD)
+ {
+ routebox_t *t = a;
+ a = b;
+ b = t;
+ }
+*/
+ /* route exactly one net, without allowing conflicts */
+ InitAutoRouteParameters (0, a->style, False, True, True);
+ /* hace planes work better as sources than targets */
+ 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 */
@@ -4230,89 +5154,93 @@ AutoRoute (Boolean selected)
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 */
+ 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;
- }
+ {
+ 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)
- {
+ {
+ /* 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)
+ {
#ifdef DEBUG_STALE_RATS
AddObjectToFlagUndoList (RATLINE_TYPE, line, line, line);
ASSIGN_FLAG (SELECTEDFLAG, True, line);
DrawRat (line, 0);
#endif /* DEBUG_STALE_RATS */
- Message ("The rats nest is stale! Aborting autoroute...\n");
- goto donerouting;
- }
- /* merge subnets into a net! */
- MergeNets (a, b, NET);
- }
+ 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);
+ 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;
+ 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;
+ changed = (RouteAll (rd).total_nets_routed > 0) || changed;
donerouting:
if (changed)
changed = IronDownAllUnfixedPaths (rd);
DestroyRouteData (&rd);
+ if (TEST_FLAG (LIVEROUTEFLAG, PCB))
+ {
+ gui->use_mask (HID_LIVE_DRAWING_OFF);
+ }
if (changed)
{
SaveUndoSerialNumber ();
@@ -4328,5 +5256,8 @@ donerouting:
ClearAndRedrawOutput ();
}
RestoreFindFlag ();
+#if defined (ROUTE_DEBUG)
+ aabort = 0;
+#endif
return (changed);
}
diff --git a/src/box.h b/src/box.h
index 59f2f47..291c6d7 100644
--- a/src/box.h
+++ b/src/box.h
@@ -37,10 +37,12 @@
#ifndef __BOX_H_INCLUDED__
#define __BOX_H_INCLUDED__
+#include <assert.h>
#include "global.h"
typedef enum
-{ NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3 } direction_t;
+{ NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3, NE = 4, SE = 5, SW = 6, NW =
+ 7, ALL = 8 } direction_t;
/* rotates box 90-degrees cw */
/* that's a strange rotation! */
@@ -79,6 +81,9 @@ typedef enum
}\
} while (0)
+/* to avoid overflow, we calculate centers this way */
+#define CENTER_X(b) ((b).X1 + ((b).X2 - (b).X1)/2)
+#define CENTER_Y(b) ((b).Y1 + ((b).Y2 - (b).Y1)/2)
/* some useful box utilities. */
typedef struct cheap_point
@@ -96,13 +101,17 @@ point_in_box (const BoxType * box, LocationType X, LocationType Y)
return (X >= box->X1) && (Y >= box->Y1) && (X < box->X2) && (Y < box->Y2);
}
-#ifndef NDEBUG
static inline Boolean
-__box_is_good (const BoxType * b)
+point_in_closed_box (const BoxType * box, LocationType X, LocationType Y)
+{
+ return (X >= box->X1) && (Y >= box->Y1) && (X <= box->X2) && (Y <= box->Y2);
+}
+
+static inline Boolean
+box_is_good (const BoxType * b)
{
return (b->X1 < b->X2) && (b->Y1 < b->Y2);
}
-#endif /* !NDEBUG */
static inline Boolean
box_intersect (const BoxType * a, const BoxType * b)
@@ -164,6 +173,50 @@ bloat_box (const BoxType * box, LocationType amount)
return shrink_box (box, -amount);
}
+/* construct a minimum box that touches the input box at the center */
+static inline BoxType
+box_center (const BoxType * box)
+{
+ BoxType r;
+ r.X1 = box->X1 + (box->X2 - box->X1)/2;
+ r.X2 = r.X1 + 1;
+ r.Y1 = box->Y1 + (box->Y2 - box->Y1)/2;
+ r.Y2 = r.Y1 + 1;
+ return r;
+}
+
+/* construct a minimum box that touches the input box at the corner */
+static inline BoxType
+box_corner (const BoxType * box)
+{
+ BoxType r;
+ r.X1 = box->X1;
+ r.X2 = r.X1 + 1;
+ r.Y1 = box->Y1;
+ r.Y2 = r.Y1 + 1;
+ return r;
+}
+
+/* construct a box that holds a single point */
+static inline BoxType
+point_box (LocationType X, LocationType Y)
+{
+ BoxType r;
+ r.X1 = X;
+ r.X2 = X + 1;
+ r.Y1 = Y;
+ r.Y2 = Y + 1;
+ return r;
+}
+
+/* close a bounding box by pushing its upper right corner */
+static inline void
+close_box (BoxType * r)
+{
+ r->X2++;
+ r->Y2++;
+}
+
/* return the square of the minimum distance from a point to some point
* inside a box. The box is half-closed! That is, the top-left corner
* is considered in the box, but the bottom-right corner is not. */
diff --git a/src/heap.c b/src/heap.c
index 4959b58..fee6412 100644
--- a/src/heap.c
+++ b/src/heap.c
@@ -138,6 +138,18 @@ heap_destroy (heap_t ** heap)
*heap = NULL;
}
+/* free all elements in the heap */
+void heap_free (heap_t *heap, void (*freefunc) (void *))
+{
+ assert (heap);
+ assert (__heap_is_good (heap));
+ for ( ; heap->size; heap->size--)
+ {
+ if (heap->element[heap->size].data)
+ freefunc (heap->element[heap->size].data);
+ }
+}
+
/* -- mutation -- */
static void
__upheap (heap_t * heap, int k)
@@ -247,3 +259,12 @@ heap_is_empty (heap_t * heap)
assert (__heap_is_good (heap));
return heap->size == 0;
}
+
+/* -- size -- */
+int
+heap_size (heap_t * heap)
+{
+ assert (__heap_is_good (heap));
+ return heap->size;
+}
+
diff --git a/src/heap.h b/src/heap.h
index 4eeb2b7..6ee973d 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -39,7 +39,7 @@
#include "global.h"
-/* type of heap costs. *must be integer!* */
+/* type of heap costs */
typedef double cost_t;
/* what a heap looks like */
typedef struct heap_struct heap_t;
@@ -48,6 +48,8 @@ typedef struct heap_struct heap_t;
heap_t *heap_create ();
/* destroy a heap */
void heap_destroy (heap_t ** heap);
+/* free all elements in a heap */
+void heap_free (heap_t * heap, void (*funcfree) (void *));
/* -- mutation -- */
void heap_insert (heap_t * heap, cost_t cost, void *data);
@@ -58,5 +60,6 @@ void *heap_replace (heap_t * heap, cost_t cost, void *data);
/* -- interrogation -- */
int heap_is_empty (heap_t * heap);
+int heap_size (heap_t * heap);
#endif /* __HEAP_INCLUDED__ */
diff --git a/src/hid.h b/src/hid.h
index 3efb9ed..d3faad6 100644
--- a/src/hid.h
+++ b/src/hid.h
@@ -351,6 +351,12 @@ typedef enum
#define HID_MASK_CLEAR 2
/* Polygons being drawn after clears. */
#define HID_MASK_AFTER 3
+ /* Set to do live drawing on the screen */
+#define HID_LIVE_DRAWING 4
+ /* stop live drawing on the screen */
+#define HID_LIVE_DRAWING_OFF 5
+ /* flush any queued drawing */
+#define HID_FLUSH_DRAW_Q 6
/* Set a color. Names can be like "red" or "#rrggbb" or special
names like "erase". *Always* use the "erase" color for removing
diff --git a/src/hid/gtk/gtkhid-main.c b/src/hid/gtk/gtkhid-main.c
index c27f857..871a0d0 100644
--- a/src/hid/gtk/gtkhid-main.c
+++ b/src/hid/gtk/gtkhid-main.c
@@ -562,8 +562,26 @@ void
ghid_use_mask (int use_it)
{
static int mask_seq_id = 0;
+ static GdkDrawable *old;
GdkColor color;
+ if (use_it == HID_FLUSH_DRAW_Q)
+ {
+ gdk_flush();
+ return;
+ }
+ else if (use_it == HID_LIVE_DRAWING)
+ {
+ old = gport->drawable;
+ gport->drawable = gport->drawing_area->window;
+ return;
+ }
+ else if (use_it == HID_LIVE_DRAWING_OFF)
+ {
+ gport->drawable = old;
+ return;
+ }
+
if (!gport->pixmap)
return;
if (use_it == cur_mask)
diff --git a/src/hid/lesstif/main.c b/src/hid/lesstif/main.c
index 99f9851..37e3f5d 100644
--- a/src/hid/lesstif/main.c
+++ b/src/hid/lesstif/main.c
@@ -3050,6 +3050,24 @@ lesstif_destroy_gc (hidGC gc)
static void
lesstif_use_mask (int use_it)
{
+ static Window old;
+
+ if (use_it == HID_FLUSH_DRAW_Q)
+ {
+ XFlush (display);
+ return;
+ }
+ else if (use_it == HID_LIVE_DRAWING)
+ {
+ old = pixmap;
+ pixmap = window;
+ return;
+ }
+ else if (use_it == HID_LIVE_DRAWING_OFF)
+ {
+ pixmap = old;
+ return;
+ }
if ((TEST_FLAG (THINDRAWFLAG, PCB) || TEST_FLAG(THINDRAWPOLYFLAG, PCB)) &&
!use_xrender)
use_it = 0;
diff --git a/src/mtspace.c b/src/mtspace.c
index b94f9cd..f5ce554 100644
--- a/src/mtspace.c
+++ b/src/mtspace.c
@@ -46,6 +46,7 @@
#include <setjmp.h>
#include "box.h"
+#include "heap.h"
#include "rtree.h"
#include "mtspace.h"
#include "vector.h"
@@ -54,6 +55,7 @@
#include <dmalloc.h>
#endif
+#define ABS(x) ((x) < 0 ? -(x) : (x))
RCSID ("$Id$");
/* mtspace data structures are built on r-trees. */
@@ -65,7 +67,7 @@ RCSID ("$Id$");
typedef struct mtspacebox
{
const BoxType box;
- BDimension keepaway; /* the smallest keepaway around this box */
+ BDimension keepaway; /* the smallest keepaway around this box */
}
mtspacebox_t;
@@ -77,27 +79,36 @@ struct mtspace
rtree_t *ftree, *etree, *otree;
};
+typedef union
+{
+ vector_t * v;
+ heap_t * h;
+} heap_or_vector;
+
/* this is a vetting_t */
struct vetting
{
- vector_t *untested;
- vector_t *no_fix;
- vector_t *no_hi;
- vector_t *hi_candidate;
+ heap_or_vector untested;
+ heap_or_vector no_fix;
+ heap_or_vector no_hi;
+ heap_or_vector hi_candidate;
BDimension radius;
BDimension keepaway;
+ CheapPointType desired;
};
+#define SPECIAL 823157
+
mtspacebox_t *
mtspace_create_box (const BoxType * box, BDimension keepaway)
{
mtspacebox_t *mtsb;
- assert (__box_is_good (box));
+ assert (box_is_good (box));
mtsb = malloc (sizeof (*mtsb));
- /* expand the box by its keepaway amount */
- *((BoxTypePtr) & mtsb->box) = bloat_box (box, keepaway);
+ /* the box was sent to us pre-bloated by the keepaway amount */
+ *((BoxTypePtr) & mtsb->box) = *box;
mtsb->keepaway = keepaway;
- assert (__box_is_good (&mtsb->box));
+ assert (box_is_good (&mtsb->box));
return mtsb;
}
@@ -143,16 +154,13 @@ mts_remove_one (const BoxType * b, void *cl)
mtspacebox_t *box = (mtspacebox_t *) b;
/* there can be duplicate boxes, we just remove one */
- if (box->keepaway == info->keepaway)
+ /* the info box is pre-bloated, so just check equality */
+ if (b->X1 == info->box.X1 && b->X2 == info->box.X2 &&
+ b->Y1 == info->box.Y1 && b->Y2 == info->box.Y2 &&
+ box->keepaway == info->keepaway)
{
- /* shrink back to original size */
- BoxType sb = shrink_box (b, box->keepaway);
- if (sb.X1 == info->box.X1 && sb.X2 == info->box.X2 &&
- sb.Y1 == info->box.Y1 && sb.Y2 == info->box.Y2)
- {
- r_delete_entry (info->tree, b);
- longjmp (info->env, 1);
- }
+ r_delete_entry (info->tree, b);
+ longjmp (info->env, 1);
}
return 0;
}
@@ -174,7 +182,7 @@ which_tree (mtspace_t * mtspace, mtspace_type_t which)
/* add a space-filler to the empty space representation. */
void
mtspace_add (mtspace_t * mtspace, const BoxType * box, mtspace_type_t which,
- BDimension keepaway)
+ BDimension keepaway)
{
mtspacebox_t *filler = mtspace_create_box (box, keepaway);
r_insert_entry (which_tree (mtspace, which), (const BoxType *) filler, 1);
@@ -183,29 +191,52 @@ mtspace_add (mtspace_t * mtspace, const BoxType * box, mtspace_type_t which,
/* remove a space-filler from the empty space representation. */
void
mtspace_remove (mtspace_t * mtspace,
- const BoxType * box, mtspace_type_t which,
- BDimension keepaway)
+ const BoxType * box, mtspace_type_t which,
+ BDimension keepaway)
{
struct mts_info cl;
+ BoxType small_search;
cl.keepaway = keepaway;
cl.box = *box;
cl.tree = which_tree (mtspace, which);
+ small_search = box_center(box);
if (setjmp (cl.env) == 0)
{
- r_search (cl.tree, box, NULL, mts_remove_one, &cl);
- assert (0); /* didn't find it?? */
+ r_search (cl.tree, &small_search, NULL, mts_remove_one, &cl);
+ assert (0); /* didn't find it?? */
}
}
struct query_closure
{
BoxType *cbox;
- vector_t *vec, *ivec;
+ heap_or_vector checking;
+ heap_or_vector touching;
+ CheapPointType *desired;
BDimension radius, keepaway;
jmp_buf env;
+ Boolean touch_is_vec;
};
+static inline void
+heap_append (heap_t *heap, CheapPointType *desired, BoxType *new)
+{
+ CheapPointType p = *desired;
+ assert (desired);
+ closest_point_in_box (&p, new);
+ heap_insert (heap, ABS(p.X - desired->X) + (p.Y - desired->Y), new);
+}
+
+static inline void
+append (struct query_closure * qc, BoxType *new)
+{
+ if (qc->desired)
+ heap_append (qc->checking.h, qc->desired, new);
+ else
+ vector_append (qc->checking.v, new);
+}
+
/* we found some space filler that may intersect this query.
* First check if it does intersect, then break it into
* overlaping regions that don't intersect this box.
@@ -230,100 +261,119 @@ query_one (const BoxType * box, void *cl)
qc->cbox->Y2 - shrink <= mtsb->box.Y1)
return 0;
/* ok, we do touch this box, now create up to 4 boxes that don't */
- if (mtsb->box.Y1 > qc->cbox->Y1 + shrink) /* top region exists */
+ if (mtsb->box.Y1 > qc->cbox->Y1 + shrink) /* top region exists */
{
int Y1 = qc->cbox->Y1;
int Y2 = mtsb->box.Y1 + shrink;
if (Y2 - Y1 >= 2 * (qc->radius + qc->keepaway))
- {
- BoxType *new = (BoxType *) malloc (sizeof (BoxType));
- new->X1 = qc->cbox->X1;
- new->X2 = qc->cbox->X2;
- new->Y1 = Y1;
- new->Y2 = Y2;
- assert (new->Y2 < qc->cbox->Y2);
- vector_append (qc->vec, new);
- }
+ {
+ BoxType *new = (BoxType *) malloc (sizeof (BoxType));
+ new->X1 = qc->cbox->X1;
+ new->X2 = qc->cbox->X2;
+ new->Y1 = Y1;
+ new->Y2 = Y2;
+ assert (new->Y2 < qc->cbox->Y2);
+ append(qc, new);
+ }
}
- if (mtsb->box.Y2 < qc->cbox->Y2 - shrink) /* bottom region exists */
+ if (mtsb->box.Y2 < qc->cbox->Y2 - shrink) /* bottom region exists */
{
int Y1 = mtsb->box.Y2 - shrink;
int Y2 = qc->cbox->Y2;
if (Y2 - Y1 >= 2 * (qc->radius + qc->keepaway))
- {
- BoxType *new = (BoxType *) malloc (sizeof (BoxType));
- new->X1 = qc->cbox->X1;
- new->X2 = qc->cbox->X2;
- new->Y2 = qc->cbox->Y2;
- new->Y1 = mtsb->box.Y2 - shrink;
- assert (new->Y1 > qc->cbox->Y1);
- vector_append (qc->vec, new);
- }
+ {
+ BoxType *new = (BoxType *) malloc (sizeof (BoxType));
+ new->X1 = qc->cbox->X1;
+ new->X2 = qc->cbox->X2;
+ new->Y2 = qc->cbox->Y2;
+ new->Y1 = Y1;
+ assert (new->Y1 > qc->cbox->Y1);
+ append (qc, new);
+ }
}
- if (mtsb->box.X1 > qc->cbox->X1 + shrink) /* left region exists */
+ if (mtsb->box.X1 > qc->cbox->X1 + shrink) /* left region exists */
{
int X1 = qc->cbox->X1;
int X2 = mtsb->box.X1 + shrink;
if (X2 - X1 >= 2 * (qc->radius + qc->keepaway))
- {
- BoxType *new;
- new = (BoxType *) malloc (sizeof (BoxType));
- new->Y1 = qc->cbox->Y1;
- new->Y2 = qc->cbox->Y2;
- new->X1 = qc->cbox->X1;
- new->X2 = mtsb->box.X1 + shrink;
- assert (new->X2 < qc->cbox->X2);
- vector_append (qc->vec, new);
- }
+ {
+ BoxType *new;
+ new = (BoxType *) malloc (sizeof (BoxType));
+ new->Y1 = qc->cbox->Y1;
+ new->Y2 = qc->cbox->Y2;
+ new->X1 = qc->cbox->X1;
+ new->X2 = X2;
+ assert (new->X2 < qc->cbox->X2);
+ append (qc, new);
+ }
}
- if (mtsb->box.X2 < qc->cbox->X2 - shrink) /* right region exists */
+ if (mtsb->box.X2 < qc->cbox->X2 - shrink) /* right region exists */
{
int X1 = mtsb->box.X2 - shrink;
int X2 = qc->cbox->X2;
if (X2 - X1 >= 2 * (qc->radius + qc->keepaway))
- {
- BoxType *new = (BoxType *) malloc (sizeof (BoxType));
- new->Y1 = qc->cbox->Y1;
- new->Y2 = qc->cbox->Y2;
- new->X2 = qc->cbox->X2;
- new->X1 = mtsb->box.X2 - shrink;
- assert (new->X1 > qc->cbox->X1);
- vector_append (qc->vec, new);
- }
+ {
+ BoxType *new = (BoxType *) malloc (sizeof (BoxType));
+ new->Y1 = qc->cbox->Y1;
+ new->Y2 = qc->cbox->Y2;
+ new->X2 = qc->cbox->X2;
+ new->X1 = X1;
+ assert (new->X1 > qc->cbox->X1);
+ append (qc, new);
+ }
}
- if (qc->ivec)
+ if (qc->touching.v)
{
- vector_append (qc->ivec, qc->cbox);
+ if (qc->touch_is_vec || !qc->desired)
+ vector_append (qc->touching.v, qc->cbox);
+ else
+ heap_append (qc->touching.h, qc->desired, qc->cbox);
}
else
- free (qc->cbox); /* done with this one */
+ free (qc->cbox); /* done with this one */
longjmp (qc->env, 1);
- return 1; /* never reached */
+ return 1; /* never reached */
}
-void
-qloop (struct query_closure *qc, rtree_t * tree, vector_t * res)
+/* qloop takes a vector (or heap) of regions to check (checking) if they don't intersect
+ * anything. If a region does intersect something, it is broken into
+ * pieces that don't intersect that thing (if possible) which are
+ * put back into the vector/heap of regions to check.
+ * qloop returns False when it finds the first empty region
+ * it returns True if it has exhausted the region vector/heap and never
+ * found an empty area.
+ */
+static void
+qloop (struct query_closure *qc, rtree_t * tree, heap_or_vector res, Boolean is_vec)
{
BoxType *cbox;
#ifndef NDEBUG
int n;
#endif
- while (!vector_is_empty (qc->vec))
+ while (!(qc->desired ? heap_is_empty (qc->checking.h) : vector_is_empty (qc->checking.v)))
{
- cbox = vector_remove_last (qc->vec);
+ cbox = qc->desired ? heap_remove_smallest (qc->checking.h) : vector_remove_last (qc->checking.v);
if (setjmp (qc->env) == 0)
- {
- assert (__box_is_good (cbox));
- qc->cbox = cbox;
+ {
+ assert (box_is_good (cbox));
+ qc->cbox = cbox;
#ifndef NDEBUG
- n =
+ n =
#endif
- r_search (tree, cbox, NULL, query_one, qc);
- assert (n == 0);
- /* nothing intersected with this tree, put it in the result vector */
- vector_append (res, cbox);
- return; /* found one - perhaps one answer is good enough */
- }
+ r_search (tree, cbox, NULL, query_one, qc);
+ assert (n == 0);
+ /* nothing intersected with this tree, put it in the result vector */
+ if (is_vec)
+ vector_append (res.v, cbox);
+ else
+ {
+ if (qc->desired)
+ heap_append (res.h, qc->desired, cbox);
+ else
+ vector_append (res.v, cbox);
+ }
+ return; /* found one - perhaps one answer is good enough */
+ }
}
}
@@ -332,18 +382,32 @@ void
mtsFreeWork (vetting_t ** w)
{
vetting_t *work = (*w);
- while (!vector_is_empty (work->untested))
- free (vector_remove_last (work->untested));
- vector_destroy (&work->untested);
- while (!vector_is_empty (work->no_fix))
- free (vector_remove_last (work->no_fix));
- vector_destroy (&work->no_fix);
- while (!vector_is_empty (work->no_hi))
- free (vector_remove_last (work->no_hi));
- vector_destroy (&work->no_hi);
- while (!vector_is_empty (work->hi_candidate))
- free (vector_remove_last (work->hi_candidate));
- vector_destroy (&work->hi_candidate);
+ if (work->desired.X != -SPECIAL || work->desired.Y != -SPECIAL)
+ {
+ heap_free (work->untested.h, free);
+ heap_destroy (&work->untested.h);
+ heap_free (work->no_fix.h, free);
+ heap_destroy (&work->no_fix.h);
+ heap_free (work->no_hi.h, free);
+ heap_destroy (&work->no_hi.h);
+ heap_free (work->hi_candidate.h, free);
+ heap_destroy (&work->hi_candidate.h);
+ }
+ else
+ {
+ while (!vector_is_empty (work->untested.v))
+ free (vector_remove_last (work->untested.v));
+ vector_destroy (&work->untested.v);
+ while (!vector_is_empty (work->no_fix.v))
+ free (vector_remove_last (work->no_fix.v));
+ vector_destroy (&work->no_fix.v);
+ while (!vector_is_empty (work->no_hi.v))
+ free (vector_remove_last (work->no_hi.v));
+ vector_destroy (&work->no_hi.v);
+ while (!vector_is_empty (work->hi_candidate.v))
+ free (vector_remove_last (work->hi_candidate.v));
+ vector_destroy (&work->hi_candidate.v);
+ }
free (work);
(*w) = NULL;
}
@@ -366,100 +430,148 @@ mtsFreeWork (vetting_t ** w)
*/
vetting_t *
mtspace_query_rect (mtspace_t * mtspace, const BoxType * region,
- BDimension radius, BDimension keepaway,
- vetting_t * work,
- vector_t * free_space_vec,
- vector_t * lo_conflict_space_vec,
- vector_t * hi_conflict_space_vec,
- Boolean is_odd, Boolean with_conflicts)
+ BDimension radius, BDimension keepaway,
+ vetting_t * work,
+ vector_t * free_space_vec,
+ vector_t * lo_conflict_space_vec,
+ vector_t * hi_conflict_space_vec,
+ Boolean is_odd, Boolean with_conflicts, CheapPointType *desired)
{
struct query_closure qc;
/* pre-assertions */
- assert (__box_is_good (region));
- assert (free_space_vec && vector_is_empty (free_space_vec));
- assert (lo_conflict_space_vec && vector_is_empty (lo_conflict_space_vec));
- assert (hi_conflict_space_vec && vector_is_empty (hi_conflict_space_vec));
+ assert (free_space_vec);
+ assert (lo_conflict_space_vec);
+ assert (hi_conflict_space_vec);
/* search out to anything that might matter */
if (region)
{
BoxType *cbox;
assert (work == NULL);
+ assert (box_is_good (region));
+ assert(vector_is_empty (free_space_vec));
+ assert(vector_is_empty (lo_conflict_space_vec));
+ assert(vector_is_empty (hi_conflict_space_vec));
work = (vetting_t *) malloc (sizeof (vetting_t));
- work->untested = vector_create ();
- work->no_fix = vector_create ();
- work->hi_candidate = vector_create ();
- work->no_hi = vector_create ();
work->keepaway = keepaway;
work->radius = radius;
- assert (work->untested && work->no_fix &&
- work->no_hi && work->hi_candidate);
cbox = (BoxType *) malloc (sizeof (BoxType));
*cbox = bloat_box (region, keepaway + radius);
- vector_append (work->untested, cbox);
+ if (desired)
+ {
+ work->untested.h = heap_create ();
+ work->no_fix.h = heap_create ();
+ work->hi_candidate.h = heap_create ();
+ work->no_hi.h =heap_create ();
+ assert (work->untested.h && work->no_fix.h &&
+ work->no_hi.h && work->hi_candidate.h);
+ heap_insert (work->untested.h, 0, cbox);
+ work->desired = *desired;
+ }
+ else
+ {
+ work->untested.v = vector_create ();
+ work->no_fix.v = vector_create ();
+ work->hi_candidate.v = vector_create ();
+ work->no_hi.v = vector_create ();
+ assert (work->untested.v && work->no_fix.v &&
+ work->no_hi.v && work->hi_candidate.v);
+ vector_append (work->untested.v, cbox);
+ work->desired.X = work->desired.Y = -SPECIAL;
+ }
return work;
}
qc.keepaway = work->keepaway;
qc.radius = work->radius;
+ if (work->desired.X == -SPECIAL && work->desired.Y == -SPECIAL)
+ qc.desired = NULL;
+ else
+ qc.desired = &work->desired;
/* do the query */
do
{
/* search the fixed object tree discarding any intersections
* and placing empty regions in the no_fix vector.
*/
- qc.vec = work->untested;
- qc.ivec = NULL;
- qloop (&qc, mtspace->ftree, work->no_fix);
+ qc.checking = work->untested;
+ qc.touching.v = NULL;
+ qloop (&qc, mtspace->ftree, work->no_fix, False);
/* search the hi-conflict tree placing intersectors in the
* hi_candidate vector (if conflicts are allowed) and
* placing empty regions in the no_hi vector.
*/
- qc.vec = work->no_fix;
- qc.ivec = with_conflicts ? work->hi_candidate : NULL;
- qloop (&qc, is_odd ? mtspace->otree : mtspace->etree, work->no_hi);
+ qc.checking.v = work->no_fix.v;
+ qc.touching.v = with_conflicts ? work->hi_candidate.v : NULL;
+ qc.touch_is_vec = False;
+ qloop (&qc, is_odd ? mtspace->otree : mtspace->etree, work->no_hi, False);
/* search the lo-conflict tree placing intersectors in the
* lo-conflict answer vector (if conflicts allowed) and
* placing emptry regions in the free-space answer vector.
*/
- qc.vec = work->no_hi;
- qc.ivec = with_conflicts ? lo_conflict_space_vec : NULL;
- qloop (&qc, is_odd ? mtspace->etree : mtspace->otree, free_space_vec);
+ qc.checking = work->no_hi;
+/* XXX lo_conflict_space_vec will be treated like a heap! */
+ qc.touching.v = (with_conflicts ? lo_conflict_space_vec : NULL);
+ qc.touch_is_vec = True;
+ qloop (&qc, is_odd ? mtspace->etree : mtspace->otree, (heap_or_vector)free_space_vec, True);
if (!vector_is_empty (free_space_vec))
- {
- if (vector_is_empty (work->untested))
- break;
+ {
+ if (qc.desired)
+ {
+ if (heap_is_empty (work->untested.h))
+ break;
+ }
else
- return work;
- }
+ {
+ if (vector_is_empty (work->untested.v))
+ break;
+ }
+ return work;
+ }
/* finally check the hi-conflict intersectors against the
* lo-conflict tree discarding intersectors (two types of conflict is real bad)
* and placing empty regions in the hi-conflict answer vector.
*/
if (with_conflicts)
- {
- qc.vec = work->hi_candidate;
- qc.ivec = NULL;
- qloop (&qc, is_odd ? mtspace->etree : mtspace->otree,
- hi_conflict_space_vec);
- }
+ {
+ qc.checking = work->hi_candidate;
+ qc.touching.v = NULL;
+ qloop (&qc, is_odd ? mtspace->etree : mtspace->otree,
+ (heap_or_vector)hi_conflict_space_vec, True);
+ }
}
- while (!vector_is_empty (work->untested));
- if (vector_is_empty (work->no_fix) &&
- vector_is_empty (work->no_hi) && vector_is_empty (work->hi_candidate))
+ while (!(qc.desired ? heap_is_empty(work->untested.h) : vector_is_empty (work->untested.v)));
+ if (qc.desired)
{
- mtsFreeWork (&work);
- return NULL;
+ if (heap_is_empty (work->no_fix.h) &&
+ heap_is_empty (work->no_hi.h) &&
+ heap_is_empty (work->hi_candidate.h))
+ {
+ mtsFreeWork (&work);
+ return NULL;
+ }
}
+ else
+ {
+ if (vector_is_empty (work->no_fix.v) &&
+ vector_is_empty (work->no_hi.v) && vector_is_empty (work->hi_candidate.v))
+ {
+ mtsFreeWork (&work);
+ return NULL;
+ }
+ }
return work;
}
int
mtsBoxCount (vetting_t * w)
{
+#if 0
int ans;
ans = 3 * vector_size (w->untested);
ans += 2 * vector_size (w->no_fix);
ans += vector_size (w->no_hi);
ans += vector_size (w->hi_candidate);
return ans;
+#endif
+ return 100;
}
diff --git a/src/mtspace.h b/src/mtspace.h
index 33157aa..4e6eb8e 100644
--- a/src/mtspace.h
+++ b/src/mtspace.h
@@ -76,7 +76,8 @@ vetting_t *mtspace_query_rect (mtspace_t * mtspace, const BoxType * region,
vector_t * free_space_vec,
vector_t * lo_conflict_space_vec,
vector_t * hi_conflict_space_vec,
- Boolean is_odd, Boolean with_conflicts);
+ Boolean is_odd, Boolean with_conflicts,
+ CheapPointType *desired);
void mtsFreeWork (vetting_t **);
int mtsBoxCount (vetting_t *);
diff --git a/src/rtree.c b/src/rtree.c
index 19741e4..aa5b41a 100644
--- a/src/rtree.c
+++ b/src/rtree.c
@@ -65,6 +65,7 @@ RCSID ("$Id$");
#define SLOW_ASSERTS
/* All rectangles are closed on the bottom left and open on the
* top right. i.e. they contain one corner point, but not the other.
+ * This requires that the corner points not be equal!
*/
/* the number of entries in each rtree node
@@ -517,7 +518,7 @@ __r_search (struct rtree_node *node, const BoxType * query, r_arg * arg)
{
assert (node);
/** assert that starting_region is well formed */
- assert (query->X1 <= query->X2 && query->Y1 <= query->Y2);
+ assert (query->X1 < query->X2 && query->Y1 < query->Y2);
assert (node->box.X1 < query->X2 && node->box.X2 > query->X1 &&
node->box.Y1 < query->Y2 && node->box.Y2 > query->Y1);
#ifdef SLOW_ASSERTS
@@ -609,8 +610,11 @@ r_search (rtree_t * rtree, const BoxType * query,
return 0;
if (query)
{
-#if DEBUG
- if (query->X2 < query->X1 || query->Y2 < query->Y1)
+#ifdef SLOW_ASSERTS
+ assert (__r_tree_is_good (rtree->root));
+#endif
+#ifdef DEBUG
+ if (query->X2 <= query->X1 || query->Y2 <= query->Y1)
return 0;
#endif
/* check this box. If it's not touched we're done here */
@@ -1035,7 +1039,7 @@ r_insert_entry (rtree_t * rtree, const BoxType * which, int man)
}
Boolean
-__r_delete (rtree_t * seed, struct rtree_node *node, const BoxType * query)
+__r_delete (struct rtree_node *node, const BoxType * query)
{
int i, flag, mask, a;
@@ -1069,7 +1073,7 @@ __r_delete (rtree_t * seed, struct rtree_node *node, const BoxType * query)
node->u.rects[i].bptr = NULL;
return True;
}
- return (__r_delete (seed, node->parent, &node->box));
+ return (__r_delete (node->parent, &node->box));
}
else
/* propegate boundary adjust upward */
@@ -1082,7 +1086,7 @@ __r_delete (rtree_t * seed, struct rtree_node *node, const BoxType * query)
}
if (node->u.kids[i])
{
- if (__r_delete (seed, node->u.kids[i], query))
+ if (__r_delete (node->u.kids[i], query))
return True;
}
else
@@ -1128,7 +1132,7 @@ __r_delete (rtree_t * seed, struct rtree_node *node, const BoxType * query)
if (!node->u.rects[0].bptr)
{
if (node->parent)
- __r_delete (seed, node->parent, &node->box);
+ __r_delete (node->parent, &node->box);
return True;
}
else
@@ -1148,7 +1152,7 @@ r_delete_entry (rtree_t * rtree, const BoxType * box)
assert (box);
assert (rtree);
- r = __r_delete (rtree, rtree->root, box);
+ r = __r_delete (rtree->root, box);
if (r)
rtree->size--;
#ifdef SLOW_ASSERTS
diff --git a/src/vector.c b/src/vector.c
index 1786607..169afd3 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -199,6 +199,20 @@ vector_insert_many (vector_t * vector, int N,
assert (__vector_is_good (vector));
}
+vector_t *
+vector_duplicate (vector_t * orig)
+{
+ vector_t * new = vector_create();
+ if (!orig)
+ return new;
+ new->element = malloc (orig->max * sizeof (*orig->element));
+ new->max = orig->max;
+ new->size = orig->size;
+ memcpy (new->element, orig->element, orig->size * sizeof (vector_element_t));
+ assert (__vector_is_good (new));
+ return new;
+}
+
/* return and delete the *last* element of vector */
vector_element_t
vector_remove_last (vector_t * vector)
diff --git a/src/vector.h b/src/vector.h
index 957f524..3eabef5 100644
--- a/src/vector.h
+++ b/src/vector.h
@@ -46,6 +46,8 @@ typedef void *vector_element_t;
vector_t *vector_create ();
/* destroy a vector */
void vector_destroy (vector_t ** vector);
+/* copy a vector */
+vector_t *vector_duplicate (vector_t * vector);
/* -- interrogation -- */
int vector_is_empty (vector_t * vector);
_______________________________________________
geda-cvs mailing list
geda-cvs@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-cvs