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? */
341 /* is this a final "smoothing" pass? */
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 bool 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 bool usedGroup
[MAX_LAYER
];
393 static int x_cost
[MAX_LAYER
], y_cost
[MAX_LAYER
];
394 static bool 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
);
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
, bool 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
->HoleIndexN
== 0 &&
772 (polygon
->Points
[0].X
== polygon
->Points
[1].X
||
773 polygon
->Points
[0].Y
== polygon
->Points
[1].Y
) &&
774 (polygon
->Points
[1].X
== polygon
->Points
[2].X
||
775 polygon
->Points
[1].Y
== polygon
->Points
[2].Y
) &&
776 (polygon
->Points
[2].X
== polygon
->Points
[3].X
||
777 polygon
->Points
[2].Y
== polygon
->Points
[3].Y
) &&
778 (polygon
->Points
[3].X
== polygon
->Points
[0].X
||
779 polygon
->Points
[3].Y
== polygon
->Points
[0].Y
))
780 is_not_rectangle
= 0;
781 rb
->flags
.nonstraight
= is_not_rectangle
;
784 if (TEST_FLAG (CLEARPOLYFLAG
, polygon
))
786 rb
->flags
.clear_poly
= 1;
787 if (!is_not_rectangle
)
793 AddText (PointerListType layergroupboxes
[], Cardinal layergroup
,
794 TextTypePtr text
, RouteStyleType
* style
)
796 AddIrregularObstacle (layergroupboxes
,
797 text
->BoundingBox
.X1
, text
->BoundingBox
.Y1
,
798 text
->BoundingBox
.X2
, text
->BoundingBox
.Y2
,
799 layergroup
, text
, style
);
802 AddArc (PointerListType layergroupboxes
[], Cardinal layergroup
,
803 ArcTypePtr arc
, RouteStyleType
* style
)
805 return AddIrregularObstacle (layergroupboxes
,
806 arc
->BoundingBox
.X1
, arc
->BoundingBox
.Y1
,
807 arc
->BoundingBox
.X2
, arc
->BoundingBox
.Y2
,
808 layergroup
, arc
, style
);
819 __found_one_on_lg (const BoxType
* box
, void *cl
)
821 struct rb_info
*inf
= (struct rb_info
*) cl
;
822 routebox_t
*rb
= (routebox_t
*) box
;
825 if (rb
->flags
.nonstraight
)
827 sb
= shrink_box (&rb
->box
, rb
->style
->Keepaway
);
828 if (inf
->query
.X1
>= sb
.X2
|| inf
->query
.X2
<= sb
.X1
||
829 inf
->query
.Y1
>= sb
.Y2
|| inf
->query
.Y2
<= sb
.Y1
)
832 if (rb
->type
== PLANE
)
833 return 1; /* keep looking for something smaller if a plane was found */
834 longjmp (inf
->env
, 1);
838 FindRouteBoxOnLayerGroup (routedata_t
* rd
,
839 LocationType X
, LocationType Y
, Cardinal layergroup
)
843 info
.query
= point_box (X
, Y
);
844 if (setjmp (info
.env
) == 0)
845 r_search (rd
->layergrouptree
[layergroup
], &info
.query
, NULL
,
846 __found_one_on_lg
, &info
);
850 #ifdef ROUTE_DEBUG_VERBOSE
852 DumpRouteBox (routebox_t
* rb
)
854 printf ("RB: (%d,%d)-(%d,%d) l%d; ",
855 rb
->box
.X1
, rb
->box
.Y1
, rb
->box
.X2
, rb
->box
.Y2
, (int) rb
->group
);
859 printf ("PAD[%s %s] ", rb
->parent
.pad
->Name
, rb
->parent
.pad
->Number
);
862 printf ("PIN[%s %s] ", rb
->parent
.pin
->Name
, rb
->parent
.pin
->Number
);
867 printf ("VIA[%s %s] ", rb
->parent
.via
->Name
, rb
->parent
.via
->Number
);
882 if (rb
->flags
.nonstraight
)
883 printf ("(nonstraight) ");
886 if (rb
->flags
.source
)
887 printf ("(source) ");
888 if (rb
->flags
.target
)
889 printf ("(target) ");
890 if (rb
->flags
.homeless
)
891 printf ("(homeless) ");
899 NetListListType Nets
;
900 PointerListType layergroupboxes
[MAX_LAYER
];
905 /* check which layers are active first */
907 for (group
= 0; group
< max_layer
; group
++)
909 for (i
= 0; i
< PCB
->LayerGroups
.Number
[group
]; i
++)
910 /* layer must be 1) not silk (ie, < max_layer) and 2) on */
911 if ((PCB
->LayerGroups
.Entries
[group
][i
] < max_layer
) &&
912 PCB
->Data
->Layer
[PCB
->LayerGroups
.Entries
[group
][i
]].On
)
915 is_layer_group_active
[group
] = true;
919 is_layer_group_active
[group
] = false;
921 /* if via visibility is turned off, don't use them */
922 AutoRouteParameters
.use_vias
= routing_layers
> 1 && PCB
->ViaOn
;
923 front
= GetLayerGroupNumberByNumber (max_layer
+ COMPONENT_LAYER
);
924 back
= GetLayerGroupNumberByNumber (max_layer
+ SOLDER_LAYER
);
925 /* determine preferred routing direction on each group */
926 for (i
= 0; i
< max_layer
; i
++)
928 if (i
!= back
&& i
!= front
)
930 x_cost
[i
] = (i
& 1) ? 2 : 1;
931 y_cost
[i
] = (i
& 1) ? 1 : 2;
944 /* create routedata */
945 rd
= malloc (sizeof (*rd
));
946 memset ((void *) rd
, 0, sizeof (*rd
));
947 /* create default style */
948 rd
->defaultstyle
.Thick
= Settings
.LineThickness
;
949 rd
->defaultstyle
.Diameter
= Settings
.ViaThickness
;
950 rd
->defaultstyle
.Hole
= Settings
.ViaDrillingHole
;
951 rd
->defaultstyle
.Keepaway
= Settings
.Keepaway
;
952 rd
->max_bloat
= BLOAT (&rd
->defaultstyle
);
953 rd
->max_keep
= Settings
.Keepaway
;
954 /* create styles structures */
955 bbox
.X1
= bbox
.Y1
= 0;
956 bbox
.X2
= PCB
->MaxWidth
;
957 bbox
.Y2
= PCB
->MaxHeight
;
958 for (i
= 0; i
< NUM_STYLES
+ 1; i
++)
960 RouteStyleType
*style
=
961 (i
< NUM_STYLES
) ? &PCB
->RouteStyle
[i
] : &rd
->defaultstyle
;
962 rd
->styles
[i
] = style
;
965 /* initialize pointerlisttype */
966 for (i
= 0; i
< max_layer
; i
++)
968 layergroupboxes
[i
].Ptr
= NULL
;
969 layergroupboxes
[i
].PtrN
= 0;
970 layergroupboxes
[i
].PtrMax
= 0;
971 GROUP_LOOP (PCB
->Data
, i
);
973 if (layer
->LineN
|| layer
->ArcN
)
976 usedGroup
[i
] = false;
980 usedGroup
[front
] = true;
981 usedGroup
[back
] = true;
982 /* add the objects in the netlist first.
983 * then go and add all other objects that weren't already added
985 * this saves on searching the trees to find the nets
987 /* use the DRCFLAG to mark objects as they are entered */
988 ResetFoundPinsViasAndPads (false);
989 ResetFoundLinesAndPolygons (false);
990 Nets
= CollectSubnets (false);
992 routebox_t
*last_net
= NULL
;
993 NETLIST_LOOP (&Nets
);
995 routebox_t
*last_in_net
= NULL
;
998 routebox_t
*last_in_subnet
= NULL
;
1001 for (j
= 0; j
< NUM_STYLES
; j
++)
1002 if (net
->Style
== rd
->styles
[j
])
1004 CONNECTION_LOOP (net
);
1006 routebox_t
*rb
= NULL
;
1007 SET_FLAG (DRCFLAG
, (PinTypePtr
) connection
->ptr2
);
1008 if (connection
->type
== LINE_TYPE
)
1010 LineType
*line
= (LineType
*) connection
->ptr2
;
1012 /* lines are listed at each end, so skip one */
1013 /* this should probably by a macro named "BUMP_LOOP" */
1016 /* dice up non-straight lines into many tiny obstacles */
1017 if (line
->Point1
.X
!= line
->Point2
.X
1018 && line
->Point1
.Y
!= line
->Point2
.Y
)
1020 LineType fake_line
= *line
;
1021 int dx
= (line
->Point2
.X
- line
->Point1
.X
);
1022 int dy
= (line
->Point2
.Y
- line
->Point1
.Y
);
1023 int segs
= MAX (ABS (dx
),
1024 ABS (dy
)) / (4 * BLOAT (rd
->styles
[j
]) + 1);
1026 segs
= MAX (1, MIN (segs
, 32)); /* don't go too crazy */
1029 for (qq
= 0; qq
< segs
- 1; qq
++)
1031 fake_line
.Point2
.X
= fake_line
.Point1
.X
+ dx
;
1032 fake_line
.Point2
.Y
= fake_line
.Point1
.Y
+ dy
;
1033 if (fake_line
.Point2
.X
== line
->Point2
.X
1034 && fake_line
.Point2
.Y
== line
->Point2
.Y
)
1037 AddLine (layergroupboxes
, connection
->group
,
1038 &fake_line
, line
, rd
->styles
[j
]);
1039 if (last_in_subnet
&& rb
!= last_in_subnet
)
1040 MergeNets (last_in_subnet
, rb
, ORIGINAL
);
1041 if (last_in_net
&& rb
!= last_in_net
)
1042 MergeNets (last_in_net
, rb
, NET
);
1043 last_in_subnet
= last_in_net
= rb
;
1044 fake_line
.Point1
= fake_line
.Point2
;
1046 fake_line
.Point2
= line
->Point2
;
1048 AddLine (layergroupboxes
, connection
->group
, &fake_line
,
1049 line
, rd
->styles
[j
]);
1054 AddLine (layergroupboxes
, connection
->group
, line
, line
,
1059 switch (connection
->type
)
1063 AddPad (layergroupboxes
, connection
->ptr1
,
1064 connection
->ptr2
, rd
->styles
[j
]);
1068 AddPin (layergroupboxes
, connection
->ptr2
, false,
1073 AddPin (layergroupboxes
, connection
->ptr2
, true,
1078 AddPolygon (layergroupboxes
,
1079 GetLayerNumber (PCB
->Data
, connection
->ptr1
),
1080 connection
->ptr2
, rd
->styles
[j
]);
1084 /* update circular connectivity lists */
1085 if (last_in_subnet
&& rb
!= last_in_subnet
)
1086 MergeNets (last_in_subnet
, rb
, ORIGINAL
);
1087 if (last_in_net
&& rb
!= last_in_net
)
1088 MergeNets (last_in_net
, rb
, NET
);
1089 last_in_subnet
= last_in_net
= rb
;
1090 rd
->max_bloat
= MAX (rd
->max_bloat
, BLOAT (rb
->style
));
1091 rd
->max_keep
= MAX (rd
->max_keep
, rb
->style
->Keepaway
);
1096 if (last_net
&& last_in_net
)
1097 MergeNets (last_net
, last_in_net
, DIFFERENT_NET
);
1098 last_net
= last_in_net
;
1101 rd
->first_net
= last_net
;
1103 FreeNetListListMemory (&Nets
);
1105 /* reset all nets to "original" connectivity (which we just set) */
1108 LIST_LOOP (rd
->first_net
, different_net
, net
);
1113 /* add pins and pads of elements */
1114 ALLPIN_LOOP (PCB
->Data
);
1116 if (TEST_FLAG (DRCFLAG
, pin
))
1117 CLEAR_FLAG (DRCFLAG
, pin
);
1119 AddPin (layergroupboxes
, pin
, false, rd
->styles
[NUM_STYLES
]);
1122 ALLPAD_LOOP (PCB
->Data
);
1124 if (TEST_FLAG (DRCFLAG
, pad
))
1125 CLEAR_FLAG (DRCFLAG
, pad
);
1127 AddPad (layergroupboxes
, element
, pad
, rd
->styles
[NUM_STYLES
]);
1131 VIA_LOOP (PCB
->Data
);
1133 if (TEST_FLAG (DRCFLAG
, via
))
1134 CLEAR_FLAG (DRCFLAG
, via
);
1136 AddPin (layergroupboxes
, via
, true, rd
->styles
[NUM_STYLES
]);
1140 for (i
= 0; i
< max_layer
; i
++)
1142 int layergroup
= GetLayerGroupNumberByNumber (i
);
1143 /* add all (non-rat) lines */
1144 LINE_LOOP (LAYER_PTR (i
));
1146 if (TEST_FLAG (DRCFLAG
, line
))
1148 CLEAR_FLAG (DRCFLAG
, line
);
1151 /* dice up non-straight lines into many tiny obstacles */
1152 if (line
->Point1
.X
!= line
->Point2
.X
1153 && line
->Point1
.Y
!= line
->Point2
.Y
)
1155 LineType fake_line
= *line
;
1156 int dx
= (line
->Point2
.X
- line
->Point1
.X
);
1157 int dy
= (line
->Point2
.Y
- line
->Point1
.Y
);
1158 int segs
= MAX (ABS (dx
), ABS (dy
)) / (4 * rd
->max_bloat
+ 1);
1160 segs
= MAX (1, MIN (segs
, 32)); /* don't go too crazy */
1163 for (qq
= 0; qq
< segs
- 1; qq
++)
1165 fake_line
.Point2
.X
= fake_line
.Point1
.X
+ dx
;
1166 fake_line
.Point2
.Y
= fake_line
.Point1
.Y
+ dy
;
1167 if (fake_line
.Point2
.X
== line
->Point2
.X
1168 && fake_line
.Point2
.Y
== line
->Point2
.Y
)
1170 AddLine (layergroupboxes
, layergroup
, &fake_line
, line
,
1171 rd
->styles
[NUM_STYLES
]);
1172 fake_line
.Point1
= fake_line
.Point2
;
1174 fake_line
.Point2
= line
->Point2
;
1175 AddLine (layergroupboxes
, layergroup
, &fake_line
, line
,
1176 rd
->styles
[NUM_STYLES
]);
1180 AddLine (layergroupboxes
, layergroup
, line
, line
,
1181 rd
->styles
[NUM_STYLES
]);
1185 /* add all polygons */
1186 POLYGON_LOOP (LAYER_PTR (i
));
1188 if (TEST_FLAG (DRCFLAG
, polygon
))
1189 CLEAR_FLAG (DRCFLAG
, polygon
);
1191 AddPolygon (layergroupboxes
, i
, polygon
, rd
->styles
[NUM_STYLES
]);
1194 /* add all copper text */
1195 TEXT_LOOP (LAYER_PTR (i
));
1197 AddText (layergroupboxes
, layergroup
, text
, rd
->styles
[NUM_STYLES
]);
1201 ARC_LOOP (LAYER_PTR (i
));
1203 AddArc (layergroupboxes
, layergroup
, arc
, rd
->styles
[NUM_STYLES
]);
1208 /* create r-trees from pointer lists */
1209 for (i
= 0; i
< max_layer
; i
++)
1211 /* create the r-tree */
1212 rd
->layergrouptree
[i
] =
1213 r_create_tree ((const BoxType
**) layergroupboxes
[i
].Ptr
,
1214 layergroupboxes
[i
].PtrN
, 1);
1217 if (AutoRouteParameters
.use_vias
)
1219 rd
->mtspace
= mtspace_create ();
1221 /* create "empty-space" structures for via placement (now that we know
1222 * appropriate keepaways for all the fixed elements) */
1223 for (i
= 0; i
< max_layer
; i
++)
1225 POINTER_LOOP (&layergroupboxes
[i
]);
1227 routebox_t
*rb
= (routebox_t
*) * ptr
;
1228 if (!rb
->flags
.clear_poly
)
1229 mtspace_add (rd
->mtspace
, &rb
->box
, FIXED
, rb
->style
->Keepaway
);
1234 /* free pointer lists */
1235 for (i
= 0; i
< max_layer
; i
++)
1236 FreePointerListMemory (&layergroupboxes
[i
]);
1242 DestroyRouteData (routedata_t
** rd
)
1245 for (i
= 0; i
< max_layer
; i
++)
1246 r_destroy_tree (&(*rd
)->layergrouptree
[i
]);
1247 if (AutoRouteParameters
.use_vias
)
1248 mtspace_destroy (&(*rd
)->mtspace
);
1253 /*-----------------------------------------------------------------
1254 * routebox reference counting.
1257 /* increment the reference count on a routebox. */
1259 RB_up_count (routebox_t
* rb
)
1261 assert (rb
->flags
.homeless
);
1265 /* decrement the reference count on a routebox, freeing if this box becomes
1268 RB_down_count (routebox_t
* rb
)
1270 assert (rb
->type
== EXPANSION_AREA
);
1271 assert (rb
->flags
.homeless
);
1272 assert (rb
->refcount
> 0);
1273 if (--rb
->refcount
== 0)
1275 if (rb
->parent
.expansion_area
->flags
.homeless
)
1276 RB_down_count (rb
->parent
.expansion_area
);
1281 /*-----------------------------------------------------------------
1282 * Rectangle-expansion routing code.
1286 ResetSubnet (routebox_t
* net
)
1289 /* reset connectivity of everything on this net */
1290 LIST_LOOP (net
, same_net
, rb
);
1291 rb
->same_subnet
= rb
->original_subnet
;
1295 static inline cost_t
1296 cost_to_point_on_layer (const CheapPointType
* p1
,
1297 const CheapPointType
* p2
, Cardinal point_layer
)
1299 cost_t x_dist
= p1
->X
- p2
->X
, y_dist
= p1
->Y
- p2
->Y
, r
;
1300 x_dist
*= x_cost
[point_layer
];
1301 y_dist
*= y_cost
[point_layer
];
1302 /* cost is proportional to orthogonal distance. */
1303 r
= ABS (x_dist
) + ABS (y_dist
);
1304 if (p1
->X
!= p2
->X
&& p1
->Y
!= p2
->Y
)
1305 r
+= AutoRouteParameters
.JogPenalty
;
1310 cost_to_point (const CheapPointType
* p1
, Cardinal point_layer1
,
1311 const CheapPointType
* p2
, Cardinal point_layer2
)
1313 cost_t r
= cost_to_point_on_layer (p1
, p2
, point_layer1
);
1314 /* apply via cost penalty if layers differ */
1315 if (point_layer1
!= point_layer2
)
1316 r
+= AutoRouteParameters
.ViaCost
;
1320 /* return the minimum *cost* from a point to a box on any layer.
1321 * It's safe to return a smaller than minimum cost
1324 cost_to_layerless_box (const CheapPointType
* p
, Cardinal point_layer
,
1327 CheapPointType p2
= closest_point_in_box (p
, b
);
1328 register cost_t c1
, c2
;
1336 return c1
* AutoRouteParameters
.MinPenalty
+ c2
;
1338 return c2
* AutoRouteParameters
.MinPenalty
+ c1
;
1341 /* get to actual pins/pad target coordinates */
1343 TargetPoint (CheapPointType
* nextpoint
, const routebox_t
* target
)
1345 if (target
->type
== PIN
)
1347 nextpoint
->X
= target
->parent
.pin
->X
;
1348 nextpoint
->Y
= target
->parent
.pin
->Y
;
1351 else if (target
->type
== PAD
)
1353 if (abs (target
->parent
.pad
->Point1
.X
- nextpoint
->X
) <
1354 abs (target
->parent
.pad
->Point2
.X
- nextpoint
->X
))
1355 nextpoint
->X
= target
->parent
.pad
->Point1
.X
;
1357 nextpoint
->X
= target
->parent
.pad
->Point2
.X
;
1358 if (abs (target
->parent
.pad
->Point1
.Y
- nextpoint
->Y
) <
1359 abs (target
->parent
.pad
->Point2
.Y
- nextpoint
->Y
))
1360 nextpoint
->Y
= target
->parent
.pad
->Point1
.Y
;
1362 nextpoint
->Y
= target
->parent
.pad
->Point2
.Y
;
1367 nextpoint
->X
= CENTER_X (target
->sbox
);
1368 nextpoint
->Y
= CENTER_Y (target
->sbox
);
1373 /* return the *minimum cost* from a point to a route box, including possible
1374 * via costs if the route box is on a different layer.
1375 * assume routbox is bloated unless it is an expansion area
1378 cost_to_routebox (const CheapPointType
* p
, Cardinal point_layer
,
1379 const routebox_t
* rb
)
1381 register cost_t trial
= 0;
1382 CheapPointType p2
= closest_point_in_routebox (p
, rb
);
1383 if (!usedGroup
[point_layer
] || !usedGroup
[rb
->group
])
1384 trial
= AutoRouteParameters
.NewLayerPenalty
;
1385 if ((p2
.X
- p
->X
) * (p2
.Y
- p
->Y
) != 0)
1386 trial
+= AutoRouteParameters
.JogPenalty
;
1387 /* special case for defered via searching */
1388 if (point_layer
> max_layer
|| point_layer
== rb
->group
)
1389 return trial
+ ABS (p2
.X
- p
->X
) + ABS (p2
.Y
- p
->Y
);
1390 /* if this target is only a via away, then the via is cheaper than the congestion */
1391 if (p
->X
== p2
.X
&& p
->Y
== p2
.Y
)
1393 trial
+= AutoRouteParameters
.ViaCost
;
1394 trial
+= ABS (p2
.X
- p
->X
) + ABS (p2
.Y
- p
->Y
);
1400 bloat_routebox (routebox_t
* rb
)
1403 LocationType keepaway
;
1404 assert (__routebox_is_good (rb
));
1406 if (rb
->flags
.nobloat
)
1409 /* Obstacle exclusion zones get bloated by the larger of
1410 * the two required clearances plus half the track width.
1412 keepaway
= MAX (AutoRouteParameters
.style
->Keepaway
, rb
->style
->Keepaway
);
1413 r
= bloat_box (&rb
->sbox
, keepaway
+
1414 HALF_THICK (AutoRouteParameters
.style
->Thick
));
1419 #ifdef ROUTE_DEBUG /* only for debugging expansion areas */
1422 fillbox (const BoxType
* b
)
1424 LayerTypePtr SLayer
= LAYER_PTR (0);
1425 gui
->set_color (Output
.fgGC
, SLayer
->Color
);
1426 gui
->fill_rect (Output
.fgGC
, b
->X1
, b
->Y1
, b
->X2
, b
->Y2
);
1429 /* makes a line on the solder layer silk surrounding the box */
1431 showbox (BoxType b
, Dimension thickness
, int group
)
1434 LayerTypePtr SLayer
= LAYER_PTR (group
);
1437 if (showboxen
!= -1 && showboxen
!= group
)
1441 gui
->set_line_width (Output
.fgGC
, thickness
);
1442 gui
->set_line_cap (Output
.fgGC
, Trace_Cap
);
1443 gui
->set_color (Output
.fgGC
, SLayer
->Color
);
1445 gui
->draw_line (Output
.fgGC
, b
.X1
, b
.Y1
, b
.X2
, b
.Y1
);
1446 gui
->draw_line (Output
.fgGC
, b
.X1
, b
.Y2
, b
.X2
, b
.Y2
);
1447 gui
->draw_line (Output
.fgGC
, b
.X1
, b
.Y1
, b
.X1
, b
.Y2
);
1448 gui
->draw_line (Output
.fgGC
, b
.X2
, b
.Y1
, b
.X2
, b
.Y2
);
1449 gui
->use_mask (HID_FLUSH_DRAW_Q
);
1452 if (b
.Y1
== b
.Y2
|| b
.X1
== b
.X2
)
1454 line
= CreateNewLineOnLayer (LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1455 b
.X1
, b
.Y1
, b
.X2
, b
.Y1
, thickness
, 0,
1457 AddObjectToCreateUndoList (LINE_TYPE
,
1458 LAYER_PTR (max_layer
+ COMPONENT_LAYER
), line
,
1462 line
= CreateNewLineOnLayer (LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1463 b
.X1
, b
.Y2
, b
.X2
, b
.Y2
, thickness
, 0,
1465 AddObjectToCreateUndoList (LINE_TYPE
,
1466 LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1469 line
= CreateNewLineOnLayer (LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1470 b
.X1
, b
.Y1
, b
.X1
, b
.Y2
, thickness
, 0,
1472 AddObjectToCreateUndoList (LINE_TYPE
,
1473 LAYER_PTR (max_layer
+ COMPONENT_LAYER
), line
,
1477 line
= CreateNewLineOnLayer (LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1478 b
.X2
, b
.Y1
, b
.X2
, b
.Y2
, thickness
, 0,
1480 AddObjectToCreateUndoList (LINE_TYPE
,
1481 LAYER_PTR (max_layer
+ COMPONENT_LAYER
),
1488 #if defined(ROUTE_DEBUG)
1490 showedge (edge_t
* e
)
1492 BoxType
*b
= (BoxType
*) e
->rb
;
1494 gui
->set_line_cap (Output
.fgGC
, Trace_Cap
);
1495 gui
->set_line_width (Output
.fgGC
, 1);
1496 gui
->set_color (Output
.fgGC
, Settings
.MaskColor
);
1498 switch (e
->expand_dir
)
1501 gui
->draw_line (Output
.fgGC
, b
->X1
, b
->Y1
, b
->X2
, b
->Y1
);
1504 gui
->draw_line (Output
.fgGC
, b
->X1
, b
->Y2
, b
->X2
, b
->Y2
);
1507 gui
->draw_line (Output
.fgGC
, b
->X1
, b
->Y1
, b
->X1
, b
->Y2
);
1510 gui
->draw_line (Output
.fgGC
, b
->X2
, b
->Y1
, b
->X2
, b
->Y2
);
1518 #if defined(ROUTE_DEBUG)
1520 showroutebox (routebox_t
* rb
)
1522 showbox (rb
->sbox
, rb
->flags
.source
? 20 : (rb
->flags
.target
? 10 : 1),
1523 rb
->flags
.is_via
? max_layer
+ COMPONENT_LAYER
: rb
->group
);
1528 EraseRouteBox (routebox_t
* rb
)
1530 LocationType X1
, Y1
, X2
, Y2
;
1533 if (rb
->box
.X2
- rb
->box
.X1
< rb
->box
.Y2
- rb
->box
.Y1
)
1535 thick
= rb
->box
.X2
- rb
->box
.X1
;
1536 X1
= X2
= (rb
->box
.X2
+ rb
->box
.X1
) / 2;
1537 Y1
= rb
->box
.Y1
+ thick
/ 2;
1538 Y2
= rb
->box
.Y2
- thick
/ 2;
1542 thick
= rb
->box
.Y2
- rb
->box
.Y1
;
1543 Y1
= Y2
= (rb
->box
.Y2
+ rb
->box
.Y1
) / 2;
1544 X1
= rb
->box
.X1
+ thick
/ 2;
1545 X2
= rb
->box
.X2
- thick
/ 2;
1548 gui
->set_line_width (ar_gc
, thick
);
1549 gui
->set_color (ar_gc
, Settings
.BackgroundColor
);
1550 gui
->draw_line (ar_gc
, X1
, Y1
, X2
, Y2
);
1553 /* return a "parent" of this edge which immediately precedes it in the route.*/
1555 route_parent (routebox_t
* rb
)
1557 while (rb
->flags
.homeless
&& !rb
->flags
.is_via
&& !rb
->flags
.is_thermal
)
1559 assert (rb
->type
== EXPANSION_AREA
);
1560 rb
= rb
->parent
.expansion_area
;
1567 path_conflicts (routebox_t
* rb
, routebox_t
* conflictor
, bool branch
)
1570 rb
->conflicts_with
= vector_duplicate (rb
->conflicts_with
);
1571 else if (!rb
->conflicts_with
)
1572 rb
->conflicts_with
= vector_create ();
1573 vector_append (rb
->conflicts_with
, conflictor
);
1574 return rb
->conflicts_with
;
1577 /* Touch everything (except fixed) on each net found
1578 * in the conflicts vector. If the vector is different
1579 * from the last one touched, untouch the last batch
1580 * and touch the new one. Always call with touch=1
1581 * (except for recursive call). Call with NULL, 1 to
1582 * clear the last batch touched.
1584 * touched items become invisible to current path
1585 * so we don't encounter the same conflictor more
1590 touch_conflicts (vector_t
* conflicts
, int touch
)
1592 static vector_t
*last
= NULL
;
1593 static int last_size
= 0;
1598 if (last
&& conflicts
!= last
)
1599 touch_conflicts (last
, 0);
1605 n
= vector_size (conflicts
);
1608 routebox_t
*rb
= (routebox_t
*) vector_element (conflicts
, i
);
1610 LIST_LOOP (rb
, same_net
, p
);
1611 if (!p
->flags
.fixed
)
1612 p
->flags
.touched
= touch
;
1624 /* return a "parent" of this edge which resides in a r-tree somewhere */
1625 /* -- actually, this "parent" *may* be a via box, which doesn't live in
1628 nonhomeless_parent (routebox_t
* rb
)
1630 return route_parent (rb
);
1633 /* some routines to find the minimum *cost* from a cost point to
1634 * a target (any target) */
1635 struct mincost_target_closure
1637 const CheapPointType
*CostPoint
;
1638 Cardinal CostPointLayer
;
1639 routebox_t
*nearest
;
1640 cost_t nearest_cost
;
1643 __region_within_guess (const BoxType
* region
, void *cl
)
1645 struct mincost_target_closure
*mtc
= (struct mincost_target_closure
*) cl
;
1646 cost_t cost_to_region
;
1647 if (mtc
->nearest
== NULL
)
1650 cost_to_layerless_box (mtc
->CostPoint
, mtc
->CostPointLayer
, region
);
1651 assert (cost_to_region
>= 0);
1652 /* if no guess yet, all regions are "close enough" */
1653 /* note that cost is *strictly more* than minimum distance, so we'll
1654 * always search a region large enough. */
1655 return (cost_to_region
< mtc
->nearest_cost
);
1658 __found_new_guess (const BoxType
* box
, void *cl
)
1660 struct mincost_target_closure
*mtc
= (struct mincost_target_closure
*) cl
;
1661 routebox_t
*guess
= (routebox_t
*) box
;
1662 cost_t cost_to_guess
=
1663 cost_to_routebox (mtc
->CostPoint
, mtc
->CostPointLayer
, guess
);
1664 assert (cost_to_guess
>= 0);
1665 /* if this is cheaper than previous guess... */
1666 if (cost_to_guess
< mtc
->nearest_cost
)
1668 mtc
->nearest
= guess
;
1669 mtc
->nearest_cost
= cost_to_guess
; /* this is our new guess! */
1673 return 0; /* not less expensive than our last guess */
1676 /* target_guess is our guess at what the nearest target is, or NULL if we
1677 * just plum don't have a clue. */
1679 mincost_target_to_point (const CheapPointType
* CostPoint
,
1680 Cardinal CostPointLayer
,
1681 rtree_t
* targets
, routebox_t
* target_guess
)
1683 struct mincost_target_closure mtc
;
1684 assert (target_guess
== NULL
|| target_guess
->flags
.target
); /* this is a target, right? */
1685 mtc
.CostPoint
= CostPoint
;
1686 mtc
.CostPointLayer
= CostPointLayer
;
1687 mtc
.nearest
= target_guess
;
1690 cost_to_routebox (mtc
.CostPoint
, mtc
.CostPointLayer
, mtc
.nearest
);
1692 mtc
.nearest_cost
= EXPENSIVE
;
1693 r_search (targets
, NULL
, __region_within_guess
, __found_new_guess
, &mtc
);
1694 assert (mtc
.nearest
!= NULL
&& mtc
.nearest_cost
>= 0);
1695 assert (mtc
.nearest
->flags
.target
); /* this is a target, right? */
1699 /* create edge from field values */
1700 /* mincost_target_guess can be NULL */
1702 CreateEdge (routebox_t
* rb
,
1703 LocationType CostPointX
, LocationType CostPointY
,
1704 cost_t cost_to_point
,
1705 routebox_t
* mincost_target_guess
,
1706 direction_t expand_dir
, rtree_t
* targets
)
1709 assert (__routebox_is_good (rb
));
1710 e
= malloc (sizeof (*e
));
1711 memset ((void *) e
, 0, sizeof (*e
));
1714 if (rb
->flags
.homeless
)
1716 e
->cost_point
.X
= CostPointX
;
1717 e
->cost_point
.Y
= CostPointY
;
1718 e
->cost_to_point
= cost_to_point
;
1719 e
->flags
.via_search
= 0;
1720 /* if this edge is created in response to a target, use it */
1723 mincost_target_to_point (&e
->cost_point
, rb
->group
,
1724 targets
, mincost_target_guess
);
1726 e
->mincost_target
= mincost_target_guess
;
1727 e
->expand_dir
= expand_dir
;
1728 assert (e
->rb
&& e
->mincost_target
); /* valid edge? */
1729 assert (!e
->flags
.is_via
|| e
->expand_dir
== ALL
);
1730 /* cost point should be on edge (unless this is a plane/via/conflict edge) */
1732 assert (rb
->type
== PLANE
|| rb
->conflicts_with
!= NULL
|| rb
->flags
.is_via
1733 || rb
->flags
.is_thermal
1734 || ((expand_dir
== NORTH
|| expand_dir
== SOUTH
) ? rb
->sbox
.X1
<=
1735 CostPointX
&& CostPointX
< rb
->sbox
.X2
1736 && CostPointY
== (expand_dir
==
1737 NORTH
? rb
->sbox
.Y1
: rb
->sbox
.Y2
- 1) :
1738 /* expand_dir==EAST || expand_dir==WEST */
1739 rb
->sbox
.Y1
<= CostPointY
&& CostPointY
< rb
->sbox
.Y2
&&
1740 CostPointX
== (expand_dir
==
1741 EAST
? rb
->sbox
.X2
- 1 : rb
->sbox
.X1
)));
1743 assert (__edge_is_good (e
));
1748 /* create edge, using previous edge to fill in defaults. */
1749 /* most of the work here is in determining a new cost point */
1751 CreateEdge2 (routebox_t
* rb
, direction_t expand_dir
,
1752 edge_t
* previous_edge
, rtree_t
* targets
, routebox_t
* guess
)
1755 CheapPointType thiscost
, prevcost
;
1758 assert (rb
&& previous_edge
);
1759 /* okay, find cheapest costpoint to costpoint of previous edge */
1760 thisbox
= edge_to_box (rb
, expand_dir
);
1761 prevcost
= previous_edge
->cost_point
;
1762 /* find point closest to target */
1763 thiscost
= closest_point_in_box (&prevcost
, &thisbox
);
1764 /* compute cost-to-point */
1765 d
= cost_to_point_on_layer (&prevcost
, &thiscost
, rb
->group
);
1766 /* add in jog penalty */
1767 if (previous_edge
->expand_dir
!= expand_dir
)
1768 d
+= AutoRouteParameters
.JogPenalty
;
1769 /* okay, new edge! */
1770 return CreateEdge (rb
, thiscost
.X
, thiscost
.Y
,
1771 previous_edge
->cost_to_point
+ d
,
1772 guess
? guess
: previous_edge
->mincost_target
,
1773 expand_dir
, targets
);
1776 /* create via edge, using previous edge to fill in defaults. */
1778 CreateViaEdge (const BoxType
* area
, Cardinal group
,
1779 routebox_t
* parent
, edge_t
* previous_edge
,
1780 conflict_t to_site_conflict
,
1781 conflict_t through_site_conflict
, rtree_t
* targets
)
1784 CheapPointType costpoint
;
1790 scale
[1] = AutoRouteParameters
.LastConflictPenalty
;
1791 scale
[2] = AutoRouteParameters
.ConflictPenalty
;
1793 assert (box_is_good (area
));
1794 assert (AutoRouteParameters
.with_conflicts
||
1795 (to_site_conflict
== NO_CONFLICT
&&
1796 through_site_conflict
== NO_CONFLICT
));
1797 rb
= CreateExpansionArea (area
, group
, parent
, true, previous_edge
);
1798 rb
->flags
.is_via
= 1;
1799 rb
->came_from
= ALL
;
1800 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_VIA_BOXES)
1802 #endif /* ROUTE_DEBUG && DEBUG_SHOW_VIA_BOXES */
1803 /* for planes, choose a point near the target */
1804 if (previous_edge
->flags
.in_plane
)
1808 /* find a target near this via box */
1809 pnt
.X
= CENTER_X (*area
);
1810 pnt
.Y
= CENTER_Y (*area
);
1811 target
= mincost_target_to_point (&pnt
, rb
->group
,
1813 previous_edge
->mincost_target
);
1814 /* now find point near the target */
1815 pnt
.X
= CENTER_X (target
->box
);
1816 pnt
.Y
= CENTER_Y (target
->box
);
1817 costpoint
= closest_point_in_routebox (&pnt
, rb
);
1818 /* we moved from the previous cost point through the plane which is free travel */
1820 (scale
[through_site_conflict
] *
1821 cost_to_point (&costpoint
, group
, &costpoint
,
1822 previous_edge
->rb
->group
));
1824 CreateEdge (rb
, costpoint
.X
, costpoint
.Y
,
1825 previous_edge
->cost_to_point
+ d
, target
, ALL
, NULL
);
1826 ne
->mincost_target
= target
;
1831 target
= previous_edge
->mincost_target
;
1832 costpoint
= closest_point_in_routebox (&previous_edge
->cost_point
, rb
);
1834 (scale
[to_site_conflict
] *
1835 cost_to_point_on_layer (&costpoint
, &previous_edge
->cost_point
,
1836 previous_edge
->rb
->group
)) +
1837 (scale
[through_site_conflict
] *
1838 cost_to_point (&costpoint
, group
, &costpoint
,
1839 previous_edge
->rb
->group
));
1840 /* if the target is just this via away, then this via is cheaper */
1841 if (target
->group
== group
&&
1842 point_in_shrunk_box (target
, costpoint
.X
, costpoint
.Y
))
1843 d
-= AutoRouteParameters
.ViaCost
/ 2;
1845 CreateEdge (rb
, costpoint
.X
, costpoint
.Y
,
1846 previous_edge
->cost_to_point
+ d
,
1847 previous_edge
->mincost_target
, ALL
, targets
);
1849 ne
->flags
.is_via
= 1;
1850 ne
->flags
.via_conflict_level
= to_site_conflict
;
1851 assert (__edge_is_good (ne
));
1855 /* create "interior" edge for routing with conflicts */
1856 /* Presently once we "jump inside" the conflicting object
1857 * we consider it a routing highway to travel inside since
1858 * it will become available if the conflict is elliminated.
1859 * That is why we ignore the interior_edge argument.
1862 CreateEdgeWithConflicts (const BoxType
* interior_edge
,
1863 routebox_t
* container
, edge_t
* previous_edge
,
1864 cost_t cost_penalty_to_box
, rtree_t
* targets
)
1867 CheapPointType costpoint
;
1870 assert (interior_edge
&& container
&& previous_edge
&& targets
);
1871 assert (!container
->flags
.homeless
);
1872 assert (AutoRouteParameters
.with_conflicts
);
1873 assert (container
->flags
.touched
== 0);
1874 assert (previous_edge
->rb
->group
== container
->group
);
1875 /* use the caller's idea of what this box should be */
1877 CreateExpansionArea (interior_edge
, previous_edge
->rb
->group
,
1878 previous_edge
->rb
, true, previous_edge
);
1879 path_conflicts (rb
, container
, true); /* crucial! */
1881 closest_point_in_box (&previous_edge
->cost_point
, interior_edge
);
1883 cost_to_point_on_layer (&costpoint
, &previous_edge
->cost_point
,
1884 previous_edge
->rb
->group
);
1885 d
*= cost_penalty_to_box
;
1886 d
+= previous_edge
->cost_to_point
;
1887 ne
= CreateEdge (rb
, costpoint
.X
, costpoint
.Y
, d
, NULL
, ALL
, targets
);
1888 ne
->flags
.is_interior
= 1;
1889 assert (__edge_is_good (ne
));
1894 KillEdge (void *edge
)
1896 edge_t
*e
= (edge_t
*) edge
;
1898 if (e
->rb
->flags
.homeless
)
1899 RB_down_count (e
->rb
);
1900 if (e
->flags
.via_search
)
1901 mtsFreeWork (&e
->work
);
1906 DestroyEdge (edge_t
** e
)
1913 /* cost function for an edge. */
1915 edge_cost (const edge_t
* e
, const cost_t too_big
)
1917 cost_t penalty
= e
->cost_to_point
;
1918 if (e
->rb
->flags
.is_thermal
|| e
->rb
->type
== PLANE
)
1919 return penalty
; /* thermals are cheap */
1920 if (penalty
> too_big
)
1923 /* cost_to_routebox adds in our via correction, too. */
1925 cost_to_routebox (&e
->cost_point
, e
->rb
->group
, e
->mincost_target
);
1928 /* given an edge of a box, return a box containing exactly the points on that
1929 * edge. Note that the return box is treated as closed; that is, the bottom and
1930 * right "edges" consist of points (just barely) not in the (half-open) box. */
1932 edge_to_box (const routebox_t
* rb
, direction_t expand_dir
)
1934 BoxType b
= shrink_routebox (rb
);
1935 /* narrow box down to just the appropriate edge */
1959 BoxType left
, center
, right
;
1960 bool is_valid_left
, is_valid_center
, is_valid_right
;
1963 static struct broken_boxes
1964 break_box_edge (const BoxType
* original
, direction_t which_edge
,
1965 routebox_t
* breaker
)
1967 BoxType origbox
, breakbox
;
1968 struct broken_boxes result
;
1970 assert (original
&& breaker
);
1972 origbox
= *original
;
1973 breakbox
= bloat_routebox (breaker
);
1974 ROTATEBOX_TO_NORTH (origbox
, which_edge
);
1975 ROTATEBOX_TO_NORTH (breakbox
, which_edge
);
1976 result
.right
.Y1
= result
.center
.Y1
= result
.left
.Y1
= origbox
.Y1
;
1977 result
.right
.Y2
= result
.center
.Y2
= result
.left
.Y2
= origbox
.Y1
+ 1;
1978 /* validity of breaker is not important because the boxes are marked invalid */
1979 //assert (breakbox.X1 <= origbox.X2 && breakbox.X2 >= origbox.X1);
1980 /* left edge piece */
1981 result
.left
.X1
= origbox
.X1
;
1982 result
.left
.X2
= breakbox
.X1
;
1983 /* center (ie blocked) edge piece */
1984 result
.center
.X1
= MAX (breakbox
.X1
, origbox
.X1
);
1985 result
.center
.X2
= MIN (breakbox
.X2
, origbox
.X2
);
1986 /* right edge piece */
1987 result
.right
.X1
= breakbox
.X2
;
1988 result
.right
.X2
= origbox
.X2
;
1990 result
.is_valid_left
= (result
.left
.X1
< result
.left
.X2
);
1991 result
.is_valid_center
= (result
.center
.X1
< result
.center
.X2
);
1992 result
.is_valid_right
= (result
.right
.X1
< result
.right
.X2
);
1994 ROTATEBOX_FROM_NORTH (result
.left
, which_edge
);
1995 ROTATEBOX_FROM_NORTH (result
.center
, which_edge
);
1996 ROTATEBOX_FROM_NORTH (result
.right
, which_edge
);
2003 share_edge (const BoxType
* child
, const BoxType
* parent
)
2006 (child
->X1
== parent
->X2
|| child
->X2
== parent
->X1
||
2007 child
->Y1
== parent
->Y2
|| child
->Y2
== parent
->Y1
) &&
2008 ((parent
->X1
<= child
->X1
&& child
->X2
<= parent
->X2
) ||
2009 (parent
->Y1
<= child
->Y1
&& child
->Y2
<= parent
->Y2
));
2012 edge_intersect (const BoxType
* child
, const BoxType
* parent
)
2015 (child
->X1
<= parent
->X2
) && (child
->X2
>= parent
->X1
) &&
2016 (child
->Y1
<= parent
->Y2
) && (child
->Y2
>= parent
->Y1
);
2020 /* area is the expansion area, on layer group 'group'. 'parent' is the
2021 * immediately preceding expansion area, for backtracing. 'lastarea' is
2022 * the last expansion area created, we string these together in a loop
2023 * so we can remove them all easily at the end. */
2025 CreateExpansionArea (const BoxType
* area
, Cardinal group
,
2026 routebox_t
* parent
,
2027 bool relax_edge_requirements
, edge_t
* src_edge
)
2029 routebox_t
*rb
= (routebox_t
*) malloc (sizeof (*rb
));
2030 memset ((void *) rb
, 0, sizeof (*rb
));
2031 assert (area
&& parent
);
2032 init_const_box (rb
, area
->X1
, area
->Y1
, area
->X2
, area
->Y2
, 0);
2034 rb
->type
= EXPANSION_AREA
;
2035 /* should always share edge or overlap with parent */
2036 assert (relax_edge_requirements
? box_intersect (&rb
->sbox
, &parent
->sbox
)
2037 : share_edge (&rb
->sbox
, &parent
->sbox
));
2038 rb
->parent
.expansion_area
= route_parent (parent
);
2040 closest_point_in_box (&rb
->parent
.expansion_area
->cost_point
, area
);
2042 rb
->parent
.expansion_area
->cost
+
2043 cost_to_point_on_layer (&rb
->parent
.expansion_area
->cost_point
,
2044 &rb
->cost_point
, rb
->group
);
2045 assert (relax_edge_requirements
? edge_intersect (&rb
->sbox
, &parent
->sbox
)
2046 : share_edge (&rb
->sbox
, &parent
->sbox
));
2047 if (rb
->parent
.expansion_area
->flags
.homeless
)
2048 RB_up_count (rb
->parent
.expansion_area
);
2049 rb
->flags
.homeless
= 1;
2050 rb
->flags
.nobloat
= 1;
2051 rb
->style
= AutoRouteParameters
.style
;
2052 rb
->conflicts_with
= parent
->conflicts_with
;
2053 /* we will never link an EXPANSION_AREA into the nets because they
2054 * are *ONLY* used for path searching. No need to call InitLists ()
2056 rb
->came_from
= src_edge
->expand_dir
;
2057 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
2059 #endif /* ROUTE_DEBUG && DEBUG_SHOW_EXPANSION_BOXES */
2063 /*------ Expand ------*/
2067 routebox_t
*n
, *e
, *s
, *w
;
2068 BDimension keep
, bloat
;
2069 BoxType inflated
, orig
;
2073 /* test method for Expand()
2074 * this routebox potentially is a blocker limiting expansion
2075 * if this is so, we limit the inflate box so another exactly
2076 * like it wouldn't be seen. We do this while keep the inflated
2077 * box as large as possible.
2080 __Expand_this_rect (const BoxType
* box
, void *cl
)
2082 struct E_result
*res
= (struct E_result
*) cl
;
2083 routebox_t
*rb
= (routebox_t
*) box
;
2085 BDimension dn
, de
, ds
, dw
, bloat
;
2087 /* we don't see conflicts already encountered */
2088 if (rb
->flags
.touched
)
2091 /* The inflated box outer edges include its own
2092 * track width plus its own keepaway.
2094 * To check for intersection, we need to expand
2095 * anything with greater keepaway by its excess
2098 * If something has nobloat then we need to shrink
2099 * the inflated box back and see if it still touches.
2102 if (rb
->flags
.nobloat
)
2106 if (rbox
.X2
<= res
->inflated
.X1
+ bloat
||
2107 rbox
.X1
>= res
->inflated
.X2
- bloat
||
2108 rbox
.Y1
>= res
->inflated
.Y2
- bloat
||
2109 rbox
.Y2
<= res
->inflated
.Y1
+ bloat
)
2110 return 0; /* doesn't touch */
2114 if (rb
->style
->Keepaway
> res
->keep
)
2115 rbox
= bloat_box (&rb
->sbox
, rb
->style
->Keepaway
- res
->keep
);
2119 if (rbox
.X2
<= res
->inflated
.X1
|| rbox
.X1
>= res
->inflated
.X2
2120 || rbox
.Y1
>= res
->inflated
.Y2
|| rbox
.Y2
<= res
->inflated
.Y1
)
2121 return 0; /* doesn't touch */
2125 /* this is an intersecting box; it has to jump through a few more hoops */
2126 if (rb
== res
->parent
|| rb
->parent
.expansion_area
== res
->parent
)
2127 return 0; /* don't see what we came from */
2129 /* if we are expanding a source edge, don't let other sources
2130 * or their expansions stop us.
2133 if (res
->parent
->flags
.source
)
2134 if (rb
->flags
.source
2135 || (rb
->type
== EXPANSION_AREA
2136 && rb
->parent
.expansion_area
->flags
.source
))
2140 /* we ignore via expansion boxes because maybe its
2141 * cheaper to get there without the via through
2142 * the path we're exploring now.
2144 if (rb
->flags
.is_via
&& rb
->type
== EXPANSION_AREA
)
2147 if (rb
->type
== PLANE
) /* expanding inside a plane is not good */
2149 if (rbox
.X1
< res
->orig
.X1
&& rbox
.X2
> res
->orig
.X2
&&
2150 rbox
.Y1
< res
->orig
.Y1
&& rbox
.Y2
> res
->orig
.Y2
)
2152 res
->inflated
= bloat_box (&res
->orig
, res
->bloat
);
2156 /* calculate the distances from original box to this blocker */
2157 dn
= de
= ds
= dw
= 0;
2158 if (!(res
->done
& _NORTH
) && rbox
.Y1
<= res
->orig
.Y1
2159 && rbox
.Y2
> res
->inflated
.Y1
)
2160 dn
= res
->orig
.Y1
- rbox
.Y2
;
2161 if (!(res
->done
& _EAST
) && rbox
.X2
>= res
->orig
.X2
2162 && rbox
.X1
< res
->inflated
.X2
)
2163 de
= rbox
.X1
- res
->orig
.X2
;
2164 if (!(res
->done
& _SOUTH
) && rbox
.Y2
>= res
->orig
.Y2
2165 && rbox
.Y1
< res
->inflated
.Y2
)
2166 ds
= rbox
.Y1
- res
->orig
.Y2
;
2167 if (!(res
->done
& _WEST
) && rbox
.X1
<= res
->orig
.X1
2168 && rbox
.X2
> res
->inflated
.X1
)
2169 dw
= res
->orig
.X1
- rbox
.X2
;
2170 if (dn
<= 0 && de
<= 0 && ds
<= 0 && dw
<= 0)
2172 /* now shrink the inflated box to the largest blocking direction */
2173 if (dn
>= de
&& dn
>= ds
&& dn
>= dw
)
2175 res
->inflated
.Y1
= rbox
.Y2
- bloat
;
2178 else if (de
>= ds
&& de
>= dw
)
2180 res
->inflated
.X2
= rbox
.X1
+ bloat
;
2185 res
->inflated
.Y2
= rbox
.Y1
+ bloat
;
2190 res
->inflated
.X1
= rbox
.X2
- bloat
;
2197 boink_box (routebox_t
* rb
, struct E_result
*res
, direction_t dir
)
2200 if (rb
->style
->Keepaway
> res
->keep
)
2201 bloat
= res
->keep
- rb
->style
->Keepaway
;
2204 if (rb
->flags
.nobloat
)
2210 if (rb
->sbox
.X2
<= res
->inflated
.X1
+ bloat
2211 || rb
->sbox
.X1
>= res
->inflated
.X2
- bloat
)
2216 if (rb
->sbox
.Y1
>= res
->inflated
.Y2
- bloat
2217 || rb
->sbox
.Y2
<= res
->inflated
.Y1
+ bloat
)
2227 /* main Expand routine.
2229 * The expansion probe edge includes the keepaway and half thickness
2230 * as the search is performed in order to see everything relevant.
2231 * The result is backed off by this amount before being returned.
2232 * Targets (and other no-bloat routeboxes) go all the way to touching.
2233 * This is accomplished by backing off the probe edge when checking
2234 * for touch against such an object. Usually the expanding edge
2235 * bumps into neighboring pins on the same device that require a
2236 * keepaway, preventing seeing a target immediately. Rather than await
2237 * another expansion to actually touch the target, the edge breaker code
2238 * looks past the keepaway to see these targets even though they
2239 * weren't actually touched in the expansion.
2242 Expand (rtree_t
* rtree
, edge_t
* e
, const BoxType
* box
)
2244 static struct E_result ans
;
2245 int noshrink
; /* bit field of which edges to not shrink */
2247 ans
.bloat
= AutoRouteParameters
.bloat
;
2249 ans
.n
= ans
.e
= ans
.s
= ans
.w
= NULL
;
2251 /* the inflated box must be bloated in all directions that it might
2252 * hit something in order to guarantee that we see object in the
2253 * tree it might hit. The tree holds objects bloated by their own
2254 * keepaway so we are guaranteed to honor that.
2256 switch (e
->expand_dir
)
2259 ans
.inflated
.X1
= (e
->rb
->came_from
== EAST
? ans
.orig
.X1
: 0);
2260 ans
.inflated
.Y1
= (e
->rb
->came_from
== SOUTH
? ans
.orig
.Y1
: 0);
2262 (e
->rb
->came_from
== WEST
? ans
.orig
.X2
: PCB
->MaxWidth
);
2264 (e
->rb
->came_from
== NORTH
? ans
.orig
.Y2
: PCB
->MaxHeight
);
2265 if (e
->rb
->came_from
== NORTH
)
2266 ans
.done
= noshrink
= _SOUTH
;
2267 else if (e
->rb
->came_from
== EAST
)
2268 ans
.done
= noshrink
= _WEST
;
2269 else if (e
->rb
->came_from
== SOUTH
)
2270 ans
.done
= noshrink
= _NORTH
;
2271 else if (e
->rb
->came_from
== WEST
)
2272 ans
.done
= noshrink
= _EAST
;
2274 ans
.done
= noshrink
= 0;
2277 ans
.done
= _SOUTH
+ _EAST
+ _WEST
;
2279 ans
.inflated
.X1
= box
->X1
- ans
.bloat
;
2280 ans
.inflated
.X2
= box
->X2
+ ans
.bloat
;
2281 ans
.inflated
.Y2
= box
->Y2
;
2282 ans
.inflated
.Y1
= 0; /* far north */
2285 ans
.done
= _SOUTH
+ _WEST
;
2287 ans
.inflated
.X1
= box
->X1
- ans
.bloat
;
2288 ans
.inflated
.X2
= PCB
->MaxWidth
;
2289 ans
.inflated
.Y2
= box
->Y2
+ ans
.bloat
;
2290 ans
.inflated
.Y1
= 0;
2293 ans
.done
= _NORTH
+ _SOUTH
+ _WEST
;
2295 ans
.inflated
.Y1
= box
->Y1
- ans
.bloat
;
2296 ans
.inflated
.Y2
= box
->Y2
+ ans
.bloat
;
2297 ans
.inflated
.X1
= box
->X1
;
2298 ans
.inflated
.X2
= PCB
->MaxWidth
;
2301 ans
.done
= _NORTH
+ _WEST
;
2303 ans
.inflated
.X1
= box
->X1
- ans
.bloat
;
2304 ans
.inflated
.X2
= PCB
->MaxWidth
;
2305 ans
.inflated
.Y2
= PCB
->MaxHeight
;
2306 ans
.inflated
.Y1
= box
->Y1
- ans
.bloat
;
2309 ans
.done
= _NORTH
+ _EAST
+ _WEST
;
2311 ans
.inflated
.X1
= box
->X1
- ans
.bloat
;
2312 ans
.inflated
.X2
= box
->X2
+ ans
.bloat
;
2313 ans
.inflated
.Y1
= box
->Y1
;
2314 ans
.inflated
.Y2
= PCB
->MaxHeight
;
2317 ans
.done
= _NORTH
+ _EAST
;
2319 ans
.inflated
.X1
= 0;
2320 ans
.inflated
.X2
= box
->X2
+ ans
.bloat
;
2321 ans
.inflated
.Y2
= PCB
->MaxHeight
;
2322 ans
.inflated
.Y1
= box
->Y1
- ans
.bloat
;
2325 ans
.done
= _NORTH
+ _SOUTH
+ _EAST
;
2327 ans
.inflated
.Y1
= box
->Y1
- ans
.bloat
;
2328 ans
.inflated
.Y2
= box
->Y2
+ ans
.bloat
;
2329 ans
.inflated
.X1
= 0;
2330 ans
.inflated
.X2
= box
->X2
;
2333 ans
.done
= _SOUTH
+ _EAST
;
2335 ans
.inflated
.X1
= 0;
2336 ans
.inflated
.X2
= box
->X2
+ ans
.bloat
;
2337 ans
.inflated
.Y2
= box
->Y2
+ ans
.bloat
;
2338 ans
.inflated
.Y1
= 0;
2341 noshrink
= ans
.done
= 0;
2344 ans
.keep
= e
->rb
->style
->Keepaway
;
2345 ans
.parent
= nonhomeless_parent (e
->rb
);
2346 r_search (rtree
, &ans
.inflated
, NULL
, __Expand_this_rect
, &ans
);
2347 /* because the overlaping boxes are found in random order, some blockers
2348 * may have limited edges prematurely, so we check if the blockers realy
2349 * are blocking, and make another try if not
2351 if (ans
.n
&& !boink_box (ans
.n
, &ans
, NORTH
))
2352 ans
.inflated
.Y1
= 0;
2355 if (ans
.e
&& !boink_box (ans
.e
, &ans
, EAST
))
2356 ans
.inflated
.X2
= PCB
->MaxWidth
;
2359 if (ans
.s
&& !boink_box (ans
.s
, &ans
, SOUTH
))
2360 ans
.inflated
.Y2
= PCB
->MaxHeight
;
2363 if (ans
.w
&& !boink_box (ans
.w
, &ans
, WEST
))
2364 ans
.inflated
.X1
= 0;
2367 if (ans
.done
!= _NORTH
+ _EAST
+ _SOUTH
+ _WEST
)
2369 r_search (rtree
, &ans
.inflated
, NULL
, __Expand_this_rect
, &ans
);
2371 if ((noshrink
& _NORTH
) == 0)
2372 ans
.inflated
.Y1
+= ans
.bloat
;
2373 if ((noshrink
& _EAST
) == 0)
2374 ans
.inflated
.X2
-= ans
.bloat
;
2375 if ((noshrink
& _SOUTH
) == 0)
2376 ans
.inflated
.Y2
-= ans
.bloat
;
2377 if ((noshrink
& _WEST
) == 0)
2378 ans
.inflated
.X1
+= ans
.bloat
;
2382 /* blocker_to_heap puts the blockers into a heap so they
2383 * can be retrieved in clockwise order. If a blocker
2384 * is also a target, it gets put into the vector too.
2385 * It returns 1 for any fixed blocker that is not part
2386 * of this net and zero otherwise.
2389 blocker_to_heap (heap_t
* heap
, routebox_t
* rb
,
2390 BoxType
* box
, direction_t dir
)
2392 BoxType b
= rb
->sbox
;
2393 if (rb
->style
->Keepaway
> AutoRouteParameters
.style
->Keepaway
)
2396 rb
->style
->Keepaway
- AutoRouteParameters
.style
->Keepaway
);
2397 b
= clip_box (&b
, box
);
2398 assert (box_is_good (&b
));
2399 /* we want to look at the blockers clockwise around the box */
2402 /* we need to use the other coordinate fraction to resolve
2403 * ties since we want the shorter of the furthest
2407 heap_insert (heap
, b
.X1
- b
.X1
/ (b
.X2
+ 1.0), rb
);
2410 heap_insert (heap
, b
.Y1
- b
.Y1
/ (b
.Y2
+ 1.0), rb
);
2413 heap_insert (heap
, -(b
.X2
+ b
.X1
/ (b
.X2
+ 1.0)), rb
);
2416 heap_insert (heap
, -(b
.Y2
+ b
.Y1
/ (b
.Y2
+ 1.0)), rb
);
2421 if (rb
->flags
.fixed
&& !rb
->flags
.target
&& !rb
->flags
.source
)
2426 /* this creates an EXPANSION_AREA to bridge small gaps or,
2427 * (more commonly) create a supper-thin box to provide a
2428 * home for an expansion edge.
2431 CreateBridge (const BoxType
* area
, routebox_t
* parent
, direction_t dir
)
2433 routebox_t
*rb
= (routebox_t
*) malloc (sizeof (*rb
));
2434 memset ((void *) rb
, 0, sizeof (*rb
));
2435 assert (area
&& parent
);
2436 init_const_box (rb
, area
->X1
, area
->Y1
, area
->X2
, area
->Y2
, 0);
2437 rb
->group
= parent
->group
;
2438 rb
->type
= EXPANSION_AREA
;
2439 rb
->came_from
= dir
;
2440 rb
->cost_point
= closest_point_in_box (&parent
->cost_point
, area
);
2441 rb
->cost
= parent
->cost
+ cost_to_point_on_layer (&parent
->cost_point
,
2444 rb
->parent
.expansion_area
= route_parent (parent
);
2445 if (rb
->parent
.expansion_area
->flags
.homeless
)
2446 RB_up_count (rb
->parent
.expansion_area
);
2447 rb
->flags
.homeless
= 1;
2448 rb
->flags
.nobloat
= 1;
2449 rb
->style
= parent
->style
;
2450 rb
->conflicts_with
= parent
->conflicts_with
;
2451 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EDGES)
2457 /* moveable_edge prepares the new search edges based on the
2458 * starting box, direction and blocker if any.
2461 moveable_edge (vector_t
* result
, const BoxType
* box
, direction_t dir
,
2463 routebox_t
* blocker
, edge_t
* e
, rtree_t
* targets
,
2464 struct routeone_state
*s
, rtree_t
* tree
, vector_t
* area_vec
)
2467 assert (box_is_good (box
));
2469 /* for the cardinal directions, move the box to overlap the
2470 * the parent by 1 unit. Corner expansions overlap more
2471 * and their starting boxes are pre-prepared.
2472 * Check if anything is headed off the board edges
2481 if (b
.Y1
<= AutoRouteParameters
.bloat
)
2482 return; /* off board edge */
2487 if (b
.X2
>= PCB
->MaxWidth
- AutoRouteParameters
.bloat
)
2488 return; /* off board edge */
2493 if (b
.Y2
>= PCB
->MaxHeight
- AutoRouteParameters
.bloat
)
2494 return; /* off board edge */
2499 if (b
.X1
<= AutoRouteParameters
.bloat
)
2500 return; /* off board edge */
2503 if (b
.Y1
<= AutoRouteParameters
.bloat
+ 1
2504 && b
.X2
>= PCB
->MaxWidth
- AutoRouteParameters
.bloat
- 1)
2505 return; /* off board edge */
2506 if (b
.Y1
<= AutoRouteParameters
.bloat
+ 1)
2507 dir
= EAST
; /* north off board edge */
2508 if (b
.X2
>= PCB
->MaxWidth
- AutoRouteParameters
.bloat
- 1)
2509 dir
= NORTH
; /* east off board edge */
2512 if (b
.Y2
>= PCB
->MaxHeight
- AutoRouteParameters
.bloat
- 1
2513 && b
.X2
>= PCB
->MaxWidth
- AutoRouteParameters
.bloat
- 1)
2514 return; /* off board edge */
2515 if (b
.Y2
>= PCB
->MaxHeight
- AutoRouteParameters
.bloat
- 1)
2516 dir
= EAST
; /* south off board edge */
2517 if (b
.X2
>= PCB
->MaxWidth
- AutoRouteParameters
.bloat
- 1)
2518 dir
= SOUTH
; /* east off board edge */
2521 if (b
.Y2
>= PCB
->MaxHeight
- AutoRouteParameters
.bloat
- 1
2522 && b
.X1
<= AutoRouteParameters
.bloat
+ 1)
2523 return; /* off board edge */
2524 if (b
.Y2
>= PCB
->MaxHeight
- AutoRouteParameters
.bloat
- 1)
2525 dir
= WEST
; /* south off board edge */
2526 if (b
.X1
<= AutoRouteParameters
.bloat
+ 1)
2527 dir
= SOUTH
; /* west off board edge */
2530 if (b
.Y1
<= AutoRouteParameters
.bloat
+ 1
2531 && b
.X1
<= AutoRouteParameters
.bloat
+ 1)
2532 return; /* off board edge */
2533 if (b
.Y1
<= AutoRouteParameters
.bloat
+ 1)
2534 dir
= WEST
; /* north off board edge */
2535 if (b
.X1
<= AutoRouteParameters
.bloat
+ 1)
2536 dir
= NORTH
; /* west off board edge */
2543 routebox_t
*nrb
= CreateBridge (&b
, rb
, dir
);
2544 /* move the cost point in corner expansions
2545 * these boxes are bigger, so move close to the target
2547 if (dir
== NE
|| dir
== SE
|| dir
== SW
|| dir
== NW
)
2551 closest_point_in_box (&nrb
->cost_point
, &e
->mincost_target
->sbox
);
2552 p
= closest_point_in_box (&p
, &b
);
2553 nrb
->cost
+= cost_to_point_on_layer (&p
, &nrb
->cost_point
,
2555 nrb
->cost_point
= p
;
2557 ne
= CreateEdge (nrb
, nrb
->cost_point
.X
, nrb
->cost_point
.Y
,
2558 nrb
->cost
, NULL
, dir
, targets
);
2559 vector_append (result
, ne
);
2561 else if (AutoRouteParameters
.with_conflicts
&& !blocker
->flags
.target
2562 && !blocker
->flags
.fixed
&& !blocker
->flags
.touched
&&
2563 !blocker
->flags
.source
&& blocker
->type
!= EXPANSION_AREA
)
2567 /* make a bridge to the edge of the blocker
2568 * in all directions from there
2573 b
.Y1
= blocker
->sbox
.Y2
- 1;
2576 b
.X2
= blocker
->sbox
.X1
+ 1;
2579 b
.Y2
= blocker
->sbox
.Y1
+ 1;
2582 b
.X1
= blocker
->sbox
.X2
- 1;
2587 if (!box_is_good (&b
))
2588 return; /* how did this happen ? */
2589 nrb
= CreateBridge (&b
, rb
, dir
);
2590 r_insert_entry (tree
, &nrb
->box
, 1);
2591 vector_append (area_vec
, nrb
);
2592 nrb
->flags
.homeless
= 0; /* not homeless any more */
2593 /* mark this one as conflicted */
2594 path_conflicts (nrb
, blocker
, true);
2595 /* and make an expansion edge */
2597 closest_point_in_box (&nrb
->cost_point
, &blocker
->sbox
);
2599 cost_to_point_on_layer (&nrb
->parent
.expansion_area
->cost_point
,
2601 nrb
->group
) * CONFLICT_PENALTY (blocker
);
2603 ne
= CreateEdge (nrb
, nrb
->cost_point
.X
, nrb
->cost_point
.Y
, nrb
->cost
,
2604 NULL
, ALL
, targets
);
2605 ne
->flags
.is_interior
= 1;
2606 vector_append (result
, ne
);
2609 else if (blocker
->type
== EXPANSION_AREA
)
2611 if (blocker
->cost
< rb
->cost
|| blocker
->cost
<= rb
->cost
+
2612 cost_to_point_on_layer (&blocker
->cost_point
, &rb
->cost_point
,
2615 if (blocker
->conflicts_with
|| rb
->conflicts_with
)
2617 /* does the blocker overlap this routebox ?? */
2618 /* does this re-parenting operation leave a memory leak? */
2619 if (blocker
->parent
.expansion_area
->flags
.homeless
)
2620 RB_down_count (blocker
->parent
.expansion_area
);
2621 blocker
->parent
.expansion_area
= rb
;
2625 else if (blocker
->flags
.target
)
2629 b
= bloat_box (&b
, 1);
2630 if (!box_intersect (&b
, &blocker
->sbox
))
2632 /* if the expansion edge stopped before touching, expand the bridge */
2636 b
.Y1
-= AutoRouteParameters
.bloat
+ 1;
2639 b
.X2
+= AutoRouteParameters
.bloat
+ 1;
2642 b
.Y2
+= AutoRouteParameters
.bloat
+ 1;
2645 b
.X1
-= AutoRouteParameters
.bloat
+ 1;
2651 assert (box_intersect (&b
, &blocker
->sbox
));
2652 b
= shrink_box (&b
, 1);
2653 nrb
= CreateBridge (&b
, rb
, dir
);
2654 r_insert_entry (tree
, &nrb
->box
, 1);
2655 vector_append (area_vec
, nrb
);
2656 nrb
->flags
.homeless
= 0; /* not homeless any more */
2657 ne
= CreateEdge (nrb
, nrb
->cost_point
.X
, nrb
->cost_point
.Y
,
2658 nrb
->cost
, blocker
, dir
, NULL
);
2659 best_path_candidate (s
, ne
, blocker
);
2674 __GatherBlockers (const BoxType
* box
, void *cl
)
2676 routebox_t
*rb
= (routebox_t
*) box
;
2677 struct break_info
*bi
= (struct break_info
*) cl
;
2680 if (bi
->parent
== rb
|| rb
->flags
.touched
||
2681 bi
->parent
->parent
.expansion_area
== rb
)
2683 if (rb
->flags
.source
&& bi
->ignore_source
)
2686 if (rb
->style
->Keepaway
> AutoRouteParameters
.style
->Keepaway
)
2689 rb
->style
->Keepaway
- AutoRouteParameters
.style
->Keepaway
);
2690 if (b
.X2
<= bi
->box
.X1
|| b
.X1
>= bi
->box
.X2
2691 || b
.Y1
>= bi
->box
.Y2
|| b
.Y2
<= bi
->box
.Y1
)
2693 return blocker_to_heap (bi
->heap
, rb
, &bi
->box
, bi
->dir
);
2696 /* shrink the box to the last limit for the previous direction,
2697 * i.e. if dir is SOUTH, then this means fixing up an EAST leftover
2698 * edge, which would be the southern most edge for that example.
2700 static inline BoxType
2701 previous_edge (LocationType last
, direction_t i
, const BoxType
* b
)
2716 Message ("previous edge bogus direction!");
2722 /* Break all the edges of the box that need breaking, handling
2723 * targets as they are found, and putting any moveable edges
2724 * in the return vector.
2727 BreakManyEdges (struct routeone_state
* s
, rtree_t
* targets
, rtree_t
* tree
,
2728 vector_t
* area_vec
, struct E_result
* ans
, routebox_t
* rb
,
2731 struct break_info bi
;
2734 LocationType first
, last
;
2739 edges
= vector_create ();
2740 bi
.ignore_source
= rb
->parent
.expansion_area
->flags
.source
;
2742 /* we add 2 to the bloat.
2743 * 1 will get us to the actual blocker that Expand() hit
2744 * but 1 more is needed because the new expansion edges
2745 * move out by 1 so they don't overlap their parents
2746 * this extra expansion could "trap" the edge if
2747 * there is a blocker 2 units from the original rb,
2748 * it is 1 unit from the new expansion edge which
2749 * would prevent expansion. So we want to break the
2750 * edge on it now to avoid the trap.
2753 bloat
= AutoRouteParameters
.bloat
+ 2;
2754 /* for corner expansion, we need to have a fake blocker
2755 * to prevent expansion back where we came from since
2756 * we still need to break portions of all 4 edges
2758 if (e
->expand_dir
== NE
|| e
->expand_dir
== SE
||
2759 e
->expand_dir
== SW
|| e
->expand_dir
== NW
)
2761 BoxType
*fb
= (BoxType
*) & fake
.sbox
;
2762 memset (&fake
, 0, sizeof (fake
));
2764 fake
.flags
.fixed
= 1; /* this stops expansion there */
2766 fake
.style
= AutoRouteParameters
.style
;
2768 /* the routbox_is_good checker wants a lot more! */
2769 fake
.flags
.inited
= 1;
2770 fb
= (BoxType
*) & fake
.box
;
2772 fake
.same_net
.next
= fake
.same_net
.prev
= &fake
;
2773 fake
.same_subnet
.next
= fake
.same_subnet
.prev
= &fake
;
2774 fake
.original_subnet
.next
= fake
.original_subnet
.prev
= &fake
;
2775 fake
.different_net
.next
= fake
.different_net
.prev
= &fake
;
2778 /* gather all of the blockers in heaps so they can be accessed
2779 * in clockwise order, which allows finding corners that can
2782 for (dir
= NORTH
; dir
<= WEST
; dir
++)
2784 /* don't break the edge we came from */
2785 if (e
->expand_dir
!= ((dir
+ 2) % 4))
2787 heap
[dir
] = heap_create ();
2788 bi
.box
= bloat_box (&rb
->sbox
, bloat
);
2789 bi
.heap
= heap
[dir
];
2791 /* convert to edge */
2795 bi
.box
.Y2
= bi
.box
.Y1
+ bloat
+ 1;
2796 /* for corner expansion, block the start edges and
2797 * limit the blocker search to only the new edge segment
2799 if (e
->expand_dir
== SE
|| e
->expand_dir
== SW
)
2800 blocker_to_heap (heap
[dir
], &fake
, &bi
.box
, dir
);
2801 if (e
->expand_dir
== SE
)
2802 bi
.box
.X1
= e
->rb
->sbox
.X2
;
2803 if (e
->expand_dir
== SW
)
2804 bi
.box
.X2
= e
->rb
->sbox
.X1
;
2805 rb
->n
= r_search (tree
, &bi
.box
, NULL
, __GatherBlockers
, &bi
);
2808 bi
.box
.X1
= bi
.box
.X2
- bloat
- 1;
2809 /* corner, same as above */
2810 if (e
->expand_dir
== SW
|| e
->expand_dir
== NW
)
2811 blocker_to_heap (heap
[dir
], &fake
, &bi
.box
, dir
);
2812 if (e
->expand_dir
== SW
)
2813 bi
.box
.Y1
= e
->rb
->sbox
.Y2
;
2814 if (e
->expand_dir
== NW
)
2815 bi
.box
.Y2
= e
->rb
->sbox
.Y1
;
2816 rb
->e
= r_search (tree
, &bi
.box
, NULL
, __GatherBlockers
, &bi
);
2819 bi
.box
.Y1
= bi
.box
.Y2
- bloat
- 1;
2820 /* corner, same as above */
2821 if (e
->expand_dir
== NE
|| e
->expand_dir
== NW
)
2822 blocker_to_heap (heap
[dir
], &fake
, &bi
.box
, dir
);
2823 if (e
->expand_dir
== NE
)
2824 bi
.box
.X1
= e
->rb
->sbox
.X2
;
2825 if (e
->expand_dir
== NW
)
2826 bi
.box
.X2
= e
->rb
->sbox
.X1
;
2827 rb
->s
= r_search (tree
, &bi
.box
, NULL
, __GatherBlockers
, &bi
);
2830 bi
.box
.X2
= bi
.box
.X1
+ bloat
+ 1;
2831 /* corner, same as above */
2832 if (e
->expand_dir
== NE
|| e
->expand_dir
== SE
)
2833 blocker_to_heap (heap
[dir
], &fake
, &bi
.box
, dir
);
2834 if (e
->expand_dir
== SE
)
2835 bi
.box
.Y1
= e
->rb
->sbox
.Y2
;
2836 if (e
->expand_dir
== NE
)
2837 bi
.box
.Y2
= e
->rb
->sbox
.Y1
;
2838 rb
->w
= r_search (tree
, &bi
.box
, NULL
, __GatherBlockers
, &bi
);
2849 (rb
->n
+ rb
->e
+ rb
->s
+
2850 rb
->w
) * AutoRouteParameters
.CongestionPenalty
/ box_area (rb
->sbox
);
2852 /* now handle the blockers:
2853 * Go around the expansion area clockwise (North->East->South->West)
2854 * pulling blockers from the heap (which makes them come out in the right
2855 * order). Break the edges on the blocker and make the segments and corners
2856 * moveable as possible.
2859 for (dir
= NORTH
; dir
<= WEST
; dir
++)
2861 if (heap
[dir
] && !heap_is_empty (heap
[dir
]))
2863 /* pull the very first one out of the heap outside of the
2864 * heap loop because it is special; it can be part of a corner
2866 routebox_t
*blk
= (routebox_t
*) heap_remove_smallest (heap
[dir
]);
2867 BoxType b
= rb
->sbox
;
2868 struct broken_boxes broke
= break_box_edge (&b
, dir
, blk
);
2869 if (broke
.is_valid_left
)
2871 /* if last > 0, then the previous edge had a segment
2872 * joining this one, so it forms a valid corner expansion
2876 /* make a corner expansion */
2881 /* possible NE expansion */
2883 db
.Y2
= MIN (db
.Y2
, broke
.left
.Y2
);
2886 /* possible SE expansion */
2888 db
.X1
= MAX (db
.X1
, broke
.left
.X1
);
2891 /* possible SW expansion */
2893 db
.Y1
= MAX (db
.Y1
, broke
.left
.Y1
);
2899 moveable_edge (edges
, &db
, dir
+ 3, rb
, NULL
, e
, targets
,
2902 else if (dir
== NORTH
) /* north is start, so nothing "before" it */
2904 /* save for a possible corner once we've
2905 * finished circling the box
2907 first
= MAX (b
.X1
, broke
.left
.X2
);
2911 /* this is just a boring straight expansion
2912 * since the orthogonal segment was blocked
2914 moveable_edge (edges
, &broke
.left
, dir
, rb
, NULL
, e
,
2915 targets
, s
, NULL
, NULL
);
2917 } /* broke.is_valid_left */
2920 /* if the last one didn't become a corner,
2921 * we still want to expand it straight out
2922 * in the direction of the previous edge,
2923 * which it belongs to.
2925 BoxType db
= previous_edge (last
, dir
, &rb
->sbox
);
2926 moveable_edge (edges
, &db
, dir
- 1, rb
, NULL
, e
, targets
, s
,
2929 if (broke
.is_valid_center
&& !blk
->flags
.source
)
2930 moveable_edge (edges
, &broke
.center
, dir
, rb
, blk
, e
, targets
, s
,
2932 /* this is the heap extraction loop. We break out
2933 * if there's nothing left in the heap, but if we * are blocked all the way to the far edge, we can
2934 * just leave stuff in the heap when it is destroyed
2936 while (broke
.is_valid_right
)
2938 /* move the box edge to the next potential free point */
2942 last
= b
.X1
= MAX (broke
.right
.X1
, b
.X1
);
2945 last
= b
.Y1
= MAX (broke
.right
.Y1
, b
.Y1
);
2948 last
= b
.X2
= MIN (broke
.right
.X2
, b
.X2
);
2951 last
= b
.Y2
= MIN (broke
.right
.Y2
, b
.Y2
);
2956 if (heap_is_empty (heap
[dir
]))
2958 blk
= heap_remove_smallest (heap
[dir
]);
2959 broke
= break_box_edge (&b
, dir
, blk
);
2960 if (broke
.is_valid_left
)
2961 moveable_edge (edges
, &broke
.left
, dir
, rb
, NULL
, e
, targets
,
2963 if (broke
.is_valid_center
&& !blk
->flags
.source
)
2964 moveable_edge (edges
, &broke
.center
, dir
, rb
, blk
, e
, targets
,
2967 if (!broke
.is_valid_right
)
2970 else /* if (heap[dir]) */
2972 /* nothing touched this edge! Expand the whole edge unless
2973 * (1) it hit the board edge or (2) was the source of our expansion
2975 * for this case (of hitting nothing) we give up trying for corner
2976 * expansions because it is likely that they're not possible anyway
2978 if ((e
->expand_dir
== ALL
? e
->rb
->came_from
: e
->expand_dir
) !=
2981 /* ok, we are not going back on ourselves, and the whole edge seems free */
2982 moveable_edge (edges
, &rb
->sbox
, dir
, rb
, NULL
, e
, targets
, s
,
2988 /* expand the leftover from the prior direction */
2989 BoxType db
= previous_edge (last
, dir
, &rb
->sbox
);
2990 moveable_edge (edges
, &db
, dir
- 1, rb
, NULL
, e
, targets
, s
,
2996 /* finally, check for the NW corner now that we've come full circle */
2997 if (first
> 0 && last
> 0)
2999 BoxType db
= rb
->sbox
;
3002 moveable_edge (edges
, &db
, NW
, rb
, NULL
, e
, targets
, s
, NULL
, NULL
);
3008 BoxType db
= rb
->sbox
;
3010 moveable_edge (edges
, &db
, NORTH
, rb
, NULL
, e
, targets
, s
, NULL
,
3015 BoxType db
= rb
->sbox
;
3017 moveable_edge (edges
, &db
, WEST
, rb
, NULL
, e
, targets
, s
, NULL
,
3021 /* done with all expansion edges of this box */
3022 for (dir
= NORTH
; dir
<= WEST
; dir
++)
3025 heap_destroy (&heap
[dir
]);
3031 rb_source (routebox_t
* rb
)
3033 while (rb
&& !rb
->flags
.source
)
3035 assert (rb
->type
== EXPANSION_AREA
);
3036 rb
= rb
->parent
.expansion_area
;
3047 routebox_t
*intersect
;
3052 foib_rect_in_reg (const BoxType
* box
, void *cl
)
3054 struct foib_info
*foib
= (struct foib_info
*) cl
;
3056 routebox_t
*rb
= (routebox_t
*) box
;
3057 if (rb
->flags
.touched
)
3059 // if (rb->type == EXPANSION_AREA && !rb->flags.is_via)
3061 rbox
= bloat_routebox (rb
);
3062 if (!box_intersect (&rbox
, foib
->box
))
3064 /* this is an intersector! */
3065 foib
->intersect
= (routebox_t
*) box
;
3066 longjmp (foib
->env
, 1); /* skip to the end! */
3070 FindOneInBox (rtree_t
* rtree
, routebox_t
* rb
)
3072 struct foib_info foib
;
3077 foib
.intersect
= NULL
;
3079 if (setjmp (foib
.env
) == 0)
3080 r_search (rtree
, &r
, NULL
, foib_rect_in_reg
, &foib
);
3081 return foib
.intersect
;
3091 ftherm_rect_in_reg (const BoxType
* box
, void *cl
)
3093 routebox_t
*rbox
= (routebox_t
*) box
;
3094 struct therm_info
*ti
= (struct therm_info
*) cl
;
3097 if (rbox
->type
!= PIN
&& rbox
->type
!= VIA
&& rbox
->type
!= VIA_SHADOW
)
3099 if (rbox
->group
!= ti
->plane
->group
)
3102 sb
= shrink_routebox (rbox
);
3106 sq
= shrink_box (&ti
->query
, rbox
->parent
.pin
->Thickness
);
3107 if (!box_intersect (&sb
, &sq
))
3109 sb
.X1
= rbox
->parent
.pin
->X
;
3110 sb
.Y1
= rbox
->parent
.pin
->Y
;
3113 if (rbox
->flags
.fixed
)
3115 sq
= shrink_box (&ti
->query
, rbox
->parent
.via
->Thickness
);
3116 sb
.X1
= rbox
->parent
.pin
->X
;
3117 sb
.Y1
= rbox
->parent
.pin
->Y
;
3121 sq
= shrink_box (&ti
->query
, rbox
->style
->Diameter
);
3122 sb
.X1
= CENTER_X (sb
);
3123 sb
.Y1
= CENTER_Y (sb
);
3125 if (!box_intersect (&sb
, &sq
))
3129 sq
= shrink_box (&ti
->query
, rbox
->style
->Diameter
);
3130 if (!box_intersect (&sb
, &sq
))
3132 sb
.X1
= CENTER_X (sb
);
3133 sb
.Y1
= CENTER_Y (sb
);
3139 longjmp (ti
->env
, 1);
3143 /* check for a pin or via target that a polygon can just use a thermal to connect to */
3145 FindThermable (rtree_t
* rtree
, routebox_t
* rb
)
3147 struct therm_info info
;
3150 info
.query
= shrink_routebox (rb
);
3152 if (setjmp (info
.env
) == 0)
3154 r_search (rtree
, &info
.query
, NULL
, ftherm_rect_in_reg
, &info
);
3160 /*--------------------------------------------------------------------
3161 * Route-tracing code: once we've got a path of expansion boxes, trace
3162 * a line through them to actually create the connection.
3165 RD_DrawThermal (routedata_t
* rd
, LocationType X
, LocationType Y
,
3166 Cardinal group
, Cardinal layer
, routebox_t
* subnet
,
3170 rb
= (routebox_t
*) malloc (sizeof (*rb
));
3171 memset ((void *) rb
, 0, sizeof (*rb
));
3172 init_const_box (rb
, X
, Y
, X
+ 1, Y
+ 1, 0);
3175 rb
->flags
.fixed
= 0;
3176 rb
->flags
.is_bad
= is_bad
;
3177 rb
->flags
.is_odd
= AutoRouteParameters
.is_odd
;
3178 rb
->flags
.circular
= 0;
3179 rb
->style
= AutoRouteParameters
.style
;
3182 MergeNets (rb
, subnet
, NET
);
3183 MergeNets (rb
, subnet
, SUBNET
);
3184 /* add it to the r-tree, this may be the whole route! */
3185 r_insert_entry (rd
->layergrouptree
[rb
->group
], &rb
->box
, 1);
3186 rb
->flags
.homeless
= 0;
3190 RD_DrawVia (routedata_t
* rd
, LocationType X
, LocationType Y
,
3191 BDimension radius
, routebox_t
* subnet
, bool is_bad
)
3193 routebox_t
*rb
, *first_via
= NULL
;
3195 int ka
= AutoRouteParameters
.style
->Keepaway
;
3197 /* a via cuts through every layer group */
3198 for (i
= 0; i
< max_layer
; i
++)
3200 if (!is_layer_group_active
[i
])
3202 rb
= (routebox_t
*) malloc (sizeof (*rb
));
3203 memset ((void *) rb
, 0, sizeof (*rb
));
3205 /*X1 */ X
- radius
, /*Y1 */ Y
- radius
,
3206 /*X2 */ X
+ radius
+ 1, /*Y2 */ Y
+ radius
+ 1, ka
);
3208 rb
->flags
.fixed
= 0; /* indicates that not on PCB yet */
3209 rb
->flags
.is_odd
= AutoRouteParameters
.is_odd
;
3210 rb
->flags
.is_bad
= is_bad
;
3211 rb
->came_from
= ALL
;
3212 rb
->flags
.circular
= true;
3213 rb
->style
= AutoRouteParameters
.style
;
3214 rb
->pass
= AutoRouteParameters
.pass
;
3215 if (first_via
== NULL
)
3218 rb
->parent
.via
= NULL
; /* indicates that not on PCB yet */
3220 /* only add the first via to mtspace, not the shadows too */
3221 mtspace_add (rd
->mtspace
, &rb
->box
, rb
->flags
.is_odd
? ODD
: EVEN
,
3222 rb
->style
->Keepaway
);
3226 rb
->type
= VIA_SHADOW
;
3227 rb
->parent
.via_shadow
= first_via
;
3230 /* add these to proper subnet. */
3231 MergeNets (rb
, subnet
, NET
);
3232 MergeNets (rb
, subnet
, SUBNET
);
3233 assert (__routebox_is_good (rb
));
3234 /* and add it to the r-tree! */
3235 r_insert_entry (rd
->layergrouptree
[rb
->group
], &rb
->box
, 1);
3236 rb
->flags
.homeless
= 0; /* not homeless anymore */
3238 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
3240 gui
->set_color (ar_gc
, PCB
->ViaColor
);
3241 gui
->fill_circle (ar_gc
, X
, Y
, radius
);
3246 RD_DrawLine (routedata_t
* rd
,
3247 LocationType X1
, LocationType Y1
, LocationType X2
,
3248 LocationType Y2
, BDimension halfthick
, Cardinal group
,
3249 routebox_t
* subnet
, bool is_bad
, bool is_45
)
3251 /* we hold the line in a queue to concatenate segments that
3252 * ajoin one another. That reduces the number of things in
3253 * the trees and allows conflict boxes to be larger, both of
3254 * which are really useful.
3256 static LocationType qX1
= -1, qY1
, qX2
, qY2
;
3257 static BDimension qhthick
;
3258 static Cardinal qgroup
;
3259 static bool qis_45
, qis_bad
;
3260 static routebox_t
*qsn
;
3263 int ka
= AutoRouteParameters
.style
->Keepaway
;
3265 /* don't draw zero-length segments. */
3266 if (X1
== X2
&& Y1
== Y2
)
3268 if (qX1
== -1) /* first ever */
3274 qhthick
= halfthick
;
3281 /* Check if the lines concatenat. We only check the
3282 * normal expected nextpoint=lastpoint condition
3284 if (X1
== qX2
&& Y1
== qY2
&& qhthick
== halfthick
&& qgroup
== group
)
3286 if (qX1
== qX2
&& X1
== X2
) /* everybody on the same X here */
3291 if (qY1
== qY2
&& Y1
== Y2
) /* same Y all around */
3297 /* dump the queue, no match here */
3299 return; /* but not this! */
3300 rb
= (routebox_t
*) malloc (sizeof (*rb
));
3301 memset ((void *) rb
, 0, sizeof (*rb
));
3302 assert (is_45
? (ABS (qX2
- qX1
) == ABS (qY2
- qY1
)) /* line must be 45-degrees */
3303 : (qX1
== qX2
|| qY1
== qY2
) /* line must be ortho */ );
3305 /*X1 */ MIN (qX1
, qX2
) - qhthick
,
3306 /*Y1 */ MIN (qY1
, qY2
) - qhthick
,
3307 /*X2 */ MAX (qX1
, qX2
) + qhthick
+ 1,
3308 /*Y2 */ MAX (qY1
, qY2
) + qhthick
+ 1, ka
);
3311 rb
->parent
.line
= NULL
; /* indicates that not on PCB yet */
3312 rb
->flags
.fixed
= 0; /* indicates that not on PCB yet */
3313 rb
->flags
.is_odd
= AutoRouteParameters
.is_odd
;
3314 rb
->flags
.is_bad
= qis_bad
;
3315 rb
->came_from
= ALL
;
3316 rb
->flags
.homeless
= 0; /* we're putting this in the tree */
3317 rb
->flags
.nonstraight
= qis_45
;
3318 rb
->flags
.bl_to_ur
= ((qX2
>= qX1
&& qY2
<= qY1
)
3319 || (qX2
<= qX1
&& qY2
>= qY1
));
3320 rb
->style
= AutoRouteParameters
.style
;
3321 rb
->pass
= AutoRouteParameters
.pass
;
3323 /* add these to proper subnet. */
3324 MergeNets (rb
, qsn
, NET
);
3325 MergeNets (rb
, qsn
, SUBNET
);
3326 assert (__routebox_is_good (rb
));
3327 /* and add it to the r-tree! */
3328 r_insert_entry (rd
->layergrouptree
[rb
->group
], &rb
->box
, 1);
3330 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
3332 LayerTypePtr layp
= LAYER_PTR (PCB
->LayerGroups
.Entries
[rb
->group
][0]);
3334 gui
->set_line_width (ar_gc
, 2 * qhthick
);
3335 gui
->set_color (ar_gc
, layp
->Color
);
3336 gui
->draw_line (ar_gc
, qX1
, qY1
, qX2
, qY2
);
3339 /* and to the via space structures */
3340 if (AutoRouteParameters
.use_vias
)
3341 mtspace_add (rd
->mtspace
, &rb
->box
, rb
->flags
.is_odd
? ODD
: EVEN
,
3342 rb
->style
->Keepaway
);
3343 usedGroup
[rb
->group
] = true;
3344 /* and queue this one */
3349 qhthick
= halfthick
;
3357 RD_DrawManhattanLine (routedata_t
* rd
,
3358 const BoxType
* box1
, const BoxType
* box2
,
3359 CheapPointType start
, CheapPointType end
,
3360 BDimension halfthick
, Cardinal group
,
3361 routebox_t
* subnet
, bool is_bad
, bool last_was_x
)
3363 CheapPointType knee
= start
;
3364 if (end
.X
== start
.X
)
3366 RD_DrawLine (rd
, start
.X
, start
.Y
, end
.X
, end
.Y
, halfthick
, group
,
3367 subnet
, is_bad
, false);
3370 else if (end
.Y
== start
.Y
)
3372 RD_DrawLine (rd
, start
.X
, start
.Y
, end
.X
, end
.Y
, halfthick
, group
,
3373 subnet
, is_bad
, false);
3376 /* find where knee belongs */
3377 if (point_in_box (box1
, end
.X
, start
.Y
)
3378 || point_in_box (box2
, end
.X
, start
.Y
))
3388 if ((knee
.X
== end
.X
&& !last_was_x
) &&
3389 (point_in_box (box1
, start
.X
, end
.Y
)
3390 || point_in_box (box2
, start
.X
, end
.Y
)))
3395 assert (AutoRouteParameters
.is_smoothing
3396 || point_in_closed_box (box1
, knee
.X
, knee
.Y
)
3397 || point_in_closed_box (box2
, knee
.X
, knee
.Y
));
3399 if (1 || !AutoRouteParameters
.is_smoothing
)
3401 /* draw standard manhattan paths */
3402 RD_DrawLine (rd
, start
.X
, start
.Y
, knee
.X
, knee
.Y
, halfthick
, group
,
3403 subnet
, is_bad
, false);
3404 RD_DrawLine (rd
, knee
.X
, knee
.Y
, end
.X
, end
.Y
, halfthick
, group
,
3405 subnet
, is_bad
, false);
3409 /* draw 45-degree path across knee */
3410 BDimension len45
= MIN (ABS (start
.X
- end
.X
), ABS (start
.Y
- end
.Y
));
3411 CheapPointType kneestart
= knee
, kneeend
= knee
;
3412 if (kneestart
.X
== start
.X
)
3413 kneestart
.Y
+= (kneestart
.Y
> start
.Y
) ? -len45
: len45
;
3415 kneestart
.X
+= (kneestart
.X
> start
.X
) ? -len45
: len45
;
3416 if (kneeend
.X
== end
.X
)
3417 kneeend
.Y
+= (kneeend
.Y
> end
.Y
) ? -len45
: len45
;
3419 kneeend
.X
+= (kneeend
.X
> end
.X
) ? -len45
: len45
;
3420 RD_DrawLine (rd
, start
.X
, start
.Y
, kneestart
.X
, kneestart
.Y
, halfthick
,
3421 group
, subnet
, is_bad
, false);
3422 RD_DrawLine (rd
, kneestart
.X
, kneestart
.Y
, kneeend
.X
, kneeend
.Y
,
3423 halfthick
, group
, subnet
, is_bad
, true);
3424 RD_DrawLine (rd
, kneeend
.X
, kneeend
.Y
, end
.X
, end
.Y
, halfthick
, group
,
3425 subnet
, is_bad
, false);
3427 return (knee
.X
!= end
.X
);
3430 /* for smoothing, don't pack traces to min clearance gratuitously */
3432 add_clearance (CheapPointType
* nextpoint
, const BoxType
* b
)
3434 if (nextpoint
->X
== b
->X1
)
3437 AutoRouteParameters
.style
->Keepaway
< (b
->X1
+ b
->X2
) / 2)
3438 nextpoint
->X
+= AutoRouteParameters
.style
->Keepaway
;
3440 nextpoint
->X
= (b
->X1
+ b
->X2
) / 2;
3442 else if (nextpoint
->X
== b
->X2
)
3445 AutoRouteParameters
.style
->Keepaway
> (b
->X1
+ b
->X2
) / 2)
3446 nextpoint
->X
-= AutoRouteParameters
.style
->Keepaway
;
3448 nextpoint
->X
= (b
->X1
+ b
->X2
) / 2;
3450 else if (nextpoint
->Y
== b
->Y1
)
3453 AutoRouteParameters
.style
->Keepaway
< (b
->Y1
+ b
->Y2
) / 2)
3454 nextpoint
->Y
+= AutoRouteParameters
.style
->Keepaway
;
3456 nextpoint
->Y
= (b
->Y1
+ b
->Y2
) / 2;
3458 else if (nextpoint
->Y
== b
->Y2
)
3461 AutoRouteParameters
.style
->Keepaway
> (b
->Y1
+ b
->Y2
) / 2)
3462 nextpoint
->Y
-= AutoRouteParameters
.style
->Keepaway
;
3464 nextpoint
->Y
= (b
->Y1
+ b
->Y2
) / 2;
3468 /* This back-traces the expansion boxes along the best path
3469 * it draws the lines that will make the actual path.
3470 * during refinement passes, it should try to maximize the area
3471 * for other tracks so routing completion is easier.
3473 * during smoothing passes, it should try to make a better path,
3474 * possibly using diagonals, etc. The path boxes are larger on
3475 * average now so there is more possiblity to decide on a nice
3476 * path. Any combination of lines and arcs is possible, so long
3477 * as they don't poke more than half thick outside the path box.
3481 TracePath (routedata_t
* rd
, routebox_t
* path
, const routebox_t
* target
,
3482 routebox_t
* subnet
, bool is_bad
)
3484 bool last_x
= false;
3485 BDimension halfwidth
= HALF_THICK (AutoRouteParameters
.style
->Thick
);
3486 BDimension radius
= HALF_THICK (AutoRouteParameters
.style
->Diameter
);
3487 CheapPointType lastpoint
, nextpoint
;
3488 routebox_t
*lastpath
;
3491 assert (subnet
->style
== AutoRouteParameters
.style
);
3492 /*XXX: because we round up odd thicknesses, there's the possibility that
3493 * a connecting line end-point might be 0.005 mil off the "real" edge.
3494 * don't worry about this because line *thicknesses* are always >= 0.01 mil. */
3496 /* if we start with a thermal the target was a plane
3497 * or the target was a pin and the source a plane
3498 * in which case this thermal is the whole path
3500 if (path
->flags
.is_thermal
)
3502 /* the target was a plane, so we need to find a good spot for the via
3503 * now. It's logical to place it close to the source box which
3504 * is where we're utlimately headed on this path. However, it
3505 * must reside in the plane as well as the via area too.
3507 nextpoint
.X
= CENTER_X (path
->sbox
);
3508 nextpoint
.Y
= CENTER_Y (path
->sbox
);
3509 if (path
->parent
.expansion_area
->flags
.is_via
)
3511 TargetPoint (&nextpoint
, rb_source (path
));
3512 /* nextpoint is the middle of the source terminal now */
3513 b
= clip_box (&path
->sbox
, &path
->parent
.expansion_area
->sbox
);
3514 nextpoint
= closest_point_in_box (&nextpoint
, &b
);
3515 /* now it's in the via and plane near the source */
3517 else /* no via coming, target must have been a pin */
3519 assert (target
->type
== PIN
);
3520 TargetPoint (&nextpoint
, target
);
3522 assert (point_in_box (&path
->sbox
, nextpoint
.X
, nextpoint
.Y
));
3523 RD_DrawThermal (rd
, nextpoint
.X
, nextpoint
.Y
, path
->group
,
3524 path
->layer
, subnet
, is_bad
);
3528 /* start from best place of target box */
3529 lastpoint
.X
= CENTER_X (target
->sbox
);
3530 lastpoint
.Y
= CENTER_Y (target
->sbox
);
3531 TargetPoint (&lastpoint
, target
);
3532 if (AutoRouteParameters
.last_smooth
3533 && box_in_box (&path
->sbox
, &target
->sbox
))
3534 path
= path
->parent
.expansion_area
;
3536 if (path
->flags
.circular
)
3537 b
= shrink_box (&b
, MIN (b
.X2
- b
.X1
, b
.Y2
- b
.Y1
) / 5);
3538 nextpoint
= closest_point_in_box (&lastpoint
, &b
);
3539 if (AutoRouteParameters
.last_smooth
)
3540 RD_DrawLine (rd
, lastpoint
.X
, lastpoint
.Y
, nextpoint
.X
, nextpoint
.Y
,
3541 halfwidth
, path
->group
, subnet
, is_bad
, TRUE
);
3543 last_x
= RD_DrawManhattanLine (rd
, &target
->sbox
, &path
->sbox
,
3544 lastpoint
, nextpoint
, halfwidth
,
3545 path
->group
, subnet
, is_bad
, last_x
);
3547 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
3548 showroutebox (path
);
3549 #if defined(ROUTE_VERBOSE)
3550 printf ("TRACEPOINT start (%d, %d)\n", nextpoint
.X
, nextpoint
.Y
);
3556 lastpoint
= nextpoint
;
3558 assert (path
->type
== EXPANSION_AREA
);
3559 path
= path
->parent
.expansion_area
;
3561 if (path
->flags
.circular
)
3562 b
= shrink_box (&b
, MIN (b
.X2
- b
.X1
, b
.Y2
- b
.Y1
) / 5);
3563 assert (b
.X1
!= b
.X2
&& b
.Y1
!= b
.Y2
); /* need someplace to put line! */
3564 /* find point on path perimeter closest to last point */
3565 /* if source terminal, try to hit a good place */
3566 nextpoint
= closest_point_in_box (&lastpoint
, &b
);
3568 /* leave more clearance if this is a smoothing pass */
3569 if (AutoRouteParameters
.is_smoothing
&&
3570 (nextpoint
.X
!= lastpoint
.X
|| nextpoint
.Y
!= lastpoint
.Y
))
3571 add_clearance (&nextpoint
, &b
);
3573 if (path
->flags
.source
&& path
->type
!= PLANE
)
3574 TargetPoint (&nextpoint
, path
);
3575 assert (point_in_box (&lastpath
->box
, lastpoint
.X
, lastpoint
.Y
));
3576 assert (point_in_box (&path
->box
, nextpoint
.X
, nextpoint
.Y
));
3577 #if defined(ROUTE_DEBUG_VERBOSE)
3578 printf ("TRACEPATH: ");
3579 DumpRouteBox (path
);
3580 printf ("TRACEPATH: point (%d, %d) to point (%d, %d) layer %d\n",
3581 lastpoint
.X
, lastpoint
.Y
, nextpoint
.X
, nextpoint
.Y
,
3585 /* draw orthogonal lines from lastpoint to nextpoint */
3586 /* knee is placed in lastpath box */
3587 /* should never cause line to leave union of lastpath/path boxes */
3588 if (AutoRouteParameters
.last_smooth
)
3589 RD_DrawLine (rd
, lastpoint
.X
, lastpoint
.Y
, nextpoint
.X
, nextpoint
.Y
,
3590 halfwidth
, path
->group
, subnet
, is_bad
, TRUE
);
3592 last_x
= RD_DrawManhattanLine (rd
, &lastpath
->sbox
, &path
->sbox
,
3593 lastpoint
, nextpoint
, halfwidth
,
3594 path
->group
, subnet
, is_bad
, last_x
);
3595 if (path
->flags
.is_via
)
3596 { /* if via, then add via */
3597 #ifdef ROUTE_VERBOSE
3600 assert (point_in_box (&path
->box
, nextpoint
.X
, nextpoint
.Y
));
3601 RD_DrawVia (rd
, nextpoint
.X
, nextpoint
.Y
, radius
, subnet
, is_bad
);
3604 assert (lastpath
->flags
.is_via
|| path
->group
== lastpath
->group
);
3606 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_ROUTE_BOXES)
3607 showroutebox (path
);
3608 #endif /* ROUTE_DEBUG && DEBUG_SHOW_ROUTE_BOXES */
3609 /* if this is connected to a plane, draw the thermal */
3610 if (path
->flags
.is_thermal
|| path
->type
== PLANE
)
3611 RD_DrawThermal (rd
, lastpoint
.X
, lastpoint
.Y
, path
->group
,
3612 path
->layer
, subnet
, is_bad
);
3613 /* when one hop from the source, make an extra path in *this* box */
3614 if (path
->type
== EXPANSION_AREA
3615 && path
->parent
.expansion_area
->flags
.source
3616 && path
->parent
.expansion_area
->type
!= PLANE
)
3618 /* find special point on source (if it exists) */
3619 if (TargetPoint (&lastpoint
, path
->parent
.expansion_area
))
3621 lastpoint
= closest_point_in_routebox (&lastpoint
, path
);
3622 b
= shrink_routebox (path
);
3624 if (AutoRouteParameters
.is_smoothing
)
3625 add_clearance (&lastpoint
, &b
);
3627 if (AutoRouteParameters
.last_smooth
)
3628 RD_DrawLine (rd
, lastpoint
.X
, lastpoint
.Y
, nextpoint
.X
,
3629 nextpoint
.Y
, halfwidth
, path
->group
, subnet
,
3633 last_x
= RD_DrawManhattanLine (rd
, &b
, &b
,
3634 nextpoint
, lastpoint
,
3635 halfwidth
, path
->group
, subnet
,
3637 #if defined(ROUTE_DEBUG_VERBOSE)
3638 printf ("TRACEPATH: ");
3639 DumpRouteBox (path
);
3641 ("TRACEPATH: (to source) point (%d, %d) to point (%d, %d) layer %d\n",
3642 nextpoint
.X
, nextpoint
.Y
, lastpoint
.X
, lastpoint
.Y
,
3646 nextpoint
= lastpoint
;
3650 while (!path
->flags
.source
);
3651 /* flush the line queue */
3652 RD_DrawLine (rd
, -1, 0, 0, 0, 0, 0, NULL
, false, false);
3653 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
3654 gui
->use_mask (HID_FLUSH_DRAW_Q
);
3657 /* create a fake "edge" used to defer via site searching. */
3659 CreateSearchEdge (struct routeone_state
*s
, vetting_t
* work
, edge_t
* parent
,
3660 routebox_t
* rb
, conflict_t conflict
, rtree_t
* targets
,
3666 assert (__routebox_is_good (rb
));
3667 /* find the cheapest target */
3670 mincost_target_to_point (&parent
->cost_point
, max_layer
+ 1, targets
,
3671 parent
->mincost_target
);
3673 target
= parent
->mincost_target
;
3675 b
= shrink_routebox (target
);
3677 parent
->cost_to_point
+ AutoRouteParameters
.ViaCost
+
3678 cost_to_layerless_box (&rb
->cost_point
, 0, &b
);
3679 if (cost
< s
->best_cost
)
3682 ne
= malloc (sizeof (*ne
));
3683 memset ((void *) ne
, 0, sizeof (*ne
));
3685 ne
->flags
.via_search
= 1;
3686 ne
->flags
.in_plane
= in_plane
;
3688 if (rb
->flags
.homeless
)
3691 ne
->mincost_target
= target
;
3692 ne
->flags
.via_conflict_level
= conflict
;
3693 ne
->cost_to_point
= parent
->cost_to_point
;
3694 ne
->cost_point
= parent
->cost_point
;
3696 heap_insert (s
->workheap
, ne
->cost
, ne
);
3700 mtsFreeWork (&work
);
3705 add_or_destroy_edge (struct routeone_state
*s
, edge_t
* e
)
3707 e
->cost
= edge_cost (e
, s
->best_cost
);
3708 assert (__edge_is_good (e
));
3709 assert (is_layer_group_active
[e
->rb
->group
]);
3710 if (e
->cost
< s
->best_cost
)
3711 heap_insert (s
->workheap
, e
->cost
, e
);
3717 best_path_candidate (struct routeone_state
*s
,
3718 edge_t
* e
, routebox_t
* best_target
)
3720 e
->cost
= edge_cost (e
, EXPENSIVE
);
3721 if (s
->best_path
== NULL
|| e
->cost
< s
->best_cost
)
3723 #if defined(ROUTE_DEBUG) && defined (ROUTE_VERBOSE)
3724 printf ("New best path seen! cost = %f\n", e
->cost
);
3726 /* new best path! */
3727 if (s
->best_path
&& s
->best_path
->flags
.homeless
)
3728 RB_down_count (s
->best_path
);
3729 s
->best_path
= e
->rb
;
3730 s
->best_target
= best_target
;
3731 s
->best_cost
= e
->cost
;
3732 assert (s
->best_cost
>= 0);
3733 /* don't free this when we destroy edge! */
3734 if (s
->best_path
->flags
.homeless
)
3735 RB_up_count (s
->best_path
);
3740 /* vectors for via site candidates (see mtspace.h) */
3741 struct routeone_via_site_state
3743 vector_t
*free_space_vec
;
3744 vector_t
*lo_conflict_space_vec
;
3745 vector_t
*hi_conflict_space_vec
;
3749 add_via_sites (struct routeone_state
*s
,
3750 struct routeone_via_site_state
*vss
,
3751 mtspace_t
* mtspace
, routebox_t
* within
,
3752 conflict_t within_conflict_level
, edge_t
* parent_edge
,
3753 rtree_t
* targets
, BDimension shrink
, bool in_plane
)
3755 int radius
, keepaway
;
3757 BoxType region
= shrink_routebox (within
);
3758 shrink_box (®ion
, shrink
);
3760 radius
= HALF_THICK (AutoRouteParameters
.style
->Diameter
);
3761 keepaway
= AutoRouteParameters
.style
->Keepaway
;
3762 assert (AutoRouteParameters
.use_vias
);
3763 /* XXX: need to clip 'within' to shrunk_pcb_bounds, because when
3764 XXX: routing with conflicts may poke over edge. */
3766 /* ask for a via box near our cost_point first */
3767 work
= mtspace_query_rect (mtspace
, ®ion
, radius
, keepaway
,
3768 NULL
, vss
->free_space_vec
,
3769 vss
->lo_conflict_space_vec
,
3770 vss
->hi_conflict_space_vec
,
3771 AutoRouteParameters
.is_odd
,
3772 AutoRouteParameters
.with_conflicts
,
3773 &parent_edge
->cost_point
);
3776 CreateSearchEdge (s
, work
, parent_edge
, within
, within_conflict_level
,
3781 do_via_search (edge_t
* search
, struct routeone_state
*s
,
3782 struct routeone_via_site_state
*vss
, mtspace_t
* mtspace
,
3785 int i
, j
, count
= 0;
3786 int radius
, keepaway
;
3789 conflict_t within_conflict_level
;
3791 radius
= HALF_THICK (AutoRouteParameters
.style
->Diameter
);
3792 keepaway
= AutoRouteParameters
.style
->Keepaway
;
3793 work
= mtspace_query_rect (mtspace
, NULL
, 0, 0,
3794 search
->work
, vss
->free_space_vec
,
3795 vss
->lo_conflict_space_vec
,
3796 vss
->hi_conflict_space_vec
,
3797 AutoRouteParameters
.is_odd
,
3798 AutoRouteParameters
.with_conflicts
, NULL
);
3799 within
= search
->rb
;
3800 within_conflict_level
= search
->flags
.via_conflict_level
;
3801 for (i
= 0; i
< 3; i
++)
3804 (i
== NO_CONFLICT
? vss
->free_space_vec
:
3805 i
== LO_CONFLICT
? vss
->lo_conflict_space_vec
:
3806 i
== HI_CONFLICT
? vss
->hi_conflict_space_vec
: NULL
);
3808 while (!vector_is_empty (v
))
3811 BoxType
*area
= vector_remove_last (v
);
3812 if (!(i
== NO_CONFLICT
|| AutoRouteParameters
.with_conflicts
))
3817 /* answers are bloated by radius + keepaway */
3818 cliparea
= shrink_box (area
, radius
+ keepaway
);
3819 close_box (&cliparea
);
3821 assert (box_is_good (&cliparea
));
3823 for (j
= 0; j
< max_layer
; j
++)
3826 if (j
== within
->group
|| !is_layer_group_active
[j
])
3828 ne
= CreateViaEdge (&cliparea
, j
, within
, search
,
3829 within_conflict_level
, i
, targets
);
3830 add_or_destroy_edge (s
, ne
);
3834 /* prevent freeing of work when this edge is destroyed */
3835 search
->flags
.via_search
= 0;
3838 CreateSearchEdge (s
, work
, search
, within
, within_conflict_level
, targets
,
3839 search
->flags
.in_plane
);
3840 assert (vector_is_empty (vss
->free_space_vec
));
3841 assert (vector_is_empty (vss
->lo_conflict_space_vec
));
3842 assert (vector_is_empty (vss
->hi_conflict_space_vec
));
3845 /* vector of expansion areas to be eventually removed from r-tree
3846 * this is a global for troubleshooting
3850 /* some routines for use in gdb while debugging */
3851 #if defined(ROUTE_DEBUG)
3853 list_conflicts (routebox_t
* rb
)
3856 if (!rb
->conflicts_with
)
3858 n
= vector_size (rb
->conflicts_with
);
3859 for (i
= 0; i
< n
; i
++)
3860 printf ("%p, ", vector_element (rb
->conflicts_with
, i
));
3864 show_area_vec (int lay
)
3872 for (n
= 0; n
< vector_size (area_vec
); n
++)
3874 routebox_t
*rb
= (routebox_t
*) vector_element (area_vec
, n
);
3881 net_id (routebox_t
* rb
, long int id
)
3884 LIST_LOOP (rb
, same_net
, p
);
3885 if (p
->flags
.source
&& p
->parent
.pad
->ID
== id
)
3892 trace_parents (routebox_t
* rb
)
3894 while (rb
&& rb
->type
== EXPANSION_AREA
)
3896 printf (" %p ->", rb
);
3897 rb
= rb
->parent
.expansion_area
;
3900 printf (" %p is source\n", rb
);
3906 show_one (routebox_t
* rb
)
3908 int save
= showboxen
;
3915 show_path (routebox_t
* rb
)
3917 while (rb
&& rb
->type
== EXPANSION_AREA
)
3920 rb
= rb
->parent
.expansion_area
;
3926 show_sources (routebox_t
* rb
)
3929 if (!rb
->flags
.source
&& !rb
->flags
.target
)
3931 printf ("start with a source or target please\n");
3934 LIST_LOOP (rb
, same_net
, p
);
3935 if (p
->flags
.source
)
3941 __show_tree (const BoxType
* b
, void *cl
)
3944 routebox_t
*rb
= (routebox_t
*) b
;
3945 if (eo
< 0 || eo
== rb
->flags
.is_odd
)
3951 show_tree (rtree_t
* tree
, int even_odd
)
3953 r_search (tree
, NULL
, NULL
, __show_tree
, (void *) even_odd
);
3954 gui
->use_mask (HID_FLUSH_DRAW_Q
);
3960 __conflict_source (const BoxType
* box
, void *cl
)
3962 routebox_t
*rb
= (routebox_t
*) box
;
3963 if (rb
->flags
.touched
|| rb
->flags
.fixed
)
3967 routebox_t
*this = (routebox_t
*) cl
;
3968 path_conflicts (this, rb
, false);
3969 touch_conflicts (this->conflicts_with
, 1);
3975 source_conflicts (rtree_t
* tree
, routebox_t
* rb
)
3977 if (!AutoRouteParameters
.with_conflicts
)
3979 r_search (tree
, &rb
->sbox
, NULL
, __conflict_source
, rb
);
3980 touch_conflicts (NULL
, 1);
3983 struct routeone_status
3986 int route_had_conflicts
;
3987 cost_t best_route_cost
;
3988 bool net_completely_routed
;
3992 static struct routeone_status
3993 RouteOne (routedata_t
* rd
, routebox_t
* from
, routebox_t
* to
, int max_edges
)
3995 struct routeone_status result
;
3998 const BoxType
**target_list
;
4001 /* vector of source edges for filtering */
4002 vector_t
*source_vec
;
4003 /* working vector */
4006 struct routeone_state s
;
4007 struct routeone_via_site_state vss
;
4009 assert (rd
&& from
);
4010 result
.route_had_conflicts
= 0;
4011 /* no targets on to/from net need keepaway areas */
4012 LIST_LOOP (from
, same_net
, p
);
4013 p
->flags
.nobloat
= 1;
4015 /* set 'source' flags */
4016 LIST_LOOP (from
, same_subnet
, p
);
4017 if (!p
->flags
.nonstraight
)
4018 p
->flags
.source
= 1;
4021 /* count up the targets */
4024 /* remove source/target flags from non-straight obstacles, because they
4025 * don't fill their bounding boxes and so connecting to them
4026 * after we've routed is problematic. Better solution? */
4028 { /* if we're routing to a specific target */
4029 if (!to
->flags
.source
)
4030 { /* not already connected */
4031 /* check that 'to' and 'from' are on the same net */
4034 LIST_LOOP (from
, same_net
, p
);
4039 assert (seen
); /* otherwise from and to are on different nets! */
4040 /* set target flags only on 'to's subnet */
4041 LIST_LOOP (to
, same_subnet
, p
);
4042 if (!p
->flags
.nonstraight
&& is_layer_group_active
[p
->group
])
4044 p
->flags
.target
= 1;
4052 /* all nodes on the net but not connected to from are targets */
4053 LIST_LOOP (from
, same_net
, p
);
4054 if (!p
->flags
.source
&& is_layer_group_active
[p
->group
]
4055 && !p
->flags
.nonstraight
)
4057 p
->flags
.target
= 1;
4063 /* if no targets, then net is done! reset flags and return. */
4064 if (num_targets
== 0)
4066 LIST_LOOP (from
, same_net
, p
);
4067 p
->flags
.source
= p
->flags
.target
= p
->flags
.nobloat
= 0;
4069 result
.found_route
= false;
4070 result
.net_completely_routed
= true;
4071 result
.best_route_cost
= 0;
4072 result
.route_had_conflicts
= 0;
4076 result
.net_completely_routed
= false;
4078 /* okay, there's stuff to route */
4079 assert (!from
->flags
.target
);
4080 assert (num_targets
> 0);
4081 /* create list of target pointers and from that a r-tree of targets */
4082 target_list
= malloc (num_targets
* sizeof (*target_list
));
4084 LIST_LOOP (from
, same_net
, p
);
4085 if (p
->flags
.target
)
4087 target_list
[i
++] = &p
->box
;
4088 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_TARGETS)
4093 targets
= r_create_tree (target_list
, i
, 0);
4094 assert (i
<= num_targets
);
4097 source_vec
= vector_create ();
4098 /* touch the source subnet to prepare check for conflictors */
4099 LIST_LOOP (from
, same_subnet
, p
);
4100 p
->flags
.touched
= 1;
4102 LIST_LOOP (from
, same_subnet
, p
);
4104 /* we need the test for 'source' because this box may be nonstraight */
4105 if (p
->flags
.source
&& is_layer_group_active
[p
->group
])
4109 BoxType b
= shrink_routebox (p
);
4111 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_SOURCES)
4114 /* may expand in all directions from source; center edge cost point. */
4115 /* note that planes shouldn't really expand, but we need an edge */
4117 cp
.X
= CENTER_X (b
);
4118 cp
.Y
= CENTER_Y (b
);
4119 e
= CreateEdge (p
, cp
.X
, cp
.Y
, 0, NULL
, ALL
, targets
);
4120 cp
= closest_point_in_box (&cp
, &e
->mincost_target
->sbox
);
4121 cp
= closest_point_in_box (&cp
, &b
);
4124 source_conflicts (rd
->layergrouptree
[p
->group
], p
);
4125 vector_append (source_vec
, e
);
4129 LIST_LOOP (from
, same_subnet
, p
);
4130 p
->flags
.touched
= 0;
4132 /* break source edges; some edges may be too near obstacles to be able
4135 /* okay, main expansion-search routing loop. */
4136 /* set up the initial activity heap */
4137 s
.workheap
= heap_create ();
4138 assert (s
.workheap
);
4139 while (!vector_is_empty (source_vec
))
4141 edge_t
*e
= vector_remove_last (source_vec
);
4142 assert (is_layer_group_active
[e
->rb
->group
]);
4143 e
->cost
= edge_cost (e
, EXPENSIVE
);
4144 heap_insert (s
.workheap
, e
->cost
, e
);
4146 vector_destroy (&source_vec
);
4147 /* okay, process items from heap until it is empty! */
4149 s
.best_cost
= EXPENSIVE
;
4150 area_vec
= vector_create ();
4151 edge_vec
= vector_create ();
4152 vss
.free_space_vec
= vector_create ();
4153 vss
.lo_conflict_space_vec
= vector_create ();
4154 vss
.hi_conflict_space_vec
= vector_create ();
4155 while (!heap_is_empty (s
.workheap
))
4157 edge_t
*e
= heap_remove_smallest (s
.workheap
);
4162 /* don't bother expanding this edge if the minimum possible edge cost
4163 * is already larger than the best edge cost we've found. */
4164 if (s
.best_path
&& e
->cost
>= s
.best_cost
)
4166 heap_free (s
.workheap
, KillEdge
);
4167 goto dontexpand
; /* skip this edge */
4169 /* surprisingly it helps to give up and not try too hard to find
4170 * a route! This is not only faster, but results in better routing.
4171 * who would have guessed?
4173 if (seen
++ > max_edges
)
4175 assert (__edge_is_good (e
));
4176 /* mark or unmark conflictors as needed */
4177 touch_conflicts (e
->rb
->conflicts_with
, 1);
4178 if (e
->flags
.via_search
)
4180 do_via_search (e
, &s
, &vss
, rd
->mtspace
, targets
);
4183 /* we should never add edges on inactive layer groups to the heap. */
4184 assert (is_layer_group_active
[e
->rb
->group
]);
4185 #if defined(ROUTE_DEBUG) && defined(DEBUG_SHOW_EXPANSION_BOXES)
4188 if (e
->rb
->flags
.is_thermal
)
4190 best_path_candidate (&s
, e
, e
->mincost_target
);
4193 /* for a plane, look for quick connections with thermals or vias */
4194 if (e
->rb
->type
== PLANE
)
4196 routebox_t
*pin
= FindThermable (targets
, e
->rb
);
4199 BoxType b
= shrink_routebox (pin
);
4202 assert (pin
->flags
.target
);
4203 nrb
= CreateExpansionArea (&b
, e
->rb
->group
, e
->rb
, true, e
);
4204 nrb
->flags
.is_thermal
= 1;
4205 /* moving through the plane is free */
4206 e
->cost_point
.X
= b
.X1
;
4207 e
->cost_point
.Y
= b
.Y1
;
4208 ne
= CreateEdge2 (nrb
, e
->expand_dir
, e
, NULL
, pin
);
4209 best_path_candidate (&s
, ne
, pin
);
4214 /* add in possible via sites in plane */
4215 if (AutoRouteParameters
.use_vias
&&
4216 e
->cost
+ AutoRouteParameters
.ViaCost
< s
.best_cost
)
4218 /* we need a giant thermal */
4220 CreateExpansionArea (&e
->rb
->sbox
, e
->rb
->group
, e
->rb
,
4222 edge_t
*ne
= CreateEdge2 (nrb
, e
->expand_dir
, e
, NULL
,
4224 nrb
->flags
.is_thermal
= 1;
4225 add_via_sites (&s
, &vss
, rd
->mtspace
, nrb
, NO_CONFLICT
, ne
,
4226 targets
, e
->rb
->style
->Diameter
, true);
4229 goto dontexpand
; /* planes only connect via thermals */
4231 if (e
->flags
.is_via
)
4232 { /* special case via */
4233 routebox_t
*intersecting
;
4234 assert (AutoRouteParameters
.use_vias
);
4235 assert (e
->expand_dir
== ALL
);
4236 assert (vector_is_empty (edge_vec
));
4237 /* if there is already something here on this layer (like an
4238 * EXPANSION_AREA), then we don't want to expand from here
4239 * at least not inside the expansion area. A PLANE on the
4240 * other hand may be a target, or not.
4243 FindOneInBox (rd
->layergrouptree
[e
->rb
->group
], e
->rb
);
4245 if (intersecting
&& intersecting
->flags
.target
4246 && intersecting
->type
== PLANE
)
4248 /* we have hit a plane */
4251 BoxType b
= shrink_routebox (e
->rb
);
4252 /* limit via region to that inside the plane */
4253 clip_box (&b
, &intersecting
->sbox
);
4254 nrb
= CreateExpansionArea (&b
, e
->rb
->group
, e
->rb
, true, e
);
4255 nrb
->flags
.is_thermal
= 1;
4256 ne
= CreateEdge2 (nrb
, e
->expand_dir
, e
, NULL
, intersecting
);
4257 best_path_candidate (&s
, ne
, intersecting
);
4261 else if (intersecting
== NULL
)
4263 /* this via candidate is in an open area; add it to r-tree as
4264 * an expansion area */
4265 assert (e
->rb
->type
== EXPANSION_AREA
&& e
->rb
->flags
.is_via
);
4266 /*assert (!r_search (rd->layergrouptree[e->rb->group],
4267 &e->rb->box, NULL, no_planes,0));
4269 r_insert_entry (rd
->layergrouptree
[e
->rb
->group
], &e
->rb
->box
,
4271 e
->rb
->flags
.homeless
= 0; /* not homeless any more */
4272 /* add to vector of all expansion areas in r-tree */
4273 vector_append (area_vec
, e
->rb
);
4274 /* mark reset refcount to 0, since this is not homeless any more. */
4275 e
->rb
->refcount
= 0;
4276 /* go ahead and expand this edge! */
4281 { /* XXX: disabling this causes no via
4283 BoxType a
= bloat_routebox (intersecting
), b
;
4286 /* something intersects this via candidate. split via candidate
4287 * into pieces and add these pieces to the workheap. */
4288 for (i
= 0; i
< 3; i
++)
4290 for (j
= 0; j
< 3; j
++)
4292 b
= shrink_routebox (e
->rb
);
4296 b
.X2
= MIN (b
.X2
, a
.X1
);
4299 b
.X1
= MAX (b
.X1
, a
.X1
);
4300 b
.X2
= MIN (b
.X2
, a
.X2
);
4303 b
.X1
= MAX (b
.X1
, a
.X2
);
4311 b
.Y2
= MIN (b
.Y2
, a
.Y1
);
4314 b
.Y1
= MAX (b
.Y1
, a
.Y1
);
4315 b
.Y2
= MIN (b
.Y2
, a
.Y2
);
4318 b
.Y1
= MAX (b
.Y1
, a
.Y2
);
4323 /* skip if this box is not valid */
4324 if (!(b
.X1
< b
.X2
&& b
.Y1
< b
.Y2
))
4326 if (i
== 1 && j
== 1)
4328 /* this bit of the via space is obstructed. */
4329 if (intersecting
->type
== EXPANSION_AREA
4330 || intersecting
->flags
.fixed
)
4331 continue; /* skip this bit, it's already been done. */
4332 /* create an edge with conflicts, if enabled */
4333 if (!AutoRouteParameters
.with_conflicts
)
4335 ne
= CreateEdgeWithConflicts (&b
, intersecting
, e
, 1
4336 /*cost penalty to box */
4338 add_or_destroy_edge (&s
, ne
);
4342 /* if this is not the intersecting piece, create a new
4343 * (hopefully unobstructed) via edge and add it back to the
4346 CreateViaEdge (&b
, e
->rb
->group
,
4347 e
->rb
->parent
.expansion_area
, e
,
4348 e
->flags
.via_conflict_level
,
4350 /* value here doesn't matter */
4352 add_or_destroy_edge (&s
, ne
);
4358 /* between the time these edges are inserted and the
4359 * time they are processed, new expansion boxes (which
4360 * conflict with these edges) may be added to the graph!
4361 * w.o vias this isn't a problem because the broken box
4362 * is not homeless. */
4367 struct E_result
*ans
;
4370 if (e
->flags
.is_interior
)
4372 assert (AutoRouteParameters
.with_conflicts
); /* no interior edges unless
4373 routing with conflicts! */
4374 assert (e
->rb
->conflicts_with
);
4376 switch (e
->rb
->came_from
)
4380 b
.X1
= CENTER_X (b
);
4385 b
.Y1
= CENTER_Y (b
);
4390 b
.X1
= CENTER_X (b
);
4395 b
.Y1
= CENTER_Y (b
);
4402 /* sources may not expand to their own edges because of
4403 * adjacent blockers.
4405 else if (e
->rb
->flags
.source
)
4406 b
= box_center (&e
->rb
->sbox
);
4409 ans
= Expand (rd
->layergrouptree
[e
->rb
->group
], e
, &b
);
4410 if (!box_intersect (&ans
->inflated
, &ans
->orig
))
4413 /* skip if it didn't actually expand */
4414 if (ans
->inflated
.X1
>= e
->rb
->sbox
.X1
&&
4415 ans
->inflated
.X2
<= e
->rb
->sbox
.X2
&&
4416 ans
->inflated
.Y1
>= e
->rb
->sbox
.Y1
&&
4417 ans
->inflated
.Y2
<= e
->rb
->sbox
.Y2
)
4421 if (!box_is_good (&ans
->inflated
))
4423 nrb
= CreateExpansionArea (&ans
->inflated
, e
->rb
->group
, e
->rb
,
4425 r_insert_entry (rd
->layergrouptree
[nrb
->group
], &nrb
->box
, 1);
4426 vector_append (area_vec
, nrb
);
4427 nrb
->flags
.homeless
= 0; /* not homeless any more */
4429 BreakManyEdges (&s
, targets
, rd
->layergrouptree
[nrb
->group
],
4430 area_vec
, ans
, nrb
, e
);
4431 while (!vector_is_empty (broken
))
4433 edge_t
*ne
= vector_remove_last (broken
);
4434 add_or_destroy_edge (&s
, ne
);
4436 vector_destroy (&broken
);
4438 /* add in possible via sites in nrb */
4439 if (AutoRouteParameters
.use_vias
&& !e
->rb
->flags
.is_via
&&
4440 e
->cost
+ AutoRouteParameters
.ViaCost
< s
.best_cost
)
4441 add_via_sites (&s
, &vss
,
4442 rd
->mtspace
, nrb
, NO_CONFLICT
, e
, targets
, 0,
4449 touch_conflicts (NULL
, 1);
4450 heap_destroy (&s
.workheap
);
4451 r_destroy_tree (&targets
);
4452 assert (vector_is_empty (edge_vec
));
4453 vector_destroy (&edge_vec
);
4455 /* we should have a path in best_path now */
4459 #ifdef ROUTE_VERBOSE
4460 printf ("%d:%d RC %.0f", ro
++, seen
, s
.best_cost
);
4462 result
.found_route
= true;
4463 result
.best_route_cost
= s
.best_cost
;
4464 /* determine if the best path had conflicts */
4465 result
.route_had_conflicts
= 0;
4466 if (AutoRouteParameters
.with_conflicts
&& s
.best_path
->conflicts_with
)
4468 while (!vector_is_empty (s
.best_path
->conflicts_with
))
4470 rb
= vector_remove_last (s
.best_path
->conflicts_with
);
4471 rb
->flags
.is_bad
= 1;
4472 result
.route_had_conflicts
++;
4475 #ifdef ROUTE_VERBOSE
4476 if (result
.route_had_conflicts
)
4477 printf (" (%d conflicts)", result
.route_had_conflicts
);
4479 if (result
.route_had_conflicts
< AutoRouteParameters
.hi_conflict
)
4481 /* back-trace the path and add lines/vias to r-tree */
4482 TracePath (rd
, s
.best_path
, s
.best_target
, from
,
4483 result
.route_had_conflicts
);
4484 MergeNets (from
, s
.best_target
, SUBNET
);
4488 #ifdef ROUTE_VERBOSE
4489 printf (" (too many in fact)");
4491 result
.found_route
= false;
4493 #ifdef ROUTE_VERBOSE
4499 #ifdef ROUTE_VERBOSE
4500 printf ("%d:%d NO PATH FOUND.\n", ro
++, seen
);
4502 result
.best_route_cost
= s
.best_cost
;
4503 result
.found_route
= false;
4505 /* now remove all expansion areas from the r-tree. */
4506 while (!vector_is_empty (area_vec
))
4508 routebox_t
*rb
= vector_remove_last (area_vec
);
4509 assert (!rb
->flags
.homeless
);
4510 if (rb
->conflicts_with
4511 && rb
->parent
.expansion_area
->conflicts_with
!= rb
->conflicts_with
)
4512 vector_destroy (&rb
->conflicts_with
);
4513 r_delete_entry (rd
->layergrouptree
[rb
->group
], &rb
->box
);
4515 vector_destroy (&area_vec
);
4516 /* clean up; remove all 'source', 'target', and 'nobloat' flags */
4517 LIST_LOOP (from
, same_net
, p
);
4518 if (p
->flags
.source
&& p
->conflicts_with
)
4519 vector_destroy (&p
->conflicts_with
);
4520 p
->flags
.touched
= p
->flags
.source
= p
->flags
.target
= p
->flags
.nobloat
= 0;
4523 vector_destroy (&vss
.free_space_vec
);
4524 vector_destroy (&vss
.lo_conflict_space_vec
);
4525 vector_destroy (&vss
.hi_conflict_space_vec
);
4531 InitAutoRouteParameters (int pass
,
4532 RouteStyleType
* style
,
4533 bool with_conflicts
, bool is_smoothing
,
4538 AutoRouteParameters
.style
= style
;
4539 AutoRouteParameters
.bloat
= style
->Keepaway
+ HALF_THICK (style
->Thick
);
4541 AutoRouteParameters
.ViaCost
=
4542 350000 + style
->Diameter
* (is_smoothing
? 80 : 30);
4543 AutoRouteParameters
.LastConflictPenalty
=
4544 (400 * pass
/ passes
+ 2) / (pass
+ 1);
4545 AutoRouteParameters
.ConflictPenalty
=
4546 4 * AutoRouteParameters
.LastConflictPenalty
;
4547 AutoRouteParameters
.JogPenalty
= 1000 * (is_smoothing
? 20 : 4);
4548 AutoRouteParameters
.CongestionPenalty
= 1e6
;
4549 AutoRouteParameters
.MinPenalty
= EXPENSIVE
;
4550 for (i
= 0; i
< max_layer
; i
++)
4552 if (is_layer_group_active
[i
])
4554 AutoRouteParameters
.MinPenalty
= MIN (x_cost
[i
],
4555 AutoRouteParameters
.
4557 AutoRouteParameters
.MinPenalty
=
4558 MIN (y_cost
[i
], AutoRouteParameters
.MinPenalty
);
4561 AutoRouteParameters
.NewLayerPenalty
= is_smoothing
?
4562 0.5 * EXPENSIVE
: 10 * AutoRouteParameters
.ViaCost
;
4564 AutoRouteParameters
.hi_conflict
= MAX (8 * (passes
- pass
+ 1), 6);
4565 AutoRouteParameters
.is_odd
= (pass
& 1);
4566 AutoRouteParameters
.with_conflicts
= with_conflicts
;
4567 AutoRouteParameters
.is_smoothing
= is_smoothing
;
4568 AutoRouteParameters
.rip_always
= is_smoothing
;
4569 AutoRouteParameters
.last_smooth
= 0; //lastpass;
4570 AutoRouteParameters
.pass
= pass
+ 1;
4575 bad_boy (const BoxType
* b
, void *cl
)
4577 routebox_t
*box
= (routebox_t
*) b
;
4578 if (box
->type
== EXPANSION_AREA
)
4584 no_expansion_boxes (routedata_t
* rd
)
4592 for (i
= 0; i
< max_layer
; i
++)
4594 if (r_search (rd
->layergrouptree
[i
], &big
, NULL
, bad_boy
, NULL
))
4601 struct routeall_status
4603 /* --- for completion rate statistics ---- */
4605 /* total subnets routed without conflicts */
4607 /* total subnets routed with conflicts */
4608 int conflict_subnets
;
4609 /* net failted entirely */
4611 /* net was ripped */
4613 int total_nets_routed
;
4615 struct routeall_status
4616 RouteAll (routedata_t
* rd
)
4618 struct routeall_status ras
;
4619 struct routeone_status ros
;
4624 heap_t
*this_pass
, *next_pass
, *tmp
;
4625 routebox_t
*net
, *p
, *pp
;
4626 cost_t total_net_cost
, last_cost
= 0, this_cost
= 0;
4629 /* initialize heap for first pass;
4630 * do smallest area first; that makes
4631 * the subsequent costs more representative */
4632 this_pass
= heap_create ();
4633 next_pass
= heap_create ();
4635 net_heap
= heap_create ();
4637 LIST_LOOP (rd
->first_net
, different_net
, net
);
4640 BoxType bb
= shrink_routebox (net
);
4641 LIST_LOOP (net
, same_net
, p
);
4643 MAKEMIN (bb
.X1
, p
->sbox
.X1
);
4644 MAKEMIN (bb
.Y1
, p
->sbox
.Y1
);
4645 MAKEMAX (bb
.X2
, p
->sbox
.X2
);
4646 MAKEMAX (bb
.Y2
, p
->sbox
.Y2
);
4649 area
= (float) (bb
.X2
- bb
.X1
) * (bb
.Y2
- bb
.Y1
);
4650 heap_insert (this_pass
, area
, net
);
4654 ras
.total_nets_routed
= 0;
4655 /* refinement/finishing passes */
4656 for (i
= 0; i
<= passes
+ smoothes
; i
++)
4658 #ifdef ROUTE_VERBOSE
4659 if (i
> 0 && i
<= passes
)
4660 printf ("--------- STARTING REFINEMENT PASS %d ------------\n", i
);
4661 else if (i
> passes
)
4662 printf ("--------- STARTING SMOOTHING PASS %d -------------\n",
4665 ras
.total_subnets
= ras
.routed_subnets
= ras
.conflict_subnets
=
4666 ras
.failed
= ras
.ripped
= 0;
4667 assert (heap_is_empty (next_pass
));
4669 while (!heap_is_empty (this_pass
))
4675 net
= (routebox_t
*) heap_remove_smallest (this_pass
);
4676 InitAutoRouteParameters (i
, net
->style
, i
< passes
, i
> passes
,
4677 i
== passes
+ smoothes
);
4680 /* rip up all unfixed traces in this net ? */
4681 if (AutoRouteParameters
.rip_always
)
4686 LIST_LOOP (net
, same_net
, p
);
4687 if (p
->flags
.is_bad
)
4695 LIST_LOOP (net
, same_net
, p
);
4696 p
->flags
.is_bad
= 0;
4697 if (!p
->flags
.fixed
)
4700 assert (!p
->flags
.homeless
);
4703 RemoveFromNet (p
, NET
);
4704 RemoveFromNet (p
, SUBNET
);
4706 if (AutoRouteParameters
.use_vias
&& p
->type
!= VIA_SHADOW
4707 && p
->type
!= PLANE
)
4709 mtspace_remove (rd
->mtspace
, &p
->box
,
4710 p
->flags
.is_odd
? ODD
: EVEN
,
4711 p
->style
->Keepaway
);
4713 mtspace_add (rd
->mtspace
, &p
->box
,
4714 p
->flags
.is_odd
? EVEN
: ODD
,
4715 p
->style
->Keepaway
);
4719 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
)
4720 && (p
->type
== LINE
|| p
->type
== VIA
))
4723 r_delete_entry (rd
->layergrouptree
[p
->group
],
4729 p
->flags
.is_odd
= AutoRouteParameters
.is_odd
;
4733 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
4734 gui
->use_mask (HID_FLUSH_DRAW_Q
);
4735 /* reset to original connectivity */
4743 heap_insert (next_pass
, 0, net
);
4747 /* count number of subnets */
4748 FOREACH_SUBNET (net
, p
);
4749 ras
.total_subnets
++;
4750 END_FOREACH (net
, p
);
4751 /* the first subnet doesn't require routing. */
4752 ras
.total_subnets
--;
4755 /* only route that which isn't fully routed */
4757 if (ras
.total_subnets
&& !aabort
)
4759 if (ras
.total_subnets
)
4762 /* the loop here ensures that we get to all subnets even if
4763 * some of them are unreachable from the first subnet. */
4764 LIST_LOOP (net
, same_net
, p
);
4767 BoxType b
= shrink_routebox (p
);
4768 /* using a heap allows us to start from smaller objects and
4769 * end at bigger ones. also prefer to start at planes, then pads */
4770 heap_insert (net_heap
, (float) (b
.X2
- b
.X1
) *
4771 #if defined(ROUTE_RANDOMIZED)
4772 (0.3 + rand () / (RAND_MAX
+ 1.0)) *
4774 (b
.Y2
- b
.Y1
) * (p
->type
== PLANE
?
4779 ros
.net_completely_routed
= 0;
4780 while (!heap_is_empty (net_heap
))
4782 p
= (routebox_t
*) heap_remove_smallest (net_heap
);
4784 if (p
->flags
.fixed
&& !p
->flags
.subnet_processed
4785 && p
->type
!= OTHER
)
4787 while (!ros
.net_completely_routed
)
4789 assert (no_expansion_boxes (rd
));
4790 /* FIX ME: the number of edges to examine should be in autoroute parameters
4791 * i.e. the 2000 and 800 hard-coded below should be controllable by the user
4794 RouteOne (rd
, p
, NULL
,
4795 ((AutoRouteParameters
.
4796 is_smoothing
? 2000 : 800) * (i
+
4799 total_net_cost
+= ros
.best_route_cost
;
4800 if (ros
.found_route
)
4802 if (ros
.route_had_conflicts
)
4803 ras
.conflict_subnets
++;
4806 ras
.routed_subnets
++;
4807 ras
.total_nets_routed
++;
4812 if (!ros
.net_completely_routed
)
4814 /* don't bother trying any other source in this subnet */
4815 LIST_LOOP (p
, same_subnet
, pp
);
4816 pp
->flags
.subnet_processed
= 1;
4820 /* note that we can infer nothing about ras.total_subnets based
4821 * on the number of calls to RouteOne, because we may be unable
4822 * to route a net from a particular starting point, but perfectly
4823 * able to route it from some other. */
4830 if (!ros
.net_completely_routed
)
4831 net
->flags
.is_bad
= 1; /* don't skip this the next round */
4834 /* Route easiest nets from this pass first on next pass.
4835 * This works best because it's likely that the hardest
4836 * is the last one routed (since it has the most obstacles)
4837 * but it will do no good to rip it up and try it again
4838 * without first changing any of the other routes
4840 heap_insert (next_pass
, total_net_cost
, net
);
4841 if (total_net_cost
< EXPENSIVE
)
4842 this_cost
+= total_net_cost
;
4843 /* reset subnet_processed flags */
4844 LIST_LOOP (net
, same_net
, p
);
4846 p
->flags
.subnet_processed
= 0;
4850 /* swap this_pass and next_pass and do it all over again! */
4852 assert (heap_is_empty (this_pass
));
4854 this_pass
= next_pass
;
4856 /* XXX: here we should update a status bar */
4857 #if defined(ROUTE_DEBUG) || defined (ROUTE_VERBOSE)
4859 ("END OF PASS %d: %d/%d subnets routed without conflicts at cost %.0f, %d conflicts, %d failed %d ripped\n",
4860 i
, ras
.routed_subnets
, ras
.total_subnets
, this_cost
,
4861 ras
.conflict_subnets
, ras
.failed
, ras
.ripped
);
4867 /* if no conflicts found, skip directly to smoothing pass! */
4868 if (ras
.conflict_subnets
== 0 && ras
.routed_subnets
== ras
.total_subnets
4870 i
= passes
- (smoothes
? 0 : 1);
4871 /* if no changes in a smoothing round, then we're done */
4872 if (this_cost
== last_cost
&& i
> passes
&& i
< passes
+ smoothes
)
4873 i
= passes
+ smoothes
- 1;
4874 last_cost
= this_cost
;
4877 Message ("%d of %d nets successfully routed.\n",
4878 ras
.routed_subnets
, ras
.total_subnets
);
4880 heap_destroy (&this_pass
);
4881 heap_destroy (&next_pass
);
4883 heap_destroy (&net_heap
);
4886 /* no conflicts should be left at the end of the process. */
4887 assert (ras
.conflict_subnets
== 0);
4900 fpin_rect (const BoxType
* b
, void *cl
)
4902 PinTypePtr pin
= (PinTypePtr
) b
;
4903 struct fpin_info
*info
= (struct fpin_info
*) cl
;
4904 if (pin
->X
== info
->X
&& pin
->Y
== info
->Y
)
4906 info
->pin
= (PinTypePtr
) b
;
4907 longjmp (info
->env
, 1);
4913 FindPin (const BoxType
* box
, PinTypePtr
* pin
)
4915 struct fpin_info info
;
4920 if (setjmp (info
.env
) == 0)
4921 r_search (PCB
->Data
->pin_tree
, box
, NULL
, fpin_rect
, &info
);
4927 if (setjmp (info
.env
) == 0)
4928 r_search (PCB
->Data
->via_tree
, box
, NULL
, fpin_rect
, &info
);
4939 /* paths go on first 'on' layer in group */
4940 /* returns 'true' if any paths were added. */
4942 IronDownAllUnfixedPaths (routedata_t
* rd
)
4944 bool changed
= false;
4946 routebox_t
*net
, *p
;
4948 LIST_LOOP (rd
->first_net
, different_net
, net
);
4950 LIST_LOOP (net
, same_net
, p
);
4952 if (!p
->flags
.fixed
)
4954 /* find first on layer in this group */
4955 assert (PCB
->LayerGroups
.Number
[p
->group
] > 0);
4956 assert (is_layer_group_active
[p
->group
]);
4957 for (i
= 0, layer
= NULL
; i
< PCB
->LayerGroups
.Number
[p
->group
];
4960 layer
= LAYER_PTR (PCB
->LayerGroups
.Entries
[p
->group
][i
]);
4964 assert (layer
&& layer
->On
); /*at least one layer must be on in this group! */
4965 assert (p
->type
!= EXPANSION_AREA
);
4966 if (p
->type
== LINE
)
4968 BDimension halfwidth
= HALF_THICK (p
->style
->Thick
);
4969 double th
= halfwidth
* 2 + 1;
4971 assert (p
->parent
.line
== NULL
);
4972 /* orthogonal; thickness is 2*halfwidth */
4973 /* flip coordinates, if bl_to_ur */
4975 total_wire_length
+=
4976 sqrt ((b
.X2
- b
.X1
- th
) * (b
.X2
- b
.X1
- th
) +
4977 (b
.Y2
- b
.Y1
- th
) * (b
.Y2
- b
.Y1
- th
));
4978 b
= shrink_box (&b
, halfwidth
);
4979 if (b
.X2
== b
.X1
+ 1)
4981 if (b
.Y2
== b
.Y1
+ 1)
4983 if (p
->flags
.bl_to_ur
)
4990 /* using CreateDrawn instead of CreateNew concatenates sequential lines */
4991 p
->parent
.line
= CreateDrawnLineOnLayer
4992 (layer
, b
.X1
, b
.Y1
, b
.X2
, b
.Y2
,
4994 p
->style
->Keepaway
* 2,
4995 MakeFlags (AUTOFLAG
|
4996 (TEST_FLAG (CLEARNEWFLAG
, PCB
) ? CLEARLINEFLAG
:
5001 AddObjectToCreateUndoList (LINE_TYPE
, layer
,
5002 p
->parent
.line
, p
->parent
.line
);
5006 else if (p
->type
== VIA
|| p
->type
== VIA_SHADOW
)
5009 (p
->type
== VIA_SHADOW
) ? p
->parent
.via_shadow
: p
;
5010 BDimension radius
= HALF_THICK (pp
->style
->Diameter
);
5011 BoxType b
= shrink_routebox (p
);
5013 assert (pp
->type
== VIA
);
5014 if (pp
->parent
.via
== NULL
)
5016 assert (b
.X1
+ radius
== b
.X2
- radius
);
5017 assert (b
.Y1
+ radius
== b
.Y2
- radius
);
5019 CreateNewVia (PCB
->Data
, b
.X1
+ radius
,
5021 pp
->style
->Diameter
,
5022 2 * pp
->style
->Keepaway
,
5023 0, pp
->style
->Hole
, NULL
,
5024 MakeFlags (AUTOFLAG
));
5025 assert (pp
->parent
.via
);
5028 AddObjectToCreateUndoList (VIA_TYPE
,
5035 assert (pp
->parent
.via
);
5036 if (p
->type
== VIA_SHADOW
)
5039 p
->parent
.via
= pp
->parent
.via
;
5042 else if (p
->type
== THERMAL
)
5043 /* nothing to do because, the via might not be there yet */ ;
5049 /* loop again to place all the thermals now that the vias are down */
5050 LIST_LOOP (net
, same_net
, p
);
5052 if (p
->type
== THERMAL
)
5054 PinTypePtr pin
= NULL
;
5055 /* thermals are alread a single point search, no need to shrink */
5056 int type
= FindPin (&p
->box
, &pin
);
5059 AddObjectToClearPolyUndoList (type
,
5060 pin
->Element
? pin
->Element
: pin
,
5062 RestoreToPolygon (PCB
->Data
, VIA_TYPE
, LAYER_PTR (p
->layer
),
5064 AddObjectToFlagUndoList (type
,
5065 pin
->Element
? pin
->Element
: pin
, pin
,
5067 ASSIGN_THERM (p
->layer
, PCB
->ThermStyle
, pin
);
5068 AddObjectToClearPolyUndoList (type
,
5069 pin
->Element
? pin
->Element
: pin
,
5071 ClearFromPolygon (PCB
->Data
, VIA_TYPE
, LAYER_PTR (p
->layer
),
5084 AutoRoute (bool selected
)
5086 bool changed
= false;
5090 total_wire_length
= 0;
5091 total_via_count
= 0;
5092 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
5094 gui
->use_mask (HID_LIVE_DRAWING
);
5099 ar_gc
= gui
->make_gc ();
5100 gui
->set_line_cap (ar_gc
, Round_Cap
);
5103 for (i
= 0; i
< NUM_STYLES
; i
++)
5105 if (PCB
->RouteStyle
[i
].Thick
== 0 ||
5106 PCB
->RouteStyle
[1].Diameter
== 0 ||
5107 PCB
->RouteStyle
[1].Hole
== 0 || PCB
->RouteStyle
[i
].Keepaway
== 0)
5109 Message ("You must define proper routing styles\n"
5110 "before auto-routing.\n");
5114 if (PCB
->Data
->RatN
== 0)
5116 SaveFindFlag (DRCFLAG
);
5117 rd
= CreateRouteData ();
5121 routebox_t
*net
, *rb
, *last
;
5123 /* count number of rats selected */
5124 RAT_LOOP (PCB
->Data
);
5126 if (!selected
|| TEST_FLAG (SELECTEDFLAG
, line
))
5130 #ifdef ROUTE_VERBOSE
5131 printf ("%d nets!\n", i
);
5134 goto donerouting
; /* nothing to do here */
5135 /* if only one rat selected, do things the quick way. =) */
5138 RAT_LOOP (PCB
->Data
);
5139 if (!selected
|| TEST_FLAG (SELECTEDFLAG
, line
))
5141 /* look up the end points of this rat line */
5145 FindRouteBoxOnLayerGroup (rd
, line
->Point1
.X
,
5146 line
->Point1
.Y
, line
->group1
);
5148 FindRouteBoxOnLayerGroup (rd
, line
->Point2
.X
,
5149 line
->Point2
.Y
, line
->group2
);
5150 assert (a
!= NULL
&& b
!= NULL
);
5151 assert (a
->style
== b
->style
);
5153 if (a->type != PAD && b->type == PAD)
5160 /* route exactly one net, without allowing conflicts */
5161 InitAutoRouteParameters (0, a
->style
, false, true, true);
5162 /* hace planes work better as sources than targets */
5163 changed
= RouteOne (rd
, a
, b
, 150000).found_route
|| changed
;
5168 /* otherwise, munge the netlists so that only the selected rats
5170 /* first, separate all sub nets into separate nets */
5171 /* note that this code works because LIST_LOOP is clever enough not to
5172 * be fooled when the list is changing out from under it. */
5174 LIST_LOOP (rd
->first_net
, different_net
, net
);
5176 FOREACH_SUBNET (net
, rb
);
5180 last
->different_net
.next
= rb
;
5181 rb
->different_net
.prev
= last
;
5185 END_FOREACH (net
, rb
);
5186 LIST_LOOP (net
, same_net
, rb
);
5188 rb
->same_net
= rb
->same_subnet
;
5191 /* at this point all nets are equal to their subnets */
5196 last
->different_net
.next
= rd
->first_net
;
5197 rd
->first_net
->different_net
.prev
= last
;
5200 /* now merge only those subnets connected by a rat line */
5201 RAT_LOOP (PCB
->Data
);
5202 if (!selected
|| TEST_FLAG (SELECTEDFLAG
, line
))
5204 /* look up the end points of this rat line */
5208 FindRouteBoxOnLayerGroup (rd
, line
->Point1
.X
,
5209 line
->Point1
.Y
, line
->group1
);
5211 FindRouteBoxOnLayerGroup (rd
, line
->Point2
.X
,
5212 line
->Point2
.Y
, line
->group2
);
5215 #ifdef DEBUG_STALE_RATS
5216 AddObjectToFlagUndoList (RATLINE_TYPE
, line
, line
, line
);
5217 ASSIGN_FLAG (SELECTEDFLAG
, true, line
);
5219 #endif /* DEBUG_STALE_RATS */
5220 Message ("The rats nest is stale! Aborting autoroute...\n");
5223 /* merge subnets into a net! */
5224 MergeNets (a
, b
, NET
);
5227 /* now 'different_net' may point to too many different nets. Reset. */
5228 LIST_LOOP (rd
->first_net
, different_net
, net
);
5230 if (!net
->flags
.touched
)
5232 LIST_LOOP (net
, same_net
, rb
);
5233 rb
->flags
.touched
= 1;
5236 else /* this is not a "different net"! */
5237 RemoveFromNet (net
, DIFFERENT_NET
);
5240 /* reset "touched" flag */
5241 LIST_LOOP (rd
->first_net
, different_net
, net
);
5243 LIST_LOOP (net
, same_net
, rb
);
5245 assert (rb
->flags
.touched
);
5246 rb
->flags
.touched
= 0;
5252 /* okay, rd's idea of netlist now corresponds to what we want routed */
5253 /* auto-route all nets */
5254 changed
= (RouteAll (rd
).total_nets_routed
> 0) || changed
;
5257 changed
= IronDownAllUnfixedPaths (rd
);
5258 Message ("Total added wire length = %f inches, %d vias added\n",
5259 total_wire_length
/ 1.e5
, total_via_count
);
5260 DestroyRouteData (&rd
);
5261 if (TEST_FLAG (LIVEROUTEFLAG
, PCB
))
5263 gui
->use_mask (HID_LIVE_DRAWING_OFF
);
5267 SaveUndoSerialNumber ();
5269 /* optimize rats, we've changed connectivity a lot. */
5270 DeleteRats (false /*all rats */ );
5271 RestoreUndoSerialNumber ();
5272 AddAllRats (false /*all rats */ , NULL
);
5273 RestoreUndoSerialNumber ();
5275 IncrementUndoSerialNumber ();
5277 ClearAndRedrawOutput ();
5280 #if defined (ROUTE_DEBUG)