4 * PCB, interactive printed circuit board design
5 * Copyright (C) 2003 DJ Delorie
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 * Contact addresses for paper mail and Email:
22 * DJ Delorie, 334 North Road, Deerfield NH 03037-1110, USA
45 #include "pcb-printf.h"
47 #ifdef HAVE_LIBDMALLOC
52 #define rint(x) (ceil((x) - 0.5))
55 #define dprintf if(0)pcb_printf
57 #define selected(x) TEST_FLAG (SELECTEDFLAG, (x))
58 #define autorouted(x) TEST_FLAG (AUTOFLAG, (x))
60 #define SB (PCB->Bloat+1)
72 #define ORIENT(x) ((x) & 0xf0)
73 #define DIRECT(x) ((x) & 0x0f)
75 /* Manhattan length of the longest "freckle" */
76 #define LONGEST_FRECKLE 2
80 typedef struct corner_s
83 struct corner_s
*next
;
91 struct line_s
**lines
;
103 typedef struct rect_s
108 #define DELETE(q) (q)->layer = 0xdeadbeef
109 #define DELETED(q) ((q)->layer == 0xdeadbeef)
111 static corner_s
*corners
, *next_corner
= 0;
112 static line_s
*lines
;
114 static int layer_groupings
[MAX_LAYER
];
115 static char layer_type
[MAX_LAYER
];
119 static int autorouted_only
= 1;
121 static const char djopt_sao_syntax
[] = "OptAutoOnly()";
123 static const char djopt_sao_help
[] =
124 "Toggles the optimize-only-autorouted flag.";
126 /* %start-doc actions OptAutoOnly
128 The original purpose of the trace optimizer was to clean up the traces
129 created by the various autorouters that have been used with PCB. When
130 a board has a mix of autorouted and carefully hand-routed traces, you
131 don't normally want the optimizer to move your hand-routed traces.
132 But, sometimes you do. By default, the optimizer only optimizes
133 autorouted traces. This action toggles that setting, so that you can
134 optimize hand-routed traces also.
139 djopt_set_auto_only (int argc
, char **argv
, Coord x
, Coord y
)
141 autorouted_only
= autorouted_only
? 0 : 1;
146 djopt_get_auto_only (void *data
)
148 return autorouted_only
;
151 HID_Flag djopt_flag_list
[] = {
152 {"optautoonly", djopt_get_auto_only
, NULL
}
155 REGISTER_FLAGS (djopt_flag_list
)
158 element_name_for (corner_s
* c
)
160 ELEMENT_LOOP (PCB
->Data
);
165 return element
->Name
[1].TextString
;
171 return element
->Name
[1].TextString
;
180 corner_name (corner_s
* c
)
182 static char buf
[4][100];
188 if (c
->net
== 0xf1eef1ee)
190 sprintf (buf
[bn
], "\033[31m[%p freed corner]\033[0m", (void *) c
);
194 sprintf (buf
[bn
], "\033[%dm[%p ",
195 (c
->pin
|| c
->pad
|| c
->via
) ? 33 : 34, (void *) c
);
196 bp
= buf
[bn
] + strlen (buf
[bn
]);
197 size_left
= sizeof (buf
[bn
]) - strlen (buf
[bn
]);
200 pcb_snprintf (bp
, size_left
, "pin %s:%s at %#mD",
201 element_name_for (c
), c
->pin
->Number
, c
->x
, c
->y
);
203 pcb_snprintf (bp
, size_left
, "via at %#mD", c
->x
, c
->y
);
206 pcb_snprintf (bp
, size_left
, "pad %s:%s at %#mD %#mD-%#mD",
207 element_name_for (c
), c
->pad
->Number
, c
->x
, c
->y
,
208 c
->pad
->Point1
.X
, c
->pad
->Point1
.Y
,
209 c
->pad
->Point2
.X
, c
->pad
->Point2
.Y
);
212 pcb_snprintf (bp
, size_left
, "at %#mD", c
->x
, c
->y
);
213 sprintf (bp
+ strlen (bp
), " n%d l%d]\033[0m", c
->n_lines
, c
->layer
);
217 static int solder_layer
, component_layer
;
220 dj_abort (char *msg
, ...)
233 #define check(c,l) check2(__LINE__,c,l)
235 check2 (int srcline
, corner_s
* c
, line_s
* l
)
237 int saw_c
= 0, saw_l
= 0;
242 for (cc
= corners
; cc
; cc
= cc
->next
)
248 for (i
= 0; i
< cc
->n_lines
; i
++)
249 if (cc
->lines
[i
]->s
!= cc
&& cc
->lines
[i
]->e
!= cc
)
250 dj_abort ("check:%d: cc has line without backref\n", srcline
);
251 if (cc
->via
&& (cc
->x
!= cc
->via
->X
|| cc
->y
!= cc
->via
->Y
))
252 dj_abort ("check:%d: via not at corner\n", srcline
);
253 if (cc
->pin
&& (cc
->x
!= cc
->pin
->X
|| cc
->y
!= cc
->pin
->Y
))
254 dj_abort ("check:%d: pin not at corner\n", srcline
);
257 dj_abort ("check:%d: corner not in corners list\n", srcline
);
258 for (ll
= lines
; ll
; ll
= ll
->next
)
264 for (i
= 0; i
< ll
->s
->n_lines
; i
++)
265 if (ll
->s
->lines
[i
] == ll
)
267 if (i
== ll
->s
->n_lines
)
268 dj_abort ("check:%d: ll->s has no backref\n", srcline
);
269 for (i
= 0; i
< ll
->e
->n_lines
; i
++)
270 if (ll
->e
->lines
[i
] == ll
)
272 if (i
== ll
->e
->n_lines
)
273 dj_abort ("check:%d: ll->e has no backref\n", srcline
);
275 && (ll
->s
->x
!= ll
->line
->Point1
.X
276 || ll
->s
->y
!= ll
->line
->Point1
.Y
277 || ll
->e
->x
!= ll
->line
->Point2
.X
278 || ll
->e
->y
!= ll
->line
->Point2
.Y
))
280 pcb_printf ("line: %#mD to %#mD pcbline: %#mD to %#mD\n",
284 ll
->line
->Point1
.Y
, ll
->line
->Point2
.X
, ll
->line
->Point2
.Y
);
285 dj_abort ("check:%d: line doesn't match pcbline\n", srcline
);
289 dj_abort ("check:%d: line not in lines list\n", srcline
);
294 #define SWAP(a,b) { a^=b; b^=a; a^=b; }
301 return n
- n
% (Settings
.Grid
);
304 /* Avoid commonly used names. */
309 return x
> 0 ? x
: -x
;
315 return x
> y
? x
: y
;
321 return x
< y
? x
: y
;
325 * Find distance between 2 points. We use floating point math here
326 * because we can fairly easily overflow a 32 bit integer here. In
327 * fact it only takes 0.46" to do so.
330 dist (int x1
, int y1
, int x2
, int y2
)
332 double dx1
, dy1
, dx2
, dy2
, d
;
339 d
= sqrt ((dx1
- dx2
) * (dx1
- dx2
) + (dy1
- dy2
) * (dy1
- dy2
));
346 line_length (line_s
* l
)
348 if (l
->s
->x
== l
->e
->x
)
349 return djabs (l
->s
->y
- l
->e
->y
);
350 if (l
->s
->y
== l
->e
->y
)
351 return djabs (l
->s
->x
- l
->e
->x
);
352 return dist (l
->s
->x
, l
->s
->y
, l
->e
->x
, l
->e
->y
);
356 dist_ltp2 (int dx
, int y
, int y1
, int y2
)
361 return dist (dx
, y
, 0, y1
);
363 return dist (dx
, y
, 0, y2
);
374 intersecting_layers (int l1
, int l2
)
376 if (l1
== -1 || l2
== -1)
380 if (layer_groupings
[l1
] == layer_groupings
[l2
])
386 dist_line_to_point (line_s
* l
, corner_s
* c
)
389 /* We can do this quickly if l is vertical or horizontal. */
390 if (l
->s
->x
== l
->e
->x
)
391 return dist_ltp2 (l
->s
->x
- c
->x
, c
->y
, l
->s
->y
, l
->e
->y
);
392 if (l
->s
->y
== l
->e
->y
)
393 return dist_ltp2 (l
->s
->y
- c
->y
, c
->x
, l
->s
->x
, l
->e
->x
);
395 /* Do it the hard way. See comments for IsPointOnLine() in search.c */
396 len
= sqrt (sqr (l
->s
->x
- l
->e
->x
) + sqr (l
->s
->y
- l
->e
->y
));
398 return dist (l
->s
->x
, l
->s
->y
, c
->x
, c
->y
);
400 (l
->s
->y
- c
->y
) * (l
->s
->y
- l
->e
->y
) + (l
->s
->x
- c
->x
) * (l
->s
->x
-
404 return dist (l
->s
->x
, l
->s
->y
, c
->x
, c
->y
);
406 return dist (l
->e
->x
, l
->e
->y
, c
->x
, c
->y
);
408 (l
->e
->y
- l
->s
->y
) * (c
->x
* l
->s
->x
) + (l
->e
->x
- l
->s
->x
) * (c
->y
-
410 return (int) (d
/ len
);
414 line_orient (line_s
* l
, corner_s
* c
)
449 common_corner (line_s
* l1
, line_s
* l2
)
451 if (l1
->s
== l2
->s
|| l1
->s
== l2
->e
)
453 if (l1
->e
== l2
->s
|| l1
->e
== l2
->e
)
455 dj_abort ("common_corner: no common corner found\n");
461 other_corner (line_s
* l
, corner_s
* c
)
467 dj_abort ("other_corner: neither corner passed\n");
472 find_corner_if (int x
, int y
, int l
)
475 for (c
= corners
; c
; c
= c
->next
)
479 if (c
->x
!= x
|| c
->y
!= y
)
481 if (!(c
->layer
== -1 || intersecting_layers (c
->layer
, l
)))
489 find_corner (int x
, int y
, int l
)
492 for (c
= corners
; c
; c
= c
->next
)
496 if (c
->x
!= x
|| c
->y
!= y
)
498 if (!(c
->layer
== -1 || intersecting_layers (c
->layer
, l
)))
502 c
= (corner_s
*) malloc (sizeof (corner_s
));
513 c
->lines
= (line_s
**) malloc (INC
* sizeof (line_s
*));
518 add_line_to_corner (line_s
* l
, corner_s
* c
)
521 n
= (c
->n_lines
+ 1 + INC
) & ~INC
;
522 c
->lines
= (line_s
**) realloc (c
->lines
, n
* sizeof (line_s
*));
523 c
->lines
[c
->n_lines
] = l
;
525 dprintf ("add_line_to_corner %#mD\n", c
->x
, c
->y
);
529 create_pcb_line (int layer
, int x1
, int y1
, int x2
, int y2
,
530 int thick
, int clear
, FlagType flags
)
534 LayerType
*lyr
= LAYER_PTR (layer
);
536 from
= (char *) lyr
->Line
;
537 nl
= CreateNewLineOnLayer (PCB
->Data
->Layer
+ layer
,
538 x1
, y1
, x2
, y2
, thick
, clear
, flags
);
539 AddObjectToCreateUndoList (LINE_TYPE
, lyr
, nl
, nl
);
541 to
= (char *) lyr
->Line
;
545 for (lp
= lines
; lp
; lp
= lp
->next
)
549 if ((char *) (lp
->line
) >= from
550 && (char *) (lp
->line
) <= from
+ lyr
->LineN
* sizeof (LineType
))
551 lp
->line
= (LineType
*) ((char *) (lp
->line
) + (to
- from
));
558 new_line (corner_s
* s
, corner_s
* e
, int layer
, LineType
* example
)
562 if (layer
>= max_copper_layer
)
563 dj_abort ("layer %d\n", layer
);
566 dj_abort ("NULL example passed to new_line()\n", layer
);
568 if (s
->x
== e
->x
&& s
->y
== e
->y
)
571 ls
= (line_s
*) malloc (sizeof (line_s
));
579 if ((example
->Point1
.X
== s
->x
&& example
->Point1
.Y
== s
->y
580 && example
->Point2
.X
== e
->x
&& example
->Point2
.Y
== e
->y
)
581 || (example
->Point2
.X
== s
->x
&& example
->Point2
.Y
== s
->y
582 && example
->Point1
.X
== e
->x
&& example
->Point1
.Y
== e
->y
))
591 ("New line \033[35m%#mD to %#mD from l%d t%#mS c%#mS f%s\033[0m\n",
592 s
->x
, s
->y
, e
->x
, e
->y
, layer
, example
->Thickness
,
593 example
->Clearance
, flags_to_string (example
->Flags
, LINE_TYPE
));
595 create_pcb_line (layer
, s
->x
, s
->y
, e
->x
, e
->y
, example
->Thickness
,
596 example
->Clearance
, example
->Flags
);
599 dj_abort ("can't create new line!");
602 add_line_to_corner (ls
, s
);
603 add_line_to_corner (ls
, e
);
611 c_orth_to (corner_s
* c
, line_s
* l
, int o
)
615 for (i
= 0; i
< c
->n_lines
; i
++)
617 if (c
->lines
[i
] == l
)
619 o2
= line_orient (c
->lines
[i
], c
);
620 if (ORIENT (o
) == ORIENT (o2
) || o2
== DIAGONAL
)
629 other_line (corner_s
* c
, line_s
* l
)
633 if (c
->pin
|| c
->pad
|| c
->via
)
635 for (i
= 0; i
< c
->n_lines
; i
++)
637 if (c
->lines
[i
] == l
)
647 empty_rect (rect_s
* rect
)
649 rect
->x1
= rect
->y1
= INT_MAX
;
650 rect
->x2
= rect
->y2
= INT_MIN
;
654 add_point_to_rect (rect_s
* rect
, int x
, int y
, int w
)
656 if (rect
->x1
> x
- w
)
658 if (rect
->x2
< x
+ w
)
660 if (rect
->y1
> y
- w
)
662 if (rect
->y2
< y
+ w
)
667 add_line_to_rect (rect_s
* rect
, line_s
* l
)
669 add_point_to_rect (rect
, l
->s
->x
, l
->s
->y
, 0);
670 add_point_to_rect (rect
, l
->e
->x
, l
->e
->y
, 0);
674 pin_in_rect (rect_s
* r
, int x
, int y
, int w
)
676 if (x
< r
->x1
&& x
+ w
< r
->x1
)
678 if (x
> r
->x2
&& x
- w
> r
->x2
)
680 if (y
< r
->y1
&& y
+ w
< r
->y1
)
682 if (y
> r
->y2
&& y
- w
> r
->y2
)
688 line_in_rect (rect_s
* r
, line_s
* l
)
692 add_point_to_rect (&lr
, l
->s
->x
, l
->s
->y
, l
->line
->Thickness
/ 2);
693 add_point_to_rect (&lr
, l
->e
->x
, l
->e
->y
, l
->line
->Thickness
/ 2);
694 dprintf ("line_in_rect %#mD-%#mD vs %#mD-%#mD\n",
695 r
->x1
, r
->y1
, r
->x2
, r
->y2
, lr
.x1
, lr
.y1
, lr
.x2
, lr
.y2
);
696 /* simple intersection of rectangles */
705 if (lr
.x1
< lr
.x2
&& lr
.y1
< lr
.y2
)
711 corner_radius (corner_s
* c
)
716 diam
= djmax (c
->pin
->Thickness
, diam
);
718 diam
= djmax (c
->via
->Thickness
, diam
);
719 for (i
= 0; i
< c
->n_lines
; i
++)
720 if (c
->lines
[i
]->line
)
721 diam
= djmax (c
->lines
[i
]->line
->Thickness
, diam
);
722 diam
= (diam
+ 1) / 2;
729 corner_layer (corner_s
* c
)
731 if (c
->pin
|| c
->via
)
735 return c
->lines
[0]->layer
;
740 add_corner_to_rect_if (rect_s
* rect
, corner_s
* c
, rect_s
* e
)
742 int diam
= corner_radius (c
);
743 if (!pin_in_rect (e
, c
->x
, c
->y
, diam
))
745 if (c
->x
< e
->x1
&& c
->y
< e
->y1
&& dist (c
->x
, c
->y
, e
->x1
, e
->y1
) > diam
)
747 if (c
->x
> e
->x2
&& c
->y
< e
->y1
&& dist (c
->x
, c
->y
, e
->x2
, e
->y1
) > diam
)
749 if (c
->x
< e
->x1
&& c
->y
> e
->y2
&& dist (c
->x
, c
->y
, e
->x1
, e
->y2
) > diam
)
751 if (c
->x
> e
->x2
&& c
->y
> e
->y2
&& dist (c
->x
, c
->y
, e
->x2
, e
->y2
) > diam
)
754 /*pcb_printf("add point %#mD diam %#mS\n", c->x, c->y, diam); */
755 add_point_to_rect (rect
, c
->x
, c
->y
, diam
);
759 remove_line (line_s
* l
)
762 LayerType
*layer
= &(PCB
->Data
->Layer
[l
->layer
]);
767 RemoveLine (layer
, l
->line
);
771 for (i
= 0, j
= 0; i
< l
->s
->n_lines
; i
++)
772 if (l
->s
->lines
[i
] != l
)
773 l
->s
->lines
[j
++] = l
->s
->lines
[i
];
776 for (i
= 0, j
= 0; i
< l
->e
->n_lines
; i
++)
777 if (l
->e
->lines
[i
] != l
)
778 l
->e
->lines
[j
++] = l
->e
->lines
[i
];
784 move_line_to_layer (line_s
* l
, int layer
)
788 ls
= LAYER_PTR (l
->layer
);
789 ld
= LAYER_PTR (layer
);
791 MoveObjectToLayer (LINE_TYPE
, ls
, l
->line
, 0, ld
, 0);
796 remove_via_at (corner_s
* c
)
798 RemoveObject (VIA_TYPE
, c
->via
, 0, 0);
803 remove_corner (corner_s
* c2
)
806 dprintf ("remove corner %s\n", corner_name (c2
));
809 for (c
= corners
; c
; c
= c
->next
)
816 if (next_corner
== c2
)
817 next_corner
= c2
->next
;
824 merge_corners (corner_s
* c1
, corner_s
* c2
)
829 dprintf ("merge corners %s %s\n", corner_name (c1
), corner_name (c2
));
830 for (i
= 0; i
< c2
->n_lines
; i
++)
832 add_line_to_corner (c2
->lines
[i
], c1
);
833 if (c2
->lines
[i
]->s
== c2
)
834 c2
->lines
[i
]->s
= c1
;
835 if (c2
->lines
[i
]->e
== c2
)
836 c2
->lines
[i
]->e
= c1
;
838 if (c1
->via
&& c2
->via
)
846 if (c2
->layer
!= c1
->layer
)
853 move_corner (corner_s
* c
, int x
, int y
)
860 if (c
->pad
|| c
->pin
)
861 dj_abort ("move_corner: has pin or pad\n");
862 dprintf ("move_corner %p from %#mD to %#mD\n", (void *) c
, c
->x
, c
->y
, x
, y
);
863 pad
= find_corner_if (x
, y
, c
->layer
);
869 MoveObject (VIA_TYPE
, via
, via
, via
, x
- via
->X
, y
- via
->Y
);
870 dprintf ("via move %#mD to %#mD\n", via
->X
, via
->Y
, x
, y
);
872 for (i
= 0; i
< c
->n_lines
; i
++)
874 LineType
*tl
= c
->lines
[i
]->line
;
877 if (c
->lines
[i
]->s
== c
)
879 MoveObject (LINEPOINT_TYPE
, LAYER_PTR (c
->lines
[i
]->layer
), tl
,
880 &tl
->Point1
, x
- (tl
->Point1
.X
),
885 MoveObject (LINEPOINT_TYPE
, LAYER_PTR (c
->lines
[i
]->layer
), tl
,
886 &tl
->Point2
, x
- (tl
->Point2
.X
),
889 dprintf ("Line %p moved to %#mD %#mD\n", (void *) tl
,
890 tl
->Point1
.X
, tl
->Point1
.Y
, tl
->Point2
.X
, tl
->Point2
.Y
);
894 merge_corners (c
, pad
);
896 for (i
= 0; i
< c
->n_lines
; i
++)
898 if (c
->lines
[i
]->s
->x
== c
->lines
[i
]->e
->x
899 && c
->lines
[i
]->s
->y
== c
->lines
[i
]->e
->y
)
901 corner_s
*c2
= other_corner (c
->lines
[i
], c
);
902 dprintf ("move_corner: removing line %#mD %#mD %p %p\n",
903 c
->x
, c
->y
, c2
->x
, c2
->y
, (void *) c
, (void *) c2
);
905 remove_line (c
->lines
[i
]);
907 merge_corners (c
, c2
);
913 gui
->progress (0, 0, 0);
921 for (l
= lines
; l
; l
= l
->next
)
925 if (l
->line
&& selected (l
->line
))
932 trim_step (int s
, int l1
, int l2
)
934 dprintf ("trim %d %d %d\n", s
, l1
, l2
);
939 if (s
!= l1
&& s
!= l2
)
944 static int canonicalize_line (line_s
* l
);
947 split_line (line_s
* l
, corner_s
* c
)
953 if (!intersecting_layers (l
->layer
, c
->layer
))
959 dprintf ("split on pad!\n");
960 if (l
->s
->pad
== c
->pad
|| l
->e
->pad
== c
->pad
)
962 dprintf ("splitting...\n");
966 pcbline
= create_pcb_line (l
->layer
,
967 c
->x
, c
->y
, l
->e
->x
, l
->e
->y
,
968 l
->line
->Thickness
, l
->line
->Clearance
,
971 return 0; /* already a line there */
975 dprintf ("split line from %#mD to %#mD at %#mD\n",
976 l
->s
->x
, l
->s
->y
, l
->e
->x
, l
->e
->y
, c
->x
, c
->y
);
977 ls
= (line_s
*) malloc (sizeof (line_s
));
985 ls
->layer
= l
->layer
;
986 for (i
= 0; i
< l
->e
->n_lines
; i
++)
987 if (l
->e
->lines
[i
] == l
)
990 add_line_to_corner (l
, c
);
991 add_line_to_corner (ls
, c
);
993 MoveObject (LINEPOINT_TYPE
, LAYER_PTR (l
->layer
), l
->line
, &l
->line
->Point2
,
994 c
->x
- (l
->line
->Point2
.X
), c
->y
- (l
->line
->Point2
.Y
));
1000 canonicalize_line (line_s
* l
)
1002 /* This could be faster */
1004 if (l
->s
->x
== l
->e
->x
)
1008 int x1
= l
->s
->x
- l
->line
->Thickness
/ 2;
1009 int x2
= l
->s
->x
+ l
->line
->Thickness
/ 2;
1016 for (c
= corners
; c
; c
= c
->next
)
1020 if ((y1
< c
->y
&& c
->y
< y2
)
1021 && intersecting_layers (l
->layer
, c
->layer
))
1024 && c
->x
< x2
&& c
->x
> x1
&& !(c
->pad
|| c
->pin
))
1026 move_corner (c
, l
->s
->x
, c
->y
);
1028 if (c
->x
== l
->s
->x
)
1030 /* FIXME: if the line is split, we have to re-canonicalize
1032 return split_line (l
, c
);
1037 else if (l
->s
->y
== l
->e
->y
)
1041 int y1
= l
->s
->y
- l
->line
->Thickness
/ 2;
1042 int y2
= l
->s
->y
+ l
->line
->Thickness
/ 2;
1049 for (c
= corners
; c
; c
= c
->next
)
1053 if ((x1
< c
->x
&& c
->x
< x2
)
1054 && intersecting_layers (l
->layer
, c
->layer
))
1057 && c
->y
< y2
&& c
->y
> y1
&& !(c
->pad
|| c
->pin
))
1059 move_corner (c
, c
->x
, l
->s
->y
);
1061 if (c
->y
== l
->s
->y
)
1063 /* FIXME: Likewise. */
1064 return split_line (l
, c
);
1071 /* diagonal lines. Let's try to split them at pins/vias
1089 for (c
= corners
; c
; c
= c
->next
)
1093 if (!c
->via
&& !c
->pin
)
1095 if ((x1
< c
->x
&& c
->x
< x2
)
1096 && (y1
< c
->y
&& c
->y
< y2
)
1097 && intersecting_layers (l
->layer
, c
->layer
))
1099 int th
= c
->pin
? c
->pin
->Thickness
: c
->via
->Thickness
;
1101 if (dist (l
->s
->x
, l
->s
->y
, c
->x
, c
->y
) > th
1102 && dist (l
->e
->x
, l
->e
->y
, c
->x
, c
->y
) > th
1103 && PinLineIntersect (c
->pin
? c
->pin
: c
->via
, l
->line
))
1105 return split_line (l
, c
);
1113 /* Make sure all vias are at line end points */
1115 canonicalize_lines ()
1123 for (l
= lines
; l
; l
= l
->next
)
1127 count
+= canonicalize_line (l
);
1137 simple_optimize_corner (corner_s
* c
)
1145 /* see if no via is needed */
1146 if (selected (c
->via
))
1147 dprintf ("via check: line[0] layer %d at %#mD nl %d\n",
1148 c
->lines
[0]->layer
, c
->x
, c
->y
, c
->n_lines
);
1149 /* We can't delete vias that connect to power planes, or vias
1150 that aren't tented (assume they're test points). */
1151 if (!TEST_ANY_THERMS (c
->via
)
1152 && c
->via
->Mask
== 0)
1154 for (i
= 1; i
< c
->n_lines
; i
++)
1156 if (selected (c
->via
))
1157 dprintf (" line[%d] layer %d %#mD to %#mD\n",
1158 i
, c
->lines
[i
]->layer
,
1159 c
->lines
[i
]->s
->x
, c
->lines
[i
]->s
->y
,
1160 c
->lines
[i
]->e
->x
, c
->lines
[i
]->e
->y
);
1161 if (c
->lines
[i
]->layer
!= c
->lines
[0]->layer
)
1164 if (i
== c
->n_lines
)
1166 if (selected (c
->via
))
1167 dprintf (" remove it\n");
1175 if (c
->n_lines
== 2 && !c
->via
)
1177 /* see if it is an unneeded corner */
1178 int o
= line_orient (c
->lines
[0], c
);
1179 corner_s
*c2
= other_corner (c
->lines
[1], c
);
1180 corner_s
*c0
= other_corner (c
->lines
[0], c
);
1181 if (o
== line_orient (c
->lines
[1], c2
) && o
!= DIAGONAL
)
1183 dprintf ("straight %#mD to %#mD to %#mD\n",
1184 c0
->x
, c0
->y
, c
->x
, c
->y
, c2
->x
, c2
->y
);
1185 if (selected (c
->lines
[0]->line
))
1186 SET_FLAG (SELECTEDFLAG
, c
->lines
[1]->line
);
1187 if (selected (c
->lines
[1]->line
))
1188 SET_FLAG (SELECTEDFLAG
, c
->lines
[0]->line
);
1189 move_corner (c
, c2
->x
, c2
->y
);
1193 if (c
->n_lines
== 1 && !c
->via
)
1195 corner_s
*c0
= other_corner (c
->lines
[0], c
);
1196 if (abs(c
->x
- c0
->x
) + abs(c
->y
- c0
->y
) <= LONGEST_FRECKLE
)
1199 * Remove this line, as it is a "freckle". A freckle is an extremely
1200 * short line (around 0.01 thou) that is unconnected at one end.
1201 * Freckles are almost insignificantly small, but are annoying as
1202 * they prevent the mitering optimiser from working.
1203 * Freckles sometimes arise because of a bug in the autorouter that
1204 * causes it to create small overshoots (typically 0.01 thou) at the
1205 * intersections of vertical and horizontal lines. These overshoots
1206 * are converted to freckles as a side effect of canonicalize_line().
1207 * Note that canonicalize_line() is not at fault, the bug is in the
1208 * autorouter creating overshoots.
1209 * The autorouter bug arose some time between the 20080202 and 20091103
1211 * This code is probably worth keeping even when the autorouter bug is
1212 * fixed, as "freckles" could conceivably arise in other ways.
1214 dprintf ("freckle %#mD to %#mD\n", c
->x
, c
->y
, c0
->x
, c0
->y
);
1215 move_corner (c
, c0
->x
, c0
->y
);
1222 /* We always run these */
1224 simple_optimizations ()
1229 /* Look for corners that aren't */
1230 for (c
= corners
; c
; c
= c
->next
)
1234 if (c
->pad
|| c
->pin
)
1236 rv
+= simple_optimize_corner (c
);
1242 is_hole (corner_s
* c
)
1244 return c
->pin
|| c
->pad
|| c
->via
;
1248 orthopull_1 (corner_s
* c
, int fdir
, int rdir
, int any_sel
)
1250 static corner_s
**cs
= 0;
1252 static line_s
**ls
= 0;
1254 int i
, li
, ln
, cn
, snap
;
1257 int adir
= 0, sdir
= 0, pull
;
1258 int saw_sel
= 0, saw_auto
= 0;
1259 int max
, len
= 0, r1
= 0, r2
;
1265 cs
= (corner_s
**) malloc (10 * sizeof (corner_s
));
1267 ls
= (line_s
**) malloc (10 * sizeof (line_s
));
1271 for (i
= 0; i
< c
->n_lines
; i
++)
1273 int o
= line_orient (c
->lines
[i
], c
);
1289 dj_abort ("fdir not right or down\n");
1298 if (c2
->pad
|| c2
->pin
|| c2
->n_lines
< 2)
1303 cs
= (corner_s
**) realloc (cs
, cm
* sizeof (corner_s
*));
1306 r2
= corner_radius (c2
);
1310 for (i
= 0; i
< c2
->n_lines
; i
++)
1312 int o
= line_orient (c2
->lines
[i
], c2
);
1318 return 0; /* we don't support overlapping lines yet */
1321 if (o
== rdir
&& c2
->lines
[i
] != ls
[ln
- 1])
1322 return 0; /* likewise */
1330 if (selected (l
->line
))
1332 if (autorouted (l
->line
))
1337 ls
= (line_s
**) realloc (ls
, lm
* sizeof (line_s
*));
1340 c2
= other_corner (l
, c2
);
1342 if (cn
< 2 || pull
== 0)
1344 if (any_sel
&& !saw_sel
)
1346 if (!any_sel
&& autorouted_only
&& !saw_auto
)
1349 /* Ok, now look for other blockages. */
1352 add_point_to_rect (&rr
, c
->x
, c
->y
, corner_radius (c
));
1353 add_point_to_rect (&rr
, c2
->x
, c2
->y
, corner_radius (c2
));
1355 if (fdir
== RIGHT
&& pull
< 0)
1357 else if (fdir
== RIGHT
&& pull
> 0)
1359 else if (fdir
== DOWN
&& pull
< 0)
1361 else if (fdir
== DOWN
&& pull
> 0)
1365 for (i
= 0; i
< cn
; i
++)
1366 for (li
= 0; li
< cs
[i
]->n_lines
; li
++)
1368 if (line_orient (cs
[i
]->lines
[li
], cs
[i
]) != edir
)
1370 len
= line_length (cs
[i
]->lines
[li
]);
1371 if (max
> len
|| max
== -1)
1374 dprintf ("c %s %4#mD cn %d pull %3d max %4#mS\n",
1375 fdir
== RIGHT
? "right" : "down ", c
->x
, c
->y
, cn
, pull
, max
);
1380 rr
.y1
= c
->y
- r1
- max
;
1383 rr
.y2
= c
->y
+ r1
+ max
;
1386 rr
.x1
= c
->x
- r1
- max
;
1389 rr
.x2
= c
->x
+ r1
+ max
;
1398 for (cb
= corners
; cb
; cb
= cb
->next
)
1403 r1
= corner_radius (cb
);
1404 if (cb
->net
== c
->net
&& !cb
->pad
)
1406 if (!pin_in_rect (&rr
, cb
->x
, cb
->y
, r1
))
1410 #define ECHK(X,Y,LT) \
1411 for (i=0; i<cn; i++) \
1413 if (!intersecting_layers(cs[i]->layer, cb->layer)) \
1415 r2 = corner_radius(cs[i]); \
1416 if (cb->X + r1 <= cs[i]->X - r2 - SB - 1) \
1418 if (cb->X - r1 >= cs[i]->X + r2 + SB + 1) \
1420 if (cb->Y LT cs[i]->Y) \
1422 sep = djabs(cb->Y - cs[i]->Y) - r1 - r2 - SB - 1; \
1424 { max = sep; snap = 1; }\
1426 for (i=0; i<ln; i++) \
1428 if (!intersecting_layers(ls[i]->layer, cb->layer)) \
1430 if (cb->X <= cs[i]->X || cb->X >= cs[i+1]->X) \
1432 sep = (djabs(cb->Y - cs[i]->Y) - ls[i]->line->Thickness/2 \
1435 { max = sep; snap = 1; }\
1452 /* We must now check every line segment against our corners. */
1453 for (l
= lines
; l
; l
= l
->next
)
1455 int o
, x1
, x2
, y1
, y2
;
1458 dprintf ("check line %#mD to %#mD\n", l
->s
->x
, l
->s
->y
, l
->e
->x
, l
->e
->y
);
1459 if (l
->s
->net
== c
->net
)
1461 dprintf (" same net\n");
1464 o
= line_orient (l
, 0);
1465 /* We don't need to check perpendicular lines, because their
1466 corners already take care of it. */
1467 if ((fdir
== RIGHT
&& (o
== UP
|| o
== DOWN
))
1468 || (fdir
== DOWN
&& (o
== RIGHT
|| o
== LEFT
)))
1470 dprintf (" perpendicular\n");
1474 /* Choose so that x1,y1 is closest to corner C */
1475 if ((fdir
== RIGHT
&& l
->s
->x
< l
->e
->x
)
1476 || (fdir
== DOWN
&& l
->s
->y
< l
->e
->y
))
1491 /* Eliminate all lines outside our range */
1492 if ((fdir
== RIGHT
&& (x2
< c
->x
|| x1
> c2
->x
))
1493 || (fdir
== DOWN
&& (y2
< c
->y
|| y1
> c2
->y
)))
1495 dprintf (" outside our range\n");
1499 /* Eliminate all lines on the wrong side of us */
1500 if ((edir
== UP
&& y1
> c
->y
&& y2
> c
->y
)
1501 || (edir
== DOWN
&& y1
< c
->y
&& y2
< c
->y
)
1502 || (edir
== LEFT
&& x1
> c
->x
&& x2
> c
->x
)
1503 || (edir
== RIGHT
&& x1
< c
->x
&& x2
< c
->x
))
1505 dprintf (" wrong side\n");
1509 /* For now, cheat on diagonals */
1530 /* Ok, now see how far we can get for each of our corners. */
1531 for (i
= 0; i
< cn
; i
++)
1533 int r
= l
->line
->Thickness
+ SB
+ corner_radius (cs
[i
]) + 1;
1535 if ((fdir
== RIGHT
&& (x2
< cs
[i
]->x
|| x1
> cs
[i
]->x
))
1536 || (fdir
== DOWN
&& (y2
< cs
[i
]->y
|| y1
> cs
[i
]->y
)))
1538 if (!intersecting_layers (cs
[i
]->layer
, l
->layer
))
1556 dprintf (" len is %#mS vs corner at %#mD\n", len
, cs
[i
]->x
, cs
[i
]->y
);
1565 /* We must make sure that if a segment isn't being completely
1566 removed, that any vias and/or pads don't overlap. */
1571 for (i
= 0; i
< cn
; i
++)
1572 for (li
= 0; li
< cs
[i
]->n_lines
; li
++)
1574 line_s
*l
= cs
[i
]->lines
[li
];
1575 corner_s
*oc
= other_corner (l
, cs
[i
]);
1576 if (line_orient (l
, cs
[i
]) != edir
)
1578 len
= line_length (l
);
1579 if (!oc
->pad
|| !cs
[i
]->via
)
1581 if (!is_hole (l
->s
) || !is_hole (l
->e
))
1586 len
-= corner_radius (l
->s
);
1587 len
-= corner_radius (l
->e
);
1614 if (snap
&& max
> Settings
.Grid
)
1617 len
+= Settings
.Grid
- 1;
1618 len
= gridsnap (len
);
1620 if ((fdir
== RIGHT
&& len
== cs
[0]->y
) || (fdir
== DOWN
&& len
== cs
[0]->x
))
1622 for (i
= 0; i
< cn
; i
++)
1626 max
= len
- cs
[i
]->y
;
1627 move_corner (cs
[i
], cs
[i
]->x
, len
);
1631 max
= len
- cs
[i
]->x
;
1632 move_corner (cs
[i
], len
, cs
[i
]->y
);
1641 /* Look for straight runs which could be moved to reduce total trace
1643 int any_sel
= any_line_selected ();
1647 for (c
= corners
; c
;)
1651 if (c
->pin
|| c
->pad
)
1657 rv
+= orthopull_1 (c
, RIGHT
, LEFT
, any_sel
);
1658 if (c
!= next_corner
)
1663 rv
+= orthopull_1 (c
, DOWN
, UP
, any_sel
);
1664 if (c
!= next_corner
)
1672 pcb_printf ("orthopull: %ml mils saved\n", rv
);
1679 /* Look for "U" shaped traces we can shorten (or eliminate) */
1681 int any_selected
= any_line_selected ();
1682 line_s
*l
, *l1
, *l2
;
1683 corner_s
*c
, *c1
, *c2
;
1685 int o
, o1
, o2
, step
, w
;
1686 for (l
= lines
; l
; l
= l
->next
)
1692 if (any_selected
&& !selected (l
->line
))
1694 if (!any_selected
&& autorouted_only
&& !autorouted (l
->line
))
1696 if (l
->s
->pin
|| l
->s
->pad
|| l
->e
->pin
|| l
->e
->pad
)
1698 o
= line_orient (l
, 0);
1701 l1
= other_line (l
->s
, l
);
1704 o1
= line_orient (l1
, l
->s
);
1705 l2
= other_line (l
->e
, l
);
1708 o2
= line_orient (l2
, l
->e
);
1709 if (ORIENT (o
) == ORIENT (o1
) || o1
!= o2
|| o1
== DIAGONAL
)
1712 dprintf ("\nline: %#mD to %#mD\n", l
->s
->x
, l
->s
->y
, l
->e
->x
, l
->e
->y
);
1713 w
= l
->line
->Thickness
/ 2 + SB
+ 1;
1715 add_line_to_rect (&rr
, l1
);
1716 add_line_to_rect (&rr
, l2
);
1717 if (rr
.x1
!= l
->s
->x
&& rr
.x1
!= l
->e
->x
)
1719 if (rr
.x2
!= l
->s
->x
&& rr
.x2
!= l
->e
->x
)
1721 if (rr
.y1
!= l
->s
->y
&& rr
.y1
!= l
->e
->y
)
1723 if (rr
.y2
!= l
->s
->y
&& rr
.y2
!= l
->e
->y
)
1725 dprintf ("range: x %#mS..%#mS y %#mS..%#mS\n", rr
.x1
, rr
.x2
, rr
.y1
, rr
.y2
);
1727 c1
= other_corner (l1
, l
->s
);
1728 c2
= other_corner (l2
, l
->e
);
1731 for (c
= corners
; c
; c
= c
->next
)
1735 if (c
->net
!= l
->s
->net
1736 && intersecting_layers (c
->layer
, l
->s
->layer
))
1737 add_corner_to_rect_if (&rp
, c
, &rr
);
1739 if (rp
.x1
== INT_MAX
)
1746 dprintf ("pin r: x %#mS..%#mS y %#mS..%#mS\n", rp
.x1
, rp
.x2
, rp
.y1
, rp
.y2
);
1751 step
= l
->s
->x
- rp
.x2
- w
;
1752 step
= gridsnap (step
);
1753 if (step
> l
->s
->x
- c1
->x
)
1754 step
= l
->s
->x
- c1
->x
;
1755 if (step
> l
->s
->x
- c2
->x
)
1756 step
= l
->s
->x
- c2
->x
;
1759 dprintf ("left step %#mS at %#mD\n", step
, l
->s
->x
, l
->s
->y
);
1760 move_corner (l
->s
, l
->s
->x
- step
, l
->s
->y
);
1761 move_corner (l
->e
, l
->e
->x
- step
, l
->e
->y
);
1766 step
= rp
.x1
- l
->s
->x
- w
;
1767 step
= gridsnap (step
);
1768 if (step
> c1
->x
- l
->s
->x
)
1769 step
= c1
->x
- l
->s
->x
;
1770 if (step
> c2
->x
- l
->s
->x
)
1771 step
= c2
->x
- l
->s
->x
;
1774 dprintf ("right step %#mS at %#mD\n", step
, l
->s
->x
, l
->s
->y
);
1775 move_corner (l
->s
, l
->s
->x
+ step
, l
->s
->y
);
1776 move_corner (l
->e
, l
->e
->x
+ step
, l
->e
->y
);
1781 if (rp
.y2
== INT_MIN
)
1783 step
= trim_step (l
->s
->y
- rp
.y2
- w
,
1784 l
->s
->y
- c1
->y
, l
->s
->y
- c2
->y
);
1787 dprintf ("up step %#mS at %#mD\n", step
, l
->s
->x
, l
->s
->y
);
1788 move_corner (l
->s
, l
->s
->x
, l
->s
->y
- step
);
1789 move_corner (l
->e
, l
->e
->x
, l
->e
->y
- step
);
1794 step
= rp
.y1
- l
->s
->y
- w
;
1795 step
= gridsnap (step
);
1796 if (step
> c1
->y
- l
->s
->y
)
1797 step
= c1
->y
- l
->s
->y
;
1798 if (step
> c2
->y
- l
->s
->y
)
1799 step
= c2
->y
- l
->s
->y
;
1802 dprintf ("down step %#mS at %#mD\n", step
, l
->s
->x
, l
->s
->y
);
1803 move_corner (l
->s
, l
->s
->x
, l
->s
->y
+ step
);
1804 move_corner (l
->e
, l
->e
->x
, l
->e
->y
+ step
);
1812 rv
+= simple_optimizations ();
1814 pcb_printf ("debumpify: %ml mils saved\n", rv
/ 50);
1819 simple_corner (corner_s
* c
)
1822 if (c
->pad
|| c
->pin
|| c
->via
)
1824 if (c
->n_lines
!= 2)
1826 o1
= line_orient (c
->lines
[0], c
);
1827 o2
= line_orient (c
->lines
[1], c
);
1828 if (ORIENT (o1
) == ORIENT (o2
))
1830 if (ORIENT (o1
) == DIAGONAL
|| ORIENT (o2
) == DIAGONAL
)
1838 /* Look for sequences of simple corners we can reduce. */
1840 corner_s
*c
, *c0
, *c1
, *cc
;
1841 int l
, w
, sel
= any_line_selected ();
1844 for (c
= corners
; c
; c
= c
->next
)
1848 if (!simple_corner (c
))
1850 if (!c
->lines
[0]->line
|| !c
->lines
[1]->line
)
1852 if (sel
&& !(selected (c
->lines
[0]->line
)
1853 || selected (c
->lines
[1]->line
)))
1855 if (!sel
&& autorouted_only
1856 && !(autorouted (c
->lines
[0]->line
)
1857 || autorouted (c
->lines
[1]->line
)))
1859 dprintf ("simple at %#mD\n", c
->x
, c
->y
);
1861 c0
= other_corner (c
->lines
[0], c
);
1862 o0
= line_orient (c
->lines
[0], c
);
1863 s0
= simple_corner (c0
);
1865 c1
= other_corner (c
->lines
[1], c
);
1866 o1
= line_orient (c
->lines
[1], c
);
1867 s1
= simple_corner (c1
);
1871 dprintf ("simples at %#mD\n", c
->x
, c
->y
);
1874 for (l
= 0; l
< c0
->n_lines
; l
++)
1875 if (c0
->lines
[l
] != c
->lines
[0]
1876 && c0
->lines
[l
]->layer
== c
->lines
[0]->layer
)
1878 int o
= line_orient (c0
->lines
[l
], c0
);
1882 for (l
= 0; l
< c1
->n_lines
; l
++)
1883 if (c1
->lines
[l
] != c
->lines
[0]
1884 && c1
->lines
[l
]->layer
== c
->lines
[0]->layer
)
1886 int o
= line_orient (c1
->lines
[l
], c1
);
1892 dprintf ("orient ok\n");
1894 w
= c
->lines
[0]->line
->Thickness
/ 2 + SB
+ 1;
1896 add_line_to_rect (&rr
, c
->lines
[0]);
1897 add_line_to_rect (&rr
, c
->lines
[1]);
1908 for (cc
= corners
; cc
; cc
= cc
->next
)
1912 if (cc
->net
!= c
->net
&& intersecting_layers (cc
->layer
, c
->layer
))
1913 add_corner_to_rect_if (&rp
, cc
, &rr
);
1915 dprintf ("rp x %#mS..%#mS y %#mS..%#mS\n", rp
.x1
, rp
.x2
, rp
.y1
, rp
.y2
);
1916 if (rp
.x1
<= rp
.x2
) /* something triggered */
1919 dprintf ("unjaggy at %#mD layer %d\n", c
->x
, c
->y
, c
->layer
);
1921 move_corner (c
, c1
->x
, c0
->y
);
1923 move_corner (c
, c0
->x
, c1
->y
);
1927 rv
+= simple_optimizations ();
1936 for (i
= 0; i
< 100; i
++)
1938 j
= unjaggy_once ();
1944 printf ("%d unjagg%s \n", r
, r
== 1 ? "y" : "ies");
1951 /* Look for vias with all lines leaving the same way, try to nudge
1952 via to eliminate one or more of them. */
1954 corner_s
*c
, *c2
, *c3
;
1956 unsigned char directions
[MAX_LAYER
];
1957 unsigned char counts
[MAX_LAYER
];
1959 memset (directions
, 0, sizeof (directions
));
1960 memset (counts
, 0, sizeof (counts
));
1962 for (c
= corners
; c
; c
= c
->next
)
1964 int o
, i
, vr
, cr
, oboth
;
1965 int len
= 0, saved
= 0;
1973 memset (directions
, 0, sizeof (directions
));
1974 memset (counts
, 0, sizeof (counts
));
1976 for (i
= 0; i
< c
->n_lines
; i
++)
1978 o
= line_orient (c
->lines
[i
], c
);
1979 counts
[c
->lines
[i
]->layer
]++;
1980 directions
[c
->lines
[i
]->layer
] |= o
;
1982 for (o
= 0, i
= 0; i
< max_copper_layer
; i
++)
1992 oboth
= LEFT
| RIGHT
;
2001 for (i
= 0; i
< max_copper_layer
; i
++)
2002 if (counts
[i
] && directions
[i
] != o
&& directions
[i
] != oboth
)
2003 goto vianudge_continue
;
2006 for (i
= 0; i
< c
->n_lines
; i
++)
2008 int ll
= line_length (c
->lines
[i
]);
2009 if (line_orient (c
->lines
[i
], c
) != o
)
2015 if (c2
== 0 || len
> ll
)
2018 c2
= other_corner (c
->lines
[i
], c
);
2021 if (c2
->pad
|| c2
->pin
|| c2
->via
)
2024 /* Now look for clearance in the new position */
2025 vr
= c
->via
->Thickness
/ 2 + SB
+ 1;
2026 for (c3
= corners
; c3
; c3
= c3
->next
)
2030 if ((c3
->net
!= c
->net
&& (c3
->pin
|| c3
->via
)) || c3
->pad
)
2032 cr
= corner_radius (c3
);
2033 if (dist (c2
->x
, c2
->y
, c3
->x
, c3
->y
) < vr
+ cr
)
2034 goto vianudge_continue
;
2037 for (l
= lines
; l
; l
= l
->next
)
2041 if (l
->s
->net
!= c
->net
)
2043 int ld
= dist_line_to_point (l
, c2
);
2044 if (ld
< l
->line
->Thickness
/ 2 + vr
)
2045 goto vianudge_continue
;
2049 /* at this point, we know we can move it */
2051 dprintf ("vianudge: nudging via at %#mD by %#mS saving %#mS\n",
2052 c
->x
, c
->y
, len
, saved
);
2054 move_corner (c
, c2
->x
, c2
->y
);
2063 pcb_printf ("vianudge: %ml mils saved\n", rv
);
2070 /* Look for traces that can be moved to the other side of the board,
2071 to reduce the number of vias needed. For now, we look for simple
2072 lines, not multi-segmented lines. */
2074 int i
, rv
= 0, vrm
= 0;
2075 int any_sel
= any_line_selected ();
2077 for (l
= lines
; l
; l
= l
->next
)
2080 int my_layer
, other_layer
;
2088 if (any_sel
&& !selected (l
->line
))
2090 if (!any_sel
&& autorouted_only
&& !autorouted (l
->line
))
2093 my_layer
= l
->layer
;
2095 dprintf ("line %p on layer %d from %#mD to %#mD\n", (void *) l
,
2096 l
->layer
, l
->s
->x
, l
->s
->y
, l
->e
->x
, l
->e
->y
);
2097 for (i
= 0; i
< l
->s
->n_lines
; i
++)
2098 if (l
->s
->lines
[i
] != l
)
2100 if (other_layer
== -1)
2102 other_layer
= l
->s
->lines
[i
]->layer
;
2103 dprintf ("noting other line %p on layer %d\n",
2104 (void *) (l
->s
->lines
[i
]), my_layer
);
2106 else if (l
->s
->lines
[i
]->layer
!= other_layer
)
2108 dprintf ("saw other line %p on layer %d (not %d)\n",
2109 (void *) (l
->s
->lines
[i
]), l
->s
->lines
[i
]->layer
,
2112 goto viatrim_other_corner
;
2115 viatrim_other_corner
:
2116 if (other_layer
== -1)
2117 for (i
= 0; i
< l
->e
->n_lines
; i
++)
2118 if (l
->e
->lines
[i
] != l
)
2120 if (other_layer
== -1)
2122 other_layer
= l
->s
->lines
[i
]->layer
;
2123 dprintf ("noting other line %p on layer %d\n",
2124 (void *) (l
->s
->lines
[i
]), my_layer
);
2126 else if (l
->e
->lines
[i
]->layer
!= other_layer
)
2128 dprintf ("saw end line on layer %d (not %d)\n",
2129 l
->e
->lines
[i
]->layer
, other_layer
);
2130 goto viatrim_continue
;
2134 /* Now see if any other line intersects us. We don't need to
2135 check corners, because they'd either be pins/vias and
2136 already conflict, or pads, which we'll check here anyway. */
2138 add_point_to_rect (&r
, l
->s
->x
, l
->s
->y
, l
->line
->Thickness
);
2139 add_point_to_rect (&r
, l
->e
->x
, l
->e
->y
, l
->line
->Thickness
);
2141 for (l2
= lines
; l2
; l2
= l2
->next
)
2145 if (l2
->s
->net
!= l
->s
->net
&& l2
->layer
== other_layer
)
2147 dprintf ("checking other line %#mD to %#mD\n", l2
->s
->x
,
2148 l2
->s
->y
, l2
->e
->x
, l2
->e
->y
);
2149 if (line_in_rect (&r
, l2
))
2151 dprintf ("line from %#mD to %#mD in the way\n",
2152 l2
->s
->x
, l2
->s
->y
, l2
->e
->x
, l2
->e
->y
);
2153 goto viatrim_continue
;
2158 if (l
->layer
== other_layer
)
2160 move_line_to_layer (l
, other_layer
);
2166 vrm
= simple_optimizations ();
2168 printf ("viatrim: %d traces moved, %d vias removed\n", rv
, vrm
);
2175 int more
= 1, oldmore
= 0;
2177 while (more
!= oldmore
&& --toomany
)
2180 more
+= debumpify ();
2182 more
+= orthopull ();
2183 more
+= vianudge ();
2194 int sel
= any_line_selected ();
2197 for (c
= corners
; c
; c
= c
->next
)
2202 if (c
->n_lines
== 2 && !c
->via
&& !c
->pin
&& !c
->via
)
2204 int o1
= line_orient (c
->lines
[0], c
);
2205 int o2
= line_orient (c
->lines
[1], c
);
2206 if (ORIENT (o1
) != ORIENT (o2
)
2207 && o1
!= DIAGONAL
&& o2
!= DIAGONAL
2208 && c
->lines
[0]->line
->Thickness
== c
->lines
[1]->line
->Thickness
)
2215 while (!done
&& progress
)
2219 for (c
= corners
; c
; c
= c
->next
)
2225 int max
= line_length (c
->lines
[0]);
2226 int len
= line_length (c
->lines
[1]);
2229 corner_s
*closest_corner
= 0, *c2
, *oc1
, *oc2
;
2230 int mx
= 0, my
= 0, x
, y
;
2231 int o1
= line_orient (c
->lines
[0], c
);
2232 int o2
= line_orient (c
->lines
[1], c
);
2234 if (c
->pad
|| c
->pin
|| c
->via
)
2241 oc1
= other_corner (c
->lines
[0], c
);
2242 oc2
= other_corner (c
->lines
[1], c
);
2250 if ((sel
&& !(selected (c
->lines
[0]->line
)
2251 || selected (c
->lines
[1]->line
)))
2252 || (!sel
&& autorouted_only
2253 && !(autorouted (c
->lines
[0]->line
)
2254 || autorouted (c
->lines
[1]->line
))))
2293 ref
= c
->x
* mx
+ c
->y
* my
;
2296 bloat
= (c
->lines
[0]->line
->Thickness
/ 2 + SB
+ 1) * 3 / 2;
2298 for (c2
= corners
; c2
; c2
= c2
->next
)
2302 if (c2
!= c
&& c2
!= oc1
&& c2
!= oc2
2303 && c
->x
* mx
<= c2
->x
* mx
2304 && c
->y
* my
<= c2
->y
* my
2305 && c
->net
!= c2
->net
2306 && intersecting_layers (c
->layer
, c2
->layer
))
2308 int cr
= corner_radius (c2
);
2309 len
= c2
->x
* mx
+ c2
->y
* my
- ref
- cr
- bloat
;
2310 if (c
->x
!= c2
->x
&& c
->y
!= c2
->y
)
2312 if (len
< dist
|| (len
== dist
&& c
->miter
!= -1))
2315 closest_corner
= c2
;
2320 if (closest_corner
&& closest_corner
->miter
== -1)
2327 if (dist
< Settings
.Grid
)
2334 dist
-= dist
% Settings
.Grid
;
2360 c2
= find_corner (x
, y
, c
->layer
);
2361 if (c2
!= other_corner (c
->lines
[0], c
))
2362 split_line (c
->lines
[0], c2
);
2380 move_corner (c
, x
, y
);
2392 classify_corner (corner_s
* c
, int this_net
)
2395 if (c
->net
== this_net
)
2398 for (i
= 0; i
< c
->n_lines
; i
++)
2399 classify_corner (other_corner (c
->lines
[i
], c
), this_net
);
2405 static int this_net
= 1;
2408 for (c
= corners
; c
; c
= c
->next
)
2414 classify_corner (c
, this_net
);
2426 for (c
= corners
; c
; c
= c
->next
)
2430 printf ("%p corner %d,%d layer %d net %d\n",
2431 (void *) c
, c
->x
, c
->y
, c
->layer
, c
->net
);
2433 for (l
= lines
; l
; l
= l
->next
)
2437 printf ("%p line %p to %p layer %d\n",
2438 (void *) l
, (void *) (l
->s
), (void *) (l
->e
), l
->layer
);
2445 nudge_corner (corner_s
* c
, int dx
, int dy
, corner_s
* prev_corner
)
2450 if (prev_corner
&& (c
->pin
|| c
->pad
))
2452 move_corner (c
, ox
+ dx
, oy
+ dy
);
2453 for (l
= 0; l
< c
->n_lines
; l
++)
2455 corner_s
*oc
= other_corner (c
->lines
[l
], c
);
2456 if (oc
== prev_corner
)
2458 if (dx
&& oc
->x
== ox
)
2459 nudge_corner (oc
, dx
, 0, c
);
2460 if (dy
&& oc
->y
== oy
)
2461 nudge_corner (oc
, 0, dy
, c
);
2467 choose_example_line (corner_s
* c1
, corner_s
* c2
)
2473 dprintf ("choose_example_line\n");
2474 for (ci
= 0; ci
< 2; ci
++)
2475 for (li
= 0; li
< c
[ci
]->n_lines
; li
++)
2477 dprintf (" try[%d,%d] \033[36m<%#mD-%#mD t%#mS c%#mS f%s>\033[0m\n",
2479 c
[ci
]->lines
[li
]->s
->x
, c
[ci
]->lines
[li
]->s
->y
,
2480 c
[ci
]->lines
[li
]->e
->x
, c
[ci
]->lines
[li
]->e
->y
,
2481 c
[ci
]->lines
[li
]->line
->Thickness
,
2482 c
[ci
]->lines
[li
]->line
->Clearance
,
2483 flags_to_string (c
[ci
]->lines
[li
]->line
->Flags
, LINE_TYPE
));
2484 /* Pads are disqualified, as we want to mimic a trace line. */
2485 if (c
[ci
]->lines
[li
]->line
== (LineType
*) c
[ci
]->pad
)
2487 dprintf (" bad, pad\n");
2490 /* Lines on layers that don't connect to the other pad are bad too. */
2491 if (!intersecting_layers (c
[ci
]->lines
[li
]->layer
, c
[1 - ci
]->layer
))
2493 dprintf (" bad, layers\n");
2496 dprintf (" good\n");
2497 return c
[ci
]->lines
[li
];
2499 dprintf ("choose_example_line: none found!\n");
2504 connect_corners (corner_s
* c1
, corner_s
* c2
)
2507 line_s
*ex
= choose_example_line (c1
, c2
);
2508 LineType
*example
= ex
->line
;
2511 ("connect_corners \033[32m%#mD to %#mD, example line %#mD to %#mD l%d\033[0m\n",
2512 c1
->x
, c1
->y
, c2
->x
, c2
->y
, ex
->s
->x
, ex
->s
->y
, ex
->e
->x
, ex
->e
->y
,
2517 /* Assume c1 is the moveable one. */
2518 if (!(c1
->pin
|| c1
->pad
|| c1
->via
) && c1
->n_lines
== 1)
2521 /* Extend the line */
2522 if (c1
->lines
[0]->s
->x
== c1
->lines
[0]->e
->x
)
2523 nx
= c1
->x
, ny
= c2
->y
;
2525 nx
= c2
->x
, ny
= c1
->y
;
2526 if (nx
!= c2
->x
|| ny
!= c2
->y
)
2528 move_corner (c1
, nx
, ny
);
2529 new_line (c1
, c2
, layer
, example
);
2534 move_corner (c1
, nx
, ny
);
2540 corner_s
*nc
= find_corner (c1
->x
, c2
->y
, layer
);
2541 new_line (c1
, nc
, layer
, example
);
2542 new_line (nc
, c2
, layer
, example
);
2551 int best_dist
[MAX_LAYER
+ 1];
2552 corner_s
*best_c
[MAX_LAYER
+ 1];
2554 int left
= 0, right
= 0, top
= 0, bottom
= 0;
2561 /* Look for pins that have no connections. See if there's a corner
2562 close by that should be connected to it. This usually happens
2563 when the MUCS router needs to route to an off-grid pin. */
2567 for (c
= corners
; c
; c
= c
->next
)
2571 if (!(c
->pin
|| c
->via
|| c
->pad
))
2576 dprintf ("\ncorner %s\n", corner_name (c
));
2577 if (c
->pin
|| c
->via
)
2579 pin
= c
->pin
? c
->pin
: c
->via
;
2580 close
= pin
->Thickness
/ 2;
2581 left
= c
->x
- close
;
2582 right
= c
->x
+ close
;
2583 bottom
= c
->y
- close
;
2588 close
= c
->pad
->Thickness
/ 2 + 1;
2589 left
= djmin (c
->pad
->Point1
.X
, c
->pad
->Point2
.X
) - close
;
2590 right
= djmax (c
->pad
->Point1
.X
, c
->pad
->Point2
.X
) + close
;
2591 bottom
= djmin (c
->pad
->Point1
.Y
, c
->pad
->Point2
.Y
) - close
;
2592 top
= djmax (c
->pad
->Point1
.Y
, c
->pad
->Point2
.Y
) + close
;
2593 if (c
->pad
->Point1
.X
== c
->pad
->Point2
.X
)
2595 int hy
= (c
->pad
->Point1
.Y
+ c
->pad
->Point2
.Y
) / 2;
2596 dprintf ("pad y %#mS %#mS hy %#mS c %#mS\n", c
->pad
->Point1
.Y
,
2597 c
->pad
->Point2
.Y
, hy
, c
->y
);
2605 int hx
= (c
->pad
->Point1
.X
+ c
->pad
->Point2
.X
) / 2;
2606 dprintf ("pad x %#mS %#mS hx %#mS c %#mS\n", c
->pad
->Point1
.X
,
2607 c
->pad
->Point2
.X
, hx
, c
->x
);
2615 dprintf ("%s x %#mS-%#mS y %#mS-%#mS\n", corner_name (c
), left
, right
, bottom
, top
);
2616 for (l
= 0; l
<= max_copper_layer
; l
++)
2618 best_dist
[l
] = close
* 2;
2622 for (c2
= corners
; c2
; c2
= c2
->next
)
2628 lt
= corner_radius (c2
);
2631 && !(c2
->pin
|| c2
->pad
|| c2
->via
)
2632 && intersecting_layers (c
->layer
, c2
->layer
)
2633 && c2
->x
>= left
- lt
2634 && c2
->x
<= right
+ lt
2635 && c2
->y
>= bottom
- lt
&& c2
->y
<= top
+ lt
)
2637 int d
= dist (c
->x
, c
->y
, c2
->x
, c2
->y
);
2638 if (pin
&& d
> pin
->Thickness
/ 2 + lt
)
2640 if (c2
->n_lines
== 1)
2643 dprintf ("found orphan %s vs %s\n", corner_name (c2
),
2645 connect_corners (c
, c2
);
2649 if (best_c
[c2
->layer
] == 0
2650 || c2
->n_lines
< best_c
[c2
->layer
]->n_lines
2651 || (d
< best_dist
[c2
->layer
]
2652 && c2
->n_lines
<= best_c
[c2
->layer
]->n_lines
))
2654 best_dist
[c2
->layer
] = d
;
2655 best_c
[c2
->layer
] = c2
;
2656 dprintf ("layer %d best now %s\n", c2
->layer
,
2660 if (!got_one
&& c
->n_lines
== (c
->pad
? 1 : 0))
2662 for (l
= 0; l
<= max_copper_layer
; l
++)
2664 dprintf ("best[%d] = %s\n", l
, corner_name (best_c
[l
]));
2665 for (l
= 0; l
<= max_copper_layer
; l
++)
2668 dprintf ("move %s to %s\n", corner_name (best_c
[l
]),
2670 connect_corners (best_c
[l
], c
);
2679 /* Now look for line ends that don't connect, see if they need to be
2680 extended to intersect another line. */
2681 for (c
= corners
; c
; c
= c
->next
)
2688 if (c
->pin
|| c
->via
|| c
->pad
)
2690 if (c
->n_lines
!= 1)
2694 lo
= line_orient (l
, c
);
2695 dprintf ("line end %#mD orient %d\n", c
->x
, c
->y
, lo
);
2697 for (t
= lines
; t
; t
= t
->next
)
2701 if (t
->layer
!= c
->lines
[0]->layer
)
2703 switch (lo
) /* remember, orient is for the line relative to the corner */
2706 if (t
->s
->x
== t
->e
->x
2709 c
->x
+ (l
->line
->Thickness
+ t
->line
->Thickness
) / 2
2710 && ((t
->s
->y
< c
->y
&& c
->y
< t
->e
->y
)
2711 || (t
->e
->y
< c
->y
&& c
->y
< t
->s
->y
)))
2713 dprintf ("found %#mD - %#mD\n", t
->s
->x
, t
->s
->y
, t
->e
->x
, t
->e
->y
);
2714 move_corner (c
, t
->s
->x
, c
->y
);
2718 if (t
->s
->x
== t
->e
->x
2721 c
->x
- (l
->line
->Thickness
+ t
->line
->Thickness
) / 2
2722 && ((t
->s
->y
< c
->y
&& c
->y
< t
->e
->y
)
2723 || (t
->e
->y
< c
->y
&& c
->y
< t
->s
->y
)))
2725 dprintf ("found %#mD - %#mD\n", t
->s
->x
, t
->s
->y
, t
->e
->x
, t
->e
->y
);
2726 move_corner (c
, t
->s
->x
, c
->y
);
2730 if (t
->s
->y
== t
->e
->y
2733 c
->y
+ (l
->line
->Thickness
+ t
->line
->Thickness
) / 2
2734 && ((t
->s
->x
< c
->x
&& c
->x
< t
->e
->x
)
2735 || (t
->e
->x
< c
->x
&& c
->x
< t
->s
->x
)))
2737 dprintf ("found %#mD - %#mD\n", t
->s
->x
, t
->s
->y
, t
->e
->x
, t
->e
->y
);
2738 move_corner (c
, c
->x
, t
->s
->y
);
2742 if (t
->s
->y
== t
->e
->y
2745 c
->y
- (l
->line
->Thickness
+ t
->line
->Thickness
) / 2
2746 && ((t
->s
->x
< c
->x
&& c
->x
< t
->e
->x
)
2747 || (t
->e
->x
< c
->x
&& c
->x
< t
->s
->x
)))
2749 dprintf ("found %#mD - %#mD\n", t
->s
->x
, t
->s
->y
, t
->e
->x
, t
->e
->y
);
2750 move_corner (c
, c
->x
, t
->s
->y
);
2759 pad_orient (PadType
* p
)
2761 if (p
->Point1
.X
== p
->Point2
.X
)
2763 if (p
->Point1
.Y
== p
->Point2
.Y
)
2775 dprintf ("\ndj: padcleaner\n");
2776 for (l
= lines
; l
; l
= nextl
)
2786 dprintf ("dj: line %p\n", (void *) l
);
2789 if (l
->s
->pad
&& l
->s
->pad
== l
->e
->pad
)
2792 ALLPAD_LOOP (PCB
->Data
);
2795 TEST_FLAG (ONSOLDERFLAG
, element
) ? LT_BOTTOM
: LT_TOP
;
2797 if (layer_type
[l
->layer
] != layerflag
)
2801 close
= pad
->Thickness
/ 2 + 1;
2802 add_point_to_rect (&r
, pad
->Point1
.X
, pad
->Point1
.Y
, close
- SB
/ 2);
2803 add_point_to_rect (&r
, pad
->Point2
.X
, pad
->Point2
.Y
, close
- SB
/ 2);
2804 if (pin_in_rect (&r
, l
->s
->x
, l
->s
->y
, 0)
2805 && pin_in_rect (&r
, l
->e
->x
, l
->e
->y
, 0)
2806 && ORIENT (line_orient (l
, 0)) == pad_orient (pad
))
2809 ("padcleaner %#mD-%#mD %#mS vs line %#mD-%#mD %#mS\n",
2810 pad
->Point1
.X
, pad
->Point1
.Y
, pad
->Point2
.X
, pad
->Point2
.Y
,
2811 pad
->Thickness
, l
->s
->x
, l
->s
->y
, l
->e
->x
, l
->e
->y
,
2812 l
->line
->Thickness
);
2823 grok_layer_groups ()
2826 LayerGroupType
*l
= &(PCB
->LayerGroups
);
2828 solder_layer
= component_layer
= -1;
2829 for (i
= 0; i
< max_copper_layer
; i
++)
2832 layer_groupings
[i
] = 0;
2834 for (i
= 0; i
< max_group
; i
++)
2837 for (j
= 0; j
< l
->Number
[i
]; j
++)
2839 if (l
->Entries
[i
][j
] == bottom_silk_layer
)
2841 if (l
->Entries
[i
][j
] == top_silk_layer
)
2844 for (j
= 0; j
< l
->Number
[i
]; j
++)
2846 if (l
->Entries
[i
][j
] < max_copper_layer
)
2848 layer_type
[l
->Entries
[i
][j
]] |= f
;
2849 layer_groupings
[l
->Entries
[i
][j
]] = i
;
2850 if (solder_layer
== -1 && f
== LT_BOTTOM
)
2851 solder_layer
= l
->Entries
[i
][j
];
2852 if (component_layer
== -1 && f
== LT_TOP
)
2853 component_layer
= l
->Entries
[i
][j
];
2859 static const char djopt_syntax
[] =
2860 "djopt(debumpify|unjaggy|simple|vianudge|viatrim|orthopull|splitlines)\n"
2861 "djopt(auto) - all of the above\n"
2864 static const char djopt_help
[] =
2865 "Perform various optimizations on the current board.";
2867 /* %start-doc actions djopt
2869 The different types of optimizations change your board in order to
2870 reduce the total trace length and via count.
2875 Looks for U-shaped traces that can be shortened or eliminated.
2878 Looks for corners which could be flipped to eliminate one or more
2879 corners (i.e. jaggy lines become simpler).
2882 Removing uneeded vias, replacing two or more trace segments in a row
2883 with a single segment. This is usually performed automatically after
2884 other optimizations.
2887 Looks for vias where all traces leave in the same direction. Tries to
2888 move via in that direction to eliminate one of the traces (and thus a
2892 Looks for traces that go from via to via, where moving that trace to a
2893 different layer eliminates one or both vias.
2896 Looks for chains of traces all going in one direction, with more
2897 traces orthogonal on one side than on the other. Moves the chain in
2898 that direction, causing a net reduction in trace length, possibly
2899 eliminating traces and/or corners.
2902 Looks for lines that pass through vias, pins, or pads, and splits them
2903 into separate lines so they can be managed separately.
2906 Performs the above options, repeating until no further optimizations
2910 Replaces 90 degree corners with a pair of 45 degree corners, to reduce
2911 RF losses and trace length.
2918 ActionDJopt (int argc
, char **argv
, Coord x
, Coord y
)
2920 char *arg
= argc
> 0 ? argv
[0] : 0;
2921 int layn
, saved
= 0;
2929 grok_layer_groups ();
2931 ELEMENT_LOOP (PCB
->Data
);
2934 c
= find_corner (pin
->X
, pin
->Y
, -1);
2941 TEST_FLAG (ONSOLDERFLAG
, pad
) ? solder_layer
: component_layer
;
2942 line_s
*ls
= (line_s
*) malloc (sizeof (line_s
));
2946 ls
->s
= find_corner (pad
->Point1
.X
, pad
->Point1
.Y
, layern
);
2948 ls
->e
= find_corner (pad
->Point2
.X
, pad
->Point2
.Y
, layern
);
2951 ls
->line
= (LineType
*) pad
;
2952 add_line_to_corner (ls
, ls
->s
);
2953 add_line_to_corner (ls
, ls
->e
);
2958 VIA_LOOP (PCB
->Data
);
2959 /* hace don't mess with vias that have thermals */
2960 /* but then again don't bump into them
2961 if (!TEST_FLAG(ALLTHERMFLAGS, via))
2964 c
= find_corner (via
->X
, via
->Y
, -1);
2970 if (NSTRCMP (arg
, "splitlines") == 0)
2972 if (canonicalize_lines ())
2973 IncrementUndoSerialNumber ();
2977 for (layn
= 0; layn
< max_copper_layer
; layn
++)
2979 LayerType
*layer
= LAYER_PTR (layn
);
2985 if(autorouted_only
&& !autorouted (line
))
2988 /* don't mess with thermals */
2989 if (TEST_FLAG (USETHERMALFLAG
, line
))
2992 if (line
->Point1
.X
== line
->Point2
.X
&&
2993 line
->Point1
.Y
== line
->Point2
.Y
)
2995 RemoveLine (layer
, line
);
2999 ls
= (line_s
*) malloc (sizeof (line_s
));
3003 ls
->s
= find_corner (line
->Point1
.X
, line
->Point1
.Y
, layn
);
3004 ls
->e
= find_corner (line
->Point2
.X
, line
->Point2
.Y
, layn
);
3006 add_line_to_corner (ls
, ls
->s
);
3007 add_line_to_corner (ls
, ls
->e
);
3015 canonicalize_lines ();
3021 if (NSTRCMP (arg
, "debumpify") == 0)
3022 saved
+= debumpify ();
3023 else if (NSTRCMP (arg
, "unjaggy") == 0)
3024 saved
+= unjaggy ();
3025 else if (NSTRCMP (arg
, "simple") == 0)
3026 saved
+= simple_optimizations ();
3027 else if (NSTRCMP (arg
, "vianudge") == 0)
3028 saved
+= vianudge ();
3029 else if (NSTRCMP (arg
, "viatrim") == 0)
3030 saved
+= viatrim ();
3031 else if (NSTRCMP (arg
, "orthopull") == 0)
3032 saved
+= orthopull ();
3033 else if (NSTRCMP (arg
, "auto") == 0)
3034 saved
+= automagic ();
3035 else if (NSTRCMP (arg
, "miter") == 0)
3039 printf ("unknown command: %s\n", arg
);
3047 IncrementUndoSerialNumber ();
3051 HID_Action djopt_action_list
[] = {
3052 {"djopt", 0, ActionDJopt
,
3053 djopt_help
, djopt_syntax
}
3055 {"OptAutoOnly", 0, djopt_set_auto_only
,
3056 djopt_sao_help
, djopt_sao_syntax
}
3059 REGISTER_ACTIONS (djopt_action_list
)