HID: Move non-PCB specific drawing calls into a separate API
[geda-pcb/pcjc2.git] / src / autoroute.c
bloba2a64c64fe49f31a4e49d4b1f399e2fd826e134d
1 /*
2 * COPYRIGHT
4 * PCB, interactive printed circuit board design
5 * Copyright (C) 1994,1995,1996 Thomas Nau
6 * Copyright (C) 1998,1999,2000,2001 harry eaton
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 * Contact addresses for paper mail and Email:
23 * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
24 * haceaton@aplcomm.jhuapl.edu
27 /* this file, autoroute.c, was written and is
28 * Copyright (c) 2001 C. Scott Ananian
29 * Copyright (c) 2006 harry eaton
30 * Copyright (c) 2009 harry eaton
32 /* functions used to autoroute nets.
35 *-------------------------------------------------------------------
36 * This file implements a rectangle-expansion router, based on
37 * "A Method for Gridless Routing of Printed Circuit Boards" by
38 * A. C. Finch, K. J. Mackenzie, G. J. Balsdon, and G. Symonds in the
39 * 1985 Proceedings of the 22nd ACM/IEEE Design Automation Conference.
40 * This reference is available from the ACM Digital Library at
41 * http://www.acm.org/dl for those with institutional or personal
42 * access to it. It's also available from your local engineering
43 * library.
45 * The code is much closer to what is described in the paper now,
46 * in that expansion areas can grow from corners and in all directions
47 * at once. Previously, these were emulated with discrete boxes moving
48 * in the cardinal directions. With the new method, there are fewer but
49 * larger expansion boxes that one might do a better job of routing in.
50 *--------------------------------------------------------------------
52 #define NET_HEAP 1
53 #ifdef HAVE_CONFIG_H
54 #include "config.h"
55 #endif
57 #include "global.h"
59 #include <assert.h>
60 #include <setjmp.h>
62 #include "data.h"
63 #include "macro.h"
64 #include "autoroute.h"
65 #include "box.h"
66 #include "create.h"
67 #include "draw.h"
68 #include "error.h"
69 #include "find.h"
70 #include "heap.h"
71 #include "rtree.h"
72 #include "misc.h"
73 #include "mtspace.h"
74 #include "mymem.h"
75 #include "polygon.h"
76 #include "rats.h"
77 #include "remove.h"
78 #include "thermal.h"
79 #include "undo.h"
80 #include "vector.h"
81 #include "pcb-printf.h"
83 #ifdef HAVE_LIBDMALLOC
84 #include <dmalloc.h>
85 #endif
87 /* #defines to enable some debugging output */
89 #define ROUTE_VERBOSE
93 #define ROUTE_DEBUG
94 //#define DEBUG_SHOW_ROUTE_BOXES
95 #define DEBUG_SHOW_EXPANSION_BOXES
96 //#define DEBUG_SHOW_EDGES
97 //#define DEBUG_SHOW_VIA_BOXES
98 #define DEBUG_SHOW_TARGETS
99 #define DEBUG_SHOW_SOURCES
100 //#define DEBUG_SHOW_ZIGZAG
103 static direction_t
104 directionIncrement(direction_t dir)
106 switch(dir)
108 case NORTH:
109 dir = EAST;
110 break;
111 case EAST:
112 dir = SOUTH;
113 break;
114 case SOUTH:
115 dir = WEST;
116 break;
117 case WEST:
118 dir = NE;
119 break;
120 case NE:
121 dir = SE;
122 break;
123 case SE:
124 dir = SW;
125 break;
126 case SW:
127 dir = NW;
128 break;
129 case NW:
130 dir = ALL;
131 break;
132 case ALL:
133 dir = NORTH;
134 break;
136 return dir;
139 #ifdef ROUTE_DEBUG
140 HID *ddraw = NULL;
141 static hidGC ar_gc = 0;
142 #endif
144 #define EXPENSIVE 3e28
145 /* round up "half" thicknesses */
146 #define HALF_THICK(x) (((x)+1)/2)
147 /* a styles maximum bloat is its keepaway plus the larger of its via radius
148 * or line half-thickness. */
149 #define BLOAT(style)\
150 ((style)->Keepaway + HALF_THICK((style)->Thick))
151 /* conflict penalty is less for traces laid down during previous pass than
152 * it is for traces already laid down in this pass. */
153 #define CONFLICT_LEVEL(rb)\
154 (((rb)->flags.is_odd==AutoRouteParameters.is_odd) ?\
155 HI_CONFLICT : LO_CONFLICT )
156 #define CONFLICT_PENALTY(rb)\
157 ((CONFLICT_LEVEL(rb)==HI_CONFLICT ? \
158 AutoRouteParameters.ConflictPenalty : \
159 CONFLICT_LEVEL(rb)==LO_CONFLICT ? \
160 AutoRouteParameters.LastConflictPenalty : 1) * (rb)->pass)
162 #define _NORTH 1
163 #define _EAST 2
164 #define _SOUTH 4
165 #define _WEST 8
167 #define LIST_LOOP(init, which, x) do {\
168 routebox_t *__next_one__ = (init);\
169 x = NULL;\
170 if (!__next_one__)\
171 assert(__next_one__);\
172 else\
173 while (!x || __next_one__ != (init)) {\
174 x = __next_one__;\
175 /* save next one first in case the command modifies or frees it */\
176 __next_one__ = x->which.next
177 #define FOREACH_SUBNET(net, p) do {\
178 routebox_t *_pp_;\
179 /* fail-fast: check subnet_processed flags */\
180 LIST_LOOP(net, same_net, p); \
181 assert(!p->flags.subnet_processed);\
182 END_LOOP;\
183 /* iterate through *distinct* subnets */\
184 LIST_LOOP(net, same_net, p); \
185 if (!p->flags.subnet_processed) {\
186 LIST_LOOP(p, same_subnet, _pp_);\
187 _pp_->flags.subnet_processed=1;\
188 END_LOOP
189 #define END_FOREACH(net, p) \
190 }; \
191 END_LOOP;\
192 /* reset subnet_processed flags */\
193 LIST_LOOP(net, same_net, p); \
194 p->flags.subnet_processed=0;\
195 END_LOOP;\
196 } while (0)
197 #define SWAP(t, f, s) do { t a=s; s=f; f=a; } while (0)
198 /* notes:
199 * all rectangles are assumed to be closed on the top and left and
200 * open on the bottom and right. That is, they include their top-left
201 * corner but don't include their bottom and right edges.
203 * expansion regions are always half-closed. This means that when
204 * tracing paths, you must steer clear of the bottom and right edges.,
205 * because these are not actually in the allowed box.
207 * All routeboxes *except* EXPANSION_AREAS now have their "box" bloated by
208 * their particular required keepaway. This simplifies the tree searching.
209 * the "sbox" contains the unbloated box.
211 /* ---------------------------------------------------------------------------
212 * some local types
215 /* enumerated type for conflict levels */
216 typedef enum
217 { NO_CONFLICT = 0, LO_CONFLICT = 1, HI_CONFLICT = 2 }
218 conflict_t;
220 typedef struct routebox_list
222 struct routebox *next, *prev;
223 }routebox_list;
225 typedef enum etype
226 { PAD, PIN, VIA, VIA_SHADOW, LINE, OTHER, EXPANSION_AREA, PLANE, THERMAL }
227 etype;
229 typedef struct routebox
231 BoxType box, sbox;
232 union
234 PadType *pad;
235 PinType *pin;
236 PinType *via;
237 struct routebox *via_shadow; /* points to the via in r-tree which
238 * points to the PinType in the PCB. */
239 LineType *line;
240 void *generic; /* 'other' is polygon, arc, text */
241 struct routebox *expansion_area; /* previous expansion area in search */
243 parent;
244 unsigned short group;
245 unsigned short layer;
246 etype type;
247 struct
249 unsigned nonstraight:1;
250 unsigned fixed:1;
251 /* for searches */
252 unsigned source:1;
253 unsigned target:1;
254 /* rects on same net as source and target don't need clearance areas */
255 unsigned nobloat:1;
256 /* mark circular pins, so that we be sure to connect them up properly */
257 unsigned circular:1;
258 /* we sometimes create routeboxen that don't actually belong to a
259 * r-tree yet -- make sure refcount of homelesss is set properly */
260 unsigned homeless:1;
261 /* was this nonfixed obstacle generated on an odd or even pass? */
262 unsigned is_odd:1;
263 /* fixed route boxes that have already been "routed through" in this
264 * search have their "touched" flag set. */
265 unsigned touched:1;
266 /* this is a status bit for iterating through *different* subnets */
267 unsigned subnet_processed:1;
268 /* some expansion_areas represent via candidates */
269 unsigned is_via:1;
270 /* mark non-straight lines which go from bottom-left to upper-right,
271 * instead of from upper-left to bottom-right. */
272 unsigned bl_to_ur:1;
273 /* mark polygons which are "transparent" for via-placement; that is,
274 * vias through the polygon will automatically be given a keepaway
275 * and will not electrically connect to the polygon. */
276 unsigned clear_poly:1;
277 /* this marks "conflicting" routes that must be torn up to obtain
278 * a correct routing. This flag allows us to return a correct routing
279 * even if the user cancels auto-route after a non-final pass. */
280 unsigned is_bad:1;
281 /* for assertion that 'box' is never changed after creation */
282 unsigned inited:1;
283 /* indicate this expansion ares is a thermal between the pin and plane */
284 unsigned is_thermal;
286 flags;
287 /* indicate the direction an expansion box came from */
288 cost_t cost;
289 CheapPointType cost_point;
290 /* reference count for homeless routeboxes; free when refcount==0 */
291 int refcount;
292 /* when routing with conflicts, we keep a record of what we're
293 * conflicting with.
295 vector_t *conflicts_with;
296 /* route style of the net associated with this routebox */
297 RouteStyleType *style;
298 /* congestion values for the edges of an expansion box */
299 unsigned char n, e, s, w;
300 /* what pass this this track was laid down on */
301 unsigned char pass;
302 /* the direction this came from, if any */
303 direction_t came_from;
304 /* circular lists with connectivity information. */
305 routebox_list same_net, same_subnet, original_subnet, different_net;
306 union {
307 PinType *via;
308 LineType *line;
309 } livedraw_obj;
311 routebox_t;
313 typedef struct routedata
315 /* one rtree per layer *group */
316 rtree_t *layergrouptree[MAX_LAYER]; /* no silkscreen layers here =) */
317 /* root pointer into connectivity information */
318 routebox_t *first_net;
319 /* default routing style */
320 RouteStyleType defaultstyle;
321 /* style structures */
322 RouteStyleType *styles[NUM_STYLES + 1];
323 /* what is the maximum bloat (keepaway+line half-width or
324 * keepaway+via_radius) for any style we've seen? */
325 Coord max_bloat;
326 Coord max_keep;
327 mtspace_t *mtspace;
329 routedata_t;
331 typedef struct edge_struct
333 routebox_t *rb; /* path expansion edges are real routeboxen. */
334 CheapPointType cost_point;
335 cost_t cost_to_point; /* from source */
336 cost_t cost; /* cached edge cost */
337 routebox_t *mincost_target; /* minimum cost from cost_point to any target */
338 vetting_t *work; /* for via search edges */
339 direction_t expand_dir;
340 struct
342 /* this indicates that this 'edge' is a via candidate. */
343 unsigned is_via:1;
344 /* record "conflict level" of via candidates, in case we need to split
345 * them later. */
346 conflict_t via_conflict_level:2;
347 /* when "routing with conflicts", sometimes edge is interior. */
348 unsigned is_interior:1;
349 /* this is a fake edge used to defer searching for via spaces */
350 unsigned via_search:1;
351 /* this is a via edge in a plane where the cost point moves for free */
352 unsigned in_plane:1;
354 flags;
356 edge_t;
358 static struct
360 /* net style parameters */
361 RouteStyleType *style;
362 /* the present bloat */
363 Coord bloat;
364 /* cost parameters */
365 cost_t ViaCost, /* additional "length" cost for using a via */
366 LastConflictPenalty, /* length mult. for routing over last pass' trace */
367 ConflictPenalty, /* length multiplier for routing over another trace */
368 JogPenalty, /* additional "length" cost for changing direction */
369 CongestionPenalty, /* (rational) length multiplier for routing in */
370 NewLayerPenalty, /* penalty for routing on a previously unused layer */
371 MinPenalty; /* smallest Direction Penalty */
372 /* maximum conflict incidence before calling it "no path found" */
373 int hi_conflict;
374 /* are vias allowed? */
375 bool use_vias;
376 /* is this an odd or even pass? */
377 bool is_odd;
378 /* permit conflicts? */
379 bool with_conflicts;
380 /* is this a final "smoothing" pass? */
381 bool is_smoothing;
382 /* rip up nets regardless of conflicts? */
383 bool rip_always;
384 bool last_smooth;
385 unsigned char pass;
387 AutoRouteParameters;
389 struct routeone_state
391 /* heap of all candidate expansion edges */
392 heap_t *workheap;
393 /* information about the best path found so far. */
394 routebox_t *best_path, *best_target;
395 cost_t best_cost;
399 /* ---------------------------------------------------------------------------
400 * some local prototypes
402 static routebox_t *CreateExpansionArea (const BoxType * area, Cardinal group,
403 routebox_t * parent,
404 bool relax_edge_requirements,
405 edge_t * edge);
407 static cost_t edge_cost (const edge_t * e, const cost_t too_big);
408 static void best_path_candidate (struct routeone_state *s,
409 edge_t * e, routebox_t * best_target);
411 static BoxType edge_to_box (const routebox_t * rb, direction_t expand_dir);
413 static void add_or_destroy_edge (struct routeone_state *s, edge_t * e);
415 static void
416 RD_DrawThermal (routedata_t * rd, Coord X, Coord Y,
417 Cardinal group, Cardinal layer, routebox_t * subnet,
418 bool is_bad);
419 static void ResetSubnet (routebox_t * net);
420 #ifdef ROUTE_DEBUG
421 static int showboxen = -2;
422 static int aabort = 0;
423 static void showroutebox (routebox_t * rb);
424 #endif
426 /* ---------------------------------------------------------------------------
427 * some local identifiers
429 /* group number of groups that hold surface mount pads */
430 static Cardinal front, back;
431 static bool usedGroup[MAX_LAYER];
432 static int x_cost[MAX_LAYER], y_cost[MAX_LAYER];
433 static bool is_layer_group_active[MAX_LAYER];
434 static int ro = 0;
435 static int smoothes = 1;
436 static int passes = 12;
437 static int routing_layers = 0;
438 static float total_wire_length = 0;
439 static int total_via_count = 0;
441 /* assertion helper for routeboxen */
442 #ifndef NDEBUG
443 static int
444 __routebox_is_good (routebox_t * rb)
446 assert (rb && (rb->group < max_group) &&
447 (rb->box.X1 <= rb->box.X2) && (rb->box.Y1 <= rb->box.Y2) &&
448 (rb->flags.homeless ?
449 (rb->box.X1 != rb->box.X2) || (rb->box.Y1 != rb->box.Y2) :
450 (rb->box.X1 != rb->box.X2) && (rb->box.Y1 != rb->box.Y2)));
451 assert ((rb->flags.source ? rb->flags.nobloat : 1) &&
452 (rb->flags.target ? rb->flags.nobloat : 1) &&
453 (rb->flags.homeless ? !rb->flags.touched : rb->refcount == 0) &&
454 (rb->flags.touched ? rb->type != EXPANSION_AREA : 1));
455 assert ((rb->flags.is_odd ? (!rb->flags.fixed) &&
456 (rb->type == VIA || rb->type == VIA_SHADOW || rb->type == LINE
457 || rb->type == PLANE) : 1));
458 assert (rb->flags.clear_poly ?
459 ((rb->type == OTHER || rb->type == PLANE) && rb->flags.fixed
460 && !rb->flags.homeless) : 1);
461 assert (rb->flags.inited);
462 /* run through conflict list showing none are homeless, targets or sources */
463 if (rb->conflicts_with)
465 int i;
466 for (i = 0; i < vector_size (rb->conflicts_with); i++)
468 routebox_t *c = vector_element (rb->conflicts_with, i);
469 assert (!c->flags.homeless && !c->flags.source && !c->flags.target
470 && !c->flags.fixed);
473 assert (rb->style != NULL && rb->style != NULL);
474 assert (rb->type == EXPANSION_AREA
475 || (rb->same_net.next && rb->same_net.prev && rb->same_subnet.next
476 && rb->same_subnet.prev && rb->original_subnet.next
477 && rb->original_subnet.prev && rb->different_net.next
478 && rb->different_net.prev));
479 return 1;
481 static int
482 __edge_is_good (edge_t * e)
484 assert (e && e->rb && __routebox_is_good (e->rb));
485 assert ((e->rb->flags.homeless ? e->rb->refcount > 0 : 1));
486 assert ((0 <= e->expand_dir) && (e->expand_dir < 9)
487 && (e->flags.
488 is_interior ? (e->expand_dir == ALL
489 && e->rb->conflicts_with) : 1));
490 assert ((e->flags.is_via ? e->rb->flags.is_via : 1)
491 && (e->flags.via_conflict_level >= 0
492 && e->flags.via_conflict_level <= 2)
493 && (e->flags.via_conflict_level != 0 ? e->flags.is_via : 1));
494 assert ((e->cost_to_point >= 0) && e->cost >= 0);
495 return 1;
499 no_planes (const BoxType * b, void *cl)
501 routebox_t *rb = (routebox_t *) b;
502 if (rb->type == PLANE)
503 return 0;
504 return 1;
506 #endif /* !NDEBUG */
508 /*---------------------------------------------------------------------
509 * route utility functions.
512 enum boxlist
513 { NET, SUBNET, ORIGINAL, DIFFERENT_NET };
514 static struct routebox_list *
515 __select_list (routebox_t * r, enum boxlist which)
517 assert (r);
518 switch (which)
520 default:
521 assert (0);
522 case NET:
523 return &(r->same_net);
524 case SUBNET:
525 return &(r->same_subnet);
526 case ORIGINAL:
527 return &(r->original_subnet);
528 case DIFFERENT_NET:
529 return &(r->different_net);
532 static void
533 InitLists (routebox_t * r)
535 static enum boxlist all[] =
536 { NET, SUBNET, ORIGINAL, DIFFERENT_NET }
537 , *p;
538 for (p = all; p < all + (sizeof (all) / sizeof (*p)); p++)
540 struct routebox_list *rl = __select_list (r, *p);
541 rl->prev = rl->next = r;
545 static void
546 MergeNets (routebox_t * a, routebox_t * b, enum boxlist which)
548 struct routebox_list *al, *bl, *anl, *bnl;
549 routebox_t *an, *bn;
550 assert (a && b);
551 assert (a != b);
552 assert (a->type != EXPANSION_AREA);
553 assert (b->type != EXPANSION_AREA);
554 al = __select_list (a, which);
555 bl = __select_list (b, which);
556 assert (al && bl);
557 an = al->next;
558 bn = bl->next;
559 assert (an && bn);
560 anl = __select_list (an, which);
561 bnl = __select_list (bn, which);
562 assert (anl && bnl);
563 bl->next = an;
564 anl->prev = b;
565 al->next = bn;
566 bnl->prev = a;
569 static void
570 RemoveFromNet (routebox_t * a, enum boxlist which)
572 struct routebox_list *al, *anl, *apl;
573 routebox_t *an, *ap;
574 assert (a);
575 al = __select_list (a, which);
576 assert (al);
577 an = al->next;
578 ap = al->prev;
579 if (an == a || ap == a)
580 return; /* not on any list */
581 assert (an && ap);
582 anl = __select_list (an, which);
583 apl = __select_list (ap, which);
584 assert (anl && apl);
585 anl->prev = ap;
586 apl->next = an;
587 al->next = al->prev = a;
588 return;
591 static void
592 init_const_box (routebox_t * rb,
593 Coord X1, Coord Y1, Coord X2,
594 Coord Y2, Coord keepaway)
596 BoxType *bp = (BoxType *) & rb->box; /* note discarding const! */
597 assert (!rb->flags.inited);
598 assert (X1 <= X2 && Y1 <= Y2);
599 bp->X1 = X1 - keepaway;
600 bp->Y1 = Y1 - keepaway;
601 bp->X2 = X2 + keepaway;
602 bp->Y2 = Y2 + keepaway;
603 bp = (BoxType *) & rb->sbox;
604 bp->X1 = X1;
605 bp->Y1 = Y1;
606 bp->X2 = X2;
607 bp->Y2 = Y2;
608 rb->flags.inited = 1;
611 static inline BoxType
612 shrink_routebox (const routebox_t * rb)
614 return rb->sbox;
617 static inline cost_t
618 box_area (const BoxType b)
620 cost_t ans = b.X2 - b.X1;
621 return ans * (b.Y2 - b.Y1);
624 static inline CheapPointType
625 closest_point_in_routebox (const CheapPointType * from, const routebox_t * rb)
627 return closest_point_in_box (from, &rb->sbox);
630 static inline bool
631 point_in_shrunk_box (const routebox_t * box, Coord X, Coord Y)
633 BoxType b = shrink_routebox (box);
634 return point_in_box (&b, X, Y);
637 /*---------------------------------------------------------------------
638 * routedata initialization functions.
641 static routebox_t *
642 AddPin (PointerListType layergroupboxes[], PinType *pin, bool is_via,
643 RouteStyleType * style)
645 routebox_t **rbpp, *lastrb = NULL;
646 int i, ht;
647 /* a pin cuts through every layer group */
648 for (i = 0; i < max_group; i++)
650 rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[i]);
651 *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
652 memset ((void *) *rbpp, 0, sizeof (**rbpp));
653 (*rbpp)->group = i;
654 ht = HALF_THICK (MAX (pin->Thickness, pin->DrillingHole));
655 init_const_box (*rbpp,
656 /*X1 */ pin->X - ht,
657 /*Y1 */ pin->Y - ht,
658 /*X2 */ pin->X + ht,
659 /*Y2 */ pin->Y + ht, style->Keepaway);
660 /* set aux. properties */
661 if (is_via)
663 (*rbpp)->type = VIA;
664 (*rbpp)->parent.via = pin;
666 else
668 (*rbpp)->type = PIN;
669 (*rbpp)->parent.pin = pin;
671 (*rbpp)->flags.fixed = 1;
672 (*rbpp)->came_from = ALL;
673 (*rbpp)->style = style;
674 (*rbpp)->flags.circular = !TEST_FLAG (SQUAREFLAG, pin);
675 /* circular lists */
676 InitLists (*rbpp);
677 /* link together */
678 if (lastrb)
680 MergeNets (*rbpp, lastrb, NET);
681 MergeNets (*rbpp, lastrb, SUBNET);
682 MergeNets (*rbpp, lastrb, ORIGINAL);
684 lastrb = *rbpp;
686 return lastrb;
688 static routebox_t *
689 AddPad (PointerListType layergroupboxes[],
690 ElementType *element, PadType *pad, RouteStyleType * style)
692 Coord halfthick;
693 routebox_t **rbpp;
694 int layergroup = (TEST_FLAG (ONSOLDERFLAG, pad) ? back : front);
695 assert (0 <= layergroup && layergroup < max_group);
696 assert (PCB->LayerGroups.Number[layergroup] > 0);
697 rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
698 assert (rbpp);
699 *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
700 assert (*rbpp);
701 memset (*rbpp, 0, sizeof (**rbpp));
702 (*rbpp)->group = layergroup;
703 halfthick = HALF_THICK (pad->Thickness);
704 init_const_box (*rbpp,
705 /*X1 */ MIN (pad->Point1.X, pad->Point2.X) - halfthick,
706 /*Y1 */ MIN (pad->Point1.Y, pad->Point2.Y) - halfthick,
707 /*X2 */ MAX (pad->Point1.X, pad->Point2.X) + halfthick,
708 /*Y2 */ MAX (pad->Point1.Y, pad->Point2.Y) + halfthick,
709 style->Keepaway);
710 /* kludge for non-manhattan pads (which are not allowed at present) */
711 if (pad->Point1.X != pad->Point2.X && pad->Point1.Y != pad->Point2.Y)
712 (*rbpp)->flags.nonstraight = 1;
713 /* set aux. properties */
714 (*rbpp)->type = PAD;
715 (*rbpp)->parent.pad = pad;
716 (*rbpp)->flags.fixed = 1;
717 (*rbpp)->came_from = ALL;
718 (*rbpp)->style = style;
719 /* circular lists */
720 InitLists (*rbpp);
721 return *rbpp;
723 static routebox_t *
724 AddLine (PointerListType layergroupboxes[], int layergroup, LineType *line,
725 LineType *ptr, RouteStyleType * style)
727 routebox_t **rbpp;
728 assert (layergroupboxes && line);
729 assert (0 <= layergroup && layergroup < max_group);
730 assert (PCB->LayerGroups.Number[layergroup] > 0);
732 rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
733 *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
734 memset (*rbpp, 0, sizeof (**rbpp));
735 (*rbpp)->group = layergroup;
736 init_const_box (*rbpp,
737 /*X1 */ MIN (line->Point1.X,
738 line->Point2.X) - HALF_THICK (line->Thickness),
739 /*Y1 */ MIN (line->Point1.Y,
740 line->Point2.Y) - HALF_THICK (line->Thickness),
741 /*X2 */ MAX (line->Point1.X,
742 line->Point2.X) + HALF_THICK (line->Thickness),
743 /*Y2 */ MAX (line->Point1.Y,
744 line->Point2.Y) +
745 HALF_THICK (line->Thickness), style->Keepaway);
746 /* kludge for non-manhattan lines */
747 if (line->Point1.X != line->Point2.X && line->Point1.Y != line->Point2.Y)
749 (*rbpp)->flags.nonstraight = 1;
750 (*rbpp)->flags.bl_to_ur =
751 (MIN (line->Point1.X, line->Point2.X) == line->Point1.X) !=
752 (MIN (line->Point1.Y, line->Point2.Y) == line->Point1.Y);
753 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ZIGZAG)
754 showroutebox (*rbpp);
755 #endif
757 /* set aux. properties */
758 (*rbpp)->type = LINE;
759 (*rbpp)->parent.line = ptr;
760 (*rbpp)->flags.fixed = 1;
761 (*rbpp)->came_from = ALL;
762 (*rbpp)->style = style;
763 /* circular lists */
764 InitLists (*rbpp);
765 return *rbpp;
767 static routebox_t *
768 AddIrregularObstacle (PointerListType layergroupboxes[],
769 Coord X1, Coord Y1,
770 Coord X2, Coord Y2, Cardinal layergroup,
771 void *parent, RouteStyleType * style)
773 routebox_t **rbpp;
774 Coord keep = style->Keepaway;
775 assert (layergroupboxes && parent);
776 assert (X1 <= X2 && Y1 <= Y2);
777 assert (0 <= layergroup && layergroup < max_group);
778 assert (PCB->LayerGroups.Number[layergroup] > 0);
780 rbpp = (routebox_t **) GetPointerMemory (&layergroupboxes[layergroup]);
781 *rbpp = (routebox_t *)malloc (sizeof (**rbpp));
782 memset (*rbpp, 0, sizeof (**rbpp));
783 (*rbpp)->group = layergroup;
784 init_const_box (*rbpp, X1, Y1, X2, Y2, keep);
785 (*rbpp)->flags.nonstraight = 1;
786 (*rbpp)->type = OTHER;
787 (*rbpp)->parent.generic = parent;
788 (*rbpp)->flags.fixed = 1;
789 (*rbpp)->style = style;
790 /* circular lists */
791 InitLists (*rbpp);
792 return *rbpp;
795 static routebox_t *
796 AddPolygon (PointerListType layergroupboxes[], Cardinal layer,
797 PolygonType *polygon, RouteStyleType * style)
799 int is_not_rectangle = 1;
800 int layergroup = GetLayerGroupNumberByNumber (layer);
801 routebox_t *rb;
802 assert (0 <= layergroup && layergroup < max_group);
803 rb = AddIrregularObstacle (layergroupboxes,
804 polygon->BoundingBox.X1,
805 polygon->BoundingBox.Y1,
806 polygon->BoundingBox.X2,
807 polygon->BoundingBox.Y2,
808 layergroup, polygon, style);
809 if (polygon->PointN == 4 &&
810 polygon->HoleIndexN == 0 &&
811 (polygon->Points[0].X == polygon->Points[1].X ||
812 polygon->Points[0].Y == polygon->Points[1].Y) &&
813 (polygon->Points[1].X == polygon->Points[2].X ||
814 polygon->Points[1].Y == polygon->Points[2].Y) &&
815 (polygon->Points[2].X == polygon->Points[3].X ||
816 polygon->Points[2].Y == polygon->Points[3].Y) &&
817 (polygon->Points[3].X == polygon->Points[0].X ||
818 polygon->Points[3].Y == polygon->Points[0].Y))
819 is_not_rectangle = 0;
820 rb->flags.nonstraight = is_not_rectangle;
821 rb->layer = layer;
822 rb->came_from = ALL;
823 if (TEST_FLAG (CLEARPOLYFLAG, polygon))
825 rb->flags.clear_poly = 1;
826 if (!is_not_rectangle)
827 rb->type = PLANE;
829 return rb;
831 static void
832 AddText (PointerListType layergroupboxes[], Cardinal layergroup,
833 TextType *text, RouteStyleType * style)
835 AddIrregularObstacle (layergroupboxes,
836 text->BoundingBox.X1, text->BoundingBox.Y1,
837 text->BoundingBox.X2, text->BoundingBox.Y2,
838 layergroup, text, style);
840 static routebox_t *
841 AddArc (PointerListType layergroupboxes[], Cardinal layergroup,
842 ArcType *arc, RouteStyleType * style)
844 return AddIrregularObstacle (layergroupboxes,
845 arc->BoundingBox.X1, arc->BoundingBox.Y1,
846 arc->BoundingBox.X2, arc->BoundingBox.Y2,
847 layergroup, arc, style);
850 struct rb_info
852 BoxType query;
853 routebox_t *winner;
854 jmp_buf env;
857 static int
858 __found_one_on_lg (const BoxType * box, void *cl)
860 struct rb_info *inf = (struct rb_info *) cl;
861 routebox_t *rb = (routebox_t *) box;
862 BoxType sb;
864 if (rb->flags.nonstraight)
865 return 0;
866 sb = shrink_box (&rb->box, rb->style->Keepaway);
867 if (inf->query.X1 >= sb.X2 || inf->query.X2 <= sb.X1 ||
868 inf->query.Y1 >= sb.Y2 || inf->query.Y2 <= sb.Y1)
869 return 0;
870 inf->winner = rb;
871 if (rb->type == PLANE)
872 return 1; /* keep looking for something smaller if a plane was found */
873 longjmp (inf->env, 1);
874 return 0;
876 static routebox_t *
877 FindRouteBoxOnLayerGroup (routedata_t * rd,
878 Coord X, Coord Y, Cardinal layergroup)
880 struct rb_info info;
881 info.winner = NULL;
882 info.query = point_box (X, Y);
883 if (setjmp (info.env) == 0)
884 r_search (rd->layergrouptree[layergroup], &info.query, NULL,
885 __found_one_on_lg, &info);
886 return info.winner;
889 #ifdef ROUTE_DEBUG_VERBOSE
890 static void
891 DumpRouteBox (routebox_t * rb)
893 pcb_printf ("RB: %#mD-%#mD l%d; ",
894 rb->box.X1, rb->box.Y1, rb->box.X2, rb->box.Y2, (int) rb->group);
895 switch (rb->type)
897 case PAD:
898 printf ("PAD[%s %s] ", rb->parent.pad->Name, rb->parent.pad->Number);
899 break;
900 case PIN:
901 printf ("PIN[%s %s] ", rb->parent.pin->Name, rb->parent.pin->Number);
902 break;
903 case VIA:
904 if (!rb->parent.via)
905 break;
906 printf ("VIA[%s %s] ", rb->parent.via->Name, rb->parent.via->Number);
907 break;
908 case LINE:
909 printf ("LINE ");
910 break;
911 case OTHER:
912 printf ("OTHER ");
913 break;
914 case EXPANSION_AREA:
915 printf ("EXPAREA ");
916 break;
917 default:
918 printf ("UNKNOWN ");
919 break;
921 if (rb->flags.nonstraight)
922 printf ("(nonstraight) ");
923 if (rb->flags.fixed)
924 printf ("(fixed) ");
925 if (rb->flags.source)
926 printf ("(source) ");
927 if (rb->flags.target)
928 printf ("(target) ");
929 if (rb->flags.homeless)
930 printf ("(homeless) ");
931 printf ("\n");
933 #endif
935 static routedata_t *
936 CreateRouteData ()
938 NetListListType Nets;
939 PointerListType layergroupboxes[MAX_LAYER];
940 BoxType bbox;
941 routedata_t *rd;
942 int group, i;
944 /* check which layers are active first */
945 routing_layers = 0;
946 for (group = 0; group < max_group; group++)
948 for (i = 0; i < PCB->LayerGroups.Number[group]; i++)
949 /* layer must be 1) not silk (ie, < max_copper_layer) and 2) on */
950 if ((PCB->LayerGroups.Entries[group][i] < max_copper_layer) &&
951 PCB->Data->Layer[PCB->LayerGroups.Entries[group][i]].On)
953 routing_layers++;
954 is_layer_group_active[group] = true;
955 break;
957 else
958 is_layer_group_active[group] = false;
960 /* if via visibility is turned off, don't use them */
961 AutoRouteParameters.use_vias = routing_layers > 1 && PCB->ViaOn;
962 front = GetLayerGroupNumberByNumber (component_silk_layer);
963 back = GetLayerGroupNumberByNumber (solder_silk_layer);
964 /* determine preferred routing direction on each group */
965 for (i = 0; i < max_group; i++)
967 if (i != back && i != front)
969 x_cost[i] = (i & 1) ? 2 : 1;
970 y_cost[i] = (i & 1) ? 1 : 2;
972 else if (i == back)
974 x_cost[i] = 4;
975 y_cost[i] = 2;
977 else
979 x_cost[i] = 2;
980 y_cost[i] = 2;
983 /* create routedata */
984 rd = (routedata_t *)malloc (sizeof (*rd));
985 memset ((void *) rd, 0, sizeof (*rd));
986 /* create default style */
987 rd->defaultstyle.Thick = Settings.LineThickness;
988 rd->defaultstyle.Diameter = Settings.ViaThickness;
989 rd->defaultstyle.Hole = Settings.ViaDrillingHole;
990 rd->defaultstyle.Keepaway = Settings.Keepaway;
991 rd->max_bloat = BLOAT (&rd->defaultstyle);
992 rd->max_keep = Settings.Keepaway;
993 /* create styles structures */
994 bbox.X1 = bbox.Y1 = 0;
995 bbox.X2 = PCB->MaxWidth;
996 bbox.Y2 = PCB->MaxHeight;
997 for (i = 0; i < NUM_STYLES + 1; i++)
999 RouteStyleType *style =
1000 (i < NUM_STYLES) ? &PCB->RouteStyle[i] : &rd->defaultstyle;
1001 rd->styles[i] = style;
1004 /* initialize pointerlisttype */
1005 for (i = 0; i < max_group; i++)
1007 layergroupboxes[i].Ptr = NULL;
1008 layergroupboxes[i].PtrN = 0;
1009 layergroupboxes[i].PtrMax = 0;
1010 GROUP_LOOP (PCB->Data, i);
1012 if (layer->LineN || layer->ArcN)
1013 usedGroup[i] = true;
1014 else
1015 usedGroup[i] = false;
1017 END_LOOP;
1019 usedGroup[front] = true;
1020 usedGroup[back] = true;
1021 /* add the objects in the netlist first.
1022 * then go and add all other objects that weren't already added
1024 * this saves on searching the trees to find the nets
1026 /* use the DRCFLAG to mark objects as they are entered */
1027 ResetConnections (false);
1028 Nets = CollectSubnets (false);
1030 routebox_t *last_net = NULL;
1031 NETLIST_LOOP (&Nets);
1033 routebox_t *last_in_net = NULL;
1034 NET_LOOP (netlist);
1036 routebox_t *last_in_subnet = NULL;
1037 int j;
1039 for (j = 0; j < NUM_STYLES; j++)
1040 if (net->Style == rd->styles[j])
1041 break;
1042 CONNECTION_LOOP (net);
1044 routebox_t *rb = NULL;
1045 SET_FLAG (DRCFLAG, (PinType *) connection->ptr2);
1046 if (connection->type == LINE_TYPE)
1048 LineType *line = (LineType *) connection->ptr2;
1050 /* lines are listed at each end, so skip one */
1051 /* this should probably by a macro named "BUMP_LOOP" */
1052 n--;
1054 /* dice up non-straight lines into many tiny obstacles */
1055 if (line->Point1.X != line->Point2.X
1056 && line->Point1.Y != line->Point2.Y)
1058 LineType fake_line = *line;
1059 Coord dx = (line->Point2.X - line->Point1.X);
1060 Coord dy = (line->Point2.Y - line->Point1.Y);
1061 int segs = MAX (ABS (dx),
1062 ABS (dy)) / (4 * BLOAT (rd->styles[j]) + 1);
1063 int qq;
1064 segs = CLAMP (segs, 1, 32); /* don't go too crazy */
1065 dx /= segs;
1066 dy /= segs;
1067 for (qq = 0; qq < segs - 1; qq++)
1069 fake_line.Point2.X = fake_line.Point1.X + dx;
1070 fake_line.Point2.Y = fake_line.Point1.Y + dy;
1071 if (fake_line.Point2.X == line->Point2.X
1072 && fake_line.Point2.Y == line->Point2.Y)
1073 break;
1074 rb =
1075 AddLine (layergroupboxes, connection->group,
1076 &fake_line, line, rd->styles[j]);
1077 if (last_in_subnet && rb != last_in_subnet)
1078 MergeNets (last_in_subnet, rb, ORIGINAL);
1079 if (last_in_net && rb != last_in_net)
1080 MergeNets (last_in_net, rb, NET);
1081 last_in_subnet = last_in_net = rb;
1082 fake_line.Point1 = fake_line.Point2;
1084 fake_line.Point2 = line->Point2;
1085 rb =
1086 AddLine (layergroupboxes, connection->group, &fake_line,
1087 line, rd->styles[j]);
1089 else
1091 rb =
1092 AddLine (layergroupboxes, connection->group, line, line,
1093 rd->styles[j]);
1096 else
1097 switch (connection->type)
1099 case PAD_TYPE:
1100 rb =
1101 AddPad (layergroupboxes, (ElementType *)connection->ptr1,
1102 (PadType *)connection->ptr2, rd->styles[j]);
1103 break;
1104 case PIN_TYPE:
1105 rb =
1106 AddPin (layergroupboxes, (PinType *)connection->ptr2, false,
1107 rd->styles[j]);
1108 break;
1109 case VIA_TYPE:
1110 rb =
1111 AddPin (layergroupboxes, (PinType *)connection->ptr2, true,
1112 rd->styles[j]);
1113 break;
1114 case POLYGON_TYPE:
1115 rb =
1116 AddPolygon (layergroupboxes,
1117 GetLayerNumber (PCB->Data, (LayerType *)connection->ptr1),
1118 (struct polygon_st *)connection->ptr2, rd->styles[j]);
1119 break;
1121 assert (rb);
1122 /* update circular connectivity lists */
1123 if (last_in_subnet && rb != last_in_subnet)
1124 MergeNets (last_in_subnet, rb, ORIGINAL);
1125 if (last_in_net && rb != last_in_net)
1126 MergeNets (last_in_net, rb, NET);
1127 last_in_subnet = last_in_net = rb;
1128 rd->max_bloat = MAX (rd->max_bloat, BLOAT (rb->style));
1129 rd->max_keep = MAX (rd->max_keep, rb->style->Keepaway);
1131 END_LOOP;
1133 END_LOOP;
1134 if (last_net && last_in_net)
1135 MergeNets (last_net, last_in_net, DIFFERENT_NET);
1136 last_net = last_in_net;
1138 END_LOOP;
1139 rd->first_net = last_net;
1141 FreeNetListListMemory (&Nets);
1143 /* reset all nets to "original" connectivity (which we just set) */
1145 routebox_t *net;
1146 LIST_LOOP (rd->first_net, different_net, net);
1147 ResetSubnet (net);
1148 END_LOOP;
1151 /* add pins and pads of elements */
1152 ALLPIN_LOOP (PCB->Data);
1154 if (TEST_FLAG (DRCFLAG, pin))
1155 CLEAR_FLAG (DRCFLAG, pin);
1156 else
1157 AddPin (layergroupboxes, pin, false, rd->styles[NUM_STYLES]);
1159 ENDALL_LOOP;
1160 ALLPAD_LOOP (PCB->Data);
1162 if (TEST_FLAG (DRCFLAG, pad))
1163 CLEAR_FLAG (DRCFLAG, pad);
1164 else
1165 AddPad (layergroupboxes, element, pad, rd->styles[NUM_STYLES]);
1167 ENDALL_LOOP;
1168 /* add all vias */
1169 VIA_LOOP (PCB->Data);
1171 if (TEST_FLAG (DRCFLAG, via))
1172 CLEAR_FLAG (DRCFLAG, via);
1173 else
1174 AddPin (layergroupboxes, via, true, rd->styles[NUM_STYLES]);
1176 END_LOOP;
1178 for (i = 0; i < max_copper_layer; i++)
1180 int layergroup = GetLayerGroupNumberByNumber (i);
1181 /* add all (non-rat) lines */
1182 LINE_LOOP (LAYER_PTR (i));
1184 if (TEST_FLAG (DRCFLAG, line))
1186 CLEAR_FLAG (DRCFLAG, line);
1187 continue;
1189 /* dice up non-straight lines into many tiny obstacles */
1190 if (line->Point1.X != line->Point2.X
1191 && line->Point1.Y != line->Point2.Y)
1193 LineType fake_line = *line;
1194 Coord dx = (line->Point2.X - line->Point1.X);
1195 Coord dy = (line->Point2.Y - line->Point1.Y);
1196 int segs = MAX (ABS (dx), ABS (dy)) / (4 * rd->max_bloat + 1);
1197 int qq;
1198 segs = CLAMP (segs, 1, 32); /* don't go too crazy */
1199 dx /= segs;
1200 dy /= segs;
1201 for (qq = 0; qq < segs - 1; qq++)
1203 fake_line.Point2.X = fake_line.Point1.X + dx;
1204 fake_line.Point2.Y = fake_line.Point1.Y + dy;
1205 if (fake_line.Point2.X == line->Point2.X
1206 && fake_line.Point2.Y == line->Point2.Y)
1207 break;
1208 AddLine (layergroupboxes, layergroup, &fake_line, line,
1209 rd->styles[NUM_STYLES]);
1210 fake_line.Point1 = fake_line.Point2;
1212 fake_line.Point2 = line->Point2;
1213 AddLine (layergroupboxes, layergroup, &fake_line, line,
1214 rd->styles[NUM_STYLES]);
1216 else
1218 AddLine (layergroupboxes, layergroup, line, line,
1219 rd->styles[NUM_STYLES]);
1222 END_LOOP;
1223 /* add all polygons */
1224 POLYGON_LOOP (LAYER_PTR (i));
1226 if (TEST_FLAG (DRCFLAG, polygon))
1227 CLEAR_FLAG (DRCFLAG, polygon);
1228 else
1229 AddPolygon (layergroupboxes, i, polygon, rd->styles[NUM_STYLES]);
1231 END_LOOP;
1232 /* add all copper text */
1233 TEXT_LOOP (LAYER_PTR (i));
1235 AddText (layergroupboxes, layergroup, text, rd->styles[NUM_STYLES]);
1237 END_LOOP;
1238 /* add all arcs */
1239 ARC_LOOP (LAYER_PTR (i));
1241 AddArc (layergroupboxes, layergroup, arc, rd->styles[NUM_STYLES]);
1243 END_LOOP;
1246 /* create r-trees from pointer lists */
1247 for (i = 0; i < max_group; i++)
1249 /* create the r-tree */
1250 rd->layergrouptree[i] =
1251 r_create_tree ((const BoxType **) layergroupboxes[i].Ptr,
1252 layergroupboxes[i].PtrN, 1);
1255 if (AutoRouteParameters.use_vias)
1257 rd->mtspace = mtspace_create ();
1259 /* create "empty-space" structures for via placement (now that we know
1260 * appropriate keepaways for all the fixed elements) */
1261 for (i = 0; i < max_group; i++)
1263 POINTER_LOOP (&layergroupboxes[i]);
1265 routebox_t *rb = (routebox_t *) * ptr;
1266 if (!rb->flags.clear_poly)
1267 mtspace_add (rd->mtspace, &rb->box, FIXED, rb->style->Keepaway);
1269 END_LOOP;
1272 /* free pointer lists */
1273 for (i = 0; i < max_group; i++)
1274 FreePointerListMemory (&layergroupboxes[i]);
1275 /* done! */
1276 return rd;
1279 void
1280 DestroyRouteData (routedata_t ** rd)
1282 int i;
1283 for (i = 0; i < max_group; i++)
1284 r_destroy_tree (&(*rd)->layergrouptree[i]);
1285 if (AutoRouteParameters.use_vias)
1286 mtspace_destroy (&(*rd)->mtspace);
1287 free (*rd);
1288 *rd = NULL;
1291 /*-----------------------------------------------------------------
1292 * routebox reference counting.
1295 /* increment the reference count on a routebox. */
1296 static void
1297 RB_up_count (routebox_t * rb)
1299 assert (rb->flags.homeless);
1300 rb->refcount++;
1303 /* decrement the reference count on a routebox, freeing if this box becomes
1304 * unused. */
1305 static void
1306 RB_down_count (routebox_t * rb)
1308 assert (rb->type == EXPANSION_AREA);
1309 assert (rb->flags.homeless);
1310 assert (rb->refcount > 0);
1311 if (--rb->refcount == 0)
1313 if (rb->parent.expansion_area->flags.homeless)
1314 RB_down_count (rb->parent.expansion_area);
1315 free (rb);
1319 /*-----------------------------------------------------------------
1320 * Rectangle-expansion routing code.
1323 static void
1324 ResetSubnet (routebox_t * net)
1326 routebox_t *rb;
1327 /* reset connectivity of everything on this net */
1328 LIST_LOOP (net, same_net, rb);
1329 rb->same_subnet = rb->original_subnet;
1330 END_LOOP;
1333 static inline cost_t
1334 cost_to_point_on_layer (const CheapPointType * p1,
1335 const CheapPointType * p2, Cardinal point_layer)
1337 cost_t x_dist = p1->X - p2->X, y_dist = p1->Y - p2->Y, r;
1338 x_dist *= x_cost[point_layer];
1339 y_dist *= y_cost[point_layer];
1340 /* cost is proportional to orthogonal distance. */
1341 r = ABS (x_dist) + ABS (y_dist);
1342 if (p1->X != p2->X && p1->Y != p2->Y)
1343 r += AutoRouteParameters.JogPenalty;
1344 return r;
1347 static cost_t
1348 cost_to_point (const CheapPointType * p1, Cardinal point_layer1,
1349 const CheapPointType * p2, Cardinal point_layer2)
1351 cost_t r = cost_to_point_on_layer (p1, p2, point_layer1);
1352 /* apply via cost penalty if layers differ */
1353 if (point_layer1 != point_layer2)
1354 r += AutoRouteParameters.ViaCost;
1355 return r;
1358 /* return the minimum *cost* from a point to a box on any layer.
1359 * It's safe to return a smaller than minimum cost
1361 static cost_t
1362 cost_to_layerless_box (const CheapPointType * p, Cardinal point_layer,
1363 const BoxType * b)
1365 CheapPointType p2 = closest_point_in_box (p, b);
1366 register cost_t c1, c2;
1368 c1 = p2.X - p->X;
1369 c2 = p2.Y - p->Y;
1371 c1 = ABS (c1);
1372 c2 = ABS (c2);
1373 if (c1 < c2)
1374 return c1 * AutoRouteParameters.MinPenalty + c2;
1375 else
1376 return c2 * AutoRouteParameters.MinPenalty + c1;
1379 /* get to actual pins/pad target coordinates */
1380 bool
1381 TargetPoint (CheapPointType * nextpoint, const routebox_t * target)
1383 if (target->type == PIN)
1385 nextpoint->X = target->parent.pin->X;
1386 nextpoint->Y = target->parent.pin->Y;
1387 return true;
1389 else if (target->type == PAD)
1391 if (abs (target->parent.pad->Point1.X - nextpoint->X) <
1392 abs (target->parent.pad->Point2.X - nextpoint->X))
1393 nextpoint->X = target->parent.pad->Point1.X;
1394 else
1395 nextpoint->X = target->parent.pad->Point2.X;
1396 if (abs (target->parent.pad->Point1.Y - nextpoint->Y) <
1397 abs (target->parent.pad->Point2.Y - nextpoint->Y))
1398 nextpoint->Y = target->parent.pad->Point1.Y;
1399 else
1400 nextpoint->Y = target->parent.pad->Point2.Y;
1401 return true;
1403 else
1405 nextpoint->X = CENTER_X (target->sbox);
1406 nextpoint->Y = CENTER_Y (target->sbox);
1408 return false;
1411 /* return the *minimum cost* from a point to a route box, including possible
1412 * via costs if the route box is on a different layer.
1413 * assume routbox is bloated unless it is an expansion area
1415 static cost_t
1416 cost_to_routebox (const CheapPointType * p, Cardinal point_layer,
1417 const routebox_t * rb)
1419 register cost_t trial = 0;
1420 CheapPointType p2 = closest_point_in_routebox (p, rb);
1421 if (!usedGroup[point_layer] || !usedGroup[rb->group])
1422 trial = AutoRouteParameters.NewLayerPenalty;
1423 if ((p2.X - p->X) * (p2.Y - p->Y) != 0)
1424 trial += AutoRouteParameters.JogPenalty;
1425 /* special case for defered via searching */
1426 if (point_layer > max_group || point_layer == rb->group)
1427 return trial + ABS (p2.X - p->X) + ABS (p2.Y - p->Y);
1428 /* if this target is only a via away, then the via is cheaper than the congestion */
1429 if (p->X == p2.X && p->Y == p2.Y)
1430 return trial + 1;
1431 trial += AutoRouteParameters.ViaCost;
1432 trial += ABS (p2.X - p->X) + ABS (p2.Y - p->Y);
1433 return trial;
1437 static BoxType
1438 bloat_routebox (routebox_t * rb)
1440 BoxType r;
1441 Coord keepaway;
1442 assert (__routebox_is_good (rb));
1444 if (rb->flags.nobloat)
1445 return rb->sbox;
1447 /* Obstacle exclusion zones get bloated by the larger of
1448 * the two required clearances plus half the track width.
1450 keepaway = MAX (AutoRouteParameters.style->Keepaway, rb->style->Keepaway);
1451 r = bloat_box (&rb->sbox, keepaway +
1452 HALF_THICK (AutoRouteParameters.style->Thick));
1453 return r;
1457 #ifdef ROUTE_DEBUG /* only for debugging expansion areas */
1459 /* makes a line on the solder layer silk surrounding the box */
1460 void
1461 showbox (BoxType b, Dimension thickness, int group)
1463 LineType *line;
1464 LayerType *SLayer = LAYER_PTR (group);
1465 if (showboxen < -1)
1466 return;
1467 if (showboxen != -1 && showboxen != group)
1468 return;
1470 if (ddraw != NULL)
1472 ddraw->graphics->set_line_width (ar_gc, thickness);
1473 ddraw->graphics->set_line_cap (ar_gc, Trace_Cap);
1474 ddraw->graphics->set_color (ar_gc, SLayer->Color);
1476 ddraw->graphics->draw_line (ar_gc, b.X1, b.Y1, b.X2, b.Y1);
1477 ddraw->graphics->draw_line (ar_gc, b.X1, b.Y2, b.X2, b.Y2);
1478 ddraw->graphics->draw_line (ar_gc, b.X1, b.Y1, b.X1, b.Y2);
1479 ddraw->graphics->draw_line (ar_gc, b.X2, b.Y1, b.X2, b.Y2);
1482 #if 1
1483 if (b.Y1 == b.Y2 || b.X1 == b.X2)
1484 thickness = 5;
1485 line = CreateNewLineOnLayer (LAYER_PTR (component_silk_layer),
1486 b.X1, b.Y1, b.X2, b.Y1, thickness, 0,
1487 MakeFlags (0));
1488 AddObjectToCreateUndoList (LINE_TYPE,
1489 LAYER_PTR (component_silk_layer), line,
1490 line);
1491 if (b.Y1 != b.Y2)
1493 line = CreateNewLineOnLayer (LAYER_PTR (component_silk_layer),
1494 b.X1, b.Y2, b.X2, b.Y2, thickness, 0,
1495 MakeFlags (0));
1496 AddObjectToCreateUndoList (LINE_TYPE,
1497 LAYER_PTR (component_silk_layer),
1498 line, line);
1500 line = CreateNewLineOnLayer (LAYER_PTR (component_silk_layer),
1501 b.X1, b.Y1, b.X1, b.Y2, thickness, 0,
1502 MakeFlags (0));
1503 AddObjectToCreateUndoList (LINE_TYPE,
1504 LAYER_PTR (component_silk_layer), line,
1505 line);
1506 if (b.X1 != b.X2)
1508 line = CreateNewLineOnLayer (LAYER_PTR (component_silk_layer),
1509 b.X2, b.Y1, b.X2, b.Y2, thickness, 0,
1510 MakeFlags (0));
1511 AddObjectToCreateUndoList (LINE_TYPE,
1512 LAYER_PTR (component_silk_layer),
1513 line, line);
1515 #endif
1517 #endif
1519 #if defined(ROUTE_DEBUG)
1520 static void
1521 showedge (edge_t * e)
1523 BoxType *b = (BoxType *) e->rb;
1525 if (ddraw == NULL)
1526 return;
1528 ddraw->graphics->set_line_cap (ar_gc, Trace_Cap);
1529 ddraw->graphics->set_line_width (ar_gc, 1);
1530 ddraw->graphics->set_color (ar_gc, Settings.MaskColor);
1532 switch (e->expand_dir)
1534 case NORTH:
1535 ddraw->graphics->draw_line (ar_gc, b->X1, b->Y1, b->X2, b->Y1);
1536 break;
1537 case SOUTH:
1538 ddraw->graphics->draw_line (ar_gc, b->X1, b->Y2, b->X2, b->Y2);
1539 break;
1540 case WEST:
1541 ddraw->graphics->draw_line (ar_gc, b->X1, b->Y1, b->X1, b->Y2);
1542 break;
1543 case EAST:
1544 ddraw->graphics->draw_line (ar_gc, b->X2, b->Y1, b->X2, b->Y2);
1545 break;
1546 default:
1547 break;
1550 #endif
1552 #if defined(ROUTE_DEBUG)
1553 static void
1554 showroutebox (routebox_t * rb)
1556 showbox (rb->sbox, rb->flags.source ? 20 : (rb->flags.target ? 10 : 1),
1557 rb->flags.is_via ? component_silk_layer : rb->group);
1559 #endif
1561 /* return a "parent" of this edge which immediately precedes it in the route.*/
1562 static routebox_t *
1563 route_parent (routebox_t * rb)
1565 while (rb->flags.homeless && !rb->flags.is_via && !rb->flags.is_thermal)
1567 assert (rb->type == EXPANSION_AREA);
1568 rb = rb->parent.expansion_area;
1569 assert (rb);
1571 return rb;
1574 static vector_t *
1575 path_conflicts (routebox_t * rb, routebox_t * conflictor, bool branch)
1577 if (branch)
1578 rb->conflicts_with = vector_duplicate (rb->conflicts_with);
1579 else if (!rb->conflicts_with)
1580 rb->conflicts_with = vector_create ();
1581 vector_append (rb->conflicts_with, conflictor);
1582 return rb->conflicts_with;
1585 /* Touch everything (except fixed) on each net found
1586 * in the conflicts vector. If the vector is different
1587 * from the last one touched, untouch the last batch
1588 * and touch the new one. Always call with touch=1
1589 * (except for recursive call). Call with NULL, 1 to
1590 * clear the last batch touched.
1592 * touched items become invisible to current path
1593 * so we don't encounter the same conflictor more
1594 * than once
1597 static void
1598 touch_conflicts (vector_t * conflicts, int touch)
1600 static vector_t *last = NULL;
1601 static int last_size = 0;
1602 int i, n;
1603 i = 0;
1604 if (touch)
1606 if (last && conflicts != last)
1607 touch_conflicts (last, 0);
1608 if (!conflicts)
1609 return;
1610 last = conflicts;
1611 i = last_size;
1613 n = vector_size (conflicts);
1614 for (; i < n; i++)
1616 routebox_t *rb = (routebox_t *) vector_element (conflicts, i);
1617 routebox_t *p;
1618 LIST_LOOP (rb, same_net, p);
1619 if (!p->flags.fixed)
1620 p->flags.touched = touch;
1621 END_LOOP;
1623 if (!touch)
1625 last = NULL;
1626 last_size = 0;
1628 else
1629 last_size = n;
1632 /* return a "parent" of this edge which resides in a r-tree somewhere */
1633 /* -- actually, this "parent" *may* be a via box, which doesn't live in
1634 * a r-tree. -- */
1635 static routebox_t *
1636 nonhomeless_parent (routebox_t * rb)
1638 return route_parent (rb);
1641 /* some routines to find the minimum *cost* from a cost point to
1642 * a target (any target) */
1643 struct mincost_target_closure
1645 const CheapPointType *CostPoint;
1646 Cardinal CostPointLayer;
1647 routebox_t *nearest;
1648 cost_t nearest_cost;
1650 static int
1651 __region_within_guess (const BoxType * region, void *cl)
1653 struct mincost_target_closure *mtc = (struct mincost_target_closure *) cl;
1654 cost_t cost_to_region;
1655 if (mtc->nearest == NULL)
1656 return 1;
1657 cost_to_region =
1658 cost_to_layerless_box (mtc->CostPoint, mtc->CostPointLayer, region);
1659 assert (cost_to_region >= 0);
1660 /* if no guess yet, all regions are "close enough" */
1661 /* note that cost is *strictly more* than minimum distance, so we'll
1662 * always search a region large enough. */
1663 return (cost_to_region < mtc->nearest_cost);
1665 static int
1666 __found_new_guess (const BoxType * box, void *cl)
1668 struct mincost_target_closure *mtc = (struct mincost_target_closure *) cl;
1669 routebox_t *guess = (routebox_t *) box;
1670 cost_t cost_to_guess =
1671 cost_to_routebox (mtc->CostPoint, mtc->CostPointLayer, guess);
1672 assert (cost_to_guess >= 0);
1673 /* if this is cheaper than previous guess... */
1674 if (cost_to_guess < mtc->nearest_cost)
1676 mtc->nearest = guess;
1677 mtc->nearest_cost = cost_to_guess; /* this is our new guess! */
1678 return 1;
1680 else
1681 return 0; /* not less expensive than our last guess */
1684 /* target_guess is our guess at what the nearest target is, or NULL if we
1685 * just plum don't have a clue. */
1686 static routebox_t *
1687 mincost_target_to_point (const CheapPointType * CostPoint,
1688 Cardinal CostPointLayer,
1689 rtree_t * targets, routebox_t * target_guess)
1691 struct mincost_target_closure mtc;
1692 assert (target_guess == NULL || target_guess->flags.target); /* this is a target, right? */
1693 mtc.CostPoint = CostPoint;
1694 mtc.CostPointLayer = CostPointLayer;
1695 mtc.nearest = target_guess;
1696 if (mtc.nearest)
1697 mtc.nearest_cost =
1698 cost_to_routebox (mtc.CostPoint, mtc.CostPointLayer, mtc.nearest);
1699 else
1700 mtc.nearest_cost = EXPENSIVE;
1701 r_search (targets, NULL, __region_within_guess, __found_new_guess, &mtc);
1702 assert (mtc.nearest != NULL && mtc.nearest_cost >= 0);
1703 assert (mtc.nearest->flags.target); /* this is a target, right? */
1704 return mtc.nearest;
1707 /* create edge from field values */
1708 /* mincost_target_guess can be NULL */
1709 static edge_t *
1710 CreateEdge (routebox_t * rb,
1711 Coord CostPointX, Coord CostPointY,
1712 cost_t cost_to_point,
1713 routebox_t * mincost_target_guess,
1714 direction_t expand_dir, rtree_t * targets)
1716 edge_t *e;
1717 assert (__routebox_is_good (rb));
1718 e = (edge_t *)malloc (sizeof (*e));
1719 memset ((void *) e, 0, sizeof (*e));
1720 assert (e);
1721 e->rb = rb;
1722 if (rb->flags.homeless)
1723 RB_up_count (rb);
1724 e->cost_point.X = CostPointX;
1725 e->cost_point.Y = CostPointY;
1726 e->cost_to_point = cost_to_point;
1727 e->flags.via_search = 0;
1728 /* if this edge is created in response to a target, use it */
1729 if (targets)
1730 e->mincost_target =
1731 mincost_target_to_point (&e->cost_point, rb->group,
1732 targets, mincost_target_guess);
1733 else
1734 e->mincost_target = mincost_target_guess;
1735 e->expand_dir = expand_dir;
1736 assert (e->rb && e->mincost_target); /* valid edge? */
1737 assert (!e->flags.is_via || e->expand_dir == ALL);
1738 /* cost point should be on edge (unless this is a plane/via/conflict edge) */
1739 #if 0
1740 assert (rb->type == PLANE || rb->conflicts_with != NULL || rb->flags.is_via
1741 || rb->flags.is_thermal
1742 || ((expand_dir == NORTH || expand_dir == SOUTH) ? rb->sbox.X1 <=
1743 CostPointX && CostPointX < rb->sbox.X2
1744 && CostPointY == (expand_dir ==
1745 NORTH ? rb->sbox.Y1 : rb->sbox.Y2 - 1) :
1746 /* expand_dir==EAST || expand_dir==WEST */
1747 rb->sbox.Y1 <= CostPointY && CostPointY < rb->sbox.Y2 &&
1748 CostPointX == (expand_dir ==
1749 EAST ? rb->sbox.X2 - 1 : rb->sbox.X1)));
1750 #endif
1751 assert (__edge_is_good (e));
1752 /* done */
1753 return e;
1756 /* create edge, using previous edge to fill in defaults. */
1757 /* most of the work here is in determining a new cost point */
1758 static edge_t *
1759 CreateEdge2 (routebox_t * rb, direction_t expand_dir,
1760 edge_t * previous_edge, rtree_t * targets, routebox_t * guess)
1762 BoxType thisbox;
1763 CheapPointType thiscost, prevcost;
1764 cost_t d;
1766 assert (rb && previous_edge);
1767 /* okay, find cheapest costpoint to costpoint of previous edge */
1768 thisbox = edge_to_box (rb, expand_dir);
1769 prevcost = previous_edge->cost_point;
1770 /* find point closest to target */
1771 thiscost = closest_point_in_box (&prevcost, &thisbox);
1772 /* compute cost-to-point */
1773 d = cost_to_point_on_layer (&prevcost, &thiscost, rb->group);
1774 /* add in jog penalty */
1775 if (previous_edge->expand_dir != expand_dir)
1776 d += AutoRouteParameters.JogPenalty;
1777 /* okay, new edge! */
1778 return CreateEdge (rb, thiscost.X, thiscost.Y,
1779 previous_edge->cost_to_point + d,
1780 guess ? guess : previous_edge->mincost_target,
1781 expand_dir, targets);
1784 /* create via edge, using previous edge to fill in defaults. */
1785 static edge_t *
1786 CreateViaEdge (const BoxType * area, Cardinal group,
1787 routebox_t * parent, edge_t * previous_edge,
1788 conflict_t to_site_conflict,
1789 conflict_t through_site_conflict, rtree_t * targets)
1791 routebox_t *rb;
1792 CheapPointType costpoint;
1793 cost_t d;
1794 edge_t *ne;
1795 cost_t scale[3];
1797 scale[0] = 1;
1798 scale[1] = AutoRouteParameters.LastConflictPenalty;
1799 scale[2] = AutoRouteParameters.ConflictPenalty;
1801 assert (box_is_good (area));
1802 assert (AutoRouteParameters.with_conflicts ||
1803 (to_site_conflict == NO_CONFLICT &&
1804 through_site_conflict == NO_CONFLICT));
1805 rb = CreateExpansionArea (area, group, parent, true, previous_edge);
1806 rb->flags.is_via = 1;
1807 rb->came_from = ALL;
1808 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_VIA_BOXES)
1809 showroutebox (rb);
1810 #endif /* ROUTE_DEBUG && DEBUG_SHOW_VIA_BOXES */
1811 /* for planes, choose a point near the target */
1812 if (previous_edge->flags.in_plane)
1814 routebox_t *target;
1815 CheapPointType pnt;
1816 /* find a target near this via box */
1817 pnt.X = CENTER_X (*area);
1818 pnt.Y = CENTER_Y (*area);
1819 target = mincost_target_to_point (&pnt, rb->group,
1820 targets,
1821 previous_edge->mincost_target);
1822 /* now find point near the target */
1823 pnt.X = CENTER_X (target->box);
1824 pnt.Y = CENTER_Y (target->box);
1825 costpoint = closest_point_in_routebox (&pnt, rb);
1826 /* we moved from the previous cost point through the plane which is free travel */
1828 (scale[through_site_conflict] *
1829 cost_to_point (&costpoint, group, &costpoint,
1830 previous_edge->rb->group));
1831 ne =
1832 CreateEdge (rb, costpoint.X, costpoint.Y,
1833 previous_edge->cost_to_point + d, target, ALL, NULL);
1834 ne->mincost_target = target;
1836 else
1838 routebox_t *target;
1839 target = previous_edge->mincost_target;
1840 costpoint = closest_point_in_routebox (&previous_edge->cost_point, rb);
1842 (scale[to_site_conflict] *
1843 cost_to_point_on_layer (&costpoint, &previous_edge->cost_point,
1844 previous_edge->rb->group)) +
1845 (scale[through_site_conflict] *
1846 cost_to_point (&costpoint, group, &costpoint,
1847 previous_edge->rb->group));
1848 /* if the target is just this via away, then this via is cheaper */
1849 if (target->group == group &&
1850 point_in_shrunk_box (target, costpoint.X, costpoint.Y))
1851 d -= AutoRouteParameters.ViaCost / 2;
1852 ne =
1853 CreateEdge (rb, costpoint.X, costpoint.Y,
1854 previous_edge->cost_to_point + d,
1855 previous_edge->mincost_target, ALL, targets);
1857 ne->flags.is_via = 1;
1858 ne->flags.via_conflict_level = to_site_conflict;
1859 assert (__edge_is_good (ne));
1860 return ne;
1863 /* create "interior" edge for routing with conflicts */
1864 /* Presently once we "jump inside" the conflicting object
1865 * we consider it a routing highway to travel inside since
1866 * it will become available if the conflict is elliminated.
1867 * That is why we ignore the interior_edge argument.
1869 static edge_t *
1870 CreateEdgeWithConflicts (const BoxType * interior_edge,
1871 routebox_t * container, edge_t * previous_edge,
1872 cost_t cost_penalty_to_box, rtree_t * targets)
1874 routebox_t *rb;
1875 CheapPointType costpoint;
1876 cost_t d;
1877 edge_t *ne;
1878 assert (interior_edge && container && previous_edge && targets);
1879 assert (!container->flags.homeless);
1880 assert (AutoRouteParameters.with_conflicts);
1881 assert (container->flags.touched == 0);
1882 assert (previous_edge->rb->group == container->group);
1883 /* use the caller's idea of what this box should be */
1884 rb =
1885 CreateExpansionArea (interior_edge, previous_edge->rb->group,
1886 previous_edge->rb, true, previous_edge);
1887 path_conflicts (rb, container, true); /* crucial! */
1888 costpoint =
1889 closest_point_in_box (&previous_edge->cost_point, interior_edge);
1891 cost_to_point_on_layer (&costpoint, &previous_edge->cost_point,
1892 previous_edge->rb->group);
1893 d *= cost_penalty_to_box;
1894 d += previous_edge->cost_to_point;
1895 ne = CreateEdge (rb, costpoint.X, costpoint.Y, d, NULL, ALL, targets);
1896 ne->flags.is_interior = 1;
1897 assert (__edge_is_good (ne));
1898 return ne;
1901 static void
1902 KillEdge (void *edge)
1904 edge_t *e = (edge_t *) edge;
1905 assert (e);
1906 if (e->rb->flags.homeless)
1907 RB_down_count (e->rb);
1908 if (e->flags.via_search)
1909 mtsFreeWork (&e->work);
1910 free (e);
1913 static void
1914 DestroyEdge (edge_t ** e)
1916 assert (e && *e);
1917 KillEdge (*e);
1918 *e = NULL;
1921 /* cost function for an edge. */
1922 static cost_t
1923 edge_cost (const edge_t * e, const cost_t too_big)
1925 cost_t penalty = e->cost_to_point;
1926 if (e->rb->flags.is_thermal || e->rb->type == PLANE)
1927 return penalty; /* thermals are cheap */
1928 if (penalty > too_big)
1929 return penalty;
1931 /* cost_to_routebox adds in our via correction, too. */
1932 return penalty +
1933 cost_to_routebox (&e->cost_point, e->rb->group, e->mincost_target);
1936 /* given an edge of a box, return a box containing exactly the points on that
1937 * edge. Note that the return box is treated as closed; that is, the bottom and
1938 * right "edges" consist of points (just barely) not in the (half-open) box. */
1939 static BoxType
1940 edge_to_box (const routebox_t * rb, direction_t expand_dir)
1942 BoxType b = shrink_routebox (rb);
1943 /* narrow box down to just the appropriate edge */
1944 switch (expand_dir)
1946 case NORTH:
1947 b.Y2 = b.Y1 + 1;
1948 break;
1949 case EAST:
1950 b.X1 = b.X2 - 1;
1951 break;
1952 case SOUTH:
1953 b.Y1 = b.Y2 - 1;
1954 break;
1955 case WEST:
1956 b.X2 = b.X1 + 1;
1957 break;
1958 default:
1959 assert (0);
1961 /* done! */
1962 return b;
1965 struct broken_boxes
1967 BoxType left, center, right;
1968 bool is_valid_left, is_valid_center, is_valid_right;
1971 static struct broken_boxes
1972 break_box_edge (const BoxType * original, direction_t which_edge,
1973 routebox_t * breaker)
1975 BoxType origbox, breakbox;
1976 struct broken_boxes result;
1978 assert (original && breaker);
1980 origbox = *original;
1981 breakbox = bloat_routebox (breaker);
1982 ROTATEBOX_TO_NORTH (origbox, which_edge);
1983 ROTATEBOX_TO_NORTH (breakbox, which_edge);
1984 result.right.Y1 = result.center.Y1 = result.left.Y1 = origbox.Y1;
1985 result.right.Y2 = result.center.Y2 = result.left.Y2 = origbox.Y1 + 1;
1986 /* validity of breaker is not important because the boxes are marked invalid */
1987 //assert (breakbox.X1 <= origbox.X2 && breakbox.X2 >= origbox.X1);
1988 /* left edge piece */
1989 result.left.X1 = origbox.X1;
1990 result.left.X2 = breakbox.X1;
1991 /* center (ie blocked) edge piece */
1992 result.center.X1 = MAX (breakbox.X1, origbox.X1);
1993 result.center.X2 = MIN (breakbox.X2, origbox.X2);
1994 /* right edge piece */
1995 result.right.X1 = breakbox.X2;
1996 result.right.X2 = origbox.X2;
1997 /* validity: */
1998 result.is_valid_left = (result.left.X1 < result.left.X2);
1999 result.is_valid_center = (result.center.X1 < result.center.X2);
2000 result.is_valid_right = (result.right.X1 < result.right.X2);
2001 /* rotate back */
2002 ROTATEBOX_FROM_NORTH (result.left, which_edge);
2003 ROTATEBOX_FROM_NORTH (result.center, which_edge);
2004 ROTATEBOX_FROM_NORTH (result.right, which_edge);
2005 /* done */
2006 return result;
2009 #ifndef NDEBUG
2010 static int
2011 share_edge (const BoxType * child, const BoxType * parent)
2013 return
2014 (child->X1 == parent->X2 || child->X2 == parent->X1 ||
2015 child->Y1 == parent->Y2 || child->Y2 == parent->Y1) &&
2016 ((parent->X1 <= child->X1 && child->X2 <= parent->X2) ||
2017 (parent->Y1 <= child->Y1 && child->Y2 <= parent->Y2));
2019 static int
2020 edge_intersect (const BoxType * child, const BoxType * parent)
2022 return
2023 (child->X1 <= parent->X2) && (child->X2 >= parent->X1) &&
2024 (child->Y1 <= parent->Y2) && (child->Y2 >= parent->Y1);
2026 #endif
2028 /* area is the expansion area, on layer group 'group'. 'parent' is the
2029 * immediately preceding expansion area, for backtracing. 'lastarea' is
2030 * the last expansion area created, we string these together in a loop
2031 * so we can remove them all easily at the end. */
2032 static routebox_t *
2033 CreateExpansionArea (const BoxType * area, Cardinal group,
2034 routebox_t * parent,
2035 bool relax_edge_requirements, edge_t * src_edge)
2037 routebox_t *rb = (routebox_t *) malloc (sizeof (*rb));
2038 memset ((void *) rb, 0, sizeof (*rb));
2039 assert (area && parent);
2040 init_const_box (rb, area->X1, area->Y1, area->X2, area->Y2, 0);
2041 rb->group = group;
2042 rb->type = EXPANSION_AREA;
2043 /* should always share edge or overlap with parent */
2044 assert (relax_edge_requirements ? box_intersect (&rb->sbox, &parent->sbox)
2045 : share_edge (&rb->sbox, &parent->sbox));
2046 rb->parent.expansion_area = route_parent (parent);
2047 rb->cost_point =
2048 closest_point_in_box (&rb->parent.expansion_area->cost_point, area);
2049 rb->cost =
2050 rb->parent.expansion_area->cost +
2051 cost_to_point_on_layer (&rb->parent.expansion_area->cost_point,
2052 &rb->cost_point, rb->group);
2053 assert (relax_edge_requirements ? edge_intersect (&rb->sbox, &parent->sbox)
2054 : share_edge (&rb->sbox, &parent->sbox));
2055 if (rb->parent.expansion_area->flags.homeless)
2056 RB_up_count (rb->parent.expansion_area);
2057 rb->flags.homeless = 1;
2058 rb->flags.nobloat = 1;
2059 rb->style = AutoRouteParameters.style;
2060 rb->conflicts_with = parent->conflicts_with;
2061 /* we will never link an EXPANSION_AREA into the nets because they
2062 * are *ONLY* used for path searching. No need to call InitLists ()
2064 rb->came_from = src_edge->expand_dir;
2065 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
2066 showroutebox (rb);
2067 #endif /* ROUTE_DEBUG && DEBUG_SHOW_EXPANSION_BOXES */
2068 return rb;
2071 /*------ Expand ------*/
2072 struct E_result
2074 routebox_t *parent;
2075 routebox_t *n, *e, *s, *w;
2076 Coord keep, bloat;
2077 BoxType inflated, orig;
2078 int done;
2081 /* test method for Expand()
2082 * this routebox potentially is a blocker limiting expansion
2083 * if this is so, we limit the inflate box so another exactly
2084 * like it wouldn't be seen. We do this while keep the inflated
2085 * box as large as possible.
2087 static int
2088 __Expand_this_rect (const BoxType * box, void *cl)
2090 struct E_result *res = (struct E_result *) cl;
2091 routebox_t *rb = (routebox_t *) box;
2092 BoxType rbox;
2093 Coord dn, de, ds, dw, bloat;
2095 /* we don't see conflicts already encountered */
2096 if (rb->flags.touched)
2097 return 0;
2099 /* The inflated box outer edges include its own
2100 * track width plus its own keepaway.
2102 * To check for intersection, we need to expand
2103 * anything with greater keepaway by its excess
2104 * keepaway.
2106 * If something has nobloat then we need to shrink
2107 * the inflated box back and see if it still touches.
2110 if (rb->flags.nobloat)
2112 rbox = rb->sbox;
2113 bloat = res->bloat;
2114 if (rbox.X2 <= res->inflated.X1 + bloat ||
2115 rbox.X1 >= res->inflated.X2 - bloat ||
2116 rbox.Y1 >= res->inflated.Y2 - bloat ||
2117 rbox.Y2 <= res->inflated.Y1 + bloat)
2118 return 0; /* doesn't touch */
2120 else
2122 if (rb->style->Keepaway > res->keep)
2123 rbox = bloat_box (&rb->sbox, rb->style->Keepaway - res->keep);
2124 else
2125 rbox = rb->sbox;
2127 if (rbox.X2 <= res->inflated.X1 || rbox.X1 >= res->inflated.X2
2128 || rbox.Y1 >= res->inflated.Y2 || rbox.Y2 <= res->inflated.Y1)
2129 return 0; /* doesn't touch */
2130 bloat = 0;
2133 /* this is an intersecting box; it has to jump through a few more hoops */
2134 if (rb == res->parent || rb->parent.expansion_area == res->parent)
2135 return 0; /* don't see what we came from */
2137 /* if we are expanding a source edge, don't let other sources
2138 * or their expansions stop us.
2140 #if 1
2141 if (res->parent->flags.source)
2142 if (rb->flags.source
2143 || (rb->type == EXPANSION_AREA
2144 && rb->parent.expansion_area->flags.source))
2145 return 0;
2146 #endif
2148 /* we ignore via expansion boxes because maybe its
2149 * cheaper to get there without the via through
2150 * the path we're exploring now.
2152 if (rb->flags.is_via && rb->type == EXPANSION_AREA)
2153 return 0;
2155 if (rb->type == PLANE) /* expanding inside a plane is not good */
2157 if (rbox.X1 < res->orig.X1 && rbox.X2 > res->orig.X2 &&
2158 rbox.Y1 < res->orig.Y1 && rbox.Y2 > res->orig.Y2)
2160 res->inflated = bloat_box (&res->orig, res->bloat);
2161 return 1;
2164 /* calculate the distances from original box to this blocker */
2165 dn = de = ds = dw = 0;
2166 if (!(res->done & _NORTH) && rbox.Y1 <= res->orig.Y1
2167 && rbox.Y2 > res->inflated.Y1)
2168 dn = res->orig.Y1 - rbox.Y2;
2169 if (!(res->done & _EAST) && rbox.X2 >= res->orig.X2
2170 && rbox.X1 < res->inflated.X2)
2171 de = rbox.X1 - res->orig.X2;
2172 if (!(res->done & _SOUTH) && rbox.Y2 >= res->orig.Y2
2173 && rbox.Y1 < res->inflated.Y2)
2174 ds = rbox.Y1 - res->orig.Y2;
2175 if (!(res->done & _WEST) && rbox.X1 <= res->orig.X1
2176 && rbox.X2 > res->inflated.X1)
2177 dw = res->orig.X1 - rbox.X2;
2178 if (dn <= 0 && de <= 0 && ds <= 0 && dw <= 0)
2179 return 1;
2180 /* now shrink the inflated box to the largest blocking direction */
2181 if (dn >= de && dn >= ds && dn >= dw)
2183 res->inflated.Y1 = rbox.Y2 - bloat;
2184 res->n = rb;
2186 else if (de >= ds && de >= dw)
2188 res->inflated.X2 = rbox.X1 + bloat;
2189 res->e = rb;
2191 else if (ds >= dw)
2193 res->inflated.Y2 = rbox.Y1 + bloat;
2194 res->s = rb;
2196 else
2198 res->inflated.X1 = rbox.X2 - bloat;
2199 res->w = rb;
2201 return 1;
2204 static bool
2205 boink_box (routebox_t * rb, struct E_result *res, direction_t dir)
2207 Coord bloat;
2208 if (rb->style->Keepaway > res->keep)
2209 bloat = res->keep - rb->style->Keepaway;
2210 else
2211 bloat = 0;
2212 if (rb->flags.nobloat)
2213 bloat = res->bloat;
2214 switch (dir)
2216 case NORTH:
2217 case SOUTH:
2218 if (rb->sbox.X2 <= res->inflated.X1 + bloat
2219 || rb->sbox.X1 >= res->inflated.X2 - bloat)
2220 return false;
2221 return true;
2222 case EAST:
2223 case WEST:
2224 if (rb->sbox.Y1 >= res->inflated.Y2 - bloat
2225 || rb->sbox.Y2 <= res->inflated.Y1 + bloat)
2226 return false;
2227 return true;
2228 break;
2229 default:
2230 assert (0);
2232 return false;
2235 /* main Expand routine.
2237 * The expansion probe edge includes the keepaway and half thickness
2238 * as the search is performed in order to see everything relevant.
2239 * The result is backed off by this amount before being returned.
2240 * Targets (and other no-bloat routeboxes) go all the way to touching.
2241 * This is accomplished by backing off the probe edge when checking
2242 * for touch against such an object. Usually the expanding edge
2243 * bumps into neighboring pins on the same device that require a
2244 * keepaway, preventing seeing a target immediately. Rather than await
2245 * another expansion to actually touch the target, the edge breaker code
2246 * looks past the keepaway to see these targets even though they
2247 * weren't actually touched in the expansion.
2249 struct E_result *
2250 Expand (rtree_t * rtree, edge_t * e, const BoxType * box)
2252 static struct E_result ans;
2253 int noshrink; /* bit field of which edges to not shrink */
2255 ans.bloat = AutoRouteParameters.bloat;
2256 ans.orig = *box;
2257 ans.n = ans.e = ans.s = ans.w = NULL;
2259 /* the inflated box must be bloated in all directions that it might
2260 * hit something in order to guarantee that we see object in the
2261 * tree it might hit. The tree holds objects bloated by their own
2262 * keepaway so we are guaranteed to honor that.
2264 switch (e->expand_dir)
2266 case ALL:
2267 ans.inflated.X1 = (e->rb->came_from == EAST ? ans.orig.X1 : 0);
2268 ans.inflated.Y1 = (e->rb->came_from == SOUTH ? ans.orig.Y1 : 0);
2269 ans.inflated.X2 =
2270 (e->rb->came_from == WEST ? ans.orig.X2 : PCB->MaxWidth);
2271 ans.inflated.Y2 =
2272 (e->rb->came_from == NORTH ? ans.orig.Y2 : PCB->MaxHeight);
2273 if (e->rb->came_from == NORTH)
2274 ans.done = noshrink = _SOUTH;
2275 else if (e->rb->came_from == EAST)
2276 ans.done = noshrink = _WEST;
2277 else if (e->rb->came_from == SOUTH)
2278 ans.done = noshrink = _NORTH;
2279 else if (e->rb->came_from == WEST)
2280 ans.done = noshrink = _EAST;
2281 else
2282 ans.done = noshrink = 0;
2283 break;
2284 case NORTH:
2285 ans.done = _SOUTH + _EAST + _WEST;
2286 noshrink = _SOUTH;
2287 ans.inflated.X1 = box->X1 - ans.bloat;
2288 ans.inflated.X2 = box->X2 + ans.bloat;
2289 ans.inflated.Y2 = box->Y2;
2290 ans.inflated.Y1 = 0; /* far north */
2291 break;
2292 case NE:
2293 ans.done = _SOUTH + _WEST;
2294 noshrink = 0;
2295 ans.inflated.X1 = box->X1 - ans.bloat;
2296 ans.inflated.X2 = PCB->MaxWidth;
2297 ans.inflated.Y2 = box->Y2 + ans.bloat;
2298 ans.inflated.Y1 = 0;
2299 break;
2300 case EAST:
2301 ans.done = _NORTH + _SOUTH + _WEST;
2302 noshrink = _WEST;
2303 ans.inflated.Y1 = box->Y1 - ans.bloat;
2304 ans.inflated.Y2 = box->Y2 + ans.bloat;
2305 ans.inflated.X1 = box->X1;
2306 ans.inflated.X2 = PCB->MaxWidth;
2307 break;
2308 case SE:
2309 ans.done = _NORTH + _WEST;
2310 noshrink = 0;
2311 ans.inflated.X1 = box->X1 - ans.bloat;
2312 ans.inflated.X2 = PCB->MaxWidth;
2313 ans.inflated.Y2 = PCB->MaxHeight;
2314 ans.inflated.Y1 = box->Y1 - ans.bloat;
2315 break;
2316 case SOUTH:
2317 ans.done = _NORTH + _EAST + _WEST;
2318 noshrink = _NORTH;
2319 ans.inflated.X1 = box->X1 - ans.bloat;
2320 ans.inflated.X2 = box->X2 + ans.bloat;
2321 ans.inflated.Y1 = box->Y1;
2322 ans.inflated.Y2 = PCB->MaxHeight;
2323 break;
2324 case SW:
2325 ans.done = _NORTH + _EAST;
2326 noshrink = 0;
2327 ans.inflated.X1 = 0;
2328 ans.inflated.X2 = box->X2 + ans.bloat;
2329 ans.inflated.Y2 = PCB->MaxHeight;
2330 ans.inflated.Y1 = box->Y1 - ans.bloat;
2331 break;
2332 case WEST:
2333 ans.done = _NORTH + _SOUTH + _EAST;
2334 noshrink = _EAST;
2335 ans.inflated.Y1 = box->Y1 - ans.bloat;
2336 ans.inflated.Y2 = box->Y2 + ans.bloat;
2337 ans.inflated.X1 = 0;
2338 ans.inflated.X2 = box->X2;
2339 break;
2340 case NW:
2341 ans.done = _SOUTH + _EAST;
2342 noshrink = 0;
2343 ans.inflated.X1 = 0;
2344 ans.inflated.X2 = box->X2 + ans.bloat;
2345 ans.inflated.Y2 = box->Y2 + ans.bloat;
2346 ans.inflated.Y1 = 0;
2347 break;
2348 default:
2349 noshrink = ans.done = 0;
2350 assert (0);
2352 ans.keep = e->rb->style->Keepaway;
2353 ans.parent = nonhomeless_parent (e->rb);
2354 r_search (rtree, &ans.inflated, NULL, __Expand_this_rect, &ans);
2355 /* because the overlaping boxes are found in random order, some blockers
2356 * may have limited edges prematurely, so we check if the blockers realy
2357 * are blocking, and make another try if not
2359 if (ans.n && !boink_box (ans.n, &ans, NORTH))
2360 ans.inflated.Y1 = 0;
2361 else
2362 ans.done |= _NORTH;
2363 if (ans.e && !boink_box (ans.e, &ans, EAST))
2364 ans.inflated.X2 = PCB->MaxWidth;
2365 else
2366 ans.done |= _EAST;
2367 if (ans.s && !boink_box (ans.s, &ans, SOUTH))
2368 ans.inflated.Y2 = PCB->MaxHeight;
2369 else
2370 ans.done |= _SOUTH;
2371 if (ans.w && !boink_box (ans.w, &ans, WEST))
2372 ans.inflated.X1 = 0;
2373 else
2374 ans.done |= _WEST;
2375 if (ans.done != _NORTH + _EAST + _SOUTH + _WEST)
2377 r_search (rtree, &ans.inflated, NULL, __Expand_this_rect, &ans);
2379 if ((noshrink & _NORTH) == 0)
2380 ans.inflated.Y1 += ans.bloat;
2381 if ((noshrink & _EAST) == 0)
2382 ans.inflated.X2 -= ans.bloat;
2383 if ((noshrink & _SOUTH) == 0)
2384 ans.inflated.Y2 -= ans.bloat;
2385 if ((noshrink & _WEST) == 0)
2386 ans.inflated.X1 += ans.bloat;
2387 return &ans;
2390 /* blocker_to_heap puts the blockers into a heap so they
2391 * can be retrieved in clockwise order. If a blocker
2392 * is also a target, it gets put into the vector too.
2393 * It returns 1 for any fixed blocker that is not part
2394 * of this net and zero otherwise.
2396 static int
2397 blocker_to_heap (heap_t * heap, routebox_t * rb,
2398 BoxType * box, direction_t dir)
2400 BoxType b = rb->sbox;
2401 if (rb->style->Keepaway > AutoRouteParameters.style->Keepaway)
2403 bloat_box (&b,
2404 rb->style->Keepaway - AutoRouteParameters.style->Keepaway);
2405 b = clip_box (&b, box);
2406 assert (box_is_good (&b));
2407 /* we want to look at the blockers clockwise around the box */
2408 switch (dir)
2410 /* we need to use the other coordinate fraction to resolve
2411 * ties since we want the shorter of the furthest
2412 * first.
2414 case NORTH:
2415 heap_insert (heap, b.X1 - b.X1 / (b.X2 + 1.0), rb);
2416 break;
2417 case EAST:
2418 heap_insert (heap, b.Y1 - b.Y1 / (b.Y2 + 1.0), rb);
2419 break;
2420 case SOUTH:
2421 heap_insert (heap, -(b.X2 + b.X1 / (b.X2 + 1.0)), rb);
2422 break;
2423 case WEST:
2424 heap_insert (heap, -(b.Y2 + b.Y1 / (b.Y2 + 1.0)), rb);
2425 break;
2426 default:
2427 assert (0);
2429 if (rb->flags.fixed && !rb->flags.target && !rb->flags.source)
2430 return 1;
2431 return 0;
2434 /* this creates an EXPANSION_AREA to bridge small gaps or,
2435 * (more commonly) create a supper-thin box to provide a
2436 * home for an expansion edge.
2438 static routebox_t *
2439 CreateBridge (const BoxType * area, routebox_t * parent, direction_t dir)
2441 routebox_t *rb = (routebox_t *) malloc (sizeof (*rb));
2442 memset ((void *) rb, 0, sizeof (*rb));
2443 assert (area && parent);
2444 init_const_box (rb, area->X1, area->Y1, area->X2, area->Y2, 0);
2445 rb->group = parent->group;
2446 rb->type = EXPANSION_AREA;
2447 rb->came_from = dir;
2448 rb->cost_point = closest_point_in_box (&parent->cost_point, area);
2449 rb->cost = parent->cost + cost_to_point_on_layer (&parent->cost_point,
2450 &rb->cost_point,
2451 rb->group);
2452 rb->parent.expansion_area = route_parent (parent);
2453 if (rb->parent.expansion_area->flags.homeless)
2454 RB_up_count (rb->parent.expansion_area);
2455 rb->flags.homeless = 1;
2456 rb->flags.nobloat = 1;
2457 rb->style = parent->style;
2458 rb->conflicts_with = parent->conflicts_with;
2459 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EDGES)
2460 showroutebox (rb);
2461 #endif
2462 return rb;
2465 /* moveable_edge prepares the new search edges based on the
2466 * starting box, direction and blocker if any.
2468 void
2469 moveable_edge (vector_t * result, const BoxType * box, direction_t dir,
2470 routebox_t * rb,
2471 routebox_t * blocker, edge_t * e, rtree_t * targets,
2472 struct routeone_state *s, rtree_t * tree, vector_t * area_vec)
2474 BoxType b;
2475 assert (box_is_good (box));
2476 b = *box;
2477 /* for the cardinal directions, move the box to overlap the
2478 * the parent by 1 unit. Corner expansions overlap more
2479 * and their starting boxes are pre-prepared.
2480 * Check if anything is headed off the board edges
2482 switch (dir)
2484 default:
2485 break;
2486 case NORTH:
2487 b.Y2 = b.Y1;
2488 b.Y1--;
2489 if (b.Y1 <= AutoRouteParameters.bloat)
2490 return; /* off board edge */
2491 break;
2492 case EAST:
2493 b.X1 = b.X2;
2494 b.X2++;
2495 if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat)
2496 return; /* off board edge */
2497 break;
2498 case SOUTH:
2499 b.Y1 = b.Y2;
2500 b.Y2++;
2501 if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat)
2502 return; /* off board edge */
2503 break;
2504 case WEST:
2505 b.X2 = b.X1;
2506 b.X1--;
2507 if (b.X1 <= AutoRouteParameters.bloat)
2508 return; /* off board edge */
2509 break;
2510 case NE:
2511 if (b.Y1 <= AutoRouteParameters.bloat + 1
2512 && b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
2513 return; /* off board edge */
2514 if (b.Y1 <= AutoRouteParameters.bloat + 1)
2515 dir = EAST; /* north off board edge */
2516 if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
2517 dir = NORTH; /* east off board edge */
2518 break;
2519 case SE:
2520 if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1
2521 && b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
2522 return; /* off board edge */
2523 if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1)
2524 dir = EAST; /* south off board edge */
2525 if (b.X2 >= PCB->MaxWidth - AutoRouteParameters.bloat - 1)
2526 dir = SOUTH; /* east off board edge */
2527 break;
2528 case SW:
2529 if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1
2530 && b.X1 <= AutoRouteParameters.bloat + 1)
2531 return; /* off board edge */
2532 if (b.Y2 >= PCB->MaxHeight - AutoRouteParameters.bloat - 1)
2533 dir = WEST; /* south off board edge */
2534 if (b.X1 <= AutoRouteParameters.bloat + 1)
2535 dir = SOUTH; /* west off board edge */
2536 break;
2537 case NW:
2538 if (b.Y1 <= AutoRouteParameters.bloat + 1
2539 && b.X1 <= AutoRouteParameters.bloat + 1)
2540 return; /* off board edge */
2541 if (b.Y1 <= AutoRouteParameters.bloat + 1)
2542 dir = WEST; /* north off board edge */
2543 if (b.X1 <= AutoRouteParameters.bloat + 1)
2544 dir = NORTH; /* west off board edge */
2545 break;
2548 if (!blocker)
2550 edge_t *ne;
2551 routebox_t *nrb = CreateBridge (&b, rb, dir);
2552 /* move the cost point in corner expansions
2553 * these boxes are bigger, so move close to the target
2555 if (dir == NE || dir == SE || dir == SW || dir == NW)
2557 CheapPointType p;
2559 closest_point_in_box (&nrb->cost_point, &e->mincost_target->sbox);
2560 p = closest_point_in_box (&p, &b);
2561 nrb->cost += cost_to_point_on_layer (&p, &nrb->cost_point,
2562 nrb->group);
2563 nrb->cost_point = p;
2565 ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y,
2566 nrb->cost, NULL, dir, targets);
2567 vector_append (result, ne);
2569 else if (AutoRouteParameters.with_conflicts && !blocker->flags.target
2570 && !blocker->flags.fixed && !blocker->flags.touched &&
2571 !blocker->flags.source && blocker->type != EXPANSION_AREA)
2573 edge_t *ne;
2574 routebox_t *nrb;
2575 /* make a bridge to the edge of the blocker
2576 * in all directions from there
2578 switch (dir)
2580 case NORTH:
2581 b.Y1 = blocker->sbox.Y2 - 1;
2582 break;
2583 case EAST:
2584 b.X2 = blocker->sbox.X1 + 1;
2585 break;
2586 case SOUTH:
2587 b.Y2 = blocker->sbox.Y1 + 1;
2588 break;
2589 case WEST:
2590 b.X1 = blocker->sbox.X2 - 1;
2591 break;
2592 default:
2593 assert (0);
2595 if (!box_is_good (&b))
2596 return; /* how did this happen ? */
2597 nrb = CreateBridge (&b, rb, dir);
2598 r_insert_entry (tree, &nrb->box, 1);
2599 vector_append (area_vec, nrb);
2600 nrb->flags.homeless = 0; /* not homeless any more */
2601 /* mark this one as conflicted */
2602 path_conflicts (nrb, blocker, true);
2603 /* and make an expansion edge */
2604 nrb->cost_point =
2605 closest_point_in_box (&nrb->cost_point, &blocker->sbox);
2606 nrb->cost +=
2607 cost_to_point_on_layer (&nrb->parent.expansion_area->cost_point,
2608 &nrb->cost_point,
2609 nrb->group) * CONFLICT_PENALTY (blocker);
2611 ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y, nrb->cost,
2612 NULL, ALL, targets);
2613 ne->flags.is_interior = 1;
2614 vector_append (result, ne);
2616 #if 1
2617 else if (blocker->type == EXPANSION_AREA)
2619 if (blocker->cost < rb->cost || blocker->cost <= rb->cost +
2620 cost_to_point_on_layer (&blocker->cost_point, &rb->cost_point,
2621 rb->group))
2622 return;
2623 if (blocker->conflicts_with || rb->conflicts_with)
2624 return;
2625 /* does the blocker overlap this routebox ?? */
2626 /* does this re-parenting operation leave a memory leak? */
2627 if (blocker->parent.expansion_area->flags.homeless)
2628 RB_down_count (blocker->parent.expansion_area);
2629 blocker->parent.expansion_area = rb;
2630 return;
2632 #endif
2633 else if (blocker->flags.target)
2635 routebox_t *nrb;
2636 edge_t *ne;
2637 b = bloat_box (&b, 1);
2638 if (!box_intersect (&b, &blocker->sbox))
2640 /* if the expansion edge stopped before touching, expand the bridge */
2641 switch (dir)
2643 case NORTH:
2644 b.Y1 -= AutoRouteParameters.bloat + 1;
2645 break;
2646 case EAST:
2647 b.X2 += AutoRouteParameters.bloat + 1;
2648 break;
2649 case SOUTH:
2650 b.Y2 += AutoRouteParameters.bloat + 1;
2651 break;
2652 case WEST:
2653 b.X1 -= AutoRouteParameters.bloat + 1;
2654 break;
2655 default:
2656 assert (0);
2659 assert (box_intersect (&b, &blocker->sbox));
2660 b = shrink_box (&b, 1);
2661 nrb = CreateBridge (&b, rb, dir);
2662 r_insert_entry (tree, &nrb->box, 1);
2663 vector_append (area_vec, nrb);
2664 nrb->flags.homeless = 0; /* not homeless any more */
2665 ne = CreateEdge (nrb, nrb->cost_point.X, nrb->cost_point.Y,
2666 nrb->cost, blocker, dir, NULL);
2667 best_path_candidate (s, ne, blocker);
2668 DestroyEdge (&ne);
2672 struct break_info
2674 heap_t *heap;
2675 routebox_t *parent;
2676 BoxType box;
2677 direction_t dir;
2678 bool ignore_source;
2681 static int
2682 __GatherBlockers (const BoxType * box, void *cl)
2684 routebox_t *rb = (routebox_t *) box;
2685 struct break_info *bi = (struct break_info *) cl;
2686 BoxType b;
2688 if (bi->parent == rb || rb->flags.touched ||
2689 bi->parent->parent.expansion_area == rb)
2690 return 0;
2691 if (rb->flags.source && bi->ignore_source)
2692 return 0;
2693 b = rb->sbox;
2694 if (rb->style->Keepaway > AutoRouteParameters.style->Keepaway)
2696 bloat_box (&b,
2697 rb->style->Keepaway - AutoRouteParameters.style->Keepaway);
2698 if (b.X2 <= bi->box.X1 || b.X1 >= bi->box.X2
2699 || b.Y1 >= bi->box.Y2 || b.Y2 <= bi->box.Y1)
2700 return 0;
2701 return blocker_to_heap (bi->heap, rb, &bi->box, bi->dir);
2704 /* shrink the box to the last limit for the previous direction,
2705 * i.e. if dir is SOUTH, then this means fixing up an EAST leftover
2706 * edge, which would be the southern most edge for that example.
2708 static inline BoxType
2709 previous_edge (Coord last, direction_t i, const BoxType * b)
2711 BoxType db = *b;
2712 switch (i)
2714 case EAST:
2715 db.X1 = last;
2716 break;
2717 case SOUTH:
2718 db.Y1 = last;
2719 break;
2720 case WEST:
2721 db.X2 = last;
2722 break;
2723 default:
2724 Message ("previous edge bogus direction!");
2725 assert (0);
2727 return db;
2730 /* Break all the edges of the box that need breaking, handling
2731 * targets as they are found, and putting any moveable edges
2732 * in the return vector.
2734 vector_t *
2735 BreakManyEdges (struct routeone_state * s, rtree_t * targets, rtree_t * tree,
2736 vector_t * area_vec, struct E_result * ans, routebox_t * rb,
2737 edge_t * e)
2739 struct break_info bi;
2740 vector_t *edges;
2741 heap_t *heap[4];
2742 Coord first, last;
2743 Coord bloat;
2744 direction_t dir;
2745 routebox_t fake;
2747 edges = vector_create ();
2748 bi.ignore_source = rb->parent.expansion_area->flags.source;
2749 bi.parent = rb;
2750 /* we add 2 to the bloat.
2751 * 1 will get us to the actual blocker that Expand() hit
2752 * but 1 more is needed because the new expansion edges
2753 * move out by 1 so they don't overlap their parents
2754 * this extra expansion could "trap" the edge if
2755 * there is a blocker 2 units from the original rb,
2756 * it is 1 unit from the new expansion edge which
2757 * would prevent expansion. So we want to break the
2758 * edge on it now to avoid the trap.
2761 bloat = AutoRouteParameters.bloat + 2;
2762 /* for corner expansion, we need to have a fake blocker
2763 * to prevent expansion back where we came from since
2764 * we still need to break portions of all 4 edges
2766 if (e->expand_dir == NE || e->expand_dir == SE ||
2767 e->expand_dir == SW || e->expand_dir == NW)
2769 BoxType *fb = (BoxType *) &fake.sbox;
2770 memset (&fake, 0, sizeof (fake));
2771 *fb = e->rb->sbox;
2772 fake.flags.fixed = 1; /* this stops expansion there */
2773 fake.type = LINE;
2774 fake.style = AutoRouteParameters.style;
2775 #ifndef NDEBUG
2776 /* the routbox_is_good checker wants a lot more! */
2777 fake.flags.inited = 1;
2778 fb = (BoxType *) &fake.box;
2779 *fb = e->rb->sbox;
2780 fake.same_net.next = fake.same_net.prev = &fake;
2781 fake.same_subnet.next = fake.same_subnet.prev = &fake;
2782 fake.original_subnet.next = fake.original_subnet.prev = &fake;
2783 fake.different_net.next = fake.different_net.prev = &fake;
2784 #endif
2786 /* gather all of the blockers in heaps so they can be accessed
2787 * in clockwise order, which allows finding corners that can
2788 * be expanded.
2790 for (dir = NORTH; dir <= WEST; dir = directionIncrement(dir))
2792 /* don't break the edge we came from */
2793 if (e->expand_dir != ((dir + 2) % 4))
2795 heap[dir] = heap_create ();
2796 bi.box = bloat_box (&rb->sbox, bloat);
2797 bi.heap = heap[dir];
2798 bi.dir = dir;
2799 /* convert to edge */
2800 switch (dir)
2802 case NORTH:
2803 bi.box.Y2 = bi.box.Y1 + bloat + 1;
2804 /* for corner expansion, block the start edges and
2805 * limit the blocker search to only the new edge segment
2807 if (e->expand_dir == SE || e->expand_dir == SW)
2808 blocker_to_heap (heap[dir], &fake, &bi.box, dir);
2809 if (e->expand_dir == SE)
2810 bi.box.X1 = e->rb->sbox.X2;
2811 if (e->expand_dir == SW)
2812 bi.box.X2 = e->rb->sbox.X1;
2813 rb->n = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
2814 break;
2815 case EAST:
2816 bi.box.X1 = bi.box.X2 - bloat - 1;
2817 /* corner, same as above */
2818 if (e->expand_dir == SW || e->expand_dir == NW)
2819 blocker_to_heap (heap[dir], &fake, &bi.box, dir);
2820 if (e->expand_dir == SW)
2821 bi.box.Y1 = e->rb->sbox.Y2;
2822 if (e->expand_dir == NW)
2823 bi.box.Y2 = e->rb->sbox.Y1;
2824 rb->e = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
2825 break;
2826 case SOUTH:
2827 bi.box.Y1 = bi.box.Y2 - bloat - 1;
2828 /* corner, same as above */
2829 if (e->expand_dir == NE || e->expand_dir == NW)
2830 blocker_to_heap (heap[dir], &fake, &bi.box, dir);
2831 if (e->expand_dir == NE)
2832 bi.box.X1 = e->rb->sbox.X2;
2833 if (e->expand_dir == NW)
2834 bi.box.X2 = e->rb->sbox.X1;
2835 rb->s = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
2836 break;
2837 case WEST:
2838 bi.box.X2 = bi.box.X1 + bloat + 1;
2839 /* corner, same as above */
2840 if (e->expand_dir == NE || e->expand_dir == SE)
2841 blocker_to_heap (heap[dir], &fake, &bi.box, dir);
2842 if (e->expand_dir == SE)
2843 bi.box.Y1 = e->rb->sbox.Y2;
2844 if (e->expand_dir == NE)
2845 bi.box.Y2 = e->rb->sbox.Y1;
2846 rb->w = r_search (tree, &bi.box, NULL, __GatherBlockers, &bi);
2847 break;
2848 default:
2849 assert (0);
2852 else
2853 heap[dir] = NULL;
2855 #if 1
2856 rb->cost +=
2857 (rb->n + rb->e + rb->s +
2858 rb->w) * AutoRouteParameters.CongestionPenalty / box_area (rb->sbox);
2859 #endif
2860 /* now handle the blockers:
2861 * Go around the expansion area clockwise (North->East->South->West)
2862 * pulling blockers from the heap (which makes them come out in the right
2863 * order). Break the edges on the blocker and make the segments and corners
2864 * moveable as possible.
2866 first = last = -1;
2867 for (dir = NORTH; dir <= WEST; dir = directionIncrement(dir))
2869 if (heap[dir] && !heap_is_empty (heap[dir]))
2871 /* pull the very first one out of the heap outside of the
2872 * heap loop because it is special; it can be part of a corner
2874 routebox_t *blk = (routebox_t *) heap_remove_smallest (heap[dir]);
2875 BoxType b = rb->sbox;
2876 struct broken_boxes broke = break_box_edge (&b, dir, blk);
2877 if (broke.is_valid_left)
2879 /* if last > 0, then the previous edge had a segment
2880 * joining this one, so it forms a valid corner expansion
2882 if (last > 0)
2884 /* make a corner expansion */
2885 BoxType db = b;
2886 switch (dir)
2888 case EAST:
2889 /* possible NE expansion */
2890 db.X1 = last;
2891 db.Y2 = MIN (db.Y2, broke.left.Y2);
2892 break;
2893 case SOUTH:
2894 /* possible SE expansion */
2895 db.Y1 = last;
2896 db.X1 = MAX (db.X1, broke.left.X1);
2897 break;
2898 case WEST:
2899 /* possible SW expansion */
2900 db.X2 = last;
2901 db.Y1 = MAX (db.Y1, broke.left.Y1);
2902 break;
2903 default:
2904 assert (0);
2905 break;
2907 moveable_edge (edges, &db, (direction_t)(dir + 3), rb, NULL, e, targets,
2908 s, NULL, NULL);
2910 else if (dir == NORTH) /* north is start, so nothing "before" it */
2912 /* save for a possible corner once we've
2913 * finished circling the box
2915 first = MAX (b.X1, broke.left.X2);
2917 else
2919 /* this is just a boring straight expansion
2920 * since the orthogonal segment was blocked
2922 moveable_edge (edges, &broke.left, dir, rb, NULL, e,
2923 targets, s, NULL, NULL);
2925 } /* broke.is_valid_left */
2926 else if (last > 0)
2928 /* if the last one didn't become a corner,
2929 * we still want to expand it straight out
2930 * in the direction of the previous edge,
2931 * which it belongs to.
2933 BoxType db = previous_edge (last, dir, &rb->sbox);
2934 moveable_edge (edges, &db, (direction_t)(dir - 1), rb, NULL, e, targets, s,
2935 NULL, NULL);
2937 if (broke.is_valid_center && !blk->flags.source)
2938 moveable_edge (edges, &broke.center, dir, rb, blk, e, targets, s,
2939 tree, area_vec);
2940 /* this is the heap extraction loop. We break out
2941 * if there's nothing left in the heap, but if we * are blocked all the way to the far edge, we can
2942 * just leave stuff in the heap when it is destroyed
2944 while (broke.is_valid_right)
2946 /* move the box edge to the next potential free point */
2947 switch (dir)
2949 case NORTH:
2950 last = b.X1 = MAX (broke.right.X1, b.X1);
2951 break;
2952 case EAST:
2953 last = b.Y1 = MAX (broke.right.Y1, b.Y1);
2954 break;
2955 case SOUTH:
2956 last = b.X2 = MIN (broke.right.X2, b.X2);
2957 break;
2958 case WEST:
2959 last = b.Y2 = MIN (broke.right.Y2, b.Y2);
2960 break;
2961 default:
2962 assert (0);
2964 if (heap_is_empty (heap[dir]))
2965 break;
2966 blk = (routebox_t *)heap_remove_smallest (heap[dir]);
2967 broke = break_box_edge (&b, dir, blk);
2968 if (broke.is_valid_left)
2969 moveable_edge (edges, &broke.left, dir, rb, NULL, e, targets,
2970 s, NULL, NULL);
2971 if (broke.is_valid_center && !blk->flags.source)
2972 moveable_edge (edges, &broke.center, dir, rb, blk, e, targets,
2973 s, tree, area_vec);
2975 if (!broke.is_valid_right)
2976 last = -1;
2978 else /* if (heap[dir]) */
2980 /* nothing touched this edge! Expand the whole edge unless
2981 * (1) it hit the board edge or (2) was the source of our expansion
2983 * for this case (of hitting nothing) we give up trying for corner
2984 * expansions because it is likely that they're not possible anyway
2986 if ((e->expand_dir == ALL ? e->rb->came_from : e->expand_dir) !=
2987 ((dir + 2) % 4))
2989 /* ok, we are not going back on ourselves, and the whole edge seems free */
2990 moveable_edge (edges, &rb->sbox, dir, rb, NULL, e, targets, s,
2991 NULL, NULL);
2994 if (last > 0)
2996 /* expand the leftover from the prior direction */
2997 BoxType db = previous_edge (last, dir, &rb->sbox);
2998 moveable_edge (edges, &db, (direction_t)(dir - 1), rb, NULL, e, targets, s,
2999 NULL, NULL);
3001 last = -1;
3003 } /* for loop */
3004 /* finally, check for the NW corner now that we've come full circle */
3005 if (first > 0 && last > 0)
3007 BoxType db = rb->sbox;
3008 db.X2 = first;
3009 db.Y2 = last;
3010 moveable_edge (edges, &db, NW, rb, NULL, e, targets, s, NULL, NULL);
3012 else
3014 if (first > 0)
3016 BoxType db = rb->sbox;
3017 db.X2 = first;
3018 moveable_edge (edges, &db, NORTH, rb, NULL, e, targets, s, NULL,
3019 NULL);
3021 else if (last > 0)
3023 BoxType db = rb->sbox;
3024 db.Y2 = last;
3025 moveable_edge (edges, &db, WEST, rb, NULL, e, targets, s, NULL,
3026 NULL);
3029 /* done with all expansion edges of this box */
3030 for (dir = NORTH; dir <= WEST; dir = directionIncrement(dir))
3032 if (heap[dir])
3033 heap_destroy (&heap[dir]);
3035 return edges;
3038 static routebox_t *
3039 rb_source (routebox_t * rb)
3041 while (rb && !rb->flags.source)
3043 assert (rb->type == EXPANSION_AREA);
3044 rb = rb->parent.expansion_area;
3046 assert (rb);
3047 return rb;
3050 /* ------------ */
3052 struct foib_info
3054 const BoxType *box;
3055 routebox_t *intersect;
3056 jmp_buf env;
3059 static int
3060 foib_rect_in_reg (const BoxType * box, void *cl)
3062 struct foib_info *foib = (struct foib_info *) cl;
3063 BoxType rbox;
3064 routebox_t *rb = (routebox_t *) box;
3065 if (rb->flags.touched)
3066 return 0;
3067 // if (rb->type == EXPANSION_AREA && !rb->flags.is_via)
3068 // return 0;
3069 rbox = bloat_routebox (rb);
3070 if (!box_intersect (&rbox, foib->box))
3071 return 0;
3072 /* this is an intersector! */
3073 foib->intersect = (routebox_t *) box;
3074 longjmp (foib->env, 1); /* skip to the end! */
3075 return 1;
3077 static routebox_t *
3078 FindOneInBox (rtree_t * rtree, routebox_t * rb)
3080 struct foib_info foib;
3081 BoxType r;
3083 r = rb->sbox;
3084 foib.box = &r;
3085 foib.intersect = NULL;
3087 if (setjmp (foib.env) == 0)
3088 r_search (rtree, &r, NULL, foib_rect_in_reg, &foib);
3089 return foib.intersect;
3092 struct therm_info
3094 routebox_t *plane;
3095 BoxType query;
3096 jmp_buf env;
3098 static int
3099 ftherm_rect_in_reg (const BoxType * box, void *cl)
3101 routebox_t *rbox = (routebox_t *) box;
3102 struct therm_info *ti = (struct therm_info *) cl;
3103 BoxType sq, sb;
3105 if (rbox->type != PIN && rbox->type != VIA && rbox->type != VIA_SHADOW)
3106 return 0;
3107 if (rbox->group != ti->plane->group)
3108 return 0;
3110 sb = shrink_routebox (rbox);
3111 switch (rbox->type)
3113 case PIN:
3114 sq = shrink_box (&ti->query, rbox->parent.pin->Thickness);
3115 if (!box_intersect (&sb, &sq))
3116 return 0;
3117 sb.X1 = rbox->parent.pin->X;
3118 sb.Y1 = rbox->parent.pin->Y;
3119 break;
3120 case VIA:
3121 if (rbox->flags.fixed)
3123 sq = shrink_box (&ti->query, rbox->parent.via->Thickness);
3124 sb.X1 = rbox->parent.pin->X;
3125 sb.Y1 = rbox->parent.pin->Y;
3127 else
3129 sq = shrink_box (&ti->query, rbox->style->Diameter);
3130 sb.X1 = CENTER_X (sb);
3131 sb.Y1 = CENTER_Y (sb);
3133 if (!box_intersect (&sb, &sq))
3134 return 0;
3135 break;
3136 case VIA_SHADOW:
3137 sq = shrink_box (&ti->query, rbox->style->Diameter);
3138 if (!box_intersect (&sb, &sq))
3139 return 0;
3140 sb.X1 = CENTER_X (sb);
3141 sb.Y1 = CENTER_Y (sb);
3142 break;
3143 default:
3144 assert (0);
3146 ti->plane = rbox;
3147 longjmp (ti->env, 1);
3148 return 1;
3151 /* check for a pin or via target that a polygon can just use a thermal to connect to */
3152 routebox_t *
3153 FindThermable (rtree_t * rtree, routebox_t * rb)
3155 struct therm_info info;
3157 info.plane = rb;
3158 info.query = shrink_routebox (rb);
3160 if (setjmp (info.env) == 0)
3162 r_search (rtree, &info.query, NULL, ftherm_rect_in_reg, &info);
3163 return NULL;
3165 return info.plane;
3168 /*--------------------------------------------------------------------
3169 * Route-tracing code: once we've got a path of expansion boxes, trace
3170 * a line through them to actually create the connection.
3172 static void
3173 RD_DrawThermal (routedata_t * rd, Coord X, Coord Y,
3174 Cardinal group, Cardinal layer, routebox_t * subnet,
3175 bool is_bad)
3177 routebox_t *rb;
3178 rb = (routebox_t *) malloc (sizeof (*rb));
3179 memset ((void *) rb, 0, sizeof (*rb));
3180 init_const_box (rb, X, Y, X + 1, Y + 1, 0);
3181 rb->group = group;
3182 rb->layer = layer;
3183 rb->flags.fixed = 0;
3184 rb->flags.is_bad = is_bad;
3185 rb->flags.is_odd = AutoRouteParameters.is_odd;
3186 rb->flags.circular = 0;
3187 rb->style = AutoRouteParameters.style;
3188 rb->type = THERMAL;
3189 InitLists (rb);
3190 MergeNets (rb, subnet, NET);
3191 MergeNets (rb, subnet, SUBNET);
3192 /* add it to the r-tree, this may be the whole route! */
3193 r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
3194 rb->flags.homeless = 0;
3197 static void
3198 RD_DrawVia (routedata_t * rd, Coord X, Coord Y,
3199 Coord radius, routebox_t * subnet, bool is_bad)
3201 routebox_t *rb, *first_via = NULL;
3202 int i;
3203 int ka = AutoRouteParameters.style->Keepaway;
3204 PinType *live_via = NULL;
3206 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
3208 live_via = CreateNewVia (PCB->Data, X, Y, radius * 2,
3209 2 * AutoRouteParameters.style->Keepaway, 0,
3210 AutoRouteParameters.style->Hole, NULL,
3211 MakeFlags (0));
3212 if (live_via != NULL)
3213 DrawVia (live_via);
3216 /* a via cuts through every layer group */
3217 for (i = 0; i < max_group; i++)
3219 if (!is_layer_group_active[i])
3220 continue;
3221 rb = (routebox_t *) malloc (sizeof (*rb));
3222 memset ((void *) rb, 0, sizeof (*rb));
3223 init_const_box (rb,
3224 /*X1 */ X - radius, /*Y1 */ Y - radius,
3225 /*X2 */ X + radius + 1, /*Y2 */ Y + radius + 1, ka);
3226 rb->group = i;
3227 rb->flags.fixed = 0; /* indicates that not on PCB yet */
3228 rb->flags.is_odd = AutoRouteParameters.is_odd;
3229 rb->flags.is_bad = is_bad;
3230 rb->came_from = ALL;
3231 rb->flags.circular = true;
3232 rb->style = AutoRouteParameters.style;
3233 rb->pass = AutoRouteParameters.pass;
3234 if (first_via == NULL)
3236 rb->type = VIA;
3237 rb->parent.via = NULL; /* indicates that not on PCB yet */
3238 first_via = rb;
3239 /* only add the first via to mtspace, not the shadows too */
3240 mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN,
3241 rb->style->Keepaway);
3243 else
3245 rb->type = VIA_SHADOW;
3246 rb->parent.via_shadow = first_via;
3248 InitLists (rb);
3249 /* add these to proper subnet. */
3250 MergeNets (rb, subnet, NET);
3251 MergeNets (rb, subnet, SUBNET);
3252 assert (__routebox_is_good (rb));
3253 /* and add it to the r-tree! */
3254 r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
3255 rb->flags.homeless = 0; /* not homeless anymore */
3256 rb->livedraw_obj.via = live_via;
3259 static void
3260 RD_DrawLine (routedata_t * rd,
3261 Coord X1, Coord Y1, Coord X2,
3262 Coord Y2, Coord halfthick, Cardinal group,
3263 routebox_t * subnet, bool is_bad, bool is_45)
3265 /* we hold the line in a queue to concatenate segments that
3266 * ajoin one another. That reduces the number of things in
3267 * the trees and allows conflict boxes to be larger, both of
3268 * which are really useful.
3270 static Coord qX1 = -1, qY1, qX2, qY2;
3271 static Coord qhthick;
3272 static Cardinal qgroup;
3273 static bool qis_45, qis_bad;
3274 static routebox_t *qsn;
3276 routebox_t *rb;
3277 Coord ka = AutoRouteParameters.style->Keepaway;
3279 /* don't draw zero-length segments. */
3280 if (X1 == X2 && Y1 == Y2)
3281 return;
3282 if (qX1 == -1) /* first ever */
3284 qX1 = X1;
3285 qY1 = Y1;
3286 qX2 = X2;
3287 qY2 = Y2;
3288 qhthick = halfthick;
3289 qgroup = group;
3290 qis_45 = is_45;
3291 qis_bad = is_bad;
3292 qsn = subnet;
3293 return;
3295 /* Check if the lines concatenat. We only check the
3296 * normal expected nextpoint=lastpoint condition
3298 if (X1 == qX2 && Y1 == qY2 && qhthick == halfthick && qgroup == group)
3300 if (qX1 == qX2 && X1 == X2) /* everybody on the same X here */
3302 qY2 = Y2;
3303 return;
3305 if (qY1 == qY2 && Y1 == Y2) /* same Y all around */
3307 qX2 = X2;
3308 return;
3311 /* dump the queue, no match here */
3312 if (qX1 == -1)
3313 return; /* but not this! */
3314 rb = (routebox_t *) malloc (sizeof (*rb));
3315 memset ((void *) rb, 0, sizeof (*rb));
3316 assert (is_45 ? (ABS (qX2 - qX1) == ABS (qY2 - qY1)) /* line must be 45-degrees */
3317 : (qX1 == qX2 || qY1 == qY2) /* line must be ortho */ );
3318 init_const_box (rb,
3319 /*X1 */ MIN (qX1, qX2) - qhthick,
3320 /*Y1 */ MIN (qY1, qY2) - qhthick,
3321 /*X2 */ MAX (qX1, qX2) + qhthick + 1,
3322 /*Y2 */ MAX (qY1, qY2) + qhthick + 1, ka);
3323 rb->group = qgroup;
3324 rb->type = LINE;
3325 rb->parent.line = NULL; /* indicates that not on PCB yet */
3326 rb->flags.fixed = 0; /* indicates that not on PCB yet */
3327 rb->flags.is_odd = AutoRouteParameters.is_odd;
3328 rb->flags.is_bad = qis_bad;
3329 rb->came_from = ALL;
3330 rb->flags.homeless = 0; /* we're putting this in the tree */
3331 rb->flags.nonstraight = qis_45;
3332 rb->flags.bl_to_ur = ((qX2 >= qX1 && qY2 <= qY1)
3333 || (qX2 <= qX1 && qY2 >= qY1));
3334 rb->style = AutoRouteParameters.style;
3335 rb->pass = AutoRouteParameters.pass;
3336 InitLists (rb);
3337 /* add these to proper subnet. */
3338 MergeNets (rb, qsn, NET);
3339 MergeNets (rb, qsn, SUBNET);
3340 assert (__routebox_is_good (rb));
3341 /* and add it to the r-tree! */
3342 r_insert_entry (rd->layergrouptree[rb->group], &rb->box, 1);
3344 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
3346 LayerType *layer = LAYER_PTR (PCB->LayerGroups.Entries[rb->group][0]);
3347 LineType *line = CreateNewLineOnLayer (layer, qX1, qY1, qX2, qY2,
3348 2 * qhthick, 0, MakeFlags (0));
3349 rb->livedraw_obj.line = line;
3350 if (line != NULL)
3351 DrawLine (layer, line);
3354 /* and to the via space structures */
3355 if (AutoRouteParameters.use_vias)
3356 mtspace_add (rd->mtspace, &rb->box, rb->flags.is_odd ? ODD : EVEN,
3357 rb->style->Keepaway);
3358 usedGroup[rb->group] = true;
3359 /* and queue this one */
3360 qX1 = X1;
3361 qY1 = Y1;
3362 qX2 = X2;
3363 qY2 = Y2;
3364 qhthick = halfthick;
3365 qgroup = group;
3366 qis_45 = is_45;
3367 qis_bad = is_bad;
3368 qsn = subnet;
3371 static bool
3372 RD_DrawManhattanLine (routedata_t * rd,
3373 const BoxType * box1, const BoxType * box2,
3374 CheapPointType start, CheapPointType end,
3375 Coord halfthick, Cardinal group,
3376 routebox_t * subnet, bool is_bad, bool last_was_x)
3378 CheapPointType knee = start;
3379 if (end.X == start.X)
3381 RD_DrawLine (rd, start.X, start.Y, end.X, end.Y, halfthick, group,
3382 subnet, is_bad, false);
3383 return false;
3385 else if (end.Y == start.Y)
3387 RD_DrawLine (rd, start.X, start.Y, end.X, end.Y, halfthick, group,
3388 subnet, is_bad, false);
3389 return true;
3391 /* find where knee belongs */
3392 if (point_in_box (box1, end.X, start.Y)
3393 || point_in_box (box2, end.X, start.Y))
3395 knee.X = end.X;
3396 knee.Y = start.Y;
3398 else
3400 knee.X = start.X;
3401 knee.Y = end.Y;
3403 if ((knee.X == end.X && !last_was_x) &&
3404 (point_in_box (box1, start.X, end.Y)
3405 || point_in_box (box2, start.X, end.Y)))
3407 knee.X = start.X;
3408 knee.Y = end.Y;
3410 assert (AutoRouteParameters.is_smoothing
3411 || point_in_closed_box (box1, knee.X, knee.Y)
3412 || point_in_closed_box (box2, knee.X, knee.Y));
3414 if (1 || !AutoRouteParameters.is_smoothing)
3416 /* draw standard manhattan paths */
3417 RD_DrawLine (rd, start.X, start.Y, knee.X, knee.Y, halfthick, group,
3418 subnet, is_bad, false);
3419 RD_DrawLine (rd, knee.X, knee.Y, end.X, end.Y, halfthick, group,
3420 subnet, is_bad, false);
3422 else
3424 /* draw 45-degree path across knee */
3425 Coord len45 = MIN (ABS (start.X - end.X), ABS (start.Y - end.Y));
3426 CheapPointType kneestart = knee, kneeend = knee;
3427 if (kneestart.X == start.X)
3428 kneestart.Y += (kneestart.Y > start.Y) ? -len45 : len45;
3429 else
3430 kneestart.X += (kneestart.X > start.X) ? -len45 : len45;
3431 if (kneeend.X == end.X)
3432 kneeend.Y += (kneeend.Y > end.Y) ? -len45 : len45;
3433 else
3434 kneeend.X += (kneeend.X > end.X) ? -len45 : len45;
3435 RD_DrawLine (rd, start.X, start.Y, kneestart.X, kneestart.Y, halfthick,
3436 group, subnet, is_bad, false);
3437 RD_DrawLine (rd, kneestart.X, kneestart.Y, kneeend.X, kneeend.Y,
3438 halfthick, group, subnet, is_bad, true);
3439 RD_DrawLine (rd, kneeend.X, kneeend.Y, end.X, end.Y, halfthick, group,
3440 subnet, is_bad, false);
3442 return (knee.X != end.X);
3445 /* for smoothing, don't pack traces to min clearance gratuitously */
3446 #if 0
3447 static void
3448 add_clearance (CheapPointType * nextpoint, const BoxType * b)
3450 if (nextpoint->X == b->X1)
3452 if (nextpoint->X +
3453 AutoRouteParameters.style->Keepaway < (b->X1 + b->X2) / 2)
3454 nextpoint->X += AutoRouteParameters.style->Keepaway;
3455 else
3456 nextpoint->X = (b->X1 + b->X2) / 2;
3458 else if (nextpoint->X == b->X2)
3460 if (nextpoint->X -
3461 AutoRouteParameters.style->Keepaway > (b->X1 + b->X2) / 2)
3462 nextpoint->X -= AutoRouteParameters.style->Keepaway;
3463 else
3464 nextpoint->X = (b->X1 + b->X2) / 2;
3466 else if (nextpoint->Y == b->Y1)
3468 if (nextpoint->Y +
3469 AutoRouteParameters.style->Keepaway < (b->Y1 + b->Y2) / 2)
3470 nextpoint->Y += AutoRouteParameters.style->Keepaway;
3471 else
3472 nextpoint->Y = (b->Y1 + b->Y2) / 2;
3474 else if (nextpoint->Y == b->Y2)
3476 if (nextpoint->Y -
3477 AutoRouteParameters.style->Keepaway > (b->Y1 + b->Y2) / 2)
3478 nextpoint->Y -= AutoRouteParameters.style->Keepaway;
3479 else
3480 nextpoint->Y = (b->Y1 + b->Y2) / 2;
3483 #endif
3485 /* This back-traces the expansion boxes along the best path
3486 * it draws the lines that will make the actual path.
3487 * during refinement passes, it should try to maximize the area
3488 * for other tracks so routing completion is easier.
3490 * during smoothing passes, it should try to make a better path,
3491 * possibly using diagonals, etc. The path boxes are larger on
3492 * average now so there is more possiblity to decide on a nice
3493 * path. Any combination of lines and arcs is possible, so long
3494 * as they don't poke more than half thick outside the path box.
3497 static void
3498 TracePath (routedata_t * rd, routebox_t * path, const routebox_t * target,
3499 routebox_t * subnet, bool is_bad)
3501 bool last_x = false;
3502 Coord halfwidth = HALF_THICK (AutoRouteParameters.style->Thick);
3503 Coord radius = HALF_THICK (AutoRouteParameters.style->Diameter);
3504 CheapPointType lastpoint, nextpoint;
3505 routebox_t *lastpath;
3506 BoxType b;
3508 assert (subnet->style == AutoRouteParameters.style);
3509 /*XXX: because we round up odd thicknesses, there's the possibility that
3510 * a connecting line end-point might be 0.005 mil off the "real" edge.
3511 * don't worry about this because line *thicknesses* are always >= 0.01 mil. */
3513 /* if we start with a thermal the target was a plane
3514 * or the target was a pin and the source a plane
3515 * in which case this thermal is the whole path
3517 if (path->flags.is_thermal)
3519 /* the target was a plane, so we need to find a good spot for the via
3520 * now. It's logical to place it close to the source box which
3521 * is where we're utlimately headed on this path. However, it
3522 * must reside in the plane as well as the via area too.
3524 nextpoint.X = CENTER_X (path->sbox);
3525 nextpoint.Y = CENTER_Y (path->sbox);
3526 if (path->parent.expansion_area->flags.is_via)
3528 TargetPoint (&nextpoint, rb_source (path));
3529 /* nextpoint is the middle of the source terminal now */
3530 b = clip_box (&path->sbox, &path->parent.expansion_area->sbox);
3531 nextpoint = closest_point_in_box (&nextpoint, &b);
3532 /* now it's in the via and plane near the source */
3534 else /* no via coming, target must have been a pin */
3536 assert (target->type == PIN);
3537 TargetPoint (&nextpoint, target);
3539 assert (point_in_box (&path->sbox, nextpoint.X, nextpoint.Y));
3540 RD_DrawThermal (rd, nextpoint.X, nextpoint.Y, path->group,
3541 path->layer, subnet, is_bad);
3543 else
3545 /* start from best place of target box */
3546 lastpoint.X = CENTER_X (target->sbox);
3547 lastpoint.Y = CENTER_Y (target->sbox);
3548 TargetPoint (&lastpoint, target);
3549 if (AutoRouteParameters.last_smooth
3550 && box_in_box (&path->sbox, &target->sbox))
3551 path = path->parent.expansion_area;
3552 b = path->sbox;
3553 if (path->flags.circular)
3554 b = shrink_box (&b, MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 5);
3555 nextpoint = closest_point_in_box (&lastpoint, &b);
3556 if (AutoRouteParameters.last_smooth)
3557 RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
3558 halfwidth, path->group, subnet, is_bad, TRUE);
3559 else
3560 last_x = RD_DrawManhattanLine (rd, &target->sbox, &path->sbox,
3561 lastpoint, nextpoint, halfwidth,
3562 path->group, subnet, is_bad, last_x);
3564 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
3565 showroutebox (path);
3566 #if defined(ROUTE_VERBOSE)
3567 pcb_printf ("TRACEPOINT start %#mD\n", nextpoint.X, nextpoint.Y);
3568 #endif
3569 #endif
3573 lastpoint = nextpoint;
3574 lastpath = path;
3575 assert (path->type == EXPANSION_AREA);
3576 path = path->parent.expansion_area;
3577 b = path->sbox;
3578 if (path->flags.circular)
3579 b = shrink_box (&b, MIN (b.X2 - b.X1, b.Y2 - b.Y1) / 5);
3580 assert (b.X1 != b.X2 && b.Y1 != b.Y2); /* need someplace to put line! */
3581 /* find point on path perimeter closest to last point */
3582 /* if source terminal, try to hit a good place */
3583 nextpoint = closest_point_in_box (&lastpoint, &b);
3584 #if 0
3585 /* leave more clearance if this is a smoothing pass */
3586 if (AutoRouteParameters.is_smoothing &&
3587 (nextpoint.X != lastpoint.X || nextpoint.Y != lastpoint.Y))
3588 add_clearance (&nextpoint, &b);
3589 #endif
3590 if (path->flags.source && path->type != PLANE)
3591 TargetPoint (&nextpoint, path);
3592 assert (point_in_box (&lastpath->box, lastpoint.X, lastpoint.Y));
3593 assert (point_in_box (&path->box, nextpoint.X, nextpoint.Y));
3594 #if defined(ROUTE_DEBUG_VERBOSE)
3595 printf ("TRACEPATH: ");
3596 DumpRouteBox (path);
3597 pcb_printf ("TRACEPATH: point %#mD to point %#mD layer %d\n",
3598 lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
3599 path->group);
3600 #endif
3602 /* draw orthogonal lines from lastpoint to nextpoint */
3603 /* knee is placed in lastpath box */
3604 /* should never cause line to leave union of lastpath/path boxes */
3605 if (AutoRouteParameters.last_smooth)
3606 RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X, nextpoint.Y,
3607 halfwidth, path->group, subnet, is_bad, TRUE);
3608 else
3609 last_x = RD_DrawManhattanLine (rd, &lastpath->sbox, &path->sbox,
3610 lastpoint, nextpoint, halfwidth,
3611 path->group, subnet, is_bad, last_x);
3612 if (path->flags.is_via)
3613 { /* if via, then add via */
3614 #ifdef ROUTE_VERBOSE
3615 printf (" (vias)");
3616 #endif
3617 assert (point_in_box (&path->box, nextpoint.X, nextpoint.Y));
3618 RD_DrawVia (rd, nextpoint.X, nextpoint.Y, radius, subnet, is_bad);
3621 assert (lastpath->flags.is_via || path->group == lastpath->group);
3623 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
3624 showroutebox (path);
3625 #endif /* ROUTE_DEBUG && DEBUG_SHOW_ROUTE_BOXES */
3626 /* if this is connected to a plane, draw the thermal */
3627 if (path->flags.is_thermal || path->type == PLANE)
3628 RD_DrawThermal (rd, lastpoint.X, lastpoint.Y, path->group,
3629 path->layer, subnet, is_bad);
3630 /* when one hop from the source, make an extra path in *this* box */
3631 if (path->type == EXPANSION_AREA
3632 && path->parent.expansion_area->flags.source
3633 && path->parent.expansion_area->type != PLANE)
3635 /* find special point on source (if it exists) */
3636 if (TargetPoint (&lastpoint, path->parent.expansion_area))
3638 lastpoint = closest_point_in_routebox (&lastpoint, path);
3639 b = shrink_routebox (path);
3640 #if 0
3641 if (AutoRouteParameters.is_smoothing)
3642 add_clearance (&lastpoint, &b);
3643 #else
3644 if (AutoRouteParameters.last_smooth)
3645 RD_DrawLine (rd, lastpoint.X, lastpoint.Y, nextpoint.X,
3646 nextpoint.Y, halfwidth, path->group, subnet,
3647 is_bad, TRUE);
3648 else
3649 #endif
3650 last_x = RD_DrawManhattanLine (rd, &b, &b,
3651 nextpoint, lastpoint,
3652 halfwidth, path->group, subnet,
3653 is_bad, last_x);
3654 #if defined(ROUTE_DEBUG_VERBOSE)
3655 printf ("TRACEPATH: ");
3656 DumpRouteBox (path);
3657 pcb_printf
3658 ("TRACEPATH: (to source) point %#mD to point %#mD layer %d\n",
3659 nextpoint.X, nextpoint.Y, lastpoint.X, lastpoint.Y,
3660 path->group);
3661 #endif
3663 nextpoint = lastpoint;
3667 while (!path->flags.source);
3668 /* flush the line queue */
3669 RD_DrawLine (rd, -1, 0, 0, 0, 0, 0, NULL, false, false);
3671 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
3672 Draw ();
3674 #ifdef ROUTE_DEBUG
3675 if (ddraw != NULL)
3676 ddraw->flush_debug_draw ();
3677 #endif
3680 /* create a fake "edge" used to defer via site searching. */
3681 static void
3682 CreateSearchEdge (struct routeone_state *s, vetting_t * work, edge_t * parent,
3683 routebox_t * rb, conflict_t conflict, rtree_t * targets,
3684 bool in_plane)
3686 routebox_t *target;
3687 BoxType b;
3688 cost_t cost;
3689 assert (__routebox_is_good (rb));
3690 /* find the cheapest target */
3691 #if 0
3692 target =
3693 mincost_target_to_point (&parent->cost_point, max_group + 1, targets,
3694 parent->mincost_target);
3695 #else
3696 target = parent->mincost_target;
3697 #endif
3698 b = shrink_routebox (target);
3699 cost =
3700 parent->cost_to_point + AutoRouteParameters.ViaCost +
3701 cost_to_layerless_box (&rb->cost_point, 0, &b);
3702 if (cost < s->best_cost)
3704 edge_t *ne;
3705 ne = (edge_t *)malloc (sizeof (*ne));
3706 memset ((void *) ne, 0, sizeof (*ne));
3707 assert (ne);
3708 ne->flags.via_search = 1;
3709 ne->flags.in_plane = in_plane;
3710 ne->rb = rb;
3711 if (rb->flags.homeless)
3712 RB_up_count (rb);
3713 ne->work = work;
3714 ne->mincost_target = target;
3715 ne->flags.via_conflict_level = conflict;
3716 ne->cost_to_point = parent->cost_to_point;
3717 ne->cost_point = parent->cost_point;
3718 ne->cost = cost;
3719 heap_insert (s->workheap, ne->cost, ne);
3721 else
3723 mtsFreeWork (&work);
3727 static void
3728 add_or_destroy_edge (struct routeone_state *s, edge_t * e)
3730 e->cost = edge_cost (e, s->best_cost);
3731 assert (__edge_is_good (e));
3732 assert (is_layer_group_active[e->rb->group]);
3733 if (e->cost < s->best_cost)
3734 heap_insert (s->workheap, e->cost, e);
3735 else
3736 DestroyEdge (&e);
3739 static void
3740 best_path_candidate (struct routeone_state *s,
3741 edge_t * e, routebox_t * best_target)
3743 e->cost = edge_cost (e, EXPENSIVE);
3744 if (s->best_path == NULL || e->cost < s->best_cost)
3746 #if defined(ROUTE_DEBUG) && defined (ROUTE_VERBOSE)
3747 printf ("New best path seen! cost = %f\n", e->cost);
3748 #endif
3749 /* new best path! */
3750 if (s->best_path && s->best_path->flags.homeless)
3751 RB_down_count (s->best_path);
3752 s->best_path = e->rb;
3753 s->best_target = best_target;
3754 s->best_cost = e->cost;
3755 assert (s->best_cost >= 0);
3756 /* don't free this when we destroy edge! */
3757 if (s->best_path->flags.homeless)
3758 RB_up_count (s->best_path);
3763 /* vectors for via site candidates (see mtspace.h) */
3764 struct routeone_via_site_state
3766 vector_t *free_space_vec;
3767 vector_t *lo_conflict_space_vec;
3768 vector_t *hi_conflict_space_vec;
3771 void
3772 add_via_sites (struct routeone_state *s,
3773 struct routeone_via_site_state *vss,
3774 mtspace_t * mtspace, routebox_t * within,
3775 conflict_t within_conflict_level, edge_t * parent_edge,
3776 rtree_t * targets, Coord shrink, bool in_plane)
3778 Coord radius, keepaway;
3779 vetting_t *work;
3780 BoxType region = shrink_routebox (within);
3781 shrink_box (&region, shrink);
3783 radius = HALF_THICK (AutoRouteParameters.style->Diameter);
3784 keepaway = AutoRouteParameters.style->Keepaway;
3785 assert (AutoRouteParameters.use_vias);
3786 /* XXX: need to clip 'within' to shrunk_pcb_bounds, because when
3787 XXX: routing with conflicts may poke over edge. */
3789 /* ask for a via box near our cost_point first */
3790 work = mtspace_query_rect (mtspace, &region, radius, keepaway,
3791 NULL, vss->free_space_vec,
3792 vss->lo_conflict_space_vec,
3793 vss->hi_conflict_space_vec,
3794 AutoRouteParameters.is_odd,
3795 AutoRouteParameters.with_conflicts,
3796 &parent_edge->cost_point);
3797 if (!work)
3798 return;
3799 CreateSearchEdge (s, work, parent_edge, within, within_conflict_level,
3800 targets, in_plane);
3803 void
3804 do_via_search (edge_t * search, struct routeone_state *s,
3805 struct routeone_via_site_state *vss, mtspace_t * mtspace,
3806 rtree_t * targets)
3808 int i, j, count = 0;
3809 Coord radius, keepaway;
3810 vetting_t *work;
3811 routebox_t *within;
3812 conflict_t within_conflict_level;
3814 radius = HALF_THICK (AutoRouteParameters.style->Diameter);
3815 keepaway = AutoRouteParameters.style->Keepaway;
3816 work = mtspace_query_rect (mtspace, NULL, 0, 0,
3817 search->work, vss->free_space_vec,
3818 vss->lo_conflict_space_vec,
3819 vss->hi_conflict_space_vec,
3820 AutoRouteParameters.is_odd,
3821 AutoRouteParameters.with_conflicts, NULL);
3822 within = search->rb;
3823 within_conflict_level = search->flags.via_conflict_level;
3824 for (i = 0; i < 3; i++)
3826 vector_t *v =
3827 (i == NO_CONFLICT ? vss->free_space_vec :
3828 i == LO_CONFLICT ? vss->lo_conflict_space_vec :
3829 i == HI_CONFLICT ? vss->hi_conflict_space_vec : NULL);
3830 assert (v);
3831 while (!vector_is_empty (v))
3833 BoxType cliparea;
3834 BoxType *area = (BoxType *)vector_remove_last (v);
3835 if (!(i == NO_CONFLICT || AutoRouteParameters.with_conflicts))
3837 free (area);
3838 continue;
3840 /* answers are bloated by radius + keepaway */
3841 cliparea = shrink_box (area, radius + keepaway);
3842 close_box (&cliparea);
3843 free (area);
3844 assert (box_is_good (&cliparea));
3845 count++;
3846 for (j = 0; j < max_group; j++)
3848 edge_t *ne;
3849 if (j == within->group || !is_layer_group_active[j])
3850 continue;
3851 ne = CreateViaEdge (&cliparea, j, within, search,
3852 within_conflict_level, (conflict_t)i, targets);
3853 add_or_destroy_edge (s, ne);
3857 /* prevent freeing of work when this edge is destroyed */
3858 search->flags.via_search = 0;
3859 if (!work)
3860 return;
3861 CreateSearchEdge (s, work, search, within, within_conflict_level, targets,
3862 search->flags.in_plane);
3863 assert (vector_is_empty (vss->free_space_vec));
3864 assert (vector_is_empty (vss->lo_conflict_space_vec));
3865 assert (vector_is_empty (vss->hi_conflict_space_vec));
3868 /* vector of expansion areas to be eventually removed from r-tree
3869 * this is a global for troubleshooting
3871 vector_t *area_vec;
3873 /* some routines for use in gdb while debugging */
3874 #if defined(ROUTE_DEBUG)
3875 static void
3876 list_conflicts (routebox_t * rb)
3878 int i, n;
3879 if (!rb->conflicts_with)
3880 return;
3881 n = vector_size (rb->conflicts_with);
3882 for (i = 0; i < n; i++)
3883 printf ("%p, ", vector_element (rb->conflicts_with, i));
3886 static void
3887 show_area_vec (int lay)
3889 int n, save;
3891 if (!area_vec)
3892 return;
3893 save = showboxen;
3894 showboxen = lay;
3895 for (n = 0; n < vector_size (area_vec); n++)
3897 routebox_t *rb = (routebox_t *) vector_element (area_vec, n);
3898 showroutebox (rb);
3900 showboxen = save;
3903 static bool
3904 net_id (routebox_t * rb, long int id)
3906 routebox_t *p;
3907 LIST_LOOP (rb, same_net, p);
3908 if (p->flags.source && p->parent.pad->ID == id)
3909 return true;
3910 END_LOOP;
3911 return false;
3914 static void
3915 trace_parents (routebox_t * rb)
3917 while (rb && rb->type == EXPANSION_AREA)
3919 printf (" %p ->", rb);
3920 rb = rb->parent.expansion_area;
3922 if (rb)
3923 printf (" %p is source\n", rb);
3924 else
3925 printf ("NULL!\n");
3928 static void
3929 show_one (routebox_t * rb)
3931 int save = showboxen;
3932 showboxen = -1;
3933 showroutebox (rb);
3934 showboxen = save;
3937 static void
3938 show_path (routebox_t * rb)
3940 while (rb && rb->type == EXPANSION_AREA)
3942 show_one (rb);
3943 rb = rb->parent.expansion_area;
3945 show_one (rb);
3948 static void
3949 show_sources (routebox_t * rb)
3951 routebox_t *p;
3952 if (!rb->flags.source && !rb->flags.target)
3954 printf ("start with a source or target please\n");
3955 return;
3957 LIST_LOOP (rb, same_net, p);
3958 if (p->flags.source)
3959 show_one (p);
3960 END_LOOP;
3963 #endif
3965 static int
3966 __conflict_source (const BoxType * box, void *cl)
3968 routebox_t *rb = (routebox_t *) box;
3969 if (rb->flags.touched || rb->flags.fixed)
3970 return 0;
3971 else
3973 routebox_t *dis = (routebox_t *) cl;
3974 path_conflicts (dis, rb, false);
3975 touch_conflicts (dis->conflicts_with, 1);
3977 return 1;
3980 static void
3981 source_conflicts (rtree_t * tree, routebox_t * rb)
3983 if (!AutoRouteParameters.with_conflicts)
3984 return;
3985 r_search (tree, &rb->sbox, NULL, __conflict_source, rb);
3986 touch_conflicts (NULL, 1);
3989 struct routeone_status
3991 bool found_route;
3992 int route_had_conflicts;
3993 cost_t best_route_cost;
3994 bool net_completely_routed;
3998 static struct routeone_status
3999 RouteOne (routedata_t * rd, routebox_t * from, routebox_t * to, int max_edges)
4001 struct routeone_status result;
4002 routebox_t *p;
4003 int seen, i;
4004 const BoxType **target_list;
4005 int num_targets;
4006 rtree_t *targets;
4007 /* vector of source edges for filtering */
4008 vector_t *source_vec;
4009 /* working vector */
4010 vector_t *edge_vec;
4012 struct routeone_state s;
4013 struct routeone_via_site_state vss;
4015 assert (rd && from);
4016 result.route_had_conflicts = 0;
4017 /* no targets on to/from net need keepaway areas */
4018 LIST_LOOP (from, same_net, p);
4019 p->flags.nobloat = 1;
4020 END_LOOP;
4021 /* set 'source' flags */
4022 LIST_LOOP (from, same_subnet, p);
4023 if (!p->flags.nonstraight)
4024 p->flags.source = 1;
4025 END_LOOP;
4027 /* count up the targets */
4028 num_targets = 0;
4029 seen = 0;
4030 /* remove source/target flags from non-straight obstacles, because they
4031 * don't fill their bounding boxes and so connecting to them
4032 * after we've routed is problematic. Better solution? */
4033 if (to)
4034 { /* if we're routing to a specific target */
4035 if (!to->flags.source)
4036 { /* not already connected */
4037 /* check that 'to' and 'from' are on the same net */
4038 seen = 0;
4039 #ifndef NDEBUG
4040 LIST_LOOP (from, same_net, p);
4041 if (p == to)
4042 seen = 1;
4043 END_LOOP;
4044 #endif
4045 assert (seen); /* otherwise from and to are on different nets! */
4046 /* set target flags only on 'to's subnet */
4047 LIST_LOOP (to, same_subnet, p);
4048 if (!p->flags.nonstraight && is_layer_group_active[p->group])
4050 p->flags.target = 1;
4051 num_targets++;
4053 END_LOOP;
4056 else
4058 /* all nodes on the net but not connected to from are targets */
4059 LIST_LOOP (from, same_net, p);
4060 if (!p->flags.source && is_layer_group_active[p->group]
4061 && !p->flags.nonstraight)
4063 p->flags.target = 1;
4064 num_targets++;
4066 END_LOOP;
4069 /* if no targets, then net is done! reset flags and return. */
4070 if (num_targets == 0)
4072 LIST_LOOP (from, same_net, p);
4073 p->flags.source = p->flags.target = p->flags.nobloat = 0;
4074 END_LOOP;
4075 result.found_route = false;
4076 result.net_completely_routed = true;
4077 result.best_route_cost = 0;
4078 result.route_had_conflicts = 0;
4080 return result;
4082 result.net_completely_routed = false;
4084 /* okay, there's stuff to route */
4085 assert (!from->flags.target);
4086 assert (num_targets > 0);
4087 /* create list of target pointers and from that a r-tree of targets */
4088 target_list = (const BoxType **)malloc (num_targets * sizeof (*target_list));
4089 i = 0;
4090 LIST_LOOP (from, same_net, p);
4091 if (p->flags.target)
4093 target_list[i++] = &p->box;
4094 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_TARGETS)
4095 showroutebox (p);
4096 #endif
4098 END_LOOP;
4099 targets = r_create_tree ((const BoxType **)target_list, i, 0);
4100 assert (i <= num_targets);
4101 free (target_list);
4103 source_vec = vector_create ();
4104 /* touch the source subnet to prepare check for conflictors */
4105 LIST_LOOP (from, same_subnet, p);
4106 p->flags.touched = 1;
4107 END_LOOP;
4108 LIST_LOOP (from, same_subnet, p);
4110 /* we need the test for 'source' because this box may be nonstraight */
4111 if (p->flags.source && is_layer_group_active[p->group])
4113 CheapPointType cp;
4114 edge_t *e;
4115 BoxType b = shrink_routebox (p);
4117 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_SOURCES)
4118 showroutebox (p);
4119 #endif
4120 /* may expand in all directions from source; center edge cost point. */
4121 /* note that planes shouldn't really expand, but we need an edge */
4123 cp.X = CENTER_X (b);
4124 cp.Y = CENTER_Y (b);
4125 e = CreateEdge (p, cp.X, cp.Y, 0, NULL, ALL, targets);
4126 cp = closest_point_in_box (&cp, &e->mincost_target->sbox);
4127 cp = closest_point_in_box (&cp, &b);
4128 e->cost_point = cp;
4129 p->cost_point = cp;
4130 source_conflicts (rd->layergrouptree[p->group], p);
4131 vector_append (source_vec, e);
4134 END_LOOP;
4135 LIST_LOOP (from, same_subnet, p);
4136 p->flags.touched = 0;
4137 END_LOOP;
4138 /* break source edges; some edges may be too near obstacles to be able
4139 * to exit from. */
4141 /* okay, main expansion-search routing loop. */
4142 /* set up the initial activity heap */
4143 s.workheap = heap_create ();
4144 assert (s.workheap);
4145 while (!vector_is_empty (source_vec))
4147 edge_t *e = (edge_t *)vector_remove_last (source_vec);
4148 assert (is_layer_group_active[e->rb->group]);
4149 e->cost = edge_cost (e, EXPENSIVE);
4150 heap_insert (s.workheap, e->cost, e);
4152 vector_destroy (&source_vec);
4153 /* okay, process items from heap until it is empty! */
4154 s.best_path = NULL;
4155 s.best_cost = EXPENSIVE;
4156 area_vec = vector_create ();
4157 edge_vec = vector_create ();
4158 vss.free_space_vec = vector_create ();
4159 vss.lo_conflict_space_vec = vector_create ();
4160 vss.hi_conflict_space_vec = vector_create ();
4161 while (!heap_is_empty (s.workheap))
4163 edge_t *e = (edge_t *)heap_remove_smallest (s.workheap);
4164 #ifdef ROUTE_DEBUG
4165 if (aabort)
4166 goto dontexpand;
4167 #endif
4168 /* don't bother expanding this edge if the minimum possible edge cost
4169 * is already larger than the best edge cost we've found. */
4170 if (s.best_path && e->cost >= s.best_cost)
4172 heap_free (s.workheap, KillEdge);
4173 goto dontexpand; /* skip this edge */
4175 /* surprisingly it helps to give up and not try too hard to find
4176 * a route! This is not only faster, but results in better routing.
4177 * who would have guessed?
4179 if (seen++ > max_edges)
4180 goto dontexpand;
4181 assert (__edge_is_good (e));
4182 /* mark or unmark conflictors as needed */
4183 touch_conflicts (e->rb->conflicts_with, 1);
4184 if (e->flags.via_search)
4186 do_via_search (e, &s, &vss, rd->mtspace, targets);
4187 goto dontexpand;
4189 /* we should never add edges on inactive layer groups to the heap. */
4190 assert (is_layer_group_active[e->rb->group]);
4191 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
4192 //showedge (e);
4193 #endif
4194 if (e->rb->flags.is_thermal)
4196 best_path_candidate (&s, e, e->mincost_target);
4197 goto dontexpand;
4199 /* for a plane, look for quick connections with thermals or vias */
4200 if (e->rb->type == PLANE)
4202 routebox_t *pin = FindThermable (targets, e->rb);
4203 if (pin)
4205 BoxType b = shrink_routebox (pin);
4206 edge_t *ne;
4207 routebox_t *nrb;
4208 assert (pin->flags.target);
4209 nrb = CreateExpansionArea (&b, e->rb->group, e->rb, true, e);
4210 nrb->flags.is_thermal = 1;
4211 /* moving through the plane is free */
4212 e->cost_point.X = b.X1;
4213 e->cost_point.Y = b.Y1;
4214 ne = CreateEdge2 (nrb, e->expand_dir, e, NULL, pin);
4215 best_path_candidate (&s, ne, pin);
4216 DestroyEdge (&ne);
4218 else
4220 /* add in possible via sites in plane */
4221 if (AutoRouteParameters.use_vias &&
4222 e->cost + AutoRouteParameters.ViaCost < s.best_cost)
4224 /* we need a giant thermal */
4225 routebox_t *nrb =
4226 CreateExpansionArea (&e->rb->sbox, e->rb->group, e->rb,
4227 true, e);
4228 edge_t *ne = CreateEdge2 (nrb, e->expand_dir, e, NULL,
4229 e->mincost_target);
4230 nrb->flags.is_thermal = 1;
4231 add_via_sites (&s, &vss, rd->mtspace, nrb, NO_CONFLICT, ne,
4232 targets, e->rb->style->Diameter, true);
4235 goto dontexpand; /* planes only connect via thermals */
4237 if (e->flags.is_via)
4238 { /* special case via */
4239 routebox_t *intersecting;
4240 assert (AutoRouteParameters.use_vias);
4241 assert (e->expand_dir == ALL);
4242 assert (vector_is_empty (edge_vec));
4243 /* if there is already something here on this layer (like an
4244 * EXPANSION_AREA), then we don't want to expand from here
4245 * at least not inside the expansion area. A PLANE on the
4246 * other hand may be a target, or not.
4248 intersecting =
4249 FindOneInBox (rd->layergrouptree[e->rb->group], e->rb);
4251 if (intersecting && intersecting->flags.target
4252 && intersecting->type == PLANE)
4254 /* we have hit a plane */
4255 edge_t *ne;
4256 routebox_t *nrb;
4257 BoxType b = shrink_routebox (e->rb);
4258 /* limit via region to that inside the plane */
4259 clip_box (&b, &intersecting->sbox);
4260 nrb = CreateExpansionArea (&b, e->rb->group, e->rb, true, e);
4261 nrb->flags.is_thermal = 1;
4262 ne = CreateEdge2 (nrb, e->expand_dir, e, NULL, intersecting);
4263 best_path_candidate (&s, ne, intersecting);
4264 DestroyEdge (&ne);
4265 goto dontexpand;
4267 else if (intersecting == NULL)
4269 /* this via candidate is in an open area; add it to r-tree as
4270 * an expansion area */
4271 assert (e->rb->type == EXPANSION_AREA && e->rb->flags.is_via);
4272 /*assert (!r_search (rd->layergrouptree[e->rb->group],
4273 &e->rb->box, NULL, no_planes,0));
4275 r_insert_entry (rd->layergrouptree[e->rb->group], &e->rb->box,
4277 e->rb->flags.homeless = 0; /* not homeless any more */
4278 /* add to vector of all expansion areas in r-tree */
4279 vector_append (area_vec, e->rb);
4280 /* mark reset refcount to 0, since this is not homeless any more. */
4281 e->rb->refcount = 0;
4282 /* go ahead and expand this edge! */
4284 else if (1)
4285 goto dontexpand;
4286 else if (0)
4287 { /* XXX: disabling this causes no via
4288 collisions. */
4289 BoxType a = bloat_routebox (intersecting), b;
4290 edge_t *ne;
4291 int i, j;
4292 /* something intersects this via candidate. split via candidate
4293 * into pieces and add these pieces to the workheap. */
4294 for (i = 0; i < 3; i++)
4296 for (j = 0; j < 3; j++)
4298 b = shrink_routebox (e->rb);
4299 switch (i)
4301 case 0:
4302 b.X2 = MIN (b.X2, a.X1);
4303 break; /* left */
4304 case 1:
4305 b.X1 = MAX (b.X1, a.X1);
4306 b.X2 = MIN (b.X2, a.X2);
4307 break; /*c */
4308 case 2:
4309 b.X1 = MAX (b.X1, a.X2);
4310 break; /* right */
4311 default:
4312 assert (0);
4314 switch (j)
4316 case 0:
4317 b.Y2 = MIN (b.Y2, a.Y1);
4318 break; /* top */
4319 case 1:
4320 b.Y1 = MAX (b.Y1, a.Y1);
4321 b.Y2 = MIN (b.Y2, a.Y2);
4322 break; /*c */
4323 case 2:
4324 b.Y1 = MAX (b.Y1, a.Y2);
4325 break; /* bottom */
4326 default:
4327 assert (0);
4329 /* skip if this box is not valid */
4330 if (!(b.X1 < b.X2 && b.Y1 < b.Y2))
4331 continue;
4332 if (i == 1 && j == 1)
4334 /* this bit of the via space is obstructed. */
4335 if (intersecting->type == EXPANSION_AREA
4336 || intersecting->flags.fixed)
4337 continue; /* skip this bit, it's already been done. */
4338 /* create an edge with conflicts, if enabled */
4339 if (!AutoRouteParameters.with_conflicts)
4340 continue;
4341 ne = CreateEdgeWithConflicts (&b, intersecting, e, 1
4342 /*cost penalty to box */
4343 , targets);
4344 add_or_destroy_edge (&s, ne);
4346 else
4348 /* if this is not the intersecting piece, create a new
4349 * (hopefully unobstructed) via edge and add it back to the
4350 * workheap. */
4351 ne =
4352 CreateViaEdge (&b, e->rb->group,
4353 e->rb->parent.expansion_area, e,
4354 e->flags.via_conflict_level,
4355 NO_CONFLICT
4356 /* value here doesn't matter */
4357 , targets);
4358 add_or_destroy_edge (&s, ne);
4362 goto dontexpand;
4364 /* between the time these edges are inserted and the
4365 * time they are processed, new expansion boxes (which
4366 * conflict with these edges) may be added to the graph!
4367 * w.o vias this isn't a problem because the broken box
4368 * is not homeless. */
4370 if (1)
4372 routebox_t *nrb;
4373 struct E_result *ans;
4374 BoxType b;
4375 vector_t *broken;
4376 if (e->flags.is_interior)
4378 assert (AutoRouteParameters.with_conflicts); /* no interior edges unless
4379 routing with conflicts! */
4380 assert (e->rb->conflicts_with);
4381 b = e->rb->sbox;
4382 switch (e->rb->came_from)
4384 case NORTH:
4385 b.Y2 = b.Y1 + 1;
4386 b.X1 = CENTER_X (b);
4387 b.X2 = b.X1 + 1;
4388 break;
4389 case EAST:
4390 b.X1 = b.X2 - 1;
4391 b.Y1 = CENTER_Y (b);
4392 b.Y2 = b.Y1 + 1;
4393 break;
4394 case SOUTH:
4395 b.Y1 = b.Y2 - 1;
4396 b.X1 = CENTER_X (b);
4397 b.X2 = b.X1 + 1;
4398 break;
4399 case WEST:
4400 b.X2 = b.X1 + 1;
4401 b.Y1 = CENTER_Y (b);
4402 b.Y2 = b.Y1 + 1;
4403 break;
4404 default:
4405 assert (0);
4408 /* sources may not expand to their own edges because of
4409 * adjacent blockers.
4411 else if (e->rb->flags.source)
4412 b = box_center (&e->rb->sbox);
4413 else
4414 b = e->rb->sbox;
4415 ans = Expand (rd->layergrouptree[e->rb->group], e, &b);
4416 if (!box_intersect (&ans->inflated, &ans->orig))
4417 goto dontexpand;
4418 #if 0
4419 /* skip if it didn't actually expand */
4420 if (ans->inflated.X1 >= e->rb->sbox.X1 &&
4421 ans->inflated.X2 <= e->rb->sbox.X2 &&
4422 ans->inflated.Y1 >= e->rb->sbox.Y1 &&
4423 ans->inflated.Y2 <= e->rb->sbox.Y2)
4424 goto dontexpand;
4425 #endif
4427 if (!box_is_good (&ans->inflated))
4428 goto dontexpand;
4429 nrb = CreateExpansionArea (&ans->inflated, e->rb->group, e->rb,
4430 true, e);
4431 r_insert_entry (rd->layergrouptree[nrb->group], &nrb->box, 1);
4432 vector_append (area_vec, nrb);
4433 nrb->flags.homeless = 0; /* not homeless any more */
4434 broken =
4435 BreakManyEdges (&s, targets, rd->layergrouptree[nrb->group],
4436 area_vec, ans, nrb, e);
4437 while (!vector_is_empty (broken))
4439 edge_t *ne = (edge_t *)vector_remove_last (broken);
4440 add_or_destroy_edge (&s, ne);
4442 vector_destroy (&broken);
4444 /* add in possible via sites in nrb */
4445 if (AutoRouteParameters.use_vias && !e->rb->flags.is_via &&
4446 e->cost + AutoRouteParameters.ViaCost < s.best_cost)
4447 add_via_sites (&s, &vss,
4448 rd->mtspace, nrb, NO_CONFLICT, e, targets, 0,
4449 false);
4450 goto dontexpand;
4452 dontexpand:
4453 DestroyEdge (&e);
4455 touch_conflicts (NULL, 1);
4456 heap_destroy (&s.workheap);
4457 r_destroy_tree (&targets);
4458 assert (vector_is_empty (edge_vec));
4459 vector_destroy (&edge_vec);
4461 /* we should have a path in best_path now */
4462 if (s.best_path)
4464 routebox_t *rb;
4465 #ifdef ROUTE_VERBOSE
4466 printf ("%d:%d RC %.0f", ro++, seen, s.best_cost);
4467 #endif
4468 result.found_route = true;
4469 result.best_route_cost = s.best_cost;
4470 /* determine if the best path had conflicts */
4471 result.route_had_conflicts = 0;
4472 if (AutoRouteParameters.with_conflicts && s.best_path->conflicts_with)
4474 while (!vector_is_empty (s.best_path->conflicts_with))
4476 rb = (routebox_t *)vector_remove_last (s.best_path->conflicts_with);
4477 rb->flags.is_bad = 1;
4478 result.route_had_conflicts++;
4481 #ifdef ROUTE_VERBOSE
4482 if (result.route_had_conflicts)
4483 printf (" (%d conflicts)", result.route_had_conflicts);
4484 #endif
4485 if (result.route_had_conflicts < AutoRouteParameters.hi_conflict)
4487 /* back-trace the path and add lines/vias to r-tree */
4488 TracePath (rd, s.best_path, s.best_target, from,
4489 result.route_had_conflicts);
4490 MergeNets (from, s.best_target, SUBNET);
4492 else
4494 #ifdef ROUTE_VERBOSE
4495 printf (" (too many in fact)");
4496 #endif
4497 result.found_route = false;
4499 #ifdef ROUTE_VERBOSE
4500 printf ("\n");
4501 #endif
4503 else
4505 #ifdef ROUTE_VERBOSE
4506 printf ("%d:%d NO PATH FOUND.\n", ro++, seen);
4507 #endif
4508 result.best_route_cost = s.best_cost;
4509 result.found_route = false;
4511 /* now remove all expansion areas from the r-tree. */
4512 while (!vector_is_empty (area_vec))
4514 routebox_t *rb = (routebox_t *)vector_remove_last (area_vec);
4515 assert (!rb->flags.homeless);
4516 if (rb->conflicts_with
4517 && rb->parent.expansion_area->conflicts_with != rb->conflicts_with)
4518 vector_destroy (&rb->conflicts_with);
4519 r_delete_entry (rd->layergrouptree[rb->group], &rb->box);
4521 vector_destroy (&area_vec);
4522 /* clean up; remove all 'source', 'target', and 'nobloat' flags */
4523 LIST_LOOP (from, same_net, p);
4524 if (p->flags.source && p->conflicts_with)
4525 vector_destroy (&p->conflicts_with);
4526 p->flags.touched = p->flags.source = p->flags.target = p->flags.nobloat = 0;
4527 END_LOOP;
4529 vector_destroy (&vss.free_space_vec);
4530 vector_destroy (&vss.lo_conflict_space_vec);
4531 vector_destroy (&vss.hi_conflict_space_vec);
4533 return result;
4536 static void
4537 InitAutoRouteParameters (int pass,
4538 RouteStyleType * style,
4539 bool with_conflicts, bool is_smoothing,
4540 bool lastpass)
4542 int i;
4543 /* routing style */
4544 AutoRouteParameters.style = style;
4545 AutoRouteParameters.bloat = style->Keepaway + HALF_THICK (style->Thick);
4546 /* costs */
4547 AutoRouteParameters.ViaCost =
4548 INCH_TO_COORD (3.5) + style->Diameter * (is_smoothing ? 80 : 30);
4549 AutoRouteParameters.LastConflictPenalty =
4550 (400 * pass / passes + 2) / (pass + 1);
4551 AutoRouteParameters.ConflictPenalty =
4552 4 * AutoRouteParameters.LastConflictPenalty;
4553 AutoRouteParameters.JogPenalty = 1000 * (is_smoothing ? 20 : 4);
4554 AutoRouteParameters.CongestionPenalty = 1e6;
4555 AutoRouteParameters.MinPenalty = EXPENSIVE;
4556 for (i = 0; i < max_group; i++)
4558 if (is_layer_group_active[i])
4560 AutoRouteParameters.MinPenalty = MIN (x_cost[i],
4561 AutoRouteParameters.
4562 MinPenalty);
4563 AutoRouteParameters.MinPenalty =
4564 MIN (y_cost[i], AutoRouteParameters.MinPenalty);
4567 AutoRouteParameters.NewLayerPenalty = is_smoothing ?
4568 0.5 * EXPENSIVE : 10 * AutoRouteParameters.ViaCost;
4569 /* other */
4570 AutoRouteParameters.hi_conflict = MAX (8 * (passes - pass + 1), 6);
4571 AutoRouteParameters.is_odd = (pass & 1);
4572 AutoRouteParameters.with_conflicts = with_conflicts;
4573 AutoRouteParameters.is_smoothing = is_smoothing;
4574 AutoRouteParameters.rip_always = is_smoothing;
4575 AutoRouteParameters.last_smooth = 0; //lastpass;
4576 AutoRouteParameters.pass = pass + 1;
4579 #ifndef NDEBUG
4581 bad_boy (const BoxType * b, void *cl)
4583 routebox_t *box = (routebox_t *) b;
4584 if (box->type == EXPANSION_AREA)
4585 return 1;
4586 return 0;
4589 bool
4590 no_expansion_boxes (routedata_t * rd)
4592 int i;
4593 BoxType big;
4594 big.X1 = 0;
4595 big.X2 = MAX_COORD;
4596 big.Y1 = 0;
4597 big.Y2 = MAX_COORD;
4598 for (i = 0; i < max_group; i++)
4600 if (r_search (rd->layergrouptree[i], &big, NULL, bad_boy, NULL))
4601 return false;
4603 return true;
4605 #endif
4607 static void
4608 ripout_livedraw_obj (routebox_t *rb)
4610 if (rb->type == LINE && rb->livedraw_obj.line)
4612 LayerType *layer = LAYER_PTR (PCB->LayerGroups.Entries[rb->group][0]);
4613 EraseLine (rb->livedraw_obj.line);
4614 DestroyObject (PCB->Data, LINE_TYPE, layer, rb->livedraw_obj.line, NULL);
4615 rb->livedraw_obj.line = NULL;
4617 if (rb->type == VIA && rb->livedraw_obj.via)
4619 EraseVia (rb->livedraw_obj.via);
4620 DestroyObject (PCB->Data, VIA_TYPE, rb->livedraw_obj.via, NULL, NULL);
4621 rb->livedraw_obj.via = NULL;
4625 static int
4626 ripout_livedraw_obj_cb (const BoxType * b, void *cl)
4628 routebox_t *box = (routebox_t *) b;
4629 ripout_livedraw_obj (box);
4630 return 0;
4633 struct routeall_status
4635 /* --- for completion rate statistics ---- */
4636 int total_subnets;
4637 /* total subnets routed without conflicts */
4638 int routed_subnets;
4639 /* total subnets routed with conflicts */
4640 int conflict_subnets;
4641 /* net failted entirely */
4642 int failed;
4643 /* net was ripped */
4644 int ripped;
4645 int total_nets_routed;
4648 static double
4649 calculate_progress (double this_heap_item, double this_heap_size,
4650 struct routeall_status *ras)
4652 double total_passes = passes + smoothes + 1; /* + 1 is the refinement pass */
4653 double this_pass = AutoRouteParameters.pass - 1; /* Number passes from zero */
4654 double heap_fraction = (double)(ras->routed_subnets + ras->conflict_subnets + ras->failed) /
4655 (double)ras->total_subnets;
4656 double pass_fraction = (this_heap_item + heap_fraction ) / this_heap_size;
4657 double process_fraction = (this_pass + pass_fraction) / total_passes;
4659 return process_fraction;
4662 struct routeall_status
4663 RouteAll (routedata_t * rd)
4665 struct routeall_status ras;
4666 struct routeone_status ros;
4667 bool rip;
4668 int request_cancel;
4669 #ifdef NET_HEAP
4670 heap_t *net_heap;
4671 #endif
4672 heap_t *this_pass, *next_pass, *tmp;
4673 routebox_t *net, *p, *pp;
4674 cost_t total_net_cost, last_cost = 0, this_cost = 0;
4675 int i;
4676 int this_heap_size;
4677 int this_heap_item;
4679 /* initialize heap for first pass;
4680 * do smallest area first; that makes
4681 * the subsequent costs more representative */
4682 this_pass = heap_create ();
4683 next_pass = heap_create ();
4684 #ifdef NET_HEAP
4685 net_heap = heap_create ();
4686 #endif
4687 LIST_LOOP (rd->first_net, different_net, net);
4689 double area;
4690 BoxType bb = shrink_routebox (net);
4691 LIST_LOOP (net, same_net, p);
4693 MAKEMIN (bb.X1, p->sbox.X1);
4694 MAKEMIN (bb.Y1, p->sbox.Y1);
4695 MAKEMAX (bb.X2, p->sbox.X2);
4696 MAKEMAX (bb.Y2, p->sbox.Y2);
4698 END_LOOP;
4699 area = (double) (bb.X2 - bb.X1) * (bb.Y2 - bb.Y1);
4700 heap_insert (this_pass, area, net);
4702 END_LOOP;
4704 ras.total_nets_routed = 0;
4705 /* refinement/finishing passes */
4706 for (i = 0; i <= passes + smoothes; i++)
4708 #ifdef ROUTE_VERBOSE
4709 if (i > 0 && i <= passes)
4710 printf ("--------- STARTING REFINEMENT PASS %d ------------\n", i);
4711 else if (i > passes)
4712 printf ("--------- STARTING SMOOTHING PASS %d -------------\n",
4713 i - passes);
4714 #endif
4715 ras.total_subnets = ras.routed_subnets = ras.conflict_subnets =
4716 ras.failed = ras.ripped = 0;
4717 assert (heap_is_empty (next_pass));
4719 this_heap_size = heap_size (this_pass);
4720 for (this_heap_item = 0; !heap_is_empty (this_pass); this_heap_item++)
4722 #ifdef ROUTE_DEBUG
4723 if (aabort)
4724 break;
4725 #endif
4726 net = (routebox_t *) heap_remove_smallest (this_pass);
4727 InitAutoRouteParameters (i, net->style, i < passes, i > passes,
4728 i == passes + smoothes);
4729 if (i > 0)
4731 /* rip up all unfixed traces in this net ? */
4732 if (AutoRouteParameters.rip_always)
4733 rip = true;
4734 else
4736 rip = false;
4737 LIST_LOOP (net, same_net, p);
4738 if (p->flags.is_bad)
4740 rip = true;
4741 break;
4743 END_LOOP;
4746 LIST_LOOP (net, same_net, p);
4747 p->flags.is_bad = 0;
4748 if (!p->flags.fixed)
4750 #ifndef NDEBUG
4751 bool del;
4752 #endif
4753 assert (!p->flags.homeless);
4754 if (rip)
4756 RemoveFromNet (p, NET);
4757 RemoveFromNet (p, SUBNET);
4759 if (AutoRouteParameters.use_vias && p->type != VIA_SHADOW
4760 && p->type != PLANE)
4762 mtspace_remove (rd->mtspace, &p->box,
4763 p->flags.is_odd ? ODD : EVEN,
4764 p->style->Keepaway);
4765 if (!rip)
4766 mtspace_add (rd->mtspace, &p->box,
4767 p->flags.is_odd ? EVEN : ODD,
4768 p->style->Keepaway);
4770 if (rip)
4772 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
4773 ripout_livedraw_obj (p);
4774 #ifndef NDEBUG
4775 del =
4776 #endif
4777 r_delete_entry (rd->layergrouptree[p->group],
4778 &p->box);
4779 #ifndef NDEBUG
4780 assert (del);
4781 #endif
4783 else
4785 p->flags.is_odd = AutoRouteParameters.is_odd;
4788 END_LOOP;
4789 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
4790 Draw ();
4791 /* reset to original connectivity */
4792 if (rip)
4794 ras.ripped++;
4795 ResetSubnet (net);
4797 else
4799 heap_insert (next_pass, 0, net);
4800 continue;
4803 /* count number of subnets */
4804 FOREACH_SUBNET (net, p);
4805 ras.total_subnets++;
4806 END_FOREACH (net, p);
4807 /* the first subnet doesn't require routing. */
4808 ras.total_subnets--;
4809 /* and re-route! */
4810 total_net_cost = 0;
4811 /* only route that which isn't fully routed */
4812 #ifdef ROUTE_DEBUG
4813 if (ras.total_subnets == 0 || aabort)
4814 #else
4815 if (ras.total_subnets == 0)
4816 #endif
4818 heap_insert (next_pass, 0, net);
4819 continue;
4822 /* the loop here ensures that we get to all subnets even if
4823 * some of them are unreachable from the first subnet. */
4824 LIST_LOOP (net, same_net, p);
4826 #ifdef NET_HEAP
4827 BoxType b = shrink_routebox (p);
4828 /* using a heap allows us to start from smaller objects and
4829 * end at bigger ones. also prefer to start at planes, then pads */
4830 heap_insert (net_heap, (float) (b.X2 - b.X1) *
4831 #if defined(ROUTE_RANDOMIZED)
4832 (0.3 + rand () / (RAND_MAX + 1.0)) *
4833 #endif
4834 (b.Y2 - b.Y1) * (p->type == PLANE ?
4835 -1 : (p->type ==
4836 PAD ? 1 : 10)), p);
4838 END_LOOP;
4839 ros.net_completely_routed = 0;
4840 while (!heap_is_empty (net_heap))
4842 p = (routebox_t *) heap_remove_smallest (net_heap);
4843 #endif
4844 if (!p->flags.fixed || p->flags.subnet_processed ||
4845 p->type == OTHER)
4846 continue;
4848 while (!ros.net_completely_routed)
4850 double percent;
4852 assert (no_expansion_boxes (rd));
4853 /* FIX ME: the number of edges to examine should be in autoroute parameters
4854 * i.e. the 2000 and 800 hard-coded below should be controllable by the user
4856 ros =
4857 RouteOne (rd, p, NULL,
4858 ((AutoRouteParameters.
4859 is_smoothing ? 2000 : 800) * (i +
4860 1)) *
4861 routing_layers);
4862 total_net_cost += ros.best_route_cost;
4863 if (ros.found_route)
4865 if (ros.route_had_conflicts)
4866 ras.conflict_subnets++;
4867 else
4869 ras.routed_subnets++;
4870 ras.total_nets_routed++;
4873 else
4875 if (!ros.net_completely_routed)
4876 ras.failed++;
4877 /* don't bother trying any other source in this subnet */
4878 LIST_LOOP (p, same_subnet, pp);
4879 pp->flags.subnet_processed = 1;
4880 END_LOOP;
4881 break;
4883 /* note that we can infer nothing about ras.total_subnets based
4884 * on the number of calls to RouteOne, because we may be unable
4885 * to route a net from a particular starting point, but perfectly
4886 * able to route it from some other. */
4887 percent = calculate_progress (this_heap_item, this_heap_size, &ras);
4888 request_cancel = gui->progress (percent * 100., 100,
4889 _("Autorouting tracks"));
4890 if (request_cancel)
4892 ras.total_nets_routed = 0;
4893 ras.conflict_subnets = 0;
4894 Message ("Autorouting cancelled\n");
4895 goto out;
4899 #ifndef NET_HEAP
4900 END_LOOP;
4901 #endif
4902 if (!ros.net_completely_routed)
4903 net->flags.is_bad = 1; /* don't skip this the next round */
4905 /* Route easiest nets from this pass first on next pass.
4906 * This works best because it's likely that the hardest
4907 * is the last one routed (since it has the most obstacles)
4908 * but it will do no good to rip it up and try it again
4909 * without first changing any of the other routes
4911 heap_insert (next_pass, total_net_cost, net);
4912 if (total_net_cost < EXPENSIVE)
4913 this_cost += total_net_cost;
4914 /* reset subnet_processed flags */
4915 LIST_LOOP (net, same_net, p);
4917 p->flags.subnet_processed = 0;
4919 END_LOOP;
4921 /* swap this_pass and next_pass and do it all over again! */
4922 ro = 0;
4923 assert (heap_is_empty (this_pass));
4924 tmp = this_pass;
4925 this_pass = next_pass;
4926 next_pass = tmp;
4927 #if defined(ROUTE_DEBUG) || defined (ROUTE_VERBOSE)
4928 printf
4929 ("END OF PASS %d: %d/%d subnets routed without conflicts at cost %.0f, %d conflicts, %d failed %d ripped\n",
4930 i, ras.routed_subnets, ras.total_subnets, this_cost,
4931 ras.conflict_subnets, ras.failed, ras.ripped);
4932 #endif
4933 #ifdef ROUTE_DEBUG
4934 if (aabort)
4935 break;
4936 #endif
4937 /* if no conflicts found, skip directly to smoothing pass! */
4938 if (ras.conflict_subnets == 0 && ras.routed_subnets == ras.total_subnets
4939 && i <= passes)
4940 i = passes - (smoothes ? 0 : 1);
4941 /* if no changes in a smoothing round, then we're done */
4942 if (this_cost == last_cost && i > passes && i < passes + smoothes)
4943 i = passes + smoothes - 1;
4944 last_cost = this_cost;
4945 this_cost = 0;
4948 Message ("%d of %d nets successfully routed.\n",
4949 ras.routed_subnets, ras.total_subnets);
4951 out:
4952 heap_destroy (&this_pass);
4953 heap_destroy (&next_pass);
4954 #ifdef NET_HEAP
4955 heap_destroy (&net_heap);
4956 #endif
4958 /* no conflicts should be left at the end of the process. */
4959 assert (ras.conflict_subnets == 0);
4961 return ras;
4964 struct fpin_info
4966 PinType *pin;
4967 Coord X, Y;
4968 jmp_buf env;
4971 static int
4972 fpin_rect (const BoxType * b, void *cl)
4974 PinType *pin = (PinType *) b;
4975 struct fpin_info *info = (struct fpin_info *) cl;
4976 if (pin->X == info->X && pin->Y == info->Y)
4978 info->pin = (PinType *) b;
4979 longjmp (info->env, 1);
4981 return 0;
4984 static int
4985 FindPin (const BoxType * box, PinType ** pin)
4987 struct fpin_info info;
4989 info.pin = NULL;
4990 info.X = box->X1;
4991 info.Y = box->Y1;
4992 if (setjmp (info.env) == 0)
4993 r_search (PCB->Data->pin_tree, box, NULL, fpin_rect, &info);
4994 else
4996 *pin = info.pin;
4997 return PIN_TYPE;
4999 if (setjmp (info.env) == 0)
5000 r_search (PCB->Data->via_tree, box, NULL, fpin_rect, &info);
5001 else
5003 *pin = info.pin;
5004 return VIA_TYPE;
5006 *pin = NULL;
5007 return NO_TYPE;
5011 /* paths go on first 'on' layer in group */
5012 /* returns 'true' if any paths were added. */
5013 bool
5014 IronDownAllUnfixedPaths (routedata_t * rd)
5016 bool changed = false;
5017 LayerType *layer;
5018 routebox_t *net, *p;
5019 int i;
5020 LIST_LOOP (rd->first_net, different_net, net);
5022 LIST_LOOP (net, same_net, p);
5024 if (!p->flags.fixed)
5026 /* find first on layer in this group */
5027 assert (PCB->LayerGroups.Number[p->group] > 0);
5028 assert (is_layer_group_active[p->group]);
5029 for (i = 0, layer = NULL; i < PCB->LayerGroups.Number[p->group];
5030 i++)
5032 layer = LAYER_PTR (PCB->LayerGroups.Entries[p->group][i]);
5033 if (layer->On)
5034 break;
5036 assert (layer && layer->On); /*at least one layer must be on in this group! */
5037 assert (p->type != EXPANSION_AREA);
5038 if (p->type == LINE)
5040 Coord halfwidth = HALF_THICK (p->style->Thick);
5041 double th = halfwidth * 2 + 1;
5042 BoxType b;
5043 assert (p->parent.line == NULL);
5044 /* orthogonal; thickness is 2*halfwidth */
5045 /* flip coordinates, if bl_to_ur */
5046 b = p->sbox;
5047 total_wire_length +=
5048 sqrt ((b.X2 - b.X1 - th) * (b.X2 - b.X1 - th) +
5049 (b.Y2 - b.Y1 - th) * (b.Y2 - b.Y1 - th));
5050 b = shrink_box (&b, halfwidth);
5051 if (b.X2 == b.X1 + 1)
5052 b.X2 = b.X1;
5053 if (b.Y2 == b.Y1 + 1)
5054 b.Y2 = b.Y1;
5055 if (p->flags.bl_to_ur)
5057 Coord t;
5058 t = b.X1;
5059 b.X1 = b.X2;
5060 b.X2 = t;
5062 /* using CreateDrawn instead of CreateNew concatenates sequential lines */
5063 p->parent.line = CreateDrawnLineOnLayer
5064 (layer, b.X1, b.Y1, b.X2, b.Y2,
5065 p->style->Thick,
5066 p->style->Keepaway * 2,
5067 MakeFlags (AUTOFLAG |
5068 (TEST_FLAG (CLEARNEWFLAG, PCB) ? CLEARLINEFLAG :
5069 0)));
5071 if (p->parent.line)
5073 AddObjectToCreateUndoList (LINE_TYPE, layer,
5074 p->parent.line, p->parent.line);
5075 changed = true;
5078 else if (p->type == VIA || p->type == VIA_SHADOW)
5080 routebox_t *pp =
5081 (p->type == VIA_SHADOW) ? p->parent.via_shadow : p;
5082 Coord radius = HALF_THICK (pp->style->Diameter);
5083 BoxType b = shrink_routebox (p);
5084 total_via_count++;
5085 assert (pp->type == VIA);
5086 if (pp->parent.via == NULL)
5088 assert (b.X1 + radius == b.X2 - radius);
5089 assert (b.Y1 + radius == b.Y2 - radius);
5090 pp->parent.via =
5091 CreateNewVia (PCB->Data, b.X1 + radius,
5092 b.Y1 + radius,
5093 pp->style->Diameter,
5094 2 * pp->style->Keepaway,
5095 0, pp->style->Hole, NULL,
5096 MakeFlags (AUTOFLAG));
5097 assert (pp->parent.via);
5098 if (pp->parent.via)
5100 AddObjectToCreateUndoList (VIA_TYPE,
5101 pp->parent.via,
5102 pp->parent.via,
5103 pp->parent.via);
5104 changed = true;
5107 assert (pp->parent.via);
5108 if (p->type == VIA_SHADOW)
5110 p->type = VIA;
5111 p->parent.via = pp->parent.via;
5114 else if (p->type == THERMAL)
5115 /* nothing to do because, the via might not be there yet */ ;
5116 else
5117 assert (0);
5120 END_LOOP;
5121 /* loop again to place all the thermals now that the vias are down */
5122 LIST_LOOP (net, same_net, p);
5124 if (p->type == THERMAL)
5126 PinType *pin = NULL;
5127 /* thermals are alread a single point search, no need to shrink */
5128 int type = FindPin (&p->box, &pin);
5129 if (pin)
5131 AddObjectToClearPolyUndoList (type,
5132 pin->Element ? pin->Element : pin,
5133 pin, pin, false);
5134 RestoreToPolygon (PCB->Data, VIA_TYPE, LAYER_PTR (p->layer),
5135 pin);
5136 AddObjectToFlagUndoList (type,
5137 pin->Element ? pin->Element : pin, pin,
5138 pin);
5139 ASSIGN_THERM (p->layer, PCB->ThermStyle, pin);
5140 AddObjectToClearPolyUndoList (type,
5141 pin->Element ? pin->Element : pin,
5142 pin, pin, true);
5143 ClearFromPolygon (PCB->Data, VIA_TYPE, LAYER_PTR (p->layer),
5144 pin);
5145 changed = true;
5149 END_LOOP;
5151 END_LOOP;
5152 return changed;
5155 bool
5156 AutoRoute (bool selected)
5158 bool changed = false;
5159 routedata_t *rd;
5160 int i;
5162 total_wire_length = 0;
5163 total_via_count = 0;
5165 #ifdef ROUTE_DEBUG
5166 ddraw = gui->request_debug_draw ();
5167 if (ddraw != NULL)
5169 ar_gc = ddraw->graphics->make_gc ();
5170 ddraw->graphics->set_line_cap (ar_gc, Round_Cap);
5172 #endif
5174 for (i = 0; i < NUM_STYLES; i++)
5176 if (PCB->RouteStyle[i].Thick == 0 ||
5177 PCB->RouteStyle[1].Diameter == 0 ||
5178 PCB->RouteStyle[1].Hole == 0 || PCB->RouteStyle[i].Keepaway == 0)
5180 Message ("You must define proper routing styles\n"
5181 "before auto-routing.\n");
5182 return (false);
5185 if (PCB->Data->RatN == 0)
5186 return (false);
5187 SaveFindFlag (DRCFLAG);
5188 rd = CreateRouteData ();
5190 if (1)
5192 routebox_t *net, *rb, *last;
5193 int i = 0;
5194 /* count number of rats selected */
5195 RAT_LOOP (PCB->Data);
5197 if (!selected || TEST_FLAG (SELECTEDFLAG, line))
5198 i++;
5200 END_LOOP;
5201 #ifdef ROUTE_VERBOSE
5202 printf ("%d nets!\n", i);
5203 #endif
5204 if (i == 0)
5205 goto donerouting; /* nothing to do here */
5206 /* if only one rat selected, do things the quick way. =) */
5207 if (i == 1)
5209 RAT_LOOP (PCB->Data);
5210 if (!selected || TEST_FLAG (SELECTEDFLAG, line))
5212 /* look up the end points of this rat line */
5213 routebox_t *a =
5214 FindRouteBoxOnLayerGroup (rd, line->Point1.X,
5215 line->Point1.Y, line->group1);
5216 routebox_t *b =
5217 FindRouteBoxOnLayerGroup (rd, line->Point2.X,
5218 line->Point2.Y, line->group2);
5220 /* If the rat starts or ends at a non-straight pad (i.e., at a
5221 * rotated SMD), a or b will be NULL since the autorouter can't
5222 * handle these.
5224 if (a != NULL && b != NULL)
5226 assert (a->style == b->style);
5227 /* route exactly one net, without allowing conflicts */
5228 InitAutoRouteParameters (0, a->style, false, true, true);
5229 /* hace planes work better as sources than targets */
5230 changed = RouteOne (rd, a, b, 150000).found_route || changed;
5231 goto donerouting;
5234 END_LOOP;
5236 /* otherwise, munge the netlists so that only the selected rats
5237 * get connected. */
5238 /* first, separate all sub nets into separate nets */
5239 /* note that this code works because LIST_LOOP is clever enough not to
5240 * be fooled when the list is changing out from under it. */
5241 last = NULL;
5242 LIST_LOOP (rd->first_net, different_net, net);
5244 FOREACH_SUBNET (net, rb);
5246 if (last)
5248 last->different_net.next = rb;
5249 rb->different_net.prev = last;
5251 last = rb;
5253 END_FOREACH (net, rb);
5254 LIST_LOOP (net, same_net, rb);
5256 rb->same_net = rb->same_subnet;
5258 END_LOOP;
5259 /* at this point all nets are equal to their subnets */
5261 END_LOOP;
5262 if (last)
5264 last->different_net.next = rd->first_net;
5265 rd->first_net->different_net.prev = last;
5268 /* now merge only those subnets connected by a rat line */
5269 RAT_LOOP (PCB->Data);
5270 if (!selected || TEST_FLAG (SELECTEDFLAG, line))
5272 /* look up the end points of this rat line */
5273 routebox_t *a;
5274 routebox_t *b;
5276 FindRouteBoxOnLayerGroup (rd, line->Point1.X,
5277 line->Point1.Y, line->group1);
5279 FindRouteBoxOnLayerGroup (rd, line->Point2.X,
5280 line->Point2.Y, line->group2);
5281 if (!a || !b)
5283 #ifdef DEBUG_STALE_RATS
5284 AddObjectToFlagUndoList (RATLINE_TYPE, line, line, line);
5285 ASSIGN_FLAG (SELECTEDFLAG, true, line);
5286 DrawRat (line, 0);
5287 #endif /* DEBUG_STALE_RATS */
5288 Message ("The rats nest is stale! Aborting autoroute...\n");
5289 goto donerouting;
5291 /* merge subnets into a net! */
5292 MergeNets (a, b, NET);
5294 END_LOOP;
5295 /* now 'different_net' may point to too many different nets. Reset. */
5296 LIST_LOOP (rd->first_net, different_net, net);
5298 if (!net->flags.touched)
5300 LIST_LOOP (net, same_net, rb);
5301 rb->flags.touched = 1;
5302 END_LOOP;
5304 else /* this is not a "different net"! */
5305 RemoveFromNet (net, DIFFERENT_NET);
5307 END_LOOP;
5308 /* reset "touched" flag */
5309 LIST_LOOP (rd->first_net, different_net, net);
5311 LIST_LOOP (net, same_net, rb);
5313 assert (rb->flags.touched);
5314 rb->flags.touched = 0;
5316 END_LOOP;
5318 END_LOOP;
5320 /* okay, rd's idea of netlist now corresponds to what we want routed */
5321 /* auto-route all nets */
5322 changed = (RouteAll (rd).total_nets_routed > 0) || changed;
5323 donerouting:
5324 gui->progress (0, 0, NULL);
5325 if (TEST_FLAG (LIVEROUTEFLAG, PCB))
5327 int i;
5328 BoxType big = {0, 0, MAX_COORD, MAX_COORD};
5329 for (i = 0; i < max_group; i++)
5331 r_search (rd->layergrouptree[i], &big, NULL, ripout_livedraw_obj_cb, NULL);
5334 #ifdef ROUTE_DEBUG
5335 if (ddraw != NULL)
5336 ddraw->finish_debug_draw ();
5337 #endif
5339 if (changed)
5340 changed = IronDownAllUnfixedPaths (rd);
5341 Message ("Total added wire length = %$mS, %d vias added\n",
5342 (Coord) total_wire_length, total_via_count);
5343 DestroyRouteData (&rd);
5344 if (changed)
5346 SaveUndoSerialNumber ();
5348 /* optimize rats, we've changed connectivity a lot. */
5349 DeleteRats (false /*all rats */ );
5350 RestoreUndoSerialNumber ();
5351 AddAllRats (false /*all rats */ , NULL);
5352 RestoreUndoSerialNumber ();
5354 IncrementUndoSerialNumber ();
5356 Redraw ();
5358 RestoreFindFlag ();
5359 #if defined (ROUTE_DEBUG)
5360 aabort = 0;
5361 #endif
5362 return (changed);