6 * PCB, interactive printed circuit board design
7 * Copyright (C) 1994,1995,1996 Thomas Nau
8 * Copyright (C) 1998,1999,2000,2001 harry eaton
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; either version 2 of the License, or
13 * (at your option) any later version.
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
24 * Contact addresses for paper mail and Email:
25 * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
26 * haceaton@aplcomm.jhuapl.edu
29 /* this file, autoroute.c, was written and is
30 * Copyright (c) 2001 C. Scott Ananian
31 * Copyright (c) 2006 harry eaton
32 * Copyright (c) 2009 harry eaton
34 /* functions used to autoroute nets.
37 *-------------------------------------------------------------------
38 * This file implements a rectangle-expansion router, based on
39 * "A Method for Gridless Routing of Printed Circuit Boards" by
40 * A. C. Finch, K. J. Mackenzie, G. J. Balsdon, and G. Symonds in the
41 * 1985 Proceedings of the 22nd ACM/IEEE Design Automation Conference.
42 * This reference is available from the ACM Digital Library at
43 * http://www.acm.org/dl for those with institutional or personal
44 * access to it. It's also available from your local engineering
47 * The code is much closer to what is described in the paper now,
48 * in that expansion areas can grow from corners and in all directions
49 * at once. Previously, these were emulated with discrete boxes moving
50 * in the cardinal directions. With the new method, there are fewer but
51 * larger expansion boxes that one might do a better job of routing in.
52 *--------------------------------------------------------------------
66 #include "autoroute.h"
84 #ifdef HAVE_LIBDMALLOC
90 /* #defines to enable some debugging output */
97 //#define DEBUG_SHOW_ROUTE_BOXES
98 #define DEBUG_SHOW_EXPANSION_BOXES
99 //#define DEBUG_SHOW_EDGES
100 //#define DEBUG_SHOW_VIA_BOXES
101 #define DEBUG_SHOW_TARGETS
102 #define DEBUG_SHOW_SOURCES
103 //#define DEBUG_SHOW_ZIGZAG
106 static hidGC ar_gc
= 0;
108 #define EXPENSIVE 3e28
109 /* round up "half" thicknesses */
110 #define HALF_THICK(x) (((x)+1)/2)
111 /* a styles maximum bloat is its keepaway plus the larger of its via radius
112 * or line half-thickness. */
113 #define BLOAT(style)\
114 ((style)->Keepaway + HALF_THICK((style)->Thick))
115 /* conflict penalty is less for traces laid down during previous pass than
116 * it is for traces already laid down in this pass. */
117 #define CONFLICT_LEVEL(rb)\
118 (((rb)->flags.is_odd==AutoRouteParameters.is_odd) ?\
119 HI_CONFLICT : LO_CONFLICT )
120 #define CONFLICT_PENALTY(rb)\
121 ((CONFLICT_LEVEL(rb)==HI_CONFLICT ? \
122 AutoRouteParameters.ConflictPenalty : \
123 CONFLICT_LEVEL(rb)==LO_CONFLICT ? \
124 AutoRouteParameters.LastConflictPenalty : 1) * (rb)->pass)
127 #define ABS(x) (((x)<0)?-(x):(x))
135 #define LIST_LOOP(init, which, x) do {\
136 routebox_t *__next_one__ = (init);\
139 assert(__next_one__);\
141 while (!x || __next_one__ != (init)) {\
143 /* save next one first in case the command modifies or frees it */\
144 __next_one__ = x->which.next
145 #define FOREACH_SUBNET(net, p) do {\
147 /* fail-fast: check subnet_processed flags */\
148 LIST_LOOP(net, same_net, p); \
149 assert(!p->flags.subnet_processed);\
151 /* iterate through *distinct* subnets */\
152 LIST_LOOP(net, same_net, p); \
153 if (!p->flags.subnet_processed) {\
154 LIST_LOOP(p, same_subnet, _pp_);\
155 _pp_->flags.subnet_processed=1;\
157 #define END_FOREACH(net, p) \
160 /* reset subnet_processed flags */\
161 LIST_LOOP(net, same_net, p); \
162 p->flags.subnet_processed=0;\
165 #define SWAP(t, f, s) do { t a=s; s=f; f=a; } while (0)
167 * all rectangles are assumed to be closed on the top and left and
168 * open on the bottom and right. That is, they include their top-left
169 * corner but don't include their bottom and right edges.
171 * expansion regions are always half-closed. This means that when
172 * tracing paths, you must steer clear of the bottom and right edges.,
173 * because these are not actually in the allowed box.
175 * All routeboxes *except* EXPANSION_AREAS now have their "box" bloated by
176 * their particular required keepaway. This simplifies the tree searching.
177 * the "sbox" contains the unbloated box.
179 /* ---------------------------------------------------------------------------
183 /* enumerated type for conflict levels */
185 { NO_CONFLICT
= 0, LO_CONFLICT
= 1, HI_CONFLICT
= 2 }
188 typedef struct routebox
190 const BoxType box
, sbox
;
196 struct routebox
*via_shadow
; /* points to the via in r-tree which
197 * points to the PinType in the PCB. */
199 void *generic
; /* 'other' is polygon, arc, text */
200 struct routebox
*expansion_area
; /* previous expansion area in search */
203 unsigned short group
;
204 unsigned short layer
;
206 { PAD
, PIN
, VIA
, VIA_SHADOW
, LINE
, OTHER
, EXPANSION_AREA
, PLANE
, THERMAL
}
210 unsigned nonstraight
:1;
215 /* rects on same net as source and target don't need clearance areas */
217 /* mark circular pins, so that we be sure to connect them up properly */
219 /* we sometimes create routeboxen that don't actually belong to a
220 * r-tree yet -- make sure refcount of homelesss is set properly */
222 /* was this nonfixed obstacle generated on an odd or even pass? */
224 /* fixed route boxes that have already been "routed through" in this
225 * search have their "touched" flag set. */
227 /* this is a status bit for iterating through *different* subnets */
228 unsigned subnet_processed
:1;
229 /* some expansion_areas represent via candidates */
231 /* mark non-straight lines which go from bottom-left to upper-right,
232 * instead of from upper-left to bottom-right. */
234 /* mark polygons which are "transparent" for via-placement; that is,
235 * vias through the polygon will automatically be given a keepaway
236 * and will not electrically connect to the polygon. */
237 unsigned clear_poly
:1;
238 /* this marks "conflicting" routes that must be torn up to obtain
239 * a correct routing. This flag allows us to return a correct routing
240 * even if the user cancels auto-route after a non-final pass. */
242 /* for assertion that 'box' is never changed after creation */
244 /* indicate this expansion ares is a thermal between the pin and plane */
248 /* indicate the direction an expansion box came from */
250 CheapPointType cost_point
;
251 /* reference count for homeless routeboxes; free when refcount==0 */
253 /* when routing with conflicts, we keep a record of what we're
256 vector_t
*conflicts_with
;
257 /* route style of the net associated with this routebox */
258 RouteStyleType
*style
;
259 /* congestion values for the edges of an expansion box */
260 unsigned char n
, e
, s
, w
;
261 /* what pass this this track was laid down on */
263 /* the direction this came from, if any */
264 direction_t came_from
;
265 /* circular lists with connectivity information. */
268 struct routebox
*next
, *prev
;
270 same_net
, same_subnet
, original_subnet
, different_net
;
274 typedef struct routedata
276 /* one rtree per layer *group */
277 rtree_t
*layergrouptree
[MAX_LAYER
]; /* no silkscreen layers here =) */
278 /* root pointer into connectivity information */
279 routebox_t
*first_net
;
280 /* default routing style */
281 RouteStyleType defaultstyle
;
282 /* style structures */
283 RouteStyleType
*styles
[NUM_STYLES
+ 1];
284 /* what is the maximum bloat (keepaway+line half-width or
285 * keepaway+via_radius) for any style we've seen? */
286 BDimension max_bloat
;
292 typedef struct edge_struct
294 routebox_t
*rb
; /* path expansion edges are real routeboxen. */
295 CheapPointType cost_point
;
296 cost_t cost_to_point
; /* from source */
297 cost_t cost
; /* cached edge cost */
298 routebox_t
*mincost_target
; /* minimum cost from cost_point to any target */
299 vetting_t
*work
; /* for via search edges */
300 direction_t expand_dir
;
303 /* this indicates that this 'edge' is a via candidate. */
305 /* record "conflict level" of via candidates, in case we need to split
307 conflict_t via_conflict_level
:2;
308 /* when "routing with conflicts", sometimes edge is interior. */
309 unsigned is_interior
:1;
310 /* this is a fake edge used to defer searching for via spaces */
311 unsigned via_search
:1;
312 /* this is a via edge in a plane where the cost point moves for free */
321 /* net style parameters */
322 RouteStyleType
*style
;
323 /* the present bloat */
325 /* cost parameters */
326 cost_t ViaCost
, /* additional "length" cost for using a via */
327 LastConflictPenalty
, /* length mult. for routing over last pass' trace */
328 ConflictPenalty
, /* length multiplier for routing over another trace */
329 JogPenalty
, /* additional "length" cost for changing direction */
330 CongestionPenalty
, /* (rational) length multiplier for routing in */
331 NewLayerPenalty
, /* penalty for routing on a previously unused layer */
332 MinPenalty
; /* smallest Direction Penalty */
333 /* maximum conflict incidence before calling it "no path found" */
335 /* are vias allowed? */
337 /* is this an odd or even pass? */
339 /* permit conflicts? */
340 Boolean with_conflicts
;
341 /* is this a final "smoothing" pass? */
342 Boolean is_smoothing
;
343 /* rip up nets regardless of conflicts? */
350 struct routeone_state
352 /* heap of all candidate expansion edges */
354 /* information about the best path found so far. */
355 routebox_t
*best_path
, *best_target
;
360 /* ---------------------------------------------------------------------------
361 * some local prototypes
363 static routebox_t
*CreateExpansionArea (const BoxType
* area
, Cardinal group
,
365 Boolean relax_edge_requirements
,
368 static cost_t
edge_cost (const edge_t
* e
, const cost_t too_big
);
369 static void best_path_candidate (struct routeone_state
*s
,
370 edge_t
* e
, routebox_t
* best_target
);
372 static BoxType
edge_to_box (const routebox_t
* rb
, direction_t expand_dir
);
374 static void add_or_destroy_edge (struct routeone_state
*s
, edge_t
* e
);
377 RD_DrawThermal (routedata_t
* rd
, LocationType X
, LocationType Y
,
378 Cardinal group
, Cardinal layer
, routebox_t
* subnet
,
380 static void ResetSubnet (routebox_t
* net
);
382 static int showboxen
= -2;
383 static int aabort
= 0;
384 static void showroutebox (routebox_t
* rb
);
387 /* ---------------------------------------------------------------------------
388 * some local identifiers
390 /* group number of groups that hold surface mount pads */
391 static Cardinal front
, back
;
392 static Boolean usedGroup
[MAX_LAYER
];
393 static int x_cost
[MAX_LAYER
], y_cost
[MAX_LAYER
];
394 static Boolean is_layer_group_active
[MAX_LAYER
];
396 static int smoothes
= 1;
397 static int passes
= 12;
398 static int routing_layers
= 0;
399 static float total_wire_length
= 0;
400 static int total_via_count
= 0;
402 /* assertion helper for routeboxen */
405 __routebox_is_good (routebox_t
* rb
)
407 assert (rb
&& (rb
->group
< max_layer
) &&
408 (rb
->box
.X1
<= rb
->box
.X2
) && (rb
->box
.Y1
<= rb
->box
.Y2
) &&
409 (rb
->flags
.homeless
?
410 (rb
->box
.X1
!= rb
->box
.X2
) || (rb
->box
.Y1
!= rb
->box
.Y2
) :
411 (rb
->box
.X1
!= rb
->box
.X2
) && (rb
->box
.Y1
!= rb
->box
.Y2
)));
412 assert ((rb
->flags
.source
? rb
->flags
.nobloat
: 1) &&
413 (rb
->flags
.target
? rb
->flags
.nobloat
: 1) &&
414 (rb
->flags
.homeless
? !rb
->flags
.touched
: rb
->refcount
== 0) &&
415 (rb
->flags
.touched
? rb
->type
!= EXPANSION_AREA
: 1));
416 assert ((rb
->flags
.is_odd
? (!rb
->flags
.fixed
) &&
417 (rb
->type
== VIA
|| rb
->type
== VIA_SHADOW
|| rb
->type
== LINE
418 || rb
->type
== PLANE
) : 1));
419 assert (rb
->flags
.clear_poly
?
420 ((rb
->type
== OTHER
|| rb
->type
== PLANE
) && rb
->flags
.fixed
421 && !rb
->flags
.homeless
) : 1);
422 assert (rb
->flags
.inited
);
423 /* run through conflict list showing none are homeless, targets or sources */
424 if (rb
->conflicts_with
)
427 for (i
= 0; i
< vector_size (rb
->conflicts_with
); i
++)
429 routebox_t
*c
= vector_element (rb
->conflicts_with
, i
);
430 assert (!c
->flags
.homeless
&& !c
->flags
.source
&& !c
->flags
.target
434 assert (rb
->style
!= NULL
&& rb
->style
!= NULL
);
435 assert (rb
->type
== EXPANSION_AREA
436 || (rb
->same_net
.next
&& rb
->same_net
.prev
&& rb
->same_subnet
.next
437 && rb
->same_subnet
.prev
&& rb
->original_subnet
.next
438 && rb
->original_subnet
.prev
&& rb
->different_net
.next
439 && rb
->different_net
.prev
));
443 __edge_is_good (edge_t
* e
)
445 assert (e
&& e
->rb
&& __routebox_is_good (e
->rb
));
446 assert ((e
->rb
->flags
.homeless
? e
->rb
->refcount
> 0 : 1));
447 assert ((0 <= e
->expand_dir
) && (e
->expand_dir
< 9)
449 is_interior
? (e
->expand_dir
== ALL
450 && e
->rb
->conflicts_with
) : 1));
451 assert ((e
->flags
.is_via
? e
->rb
->flags
.is_via
: 1)
452 && (e
->flags
.via_conflict_level
>= 0
453 && e
->flags
.via_conflict_level
<= 2)
454 && (e
->flags
.via_conflict_level
!= 0 ? e
->flags
.is_via
: 1));
455 assert ((e
->cost_to_point
>= 0) && e
->cost
>= 0);
460 no_planes (const BoxType
* b
, void *cl
)
462 routebox_t
*rb
= (routebox_t
*) b
;
463 if (rb
->type
== PLANE
)
469 /*---------------------------------------------------------------------
470 * route utility functions.
474 { NET
, SUBNET
, ORIGINAL
, DIFFERENT_NET
};
475 static struct routebox_list
*
476 __select_list (routebox_t
* r
, enum boxlist which
)
484 return &(r
->same_net
);
486 return &(r
->same_subnet
);
488 return &(r
->original_subnet
);
490 return &(r
->different_net
);
494 InitLists (routebox_t
* r
)
496 static enum boxlist all
[] =
497 { NET
, SUBNET
, ORIGINAL
, DIFFERENT_NET
}
499 for (p
= all
; p
< all
+ (sizeof (all
) / sizeof (*p
)); p
++)
501 struct routebox_list
*rl
= __select_list (r
, *p
);
502 rl
->prev
= rl
->next
= r
;
507 MergeNets (routebox_t
* a
, routebox_t
* b
, enum boxlist which
)
509 struct routebox_list
*al
, *bl
, *anl
, *bnl
;
513 assert (a
->type
!= EXPANSION_AREA
);
514 assert (b
->type
!= EXPANSION_AREA
);
515 al
= __select_list (a
, which
);
516 bl
= __select_list (b
, which
);
521 anl
= __select_list (an
, which
);
522 bnl
= __select_list (bn
, which
);
531 RemoveFromNet (routebox_t
* a
, enum boxlist which
)
533 struct routebox_list
*al
, *anl
, *apl
;
536 al
= __select_list (a
, which
);
540 if (an
== a
|| ap
== a
)
541 return; /* not on any list */
543 anl
= __select_list (an
, which
);
544 apl
= __select_list (ap
, which
);
548 al
->next
= al
->prev
= a
;
553 init_const_box (routebox_t
* rb
,
554 LocationType X1
, LocationType Y1
, LocationType X2
,
555 LocationType Y2
, BDimension keepaway
)
557 BoxType
*bp
= (BoxType
*) & rb
->box
; /* note discarding const! */
558 assert (!rb
->flags
.inited
);
559 assert (X1
<= X2
&& Y1
<= Y2
);
560 bp
->X1
= X1
- keepaway
;
561 bp
->Y1
= Y1
- keepaway
;
562 bp
->X2
= X2
+ keepaway
;
563 bp
->Y2
= Y2
+ keepaway
;
564 bp
= (BoxType
*) & rb
->sbox
;
569 rb
->flags
.inited
= 1;
572 static inline BoxType
573 shrink_routebox (const routebox_t
* rb
)
579 box_area (const BoxType b
)
581 cost_t ans
= b
.X2
- b
.X1
;
582 return ans
* (b
.Y2
- b
.Y1
);
585 static inline CheapPointType
586 closest_point_in_routebox (const CheapPointType
* from
, const routebox_t
* rb
)
588 return closest_point_in_box (from
, &rb
->sbox
);
591 static inline Boolean
592 point_in_shrunk_box (const routebox_t
* box
, LocationType X
, LocationType Y
)
594 BoxType b
= shrink_routebox (box
);
595 return point_in_box (&b
, X
, Y
);
598 /*---------------------------------------------------------------------
599 * routedata initialization functions.
603 AddPin (PointerListType layergroupboxes
[], PinTypePtr pin
, Boolean is_via
,
604 RouteStyleType
* style
)
606 routebox_t
**rbpp
, *lastrb
= NULL
;
608 /* a pin cuts through every layer group */
609 for (i
= 0; i
< max_layer
; i
++)
611 rbpp
= (routebox_t
**) GetPointerMemory (&layergroupboxes
[i
]);
612 *rbpp
= malloc (sizeof (**rbpp
));
613 memset ((void *) *rbpp
, 0, sizeof (**rbpp
));
615 ht
= HALF_THICK (MAX (pin
->Thickness
, pin
->DrillingHole
));
616 init_const_box (*rbpp
,
620 /*Y2 */ pin
->Y
+ ht
, style
->Keepaway
);
621 /* set aux. properties */
625 (*rbpp
)->parent
.via
= pin
;
630 (*rbpp
)->parent
.pin
= pin
;
632 (*rbpp
)->flags
.fixed
= 1;
633 (*rbpp
)->came_from
= ALL
;
634 (*rbpp
)->style
= style
;
635 (*rbpp
)->flags
.circular
= !TEST_FLAG (SQUAREFLAG
, pin
);
641 MergeNets (*rbpp
, lastrb
, NET
);
642 MergeNets (*rbpp
, lastrb
, SUBNET
);
643 MergeNets (*rbpp
, lastrb
, ORIGINAL
);
650 AddPad (PointerListType layergroupboxes
[],
651 ElementTypePtr element
, PadTypePtr pad
, RouteStyleType
* style
)
653 BDimension halfthick
;
655 int layergroup
= (TEST_FLAG (ONSOLDERFLAG
, pad
) ? back
: front
);
656 assert (0 <= layergroup
&& layergroup
< max_layer
);
657 assert (PCB
->LayerGroups
.Number
[layergroup
] > 0);
658 rbpp
= (routebox_t
**) GetPointerMemory (&layergroupboxes
[layergroup
]);
660 *rbpp
= malloc (sizeof (**rbpp
));
662 memset (*rbpp
, 0, sizeof (**rbpp
));
663 (*rbpp
)->group
= layergroup
;
664 halfthick
= HALF_THICK (pad
->Thickness
);
665 init_const_box (*rbpp
,
666 /*X1 */ MIN (pad
->Point1
.X
, pad
->Point2
.X
) - halfthick
,
667 /*Y1 */ MIN (pad
->Point1
.Y
, pad
->Point2
.Y
) - halfthick
,
668 /*X2 */ MAX (pad
->Point1
.X
, pad
->Point2
.X
) + halfthick
,
669 /*Y2 */ MAX (pad
->Point1
.Y
, pad
->Point2
.Y
) + halfthick
,
671 /* kludge for non-manhattan pads (which are not allowed at present) */
672 if (pad
->Point1
.X
!= pad
->Point2
.X
&& pad
->Point1
.Y
!= pad
->Point2
.Y
)
673 (*rbpp
)->flags
.nonstraight
= 1;
674 /* set aux. properties */
676 (*rbpp
)->parent
.pad
= pad
;
677 (*rbpp
)->flags
.fixed
= 1;
678 (*rbpp
)->came_from
= ALL
;
679 (*rbpp
)->style
= style
;
685 AddLine (PointerListType layergroupboxes
[], int layergroup
, LineTypePtr line
,
686 LineTypePtr ptr
, RouteStyleType
* style
)
689 assert (layergroupboxes
&& line
);
690 assert (0 <= layergroup
&& layergroup
< max_layer
);
691 assert (PCB
->LayerGroups
.Number
[layergroup
] > 0);
693 rbpp
= (routebox_t
**) GetPointerMemory (&layergroupboxes
[layergroup
]);
694 *rbpp
= malloc (sizeof (**rbpp
));
695 memset (*rbpp
, 0, sizeof (**rbpp
));
696 (*rbpp
)->group
= layergroup
;
697 init_const_box (*rbpp
,
698 /*X1 */ MIN (line
->Point1
.X
,
699 line
->Point2
.X
) - HALF_THICK (line
->Thickness
),
700 /*Y1 */ MIN (line
->Point1
.Y
,
701 line
->Point2
.Y
) - HALF_THICK (line
->Thickness
),
702 /*X2 */ MAX (line
->Point1
.X
,
703 line
->Point2
.X
) + HALF_THICK (line
->Thickness
),
704 /*Y2 */ MAX (line
->Point1
.Y
,
706 HALF_THICK (line
->Thickness
), style
->Keepaway
);
707 /* kludge for non-manhattan lines */
708 if (line
->Point1
.X
!= line
->Point2
.X
&& line
->Point1
.Y
!= line
->Point2
.Y
)
710 (*rbpp
)->flags
.nonstraight
= 1;
711 (*rbpp
)->flags
.bl_to_ur
=
712 (MIN (line
->Point1
.X
, line
->Point2
.X
) == line
->Point1
.X
) !=
713 (MIN (line
->Point1
.Y
, line
->Point2
.Y
) == line
->Point1
.Y
);
714 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ZIGZAG)
715 showroutebox (*rbpp
);
718 /* set aux. properties */
719 (*rbpp
)->type
= LINE
;
720 (*rbpp
)->parent
.line
= ptr
;
721 (*rbpp
)->flags
.fixed
= 1;
722 (*rbpp
)->came_from
= ALL
;
723 (*rbpp
)->style
= style
;
729 AddIrregularObstacle (PointerListType layergroupboxes
[],
730 LocationType X1
, LocationType Y1
,
731 LocationType X2
, LocationType Y2
, Cardinal layergroup
,
732 void *parent
, RouteStyleType
* style
)
735 LocationType keep
= style
->Keepaway
;
736 assert (layergroupboxes
&& parent
);
737 assert (X1
<= X2
&& Y1
<= Y2
);
738 assert (0 <= layergroup
&& layergroup
< max_layer
);
739 assert (PCB
->LayerGroups
.Number
[layergroup
] > 0);
741 rbpp
= (routebox_t
**) GetPointerMemory (&layergroupboxes
[layergroup
]);
742 *rbpp
= malloc (sizeof (**rbpp
));
743 memset (*rbpp
, 0, sizeof (**rbpp
));
744 (*rbpp
)->group
= layergroup
;
745 init_const_box (*rbpp
, X1
, Y1
, X2
, Y2
, keep
);
746 (*rbpp
)->flags
.nonstraight
= 1;
747 (*rbpp
)->type
= OTHER
;
748 (*rbpp
)->parent
.generic
= parent
;
749 (*rbpp
)->flags
.fixed
= 1;
750 (*rbpp
)->style
= style
;
757 AddPolygon (PointerListType layergroupboxes
[], Cardinal layer
,
758 PolygonTypePtr polygon
, RouteStyleType
* style
)
760 int is_not_rectangle
= 1;
761 int layergroup
= GetLayerGroupNumberByNumber (layer
);
763 assert (0 <= layergroup
&& layergroup
< max_layer
);
764 rb
= AddIrregularObstacle (layergroupboxes
,
765 polygon
->BoundingBox
.X1
,
766 polygon
->BoundingBox
.Y1
,
767 polygon
->BoundingBox
.X2
,
768 polygon
->BoundingBox
.Y2
,
769 layergroup
, polygon
, style
);
770 if (polygon
->PointN
== 4 &&
771 (polygon
->Points
[0].X
== polygon
->Points
[1].X
||
772 polygon
->Points
[0].Y
== polygon
->Points
[1].Y
) &&
773 (polygon
->Points
[1].X
== polygon
->Points
[2].X
||
774 polygon
->Points
[1].Y
== polygon
->Points
[2].Y
) &&
775 (polygon
->Points
[2].X
== polygon
->Points
[3].X
||
776 polygon
->Points
[2].Y
== polygon
->Points
[3].Y
) &&
777 (polygon
->Points
[3].X
== polygon
->Points
[0].X
||
778 polygon
->Points
[3].Y
== polygon
->Points
[0].Y
))
779 is_not_rectangle
= 0;
780 rb
->flags
.nonstraight
= is_not_rectangle
;
783 if (TEST_FLAG (CLEARPOLYFLAG
, polygon
))
785 rb
->flags
.clear_poly
= 1;
786 if (!is_not_rectangle
)
792 AddText (PointerListType layergroupboxes
[], Cardinal layergroup
,
793 TextTypePtr text
, RouteStyleType
* style
)
795 AddIrregularObstacle (layergroupboxes
,
796 text
->BoundingBox
.X1
, text
->BoundingBox
.Y1
,
797 text
->BoundingBox
.X2
, text
->BoundingBox
.Y2
,
798 layergroup
, text
, style
);
801 AddArc (PointerListType layergroupboxes
[], Cardinal layergroup
,
802 ArcTypePtr arc
, RouteStyleType
* style
)
804 return AddIrregularObstacle (layergroupboxes
,
805 arc
->BoundingBox
.X1
, arc
->BoundingBox
.Y1
,
806 arc
->BoundingBox
.X2
, arc
->BoundingBox
.Y2
,
807 layergroup
, arc
, style
);
818 __found_one_on_lg (const BoxType
* box
, void *cl
)
820 struct rb_info
*inf
= (struct rb_info
*) cl
;
821 routebox_t
*rb
= (routebox_t
*) box
;
824 if (rb
->flags
.nonstraight
)
826 sb
= shrink_box (&rb
->box
, rb
->style
->Keepaway
);
827 if (inf
->query
.X1
>= sb
.X2
|| inf
->query
.X2
<= sb
.X1
||
828 inf
->query
.Y1
>= sb
.Y2
|| inf
->query
.Y2
<= sb
.Y1
)
831 if (rb
->type
== PLANE
)
832 return 1; /* keep looking for something smaller if a plane was found */
833 longjmp (inf
->env
, 1);
837 FindRouteBoxOnLayerGroup (routedata_t
* rd
,
838 LocationType X
, LocationType Y
, Cardinal layergroup
)
842 info
.query
= point_box (X
, Y
);
843 if (setjmp (info
.env
) == 0)
844 r_search (rd
->layergrouptree
[layergroup
], &info
.query
, NULL
,
845 __found_one_on_lg
, &info
);
849 #ifdef ROUTE_DEBUG_VERBOSE
851 DumpRouteBox (routebox_t
* rb
)
853 printf ("RB: (%d,%d)-(%d,%d) l%d; ",
854 rb
->box
.X1
, rb
->box
.Y1
, rb
->box
.X2
, rb
->box
.Y2
, (int) rb
->group
);
858 printf ("PAD[%s %s] ", rb
->parent
.pad
->Name
, rb
->parent
.pad
->Number
);
861 printf ("PIN[%s %s] ", rb
->parent
.pin
->Name
, rb
->parent
.pin
->Number
);
866 printf ("VIA[%s %s] ", rb
->parent
.via
->Name
, rb
->parent
.via
->Number
);
881 if (rb
->flags
.nonstraight
)
882 printf ("(nonstraight) ");
885 if (rb
->flags
.source
)
886 printf ("(source) ");
887 if (rb
->flags
.target
)
888 printf ("(target) ");
889 if (rb
->flags
.homeless
)
890 printf ("(homeless) ");
898 NetListListType Nets
;
899 PointerListType layergroupboxes
[MAX_LAYER
];
904 /* check which layers are active first */
906 for (group
= 0; group
< max_layer
; group
++)
908 for (i
= 0; i
< PCB
->LayerGroups
.Number
[group
]; i
++)
909 /* layer must be 1) not silk (ie, < max_layer) and 2) on */
910 if ((PCB
->LayerGroups
.Entries
[group
][i
] < max_layer
) &&
911 PCB
->Data
->Layer
[PCB
->LayerGroups
.Entries
[group
][i
]].On
)
914 is_layer_group_active
[group
] = True
;
918 is_layer_group_active
[group
] = False
;
920 /* if via visibility is turned off, don't use them */
921 AutoRouteParameters
.use_vias
= routing_layers
> 1 && PCB
->ViaOn
;
922 front
= GetLayerGroupNumberByNumber (max_layer
+ COMPONENT_LAYER
);
923 back
= GetLayerGroupNumberByNumber (max_layer
+ SOLDER_LAYER
);
924 /* determine preferred routing direction on each group */
925 for (i
= 0; i
< max_layer
; i
++)
927 if (i
!= back
&& i
!= front
)
929 x_cost
[i
] = (i
& 1) ? 2 : 1;
930 y_cost
[i
] = (i
& 1) ? 1 : 2;
943 /* create routedata */
944 rd
= malloc (sizeof (*rd
));
945 memset ((void *) rd
, 0, sizeof (*rd
));
946 /* create default style */
947 rd
->defaultstyle
.Thick
= Settings
.LineThickness
;
948 rd
->defaultstyle
.Diameter
= Settings
.ViaThickness
;
949 rd
->defaultstyle
.Hole
= Settings
.ViaDrillingHole
;
950 rd
->defaultstyle
.Keepaway
= Settings
.Keepaway
;
951 rd
->max_bloat
= BLOAT (&rd
->defaultstyle
);
952 rd
->max_keep
= Settings
.Keepaway
;
953 /* create styles structures */
954 bbox
.X1
= bbox
.Y1
= 0;
955 bbox
.X2
= PCB
->MaxWidth
;
956 bbox
.Y2
= PCB
->MaxHeight
;
957 for (i
= 0; i
< NUM_STYLES
+ 1; i
++)
959 RouteStyleType
*style
=
960 (i
< NUM_STYLES
) ? &PCB
->RouteStyle
[i
] : &rd
->defaultstyle
;
961 rd
->styles
[i
] = style
;
964 /* initialize pointerlisttype */
965 for (i
= 0; i
< max_layer
; i
++)
967 layergroupboxes
[i
].Ptr
= NULL
;
968 layergroupboxes
[i
].PtrN
= 0;
969 layergroupboxes
[i
].PtrMax
= 0;
970 GROUP_LOOP (PCB
->Data
, i
);
972 if (layer
->LineN
|| layer
->ArcN
)
975 usedGroup
[i
] = False
;
979 usedGroup
[front
] = True
;
980 usedGroup
[back
] = True
;
981 /* add the objects in the netlist first.
982 * then go and add all other objects that weren't already added
984 * this saves on searching the trees to find the nets
986 /* use the DRCFLAG to mark objects as they are entered */
987 ResetFoundPinsViasAndPads (False
);
988 ResetFoundLinesAndPolygons (False
);
989 Nets
= CollectSubnets (False
);
991 routebox_t
*last_net
= NULL
;
992 NETLIST_LOOP (&Nets
);
994 routebox_t
*last_in_net
= NULL
;
997 routebox_t
*last_in_subnet
= NULL
;
1000 for (j
= 0; j
< NUM_STYLES
; j
++)
1001 if (net
->Style
== rd
->styles
[j
])
1003 CONNECTION_LOOP (net
);
1005 routebox_t
*rb
= NULL
;
1006 SET_FLAG (DRCFLAG
, (PinTypePtr
) connection
->ptr2
);
1007 if (connection
->type
== LINE_TYPE
)
1009 LineType
*line
= (LineType
*) connection
->ptr2
;
1011 /* lines are listed at each end, so skip one */
1012 /* this should probably by a macro named "BUMP_LOOP" */
1015 /* dice up non-straight lines into many tiny obstacles */
1016 if (line
->Point1
.X
!= line
->Point2
.X
1017 && line
->Point1
.Y
!= line
->Point2
.Y
)
1019 LineType fake_line
= *line
;
1020 int dx
= (line
->Point2
.X
- line
->Point1
.X
);
1021 int dy
= (line
->Point2
.Y
- line
->Point1
.Y
);
1022 int segs
= MAX (ABS (dx
),
1023 ABS (dy
)) / (4 * BLOAT (rd
->styles
[j
]) + 1);
1025 segs
= MAX (1, MIN (segs
, 32)); /* don't go too crazy */
1028 for (qq
= 0; qq
< segs
- 1; qq
++)
1030 fake_line
.Point2
.X
= fake_line
.Point1
.X
+ dx
;
1031 fake_line
.Point2
.Y
= fake_line
.Point1
.Y
+ dy
;
1032 if (fake_line
.Point2
.X
== line
->Point2
.X
1033 && fake_line
.Point2
.Y
== line
->Point2
.Y
)
1036 AddLine (layergroupboxes
, connection
->group
,
1037 &fake_line
, line
, rd
->styles
[j
]);
1038 if (last_in_subnet
&& rb
!= last_in_subnet
)
1039 MergeNets (last_in_subnet
, rb
, ORIGINAL
);
1040 if (last_in_net
&& rb
!= last_in_net
)
1041 MergeNets (last_in_net
, rb
, NET
);
1042 last_in_subnet
= last_in_net
= rb
;
1043 fake_line
.Point1
= fake_line
.Point2
;
1045 fake_line
.Point2
= line
->Point2
;
1047 AddLine (layergroupboxes
, connection
->group
, &fake_line
,
1048 line
, rd
->styles
[j
]);
1053 AddLine (layergroupboxes
, connection
->group
, line
, line
,
1058 switch (connection
->type
)
1062 AddPad (layergroupboxes
, connection
->ptr1
,
1063 connection
->ptr2
, rd
->styles
[j
]);
1067 AddPin (layergroupboxes
, connection
->ptr2
, False
,
1072 AddPin (layergroupboxes
, connection
->ptr2
, True
,
1077 AddPolygon (layergroupboxes
,
1078 GetLayerNumber (PCB
->Data
, connection
->ptr1
),
1079 connection
->ptr2
, rd
->styles
[j
]);
1083 /* update circular connectivity lists */
1084 if (last_in_subnet
&& rb
!= last_in_subnet
)
1085 MergeNets (last_in_subnet
, rb
, ORIGINAL
);
1086 if (last_in_net
&& rb
!= last_in_net
)
1087 MergeNets (last_in_net
, rb
, NET
);
1088 last_in_subnet
= last_in_net
= rb
;
1089 rd
->max_bloat
= MAX (rd
->max_bloat
, BLOAT (rb
->style
));
1090 rd
->max_keep
= MAX (rd
->max_keep
, rb
->style
->Keepaway
);
1095 if (last_net
&& last_in_net
)
1096 MergeNets (last_net
, last_in_net
, DIFFERENT_NET
);
1097 last_net
= last_in_net
;
1100 rd
->first_net
= last_net
;
1102 FreeNetListListMemory (&Nets
);
1104 /* reset all nets to "original" connectivity (which we just set) */
1107 LIST_LOOP (rd
->first_net
, different_net
, net
);
1112 /* add pins and pads of elements */
1113 ALLPIN_LOOP (PCB
->Data
);
1115 if (TEST_FLAG (DRCFLAG
, pin
))
1116 CLEAR_FLAG (DRCFLAG
, pin
);
1118 AddPin (layergroupboxes
, pin
, False
, rd
->styles
[NUM_STYLES
]);
1121 ALLPAD_LOOP (PCB
->Data
);
1123 if (TEST_FLAG (DRCFLAG
, pad
))
1124 CLEAR_FLAG (DRCFLAG
, pad
);
1126 AddPad (layergroupboxes
, element
, pad
, rd
->styles
[NUM_STYLES
]);
1130 VIA_LOOP (PCB
->Data
);
1132 if (TEST_FLAG (DRCFLAG
, via
))
1133 CLEAR_FLAG (DRCFLAG
, via
);
1135 AddPin (layergroupboxes
, via
, True
, rd
->styles
[NUM_STYLES
]);
1139 for (i
= 0; i
< max_layer
; i
++)
1141 int layergroup
= GetLayerGroupNumberByNumber (i
);
1142 /* add all (non-rat) lines */
1143 LINE_LOOP (LAYER_PTR (i
));
1145 if (TEST_FLAG (DRCFLAG
, line
))
1147 CLEAR_FLAG (DRCFLAG
, line
);
1150 /* dice up non-straight lines into many tiny obstacles */
1151 if (line
->Point1
.X
!= line
->Point2
.X
1152 && line
->Point1
.Y
!= line
->Point2
.Y
)
1154 LineType fake_line
= *line
;
1155 int dx
= (line
->Point2
.X
- line
->Point1
.X
);
1156 int dy
= (line
->Point2
.Y
- line
->Point1
.Y
);
1157 int segs
= MAX (ABS (dx
), ABS (dy
)) / (4 * rd
->max_bloat
+ 1);
1159 segs
= MAX (1, MIN (segs
, 32)); /* don't go too crazy */
1162 for (qq
= 0; qq
< segs
- 1; qq
++)
1164 fake_line
.Point2
.X
= fake_line
.Point1
.X
+ dx
;
1165 fake_line
.Point2
.Y
= fake_line
.Point1
.Y
+ dy
;
1166 if (fake_line
.Point2
.X
== line
->Point2
.X
1167 && fake_line
.Point2
.Y
== line
->Point2
.Y
)
1169 AddLine (layergroupboxes
, layergroup
, &fake_line
, line
,
1170 rd
->styles
[NUM_STYLES
]);
1171 fake_line
.Point1
= fake_line
.Point2
;
1173 fake_line
.Point2
= line
->Point2
;
1174 AddLine (layergroupboxes
, layergroup
, &fake_line
, line
,
1175 rd
->styles
[NUM_STYLES
]);
1179 AddLine (layergroupboxes
, layergroup
, line
, line
,
1180 rd
->styles
[NUM_STYLES
]);
1184 /* add all polygons */
1185 POLYGON_LOOP (LAYER_PTR (i
));
1187 if (TEST_FLAG (DRCFLAG
, polygon
))
1188 CLEAR_FLAG (DRCFLAG
, polygon
);
1190 AddPolygon (layergroupboxes
, i
, polygon
, rd
->styles
[NUM_STYLES
]);
1193 /* add all copper text */
1194 TEXT_LOOP (LAYER_PTR (i
));
1196 AddText (layergroupboxes
, layergroup
, text
, rd
->styles
[NUM_STYLES
]);
1200 ARC_LOOP (LAYER_PTR (i
));
1202 AddArc (layergroupboxes
, layergroup
, arc
, rd
->styles
[NUM_STYLES
]);
1207 /* create r-trees from pointer lists */
1208 for (i
= 0; i
< max_layer
; i
++)
1210 /* create the r-tree */
1211 rd
->layergrouptree
[i
] =
1212 r_create_tree ((const BoxType
**) layergroupboxes
[i
].Ptr
,
1213 layergroupboxes
[i
].PtrN
, 1);
1216 if (AutoRouteParameters
.use_vias
)
1218 rd
->mtspace
= mtspace_create ();
1220 /* create "empty-space" structures for via placement (now that we know
1221 * appropriate keepaways for all the fixed elements) */
1222 for (i
= 0; i
< max_layer
; i
++)
1224 POINTER_LOOP (&layergroupboxes
[i
]);
1226 routebox_t
*rb
= (routebox_t
*) * ptr
;
1227 if (!rb
->flags
.clear_poly
)
1228 mtspace_add (rd
->mtspace
, &rb
->box
, FIXED
, rb
->style
->Keepaway
);
1233 /* free pointer lists */
1234 for (i
= 0; i
< max_layer
; i
++)
1235 FreePointerListMemory (&layergroupboxes
[i
]);
1241 DestroyRouteData (routedata_t
** rd
)
1244 for (i
= 0; i
< max_layer
; i
++)
1245 r_destroy_tree (&(*rd
)->layergrouptree
[i
]);
1246 if (AutoRouteParameters
.use_vias
)
1247 mtspace_destroy (&(*rd
)->mtspace
);
1252 /*-----------------------------------------------------------------
1253 * routebox reference counting.
1256 /* increment the reference count on a routebox. */
1258 RB_up_count (routebox_t
* rb
)
1260 assert (rb
->flags
.homeless
);
1264 /* decrement the reference count on a routebox, freeing if this box becomes
1267 RB_down_count (routebox_t
* rb
)
1269 assert (rb
->type
== EXPANSION_AREA
);
1270 assert (rb
->flags
.homeless
);
1271 assert (rb
->refcount
> 0);
1272 if (--rb
->refcount
== 0)
1274 if (rb
->parent
.expansion_area
->flags
.homeless
)
1275 RB_down_count (rb
->parent
.expansion_area
);
1280 /*-----------------------------------------------------------------
1281 * Rectangle-expansion routing code.
1285 ResetSubnet (routebox_t
* net
)
1288 /* reset connectivity of everything on this net */
1289 LIST_LOOP (net
, same_net
, rb
);
1290 rb
->same_subnet
= rb
->original_subnet
;
1294 static inline cost_t
1295 cost_to_point_on_layer (const CheapPointType
* p1
,
1296 const CheapPointType
* p2
, Cardinal point_layer
)
1298 cost_t x_dist
= p1
->X
- p2
->X
, y_dist
= p1
->Y
- p2
->Y
, r
;
1299 x_dist
*= x_cost
[point_layer
];
1300 y_dist
*= y_cost
[point_layer
];
1301 /* cost is proportional to orthogonal distance. */
1302 r
= ABS (x_dist
) + ABS (y_dist
);
1303 if (p1
->X
!= p2
->X
&& p1
->Y
!= p2
->Y
)
1304 r
+= AutoRouteParameters
.JogPenalty
;
1309 cost_to_point (const CheapPointType
* p1
, Cardinal point_layer1
,
1310 const CheapPointType
* p2
, Cardinal point_layer2
)
1312 cost_t r
= cost_to_point_on_layer (p1
, p2
, point_layer1
);
1313 /* apply via cost penalty if layers differ */
1314 if (point_layer1
!= point_layer2
)
1315 r
+= AutoRouteParameters
.ViaCost
;
1319 /* return the minimum *cost* from a point to a box on any layer.
1320 * It's safe to return a smaller than minimum cost
1323 cost_to_layerless_box (const CheapPointType
* p
, Cardinal point_layer
,
1326 CheapPointType p2
= closest_point_in_box (p
, b
);
1327 register cost_t c1
, c2
;
1335 return c1
* AutoRouteParameters
.MinPenalty
+ c2
;
1337 return c2
* AutoRouteParameters
.MinPenalty
+ c1
;
1340 /* get to actual pins/pad target coordinates */
1342 TargetPoint (CheapPointType
* nextpoint
, const routebox_t
* target
)
1344 if (target
->type
== PIN
)
1346 nextpoint
->X
= target
->parent
.pin
->X
;
1347 nextpoint
->Y
= target
->parent
.pin
->Y
;
1350 else if (target
->type
== PAD
)
1352 if (abs (target
->parent
.pad
->Point1
.X
- nextpoint
->X
) <
1353 abs (target
->parent
.pad
->Point2
.X
- nextpoint
->X
))
1354 nextpoint
->X
= target
->parent
.pad
->Point1
.X
;
1356 nextpoint
->X
= target
->parent
.pad
->Point2
.X
;
1357 if (abs (target
->parent
.pad
->Point1
.Y
- nextpoint
->Y
) <
1358 abs (target
->parent
.pad
->Point2
.Y
- nextpoint
->Y
))
1359 nextpoint
->Y
= target
->parent
.pad
->Point1
.Y
;
1361 nextpoint
->Y
= target
->parent
.pad
->Point2
.Y
;
1366 nextpoint
->X
= CENTER_X (target
->sbox
);
1367 nextpoint
->Y
= CENTER_Y (target
->sbox
);
1372 /* return the *minimum cost* from a point to a route box, including possible
1373 * via costs if the route box is on a different layer.
1374 * assume routbox is bloated unless it is an expansion area
1377 cost_to_routebox (const CheapPointType
* p
, Cardinal point_layer
,
1378 const routebox_t
* rb
)
1380 register cost_t trial
= 0;
1381 CheapPointType p2
= closest_point_in_routebox (p
, rb
);
1382 if (!usedGroup
[point_layer
] || !usedGroup
[rb
->group
])
1383 trial
= AutoRouteParameters
.NewLayerPenalty
;
1384 if ((p2
.X
- p
->X
) * (p2
.Y
- p
->Y
) != 0)
1385 trial
+= AutoRouteParameters
.JogPenalty
;
1386 /* special case for defered via searching */
1387 if (point_layer
> max_layer
|| point_layer
== rb
->group
)
1388 return trial
+ ABS (p2
.X
- p
->X
) + ABS (p2
.Y
- p
->Y
);
1389 /* if this target is only a via away, then the via is cheaper than the congestion */
1390 if (p
->X
== p2
.X
&& p
->Y
== p2
.Y
)
1392 trial
+= AutoRouteParameters
.ViaCost
;
1393 trial
+= ABS (p2
.X
- p
->X
) + ABS (p2
.Y
- p
->Y
);
1399 bloat_routebox (routebox_t
* rb
)
1402 LocationType keepaway
;
1403 assert (__routebox_is_good (rb
));
1405 if (rb
->flags
.nobloat
)
1408 /* Obstacle exclusion zones get bloated by the larger of
1409 * the two required clearances plus half the track width.
1411 keepaway
= MAX (AutoRouteParameters
.style
->Keepaway
, rb
->style
->Keepaway
);
1412 r
= bloat_box (&rb
->sbox
, keepaway
+
1413 HALF_THICK (AutoRouteParameters
.style
->Thick
));
1418 #ifdef ROUTE_DEBUG /* only for debugging expansion areas */
1421 fillbox (const BoxType
* b
)
1423 LayerTypePtr SLayer
= LAYER_PTR (0);
1424 gui
->set_color (Output
.fgGC
, SLayer
->Color
);
1425 gui
->fill_rect (Output
.fgGC
, b
->X1
, b
->Y1
, b
->X2
, b
->Y2
);
1428 /* makes a line on the solder layer silk surrounding the box */
1430 showbox (BoxType b
, Dimension thickness
, int group
)
1433 LayerTypePtr SLayer
= LAYER_PTR (group
);
1436 if (showboxen
!= -1 && showboxen
!= group
)
1440 gui
->set_line_width (Output
.fgGC
, thickness
);
1441 gui
->set_line_cap (Output
.fgGC
, Trace_Cap
);
1442 gui
->set_color (Output
.fgGC
, SLayer
->Color
);
1444 gui
->draw_line (Output
.fgGC
, b
.X1
, b
.Y1
, b
.X2
, b
.Y1
);
1445 gui
->draw_line (Output
.fgGC
, b
.X1
, b
.Y2
, b
.X2
, b
.Y2
);
1446 gui
->draw_line (Output
.fgGC
, b
.X1
, b
.Y1
, b
.X1
, b
.Y2
);
1447 gui
->draw_line (Output
.fgGC
, b
.X2
, b
.Y1
, b
.X2
, b
.Y2
);
1448 gui
->use_mask (HID_FLUSH_DRAW_Q
);
1451 if (b
.Y1
== b
.Y2
|| b
.X1
== b
.X2
)
1453 line
= CreateNewLineOnLayer (LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1454 b
.X1
, b
.Y1
, b
.X2
, b
.Y1
, thickness
, 0,
1456 AddObjectToCreateUndoList (LINE_TYPE
,
1457 LAYER_PTR (max_layer
+ COMPONENT_LAYER
), line
,
1461 line
= CreateNewLineOnLayer (LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1462 b
.X1
, b
.Y2
, b
.X2
, b
.Y2
, thickness
, 0,
1464 AddObjectToCreateUndoList (LINE_TYPE
,
1465 LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1468 line
= CreateNewLineOnLayer (LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1469 b
.X1
, b
.Y1
, b
.X1
, b
.Y2
, thickness
, 0,
1471 AddObjectToCreateUndoList (LINE_TYPE
,
1472 LAYER_PTR (max_layer
+ COMPONENT_LAYER
), line
,
1476 line
= CreateNewLineOnLayer (LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1477 b
.X2
, b
.Y1
, b
.X2
, b
.Y2
, thickness
, 0,
1479 AddObjectToCreateUndoList (LINE_TYPE
,
1480 LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1487 #if defined(ROUTE_DEBUG)
1489 showedge (edge_t
* e
)
1491 BoxType
*b
= (BoxType
*) e
->rb
;
1493 gui
->set_line_cap (Output
.fgGC
, Trace_Cap
);
1494 gui
->set_line_width (Output
.fgGC
, 1);
1495 gui
->set_color (Output
.fgGC
, Settings
.MaskColor
);
1497 switch (e
->expand_dir
)
1500 gui
->draw_line (Output
.fgGC
, b
->X1
, b
->Y1
, b
->X2
, b
->Y1
);
1503 gui
->draw_line (Output
.fgGC
, b
->X1
, b
->Y2
, b
->X2
, b
->Y2
);
1506 gui
->draw_line (Output
.fgGC
, b
->X1
, b
->Y1
, b
->X1
, b
->Y2
);
1509 gui
->draw_line (Output
.fgGC
, b
->X2
, b
->Y1
, b
->X2
, b
->Y2
);
1517 #if defined(ROUTE_DEBUG)
1519 showroutebox (routebox_t
* rb
)
1521 showbox (rb
->sbox
, rb
->flags
.source
? 20 : (rb
->flags
.target
? 10 : 1),
1522 rb
->flags
.is_via
? max_layer
+ COMPONENT_LAYER
: rb
->group
);
1527 EraseRouteBox (routebox_t
* rb
)
1529 LocationType X1
, Y1
, X2
, Y2
;
1532 if (rb
->box
.X2
- rb
->box
.X1
< rb
->box
.Y2
- rb
->box
.Y1
)
1534 thick
= rb
->box
.X2
- rb
->box
.X1
;
1535 X1
= X2
= (rb
->box
.X2
+ rb
->box
.X1
) / 2;
1536 Y1
= rb
->box
.Y1
+ thick
/ 2;
1537 Y2
= rb
->box
.Y2
- thick
/ 2;
1541 thick
= rb
->box
.Y2
- rb
->box
.Y1
;
1542 Y1
= Y2
= (rb
->box
.Y2
+ rb
->box
.Y1
) / 2;
1543 X1
= rb
->box
.X1
+ thick
/ 2;
1544 X2
= rb
->box
.X2
- thick
/ 2;
1547 gui
->set_line_width (ar_gc
, thick
);
1548 gui
->set_color (ar_gc
, Settings
.BackgroundColor
);
1549 gui
->draw_line (ar_gc
, X1
, Y1
, X2
, Y2
);
1552 /* return a "parent" of this edge which immediately precedes it in the route.*/
1554 route_parent (routebox_t
* rb
)
1556 while (rb
->flags
.homeless
&& !rb
->flags
.is_via
&& !rb
->flags
.is_thermal
)
1558 assert (rb
->type
== EXPANSION_AREA
);
1559 rb
= rb
->parent
.expansion_area
;
1566 path_conflicts (routebox_t
* rb
, routebox_t
* conflictor
, Boolean branch
)
1569 rb
->conflicts_with
= vector_duplicate (rb
->conflicts_with
);
1570 else if (!rb
->conflicts_with
)
1571 rb
->conflicts_with
= vector_create ();
1572 vector_append (rb
->conflicts_with
, conflictor
);
1573 return rb
->conflicts_with
;
1576 /* Touch everything (except fixed) on each net found
1577 * in the conflicts vector. If the vector is different
1578 * from the last one touched, untouch the last batch
1579 * and touch the new one. Always call with touch=1
1580 * (except for recursive call). Call with NULL, 1 to
1581 * clear the last batch touched.
1583 * touched items become invisible to current path
1584 * so we don't encounter the same conflictor more
1589 touch_conflicts (vector_t
* conflicts
, int touch
)
1591 static vector_t
*last
= NULL
;
1592 static int last_size
= 0;
1597 if (last
&& conflicts
!= last
)
1598 touch_conflicts (last
, 0);
1604 n
= vector_size (conflicts
);
1607 routebox_t
*rb
= (routebox_t
*) vector_element (conflicts
, i
);
1609 LIST_LOOP (rb
, same_net
, p
);
1610 if (!p
->flags
.fixed
)
1611 p
->flags
.touched
= touch
;
1623 /* return a "parent" of this edge which resides in a r-tree somewhere */
1624 /* -- actually, this "parent" *may* be a via box, which doesn't live in
1627 nonhomeless_parent (routebox_t
* rb
)
1629 return route_parent (rb
);
1632 /* some routines to find the minimum *cost* from a cost point to
1633 * a target (any target) */
1634 struct mincost_target_closure
1636 const CheapPointType
*CostPoint
;
1637 Cardinal CostPointLayer
;
1638 routebox_t
*nearest
;
1639 cost_t nearest_cost
;
1642 __region_within_guess (const BoxType
* region
, void *cl
)
1644 struct mincost_target_closure
*mtc
= (struct mincost_target_closure
*) cl
;
1645 cost_t cost_to_region
;
1646 if (mtc
->nearest
== NULL
)
1649 cost_to_layerless_box (mtc
->CostPoint
, mtc
->CostPointLayer
, region
);
1650 assert (cost_to_region
>= 0);
1651 /* if no guess yet, all regions are "close enough" */
1652 /* note that cost is *strictly more* than minimum distance, so we'll
1653 * always search a region large enough. */
1654 return (cost_to_region
< mtc
->nearest_cost
);
1657 __found_new_guess (const BoxType
* box
, void *cl
)
1659 struct mincost_target_closure
*mtc
= (struct mincost_target_closure
*) cl
;
1660 routebox_t
*guess
= (routebox_t
*) box
;
1661 cost_t cost_to_guess
=
1662 cost_to_routebox (mtc
->CostPoint
, mtc
->CostPointLayer
, guess
);
1663 assert (cost_to_guess
>= 0);
1664 /* if this is cheaper than previous guess... */
1665 if (cost_to_guess
< mtc
->nearest_cost
)
1667 mtc
->nearest
= guess
;
1668 mtc
->nearest_cost
= cost_to_guess
; /* this is our new guess! */
1672 return 0; /* not less expensive than our last guess */
1675 /* target_guess is our guess at what the nearest target is, or NULL if we
1676 * just plum don't have a clue. */
1678 mincost_target_to_point (const CheapPointType
* CostPoint
,
1679 Cardinal CostPointLayer
,
1680 rtree_t
* targets
, routebox_t
* target_guess
)
1682 struct mincost_target_closure mtc
;
1683 assert (target_guess
== NULL
|| target_guess
->flags
.target
); /* this is a target, right? */
1684 mtc
.CostPoint
= CostPoint
;
1685 mtc
.CostPointLayer
= CostPointLayer
;
1686 mtc
.nearest
= target_guess
;
1689 cost_to_routebox (mtc
.CostPoint
, mtc
.CostPointLayer
, mtc
.nearest
);
1691 mtc
.nearest_cost
= EXPENSIVE
;
1692 r_search (targets
, NULL
, __region_within_guess
, __found_new_guess
, &mtc
);
1693 assert (mtc
.nearest
!= NULL
&& mtc
.nearest_cost
>= 0);
1694 assert (mtc
.nearest
->flags
.target
); /* this is a target, right? */
1698 /* create edge from field values */
1699 /* mincost_target_guess can be NULL */
1701 CreateEdge (routebox_t
* rb
,
1702 LocationType CostPointX
, LocationType CostPointY
,
1703 cost_t cost_to_point
,
1704 routebox_t
* mincost_target_guess
,
1705 direction_t expand_dir
, rtree_t
* targets
)
1708 assert (__routebox_is_good (rb
));
1709 e
= malloc (sizeof (*e
));
1710 memset ((void *) e
, 0, sizeof (*e
));
1713 if (rb
->flags
.homeless
)
1715 e
->cost_point
.X
= CostPointX
;
1716 e
->cost_point
.Y
= CostPointY
;
1717 e
->cost_to_point
= cost_to_point
;
1718 e
->flags
.via_search
= 0;
1719 /* if this edge is created in response to a target, use it */
1722 mincost_target_to_point (&e
->cost_point
, rb
->group
,
1723 targets
, mincost_target_guess
);
1725 e
->mincost_target
= mincost_target_guess
;
1726 e
->expand_dir
= expand_dir
;
1727 assert (e
->rb
&& e
->mincost_target
); /* valid edge? */
1728 assert (!e
->flags
.is_via
|| e
->expand_dir
== ALL
);
1729 /* cost point should be on edge (unless this is a plane/via/conflict edge) */
1731 assert (rb
->type
== PLANE
|| rb
->conflicts_with
!= NULL
|| rb
->flags
.is_via
1732 || rb
->flags
.is_thermal
1733 || ((expand_dir
== NORTH
|| expand_dir
== SOUTH
) ? rb
->sbox
.X1
<=
1734 CostPointX
&& CostPointX
< rb
->sbox
.X2
1735 && CostPointY
== (expand_dir
==
1736 NORTH
? rb
->sbox
.Y1
: rb
->sbox
.Y2
- 1) :
1737 /* expand_dir==EAST || expand_dir==WEST */
1738 rb
->sbox
.Y1
<= CostPointY
&& CostPointY
< rb
->sbox
.Y2
&&
1739 CostPointX
== (expand_dir
==
1740 EAST
? rb
->sbox
.X2
- 1 : rb
->sbox
.X1
)));
1742 assert (__edge_is_good (e
));
1747 /* create edge, using previous edge to fill in defaults. */
1748 /* most of the work here is in determining a new cost point */
1750 CreateEdge2 (routebox_t
* rb
, direction_t expand_dir
,
1751 edge_t
* previous_edge
, rtree_t
* targets
, routebox_t
* guess
)
1754 CheapPointType thiscost
, prevcost
;
1757 assert (rb
&& previous_edge
);
1758 /* okay, find cheapest costpoint to costpoint of previous edge */
1759 thisbox
= edge_to_box (rb
, expand_dir
);
1760 prevcost
= previous_edge
->cost_point
;
1761 /* find point closest to target */
1762 thiscost
= closest_point_in_box (&prevcost
, &thisbox
);
1763 /* compute cost-to-point */
1764 d
= cost_to_point_on_layer (&prevcost
, &thiscost
, rb
->group
);
1765 /* add in jog penalty */
1766 if (previous_edge
->expand_dir
!= expand_dir
)
1767 d
+= AutoRouteParameters
.JogPenalty
;
1768 /* okay, new edge! */
1769 return CreateEdge (rb
, thiscost
.X
, thiscost
.Y
,
1770 previous_edge
->cost_to_point
+ d
,
1771 guess
? guess
: previous_edge
->mincost_target
,
1772 expand_dir
, targets
);
1775 /* create via edge, using previous edge to fill in defaults. */
1777 CreateViaEdge (const BoxType
* area
, Cardinal group
,
1778 routebox_t
* parent
, edge_t
* previous_edge
,
1779 conflict_t to_site_conflict
,
1780 conflict_t through_site_conflict
, rtree_t
* targets
)
1783 CheapPointType costpoint
;
1789 scale
[1] = AutoRouteParameters
.LastConflictPenalty
;
1790 scale
[2] = AutoRouteParameters
.ConflictPenalty
;
1792 assert (box_is_good (area
));
1793 assert (AutoRouteParameters
.with_conflicts
||
1794 (to_site_conflict
== NO_CONFLICT
&&
1795 through_site_conflict
== NO_CONFLICT
));
1796 rb
= CreateExpansionArea (area
, group
, parent
, True
, previous_edge
);
1797 rb
->flags
.is_via
= 1;
1798 rb
->came_from
= ALL
;
1799 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_VIA_BOXES)
1801 #endif /* ROUTE_DEBUG && DEBUG_SHOW_VIA_BOXES */
1802 /* for planes, choose a point near the target */
1803 if (previous_edge
->flags
.in_plane
)
1807 /* find a target near this via box */
1808 pnt
.X
= CENTER_X (*area
);
1809 pnt
.Y
= CENTER_Y (*area
);
1810 target
= mincost_target_to_point (&pnt
, rb
->group
,
1812 previous_edge
->mincost_target
);
1813 /* now find point near the target */
1814 pnt
.X
= CENTER_X (target
->box
);
1815 pnt
.Y
= CENTER_Y (target
->box
);
1816 costpoint
= closest_point_in_routebox (&pnt
, rb
);
1817 /* we moved from the previous cost point through the plane which is free travel */
1819 (scale
[through_site_conflict
] *
1820 cost_to_point (&costpoint
, group
, &costpoint
,
1821 previous_edge
->rb
->group
));
1823 CreateEdge (rb
, costpoint
.X
, costpoint
.Y
,
1824 previous_edge
->cost_to_point
+ d
, target
, ALL
, NULL
);
1825 ne
->mincost_target
= target
;
1830 target
= previous_edge
->mincost_target
;
1831 costpoint
= closest_point_in_routebox (&previous_edge
->cost_point
, rb
);
1833 (scale
[to_site_conflict
] *
1834 cost_to_point_on_layer (&costpoint
, &previous_edge
->cost_point
,
1835 previous_edge
->rb
->group
)) +
1836 (scale
[through_site_conflict
] *
1837 cost_to_point (&costpoint
, group
, &costpoint
,
1838 previous_edge
->rb
->group
));
1839 /* if the target is just this via away, then this via is cheaper */
1840 if (target
->group
== group
&&
1841 point_in_shrunk_box (target
, costpoint
.X
, costpoint
.Y
))
1842 d
-= AutoRouteParameters
.ViaCost
/ 2;
1844 CreateEdge (rb
, costpoint
.X
, costpoint
.Y
,
1845 previous_edge
->cost_to_point
+ d
,
1846 previous_edge
->mincost_target
, ALL
, targets
);
1848 ne
->flags
.is_via
= 1;
1849 ne
->flags
.via_conflict_level
= to_site_conflict
;
1850 assert (__edge_is_good (ne
));
1854 /* create "interior" edge for routing with conflicts */
1855 /* Presently once we "jump inside" the conflicting object
1856 * we consider it a routing highway to travel inside since
1857 * it will become available if the conflict is elliminated.
1858 * That is why we ignore the interior_edge argument.
1861 CreateEdgeWithConflicts (const BoxType
* interior_edge
,
1862 routebox_t
* container
, edge_t
* previous_edge
,
1863 cost_t cost_penalty_to_box
, rtree_t
* targets
)
1866 CheapPointType costpoint
;
1869 assert (interior_edge
&& container
&& previous_edge
&& targets
);
1870 assert (!container
->flags
.homeless
);
1871 assert (AutoRouteParameters
.with_conflicts
);
1872 assert (container
->flags
.touched
== 0);
1873 assert (previous_edge
->rb
->group
== container
->group
);
1874 /* use the caller's idea of what this box should be */
1876 CreateExpansionArea (interior_edge
, previous_edge
->rb
->group
,
1877 previous_edge
->rb
, True
, previous_edge
);
1878 path_conflicts (rb
, container
, True
); /* crucial! */
1880 closest_point_in_box (&previous_edge
->cost_point
, interior_edge
);
1882 cost_to_point_on_layer (&costpoint
, &previous_edge
->cost_point
,
1883 previous_edge
->rb
->group
);
1884 d
*= cost_penalty_to_box
;
1885 d
+= previous_edge
->cost_to_point
;
1886 ne
= CreateEdge (rb
, costpoint
.X
, costpoint
.Y
, d
, NULL
, ALL
, targets
);
1887 ne
->flags
.is_interior
= 1;
1888 assert (__edge_is_good (ne
));
1893 KillEdge (void *edge
)
1895 edge_t
*e
= (edge_t
*) edge
;
1897 if (e
->rb
->flags
.homeless
)
1898 RB_down_count (e
->rb
);
1899 if (e
->flags
.via_search
)
1900 mtsFreeWork (&e
->work
);
1905 DestroyEdge (edge_t
** e
)
1912 /* cost function for an edge. */
1914 edge_cost (const edge_t
* e
, const cost_t too_big
)
1916 cost_t penalty
= e
->cost_to_point
;
1917 if (e
->rb
->flags
.is_thermal
|| e
->rb
->type
== PLANE
)
1918 return penalty
; /* thermals are cheap */
1919 if (penalty
> too_big
)
1922 /* cost_to_routebox adds in our via correction, too. */
1924 cost_to_routebox (&e
->cost_point
, e
->rb
->group
, e
->mincost_target
);
1927 /* given an edge of a box, return a box containing exactly the points on that
1928 * edge. Note that the return box is treated as closed; that is, the bottom and
1929 * right "edges" consist of points (just barely) not in the (half-open) box. */
1931 edge_to_box (const routebox_t
* rb
, direction_t expand_dir
)
1933 BoxType b
= shrink_routebox (rb
);
1934 /* narrow box down to just the appropriate edge */
1958 BoxType left
, center
, right
;
1959 Boolean is_valid_left
, is_valid_center
, is_valid_right
;
1962 static struct broken_boxes
1963 break_box_edge (const BoxType
* original
, direction_t which_edge
,
1964 routebox_t
* breaker
)
1966 BoxType origbox
, breakbox
;
1967 struct broken_boxes result
;
1969 assert (original
&& breaker
);
1971 origbox
= *original
;
1972 breakbox
= bloat_routebox (breaker
);
1973 ROTATEBOX_TO_NORTH (origbox
, which_edge
);
1974 ROTATEBOX_TO_NORTH (breakbox
, which_edge
);
1975 result
.right
.Y1
= result
.center
.Y1
= result
.left
.Y1
= origbox
.Y1
;
1976 result
.right
.Y2
= result
.center
.Y2
= result
.left
.Y2
= origbox
.Y1
+ 1;
1977 /* validity of breaker is not important because the boxes are marked invalid */
1978 //assert (breakbox.X1 <= origbox.X2 && breakbox.X2 >= origbox.X1);
1979 /* left edge piece */
1980 result
.left
.X1
= origbox
.X1
;
1981 result
.left
.X2
= breakbox
.X1
;
1982 /* center (ie blocked) edge piece */
1983 result
.center
.X1
= MAX (breakbox
.X1
, origbox
.X1
);
1984 result
.center
.X2
= MIN (breakbox
.X2
, origbox
.X2
);
1985 /* right edge piece */
1986 result
.right
.X1
= breakbox
.X2
;
1987 result
.right
.X2
= origbox
.X2
;
1989 result
.is_valid_left
= (result
.left
.X1
< result
.left
.X2
);
1990 result
.is_valid_center
= (result
.center
.X1
< result
.center
.X2
);
1991 result
.is_valid_right
= (result
.right
.X1
< result
.right
.X2
);
1993 ROTATEBOX_FROM_NORTH (result
.left
, which_edge
);
1994 ROTATEBOX_FROM_NORTH (result
.center
, which_edge
);
1995 ROTATEBOX_FROM_NORTH (result
.right
, which_edge
);
2002 share_edge (const BoxType
* child
, const BoxType
* parent
)
2005 (child
->X1
== parent
->X2
|| child
->X2
== parent
->X1
||
2006 child
->Y1
== parent
->Y2
|| child
->Y2
== parent
->Y1
) &&
2007 ((parent
->X1
<= child
->X1
&& child
->X2
<= parent
->X2
) ||
2008 (parent
->Y1
<= child
->Y1
&& child
->Y2
<= parent
->Y2
));
2011 edge_intersect (const BoxType
* child
, const BoxType
* parent
)
2014 (child
->X1
<= parent
->X2
) && (child
->X2
>= parent
->X1
) &&
2015 (child
->Y1
<= parent
->Y2
) && (child
->Y2
>= parent
->Y1
);
2019 /* area is the expansion area, on layer group 'group'. 'parent' is the
2020 * immediately preceding expansion area, for backtracing. 'lastarea' is
2021 * the last expansion area created, we string these together in a loop
2022 * so we can remove them all easily at the end. */
2024 CreateExpansionArea (const BoxType
* area
, Cardinal group
,
2025 routebox_t
* parent
,
2026 Boolean relax_edge_requirements
, edge_t
* src_edge
)
2028 routebox_t
*rb
= (routebox_t
*) malloc (sizeof (*rb
));
2029 memset ((void *) rb
, 0, sizeof (*rb
));
2030 assert (area
&& parent
);
2031 init_const_box (rb
, area
->X1
, area
->Y1
, area
->X2
, area
->Y2
, 0);
2033 rb
->type
= EXPANSION_AREA
;
2034 /* should always share edge or overlap with parent */
2035 assert (relax_edge_requirements
? box_intersect (&rb
->sbox
, &parent
->sbox
)
2036 : share_edge (&rb
->sbox
, &parent
->sbox
));
2037 rb
->parent
.expansion_area
= route_parent (parent
);
2039 closest_point_in_box (&rb
->parent
.expansion_area
->cost_point
, area
);
2041 rb
->parent
.expansion_area
->cost
+
2042 cost_to_point_on_layer (&rb
->parent
.expansion_area
->cost_point
,
2043 &rb
->cost_point
, rb
->group
);
2044 assert (relax_edge_requirements
? edge_intersect (&rb
->sbox
, &parent
->sbox
)
2045 : share_edge (&rb
->sbox
, &parent
->sbox
));
2046 if (rb
->parent
.expansion_area
->flags
.homeless
)
2047 RB_up_count (rb
->parent
.expansion_area
);
2048 rb
->flags
.homeless
= 1;
2049 rb
->flags
.nobloat
= 1;
2050 rb
->style
= AutoRouteParameters
.style
;
2051 rb
->conflicts_with
= parent
->conflicts_with
;
2052 /* we will never link an EXPANSION_AREA into the nets because they
2053 * are *ONLY* used for path searching. No need to call InitLists ()
2055 rb
->came_from
= src_edge
->expand_dir
;
2056 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
2058 #endif /* ROUTE_DEBUG && DEBUG_SHOW_EXPANSION_BOXES */
2062 /*------ Expand ------*/
2066 routebox_t
*n
, *e
, *s
, *w
;
2067 BDimension keep
, bloat
;
2068 BoxType inflated
, orig
;
2072 /* test method for Expand()
2073 * this routebox potentially is a blocker limiting expansion
2074 * if this is so, we limit the inflate box so another exactly
2075 * like it wouldn't be seen. We do this while keep the inflated
2076 * box as large as possible.
2079 __Expand_this_rect (const BoxType
* box
, void *cl
)
2081 struct E_result
*res
= (struct E_result
*) cl
;
2082 routebox_t
*rb
= (routebox_t
*) box
;
2084 BDimension dn
, de
, ds
, dw
, bloat
;
2086 /* we don't see conflicts already encountered */
2087 if (rb
->flags
.touched
)
2090 /* The inflated box outer edges include its own
2091 * track width plus its own keepaway.
2093 * To check for intersection, we need to expand
2094 * anything with greater keepaway by its excess
2097 * If something has nobloat then we need to shrink
2098 * the inflated box back and see if it still touches.
2101 if (rb
->flags
.nobloat
)
2105 if (rbox
.X2
<= res
->inflated
.X1
+ bloat
||
2106 rbox
.X1
>= res
->inflated
.X2
- bloat
||
2107 rbox
.Y1
>= res
->inflated
.Y2
- bloat
||
2108 rbox
.Y2
<= res
->inflated
.Y1
+ bloat
)
2109 return 0; /* doesn't touch */
2113 if (rb
->style
->Keepaway
> res
->keep
)
2114 rbox
= bloat_box (&rb
->sbox
, rb
->style
->Keepaway
- res
->keep
);
2118 if (rbox
.X2
<= res
->inflated
.X1
|| rbox
.X1
>= res
->inflated
.X2
2119 || rbox
.Y1
>= res
->inflated
.Y2
|| rbox
.Y2
<= res
->inflated
.Y1
)
2120 return 0; /* doesn't touch */
2124 /* this is an intersecting box; it has to jump through a few more hoops */
2125 if (rb
== res
->parent
|| rb
->parent
.expansion_area
== res
->parent
)
2126 return 0; /* don't see what we came from */
2128 /* if we are expanding a source edge, don't let other sources
2129 * or their expansions stop us.
2132 if (res
->parent
->flags
.source
)
2133 if (rb
->flags
.source
2134 || (rb
->type
== EXPANSION_AREA
2135 && rb
->parent
.expansion_area
->flags
.source
))
2139 /* we ignore via expansion boxes because maybe its
2140 * cheaper to get there without the via through
2141 * the path we're exploring now.
2143 if (rb
->flags
.is_via
&& rb
->type
== EXPANSION_AREA
)
2146 if (rb
->type
== PLANE
) /* expanding inside a plane is not good */
2148 if (rbox
.X1
< res
->orig
.X1
&& rbox
.X2
> res
->orig
.X2
&&
2149 rbox
.Y1
< res
->orig
.Y1
&& rbox
.Y2
> res
->orig
.Y2
)
2151 res
->inflated
= bloat_box (&res
->orig
, res
->bloat
);
2155 /* calculate the distances from original box to this blocker */
2156 dn
= de
= ds
= dw
= 0;
2157 if (!(res
->done
& _NORTH
) && rbox
.Y1
<= res
->orig
.Y1
2158 && rbox
.Y2
> res
->inflated
.Y1
)
2159 dn
= res
->orig
.Y1
- rbox
.Y2
;
2160 if (!(res
->done
& _EAST
) && rbox
.X2
>= res
->orig
.X2
2161 && rbox
.X1
< res
->inflated
.X2
)
2162 de
= rbox
.X1
- res
->orig
.X2
;
2163 if (!(res
->done
& _SOUTH
) && rbox
.Y2
>= res
->orig
.Y2
2164 && rbox
.Y1
< res
->inflated
.Y2
)
2165 ds
= rbox
.Y1
- res
->orig
.Y2
;
2166 if (!(res
->done
& _WEST
) && rbox
.X1
<= res
->orig
.X1
2167 && rbox
.X2
> res
->inflated
.X1
)
2168 dw
= res
->orig
.X1
- rbox
.X2
;
2169 if (dn
<= 0 && de
<= 0 && ds
<= 0 && dw
<= 0)
2171 /* now shrink the inflated box to the largest blocking direction */
2172 if (dn
>= de
&& dn
>= ds
&& dn
>= dw
)
2174 res
->inflated
.Y1
= rbox
.Y2
- bloat
;
2177 else if (de
>= ds
&& de
>= dw
)
2179 res
->inflated
.X2
= rbox
.X1
+ bloat
;
2184 res
->inflated
.Y2
= rbox
.Y1
+ bloat
;
2189 res
->inflated
.X1
= rbox
.X2
- bloat
;
2196 boink_box (routebox_t
* rb
, struct E_result
*res
, direction_t dir
)
2199 if (rb
->style
->Keepaway
> res
->keep
)
2200 bloat
= res
->keep
- rb
->style
->Keepaway
;
2203 if (rb
->flags
.nobloat
)
2209 if (rb
->sbox
.X2
<= res
->inflated
.X1
+ bloat
2210 || rb
->sbox
.X1
>= res
->inflated
.X2
- bloat
)
2215 if (rb
->sbox
.Y1
>= res
->inflated
.Y2
- bloat
2216 || rb
->sbox
.Y2
<= res
->inflated
.Y1
+ bloat
)
2226 /* main Expand routine.
2228 * The expansion probe edge includes the keepaway and half thickness
2229 * as the search is performed in order to see everything relevant.
2230 * The result is backed off by this amount before being returned.
2231 * Targets (and other no-bloat routeboxes) go all the way to touching.
2232 * This is accomplished by backing off the probe edge when checking
2233 * for touch against such an object. Usually the expanding edge
2234 * bumps into neighboring pins on the same device that require a
2235 * keepaway, preventing seeing a target immediately. Rather than await
2236 * another expansion to actually touch the target, the edge breaker code
2237 * looks past the keepaway to see these targets even though they
2238 * weren't actually touched in the expansion.
2241 Expand (rtree_t
* rtree
, edge_t
* e
, const BoxType
* box
)
2243 static struct E_result ans
;
2244 int noshrink
; /* bit field of which edges to not shrink */
2246 ans
.bloat
= AutoRouteParameters
.bloat
;
2248 ans
.n
= ans
.e
= ans
.s
= ans
.w
= NULL
;
2250 /* the inflated box must be bloated in all directions that it might
2251 * hit something in order to guarantee that we see object in the
2252 * tree it might hit. The tree holds objects bloated by their own
2253 * keepaway so we are guaranteed to honor that.
2255 switch (e
->expand_dir
)
2258 ans
.inflated
.X1
= (e
->rb
->came_from
== EAST
? ans
.orig
.X1
: 0);
2259 ans
.inflated
.Y1
= (e
->rb
->came_from
== SOUTH
? ans
.orig
.Y1
: 0);
2261 (e
->rb
->came_from
== WEST
? ans
.orig
.X2
: PCB
->MaxWidth
);
2263 (e
->rb
->came_from
== NORTH
? ans
.orig
.Y2
: PCB
->MaxHeight
);
2264 if (e
->rb
->came_from
== NORTH
)
2265 ans
.done
= noshrink
= _SOUTH
;
2266 else if (e
->rb
->came_from
== EAST
)
2267 ans
.done
= noshrink
= _WEST
;
2268 else if (e
->rb
->came_from
== SOUTH
)
2269 ans
.done
= noshrink
= _NORTH
;
2270 else if (e
->rb
->came_from
== WEST
)
2271 ans
.done
= noshrink
= _EAST
;
2273 ans
.done
= noshrink
= 0;
2276 ans
.done
= _SOUTH
+ _EAST
+ _WEST
;
2278 ans
.inflated
.X1
= box
->X1
- ans
.bloat
;
2279 ans
.inflated
.X2
= box
->X2
+ ans
.bloat
;
2280 ans
.inflated
.Y2
= box
->Y2
;
2281 ans
.inflated
.Y1
= 0; /* far north */
2284 ans
.done
= _SOUTH
+ _WEST
;
2286 ans
.inflated
.X1
= box
->X1
- ans
.bloat
;
2287 ans
.inflated
.X2
= PCB
->MaxWidth
;
2288 ans
.inflated
.Y2
= box
->Y2
+ ans
.bloat
;
2289 ans
.inflated
.Y1
= 0;
2292 ans
.done
= _NORTH
+ _SOUTH
+ _WEST
;
2294 ans
.inflated
.Y1
= box
->Y1
- ans
.bloat
;
2295 ans
.inflated
.Y2
= box
->Y2
+ ans
.bloat
;
2296 ans
.inflated
.X1
= box
->X1
;
2297 ans
.inflated
.X2
= PCB
->MaxWidth
;
2300 ans
.done
= _NORTH
+ _WEST
;
2302 ans
.inflated
.X1
= box
->X1
- ans
.bloat
;
2303 ans
.inflated
.X2
= PCB
->MaxWidth
;
2304 ans
.inflated
.Y2
= PCB
->MaxHeight
;
2305 ans
.inflated
.Y1
= box
->Y1
- ans
.bloat
;
2308 ans
.done
= _NORTH
+ _EAST
+ _WEST
;
2310 ans
.inflated
.X1
= box
->X1
- ans
.bloat
;
2311 ans
.inflated
.X2
= box
->X2
+ ans
.bloat
;
2312 ans
.inflated
.Y1
= box
->Y1
;
2313 ans
.inflated
.Y2
= PCB
->MaxHeight
;
2316 ans
.done
= _NORTH
+ _EAST
;
2318 ans
.inflated
.X1
= 0;
2319 ans
.inflated
.X2
= box
->X2
+ ans
.bloat
;
2320 ans
.inflated
.Y2
= PCB
->MaxHeight
;
2321 ans
.inflated
.Y1
= box
->Y1
- ans
.bloat
;
2324 ans
.done
= _NORTH
+ _SOUTH
+ _EAST
;
2326 ans
.inflated
.Y1
= box
->Y1
- ans
.bloat
;
2327 ans
.inflated
.Y2
= box
->Y2
+ ans
.bloat
;
2328 ans
.inflated
.X1
= 0;
2329 ans
.inflated
.X2
= box
->X2
;
2332 ans
.done
= _SOUTH
+ _EAST
;
2334 ans
.inflated
.X1
= 0;
2335 ans
.inflated
.X2
= box
->X2
+ ans
.bloat
;
2336 ans
.inflated
.Y2
= box
->Y2
+ ans
.bloat
;
2337 ans
.inflated
.Y1
= 0;
2340 noshrink
= ans
.done
= 0;
2343 ans
.keep
= e
->rb
->style
->Keepaway
;
2344 ans
.parent
= nonhomeless_parent (e
->rb
);
2345 r_search (rtree
, &ans
.inflated
, NULL
, __Expand_this_rect
, &ans
);
2346 /* because the overlaping boxes are found in random order, some blockers
2347 * may have limited edges prematurely, so we check if the blockers realy
2348 * are blocking, and make another try if not
2350 if (ans
.n
&& !boink_box (ans
.n
, &ans
, NORTH
))
2351 ans
.inflated
.Y1
= 0;
2354 if (ans
.e
&& !boink_box (ans
.e
, &ans
, EAST
))
2355 ans
.inflated
.X2
= PCB
->MaxWidth
;
2358 if (ans
.s
&& !boink_box (ans
.s
, &ans
, SOUTH
))
2359 ans
.inflated
.Y2
= PCB
->MaxHeight
;
2362 if (ans
.w
&& !boink_box (ans
.w
, &ans
, WEST
))
2363 ans
.inflated
.X1
= 0;
2366 if (ans
.done
!= _NORTH
+ _EAST
+ _SOUTH
+ _WEST
)
2368 r_search (rtree
, &ans
.inflated
, NULL
, __Expand_this_rect
, &ans
);
2370 if ((noshrink
& _NORTH
) == 0)
2371 ans
.inflated
.Y1
+= ans
.bloat
;
2372 if ((noshrink
& _EAST
) == 0)
2373 ans
.inflated
.X2
-= ans
.bloat
;
2374 if ((noshrink
& _SOUTH
) == 0)
2375 ans
.inflated
.Y2
-= ans
.bloat
;
2376 if ((noshrink
& _WEST
) == 0)
2377 ans
.inflated
.X1
+= ans
.bloat
;
2381 /* blocker_to_heap puts the blockers into a heap so they
2382 * can be retrieved in clockwise order. If a blocker
2383 * is also a target, it gets put into the vector too.
2384 * It returns 1 for any fixed blocker that is not part
2385 * of this net and zero otherwise.
2388 blocker_to_heap (heap_t
* heap
, routebox_t
* rb
,
2389 BoxType
* box
, direction_t dir
)
2391 BoxType b
= rb
->sbox
;
2392 if (rb
->style
->Keepaway
> AutoRouteParameters
.style
->Keepaway
)
2395 rb
->style
->Keepaway
- AutoRouteParameters
.style
->Keepaway
);
2396 b
= clip_box (&b
, box
);
2397 assert (box_is_good (&b
));
2398 /* we want to look at the blockers clockwise around the box */
2401 /* we need to use the other coordinate fraction to resolve
2402 * ties since we want the shorter of the furthest
2406 heap_insert (heap
, b
.X1
- b
.X1
/ (b
.X2
+ 1.0), rb
);
2409 heap_insert (heap
, b
.Y1
- b
.Y1
/ (b
.Y2
+ 1.0), rb
);
2412 heap_insert (heap
, -(b
.X2
+ b
.X1
/ (b
.X2
+ 1.0)), rb
);
2415 heap_insert (heap
, -(b
.Y2
+ b
.Y1
/ (b
.Y2
+ 1.0)), rb
);
2420 if (rb
->flags
.fixed
&& !rb
->flags
.target
&& !rb
->flags
.source
)
2425 /* this creates an EXPANSION_AREA to bridge small gaps or,
2426 * (more commonly) create a supper-thin box to provide a
2427 * home for an expansion edge.
2430 CreateBridge (const BoxType
* area
, routebox_t
* parent
, direction_t dir
)
2432 routebox_t
*rb
= (routebox_t
*) malloc (sizeof (*rb
));
2433 memset ((void *) rb
, 0, sizeof (*rb
));
2434 assert (area
&& parent
);
2435 init_const_box (rb
, area
->X1
, area
->Y1
, area
->X2
, area
->Y2
, 0);
2436 rb
->group
= parent
->group
;
2437 rb
->type
= EXPANSION_AREA
;
2438 rb
->came_from
= dir
;
2439 rb
->cost_point
= closest_point_in_box (&parent
->cost_point
, area
);
2440 rb
->cost
= parent
->cost
+ cost_to_point_on_layer (&parent
->cost_point
,
2443 rb
->parent
.expansion_area
= route_parent (parent
);
2444 if (rb
->parent
.expansion_area
->flags
.homeless
)
2445 RB_up_count (rb
->parent
.expansion_area
);
2446 rb
->flags
.homeless
= 1;
2447 rb
->flags
.nobloat
= 1;
2448 rb
->style
= parent
->style
;
2449 rb
->conflicts_with
= parent
->conflicts_with
;
2450 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EDGES)
2456 /* moveable_edge prepares the new search edges based on the
2457 * starting box, direction and blocker if any.
2460 moveable_edge (vector_t
* result
, const BoxType
* box
, direction_t dir
,
2462 routebox_t
* blocker
, edge_t
* e
, rtree_t
* targets
,
2463 struct routeone_state
*s
, rtree_t
* tree
, vector_t
* area_vec
)
2466 assert (box_is_good (box
));
2468 /* for the cardinal directions, move the box to overlap the
2469 * the parent by 1 unit. Corner expansions overlap more
2470 * and their starting boxes are pre-prepared.
2471 * Check if anything is headed off the board edges
2480 if (b
.Y1
<= AutoRouteParameters
.bloat
)
2481 return; /* off board edge */
2486 if (b
.X2
>= PCB
->MaxWidth
- AutoRouteParameters
.bloat
)
2487 return; /* off board edge */
2492 if (b
.Y2
>= PCB
->MaxHeight
- AutoRouteParameters
.bloat
)
2493 return; /* off board edge */
2498 if (b
.X1
<= AutoRouteParameters
.bloat
)
2499 return; /* off board edge */
2502 if (b
.Y1
<= AutoRouteParameters
.bloat
+ 1
2503 && b
.X2
>= PCB
->MaxWidth
- AutoRouteParameters
.bloat
- 1)
2504 return; /* off board edge */
2505 if (b
.Y1
<= AutoRouteParameters
.bloat
+ 1)
2506 dir
= EAST
; /* north off board edge */
2507 if (b
.X2
>= PCB
->MaxWidth
- AutoRouteParameters
.bloat
- 1)
2508 dir
= NORTH
; /* east off board edge */
2511 if (b
.Y2
>= PCB
->MaxHeight
- AutoRouteParameters
.bloat
- 1
2512 && b
.X2
>= PCB
->MaxWidth
- AutoRouteParameters
.bloat
- 1)
2513 return; /* off board edge */
2514 if (b
.Y2
>= PCB
->MaxHeight
- AutoRouteParameters
.bloat
- 1)
2515 dir
= EAST
; /* south off board edge */
2516 if (b
.X2
>= PCB
->MaxWidth
- AutoRouteParameters
.bloat
- 1)
2517 dir
= SOUTH
; /* east off board edge */
2520 if (b
.Y2
>= PCB
->MaxHeight
- AutoRouteParameters
.bloat
- 1
2521 && b
.X1
<= AutoRouteParameters
.bloat
+ 1)
2522 return; /* off board edge */
2523 if (b
.Y2
>= PCB
->MaxHeight
- AutoRouteParameters
.bloat
- 1)
2524 dir
= WEST
; /* south off board edge */
2525 if (b
.X1
<= AutoRouteParameters
.bloat
+ 1)
2526 dir
= SOUTH
; /* west off board edge */
2529 if (b
.Y1
<= AutoRouteParameters
.bloat
+ 1
2530 && b
.X1
<= AutoRouteParameters
.bloat
+ 1)
2531 return; /* off board edge */
2532 if (b
.Y1
<= AutoRouteParameters
.bloat
+ 1)
2533 dir
= WEST
; /* north off board edge */
2534 if (b
.X1
<= AutoRouteParameters
.bloat
+ 1)
2535 dir
= NORTH
; /* west off board edge */
2542 routebox_t
*nrb
= CreateBridge (&b
, rb
, dir
);
2543 /* move the cost point in corner expansions
2544 * these boxes are bigger, so move close to the target
2546 if (dir
== NE
|| dir
== SE
|| dir
== SW
|| dir
== NW
)
2550 closest_point_in_box (&nrb
->cost_point
, &e
->mincost_target
->sbox
);
2551 p
= closest_point_in_box (&p
, &b
);
2552 nrb
->cost
+= cost_to_point_on_layer (&p
, &nrb
->cost_point
,
2554 nrb
->cost_point
= p
;
2556 ne
= CreateEdge (nrb
, nrb
->cost_point
.X
, nrb
->cost_point
.Y
,
2557 nrb
->cost
, NULL
, dir
, targets
);
2558 vector_append (result
, ne
);
2560 else if (AutoRouteParameters
.with_conflicts
&& !blocker
->flags
.target
2561 && !blocker
->flags
.fixed
&& !blocker
->flags
.touched
&&
2562 !blocker
->flags
.source
&& blocker
->type
!= EXPANSION_AREA
)
2566 /* make a bridge to the edge of the blocker
2567 * in all directions from there
2572 b
.Y1
= blocker
->sbox
.Y2
- 1;
2575 b
.X2
= blocker
->sbox
.X1
+ 1;
2578 b
.Y2
= blocker
->sbox
.Y1
+ 1;
2581 b
.X1
= blocker
->sbox
.X2
- 1;
2586 if (!box_is_good (&b
))
2587 return; /* how did this happen ? */
2588 nrb
= CreateBridge (&b
, rb
, dir
);
2589 r_insert_entry (tree
, &nrb
->box
, 1);
2590 vector_append (area_vec
, nrb
);
2591 nrb
->flags
.homeless
= 0; /* not homeless any more */
2592 /* mark this one as conflicted */
2593 path_conflicts (nrb
, blocker
, True
);
2594 /* and make an expansion edge */
2596 closest_point_in_box (&nrb
->cost_point
, &blocker
->sbox
);
2598 cost_to_point_on_layer (&nrb
->parent
.expansion_area
->cost_point
,
2600 nrb
->group
) * CONFLICT_PENALTY (blocker
);
2602 ne
= CreateEdge (nrb
, nrb
->cost_point
.X
, nrb
->cost_point
.Y
, nrb
->cost
,
2603 NULL
, ALL
, targets
);
2604 ne
->flags
.is_interior
= 1;
2605 vector_append (result
, ne
);
2608 else if (blocker
->type
== EXPANSION_AREA
)
2610 if (blocker
->cost
< rb
->cost
|| blocker
->cost
<= rb
->cost
+
2611 cost_to_point_on_layer (&blocker
->cost_point
, &rb
->cost_point
,
2614 if (blocker
->conflicts_with
|| rb
->conflicts_with
)
2616 /* does the blocker overlap this routebox ?? */
2617 /* does this re-parenting operation leave a memory leak? */
2618 if (blocker
->parent
.expansion_area
->flags
.homeless
)
2619 RB_down_count (blocker
->parent
.expansion_area
);
2620 blocker
->parent
.expansion_area
= rb
;
2624 else if (blocker
->flags
.target
)
2628 b
= bloat_box (&b
, 1);
2629 if (!box_intersect (&b
, &blocker
->sbox
))
2631 /* if the expansion edge stopped before touching, expand the bridge */
2635 b
.Y1
-= AutoRouteParameters
.bloat
+ 1;
2638 b
.X2
+= AutoRouteParameters
.bloat
+ 1;
2641 b
.Y2
+= AutoRouteParameters
.bloat
+ 1;
2644 b
.X1
-= AutoRouteParameters
.bloat
+ 1;
2650 assert (box_intersect (&b
, &blocker
->sbox
));
2651 b
= shrink_box (&b
, 1);
2652 nrb
= CreateBridge (&b
, rb
, dir
);
2653 r_insert_entry (tree
, &nrb
->box
, 1);
2654 vector_append (area_vec
, nrb
);
2655 nrb
->flags
.homeless
= 0; /* not homeless any more */
2656 ne
= CreateEdge (nrb
, nrb
->cost_point
.X
, nrb
->cost_point
.Y
,
2657 nrb
->cost
, blocker
, dir
, NULL
);
2658 best_path_candidate (s
, ne
, blocker
);
2669 Boolean ignore_source
;
2673 __GatherBlockers (const BoxType
* box
, void *cl
)
2675 routebox_t
*rb
= (routebox_t
*) box
;
2676 struct break_info
*bi
= (struct break_info
*) cl
;
2679 if (bi
->parent
== rb
|| rb
->flags
.touched
||
2680 bi
->parent
->parent
.expansion_area
== rb
)
2682 if (rb
->flags
.source
&& bi
->ignore_source
)
2685 if (rb
->style
->Keepaway
> AutoRouteParameters
.style
->Keepaway
)
2688 rb
->style
->Keepaway
- AutoRouteParameters
.style
->Keepaway
);
2689 if (b
.X2
<= bi
->box
.X1
|| b
.X1
>= bi
->box
.X2
2690 || b
.Y1
>= bi
->box
.Y2
|| b
.Y2
<= bi
->box
.Y1
)
2692 return blocker_to_heap (bi
->heap
, rb
, &bi
->box
, bi
->dir
);
2695 /* shrink the box to the last limit for the previous direction,
2696 * i.e. if dir is SOUTH, then this means fixing up an EAST leftover
2697 * edge, which would be the southern most edge for that example.
2699 static inline BoxType
2700 previous_edge (LocationType last
, direction_t i
, const BoxType
* b
)
2715 Message ("previous edge bogus direction!");
2721 /* Break all the edges of the box that need breaking, handling
2722 * targets as they are found, and putting any moveable edges
2723 * in the return vector.
2726 BreakManyEdges (struct routeone_state
* s
, rtree_t
* targets
, rtree_t
* tree
,
2727 vector_t
* area_vec
, struct E_result
* ans
, routebox_t
* rb
,
2730 struct break_info bi
;
2733 LocationType first
, last
;
2738 edges
= vector_create ();
2739 bi
.ignore_source
= rb
->parent
.expansion_area
->flags
.source
;
2741 /* we add 2 to the bloat.
2742 * 1 will get us to the actual blocker that Expand() hit
2743 * but 1 more is needed because the new expansion edges
2744 * move out by 1 so they don't overlap their parents
2745 * this extra expansion could "trap" the edge if
2746 * there is a blocker 2 units from the original rb,
2747 * it is 1 unit from the new expansion edge which
2748 * would prevent expansion. So we want to break the
2749 * edge on it now to avoid the trap.
2752 bloat
= AutoRouteParameters
.bloat
+ 2;
2753 /* for corner expansion, we need to have a fake blocker
2754 * to prevent expansion back where we came from since
2755 * we still need to break portions of all 4 edges
2757 if (e
->expand_dir
== NE
|| e
->expand_dir
== SE
||
2758 e
->expand_dir
== SW
|| e
->expand_dir
== NW
)
2760 BoxType
*fb
= (BoxType
*) & fake
.sbox
;
2761 memset (&fake
, 0, sizeof (fake
));
2763 fake
.flags
.fixed
= 1; /* this stops expansion there */
2765 fake
.style
= AutoRouteParameters
.style
;
2767 /* the routbox_is_good checker wants a lot more! */
2768 fake
.flags
.inited
= 1;
2769 fb
= (BoxType
*) & fake
.box
;
2771 fake
.same_net
.next
= fake
.same_net
.prev
= &fake
;
2772 fake
.same_subnet
.next
= fake
.same_subnet
.prev
= &fake
;
2773 fake
.original_subnet
.next
= fake
.original_subnet
.prev
= &fake
;
2774 fake
.different_net
.next
= fake
.different_net
.prev
= &fake
;
2777 /* gather all of the blockers in heaps so they can be accessed
2778 * in clockwise order, which allows finding corners that can
2781 for (dir
= NORTH
; dir
<= WEST
; dir
++)
2783 /* don't break the edge we came from */
2784 if (e
->expand_dir
!= ((dir
+ 2) % 4))
2786 heap
[dir
] = heap_create ();
2787 bi
.box
= bloat_box (&rb
->sbox
, bloat
);
2788 bi
.heap
= heap
[dir
];
2790 /* convert to edge */
2794 bi
.box
.Y2
= bi
.box
.Y1
+ bloat
+ 1;
2795 /* for corner expansion, block the start edges and
2796 * limit the blocker search to only the new edge segment
2798 if (e
->expand_dir
== SE
|| e
->expand_dir
== SW
)
2799 blocker_to_heap (heap
[dir
], &fake
, &bi
.box
, dir
);
2800 if (e
->expand_dir
== SE
)
2801 bi
.box
.X1
= e
->rb
->sbox
.X2
;
2802 if (e
->expand_dir
== SW
)
2803 bi
.box
.X2
= e
->rb
->sbox
.X1
;
2804 rb
->n
= r_search (tree
, &bi
.box
, NULL
, __GatherBlockers
, &bi
);
2807 bi
.box
.X1
= bi
.box
.X2
- bloat
- 1;
2808 /* corner, same as above */
2809 if (e
->expand_dir
== SW
|| e
->expand_dir
== NW
)
2810 blocker_to_heap (heap
[dir
], &fake
, &bi
.box
, dir
);
2811 if (e
->expand_dir
== SW
)
2812 bi
.box
.Y1
= e
->rb
->sbox
.Y2
;
2813 if (e
->expand_dir
== NW
)
2814 bi
.box
.Y2
= e
->rb
->sbox
.Y1
;
2815 rb
->e
= r_search (tree
, &bi
.box
, NULL
, __GatherBlockers
, &bi
);
2818 bi
.box
.Y1
= bi
.box
.Y2
- bloat
- 1;
2819 /* corner, same as above */
2820 if (e
->expand_dir
== NE
|| e
->expand_dir
== NW
)
2821 blocker_to_heap (heap
[dir
], &fake
, &bi
.box
, dir
);
2822 if (e
->expand_dir
== NE
)
2823 bi
.box
.X1
= e
->rb
->sbox
.X2
;
2824 if (e
->expand_dir
== NW
)
2825 bi
.box
.X2
= e
->rb
->sbox
.X1
;
2826 rb
->s
= r_search (tree
, &bi
.box
, NULL
, __GatherBlockers
, &bi
);
2829 bi
.box
.X2
= bi
.box
.X1
+ bloat
+ 1;
2830 /* corner, same as above */
2831 if (e
->expand_dir
== NE
|| e
->expand_dir
== SE
)
2832 blocker_to_heap (heap
[dir
], &fake
, &bi
.box
, dir
);
2833 if (e
->expand_dir
== SE
)
2834 bi
.box
.Y1
= e
->rb
->sbox
.Y2
;
2835 if (e
->expand_dir
== NE
)
2836 bi
.box
.Y2
= e
->rb
->sbox
.Y1
;
2837 rb
->w
= r_search (tree
, &bi
.box
, NULL
, __GatherBlockers
, &bi
);
2848 (rb
->n
+ rb
->e
+ rb
->s
+
2849 rb
->w
) * AutoRouteParameters
.CongestionPenalty
/ box_area (rb
->sbox
);
2851 /* now handle the blockers:
2852 * Go around the expansion area clockwise (North->East->South->West)
2853 * pulling blockers from the heap (which makes them come out in the right
2854 * order). Break the edges on the blocker and make the segments and corners
2855 * moveable as possible.
2858 for (dir
= NORTH
; dir
<= WEST
; dir
++)
2860 if (heap
[dir
] && !heap_is_empty (heap
[dir
]))
2862 /* pull the very first one out of the heap outside of the
2863 * heap loop because it is special; it can be part of a corner
2865 routebox_t
*blk
= (routebox_t
*) heap_remove_smallest (heap
[dir
]);
2866 BoxType b
= rb
->sbox
;
2867 struct broken_boxes broke
= break_box_edge (&b
, dir
, blk
);
2868 if (broke
.is_valid_left
)
2870 /* if last > 0, then the previous edge had a segment
2871 * joining this one, so it forms a valid corner expansion
2875 /* make a corner expansion */
2880 /* possible NE expansion */
2882 db
.Y2
= MIN (db
.Y2
, broke
.left
.Y2
);
2885 /* possible SE expansion */
2887 db
.X1
= MAX (db
.X1
, broke
.left
.X1
);
2890 /* possible SW expansion */
2892 db
.Y1
= MAX (db
.Y1
, broke
.left
.Y1
);
2898 moveable_edge (edges
, &db
, dir
+ 3, rb
, NULL
, e
, targets
,
2901 else if (dir
== NORTH
) /* north is start, so nothing "before" it */
2903 /* save for a possible corner once we've
2904 * finished circling the box
2906 first
= MAX (b
.X1
, broke
.left
.X2
);
2910 /* this is just a boring straight expansion
2911 * since the orthogonal segment was blocked
2913 moveable_edge (edges
, &broke
.left
, dir
, rb
, NULL
, e
,
2914 targets
, s
, NULL
, NULL
);
2916 } /* broke.is_valid_left */
2919 /* if the last one didn't become a corner,
2920 * we still want to expand it straight out
2921 * in the direction of the previous edge,
2922 * which it belongs to.
2924 BoxType db
= previous_edge (last
, dir
, &rb
->sbox
);
2925 moveable_edge (edges
, &db
, dir
- 1, rb
, NULL
, e
, targets
, s
,
2928 if (broke
.is_valid_center
&& !blk
->flags
.source
)
2929 moveable_edge (edges
, &broke
.center
, dir
, rb
, blk
, e
, targets
, s
,
2931 /* this is the heap extraction loop. We break out
2932 * if there's nothing left in the heap, but if we * are blocked all the way to the far edge, we can
2933 * just leave stuff in the heap when it is destroyed
2935 while (broke
.is_valid_right
)
2937 /* move the box edge to the next potential free point */
2941 last
= b
.X1
= MAX (broke
.right
.X1
, b
.X1
);
2944 last
= b
.Y1
= MAX (broke
.right
.Y1
, b
.Y1
);
2947 last
= b
.X2
= MIN (broke
.right
.X2
, b
.X2
);
2950 last
= b
.Y2
= MIN (broke
.right
.Y2
, b
.Y2
);
2955 if (heap_is_empty (heap
[dir
]))
2957 blk
= heap_remove_smallest (heap
[dir
]);
2958 broke
= break_box_edge (&b
, dir
, blk
);
2959 if (broke
.is_valid_left
)
2960 moveable_edge (edges
, &broke
.left
, dir
, rb
, NULL
, e
, targets
,
2962 if (broke
.is_valid_center
&& !blk
->flags
.source
)
2963 moveable_edge (edges
, &broke
.center
, dir
, rb
, blk
, e
, targets
,
2966 if (!broke
.is_valid_right
)
2969 else /* if (heap[dir]) */
2971 /* nothing touched this edge! Expand the whole edge unless
2972 * (1) it hit the board edge or (2) was the source of our expansion
2974 * for this case (of hitting nothing) we give up trying for corner
2975 * expansions because it is likely that they're not possible anyway
2977 if ((e
->expand_dir
== ALL
? e
->rb
->came_from
: e
->expand_dir
) !=
2980 /* ok, we are not going back on ourselves, and the whole edge seems free */
2981 moveable_edge (edges
, &rb
->sbox
, dir
, rb
, NULL
, e
, targets
, s
,
2987 /* expand the leftover from the prior direction */
2988 BoxType db
= previous_edge (last
, dir
, &rb
->sbox
);
2989 moveable_edge (edges
, &db
, dir
- 1, rb
, NULL
, e
, targets
, s
,
2995 /* finally, check for the NW corner now that we've come full circle */
2996 if (first
> 0 && last
> 0)
2998 BoxType db
= rb
->sbox
;
3001 moveable_edge (edges
, &db
, NW
, rb
, NULL
, e
, targets
, s
, NULL
, NULL
);
3007 BoxType db
= rb
->sbox
;
3009 moveable_edge (edges
, &db
, NORTH
, rb
, NULL
, e
, targets
, s
, NULL
,
3014 BoxType db
= rb
->sbox
;
3016 moveable_edge (edges
, &db
, WEST
, rb
, NULL
, e
, targets
, s
, NULL
,
3020 /* done with all expansion edges of this box */
3021 for (dir
= NORTH
; dir
<= WEST
; dir
++)
3024 heap_destroy (&heap
[dir
]);
3030 rb_source (routebox_t
* rb
)
3032 while (rb
&& !rb
->flags
.source
)
3034 assert (rb
->type
== EXPANSION_AREA
);
3035 rb
= rb
->parent
.expansion_area
;
3046 routebox_t
*intersect
;
3051 foib_rect_in_reg (const BoxType
* box
, void *cl
)
3053 struct foib_info
*foib
= (struct foib_info
*) cl
;
3055 routebox_t
*rb
= (routebox_t
*) box
;
3056 if (rb
->flags
.touched
)
3058 // if (rb->type == EXPANSION_AREA && !rb->flags.is_via)
3060 rbox
= bloat_routebox (rb
);
3061 if (!box_intersect (&rbox
, foib
->box
))
3063 /* this is an intersector! */
3064 foib
->intersect
= (routebox_t
*) box
;
3065 longjmp (foib
->env
, 1); /* skip to the end! */
3069 FindOneInBox (rtree_t
* rtree
, routebox_t
* rb
)
3071 struct foib_info foib
;
3076 foib
.intersect
= NULL
;
3078 if (setjmp (foib
.env
) == 0)
3079 r_search (rtree
, &r
, NULL
, foib_rect_in_reg
, &foib
);
3080 return foib
.intersect
;
3090 ftherm_rect_in_reg (const BoxType
* box
, void *cl
)
3092 routebox_t
*rbox
= (routebox_t
*) box
;
3093 struct therm_info
*ti
= (struct therm_info
*) cl
;
3096 if (rbox
->type
!= PIN
&& rbox
->type
!= VIA
&& rbox
->type
!= VIA_SHADOW
)
3098 if (rbox
->group
!= ti
->plane
->group
)
3101 sb
= shrink_routebox (rbox
);
3105 sq
= shrink_box (&ti
->query
, rbox
->parent
.pin
->Thickness
);
3106 if (!box_intersect (&sb
, &sq
))
3108 sb
.X1
= rbox
->parent
.pin
->X
;
3109 sb
.Y1
= rbox
->parent
.pin
->Y
;
3112 if (rbox
->flags
.fixed
)
3114 sq
= shrink_box (&ti
->query
, rbox
->parent
.via
->Thickness
);
3115 sb
.X1
= rbox
->parent
.pin
->X
;
3116 sb
.Y1
= rbox
->parent
.pin
->Y
;
3120 sq
= shrink_box (&ti
->query
, rbox
->style
->Diameter
);
3121 sb
.X1
= CENTER_X (sb
);
3122 sb
.Y1
= CENTER_Y (sb
);
3124 if (!box_intersect (&sb
, &sq
))
3128 sq
= shrink_box (&ti
->query
, rbox
->style
->Diameter
);
3129 if (!box_intersect (&sb
, &sq
))
3131 sb
.X1
= CENTER_X (sb
);
3132 sb
.Y1
= CENTER_Y (sb
);
3138 longjmp (ti
->env
, 1);
3142 /* check for a pin or via target that a polygon can just use a thermal to connect to */
3144 FindThermable (rtree_t
* rtree
, routebox_t
* rb
)
3146 struct therm_info info
;
3149 info
.query
= shrink_routebox (rb
);
3151 if (setjmp (info
.env
) == 0)
3153 r_search (rtree
, &info
.query
, NULL
, ftherm_rect_in_reg
, &info
);
3159 /*--------------------------------------------------------------------
3160 * Route-tracing code: once we've got a path of expansion boxes, trace
3161 * a line through them to actually create the connection.
3164 RD_DrawThermal (routedata_t
* rd
, LocationType X
, LocationType Y
,
3165 Cardinal group
, Cardinal layer
, routebox_t
* subnet
,
3169 rb
= (routebox_t
*) malloc (sizeof (*rb
));
3170 memset ((void *) rb
, 0, sizeof (*rb
));
3171 init_const_box (rb
, X
, Y
, X
+ 1, Y
+ 1, 0);
3174 rb
->flags
.fixed
= 0;
3175 rb
->flags
.is_bad
= is_bad
;
3176 rb
->flags
.is_odd
= AutoRouteParameters
.is_odd
;
3177 rb
->flags
.circular
= 0;
3178 rb
->style
= AutoRouteParameters
.style
;
3181 MergeNets (rb
, subnet
, NET
);
3182 MergeNets (rb
, subnet
, SUBNET
);
3183 /* add it to the r-tree, this may be the whole route! */
3184 r_insert_entry (rd
->layergrouptree
[rb
->group
], &rb
->box
, 1);
3185 rb
->flags
.homeless
= 0;
3189 RD_DrawVia (routedata_t
* rd
, LocationType X
, LocationType Y
,
3190 BDimension radius
, routebox_t
* subnet
, Boolean is_bad
)
3192 routebox_t
*rb
, *first_via
= NULL
;
3194 int ka
= AutoRouteParameters
.style
->Keepaway
;
3196 /* a via cuts through every layer group */
3197 for (i
= 0; i
< max_layer
; i
++)
3199 if (!is_layer_group_active
[i
])
3201 rb
= (routebox_t
*) malloc (sizeof (*rb
));
3202 memset ((void *) rb
, 0, sizeof (*rb
));
3204 /*X1 */ X
- radius
, /*Y1 */ Y
- radius
,
3205 /*X2 */ X
+ radius
+ 1, /*Y2 */ Y
+ radius
+ 1, ka
);
3207 rb
->flags
.fixed
= 0; /* indicates that not on PCB yet */
3208 rb
->flags
.is_odd
= AutoRouteParameters
.is_odd
;
3209 rb
->flags
.is_bad
= is_bad
;
3210 rb
->came_from
= ALL
;
3211 rb
->flags
.circular
= True
;
3212 rb
->style
= AutoRouteParameters
.style
;
3213 rb
->pass
= AutoRouteParameters
.pass
;
3214 if (first_via
== NULL
)
3217 rb
->parent
.via
= NULL
; /* indicates that not on PCB yet */
3219 /* only add the first via to mtspace, not the shadows too */
3220 mtspace_add (rd
->mtspace
, &rb
->box
, rb
->flags
.is_odd
? ODD
: EVEN
,
3221 rb
->style
->Keepaway
);
3225 rb
->type
= VIA_SHADOW
;
3226 rb
->parent
.via_shadow
= first_via
;
3229 /* add these to proper subnet. */
3230 MergeNets (rb
, subnet
, NET
);
3231 MergeNets (rb
, subnet
, SUBNET
);
3232 assert (__routebox_is_good (rb
));
3233 /* and add it to the r-tree! */
3234 r_insert_entry (rd
->layergrouptree
[rb
->group
], &rb
->box
, 1);
3235 rb
->flags
.homeless
= 0; /* not homeless anymore */
3237 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
3239 gui
->set_color (ar_gc
, PCB
->ViaColor
);
3240 gui
->fill_circle (ar_gc
, X
, Y
, radius
);
3245 RD_DrawLine (routedata_t
* rd
,
3246 LocationType X1
, LocationType Y1
, LocationType X2
,
3247 LocationType Y2
, BDimension halfthick
, Cardinal group
,
3248 routebox_t
* subnet
, Boolean is_bad
, Boolean is_45
)
3250 /* we hold the line in a queue to concatenate segments that
3251 * ajoin one another. That reduces the number of things in
3252 * the trees and allows conflict boxes to be larger, both of
3253 * which are really useful.
3255 static LocationType qX1
= -1, qY1
, qX2
, qY2
;
3256 static BDimension qhthick
;
3257 static Cardinal qgroup
;
3258 static Boolean qis_45
, qis_bad
;
3259 static routebox_t
*qsn
;
3262 int ka
= AutoRouteParameters
.style
->Keepaway
;
3264 /* don't draw zero-length segments. */
3265 if (X1
== X2
&& Y1
== Y2
)
3267 if (qX1
== -1) /* first ever */
3273 qhthick
= halfthick
;
3280 /* Check if the lines concatenat. We only check the
3281 * normal expected nextpoint=lastpoint condition
3283 if (X1
== qX2
&& Y1
== qY2
&& qhthick
== halfthick
&& qgroup
== group
)
3285 if (qX1
== qX2
&& X1
== X2
) /* everybody on the same X here */
3290 if (qY1
== qY2
&& Y1
== Y2
) /* same Y all around */
3296 /* dump the queue, no match here */
3298 return; /* but not this! */
3299 rb
= (routebox_t
*) malloc (sizeof (*rb
));
3300 memset ((void *) rb
, 0, sizeof (*rb
));
3301 assert (is_45
? (ABS (qX2
- qX1
) == ABS (qY2
- qY1
)) /* line must be 45-degrees */
3302 : (qX1
== qX2
|| qY1
== qY2
) /* line must be ortho */ );
3304 /*X1 */ MIN (qX1
, qX2
) - qhthick
,
3305 /*Y1 */ MIN (qY1
, qY2
) - qhthick
,
3306 /*X2 */ MAX (qX1
, qX2
) + qhthick
+ 1,
3307 /*Y2 */ MAX (qY1
, qY2
) + qhthick
+ 1, ka
);
3310 rb
->parent
.line
= NULL
; /* indicates that not on PCB yet */
3311 rb
->flags
.fixed
= 0; /* indicates that not on PCB yet */
3312 rb
->flags
.is_odd
= AutoRouteParameters
.is_odd
;
3313 rb
->flags
.is_bad
= qis_bad
;
3314 rb
->came_from
= ALL
;
3315 rb
->flags
.homeless
= 0; /* we're putting this in the tree */
3316 rb
->flags
.nonstraight
= qis_45
;
3317 rb
->flags
.bl_to_ur
= ((qX2
>= qX1
&& qY2
<= qY1
)
3318 || (qX2
<= qX1
&& qY2
>= qY1
));
3319 rb
->style
= AutoRouteParameters
.style
;
3320 rb
->pass
= AutoRouteParameters
.pass
;
3322 /* add these to proper subnet. */
3323 MergeNets (rb
, qsn
, NET
);
3324 MergeNets (rb
, qsn
, SUBNET
);
3325 assert (__routebox_is_good (rb
));
3326 /* and add it to the r-tree! */
3327 r_insert_entry (rd
->layergrouptree
[rb
->group
], &rb
->box
, 1);
3329 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
3331 LayerTypePtr layp
= LAYER_PTR (PCB
->LayerGroups
.Entries
[rb
->group
][0]);
3333 gui
->set_line_width (ar_gc
, 2 * qhthick
);
3334 gui
->set_color (ar_gc
, layp
->Color
);
3335 gui
->draw_line (ar_gc
, qX1
, qY1
, qX2
, qY2
);
3338 /* and to the via space structures */
3339 if (AutoRouteParameters
.use_vias
)
3340 mtspace_add (rd
->mtspace
, &rb
->box
, rb
->flags
.is_odd
? ODD
: EVEN
,
3341 rb
->style
->Keepaway
);
3342 usedGroup
[rb
->group
] = True
;
3343 /* and queue this one */
3348 qhthick
= halfthick
;
3356 RD_DrawManhattanLine (routedata_t
* rd
,
3357 const BoxType
* box1
, const BoxType
* box2
,
3358 CheapPointType start
, CheapPointType end
,
3359 BDimension halfthick
, Cardinal group
,
3360 routebox_t
* subnet
, Boolean is_bad
, Boolean last_was_x
)
3362 CheapPointType knee
= start
;
3363 if (end
.X
== start
.X
)
3365 RD_DrawLine (rd
, start
.X
, start
.Y
, end
.X
, end
.Y
, halfthick
, group
,
3366 subnet
, is_bad
, False
);
3369 else if (end
.Y
== start
.Y
)
3371 RD_DrawLine (rd
, start
.X
, start
.Y
, end
.X
, end
.Y
, halfthick
, group
,
3372 subnet
, is_bad
, False
);
3375 /* find where knee belongs */
3376 if (point_in_box (box1
, end
.X
, start
.Y
)
3377 || point_in_box (box2
, end
.X
, start
.Y
))
3387 if ((knee
.X
== end
.X
&& !last_was_x
) &&
3388 (point_in_box (box1
, start
.X
, end
.Y
)
3389 || point_in_box (box2
, start
.X
, end
.Y
)))
3394 assert (AutoRouteParameters
.is_smoothing
3395 || point_in_closed_box (box1
, knee
.X
, knee
.Y
)
3396 || point_in_closed_box (box2
, knee
.X
, knee
.Y
));
3398 if (1 || !AutoRouteParameters
.is_smoothing
)
3400 /* draw standard manhattan paths */
3401 RD_DrawLine (rd
, start
.X
, start
.Y
, knee
.X
, knee
.Y
, halfthick
, group
,
3402 subnet
, is_bad
, False
);
3403 RD_DrawLine (rd
, knee
.X
, knee
.Y
, end
.X
, end
.Y
, halfthick
, group
,
3404 subnet
, is_bad
, False
);
3408 /* draw 45-degree path across knee */
3409 BDimension len45
= MIN (ABS (start
.X
- end
.X
), ABS (start
.Y
- end
.Y
));
3410 CheapPointType kneestart
= knee
, kneeend
= knee
;
3411 if (kneestart
.X
== start
.X
)
3412 kneestart
.Y
+= (kneestart
.Y
> start
.Y
) ? -len45
: len45
;
3414 kneestart
.X
+= (kneestart
.X
> start
.X
) ? -len45
: len45
;
3415 if (kneeend
.X
== end
.X
)
3416 kneeend
.Y
+= (kneeend
.Y
> end
.Y
) ? -len45
: len45
;
3418 kneeend
.X
+= (kneeend
.X
> end
.X
) ? -len45
: len45
;
3419 RD_DrawLine (rd
, start
.X
, start
.Y
, kneestart
.X
, kneestart
.Y
, halfthick
,
3420 group
, subnet
, is_bad
, False
);
3421 RD_DrawLine (rd
, kneestart
.X
, kneestart
.Y
, kneeend
.X
, kneeend
.Y
,
3422 halfthick
, group
, subnet
, is_bad
, True
);
3423 RD_DrawLine (rd
, kneeend
.X
, kneeend
.Y
, end
.X
, end
.Y
, halfthick
, group
,
3424 subnet
, is_bad
, False
);
3426 return (knee
.X
!= end
.X
);
3429 /* for smoothing, don't pack traces to min clearance gratuitously */
3431 add_clearance (CheapPointType
* nextpoint
, const BoxType
* b
)
3433 if (nextpoint
->X
== b
->X1
)
3436 AutoRouteParameters
.style
->Keepaway
< (b
->X1
+ b
->X2
) / 2)
3437 nextpoint
->X
+= AutoRouteParameters
.style
->Keepaway
;
3439 nextpoint
->X
= (b
->X1
+ b
->X2
) / 2;
3441 else if (nextpoint
->X
== b
->X2
)
3444 AutoRouteParameters
.style
->Keepaway
> (b
->X1
+ b
->X2
) / 2)
3445 nextpoint
->X
-= AutoRouteParameters
.style
->Keepaway
;
3447 nextpoint
->X
= (b
->X1
+ b
->X2
) / 2;
3449 else if (nextpoint
->Y
== b
->Y1
)
3452 AutoRouteParameters
.style
->Keepaway
< (b
->Y1
+ b
->Y2
) / 2)
3453 nextpoint
->Y
+= AutoRouteParameters
.style
->Keepaway
;
3455 nextpoint
->Y
= (b
->Y1
+ b
->Y2
) / 2;
3457 else if (nextpoint
->Y
== b
->Y2
)
3460 AutoRouteParameters
.style
->Keepaway
> (b
->Y1
+ b
->Y2
) / 2)
3461 nextpoint
->Y
-= AutoRouteParameters
.style
->Keepaway
;
3463 nextpoint
->Y
= (b
->Y1
+ b
->Y2
) / 2;
3467 /* This back-traces the expansion boxes along the best path
3468 * it draws the lines that will make the actual path.
3469 * during refinement passes, it should try to maximize the area
3470 * for other tracks so routing completion is easier.
3472 * during smoothing passes, it should try to make a better path,
3473 * possibly using diagonals, etc. The path boxes are larger on
3474 * average now so there is more possiblity to decide on a nice
3475 * path. Any combination of lines and arcs is possible, so long
3476 * as they don't poke more than half thick outside the path box.
3480 TracePath (routedata_t
* rd
, routebox_t
* path
, const routebox_t
* target
,
3481 routebox_t
* subnet
, Boolean is_bad
)
3483 Boolean last_x
= False
;
3484 BDimension halfwidth
= HALF_THICK (AutoRouteParameters
.style
->Thick
);
3485 BDimension radius
= HALF_THICK (AutoRouteParameters
.style
->Diameter
);
3486 CheapPointType lastpoint
, nextpoint
;
3487 routebox_t
*lastpath
;
3490 assert (subnet
->style
== AutoRouteParameters
.style
);
3491 /*XXX: because we round up odd thicknesses, there's the possibility that
3492 * a connecting line end-point might be 0.005 mil off the "real" edge.
3493 * don't worry about this because line *thicknesses* are always >= 0.01 mil. */
3495 /* if we start with a thermal the target was a plane
3496 * or the target was a pin and the source a plane
3497 * in which case this thermal is the whole path
3499 if (path
->flags
.is_thermal
)
3501 /* the target was a plane, so we need to find a good spot for the via
3502 * now. It's logical to place it close to the source box which
3503 * is where we're utlimately headed on this path. However, it
3504 * must reside in the plane as well as the via area too.
3506 nextpoint
.X
= CENTER_X (path
->sbox
);
3507 nextpoint
.Y
= CENTER_Y (path
->sbox
);
3508 if (path
->parent
.expansion_area
->flags
.is_via
)
3510 TargetPoint (&nextpoint
, rb_source (path
));
3511 /* nextpoint is the middle of the source terminal now */
3512 b
= clip_box (&path
->sbox
, &path
->parent
.expansion_area
->sbox
);
3513 nextpoint
= closest_point_in_box (&nextpoint
, &b
);
3514 /* now it's in the via and plane near the source */
3516 else /* no via coming, target must have been a pin */
3518 assert (target
->type
== PIN
);
3519 TargetPoint (&nextpoint
, target
);
3521 assert (point_in_box (&path
->sbox
, nextpoint
.X
, nextpoint
.Y
));
3522 RD_DrawThermal (rd
, nextpoint
.X
, nextpoint
.Y
, path
->group
,
3523 path
->layer
, subnet
, is_bad
);
3527 /* start from best place of target box */
3528 lastpoint
.X
= CENTER_X (target
->sbox
);
3529 lastpoint
.Y
= CENTER_Y (target
->sbox
);
3530 TargetPoint (&lastpoint
, target
);
3531 if (AutoRouteParameters
.last_smooth
3532 && box_in_box (&path
->sbox
, &target
->sbox
))
3533 path
= path
->parent
.expansion_area
;
3535 if (path
->flags
.circular
)
3536 b
= shrink_box (&b
, MIN (b
.X2
- b
.X1
, b
.Y2
- b
.Y1
) / 5);
3537 nextpoint
= closest_point_in_box (&lastpoint
, &b
);
3538 if (AutoRouteParameters
.last_smooth
)
3539 RD_DrawLine (rd
, lastpoint
.X
, lastpoint
.Y
, nextpoint
.X
, nextpoint
.Y
,
3540 halfwidth
, path
->group
, subnet
, is_bad
, TRUE
);
3542 last_x
= RD_DrawManhattanLine (rd
, &target
->sbox
, &path
->sbox
,
3543 lastpoint
, nextpoint
, halfwidth
,
3544 path
->group
, subnet
, is_bad
, last_x
);
3546 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
3547 showroutebox (path
);
3548 #if defined(ROUTE_VERBOSE)
3549 printf ("TRACEPOINT start (%d, %d)\n", nextpoint
.X
, nextpoint
.Y
);
3555 lastpoint
= nextpoint
;
3557 assert (path
->type
== EXPANSION_AREA
);
3558 path
= path
->parent
.expansion_area
;
3560 if (path
->flags
.circular
)
3561 b
= shrink_box (&b
, MIN (b
.X2
- b
.X1
, b
.Y2
- b
.Y1
) / 5);
3562 assert (b
.X1
!= b
.X2
&& b
.Y1
!= b
.Y2
); /* need someplace to put line! */
3563 /* find point on path perimeter closest to last point */
3564 /* if source terminal, try to hit a good place */
3565 nextpoint
= closest_point_in_box (&lastpoint
, &b
);
3567 /* leave more clearance if this is a smoothing pass */
3568 if (AutoRouteParameters
.is_smoothing
&&
3569 (nextpoint
.X
!= lastpoint
.X
|| nextpoint
.Y
!= lastpoint
.Y
))
3570 add_clearance (&nextpoint
, &b
);
3572 if (path
->flags
.source
&& path
->type
!= PLANE
)
3573 TargetPoint (&nextpoint
, path
);
3574 assert (point_in_box (&lastpath
->box
, lastpoint
.X
, lastpoint
.Y
));
3575 assert (point_in_box (&path
->box
, nextpoint
.X
, nextpoint
.Y
));
3576 #if defined(ROUTE_DEBUG_VERBOSE)
3577 printf ("TRACEPATH: ");
3578 DumpRouteBox (path
);
3579 printf ("TRACEPATH: point (%d, %d) to point (%d, %d) layer %d\n",
3580 lastpoint
.X
, lastpoint
.Y
, nextpoint
.X
, nextpoint
.Y
,
3584 /* draw orthogonal lines from lastpoint to nextpoint */
3585 /* knee is placed in lastpath box */
3586 /* should never cause line to leave union of lastpath/path boxes */
3587 if (AutoRouteParameters
.last_smooth
)
3588 RD_DrawLine (rd
, lastpoint
.X
, lastpoint
.Y
, nextpoint
.X
, nextpoint
.Y
,
3589 halfwidth
, path
->group
, subnet
, is_bad
, TRUE
);
3591 last_x
= RD_DrawManhattanLine (rd
, &lastpath
->sbox
, &path
->sbox
,
3592 lastpoint
, nextpoint
, halfwidth
,
3593 path
->group
, subnet
, is_bad
, last_x
);
3594 if (path
->flags
.is_via
)
3595 { /* if via, then add via */
3596 #ifdef ROUTE_VERBOSE
3599 assert (point_in_box (&path
->box
, nextpoint
.X
, nextpoint
.Y
));
3600 RD_DrawVia (rd
, nextpoint
.X
, nextpoint
.Y
, radius
, subnet
, is_bad
);
3603 assert (lastpath
->flags
.is_via
|| path
->group
== lastpath
->group
);
3605 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
3606 showroutebox (path
);
3607 #endif /* ROUTE_DEBUG && DEBUG_SHOW_ROUTE_BOXES */
3608 /* if this is connected to a plane, draw the thermal */
3609 if (path
->flags
.is_thermal
|| path
->type
== PLANE
)
3610 RD_DrawThermal (rd
, lastpoint
.X
, lastpoint
.Y
, path
->group
,
3611 path
->layer
, subnet
, is_bad
);
3612 /* when one hop from the source, make an extra path in *this* box */
3613 if (path
->type
== EXPANSION_AREA
3614 && path
->parent
.expansion_area
->flags
.source
3615 && path
->parent
.expansion_area
->type
!= PLANE
)
3617 /* find special point on source (if it exists) */
3618 if (TargetPoint (&lastpoint
, path
->parent
.expansion_area
))
3620 lastpoint
= closest_point_in_routebox (&lastpoint
, path
);
3621 b
= shrink_routebox (path
);
3623 if (AutoRouteParameters
.is_smoothing
)
3624 add_clearance (&lastpoint
, &b
);
3626 if (AutoRouteParameters
.last_smooth
)
3627 RD_DrawLine (rd
, lastpoint
.X
, lastpoint
.Y
, nextpoint
.X
,
3628 nextpoint
.Y
, halfwidth
, path
->group
, subnet
,
3632 last_x
= RD_DrawManhattanLine (rd
, &b
, &b
,
3633 nextpoint
, lastpoint
,
3634 halfwidth
, path
->group
, subnet
,
3636 #if defined(ROUTE_DEBUG_VERBOSE)
3637 printf ("TRACEPATH: ");
3638 DumpRouteBox (path
);
3640 ("TRACEPATH: (to source) point (%d, %d) to point (%d, %d) layer %d\n",
3641 nextpoint
.X
, nextpoint
.Y
, lastpoint
.X
, lastpoint
.Y
,
3645 nextpoint
= lastpoint
;
3649 while (!path
->flags
.source
);
3650 /* flush the line queue */
3651 RD_DrawLine (rd
, -1, 0, 0, 0, 0, 0, NULL
, False
, False
);
3652 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
3653 gui
->use_mask (HID_FLUSH_DRAW_Q
);
3656 /* create a fake "edge" used to defer via site searching. */
3658 CreateSearchEdge (struct routeone_state
*s
, vetting_t
* work
, edge_t
* parent
,
3659 routebox_t
* rb
, conflict_t conflict
, rtree_t
* targets
,
3665 assert (__routebox_is_good (rb
));
3666 /* find the cheapest target */
3669 mincost_target_to_point (&parent
->cost_point
, max_layer
+ 1, targets
,
3670 parent
->mincost_target
);
3672 target
= parent
->mincost_target
;
3674 b
= shrink_routebox (target
);
3676 parent
->cost_to_point
+ AutoRouteParameters
.ViaCost
+
3677 cost_to_layerless_box (&rb
->cost_point
, 0, &b
);
3678 if (cost
< s
->best_cost
)
3681 ne
= malloc (sizeof (*ne
));
3682 memset ((void *) ne
, 0, sizeof (*ne
));
3684 ne
->flags
.via_search
= 1;
3685 ne
->flags
.in_plane
= in_plane
;
3687 if (rb
->flags
.homeless
)
3690 ne
->mincost_target
= target
;
3691 ne
->flags
.via_conflict_level
= conflict
;
3692 ne
->cost_to_point
= parent
->cost_to_point
;
3693 ne
->cost_point
= parent
->cost_point
;
3695 heap_insert (s
->workheap
, ne
->cost
, ne
);
3699 mtsFreeWork (&work
);
3704 add_or_destroy_edge (struct routeone_state
*s
, edge_t
* e
)
3706 e
->cost
= edge_cost (e
, s
->best_cost
);
3707 assert (__edge_is_good (e
));
3708 assert (is_layer_group_active
[e
->rb
->group
]);
3709 if (e
->cost
< s
->best_cost
)
3710 heap_insert (s
->workheap
, e
->cost
, e
);
3716 best_path_candidate (struct routeone_state
*s
,
3717 edge_t
* e
, routebox_t
* best_target
)
3719 e
->cost
= edge_cost (e
, EXPENSIVE
);
3720 if (s
->best_path
== NULL
|| e
->cost
< s
->best_cost
)
3722 #if defined(ROUTE_DEBUG) && defined (ROUTE_VERBOSE)
3723 printf ("New best path seen! cost = %f\n", e
->cost
);
3725 /* new best path! */
3726 if (s
->best_path
&& s
->best_path
->flags
.homeless
)
3727 RB_down_count (s
->best_path
);
3728 s
->best_path
= e
->rb
;
3729 s
->best_target
= best_target
;
3730 s
->best_cost
= e
->cost
;
3731 assert (s
->best_cost
>= 0);
3732 /* don't free this when we destroy edge! */
3733 if (s
->best_path
->flags
.homeless
)
3734 RB_up_count (s
->best_path
);
3739 /* vectors for via site candidates (see mtspace.h) */
3740 struct routeone_via_site_state
3742 vector_t
*free_space_vec
;
3743 vector_t
*lo_conflict_space_vec
;
3744 vector_t
*hi_conflict_space_vec
;
3748 add_via_sites (struct routeone_state
*s
,
3749 struct routeone_via_site_state
*vss
,
3750 mtspace_t
* mtspace
, routebox_t
* within
,
3751 conflict_t within_conflict_level
, edge_t
* parent_edge
,
3752 rtree_t
* targets
, BDimension shrink
, Boolean in_plane
)
3754 int radius
, keepaway
;
3756 BoxType region
= shrink_routebox (within
);
3757 shrink_box (®ion
, shrink
);
3759 radius
= HALF_THICK (AutoRouteParameters
.style
->Diameter
);
3760 keepaway
= AutoRouteParameters
.style
->Keepaway
;
3761 assert (AutoRouteParameters
.use_vias
);
3762 /* XXX: need to clip 'within' to shrunk_pcb_bounds, because when
3763 XXX: routing with conflicts may poke over edge. */
3765 /* ask for a via box near our cost_point first */
3766 work
= mtspace_query_rect (mtspace
, ®ion
, radius
, keepaway
,
3767 NULL
, vss
->free_space_vec
,
3768 vss
->lo_conflict_space_vec
,
3769 vss
->hi_conflict_space_vec
,
3770 AutoRouteParameters
.is_odd
,
3771 AutoRouteParameters
.with_conflicts
,
3772 &parent_edge
->cost_point
);
3775 CreateSearchEdge (s
, work
, parent_edge
, within
, within_conflict_level
,
3780 do_via_search (edge_t
* search
, struct routeone_state
*s
,
3781 struct routeone_via_site_state
*vss
, mtspace_t
* mtspace
,
3784 int i
, j
, count
= 0;
3785 int radius
, keepaway
;
3788 conflict_t within_conflict_level
;
3790 radius
= HALF_THICK (AutoRouteParameters
.style
->Diameter
);
3791 keepaway
= AutoRouteParameters
.style
->Keepaway
;
3792 work
= mtspace_query_rect (mtspace
, NULL
, 0, 0,
3793 search
->work
, vss
->free_space_vec
,
3794 vss
->lo_conflict_space_vec
,
3795 vss
->hi_conflict_space_vec
,
3796 AutoRouteParameters
.is_odd
,
3797 AutoRouteParameters
.with_conflicts
, NULL
);
3798 within
= search
->rb
;
3799 within_conflict_level
= search
->flags
.via_conflict_level
;
3800 for (i
= 0; i
< 3; i
++)
3803 (i
== NO_CONFLICT
? vss
->free_space_vec
:
3804 i
== LO_CONFLICT
? vss
->lo_conflict_space_vec
:
3805 i
== HI_CONFLICT
? vss
->hi_conflict_space_vec
: NULL
);
3807 while (!vector_is_empty (v
))
3810 BoxType
*area
= vector_remove_last (v
);
3811 if (!(i
== NO_CONFLICT
|| AutoRouteParameters
.with_conflicts
))
3816 /* answers are bloated by radius + keepaway */
3817 cliparea
= shrink_box (area
, radius
+ keepaway
);
3818 close_box (&cliparea
);
3820 assert (box_is_good (&cliparea
));
3822 for (j
= 0; j
< max_layer
; j
++)
3825 if (j
== within
->group
|| !is_layer_group_active
[j
])
3827 ne
= CreateViaEdge (&cliparea
, j
, within
, search
,
3828 within_conflict_level
, i
, targets
);
3829 add_or_destroy_edge (s
, ne
);
3833 /* prevent freeing of work when this edge is destroyed */
3834 search
->flags
.via_search
= 0;
3837 CreateSearchEdge (s
, work
, search
, within
, within_conflict_level
, targets
,
3838 search
->flags
.in_plane
);
3839 assert (vector_is_empty (vss
->free_space_vec
));
3840 assert (vector_is_empty (vss
->lo_conflict_space_vec
));
3841 assert (vector_is_empty (vss
->hi_conflict_space_vec
));
3844 /* vector of expansion areas to be eventually removed from r-tree
3845 * this is a global for troubleshooting
3849 /* some routines for use in gdb while debugging */
3850 #if defined(ROUTE_DEBUG)
3852 list_conflicts (routebox_t
* rb
)
3855 if (!rb
->conflicts_with
)
3857 n
= vector_size (rb
->conflicts_with
);
3858 for (i
= 0; i
< n
; i
++)
3859 printf ("%p, ", vector_element (rb
->conflicts_with
, i
));
3863 show_area_vec (int lay
)
3871 for (n
= 0; n
< vector_size (area_vec
); n
++)
3873 routebox_t
*rb
= (routebox_t
*) vector_element (area_vec
, n
);
3880 net_id (routebox_t
* rb
, long int id
)
3883 LIST_LOOP (rb
, same_net
, p
);
3884 if (p
->flags
.source
&& p
->parent
.pad
->ID
== id
)
3891 trace_parents (routebox_t
* rb
)
3893 while (rb
&& rb
->type
== EXPANSION_AREA
)
3895 printf (" %p ->", rb
);
3896 rb
= rb
->parent
.expansion_area
;
3899 printf (" %p is source\n", rb
);
3905 show_one (routebox_t
* rb
)
3907 int save
= showboxen
;
3914 show_path (routebox_t
* rb
)
3916 while (rb
&& rb
->type
== EXPANSION_AREA
)
3919 rb
= rb
->parent
.expansion_area
;
3925 show_sources (routebox_t
* rb
)
3928 if (!rb
->flags
.source
&& !rb
->flags
.target
)
3930 printf ("start with a source or target please\n");
3933 LIST_LOOP (rb
, same_net
, p
);
3934 if (p
->flags
.source
)
3940 __show_tree (const BoxType
* b
, void *cl
)
3943 routebox_t
*rb
= (routebox_t
*) b
;
3944 if (eo
< 0 || eo
== rb
->flags
.is_odd
)
3950 show_tree (rtree_t
* tree
, int even_odd
)
3952 r_search (tree
, NULL
, NULL
, __show_tree
, (void *) even_odd
);
3953 gui
->use_mask (HID_FLUSH_DRAW_Q
);
3959 __conflict_source (const BoxType
* box
, void *cl
)
3961 routebox_t
*rb
= (routebox_t
*) box
;
3962 if (rb
->flags
.touched
|| rb
->flags
.fixed
)
3966 routebox_t
*this = (routebox_t
*) cl
;
3967 path_conflicts (this, rb
, False
);
3968 touch_conflicts (this->conflicts_with
, 1);
3974 source_conflicts (rtree_t
* tree
, routebox_t
* rb
)
3976 if (!AutoRouteParameters
.with_conflicts
)
3978 r_search (tree
, &rb
->sbox
, NULL
, __conflict_source
, rb
);
3979 touch_conflicts (NULL
, 1);
3982 struct routeone_status
3984 Boolean found_route
;
3985 int route_had_conflicts
;
3986 cost_t best_route_cost
;
3987 Boolean net_completely_routed
;
3991 static struct routeone_status
3992 RouteOne (routedata_t
* rd
, routebox_t
* from
, routebox_t
* to
, int max_edges
)
3994 struct routeone_status result
;
3997 const BoxType
**target_list
;
4000 /* vector of source edges for filtering */
4001 vector_t
*source_vec
;
4002 /* working vector */
4005 struct routeone_state s
;
4006 struct routeone_via_site_state vss
;
4008 assert (rd
&& from
);
4009 result
.route_had_conflicts
= 0;
4010 /* no targets on to/from net need keepaway areas */
4011 LIST_LOOP (from
, same_net
, p
);
4012 p
->flags
.nobloat
= 1;
4014 /* set 'source' flags */
4015 LIST_LOOP (from
, same_subnet
, p
);
4016 if (!p
->flags
.nonstraight
)
4017 p
->flags
.source
= 1;
4020 /* count up the targets */
4023 /* remove source/target flags from non-straight obstacles, because they
4024 * don't fill their bounding boxes and so connecting to them
4025 * after we've routed is problematic. Better solution? */
4027 { /* if we're routing to a specific target */
4028 if (!to
->flags
.source
)
4029 { /* not already connected */
4030 /* check that 'to' and 'from' are on the same net */
4033 LIST_LOOP (from
, same_net
, p
);
4038 assert (seen
); /* otherwise from and to are on different nets! */
4039 /* set target flags only on 'to's subnet */
4040 LIST_LOOP (to
, same_subnet
, p
);
4041 if (!p
->flags
.nonstraight
&& is_layer_group_active
[p
->group
])
4043 p
->flags
.target
= 1;
4051 /* all nodes on the net but not connected to from are targets */
4052 LIST_LOOP (from
, same_net
, p
);
4053 if (!p
->flags
.source
&& is_layer_group_active
[p
->group
]
4054 && !p
->flags
.nonstraight
)
4056 p
->flags
.target
= 1;
4062 /* if no targets, then net is done! reset flags and return. */
4063 if (num_targets
== 0)
4065 LIST_LOOP (from
, same_net
, p
);
4066 p
->flags
.source
= p
->flags
.target
= p
->flags
.nobloat
= 0;
4068 result
.found_route
= False
;
4069 result
.net_completely_routed
= True
;
4070 result
.best_route_cost
= 0;
4071 result
.route_had_conflicts
= 0;
4075 result
.net_completely_routed
= False
;
4077 /* okay, there's stuff to route */
4078 assert (!from
->flags
.target
);
4079 assert (num_targets
> 0);
4080 /* create list of target pointers and from that a r-tree of targets */
4081 target_list
= malloc (num_targets
* sizeof (*target_list
));
4083 LIST_LOOP (from
, same_net
, p
);
4084 if (p
->flags
.target
)
4086 target_list
[i
++] = &p
->box
;
4087 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_TARGETS)
4092 targets
= r_create_tree (target_list
, i
, 0);
4093 assert (i
<= num_targets
);
4096 source_vec
= vector_create ();
4097 /* touch the source subnet to prepare check for conflictors */
4098 LIST_LOOP (from
, same_subnet
, p
);
4099 p
->flags
.touched
= 1;
4101 LIST_LOOP (from
, same_subnet
, p
);
4103 /* we need the test for 'source' because this box may be nonstraight */
4104 if (p
->flags
.source
&& is_layer_group_active
[p
->group
])
4108 BoxType b
= shrink_routebox (p
);
4110 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_SOURCES)
4113 /* may expand in all directions from source; center edge cost point. */
4114 /* note that planes shouldn't really expand, but we need an edge */
4116 cp
.X
= CENTER_X (b
);
4117 cp
.Y
= CENTER_Y (b
);
4118 e
= CreateEdge (p
, cp
.X
, cp
.Y
, 0, NULL
, ALL
, targets
);
4119 cp
= closest_point_in_box (&cp
, &e
->mincost_target
->sbox
);
4120 cp
= closest_point_in_box (&cp
, &b
);
4123 source_conflicts (rd
->layergrouptree
[p
->group
], p
);
4124 vector_append (source_vec
, e
);
4128 LIST_LOOP (from
, same_subnet
, p
);
4129 p
->flags
.touched
= 0;
4131 /* break source edges; some edges may be too near obstacles to be able
4134 /* okay, main expansion-search routing loop. */
4135 /* set up the initial activity heap */
4136 s
.workheap
= heap_create ();
4137 assert (s
.workheap
);
4138 while (!vector_is_empty (source_vec
))
4140 edge_t
*e
= vector_remove_last (source_vec
);
4141 assert (is_layer_group_active
[e
->rb
->group
]);
4142 e
->cost
= edge_cost (e
, EXPENSIVE
);
4143 heap_insert (s
.workheap
, e
->cost
, e
);
4145 vector_destroy (&source_vec
);
4146 /* okay, process items from heap until it is empty! */
4148 s
.best_cost
= EXPENSIVE
;
4149 area_vec
= vector_create ();
4150 edge_vec
= vector_create ();
4151 vss
.free_space_vec
= vector_create ();
4152 vss
.lo_conflict_space_vec
= vector_create ();
4153 vss
.hi_conflict_space_vec
= vector_create ();
4154 while (!heap_is_empty (s
.workheap
))
4156 edge_t
*e
= heap_remove_smallest (s
.workheap
);
4161 /* don't bother expanding this edge if the minimum possible edge cost
4162 * is already larger than the best edge cost we've found. */
4163 if (s
.best_path
&& e
->cost
>= s
.best_cost
)
4165 heap_free (s
.workheap
, KillEdge
);
4166 goto dontexpand
; /* skip this edge */
4168 /* surprisingly it helps to give up and not try too hard to find
4169 * a route! This is not only faster, but results in better routing.
4170 * who would have guessed?
4172 if (seen
++ > max_edges
)
4174 assert (__edge_is_good (e
));
4175 /* mark or unmark conflictors as needed */
4176 touch_conflicts (e
->rb
->conflicts_with
, 1);
4177 if (e
->flags
.via_search
)
4179 do_via_search (e
, &s
, &vss
, rd
->mtspace
, targets
);
4182 /* we should never add edges on inactive layer groups to the heap. */
4183 assert (is_layer_group_active
[e
->rb
->group
]);
4184 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
4187 if (e
->rb
->flags
.is_thermal
)
4189 best_path_candidate (&s
, e
, e
->mincost_target
);
4192 /* for a plane, look for quick connections with thermals or vias */
4193 if (e
->rb
->type
== PLANE
)
4195 routebox_t
*pin
= FindThermable (targets
, e
->rb
);
4198 BoxType b
= shrink_routebox (pin
);
4201 assert (pin
->flags
.target
);
4202 nrb
= CreateExpansionArea (&b
, e
->rb
->group
, e
->rb
, True
, e
);
4203 nrb
->flags
.is_thermal
= 1;
4204 /* moving through the plane is free */
4205 e
->cost_point
.X
= b
.X1
;
4206 e
->cost_point
.Y
= b
.Y1
;
4207 ne
= CreateEdge2 (nrb
, e
->expand_dir
, e
, NULL
, pin
);
4208 best_path_candidate (&s
, ne
, pin
);
4213 /* add in possible via sites in plane */
4214 if (AutoRouteParameters
.use_vias
&&
4215 e
->cost
+ AutoRouteParameters
.ViaCost
< s
.best_cost
)
4217 /* we need a giant thermal */
4219 CreateExpansionArea (&e
->rb
->sbox
, e
->rb
->group
, e
->rb
,
4221 edge_t
*ne
= CreateEdge2 (nrb
, e
->expand_dir
, e
, NULL
,
4223 nrb
->flags
.is_thermal
= 1;
4224 add_via_sites (&s
, &vss
, rd
->mtspace
, nrb
, NO_CONFLICT
, ne
,
4225 targets
, e
->rb
->style
->Diameter
, True
);
4228 goto dontexpand
; /* planes only connect via thermals */
4230 if (e
->flags
.is_via
)
4231 { /* special case via */
4232 routebox_t
*intersecting
;
4233 assert (AutoRouteParameters
.use_vias
);
4234 assert (e
->expand_dir
== ALL
);
4235 assert (vector_is_empty (edge_vec
));
4236 /* if there is already something here on this layer (like an
4237 * EXPANSION_AREA), then we don't want to expand from here
4238 * at least not inside the expansion area. A PLANE on the
4239 * other hand may be a target, or not.
4242 FindOneInBox (rd
->layergrouptree
[e
->rb
->group
], e
->rb
);
4244 if (intersecting
&& intersecting
->flags
.target
4245 && intersecting
->type
== PLANE
)
4247 /* we have hit a plane */
4250 BoxType b
= shrink_routebox (e
->rb
);
4251 /* limit via region to that inside the plane */
4252 clip_box (&b
, &intersecting
->sbox
);
4253 nrb
= CreateExpansionArea (&b
, e
->rb
->group
, e
->rb
, True
, e
);
4254 nrb
->flags
.is_thermal
= 1;
4255 ne
= CreateEdge2 (nrb
, e
->expand_dir
, e
, NULL
, intersecting
);
4256 best_path_candidate (&s
, ne
, intersecting
);
4260 else if (intersecting
== NULL
)
4262 /* this via candidate is in an open area; add it to r-tree as
4263 * an expansion area */
4264 assert (e
->rb
->type
== EXPANSION_AREA
&& e
->rb
->flags
.is_via
);
4265 /*assert (!r_search (rd->layergrouptree[e->rb->group],
4266 &e->rb->box, NULL, no_planes,0));
4268 r_insert_entry (rd
->layergrouptree
[e
->rb
->group
], &e
->rb
->box
,
4270 e
->rb
->flags
.homeless
= 0; /* not homeless any more */
4271 /* add to vector of all expansion areas in r-tree */
4272 vector_append (area_vec
, e
->rb
);
4273 /* mark reset refcount to 0, since this is not homeless any more. */
4274 e
->rb
->refcount
= 0;
4275 /* go ahead and expand this edge! */
4280 { /* XXX: disabling this causes no via
4282 BoxType a
= bloat_routebox (intersecting
), b
;
4285 /* something intersects this via candidate. split via candidate
4286 * into pieces and add these pieces to the workheap. */
4287 for (i
= 0; i
< 3; i
++)
4289 for (j
= 0; j
< 3; j
++)
4291 b
= shrink_routebox (e
->rb
);
4295 b
.X2
= MIN (b
.X2
, a
.X1
);
4298 b
.X1
= MAX (b
.X1
, a
.X1
);
4299 b
.X2
= MIN (b
.X2
, a
.X2
);
4302 b
.X1
= MAX (b
.X1
, a
.X2
);
4310 b
.Y2
= MIN (b
.Y2
, a
.Y1
);
4313 b
.Y1
= MAX (b
.Y1
, a
.Y1
);
4314 b
.Y2
= MIN (b
.Y2
, a
.Y2
);
4317 b
.Y1
= MAX (b
.Y1
, a
.Y2
);
4322 /* skip if this box is not valid */
4323 if (!(b
.X1
< b
.X2
&& b
.Y1
< b
.Y2
))
4325 if (i
== 1 && j
== 1)
4327 /* this bit of the via space is obstructed. */
4328 if (intersecting
->type
== EXPANSION_AREA
4329 || intersecting
->flags
.fixed
)
4330 continue; /* skip this bit, it's already been done. */
4331 /* create an edge with conflicts, if enabled */
4332 if (!AutoRouteParameters
.with_conflicts
)
4334 ne
= CreateEdgeWithConflicts (&b
, intersecting
, e
, 1
4335 /*cost penalty to box */
4337 add_or_destroy_edge (&s
, ne
);
4341 /* if this is not the intersecting piece, create a new
4342 * (hopefully unobstructed) via edge and add it back to the
4345 CreateViaEdge (&b
, e
->rb
->group
,
4346 e
->rb
->parent
.expansion_area
, e
,
4347 e
->flags
.via_conflict_level
,
4349 /* value here doesn't matter */
4351 add_or_destroy_edge (&s
, ne
);
4357 /* between the time these edges are inserted and the
4358 * time they are processed, new expansion boxes (which
4359 * conflict with these edges) may be added to the graph!
4360 * w.o vias this isn't a problem because the broken box
4361 * is not homeless. */
4366 struct E_result
*ans
;
4369 if (e
->flags
.is_interior
)
4371 assert (AutoRouteParameters
.with_conflicts
); /* no interior edges unless
4372 routing with conflicts! */
4373 assert (e
->rb
->conflicts_with
);
4375 switch (e
->rb
->came_from
)
4379 b
.X1
= CENTER_X (b
);
4384 b
.Y1
= CENTER_Y (b
);
4389 b
.X1
= CENTER_X (b
);
4394 b
.Y1
= CENTER_Y (b
);
4401 /* sources may not expand to their own edges because of
4402 * adjacent blockers.
4404 else if (e
->rb
->flags
.source
)
4405 b
= box_center (&e
->rb
->sbox
);
4408 ans
= Expand (rd
->layergrouptree
[e
->rb
->group
], e
, &b
);
4409 if (!box_intersect (&ans
->inflated
, &ans
->orig
))
4412 /* skip if it didn't actually expand */
4413 if (ans
->inflated
.X1
>= e
->rb
->sbox
.X1
&&
4414 ans
->inflated
.X2
<= e
->rb
->sbox
.X2
&&
4415 ans
->inflated
.Y1
>= e
->rb
->sbox
.Y1
&&
4416 ans
->inflated
.Y2
<= e
->rb
->sbox
.Y2
)
4420 if (!box_is_good (&ans
->inflated
))
4422 nrb
= CreateExpansionArea (&ans
->inflated
, e
->rb
->group
, e
->rb
,
4424 r_insert_entry (rd
->layergrouptree
[nrb
->group
], &nrb
->box
, 1);
4425 vector_append (area_vec
, nrb
);
4426 nrb
->flags
.homeless
= 0; /* not homeless any more */
4428 BreakManyEdges (&s
, targets
, rd
->layergrouptree
[nrb
->group
],
4429 area_vec
, ans
, nrb
, e
);
4430 while (!vector_is_empty (broken
))
4432 edge_t
*ne
= vector_remove_last (broken
);
4433 add_or_destroy_edge (&s
, ne
);
4435 vector_destroy (&broken
);
4437 /* add in possible via sites in nrb */
4438 if (AutoRouteParameters
.use_vias
&& !e
->rb
->flags
.is_via
&&
4439 e
->cost
+ AutoRouteParameters
.ViaCost
< s
.best_cost
)
4440 add_via_sites (&s
, &vss
,
4441 rd
->mtspace
, nrb
, NO_CONFLICT
, e
, targets
, 0,
4448 touch_conflicts (NULL
, 1);
4449 heap_destroy (&s
.workheap
);
4450 r_destroy_tree (&targets
);
4451 assert (vector_is_empty (edge_vec
));
4452 vector_destroy (&edge_vec
);
4454 /* we should have a path in best_path now */
4458 #ifdef ROUTE_VERBOSE
4459 printf ("%d:%d RC %.0f", ro
++, seen
, s
.best_cost
);
4461 result
.found_route
= True
;
4462 result
.best_route_cost
= s
.best_cost
;
4463 /* determine if the best path had conflicts */
4464 result
.route_had_conflicts
= 0;
4465 if (AutoRouteParameters
.with_conflicts
&& s
.best_path
->conflicts_with
)
4467 while (!vector_is_empty (s
.best_path
->conflicts_with
))
4469 rb
= vector_remove_last (s
.best_path
->conflicts_with
);
4470 rb
->flags
.is_bad
= 1;
4471 result
.route_had_conflicts
++;
4474 #ifdef ROUTE_VERBOSE
4475 if (result
.route_had_conflicts
)
4476 printf (" (%d conflicts)", result
.route_had_conflicts
);
4478 if (result
.route_had_conflicts
< AutoRouteParameters
.hi_conflict
)
4480 /* back-trace the path and add lines/vias to r-tree */
4481 TracePath (rd
, s
.best_path
, s
.best_target
, from
,
4482 result
.route_had_conflicts
);
4483 MergeNets (from
, s
.best_target
, SUBNET
);
4487 #ifdef ROUTE_VERBOSE
4488 printf (" (too many in fact)");
4490 result
.found_route
= False
;
4492 #ifdef ROUTE_VERBOSE
4498 #ifdef ROUTE_VERBOSE
4499 printf ("%d:%d NO PATH FOUND.\n", ro
++, seen
);
4501 result
.best_route_cost
= s
.best_cost
;
4502 result
.found_route
= False
;
4504 /* now remove all expansion areas from the r-tree. */
4505 while (!vector_is_empty (area_vec
))
4507 routebox_t
*rb
= vector_remove_last (area_vec
);
4508 assert (!rb
->flags
.homeless
);
4509 if (rb
->conflicts_with
4510 && rb
->parent
.expansion_area
->conflicts_with
!= rb
->conflicts_with
)
4511 vector_destroy (&rb
->conflicts_with
);
4512 r_delete_entry (rd
->layergrouptree
[rb
->group
], &rb
->box
);
4514 vector_destroy (&area_vec
);
4515 /* clean up; remove all 'source', 'target', and 'nobloat' flags */
4516 LIST_LOOP (from
, same_net
, p
);
4517 if (p
->flags
.source
&& p
->conflicts_with
)
4518 vector_destroy (&p
->conflicts_with
);
4519 p
->flags
.touched
= p
->flags
.source
= p
->flags
.target
= p
->flags
.nobloat
= 0;
4522 vector_destroy (&vss
.free_space_vec
);
4523 vector_destroy (&vss
.lo_conflict_space_vec
);
4524 vector_destroy (&vss
.hi_conflict_space_vec
);
4530 InitAutoRouteParameters (int pass
,
4531 RouteStyleType
* style
,
4532 Boolean with_conflicts
, Boolean is_smoothing
,
4537 AutoRouteParameters
.style
= style
;
4538 AutoRouteParameters
.bloat
= style
->Keepaway
+ HALF_THICK (style
->Thick
);
4540 AutoRouteParameters
.ViaCost
=
4541 350000 + style
->Diameter
* (is_smoothing
? 80 : 30);
4542 AutoRouteParameters
.LastConflictPenalty
=
4543 (400 * pass
/ passes
+ 2) / (pass
+ 1);
4544 AutoRouteParameters
.ConflictPenalty
=
4545 4 * AutoRouteParameters
.LastConflictPenalty
;
4546 AutoRouteParameters
.JogPenalty
= 1000 * (is_smoothing
? 20 : 4);
4547 AutoRouteParameters
.CongestionPenalty
= 1e6
;
4548 AutoRouteParameters
.MinPenalty
= EXPENSIVE
;
4549 for (i
= 0; i
< max_layer
; i
++)
4551 if (is_layer_group_active
[i
])
4553 AutoRouteParameters
.MinPenalty
= MIN (x_cost
[i
],
4554 AutoRouteParameters
.
4556 AutoRouteParameters
.MinPenalty
=
4557 MIN (y_cost
[i
], AutoRouteParameters
.MinPenalty
);
4560 AutoRouteParameters
.NewLayerPenalty
= is_smoothing
?
4561 0.5 * EXPENSIVE
: 10 * AutoRouteParameters
.ViaCost
;
4563 AutoRouteParameters
.hi_conflict
= MAX (8 * (passes
- pass
+ 1), 6);
4564 AutoRouteParameters
.is_odd
= (pass
& 1);
4565 AutoRouteParameters
.with_conflicts
= with_conflicts
;
4566 AutoRouteParameters
.is_smoothing
= is_smoothing
;
4567 AutoRouteParameters
.rip_always
= is_smoothing
;
4568 AutoRouteParameters
.last_smooth
= 0; //lastpass;
4569 AutoRouteParameters
.pass
= pass
+ 1;
4574 bad_boy (const BoxType
* b
, void *cl
)
4576 routebox_t
*box
= (routebox_t
*) b
;
4577 if (box
->type
== EXPANSION_AREA
)
4583 no_expansion_boxes (routedata_t
* rd
)
4591 for (i
= 0; i
< max_layer
; i
++)
4593 if (r_search (rd
->layergrouptree
[i
], &big
, NULL
, bad_boy
, NULL
))
4600 struct routeall_status
4602 /* --- for completion rate statistics ---- */
4604 /* total subnets routed without conflicts */
4606 /* total subnets routed with conflicts */
4607 int conflict_subnets
;
4608 /* net failted entirely */
4610 /* net was ripped */
4612 int total_nets_routed
;
4614 struct routeall_status
4615 RouteAll (routedata_t
* rd
)
4617 struct routeall_status ras
;
4618 struct routeone_status ros
;
4623 heap_t
*this_pass
, *next_pass
, *tmp
;
4624 routebox_t
*net
, *p
, *pp
;
4625 cost_t total_net_cost
, last_cost
= 0, this_cost
= 0;
4628 /* initialize heap for first pass;
4629 * do smallest area first; that makes
4630 * the subsequent costs more representative */
4631 this_pass
= heap_create ();
4632 next_pass
= heap_create ();
4634 net_heap
= heap_create ();
4636 LIST_LOOP (rd
->first_net
, different_net
, net
);
4639 BoxType bb
= shrink_routebox (net
);
4640 LIST_LOOP (net
, same_net
, p
);
4642 MAKEMIN (bb
.X1
, p
->sbox
.X1
);
4643 MAKEMIN (bb
.Y1
, p
->sbox
.Y1
);
4644 MAKEMAX (bb
.X2
, p
->sbox
.X2
);
4645 MAKEMAX (bb
.Y2
, p
->sbox
.Y2
);
4648 area
= (float) (bb
.X2
- bb
.X1
) * (bb
.Y2
- bb
.Y1
);
4649 heap_insert (this_pass
, area
, net
);
4653 ras
.total_nets_routed
= 0;
4654 /* refinement/finishing passes */
4655 for (i
= 0; i
<= passes
+ smoothes
; i
++)
4657 #ifdef ROUTE_VERBOSE
4658 if (i
> 0 && i
<= passes
)
4659 printf ("--------- STARTING REFINEMENT PASS %d ------------\n", i
);
4660 else if (i
> passes
)
4661 printf ("--------- STARTING SMOOTHING PASS %d -------------\n",
4664 ras
.total_subnets
= ras
.routed_subnets
= ras
.conflict_subnets
=
4665 ras
.failed
= ras
.ripped
= 0;
4666 assert (heap_is_empty (next_pass
));
4668 while (!heap_is_empty (this_pass
))
4674 net
= (routebox_t
*) heap_remove_smallest (this_pass
);
4675 InitAutoRouteParameters (i
, net
->style
, i
< passes
, i
> passes
,
4676 i
== passes
+ smoothes
);
4679 /* rip up all unfixed traces in this net ? */
4680 if (AutoRouteParameters
.rip_always
)
4685 LIST_LOOP (net
, same_net
, p
);
4686 if (p
->flags
.is_bad
)
4694 LIST_LOOP (net
, same_net
, p
);
4695 p
->flags
.is_bad
= 0;
4696 if (!p
->flags
.fixed
)
4699 assert (!p
->flags
.homeless
);
4702 RemoveFromNet (p
, NET
);
4703 RemoveFromNet (p
, SUBNET
);
4705 if (AutoRouteParameters
.use_vias
&& p
->type
!= VIA_SHADOW
4706 && p
->type
!= PLANE
)
4708 mtspace_remove (rd
->mtspace
, &p
->box
,
4709 p
->flags
.is_odd
? ODD
: EVEN
,
4710 p
->style
->Keepaway
);
4712 mtspace_add (rd
->mtspace
, &p
->box
,
4713 p
->flags
.is_odd
? EVEN
: ODD
,
4714 p
->style
->Keepaway
);
4718 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
)
4719 && (p
->type
== LINE
|| p
->type
== VIA
))
4722 r_delete_entry (rd
->layergrouptree
[p
->group
],
4728 p
->flags
.is_odd
= AutoRouteParameters
.is_odd
;
4732 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
4733 gui
->use_mask (HID_FLUSH_DRAW_Q
);
4734 /* reset to original connectivity */
4742 heap_insert (next_pass
, 0, net
);
4746 /* count number of subnets */
4747 FOREACH_SUBNET (net
, p
);
4748 ras
.total_subnets
++;
4749 END_FOREACH (net
, p
);
4750 /* the first subnet doesn't require routing. */
4751 ras
.total_subnets
--;
4754 /* only route that which isn't fully routed */
4756 if (ras
.total_subnets
&& !aabort
)
4758 if (ras
.total_subnets
)
4761 /* the loop here ensures that we get to all subnets even if
4762 * some of them are unreachable from the first subnet. */
4763 LIST_LOOP (net
, same_net
, p
);
4766 BoxType b
= shrink_routebox (p
);
4767 /* using a heap allows us to start from smaller objects and
4768 * end at bigger ones. also prefer to start at planes, then pads */
4769 heap_insert (net_heap
, (float) (b
.X2
- b
.X1
) *
4770 #if defined(ROUTE_RANDOMIZED)
4771 (0.3 + rand () / (RAND_MAX
+ 1.0)) *
4773 (b
.Y2
- b
.Y1
) * (p
->type
== PLANE
?
4778 ros
.net_completely_routed
= 0;
4779 while (!heap_is_empty (net_heap
))
4781 p
= (routebox_t
*) heap_remove_smallest (net_heap
);
4783 if (p
->flags
.fixed
&& !p
->flags
.subnet_processed
4784 && p
->type
!= OTHER
)
4786 while (!ros
.net_completely_routed
)
4788 assert (no_expansion_boxes (rd
));
4789 /* FIX ME: the number of edges to examine should be in autoroute parameters
4790 * i.e. the 2000 and 800 hard-coded below should be controllable by the user
4793 RouteOne (rd
, p
, NULL
,
4794 ((AutoRouteParameters
.
4795 is_smoothing
? 2000 : 800) * (i
+
4798 total_net_cost
+= ros
.best_route_cost
;
4799 if (ros
.found_route
)
4801 if (ros
.route_had_conflicts
)
4802 ras
.conflict_subnets
++;
4805 ras
.routed_subnets
++;
4806 ras
.total_nets_routed
++;
4811 if (!ros
.net_completely_routed
)
4813 /* don't bother trying any other source in this subnet */
4814 LIST_LOOP (p
, same_subnet
, pp
);
4815 pp
->flags
.subnet_processed
= 1;
4819 /* note that we can infer nothing about ras.total_subnets based
4820 * on the number of calls to RouteOne, because we may be unable
4821 * to route a net from a particular starting point, but perfectly
4822 * able to route it from some other. */
4829 if (!ros
.net_completely_routed
)
4830 net
->flags
.is_bad
= 1; /* don't skip this the next round */
4833 /* Route easiest nets from this pass first on next pass.
4834 * This works best because it's likely that the hardest
4835 * is the last one routed (since it has the most obstacles)
4836 * but it will do no good to rip it up and try it again
4837 * without first changing any of the other routes
4839 heap_insert (next_pass
, total_net_cost
, net
);
4840 if (total_net_cost
< EXPENSIVE
)
4841 this_cost
+= total_net_cost
;
4842 /* reset subnet_processed flags */
4843 LIST_LOOP (net
, same_net
, p
);
4845 p
->flags
.subnet_processed
= 0;
4849 /* swap this_pass and next_pass and do it all over again! */
4851 assert (heap_is_empty (this_pass
));
4853 this_pass
= next_pass
;
4855 /* XXX: here we should update a status bar */
4856 #if defined(ROUTE_DEBUG) || defined (ROUTE_VERBOSE)
4858 ("END OF PASS %d: %d/%d subnets routed without conflicts at cost %.0f, %d conflicts, %d failed %d ripped\n",
4859 i
, ras
.routed_subnets
, ras
.total_subnets
, this_cost
,
4860 ras
.conflict_subnets
, ras
.failed
, ras
.ripped
);
4866 /* if no conflicts found, skip directly to smoothing pass! */
4867 if (ras
.conflict_subnets
== 0 && ras
.routed_subnets
== ras
.total_subnets
4869 i
= passes
- (smoothes
? 0 : 1);
4870 /* if no changes in a smoothing round, then we're done */
4871 if (this_cost
== last_cost
&& i
> passes
&& i
< passes
+ smoothes
)
4872 i
= passes
+ smoothes
- 1;
4873 last_cost
= this_cost
;
4876 Message ("%d of %d nets successfully routed.\n",
4877 ras
.routed_subnets
, ras
.total_subnets
);
4879 heap_destroy (&this_pass
);
4880 heap_destroy (&next_pass
);
4882 heap_destroy (&net_heap
);
4885 /* no conflicts should be left at the end of the process. */
4886 assert (ras
.conflict_subnets
== 0);
4899 fpin_rect (const BoxType
* b
, void *cl
)
4901 PinTypePtr pin
= (PinTypePtr
) b
;
4902 struct fpin_info
*info
= (struct fpin_info
*) cl
;
4903 if (pin
->X
== info
->X
&& pin
->Y
== info
->Y
)
4905 info
->pin
= (PinTypePtr
) b
;
4906 longjmp (info
->env
, 1);
4912 FindPin (const BoxType
* box
, PinTypePtr
* pin
)
4914 struct fpin_info info
;
4919 if (setjmp (info
.env
) == 0)
4920 r_search (PCB
->Data
->pin_tree
, box
, NULL
, fpin_rect
, &info
);
4926 if (setjmp (info
.env
) == 0)
4927 r_search (PCB
->Data
->via_tree
, box
, NULL
, fpin_rect
, &info
);
4938 /* paths go on first 'on' layer in group */
4939 /* returns 'True' if any paths were added. */
4941 IronDownAllUnfixedPaths (routedata_t
* rd
)
4943 Boolean changed
= False
;
4945 routebox_t
*net
, *p
;
4947 LIST_LOOP (rd
->first_net
, different_net
, net
);
4949 LIST_LOOP (net
, same_net
, p
);
4951 if (!p
->flags
.fixed
)
4953 /* find first on layer in this group */
4954 assert (PCB
->LayerGroups
.Number
[p
->group
] > 0);
4955 assert (is_layer_group_active
[p
->group
]);
4956 for (i
= 0, layer
= NULL
; i
< PCB
->LayerGroups
.Number
[p
->group
];
4959 layer
= LAYER_PTR (PCB
->LayerGroups
.Entries
[p
->group
][i
]);
4963 assert (layer
&& layer
->On
); /*at least one layer must be on in this group! */
4964 assert (p
->type
!= EXPANSION_AREA
);
4965 if (p
->type
== LINE
)
4967 BDimension halfwidth
= HALF_THICK (p
->style
->Thick
);
4968 double th
= halfwidth
* 2 + 1;
4970 assert (p
->parent
.line
== NULL
);
4971 /* orthogonal; thickness is 2*halfwidth */
4972 /* flip coordinates, if bl_to_ur */
4974 total_wire_length
+=
4975 sqrt ((b
.X2
- b
.X1
- th
) * (b
.X2
- b
.X1
- th
) +
4976 (b
.Y2
- b
.Y1
- th
) * (b
.Y2
- b
.Y1
- th
));
4977 b
= shrink_box (&b
, halfwidth
);
4978 if (b
.X2
== b
.X1
+ 1)
4980 if (b
.Y2
== b
.Y1
+ 1)
4982 if (p
->flags
.bl_to_ur
)
4989 /* using CreateDrawn instead of CreateNew concatenates sequential lines */
4990 p
->parent
.line
= CreateDrawnLineOnLayer
4991 (layer
, b
.X1
, b
.Y1
, b
.X2
, b
.Y2
,
4993 p
->style
->Keepaway
* 2,
4994 MakeFlags (AUTOFLAG
|
4995 (TEST_FLAG (CLEARNEWFLAG
, PCB
) ? CLEARLINEFLAG
:
5000 AddObjectToCreateUndoList (LINE_TYPE
, layer
,
5001 p
->parent
.line
, p
->parent
.line
);
5005 else if (p
->type
== VIA
|| p
->type
== VIA_SHADOW
)
5008 (p
->type
== VIA_SHADOW
) ? p
->parent
.via_shadow
: p
;
5009 BDimension radius
= HALF_THICK (pp
->style
->Diameter
);
5010 BoxType b
= shrink_routebox (p
);
5012 assert (pp
->type
== VIA
);
5013 if (pp
->parent
.via
== NULL
)
5015 assert (b
.X1
+ radius
== b
.X2
- radius
);
5016 assert (b
.Y1
+ radius
== b
.Y2
- radius
);
5018 CreateNewVia (PCB
->Data
, b
.X1
+ radius
,
5020 pp
->style
->Diameter
,
5021 2 * pp
->style
->Keepaway
,
5022 0, pp
->style
->Hole
, NULL
,
5023 MakeFlags (AUTOFLAG
));
5024 assert (pp
->parent
.via
);
5027 AddObjectToCreateUndoList (VIA_TYPE
,
5034 assert (pp
->parent
.via
);
5035 if (p
->type
== VIA_SHADOW
)
5038 p
->parent
.via
= pp
->parent
.via
;
5041 else if (p
->type
== THERMAL
)
5042 /* nothing to do because, the via might not be there yet */ ;
5048 /* loop again to place all the thermals now that the vias are down */
5049 LIST_LOOP (net
, same_net
, p
);
5051 if (p
->type
== THERMAL
)
5053 PinTypePtr pin
= NULL
;
5054 /* thermals are alread a single point search, no need to shrink */
5055 int type
= FindPin (&p
->box
, &pin
);
5058 AddObjectToClearPolyUndoList (type
,
5059 pin
->Element
? pin
->Element
: pin
,
5061 RestoreToPolygon (PCB
->Data
, VIA_TYPE
, LAYER_PTR (p
->layer
),
5063 AddObjectToFlagUndoList (type
,
5064 pin
->Element
? pin
->Element
: pin
, pin
,
5066 ASSIGN_THERM (p
->layer
, PCB
->ThermStyle
, pin
);
5067 AddObjectToClearPolyUndoList (type
,
5068 pin
->Element
? pin
->Element
: pin
,
5070 ClearFromPolygon (PCB
->Data
, VIA_TYPE
, LAYER_PTR (p
->layer
),
5083 AutoRoute (Boolean selected
)
5085 Boolean changed
= False
;
5089 total_wire_length
= 0;
5090 total_via_count
= 0;
5091 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
5093 gui
->use_mask (HID_LIVE_DRAWING
);
5098 ar_gc
= gui
->make_gc ();
5099 gui
->set_line_cap (ar_gc
, Round_Cap
);
5102 for (i
= 0; i
< NUM_STYLES
; i
++)
5104 if (PCB
->RouteStyle
[i
].Thick
== 0 ||
5105 PCB
->RouteStyle
[1].Diameter
== 0 ||
5106 PCB
->RouteStyle
[1].Hole
== 0 || PCB
->RouteStyle
[i
].Keepaway
== 0)
5108 Message ("You must define proper routing styles\n"
5109 "before auto-routing.\n");
5113 if (PCB
->Data
->RatN
== 0)
5115 SaveFindFlag (DRCFLAG
);
5116 rd
= CreateRouteData ();
5120 routebox_t
*net
, *rb
, *last
;
5122 /* count number of rats selected */
5123 RAT_LOOP (PCB
->Data
);
5125 if (!selected
|| TEST_FLAG (SELECTEDFLAG
, line
))
5129 #ifdef ROUTE_VERBOSE
5130 printf ("%d nets!\n", i
);
5133 goto donerouting
; /* nothing to do here */
5134 /* if only one rat selected, do things the quick way. =) */
5137 RAT_LOOP (PCB
->Data
);
5138 if (!selected
|| TEST_FLAG (SELECTEDFLAG
, line
))
5140 /* look up the end points of this rat line */
5144 FindRouteBoxOnLayerGroup (rd
, line
->Point1
.X
,
5145 line
->Point1
.Y
, line
->group1
);
5147 FindRouteBoxOnLayerGroup (rd
, line
->Point2
.X
,
5148 line
->Point2
.Y
, line
->group2
);
5149 assert (a
!= NULL
&& b
!= NULL
);
5150 assert (a
->style
== b
->style
);
5152 if (a->type != PAD && b->type == PAD)
5159 /* route exactly one net, without allowing conflicts */
5160 InitAutoRouteParameters (0, a
->style
, False
, True
, True
);
5161 /* hace planes work better as sources than targets */
5162 changed
= RouteOne (rd
, a
, b
, 150000).found_route
|| changed
;
5167 /* otherwise, munge the netlists so that only the selected rats
5169 /* first, separate all sub nets into separate nets */
5170 /* note that this code works because LIST_LOOP is clever enough not to
5171 * be fooled when the list is changing out from under it. */
5173 LIST_LOOP (rd
->first_net
, different_net
, net
);
5175 FOREACH_SUBNET (net
, rb
);
5179 last
->different_net
.next
= rb
;
5180 rb
->different_net
.prev
= last
;
5184 END_FOREACH (net
, rb
);
5185 LIST_LOOP (net
, same_net
, rb
);
5187 rb
->same_net
= rb
->same_subnet
;
5190 /* at this point all nets are equal to their subnets */
5195 last
->different_net
.next
= rd
->first_net
;
5196 rd
->first_net
->different_net
.prev
= last
;
5199 /* now merge only those subnets connected by a rat line */
5200 RAT_LOOP (PCB
->Data
);
5201 if (!selected
|| TEST_FLAG (SELECTEDFLAG
, line
))
5203 /* look up the end points of this rat line */
5207 FindRouteBoxOnLayerGroup (rd
, line
->Point1
.X
,
5208 line
->Point1
.Y
, line
->group1
);
5210 FindRouteBoxOnLayerGroup (rd
, line
->Point2
.X
,
5211 line
->Point2
.Y
, line
->group2
);
5214 #ifdef DEBUG_STALE_RATS
5215 AddObjectToFlagUndoList (RATLINE_TYPE
, line
, line
, line
);
5216 ASSIGN_FLAG (SELECTEDFLAG
, True
, line
);
5218 #endif /* DEBUG_STALE_RATS */
5219 Message ("The rats nest is stale! Aborting autoroute...\n");
5222 /* merge subnets into a net! */
5223 MergeNets (a
, b
, NET
);
5226 /* now 'different_net' may point to too many different nets. Reset. */
5227 LIST_LOOP (rd
->first_net
, different_net
, net
);
5229 if (!net
->flags
.touched
)
5231 LIST_LOOP (net
, same_net
, rb
);
5232 rb
->flags
.touched
= 1;
5235 else /* this is not a "different net"! */
5236 RemoveFromNet (net
, DIFFERENT_NET
);
5239 /* reset "touched" flag */
5240 LIST_LOOP (rd
->first_net
, different_net
, net
);
5242 LIST_LOOP (net
, same_net
, rb
);
5244 assert (rb
->flags
.touched
);
5245 rb
->flags
.touched
= 0;
5251 /* okay, rd's idea of netlist now corresponds to what we want routed */
5252 /* auto-route all nets */
5253 changed
= (RouteAll (rd
).total_nets_routed
> 0) || changed
;
5256 changed
= IronDownAllUnfixedPaths (rd
);
5257 Message ("Total added wire length = %f inches, %d vias added\n",
5258 total_wire_length
/ 1.e5
, total_via_count
);
5259 DestroyRouteData (&rd
);
5260 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
5262 gui
->use_mask (HID_LIVE_DRAWING_OFF
);
5266 SaveUndoSerialNumber ();
5268 /* optimize rats, we've changed connectivity a lot. */
5269 DeleteRats (False
/*all rats */ );
5270 RestoreUndoSerialNumber ();
5271 AddAllRats (False
/*all rats */ , NULL
);
5272 RestoreUndoSerialNumber ();
5274 IncrementUndoSerialNumber ();
5276 ClearAndRedrawOutput ();
5279 #if defined (ROUTE_DEBUG)